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 produjo una teoría computacional de detección de bordes que explica por qué funciona la técnica.

Desarrollo

La detección de bordes Canny 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 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 para abordar 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 detectar con precisión tantos bordes mostrados en la imagen como sea posible.
2. El punto del borde detectado por el operador debe localizarse con precisión en el centro del borde.
3. Un borde determinado de 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 un funcional determinado . 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 una gaussiana .

Entre los métodos de detección de bordes desarrollados hasta ahora, 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 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 Canny se puede dividir en cinco pasos diferentes:

1. Aplique el filtro gaussiano para suavizar la imagen y eliminar el ruido.
2. Encuentra los gradientes de intensidad de la imagen.
3. Aplique umbrales de magnitud de gradiente o supresión de límite inferior para eliminar respuestas espurias a la detección de bordes
4. Aplicar doble umbral para determinar posibles bordes
5. Borde de seguimiento 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 que se haya pasado una máscara gaussiana de 5 × 5 a través de cada píxel.

Dado que todos los resultados de la detección de bordes se ven fácilmente afectados por el ruido de la imagen, es esencial filtrar el ruido para evitar una detección falsa 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}}}\right);1\leq i,j\leq (2k+1)}$

A continuación se muestra un ejemplo de un filtro gaussiano de 5 × 5, utilizado para crear la imagen adyacente, con = 1. (El asterisco indica 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 comprender 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 5×5 es un buen tamaño para la mayoría de los casos, pero 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 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 en la dirección vertical (G _y ). A partir de esto se puede determinar la pendiente 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 usando 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 inferior

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

Se aplica la supresión del límite inferior para encontrar las ubicaciones con el cambio más pronunciado en el valor de intensidad. El algoritmo para cada píxel en la imagen degradada 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 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á encima y 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 del gradiente continuo en un pequeño conjunto de direcciones discretas y luego mueve un filtro de 3x3 sobre la salida del paso anterior (es decir, la intensidad del borde y las direcciones del 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 dirección norte-sur), se considerará que el punto está en el borde si su magnitud de gradiente es mayor que las magnitudes en los píxeles en las direcciones este y oeste ,
• si el ángulo de gradiente redondeado es de 90° (es decir, el borde está en dirección este-oeste), se considerará que el punto está en el borde si su magnitud de gradiente es mayor que las magnitudes en los píxeles en las direcciones norte y sur ,
• si el ángulo de gradiente redondeado es de 135° (es decir, el borde está en dirección noreste-suroeste), se considerará que el punto está en el borde si la magnitud de su gradiente es mayor que las magnitudes en los píxeles del noroeste y sureste. direcciones,
• si el ángulo de gradiente redondeado es de 45° (es decir, el borde está en dirección noroeste-sureste), se considerará que el punto está en el borde si su magnitud de gradiente es mayor que las magnitudes en los píxeles en el noreste y suroeste. direcciones.

En implementaciones más precisas, se utiliza la interpolación lineal entre los dos píxeles vecinos que se encuentran 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 (usando las convenciones del último párrafo). La magnitud del gradiente en el píxel central debe ser mayor que ambas 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 una supresión no máxima, los píxeles de borde restantes proporcionan una representación más precisa de los bordes reales de 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 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 superior al 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 umbral se determinan empíricamente y su definición dependerá del contenido de una imagen de entrada determinada.

Seguimiento de bordes por histéresis

Canny detección de bordes aplicada a una fotografía

Los píxeles de borde fuertes ciertamente deberían participar en la imagen de borde final; se considera que provienen de bordes reales de la imagen. Sin embargo, habrá cierto debate sobre los píxeles de los bordes débiles. Queremos determinar si estos píxeles provienen de un borde real o de variaciones de ruido/color. Los píxeles de borde débil deben descartarse si se trata de lo último. Este algoritmo utiliza la idea de que los píxeles de borde débiles de los bordes verdaderos (normalmente) estarán conectados a un píxel de borde fuerte mientras que las respuestas al ruido no están conectadas. Para rastrear la conexión del borde, se aplica el 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 involucrado en la mancha, ese punto de borde débil puede identificarse como uno que debe preservarse. Estos píxeles de borde débil se convierten en bordes fuertes que luego pueden hacer que se conserven los 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 robustez de 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 pierdan bordes débiles y la aparición de bordes aislados en el resultado.
2. Para el cálculo de la amplitud del gradiente, el antiguo algoritmo de detección de bordes Canny utiliza 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.
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, diferentes áreas locales necesitarán valores de umbral muy diferentes para encontrar con precisión los bordes reales. Además, los valores umbral globales se determinan manualmente mediante experimentos con el método tradicional, lo que conlleva una complejidad de cálculo cuando es necesario procesar un gran número de imágenes diferentes.
4. 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 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 suave en 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 necesaria ]} . 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 ponderación del 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 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 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 la 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 del umbral dual, se puede utilizar el método de Otsu ^[3] en la imagen de magnitud del gradiente suprimido no máximo para generar el umbral alto. En este caso, el umbral bajo normalmente se establece en la mitad del umbral alto. Dado que la imagen de magnitud del gradiente tiene un valor continuo sin un máximo bien definido, el método de Otsu debe adaptarse para utilizar pares valor/recuento 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 desarrollan una técnica de morfología matemática para adelgazar 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 fuerza de los bordes de la imagen, al 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 eliminar 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 utilizar el enfoque de detección diferencial de bordes , 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 espacial 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 un funcional de Kronrod-Minkowski mientras se maximiza la integral sobre la alineación de el borde con el campo 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 eficacia 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 provocan menos borrosidad y permiten la detección de líneas pequeñas y nítidas. Un filtro más grande provoca 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 más 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 problemas generales de los enfoques de umbralización. Un umbral demasiado alto puede pasar por alto información importante. Por otro lado, un umbral demasiado bajo identificará falsamente información irrelevante (como el ruido) como importante. Es difícil dar un umbral genérico que funcione bien en todas las imágenes. Aún no existe ningún enfoque probado para este problema.

Conclusión

El algoritmo Canny es adaptable a diversos entornos. Sus parámetros le permiten adaptarse al reconocimiento de bordes de diferentes características según 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 , cuyo cálculo puede ser lento 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 al impulso infinito del filtro de Canny de Rachid Deriche (el detector Canny-Driche ), que es recursivo y que se puede calcular en un período de tiempo corto y fijo para cualquier cantidad de suavizado deseada. . La segunda forma es adecuada para implementaciones en tiempo real en FPGA o DSP , o PC integradas muy rápidas. En este contexto, sin embargo, la implementación recursiva regular del operador Canny no proporciona una buena aproximación de la simetría rotacional y, por tanto, da una tendencia hacia los bordes horizontales y verticales.

Ver también

• Visión por computador
• Procesando imagen digital
• Detección de características (visión por computadora)
• Extracción de características
• Detección de crestas
• Espacio de escala

Referencias

1. Li, Q., Wang, B. y Fan, S. (2009). Explorar publicaciones de conferencias Ingeniería y Ciencias de la Computación... Ayuda para trabajar con resúmenes Un algoritmo de detección de bordes CANNY mejorado. En 2009, actas del Segundo Taller Internacional sobre Ingeniería y Ciencias de la Computación: WCSE 2009: 28 a 30 de octubre de 2009, Qingdao, China (págs. 497 a 500). Los Alamitos, CA: Sociedad de Computación IEEE
2. Zhou, P., Ye, W. y Wang, Q. (2011). Un algoritmo Canny mejorado para la detección de bordes. Revista de sistemas de información computacional, 7 (5), 1516-1523.
3. Otsu N. Un método de selección de umbral a partir de histogramas de niveles de grises. IEEE Trans Systems, Man and Cybernetics, 9(1):62-66,1979.
4. Mallat S, Zhong S. Caracterización de señales de bordes de múltiples escalas [J]. IEEE Trans en PAMI, 1992, 14 (7):710-732.
5. Gebäck, T.; Koumoutsakos, P. (2009). "Detección de bordes en imágenes de microscopía mediante curvas". Bioinformática BMC . 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 de forma recursiva , Int. J. Visión por computadora, 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 de Haralick-Canny detector de bordes.)
• Moeslund, T. (23 de marzo de 2009). Detección de bordes astuta. Consultado el 3 de diciembre de 2014.
• Thomas B. Moeslund. Procesamiento de Imágenes y Vídeo. agosto de 2008
• Green, B. (2002, 1 de enero). 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 revistas de Ron Kimmel
• Detección de bordes astuta en c++ OpenCV
• Detección de bordes canny en Python OpenCV Archivado el 29 de abril de 2014 en Wayback Machine.
• Canny Edge World - vídeo de ejemplo