- cÓdigo de cadenas - realizado por: - beatriz bravo de mansilla jimÉnez. - raÚl rodrÍguez...
Post on 24-Jan-2016
236 Views
Preview:
TRANSCRIPT
- CÓDIGO DE CADENAS -
REALIZADO POR:
- BEATRIZ BRAVO DE MANSILLA JIMÉNEZ.- RAÚL RODRÍGUEZ OLIVARES.- DANIEL DÍAZ PÉREZ.
ÍNDICE
• CÁLCULO DEL CÓDIGO DE CADENAS.• CURVA ABIERTA / CERRADA.• LONGITUD DE ARCO / PERÍMETRO.• RECTA DIGITAL.• ÁREA.• POLÍGONO.• COMPLEJIDAD.• TIPO DE DATOS.
CÓDIGO DE CADENAS (I)
• Representación de bordes
• Punto inicial
• Lista de movimientos
• 4 / 8 Adyacencia
• Código de cadenas de ida
• Ejemplo de cálculo
CÓDIGO DE CADENAS (II)
Punto inicial (4,0)10 0 0
0
010 0 0 0 1
00 0 0
0 0111
16 55 31 Código de cadenas:1
CURVA CERRADA / ABIERTA (I)
0 0 0 1 00 0 1 0 00 1 0 0 00 0 1 0 10 0 0 1 0
0 1 1 1 01 0 0 0 11 0 0 0 11 0 0 0 10 1 1 1 0
(1,0): 007665443221 (3,0): 55771
CURVA CERRADA / ABIERTA (II)
• Simetría de movimientos
• Ejemplo
n7 + n0 + n1 = n3 + n4 + n5 Mov. Horizontalesn1 + n2 + n3 = n5 + n6 + n7 Mov. Verticales
0 1 1 1 01 0 0 0 11 0 0 0 11 0 0 0 10 1 1 1 0
(1,0): 0 0 7 6 6 5 4 4 3 2 2 1
1 + 2 + 1 = 1 + 2 + 11 + 2 + 1 = 1 + 2 + 1
LONGITUD DE ARCO / PERÍMETRO
• Movimientos horizontales y verticales: +1
• Movimientos diagonales: +2• Ejemplo: 0 1 1 1 0
1 0 0 0 11 0 0 0 11 0 0 0 10 1 1 1 0
Perímetro: 1 + 1 + 2 + 1 + 1 + 2 + 1 + 1 + 2 + 1 + 1 + 2
Código: 0 0 7 6 6 5 4 4 3 2 2 1
RECTA DIGITAL: PROBLEMAS
• ¿ DISTINGUIR QUÉ ES UNA RECTA EN EL ÁMBITO DIGITAL?
RECTA DIGITAL: EJEMPLOS
EXISTEN CASOS EN LOS QUE NO HAY PROBLEMAS:EXISTEN CASOS EN LOS QUE NO HAY PROBLEMAS:
• HORIZONTALES
• VERTICALES
• DIAGONALES
RECTA DIGITAL: EJEMPLOS
HORIZONTALES:
1 1 1 1 1 1 1 1 1 1 1 ...
RECTA DIGITAL: EJEMPLOS
VERTICALES:
111111
RECTA DIGITAL: EJEMPLOS
DIAGONALES:
1
1
1
1
1
RECTA DIGITAL: EJEMPLOS
EN ALGUNOS CASOS NO ESTÁ CLARO SI ES O NO RECTA DIGITAL
1111 11
1111111 111111111
11111 111111111111
RECTA DIGITAL: PROPIEDADES
• PARA QUE UNA IMAGEN SEA RECTA DIGITAL DEBE CUMPLIR TRES PROPIEDADES.
• ESTAS PROPIEDADES SE ESTUDIARÁN CUANDO NO QUEDE CLARO SI LA IMAGEN ES O NO RECTA DIGITAL.
RECTA DIGITAL: PROPIEDADES
PROPIEDAD 1
• COMO MÁXIMO HAY DOS PENDIENTES DISTINTAS EN EL CÓDIGO DE CADENAS.
• SI HAY DOS, ÉSTAS NO DIFIEREN EN MÁS DE 45º.
RECTA DIGITAL: PROPIEDADES
PROPIEDAD 1
CORRECTA
1111 1111 1111
INCORRECTA
1111 1 1 1 1111
RECTA DIGITAL: PROPIEDADES
PROPIEDAD 2
• AL MENOS UNA DE LAS DOS PENDIENTES OCURRE EN LOS TRAMOS DE LONGITUD DOS.
RECTA DIGITAL: PROPIEDADES
PROPIEDAD 2
CORRECTA
1111 1111 1111
INCORRECTA
1111 1 1111
RECTA DIGITAL: PROPIEDADES
PROPIEDAD 3
• LA OTRA PENDIENTE OCURRE EN TRAMOS CUYAS LONGITUDES DIFIEREN COMO MÁXIMO EN 1.
RECTA DIGITAL: PROPIEDADES
PROPIEDAD 3
CORRECTA
11111 1111 11111
INCORRECTA
1111111 11
1111111111111
RECTA DIGITAL: CÁLCULO
• PARA VERIFICAR SI UNA IMAGEN ES O
NO RECTA DIGITAL SE COMPROBARÁN
LAS TRES CONDICIONES ANTERIORES.
RECTA DIGITAL: CÁLCULO
PROPIEDAD 1
• COMPROBAR EL NÚMERO DE CÓDIGOS DISTINTOS QUE HAY EN EL CÓDIGO DE CADENAS (DOS COMO MÁXIMO).
• COMPROBAR QUE ESTOS SE DIFERENCIAN EN UNO.
RECTA DIGITAL: CÁLCULO
PROPIEDAD 1
1 1 1 1 1 1 1 1 1 1
CODIGO DE CADENAS
0 0 0 7 0 0 7 0 0
RECTA DIGITAL: CÁLCULO
PROPIEDAD 2
• COMPROBAR QUE UNO DE LOS CÓDIGOS SE REPITE SÓLO EN TRAMOS DE LONGITUD UNO EN EL CÓDIGO DE CADENAS.
• QUE SE REPITA EN UNO EN EL CÓDIGO SIGNIFICA QUE EN LA IMAGEN EL TRAMO MIDE DOS.
RECTA DIGITAL: CÁLCULO
PROPIEDAD 2
1 1 1 1 1 1 1 1 1 1
CÓDIGO DE CADENAS
0 0 0 7 0 0 7 0 0
RECTA DIGITAL: CÁLCULO
PROPIEDAD 3
• PARA COMPROBAR LA LONGITUD DE LOS TRAMOS SE ESTUDIARÁN LAS K-PENDIENTES.
• SI HAY MÁS DE DOS K-PENDIENTES NO SERÁ RECTA DIGITAL.
• LA ÚLTIMA K-PENDIENTE A COMPROBAR SERÁ IGUAL A LA LONGITUD DEL TRAMO MAYOR.
RECTA DIGITAL: CÁLCULO
K-PENDIENTE
• ES LA PENDIENTE DE UN TRAMO DE LONGITUD K.
1 1
1 1 1 3-PENDIENTE = Arctg (1/3)
RECTA DIGITAL: CÁLCULO
PROPIEDAD 3
• SI HAY MÁS DE DOS K-PENDIENTES DISTINTAS NO SERÁ RECTA DIGITAL, YA QUE ENTONCES EXISTIRÁ MUCHA DIFERENCIA EN LAS LONGITUDES.
11111111111 1111111111
3-PENDIENTE : 0 0 0 0 0 1/3 1/3 2/3 1/3 1/3 0 0 0 ...
RECTA DIGITAL: CÁLCULO
PROPIEDAD 3
1 1 1 1 1 1
1 1 1 1
K-PENDIENTES
k=1 : 0 0 0 1 0 0 1 0 0
k=2 : 0 0 1/2 1/2 0 1/2 1/2 0
k=3 : 0 1/3 1/3 1/3 1/3 1/3 1/3
k=4 : 1/4 1/4 1/4 1/2 1/4 1/4
ÁREA (I)
• Definición: Número de puntos
• Proceso: Integración discreta del borde de una imagen
• Imagen Compleja:- Agujeros
- Otras componentes
0 0 0 0 0 0 0 0 00 0 1 1 1 1 0 0 00 1 0 0 0 0 1 0 00 0 1 0 0 0 0 1 00 0 0 1 1 1 1 0 00 0 0 0 0 0 0 0 0
Área encerrada = 24
ÁREA (II): Procedimiento de cálculo
• Determinación del área por columnas
• Clasificación de puntos Puntos que no intervienen en el contorno Puntos que intervienen en el contorno
- Puntos salientes- Resto de puntos
ÁREA (III): Clasificación de puntos (I)
• Puntos que no intervienen en el contorno1 P 1
.. 6 7 ..
1P 1
.. 5 7 ..
1P1
.. 6 6 ..
1P 1
.. 5 6 ..
1 P 1
.. 2 3 ..
1 P1
.. 1 2 ..
1 P
1 .. 1 3 ..
1P1
.. 2 2 ..
ÁREA (IV): Clasificación de puntos (II)
• Puntos que intervienen en el contorno- Puntos salientes -
1 P 1
1P 1
Llegamos a ‘P’ con 7,
y lo abandonamos con 5Llegamos a ‘P’ con 3,
y lo abandonamos con 1
- Resto de puntos -
ÁREA (V): Ejemplo
1 1 1
11
1
1
1
11
1
1
1
1
1
El primero que se analiza es el siguiente del punto inicialya que hace falta realizar un movimiento para comprobar de qué tipo de punto se trata.
1 C1 C2 C3 C4 C5 C6
11
11
1
1
6 6
4
51 1
6
11
11 1
3
22
2
53
5
11
1
1
6
2 + 5 + 6 + 6 + 6 + 3 = 28
POLÍGONO (I)
• Definición: Segmentos de línea recta
• Longitud mínima ~ (tamaño del pixel)
• Lados y vértices
0 0 1 0 00 1 0 1 01 0 0 0 10 1 0 1 00 0 1 0 0
POLÍGONO (II): Proceso
• Determinación de lado
1
111
111
1
11
1
1
1.- Determinación del segmento mínimo
11
11
1
2.- Adición de un nuevo elemento
Es recta
Es recta
3.- Adición de un nuevo elemento
NO es recta
4.- Elección de un nuevo vértice
POLÍGONO (III): Proceso
• Determinación de vértice
1
111
111
1
11
1
1
Condiciones de elección del vértice 1.- Cambio brusco: Retrocede 1 2.- Cambio suave: Retrocede 2
Nuevo vértice
COMPLEJIDAD Cálculo del código de cadenas: O(n2)
Curva abierta o cerrada: O(n)
Cálculo de la longitud de arco o el perímetro: O(n)
Comprobación de rectas y cálculo de pendiente: O(n2)
Comprobación de polígono: O(s*m2)
Cálculo del área de una curva cerrada: O(n2)
TIPOS DE DATOS
• TIPO IMGTypedef struct{
int fila
int columna
int grises
int adyacencia
byte Matriz(128)(128)
}img;
TIPOS DE DATOS
• TIPO PUNTO
Typedef struct{
int fila
int columna
}punto;
TIPOS DE DATOS
• TIPO COD_CADENAS
Typedef struct{
unsigned codigo: 3;
void *sig;
}Cod_Cadenas;
top related