Code Optimierung: floodfill innerhalb 1/10 sek

[mr_emre_d]

Hallo liebe Leute,

Ich bin grad schon länger dabei ein Headtracking Programm nachzuschreiben es funktioniert halt auch alles bis auf die Geschwindigkeit des FIlters( hab ne eigene Methode dafür geschrieben )

Jetzt denk ich mir halt ich machs mit floodfill nur nicht mit der schon definierten sondern mit einer eigenen, weil ich nach jedem Schrit die Koordinaten abspeichern will .. -- temporär - versteht sich

hier der daweilige code:

Code:

procedure TForm1.rFloodFill(bmp: TBitmap; Pos: TPoint; Color: TColor);
var
  GColor: TColor; // Get Color
  abs: Byte;  // Abstände
  function CheckKol: Boolean;
  begin
    Result:= false;
    if ( pos.X < 1 ) and ( pos.x > bmp.Width - 1 ) and
       ( pos.y < 1 ) and ( pos.y > bmp.Height - 1 )
    then
      Result:= True;  // sie ist an der wand !
  end;
begin
  abs:= 2;
  try

  if not CheckKol then
  with pos do
  begin
    if ( not Setted[pos.x-abs,pos.Y] ) and
       ( not ( bmp.Canvas.Pixels[pos.x-abs, pos.y] = Color ) ) and
       ( bmp.canvas.Pixels[pos.x-abs, pos.y] = ClickedColor ) then
    begin
      bmp.Canvas.pixels[pos.x-abs,pos.Y]:= Color;
      Setted[pos.X-abs,pos.Y]:= true;
      rFloodFill( bmp, point( x - abs, y ), Color );
    end else
      exit;

    if ( not Setted[pos.x,pos.Y+abs] ) and
       ( not ( bmp.Canvas.Pixels[pos.x, pos.y+abs] = Color ) ) and
       ( bmp.canvas.Pixels[pos.x, pos.y+abs] = ClickedColor ) then  // ist in public definiert, zeigt die erste farbe an !
    begin
      bmp.Canvas.pixels[pos.x,pos.Y+abs]:= Color;
      Setted[pos.X,pos.Y+abs]:= true;
      rFloodFill( bmp, point( x, y+abs ), Color );
    end else
      exit;

    if ( not Setted[pos.x+abs,pos.Y] ) and
       ( not ( bmp.Canvas.Pixels[pos.x+abs, pos.y] = Color ) ) and
       ( bmp.canvas.Pixels[pos.x+abs, pos.y] = ClickedColor ) then
    begin
      bmp.Canvas.pixels[pos.x+abs,pos.Y]:= Color;
      Setted[pos.X+abs,pos.Y]:= true;
      rFloodFill( bmp, point( x + abs, y ), Color );
    end else
      exit;

    if ( not Setted[pos.x,pos.Y-abs] ) and
       ( not ( bmp.Canvas.Pixels[pos.x, pos.y-abs] = Color ) ) and
       ( bmp.canvas.Pixels[pos.x, pos.y-abs] = ClickedColor ) then
    begin
      bmp.Canvas.pixels[pos.x,pos.Y-abs]:= Color;
      Setted[pos.X,pos.Y-abs]:= true;
      rFloodFill( bmp, point( x, y-abs ), Color );
    end else
      exit;
  end;
  except

  end;
end;

ich habs geschafft, dass ich es von 9 Sekunden auf 3 runterbringe nur reicht das immernoch nicht... uund es sind noch n paar Fehler wahrschinlich drinnen + hab gerade jetzt kommentiert also entschuldige ich mich schon im voraus für die Fehler !

MfG

[Die Muhkuh]

Der Zugriff auf pixels wird das ganze noch langsam machen.

[mkinzler]

Entferne mal die Subfubktion, sie wird ja sowieso nur einmal aufgerufen

[mr_emre_d]

ich habs mit scanline auch probiert, bringt nicht viel warum denn auch ? es muss nicht zeilenweiße gelesen werden, sondern nur einzelne pixels + rekursive points ...

kann aber auch sein das ich n denkfehler hab... kein schlaf mehr seit 2 tagen .. :cry:

mkinzler: ist schon weg !

[Namenloser]

Wenn du die Pixel nicht in zeilenweise Arrays packst, sondern in ein großes, kannst du schnelelr drauf zugreifen. Die Graphics32 ( :love: ) machen das z.B. so. Guck dir die mal an, die sind komplett auf Geschwindigkeit getrimmt.

[mr_emre_d]

im bisherigen code packe ich noch nichts... da schaue ich nur obs gesetted ist .. mehr nicht ...aber danke für den tipp

[alzaimar]

Floodfill ist ja nun auch nicht gerade die schnellste Variante. Du solltest Zeilenweise füllen (Dann bringt Scanline auch etwas). Hab grad vergessen, wie das Verfahren heißt.

P.S.: Dein 'setted' ist das grauslichste Englisch, was ich seit langem gesehen Es bringt zwar performancetechnisch Nichts, aber reputationsmäßig Einiges, bei der Nomenklatur grammatikalisch und orthographisch auf der richtigen Seite zu sein. Wieso nicht ein 'Gesetzt' oder -wenns denn englisch sein soll- 'IsSet'. Na ja, ist OT.

[Namenloser]

Du hast echt länger nicht mehr geshclafen, oder? ;)
Wenn alles in einem Array ist, kannst du sehr einfach ausrechnen, wo der Pixel ist, den du brauchst: Array[Y*Breite+X]; Das ganze kannst du dann auch noch als pointer nehmen (pColor32). Relative Sprünge (also z.b. pixel rechts darunter) sind dann auch sau einfach: inc(pixel,width+1);

[mr_emre_d]

alzaimer: bitte hab erbarmen ...

Meinst du die wo man per scanline alles einließt und dann halt damit dementstprechend rechnet ? Diese methode ist glaub ich langsamer!


Das mit dem Array klingt gut... nur geht es hier um eine Webcam aufnahme ! Und da sich die mühe machne, das ganze bild innerhalb 1/10 sek in einem array abzuspeichern ... hmmm wenn das schneller ist dann heiß ich Franz !

[Namenloser]

Dann heißte wohl Franz. Nimm dir ein TBitmap32 und zeichne das Webcambild per BitBlt auf das handle des Bitmap 32. Mit .bits und .pixel kannste auf das bild zugreifen.

[Medium]

Scanline ist immer schneller als Pixels[]. Du solltest es mal messen, statt es zu vermuten/glauben. (Man sollte sich halt nur nicht für jedes Pixel eine neue Scanline holen ;))
Die Graphics32 sind jedoch mMn immer die bessere Alternative zu TBitmap/TImage/etc., nicht nur weil sie auch ohne Verrenkungen schon sehr fix sind, sondern weil du auch gleich eine ganze Menge an Funktionsumfang dabei hast, den ich zumindest sonst schon an diversen Ecken vermisst hätte, und wo sich der Aufwand des Selberschreibens oftmals kaum gelohnt hätte.

[mkinzler]

http://www.torry.net/vcl/graphics/ef...aphic32Grf.zip

[mr_emre_d]

Ihr bringt mich auf neue Ideen... Das Schlafen hat sich doch ausgezahlt

MfG Franz

[mr_emre_d]

Code:

var
  aBmp: Array of TRGBTriple

procedure form1.imgOnLoad
begin
  SetLength( aBmp, bmp.height );
end;

proc. blablablablablabla....;
begin
  1. speichere alles ins array
  2. suche im array nach bestimmten wert und tu was du wills damit !
end;

so ca müsste es schneller sein oder ?

edit:
omfg, es geht... ich bin sicher nur wegen der Schlaflosigkeit nicht draufgekommen ... :)

Vielen Dank !

Ich liebe Delphipraxis.net ! Meine Lieblingsseite ! Klasse Design, Klasse Mods., Klasse Leute... N kleiner Dank von mir an euch ! :)

edit2:
Nun gehts wieder nicht mehr... Ich hab einfach so zum Probieren einen Code compiliert... ging auch... dann ein wenig umgändert und jetzt gehts nicht mehr.. das Problem ist ich weiß nicht was ich umgeändert hab..

MfG Franz

[mr_emre_d]

Ich hätte da noch ne Frage ( zu ^TRGBTriple, also dazu gehört ):

Mit Scanline ermittelman ja die Anfangsposition !
Mit inc geht man stückweiße nach rechts, sag ich mal !

Wie kann ich aber bestimmte sprüng nach rechts UND links machen ? und bitte nicht mit inc, dec sagen !
Kann ich die Position beliebig setzten ?


Das wärs schon
Danke

[alzaimar]

Du musst die OH genau lesen: ScanLine ist einfach nur ein ^TByteArray in eine Zeile des Bildes. Was da genau steht, ist vom Bildformat abhängig. Wenn Du ein 24bit Bild hast, sind das lauter TRGBTriple-Werte, also kannst Du einfach ein entsprechendes Array deklarieren und direkt jedes Pixel ansprechen:

Delphi-Quellcode:

Type
  TRGBLine = Array [0..0] Of TRGBTriple; // Achtung! Mit {$RANGECHECKS OFF} kompilieren
  PRGBLine = ^TRGBLine;

...
Var
  pPixelLine : PRGBLine;

Begin
  pPixelLine := PRGBLine (MyBitmap.ScanLine[x]);
//  pPixelLine^[25]  ist nun das 26.Pixel von Links (wenn MyBitmap eine 24bit Bitmap ist)
...

[mr_emre_d]

das weiß ich doch schon

mit scanline kann man die einzelnen farben ausrechnen auf der y achse ausrechnen
und mit inc( rgb ) = ^trgbtriple der x wert eine stelle nach rechts ( so sag ich das, stimmt vlt nicht, da ich grad gelesen hab, dass es verkehrt herum gespeicher wird usw....)

wie positioniere ich es nach beliebenb ????

[Medium]

Du kannst auch auf das gesamte Bitmap mit einer Scanline zugreifen, da du mit SizeOf(TRGBTriple)*Bitmap.Width eine ganze Zeile springst. Es wird jedoch immer mal wieder darauf hingewiesen, dass Bitmaps im Speicher nicht immer gleich vorliegen. Normalerweise sind sie "falsch herum", sprich mit der letzten Zeile zu erst hinterlegt, es kann aber durchaus mal sein, dass es genau anders herum ist. Wann das so ist, war IIRC nicht ohne weiteres feststellbar.
Der sichere Weg wäre also sich trotz dessen für jede Zeile die Scanline neu geben zu lassen, ich rate aber weiterhin zur Graphics32 ;)

Edit: Das hat alzaimar doch gerade gezeigt :gruebel:

[mr_emre_d]

achso... ich hab mir den code nicht angeschaut..

thx

ich probiers mal

EDIT: alzaimer

Ich versteh deinen Code nicht .. und zwar genau die Stelle:

Code:

pPixelLine := PRGBLine (MyBitmap.ScanLine[x]);

und das

Code:

SizeOf(TRGBTriple)*Bitmap.Width

auch nicht ... :(

EIDT2: Das von Alzaimer funktioniert wunderbar, nur will ich es auch gerne verstehen !
:gruebel:

[Union]

Am schnellsten gehts, wenn Du die ganze TBitmap Sch... wegläßt und direkt mit TDIBSection arbeitest. Dann kannnst Du Dir die für den speziellen Anwendungsfall hochoptimierten Zugriffe auf das Bitmap im Speicher ohne Overhead erstellen.

[mr_emre_d]

Kann mir das bitte einer erklären ???