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

[sutra]

10 итераций (+- 20 по всем каналам) 1,2 сек. При работе в параллельном тесте, не прерывая работу моего другого скрипта.

Это large

И это искался и фон.

local PIC=f.CreateFindArray({{[[A:\fi_large.bmp]],r=195,g=195,dev=20}},1920) -- 0,109

Это задал фон - быстрее сразу в 10 раз.


В общем, однозначно пользуюсь своим, проверенным.

И что сложного в моих скриптах, на мой взгляд всё не так и сложно.

4 маленьких картинки нашлись за 0,13 сек (10 итераций цикла)

Как и говорил ранее - главный тормоз getimage . Теперь уже в прошлом!

[sutra]

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

Естественно всё это СИ-шные массивы.

Я знаю где тормоз. У меня матрица содержит сведения ГДЕ находится искомый пиксель. Я не лопачу всё подряд, а смотрю конкретную позицию. Вот за счёт этого и скорость. Дарю идею - пользуйся. Хотя ещё полтора года назад дарил.

n=ins+pic[i][6] -- это индекс в битовой маске - это ключ скорости.

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

[sutra]

Держи всё целиком. Лепил из кусков модуля, мог и накосячить, но вроде работает.
Только пути к файлам переправьте.

код

Код

--lua
local ffi=require "ffi"
local rmem=ffi.cast
log "clear" log "mode compact"                                                 -->Очистка лога. Установка компактного режима отображения лог информации
local function ImageToArray(ad,l,x1,y1,x2,y2,de)
  local h,w=y2-y1+1,x2-x1+1
  local k=h*w
  local d,a=ad+3*x1+l*y1,ffi.new("uint8_t["..k.."][3]")
  if w*3==l then
      for i=0,k-1 do  a[i][0],a[i][1],a[i][2],d=rmem("unsigned char*",d)[0],rmem("unsigned char*",d)[1],rmem("unsigned char*",d)[2],d+3  end
    else
      local i,s=0,l-w*3
      for y=1,h do
        for x=0,w-1 do  a[i][0],a[i][1],a[i][2],d,i=rmem("unsigned char*",d)[0],rmem("unsigned char*",d)[1],rmem("unsigned char*",d)[2],d+3,i+1  end
        d=d+s
      end
  end
  if de then  deleteimage(ad)  end  return a
end----------------------------------------------------------------------------
local function CreateFindArray(co,WI,deladr)
  local k,z,b,g,r,p,d,ad,w,h,l=0,0,ffi.new("uint8_t"),ffi.new("uint8_t"),ffi.new("uint8_t"),ffi.new("uint8_t[6]"),ffi.new("int16_t[6]")
  if type(co[1][1])=="string" then
      ad,w,h,l=loadimage(co[1][1])
    else  ad,w,h,l=co[1][1],co[1][2],co[1][3],co[1][4]
  end
  local ar,f,x,y,i,R,G,B,P,D,RG,RB,GB,ba,ga,ra,acc,v,zat=ffi.new("uint32_t[?][7]",w*h+1),ffi.new("uint16_t["..h.."]["..w.."]")
  if co[1].zat then  zat=co[1].zat/100  else  zat=0  end
  while z<#co do
   & nbsp;z,R,G,B,P,D,RG,RB,GB,y,x,i=z+1,true,true,true,true,true,true,true,true,0,0,
ad
    if co[z].r then  P,R,p[0],p[1]=false,false,co[z].r,co[z].R or co[z].r  end
    if co[z].g then  P,G,p[2],p[3]=false,false,co[z].g,co[z].G or co[z].g  end
    if co[z].b then  P,B,p[4],p[5]=false,false,co[z].b,co[z].B or co[z].b  end
    if co[z].rg then  D,RG,d[0],d[1]=false,false,co[z].rg,co[z].RG or 255  end
    if co[z].rb then  D,RB,d[2],d[3]=false,false,co[z].rb,co[z].RB or 255  end
    if co[z].gb then  D,GB,d[4],d[5]=false,false,co[z].gb,co[z].GB or 255  end
    if co[z].acc and co[z].acc<100 then  acc=(100-co[z].acc)/100  else  acc=0  end
    if co[z].dev then  v=co[z].dev  else  v=0  end
    if co[z].fgr then
        while y<h do
          while x<w do
            if f[y][x]==0 then
              b,g,r=rmem("unsigned char*",i)[0],rmem("unsigned char*",i)[1],rmem("unsigned char*",i)[2]
              if(D or((RG or r-g>=d[0]and r-g<=d[1])and(RB or r-b>=d[2]and r-b<=d[3])and(GB or g-b>=d[4]and g-b<=d[5])))and(P or((R or r>=p[0]and r<=p[1])and(G or g>=p[2]and g<=p[3])and(B or b>=p[4]and b<=p[5])))then
                if zat>0 then  b,g,r=math.floor(b-b*zat),math.floor(g-g*zat),math.floor(r-r*zat)  end
                k,ba,ga,ra,f[y][x]=k+1,b*acc+v,g*acc+v,r*acc+v,1
                ar[k]={math.max(0,math.floor(b-ba)),math.max(0,math.floor(g-ga)),math.max(0,math.floor(r-ra)),math.min(255,math.ceil(b+ba)),math.min(255,math.ceil(g+ga)),math.min(255,math.ceil(r+ra)),x+y*WI}
              end
            end
            i,x=i+3,x+1
          end
          y=y+1  i,x=ad+y*l,0
        end
      else
        while y<h do
          while x<w do
            if f[y][x]==0 then
              b,g,r=rmem("unsigned char*",i)[0],rmem("unsigned char*",i)[1],rmem("unsigned char*",i)[2]
              if not((D or((RG or r-g>=d[0]and r-g<=d[1])and(RB or r-b>=d[2]and r-b<=d[3])and(GB or g-b>=d[4]and g-b<=d[5])))and(P or((R or r>=p[0]and r<=p[1])and(G or g>=p[2]and g<=p[3])and(B or b>=p[4]and b<=p[5]))))then
                if zat>0 then  b,g,r=math.floor(b-b*zat),math.floor(g-g*zat),math.floor(r-r*zat)  end
                k,ba,ga,ra,f[y][x]=k+1,b*acc+v,g*acc+v,r*acc+v,1
                ar[k]={math.max(0,math.floor(b-ba)),math.max(0,math.floor(g-ga)),math.max(0,math.floor(r-ra)),math.min(255,math.ceil(b+ba)),math.min(255,math.ceil(g+ga)),math.min(255,math.ceil(r+ra)),x+y*WI}
              end
            end
            i,x=i+3,x+1
          end
          y=y+1  i,x=ad+y*l,0
        end
    end
  end
  if not(deladr)then  deleteimage(ad)  end  ar[0]={k,WI,w,h}  return ar
end --------------------------------------------------------------------------------
local function FindImage(a,lG,x1,y1,x2,y2,pic,numf,sim,v1,v2,v3) -- v1-v3 очерёдность анализа калов (0-blue, 1-green, 2-red) (нафиг не нужны, по логике должен быть прирост)
  local af,k,wi={},1
  if type(a)~="cdata" then
    if not(a)then
        x1,y1,x2,y2,a,wi,wi,lG=0,0,x2-x1,y2-y1,getimage(x1,y1,x2,y2,lG)
        a=ImageToArray(a,lG,x1,y1,x2,y2,true)
      else
        a=ImageToArray(a,lG,x1,y1,x2,y2)
    end
  end
  wi,numf,sim,v1,v2,v3=x2-x1+1,numf or 1,sim or 100,v1 or 2,v2 or 1,v3 or 0
  if type(pic)~="cdata" then  pic=CreateFindArray(pic,wi)
    elseif pic[0][1]~=x2-x1+1 then
--      log(pic[0][1],x2-x1+1)  -- оставлено информирование для себя, т.к. это лишний тормоз
      for i=1,pic[0][0]do     -- пересчёт позиций
        local ys=math.floor(pic[i][6]/pic[0][1])
        pic[i][6]=pic[i][6]-ys*pic[0][1]+ys*wi
      end
      pic[0][1]=x2-x1+1
  end
  if pic[0][0]==0 then  return 0,nil  end
  local sr,x,y,ins,xe,ye,V1,V2,V3,n=true,0,0,0,wi+1-pic[0][2],(y2+2-pic[0][3]-y1)*wi,v1+3,v2+3,v3+3
  if sim<100 then
      sim=pic[0][0]*0.01*(100-sim)  local j=0
      while y<ye do
        while x<xe do
          for i=1,pic[0][0]do     -- pic - матрица
            n=ins+pic[i][6]
            if a[n][v1]<pic[i][v1]or a[n][v1]>pic[i][V1]or a[n][v2]<pic[i][v2]or a[n][v2]>pic[i][V2]or a[n][v3]<pic[i][v3]or a[n][v3]>pic[i][V3]then
              j=j+1 if j>sim then  sr=false  break  end  -- sim аккуратность
            end
          end
          if sr then  af[k],k={x,y/wi},k+1  if k>numf then  return k-1,af  end  end
          x,sr,ins,j=x+1,true,ins+1,0
        end
        x,y,ins=0,y+wi,ins+pic[0][2]-1
      end
    else
      while y<ye do
        while x<xe do
          for i=1,pic[0][0]do
            n=ins+pic[i][6]
            if a[n][v1]<pic[i][v1]or a[n][v1]>pic[i][V1]or a[n][v2]<pic[i][v2]or a[n][v2]>pic[i][V2]or a[n][v3]<pic[i][v3]or a[n][v3]>pic[i][V3]then
              sr=false  break
            end
          end
          if sr then  af[k],k={x,y/wi},k+1  if k>numf then  return k-1,af  end  end
          x,sr,ins=x+1,true,ins+1
        end
        x,y,ins=0,y+wi,ins+pic[0][2]-1
      end
  end
  return k-1,af
end --------------------------------------------------------------------------------

local p,w,h,l=loadimage([[A:\scr.bmp]])
--local PIC=CreateFindArray({{[[A:\fi_large.bmp]],r=195,g=195,dev=20}},1920)
local PIC=CreateFindArray({{[[A:\fi.bmp]],r=195,g=195,dev=20}},1920)

local k,m
local t1=os.clock()
for i=1,10 do
  k,m=FindImage(p,l,0,0,1919,1079,PIC,5)
end
local t2=os.clock()
deleteimage(p)
log(k)
log(m[k][1],m[k][2])  -- 1874 1039
log(t2-t1)            -- 0.109

Дарк, сделай сворачивалку, забыл как.

Описание функций лень писать. Если у кого интерес будет - распишу всё подробно. Делал то для себя. Сам и то не всё помню, чего нагородил. Много можно упростить, так как особого прироста скорости нет.

Никакого контроля ошибок нет, так что аккуратнее.

Сообщение отредактировал DarkMaster - 5.4.2021, 23:47

[sutra]

z,R,G,B,P,D,RG,RB,GB,y,x,i=z+1,true,true,true,true,true,true,true,true,0,0,ad

Вот так должна выглядеть строка в функции CreateFindArray

которая следует за началом цикла
while z<#co do

почему-то некорректно копируется код. Так что правьте эту строку руками.

Ну или держите файл как есть.

[cirus]

DarkMaster, когда давно, по-моему ты и задавал вопрос как определяется точность, с которой была найдена картинка. Кнайт подтвердил мой предположение что точность определяется после поиска. Из чего можно сделать вывод что всегда ищется вся картинка. Т. е. в цикле нет проверки что дальше нет смысла искать, только счётчик сколько совпало пикселей. А уже после поиска проверка достаточно ли совпало пикселей.
Точность поиска не влияет на скорость в пилотном findimage, т. е. в нём явно нет тупого перебора всех пикселей. Также sutra писал что поиск тормозит при большом отклонении в цвете, что вполне логично, находится много пикселей и надо во всех проверить есть ли в этих местах картинка.
По сути надо как минимум 2 варианта поиска. Тот что сейчас сильно зависит от точности, но почти не зависит от отклонения в цвете. Предложенный мной вариант не зависит от точности поиска, но зависит от отклонения в цвете.

[DarkMaster]

точность определяется после поиска

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

[DarkMaster]

Кстати 1920*1080 ~= 2 миллионов, а не миллиардов :-P

[sutra]

Друзья, вы меня конечно извините, но вы не над тем голову ломаете. Давайте по фактам.
Чем больше диапазон поиска (не важно какими параметрами он расширен), тем дольше будет поиск и ничего тут ускорить нельзя. Дарк, твой пример для тестов не годится. Чтобы реально нагрузить поиск, весь экран должен быть напичкан похожими картинками. И вот для такого случая я бы привёл вам реальные примеры использования моего финда, увеличивая скорость поиска в разы.
Далее ... Одну картинку найти - это не проблема. Давайте исходить из того, что нам придётся искать их сотню. Я подправил немножко имеющийся тест, подсовывая для поиска в функцию не адрес, а СИ-шный массив. Скорость выросла ровно в 2 раза и составила 0,5 секунды.

Код

local p,w,h,l=loadimage([[A:\scr.bmp]])
local PIC=CreateFindArray({{[[A:\fi_large.bmp]],r=0,R=255,fgr=true,dev=20}},1920)
--local PIC=CreateFindArray({{[[A:\fi.bmp]],r=195,g=195,dev=20}},1920)
local SCR=ImageToArray(p,l,0,0,1919,1079,1)
local k,m
local t1=os.clock()
for i=1,100 do
  k,m=FindImage(SCR,l,0,0,1919,1079,PIC,5)
end
local t2=os.clock()
--deleteimage(p)
log(k)                -- 1
log(m[k][1],m[k][2])  -- 1874 1039
log(t2-t1)            -- 0.514

В принципе не так плохо. Но если тест будет не синтетическим, а реальным, скорость резко упадёт.
В чём моя фишка, в том, что я могу задавать последовательность поиска. То есть, первым условием я ставлю условие {r=0} - это искать голубые пиксели, так как их намного меньше. А вторым условием - искать все остальные {r=0,R=255} - это если учитывать все пиксели, в том числе и пиксели фона.
Моя матрица содержит X,Y искомых пикселей - вот за счёт чего достигается скорость. Ты повнимательнее Дарк посмотри код, уверен, что улучшишь свой алгоритм, хотя меня мой вполне устраивает. Если там сделать проверки на ошибки, можно запросто запускать в оборот.

[DarkMaster]

Сколько if'ов в секунду у тебя выполняется?

Дарк, твой пример для тестов не годится

Он был создан исключительно для тестов краев. После первой жалобы на скорость был создан большой квадрат.

[sutra]

Сколько if'ов в секунду у тебя выполняется?

Ну сколько ... примерно 1920*1080. Чего там искать на пустом экране? Я ж говорю тест слабый.

На практике, у любой картинки есть своя уникальность: сверкающий меч или шлем; опознавательный знак и т.д.. И у меня есть возможность задать приоритетные пиксели, с которых и начинается поиск, и в подавляющем большинстве случаев идёт переход на следующую итерацию поиска.

[sutra]

Единственное, что можно было бы добавить в мой (ну и в твой наверное тоже) алгоритм - шаг поиска картинки. Но мне это не надо, а всем остальным, как я понимаю мои идеи не интересны. Живой пример. Cirus кстати его давал. Нужно собрать ресурсы (золотишко) с домиков. Я могу легко и однозначно найти золото синтетической картинкой из 3-х пикселей. Но будет искаться несколько картинок на одном фрагменте золота, а вот если после первой найденной, делать смещение на n-е количество пикселей - этого можно избежать. Короче, найти можно абсолютно всё (ну почти всё), надо всё-таки двигаться в технологичном направлении. При подробном описании возможностей функции, с конкретными примерами, даже не самые продвинутые юзеры (хотя Пилот не для тупых) будут в восторге.

А тебе Дарк - это всё внедрить просто сам бог велел. Это же твой хлеб - реальные деньги. Нарисовал юзеру скрипт, который всех кладёт на лопатки - юзер тебя отблагодарит. Ну кроме меня, меня вам не уложить. (IMG:style_emoticons/default/biggrin.gif)

Если смог чем-то помочь, с вас новый loadimage , а то боюсь, что я с моим знанием СИ такого наваяю...

[DarkMaster]

Ну сколько ... примерно 1920*1080. Чего там искать на пустом экране?

При поиске картинки 46*41 с допустимым отсутствием 10% пикселей - это примерно 367 999 254 проверок. Это много. Поэтому я еще раз спрашиваю сколько ифов в секунду выполняет у тебя твой код?

Если смог чем-то помочь, с вас новый loadimage , а то боюсь, что я с моим знанием СИ такого наваяю...

Накидаю, как раз нужно мозги от финда отвлечь. Что-то тут не то, надо принципиально понять, что. 100% правильных идей (прям совсем правильных) мне приходили не за компом - код только мешает.

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

[sutra]

с допустимым отсутствием 10% пикселей

Нет там никакого отсутствия. Я искал с отклонением +-20. 1 951 885 if-ов.

[sutra]

Пропуск пикселей - это задача для мозгов. Тут ты никак не победишь тормоз. Глупо, наивно и бессмысленно искать с потерей 10% картинку такого размера. Пропуск нужен не для точности, для этого есть диапазон, а для поиска перекрытых друг другом картинок, как правило - это небольшие объекты. А для такой огромной картинки о каких 10% может идти речь? Предположим, на ней есть паразитное изображение, вопрос, какого оно размера? 10%? Не о том вы думаете. Короче, тут вопросы не к алгоритму, а к подходу к проблеме юзера и даже не заморачивайся на этом. ПРОПУСК - это край, и надо 100 раз почесать репу, прежде чем решить, а мне это надо???

Если пропускать, то обязательно применять МОЙ подход к делу.

Код

local p,w,h,l=loadimage([[A:\scr.bmp]])
local PIC=CreateFindArray({{[[A:\fi_large.bmp]],r=0,fgr=true,dev=20}},1920)
--local PIC=CreateFindArray({{[[A:\fi.bmp]],r=195,g=195,dev=20}},1920)
local SCR=ImageToArray(p,l,0,0,1919,1079,1)
local k,m,n
local t1=os.clock()
for i=1,10 do
  k,m,n=FindImage(SCR,l,0,0,1919,1079,PIC,5,90)  -- 90%
end
local t2=os.clock()
deleteimage(p)
log(k)                -- 1
log(m[k][1],m[k][2])  -- 1874 1039
log(t2-t1)            -- 0.842
log(n)                -- 13650074 ифов

А если искать все пиксели - даже пробовать не буду - лень ждать.

Я даже представить себе не могу, что может быть таким "паразитным" объектом. Гигантский прицел?

Если действительно возникает проблема, что юниты в куче друг на друге, только скрупулезный анализ изображений этих юнитов и грамотный подход к созданию эталонных картинок может решить вопрос скорости - это как раз ТВОЙ хлеб. А ежели кажный хмырь будет уметь это делать???

Короче. Резюме. Скорость - это не только алгоритм. Вся база на текущий момент практически идеальна. Всё равно - главное - это: размер картинки; зона (зоны) поиска; интеллектуальное слежение за объектами (что они как грибы? то тут, то там?); грамотное создание картинок; грамотное задание условий поиска. Да - это нельзя достичь тупо написав findimage, надобно включать голову, без этого никак. Всё, больше даже не желаю обсуждать эту тему.

[DarkMaster]

Нет там никакого отсутствия.

Так я поэтому и спрашивал. Deviation в моем методе поиска вообще никак не влияет на скорость. Хоть 1 хоть 255. У меня при твоих условиях делает 100 прогонов на 1.66 секунды. Поставь точность на 100% и девийшн в любое положение.

А для такой огромной картинки о каких 10% может идти речь? Предположим, на ней есть паразитное изображение, вопрос, какого оно размера? 10%?

Понятно, что тестовое изображение дубовое. Оно создано исключительно для того, чтобы давать нарузку и служить _стресс_ тестом.

Не о том вы думаете.

Проблема в том, что старый финдимидж все это лопатит несопостовимо быстрее. Т.е. если делать дубовый поиск влоб перебором, то у меня это 10 секунд, у старого финда - 0.1 секунды. Т.е. разницы в 100 раз. И это вопрос непосредственно алгоритма и его реализации. Т.е. при тех же входных данный дикий проигрышь. Ты говоришь, что скорость это основное - ну так проигрышь в 100 раз это нифига не правильно, да я понимаю, что это можно начать компенсировать правильным подбором изображения, но почему не привести сразу в порядок функцию непосредственно поиска? Это же логично. Хочется еще - образай картинки, тебе уже дали ускорение в 100 раз. Короче надо разбираться до конца. У меня есть идеи, хочу поднапрячь человека чтобы мне "правильных" изображений нагенерил. Правильных в том плане, чтобы они содержали критичные ситуации для разных типов подхода поиска. Тогда смогу оправдать или развеять мои теории.

Нет смысла убирать якорь в гетимидже и делать новый якорь в финдах =) Надо доводить до ума.

[sutra]

Проблема в том, что старый финдимидж все это лопатит несопостовимо быстрее

Что-то я такого не замечал. Для всех моих случаев, при моих условиях поиска, он был в 1000 раз медленнее. Надо будет как-нить потестить старый. Но я ж говорю, там даже на deviation такой якорь наступает, а это в 100 раз важнее пропуска, тем более, старый финд он чего ищет? Там конкретно просит фон, а всё остальное ищет - это вообще лично для меня неприемлемо. Там какой-то свой алгоритм, возможно есть там что-то, но только я сильно сомневаюсь, что там есть что-то супергениальное.

Что может найти старый финд? Кучу юнитов друг на друге - НЕТ? Прицел - НЕТ? Ничего подобного он не может, вот и весь мой вердикт.

Cirus, спасибо!!! Я однозначно перехожу на твою технологию. Напишете loadimage - спасибо. Нет, ну поковыряюсь сам, чего-нибудь однозначно придумаю.

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

[DarkMaster]

Напишете loadimage - спасибо

Я уже сказал, что накидаю.

[sutra]

Я не знаю как тестировать старый, только если искать изображение в редакторе. А как задать цикл? Если там всё время подгружается файл? Без цикла, будет неточный тест.

Если хватит воли и смогу победить свою лень, если потестирую старый - отпишусь.

[DarkMaster]

Я не знаю как тестировать старый, только если искать изображение в редакторе.

я так тестирую.

А как задать цикл? Если там всё время подгружается файл? Без цикла, будет неточный тест.

Можно использовать мой гетимидж.

По сути тест старого для меня лично особо не критичен. Понять бы как допрыгнуть)

[cirus]

Напишете loadimage

А чем пилотный не подходит? Адрес возвращает, больше от него ничего и не нужно.