Normalmente, las texturas se caracterizan por una función o por un vector de características. Aquí vamos a presentar un método para caracterizar texturas, basado en las propiedades topológicas de los diferentes niveles de gris y de las distintas resoluciones.

Se usará una estructura de datos llamada MRCG(Multi Resolution Cluster Graphs). Esta estructura está formada por una secuencia de grafos denotados por {Ns(t)}s e I. En la que dados s y t, Ns(t) se define como el número de componentes conexas formadas por al menos s píxeles, para una imagen binarizada con umbral t.

La secuencia de grafos no se calcula exhaustivamente, pero los píxeles de la imagen re recorren linealmente. En el peor de los casos, la complejidad en tiempo para crear la secuencia completa de grafos es casi lineal. Exactamente es de O(a(n,n) n), donde n es el número de píxeles de la imagen y a(n,n) es la inversa de la función de Ackerman.

La estructura {Ns(t)}s e I es una representación multinivel de la imagen donde el parámetro s controla la resolución.

En este estudio consideraremos que un píxel es vecino de otro si entre ellos existe u una relación de 4-vecindad.

Vecino

Figura 1. Representación de la 4-vecindad

Este documento está estructurado de la siguiente manera: en el apartado 2 se expone una idea general de este método, en el apartado 3 hay una breve descripción del trabajo previo, en el apartado 4 se describe la estructura de datos {Ns(t)}s e I. En el apartado 5 se discuten las propiedades más relevantes de este caracterizador de texturas. El apartado 6 contiene resultados experimentales, en el apartado 7 se muestra el código del programa, en el 8 un breve manual de usuario y en el apartado 9 se recogen las conclusiones. Se añade también un anexo con un test de 10 preguntas referentes al trabajo realizado.

2. IDEA GENERAL

La idea de este nuevo enfoque para caracterizar texturas consiste en lo siguiente:

Esquema Dada una imagen en niveles de grises, calcularemos su histograma y a partir de él haremos binarizaciones con distintos valores umbrales. El estudio de las componentes conexas de las imágenes binarizadas nos dirá si se trata de una imagen muy granulosa, granulosa o poco granulosa. Si el número de componentes conexas cambia rápidamente cuando tomamos valores umbrales cercanos, estaremos frente a una imagen muy granulosa, si por el contrario el número de componentes conexas no varía al ir cogiendo distintos valores umbrales cercanos, pero varía cuando cogemos valores umbrales muy lejanos querrá decir que la imagen es poco granulosa.

Figura 2. Esquema de la idea general

3. TRABAJO PREVIO

Las características más sencillas de las texturas son las estadísticas de primer orden extraídas del histograma. Otras características más fiables son aquellas estadísticas que contienen información espacial y que no se obtienen a partir del histograma. Estamos hablando del método de la diferencia de los niveles de gris (GLMD).

Como estos, existen multitud de métodos para caracterizar texturas, algunos de ellos son:

Análisis de Wavelets.

Caracterización de texturas según el área de la imagen.

Cálculo de las 5 características del histograma.

Gray Level Run Lengths.

Markov Random Field.

...

4. LA ESTRUCTURA DE DATOS {Ns(t)}s e I

Sea I la imagen de entrada y sea It la imagen resultante de binarizar la imagen I con un umbral t.

Se define {Ns(t)}s e S como el conjunto de Ns(t), donde:

Ns(t) es el número de componentes conexas con un tamaño de al menos s píxeles en una imagen binarizada con umbral t.

t e [0, 255]

s se toma de un conjunto de valores de resoluciones R.

Método MRCG

Figura 3. Obtención del MRCG a partir de la imagen binarizada

En el peor de los casos la secuencia de grafos {Ns(t)}s e S puede ser calculada en O(a(n,n). | T | . | R | . n), donde:

a(n,n) es la inversa de la función de Ackerman y es casi constante

| T | es independiente del tamaño de entrada de la imagen

| R | es prácticamente una constante

n es el número de píxeles de la imagen

Por tanto podemos decir que la complejidad del cálculo de {Ns(t)}s e S es lineal.

4.1. Cálculo de los grafos Ns(t)

A continuación expondremos los pasos que hay que seguir.

Para cada tamaño s hay que construir el grafo de la función Ns(t). Por tanto para cada valor umbral t, el número de objetos de tamaño s tendrá que ser calculado. Denotaremos por It la imagen resultante de binarizar la imagen de entrada con un umbral t. Cada píxel de It será blanco o negro dependiendo del valor del píxel correspondiente en la imagen de entrada, si el nivel de gris es menor que el umbral será negro, en otro caso será blanco. Es fácil de ver que los píxeles negros de It+1 serán también píxeles negros en It. Por tanto el cálculo de Ns(t+1) se basa en los cálculos hechos para Ns(t).

Sea m el número de niveles de gris (en nuestro caso 256) y n el número de píxeles de la imagen de entrada, la construcción del grafo Ns(t) se hace de la siguiente manera:

a) Construir una lista L de n píxeles y un array idx de tamaño m, tal que idx(i) sea el índice del primer elemento de L con nivel de gris i.

Lista L

Figura 4. Representación de los Arrays L e idx.

b) Definir una estructura en la que inicialmente cada píxel sea un conjunto disjunto.

c) Contar el número de objetos. Para ello inicializaremos la cuenta a cero y recorreremos la lista L. Sea t el nivel de gris del píxel p, uniremos p con cada uno de sus vecinos(4-adyacentes) si el nivel de gris del vecino de p no es mayor que t. Si la unión se lleva a cabo actualizaremos el número de Ns(t) de la siguiente manera:

Sean s1 y s2 los tamaños de los dos conjuntos que voy a unir. Si s1 y s2 son menores que s, y s1+s2>=s entonces tenemos un nuevo objeto, por tanto incrementamos la cuenta.

Pero si s1 y s2 no son menores que s entonces decrementamos en uno la cuenta.

El valor de Ns(t) será el resultante después de procesar el último píxel con nivel de gris t.

5. USO DEL MRCG PARA CARACTERIZAR TEXTURAS

5.1. Texturas uniformes

Si la imagen de entrada I es una imagen con textura uniforme entonces It (que será la imagen I binarizada), no será más que una imagen de ceros y unos repartidos aleatoriamente donde la probabilidad de que sea un 1 es p(t), y la probabilidad de que sea un 0 es 1- p(t). p(t) es una función monótona creciente y su valor depende de la distribución de la uniformidad. Si la distribución del ruido blanco es uniforme en el intervalo [tmin,tmax] entonces podemos definir p(t) como:

Función p(t)

Para comprender mejor el significado del Ns(t) vamos a ver el caso unidimensional. Para el caso unidimensional, la imagen uniforme es una secuencia binaria aleatoria con una probabilidad p(t) de que sea “1” y una probabilidad 1-p(t) de que sea “0”. En este caso una componente conexa es una secuencia de unos rodeado de ceros. El número de componentes conexas para cualquier tamaño de s será N1(t). Cada componente conexa tiene exactamente una ocurrencia de “10”, excepto la última componente. Por tanto, dado un número de n bits, el número de ocurrencias de “10” será el número de componentes conexas con una desviación de 1 como mucho. Y la probabilidad de ser “10” es de p*q.

Figura 5. Representación del caso unidimensional

De este razonamiento podemos sacar la siguiente proposición:

Proposición 1:

Dada una imagen unidimensional, uniforme, con probabilidad p de que un píxel sea negro, el valor de Ns(t) viene dado por la expresión: (n-s-1) p^sq.

El caso de dos dimensiones es más complicado, pero se intentará explicarlo de la forma más clara posible. Sea ES una componente conexa de s píxeles. Diremos que ES le ocurre al píxel x si x es el píxel más a la derecha y más abajo de entre todos los píxeles de la columna de x. La probabilidad de que ES le ocurra a algún píxel x viene dada por p^sq^rdonde r es el número de píxeles del perímetro. Veámoslo con un ejemplo:

Para s = 1 r = 4

Figura 6 . Perímetro para un pixel.

Para s=2 r=6

Figura 7. Perímetro para dos píxeles

.

Para s = 3 r = 8

Figura 8. Perímetro para tres píxeles.

Para s = 3 r = 7

Figura 9. Otro perímetro para tres píxeles.

Si nos fijamos, podemos darnos cuenta de que cuando la componente es una línea, r viene dado por r = 2s + 2. Y para valores grandes de s r = ¶s. Denotemos por a_{s, r, i, j}al número de componentes conexas distintas de s píxeles, cuando el píxel más a la derecha y más abajo es el (i, j). Por ejemplo, para i,j >=s, a _1,4= 1, a _2,6= 2, a _3,8= 2, a _3,7= 2, etc. (Ver figura anterior).

Proposición 2:

Para imágenes 2D uniformes, el valor de Ns(t) es una combinación lineal de p^sq^r

5.2. Modelos de filtro

En este apartado se describe la relación de los modelos de filtro con la estructura {Ns(t)}s e S para texturas uniformes.

Un modelo de filtro se define como una cuadrícula o enrejado en el que cada vértice se declara como abierto con una probabilidad p y como vértice cerrado con una probabilidad de 1-p. Podemos establecer las siguientes relaciones entre el modelo de filtros y la estructura Ns(t):

Modelo de filtro	Imagen binaria
vértice abierto	píxel negro
componente conexa abierta	objeto formado por al menos s píxeles

Es decir, que un vértice abierto en el modelo de filtros es equivalente a lo que nosotros hemos llamado píxel negro en una imagen binaria. Y un subgrafo conexo de al menos s vértices abiertos del modelo de filtros se corresponde en una imagen binaria a un objeto formado por al menos s píxeles.

Se define probabilidad crítica como la probabilidad de que dado un vértice pertenezca a una componente abierta. Para el modelo anteriormente definido pc = 0.592764, es decir, que si la probabilidad de que un vértice sea negro es >pc entonces existe una componente conexa en Z2 con probabilidad 1. Esto implica que para valores lo suficientemente grandes de s existe un t' tal que Ns(t)=0 para t <= t'.

5.3. Propiedades del MRCG para texturas

Lo explicado en el apartado anterior también se puede aplicar a texturas más complejas.

5.3.1. Transformaciones de niveles de gris

El comportamiento del MRCG cuando hacemos transformaciones de niveles de gris se recoge en la siguiente proposición:

Proposición: Sea I una imagen de entrada y sea II la imagen obtenida al aplicarle a I la transformación de escala de grises a(t). Si Ns(t) es el MRCG de I entonces el MRCG de II será Ns(a(t)).

Demostración: para cualquier t se cumple que It = IIa(t), es decir, que las imágenes binarizadas son las mismas.

Como la ecualización del histograma es una transformación de escala de grises monótona creciente de la propiedad anterior se obtiene el siguiente corolario:

Corolario: Sean

I: imagen de entrada y II: la imagen ecualizada, entonces MRCG de I y MRCG de II se diferencian en una transformación monótona de t.

Este corolario nos proporciona una herramienta para normalizar texturas como una etapa previa al procesamiento, o sea, que antes de trabajar con las imágenes podremos hacerles un preprocesamiento que consistirá simplemente en una ecualización del histograma.

5.3.2. Alisar / perfilar una imagen

El efecto de alisar una imagen es similar a incrementar el valor del parámetro s. Una componente conexa se corresponde con un valle en la superficie de la imagen que está por debajo del plano binarizado. El tamaño de la componente conexa es el área en el plano binarizado, el cual es cortado por la superficie de la imagen. Los valles que cortan el plano binarizado con un área menor que s no cuentan para el cálculo de Ns(t). Por tanto cortar los valles por debajo de la primera cima que crea una componente conexa de tamaño >=s no tiene efecto alguno sobre el grafo Ns(t).

5.3.3. Características básicas de las texturas

En este apartado examinaremos la influencia que tienen algunas características “clásicas” de texturas sobre el MRCG.

Antes de nada cabe comentar que el MRCG es invariante respecto a la orientación, es decir, que el resultado será el mismo sea cual sea la orientación de la imagen y esto hace que sea un método muy bueno en comparación con otros métodos.

Características de las texturas:

Regularidad: una textura es regular cuando está formada por una repetición de elementos básicos. Cuanto más regular sea una textura más liso será su grafo Ns(t).

Linealidad: si cogemos dos imágenes: I1 y I2, donde I1 está formada por líneas de s' píxeles, I2 está formada por cuadrados de s' píxeles, nos damos cuenta de que al binarizar con umbral t, las imágenes que obtenemos contienen sólo porciones de esas líneas (o cuadrados) esto es porque son imágenes digitales y el nivel de gris de los píxeles de un objeto no es el mismo. Es más fácil romper líneas que cuadrados, por tanto los Ns(t) grafos serán mayores para valores pequeños de s' (y Linealidad al revés).

Figura 10. Ejemplo de una imagen con líneas y su correspondiente binarización.

Densidad: para valores lo suficientemente grandes de s, texturas densas o tupidas implican valores grandes para la función Ns(t). Además los objetos densos se unen más rápidamente.

Falta de finura: una textura poco fina significa grandes componentes conexas en la imagen.

6. RESULTADOS EXPERIMENTALES

En este apartado se presentarán los resultados obtenidos de la comparación de los métodos SGLDM y Fractal signature con el método que estamos estudiando.

Para la obtención de los resultados se tomó un conjunto de 13 imágenes, entre ellas estaban una imagen de corcho, de un tejido, de lana, de lona, e incluso de agua. Cada imagen fue escaneada con una resolución de 75 dpi y 256 niveles de gris. De estas imágenes se tomaron muestras de 128x128. Se aplicó una ecualización a cada una de ellas para neutralizar los efectos de las estadísticas de primer orden, ya que normalmente estas estadísticas son poco fiables. Es importante que nos demos cuenta de que en estas imágenes hay texturas que son diferenciables fácilmente con sólo mirarlas, debido a las diferencias significativas que presentan las estadísticas de primer orden, pero que después de la ecualización del histograma ya no son tan diferenciables. En estos experimentos se caracterizan a las texturas por los valores de sus grafos N₂(t). Se escogió una resolución de tamaño 2 por el siguiente motivo: si ns(t) es el número de componentes conexas de tamaño s exactamente en la imagen binarizada con umbral t, Ns(t)S=n_u(t). Se observa claramente que Ns(t) contiene más información para valores pequeños de s.

Para medir resultados definiremos el concepto de distancia:

La distancia entre dos grafos Ns(t) se define como la suma normalizada de los cuadrados de las diferencias:

D( Ns'(t), Ns''(t) ) = (1/x) S[ Ns'(t) - Ns''(t) ]²,

donde x = max(a, b)², siendo a y b los valores máximos de Ns'(t) y Ns''(t) respectivamente.

Resumiendo los experimentos realizados, comentaré que para los otros métodos se obtenían distancias mayores entre muestras que pertenecían a una misma textura que con el MRCG. Incluso, hubo ocasiones en las que la distancia entre muestras de diferentes texturas era menor que la distancia entre muestras sacadas de la misma textura.

En general podemos decir lo siguiente:

SGLDM

Salen valores más bajos que para el método MRCG.

Es más apropiado para microtexturas.

Las diferencias con el método MRCG son muy acusadas y no son consecuencia de una mala elección de características sino una falta de información en las matrices de co-ocurrencias.

Fractal Signature

Los resultados del MRCG son mejores que los del Fractal Signature y los del Fractal Signature son mejores que los del SGLDM.

9. CONCLUSIONES

El MRCG es una secuencia de grafos de la forma {Ns(t)}s e I tal que dado un valor s, definimos la función Ns(t) como el número de componentes conexas con un número de píxeles >=s en una imagen binarizada con un umbral t.

En el peor de los casos la complejidad es casi lineal.

Es un método bueno tanto para macrotexturas como para microtexturas.

Es invariante respecto de la orientación.

10. REFERENCIAS

"Efficient Topological Characterization of Gray-Level Textures, Using a Multiresolution Representation".
Graphical Models and Image Processing. Vol. 59, n. 1, 1-17, 1997

"Tratamiento digital de imágenes"
González, R.C. y Woods, R.E.
Editorial:Addison-Wesley/Díaz de Santos, 1996

Apuntes de Tecnologías para Imagen Documental (3º ITIG)

Apuntes de Tratamiento de Imágenes (5º II)

Trabajo dirigido PID “Texturas caracterizadas topológicamente”. Año 2002/03.

Autor: Carmen Barba Riquel

Trabajo dirigido PID de Texturas: Propiedades estadísticas.(José.A. Díaz-Otero Muñoz-Repiso Federico Navarro Giráldez)

https://www.ee.siue.edu

"Color Conversion Algorithms"

https://www.cs.rit.edu/~ncs/color/t_convert.html

Nan C. Schaller

Professor, Computer Science Department

Rochester Institute of Technology