Сравните трехмерные структуры

Question

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

Более того, мне бы очень хотелось, чтобы, если две геометрии немного различались, хэши также не сильно различались.

Кто-нибудь знает какой-нибудь алгоритм, который соответствует моим потребностям, и может предоставить ссылку для дальнейшего изучения?

Спасибо

Answer 1

Вашей первой мыслью может быть попытка найти вращение, которое отображает один объект на другой, но это очень и очень сложная тема ... и на самом деле в этом нет необходимости! Вы не спрашиваете, как лучше всего соответствовать двум, вы просто спрашиваете, являются ли они одинаковыми или нет.

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

Три вопроса:

1) Что, если количество точек велико, это большой список пар (N * (N-1) / 2). В этом случае вы можете выбрать оставить только самые длинные или, что еще лучше, оставить 1 или 2 самых длинных для каждой вершины, чтобы каждая часть вашей модели имела некоторый вклад. Однако отбрасывание подобной информации меняет проблему на вероятностную, а не детерминированную.

2) При этом используются только вершины для определения формы, а не ребра. Это может быть хорошо (и на практике будет), но если вы ожидаете, что у вас будут фигуры с одинаковыми вершинами, но разными соединительными ребрами. Если это так, сначала проверьте сходство вершин. Если это пройдет, тогда назначьте уникальную маркировку каждой вершине, используя это отсортированное расстояние. Самый длинный край имеет две вершины. Для каждой из этих вершин найдите вершину с самым длинным (оставшимся) ребром. Пометьте первую вершину 0 и следующую вершину 1. Повторите процедуру для других вершин по порядку, и вам будут назначены теги, которые не зависят от сдвига и вращения. Теперь вы можете точно сравнивать топологии ребер (проверьте, что для каждого ребра в объекте 1 между двумя вершинами существует соответствующий ребро между теми же двумя вершинами в объекте 2). необходимо сопоставление связей, чтобы сделать задания стабильными и уникальными.

3) Существует вероятность того, что две фигуры имеют одинаковую длину ребер, но они не идентичны ... это верно, когда один объект является зеркальным отражением другого. Это довольно раздражает, чтобы обнаружить! Один из способов сделать это - использовать четыре некомпланарные точки (возможно, те, которые отмечены от 0 до 3 из предыдущего шага) и сравнить «управляемость» системы координат, которую они определяют. Если вручение не совпадает, объекты являются зеркальными изображениями.

Обратите внимание, что список расстояний позволяет легко отбрасывать неидентичные объекты. Это также позволяет добавить «нечеткое» принятие, допуская определенное количество ошибок в заказах. Возможно, хорошо бы использовать среднеквадратичную разницу между двумя списками в качестве «меры сходства».

Редактировать: похоже, ваша проблема - облако точек без краев. Тогда надоедливая проблема соответствия краев (# 2) даже не применяется и может быть проигнорирована! Вы все еще должны быть осторожны с проблемой зеркального отображения # 3.

Answer 2

1. Если вы хотите оценить жесткие преобразование между двумя похожими облака точек вы можете использовать устоявшихся Метод итеративной ближайшей точки . Этот метод начинается с грубой оценка трансформации и затем итеративно оптимизирует для преобразование, вычисляя ближайший соседи и сведение к минимуму связанная функция стоимости. Может быть эффективно реализовано (даже в реальном времени) и есть в наличии реализации доступны для matlab, c ++ ... Этот метод был расширен и имеет несколько вариантов, в том числе оценка нежестких деформации, если вы заинтересованы в расширениях вы должны посмотреть на Решение компьютерной графики проблема регистрации сканирования, где Ваша проблема является решающим шагом. За отправную точку см. Википедия страница на итеративной ближайшей точке который имеет несколько хороших внешних ссылки. Просто изображение-тизер из реализации Matlab , которая была разработана для соответствия облакам точек:
   _{(источник: mathworks.com )}

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

2. Использование дескрипторов форм можно вычислить отпечатки пальцев форм, которые часто инвариантны относительно переводы / повороты. В большинстве случаев они определены для сеток, а не для облаков точек, тем не менее, существует множество дескрипторов форм, поэтому в зависимости от ваших входных данных и требований вы можете найти что-то полезное. Для этого вам следует обратиться к области анализа формы и, вероятно, этой презентации курса SIGGRAPH 2004 года может дать представление о том, что люди делают для вычисления дескрипторов формы.

Answer 3

изображения спина - один из способов сделать это.

Answer 4

Есть множество публикаций SIGGRAPH, которые могут оказаться полезными для вас.

например. Браун и Русинкевич: «Глобальное нетвердое выравнивание трехмерных сканов»:

http://portal.acm.org/citation.cfm?id=1276404

Общий поиск, с которого можно начать:

http://scholar.google.com/scholar?q=siggraph+point+cloud+registration

Answer 5

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

Гугл

least squares rotation translation

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

Обновите следующий комментарий ниже: Если однозначное соответствие между точками неизвестно (как предполагается в статье выше), то вам просто нужно убедиться, что минимизируемая оценка не зависит от порядка точек. Например, если вы рассматриваете точки как малые массы (сферы конечного радиуса, чтобы избежать раздувания на нулевом расстоянии) и настроены на минимизацию общей гравитационной энергии системы путем оптимизации параметров перемещения и вращения, это должно сработать.

Answer 6

Вот как бы я это сделал:

1. Поместите наборы в центр масс
2. Вычислить тензор инерции . Это дает вам три координатные оси. Повернись к ним. [*]
3. Запишите список точек в заданном порядке (например, сверху вниз, слева направо) с требуемой точностью.
4. Примените любой алгоритм, который вы хотите для результирующего массива.

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

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

[*] Если две или три вашей оси совпадают, выберите координаты другими способами, например, как самое длинное расстояние. Но это крайне редко для случайных точек.

Answer 7

Может быть, вам стоит прочитать алгоритм RANSAC. Он обычно используется для сшивания панорамных изображений, которые, похоже, немного похожи на вашу проблему, только в двух измерениях Просто Google для RANSAC, панорамы и / или шить, чтобы получить отправную точку.