Поиск фрагмента карты/рисунка

[romangrom]

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

[romangrom]

Неужели ни у кого не было такой задачи?!?!?!

[svp]

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

Речь, кстати, идёт о гугловских снимках, или вообще абстрактных?
Для чего масштабирование? Это резко усложняет задачу. Вы хотите сказать, что надо искать фрагмент растра, который не только был вырезан, но и, возможно, смасштабирован?

[Parasite]

:( Неужели ни у кого не было такой задачи?!?!?!

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

[romangrom]

Спасибо за ответы; я действительно не хочу усложнять задачу, снимки гугливские, рисунок для поиска тоже, то есть обычный растровый поиск. Может есть какие-то соображения?

[vdemidov]

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

[romangrom]

А существует какая-то уже написанная программка по такому поиску?

[vdemidov]

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

[romangrom]

Буду искать.

[zed]

В принципе, мне видется решение довольно просто:
-конвертятся оба изображения в bmp/raw;
-затем - побайтное/попиксельное (по 3 байта - если 24 битный bmp) сканирование большого снимка на предмет совпадения строки из малого файла;
-как только строка найдена - проверка остальных строк (уже не сканированием, а на основе расчётов: в определённом месте большого bmp ищем соответствие строкам из малого файла).
делов-то... только написать прогу надо, а найти готовую будет наверное сложно.