Time complexity of ImageSearch Topic is solved

[tyroneous9]

How do options like shade variation and size scale (referring to n* and *wn) affect the time complexity of ImageSearch? My assumption is that each shade/size being checked will double the run time, but after very minor testing, they don't seem to have much impact.

[Rohwedder]

Hallo,
simply measure it yourself:

Code: Select all

DllCall("QueryPerformanceFrequency",Int:="Int64*",Freq),Time:=Count:=0
q::
DllCall("QueryPerformanceCounter",Int,Count1)
;Time duration measurement of this:
	Sleep, 50
;Multiple execution increases accuracy by means of averaging!
DllCall("QueryPerformanceCounter",Int,Count2)
ToolTip,% "Time: " Round((Time+=(Count2-Count1)/Freq*1.E6)/++Count) " µs"
Return

[boiler]

How do options like shade variation and size scale (referring to n* and *wn) affect the time complexity of ImageSearch? My assumption is that each shade/size being checked will double the run time, but after very minor testing, they don't seem to have much impact.

You are not thinking about how it checks for allowable shade variation correctly. It doesn’t do another scan for each allowable shade variation. And if it did, it would be much more than double (more like thousands or millions of times longer) because each pixel could vary in a different direction and/or amount, leading to tons of possible images it would need to scan for. It checks to see if the color value of each pixel is within the allowable range relative to that pixel in the reference image, which doesn’t take much longer than checking to see if it is an exact match. It is similar to checking if (x > 0 and x < 8) instead of just checking if (x = 5).

Also, the scaling options aren’t checking a variety of scales, so it wouldn’t increase the time to scan. It is scaling the image as specified then it performs the scan once.