Dotaz: Jak najit pozici obrazku v screenshotu

[Gilhad]

Mam program v pythonu, ktery sejme screenshot. Ted potrebuju v tom screenshotu najit souradnice obrazku (nebo zjistit, ze tam neni).

Obrazek byl vyriznut z jineho screenshotu, takze staci hledat na presnou shodu.

Samozrejme se da zacit prochazet screenshot po souradnicich a proste to brutal-force zkouset, ale to trva celkem dlouho, tak se ptam, jestli nekdo neco chytrejsiho uz nenapsal (nejlepe jako knihovnu pro python)

Odpovědi

[Gilhad]

Jeste poznamka, jde o bitmapy, obrazky jsou generovane, takze skutecne lze spolehlive testovat rovnost.

[l4m4]

Normálně se hledá maximum korelace, což lze pomocí FFT a s numpy by to asi ani nebylo tak těžké, ale zde pořád tak trochu kanón na vrabce.

[tyf]

Neni to spis maximum konvoluce? Pokud jo, pak fft netreba a staci dvojity for. A pokud hleda presnou shodu, muze si dokonce hodnotu maxima predem spocitat.

[l4m4]

Konvoluce: Ne, korelace. Rozdíl mezi konvolucí a korelací si najdeš i na Wikipedii. Z hlediska výpočetní složitosti jsou ekvivalentní (liší se obrácením kernelu), takže nerozumím, co se snažíš řešit.

Stačí dvojítý for: Ne, nestačí, protože to se tím zvedne algoritmická složitost z O(N log N) na O(MN), kde N a M jsou velikosti celého screenshotu a hledaného vzoru (předp. M < N), takže je to příšerně nechutně tragicky kolosálně pomalé.

Předem spočítat: WTF? Co spočítat? Nalezení maxima, když už mám spočtenu korelaci, je triviální O(N) operace, ta se vůbec neřeší.

[tyf]

Nojo, termitologie. Zmatlo me mathworksove conv2/filter2 spojene s mou vrelou nenavisti ke statistice a tamni kovarianci a korelaci.

Algoritmicka narocnost by me netrapila. V nejblizsi spoustu let tohle pro realne screenshoty urcite nebude prusvih. Zato mivam problemy, ze mi algoritmy lezou z pameti a swapovani to zabije. Odhaduju, ze FFT nejde pocitat v uint8.

Proc predem spocitat hodnotu maxima? Je to jenom navrh, jak nejenom najit argmax, ale i rozhodnout, jestli je vubec vzor pritomen.

Ale mam podezreni, ze pro presnou shodu bude lepsi ten retezcovy algoritmus.

[l4m4]

V nejblizsi spoustu let tohle pro realne screenshoty urcite nebude prusvih.

Ty akorát tak provokuješ, abychom se tu nenudili, co? V nejbližší spoustu let to pro reálné screenshoty znamená trvání hledání v minutách, pro větší monitor a screenshot i v desítkách minut. Na rozdíl od použití FFT, se kterým to v náročnějších případech mohou být jednotky sekund.

Zato bych prosil vysvětlit, jak by ses dokázal dostat s potřebnou pamětí přes 100MB, což je dnes zlomek operační paměti, i při výpočtu s FFT v double. Máš monitor s rozlišením 10000x10000?

[HrabalVojta]

http://en.wikipedia.org/wiki/String_searching_algorithm a nebo http://en.wikipedia.org/wiki/Fuzzy_string_searching

[l4m4]

Při přesné shodě bude Boyer-Moore výborný (aplikovaný po řádcích), ale fuzzy algoritmy pro stringy nejsou vhodné pro obrázky.

[vasek]

Boyer-Moore není vhodný pro binární data. Tady bych použil KMP, ten by měl být o něco rychlejší.

[l4m4]

To bych takhle kategoricky rozhodně neřekl, (ne)shody lze snadno hledat v každém RGB kanálu zvlášť. Naopak unicodový text má dneska buď příliš velkou abecedu (UCS-32) nebo je zamořen velkým množstvím identických bajtů a jejich sekvencí (UTF-8).