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.