Rilevamento di immagini quasi duplicate [chiuso]

StackOverflow https://stackoverflow.com/questions/1034900

Domanda

Qual è un modo rapido per ordinare un determinato set di immagini in base alla loro somiglianza tra loro.

Al momento ho un sistema che esegue l'analisi dell'istogramma tra due immagini, ma questa è un'operazione molto costosa e sembra eccessiva.

In modo ottimale sto cercando un algoritmo che dia ad ogni immagine un punteggio (ad esempio un punteggio intero, come la media RGB) e posso semplicemente ordinare in base a quel punteggio. Punteggi identici o punteggi uno accanto all'altro sono possibili duplicati. 

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994

La media RGB per immagine fa schifo, c'è qualcosa di simile?

È stato utile?

Soluzione

Sono state fatte molte ricerche sulla ricerca di immagini e misure di somiglianza. Non è un problema facile. In generale, un singolo int non sarà sufficiente per determinare se le immagini sono molto simili. Avrai un alto tasso di falsi positivi.

Tuttavia, dal momento che sono state fatte molte ricerche, potresti dare un'occhiata ad alcune di esse. Ad esempio, questo documento (PDF ) fornisce un algoritmo di fingerprinting compatto delle immagini adatto a trovare immagini duplicate rapidamente e senza memorizzare molti dati. Sembra che questo sia l'approccio giusto se vuoi qualcosa di robusto.

Se stai cercando qualcosa di più semplice, ma sicuramente più ad-hoc, questa domanda SO ha alcune idee decenti.

Altri suggerimenti

Consiglierei di prendere in considerazione l'idea di abbandonare il semplice utilizzo di un istogramma RGB.

Un migliore digest della tua immagine può essere ottenuto se prendi una wavelet 2d Haar dell'immagine (è molto più facile di quanto sembri, è solo una media e alcune radici quadrate utilizzate per pesare i tuoi coefficienti) e mantieni i k coefficienti ponderati più grandi nella wavelet come un vettore rado, lo normalizzano e lo salvano per ridurne le dimensioni. Dovresti ridimensionare R G e B utilizzando almeno i pesi percettivi in ??anticipo o consiglierei di passare a YIQ (o YCoCg, per evitare il rumore di quantizzazione) in modo da poter campionare le informazioni di crominanza con importanza ridotta.

Ora puoi usare il prodotto punto di due di questi vettori normalizzati sparsi come misura di somiglianza. Le coppie di immagini con i punti più grandi avranno una struttura molto simile. Questo ha il vantaggio di essere leggermente resistente al ridimensionamento, allo spostamento di tonalità e alla filigrana, e di essere davvero facile da implementare e compatto.

È possibile compromettere l'archiviazione e la precisione aumentando o diminuendo k.

L'ordinamento per singolo punteggio numerico sarà intrattabile per questo tipo di problema di classificazione. Se ci pensate, richiederebbe che le immagini possano "cambiare" solo lungo un asse, ma non lo fanno. Questo è il motivo per cui hai bisogno di un vettore di funzionalità. Nel caso delle onde Haar è approssimativamente il punto in cui si verificano le discontinuità più nitide nell'immagine. Puoi calcolare una distanza tra le immagini in coppia, ma poiché tutto ciò che hai è una metrica della distanza un ordinamento lineare non ha modo di esprimere un "triangolo" di 3 immagini tutte ugualmente distanti. (vale a dire pensare a un'immagine che è tutta verde, un'immagine che è tutta rossa e un'immagine che è tutta blu.)

Ciò significa che qualsiasi soluzione reale al tuo problema avrà bisogno di operazioni O (n ^ 2) nel numero di immagini che hai. Considerando che se fosse stato possibile linearizzare la misura, si potrebbe richiedere solo O (n log n) o O (n) se la misura fosse adatta, diciamo, a un ordinamento radix. Detto questo, non è necessario spendere O (n ^ 2) poiché in pratica non è necessario setacciare l'intero set, è sufficiente trovare la roba più vicina di qualche soglia. Quindi, applicando una delle diverse tecniche per partizionare il tuo spazio vettoriale scarso, puoi ottenere asintotici molto più veloci per il problema "trovarmi k delle immagini che sono più simili di una determinata soglia" piuttosto che confrontare ingenuamente ogni immagine con ogni immagine, dandoti probabilmente hai bisogno di ... se non proprio quello che hai chiesto.

In ogni caso, l'ho usato qualche anno fa con buoni risultati personali quando ho cercato di minimizzare il numero di diverse trame che stavo memorizzando, ma c'è stato anche molto rumore di ricerca in questo spazio che mostra la sua efficacia (e in questo caso confrontandolo con una forma più sofisticata di classificazione dell'istogramma):

http://www.cs.princeton.edu/cass/papers/ spam_ceas07.pdf

Se hai bisogno di una maggiore accuratezza nel rilevamento, gli algoritmi minHash e tf-idf possono essere usati con l'onda Haar (o l'istogramma) per gestire le modifiche in modo più efficace:

http://cmp.felk.cvut.cz/~chum/ carte / chum_bmvc08.pdf

Infine, Stanford ha una ricerca di immagini basata su una variante più esotica di questo tipo di approccio, basata sul fare più estrazione delle caratteristiche dalle wavelet per trovare sezioni di immagini ruotate o ridimensionate, ecc., ma ciò probabilmente va ben oltre la quantità di lavoro che vorresti fare.

http://wang14.ist.psu.edu/cgi- bin / Zwang / regionsearch_show.cgi

Ho implementato un algoritmo molto affidabile per questo chiamato Fast Multiresolution Image Querying . Il mio codice (antico, non mantenuto) è qui .

Ciò che fa la query di immagini multirisoluzione veloce è dividere l'immagine in 3 pezzi in base allo spazio colore YIQ (migliore per le differenze di corrispondenza rispetto a RGB). Quindi l'immagine viene essenzialmente compressa usando un algoritmo wavelet fino a quando sono disponibili solo le caratteristiche più importanti di ogni spazio colore. Questi punti sono memorizzati in una struttura di dati. Le immagini delle query passano attraverso lo stesso processo e le caratteristiche importanti nell'immagine delle query vengono confrontate con quelle nel database memorizzato. Più corrispondenze, più è probabile che le immagini siano simili.

L'algoritmo viene spesso utilizzato per " query per sketch " funzionalità. Il mio software consentiva solo di inserire immagini di query tramite URL, quindi non esisteva l'interfaccia utente. Tuttavia, ho scoperto che ha funzionato eccezionalmente bene per abbinare le anteprime alla versione grande di quell'immagine.

Molto più impressionante del mio software è retrievr che ti consente di provare l'algoritmo FMIQ usando le immagini Flickr come fonte. Molto bello! Provalo tramite uno schizzo o usando un'immagine sorgente e puoi vedere come funziona.

Un'immagine ha molte caratteristiche, quindi a meno che non ti limiti a una, come la luminosità media, hai a che fare con uno spazio problematico n-dimensionale.

Se ti chiedessi di assegnare un singolo numero intero alle città del mondo, in modo da poter dire quali sono vicine, i risultati non sarebbero grandi. Ad esempio, potresti scegliere il fuso orario come numero intero singolo e ottenere buoni risultati con determinate città. Tuttavia, una città vicino al polo nord e un'altra città vicino al polo sud possono trovarsi nello stesso fuso orario, anche se si trovano alle estremità opposte del pianeta. Se ti permettessi di usare due numeri interi, potresti ottenere ottimi risultati con latitudine e longitudine. Il problema è lo stesso per la somiglianza delle immagini.

Detto questo, ci sono algoritmi che provano a raggruppare immagini simili insieme, che è effettivamente ciò che stai chiedendo. Questo è ciò che accade quando esegui il rilevamento del volto con Picasa. Anche prima di identificare i volti, li raggruppa insieme in modo che sia facile passare attraverso una serie di volti simili e dare a molti di essi lo stesso nome.

Esiste anche una tecnica chiamata Principle Component Analysis, che consente di ridurre i dati n-dimensionali fino a un numero inferiore di dimensioni. Quindi un'immagine con n funzioni potrebbe essere ridotta a una funzione. Tuttavia, questo non è ancora l'approccio migliore per confrontare le immagini.

Esiste una libreria C (" libphash " - http://phash.org/ ) che calcolerà un "hash percettivo" di un'immagine e ti consentono di rilevare immagini simili confrontando gli hash (quindi non devi confrontare ogni immagine direttamente con ogni altra immagine) ma sfortunatamente non sembrava essere molto preciso quando l'ho provato.

Devi decidere cosa è " simile. " Contrasto? Hue?

L'immagine è "simile"? alla stessa immagine sottosopra?

Scommetto che puoi trovare molte " chiudi chiamate " suddividendo le immagini in pezzi 4x4 e ottenendo un colore medio per ogni cella della griglia. Avresti sedici punteggi per immagine. Per giudicare la somiglianza, dovresti semplicemente fare una somma di quadrati di differenze tra le immagini.

Non penso che un singolo hash abbia senso, a meno che non sia contro un singolo concetto come tonalità, luminosità o contrasto.

Ecco la tua idea: 

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994

Prima di tutto, suppongo che questi siano numeri decimali che sono R * (2 ^ 16) + G * (2 ^ 8) + B, o qualcosa del genere. Ovviamente non va bene perché il rosso è ponderato in modo eccessivo.

Spostarsi nello spazio HSV sarebbe meglio. Puoi diffondere i bit di HSV fuori nell'hash, o potresti semplicemente sistemare H o S o V individualmente, oppure potresti avere tre hash per immagine.

Un'altra cosa. Se pesi R, G e B. Peso verde più alto, quindi rosso, quindi blu per abbinare la sensibilità visiva umana.

Nell'era dei servizi Web potresti provare http://tineye.com

La domanda Un buon modo per identificare immagini simili? sembra fornire una soluzione alla tua domanda.

ho ipotizzato che un altro software di ricerca di immagini duplicate esegua una FFT sulle immagini e memorizzi i valori delle diverse frequenze come vettori: 

Image1 = (u1, u2, u3, ..., un)
Image2 = (v1, v2, v3, ..., vn)

e quindi puoi confrontare due immagini per uguaglianza calcolando la distanza tra i vettori di peso di due immagini: 

distance = Sqrt(
     (u1-v1)^2 +
     (u2-v2)^2 +
     (u2-v3)^2 +
     ...
     (un-vn)^2);

Una soluzione è eseguire un RMS / RSS su ogni coppia di immagini necessarie per eseguire un ordinamento a bolle. In secondo luogo, potresti eseguire un FFT su ogni immagine e fare una media degli assi per recuperare un singolo intero per ogni immagine che useresti come indice per ordinare. Puoi prendere in considerazione qualsiasi confronto su una versione ridimensionata (25%, 10%) dell'originale a seconda di quanto piccola differenza scegli di ignorare e di quanto velocità richiedi. Fammi sapere se queste soluzioni sono interessanti e possiamo discutere o posso fornire un codice di esempio.

Gli approcci più moderni per rilevare il rilevamento di immagini quasi duplicate utilizzano il rilevamento di punti interessanti e descrittori che descrivono l'area intorno a tali punti. Spesso viene utilizzato SIFT . Quindi è possibile quatizzare i descrittori e utilizzare i cluster come vocabolario di parole visive.

Quindi, se vediamo il rapporto tra le parole visive comuni di due immagini e tutte le parole visive di queste immagini, si stima la somiglianza tra le immagini. Ci sono molti articoli interessanti. Uno di questi è Rilevamento di immagini quasi duplicate: minHash e tf-idf Ponderazione

Ad esempio, utilizzando l'estensione IMMI e IMMI, puoi esaminare molti modi diversi per misurare la somiglianza tra le immagini: http: / /spl.utko.feec.vutbr.cz/en/component/content/article/46-image-processing-extension-for-rapidminer-5

Definendo una soglia e selezionando un metodo è possibile misurare la somiglianza.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top