Apuntes de Morfologia

Sean A y B son conjuntos en un n-espacio Eⁿ con elementos a = (a₁,..., a_n) y b = (b₁,..., b_n) respectivamente siendo ambos n-tuplas.

El lenguaje de la morfología matemática binaria es el de la teoría de conjuntos. Los conjuntos en morfología matemática representan las formas presentes en imágenes binarias o de niveles de gris. El conjunto de todos los píxeles blancos en una imagen en blanco y negro (binaria) constituye una descripción completa de la imagen.

Los puntos en un conjunto sobre los que se aplica la transformación son el conjunto de puntos seleccionado y el complementario el no seleccionado. En las imágenes binarias los puntos seleccionados son los que no pertenecen al fondo.

Las operaciones primarias morfológicas son la erosión y la dilatación. A partir de ellas podemos componer las operaciones de apertura y clausura. Son estas dos operaciones las que tienen mucha relación con la representación de formas, la descomposición y la extracción de primitivas.

La dilatación es la transformación morfológica que combina dos vectores utilizando la suma. La dilatación binaria fue usada primero por Minkowski, y en la literatura matemática recibe el nombre de suma de Minkowski. Si A y B son conjuntos en un n-espacio Eⁿ con elementos a = (a₁,..., a_n) y b = (b₁,..., b_n), respectivamente, siendo ambos n-tuplas, entonces la dilatación de A por B es el conjunto de todos los posibles vectores que son suma de pares de elementos, uno de A y otro de B.

Más formalmente, la dilatación de A por B se nota A $\oplus$ B y se define mediante

A $\displaystyle \oplus$ B = {c $\displaystyle \in$ Eⁿ| c = a + b para algún a $\displaystyle \in$ A y b $\displaystyle \in$ B}

Se puede probar que las siguientes definiciones de la dilatación son equivalentes

A $\displaystyle \oplus$ B = {x|( $\displaystyle \hat{B}$ )_x $\displaystyle \cap$ A $\displaystyle \neq$ $\displaystyle \emptyset$ } = $\displaystyle \cup_{b \in B}^{}$ A_b

En la práctica los conjuntos A y B no son simétricos. El primer elemento de la dilatación, A, está asociado con la imagen que se está procesando y el segundo recibe el nombre de elemento estructural, la forma que actúa sobre A en la dilatación para producir A $\oplus$ B.

Cuando se realiza una dilatación con un elemento estructural que contiene el cero, lo que realizamos es la expansión de una imagen y es fácil pensar en una implementación paralela. Algunos ejemplos se muestran en las figuras 1 , 2 . Es importante tener en cuenta que el sistema de coordenadas que se usará en este tema es (fila,columna).

**Figura 1: Ejemplo de dilatación. (a) Elemento estructural, B. (b) Imagen, A. (c) Resultado de la dilatación A $\oplus$ B**

**Figura 2: Otro ejemplo de dilatación. (a) Elemento estructural, B. (b) Imagen, A . (c) Resultado de la dilatación A $\oplus$ B**

La erosión es la operación morfológica dual, un concepto que definiremos formalmente a continuación, de la dilatación. Es la transformación morfológica que combina dos conjuntos usando el concepto de inclusión. Si A y B son conjuntos en el espacio euclídeo n-dimensional, entonces la erosión de A por B es el conjunto de todos los elementos x para los que x + b $\in$ A para todo b $\in$ B. La sustracción de Minkowski está muy relacionada con la erosión.

A $\displaystyle \ominus$ B = {x $\displaystyle \in$ Eⁿ| x + b $\displaystyle \in$ A para todo b $\displaystyle \in$ B}

**Figura 3: Ejemplo de erosión. (a) Elemento estructural, B. (b) Imagen, A. (c) Resultado de la erosión A $\ominus$ B**

La utilidad de la erosión puede apreciarse mejor cuando ésta se expresa de forma diferente. La erosión de una imagen, A , por un elemento estructural, B, es el conjunto de todos los elementos x $\in$ Eⁿ para los cuales B trasladado por x está contenido en A. La demostración es inmediata y se tiene

A $\displaystyle \ominus$ B = {x $\displaystyle \in$ Eⁿ| B_x $\displaystyle \subseteq$ A}

Mientras que la dilatación puede representarse como la unión de los trasladados, la erosión puede representarse como la intersección de los trasladados negativos.

A $\displaystyle \ominus$ B = $\displaystyle \cap_{b \in B}^{}$ A_-b

La erosión se concibe usualmente como una reducción de la imagen original. En términos de teoría de conjuntos, el conjunto erosionado se suele pensar que siempre está contenido en el original. Una transformación que cumple esta propiedad se dice antiextensiva. Sin embargo, la erosión es antiextensiva cuando el origen pertenece al elemento estructural. Esto es, si 0 $\in$ B, entonces A $\ominus$ B $\subseteq$ A, la demostración de esta propiedad, al igual que de las anteriores, es obvia.

Al igual que la dilatación, la erosión es también creciente: si A $\subseteq$ B entonces A $\ominus$ K $\subseteq$ B $\ominus$ K. Además la erosión por un elemento estructural mayor produce un resultado menor si K $\subseteq$ L entonces A $\ominus$ L $\subseteq$ A $\ominus$ K.

La dilatación y la erosión son muy similares en el sentido de que lo que uno hace al objeto el otro lo hace al fondo. Esta relación puede formularse como una relación de dualidad.

Dos operadores son duales cuando la negación de una formulación empleado en el primero es igual a la misma formulación empleando el segundo operador en la variable negada. Un ejemplo es la ley de DeMorgan que establece la dualidad entre la unión y la intersección (A $\cup$ B)^c = A^c $\cap$ B^c, siendo la negación el complementario.

En morfología la negación de un conjunto puede ocurrir de dos formas diferentes: en un sentido lógico, siendo la negación la complementación o en un sentido geométrico, siendo la negación el cambio de la orientación de un conjunto con respecto a los ejes de coordenadas. Esta negación recibe el nombre de reflexión.

Sea B $\subseteq$ Eⁿ, como ya sabemos, la reflexión de B se nota $\hat{B}$ y se define mediante

$\displaystyle \hat{B}$ = {x| para algún b $\displaystyle \in$ B, x = - b}

Como se ve en el siguiente teorema, el complemento de la erosión es la dilatación de un complemento por reflexión. La dualidad de dilatación y erosión usa negaciones lógicas y geométricas por los diferentes papeles jugados por la imagen y el elemento estructural.

Teorema . Dualidad de la erosión y la dilatación.

(A $\displaystyle \ominus$ B)^c = A^c $\displaystyle \oplus$ $\displaystyle \hat{B}$

Corolario .

(A $\displaystyle \oplus$ B)^c = A^c $\displaystyle \ominus$ $\displaystyle \hat{B}$

Finalmente, con respecto a la descomposición de elementos estructurales, una regla de la cadena para la erosión se verifica cuando el elemento estructural se puede descomponer mediante dilatación.

A $\displaystyle \ominus$ (B $\displaystyle \oplus$ C) = (A $\displaystyle \ominus$ B) $\displaystyle \ominus$ C

Basándonos en la discusión anterior, podemos ahora abordar algunos usos prácticos de la morfología. Cuando trabajamos con imágenes binarias, la principal aplicación de la morfología es la extracción de componentes de la imagen que son útiles para la descripción y representación de formas, en particular consideraremos los algoritmos morfológicos para extraer fronteras, componentes conexas, envolventes convexas y el esqueleto de una región. También es posible elaborar varios métodos para rellenar, aumentar, disminuir y podar regiones que se usan en conjunción con estos algoritmos como pre- o post- procesamiento.

En este apartado veremos sólo los algoritmos que están basados en erosiones y dilataciones simples

La frontera de un conjunto A, que se nota $\beta$ (A), se puede obtener primero erosionando A por B y realizando posteriormente la diferencia entre A y su erosión. Es decir,

$\displaystyle \beta$ (A) = A - (A $\displaystyle \ominus$ B)

La figura 4 ilustra la mecánica de la extracción de fronteras. Con un elemento estructural simple. Aunque el elemento estructural usado es muy simple, existen elecciones más complejas, por ejemplo de tamaño 5 x 5 que ampliaría el grosor de la frontera a dos o tres píxeles

**Figura .4: Extracción de fronteras usando la erosión**

A continuación desarrollaremos un algoritmo simple basado en un conjunto de dilataciones, complementaciones e intersecciones para rellenar regiones. Veamos como hacerlo con un ejemplo, en la figura 5 tenemos una frontera, A, 8-conectada de una región, cuyo objetivo es rellenarla. Comenzamos con un punto p dentro del objeto, es decir en la región, el objetivo es rellenar la región entera con unos.

Con la hipótesis que tenemos todos los puntos no frontera son cero y determinan el complementario de A, p tiene el valor uno al comenzar el procedimiento. El siguiente procedimiento rellena la región con unos (píxeles grises).

X_k = (X_{k - 1} $\displaystyle \oplus$ B) $\displaystyle \cap$ A^c *2cmk = 1, 2, 3...

Es importante notar que el proceso anterior rellenaría la región entera si no hiciéramos la intersección con A^c , sin embargo esta intersección limita el proceso a la región de interés (este tipo de dilatación recibe a veces el nombre de dilatación condicionada). Es obvio que el proceso se puede extender a cualquier número de subconjuntos siempre que conozcamos puntos dentro de ellos.

Con el concepto de conectividad conocido de capítulos anteriores veamos como utilizar la morfología matemática para extraer componentes conexas, un concepto que es básico en muchas aplicaciones del análisis de imágenes. Supongamos que Y representa una componente conexa contenida en un conjunto A y supongamos que conocemos un punto p que pertenece a dicha región. Entonces, el siguiente procedimiento puede utilizarse para extraer Y

X_k = (X_{k - 1} $\displaystyle \oplus$ B) $\displaystyle \cap$ A *2cmk = 1, 2,...

Figura 6: A contiene una componente conexa que comienza en p, (tono gris para distinguirlo de los otros. En (c) el resultado de la primera aplicación del proceso iterativo, (d) el segundo paso (e) el tercero y (e) el último

La transformación morfológica de hit-or-miss es una herramienta básica para la detección de formas.

Sea B = (J, K) donde J es el conjunto formado por los elementos de K asociados con el objeto y B₂ el asociado con el fondo, la transformación hit-or-miss se define como

A $\displaystyle \otimes$ B = (A $\displaystyle \ominus$ J) $\displaystyle \cap$ (A^c $\displaystyle \ominus$ K)

Por tanto, el conjunto A $\otimes$ B contiene todos los puntos en los que simultáneamente J tiene una ganancia en A y K la tiene en A^c.

Utilizando la definición de diferencia de conjuntos y la relación dual entre la erosión y la dilatación, podemos escribir la ecuación anterior como

A $\displaystyle \otimes$ B = (A $\displaystyle \ominus$ J) - (A $\displaystyle \oplus$ $\displaystyle \hat{K}$ )

Un ejemplo de aplicación de la transformación hit-or-miss es la búsqueda de puntos aislados, si J = {(0, 0)} y K = {(0, 1),(0, - 1),(1, 0),(- 1, 0)}, entonces I $\otimes$ B es el conjunto de todos los píxeles 4-aislados. Por último, la figura 7 muestra como encontrar esquinas superiores derechas de imágenes usando transformaciones de ganancia-pérdida.

**Figura 7: Aplicación de la transformación ganancia-pérdida para encontrar esquinas superiores derechas**

El concepto de envolvente convexa fue ya introducido, siendo además un descriptor útil de las regiones de una imagen. Veamos ahora como obtener la envolvente convexa basándonos en la morfología matemática. Denotemos C(A) la envolvente convexa de un conjunto A, sean Bⁱ, i = 1, 2, 3, 4 cuatro elementos estructurales. El procedimiento consiste en implementar la siguiente ecuación

X_kⁱ = (X $\displaystyle \otimes$ $\displaystyle \cal {B}$ ⁱ) $\displaystyle \cup$ A *2cmi = 1, 2, 3, 4 y k = 1, 2,...

La figura 8 ilustra con un ejemplo el procedimiento para extraer la envolvente convexa. El origen está siempre en el centro del elemento estructural y los píxeles marcados x no se usan para construir el complementario del elemento estructural

**Figura 8: Cálculo de la envolvente convexa de un conjunto**

La disminución de un conjunto A por un elemento estructural B puede ser definida en términos de la transformación ganancia-pérdida

AøB = A - (A $\displaystyle \otimes$ B) = A $\displaystyle \cup$ (A $\displaystyle \otimes$ B)^c

Una definición más útil para el adelgazamiento de A simétrico está basado en una sucesión de elementos estructurales como

La figura 9 muestra los elementos estructurales que son necesarios para construir la m-conectividad de una región.

**Figura 9: Elementos estructurales para el cálculo de la m-conectividad**

La ampliación es el dual morfológico de la disminución y se define mediante la expresión

A $\displaystyle \odot$ B = A $\displaystyle \cup$ (A $\displaystyle \otimes$ B)

A $\displaystyle \odot$ {B} = ((...((A $\displaystyle \odot$ B¹) $\displaystyle \odot$ B²)...) $\displaystyle \odot$ Bⁿ)

Con los conceptos que hemos visto podemos comprender ahora mejor las razones por las que la dilatación y la erosión están muy relacionados con la forma. La erosión y la dilatación usualmente se emplean por pares, bien la dilatación seguida por la erosión o al revés. En cualquier caso, el resultado de esta aplicación sucesiva de erosiones y dilataciones es una eliminación de detalles menores que el elemento estructural, sin distorsionar la forma global del objeto.

Un aspecto fundamental de esta aplicación sucesiva es el hecho de que la aplicación sucesiva de erosiones y dilataciones es idempotente, es decir la aplicación sucesiva de estos operadores no cambia el resultado. La importancia práctica de este resultado es que las transformaciones idempotentes forman un estado completo de los algoritmos del análisis de imágenes ya que las formas podrían ser descritas en términos de los elementos estructurales bajo los cuales pueden ser abiertos o cerrados y quedarse igual.

Podría decirse que la apertura y la clausura corresponden dentro de la morfología a lo que las proyecciones ortogonales son al álgebra lineal. Una proyección ortogonal es idempotente y selecciona la parte de un vector que está en un determinado subespacio. Análogamente, la apertura y la clausura proporcionan los medios por los cuales seleccionar subformas y superformas de una forma compleja.

Como hemos visto, cuando el elemento estructural contiene el origen, la dilatación expande la imagen y la erosión la reduce. En esta sección discutiremos otras dos importantes operaciones morfológicas: apertura y clausura. La apertura generalmente suaviza los contornos de una imagen.

La apertura de A por un elemento estructural K se nota AoK, se define como

AoK = (A $\displaystyle \ominus$ K) $\displaystyle \oplus$ K

La clausura de A por un elemento estructural K se nota A $\bullet$ K, se define como

A $\displaystyle \bullet$ K = (A $\displaystyle \oplus$ K) $\displaystyle \ominus$ K

Si A no cambia con la apertura con K diremos que A es abierto con respecto a K. Si A no cambia con la clausura con K diremos que A es cerrado con respecto a K.

La habilidad de una apertura para seleccionar de un conjunto el subconjunto que se acopla al elemento estructural es clara por el teorema de caracterización

AoK = {x $\displaystyle \in$ A| para algún t $\displaystyle \in$ A $\displaystyle \ominus$ K, x $\displaystyle \in$ K_t y K_t $\displaystyle \subseteq$ A}

AoK = $\displaystyle \bigcup_{y \in A \ominus K}^{}$ K_y = $\displaystyle \bigcup_{K_y \subseteq A}^{}$ K_y

Veamos una interpretación geométrica simple de la apertura. Supongamos que consideramos el disco que constituye un elemento estructural K como una bola plana que rueda en R². La frontera de AoK viene dada por los puntos de la frontera de K que alcanzan la parte más lejana de la frontera de A cuando K rueda alrededor de la parte interior de la frontera.

La figura 10 ilustra como podemos usar la apertura para descomponer objetos. Supongamos un cuadrado unido a un asa. El procedimiento descrito en la figura nos sirve para separar las dos partes.

**Figura 10: Extracción de cuerpo y asa. (a) contiene la imagen A, (b) el elemento estructural K, (c) la apertura A`o` K y (d ) A - A`o`K.**

(A $\displaystyle \bullet$ K)^c = A^co $\displaystyle \hat{K}$

El teorema de caracterización para la apertura y la dualidad entre apertura y clausura nos lleva a la caracterización de la clausura que establece que

A $\displaystyle \bullet$ K = {x| x $\displaystyle \in$ $\displaystyle \hat{K}_{t}^{}$ implica $\displaystyle \hat{K}_{t}^{}$ $\displaystyle \cap$ A $\displaystyle \neq$ $\displaystyle \emptyset$ }

La clasura de A incluye todos los puntos que cumplen la condición de que cuando son cubiertos por un trasladado del reflejado del elemento estructural, este trasladado y A deben tener intersección no vacía. De nuevo esta transformación es invariante por traslaciones del elemento estructural.

La apertura y clausura con un elemento estructural isotrópico se usa para eliminar detalles específicos más pequeños que el elemento estructural sin distorsionar la forma global de los objetos.

De los teoremas de caracterización se sigue que la apertura es antiextensiva, Ao K $\subseteq$ A, y la clausura es extensiva, A $\subseteq$ A $\bullet$ K.

Otro aspecto significativo de estas operaciones es que son idempotentes, es decir,

X`o`B	=	(X`o`B)`o` B
X $\displaystyle \bullet$ B	=	(X $\displaystyle \bullet$ B) $\displaystyle \bullet$ B

Serra entre otros probó que el esqueleto de un conjunto A puede ser expresado en términos de erosiones y aperturas. Esto es, con S(A) notando el esqueleto de A, se puede probar que

S_k(A) = $\displaystyle \cup_{l=0}^{k}$ {(A $\displaystyle \ominus$ lK) - [(A $\displaystyle \ominus$ lK)oK]}

L = max{l|(A $\displaystyle \ominus$ lK) $\displaystyle \neq$ $\displaystyle \emptyset$ }

La formulación dada en las ecuaciones anteriores establece que el esqueleto de A puede obtenerse como la unión de los subconjuntos de esqueletos S_k(A). Puede probarse también que

A = $\displaystyle \cup_{l=0}^{L}$ (S_l(A) $\displaystyle \oplus$ lK)

En esta sección extenderemos a imágenes de niveles de gris, las operaciones básicas de dilatación, erosión, apertura y clausura y usaremos estos operadores para el desarrollo de algunos algoritmos básicos. De nuevo, el objetivo es el uso de la morfología de niveles de gris para extraer componentes de la imagen que son útiles en la representación y descripción de las formas. En particular veremos algoritmos para extraer fronteras de imágenes mediante el gradiente morfológico y para la partición de regiones basada en su contenido en textura. También discutiremos algoritmos para alisamiento y realce que de nuevo pueden ser pasos en pre- post- procesamiento.

Vamos, por simplicidad, a formular el estudio en Z² aunque es posible su realización en otros espacios. Trabajaremos con imágenes de la forma f (x, y) y b (x, y) donde f (x, y) es una imagen de entrada y b(x, y) un elemento estructural, de hecho una subimagen. Supondremos que las imágenes son discretas, es decir si Z denota los enteros, supondremos que (x, y) son enteros de Z x Z y que f y b son funciones que asignan un número real a cada par de coordenadas (x, y), si los niveles de gris son enteros, Z sustituirá a R.

La dilatación de una imagen de niveles de gris f por b que se notará f $\oplus$ b, se define como

(f $\displaystyle \oplus$ b)(s, t) = max{f (s - x, t - y) + b(x, y)|(s - x, t - y) $\displaystyle \in$ D_f,(x, y) $\displaystyle \in$ D_b}

Observemos que se impone la condición de inclusión en el espacio de definición y que la ecuación anterior es casi como una convolución con el máximo reemplazando a la suma de la convolución y la suma al producto con el nucleo de convolución..

En la figura 11 se ilustra un ejemplo de dilatación para niveles de grises. Puede probarse que el efecto de la dilatación es como si tuvieramos una imagen que fuese el relleno de la función y un elemento estructural que fuese el relleno también de la función elemento estructural y calculásemos la dilatación binaria clásica extrayendo luego sólo la parte superior de la imagen.

Figura 11: (a) Elemento estructural b, (b) imagen f, (c) f $\oplus$ b. (d) relleno de b, notado U(b), (e) relleno de f, notado U(f ), la extracción de la parte superior de U(f ) $\oplus$ U(b) ques se nota T(U(f ) $\oplus$ U(k)) produce f $\oplus$ b.

La erosión de niveles de grises, que se nota f $\ominus$ b, se define mediante

(f $\displaystyle \ominus$ b)(s, t) = min{f (s + x, t + y) - b(x, y)|(s + x, t + y) $\displaystyle \in$ D_f,(x, y) $\displaystyle \in$ D_b}

Observemos que se impone la condición de inclusión en el espacio de definición y que la ecuación anterior es casi como una correlación con el máximo reemplazando la suma y la diferencia el producto.

En la figura 12 se ilustra un ejemplo de erosión para niveles de grises. Puede probarse que el efecto de la erosión es como si tuvieramos una imagen que fuese el relleno de la función y un elemento estructural que fuese el relleno también de la función elemento estructural y calculásemos la erosión binaria clásica extrayendo luego sólo la parte superior de la imagen.

Figura 12: (a) Elemento estructural b, (b) imagen f, (c) f $\ominus$ b. (d) relleno de b, notado U(b), (e) relleno de f, notado U(f ), la extracción de la parte superior de U(f ) $\ominus$ U(b) ques se nota T(U(f ) $\ominus$ U(k)) produce f $\ominus$ b.

Al igual que antes la erosión y la dilatación, ahora para niveles de grises son operaciones duales con respecto a la complementación y reflexión, es decir,

(f $\displaystyle \ominus$ b)^c(x, y) = (f^c $\displaystyle \oplus$ $\displaystyle \hat{b}$ )(x, y)

Las expresiones para la apertura y clausura de niveles de gris tienen la misma forma que la apertura y clausura binarias. La apertura de f por un elemento estructural b, se nota fob y se define mediante

fob = (f $\displaystyle \ominus$ b) $\displaystyle \oplus$ b

f $\displaystyle \bullet$ b = (f $\displaystyle \oplus$ b) $\displaystyle \ominus$ b

La apertura y la clausura son duales con respecto a la complementación y reflexión. Es decir,

(f $\displaystyle \bullet$ b)^c = f^co $\displaystyle \hat{b}$

La apertura y la clausura de una imagen tienen una interpretación geométrica simple. Supongamos que vemos una función de imagen f (x, y) en perspectiva 3 - D siendo x e y las coordenadas usuales y la tercera el nivel de brillo (la función). En esta representación, la imagen aparece como usa superficie discreta cuyo valor en cualquier punto (x, y ) es el valor de la imagen. Supongamos que queremos realizar la apertura por un elemento esférico b (de hecho es sólo la semiesfera lo que necesitamos) y vemos el elemento estructural como una bola que rueda. Entonces el mecanismo para abrir f por b puede interpretarse geométricamente como el proceso de hacer rodar la bola por la parte inferior de la función y la clausura conlleva hacerla rodar por la parte superior. La figura 13 ilustra el procedimiento.

**Figura 13: (a) Elemento estructural que se interpreta como esfera, (b) imagen, (c) proceso para obtener la apertura, (d) proceso para obtener la clausura**

Terminaremos este estudio sobre la morfología matemática analizando algunas aplicaciones de la misma.

Una forma de llevar a cabo el alisamiento de una imagen es realizar una apertura seguida de una clausura. El resultado de estas dos operaciones es suprimir o atenuar elementos extraños muy brillantes u oscuros.

Además de las operaciones antes discutidas para la supresión de elementos extraños, a menudo la dilatación y la erosión se usan para calcular el gradiente morfológico de una imagen que se nota g y se define

g = f $\displaystyle \oplus$ b - f $\displaystyle \ominus$ b

Apuntes de Morfología