GetUniqueColors

  • Ich möchte gern ermitteln, wie viele verschiedene Farben in einem Bild verwendet werden.

    Dazu habe ich mir eine Funktion geschrieben, die alle Pixel durchgeht und in einem Dictionary die Farben speichert.

    Das funktioniert auch recht gut, aber das dauert zu lange. Seht ihr vielleicht noch eine Möglichkeit, das schneller hinzukriegen?

    Als Ergebnis bekomme ich:

    Code
    1. $iW * $iH = 708197 px
    2. Zeit: 4717 ms
    3. Anzahl der Farben: 99394

    Fast 5 Sekunden für so ein kleines Bild dauert mir zu lange.

  • Mit Arrays (vorausgesetzt es existiert keine Transparenz, da das sonst die Arraygrößen sprengt) schaffe ich es in rund 1300ms.

    Den Speicherverbrauch von 80 Megabyte ignorieren wir mal :D

    Code
    1. $iW * $iH = 708197 px
    2. Zeit: 1366 ms
    3. Anzahl der Farben: 99394
  • Ich hatte das hier mal zusammengestellt:

  • Ohne Hex ergibt bei mir 0 Colors. Scheinbar mag das Scripting.Dictionary keine Zahlen als Item.


    alpines : Die Array-Variante ist zumindest schonmal schneller. Um Fehler bei Alphawerten auszuschließen sollte man aber BitAnd benutzen:

    Aber letztendlich ist auch das zu langsam. Wenn ich den Test mit einem 4608 x 3456 Pixel Bild (aus meiner Kamera) mache, dann dauert das fast 34 sekunden.

  • Hm, stimmt. Das ist mir eben nicht aufgefallen, weil die Hexfunktion doch den größten Teil ausmachte (von 6674ms zu 2765ms).

    Wieso ist hier die Zuweisung in ein Array schneller, alpines ? Das widerspricht total meinen bisherigen (geringen) Erfahrungen. Ich war schon so weit, dass ich versuchen wollte alle einfachen Arrays durch Dictionaries zu ersetzen.

  • Wieso ist hier die Zuweisung in ein Array schneller, alpines?

    Nun, ich könnte dir eine komplizierte Erklärung liefern mit Suchlaufzeiten (O(n) etc) und B+ Bäumen aber ich halt es mal kurz und knapp:


    Der Arrayzugriff benötigt eine konstante Laufzeit,

    da der Index direkt angesprochen ist und man mittels $pArrayBase + $iIndexOffset * sizeof($array_entry) den Eintrag direkt adressieren kann.


    Dictionaries sind vermutlich als Bäume implementiert und um einen Eintrag zu finden musst du den Suchbaum durchgehen und immer deinen Eintrag suchen, das kann bei einer effizienten Implementierung auf etwa logarithmische Laufzeit heruntergebrochen werden.


    Der Vorteil der Baumimplementation allerdings wird schnell ersichtlich: Es wird Unmengen an Speicherplatz gespart, da man für jede existierende Farbe Speicher benötigt und in einem Suchbaum nur die Farben gespeichert werden die bisher gefunden wurden.


    Würde man das Array mit jeder gefundenen Farbe redimmen und den Index vergleichen wäre das DEUTLICH langsamer als die Dictionaryvariante.


    //Edit: Dictionaries können aber auch als Hash implementiert sein, die Baumimplementation ist nur eine von vielen Möglichkeiten.

  • Mit Arrays (vorausgesetzt es existiert keine Transparenz, da das sonst die Arraygrößen sprengt) schaffe ich es in rund 1300ms.

    Den Speicherverbrauch von 80 Megabyte ignorieren wir mal :D

    Code
    1. $iW * $iH = 708197 px
    2. Zeit: 1366 ms
    3. Anzahl der Farben: 99394

    Schöne Lösung, mit einem klitzekleinen Fehler:

    Das Array braucht eine Größe von 0xFFFFFF + 1, da du sonst kein Weiß drinnen hast.

  • mit einem klitzekleinen Fehler

    Da hast du natürlich recht, besser wäre wohl 0x1000000 oder zur besseren Veranschaulichung deine Version mit 0xFFFFFF + 1.


    Den anderen "Fehler" hatte Oscar ja schon gewähnt: Lieber BitAND nutzen, ansonsten muss man erst prüfen, ob das Bild Transparenz besitzt.

    Ich weiß allerdings nicht ob BitAnd() oder die einfache Subtraktion (mit kurzer Prüfung im voraus) schneller ist.


    // Ein kleiner Test zeigt, dass beim Testbild die BitAnd Variante bei mir um etwa 100ms langsamer ist.

  • Ich weiß allerdings nicht ob BitAnd() oder die einfache Subtraktion (mit kurzer Prüfung im voraus) schneller ist.

    In jedem Falle ist BitAND richtig, so viel vorweg. Ich habe es jetzt ein paar Mal mit Beidem durchlaufen lassen, das BitAnd dauert um die 100ms länger (1700 vs 1800).


    Soweit ich das jetzt "gemessen" habe, ist das Bottleneck die DllStruct. Schneller als mit alpines' Array wirst du es nicht hinbekommen, es sei denn man nimmt ein Hashset, so wie ich das sehe hast du das aber in der ursprünglichen Version schon getan.

  • Ich habe mal die IsDeclared/Assign-Variante von UEZ noch etwas abgeändert, um noch etwas Geschwindigkeit rauszuholen und auch die Array-Variante von alpines habe ich noch etwas geändert.

    Meine Ursprungsversion mit dem Dictionary habe ich ebenfalls noch etwas verbessert. Mit diesen drei Versionen habe ich Tests mit 3 unterschiedlich großen (klein/mittel/groß) Bildern durchgeführt.

    Ich darf schonmal vorwegnehmen, dass die Array-Variante am schnellsten war. Auch die IsDeclared/Assign-Version hat sich noch ganz gut geschlagen und landete auf Platz 2.

    Die Dictionary-Version ist nicht zu empfehlen. Mit zunehmender Bildgröße benötigt sie immer mehr Zeit (beim großen Bild fast 9 Minuten).

    Das Einzige, was man ihr zugute halten kann, ist, dass sie am wenigsten Speicher benötigte. Das Testscript mit den drei Versionen findet ihr im Anhang.

    Hier die Ergebnisse im einzelnen (Bild klein/mittel/groß):

    Insgesamt muss man wohl sagen, das AutoIt mit dieser Aufgabe überfordert ist.

    Eine Schleife, die über 15 Mio mal durchlaufen werden muss, ist für eine Interpretersprache wohl zu viel.

    Jedenfalls sind die fast 29 Sekunden (für das große Bild) der schnellsten Version immer noch zu langsam.

  • Nur als kleiner Tip: Die Arrayvariante lässt sich noch etwas aufbohren, wenn man die Farben nicht "zählt" sondern einfach nur eine 0 oder eine 1 hinterlegt, je nachdem ob die Farbe schonmal aufgetaucht ist. (Dann verbraucht man auch keine wertvollen Takte um abzuspeichern, dass die Farbe FF4265 genau 5531x aufgetaucht ist).

    ------------------------------------------------------------------------------------------

    Wenn man jetzt von Arrays auf Structs umsteigt kann man (theoretisch) jedes einzelne Bit als Indikator benutzen ob die Farbe bereits vorhanden war (Geringer Speicherverbrauch, langsam) oder man nimmt die Variante, die dem Prozessor am besten schmeckt und nutzt 8Bit (bei Ungerader Pixelzahl muss hier am Ende ein 32er Register vollgestückelt werden glaube ich) oder 32Bit (supereinfach, superschnell, Speicherintensiv. Das Ganze ist auch in ASM ziemlich einfach, ich kann es aber leider gerade nicht machen... sollte für gewisse Leute hier eine Sache von 5 Minuten sein.


    lg

    M

  • Ich habe mal ein bisschen geschummelt und alpines Skript etwas modifiziert. Wenn es wirklich nur um die reine Leistung geht, ist AutoIt halt langsam - wissen wir ja. C aber nicht. :P


    Code
    1. int DLL_EXPORT count_colors(unsigned int* pixel, int len) {
    2. int i, colorSum = 0;
    3. int* colors = calloc(0xffffff + 1, sizeof(unsigned int));
    4. for(i = 0; i < len; i++) {
    5. colors[pixel[i] & 0xffffff] = 1;
    6. }
    7. for(i = 0; i < (0xffffff + 1); i++) colorSum += colors[i];
    8. free(colors);
    9. return colorSum;
    10. }

    Als DLL-Funktion in AutoIt aufgerufen:

    Auf meinem Rechner hier braucht alpines' Ursprungsvariante in einem Testlauf etwa 1737 ms. Mit der DLL sind's dann noch 79 ms. ^^


    HINWEIS: Das Forum erlaubt keine DLL-Anhänge, daher müsst ihr zum Testen bei dem Dateianhang die Endung .au3 wieder entfernen.

  • Nun ja, es sollten auch 32-bit Bilder unterstützt werden, was die schnellste Variante in dieser Version nicht tut.


    Als Beispiel ein Bild mit genau 256 Farben, die nur sich über den Alpha Kanal unterscheiden.

  • Na gut, nach dem scheitern von AutoIt (pur), gehen wir zu einer DLL in C über. :)

    Nachdem Chesstiger eine Vorlage gegeben hat, wollte ich auch mal ein bißchen mit C rumspielen.

    Rausgekommen ist das:

    Compiliert mit dem Tiny C Compiler (TCC) entsteht eine nur 2kB kleine DLL.

    Ich habe mal das AutoIt-Script, die DLL und ein Testbild in das ZIP-Archiv im Anhang gepackt.

    In C ist das Ganze wahnsinnig schnell (bei mir 34 und 49 ms). Selbst mit einem großen Testbild (4608 x 3456 Pixel) dauert es nur 275 ms.

  • ich hab leider keinen C Compiler hier. Hast du ausprobiert, ob es schneller ist im loop (Zeile 9, 10, 11) VOR die Zuweisung der Zahl 1 eine Abfrage mit If colors[pixel[i] & 0xffffff] == 0 Then colorSum++ einzubauen? Dann muss nicht das komplette Array (was ja von 0 bis 0xffffff geht) durchlaufen werden, sondern nur die Parts die relevant sind. Ich schätze das hilft auch in C und ASM ein wenig.


    Edit1: (je nachdem wie der Compiler intern arbeitet muss man ggf das mehrfache Auftreten von pixel[i] & 0xffffff in eine Variable packen, sonst lässt er das mehrfach ausführen, was mehr Ram-Zugriffe bedeutet und damit langsamer sein sollte)

    Edit2: (wieder je nachdem wie es läuft ist colorsum += (1-colors[pixel[i] & 0xffffff]) schneller als das If)

  • Ah, gute Optimierungsmöglichkeiten! :thumbup:

    Das sieht in C jetzt so aus:

    Und schon reduziert sich die Zeit für das große Bild von 275 ms auf 200 ms. Danke für die Verbesserungsvorschläge! :klatschen:

    Die neue DLL befindet sich im Anhang.

  • Ist es denn 100% gewährleistet, dass der Speicher für das Bool auch wirklich 0 ist? Ich meine es gab da was, dass man nicht gewährleisten kann, was im Speicher drinnen steht. Würde das dann nicht im Extremfall zum Ausbleiben von gefundenen Pixeln führen?