Разработка findcolor, findimage, Pure lua Опции

[sutra]

А раньше как было ? GetDIBits вроде и возвращает битовую карту, где каждый элемент состоит из каналов. К чему там вообще memcpy был ? Чтобы обойти тормоза lua ?

Раньше я получал битовую маску и делал зеркалирование используя memcpy только в loadimage. Там всё нормально. Я и сейчас его использую. Но раньше это была реальная битовая маска: new('unsigned char[?]',maxPix*3+4)
Простой массив данных. Из него через индексы вытаскивались байты значений каналов. Поскольку я напрямую, без указателей к ней обращался (ну плюнул на память, хватает её, чего её жалеть). Вот я и подумал, а зачем такие сложности. Теперь сразу формирую образ в более удобном для использования виде: new("uint8_t["..maxHeight.."]["..maxWidth.."][3]")
Теперь обращение идёт напрямую в зависимости от координат поиска. memcpy я убрал из цикла поиска, при этом математики никакой не добавилось, вот за счёт этого получился такой прирост.

Я специально показал цикл поиска, можно сравнить с предыдущим кодом.

Я конечно не спец, но мне казалось что memcpy - это самый быстрый способ инициализации элементов массива, что тут сложного, даже проверки за выход диапазона не делается. То есть вызывая memcpy в цикле я инициализировал минимассив для каналов RGB, вместо использования математики для определения индекса. В общем не знаю что и как там влияет, результат получился отличный, а это главное.

[Cockney]

Я конечно не спец, но мне казалось что memcpy - это самый быстрый способ инициализации элементов массива, что тут сложного, даже проверки за выход диапазона не делается. То есть вызывая memcpy в цикле я инициализировал минимассив для каналов RGB, вместо использования математики для определения индекса. В общем не знаю что и как там влияет, результат получился отличный, а это главное.

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

[sutra]

В теории, выигрыш только на больших картинках, а так может даже и хуже

Я согласен, всё на всё влияет. Я для себя уяснил лишь одно, всё это актуально именно на больших циклах. Теперь то у меня memcpy используется в функции GetImage, для переброса данных из буфера (битовой маски) в массив, который я показал. Но там всё это выполняется мгновенно. Вся и фишка, что это улучшает работу поиска именно в FindImage. Остальное и так всё "летает".

Сейчас при поиске картинок вся математика цикла - два плюса, определяющие X и Y сравниваемого пикселя.

[sutra]

Попробовал как новая редакция отработает вариант поиска с целиковой картинкой, используя отсев пикселей. Улучшение составило всего 1 секунду. Было 10 сек. стало 9 сек. Но в любом случае быстрее.
Вообще главная проблема, что у меня получилась очень запутанная модель формирования искомой картинки. Я то за 2 года "руку набил" и сразу вижу как надо формировать картинку, а у людей возникают вопросы. Но без использования графического редактора, реально ускорить процесс, да ещё и обеспечить достоверность поиска - НУ НЕ ПОЛУЧИТСЯ.

Если подвести итоги, основанные на результатах различных вариантов поиска. По крайней мере для себя я уяснил одно. Есть какие-то ограничения по скорости в lua, если количество итераций циклов становится слишком большим. Вывод тоже напрашивается сам собой. Именно уменьшением искомых пикселей можно добиться приемлемого результата скорости и тут без редактора и творческого подхода проблему не решить или всё это надо делать не на lua. Но это уже не мой уровень.

Увеличил скорость поиска с 9 секунд до 6 секунд.
Что сделал, было local iy,ix=pic[1][i][0]+y,pic[1][i][1]+x
Убрал local, объявив переменные перед циклом.
Так что любой локал - распределение в памяти - это тормоз, интуиция меня не подвела.
Надо минимизировать такие конструкции.

[Cockney]

Можно картинки, на которых поиск идет такое время ?

[Cockney]

Так что любой локал - распределение в памяти - это тормоз, интуиция меня не подвела.
Надо минимизировать такие конструкции.

На сколько помню, это поможет до определенного момента, дальше пойдут провалы по скорости.

[sutra]

На сколько помню, это поможет до определенного момента, дальше пойдут провалы по скорости.

Я гарантировать что-то на lua даже пытаться не буду. В данном случае прирост 1/3 - это ОЧЕНЬ не хило. Люди за прирост скорости камушка в 10% бешеные деньги переплачивают, а тут все 33%. С точки зрения логики, я не вижу противоречий своему пониманию происходящего. В общем, что смог, то выжал из данного алгоритма. А других пока собственно и нет, может Дарк "допилит" свой, может Вы что-то предложите. Про стандарт даже заикаться не буду, там нет гарантий достоверности поиска, да и скорость не велика, даже при самых "благоприятных" условиях. А в рассматриваемых условиях мой алгоритм делает это за 6 секунд и находит всё, что должен находить, а стандарт это делает за 42 секунды (в 7 раз дольше) и находит не всё.

[sutra]

Ну и в 10-ый раз повторюсь. Я всё делал для собственных задач и просто поделился своими мыслями. Если кому-то это поможет, значит не зря это делал. Если кто-то матерится, что зря потратил время на чтение этой хрени - извините. У меня была одна проблема - getimage. Cirus избавил всех нас от этого "якоря", что удивительно предложив абсолютно стандартный подход решения сей проблемы, за что ему огромное спасибо.

[sutra]

Можно картинки, на которых поиск идет такое время ?

Так в моём архиве все картинки есть, ничего нового я не тестил специально. И код весь есть, пусть кривой и совсем сырой, но примеры вроде все корректно отработали.

Я про этот пример толкую, где лог такой:
Затрачено времени на поиск: 9.6900000000605

Сейчас у меня стал такой:
Затрачено времени на поиск: 5.8099999999977

[Cockney]

Ну если брать пример с картинкой игрового мира (Empire.bmp) и полной картинкой монетки (без обработки в редакторе) (gold.bmp), то поиск в моей версии идет 0.01с, вот и интересно почему в вашем варианте 6с.

[sutra]

Ну если брать пример с картинкой игрового мира (Empire.bmp) и полной картинкой монетки (без обработки в редакторе) (gold.bmp), то поиск в моей версии идет 0.01с, вот и интересно почему в вашем варианте 6с.

Ну не знаю. А количество? Координаты? Всё аналогично? Условия поиска?

Может чего не досмотрел, но когда я попробовал Ваш бенчмарк, что-то он там не то искал. Может новая версия есть?

По скорости понятно хуже быть не может, вопрос насколько прирост. Мне было лень проверять на Дельфине. Опять же скорость зависит от алгоритма, какой он у Вас я не знаю. Возможно как-то более продвинуто ищете.

[Cockney]

Ну не знаю. А количество? Координаты? Всё аналогично? Условия поиска?

Лучше я приложу последнюю сборку, а вы сами смотрите. Может я уже поплыл и не туда смотрю. Точность 90, отклонение цвета 30. Запускается точно также.

[sutra]

ОК. Попробую потестить и отпишусь.

[Cockney]

Проверил на своей варианте вариант с формированием матрицы [h][w][3]. Время загрузки ожидаемо выросло, а поиск занимает точно такое же время. Не знаю за луа, но видимо плюсовый компилятор умеет оптимизировать математику расчета индекса в цикле. Поэтому нет особого смысла делать такое на делфи/с++.

[sutra]

У Вас всё работает как надо. Насколько я понял deviation - это процент от 255 ? Как у Кнайта?
И вопрос, сам алгоритм поиска такой же? Или что-то своё хитрое?
Если такой же перебор всех позиций, значит скорость поиска выше ну где-то раз в 300 по сравнению с моим.

[Cockney]

У Вас всё работает как надо. Насколько я понял deviation - это процент от 255 ? Как у Кнайта?

Да, как у Кнайта. Само собой, когда нибудь будет и относительное и разность каналов.

И вопрос, сам алгоритм поиска такой же? Или что-то своё хитрое?
Если такой же перебор всех позиций, значит скорость поиска выше ну где-то раз в 300 по сравнению с моим.

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

[sutra]

Ну а вообще не удивительно. Я посчитал и если бы на lua скорость не падала на больших циклах, то про те 6 секунд, про которые я говорил, по идее максимум должен был бы быть 0,75 сек, а никак не 6 сек, не говоря уж про 10.

Ну а сам поиск многопоточный.

Ну значит всё так и есть. Если 0,75 разделить на потоки - это примерно как раз Ваш результат. Так что по уму надо делать dll.

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

[Cockney]

Исключение дублей нужно, но вопрос в том, что если вводить шаг, то тогда нужна уверенность, что в зоне правее/ниже не будет изображения с большей схожестью. Иначе ситуация когда у нас точность поиска 90-100, мы нашли изображение со схожестью ~80 и отбросили его, при этом сдвинулись на шаг (шаг размером 1 не имеет смысла, полагаю, что он как минимум равен половине ширины или высоты искомого изображения), а дальше ничего точно также не нашли. Единственный пока вариант, что предложил cirus: смотреть на диапазон координат, из него выбирать самый лучший процент совпадения, остальные в утиль.

[sutra]

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

Конечно, можно и так. Это так сказать более "ленивый" метод, для того, чтобы юзер совсем не напрягался. (IMG:style_emoticons/default/biggrin.gif)
Ну и конечно всё это надо потом проверять на практике. Что там отсеялось правильно, а что нет. В целом задача решена. Если всё это доведёте до финиша, юзеры будут благодарны. Я уже своё спасибо вам всем сказал. Я кое-чему всё-таки поднаучился.

В общем ждём ваших реализаций. Свой хлам больше тут показывать нет смысла. Всем удачи.

[Cockney]

Конечно, можно и так. Это так сказать более "ленивый" метод, для того, чтобы юзер совсем не напрягался. (IMG:style_emoticons/default/biggrin.gif)

Когда стоит задача найти что-то на экране (хорошо, что у меня таких нет), то на подбор шага, разницу каналов уйдет время. То, что функция тебе все найдет в наилучшем виде и САМА - это прекрасно. Конечно, будет 1% случаев, когда ну не находится и все, но и это подпилить можно. В конечном итоге, чем больше исходных данных тем меньше нужно делать функции. В идеале, было бы интересно видеть реализацию, где способ проверки пикселей и оценку результатов задает сам пользователь своей функцией, чтобы функция была максимально гибкой, но на вызовы функции тратиться уйма ресурсов, а вызывать придется много.