Flood Fill

Statement zur DSGVO im Forum

Alles zur DSGVO und zur Umsetzung im Forum hier: Statement zur DSGVO (letztes Update: 30.05.2018)
  • Moin,


    ich habe wiedermal ein unnützes Problem und suche nützliche Kommentare:*

    Es geht um den FloodFill Algorithmus in 4 Richtungen (also Pixel die durch eine "1px breite Diagonale" getrennt sind gehören NICHT zusammen).


    Der Klassiker ist der einfache Rekursive Ansatz bei welchem man einfach Rekursiv mit x-1, x+1, y-1 und y+1 sich selbst aufruft und so jeden Pixel überprüft. Dabei geht die anzahl Rekursionsschritte aber sehr schnell durch die Decke, sodass diese Methode nicht nur relativ langsam, sondern auch nur für relativ kleine Anwendungen geeignet ist.


    UEZ hat dazu schonmal vor einiger Zeit einen Thread gestartet (im EN-Forum) bei dem vorgeschlagen (und auch umgesetzt) wurde, dass man einen Stack benutzt um die Rekursion loszuwerden.

    Das Problem ist aber villeicht nicht unbedingt der Stack, sondern die Methode ansich. Es gibt viele Wege um eine FloodFill Funktion zu realisieren und nur eine einzige davon ist es, für jeden Pixel (in 1 px Schritten) in alle 4 Richtungen zu suchen (Hier werden noch ein paar Methoden gezeigt). Im englischen Wikipedia ist z.B. noch eine Right-Hand Fill Method vermerkt (die im Deutschen fehlt). Im Deutschen Wiki ist dafür noch eine kurze Vermerkung zu einem gewissen Span Flood Fill.


    Und hier kommt der Hilfegesuch:

    Bevor ich jetzt 50 verschiedene Methoden (ich zähle eine Rekursive und eine Iterative Methode als EINE Methode, sofern sie gleich vorgeht) implementiere und gegeneinander antreten lasse möchte ich herumfragen ob jemand schonmal etwas in diese Richtung programmiert hat (vllt sogar in AutoIt) und dazu irgendein Statement hat welche Methode in AutoIt eventuell recht schnell arbeitet.


    Im Beispielskript sind 3 FloodFill Methoden eingebaut.

    - FloodFill1: Das erste was Wikipedia sagt muss auch zuerst implementiert werden.

    - FloodFill2: Genau wie FF1 mit dem Unterschied, dass man keinen "Schritt zurück" gehen kann. (also wenn ich x+1 gehe kann man im nächsten Schritt nicht x-1 gehen)

    - FloodFill3: Habe ich mir ausgedacht und später herausgefunden, dass das Ganze eine Variation des Recursive Scanline Flood Fill Algorithmus ist.


    Natürlich kann jeder der Lust hat auch Eigenkreationen ausprobieren, die können villeicht besser als alles was es bereits gibt sein ;)


    lg

    M

  • Hi,

    habe keine rekursive, sondern iterative Variante.

    Schau aber bei deinem floodfill3() mal nach, ob das Ergebnis so gewollt ist, auch "diagonal" erreichbare Felder zu füllen?!

    Mein Beispiel könnte bei Bearbeitung einer "realen" Bitmap (die ist nämlich kein Array mit x- und y-Koordinaten ;-) ) noch etwas schneller sein, da die meisten Umrechnungen entfallen.

    Die iterative Variante hat den Vorteil, die unbearbeiteten, in der abzuarbeitenden Liste befindlichen "Pixel" je einem Thread zuordnen zu können, ohne dass es zu Überschneidungen oder Ärger mit Synchronisierungen kommt.

    Per OpenCL bspw. kann/könnte man somit mehrere Listenblöcke von bspw. je 256 Pixelpositionen GLEICHZEITIG bearbeiten.

    Nachteil ist, dass man eine weite 1-Bit-Bitmap als Markierungshilfe benötigt....

  • Interessanter Ansatz.

    Das mit den Diagonalen habe ich leider schon schmerzlich lernen müssen, da in einem Programm grober Unfug herauskam. Dort wird das Verfahren zur Flächenerkennung benutzt indem man immer noch alle (eck) Koordinaten speichert. So kann man minX, minY, maxX, maxY herausbekommen und eine Bitmapkopie der Fläche anfertigen. Da gab es mit meiner Methode einen Geschwindigkeitsvorteil vom Faktor 3 im Vergleich zur voll Rekursiven Wikipediamethode. Deine werde ich dann demnächst auch mal ausprobieren :)


    Zur Diagonalen korrektur muss man nur jeweils das If $xMin = -1 Then $xMin = 0 durch ein Penetrantes $xMin += 1 (äquivalent für y) austauschen.

  • Ich habe, wie du sicher festgestellt hast, in weiser Voraussicht schon "Loop unrolling" betrieben, mit dem Hintergrund, so nur 2 Koordinaten je Pixel (s. Script) prüfen zu müssen.

    Bissl kürzbar und "schneller" ist auch, die Position $pos vor dem Vergleich auszurechnen.

    Umgewandelt in eine "Struct"-Version statt Array wäre das dann eine Steilvorlage für ....na schaumamal^^

    //EDIT

    Script Teil geändert/gekürzt

  • ....wenn man mal eine Nacht schläft, dann kommt man oft zu erstaunlichen Ergebnissen am nächsten Morgen :o)

    Die Abfrage je Pixel reduziert sich um eine weitere, denn wenn ich bspw. die Position um 1 in x-Richtung vermindere, dann brauche ich zwangsläufig nicht mehr auf $x<$iW zu prüfen, sondern nur noch auf $x>=0

    Gegenüber der von dir schon verlinkten"kurzen" Version in einer Schleife reduziert sich beim loop unrolling die Abfrage bzw. die Vergleiche pro Pixel von 5 auf 3!

    1) "neue" Position If $xL >= 0 And

    2) ist diese Pixelposition bereits Element in der "Liste" $bitmap_marker[$pos]=0 Then

    3) Farbe lesen an dieser Position If Read($xL, $y) = $iColRead Then

    wird dann zu

    Code
    1. $pos=$y * $iW + $xL ;neue x-position
    2. If $xL >= 0 and $bitmap_marker[$pos]=0 Then ;wenn im bereich und noch nicht in der Liste
    3. If Read($xL, $y) = $iColRead Then ;Pixel mit $iColRead gefunden
    4. Write($xL, $y, $iColFill)
    5. $listcounter += 1
    6. $liste[$listcounter] = $pos ;position pixel in bitmap
    7. $bitmap_marker[$pos]=1 ;position in der 1-Bit-Bitmap :-) markieren
    8. EndIf
    9. EndIf

    Gegenüber den 5 Vergleichen im Link eine massive Verbesserung, da dort der eigentliche Vorteil, nämlich die Abfrage, ob das Pixel in der Liste bereits schon berechnet wurde, gar nicht berücksichtigt ist!

    In der verlinkten Version wird ja die Position des zu untersuchenden Pixels auf den "Stack" gepushed. Da in den meisten Fällen dieses Pixel aber wiederum 4 Nachbarn hat, pushed jeder Nachbar (unötigerweise) diese Position, der Stack muss zwangsläufig viel größer werden und die Abfragen wachsen im gleichen Anteil!

    Die Reihenfolge der Pixelprüfungen legt man günstiger Weise auf oben, links, rechts, unten. So liegen auch bei großen Bitmaps sämtliche Positionen bereits nach der Prüfung auf "oben" im Cache (zwei komplette Pixelzeilen).



    //EDIT Komplettscript:

    Gegenüber Vorversion ca. 10% Laufzeit eingespart...bei Autoit ( ! ), gar nicht auszumalen, wie sich das bei einer Compilersprache auswirken würde

  • Das mit dem "merken an welchen Stellen man bereits war" ist ein Problem.


    Wenn die Funktionen Read/Write langsam im Vergleich zur Prüfliste sind ist die Methode extrem gut. In einer üblichen Bitmap ist es aber nahezu gleich Aufwändig die Bitmapadresse auf "[Adresse] = color" zu testen oder die Prüfliste mit "[pos] = 0" zu checken. Wenn man (in einer Compilersprache) den Prozessor zwingen könnte die Prüfliste in den Cache zu stecken wäre das nochtmal eine andere Geschichte, dann sollte die Liste viel schneller sein als der Farbcheck im RAM.


    Multithreading ist bei der Methode ganz interessant, OpenCL werde ich aber nie wieder anfassen, das ist Hexerei und Zauberei :D


    Hatte in der Info Funktion noch einen Fehler (statt UBound eine 15 genommen, weil ich zwischenzeitlich ein 15x15 Array hatte). Startpost wird aktualisiert. Hab die auch mal überall auf True gesetzt, damit man die Zugriffsliste sieht.


    Also welche Checks kann man ausschließen.

    Code
    1. - FF1: Schließt garnichts aus. (effektive Reads: 4/px)
    2. - FF2: Checkt alle 4 Pixel, mit Puffer für 1 Pixel. (effektive Reads: 3/px)
    3. - Andy1&2: Checkt alle 4 Pixel mit Puffer für 4 Pixel für alle 4 Pixel. (effektive Reads: 1/px)
    4. - FF3: Checkt nicht nach hinten beim durchlaufen einer Linie. (effektive Reads: 3/px)

    Wichtig ist: je mehr man ausschließt, desto besser, ABER NUR wenn der algorithmus nicht extra irgendwas überprüfen muss. Beispiel ist FF3, dort wird nicht geprüft ob man den Check nach "hinten" machen sollte, er findet einfach nicht statt (weil er logisch ausgeschlossen werden kann), weshalb es auch einen großen Geschwindigkeitsvorteil gibt.

    Angenommen man würde in Form eines sich ausdehnenden Rechtecks vorgehen, dann könnte man alle Checks nach "innen" ausschließen, weil man genau weiß, dass eine vollkommen umschlossene Fläche fertig gefärbt ist.

    Edit: Villeicht wenn man eine Art QuadTree aufspannt und jeweils nur nach "unten" und nicht "horizontal" sucht. Dann müsste ein Großteil der Nachbarn per Definition nicht überprüft werden. Bin aber noch nicht sicher, wie man das anstellen soll, da man ja vorher die Gesamtgröße der Fläche nicht kennt, einen Quadtree spannt man aber üblicherweise von oben auf und nicht von unten. (nur eine Überlegung, villeicht kommt ja der Geistesblitz noch :D)

  • den Prozessor zwingen könnte die Prüfliste in den Cache zu stecken wäre das nochtmal eine andere Geschichte,

    In dem Moment, wo du die erste Position aus der "Liste" (sprich "Speicherbereich", vorteilhafter Weise eine Struct ) liest, werden sämtliche darauf folgenden Positionen in den Cache geladen. Dann liegen zwar die Listenitems alle im Cache, aber das sind ja nur die Adressen bzw. Positionen der Pixel. Idealerweise würde man dann die "kleinste" Adresse dort zuerst laden und hätte die meisten anderen somit im Cache...

    Bei 128kB Lvl1-Cache passt da ja ein Teil der Bitmap rein^^

    In einer üblichen Bitmap ist es aber nahezu gleich Aufwändig die Bitmapadresse auf "[Adresse] = color" zu testen oder die Prüfliste mit "[pos] = 0" zu checken.

    DAS stimmt, ist aber nicht die Intention der Liste. Sinn ist es, die Anzahl der Listenitems, also die "nächsten abzuarbeitenden" Pixelpositionen, radikal zu dezimieren. Wenn es dumm läuft, und das ist bei den meisten Pixeln so, und auch bei sämtlichen Rekursionsmodellen, dann wird jedes zu prüfende Pixel 4 mal, nämlich von Links, Rechts, Oben und Unten, "vorgemerkt". An dieser Stelle ist an diesem Zeitpunkt nämlich die Farbe nicht $iColFill sondern $iColRead!

    In der Liste befinden sich AUSSCHLIESSLICH zu prüfende Pixel, d,h. ich könnte mit einem Thread einen Teil der Liste abarbeiten, und mit einem anderen den Rest.

    Da die Liste extrem schnell wächst (mit jeder Iteration kommen idealerweise 3 Pixel dazu (eins wird ja aktuell abgearbeitet)) lohnt es sich bestimmt, die Arbeit "aufzuteilen".

    OpenCL werde ich aber nie wieder anfassen, das ist Hexerei und Zauberei

    Ach, bissl Voodoo muss ab und zu sein, du weisst schon...."separates the boys from the men":rofl:

    Blöd ist natürlich nur, dass am Anfang die Liste nicht viele Items enthält, jede Rückgabe der OCL-Abarbeitungsfunktion würde die weiteren ermittelten Listitems erhalten.

    Bei kleinen Flächen macht das imho wenig Sinn, aber wenn ich 1024 Workitems gleichzeitig eine Pixelfarbe setzen und danach wieder 1024 Listitems zurückgeben lasse, dann rockt der Algorithmus schon^^

    Edit: Villeicht wenn man eine Art QuadTree aufspannt

    Der vorliegende Algorithmus "baut" dir ja den QuadTree auf! Logisch, wenn man alle einzufärbenden Pixel bereits hat, DANN ist es einfach ;)



    //EDIT

    Und wieder fragt man sich, warum man bei einer Funktion, welche auch bei großen Bitmaps nur einige Millisekunden dauert, den Aufwand einer "Beschleunigung um Faktor X" treiben sollte...

  • Hatte doch noch einen Geistesblitz (beim schlafen, kein Scherz).


    Also wie funktioiert der Scanline Flood Fill?

    - Startposition x,y

    - x nach Links gehen bis falsche Farbe kommt -> xMin speichern

    - x nach Rechts gehen bis falche Farbe kommt -> xMax speichern

    - von xMin bis xMax jeweils rekursiv für y-1 und y+1 eine Runde starten.


    Was geht da noch?

    - Startposition x,y

    - x nach Links gehen bis falsche Farbe kommt -> xMin speichern

    - x nach Rechts gehen bis falche Farbe kommt -> xMax speichern

    - Den Bereich aufteilen in 3 Teile

    --- [1] Bereich links von xMinALT (wenn die Zeile weiter nach Links geht als die vorherige)

    --- [2] Bereich mitte von xMinALT bis xMaxAlt (quasi genau die Zeile vorher)

    --- [3] Bereich rechts (äquivalent)

    - Man muss nur noch für Bereich [1] und [3] jeweils in y-1 und y+1 checken

    - Man muss für bereich [2] nur entweder in y-1 oder y+1 checken, je nachdem wo man herkommt.
    Und Tadaaa -> Durch logisches Ausschließen von Bereichen auf 2.3 - 2.4 checks/Pixel gekommen und eine neue Rekordgeschwindigkeit aufgestellt.


    Vorteil:

    - Wenn Gebiete lange zeilen haben die übereinander liegen und gleichfarbig sind gibt es einen großen Geschwindigkeitsvorteil.


    Nachteil:

    - Gebiete in denen die Zeilen sehr selten länger sind haben viel overhead -> langsam

    - Ich habe keine Ahnung wie man die Diagonalen wieder "ausbaut", denn diese werden schon wieder gefunden...


    Edit1:

    Habe jetzt die Diagonalen draußen, bin aber nicht ganz sicher, ob die Funktion noch zu 100% sauber arbeitet. Das ist ein weiterer Nachteil, je komplexer die Funktion, desto schwieriger ist es ihre korrektheit zu zeigen...


    Edit2:

    Am anderen PC (desktop) ist die FF3+ Version langsamer als FF3.... hier ist doch was böses im Busch.


    Edit3:

    Nochmals überarbeitet. Jetzt ist FF3+ (heißt jetzt FF4) in (fast) jedem Fall schneller als FF3 (ca. 88% der ursprünglichen Zeit wenn man 1000 Tests mit Zufallsstartwerten auf der vorgegebenen "Bitmap" zündet)

    Der nächste Trick wird es sein unter einen Durchschnitt von 2 Reads/Px zu kommen (aktuell ca. 2.2/px). Das geht indem man rückwirkend (also rückwärts durch die Rekursion) die Überprüfung aufhält sollte sie zukünftig obsolet werden (und das ganze in weniger Rechenoperationen als die tatsächliche Überprüfung brauchen würde). Der letzte Schritt zur vollendung der besten FloodFill Funktion des Planeten wird das ganze auf eine Iterative Version umgestellt (incl Umstellung der Bitmap auf eine Struct) und geschaut ob man dann noch etwas wegkürzen kann (wahrscheinlich ein paar Umrechnungen von xy -> pointer). Für ASM wird die Sache dann wohl zu lang zum programmieren werden, aber in C/Go/Basic ist das quasi Copy & Paste -> Compilen, inlinen (DllCallAdress) -> schnellste Version die es gibt. Um dazu eine gute Idee zu bekommen gehe ich jetzt aber mal wieder ins Bett :D

  • Die Nachricht war zu lang (maximal 20.000 Zeichen). Daher der Code in einem Doppelpost.


  • Der letzte Schritt zur vollendung der besten FloodFill Funktion des Planeten wird das ganze auf eine Iterative Version umgestellt (incl Umstellung der Bitmap auf eine Struct) und geschaut ob man dann noch etwas wegkürzen kann (wahrscheinlich ein paar Umrechnungen von xy -> pointer). Für ASM wird die Sache dann wohl zu lang zum programmieren werden, aber in C/Go/Basic ist das quasi Copy & Paste -> Compilen, inlinen (DllCallAdress) -> schnellste Version die es gibt. Um dazu eine gute Idee zu bekommen gehe ich jetzt aber mal wieder ins Bett

    Der Algorithmus ist nur dann "schnellstmöglich" wenn im Vorfeld so wenige Vergleiche wie nötig stattfinden. Rekursion fällt definitiv weg, da schon bei "kleinen" Flächen der Stack überläuft...

    Scanline hat imho auch keinen Vorteil, da die Abfrage "ist der nächste Punkt in der Farbe iColRead ? Ja, dann einfärben mit iColFill! Nein, nächster Punkt suchen..." die Minimalstabfolge ist!

    Der Knackpunkt dabei ist ja "Nein, nächster Punkt suchen..."!

    Die von mir angewandte "Liste" enthält ja bereits nur Pixel(adressen), die auf "Nachbarn" zu untersuchen sind. Und jeder dieser Pixel hat nun mal 4 Nachbarn, von denen definitiv einer (der vorherige Startpunkt) bereits mit iColFill gefüllt wurde. Mal angenommen, man würde dieser "Pixeladresse" 4 Bits mitgeben (die 4 MSB werden bei "normalgroßen" Bitmaps sowieso nicht genutzt) welche die 4 Richtungen der weiteren Prüfung freigeben (1) oder sperren(0).

    Die Frage lautet jetzt, ob es mehr Prozessortakte kostet, die 4 Bits abzufragen, oder gleich (alle) 4 Adressen der Nachbarpixel, wobei man bei einem "Treffer" direkt schon auf iColRead geprüft hätte....

    Ist die im schlechtesten Fall eine überflüssige Abfrage auf den Ursprungspunkt den Aufwand "Bits vergleichen und eine Jump-chain abklappern" wert?

    Sehr interessant!!! -> Ausprobieren!:D

    In meinem vorliegenden Algorithmus habe ich ja eine "1-Bit-Bitmap" implementiert, um die zu "sperrenden" bzw. nicht weiter zu berücksichtigenden Pixeladressen direkt zu markieren. Dieses Bit kann man aber auch einfach direkt an das MSB der "Listenadresse" schreiben....


    Was ich definitiv machen würde, wäre per SSE, die 4 "Nachbaradressen" gleichzeitig(!) zu berechnen (1 Takt) und auch abzufragen. Liegen dann diese 4 Pixeladressen im Cache, "schwuppt" die folgende Abfrage innerhalb eines Prozessortaktes. So wie ich das zzt. sehe, läuft alles auf eine clevere Nutzung des Cache raus!

    An der eigentlichen "Berechnung" ist ja sowieso nix dran.8)

    Wobei in heutige Lvl3-Caches ohne Probleme die meisten Bitmaps reinpassen sollten^^

    Da der Lvl3-Cache von allen Cores auch gleichzeitig genutzt werden kann, würde sich ein Multithreading anbieten, bei ASM also absolut kein Thema



    Die OpenCL-Variante lass ich mal außen vor:theke:

  • Scanline hat sehr wohl einen Vorteil, hier werden Bereiche "gesperrt" (eigentlich logisch ausgeschlossen) und nicht einzelne Pixel. Das heißt, dass man für den ganzen Bereich auch nur eine einzige Abfrage braucht.


    Beispiel.

    An irgendeiner Startadresse bin ich nach links 5px und nach rechts 10px weit gekommen (mittelteil)

    Jetzt gehe ich einen Schritt nach oben. Dann kann man (wieder im Mittelteil, eine Zeile darüber) den Bereich des unteren Mittelteils ausschließen. Eine Abfrage nach unten fällt also für jeden Pixel weg, obwohl man nur 2 Werte zwischenlagern musste (nämlich xMinOld und xMaxOld). Für eine im Grenzfall sehr lange Linie kann man also mit vernachlässigbar wenigen Operationen sehr viele Checks einsparen. Das ist mit der Einpixelmethode nicht machbar, da man egal wie man es anstellt immer nur Informationen über die direkten Nachbarn speichern kann und nicht über eine ganze Zeile.


    Für kleine Flächen ist das villeicht noch vernachlässigbar, sobald man aber irgendwo z.B. ein 40x10px Feld einfarbig hat wird die Scanline Methode pro Zeile nur 2 Abfragen brauchen (also 20 Stück), während die Pixelmethode mindestens 1/4*40*10 = 100 Abfragen braucht.


    Die Rekursion ist nicht schön, bei der Scanline Methode geht die Tiefe aber mit der Anzahl an Abschnitten hoch. Da ein Abschnitt idr >1px ist gibt es keine Probleme. Für eine "richtige" implementierung muss das natürlich raus. Rekursion ist keine Option wenn man eine allgemeingültige Funktion haben will.

  • Scanline hat sehr wohl einen Vorteil, hier werden Bereiche "gesperrt" (eigentlich logisch ausgeschlossen) und nicht einzelne Pixel. Das heißt, dass man für den ganzen Bereich auch nur eine einzige Abfrage braucht.

    Frage: Wie viele Abfragen auf jedes Pixel hast du in einer Scanline?

    DU MUSST jedes einzelne Pixel abfragen, Und das ist der Punkt!

    Für eine im Grenzfall sehr lange Linie kann man also mit vernachlässigbar wenigen Operationen sehr viele Checks einsparen.

    Du sparst ja nur das ein, was du im Vorfeld durch die "faule" Methode bereits "rausgeballert" hast.

    if(nx >= 0 && nx < w && ny >= 0 && ny < h && screenBuffer[ny][nx] == oldColor) { push(stack, nx, ny);DAS ist die Krankheit!

    5 Abfragen, obwohl 3 reichen würden!

    Letztendlich kannst du nur einsparen, indem du mehrere Pixel gleichzeitig abfragst, und das geht bspw. durch SSE (wirklich SEHR einfach in C zu implementieren, da müssen nur die Variablen mit uint4 spezifiziert werden).

    Da kann ich pro Speicher-read 4 Pixel gleichzeitig auf iColRead prüfen UND AUCH GLEICH mit iColFill BESCHREIBEN!

  • Wenn du ernsthaft drangehen solltest, hier mal eine kleine Idee, wie man Koordinaten "anders" speichern kann...

    Gerade die Umwandlung von einer Pixeladresse in x- und y-Koordinaten "tut weh" weil MOD und DIV schon arg "teure" Operationen sind. (Na gut, Assembler gibt bei DIV sowohl den Quotient als auch den Rest zurück, "teuer" ist es trotzdem)

    Da ich die Pixelposition nur aus meiner Liste nehme, speichere ich sie dort direkt als 32Bit-Zahl ab, aufgeteilt in die 16 MSB als x-Koordinate und die 16 LSB als y-Koordinate

    $liste[$listcounter] = BitShift($x,-16)+$y

    und wieder zurück

    $y=bitand($liste[$counter],0xFFFF) ;16 LSB

    $x=Bitshift($liste[$counter],16) ;16 MSB


    Kostet für jede Koordinate 1 Takt, ein je nach Prozessor ausgeführtes DIV bis zu 20 Takte bei 32Bit bzw. bei 64Bit auch mal >50Takte


  • Gerade die Umwandlung von einer Pixeladresse in x- und y-Koordinaten "tut weh" weil MOD und DIV schon arg "teure" Operationen sind. (Na gut, Assembler gibt bei DIV sowohl den Quotient als auch den Rest zurück, "teuer" ist es trotzdem)

    Hier übrigens ein interessanter Artikel dazu wie teuer Modulo tatsächlich sein kann: https://embeddedgurus.com/stac…us-operator-with-caution/

  • Man kann sich ja einen LUT basteln indem die 16HI = x und 16LOW = y sind. 1x initialisieren beim Starten und bei allen weiteren Problemen braucht man nur einen RAM Zugriff und ein BitAND :D

  • Ich verfolge scheinbar ein anderes Ziel:

    Ich suche die "schnellste mögliche single Threaded" FloodFill Version die man in AutoIt basteln kann (ohne OpenCL).

    ASM ist natürlich erlaubt, aber in die Read/Write Funktionen kommt ggf. etwas AutoIt-Code (den man im Optimalfall direkt hardcoded in die FloodFill Funktion einbaut, zum Testen kann man ihn aber außen vor lassen, da ich keine gesteigerte Lust auf Callbacks (gibt in ASM bei gleichzeitiger Benutzung von Events manchmal Probleme) habe bleibe ich bei reinem AutoIt).


    Außerdem glaube ich, dass wir irgendwie aneinander vorbeireden und beide in unserer "Sphäre" Recht haben.

    Korrekt ist: Man muss jeden Pixel mindestens 1x lesen. Wenn man in ASM via SSE auch 4 "gleichzeitig" lesen kann (etwas herumgespringe ist immer nötig, man geht ja in der Bitmap nicht nur x+1 und x-1 sondern auch in y richtung. 1 SSE movdqX reicht also nicht aus) ist man logischerweise schneller als die schnellst mögliche Variante die immer nur einen einzigen gleichzeitig liest und durch Ausschlussverfahren versucht jeden Pixel möglichst selten zu lesen. ABER man ist nicht schneller als eine (theoretische) SSE Variante die sowohl mehrere Pixel, als auch das Ausschlussverfahren drauf hat.


    Mein Aktueller Spitzenkandidat tut folgendes (rekursive Scanline Methode mit einigen "Tricks")

    1. Startposition lesen + schreiben

    2. nach links gehen und nach rechts gehen und schauen wie weit man kommt -> xMin, xMax
    3. Aufteilung in [Links] (<xMinOld), [Mitte] (parallelzeile zu vorher), [Rechts] (>xMaxOld)

    4. Wie vorher: Bereich [Mitte] nach oben ODER unten weiter absuchen, [Links] und [Rechts] nach oben UND unten absuchen

    5. NEU: Da Rekursiv gearbeitet wird ist der nächste Schritt in (4.) automatisch Schritt (2.) -> Rückwirkendes überspringen der bereits in (2. aber ein Rekurstionsschritt tiefer) besuchten Pixel.
    6. NEU: Der beste Trick den jeder kennt: Loop-Unrolling, nur in diesem Fall wird ein Rekursionsschritt geunrollt.

    # Da es lustigerweise mehr Operationen durch die übersprungenen Pixel einspart (1.5 Reads/Px sind übrig) als die Überprüfung brauchen würde ist die Version schneller als vorher.

    # Irgendwas stimmt am rechten Rand nicht, dort werden Pixel 3x gecheckt obwohl ich nicht weiß warum.

    # Auch lustig ist, dass ein 200+ Zeilen langes Riesenteil mit mehrfach verschachtelten Schleifen 5x schneller ist als ein 3 Zeiler der eigentlich das gleiche tut.


    Mir geht es vorallem darum die Zeit zu überbieten, solange es noch möglich ist die Read/Write Funktion irgendwie via AutoIt zu modifizieren ist mir Wurst wie der Rest abläuft.

    In nativem AutoIt hat es doch auch etwas an die Grenzen des Machbaren zu stoßen :D


    Edit: Die Rekursion kann man wahrscheinlich drinlassen (habe versucht sie auszubauen, aber eine Iterative Funktion ist unglaublich viel komplizierter wenn sie das gleiche leisten soll), da die Rekursionstiefe nur langsam ansteigt.


    lg

    M

  • Die Rekursion kann man wahrscheinlich drinlassen

    AutoIt steigt (jedenfalls bei mir) schon bei relativ "kleinen" Floodfills aus. Genau aus diesem Grund ist die iterative Variante besser, da macht es auch nix, wenn eine Bitmap mal mit 10000x10000 Pixeln "gefloodfilled" werden muss.


    Mir geht es vorallem darum die Zeit zu überbieten, solange es noch möglich ist die Read/Write Funktion irgendwie via AutoIt zu modifizieren ist mir Wurst wie der Rest abläuft.

    In nativem AutoIt hat es doch auch etwas an die Grenzen des Machbaren zu stoßen

    AutoItcode zu verwenden ist, wenn es auf Geschwindigkeit bei BERECHNUNGEN in langen Schleifen ankommt, extremst suboptimal!


    Bei einem Vergleich von zwei Algorithmen A und B gewinnt der bei einer Compilersprache 20x ( !!! ) schnellere Algorithmus A das Rennen, bei AutoIt allerdings B, weil AutoIt den Algorithmus B "besser" (schneller) verarbeiten kann, weil bspw. einfach die Codelänge kürzer ist! Das ist die Krux bei Interpreter vs Compiler, und nicht etwa, dass der Compiler "so viel schneller" ist! Denn DAS stimmt nur bei den schon erwähnten "langen" Berechnungsschleifen!


    Ich bin sicher, selbst der "langsamste" von dir verlinkte C-Code erfüllt die Aufgabe in einer beliebig großen Bitmap in nur in einer Handvoll Millisekunden. Und der "schnellste" Code ist dann wegen mir doppelt so schnell. Und jetzt? Ist ein "halber" Augenblick schneller als ein ganzer?!


    Bei AutoIt stellt sich diese Frage überhaupt nicht! Dort stellt sich eher die Frage "wieso AutoIt-Code"?! Wenn du eine 500x500 Pixel Bitmap per AutoIt-Code Floodfillen willst und dafür 3 Minuten brauchst und mit einem "AutoItoptimierten" Code dann nur noch 1,5 Minuten, dann ist das zwar absolut gesehen eine Verbesserung auf 50% Codelaufzeit, relativ gesehen ist dein Code aber 5000% langsamer als ein Algorithmusunabhängig schnellerer/langsamerer Compiler-Code....

    Den man, wie bereits von dir beschrieben, ja simpelst bspw. als Compilersprachen-Funktion in einer DLL (oder direkt) "inlinen" kann.



    //EDIT

    Nur mal für die Galerie, hier mal dein sonst unverändertes Script mit anderem Startpunkt und 800x800 Pixeln....soviel zum Thema "Spitzenkandidat" :whistling:

    Fast Flood Fill 800x800.au3

    Was dann bei mir zu folgendem Ergebnis führt:

  • Irgendwas stimmt das auch mit den Writes nicht, die müssten alle gleich viele haben. Kannst du das Ergebnis reproduzieren?

  • s. mein EDIT2 im vorherigen Post, ändert aber nichts an der Tatsache...

    Irgendwas stimmt das auch mit den Writes nicht, die müssten alle gleich viele haben. Kannst du das Ergebnis reproduzieren?

    hmmmm, wirklich seltsam....jetzt passt es

  • btw, bei deiner 5x-Funktion ist noch irgendwo der Wurm drin, schau mal hier in die Ergebnisbitmap:

    Ich hab da mal einen 1 Pixel breiten "Kamm" in den unteren Teil eingebaut...

    Fast Flood Fill 80x80 Kamm.au3