Входные параметры:
1. Есть карта - растровое изображение. 
2. На карте обозначени объекты (оцыфрованы). Т.е. имеим их растровые координаты.
3. Объектов, скажем, n(растр) штук
4. Есть база данных реальных координат этих объектов.
5. Реальных бъектов в БД, n(реал) штук

Задача:
1. Найти линейную зависимость, дающую минимальную погрешность для перевода растровых координат в реальные, т.е. уравнения для Х и Y:
  RealX = AX + KX * RastrX
  RealY = AY + KY * RastrY

Дополнительные условия
1. n(растр) не обязательно равно n(реал), т.е. количество оцыфрованых объектов может быть равно, больше или меньше объектов в БД
2. Неизвестно какому объекту на карте соответствует какой объект в базе данных
3. Возможны промахи (большие отклонения) - некоторые объекти могут не соответствовать при преобразовании реальным координатам. Их надо исключать из расчета
4. Присутствует небольшая погрешность. При  преобразовании растровые объекти не абсолютно точно совпадают с реальными.

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

Подскажите методы, ссылки, в какую сторону копать

Присоединённый файл ( Кол-во скачиваний: 18 )
 __________.JPG 24,45 Kb

Полиномиальные преобразования
Полиномиальные преобразования - математика
Полиномиальные преобразования - примеры реализации

Насколько я понял именно это тебе нужно. И это ты уже реализовал? 

Кстати, я избавлялся от большой ошибки привязки(которая возникает в силу деформации исходного бумажного носителя из-за возраста или при сканировании) путём использования более совершенных алгоритмов привязки, например TPS (thin-plate spline interpolation). 

Далее про распознавание. Я не слишком понимаю, что тебе здесь нужно? Твои объекты это точки, линии или полигоны? Чем описываются объекты? Только координатами? Что именно распознавать надо мне неясно. 

Задача состоит в том, чтобы найти наиболее подходящую пару в случае, если объекты в БД и на растре не совпадают? 

Преобразования я реализовал. 

Объекты это только точки. Их характеристики координати XY. 

Проблема состоит в нахождении пары "точка растра" - "точка БД". Еще сложность в том что точек может быть не одинаковоэ количество. Или на растре оцифровано больше чем есть в БД или в БД больше чем оцифровано

Спасибо за линки! Почитаю.

Из-за чего возникает такая проблема? Из-за ошибки привязки? Вы, например, уверены, что у вас проекции соблюдены? А то в БД координаты точек в одной проекции, а при оцифровке вы их получаете в другой. 

Нет! Идея задачи поставить все на конвеер, т.е. пользователь оцыфровывает точки на карте(растре) и никак не сохраняет их названия(номер, подпись). Просто кликает мышью на точках и сохраняет ето в файл. Карт много, но объекты(точки) на них те же. Тоесть координаты точек в БД одинаковы, а на растрах разные. 
Оцифровав все карты (проклацав точки) пользователь сохраняет все эти файли в одну папку. 
Потом все это должно пакетно обработатся, без участия пользователя над каждой картой. Просто указать папку и система находит коефициенты уравнений для всех карт.

P.S.: Чтоб было понятней расскажу предметную область. Точки - это скважины. Карты различные - разных горизонтов, параметров, давлений и т.д. Но на всех картах отображены те же скважины. Получив уравнения по реперным точкам (скважинах) мы используя их преобразовываем другие объекты - линии, а так же можем узнать реальные координаты скважины которой нет в БД.
Фу! Ну й намудрил. Не знаю поймете ли вы из этого что-то ))


P.S.2: Вариант когда указывается пара точка растра - скважина сейчас работает и используется. Правда используется линейное преобразование с подбором угла поворота растра. Пробую прикрутить туда полиномиальные. Для увеличения производительности была принята попытка делать все конвеерно


Это сообщение отредактировал(а) elvis79 - 14.11.2008, 15:46

Подождите, я не понимаю  Давайте по-порядку.

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

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

Почему координаты полученных точек могут не совпадать с координатами точек в БД:

1. Ошибка пользователя. Пользователь неточно "тыкнул" на карте. Решается путём поиска ближайшей по координатами точки в БД.
2. Ошибка привязки. Скажем у вас растр деформирован и при решении системы уравнений в процессе привязки вы можете получить сильно изкажённую плоскость, поэтому при переводе локальных координат (растровых) в географические вы можете получать огромные погрешности. Решается использованием полиномов более высоких порядков и следовательно увеличением числа контрольных точек при привязке или использованием более совершенных алгоритмов, стойких в локальным деформациям растра(TPS например).
3. Разные проекции. Карта может быть отпечатана в проекции, например, Гаусса-Крюгера или UTM, а координаты точек в БД могут находится в прямоугольной географической проекции(Latitude&Longitude). Решается простым конвертированием точек из одной проекции в другую. Надо лишь знать в какой проекции находятся координаты. 

Они совпадают. Но я не знаю что, например первая точка на карте это скажем 10-я скважина, а вторая точка - это 8-я кважина

И этих данных нет в БД? И вы хотите, что бы из координат точки можно было получить номер скважины? 

Это надо как раз потом делать, и это решено. Вначале надо узнать какая локальная координата какой географической соответствует. 

В математическом смысле у нас есть 2 отдельных массива, причем не обезательно равной длины. Надо узнать какой елемент первого какому элементу вторго соответствует

Добавлено @ 16:06
А разве нельзя, имея 2 кучи точек, смасштабировав и повернув одну из них наложить на вторую чтоб точки совпали? 

Это сообщение отредактировал(а) elvis79 - 14.11.2008, 16:07

Это и есть привязка. И чтобы узнать какая какой соответствует вам надо иметь КОНТРОЛЬНЫЕ ТОЧКИ. Точки, чьи локальные и географические координаты известны, далее определиться с методом привязки и осуществить вычисления. 

Спасибо за ответы!

Буду прикручивать полиномиальные преобразования и думать как найти контрольные точки. 

Пока кроме простого перебора ничего в голову не приходит:
1. Найти 2 точки на растре между которыми расстояние наибольшее
2. Найти в БД эти 2 точки
3. Вычислить приблизительный коефициент массштабирования
4. Массштабировать растр и совместить координаты
5. В цыкле найти все расстояния от каждой трансформированой точки к каждой точке в БД. 
6. Взять пары точек в которых эти расстояния наименьшие
7. Реализовать полиномиальные преобразование

2 точки для привязки мало. Ну как минимум 3-4 по углам карты (для преобразований первого порядка требуется 3 уравнения), лучше штук 6-7 (для полиномиальных второго порядка). 




Зачем? Масштабирование и поворот учитывается при решении системы уравнений, поэтому это лишние действия.



Вообще не понял зачем.

Вам надо найти как минимум 3-4 угловые точки на растре и соответствующие им координаты точек в БД. Далее использовать сразу полиномиальные преобразования. 
Желательно взять ещё пару точек, тогда можно использовать преобразования второго порядка, что позволит увеличить точность.

Добавлено @ 16:42
Вот, ради интереса, какую картину получал я при решении похожей задачей теми же полиномиальными преобразованиями:



Растр был лишь слегка деформирован в правом нижнем углу из-за не очень качественного сканирования бумажного носителя, а ошибка достигала десятков километров между реальными точками на поверхности Земли и расчитанными мною. Алгоритм TPS меня спас.

Добавлено через 13 минут и 8 секунд
Кстати, могу поделиться классами для привязки карт на С++ как алгоритмом полиномиальных преобразований, так и алгоритмом TPS, я их когда-то выдёргивал из OpenSource ГИС-проектов. 

Это сообщение отредактировал(а) W4FhLF - 14.11.2008, 16:44

Вот это как раз и пытаюсь решить. Посмотрите на рисунок. Не могу придумать эфективный алгоритм для поиска пар точек

Линии которые нарисованы между точками растра и реальными точками - их на самом деле нет. Т.е. я не знаю какая точка растра какой реальной соответствует

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

Если листы примерно совпадают пространственно (т.е. нет ситуации, когда база единая на все точки, а каждый лист содержит малую часть точек), то можно предложить такой подход. Каким-то образом угадываем 2 точки (лучше по диагонали). Они дают нам линейное преобразование. По этому преобразованию вычисляем наиболее вероятное сответствие для 3й точки (т.е берем ближайшую к образу), уточняем преобразование, делаем то же для следующей точки и т.д. Если на каком то этапе невязки становятся слишком большими, то либо выбрасываем эти точки (если их мало), либо считаем, что первые 2 не угадали и пробуем угадать по другому.  В принципе, в последнем случае ошибка должна проявиться быстро, на 3-4 точках. Для угадывания первых точек можно разные варианты попробовать. Если угол поворота СК невелик, то можно, скажем, разбить лист на кластеры и попытаться совместить точки диагональных кластеров. В любом случае будет какая-то угадайка с проверкой и оценкой.

Поскольку задача поставлена для ускорения текущего процесса (когда пользователи все пары задают руками), то можно предложить частичное решение: пусть дадут руками 2 точки, а остальное вполне реально посчитать автоматом - лучше чем все вручную. А там, глядишь, для полной автоматизации что-нибудь придумаешь.

Добавлено через 6 минут и 14 секунд
Все таки странно, что ты используешь линейное преобразование. Афинное было бы лучше (6 коэффициетнов вместо 4), хотя тоже линейное. Насчет полиномиальных преобразований... не знаю... видела я карты скважин, там такие "относительные" координаты, что хорошо они привязываются только локальными преобразованиями - т.е. строим триангуляцию по опорным точкам, внутри каждого треугольника свое афинное преобразование. Все-таки полиномиальное преобразование подразумевает коррекцию непрерывных искажений, а на наших картах они... разные, в общем.

Что-то пробую и даже получается.

А насчет 

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

Для примера ниже привожу реальную карту:


Как видно, точек по краях у нас не будет, поскольку там нету скважин. И это создает определенные трудности и ошибки по краях. К тому-же 6 точек здесь не насобирается. Хотя есть карты где скважин может быть и несколько десятков.

W4FhLF, Earnest спасибо! Как решу. сообщу о результатах