Войти

Показать полную графическую версию : Алгоритм поиска в двумерном массиве


nslim13
27-07-2016, 21:58
Имеется двумерный массив элементами которого являются цвета пикселей (попросту - скриншот :) ). Необходимо найти квадрат заданного размера (для примера 100х100) который в себе содержит заданное количество пиксели заданного цвета (например цветов три: 20 пикселей красного цвета, 30 пикселей синего и 10 желтого). Для чего это нужно: я знаю, что на скриншоте присутствует объект непостоянной формы (а значит найти кусок изображения по шаблону не получится), но я знаю, что объект всегда содержит описанный выше набор пикселей. Существую ли алгоритмы решения подобной задачи?

shisik
28-07-2016, 02:25
nslim13, ну а что мешает просто по порядку перебрать все возможные варианты и подсчитать кол-во пикселей заданных цветов в них? Понимаю, не самый оптимальный способ. Но самый очевидный. То есть сначала берёшь квадрат от точки 0:0 и считаешь пиксели нужных цветов. Потом 0:1, потом 0:2 и т.д. Дойдёшь до конца - смещаешься на 1 вниз и по-новой: 1:0, 1:1, 1:2 и т.д.

Iska
28-07-2016, 02:58
nslim13, никак не получается 100x100 из 60 пикселей. И даже квадрат из 60 пикселей — ну никак не получается.

и подсчитать кол-во пикселей заданных цветов в них? »
Токмо «считать» достаточно один раз — в начале. Далее, при «перемещении» квадрата «над» полем, нужно вычитать цвета «уходящих» из-под квадрата пикселей и добавлять цвета «приходящих» в него.

nslim13
28-07-2016, 14:18
ну а что мешает просто по порядку перебрать все возможные варианты и подсчитать кол-во пикселей заданных цветов в них? »

В том-то и смысл, чтоб ускорить алгоритм, чтоб он мог выполняться в реальном времени

никак не получается 100x100 из 60 пикселей. И даже квадрат из 60 пикселей — ну никак не получается. »

Заданные пиксели не обязательно должны составлять 100% заданного квадрата. Задумка такая: на экране есть объект неопределенной формы (условно модель монстра в 3d игре). Я знаю, что монстр занимает примерный размер 100х100 пикселей на экране, имеет зеленые пятна на теле и красные глаза. По этим признакам я хочу определить координаты квадрата 100х100 в который входит хотя бы, например, 10 пикселей зеленого цвета и 4 пикселя красного. Как-то так...

lxa85
28-07-2016, 15:08
nslim13, звучит слишком абстрактно. Корректней выражайте желания.
Помниться пару лет назад один из участников форума писал управлялку для он-лайн игры.
Чтобы она сама по локациям с заданным промежутком времени кликала и денежку собирала.

lxa85
28-07-2016, 17:06
Решал свои проблемы, заодно наткнулся на подборку автокликкеров (http://www.lamerkomp.ru/load/sistemnye_utility/avtoklikery/56).
Запись действий пользователя (клавиатура + мышь) воспроизведение, просто нажималки и прочее.
nslim13, там что-то и про цветовые пятна встречалось. Посмотрите.

nslim13
28-07-2016, 17:56
Раз уж речь зашла об автокликерах - меня интересует алгоритм, как findheapcolor в kibor-bot (ищет области на которых есть скученности пикселей определенных цветов)

lxa85
28-07-2016, 22:19
nslim13, еще раз, полнее выражайте желаемое.
Желательно с кликабельными примерами, чтобы в гугл два раза не лазить.
https://habrahabr.ru/post/111339/
http://forum.codenet.ru/q52181/Программный+скриншот+на+C%2B%2B
Устал, ничего более внятного ответить не сумею.

nslim13
29-07-2016, 08:02
http://kibor-bot.com/forum/topic.php?forum=1&topic=37

Меня интересует реализация вот этогй функции. Возможно я просто неверно выражаюсь. Может это не поиск, а кластеризация, или классификация, или как-то еще...

Я написал для себя мини прогру, которая находит фрагмент изображения на скрине и возвращает его координаты (image template matching). Фрагмент в виде файла .bmp. Скрин и фрагмент преобразуются в двумерный массив целочисленных значений цветов пикселей. После этого осуществляется попиксельное сравнение двух массивов на предмет вхождения одного в другой. Работало, но медленно. Для ускорения я адаптировал под себя алгоритм Бойера-Мура, заменив им тупой перебор. Скорость поиска увеличилась в среднем в 5 раз. Приятно :)
Тепер я хочу расширить функционал, добавив такую же функцию, как по ссылке выше, и чую, что кибор реализовал ее не тупым перебором пикселей. Представьте сколько времени будет выполняться один проход по fullHD скрину...




© OSzone.net 2001-2012