🙄 ✋ 🎅 Algoritmos de detección de esquema de imagen 🧒🏻 ♾ 🌍

El artículo presenta los cuatro algoritmos de detección de bucle más comunes.

Los dos primeros, a saber, el algoritmo para trazar cuadrados y trazar los alrededores de Moore, son fáciles de implementar y, por lo tanto, a menudo se usan para determinar el contorno de un patrón dado. Desafortunadamente, ambos algoritmos tienen varias debilidades, lo que hace que sea imposible detectar el contorno de una gran clase de patrones debido a su tipo especial de adyacencia.

Estos algoritmos ignorarán todos los "agujeros" en el patrón. Por ejemplo, si tenemos un patrón similar al que se muestra en la Figura 1 , entonces el circuito detectado por los algoritmos será similar al que se muestra en la Figura 2 (el contorno se indica mediante píxeles azules). En algunas áreas de aplicación, esto es bastante aceptable, pero en otras áreas, por ejemplo, en el reconocimiento de caracteres, se requiere la detección de las partes internas de un patrón para encontrar todos los espacios que distinguen un carácter específico. (La Figura 3 muestra el esquema "completo" del patrón).

Por lo tanto, para obtener un contorno completo, primero es necesario usar el algoritmo de "búsqueda de agujeros" que determina los agujeros en un patrón dado, y luego aplicar el algoritmo de detección de contorno a cada agujero.

¿Qué es la conectividad?

En imágenes digitales con valores binarios, un píxel puede tener uno de los siguientes valores: 1: cuando forma parte del patrón o 0: cuando forma parte del fondo, es decir, sin gradación de gris. (Asumiremos que los píxeles con un valor de 1 son negros y con un valor de 0 son blancos).

Para identificar objetos en un patrón digital, necesitamos encontrar grupos de píxeles negros que estén "conectados" entre sí. En otras palabras, los objetos en un patrón digital dado son los componentes conectados de este patrón.

En el caso general, un componente conectado es un conjunto de píxeles negros P , de modo que para cada par de píxeles p _i y p _j en P hay una secuencia de píxeles p _i , ..., p _j tal que:

a) todos los píxeles en la secuencia están en el conjunto P , es decir son negros y

b) cada 2 píxeles en la secuencia uno al lado del otro son "vecinos".

Surge una pregunta importante: ¿ cuándo podemos decir que 2 píxeles son "vecinos"? Dado que usamos píxeles cuadrados, la respuesta a la pregunta anterior no es trivial por la siguiente razón: en la teselación cuadrada, los píxeles tienen un borde común o un vértice, o no tienen nada en común. Cada píxel tiene 8 píxeles en común con él; tales píxeles forman el "vecindario de Moore" de ese píxel. ¿Deberíamos considerar que los píxeles "vecinos" tienen un solo vértice común? ¿O para ser considerados "vecinos", dos píxeles deben tener un borde común?

Entonces, hay dos tipos de conectividad, a saber: 4-conectividad y 8-conectividad.

4 conexiones

¿Cuándo podemos decir que un conjunto dado de píxeles negros está 4-conectado? Primero, debe definir el concepto de un vecino de 4 (también llamado vecino directo ):

Definición de 4 vecinos : un píxel Q es un 4 vecino de un píxel P dado si Q y P tienen un borde común. Los 4 vecinos del píxel P (designado como P2, P4, P6 y P8 ) se muestran en la Figura 2 a continuación.

Definición de un componente conectado a 4 : el conjunto de píxeles negros P es un componente conectado a 4 si para cada par de píxeles p _i y p _j en P hay una secuencia de píxeles p _i , ..., p _j tal que:

a) todos los píxeles en la secuencia están en el conjunto P , es decir son negros y

b) cada dos píxeles adyacentes en la secuencia son 4 vecinos

Ejemplos de patrones 4 conectados

Los siguientes diagramas muestran ejemplos de patrones conectados a 4:

8 conexiones

¿Cuándo puedo decir que un conjunto dado de píxeles negros está conectado a 8 ? Primero, necesitamos definir el concepto de un vecino de 8 (también llamado vecino indirecto ):

Definición de 8 vecinos : un píxel Q es un 8 vecino (o simplemente un vecino ) de un píxel P dado si Q y P tienen un borde o vértice común. Los 8 vecinos de un píxel P conforman el vecindario de Moore de este píxel.

Definición de un componente conectado a 8 : el conjunto de píxeles negros P es un componente conectado a 8 (o simplemente un componente conectado ) si para cada par de píxeles p _i y p _j en P hay una secuencia de píxeles p _i , ..., p _j tal que :

a) todos los píxeles en la secuencia están en el conjunto P , es decir son negros y

b) cada dos píxeles adyacentes en esta secuencia son 8 vecinos

Nota : todos los patrones conectados a 4 están conectados a 8, es decir Los patrones de 4 conectados son un subconjunto de los muchos patrones de 8 conectados. Por otro lado, un patrón conectado a 8 puede no estar conectado a 4.

Ejemplo de patrón de 8 enlaces

El siguiente diagrama muestra un patrón que está conectado a 8 pero no a 4:

Un ejemplo de un patrón no conectado a 8:

El siguiente diagrama muestra un ejemplo de un patrón que no está conectado a 8, es decir compuesto de más de un componente conectado (el diagrama muestra tres componentes conectados):

Algoritmo de traza cuadrada

Idea

La idea detrás del algoritmo de trazado cuadrado es muy simple; Esto puede atribuirse al hecho de que el algoritmo fue uno de los primeros intentos de detectar el contorno de un patrón binario.

Para entender cómo funciona, necesitas un poco de imaginación ...

Supongamos que tenemos un patrón digital, por ejemplo, un grupo de píxeles negros sobre un fondo de píxeles blancos, es decir, en la cuadrícula; encontrar el píxel negro y declararlo como nuestro píxel " inicial ". (Encontrar el píxel " inicial " se puede implementar de muchas maneras diferentes; comenzaremos desde la esquina inferior izquierda de la cuadrícula, escanearemos cada columna de píxeles de abajo hacia arriba, desde la columna más a la izquierda hasta la derecha, hasta encontrar un píxel negro. Lo declararemos " inicial " ".)

Ahora imagine que es una mariquita parada en el píxel inicial , como se muestra en la Figura 1 a continuación. Para obtener el esquema de un patrón, debe hacer lo siguiente:

, , ,

, , ,

.

Los píxeles negros que rodeaste serán el contorno del patrón.

Un aspecto importante del algoritmo de traza cuadrada es el "sentido de dirección". Los giros hacia la izquierda y hacia la derecha se realizan en relación con la ubicación actual, que depende de cómo llegó al píxel actual. Por lo tanto, para realizar los movimientos correctos, debe seguir su dirección.

Algoritmo

La siguiente es una descripción formal del algoritmo de rastreo cuadrado:

Entrada: teselación cuadrada, T , que contiene el componente conectado P de las células negras.

Salida: fila B (b ₁ , b ₂ , ..., b _k ) de píxeles de borde, es decir contorno

Inicio

Defina B como un conjunto vacío.
Escanee las celdas T de abajo hacia arriba y de izquierda a derecha hasta encontrar un píxel negro s de P.
Inserte s en B.
Convierta el píxel actual p en el píxel inicial s .
Gire a la izquierda, es decir ir al píxel vecino a la izquierda de p .
Actualización p , es decir se convierte en el píxel actual.
Mientras p no es igual a s , ejecute

Si el píxel actual p es negro
- inserte p en B y gire a la izquierda (vaya al píxel vecino a la izquierda de p ).
- Actualización p , es decir se convierte en el píxel actual.
de lo contrario
- gire a la derecha (vaya al siguiente píxel a la derecha de p ).
- Actualización p , es decir se convierte en el píxel actual.
Fin del ciclo "Bye"

El final

Nota: los conceptos de "izquierda" y "derecha" deben considerarse no con respecto a la página o al lector, sino con respecto a la dirección de entrada en el píxel "actual" durante el escaneo.

Demostración

La siguiente es una demostración animada de cómo el algoritmo de rastreo cuadrado detecta el contorno de un patrón. No olvides que la mariquita se mueve en píxeles; observe cómo cambia su dirección al girar a la izquierda y a la derecha. Los giros hacia la izquierda y hacia la derecha se realizan en relación con la dirección actual en un píxel, es decir Orientación de mariquita.

Análisis

Resulta que las capacidades del algoritmo de rastreo cuadrado son muy limitadas. No puede detectar los contornos de una gran familia de patrones que a menudo surgen en aplicaciones del mundo real.

Esto se debe principalmente al hecho de que las rotaciones izquierda y derecha no tienen en cuenta los píxeles ubicados "a lo largo de
diagonales "del píxel actual.

Veamos los diferentes patrones con diferente conectividad y veamos por qué falla el algoritmo de rastreo cuadrado. Además, estudiaremos formas de mejorar las capacidades del algoritmo y hacerlo funcionar incluso con patrones que tienen un tipo especial de conectividad.

Criterio de parada

Una de las debilidades del algoritmo es la elección del criterio de detención. En otras palabras, ¿cuándo deja de ejecutarse un algoritmo?

En la descripción original del algoritmo de rastreo cuadrado, la condición de finalización es alcanzar el píxel inicial por segunda vez. Resulta que si el algoritmo depende de tal criterio, entonces no podrá detectar los contornos de una gran familia de patrones.

La siguiente es una demostración animada que explica cómo el algoritmo no puede detectar el contorno exacto del patrón debido a la selección de un criterio de detención incorrecto:

Como puede ver, mejorar el criterio de detención puede ser un buen comienzo para mejorar el rendimiento general del algoritmo. Hay dos alternativas efectivas para un criterio de apagado existente:

a) Pare solo visitando el píxel inicial n veces, donde n es al menos 2, O

b) Deténgase después de golpear el píxel de inicio por segunda vez, tal como lo golpeamos inicialmente.

Este criterio fue propuesto por Jacob Eliosoff , por lo que lo llamaremos el criterio para detener a Jacob .

Cambiar el criterio de detención en el caso general mejora la efectividad del algoritmo de rastreo cuadrado, pero no supera otras debilidades que tiene en el caso de patrones con tipos especiales de conectividad.

El algoritmo de rastreo cuadrado no puede detectar el contorno de una familia de patrones con una conectividad de 8 que NO tiene una conectividad de 4.

La siguiente es una demostración animada de cómo el algoritmo de rastreo cuadrado (con el criterio de detención de Jacob) no puede detectar el esquema correcto de un patrón con conectividad 8 sin conectividad 4:

¿Es este algoritmo completamente inútil?

Si lee el análisis anterior, probablemente piense que el algoritmo de rastreo cuadrado no puede detectar los contornos de la mayoría de los patrones. Pero resulta que que existe una familia especial de patrones en los que el algoritmo de rastreo cuadrado detecta completamente la ruta.

Sea P el conjunto de píxeles negros con conectividad 4 en la cuadrícula. Deje que los píxeles blancos de la cuadrícula, es decir los píxeles de fondo W también tienen una conectividad de 4. Resulta que bajo tales condiciones del patrón y su fondo, se puede demostrar que el algoritmo de traza cuadrada (con el criterio de detención de Jacob) siempre se ocupará con éxito de la determinación del contorno.

A continuación se muestra la prueba de que, en el caso de que tanto el patrón como los píxeles de fondo estén conectados, el algoritmo de traza cuadrada determinará correctamente el contorno cuando se utilice el criterio de detención de Jacob.

Prueba
Dado : el patrón P es tal que todos los píxeles del patrón (es decir, negro) y los píxeles de fondo (es decir, blanco) W tienen una conectividad de 4.

Primera observación

Dado que el conjunto de píxeles blancos W tiene una conectividad de 4, esto significa que no puede haber " agujeros " en el patrón (en términos informales, " agujeros " nos referimos a grupos de píxeles blancos completamente rodeados por píxeles negros del patrón).

La presencia de cualquier " agujero " en el patrón conducirá a la separación del grupo de píxeles blancos de los píxeles blancos restantes; sin embargo, muchos píxeles blancos pierden conectividad 4.

La Figura 2 y la Figura 3 a continuación muestran dos tipos de " agujeros " que pueden ocurrir en un patrón con conectividad 4:

Segunda observación

Cualquiera de los dos píxeles negros de un patrón DEBE tener un lado común.

Supongamos que dos píxeles negros tienen solo un vértice común. Luego, para satisfacer la propiedad de 4-conectividad del patrón, debe haber una ruta que conecte estos dos píxeles para que cada dos píxeles adyacentes en esta ruta tengan una conectividad de 4. Pero esto nos dará un patrón similar a la Figura 3 . En otras palabras, esto dará como resultado una separación de píxeles blancos. La Figura 4 a continuación muestra un patrón típico que satisface la suposición de que los píxeles en el patrón y el fondo están conectados a 4, es decir no tienen " agujeros ", y cada dos píxeles negros tienen un lado común:

Es útil representar tales patrones de la siguiente manera:

Primero consideramos los píxeles del límite, es decir esquema del patrón. Luego, si consideramos que cada píxel límite tiene 4 bordes de unidad de longitud, veremos que algunos de estos bordes son comunes con los píxeles blancos vecinos. Llamaremos a estos bordes bordes límite .

Tales bordes límite pueden considerarse como bordes de un polígono. En la foto
5 a continuación, esta idea se demuestra con el ejemplo de un polígono correspondiente al patrón de la Figura 4 anterior:

Si consideramos todas las "configuraciones" posibles de píxeles límite que pueden ocurrir en dichos patrones, veremos que hay dos casos simples, que se muestran en la Figura 6 y la Figura 7 a continuación.

Los píxeles de límite pueden ser múltiplos de estos casos u otros arreglos, es decir los giros y vueltas de estos dos casos. Las costillas límite están marcadas en azul como E1, E2, E3 y E4 .

Tercera observación

En el caso de los dos casos anteriores, sin importar el píxel inicial que elijamos, y en cualquier dirección en la que caiga , el algoritmo de traza cuadrada nunca "retrocederá" (retroceso) , nunca "atravesará" el borde del límite dos veces ( solo si no traza el borde por segunda vez) y nunca pierde el borde del límite . ¡Compruébalo!

Aquí hay que aclarar dos conceptos:

a) el algoritmo "retrocede" , cuando antes de trazar todo el borde vuelve a visitar un píxel ya visitado, y

b) para cada costilla límite, hay dos formas de "pasar a través de ella" , a saber, "hacia adentro" y "hacia afuera" (donde "hacia adentro" significa el movimiento hacia adentro del polígono correspondiente, y "hacia afuera" - hacia afuera del polígono).

Además, cuando el algoritmo pasa "hacia adentro" a través de uno de los bordes del límite, pasará "hacia afuera" a través del siguiente borde del límite, es decir el algoritmo de traza cuadrada no debería poder pasar a través de dos bordes consecutivos de la misma manera.

Última observación

Cada patrón tiene un número par de bordes límite .

Si observa el polígono de la Figura 5 , puede ver que:

Si queremos comenzar desde el vértice S marcado en el diagrama y seguir los bordes límite hasta que alcancemos S nuevamente, entonces notamos que en el proceso cruzamos un número par de bordes límite. Podemos considerar cada borde límite como un "paso" en una dirección separada. Luego, para cada "paso" a la derecha debe haber un "paso" correspondiente a la izquierda, si queremos volver a la posición inicial. Lo mismo se aplica a los "pasos" verticales. Por lo tanto, los "pasos" deben tener pares correspondientes, y esto explica por qué cada uno de estos patrones tendrá un número par de bordes de límite.

Por lo tanto, cuando el algoritmo para trazar cuadrados ingresa por el borde límite inicial (del píxel inicial) por segunda vez, lo hará en la misma dirección que la primera vez.

La razón de esto es que, dado que hay dos formas de atravesar el borde límite, y el algoritmo se mueve alternativamente hacia adentro y hacia afuera, y hay un número par de bordes límite, el algoritmo pasará por el borde límite inicial por segunda vez de la misma manera que en el primero

Conclusión

En el caso de un patrón y un fondo 4 conectados, el algoritmo de rastreo cuadrado detectará todo el borde, es decir contorno, patrón y dejará de funcionar después de una sola traza, es decir no lo rastreará nuevamente, porque cuando alcanza el borde límite inicial por segunda vez, lo ingresará de la misma manera que la primera vez. En consecuencia, el algoritmo de traza cuadrada con el criterio de detención de Jacob determinará correctamente el contador de cualquier patrón, siempre que tanto el patrón como el fondo estén 4 conectados.

Rastreando los alrededores de Moore

Idea

La idea detrás del rastreo de Moore-Neighbour es simple; pero antes de explicarlo, necesitamos explicar un concepto importante: el vecindario Moore de un píxel.

El barrio de Moore

El vecindario de Moore de un píxel P es un conjunto de 8 píxeles que tienen un vértice o borde común con ese píxel. Dichos píxeles, a saber, P1, P2, P3, P4, P5, P6, P7 y P8 , se muestran en la Figura 1 .

El vecindario de Moore (también llamado 8-vecinos o vecinos indirectos ) es un concepto importante al que a menudo se hace referencia en la literatura.

Ahora estamos listos para familiarizarnos con la idea subyacente en el rastro de los alrededores de Moore.

Que haya un patrón digital, es decir un grupo de píxeles negros, sobre un fondo de píxeles blancos, es decir en la cuadrícula; encuentre el píxel negro y declare el píxel " inicial ". (Hay varias formas de encontrar el píxel " inicial ", pero, como antes, comenzaremos desde la esquina inferior izquierda y escanearemos todas las columnas de píxeles en orden, hasta que encontremos el primer píxel negro, que declararemos " inicial ").

Ahora, de nuevo, imagine que es una mariquita parada en el píxel inicial , como se muestra en la Figura 2 a continuación. Sin pérdida de generalización, detectaremos el contorno moviéndonos alrededor del patrón en el sentido de las agujas del reloj. (No importa qué dirección elijamos, lo principal es usarla constantemente en el algoritmo).

La idea general es esta: cada vez que llegamos al píxel negro P , volvemos, es decir, al píxel blanco en el que nos encontramos antes. Luego damos la vuelta al píxel P en el sentido de las agujas del reloj, visitando cada píxel en su vecindad de Moore, hasta llegar al píxel negro. El algoritmo termina cuando el píxel de inicio alcanza el píxel de inicio por segunda vez.

Esos píxeles negros que visitó el algoritmo serán el contorno del patrón.