Algoritmo adaptativo con el grado de movimiento para el desentrelazado de vídeo

ALGORITMO ADAPTATIVO CON EL GRADO DE MOVIMIENTO PARA EL DESENTRELAZADO DE V´ IDEO P. Brox1,I.Baturone 1,S.S´anchez-Solano1,J.Guti´errez-R´ıos2and F. Fern´andez-Hern´andez2 1Instituto de Microelectr´onica de Sevilla (IMSE-CNM-CSIC) Avda. Reina Mercedes S/N. Edificio CICA. 41012 Sevilla e-mail:[email protected] 2Dpto. Tecnolog´ıa Fot´onica. Facultad de Inform´atica de la Universidad Polit´ecnica de Madrid Campus de Montegancedo S/N. 28660 Boadilla del Monte (Madrid) e-mail:jgr@fi.upm.es Resumen En esta comunicaci´on se presenta un algoritmo adaptativo con el movimiento para el desentrelazado de v´ıdeo. Se basa en un sistema de inferencia difuso, que realiza una interpolaci´on entre dos t´ecnicas lineales en funci´on del grado de movimiento. Se ha realizado un estudio de diferentes sistemas difusos con distinto n´umero de funciones de pertenencia, analiz´andose el grado de complejidad de los mismos frente a su eficacia desentrelazando varias secuencias de v´ıdeo. Palabras Clave: Desentrelazado de v´ıdeo, Movimiento adaptativo, Sistemas de inferencia difusos, T´ecnicas de aprendizaje supervisado. 1 INTRODUCCI ´ ON Los principales formatos de transmisi´on de se˜nales de televisi´on (NTCS, PAL, SECAM) utilizan una se˜nal de v´ıdeo entrelazada, donde s´olo se transmiten alternativamente las l´ıneas pares e impares de cada fotograma. De este modo, el ancho de banda de la transmisi´on se reduce a la mitad de una forma muy efectiva ya que, debido a las caracter´ısticas del sistema de visi´on humano, el parpadeo provocado por la eliminaci´on de l´ıneas es pr´acticamente inapreciable [3]. No obstante, el auge de dispositivos que requieren un barrido progresivo de la se˜nal de v´ıdeo (televisores de alta definici´on, DVDs, proyectores, etc.) ha fomentado el desarrollo de algoritmos de desentrelazado que realizan alg´un tipo de interpolaci´on espacio-temporal para calcular las l´ıneas no transmitidas. Entre los algoritmos de desentrelazado pueden distinguirse globalmente aquellos que utilizan un vector representativo del movimiento de la imagen para interpolar las l´ıneas ausentes y los que no lo hacen [4]. Los primeros realizan una interpolaci´on m´as precisa a costa de un elevado coste computacional requerido para calcular dicho vector. Los diferentes algoritmos pueden clasificarse atendiendo a si interpolan siempre los mismos p´ıxeles (t´ecnicas lineales) [6] [11], o si la interpolaci´on se adapta a las caracter´ısticas de la imagen (t´ecnicas no-lineales) [1] [5]. Entre los algoritmos adaptativos se distinguen a su vez dos grupos: aquellos que tratan de adaptar la interpolaci´onalapresencia de bordes en la imagen [5]; y aquellos otros que eval´uan la cantidad de movimiento en la imagen adaptando la interpolaci´on a ´esta [1]. Cuando se emplean t´ecnicas de movimiento adaptativo es fundamental realizar una buena estimaci´on del grado de movimiento. B´asicamente los detectores de movimiento eval´uan la diferencia de valores de luminancia entre p´ıxeles de campos consecutivos. No obstante, esta medida no siempre es fiable debido a la presencia de bordes o detalles con grandes constrantes de valores de luminancia en la direcci´on vertical de la imagen, y a que la se˜nal puede contener ruido. Para aumentar la robustez de los detectores de movimiento algunos autores proponen conectar varios en cascada, de modo que solo si todos ellos detectan movimiento la se˜nalseactive[3]. Tambi´en se han propuesto distintos algoritmos basados en l´ogica difusa para realizar un desentrelazado adaptativo con el grado de movimiento obteniendo mejoras significativas. Esto se debe a la capacidad de las t´ecnicas difusas para realizar interpolaciones en zonas donde la informaci´on es imprecisa y, por tanto, la decisi´on no es trivial [10]. La t´ecnica propuesta en [10] obtiene buenos resultados pero emplea una base de reglas compleja que requiere un coste computacional considerable. En esta comunicaci´on se propone un nuevo algoritmo adaptativo para el desentrelazado de v´ıdeo que emplea un sistema de inferenciadifusoparadeterminar, en funci´on del movimiento, la interpolaci´ on entre los p´ıxeles de las l´ıneas trasnmitidas. El algoritmo es descrito en detalle en la secci´on 2. Su validez es analizada en la secci´on 3 desentrelazando varias secuencias de im´agenes. Finalmente, las conclusiones del trabajo son resumidas en la secci´on 4. 2 DESCRIPCI ´ ON DEL ALGORITMO El algoritmo de desentrelazado adaptativo en funci´on del movimiento que presentamos se basa en la siguiente heur´ıstica:sielp´ıxel a calcular corresponde a un ´area donde no existe movimiento, el resultado mejor se obtiene realizando una interpolaci´on entre p´ıxeles del campo anterior (interpolaci´on temporal). Si por el contrario el p´ıxel corresponde a un ´area donde el grado de movimiento es elevado, lo m´as adecuado es realizar una interpolaci´on entre distintos p´ıxeles del campo actual (interpolaci´on espacial). Entre las t´ecnicas lineales temporales y espaciales se han elegido las m´as b´asicas: la t´ecnica de inserci´on del p´ıxel del campo anterior como temporal (IT) y la media artim´etica de los p´ıxeles de las l´ıneas superior e inferior como espacial (IS). El grado de movimiento es evaluado procesando la se˜nal que se obtiene al realizar la convoluci´on bi-dimensional de la diferencia de luminancia en valor absoluto de dos campos que contienen l´ıneas de la misma paridad. Matem´aticamente puede expresarse como: mov(x, y, t)=Σ 3 i=1(Σ3 j=1Hij Cij )(1) donde Hij, Cij, vienen dadas por las siguientes matrices: ⎛ ⎝ 121 C=1 16 242 121 ⎞ ⎠(2) ⎛ ⎝ Hx−1y−1t−1Hx−1yt Hx−1y+1t−1 Hxyt =Hxy−1t−1Hxyt Hxy+1t−1 Hx+1y−1t−1Hx+1yt Hx+1y+1t−1 ⎞ ⎠(3) siendo Hxyt la diferencia en valor absoluto de la luminancia de los p´ıxeles que pertenecen a dos campos que contienen l´ıneas de la misma paridad: Hxyt =H(x, y, t)=|I(x, y, t −1) −I(x, y, t +1)| 2(4) La notaci´on (x,y,t) significa que el p´ıxel tiene una ubicaci´on espacial determinada por las coordenadas (x,y) y corresponde a un campo determinado (t) de la secuencia de video. Atendiendo al tama˜no de las matrices H y C, se observa que se emplea una ventana de convoluci´on bi-dimensional de tama˜no 3x3. La idea de utilizar t´ecnicas de convoluci´on para evaluar el movimiento fue introducida en [7]. La principal ventaja de ´estas es que permiten tener en cuenta la contribuci´on de los vecinos espacio-temporales al estimar el movimiento en el p´ıxel actual. De este modo, puede minimizarse la influencia de los eventuales errores en la detecci´on de movimiento debido a la presencia de ruido, bordes o detalles con contrastes de luminancia elevados. Adem´as es posible asignar un peso ponderando cada uno de los p´ıxeles vecinos mediante los coeficientes de la matriz C, tal y como indica la expressi´on (2). Se ha realizado un estudio para evaluar distintas posibilidades de la ventana de convoluci´on analizando distintas dimensiones y valores de los coeficientes que la componen [2]. Como conclusi´on se ha seleccionado la indicada en la expresi´on (2). Las t´ecnicas de movimiento adaptativo fueron originalmente introducidas en [1]. El grado de movimiento se evaluaba comparando el valor de la se˜nal correspondiente a la diferencia de luminancia entre campos consecutivos con un valor umbral constante. El objetivo del trabajo descrito en esta comunicaci´on ha sido emplear una t´ecnica de movimiento adaptativo que emplea un sistema difuso para realizar la transici´on entre las dos t´ecnicas de interpolaci´on (IS,IT)demanera m´as suave. De este modo, en las zonas donde el grado de movimiento es medio y por tanto, la decisi´on no es trivial, se realiza una interpolaci´on no-lineal entre IS eIT. 2.1 DESCRIPCI´ ON DEL SISTEMA DE INFERENCIA DIFUSO El conocimiento heur´ıstico empleado por las t´ecnicas de movimiento adaptativo es modelado mediante un sistema de inferencia difuso. En primer lugar, se ha empleado un sistema con solo dos reglas, donde los conceptos SMALL y LARGE se representan mediante los conjuntos difusos de la Figura 1(a). No obstante, podemos aprovechar la capacidad de interpolaci´on de la l´ogica difusa considerando la posibilidad de ampliar el n´umero de conjuntos difusos. De este modo, ser´ıa posible contemplar un nuevo conjunto difuso (representado con la etiqueta MEDIUM en la Figura 1(b)). La base de reglas se amplia considerando una nueva regla que, en el caso de activarse, implementa una combinaci´on lineal de las t´ecnicas ISyIT. Este razonamiento puede extenderse aumentando el n´umero de conjuntos difusos considerados a los cuatro (SMALL, SMALL-MEDIUM, MEDIUM-LARGE, LARGE) o cinco (SMALL, SMALL-MEDIUM, ME- Figura 1: Funciones de pertenecia utilizadas por los distintos sistemas de inferencia DIUM, MEDIUM-LARGE, LARGE) representados en las Figura 1(c) y 1(d) respectivamente. El n´umero de reglas de la base de reglas aumenta del mismo modo. El problema de esta t´ecnica es que ”a priori” no existe ninguna indicaci´on para fijar las constantes de los consecuentes de las bases de reglas con m´as de dos reglas , ni tampoco para determinar las constastes (A, B, C, D, E) que definen los conjuntos difusos asociados a las distintas etiquetas lingu´ısticas. Para fijar estos valores podemos entrenar los sistemas difusos empleando t´ecnicas de aprendizaje supervisado. El apartado siguiente describe en detalle dicho proceso. 2.2 PROCESO DE APRENDIZAJE SUPERVISADO Los sistemas han sido implementados en el entorno de desarrollo de sistemas difusos Xfuzzy [8]. Este entorno facilita el dise˜no de sistemas de inferencia basados en l´ogica difusa al incluir distintas herramientas de CAD que cubren las etapas de descripci´on, identificaci´on, simplificaci´on, verificaci´on, ajuste autom´atico ys´ıntesis. La etapa de ajuste constituye habitualmente una de lastareasm´as complejas del dise˜no de sistemas difusos. La herramienta que se encarga de implementar esta etapa en Xfuzzy se denomina xfl [9]. Esta herramienta permite aplicar algoritmos de aprendizaje Figura 2: Valores de MSE obtenidos por los distintos sistemas de inferencia difusos al desentrelazar las secuencias de video supervisado donde el comportamiento deseado del sistema es descrito mediante un conjunto de patrones de entrenamiento. Los sistemas han sido entrenados utilizando como patrones de entrenamiento un conjunto de fotogramas de v´ıdeo progresivo. De este modo, el algoritmo de aprendizaje supervisado seleccionado (Marquardt-Levenberg en nuestro caso) intenta minimizar una funci´on de error que eval´ua la diferencia entre el comportamiento actual y el deseado (determinado por los patrones de entrada/salida). La herramienta xfl permite aplicar el proceso de ajuste a los distintos par´ametros de los sistemas de inferencia difusos implementados. La utilidad de esta etapa del proceso de dise˜no se ha verificado desentrelazando varias secuencias de v´ıdeo, y se explica en detalle en la secci´on 3. 3 RESULTADOS DE SIMULACI ´ ON El algoritmo propuesto ha sido probado simulando distintas secuencias de v´ıdeo est´andares ampliamente utilizadas por la comunidad cient´ıfica y accesibles a trav´es de la p´agina web: http://decsai.ugr.es. Las secuencias utilizadas se encuentran originalmente en un formato de v´ıdeo progresivo por lo han sido desentrelazadas artificialmente, es decir, eliminado l´ıneasdecadadeuno de los fotogramas que las componen. Los datos del fichero de entrenamiento se obtiene seleccionando un conjunto de im´agenes progresivas de cada una de las secuencias. La Figura 2 muestra el error cuadr´atico medio (MSE) obtenido al desentrelazar seis secuencias de v´ıdeo. Este valor corresponde al valor medio de las im´agenes desentrelazadas (aproximadamente se han simulado unas Tabla 1: Valor medio de PSNR (en dBs) obtenido al desentrelazar distintas secuencia con diferentes algoritmos. Secuencia Missa Salesman Carphone Paris Trevor News Formato CIF CIF QCIF CIF CIF QCIF RL 36.44 29.75 28.25 23.61 31.05 25.18 IS40.47 33.53 32.61 26.67 35.04 29.25 IT38.36 36.17 30.34 29.86 34.36 33.13 VT-2fields 40.25 36.54 34.08 30.73 36.61 35.46 VT-3fields 40.52 36.95 34.54 31.37 37.16 35.67 T´ecnica [10] 40.01 37.62 32.27 33.12 35.38 34.73 Propuesta 2 reglas 40.18 38.29 34.78 35.28 36.69 37.51 Propuesta 3 reglas 40.51 38.44 34.83 35.78 37.49 38.68 Propuesta 4 reglas 39.65 38.23 34.94 35.55 36.77 38.65 Propuesta 5 reglas 39.67 38.21 34.94 35.93 37.16 39.15 50 im´agenes de cada secuencia). Las gr´aficas de la Figura 2 muestran los resultados obtenidos al implementar un algoritmo donde los conceptos, SMALL, SMALL-MEDIUM, MEDIUM, MEDIUM-LARGE y LARGE est´an definidos mediante valores umbrales, es decir, determinados por un valor num´erico constante. Tambi´en se muestran los resultados obtenidos mediante la implementaci´on de los sistemas difusos con distinto n´umero de reglas (con y sin aprendizaje). Comparando las tres series de resultados puede deducirse que los algoritmos que implementan los sistemas difusos obtiene los errores m´as peque˜nos, reduci´endose a´un m´as estos valores si las funciones de pertenencia y los consecuentes se modifican mediante el proceso de aprendizaje. Finalmente, analizando el n´umero de reglas empleadas y el valor de MSE obtenido se deduce que si se utilizan tres reglas se obtienen mejores resultados que con dos. No obstante, las mejoras introducidas con cuatro y cinco funciones de pertenecia no son significativas con respecto a la propuesta que utiliza tres. Es m´as, en determinados casos incluso dan lugar a errores ligeramente superiores. El algoritmo propuesto tambi´en ha sido comparado con otras t´ecnicas de desentrelazado. La Tabla 1 muestra el valor medio en PSNR obtenido al desentrelazar distintas secuencias de v´ıdeo aplicando una serie de algoritmos. Concretamente se han analizado las t´ecnicas lineales m´as simples: duplicaci´on o repetici´on del p´ıxel de la l´ınea anterior (RL) y el valor medio de las l´ıneas superior e inferior (IS)comot´ecnicas espaciales y la inserci´on del p´ıxel del campo anterior (IT)comotemporal. Tambi´en se han considerado en el estudio t´ecnicas lineales espacio-temporales actualmente utilizadas en chips comerciales [5], [10]. Finalmente, hemos considerado una t´ecnica de movimiento adaptativo que tambi´en emplea un sistema difuso para realizar la interpolaci´on [9]. Analizando los resultados mostrados en la Tabla 1 se observa que los resultados m´as altos de PSNR y por tanto, los errores m´as bajos corresponden al algoritmo propuesto (se indican los valores obtenidos con las distintas funciones de pertenencia tras realizarse el proceso de aprendizaje). Esto tambi´en puede ser corroborado analizando las im´agenes desentrelazadas de la Figura 3. Finalmente, se ha realizado un an´alisis del coste computacional involucrado en la implementaci´on de cada uno de los algoritmos. Para ello todos los algoritmos han sido ejecutados en la misma plataforma (un PC con procesador Pentium IV y sistema operativo MSWindow XP) determin´andose el tiempo empleado por cada uno de ellos en procesar una misma secuencia. Los resultados se muestran en la Tabla 2. Puede comproborse c´omo las t´ecnicas lineales son la m´as r´apidas aunque los resultados obtenidos por ellas se ven ampliamente mejorados por nuestra propuesta. 4CONCLUSIONES En este comunicaci´on se ha presentado un sistema difuso que en funci´on del grado de movimiento implementa distintas combinaciones entre dos t´ecnicas lineales. Est´a basado en las t´ecnicas cl´asicas de movimiento adaptativo pero utiliza deficiones difusas en lugar de crisp para determinar el grado de movimiento. Se han implementado distintos sistemas disfusos con distinto grado de complejidad analizando la eficacia de cada uno de ellos para realizar la interpolaci´on. Los par´ametros que definen el sistema de inferencia difuso han sido determinados mediante un proceso de ajuste autom´atico implementando un proceso de aprendizaje supervisado. En funci´on de los resultados obtenidos se deduce que un sistema que eval´ua el grado de movimiento con tres funciones de pertenencia es eficiente tanto por los resultados que consigue como por su coste computacional. Tabla 2: Tiempo de ejecuci´on para desentrelazar una de las secuencias. Algoritmo RL ISITVT VT T´ecnica Propuesta 2fields 3fields [10] 2-3-4-5 reglas Tiempo(s) 2.03 2.05 3.28 10.62 14.65 143.03 29.23-30.95-31.76-32.65 Figura 3: Im´agenes desentrelazadas obtenidas aplicando: (a) RL, (b) IS,(c)IT, (d) VT2fields, (e) VT3fields, (f) t´ecnica [10], (g) propuesta de 2 y (h) 3reglas Agradecimientos Este trabajo ha sido parcialmente financiado por los proyectos TEC2005-04359/MIC del Ministerio espa˜nol de Educaci´on y Ciencia, y TIC2006-635 de la Junta de Andaluc´ıa. El primer autor forma parte del programa de formaci´on para estudiantes de doctorado F.P.U., del Ministerio espa˜nol de Educaci´on y Ciencia. Referencias [1] A. M. Bock. Motion adaptive standards conversion between formats of similar field rates. Signal Processing: Image Communication, Vol. 6, no. 3, P´ag.275-280, 1994. [2] P. Brox, I. Baturone, S. S´anchez-Solano. A Fuzzy Motion Adaptive Algorithm for Interlaced-toProgressive Conversion. It will be published in Proc. of the Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU’2006), 2006. [3] G. De Haan. Video Processing. University Press, Eindhoven, 2004. [4] G. De Haan and E. B. Bellers. De-interlacing: An overview. Proc. of the IEEE, Vol. 86, P´ag.18391857, 1998. [5] T. Doyle and M. Looymans. Progressive scan conversion using edge information. Signal Processing of HDTV. Ed. Elsevier Science Publishers, Vol. II, P´ag.711-721, 1990. [6] Genesis Microchip, Inc., Preliminary data sheet of Genesis gmVLD8, 8 bit digital video line doubler, versi´on 1, 1996. [7] J. Guti´errez-R´ıos, F. Fern´andez-Hern´andez, J. C. Crespo and G. Trivi˜no. Motion adaptive fuzzy video de-interlacing method based on convolution techniques. Proc. of Information Processing and Management of Uncertainty in Knowledge-Bsed Systems, 2004. [8] F. J. Moreno-Velo, I. Baturone, S.S´anchez-Solano and A. Barriga. Rapid design of complex fuzzy systems with XFUZZY. Proc. IEEE Int. Conf. on Fuzzy Systems,P´ags.342-347, 2003. [9] F. J. Moreno-Velo, I. Baturone, R. Senhadji y S. S´anchez-Solano. Tuning complex fuzzy systems by supervised learning algorithms. Proc. IEEE Int. Conf. on Fuzzy Systems,P´ags. 226-231, 2003. [10] D. Van de Ville, B. Rogge, W. Philips and I. Lemahieu. De-interlacing using fuzzy-based motion detection. Proc.3rdInt.Conf.onKnowledgeBased Intelligent Information Engineering Systems,P´ag.263-267, 1999. [11] M. Weston. Interpolating lines of video signals. US-patent 4, P´ag.789-893, 1998.