Bildausschnitt mit Bild vergleichen

[Nikolas]

> Also müsste ich rein theoretisch 60 x 75 Pixel vergleichen (4500)

In der ganz naiven Methode schiebst du den kleinen Bildausschnitt an alle möglichen Positionen und summierst dann über alle Pixel des kleinen Bild den unterschied zum Pixel im großen Bild. Bei 70x85 und 10x10 sind das 60*57 Vergleiche und jeweils 100Vergleiche. Wenn du allerdings weisst, dass das kleine Bild exakt aus dem großem kopiert wurde, kannst du natürlich nach dem ersten unterschiedlichen Pixel aufhören und wirst in den meisten Fällen wirklich mit einem Aufwand rechnen können, der grob der Anzahl der Pixel im großen Bild entspricht.

Aber nochmal zum Verständnis: Du hast einen kleinen Ausschnitt und 15000 Bilder aus dem er stammen kann. Was für eine Art Spiel ist das eigentlich? So richtig einen Sinn kann ich dahinter nichts sehen...

[Medium]

Da wird's mit schnell aber recht flott eng. Nimmt man die Bildgröße mal der Anzahl, hast du es mit rund 94 mio. Pixeln zu tun, so dass die Gesamtaufgabe wird: Finde ein 10x10 Pixel großen Bereich in einem ca. 9700x9700 Pixel großen Bild. (Da man nicht über Bildkanten hinaus vergleichen muss, ist der Wert genorös abgerundet um das mit abzuschätzen. Grad keine Lust das ganz genau zu berechnen )

Der Best-Case ist zwar in 100 Vergleichen abgetan (sofortiger Fund), aber:
24 Bit RGB kann zwischen 16.777.216 Farben unterscheiden. Dein "Pool" ist ~94.000.000 Pixel, was heisst, dass statistisch jede Farbe 5,6 Mal vor kommt, so dass selbst mit der "early-out"-Optimierung eher selten nach dem ersten Vergleich Schluss ist. Nach dem 2. ist es schon ganz erheblich wahrscheinlicher (kommt halt auch sehr stark auf die Ähnlichkeiten der Bilder untereinander an). Du musst also zum Ausschließen einer Position grob geschätzt im Mittel(!) mindestens 2 Vergleiche haben, so dass du im best worst case schon ~188.000.000 Vergleiche brauchst. Im aller schlimmsten (aber auch extrem unwahrscheinlichen) Worst-Worst-Case bist du bei ~9.400.000.000 Operationen. Die Spanne ist riesig! 100 bis 9 Milliarden Operationen. Der mittlere zu erwartende Aufwand hängt dann von den konkreten Bildern selbst ab.
Man nagle mich jetzt auch nicht auf genaue Werte fest, das sind alles Pi*Daumen Schätzungen, um ein Gefühl für die Größenordnungen zu bekommen.
(Und wenn das Kandidatenbild bzw. die Basisbilder nicht 100%ig exakt sind (z.B. jpeg Kompression im Spiel ist), muss man das ganze auch noch tolerant gestalten, was die Rechenzeit gerne auch mal sehr merklich erhöht. Just in case...)

Nebenbei: Die Basisdaten verbraten 70*85*24/8 = 282.744.000 Byte im Speicher. Wenn das ganze eine isolierte Funktion eines Tools ist, locker verschmerzbar. Wenn es zu einem größeren Programm gehört, lohnt es sich ggf. aber auch da drauf zu gucken und ggf. etwas Cashing zu betreiben. Ist jetzt an sich nicht kritisch, aber genug um's zu erwähnen

Jetzt die spannende Frage: Wie schnell brauchst du diese Funktion? Und: Muss sie verlässlich N mal pro Zeiteinheit ausgeführt werden?

[AbesCid]

Erst einmal wieder vielen Dank für eure Antworten und den interessanten Gedanken

An Nikolas:
Das ganze ist für ein Online Spiel. Es gibt Sets, diese bestehen aus jeweils 12 Karten. Das eigentliche Spiel zeigt mir ein Bild und aus diesem Bild soll ich erkennen welche "große" Karte gemeint ist. Das müsst ihr nicht unbedingt verstehen. Es handelt sich dabei um eine Art Zeitvertreib. Wenn du nun das Bild erkannt hast, dann bekommst du Preise etc.
Wie gesagt es ist eher ein Spiel und daher auch nicht soooo wichtig. Ich habe für dieses Onlinespiel schon einige Programme geschrieben, die mir einen Vorteil verschaffen. Einige sagen jetzt sicher Betrug, aber ich programmiere die Programme aus Spaß und nicht nur, um einen Vorteil zu erhaschen.
Vielmehr bin ich stolz darauf ein nutzbares Programm geschrieben zu haben, welches auch wirklich funktioniert.
So zurück zum Thema und gleich zur Frage von Medium.
Wie du nun bestimmt schon erahnen kannst (aus meiner obigen Antwort) brauche ich die Funktion nicht unbedingt. Es ging mir einfach nur darum, ob ich so etwas mit einer einfachen Funktion von Delphi hätte programmieren können. Mehr nicht. Da sich das nun alles sehr kompliziert erweist bzw. anhört, werde ich mich irgendwann später nochmal mit der Sache beschäftigen oder eben einfach sein lassen.

Dennoch vielen Dank für eure Hilfe und fürs Erschlagen mit den vielen Zahlen

Außerdem sollte ich mich mal mit effektiverem Programmieren beschäftigen. Leider verschaffen meine bisherigen Programme sehr viel CPU-Auslastung (teilweise bis 100% und eine Spreicherauslastung von ca. 20.000 K).

Wie kann ich so etwas optimieren? (jetzt fange ich gleich eine neue Frage in einer Frage an ... ahh -> ich bitte um Verzeihung)
Also wo ist das Problem? Muss ich nach Optimierung suchen (hier im Forum) oder wie oder was?

[blackfin]

Zitat:

Da wird's mit schnell aber recht flott eng.

Der Satz gehört in eine Zitate-Liste

[youuu]

Hm sollte es nicht möglich sein, die Autoit Bibliotheken zu implementieren und dann die relative gut vorhanden Pixel Funktionen zu verwenden?

[bernhard_LA]

für die technische Lösung dieses Themas habe ich einen neuen Thread aufgemacht :


http://www.delphipraxis.net/165081-c...ml#post1141307