Detector de bordes astuto

Algoritmo de detección de bordes de imagen

El detector de bordes Canny es un operador de detección de bordes que utiliza un algoritmo de varias etapas para detectar una amplia gama de bordes en imágenes. Fue desarrollado por John F. Canny en 1986. Canny también elaboró ​​una teoría computacional de detección de bordes que explica por qué funciona la técnica.

Desarrollo

La detección de bordes de Canny es una técnica que permite extraer información estructural útil de diferentes objetos de visión y reducir drásticamente la cantidad de datos que se deben procesar. Se ha aplicado ampliamente en varios sistemas de visión artificial . Canny ha descubierto que los requisitos para la aplicación de la detección de bordes en diversos sistemas de visión son relativamente similares. Por lo tanto, se puede implementar una solución de detección de bordes que aborde estos requisitos en una amplia gama de situaciones. Los criterios generales para la detección de bordes incluyen:

1. Detección de bordes con baja tasa de error, lo que significa que la detección debe capturar con precisión tantos bordes como sea posible que se muestren en la imagen
2. El punto del borde detectado por el operador debe localizarse con precisión en el centro del borde.
3. Cada borde determinado de la imagen solo debe marcarse una vez y, siempre que sea posible, el ruido de la imagen no debe crear bordes falsos.

Para satisfacer estos requisitos, Canny utilizó el cálculo de variaciones , una técnica que encuentra la función que optimiza una función dada . La función óptima en el detector de Canny se describe mediante la suma de cuatro términos exponenciales , pero se puede aproximar mediante la primera derivada de una función gaussiana .

Entre los métodos de detección de bordes desarrollados hasta el momento, el algoritmo de detección de bordes Canny es uno de los métodos más estrictamente definidos que proporciona una detección buena y confiable. Debido a su capacidad óptima para cumplir con los tres criterios de detección de bordes y la simplicidad del proceso de implementación, se convirtió en uno de los algoritmos más populares para la detección de bordes.

Proceso

El proceso del algoritmo de detección de bordes de Canny se puede dividir en cinco pasos diferentes:

1. Aplicar filtro gaussiano para suavizar la imagen con el fin de eliminar el ruido.
2. Encuentra los gradientes de intensidad de la imagen.
3. Aplicar el umbral de magnitud de gradiente o la supresión de límite de corte inferior para eliminar la respuesta espuria a la detección de bordes
4. Aplicar doble umbral para determinar bordes potenciales
5. Seguimiento de bordes por histéresis : finaliza la detección de bordes suprimiendo todos los demás bordes que sean débiles y no estén conectados a bordes fuertes.

Filtro gaussiano

La imagen después de pasar una máscara gaussiana de 5×5 a través de cada píxel.

Dado que todos los resultados de detección de bordes se ven fácilmente afectados por el ruido en la imagen, es esencial filtrar el ruido para evitar detecciones falsas causadas por él. Para suavizar la imagen, se realiza una convolución de un núcleo de filtro gaussiano con la imagen. Este paso suavizará ligeramente la imagen para reducir los efectos del ruido obvio en el detector de bordes. La ecuación para un núcleo de filtro gaussiano de tamaño (2 k + 1) × (2 k + 1) viene dada por:

${\displaystyle H_{ij}={\frac {1}{2\pi \sigma ^{2}}}\exp \left(-{\frac {(i-(k+1))^{2}+(j-(k+1))^{2}}{2\sigma ^{2}}}\right);1\leq i,j\leq (2k+1)}$

A continuación se muestra un ejemplo de un filtro gaussiano 5×5, utilizado para crear la imagen adyacente, con = 2. (El asterisco denota una operación de convolución ). ${\displaystyle \sigma }$

${\displaystyle \mathbf {B} ={\frac {1}{159}}{\begin{bmatrix}2&4&5&4&2\\4&9&12&9&4\\5&12&15&12&5\\4&9&12&9&4\\2&4&5&4&2\end{bmatrix}}*\mathbf {A} .}$

Es importante entender que la selección del tamaño del núcleo gaussiano afectará el rendimiento del detector. Cuanto mayor sea el tamaño, menor será la sensibilidad del detector al ruido. Además, el error de localización para detectar el borde aumentará ligeramente con el aumento del tamaño del núcleo del filtro gaussiano. Un tamaño de 5x5 es un buen tamaño para la mayoría de los casos, pero esto también variará según las situaciones específicas.

Encontrar el gradiente de intensidad de la imagen

Un borde en una imagen puede apuntar en una variedad de direcciones, por lo que el algoritmo Canny utiliza cuatro filtros para detectar bordes horizontales, verticales y diagonales en la imagen borrosa. El operador de detección de bordes (como Roberts , Prewitt o Sobel ) devuelve un valor para la primera derivada en la dirección horizontal (G _x ) y la dirección vertical (G _y ). A partir de esto, se puede determinar el gradiente y la dirección del borde:

Dirección del gradiente

${\displaystyle \mathbf {G} ={\sqrt {{\mathbf {G} _{x}}^{2}+{\mathbf {G} _{y}}^{2}}}}$

${\displaystyle \mathbf {\Theta } =\operatorname {atan2} \left(\mathbf {G} _{y},\mathbf {G} _{x}\right)}$,

donde G se puede calcular utilizando la función hipot y atan2 es la función arcotangente con dos argumentos. El ángulo de dirección del borde se redondea a uno de los cuatro ángulos que representan la vertical, la horizontal y las dos diagonales (0°, 45°, 90° y 135°). La dirección del borde que cae en cada región de color se establecerá en un valor de ángulo específico, por ejemplo, θ en [0°, 22,5°] o [157,5°, 180°] se asigna a 0°.

Umbral de magnitud de gradiente o supresión de límite de corte inferior

La supresión de corte mínimo de magnitudes de gradiente, o umbralización de límite inferior, es una técnica de adelgazamiento de bordes .

Se aplica la supresión de límite inferior para encontrar las ubicaciones con el cambio más pronunciado en el valor de intensidad. El algoritmo para cada píxel de la imagen de gradiente es:

1. Compare la intensidad del borde del píxel actual con la intensidad del borde del píxel en las direcciones de gradiente positivo y negativo.
2. Si la intensidad del borde del píxel actual es la mayor en comparación con los demás píxeles de la máscara con la misma dirección (por ejemplo, un píxel que apunta en la dirección y se comparará con el píxel que se encuentra por encima y por debajo de él en el eje vertical), el valor se conservará. De lo contrario, el valor se suprimirá.

En algunas implementaciones, el algoritmo clasifica las direcciones de gradiente continuo en un pequeño conjunto de direcciones discretas y luego mueve un filtro 3x3 sobre la salida del paso anterior (es decir, la intensidad del borde y las direcciones de gradiente). En cada píxel, suprime la intensidad del borde del píxel central (estableciendo su valor en 0) si su magnitud no es mayor que la magnitud de los dos vecinos en la dirección del gradiente. Por ejemplo,

• Si el ángulo de gradiente redondeado es 0° (es decir, el borde está en la dirección norte-sur), se considerará que el punto está en el borde si la magnitud de su gradiente es mayor que las magnitudes de los píxeles en las direcciones este y oeste .
• Si el ángulo de gradiente redondeado es de 90° (es decir, el borde está en la dirección este-oeste), se considerará que el punto está en el borde si la magnitud de su gradiente es mayor que las magnitudes de los píxeles en las direcciones norte y sur .
• Si el ángulo de gradiente redondeado es de 135° (es decir, el borde está en la dirección noreste-suroeste), el punto se considerará que está en el borde si la magnitud de su gradiente es mayor que las magnitudes de los píxeles en las direcciones noroeste y sureste .
• Si el ángulo de gradiente redondeado es de 45° (es decir, el borde está en la dirección noroeste-sureste), el punto se considerará como en el borde si su magnitud de gradiente es mayor que las magnitudes de los píxeles en las direcciones noreste y suroeste .

En implementaciones más precisas, se utiliza la interpolación lineal entre los dos píxeles vecinos que se extienden a ambos lados de la dirección del gradiente. Por ejemplo, si el ángulo del gradiente está entre 89° y 180°, la interpolación entre los gradientes en los píxeles norte y noreste dará un valor interpolado, y la interpolación entre los píxeles sur y suroeste dará el otro (utilizando las convenciones del último párrafo). La magnitud del gradiente en el píxel central debe ser mayor que ambos para que se marque como un borde.

Tenga en cuenta que el signo de la dirección es irrelevante, es decir, norte-sur es lo mismo que sur-norte, y así sucesivamente.

Doble umbral

Después de aplicar la supresión no máxima, los píxeles de borde restantes proporcionan una representación más precisa de los bordes reales en una imagen. Sin embargo, quedan algunos píxeles de borde que son causados ​​por el ruido y la variación de color. Para tener en cuenta estas respuestas espurias, es esencial filtrar los píxeles de borde con un valor de gradiente débil y preservar los píxeles de borde con un valor de gradiente alto. Esto se logra seleccionando valores de umbral alto y bajo. Si el valor de gradiente de un píxel de borde es mayor que el valor de umbral alto, se marca como un píxel de borde fuerte. Si el valor de gradiente de un píxel de borde es menor que el valor de umbral alto y mayor que el valor de umbral bajo, se marca como un píxel de borde débil. Si el valor de gradiente de un píxel de borde es menor que el valor de umbral bajo, se suprimirá. Los dos valores de umbral se determinan empíricamente y su definición dependerá del contenido de una imagen de entrada determinada.

Seguimiento de bordes por histéresis

Detección de bordes astuta aplicada a una fotografía

Los píxeles de borde fuerte ciertamente deberían estar involucrados en la imagen de borde final; se considera que provienen de bordes verdaderos en la imagen. Sin embargo, habrá cierto debate sobre los píxeles de borde débil. Queremos determinar si estos píxeles provienen de un borde verdadero o de variaciones de ruido/color. Los píxeles de borde débil deberían descartarse de la consideración si es lo último. Este algoritmo utiliza la idea de que los píxeles de borde débil de bordes verdaderos (generalmente) estarán conectados a un píxel de borde fuerte mientras que las respuestas de ruido no están conectadas. Para rastrear la conexión de borde, se aplica un análisis de blobs observando un píxel de borde débil y sus 8 píxeles vecinos conectados. Siempre que haya un píxel de borde fuerte que esté involucrado en el blob, ese punto de borde débil puede identificarse como uno que debe conservarse. Estos píxeles de borde débil se convierten en bordes fuertes que luego pueden hacer que se conserven sus píxeles de borde débil vecinos.

Tutorial del algoritmo

Esta sección mostrará la progresión de una imagen a través de cada uno de los cinco pasos.

Mejoras

Si bien la detección de bordes tradicional de Canny proporciona una metodología relativamente simple pero precisa para el problema de detección de bordes, con requisitos más exigentes en cuanto a precisión y solidez en la detección, el algoritmo tradicional ya no puede manejar la desafiante tarea de detección de bordes. Los principales defectos del algoritmo tradicional se pueden resumir de la siguiente manera: ^[1]

1. Se aplica un filtro gaussiano para suavizar el ruido, pero también suavizará el borde, que se considera la característica de alta frecuencia. Esto aumentará la posibilidad de que se pasen por alto los bordes débiles y de que aparezcan bordes aislados en el resultado.
2. Para el cálculo de la amplitud del gradiente, el antiguo algoritmo de detección de bordes de Canny utiliza el centro en una pequeña ventana de vecindad de 2x2 para calcular el valor medio de la diferencia finita para representar la amplitud del gradiente. Este método es sensible al ruido y puede detectar fácilmente los bordes falsos y perder los bordes reales.
3. En el algoritmo tradicional de detección de bordes de Canny, habrá dos valores de umbral globales fijos para filtrar los bordes falsos. Sin embargo, a medida que la imagen se vuelve compleja, las diferentes áreas locales necesitarán valores de umbral muy diferentes para encontrar con precisión los bordes reales. Además, los valores de umbral globales se determinan manualmente a través de experimentos en el método tradicional, lo que genera una complejidad de cálculo cuando se necesita tratar con una gran cantidad de imágenes diferentes.
4. El resultado de la detección tradicional no puede alcanzar una precisión satisfactoria de una única respuesta para cada borde: aparecerán respuestas de múltiples puntos.

Para solucionar estos defectos, en los siguientes párrafos se presenta una mejora del algoritmo canny edge.

Reemplazar el filtro gaussiano

Como tanto el borde como el ruido se identificarán como una señal de alta frecuencia, un filtro gaussiano simple agregará un efecto de suavizado a ambos. Sin embargo, para alcanzar una alta precisión en la detección del borde real, se espera que se aplique un efecto más suave al ruido y se agregue un efecto menos suave al borde. Bing Wang y Shaosheng Fan de la Universidad de Ciencia y Tecnología de Changsha desarrollaron un filtro adaptativo, donde el filtro evaluará la discontinuidad entre los valores de escala de grises de cada píxel. ^{[ cita requerida ]} Cuanto mayor sea la discontinuidad, menor será el valor de peso que se establece para el filtro de suavizado en ese punto. Por el contrario, cuanto menor sea la discontinuidad entre los valores de escala de grises, mayor será el valor de peso que se establece para el filtro. El proceso para implementar este filtro adaptativo se puede resumir en cinco pasos:

1. K = 1, establezca la iteración n y el coeficiente de la amplitud del borde h.

2. Calcular el valor del gradiente y ${\displaystyle G_{x}(x,y)}$ ${\displaystyle G_{y}(x,y)}$

3. Calcula el peso según las fórmulas siguientes:

${\displaystyle d(x,y)={\sqrt {G_{x}(x,y)^{2}+G_{y}(x,y)^{2}}}}$

${\displaystyle w(x,y)=\exp \left(-{\frac {\sqrt {d(x,y)}}{2h^{2}}}\right)}$

4. La definición del filtro adaptativo es:

${\displaystyle f(x,y)={\frac {1}{N}}\sum \limits _{i=-1}^{1}\sum \limits _{j=-1}^{1}f(x+i,y+j)w(x+i,y+j)}$

para suavizar la imagen, donde

${\displaystyle N=\sum \limits _{i=-1}^{1}\sum \limits _{j=-1}^{1}w(x+i,y+j)}$

5. Cuando K = n, detenga la iteración; de lo contrario, k = k+1, continúe con el segundo paso.

Mejora en el cálculo de la magnitud y dirección del gradiente

La magnitud y dirección del gradiente se pueden calcular con una variedad de operadores de detección de bordes diferentes, y la elección del operador puede influir en la calidad de los resultados. Uno de los más elegidos es el filtro Sobel 3x3 . Sin embargo, otros filtros pueden ser mejores, como un filtro Sobel 5x5, que reducirá el ruido, o el filtro Scharr , que tiene una mejor simetría rotacional. Otras opciones comunes son Prewitt (utilizado por Zhou ^[2] ) y Roberts Cross .

Método robusto para determinar el valor de umbral dual

Para resolver los desafíos en los que es difícil determinar empíricamente el valor de umbral dual, se puede utilizar el método de Otsu ^[3] en la imagen de magnitud de gradiente suprimida no máxima para generar el umbral alto. El umbral bajo se establece típicamente en la mitad del umbral alto en este caso. Dado que la imagen de magnitud de gradiente tiene un valor continuo sin un máximo bien definido, el método de Otsu debe adaptarse para utilizar pares de valor/conteo en lugar de un histograma completo .

El adelgazamiento del borde

Si bien la detección de bordes tradicional de Canny logra un buen resultado de detección para cumplir con los dos primeros criterios, no cumple estrictamente con la respuesta única por borde. Mallat S y Zhong desarrollaron una técnica de morfología matemática para afinar el borde detectado. ^[4]

Uso de curvas

Se han utilizado curvas en lugar del filtro gaussiano y la estimación de gradiente para calcular un campo vectorial cuyas direcciones y magnitudes se aproximan a la dirección y la intensidad de los bordes de la imagen, a los que se aplican los pasos 3 a 5 del algoritmo Canny. Las curvas descomponen las señales en componentes separados de diferentes escalas, y la eliminación de los componentes de escalas más finas puede reducir el ruido. ^[5]

Formulación geométrica diferencial

Un enfoque más refinado para obtener bordes con precisión de subpíxeles es la detección de bordes diferenciales , donde el requisito de supresión no máxima se formula en términos de derivadas de segundo y tercer orden calculadas a partir de una representación del espacio de escala (Lindeberg 1998); consulte el artículo sobre detección de bordes para obtener una descripción detallada.

Formulación variacional del detector de bordes Haralick-Canny

Se demostró que una explicación variacional para el ingrediente principal del detector de bordes Canny, es decir, encontrar los cruces por cero de la 2.ª derivada a lo largo de la dirección del gradiente, era el resultado de minimizar un funcional de Kronrod-Minkowski mientras se maximizaba la integral sobre la alineación del borde con el campo de gradiente (Kimmel y Bruckstein 2003). Consulte el artículo sobre cruces por cero laplacianos regularizados y otros integradores de bordes óptimos para obtener una descripción detallada.

Parámetros

El algoritmo Canny contiene una serie de parámetros ajustables que pueden afectar el tiempo de cálculo y la efectividad del algoritmo.

• El tamaño del filtro gaussiano: el filtro de suavizado utilizado en la primera etapa afecta directamente los resultados del algoritmo Canny. Los filtros más pequeños causan menos desenfoque y permiten la detección de líneas pequeñas y nítidas. Un filtro más grande causa más desenfoque, difuminando el valor de un píxel determinado en un área más grande de la imagen. Los radios de desenfoque más grandes son más útiles para detectar bordes más grandes y suaves, por ejemplo, el borde de un arco iris.
• Umbrales: el uso de dos umbrales con histéresis permite una mayor flexibilidad que un enfoque de umbral único, pero los problemas generales de los enfoques de umbralización aún se aplican. Un umbral establecido demasiado alto puede pasar por alto información importante. Por otro lado, un umbral establecido demasiado bajo identificará erróneamente información irrelevante (como ruido) como importante. Es difícil proporcionar un umbral genérico que funcione bien en todas las imágenes. Todavía no existe un enfoque probado y comprobado para este problema.

Conclusión

El algoritmo Canny se adapta a varios entornos. Sus parámetros permiten que se adapte al reconocimiento de bordes de diferentes características según los requisitos particulares de una implementación dada. En el artículo original de Canny, la derivación del filtro óptimo condujo a un filtro de respuesta de impulso finito , que puede ser lento de calcular en el dominio espacial si la cantidad de suavizado requerida es importante (el filtro tendrá un gran soporte espacial en ese caso). Por esta razón, a menudo se sugiere utilizar la forma de respuesta de impulso infinito de Rachid Deriche del filtro de Canny (el detector Canny-Deriche ), que es recursivo y que se puede calcular en una cantidad de tiempo fija y corta para cualquier cantidad de suavizado deseada. La segunda forma es adecuada para implementaciones en tiempo real en FPGA o DSP , o PC integrados muy rápidos. En este contexto, sin embargo, la implementación recursiva regular del operador Canny no da una buena aproximación de la simetría rotacional y, por lo tanto, da un sesgo hacia los bordes horizontales y verticales.

Véase también

• Visión por computadora
• Procesamiento de imágenes digitales
• Detección de características (visión por computadora)
• Extracción de características
• Detección de crestas
• Máscara de brújula Robinson
• Espacio de escala

Referencias

1. Li, Q., Wang, B. y Fan, S. (2009). Examinar publicaciones de conferencias Ciencias de la computación e ingeniería ... Ayuda para trabajar con resúmenes Un algoritmo de detección de bordes CANNY mejorado. En 2009, Actas del Segundo taller internacional sobre ciencias de la computación e ingeniería: WCSE 2009: 28-30 de octubre de 2009, Qingdao, China (pp. 497-500). Los Alamitos, CA: IEEE Computer Society
2. Zhou, P., Ye, W. y Wang, Q. (2011). Un algoritmo Canny mejorado para la detección de bordes. Journal of Computational Information Systems, 7(5), 1516-1523.
3. Otsu N. Un método de selección de umbral a partir de histogramas de niveles de gris. IEEE Trans Systems, Man and Cybernetics, 9(1):62-66,1979.
4. Mallat S, Zhong S. Caracterización de señales de bordes multiescala [J]. IEEE Trans on PAMI, 1992, 14 (7):710-732.
5. Gebäck, T.; Koumoutsakos, P. (2009). "Detección de bordes en imágenes de microscopía utilizando curvas pequeñas". BMC Bioinformatics . 10 : 75. doi : 10.1186/1471-2105-10-75 . PMC  2663783 . PMID  19257905.

• Canny, J., Un enfoque computacional para la detección de bordes , IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6):679–698, 1986.
• R. Deriche, Uso de los criterios de Canny para derivar un detector de bordes óptimo implementado recursivamente , Int. J. Computer Vision, Vol. 1, págs. 167–187, abril de 1987.
• Lindeberg, Tony "Detección de bordes y detección de crestas con selección automática de escala", International Journal of Computer Vision, 30, 2, págs. 117-154, 1998. (Incluye el enfoque diferencial para la supresión no máxima).
• Kimmel, Ron y Bruckstein, Alfred M. "Sobre cruces por cero laplacianos regularizados y otros integradores de bordes óptimos", International Journal of Computer Vision, 53(3):225–243, 2003. (Incluye la interpretación variacional geométrica para el detector de bordes Haralick-Canny).
• Moeslund, T. (23 de marzo de 2009). Canny Edge Detection. Consultado el 3 de diciembre de 2014.
• Thomas B. Moeslund. Procesamiento de imágenes y vídeos. Agosto de 2008
• Green, B. (1 de enero de 2002). Tutorial de detección de bordes de Canny. Consultado el 3 de diciembre de 2014; archivado aquí

Enlaces externos

• Página de inicio de John Canny
• Lista de publicaciones de Rachid Deriche
• Publicaciones de la revista Ron Kimmel
• Detección de bordes de Canny en C++ OpenCV
• Detección de bordes astuta en Python OpenCV Archivado el 29 de abril de 2014 en Wayback Machine
• Canny Edge World: vídeo de ejemplo