image - vocale - Confronto immagini-algoritmo veloce




riconoscimento facciale c++ (6)

Come ha sottolineato Cartman, è possibile utilizzare qualsiasi tipo di valore hash per trovare duplicati esatti.

Un punto di partenza per trovare immagini ravvicinate potrebbe essere here . Questo è uno strumento utilizzato dalle aziende CG per verificare se le immagini rinnovate mostrano ancora essenzialmente la stessa scena.

Sto cercando di creare una tabella di base delle immagini e quindi confrontare qualsiasi nuova immagine con quella per determinare se la nuova immagine è un duplicato esatto (o vicino) della base.

Ad esempio: se si desidera ridurre l'archiviazione della stessa immagine per centinaia di volte, è possibile memorizzarne una copia e fornire collegamenti di riferimento. Quando viene inserita una nuova immagine, vuoi confrontarla con un'immagine esistente per assicurarti che non sia un duplicato ... idee?

Una mia idea era quella di ridurre a una piccola miniatura e quindi selezionare casualmente 100 posizioni pixel e confrontare.


Credo che ridurre la dimensione dell'immagine a una dimensione quasi icona, ad esempio 48x48, quindi convertire in scala di grigi, quindi la differenza tra i pixel, o Delta, dovrebbe funzionare bene. Poiché stiamo confrontando il cambiamento nel colore dei pixel, piuttosto che il colore effettivo dei pixel, non importa se l'immagine è leggermente più chiara o più scura. Grandi cambiamenti contano poiché i pixel che diventano troppo chiari / scuri andranno persi. Puoi applicarlo su una riga, o quante ne vuoi, per aumentare la precisione. Al massimo avresti 47x47 = 2,209 sottrazioni da fare per formare una chiave paragonabile.


Ho un'idea, che può funzionare e molto probabilmente è molto veloce. Puoi sottocampionare un'immagine per dire risoluzione 80x60 o comparabile e convertirla in scala di grigi (dopo il sottocampionamento sarà più veloce). Elabora entrambe le immagini che vuoi confrontare. Quindi esegui la somma normalizzata delle differenze quadratiche tra due immagini (l'immagine della query e ciascuna dal db), o anche la migliore correlazione incrociata normalizzata, che dà una risposta più vicina a 1, se entrambe le immagini sono simili. Quindi se le immagini sono simili puoi procedere a tecniche più sofisticate per verificare che siano le stesse immagini. Ovviamente questo algoritmo è lineare in termini di numero di immagini nel database, quindi anche se sarà molto veloce fino a 10000 immagini al secondo sull'hardware moderno. Se hai bisogno di invarianza alla rotazione, per questa piccola immagine si può calcolare una sfumatura dominante, e quindi l'intero sistema di coordinate può essere ruotato in direzione canonica, sebbene questo sia più lento. E no, non c'è invarianza di scala qui.

Se si desidera qualcosa di più generale o l'utilizzo di grandi database (milioni di immagini), è necessario esaminare la teoria del recupero di immagini (un sacco di documenti è apparso negli ultimi 5 anni). Ci sono alcuni suggerimenti in altre risposte. Ma potrebbe essere eccessivo e l'approccio dell'istogramma di suggerimento farà il suo lavoro. Anche se penserei che la combinazione di molti approcci rapidi diversi sarà ancora meglio.


Il metodo migliore che conosco è usare un Hash percettivo. Sembra che ci sia una buona implementazione open source di un simile hash disponibile su:

http://phash.org/

L'idea principale è che ogni immagine sia ridotta a un piccolo codice hash o "impronta digitale" identificando le caratteristiche salienti nel file immagine originale e eseguendo una rappresentazione compatta di tali caratteristiche (piuttosto che l'hashing dei dati dell'immagine direttamente). Ciò significa che il tasso di falsi positivi è molto ridotto rispetto a un approccio semplicistico, come la riduzione delle immagini fino a un'immagine di dimensioni minuscole e il confronto delle impronte digitali.

phash offre diversi tipi di hash e può essere utilizzato per immagini, audio o video.


Se si dispone di un numero elevato di immagini, esaminare un filtro Bloom , che utilizza più hash per un risultato probablistico ma efficiente. Se il numero di immagini non è enorme, dovrebbe essere sufficiente un hash crittografico come md5.


Questo post è stato il punto di partenza della mia soluzione, un sacco di buone idee qui, quindi ho pensato di condividere i miei risultati. L'intuizione principale è che ho trovato un modo per aggirare la lentezza della corrispondenza delle immagini basata su punti chiave sfruttando la velocità di phash.

Per la soluzione generale, è meglio utilizzare diverse strategie. Ogni algoritmo è più adatto per determinati tipi di trasformazioni di immagine e puoi trarne vantaggio.

In cima, gli algoritmi più veloci; in basso il più lento (anche se più preciso). È possibile saltare quelli lenti se si trova una buona corrispondenza al livello più veloce.

  • basato su file hash (md5, sha1, ecc.) per duplicati esatti
  • hashing percettivo (phash) per immagini riscalate
  • basato sulle funzionalità (SIFT) per le immagini modificate

Sto ottenendo ottimi risultati con phash. La precisione è buona per le immagini riscalate. Non va bene per le immagini (percettivamente) modificate (ritagliate, ruotate, specchiate, ecc.). Per gestire la velocità di hashing, dobbiamo utilizzare una cache del disco / database per mantenere gli hash per il pagliaio.

La cosa veramente bella di Phash è che una volta creato il tuo database hash (che per me è di circa 1000 immagini / sec), le ricerche possono essere molto, molto veloci, in particolare quando puoi tenere in memoria l'intero database hash. Questo è abbastanza pratico dal momento che un hash è solo 8 byte.

Ad esempio, se si dispone di 1 milione di immagini richiederebbe un array di 1 milione di valori hash a 64 bit (8 MB). Su alcune CPU questo si adatta alla cache L2 / L3! Nell'uso pratico ho visto un confronto corei7 a oltre 1 Giga-hamm / sec, è solo una questione di larghezza di banda della memoria della CPU. Un database di 1 miliardi di immagini è pratico su una CPU a 64 bit (8 GB di RAM necessari) e le ricerche non superano 1 secondo!

Per le immagini modificate / ritagliate sembrerebbe una caratteristica invariante di trasformazione / rilevatore di punti chiave come SIFT è la strada da percorrere. SIFT produrrà buoni punti chiave che rileveranno il ritaglio / ruota / specchio ecc. Tuttavia, il confronto del descrittore è molto lento rispetto alla distanza di hamming utilizzata da phash. Questo è un limite importante. Ci sono parecchie cose da fare, dato che ci sono un massimo descrittore IxJxK paragonabile alla ricerca di un'immagine (I = num immagini di pagliaio, J = punti chiave di destinazione per immagine di pagliaio, K = punti chiave di destinazione per immagine ago).

Per aggirare il problema della velocità, ho provato a utilizzare phash attorno a ciascun punto chiave trovato, utilizzando la dimensione / raggio della funzione per determinare il sub-rettangolo. Il trucco per farlo funzionare bene, è quello di aumentare / ridurre il raggio per generare diversi livelli sub-rettali (sull'immagine dell'ago). In genere il primo livello (non graduato) corrisponderà, tuttavia spesso ne occorrono altri. Non sono sicuro al 100% sul perché funzioni, ma posso immaginare che abiliti funzioni troppo piccole per far funzionare phash (phash ridimensiona le immagini fino a 32x32).

Un altro problema è che SIFT non distribuirà i punti chiave in modo ottimale. Se c'è una sezione dell'immagine con molti bordi, i punti chiave si raggruppano e non ne ottieni in un'altra area. Sto usando GridAdaptedFeatureDetector in OpenCV per migliorare la distribuzione. Non sono sicuro quale sia la dimensione della griglia migliore, sto usando una piccola griglia (1x3 o 3x1 a seconda dell'orientamento dell'immagine).

Probabilmente vuoi ridimensionare tutte le immagini (e l'ago) del pagliaio in una dimensione più piccola prima del rilevamento delle funzioni (io uso 210px sulla dimensione massima). Ciò ridurrà il rumore nell'immagine (sempre un problema per gli algoritmi di visione artificiale), inoltre focalizzerà il rivelatore su caratteristiche più importanti.

Per le immagini di persone, potresti provare a rilevare il volto e utilizzarlo per determinare la dimensione dell'immagine in scala e la dimensione della griglia (ad esempio, la faccia più grande ridimensionata per essere 100 px). Il rilevatore di feature tiene conto di più livelli di scala (usando le piramidi) ma c'è una limitazione al numero di livelli che userà (questo è ovviamente sintonizzabile).

Il rilevatore di punti chiave sta probabilmente funzionando meglio quando restituisce meno del numero di funzioni che si desidera. Ad esempio, se chiedi 400 e ottieni 300 indietro, va bene. Se ne ricevi 400 ogni volta, probabilmente alcune buone caratteristiche dovevano essere tralasciate.

L'immagine dell'ago può avere meno punti chiave delle immagini del pagliaio e ottenere comunque buoni risultati. L'aggiunta di più non comporta necessariamente enormi guadagni, ad esempio con J = 400 e K = 40 il mio tasso di successo è di circa il 92%. Con J = 400 e K = 400 il tasso di successo raggiunge solo il 96%.

Possiamo sfruttare l'estrema velocità della funzione hamming per risolvere il ridimensionamento, la rotazione, il mirroring, ecc. È possibile utilizzare una tecnica a più passaggi. In ogni iterazione, trasforma i sub-rettangoli, re-hash ed esegui di nuovo la funzione di ricerca.





computer-vision