EDIT: removed a msgbox from the code I had for other purposes
I've played around with the code and managed to make the imagesearch with variance faster and in some cases depending on the needle much much faster.
I made the following changes:
- Moved the pointer math into the if statements
- Changed the if statements from: "if (N[#] > H[#]+V || N[#] < H[#]-V) nomatch" to:
- "if (N[#] < H[#]+V && N[#] < H[#]-V) continue checking"
Added the option to change the search direction on the needle
The huge speed improvement comes from the needle search direction option. The default method is left->right, top->bottom. The new option lets you specify which scan direction you want to use:
- 0 : auto detect best scan direction
- 1 : left->right, top->bottom
- 2 : left->right, bottom->top
- 3 : right->left, bottom->top
- 4 : right->left, top->bottom
The way auto detect works is:
- If auto-detect was set and variation was set and needle width >= 20 and needle height >= 20
- Copy the needle into 4 split images
- Average the A, R, G, B values for a given corner
- Find the number of pixels that do not fall +- 20 pixels of the average A, R, G, B values
- Scan from the corner with the highest unique pixel count first (1, 2, 3, 4)
In my testing the auto-detect takes maybe 10-20 milliseconds to run (not worth counting) on a
420x280 image. The speed improvement went from 47~ seconds to return no-match down to 500~ MS to return a no-match.
Gdip_ImageSearch(pBitmapHayStack, pBitmapNeedle, ByRef x, ByRef y, Variation=0, sx="", sy="", w="", h="", sd=0) { static _ImageSearch1, _ImageSearch2, _PixelSearch1, _PixelSearch2 if !_ImageSearch1 { MCode_ImageSearch1 := "83EC108B44242C9983E20303C28BC88B4424309983E20303C253C1F80255894424148B44244056C1F9023B44244C578944244" . "80F8DCA0000008B7C24348D148D000000000FAFC88B442444895424148B54242403C88D1C8A8B4C244C895C24183BC1894424407D7A895C24108D6424" . "008B6C2428C744243C000000008D6424008B44243C3B4424380F8D9400000033C985FF7E178BD58BF38B063B02752283C10183C20483C6043BCF7CED8" . "B44241C035C24148344243C0103C003C003E8EBC08B4424408B5C24108B4C244C83C00183C3043BC189442440895C24107C928B4424448B5424488B5C" . "2418035C241483C2013B54245089542448895C24180F8C5DFFFFFF8B5424548B4424585F5EC702FFFFFFFF5DC700FFFFFFFF83C8FF5B83C410C38B4C2" . "4548B5424408B4424585F89118B4C24445E5D890833C05B83C410C3" VarSetCapacity(_ImageSearch1, StrLen(MCode_ImageSearch1)//2) Loop % StrLen(MCode_ImageSearch1)//2 ;% NumPut("0x" SubStr(MCode_ImageSearch1, (2*A_Index)-1, 2), _ImageSearch1, A_Index-1, "char") } if !_ImageSearch2 { MCode_ImageSearch2 := "83EC208B44244853555657894424183B4424600F8D3E0400008B5C244C8B7C24508B6C24388BCB0FAFC8894C24148B4C24488D" . "7401FF8B4424640FAFF38B4C24548974242CEB098DA424000000008BFF894C24103B4C245C0F8DDD0300008BFF8B5424708B4C244883FA010F85DB0000" . "008B742414C7442458000000008D55028954242489742428394C24580F8DE403000033DB395C24440F8E910000008B4C24108D0C8E8B7424348D4C3102" . "8D49000FB671010FB67A018D2C063BFD0F8D510300002BF03BFE0F8E470300000FB6310FB63A8D2C063BFD0F8D360300002BF03BFE0F8E2C0300000FB6" . "71FF0FB67AFF8D2C063BFD0F8D190300002BF03BFE0F8E0F0300000FB671FE0FB67AFE8D2C063BFD0F8DFC0200002BF03BFE0F8EF20200004383C10483" . "C2043B5C24447C818B7424288B5424240374244CFF442458035424508B4C2448E934FFFFFF83FA020F85F4000000498974241C8BD38BF7F7DAF7DE8BD9" . "0FAFDF8D7C2B028954242889742424897C2420894C245883F9FF0F8EF202000033DB395C24440F8EAB0000008B7424108B4C241C8B5424208D0CB18B74" . "24348D4C3102EB078DA424000000000FB671010FB67A018D2C063BFD0F8D510200002BF03BFE0F8E470200000FB6310FB63A8D2C063BFD0F8D36020000" . "2BF03BFE0F8E2C0200000FB671FF0FB67AFF8D2C063BFD0F8D190200002BF03BFE0F8E0F0200000FB671FE0FB67AFE8D2C063BFD0F8DFC0100002BF03B" . "FE0F8EF20100004383C10483C2043B5C24447C818B7424248B5424288B4C24580154241C4901742420E92EFFFFFF83FA030F85FC0000008D51FF897424" . "208BCA8BF30FAFCFF7DEF7DF89742428897C2424894C241C8954245883FAFF0F8EF90100008B5C24444B83FBFF0F8EB30000008B7424208D14998B4C24" . "1003CB8D0C8E8B7424348D542A028D4C3102EB078DA424000000000FB671010FB67A018D2C063BFD0F8D510100002BF03BFE0F8E470100000FB6310FB6" . "3A8D2C063BFD0F8D360100002BF03BFE0F8E2C0100000FB671FF0FB67AFF8D2C063BFD0F8D190100002BF03BFE0F8E0F0100000FB671FE0FB67AFE8D2C" . "063BFD0F8DFC0000002BF03BFE0F8EF20000004B83E90483EA0483FBFF7F828B7C24248B7424288B4C241C8B542458017424208B6C24384A03CFE91EFF" . "FFFF83FA040F851F0100008B74241433FF897C2458897C242489742428394C24580F8D030100008B5C24444B83FBFF7E768B4C241003CB8D0C8E8B7424" . "348D149F8D542A028D4C31020FB671010FB67A018D2C063BFD7D702BF03BFE7E6A0FB6310FB63A8D2C063BFD7D5D2BF03BFE7E570FB671FF0FB67AFF8D" . "2C063BFD7D482BF03BFE7E420FB671FE0FB67AFE8D2C063BFD7D332BF03BFE7E2D4B83E90483EA0483FBFF7FA28B7424288B7C24240374244CFF442458" . "037C24508B4C24488B6C2438E94DFFFFFF8B4C24108B74242C8B7C24508B5C244C8B6C243841894C24103B4C245C0F8C29FCFFFF8B4C2454FF4424188B" . "542418015C241403F38974242C3B5424600F8CF9FBFFFF8B4C24688B54246C5F5E5DC701FFFFFFFFC702FFFFFFFF83C8FF5B83C420C38B4424688B4C24" . "108B54246C5F89088B4424145E5D890233C05B83C420C3" VarSetCapacity(_ImageSearch2, StrLen(MCode_ImageSearch2)//2) Loop % StrLen(MCode_ImageSearch2)//2 ;% NumPut("0x" SubStr(MCode_ImageSearch2, (2*A_Index)-1, 2), _ImageSearch2, A_Index-1, "char") } if !_PixelSearch1 { PixelAverage1 := "8B4C24148B44240833D2891189510489510889510C89511089511489511889511C3BC27E5B538B5C2414558B6C240C565783C502894" . "424248B7C241C3BFA7E338BF50FB646019901011151040FB6069901410811510C0FB646FF990141101151140FB646FE9901411811511C03F34F75D133D" . "283C504FF4C242475BC5F5E5D5BC3" , PixelAverage2 := "83EC1C8B4C243053568B318D5E1983C6E7897424088B7108578D7E1983C6E7897424148B71108B4918897C24108D7E1983C6E7897" . "4241C8D711983C1E7894C24248B4C243033C033D2897C24188974242085C90F8E8C0000008B74242C8B7C243483C6028974243C894C24308D64240085F" . "F7E600FB64E013BCB7F063B4C240C7D0683C00183D2000FB60E3B4C24107F063B4C24147D0683C00183D2000FB64EFF3B4C24187F063B4C241C7D0683C" . "00183D2000FB64EFE3B4C24207F063B4C24247D0683C00183D200037424384F75A48B7C24348B74243C83C604FF4C24308974243C758B5F5E5B83C41CC3" VarSetCapacity(_PixelSearch1, StrLen(PixelAverage1)//2) Loop % StrLen(PixelAverage1)//2 ;% NumPut("0x" SubStr(PixelAverage1, (2*A_Index)-1, 2), _PixelSearch1, A_Index-1, "char") VarSetCapacity(_PixelSearch2, StrLen(PixelAverage2)//2) Loop % StrLen(PixelAverage2)//2 ;% NumPut("0x" SubStr(PixelAverage2, (2*A_Index)-1, 2), _PixelSearch2, A_Index-1, "char") } if (Variation > 255 || Variation < 0) return -2 Gdip_GetImageDimensions(pBitmapHayStack, hWidth, hHeight), Gdip_GetImageDimensions(pBitmapNeedle, nWidth, nHeight) if !(hWidth && hHeight && nWidth && nHeight) return -3 if (nWidth > hWidth || nHeight > hHeight) return -4 sx := (sx = "") ? 0 : sx , sy := (sy = "") ? 0 : sy , w := (w = "") ? hWidth-sx : w , h := (h = "") ? hHeight-sy : h , sd := (sd < 0 Or sd > 4) ? 1 : sd if (sx+w > hWidth-nWidth) w := hWidth-sx-nWidth+1 if (sy+h > hHeight-nHeight) h := hHeight-sy-nHeight+1 if (sd = 0 And Variation And nWidth >= 20 And nHeight >= 20){ pBitmap_Needle_S1 := Gdip_CloneBitmapArea(pBitmapNeedle, 0, 0, Floor(nWidth / 2), Floor(nHeight / 2)) , pBitmap_Needle_S2 := Gdip_CloneBitmapArea(pBitmapNeedle, 0, Floor(nHeight / 2), Floor(nWidth / 2), Ceil(nHeight / 2)) , pBitmap_Needle_S3 := Gdip_CloneBitmapArea(pBitmapNeedle, Floor(nWidth / 2), Floor(nHeight / 2), Ceil(nWidth / 2), Ceil(nHeight / 2)) , pBitmap_Needle_S4 := Gdip_CloneBitmapArea(pBitmapNeedle, Floor(nWidth / 2), 0, Ceil(nWidth / 2), Floor(nHeight / 2)) , Last_Score := 0 , sd := 1 loop, 4 { Gdip_GetImageDimensions(pBitmap_Needle_S%A_Index%, Sector_Width, Sector_Height) if !(Sector_Width && Sector_Height) return -3 if (Gdip_LockBits(pBitmap_Needle_S%A_Index%, 0, 0, Sector_Width, Sector_Height, Sector_Stride, Sector_Scan, Sector_BitmapData)) return -5 VarSetCapacity(Sector_Averages, 8 * 4, 0) , DllCall(&_PixelSearch1, "UInt", Sector_Scan, "Int", Sector_Width, "Int", Sector_Height, "Int", Sector_Stride, "UInt", &Sector_Averages) loop, 4 N := NumGet(Sector_Averages, (A_Index - 1) * 8, "Int64") // (Sector_Width * Sector_Height) , NumPut(N, Sector_Averages, (A_Index - 1) * 8, "Int64") Sector_Score := DllCall(&_PixelSearch2, "UInt", Sector_Scan, "Int", Sector_Width, "Int", Sector_Height, "Int", Sector_Stride, "UInt", &Sector_Averages, "cdecl int64") , Gdip_UnlockBits(pBitmap_Needle_S%A_Index%, Sector_BitmapData) , Gdip_DisposeImage(pBitmap_Needle_S%A_Index%) if (Sector_Score > Last_Score) sd := A_Index, Last_Score := Sector_Score } } E1 := Gdip_LockBits(pBitmapHayStack, 0, 0, hWidth, hHeight, Stride1, Scan01, BitmapData1) , E2 := Gdip_LockBits(pBitmapNeedle, 0, 0, nWidth, nHeight, Stride2, Scan02, BitmapData2) if (E1 || E2) return -5 x := y := 0 if (Variation = 0) { E := DllCall(&_ImageSearch1, "uint", Scan01, "uint", Scan02, "int", hWidth, "int", hHeight, "int", nWidth, "int", nHeight, "int", Stride1 , "int", Stride2, "int", sx, "int", sy, "int", w, "int", h, "int*", x, "int*", y) } else { E := DllCall(&_ImageSearch2, "uint", Scan01, "uint", Scan02, "int", hWidth, "int", hHeight, "int", nWidth, "int", nHeight, "int", Stride1 , "int", Stride2, "int", sx, "int", sy, "int", w, "int", h, "int", Variation, "int*", x, "int*", y, "int", sd) } Gdip_UnlockBits(pBitmapHayStack, BitmapData1), Gdip_UnlockBits(pBitmapNeedle, BitmapData2) return (E = "") ? -6 : E }
The new C code is as follows:
int Gdip_ImageSearch2(unsigned char * HayStack, unsigned char * Needle, int w1, int h1, int w2, int h2, int Stride1, int Stride2, int sx, int sy, int w, int h, int v, int * x, int * y, int sd) { int tx, ty, ph, pn, Ah, Rh, Gh, Bh, An, Rn, Gn, Bn; int y1, y2, x1, x2; for (y1 = sy; y1 < h; ++y1) { for (x1 = sx; x1 < w; ++x1) { if (sd == 1){ ty = y1; for (y2 = 0; y2 < h2; ++y2) { tx = x1; for (x2 = 0; x2 < w2; ++x2) { if (Needle[(4*x2)+(y2*Stride2)+3] < HayStack[(4*tx)+(ty*Stride1)+3]+v && Needle[(4*x2)+(y2*Stride2)+3] > HayStack[(4*tx)+(ty*Stride1)+3]-v && Needle[(4*x2)+(y2*Stride2)+2] < HayStack[(4*tx)+(ty*Stride1)+2]+v && Needle[(4*x2)+(y2*Stride2)+2] > HayStack[(4*tx)+(ty*Stride1)+2]-v && Needle[(4*x2)+(y2*Stride2)+1] < HayStack[(4*tx)+(ty*Stride1)+1]+v && Needle[(4*x2)+(y2*Stride2)+1] > HayStack[(4*tx)+(ty*Stride1)+1]-v && Needle[(4*x2)+(y2*Stride2)] < HayStack[(4*tx)+(ty*Stride1)]+v && Needle[(4*x2)+(y2*Stride2)] > HayStack[(4*tx)+(ty*Stride1)]-v) tx++; else goto NoMatch; } ty++; } } else if (sd == 2){ ty = y1 + h2 - 1; for (y2 = h2 - 1; y2 > -1; --y2) { tx = x1; for (x2 = 0; x2 < w2; ++x2) { if (Needle[(4*x2)+(y2*Stride2)+3] < HayStack[(4*tx)+(ty*Stride1)+3]+v && Needle[(4*x2)+(y2*Stride2)+3] > HayStack[(4*tx)+(ty*Stride1)+3]-v && Needle[(4*x2)+(y2*Stride2)+2] < HayStack[(4*tx)+(ty*Stride1)+2]+v && Needle[(4*x2)+(y2*Stride2)+2] > HayStack[(4*tx)+(ty*Stride1)+2]-v && Needle[(4*x2)+(y2*Stride2)+1] < HayStack[(4*tx)+(ty*Stride1)+1]+v && Needle[(4*x2)+(y2*Stride2)+1] > HayStack[(4*tx)+(ty*Stride1)+1]-v && Needle[(4*x2)+(y2*Stride2)] < HayStack[(4*tx)+(ty*Stride1)]+v && Needle[(4*x2)+(y2*Stride2)] > HayStack[(4*tx)+(ty*Stride1)]-v) tx++; else goto NoMatch; } ty--; } } else if (sd == 3){ ty = y1 + h2 - 1; for (y2 = h2 - 1; y2 > -1; --y2) { tx = x1 + w2 - 1; for (x2 = w2 - 1; x2 > -1; --x2) { if (Needle[(4*x2)+(y2*Stride2)+3] < HayStack[(4*tx)+(ty*Stride1)+3]+v && Needle[(4*x2)+(y2*Stride2)+3] > HayStack[(4*tx)+(ty*Stride1)+3]-v && Needle[(4*x2)+(y2*Stride2)+2] < HayStack[(4*tx)+(ty*Stride1)+2]+v && Needle[(4*x2)+(y2*Stride2)+2] > HayStack[(4*tx)+(ty*Stride1)+2]-v && Needle[(4*x2)+(y2*Stride2)+1] < HayStack[(4*tx)+(ty*Stride1)+1]+v && Needle[(4*x2)+(y2*Stride2)+1] > HayStack[(4*tx)+(ty*Stride1)+1]-v && Needle[(4*x2)+(y2*Stride2)] < HayStack[(4*tx)+(ty*Stride1)]+v && Needle[(4*x2)+(y2*Stride2)] > HayStack[(4*tx)+(ty*Stride1)]-v) tx--; else goto NoMatch; } ty--; } } else if (sd == 4){ ty = y1; for (y2 = 0; y2 < h2; ++y2) { tx = x1 + w2 - 1; for (x2 = w2 - 1; x2 > -1; --x2) { if (Needle[(4*x2)+(y2*Stride2)+3] < HayStack[(4*tx)+(ty*Stride1)+3]+v && Needle[(4*x2)+(y2*Stride2)+3] > HayStack[(4*tx)+(ty*Stride1)+3]-v && Needle[(4*x2)+(y2*Stride2)+2] < HayStack[(4*tx)+(ty*Stride1)+2]+v && Needle[(4*x2)+(y2*Stride2)+2] > HayStack[(4*tx)+(ty*Stride1)+2]-v && Needle[(4*x2)+(y2*Stride2)+1] < HayStack[(4*tx)+(ty*Stride1)+1]+v && Needle[(4*x2)+(y2*Stride2)+1] > HayStack[(4*tx)+(ty*Stride1)+1]-v && Needle[(4*x2)+(y2*Stride2)] < HayStack[(4*tx)+(ty*Stride1)]+v && Needle[(4*x2)+(y2*Stride2)] > HayStack[(4*tx)+(ty*Stride1)]-v) tx--; else goto NoMatch; } ty++; } } x[0] = x1; y[0] = y1; return 0; NoMatch:; } } x[0] = -1; y[0] = -1; return -1; } int PixelAverage1(unsigned char * Needle, int w, int h, int Stride, long long int * ARGB_A) { int x, y; ARGB_A[0] = 0; ARGB_A[1] = 0; ARGB_A[2] = 0; ARGB_A[3] = 0; for (x = 0; x < w; x++) { for (y = 0; y < h; y++) { ARGB_A[0] += Needle[(4*x)+(y*Stride)+3]; ARGB_A[1] += Needle[(4*x)+(y*Stride)+2]; ARGB_A[2] += Needle[(4*x)+(y*Stride)+1]; ARGB_A[3] += Needle[(4*x)+(y*Stride)]; } } } long long int PixelAverage2(unsigned char * Needle, int w, int h, int Stride, long long int * ARGB_A) { int x, y, A0H, A0L, A1H, A1L, A2H, A2L, A3H, A3L; long long int c = 0; A0H = ARGB_A[0] + 25; A0L = ARGB_A[0] - 25; A1H = ARGB_A[1] + 25; A1L = ARGB_A[1] - 25; A2H = ARGB_A[2] + 25; A2L = ARGB_A[2] - 25; A3H = ARGB_A[3] + 25; A3L = ARGB_A[3] - 25; for (x = 0; x < w; x++) { for (y = 0; y < h; y++) { if (Needle[(4*x)+(y*Stride)+3] > A0H || Needle[(4*x)+(y*Stride)+3] < A0L) c ++; if (Needle[(4*x)+(y*Stride)+2] > A1H || Needle[(4*x)+(y*Stride)+2] < A1L) c ++; if (Needle[(4*x)+(y*Stride)+1] > A2H || Needle[(4*x)+(y*Stride)+1] < A2L) c ++; if (Needle[(4*x)+(y*Stride)] > A3H || Needle[(4*x)+(y*Stride)] < A3L) c ++; } } return c; }