Representaci¶on y Descripci¶ondea.unsj.edu.ar/imagenes/recursos/capitulo6.pdf · una curva cerrada, la aproximaci¶on es exacta cuando el numero¶ de lados del pol¶‡gono es igual

Capıtulo 6

Representacion y Descripcion

6.1 Introducion

Despues de segmentar una imagen, cada una de sus partes constitutivas debe ser representadaadecuadamente. El representar una region implica una de dos posibilidades,

1. Hacerlo en terminos de sus caracterısticas externas (su contorno).

2. Hacerlo en base a sus caracterısticas internas (los pixeles que comprenden la region).

La eleccion del metodo de representacion es solamente una parte de la tarea a realizar, el pasosiguiente consiste en describir la zona con la representacion elegida.

Generalmente se elige una representacion externa cuando el objetivo principal se centra en lascaracterısticas de forma y una representacion interna cuando el principal interes se centra en laspropiedades de reflectividad, tales como color y textura. En cualquier caso, las caracterısticas se-leccionadas como descriptores deberıan ser tan insensibles como fuera posible a cambios de tamano,traslacion y rotacion.

6.2 Esquemas de Representacion

La tecnicas de segmentacion estudiadas anteriormente producen datos en bruto en forma de pixelesde un contorno o de una region. Aunque algunas veces estos datos se utilizan de esta manerapara obtener descriptores, la practica comun es utilizar esquemas que compacten los datos enrepresentaciones que son mas utiles en el calculo de descriptores.

Las tecnicas se pueden clasificar en:

• Codigos cadena

209

210 CAPITULO 6. REPRESENTACION Y DESCRIPCION

Figura 6.1: Codificacion para conectividad 4 u 8.

• Aproximaciones poligonales

• Firmas

• Lados del contorno

• Esqueleto de una region

6.2.1 Codigos de Cadena

Los codigos de cadena se utilizan para representar un contorno por medio de una sucesion conexade segmentos de longitud y direccion especificadas. Normalmente esta representacion se basa ensegmentos de conectividad 4 u 8. La direccion de cada segmento se codifica utilizando un esquemade numeracion como se muestra en la figura 6.1.

Debido a que las imagenes digitales se adquieren sobre una cuadrıcula con igual espaciado horizontaly vertical, se podrıa generar un codigo cadena siguiendo el contorno, por ejemplo, en el sentido delas agujas del reloj y asignando una direccion a los segmentos que conectan cada par de pixeles.Este metodo es inaceptable por dos razones principales:

1. la cadena resultante es generalmente muy larga.

2. una pequena perturbacion debida al ruido o segmentacion imperfecta origina cambios en elcodigo, normalmente no relacionados al contorno.

Una de las soluciones que se puede utilizar es volver a muestrear el contorno seleccionando unespaciado de cuadrıcula mayor. Entonces segun se recorre el contorno, se asigna un punto delmismo a cada nodo del nuevo cuadriculado. El nuevo contorno obtenido se puede representar porun codigo de conectividad 4 u 8. El punto de partida, se define a voluntad. Obviamente la precisiondel codigo obtenido depende del espaciado seleccionado para el nuevo muestreo. Esta tecnica seejemplifica en la figura 6.2 y la figura 6.3 muestra los codigos cadena resultantes.

El codigo cadena de un contorno depende del punto de partida elegido, pero se puede normalizarpor un sencillo procedimiento:

6.2. ESQUEMAS DE REPRESENTACION 211

Figura 6.2: Resultado del nuevo muestreo.

Figura 6.3: Codigo cadena usando vecindad 4 y 8.


Dado un codigo cadena generado desde una posicion arbitraria, se trata como una serie circularde numeros y se redefine el punto de partida de modo que la serie de numeros resultante forme unentero de modulo mınimo.

Otra forma de normalizacion es por rotacion utilizando la primera diferencia del codigo cadena enlugar del propio codigo. Esta diferencia se obtiene simplemente contando (en sentido contrario alas agujas del reloj) el numero de direcciones que separan dos elementos adyacentes del codigo. Porejemplo, dado el codigo,

10103322, su primera diferencia es 3133030

si se decide tratar al codigo como una serie circular entonces el primer elemento de la diferencia secalcula entre el ultimo y el primer elemento, cuyo resultado es,

33133030

Hay que tener en cuenta que las normalizaciones son exactas solamente si los contornos son invari-antes a la rotacion y al cambio de escala, lo cual, rara vez ocurre en la practica.

6.2.2 Aproximaciones Poligonales

Un contorno digital se puede tratar con una precision arbitraria mediante un polıgono. Parauna curva cerrada, la aproximacion es exacta cuando el numero de lados del polıgono es igual alnumero de puntos del contorno, de forma tal que cada par de puntos adyacentes define un ladodel polıgono. En la practica, el objetivo de una aproximacion poligonal es captar la esencia de laforma del contorno, con un polıgono con el menor numero de lados posible.

Existen varias tecnicas de aproximacion poligonal de complejidad moderada que son adecuadaspara aplicaciones de procesamiento de imagenes.

Una de estas tecnicas consiste en encontrar un polıgono de perımetro mınimo. Supongase que seencierra el contorno en un conjunto de celulas concatenadas. Se puede pensar que estas celulasdefinen dos paredes correspondientes a los bordes exterior e interior de la sucesion de celulas, ypensando que el contorno es una banda de goma contenida entre las paredes. Si se permite que labanda de goma se encoja, tomara la forma de la figura 6.4.

produciendo un polıgono de perımetro mınimo que se adapta a la geometrıa establecida por lasucesion de celulas. Si cada celula abarca solamente un punto del contorno, el error en cada celulaentre el contorno original y la aproximacion de la banda de goma serıa, como maximo,

√2d, siendo

d la distancia entre pixeles. Este error se puede reducir a la mitad haciendo que cada celula estecentrada en su pixel correspondiente.

Un metodo para dividir lados del contorno consiste en subdividir sucesivamente el lado en dospartes hasta que se satisfaga un criterio dado. Por ejemplo, un requisito podrıa ser que la distanciaperpendicular maxima desde un lado del contorno a la lınea que une sus dos extremos no excedaun umbral establecido previamente. Si lo hace, el punto mas alejado se convierte en un vertice,


Figura 6.4: Poligono de perimetro minimo.

Figura 6.5: Subdivision de un contorno para busqueda de una aproximacion poligonal.

subdividiendo ası el lado en dos sublados. Esta aproximacion tiene la ventaja de buscar puntos deinflexion destacados. Para un contorno cerrado, los mejores puntos para comenzar son normalmentelos dos puntos mas separados del contorno. En la figura 6.5 se ejemplifica este procedimiento, semuestra el contorno de un objeto (a), la subdivision de este contorno (b), el punto c tiene la mayordistancia normal desde el lado superior a la lınea ab. De igual forma el punto d. El resultado deutilizar este procedimiento con un umbral igual a 0.25 veces la longitud de la lınea ab se muestraen (c). El resultado final se muestra en (d).

6.2.3 Firmas

Una firma es una representacion funcional unidimensional de un contorno y se puede generar devarias formas. Una de las mas simples es representar la distancia desde el centro al contorno comouna funcion del angulo. Las firmas generadas de esta manera no varıan con la traslacion, perodependen de la rotacion y del cambio de escala. Se puede normalizar con respecto a la rotacionencontrando un modo de seleccionar el mismo punto de partida para generar la firma y ası serindependiente de la orientacion del objeto. Un metodo podrıa ser elegir el punto mas alejado delcentro del objeto como punto de partida. Otro forma serıa elegir un punto sobre el eje mayor delobjeto. Con respecto a la variacion por cambio de escala, se puede normalizar escalando todas lasfunciones de manera tal que siempre abarque el rango de valores [0, 1]. La figura 6.6 muestra un


Figura 6.6: Objetos y su correspondiente firma.

Figura 6.7: Objeto y deficiencia convexa.

ejemplo de firma de objetos.

6.2.4 Lados del Contorno

En algunas ocasiones es util descomponer un contorno en lados. La descomposicion reduce lacomplejidad del contorno y simplifica ası el proceso de descripcion. Esta tecnica es apropiadacuando el contorno presenta una o mas concavidades significativas que contienen informacion sobrela forma.

En este caso el empleo del cerco convexo de la region abarcada por el contorno representa unapoderosa herramienta para la descomposicion robusta del contorno.

El cerco convexo H de un conjunto arbitrario S es el conjunto convexo mas pequeno que contienea S. El conjunto diferencia H − S se denomina deficiencia convexa D del conjunto S.

La figura 6.7(a) muestra un objeto (conjunto S) y su deficiencia convexa (region sombreada).

El contorno de la region se puede dividir siguiendo el contorno de S y marcando los puntos en losque se hace una transicion hacia adentro o afuera de un componente de la deficiencia convexa. Lafigura 6.7(b) muestra el resultado.

En la practica los contornos son irregulares a causa de la digitalizacion, el ruido, y las variaciones


Figura 6.8: Ejemplo de la MAT de una region.

en la segmentacion.

Estos efectos normalmente producen una deficiencia convexa que tiene componentes pequenos,esparcidos aleatoriamente sobre el contorno. Por este motivo, es practica comun suavizar el contornoantes de su division. Un mecanismo para hacer esto consiste en recorrer el contorno y reemplazarlas coordenadas de cada pixel por las coordenadas medias de sus m vecinos a lo largo del contorno.

6.2.5 El Esqueleto de una Region

Una importante aproximacion para representar la forma estructural de una region plana es reducirlaa un grafo. En esta reduccion se puede obtener el esqueleto de la region mediante un algoritmo dereduccion, denominado esqueletizacion.

El esqueleto de una region se puede definir en base a la Transformacion del Eje Medio (MAT)propuesta por [Blum, 1967].

La MAT de una region R con borde B se define como,

Para cada punto p de R, se encuentra su vecino mas proximo en B. Si p tiene mas de un vecinode estos, se dice que pertenece al eje medio (esqueleto) de R.

El concepto mas proximo depende de la definicion de distancia que se utilice, y por lo tanto losresultados de una operacion MAT estan influidos por esta eleccion. La figura 6.8 muestra el procesode obtencion de la MAT.

Aunque la MAT de una region proporciona un esqueleto instintivamente atrayente, la imple-mentacion directa de esa definicion normalmente es prohibitiva en terminos de calculo. La im-plementacion implica potencialmente el calculo de la distancia desde cada punto interior a cadapunto del contorno de una regi6n. Se han propuesto muchos algoritmos para mejorar la eficaciade calculo, mientras se intenta a la vez producir una representacion del eje medio de una region.Normalmente, estos son algoritmos de reduccion que suprimen iterativamente los puntos del mar-gen de una region sujetos a las restricciones que la supresion de estos puntos 1) no elimine puntosextremos, 2) no rompa la continuidad y 3) no cause excesiva erosion en la region. Se presenta un


algoritmo de reduccion de regiones binarias. Se supone que los puntos de la region tienen valor 1 ylos puntos del fondo tienen valor 0. El metodo consiste en pasadas sucesivas de dos pasos basicosaplicados a los puntos del contorno de una region dada, siendo un punto de contorno cualquierpixel con valor 1 que tenga al menos un 8-vecino con valor 0.

Con referencia a la definicion de 8-vecindad, el paso 1 marca un punto del contorno p para que seaeliminado si se satisfacen las siguientes condiciones:

1. 2 ≤ N(p1) ≤ 6

2. S(p1) = 1

3. p2.p4.p6 = 0

4. p4.p6.p8 = 0

donde N(p1) es el numero de vecinos no cero de p1, esto es:

N(p1) = p2 + p3 + · · ·+ p8 + p9

y S(p1) es el numero de transiciones 0− 1 en la secuencia ordenada p2, p3, · · · , p8, p9. Por ejemplo,N(p1) = 4 y S(p1) = 3 en la siguiente subimagen.

p9 p2 p3

p8 p1 p4

p7 p6 p5

0 0 11 p1 01 0 1

En el paso 2, las condiciones a) y b) permanecen igual pero las condiciones c) y d) cambian a,

1. p2.p4.p8 = 0

2. p2.p6.p8 = 0

El paso 1 se aplica a todo pixel del borde de la region binaria considerada. Si se violan una o masde las condiciones c) y d), no se cambia el valor del punto en cuestion. Si se satisfacen todas lascondiciones, se marca el punto para su supresion. Sin embargo, no se borra el punto hasta quetodos los puntos del borde hayan sido procesados. Este retraso impide que se cambie la estructurade los dates durante la ejecucion del algoritmo.

Despues de haber aplicado el paso 1 a todos los puntos del borde, se eliminan (se ponen a 0) aquellosque estaban marcados. A continuaci6n se aplica el paso 2 a los datos resultantes exactamente de lamisma forma que el paso 1. De esta forma, una iteraci6n del algoritmo de reducci6n consiste en:1)aplicar el paso 1 para marcar los puntos del borde a suprimir; 2) borrar los puntos marcados, 3)aplicar el paso 2 para marcar los restantes puntos del borde para su eliminaci6n, y 4) borrar lospuntos marcados. Este procedimiento basico se aplica iterativamente hasta que no se suprimen mas


Figura 6.9: Imagen original, esqueleto y MAT.

puntos, momento en el que termina el algoritmo, produciendo el esqueleto de la regi6n.La condici6na) no se cumple cuando el punto p1 del borde tiene solamente uno o siete 8-vecinos con valor 1, Eltener solamente uno de tales vecinos implica que el punto pl es el extremo de un trazo del esqueletoy evidentemente no deberıa ser borrado. Borrar p1 si tiene 7 de estos vecinos causarıa erosion en laregion. La condicion b) no se cumple cuando se aplica a puntos de un trazo de un pixel de grosor.

Por tanto, esta condicion evita la discontinuidad de segmentos de un esqueleto durante la operacionde reduccion. Las condiciones c) y (d) se satisfacen simultaneamente por el conjunto mınimo devalores: (p4 = 0 o p6 = 0) o (p2 = 0 y p8 = 0). Por tanto, y con respecto a la estructura de vecindad,un punto que satisface estas condiciones, ası come las a) y b), es un punto del borde sur o este oun punto de la esquina noroeste del contorno. En cualquier caso, p1 no forma parte del esqueletoy deberıa eliminarse. De igual forma, las condiciones c’) y d’) se satisfacen simultaneamente por elsiguiente conjunto mınimo de valores: (p2 = 0 o p8 = 0) o (p4 = 0 y p6 = 0). Estos corresponden alos puntos del borde norte u oeste, o al punto de la esquina sudeste. Observese que los puntos de laesquina nordeste tienen (p2 = 0 y p4 = 0) y por tanto satisfacen las condiciones c) y d) al igual quelos c’) y d’). Lo mismo es cierto para los puntos de la esquina sudoeste, que tienen p6 = 0 y p8 = 0.

Las figuras 6.9, 6.10, 6.11, 6.12 y 6.13 son ejemplos del esque leto de objetos frenta a distintassituaciones.

Algunas veces la sensibilidad a pequenos cambios puede ser util. Frecuentemente, sin embargo,se necesita extraer una imagen binaria desde la imagen es tonos de gris. En estos casos, es difıcilobtener la forma ideal del objeto, por lo tanto el esqueleto es muy complejo. Suponga la imagende la figura 6.14.

La figura 6.15 muestra el esqueleto encontrado en donde se observa la compleja forma que posee.La figura 6.16 ejemplifica la obtencion del esqueleto en una imagen contaminada con ruido.






Figura 6.13: Esta imagen demuestra la sensibilidad del esqueleto a pequenos cambios.

Figura 6.14: Imagen original.

Figura 6.15: Umbral=100 y esqueleto.


Figura 6.16: Sensibilidad al ruido del esqueleto.

6.3 Descriptores de Contorno

6.3.1 Descriptores Simples

Longitud del contorno: es el numero de pixeles a lo largo del contorno. Es la cantidad de compo-nentes horizontales + la cantidad de componentes verticales +

√2 veces la cantidad de componentes

diagonales.

Diametro de un contorno: Se B el contorno de un objeto. se define su diametro como,

Diam(B) = maxi,j

[D(pi, pj)]

donde D(pi, pj) es una medida de distancia.

Esquinas: Son lugares sobre el contorno donde la curvatura k(B) no esta acotado, es decir,

|k(B)|2 =(

d2y

dB2

)2

+(

d2x

dB2

)2

En la practica, se declara una esquina cuando la ecuacion anterior asume un valor suficientementealto, ver figura 6.17.

6.3.2 Numeros de Forma:

Segun se explico, la primera diferencia de un contorno codificado en codigo cadena depende delpunto de comienzo. El numero de forma de un contorno, basado en el codigo de 4-direcciones sedefine como el entero de modulo mınimo de la primera diferencia. El orden n de un numero de

6.3. DESCRIPTORES DE CONTORNO 221

Figura 6.17: Curva B y la medida de las esquinas.

Figura 6.18: Formas posibles de orden 4, 6 y 8.

forma se define como el numero de dıgitos de su representacion. Ademas, n es par para un contornocerrado y su valor limita el numero de formas posibles.

La figura 6.18 muestra todas las formas posibles de orden 4, 6 y 8.

Aunque la primera diferencia de un codigo cadena es independiente de la rotacion, en general elcontorno codificado depende de la orientacion de la grilla utilizada. Una forma de evitar esto es:

El eje mayor de un contorno es el segmento de recta que une los dos puntos mas separados entre sı.El eje menor es perpendicular al eje mayor y de una longitud tal que se puede formar un rectanguloque contenga exactamente al contorno (rectangulo mınimo). La relacion entre el eje mayor y el ejemenor se denomina la excentricidad de contorno, y el rectangulo ası formado rectangulo basico.

En la practica para un numero de forma deseado se halla el rectangulo de orden n cuya excentricidadse aproxime mejor a la del rectangulo basico y se utiliza este nuevo rectangulo para establecer eltamano de la grilla. Por ejemplo, si n = 12 todos los rectangulos de orden 12 (perımetro=12) son2× 4, 3× 3, 1× 5. Si la excentricidad del rectangulo de 2× 4 se acopla mejor a la del rectangulobasico se toma este como grilla y se obtiene el codigo cadena.

Por ejemplo supongase la figura 6.19 en donde n = 18, la figura 6.20 muestra la grilla utilizada y


Figura 6.19: Contorno original, ejes mayor y menor y rectangulo basico.

el codigo cadena generado.

6.3.3 Descriptores de Fourier

La figura 6.21 muestra el contorno digital de N puntos en el plano x − y. Partiendo de un puntoarbitrario (x0, y0), los pares de coordenadas (x0, y0),(x1, y1),(x2, y2) ,· · · ,(xN−1, yN−1) se encuentranal recorrer el contorno, por ejemplo en el sentido de las agujas del reloj.

Estas coordenadas se pueden expresar en la forma de una secuencia de valores discretos de la formax(k) = xk, y(k) = yk. Cada par de coordenadas de esta secuencia se puede tratar como un numerocomplejo tal que,

s(k) = x(k) + jy(k) k = 0, 1, 2, · · · , N − 1

Entonces se toma el eje x como eje real y el y como eje imaginario de la serie de numeros complejos.La ventaja de este procedimiento es que convierte un problema bidimensional en uno unidimen-sional.

La transformada discreta de Fourier de la serie s(k) es,

a(u) =1N

N−1∑

k=0

s(k) exp [−j2πuk/N ] u = 0, 1, 2, · · · , N − 1

Los coeficientes complejos a(u) se denominan descriptores de Fourier del contorno. La transformada


Figura 6.20: Rectangulo adoptado, codigo cadena generado.

Figura 6.21: Contorno digital expresado como sucesion de numeros complejos.


Figura 6.22: Contorno de un cuadrado y su reconstruccion con diferente numero de coeficientes.

inversa de Fourier de los a(u) restaura el contorno s(k). Es decir,

s(k) =N−1∑

u=0

a(u) exp [j2πuk/N ] k = 0, 1, 2, · · · , N − 1

Supongase que en lugar de utilizar todos los a(u) se utilizan los primeros M coeficientes. Esto esequivalente a hacer a(u) = 0 para u > M − 1. El resultado es la aproximacion de s(k),

s(k) =M−1∑

u=0

a(u) exp [j2πuk/N ] k = 0, 1, 2, · · · , N − 1

Recordar que los componentes de alta frecuencia responden al detalle fino y que los componentesde baja frecuencia determinan la forma global. Ası, cuanto menor sea M mas detalles se pierden.

La figura 6.22 muestra un contorno cuadrado que consiste de N = 64 puntos, y el resultado deutilizar la ecuacion anterior para varios valores de M . Se puede observar que con M = 8 la formadel contorno reconstruido se parece al cuadrado original. Cuando M = 56 comienzan a formarselas esquinas del cuadrado. Por lo tanto con pocos coeficientes se puede capturar la forma principal,mientras que se necesitan casi la totalidad para reconstruir los detalles.

Se ha dicho que los descriptores a utilizar deberıan ser insensibles a la rotacion, traslacion, el cambiode escala y tambien al punto de partida. Los descriptores de Fourier no son directamente insensiblesa estos cambios geometricos, pero los cambios estan relacionados con transformaciones simples.


Figura 6.23: Ejemplo de un contorno.

6.3.4 Momentos

La forma de los lados del contorno y de las firmas se pueden describir cuantitativamente utilizandomomentos. Considere la figura 6.23 que muestra un lado de contorno (a) y el mismo lado expresadocomo una funcion unidimensional g(r) de la variable r. Tratando la amplitud g como una variablealeatoria v y formando un histograma de amplitud p(vi), i = 1, 2, · · · , k siendo k el numero deincrementos de amplitud discretos..

Entonces se define el momento n-esimo de v respecto a su media, como,

µn(v) =k∑

i=1

(vi −m)np(vi)

donde m es la media,

m =k∑

i=1

vip(vi)

y µ2 la varianza.

Generalmente solo se necesitan los primeros momentos para diferenciar firmas claramente distintas.

Un metodo alternativo consiste en normalizar g(r) por unidad de area y tratarlo como un his-tograma. En este caso r se convierte en la variable aleatoria y los momentos se definen como,

µn(r) =L∑

i=1(ri −m)ng(ri)

m =L∑

i=1rip(ri)

En esta notacion, L es el numero de puntos del contorno y los momentos estan directamenterelacionados con la forma de g(r). Por ejemplo, el segundo momento mide la dispersion de la curva


respecto al valor medio de r y el tercer momento mide su simetrıa respecto a la media.

6.3.5 Descriptores de Region

Descriptores Basicos

Area: se define como el numero de pixeles encerrados por su contorno (A0).

Perımetro: Es la longitud del contorno de la region (P ).

Densidad: Este parametro, tambien llamado Circularidad se define como,

C =P 2

A0

Rectangularidad: se define como la razon entre el area total de la region sobre el area delrectangulo basico de la misma,

R =A0

AR

Ejes principales: se definen como los vectores propios de la matriz de Covarianza obtenida al utilizarlos pixeles interiores de la region como variables aleatorias. Los dos vectores propios de esta matrizapuntan en las direcciones de maxima expansion de la region, y estan sujetos a la restriccion deser ortogonales. El grado de expansion se mide por los valores propios correspondientes. Este tipode descriptor es insensible a la rotacion pero depende del cambio de escala. Para compensar esteinconveniente, se utiliza a veces, la relacion entre los dos valores propios.

6.3.6 Descriptores Topologicos

Las propiedades topologicas son utiles para descripciones globales de regiones. Definida en formasimple, la topologıa es el estudio de las propiedades de una figura a las que no afecta ningunadeformacion, en tanto no haya division horizontal o uniones en la figura (distorsiones de hojaelastica), figura 6.24.

Si se define un descriptor topologico como el numero e huecos de la region. Este numero puedevariar si se dobla o parte la region. Pero si estiramos la region este descriptor no se vera afectado.

Otra propiedad util como descriptor topologico es el numero de componentes conexas.

Una componente conexa de un conjunto es un subconjunto de tamano maximo tal que cualquierpar de puntos del mismo se puede unir por una curva conexa trazada completamente dentro delsubconjunto.

En la figura 6.24 existe una componente conexa.


Figura 6.24: Topologıa.

Figura 6.25: a) H=1, C=1, entonces E=0., b) H=2, C=1, entonces E=-1.

El Numero de Huecos H y de Componentes Conexas C de una figura se usan para definir el Numerode Euler,

E = C −H

Este numero es tambien una propiedad topologica. En la figura 6.25 se muestra este numero.

Las regiones representadas por segmentos de rectas (redes poligonales) poseen una sencilla inter-pretacion en terminos del numero de Euler. Sea la figura de la red poligonal 6.26.

A veces es importante clasificar las regiones interiores de la red en caras y huecos. Representando elnumero de vertices por W , el de bordes por Q y el de caras por F se obtiene la relacion, denominadaformula de Euler,

W −Q + F = C −H = E

La red mostrada en la figura 6.26 posee, W = 7, Q = 11, F = 2, C = 1, H = 3, por lo tantoE = −2.


Figura 6.26: Red poligonal.

6.3.7 Textura

Un metodo importante para para la descripci6n de regiones consiste en cuantificar su contenidode textura. Aunque no existe una definici6n formal de la textura, este descriptor proporcionaintuitivamente medidas de propiedades tales como suavizado, rugosidad y regularidad. Los tresmetodos principales mas utilizados en el procesado de imagenes para describir la textura de unaregion son:

• Estadısticos.

• Estructurales.

• Espectrales.

Las soluciones estadısticas proporcionan caracterısticas de texturas tales como suavidad, rugosidad,granulosidad, y otras similares. Las tecnicas estructurales tratan de la composicion de primitivasde imagenes, tales como la descripcion de texturas basadas en lıneas paralelas regularmente espa-ciadas. Las tecnicas espectrales se basan en las propiedades del espectro de Fourier y se utilizanprimordialmente para detectar la periodicidad global de una imagen mediante la identificaci6n depicos estrechos de alta energıa del espectro.

Metodos Estadısticos

Uno de los metodos mas simples para describir la textura consiste en utilizar mementos del his-tograma de nivel gris de una imagen o region. Sea z una variable aleatoria que indica la intensidadde una imagen discreta y sea p(zi), i = 1, 2, · · · , L el correspondiente histograma, donde L es elnumero de niveles de intensidad diferentes. Come se indico anteriormente, el momento n-esimo dez respecto a la media es:


µn(z) =L∑

i=1(zi −m)np(zi)

m =k∑

i=1zip(zi)

Se observa de estas ecuaciones que el momento 0 es igual a 1 y el momento 1 es igual a 0. Elsegundo momento (la varianza) es de particular importancia en la descripcion de texturas. Estaes una medida del contraste del nivel de gris que se puede utilizar para establecer descriptores desuavidad relativa.

R = 1− 11 + σ2(z)

Por ejemplo, la medida, es 0 para areas de intensidad constante (σ = 0 si todas las zi tienen elmismo valor) y se aproxima a 1 para valores grandes de σ(z). El tercer momento es una medidade la desviaci6n del histograma, mientras que el cuarto lo es de la monotonıa relativa. El quintomomento ası como los siguientes no estan tan facilmente relacionados con la forma del histograma,pero proporcionan una mayor discriminaci6n cuantitativa del contenido de la textura.

Las medidas de la textura calculadas utilizando solamente histogramas presentan la limitaci6n deno contener informacion referente a la posici6n relativa de cada pixel con respecto a los otros. Unaforma de introducir este tipo de informacion en el proceso de analisis de la textura consiste enconsiderar no solamente la distribucion de intensidades, sino tambien las posiciones de pixeles quetienen iguales, o casi iguales, valores de intensidad.

Sea P un operador de posicion y A una matriz k × k cuyo elemento aii es el numero de veces queaparecen puntos con nivel de gris zi en la posicion especificada por P en relacion con los puntoscon nivel de gris zj , con 1 ≤ i, j ≤ k. Por ejemplo, considerese una imagen con tres niveles de gris,zl = 0, z2 = 1 y z3 = 2, de la siguiente forma:

0 0 0 1 21 1 0 1 12 2 1 0 01 1 0 2 00 0 1 0 1

Definiendo el operador de posicion P como un pixel a la derecha y un pixel abajo genera la siguientematriz de 3× 3, A:

A =

4 2 12 3 20 2 0

donde, por ejemplo, a11 es el numero de veces que un punto con nivel zl = 0 aparece en la posicionde un pixel debajo y a la derecha de un pixel con el mismo nivel de gris; y al3 es el numero de veces


que un punto con nivel zl = 0 aparece en la posicion de un pixel debajo y a la derecha de un puntocon nivel de gris z3 = 2. El tamano de A esta determinado estrictamente por el numero de nivelesde gris diferentes de la imagen de entrada. Por ello la aplicacion de los conceptos presentados aquınormalmente requieren que se vuelvan a cuantificar las intensidades en unas pocas bandas de nivelde gris para mantener el tamano de A razonable. Sea n el numero total de pares de puntos de laimagen que satisfacen P (en el ejemplo anterior, n = 16).

Si se forma una matriz C dividiendo cada elemento de A por n, entonces cii es una estimacion de laprobabilidad conjunta que un par de puntos que satisfacen P tengan valores (zi, zj). La matriz Cse denomina matriz de coocurrencia de nivel de gris. Como C depende de P , se puede detectar lapresencia de un patron de textura dado eligiendo un operador de posicion apropiado. Por ejemplo, eloperador utilizado en el ejemplo anterior es sensible a bandas de intensidad constante ejecutandosea −45◦ (observese que el mayor valor de A era a11 = 4, que se debe parcialmente a una lınea depuntos de intensidad 0 y corriendo a −45◦). Mas generalmente, el problema consiste en analizaruna matriz dada C con el fin de establecer la categorıa de la textura de la region sobre la que secalculo C. Un conjunto de descriptores utiles para este fin incluye:

1. Maxima Probabilidadmax

i,j(cij)

2. Momento diferencia de orden k: ∑

i

∑

j

(i− j)kcij

3. Momento inverso diferencia de orden k:

∑

i

∑

j

cij

(i− j)ki 6= j

4. Entropıa:−

∑

i

∑

j

cij log cij4)

5. Uniformidad ∑

i

∑

j

c2ij

La primera propiedad da una indice de la respuesta mas fuerte a P . El segundo posee los valoresmas bajos cuando los mayores valores de C estan proximos a la diagonal. El tercer descriptor tieneel efecto inverso. El cuarto mide la aleatoriedad y finalmente el quinto tiene el efecto inverso alcuarto.

Otros descriptores estadısticos son los que estan basados en el histograma. Sea p(z) la funcion dedensidad de probabilidad de la imagen. Los primeros 4 momentos centrales se definen por,


1. Media

µ =N∑

k=1

zip(zi)

2. Varianza

σ2 =N∑

k=1

(zi − µ)2p(zi)

3. Asimetrıa

µ3 =1σ3

N∑

k=1

(zi − µ)3p(zi)

4. Kurtosis

µ4 =14

N∑

k=1

(zi − µ)4p(zi)− 34)

Metodos Espectrales

Como se indico cuando se estudio la transformada de Fourier, el espectro de Fourier esta idealmenteindicado para describir la direccionalidad de patrones bidimensionales periodicos o casi periodicosde una imagen. Estos patrones de textura global, aunque son facilmente distinguibles como concen-traciones de alta energıa del espectro, generalmente son bastante difıciles de detectar con metodosespaciales a causa de la naturaleza local de estas tecnicas. Aquı se consideran tres caracterısticasdel espectro de Fourier que son utiles para la descripci6n de la textura:

1. picos prominentes del espectro que dan la direccion principal de los patrones de textura,

2. la localizacion de los picos en el plano de frecuencia da el periodo espacial fundamental de lospatrones, y

3. la eliminaci6n de los componentes periodicos mediante el filtrado deja elementos de la imagenno periodicos, que se pueden describir portecnicas estadısticas.

Se recuerda que el espectro de una imagen real es simetrico con respecto al origen, ası pues solo senecesita considerar la mitad del plano de frecuencia.

Por lo tanto, a efectos del analisis, cada patron periodico esta asociado con un solo pico del espectro,en lugar de con dos. La detecci6n e interpretacion de las caracterısticas del espectro que se acabande mencionar se simplifican a veces expresando el espectro en coordenadas polares para produciruna funcion S(r, θ), siendo S la funcion del espectro y r y θ las variables de este sistema decoordenadas. Para cada direccion θ, se puede considerar S(r, θ) como una funcion unidimensionalSθ(r). De forma similar, para cada frecuencia r, Sr(θ) es una funcion unidimensional. AnalizandoSθ(r) para un valor fijo de θ se obtiene el comportamiento del espectro (tal como la presencia depicos) a lo largo de una direccion radial desde el origen, mientras que analizando Sr(θ) para unvalor fijo de r se obtiene el comportamiento a lo largo de un cırculo centrado en el origen.


Figura 6.27: Imagen con textura periodica, y su espectro de Fourier.

Una descripcion mas global se obtiene integrando (sumando variables discretas) estas funciones:

S(r) =π∑

θ=0

Sθ(r)

S(θ) =R∑

r=1Sr(θ)

siendo R el radio de un circulo centrado en el origen. Para un espectro N × N , R se escogenormalmente como N/2. Los resultados de las ecuaciones anteriores constituyen un par de valoresS(r), S(θ) para cada par de coordenadas (r, θ). Variando estas coordenadas se pueden generar dosfunciones unidimensionales, S(r) y S(θ), que constituyen una descripcion de la energıa espectral dela textura para una imagen o region completa. Mas aun, los mismos descriptores de estas funcionesse pueden calcular para caracterizar su comportamiento cuantitativamente. Los descriptores quenormalmente se utilizan para este fin son la localizacion del valor maximo, de la media y la varianzade la amplitud y de las variaciones axiales, y la distancia entre los valores maximo y medio de lafuncion.

Las figuras 6.27 y 6.28 muestran una imagen y su correspondiente analisis por esta tecnica.

6.3.8 Momentos

Para una funcion continua bidimensional f(x, y), el momento de orden (p + q) esta definido por,

mpq =

∞∫

−∞

∞∫

−∞xpyqf(x, y)dxdy

El teorema de unicidad establece que si f(x, y) es parcialmente continua y tiene valores diferentesde cero solamente en una parte finita del plano x − −y, existen momentos de todos los ordenes y


Figura 6.28: Diagrama de S(r) y de S(θ).

la secuencia de momentos esta determinada especialmente por f(x, y). A la inversa, los momentosmpq determinan especialmente f(x, y). Los momentos centrales se pueden expresar como,

µpq =

∞∫

−∞

∞∫

−∞(x− x)p(y − y)qf(x, y)dxdy

donde,

x =m10

m00y =

m01

m00

Para una imagen digital, las ecuaciones continuas anteriores se convierten en,

µpq =∑

x

∑y

(x− x)p(y − y)qf(x, y)

Algunos momentos centrales son,

µ10 =∑

x

∑y

(x− x)1(y − y)0f(x, y) = m10 − m10

m00(m00) = 0

µ11 =∑

x

∑y

(x− x)1(y − y)1f(x, y) = m11 − m10m01

m00

En resumen:


Figura 6.29: Ecuaciones de los momentos invariantes.

µ00 = m00 µ11 = m11 − ym10

µ10 = 0 µ30 = m30 − 3xm20 + 2m10x2

µ01 = 0 µ12 = m12 − 2ym11 − xm02 + 2y2m10

µ20 = m20 − xm10 µ21 = m21 − 2xm11 − ym20 + 2x2m01

µ02 = m02 − ym01 µ03 = m03 − 3ym02 + 2y2m01

Los momentos centrales normalizados se definen como,

ηpq =µpq

µγ00

γ =p + q

2+ 1 p, q = 2, 3, . . .

De los momentos centrales normalizados segundo y tercero se pueden derivar un conjunto de 7momentos invariantes a la rotacion, traslacion y cambio de escala que se muestran en la figura6.29.

6.4 Morfologıa

La palabra morfologıa indica normalmente una rama de la biologıa que trata de la forma y es-tructura de animales y plantas. Se utilizara aquı la misma palabra en el contexto de morfologıamatematica como una herramienta para extraer componentes de una imagen que sean utiles en larepresentacion y descripcion de la forma de una region, tales como contornos, esqueletos y cercoconvexo. Tambien son de interes las tecnicas morfologicas para el pre o postprocesado, tales comeel filtrado morfologico, la reduccion y el recortado. El lenguaje de la morfologıa matematica esla teorıa de conjuntos. Como tal, la morfologıa ofrece un metodo poderoso y unico de abordar

6.4. MORFOLOGIA 235

numerosos problemas del procesado de imagenes. Los conjuntos en la morfologıa matematica rep-resentan las formas de los objetos de una imagen. Por ejemplo, el conjunto de todos los pixelesnegros de una imagen binaria es una descripcion completa de ella. En imagenes binarias, los con-juntos en cuestion son miembros del espacio bidimensional entero Z2, donde cada elemento deun conjunto es una dupla cuyas coordenadas son las coordenadas (x, y) de un pixel negro (porconvencion) de una imagen.

Las imagenes digitales de escala de grises se pueden representar como conjuntos cuyos componentesestan en Z3. En este caso, dos componentes de cada elemento del conjunto hacen referencia a lascoordenadas de un pixel, y el tercero corresponde a su valor de intensidad discreta. Los conjuntosde espacios de dimensiones mayores pueden contener otros atributos de imagen, tales come colory componentes variables con el tiempo. En las siguientes secciones se desarrollaran e ilustraranvarias conceptos importantes en morfologıa matematica. Aunque ya se presentaron conceptos talescome el esqueleto y el contorno de una region, se volveran a ver aquı como casos especiales deun conjunto mucho mayor de operaciones morfologicas. Muchas de estas operaciones se puedenformular en terminos del espacio euclideo n-dimensional, En. Sin embargo, aquı nos centraremosen imagenes binarias cuyos componentes son elementos de Z2. Tambien se pueden definir lasoperaciones basicas de la morfologıa matematica para imagenes de escala de grises.

6.4.1 Definiciones basicas

Sean A y B conjuntos de Z2, con componentes a = (a1, a2) y b = (b1, b2).

Se define la traslacion de A por x = (x1, x2), representada por (A)x, como,

(A)x = {c/c = a + x, para a ∈ A}

La figura 6.30 muestra el concepto de traslacion de un conjunto.

La reflexion de B, representada por Br, se define como,

Br = {x/x = −b, para b ∈ B}

La figura 6.31 muestra la reflexion de un conjunto.

El complemento del conjunto A se define como,

Ac = {x/x /∈ A}

La diferencia entre dos conjuntos A y B por,

A−B = {x/x ∈ A, x /∈ B} = A ∩Bc

La figura 6.32 muestra el complemento y la diferencia entre dos conjuntos.


Figura 6.30: Traslacion.

Figura 6.31: Reflexion.

6.4. MORFOLOGIA 237

Figura 6.32: Conjunto, Complemento y Diferencia.

6.4.2 Dilatacion

Con A y B como conjuntos de Z2 y φ representando el conjunto vacıo, la dilatacion de A por B sedefine como,

A⊕B = {x/(Br)x ∩A 6= φ}

La dilatacion de A por B es entonces el conjunto de todos los desplazamientos x tales que Br y Ase solapen en al menos un elemento distinto de cero. Otra definicion equivalente de la Dilataciones,

A⊕B = {x/ [(Br)x ∩A] ⊆ A}

Al conjunto B se lo conoce normalmente como el elemento de estructura de la dilatacion, al igualque en otras operaciones morfologicas. La figura 6.33 muestra el proceso de la dilatacion.

6.4.3 Erosion

Con A y B como conjuntos de Z2, la erosion de A por B se define como,

AªB = {x/(B)x ⊆ A}

La erosion de A por B es entonces el conjunto de todos los desplazamientos x tales que B, trasladadopor x esta contenido en A. La figura 6.34 muestra el proceso de la erosion.

La Dilatacion y la erosion son duales entre sı con respecto a los conjuntos complemento y reflexion,es decir,


Figura 6.33: Proceso de Dilatacion .

Figura 6.34: Proceso de Erosion.

(AªB)c = Ac ⊕Br

6.4.4 Apertura y Cierre

Como se ha estudiado la dilatacion expande una imagen y la erosion la contrae. Otras dos im-portantes operaciones morfologicas son la Apertura (Openning) y Cierre (Closing). La aperturageneralmente suaviza el contorno de una imagen, rompe istmos estrechos y elimina protuberanciasdelgadas. El cierre tambien tiende a suavizar secciones de contorno, pero, en oposicion a la aper-tura, generalmente fusiona separaciones estrechas y entrantes delgados y profundos, elimina huecospequenos y rellena agujeros del contorno.

La Apertura de un conjunto A por un elemento de estructura B se define como:

6.4. MORFOLOGIA 239

Figura 6.35: Conjunto A.

Figura 6.36: Apertura de A por B.

A ◦B = (AªB)⊕B

El Cierre de un conjunto A por un elemento de estructura B, se define por:

A •B = (A⊕B)ªB

La figura 6.35 muestra un objeto y la figura 6.36 el proceso de apertura, ademas la figura 6.37 y6.38 muestra la imagen del objeto original y el proceso de cierre. Hay que tener en cuenta la formadel elemento de estructura utilizado en estos ejemplos.

Propiedades de la Apertura y del Cierre

La Apertura satisface las siguientes propiedades:

• A ◦B es un subconjunto de A.


Figura 6.37: Conjunto A.

Figura 6.38: Cierre de A por B.

6.4. MORFOLOGIA 241

Figura 6.39: Filtro morfologico. (A ◦B) •B.

• Si C es un subconjunto de D, entonces C ◦D es un subconjunto de D ◦B.

• (A ◦B) ◦B = A ◦B.

El Cierre satisface las siguientes propiedades:

• A es un subconjunto de A •B.

• Si C es un subconjunto de D, entonces C •D es un subconjunto de D •B.

• (A •B) •B = A •B.

6.4.5 Filtros Morfologicos

Una aplicacion de las operaciones de apertura y cierre son los filtros morfologicos, como se muestraen la figura 6.39.

6.4.6 Transformacion al azar

La transformacion al azar es una herramienta basica para la deteccion de formas. El objetivo dela aplicacion de esta transformacion consiste en encontrar la posicion de una forma, X cualquieraen una imagen. La figura 6.40 muestra una imagen con varios objetos. Las imagenes de las figuras6.41, 6.42 y 6.43 explican este proceso.

Se define el conjunto de concordancias de B(X) en A por,

A⊗B = (AªX) ∩ [Ac ª (W −X)]

Se puede generalizar el concepto haciendo que B = (B1, B2), donde B1 es el conjunto formado porB asociados con un objeto y B2 asociados con el fondo. Entonces, B1 = X y B2 = W −X.


Figura 6.40: Imagen para la aplicacion de la transformacion al azar.

Figura 6.41: Erosion de la imagen con AªX.

Figura 6.42: Erosion de la imagen con Ac ª (W −X).

6.4. MORFOLOGIA 243

Figura 6.43: Resultado de la interseccion de las dos imagenes anteriosres.

Figura 6.44: Ejemplo de la extraccion de Contornos.

Entonces se puede escribir,

A⊗B = (AªB1) ∩ (Ac ªB2)A⊗B = (AªB1) ∩ (A⊕Br2)

6.4.7 Algoritmos Morfologicos Basicos

Extraccion de Contornos

El contorno de una region A se puede obtener con la eleccion del elemento de estructura B con laecuacion,

β(A) = A− (AªB)

la figura 6.44 muestra una imagen y la extraccion de contornos realizada por este metodo.


Esqueleto

Se puede obtener el esqueleto de una region aplicando la ecuacion,

S(A) =K⋃

k=0

Sk(A)

Sk(A) = {(Aª kB)− [(Aª kB) ◦B]}

Reduccion

La reduccion de A por el elemento de estructura B se define,

A− (A⊗B) = A ∩ (A⊗B)2

{B} ={B1, B2, . . . , Bn

}

Otra forma es, suponga una secuencia, donde Bi es una version girada de Bi−1. Se obtiene lareduccion mediante,

((. . .

((A red B1

)red B2

). . .

)red Bn

)

Engrosamiento

El engrosamiento (dual de la reduccion) se puede calcular como,

A ∪ (A⊗B)2

o,

((. . .

((A eng B1

)eng B2

). . .

)eng Bn

)

Ejemplos de operaciones morfologicas

La figura 6.45 muestra una imagen y el resultado de la dilatacion. La figura 6.46 demuestra el usode la dilatacion en una imagen contaminada con ruido sal y pimienta.

La imagen de la figura 6.47 muestra una extraccion de contornos realizada en base al metododescripto en parrafos anteriores.

En las figuras 6.48, 6.49 y 6.50 se ejemplifica la erosion.

6.4. MORFOLOGIA 245

Figura 6.45: Imagen de un cudrado y su dilatacion.

Figura 6.46: Imagen con ruido sal y pimienta, imagen dilatada.


Figura 6.47: Imagen Original e Imagen con la extraccion de contorno realizada en base a la dilat-acion.

Figura 6.48: Imagen Original y erosionada.

Figura 6.49: Imagen Original, umbral=90 y erosionada.

6.4. MORFOLOGIA 247

Figura 6.50: Imagen Original y erosionada.

Los ejemplos de la apertura se observan en la figura 6.51, 6.52 y 6.53, mientras que las imagenesde las figuras 6.54 y 6.55 demuestran la utilizacion del operador de cierre.

La ultima figura 6.56 es una ejemplo del operador de reduccion.


Figura 6.51: Imagen original. Imagen de apertura para separar las lıneas de los cırculos.

Figura 6.52: Imagen original y la aplicacion del operador apertura.

6.4. MORFOLOGIA 249

Figura 6.53: Imagen Original, unmbralizada T=210 y aplicacion operador apertura.

Figura 6.54: Imagen original y aplicacion del operador de cierre.

Figura 6.55: Imagen original, umbralizada, operador cierre, esqueleto.


Figura 6.56: Imagen original, t=60 y reduccion.

Documents

Representaci¶on y Descripci¶ondea.unsj.edu.ar/imagenes/recursos/capitulo6.pdf · una curva cerrada, la aproximaci¶on es exacta cuando el numero¶ de lados del pol¶‡gono es igual