Поиск по изображению

[Гром]

Доброго времени суток!
Решил я недавно в образовательных целях написать бот для онлайн-игрушки (конкретно - хочу взять в качестве подопытного "Легенду: Наследие драконов", т.к. знаком с ней и представляю, чем может бот в ней заниматься).
Для начала, допустим, бот будет тупо собирать ресурсы. В Легенде это выглядит так: на экране "Охоты" на фоне локации ходят монстры, а также периодически появляются картинки различных ресурсов (растений/камней/круги на воде от рыбы), причем повернутые под различными углами, на эти картинки необходимо дважды щелкнуть мышкой, появляется прогресс-бар, через некоторое время ресурс собран (или нет - тогда появляется сообщение об этом).
Собственно, логика алгоритма вполне прозрачна:
1. Делаем скриншот окна браузера
2. Ищем на скриншоте (повернутое) изображение необходимого ресурса (его картинку мы заранее имеем на руках), если находим - переходим к пункту 3, если нет или ресурс занят (маленькая иконочка слева сверху от изображения) - к п.4.
3. Наводим курсор на изображение ресурса, клац-клац левой кнопкой и ждем окончания сбора, переходим к п.1.
4. Скроллируем окошко охоты или переходим в другую четверть поля охоты, переходим к п.1.
Однако, в отличие от остальных, пункт 2 вызывает у меня вполне естественное затруднение, т.к. раньше я подобные задачи себе не ставил. В связи с чем собственно вопрос:
Как же осуществить поиск в одном изображении другого, причем заведомо повернутого на неизвестный угол и имеющего прозрачные участки?
Если бы рисунки были однотонные, можно было бы, к примеру, построить для картинки ресурса гистограмму частоты вхождения пикселей различных цветов, потом строить такую же для различных фрагментов основной картинки и искать вхождения первой во вторую с учетом погрешностей (деформация картинки при повороте или небольшое изменение цвета картинки администрацией). Однако для трехканального цвета непрерывную (а для учета погрешности это важно) гистограмму можно разве что четырехмерную сделать. Цветовая модель HSB? Опять же - яркость и насыщенность.
В общем, пока себе слабо представляю, как можно такое провернуть без использования каких-нибудь особо тяжелых средств типа компьютерного зрения.
И еще один вопрос - а как найти на рисунке известный недеформированный фрагмент (в основном это касается надписей и кнопок)? Тупо сравнивать пиксели до полного сходства? Или есть более оптимальные способы?

Буду рад любой подсказке по данной теме - что почитать, какие средства использовать, что изменить в алгоритме и т.п.

P.S. Надеюсь, тема не противоречит правилам форума? Вроде еще раз просмотрел, ничего такого не нашел, опять же пишу для себя и с академическими целями.

[JDredd]

можно водить окошком :

вырезаем квадратик 5х5 пикселей из картики ресурса
находим среднее значение цвета

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

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

П.С. сам пишу бота, но для другой игры.

[Гром]

JDredd, в Легенде картинки ресурсов статичные, а вот монстров как раз анимированные. В принципе в некоторых случаях способ со "средним цветом" может сработать, правда, явно не во всех. К примеру, есть там такие монстры как "пес-демон" и "матерый пес-демон", которые на экране охоты выглядят как черные тушки с оранжевыми пятнышками лап и, вроде бы, еще морды. И при этом ходят по локации, где черный цвет - отнюдь не редкость. Да и вообще зачастую монстр или ресурс включает в себя несколько основных цветов, которые могут в принципе служить для индикации, но в область 5 на 5 не попасть.
В общем, хотелось бы услышать еще соображения данному поводу

[blob]

Копать в теме "свёртка" или "convolution" как подтема из image processing, преобразование Фурье (FFT). Почитать тут

[f.hump]

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