GetUniqueColors

AspirinJunkie Bei mir funzt dein Skript nicht.

CountColors.au3" (28) : ==> Subscript used on non-accessible variable.:
Return $a_Ret[0]
Return $a_Ret^ ERROR

Eventuell fehlen die Visual C++ 2017 Runtimes?

Also von hier ganz unten: https://www.visualstudio.com/de/downloads/

Ist bereits installiert.

Ok dann weiß ich es spontan auch nicht.
Hab es hier auf Win10 x64 laufen und es läuft sowohl als x64 als auch als x86 dll.

Eventuell hab ich gegen eine Win10-API gelinkt. Nutzt du Windows 10 oder vielleicht was anderes?
Heute komm ich aber sicher nicht mehr dazu genauer nachzuschauen - wenn dann morgen Abend.

Edit: Hab es gerade auf einem Win 8.1 x64 probiert: Nachdem ich die VS 2017 Redistributables installiert habe lief es auch dort.
Kann es eventuell nochmal jemand anderes versuchen?

Zitat von AspirinJunkie

Kann es eventuell nochmal jemand anderes versuchen?

Test OK

System : Windows 7 Pro SP1 - 64 Bit

VC Runtime 2017 (VC_redist.x64.exe) muss installiert sein !

(siehe EDIT : 2013, 2015 und 2017 funktionieren !)

#AutoIt3Wrapper_UseX64=y

Zeitbedarf : 130 - 160 ms ; Anzahl Farben: 99394

#AutoIt3Wrapper_UseX64=n

Zeitbedarf : 130 - 160 ms ; Anzahl Farben: 99394

EDIT : Nachtrag

Ich habe die VC Runtimes 2013, 2015 und 2017 entfernt (x86 und x64).

Dann kommt die Fehlermeldung : MSVCP140.dll fehlt !

- Es reicht also aus, die VC Runtimes 2015 (x86 und x64) zu installieren !

- VC Runtimes 2013 (x86 und x64) funktionieren auch !

Gruß Musashi

Zitat von Musashi

Es reicht also aus, die VC Runtimes 2015 (x86 und x64) zu installieren !

Du kannst auch einfach die DLL in das selbe Verzeichnis packen (oder irgendwo im Windowsordner) und dann hast du das gleiche Ergebnis.

Ich habs nicht gerne, wenn auf meinem Rechner 50.000 Runtimes drauf sind, wenn eine DLL fehlt lade ich sie einzeln runter und schiebe sie ins Verzeichnis.

Zitat von alpines

Du kannst auch einfach die DLL in das selbe Verzeichnis packen (oder irgendwo im Windowsordner) und dann hast du das gleiche Ergebnis.

Ich habs nicht gerne, wenn auf meinem Rechner 50.000 Runtimes drauf sind, wenn eine DLL fehlt lade ich sie einzeln runter und schiebe sie ins Verzeichnis.

Ich im Allgemeinen auch nicht . (Nebenbei : Dass es ausreicht, die entsprechende .Dll zu kopieren ist mir bekannt)

Die VC Runtime Installer sind, für Microsoft-Verhältnisse, aber recht sauber programmiert. Ich hatte nie irgendwelche Konflikte bzw. Probleme, sie (sogar im laufenden Betrieb) zu installieren oder zu deinstallieren. Viele Programme installieren die benötigte Version eh gleich mit. Außerdem werden sie durch die Installation unter Systemsteuerung->Programme gut sichtbar aufgelistet. Ich weiß nicht, ob das durch ein Kopieren der .Dll auch so ist.

Ergänzung (Beispiel) :

-> Man installiert Programm A (benötigt z.B. die VC Runtime 2015). Der VC Installer wird im Rahmen des Setups automatisch ausgeführt und prüft, ob die entsprechende Runtime existiert. Falls nicht, wird sie installiert.

-> Man installiert Programm B (gleiches Szenario). Der VC Installer erkennt, dass die benötigte Runtime bereits vorhanden ist und überspringt die Installation.

==> Die Runtime wird nun also von beiden Programmen genutzt !

-> Programm A wird deinstalliert.

Bei schlecht programmierten Uninstallern habe ich aber schon gesehen, dass auch die Runtime deinstalliert wird.

Das ist natürlich fatal, da man somit dem Programm B die Hand unter dem A*rsch wegzieht .

(Gleiches gilt für das manuelle Entfernen einer Runtime !)

Dieses Problem könnte man mit der von alpines beschriebenen Vorgehensweise entschärfen.

Allerdings wird man, wie gesagt, von vielen Setups aber gar nicht erst gefragt, ob eine Runtime installiert werden soll.

Gruß Musashi

Zitat von BugFix

Laut Bildbetrachter XnView sind es 103240 Farben - ein bischen Schwund ist immer

[...]

Anzahl Farben: 99394 (in XnView: 99375)

XnView zählt mal mehr, mal weniger als diese Funktion. (Wer zählt von Hand nach? )

Ist der selbe Grund wie hier schon vorher genannt. Liegt am JPEG-Decoder der unterschiedliche Ergebnisse produziert.

Lass dir die Datei in XNView mal als PNG ausgeben dann sollten die Zahlen bei beiden übereinstimmen.

Habe der DLL mal noch eine Multithread-Version hinzugefügt.
Hätte nicht gedacht dass es viel ausmacht aber gerade bei großen Bildern bringt es wirklich einen großen Unterschied.

Siehe Anhang

Zitat von Oscar

Wie würde die Multi-Thread-Version wohl mit der Array-Methode aussehen?

Zeig mir mal den Single-Thread Code und ich füg ihn noch als Threaded-Version der DLL hinzu.

AspirinJunkie : diesmal funktionieren die DLLs:

x64:

Dimension: 7360x4912
Single-Thread-Version:
          Zeitbedarf:  5196.39 ms
       Anzahl Farben:   402990

Multi-Thread-Version:
          Zeitbedarf:   865.69 ms
       Anzahl Farben:   402990

Hier meine x86 FreeBasic ST Version:

Loading image
Image dimensions: 7360x4912
Counting all 24-bit colors
Unique color count: 402990
1318.890535639614 ms

Ich glaube nicht, dass MT hier noch was bringt bzw. MT sich richtig lohnt.

FB Version siehe unten.

Oscar

Multi-Threading wird bei dieser Lösung wohl fast keinen großen Sinn machen.

Warum? Nun wir haben hier den klassischen Fall von Race-Conditions.

Schauen wir uns mal den wichtigen Codeausschnitt an:

for(int i = 0; i < len; i++) {            
   if (colors[aPixel[i] & 0xffffff] == 0){
      colorSum++;
      colors[aPixel[i] & 0xffffff] = 1;
   }
}

Was passiert in einem besonders blöden Fall:

• Thread 1 hat ein Pixel mit der Farbe 0 (schwarz also).
• Thread 1 fragt an der entsprechenden Stelle im Array colors nach ( [0] ) und vergleicht dort auf 0 -> Ergebnis: Es ist noch 0
• Also springt Thread 1 in den True-Case der If-Verzweigung
• In der Zwischenzeit hat Thread 2 ebenfalls ein Pixel der Farbe 0 und testet gegen das Array colors -> und siehe da: Noch ist der Wert dort ebenfalls noch 0 da Thread 1 ja noch nicht geschrieben hat und springt ebenfalls in den True-Case
• colorSum wird dann einmal von Thread 1 als auch nochmal von Thread 2 inkrementiert.
• Die Farbe schwarz wurde also fälschlicherweise doppelt gezählt!
• Unser Ergebnis wird also höher sein als das korrekte.

Nun wie kann man das nun verhindern?
Im Grunde durch Locks oder atomare Prozeduren.

Der Lock müsste im Grunde aber auf die ganze If-Abfrage gesetzt werden. Da damit der gesamte Schleifeninhalt hierbei als nichtparallel definiert wird kann man sich diese Lösung ergo aber schenken wenn man das ganze parallelisieren möchte.

Atomare Typen und Prozeduren als Alternative hierzu bringen hingegen soviel Overhead mit, dass der Geschwindigkeitsvorteil durch die Parallelisierung davon wieder mehr als aufgefressen wird.

Kurz: Auf Anhieb hab ich keine Lösung wie man bei einer Parallelisierung korrekte Werte erhält und dennoch einen Performancezuwachs gegenüber der Single-Thread-Variante erwarten kann. Vielleicht finde ich noch ne Lösung - mal schauen.

Die Multithread-Variante die zwar fix ist aber leicht falsche Ergebnisse produziert habe ich mal zum Nachvollziehen in der DLL belassen.

Edit: So nun doch eine Variante gefunden welche zumindest bei großen Bildern bessere Performance liefern kann und dennoch korrekte Werte liefert (über die Windows-API-Funktion InterlockedIncrement16 umgesetzt).

UEZ

Oh super. Blöd nur dass wir bis jetzt nicht wissen warum die erste DLL bei dir nicht funktioniert hat.

Zitat von UEZ

Ich glaube nicht, dass MT hier noch was bringt bzw. MT sich richtig lohnt.

Warum nicht?

Zitat von Oscar

Bezüglich der "nur 24Bit": Wenn man "_GDIPlus_BitmapLockBits" mit "$GDIP_PXF32PARGB", also PARGB aufruft, dann werden die Alphawerte doch vorher auf die RGB-Werte umgerechnet und somit müsste die Anzahl der Farben wieder stimmen, oder liege ich da falsch?

Naja kommt halt darauf an was du genau zählen willst.
Der Alpha-Channel ist kein Farbwert an sich - klar. Aber er beeinflusst dennoch die Darstellung des jeweiligen Pixels.

Jetzt ist die Frage ob man diese Info dazuzählen möchte oder lediglich das Endergebnis auf einem homogenen Hintergrund wichtig ist.

Wenn man den Alphachannel als eigenständigen Kanal betrachten will dann kann PARGB hingegen nicht die Lösung sein.
Wir haben in diesem Fall eine surjektive Abbildung von 32Bit auf 24Bit -> also einen Informationsverlust.
Unterschiedliche Ausgangswerte können also gleiche Ergebniswerte produzieren, was dazu führt, dass eigentlich unterschiedliche Farbwerte fälschlicherweise als gleichfarbig gezählt werden.

Also wie gesagt: Was willst du genau zählen bzw. wozu brauchst du es?

Man könnte MT nutzen und das Array statt auf den Wert 1 zu setzen um 1 erhöhen (Das Array ist ja sowieso mit byte[] besetzt). Damit springen wir zwar wieder zurück auf die Abfrage "> 0" statt "==0" das sollte in C und ASM aber keinen Unterschied machen (je 1 Takt). Die "zuviel" gezählten Farben müssen nun den "zuviel" gezählten Werten im Array entsprechen.

Beispiel:

4 Threads, alle 4 testen gleichzeitig einen Pixel mit der gleichen Farbe.

-> byte[col] = 4 (nachdem alle Threads fertig sind)

-> farbcounter = 4 (nachdem alle Threads fertig sind)

Die Tatsächliche Anzahl Farben ist also: farbcounter MINUS (Summe der Bytestruct MINUS 1 für jedes Element >0) = 4 - 3 = 1

Zusatzaufwand:

- Summe der 4 farbcounter (das sind nur ein paar Takte, oder kann man hier Threadübergreifend den gleichen nehmen?)

- Summe der (Bytestruct - 1) für jedes Element >0. (das wird etwas Zeit brauchen, bei 2^24 Elementen und angenommenen 3ghz -> ca. 15-20 Millisekunden, wobei sich dieser Vorgang ebenfalls parallelisieren lässt in z.B. 4*2^22 Elemente)

Voraussetzungen:

- Weniger als 256 Threads (da die Bytestruct sonst im Zweifelsfall überläuft)

- Information was passiert, wenn 2 oder mehr Threads eine Speicherstelle um 1 erhöhen. Werden dann tatsächlich alle Erhöhungen gemacht?

M

Zitat von Mars

byte[col] = 4 (nachdem alle Threads fertig sind)

Nicht unbedingt.
Inkrement funktioniert (falls es kein atomares inkrement ist) so:

• aktuellen Wert aus Speicher auslesen
• im Register addieren
• Neuen Wert schreiben

Gehen wir doch mal einen möglichen Fall das 4 Threads gleichzeitig die selbe Farbe haben durch:

• Thread 1 liest aus -> 0
• Thread 2 liest aus -> 0
• Thread 1 addiert 1 im Register (Registerwert = 1)
• Thread 3 liest aus -> 0
• Thread 2 addiert 1 im Register (Registerwert = 1)
• Thread 1 schreibt seinen Wert zurück in den Speicher -> 1
• Thread 4 liest aus -> 1
• Thread 2 schreibt seinen Wert zurück in den Speicher -> 1
• Thread 3 addiert 1 im Register -> (Registerwert = 1)
• Thread 3 schreibt seinen Wert zurück in Speicher -> 1
• Thread 4 addiert 1 im Register -> (Registerwert = 2)
• Thread 4 schreibt seinen Wert zurück in den Speicher -> 2

Heißt: 4 Threads haben einen Anfangswert von 0 inkrementiert und nachdem alle fertig sind steht als Ergebnis eine 2 da.

Die nächste Frage ist wie man das Überlaufproblem behandelt. Bei homogenen Bildern wo eine Farbe mehr als 256x vorkommt kommt es zu einem Überlauf und es geht wieder bei 0 los.

Zitat von Mars

farbcounter = 4 (nachdem alle Threads fertig sind)

Die Tatsächliche Anzahl Farben ist also: farbcounter MINUS (Summe der Bytestruct MINUS 1 für jedes Element >0) = 4 - 3 = 1

Wann bestimmst du den Moment dass gerade alle Threads fertig sind und an welcher Stelle soll die anschließende Rechnung stattfinden?

Ich arbeite bei meiner MT-Variante mit einem atomaren Inkrement+Fetch. Heißt: Es ist garantiert dass auf die Speicherstelle für den gesamten Vorgang (auslesen, inkrementieren, neu schreiben) nur ein Thread zugreift.

Anschließend wird der Farbcounter nur hochgezählt wenn das inkrement-Ergebnis 1 ist.

Zum Überlauf:

Sobald eine Farbe ein Mal aufgetreten ist, ist der Wert von byte[col] >0 und die Farbe wird nicht erneut gezählt, also ist es nur wichtig wie viele Threads existieren (da bei gleichzeitigem Lesen der Farbe die einzige Möglichkeit besteht, dass sie doppelt gezählt wird) und nicht wie oft die Farbe im Bild vorkommt.

Zum parallelen Schreiben in die gleiche Variable:

Das wusste ich nicht, da ich noch nicht viel mit MT betrieben habe. Ich dachte bei gleichzeitigem erhöhen einer Variable wird das irgendwie Prozessorintern behandelt, sodass beide Erhöhungen stattfinden. Wenn da quasi alles von 1 bis 4 herauskommen kann funktioniert mein Ansatz natürlich nicht...

Scheint doch nicht so einfach zu sein wie zuerst gedacht

Edit: Ich hatte dein Beispiel weiter oben schon gelesen, aber wohl falsch interpretiert. Da hätte mir eigentlich klar sein müssen wie das abläuft.