algoritmo de búsqueda de bordes en una imagen digital. obtención del código de fisuras y de...

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

Obtención del código de fisuras y de cadenas

Grupo:

José Manuel Berrio MorgadoFrancisco José Carrasquilla OrtizMaría Jesús León PeñaMarí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íaBú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

00000000000000000000000111111110000000001111111100000000010000001000000000100000010000000001111111100000000000000000000

Búsqueda de bordes

El problema de la repetición de bordes

00000000000000000000000111111110000000001111111100000000010000001000000000100000010000000001111111100000000000000000000

Búsqueda de bordes

Solución a la repetición: Marcado

00000000000000000000000111111110000000001111111100000000010000001000000000100000010000000001111111100000000000000000000

Búsqueda de bordesBordes exteriores e interiores

simultáneamente

00000000000000000000000111111110000000001111111100000000010000001000000000100000010000000001111111100000000000000000000

Búsqueda de bordesMarcado en función de la componente

conexa del blanco

00000000000000000000000111111110000000001111111100000000010000001000000000100000010000000001111111100000000000000000000

Etiquetado de componentes conexas

11111111111111111111111 111111111 1111 333333 1111 2222 333333 1111 11111111111111111111


00000000000000000000000 000000000 0000 000000 0000 0000 000000 0000 00010000000000000000


00000000000000000000000 000000000 0000 000000 0000 0000 000000 0001 00011000000000000000


00000000000000000000000 000000000 0000 000000 0001 0000 000000 0001 00011100000000000000


00000000000000000000000 000000000 0001 000000 0001 0000 000000 0001 00011110000000000000


00000000000000000000000 000110000 0001 000000 0001 0000 000000 0001 00011111000000000000


00000000000000000111000 000111000 0001 000000 0001 0000 000000 0001 00011111100000000000


11111111111111111111111 111111111 1111 000000 1111 0000 000000 1111 11111111111111111111


11111111111111111111111 111111111 1111 000000 1111 2000 000000 1111 11111111111111111111


11111111111111111111111 111111111 1111 000000 1111 2200 000000 1111 11111111111111111111


11111111111111111111111 111111111 1111 000000 1111 2222 000000 1111 11111111111111111111


11111111111111111111111 111111111 1111 000000 1111 2222 300000 1111 11111111111111111111


11111111111111111111111 111111111 1111 330000 1111 2222 330000 1111 11111111111111111111


11111111111111111111111 111111111 1111 333000 1111 2222 333000 1111 11111111111111111111


11111111111111111111111 111111111 1111 333333 1111 2222 333333 1111 11111111111111111111

Teoría

Crack following

000000000000001110000000111000000011100000001110000000000000

Teoría

Crack following

000000000000001110000000111000000011100000001110000000000000

PU UV VQ QPQV PQ UP VU

U V P’ Q’ Giro

- 1 V Q Derecha1 0 U V No0 0 P U Izquierda

Código: 122 8 adyacencia

Teoría

Crack following

000000000000001110000000111000000011100000001110000000000000

PU UV VQ QPQV PQ UP VU

U V P’ Q’ Giro

- 1 V Q Derecha1 0 U V No0 0 P U Izquierda

Código: 12228 adyacencia

TeoríaBorder following

000000000000000011111000000011011000000011011000000011111000000000000000


000000000000000011111000000011011000000011011000000011111000000000000000

Código: 0


000000000000000011111000000011011000000011011000000011111000000000000000

Código: 00


000000000000000011111000000011011000000011011000000011111000000000000000

Código: 000


000000000000000011111000000011011000000011011000000011111000000000000000

Código: 0000


000000000000000011111000000011011000000011011000000011111000000000000000

Código: 00002


000000000000000011111000000011011000000011011000000011111000000000000000

Código: 00002

3214P0567

Movimientos

000000000000000011111000000011011000000011011000000011111000000000000000Código: 000022

Detalles de implementaciónEstructura del fichero

3,4,2,4,8

000001100000

Número de filas

Número de columnas

Número de colores

Adyacencia para el negro

Adyacencia para el blanco

Matriz binaria

Detalles de implementaciónEstructura 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ónEstructura de un pixel

struct pxl{char color;int compconexa;int marcado;

};

Detalles de implementaciónEstructura 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.

algoritmo de búsqueda de bordes en una imagen digital. obtención del código de fisuras y de...

Documents