Bildausschnitt mit Bild vergleichen

[AbesCid]

Hallo liebe Gemeinde,
auch ich habe mal wieder eine kleine Frage zum Programmieren.

Wie der Titel schon beschreibt möchte ich wissen, ob es überhaupt möglich ist, dass ich einen Bildausschnitt mit einem Bild vergleichen kann und da soll dann im Prinzip true bzw. false ausgegeben werden.
Um es noch einmal genau zu erläutern: Dies ist für eine Art Spiel. Ich bekomme einen Bildausschnitt vorgezeigt und soll dann das passende Bild in groß finden.
Ich poste diesen Beitrag in Netzwerke, weil das alles online ablaufen soll. D.h. ich müsste ersteinmal den Bildausschnitt "herunterladen" und dann diesen mit anderen Bildern vergleichen.

Wie gesagt, das ist erstmal ne Frage, ob es überhaupt mit Delphi geht und was ich alles benötige, um es zu programmieren. (idhttp,...)

Für einige Anregungen bin ich sehr dankbar.

AbesCid

[Desmulator]

Sicherlich sollte es einfach sein die Bilddatei aus dem Internet herrunter zu laden. Wie du erwähnt hast kannst du das mit IdHTTP machen. Dafür müsstest du dann die Datei laden und z.b. in einer tmp-Datei speichern und diese dann als jpg o.Ä. laden, oder direkt vom Socket in den Speicher fürs Bild.

Das eigentlich schwierige wird sein den Bildausschnitt zu finden. Dazu musst du nämlich jeden Pixel mit jedem vergleichen. Dies ist sehr zeitintensiv, angenommen du hast einen ausschnitt von 25*100 Pixel auf einem Gesamtbild von 800*600, dann musst du 2500 Pixel mit 480000 Pixel vergleichen. Wenn man jedoch bedenkt, dass das kleiner Bild nicht herraus ragen kann, dann sind es nurnoch 387500 ( 775 * 500 ) Pixel die verglichen werden müssen. Also kommst du im schlechtesten Fall, wenn z.B. der Ausschnitt nicht vorhanden ist auf 968750000 Vergleiche. Und wenn man dann noch die Geschwindigkeit von Canvas.Pixels[x, y] bedenkt ... nunja

Und wenn du jetzt noch aus mehreren Bildern dieses eine mit diesem einen Ausschnitt finden sollst, na dann Nacht Mattes xD

[omata]

Zitat von Desmulator:

Und wenn man dann noch die Geschwindigkeit von Canvas.Pixels[x, y] bedenkt ... nunja

Das man ja nicht verwendet, weil man ja Scanline benutzt.

[blackfin]

schneller dürfte es gehen, wenn man im Ausschluss-Verfahren arbeitet:
Im Sub-Bild die Farbe des ersten Pixels auslesen und den ersten Pixel mit der Farbe im grossen Bild finden, wenn diese zutrifft, auf den zweiten Pixel prüfen, wenn dieser nicht zutrifft, weitergehen. So kann man anhand der Bild-Dimensionen des kleinen Bildes und der gefundenen X-Y-Koordinaten schon ziemlich viele aussschliessen, die man gar nicht prüfen muss.

Eine andere, theoretische Möglichkeit wäre es vielleicht, eine Art "Quad-Tree" als Farb-Durchschnitt zu erzeugen (beide Bilder in Blöcke unterteilen und von diesen den Farb-Durchschnitt speichern, dann im grossen Bild dort anfangen, wo ein Block am ehesten dem Durchschnitt entspricht und sich dann an die Kanten herantasten)

[Medium]

Ein klassischer Fall für die Kreuzkorrelation. (Englisch, weil die Deutsche Variante nicht viel her gibt.)

[AbesCid]

Vielen Dank für die schnellen Antworten.
Leider habe ich noch nicht viel Ahnung von dem was ihr dort beredet
Aber das wird sich sicher bald ändern
Nun gut, anscheinend ist das alles viel zu kompliziert.

Nur zu Info:
Die Originalgröße des "größeren" Bildes ist 70px × 85px (laut Firefox)
und die Größe des Ausschnittes ist ein 10px × 10px kleines Bild.

Also müsste ich rein theoretisch 60 x 75 Pixel vergleichen (4500)
Hört sich doch schonmal nicht viel an oder? Aber leider habe ich 15840 Bilder, die ich im "schlimmsten" Fall mit dem Ausschnitt vergleichen muss.

[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