Download Extracción de bordes de imágenes digitales a través del análisis

Extracción de Bordes de
Imágenes Digitales a Través
del Análisis Multifractal
Duffaut, E. L. A. i ,2, Posadas, D. A.1 y Quiroz, R.1
1
Centro Internacional de la Papa,
División de Manejo de Recursos Naturales
PO Box 1558, Lima 12.
2
Pontificia Universidad Católica del Perú,
Escuela de Graduados
RESUMEN
La extracción de información de
una imagen siempre ha sido un tema de
gran importancia práctica tanto en física
como en las ciencias aplicadas. En los
últimos años, al gran avance
tecnológico de la informática ha
permitido un gran salto en el desarrollo
de técnicas dedicadas al análisis de
imágenes. Así, en el presente trabajo
desarrollamos un método para el
análisis y extracción de los bordes de
una imagen digitalizada basado en la
teoría multifractal, técnica aun muy
poco usada en la literatura para el
análisis de imágenes. A diferencia de
los métodos clásicos, la técnica
multifractal asocia la imagen a un
conjunto de medidas relacionadas a su
intensidad de niveles de gris en cada
píxel, los cuales a su vez, son
caracterizados por un coeficiente
denominado de Holder indicador de la
singularidad de un elemento de la
imagen. En este contexto son
introducidos parámetros de medidas
como “sum”, “max”, “min”, e “iso”,
que cuantifican la singularidad en torno
a un punto de la imagen, obteniendo
información del comportamiento local
de la medida perteneciente al borde que
se quiere extraer. De esta forma el
proceso es capaz de detectar y extraer
los bordes de una imagen en una forma
mucho mas robusta que los métodos
tradicionales. Son presentados ejemplos
de aplicaciones donde se muestra la
robustez del método con relación a los
métodos mas comúnmente utilizados.
Palabras Clave:
Multifractales, Coeficiente de Holder,
Dimensión Fractal, Box-counting,
Medidas (Capacidades)
I. INTRODUCCIÓN
La extracción de información de
una imagen siempre ha sido un tema de
suma importancia en el campo de la
Física por el fácil manejo de una
imagen, su bajo costo y en los últimos
años, por el avance tecnológico de la
informática. El campo de aplicaciones
del análisis de imágenes es muy amplio
cubriendo áreas como la medicina,
agricultura y medio ambiente, robótica,
sensoramiento remoto, biología y otros.
Una aplicación importante del análisis
de imágenes es la segmentación de una
imagen que consiste en obtener una
descripción concreta en términos de sus
bordes y/o regiones. Esto significa
identificar las características que
describen tanto los contornos (detección
de bordes) como las regiones donde
ellos se concentran (extracción de
regiones). Estas dos aproximaciones son
duales pero sus algoritmos de
identificación son muy diferentes y
desgraciadamente la mayoría de veces
lleva a resultados diferentes
de
segmentación. Los métodos clásicos de
segmentación de imágenes usualmente
asumen los bordes como los extremos
locales del gradiente de los niveles de
gris, los cuales introducen dificultades
en su detección debido al ruido
introducido por la cámara, el muestreo o
los mismos objetos que componen la
imagen.
Estas
dificultades
de
segmentación se genera básicamente
por el hecho de usar operadores
matemáticos definidos en el dominio de
las funciones continuas y extrapoladas a
funciones discretas de una imagen
(Levy and Berroir, 1993). En los
últimos años nuevas técnicas de
procesamiento se han introducido, como
los métodos basados en la teoría de
wavelets (Prasad and Iyengar, 1997) y
multifractales (Guiheneuf and Levy,
1996). En el presente trabajo
se
investiga la potencialidad del método
multifractal para la segmentación de
imágenes.
cada píxel de la imagen (Chhabra, et al.,
1989).
II. FENOMENO MULTIFRACTAL
La geometría fractal fue propuesta en
los años setenta y ganó aceptación
inmediata en diversas áreas científicas
debido a su flexibilidad para describir
las formas irregulares encontradas en la
naturaleza (Mandelbrot, 1982, Feder,
1988; Gouyet, 1996). Esta situación,
también observada en otros campos
científicos, llevó a definir los llamados
“fractales
estadísticos”
en
contraposición
a
los
“fractales
matemáticos”. Los primeros son
estadísticamente
válidos
en
un
determinado rango de escalas, mientras
que los “fractales matemáticos” son
exactos y válidos en todas las escalas de
definición (Bicsek, 1992).
El simple conocimiento de la dimensión
fractal de un objeto es insuficiente para
caracterizar su geometría, así como
también cualquier propiedad física
inherente a dicho objeto. La dimensión
fractal describe objetos uniformes o
sistemas homogéneos, pero no ofrece
información alguna a cerca de las bajas
o altas distribuciones irregulares dentro
del sistema. Por ejemplo, el método
fractal no hace distinción entre los dos
cuadrados que se muestran en la figura
1, a pesar de la notable diferencia en la
proporción de negro que cada uno de
ellos contiene. Con la finalidad de
obtener información de este tipo, una
generalización del concepto, “Los
Multifractales”, deberá ser usado.
El concepto de multifractales contempla
un número infinito de dimensiones
fractales y por lo tanto puede ser más
apropiado para la descripción de
propiedades físicas. Un proceso
multifractal se caracteriza por eventos
extremos y más o menos aislados,
asociados a una medida μ que
representa la “materia” contenida en
δ1
δn
Figura 1 peso de la medida de una caja
A pesar de las ventajas conceptuales y
de una mayor flexibilidad en el análisis,
la técnica multifractal no ha sido
aplicado intensivamente para el
procesamiento
imágenes
digitales,
posiblemente debido a la complejidad
matemática que ella representa y las
limitaciones computacionales.
III. DEFINICIÓN DE MEDIDA Y
EXPONENTE DE HOLDER
El principal motivo por el que se
justifica
la
introducción
de
multifractales en el análisis de imágenes
es que la dimensión fractal es una
herramienta excelente para caracterizar
la irregularidad de una curva o una
superficie. Comúnmente se asume que
una imagen (2D) puede ser vista como
una superficie 3D, o equivalentemente
los niveles de gris pueden asumirse
como una coordenada en el eje Z. Así,
se introducirá la definición de una
medida sobre una región asociada a una
función discreta de niveles de gris lo
cual nos permitirá usar técnicas
fractales
para
resolver
algunos
problemas específicos. En este contexto
son introducidos parámetros de medidas
como “sum”, “max”, “min”, e “iso”,
sobre una región Ω perteneciente al
conjunto de escenas de la imagen
(Levy and Berroir, 1993). Si Ω’ es el
subconjunto de Ω donde la intensidad
de los niveles de gris p(i) definido en
cada píxel i es diferente de cero, se
define:
μmax(Ω)=maxi∈Ωp(i)
μmin(Ω)=mini∈Ω’p(i)
La medida “iso” depende de una
discretización de niveles de gris tal que:
pδ(i) = pδ (j) ⇔ ⏐p(i)-p(j)⏐< δ
Si G(Ω) es el centro geométrico de Ω,
entonces se define:
μ iso (Ω) = Card {i ∈ Ω / p δ (i ) = p δ ( j )}
Veremos que los exponentes dados por
las diferentes medidas dan diferente
información sobre las singularidades
encontradas: αmáx. y αmin. que solo
dependen del peso de la singularidad,
αiso solo depende de la forma de
singularidad, y αsum depende de ambas
características (peso y forma), siendo el
parámetro de singularidad α el
exponente de Holder, definido como:
α=
log(μ (box))
log ε
De este modo el exponente α
corresponde a la dimensión fractal de la
medida. Para una clase grande de
multifractales el valor de α está
restringido a un intervalo [αmin, αmax],
donde 0 < αmin < αmax < ∞. Este valor,
para una señal unidimensional (1D,
teniendo medida μ ) está próximo de 1,
y para 2D (imágenes) esta cerca de 2.
Si establecemos una distribución de
frecuencias de este parámetro α en toda
la imagen, para cada valor de α, se
evalúa el numero de cajas Nε (α) de
tamaño ε teniendo exponente de Holder
α. Desde que el número total de cajas
de tamaño ε es proporcional a ε−DE
donde DE es la dimensión euclidiana de
la caja, la probabilidad de tener el valor
α es
pε = Nε(α) / ε−DE
Desde que ε →0, es apropiado
considerar la función:
log N ε (α )
,
f ε (α ) =
log ε
para el cual existe un limite bien
definido f(α) .
Esto significa que, para cada α y ε
decreciente, el número de cajas aumenta
como: Nε (α)≈ ε−f (α).
El exponente f(α) es una función
continua de α. En muchos casos la
gráfica de f(α) es de forma parabólica,
con un máximo cerca de α = 1 (para
señales 1D), o cerca de α = 2 (para
señales 2D). Los valores de f(α) son
interpretados como una dimensión
fractal generalizada denominada de
espectro multifractal (Bicsek, 1992).
Existen varios métodos para obtener la
función f(α), en este trabajo es usado el
método de Box-counting descrito en la
sección IV. La clasificación del
espectros f(α), usado para el análisis de
imágenes fue introducida por LevyVehel and Berroir (1993). El valor de
α es asociado a la información LOCAL
de la regularidad de un punto en la
imagen, pues la medida μ hace que cada
píxel de la imagen sea caracterizado por
un valor propio de α. Por ejemplo,
puntos de la imagen con α ≡ 2 son
regiones donde la medida es regular y la
probabilidad de cambios en la señal es
pequeña. Puntos con α ≠ 2 denotan
regiones donde "algo ocurre" y son
consideradas zonas poco regulares. Así,
puntos con α << 2 o α >> 2 denotan
regiones caracterizadas por un gradiente
muy alto o discontinuidades de la señal.
IV. METODO DE HISTOGRAMA
(BOX-COUNTING)
Una de las diferentes versiones del
cálculo numérico de la dimensión
fractal es la llamada de box-counting
que se relaciona con el concepto de
estructura auto-similar. La metodología
consiste en sobreponer a la estructura a
ser analizada una rejilla con una malla
de
tamaños,
ε
formando
un
recubrimiento de cajas. El número de
cajas que contienen valores de la
estructura a caracterizar es Nε(α), el
cual varia con el valor de ε escogido.
Figura (2) Método de "box-counting" cubrimientos a
diferentes escalas
Para realizar el correspondiente calculo
de la dimensión fractal se procede a
contar el número de cajas Nε(α) a
diferentes escalas (figura (2)), la
variación de escala de un paso al
siguiente es dependiente del tamaño de
la imagen y de los múltiplos de ese
tamaño. El valor de la dimensión
corresponde a la pendiente de la
representación log(Nε(α)) Vs. log(ε)
(figura (3)).
Figura (3). Método de "box-counting" Regresión
log(Nε(α)) vs. Log(ε)
La gran ventaja de esta metodología es
el hecho de aplicarse en forma
sistemática por su simplicidad en la
creación del recubrimiento de cajas y el
correspondiente recuento, que se
efectúa rápidamente, inclusive para
imágenes de alta resolución (Bicsek,
1992).
El método box-counting se aplica
dividiendo el lado L de la imagen en s
cajas de igual tamaño (s=L/ε). Estas
varían desde la dimensión máxima
posible del lado L hasta la unidad
mínima de la imagen que corresponde a
un píxel. Para cada uno de estos valores
de s se realiza un recubrimiento de toda
la imagen con una disposición regular
de cajas de lado δi =L/s, R(δ). Con el
recuento de cajas que contienen algún
valor de α en su interior se obtiene el
valor de Nε(α).
La representación log(Nε(α)) Vs.
log(L/ε) que caracteriza a cada conjunto
de α’s, y si los puntos aparecen
alineados obtenemos la dimensión
fractal característica que corresponde a
la pendiente de la recta de regresión que
pasa por los puntos representativos del
rango
de
escalas
consideradas.
Obviamente las pendientes asociadas a
puntos aislados o a rectas en un plano
corresponden a los valores Euclideos de
0 o 1. Si el conjunto es lo
suficientemente denso para cubrir
totalmente el plano de la imagen a las
distintas escalas estudiadas εi, entonces
el valor de la dimensión es 2.
IV. PROCEDIMIENTO Y ANALISIS
Como estamos interesados en extraer los
bordes de una imagen usando la técnica
multifractal y mostrar su potencialidad,
escogimos una imagen con cierto grado de
complejidad en su procesamiento. Se trata
de una imagen correspondiente a una
distribución
de
pelos
de
alpaca
pertenecientes a una determinada región del
camélido (figura 7).
Inicialmente transformamos la imagen a
escala de grises y luego caracterizamos la
imagen con las medidas mencionadas
anteriormente (figuras (10), (11), (12), (13))
las cuales formaran grupos dentro de la
imagen. Con estos grupos se obtiene un
rango de valores de α’s los cuales son
agrupados convenientemente y a cada
grupo se le calcula su respectiva dimensión
de box-counting para una posterior
segmentación de la imagen (figuras(14)). El
hecho de agruparlos en rangos de valores de
α’s es la razón por la que se le conoce, a
este
método,
como
“método
del
histograma”(Chhabra, et al, 1989).
Como una comparación se muestra la
respuesta de esta técnica al ruido de tipo
uniforme (figuras (4), (5) y (6)) comparado,
por ejemplo, al método de detector de
canny mas ampliamente usado.
figura (7) Imagen de microscopia láser de una muestra de
pelo de alpaca
V. RESULTADOS
A continuación mostramos algunos
resultados, por ejemplo, la figura 4 muestra
como el detector reacciona frente a un ruido
uniforme en comparación al detector de
bordes de Canny (figuras (5). Con varios
niveles de detección obtenemos un mejor
resultado (figura (7) medida Iso y posterior
segmentación con respecto a las
dimensiones cercanas a 1.
figura (8) Imagen Binarizada usando método de Otsu
(izquierda), detección de bordes detector de Canny
figura (4) ruido uniforme (Izquierda) espectro multifractal
(Derecha)
figura (5) Detector con filtro Canny 0.3 (Izquierda), 1.0
(Medio), 1.9 (Derecha)
figura (6) Puntos con f(alfa) cercano a 1
Se muestra también la detección y
extracción de Bordes de la figura(7)
(500x400 píxeles RGB) y se compara
con métodos usados comúnmente como
el de threshold usando el método de
OTSU y el método de Canny mostrada
en la figura(8). También se quiso
mostrar como era la detección con
respecto a softwares más comerciales
(figura(9)) como lo son el de
PHOTOSHOP y el COREL DRAW.
figura (9) Imágenes de bordes usando diversos métodos de
detección de bordes implementados en Photoshop y Corel
Draw
En las figuras 10,11,12,13 se muestran
las imágenes de las características
extraídas usando las medidas SUM,
ISO, MAX y MIN mostrando también
sus respectivos espectros multifractales.
Finalmente vemos como una simple
binarización de las dimensiones de cada
grupo nos muestra una imagen de
bordes bien definida según sea la
medida, en la figura 14 mostramos los
resultados más aceptables.
dimensión medida ‘min’ segmentada con dimensiones
cercanas a 1 (derecha)
VI. CONCLUSIONES
Dependiendo del tipo de medida usada,
la detección no es muy afectada por la
presencia de ruido uniforme.
figura (10) imagen de alfas medida ‘sum’ (izquierda),
espectro multifractal
Podemos destacar que la técnica
multifractal se basa solo en la
característica de que una línea tiene
dimensión 1 por eso es un buen detector
Se observa también que la imagen
analizada ha sido adquirida con una
inadecuada iluminación que afecta a
cualquier proceso que se le quiera
realizar, pero que la técnica Multifractal
no es afectada por este defecto en la
toma de la imagen.
figura (11) imagen de alfas medida ‘Iso’ (izquierda),
espectro multifractal
figura (12) imagen de alfas medida ‘Max’ (izquierda),
espectro multifractal
La medida MIN nos ha destacado las
hebras mas definidas y que están mas
por encima, en cambio la SUM nos
destaca casi todas, siendo esta la que
nos dio mejor resultado.
En comparación con los otros métodos
la técnica multifractal proporciona
resultados notoriamente mejores, como
se observa al comparar las figuras 8 y 9
con la figura 14 en la cual, según sea la
medida, podemos destacar todas las
hebras o solo las que no están borrosas.
VII. BIBLIOGRAFIA
figura (13) imagen de alfas medida ‘Min’ (izquierda),
espectro multifractal
[1] Introduction to the Multifractal Analysis of Images
Jacques Lévy Véhel
In Fractal Image Encoding and Analysis, 1998.
Book Chapter
[2] Multifractal Segmentation of Images
Jacques Lévy Véhel and Pascal Mignot
In Fractals, Vol. 2, Issue No. 3, pp. 371-378, June, 1994.
Refereed Journal Article
figura (14) Imagen de dimensión medida ‘sum’ segmentada
con dimensiones cercanas a 1(izquierda), imagen de
[3] Multifractal Analysis of Choquet Capacities: Preliminary
Results
Jacques Lévy Véhel and Robert Vojak
In Advances in Applied Mathematics, Vol. 20, No. 1, pp.
1-43, January, 1998.
Refereed Journal Article
[4] Fractal Approaches in Signal Processing
Jacques Lévy Véhel
In Fractal Geometry and Analysis, The Mandelbrot
Festschrift, Curacao. C.J.G. Evertsz,
[5] H.-O. Peitgen & R.F. Voss Editors, World Scientific,
1996., 1995.
Book Chapter