http://www.youtube.com/watch?v=z00ORu4bU-A
http://dl.dropbox.com/u/8841028/raster_vec...nflate_1_lg.jpg
http://dl.dropbox.com/u/8841028/raster_vec...n/conflexex.gif
http://dl.dropbox.com/u/8841028/raster_vec...align/p6543.jpg

ну вообщем я думаю по картинкам понятно что нужно сделать.
вопрос есть ли это уже реализованное или хотя бы по каким словам гуглить.
возможно в каких то GIS системах это реализовано?

я нашел только немного по "conflation process"

Это сообщение отредактировал(а) mrgloom - 5.12.2012, 17:11

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

Не совсем понятно, что именно ты хочешь: чтобы оно совсем само или контрольные точки все же руками расставлять. Если второе, так практически все ГИСы это умеют в том или ином виде. Как обычно, задается набор пар точек и строится преобразование, например кусочно-аффинное. 
Собственно, полностью автоматическому процессу тоже нужен набор точек, только определить его он должен сам. 

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

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

но самое прекрасное в том, что преобразование нельзя описать даже перспективным искажением, т.е. можно попытаться "вписать"   используя перспективное искажение и использовать это только как первое приближение, но потом надо уже делать что то типа free-form\non-rigid дополнительного уточняющего наложения и я предполагаю что это можно сделать используя какой либо солвер\минимайзер, т.е. мы должны решить что то типа оптимизационной задачи(только как должна быть поставлена эта задача не очень понятно). 
непонятно даже можно ли задать преобразование параметрически, возможно можно использовать TPS(Thin plate spline).


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



 а что значит кусочно-аффинное? (что такое аффинное я знаю).
Да я хочу чтоб "оно само", но возможно для начала я могу позволить себе давать алгоритму начальное приближение руками или же использовать вписывание в преспективное преобразование как начальное приближение, т.е. сложность,как я писал выше, во втором шаге как это всё наложить более точно(например вписать в перспективное преобразование и потом для каждой точки найти ближайшую точку(тупо по евклидовой метрике) и варпнуть мне кажется не вариант).
http://www.eng.chula.ac.th/newsletter/file...6_dynamic_1.jpg
http://homepages.inf.ed.ac.uk/group/sli_ar.../DTWExplain.png
можно использовать что то типа как на картинках для локальной области, но мне кажется потом когда я буду варпать растр, будут "стяжки".  

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


возможно стоит поискать опенсорсные гисы которые так умеют, только непонятно по каким запросам гуглить.

Это сообщение отредактировал(а) mrgloom - 6.12.2012, 10:47

Кусочно-аффинное - это когда ты строишь по опорным точкам триангуляцию, и в каждом треугольнике свое преобразование. Опорные точки при этом ложатся точно. Опыт показывает, что локально-аффинное преобразование по триангуляции позволяет скомпенсировать почти любую кривоту. Понятно, что в определенных пределах. Из наложения карты Лас-Вегаса на Москву вряд ли что-то путное получится. Но, например, схему города (для туристов) можно наложить на снимок либо топографическую карту. Абсолютного совпадения, конечно, не будет, но основные перекрестки совместить можно.
Насчет поиска опорных точек (автоматического):
DTW-подход не очень поможет, мне кажется, ибо он предназначен для временных рядов, т.е. упорядоченных последовательностей. Если бы у тебя были 2 кривые, которые нужно сопоставить...
Что касается срезок при преобразованиях растра (да и вектора тоже), то да, они возможны, если преобразования в соседних треугольниках сильно отличаются или треугольники очень вытянутые. Если расставлять точки руками (и не ошибаться), то проблемы бывают редко.

Кстати, почему корректировать растр? Тема называется "наложить схему на растр", что предполагает растр как основу, т.е. тянуть эту самую схему. В принципе не важно, просто замечание.

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

Добавлено через 14 минут и 38 секунд
или вы про такое?

http://fiji.sc/wiki/index.php/Interactive_...g_Least_Squares

т.е. сетка постоянна, а деформация треугольников высчитывается исходя из смещения всех точек?

Это сообщение отредактировал(а) mrgloom - 6.12.2012, 14:52

Соединяются преобразования как-раз хорошо - в этом прелесть локально-аффинного, на границах треугольников оно 0-непрерывно. т е, прямая может изломиться, но не разорвется. На практике, при вменяемых преобразованиях, вообще все красиво. Но при плохих треугольниках возможны срезки...
Если говорить о трансформации растра, то триангуляцию нужно строить по точкам конечным (идеальным) чтобы делать обратное преобразование, т.е. заполнять новый растр последовательно и целиком. Для производительности, на каждой строке нового растра вычисляются диапазоны различных преобразований (т.е. пересечение строки с триангуляцией), чтобы не для каждой точки определять куда она попала.
И нет там никаких наименьших квадратов: 3 точки как раз определяют аффинное преобразование.

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

И да, точность регулируется число опорных точек => числом треугольников.
Метод хорош тем, что позволяет корректировать материал с неоднородными искажениями. Например, когда почти везде все хорошо, а один угол уплыл.

что то я эту сентенцию не понял.
что значит "изломиться, но не разорвется" т.е. сторона треугольника может стать не отрезком, а кривой?
"3 точки как раз определяют аффинное преобразование" три точки чего? каждого треугольника? если я двум соседним треугольникам например задам преобразования по 3-м точкам: одному задам стоять на месте, а второму сдвинуться на приличное расстояние, а одна сторона у них общая, то как они должны себя вести?

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

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

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