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

[vdemidov]

Не. Такой метод практически бесполезен. Малейшая потеря качества при перекодировании, или коррекция цвета и уже не пашет. В конце концов большой файл даже распаковать целиком в память уже проблема.

[Parasite]

В принципе, мне видется решение довольно просто:
побайтное/попиксельное (по 3 байта - если 24 битный bmp) сканирование большого снимка на предмет совпадения строки из малого файла

Как быть с масштабированием\поворотом искомого кусочка изображения и наличием (непредсказуемых) жпег-артефактов при распаковке к примеру жпег-сорца в БМП? Как быть с автоматической отработкой false-positive срабатываний?
Опять же, банальный перекос на доли градуса при сканировании (если брать сканированные изображения) оригинала - как "подложки", так и\или "искомого" - сведет весь метод на нет....

делов-то...

А мужики-то из ABBYY\IRIS и не знают....

[vdemidov]

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

[svp]

Раз уж речь зашла об алгоритмах... Тогда вот такие соображения:
1. Нужно преобразовать исходное и искомое изображение к виду, инвариантному поворотам, масштабированию изменению яркости, контраста и гаммы.
Для этого производим грубую векторизацию изображения, после чего избавляемся от абсолютных декартовых координат, заменяя их угловыми и относительнымивеличинами, характеризующими взаимное расположение точек.
2. Такому же преобразованию подвергаем искомый участок, учитывая, что края его не должны влиять на его результирующую внутреннюю векторную структуру.
3. После 1 и 2 пунктов мы имеем 2 графа, причём, если искомое изображение в исходном есть, то второй должен быть нечётким подграфом первого.

Остаётся самая малость, разработать эти чудесные алгоритмы=)
Интересная задачка. В институте я решал похожую для индентификации самолётов по силуэтам. Само собой это было чуть проще: там по сути монохромная картинка рассматривалась.

[vdemidov]

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

[svp]

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

На самом деле задача по сути не была поставлена. Слишком общие условия. Самое дешёвое решение в таком ОБЩЕМ случае -- разбить на квадраты и посадить за это дело трудолюбивых китайцев.
Векторизация хороша выигрывает у Вашего метода растр. в котором происходит поиск очень велик и в нём делают поиск неоднократно. Перебор всех возможных окон в растре -- очень трудоёмкая задача в этом случае. А вообще, чем чаще и быстрее надо делать поиск, тем сильнее надо упрощать исходные данные.

[vdemidov]

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

[Parasite]

большая картинка таки клеилась из тайлов, один из которых мы и ищем.

Тю. Всего-то навсего?
Если клеилась ровно по границам тайлов - то побить исходную картинку на блоки по 256\256, вычислить средневзвешенное значение цвет\яркость у искомого тайла, и пройтись по всем получившимся тайлам на предмет совпадения. False positive если и будут - то не так много, можно предложить юзеру выбрать нужное "глазками" либо провести более точный анализ уже по найденным.
Если большая картинка резалась не точно по тайлам, а произвольно - то сложнее.

[vdemidov]

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

Ну скажите пожалуйста

Пожалуйста.

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

Это то, что я и имел ввиду под словами "более точный анализ" из поста выше. Сперва грубо пройтись по всей большой картинке, потом уже по найденным совпадениям (с одновременным ужесточением параметров поиска, но и с большей точностью обсчета), потом - еще ужесточить и еще раз пройтись по оставшимся, итд итп, пока There must be only one!©
Просто считать ВСЮ картинку сразу по более точным (и более ресурсоемким) алгоритмам - это потеря времени, так как 99% из оных будет затрачено впустую (я не думаю, что на одной большой картинке будет много именно одинаковых тайлов, и именно их и будем искать).

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

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

A verbis ad verbera: готовы ли Вы написать законченное юзабельное приложение для запрашивающего?

[vdemidov]

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

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