¿Cuál es considerado actualmente el "mejor" algoritmo para la coincidencia de puntos 2D?

Question

Tengo dos listas que contienen coordenadas x-y (de estrellas). También podría tener magnitudes (brillo) unidas a cada estrella. Ahora cada estrella tiene sacudidas de posición aleatorias y puede haber algunos puntos extra o faltantes en cada imagen. Mi pregunta es: "¿Cuál es el mejor algoritmo de coincidencia de punto 2D para un conjunto de datos como este?" Supongo que tanto para un simple lineal (traducción, rotación, escala) y no lineal (por ejemplo, polinomios de n grados en las coordenadas). En la jerga del campo de coincidencia de puntos, estoy buscando los algoritmos que ganarían en un tiroteo entre los programas de concordancia de punto 2D con ruido y puntos espurios. Puede haber diferentes "ganadores" dependiendo de si se utiliza la información de etiquetado (las magnitudes) y/o la transformación se limita a ser lineal.

Soy consciente de que hay muchas clases de algoritmos de coincidencia de punto 2D y muchos algoritmos en cada clase (literalmente cientos en total) pero no sé cuál, si es que alguno, es considerado el "mejor" o el "más estándar" por personas en el campo de la visión por computadora. Tristemente, muchos de los artículos para los artículos que quiero leer no tienen versiones en línea y solo puedo leer el resumen. Antes de establecer un algoritmo particular para implementar, sería bueno escuchar a algunos expertos para separar el trigo de la paja.

Tengo un programa de coincidencia de trabajo que utiliza triángulos pero falla con bastante frecuencia (~ 5% del tiempo) de manera que la transformación de la solución tiene distorsiones obvias pero sin ninguna razón obvia. Este programa no fue escrito por mí y proviene de un documento escrito hace casi 20 años. Quiero escribir una nueva implementación que funcione de manera más robusta. Estoy asumiendo (con la esperanza) que ha habido algunos avances en esta área que hacen que esto sea plausible.

Answer 1

Hace un tiempo, vi un programa sobre la forma en que los investigadores tomaban fotos de las ballenas y utilizaban las manchas (únicas para cada ballena) para identificar a cada ballena. Usó los ángulos entre las manchas. Al usar los ángulos, no importaba si la imagen se giraba, escalaba o traducía. Eso suena similar a lo que estás haciendo con tus triángulos.

Answer 2

Creo que la "mejor" (la más técnica) manera sería tomar la Transformada de Fourier de la imagen original y de la nueva imagen modificada linealmente. Al hacer un simple filtrado, debería ser fácil determinar la orientación y la escala de su imagen con respecto a la anterior. Hay una descripción de la 2d Transformada de Fourier here.

Answer 3

No hay un solo "mejor" algoritmo para esto. Hay muchas técnicas diferentes, y cada una funciona mejor que otras en conjuntos de datos específicos y tipos de datos.

Una cosa que recomendaría es leer this introduction to image registration de los tutoriales del Insight Toolkit. ITK admite MUCHOS tipos de registro de imágenes (que es lo que parece que está intentando), y es muy robusto en muchos casos. La mayoría de sus usuarios están en el campo de la medicina, por lo que tendrá que pasar por una gran cantidad de jerga médica, pero los algoritmos y el código funcionan con cualquier tipo de imagen (incluidas las imágenes 1, 2, 3 y n dimensiones, de diferentes tipos, etc.).

Answer 4

Puede considerar aplicar su algoritmo primero solo en las N estrellas más brillantes, luego incluir progresivamente las demás para refinar el resultado, reduciendo el rango de búsqueda al mismo tiempo.

El uso de RANSAC para la robustez de los puntos extra también es muy común.

Answer 5

Si está interesado en la coincidencia de estrellas, consulte Astrometry.net blind astrometry solver y paper on it here. Usan cuatro puntos para resolver configuraciones estelares en imágenes de Flickr del cielo nocturno. Consulte this interview.

Answer 6

No estoy seguro de que funcionaría, pero vale la pena intentarlo:

Por cada estrella no transformada de Fourier rayos hora del círculo - en torno a ella - de todas las otras estrellas (nota: esto no es la norma Transformada de Fourier, que es la línea de tiempos de línea). El espacio de fase de circle times ray es un número entero por línea, pero como solo tenemos una precisión finita, obtienes una matriz; las dimensiones de la matriz dependen de la precisión. Ahora intente emparejar las matrices entre sí (por ejemplo, usando la norma L_2)