Rubén Morcillo Díaz

Como ya se ha comentado antes, el proyecto fin de carrera «Extracción de características en vídeos digitales» de Antonio Sánchez Benavente permite obtener los vectores de características de TODOS los frames de un vídeo, no solo de los keyframes. Este proceso consiste en lo siguiente. Cada uno de los frames se divide en un número de partes iguales según una de las siguientes opciones.

A continuación, para cada una de esas partes, se calcula la media de color, pudiendo elegir entre una de las siguientes cinco medidas:

• La componente de color azul (B), donde Bi representa la componente B del píxel i:

• La componente de color verde (G), donde Gi representa la componente G del píxel i:

• La componente de color rojo (R), donde Ri representa la componente R del píxel i.

• La media de gris por banda, entendiéndose por banda, cada una de las componentes que constituyen un píxel (generalmente, BGR en imágenes en color). Se calcula aplicando la siguiente expresión:

• La media por bandas. Se calcula:

Donde n_canales hace referencia al número de canales por píxel (3, en el caso de vídeos en color y 1 en el caso de vídeos en blanco y negro).

El vector de características del frame estará formado por esos valores calculados para cada una de las partes en que se divide, ordenándolos tal y como se indica en la figura con las posibles divisiones del frame, por lo que el tamaño del vector será igual al número de divisiones.

De esta forma tenemos los vectores de todos los frames, pero nosotros sólo necesitamos los de los keyframes, por lo que es necesario conocer las distintas escenas del vídeo. El proyecto de Antonio también tiene un proceso para detectar los cambios de escena, que basicamente consiste en ir comparando los vectores de frames consecutivos, sin embargo, esta funcionalidad no era un objetivo principal del proyecto y por lo tanto no está demasiado pulida. Por ello se va a utlizar otro proyecto fin de carrera que si se centra en buscar los cambios de escena en un vídeo, se trata del proyecto “Detección del corte entre escenas para la clasificación de vídeos digitales” de Alberto Aparicio Ríos. Éste devuelve el número de los frames donde se producen dichos cambios, pero el proceso es bastante complejo y no vamos a entrar en detalles de su funcionamiento, aunque sí hay que especificar una serie de parámetros configurables de los que puede depender la eficacia del proceso. Estos son los parámetros:

• Salto entre frames: Indica la distancia que habrá entre cada par de imágenes comparadas para la detección de cortes. Cuanto mayor sea más rápido será la ejecución, pero quizá puede dar peores resultados.

• Radio de dilatación: Es el radio del rombo que dilatará los bordes de cada uno de los frames a comparar. Por hacer una semejanza, sería el grosor de las líneas de cada dibujo. Cuanto mayor sea más tardará la imagen y mayor será el porcentaje de acierto en las comparaciones, puesto que más blancas estarán ambas imágenes, aunque un valor excesivamente alto obtendrá similitudes entre imágenes que no son semejantes.

• Compensación de movimiento: Si se activa este parámetro se tratará de minimizar el impacto del movimiento de la cámara o de los personajes de tal forma que la comparación de un frame con el siguiente sea lo mejor posible, aunque haya habido desplazamientos. Es el proceso que más tiempo lleva, y por tanto solamente se recomienda su uso cuando haya claros movimientos de cámara o de los personajes, y que este movimiento suponga una gran parte del frame.

• Número de cuadrados: En caso de que se use compensación de movimiento, este parámetro indica el método de detección de movimiento a utilizar, pudiendo elegir entre un cuadrado grande central o cuatro cuadrados pequeños distribuidos por la imagen.

• Utilizar media y desviación estándar: Este parámetro trata de establecer el umbral para que un salto sea considerado corte o no. Para usar un umbral constante este parámetro estará desactivado y si se quiere que el umbral se adapte al video se activará, debiendo configurar los siguientes parámetros.

• Umbral de cambio de escena: Este parámetro se utiliza para establecer un umbral fijo para identificar los saltos. Es realmente difícil que un umbral pueda servir para muchos videos, pero sí que se podrá encontrar un umbral óptimo para cada video por separado.

• Media y desviación local: Si se ha escogido utilizar la media y la desviación estándar para determinar el umbral de cambio de escena, se tendrá ahora la opción de aplicarlo al vector completo o bien a una determinada ventana. En este caso, si está activado se aplicará a una ventana local, tomando especial importancia la escena actual, frente al video completo en caso de no marcar esta opción.

• Radio del entorno de media y desviación: Este parámetro nos indica cómo de grande será la ventana sobre la que se calculará la media y la desviación estándar. Cuanto más pequeña sea, más rápida será la ejecución, y cuanto más grande más relación guardará con el video.

• Calcular cambiantes como suma: A la hora de calcular el porcentaje de píxeles cambiantes se tienen dos alternativas. Se puede utilizar el máximo entre entrantes y salientes, o también la suma entre ambos. Si se utiliza la suma se potenciarán más las diferencias entre dos frames consecutivos, aunque puede dar peores resultados si el video tiene movimiento que no haya sido bien detectado, haciendo aún más grandes las pequeñas diferencias.

• Usar incrementos: Para calcular el porcentaje de píxeles cambiantes se debe tomar una segunda decisión. Bien se puede utilizar los porcentajes obtenidos en la comparación, o bien el incremento de dichos porcentajes. Si se utiliza el incremento de los mismos la identificación de los cortes se situará en aquellos saltos en que más cambia la imagen con respecto a la siguiente. La eficiencia temporal es la misma, pero los resultados, según las pruebas, serían mejores si se utilizan los incrementos, por lo que se recomienda su utilización.

• Mínimo de píxeles cambiantes en barrido: Un barrido será detectado cuando los píxeles están concentrados en un lateral de la imagen, y poco a poco van avanzando hacia el lateral contrario. No en cualquier caso que se cumpla esto habrá un barrido, es necesario establecer un mínimo de puntos cambiantes que deberán formar parte de dicho barrido, para descartar los frames aislados en los que haya cambios concentrados.

• Porcentaje de píxeles en la franja del barrido: Este parámetro sirve para cuantificar el porcentaje mínimo de píxeles que deberá contener la franja correspondiente al barrido. Si cualquiera de las cuatro mitades de la imagen concentra un número de píxeles mayor que el indicado en este porcentaje se estará ante un barrido. Por esto, se recomienda un porcentaje superior al 50%, ya que si es inferior, la otra mitad lo superará claramente. Si los barridos son muy rápidos, la franja que cambiará de una imagen a otra será más ancha que si son lentos. Cuanto más ancha sea la franja mayor número de píxeles contendrá, y por tanto, mayor porcentaje de cambiantes. Por tanto se debe establecer este parámetro de tal forma que se adapte a las velocidades de los barridos, si los hubiera.

• Separación mínima de barridos: La separación de barridos no es más que la distancia mínima que debe haber entre dos barridos distintos. Esto es necesario porque a menudo algunos frames del barrido son detectados como tal, pero otros no, quedando huecos en medio que se supone que no son barridos, pero es necesario unificarlos todos para tener uno solamente, desde su inicio a su fin, y distinguirlo, gracias a este parámetro, del resto de barridos.

¿Y como nos devuelven estos dos proyectos los vectores de características y los frames de cambio de escena? Pues cada uno genera un fichero de texto con esta información. El proyecto de Antonio para los vectores de características crea un fichero con una cabecera primero donde se especifica el nombre dle vídeo, el número total de frames, el tipo de división escogida y la media de color utilizada, y a continuación hay una línea de fichero para cada vector de características, en las que los valores estan separados por espacios. A continuación se muestra un ejemplo de fichero con una división de 3×3 y la media para la componente verde.

La salida del proyecto de Alberto Aparicio consiste en un fichero de texto donde se especifican primero los parámetros que se han utilizado para encontrar los saltos de escena, después las características del vídeo procesado, y a continuación una lista con los frames donde se producen dichos saltos. La siguiente figura muestra un ejemplo con el formato de estos ficheros.

Ahora sabemos qué proyectos vamos a usar para caracterizar los vídeos, pero todavía hay que decidir algunos aspectos relacionados con las opciones y configuraciones de estos proyectos. Lo primero es elegir el tipo de división en el proyecto para obtener los vectores de características de los frames. Según este proyecto la división de 3×3 ofrece resultados aceptables sin tener que utilizar vectores de características tan grandes como los obtenidos mediante la división de 4×4, por lo que se empezará a trabajar con esta división. Respecto a la media de color, en lugar de ceñirnos a una sola medida, se ha optado por utilizar la componente de color rojo, verde y azul, ya que la información proporcionada por el color puede ser muy importante durante el proceso de comparación. De esta forma, para cada frame, en vez de obtener un único vector de características, se tendrán tres vectores con 9 valores cada uno (debido a la división de 3×3), y con los que se construirá el vector de características final del frame, formado por 27 valores, y por lo tanto, en lugar de generarse un solo fichero, se crearán tres, uno para cada componente. La siguiente figura explica como se formaría el vector de característica final del frame.

Por último, para el proyecto de Alberto Aparicio, hay que espicificar el valor de los parámetros de configuración. La siguiente tabla muestra el valor utilizado para cada uno de ellos, elegidos en base a las recomendaciones hechas en el propio proyecto según las pruebas realizadas.

PARÁMETRO	VALOR
Salto entre frames	1
Radio de Dilatación	4 (4-6)
Compensar movimiento	NO
Número de cuadrados	–
Utilizar media y desviación típica para determinar cortes	NO (Utilizar valor constante)
Umbral de cambio de escena	20
Media y desviación local	–
Radio del entorno de media y desviación	–
Calcular cambiantes como suma	SI
Utilizar incrementos	SI
Mínimo de pixeles cambiantes en barrido	1
Porcentaje mínimo de pixeles en la franja de barrido	80
Separación mínima entre barridos	10

Una vez que sabemos todo esto, nos creamos una pequeño método que coja los tres ficheros con los vectores de características (uno de cada componente de color) y el fichero con los cambios de escena, y forme los vectores de 27 características correspondientes a cada uno de los keyframes del vídeo tal y como se ha explicado antes, generando un fichero con el formato del siguiente ejemplo:

Pero para poder probar este método y las posteriores comparaciones es necesario disponer de una serie de vídeos con los que trabajar. Se ha optado por utilizar vídeos deportivos divididos en varias categorías, concretamente en baloncesto, balonmano, formula 1, fútbol, motociclismo, natación, rugby y tenis. En un principio en cada una de estas categorías va a predominar un color, por ejemplo, en futbol predominará el verde y en natación el azul, y cuando se realicen las pruebas de comparación los vídeos de una misma categoría deberán de tener un mayor parecido entre sí que con vídeos de categorías diferentes.

Francisco Ruiz Romero ha sido el encargado de conseguir vídeos de estas categorías, con una duración de dos minutos aproximadamente cada uno, y además, tambien ha sido el encargado de utlizar las aplicaciones de Antonio Sánchez Benavente y de Alberto Aparicio Rios para obtener los ficheros con los vectores de caracteristicas según las tres componentes y el fichero con los saltos de escena de cada uno de los videos deportivos. Por lo tanto, Francisco es quien me proporciona esos ficheros, que yo utilizo para generar los ficheros con los vectores que caracterizan los vídeos que se usarán para realizar la comparación.

PROCESO DE COMPARACIÓN

Una vez que se tenía crado el método para obtener los vectores de características de los keyframes de cada uno de los vídeos y guardarlos en un fichero, había que pensar ya en cómo se iba a realizar la comparación. En el post de Octubre ya se comentó que se ha tomado como idea el documento “Bounded Coordinate System Indexing for Real-Time Video Clip Search” de Zi Huang, Heng Tao Shen, Jie Shao, Xiaofang Zhou y Bin Cui, y que según éste, un video se puede representar en un espacio N-dimensional, siendo N el número de características de los vectores de características, y por tanto, cada una de las características será una dimensión. Cada uno de los vectores de características dará lugar a un punto en ese espacio, cuya coordenada videne dada por el valor de cada característica. De esta forma un vídeo estará formado por un conjunto de puntos. Sin embargo, en dicho trabajo, a este conjunto de puntos se le aplica un análisis de componentes principales, obteniendo un nuevo sistema de coordenadas para cada vídeo, de manera que la primera componente describe la mayor varianza de los puntos, la segunda componente la siguiente mayor varianza, etc. Además esos sistemas de coordenadas están acotados por los propios puntos, es lo que llama «Bounded coordinate system» o sistema de coordenadas acotados, y la forma de comparar dos vídeos es mediante la comparación entre sus sistemas de coordenadas acotados.

Sin embargo, con el fin de simplificar el método, nosotros hemos decidido descartar el procesos de análisis de componentes principales, quedando todos los vídeos representados en el mismo espacio N-dimensional (todos los vídeos usan el mismo número de características). Ahora no vamos a ver cada vídeo como un sistema de coordenadas independiente, sino más bien como una caja N-dimensional. El tamaño de esta caja en cada dimensión viene dado por el valor máximo y mínimo de los puntos en dicha dimensión y su centro es el centro está situado en su mitad en cada una de las dimensiones. Veamos un ejemplo simplificado para comprenderlo mejor. Supongamos que tenemos un vídeo que solamente tiene dos características, X e Y, y que está formado por seis escenas o clusters, por lo que tendrá seis keyframes. El vídeo quedaría caracterizado por seis vectores de características, cada uno de ellos con 2 valores, dando lugar a 6 puntos en un espacio de dos dimensiones, una para cada característica, y formando una caja de dos dimensiones también que representará al vídeo. En la siguiente tabla se muestran valores de ejemplo para estos vectores y en la figura de más abajo se observa la representación de dichos vectores y la caja que representa al vídeo.

		X	Y
Vectores de características	Keyframe 1	1	3
	Keyframe 2	2	3
	Keyframe 3	3	1
	Keyframe 4	3	4
	Keyframe 5	5	2
	Keyframe 6	6	4
Centro		3’5	2’5

Así, cada vídeo es una caja dentro de ese espacio N-dimensional, y comparar dos vídeos para ver el parecido que hay entre ellos significa comparar las dos cajas que los representan. Esa comparación se va a medir como una distancia entre las cajas, que indicará un mayor parecido entre los vídeos mientras menor sea su valor. La forma de calcular esa distancia es mediante otra serie de medidas independientes que se combinarán de alguna forma para dar esa distancia definitiva. A continuación se explican esas medidas que se están utilizando, aunque no son definitivas y dependiendo de los resultados de las pruebas puede que haya que modificarlas.

• Distancia entre centros: consiste en medir la distancia euclídea entre los centros de las cajas a comparar. Cuanto más cerca estén una caja de la otra, y por tanto sus centros, más parecidos serán los vídeos. La formula de la distancia euclídea entre dos puntos P y Q es la siguiente:

• Distancia de Jaccard: Dos cajas pertenecientes a dos vídeos muy parecidos estarán solapadas, y mientras mayor sea ese solapamiento, o lo que es lo mismo, el volumen de la intersección entre las cajas, mayor será el parecido.  Pero el volumen de la intersección hay que mirarlo respecto al volumen total de las cajas, que sería el volumen de la unión de ambas. Para ello se utiliza la distancia de Jaccard, que es igual a 1 – (volumen intersección / volumen unión). Esta distancia dará un valor comprendido entre 0 y 1. Para dos cajas muy parecidas el volumen de la intersección será muy próximo al de la unión, por lo que esta distancia será cercana a 0, es decir, cuanto más se acerque la distancia a 0, más parecidos serán los vídeos.

• Distancia de transformación: Esta distancia mide el coste de transformar la caja que representa un vídeo en la caja que representa a otro. Para ello primero se calcula la distancia euclídea entre los extremos mínimos de ambas cajas, entendiendo por extremo mínimo el extremo de la caja con las coordenadas mas bajas. Y por otro lado se calcula la distancia euclídea entre los extremos máximos de ambas cajas. La suma de esas dos distancias dará la distancia de transformación, la cual significa que a menor distancia, menos costará transformar una caja en otra, y por lo tanto más parecidos serán los vídeos.

Sabiendo ya el método de comparación, ahora toca implementar una aplicación que pueda realizar la comparación entre dos vídeos y la comparación de un vídeo con todos los vídeos de la colección para ver cuales son los más parecidos. Para ello hay que implementar los métodos necesarios para cargar un vídeo desde el fichero con los vectores de características, calcular el volumen y el centro de una caja, calcular la union e intersección de dos cajas, realizar el cálculo de las tres distancias utilizadas, o guardar el resultado de la comparación en un fichero entre otros. De momento las tres distancias no se van a combinar como una sola, para lo cual habría que normalizar el resultado de cada una para que den valores dentro del mismo rango, y se van a analizar los resultados de cada una por separado para ver si son eficaces.