Jump to content

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

Gdip_ImageSearch


  • Please log in to reply
63 replies to this topic
guest3456
  • Members
  • 1704 posts
  • Last active: Nov 19 2015 11:58 AM
  • Joined: 10 Mar 2011
as i was trying to optimize this to make it faster, Uberi suggested i look into the Boyer-Moore-Horspool string searching algorithm. i spent a lot of time trying to understand that algorithm, looking at many examples across the web, and then learning C and getting MCode set up. finally, i decided to base my approach off of this stackoverflow post which suggested to use BMH only for the x dimension, and then once found, proceed with the normal naive search in the rectangle directly below. this makes a lot of sense and is easy to understand instead of trying to do full 2d BMH

my attempt is below. i share the code incase anyone wants to pick it up from here. maybe they can get it faster

i never got around to implementing the rest of the naive search below the first line, so the code below IS NOT COMPLETE. it will only match the first line of the needle in the haystack. after benchmarking at 50% slower than RSeding's naive algo, i decided to not puruse it since it was already slower, without even matching the whole image. maybe i've screwed something up.

benchmark RSeding vs my one line BHM:

Spoiler

 
and the C code used is below:
 
Spoiler


one thing i learned is that you cannot allocate memory inside the C function when calling via MCode, it will fail with the DllCall access violation. that is why i had to VerSetCapacity for the shift_table prior

Rseding91
  • Members
  • 703 posts
  • Last active: Apr 02 2016 05:05 AM
  • Joined: 07 Jun 2010

I meant to do this myself when all of the multi-image searching conversation started but I've been to busy. If maximum speed is wanted when searching for multiple images this would do that:

 

Us this: http://www.autohotke...ivision-on-x86/ to add a call-back to the image search code that sends a "found a match here (x/y)" message to the AHK script which then records that location and remove the "found it, now return" part of the C code.

 

 

The advantages of that being; the MCode is executed once in a single sweep through the image data doing call-backs each time it finds a match.



guest3456
  • Members
  • 1704 posts
  • Last active: Nov 19 2015 11:58 AM
  • Joined: 10 Mar 2011
interesting, thanks

the issue then is the best way to handle the incoming data via the callback function. because if you are running loops of many multiple image searches, that callback function will be getting triggered often, and you would need to manage how/when the callback occurred

i mean i guess you could also change the C function itself, instead of returning after a found image, you simply add the found x/y to an array, and then return the whole array ? is that possible?

MasterFocus
  • Moderators
  • 4323 posts
  • Last active: Jan 28 2016 01:38 AM
  • Joined: 08 Apr 2009

Very interesting indeed, Rseding91! However, what if the user only wants to find x intances of the needle?

My current code is able to handle this situation using the last parameter, "Instances" (by the way, 0 means "all").

Unless we pass the Instances value to the MCode itself... Hmmm, I shall think about that later!

 

I think what has been done so far has already improved Gdip_ImageSearch greatly.

I'm currently just doing some tests now regarding the use (or not) of PixelAverage.

I'm also trying to implement a search direction for the haystack instead of the needle.

 

I'm gonna be kinda busy until wednesday, but thanks in advance for your support! happy.png


-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Antonio França -- git.io -- github.com -- ahk4.net -- sites.google.com -- ahkscript.org

Member of the AHK community since 08/Apr/2009. Moderator since mid-2012.


MasterFocus
  • Moderators
  • 4323 posts
  • Last active: Jan 28 2016 01:38 AM
  • Joined: 08 Apr 2009

BUMP + EDIT

[ 24/march/2013 17:37h BRT ]

 

Code updated!

Further updates have already been made after the first commit of 24/march.

Make sure you check GitHub for the latest version: https://github.com/MasterFocus/

 

1st commit of 24/march: https://github.com/M...689dfc421f57f3d

1st commit of 23/march: https://github.com/M...e7de62bcf7263db

1st commit of 22/march: https://github.com/M...c21cad50d5ddff1

 

Additional notes (mostly not mentioned in the commit logs):

 

+ 24/march [first commit]

- Minor fix for TestScript.ahk (forgot to change the filenames after renaming the images)

- As promised, I added 4 new search directions and reduced Gdip_MultiLockedBitsSearch() accordingly

- I still have to adjust Gdip_SetBitmapTransColor(), and I also wanna review a few return values/methods

 

+ 23/march [first commit]

- A new function called Gdip_SetBitmapTransColor() is now available (which uses part of the old C code)

- The Trans parameter is now working correctly, but is supported only by Gdip_ImageSearch()

- To use any helper function directly, the user must set the bitmap transparency beforehand

- This new code should be even faster, as the transparent pixels are set only once in the whole process

- Thanks to guest3456 for his great help with the NumPut workaround

- I reordered the functions in the file, to match the order in which they are called (this may cause some confusion! sorry!)

- To do: implement 4 more haystack search directions and reduce Gdip_MultiLockedBitsSearch() as possible

- I'd also like to adjust Gdip_SetBitmapTransColor() later, so it can tell how many pixels were modified

 

+ 22/march [first commit]

- The new code should be faster than the previous one, according to my tests

- Thanks to Bentschi for his online MCode generatorhttp://www.autohotke...or-x86-and-x64/

- I know a few things regarding the search directions can be improved, but I just wanted to upload the latest changes ASAP

- I'm still thinking about a way to solve the current Trans problem (as showed in TestScript.ahk, I have to specify "ÿÿÿ" to use white as the transparent color)

 

Functions included in Gdip_ImageSearch.ahk as of 24/march/2013:

# Gdip_ImageSearch() # Gdip_SetBitmapTransColor() # Gdip_MultiLockedBitsSearch() # Gdip_LockedBitsSearch() #

These should work as tags for indexing the forum search.


-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Antonio França -- git.io -- github.com -- ahk4.net -- sites.google.com -- ahkscript.org

Member of the AHK community since 08/Apr/2009. Moderator since mid-2012.


Marshall666
  • Members
  • 45 posts
  • Last active: May 16 2013 04:03 PM
  • Joined: 09 Mar 2013

I would like to know how this works and how i can use it with my .png Image!

BUT my English is very terrible pls can somone translate this Thread? ;(

 

PLEEAASSEE!!!  ;(



MasterFocus
  • Moderators
  • 4323 posts
  • Last active: Jan 28 2016 01:38 AM
  • Joined: 08 Apr 2009

@Marshall666:

 

My current implementation (here) includes a header for Gdip_ImageSearch() which explains what each parameter means.

Also, the TestScript.ahk file shows a small usage example.

 

If you still have any problems, please let me know.

As you may not understand english very well, feel free to send me a message if necessary.


-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Antonio França -- git.io -- github.com -- ahk4.net -- sites.google.com -- ahkscript.org

Member of the AHK community since 08/Apr/2009. Moderator since mid-2012.


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

Great stuff guys, but could you write  wrapper around it so that you could search multiple needles in multiple haystacks in one go,

while allowing mixed use of bitmaps on screen or from file, something like:

 

image("novo1.png","novo2.png","myneedle:S1:100:100:150:150",IN,"myhaystack:S2:200:200","novo3.png")
 
MATCHES:  function returns these variables, values.
 
needles = 3
haystacks = 2
matches = 3
 
novo1matches = 0
 
novo2matches = 1
novo2match1 = novo3
 
myneedlematches = 2
myneedlematch1 = myhaystack
myneedlematch2 = novo3
 
An average user like me don't want to be concerned with opening and closing gdip in his script and making sure bitmaps are discarded,
I would be very happy if this could happen automatically in the Gdip script while calling the multi needle/haystack search function.
 
I really like how you have taken imagesearch to the next speed level, whats next GPU accelleration? . 


stevenp
  • Members
  • 197 posts
  • Last active: Sep 23 2014 05:47 PM
  • Joined: 28 Aug 2006

Great work, Thanks!

 

Just one addition - the OuterX2,OuterY2 parameters are broken, but it was easy to fix that by moving the Outer* assignments right after getting image dimensions

    ; Getting the dimensions 
    Gdip_GetImageDimensions(pBitmapHaystack,hWidth,hHeight)
    Gdip_GetImageDimensions(pBitmapNeedle,nWidth,nHeight)


    ; Adjust the search box. "OuterX2,OuterY2" will be the last pixel evaluated
    ; as possibly matching with the needle's first pixel. So, we must avoid going
    ; beyond this maximum final coordinate.
    OuterX2 := ( !OuterX2 ? hWidth-nWidth+1 : OuterX2-nWidth+1 )
    OuterY2 := ( !OuterY2 ? hHeight-nHeight+1 : OuterY2-nHeight+1 )
    

    ; locking the bits [haystack]
    ...

"Simplifying complexity is not simple"

MasterFocus
  • Moderators
  • 4323 posts
  • Last active: Jan 28 2016 01:38 AM
  • Joined: 08 Apr 2009

stevenp, how did you figure those were "broken"?

I've never had any similar problems, and I don't see what would currently affect those assignments.

(supposedly, the function should return if NumGet() fails)


-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Antonio França -- git.io -- github.com -- ahk4.net -- sites.google.com -- ahkscript.org

Member of the AHK community since 08/Apr/2009. Moderator since mid-2012.


stevenp
  • Members
  • 197 posts
  • Last active: Sep 23 2014 05:47 PM
  • Joined: 28 Aug 2006

It was easy to figure out because the specified bitmap that was loaded from a file with Gdip_CreateBitmapFromFile() was constantly failing to be found in another bitmap that was loaded with Gdip_BitmapFromScreen() in the specified rect constraints

I didn't dig deeper, but that was a solution


"Simplifying complexity is not simple"

fump2000
  • Members
  • 591 posts
  • Last active: Nov 11 2015 07:52 AM
  • Joined: 01 Nov 2012

Hello!

 

Can a bmpHaystack take an active window? If so, how should I go about it?

 

bg

fump



Raccoon
  • Members
  • 178 posts
  • Last active: Oct 06 2014 05:58 PM
  • Joined: 02 Jan 2008

Hey MasterFocus,

 

How impractical would it be to search the haystack from a specified coordinate and spiral outward?  For example, if you want to search for the match nearest to a target rectal or a point on a game map?  Or would it be cheaper to find _all_ matches and then do the distance math on each one?

P.S. I commented on your roman numeral script with a link to my own teensy version. :)


Posted Image

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

MasterFocus
  • Moderators
  • 4323 posts
  • Last active: Jan 28 2016 01:38 AM
  • Joined: 08 Apr 2009

@stevenp: I still don't see how that small change could have such effect. Unless you're searching a very specific area and the needle is being reduced by 1 pixel in both dimensions or something like that. I will investigate it later.

 

@fump2000: Yes. You probably want Gdip_BitmapFromHWND(). See: http://www.autohotke...area-of-screen/

Please refer to the GDIP topic if you need further help with that: http://www.autohotke...ary-145-by-tic/

 

@Raccoon: Thanks for the comment. I'm following you now on GitHub.  :)

I've already been interested in "spiral detection". It was too slow when I tried it with the default commands (PixelSearch, PixelGetColor, ImageSearch) some time ago.

I'm not 100% sure if I already tried to implement it in Gdip_ImageSearch()'s MCode, but I suppose it would still be slower.

It has something to do with the cache: reading sequential pixels is much faster than skipping, thus it may be more efficient to actually search all matches around the desired point and calculate the closest one afterwards.

Perhaps in January I'll have more spare time to experiment once again with spiral detection.


-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Antonio França -- git.io -- github.com -- ahk4.net -- sites.google.com -- ahkscript.org

Member of the AHK community since 08/Apr/2009. Moderator since mid-2012.


fump2000
  • Members
  • 591 posts
  • Last active: Nov 11 2015 07:52 AM
  • Joined: 01 Nov 2012
Hello! Is it possible to put a needle two image files? The problem is that changing the needle, depending on the status of the haystack.
 
----------------------------
 
To use a HWND with IE or other browsers, it is better to use this function (thx to "just me"): Gdip_BitmapFromScreen("hwnd:" . HWND)