Por Benjamín Bustos, profesor del Departamento de Ciencias de la Computación, FCFM, U. de Chile.

Un problema muy interesante relacionado con la búsqueda por similitud en el área multimedia es el de detección de copias de vídeo. El problema, en palabras simples, es el siguiente: se tiene una colección grande de vídeos (pueden ser películas, series de televisión, vídeos bajados de Internet, etc.) y dado un nuevo vídeo, se pide encontrar si: a) el vídeo corresponde a un vídeo de la colección (es decir, es una copia íntegra) b) un segmento del vídeo corresponde a un segmento de algún vídeo de la colección (copia parcial), o c) el vídeo no es copia (ni total ni parcial) de ningún vídeo de la colección.

El problema se puede complicar de muchísimas formas, por ejemplo agregándole ruido al vídeo que uno quiere buscar; agregándole subtítulos o bordes negros horizontales o verticales; cambiando el contraste/brillo de la imagen; invirtiendo la imagen (como se vería en un espejo); desenfocando las imágenes o agregando un Picture-In-Picture a la imagen (que de alguna forma hay que ignorar), o grabando el video original mientras éste se reproduce en el televisor o en el cine (conocido como screening o camcording) ¡y aún así uno espera poder encontrarlo! El problema general es tan complejo que es tema de investigación en la actualidad. Incluso, hay una competencia de detección de vídeos organizada por la NIST en donde participan equipos de todo el mundo. En esta columna me voy a remitir a un solo aspecto fundamental de este problema: ¿cuánto tiempo tomaría encontrar una copia, o descartar que un vídeo sea copia?

Un vídeo se compone de frames, que son imágenes que se van mostrando una tras otra. Típicamente un vídeo muestra 24-25 frames por segundo, lo cual da la sensación de continuidad y movimiento. Una forma de poder detectar si un vídeo es copia de otro es comparar todos los frames de un vídeo con todos los frames del otro (suponiendo que se dispone de un buen algoritmo de comparación de imágenes que nos diga si dos frames se parecen o no). Si varios frames consecutivos de ambos vídeos se parecen mucho, es muy probable que se trate entonces de una copia. Supongamos que los vídeos son películas, con una duración típica de 90 minutos. Eso nos da que un vídeo tiene 129.600 frames, por lo que si se comparan todos los frames de un vídeo contra todos los de otro vídeo habría que realizar algo así como 16 mil millones de comparaciones, ¡lo que tomaría mucho tiempo! Incluso, considerando que los computadores son muy eficientes haciendo cálculos, si suponemos que nuestro computador es capaz de hacer una comparación de frames en una millonésima de segundo, en total le tomaría 16.000 segundos en determinar si el vídeo era o no copia de otro (poco menos de 4 horas y media). Si bien esto puede parecer razonable, en realidad es lento: si la colección contiene 1.000 vídeos, con este método tomaría más de cinco meses revisar todos los vídeos de la colección, lo cual es definitivamente muy lento, y esto sólo para encontrar si un solo vídeo es copia de una colección, imagínense si uno tuviera un listado largo de vídeos a verificar… Resulta evidente entonces que este algoritmo de “fuerza bruta” que compara todo contra todo es demasiado lento para el problema de la detección de copias de vídeo, y por lo tanto es vital recurrir a algoritmos de búsqueda eficientes que nos eviten caer en la “fuerza bruta”.

Un método relativamente sencillo para evitar comparar frames en forma innecesaria se basa en el denominado “indexamiento basado en pivotes”. Supongamos que d() es una función que me permite comparar frames (funciona como una distancia: 0 significa que son iguales, y mientras más lejos estén más distintos son). Se escoge un frame p (de “pivote”) del vídeo de la colección, y ahora se necesita saber si se deben comparar dos frames a y b. A uno le interesa compararlos sólo si a y b están cerca (se parecen), si están lejos entonces no vale la pena hacer el cálculo y se puede ahorrar dicho tiempo. Para esto se ocupa el pivote, que permite estimar la distancia entre a y b como cota=|d(a,p)-d(p,b)| (ver Figura). Si la cota de distancia es un valor alto, entonces a y b no pueden ser muy parecidos. Note que obtener la cota implica realizar una simple resta, mucho menos costoso que calcular d(a,b).

“Detalles técnicos para los interesados: para que la cota sea válida, la función d() debe cumplir con la propiedad de ser métrica, en particular debe satisfacer la desigualdad triangular.”

Esta idea se puede generalizar y usar varios pivotes, lo que mejora aún más la eficiencia. ¿Cuánto se gana? Al menos en nuestro sistema de detección de copias de vídeo se gana bastante en eficiencia: el sistema funciona unas 300 veces más rápido comparado con la fuerza bruta, lo que aplicado al ejemplo permitiría bajar el tiempo de procesamiento de meses a horas. Hay por supuesto otras optimizaciones que se pueden hacer. Por ejemplo no es necesario procesar todos los frames de un vídeo, basta con escoger un frame representativo por segundo de vídeo para obtener buenos resultados, lo que permite reducir el tiempo de procesamiento aún más (a minutos).

La detección de copias de vídeo es un sólo un ejemplo donde se puede utilizar el indexamiento basado en pivotes. Es una técnica sencilla que puede acelerar la resolución problema en donde se requiera buscar por similitud en colecciones masivas de datos en forma eficiente.