Sistema-de-codificacion-y-transmision-de-video-sobre-redes-TCPIP-basado-en-la-transformada-polinomial

Vista previa del material en texto

UNIVERSIDAD NACIONAL AUTÓNOMA 
 DE MÉXICO 
 
 
FACULTAD DE INGENIERÍA 
 
 
 
 
 
 
 
SISTEMA DE CODIFICACIÓN Y TRANSMISIÓN 
DE VIDEO SOBRE REDES TCP/IP BASADO EN 
LA TRANSFORMADA POLINOMINAL 
 
 
 
T E S I S 
 
 
QUE PARA OBTENER EL TÍTULO DE: 
INGENIERO EN COMPUTACIÓN 
 
 
P R E S E N T A : 
MIGUEL ANDRÉS TRONCOSO MUÑOZ 
 
 
 
DIRECTOR DE TESIS: 
DR. BORIS ESCALANTE RAMÍREZ 
 
 
 
 MÉXICO, D.F. OCTUBRE 2005 
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
 
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
 
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
 
 
 
 iii
Agradecimientos 
 
 
 
A mis padres, Jesús Antonio y Flor María, por su amor, cariño y apoyo incondicional sin el cual no 
hubiese sido posible llegar hasta aquí. Este logro es también de ustedes. 
 
 
A mi hermano Alejandro por el cariño y respeto que nos hemos tenido siempre. Se que pronto lograrás 
también tus objetivos. 
 
 
A la memoria de mi hermana Marian. Tu recuerdo es un aliento que siento todos los días. Gracias por 
tu ejemplo de lucha y perseverancia. Nunca te olvidaré. 
 
 
A mi mujer, Maricruz, por todo tu amor y apoyo para alcanzar este objetivo. Gracias por todo este 
tiempo. 
 
 
A mi hijo, Carlos Andrés, por ser una motivación muy importante en mi vida. Esto es por ti. 
 
 
A todos mis compañeros y amigos. En especial a Juan Antonio con quien he compartido más de siete 
años de amistad. Sigue luchando por cumplir con este mismo objetivo. 
 
 
A la Universidad Nacional Autónoma de México, por ser la institución pública en busca de la 
excelencia que me permitió culminar con esta etapa de mi vida profesional. En particular a la Facultad 
de Ingeniería que cubrió ampliamente mis expectativas educativas y siempre me proporcionó las 
herramientas necesarias para mi desarrollo académico. 
 
 
Al Programa de Alto Rendimiento Académico de la Facultad de Ingeniería al que pertenecí con mucho 
orgullo, así como al Plan de Becarios de la Dirección de Sistemas de la Dirección General de Cómputo 
y Servicios Académicos por haber complementado mi formación académica. 
 
 
A todos mis profesores que me transmitieron sus conocimientos y contribuyeron a mi formación tanto 
académica como personal. 
 
 
Al Dr. Boris Escalante Ramírez por haberme introducido al mundo del procesamiento digital de 
imágenes y ser una guía para el desarrollo del presente trabajo. Gracias por sus consejos y su amistad. 
 
 
 
Miguel Andrés Troncoso Muñoz 
 
 v
Contenido 
 
 
Agradecimientos iii 
Contenido v 
Lista de Figuras vii 
Introducción 1 
 
1. Conceptos Generales 3 
1.1. Visión humana ........................................................................................................................ 3 
1.1.1. Percepción y codificación ............................................................................................. 3 
1.1.2. Modelos de la visión humana ....................................................................................... 6 
1.2. Principios de compresión ........................................................................................................ 7 
1.2.1. Codificación de fuente .................................................................................................. 8 
1.2.2. Cuantización ................................................................................................................. 9 
1.2.3. Codificación de entropía ............................................................................................... 9 
1.3. Estándares de compresión de video......................................................................................... 11 
1.3.1. MPEG ........................................................................................................................... 11 
1.3.1.1. Video MPEG ........................................................................................................ 11 
1.3.1.2. Sintaxis de video MPEG-1 ................................................................................... 15 
1.3.1.3. MPEG 2 ................................................................................................................ 17 
1.3.1.4. MPEG 4 y 7 .......................................................................................................... 18 
1.3.2. Otros estándares de compresión ................................................................................... 18 
1.4. Esquemas de estimación de movimiento ................................................................................ 19 
1.4.1. Block-Matching ............................................................................................................ 20 
1.4.2. Estimación basada en el gradiente ................................................................................ 22 
1.4.3. Estimación en el dominio de la frecuencia ................................................................... 22 
1.5. Transmisión de video digital sobre Internet ........................................................................... 23 
1.5.1. Principales obstáculos y soluciones .............................................................................. 24 
1.5.2. Protocolos para transmisión de video ........................................................................... 26 
 
2. Codificación de imágenes por transformada 29 
2.1. Esquema general ..................................................................................................................... 29 
2.2. Transformada de Hermite ....................................................................................................... 30 
2.2.1. Descomposición de la imagen ...................................................................................... 32 
2.2.2. Reconstrucción de la imagen ........................................................................................ 33 
2.2.3. Latís de muestreo .......................................................................................................... 34 
2.2.4. Rotación local ............................................................................................................... 35 
 
3. Lenguaje de programación Java 37 
3.1. ¿Que es Java? .......................................................................................................................... 37 
3.2. Conceptos de programación orientada a objetos .................................................................... 38 
3.3. Objetos, clases e interfaces ..................................................................................................... 38 
3.4. Operadores, tipos de datos y modificadores de acceso ........................................................... 40 
3.5. Applets .................................................................................................................................... 41 
3.5.1. Plug-in de java para exploradoresy htmlconverter ...................................................... 42 
3.6. Seguridad en Java ................................................................................................................... 43 
3.6.1. Llaves y certificados digitales ...................................................................................... 44 
3.6.1.1. keytool .................................................................................................................. 45 
3.6.1.2. jarsigner ................................................................................................................ 45 
 
 vi
3.7. Java Media Framework ........................................................................................................... 46 
3.7.1. Arquitectura de JMF ..................................................................................................... 46 
3.7.1.1. Modelo temporal ................................................................................................... 47 
3.7.1.2. Modelo de eventos ................................................................................................ 48 
3.7.1.3. Modelo de datos .................................................................................................... 49 
3.7.1.4. Controles ............................................................................................................... 50 
3.7.1.5. Extensibilidad ....................................................................................................... 50 
3.7.2. Presentación y procesamiento de multimedia ............................................................... 51 
3.7.2.1. Players ................................................................................................................... 52 
3.7.2.2. Processors ............................................................................................................. 53 
3.7.2.3. Controles de presentación y procesamiento ......................................................... 54 
3.7.3. Captura, almacenamiento y transmisión de multimedia ............................................... 55 
3.7.4. JMF RTP API ............................................................................................................... 56 
3.7.4.1. RTPManager ......................................................................................................... 56 
3.7.4.2. Eventos RTP ......................................................................................................... 56 
3.7.4.3. Datos RTP ............................................................................................................. 56 
3.7.4.4. Recepción y presentación de flujos multimedia en RTP ...................................... 56 
3.7.4.5. Transmisión de flujos multimedia en RTP ........................................................... 57 
3.7.4.6. Extendiendo JMF RTP ......................................................................................... 57 
 
4. Desarrollo del sistema de codificación y transmisión de video 59 
4.1. Modelo del sistema en general ............................................................................................... 59 
4.2. Codificación y decodificación ................................................................................................ 59 
4.2.1. Implantación del codificador ........................................................................................ 60 
4.2.2. Implantación del decodificador .................................................................................... 61 
4.3. Algoritmo de estimación de movimiento ............................................................................... 61 
4.4. Algoritmo de la transformación de imágenes ......................................................................... 63 
4.4.1. Aplicación de la DHT ................................................................................................... 64 
4.4.2. Submuestreo de los coeficientes ................................................................................... 65 
4.4.3. Rotación de los coeficientes ......................................................................................... 66 
4.5. Cuantización ........................................................................................................................... 67 
4.6. Codificación de entropía.......................................................................................................... 71 
4.7. Sintaxis de la trama ................................................................................................................. 71 
4.8. Transmisión de video .............................................................................................................. 72 
4.8.1. Corrección de pérdida de datos....................................................................................... 73 
4.9. Despliegue de las imágenes..................................................................................................... 73 
4.10 . Resultados del sistema........................................................................................................... 74 
4.10.1. Velocidades de procesamiento...................................................................................... 74 
4.10.2. Radios de compresión ................................................................................................... 75 
 
5. Conclusiones 77 
5.1 Anotaciones finales ................................................................................................................... 77 
5.2 Mejoras propuestas ................................................................................................................... 77 
5.3 Campos de aplicación ............................................................................................................... 78 
 
Referencias 79 
 
Anexo A. Secuencias de prueba 85 
 
Anexo B. Documentación del código fuente 87 
 
 vii
Lista de figuras 
 
 
1.1. Sección transversal del ojo humano................................................................................................ 3 
1.2. Distribución de conos y bastones en la retina ................................................................................. 4 
1.3. Espectro sensitivo de un ser humano “típico” ................................................................................ 5 
1.4. Escalas de grises.............................................................................................................................. 6 
1.5. Sensibilidad espectral de un observador “típico” ........................................................................... 6 
1.6. Diagrama de bloques de un algoritmo de codificación de imágenes.............................................. 8 
1.7. Grupo de imágenes MPEG ............................................................................................................ 12 
1.8. Barrido en forma de zigzag de los coeficientes DCT .................................................................... 13 
1.9. Codificador típico MPEG .............................................................................................................. 14 
1.10. Decodificador típico MPEG......................................................................................................... 15 
1.11. Capas de un flujo de video........................................................................................................... 15 
1.12. Block-Matching ........................................................................................................................... 20 
1.13. Pila de protocolos para video streaming ...................................................................................... 27 
 
2.1. Sistema de codificación por transformada: (a) codificador;(b) decodificador ............................. 29 
2.2. Análisis y síntesis de la transformada polinomial.......................................................................... 31 
2.3. Funciones de los filtros en el dominio espacial para σ = 1............................................................ 32 
2.4. Distribución de los operadores sobre rejillas de muestreo cuadradas............................................ 34 
 
3.1. Grabación, procesamiento y presentación de elementos multimedia ............................................ 46 
3.2. Arquitectura global de JMF ........................................................................................................... 47 
3.3. Modelo temporal de JMF............................................................................................................... 47 
3.4. Modelo de datos de JMF................................................................................................................ 49 
3.5. Modelo de reproducción de JMF. .................................................................................................. 52 
3.6. Estados de un Player...................................................................................................................... 52 
3.7. Estados de un Processor ................................................................................................................ 54 
 
4.1. Modelo del sistema de codificación y transmisión de video ......................................................... 59 
4.2. Esquema propuesto del codificador de video ................................................................................ 60 
4.3. Esquema propuesto del decodificador de video............................................................................. 61 
4.4. Ejemplo de convergencia para el algoritmo de “búsqueda por los tres pasos”.............................. 62 
4.5. Coeficientes DHT para N=2 .......................................................................................................... 65 
4.6. Submuestreo de los coeficientes de “DC” sobre una latís tipo quincunx ...................................... 66 
4.7. Coeficientes DHT rotados para N=2 ............................................................................................. 67 
4.8. Ángulos discretos en una rejilla de muestreo cuadrada ................................................................. 68 
4.9. Imágenes codificadas con N=2 y diferentes valores de cuantización............................................ 69 
4.10. Imágenes codificadas con N=4 y diferentes valores de cuantización.......................................... 70 
4.11. Sintaxis de la trama...................................................................................................................... 71 
4.12 Ventana del navegador Firefox recibiendo la señal de video 
capturada en el Laboratorio de Imágenes de la Facultad de Ingeniería ................................................ 74 
4.13. Tiempo de procesamiento para diferentes órdenes de transformación en 
diferentes computadoras ....................................................................................................................... 75 
 
 
 
 
Introducción 
 
 
El video digital ha tenido un gran desarrollo en los últimos años de tal manera que hoy en día podemos 
encontrar un sin número de aplicaciones que lo utilizan como es el caso de las videoconferencias, 
videotelefonía, televisión digital, cámaras de video digital caseras, DVD, teléfonos celulares con 
cámara de video, transmisión de video en Internet, monitoreo, por mencionar algunas. 
 
El desarrollo del video digital ha obedecido entre otras cosas a las ventajas que ofrece en la transmisión 
y almacenamiento del mismo. Sin embargo, debido a la cantidad de información requerida por el video 
digital, los anchos de banda de los canales de transmisión y las capacidades limitadas de los medios de 
almacenamiento, un factor importante en los esquemas de codificación de video es la compresión de 
datos. 
 
Los sistemas de codificación de video se apoyan en un principio en la codificación de las imágenes que 
conforman a las secuencias de video. La mayoría de los esquemas actuales de codificación de video 
digital utilizan una codificación por transformada para las imágenes basada en la transformada coseno 
discreta (DCT), tal es el caso de MPEG. La DCT logra buenos resultados en la compresión de datos en 
función de que descompone a las imágenes en sus componentes de frecuencia, agrupando la 
información o la energía de las imágenes en pocos coeficientes de transformación. Sin embargo, la 
DCT no toma en cuenta las características del sistema de visión humana (SVH). A diferencia de la 
DCT, la transformada de Hermite discreta (DHT), que es un caso particular de la transformada 
polinomial discreta, se basa los modelos biológicos de los campos receptivos del SVH estudiados, los 
cuales obedecen a funciones gaussianas. 
 
El objetivo del presente trabajo es desarrollar un esquema alterno de codificación de video digital 
basado en la transformada polinomial, específicamente en la transformada de Hermite, que se 
ajuste a los modelos de la visión humana para obtener imágenes que sean percibidas con calidad 
visual para el ojo humano y al mismo tiempo lograr una compresión de las secuencias de video e 
implementarlo en el desarrollo de un sistema de transmisión de video en tiempo real que funcione 
sobre redes TCP/IP. 
 
En el capítulo 1 se presentan los conceptos generales utilizados en la codificación y transmisión de 
video digital, como es el caso del estudio del sistema de visión humana, las técnicas de compresión de 
información, los estándares actuales de codificación de video, los métodos de estimación de 
movimiento y la transmisión de video digital sobre Internet. El capítulo 2 muestra el tema relacionado 
con la codificación por transformada de imágenes y describe la transformada utilizada en el desarrollo 
del sistema de codificación del presente trabajo. El capítulo 3 está dedicado al lenguaje de 
programación Java por ser éste el elegido para el desarrollo del sistema. En el capítulo 4 se describe la 
implantación del sistema de codificación y transmisión, mostrando el esquema de codificación y 
decodificación propuesto, el algoritmo de estimación de movimiento utilizado, el algoritmo de la 
transformación de imágenes, los procesos de cuantización y codificación de entropía, la sintaxis 
propuesta de la trama del video codificado, el tipo de transmisión, el despliegue de las imágenes en el 
cliente y finalmente los resultados obtenidos con relación a las velocidades de procesamiento y a los 
radios de compresión. Por último, el capítulo 5 está dedicado a las conclusiones del trabajo, las mejoras 
propuestas y los campos de aplicación. 
 
 1
Capítulo 1 
Conceptos Generales 
 
 
Este primer capítulo tiene como objetivo introducir al lector con algunos de los conceptos básicos 
necesarios para comprender el desarrollo del presente trabajo. En primer lugar hablaré de la visión 
humana y los modelos matemáticos que se han desarrollado para tratar de explicarla. A continuación 
trataré las técnicas de compresión de datos utilizadas para la codificación de imágenes y video. 
Enseguida mostraré los estándares de codificación de video, poniendo más atención en el estándar 
MPEG. Posteriormente hablaré de las técnicas de estimación de movimiento utilizadas para la 
codificación del video digital. Finalmente presentaré los temas relacionados con redes y transmisión del 
video. 
 
1.1 Visión humana 
 
Es importante comenzar el presente trabajo con los conceptos básicos de la visión humana, ya que el 
procesamiento digital de imágenes y de video tiene como principal objetivo, más no el único, obtener, 
procesar y mostrar información gráfica para la percepción visual humana. Por lo tanto, es necesario 
comprender las características y limitaciones del sistema devisión humana (SVH), los modelos de los 
procesos visuales necesarios para el diseño de sistemas de procesamiento de imágenes y de esta 
manera, poder generar medidas de fidelidad e inteligibilidad de las imágenes procesadas. 
 
1.1.1 Percepción y codificación 
 
El ojo humano es casi una esfera de 2 cm de diámetro aproximadamente, formada por un conjunto de 
membranas denominadas córnea, esclera o esclerótica, coroide y retina [1]. La figura 1.1 muestra la 
sección transversal del globo ocular humano. 
 
Figura 1.1. Sección transversal del ojo humano [3]. 
 
La pared exterior en su porción posterior está formada por la esclerótica. Esta porción blanca de la 
pared ocular tiene una función protectora. La porción anterior de la pared esta constituida por la córnea 
que es una membrana transparente que permite la entrada de los rayos luminosos. Detrás de la córnea 
3 
Conceptos Generales 4
hay un espacio lleno de líquido claro llamado humor acuoso que separa la córnea de la lente del 
cristalino. 
La capa media o úvea tiene a su vez tres diferentes partes: la coroide que es una capa vascular 
encargada de nutrir al ojo. Se continúa hacia delante con el cuerpo ciliar encargado de producir el 
humor acuoso y a continuación queda el iris. Este último es encargado de regular la cantidad de luz que 
entra al ojo con ayuda de una abertura llamada pupila. 
 
La retina es la capa más interna y también la más compleja. Está compuesta principalmente por células 
nerviosas. Las células receptoras sensibles a la luz se encuentran en su superficie exterior delante de 
una capa de tejido pigmentado. Estos fotorreceptores se llaman conos y bastones. Cuando la luz llega 
al ojo, la imagen que transporta se forma en la retina por la sensibilización de estos fotorreceptores. La 
retina es mucho más que un conjunto de células fotorreceptoras, pues contiene además otras células 
nerviosas cuyas interacciones sinápticas suponen el inicio del complejo procesamiento de las señales 
visuales. La retina contiene 5 tipos principales de células: fotorreceptoras, bipolares, horizontales, 
amacrinas y ganglionares. Cada una de ellas funciona de manera similar a un filtro que permite detectar 
ciertos rasgos de una imagen y discernirlos de otros (bordes, líneas, texturas, color, etc.). 
 
La noción de campo receptivo de una neurona de la vía visual es el concepto fundamental en el que se 
asienta la neurofisiología sensorial moderna y, por supuesto, los modelos fisiológicos que tratan de 
explicar la visión. Un campo receptivo es un área de la retina (formada por un conjunto de 
fotorreceptores) cuyas respuestas a los impulsos que recibe influyen en células más avanzadas de 
procesamiento visual. De tal modo que tiene lugar un análisis de la imagen la cual es procesada por 
pequeños trozos o campos receptivos [2]. 
 
El número de conos existentes en un ojo está entre 6 y 7 millones y su situación dentro de él se 
concentra alrededor de un punto llamada fóvea. La misión de los conos es doble, por un lado son 
responsables de la detección del color y por otra ayudan a resolver los detalles finos de la imagen. La 
visión a través de los conos se denomina visión fotocópica o de luz brillante. 
 
Por otro lado, el número de bastones existentes en un ojo es muy superior a la de los conos y está entre 
75 y 150 millones. Los bastones se distribuyen sobre toda la retina y al igual que los conos tienen una 
doble misión. Por un lado son responsables de dar una impresión general del campo de visión y por 
otro lado son responsables de la sensibilidad a niveles bajos de iluminación, ya que son más sensibles a 
la luz que los conos. A la visión a través de los bastones se le denomina visión escotópica o de luz 
tenue [3]. La figura 1.2 muestra la distribución de los conos y los bastones en la retina. 
 
 
Figura 1.2. Distribución de conos y bastones en la retina [3]. 
 
Conceptos Generales 5
 
 
El nervio óptico se encarga a través de las múltiples fibras que lo conforman, de enviar la información 
visual desde el ojo hacia el cerebro. En el punto donde parte del globo ocular no existen conos ni 
bastones por lo que se forma una zona conocida como punto ciego. 
 
Debido a la localización de los conos en el ojo alrededor de la fóvea, cuando observamos un objeto que 
abarca varios grados del campo de visión es necesario realizar movimientos del ojo, pues los detalles 
de la información visual únicamente pueden ser obtenidos a través de la fóvea, es decir, necesitamos 
que la luz del objetivo que queremos enfocar u observar con una alta resolución sea reflejada en la 
fóvea. Los demás objetos se perciben con una baja resolución o borrosos. El campo de visión que 
abarca la fóvea es tan sólo de alrededor de un grado. Generalmente ocurren 3 fijaciones del ojo por 
segundo; estas fijaciones del ojo están intercaladas por rápidos saltos del ojo durante los cuales la 
visión es suprimida. Este fenómeno fue observado por Guy Buswell [4] y más ampliamente estudiado 
por primera vez por Alfred Yarbus [5]. De esta manera es como obtenemos información de alta y baja 
resolución de una escena. 
 
Con respecto a la sensibilidad del brillo del SVH, podemos dividirla en la sensibilidad con respecto a la 
longitud de onda y la sensibilidad con respecto al estimulo. 
En el caso de la sensibilidad con respecto a la longitud de onda, el SVH tiene limitaciones con relación 
a las longitudes de las ondas electromagnéticas, es decir que sólo percibimos señales en un rango del 
espectro electromagnético. Las ondas electromagnéticas para las cuales el ojo humano está adaptado se 
encuentran entre longitudes de onda de 400 nm (violeta) y 700 nm (rojo). La siguiente figura muestra el 
espectro sensitivo para un ser humano “típico”. 
 
 
Figura 1.3. Espectro sensitivo de un ser humano “típico” [6]. 
 
En el caso de la sensibilidad con respecto al estímulo, se ha demostrado que la respuesta visual R es 
proporcional al logaritmo de la intensidad del brillo I. Esto es conocido como la ley de Webner-
Fechner. 
 
)log(IR = (1.1) 
 
En la figura 1.4 se muestran dos escalas de grises. En la parte alta las intensidades están espaciadas de 
manera uniforme. En la parte baja se muestran intensidades espaciadas de manera exponencial las 
cuales son percibidas como mejor ecualizadas por la visión humana. Adicionalmente, en la figura 1.4 
se puede observar un fenómeno conocido como “Mach bands” [7]. A pesar de que el brillo físico es 
constante en cada franja vertical, el ser humano percibe una variación en los límites de cada banda, 
Conceptos Generales 6
apreciando un brillo mayor en la frontera con un tono más oscuro y un brillo menor en la frontera con 
un tono más claro. 
 
Figura 1.4. Escalas de grises. 
 
Con relación a la percepción del color en el SVH podemos mencionar que en años recientes se ha 
determinado experimentalmente que existen tres tipos básicos de conos en la retina. Estos conos poseen 
diferentes características de absorción en función de la longitud de onda con máximos en las regiones 
roja )(λx , verde )(λy y azul )(λz del espectro óptico como se muestra en la figura 1.5. La existencia 
de tres tipos de conos provee bases fisiológicas para la teoría tricromática de la visión a color. 
 
Figura 1.5. Sensibilidad espectral de un observador “típico” [6]. 
 
En lo que respecta a la percepción espacio-temporal, es decir, a la manera en como percibimos el 
movimiento de los objetos, existen también diferentes estudios. El procesamiento del movimiento es 
generalmente entendido como un proceso que consiste en varias etapas [8], [9], [10], [11]. En la 
primera etapa o “etapa temprana del movimiento”, se toman en cuenta los valores de luminancia del 
estímulo visual y la sensibilidad a la dirección del movimiento de contornos de una dimensión en la 
dirección de un eje espacial en particular. En etapas posteriores se estudian las respuestas neuronales y 
las interpretacionesrealizada por el cerebro de dichos estímulos. 
 
1.1.2 Modelos de la visión humana 
 
Gracias a los estudios fisiológicos realizados al SVH se han podido desarrollar modelos eficientes que 
aprovechen sus características. En el campo de la codificación de imágenes, Schreiber fue uno de los 
primeros en reconocer las implicaciones de los modelos de visión humana [12]. Stockham comenzó el 
 
Conceptos Generales 7
 
 
diseño de las técnicas de procesamiento de imágenes basados en modelos biológicos, desarrollando una 
técnica de realce de contraste basado en la propiedad de que la percepción del brillo de escenas 
naturales está principalmente determinada por las propiedades de reflexión de la escena iluminada y no 
por la intensidad de la fuente de iluminación [13]. Tanto los neurobiólogos como los psicofísicos 
coinciden en que los procesos de visión en sus etapas primarias pueden ser descritos por un conjunto de 
canales operando en paralelo. El brillo de cada posición dentro del campo visual es obtenido integrando 
las respuestas de todas las celdas con diferentes tamaños de campos receptivos en esa posición. 
 
El modelado de los campos receptivos ha sido una práctica común entre los fisiólogos desde la 
introducción de las ecuaciones de Hartline-Ratliff [14],[15]. En diferentes estudios se han propuesto 
ecuaciones utilizando campos receptivos lineales. En dichos modelos, la respuesta neuronal es una 
suma del contraste de los estímulos locales utilizando una función de peso. Rodieck [16] propuso 
diferencias de Gaussianas concéntricas como modelo del perfil de la sensibilidad de los campos 
receptivos de las células de la retina. Así mismo, Young [17] demostró que la distribución de los 
campos receptivos del ojo humano obedece a funciones derivativas Gaussianas. Dos modelos que 
utilizan el modelo de los campos receptivos con funciones Gaussianas son el modelo de Gabor y el 
modelo de Hermite. 
 
Uno de los modelos del SVH más utilizados en la codificación de imágenes es el modelo de Gabor 
[18], que representa a los campos receptivos de la corteza visual con funciones Gaussianas moduladas 
con exponenciales complejas. Básicamente el modelo de Gabor es el producto de una función seno o 
coseno y una función Gaussiana. La transformada de Gabor es utilizada para codificar imágenes y 
secuencias de imágenes explotando el SVH introduciendo un error de cuantización de manera que no 
sea visualmente ofensivo. 
 
Otro modelo relacionado con funciones Gaussianas estudiado por Martens [19] interpreta derivadas 
Gaussianas como el producto de polinomios Hermitianos y una ventana Gaussiana, donde las imágenes 
son descompuestas en un conjunto de polinomios Hermitianos. La transformación de la imagen 
introducida por Martens descompone una imagen utilizando derivadas de Gaussianas. El presente 
trabajo se basa en la transformada Hermitiana, de la que se hablará mas a detalle en el capítulo 2. 
 
1.2 Principios de compresión 
 
Cuando se trabaja con imágenes digitales ocupamos grandes cantidades de datos, los cuales 
generalmente necesitamos almacenar o transmitir de un lugar a otro. Debido a las limitaciones tanto de 
los medios de almacenamiento, pero principalmente de los anchos de banda de los canales de 
transmisión necesitamos utilizar diferentes técnicas de compresión. 
 
Las imágenes contienen una cantidad considerable de información redundante y mucha que es 
irrelevante para el sistema de visión humana. La codificación de imágenes se basa principalmente en 
este hecho, pues su objetivo es poder describir la imagen original con el menor número de datos y al 
mismo tiempo conservar la mejor calidad visual posible. Las técnicas de compresión de datos explotan 
las redundancias inherentes e irrelevantes reduciendo la cantidad de datos original a un menor tamaño 
para posteriormente reconstruirla de manera exacta o aproximada. La razón entre la cantidad de datos 
originales y los datos después de ser comprimidos se conoce como el radio de compresión. 
 
Algunos algoritmos de compresión de datos son con pérdidas, mientras que otros no lo son. Un 
algoritmo sin pérdidas elimina sólo la información redundante, de manera que se puede recuperar de 
manera exacta la información. Un método de compresión con pérdidas elimina también la información 
Conceptos Generales 8
considerada irrelevante y esto permite sólo una reconstrucción aproximada del original. Como es de 
suponerse, los métodos de compresión con pérdidas logran radios de compresión más altos. En el caso 
de imágenes digitales, una pequeña pérdida de fidelidad es casi siempre aceptable para lograr un muy 
alto nivel de compactación. 
 
Los tiempos requeridos para la compresión y descompresión de datos no son despreciables. Los 
algoritmos que logran una compactación mayor no son generalmente los más rápidos, lo cual es algo 
que se tiene que tomar en cuenta en sistemas en tiempo real, como es el caso del presente trabajo. 
 
En la actualidad, los algoritmos de codificación que reducen la cantidad de datos para representar una 
imagen combinan diferentes técnicas de compresión. En la figura 1.6 se muestra el diagrama de 
bloques que representa el procesamiento que utilizan dichos algoritmos. 
 
 
Figura 1.6. Diagrama de bloques de un algoritmo de codificación de imágenes. 
 
La preparación de la imagen incluye la conversión analógica a digital y la generación de una 
representación digital apropiada de los datos. 
El procesamiento o transformación es el primer paso del proceso de compresión utilizando 
algoritmos sofisticados. Por ejemplo, una transformación del dominio del tiempo al dominio de la 
frecuencia puede ser realizada utilizando la DCT. 
La cuantización relaciona los números obtenidos del paso anterior a un intervalo de cuantización 
reduciendo la precisión. 
La codificación de entropía es comúnmente la última etapa en este esquema. Comprime la secuencia 
de bits obtenida de los procesos anteriores sin pérdida de datos utilizando una representación diferente 
que requiera menos bits por unidad de datos. 
 
En las siguientes secciones se describen más a detalle los procesos mencionados. 
 
1.2.1 Codificación de fuente 
 
La codificación de fuente en imágenes toma ventaja de las propiedades del ojo humano y la semántica 
de los datos como es el caso de las redundancias espaciales en imágenes fijas y las redundancias 
temporales en el caso de video. Existen varias técnicas que se pueden clasificar en este rubro como se 
mencionan a continuación. 
 
Las técnicas de compresión más simples están basadas en la interpolación y el submuestreo. En este 
caso es posible hacer uso de las características específicas de la visión humana. Por ejemplo, el ojo 
humano es más sensible a las diferencias en el brillo que a las diferencias en el color. Por lo tanto, es 
razonable dividir la imagen en componentes YUV (luminancia Y; dos crominancias U, V) en lugar de 
componentes RGB (rojo, verde y azul). En donde Y = 0.3R + 0.59G + 0.11B, U = B – Y, V = R - Y. 
De esta manera las componentes U y V pueden ser muestreadas con una resolución más baja. 
 
La codificación de diferencias conocida también como codificación con predicción o codificación 
relativa se basa en valores anteriores, codificando únicamente la diferencia entre el valor actual y el 
valor anterior. Un ejemplo de esta técnica es conocida como DPCM (Differential Pulse Code 
Modulation) utilizada comúnmente para codificar audio [20]. En el caso del video, el uso de la 
 
Conceptos Generales 9
 
 
codificación relativa en el dominio del tiempo se basa en el hecho de que en una secuencia existen 
muchas áreas que no cambian, o cambian muy poco. De esta manera, únicamente son codificadas las 
diferencias con la imagen anterior. 
 
La codificación por transformada utiliza un enfoque diferente: los datos son transformados en un 
dominio matemático diferente que sea más adecuado para la compresión. El ejemplo más familiar es la 
Transformada de Fourier que convierte los datosdel dominio del tiempo al dominio de la frecuencia. 
Otra transformación comúnmente utilizada es la DCT, utilizada por el formato JPG. En el presente 
trabajo se hace uso de la transformada polinomial, específicamente de la Transformada Hermitiana 
Discreta (DHT). 
El dominio original es una imagen de dos dimensiones, en la que cada píxel es representado por un 
valor en escala de grises o un valor de color. Si elimináramos algunos píxeles para comprimir los datos 
sería visualmente molesto. En el domino transformado los elementos de la imagen son representados 
por coeficientes de frecuencias: el coeficiente de “DC” describe el valor de gris promedio, mientras que 
los coeficientes de frecuencias altas corresponden a los bordes nítidos. Si se sacrifica precisión para los 
coeficientes de orden altos el efecto visual seria tener menos detalles en los bordes nítidos de la 
imagen. Para muchas aplicaciones esto es visualmente más aceptable que perder precisión en el 
dominio de dos dimensiones de la imagen. En el capítulo 2 se tratará mas a detalle la codificación de 
imágenes por transformada. 
 
Otra técnica es la codificación por bandas en la que en lugar de convertir todos los datos a otro 
dominio se realiza una transformación seleccionando bandas de frecuencia y realizando codificaciones 
diferentes para cada banda [21]. 
 
1.2.2 Cuantización 
 
El ojo humano responde con diferente sensibilidad a la información visual que recibe. La información a 
la que es menos sensible se puede descartar sin afectar a la percepción de la imagen. Se suprime así lo 
que se conoce como redundancia visual. La eliminación de la redundancia esta relacionada con la 
cuantificación de la información, lo que conlleva una pérdida de información irreversible. Existen dos 
tipos de cuantización: escalar y vectorial. 
 
La cuantización escalar se lleva a cabo forzando a que la imagen tenga un número menor de niveles 
de gris. Cuando la entrada cae entre dos umbrales de decisión, la salida es colocado en el nivel 
representativo correspondiente. 
 
La cuantización vectorial es un procedimiento más moderno mediante el cual los datos son divididos 
en bloques de n bytes (n >1). Una tabla predefinida contiene un conjunto de patrones. Para cada bloque 
se identifica la entrada de la tabla con el patrón más similar. Cada patrón de la tabla es asociado con un 
índice. Dicha tabla puede ser multidimensional, en este caso el índice es un vector. Este vector es 
utilizado como el código para el bloque de bytes. El decodificador utiliza la misma tabla para generar 
una aproximación de los datos originales. Para más detalles de este método, ver [22]. 
 
1.2.3 Codificación de Entropía 
 
La codificación de entropía es un proceso sin pérdidas que puede ser utilizado para cualquier tipo de 
datos. Los datos a ser comprimidos son considerados únicamente como una secuencia de bits y su 
semántica es ignorada. 
Conceptos Generales 10
Shannon [23] definió una medida de la información dada por la ocurrencia del símbolo ak en el mensaje 
como: 
 
[ ])(log)( kk aPaI −= (1.2) 
 
La entropía de la fuente está definida por: 
[∑
−
=
−==
1
0
)(log)()}({
K
k
kkk aPaPaIEH ] (1.3) 
 
 y especifica el promedio de información contenido por símbolo de los mensajes generados por la 
fuente. La entropía de un mensaje es no negativa y llega a su valor máximo cuando todos los símbolos 
son igualmente probables. Si escogemos 2 como la base del logaritmo, las unidades de entropía serán 
entonces bits por símbolo. 
A continuación se describen brevemente algunas técnicas de codificación de entropía. 
 
La codificación de longitud corrida o Run-Length se basa en el hecho de que las muestras de datos 
de imágenes y video contienen secuencias de bytes idénticas. Reemplazando estas secuencias de bytes 
con un carácter de escape, luego el byte que se repite y finalmente el número de sus ocurrencias, la 
cantidad de datos pueden ser reducidos significativamente. 
La codificación de longitud corrida es una generalización de la supresión de ceros. La supresión de 
ceros asume que únicamente un símbolo en particular es el que sucede con mayor frecuencia en los 
datos. Todas las secuencias de tres o más ocurrencias de este símbolo son sustituidas por un carácter de 
escape y un número que especifique las ocurrencias del mismo. 
 
Una técnica que puede ser utilizadas para la compresión de texto es sustituir bytes aislados por patrones 
que ocurran frecuentemente. Por ejemplo, en un programa escrito en un lenguaje de programación de 
alto nivel podemos sustituir algunas palabras como “if”, “begin", “end”, por un carácter de escape y un 
número que sirva de índice, utilizado como referencia a una lista de 256 palabras. Esta técnica es 
conocida como sustitución de patrones estáticos. 
 
Si no se conocen a priori las secuencias de símbolos que ocurren más frecuentemente, la situación es 
diferente. En este caso mientras se codifican los datos se puede ir construyendo una tabla de códigos y 
de esta manera encontrar patrones que ocurran frecuentemente. A esta técnica se le conoce como 
sustitución de patrones dinámicos. Un ejemplo de esta técnica es la utilizada por el algoritmo 
Lempel-Ziv comúnmente implementado en las utilerías del sistema operativo UNIX para comprimir 
datos. 
 
En la codificación de longitud variable la idea es representar los datos con diferentes números de bits, 
en lugar de utilizar siempre un número fijo. El código Morse es un ejemplo en el que los caracteres que 
ocurren con mayor frecuencia son representados con un patrón más corto. El código depende de la 
frecuencia de las ocurrencias de los bytes de datos en una secuencia. Existen varios ejemplos que 
utilizan técnicas basadas en métodos estadísticos, el ejemplo más importante es el desarrollado por 
David Huffman [24]. El código de Huffman es un método estadístico sin pérdidas que siempre 
encuentra un código de longitud variable con la menor redundancia posible. Usa un árbol de 
codificación binario para representar los valores que tienen mayor ocurrencia con pocos bits y los 
valores con menor ocurrencia con más bits. 
 
Conceptos Generales 11
 
 
Gharavi es uno de los autores que ha realizado diferentes estudios utilizando esta técnica, al igual que 
la codificación por longitud corrida para codificar imágenes representadas con niveles de grises 
[25],[26]. 
 
1.3 Estándares de compresión de video 
 
Comercialmente, la estandarización internacional de protocolos y sistemas de comunicación con video 
ha ayudado a cumplir dos propósitos: interoperabilidad y reducción de costos. Desde el principio de los 
años 80 comenzaron un gran número de actividades internacionales de estandarización de audio y 
video dentro del Comité Consultivo de Telefonía Internacional (CCITT), seguidos del Comité 
Consultivo Internacional de la Radio (CCIR) y la Organización Internacional de Estandarización (ISO). 
En la actualidad existen diferentes estándares para codificar video digital. Los más utilizados son los 
desarrollados por la ISO a través del Grupo de Expertos en Imágenes en Movimiento o MPEG (Moving 
Picture Experts Group). A continuación se explican brevemente algunos de los estándares principales. 
 
1.3.1 MPEG 
 
El estándar MPEG-1 fue publicado en 1992 y define la representación del flujo de bits para audio y 
video digital sincronizados y comprimidos para ocupar un ancho de banda de 1.5 Mbits/s. MPEG-1 
está formado por tres partes o capas: video MPEG, audio MPEG y el sistema MPEG encargado de 
controlar el flujo tanto del video como del audio. La aplicación más importante de MPEG-1 es el 
almacenamiento de la información audio visual en medios digitales, tales como CD-ROM y DAT. La 
codificación que realiza MPEG-1 se basa en la codificación de imágenes JPG y el estándar H.261. Sólo 
se muestra lo relacionado con el video MPEG, pues el audio MPEG queda fuera del alcance del 
presentetrabajo. 
 
1.3.1.1 Video MPEG [27],[28] 
Ya se ha mencionado que cuando trabajamos con una secuencia de imágenes o video existe una gran 
correlación entre imágenes sucesivas. A las imágenes codificadas que utilizan información de otras 
imágenes se les denomina inter-codificadas o inter-coded. Cuando se da un cambio de escena (y en 
ocasión por otros motivos) no funciona la inter-codificación y el modelo de compresión cambia. En 
este caso el modelo de compresión debe ser estructurado para tomar ventaja de la similitud que existe 
en una región dada de la imagen con respecto a las áreas adyacentes de la misma. Las imágenes 
codificadas que no utilizan la información de otras imágenes son llamadas intra-codificadas o intra-
coded. 
 
MPEG aprovecha la similitud entre una imagen y la siguiente en una secuencia. Cada secuencia de 
video MPEG está dividida en grupos de imágenes (GOP) y cada grupo de imágenes se compone de 
una o más imágenes. Existen cuatro diferentes tipos de imágenes en el estándar MPEG-1, llamados “I”, 
“P”, “B” y “D”. La primera imagen del video debe ser una imagen intra-codificada o imagen de tipo 
“I”. Detrás de cada imagen de tipo “I”, pueden existir dos tipos de imágenes basadas en predicción o 
inter-codificadas. Las imágenes con predicción hacia delante son llamadas imágenes “P”. La referencia 
para estas imágenes es la última imagen de tipo “I” o “P”. Otro tipo de predicción es la predicción 
hacia atrás con una referencia a una imagen futura de tipo “I” o “P”. También puede utilizarse una 
predicción bidireccional en donde se utilice como referencia la ultima y la siguiente imagen de tipo “I” 
o “P”. Estas dos últimas predicciones son utilizadas por las imágenes de tipo “B”. Las imágenes de tipo 
“B” no pueden ser utilizadas como referencias. El tipo de imágenes “D” son imágenes que utilizan 
únicamente los coeficientes de DC. Estas imágenes son utilizadas principalmente para un adelanto o 
Conceptos Generales 12
atraso rápido donde la calidad de la imagen puede ser menor, aunque raramente son utilizadas. En la 
figura 1.7 se muestra un ejemplo de un grupo de imágenes. 
 
 
Figura 1.7. Grupo de imágenes MPEG. 
 
Como MPEG utiliza información de imágenes futuras dentro de la secuencia, el orden de codificación 
no es el mismo que el orden de despliegue. En el caso de la figura 1.7, el orden de codificación de las 
imágenes es el siguiente: 
 
I-P-B-B-P-B-B-… 
 
El algoritmo de compresión MPEG comienza con una imagen en formato YCbCr. El bloque básico de 
construcción para una imagen MPEG es el macrobloque que consiste de un arreglo de 16 x 16 
muestras de luminancias (Y) y dos bloques de 8 x 8 para las componentes de crominancias (Cb, Cr). El 
arreglo de muestras de luminancias está realmente compuesto por cuatro bloques de 8 x 8. El 
procesamiento de las imágenes en MPEG trabaja sobre un bloque de 8 x 8 a la vez y siguen el modelo 
mostrado en la figura 1.6. 
 
La imagen MPEG no es simplemente un arreglo de macrobloques, sino que está compuesta de 
rebanadas o slices. Cada rebanada es una secuencia contigua de macrobloques en orden horizontal de 
barrido empezando en una posición específica de la imagen. Una imagen puede estar compuesta por 
una o más rebanadas. Esta estructura de rebanadas, entre otras cosas, permite una gran flexibilidad en 
cambios de señalización de algunos de los parámetros de la codificación. Esto es necesario tanto para 
optimizar como para controlar la calidad para una tasa de transmisión dada. A pesar de esto, algunas 
implementaciones de codificadores ignoran la estructura de rebanadas por causar esto una 
complicación computacional del algoritmo. 
 
Al igual que en JPEG1, la compresión de un bloque de 8 x 8 comienza con una DCT. Básicamente, la 
DCT es un método que descompone un bloque de datos en una suma ponderada de frecuencias 
espaciales. Cada uno de estos patrones de frecuencias espaciales tiene un coeficiente correspondiente: 
la amplitud necesaria para representar la contribución de ese patrón de frecuencia espacial en el bloque 
de datos analizado. El resultado de esta transformación es nuevamente una matriz de 64 coeficientes 
DCT. El coeficiente superior izquierdo de la matriz es llamado coeficiente de “DC” y representa el 
valor promedio de gris o de componente de color Cb o Cr. 
 
 
1 JPEG (Joint Photographic Experts Group) es un método de compresión de imágenes con pérdidas estandarizado por la 
ISO. 
Conceptos Generales 13
 
 
 
Después de obtener los coeficientes DCT, éstos son cuantizados dando más importancia a los 
coeficientes de DC y bajas frecuencias que a los de altas frecuencias para imágenes intra-codificadas. 
Para imágenes inter-codificadas todos los coeficientes son cuantizados asignándoles el mismo peso. La 
cuantización se lleva a cabo dividiendo los coeficientes por un entero positivo, llamado el valor de 
cuantización, y redondeando el cociente de esta división al entero más cercano. Los valores de 
cuantización forman la llamada “matriz de cuantización”, misma que el estándar JPEG recomienda. 
Esta matriz fue hallada a partir de una serie exhaustiva de experimentaciones llevadas a cabo por el 
grupo de expertos en diferentes tipos de imágenes, tratando de cuantificar la importancia relativa de 
cada uno de los coeficientes dentro de un análisis psicovisual. La cuantización en MPEG-1 es variable 
con el fin de mantener la tasa de bits de salida constante mientras se obtiene la mejor calidad de imagen 
posible. 
 
Los coeficientes son arreglados de acuerdo a una secuencia unidimensional en forma de zigzag como 
se muestra en la figura 1.8. El ordenamiento sigue el criterio de frecuencia espacial ascendente. Cómo 
la cuantización visualmente ponderada descarta fuertemente a las altas frecuencias espaciales, sólo 
algunos coeficientes de alta frecuencia son distintos de cero en una transformación típica. 
 
 
Figura 1.8. Barrido en forma de zigzag de los coeficientes DCT. 
 
Los coeficientes DCT cuantizados son codificados sin pérdida con una codificación de entropía que 
utiliza codificación de longitud corrida y codificación de longitud variable basada en el código 
Huffman. Esta codificación se basa en un diccionario de códigos llamado códigos de longitud variable 
(VLC). 
 
La codificación de los coeficientes de DC de los macrobloques sucesivos para imágenes de tipo “I” se 
lleva a cabo con la ayuda de un código diferencial de Huffman modificado. Se toma el primer 
coeficiente como referencia y se codifica sólo la diferencia con el siguiente, aprovechando la alta 
correlación que existe entre macrobloques adyacentes. 
 
Si hay movimiento en la secuencia, se puede obtener una mejor predicción codificando las diferencias 
relativas a las áreas que están corridas con respecto al área que está siendo codificada. A este proceso 
se le llama compensación de movimiento. El proceso que se lleva a cabo para determinar los vectores 
de movimiento en el codificador se llama estimación de movimiento. 
Conceptos Generales 14
Los vectores de movimiento que describen la dirección y cantidad de movimiento de los macrobloques 
son transmitidos al decodificador como parte del flujo de bits. Es entonces cuando el decodificador 
sabe que área de la imagen de referencia fue usada para cada predicción y suma la diferencia 
decodificada con esta predicción de movimiento compensado para obtener la salida. El codificador 
debe seguir el mismo procedimiento cuando la imagen reconstruida es usada para predecir otras 
imágenes. El proceso de reconstrucción en el codificador se llama “decodificación local”. 
 
Es importante notar que el sistema MPEG es altamente asimétrico. Los decodificadores son 
relativamente simples, ya que únicamente siguen las direcciones codificadas dentro del flujo de bits. 
Los codificadores, por el contrario, son mucho más complejos que los decodificadores. Entre otras 
cosas, los codificadores deben identificar las áreas de movimiento,determinar los vectores óptimos de 
movimiento, controlar la tasa de bits, controlar el manejo de datos en los buffers, determinar donde 
cambiar la cuantización, decidir cuándo un bloque determinado puede ser simplemente repetido, tomar 
la decisión de cuando utilizar las técnicas “intra” o “inter” de codificación y variar todos estos 
parámetros y decisiones dinámicamente para maximizar la calidad deseada para la tasa de transmisión 
requerida. 
 
En las figuras 1.9 y 1.10 se muestran respectivamente el codificador y decodificador típicos de MPEG . 
 
 
 
 
 
Figura 1.9. Codificador típico MPEG [29]. 
 
Conceptos Generales 15
 
 
 
Figura 1.10. Decodificador típico MPEG [29]. 
 
1.3.1.2 Sintaxis de video MPEG-1 [28] 
A continuación se describe la sintaxis de las seis capas del flujo de bits MPEG-1: secuencia de video, 
grupo de imágenes, imágenes, rebanadas, macrobloques y bloques. 
 
La figura 1.11 muestra una perspectiva general de las seis capas en secuencias de video MPEG-1. La 
capa de sistema, no mostrada en la figura 1.11, provee una envoltura a la capa de secuencia de video. 
Entre otras cosas, la capa de sistema sincroniza y multiplexa los flujos de bits de audio y video en un 
solo flujo de datos. 
 
 
Figura 1.11. Capas de un flujo de video. 
Conceptos Generales 16
 
Una secuencia de video siempre comienza con un encabezado de secuencia. El encabezado de 
secuencia es seguido por uno o más grupos de imágenes (GOP) y termina con un código de fin de 
secuencia. Adicionalmente, los encabezados de secuencia pueden aparecer dentro de la secuencia de 
video. Una de las razones posibles para incluir encabezados de secuencia extras es para ayudar en la 
reproducción aleatoria o en la edición de video. 
Un grupo de imágenes siempre empieza con un encabezado de grupo de imágenes y es seguido por una 
o más imágenes. 
Cada imagen en el grupo de imágenes tiene un encabezado de imagen seguido por una o más 
rebanadas. A su vez, cada rebanada esta compuesta por un encabezado de rebanada y uno o más 
macrobloques. La primera rebanada comienza en la esquina superior izquierda de una imagen y la 
última rebanada (posiblemente la misma) termina en la esquina inferior derecha. 
Cada macrobloque está compuesto de un encabezado de macrobloque, el cual contiene información 
acerca de cuales bloques DCT están codificados. Aunque en la figura 1.11 se muestran los seis bloques, 
en la práctica algunos de los bloques pueden no estar codificados. 
Los bloques DCT como ya vimos pueden codificarse de manera “inter” o “intra”. Si un bloque es intra-
codificado, la diferencia entre el coeficiente de DC el valor anterior es codificado primero. Los 
coeficientes de AC son codificados después, utilizando códigos de longitud variable (VLC). Si el 
bloque es inter-codificado, los coeficientes de DC y AC son codificados de la misma manera utilizando 
los VLC. 
 
Las capas de sistema y de video MPEG contienen patrones únicos de 32 bits llamados códigos de 
comienzo o start codes. Estos códigos, como su nombre lo indican, comienzan ciertos segmentos de 
alto nivel del flujo de bits. Todos los códigos de comienzo tienen un prefijo de tres bytes con 23 bits 
ceros seguidos de un bit 1. El último byte (conocido como valor del código de comienzo o start code 
value en MPEG-2) identifica a un código de comienzo en particular. Los códigos de comienzo para la 
capa de video van del 00000100 al 000001B8 en hexadecimal. El encabezado de secuencia, 
encabezado de grupo de imágenes, encabezado de imagen y encabezado de rebanada comienzan 
precisamente con un código de comienzo. Dichos códigos son alineados, es decir que comienzan 
cuando comienza un byte, agregando tantos ceros como sea necesario para lograr la alineación. En la 
siguiente tabla se muestran los códigos de comienzo para el video MPEG. 
 
Nombre del código hexadecimal binario 
extension start code 000001B5 00000000 00000000 00000001 10110101 
group start code 000001B8 00000000 00000000 00000001 10111000 
picture start code 00000100 00000000 00000000 00000001 00000000 
Reserved 000001B0 00000000 00000000 00000001 10110000 
Reserved 000001B1 00000000 00000000 00000001 10110001 
Reserved 000001B6 00000000 00000000 00000001 10110110 
sequence end code 000001B7 00000000 00000000 00000001 10110111 
sequence error code 000001B4 00000000 00000000 00000001 10110100 
sequence header code 000001B3 00000000 00000000 00000001 10110011 
slice start code 1 00000101 00000000 00000000 00000001 00000001 
… … … 
slice start code 175 000001AF 00000000 00000000 00000001 10101111 
user data start code 000001B2 00000000 00000000 00000001 10110010 
Tabla 1.1. Códigos de comienzo de video MPEG. 
 
Cada encabezado contiene además del código de comienzo, datos necesarios para la capa en cuestión. 
Por ejemplo, para la capa de imagen, el encabezado contiene los datos que identifican el tipo de imagen 
Conceptos Generales 17
 
 
(I, P, B o D), si el vector de movimiento tiene una escala de 1 píxel o medio píxel, si la referencia para 
el vector de movimiento es pasada o futura, etc. 
 
1.3.1.3 MPEG-2 [28] 
MPEG-2 es una extensión y mejora del estándar MPEG-1, desarrollado por el mismo comité de la ISO. 
La capa de video MEPG-2 permite tasas de datos de hasta 100 Mbit/s, soporta formatos de video 
entrelazado e incluye soporte para Televisión de Alta Definición o HDTV entre otras mejoras. El video 
MPEG-2 puede ser utilizado para transmisiones digitales de video vía satélite, por cable y otros canales 
de transmisión. 
MPEG-2 provee servicios multimedia interactivos tales como: 
• Acceso aleatorio para televisión interactiva. 
• Modos de operación que proveen funcionalidades como la de un reproductor de video casete, tales 
como avance rápido, reversa, cámara lenta, etc. 
• Múltiples flujos de audio y video (estereo, multi-lenguajes). 
 
A diferencia de MPEG-1 que está diseñado para el almacenamiento de video, MPEG-2 contiene un 
control de errores más robusto para poder ser transmitido sobre canales con pérdidas. El flujo de 
transporte utiliza paquetes de longitud fija de 188 bytes. 
Originalmente, la especificación de video MPEG-2 tenía la intención de soportar video entrelazado a la 
resolución de televisión estándar en rangos de 4 a 9 Mbits/s. Sin embargo, el alcance de MPEG-2 fue 
ampliado considerablemente para incluir resoluciones y tasas de bits más altas, así como codificación 
jerárquica. Entre otras nuevas utilidades incluidas en MPEG-2 se encuentra el soporte de diferentes 
modos de muestreo de crominancias. El modo estándar de muestreo utilizado en JPEG, MPEG-1 y 
H.261 es llamado (4:2:0), en donde las muestras de las componentes de crominancia son la mitad de las 
muestras de luminancia tanto en la dirección vertical como en la horizontal. Un muestreo (4:2:2) 
produce componentes de crominancia con la misma resolución vertical y la mitad de la resolución 
horizontal que las componentes de luminancia. Incluso soporta un muestreo (4:4:4) que provee 
idénticas resoluciones para crominancias y luminancias. 
 
Otra característica importante de MPEG-2 es la escalabilidad. Los modos escalables permiten que la 
información de video pueda ser codificada en dos o más capas. El estándar define cuatro modos de 
codificación por capas: 
• La escalabilidad espacial permite a cada imagen ser codificada con un rango de resoluciones que 
puede ir hasta la resolución máxima. Esta característica permite, por ejemplo, ser utilizado para 
transmitir video para terminales de televisión estándar así como de HDTV simultáneamente. 
• La partición de datos permite que los datos codificados puedan ser separados en flujos de alta y 
baja prioridad. 
• La escalabilidad de la relación señal a ruido (SNR) permite a las imágenes ser codificadas con una 
calidad base. Las capas adicionales pueden proveer de la información complementaria para 
decodificar la imagen con la máxima calidad. 
• La escalabilidad temporal permite a las secuencias ser codificadas a diferentes tasas de cuadrospor 
segundo. La capa base puede contener la secuencia en una tasa de cuadros baja y oras capas pueden 
contener los cuadros faltantes para obtener una calidad máxima. 
 
Al igual que MPEG-1, el estándar de video MPEG-2 no especifica el proceso de codificación de video, 
sino únicamente la sintaxis del flujo de bits y la semántica de decodificación. 
 
 
Conceptos Generales 18
 
1.3.1.4 MPEG-4 y 7 
Puede parecer sorprendente que no exista MPEG-3. MPEG-3 fue inicialmente planeado para ser un 
estándar para video de alta calidad en tasas altas de datos (en particular para HDTV). Sin embargo, 
durante el trabajo del comité notaron que los nuevos algoritmos de compresión y los esquemas 
emergentes de MPEG-2 podían ser apropiados para soportar los escenarios de la HDTV. 
MPEG-4 tiene un enfoque diferente y su motivo es que las aplicaciones multimedia han sido cada vez 
más complejas. La introducción de la realidad virtual requiere una codificación eficiente y modelos 
sintéticos. Incluso, es previsible que las aplicaciones futuras puedan contener múltiples vistas de 
escenas y gráficas. 
A pesar de que el objetivo original del comité MPEG-4 fue desarrollar un estándar de codificación para 
aplicaciones con tasas muy bajas de bits, la atención cambió a una codificación orientada a objetos. Por 
ejemplo, si consideramos un carro que circula frente al horizonte de una ciudad, en lugar de codificar 
cada imagen como un todo, el carro en el primer plano y el fondo estacionario puede ser codificado 
independientemente con diferentes métodos y parámetros de compresión. El audio también puede ser 
identificado como diferentes objetos, de tal manera que podemos tener audio como fondo, música y 
diálogos. De la misma manera, el texto que aparece en un video, como es el caso de los subtítulos, 
puede ser codificado en ASCII y desplegado con un algoritmo de despliegue parametrizado por parte 
del receptor. 
 
Recientemente la ISO ha decidido establecer un grupo de trabajo sobre meta-datos, para acompañar un 
flujo de audio y video en pistas diferentes. Este es el alcance de MPEG-7. La idea de este trabajo es el 
hecho de que existe un conocimiento considerable del contenido semántico de una pista de video o 
audio al momento de producirse. Este conocimiento es perdido cuando son almacenadas o transmitidas 
dichas pistas de audio y video. Algunos ejemplos incluyen el nombre de los autores, actores y 
directores de una película, los nombres de los políticos o celebridades y el tiempo exacto de grabación 
de un documental o entrevista, etc. Para un acceso futuro de los materiales digitalizados, sería muy 
deseable almacenar estos datos junto con el audio y el video. 
Si asumimos que los meta-datos son almacenados junto con la información audiovisual, podemos 
construir motores de búsqueda de piezas específicas de audio y video en archivos grandes de 
información audiovisual y poder ser utilizado, por ejemplo, por los productores de documentales o 
noticieros para reutilizar secuencias en nuevas producciones. 
 
1.3.2 Otros estándares de compresión [30] 
 
H.120 fue el primer estándar de codificación de video desarrollado por al ITU-T en 1984 en su primera 
versión y en 1988 en su segunda versión [31]. El estándar tenía como objetivo aplicaciones para 
videoconferencias en rangos de 1.5 Mbits/s para NTSC y 2 Mbits/s para PAL. El estándar consta de 3 
partes. La parte 1 para regiones 625/50 (PAL), la parte 3 para 525/60 (NTSC) y la parte 2 para uso 
internacional. Las partes 1 y 2 utilizan DPCM, mientras la parte 3 utiliza compensación de movimiento 
y predicción hacia atrás. Este estándar nunca tuvo éxito comercial. 
 
La recomendación H.261 propuesta en 1991 por la ITU-T (también conocida como el estándar “p x 
64”) [32] tuvo su origen gracias al desarrollo de las Redes de Servicios Integrados o ISDN. Este 
estándar describe los métodos de codificación y decodificación de video para servicios audiovisual en 
rangos de p x 64 bits/s, donde p puede tomar valores entre 1 y 30. Para video-telefonía, son suficientes 
valores de 1 y 2 para p, pero videoconferencias de mejor calidad necesitan al menos un valor de p = 6. 
Está basado, al igual que MPEG, en la DCT aplicada a bloques de 8 x 8 y utiliza compensación de 
movimiento. Introdujo las técnicas de cambio de modos SKIP/INTER/INTRA a nivel macrobloque, 
Conceptos Generales 19
 
 
escaneo en zigzag, cuantización escalar y codificación de entropía VLC utilizada en la mayoría de los 
estándares de codificación de video. 
De manera paralela a las actividades de estandarización de la CCITT, la CCIR comenzó la 
estandarización para codificación de video para señales con calidad de TV. La recomendación CCIR-
721 [33] surgió en 1990. Su principal objetivo fue la transmisión de las señales de TV digital 
codificada para aplicaciones en tasas cerca de los 140 Mbits/s. La recomendación utilizó una simple 
forma de codificación inter-frame DPCM para permitir una implementación poco compleja y un alto 
grado de acceso aleatorio. 
 
La recomendación CCIR-723 [34] surgió en 1992. Su principal objetivo fue el mismo que CCIR-721 
pero para un rango de tasas de 34-5 Mbits/s. La recomendación utiliza de manera híbrida MC-
DPCM/DCT para modo intra-frame y dos modos inter-frames (con y sin compensación de 
movimiento, MC). Ambas recomendaciones, CCIR-721 y CCIR-723, no son generales. A diferencia de 
otros estándares, especifican de manera completa tanto el codificador como el decodificador. 
 
Otro estándar de codificación de video es el H.263 de la ITU-T [35]. Fue diseñado para una 
comunicación a bajas tasas de bits. Su algoritmo de codificación es similar al utilizado por H.261 con 
algunas mejoras en su desempeño y recuperación de errores. Entre las diferencias de H.263 con H.261 
es que utiliza una precisión de medio píxel para la compensación de movimiento, y una predicción 
hacia delante y hacia atrás similar a los cuadros “P” y “B” de MPEG. 
 
1.4 Esquemas de estimación de movimiento 
 
Actualmente los estudios enfocados al análisis del movimiento de imágenes están motivados por 
diferentes aplicaciones [36]. Algunos ejemplos son: 
• Televisión. Para codificar imágenes de video con compensación de movimiento. Al estimar 
movimiento se puede obtener una imagen con mayor correlación que la imagen sucesiva y así poder 
aprovecharlo para lograr una mayor compresión. 
• Robots móviles. Gracias a la posibilidad de segmentar los objetos al detectar su movimiento en una 
escena, se puede proveer a los robots de la capacidad de navegar autónomamente en ambientes 
parcial o totalmente desconocidos o ambientes dinámicos. 
• Aplicaciones militares. La estimación y detección de movimiento pueden ser utilizadas para el 
seguimiento de objetivos y navegación autónoma de vehículos. 
• Imágenes biomédicas. Se pueden aprovechar las técnicas de detección de movimiento para realizar 
un análisis de los órganos internos como el corazón. 
• Monitoreo de espacios. Puede tener aplicaciones en la detección de intrusos, revisión de tráfico, etc. 
• Realidad virtual e interfaces. Se pueden aplicar las técnicas de estimación de movimiento para la 
interpretación de movimientos faciales en la interpretación de interfaces hombre-máquina. 
• Deportes. Gracias al estudio del movimiento del cuerpo humano, los deportistas pueden analizar y 
mejorar sus movimientos para lograr sus objetivos. 
 
El movimiento en la imagen, es decir, el movimiento sobre la superficie de proyección del sistema de 
visión, se debe al movimiento relativo entre el sistema de visión y la escena. A la distribución de los 
vectores de velocidad aparente asociados a cada punto de la imagen se le denomina flujo óptico [37]. 
La estimación de movimiento es la operación mediante la cual se estima dicho flujo. Muchos esquemas 
de estimación de movimiento suponen que la imagen, representada con intensidades de luminosidad, se 
mueve de manera continua en forma traslacional y que las condiciones de iluminación permanecen 
constantes.Si esto fuera cierto, el detectar el movimiento local en una imagen resultaría trivial, 
Conceptos Generales 20
bastando restar punto a punto la distribución de las intensidades de la imagen en dos instantes de 
tiempo. Por este medio, solamente en las regiones cercanas a las discontinuidades de la distribución de 
intensidades que se han movido se encontrarán valores distintos a cero. 
Adicionalmente, se han detectado algunos problemas que influyen en la estimación de movimiento. El 
problema de apertura [38] surge del hecho de que el movimiento aparente que puede medirse para 
cualquier porción local de una estructura fuertemente orientada (por ejemplo un borde), es únicamente 
la componente ortogonal a la orientación local. Si se coloca una ventana sobre una línea recta, la 
componente del desplazamiento paralelo no puede ser detectado. Otro inconveniente conocido es el 
problema de oclusión que sucede cuando un objeto que cubre a otro se desplaza dejando al descubierto 
al objeto ocultado que puede a su vez estar en movimiento. En este caso sucede una discontinuidad en 
el campo de la distribución de las intensidades de luminosidad. 
 
Las técnicas de estimación de movimiento pueden clasificarse en tres grupos: los que se basan en la 
solución de correspondencia (block-matching), los que se basan en el cálculo del gradiente y los que se 
basan en una estimación en el dominio de la frecuencia. En las siguientes secciones se describen cada 
uno de estos grupos. 
 
1.4.1 Block-Matching 
 
Los algoritmos basados en correspondencia conocidos como block-matching se han vuelto muy 
populares debido a su simplicidad, robustez y fácil implementación. El interés en este método fue 
iniciado por Jain y Jain en 1981 [39]. Para el caso de la codificación de video, más que realizar un 
análisis del movimiento, detección de objetos u otras aplicaciones posibles, lo que nos interesa es poder 
aumentar la correlación entre dos imágenes sucesivas y de esta manera mejorar la compresión, lo cual 
es logrado eficazmente con los métodos basados en correspondencia. La idea es poder representar una 
imagen de la secuencia con base en la imagen previa y el movimiento ocurrido entre ambas. Como en 
la práctica esto no siempre es posible, a la codificación se agrega la diferencia entre la imagen actual y 
la imagen previa con compensación de movimiento. 
 
En la estimación de movimiento por block-matching la imagen a ser codificada es dividida en bloques 
de tamaño m x n asumiendo que todos los píxeles dentro del bloque tienen el mismo vector de 
desplazamiento. El vector de movimiento correspondiente a cada bloque es estimado realizando una 
búsqueda a través de un bloque mayor (ventana de búsqueda), con centro en la misma posición en el 
cuadro anterior como se muestra en la figura 1.12. 
 
Figura 1.12. Block-Matching. 
 
 
Conceptos Generales 21
 
 
El modelo de movimiento traslacional de bloques s, puede ser simplificado de la siguiente manera: 
 
s(n1, n2 , k) = s (n1+d1, n2+d2, k+1) (1.4) 
 
En dónde n1,n2 es la posición del bloque en la imagen, k es el índice de la imagen en la secuencia y 
d1,d2 son las componentes del vector de desplazamiento de dicho bloque o en otras palabras, el vector 
de movimiento. 
 
Un parámetro importante a considerar en estos métodos es el tamaño del bloque. Por un lado, si 
elegimos un bloque pequeño, éste se adecuará más a los límites de los objetos y nos dará una buena 
aproximación del movimiento real, aunque no sería práctico debido a que aumentaría la cantidad de 
información de los vectores de movimiento. Por otro lado si elegimos bloques muy grandes, 
seguramente cada bloque abarcaría más de un objeto posiblemente con movimientos diferentes lo cual 
aumentaría el error entre la imagen actual y la imagen previa con compensación de movimiento. 
 
Otro parámetro involucrado es el tamaño de la ventana de búsqueda. El elegir una ventana pequeña 
limita las posibles posiciones a las que se puede desplazar un bloque, mientras que elegir una ventana 
de búsqueda más grande aumenta el procesamiento necesario para localizar la mejor posición 
correspondiente del bloque. 
 
Entre los métodos de estimación por block-matching varían, además del tamaño del bloque y de la 
ventana de búsqueda, dos cosas: el procedimiento de búsqueda y el criterio de error o de coincidencia 
(mínima diferencia absoluta, máxima correlación de cruz, mínimo error cuadrático, etc.). 
 
Los procedimientos de búsqueda toman un bloque de la imagen previa del cual se desea conocer su 
vector de movimiento y se prueba sobre diferentes posiciones dentro de la ventana de búsqueda en la 
imagen actual para localizar la que tenga la mejor correspondencia de acuerdo a algún criterio de 
coincidencia. Estos procedimientos van desde la búsqueda exhaustiva en el cual todas las posiciones 
posibles son evaluadas, hasta algunos que siguen un algoritmo más eficiente como son la búsqueda 
logarítmica [39], la búsqueda por los tres pasos [40], la búsqueda diamante [41] y la búsqueda en Cruz 
[42]. 
 
Los principales criterios de error o de coincidencia son: 
• El criterio de mínimo error cuadrático (MSE) 
Se evalúa una función de la siguiente forma: 
 
[ ]∑
∈
+++−=
Bnn
kdndnsknns
NN
ddMSE
),(
2
221121
21
21
21
)1,,(),,(1),( (1.5) 
donde B denota un bloque de N1 x N2, para un conjunto de vectores candidatos (d1,d2). 
 
• El criterio de mínima diferencia absoluta (MAD) 
De forma similar, se evalúa una función de la siguiente forma: 
∑
∈
+++−=
Bnn
kdndnsknns
NN
ddMAD
),(
221121
21
21
21
)1,,(),,(1),( (1.6) 
 
• El criterio del conteo de máxima concordancia de píxeles coincidentes (MPC) 
En esta alternativa, cada píxel dentro del bloque B es clasificado como un píxel concordante o 
discordante de acuerdo a: 
Conceptos Generales 22
=),;,( 2121 ddnnT {1 si tkdndnsknns ≤+++− )1,,(),,( 221121 ; 0 si cualquier otro caso} (1.7) 
 
donde t es un umbral predeterminado. Entonces, el número de píxeles concordantes dentro del bloque 
está dado por: 
∑
∈
=
Bnn
ddnnTddMPC
),(
212121
21
),;,(),( (1.8) 
 
1.4.2 Estimación basada en el gradiente 
 
Los métodos basados en el gradiente son ampliamente utilizados en la estimación de movimiento. 
Estos métodos asumen que la intensidad de la imagen se conserva a través de una trayectoria 
espaciotemporal durante el movimiento. La formalización clásica dada por Horn y Schunck [43] es la 
siguiente. Sean las variaciones espaciotemporales de intensidades representadas por una función 
derivable l(r,t) y sea la proyección de la trayectoria de movimiento s(t) en el instante t de un punto que 
se mueve en el espacio. Si asumimos que la intensidad registrada para el punto del objeto físico no 
cambia a medida que el objeto se mueve, entonces la composición l(r,t) en r = s(t) es constante. Así, 
derivando respecto a t se obtiene: 
 
tllv −=∇⋅ (1.9) 
 
donde el vector es el gradiente espacial de l, es la derivada parcial de l respecto a t y v = (vl∇ tl x,vy) es 
el vector de velocidad asociado a la proyección del punto en el espacio, es decir, la derivada de la 
trayectoria s(t). 
 
Esta ecuación es referida como la ecuación del gradiente y constituye una restricción local del 
movimiento. La proyección (vn) de v sobre la dirección del gradiente se obtiene fácilmente de (1.9). 
 
2l
llv tn
∇
∇
−= (1.10) 
 
Así, conocidas las derivadas espacial y temporal de la imagen, la ecuación del gradiente permite 
calcular la componente de velocidad en la dirección del gradiente, es decir, la componente ortogonal a 
la orientación de una estructura localmente unidimensional tal como un borde o una línea. 
 
El método basado en el gradiente más conocido es el de Horn- Schunck [43]. Su método impuso una