Detector de esquinas

La detección de esquinas es un acercamiento usado en los sistemas de visión por computadora para extraer ciertos tipos de rasgos e inferir el contenido de una imagen. La detección de esquinas frecuentemente se usa en la detección de movimiento, análisis de imagen, rastreo en video, modelado 3D y reconocimiento de objetos entre otros. La detección de esquinas se solapa con un tema más abarcador: la detección de puntos de interés.

Formalización

Una esquina puede definirse como la intersección de dos bordes. También puede definirse como un punto para el que hay dos direcciones de bordes dominantes y diferentes en una vecindad local del punto.

Un punto de interés es un punto en una imagen que tiene una posición bien definida y puede ser detectado de forma robusta. Esto significa que un punto de interés puede ser una esquina pero también puede ser, por ejemplo, un punto aislado de intensidad local máxima o mínima, final de líneas, o un punto en una curva donde la curvatura es localmente máxima.

En la práctica, los métodos de detección de esquinas son llamados detección de puntos de interés en general. Como una consecuencia, si solo esquinas serán descubiertas es necesario hacer un análisis local de detección de puntos de interés para determinar cuales de estos son las esquinas reales. Existen detectores de bordes que pueden usarse para descubrir esquinas con post-procesado, estos son el operador Kirsch y el Frei-Chen masking set.​

"Esquinas", "puntos de interés" y "rasgos";se usan en la literatura a veces indistintamente, confundiendo el problema. Hay específicamente, algunos detectores usados en el reconocimiento de regiones que pueden ser llamados operadores de puntos de interés, pero que a veces son erróneamente llamados detectores de esquinas. Los detectores de esquinas normalmente no son muy robustos y a menudo requieren supervisión especializada o la introducción de grandes redundancias para impedir el efecto de errores individuales en la tarea de reconocimiento.

Una forma de determinar la calidad de un detector de esquinas es su habilidad de descubrir la misma esquina en múltiples imágenes similares, bajo condiciones de iluminación diferentes, traslación y rotación entre otras transformaciones. Un acercamiento simple para la detección de esquinas en imágenes es usando la correlación, pero este es costoso computacionalmente y suboptimal. Un acercamiento alternativo frecuentemente usado es basado en un método propuesto por Harris y Stephens, que a su vez es una mejora del de Moravec.

El algoritmo de Moravec para la detección de esquinas

Éste es uno de los primeros algoritmos de detección de esquinas.​ El algoritmo analiza cada píxel en la imagen para ver si hay una esquina, considerando la similitud con un parche centrado en el píxel cercano, solapando así los parches. La similitud es moderada tomando la suma de diferencias cuadradas (SDC) entre los dos parches. Un bajo número indica más similitud.

Si el píxel está en una región de intensidad uniforme, entonces los parches cercanos parecerán similares. Si el píxel está en un borde, entonces los parches cercanos en una dirección perpendicular al borde se verán bastante diferentes, pero los cercanos en una dirección paralela al borde solo producirán un pequeño cambio. Si el píxel está en un rasgo con variación en todas las direcciones, entonces ninguno de los parches cercanos parecerá similar.

La fuerza de la esquina se define como el SDC más pequeño entre el parche y sus vecinos (horizontal, vertical y en las dos diagonales). Si este número es localmente máximo, entonces un rasgo de interés está presente. Uno de los problemas principales con este operador es que no es isotrópico: si existe un borde que no está en la dirección de la vecindad, entonces el SSD más pequeño será el más grande y el borde se escogerá incorrectamente como un punto de interés.

El algoritmo Harris & Stephens / Plessey / el Shi-Tomasi detector de esquinas

Harris y Stephens​ mejoró el detector de esquinas de Moravec considerando el diferencial del valor de la esquina directamente con respecto a la dirección, en lugar de usar los parches cambiados. (Este valor de la esquina es a menudo llamado autocorrelación, en trabajos en los que se describe este detector). Sin pérdida de generalidad, se asumirá que se usa una imagen bidimensional de escala de grises. Definamos esta imagen por $I$. Tomemos un parche de la imagen encima del área $(u,v)$ y cambiándolo por $(x,y)$. La suma ponderada de las diferencias cuadradas (SDC) entre estos dos parches, denotada por $S$, viene dada por:

$S(x,y)=\sum _{u}\sum _{v}w(u,v)\,\left(I(u+x,v+y)-I(u,v)\right)^{2}$

$I(u+x,v+y)$ puede aproximarse por una serie de Taylor. Definamos a $I_{x}$ y $I_{y}$ como las derivadas parciales de $I$, tal que:

$I(u+x,v+y)\approx I(u,v)+I_{x}(u,v)x+I_{y}(u,v)y$

Esto produce la aproximación:

$S(x,y)\approx \sum _{u}\sum _{v}w(u,v)\,\left(I_{x}(u,v)x+I_{y}(u,v)y\right)^{2},$

que puede escribirse en la forma de la matriz:

$S(x,y)\approx {\begin{pmatrix}x&y\end{pmatrix}}A{\begin{pmatrix}x\\y\end{pmatrix}},$

donde A es el structure tensor,

$A=\sum _{u}\sum _{v}w(u,v){\begin{bmatrix}I_{x}^{2}&I_{x}I_{y}\\I_{x}I_{y}&I_{y}^{2}\end{bmatrix}}={\begin{bmatrix}\langle I_{x}^{2}\rangle &\langle I_{x}I_{y}\rangle \\\langle I_{x}I_{y}\rangle &\langle I_{y}^{2}\rangle \end{bmatrix}}$

Esta matriz es la de Harris, y pudiéndose ver los promedios (es decir la suma sobre de $(u,v)$). Si una ventana redonda (o circularmente pesó la ventana, es usada como una función gaussiana, entonces la respuesta será isotrópica.

Una esquina (o en general un punto de interés) se caracteriza por una variación grande de $S$ en todas las direcciones del vector ${\begin{pmatrix}x&y\end{pmatrix}}$. Analizando los valores propios de $A$, esta caracterización puede expresarse de la manera siguiente: $A$ debe tener dos valores propios "grandes" para ser un punto de interés. Basado en las magnitudes de los valores propios, puede inferirse lo siguiente:

1. Si $\lambda _{1}\approx 0$ y $\lambda _{2}\approx 0$ entonces este pixel $(x,y)$ no tiene ningún rasgo de interés.
2. Si $\lambda _{1}\approx 0$ y $\lambda _{2}$ tiene algún valor positivo grande, entonces existe un borde.
3. Si $\lambda _{1}$ y $\lambda _{2}$ tienen los valores positivos grandes, entonces existe una esquina.

Harris y Stephens nota de que el cómputo exacto de los valores propios es costoso computacionalmente, dado que requiere el cómputo de una raíz cuadrada, y en cambio hace pensar en la función $M_{c}$ dónde $\kappa$ es un parámetro de sensibilidad:

$M_{c}=\lambda _{1}\lambda _{2}-\kappa \,(\lambda _{1}+\lambda _{2})^{2}=\operatorname {det} (A)-\kappa \,\operatorname {trace} ^{2}(A)$

Por consiguiente, el algoritmo no tiene que computar la descomposición en valores propios de la matriz $A$ y en cambio es suficiente evaluar el determinante y la traza de $A$ para encontrar las esquinas, o el rasgo de interés en general.

El detector de esquinas Shi-Tomasi​ computa el $min(\lambda _{1},\lambda _{2})$ porque bajo ciertas supusiciones, las esquinas son más estables para rastrear. Este método también es llamado el detector de esquinas Kanade-Tomasi.

El valor de $\kappa$ tiene que ser determinada empíricamente, y en los valores de la literatura en el rango 0.04–0.15 es el que se ha dado como factible.

Uno puede evitar la escena el parámetro $\kappa$ usando Noble's^{[cita requerida]} la medida de la esquina $M_{c}'$ que suma a la media armónica de los valores propios:

$M_{c}'=2{\frac {\operatorname {det} (A)}{\operatorname {trace} (A)+\epsilon }},$

$\epsilon$ que es una constante positiva pequeña. La matriz de covarianza para la posición de la esquina es $A^{-1}$, es decir:

${\frac {1}{\langle I_{x}^{2}\rangle \langle I_{y}^{2}\rangle -\langle I_{x}I_{y}\rangle ^{2}}}{\begin{bmatrix}\langle I_{y}^{2}\rangle &-\langle I_{x}I_{y}\rangle \\-\langle I_{x}I_{y}\rangle &\langle I_{x}^{2}\rangle \end{bmatrix}}.$

Otros algoritmos y métodos

El detector de esquinas Förstner:

En algunos casos, uno puede desear computar la situación de una esquina con la exactitud del subpixel. Para lograr una solución aproximada, el algoritmo Förstner​ resuelve el punto más cerca para todas las líneas tangentes a la esquina en una ventana dada. El algoritmo se basa en el hecho que para una esquina ideal, se cruzan las líneas tangentes en un solo punto.

Algoritmo de Förstner

Detectores de rasgos basados en AST:

AST es una sigla que representa la prueba del segmento acelerada en inglés. Esta prueba es una versión relajada del detector SUSAN.​ En lugar de evaluar el disco de los pixeles en un círculo de Bresenham de radio $r$ alrededor del punto candidato considerado. Si $n$ los pixeles inmediatos son todos más luminosos que el núcleo $t$ por lo menos o todos más oscuros que el núcleo entonces se considera que el pixel bajo el núcleo es un rasgo por $t$. Esta prueba se informa para producir los rasgos muy estables.​ Los árboles de decisión cortos construyendo para este problema resultan en la mayoría de los detectores de rasgos computacionalmente eficientes.

El primer algoritmo de descubrimiento de esquinas basado en el AST es FAST (features from accelerated segment test).​ Aunque $r$ puede tomar cualquier valor, FAST sólo usa un valor de 3 (correspondiendo a un círculo de 16 pixeles de circunferencia), y muestra de las pruebas que los resultados más buenos se logran con $n$ que es 9. Este valor de $n$ es el más bajo en que no se descubren bordes. El orden en que se prueban los pixeles es determinado por el algoritmo ID3 de un conjunto de entrenamiento de imágenes.

La síntesis automática de detectores:

Trujillo y Olague​ introdujeron un método en el cual se usa la programación genética para sintetizar a operadores de imagen que pueden descubrir los puntos de interés automáticamente. Los conjuntos de funciones contienen que funciones primitivas comunes en muchos diseños. El rendimiento es probado experimentalmente con el uso de secuencias de imágenes de prueba y entrenamiento modificadas progresivamente. El propósito de los algoritmos de programación genética es el uso de una solución competitiva al problema de la detección de puntos de interés.

Véase también

• Reconocimiento de regiones
• Adaptación de forma afín

• Datos: Q697320