Download Document

Representación y
Descripción
Introducción
„
„
La representation se utiliza para hacer los
datos útiles a una computadora (posterior
descripción del proceso)
representando una región en 2 formas
„
„
„
en términos de sus características externas (su
contorno) > en base a las características de forma
en términos de sus características internas (su
región) > en base a sus propiedades regionales, por
ej., color, textura
algunas veces, necesitamos utilizar ambas
formas
2
Introducción
„
„
La Descripción describe la región en base
a la representación elegida
por ej.
„
„
representación > contorno
descripción > longitud del contorno,
orientación de la línea recta que une sus
puntos extremos, y el número de
concavidades en el contorno.
3
Sensibilidad
„
las características seleccionadas como
descriptores deben ser tan insensibles
como sea posible para variaciones en
„
„
„
„
tamaño
translación
rotación
los siguientes descriptores satisfacen
yna o mas de estas propiedades.
4
Representación
„
„
„
Las técnicas de segmentación dan datos en
crudo en forma de pixeles a lo largo de un
contorno de pixeles conectados en una región
estos datos se utilizan directamente para
obtener descriptores
Slas técnicas de uso estándar para calculan los
datos mas útiles (descriptores) desde los datos
en crudo a fin de disminuir el tamaño de los
datos.
5
Codigos cadena
FIGURA 11.1
Números de dirección
para (a) código cadena
de 4 direcciones, y (b)
código cadena de 8
direcciones
„
basados en conectividad 4 u 8
6
FIGURA 11.2
(a)
Contorno
digital con
grilla remuestreada
superpuesta.
(b)
Resultado del
re-muestreo
(c)
Código cadena
de 4direcciones
(d)
Código cadena
de 8
direcciones
7
Códigos cadena
„
inaceptables dado que
„
„
los códigos cadena resultantes tienden a se
bastante largos
cualquier perturbación pequeña a lo largo del
contorno debido al ruido o segmentación
imperfecta causan cambios en el código que
pueden no estar relacionadas a la forma del
contorno
8
Códigos cadena
„
solucionando los problemas por
„
„
„
„
remuestreo del contorno seleccionando una grilla de
espaciado mas grande
sin embargo, diferentes grillas pueden generar
diferentes códigos cadena
el punto de inicio es arbitrario
necesita ser normalizado para la generación del
código de forma que los códigos con diferente
punto de inicio sean iguales.
9
Códigos cadena normalizados
„
„
„
„
se tratan los códigos cadena como una secuencia circular
de números dirección y se redefine el punto de inicio de
modo que la secuencia resulante de números forme un
entero de magnitud mínima > “números de forma”
o se utiliza la diferencia primera del código cadena
diferencia = el números de cambios de dirección en una
dirección contraria a las agujas del reloj
Ej.
„
„
„
„
código 10103322
la diferencia es diferencia es 3133030
código cadena circular: 33133030
rotación del código cadena circular: 03033133
10
Códigos cadena normalizados
„
„
son exactos solamente si los contornos son
invariantes a rotación y cambio de escala.
pero estos raramente son los casos.
11
Aproximación Poligonal
„
„
„
el contorno puede ser aproximado con una
precisión arbitraria por un polígono
trata de capturar la “esencia” de la
forma del contorno con la menor cantidad
posible de segmentos del poligono.
no es trivial y consume tiempo
12
Polígonos de perímetro mínimo
FIGURA 11.3
(a)
Contorno de
un objeto
encerrado por
celdas.
(b)
Polígono de
perimetro
mínimo
„
„
„
si cada celda encierra solamente un punto del contorno
el error es como máximo 2d
d es la mínima distancia posible entre pixeles diferentes
13
Técnicas de Unión
„
„
baseadas en el error promedio u otros
criterios
Une los puntos a lo largo del contorno
hasta que el error cuadrático mínimo de
la línea de ajuste formada por los puntos
unidos exceda un umbral definido
14
Técnicas de división
FIGURA 11.4
(a)
Contorno
original.
(b)
Contorno
dividido en
segmentos
basado en los
puntos
extremos.
(c)
Unión de los
vértices
(d)
Polígono
resultante
1. buscar el eje principal
2. buscar el eje menor que es perpendicular al eje
mayor y tiene distancia mayor que un umbral
3. repetir hasta que no se pueda dividir mas
15
Firmas
FIGURA 11.5
Firmas distanciaversus-ángulo. En (a)
r(Θ) es constante. En
(b), la firma consiste de
las repeticiones del
patrón
mapea una función 2D en una función 1D
16
Segmentos de Contornos
FIGURA 11.6
(a) Una región S y su
deficiencia convexa
(sombreada).
(b) Contorno
particionado
„
„
el cerco convexo H de un conjunto arbitrario S es el
conjunto convexo mas pequeño contenido en S
el conjunto diferencia H-S se llama deficiencia convexa
D del conjunto S
17
Esqueletos
FIGURA 11.7
Eje medio
(entrecortado) de tres
regiones simples
eje medio (esqueleto)
18
MAT
„
MAT de la región R con borde B es como
sigue.
„
„
„
para cada punto p en R, buscamos su vecino
mas cercano en B.
si p tiene mas que uno de tales vecinos, se
dice que pertenece al eje medio de R
el mas cercano depende de la definición
de distancia
19
Adelgazamiento
FIGURA 11.8
Arreglo de vecindad
usado por el
algoritmo de
adelgazamiento
eliminación iterativa de los puntos de borde de una
región con restricciones
1. no remover puntos extremos
2. no romper la conectividad
3. no causar excesiva erosión de la región
20
Se supone que los puntos de la región tienen valor 1 y que
los puntos de fondo tienen valor 0
Punto de contorno es cualquier
pixel con valor 1 y que tiene al
menos uno de 8-vecinos de valor 0
paso 1: marcar con un flag un punto de contorno
p1 para eliminar si se satisfacen las siguientes
condiciones
(a) 2 ≤ N(p ) ≤ 6
i
(b) T(p1 ) = 1
(c) p2 ⋅ p4 ⋅ p6 = 0
(d) p4 ⋅ p6 ⋅ p8 = 0
N ( p1 ) = p 2 + p 3 + K + p 8 + p 9
N(pi) es el número de vecinos no ceros de pi
21
Adespués que el paso 1 tiene marcados todos los
puntos del contorno que satisfacen todas las 4
condiciones, eliminar esos pixeles.
paso 2: permanecen las condiciones (a) y (b)
pero cambian las condiciones (c) y (d) a las
siguientes
(c)′ p2 ⋅ p4 ⋅ p8 = 0
(d)′ p2 ⋅ p6 ⋅ p8 = 0
poner un flag a los puntos restantes para
eliminar.
luego eliminar los puntos marcados
repetir los pasos 1) y 2) hasta que no haya mas
puntos para eliminar
22
Ejemplo
FIGURA 11.9
Ilustración de
condiciones (a) y
(b) en ec. (11.11). En este caso
N(p1)=4 y
T(p1)=3
23
Ejemplo
FIGURA 11.10
Hueso de una pierna
humana y esqueleto de
la región mostrado
superpuesto.
24
Descriptores de Contorno
„
„
„
„
„
„
longitud de un contorno
diametros
excentricidad
curvatura
número de forma
descriptores de Fourier
25
Longitud de un contorno
„
„
el número de pixeles a lo largo del
contorno
da una aproximación grosera de su
longitud
26
Diametros
Diam( B) = max[ D( pi , p j )]
i, j
„
„
D es una medida de distancia
pi y pj son puntos sobre el contorno B
27
Excentricidad
„
„
„
relación del eje mayor al eje menor
eje mayor = la línea que contiene los dos
puntos extremos que comprenden el
diámetro
eje menor = la línea perpendicular al eje
mayor
28
Curvatura
„
„
„
„
„
la velocidad de cambio de pendiente
dificil de obtener dado que los contornos
digitales tienden a ser localmente “quebrados”
usando la diferencia entre las pendientes de los
segmentos adyacentes (los que son
representados como líneas rectas)
usando división y unión para crear segmentos de
contorno adyacentes
concavo, convexo y esquina
29
número de Forma
FIGURA 11.11. Todas
las formas de orden 4,
6 y 8. Las direcciones
son desde la fig.
11.11(a) y el punto
indica el punto de
comienzo
Código 4-direccional
30
Figura 11.12
Pasos en la
generación de un
número de forma
31
Descriptores de Fourier
contorno = (x0,y0), … , (xK-1,yk-1)
FIGURA 11.13. Un contorno digital y su representación como una secuencia compleja. Los
puntos (x0,y0) y (x1,y1) mostrados son (arbitrariamente) los dos primeros puntos de la
secuencia
s (k ) = x(k ) + jy (k ) for k = 0 ,1,...,K-1
32
Descriptores de Fourier
transformación de Fourier
1
a (u ) =
K
K −1
∑ s ( k )e
(DFT)
− j 2πuk / K
for u = 0 ,1,...,K-1
k =0
a(u) : coeficientes de Fourier (Descriptores de Fourier)
Transformación Inversa de Fourier
K −1
s (k ) = ∑ a (u )e
j 2πuk / K
for k = 0 ,1,...,K-1
k =0
33
P Coeficientes de los
Descriptores de Fourier
P −1
sˆ(k ) = ∑ a (u )e
j 2πuk / K
for k = 0 ,1,...,K-1
k =0
aproximación a s(k)
descriptores > número P de coeficientes
34
FIGURA 11.14
Ejemplos de la
reconstrucción
desde los
descriptores de
Fourier. P es el
número de
coeficientes de
Fourier usados
en la
reconstrucción
del contorno
35
Invariantes
TABLA 11.1
Identidad
Rotación
Translación
Escalado
Algunas
propiedades de
los descriptores
de Fourier
Punto de inicio
36
Descriptores Regionales
„
„
„
„
„
área
perímetro
densidad
descriptores topológicos
textura
37
Descriptores Simples
„
„
„
área = el número de píxeles en la región
perímetro = lengitud de su contorno
Densidad = (perímetro)2/área
38
Descriptores Topológicos
E=C-H
E = número de Euler
C = númbero de regiones conectadas
H = número de agujeros
FIGURA 11.17 Una región con dos agujeros
FIGURA 11.18 Una región con tres componentes conectados
39
FIGURA 11.19 Regiones con números de Euler iguales a 0 y -1, respectivamente
Segmentos de líneas rectas (redes poligonales)
V–Q+F=C–H=E
V = número de vértices
Q = número de bordes
F = número de caras
7-11+2 = 1-3 = -2
FIGURA 11.20 Una región conteniendo una red poligonal
40