Keressen a képeket részlet szerint, savepearlharbor
Beszédében Alexander Krainov elmondta, hogy a Yandex.Kartinki fürtözött duplikált képeket. Más szóval, az ismétlődő képeket választottuk és szűrtük. Ahol az alapötlet a vázlatos képek kiválasztása a DoG szűrőn keresztül. majd keresse meg a kulcspontokat és szerezzen leírást.
A másolatok csoportosítása csökkenti a leíró karakterek lekérdezését. Ez a legfontosabb pontok "digitális formátuma" a cikkből A duplikátumok csoportosítása a képkeresésben.
De szeretnék egy kicsit többet megtudni arról, hogy milyen descriptorok vannak, és hogyan kell keresni őket.
leírások
A legfontosabb pontok olyan pontok, amelyek ideális esetben nem változnak a kép módosításakor vagy módosításakor.
A jellemzők általában a jellemzők konvolúciója és a kulcsfontosságú pontok ábrázolása egy olyan formában, amely elérhető a véletlenszerű ellenőrzésre.
A kulcsfontosságú pontok, azok leírása és a véletlenszerű ellenőrzési módszerek hatékony kiválasztásának keresése még mindig napirenden van.
De el kell indítanunk valahol, ezért forduljunk az OpenCV könyvtárához.
Az első dolog, ami elkapja a szemed, a SURF leírók.
Ki ígér rendkívüli pontosságot. Ami a tesztek után megerősítésre kerül.
De van néhány árnyalat.
A SURF leíró a 128 (vagy 64) számról egy kulcspontra. A véletlen próbát a legközelebbi pont (vagy akár kettő) keresésével végezzük. És minél közelebb van a pont, annál jobb.
Kiderül, hogy 1000 kulcsponttal rendelkező képen 128 000 lebegőpontos számra van szükség.
Ráadásul a pontok felismerése meglehetősen bonyolult művelet, és jelentős időt igényel. Ez nem teszi lehetővé az algoritmus hatékony használatát kis eszközökön. Ezenkívül az algoritmus maga is zárt és szabadalmaztatott (az USA-ban).
Miután megismerkedtem a SIFT és a SURF programmal, a megvalósításban valami egyszerűt akartam, miközben kis szerverre vagy eszközre is alkalmazhattam.
Perceptuális hash
És észlelő vagy észlelő hashokat találtak.
A probléma az, hogy ha a kép kissé megváltozik, a hash szintén jelentéktelen mértékben változott.
A véletlen próbát úgy végezzük, hogy számba vesszük a különbözõ pozíciók számát a két hash között. Ie Hamming távolságot számolva. És minél kisebb, annál kisebb a különböző elemek, annál nagyobb a véletlen.
Ez a módszer arra szolgál, hogy teljes vagy részleges duplikált képeket keres. Ie ha a kép formátumában vagy a tartalomban bekövetkező interferenciákban jelentős változás következik be, akkor lehetetlen ellenőrizni a mérkőzést, mivel a hasok jelentősen eltérnek egymástól.
Más szavakkal, az észlelő hashok nem alkalmasak semidoublet keresésre.
Ennek alapján kísérletet tettünk arra, hogy kombináljuk a SURF leíróit és az észlelő hashokat, hogy megoldjuk a fuzzy félhullámok megtalálásának problémáját.
A módszer a kulcsfontosságú pontok klaszterezésén alapul, oly módon, hogy a klaszterközpontok egybeesnek az eredeti és az összeomlott képekkel. Aztán a kulcspont körüli képfájlt kivontuk, és észlelő hashot kaptunk. Ennek eredményeképpen egy kép körülbelül 200 vágott lécet és hashajtását eredményezett.
Ennek a módszernek két és fél jelentős hátránya van:
1. A véletlen ellenőrzés alacsony sebessége nagy mennyiségű hashúzással. 1 millió takarmányt keresett 20 másodperc
2. a kulcspontok megszerzésének alacsony sebessége
3. Alacsony pontosság, sok hamis pozitívum, nagy követelmény a célállomásra, nem alkalmas minden képre, előminősítésre van szükség stb.
Az az elképzelés, hogy az lenne a kép generál egy bizonyos számú nyomatok (ujjlenyomat), ami egyszerűen össze egymással, lenyűgözött.
Ezért úgy döntöttek, hogy megoldást találnak ezekre a problémákra.
Lassú mintavételi arány
A Hamming-távolság megtalálásának és kiszámításának bonyolultsága egy nagy adathalmazon független probléma, és független megközelítést igényel.
Némi kutatás után kiderült, hogy számos megoldás létezik ehhez a problémához.
A leghatékonyabb algoritmust, a HEngine-t választották és valósították meg. ami lehetővé tette
60-szor, hogy gyorsítsák fel a kiválasztást az adatbázisból.
SURF és kulcspontok
Mivel mi már dolgozik bináris hash vagy az ujjlenyomatok és a megfelelő hinni Hamming távolság, ez furcsa, hogy az ilyen gép, mint a felszíni és szükséges lenne, hogy más módszerek egyre legfontosabb pontok és a leírásokat.
Általában az OpenCV kétféle leíró típust tartalmaz:
- Lebegőpontos leíró
- És bináris leírók
Itt a bináris descriptorok, mint senki más, nem alkalmasak a mi problémánkra, mert a Hamming távolságot is használják a mérkőzések ellenőrzésére.
ORB: a SIFT vagy SURF hatékony alternatívája
OpenCV már egy kiváló alternatívája a surf, ami nem elég, hogy egy nyílt és engedélyezés nélkül korlátozásokat, így még könnyebb és gyorsabb. [1]
Az ORB egy orientált FAST és elforgatott BRIEF - egy továbbfejlesztett verzió és a FAST kulcspont-detektor és a BRIEF bináris descriptor kombinációja.
Az ORB-nek van egy jelentős árnyalata számunkra - a leírók mérete 32 bájt / pont.
A véletlen teszt a Hamming-távolságok összege a leíró minden egyes bájtja esetében (az első az első, a második a második, stb.
A mi a probléma azt jelenti, hogy egy pontot ad egy értéket, majd kiderül 32, amelyek szükségesek is összefoglalni a megfelelő index (az első az első, a második a második, és így tovább), a cél adatbázisban.
Mivel a hash egy 64 bites szám, az előírt 32 bájtos leíró zsugorodik 8 bájt, és nem sokat veszít a pontosság.
Egyes tesztek után úgy döntöttek, hogy megpróbálják kipróbálni ezt a 32 bájtot, hogy 16 × 16 bites mátrixot képviseljenek. És ezt követően átadja ezt a mátrixot az észlelő hash PHash segítségével. Az eredmény csak 64 bites szám volt.
Most a koncepció teljes leírására jutunk.
Hogyan működik az indexelés?
1. Szerezd meg az ORB kulcsfontosságú pontokat és leírókat, válassza ki a szükséges pontok számát a képen.
2. Az eredményül kapott 32 bájtos leírók 16 × 16 bites mátrixként vannak ábrázolva.
3. A mátrixot 64-bites számra konvertálja a PHash használatával.
4. 64 bites nyomatokat mentünk a MySQL-be.
5. Válassza ki a kívánt Hamming távolságot, és futtassa a HEngine démont, amely elvégzi a keresést.
A keresés működése
Ugyanazokat a lépéseket hajtjuk végre, mint az indexelés, csak a kért képen.
4. Kérünk a HEngine démont, amely a megadott limitben minden hashajtót visszaad.
5. Ha szükséges, szûrje ki az irreleváns eredményeket.
1. ábra Hamming távolságkorlát 7. A szürke pontok a kulcsfontosságú pontok. Zöld - egybeeső pontok. Vörös - egybeesik a standard ORB teljes brute force.
És mi a végén?
Végül számos problémát sikerült megoldani:
- megtalálja a módját, hogy gyorsan kiszámolja Hamming távolságát egy nagy adathalmazon
- megszabadulni a nagy és kellemetlen SURF-től
- növeli a kulcspontok és az ujjlenyomatok kiválasztásának sebességét
- és nem is veszítenek pontosan.
Ez lehetővé tette a képek töredékét, valamint a nagyszámítógépes erőforrások nélküli fuzzy semidoubie-t.
Tekintettel arra, hogy a beállításoktól függően az ismertetett algoritmus az ORB bináris descriptoron keresztül körülbelül 1000 darabnyi hash-ot produkál képenként.
1000 kép alapján 1 000 000 törmelék keletkezik az adatbázisban. És az adatbázisban lévő összes kép teljes keresése másfél percet vesz igénybe.
Összehasonlításképpen, a krainov-jelentésében Alexander Krainov kifejti, hogy az egymillió kép duplikátumainak keresése kb. Két percet vesz igénybe.