Теория - Алгоритм поиска в двумерном массиве

[nslim13]

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

[shisik]

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

[Iska]

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




Цитата shisik:



и подсчитать кол-во пикселей заданных цветов в них?

Теория - Алгоритм поиска в двумерном массиве

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

[nslim13]

Цитата shisik:



ну а что мешает просто по порядку перебрать все возможные варианты и подсчитать кол-во пикселей заданных цветов в них?

Теория - Алгоритм поиска в двумерном массиве

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




Цитата Iska:



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

Теория - Алгоритм поиска в двумерном массиве

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

[lxa85]

nslim13, звучит слишком абстрактно. Корректней выражайте желания.

Помниться пару лет назад один из участников форума писал управлялку для он-лайн игры.

Чтобы она сама по локациям с заданным промежутком времени кликала и денежку собирала.

[lxa85]

Решал свои проблемы, заодно наткнулся на

подборку автокликкеров

.

Запись действий пользователя (клавиатура + мышь) воспроизведение, просто нажималки и прочее.

nslim13, там что-то и про цветовые пятна встречалось. Посмотрите.

[nslim13]

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

[lxa85]

nslim13, еще раз, полнее выражайте желаемое.

Желательно с кликабельными примерами, чтобы в гугл два раза не лазить.

https://habrahabr.ru/post/111339/

http://forum.codenet.ru/q52181/Прогр...шот+на+C%2B%2B

Устал, ничего более внятного ответить не сумею.

[nslim13]

http://kibor-bot.com/forum/topic.php?forum=1&topic=37

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



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

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