issn: 1994-1536 | e-issn: 2227-1899 basan habitualmente en resultados de una serie de etapas que...
TRANSCRIPT
Revista Cubana de Ciencias Informáticas
ISSN: 1994-1536
Universidad de las Ciencias Informáticas
Cuba
Blanco Rosabal, Yendrys; Orozco González, Roelkis
Propuesta de un método para el resumen automático de video
Revista Cubana de Ciencias Informáticas, vol. 6, núm. 3, 2012, pp. 1-11
Universidad de las Ciencias Informáticas
Ciudad de la Habana, Cuba
Disponible en: http://www.redalyc.org/articulo.oa?id=378343678002
Cómo citar el artículo
Número completo
Más información del artículo
Página de la revista en redalyc.org
Sistema de Información Científica
Red de Revistas Científicas de América Latina, el Caribe, España y Portugal
Proyecto académico sin fines de lucro, desarrollado bajo la iniciativa de acceso abierto
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 3, julio-septiembre, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial ―Ediciones Futuro‖
Universidad de las Ciencias Informáticas. La Habana, Cuba
Tipo de artículo: Artículo original
Temática: Reconocimiento de imágenes
Recibido: 4/07/2012 | Aceptado: 10/09/2012
Propuesta de un método para el resumen automático de video
Proposal of a method for automatic video summary
Yendrys Blanco Rosabal1*
Roelkis Orozco González2
1 Delegación del Ministerio de la Informática y las Comunicaciones, Guantánamo, Ahogados entre 11 y 12
norte, Edificio ETECSA, Guantánamo. CP.: 95100
2 Departamento de Informática, Universidad de Guantánamo, km 1 ½, carretera de Santiago de Cuba,
Guantánamo. CP.: 95100
[email protected]; [email protected]
Resumen: Este trabajo tiene como objetivo el desarrollo de un método que de manera simple permita el
resumen automático de video haciendo uso de métodos estadísticos, tales como el procesamiento de
histogramas.
Palabras clave: fotogramas claves, métodos estadísticos, procesamiento de histogramas, resumen de video.
Abstract: This work aims at developing a simple method which allows automatic video summary using
statistical methods, such as processing histograms. The most significant work is to demonstrate the creation
of a video summarization.
Keywords: histogram processing, keyframes, summary video, statistical methods.
1. Introducción
A diferencia del estudio de los mecanismos de la visión humana, el procesamiento y análisis de
imágenes digitales nacen en el momento en que se dispone de recursos tecnológicos para captar y manipular
gran cantidad de información espacial, en forma de matrices de valores.
Algunos problemas iniciales para la mejora de la calidad de la imagen estaban relacionados con la selección del
método de impresión y la distribución de los niveles de gris. Los primeros sistemas, de los años veinte, eran
capaces de codificar cinco niveles de gris distintos. En 1929 ya se utilizaban quince.
El procesamiento de imágenes como tal comienza en la etapa de los años 50 al 60 debido a la
combinación de dos hechos, por una parte la aparición de los microcomputadores digitales y por otra los
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 3, julio-septiembre, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial ―Ediciones Futuro‖
Universidad de las Ciencias Informáticas. La Habana, Cuba
programas espaciales. En esta técnica, convergen varios aspectos como es el caso de la percepción psico-
visual del ser humano. Este es un factor importante porque independientemente del tratamiento que se le aplique
a una imagen, el observador será quien, según su percepción visual, decidirá si dicha imagen le agrada o
no. El desarrollo de los métodos de procesamiento digital de imágenes tiene su origen en dos áreas
principales de aplicación: el mejoramiento de la información pictórica para la interpretación
humana, y el procesamiento de datos de la imagen para la percepción de máquinas autónomas en el
que se incluyen etapas de transmisión y/o almacenamiento de estos datos.
Al procesar el video digital se parte de la concepción de obtener cada uno de los fotogramas (imágenes
digitales) que lo componen para posibles análisis. Los algoritmos de análisis automático de video digital se
basan habitualmente en resultados de una serie de etapas que tratan de extraer la estructura y significado de
la enorme cantidad de datos e información contenidos en este medio. El objetivo es dividir el video
completo en una serie de segmentos (fotogramas), que revelen su estructura sintáctica.
El uso del video como medio visual, ocupa temas tan importante como la vigilancia, la seguridad, la
documentación, el entretenimiento entre otros aspectos, donde estos videos son almacenados
sistemáticamente, y realmente llega a ser una gran cantidad de información a manejar, por lo que es
recomendable emplear los resúmenes de videos para su futura catalogación, la idea es simple, basta con tener
que visualizar un video del que se desconoce su contenido y este video tenga una duración de 4 horas, si de
este video se obtiene un resumen automático de video que estaría compuesto por los fotogramas más
significativos, se podría tener una idea del video original en solo pocos minutos.
2. Materiales y métodos
Las Imágenes Digitales
El concepto de imagen está asociado a una función bidimensional f (x, y), cuya amplitud o valor será el grado
de iluminación en el espacio de coordenadas (x, y) de la imagen para cada punto. El valor de esta función
depende de la cantidad de luz que incide sobre la escena, los componentes que más afectan son la ilumina-
ción, determinada por la fuente, y la reflexión, que depende de las características del objeto en la escena.
La conectividad entre píxeles en una imagen digital, es un concepto importante usado para establecer las
fronteras de los objetos y las regiones componentes de una imagen. Para establecer si dos píxeles están
conectados se ha de establecer si son adyacentes en algún sentido (por ejemplo si son de vecindad 4 o
vecindad 8 y si sus niveles de gris cumplen algún criterio de similitud). Así en una imagen binaria con
valores 0 y 1, dos píxeles pueden ser de vecindad 4 y no estar conectados salvo que tengan el mismo valor
pero permitiendo conocer la distancia entre ellos.
Distancia entre píxeles
Con la distancia se quiere obtener el mínimo número de pasos elementales que se necesitan para ir de un
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 3, julio-septiembre, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial ―Ediciones Futuro‖
Universidad de las Ciencias Informáticas. La Habana, Cuba
punto a otro. Dados tres píxeles p, q y z con coordenadas (x, y), (s, t) y (u, v) respectivamente, se puede
definir una función de distancia D si cumple:
Figura 1. Distancia entre píxeles.
Las funciones de distancia usadas comúnmente son:
Distancia Euclidiana entre p y q, se define como:
Figura 2. Distancia Euclidiana.
Para esta medida de distancia, los píxeles están a una distancia r de un píxel dado, definiendo un disco de
radio r centrado en el punto (p, q).
Distancia Manhattan, se toman solamente en cuenta los píxeles de vecindad de orden 4 y se define como:
Figura 3. Distancia de Manhattan.
Distancia Tablero de Ajedrez, en esta distancia se tienen en cuenta los píxeles de vecindad de orden 8 y se
define como:
Figura 4. Distancia tablero de ajedrez.
Fundamentos del color de una imagen
El ojo humano percibe los colores según la longitud de onda de la luz que a él llega, permitiendo dividir el
espacio de color en seis regiones: violeta, azul, verde, amarillo, naranja y rojo. La caracterización de la luz en
una escena de color es fundamental. Si la luz es acromática, su único atributo es su intensidad, donde la luz
que contiene la mayor intensidad aparece como luz blanca, mientras que la ausencia de luz es percibida
como color negro.
Por otra parte la luz cromática expande el espectro electromagnético y permite realizar el análisis de la
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 3, julio-septiembre, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial ―Ediciones Futuro‖
Universidad de las Ciencias Informáticas. La Habana, Cuba
escena a partir de tres componentes: luminancia, brillo y resplandor. La luminancia expresa la cantidad de
energía que el observador percibe de la fuente de luz. El brillo consiste en la claridad u oscuridad relativa a
cada tono de color. El resplandor, es la cantidad total de energía que fluye de la fuente de luz.
Espacio de color RGB o canales de color RGB
El modelo de color RGB presenta las componentes espectrales primarias de luz: roja (R), verde (G) y azul
(B), en los ejes de un espacio cartesiano tridimensional. Por conveniencia se han normalizado las
componentes para representar este modelo como el cubo unitario de la figura que se muestra a continuación.
Los colores primarios aparecen en los vértices sobre los ejes: rojo (1, 0, 0), verde (0, 1, 0) y azul (0, 0, 1).
Los colores secundarios están en los vértices adyacentes a dos colores primarios: amarillo (1, 1, 0) entre el
rojo y el verde, magenta (1, 0, 1) entre rojo y azul y cian (0, 1, 1) entre verde y azul. El negro (0, 0, 0) esta en
el origen y el blanco (1, 1, 1) en el vértice opuesto. La diagonal principal de este cubo, que va desde el negro
al blanco corresponde a la escala de grises.
Figura 5. Espacio de colores.
Histogramas
El histograma es una función discreta que contabiliza el número de ocurrencias de cada nivel de gris presente
en una imagen. Representa estadísticamente una gráfica de una variable en forma de barras, donde la
superficie de cada barra es proporcional a la frecuencia de los valores representados. En el eje vertical se
representan las frecuencias, y en el eje horizontal los valores de las variables, normalmente señalando las
marcas de clase, es decir, la mitad del intervalo en el que están agrupados los datos.
En términos matemáticos, puede ser definida como una función inyectiva (o mapeo) que acumula (cuenta)
las observaciones que pertenecen a cada subintervalo de una partición. El histograma, como es
tradicionalmente entendido, no es más que la representación gráfica de dicha función, esta se utiliza cuando
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 3, julio-septiembre, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial ―Ediciones Futuro‖
Universidad de las Ciencias Informáticas. La Habana, Cuba
se estudia una variable continua, como franjas de edades o altura de la muestra, y, por comodidad, sus
valores se agrupan en clases, es decir, valores continuos. En los casos en los que los datos son cualitativos
(no-numéricos), como sexto grado de acuerdo o nivel de estudios, es preferible un diagrama de sectores.
En el procesamiento digital de imágenes si al histograma de una imagen se le divide por el número de píxeles
de dicha imagen se obtendrá la función de probabilidad muestreal de cada nivel de gris en la imagen tal y
como se define:
Figura 6. Definición muestreal del histograma.
Siendo M y N el número de filas y columnas de la imagen, h(i) es la función histograma y p(i) su
probabilidad. Un histograma no dice nada sobre la disposición espacial de las distintas intensidades. Dos
imágenes diferentes pueden tener igual histograma. Sin embargo, el histograma habla sobre el tipo de
adquisición que ha sido realizado. El histograma proporciona información estadística de la imagen. Esta
información es bastante útil para conocer cómo se ha producido el proceso de formación de la imagen.
Figura 7. Función estadística del histograma.
El histograma 3D
Se define de forma similar al 2D. Sin embargo este histograma resulta difícil de representar sobre el papel.
Existen tres maneras posibles: mediante cortes por planos obteniendo diferentes histogramas 2D que no
serían más que proyecciones del histogramas 3D en tres 2D, y por último mediante la representación en
perspectiva, siendo esta mucho más compleja y con mucha carga computacional. Una vez visto que se puede
trabajar con histogramas 3D usando histogramas 2D, es lógico pensar que podremos usar los mismos
algoritmos o incluso combinarlos para segmentar exactamente la zona que se desee pero teniendo la
información de las tres componentes de color RGB.
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 3, julio-septiembre, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial ―Ediciones Futuro‖
Universidad de las Ciencias Informáticas. La Habana, Cuba
Resumen Automático de Video
La creciente utilización de datos de multimedia como el vídeo en ordenadores personales y equipamiento
del hogar crea un fuerte requisito de herramientas eficientes para manipular este tipo de dato.
El resumen automático de video digital comprende el proceso de extracción de información representativa
sobre el contenido o estructura del video, centrada en la obtención de una representación simplificada de
este con un tamaño siempre inferior, esto se logra de manera global aplicando el enfoque de extracción de los
fotogramas más representativos.
Fotogramas más representativos (key-frames)
Los key-frames son las imágenes estáticas, extraídas del video original, que mejor representan el contenido
de las escenas, por ejemplo, en el proceso de indexación de texto se utilizan palabras clave (key-words) o
resúmenes que se utilizan como índices para la localización de párrafos, capítulos o documentos completos.
De forma análoga, en el proceso de indexación de video, se pueden extraer key-frames como índices para la
localización de escenas o videos completos.
Un key-frame es, por tanto, un fotograma que condensa un gran valor semántico, representando fielmente
una parte del video aprovechándose de la redundancia temporal en el contenido de fotogramas cercanos. Los
key-frames deben, por ende, reflejar los cambios de contenido de un video. En teoría se debería utilizar
información semántica acerca de objetos, acciones y eventos.
Algoritmo de resumen automático de video
Como elemento de investigación se estudiaron diversos algoritmos que describen el proceso de realizar el
resumen automático de video, por ser objetivo y práctico se decidió utilizar un algoritmo de origen hindú
como variante inicial para exponer los resultados de esta investigación.
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 3, julio-septiembre, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial ―Ediciones Futuro‖
Universidad de las Ciencias Informáticas. La Habana, Cuba
Figura 8. Algoritmo inicial.
Descripción del Algoritmo
Paso 1. Acceso a los fotogramas
El acceso a los fotogramas se realiza al cargar el video.
Paso 2. Calcular Histograma 3D
Cada fotograma está en el espacio de color RGB, donde la componente R (red, rojo), o G (green, verde) o B
(blue, azul) es escalada en un rango de 0 hasta 5 de manera empírica, debido a que el rango de valores reales
posibles a calcular es de 0 hasta 255 (256 valore en total) y esto supondría un alto coste computacional. Esto
da como resultado que el conjunto de ellos (5*5*5) conforman un histograma de 3 dimensiones.
Para obtener la información espacial de la distribución de los colores, cada fotograma es dividido en una
matriz de 3*3, obteniendo 9 bloques por 125, como resultado final un vector de dimensión de 1125 que
caracteriza a la imagen.
Paso 3. Creación de la matriz característica
Para obtener la matriz característica es necesario obtener la información que brinda el histograma de color (3
dimensiones para el espacio de color RGB) de los fotogramas que son manipulados para guardar la
información obtenida en un vector. El conjunto de todos los vectores finalmente caracterizan al video,
conformando finalmente una matriz de n fotogramas por 1125 vectores.
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 3, julio-septiembre, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial ―Ediciones Futuro‖
Universidad de las Ciencias Informáticas. La Habana, Cuba
Paso 4. Calculo de la Distancia Euclidiana
Para calcular la distancia euclidiana se toman los valores de la matriz característica con la siguiente fórmula:
DE = sqrt ( sum ( ( Xj – Yj )2 ) ) para toda “j”
Donde sqrt, es la raíz cuadrada, sum es la sumatoria, X y Y representan dos fotogramas diferentes y j
representa el recorrido del vector de 1125 valores.
Paso 5. Creación de subconjunto por división de nodos
La distancia euclidiana es el primer parámetro para la creación de subconjuntos de los fotogramas, los
siguientes pasos explican como realizar el corte de los fotogramas y la conformación de los nodos.
1. Se parte de la idea de que existe un nodo de valor 1 (todo el conjunto de fotogramas).
2. Para todos los nodos realizar los pasos desde el a hasta el d
a. Buscar la mínima (edmin) y máxima (edmax) distancia euclidiana en el nodo inicial. El valor de
ei representa la distancia euclidiana entre un fotograma y el siguiente por tanto el edmin y el edmax
esta definido por:
edmin = min (ei)
edmax = max (ei)
Donde i representa el conjunto sucesivo de fotogramas.
b. Calcular el promedio de la distancia euclidiana en el vector euclidiano creado
edavg = (edmin+edmax)/2
c. Comparar el promedio de la distancia euclidiana con cada uno de los valores del vector euclidiano.
d. Al encontrar un valor mayor que el promedio calculado en una posición determinada en el vector
euclidiano, entonces se crea una partición del nodo en este punto, dando a lugar divisiones de
nodos donde el valor de la posición sea mayor que el promedio calculado y formando así el video
con los nodos creados.
Después de varias pruebas se evidencio que el funcionamiento y rendimiento podía arrojar mejores
resultados si se realizaban algunos cambios al algoritmo como la creación de un nuevo vector denominado
―semilla‖ en conjunto con el ―average‖, los cuales serian los elementos esenciales para determinar la
eficiencia en comparación con el algoritmo antes descrito, dando como resultado una nueva variante, la cual
ha demostrado mejor rendimiento y mas información obtenida de la comparación entre los fotogramas.
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 3, julio-septiembre, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial ―Ediciones Futuro‖
Universidad de las Ciencias Informáticas. La Habana, Cuba
.
Figura 9. Algoritmo nuevo (resultado de varias modificaciones).
3. Resultados
Se ha logrado obtener una solución inicial que puede ser utilizada como herramienta que permita crear un
resumen automático de video. En el plano económico puede favorecer a varios sectores del país al definir el
punto de partida de una herramienta informática que permita obtener una idea general de un video de larga
duración en pocos minutos.
4. Conclusiones
Teniendo en cuenta todo lo mencionado, se hace evidente la necesidad de seguir investigando sobre la
utilidad que brinda la creación de los resúmenes automáticos de video. Se ha cumplido con el objetivo
planteado en el documento, donde los resultados de esta investigación se han expuesto a través de la
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 3, julio-septiembre, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial ―Ediciones Futuro‖
Universidad de las Ciencias Informáticas. La Habana, Cuba
implementación de un algoritmo como caso de estudio. La implementación de una solución informática
puede permitir y facilitar a los observadores comprender la utilidad del uso de poco tiempo para visualizar
un video, así como mayor agilidad y oportunidad en el procesamiento de la información lo que facilita
mayor celeridad en la toma de decisiones.
Referencias
TASKIRAN, C. M. and DELP E. J. ‖Video Summarization‖, CRC Press LLC. 2005.
HAHN, U. and MANI, I. ―The challenges of Automatic Summarization‖, IEEE Computer. 2000.
SUN, X. and MOHAN, S. K. ―Video Summarization Using R-Sequences ―, Real-Time Imaging 6. 2000. p.
449-459.
SMITH, M.A. and KANADE, T. ―Video Skimming for Quick Browsing Based on Audio and Image
Characterization‖, Carnegie Mellon University, Technical Report No. CMU-CS-95-186. 1995.
GONG, Y. and LIU, X. ―Video Summarization and Retreival Using Singular Value Decomposition‖, NEC
Laboratories of America. Multimedia Systems 9: 2003. p. 157-168.
DEMENTHON, D., KOBLA, V. and DOERMANN, D. ―Video Summarization by Curve Simplification‖,
ACM MM98. 1998.
NAPHADE, M. R. and HUANG, T.S. ―Multimedia Understanding : Challenges in the New Millennium‖,
Proc. of IEEE Internacional Conference on Image Processing, Vancouver. 2000.
DUFAUX F. ―Key Frame Selection to Represent a Video‖, Proc of IEEE International Conference on Image
Processing. Vancouver. 2000.
HANJALIC A, LAGENDIJK R. L and BIEMOND J. ―A New Method for Key Frame Based Video Content
Representation‖, in Image Data-Bases and Multi Multimedia Search, World Scientific Singapore. 1977.
NAM, J. and TEWFIK, A. ―Dynamic Video Summarization and Visualization‖, Proceedings of ACM
International Conference on Multimedia, Orlando, FL. 1999.
MAYBURY, M.T. and MERLINO, A.E. ―Multimedia Summaries of Broadcast News‖, IEEE Intelligent
Information Systems. 1997.
VASCONCELOS N. and LIPPMAN A. ―Bayesian Modeling of Video Editing and Structure: Semantic
Features for Video Summarisation and Browsing‖, IEEE Intl. Conf. on Image Processing. 1998.
LIENHART, R., PFEIFFER, S. and EFFELSBERG, W. ―Video Abstracting‖. In Communications of ACM.
1997.
VASUDEVAN N, VASUDEVAN N and AGRAWAL H. Iterative Image Based Video Summarization by
Node Segmentation. 18 National Computer Conference, Saudi Computer Society (SCS), Riyadh, Saudi
Arabia, March, 2006.
KADIR, T, BRADY M. Scale. Saliency and Image Description. International Journal of Computer Vision,
Springer, Netherlands. 2001. IJCV 45(2). 2001. p. 83 – 105.
Revista Cubana de Ciencias Informáticas (RCCI)
Vol. 6, No. 3, julio-septiembre, 2012
ISSN: 1994-1536 | e-ISSN: 2227-1899
RNPS: 0547 | e-RNPS: 2301
http://rcci.uci.cu
Grupo Editorial ―Ediciones Futuro‖
Universidad de las Ciencias Informáticas. La Habana, Cuba
JURIE, F., SCHMID, C. Scale-Invariant Shape Features for Recognition of Object Categories. 2004 –
Disponible en: [www.computer.org]. Volume II. 2004. p. 90 – 96.
FLORACK, L.M.J., HAAR ROMENY, B.M.t., Koenderink, J. J., Viergever, M.A. General Intensity
Transformations and Differential Invariants. Journal of Mathematical, - Springe 1994. JMIV 4. 1994. p. 171–
187.
BAUMBERG, A. Reliable Feature Matching Across Widely Separated Views. Disponible en:
[www.computer.org] 2000. p. 774 – 781.
SCHAFFALITZKY, F., ZISSERMAN, A. Multi-view Matching for Unordered Image Sets. Computer
Vision— 2002 - Springer. Volume 1. 2002. p. 414 – 431.
FREEMAN, W.T., ADELSON, E.H. The Design and Use of Steerable Filters. 1991. p. 891 – 906.
CARNEIRO, G., JEPSON, A. Multi-Scale Phase-Based Local Features. 2003. p. 736 – 743.
LOWE, D. Distinctive Image Features from Scale-Invariant Keypoints, Cascade Filtering Approach.
International Journal of Computer Vision, Springer. 2004. p. 91 – 110.