Características de la prueba de segmento acelerada

Las características de la prueba de segmento acelerado (FAST) son un método de detección de esquinas , que podría usarse para extraer puntos de características y luego usarse para rastrear y mapear objetos en muchas tareas de visión por computadora . El detector de esquinas FAST fue desarrollado originalmente por Edward Rosten y Tom Drummond, y se publicó en 2006. ^[1] La ventaja más prometedora del detector de esquinas FAST es su eficiencia computacional. Haciendo referencia a su nombre, es de hecho más rápido que muchos otros métodos de extracción de características conocidos, como la diferencia de Gaussianas (DoG) utilizada por los detectores SIFT , SUSAN y Harris . Además, cuando se aplican técnicas de aprendizaje automático, se puede lograr un rendimiento superior en términos de tiempo de cálculo y recursos. El detector de esquinas FAST es muy adecuado para la aplicación de procesamiento de video en tiempo real debido a este rendimiento de alta velocidad.

El detector de esquinas FAST utiliza un círculo de 16 píxeles (un círculo de Bresenham de radio 3) para clasificar si un punto candidato p es en realidad una esquina. Cada píxel del círculo está etiquetado del número entero 1 al 16 en el sentido de las agujas del reloj. Si un conjunto de N píxeles contiguos en el círculo son todos más brillantes que la intensidad del píxel candidato p (indicado por I _p ) más un valor umbral t o todos más oscuros que la intensidad del píxel candidato p menos el valor umbral t, entonces p se clasifica como esquina. Las condiciones se pueden escribir como:

• Condición 1: Un conjunto de N píxeles contiguos S, , (una esquina oscura sobre un fondo brillante)${\displaystyle \para todo x\en S}$${\displaystyle I_{x}>I_{p}+t}$
• Condición 2: Un conjunto de N píxeles contiguos S, , (una esquina brillante sobre un fondo oscuro)${\displaystyle \para todo x\en S}$${\displaystyle I_{x}<I_{p}-t}$

Entonces, cuando se cumple cualquiera de las dos condiciones, el candidato p puede clasificarse como una esquina. Existe una compensación entre elegir N, la cantidad de píxeles contiguos y el valor umbral t. Por un lado, la cantidad de puntos de esquina detectados no debe ser demasiado grande, por otro lado, el alto rendimiento no debe lograrse sacrificando la eficiencia computacional. Sin la mejora del aprendizaje automático , N generalmente se elige como 12. Se podría aplicar un método de prueba de alta velocidad para excluir los puntos que no sean esquinas.

La prueba de alta velocidad para rechazar puntos que no sean esquinas se realiza examinando 4 píxeles de ejemplo, a saber, los píxeles 1, 9, 5 y 13. Dado que debería haber al menos 12 píxeles contiguos que sean más brillantes o más oscuros que la esquina candidata, debería haber al menos 3 píxeles de estos 4 píxeles de ejemplo que sean más brillantes o más oscuros que la esquina candidata. En primer lugar, se examinan los píxeles 1 y 9; si tanto I ₁ como I ₉ están dentro de [I _p - t, I _p + t], entonces el candidato p no es una esquina. De lo contrario, se examinan más a fondo los píxeles 5 y 13 para verificar si tres de ellos son más brillantes que I _p + t o más oscuros que I _p - t. Si existen 3 de ellos que son más brillantes o más oscuros, se examinan los píxeles restantes para llegar a una conclusión final. Y según el inventor en su primer artículo ^[2] , en promedio se necesitan 3,8 píxeles para verificar el píxel de esquina candidato. En comparación con los 8,5 píxeles para cada esquina candidata, 3,8 es realmente una gran reducción que podría mejorar enormemente el rendimiento.

Sin embargo, este método de prueba presenta varias debilidades:

1. La prueba de alta velocidad no se puede generalizar bien para N < 12. Si N < 12, sería posible que un candidato p sea una esquina y solo 2 de los 4 píxeles de prueba de ejemplo sean más brillantes I _p + t o más oscuros que I _p - t.
2. La eficiencia del detector depende de la elección y el orden de estos píxeles de prueba seleccionados. Sin embargo, es poco probable que los píxeles elegidos sean óptimos, lo que genera preocupaciones sobre la distribución de las apariencias de las esquinas.
3. Se detectan múltiples características adyacentes entre sí.

Para abordar los dos primeros puntos débiles de la prueba de alta velocidad, se introduce un enfoque de aprendizaje automático para ayudar a mejorar el algoritmo de detección. Este enfoque de aprendizaje automático funciona en dos etapas. En primer lugar, se procesa la detección de esquinas con una N determinada en un conjunto de imágenes de entrenamiento que son preferibles del dominio de la aplicación de destino. Las esquinas se detectan a través de la implementación más simple que literalmente extrae un anillo de 16 píxeles y compara los valores de intensidad con un umbral apropiado.

Para el candidato p, cada posición en el círculo x ∈ {1, 2, 3, ..., 16} se puede denotar mediante p→x. El estado de cada píxel, S _p→x, debe estar en uno de los tres estados siguientes:

• d, I _p→x ≤ I _p - t (más oscuro)
• s, I _p - t ≤ I _p→x ≤ I _p + t (similares)
• b, I _p→x ≥ I _p + t (más brillante)

Luego, al elegir una x (igual para todos los p), se divide P (el conjunto de todos los píxeles de todas las imágenes de entrenamiento) en 3 subconjuntos diferentes, P _d , P _s , P _b donde:

• P _d = {p ∈ P : S _p→x = d }
• P _s = {p ∈ P : S _p→x = s }
• Pb ₌ {p ∈ P : S _p→x = b }

En segundo lugar, se aplica un algoritmo de árbol de decisión , el algoritmo ID3 , a las 16 ubicaciones para lograr la máxima ganancia de información . Sea K _p una variable booleana que indica si p es una esquina, entonces se utiliza la entropía de K _p para medir la información de que p es una esquina. Para un conjunto de píxeles Q, la entropía total de K _Q (no normalizada) es:

• H(Q) = ( c + n ) log ₂ ( c + n ) - obstruir ₂ c - nlog ₂ n
  • donde c = |{ i ∈ Q: K _i es verdadero }| (número de esquinas)
  • donde n = |{ i ∈ Q: K _i es falso}| (número de no esquinas)

La ganancia de información puede entonces representarse como:

• H _g = H(P) - H(P _b ) - H(P _s ) - H(P _d )

Se aplica un proceso recursivo a cada subconjunto para seleccionar cada x que pueda maximizar la ganancia de información. Por ejemplo, primero se selecciona una x para dividir P en P _d , P _s , P _b con la mayor cantidad de información; luego, para cada subconjunto P _d , P _s , P _b , se selecciona otra y para obtener la mayor ganancia de información (observe que la y podría ser la misma que x ). Este proceso recursivo termina cuando la entropía es cero, de modo que todos los píxeles de ese subconjunto son esquinas o no son esquinas.

Este árbol de decisiones generado se puede convertir luego en código de programación, como C y C++ , que es simplemente un conjunto de instrucciones if-else anidadas. Para fines de optimización, se utiliza la optimización guiada por perfiles para compilar el código. El código compilado se utiliza como detector de esquinas más adelante para otras imágenes.

Tenga en cuenta que las esquinas detectadas con este algoritmo de árbol de decisiones deberían ser ligeramente diferentes de los resultados obtenidos con el detector de prueba de segmentos. Esto se debe a que ese modelo de árbol de decisiones depende de los datos de entrenamiento, que no pudieron cubrir todas las esquinas posibles.

"Dado que la prueba de segmento no calcula una función de respuesta de esquina, no se puede aplicar una supresión no máxima directamente a las características resultantes". Sin embargo, si N es fijo, para cada píxel p la intensidad de la esquina se define como el valor máximo de t que hace que p sea una esquina. Por lo tanto, se podrían utilizar dos enfoques:

• Se podría aplicar un algoritmo de búsqueda binaria para encontrar el valor t más grande para el cual p sigue siendo un vértice. De modo que cada vez se establece un valor t diferente para el algoritmo del árbol de decisión. Cuando logra encontrar el valor t más grande, ese valor t puede considerarse como la fuerza del vértice.
• Otro enfoque es un esquema de iteración, donde cada vez t se incrementa hasta el valor más pequeño que pasa la prueba.

El detector FAST-ER es una mejora del detector FAST que utiliza un algoritmo metaheurístico , en este caso el recocido simulado . De modo que después de la optimización, la estructura del árbol de decisión estaría optimizada y sería adecuada para puntos con alta repetibilidad. Sin embargo, dado que el recocido simulado es un algoritmo metaheurístico, cada vez el algoritmo generaría un árbol de decisión optimizado diferente. Por lo tanto, es mejor realizar una gran cantidad de iteraciones de manera eficiente para encontrar una solución que se acerque a la óptima real. Según Rosten, se necesitan aproximadamente 200 horas en un Pentium 4 a 3 GHz, lo que equivale a 100 repeticiones de 100 000 iteraciones para optimizar el detector FAST.

En la investigación de Rosten, ^[3] los detectores FAST y FAST-ER se evalúan en varios conjuntos de datos diferentes y se comparan con los detectores de esquina DoG , Harris , Harris-Laplace , Shi-Tomasi y SUSAN .

Los ajustes de parámetros para los detectores (excepto FAST) son los siguientes:

• El resultado de la prueba de repetibilidad se presenta como el área promedio bajo las curvas de repetibilidad para 0-2000 esquinas por cuadro en todos los conjuntos de datos (excepto el ruido aditivo):

• Las pruebas de velocidad se realizaron en un ordenador Pentium 4-D de 3,0 GHz . El conjunto de datos se divide en un conjunto de entrenamiento y un conjunto de prueba. El conjunto de entrenamiento consta de 101 imágenes monocromáticas con una resolución de 992×668 píxeles. El conjunto de prueba consta de 4968 fotogramas de vídeo monocromático de 352×288 píxeles. Y el resultado es:

• Rosten, Edward; Tom Drummond (2005). "Fusionar puntos y líneas para un seguimiento de alto rendimiento". Décima Conferencia Internacional IEEE sobre Visión por Computador (ICCV'05) Volumen 1 (PDF) . Vol. 2. págs. 1508–1511. CiteSeerX  10.1.1.60.4715 . doi :10.1109/ICCV.2005.104. ISBN. 978-0-7695-2334-7.S2CID 1505168  .
• Rosten, Edward; Reid Porter; Tom Drummond (2010). "MÁS RÁPIDO y mejor: Un enfoque de aprendizaje automático para la detección de esquinas". IEEE Transactions on Pattern Analysis and Machine Intelligence . 32 (1): 105–119. arXiv : 0810.2434 . doi :10.1109/TPAMI.2008.275. PMID  19926902. S2CID  206764370.
• Rosten, Edward; Tom Drummond (2006). "Aprendizaje automático para detección de esquinas a alta velocidad". Visión artificial – ECCV 2006 (PDF) . Apuntes de clase en informática. Vol. 1. págs. 430–443. CiteSeerX  10.1.1.64.8513 . doi :10.1007/11744023_34. ISBN 978-3-540-33832-1.S2CID 1388140  . {{cite book}}: |journal=ignorado ( ayuda )

• Página de inicio de Advanced Vision