În discursul său, Alexander Krainov a spus cum Yandex.Kartinki a grupat imagini duplicate. Cu alte cuvinte, fotografiile duplicate au fost selectate și filtrate. În cazul în care ideea de bază a fost de a selecta imagini contur prin filtrul DoG. apoi găsiți punctele cheie și obțineți descriptorii acestora.
Clustering duplicates reduce la găsirea potrivirilor descriptorilor. Acesta este "formatul digital" al punctelor-cheie din articolul Clustering duplicates în căutarea imaginilor.
Dar aș dori să învăț ceva mai mult despre ce fel de descriptori sunt și cum să le căutați.
descriptori
Punctele cheie sunt puncte care, în mod ideal, nu ar trebui să se schimbe atunci când modificați sau modificați o imagine.
Descriptorii sunt, în general, convoluția caracteristicilor și reprezentarea punctelor-cheie într-un format care este disponibil pentru verificarea coincidenței.
Căutarea unei selecții eficiente a punctelor cheie, a descriptorilor acestora și a metodelor de verificare a coincidențelor este încă pe ordinea de zi.
Dar trebuie să începem undeva, deci hai să ne întoarcem la ajutorul bibliotecii OpenCV.
Primul lucru care vă atrage privirea este descriptorii SURF.
Cine promite precizie extraordinară. Ceea ce se confirmă după teste.
Dar există mai multe nuanțe.
Descriptorii SURF sunt vectori de la 128 (sau 64) numere la un punct-cheie. Testul de coincidență se efectuează prin căutarea celui mai apropiat punct (sau chiar doi). Și cu cât este mai aproape punctul, cu atât mai bine.
Se pare că pe o imagine cu 1.000 de puncte cheie aveți nevoie de 128.000 de numere cu virgulă mobilă.
În plus, detectarea punctelor este o operație destul de complicată și necesită un timp considerabil. Acest lucru nu permite utilizarea eficientă a acestui algoritm pe dispozitivele mici. În plus, algoritmul în sine este închis și brevetat (în SUA).
După ce am făcut cunoștință cu SIFT și SURF, am vrut ceva simplu în implementare, cu capacitatea de a aplica pe un mic server sau dispozitiv.
Permisive hashes
Și s-au găsit șuvițe perceptuale sau perceptive.
Problema este că, dacă imaginea se schimbă ușor, hașul sa schimbat și nesemnificativ.
Testul de coincidență se efectuează prin numărarea numărului de poziții diferite între cele două hași. Ie numără distanța Hamming. Cu cât este mai mică, cu atât sunt mai puține elementele diferite, cu atât este mai mare coincidența.
Această metodă este concepută pentru a căuta imagini duplicate complete sau parțiale. Ie dacă există o schimbare semnificativă a formatului imaginii sau a interferenței în conținut, este imposibil să verificați un meci, deoarece hașirile vor diferi semnificativ.
Cu alte cuvinte, hash-urile perceptive nu sunt potrivite pentru căutarea unor semidoublete.
Pe baza acestui fapt, sa încercat combinarea descriptorilor SURF și a hashesurilor perceptuale pentru a rezolva problema găsirii semidoublelor fuzzy.
Metoda se bazează pe gruparea punctelor-cheie astfel încât centrele de cluster să coincidă cu imaginea originală și cu imaginea accidentată. Apoi fragmentul imaginii din jurul punctului cheie a fost extras și a fost obținut un hash perceptual. Drept urmare, o imagine a produs aproximativ 200 de slicks decupate și hașișele lor.
Această metodă are două și jumătate neajunsuri semnificative:
1. Verificarea vitezei reduse a coincidenței pe un set mare de hashes. Căutarea unui milion de hashuri a durat 20 de secunde
2. viteza redusă de obținere a punctelor cheie
3. Precizie scăzută, o mulțime de poziții false, cerințe ridicate la baza țintă, nu este potrivit pentru toate fotografiile, necesită pre-moderare etc.
Ideea exactă că ar exista un anumit număr de amprente digitale din imagine, care ar putea fi comparate pur și simplu între ele, vor fi îmbătate.
Prin urmare, sa decis să încercăm să găsim soluții la aceste probleme.
Rată de eșantionare lentă
Complexitatea descoperirii și calculării distanței Hamming pe un set mare de date este o problemă independentă și necesită o abordare independentă.
După unele cercetări pe această temă, sa dovedit că există multe soluții la această problemă.
Cel mai eficient algoritm, numit HEngine, a fost ales și implementat. care a permis
De 60 de ori pentru a accelera selecția din baza de date.
SURF și puncte cheie
Din moment ce am fost de lucru cu hash-uri binare sau amprente, și potrivire cred Hamming distanță, este ciudat de a utiliza o astfel de mașină ca SURF și ar fi necesar să se ia în considerare alte metode de a obține punctele cheie și descriptorii.
În general, OpenCV oferă două tipuri de descriptori:
- Descriptorii punctelor plutitoare
- Și descriptorii binari
Aici, descriptorii binari ca nimeni altul nu sunt potriviți pentru problema noastră, deoarece folosesc și distanța Hamming pentru a verifica potrivirile.
ORB: o alternativă eficientă la SIFT sau SURF
OpenCV este deja la o alternativa excelenta la SURF, care nu este suficient ca un dialog deschis și fără restricții de licențiere, astfel încât, chiar ușor și mai rapid [1].
ORB este un FAST orientat și rotit BRIEF - o versiune îmbunătățită și o combinație de detector de puncte cheie FAST și descriptori binare BRIEF.
ORB are o nuanță semnificativă pentru noi - mărimea descriptorilor este de 32 octeți pe punct.
Testul de coincidență este suma distanțelor Hamming pentru fiecare octet al descriptorului (primul este comparat cu primul, al doilea cu cel de-al doilea și așa mai departe).
În problema noastră se înțelege că un punct dă o singură valoare, iar apoi se transformă 32, care sunt necesare, de asemenea, suma cu indicele corespunzător (mai întâi cu primul, al doilea al doilea, și așa mai departe), în baza de date țintă.
Deoarece hash-ul nostru are un număr de 64 de biți, avem nevoie de 32 octeți ai descriptorului pentru a stoarce în 8 octeți și să nu pierdem prea mult în precizie.
După câteva teste, sa decis încercarea acestor 32 de octeți să reprezinte o matrice de 16x16 biți. Apoi, pentru a trece această matrice prin PHash perceptiv. Rezultatul a fost doar un număr de 64 biți.
Acum ajungem la o descriere completă a conceptului.
Cum funcționează indexarea
1. Obțineți punctele cheie și descriptorii ORB, selectați numărul de puncte necesare în imagine.
2. Descriptorii de 32 de octeți care rezultă sunt reprezentați ca matrice de biți de 16x16.
3. Convertiți matricea la un număr pe 64 de biți utilizând PHash.
4. Salvam imprimate pe 64 de biți în MySQL.
5. Selectați distanța Hamming necesară și rulați daemonul HEngine, care va efectua căutarea.
Cum funcționează căutarea
Efectuăm pași identici 1 - 3 din indexare, dar numai pe imaginea solicitată.
4. Facem o cerere catre daemonul HEngine, care returneaza toate hash-urile in limita specificata.
5. Dacă este necesar, filtrați rezultatele irelevante.
Figura 1. Limita distanței Hamming 7. Punctele grele sunt punctele cheie găsite. Verde - puncte coincide. Roșu - coincide cu forța normală ORB standard.
Și în cele din urmă?
În cele din urmă, am reușit să rezolvăm câteva probleme:
- găsiți o modalitate de a calcula rapid distanța Hamming pe un set mare de date
- scapă de SURF mare și inconfortabil
- creșterea vitezei de selectare a punctelor cheie și a amprentelor digitale
- și, de asemenea, să nu piardă prea precis.
Acest lucru a permis găsirea de imagini pe fragmentul lor, precum și semidoublele fuzzy fără mari resurse de calcul.
Având în vedere că, în funcție de setări, algoritmul descris prin descriptorii binari ORB produce aproximativ 1000 de hashes pe imagine.
Pe baza a 1000 de imagini, în baza de date sunt produse 1 000 000 de hashes. Și o căutare completă a tuturor imaginilor din baza de date durează un minut și jumătate.
Pentru comparație, în raportul său krainov Alexander Krainov explică faptul că căutarea duplicatelor de 1 milion de imagini durează aproximativ două minute.