Download Document
Document related concepts
no text concepts found
Transcript
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