LINUX.ORG.RU
ФорумTalks

Вопрос для математиков про 2D деформации.

 , упороться,


2

5

Есть некая «правильная» сетка ограниченного размера из двумерных точек с координатами x1,у1 равномерно рапределённых в некоем прямоугольнике.

И есть «неправильная», «деформированная», «искажённая» сетка с теми же самыми точками, но с координатами x2,y2.

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

Эта деформация постоянна и не изменяется. Задача состит в том, чтобы имея эти 2 набора данных найти некую функцию (набор функций) которая позволит из произвольных «искажённых» координат x2,y2 в этом прямоугольнике получать «правильные» координаты x1,y1. Т.е. надо найти математическое выражение этой деформации.

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

Собственно вопрос в том, как эта задача в общем виде называется у математиков. Желательно по-английски. Всякое deconvolution как-то выносит в основном на что-то типа этого http://www.vassg.hu/pdf/vass_gg_2003_lo.pdf заточенное на заведомо известную модель искажений. Если модель заранее известна, то решение и так понятно как найти. А вот совсем общее решение, аналогичное какой-нибудь 1D/2D polynomial regression для произвольного набора экспериментальных данных что-то никак не находится.

Сейчас я, например, беру каждую точку и её соседей и апроксимирую тем или иным образом искажение для каждой точки. Для произвольной точки x2,y2 нахожу ближайшую из калибровочного набора и использую вычисленную для неё апроксимацию чтобы получить искомые «недеформированные» x1,x2. Может быть это можно делать как-то оптом для всего набора точек сразу?.

★★★★★

Последнее исправление: Stanson (всего исправлений: 2)

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

По-моему это замена координат, от прямоугольных к криволинейным.

Новые координаты являются функцией старых.

x_2 = f(x_1, y_1)

y_2 = g(x_1, y_1)

И у тебя есть значения в N точках.

Представляешь f и g например полиномами N-ной степени, получаешь линейную систему из N уравнений на N коэффициентов в каждом случае.

alpha ★★★★★
()
Ответ на: комментарий от alpha

Логично. Потом тупо LSE и в дамках. Спасибо.

А ещё варианты подходов есть? Какое-нибудь поле векторов искажений построить и кастануть какую-нибудь матанскую магию?

Stanson ★★★★★
() автор топика

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

DawnCaster ★★
()

Эм, разве ты не можешь восстановить исходную плоскость просто посчитав количество точек по левому краю и низу и поделить заново плоскость на это количество точек?

Tark ★★
()
Ответ на: комментарий от DawnCaster

Нашёл я Дональда Федера (sci-hub рулит), но, если я правильно понял, это всё же на оптику заточено и на заранее известный характер искажений.

Здесь же задача, если на оптику перекладывать такая - есть исходная картинка, и та же самая картинка но через рифлёное стекло со случайной поверхностью. Надо вычислить как именно это рифлёное стекло искажает изображение, а потом используя эту информацию, имея только искажённую картинки получать из них реальные.

Stanson ★★★★★
() автор топика
Ответ на: комментарий от Tark

Эм, разве ты не можешь восстановить исходную плоскость просто посчитав количество точек по левому краю и низу и поделить заново плоскость на это количество точек?

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

Stanson ★★★★★
() автор топика
Ответ на: комментарий от Stanson

ИИИ? У тебя координаты изначально равномерно распределенные же, и потом складок нет, значит точки по краям будут в том же количестве, что и изначально. И потом уже восстановив изначальные точки ты получишь вектора смещений для каждой. Но это конечно если у тебя в результате искажений столько же точек, сколько и изначально.

Потом просто по произвольной точке смотришь в каком она квадрате и располагаешь пропорционально этим векторам в изначальной сетке. Разве так работать не будет?

П.С.

Я не математик.

Tark ★★
()
Последнее исправление: Tark (всего исправлений: 2)
Ответ на: комментарий от Stanson

Мне кажется в такой постановке задачи магия может проявиться либо в вопросе, чем именно приблизить f и g, либо в вопросе, что делать с огромным N.

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

Если ни то, ни то тебе не принципиально, то магия не сильно и нужна.

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

alpha ★★★★★
()
Ответ на: комментарий от Tark

ИИИ? У тебя координаты изначально равномерно распределенные же,

Равномерно, да, но не квадратно-гнездовым способом. Просто на единицу площади везде примерно одинаковое количество точек.

и потом складок нет, значит точки по краям будут в том же количестве, что и изначально.

Далеко не факт, что они будут именно по краям.

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

Ну эти вектора и так есть. Но как это поможет узнать «истинные» координаты любой произвольной точки на «деформированной» поверхности?

Stanson ★★★★★
() автор топика

А, блин, так у тебя еще и первоначальная сетка известна. Что тогда мешает воспользоваться ну там самым базовым инструментом в этом вопросе? Узнаешь в какой квадрат оно входит в искаженной сетке и дальше https://ru.wikipedia.org/wiki/Аффинное_преобразование Складок и пересечений же нет, значит любой четвероугольник в искаженной сетке соответствует квадрату в изначальной.

Tark ★★
()
Последнее исправление: Tark (всего исправлений: 2)
Ответ на: комментарий от Stanson

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

Ещё можно попробовать тензорное исчисление, по описанию оно тоже должно работать с корявым

Но скорее всего тебе нужно что-то из матанализа, правда из какой его части и теории не знаю.

torvn77 ★★★★★
()
Последнее исправление: torvn77 (всего исправлений: 1)
Ответ на: комментарий от alpha

А, нет, я не права.

Ты потому что не ту задачу решаешь что написана в топ-посте.

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

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

Так что магия нужна.

И наверное нужны тебе двумерные сплайны:

http://alglib.sources.ru/interpolation/spline2d.php

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

alpha ★★★★★
()
Ответ на: комментарий от alpha

чем именно приблизить f и g,

Полином вполне годится. Даже не особо высокой степени.

либо в вопросе, что делать с огромным N.

N на самом деле невелико, пара тыщ, или около того, это всё за миллисекунды можно считать на любом современном процессоре.

Если ни то, ни то тебе не принципиально, то магия не сильно и нужна.

Ну в общем да, предложенного тобой подхода «в лоб» вполне достаточно. Просто интересно, какие ещё есть варианты.

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

Не, с этой точки зрения всё ровно и неразрывно.

Stanson ★★★★★
() автор топика
Ответ на: комментарий от Tark

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

peregrine ★★★★★
()
Последнее исправление: peregrine (всего исправлений: 1)
Ответ на: комментарий от alpha

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

Этого и не нужно.

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

«Картинка» может быть тупо смещена, например. И точки будут «убежавшими» весьма прилично. Главное что точка нумер 4 это точка нумер 4 вне зависимости от того, насколько она оказалась далеко.

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

Ну я сейчас примерно так и считаю, просто хочется сделать как можно проще и красивее. KISS и всё такое.

Stanson ★★★★★
() автор топика

Очень похоже на задачу морфинга изображений.

Натягиваешь на исходную сетку треугольники, ставишь им в соответствие треугольники деформированной сетки и преобразуешь треугольники друг в друга по мере надобности.

Точного алгоритма преобразования треугольников я не знаю, но он должен найтись по ключевым словам: image morphing triangulation

cdslow ★★
()
Ответ на: комментарий от peregrine

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

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

Но апроксимация всей ботвы целиком полиномами от 2х переменных выглядит гораздо элегантнее.

Stanson ★★★★★
() автор топика
Последнее исправление: Stanson (всего исправлений: 1)
Ответ на: комментарий от cdslow

Только что другому персонажу отвечал про треугольники. Метод сработает, но с треугольниками можно только линейную апроксимацию получить, да и по ресурсам не самый оптимальный способ.

Stanson ★★★★★
() автор топика
Последнее исправление: Stanson (всего исправлений: 1)
Ответ на: комментарий от peregrine

Вообще в результате растяжений могут появиться и вогнутые четырехугольники, и центр картинки можно в спираль закрутить, но вроде в условии «первая сетка резиновая и её как-то растянули/сжали», «произвольных «искажённых» координат x2,y2 в этом прямоугольнике», типа прямоугольность сохраняется похоже. А преобразовать один прямоугольник в другой афинное преобразование годится.

Tark ★★
()
Ответ на: комментарий от Stanson

Этого и не нужно.

Нужно. Представь, у тебя есть точки

A=(-2,0), B=(-1,0), C=(0,0), D=(1,0).

A --- B --- C --- D

И ты начинаешь искажать картинку, то есть тыкаешь пальцем в первую точку и двигаешь вниз, на (-2, -6).

По «логике вещей» - это локальное искажение, оно затрагивает точку A и её окрестности, но не трогает всё остальное что лежит за точкой B.

И «естественным» приближением в таком случае будет что-то вроде:

     B --- C --- D
   /
  /
 /
A

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

Полином в данном случае будет x^3-x

       
       --
     /    \        /
    B      C      D
   /        \    / 
  /           --
 /
A

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

Сплайны в отличие от полиномов локальны, изменение значения одной точки не дает эффекта на остальные точки вне малой окрестности. Они в данной ситуации предпочтительнее.

alpha ★★★★★
()
Последнее исправление: alpha (всего исправлений: 2)

Эта деформация постоянна и не изменяется. Задача состит в том, чтобы имея эти 2 набора данных найти некую функцию (набор функций) которая позволит из произвольных «искажённых» координат x2,y2 в этом прямоугольнике получать «правильные» координаты x1,x2. Т.е. надо найти математическое выражение этой деформации.

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

Эти задачи почти наверняка не связаны. Оптика на фотоаппаратах в первую очередь вносит линейные искажения, а в твоей задаче - нелинейные.

ЗЫ: много раз интересовался но так и не нашел решение твоей задачи

cvv ★★★★★
()
Ответ на: комментарий от alpha

Да, всё верно, но «резина» такая, что если тронул точку А, то поедут и все остальные точки по всей поверхности. Чем дальше, тем влияние будет меньше, но тем не менее будет. Так что полином по всем точкам оптом - весьма годен.

Stanson ★★★★★
() автор топика
Ответ на: комментарий от Tark

Вообще в результате растяжений могут появиться и вогнутые четырехугольники, и центр картинки можно в спираль закрутить,

Да, можно, разве что «складок» или «дырок» быть не может.

типа прямоугольность сохраняется похоже

Совершенно необязательно.

Stanson ★★★★★
() автор топика
Ответ на: комментарий от Stanson

это всё же на оптику заточено и на заранее известный характер искажений.

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

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

Так что рекомендую.

DawnCaster ★★
()

Собственно вопрос в том, как эта задача в общем виде называется у математиков.

Гуглить в сторону: метод конечных элементов\задача плоской деформации.

quickquest ★★★★★
()
Ответ на: комментарий от Stanson

Здесь же задача, если на оптику перекладывать такая - есть исходная картинка, и та же самая картинка но через рифлёное стекло со случайной поверхностью. Надо вычислить как именно это рифлёное стекло искажает изображение, а потом используя эту информацию, имея только искажённую картинки получать из них реальные.

Вот как я вижу эту задачу с точки зрения систем координат Федера:

- У нас есть основная система координат со своими матрицами переноса, масштабирования и поворота.

- У нас есть вторая система координат для «деформированной» плоскости. Значения в матрицах переноса, масштабирования и поворота в ней зависят от базовых значений + функция от координаты точки внутри этой деформированной плоскости в её системе координат.

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

Конечно, если у вас «деформация» второй плоскости каждый раз случайная и нет математической модели её описывающей, то данный метод подходит не особо хорошо.

DawnCaster ★★
()
Последнее исправление: DawnCaster (всего исправлений: 1)
Ответ на: комментарий от Tark

А если пальцем не просто в сторону, а провернуть? Типа спиралька. Но учитывая что изначально известно какая точка какая... Или он не договаривает.

deep-purple ★★★★★
()

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

Навелосипедить чего-то можно легко. Для примера возьмем квадрат (0,0) - (1,1) и допустим, что мы знаем все f(x,0), f(0,y) for x,y in [0,1];

Тогда, если отображение выпукло, можем взять f(x,y) = 1/2*( y*f(x,0) + (1-y)*f(x,1) + x*f(0,y) + (1-x)*f(1,y) )

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

tyakos ★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.