Что в настоящее время считается «лучшим» алгоритмом для двумерного сопоставления точек?

Question

У меня есть два списка, содержащие координаты x-y (звезд). Я мог бы также иметь величины (яркости), прикрепленные к каждой звезде. Теперь у каждой звезды есть случайные положения, и на каждом изображении может быть несколько лишних или недостающих точек. Мой вопрос: «Каков наилучший алгоритм 2D точечного сопоставления для такого набора данных?» Я предполагаю, что для простых линейных (перемещение, вращение, масштаб) и нелинейных (скажем, полиномов n-степени в координатах). В жаргоне поля сопоставления точек я ищу алгоритмы, которые выиграли бы в перестрелке между программами сопоставления двумерных точек с шумом и паразитными точками. Могут быть разные «победители», в зависимости от того, используется ли информация о маркировке (величины) и / или преобразование ограничено линейностью.

Мне известно, что в каждом классе есть много классов алгоритмов двумерного сопоставления точек и много алгоритмов (буквально, вероятно, сотни), но я не знаю, какой, если таковой имеется, считается "лучшим" или " Самый стандартный »от людей в области компьютерного зрения. К сожалению, многие статьи к статьям, которые я хочу прочитать, не имеют онлайн-версий, и я могу только читать реферат. Прежде чем я остановлюсь на конкретном алгоритме реализации, было бы неплохо услышать мнение нескольких экспертов об отделении пшеницы от плевел.

У меня есть рабочая программа сопоставления, в которой используются треугольники, но она часто выходит из строя (~ 5% времени), так что преобразование решения имеет явные искажения, но без видимой причины. Эта программа была написана не мной и написана почти 20 лет назад. Я хочу написать новую реализацию, которая работает наиболее надежно. Я предполагаю (надеюсь), что в этой области были достигнуты определенные успехи, которые делают это правдоподобным.

Answer 1

Если вы заинтересованы в подборе звезд, посмотрите Astrometry.net слепой астрометрический решатель и документ здесь Они используют четырехточечные четырехугольники для решения звездных конфигураций на изображениях ночного неба на Flickr. Проверьте это интервью .

Answer 2

Не существует единого «лучшего» алгоритма для этого. Существует множество различных методов, и каждый из них работает лучше других над определенными наборами данных и типами данных.

Одна вещь, которую я бы порекомендовал, - прочитать это введение в регистрацию изображений из учебников Insight Toolkit. ITK поддерживает МНОГО типов регистрации изображений (что звучит так: как вы пытаетесь), и во многих случаях очень надежный. Большинство их пользователей работают в области медицины, поэтому вам придется разбираться с большим количеством медицинских терминов, но алгоритмы и код работают с любым типом изображения (включая 1,2,3 и n-мерные изображения разных типы и т.д.).

Answer 3

Я не уверен, что это сработает, но стоит попробовать:

Для каждой звезды выполните круговое преобразование Фурье луча времени - центрированное вокруг него - всех других звезд (примечание: это не стандартное преобразование Фурье, которое является линией времен линии). Фазовое пространство круга и времени луча является целой линией времен, но поскольку у нас только конечная точность, вы просто получаете матрицу; Размеры матрицы зависят от точности. Теперь попробуйте соединить матрицы друг с другом (например, используя норму L_2)

Answer 4

Вы можете рассмотреть возможность применения вашего алгоритма сначала только к N наиболее ярким звездам, а затем постепенно добавлять остальные для уточнения результата, одновременно уменьшая диапазон поиска.

Использование RANSAC для устойчивости к дополнительным очкам также очень распространено.

Answer 5

Я думаю, что «лучшим» (наиболее техническим) способом было бы взять преобразование Фурье исходного изображения и нового линейно модифицированного изображения. Выполнив некоторую простую фильтрацию, вы сможете легко определить ориентацию и масштаб вашего изображения относительно старого. Описание 2d преобразования Фурье здесь .

Answer 6

Я недавно видел по телевизору программу о том, как исследователи фотографировали китов и использовали пятна на них (которые уникальны для каждого кита), чтобы идентифицировать каждого кита. Он использовал углы между пятнами. При использовании углов не имело значения, было ли изображение повернуто, масштабировано или переведено. Это похоже на то, что вы делаете со своими треугольниками.