Aportaciones algorítmicas y arquitecturales para la estimación de movimiento en sistemas de codificación híbrida de vídeo basados en los estándares H.263 y H. 264/AVC

A mis padres y a mi hermana Elena. n La inspiración existe, pero tiene que encontrarte trabajando." Pablo Ruiz Picasso, pintor y escultor espariol (1881-1975). En estas dos últimas décadas se ha producido un espectacular avance de los estándares de compresión de hagen y vídeo, guiado por el objetivo de conseguir unas tasas de compresión cada vez más ambiciosas. No obstante, esta evolución, ha traído consigo un considerable aumento en los requisitos de procesamiento exigidos a los sistemas de codif/cación y decodificación compatibles con estos estándares de compresión. Este hecho cobra especial relevancia en la estimación de movimiento, pues ésta representa, por su elevado coste computacional, así como por su hpacto sobre los niveles de compresión alcanzados, la etapa crítica de un codif/cador de vídeo compatible con cualquier estándar de compresión híbrida de vlCeo conocido. En este contexto, numerosos hvestigadores han propuesto multitud de estrategias de búsqueda de vectores de movimiento con el objetivo de reducir el esfuerzo computacional inherente al proceso de estimación de movimiento. Estas estrategias se Resumen basan, por lo general, en un conjunto de consideraciones hiciales acerca de las caracterljticas espaciales y temporales de la secuencia de vídeo a comprimir. Asimismo, con el objetivo de maximkar sus prestaciones para determinadas aplicaciones, la mayor parte de las estrategias de estimación de movimiento están particularkadas para un determinado estándar de codificación de vídeo y, dentro de éste, para un rango concreto del porcentaje de compresión. Estas caracterljticas determinan que, ante cambios en la naturaleza de la secuencia de vídeo a comprimir, en las necesidades del usuario, y/o en los requisitos del estándar, las prestaciones de compresión proporcionadas por las estrategias de estimación de movimiento propuestas hasta ahora no estén garantizadas. En esta Tesis Doctoral se propone un nuevo algon0no de estimación de movimiento, denominado VBS-ACBM (Variable Block Ske - Adaptive Cost Block Matching), que realka el cálculo de vectores de movimiento para cualquiera de los tamaños de bloques de pReIes y precisión de los vectores de movimiento definidos por los estándares H.263 y H264/A VC y por 10 tanto, de manera Nnplícita, para los definidos por cualquier estándar de compresión de vlCeo. Este algoritmo garantka, gracias al uso de las estrategias adaptativas desarrolladas en esta Tesis, unas prestaciones de compresión óptimas para todo tipo de secuencias de vídeo y requisitos de compresión, con un coste computacional reducido. De igual manera, se presentan en esta Tesis un conjunto de soluciones arquitecturales para la hplementación eficiente del algoritmo VBS-ACBM en co&ficadores de vídeo con restricciones de funcionamiento en tiempo real. En particular, se aportan dos nuevas arquitecturas para la estimación de movimiento con precisión entera y posterior refinamiento sub-pReI de vectores de movimiento. La introducción de un conjunto de novedosas estrategias arquitecturales planteadas en esta Tesis permite obtener, en ambas arquitecturas, mejoras significativas con respecto a trabajos publicados en la bibliografiá reciente. Tengo la inmensa suerte de poder afirmar que la realización de esta Tesis Doctoral se ha convertido en una experiencia inolvidable. Desde estas líneas, me gustaría expresar mi más sincero agradecimiento a las personas que lo han hecho posible. A mis directores de Tesis, José Fco López y Roberto Sarmiento, por la confianza que depositaron en mídesde el primer momento, así como por su incondicional apoyo durante todos estos años. El hecho de que dos personas a las que admiro profundamente, tanto desde el punto de vista profesional como personal, y que representan para mí un ejemplo a seguir, se hayan convertido no sólo en mis directores de Tesis sino también en verdaderos amigos, me lleva a reafirmarme en mi idea de que he tenido muchísima suerte. A mis compañeros Valentín de Armas, Gustavo Marrero y Félix Tobajas les tengo que dar las gracias por tantas cosas que, para no aburrir al lector, y abusando de la confianza que tengo con ellos, las resumiré en un inj~~sto 'pcias por todo': En cualquier caso, lo que no quiero pasar por alto es aquello por lo que, sin duda alyna, les estoy más agradecido: su impagable amistad con la que me honran cada día. I iii Agradecimientos A Antonio Núñez por abrirme de par en par las puertas del Instituto Universitario de Microelectrónica Aplicada, dentro del cual he podido realizar esta Tesis Doctoral A Rubén Arteaga, Roberto Esper-Chaín, Francisco González Luis Hernández Juan Antonio Montiel, Héctor Navarro, Raúl Regidor, Carlos Javier Sosa y 6scar Tubío les agradezco su absoluta disposición a la hora de ayudarme a saltar muchos de los obstáculos con los que me he encontrado durante estos años. A Ernesto Perea y a Viviana D 'Alto, por brindarme la extraordinaria oportunidad de realizar una estancia de investigación en los centros de Milán y Padova de la compañía STMicroelectronics, permitiéndome partic~par de pleno en el excitante proyecto Nomadik Asimismo, quisiera expresar mi agradecimiento a la Fundación Universitaria de Las Palmas y a La Caja de Canarias, por colaborar en la financiación de esta estancia por medio del programa Innova. Fuera del ámbito meramente académico e investigador, me gustaría darle las gracias a mi otro grupo de amigos, por lo mucho que supone para míque sean precisamente eso, mis amigos. Gracias a ti, Vanessa, por tu aliento constante para que sacara adelante la Tesis, soportándome y animándome con infinita paciencia y generosidad en los momentos menos buenos, en los que has sido la única persona capaz de arrancarme una sonrisa. Para mi fortuna, esto no esto todo por lo que tengo que darte las gracias, al contrario, me queda lo más importante. Sin duda alguna, lo que más te agradezco son los inolvidables momentos que me has regalado a tu lado. Desde este ';Oizquito " de texto, de todo corazón, infinitas gracias. Por último, gracias a mis padres, Sebastián y Micaela, porque ellos, sencillamente, me han dado todo a cambio de nada. Sólo espero que todos estos años de trabajo y silenciosos esfuerzos por su parte, dedicados en exclusividad a dar una formación y unos valores a sus dos hgos, hayan servido para que hoy se sientan tan orgullosos de ml; como yo lo estoy de tenerlos como padres. A ellos les debo todo lo que soy ~~NDICE GENERAL Resumen .................................................................................................................... i , , . . , Agradecimientos ....................................................................................................... III hdice general ............................................................................................................ v hdice de figuras ........................................................................................................ xi [ndice de tablas ....................................................................................................... xvii Acr6nimos.. ............................................................................................................. xix 1 lNTRODUCCl6N .............................................................................................. 1 1.1 PLANTEAMIENTO DEL PROBLEMA 3 1.2 MOTIVACI~N DE LA TESI 5 1 .3 OBJETIVOS DE LA TESIS .................................................................................. 9 1.4 ORGAN~ZAC~~N DE LA TESI 11 índice general 2 ESTADO DEL ARTE DE LA CODIFICACI6N HfBRIDA DE VfDEO ................... 15 2.1 CODIFICACI~N HíBRIDA DE VIDEO 17 2.1.1 Esquema general de funcionamiento de un codificador híbrido de vídeo ...... 17 2.1.1.1 Unidad de preproces 18 2.1.1.2 Unidad de reducción de redundancias espaciales ................................ 20 2.1.1.3 Unidad de reducción de redundancias temporales .............................. 22 2.1.2 Estándares de compresión de imagen y vídeo 25 2.1.2.1 Estándares de compresión de imagen 26 2.1.2.2 Estándares de compresión de vídeo 2 7 2.1.2.3 Novedades en la etapa de estimación de movimiento durante el proceso de estandarización 32 2.2 TECNICAS DE OPTIMIZACION LAGRANGIANA EN CODIFICADORES HíBRIDOS DE VIDEO 39 2.2.1 Técnicas de optimización basadas en multiplicadores de Lagrange ............. 40 2.2.2 Aplicación de las técnicas de optimización lagrangiana a codificadores híbridos de vídeo 42 2.3 ESTADO DEL ARTE EN ESTlMAClON DE MOVIMIENTO 45 2.3.1 Algoritmos rápidos de estimación de movimiento ...................................... 45 2.3.2 Arquitecturas de estimación de movimiento 53 2.3.2.1 Arquitecturas de estimación de movimiento con precisión entera ........ 55 2.3.2.2 Arquitecturas de estimación de movimiento con precisión sub-píxel .... 58 2.4 CONCLUSIONE 60 3 PROPUESTAS ALGORrTMICAS DE ESTlMACl6N DE MOVIMIENTO ADAPTATIVA ........................................................................................................ 63 3.1 ANALISIS DEL PROCESO DE ESTIMACION DE MOVIMIENTO .................................... 65 3.1.1 Motivación del análisis ............................................................................. 65 3.1.2 Entorno de análisis: propuesta sobre los parámetros de caracterización ....... 69 3.1.3 Resultados de la caracterización ............................................................... 71 índice de figuras Figura 3.16: Número medio de posiciones evaluadas por macrobloque con ajuste de la constante adaptativa con 8 Figura 3.17: Zonas estáticas de alta actividad espacial en la secuencia DEADLINE. ................... 99 Figura 3.18: Esquema de decisión con ajuste de la constante adaptativa para bloques de alta . . actividad espacial. .............................................................................................................. 100 Figura 3.19: Resultados de compresión para diferentes valores de y ..................................... 101 Figura 3.20: Número medio de posiciones evaluadas por macrobloque para diferentes valores de 102 Figura 3.21: Prestaciones de compresión con factores de cuantificación elevados para las tasas de muestre0 temporal estudiadas. ....................................................................................... 104 Figura 3.22: Prestaciones de compresión con factores de cuantificación bajos para secuencias muestreadas a 5 fotogramas por segundo. ........................................................................... 105 Figura 3.23: Número medio de posiciones evaluadas por macrobloque con criterio de decisión dinámico. .......................................................................................................................... 106 Figura 3.24: Etapa de refinamiento en el algoritmo PBM (a) y propuesta de modificación para reducir el coste hardware asociado (b) 110 Figura 3.25: Comparación de prestaciones de compresión entre el algoritmo ACBM original y ACBM modificad 111 Figura 3.26: Número medio de posiciones evaluadas por macrobloque en la solución final adoptad 112 Figura 3.27: Estudio de modos de codificación utilizados por el estándar H.264/AVC. .......... 115 Figura 3.28: Esquema de decisión en el algoritmo VBS-ACBM 11 7 Figura 3.29: Prestaciones de compresión obtenidas con el algoritmo VBS-ACBM para el estándar H.264/AVC 118 Figura 3.30: Número medio de posiciones evaluadas por macrobloque con el algoritmo VBSACBM para el estándar H.264/AVC. 119 Figura4.1: Esquema general de la arquitectura propuesta para la estimación de movimiento según el algoritmo VBS-ACB 128 1 xiii índice de figuras Figura4.2: Esquema general de la arquitectura propuesta para el módulo de estimación de movimiento con precisión entera .......................................................................................... 133 Figura 4.3: Evaluación de posiciones dentro del área de búsqueda por parte de cada uno de los grupos de elementos de proces 135 Figura 4.4: Estructura interna de un elemento de proceso genérico. ...................................... 144 Figura 4.5: Diagrama de bloques correspondiente a un grupo de elementos de proceso. .......... 145 Figura 4.6: Propuesta de almacenamiento en cuatro registros de acumulación de los SADs correspondientes a los bloques 4x4 dentro de un macrobloqu 145 Figura 4.7: Estructura y control del bloque SADpCOMPOSER 147 Figura 4.8: Estructura y control del bloque comparador de mínimos ...................................... 149 Figura 4.9: Campos del registro de configuració 150 Figura 4.10: Arbol de dependencias. 152 Figura 4.1 I : Diferentes posibilidades de comparación en cada uno de los módulos CHECKER.153 Figura 4.12: Modificación del grupo de elementos de proceso para el caso de estudio M = 4 y N - - 155 Figura 4.13: Resultados en términos de eliminación temprana de candidatos para la arquitectura deestudiocon M= 16y N= 1 158 Figura 4.14: Resultados en términos de eliminación temprana de candidatos para la arquitectura de estudio con M= 4 y N= 4. 161 Figura 4.15: Grupo de elementos de proceso modificado para la implementación del algoritmo PBM-HW 167 Figura4.16: Arquitectura del módulo de refinamiento de medio píxel a nivel de bloques funcionale 172 Figura 4.17: Campos del registro de configuración modificado 173 Figura 4.18: Distribución de los píxeles utilizados y las muestras de medio píxel calculadas por un bloque interpolador del módulo de refinamiento de medio píxe 174 Figura 4.19: Estructura de filtrado de cada bloque interpolador de medio píxel. ..................... 176 Figura 4.20: Distribución de los píxeles utilizados y las muestras de medio píxel calculadas por un bloque interpolador mediante interpolación bilineal ............................................................... 178 índice de figuras Figura 4.21: Arquitectura sistólica de refinamiento de vectores de movimiento a coordenadas de medio píxel con M=l y N=8. ............................................................................................. 179 Figura 4.22: Elemento de proceso genérico de la arquitectura sistólica de refinamiento de medio píxel. ................................................................................................................................. 181 Figura4.23: Almacenamiento de SADs en un elemento de proceso de medio píxel para los diferentes modos de estimación de movimiento. ................................................................... 182 Figura4.24: Diagrama de tiempos de refinamiento de vectores a coordenadas de medio píxel para un modo de estimación de movimiento cualquier 184 Figura4.25: Arquitectura del módulo de refinamiento de cuarto de píxel a nivel de bloques funcionale 185 Figura4.26: Distribución de las muestras de píxel y medio píxel utilizadas, y muestras de cuarto de píxel calculadas por un bloque interpolador de cuarto de píxel para un desplazamiento determinado 188 Figura 4.27: Arquitectura sistólica con M=l y N=8 de refinamiento de vectores de movimiento a coordenadas de cuarto de píxe 190 Figura 4.28: Elemento de proceso genérico de la arquitectura sistólica de refinamiento de cuarto de píxe 191 Figura 4.29: Diagrama de tiempos de refinamiento de vectores a coordenadas de cuarto de píxel para el modo de estimación de movimiento 4x4 193 Figura 4.30: Ciclos de trabajo por macrobloque obtenidos para el refinamiento sub-píxel en diferentes casos de estudi 194 Figura 4.3 1 : Estrategia de verificación empleada en esta Tesis 200 Figura 4.32: Modificación del elemento de proceso propuesta en [CCHtOGa] con el objetivo de soportar diferentes modos de estimación de movimiento 205 Figura 4.33: Número de puertas NAND2 equivalentes para diferentes formatos de vídeo y arquitecturas. 207 Figura A. I : Fotograma de muestra de las secuencias TABLE (A), DEADLINE (B), FOREMAN (C), Miss AMERICA (D), PAMPHLET (E), SUZIE (F) y COASTGUARD (G). ..................................... 251 índice de figuras 0 ~~NDICE DE TABLAS Tabla 4.1 : Diagrama de tiempos del módulo de estimación de movimiento con precisión entera para M= 1 y N= 16 138 Tabla4.2: Diagrama de tiempos simplificado del módulo de estimación de movimiento con precisión entera para M= 4 y N = 4. 139 Tabla4.3: Diagrama de tiempos simplificado del módulo de estimación de movimiento con precisión entera para M= 16 y N= 1 140 Tabla 4.4: Casos seleccionados para la comparación arquitectura1 de prestaciones en términos de eliminación temprana de candidato 156 Tabla4.5: Numero de puertas NAND2 equivalentes (miles) para cada bloque funcional y arquitectur 162 Tabla4.6: Diagrama de tiempos simplificado del módulo de estimación de movimiento con precisión entera para el algoritmo PBM-HW 166 Tabla4.7: Diagrama de tiempos del sistólico de elementos de proceso de medio píxel para un bloque genérico de 4x4 píxele 180 xvii índice de tablas Tabla4.8: Diagrama de tiempos del sistólico de elementos de proceso de cuarto de píxel para un bloque genérico de 4x4 píxeles. ............................................................................................ 192 Tabla 4.9: Número de puertas NAND2 equivalentes (miles) para cada bloque funcional de los sub-módulos de refinamiento de medio y cuarto de píxe 197 Tabla 4.10: Requisitos de almacenamiento (en bytes) del módulo de refinamiento sub-píxel propuesto 198 Tabla 4.1 I : Casos de test verificados en las arquitecturas propuestas. ................................... 201 Tabla 4.12: Resumen de las características de las arquitecturas de estimación de movimiento con precisión entera analizada 209 Tabla A. I : Características espaciales y temporales de las secuencias de vídeo utilizadas .......... 250 xviii 1 4CIF: ACBM: ACBM-HW: AMPD: AVC: CD-ROM: CGRA: CIF: CMOS: DCT: ENDIVIA: ETSII: FIR: FPGA: FSBM: 4 Common lntermediate Format. Adaptive Cost Block Matching. Adaptive Cost Block Matching - HardWare. Advanced Mode Pre-Decision. Advanced Video Coding. Compact Disc - Read Only Memory Coarse-Grain Reconfigurable Architectures. Common lntermediate Format. Complementary Metal Oxide Semiconductor Discrete Cosine Transform. ENtorno de Diseño basado en lPs con soporte para Verificación y depuración, Integración con redes en chip y Aplicaciones multimedia. Escuela Técnica Superior de Ingenieros Industriales. Finite Impulse Response. Field Programmable Gate Array Full Search Block Matching. xix Acrónimos 0 HDTV: HPR: IMEC: I P: ISO: ITU: JPEG: Jvr: LUT: MPEG: NoC: PBM: PBM-HW: PE: PSNR: QCIF: QPR: RTL: SAD: SOB: SVC: VBS-ACBM: VBSME: VCEG: VOD: H~gh Definition Tele Vision. Half Pixel Refinement. lnteruniversities MicroElectronics Center. lntellectual Property lnternational Organization for Standardkation. lnternational Telecommunication Union. Joint Photographk Experts Group. Joint Video Team. L ookUp Table. Moving Picture Experts Group. Network on Chip. Predictive Block Matching. Predictive Block MatchingHardWare. Processing Element. Peak S~gnal to Noise Ratio. Quarter Common Intermediate Format. Quarter Pixel Refinement. Register Transfer Leveel Sum ofAbsolute Differences. Start Of Block. Scalable Video Coding. Variable Block SizeAdaptive Cost Block Matching. Variable Block Size Motion Estimation. Video Coding Experts Group. Video On Demand. Introducción Las técnicas involucradas en el proceso de compresión de vídeo se encuentran hmersas en un continuo proceso de transformación y evolución. Este hecho viene determinado por las necesidades de un mercado altamente dinámico, el cual hcorpora rápidamente los resultados obtenidos en los diferentes centros de hvestigación. En este sentido, la estimación de movimiento, por su relevancia dentro del proceso de compresión híbnVa de vlCeo, continúa centrando los esfuerzos de numerosos hvestigadores, con el objetivo de proponer nuevos algoritmos y arquitecturas que contribuyan a mejorar sus prestaciones. 1 Introducción En este primer capítulo se señalan los motivos que dan origen a enfocar esta Tesis en el proceso de estimación de movimiento, describiéndose asimismo los objetivos a alcanzary la estructura en capítulos delpresente trabajo. Ausencia de comportamiento multiestándar. El desarrollo de los estándares de codificación de vídeo ha venido acompañado del estudio de nuevas posibilidades en el proceso de estimación de movimiento. Así, en el reciente estándar H.264/AVC existe la posibilidad de calcular hasta un total de 41 vectores de movimiento con precisión de cuarto de píxel para un mismo macrobloque (bloque de 16x16 píxeles), mientras que en el pionero estándar H.261 [H261] sólo se permite un vector de movimiento con precisión de píxel por macrobloque. Si bien las propuestas más recientes cumplen total o parcialmente con las recomendaciones establecidas por H.264/AVC, y a su vez éste engloba a sus predecesores en lo que a estimación de movimiento se refiere, dichas arquitecturas son incapaces de adaptar su potencia de cómputo a las necesidades del estándar en uso por el codificador correspondiente. Este conjunto de circunstancias, junto con el continuo avance de las plataformas de compresión de vídeo, determina que sea absolutamente necesario el diseño de nuevas etapas de estimación de movimiento multiestándar que soporten las recomendaciones establecidas por el estándar H.264/AVC y que a la vez, hagan un uso óptimo de un número de recursos escaso. Para ello, la triple adaptación de la arquitectura a las necesidades del usuario, a las características de las secuencias de vídeo a comprimir y a los requisitos del estándar de codificación en uso, representa una eficaz estrategia a seguir. 1.3 Objetivos de la Tesis La finalidad de esta Tesis Doctoral es proporcionar soluciones algorítmicas y arquitecturales para etapas de estimación de movimiento multiestándar haciendo un uso inteligente de los recursos disponibles. Para conseguir este propósito, la Tesis se centra en alcanzar los siguientes objetivos: 1 Introducción Estudio del estado del arte y en especial, de las arquitecturas propuestas en las que se implemente, con algún grado de adaptación de los recursos de cómputo, el proceso de estimación de movimiento mediante ajuste de bloques para cualquiera de los estándares de compresión de vídeo existentes. En este punto, es de especial importancia analizar y evaluar la estrategia de adaptación utilizada, tanto desde el punto de vista algorítmico como desde el punto de vista puramente arquitectural. Creación de un entorno de análisis que permita investigar en profundidad el proceso de estimación de movimiento y que a la vez, sirva como soporte para la elección de la estrategia de diseño que se aportará en esta Tesis. Este entorno se basará en la simulación y modelado de un estimador de movimiento genérico y permitirá extraer los parámetros esenciales del proceso sobre los cuales se construirán las propuestas desarrolladas en la Tesis. Aportar y evaluar un nuevo algoritmo que, en función de los parámetros mencionados en el punto anterior, sea capaz de estimar el movimiento entre dos imágenes de una secuencia de vídeo según las necesidades del estándar de codificación en uso, utilizando eficientemente los recursos disponibles y adaptándolos a las exigencias del usuario y a las características de la secuencia a comprimir. Para evaluar la bondad de este algoritmo, se utilizará una plataforma de validación que integre la solución aportada en codificadores basados en los estándares H.263 y H.264/AVC, de tal manera que cumpla con las características de estimación de movimiento para tamaños de bloque variables y precisión sub-píxel, tal y como se requiere por ambos estándares. Esta plataforma permitirá la evaluación de las prestaciones del algoritmo aportado para diferentes secuencias y tasas de compresión. En este punto es importante destacar que los resultados y conclusiones que se obtengan para el estándar H.263, serán absolutamente extrapolables para sistemas basados en MPEG- 4, al ser ambos estándares idénticos en sus perfiles básicos en cuanto al proceso de estimación de movimiento. Analizar las diferentes alternativas para el diseño arquitectura1 del algoritmo propuesto, desarrollando en paralelo un conjunto de técnicas que permitan aumentar las prestaciones de la arquitectura, tanto para la estimación de movimiento con precisión entera como para la estimación con precisión sub-píxel. Esta exploración permitirá evaluar y comparar, en términos arquitecturales, el conjunto de posibles soluciones. Proponer y evaluar una arquitectura que, una vez analizadas las diferentes alternativas arquitecturales, sea capaz de realizar el proceso de estimación de movimiento en tiempo real para formatos de vídeo de baja y media resolución según las directrices establecidas por los estándares H.263 y H.264/AVC de acuerdo al algoritmo propuesto. Asimismo, y de manera independiente al algoritmo propuesto, es también objetivo de esta Tesis mejorar las prestaciones arquitecturales de los trabajos previos más significativos recopilados en el estado del arte. 1.4 Organización de la Tesis El trabajo desarrollado en esta Tesis Doctoral se ha estructurado en cinco capítulos, de los cuales el primero de ellos lo constituye el presente capítulo de introducción. El contenido del resto de los capítulos se describe a continuación. Capítulo 2 En este capítulo se describe la evolución histórica del proceso de estandarización en compresión de imagen y vídeo, detallándose previamente la estructura de un codificador híbrido de vídeo genérico, base sobre la que se asientan los mencionados estándares. Asimismo, se recogen las novedades más significativas introducidas en el proceso de estimación de movimiento a lo largo del proceso de estandarización, finalizando el capítulo con una recopilación de los trabajos que, tanto desde el punto de vista algorítmico como arquitectural, constituyen el estado del arte en el ámbito de la estimación de movimiento En el capítulo 3 se describe el entorno de análisis propuesto en esta Tesis con el objetivo de interpretar, mediante el uso de parámetros, el proceso de estimación de movimiento en términos de la función de coste de Lagrange. A partir de los resultados obtenidos con dicho entorno, se presenta el algoritmo de estimación de movimiento adaptativa propuesto en esta Tesis, mostrándose los resultados obtenidos en términos de compresión y coste computacional. Por último, se detallan las variaciones introducidas con los objetivos de adaptar dicho algoritmo a estándares con estimación de movimiento de tamaño de bloque variable y facilitar su posterior implementación hardware. Capítulo 4 En este capítulo se introduce la arquitectura de estimación de movimiento propuesta en esta Tesis. En particular, se describen por separado la arquitectura de estimación de movimiento con precisión entera y la arquitectura de refinamiento de vectores de movimiento a coordenadas de medio y cuarto de 1.4 Organzacón de a Tess 1 píxel, poniendo de relevancia las aportaciones introducidas con el objetivo de mejorar sus prestaciones. Asimismo, se presenta una comparación en términos arquitecturales con trabajos previos recientemente publicados. Capítulo 5 Por último, se presentan en el capítulo 5 las conclusiones extraídas a partir del trabajo desarrollado en esta Tesis así como las líneas de investigación futuras que se pretenden continuar. Estado del arte de la codificación híbrida de vídeo El avance de la hdustria audiovisual ha convertido la codificación y decodificación de hágenes y vlíJeo en un proceso que, aunque transparente para el cliente final, resulta de uso cotidiano para millones de usuarios de aplicaciones multimedia. Para llegar a esta situación ha resultado absolutamente necesario desarrollar un conjunto de estándares que no sólo han permitido regularkar dicho proceso, sino también, mejorarlo en términos de las tasas de compresión alcanzadas. En este capítulo se revisan las bases sobre las que se asientan los estándares de compresión de imagen y vlCeo actuales. Asimismo, se describen las modificaciones 2 Estado del arte de la codificación híbrido de vídeo que han ido hcorporando estos estándares en relación con el proceso de estimación de movimiento con el objetivo de aumentar las prestaciones de los co&ficadores híbrido5 de vídeo basados en algún tipo de estándar. Dicho proceso de optimilación ha llevado consigo un aumento exponencial de la compkjídad de la estimación de movimiento por ajuste de bloques, despertando el interés de la comunidad científica por el desarrollo de nuevos algorimos y arquitecturas capaces de acelerar el proceso de cálculo de vectores de movimiento. En este sentido, se recogen en este capítulo las aportaciones más s@nificativas realizadas en esta área, poniendo de manifiesto aquellos aspectos aún sin resolvery que constituyen el objeto principal de esta Tesis. 2.1 Codfcacón híbrda de vídeo 2 2.1 Codificación híbrida de vídeo La codificación o compresión híbrida de vídeo es un campo específico dentro del procesamiento de señal multidimensional cuyo objetivo fundamental es obtener una representación compacta de una señal de vídeo digital cualquiera mediante la reducción de las redundancias espaciales y temporales presentes en la señal original. Este proceso puede ser reversible (compresión sin pérdidas) o irreversible (compresión con pérdidas), obteniéndose de manera general mayores niveles de compresión, y por lo tanto una peor calidad de imagen, en el segundo caso. En este apartado, se describen las técnicas sobre las que se fundamenta un codificador híbrido de vídeo genérico, así como las características más relevantes de los diferentes estándares que a lo largo de estos últimos años han sido desarrollados con el objetivo de normalizar, a la par que enriquecer y mejorar, dicho proceso de compresión. En este sentido, se resaltarán los conceptos teóricos directamente relacionados con los objetivos a conseguir en esta Tesis, pudiéndose obtener una visión más amplia y detallada acerca del proceso de compresión de vídeo en las publicaciones [BK97], [Ric02], [Rico31 y [Woo05], entre otras. 2.1.1 Esquema general de funcionamiento de un codificador híbrido de vídeo El diagrama de bloques de un codificador híbrido de vídeo genérico se muestra en la Figura 2.1, distinguiéndose fundamentalmente tres unidades funcionales: unidad de preproceso, unidad de reducción de redundancias espaciales y unidad de reducción de redundancias temporales. 2.1 Codfcacón híbrda de vídeo 2 de esta Tesis, se realizará posteriormente una descripción detallada, tanto desde el punto de vista algorítmico, como arquitectural. Compensacidn de movimiento. La compensación de movimiento obtiene de la memoria de reconstrucción el macrobloque señalado por el vector calculado por el estimador de movimiento. Así, a la salida del compensador de movimiento se obtiene un predictor, cuya resta con el macrobloque actual constituye el macrobloque diferencia que será procesado por la unidad de reducción de redundancias espaciales. Finalmente, cabe señalar dentro de la estructura genérica de un codificador híbrido de vídeo un conjunto de elementos de control encargados de seleccionar el tipo de codificación para cada macrobloque de la secuencia de vídeo (INTRA/INTER). Obviamente, todos los macrobloques del primer fotograma han de ser necesariamente codificados como tipo INTRA, decidiendo el codificador el modo de codificación a utilizar para el resto de macrobloques. 2.1.2 Estándares de compresión de imagen y vídeo La aparición de técnicas eficientes de compresión de datos multimedia ha determinado que, durante estos últimos veinte años, se haya realizado por parte de grupos de investigación y compañías del sector un exhaustivo esfuerzo de normalización, dando lugar a un potente conjunto de estándares de compresión de imagen y vídeo. Con el objetivo de caracterizar y comparar las prestaciones de cada estándar, se utilizan un conjunto de curvas conocidas como curvas de tasa de transmisión-distorsión (rate-distortion), en las que se representa la calidad de la imagen o secuencia decodificada frente a la tasa de transmisión utilizada. Para medir de manera objetiva la calidad de una imagen decodificada de MxN píxeles, la métrica 2 Estado del arte de la codificación híbrido de vídeo más utilizada es la relación de pico señal a ruido (Peak Signal to Noise Ratio - PSNR) expresada en unidades de decibelios, y definida como: (ec. 2.3) donde por y p representan los píxeles de la imagen original y decodificada, respectivamente. En secuencias de vídeo, cada uno de los puntos de la mencionada curva representa el PSNR medio obtenido considerando todos los fotogramas de la secuencia. Por último, recordar que cada estándar sólo define la estructura del decodificador, dejando un holgado grado de libertad para el diseño del codificador siempre y cuando las tramas generadas por éste sean compatibles con el decodificador definido. 2.1.2.1 Estándares de compresión de imagen Dentro de los estándares de compresión de imagen destaca, por su relevancia, el estándar JPEG (Joint Photographic Experts Group) [JPEG], que debe su nombre al grupo encargado de su desarrollo, fruto de la unión de los expertos en compresión de imágenes en color de las organizaciones ISO (lnternational Organization for Standardization) e ITU (lnternational Telecommunication Union). Dicho estándar permite comprimir imágenes digitales de tono continuo con unos rangos de compresión típicos de 10:l hasta 50:l garantizando una calidad de imagen aceptable [PM92]. Con el objetivo de aumentar las prestaciones de este estándar, el mismo comité de expertos ha desarrollado recientemente el estándar JPEG2000 [JPEG2K] que permite aumentar el 2.1 Codfcacón híbrda de vídeo 2 nivel de compresión entre un 11% y un 53% con respecto a su predecesor [CSEOO] debido principalmente al uso de transformadas waveleten lugar de la transformada DCT [LLT+01], [LCT+04], [LCL+05c] y codificadores aritméticos en la codificación entrópica del proceso de reducción de redundancias espaciales [ATL+02], [ALL+03] 2.1.2.2 Estándares de compresión de vídeo Dentro de los estándares de compresión de vídeo, destacan como pioneros los estándares H.261 [H261] y MPEG-1 [MPEGI] desarrollados por el Grupo de Expertos en Codificación de Vídeo ( Kdeo Coding Experts Group - VCEG) de la ITU (lnternational Telecommunication Union) y por el grupo de expertos en vídeo y audio digital MPEG (Moving Pictures Expert Group) de la organización ISO (lnternational Organkation for Standardkation), respectivamente. Aunque coetáneos, el objetivo de cada uno de estos estándares es bien distinto, puesto que mientras que H.261 fue ideado para aplicaciones de videotelefonía, el objetivo fundamental de MPEG-1 es el almacenamiento eficiente de vídeo digital, típicamente en formato CD-ROM. De esta manera, H.261 alcanza sus máximas prestaciones para anchos de banda múltiplos enteros de 64 Kbps, mientras que MPEG-1 lo hace para tasas de transmisión de 1.5 Mb~s. Debido al tremendo éxito de ambos estándares, los posteriores trabajos de estandarización dieron lugar al nacimiento del estándar MPEG-2 (Recomendación H.262 de la ITU) [MPEG2]. El principal objetivo de este estándar es la codificación y transmisión eficiente de imágenes de televisión para tasas de transmisión por debajo de 10 Mbps, respetando la compatibilidad con los estándares H.261 y MPEG-1, y permitiendo como formato de entrada no sólo vídeo progresivo, sino también vídeo entrelazado. Para lograr este objetivo, MPEG-2 conserva las técnicas de compresión que resultaron ser más eficaces dentro del estándar 2 Estado del arte de la codificación híbrido de vídeo MPEG-1, destacando entre ellas la predicción bidireccional y la estimación de movimiento con precisión de medio píxel, además de introducir nuevos modos de predicción específicos para el formato entrelazado. El estándar MPEG-4 [MPEG4] surge con el doble objetivo de aumentar las prestaciones de compresión alcanzadas por los estándares anteriores para tasas de transmisión bajas, además de proporcionar interactividad con el usuario. Para lograrlo, dicho estándar contempla el uso de técnicas avanzadas de compresión además de dividir la secuencia en objetos audiovisuales, permitiendo de esta manera el acceso y manipulación de su contenido. El estándar define un objeto audiovisual como cualquier representación de un objeto, natural o sintético, visual y/o sonoro, como por ejemplo audio natural o sintético, texturas y formas de objetos presentes en un fotograma, objetos sintéticos en dos y tres dimensiones o representaciones sintéticas de caras y cuerpos humanos, entre otros. Además, en el estándar MPEG-4 se presta especial atención a la transmisión eficiente del vídeo comprimido, dotándose de estrategias de protección ante errores y diversos grados de escalabilidad [PE02]. De manera paralela al desarrollo del estándar MPEG-4, el grupo VCEG de la ITU comenzó el desarrollo del estándar H.263 [H263]. La finalidad de este estándar no es otra que, a partir de la estructura básica del estándar H.261, mejorar las prestaciones de compresión para tasas de transmisión muy bajas, típicamente por debajo de 64 Kbps (nótese que el estándar H.261 estaba inicialmente concebido para la transmisión de vídeo en redes de conmutación de circuitos con un ancho de banda de px64 Kbps, siendo p un número entero entre 1 y 30). Para conseguir este objetivo el estándar define un núcleo básico de compresión similar al especificado en el estándar H.261 y un conjunto de 18 modos avanzados de compresión opcionales en forma de anexos al estándar. En particular, la recomendación H.263 se compone del mencionado núcleo básico y cuatro de estos modos de codificación opcionales (anexos D, E, F y G), incluyéndose el resto de anexos en las recomendaciones conocidas como 2.1 Codfcacón híbrda de vídeo 2 H.263+ [H263+] y H.263+ + [H263+ +] a razón de doce (anexos I a T) y dos (anexos U y V) modos opcionales, respectivamente. La continua aparición, un tanto desordenada, de diferentes estándares de compresión de vídeo intentando mejorar las prestaciones de sus antecesores, así como la excesiva especialización de éstos para un conjunto específico de aplicaciones, llevó al grupo VCEG al comienzo del desarrollo de un nuevo estándar que presentara prestaciones de compresión superiores al resto para todo tipo de aplicaciones, denominándose dicho estándar H.26L (la letra 'L' responde a la filosofía de trabajo del grupo de VCEG en su intento de crear un estándar de larga duración, long-term standard). Una vez comenzado el desarrollo del estándar, la ISO, a través de su grupo MPEG, realizó en el año 2001 una llamada abierta a la comunidad científica internacional en búsqueda de nuevas soluciones dentro del campo de la codificación de vídeo avanzada (Advanced Kdeo Coding - AVC) El objetivo de dicho proceso era encontrar nuevas soluciones que permitieran mejorar las prestaciones del estándar MPEG-4 que, aunque prometedor, no había causado un impacto en el mercado similar al de MPEG-2. Entre las propuestas recibidas se encontraban los primeros trabajos realizados por el VCEG dentro del marco del estándar H.26L, resultando ser la propuesta más innovadora a juicio de los expertos del grupo MPEG. Este hecho provocó que ambas organizaciones se fundieran en un nuevo grupo de trabajo conjunto (Joint Kdeo Team - JVT) con el objetivo de crear 'una solución única para la próxima generación de estándares de codificación de vídeo': Los esfuerzos del grupo de trabajo JVT, dieron lugar al desarrollo de un nuevo estándar denominado H.264/AVC [H264], también conocido como JVT, H.26L o MPEG-4 part 10, que se encuentra hoy en día en continua ampliación y desarrollo y que, sin duda alguna, representa el estado delarteen el campo de la codificación híbrida de vídeo. En este sentido, el nuevo estándar consigue reducir, por término medio, las tasas de transmisión requeridas por un codificador MPEG-2 en un 50%, y en un 35 % las correspondientes a codificadores basados en los estándares H.263 o MPEG-4 [KA03], [OBL+04]. Este hecho se 2 Estado del arte de la codificación híbrido de vídeo puede comprobar en la Figura 2.5, en la que se muestra la evolución de la tasa de transmisión media conseguida por los estándares mencionados durante los últimos diez años para secuencias de 720x480 píxeles. Figura 2.5: Evolución de la tasa de transmisión requerida por los estándares MPEG-2, MPEG-4, H263 y H264lAVC para codificar una secuencia de vídeo de 720x480 oíxeles. Asimismo, y a modo de resumen del proceso de estandarización, se muestra en la Figura 2.6 la evolución histórica de cada uno de los estándares mencionados en este apartado. En esta figura no se incluyen los estándares MPEG-7 [MPEG7] y MPEG-21 [MPEG21] debido a que su objetivo no es la compresión de vídeo. En particular, el estándar MPEG-7 representa una interfaz de descripción de contenidos multimedia diseñada para facilitar el acceso, recuperación, filtrado y manejo de datos multimedia. Para ello, este estándar se basa en la realización de bases de datos de información multimedia basadas en contenidos, las cuales permiten realizar búsquedas indexadas de imágenes y vídeo utilizando características como su color, textura, información de su forma y/o contorno de los objetos. En cuanto al estándar MPEG-21, su finalidad es permitir el uso transparente de recursos multimedia y aumentar su 2.1 Codfcacón híbrda de vídeo 2 acceso a través de un amplio rango de redes y dispositivos, proporcionando interoperabilidad entre distintos estándares. Así, el ámbito de MPEG-21 cubre funciones como creación, producción, consumo y uso de los contenidos; identificación, descripción y representación de los contenidos, o protección y gestión de la propiedad intelectual, entre otras. Estándares ITU (H.26~) stándares ISO (MPEG) 1 Figura 2.6: Evolución histórica del proceso de estandariración de compresión de vídeo. De igual manera, tampoco se ha incluido en la Figura 2.6 la extensión del estándar H.264/AVC conocida como SVC (Scalable Kdeo Coding), por estar en el momento de la escritura de esta Tesis en fase de desarrollo [SVC]. La idea que persigue dicha extensión del estándar es poder codificar una secuencia de vídeo a la mayor resolución espacio-temporal posible, pero permitiendo a los decodificadores realizar un proceso de decodificación escalonado, obteniendo así una secuencia decodificada con unas características espaciales y temporales acordes con la aplicación en uso y con las características del decodificador. Aunque esta posibilidad ya se había incluido de alguna manera en los estándares MPEG-2 y MPEG-4, la extensión SVC busca mejorar este proceso mediante la introducción de nuevas 2 Estado del arte de la codificación híbrido de vídeo técnicas y algoritmos de compresión optimizados para vídeo escalable [SMS+05], [SSM+05], [PKJ+06]. 2.1.2.3 Novedades en la etapa de estimación de movimiento durante el proceso de estandarización El desarrollo de los diferentes estándares mencionados en el apartado anterior ha llevado consigo la modificación y creación de nuevos algoritmos con el objetivo de llevar a cabo cada uno de los procesos propios del codificador híbrido de video de manera más eficiente, y como consecuencia, mejorar las prestaciones de éste. En este sentido, el hecho de que la etapa de estimación de movimiento sea la más influyente en cuanto a las variaciones de las prestaciones de compresión alcanzadas por un codificador híbrido de vídeo, ha determinado que los requisitos de dicha etapa sean cada vez más exigentes, particularmente a partir de la a~arición del estándar H.264/AVC. 2.1.2.3.1 Meioras en los estándares anteriores a H.264/AVC Tomando como punto de referencia el estándar H.261, las dos primeras variantes a considerar son la introducción de vectores de movimiento con precisión de medio píxel y los fotogramas bidireccionales por parte del estándar MPEG-1 Los vectores con precisidn de medio plxel se obtienen típicamente mediante un proceso de búsqueda en dos pasos. En el primero de ellos se obtiene un vector de movimiento con precisión de píxel (precisión entera) según el procedimiento descrito en el apartado 2.1.1.3. Una vez que se ha obtenido un vector con precisión entera, se realiza un refinamiento alrededor de las ocho posiciones situadas a una distancia de medio píxel de ésta, tal y como se muestra en la Figura 2.7, en la que se señalan únicamente las muestras de medio píxel que le 2.1 Codfcacón híbrda de video 2 corresponden al píxel situado en la esquina superior izquierda del macrobloque seleccionado por la búsqueda de precisión entera. [ Pixei Medio pixel \ Dirección de refinamiento ] Figura 2.7: Proceso de refinamiento de medio píxel a partir de las coordenadas del vector de movimiento con precisión entera. Las muestras de medio píxel necesarias para realizar el refinamiento, se calculan mediante interpolación bilineal, tal y como indica la Figura 2.8 Figura 2.8: Cálculo de muestras de medio píxel mediante interpolación bilineal. Los fotogramas bidireccionales (tipo B) son codificados usando la predicción de movimiento de dos fotogramas, un fotograma pasadoy otro futuro, pudiendo ser ambos tipo INTRA (tipo 1) o INTER (tipo P). Estos fotogramas no se utilizan en la predicción de otros fotogramas tipo B o P y por lo tanto, pueden tener más distorsión y ofrecer un factor de compresión más 2 Estado del arte de la codificación híbrido de video alto que los fotogramas I o P. Para codificar o decodificar una imagen tipo B, el codificador y el decodificador necesitarán la imagen I o P que la precede y la imagen P o I que la sigue. El orden de las imágenes será por tanto modificado antes de la codificación, de forma que el codificador y el decodificador dispongan, antes que las imágenes B, de las imágenes I y/o P necesarias para su procesamiento. Estas variaciones han resultado ser muy beneficiosas en términos de compresión y por ello han sido incorporadas de manera natural en todos los estándares posteriores. En cuanto al proceso de estimación de movimiento, las novedades más importantes por su impacto en los niveles de compresión alcanzados, aparte de las ya mencionadas, se localizan en los siguientes anexos del estándar H.263: Modo de vectores de movimiento no restringidos (Unrestricted Motion Vector Mode, Anexo D). Este modo opcional permite que los vectores de movimiento apunten fuera de un fotograma para macrobloques situados en los bordesdel fotograma actual. Este hecho ocurrirá cuando parte del área de búsqueda quede fuera del fotograma previamente codificado tomado como referencia, interpolando el estimador de movimiento los píxeles necesarios hasta completar el área de búsqueda. Modo de prediccidn avanzada (Advanced Prediction Mode, Anexo F). Este modo opcional considera la posibilidad de que en un macrobloque hayan diferentes objetos moviéndose en diferentes sentidos y velocidades. Debido a esta razón, se permite la posibilidad de que existan cuatro vectores de movimiento para un mismo macrobloque (un vector de movimiento por cada bloque de 8x8 píxeles de luminancia). De esta manera, el codificador calcula, además de un vector de movimiento para cada macrobloque según el procedimiento descrito anteriormente, cuatro vectores más para cada uno de los bloques de 8x8 píxeles con el consiguiente incremento del coste computacional del proceso de estimación de movimiento. En 2.2 Técncas de optmzacón lagrangana en codfcadores híbrdos de video 2 donde D(S,,I) y R(S,,I) representan, respectivamente, la distorsión total y el número de bits resultantes de codificar las Kmuestras del vector S, seleccionando para ello las opciones de codificación 1. Una solución elegante a este problema se obtiene mediante el desacoplamiento de la ecuación 2.7, lo que conduce a encontrar un conjunto de opciones de codificación / de manera que: (ec. 2.8) donde A es una constante positiva denominada constante o multiplicador de Lagrange y la función J(S,//A) a minimizar recibe el nombre de función de coste de Lagrange. La solución / que minimiza la función de coste es óptima en el sentido de que, si la constante R, se corresponde con el valor del multiplicador de Lagrange seleccionado, dicha solución garantiza mínima distorsión. Asumiendo que la distorsión y el número de bits son cantidades aditivas, y suponiendo que el valor de dichas cantidades depende única y exclusivamente de las opciones seleccionadas para codificar una muestra S, específica, la ecuación 2.8 se puede reformular de la siguiente manera: 2 Estado del arte de la codificación híbrido de vídeo De este modo, el problema descrito a través de la ecuación 2.7 puede ser resuelto de manera sencilla, seleccionando las opciones de codificación para cada una de las muestras S, de manera totalmente independiente. 2.2.2 Aplicación de las técnicas de optimización lagrangiana a codificadores híbridos de vídeo La implementación de las técnicas de optimización anteriormente descritas en codificadores híbridos de vídeo no es una tarea trivial, debido fundamentalmente a la multitud de opciones existentes para codificar cada uno de los fotogramas de la secuencia y al impacto que tienen las decisiones que se tomen en el resto del proceso de codificación de la secuencia de vídeo. Estas decisiones versan sobre aspectos tan críticos en un codificador de vídeo como la división del fotograma en conjuntos de píxeles con diferentes topologías; la posibilidad de codificar cada uno de estos conjuntos haciendo referencia a otros en el mismo o en un fotograma diferente, o decidir cuál es el conjunto de píxeles óptimo para hacer referencia a los píxeles de cada fotograma, entre otros. Como puede deducirse, el conjunto de posibilidades a explorar es amplísimo y por lo tanto, imposible de evaluar fielmente en tiempo real para una secuencia cualquiera en los sistemas de compresión de vídeo convencionales. Este hecho ha determinado que en los codificadores híbridos de vídeo basados en alguno de los estándares conocidos, el espacio de exploración se haya acotado con el objetivo de evaluar, mediante funciones de coste independientes, sólo aquellas opciones de codificación que mayor impacto presenten en las prestaciones de compresión. De esta manera, las opciones a evaluar resultan ser las relacionadas con la selección del modo de codificación y del conjunto de vectores de movimiento óptimo para cada macrobloque [WSJ+03], [KKA05]. 2.2 Técncas de optmzacón lagrangana en codfcadores híbrdos de vídeo 2 En particular, para el proceso de estimación de movimiento la función de coste J,,,,, a minimizar para cada macrobloque Skes la siguiente: (ec. 2.10) donde mv,representa el conjunto de vectores de movimiento posibles para el macrobloque S, Rm,,,,(Sk,mvk) es el número de bits necesarios para codificar dichos vectores de movimiento, y SAD (Sk,mvk) representa el SAD obtenido para los vectores de movimiento bajo análisis. En los estándares de codificación de vídeo, la codificación de los vectores de movimiento se realiza de forma diferencial con el objetivo de minimizar el número de bits R,,,,, necesarios para su transmisión. En el caso particular de los estándares H.263 y H.264/AVC, se codifica la diferencia entre el vector de movimiento calculado y un vector de movimiento predicho. Dicha predicción se obtiene, salvo para los macrobloques situados en los extremos de un fotograma, a partir de los vectores de los macrobloques vecinos M&, Mí?, y Mí?,,,,, señalados en la Figura 2.11 - Figura 2. I I : Macrobloquesvecinos utilizados en la predicción del vector de movimiento. 2 Estado del arte de la codificación híbrido de video Salvo para algunos casos particulares contemplados por ambos estándares (véase [H263, pp. 44-45] y [H264, pp. 129-1301), la predicción para el vector de movimiento del macrobloque que se está procesando se calcula como la mediana de los tres vectores vecinos anteriormente señalados. De esta manera, si los vectores de movimiento obtenidos para macrobloques vecinos son muy diferentes, el término Rm0,, aumentará drásticamente su valor, determinándose que el campo de vectores de movimiento obtenido es incoherente. Con respecto a la determinación del valor de la constante Amor,,, se han realizado un gran número de experimentos con un conjunto de secuencias de entrada altamente heterogéneo que han sido publicados en [WGOI] y [WSJ+03]. A partir de los resultados obtenidos, los autores proponen como valores óptimos del multiplicador de Lagrange Amor, para su aplicación en codificadores basados en los estándares H.263 y H.264/AVC, los siguientes: (ec. 2.11) Por último, es importante destacar que para estándares que permiten estimación de movimiento con tamaño de bloque variable, este proceso de minimización es doble, en el sentido de que no sólo se persigue encontrar para cada modo de estimación de movimiento cuáles son los vectores óptimos, sino también cuál de todos los modos posibles es el mejor para el macrobloque bajo análisis. El conjunto de vectores de movimiento que presente una JmOr,,mínima será el considerado para la predicción del macrobloque bajo proceso, siempre y cuando el modo de codificación elegido por el codificador para el citado macrobloque sea /N TER 2.3 Estado de arte en estmacón de movmento 2 2.3 Estado del arte en estimación de movimiento La estimación de movimiento constituye, sin lugar a dudas, la etapa dentro del proceso de codificación híbrida de vídeo sobre la que se ha realizado un mayor número de trabajos de investigación durante los últimos veinte años. Estos trabajos han centrado sus esfuerzos en dos aspectos: Obtener nuevos algoritmos de estimación de movimiento de bajo coste computacional que permitan obtener unas prestaciones de compresión similares a las ofrecidas por el algoritmo de búsqueda exhaustiva. De manera genérica, estos algoritmos reciben el nombre de algoritmos rápidos de estimación de movimiento. Desarrollar arquitecturas eficientes de estimación de movimiento para su posterior implementación en sistemas de compresión de vídeo en tiempo real. En este apartado se resumen los trabajos más significativos en estas dos áreas, poniendo de manifiesto las limitaciones encontradas en cada caso y que serán posteriormente abordadas en esta Tesis. 2.3.1 Algoritmos rápidos de estimación de movimiento El ingente número de publicaciones existente en este campo hace del todo inviable realizar, en el ámbito de esta Tesis, una recopilación exhaustiva de las propuestas realizadas durante las dos últimas décadas para la realización de la estimación de movimiento en codificadores híbridos de vídeo. En este sentido, se pueden encontrar recopilaciones de los algoritmos más significativos, entre otros, en los trabajos [FGWSG], [CH97], [KuhSS, pp.17-601, [DHOO], 2 Estado del arte de la codificación híbrido de video [ACB03], [L004], [HCT+O6] y [HuiOG], junto con una comparación de sus características en términos de calidad de imagen reconstruida y coste computacional asociado. De manera genérica, los algoritmos rápidos recogidos en estas publicaciones se pueden clasificar en: Algoritmos basados en la reducción del número de posiciones a evaluar. Estos algoritmos evalúan un subconjunto de candidatos dentro del área de búsqueda, seleccionado de manera dinámica las posiciones a evaluar a partir de los resultados parciales obtenidos. Para ello, se basan en la idea de que el SAD es una función monótona creciente, en el sentido de que su valor siempre aumenta a medida que la posición evaluada se aleja de la posición de mínimo SAD. Este hecho determina que estos algoritmos puedan quedar fácilmente atrapados en mínimos locales de la función SAD, proporcionando una pobre estimación de movimiento. Es de destacar que la mayor parte de los algoritmos rápidos de estimación de movimiento se encuentran dentro de este grupo. Algoritmos basados en la evaluación de metricas simplificadas. En este caso, se evalúan todas las posiciones del área de búsqueda haciendo uso de una métrica computacionalmente más sencilla que el SAD para determinar la posición ganadora, y por lo tanto, el vector de movimiento. Para ello, gran parte de los algoritmos dentro de este grupo proponen evaluar el SAD de cada posición sólo para un subconjunto de píxeles dentro del macrobloque [LZ93], [CS96], [WWKOO] o bien, reducir el número de bits asociado a cada píxel mediante truncamiento [LCL+02]. Algoritmos jerárquicos. Estos algoritmos se basan en realizar estimaciones de movimiento a diferentes niveles de resolución de imagen, desplazándose desde el nivel más bajo al más alto. De esta manera, se obtiene un primer vector de movimiento a partir del nivel más bajo, en el cual los bloques de píxeles son de dimensiones reducidas y por lo tanto, se puede establecer un área de búsqueda amplia. A partir de 2.3 Estado de arte en estmacón de movmento 2 esta primera estimación, se procede el refinamiento en los sucesivos niveles en los que, al ser los bloques de píxeles mayores, el área de búsqueda se va reduciendo proporcionalmente al tamaño del bloque. Normalmente, estos algoritmos suelen considerar entre dos y tres niveles dejerarquía [NKP+95], [LLS+01], [LL04]. Algoritmos predictivos. Los algoritmos predictivos se basan en la coherencia del campo de vectores de movimiento de una secuencia de vídeo y por lo tanto, en la idea de que los vectores de movimiento de los macrobloques situados en una vecindad espacio-temporal deben ser similares. En este sentido, este tipo de algoritmos evalúan sólo aquellas posiciones apuntadas por un conjunto de vectores cuidadosamente seleccionado de entre los calculados en el fotograma anterior y en los macrobloques procesados del fotograma actual [HBH+93], [CFP02], [TAL02]. Los algoritmos predictivos han recibido una especial atención en estos últimos años debido a que, para diferentes estándares de compresión de vídeo, presentan mejores prestaciones que la mayor parte de los algoritmos rápidos clasificados en otros grupos de los anteriormente mencionados [CFP02], [HCT+O6]. En particular, el algoritmo predictivo publicado en [CFP02] denominado algoritmo PBM (Predictive Block Matching) ha demostrado ser altamente eficiente en codificadores de vídeo basados en el estándar H.263, y por lo tanto, constituye una importante referencia en el marco de esta Tesis Doctoral. El algoritmo PBM realiza la estimación de movimiento en dos etapas. En la primera de ellas se evalúan las posiciones apuntadas por los cuatro vectores de movimiento correspondientes a los macrobloques señalados en la Figura 2.12 como MBmr,,,, MB,,,r,T~,, MB,efi,Ty Mí?,,. además de la posición apuntada por el vector (0,O). 2 Estado del arte de la codificación híbrido de video Figura 2.12: Vecindad espacio-temporal de vectores de movimiento utilizados por el algoritmo PBM en la primera etapa de estimación de movimiento. A partir de la posición apuntada por el mejor de los cinco vectores evaluados, se procede a una segunda fase de refinamiento en la que se evalúan las ocho posiciones alrededor del vector obtenido en la primera etapa que se muestran en la Figura 2.13, obteniéndose finalmente un vector de movimiento con precisión de medio píxel. I I . . m.. .l.. . ; . . .l.. 1 1 .m. I I I I PDIiciDn npintadn par la pimra ctap PmitiDn de refinamiento J Figura 2.13: Posiciones de refinamiento evaluadas en la segunda etapa del algoritmo PBM. 2.3 Estado de arte en estmacón de movmento 2 De forma general, la principal desventaja de los algoritmos rápidos de estimación de movimiento existentes radica en que, directa o indirectamente, realizan un conjunto de suposiciones acerca de la secuencia de vídeo a codificar con el objetivo de reducir el coste computacional del proceso de estimación de movimiento. No obstante, estas hipótesis de partida conllevan que las prestaciones de compresión alcanzadas por los algoritmos rápidos de estimación de movimiento, indistintamente del grupo al que pertenezcan, sean extremadamente dependientes de la naturaleza de la secuencia de vídeo a codificar. En este sentido, los algoritmos rápidos de estimación de movimiento pueden presentar una seria degradación de sus prestaciones en aquellas secuencias de vídeo con características diferentes de las suwestas. Este hecho ha motivado la búsqueda de nuevas soluciones para la realización del proceso de estimación de movimiento con un coste computacional reducido, pero manteniendo a la misma vez tasas de compresión altas para cualquier tipo de secuencia de vídeo. Esta es la finalidad de los denominados algoritmos de estimacidn de movimiento adaptativos, en los cuales el coste computacional del proceso de estimación de movimiento varía de acuerdo a las características de la secuencia de vídeo a comprimir. Sin embargo, a pesar de que se han publicado numerosos trabajos en este campo, los algoritmos propuestos hasta la fecha presentan, al menos, alguna de las siguientes limitaciones: El mecanismo de adaptacidn es exclusivo para tamaño de macrobloque. A pesar de que, desde la aparición de los estándares H.263 y MPEG-4, y muy especialmente a partir del advenimiento del estándar H.264/AVC, se realiza una apuesta clara por incorporar diferentes tamaños de bloque en el proceso de estimación de movimiento, una gran parte de los algoritmos de estimación de movimiento adaptativos realizan el cálculo de un solo vector de movimiento por macrobloque [CP96], [FLM+98], [MKCOO], [ANSOI], [BJVOI], [LCOI], [TLWOI], [MM02], [CTY+02], [Hos03], 2 Estado del arte de la codificación híbrido de video [MKD03], [YL03], [CHW04], [JLB+04], [CD05], [HCW05], [LJ1+05], [NM05], [AZL+O6]. Este hecho determina que, en principio, resulte obligatorio repetir el procedimiento fjado por estos algoritmos 5 y 41 veces para los estándares H.263/MPEG-4 y H.264/AVC respectivamente, por lo que la reducción en el coste computacional total es insignificante. Es de destacar que, en el caso de los algoritmos adaptativos basados en la modificación de parámetros asociados al proceso de búsqueda exhaustiva, los cuales se definirán a continuación, este bucle repetitivo no es necesario, al poderse reaprovechar los resultados parciales obtenidos con los bloques de píxeles de menor tamaño [LTV+05a]. lneficiente adaptacidn mediante ajuste dinámico del tamaño del área de búsqueda del algoritmo de búsqueda exhaustiva. Un gran número de los algoritmos adaptativos publicados recientemente se basan en la sencilla estrategia de reducir el área de búsqueda en aquellos macrobloques en los que, de algún modo, se determine que sólo es necesario evaluar un pequeño número de posiciones alrededor del vector cero [FLM+95], [OL98], [PB98], [MS99], [OLOO], [SM02], [SF04], [CCC05], [ZG05a]. Estos algoritmos son muy eficientes en el procesamiento, tanto de macrobloques sin movimiento (áreas de búsqueda muy reducidas) como de macrobloques con una gran cantidad de movimiento (áreas de búsqueda amplias). Sin embargo, en aquellos macrobloques con un grado de movimiento medio, el algoritmo de búsqueda exhaustiva requiere, por término medio, de un área de búsqueda de 24x24 píxeles para obtener unos resultados aceptables [SF04], lo cual supone la evaluación de 81 posiciones para obtener un vector de precisión entera. Para la inmensa mayoría de estos macrobloques, muchos de los algoritmos rápidos de estimación de movimiento son capaces de obtener un vector de movimiento de igual calidad realizando un número de operaciones considerablemente menor. Además, algunos de estos algoritmos proponen reajustar el área de búsqueda por fotograma en lugar de por macrobloque, lo que conlleva una pérdida apreciable en la calidad de la imagen 2.3 Estado de arte en estmacón de movmento 2 cuenta el impacto de inhabilitar un elemento de proceso que está calculando el SAD asociado a una posición de 4x4 píxeles, sobre los modos superiores. Determinar si los beneficios obtenidos en términos de ciclos inactivos son similares para el caso de arquitecturas con estimación de movimiento multimodo, particularmente para arquitecturas compatibles con el estándar H.264/AVC. Establecer, en términos de área ocupada, el coste hardware resultante de incorporar mecanismos de eliminación temprana de candidatos en arquitecturas de estimación de movimiento multimodo. En este punto, es importante señalar que en ninguna de las arquitecturas referenciadas con eliminación temprana, los autores ofrecen datos objetivos acerca de este aspecto. 3. Inexistencia de criterios en la agrupación de elementos de proceso. La inmensa mayoría de las arquitecturas bidimensionales dedicadas el cálculo de vectores de movimiento mediante búsqueda exhaustiva para el estándar H.264/AVC están compuestas por un matriz de 16x16 elementos de proceso y un árbol de sumas. Estos elementos de proceso funcionan como un solo grupo, de manera que la arquitectura es totalmenteagrupada. Las ventajas de esta agrupación de elementos de proceso son evidentes, al facilitarse enormemente la composición de los vectores de los modos superiores a partir de la obtención en paralelo de los SADs de cada uno de los bloques de 4x4 píxeles presentes en un macrobloque, sin necesidad de incorporar registros intermedios [HWH+03], [DGH+05], [KHC05], [WG05a]. En el caso de las arquitecturas unidimensionales, típicamente constituidas por un número de elementos de proceso menor, no existe un criterio claro a la hora de establecer grupos entre los elementos de proceso. Por lo tanto, resulta necesario estudiar las diferentes 2 Estado del arte de la codificación híbrido de video posibilidades de agrupación de elementos de proceso, así como su impacto en las prestaciones de la arquitectura. 2.3.2.2 Arquitecturas de estimación de movimiento con precisión sub-píxel A pesar de la importancia que posee el refinamiento de vectores a coordenadas sub-píxel en el estándar H.264/AVC, el número de publicaciones en esta área es muy reducido. De hecho, los trabajos más significativos se han centrado en los siguientes aspectos: Arquitecturas de refinamiento de vectores a coordenadas de medio píxel para estándares anteriores a H.264/AVC [GSJ +02], [SB03], [CCC04], [WYZ+04], [DRS05]. Obviamente, los requisitos de procesamiento en dichas arquitecturas son mucho menos exigentes, debido a que el número de modos de estimación de movimiento es menor (en estas arquitecturas sólo se contemplan tamaños de bloque de 16x16 y 8x8 píxeles) y sólo hay que realizar el refinamiento hasta coordenadas de medio píxel. Además, el método de interpolación bilineal implementado para generar las muestras de medio píxel es más sencillo que el filtrado propuesto por H.264/AVC. A partir del análisis de estas arquitecturas se observa que todas ellas son arquitecturas no agrupadas, en las que cada elemento de proceso evalúa una posición de refinamiento. Optimización del proceso de interpolación de muestras de medio y cuarto de píxel para decodificadores basados en el estándar H.264/AVC [LWW05], [SLG+05], [SN05], [HKL+06], sin necesidad de realizar el proceso de refinamiento propiamente dicho. 2.3 Estado de arte en estmacón de movmento 2 Para el caso particular del estándar H.264/AVC, sólo se han encontrado dos arquitecturas capaces de realizar dicho proceso de refinamiento según las directrices de dicho estándar. Dichos trabajos han sido publicados en [CHC04b] y [RB05], siendo relevante únicamente el primero de ellos. En este trabajo, realizado por Chen, Huang y Chen y publicado en [CHC04b], se presenta una arquitectura de refinamiento sub-píxel de vectores de movimiento como parte de un chip codificador en el que participan los autores [CCH+O6b]. Se trata de una arquitectura formada por 36 elementos de proceso en la que se ha incluido la lógica r. D D necesaria para seleccionar, según el criterio lagrangiano recomendado por el estándar N 6 .- L m c H.264/AVC, el mejor modo de estimación de movimiento al terminar el refinamiento de L" > .- c 3 cuarto de píxel para cada uno de los macrobloques de la secuencia de vídeo bajo análisis. Los m a - .- - autores presentan, junto con la arquitectura, un algoritmo denominado AMPD (Advanced e m o C1 Mode Pre-Decision) el cual, sobre la base de los resultados obtenidos durante la búsqueda 5 3 L 0 * con precisión entera, elige sólo tres de los siete posibles modos de estimación de movimiento m n N .- - m para los cuales se realizará el refinamiento sub-píxel a costa de una ligera pérdida de ? c :o m capacidad de compresión. De esta manera, y según los datos aportados por los autores, la .- - m c m .- O arquitectura es capaz de procesar 49K macrobloques por segundo a una frecuencia de trabajo m ? - de 100 MHz utilizando para ello 79,4K puertas NAND2 equivalentes. m m 0 - La segunda propuesta consiste en una arquitectura de refinamiento compuesta por 128 elementos de proceso (8 grupos de 16 elementos de proceso cada uno) que ha sido sintetizada sobre una FPGA modelo Virtex2 de Xilinx ocupando 14k slices y 28,5k LUTs, lo cual, a juicio de los autores, se corresponden con 225k puertas NAND2 equivalentes. Esta arquitectura, de manera contraria a la recomendación establecida por el estándar, realiza el proceso de búsqueda inspeccionado todas las posiciones contenidas en el área de búsqueda, independientemente de si éstas son de precisión entera o sub-píxel. Debido a este esquema de funcionamiento, esta arquitectura evalúa un número de posiciones de búsqueda elevadísimo y, como consecuencia directa, necesita interpolar un número de muestras sub-píxel que crece 2 Estado del arte de la codificación híbrido de vídeo de manera exponencial con el aumento del número de posiciones consideradas. Por último, es de destacar que los autores suponen que toda el área de búsqueda está pre-interpolada y ubicada en un conjunto de memorias consideradas para tal fin (no proponen ningún circuito de interpolación) y que además, no justifican los beneficios de buscar en todas las posibles posiciones en lugar de seguir el clásico esquema de búsqueda de precisión entera y posterior refinamiento sub-~íxel. Por último, es de resaltar el hecho de que en todos los trabajos mencionados, ya sea en arquitecturas de precisión entera o de precisión sub-píxel, el número de modos de estimación de movimiento evaluados es constante. En este sentido, las arquitecturas mencionadas no permiten incorporar los resultados aportados por numerosísimos trabajos que permiten reducir el número de modos de estimación de movimiento sin pérdidas apreciables en la calidad de la imagen reconstruida, entre los que destacan, entre otros, los publicados en [AKM+04], [JC04] y [WPL+05]. Por lo tanto, y puesto que estas estrategias han demostrado su validez en términos de compresión, resulta de interés investigar sus posibles beneficios en términos puramente arquitecturales. 2.4 Conclusiones En este capítulo se han establecido las bases de la codificación híbrida de vídeo haciendo especial hincapié, por su relevancia en esta Tesis, en el proceso de estimación de movimiento. En particular, se ha descrito la evolución de la etapa de cálculo de vectores de movimiento a lo largo del procedimiento de estandarización, revisándose asimismo las aportaciones más significativas al proceso de estimación de movimiento, tanto desde el punto de vista algorítmico como arquitectural. En primer lugar, se ha revisado la estructura interna de un codificador híbrido de vídeo genérico, pues constituye el núcleo básico de computación sobre el que se construyen los diferentes estándares de compresión de vídeo. En este análisis ha quedado de manifiesto la presencia de tres unidades funcionales claramente diferenciadas dentro del codificador: unidad de preproceso, unidad de reducción de redundancias espaciales y unidad de reducción de redundancias temporales, perteneciendo a esta última la etapa de estimación de movimiento. Igualmente, se han estudiado los requisitos impuestos por cada estándar a los vectores de movimiento calculados por macrobloque y en consecuencia, a los estimadores de movimiento. A partir de este estudio se concluye que el estándar H.264/AVC es el más exigente en cuanto al proceso de movimiento se refiere, al considerar un número variable de vectores de movimiento (entre 1 y 16) con precisión de cuarto de píxel por macrobloque que además, pueden apuntar a cualquiera de los cinco fotogramas previamente procesados por el codificador. c :o m Esta creciente diversificación de las alternativas relacionadas con el proceso de estimación de .- - m c m .- O movimiento en los estándares de compresión de vídeo, ha creado la necesidad de disponer de m ? - un conjunto de mecanismos que permitan decidir, para cada macrobloque, el mejor conjunto m m 0 - o - de opciones para maximizar la tasa de compresión alcanzada. Las técnicas de optimización a a 0 lagrangiana introducidas en este capítulo permiten seleccionar el conjunto de vectores óptimo n - a O O para cada macrobloque mediante la minimización de la función de coste J,,,,. El estudio de dicha función de coste será de especial relevancia en la definición del algoritmo adaptativo de estimación de movimiento que se desarrollará en el siguiente capítulo de esta Tesis. Por último, se han recopilado en este capítulo las aportaciones más significativas al proceso de estimación de movimiento. En dicha recopilación se ha prestado especial atención a los trabajos relacionados con estimación de movimiento adaptativa bajo los requisitos impuestos por el estándar H.264/AVC, tanto desde el punto de vista algorítmico como arquitectural. 2 Estado del arte de la codificación híbrido de video Como resultado, se ha puesto de manifiesto para ambos casos un conjunto de problemas que serán abordados en los siguientes capítulos y cuya solución representa, en gran medida, las aportaciones de esta Tesis. Propuestas algorítmicas de estimación de movimiento adaptativa La estimación de movimiento representa, sin lugar a dudas, la etapa crítica dentro de un co&ficador híbrdo de vlCeo debido a su elevado coste computacional e hfluencia en la tasa de compresión. Este hecho ha dado lugar al desarrollo de numerosos algorimos rápidos de estimación de movimiento porparte de la comunidad científica, los cuales presentan una reducción del coste computacional con respecto al algoritmo de búsqueda exhaustiva. Sin embargo, las prestaciones de compresión ofrecidas por dichos algorimos rápidos dependen extraordinariamente de las caracterljticas espaciales y temporales de la secuencia de vlCeo a comprimir. 3 Propuestas algorítmicas de estimación de movimiento adaptativa Con el objetivo de eliminar esta dependencia, se propone en este capítulo un nuevo algoritmo adaptativo de estimación de movimiento. Este algoritmo permite, mediante adaptación a las caracterljticas de la secuencia y a las exigencias del estándar en uso, obtener unos excelentes niveles de compresión para todo tipo de secuencias y tasas de transmisión, asegurando un coste computacional hferior al del algoritmo de búsqueda exhaustiva. Asimismo, el algoritmo propuesto supera las lNnitaciones encontradas en los trabajos previos que conforman el estado delarte en estimación de movimiento adaptativa. 3.1 Anóss de proceso de estmacón de movmento 3 3.1 Análisis del proceso de estimación de movimiento En el capítulo anterior ha quedado de manifiesto que en los sistemas de codificación híbrida de vídeo con prestaciones de tiempo real basados en algún tipo de estándar de compresión, la etapa de estimación de movimiento se realiza mediante ajuste de bloques (ver apartado 2.1.1.3). El número de vectores de movimiento, y en consecuencia los diferentes tamaños de bloque a considerar dentro de un macrobloque, así como la precisión de dichos vectores, dependerán del estándar que se utilice. En cualquier caso, cada codificador deberá decidir cuántos vectores de movimiento deberá enviar por macrobloque y qué algoritmo de ajuste de bloques utilizará para su cálculo. Para ello, las ecuaciones de optimización en términos de multiplicadores de Lagrange introducidas en el capítulo anterior resultan ser una solución eficiente. En esta sección se presenta un entorno de simulación que permite analizar de manera detallada el proceso de ajuste de bloques en términos de la ecuación de optimización de Lagrange aplicada al proceso de estimación de movimiento. A partir de este análisis, se extraerán una serie de conclusiones que serán claves en el diseño de la estrategia adaptativa de estimación de movimiento propuesta en esta Tesis. 3.1.1 Motivación del análisis El algoritmo de búsqueda exhaustiva obtiene las mayores tasas de compresión dentro de los algoritmos de ajuste de bloques mediante la evaluación de todas las posibles posiciones dentro del área de búsqueda. Sin embargo, el principal problema que presenta este algoritmo, aparte de su elevado coste computacional, es que se basa exclusivamente en minimizar una métrica de error (SAD), sin tener en cuenta la consistencia de los vectores de movimiento 3 Propuestas algorítmicas de estimación de movimiento adaptativa calculados [JZC03]. En el contexto de la estimación de movimiento, la consistencia del campo de vectores de movimiento se refiere al hecho de que no existan grandes diferencias entre vectores de movimiento de bloques vecinos, o dicho de otra manera, que el conjunto de vectores de movimiento obtenido sea "suave". Esta suposición está completamente justificada, pues, lo que no parece lógico es que bloques de píxeles que pertenecen a un mismo objeto dentro de una misma imagen presenten movimientos con velocidades y direcciones diametralmente opuestas. Sin embargo, y debido a los problemas ya mencionados del algoritmo de búsqueda exhaustiva, una situación muy común que se produce tras una estimación de movimiento basada en este algoritmo es la obtención de un conjunto vectores de movimiento que no reproducen fielmente el movimiento real existente en la secuencia de vídeo, pudiendo obtenerse para bloques vecinos resultados completamente dispares. Debido a que, tal y como y se ha explicado, en los estándares de compresión de vídeo los vectores de movimiento se codifican de forma diferencial con respecto a los vectores de bloques vecinos, este hecho conlleva que se emplee un número excesivo de bits para la transmisión de todos los vectores de movimiento correspondientes a un fotograma, y por lo tanto un considerable aumento del valor de la función de Lagrange J,,,,. Asimismo, la obtención de vectores de movimiento verdaderos - entendiéndose por vector de movimiento verdadero aquel que reproduce el movimiento real de la escena que se analiza - resulta ser de vital importancia en aplicaciones que cohabitan con los sistemas de compresión de vídeo. Ejemplos claros de estas aplicaciones, en las que las prestaciones globales del sistema dependen extraordinariamente de la veracidad de los vectores de movimiento, son: Aumento de la resolucidn temporal de la secuencia de vldeo. En muchas ocasiones, con el objetivo de aumentar la tasa de compresión obtenida o bien ante situaciones variables en el canal de transmisión, se submuestrea en la dimensión temporal la 3.1 Anóss de proceso de estmacón de movmento 3 Figura 3.2: Resultados del proceso de caracterización en función de los parámetros lntra - JAD y JAD - minpara Qp = 30. 3 Propuestas algorítmicas de estimación de movimiento adaptativa A partir de estas gráficas se extraen las siguientes conclusiones: Al aumentar el nivel de distorsión de la imagen recuperada con el aumento del escalón de cuantificación, el número de vectores erróneos es considerablemente mayor. De hecho, en el caso de estudio descrito, el porcentaje de vectores de movimiento verdaderos disminuye desde el 60.75% hasta el 38.23% al cambiar el escalón de cuantificación de Q,=2 a Q,=30. Debido a este aumento en el nivel de distorsión, los valores de SALmin son mayores a medida que aumenta el valor del escalón de cuantificación, indicando una menor similitud entre imágenes. Asimismo, los macrobloques de alta varianza espacial (valores de ha-SAD elevados) presentan altos valores de SAD-min, siendo este hecho más evidente a medida que aumenta el nivel de distorsión. Los macrobloques con valores altos de ha-SAD presentan un mayor grado de probabilidad de ser verdaderos, probabilidad que aumenta con la disminución del escalón de cuantificación. Este hecho, junto con el anterior, desmiente la clásica suposición de que un vector de movimiento que tiene asociado un alto valor de SALmines fruto de una mala estimación de movimiento. 3000 , ERROR -O , I OOOIf~~ ~ ;---:;-.-;;--,-;;--;- ~ ;--- .- E, iao ----N---- 4 ---- L ----,-----N---- 0 Q 3, .. ' ., 1000 ---- ; *-- 2-.& ----,L-- --N---- . .. ,'. :.! :.. ao -- : 7,Lif --- ;iy3e!:*. 4 . " , . , 3.1 Anóss de proceso de estmacón de movmento 3 Figura 3.3: Resultados del proceso de caracterización en función de los parámetros lntra - JAD y JAD - minpara Qp = 2. 3.1.3.2 Resultados de la veracidad de los vectores de movimiento en términos de Intro-SAD y SAD-deviotion Se presentan en las Figuras 3.4 (Q,=30) y 3.5 (Q,=2) las gráficas análogas a las anteriormente presentadas, pero esta vez en función de los parámetros Intra-SAD y SAL De viation. 3 Propuestas algorítmicas de estimación de movimiento adaptativa Figura 3.4: Resultados del proceso de caracterización en función de los parámetros lntra - JAD y JAD - deviationpara Qp = 30. Además de confirmar las conclusiones establecidas en el apartado anterior acerca del porcentaje de vectores de movimiento verdaderos en función del escalón de cuantificación, estas gráficas permiten extraer nuevas conclusiones: 3.1 Anóss de proceso de estmacón de movmento 3 Los macrobloques que presentan un alto valor de ha-SADtienen asociado un valor de SALdeviation elevado. A pesar de que en la magnitud del SAEmin existen notables diferencias entre los dos casos extremos del valor de cuantificación seleccionados, estas diferencias son menos apreciables en lo que respecta al valor de SA&deviation Dicho de otra manera, los bloques de alta varianza espacial presentan un alto valor de SAD-deviation, independientemente del nivel de compresión. 3 Propuestas algorítmicas de estimación de movimiento adaptativa Figura 3.5: Resultados del proceso de caracterización en función de los parámetros lntra - JAD y JAD - deviationpara Qp = 2. 3.1.3.3 Evolución del número de vectores de movimiento verdaderos con el nivel de compresión Como último resultado de esta caracterización se presenta, para tres secuencias de vídeo obtenidas a partir del entorno de simulación propuesto tomando el primer fotograma de las secuencias SUZIE, MISS AMERICA y COASTGUARD, la tendencia del número de vectores de movimiento verdaderos con el valor del escalón de cuantificación. Los resultados obtenidos se muestran en la Figura 3.6, confirmando claramente las afirmaciones establecidas en los apartados anteriores de esta misma sección 3.1.3. En este sentido, si se analizan los resultados obtenidos para un mismo valor del escalón de cuantificación, se constata que la mayor cantidad de vectores de movimiento verdaderos se obtiene para la secuencia con mayor actividad espacial, en este caso, la secuencia creada a partir del primer fotograma de SUZIE. Asimismo, se observa que para cualquiera de las tres secuencias de vídeo estudiadas, el número de vectores verdaderos obtenidos tras una estimación de movimiento por ajuste de bloques disminuye con el aumento del factor de cuantificación de manera no lineal. 3.1 Anóss de proceso de estmacón de movmento 3 Escaon de cuantificación Figura 3.6: Evolución del número devectoresverdaderos para las tres secuencias estudiadas. 3.1.4 Análisis de los resultados y conclusiones Los resultados obtenidos en el apartado anterior permiten establecer una serie de afirmaciones en cuanto al uso de un determinado algoritmo de estimación de movimiento por ajuste de bloques y su repercusión en la tasa de compresión. Así, analizando dichos resultados e interpretándolos en función de los parámetros propios de la ecuación de Lagrange para la estimación de movimiento, se establecen las siguientes conclusiones: En los bloques de alta actividad espacial, la evaluación de un número elevado de posiciones dentro del área de búsqueda es crltica. Los bloques que presentan un ha-SAD alto se caracterizan por tener asociado un elevado valor de SAD-deviation. Por lo tanto, si el algoritmo de ajuste de bloques no es capaz de encontrar la posición de mínimo SAD dentro del área de búsqueda, existen muchas probabilidades de que la función de coste J,,,, crezca drásticamente, independientemente del nivel de compresión con el que se esté trabajando. Este hecho ocurre con frecuencia en 3 Propuestas algorítmicas de estimación de movimiento adaptativa algoritmos rápidos de estimación de movimiento los cuales, debido a sus características intrínsecas de funcionamiento, quedan típicamente atrapados en mínimos locales. La aplicación del algoritmo de búsqueda exhaustiva resulta ser muy eficaz a la hora de proporcionar un vector de movimiento verdadero para este tipo de bloques, particularmente para valores bajos del escalón de cuantificación. Por lo tanto, al ser el movimiento real de las escenas generalmente suave, el término Rm0,, se beneficia también del uso de esta estrategia de búsqueda. En los bloques de baja actividad espacial, la obtencidn de un campo de vectores de movimiento homogeneo es crltica. Los bloques que presentan un ha-SAD bajo también presentan un valor de SALdeviation reducido. Este hecho determina que la aplicación de un algoritmo rápido no suponga un riesgo elevado en cuanto al crecimiento de la función de coste Jm0,,, pues el SAD asociado a una posición no mínima no distará demasiado del SA&mincorrespondiente a dicha posición de mínimo. Además, y de manera análoga a lo que ocurría en los bloques de alta actividad espacial, este hecho se da para todo el rango posible de valores del escalón de cuantificación. La obtención de un campo de vectores de movimiento homogéneo es crucial en estos bloques, pues de no ser así, el término R,,,, aumentará considerablemente. Este hecho se observa claramente en la Figura 3.7, en la cual se representa una imagen tipo P decodificadajunto con los vectores de movimiento asociados a cada uno de sus macrobloques. En las zonas resaltadas en dicha figura se observa que el conjunto obtenido de vectores de movimiento es altamente incoherente, provocando un considerable aumento en el número de bits necesario para la transmisión diferencial de los vectores 3 Propuestas algorítmicas de estimación de movimiento adaptativa embargo, conlleva un aumento excesivo del número de bits necesario para la transmisión de dichos vectores de movimiento. 3.2 Post-procesamiento de vectores de movimiento En el apartado anterior se ha expuesto la importancia de obtener un campo de vectores de movimiento coherente para la optimización de la tasa de compresión de un codificador híbrido de vídeo. Este hecho cobra especial relevancia en los bloques de baja actividad espacial, en los que la aplicación de un algoritmo de ajuste de bloques por búsqueda exhaustiva, si bien encuentra el mínimo SAD posible dentro del área de búsqueda, resulta claramente ineficiente en cuanto a la transmisión de los vectores de movimiento calculados. Por lo tanto, en codificadores de vídeo en los que se desee alta capacidad de compresión haciendo uso de un algoritmo de ajuste de bloques por búsqueda exhaustiva, resulta necesaria la modificación de los vectores obtenidos sin que ello suponga un detrimento en las prestaciones originales, independientemente de la secuencia de vídeo a comprimir. Una solución a este problema podría obtenerse mediante la aplicación de etapas de postprocesamiento de los vectores de movimiento. En este apartado se analiza esta posibilidad y se detallan los resultados de su aplicación a las secuencias que se utilizan como elementos de prueba. 3.2.1 Estrategia de post-procesamiento propuesta La etapa de post-procesamiento propuesta, la cual ha sido publicada en la revista internacional IEEElectronics Letters [LCL+03b] y en la revista de ámbito local Vector Plus [LCL+05a], se basa en realizar un filtrado del vector de movimiento obtenido. Para ello, se 3.3 Propuestas algorítmcas para a estmacón de movmento 3 satisfactorio se ejecuta el algoritmo de búsqueda exhaustiva, tal y como se muestra en la Figura 3.11 Algoritmo FSBM ~Vector movimiento satisfactorio? I finalizada Figura 3.1 1 : Esquema general de decisión dentro de la estrategia adaptativa. 3.3.2 Parámetros necesarios y criterios de decisión adaptativos Una vez establecidas las líneas básicas de la estrategia de estimación de movimiento adaptativa, es necesario identificar un conjunto de parámetros que permita establecer, de manera sencilla, un criterio de decisión acerca de la validez del vector de movimiento obtenido por el algoritmo predictivo. Tal y como se muestra en la Figura 3.11, estos parámetros deberán proveer información acerca de tres factores: Necesidades de la aplicacibn. Obviamente, mientras mayor sea el número de bloques para los que el vector de movimiento calculado por el algoritmo predictivo es satisfactorio, menor será el coste computacional asociado. Sin embargo, para la inmensa mayoría de los casos, esta disminución del coste computacional llevará consigo una disminución de las prestaciones de compresión del codificador. 3 Propuestas algorítmicas de estimación de movimiento adaptativa Caracterlsticas de la secuencia de vldeo a comprimir. Una vez fgadas las necesidades de la aplicación, la adaptación a las singularidades de la secuencia a comprimir resulta clave para realizar un uso eficiente de los recursos de cómputo. Para ello, un parámetro clave es el Intra-SAD del bloque de referencia pues, tal y como ha quedado demostrado, su valor es indicativo de las probabilidades de éxito de un algoritmo de naturaleza predictiva. En particular, si el valor de Intra-SADes bajo, el algoritmo PBM resulta una opción muy eficiente, decreciendo sus prestaciones a medida que el valor de lntra-SADaumenta. Calidad del vector de movimiento calculado por el algoritmo PBM. Por último, es necesario evaluar de manera precisa la idoneidad del vector proporcionado por el algoritmo predictivo. Para este propósito, se inspecciona la magnitud del SAD del vector de movimiento calculado por el algoritmo PBM (de aquí en adelante SAD-PBM), pues mientras menor sea el SAD-PBM, menor será la función coste lagrangiana asociada a ese vector. Con estos parámetros, y puesto que ya ha quedado de manifiesto en el presente capítulo que la valoración de una determinada estrategia de estimación de movimiento no debe estar basada exclusivamente en métricas de error, se establece como criterio de decisión la evaluación de la suma de los parámetros lntra-SADy SAD-PBM, tal y como se indica en la Figura 3.12. 3.3 Propuestas algorítmcas para a estmacón de movmento 3 1 Algoritmo PBM 1 Estimación de Algoritmo FSBM < comm movimiento I finalizada Figura 3. 12: Esquema de decisión dentro de la estrategia adaptativa en función de los parámetros seleccionados. 3.3.3 Resultados de la estimación de movimiento adaptativa Tal y como se ha expresado en el apartado anterior, el criterio de decisión vendrá determinado por una constante, C, que denominaremos constanteadaptativa. A continuación se presentan los resultados obtenidos con el criterio de decisión fgado previamente para diferentes valores de esta constante. En particular, los resultados se han obtenido con secuencias de muy diferentes características espaciales y temporales en las que todos los fotogramas, excepto el primero, han sido codificados en modo INTER con un codificador H.263. Los vectores de movimiento se han calculado con precisión de medio píxel sobre bloques de 16x16 píxeles con un área de búsqueda, en el caso de aplicar el algoritmo de búsqueda exhaustiva, de 46x46 píxeles (pl=p2=15). Asimismo, con el objetivo de evaluar la bondad del criterio de decisión para tasas de transmisión bajas, todas las secuencias han sido codificadas para valores del escalón de cuantificación entre 30 y 16. En todos los casos, se han elegido secuencias de tamaño QCIF muestreadas a 10 fotogramas por segundo debido a que, bajo estas condiciones de baja tasa de muestreo, la hipótesis de que el movimiento en 3 Propuestas algorítmicas de estimación de movimiento adaptativa una secuencia de vídeo es suave y continuo pierde consistencia, y por lo tanto, se puede observar un alto porcentaje de casos en los que el algoritmo predictivo no es eficaz. Una vez fjado el criterio de decisión para estas condiciones, se investigará si es igualmente válido para tasas de transmisión y de muestre0 temporal mayores. En la Figura 3.13 se muestran los resultados obtenidos para las secuencias CARPHONE, FOREMAN, MISS AMERICA y TABLE para los siguientes valores de la constante adaptativa: C = O, 5000,10000,15000 y 20000. CARPHONE 13 18 23 28 Taia de transmisión (kbpi) FOREMAN 18 23 28 33 38 Taia de transmisión (kbpi) TABLE z a 335 320 5 6 7 8 9 15 20 25 30 35 Tasa de transmisión (kbpi) Tasa de transmisión (kbpi) Figura 3.13: Resultados de compresión para diferentes valores de la constante adaptativa. 3.3 Propuestas algorítmcas para a estmacón de movmento 3 A partir de estas gráficas se extraen las siguientes conclusiones: Para tasas bajas de transmisión, las mejores prestaciones de codificación se obtienen para los valores de constante C = 5000 y C = 10000, incluso superiores a las obtenidas con C = O. Por lo tanto, con estos valores se consigue inyectar una relación adecuada de vectores de movimiento obtenidos con el algoritmo predictivo que hacen que la función global de coste JmOr,,disminuya. Para tasas de transmisión mayores, las mejores prestaciones de codificación se obtienen para los valores de constante C = O y C = 5000. Al bajar el valor del escalón de cuantificación, el peso asignado al término Rm0,, disminuye y por lo tanto, cobra mucho mayor protagonismo dentro de la función de coste el SAD correspondiente al vector calculado. Las diferencias en las curvas de prestaciones provocadas por cambios en el valor de la constante son mucho más apreciables en el caso de secuencias con elevado movimiento y/o alta actividad espacial (FOREMAN y TABLE) que para el caso contrario (Miss AMERICA), en el cual apenas existen variaciones entre las curvas correspondientes a diferentes valores de la constante. Con el objetivo de completar el análisis de los resultados obtenidos, se presentan en la Figura 3.14 el coste computacional (en términos del número medio de posiciones evaluadas por macrobloque dentro del área de búsqueda) obtenido para cada uno de los casos y secuencias estudiadas. 3 Propuestas algorítmicas de estimación de movimiento adaptativa CARPHONE ~20000 + 15000 -N10000 -5000 -0 , 15 18 21 21 27 30 Escalón de cuantificación MISS AMERICA 15 18 21 21 27 30 Escalón de cuantificación FOREMAN Escalón de cuantificación TABLE Escalón de cuantificación Figura 3.14: Número medio de posiciones evaluadas por macrobloque para diferentes valores de la constante adaptativa. Como era de esperar, el número de posiciones evaluadas disminuye a medida que aumenta el valor de la constante. Además de esta evidencia, a partir de la observación de estas gráficas se puede afirmar lo siguiente: El número de posiciones evaluadas permanece estable aunque varíe el valor del escalón de cuantificación, y por lo tanto, el nivel de compresión. 3.3 Propuestas algorítmcas para a estmacón de movmento 3 Para cada uno de los valores de la constante analizados, el menor coste computacional se obtiene para aquellas secuencias con poco movimiento y/o poca actividad espacial, como es el caso de la secuencia Miss AMERICA. 3.3.3.1 Ajuste de la constante adaptativa con Qp Con el objetivo de alcanzar siempre unas determinadas prestaciones de compresión, se introduce un ajuste cuadrático con Q,de la constante adaptativa: Como puede observarse, el valor de la constante adaptativa aumenta rápidamente con el nivel de compresión. Asimismo, con la finalidad de poder ajustar fácilmente su valor según las prestaciones requeridas, los parámetros a y p permiten realizar, respectivamente, un ajuste fino y un ajuste grueso del valor de esta constante. Con el objetivo de evaluar los cambios en las curvas correspondientes a las Figuras 3.13 y 3.14 mostradas anteriormente, se han fgado los valores de a y p de tal manera que se consigan, como mínimo, las mismas prestaciones que con C = O (equivalente a elegir siempre el vector de movimiento calculado por el algoritmo de búsqueda exhaustiva). 3 Propuestas algorítmicas de estimación de movimiento adaptativa CARPHONE Taia de transmisión (kbpi) FOREMAN Taia de transmisión (kbpil MISS AMERICA TABLE Tasa de tranirniiion (kbpi) Tasa de tranimiiion (kbpi) Figura 3.1 5: Resultados de compresión con ajuste de la constante adaptativa con Qp. Para ello, y tras realizar numerosas simulaciones para satisfacer la condición impuesta, se fjan los valores a = 1000 y P = 8, obteniéndose las curvas de compresión mostradas en la Figura 3.15. En esta figura se comparan las prestaciones obtenidas en los casos límite C = O (siempre se elige el vector proporcionado por el algoritmo FSBM) y C = 20000 (prácticamente igual a elegir siempre el vector proporcionado por el algoritmo PBM), con las obtenidas mediante el ajuste de la constante adaptativa con Q,. Los valores de a y /se han fjado con el objetivo de obtener, para cada valor posible del escalón de cuantificación, un valor de la constante adaptativa que ofrezca prestaciones de compresión óptimas para cualquier secuencia de vídeo según lo establecido en la Figura 3.13. Asimismo, la relación 3.3 Propuestas algorítmcas para a estmacón de movmento 3 cuadrática de la constante adaptativa con el escalón de cuantificación permite evitar la rápida pérdida de calidad que se produce en secuencias de vídeo con movimientos caóticos (como es el caso de FOREMAN) para valores altos de la mencionada constante a medida que aumenta el valor de Q, manteniendo el coste computacional por debajo del exhibido por el algoritmo de búsqueda exhaustiva. De esta manera, al introducir una constante ajustable se alcanza el objetivo de conseguir unas prestaciones de compresión máximas y constantes, en el sentido de que siempre se alcanzan las prestaciones máximas de compresión si se seleccionan adecuadamente los valores de los parámetros a y p Este objetivo se obtiene realizando un esfuerzo computacional variable, tal y como se muestra en la Figura 3.16. A partir del estudio de estas gráficas, se puede observar cómo el algoritmo propuesto cumple con uno de los objetivos de esta Tesis, que no es otro que la doble adaptación del coste computacional a las necesidades de compresión y a las características de la secuencia de vídeo a comprimir: Adaptacibn a las necesidades de compresibn. Como puede observarse, para cada secuencia individual el coste computacional varía con el valor del escalón de cuantificación, manteniendo siempre unos requisitos de máxima compresión. Adaptacibn a la secuencia a comprimir. Para lograr este objetivo, el algoritmo realiza un uso inteligente de los recursos, obteniéndose un coste computacional acorde con las peculiaridades de la secuencia a comprimir. 3 Propuestas algorítmicas de estimación de movimiento adaptativa Escalón de cuantificación FOREMAN -20000 cC(1000.80pJ +O - 15 18 21 21 27 30 Escalón de cuantificación Escalón de cuantificación Escalón de cuantificación Figura 3.16: Número medio de posiciones evaluadas por macrobloque con ajuste de la constante adaptativa con Qp. Sin embargo, a pesar de que el objetivo de la doble adaptabilidad está cumplido, todavía se puede reducir el coste computacional global de la solución aportada. Para ello, habrá que tener en cuenta el hecho de que en algunas ocasiones el algoritmo PBM proporciona un vector válido aunque no se cumplan las especificaciones establecidas por el criterio de decisión 3.3 Propuestas algorítmcas para a estmacón de movmento 3 CARPHONE. 5 fps Taia de transmisión (kbpi] MISS AMERICA, 5 fps """"""""J 6 26 16 66 86 Taia de transmisión (kbpi) FOREMAN. 5 fps Taia de transmisión (kbpi] TABLE. 5 fps 20 m 120 170 220 Taia de transmisión (kbpi) Figura 3.22: Prestaciones de compresión con factores de cuantificación bajos para secuencias muestreadas a 5 fotogramas por segundo. A partir de estas gráficas, y de los resultados anteriores, se deduce que el algoritmo ACBM es capaz de obtener las mejores prestaciones de compresión independientemente del escalón de cuantificación utilizado. Por lo tanto, la solución final propuesta es capaz de adaptar automáticamente el coste computacional, no sólo a las características espaciales y temporales de la secuencia de vídeo a comprimir, sino también al nivel de compresión a obtener. 3 Propuestas algorítmicas de estimación de movimiento adaptativa 3.3.4.3 Coste computacional de la solución propuesta Por último, en la Figura 3.23 se muestra el coste computacional, en términos del número medio de posiciones evaluadas por macrobloque, asociado a la solución propuesta para los dos casos extremos de muestre0 temporal estudiados. Escalón de cuantificación Escalón de cuantificación MISS AMERICA TABLE 1 1 7 10 13 16 19 22 25 28 31 1 1 7 10 13 16 19 22 25 28 31 Escalón de cuantificación Escalón de cuantificación Figura 3.23: Número medio de posiciones evaluadas por macrobloque con criterio de decisión dinámico. 3.3 Propuestas algorítmcas para a estmacón de movmento 3 A partir de estas gráficas se extraen las siguientes conclusiones: El algoritmo propuesto es capaz de adaptar automáticamente el coste computacional a las características espaciales y temporales de la secuencia a comprimir. En particular, a medida que disminuye la tasa de muestreo, el algoritmo incrementa el esfuerzo computacional debido al empeoramiento de las prestaciones del algoritmo predictivo. En todos los casos, el coste computacional es claramente inferior al asociado al algoritmo FSBM. Sin embargo, y tal y como se ha demostrado anteriormente, las prestaciones de compresión obtenidas son ligeramente superiores. El coste computacional obtenido no crece monótonamente con el valor del escalón de cuantificación. Este hecho es debido a que, a medida que decrece el nivel de distorsión, los vectores de movimiento óptimos para compresión se asemejan en mayor medida a los vectores que reproducen el movimiento real de la escena y por lo tanto, existe mayor probabilidad de que entre el conjunto de posiciones calculadas por el algoritmo predictivo, exista al menos una satisfactoria. 3.3.5 Reducción del coste hardware asociado al algoritmo ACBM propuesto El algoritmo ACBM propuesto en esta Tesis representa una estrategia eficaz de estimación de movimiento y, tal como se ha mostrado, permite obtener unas excelentes prestaciones mediante la adaptación del esfuerzo computacional a las características de la secuencia de vídeo y a las necesidades de compresión. Sin embargo, ciertas aplicaciones requieren que el hardware utilizado sea de bajo coste. En este sentido el algoritmo ACBM, propuesto como 3 Propuestas algorítmicas de estimación de movimiento adaptativa una combinación del PBM y del FSBM, presenta un conjunto de características que dificultan la utilización de un hardware reducido. Entre ellas las más importantes son las siguientes: El algoritmo PBM toma los vectores correspondientes a la vecindad espacio-temporal en coordenadas de medio plxel. Este hecho hace que, cada vez que se calcule el SAD de uno de los candidatos elegidos, sea necesario interpolar la zona a la que dicho vector candidato apunta. El algoritmo PBM evalúa durante la fase de refinamiento posiciones de plxel y medio plxel indistintamente. Esta característica del algoritmo PBM dificulta en gran medida su implementación, pues en las arquitecturas de estimación de movimiento se realiza de manera separada la búsqueda con precisión entera y la búsqueda sub-píxel, dependiendo esta última del vector de movimiento obtenido con precisión entera. El área de búsqueda. en el caso de que se tenga que ejecutar el algoritmo FSBM. resulta ser de 46x46 plxeles @,= p,= 15). Puesto que cada píxel esta codificado con 8 bits, el tamaño de la memoria cache necesaria para el almacenamiento del área de búsqueda es de 16928 bits. Además, el número de posiciones a evaluar para cada macrobloque sobre el que se decide ejecutar el algoritmo de búsqueda exhaustiva es de (p, + p, + l)', más 8 posiciones para obtener un vector de coordenadas de medio píxel. Con el objetivo de reducir el coste de la implementación hardware del algoritmo ACBM, manteniendo la calidad del resultado final, en esta Tesis se proponen realizar las siguientes modificaciones en los algoritmos PBM y FSBM: 3.3 Propuestas algorítmcas para a estmacón de movmento 3 Se reduce el número de vectores candidatos a evaluar durante la primera fase del algoritmo PBM. En lugar de elegir cuatro vectores a partir de la vecindad espaciotemporal del macrobloque bajo análisis, se seleccionan sólo tres. En particular, se eligen los vectores de los macrobloques superior e izquierdo dentro del mismo fotograma, así como el vector correspondiente a la misma posición de macrobloque en el fotograma anterior (macrobloques Mí3 ,,, y Mí3 ,, ,, en la terminología de la Figura 2.12). La elección de estos vectores se debe a que son los que presentan mayor correlación espacio-temporal con el vector de movimiento a calcular [CFP02]. Los cuatro vectores candidatos elegidos durante la primera fase del algoritmo PBM, asl como las posiciones correspondientes a la segunda fase de refinamiento, han de estar en coordenadas de plxel. De esta manera, y tras la evaluación de los tres vectores de la vecindad espacio-temporal más el vector cero, se procede a la fase de refinamiento en la forma en la que se indica en la Figura 3.24 (b), sustituyendo la fase original de refinamiento mostrada en la Figura 3.24 (a). El refinamiento a coordenadas sub-plxel es común para ambos algoritmos. Una vez evaluadas las doce posiciones correspondientes al algoritmo PBM, se determina si el vector de coordenadas de píxel obtenido es satisfactorio. En caso afirmativo, se procede al refinamiento a coordenadas de medio píxel y se concluye la estimación de movimiento. En caso contrario, se realiza la búsqueda exhaustiva con precisión entera, realizándose después el correspondiente refinamiento de medio píxel. 3 Propuestas algorítmicas de estimación de movimiento adaptativa r Porición apuntada por la primera etapa (coordenadas de pixcl o de medio pixg 1 I I ..e... l.. *... l..... I I I I I I r Posición apuntada por la primera ctapa (coomlcnadar de pixc) Posición de refinamiento Pmición de refinamiento (cowdcnadas de pixel o de medio pix<ll (<oordenadar de pkc) (4 (b) Figura 3.24: Etapa de refinamiento en el algoritmo PBM (a) y propuesta de modificación para reducir el coste hardware asociado (b). En los casos en los que se tenga que ejecutar el algoritmo FSBM, el área de búsqueda se reduce a 31x31 plxeles. De esta manera, el tamaño de la memoria interna del estimador de movimiento será de 7688 bits y el número de posiciones a evaluar dentro del área de búsqueda será igual a 256 Este nuevo algoritmo predictivo propuesto, cuyo coste de implementación es significativamente menor que el correspondiente al algoritmo PBM original, se denominará, en el marco de esta Tesis, algoritmo PBM-HW (Predictive Block MatchingHardWare). De manera análoga, el algoritmo adaptativo que hace uso de dicho algoritmo predictivo PB M-H W se denominará ACBM-HW (Adaptive Cost Block MatchingHardWare) ). Llegados a este punto, es necesario evaluar las prestaciones del algoritmo ACBM con las modificaciones introducidas. Dicha evaluación se muestra gráficamente en la Figura 3.25, en la cual se han utilizado las secuencias de estudio muestreadas a 10 fotogramas por segundo, 3.3 Propuestas algorítmcas para a estmacón de movmento 3 presentándose también los resultados obtenidos con las dos áreas de búsqueda definidas. En estas gráficas se constata que las modificaciones del algoritmo ACBM no conllevan pérdidas apreciable en las prestaciones de compresión con respecto al original salvo para el caso de la secuencia con mayor cantidad de movimiento, esto es, la secuencia FOREMAN. Sin embargo, y tal y como se puede observar en la gráfica correspondiente a esta secuencia, este empeoramiento está motivado única y exclusivamente por la disminución del tamaño del área de búsqueda. A partir de este resultado, se puede afirmar que las modificaciones introducidas sobre el algoritmo PBM con el objetivo de facilitar su posterior implementación hardware, no conlleva pérdidas apreciables en las prestaciones del algoritmo ACBM final. CARPHONE FOREMAN 310 XFSBM (46x46) -ACBM~HW tFSBM(31x31I 13 18 23 28 Taia de transmisión (kbpi) XFSBM (46x46) tFSBM (31x311 Taia de transmisión (kbpi) !!. 18 23 28 33 38 Taia de transmisión (kbpi) TABLE Figura 3.25: Comparación de prestaciones de compresión entre el algoritmo ACBM original y ACBM modificado 3 Propuestas algorítmicas de estimación de movimiento adaptativa Para completar el análisis efectuado en este apartado, se muestra en la Figura 3.26 el coste computacional de la versión modificada del algoritmo ACBM, comprobándose la considerable reducción en el número medio de posiciones evaluadas. CARPHONE 15 18 21 21 27 30 Escalón de cuantificación 15 18 21 21 27 30 Escalón de cuantificación FOREMAN 15 18 21 21 27 30 Escalón de cuantificación TABLE 15 18 21 21 27 30 Escalón de cuantificación Figura 3.26: Número medio de posiciones evaluadas por macrobloque en la solución final adoptada. 3.4 Estmacón de movmento adaptatva para bloques de topología varobe 3 3.4 Estimación de movimiento adaptativa para bloques de topología variable En el apartado anterior se han mostrado los resultados obtenidos con la estrategia diseñada para estimación de movimiento en macrobloques (16x16 píxeles), usando para su validación el estándar H.263. Sin embargo, tanto en este estándar como en H.264/AVC, se introduce la posibilidad de realizar la estimación de movimiento para diferentes tamaños dentro de un mismo macrobloque (estimación de movimiento multimodo). En particular, el estándar H.263 soporta de manera opcional que un macrobloque pueda codificarse haciendo uso de un solo vector de movimiento o de 4 vectores de movimiento, uno para cada bloque de 8x8 píxeles. Asimismo, tal y como se recoge en el capítulo anterior, el estándar H.264/AVC permite dividir un macrobloque de siete maneras diferentes, de forma que un macrobloque pueda tener asociado un número de vectores de movimiento variable comprendido entre 1 y 16. En este apartado se presentan las modificaciones realizadas en el algoritmo ACBM con el objetivo de obtener vectores de movimiento para tamaños de bloque variables siguiendo la misma estrategia adaptativa. Igualmente, se presentan los resultados obtenidos con las modificaciones introducidas para el caso de los estándares H.263 y H.264/AVC, utilizando para ello las secuencias habituales de test. 3.4.1 Análisis de la utilización de bloques de tamano variable en la codificación híbrida de vídeo En general y de manera muy resumida, el algoritmo ACBM descrito hasta ahora considera que el vector proporcionado por el algoritmo predictivo es satisfactorio cuando se produce alguna de estas dos condiciones: 3 Propuestas algorítmicas de estimación de movimiento adaptativa El macrobloque de referencia presenta un alto grado de homogeneidad. Este hecho se controla dentro del algoritmo mediante la inspección del parámetro Intra-SAD, favoreciendo el vector obtenido por el algoritmo predictivo. El macrobloque de referencia presenta un excelente encaje con respecto a alguna posición del área de búsqueda. Para ello, se evalúa el SAD asociado al vector obtenido por el algoritmo PBM (SAD-PBM), determinando si éste es lo suficientemente pequeño como para que el vector obtenido se considere satisfactorio en términos de compresión Además de estas características, en la adaptación del algoritmo ACBM para su utilización en estimación de movimiento con bloques de tamaño variable, se ha estudiado la frecuencia con la que los estándares H.263 y H.264/AVC utilizan las diferentes topologías de bloque. Para ello, y puesto que el estándar H.264/AVC contempla un mayor número de posibilidades en cuanto a los tamaños y formas de bloque, se ha analizado la probabilidad de que un macrobloque tipo INTER sea codificado haciendo uso de un patrón determinado. En particular, se ha utilizado un codificador H.264/AVC en su perfilbásico (baseheprofle) con las secuencias de estudio muestreadas a 10 fotogramas por segundo, empleando en la estimación de movimiento el algoritmo de búsqueda exhaustiva con un área de búsqueda de 31x31 píxeles. Los resultados obtenidos se muestran en las gráficas de la Figura 3.27, representándose en el eje izquierdo el porcentaje de macrobloques que han sido codificados con una única partición (16x16) y en el eje derecho la tasa de transmisión obtenida en la codificación de la secuencia con el escalón de cuantificación seleccionado. actividad espacial, en los que sólo es necesario evaluar un número reducido de candidatos, siempre y cuando se garantice que el vector de movimiento resultante sea coherente con respecto a los de los macrobloques vecinos, pues de lo contrario, se incrementaría el número de bits R,,,,. A raíz de las conclusiones extraídas, se ha propuesto una etapa de post-procesamiento de vectores de movimiento que permite aumentar ligeramente las prestaciones de compresión obtenidas mediante el algoritmo de búsqueda exhaustiva para cualquier tipo de secuencia. Esta etapa de post-procesamiento resulta de utilidad en estimadores de movimiento por búsqueda exhaustiva, pues permite obtener un conjunto de vectores de movimiento que reproducen de manera más fidedigna el movimiento real en la escena, corrigiendo los defectos del algoritmo exhaustivo en zonas de baja actividad espacial. De esta manera, se obtienen beneficios en aplicaciones complementarias al proceso de decodificación, tales como corrección de errores, transcodificación, o aumento de la resolución espacio-temporal de la secuencia de vídeo comprimida. L 0 - Con el objetivo de obtener una solución de coste computacional reducido, se ha propuesto el m m 0 - algoritmo ACBM. En este algoritmo se introduce una constante adaptativa que, al depender directamente del valor del escalón de cuantificación Q, permite establecer un compromiso entre el coste computacional y el nivel de compresión. Los resultados obtenidos demuestran que el algoritmo ACBM, evaluando un número de posiciones significativamente menor, es capaz de obtener unas prestaciones de compresión iguales a las ofrecidas por el algoritmo de búsqueda exhaustiva para todo el rango de valores posibles de Q, con secuencias de muy diferentes características espaciales y tasas de muestre0 temporal (desde 5 hasta 30 fotogramas por segundo). Asimismo, se han introducido un conjunto de modificaciones en el algoritmo ACBM que facilitarán en gran medida su posterior implementación hardware, sin que esto conlleve una degradación de sus prestaciones. Dicha implementación es abordada en 3 Propuestas algorítmicas de estimación de movimiento adaptativa el siguiente capítulo, introduciéndose durante su desarrollo las aportaciones arquitecturales de esta Tesis. Por último, se ha propuesto un nuevo algoritmo denominado VBS-ACBM (Variable Block SkeAdaptive Cost Block Matching) para estándares con estimación de movimiento con bloques de tamaño variable, incluyendo el estándar H.264/AVC con sus siete modos de estimación de movimiento. Al conservar las características del algoritmo ACBM anteriormente mencionadas, el nuevo algoritmo VBS-ACBM representa una importante contribución en el área de la estimación de movimiento adaptativa, al eliminar las deficiencias encontradas en trabajos previos garantizando, a la misma vez, unas prestaciones de compresión óptimas para todo tipo de secuencias. Arquitecturas multiestándar de estimación de movimiento adaptativa En el capítulo anterior se ha demostrado que el algoritmo VBS-ACBM aportado representa, mediante la adaptación del esfuerzo computacional a las caracterljticas espacio-temporales de la secuencia a comprimir, una eficaz solución para realizar la estimación de movimiento en codificadores híbrdos que permitan el uso de vectores de movimiento multhodo. Sin embargo, para su utilización en aplicaciones con restricciones de funcionamiento en tiempo real, es necesario aportar nuevas soluciones arquitecturales adecuadas a la hplementación del proceso de estimación de movimiento según las directrices delalgoritmo VBS-ACBM de manera eficiente. 4 Arquitecturas multiestándar de estimación de movimiento adaptativa En este capítulo se proponen nuevas soluciones arquitecturales adaptadas al algoritmo VBS-ACBM mediante la división del cálculo de vectores de movimiento en dos procesos: estimación de movimiento con precisión entera yposterior refinamiento sub-plírel. As/; en esta Tesis se propone una nueva arquitectura unidimensional agrupada de estimación de movimiento con precisión entera mediante búsqueda predictiva/exhaustiva, que permite obtener los vectores de movimiento correspondientes a un macrobloque de acuerdo al estándar H.264/A VC y, por defecto, los vectores demandados por cualquiera de los estándares anteriores. Asimismo, se propone en esta Tesis una nueva arquitectura unidimensional no agrupada de refinamiento sub-plírel Dicha arquitectura permite calcular los vectores de movimiento de acuerdo a lo establecido por los estándares H.263 y H.264/A VC refinando en cada caso, bien 5 vectores de movimiento a coordenadas de medio plírel mediante hterpolación bilineal, o bien 41 vectores de movimiento a coordenadas de cuarto de plírel mediante ecuaciones específicas de interpelación, respectivamente. Para ambas arquitecturas propuestas se obtienen mejoras significativas con respecto a trabajos predecesores recientemente publicados. 4.1 Introducción Durante los últimos años se han propuesto numerosas arquitecturas de estimación de movimiento que persiguen, como objetivo principal, calcular en tiempo real los vectores de movimiento correspondientes a una determinada secuencia de vídeo bajo los requisitos establecidos por un estándar de compresión específico. Para ello, diversos autores han propuesto el uso de arquitecturas sistólicas, tanto para la obtención de vectores de movimiento de precisión entera (precisión de píxel) como para el posterior refinamiento de éstos a coordenadas sub-píxel (precisión de medio píxel y, en menor medida, cuarto de píxel). Estas arquitecturas han sido analizadas en el capítulo 2 de esta Tesis, detallándose con especial énfasis las deficiencias encontradas en arquitecturas adaptativas y/o capaces de cumplir con los estrictos requerimientos del estándar H.264/AVC. La propuesta arquitectura1 aportada en esta Tesis realiza el proceso de estimación de movimiento según las directrices definidas por el algoritmo VBS-ACBM expuesto en el capítulo anterior. Esta arquitectura es capaz de obtener vectores de movimiento a partir de esquemas predictivos y/o mediante búsqueda exhaustiva con precisión de medio y cuarto de píxel. Asimismo, en el caso de aplicarse búsqueda exhaustiva, la arquitectura propuesta permite obtener vectores de movimiento para cualquiera de los siete modos de estimación de movimiento definidos por el estándar H.264/AVC, dentro de los cuales se encuentran los modos específicos de cualquier estándar anterior a éste, lo que convierte la arquitectura propuesta en multiestándar. Para lograr este objetivo de manera eficiente, y con el objetivo de cubrir las carencias detectadas en trabajos previos, se ha estudiado en esta Tesis un conjunto de novedosas estrategias independientes de la capacidad de adaptación ofrecida por el algoritmo VBS-ACBM. Dichas estrategias, cuya incorporación en la arquitectura propuesta en esta Tesis se describirá en detalle durante este capítulo, se detallan a continuación: 4 Arquitecturas multiestándar de estimación de movimiento adaptativa A) Mecanismos de eliminación temprana de candidatos en arquitecturas multimodo. El proceso del cálculo del SAD correspondiente a un determinado vector de movimiento puede ser detenido si el valor acumulado hasta ese momento es mayor que el SAD mínimo provisional. Los beneficios obtenidos mediante esta técnica, así como sus implicaciones arquitecturales, han sido estudiados por otros autores para arquitecturas basadas en estándares de topología fga [DY98], [SouSS], [SRSS], [LTC04], [DRS05]. En arquitecturas de estimación de movimiento de precisión entera para topología de macrobloque se obtiene una reducción media en el consumo de potencia de entre un 50% y un 65% en arquitecturas sistólicas unidimensionales [SRSS], [LTC04] y de entre un 20% y un 40% en arquitecturas sistólicas bidimensionales [DY98], [SouSS], mientras que para las arquitecturas típicas de refinamiento de medio píxel el porcentaje de reducción es de un 20% [DRS05]. Sin embargo, y a pesar de la decidida apuesta dentro de los estándares de compresión de vídeo por el uso de etapas de estimación de movimiento de topología de bloque variable, no existe ningún trabajo en la bibliografía disponible acerca del uso de los mencionados mecanismos de eliminación de candidatos en arquitecturas multimodo. En este capítulo se propone una arquitectura de estimación de movimiento con capacidad de eliminación temprana de candidatos tanto durante la estimación con precisión entera como en el posterior refinamiento a coordenadas sub-píxel, respetando los requisitos establecidos por los estándares H.263 y H.264/AVC en cuanto al uso de bloques de tamaño variable y precisión de los vectores. Asimismo, se investiga por primera vez si las técnicas de eliminación temprana de candidatos son igualmente efectivas, en términos de ciclos inactivos y coste hardware asociado, para arquitecturas de estimación de movimiento con topología variable. 8) Elección flexible del número de modos y precisión de los vectores de movimiento por macrobloque. de estimaciói 1261 Los estándares de compresión de vídeo definen un número máximo de modos I de movimiento, así como una precisión máxima para los vectores de movimiento de cada macrobloque. Mediante el estudio de las características de la secuencia de vídeo a codificar puede reducirse en el codificador el número de modos a evaluar, así como la precisión de los vectores de movimiento, sin pérdidas apreciables en los niveles de compresión, tal y como demuestran los trabajos referenciados en la parte final del apartado 2.3.2.2 de esta Tesis. Este hecho no es considerado por las arquitecturas de estimación de movimiento publicadas hasta la fecha, en las cuales siempre se realiza la estimación de movimiento para un número de modos y una precisión en los vectores de movimiento constantes En este capítulo se investiga, sobre la base de la arquitectura propuesta, los beneficios arquitecturales derivados de considerar una total flexibilidad en el número de modos de estimación de movimiento y en la precisión de los vectores de movimiento por macrobloque. C) Agrupación de elementos de proceso. En los trabajos previos a esta Tesis no se han estudiado las implicaciones que resultan de la manera en que se agrupan los elementos de proceso en una arquitectura de estimación de movimiento. En este capítulo se estudian dichos efectos en términos arquitecturales que, como consecuencia de lo establecido en los dos puntos anteriores, resultan ser totalmente novedosos en el ámbito de las arquitecturas de estimación de movimiento multimodo. A lo largo del presente capítulo se detallan los estudios realizados en relación con estos aspectos, tanto en el proceso de estimación de movimiento con precisión entera como en el de refinamiento de vectores de movimiento a coordenadas sub-píxel, mostrándose las contribuciones propias de esta Tesis dentro de ambos ámbitos. 4 Arquitecturas multiestándar de estimación de movimiento adaptativa 4.2 Características generales de la arquitectura propuesta La estructura a nivel de módulos funcionales de la arquitectura propuesta en esta Tesis Doctoral para la estimación de movimiento según el algoritmo VBS-ACBM se muestra de forma esquemática en la Figura 4.1 Memona de 1uminancia del fotograma actual Memoria de 1uminancia del foiograma recuperado Figura 4.1 : Esquema general de la arquitectura propuesta para la estimación de movimiento según el algoritmo VBS-ACBM. Tal y como puede deducirse a partir de la Figura 4.1, la arquitectura propuesta consta de dos módulos arquitecturales claramente diferenciados: 1. Mddulo de estimación de movimiento con precisión entera. El módulo de estimación de movimiento con precisión entera propuesto en esta Tesis calcula los vectores de movimiento con precisión entera mediante búsqueda predictiva o exhaustiva. El tipo de búsqueda dependerá de si la estimación se está realizando por primera vez para un nuevo macrobloque o, si por el contrario, ya se ha realizado una primera estimación predictiva pero el vector obtenido no es satisfactorio en los términos establecidos por 4.2 Característcas generales de a arqutectura propuesta 4 el algoritmo VBS-ACBM propuesto. En el caso de realizarse la búsqueda exhaustiva, este proceso se realizará sólo para aquellos modos que sea necesario y que en el contexto de esta Tesis se denominan modos activos Esta condición, tal y como se indicó anteriormente, representa una novedad con respecto a las arquitecturas de búsqueda exhaustiva precedentes y ha sido introducida con el objetivo de estudiar los posibles beneficios arquitecturales asociados a ella, así como proporcionar una adaptación total de la arquitectura al estándar en uso. En cualquier caso, este módulo es capaz de obtener los vectores de movimiento para los siete modos definidos por el estándar H.264/AVC y por lo tanto, para cualquiera de sus estándares predecesores. 2. Módulo de refinamiento sub-plxel. A partir de las coordenadas de los vectores de movimiento con precisión de píxel calculados por el módulo de estimación de movimiento con precisión entera, el módulo de refinamiento sub-píxel se encarga de refinar dichos vectores, obteniendo el mismo número de vectores en coordenadas de cuarto de píxel. Es importante destacar que, tomando como referencia el estándar H.264/AVC, el refinamiento de vectores de movimiento a coordenadas de cuarto de píxel supone un 45% del esfuerzo computacional medio del proceso de estimación de movimiento, proporcionando una mejora en la calidad de la secuencia de 4 dBs de media para una misma tasa de transmisión [CHC04b]. Sin embargo, y a pesar de estos relevantes números, las aportaciones algorítmicas y arquitecturales realizadas en el marco del refinamiento de vectores de movimiento en la bibliografía reciente son prácticamente inexistentes cuando se comparan con los trabajos relacionados con la estimación de movimiento con precisión entera. Para realizar este proceso de manera eficiente, el módulo de refinamiento propuesto en esta Tesis está compuesto por dos sub-módulos: 4 Arquitecturas multiestándar de estimación de movimiento adaptativa Sub-modulo de refinamiento de medio plxel. A partir de las posiciones apuntadas por los vectores de movimiento proporcionados por el módulo de estimación de movimiento con precisión entera, este sub-módulo realiza el refinamiento de los vectores recibidos a coordenadas de medio píxel. Para ello, después de completar una primera etapa en la que se calculan los valores de las posiciones de medio píxel necesarias, se realiza el refinamiento propiamente dicho mediante la inspección de ocho posiciones de medio píxel situadas alrededor de la posición con precisión entera apuntada. De nuevo, este proceso sólo se realizará para aquellos modos que hayan sido activados, de acuerdo a los vectores calculados por el módulo de estimación de movimiento con precisión entera. Asimismo, este proceso sólo se realizará si el estándar lo requiere, o lo que es lo mismo, si permite realizar la compensación de movimiento en coordenadas de medio píxel. Sub-mbdulo de refinamiento de cuarto plxel. Este sub-módulo es análogo al de refinamiento de medio píxel, con la salvedad de que el refinamiento se produce mediante la inspección de ocho posiciones de cuarto de píxel alrededor del conjunto de vectores de medio píxel. Tal y como se puede deducir a partir de las características descritas, de las tres grandes novedades introducidas por el estándar H.264/AVC en cuanto al proceso de estimación de movimiento se refiere [WSB+03], la arquitectura propuesta en esta Tesis aborda de manera implícita dos de ellas - estimación de movimiento para bloques de topología variable y precisión de hasta cuarto de píxel -, no abordando la estimación de movimiento multifotograma. Este hecho se debe fundamentalmente a las razones siguientes: En primer lugar, la arquitectura propuesta es absolutamente transparentecon respecto a los fotogramas utilizados para la estimación de movimiento. Tal y como se detallará posteriormente, la arquitectura completa el proceso de estimación de movimiento a partir de Bibliografía [ESBOO] [FLM +95] [FLM +98] M.A. ELGAMEL, A.M. SHAMS Y M.A. BAYOUMI, "A comparative analysis for (~2.~53) low power motion estimation VLSl architectures", Proceed~ngs IEEE (c2,p56) Workshop on S~gnal Process~ng Systems (SIPS), pp. 149-1 58, octubre 2000. M.A. ELGAMEL, A.M. SHAMS, X. XUELING Y M.A. BAYOUMI, "Enhanced low (~2.~53) power motion estimation VLSl architectures for video compression", (c2,p56) Proceed~ngs IEEE lnternat~onal Sympos~um on C/rcu/ts and Systems (~4.~150) (ISCAS), vol. 4, pp. 474-477, mayo 2001 H. EVERETT III, "Generalized lagrange multiplier method for solving (~2.~40) problems of optimum allocation of resources", Operat~ons Research, vol. 11, num. 3, pp. 399-41 7, mayo Junio 1963. B. FURHT, J. GREENBERG Y R. WESTWATER, Motion estimation algorithms (~2.~46) for video compression. The lnternat~onal Serles /n Eng/neer/ng and ComputerSc/ence, Springer, 1996. J. FENG, K.T. LO, H. MEHRPOUR Y A.E. KARBOWIAK, "Adaptive block (~2.~50) matching motion estimation algorithm for video coding", IEE Electron~cs (c2,p51) Letters, vol. 31, num. 18, pp. 1542-1543. agosto 1995. J. FENG, K.T. LO, H. MEHRPOUR Y A.E. KARBOWIAK, "Adaptive block (~2.~49) matching algorithm for video compression". IEE Proceed~ngs Ihsion, lmage (c2,p51) andS~gnalProcess/ng vol. 145, num. 3, pp. 173-178,junio 1998. V. FOTOPOULOS Y A.N. SKODRAS, "sMAE: an improved block matching (~2.~24) criterion", Proceed~ngs lnternat~onal Conference on Electron~cs, C/rcu/ts andSystems, vol. 3, pp. 519-522, septiembre 1998. MAT~AS JAVIER GARRIDO GONZALEZ, "Arquitectura versátil para la (~1.~6) codificación de vídeo multi-estándar: aportaciones metodológicas para el (c4,p168) diseno de sistemas reutilizables y sistemas en un chip", Tes/s Doctoral. 2004. M.J. GARRIDO, C. SANZ, M. JIMENEZ Y J.M. MENESES, "An FPGA (~2.~58) implementation of a flexible architecture for H.263 video coding", IEEE Transact~ons on Consumer Electron/cs. vol. 48, num. 4, pp. 1056-1 066, noviembre 2002. ITU-T Recommendation H.261, "Video codec for Audiovisual Services at (~1.~9) px64 kbit/sr', 1993. (~2.~27) Bibliografía ITU-T Recommendation H.263, "Video coding for low bit rate (~1.~6) communication", version 1, 1995. (~2.~28) (~2.~44) (c4.p 168) ITU-T Recommendation H.263, "Video coding for low bit rate (~2.~29) communication", version 2, 1998. [H263+ +] ITU-T Recommendation H.263, "Video coding for low bit rate (~2.~29) communication" version 3, 2000. [H263code] Disponible en: ftp:// bonde.nta.no/pub/tmn [Online] Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG Draft ITU-T (~1.~6) Recommendation and Final Draft lnternational Standard of Joint Video (c2,p29) Specification (ITU-T Rec. H.264/ISO/IEC 14496-10 AVC), 2003. (~2.~44) (c4.p 168) [H264code] Disponible en: http://iphome.hhi.de/suehring/tml/index.htm [Online]. (c4.p 198) A. HABIBI, "Hybrid coding of pictorial data", IEEE TransactIons on (~1.~4) CommunIcatIons, vol. COM-22, num. 5, pp. 614-615, mayo 1974. G. DE HAAN Y P.W.A.C. BIEZEN, "An efficient true-motion estimator using (~3.~81) candidate vectors from a parametric motion model", IEEE TransactIons on CIrcuIts and Systems for Hdeo Technology. vol. 8, num. 1, pp. 85-91. febrero 1998. [HBH+931 G. DE HAAN, P.W.A.C. BIEZEN, H. HUIJGEN Y O.A. OJO, "True-motion (~2.~47) estimation with 3-D recursive search block matching", IEEE TransactIons (c3,p81) on CIrcuIts and Systems for Hdeo Technology. vol. 3, num. 5, pp. 368 - 379, octubre 1993. [HCH+041 Y.W. HUANG, S.Y. CHIEN, B.Y. HSIEH Y L.G. CHEN, "Global elimination (~2.~56) algorithm and architecture design for fast block matching motion (",p150) estimation", IEEE TransactIons on CIrcuIts and Systems for Hdeo Technology. vol. 14, num. 6, pp. 898-907,junio 2004. [HCT+O51 Y.W. HUANG, T.C. CHEN, C.H. TSAI, C.Y. CHEN, T.W. CHEN, C.S. CHEN, (~4.~203) C.F. SHEN. S.Y. MA, T.C. WANG, B.Y. HSIEH, H.C. FANG Y L.G. CHEN, "A 1.3 TOPS H.2641AVC single-chip encoder for HDTV applications", D~gest of TechnIcal Papers, IEEE InternatIonal Solid-State CIrcuIts Conference flSSCC), vol. 1, pp. 128-1 29, febrero 2005. Bibliografía [HCT+O61 Y.W. HUANG, C.Y. CHEN, C.H. TSAI, C.F. SHEN Y L.G. CHEN, "Survey on (~1.~7) block matching motion estimation algorithms and architectures with new (c2,@7) (~2.~53) results", Journal of VLSI S~gnal Process~ng, vol. 42, num. 3, pp. 297-320, (c3,p88) marzo 2006. S.Y. HUANG, C.Y. CHO Y J.S. WANG, "Adaptive fast block-matching (~2.~50) algorithm by switching search patterns for sequences with wide-range (c2,p51) motion content", IEEE Transact~ons on C/rcu/ts and Systems for Hdeo Technology. vol. 15, num. 11, pp. 1373-1 384, noviembre 2005. Y.W. HUANG, B.Y. HSIEH, S.Y. CHIEN, S.Y. MAY L.G. CHEN, "Analysis and (~1.~7) complexity reduction of multiple reference frames motion estimation in (c2,p35) H .264/AVCr', IEEE Transact~ons on C/rcu/ts and Systems for Hdeo (~4.~131) Technology. vol. 16, num. 4, pp. 507-522, abril 2006. H. HERNANDEZ, A. KANSTEIN, S. LOPEZ, J.F. LOPEZ Y M. BEREKOVIC, (~2.~58) "Mapping of the H.264/AVC motion compensation algorithm onto coarse (c5,p225) grain reconfigurable array", Proceed~ngs XXI Des~gn of lntegrated C/rcu/ts and Systems (DCIS) Conference, aceptado para supubl/cac/ón, 2006. T. HA, S. LEE Y J. KIM, "Motion compensated frame interpolation by new (~3.~67) block-based motion estimation algorithm", IEEE Transact~ons on ConsumerElectron/cs, vol. 50, num. 2, pp. 752-759, mayo 2004. P.I. HOSUR, "Motion adaptive search for fast motion estimation". IEEE (~2.~49) Transact~ons on Consumer Electron/cs. vol. 49, num. 4, pp. 1 330-1 340. (c2,p51) noviembre 2003. K.C. HUI, W.C. Slu Y Y.L. CHAN, "New adaptive partial distortion search (~2.~56) using clustered pixel matching error characteristic", IEEE Transact~ons on lmage Process~ng, vol. 14, num. 5, pp. 597-607, mayo 2005. Y. Hu, A. SIMPSON, K. MCADOO Y J. CUSH, "A high definition H.264/AVC (~1.~7) hardware video decoder core for multimedia SoC's", Proceed~ngs IEEE lnternat~onal Sympos~um on Consumer Electron/cs. p p p. 38 5389, septiembre 2004. C. HUI, Analysis and motion estimation strategies for frame and video (~2.~46) object coding, ProQuest/UML 2006. Y.W. HUANG, T.C. WANG, B.Y. HSIEHY L.G. CHEN, "Hardware architecture (~2.~55) design for variable block size motion estimation in MPEG-4 (c2,p57) (~4.~202) AVC/JVT/ITU-T H. 264". Proceed~ngs lnternat~onal Sympos~um on (c4,p203) C/rcu/tsandSystems (ISCAS), vol. 2, pp. 796-799, mayo 2003. (~4.~209) Bibliografía [JPEG] X. JING Y L.P. CHAU, "Fast approach for H.264 inter mode decision", IEE (~2.~60) ElectronIcsLetters, vol. 40, num. 17, pp. 1050-1052, agosto 2004. J.C.H. Ju, Y.K. CHEN Y S.Y. KUNG, "A fast rate-optimized motion (~3.~68) estimation algorithm for low-bit-rate video coding". IEEE TransactIons on CIrcuIts and Systems for Hdeo Technology. vol. 9, num. 7, pp. 994-1 002, octubre 1999. J.R. JAIN Y A.K. JAIN, "Displacement measurement and its application in (~1.~6) interframe image coding". IEEE TransactIons on CommunIcatIons, vol COM-29, num. 12, pp. 1799-1808. diciembre 1981 P. JAIN, A. LAFFELY, W. BURLESON, R. TESSIER Y D. GOECKEL, (~2.~50) "Dynamically parameterized algorithms and architectures to exploit signal variations", Journal of VLSI S~gnal ProcessIng, vol. 36, num.1, pp. 27-40, noviembre 2004. ISO/IEC JTCI 10918-1, ITU-T Recommendation 7.81, "lnformation (~2.~26) Technology - Digital compression and coding of continuous-tone still images: requirements and guidelines", 1994. ISO/IEC JTCI/SC29/WGl, "lnformation technology - JPEG 2000 image (~2.~26) coding system: Core coding system", marzo 2000. X. JING, C. ZHU Y L.P. CHAU, "Smooth constrained block matching criterion (~3.~66) for motion estimation", ProceedIngs IEEE InternatIonal Conference on AcoustIcs, Speech and S~gnal ProcessIng (ICASSP), vol. 3, pp. 661 664. abril 2003. N. KAMACI Y Y. ALTUNBASAK, "Performance comparison of the emerging (~2.~29) H.264 video coding standard with the existing standards", ProceedIngs InternatIonal Conference on MuItImedIa and Expo (ICME), vol. 1, pp. 345348,julio 2003. M. KIM, l. HWANG Y S.I. CHAE, "A fast VLSI architecture for full-search (~2.~55) variable block size motion estimation in MPEG-4 AVC/H.264", (c2,p57) (~4.~202) ProceedIngs AsIa and South PacIfic Des~gn AutomatIon Conference (ASP- (c4,p203) DAC), vol. 1, pp. 631634. enero 2005. (~4.~209) H.Y. KANG, K.A. JEONG, J.Y. BAE, Y.S. LEE Y S.H. LEE, "MPEG4 (~1.~7) AVWH.264 decoder with scalable bus architecture and dual memory controller", ProceedIngs InternatIonal SymposIum on CIrcuIts and Systems (ISCAS), vol. 2, pp. 145-1 48, mayo 2004. Bibliografía H. KIM, N. KAMACI Y Y. ALTUNBASAK, "Low-complexity rate-distortion (~2.~42) optimal macroblock mode selection and motion estimation for MPEG-like video coders", IEEE Transact~ons on C/rcu/ts and Systems for Hdeo Technology. vol. 15, num. 7, pp. 823-834,julio 2005. HELGA KOLB, "HOW the Retina Works," Amer/canSc/ent/st, vol. 91, num.1, (~2.~19) pp. 28-35, enero 2003. ARTHUR KORN, "La télégraphie des images", Je sa/s tout. num. 27, abril (~1.~3) 1907. PETER KUHN, Algorithms, complexity, analysis and VLSl architectures for (~1.~7) MPEG-4 motion estimation, KluwerAcadem/c Publ~shers, 1999. (~2.~45) (~2.~53) Y. LIANG, l. AHMAD, J. LUO, Y. SUN Y V. SWAMINATHAN, "A fast adaptive (~2.~51) motion estimation using hierarchical history of motion intensity in H .264/AVCr', IEEE Transact~ons on C/rcu/ts and Systems for Hdeo Technology. aceptado para puMcac/ón, 200 6 J.H. LIM Y H.W. CHOI, "Adaptive motion estimation algorithm using spatial (~2.~49) and temporal correlation", Proceed~ngs IEEE Pac~fic R/m Conference on Commun/cat/ons, Computers and S~gnal Process~ng, pp. 47 3-47 6, agosto 2001 J.F. LOPEZ, P. CORTES, S. LOPEZ Y R. SARMIENTO, "Gallium Arsenide (~4.~132) Processing Elements for Motion Estimation Full Search Algorithm", SPIE Proceed~ngs Electron~cs and Structures for MEMS vol. 4591 , pp. 1 01 1 1 2, noviembre 2001 J.F. LOPEZ, P. CORTES, S. LOPEZ Y R. SARMIENTO, "Design of a 270 (~2.~46) MHz/340 mW processing element for high performance motion estimation (c4,p132) systems application", M/croelectron/csJourna/. vol. 33, num. 12, pp. 112311 34, diciembre 2002. S. LOPEZ, G.M. CALLICO, J.F. LOPEZ Y R. SARMIENTO, "High confident (~3.~69) characterization for block-matching true motion vectors", Proceed~ngs of the Work ln Progress Sess~on of the 29th Eurom/cro Conference, pp. 79-80, septiembre 2003. S. LOPEZ, G.M. CALLICO, J.F. LOPEZ Y R. SARMIENTO, "Adaptive motion (~3.~82) vector post-processing for low cost rate-distortion optimisation", IEE Electron~cs Letters, vol. 39, num. 24, pp. 1720-1721, diciembre 2003. Bibliografía [LCL+O5al S. LOPEZ, G.M. CALLICO, J.F. LOPEZ Y R. SARMIENTO, "Compresión de (~3.~82) vídeo mediante técnicas de post-procesamiento", Rev~sta Vector PLUS. Fundación Universitaria de Las Palmas, num. 25, pp. 27-36, enero 2005. [LCLtOSb] S. LOPEZ, G.M. CALLICO, J.F. LOPEZ Y R. SARMIENTO, "A high quality/low (~3.~87) computational cost technique for block matching motion estimation", Proceed~ngs Des~gn, Automat~on and Test /n Europe Conference and Exh/b/ton (DATE), vol. 3, pp. 2-7, marzo 2005. [LCL+O5c] S. LOPEZ, G.M. CALLICO, J.F. LOPEZ Y R. SARMIENTO, "A low-cost (~2.~27) bidimensional smart pixel network for video coding operations", Proceed~ngs SPIE VLSI C/rcu/ts and Systems, lnternat~onal Sympos~um on M/crotechnolog/es for the New M/llenn/um, vol. 5837, pp. 638-649, mayo 2005. S. LOPEZ, R. CALZADA, A. TEJER¿, J.F. LOPEZ Y R. SARMIENTO, "Real time (~2.~27) smart pixels processing array for mobile multimedia applications", Proceed~ngs XIX lntegrated C/rcu/ts and Systems Conference (DCIS), pp. 386-391, noviembre 2004. S. Ll, Y. JIANG, T. IKENAGA Y S. GOTO, "Content-based motion estimation (~2.~50) with extended temporal-spatial analysis", IEICE Transact~ons on (c2,p51) lnformat/onandSystems, vol. E88-D. num. 7, pp. 15611 567,julio 2005. S.H. LEE, O. KWON Y R.H. PARK, "Weighted-adaptive motion-compensated (~3.~67) frame rate up-conversion ", IEEE Transact~ons on Consumer Electron/cs. vol. 49, num. 3, pp. 485-492, agosto 2003. J.H. LEE Y N.S. LEE, "Variable block size motion estimation algorithm and (~2.~47) its hardware architecture for H.264/AVCr', Proceed~ngs lnternat~onal Sympos~um on C/rcu/ts and Systems (ISCAS), vol. 3, pp. 741 -744, mayo 2004. J.H. LEE, K.W. LIM, B.C. SONG Y J.B. RA, "A fast multi-resolution block (~2.~47) matching algorithm and its LSI architecture for low bit-rate video coding", IEEE Transact~ons on C/rcu/ts and Systems for Hdeo Technology. vol. 1 1, num. 12, pp. 1289-1 301, diciembre 2001 S. LOPEZ, J.F. LOPEZ Y R. SARMIENTO, "Cost-adaptive motion estimation (~3.~87) strategy for high-performance video encoders", IEEElectron/cs Letters, vol. 41, num. 4, pp. 182-183. febrero 2005. Bibliografía [LTC +O61 J.F. LOPEZ, S. LALCHAND, F. TOBAJAS, S. LOPEZ, A. NÚNEZ Y R. (~2.~27) SARMIENTO, "Gallium Arsenide multiplierless filter bank for two dimensional discrete wavelet transform (2D-DWT) computation", Proceed~ngs SPIE lnternat~onal Symposhm on Smart Electron~cs and MEMs, vol. 4951, pp. 273-280, noviembre 2001 Y. LIU Y S. ORAINTARA, "Complexity comparison of fast block-matching (~1.~7) motion estimation algorithms", Proceed~ngs IEEE lnternat~onal Acoust~cs, (c2~p46) SpeechandS~gnal Process~ng (ICASSP), vol. 3, pp. 341344. mayo 2004. S.H. LEE, J.H. PARK, S.W. KIM, S.J. KO Y S. KIM, "lmplementation of (~1.~7) H.264/AVC decoder for mobile video applications", Proceed~ngs As/a and South Pac~fic Conference Des~gn Automat~on, pp. 1 20-1 21, enero 2006. S. LOPEZ, F. TOBAIAS, G.M. CALLICO, P.PEREz Y R. SARMIENTO, "A novel (~2.~39) high performance architecture for H.264/AVC deblocking filtering", IEE Electron~cs L etters, en v/ado para su puMcac/ón, 200 6. S.S. LIN, P.C. TSENG Y L.G. CHEN, "LOW power parallel tree architecture for (~4.~126) full search block-matching motion estimation". Proceed~ngs lnternat~onal (c4,p143) Sympos~um on C/rcu/ts and Systems (ISCAS), vol. 2, pp. 31 3-31 6, mayo (c4.p 150) 2004. J.F. LOPEZ, F. TOBAJAS, S. LOPEZ, P. CORTES, S. LALCHAND Y R. (~4.~132) SARMIENTO, "VLSI video processing elements for real time applications", Proceed~ngs 28th Annual Conference of the IEEE lndustr~al Electron~cs Soc/ety(IECON2OO2), noviembre 2002. S. LOPEZ, F. TOBAJAS, A. VILLAR, V. DE ARMAS, J.F. LOPEZ Y R. (~2.~50) SARMIENTO, "LOW cost efficient architecture for H.264 motion estimation". (c4,p136) Proceed~ngs IEEE lnternat~onal Symposhm on C/rcu/ts and Systems (ISCAS), vol. 1, pp. 41 2-41 5, mayo 2005. S. LOPEZ, F. TOBAJAS, A. VILLAR, J. BIENES, V. DE ARMAS, G.M. CALLICO, (~4.~170) J.F. LOPEZ Y R. SARMIENTO, "A quarter pixel precision motion estimation architecture for H.264/AVC video coding", SPIE Proceed~ngs of VLSI C/rcu/ts and Systems, lnternat~onal Symposhm on M~crotechnolog/es for the NewMlllenn~um, vol. 5837, pp. 174-184. mayo 2005. V. LIGUORI Y K. WONG, "Designing a real-time HDTV 1080p baseline (~1.~7) H.264/AVC encoder core", Des~gnCon 2006: 2006. Bibliografía M. LI, R. WANG Y W. WU, "The high throughput and low memory access (~2.~58) design of sub-pixel interpolation for H.264/AVC HDTV decoder", ProceedIngs IEEE Workshop on S~gnal ProcessIng Systems Des~gn and lmplernentat~on, pp. 296-301, noviembre 2005. W.N. LIE, H.C. YEH, T.C.I. LIN Y C.F. CHEN, "Hardware-efficient computing (~4.~173) architecture for motion compensation interpolation in H.264 video coding", ProceedIngs IEEE lnternat~onal SymposIum on CIrcuIts and Systems (ISCAS), vol. 3, pp. 21 36-21 39, mayo 2005. B. Llu Y A. ZACCARIN, "New fast algorithms for the estimation of block (~2.~46) motion vectors", IEEE TransactIons on CIrcuIts and Systems for Hdeo Technology. vol. 3, num. 2, pp. 148-157. abril 1993. GUSTAVO MARRERO CALLICO, "Real-time and low-cost super-resolution (~3.~67) algorithms onto hybrid video encoders", TesIs Doctoral. Universidad de Las Palmas de Gran Canaria, julio 2003. S. MA, W. GAO Y Y. Lu, "Rate-distortion analysis for H.264/AVC video (~2.~40) coding and its application to rate control", IEEE TransactIons on CIrcuIts and Systems for Hdm Technology. vol. 15, num. 12, pp. 1533-1 544, diciembre 2005. [MGS+021 H. MAHMOUD, S. GOEL, M. SHAABAN, T. DARWISH Y M. BAYOUMI, "A low CALV PISO) power VLSl architecture for multi-stage interval-based motion estimation (MI M E) algorithm", ProceedIngs lnternat~onal Workshop on D~gItal and ComputatIonal Hdeo, pp. 159-1 66, noviembre 2002. [MKCOO] F. MOSCHETTI, M. KUNT Y F. CALVANO, "A nested-multilevel redundancy (~2.~49) exploitation for fast block matching", ProceedIngs lnternat~onal Conference (c2,p51) on lmage ProceesIng flClP), vol. 1, pp. 856-859, septiembre 2000. F. MOSCHETTI, M. KUNT Y E. DEBES, "A statistical adaptive block- (~2.~50) matching motion estimation", IEEE TransactIons on CIrcuIts and Systems for Hdeo Technology. vol. 13, num. 4, pp. 417-431, abril 2003. V.G. MOSHNYAGA Y K. MASUNAGA, "Reducing computational complexity of (~2.~49) adaptive motion estimation through binary comparison", ProceedIngs lnternat~onal SymposIum on CIrcuIts andsystems (ISCAS), vol. 2, pp. 484487, mayo 2002. ISO/IEC 11172: "lnformation technology-coding of moving pictures and (~2.~27) associated audio for digital storage media at up to about 1.5 Mbit/sr', 1993. Bibliografía ISO/IEC 13818-2: "Generic coding of moving pictures and associated audio (~2.~27) information-Part 2: Video", (también /TU-T RecommendatIon H.262). 1994. ISO/IEC JTCI/SC29/WG11 N5525, "MPEG-21, Overview v.9". 2003. ISO/IEC 14496-2: "lnformation technology-coding of audiovisual (~1.~6) objects-part 2: visual", 2000. (~2.~28) (c4.p 169) ISO/IEC 15938-3: "Multimedia Content Description Interfaces. Part 3: (~2.~30) Visual", 2002. B. MONTRUCCHIO Y D. QUAGLIA, "New sorting-based lossless motion (~2.~56) estimation algorithms and a partial distortion elimination performance analysis", IEEE TransactIons on CIrcuIts and Systems for Hdeo Technology. vol. 15, num. 2, pp. 210-220, febrero 2005. J. MINOCHA Y N.R. SHANBHAG, "A low power data-adaptive motion (~2.~50) esti mat ion algori t hm ", ProceedIngs IEEE Workshop on MuItImedIa S~gnal ProcessIng, pp. 685-690, septiembre 1999. K.M. NAM, J.S. KIM, R.H. PARK Y Y.S. SHIM, "A fast hierarchical motion (~2.~47) vector estimation algorithm using mean pyramid", IEEE TransactIons on CIrcuIts and Systems for Hdeo Technology. vol. 5, num. 4, pp. 344-351, agosto 1995. Y. NIE Y K.K. MA, "Adaptive irregular pattern search with matching (~2.~50) prejudgment for fast block-matching motion estimation", IEEE (c2,p51) TransactIons on CIrcuIts and Systems for Hdeo Technology. vol. 1 5, n u m 6, pp. 789-794, junio 2005. "Nomadik - open multimedia platform for next generation mobile devices", (~1.~4) STMicroelectronics, TA305 Technical article, 2004. "Nomadik mobile multimedia application processor", STMicroelectronics, (~1.~7) STn8815 Data Brief. 2006. J. OSTERMANN, J. BORMANS, P. LIST, D. MARPE, M. NARROSCHKE, F. (~1.~6) PEREIRA, T. STOCKHAMMER Y T. WEDI, "Video coding with H.264/AVC: (c2,p29) (~2.~35) tools. aerformance and comalexitv". IEEE CIrcuIts and Svstems MaaazIne, < vol. 4, num. 1, pp. 7-28, enero 2004. Bibliografía [PKJ +O61 H.S. OH Y H.K. LEE, "Block-matching algorithm based on an adaptive (~2.~50) reduction of the search area for motion estimation". Real-77me ImagIng (c2,p51) Journal. vol.6, num.5, pp. 407-414, octubre 2000. H.S. OH Y H.K. LEE, "Adaptive adjustment of the search window for block- (~2.~50) matching algorithm with variable block size", IEEE TransactIons on (c2,p51) ConsumerElectronIcs, vol. 44, num. 3, pp. 659-666, agosto 1998. C.M. Ou, C.F. LE Y W.J. HWANG, "An efficient VLSl architecture for H.264 (~2.~55) variable block size motion estimation". IEEE TransactIons on Consumer (",p205) ElectronIcs, vol. 51, num. 4, pp. 1291 -1299, noviembre 2005. (~4.~206) (~4.~209) E. ONG, H. WANG Y P. XUE, "Video coding based on true motion (~3.~68) estimation". ProceedIngs IEEE InternatIonal Conference on AcoustIcs, Speech ands~gnal ProcessIng (ICASSP), pp. 409-41 2, abril 2003. S.R. PARK Y W. BURLESON, "Reconfiguration for power saving in real-time (~2.~51) motion estimation". ProceedIngs IEEE InternatIonal Conference on AcoustIc, Speech and S~gnal ProcessIng (ICASSP), vol. 5, pp. 3037-3040, mayo 1998. S. PARK, H. CHO, H. JUNG Y D. LEE, "An implemented of H.264 video (~1.~7) decoder using hardware and software", ProceedIngs IEEE Custom IntegratedCIrcuIts Conference, pp. 271275. septiembre 2005. S.H. PARK, H.K. KIM, J.W. JUNG Y S.J. Ko, "Efficient SVC encoding (~2.~32) scheme for the video transmission over various networks", ProceedIngs InternatIonal Conference on Consumer ElectronIcs (ICCE), p p. 487 - 488, enero 2006. W.B. PENNEBAKERY J.L. MITCHELL, JPEG still data compression standard, (~2.~26) SprInger. 1 992 R. PESET-LLOPIS, R. SETHURAMAN, C. ALBA-PINTO, H. PETERS, S. MAUL Y (~1.~6) M. OOSTERHUIS, "A low-cost and low-power multi-standard video encoder", ProceedIngs IEEE/ACM/lFlP InternatIonal Conference on Hardware/Software Codes~gn and Systems SynthesIs, pp. 97-1 02, octubre 2003 C.A. RAHMAN Y W. BADAWY, "A quarter pel full search block motion (~2.~59) estimation architecture for H .264/AVCr', ProceedIngs IEEE InternatIonal Conference on MuItImedIa and Expo (ICME), pp. 41 4-41 7, julio 2005. l. RICHARDSON, Video codec design: developing image and video (~2.~17) compression systems, John WIley & Sons, 2002. Secuencias de vídeo utilizadas En este anexo se resumen las principales caracterljticas espaciales y temporales de las secuencias de vídeo utikadas en esta Tesis Doctoral. A Secuencias de vídeo utilizadas A.1 Características de las secuencias de vídeo utilizadas En esta Tesis se han utilizado numerosas secuencias de vídeo en formato QClF (Quarter Common Intermediate Format, 176x144 píxeles) para evaluar las prestaciones de los algoritmos y arquitecturas propuestas. A lo largo de la Tesis, se muestran alternativamente resultados obtenidos con las secuencias cuyas características se resumen en la Tabla A.1 TABLE (300 fotogramas) DEADLINE 1375 fotogramas) FOREMAN (400 fotogramas) Miss AMERICA (1 50 fotogramas) PAMPHLET (300 fotogramas) SUZlE (40 fotogramas) COASTGUARD (100 fotogramas) Gran cantidad de movimiento en objetos de diferentes tamaños Existencia de cambios de contexto y diferentes enfoques (zoom) No existe movimiento de cámara Secuencia con gran cantidad de texturas heterogéneas Poco movimiento limitado al objeto central de la secuencia No existen cambios ni en el contexto ni en el enfoque No existe movimiento de cámara Secuencia con gran cantidad de texturas heterogéneas Gran cantidad de movimiento, con muy diferentes sentidos y velocidades Existencia de cambios de contexto sin diferentes enfoques Existe movimiento de cámara Secuencia con gran cantidad de texturas homogéneas Poco movimiento limitado al objeto central de la secuencia No existen cambios ni en el contexto ni en el enfoque No existe movimiento de cámara Secuencia con mezcla de texturas homogéneas y heterogéneas Gran cantidad de movimiento, con muy diferentes sentidos y velocidades Existencia de cambios de contexto sin diferentes enfoques No existe movimiento de cámara Secuencia con mezcla de texturas homogéneas y heterogéneas Gran cantidad de movimiento, con muy diferentes sentidos y velocidades No existen cambios ni en el contexto ni en el enfoque No existe movimiento de cámara Secuencia con gran cantidad de texturas homogéneas Poca cantidad de movimiento, exclusivamente en sentido horizontal No existen cambios ni en el contexto ni en el enfoque Existe movimiento de cámara Tabla A. I : Características espaciales y temporales de las secuencias de vídeo utilizadas. A Secuencias de video utilizadas