Esto 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 la extracción de los datos necesarios de cada video para cualquier métrica de comparación que se vaya a utilizar. 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 dos primeros 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 debemos usarlo primero, incluso antes de comenzar a confirmar una coincidencia.
Para caracterizar la base de datos Primero, realice un muestreo y una coincidencia manual para estimar el grado de coincidencia dentro de la base de datos. Este experimento debe mostrar cómo los videos redundantes se "agruparon": si un video dado tenía una coincidencia, ¿qué tan probable era tener más de una coincidencia? ? ¿Qué porcentaje de todos los partidos también formaban parte de una coincidencia múltiple? Este proceso generará 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 I asumirá que los partidos son relativamente raros. Después de todo, si hay muchos partidos, el video os se "agruparán", haciendo que la base de datos sea más pequeña y simplificando el problema. Supongamos que el problema se mantiene lo más difícil posible.
Recomendaría un enfoque de categorización multinivel, donde construiríamos una secuencia de algoritmos que repetidamente realizan 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 maneras: False Positive (los videos que no coinciden son mislabled como coincidentes) y False Negative (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.
Como 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 "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é pasa con 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 "lo suficientemente diferentes" (si se prueban), lo que significa que no podemos posarnos mirando los datos de video 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.
Como 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 también tolerante al ruido y/o datos añadidos perdido como parte de cambiar 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 cierto grado de recorte y/o llenado, como ocurriría a partir de un cambio entre 4: 3 y 16: 9 proporciones (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 toda una 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 mismas se pueden descomponer 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 tales 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 utilizaré es en lugar de decodificar marcos por completo, en cambio los decodificaré solo en canales de componentes separados (HSV, HSL, YUV, lo que sea) y no hasta el framebuffer RGB (a menos que eso sea 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.
A continuación, 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 coincidir? 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 simple (pero lento) camino a seguir 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 hemos transformado las tramas monocromas en un dominio más pequeño y útil, aún debemos realizar la comparación con otra transmisión de ese tipo desde 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 mira la secuencia de cuadros FFT, notará 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.
Al tomar esta huella digital de un video completo se obtienen datos que son enormemente 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 marcos monocromos 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 deben ser muy rápidos para encontrar coincidencias y que no requieren 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 ha dejado como un ejercicio para el lector. ; ^)
+1 para una pregunta muy interesante, pero esto definitivamente necesita etiquetas diferentes. PHP no será el idioma elegido aquí. –
Estoy de acuerdo @Pekka. – Josh
Estoy de acuerdo también: No sé por qué lo puse ahí: D –