Как сопоставить точку на искаженной сетке

Question

Скажем, у вас есть набор точек с координатами на декартовой системе координат.

Вы хотите построить еще один момент, и вы знаете свои координаты в одной и той же декартовой системе координат.

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

(source)

Вы знаете, растянутые и Unstretched координаты каждого из вашего набора точек, но не основная функция натяжкой. Вы знаете нерастянутые координаты новой точки.

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

другие возможные ключевые слова: деформированные искажены сетки сетки плоскости координат unwarp

Answer 1

Ok, так что это звучит как искривления изображения. Это то, что вы должны сделать:

1. Создать Delaunay triangulation вашей unwarped сетки и использовать свои знания соответствий между извращенной и unwarped сеткой для создания триангуляции для искривленной сетки. Теперь вы знаете соответствующие треугольники в каждом изображении и, поскольку нет перекрытия, вы можете выполнить следующий шаг без особых трудностей.

2. Теперь, чтобы найти соответствующую точку A, в деформированном изображении:

   1. Найти треугольника A ложь в и использовать преобразование между trianble в unwarped сетки и деформированные сетки, чтобы выяснить Новая позиция.

Это объясняется в явном подробно here.

Другой (гораздо более сложный) метод - это Thin Plate Spline (что также объясняется в слайдах выше).

Answer 2

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

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

Answer 3

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

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

Preprocess

1. Генерирование Delaunay triangulation из точек обернутой сетки, давайте назовем его WT.
2. Для каждого треугольника в WT добавьте треугольник между соответствующими вершинами в развернутой сетке. Это дает триангуляцию UWT развернутых точек.

Карта точки p в обернутой сетки

1. Найти треугольник T(p1,p2,p3) в UWT, который содержит p.
2. Вычисляется barycentric coordinates(b1,b2,b3) из p в T(p1,p2,p3)
3. Пусть Tw(q1,q2,q3) треугольник, в WT, соответствующий T(p1,p2,p3). Новая позиция -
   b1 * q1 + b2 * q2 + b3 * q3.

Примечания Это дает функцию деформации как linear spline. Для более плавного поведения можно было использовать ту же триангуляцию, но иметь приближение более высокого порядка, что привело бы к более сложному вычислению вместо барицентрических координат.

Answer 4

Другие ответы велики. Единственное, что я хотел бы добавить, это то, что вы можете взглянуть на Free form deformation как способ описания деформаций.

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