language agnostic - una - Encontrar archivos de video duplicados por base de datos(millones), huella digital? ¿Reconocimiento de patrones?
eliminar videos duplicados (3)
Este es un gran problema, así que he elegido escribir una respuesta bastante larga para tratar de descomponer el problema en partes que pueden ser más fáciles de resolver.
Es importante que las comparaciones se realicen utilizando los recursos informáticos y de tiempo disponibles: dudo que una solución que lleve meses ejecutar sea muy útil en una base de datos dinámica de video. Y el tamaño de la base de datos probablemente hace que el uso de los recursos de computación en la nube sea inviable. Entonces, realmente nos importa el costo local de cada comparación en varios dominios diferentes: 1) almacenamiento de datos, 2) recursos informáticos, y 3) tiempo.
Un costo clave a considerar es extraer los datos necesarios de cada video para cualquier métrica de comparación que deba usarse. Una vez que los datos extraídos están disponibles, se debe considerar el costo de realizar una comparación. Finalmente, se deben realizar las comparaciones necesarias para hacer coincidir todos los videos entre sí.
El costo de los primeros dos pasos es O (1) en la cantidad de videos. El costo del último paso debe ser peor que O (1), potencialmente mucho peor. Por lo tanto, nuestro objetivo principal debe ser minimizar los costos del último paso, incluso si eso significa agregar muchos pasos iniciales simples.
Los algoritmos óptimos para este proceso dependerán en gran medida de las características de la base de datos, el nivel en el que existen coincidencias únicas y múltiples. Si el 100% de los videos coinciden con algún otro video, entonces querremos minimizar el costo de una coincidencia exitosa. Sin embargo, lo más probable es que las coincidencias sean raras, por lo que querremos minimizar el costo de una coincidencia fallida. Es decir, si hay una manera rápida y sucia de decir "estos dos videos no pueden ser coincidencias", entonces deberíamos usarlo primero, incluso antes de comenzar a confirmar una coincidencia.
Para caracterizar la base de datos, primero haga un muestreo y ajuste manual para estimar el grado de coincidencia dentro de la base de datos. Este experimento debería mostrar cómo los videos redundantes se "agruparon": si un video dado tenía una coincidencia, ¿qué posibilidades había de tener más de una coincidencia? ¿Qué porcentaje de todos los partidos también fueron parte de una partida múltiple? Este proceso producirá un "modelo" de la base de datos (una distribución estadística) que se utilizará para ayudar a la selección del algoritmo y ajustar el sistema.
En el futuro, supongo que los partidos son relativamente raros. Después de todo, si hay muchas coincidencias, los videos se "agruparán", reduciendo de hecho la base de datos y simplificando el problema. Supongamos que el problema se mantiene lo más difícil posible.
Yo recomendaría un enfoque de categorización multinivel, donde construiríamos una secuencia de algoritmos que repetidamente realizaría la decisión binaria de "estos dos videos no coinciden" / "estos dos videos posiblemente coincidan". Solo el último algoritmo de la cadena debe emitir la respuesta "Estos dos videos coinciden".
Los algoritmos de clasificación / coincidencia pueden fallar de una o dos formas: Falso positivo (los videos que no coinciden son desajustables como coincidencia) y False Negativo (los videos que coinciden son etiquetados erróneamente como no coincidentes). Cada una de estas decisiones erróneas tiene un rango de probabilidades asociadas, y queremos minimizar ambas.
Dado que estamos construyendo una canalización de algoritmos, queremos algoritmos que sean muy buenos para identificar no coincidencias sin error, lo que significa que deben tener una tasa de rechazo falso extremadamente baja, y no nos importa demasiado la tasa de aceptación falsa. Por ejemplo, el clon de un video de Wierd Al puede verse y parecerse mucho al original, y es posible que no podamos mostrar que no coincide con el original hasta más adelante en la canalización del algoritmo.
Los algoritmos más simples, rápidos y confiables se deben ejecutar primero, ya que la inmensa mayoría de las pruebas producirán el resultado de "no coinciden". La comprobación más simple sería buscar archivos idénticos dentro de la base de datos, algo hecho por muchos sistemas de archivos rápidos y simples y utilidades de mantenimiento de bases de datos. Después de ejecutar este escaneo, podemos suponer que realmente necesitaremos abrir y leer los archivos de video para detectar diferencias.
Como la comparación de video es relativamente difícil, comencemos con el audio. Piense en la base de datos como la primera que es una colección de MP3 que puede contener duplicados. Después de todo, si conseguimos una buena coincidencia de audio, es muy probable que tengamos una coincidencia de video, y viceversa. Podemos decir con seguridad que el audio es un representante ''justo'' para el video. Afortunadamente, una búsqueda rápida en Internet arrojará muchas huellas dactilares de audio y paquetes de comparación que son confiables, rápidos y maduros. La huella digital de audio necesitaría generarse para cada video en la base de datos. Los videos que carecen de una pista de audio caen automáticamente en el conjunto "podría corresponder".
Pero hay un "gotcha" aquí: ¿qué hay de las voces en off? Si un video determinado está codificado dos veces, con y sin una voz en off, ¿coinciden o no? ¿Qué pasa con el audio francés frente al español o el inglés? Si se debe considerar que todas estas cosas coinciden, es posible que sea necesario omitir las pruebas de audio.
En este punto, sabemos que las entradas del sistema de archivos son "lo suficientemente diferentes", y sabemos que las pistas de audio son todas "lo suficientemente diferentes" (si se prueban), lo que significa que no podemos dejar de mirar los datos de video por más tiempo. Afortunadamente, esto debería hacerse solo por una pequeña fracción de la base de datos de video, de modo que podamos tolerar algún costo. Al igual que antes, aún querremos primero tratar de eliminar rápidamente más no coincidencias antes de tratar de etiquetar positivamente un partido.
Dado que debemos tener en cuenta los cambios de resolución (por ejemplo, de 1080p a iPod), necesitaremos una manera de caracterizar la información de video que no solo sea independiente de la resolución, sino que también sea tolerante al ruido agregado y / o a la pérdida de datos como parte de cambiando la resolución. Debemos tolerar los cambios de velocidad de fotogramas (por ejemplo, de 24 fps de una película a 30 fps de video). También hay cambios en la relación de aspecto a considerar, como 4: 3 NTSC a 16: 9 HD. Quisiéramos manejar los cambios de espacio de color, como de color a monocromo.
Luego hay transformaciones que afectan a todos estos a la vez, como la transcodificación entre HD y PAL, que puede afectar simultáneamente el espacio de color, la velocidad de fotogramas, la relación de aspecto y la resolución. La caracterización también debe ser tolerante a algún grado de recorte y / o relleno, como sucedería a partir de un cambio de una relación de aspecto de 4: 3 a 16: 9 (letterboxing, pero no pan & scan). También debemos manejar los videos que se han truncado, como eliminar los créditos del final de una película. Y, obviamente, también debemos manejar las diferencias creadas por diferentes codificadores que fueron alimentados con una transmisión de video idéntica.
¡Esa es una buena lista! Consideremos algunas cosas que podemos elegir no tener en cuenta: sospecho que está bien no encontrar una coincidencia cuando hay deformación de imagen, a pesar del hecho de que la deformación anamórfica no es infrecuente, especialmente en las películas de pantalla panorámica de 35 mm que estaban directamente escaneada sin reconstrucción anamórfica (personas altas y flacas). También podemos optar por fallar cuando hay marcas de agua grandes en el centro del marco, aunque querremos tolerar marcas de agua más pequeñas en las esquinas. Y, por último, está bien que no coincida con los videos que se han distorsionado temporalmente o espaciado, como cuando uno es un slo-mo del otro, o se ha volteado de izquierda a derecha.
¿Eso cubre el espacio de video? Espero que esté claro por qué es importante comenzar con el sistema de archivos y el audio. Es decir, primero piense en su base de datos más como una colección de MP3 antes de considerarla como una colección de videos.
Ignorar el audio, el video es solo una secuencia ordenada de 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 temporales. Esto podría ser pares de algoritmos separados (caracterizar cada fotograma, luego caracterizar la secuencia de fotogramas), o podría fusionarse en un solo algoritmo (ver las diferencias entre fotogramas).
Las imágenes en sí mismas pueden descomponerse aún más, en una imagen "estructural" monocromática y una "superposición" de color. Creo que podemos ignorar la información de color de forma segura, si es conveniente hacerlo desde el punto de vista computacional.
De lo anterior, puede parecer que he asumido que tendremos que decodificar por completo un video para poder realizar comparaciones en él. Ese no es necesariamente el caso, aunque la comparación de datos codificados tiene muchas dificultades que limitan su utilidad. La única excepción significativa a esto es para las codificaciones de video a nivel de objetos como MP4, donde se han realizado comparaciones de fotogramas múltiples de muy alto nivel. Desafortunadamente, las comparaciones de objetos entre las transmisiones de MP4 no se han investigado mucho, y no tengo conocimiento de que ningún paquete pueda realizar esta función. ¡Pero si encuentras uno, úsalo!
La mayoría de las otras secuencias de video digital usan esquemas de codificación como MPEG2, Quicktime o algo similar. Todos estos esquemas utilizan el concepto de fotogramas clave y fotogramas diferenciados, aunque cada uno lo implementa de forma diferente. Cuando se comparan diferentes videos (que no son del mismo tamaño), es poco probable que los fotogramas clave y los cuadros de diferencia coincidan con cualquier grado útil. Sin embargo, esto no significa que sea imposible, y existen paquetes que intentan extraer información útil de dichas transmisiones sin realizar una descodificación completa. Si encuentra uno que sea rápido, puede caer en una categoría de pruebas "por qué no intentarlo".
El único truco que usaré es en lugar de decodificar por completo los marcos, en cambio los decodificaré solo en canales de componentes separados (HSV, HSL, YUV, lo que sea) y no todo el camino al framebuffer RGB (a menos que eso haya sido codificado, por supuesto ) A partir de aquí, crearé marcos de luminancia y crominancia (color) separados para que se puedan realizar comparaciones en dominios relacionados. La decodificación hasta un framebuffer RGB puede introducir errores que pueden dificultar la búsqueda de coincidencias.
Luego, descartaría la información de color. Como un video monocromático debe coincidir con el color original, ¡simplemente no nos importa el color!
¿Cómo se puede comparar mejor la secuencia resultante de fotogramas monocromáticos con otra secuencia que puede parecer muy diferente, pero que aún puede ser una coincidencia? Ha habido literalmente décadas de investigación en esta área, muchas de ellas clasificadas bajo "detección de coincidencia invariable de escala". Desafortunadamente, muy poco de esta investigación se ha aplicado directamente para determinar cuándo los videos coinciden o no.
Para nuestros propósitos, podemos abordar este problema desde varias direcciones. Primero, debemos saber por nosotros mismos qué es y qué no coincide en el dominio monocromático. Por ejemplo, no nos importan las diferencias de nivel de píxel, ya que incluso si dos videos coincidentes pero diferentes tienen la misma resolución, debemos tolerar cierto nivel de ruido debido a cosas como las diferencias del codificador.
Un camino sencillo (pero lento) es transformar cada imagen en una forma que es independiente tanto de la resolución como de la relación de aspecto. Una de estas transformaciones es en el dominio de frecuencia espacial, y la FFT 2D es ideal para esto. Después de descartar 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 la relación de aspecto, luego se normaliza a una escala estándar para eliminar las diferencias de resolución. Los datos resultantes se ven como una imagen pequeña e impar que se puede comparar directamente a través de las transmisiones de video.
Existen muchas otras posibles estrategias de transformación de trama, muchas mucho más eficientes que la FFT, y una búsqueda bibliográfica debe resaltarlas. Desafortunadamente, conozco algunos que se han implementado en bibliotecas de software que son tan fáciles de usar como la FFT.
Una vez que hayamos transformado los cuadros monocromáticos en un dominio más pequeño y útil, aún debemos realizar la comparación con otro flujo de ese otro video. Y es casi seguro que ese video no sea una coincidencia de fotograma a fotograma, por lo que una simple comparación fracasará. Necesitamos una comparación que tenga en cuenta las diferencias en el dominio del tiempo, incluidos los fotogramas añadidos / eliminados y las diferencias en la velocidad de fotogramas.
Si miras la secuencia de cuadros FFT, notarás un comportamiento muy distinto. Los desvanecimientos de escena son abruptos y extremadamente fáciles de detectar, los cortes también se pueden distinguir, y por lo general solo se observan cambios lentos en la FFT entre cortes. A partir de la secuencia de FFT, podemos etiquetar cada cuadro como el primero después de un corte / fundido, o como un cuadro entre cortes / fundidos. Lo importante es el tiempo entre cada corte / fundido, independiente de los marcos numéricos entre ellos, lo que crea una firma o huella digital que es en gran parte independiente de la velocidad de cuadros.
Tomar esta huella digital de un video completo produce datos que son masivamente más pequeños que el video en sí. También es una secuencia lineal de números, un simple vector de series temporales, muy parecido al audio, y puede analizarse utilizando muchas de las mismas herramientas.
La primera herramienta es realizar una correlación, para determinar si el patrón de cortes en un video es una coincidencia cercana a la de otro video. Si hay diferencias significativas, entonces los videos son diferentes. Si son una coincidencia cercana, entonces las únicas pocas FFT después de cada corte correlacionado deben ser comparadas para determinar si los marcos son lo suficientemente similares como para ser una coincidencia.
No entraré en la comparación de las FFT en 2D aquí, ya que hay abundantes referencias que hacen el trabajo mucho mejor que yo.
Nota: Hay muchas otras manipulaciones (más allá de una FFT 2D) que se pueden aplicar a cuadros monocromáticos para obtener huellas dactilares adicionales. Las representaciones del contenido real de la imagen pueden crearse extrayendo los bordes interiores de la imagen (literalmente como una huella dactilar del FBI), o seleccionando el umbral de la imagen y realizando una operación ''blobbing'' (creando una lista vinculada de descriptores de región relacionados). El seguimiento de la evolución de los bordes y / o blobs entre fotogramas se puede usar no solo para generar listas de cortes, sino que también se puede usar para extraer características de imágenes de alto nivel adicionales que se perderían utilizando una FFT 2D.
Hemos construido una secuencia de algoritmos de comparación que debe ser muy rápida para encontrar coincidencias y no requiere demasiado tiempo para determinar las coincidencias de manera concluyente. Por desgracia, tener algoritmos no hace una solución! Debemos considerar varios problemas relacionados con la mejor forma de implementar estos algoritmos.
En primer lugar, no queremos abrir y leer cada archivo de video más veces de las necesarias, de lo contrario, la CPU podría quedarse atascada en espera de los datos del disco. Tampoco queremos leer más de lo necesario en un archivo, aunque no queremos dejar de leer demasiado pronto y posiblemente perder un partido posterior. ¿Debería guardarse la información que caracteriza cada video, o debería ser recalculada cuando sea necesario? Abordar estos problemas permitirá desarrollar, probar y desplegar un sistema de comparación de video eficiente y efectivo.
Hemos demostrado que es posible comparar videos con la esperanza de encontrar coincidencias en condiciones muy variables, con eficiencia computacional.
El resto se dejó como un ejercicio para el lector. ; ^)
En el siguiente escenario:
Obtuve un proyecto con un catálogo de aproximadamente diez mil archivos de video, el número va a aumentar drásticamente.
Sin embargo, muchos de ellos son duplicados. Con cada archivo de video, tengo información semántica y descriptiva asociada a la que quiero unir duplicados para obtener mejores resultados para cada uno.
Ahora necesito algún tipo de procedimiento en el que indexe los metadatos en una base de datos, y cada vez que un nuevo video ingresa al catálogo, se calculan y contrastan los mismos datos en la base de datos.
El problema es que los videos no son duplicados exactos. Pueden tener diferente calidad, amby cropped, watermarked o tener una secuela / precuela. O se cortan al principio y / o al final.
Desafortunadamente, cuanto mejor sea la comparación, más memoria y memoria se necesitan, así que planeo implementar varias capas de comparación que comiencen con una comparación muy elegante pero rápida (maby video lengh con una tolerancia del 10%) y terminen con la comparación final que decide si es realmente un duplicado (eso sería un voto comunitario).
Entonces, como tengo una comunidad para verificar los resultados, basta con dar "buenas suposiciones" con una baja proporción de errores.
Así que ahora mi pregunta es ¿en qué capas pueden pensar ustedes o tienen un mejor enfoque?
No me importa el esfuerzo de crear los metadatos, tengo suficientes esclavos para hacer eso. Solo la comparación debe ser rápida. Entonces, si ayuda, puedo convertir el video 100 veces también ...
Estas son mis ideas actuales:
duración del video (segundos)
primer y último análisis de cuadro de cuadro
Volvería a muestrear la imagen a un tamaño de miniatura y obtendría los valores medios de rgb luego serializar píxeles por píxel si el color en este píxel es mayor / menor que el promedio representado por 0 o 1. Así que obtengo una cadena binaria que puedo almacenar en mysql y hacer una boolean bit-sum (soportada por mysql internamente) y contar los bits impares restantes (también soportados internamente, que serían entonces la distancia de Levenshtein de las cadenas de bian)
- Desarrollo de la tasa de bits en el tiempo con el mismo códec vbr
Transcodificaría el video en un archivo de video vbr con la misma configuración exacta. Luego, vería la tasa de bits en determinados momentos (porcentaje del video completado o segundos absolutos ... luego solo analizaríamos una parte del video). lo mismo que con la imagen. Si la tasa de bits es mayor, el promedio es 1 más es 0. hacemos una cadena binaria y la almacenamos en db y calculamos la distancia Levenshtein más tarde
análisis de audio (tasa de bits y variación de decibeles en el tiempo igual a la velocidad de bits del video)
análisis de fotogramas clave
Comarision de imagen al igual que el primer y último fotograma, pero en las posiciones de fotograma clave? Utilizaríamos los mismos archivos fuente que utilizamos para las calcuaciones de bitrate porque los fotogramas clave dependen mucho del códec y la configuración.
- desarrollo del color a lo largo del tiempo
Tal vez tomemos una o más áreas / píxeles dentro de la imagen y veamos cómo se desarrollan con el tiempo. También el cambio por encima / debajo del promedio. negro / blanco sería suficiente, creo.
- presentar las sugerencias al usuario para su aprobación final ...
¿O estoy yendo completamente mal? Creo que no puedo ser el primero en tener este problema, pero no he tenido suerte para encontrar soluciones.
Gran pregunta! Solo las pruebas indicarán cuáles de esos factores serán los mejores indicadores. Algunas ideas:
- Desarrollo de la tasa de bits a lo largo del tiempo con el mismo códec vbr: Suena muy intensivo en CPU, pero imagino que daría excelentes resultados. Parece que el análisis de audio daría resultados similares con menos trabajo.
- primer y último análisis de cuadro: ¿el 50% de estos no sería negro? Una mejor idea podría ser utilizar el cuadro medio, pero no confiaría en que esta técnica sea confiable.
- Use las estadísticas Bayesianas para registrar qué factores hacen las mejores contribuciones para una coincidencia positiva. Esto podría hacerse en la fase de prueba para descartar comparaciones inútiles y costosas.
- ¡Ayuda a los usuarios a ayudar! Permita que los usuarios agrupen los duplicados que encuentren. Votan en el que tiene la mejor calidad y que actuará como la versión principal / oficial dentro del grupo.
- Comience con las comparaciones más fáciles y agregue pruebas más sofisticadas cuando encuentre las deficiencias de las simples. La duración del video sería una buena para comenzar, luego tal vez un análisis de audio rudimentario, y siga subiendo desde allí.
Simplemente pruebe este producto: Duplicate Video Search (por ejemplo, Visual Search Pony), que puede encontrar archivos de video duplicados de varias velocidades de bits, formatos, resoluciones, etc.
Por ejemplo, star-wars.avi (640x480 H.264) y sw.mpg (1280x720 MPEG) se detectarán como duplicados, en caso de que ambos sean copias de una gran película: Star Wars.
Según su sitio web, el producto utiliza algunas técnicas de huellas dactilares de video, como la extracción de fotogramas clave o smth. así, sé independiente de la codificación de video, resolución, calidad, tasa de bits, etc.