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

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

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

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

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

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

Это всегда потребует больших вычислений, особенно если вы хотите обработать до 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 = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2+(z_1 - z_2)^2}$

$2000 \choose 2$

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

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

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

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

Обновить:

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

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

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

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