18/06/21

Jak funguje reverse image search... nejspíš

Jak funguje "reverse image search" neboli vyhledávání podle obrázku ve vyhledávačích jako Google nebo TinEye můžeme jen hádat. Pravděpodobně vychází z dostupných veřejných technologií. TinEye byl první známější vyhledávač obrázků s touto funkcí a byl spuštěn v roce 2008. Google vyhledávání ubrázků spustil v roce 2001, avšak funkci vyhledávání podle obrázku přidal až v roce 2011, shodou okolností se v této době stal trendem thread v programovací části redditu, kde diskutující řešili, jak nejspíš TinEye funguje. Toho si autoři TE všimli a jejich odpověď byla "TinEye is Magic!". Abychom se dostali k jádru tohoto kouzla a jak nejspíš podobné vyhledávače, ale i technologie na to napojené fungují, musíme si ujasnit pár základních pojmů. Jako co je to bit, byte, integer a hash. Předpokládám že to víceméně všichni znají, ale pro připomenutí... (experti mohou přeskočit)


Bit Byte

Bit je 1 nebo 0 a takto se vyjadřují čísla v binární(dvojkové) soustavě. Byte (bajt) je 8 bitů, např. 10011101, což je v desítkové soustavě číslo 157 a v hexadecimální(šetnáctkové) je to 9D (9 x 16 + 13 = 157 (13 je protože hex soustava počítá 0-9 a pak ABCDEF místo 10 – 15, takže D je 13). Počítačová paměť umí uložit jako nejmenší fragment jeden byte(8 bitů).

Integer

Integer znamená latinsky celý a je to tedy pouze celé číslo a využívá se při programování. "signed a unsigned" znamená že je možné číslo vyjádřit se znaménkem - a nebo bez něj. Budeme se zabývat jen tím s kladnou hodnotou. Bežně užívaný nezkrácený integer Int32 je 32 bitů dlouhý kus v paměti, tj. 4 bajty a jeho maximální hodnota je tak 32 jedniček v binárním kodu. Nebo FFFFFFFF v hexadec. soustavě a 4 294 967 295 v decimální.

(Jen pro zajímavost uvedu, že YouTube muselo poprvé kvuli korejské písničce Gangnam Style přejít ze signed 32 inteegeru počítání views na 64bit z důvodu že skladba mířila k přesažení max hodnoty signed int32 tj. 2147483647 a při přetečení by to začalo počítat od minimální hodnoty -2147483648)


Hash

Hash je prakticky integer o různých délkách bitů 64, 128, 256... Získává se ze vstupních dat pomocí nějaké funkce a výstupem je číslo. Nejčastejší užití je při šifrování internetové komunikace HTTPS, nebo při komunikaci s modemem přes WiFi. Jsou různé druhy a užití, nemá prakticky žádné hranice. Některé hashe jsou reverzní, tj. že z jeho hodnoty lze dopočítat původní data a z některých nikoliv, takové slouží například k ukládání hesel do databáze aby heslo na přihlášení na web nebylo uloženo jako prostý text. Když se uživatel někam přihlašuje tak je heslo převedeno na hash a na serveru se porovnávají hashe aniž by šlo zjistit co je původní slovo. Teoreticky se může stát, že dvě rozdílá vstupní data mají hash stejný, ale nevím zda tomu může být i u hesel, nejspíš se počítá s pravděpodobností jako u klíčů a zámků, že existují duplikáty ale není pravděpodobné že se potkají se správným zámkem.

Image Search

(Tím jsem se dostal k samotnému hledání. Dále popíšu základ a spekulaci jak to nejspíš může a nemusí u známých vyhledávačů fungovat v principu)

Nahrajete obrázek na Google nebo TinEye a vytvoří se z něj na straně serveru takzvaný "perceptual hash" (narozdíl od výpočtu hashe hesla, výpočet hashe obrázku probíhá u nich na serveru, aby nikdo nevěděl jak hash počítají). Takže v tomto případě zde nemusí být angažována žádná AI, ani machine learning. Perceptual hash je vlastně orientační hash jak daný obrázek vypadá pro lidské oko. Hash lze vytvořit více způsoby. Já popíšu ten, se kterým jsem dělal pokusy, tj. Difference hash.

Jak už vám asi došlo, vyhledávání obrázků probíhá porovnáváním těchto hashů. Perceptual hash musí být odolný na jemné změny v obrázku jako změna barev, ořez, vodoznak a nebo rozdílný poměr stran. Nemůžou se zde využít již existující typy využité při šifrování hesel a připojení, protože my potřebujeme aby podobné obrázky měly velmi podobné hashe. U šifrovacích hashů by tak stačilo zmenit jediný pixel a vyšlo by uplně jiné číslo. 

Zmiňovaný difference hast vypočteme tak, že si to celé zjednodušíme tím, že zdrojový RGB obrázek převedeme do černobílé barvy, tím se docílí odstranění rozdílů v barevné saturaci a zároveň obsáhneme i černobílé verze obrázku a rychleji se počítají následující výpočty, protože místo tří barevných kanálu máme jen jeden. Dále se v mé metodě obrázek zmenší na 8x8 pixelů. Tím nám vznikne mžížka s 64 pixely v odstínech šedé. Jeden pixel má v paměti velikost 1 byte a může mít hodnotu 0 – 255 (0 = černá, 255 = bílá).

V mé metodě toto 2D 8x8 pole převedu na 1D pole o 64 hodnotách. Takže máme 64 bytové(bajtové) pole, to je 512 bitů. Nám to ale stačí převést na 64 bitů aby obrázek vyjadřoval jeden 64 bitový integer. Zárověň nás nezajímá přímá hodnota pixelů v obrázku, protože ta se může lišit pokud například někdo zmenil jas nebo kontrast. Náš zajímají rozdíly mezi sousedy (proto difference hash). Takže si prakticky projdeme to 1D pole s 64 byt hodnotami a vždy porovnáváme dva sousedící byty. Metody se můžou lišit ale při vytváření databáze a následném hledání je potrebné použít vždy stejné postupy a to i v případě zmenšování (a vlastně i tím resamplování) obrázku a konvertování stejně tak, aby v případě zmeny techniky přesamplování (cubic, nearest, bilinear) nedošlo k jiné miniatuře a jiným poměrům mezi pixely a následné nekompatibilitě s již vytvořenou databází.


Příklad

V příkladu na následujícím obrázku máme obrázek A, 4K screenshot z nedávno remasterované verze Terminátor 2.  B je HD Bluray neremasterovaná verze. C je lehce jinak oříznutá verze B ale v 240p s artefakty od komprese a logem televize. D nemusím vysvětlovat. Obrázek se transformuje na poměr stran 1:1, což probehne současně se zmenšením na 8x8 pixelů a následně se obrázek převede do černobílé. 

Hash získáme z černobílé miniatury tak, že porovnáváme hodnoty sousedních bytů(pixelů) 1 – 64 a nakonec 64 s 1. Například pokud je byte[1] > byte[2] zapíše se do výsledku 0 a pokud byte[1] < byte[2] zapíše se 1. Tímto nám vznikne binární číslo o 64 bitech 1 a 0, které se pro zkrácení a čitelnost zobrazuje v hexa decimálním formátu. Hash screenshotu A je tak v binárním kodu 0001 1001 1101 1001 1101 1101 0001 1101 0001 1001 0001 1001 0001 1101 000 11101 a v hexadecimálním 19d9dd1d19191d1d

Tento kód je uložen v nějaké databízi spolu s odkazem na daný obrázek a pak už je jen na vyhledávači zda si pro další účely nechá i originál, ale není to potřeba. Takže informace o podobě jednoho obrázku zabírá pouhých 8 bytů(bajtů). Porovnávání se dělá porovnáním binárních hashů za pomocí Hammingovy vzdálenosti, prakticky pouhý součet rozdílných bitů. 

Na obrázku tak lze vidět že pokud bereme A jako startovní obrázek v databázi (např. v Google), tak B se liší o 4 bity, lehce oříznuté C s kompresí a malým tozlišením se liší o 6 bitů, ale jen o pouhé 2 od obrázku B (modře) a D je rozdílný obrázek a tam se liší 35 ze 64 bitů. Hodnota kde se rozdíl pohybuje kolem 50% je vlastně absolutně nestejný obrázek, protože kdyby se blížila 100% tak by nám vycházelo že se jedná o invertované barvy téhož obrázku. Dle článků které jsem četl se dají obrázky považovat za podobné cca do hodnoty 10 rozdílných bitů ze 64 což je cca 15%.


Další užití a závěr

Terminátor 2 má 137 minut, odečteme titulky 7 min. 130m x 60s je 7800 sekund a při 24 snímcích za sekundu dostaneme 187200 snímků, ze kterých se skládá film. 187200 x 8 bytů = 1462,5 kb hash informací na celý film. Pokud bychom hashovali jen každý druhý frame jsme na 731 kb a optimalizovat by se dalo dál, jako třeba mazat hashe kde není rozdíl vetší než 3 bity. Věřím že bychom se tak dostali až na nějakých 25-50 kb. A teď jsem popsal jak nejspíš funguje Content ID na YouTube. Máte hash tabulku o velikosti pár kb a jste z ní schopni poznat celý dvouhodinový film bez AI.

Závěrem bych chtěl dodat, že když jsem si kolem této problematiky hledal materiály, byl jsem překvapen, jak je to v principu jednoduché. Samozřejmě se v praxi používají i složitější hashovací funkce, ta mnou uvedená je dle testů asi nejblbější. V odkaze naleznete porovnání s dalšími hashovacími funkcemi.

A zde jako zajímavost je článek jak někdo používá AI na reverzní výpočet obličejů z 256 bit (16x16) hashe.


10 comments:

  1. Vyhledavani pomoci obrazku na Google pouzivam velmi casto a je to celkem spolehlive. Obcas to vyhazuje i nesmysly nebo je dobre hledat jen podle popisku...By me zajimalo jestli na stejnem principu funfuje take Shazam, ktery pohotove rozpoznava prehravanou skladbu...

    ReplyDelete
    Replies
    1. Google dost ovlivňuje a customizuje výsledky. Údajně nejlepší vyhledávač je to TinEye protože to rozpozná i ořezaný a pozměněný obrázky, ale oni nemají tak velkou databázi jak google. Stejně tak je údajně velmi dobrý Yandex, ten výsledky asi nefiltruje, ale mají ten index mimo rusko dost omezenej. Nedávno tu službu provozoval i seznam, ale už to vypnuli. Jinak jak funguje shazam rozebírají tady, ale taky jen hádá https://www.youtube.com/watch?v=RRsq9apr5QY

      Delete
    2. tady ten Shazam popisuje lépe, takže to funguje víceméně jak ty obrázky. Má to vytvořenou hash tabulku a s tou to pak porovnává https://www.youtube.com/watch?v=kMNSAhsyiDg

      Delete
  2. ... ako povedal klasik .. ked google hlada obrazok, tak nerozumie tomu co vidi, ze ide napriklad o psa ale ide o analyzu podobnosti pixelov, morfologia, obrazove vzorce.
    .. tento clanok ma teda s hrami vela spolocne, lebo aj v hrach by sme chceli aby AI videla a identifikovala objekt ako my .. ma to 4 nohy, ktorymi beha po zemi, ma to chvost, srst, ma to specificke drzanie tela .. je to pes /good luck pre AI od seba odlisit psa, macku, zajaca, ak su morfolog. kurva podobne/ .. to iste, ked AI vidi rozbite okno .. policajt v GTA atd. atd.

    ReplyDelete
    Replies
    1. To co popisuješ je Convolutional Neural Network CNN. Rozloží to obrázek na grid a ten na další, až vznikne spousta malých vzorů. https://qjjnh3a9hpo1nukrg1fwoh71-wpengine.netdna-ssl.com/wp-content/uploads/2019/07/1_ZD3ewOfpfsMAjhp4MYFnog-edited.jpg
      Unity už má u té své Machine Learning Agents i funkci Vision. Říkal jsem si, že bych do hry dal roboty co mají vidění 128x128 pixelů a ať se tím realisticky řídí. https://youtu.be/ZV12uozR36k?t=634

      Delete
    2. ... ano, kto si mysli, ze sa nemame kde pohnut s PS2 gameplay tak sa myli .. dnesna GTA vie ze drzim zbran v ruke, nie preto, ze ju AI vidi ale preto, ze svieti flag v kode, ze ju mam vytiahnutu .. to je prdlacka.

      Delete
    3. Na druhou stranu AI se může skládat z více částí a pakticky jedna část nahradí ten flag, stejně jako ve videu on vidí prasata jako růžový čtverce. Četl sjem o tom něco a někdo tvrdí proč vlastně dopočítávat informaci, kterou už mám. Ten výkon se pak dá věnovat dalšícm věcem, jako třeba vlezu do kanceláře a zaterasim dveře stolem... situace z Half Life 2 a nebo real life v české politice. Pak bych chtěl aby AI v nějakým behavior tree vybrala ukony co provede... rozbije okno, vyseká dveře sekerou, vykopne je, odejde a počká za rohem... Všechno tohle mám v plánu do moji hry, ale jestli se k ní někdy vubec dostanu. Každopádně tohle jsou věci co naprogramuješ za týden v prototypu a pak odladíš...

      Delete
    4. ... pri dobrej AI /dobra AI je siroky pojem ale znamena hlavne herne zabavna pre dospeleho hraca, kt. nie je dusevne mrtvy a teda chce viac ako len IF-THAN pac-man AI/ ma zacnu aj hry opat bavit.

      Delete
  3. Trochu offtopic, ale souvisí to s tím Shazam resp. detekcí audia. Určitě jste si někdy stáhli nějakou hudbu v MP3 a dumali nad tím jak moc je to zkomprimováno. Kdysi velmi dávno (cca 1999) jsem dělal na hifi sluchátkách porovnávačky originálního audio CD a zkonvertovaných MP3. Byla to doba kdy byla MP3 128 kbps v tisku vydávána za audio CD kvalitu, ale byl to blábol. Tehdy jsem měl mladé zdravé uši a vyšlo mi že 128 je zkreslené a neposlouchatelné, 160 už bylo řádově lepší ale furt občas špatně, no a u 192 kbps jsem už poprvé nerozeznal audio CD od MP3, bezpečně 224 kbps už jednoznačně overkill a nemožnost rozeznat absolutně nic. Z toho jasně vyplývá že pokud máte MP3 320 kbps jste overkill a za vodou. Jak ale dokázat že to není upscalovaná 320-tka např. ze 128-čky? (Proč by to někdo dělal? No protože internet je plný šmejdů co v rámci exhibování jsou schopní čehokoliv a když je možnost někde ukradnout zdarma 128 kbps stream...). Dokážeme to SPEKTRÁLNÍ ANALÝZOU programem Spek:

    https://www.deephouseamsterdam.com/this-handy-tool-checks-the-real-quality-of-your-music-files/
    http://spek.cc/

    Pokud vám zvuk šahá do 20 kHz je to 320, pokud 16 je to oněch pro mě minimálních 192, neakceptovatelná 128čka je pak 12 kHz...

    ReplyDelete
    Replies
    1. ... ano, za starych cias som sa snazil brat iba 192-320 kilove mp3, 128 bolo zalostne malo aj na lacnych stuploch do ucha za 7 euro, prislo mi to ako 8 bitove 22Khz amiga sample .. problem bol s upscale smejdom.

      Delete

**** pre vloženie hypertextového odkazu do komentára použi CSS kód: hyperlink ****