PDF de programación - CAPÍTULO 2 ANÁLISIS Y PROCESAMIENTO DE IMÁGENES (REDUCCIÓN Y RECUPERACIÓN DE INFORMACIÓN)

CAPÍTULO 2

ANÁLISIS Y PROCESAMIENTO DE IMÁGENES

(REDUCCIÓN Y RECUPERACIÓN DE INFORMACIÓN)



La importancia de reducir una imagen consiste en agilizar la transmisión de la

información a través de la red así como la recuperación de la información y la comparación

entre las imágenes.



2.1 Reducción de información

Como se mencionó en el Capítulo 1, existen varias técnicas de compresión. Entre

ellas se encuentran los Wavelets, los cuales son funciones matemáticas que toman datos de

diferentes componentes de frecuencia y además estudian cada componente con una

resolución que coincide con su escala. Las ventajas son su capacidad de ser reversibles en

algunas implementaciones [Ruiz, et.al, 2001].

Otro tipo de compresión es el estándar JPEG, el cual es más que un algoritmo para

compresión de imágenes ya que contiene una arquitectura para un grupo de funciones de

compresión de imágenes además de muchas capacidades que permiten que sea útil para un

rango de aplicaciones que se refieren a compresión de imágenes. JPEG está relacionado

con imágenes que contienen dos dimensiones, escala de grises y color. Por la facilidad de

manejar los Quadtrees de acuerdo a las necesidades de cada problema, se decidió elegir

esta técnica para reducir las imágenes en nuestro sistema.





La estructura de un quadtree se emplea en el procesamiento de imágenes digitales y

graficas por computadora para modelar la segmentación espacial de imágenes y superficies.

2.1.1 Quadtrees

2.1.2 Estructura de un quadtree


Los métodos de descomposición espacial se basan en formar modelos a partir de

pequeños bloques, cuyas dimensiones dan la resolución del sólido, por lo tanto son métodos

con gran flexibilidad. Dependiendo de la clase del objeto base o primitiva y la forma de

combinarlo, se emplean diversas técnicas, como las siguientes: [Chacon, 2000]



?? Descomposición de celdas

?? Enumeración espacial

?? Árboles octales



Los árboles octales son el principal ejemplo de la división adaptativa, dentro de la

representación de sólidos en 3-D, pero en este caso utilizaremos objetos en 2-D, así que la

alternativa son los quadtrees [Chacon, 2000].



Los quadtres son una variante de los octrees. Estos árboles se basan en el principio

de descomposición recursiva del espacio. La imagen se descompone en cuatro cuadrantes

de igual

tamaño. Si los cuadrantes no son uniformes, es decir si están parcialmente

ocupados por

la

imagen que se está analizando, éstos se subdividen en cuatro

subcuadrantes. La descomposición se detiene si los cuadrantes uniformes son encontrados

o si los cuadrantes contienen solamente un píxel. [Bow, 1992]



La descomposición recursiva puede representarse en un árbol. En el nivel superior del

árbol, que se le llama raíz, empieza la descomposición. La raíz corresponde a la imagen

binaria completa. Se conecta por medio de aristas a sus cuatro nodos, los cuales

representan de izquierda a derecha los cuadrantes: Noroeste, Noreste, Suroeste y el

Sureste. Si un cuadrante necesita subdivisión, lo representa un nodo terminal u hoja en el

árbol. Al nodo hoja se le llama “negro” cuando el cuadrante asociado es parte completa de

un objeto, o “blanco”, en el caso en que no es parte del objeto, y se indica por medio de un

nodo relleno en el caso de negro y un nodo vacío en el caso de que sea blanco. Los nodos

que no son hojas; es decir, que todavía se subdividen, son los grises. Como podemos ver en

la siguiente imagen binaria de 16 x 16 en (a) y en (b) la representación en árbol y (c) lineal:

[http://www.ece.gatech.edu, 2000].



Píxelapagado(0)

Píxel prendido(1)



Figura 2.1a Ejemplo de una imagen binaria de 8X8 pixeles







Imagen completa



Primer nivel


Segundo nivel


Tercer nivel


Cuarto nivel

Gris

Negro

Blanco



Figura 2.1b Representación del quadtree

g(g(wwg(wwwb)b)wg(g(wbwb)bwg(wbww))g(bwg(bbww)w))



Figura 2.1c En forma lineal

Como hemos visto, en el quadtree, el plano se divide en cuadrantes. Un quadtree

lineal se refiere a un arreglo simple de nodos.

El algoritmo de descomposición de un quadtree trabaja por medio de bloques.

Como en el ejemplo anterior, supongamos que la imagen es de 8 por 8 La función

comienza entonces con un bloque de 8 por 8. Si los pixeles del bloque no son similares, la

función subdivide el bloque en 4 bloques de 4 x 4. La función luego subdivide los bloques

no similares de 4 por 4 en cuatro bloques de 2 por 2, y los bloques de 2 por 2 no similares

se subdividen en cuatro bloques de 1 por 1 y como es lo mínimo, ya no se pueden

subdividir más. Así que, si es parcialmente lleno (si está mas lleno que vacío) se le da el

color negro, de lo contrario, se le da el color blanco, es decir, la compresión por medio de

quadtrees es recursiva. [Bow, 1992]

Esta técnica se utiliza principalmente cuando la figura es una matriz cuadrada.

Luego la matriz se divide en cuatro cuadrantes como se mencionó anteriormente [Bow,

1992].

En este caso se manejaron diferentes tipos de imágenes. La forma en la que se están

manejando los quadtrees es solamente la segmentación y generación de una cadena que

representa cada uno de los cuadrantes.. Pero podemos ver otro ejemplo de cómo se

representa un triángulo en quadtrees:



La representación lineal es:
100 10000 10000000 11 00000 100 1011 01 0000 01...

1 = Subdividido
0 = Dividido

1 = Rojo
0 = Blanco

Figura 2.2. -Representación lineal de un quadtree.



En cada uno de los servidores, se van a colocar diferentes páginas con imágenes con

figuras fragmentadas mediante mx-quadtrees.

2.1.2. MX-quadtrees

En contraste con los kd-trees y los punto-quadtree, la figura del árbol mx-quadtree

es independiente del numero de nodos presentes en el árbol, así como el orden de inserción

en estos nodos [Subrahmanian, 1998].

La raíz de un mx-quadtree representa la región especificada por XLB=0, XUB=2k,

YLB=0, YUB=2k. Si N es un nodo, las regiones de los 4 hijos son representadas por la

siguiente tabla, que es una extensión del trabajo realizado por Subrahmanian:

En esta tabla, ancho=weight=(N.XUB-N.XLB) es lo mismo que weight=(N.YUB-

N.YLB) [Subrahmanian, 1998].

HIJOS

N.XLB

N.XUB

N.YLB

N.YUB

N.XLB

N.XLB + w/2

N.YLB + w/2

N.YLB + w

N.XLB

N.XLB + w/2

N.YLB

N.YLB + w/2

N.XLB + w/2

N.XLB + w

N.YLB + w/2

N.YLB + w

N.XLB + w/2

N.XLB + w

N.YLB

N.YLB + w/2

Tabla 2.1 Descripción de coordenadas de los cuadrantes de un mx-quadtree

NW

SW

NE

SÉ



Como podemos ver en la siguiente figura, se describe el área completa de la imagen:


YUB



YLB


NO

SO

XLB

NE

SE



XUB

Figura 2.3 Representación de los 4 cuadrantes de un mx-quadtree así como sus coordenadas inferiores y

superiores.

2.1.3 Inserción y búsqueda en un Mx-quadtree.

Cada punto(x,y) en un mx-quadtree, representa una región de 1*1 en donde su

extremo inferior izquierdo es (x,y). Un punto se inserta en el nodo representado por la

región 1*1 correspondiente a ese punto. Es decir, en general, los puntos se insertan siempre

en el nivel k en los mx-quadtrees [Subrahmanian, 2000].

2.1.4 Eliminación en un mx-quadtree

El borrado en un mx-quadtree es una operación muy sencilla porque todos los

puntos son representados por los niveles de las hojas. Si N es un nodo anterior en un mx-

quadtree cuya raíz es el punto representado por T, la región representada por el nodo N,

contiene al menos un punto que se encuentra dentro del árbol. Si queremos borrar un

punto(x,y) del árbol T, seguimos los siguientes pasos [Subrahmanian, 1998]:

?? Primero, asignamos un link del padre de N a nulo. Es decir, si M es padre de N, y si

M.DIR apunta a N, asignamos M.DIR= nulo y regresamos N como un lugar

disponible.

?? Entonces, revisamos si los 4 campos de M son todos nulos. De ser así, revisamos al

padre de M (que ahora es P). Como M es hijo de P, encontramos un campo DIR1

así como P.DIR1=M, entonces seguimos los mismos pasos.

Todo consiste en atravesar el árbol de la punta hasta el final (para poder encontrar

el nodo que ha sido borrado).

2.2 Recuperación de información

La compresión de

imágenes se vuelve necesaria cuando deseamos calcular el

número de bits por imagen de una estimación de muestras y conteo de algún esquema. Uno

de los aspectos más importantes del almacenaje de imágenes es obtener una compresión

eficiente.

En un ambiente distribuido, los archivos de imágenes grandes permanecen en un

cuello de botella principal sin sistemas de compresión, lo cual representa un componente

importante para las soluciones permitidas de crear archivos de dimensiones manejables y

transmisibles.

La portabilidad de plataformas y ejecución son importantes pa