Detector de bordes canny - Canny edge detector

El detector de bordes Canny aplicado a una fotografía en color de una máquina de vapor.

La imagen original.

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 las imágenes. Fue desarrollado por John F. Canny en 1986. Canny también produjo una teoría computacional de detección de bordes que explica por qué funciona la técnica.

Desarrollo

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

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 en la imagen.
El punto del borde detectado por el operador debe ubicarse con precisión en el centro del borde.
Un borde determinado en la imagen solo debe marcarse una vez y, cuando 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 determinada . La función óptima en el detector de Canny se describe mediante la suma de cuatro términos exponenciales , pero puede aproximarse mediante la primera derivada de un gaussiano .

Entre los métodos de detección de bordes desarrollados hasta ahora, el algoritmo de detección de bordes de Canny es uno de los métodos más estrictamente definidos que proporciona una detección buena y confiable. Debido a su optimización para cumplir con los tres criterios para la 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:

Aplique el filtro gaussiano para suavizar la imagen con el fin de eliminar el ruido.
Encuentra los gradientes de intensidad de la imagen.
Aplique umbral de magnitud de gradiente o supresión de corte de límite inferior para deshacerse de la respuesta falsa a la detección de bordes
Aplicar doble umbral para determinar posibles bordes
Seguimiento de bordes por histéresis : finalice la detección de bordes suprimiendo todos los demás bordes que son débiles y no están conectados a bordes fuertes.

Filtro gaussiano

La imagen después de una máscara gaussiana de 5 × 5 se ha pasado 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 una falsa detección causada por él. Para suavizar la imagen, se convoluciona 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}}} \ derecha); 1 \ leq i, j \ leq (2k + 1)}$

A continuación se muestra un ejemplo de un filtro gaussiano de 5 × 5, que se utiliza para crear la imagen adyacente, con = 1. (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 {bmatrixf}} * \ .}

Es importante comprender que la selección del tamaño del kernel 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 5 × 5 es un buen tamaño para la mayoría de los casos, pero esto también variará dependiendo de 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 usa 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:

{\ 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 puede ser calculado usando el hypot función y atan2 es la función arco tangente 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 °). Una dirección de borde que cae en cada región de color se establecerá en un valor de ángulo específico, por ejemplo, θ en mapas de [0 °, 22,5 °] o [157,5 °, 180 °] a 0 °.

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

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

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

Compare la fuerza del borde del píxel actual con la fuerza del borde del píxel en las direcciones de gradiente positiva y negativa.
Si la fuerza del borde del píxel actual es la mayor en comparación con los otros 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 está arriba y abajo en el eje vertical ), se conservará el valor. De lo contrario, se suprimirá el valor.

En algunas implementaciones, el algoritmo categoriza las direcciones continuas del gradiente en un pequeño conjunto de direcciones discretas y luego mueve un filtro de 3x3 sobre la salida del paso anterior (es decir, la fuerza del borde y las direcciones del gradiente). En cada píxel, suprime la fuerza 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 su magnitud de gradiente es mayor que las magnitudes en 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 su magnitud de gradiente es mayor que las magnitudes en píxeles en las direcciones norte y sur ,
si el ángulo de gradiente redondeado es 135 ° (es decir, el borde está en la dirección noreste-suroeste), se considerará que el punto está en el borde si su magnitud de gradiente es mayor que las magnitudes en píxeles en el noroeste y sureste direcciones,
si el ángulo de gradiente redondeado es de 45 ° (es decir, el borde está en la dirección noroeste-sureste), se considerará que el punto está en el borde si su magnitud de gradiente es mayor que las magnitudes en píxeles en el noreste y sur -Direcciones oeste .

En implementaciones más precisas, se utiliza la interpolación lineal entre los dos píxeles vecinos que se encuentran en la dirección del gradiente. Por ejemplo, si el ángulo de gradiente es de entre 89 ° y 180 °, la interpolación entre los gradientes en los norte y norte-este pixeles dará un valor interpolado, y la interpolación entre los sur y sur-oeste pixeles dará el otro (usando las convenciones del último párrafo). La magnitud del degradado 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.

Umbral doble

Después de la aplicación de 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 causados por el ruido y la variación de color. Para tener en cuenta estas respuestas falsas, es esencial filtrar los píxeles de borde con un valor de gradiente débil y conservar 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 degradado 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 degradado 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 degradado de un píxel de borde es menor que el valor de umbral bajo, se suprimirá. Los dos valores 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

Hasta ahora, los píxeles del borde fuerte deberían estar involucrados en la imagen del borde final, ya que se extraen de los bordes reales de la imagen. Sin embargo, habrá cierto debate sobre los píxeles del borde débil, ya que estos píxeles pueden extraerse del borde verdadero o de las variaciones de ruido / color. Para lograr un resultado preciso, se deben eliminar los bordes débiles causados por las últimas razones. Por lo general, un píxel de borde débil causado por bordes verdaderos se conectará a un píxel de borde fuerte mientras que las respuestas al ruido no están conectadas. Para realizar un seguimiento de la conexión de borde, el análisis de blob se aplica al observar 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 la mancha, ese punto de borde débil puede identificarse como uno que debe conservarse.

Tutorial del algoritmo

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

La imagen original

La imagen se ha reducido a escala de grises y se ha aplicado un filtro gaussiano de 5x5 con σ = 1,4

El gradiente de intensidad de la imagen anterior. Los bordes de la imagen se han manejado mediante la replicación.

Supresión no máxima aplicada a la imagen anterior.

Doble umbral aplicado a la imagen anterior. Los píxeles débiles son aquellos con un valor de degradado entre 0,1 y 0,3. Los píxeles fuertes tienen un valor de degradado superior a 0,3

Histéresis aplicada a la imagen anterior

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:

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 falten bordes débiles y la aparición de bordes aislados en el resultado.
Para el cálculo de la amplitud del gradiente, el antiguo algoritmo de detección de bordes de Canny usa el centro en una pequeña ventana de vecindad de 2 × 2 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 bordes falsos y perder bordes reales.
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, diferentes áreas locales necesitarán valores de umbral muy diferentes para encontrar con precisión los bordes reales. Además, los valores de los umbrales globales se determinan manualmente mediante experimentos en el método tradicional, lo que conduce a una complejidad de cálculo cuando es necesario tratar un gran número de imágenes diferentes.
El resultado de la detección tradicional no puede alcanzar una alta precisión satisfactoria de una sola respuesta para cada borde; aparecerán respuestas multipunto.

Para abordar estos defectos, en los siguientes párrafos se presenta una mejora del algoritmo de borde astuto.

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 suave en ambos. Sin embargo, para alcanzar una alta precisión de detección del borde real, se espera que se aplique un efecto más suave al ruido y que 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. Cuanto mayor sea la discontinuidad, menor será el valor de peso establecido para el filtro suave en ese punto. Por el contrario, cuanto menor sea la discontinuidad entre los valores de la escala de grises, mayor será el valor de peso establecido en el filtro. El proceso para implementar este filtro adaptativo se puede resumir en cinco pasos:

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

2. Calcule el valor del gradiente y

{\ Displaystyle G_ {x} (x, y)}

{\ Displaystyle G_ {y} (x, y)}

3. Calcule el peso de acuerdo con 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, siga haciendo el segundo paso

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

La magnitud y la dirección del gradiente se pueden calcular con una variedad de diferentes operadores de detección de bordes, 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 de 5x5 que reducirá el ruido o el filtro Scharr que tiene una mejor simetría rotacional. Otras opciones comunes son Prewitt (utilizado por Zhou) y Roberts Cross .

Método robusto para determinar el valor de doble umbral

Para resolver los desafíos en los que es difícil determinar empíricamente el valor de doble umbral, el método de Otsu se puede utilizar en la imagen de magnitud de gradiente suprimido no máximo para generar el umbral alto. En este caso, el umbral bajo se establece típicamente a la mitad del umbral alto. 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 usar pares de valor / conteo en lugar de un histograma completo.

El adelgazamiento del borde

Si bien la detección de bordes tradicional de Canny implementa 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 adelgazar el borde detectado.

Uso de Curvelets

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 fuerza de los bordes en la imagen, a los que luego se aplican los pasos 3 a 5 del algoritmo Canny. Los curvelets 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.

Formulación geométrica diferencial

Un enfoque más refinado para obtener bordes con precisión de subpíxeles es utilizar el enfoque de detección de borde diferencial , 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 segunda derivada a lo largo de la dirección del gradiente, es el resultado de minimizar una función de Kronrod-Minkowski mientras se maximiza la integral sobre la alineación de el borde con el campo degradado (Kimmel y Bruckstein 2003). Consulte el artículo sobre cruces por cero regularizados de Laplacia y otros integradores de borde ó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 eficacia del algoritmo.

El tamaño del filtro gaussiano: el filtro de suavizado utilizado en la primera etapa afecta directamente los resultados del algoritmo de Canny. Los filtros más pequeños provocan menos borrosidad y permiten la detección de líneas pequeñas y nítidas. Un filtro más grande causa más borrosidad, difuminando el valor de un píxel dado 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 más flexibilidad que un enfoque de umbral único, pero aún se aplican los problemas generales de los enfoques de umbral. Un umbral establecido demasiado alto puede perder información importante. Por otro lado, un umbral demasiado bajo identificará falsamente la información irrelevante (como el ruido) como importante. Es difícil dar un umbral genérico que funcione bien en todas las imágenes. Todavía no existe un enfoque probado para este problema.

Conclusión

El algoritmo Canny es adaptable a varios entornos. Sus parámetros permiten que se adapte al reconocimiento de bordes de diferentes características en función de los requisitos particulares de una implementación determinada. 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 corta y fija para cualquier cantidad deseada de suavizado. . La segunda forma es adecuada para implementaciones en tiempo real en FPGA o DSP , o en PC integradas muy rápidas. 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.

Ver también

Referencias

Canny, J., A Computational Approach To Edge Detection , IEEE Transactions on Pattern Analysis and Machine Intelligence, 8 (6): 679–698, 1986.
R. Deriche, Utilizando los criterios de Canny para derivar un detector de bordes óptimo implementado de forma recursiva , 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, pp 117-154, 1998. (Incluye el enfoque diferencial para la supresión no máxima).
Kimmel, Ron y Bruckstein, Alfred M. "Sobre los cruces por cero regularizados de Laplacia y otros integradores de bordes óptimos", International Journal of Computer Vision, 53 (3): 225–243, 2003. (Incluye la interpretación geométrica variacional para Haralick-Canny detector de bordes.)
Moeslund, T. (2009, 23 de marzo). Canny Edge Detection. Consultado el 3 de diciembre de 2014.
Thomas B. Moeslund. Procesamiento de imágenes y videos. Agosto de 2008
Green, B. (2002, 1 de enero). Tutorial de Canny Edge Detection. Consultado el 3 de diciembre de 2014 ; archivado aquí

Languages

In other projects