Pixelabfrage extrem langsam [erledigt]

Für Probleme bezüglich Grafik, Audio, GL, ACS, ...
siro
Beiträge: 758
Registriert: Di 23. Aug 2016, 14:25
OS, Lazarus, FPC: Windows 11
CPU-Target: 64Bit
Wohnort: Berlin

Pixelabfrage extrem langsam [erledigt]

Beitrag von siro »

Hallo zusammen,
ich dachte eben meine Software ist abgestürzt... :shock:
Habe dann festgestellt, das meine vermutlich völlig falsche Vorgehensweise für mein Problem daran schuld ist.

Was will ich machen ?
Ich möchte in einer Paintbox feststellen wo sich der erste Pixel ungleich weiss befindet.
und zwar von links , von rechts, von oben und von unten. Im Prinzip suche ein umschließendes Rechteck meiner dargestellten Grafik.

Dazu meine Funktionen:

Code: Alles auswählen

{------------------------------------------------------------------------------}
{ sucht von links an den ersten Pixel ungleich weiss   }
{ liefert 0.. width-1 zurück wenn Pixel gefunden wurde }
{ liefert -1 zurück wenn kein Pixel gefunden wurde     }
function FindLeft(canvas:TCanvas):Integer;
var x,y,width,height:Integer;
begin
  width :=canvas.ClipRect.Right;
  height:=canvas.ClipRect.Bottom;
  for x:=0 to width-1 do begin   { horizontal von links nach rechts suchen }
    result:=x;
    for y:=0 to height-1 do begin  { vertikal von oben nach unten suchen }
      if canvas.Pixels[x,y]<>clWhite then exit; { Pixel gefunden, dann Ende }
    end;
  end;
  result:=-1;  { result = -1 wenn keinen Pixel gefunden }
end;
{------------------------------------------------------------------------------}
{ sucht von rechts an den ersten Pixel ungleich weiss  }
{ liefert 0.. width-1 zurück wenn Pixel gefunden wurde }
{ liefert -1 zurück wenn kein Pixel gefunden wurde     }
function FindRight(canvas:TCanvas):Integer;
var x,y,width,height:Integer;
begin
  width :=canvas.ClipRect.Right;
  height:=canvas.ClipRect.Bottom;
  for x := width-1 DownTo 0 do begin { horizontal von rechts nach links suchen }
    result:=x;
    for y:=0 to height-1 do begin  { vertikal von oben nach unten suchen }
      if canvas.Pixels[x,y]<>clWhite then exit;{ wenn Pixel gefunden dann Ende }
    end;
  end;
  result:=-1;  { result = -1 wenn keinen Pixel gefunden }
end;
{------------------------------------------------------------------------------}
{ sucht von oben nach unten den ersten Pixel ungleich weiss  }
{ liefert 0.. height-1 zurück wenn Pixel gefunden wurde }
{ liefert -1 zurück wenn kein Pixel gefunden wurde     }
function FindTop(canvas:TCanvas):Integer;
var x,y,width,height:Integer;
begin
  width :=canvas.ClipRect.Right;
  height:=canvas.ClipRect.Bottom;
  for y:=0 to height-1 do begin  { vertikal von oben nach unten suchen }
    result:=y;
    for x := 0 to width-1 do begin   { horizontal von links nach rechts suchen }
      if canvas.Pixels[x,y]<>clWhite then exit;{ wenn Pixel gefunden dann Ende }
    end;
  end;
  result:=-1;  { result = -1 wenn keinen Pixel gefunden }
end;
{------------------------------------------------------------------------------}
{ sucht von unten nach oben den ersten Pixel ungleich weiss  }
{ liefert 0..height-1 zurück, wenn ein Pixel gefunden wurde  }
{ liefert -1 zurück, wenn kein Pixel gefunden wurde          }
{ UPPS, bei einer Paintbox von 310*170 Pixeln dauert das rund 30 Sekunden !!!!!!! }
function FindBottom(canvas:TCanvas):Integer;
var x,y,w,h:Integer;
begin
  w:=canvas.ClipRect.Right;
  h:=canvas.ClipRect.Bottom;
  for y:=h-1 DownTo 0  do begin  { vertikal von unten nach oben suchen }
    result:=y;
    for x := 0 to w-1 do begin   { horizontal von links nach rechts suchen }
      if canvas.Pixels[x,y]<>clWhite then exit;{ wenn Pixel gefunden dann Ende }
    end;
  end;
  result:=-1;  { result = -1 wenn keinen Pixel gefunden }
end;

Das dauert bei einer Paintbox mit 310*170 Pixel für jede Funktion so rund 30 Sekunden :shock:
und ist natürlich so völlig inakzeptabel.

Nun die Frage an die Experten, wie macht man das sinnvoller/schneller ?
Ich erwarte keine fertige Lösung von euch, nur einen neuen Ansatzpunkt für dieses Problem.
Manchmal sieht man ja den Wald vor Bäumen nicht.... :P
Zuletzt geändert von siro am Mo 21. Apr 2025, 16:33, insgesamt 1-mal geändert.
Grüße von Siro
Bevor ich "C" ertragen muß, nehm ich lieber Lazarus...

Benutzeravatar
Zvoni
Beiträge: 363
Registriert: Fr 5. Jul 2024, 08:26
OS, Lazarus, FPC: Windoof 10 Pro (Laz 2.2.2 FPC 3.2.2)
CPU-Target: 32Bit
Wohnort: BW

Re: Pixelabfrage extrem langsam

Beitrag von Zvoni »

Du brauchst nur zwei Funktion statt der vier, sofern es denn tatsächlich ein Rechteck ist.
FindLeft liefert dir ja die "Linke obere" Ecke (auch wenn du es im Result nicht zurück gibst. Umschreiben auf Procedure mit "var/out"-Argumenten)

Code: Alles auswählen

Procedure FindLeftTop(Canvas:TCanvas;out ATop:Integer {Ist y bei dir}; out ALeft:Integer {Ist x bei dir});
FindRight würde ich umschreiben auf "von rechts nach links und von unten nach oben". Damit bekommst du die "Rechte untere" Ecke. (Rest siehe FindLeft oben drüber)

Oder ich hab etwas grundsätzlich falsch verstanden.

Ein weiterer Ansatz wäre statt einem "<>" einen Bitweisen And zu machen.

Aircode

Code: Alles auswählen

If Pixel[x,y] And clWhite Then IstWeiss Else NichtWeiss
Ein System sie alle zu knechten, ein Code sie alle zu finden,
Eine IDE sie ins Dunkel zu treiben, und an das Framework ewig zu binden,
Im Lande Redmond, wo die Windows drohn.

Benutzeravatar
Jorg3000
Lazarusforum e. V.
Beiträge: 359
Registriert: So 10. Okt 2021, 10:24
OS, Lazarus, FPC: Win64
Wohnort: NRW

Re: Pixelabfrage extrem langsam

Beitrag von Jorg3000 »

Hi!
Der Zugriff auf Canvas.Pixels[x,y] ist ultra-lahm. Schneller geht es, wenn man es zuvor in ein Bitmap kopiert und darin die Bytes untersucht.

Hier meine Lösung dazu:

Code: Alles auswählen

function CanvasToBMP(gc: TGraphicControl): TBitmap;
var r: TRect;
begin
  Result := TBitmap.Create;
  Result.PixelFormat := pf24bit;
  Result.SetSize(gc.Width, gc.Height);

  r.Left := 0;
  r.Top  := 0;
  r.Right  := gc.Width;
  r.Bottom := gc.Height;

  Result.Canvas.CopyRect(r, gc.Canvas, r);
end;


function FindPicture(bmp: TBitmap; out LeftX, TopY, RightX, BottomY: Integer): Boolean;
var
  x, y: Integer;
  p: PByte;
begin
  Result := false;
  if bmp.PixelFormat <> pf24bit then Exit;

  LeftX  := bmp.Width;
  RightX := 0;
  TopY   := bmp.Height;
  BottomY := 0;

  for y := 0 to bmp.Height - 1 do
   begin
    p := bmp.ScanLine[y] -3;
    for x := 0 to bmp.Width-1 do
      begin
       inc(p,3);
       if (p^{blue}=255) and ((p+1)^{green}=255) and ((p+2)^{red}=255) then Continue;

       if x < LeftX   then LeftX := x;
       if x > RightX  then RightX := x;
       if y < TopY    then TopY := y;
       if y > BottomY then BottomY := y;
       Result := true;
      end;
   end;

  if not Result then
   begin
    LeftX := -1;
    TopY := -1;
    RightX := -1;
    BottomY := -1;
   end;
end;



procedure TForm1.Button4Click(Sender: TObject);
var 
  bmp: TBitmap;
  LeftX, TopY, RightX, BottomY: Integer;
begin
  bmp := CanvasToBMP(PaintBox1);
  
  if FindPicture(bmp,{out}LeftX, TopY, RightX, BottomY)
    then ShowMessage( IntToStr(LeftX)+' '+IntToStr(TopY)+' '+IntToStr(RightX)+' '+IntToStr(BottomY) );
    
  bmp.Destroy;
end;
Mach damit mal einen Geschwindigkeitstest, bin gespannt.
Grüße, Jörg

Benutzeravatar
Zvoni
Beiträge: 363
Registriert: Fr 5. Jul 2024, 08:26
OS, Lazarus, FPC: Windoof 10 Pro (Laz 2.2.2 FPC 3.2.2)
CPU-Target: 32Bit
Wohnort: BW

Re: Pixelabfrage extrem langsam

Beitrag von Zvoni »

Jorg3000 hat geschrieben: Do 17. Apr 2025, 15:47 Hi!
Der Zugriff auf Canvas.Pixels[x,y] ist ultra-lahm. Schneller geht es, wenn man es zuvor in ein Bitmap kopiert und darin die Bytes untersucht.

Hier meine Lösung dazu:

Mach damit mal einen Geschwindigkeitstest, bin gespannt.
Grüße, Jörg
Hmm....interessant....
das einzige was mich stört, ist dass du dennoch alle "Linien" durchläufst.
Idee Algoritmus:
1) Äussere Schleife: Von oben nach unten (wie in deinem Code).
2) Führe ScanLine aus, und durchlaufe die Bytes von Links nach Rechts.
3) Falls in dieser Linie "etwas" NICHT weiss ist (Dein If-Then), dann hast du TopLeft. Springe aus Innerer Schleife.
4) In dieser Linie (!!!) laufst du die ScanLine von Rechts nach Links durch (!!). Das erste ungleich Weiss ist TopRight. Springe aus Innerer UND äusserer Schleife.
5) Starte neue äussere Schleife, aber von unten nach oben
6) Führe in dieser neuen äusseren Schleife die Schritte wie beschrieben in 2 bis 4 durch, bekommst aber jedoch BottomLeft und BottomRight als Ergebnis
Ein System sie alle zu knechten, ein Code sie alle zu finden,
Eine IDE sie ins Dunkel zu treiben, und an das Framework ewig zu binden,
Im Lande Redmond, wo die Windows drohn.

Benutzeravatar
Jorg3000
Lazarusforum e. V.
Beiträge: 359
Registriert: So 10. Okt 2021, 10:24
OS, Lazarus, FPC: Win64
Wohnort: NRW

Re: Pixelabfrage extrem langsam

Beitrag von Jorg3000 »

Zvoni hat geschrieben: Do 17. Apr 2025, 16:00dann hast du TopLeft.
Nur wenn die gesuchte Grafik ein Rechteck ist.
Sie könnte aber auch unförmig sein oder z.B. ein Kreis. Dann muss man alle Zeilen durchlaufen, um die breiteste Stelle zu finden.

Mathias
Beiträge: 6899
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Pixelabfrage extrem langsam

Beitrag von Mathias »

Hi!
Der Zugriff auf Canvas.Pixels[x,y] ist ultra-lahm. Schneller geht es, wenn man es zuvor in ein Bitmap kopiert und darin die Bytes untersucht.
Oder man geht direkt über TRawImages, dies ist so ziemlich der schnellste Zugriff.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

wennerer
Beiträge: 607
Registriert: Di 19. Mai 2015, 20:05
OS, Lazarus, FPC: Linux Mint 20 Cinnamon,Lazarus 2.2.6 (rev lazarus_2_2_6) FPC 3.2.2 x86_64-linux-
CPU-Target: x86_64-linux-gtk2

Re: Pixelabfrage extrem langsam

Beitrag von wennerer »

Hallo Siro,
ich hab mal schnell was zusammen geklickt (unter Linux). Vielleicht gefällt es dir.
Sehr interssant: https://wiki.lazarus.freepascal.org/Dev ... TLazCanvas

Viele Grüße
Bernd
Dateianhänge
project1.zip
(140.29 KiB) 108-mal heruntergeladen

siro
Beiträge: 758
Registriert: Di 23. Aug 2016, 14:25
OS, Lazarus, FPC: Windows 11
CPU-Target: 64Bit
Wohnort: Berlin

Re: Pixelabfrage extrem langsam

Beitrag von siro »

Ersteinmal vielen Dank für eure Anregungen und auch euren Code.

Dickes Danke an Jörg, das hat sofort geklappt und geht natürlich WESENTLICH schneller.
Bernd kam eben noch mit Code hinterher.
Den schaue ich mir auch nochmal genauer an, lief auf Windows nicht sofort, habe es aber hinbekommen.

Es ist tatsächlich so, dass ich keine rechteckigen Bilddaten habe, sondern es geht um einzelne Buchstaben in schwarz weiss.
Die zeichne ich in verschiedenen Größen und erzeuge mir aus den Pixeln einen speziellen Code für ein kleines Display.
Embedded Project. Sozusagen ein Fontgenerator den ich da grad mache.

Ich versteh noch nicht alles, aber ich forsche noch an eurem Code... :wink:
Auf jeden Fall vielen Dank euch allen und genießt das Osterwochenende.
Grüße von Siro
Bevor ich "C" ertragen muß, nehm ich lieber Lazarus...

Benutzeravatar
Jorg3000
Lazarusforum e. V.
Beiträge: 359
Registriert: So 10. Okt 2021, 10:24
OS, Lazarus, FPC: Win64
Wohnort: NRW

Re: Pixelabfrage extrem langsam

Beitrag von Jorg3000 »

Guten Morgen!
siro hat geschrieben: Do 17. Apr 2025, 18:16 Dickes Danke an Jörg, das hat sofort geklappt und geht natürlich WESENTLICH schneller.
Das freut mich sehr!
siro hat geschrieben: Do 17. Apr 2025, 18:16 Ich versteh noch nicht alles, aber ich forsche noch an eurem Code... :wink:
Bezüglich deines ursprünglichen Plans:
Bei ungleichmäßig geformten Buchstaben muss man sich von allen 4 Seiten nähern. Würde man das in 4 einzelnen Funktionen machen, wäre es insbesondere von-links und von-rechts besonders langsam (Erklärung unten).

Mein Ansatz mit TBitmap.ScanLine (Zugriff auf die RGB-Rohdaten) durchläuft zwar immer alle Pixel, tut dies aber um ein vielfaches schneller. Ich denke für deine Anforderung ist es die schnellste Lösung.
Ebenso kann man mit TLazIntfImage.GetDataLineStart (Vorschlag von Bernd) oder TBGRABitmap.ScanLine arbeiten. Das ist genau das gleiche Prinzip, jedoch hat es den Nachteil, dass dann die Zeichenfläche 2x kopiert werden muss, nämlich zuerst vom Canvas in ein TBitmap und dann nochmal in ein TLazIntfImage oder TBGRABitmap. Dabei wird die Reihenfolge der R,G,B-Bytes getauscht, weshalb der Kopiervorgang nicht schnell ist. Deshalb bleibe ich hier einfach beim TBitmap.

Der Zugriff auf Pixel über X,Y-Koordinaten ist wesentlich langsamer, weil zuerst eine Multiplikation mit Y durchgeführt werden muss, um an die Speicheradresse des Zeilenanfangs zu gelangen, und dann noch eine Multiplikation 3*X, um an die Zieladresse zu kommen. Deine Paintbox hat 310*170 = 52.700 Pixel, was über 100.000 Multiplikation bedeutet, von denen jede relativ langsam ist.
Hingegen wird beim Zugriff über die ScanLine nur eine Multiplikation pro Zeile (also insgesamt nur 170) durchgeführt, sofern man die Variable X nicht verwendet. In meinem Code wird der Speicher linear durchlaufen, weshalb beim Farb-Vergleich kein Zugriff auf X nötig ist.

Außerdem sollte man die innere Schleife so schnell wie möglich gestalten. Wenn man darin erst Variablen R,G,B setzt und dann wieder per RGB() zusammenfügt, ist ein Teil des Geschwindkeitsvorteils wieder zunichte gemacht.
Grüße, Jörg

Benutzeravatar
Jorg3000
Lazarusforum e. V.
Beiträge: 359
Registriert: So 10. Okt 2021, 10:24
OS, Lazarus, FPC: Win64
Wohnort: NRW

Re: Pixelabfrage extrem langsam

Beitrag von Jorg3000 »

PS:
Brauchst du die Paintbox überhaupt? Man kann einen Buchstaben auch direkt auf ein Bitmap schreiben. Dadurch könnte man sich das Umkopieren aus der Paintbox sparen.

Code: Alles auswählen

  bmp:=TBitmap.Create;
  bmp.SetSize(310,170);

  bmp.Canvas.Brush.Color:=clWhite;
  bmp.Canvas.FillRect(Rect(0,0, 310,170));

  bmp.Canvas.Font.Name := 'Arial';
  bmp.Canvas.Font.Size := 130;
  bmp.Canvas.Font.Color  := clBlack;
  bmp.Canvas.Brush.Style := bsClear;  // durchsichtiger Hintergrund
  bmp.Canvas.TextOut(0,0,'A');

  if FindPicture(bmp, {out}LeftX, TopY, RightX, BottomY)
    then ShowMessage( IntToStr(LeftX)+' '+IntToStr(TopY)+' '+IntToStr(RightX)+' '+IntToStr(BottomY) );

  bmp.Destroy;
Für mehrere Durchläufe (Buchstaben) kann man natürlich das erzeugte bmp mehrfach verwenden, um die jeweilen Create/Destroy und .SetSize() zu sparen.

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6762
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Re: Pixelabfrage extrem langsam

Beitrag von af0815 »

Die Frage ist, ob man für die Aufgabenstellung (Bild Generator für Embedded) das Pferd nicht anders aufzäumen sollte.

Das ganze in einen Array im Speicher halten und nur für die Visualisierung in der GUI umkopieren. Vor allen, brauche ich bei Embedded den RGB Farbraum ?
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

wp_xyz
Beiträge: 5129
Registriert: Fr 8. Apr 2011, 09:01

Re: Pixelabfrage extrem langsam

Beitrag von wp_xyz »

Oder noch anders: gleich direkt die Fontbeschreibung in der ttf-Datei auslesen. Es gibt dafür mehrere FreeType-Units mit der man das erledigen kann. Im Anhang ein Beispiel, das auf dem Demo-Programm im Ordner examples/lazFreeType der Lazarus-Installation beruht. Falls dir auffällt, dass die BoundingBoxes um die Zeichen oft um 1 Pixel zu groß sind: das liegt wahrscheinlich daran, dass FreeType intern mit Floats rechnet, die auf Integer gerundet werden müssen. Aber ich denke, dasselbe Problem wirst du auch haben, denn die Zeichen werden mit Antialiasing ausgegeben, so dass kaum ein Zeichen abrupt aufhört, sondern mit einem Grauverlauf, und wenn du nun nach dem ersten Pixel suchst, das von weiß verschieden ist, wird dieses im Mittel auch etwas vom "eigentlichen" Zeichenrand entfernt sein.
Dateianhänge
boundingbox.png
boundingbox.png (9.54 KiB) 792 mal betrachtet
Character_BoundingBox.zip
(3.52 KiB) 94-mal heruntergeladen

Mathias
Beiträge: 6899
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Pixelabfrage extrem langsam

Beitrag von Mathias »

Es ist tatsächlich so, dass ich keine rechteckigen Bilddaten habe, sondern es geht um einzelne Buchstaben in schwarz weiss.
Die zeichne ich in verschiedenen Größen und erzeuge mir aus den Pixeln einen speziellen Code für ein kleines Display.
Embedded Project. Sozusagen ein Fontgenerator den ich da grad mache.
Was auch noch eine Alternative ist, mit SDL_TTF. Da kann man die einzelnen Zeichen auch als Bitmap abspeichern.
Evtl, noch Cairo, oder wie wp_xyz schon sagt, FreeType.
Das TBitmap was die LCL bietet ist ein echt mühsamer Bock für solche Sachen.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

siro
Beiträge: 758
Registriert: Di 23. Aug 2016, 14:25
OS, Lazarus, FPC: Windows 11
CPU-Target: 64Bit
Wohnort: Berlin

Re: Pixelabfrage extrem langsam

Beitrag von siro »

Moin zusammen,
ooooh, so viele neue Anregungen, :shock:
die Infos reichen ja noch bis Pfingsten... :)

Erstmal auch vielen Dank an wp_xyz, das ist natürlich eine ganz andere Herangehensweise.
Diese Units/Funktionen kannte ich noch garnicht.

@0815
Du hast völlig recht, ich brauche überhaupt keinen Farbraum, das ist ein einfaches Schwarz/Weiss Display

Ich teste noch ein bischen rum, Infos habe ich ja nun genug.

Es geht lediglich darum Fonts zu erstellen für dieses Mini Display
Display_128x32.png
Display_128x32.png (179.81 KiB) 695 mal betrachtet
ich weis, da gibt es auch Fertiges von Arduino usw, aber ich mache das gerne alles selber für einen Microchip PIC :P
Danke an euch alle
Grüße von Siro
Bevor ich "C" ertragen muß, nehm ich lieber Lazarus...

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6762
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Re: Pixelabfrage extrem langsam

Beitrag von af0815 »

Sieht ja gut aus. Was verwendest du da für Komponenten ?
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

Antworten