Как "натянуть" одну фигуру на другую?

[arseniiv]

Kosat в сообщении #835909 писал(а):

Прочитал про афинные преобразования. Техники у меня особой нет. Не слишком ли это всё сложно реализовать НА ПРАКТИКЕ? Всё-таки это не понятно.

Аффинные преобразования обычно нетрудно, и я именно про вычисление параметров преобразования по каким-то данным (например, по образам данных трёх точек) — если всё правильно, получится СЛАУ, которая решается стандартно. Можно даже перспективное преобразование линейной системой определить (по образам четырёх данных точек). (У вас случай, конечно, сложнее, это я просто для примера привёл.)

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

-- Ср мар 12, 2014 19:41:53 --

arseniiv в сообщении #835929 писал(а):

параметрам преобразования (их всего шесть)

Для плоскости, конечно. В $\mathbb R^n$ их $n(n+1)$.

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

[Pavia]

Kosat в сообщении #835909 писал(а):

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

Каким образом? Я не говорил, что нужны сплайны.

Так уже писали.

svv в сообщении #834790 писал(а):

Есть идея. Сначала надо научиться любую фигуру (из хорошего, «допустимого» класса) отображать на круг. Тогда нужное Вам отображение между двумя фигурами можно построить как композицию отображений «фигура 1 $\to$ круг» и «круг $\to$ фигура 2».

Могу добавить берём на контуре N точек и на другом и нумеруем их. И ставим в соответствии точки с одинаковыми номерами.

-- Ср мар 12, 2014 19:30:03 --

arseniiv

arseniiv в сообщении #835929 писал(а):

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

Для градиентный спуска функция должна быть монотонной и гладкой. Что врят ли будет на практике. К примеру две одинаковых шестерёнки и попробуйте их по вращать.
Зато есть работы где с начало применяют оптимизацию по координате потом по вращению и с ново по координате и с ново по вращению. Пишут что достаточно 2-х циклов.

[arseniiv]

Pavia в сообщении #836011 писал(а):

Зато есть работы где с начало применяют оптимизацию по координате потом по вращению и с ново по координате и с ново по вращению.

Так я и предлагал по всем параметрам аффинного преобразования смотреть: вращения и всё другое выполнится при случае. Но метрика на афф. преобразованиях, инвариантная относительно изометрий точек пока не нашлась. (А бывает ли такая вообще.)

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

[rtfai]

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

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

[Kosat]

Прежде всего напомню, что мы общаемся в теме COMPUTER SCIENCE (практической!).

Вот TPS-функция для 3D в Matlab: http://www.mathworks.com/matlabcentral/ ... g-function . Непонятно, как тут это сделано – похоже, что центральная здесь только функция «псевдообращения (pinv)» (в отличии от двумерного случая, где в Matlab есть встроенная TPS-функция). Но вроде какой-то результат выдаёт (отдалённо похожий на тот, который я ожидаю).

Во время учёбы в вузе я уже сталкивался со случаем СЛАУ, где всё многообразие численных (и не очень) методов перечёркивается одной строчкой «обращения (inv)» в Matlab. Может, здесь тоже такой случай (хотя и писали, что эта тема близка не СЛАУ, а сплайнам, да и в отличие от этих «тем» данная есть отображение 3D в 3D, а не nD в 1D или 1D в 1D, что совсем непросто). Я прав?

P.S. У меня в запасе есть ещё одна функция для трёхмерного TPS-преобразования в Matlab, но и эта вроде работает. http://www.mathworks.com/matlabcentral/ ... te-splines

P.P.S. Вроде вся эта методология как-то близко связана именно с «афинным» преобразованием (с помощью матриц). Да же, вроде?

[Pavia]

Kosat в сообщении #837362 писал(а):

Во время учёбы в вузе я уже сталкивался со случаем СЛАУ, где всё многообразие численных (и не очень) методов перечёркивается одной строчкой «обращения (inv)» в Matlab.

Нет конечно. Есть же определённые, переопределённые, недоопределённые, совместные и не совместные СЛАУ. И inv может решать только узкий класс. Я бы использовал метод наименьших квадратов(МНК). Тем более в матлабе уже есть нужная функция lsqlin.

Kosat в сообщении #837362 писал(а):

Вроде вся эта методология как-то близко связана именно с «афинным» преобразованием (с помощью матриц). Да же, вроде?

Нет. Это два разных метода.
В афинном ты вращаешь перемещаешь и маштабируешь. А в TPS ты берёшь пластину за определённые точки и растягиваешь в разные стороны чтобы их совместить.