Zusammenhängene Pixel zählen

[Eichhoernchen]

Hi, ich hatte vor eine function zu schreiben, die aus einem schwarz/weiß Bild alle Stücke heraus löscht, bei denen die Anzahl der zusammenhängenden schwarzen Pixel kleiner als 100 ist.

Ich hab mir dass folgender maßen gedacht, ein array of array of TPoint;
Die 1. Array dimension gibt den Pixelbrocken an, und in die 2. Dimension werden dann alle TPoint Werte des Pixelbrockens gespeichert.

Ich habe mir jetzt folgenden Code zusammengedacht aber leider klappt es nicht jedoch weiß ich auch nicht wo ich einen Fehler gemacht hab, also bitte helft mir(ich glaube bei der Verwendung von setlength, bin aber nicht sicher)

Delphi-Quellcode:

function killsmallareas(bmp : TBitmap) : TBitmap;
var i, j, k, l : integer;
    Polygones : array of array of TPoint;
    found : boolean;
Begin
result := TBitmap.Create;
result.Width := bmp.Width;
result.Height := bmp.Height;
result.PixelFormat := bmp.PixelFormat;
SetLength(polygones, 1, 1);
 for i := 0 to bmp.Width - 1 do
  for j := 0 to bmp.Height - 1 do
   Begin
    if bmp.Canvas.Pixels[i, j] = clblack
      then Begin
            with bmp.Canvas do
             Begin
               if (Pixels[i-1, j] = clblack) or (Pixels[i-1, j-1] = clblack)
               or (Pixels[i, j-1] = clblack) or (Pixels[i+1, j-1] = clblack)
               or (Pixels[i+1, j] = clblack) or (Pixels[i+1, j+1] = clblack)
               or (Pixels[i, j+1] = clblack) or (Pixels[i-1, j+1] = clblack)
                 then Begin
                       k := 0;
                       found := false;
                       while ( k < high(polygones)) and (found = false) do
                        Begin
                         l := 0;
                         while ( l < high(polygones[k])) and ( not(PointsEqual(polygones[k, l], Point(i-1, j)))
                          or not(PointsEqual(polygones[k, l], Point(i-1, j-1))) or not(PointsEqual(polygones[k, l], Point(i, j-1)))
                          or not(PointsEqual(polygones[k, l], Point(i+1, j-1))) or not(PointsEqual(polygones[k, l], Point(i+1, j)))
                          or not(PointsEqual(polygones[k, l], Point(i+1, j+1))) or not(PointsEqual(polygones[k, l], Point(i, j+1)))
                          or not(PointsEqual(polygones[k, l], Point(i-1, j+1))) ) do inc(l);
                         if l < high(polygones[k]) then found := true;
                         inc(k);
                        end;
                        if found
                          then Begin
                                dec(k);
                                SetLength(polygones[k], high(polygones[k])+1);
                                polygones[k, high(polygones[k])] := Point(i, j);
                               end
                          else Begin
                                setlength(polygones, high(polygones)+1);
                                setlength(polygones[high(polygones)], 1);
                                polygones[high(polygones), 0] := Point(i, j);
                               end;
                      end;
             end;
           end;
   end;
   for k := 0 to High(polygones) do
     if high(polygones[k]) > 100
       then for l := 0 to high(polygones[k]) do
             result.Canvas.Pixels[polygones[k, l].X, polygones[k, l].Y] := clblack;
end;

Ich hoffe man steigt durch den Code durch.


Vielen Dank schonmal für eure Antworten!

[marabu]

Guten Morgen, Jan.

Willst du deinen Code neu geschrieben bekommen oder sollen nur Fehler behoben werden? Du hast leider nicht geschrieben, was nicht funktioniert.

Noch ein paar allgemeine Hinweise in ungeordneter Folge und ohne Anspruch auf Vollständigkeit:

Die Matrix polygones würde ich mit (0,0) vordimensionieren, nicht mit (1,1).
Eine horizontale Linie mit weniger als 101 Pixeln Breite wird bei deinem Ansatz eliminiert - vielleicht solltest du deine Definition von "zusammenhängend" nochmal überdenken.
Der Zugriff über Pixels[] wird bei großen Bildern zu langsam (ScanLine).
Dein Pixel-Test scheitert an den Bildrändern.
Die Pixel-Tests sind redundant, statt acht Tests sind wahrscheinlich nur drei nötig.
(not found) ist besser als (found = False).
Der riesige boolsche Ausdruck mit PointsEqual() kann vereinfacht werden - (not a or not b) ist das gleiche wie not (a and b) - aber ob die Bedingung überhaupt richtig formuliert ist?
Am Ende übermalst du schwarze Pixel nochmal mit schwarz - was soll sich dabei ändern?

Grüße vom marabu

[Eichhoernchen]

Ne ich will natürlich nicht, dass ihr mir den Code neu schreibt, dass was du gemacht hast ist genau dass was ich wollte, habe da irgendwie nen Knoten im Kopf.

So, ja über die Initialisierung mit setlength war ich mir nicht klar, wenn ich mit (0,0) initialisiert habe, hat high() immer -1 als Ergebnis gebracht. Über high sagt die Delphi hilfe dass es -1 als Ergebnis zurück gibt wenn das array leer ist, heißt leer im Sinne von ohne Werte oder unterdimensioniert?

Wie kann ich dass mit scanline umsetzen? damit kann ich doch immer nur 1 Pixel betrachten und nicht mehrere oder?

Zitat:

Eine horizontale Linie mit weniger als 101 Pixeln Breite wird bei deinem Ansatz eliminiert

ne ist schon richtig das eine Linie mit weniger als 100 Pixeln elemeniert werden soll.


Ich hatte zuerst auch weniger Abfragen für die Pixel, und zwar immer nur links, rechts, oben, obenlinks und obenrechts, jedoch würde das Pixel dann aus der Liste fallen wenn in diesen bereich kein schwarzes Pixel aber unten drunter eins. Und ich glaube es war nicht schlimm ob man über den Rand hinaus ging!

Zitat:

(not a or not b) ist das gleiche wie not (a and b)

Das werd ich überarbeiten, das würde es schonmal übersichtlicher machen, aber er tut ja das Selbe, also ist es ja nicht falsch.

Zitat:

Am Ende übermalst du schwarze Pixel nochmal mit schwarz - was soll sich dabei ändern?

Nein ich Zeichne alle Bereiche mit mehr als 100 Pixeln auf eine neue Bitmap, die der Rückgabewert ist.


Ist der Ansatz überhaupt gut, dass mit einem array zu machen, wie wäret ihr denn an das Problem heran gegangen?

[Hawkeye219]

Hallo!

Zitat:

Zitat von Eichhoernchen

ich glaube bei der Verwendung von setlength, bin aber nicht sicher

Meinst du vielleicht diese Stellen (Zeilen 43 und 47)?

Delphi-Quellcode:

SetLength(polygones[k], high(polygones[k])+1);

High(Array) liefert den Index des obersten Elements, High(Array) + 1 also die aktuelle Länge des Arrays...

Gruß Hawkeye

[Eichhoernchen]

Zitat:

Zitat von Hawkeye219

High(Array) liefert den Index des obersten Elements, High(Array) + 1 also die aktuelle Länge des Arrays...

Gruß Hawkeye

das heißt damit ich das Array um eins verlänger, muss ich:

Delphi-Quellcode:

SetLength(polygones[k], high(polygones[k])+2);

Dann werd ich dass mal Testen!

[Hawkeye219]

Das sieht schon besser aus. Dummerweise habe ich dir eine Information vorenthalten: die Standardfunktion Length kann man auch auf dynamische Arrays anwenden, sie liefert dann die Länge des Arrays:

Delphi-Quellcode:

Length(ArrayVar) = High(ArrayVar) + 1

Damit kannst du deine letzte Anweisung noch etwas lesbarer gestalten:

Delphi-Quellcode:

SetLength (polygones[k], Length(polygones[k]) + 1);

Jetzt sieht man mit einem Blick, daß hier ein Array um ein Element vergrößert wird.

Gruß Hawkeye

[Eichhoernchen]

ahh wunderbar, ich dachte immer high wäre das length von dynamischen arrays.


So geändert hab ich das, leider klappt es immernoch nicht. ich hab nen bild erstellt mit nem großen Pixelblock, 225 Pixeln (15x15)
jedoch bekomm ich steht ein weißes Bild am Ende....

[Nikolas]

Delphi-Quellcode:

Procedure Next(var cnt: integer; x,y: integer; stop: integer);
begin
if stop then exit;

pixel[x,y].color:=clmaroon; // Gezähltes Pixel wird markiert

if Pixel[x+1,y+1]=clblack then // ein Nachbar wird überprüft 
 begin
 inc(cnt);
 next(cnt,x+1,y+1, stop);
 end;

if Pixel[x,y+1]=clblack then
  ...
if ..
if ..

if cnt>100 then   // Fertig. 
 begin
 Myfloodfill(x,y);
 stop:= true;   // alle anderen Ableger der Funktion sterben
 end;

end;

Procedure Myfloodfill(x,y); // sollte klar sein. 
begin
pixel[x,y].color:= :=clnone;

if Pixel[x+1,y].color:=clmaroon then myfloodfill[x+1,y];
if ..
if ..
if ..
end;

Die Idee sollte klar sein. Du suchst nach einem schwarzen Pixel und rufst die Suchfunktion rekursiv für die schwarzen Nachbarn auf. Ein Gefundenes Feld wird Rot angemalt, damit es nicht nochmal gezählt wird, sonst verwickeln schon zwei benachbarte schwarze die Funktion in eine Endlosschleife. Jede neu erzeugte Suchfunktion meldet ihre Treffer an einen Zähler und sobald irgendwo das hunderste Feld gefunden wurde, wird die Suche abgebrochen und die Felder angemalt. Bei meiner Methode brauchst du dir nicht zu merken, welche Felder du durchlaufen hast, weil du den Weg einfach rekonstruieren kannst.

Bis auf Feinheiten, sollte das so funktionieren und wäre dann deutlich einfacher als dein Code. Obs schneller ist, weiss ich nicht, aber das sollte rauszufinden sein.

[loetmann]

Hallo,

Zitat:

Zitat von Eichhoernchen

Wie kann ich dass mit scanline umsetzen? damit kann ich doch immer nur 1 Pixel betrachten und nicht mehrere oder?

Mit scanline greifst du auf eine komplette Zeile eines Bitmaps zu.

Folgendes setzt einen RGB Pixel in einem RGB Bild:

Delphi-Quellcode:

procedure mp_setpixel(x,y:integer;r,g,b:byte;bitm:TBitmap);
var p:PByteArray;
begin
 p:=bitm.ScanLine[y];
 p[x*3]  :=b;
 p[x*3+1]:=g;
 p[x*3+2]:=r;
end;

Eine Zeile ist dann ein Array das bei RGB-Bilder so Aufgebaut ist: bgrbgrbgr...
(der Zugriff ist dann Schneller als Pixels)

Wenn Du z.B. 2 Zeilen gleichzeitig betrachten möchstest kannst Du mit

Delphi-Quellcode:

p:=bitm.ScanLine[4];
p1:=bitm.ScanLine[5];

auf die 4. und 5.Zeile zugreifen. (Zählung ab 0)

Ein Gruß

[Eichhoernchen]

Jo das war mir schon klar, nur bin ich nicht sicher ob da nicht der Aufwand, wenn ich 3 scanlines brauche größer ist als eben über pixels anzusprechen.

Naja gut das ist "tuning", wenn es klappt kann werde ich dass machen, aber rein von der Übersicht ist es mit pixels deutlicher.

[Ultimator]

Ich kann dir nur empfehlen, Scanline so bald wie möglich zu verwenden. Das Performanceunterschied ist einfach gewaltig.

[himitsu]

Oder man besorgt sich per ScanLine die Adresse des ersten Pixel (des Bildes) im RAM und legt darauf ein nettes passend zurechtdimensioniertes (statisches) Array ( Array[0..x, 0..y] of PixelFormat ).
Danach kann man wesendlich schneller direkt zugreifen und das ohne sich jedesmal mehrere ScanLines, oder Pixel besorgen zu müssen.

[dizzy]

Dabei sollte man nur im Hinterkopf behalten, dass Bitmaps mal top-down, und mal "richtig herum" im Speicher liegen. Ich weiss nur grad nicht wodurch das defniniert ist, bzw. ob das überhaupt definiert ist. Für diesen Fall hier sollte das allerdings keine großen Unterschiede machen.

Btw: Als ich "zusammenhängende Pixel" las, musste ich auch zu aller erst an "Rekursion" denken. Ich denke der Ansatz von Toxman ist sehr brauchbar.
Anmerkung zu "SetLength(array, Length(array)+1);": Dazu gab es in der DP schon irre Threads. Fakt ist: Es ist unglaublich ineffizient, und aus Sicht des Speichermanagements ein Schlag ins Gesicht :)
Und zu Scanline vs. Pixels[]: Auch die Verwaltung von 3 oder mehr Scanlines ist im Zweifel erheblich schneller als Pixels! Man kann aber auch mit Wissen um die Breite eines Bildes mit einfachen Rechnungen an Pixel über oder unter dem aktuellen kommen, was noch immer viel viel effizienter ist als Pixels. (Ein Bitmap wird ja immerhin 1-dimensional gespeichert, und zwar so, dass die Zeilen im Speicher "nebeneinander" liegen. Um kontrolliert zugreifen zu können reichen also die folgenden 3 Infos völlig aus: Pointer auf den ersten Pixel; Pixelformat; Höhe+Breite des Bildes.)
Wenn man sich btw. anschaut, was Pixels alles für Umwege macht beim Zugriff darauf, wird denke ich auch deutlich wo da der Hund begraben ist. Pixels ist imho eines der dicken "don'ts" im Umgang mit Bitmaps, bzw. gerade dann, wenn man mehr als nur eine Hand voll Pixel lesen/schreiben will.


Gruss,
Fabian

[Muetze1]

Ich sehe bei einem 2-dimensionalen Array auch noch das Problem, dass bei manchen Pixelformaten ein Packed angegeben werden muss (z.B: 24bpp) um die Ausrichtung des Array anzupassen. Nun ist da aber noch das Problem, dass die ScanLines nach meinem Wissen aligned werden. Wenn also am Ende einer Pixeldatenzeile noch ein Byte übrig ist vor der nächsten Zeile, dann wird das leer gelassen - die Array Definition benutzt dieses aber mit und schon verschiebt sich alles.