La búsqueda de archivos de vídeo duplicados por la base de datos (millones), la huella digital? ¿Reconocimiento de patrones?

Question

En el siguiente escenario:

Tengo un proyecto que tiene un catálogo de momento, unos diez mil archivos de vídeo, el número va a aumentar de forma espectacular.

Sin embargo muchos de ellos están duplicados. Con cada archivo de vídeo que he asociado la información semántica y descriptivo que quiero fusionar duplicados a achive mejores resultados para cada uno.

Ahora necesito algún tipo de procedimiento en el que los metadatos de índice en una base de datos, y cada vez que un nuevo video entra en el catálogo se calcula y se compara con la base de datos en los mismos datos.

El problema es que los vídeos no son copias exactas. Pueden tener diferentes calidades, se amby recortada, con marcas de agua o tener una secuela / precuela. O están cortadas al principio y / o al final.

Por desgracia, la mejor es la comparación más CPU y memoria intensiva se pone tan planeo en la aplicación de varias capas de comparación que comienzan con muy graciosa pero comparación rápida (lengh de vídeo maby con una tolerancia del 10%) y terminan con la comparación definitiva que decide si es realmente un duplicado (que sería un voto de la comunidad).

Así como tengo una comunidad para verificar los resultados es suficiente para entregar "buenas conjeturas" con una baja relación señorita.

Así que ahora mi pregunta es ¿qué capas pueden ustedes pensar o tiene un mejor enfoque?

No me importa el esfuerzo de crear los metadatos, tengo suficientes esclavos para hacer eso. Sólo la comparación debe ser rápido. Así que si ayuda que puedo convertir el vídeo 100 veces, así ...

Estas son mis ideas actuales:

• duración de vídeo (segundos)

• primero y último análisis marco de imagen

Me sería volver a muestrear la imagen a un tamaño de miniatura y obtener los valores medios rgb continuación serializar píxel a píxel si el color en este pixel es mayor / menor que el promedio representado por 0 o 1. Así que tengo una cadena binaria que me puede almacenar en MySQL y hacer un poco de suma booleana (soportado por MySQL internamente) y contar los bits uneval restantes (así apoyado internamente, que sería entonces la distancia Levenshtein de las cuerdas binario a)

• developement de la tasa de bits en el tiempo con la misma vbr codec

Me transcodificar el vídeo en un archivo de vídeo VBR con la misma configuración. a continuación, me gustaría ver la tasa de bits en ciertos puntos de tiempo (porcentaje del video completo o segundos absolutos .. entonces sería solamente analizar una parte del video). lo mismo que con la imagen. Iif la tasa de bits es mayor a la media de su 1 persona su 0. hacemos una cadena binaria y la almacenamos en db y calculamos la distancia Levenshtein tarde

• análisis el audio (bitrate y decibelios varaition con el tiempo al igual que la tasa de bits del vídeo)

• análisis fotograma clave

Imagen comarision al igual que el primero y el último cuadro, pero en las posiciones de fotogramas clave? Volveremos a utilizar los mismos archivos de código fuente que utilizamos para calcluiations tasa de bits, porque los fotogramas clave son pesados ??dependían del códec y la configuración.

• Desarrollos de color con el tiempo

Tal vez Tomemos una o más áreas / píxeles dentro de la imagen y ver cómo se develope lo largo del tiempo. Así el cambio abov / debajo de la media. negro / blanco sería suficiente pienso.

• presente las sugerencias al usuario para su aprobación final ...

O voy el camino completamente equivocado? Creo que no puedo ser el primero en tener este problema, pero no he tenido ninguna suerte para encontrar soluciones.

Answer 1

Este es un gran problema, por lo que he elegido escribir una larga respuesta en lugar de tratar de descomponer el problema en partes que pueden ser más fáciles de resolver.

Es importante que las comparaciones se realizaron utilizando los recursos informáticos y el tiempo disponible: Dudo una solución que lleva meses de ejecución será de gran utilidad en una base de datos de imágenes dinámicas. Y el tamaño de la base de datos probablemente hace que el uso de los recursos informáticos en nube inviable. Así que realmente se preocupan por el costo local de cada comparación en varios dominios diferentes:. 1) de almacenamiento de datos, 2) los recursos informáticos y de tiempo 3)

Uno de los costos clave a considerar es la de extraer los datos necesarios de cada vídeo por cualquier métricas de comparación se van a utilizar. Una vez que los datos extraídos se encuentra disponible, entonces el costo de llevar a cabo una comparación debe ser considerado. Por último, las comparaciones necesarias para que coincida con todos los vídeos entre sí se deben realizar.

El costo de los dos primeros pasos es O (1) sobre el número de videos. El coste de la última etapa debe ser peor que O (1), potencialmente mucho peor. Por lo que nuestro objetivo principal debe ser reducir al mínimo los costos de la última etapa, incluso si esto significa la adición de muchos de los primeros, pasos simples.

Los algoritmos óptimos para este proceso dependerá en gran medida de las características de la base de datos, el nivel al que existan partidos individuales y múltiples. Si el 100% de los videos que coincida con alguna otra de vídeo, a continuación, vamos a querer minimizar el costo de una persona compatible. Sin embargo, el caso más probable es que partidos serán raros, por lo que vamos a querer minimizar el costo de un partido sin éxito. Es decir, si hay una manera rápida y sucia que decir "estos dos videos no pueden ser partidos, entonces debemos utilizar por primera vez, sin siquiera haber empezado a confirmar un partido.

Para caracterizar la base de datos, primero hacer algunas de muestreo y de la mano de coincidencia a estimnate el grado de coincidencia dentro de la base de datos. Este experimento debe mostrar cómo los vídeos redundantes "agrupados": Si un vídeo determinado tuvo un partido, la probabilidad de que se tenga más de un solo partido? ¿Qué porcentaje de todos los partidos eran también parte de una coincidencia múltiple? Este proceso dará lugar a un 'modelo' de la base de datos (una distribución estadística) que se utiliza para ayudar algoritmo de selección y ajustar el sistema.

En el futuro voy a asumir partidos son relativamente raros. Después de todo, si hay un montón de partidos, los vídeos se "agrupan", haciendo efectiva la base de datos más pequeña, y con lo que el problema más sencillo. Vamos a suponer que las estancias de problemas tan duro como sea posible.

, abogo por un enfoque de categorización de varios niveles, donde nos gustaría construir una secuencia de algoritmos que realizan repetidamente la decisión binaria de "estos dos videos no coinciden" / "estos dos videos, posiblemente, puede igualar". Sólo el último algoritmo en las necesidades de la cadena de salida a la respuesta "Estos dos vídeos corresponden."

Clasificación / algoritmos de correspondencia puede faltar en una o ambas de dos maneras: Falso Positivo (vídeos no coincidentes se mislabled como coincidente) y falsos negativos (se encontraron videos están mal etiquetados como no coincidente). Cada una de estas decisiones equivocadas tiene un rango de probabilidades asociadas con ella, y se desea minimizar ambos.

Dado que estamos construyendo un oleoducto algoritmo, queremos algoritmos que son muy buenos en la identificación de los no partidos sin error, lo que significa que deben tener una muy baja tasa de falso rechazo, y no les importa mucho acerca de la tasa de falso Aceptar. Por ejemplo, el clon de Weird Al de un video de aspecto y contenido muy parecido al original, y puede no ser capaz de demostrar que no es una coincidencia con el original hasta más tarde en la tubería algoritmo.

El más simple, más rápido, la mayoría de los algoritmos fiables se debe ejecutar en primer lugar, ya que la abrumadora mayoría de las pruebas dará lugar a la "no coinciden" número. La comprobación más simple sería buscar archivos idénticos dentro de la base de datos, algo hecho por muchas utilidades de sistema de archivos y bases de datos de mantenimiento rápido y sencillo.Después de ejecutar este análisis, podemos asumir que en realidad se necesita abrir y leer los archivos de vídeo para detectar diferencias.

Desde la comparación de vídeo es relativamente difícil, vamos a empezar con el audio. Piense en la base de datos como una primera colección de MP3 que puede contener duplicados. Después de todo, si conseguimos un buen partido de audio, es muy probable que tengamos un partido de vídeo, y viceversa. Podemos decir con seguridad que el audio es un representante 'justo' para el vídeo. Afortunadamente, una búsqueda rápida en la web rendirá muchos paquetes de huellas dactilares y la comparación de audio que son fiable, rápido y madurar. tendría que ser generado para cada vídeo en la base de datos de huellas digitales de audio al. Videos que carecen de una pista de audio caerían automáticamente en el "podría coincidir" conjunto.

Pero hay un 'Gotcha' aquí: ¿Qué pasa con la voz en off? Si un vídeo determinado se codifica dos veces, con y sin una voz en off, que son un partido o no? ¿Qué pasa con el audio en francés vs el Español o Inglés? Si todos éstos deben ser considerados como un partido, entonces puede ser necesario omitir las pruebas de audio.

En este punto, sabemos que las entradas del sistema de archivos son "suficientemente diferentes", y sabemos que las pistas de audio son todos "lo suficientemente diferentes" (si es probado), lo que significa que no podemos postergar mirar los datos de vídeo de cualquier más. Afortunadamente, esto debería ser necesario hacer sólo una pequeña fracción de la base de datos de vídeo, por lo que puede tolerar un cierto coste. Al igual que antes, todavía a querer primer intento para eliminar rápidamente los no más partidos antes de tratar de etiquetar positivamente un partido.

Dado que tenemos que tener cambios de resolución en cuenta (por ejemplo, de 1080p para iPod), vamos a necesitar una forma de información de vídeo caracterizan a que no sólo es independiente de la resolución, pero también tolerante con el ruido añadido y / o datos perdidos como parte de cambiar la resolución. Debemos tolerar cambios de velocidad de cuadro (por ejemplo, de 24 fps de una película a 30 fps de vídeo). También hay cambios de relación de aspecto a considerar, tales como a partir de 4: 3 NTSC a 16: 9 HD. Nos gustaría manejar los cambios de espacio de color, como de color a blanco y negro.

Luego están transformaciones que afectan a todos estos a la vez, como la transcodificación entre HD y PAL, que puede afectar simultáneamente de espacio de color,-velocidad de cuadro, relación de aspecto, y la resolución. La caracterización también debe ser tolerante con algún grado de cultivo y / o relleno, tal como sucedería de una parte posterior del interruptor y vuelta entre 4: 3 y 16: 9 relaciones de aspecto (Letterboxing, pero no pan & scan). También hay que manejar videos que han sido truncados, tales como la eliminación de los créditos del final de una película de la característica. Y, obviamente, también hay que manejar las diferencias creadas por diferentes codificadores que fueron alimentados con una secuencia de vídeo idénticas.

Esa es una lista! Vamos a considerar algunas cosas que pueden optar por no dar cuenta de: Sospecho que es bien fracasar para encontrar una coincidencia cuando la imagen deformación está presente, a pesar del hecho de que la deformación anamórfico no es infrecuente, especialmente en películas de 35 mm de pantalla ancha que estaban directamente escaneada sin reconstrucción anamórfico (personas de alto-flacos). También podemos elegir a fallar cuando las grandes marcas de agua están presentes en el centro de la trama, aunque vamos a querer tolerar pequeñas marcas de agua en las esquinas. Y, por último, es bien fracasar para que coincida con los videos que han sido distorsionadas temporal o espacialmente volteado, como cuando se trata de una cámara lenta de la otra, o si se ha volteado de izquierda a derecha.

¿Tiene que casi cubre el espacio de vídeo? Es de esperar que está claro por qué es importante comenzar con el sistema de archivos y el audio! Eso es, en primer lugar pensar en su base de datos más como una colección de MP3 antes de considerar como una colección de vídeo.

Sin hacer caso del audio, vídeo es sólo una secuencia ordenada de las imágenes fijas. Así que en realidad estamos buscando uno o más algoritmos de comparación de imágenes combinados con uno o más algoritmos de comparación de series de tiempo. Esto podría ser o bien pares de algoritmos separados (caracterísrize cada trama, entonces caracterizar la secuencia de tramas), o puede ser combinado en un único algoritmo (vistazo a las diferencias entre cuadros).

Las imágenes en sí se puede descomponer aún más, en una imagen 'estructural' blanco y negro y un color 'superposición'. Creo que podemos ignorar la información de color, si es computacionalmente conveniente hacerlo.

A partir de lo anterior, puede sonar como que he asumido que tendremos que descifrar completamente un video con el fin de realizar comparaciones sobre el mismo. Eso no es necesariamente el caso, aunque la comparación de los datos codificados tiene muchas dificultades que limitan su utilidad. La única excepción a esto es importante para codificaciones de video a nivel de objeto, tales como MP4, donde se han realizado comparaciones múltiples cuadros de muy alto nivel. Por desgracia, las comparaciones entre objetos corrientes MP4 no ha visto mucha investigación, y estoy al tanto de ningún paquete capaces de realizar esta función. Pero si usted encuentra uno, utilizarlo!

La mayoría de los otros flujos de vídeo digitales utilizan esquemas de codificación tales como MPEG2, Quicktime, o algo similar. Estos esquemas utilizan todo el concepto de fotogramas clave y marcos de diferencia, aunque cada uno implementa de manera diferente. Cuando diferentes vídeos están siendo comparados (los que no son del mismo tamaño), es poco probable que los fotogramas clave y marcos de diferencia coincidirá con cualquier grado útil. Sin embargo, esto no significa que sea imposible, y existen paquetes que intentan extraer información útil de tales corrientes y sin realizar la decodificación completa. Si usted encuentra uno que es rápido, puede caer en un "¿por qué no intentarlo" categoría de pruebas.

El único truco que utilizaremos es lugar de decodificación de marcos por completo, yo en cambio decodificar únicamente en canales separados de componentes (HSV, HSL, YUV, lo que sea) y no todo el camino al uso de este dispositivo RGB (a menos que eso es lo que ha codificado , por supuesto). A partir de aquí, yo creo siguiente (color) marcos de crominancia luminancia separada y lo que las comparaciones se pueden realizar en otros ámbitos relacionados. La decodificación de todo el camino a un framebuffer RGB puede introducir errores que pueden hacer que la búsqueda de coincidencias más difícil.

A continuación, me gustaría descartar la información de color. Desde un video en blanco y negro debe coincidir con su color original, simplemente no se preocupan por el color!

¿Cómo puede la secuencia resultante de cuadros monocromos mejores compararse con otra secuencia que puede parecer muy diferentes, y aún así, posiblemente, puede ser un partido? Ha habido, literalmente, décadas de investigación en esta área, muchos de ellos clasifican en "detección partido invariante en escala". Desafortunadamente, muy poco de esta investigación se ha aplicado directamente a la determinación de cuándo vídeos hacen o no se correspondan.

Para nuestros propósitos, podemos abordar este tema desde varias direcciones. En primer lugar, hay que saber por nosotros mismos lo que es y no es una coincidencia en el dominio monocromo. Por ejemplo, no se preocupan por las diferencias a nivel de píxel, ya que incluso si dos se encontraron videos-pero-diferente tenían la misma resolución, hay que tolerar un cierto nivel de ruido debido a cosas como las diferencias de codificador.

Un simple (pero lento) camino a seguir es transformar cada imagen en una forma que es independiente tanto de resolución y relación de aspecto. Un tal transformación es en el dominio de la frecuencia espacial, y la FFT 2D es ideal para esto. Después de desechar el componente imaginario, el componente real se puede truncar a altas frecuencias para eliminar el ruido y a bajas frecuencias para eliminar los efectos de relación de aspecto, a continuación, normalizado a una escala estándar eliminar las diferencias de resolución. Las miradas resultantes de datos como una pequeña extraña imagen que puede ser comparado directamente a través de secuencias de vídeo.

Hay muchas otras estrategias posibles de transformación del marco, muchos mucho más eficiente que la FFT, y una búsqueda de la literatura debe resaltar ellos. Por desgracia, no conozco pocos que se han implementado en bibliotecas de software que son tan fáciles de usar como la FFT.

Una vez que hemos transformado el monocromomarcos en un dominio más pequeño y más útil, que todavía tienen que realizar la comparación con otro tal corriente de otro vídeo. Y que el video es casi seguro que no será un partido de cuadro a cuadro, por lo que una simple comparación se tienen que fallar. Necesitamos una comparación que tendrá en cuenta las diferencias en el dominio del tiempo, incluyendo los marcos añadido / borrado y las diferencias en la velocidad de fotogramas.

Si nos fijamos en la secuencia de fotogramas de FFT, se dará cuenta de un comportamiento muy distinto. se desvanece de la escena son abruptos y extremadamente fácil de detectar, recortes también se pueden distinguir, y normalmente hay sólo cambios lentos visto en la FFT entre los cortes. A partir de la secuencia de FFT podemos etiquetar cada trama como siendo el primero después de un corte / fade, o como un marco entre cortes / desvanece. Lo que es importante es el tiempo entre cada corte / fade, independientemente de los fotogramas de números entre ellos, lo que crea una firma o huella digital que es en gran medida independiente de la velocidad de fotogramas.

Tomando esta huella digital de todo un vídeo produce datos que es enormemente más pequeño que el propio vídeo. También es una secuencia lineal de números, un simple vector de series de tiempo, al igual que audio, y se puede analizar utilizando muchas de las mismas herramientas.

La primera herramienta es llevar a cabo una correlación, para determinar si el patrón de cortes en una de vídeo es un partido cercano a la de otro video. Si hay diferencias significativas, a continuación, los videos son diferentes. Si son un partido cerrado, entonces los únicos unos FFT después de cada corte correlacionada necesitan ser comparados para determinar si las tramas son lo suficientemente similares como para ser una coincidencia.

No entraremos en la comparación de las FFT 2D aquí, ya que hay abundantes referencias que hacen el trabajo mucho mejor que pueda.

Nota: Hay muchas otras manipulaciones (más allá de una FFT 2D) que se puede aplicar a los marcos en blanco y negro para obtener huellas digitales adicionales. Representaciones del contenido de la imagen actual se pueden crear mediante la extracción de los bordes interiores de la imagen (literalmente como una huella digital FBI), o por umbralización selectivamente la imagen y realizar una operación de 'blobbing' (la creación de una lista enlazada de descriptores de región relacionados). El seguimiento de la evolución de los bordes y / o manchas entre los marcos se puede utilizar no sólo para generar listas de corte, pero también puede ser utilizado para extraer características de la imagen de alto nivel adicionales que se perderían usando una FFT 2D.

Hemos construido una secuencia de algoritmos de comparación que deberían ser muy rápido en la búsqueda de los no partidos, y no requiere demasiado tiempo para determinar de manera concluyente partidos. Por desgracia, tener algoritmos no hace un maquillaje solución! Debemos tener en cuenta varias cuestiones relacionadas con cómo deben ser implementadas mejor estos algoritmos.

En primer lugar, no quiero abrir y leer cada archivo de vídeo alguna más veces de lo necesario, de lo contrario la CPU podría estancar la espera de los datos del disco. Tampoco queremos seguir leyendo en un archivo de lo necesario, a pesar de que no queremos dejar de leer demasiado pronto y potencialmente perder un partido después. En caso de que la información que caracteriza a cada vídeo salvarse, o debe ser recalculado cuando sea necesario? Para abordar estas cuestiones permitirá un sistema de comparación de vídeo eficiente y eficaz para ser desarrollado, probado y desplegado.

Hemos demostrado que es posible comparar los vídeos con alguna esperanza de encontrar coincidencias en condiciones muy variables, la eficiencia computacional.

El resto se ha dejado como ejercicio para el lector. ; ^)

Answer 2

Muy buena pregunta! Sólo las pruebas le dirá cuál de estos factores serán los mejores indicadores. Algunas ideas:

• desarrollo de la tasa de bits en el tiempo con el mismo códec VBR: Los sonidos muy intensivo de la CPU, pero me imagino que sería dar grandes resultados. análisis de audio parece que sería dar resultados similares con menos trabajo.
• nombre y análisis de imágenes último cuadro: ¿No 50% de éstos sería negro? Una mejor idea podría ser la de utilizar el marco mismo centro, pero no contaría con esta técnica es fiable.
• Uso estadísticas Bayesianas para registrar qué factores hacen que las mejores contribuciones a un resultado positivo. Esto podría hacerse en la fase de pruebas para eliminar a las comparaciones inútiles y costosas.
• Mostrar usuarios para ayudar! Que grupo de usuarios en conjunto duplica que encuentran. Votan en el que tiene la mejor calidad y que uno actuará como la versión principal / oficial dentro del grupo.
• Inicio de las comparaciones más fáciles y añadir pruebas más sofisticadas cuando encuentre las deficiencias de los sencillos. la duración del vídeo sería una buena para empezar, tal vez algunos análisis de audio a continuación, rudimentaria, y su forma de trabajo a partir de ahí.

Answer 3

Solo trata este producto - Duplicar Videos Búsqueda (Ex. Pony búsqueda visual), que se puede encontrar archivos de vídeo de varios duplicados velocidades de bit, resoluciones y formatos, etc.

Por ejemplo, se detectará el wars.avi-estrella (640x480 H.264) y sw.mpg (1280x720 MPEG) como duplicados, en caso de que dos de ellos son copias de una gran película -. Star Wars

De acuerdo con su página web, el producto utiliza algunas técnicas de vídeo de huellas dactilares, como key-frames exctraction o algo bajo. de esta manera, hacer ser independiente de la codificación de vídeo, resolución, calidad, velocidad de bits y etc.