Bildausschnitt mit Bild vergleichen

[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?