SASGIS

Веб-картография и навигация

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

Обсуждение различной информации связанной с картографией в САСе, а также сторонние программные продукты для связки с САСом

Модератор: Tolik

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

Сообщение vdemidov » 15 дек 2008, 01:07

Не. Такой метод практически бесполезен. Малейшая потеря качества при перекодировании, или коррекция цвета и уже не пашет. В конце концов большой файл даже распаковать целиком в память уже проблема.
Чтобы понять программу, вы должны стать одновременно и машиной, и программой.
Аватара пользователя
vdemidov
Гуру
 
Сообщения: 1687
Зарегистрирован: 12 дек 2008, 13:10
Откуда: Киев
Благодарил (а): 191 раз.
Поблагодарили: 157 раз.

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

Сообщение Parasite » 15 дек 2008, 07:10

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

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

zed писал(а):делов-то...

А мужики-то из ABBYY\IRIS и не знают.... :lol:
The only difference between me and a mad man is that I am not mad. /Salvador Dali/
Изображение
Аватара пользователя
Parasite
Администратор
 
Сообщения: 5646
Зарегистрирован: 23 окт 2008, 17:38
Благодарил (а): 124 раз.
Поблагодарили: 512 раз.

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

Сообщение vdemidov » 15 дек 2008, 14:18

Ну жпег артефакты и маленькие повороты тем методом, который предлагал я схаваются без проблем. Главное быть уверенным, что размер участка, который мы ищем в большой картинке, будет очень близок к размеру образца.
Чтобы понять программу, вы должны стать одновременно и машиной, и программой.
Аватара пользователя
vdemidov
Гуру
 
Сообщения: 1687
Зарегистрирован: 12 дек 2008, 13:10
Откуда: Киев
Благодарил (а): 191 раз.
Поблагодарили: 157 раз.

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

Сообщение svp » 15 дек 2008, 15:41

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

Остаётся самая малость, разработать эти чудесные алгоритмы=)
Интересная задачка. В институте я решал похожую для индентификации самолётов по силуэтам. Само собой это было чуть проще: там по сути монохромная картинка рассматривалась.
Аватара пользователя
svp
Советчик
 
Сообщения: 447
ICQ: 204094886
Зарегистрирован: 26 авг 2008, 11:14
Откуда: Белгород
Благодарил (а): 2 раз.
Поблагодарили: 7 раз.

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

Сообщение vdemidov » 15 дек 2008, 16:20

Векторизация это очень дорогая и не устойчивая операция. Я предлагаю рассчитывать для искомого изображения инварианты Ху (их 7 чисел и они инвариантны к повороту, смещению и масштабированию), потом их же рассчитывать для разных окон на большом изображении. После чего по различию чисел судить о похожести каждого конкретного окна. Еще можно воспользоваться комплексными ортогональными моментами Цернике, они надежнее, но их рассчитывать сложнее.
Чтобы понять программу, вы должны стать одновременно и машиной, и программой.
Аватара пользователя
vdemidov
Гуру
 
Сообщения: 1687
Зарегистрирован: 12 дек 2008, 13:10
Откуда: Киев
Благодарил (а): 191 раз.
Поблагодарили: 157 раз.

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

Сообщение svp » 15 дек 2008, 16:26

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


На самом деле задача по сути не была поставлена. Слишком общие условия. Самое дешёвое решение в таком ОБЩЕМ случае -- разбить на квадраты и посадить за это дело трудолюбивых китайцев.
Векторизация хороша выигрывает у Вашего метода растр. в котором происходит поиск очень велик и в нём делают поиск неоднократно. Перебор всех возможных окон в растре -- очень трудоёмкая задача в этом случае. А вообще, чем чаще и быстрее надо делать поиск, тем сильнее надо упрощать исходные данные.
Аватара пользователя
svp
Советчик
 
Сообщения: 447
ICQ: 204094886
Зарегистрирован: 26 авг 2008, 11:14
Откуда: Белгород
Благодарил (а): 2 раз.
Поблагодарили: 7 раз.

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

Сообщение vdemidov » 15 дек 2008, 17:09

Не буду спорить, но при той формулировке, которая была векторизация слишко сложная и неэффективная, а окна можно с большим шагом брать, если предположить что большая картинка таки клеилась из тайлов, один из которых мы и ищем.
Чтобы понять программу, вы должны стать одновременно и машиной, и программой.
Аватара пользователя
vdemidov
Гуру
 
Сообщения: 1687
Зарегистрирован: 12 дек 2008, 13:10
Откуда: Киев
Благодарил (а): 191 раз.
Поблагодарили: 157 раз.

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

Сообщение Parasite » 15 дек 2008, 20:05

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

Тю. Всего-то навсего?
Если клеилась ровно по границам тайлов - то побить исходную картинку на блоки по 256\256, вычислить средневзвешенное значение цвет\яркость у искомого тайла, и пройтись по всем получившимся тайлам на предмет совпадения. False positive если и будут - то не так много, можно предложить юзеру выбрать нужное "глазками" либо провести более точный анализ уже по найденным.
Если большая картинка резалась не точно по тайлам, а произвольно - то сложнее. :(
The only difference between me and a mad man is that I am not mad. /Salvador Dali/
Изображение
Аватара пользователя
Parasite
Администратор
 
Сообщения: 5646
Зарегистрирован: 23 окт 2008, 17:38
Благодарил (а): 124 раз.
Поблагодарили: 512 раз.

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

Сообщение vdemidov » 16 дек 2008, 03:11

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

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

Пожалуйста. :lol:

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

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

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

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

A verbis ad verbera: готовы ли Вы написать законченное юзабельное приложение для запрашивающего? :)
Чтобы понять программу, вы должны стать одновременно и машиной, и программой.
Аватара пользователя
vdemidov
Гуру
 
Сообщения: 1687
Зарегистрирован: 12 дек 2008, 13:10
Откуда: Киев
Благодарил (а): 191 раз.
Поблагодарили: 157 раз.

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

Сообщение vdemidov » 17 дек 2008, 15:55

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

Ну если не морочить голову с размерами изображения, тоесть если большой джепег можно распаковать целиком в память, и не писать красивый GUI, то готов написать. Даже с произвольным сдвигом окна. И время работы будет сравнимое со временм иросчета средней якркости и контрастности.
Чтобы понять программу, вы должны стать одновременно и машиной, и программой.
Аватара пользователя
vdemidov
Гуру
 
Сообщения: 1687
Зарегистрирован: 12 дек 2008, 13:10
Откуда: Киев
Благодарил (а): 191 раз.
Поблагодарили: 157 раз.

Пред.След.

Вернуться в Другие программы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5

cron