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

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

an unwarped grid

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

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

a warped grid (источник)

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

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

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

Ответы

Ответ 1

Хорошо, так что это похоже на деформацию изображения. Это то, что вы должны сделать:

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

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

    • Найти треугольник A лежит и использовать преобразование между треугольником в необожженной сетке и искаженной сеткой для определения новой позиции.

Это подробно объясняется здесь.

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

Ответ 2

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

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

Preprocess

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

Сопоставьте точку p в завернутой сетке

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

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

Ответ 3

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

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

Ответ 4

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

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