PAIDEIA XXI
Vol. 4, Nº 5, Lima, agosto 2014, pp. 202-212
En este artículo se propone una técnica para transmisión progresiva de
imágenes. Esta técnica está basada en el modelo piramidal de Burt y Adel-
son, haciendo uso de la codicación por Cuantización Vectorial en imágenes
representadas por una estructura piramidal, denominada pirámide de imágenes
diferencia, que son exactamente las imágenes a transmitirse progresivamente
del nivel más alto al nivel más bajo, para ir formando las denominadas imáge-
nes media. La técnica es comparada a otros métodos conocidos en la literatura
en términos de relación señal-ruido de pico, por su calidad subjetiva y por el
esfuerzo computacional asociado.
Palabras clave: Cuantización Vectorial, Técnica Piramidal, codicación de
imágenes.
In this paper is proposed a technique for progressive images transmission.
This technique is based on the pyramidal model of Burt and Adelson, making use
of the codication by Vectorial Quantization in images represented by a pyrami-
dal structure, designated images pyramid difference, that they are exactly the
images that they will be transmitted progressively of the highest level at bottom
most level, to go forming the designated mean images. The technique is compa-
red to other methods known in the literature in terms of relationship sign-peak
noise, for your subjective quality and for the effort computational associate.
Keywords: Vectorial Quantization, pyramid technique, Image coding.
Resumen
Abstract
TÉCNICA DE CODIFICACIÓN PIRAMIDAL
UTILIZANDO LA CUANTIZACIÓN VECTORIAL PARA
LA TRANSMISIÓN PROGRESIVA DE IMÁGENES
Pedro Freddy Huamaní Navarrete
Técnica de codicación piramidal utilizando la cuantización vectorial
203
PAIDEIA XXI
INTRODUCCIÓN
Los avances de la tecnología digital
en la década pasada, principalmente
en la transmisión y almacenamiento
de datos, ha traído muchas aplicacio-
nes al procesamiento digital de imáge-
nes. Así tenemos: transmisión de imá-
genes en redes de distribución de TV,
monitoreo remoto vía satélite, comu-
nicaciones militares vía radar o sonar,
teleconferencia, transmisión de fax,
almacenamiento de documentos edu-
cacionales, de negocios, de imágenes
médicas usadas en sistemas de moni-
toreo de pacientes, mapas climáticos,
etc. (Jain, 1989).
En todas estas aplicaciones, el
principal obstáculo radica en la enor-
me cantidad de datos requeridos para
representar digitalmente la imagen.
Por lo tanto, el uso frecuente de imá-
genes digitales implica altos costos
de transmisión y/o almacenamiento,
sumándose a esto las limitaciones de
memoria, canal y velocidad. Es así que
se torna muy necesario el uso de téc-
nicas de compresión para la reducción
de la tasa de bits, minimizando así el
número de bits requeridos para su re-
presentación.
El enfoque principal de este traba-
jo es transmitir progresivamente imá-
genes comprimidas. Para esto, una
imagen de menor resolución es trans-
mitida, para luego mejorar progresiva-
mente esta imagen con transmisiones
complementarias. De esta manera, la
transmisión progresiva de imágenes
facilita al usuario ver la imagen y to-
mar una decisión sobre si es necesario
o no toda su denición. Todo esto, en
un corto tiempo. Este trabajo utiliza
una Técnica de Codicación Piramidal
(Burt, & Adelson, 1983), conformado
por pirámides de medias y diferencias.
La pirámide de medias es formada
por sucesivas medias sobre bloques
de 2x2 pixels iniciando de la imagen
original, y la pirámide de diferencia se
obtiene con la diferencia de cada ima-
gen media menos una imagen enreda-
da, previamente formada.
Finalmente, la Cuantización Vec-
torial (V.Q) es la utilizada para com-
primir o codicar las imágenes dife-
rencias de cada nivel de la pirámide,
iniciándose en la imagen de media de
menor dimensión y nalizando en la
de dimensión total.
DESARROLLO DEL TRABAJO
Esta técnica utilizada representa
una imagen en diferentes dimensiones
y formando una pirámide de imágenes
de dimensiones cada vez menores. La
Figura 1 muestra el diagrama de blo-
ques del análisis de esta técnica.
Pedro Freddy Huamaní Navarrete
204
PAIDEIA XXI
PIRÁMIDE DE IMÁGENES MEDIAS
Esta pirámide se forma de una me-
dia aritmética sobre cada uno de los
bloques de 2x2 pixels no superpues-
tos, de una secuencia de imágenes de
resoluciones cada vez menores, donde
cada nueva imagen ocupará siempre
un cuarto de la dimensión de la ima-
gen de la cual fue obtenida.
PIRÁMIDE DE IMÁGENES
ENREDADAS
La operación de enredamiento es
aplicada para cada nivel de la pirámi-
de de imágenes media, partiendo de
la imagen original (considerada como
“la primera imagen media”). Esta ope-
ración consiste en hacer una decima-
ción de una imagen media, sin elimi-
nar ninguna información de línea y
columna. La decimación es primero
realizada en las líneas y después en
las columnas, de forma a reducir a un
cuarto la dimensión de la imagen deci-
mada. Como la operación es realizada
en cada nivel de la pirámide de imáge-
nes media, se tendrá como consecuen-
cia la creación de una nueva pirámide
denominada de enredamiento, la cual
contribuirá al cálculo de la pirámide
de imágenes diferencia.
PIRÁMIDE DE IMÁGENES
DIFERENCIA
Se consigue con la diferencia entre
la pirámide de imágenes media con
la pirámide de imágenes enredadas.
Por lo tanto, esta diferencia recibe el
nombre de Pirámide de Imágenes de
Errores, la cual será codicada más
adelante.
Los resultados por cada nivel de
esta pirámide corresponden a cuatro
imágenes diferencia con la aparien-
cia de haber sido ltradas por un l-
tro pasa-alto (Jain, 1989). Estas cua-
tro imágenes también presentan una
propiedad de dependencia lineal; por
tanto, solo se necesita codicar tres
sub-imágenes diferencia, porque la
cuarta surge de la combinación de las
otras tres. De esta manera se mejora
la compresión en relación a otros mé-
todos (Garrido, 989)
Figura 1. Diagrama de Bloques del Análisis
Técnica de codicación piramidal utilizando la cuantización vectorial
205
PAIDEIA XXI
RECONSTRUCCIÓN DE LA PIRÁMI-
DE DE IMÁGENES MEDIA
Se realiza a partir de la diferencia
entre las imágenes diferencia del últi-
mo nivel de la pirámide con la imagen
de media de menor dimensión. Segui-
damente, se realiza la operación de
CODIFICACIÓN POR CUANTIZA-
CIÓN VECTORIAL EN LA ESTRUC-
TURA PIRAMIDAL
Esta sección trata del método de co-
dicación por Cuantización Vectorial
(V.Q), aplicado a la pirámide de imá-
genes diferencia. Así, sea una imagen
dividida en bloques de p x p pixels, un
V.Q consiste en encontrar un conjunto
jo de vectores (denominado Dicciona-
rio de Códigos) que representen todos
los bloques de esta imagen. El bloque
será codicado escogiendo el vector
del diccionario que mejor se aproxime,
teniendo como base de medida la Dis-
tancia Euclidiana, la cual es mostrada
en la siguiente ecuación [11],
d(x, y) X Y
i i
i 0
2
= −
=
= −
∑
i p p* 1
(01)
des-enredamiento de imagen desde el
último nivel hacia el primer nivel, re-
construyendo nalmente la imagen de
tamaño original.
La Figura 2 muestra el diagrama de
bloques de la síntesis o reconstrucción
de esta técnica.
Donde:
X indica el vector de entrada
Y el vector-código perteneciente al dic-
cionario.
De esta manera, la V.Q es aplica-
da a cada nivel de la pirámide, reali-
zándose así una codicación basada
en tres diccionarios diferentes por
nivel, cada uno de estos asociado a
cada imagen diferencia de determina-
do nivel. Solo las imágenes diferencia
son codicadas por poseer gran pro-
porción de pixels con niveles de gris
próximos a cero, correspondientes
a las regiones de baja frecuencia de
la imagen original (González, Woods
& Eddins, 2004). En la Figura 3, se
muestra el diagrama de bloques bási-
co de un Cuantizador Vectorial.
Figura 2. Diagrama de Bloques de la Síntesis
Pedro Freddy Huamaní Navarrete
206
PAIDEIA XXI
PROYECTO DEL DICCIONARIO
Existen diversos algoritmos iterati-
vos que, dado el criterio de distorsión,
otorgan un diccionario óptimo. Como
datos de entrada, estos algoritmos ne-
cesitan el tamaño del diccionario (N
niveles) y el tamaño del vector (pxp).
Otro dato importante es el dicciona-
rio inicial que puede, por ejemplo, ser
generado con bloques aleatoriamente
escogidos de un grupo de imágenes
diferentes de la que se desea codicar
(Gersho & Gray, 1992). Entre algunos
algoritmos iterativos generalmente
utilizados, encontramos: el algoritmo
LBG y el llamado “Nearest Neighbor”
o vecino más próximo (González, &
Woods, 1996), que es signicativa-
mente más rápido que el primero pero
en consecuencia presenta mayor de-
gradación (Garrido, 1989).
Para la formación de los dicciona-
rios, se escogió el algoritmo LBG (Gon-
zález, & Woods, 1996), que toma como
datos de entrada:
1. La secuencia de entrenamiento
formada, en este caso, por cuatro
imágenes diferentes de aquellas
que serán codicadas.
2. El tamaño del diccionario.
3. El diccionario inicial generado a
partir de bloques aleatorios dentro
del margen dinámico de la imagen.
4. El umbral de distorsión, a ser de-
nido.
Los vectores de la secuencia de
entrenamiento son mapeados en los
vectores-código, según el criterio del
menor error cuadrático. Si el error
cuadrático medio de todos los vectores
fuera menor que el umbral de distor-
sión, se llega al diccionario nal. Caso
contrario, se sustituye cada vector-
código por el centroide de los vectores
que en él se mapearán.
CUANTIZACIÓN VECTORIAL (VQ)
EN LAS IMÁGENES DIFERENCIA
La codicación por VQ es espacial
y realizada directamente sobre cada
Figura 3. Esquema Básico de la Codicación Vectorial
Técnica de codicación piramidal utilizando la cuantización vectorial
207
PAIDEIA XXI
una de las imágenes diferencia, codi-
cando del nivel más alto (imagen de
menor dimensión) al nivel más bajo.
a) Codicación del Tercer Nivel
La última imagen de media, al igual
que las otras, tienen las mismas ca-
racterísticas de la imagen original. Por
tanto, cada uno de sus pixels es un
número real positivo que se encuentra
dentro de la franja dinámica de imáge-
nes monocromáticas con 256 niveles
de gris (0 hasta 255).
En este nivel, son dos los tipos de
codicación a utilizar. La primera hace
uso de la VQ para el grupo de imáge-
nes diferencia, dividiendo en bloques
de 2x2 pixels cada imagen; y, la se-
gunda, utiliza una codicación pixel a
pixel.
Durante la codicación por VQ sur-
ge un problema –como es de esperar,
aparecen errores, los cuales se propa-
garan conforme se avanza en dimen-
sión durante la reconstrucción–. Por
lo tanto, estos errores eventualmente
pueden replicarse creando un efecto
de bloques en la imagen original. Para
minimizar este problema, se optó por
codicar estas imágenes diferencia con
un Cuantizador Vectorial de dos Niveles
Jerárquicos, donde el primer nivel co-
dica directamente las imágenes dife-
rencia y el segundo codica los errores
obtenidos en la primera codicación.
Cuantizador Vectorial de Dos Etapas
Este modelo codica la primera
etapa con un cuantizador vectorial di-
recto q (.), y un diccionario de códigos
“A”, donde el vector de entrada “x” es
cuantizado. Luego, un segundo cuan-
tizador vectorial q’ (.), con otro diccio-
nario de códigos “ A’ “, opera sobre el
vector diferencia entre el vector origi-
nal y la salida cuantizada de la prime-
ra etapa (Gersho & Gray, 1992).
Realizada la codicación, se ob-
serva la presencia de tenuidad así
como información de bordes en cada
imagen, lo que obliga a la división del
diccionario en dos grupos. Para su
construcción, se realizaron entrena-
mientos de bloques de 2x2 pixel con
imágenes tenues y de bordes, tomán-
dose en cuenta la separación de los
bloques pertenecientes a la tenuidad
(denominados inactivos) y los bloques
pertenecientes a los bordes (denomi-
nados activos), tal como se muestra a
continuación:
Si: Imagen
∈ ±
Umbral → Bloque
Inactivo
Caso Contrario → Bloque Activo
Donde:
Umbral, corresponde a un valor dife-
rente para cada nivel de la pirámide
de imágenes diferencia. La selección
de este valor está basada en previa ex-
periencia.
b) Codicación del Segundo Nivel
En este nivel, la codicación tam-
bién se lleva a cabo solo para tres
imágenes diferencias. Se utilizan pa-
labras-códigos con 4 elementos cada
una, ya que estas imágenes presen-
tan muchos detalles que pueden no
ser tomados en cuenta si las codica-
mos con vectores de más elementos.
Al igual que en el nivel anterior, se
Pedro Freddy Huamaní Navarrete
208
PAIDEIA XXI
observó enorme cantidad de regiones
tenues y con bordes; por esa misma
razón, se optó por una nueva partición
del diccionario en dos, para codicar
independientemente la parte tenue y
de borde, y teniendo en cuenta la ex-
presión de bloques activos e inactivos.
c) Codicación del Primer Nivel
Para este nivel, se aumenta el nú-
mero de elementos para cada vector-
código, caso contrario la compacta-
ción de datos quedaría reducida. Por
tanto, son tomados 16 elementos para
cada vector. Nuevamente es utilizada
la técnica de división del diccionario
para la parte tenue y de bordes, por la
enorme cantidad de los mismos.
La Tabla 1 muestra el tamaño del
diccionario para cada nivel, así como
el número de pixels para cada pala-
bra-código.
Niveles Bloques Diccionarios
Tenue y Borde
3er Nivel 2x2 14 242
2do Nivel 2x2 18 238
1er Nivel 4x4 24 488
Tabla 1. Tamaño de Diccionarios
para la VQ
Reconstrucción de la Imagen
Iniciando en la imagen media del
nivel más alto de la pirámide, se se-
lecciona un vector para realizar una
búsqueda en el diccionario de códigos
de la primera etapa, de tal manera a
localizar al que mejor lo represente. Se-
guidamente, es calculado el vector de
error. Una vez codicado, se transmite
el par de índices de las dos etapas, don-
de la tarea del decodicador es generar
la composición de los dos vectores có-
digos correspondientes a estos índices
de cada diccionario de cada etapa.
La reconstrucción se realiza progre-
sivamente, reconstruyendo primero
las imágenes de media por cada nivel
de la pirámide. La Figura 4 muestra
una representación de un ejemplo de
descomposición piramidal.
Figura 4. Representación de un ejem-
plo de descomposición piramidal.
PROCESO DE SIMULACIÓN
Para ejecutar el proceso de simula-
ción, se utilizó el entorno del Software
Matlab, con imágenes en tonos de gris
y típicas en investigaciones que se re-
lacionan con técnicas de compresión
o codicación. A continuación, en la
Figura 5a, se muestra el resultado de
obtener la pirámide de imágenes me-
dia correspondiente a las resoluciones
de 32x32, 64x64, 128x128 y 256x256
pixels. De la misma forma, la Figura
5b muestra el resultado del conjunto
de imágenes enredadas con las reso-
luciones (64x64, 128x128 y 256x256),
y la Figura 5c, la perteneciente a las
imágenes diferencia con las resolucio-
nes (64x64, 128x128 y 256x256).
Técnica de codicación piramidal utilizando la cuantización vectorial
209
PAIDEIA XXI
(a) (b) (c)
Figura 5. Imágenes LENA media,
enredada y diferencia.
RESULTADOS
En esta sección, se muestran los
resultados visuales y numéricos de
la codicación por Cuantización Vec-
torial en la pirámide de imágenes di-
ferencia. Para esta operación, se uti-
lizaron dos grupos de imágenes de
256x256 pixels con 8 bpp. Un primer
grupo de entrenamiento para sinteti-
zar los diccionarios teniendo en cuen-
ta la tenuidad y bordes existente en
cada imagen de cada nivel de la pirá-
mide; y un segundo grupo para reali-
zar las pruebas y, por tanto, ajenas al
grupo de entrenamiento.
Para medir la calidad de la ima-
gen reconstruída (análisis objetivo), se
utilizó la relación señal-ruido de pico,
PSNR, denida por (Garrido, 1989):
PSNR
MN j
N
i o
M
= ∗
=
−
=
−∑∑
10 255
1
10
2
2
0
11
log
() x - x
ij ij
dB (02)
Donde:
255 el valor pico de la señal.
X: la imagen original.
x
: la imagen reconstruída.
Ambas imágenes con tamaño de
M x N pixels.
De esta forma, la simulación fue rea-
lizada en el grupo de imágenes ajenas
al entrenamiento, mostrándose los re-
sultados numéricos para cada imagen
media. Ver Tabla 2. De igual forma, los
resultados visuales, pertenecientes a
la imagen LENA, son mostrados en la
Figura 6.
Imágenes Me-
dia
PSNR
(dB)
Bpp
LENA 32 x 32 330.2 7.0
LENA 64 x 64 41.3 3.7
LENA 128 x 128 35.4 2.4
LENA original 31.5 1.0
Tabla 2. Resultados de Simulación
Pedro Freddy Huamaní Navarrete
210
PAIDEIA XXI
CONCLUSIONES
Muchas técnicas requieren opera-
ciones de transformaciones al dominio
de la frecuencia, por lo cual utilizan
mayor tiempo computacional y, por
consiguiente, se tornan más lentos
que el método propuesto en este ar-
tículo.
La construcción de la pirámide de
medias requiere poco esfuerzo compu-
tacional, basado en simples cálculos
de medias aritméticas sobre bloques
de 2x2 pixels no sobrepuestos. Los
cálculos son ejecutados tres veces
consecutivas, originando de esta ma-
nera una pirámide media con cuatro
niveles. La última imagen media con
dimensión más pequeña, no necesita-
rá ser más sub-muestreada. De este
modo, se cuantiza y codica directa-
mente pixel a pixel para posteriormen-
te ser transmitida.
La mayoría de las imágenes natu-
rales tienen alto grado de correlación
entre pixels vecinos. Por tanto, la ma-
yoría de los pixels en las imágenes
diferencia tienden a concentrarse en
valores cerca de cero (próximos del
color negro), o sea con menor energía
(Gornsztejn, 1993). Esto hace que el
conjunto de imágenes diferencia se
asemejen al conjunto de imágenes ob-
tenidas en una codicación por sub-
bandas (Woods & O’neil, 1986).
El grupo de imágenes diferencia
representará las transiciones de la
imagen, a pesar de poseer poca ener-
gía; por lo tanto, son muy importantes
porque determinan la mayor o menor
denición en la imagen reconstruida.
Las operaciones de medias se ase-
mejan al tipo de ltrado de media no
lineal, localizada y espacial, porque
cada bloque de 2x2 pixels es tratado
independientemente sin ser sobre-
Imagen Original Imagen Recuperada
Figura 6. Imagen LENA codicada
Técnica de codicación piramidal utilizando la cuantización vectorial
211
PAIDEIA XXI
puestos a los bloques vecinos. De esta
manera, solo se codican tres imá-
genes diferencia por cada nivel de la
pirámide, porque estas poseen la pro-
piedad de dependencia lineal.
Sin embargo, la codicación con un
único diccionario para las tres imáge-
nes diferencia, por cada nivel de la
pirámide, trae una degradación en la
reconstrucción de la imagen, ya que
los errores se propagan a través de la
pirámide.
Por lo tanto, el uso de tres diccio-
narios diferentes por cada nivel de la
estructura piramidal aumenta la tasa
de compresión, pero mejora notable-
mente el aspecto visual y numérico de
la imagen reconstruida. Así mismo, se
optó por la división en dos de los dic-
cionarios; uno para codicar la parte
tenue y otro para la parte de bordes.
De esta manera, se pudo representar
la enorme cantidad de vectores tenues
en cada imagen diferencia, lo cual fue
posible al seleccionar el tamaño de las
particiones para tenuidad y bordes a
través de la técnica de ensayo y error.
Propuestas Futuras
Organización de los diccionarios
para la operación de búsqueda del
vector más próximo. Esto quiere decir
que se podrá establecer, una búsque-
da por energía, dividiendo el dicciona-
rio en particiones.
Optimización del tamaño de las
particiones en los diccionarios de te-
nuidad y bordes. Es decir, encontrar
una cantidad óptima de vectores, de
tal forma a representar adecuadamen-
te las informaciones de tenuidad y
bordes en la codicación.
Pedro Freddy Huamaní Navarrete
212
PAIDEIA XXI
REFERENCIAS BILIOGRÁFICAS
1 González, R.; Woods, R. & Eddins, S. (2004). “Digital Image processing
using MATLAB”. Editorial Dorling Kindersley.
2.González, R. C. & Woods R. E. (1996). “Tratamiento Digital de Imágenes”.
Addison-Weslley Iberoamericana S.A, U.S.A.
3. Garrido, D. P. (1990). “Laplacian Pyramid Coding Using Scalar and Vec-
tor Quantization”.Rio de Janeiro ICASSP-90 Technical Program Commitee.
4 Burt, P.J. & Adelson, E. H. (1983). “The Laplacian Pyramid as a Compact
Image Code,” Transactions on Communications, vol. 31, pp. 532-540.
5 Woods, J.W. & O’neil, S. D., (1986). “Subband Coding of Images,” Transac-
tions on Communications, vol. 34, pp. 1278-1288.
6 Linde, Y.; Buzo, A. & Gray, R. M. (1980). “An Algorithm for Vector Quantizer
Design,” Transactions on Communications, vol. 28, pp. 84-95, Janeiro.
7 Garrido, D. P. (1989). “Um Sistema de Codicação de Imagem via Dois
Canais,” Dissertação de Mestrado, Departamento de Engenharia Elétrica - PUC-
Rio.
8 Smith, M. J. T. & Eddins, S. L. (1990). “Analysis/Synthesis Techniques for
Subband Image Coding,” IEEE Transactions on Acoustics, Speech and Signal
Processing, vol. 38, no 8, pp. 1446-1456.
9 Jain, A. K. (1989). “Fundamentals of Digital Image Processing,” Englewood
Cliffs, New Jersey: Prentice Hall.
10 Gornsztejn, J. (1993). “Técnicas de Compressão de Imagens por Sub-Ban-
das” Dissertação de Mestrado, Departamento de Engenharia Elétrica - PUC-Rio.
11 Gersho, A. & Gray, R. M. (1992). “Vector Quantization and Signal Com-
pression”, Kluwer Academic Publishers.