Algoritmo de búsqueda de bordes
en una imagen digital.
Obtención del código de fisuras y de
cadenas
Grupo:
José Manuel Berrio Morgado
Francisco José Carrasquilla Ortiz
María Jesús León Peña
María del Mar López Maraver
Contenido
1. Introducción
2. Teoría
2.1. Búsqueda de bordes.
2.2. Etiquetado de componentes conexas.
2.3. Crack following (fisuras).
2.4. Border following (cadenas).
Contenido
3. Detalles de implementación
3.1. Estructura del fichero.
3.2. Estructura de la matriz.
3.3. Estructura de un píxel.
3.4. Estructura de un borde.
Contenido
4. Complejidad
4.1. Búsqueda de bordes.
4.2. Etiquetado de componentes conexas.
4.3. Crack following.
4.4. Border following.
Introducción
Objetivos: Analizar una imagen digital, y encontrar todos
los bordes de la misma, tanto exteriores como interiores.
Para cada borde encontrado, se realizará un seguimiento
con dos métodos:
* código de fisuras (crack following).
* código de cadenas (border following).
Requisitos: Para realizar una correcta búsqueda, se ha
implementado el algoritmo de etiquetado de componentes
conexas.
Teoría
Búsqueda de bordes
1. Detección de bordes.
2. El problema de la repetición de bordes. Marcado.
3. El problema de la detección de bordes exteriores e
interiores simultáneamente.
Búsqueda de bordes
Detección de bordes
00000000000000000
00000011111111000
00000011111111000
00000010000001000
00000010000001000
00000011111111000
00000000000000000
Búsqueda de bordes
Detección de bordes
00000000000000000
00000011111111000
00000011111111000
00000010000001000
00000010000001000
00000011111111000
00000000000000000
Búsqueda de bordes
Detección de bordes
00000000000000000
00000011111111000
00000011111111000
00000010000001000
00000010000001000
00000011111111000
00000000000000000
Búsqueda de bordes
Detección de bordes
00000000000000000
00000011111111000
00000011111111000
00000010000001000
00000010000001000
00000011111111000
00000000000000000
Búsqueda de bordes
Detección de bordes
00000000000000000
00000011111111000
00000011111111000
00000010000001000
00000010000001000
00000011111111000
00000000000000000
Búsqueda de bordes
Detección de bordes
00000000000000000
00000011111111000
00000011111111000
00000010000001000
00000010000001000
00000011111111000
00000000000000000
Búsqueda de bordes
Detección de bordes
00000000000000000
00000011111111000
00000011111111000
00000010000001000
00000010000001000
00000011111111000
00000000000000000
Búsqueda de bordes
El problema de la repetición de bordes
00000000000000000
00000011111111000
00000011111111000
00000010000001000
00000010000001000
00000011111111000
00000000000000000
Búsqueda de bordes
Solución a la repetición: Marcado
00000000000000000
00000011111111000
00000011111111000
00000010000001000
00000010000001000
00000011111111000
00000000000000000
Búsqueda de bordes
Bordes exteriores e interiores
simultáneamente
00000000000000000
00000011111111000
00000011111111000
00000010000001000
00000010000001000
00000011111111000
00000000000000000
Búsqueda de bordes
Bordes exteriores e interiores
simultáneamente
00000000000000000
00000011111111000
00000011111111000
00000010000001000
00000010000001000
00000011111111000
00000000000000000
Búsqueda de bordes
Bordes exteriores e interiores
simultáneamente
00000000000000000
00000011111111000
00000011111111000
00000010000001000
00000010000001000
00000011111111000
00000000000000000
Búsqueda de bordes
Marcado en función de la componente
conexa del blanco
00000000000000000
00000011111111000
00000011111111000
00000010000001000
00000010000001000
00000011111111000
00000000000000000
Etiquetado de componentes
conexas
11111111111111111
111111
111
111111
111
1
333333 111
1 2222 333333 111
1
111
11111111111111111
Etiquetado de componentes
conexas
00000000000000000
000000
000
000000
000
0
000000 000
0 0000 000000 000
0
000
10000000000000000
Etiquetado de componentes
conexas
00000000000000000
000000
000
000000
000
0
000000 000
0 0000 000000 000
1
000
11000000000000000
Etiquetado de componentes
conexas
00000000000000000
000000
000
000000
000
0
000000 000
1 0000 000000 000
1
000
11100000000000000
Etiquetado de componentes
conexas
00000000000000000
000000
000
000000
000
1
000000 000
1 0000 000000 000
1
000
11110000000000000
Etiquetado de componentes
conexas
00000000000000000
000000
000
110000
000
1
000000 000
1 0000 000000 000
1
000
11111000000000000
Etiquetado de componentes
conexas
00000000000000000
111000
000
111000
000
1
000000 000
1 0000 000000 000
1
000
11111100000000000
Etiquetado de componentes
conexas
11111111111111111
111111
111
111111
111
1
000000 111
1 0000 000000 111
1
111
11111111111111111
Etiquetado de componentes
conexas
11111111111111111
111111
111
111111
111
1
000000 111
1 2000 000000 111
1
111
11111111111111111
Etiquetado de componentes
conexas
11111111111111111
111111
111
111111
111
1
000000 111
1 2200 000000 111
1
111
11111111111111111
Etiquetado de componentes
conexas
11111111111111111
111111
111
111111
111
1
000000 111
1 2222 000000 111
1
111
11111111111111111
Etiquetado de componentes
conexas
11111111111111111
111111
111
111111
111
1
000000 111
1 2222 300000 111
1
111
11111111111111111
Etiquetado de componentes
conexas
11111111111111111
111111
111
111111
111
1
330000 111
1 2222 330000 111
1
111
11111111111111111
Etiquetado de componentes
conexas
11111111111111111
111111
111
111111
111
1
333000 111
1 2222 333000 111
1
111
11111111111111111
Etiquetado de componentes
conexas
11111111111111111
111111
111
111111
111
1
333333 111
1 2222 333333 111
1
111
11111111111111111
Teoría
Crack following
0000000000
0000111000
0000111000
0000111000
0000111000
0000000000
Teoría
Crack following
0000000000
0000111000
0000111000
0000111000
0000111000
0000000000
Teoría
Crack following
0000000000
0000111000
0000111000
0000111000
0000111000
0000000000
Teoría
Crack following
0000000000
0000111000
0000111000
0000111000
0000111000
0000000000
Código: 122
PU
QV
UV
PQ
VQ
UP
QP
VU
U
V
P’
Q’
Giro
1
0
1
0
0
V
U
P
Q
V
U
Derecha
No
Izquierda
8 adyacencia
Teoría
Crack following
0000000000
0000111000
0000111000
0000111000
0000111000
0000000000
Código: 1222
PU
QV
U
V
1
0
1
0
0
UV
PQ
P’
VQ
UP
Q’
V
Q
U
V
P
U
8 adyacencia
QP
VU
Giro
Derecha
No
Izquierda
Teoría
Border following
000000000000
000011111000
000011011000
000011011000
000011111000
000000000000
Teoría
Border following
000000000000
000011111000
000011011000
000011011000
000011111000
000000000000
Código: 0
Teoría
Border following
000000000000
000011111000
000011011000
000011011000
000011111000
000000000000
Código: 00
Teoría
Border following
000000000000
000011111000
000011011000
000011011000
000011111000
000000000000
Código: 000
Teoría
Border following
000000000000
000011111000
000011011000
000011011000
000011111000
000000000000
Código: 0000
Teoría
Border following
000000000000
000011111000
000011011000
000011011000
000011111000
000000000000
Código: 00002
Teoría
Border following
000000000000
000000000000
000011111000
000011111000
321
000011011000
000011011000
4P0
000011011000
000011011000
567
000011111000
000011111000
000000000000 Movimientos 000000000000
Código: 00002
Código: 000022
Detalles de implementación
Estructura del fichero
3,4,2,4,8
Número de filas
0000
0110
0000
Número de columnas
Número de colores
Adyacencia para el negro
Adyacencia para el blanco
Matriz binaria
Detalles de implementación
Estructura de la matriz
#define F 20
#define C 50
struct MatBin{
int filas;
int columnas;
int numcolores;
int adnegro;
int adblanco;
pxl pixel[F][C];
};
Detalles de implementación
Estructura de un pixel
struct pxl{
char color;
int compconexa;
int marcado;
};
Detalles de implementación
Estructura de un borde
struct Borde{
int fila;
int columna;
int codigoCadena[150];
int codigoFisura[150];
};
Complejidad
Búsqueda de bordes: O(N2)
Etiquetado de componentes conexas: O(N2)
Crack following: O(M)
Border following: O(M)
N: nº de filas/columnas de la matriz.
M: nº de pixels del borde.
Descargar

Algoritmo de búsqueda de bordes en una imagen digital.