Соответствие профиля в облаке точек

14

Облако точек генерируются с использованием равномерной случайной функции для (x,y,z). Как показано на следующем рисунке, исследуется плоская пересекающаяся плоскость ( профиль ), которая соответствует как лучшему (даже если не точному) целевому профилю, т.е. заданному в левом нижнем углу. Итак, вопрос :

1- Как найти такой матч дается target 2D point mapчерез point cloudучитывая следующие указания / условия?
2- Каковы тогда координаты / ориентации / степень сходства и т. Д.?

Примечание 1: Интересующий профиль может находиться в любом месте с любым поворотом вдоль осей, а также может иметь различную форму, например треугольник, прямоугольник, четырехугольник и т. Д., В зависимости от его местоположения и ориентации. На следующей демонстрации показан только простой прямоугольник.

Примечание 2. Значение допуска можно рассматривать как расстояние между точками и профилем. Чтобы продемонстрировать это на следующем рисунке предположим допуск 0.01раз наименьший размер (~1)так tol=0.01. Поэтому, если мы удалим оставшуюся часть и спроецируем все оставшиеся точки на плоскости исследуемого профиля, мы сможем проверить его сходство с целевым профилем.

Примечание 3: Соответствующую тему можно найти в разделе « Распознавание точечных паттернов» .

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

разработчик
источник
@Developer Не по теме, но какое программное обеспечение вы используете для создания этих графиков?
Спейси
1
@ Мохаммад Я использую Python+, MatPlotLibчтобы делать свои исследования и создавать графики и т. Д.
Разработчик
@Developer Fantastic - это через Python, но что они означают «оболочка Python ala Matlab»?
Спейси
Как хранятся облака точек? Как набор координат для центра каждой точки или как объемный набор данных, который имеет ненулевые значения в координатах вокруг точек?
эндолит
@endolith Все точки имеют координаты, связанные как P:{x,y,z}. Это действительно безразмерные точки. Однако в некотором приближении они могут быть дискретизированы до однопиксельного измерения как трехмерные массивы. Они могут включать в себя также другие атрибуты (например, веса и т. Д.) По координатам.
Разработчик

Ответы:

4

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

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

Моя попытка решения:

Предположения:

  • Вы хотите найти лучшее совпадение, а не просто проигрышное или «вероятно правильное» совпадение
  • У совпадения будет небольшая ошибка из-за шума в измерениях или вычислениях
  • Исходные точки копланарны
  • Все исходные точки должны существовать в цели (= любая несогласованная точка является несовпадением для всего профиля)

Таким образом, вы должны быть в состоянии использовать много ярлыков, дисквалифицируя вещи и уменьшая время вычислений. Короче говоря:

  1. выбрать три точки из источника
  2. поиск по целевым точкам, поиск наборов из 3 точек одинаковой формы
  3. когда найдено совпадение из 3 точек, проверьте все остальные точки в плоскости, которую они определяют, чтобы увидеть, являются ли они близким совпадением
  4. если найдено более одного совпадения всех точек, выберите ту, в которой ошибка наименьшей суммы трехмерных расстояний

Более подробный:

pick a point from the source for testing s1 = (x1, y1)
Find nearest point in source s2 = (x2, y2)
d12 = (x1-x2)^2 + (y1-y2)^2
Find second nearest point in source s3 = (x3, y3)
d13 = (x1-x3)^2 + (y1-y3)^2
d23 = (x2-x3)^2 + (y2-y3)^2

for all (x,y,z) test points t1 in target:
    # imagine s1 and t1 are coincident
    for all other points t2 in target:
        if distance from test point > d12:    
            break out of loop and try another t2 point
        if distance ≈ d12:
            # imagine source is now rotated so that s1 and s2 are collinear with t1 and t2
            for all other points t3 in target:
                if distance from t1 > d13 or from t2 > d23:
                    break and try another t3
                if distance from t1 ≈ d13 and from t2 ≈ d23:
                    # Now you've found matching triangles in source and target
                    # align source so that s1, s2, s3 are coplanar with t1, t2, t3
                    project all source points onto this target plane 
                    for all other points in source:
                        find nearest point in target
                        measure distance from source point to target point
                        if it's not within a threshold:
                            break and try a new t3
                        else:
                            sum errors of all matched points for this configuration (defined by t1, t2, t3)

Какая конфигурация имеет наименьшую квадратичную ошибку для всех остальных точек, это лучшее совпадение

Поскольку мы работаем с 3 ближайшими соседними контрольными точками, сопоставление целевых точек можно упростить, проверив, находятся ли они в некотором радиусе. Например, при поиске радиуса 1 из (0, 0) мы можем дисквалифицировать (2, 0) на основе x1 - x2, не вычисляя фактическое евклидово расстояние, чтобы немного его ускорить. Это предполагает, что вычитание происходит быстрее, чем умножение. Есть оптимизированный поиск, основанный на большем произвольном фиксированном радиусе .

function is_closer_than(x1, y1, z1, x2, y2, z2, distance):
    if abs(x1 - x2) or abs(y1 - y2) or abs(z1 - z2) > distance:
        return False
    return (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 > distance^2 # sqrt is slow

dзнак равно(Икс1-Икс2)2+(Y1-Y2)2+(Z1-Z2)2

(20002)

На самом деле, поскольку вам все равно придется вычислять все эти значения, находите ли вы совпадения или нет, и поскольку для этого шага вас интересуют только ближайшие соседи, если у вас есть память, вероятно, лучше предварительно рассчитать эти значения с использованием оптимизированного алгоритма. , Что-то вроде триангуляции Делоне или Питтеуэя , где каждая точка в цели связана с ее ближайшими соседями. Сохраните их в таблице, затем найдите их для каждой точки, пытаясь подогнать исходный треугольник к одному из целевых треугольников.

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

эндолиты
источник
1
Первая часть в вашем ответе - это метод грубой силы, который ищет близлежащие точки (считая порог) вокруг всех возможных плоскостей через облако точек. Это чрезвычайно интенсивно для вычислений, например, только для 2000 очков потребуется вычисление расстояния 2 662 668 000 000 (Формула) !
Разработчик
@Developer: Да, потребуется много вычислений, особенно если у вас тысячи очков. Да, за 2000 очков, если вы не найдете самолетов, вы в конечном итоге выполните 2 658 673 998 000 вычислений. Предположительно вы бы найти самолеты, хотя, что позволит сократить время , потому что он останавливается , как только он нашел достаточное количество очков. Но в любом случае, я думал об этом, и, возможно, у меня получше идея, и я изменю ответ.
Эндолит
1
Вы абсолютно правильно поняли суть. Просто добавьте, что критерии остановки не могут применяться даже после нахождения подходящей плоскости, в то время как может быть, что есть намного лучшее соответствие, поэтому необходимо проверять все возможные плоскости. Я уже реализовал эту идею и обнаружил, что даже с помощью Fortranчисел, превышающих 500баллы, невозможно иметь опыт работы с ПК.
Разработчик
2

Я бы добавил @ mirror2image описание альтернативного решения, кроме RANSAC, вы можете рассмотреть алгоритм ICP (итеративная ближайшая точка), описание можно найти здесь !

Я думаю, что следующая проблема в использовании этого ICP состоит в том, чтобы определить вашу собственную функцию стоимости и начальную позу целевой плоскости относительно данных трехмерной точки облачности. Некоторый практический подход заключается во введении некоторого случайного шума в данные во время итерации, чтобы избежать сближения с ложными минимумами. Это эвристическая часть, я думаю, вам нужно разработать.

Обновить:

Этапы в упрощенном виде это:

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

Повторите шаг 1-4.

Есть доступная библиотека, которую вы можете рассмотреть здесь ! (Я еще не пробовал), есть один раздел по части регистрации (включая другие методы).

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