Beiträge von Mars

  • [GDI+] Bild aus anderem Bild zusammensetzen

    So Update im ersten Post. Das Problem mit den "offensichtlich falschen" Pixeln sollte (zumindest mit großer Wahrscheinlichkeit) gelöst sein. Sehr selten tritt es noch auf (wie das halt so ist mit Wahrscheinlichkeitsbasierten Verfahren). Ggf muss noch ein bisschen gebastelt werden.

    Außerdem ist die von Andy herzlich herbeigesehnte Brute Force Methode jetzt auch da :D

  • [GDI+] Bild aus anderem Bild zusammensetzen

    Auch wenn es nur ein kurzer Kommentar zu //EDIT2 ist:

    Hatte schon eine gute Idee um besonders störende Rechtecke zu entfernen.

    - Finde das Teilbild mit der größten Abweichung

    - Probiere vertauschungen aus bis eine gefunden wird die die Gesamtabweichung minimiert

    - Führe die Vertauschung aus

    - Solange bis z.B. Wurzel(Gesamtzahl Teilbilder) Vertauschungen durchgeführt wurden, oder keine Vertauschung mehr gefunden werden kann.

    Klingt wiedermal super Rechenaufwändig (bruteForce ftw) aber mit den vielen Optimierungen die ich mir ausgedacht, aber noch nicht programmiert habe (ich bin heute insg. DREI STUNDEN an Bahnhöfen gewesen weil wiedermal jeder Zug entweder nicht fährt oder so viel Verspätung hat, dass man den Anschluss verpasst und hatte daher viel Zeit nachzudenken) sollte das kein Problem mehr sein. Ich schätze allein durch ein paar Umstellungen hat man bei gleicher Funktionalität ca. 10-100x mehr Geschwindigkeit (sodass man auch ein FullHD Bild in einigen Sekunden verarbeiten kann).

    Die Sache mit "sollte man doppelte verwenden oder nicht" habe ich mir auch überlegt. In manchen Situationen wird man durch geschicktes Vertauschen das Resultat auch nicht mehr "retten" können, weil z.B. einfach andere Farben in Quelle und Ziel vorliegen. In dem Fall würde ich bis zu einem Abweichungs Grenzwert (den man empirisch ausprobieren und finden muss) trotzdem alle Teile nur 1x verwenden. Wird dieser Grenzwert überschritten wird das Quellbild resettet und es stehen wieder alle Teile genau 1x zur Verfügung, solange bis wieder der Grenzwert überschritten wird, und so weiter und so weiter. Dadurch sollte man (zusammen mit der Zufallswahl der Auszufüllenden Stellen) keine allzu auffälligen Wiederholungen haben. Was ich nämlich unter allen Umständen vermeiden möchte ist sowas wie dass das gleiche Teilbild 50x verwendet wird, nur weil es gut passt. Das mag zwar rechnerisch ein besseres Ergebnis liefern (und vllt auch auf den ERSTEN Blick optisch, aber sobald man näher hinsieht springt einem das ins Auge und man bekommt sofort Krebs).

    Den ASM Code habe ich hier:

    Und TATSACHE, ich speichere in xmm0 die Gesamtabweichung über alle Pixel und gehe davon aus, dass es 0 initialisiert ist. Bist du Hellseher? Woher wusstest du das? (Der Code war nicht beigelegt. Da war wohl Dr. Decompile am Werk, oder deine Glaskugel ist meiner weit überlegen)

    PS Der Code kommt eigentlich komplett ohne SSE aus, xmm wird nur zum hochzählen verwendet weil ein Register gefehlt hat. 3 Schläge auf den Hinterkopf für mich... Ich bin schon auf dem Level eines handelsüblichen Compilers angekommen :( (Wollte aber nicht zu viel Arbeit reinstecken, weil ich darin keinen Flaschenhals sehe, vorallem wenn ein AutoIt Befehl länger dauert als die Abweichung zwischen 2 Vollbildern zu berechnen... übertrieben dargestellt, so schnell ist das natürlich nicht :) )

    Oh wurde wohl doch ein langer Kommentar^^

  • [GDI+] Bild aus anderem Bild zusammensetzen

    Moin,

    habe letztens ein "Kunstwerk" gesehen das nichts anderes war als aus vielen kleinen Bildern/Teilbildern ein neues Bild zusammenzusetzen. Das lässt sich auch mit einem Skript ziemlich einfach erledigen.

    Meine Methode ist folgendes:

    - Teile Quellbild (Q), Zielbild (Z) und zusammengesetztes Bild (R) in Rechtecke der Größe P * P

    - Wähle zufälliges Teilbild von Z

    - Wähle aus den Teilbilgern von Q das Bild was am besten passt aus

    - Lösche das gewählte Bild aus Q (man kann Teilbilder nur 1x nutzen)

    - Setze das gewählte Bild an die richtige Stelle von R

    - Solange bis keine Teilbilder von Q mehr übrig sind

    Probleme:

    - Ewig lange Laufzeit (und aus irgendwelchen Gründen gibt mein ASM manchmal nichts aus, wenn man zu schnell auf den Speicher zugreift, daher das Sleep(0) vor jedem Aufruf)

    - Die letzten paar Teilbilder passen nicht gut, da in Q nur noch z.B. 5 übrig sind die aber alle nicht zu den letzten 5 Teilen aus Z passen.

    - (Zumindest in jetziger Ausführung) müssen Q und Z exakt gleichgroß sein und Breite sowie Höhe muss durch P teilbar sein.

    - Nicht optimiert, da geht geschwindigkeitstechnisch noch einiges, aber ich hatte keine Lust :(

    Im Beispiel habe ich natürlich etwas geschummelt und zwei Bilder beigelegt die sich super ineinander umwandeln lassen weil sie gleich viel Schwarz und Weiß enthalten.:*

    Falls jemand Ideen für einen besseren Algorithmus hat, oder genau das gleiche auch schonmal gebastelt hat kann es ja hier verlinken :)

    Edit 20.10.2018:

    Habe erstmal den Code aufgeräumt (und den Algorithmus klarer gemacht, sodass man jetzt viel leichter daran herumbasteln kann) und ein paar kleine Änderungen vorgenommen. Die Funktionalität ist vollständig unverändert (es wird nach wie vor der gleiche O(n²) schwere Algorithmus verwendet). Durch einige Optimierungen/Fehlerbeseitigungen (DANKE an Andy für seinen xmm0 Tip) konnte ich ca. 30% mehr Tempo rausholen (statt 15s braucht das Skript nun nur noch 11s).

    Beim nächsten Mal wird der Algorithmus selbst angegangen, habe da schon einige gute Ideen die eine n^(3/2) Komplexität erreichen könnten. Ausprobieren hat gezeigt, die Laufzeit damit ca. 10-15x kürzer ist (für das kleine Testbild), bei großen Bildern ist da natürlich weeesentlich mehr drin, allerdings bin ich mit dem Ergebnis noch nicht zufrieden.

    Wer es ausprobieren will kann in Zeile 98 und 102 das $iUBound_SrcLinear durch Ceiling($iUBound_SrcLinear^0.5) ersetzen, damit wird nicht mehr allzuviel verglichen, das Resultat leidet aber deutlich. Andere Exponenten wie z.B. 0.8 ergeben nahezu das gleiche Ergebnis bei ca. 1/3 Laufzeit, da geht also was.

    Meine Hoffnung ist, dass zufälliges versuchen (anstatt lineares) ein nahezu identisches Ergebnis liefert wie die Ursprungsfunktion, aber 10x schneller läuft.) Zuletzt kommt noch eine Fehlerkorrektur die ich in Post3 schon angerissen habe, damit sollten die Resultätbilder weniger störende "offensichtlich falsche" Rechtecke mehr haben.

    Weiterhin halte ich vom Vergleich der Durchschnittsfarbe nicht viel, das würde zwar den ASM Teil beschleunigen (der sowieso schon schnell ist). Habe ausprobiert, dass eine Verkleinerung des Bildes von 512x512 auf 256x256 bei gleicher Zerlegung (also gleicher Anzahl) ca. 10% mehr Tempo bringt. Man könnte intern das Bild auf 1/x herunterskalieren um so nochmal ca. 50% rauszuholen, aber bei 1x1 Pixel vergleichen leidet die Genauigkeit extrem, der Trick soll ja sein dass die Teilbilder auch die Form ganz gut wiederspiegeln. Für einen "ersten Vergleich" kann man den 1px Vergleich ggf. heranziehen und wenn man sieht, dass das Teil sowieso nicht passt direkt zum nächsten wandern als einen "richtigen" Vergleich zu starten.

    Edit 24.10.2018:

    Sehr viel Bastelei später und sehr viele Erklärungen (die im Code stehen) später hat sich ergeben, dass man über soetwas wie "Qualitätsschalter" nicht drum herumkommt. Man muss irgendwo einstellen können was man haben will. Dafür gibt es jetzt eine ganze Palette verschiedene Sachen:

    - iPixelsize - Kennt man, in diese Stückchen wird das Bild zerlegt. Zukünftig soll das noch in W und H geändert werden damit es nicht immer gleichseitige Vierecke sein müssen

    - bMultipleds- False/True - Man kann nun erlauben Teile doppelt zu verwenden. Bei den meisten Bildern ist das Sinnvoll

    - iShuffleCount - Intern wird sehr viel gewürfelt. Was das bringt genau zu erklären sprengt den Rahmen, daher iShufflecount ist die Obergrenze für erlaubte Mehrfachvorkommen, falls bMultiples = true, und auch ansonsten bedeutet "ab und zu mal Würfeln" bessere Ergebnisse. Zu viel würfeln ist aber sinnlos, es sollte sich so im Rahmen 4 bis 64 bewegen, je nach Anzahl Teilbilder.

    - fExponent - Hier ist der Hauptgeschwindigkeitsschalter, er bestimmt wie viele Vergleiche durchgeführt werden. Bei z.B. e = 0.5 wird in jedem Durchlauf jedes Bild nur mit Sqrt(n) Teilbildern verglichen, sodass man damit von der n² Komplexität herunterkommt. Ist dieser Wert 1 wird Brute Force ALLES durchprobiert.

    - iCorrectionTime - Nachdem das Bild fertig ist werden gezielt Teile mit schlechter Abweichung so vertauscht, dass die Gesamtabweichung sinkt. Leider gibt es dafür kein gutes Maß "wie oft" man das machen muss (oder mir ist keines eingefallen), daher ist das ein Multiplikator. Bei Time = 1 wird die gleiche Zeit die der Zusammensetzalgo gebraucht hat erneut für Korrekturen aufgewendet. Hier kann sicherlich noch viel optimiert werden, aber es funktioniert erstmal.

    Kurz zusammengefasst gibt es Qualitätsprofile: low (Ergebnis ist besser als das best mögliche Ergebnis des vorherigen Algo und ca. 7x schneller), mid (ca. 3x schneller als vorher), high (vergleichbar schnell wie der vorherige, aber wesentlich besseres Ergebnis), max (Brute Force, langsam, wählt ÜBERALL das best passende Teil)

    Mal schauen wann ich Lust habe weiterzubasteln, have fun :)

    (wer läd eigentlich immer die alten Dateien herunter, die sind eigentlich nur zum Vergleich da damit man sieht was sich verändert hat^^)

    lg

    M

  • Doodle Jump gesucht

    Ja das ist hier etwas zu einer Grundsatzdiskussion geworden. Ich finde es auch schrecklich, dass sehr viele alte Skripte einfach nicht mehr lauffähig sind. Aber das davor die meisten Softwarefirmen sicher sind ist ein Irrtum, die kapseln ihre Sachen nur ab und haben anständig definierte Schnittstellen. Könnte wetten dass 80% aller dlls die man so verwendet mit den aktuellen Softwareversionen nicht mehr kompilierbar sind. Deshalb sind die Programme heutzutage oft auch so unnötig groß, weil sie teilweise nur einen Bruchteil von irgendwelchem abgekapselten Code brauchen und dafür die ganze Kiste mitnehmen müssen.

  • Doodle Jump gesucht

    Ich weiß nicht wie lange das her ist, aber früher war Hex($a) implizit ein Hex(Int($a)). Daher tauchen in manchen alten Skripten unnsinnige Werte bei gewissen Rechnungen auf die Hex() benutzen. Da muss man dann ein Hex(Int()) draus machen. (Hab mir den Quellcode hier nicht angesehen, vllt taucht das garnicht auf, könnte aber z.B. irgendwo bei Koordinatenberechnungen verwendet worden sein, sodass die Gegner nicht mehr auftauchen, weil sie irgendwo außerhalb des Bildschirms sind). Der Vollständigkeit halber aber mal erwähnt.

  • GDIPlus Kreisbogen ( G02 und G03 )

    Wahrscheinlich ist mein Post hier überflüssig, aber für Kreisausschnitte habe ich in einem alten Skript folgendes gefunden:

    AutoIt
    Func _PieSegment($GFX, $mX, $mY, $W, $H, $D, $fStart, $fSweep, $iCol)
    DllCall($__g_hGDIPDll, 'int', 'GdipDrawArc', 'handle', $GFX, 'handle', $PEN, 'float', $mX + $D / 2 - $W / 2, 'float', $mY + $D / 2 - $H / 2, 'float', $W - $D, 'float', $H - $D, 'float', $fStart, 'float', $fSweep)
EndFunc   ;==>_PieSegment

    Macht genau was man vermutet: Mittelpunkt, Durchmesser, Startwinkel und Überspannender Winkel müssen bekannt sein und dann malt es einen Teilkreis (W und H sind größen der zu bemalenden Fläche).

    [GDI+] Rotierende Kreisausschnittsegmente

    (Hilft wahrscheinlich nicht sonderlich weiter, der Vollständigkeit halber aber mal erwähnt :P)

    lg

    M

  • GUICtrlCreate Dummy? Was macht das?

    Da ein Dummy ebenfalls eine CtrlID zugewiesen bekommt kann man andere Ctrl-Elemente via Offset ansprechen. (ich glaube das habe ich insgesamt nur 1x irgendwo gemacht weil es sonst nie sinnvoll war, aber der Vollständigkeit halber ein Beispielskript)

    lg

    M

  • GaussKernel (z.B. für Gauß'sche Unschärfe)

    Moin,

    Habe für einen Unschärfealgorithmus (in Go, daher gibts hier keinen AutoIt-Code) verschiedene Integrale der Gaußkurve gebraucht. Zum Glück konnte mir AspirinJunkie mit seiner Stat-UDF aushelfen. Für den extrem unwahrscheinlichen Fall, dass irgendjemand manuell einen Gauß-Filter basteln möchte (und noch einen Filterkern braucht) kann er sich gerne an meinem Skript dazu bedienen. Sowas kann man sich auch auf die Schnelle selbst zusammenbasteln, aber schön aufgeräumt/formatiert sieht es doch besser aus, villeicht spart dieses Skript irgendwem 5 Minuten seiner Lebenszeit ein, dann bin ich schon zufrieden :)

    Edit: Für AutoIt gibts absichtlich keinen Konsolen Export, da man das Skript einfach einfügen kann und die nötigen Daten zur Laufzeit generieren kann. Den Teil zu programmieren ist kein großer Aufwand, wer es unbedingt braucht kann ihn gerne ergänzen :)

    Edit2: Es gibt auch einen Online Generator unter LINK. Dieser hat aber eine andere Interpretation, sodass dort eine andere Abhängigkeit zwischen Sigma und dem Radius vorliegt (z.B. ist _GK_KernelCreate(2, 2.5, 4) äquivalent zu Sigma = 1 und Durchmesser = 5 im Online Generator, unten in der angezeigten Grafik auf der Seite sieht man auch deutlich, dass die Rechtecke bei 2.5 Sigma aufhören). Welche Interpretation die richtige ist weiß nur der Wind.

    lg

    M

  • Flood Fill

    Ich glaube ich bin hier Opfer eines XY Problems geworden und mit meinem Tunnelblick habe ich es selbst nicht bemerkt.

    Ich will X, suche Y, bekomme irgendwas zwischen Y und Z mit einer Prise X und frage mich was X eigentlich war :D

    -> +

    X: (Das habe ich gesucht)

    Ein mit einer ein Pixel breiten schwarzen (0xFF000000) Linie begrenztes Gebiet identifizieren/kopieren/schwerpunkt.

    - identifizieren: Im Anhangbild sind 2 gebiete. Es sollen beide getrennt wahrgenommen werden. (daher kein FloodFill durch diagonalen)

    - kopieren: Es soll eine Bitmap die genau Breite und Höhe des Gebiets hat geben die eine Kopie des Gebiets enthält. Da man vorher nicht weiß wie groß das Gebiet ist kann man zuerst eine zu große Bitmap (Gebietgröße ist immer kleiner als irgendeine Vorgabe z.B. 256px) erstellen, kopieren und nachher die Ränder abschneiden/extrahieren/etc.

    - schwerpunkt: Einfach der Mittelwert aller Positionen aller Pixel des Gebiets.

    Y: (Danach habe ich gefragt)

    FloodFill mit zugänglicher R/W Funktion. Mein bisheriges Programm verwendet FloodFill und vergleicht Werte wie xMin und xMax und y mit einem übergeordneten x, y, w, h für das Gebiet um herauszufinden wie groß das Gebiet ist. Gleichzeitig kann man mit der Write Funktion die einzelnen Pixel in eine 2te Bitmap kopieren, aus der man dann, mit den ermittelten Werten zur Gebietsgröße (und mit dem Startwert wo FloodFill angesetzt wurde) das Gebiet direkt extrahieren (DrawRectRect) kann. Da man ggf. hunderte oder "viele große" Gebiete hat muss die Funktion möglichst schnell sein.

    Z: (Das wurde entwickelt)

    Schnelle FloodFill Methoden die in ASM wahrscheinlich überragend schnell sind und schnelle FloodFill Methoden die in AutoIt sehr schnell (die schnellste ist fehlerhaft) sind.

    Alternative/Erweiterung zu X: (das wurde noch garnicht erwähnt)

    Sinnvoller ist eigentlich sogar eine Vektorisierung des Gebiets, da man dann transformationen wie z.B. Breite * 1.5 oder Rotation um 15° fehlerfrei durchführen kann, während man für Pixelgebilde immer anschließend auf Artefaktbeseitigungstour gehen muss. Da hatte ich geplant, diese anschließend aus den einzelnen Bitmaps mit den einzelnen Gebieten anzufertigen (Rand ablaufen und überall Punkte setzen, sodass man später mit Draw/Fill Polygon das Gebiet EXAKT (nur das Gebiet, nicht der Rand, den braucht niemand) rekonstruieren kann, hier darf es zumindest ohne Transformation keinen einzigen Pixel Abweichung geben).

    Das Problem wollte ich möglichst klein halten und habe mich daher auf die FloodFill Komponente beschränkt, aber bevor Andy jetzt ambitioniert eine Lösung für Y findet will ich ihn bremsen. Die Verwirrung war mein Fehler, entschuldigt bitte...

    Falls sich jemand fragt für was man so einen Unfug braucht: Googelt mal das DOS Spiel Conquest. Der Hersteller davon hat vor 10+ Jahren eine Windows Version geschrieben die unvorstellbarer Schrott ist, das kann ich mit Sicherheit wesentlich besser. Dafür will ich auf einen Mapeditor verzichten, eine Map wird mit Paint gemalt und vom Programm analysiert, sodass JEDER eine Map machen kann ohne von irgendwas irgendeine Ahnung zu haben.

    CONQMAP.PNG

    (Beispiel der Standardmap aus dem Originalspiel. Statt einen Mapeditor zu verwenden kann man diese Karte auch mit Paint malen, sofern man sich ein ein paar Farbvorgaben hält (z.B. Gebietbonus hat gleiche Farbe wie zugehöriges Gebiet, Hintergrund hat dieses seltsame Blau, Verbindungslinien sind Weiß, usw usw.).


    lg

    M

  • Flood Fill

    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

  • Flood Fill

    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

  • Flood Fill

    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.

  • Flood Fill

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

  • AutoIt Package/Module Manager

    Da man an SCiTe oder den Au3Check und andere Tools nicht ran kommt (sowas würde Sinn machen, wenn das vom Präprozessor direkt gefressen und included wird), wäre das vielleicht eine Idee fürs ISN Autoit Studio ?

    Richtig dufte wäre, wenn man einfach #onlineInclude "Aspirinjunkie.JSON" ganz normal in die Includes schreibt und der Präprozessor beim ersten Ausführen dieser Zeile automatisch nach dem Include sucht, es herunterlät und dann normal included (und natürlich sobald es heruntergeladen ist auch die Autovervollständigung aktualisiert usw.)

    Das doofe ist, dass man als Scite Nutzer erst irgendeinen Zusatz installieren müsste (Präprozessor und geändertes Au3Check), in ISN könnte man das direkt fest verbauen.

    Aber das ist Zukunftsmusik, erstmal brauchen wir einen "UDF" Foren Abschnitt.

  • Flood Fill

    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

  • Flood Fill

    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
    - FF1:     Schließt garnichts aus. (effektive Reads: 4/px)
- FF2:     Checkt alle 4 Pixel, mit Puffer für 1 Pixel. (effektive Reads: 3/px)
- Andy1&2: Checkt alle 4 Pixel mit Puffer für 4 Pixel für alle 4 Pixel. (effektive Reads: 1/px)
- 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)

  • Flood Fill

    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.