Las características de la prueba de segmento acelerado (FAST) es 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. En referencia a su nombre, de hecho es más rápido que muchos otros métodos de extracción de características bien conocidos, como la diferencia de gaussianos (DoG) utilizados por SIFT , SUSAN y Harris.detectores. Además, cuando se aplican técnicas de aprendizaje automático, se puede lograr un rendimiento superior en términos de tiempo y recursos de cálculo. El detector de esquina FAST es muy adecuado para aplicaciones de procesamiento de video en tiempo real debido a este rendimiento de alta velocidad.
Detector de prueba de segmento
El detector de esquina 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 realmente una esquina. Cada píxel del círculo está etiquetado desde el 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 de umbral t o todos más oscuros que la intensidad del píxel candidato p menos el valor de 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, , la intensidad de x> I p + umbral, o
- Condición 2: un conjunto de N píxeles contiguos S, ,
Entonces, cuando se cumple cualquiera de las dos condiciones, el candidato p puede clasificarse como una esquina. Existe una compensación al elegir N, el número de píxeles contiguos y el valor umbral t. Por un lado, el número de puntos de esquina detectados no debe ser demasiado, por otro lado, el alto rendimiento no debe lograrse sacrificando la eficiencia computacional. Sin la mejora del aprendizaje automático , N se elige normalmente como 12. Se podría aplicar un método de prueba de alta velocidad para excluir los puntos que no son de esquina.
Prueba de alta velocidad
La prueba de alta velocidad para rechazar los puntos que no son de esquina se realiza examinando 4 píxeles de ejemplo, a saber, los píxeles 1, 9, 5 y 13. Dado que debe haber al menos 12 píxeles contiguos que sean todos más brillantes o más oscuros que la esquina candidata, por lo que debe haber al menos 3 píxeles de estos 4 píxeles de ejemplo que sean todos 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 1 como I 9 están dentro de [I p - t, I p + t], el candidato p no es una esquina. De lo contrario, los píxeles 5 y 13 se examinan más a fondo para comprobar si tres de ellos son más brillantes que I p + t o más oscuros que I p - t. Si hay 3 de ellos que son más brillantes o más oscuros, el resto de píxeles se examinan para la conclusión final. Y según el inventor en su primer artículo, [2] se necesitan en promedio 3,8 píxeles para comprobar si hay un píxel de esquina candidato. Comparado con 8.5 píxeles para cada esquina candidata, 3.8 es realmente una gran reducción que podría mejorar en gran medida el rendimiento.
Sin embargo, existen varias debilidades para este método de prueba:
- 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 + to más oscuros que I p - t.
- 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 se preocupa por la distribución de las apariencias de las esquinas.
- Se detectan varias características adyacentes entre sí
Mejora con el aprendizaje automático
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 opera en dos etapas. En primer lugar, la detección de esquinas con una N determinada se procesa en un conjunto de imágenes de entrenamiento que son preferibles del dominio de aplicación de destino. Las esquinas se detectan mediante 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 ubicación en el círculo x ∈ {1, 2, 3, ..., 16} se puede denotar por p → x. El estado de cada píxel, S p → x debe estar en uno de los siguientes tres estados:
- d, I p → x ≤ I p - t (más oscuro)
- s, I p - t ≤ I p → x ≤ I p + t (similar)
- b, I p → x ≥ I p + t (más brillante)
Luego, al elegir una x (igual para todas las p), P (el conjunto de todos los píxeles de todas las imágenes de entrenamiento) se divide 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}
- P b = {p ∈ P: S p → x = b}
En segundo lugar, un algoritmo de árbol de decisión , el algoritmo ID3 se aplica 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 la entropía de K p se usa 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 2 (c + n) - obstruir 2 c - nlog 2 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 se puede representar 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, al principio 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 producir la mayor ganancia de información (observe que la y podría ser la misma que x). Este proceso recursivo finaliza cuando la entropía es cero, de modo que todos los píxeles de ese subconjunto son esquinas o no esquinas.
Este árbol de decisiones generado se puede convertir en código de programación, como C y C ++, que es solo un montón de declaraciones if-else anidadas. Con fines de optimización, se utiliza la optimización guiada por perfiles para compilar el código. El código cumplido se utiliza posteriormente como detector de esquinas para otras imágenes.
Tenga en cuenta que las esquinas detectadas con este algoritmo de árbol de decisión deben ser ligeramente diferentes de los resultados con el detector de prueba de segmento. Esto se debe a que ese modelo de árbol de decisión depende de los datos de entrenamiento, que no pueden cubrir todos los rincones posibles.
Supresión no máxima
"Dado que la prueba de segmento no calcula una función de respuesta de esquina, la supresión no máxima no se puede aplicar directamente a las características resultantes". Sin embargo, si N es fijo, para cada píxel p, la fuerza de la esquina se define como el valor máximo de t que hace que pa sea la esquina. Por tanto, se podrían utilizar dos enfoques:
- Se podría aplicar un algoritmo de búsqueda binaria para encontrar la t más grande para la que p sigue siendo una esquina. Entonces, cada vez que se establece una t diferente para el algoritmo del árbol de decisión. Cuando se las arregla para encontrar la t más grande, esa t podría considerarse como la fuerza de la esquina.
- Otro enfoque es un esquema de iteración, donde cada vez que t se incrementa hasta el valor más pequeño de los que pasan la prueba.
FAST-ER: repetibilidad mejorada
El detector FAST-ER es una mejora del detector FAST que utiliza un algoritmo metaheurístico , en este caso recocido simulado . De modo que después de la optimización, la estructura del árbol de decisión estaría optimizada y adecuada para puntos con alta repetibilidad. Sin embargo, dado que el recocido simulado es un algoritmo metaheurísico, cada vez el algoritmo generaría un árbol de decisión optimizado diferente. Por lo tanto, es mejor tomar de manera eficiente una gran cantidad de iteraciones para encontrar una solución que se acerque al óptimo real. Según Rosten, se necesitan unas 200 horas en un Pentium 4 a 3 GHz, que son 100 repeticiones de 100.000 iteraciones para optimizar el detector FAST.
Comparación con otros detectores
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 los parámetros para los detectores (distintos de FAST) son los siguientes:
Detector | Ajuste de parámetros | Valor |
---|---|---|
Perro | ||
Escalas por octava | 3 | |
Desenfoque inicial σ | 0,8 | |
Octavas | 4 | |
SUSAN | Umbral de distancia | 4.0 |
Harris, Shi-Tomasi | Desenfocar σ | 2.5 |
Harris-Laplace | Desenfoque inicial σ | 0,8 |
Desenfoque de Harris | 3 | |
Octavas | 4 | |
Escalas por octava | 10 | |
Parametros generales | ε | 5 píxeles |
- El resultado de la prueba de repetibilidad se presenta como el área promediada bajo las curvas de repetibilidad para 0-2000 esquinas por fotograma en todos los conjuntos de datos (excepto el ruido aditivo):
Detector | A |
---|---|
MÁS RÁPIDO | 1313,6 |
RÁPIDO-9 | 1304.57 |
PERRO | 1275.59 |
Shi y Tomasi | 1219.08 |
Harris | 1195.2 |
Harris-Laplace | 1153.13 |
RÁPIDO-12 | 1121.53 |
SUSAN | 1116,79 |
Aleatorio | 271,73 |
- Las pruebas de velocidad se realizaron en una computadora Pentium 4-D a 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 monocromas con una resolución de 992 × 668 píxeles. El equipo de prueba consta de 4968 fotogramas de video monocromo de 352 × 288. Y el resultado es:
Detector | Tasa de píxeles del conjunto de entrenamiento | Tasa de píxeles del conjunto de prueba |
---|---|---|
RÁPIDO n = 9 | 188 | 179 |
RÁPIDO n = 12 | 158 | 154 |
RÁPIDO original n = 12 | 79 | 82,2 |
MÁS RÁPIDO | 75,4 | 67,5 |
SUSAN | 12,3 | 13,6 |
Harris | 8.05 | 7,90 |
Shi-Tomasi | 6,50 | 6,50 |
Perro | 4,72 | 5.10 |
Referencias
- ^ Rosten, Edward; Drummond, Tom (2006). "Machine Learning para la detección de esquinas de alta velocidad". Visión por computadora - ECCV 2006 . Apuntes de conferencias en informática. 3951 . págs. 430–443. doi : 10.1007 / 11744023_34 . ISBN 978-3-540-33832-1. S2CID 1388140 .
- ^ Edward Rosten, Anotaciones de video en tiempo real para realidad aumentada
- ^ Edward Rosten, MÁS RÁPIDO y mejor: un enfoque de aprendizaje automático para la detección de esquinas
Bibliografía
- Rosten, Edward; Tom Drummond (2005). Fusionar puntos y líneas para un seguimiento de alto rendimiento (PDF) . Conferencia Internacional IEEE sobre Visión por Computador . 2 . págs. 1508-1511. CiteSeerX 10.1.1.60.4715 . doi : 10.1109 / ICCV.2005.104 . ISBN 978-0-7695-2334-7.
- 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". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 32 (1): 105-119. arXiv : 0810.2434 . doi : 10.1109 / TPAMI.2008.275 . PMID 19926902 .
- Rosten, Edward; Tom Drummond (2006). Aprendizaje automático para la detección de esquinas de alta velocidad (PDF) . Congreso Europeo de Visión por Computador . Apuntes de conferencias en informática. 1 . págs. 430–443. CiteSeerX 10.1.1.64.8513 . doi : 10.1007 / 11744023_34 . ISBN 978-3-540-33832-1.
enlaces externos
- Página de inicio de Advanced Vision