Jump to content

Sky Slate Blueberry Blackcurrant Watermelon Strawberry Orange Banana Apple Emerald Chocolate
Photo

Awesome new PixelSearch and ImageSearch... OMG!


  • Please log in to reply
13 replies to this topic
Raccoon
  • Members
  • 178 posts
  • Last active: Oct 06 2014 05:58 PM
  • Joined: 02 Jan 2008
Currently, the commands are:PixelSearch, OutputVarX, OutputVarY, X1, Y1, X2, Y2, ColorID [, Variation, Fast|RGB]
ImageSearch, OutputVarX, OutputVarY, X1, Y1, X2, Y2, [*options] ImageFileSuggested addition:PixelSearch, OutputVarX, OutputVarY, X1, Y1, X2, Y2, ColorID [, Variation, Fast|RGB|Center]
ImageSearch, OutputVarX, OutputVarY, X1, Y1, X2, Y2, [*options *center *xn *yn] ImageFileExplanation of these changes:

The feature I am proposing is the ability for PixelSearch and ImageSearch to perform their scan in a center-out method, in addition to the current top-left-to-bottom-right scan, without breaking compatibility in existing scripts.

The benefit of a center-out scan becomes immediately obvious when trying to perform any type of object targeting, whether in a game or any dynamic interface. This center-out scan will enhance performance of existing scripts, and will open the doors to new uses of these two commands.

In the first command, PixelSearch, I propose the added Center option which can be used in combination with the existing Fast|RGB options. This will modify the behavior of the command, and will modify the definitions of the X1, Y1, X2, Y2 arguments. X1, Y1 would specify the center point coordinates to begin the pixel scan, X2, Y2 would specify the X-Radius (width) and Y-Radius (height) where-in scanning is to occur.

So instead of scanning starting at X1,Y1 top left, and continuing right-and-down to X2,Y2... it will scan from X1,Y1 center, and continue around in ever increasing circles (or squares) outward until the bounds of X2,Y2 radius have been reached.

Already many scripts try to simulate this method by confining PixelSearch to a small area, and then continually enlarge the area until a match has been found. Unfortunately, this generally means repeatedly scanning the same region over and over again with each subsequent enlargement.

With the second command, ImageSearch, the concept is very much the same with a couple of additions. The option *center (conforming with existing option flags) would define the meanings of X1, Y1, X2, Y2 same as with PixelSearch. While *xn and *yn will define a "hot spot" center in the image file that's being looked for.

The purpose of this hot-spot center is best imagined in a scenario where you're searching for the cross-hairs of a targeting reticule. You would want to begin searching where you last remember seeing the reticule, and you want to line it up with the center point of your cross-hairs image. In this way, the OutputX and OutputY values will be accurate with the target center, and not the top-left corner of the cross hairs image.


I do hope that either Chris or Lexikos will take on the charge of this feature request. I know there's a lot on both of their plates, but I sincerely believe this improvement will bring a lot more use to these commands.

Regards. Rac
Posted Image

Need help right away? Get live support on IRC.
Already have an IRC client installed? /join #ahk

Raccoon
  • Members
  • 178 posts
  • Last active: Oct 06 2014 05:58 PM
  • Joined: 02 Jan 2008
no replies? :cry:
Posted Image

Need help right away? Get live support on IRC.
Already have an IRC client installed? /join #ahk

  • Guests
  • Last active:
  • Joined: --

no replies? :cry:

...sucks don't it?...
Simple CMS/Wiki for creating pages for AutoHotkey Scripts?

Cyiode
  • Guests
  • Last active:
  • Joined: --
I could see this being implemented very easily for PixelSearch.

For ImageSearch, it would require a much more complex algorithm. Pattern matching algorithms seem to be designed to be efficient at searching from top left to bottom right. I'm not sure exactly out it would be implemented using your start at the center approach. If it's not done efficiently then you lose any benefit that you have gained by assuming the image is normally near the center of the region.

Another feature to add to this, would be not just specifying the "Center" as the starting point, but also you could give it an x,y as the starting point. That x,y position could be set to wherever it found the image the last time it searched, if you know that the image will again appear near where it appeared before.

Raccoon
  • Members
  • 178 posts
  • Last active: Oct 06 2014 05:58 PM
  • Joined: 02 Jan 2008
Cyiode: Starting with your final suggestion... The X1,Y1 that originally specified the top-left corner starting-point now specifies the center x,y pixel as the starting-point. Additionally, the X2,Y2 that originally specified the bottom-right corner ending-point now specifies the X-width and Y-width radius to search within. The only thing the 'Center' option does is change this behavior and the X1,Y1,X2,Y2 usage, rather than creating an entirely new command name. The command remains backwards compatible.

As far as the search algorithm potentially becoming inefficient, I don't see this as being a problem. The actual pattern matching is still performed from top-left to bottom-right for each match attempt, but the starting point (top-left corner) is moved around from the center out within the parent loop.
Posted Image

Need help right away? Get live support on IRC.
Already have an IRC client installed? /join #ahk

Scratch
  • Members
  • 108 posts
  • Last active: Mar 16 2014 08:02 PM
  • Joined: 22 Jan 2009
Nice suggestions, I'm always in favour for possible ways that speed up / ease up patternmatching.

To that end, may I suggest on top of that, the use of Masks, masks that will tell AHK not to search for every pixel contained in the Imagefile, but only for the onces that matter.

This becomes apparent in your Crosshair Example. Suppose You have a green crosshair and stored that in an imagefile, you're left with the problem that crosshairs move over a dynamically changing background.

You either have to make tens of imagefiles containing the crosshair with included background target, or a way to seperate the crosshair from any background info and tell AHK only to look for the crosshair, this is where the *Mask:color option comes in.

Suppose you have stored an imagefile of a green crosshair on a black background. Now tell AHK to ignore all black pixels in the search (background) and only match the remaining (green, foreground) pixels.

This works out as:

ImageSearch, OutputVarX, OutputVarY, X1, Y1, X2, Y2, *center *Mask:0x000000 ImageFile

This would find the crosshair regardless of its semitransparant nature and changing backgrounds.

Scratch that
  • Guests
  • Last active:
  • Joined: --

*TransN: This option makes it easier to find a match by specifying one color within the image that will match any color on the screen.



Scratch
  • Members
  • 108 posts
  • Last active: Mar 16 2014 08:02 PM
  • Joined: 22 Jan 2009
I will :lol:

But if I had some green pixels in the background the search would go wrong, it would be nice to have a hard exclusion zone to mask the background

Perhaps its even an idea to introduce a search-optimized graphics format and pre compiled your BMP/PNG pictures into chunks of machinecode that contains less, only the relevant pixels in optimized searchorder (no exception handling needed) and thus could be much faster than having the general purpose imagesearch algorithm search within a whole rectangle.

Like Icons in an imagelist, these compiled images/searchcodes could be loaded in memory at execution of the script for even faster matching.

Scratch that too
  • Guests
  • Last active:
  • Joined: --

But if I had some green pixels in the background the search would go wrong,

If the green background pixels on screen coincide with "*Trans" pixels in the search image, they would be ignored. That's the whole point of *Trans. e.g. Black pixels in the image will match anything if you use *TransBlack.

Scratch
  • Members
  • 108 posts
  • Last active: Mar 16 2014 08:02 PM
  • Joined: 22 Jan 2009
I will investigate this, do some testcode, before i run my mouth again, I admit I did not realize the full potential of the *Trans option, thx for pointing this out. I am doing a RTFM as we speak right now....

Meanwhile I would like to maintain that AHK definately could use suggestions such as from the original poster, to give it more speed in the graphics heavy department.

AHK is much more friendly for most of us to get into than lowlevel/C++ code, but still we wish we had that kind of performance and be able to accurately track dozens of objects realtime.

>> tested, works like charm

Jamie
  • Members
  • 129 posts
  • Last active: Dec 02 2012 04:59 AM
  • Joined: 26 Mar 2010
I've implemented a search algorithm that improves performance by changing the order that the template pixels are checked. It's not quite the same as the topic of this thread because it changes the order that the pixels within the template are checked, not the order in which candidate locations are checked. But the C code at the end could be modified or extended so it might be a useful starting point for getting your center-out search.

The reason I made this in the first place is that I had noticed poor performance with some templates, when the template has blank areas that are the same color as blank areas in the window.

As an example, consider searching for this template (a piece of the autohotkey logo): Posted Image

If the window has a lot of white area, and the search algorithm checks template pixels left to right, top to bottom, it has to scan many template pixels before finding a nonmatching one. This can be very bad if you're not careful to crop out as much background as possible.

My algorithm loads a template and rearranges it into a sort of 'out of order RLE' (OOORLE) format, with the least frequent template colors occuring first. Each run is encoded as six bytes: red, green, blue, x position (run start), y position, and run length. The template size is limited to 255x255 pixels for simplicity. Transparent template pixels are simply absent from the out-of-order RLE format and require neither space nor time. The OOORLE format also has five bytes at the very start to indicate the width and height and number of runs.

These are functions for loading a bmp image and transforming it into OOORLE format:
BMPWidth(ByRef bmpdata) {
  return NumGet(bmpdata, 18, "UInt")
}

BMPHeight(ByRef bmpdata) {
  return NumGet(bmpdata, 22 "UInt")
}

BMPBpp(ByRef bmpdata) {
  return NumGet(bmpdata, 28, "UShort")
}

; load bitmap and do some basic sanity checking
BMPLoad(fname, ByRef bmpdata) {
  FileRead, bmpdata, %fname%
  bytes := VarSetCapacity(bmpdata)
  ; check magick number
  if (NumGet(bmpdata, 0, "UShort") != 0x4D42) {
    return "bad bmp file format"
  }
  ; check expected file size in header
  if (NumGet(bmpdata, 2, "UInt") != VarSetCapacity(bmpdata)) {
    return "file size in header doesn't match actual file size"
  }
  ; check bits per pixel is something we can handle (24 or 32)
  bpp := BMPBpp(bmpdata)
  if (bpp != 24 && bpp != 32) {
    return "only 24 and 32 bit bitmaps are supported at the moment"
  }
  ; check compression
  if (NumGet(bmpdata, 30, "UInt") != 0) {
    return "only uncompressed (compression=0 for 'BI_RGB') is supported"
  }
  ; check height is positive (can't handle negative heights at the moment)
  if (BMPHeight(bmpdata) < 0) {
    return "negative height"
  }
  ; all passed, return empty string for success
  return ""
}

BMPGetPixel(ByRef bmpdata, x, y) {
  bpp := BMPBpp(bmpdata)
  width := BMPWidth(bmpdata)
  height := BMPHeight(bmpdata)
  stride := (bpp*width + 7)//8 ; number of bytes needed to encode the pixel data
  stride := (stride + 3) // 4 * 4 ; round up to the next multiple of 4 bytes
  headersize := 54 ; standard header is 54 bytes when there is no palette
  pixelbytes := bpp//8
  rowoffs := (height-1-y)*stride
  pixoffs := x*pixelbytes
  ; bytes are BB GG RR XX, but when read into a UInt on a little-endian machine
  ; it turns into 0xXXRRGGBB, where least significant bits is the blue value.
  xRGB := NumGet(bmpdata, headersize+rowoffs+pixoffs, "UInt") ; read 4 bytes which may include junk
  return (xRGB & 0xFFFFFF) ; discard the high byte
}

; transpc is the transparent color or -1 which won't match any bmp pixels
BMPTransform(ByRef bmpdata, ByRef output, transpc=-1) {
  height := BMPHeight(bmpdata)
  width := BMPWidth(bmpdata)
  colorlist := ""
  runcount := 0
  ; count the number of occurrences of each color, and build a list of all colors that appear
  Loop, %height% {
    y := A_Index - 1
    lastcolor := -1
    lastcount := 0
    Loop, %width% {
      x := A_Index - 1
      pixrgb := BMPGetPixel(bmpdata, x, y)
      if (n%pixrgb%) {
        n%pixrgb% += 1
      }
      else { ; first occurrence of this color
        if (pixrgb != transpc) {
          colorlist .= pixrgb . "|"
        }
        n%pixrgb% := 1
        r%pixrgb% := ""
      }
      
      if (pixrgb == lastcolor) { ; continue existing RLE
        lastcount++
      }
      else {
        if (lastcount > 0) { ; end of RLE
          if (lastcolor != transpc) {
            runstart := x - lastcount
            r%lastcolor% .= runstart . " " . y . " " . lastcount . "|"
            runcount++
          }
        }
        lastcolor := pixrgb
        lastcount := 1
      }
    }
    if (lastcolor != transpc) {
      runstart := width - lastcount
      r%lastcolor% .= runstart . " " . y . " " . lastcount . "|"
      runcount++
    }
  }

  StringTrimRight, colorlist, colorlist, 1 ; chop off trailing pipe character
  
  ; build a newline-delimited list of colors with their respective counts
  ncolorlist := ""
  Loop, Parse, colorlist, |
  {
    ncolorlist .= n%A_LoopField% . " " . A_LoopField . "`n"
  }
  StringTrimRight, ncolorlist, ncolorlist, 1 ; chop off trailing newline
  
  ; sort the list of colors from rarest to most common
  Sort, ncolorlist, N
 
  VarSetCapacity(output, 5 + runcount*6) ; 5 'header' bytes and each run consumes 6 bytes
  outbyte := 0
  NumPut(1, output, outbyte++, "UChar") ; magic number 1
  NumPut(width, output, outbyte++, "UChar") ; width
  NumPut(height, output, outbyte++, "UChar") ; height
  NumPut(runcount, output, outbyte, "UShort") ; number of runs (little endian format)
  outbyte += 2

  Loop, Parse, ncolorlist, `n
  {
    StringSplit, part, A_LoopField, %A_Space% ; part1 is the count, part2 is the color
    
    ; output the runs for pixels matching the color
    matchcolor := part2
    StringTrimRight, r%matchcolor%, r%matchcolor%, 1
    Loop, Parse, r%matchcolor%, |
    {
      StringSplit, xyc, A_LoopField, %A_Space%
      NumPut((matchcolor >> 16) & 255, output, outbyte++, "UChar") ; red
      NumPut((matchcolor >> 8) & 255, output, outbyte++, "UChar") ; green
      NumPut(matchcolor & 255, output, outbyte++, "UChar") ; blue
      NumPut(xyc1, output, outbyte++, "UChar") ; x coordinate of run start
      NumPut(xyc2, output, outbyte++, "UChar") ; y coordinate of run start
      NumPut(xyc3, output, outbyte++, "UChar") ; run length
    }
  }
  return outbyte ; should be 5+runcount*6
}

Then here are functions to grab a snapshot of a window to a DIB and then search that DIB for the OOORLE template:
OffscreenSnap(wid) {
  global snappixbuf, snapwidth, snapheight
  bpp := 24
  WinGetPos, , , snapwidth, snapheight, ahk_id %wid%
  sdc := GetDC(wid)
  dc2 := CreateCompatibleDC(sdc)
  hbmp := CreateCompatibleBitmap(sdc, snapwidth, snapheight)
  oldobj := SelectObject(dc2, hbmp)
  bufsize := AllocateDIBBuf(snappixbuf, snapwidth, snapheight, bpp)
  PrintWindow(wid, dc2) ; bitblt doesn't work for obscured or offscreen windows
  MakeBitmapInfoHeader(bmi, snapwidth, snapheight, bpp)
  GetDIBits(sdc, hbmp, 0, snapheight, &snappixbuf, bmi)
  SelectObject(dc2, oldobj)
  DeleteObject(hbmp)
  DeleteDC(dc2)
  ReleaseDC(wid, sdc)
}

SearchLastSnap(ByRef foundx, ByRef foundy, x1, y1, x2, y2, templaddr) {
  global snappixbuf, snapwidth, snapheight  
  static isearch24, first:=1
  if (first) {
    first := 0
    Base64Decode(isearch24, "i1QkIIPsJIA6AXQLuAIAAACDxCTCKAAPt0IDD7ZKAlOJRCQYVVZXi3wkSIvHK8"
    . "GLTCRQjVwIAQ+2QgGLTCREi/Er8ItEJEyNRAYBiUQkLItEJDyNdEADD7ZCBYhEJEwPtkIGiEQkPA"
    . "+2QgeIRCQSD7ZCCMHuAgP2iEQkUA+2QgkD9olcJDCIRCRIO/sPg48BAACLbCQ46wiNpCQAAAAAkI"
    . "lMJBg7TCQsD4NqAQAAD7ZEJEiLXCRAK9gPtkQkUCvfSw+v3gPBjQxAA92NRBkBiUQkKIpMJEw6SA"
    . "EPhRIBAACKTCQ8OggPhQYBAACKTCQSOkj/D4X5AAAAM8C5AQAAAIlMJCDHRCQcAAAAAGY7RCQkci"
    . "GLRCQYi1QkWItMJFyJAok5X15dM8Bbg8QkwigAkItUJFSFyQ+EtgAAAA+3RCQcjQRAilxCB40EQg"
    . "+2UAWIVCQWD7ZQBohUJBUPtlAIiFQkFA+2UAmKQAqIVCQTMtKIRCQXhMB2WoXJdFYPtkwkE4tEJE"
    . "ArwQ+2TCQUK8dID6/GD7bqA2wkGAPNi2wkOI0MSQPIOBwpjQQpdRKKTCQVOEgBdQmKTCQWOEgCdA"
    . "gzyYlMJCDrBItMJCD+wjpUJBdypotEJBxAiUQkHGY7RCQkD4JK////hckPhSX///+LVCRUi0wkGI"
    . "tEJChBg8ADiUwkGIlEJCg7TCQsD4LD/v//i0wkRItcJDBHO/sPgn/+//9fXl24AQAAAFuDxCTCKAA=")
  }
  
  x1 := (x1 < 0) ? snapwidth+x1 : x1
  y1 := (y1 < 0) ? snapheight+y1 : y1
  x2 := (x2 < 0) ? snapwidth+x2 : x2
  y2 := (y2 < 0) ? snapheight+y2 : y2
  searchwidth := x2-x1+1
  searchheight := y2-y1+1
  if (searchwidth < 0 || searchheight < 0) {
    return 0
  }
  rc := DllCall(&isearch24, "UInt", &snappixbuf, "UInt", snapwidth, "UInt", snapheight, "UInt", x1, "UInt", y1
  , "UInt", searchwidth, "UInt", searchheight, "UInt", templaddr, "UInt*", foundx, "UInt*", foundy)
  return rc
}

This is the C code for the "mcode" function stored in isearch24 (but base64 encoded to be more compact):
typedef unsigned char uchar;
typedef unsigned short ushort;
typedef unsigned int uint;

#define PLIST_HSIZE 5

uint __stdcall imgsearch24(uchar *DIB24, uint dibwidth, uint dibheight, uint searchx0, uint searchy0, 
				 uint searchwidth, uint searchheight, uchar *pixlist, uint *foundx, uint *foundy) 
{
	const uchar format = pixlist[0];
	if (format != 1) { // this function can only handle the 1-byte templates (dimensions up to 255)
		return 2;
	}
	const uchar templwidth = pixlist[1];
	const uchar templheight = pixlist[2];
	const ushort pixcount = *(ushort *)(pixlist + 3);
	const uint ylim = searchy0 + searchheight - templheight + 1;
	const uint xlim = searchx0 + searchwidth - templwidth + 1;
	const uint dibstride = (dibwidth*3+3)/4*4;
	const uchar firstr = pixlist[PLIST_HSIZE+0];
	const uchar firstg = pixlist[PLIST_HSIZE+1];
	const uchar firstb = pixlist[PLIST_HSIZE+2];
	const uchar firstx = pixlist[PLIST_HSIZE+3];
	const uchar firsty = pixlist[PLIST_HSIZE+4];
	for (uint y=searchy0; y < ylim; y++) {
		for (uint x=searchx0; x < xlim; x++) {
			uint match = 0;
			// check the first pixel outside the loop, might be faster
			if (firstr==DIB24[(dibheight-1-y-firsty)*dibstride+(x+firstx)*3+2] &&
				firstg==DIB24[(dibheight-1-y-firsty)*dibstride+(x+firstx)*3+1] &&
				firstb == DIB24[(dibheight-1-y-firsty)*dibstride+(x+firstx)*3]) 
			{
				match = 1;
				// look for a nonmatching pixel in the list
				for (ushort pixno=0; pixno < pixcount && match; pixno++) {
					const uchar pr = pixlist[pixno*6+PLIST_HSIZE+0];
					const uchar pg = pixlist[pixno*6+PLIST_HSIZE+1];
					const uchar pb = pixlist[pixno*6+PLIST_HSIZE+2];
					const uchar px = pixlist[pixno*6+PLIST_HSIZE+3];
					const uchar py = pixlist[pixno*6+PLIST_HSIZE+4];
					const uchar pc = pixlist[pixno*6+PLIST_HSIZE+5];

					for (uchar j=0; j < pc && match; j++) {
						const uint yoffs = (dibheight-1-y-py)*dibstride;
						const uint xoffs = (x+px+j)*3;
						const uchar b = DIB24[yoffs+xoffs];
						const uchar g = DIB24[yoffs+xoffs+1];
						const uchar r = DIB24[yoffs+xoffs+2];
						if (b != pb || g != pg || r != pr) {
							match = 0; // found a nonmatching pixel
						}
					}
				}
			}
			if (match) {  // didn't find any nonmatching pixels, we're good!
				*foundx = x;
				*foundy = y;
				return 0;
			}
		}
	}
	return 1;
}

This is showing very good performance for me, esp since I can grab the DIB once and then search it for numerous templates.

I hope this helps!

Raccoon
  • Members
  • 178 posts
  • Last active: Oct 06 2014 05:58 PM
  • Joined: 02 Jan 2008
:idea: {bumped}
Posted Image

Need help right away? Get live support on IRC.
Already have an IRC client installed? /join #ahk

otisg
  • Guests
  • Last active:
  • Joined: --
hi jamie, this looks great but how can i implement it? can you give an example? thank you!

Note from moderator: Removed huge quoted section.

MacroMan!
  • Members
  • 604 posts
  • Last active: Mar 20 2012 11:40 AM
  • Joined: 28 Aug 2009
Did you have to quote his entire post?
What ever happened, happened.