PROCESAMIENTO DE IMÁGENES DIGITALES
ETIQUETADO DE
COMPONENTES CONEXAS EN
ÁRBOLES CUADRÁTICOS
AUTORES
• Borja González García de Cosío.
• José Luis Solano Pérez.
• Juan Fournier Torres.
ÍNDICE
1.
Objetivos.
2.
Nociones básicas (quadtree).
3.
Aplicaciones.
4.
Paso de malla a quadtree.
5.
Etiquetado de componentes conexas sobre el quadtree.
6.
Ventajas y desventajas (conclusiones).
7.
Bibliografía y referencias.
ÍNDICE
1.
Objetivos.
2.
Nociones básicas (quadtree).
3.
Aplicaciones.
4.
Paso de malla a quadtree.
5.
Etiquetado de componentes conexas sobre el quadtree.
6.
Ventajas y desventajas (conclusiones).
7.
Bibliografía y referencias.
OBJETIVOS DEL PROYECTO
1.
Conversión de imágenes digitales a un formato
basado en árboles cuadráticos (quadtrees).
2.
Tratamiento de la adyacencia sobre el formato
quadtree. Etiquetado de componentes conexas.
ÍNDICE
1.
Objetivos.
2.
Nociones básicas (quadtree).
3.
Aplicaciones.
4.
Paso de malla a quadtree.
5.
Etiquetado de componentes conexas sobre el quadtree.
6.
Ventajas y desventajas (conclusiones).
7.
Bibliografía y referencias.
NOCIONES BÁSICAS (QUADTREE) (1 de 2)
NO
NE
SO
SE
NO
NE
SO
Cada nodo gris representa un cuadrante que por no ser
homogéneo se subdivide en 4 nuevas ramas del árbol.
Cada nodo hoja representa un cuadrante de cualquier
tamaño que es homogéneo en color (negro o blanco).
SE
NOCIONES BÁSICAS (QUADTREE) (2 de 2)
NO
NE
NO
NE
SO
SE
SO
SE
NO
NE
NO
NE
SO
SE
SO
SE
ÍNDICE
1.
Objetivos.
2.
Nociones básicas (quadtree).
3.
Aplicaciones.
4.
Paso de malla a quadtree.
5.
Etiquetado de componentes conexas sobre el quadtree.
6.
Ventajas y desventajas (conclusiones).
7.
Bibliografía y referencias.
APLICACIONES (1 de 6)
•
Compresión.
•
Diagramas deVoronoi.
•
Fractales.
APLICACIONES (2 de 6)
Compresión
•
•
•
•
Se realiza al mismo tiempo que la compresión del árbol.
Fácil codificación y decodificacíon.
No necesita preprocesamiento.
Quadtree frente a JPG.
APLICACIONES (3 de 6)
Diagramas deVoronoi
APLICACIONES (4 de 6)
Diagramas deVoronoi
1 1 1
2
2
2
2
3
4
4 4
4 4
4 4
5
5 5
5 5
2
2
2
2
2
4
4
4
4
4
2
2
2
2
2
4
4
4
4
4
2
2
2
2
2
4
4
4
4
4
-1
2
2
2
2
-1
-1
-1
-1
-1
1
1
1
-1
2
5
5
5
5
5
1 1 1 1
2 2 1 1 1 1
2 2 1 1 1 1
2 2
3
3
4
5 5 5 3
4
5 5 5 5
4
5 5 5 5
5 5 5 5
1
1
1
-1
5
5
5
5
5
1
1
1
-1
3
-1
5
5
5
5
1
1
1
-1
3
3
3
5
5
5
1
1
1
-1
3
3
3
-1
5
5
1
1
1
-1
3
3
3
3
1
1
1
3 3
3 3
3 3
2
2
2
2
2
4
4
4
4
4
2
2
2
2
2
4
4
4
4
4
2
2
2
2
2
4
4
4
4
4
-1
2
2
2
2
-1
-1
-1
-1
-1
1
1
1
-1
2
5
5
5
5
5
1
1
1
-1
-1
5
5
5
5
5
1
1
1
-1
3
-1
5
5
5
5
1
1
1
-1
3
3
3
5
5
5
1
1
1
-1
3
3
3
-1
5
5
1
1
1
-1
3
3
3
3
-1
5
APLICACIONES (5 de 6)
Diagramas deVoronoi
• Detección de regiones ( puestos de socorro, policía, incendios... ).
• Reconocimiento de patrones (imágen y sonido).
• Control aéreo.
• Aplicaciones científicas (medicina, biología, química, ...).
• Manipulación de datos espaciales (estadística).
•Sistemas de Información Geográfica ( SIG ).
APLICACIONES (6 de 6)
Fractales
•Como formato de compresión.
•Arte.
ÍNDICE
1.
Objetivos.
2.
Nociones básicas (quadtree).
3.
Aplicaciones.
4.
Paso de malla a quadtree.
5.
Etiquetado de componentes conexas sobre el quadtree.
6.
Ventajas y desventajas (conclusiones).
7.
Bibliografía y referencias.
PASO DE MALLA A QUADTREE
-En un primer paso, construimos un arbol cuaternario
completo, extendido hasta el nivel de hojas.
-Posteriormente en un recorrido de este árbol, vamos
asignando los colores a los nodos intermedios y eliminando
los nodos de niveles inferiores cuando sea oportuno.
Nodo
Sin color
ÍNDICE
1.
Objetivos.
2.
Nociones básicas (quadtree).
3.
Aplicaciones.
4.
Paso de malla a quadtree.
5.
Etiquetado de componentes conexas sobre el quadtree.
6.
Ventajas y desventajas (conclusiones).
7.
Bibliografía y referencias.
ETIQUETADO DE COMPONENTES CONEXAS
¿QUÉ VAMOS A HACER?
¿CÓMO HACERLO VORAZMENTE?
¿CÓMO HACERLO EFICIENTEMENTE?
(1 de 6)
ETIQUETADO DE COMPONENTES CONEXAS
¿QUÉ VAMOS A HACER?
Queremos conocer las
componentes conexas de una
imagen a partir de su
representación quadtree.
5 componentes conexas negras.
2 componentes conexas blancas.
(4-adyacencia)
(2 de 6)
ETIQUETADO DE COMPONENTES CONEXAS
(3 de 6)
¿QUÉ VAMOS A HACER?
Imagen
(malla)
quadtree
PROCESO DE ETIQUETADO
1. Etiquetado de nodos
Ya sabemos a qué
componente
conexa pertenece
cada nodo
• Vorazmente
• Eficientemente
2. Procesado de etiquetas
equivalentes
ETIQUETADO DE COMPONENTES CONEXAS
(4 de 6)
ETIQUETADO DE NODOS VORAZ
QUADTREE
IMÁGEN
SI Pertenecerán a la
Misma componente conexa
Algoritmo CRO
NO No pertenecerán a la
Misma componente conexa
¿SERÁN 4-ADYACENTES EN
LA IMAGEN
ESOS DOS GRUPOS
DE PÍXELES?
Algoritmo CRO
GRUPO DE
PÍXELES
DEL
MISMO
COLOR
GRUPO DE
PÍXELES
DEL
MISMO
COLOR
ETIQUETADO DE COMPONENTES CONEXAS
(5 de 6)
ETIQUETADO DE NODOS VORAZ
Basta con recorrer las hojas del árbol dos a dos, e ir preguntando por el color y la adyacencia
de la pareja. Orden de complejidad prohibitivo.
Algoritmo CRO  ¿ son 4-adyacentes dos hojas del
quadtree?
NO - NE - SE NO - NE - SE -
NE - SO NO - SE -
SO - NO
SE - NE
Regla 1: coinciden siempre en una de las dos componenetes
(ROJO)
Regla 2: la otra comp.coincidirá hasta un punto (AZUL) a partir
del cual se cambia y se mantiene en el resto de su camino.
ETIQUETADO DE COMPONENTES CONEXAS
(6 de 6)
ETIQUETADO DE NODOS EFICIENTE
Función de vecindad:
NODO GTEQUAL(NODO n , DIRECCION d)
Devuelve el nodo vecino a “n” en la dirección d,
siendo la dirección Norte, Sur, Este u Oeste.
1 2
GTEQUAL (1 , Este)
Nodo 2
GTEQUAL (2 , Oeste)
Nodo 1
ETIQUETADO DE COMPONENTES CONEXAS
(7 de 6)
ETIQUETADO DE NODOS EFICIENTE
2
1
1
GTEQUAL (1 , Este)
Nodo 2
GTEQUAL (1 , Este)
Nodo 2
2
ETIQUETADO DE COMPONENTES CONEXAS
(8 de 6)
ETIQUETADO DE NODOS EFICIENTE
- Recorrido de los nodos negros del quadtree comprobando cada
nodo con sus vecinos Sur y Este, por si estos también son negros
- Si ya estuviesen etiquetados ambos con etiquetas dintintas, se
guarda la pareja en la tabla de equivalencias
1
2 2
1
2
1 1 1 2
ET 1
....
1
...
ET 2
....
2
...
TABLA DE EQUIVALENCIAS
ETIQUETADO DE COMPONENTES CONEXAS
(8 de 6)
PROCESADO DE ETIQUETAS EQUIVALENTES
ET 1
1
2
3
....
ET 2
2
3
4
....
TABLA DE
EQUIVALENCIAS
• Recorrido de las etiquetas del primer
proceso (antiguas) comprobando las
transitividades de forma recursiva
• Para cada etiqueta-antigua hay que
recorrer el quadtree entero
• Problema con orden de complejidad a
considerar para imágenes grandes
ÍNDICE
1.
Objetivos.
2.
Nociones básicas (quadtree).
3.
Aplicaciones.
4.
Paso de malla a quadtree.
5.
Etiquetado de componentes conexas sobre el quadtree.
6.
Ventajas y desventajas (conclusiones).
7.
Bibliografía y referencias.
VENTAJAS Y DESVENTAJAS (CONCLUSIONES)
VENTAJAS
• Rápida transformación de la imagen al quadtree y viceversa.
• Gran compresión en imágenes simples (homogeneidad).
• No necesita preprocesamiento en la compresión.
• Buen comportamiento en tratamiento recursivo.
DESVENTAJAS
• Poca compresión en imágenes demasiado complejas en el colorido / grises.
• Mal comportamiento sobre imágenes no homogéneas.
• El orden de la matriz (cuadrada) debe ser potencia de dos, bytes relleno.
• Tratamiento del color.
ÍNDICE
1.
Objetivos.
2.
Nociones básicas (quadtree).
3.
Aplicaciones.
4.
Paso de malla a quadtree.
5.
Etiquetado de componentes conexas sobre el quadtree.
6.
Ventajas y desventajas (conclusiones).
7.
Bibliografía y referencias.
BIBLIOGRAFÍA Y REFERENCIAS.
“Connected Component Labeling Using Quadtrees.”
Hanan Samet.
“Quadtree conectivity.”
http://geometrycomputing.issyua.ru/dep14/~qtree.html
“Computer graphics and image processing”
Charles R. Dyer
Descargar

www.sav.us.es