Алгоритм сопоставления точек с двух разных изображений

Я ищу метод или алгоритм, который позволил бы мне распознавать и соединять наборы точек из двух разных изображений для целей стереозрения. picture

На прикрепленном изображении представлено то, что у меня есть на данный момент: 2 камеры выровнены по оси Y и немного смещены по оси X, глядя на набор точек. Я могу отслеживать и получать 2D-позиции каждой из этих точек на двух изображениях камеры (IMG0 и IMG1).

Таким образом, у меня есть два списка 2D-координат:

L0 = { a0, a1, a2, a3, a4, a5, a6 }
L1 = { b0, b1, b2, b3, b4, b5, b6 }

Теперь, чтобы выполнить триангуляцию для получения трехмерного положения каждой точки, мне нужно знать, какая точка на изображении IMG1 соответствует какой точке на IMG0. Обе камеры видят один и тот же набор точек с одинаковой общей формой, но, очевидно, из-за небольшого искажения и смещения камеры по горизонтали 2D-координаты не совпадают от изображения к другому.

В идеале алгоритм сопоставления точек, который я ищу, должен привести к такому списку:

List = {a0-b0, a1-b1, a2-b2,...}

Порядок в списке не имеет значения, пока я уверен, что каждая точка связана с правильной точкой на втором изображении.

Я просмотрел несколько статей, в которых представлены алгоритмы стереокарты, но я не нашел ничего, относящегося к моей проблеме, так как большинство алгоритмов основаны на распознавании тяжелых изображений, что не подходит в моем случае, когда я хочу быстро обработать все в реальном -время. Ближайшим решением, которое я нашел, является алгоритм сопоставления точек, представленный здесь, но, опять же, он кажется слишком тяжелым для моя проблема.

Любая помощь будет принята с благодарностью.


person user2187623    schedule 19.03.2013    source источник
comment
когда я искал в Интернете, я смог получить много соответствующих ссылок (в основном реализованных в Matlab). Например: mathworks.com/matlabcentral/fileexchange/28522-stereo-matching .   -  person ElKamina    schedule 19.03.2013
comment
Насколько близко точки могут быть к камере? Если точки находятся очень близко к камере или если камеры находятся очень далеко друг от друга, форма облаков точек может сильно отличаться, и может потребоваться другой алгоритм сопоставления.   -  person mbeckish    schedule 19.03.2013


Ответы (1)


Прежде всего, вы должны убедиться, что понимаете основные понятия эпиполярной геометрии, особенно понятие эпиполярная линия.

В двух словах: допустим, у вас есть трехмерная точка P, которая проецируется в двухмерную точку q на изображении с камеры A. Теперь у вас есть вторая камера, назовите ее B, и вы хотите найти изображение P в B. Эпиполярная геометрия говорит вам, что возможные положения изображения P в B при заданном q ограничены линией, называемой эпиполярной линией. Он также говорит вам, что (и как) вы можете вычислить эту линию из q и калибровки ваших камер, используя так называемую Фундаментальную матрицу.

Для вашей проблемы это имеет следующие последствия:

Пусть q будет точкой из списка L0.

  • Если в вашем списке L1 есть одна точка, которая находится на эпиполярной линии q на втором изображении, то это правильное соответствие для q.
  • Если на эпиполярной линии несколько точек, то ваша задача не может быть решена с помощью данной информации. В этом случае вам нужно сделать эвристические предположения о распределении ваших точек в 3D, поскольку вы получаете одну возможную 3D точку для каждой пары q с точкой на эпиполярной линии.

Если ваши камеры смещены только по оси X и если они одинаково ориентированы (т.е. плоскости изображения параллельны), то это ваш счастливый день: в этой специальной конфигурации камеры эпиполярные линии горизонтальны, т.е. для точки (x,y) эпиполярная линия — это линия всех точек с произвольной координатой X и координатой Y y.

Обратите внимание, что на практике вы также столкнетесь с проблемой, что точки вряд ли будут точно на эпиполярных линиях из-за ошибок измерения и проблем с числами.

person DCS    schedule 19.03.2013
comment
Спасибо большое. Да, мои камеры смещены только по оси X. Итак, предположительно, для данной точки в L0, я думаю, я могу проверить L1 для всех точек, которые имеют одинаковое положение Y (я говорю похожие, потому что они не будут точно такими же, как вы сказали, из-за потенциальных ошибок измерений) . В случае, если у меня есть больше совпадений точек на линии, я могу отсортировать их, используя позицию X. Я попробую, но я думаю, что это сработает. - person user2187623; 20.03.2013
comment
Это должно сработать, но, как я уже сказал: имея более одного кандидата на эпиполярной линии, вам нужно подумать, какая точка более правдоподобна, учитывая конкретную сцену, которую вы реконструируете. Я бы триангулировал всех кандидатов, а затем посмотрел на точки 3D, которые нужно выбрать. - person DCS; 20.03.2013
comment
Если у вас есть несколько точек в L1, лежащих на одной и той же эпиполярной линии, порожденной точкой в ​​L0, я бы предложил создать граф, в котором есть вершина для каждой точки в L0, вершина для каждой точки в L1 и ребро между двумя вершинами, когда одна из них лежит на эпиполярной линии другой. Затем вы можете найти наилучшее совпадение точек, запустив алгоритм двудольного максимального совпадения на этом графике. - person j_random_hacker; 20.03.2013
comment
@j_random_hacker: Я думаю, что у него столько же очков в L0, сколько и в L1, поэтому вам придется ввести веса, чтобы отдать предпочтение одному совпадению над другим. Поддерживает ли двудольное максимальное соответствие веса или оно строго комбинаторно? - person DCS; 20.03.2013
comment
Я не понимаю ваше первое предложение, извините - лучшим случаем было бы, если L0 и L1 имеют одинаковое количество точек, так как тогда можно было бы сопоставить каждую точку в одной с какой-то отдельной точкой в другом. Относительно предложения 2: существует взвешенное двудольное максимальное соответствие. Это может быть предпочтительнее, так как вы можете придать больший вес точкам, которые находятся ближе к эпиполярным линиям. - person j_random_hacker; 20.03.2013
comment
Это то, что у меня есть на все времена. L0 и L1 всегда имеют одинаковое количество точек, и каждая точка из L0 соответствует одной точке в L1. - person user2187623; 20.03.2013