Rimozione di immagini duplicate [chiuso]

https://stackoverflow.com/questions/225210

03-07-2019
|

Domanda

Abbiamo una raccolta di immagini fotografiche che misurano alcune centinaia di concerti. Un gran numero di foto sono duplicate visivamente, ma con dimensioni, risoluzione, compressione ecc. Diverse

È possibile utilizzare metodi specifici di elaborazione delle immagini per cercare e rimuovere queste immagini duplicate?

Soluzione

Di recente ho voluto svolgere questo compito per una galleria di immagini PHP. Volevo essere in grado di generare un & Quot; fuzzy & Quot; impronta digitale per un'immagine caricata e verifica se nel database sono presenti immagini con la stessa impronta digitale, indicando che erano simili, quindi confrontale più da vicino per determinare quanto simili.

L'ho realizzato ridimensionando l'immagine caricata a 150 pixel di larghezza, riducendola alla scala di grigi, arrotondando il valore di ciascun colore al multiplo più vicino di 16 (dando 17 possibili sfumature di grigio tra 0 e 255), normalizzandole e memorizzarli in un array, creando così un " fuzzy " istogramma di colore, quindi creando un md5sum dell'istogramma che potrei quindi cercare nel mio database. Questo è stato estremamente efficace nel restringere le immagini che erano molto simili visivamente al file caricato.

Quindi, per confrontare il file caricato con ogni " simile " immagine nel database, ho preso entrambe le immagini, le ho ridimensionate a 16x16 e le ho analizzate pixel per pixel e ho tolto il valore RGB di ogni pixel dal valore del pixel corrispondente nell'altra immagine, sommando tutti i valori e dividendoli per il numero di pixel che mi dà una deviazione del colore media. Qualcosa di meno del valore specifico è stato determinato come duplicato.

Il tutto è scritto in PHP usando il modulo GD, e un confronto con migliaia di immagini richiede solo poche centinaia di millisecondi per file caricato.

Il mio codice e la mia metodologia sono qui: http://www.catpa.ws / php-duplicate-image-finder /

Altri suggerimenti

Prova PerceptualDiff per confrontare 2 immagini con le stesse dimensioni. Consente di non distinguere visivamente immagini come la considerazione di immagini con solo un numero X di pixel diversi.

Se i duplicati visivi possono avere dimensioni diverse a causa del ridimensionamento o di tipi di file diversi, potresti voler creare un formato standard per i confronti. Ad esempio, potrei usare ImageMagick per ridimensionare tutte le immagini su 100x100 e salvarle come file PNG.

Un approccio molto semplice è il seguente:

Converti l'immagine in scala di grigi in memoria, quindi ogni pixel è solo un numero compreso tra 0 (nero) e 255 (bianco).
Ridimensiona l'immagine a una dimensione fissa. Trovare la giusta dimensione è importante, dovresti giocare con diverse dimensioni. Per esempio. potresti ridimensionare ogni immagine a 64x64 pixel, ma potresti ottenere risultati migliori o peggiori con immagini più piccole o più grandi.
Una volta fatto questo per tutte le immagini (sì, ci vorrà del tempo), carica sempre due immagini in memoria e sottrale l'una dall'altra. Cioè sottrarre il valore di pixel (0,0) nell'immagine A ob il valore di pixel (0,0) nell'immagine B, ora fare lo stesso per (0,1) in entrambi e così via. Il valore risultante potrebbe essere positivo o negativo, dovresti sempre memorizzare il valore assoluto (quindi 5 risultati in 5, -8 ma risultati in 8).
Ora hai una terza immagine essendo " differenza immagine " (immagine delta) dell'immagine A e B. Se fossero identici, l'immagine delta è tutta nera (tutti i valori verranno sottratti a zero). Il & Quot; meno nero & Quot; è, meno identiche sono le immagini. Devi trovare una buona soglia, poiché anche se le immagini sono in effetti identiche (ai tuoi occhi), ridimensionando, alterando la luminosità e così via, l'immagine delta non sarà totalmente nera, ma avrà solo grigi molto scuri. Quindi hai bisogno di una soglia che dice & Quot; Se l'errore medio (luminosità dell'immagine delta) è inferiore a un certo valore, ci sono ancora buone probabilità che possano essere identici, tuttavia se è al di sopra di quel valore, molto probabilmente non lo sono . Trovare la soglia giusta è difficile come trovare la giusta dimensione di ridimensionamento. Avrai sempre falsi positivi (immagini ritenute identiche, anche se non lo sono affatto) e falsi negativi (immagini ritenute non identiche, sebbene lo siano).

Questo algoritmo è ultra lento. In realtà solo la creazione di immagini in scala di grigi richiede tonnellate di tempo. Quindi devi confrontare ogni immagine GS con un'altra, ancora una volta, tonnellate di tempo. Anche la memorizzazione di tutte le immagini GS richiede molto spazio su disco. Quindi questo algoritmo è pessimo, ma i risultati non sono poi così male, anche se è così semplice. Sebbene i risultati non siano sorprendenti, sono migliori di quanto avessi inizialmente pensato.

L'unico modo per ottenere risultati ancora migliori è utilizzare l'elaborazione avanzata delle immagini e qui inizia a diventare davvero complicato. Implica molta matematica (molto); ci sono buone applicazioni (dupe finder) per molti sistemi che li hanno implementati, quindi a meno che tu non debba programmarlo tu stesso, probabilmente stai meglio usando una di queste soluzioni. Ho letto molti articoli su questo argomento, ma temo che la maggior parte di questo vada oltre il mio orizzonte. Anche gli algoritmi che potrei essere in grado di implementare secondo questi articoli sono al di là di esso; ciò significa che capisco cosa deve essere fatto, ma non ho idea del perché funzioni o di come funzioni effettivamente, è solo magia ;-)

In realtà ho scritto una applicazione che fa proprio questo.

Ho iniziato con un'applicazione precedente che utilizzava un algoritmo di base Levenshtein Distance per calcolare la somiglianza delle immagini, ma questo metodo è indesiderabile per una serie di motivi. Senza dubbio, l'algoritmo più veloce che troverai per determinare la somiglianza delle immagini è errore al quadrato medio o significa errore assoluto (entrambi hanno un tempo di esecuzione di O (n), dove n è il numero di pixel nell'immagine, e sarebbe anche banale infilare un'implementazione di entrambi gli algoritmi in diversi modi). Il post di Mecki è in realtà solo un'implementazione di Errore assoluto medio, che la mia applicazione può eseguire (il codice è disponibile anche per il piacere di navigare, se lo desideri).

In ogni caso, nella nostra applicazione, eseguiamo prima il down-campionamento delle immagini (ad es. tutto viene ridimensionato, ad esempio, 32 * 32 pixel), quindi convertiamo in scala di grigi e quindi eseguiamo le immagini risultanti attraverso i nostri algoritmi di confronto. Stiamo anche lavorando su alcuni algoritmi di pre-elaborazione più avanzati per normalizzare ulteriormente le immagini, ma ... non ancora del tutto.

Esistono algoritmi decisamente migliori di MSE / MAE (in effetti, i problemi con questi due algoritmi applicati alle informazioni visive sono stati ben documentati), come SSIM , ma ha un costo. Altre persone tentano di confrontare altre qualità visive nell'immagine, come luminanza, contrasto, istogrammi di colore, ecc., Ma è tutto costoso rispetto alla semplice misurazione del segnale di errore.

La mia applicazione potrebbe funzionare, a seconda di quante immagini sono presenti in quelle cartelle. È multi-thread (l'ho visto caricare completamente otto core del processore durante i confronti), ma non ho mai testato un database di immagini più grande di qualche centinaio di immagini. Alcune centinaia di concerti di immagini suonano in modo proibitivo. (semplicemente leggerli dal disco, effettuare il downsampling, convertirli in scala di grigi e archiviarli in memoria - supponendo che abbiate memoria sufficiente per contenere tutto, cosa che probabilmente non riuscite - potrebbe richiedere un paio d'ore).

Questa è ancora un'area di ricerca, credo. Se hai del tempo a disposizione, alcune parole chiave pertinenti sono:

Rilevamento copia immagine
Recupero di immagini in base al contenuto
Indicizzazione delle immagini
Rimozione duplicati immagine

Fondamentalmente, ogni immagine viene elaborata (indicizzata) per produrre un " firma dell'immagine " ;. Immagini simili hanno firme simili. Se le tue immagini vengono ridimensionate, probabilmente la loro firma è quasi identica, quindi si raggruppano bene. Alcune firme popolari sono i descrittori MPEG-7. Per raggruppare, penso che K-Means o una qualsiasi delle sue varianti possano essere sufficienti. Tuttavia, probabilmente dovrai gestire milioni di immagini, questo potrebbe essere un problema.

Ecco un link alla voce principale di Wikipedia:
http://en.wikipedia.org/wiki/CBIR

Spero che questo aiuti.

La somiglianza delle immagini è probabilmente un sottocampo dell'elaborazione delle immagini / AI.

Preparati a implementare algoritmi / formule dagli articoli se stai cercando una soluzione eccellente (cioè performante e scalabile).

Se vuoi qualcosa di veloce e sporco, cerca in Google Somiglianza d'immagine

Ecco un'app di somiglianza di immagine C # che potrebbe fare ciò vuoi.

Fondamentalmente, tutti gli algoritmi estraggono e confrontano le funzionalità. Come definiscono & Quot; feature & Quot; dipende dal modello matematico su cui si basano.

Un trucco rapido è quello di scrivere un programma che calcolerà il valore del pixel medio in ogni immagine, in scala di grigi, ordinando per questo valore e poi confrontandoli visivamente. Immagini molto simili dovrebbero comparire una accanto all'altra nell'ordine ordinato.

Avrai bisogno di uno strumento da riga di comando per gestire così tanti dati.

Il confronto di ogni possibile coppia di immagini non si ridimensionerà a un insieme così ampio di immagini. È necessario ordinare l'intero set di immagini in base ad alcune metriche in modo che ulteriormente i confronti sono necessari solo sulle immagini vicine.

Un esempio di metrica semplice è il valore medio di tutti i pixel in un'immagine, espresso come un singolo valore in scala di grigi. Questo dovrebbe funzionare solo se i duplicati non hanno avuto alterazioni visive. L'uso di un formato di file con perdita può anche comportare alterazioni visive.

Pensando fuori dagli schemi, potresti essere in grado di usare i metadati delle immagini per restringere il tuo set di dati. Ad esempio, le tue immagini potrebbero avere campi che mostrano la data e l'ora in cui è stata scattata l'immagine, fino al secondo più vicino. È probabile che i duplicati abbiano valori identici. Uno strumento come exiv2 potrebbe essere utilizzato per scaricare questi dati in un formato di testo più comodo e ordinabile (con una piccola conoscenza degli script batch / shell).

Anche campi come il produttore e il modello della fotocamera potrebbero essere utilizzati per ridurre un set di 1.000.000 di immagini per dire 100 serie di 10.000 immagini, un miglioramento significativo.

Il programma gqview ha un'opzione per trovare duplicati, quindi potresti provare a cercarlo. Tuttavia, non è infallibile, quindi sarebbe solo euristico presentare duplicati a un essere umano, per una conferma manuale.

La parte più importante è rendere i file comparabili.

Una soluzione generica potrebbe essere quella di ridimensionare tutte le immagini a una determinata dimensione e scala di grigi fisse. Quindi salvare le immagini risultanti in una directory separata con lo stesso nome per riferimento futuro. Sarebbe quindi possibile ordinare per dimensione del file e confrontare visivamente le voci vicine.

Le immagini risultanti potrebbero essere quantificate in alcuni modi per rilevare programmaticamente somiglianze (media di blocchi, linee ecc.).

Immagino che il metodo più scalabile sarebbe quello di memorizzare un'impronta digitale con ogni immagine. Quindi quando viene aggiunta una nuova immagine, è un semplice caso di SELECT id FROM photos where id='uploaded_image_id' verificare la presenza di duplicati (o eseguire il fingerprinting di tutte le immagini, quindi eseguire una query per duplicati

Ovviamente un semplice hash di file non funzionerebbe poiché il contenuto effettivo differisce ..

Impronta digitale acustica / questo documento può essere un buon inizio per il concetto, poiché ci sono molte implementazioni di questo. Qui è un documento sull'impronta digitale delle immagini.

Detto questo, potresti riuscire a cavartela con qualcosa di più semplice. Qualcosa di semplice come ridimensionare l'immagine alla stessa larghezza o altezza, sottraendo image_a da image_b e sommando la differenza. Se la differenza totale è inferiore a una soglia, l'immagine è un duplicato.

Il problema è che devi confrontare ogni immagine con un'altra. Il tempo richiesto aumenterà esponenzialmente ..

Se riesci a trovare un modo per confrontare le immagini che obbediscono alla disuguaglianza del triangolo (ad esempio, se d (a, b) è la differenza tra le immagini aeb, quindi d (a, b) < d (a, c) + d (b, c) per tutti a, b, c), quindi a BK-Tree sarebbe un modo efficace di indicizzare le immagini in modo tale da poter trovare corrispondenze nel tempo O (log n) anziché in O (n) per ogni immagine.

Se le tue corrispondenze sono limitate alla stessa immagine dopo aver variato quantità di compressione / ridimensionamento / ecc., la conversione in alcune dimensioni canoniche / bilanciamento del colore / ecc. e la semplice somma dei quadrati delle differenze di ciascun pixel può essere una buona metrica e questo obbedisce alla disuguaglianza del triangolo, quindi potresti usare un albero BK per un accesso efficiente.

Se hai un po 'di soldi da spendere, e forse una volta che esegui un primo passaggio per determinare quali immagini sono forse , potresti scrivere un test per Mechanical Turk di Amazon.

https://www.mturk.com/mturk/welcome

In sostanza, dovresti creare un piccolo widget che AMT mostrerebbe agli utenti umani reali che in pratica dovrebbero semplicemente rispondere alla domanda " Queste due immagini sono uguali? " ;. Oppure potresti mostrare loro una griglia di dire immagini 5x5 e chiedere loro & Quot; Quali di queste immagini corrispondono? & Quot ;. Quindi raccoglieresti i dati.

Un altro approccio sarebbe quello di utilizzare i principi della computazione umana che sono stati più famosi sposati da Luis Von Ahn ( http://www.cs.cmu.edu/~biglou/ ) con reCaptcha, che utilizza le risposte Captcha per determinare le parole illeggibili che sono state eseguite attraverso il riconoscimento ottico dei caratteri, contribuendo così alla digitalizzazione dei libri. È possibile creare un captcha che chieda agli utenti di aiutare a perfezionare le immagini.

Sembra un problema procedurale piuttosto che un problema di programmazione. Chi carica le foto? Tu o i clienti? Se stai caricando la foto, standardizza le dimensioni in una scala fissa e in un formato file. In questo modo i confronti saranno più facili. Tuttavia, per così dire, a meno che tu non abbia giorni - o addirittura settimane di tempo libero - ti suggerisco di rimuovere invece manualmente le immagini duplicate da te o dal tuo team confrontando visivamente le immagini.

Forse dovresti raggruppare le immagini per posizione poiché si tratta di immagini turistiche.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow