Immagine dell'impronta digitale per confrontare la somiglianza di molte immagini

Question

Ho bisogno di creare impronte digitali di molte immagini (circa 100.000 esistenti, 1000 nuove al giorno, RGB, JPEG, dimensione massima 800x800) per confrontare ogni immagine con ogni altra immagine molto velocemente. Non posso usare metodi di confronto binario perché dovrebbero essere riconosciute anche immagini che sono quasi simili.

La migliore sarebbe una libreria esistente, ma anche alcuni suggerimenti sugli algoritmi esistenti potrebbero aiutarmi molto.

Answer 1

Un modo per farlo è ridimensionare l'immagine e ridurre significativamente la risoluzione (a 200x200 forse?), Memorizzando una versione più piccola (mediata da pixel) per fare il confronto. Quindi definire una soglia di tolleranza e confrontare ciascun pixel. Se l'RGB di tutti i pixel è all'interno della tolleranza, hai una corrispondenza.

L'esecuzione iniziale è O (n^2) ma se si catalogano tutte le corrispondenze, ogni nuova immagine è solo un algoritmo O (n) da confrontare (è sufficiente confrontarlo con ciascuna immagine inserita in precedenza). Alla fine si romperà comunque, poiché l'elenco di immagini da confrontare diventa più grande, ma penso che tu sia al sicuro per un po '.

Dopo 400 giorni di funzionamento, avrai 500.000 immagini, ovvero (riduzione del tempo necessario per ridimensionare l'immagine) 200(H)*200(W)*500,000(images)*3(RGB) = 60.000.000.000 di confronti. Se ogni immagine è una corrispondenza esatta, rimarrai indietro, ma probabilmente non sarà così, giusto? Ricorda, puoi scartare un'immagine come corrispondenza non appena un singolo confronto cade al di fuori della tua soglia.

Answer 2

Vuoi letteralmente confrontare ogni immagine con le altre? Qual è l'applicazione? Forse hai solo bisogno di una sorta di indicizzazione e recupero di immagini basate su determinati descrittori? Quindi, ad esempio, è possibile consultare lo standard MPEG-7 per Multimedia Content Description Interface. Quindi è possibile confrontare i diversi descrittori di immagine, che non saranno così precisi ma molto più veloci.

Answer 3

Simile alla risposta di Ic - è possibile provare a confrontare le immagini a più risoluzioni. Quindi ogni immagine viene salvata come 1x1, 2x2, 4x4 .. 800x800. Se la risoluzione più bassa non corrisponde (soggetta a una soglia), puoi immediatamente respingerla. Se corrisponde, puoi confrontarli alla successiva risoluzione più alta, e così via.

Inoltre, se le immagini condividono strutture simili, ad esempio immagini mediche, potresti essere in grado di estrarre quella struttura in una descrizione questo è più facile/più veloce da confrontare.

Answer 4

Sembra che gli algoritmi di hashing delle immagini specializzate siano un'area di ricerca attiva, ma forse un normale calcolo dell'hash dei byte di immagine farebbe il trucco.

Stai cercando immagini identiche a byte piuttosto che cercare immagini derivate dalla stessa fonte ma potrebbe essere un formato o una risoluzione diversi (il che mi sembra un problema piuttosto difficile).

Answer 5

Gli algoritmi di calcolo hash normale o CRC non funzionano correttamente con i dati di immagine. La natura dimensionale delle informazioni deve essere presa in considerazione.

Se hai bisogno di impronte digitali estremamente robuste, in modo che le trasformazioni affini (ridimensionamento, rotazione, traslazione, flipping) siano prese in considerazione, puoi usare un Radon transformation on the image source per produrre una mappatura normativa dei dati dell'immagine - memorizzarla con ogni immagine e poi confronta solo le impronte digitali. Questo è un algoritmo complesso e non per i deboli di cuore.

alcune soluzioni semplici sono possibili:

1. Creare un istogramma di luminosità per l'immagine come un'impronta digitale
2. Crea versioni ridimensionate di ogni immagine come un'impronta digitale
3. combinate tecnica (1) e (2) in un approccio ibrido per una migliore qualità di confronto

Un istogramma di luminosità (specialmente uno che è separato in componenti RGB) è un'impronta digitale ragionevole per r un'immagine - e può essere implementata in modo abbastanza efficiente. Sottraendo un istogramma da un altro produrrà un nuovo storgram che puoi elaborare per decidere in che modo due immagini simili sono. Gli istogrammi, poiché valutano solo la distribuzione e l'occorrenza di luminosità/colore, gestiscono abbastanza bene le trasformazioni affini. Se si quantizzano le informazioni sulla luminosità di ciascun componente del colore su un valore di 8 bit, 768 byte di spazio di archiviazione sono sufficienti per l'impronta digitale di un'immagine di quasi tutte le dimensioni ragionevoli. Gli istogrammi di luminosità producono falsi negativi quando viene manipolata l'informazione sul colore in un'immagine. Se applichi trasformazioni come contrasto/luminosità, posterizzazione, spostamento del colore, modifica delle informazioni sulla luminosità. I falsi positivi sono anche possibili con certi tipi di immagini ... come paesaggi e immagini in cui un singolo colore domina gli altri.

L'utilizzo di immagini ridimensionate è un altro modo per ridurre la densità di informazioni dell'immagine a un livello più facile da confrontare. Le riduzioni al di sotto del 10% delle dimensioni dell'immagine originale in genere perdono troppe informazioni per essere utilizzate, pertanto un'immagine di 800x800 pixel può ridimensionarsi a 80x80 e fornire comunque informazioni sufficienti per eseguire impronte digitali decenti. A differenza dei dati dell'istogramma, è necessario eseguire il ridimensionamento anisotropico dei dati dell'immagine quando le risoluzioni di origine hanno proporzioni variabili. In altre parole, la riduzione di un'immagine 300x800 in una miniatura 80x80 causa la deformazione dell'immagine, in modo tale che se confrontata con un'immagine 300x500 (che è molto simile) causerà falsi negativi. Anche le impronte digitali delle miniature producono spesso falsi negativi quando sono coinvolte le trasformazioni affini. Se si capovolge o ruota un'immagine, la sua miniatura sarà molto diversa dall'originale e potrebbe risultare in un falso positivo.

La combinazione di entrambe le tecniche è un modo ragionevole per proteggere le proprie scommesse e ridurre l'insorgenza di falsi positivi e falsi negativi.

Answer 6

Molto tempo fa ho lavorato su un sistema che ha avuto alcune caratteristiche simili, e questo è un'approssimazione dell'algoritmo abbiamo seguito:

1. Divide l'immagine in zone. Nel nostro caso avevamo a che fare con video con risoluzione 4: 3, quindi abbiamo utilizzato 12 zone. In questo modo la risoluzione delle immagini di origine viene rimossa dall'immagine.
2. Per ogni zona, calcolare un colore generale - la media di tutti i pixel nella zona
3. Per l'intera immagine, calcolare un colore generale - la media di tutte le zone

Quindi, per ogni immagine, è Stai memorizzando i valori interi n + 1, dove n è il numero di zone che stai monitorando.

Per i confronti, è inoltre necessario esaminare singolarmente ciascun canale di colore.

1. Per l'immagine complessiva, confrontare i canali di colore per i colori complessivi per vedere se si trovano entro una certa soglia - per esempio, il 10%
2. Se le immagini sono entro la soglia, confrontare prossimo ogni zona. Se anche tutte le zone sono all'interno della soglia, le immagini sono abbastanza forti da poterle almeno contrassegnare per ulteriori confronti.

Ciò consente di eliminare rapidamente le immagini che non corrispondono; puoi anche utilizzare più zone e/o applicare l'algoritmo in modo ricorsivo per ottenere maggiore sicurezza di corrispondenza.

Answer 7

C'è un approccio molto meno ad-hoc rispetto alle varianti di immagine ridotte che sono state proposte qui che mantengono il loro sapore generale, ma che fornisce una base matematica molto più rigorosa per ciò che sta accadendo.

Prendere un Haar wavelet dell'immagine. Fondamentalmente l'wavelet Haar è la successione di differenze dalle immagini a risoluzione più bassa a ciascuna immagine a risoluzione più alta, ma ponderata dalla profondità che si ha nell''albero 'di mipmaps. Il calcolo è semplice. Quindi, una volta che l'wavelet Haar è stata opportunamente ponderata, butta via tutti i coefficienti k più grandi (in termini di valore assoluto), normalizza il vettore e salvalo.

Se si prende il prodotto punto di due di quei vettori normalizzati, si ottiene una misura di somiglianza con 1 quasi identico. Ho pubblicato ulteriori informazioni su here.

Answer 8

oppure è possibile utilizzare http://tineye.com che fa esattamente quello che vuoi! (Controllare l'API commerciale)

ma sono interessato su come lo fanno, che la tecnologia ecc ...

Answer 9

Così si vuole fare "corrispondenza dell'impronta digitale" che è abbastanza diverso da "immagine corrispondente". l'analisi delle impronte digitali è stato studiato a fondo nel corso degli ultimi 20 anni, e sono stati sviluppati diversi algoritmi interessanti al fine di garantire il tasso di rilevamento a destra (rispetto alla FAR e FRR misure - False Acceptance Rate e False Rejection Rate).

Ti suggerisco di guardare meglio a LFA (Local Feature Analysis) classe di tecniche di rilevamento, per lo più costruite su ispezione minuzie. Le minuzie sono caratteristiche specifiche di qualsiasi impronta digitale e sono state classificate in diverse classi. La mappatura di un'immagine raster in una mappa delle minuzie è ciò che effettivamente fa la maggior parte delle autorità pubbliche per depositare criminali o terroristi.

Vedi here per ulteriori riferimenti

Answer 10

Per iPhone confronto delle immagini e l'immagine di sviluppo somiglianza check out: http://sites.google.com/site/imagecomparison/

per vederlo in azione, controlla eyeBuy Visual Search su iTunes AppStore.

Answer 11

Si consiglia di dare un'occhiata a phash.

Per confronto delle immagini c'è questo php progetto: https://github.com/kennethrapp/phasher

E la mia piccola javascript clone: ​​ https://redaktorcms.com/dev/phasher/demo_js/index.html

Purtroppo questo è "bitcount" Cheng, ma riconosceranno immagini ruotate. Un altro approccio in javascript è stato quello di costruire un istogramma di luminosità dall'immagine con l'aiuto della tela. È possibile visualizzare un istogramma poligonale sulla tela e confrontare quel poligono nel database (ad esempio, mySQL spaziale ...)

Si tratta di una demo per istogrammi di video: https://redaktorcms.com/dev/globetrottr/testHashVideo.php

Answer 12

A partire dal 2015 (ritorno al futuro ... in questa domanda del 2009 che ora è di alto livello in Google) la somiglianza delle immagini può essere calcolata utilizzando tecniche di Deep Learning. La famiglia di algoritmi noti come Encoder automatici può creare una rappresentazione vettoriale che è ricercabile per similarità. C'è una demo here.