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

[Cockney]

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

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

П.с. а вообще мог бы спросить напрямую у него на условиях не разглашения

[DarkMaster]

П.с. а вообще мог бы спросить напрямую у него на условиях не разглашения

Последний раз я говорил с ним в декабре. В январе я ему написал, потом еще написал, что мы его ждем (ты вроде просил). Жду ответа.

Причем список ухищрений и способов реализации в виде подробного описания у меня есть) А тупой перебор как он таким сделал понять не могу...

[Cockney]

Последний раз я говорил с ним в декабре. В январе я ему написал, потом еще написал, что мы его ждем (ты вроде просил). Жду ответа.

Причем список ухищрений и способов реализации в виде подробного описания у меня есть) А тупой перебор как он таким сделал понять не могу...

Значит это не тупой перебор, пример я привел

[DarkMaster]

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

[Cockney]

2.42. Нашел с закрашенными пикселями с точностью 100

[DarkMaster]

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

[DarkMaster]

Ты знаешь за прошедшие пару дней я получил столько удовольствия от оптимизации, что для меня ffi в луа c jit'ом впридачу кажутся более предсказуемыми.
Ну, например, есть цикл:

Код

    for (char *restrict area_y = area + area_offset_y1*area_lenght;
              area_y < area + (area_offset_y2-pattern_height)*area_lenght;
              area_y = area_y + area_lenght){
        // Перебор пикселей в линии скрина
        for (char *restrict area_x = area_y+area_offset_x1*3;
                      area_x < area_y+(area_offset_x2-pattern_width)*3;
                      area_x = area_x + 3){

Вот только незадача - нужно компенсировать "убегающую" единичку и строгое сравнение.
area_y < area + (area_offset_y2-pattern_height)*area_lenght
area_y < area + (area_offset_y2-pattern_height+2)*area_lenght

area_x < area_y+(area_offset_x2-pattern_width)*3
area_x < area_y+(area_offset_x2-pattern_width+2)*3
Ну какие могут быть от этого проблемы? А проблемы +26% времени поиска. Почему? Как? Площадь увеличилась на 4%, а время на 26%. Причем если не делать эти +2, а просто при вызове передать заведомо увеличенные на 2 pattern_height и pattern_width, то время выполнения не то, что не увеличится на 26%, а и вовсе где-то в погрешностях затеряется.

Причем это вершина айсберга. Там столько подобного бреда уже словил, что дальше некуда. Добавляем лишний счетчик - скорость увеличивается (просто счетчик который пишет в память выделенную вне длл). Удаляем паразитное условие, которое было просто для отладки - скорость падает. С такими приколами уже не знаешь, чего ожидать.

Сообщение отредактировал DarkMaster - 27.6.2022, 17:03

[Cockney]

Ты знаешь за прошедшие пару дней я получил столько удовольствия от оптимизации, что для меня ffi в луа c jit'ом впридачу кажутся более предсказуемыми.
Ну, например, есть цикл:

Код

    for (char *restrict area_y = area + area_offset_y1*area_lenght;
          area_y < area + (area_offset_y2-pattern_height)*area_lenght;
              area_y = area_y + area_lenght){
        // Перебор пикселей в линии скрина
        for (char *restrict area_x = area_y+area_offset_x1*3;
                      area_x < area_y+(area_offset_x2-pattern_width)*3;
                      area_x = area_x + 3){

Вот только незадача - нужно компенсировать "убегающую" единичку и строгое сравнение.
area_y < area + (area_offset_y2-pattern_height)*area_lenght
area_y < area + (area_offset_y2-pattern_height+2)*area_lenght

area_x < area_y+(area_offset_x2-pattern_width)*3
area_x < area_y+(area_offset_x2-pattern_width+2)*3
Ну какие могут быть от этого проблемы? А проблемы +26% времени поиска. Почему? Как? Площадь увеличилась на 4%, а время на 26%. Причем если не делать эти +2, а просто при вызове передать заведомо увеличенные на 2 pattern_height и pattern_width, то время выполнения не то, что не увеличится на 26%, а и вовсе где-то в погрешностях затеряется.

Причем это вершина айсберга. Там столько подобного бреда уже словил, что дальше некуда. Добавляем лишний счетчик - скорость увеличивается (просто счетчик который пишет в память выделенную вне длл). Удаляем паразитное условие, которое было просто для отладки - скорость падает. С такими приколами уже не знаешь, чего ожидать.

Я уже вроде писал, что особо ты ничего выкрутасами этими не добьешься. Мое мнение - нужно снижать алгоритмическую сложность. Условно, в стандартном варианте это O(n^4), т.к. 4 цикла вложенных. Сделая O(n^3) или еще лучше - O(n^2). Далее думай уже над мелочами типа скорость обработки инта.

А касательно магии, так это нормально. Тут нет логики. Нужно постоянно смотреть выхлоп компилятора, например, в rust, бывают такие вещи:

Код

int f1(int a, int b) {
   for (int i = 0; i < b; ++i) {
      a += i;
      if (a - 1 > b - 3)
         return a;
   }
}

Выполняется условные 10мс

А вот в таком варианте:

Код

int f1(int a, int b) {
   for (int i = 0; i < b; ++i) {
      a += i;
      if (a - 1 > b - 3)
         return a;
   }
   unreacheable!(); //подсказка компилятору
}

Выполняется менее 1мс.

Естественно такое поймать глазами почти невозможно. А компиляторы пока слабы в таких анализах вроде как.

Сообщение отредактировал DarkMaster - 27.6.2022, 17:03

[DarkMaster]

Условно, в стандартном варианте это O(n^4), т.к. 4 цикла вложенных. Сделая O(n^3) или еще лучше - O(n^2).

разворачивание вложенных циклов привело лишь к увеличению времени работы. Делал разные варианты (сейчас есть 8 штук и еще один на луа) вплоть до двух goto без форов и прозрачного вычисления следющего указателя. Смысла в этом не оказалось. Вцелом скорость сносная - 28мс на грубый перебор паттерна 10*10 в скрине 1920*1080 с дико древнем камнем q9600. Да, хотелось бы нолик убрать, а в идеале получить ~2мс на 15*15, но думаю, что это не очень реально - просто тактов даже при идеальном коде не хватит. У меня есть ряд идей по ускорению поиска, которые могут привести к скорости значительно выше, но при этом не будет соблюдаться правило строго порядка слева->направо, сверху->вниз, могут быть пропуски. Т.е. это шустрый вариант когда нужно выдернуть любое подходящее изображение в некоторой области (по факту не менее 90% поиска именно такие). Ну и многопоточку никто не отменял. Но все попорядку - нужно базу иметь адекватную. А в базе дикий вынос мозга ибо война с компилятором (IMG:style_emoticons/default/smile.gif)

[Cockney]

разворачивание вложенных циклов привело лишь к увеличению времени работы. Делал разные варианты (сейчас есть 8 штук и еще один на луа) вплоть до двух goto без форов и прозрачного вычисления следющего указателя. Смысла в этом не оказалось. Вцелом скорость сносная - 28мс на грубый перебор паттерна 10*10 в скрине 1920*1080 с дико древнем камнем q9600. Да, хотелось бы нолик убрать, а в идеале получить ~2мс на 15*15, но думаю, что это не очень реально - просто тактов даже при идеальном коде не хватит. У меня есть ряд идей по ускорению поиска, которые могут привести к скорости значительно выше, но при этом не будет соблюдаться правило строго порядка слева->направо, сверху->вниз, могут быть пропуски. Т.е. это шустрый вариант когда нужно выдернуть любое подходящее изображение в некоторой области (по факту не менее 90% поиска именно такие). Ну и многопоточку никто не отменял. Но все попорядку - нужно базу иметь адекватную. А в базе дикий вынос мозга ибо война с компилятором (IMG:style_emoticons/default/smile.gif)

Разворачивание циклов это не снижение сложности. Снижение сложности это когда вместо целого изображения обрабатываешь только половину, например

[DarkMaster]

Но это снижение вложенности. Прогнозирование ветвлений и все такое. Ну и компилятор черт пойми что соберет и в какую сторону его переклинит.

А искать куски имхо очень спорная идея. Ну возможно в каких-то случаях шаг сетки может помочь, идея спорная. С тем же успехом можно просто изображение сделать меньше. Я представляю себе развлечение с попытками найти кривые пиксели и перекрасить их в фон, когда там ищет сеткой. Лично мое мнение текущая скорость выполнения даже в 1 поток допустимая. Кстати сложность тут не O^4, а O1^2*O2^2, что сильно меняет дело, учитывая, что O1 и O2 у нас очень существенно отличаются. Да и ^2 тоже очень условно ибо далеко не всегда это квадратики, но тут уже можно в какой-то степени пренебречь.

[Cockney]

Но это снижение вложенности. Прогнозирование ветвлений и все такое. Ну и компилятор черт пойми что соберет и в какую сторону его переклинит.

А искать куски имхо очень спорная идея. Ну возможно в каких-то случаях шаг сетки может помочь, идея спорная. С тем же успехом можно просто изображение сделать меньше. Я представляю себе развлечение с попытками найти кривые пиксели и перекрасить их в фон, когда там ищет сеткой. Лично мое мнение текущая скорость выполнения даже в 1 поток допустимая. Кстати сложность тут не O^4, а O1^2*O2^2, что сильно меняет дело, учитывая, что O1 и O2 у нас очень существенно отличаются. Да и ^2 тоже очень условно ибо далеко не всегда это квадратики, но тут уже можно в какой-то степени пренебречь.

Ну скажем, худшая точно о(н^4), ибо можно искать 10х10 на скрине 10х10, частные случаи да, чуть меньше, но асимптотика такая же.

Почему спорная искать куски ? Если целиком искать то в игнор попадает 1 только цвет, при этом куча мусорных пикселей остается и съедает ресурсы. Ну, имхо, при поиске реального объекта типа монетки или галочки это выход, а вот просто мешанина уникальных пикселей - да, не очень.

[DarkMaster]

Как человек, который писал не под одну сотню приложений могу смело сказать, что реально однотонных пикселей найти бывает ну очень сложно. Даже если их будет 2-3 штуки либо пара групп по 2-3 штуки в изображении 10*10 - оно вообще никак существенно не повлияет на результат. Наличие реально однотонных объектов, где этот тон не является фоном - очень частный случай. Для меня сетка может иметь только некторый смысл в плане надежности поиска. Имхо 10 пикселей в куче может дать ложное срабатывание с бОльшим шансом, чем эти же 10 пикселей с некоторым шагом. Все остальное имхо частное.

Кстати конкретно про монетки и галочки - объекты мелки, как правило с очень хорошим контрастом относительно фона и резко отличающейся цветовой гаммой. Т.е. конкретно эти вещи - вообще пофигу чем и как искать, т.к. будет очень быстро и с минимальным перебором мусора.

[Cockney]

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

[DarkMaster]

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

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

Сообщение отредактировал DarkMaster - 18.6.2022, 10:12

[DarkMaster]

Можешь объяснить как tracy подключить к дллке?

Вообще приколы с кэшем оказались ключевыми с переборами. В зависимости от функции после оптимизаций получал увеличение производительности от 1.5 до 3.5 раз.

И есть еще одна проблема... как только я подключаю профайлер скрпт не может завершиться - доходит до конца виснет. Есть идеи?

[Cockney]

что такое tracy ? я нагуглил только профайлер.


Два варианта: 1) написать прокси-приложение где вызываются функции из длл и уже его подключить. но в таком случае только примерная инфа будет. 2) написать прокси-приложение и статически прилинковать библиотеку - получишь полную информацию

[DarkMaster]

Вообще трейси ты сам мне кидал линк пару страниц назад.

[Cockney]

Да я ж просто с гугла скидываю не запоминая. Тем не менее, примерные шаги отписал.

[DarkMaster]

C.GetDC(handle or 0)
вот эта радость почему-то не хочет работать с 12 директом. Идеи?