Trovare i file video duplicati dal database di (milioni), delle impronte digitali? il riconoscimento del modello?

Question

Nel seguente scenario:

Ho un progetto che abbia un catalogo di attualmente circa diecimila file video, il numero è destinato ad aumentare in modo drammatico.

Tuttavia molti di loro sono duplicati. Con ogni file video che ho associato informazione semantica e descrittive che voglio unisci duplicati per achive risultati migliori per tutti.

Ora ho bisogno di un qualche tipo di procedura in cui ho indice di metadati in un database, e ogni volta che un nuovo video entra nel catalogo gli stessi dati viene calcolata e confrontata nel database.

Il problema è che i video non sono duplicati esatti. Possono avere diversa qualità, sono amby ritagliate, in filigrana o di avere un sequel / prequel. O sono tagliati fuori all'inizio e / o alla fine.

Sfortunatamente meglio il confronto più CPU e molta memoria diventa così ho intenzione di attuazione diversi strati di confronto che iniziano con molto elegante ma Comparazione veloce (video lengh maby con una tolleranza di 10%) e terminare con il confronto finale che decide se la sua davvero un duplicato (che sarebbe stato un voto della Comunità).

Quindi, come ho una comunità per verificare i risultati è sufficiente per fornire "buone ipotesi" con un basso rapporto perdere.

Così ora la mia domanda è che cosa strati possono voi ragazzi pensare o avete un approccio migliore?

non mi interessa lo sforzo per creare i metadati, ho abbastanza schiavi per farlo. Proprio il confronto dovrebbe essere veloce. Quindi, se aiuta posso convertire il video 100 volte così ...

Ecco le mie idee correnti:

• alla durata del video (secondi)

• prima e l'ultima analisi cornice

Vorrei ricampionare l'immagine a una dimensione delle miniature e ottenere i valori medi rgb poi pixel per pixel serialize se il colore a questo pixel è maggiore / minore rispetto alla media rappresentata da 0 o 1. Così ottengo una stringa binaria che ho può memorizzare in mysql e fare un po somma booleana (supportato da mysql internamente) e contare i bit rimanenti uneval (come ben supportato internamente, che sarebbe allora la distanza Levenshtein delle corde bianry)

• sviluppo del bitrate nel tempo con lo stesso codec VBR

vorrei convertire il video in un file video VBR con le stesse impostazioni. quindi vorrei guardare il bitrate in certi punti del tempo (percentuale del video completato o secondi assoluti .. poi ci sarebbe di analizzare solo una parte del video). stessa cosa con l'immagine. Iif il bitrate è maggiore della media Nella 1 altro suo 0. facciamo una stringa binaria e conservarla in db e calcoliamo la distanza Levenshtein tardi

• L'analisi audio (bitrate e decibel varaition nel tempo proprio come il bitrate del video)

• analisi fotogramma chiave

Immagine comarision proprio come il primo e l'ultimo fotogramma, ma in posizioni dei fotogrammi chiave? Vorremmo utilizzare gli stessi file di origine che abbiamo usato per calcluiations bitrate, perché i fotogrammi chiave sono pesanti dipendeva il codec e le impostazioni.

• sviluppo del colore nel tempo

Forse Diamo una o più aree / pixel all'interno dell'immagine e vedere come sviluppare nel corso del tempo. Come pure il cambiamento abov / sotto la media. nero / bianco sarebbe sufficiente che penso.

• presente i suggerimenti per l'utente per l'approvazione definitiva ...

o sto andando nella direzione completamente sbagliata? Penso che non posso essere il primo uno che ha questo problema, ma non ho avuto alcuna fortuna trovare soluzioni.

Answer 1

Questo è un problema enorme, così ho scelto di scrivere una risposta piuttosto lunga per provare a scomporre il problema in parti che possono essere più facili da risolvere.

E 'importante che i confronti siano effettuati utilizzando le risorse di calcolo e di tempo a disposizione: Dubito una soluzione che vogliono mesi per l'esecuzione sarà molto utile in un database video dinamici. E la dimensione del database probabilmente rende l'uso del cloud risorse informatiche irrealizzabile. Così abbiamo veramente a cuore il costo locale di ogni confronto in diversi ambiti differenti:. 1) stoccaggio dei dati, 2) risorse di calcolo, e 3) il tempo

Un costo fondamentale da considerare è quello di estrarre i dati necessari da ogni video per qualsiasi metriche di confronto devono essere utilizzati. Una volta che i dati estratti è disponibile, allora il costo di eseguire un confronto deve essere considerato. Infine, i confronti necessari per soddisfare tutti i video tra di loro deve essere eseguita.

Il costo dei primi due passi è O (1) sul numero di video. Il costo dell'ultima passo deve essere peggiore O (1), potenzialmente molto peggio. Così il nostro obiettivo primario dovrebbe essere ridurre al minimo i costi di l'ultimo passo, anche se ciò significa l'aggiunta di molti dei primi, semplici passaggi.

Gli algoritmi ottimali per questo processo notevolmente dipenderà dalle caratteristiche del database, il livello al quale esistono partite singole e multiple. Se il 100% dei video corrisponde qualche altro video, quindi vorremo ridurre al minimo il costo di un successo di abbinamento. Tuttavia, il caso più probabile è che le partite saranno rare, quindi vorremo ridurre al minimo il costo di una partita senza successo. Vale a dire, se c'è un modo rapido e sporco di dire "questi due video non possono essere partite, allora dovremmo usarlo primo luogo, prima ancora di iniziare a confermare una partita.

Per caratterizzare il database, prima fare un po 'di campionamento e la mano-matching per estimnate il grado di corrispondenza all'interno del database. Questo esperimento dovrebbe mostrare come i video ridondanti "aggregata": Se un dato video ha avuto un incontro, come probabilmente era di avere più di una singola partita? Qual è la percentuale di tutte le partite erano anche parte di una partita più? Questo processo produrrà un 'modello' del database (una distribuzione statistica) che verrà utilizzato per aiutare algoritmo di selezione e ottimizzare il sistema.

Andando avanti mi assumo le partite sono relativamente rari. Dopo tutto, se ci sono un sacco di partite, i video saranno "aggregano", di fatto rendendo il database più piccoli, e rendendo così il problema più semplice. Supponiamo che i soggiorni problema il più forte possibile.

mi piacerebbe sostengono un approccio a più livelli di categorizzazione, dove avevamo costruire una sequenza di algoritmi che eseguono più volte la decisione binario di "questi due video non corrispondono" / "questi due video possono eventualmente corrispondere". Solo l'ultimo algoritmo nelle esigenze della catena di uscita la risposta "Questi due video partita".

Classificazione / corrispondenza algoritmi può fallire in uno o entrambi dei seguenti modi: False Positive (video non corrispondenti vengono mislabled come corrispondenza) e falso negativo (video corrispondenti vengono scambiati per non-matching). Ognuna di queste decisioni sbagliate ha una gamma di probabilità ad esso associati, e vogliamo minimizzare sia.

Dato che stiamo costruendo una pipeline algoritmo, vogliamo algoritmi che sono molto bravo a identificare i non partite senza errori, nel senso che devono avere un bassissimo tasso di False Reject, e noi non facciamo molta cura sulla False Accept tasso. Ad esempio, il clone di Wierd Al di un video può look e il suono molto simile all'originale, e potremmo non essere in grado di dimostrare che non è una partita all'originale fino a tardi in cantiere algoritmo.

Il più semplice, più veloce, la maggior parte degli algoritmi affidabili deve essere eseguito prima, dal momento che la stragrande maggioranza dei test produrrà il risultato "non corrispondono". Il controllo più semplice sarebbe quella di cercare i file identici all'interno del database, qualcosa di fatto da molti programmi di utilità del file system e di manutenzione del database semplici e veloci.Dopo questa scansione viene eseguita, si può supporre che sarà effettivamente bisogno di aprire e leggere i file video per rilevare le differenze.

Dal confronto il video è relativamente difficile, cominciamo con l'audio. Pensate al database come primo è una raccolta di MP3 che può contenere duplicati. Dopo tutto, se vogliamo ottenere una buona partita audio, è molto probabile che avremo un match video, e viceversa. Possiamo tranquillamente dire l'audio è un rappresentante 'giusto' per il video. Fortunatamente, un rapida ricerca sul web produrrà molti pacchetti impronte digitali e confronto audio che sono affidabili, veloci e maturo. L'impronta digitale audio dovrebbe essere generato per ogni video nel database. Video prive di una traccia audio cadrebbero automaticamente nella "potrebbe corrispondere a" set.

Ma c'è un 'Gotcha' qui: Che dire di voice-over? Se un dato video è codificato due volte, con e senza una voce fuori campo, essi sono un fiammifero o no? Che cosa circa l'audio francese contro la spagnola o inglese? Se questi dovrebbero essere considerati una corrispondenza, allora il test audio potrebbe dover essere saltato.

A questo punto, sappiamo che le voci del filesystem sono tutti "abbastanza diversa", e sappiamo che le tracce audio sono tutti "abbastanza diversa" (se testato), il che significa che non possiamo mettere fuori guardando i dati video qualsiasi più a lungo. Fortunatamente, questo dovrebbe aver bisogno di essere fatto solo una piccola frazione del database dei video, in modo che possiamo tollerare qualche costo. Come prima, ci sarà ancora voglia di prima di tentare di eliminare rapidamente più non-match prima di cercare di etichettare positivamente un match.

Dal momento che abbiamo bisogno di prendere risoluzione cambia in considerazione (ad esempio, da 1080p a iPod), si avrà bisogno di un modo per informazioni video caratterizzano che non è solo indipendente dalla risoluzione, ma anche tollerante di rumore aggiunti e / o perdita di dati come parte della modifica della risoluzione. Dobbiamo tollerare variazioni di frame rate (per esempio, da 24 fps di un film a 30 fps di video). Ci sono anche cambiamenti proporzioni da considerare, ad esempio da 4: 3 NTSC a 16: 9 HD. Vorremmo gestire le modifiche di spazio colore, come ad esempio da colore a bianco e nero.

Poi ci sono trasformazioni che interessano tutti questi immediatamente, come transcodifica tra HD e PAL, che può influenzare contemporaneamente spazio colore, frame rate, proporzioni e risoluzione. La caratterizzazione dovrebbe anche essere tollerante di un certo grado di ritaglio e / o di riempimento, come accadrebbe da una schiena interruttore e indietro tra 4: 3 e 16: 9 proporzioni (Letterboxing, ma non pan & scan). Abbiamo anche dovuto gestire i video che sono stati troncati, come la rimozione dei crediti dalla fine di un lungometraggio. E, ovviamente, dobbiamo anche gestire le differenze creati da diversi codificatori che sono stati alimentati un flusso video identica.

Questo è un bel lista! Prendiamo in considerazione alcune cose che possono scegliere di non conto: ho il sospetto che è OK non riuscire a trovare una corrispondenza quando l'immagine deformazione è presente, nonostante il fatto che la deformazione anamorfica non è raro, soprattutto nei film 35 millimetri wide-screen che erano direttamente digitalizzato senza anamorfico ricostruzione (persone alte-magre). Si può anche scegliere di non riuscire quando grandi filigrane sono presenti nel centro del telaio, anche se vorremo tollerare filigrane più piccole negli angoli. E, infine, è OK per riuscire a soddisfare i video che sono stati temporaneamente distorti o spazialmente capovolto, come quando uno è uno slo-mo dell'altro, o è stato capovolto da sinistra a destra.

fa che quasi coprono lo spazio video? Speriamo che sia chiaro il motivo per cui è importante iniziare con il file system e l'audio! Questo è, in primo luogo pensare del database più come una collezione di MP3 prima di considerare come una collezione di video.

Ignorando l'audio, il video è solo una sequenza ordinata di immagini fisse. Quindi stiamo in realtà alla ricerca di uno o più algoritmi di confronto delle immagini in combinazione con uno o più algoritmi di confronto di serie temporali. Questo potrebbe essere o coppie di algoritmi separati (characteRIZE ogni fotogramma, quindi caratterizzare la sequenza di fotogrammi), oppure potrebbe essere fusa in un solo algoritmo (esaminare le differenze tra i fotogrammi).

Le immagini stesse può essere scomposto ulteriormente, in un'immagine monocromatica 'strutturale' e un colore 'overlay'. Credo che possiamo tranquillamente ignorare le informazioni sul colore, se è computazionalmente conveniente farlo.

Da quanto sopra, può sembrare che abbia assunto dovremo decodificare completamente un video al fine di eseguire qualsiasi confronto su di esso. Che non è necessariamente il caso, anche se il confronto dei dati codificati ha molte difficoltà che limitano la sua utilità. L'unica eccezione a questa è significativo per le codifiche di video a livello di oggetti quali MP4, dove sono state eseguite molto alto livello comparazioni fotogrammi multipli. Purtroppo, il confronto tra i flussi oggetto MP4 non ha visto molte ricerche, e sono a conoscenza di nessun pacchetto in grado di svolgere questa funzione. Ma se trovate uno, usarlo!

La maggior parte degli altri flussi video digitali utilizzano la codifica di programmi come MPEG2, QuickTime, o qualcosa di simile. Questi schemi tutti usano il concetto di fotogrammi chiave e cornici di differenza, anche se ogni implementa in modo diverso. Quando diversi video sono messi a confronto (quelli che non sono della stessa dimensione), è improbabile che i fotogrammi chiave e cornici differenza corrisponderà a qualsiasi grado utile. Tuttavia, questo non significa che è impossibile, e pacchetti esistono che tentano di estrarre informazioni utili da tali flussi senza eseguire decodifica completa. Se si trova uno che è veloce, potrebbe cadere in un "perché non provare" categoria di test.

L'unico trucco che verrà utilizzata è invece di decodificare completamente telai, vorrei invece li decodifica solo in canali separati componenti (HSV, HSL, YUV, qualsiasi cosa) e non fino al framebuffer RGB (a meno che questo è ciò che è stato codificati , ovviamente). Da qui, mi piacerebbe creare prossimo luminanza e crominanza separati (colore) fotogrammi in modo confronti possono essere eseguiti in domini correlati. Decodifica tutta la strada a un framebuffer RGB può introdurre errori che possono rendere le partite trovando più difficile.

Poi, mi piacerebbe scartare le informazioni sul colore. Dal momento che un video in bianco e nero deve corrispondere il suo colore originale, semplicemente non si preoccupano di colore!

Come può la sequenza risultante di fotogrammi in bianco e nero più essere paragonata ad un'altra sequenza che può apparire molto diverso, ma ancora può eventualmente essere una partita? Ci sono stati letteralmente decenni di ricerca in questo settore, in gran parte classificati con "match rilevamento scala-invariante". Purtroppo, molto poco di questa ricerca è stata direttamente applicata a determinare quando i video non o non corrispondono.

Per i nostri scopi, siamo in grado di affrontare questo problema da diverse direzioni. In primo luogo, dobbiamo sapere per noi stessi ciò che è e non è una partita nel dominio in bianco e nero. Per esempio, non si preoccupano di differenze a livello di pixel, in quanto anche se due video di corrispondenza ma-differenti avevano la stessa risoluzione, dobbiamo tollerare un certo livello di rumore a causa di cose come le differenze encoder.

Un semplice (ma lento) modo è ora di trasformare ogni immagine in una forma che è indipendente sia risoluzione e rapporto di aspetto. Una tale trasformazione è nel dominio delle frequenze spaziali, e la FFT 2D è ideale per questo. Dopo aver scartato la componente immaginaria, la componente reale può essere troncato alle alte frequenze per rimuovere il rumore e alle basse frequenze per rimuovere gli effetti proporzioni, quindi normalizzato a una scala standard eliminare differenze di risoluzione. I risultanti aspetto di dati, come un'immagine piccolo strano che possa essere confrontato direttamente attraverso flussi video.

Ci sono molte altre strategie possibili cornice di trasformazione, molte di gran lunga più efficiente rispetto alla FFT, e una ricerca bibliografica dovrebbe evidenziarle. Purtroppo, io so di pochi che sono state attuate in librerie software che sono facili da usare come FFT.

Una volta che abbiamo trasformato il bianco e nerotelai in un dominio più piccolo e più utile, abbiamo ancora devono eseguire il confronto ad un altro tale flusso da un altro video. E che il video è quasi certo di non essere una partita fotogramma per fotogramma, in modo da un semplice confronto sarà certamente fallire. Abbiamo bisogno di un confronto che porterà sulla considerazione le differenze nel dominio del tempo, tra cui aggiunti fotogrammi / rimossi e le differenze di frame rate.

Se si guarda alla sequenza di fotogrammi FFT, si noterà un comportamento molto distinto. dissolvenze scena sono brusco ed estremamente facile da individuare, tagli possono anche essere distinti, e ci sono tipicamente modifiche solo lenti visto nel FFT tra tagli. Dalla sequenza di FFT si può individuare ogni fotogramma come la prima dopo un taglio / dissolvenza, o come una cornice tra tagli / svanisce. Quello che è importante è il tempo che intercorre tra ogni taglio / dissolvenza, indipendente dalle cornici numero tra di loro, che crea una firma o impronte digitali, che è in gran parte indipendente dal frame rate.

Alla luce di questa impronta digitale di un intero video produce dati che sono massicciamente più piccolo del video stesso. E 'anche una sequenza lineare di numeri, una semplice serie temporale di vettore, molto simile audio, e può essere analizzato utilizzando molti degli stessi strumenti.

Il primo strumento è quello di eseguire una correlazione, per determinare se il modello di tagli in una video è una stretta corrispondenza a quella di un altro video. Se ci sono differenze significative, quindi i video sono differenti. Se sono una stretta corrispondenza, quindi gli unici a pochi FFT dopo ogni taglio correlato hanno bisogno di essere confrontati per determinare se i telai sono abbastanza simili per essere un match.

Io non andrò in confronto di FFT 2D qui, dato che ci sono abbondanti riferimenti che fanno il lavoro di gran lunga meglio di me.

Nota: Non ci sono molte altre manipolazioni (al di là di una FFT 2D) che può essere applicato ai telai in bianco e nero per ottenere altre impronte digitali. Rappresentazioni di contenuto dell'immagine reale possono essere create estraendo i bordi interni dell'immagine (letteralmente come un'impronta digitale FBI), oppure sogliatura selettivamente l'immagine ed eseguendo un'operazione 'blobbing' (creazione di un elenco collegato di regione relativi descrittori). Monitoraggio l'evoluzione dei bordi e / o chiazze tra i fotogrammi può essere utilizzato non solo per generare liste di taglio, ma può anche essere usato per estrarre ulteriori caratteristiche di immagine di alto livello, che andrebbero persi utilizzando una FFT 2D.

abbiamo costruito una serie di algoritmi di confronto che dovrebbero essere molto veloce nel trovare non-match, e non richiedono troppo tempo per stabilire in modo definitivo le partite. Ahimè, avendo algoritmi non si fanno una soluzione! Dobbiamo considerare diversi problemi relativi a come dovrebbero essere meglio implementati questi algoritmi.

In primo luogo, non si vuole aprire e leggere ogni file video qualsiasi più volte del necessario, altrimenti la CPU potrebbe stallo in attesa dei dati dal disco. Noi, inoltre, non vogliamo leggere oltre in un file del necessario, anche se non vogliamo smettere di leggere troppo presto e potenzialmente perdere una partita dopo. Se l'informazione che caratterizza ogni video da salvare, o dovrebbe essere ricalcolato quando necessario? Affrontare questi temi consentirà un sistema di confronto di video efficiente ed efficace per essere sviluppato, testato e distribuito.

Abbiamo dimostrato che è possibile confrontare i video con qualche speranza di trovare partite in condizioni molto variabili, con efficienza computazionale.

Il resto è stato lasciato come esercizio per il lettore. ; ^)

Answer 2

Grande domanda! Solo il test dirà quale di questi fattori saranno i migliori indicatori. Alcune idee:

• sviluppo del bitrate nel tempo con lo stesso codec VBR: Suoni molto-CPU ma immagino che avrebbe dato grandi risultati. analisi audio sembra che darebbe risultati simili con meno lavoro.
• primo e l'ultimo fotogramma di analisi d'immagine: Non sarebbe il 50% di questi sarebbe il nero? Un'idea migliore potrebbe essere quella di utilizzare il telaio molto centrale, ma non vorrei contare su questa tecnica di essere affidabile.
• statistiche Usa bayesiana di segnare i fattori rendono i migliori contributi a un riscontro positivo. Ciò potrebbe essere fatto in fase di sperimentazione per eliminare i paragoni inutili e costosi.
• convincere gli utenti a dare una mano! Lascia gruppo di utenti insieme duplica che trovano. Essi votano quello con la migliore qualità e che si agirà come la versione primario / ufficiale all'interno del gruppo.
• Inizia con i paragoni più semplici e aggiungere test più sofisticati quando trovi le carenze di quelli semplici. la durata del video sarebbe una buona per cominciare, allora forse alcune analisi audio rudimentale, e il tuo lavoro da lì.

Answer 3

Basta provare questo prodotto - Duplicate Video Search (. Es Visual Search Pony), che può trovare i file video duplicati di vario bitrate, formati, risoluzioni e ecc.

Ad esempio, la stella-wars.avi (640x480 H.264) e sw.mpg (1280x720 MPEG) sarà rilevato come i duplicati, nel caso in cui entrambi sono copie di un grande film -. Star Wars

Come per il loro sito web, il prodotto utilizza alcuni video di impronte digitali, tecniche come fotogrammi chiave exctraction o si dovrebbe occupare. in questo modo, si deve essere indipendente dalla codifica video, la risoluzione, la qualità, il bitrate ed ecc.