BmpSearch - Search for Bitmap within Bitmap - Assembly Version

[Beege]

Heres a function for searching for a bitmap within another bitmap. The heart of it is written assembly (source included) and working pretty quick I feel. I have included an example which is pretty basic and should be easily enough for anyone to get the concept. 

You will be given a small blue window that will take a screencapture of that size:

 

It will then take a full screenshot and highlight all locations that it found

Please let me know if you have any issues or questions. Thanks!

 

Update 8/5/2019:

Rewrote for fasmg. Added full source with everything needed to modify

BmpSearch_8-5-2019.7z

BmpSearch.zip

 

GAMERS - Asking for help with ANY kind of game automation is against the forum rules. DON'T DO IT.

Edited August 6, 2019 by Beege

[l3ill]

That is pretty fricken cool man!  

...good call on the disclaimer BTW

[Beege]

Thanks!  

[kvm2001]

Maybe you can add the ability to use mask and toloerance in your real cool lib? It'd make this a really invaluable.

[junkew]

nice.

See another one I wrote in AU3 

As I assume ASM will be much faster you could enhance it with some of the things I did in that AU3 version

• differentiate the colordepth (B/W, 4,8,16,32, n colors)
• find using line by line of the image searched (=search multiple bits at 1 call)

[HomeScript]

I have problem with this

#include <file.au3>
#include "BmpSearch.au3"

Global $Bmp1 = FileOpen(@ScriptDir & "\CALCULATOR.BMP")
Global $Bmp2 = FileOpen(@scriptDir & "\BACKSPACE.BMP")

Local $aCords = _BmpSearch($Bmp1, $Bmp2)

Error: 

Variable must be of type "Object".:
Local $iRowInc = ($tSizeSource.X - $tSizeFind.X) * 4
Local $iRowInc = ($tSizeSource^ ERROR

[Sw4rM]

Hello Beege, I impress with this UDF that it can search bitmap within another bitmap very fast. But it isn't work when I search 1x1 bitmap size (single pixel).

Please set these variables to 1
$hBMP_Width = 1
$hBMP_Height = 1

How can i fix it?

Best Regards
 

expandcollapse popup

#include <ScreenCapture.au3>
#include <Array.au3>
#include <GUIConstantsEx.au3>
#include <WindowsConstants.au3>
#include <GDIPlus.au3>
#include <BmpSearch.au3>

_Example()

Func _Example()
    local $hBMP_Width = 200
    local $hBMP_Height = 200

    local $FindX = 100
    local $FindY = 100

    _GDIPlus_Startup()

    local $WinHandle = _WinAPI_GetDesktopWindow()
    local $hDDC = _WinAPI_GetDC($WinHandle)
    local $hCDC = _WinAPI_CreateCompatibleDC($hDDC)
    local $hBMP = _WinAPI_CreateCompatibleBitmap($hDDC, $hBMP_Width, $hBMP_Height)

    _WinAPI_SelectObject($hCDC, $hBMP)
    _WinAPI_BitBlt($hCDC, 0, 0, $hBMP_Width, $hBMP_Height, $hDDC, $FindX, $FindY, $SRCCOPY)

    Local $BMP = _GDIPlus_BitmapCreateFromHBITMAP($hBMP)

    $hGUI = GUICreate("hFind", 400, 300)
    GUISetState(@SW_SHOW)

    ; Draw bitmap to GUI

    $hGraphic = _GDIPlus_GraphicsCreateFromHWND($hGUI)
    _GDIPlus_GraphicsDrawImage($hGraphic, $BMP, 0, 0)

    MsgBox($MB_TOPMOST, 'TEST', "Press OK")
    Sleep(500)
    GUIDelete($hGUI)

    Local $hSource = _ScreenCapture_Capture('')

    Local $aCords = _BmpSearch($hSource, $hBMP)
    If Not @error Then
        $iTime = @extended / 1000

        If $aCords[0][0] > 100 Then
            _ArrayDisplay($aCords)
        Else
            ;highligh matches
            Local $aGUI[$aCords[0][0] + 1]
            For $i = 1 To $aCords[0][0]
                ConsoleWrite($aCords[$i][0] & ',' & $aCords[$i][1] & ',' & $aCords[$i][2] & ',' & $aCords[$i][3] & @LF)
                $aGUI[$i] = GUICreate("", $aCords[$i][0], $aCords[$i][1], $aCords[$i][2], $aCords[$i][3], $WS_POPUPWINDOW, $WS_EX_CONTROLPARENT)
                GUISetBkColor(0xFFFF00, $aGUI[$i])
                WinSetTrans($aGUI[$i], '', 150)
                GUISetState(@SW_SHOW)
            Next

            MsgBox(0, 'Found', $aCords[0][0] & ' matches found. Time = ' & $iTime & ' ms')

            For $i = 1 To UBound($aGUI) - 1
                GUIDelete($aGUI[$i])
            Next
        EndIf

    Else
        MsgBox(0, 'NO MATCHES', 'No Matches Found!')
    EndIf

    _WinAPI_DeleteObject($hSource)
    _WinAPI_ReleaseDC($WinHandle, $hDDC)
    _WinAPI_DeleteDC($hCDC)
    _WinAPI_DeleteObject($hBMP)
    _GDIPlus_ImageDispose($BMP)
    _GDIPlus_GraphicsDispose($hGraphic)
    _GDIPlus_Shutdown()

EndFunc   ;==>_Example

 

[InnI]

18 hours ago, Sw4rM said:

How can i fix it?

In BmpSearch.au3 replace function _FindFirstDiff with this

;Find first pixel that is diffrent than ....the first pixel
Func _FindFirstDiff($tPix)

    ;####### (BinaryStrLen = 106) ########################################################################################################################
    Static Local $Opcode = '0xC80000008B5D0C8B1383C3048B4D103913750C83C304E2F7B800000000EB118B5508FF338F028B451029C883C002EB00C9C20C00'
    Static Local $aMemBuff = DllCall("kernel32.dll", "ptr", "VirtualAlloc", "ptr", 0, "ulong_ptr", BinaryLen($Opcode), "dword", 4096, "dword", 64)
    Static Local $tMem = DllStructCreate('byte[' & BinaryLen($Opcode) & ']', $aMemBuff[0])
    Static Local $fSet = DllStructSetData($tMem, 1, $Opcode)
    ;#####################################################################################################################################################

    Local $iMaxLoops = (DllStructGetSize($tPix) / 4) - 1
    If $iMaxLoops Then
        Return DllCallAddress('dword', DllStructGetPtr($tMem), 'dword*', 0, 'struct*', $tPix, 'dword', $iMaxLoops)
    Else
        Local $aRet[] = [1, DllStructGetData($tPix, 1, 1)]
        Return $aRet
    EndIf
EndFunc   ;==>_FindFirstDiff

 

[jmaruca]

Hi Beege,

This looks quite good and it works on Windows 10 x64.  Would it be possible to do some sort of search for a particular icon / button then double-click on it?.  I have been eagerly searching for a solution to select certain buttons on a Citrix Published application; would be really great, many thanks.

[Sw4rM]

@InnI Thank you so much, It works perfectly .

[Beege]

On 10/28/2018 at 9:39 AM, Sw4rM said:

Hello Beege, I impress with this UDF that it can search bitmap within another bitmap very fast. But it isn't work when I search 1x1 bitmap size (single pixel).

Please set these variables to 1
$hBMP_Width = 1
$hBMP_Height = 1

How can i fix it?

 

18 hours ago, InnI said:

In BmpSearch.au3 replace function _FindFirstDiff with this

Will that fix searching for a single row in general? 1x5 for example. Honestly I never even thought of that or a single vertical row. All three I think would fail with my code because im looking for 4 corners as a pre-check

[Beege]

19 hours ago, jmaruca said:

Hi Beege,

This looks quite good and it works on Windows 10 x64.  Would it be possible to do some sort of search for a particular icon / button then double-click on it?.  I have been eagerly searching for a solution to select certain buttons on a Citrix Published application; would be really great, many thanks.

Yes that should be possible. At one point in time I was making a capture tool that could be used to capture a small pic like your describing, and then encode the bmp into a string and wrap it up into a function that you could call for just for simply that - look for this picture and click here within that pic. I have not tried this on windows 10 yet but give this a shot and see if you have any luck getting it to generate. If works it will generate a function that has the picture of the icon you captured and will move the mouse to that location. I have the code to click the button commented out for testing. 

Edit: a little about how the tool works - after you capture an image, it will show you the image back zoomed in. This is so you can capture where you want the mouse to go. So capture one is the image you are looking for - capture 2 is where you want to click within that image. The idea here was to help in situations where you have multiple buttons on the screen that look the same. This way I can more easily say for example - find this picture, but click the top left corner. 

BmpSearch_with_Capture.zip

Edited October 30, 2018 by Beege

[MaximusCZ]

It seems OP script doesnt find results when its shown on negative coordinates. ie if primary monitor is on right side, whole space of left monitor have neagtive x coord.

Is there a way to make it search on all monitors?

[InnI]

8 hours ago, Beege said:

All three I think would fail with my code because im looking for 4 corners as a pre-check

Your function works good up to two pixels dimensions picture: 1x2 or 2x1. With my fix it works with 1x1 picture too (in fact returns array of pixels). But there is some trouble in algorithm on right side of image. Try this example

#include <WinAPIGdi.au3>
#include <BmpSearch.au3>
#include <Array.au3>

$hWnd = GUICreate("")

$hSource = _WinAPI_CreateSolidBitmap($hWnd, 0x00FFFFFF, 3, 3)
$hFind = _WinAPI_CreateSolidBitmap($hWnd, 0x00FFFFFF, 2, 2)

$aData = _BmpSearch($hSource, $hFind)
If @error Then Exit MsgBox(0, "", "Not found")

_ArrayDisplay($aData)

; result

; 5         <= must be 4
; 2 2 0 0
; 2 2 1 0
; 2 2 2 0   <= error
; 2 2 0 1
; 2 2 1 1

In white square 3x3 function finds 5 white squares 2x2, but must find 4. Algorithm does not stop on right side and continues to search on next row from left side. The result is a picture in which the left side of $hFind is found on the right side of $hSource, and the right side of $hFind on the left side of $hSource.

Also I think will be better to ignore alpha channel. Some functions return alpha channel as 0x00 (gdi32) but other as 0xFF (GDI+) and identical bitmaps will not be found.

And you need to add error checking after all _WinAPI_GetBitmapDimension functions.

[Beege]

12 hours ago, MaximusCZ said:

It seems OP script doesnt find results when its shown on negative coordinates. ie if primary monitor is on right side, whole space of left monitor have neagtive x coord.

Is there a way to make it search on all monitors?

Correct.. The OP script example does not search all monitors. Remember, this function is for searching bitmaps, not the monitors. If you need to search your other monitors, your script needs to take screenshots of the other screens and feed them into the _Bmpsearch()

[Beege]

7 hours ago, InnI said:

Your function works good up to two pixels dimensions picture: 1x2 or 2x1. With my fix it works with 1x1 picture too (in fact returns array of pixels). But there is some trouble in algorithm on right side of image. Try this example

Thanks Innl, Ill be rethinking some of these scenarios pointed out. Post that ex function

[MaximusCZ]

9 hours ago, Beege said:

Correct.. The OP script example does not search all monitors. Remember, this function is for searching bitmaps, not the monitors. If you need to search your other monitors, your script needs to take screenshots of the other screens and feed them into the _Bmpsearch()

Thank you, elegant solution that just didnt cross my mind.

Also, its interesting that when I work with example, I select an area on screen and let it find, it reports the output on same coords, but size is -1 in ever direction than given example:

 

First line is marked area, second line is first area found.

 

btw, Are you thinking about adding some tolerance in variation? Sometimes (in some programs regulary) you cant find same bitmap twice because of very tiny variance in pixel colors

[InnI]

On 10/31/2018 at 12:37 AM, Beege said:

Post that ex function

I used _BmpSearch quite often. And I made some changes to improve usability:

• now it is not a UDF, but a function
• now the function accepts not only gdi32 hBitmap, but also GDI+ hImage or simply path to image file
• now there is no problem with the alpha channel
• now you can search for a 1x1 pixel image and get array of pixels
• now the search time is returned to the $aCoords[0][1] in milliseconds
• added error checking

expandcollapse popup

#include <GDIPlus.au3>

#pragma compile(x64, false)

; #FUNCTION# ====================================================================================================================
; Name          : _BmpSearchEx
; Description   : Searches for Bitmap in a Bitmap
; Syntax        : _BmpSearchEx($vPic1, $vPic2, $iMax = 5000)
; Parameters    : $vPic1   - Handle to bitmap (gdi32 or GDI+) to search or path to image file
;               : $vPic2   - Handle to bitmap (gdi32 or GDI+) to find or path to image file
;               : $iMax    - Max matches to find
; Return values : Success: Returns a 2d array with the following format:
;               :          $aCoords[0][0]  = Total matches found (0 if not found)
;               :          $aCoords[0][1]  = Time of search in ms
;               :          $aCoords[$i][0] = Width of bitmap
;               :          $aCoords[$i][1] = Height of bitmap
;               :          $aCoords[$i][2] = X coordinate
;               :          $aCoords[$i][3] = Y coordinate
;               : Failure: Returns 0 and sets @error:
;               :          @error = 1 - file $vPic1 not found
;               :          @error = 2 - file $vPic2 not found
;               :          @error = 3 - $vPic1 is not a bitmap
;               :          @error = 4 - $vPic2 is not a bitmap
;               :          @error = 5 - error decode opcode
; Author        : Brian J Christy (Beege)
; Modified      : InnI
; ===============================================================================================================================
Func _BmpSearchEx($vPic1, $vPic2, $iMax = 5000)
  If $iMax < 1 Then $iMax = 5000
  Local $hImg1, $hImg2, $iErr1, $iErr2, $iTime = TimerInit()
  _GDIPlus_Startup()
  If IsString($vPic1) Then
    If Not FileExists($vPic1) Then Return SetError(1, _GDIPlus_Shutdown(), 0)
    $hImg1 = _GDIPlus_BitmapCreateFromFile($vPic1)
  Else
    $hImg1 = _GDIPlus_BitmapCreateFromHBITMAP($vPic1)
    $iErr1 = @error
  EndIf
  If IsString($vPic2) Then
    If Not FileExists($vPic2) Then Return SetError(2, _GDIPlus_Shutdown(), 0)
    $hImg2 = _GDIPlus_BitmapCreateFromFile($vPic2)
  Else
    $hImg2 = _GDIPlus_BitmapCreateFromHBITMAP($vPic2)
    $iErr2 = @error
  EndIf
  $hSource = ($iErr1) ? _GDIPlus_BitmapCreateHBITMAPFromBitmap($vPic1) : _GDIPlus_BitmapCreateHBITMAPFromBitmap($hImg1)
  If Not $iErr1 Then _GDIPlus_BitmapDispose($hImg1)
  $hFind = ($iErr2) ? _GDIPlus_BitmapCreateHBITMAPFromBitmap($vPic2) : _GDIPlus_BitmapCreateHBITMAPFromBitmap($hImg2)
  If Not $iErr2 Then _GDIPlus_BitmapDispose($hImg2)
  _GDIPlus_Shutdown()
  Static Local $aMemBuff, $tMem, $fStartup = True
  If $fStartup Then
    ;####### (BinaryStrLen = 490) #### (Base64StrLen = 328 )#####################################################################
    Local $Opcode = 'yBAAAFCNRfyJRfSNRfiJRfBYx0X8AAAAAItVDP8yj0X4i10Ii0UYKdiZuQQAAAD38YnBi0X4OQN0CoPDBOL36akAAACDfSgAdB1TA10oO10YD4OVAAAAi1UkORN1A1vrBluDwwTrvVOLVSyLRTADGjtdGHd3iwg5C3UhA1oEi0gEO10Yd2Y5C3USA1oIi0gIO10Yc1c5' & _
        'C3UDW+sGW4PDBOuCi1UUid6LfQyLTRCJ2AHIO0UYczfzp4P5AHcLSoP6AHQNA3Uc6+KDwwTpVP///4tFIIkYg0UgBIPDBP9F/ItVNDlV/HQG6Tj///9bi0X8ycIwAA=='
    Local $aDecode = DllCall("Crypt32.dll", "bool", "CryptStringToBinary", "str", $Opcode, "dword", 0, "dword", 1, "struct*", DllStructCreate("byte[254]"), "dword*", 254, "ptr", 0, "ptr", 0)
    If @error Or (Not $aDecode[0]) Then Return SetError(5, 0, 0)
    $Opcode = BinaryMid(DllStructGetData($aDecode[4], 1), 1, $aDecode[5])
    $aMemBuff = DllCall("kernel32.dll", "ptr", "VirtualAlloc", "ptr", 0, "ulong_ptr", BinaryLen($Opcode), "dword", 4096, "dword", 64)
    $tMem = DllStructCreate('byte[' & BinaryLen($Opcode) & ']', $aMemBuff[0])
    DllStructSetData($tMem, 1, $Opcode)
    ;############################################################################################################################
    $fStartup = False
  EndIf
  Local $tSizeSource = _WinAPI_GetBitmapDimension($hSource)
  If @error Then Return SetError(3, 0, 0)
  Local $tSizeFind = _WinAPI_GetBitmapDimension($hFind)
  If @error Then Return SetError(4, 0, 0)
  Local $iRowInc = ($tSizeSource.X - $tSizeFind.X) * 4
  Local $tSource = DllStructCreate('dword[' & ($tSizeSource.X * $tSizeSource.Y) & ']')
  _WinAPI_GetBitmapBits($hSource, DllStructGetSize($tSource), DllStructGetPtr($tSource))
  Local $tFind = DllStructCreate('dword[' & ($tSizeFind.X * $tSizeFind.Y) & ']')
  _WinAPI_GetBitmapBits($hFind, DllStructGetSize($tFind), DllStructGetPtr($tFind))
  _WinAPI_DeleteObject($hSource)
  _WinAPI_DeleteObject($hFind)
  ;####### (BinaryStrLen = 106) #################################################################################################
  Static Local $Opcode_ = '0xC80000008B5D0C8B1383C3048B4D103913750C83C304E2F7B800000000EB118B5508FF338F028B451029C883C002EB00C9C20C00'
  Static Local $aMemBuff_ = DllCall("kernel32.dll", "ptr", "VirtualAlloc", "ptr", 0, "ulong_ptr", BinaryLen($Opcode_), "dword", 4096, "dword", 64)
  Static Local $tMem_ = DllStructCreate('byte[' & BinaryLen($Opcode_) & ']', $aMemBuff_[0])
  DllStructSetData($tMem_, 1, $Opcode_)
  ;##############################################################################################################################
  Local $iFirstDiffIdx, $iFirstDiffPix, $aFirstDiffCoords[2], $iMaxLoops = (DllStructGetSize($tFind) / 4) - 1
  If $iMaxLoops Then
    Local $aFD = DllCallAddress('dword', DllStructGetPtr($tMem_), 'dword*', 0, 'struct*', $tFind, 'dword', $iMaxLoops)
    $iFirstDiffIdx = $aFD[0]
    $iFirstDiffPix = $aFD[1]
  Else
    $iFirstDiffIdx = 1
    $iFirstDiffPix = DllStructGetData($tFind, 1, 1)
  EndIf
  $aFirstDiffCoords[1] = Int(($iFirstDiffIdx - 1) / $tSizeFind.X)
  $aFirstDiffCoords[0] = ($iFirstDiffIdx - 1) - ($aFirstDiffCoords[1] * $tSizeFind.X)
  Local $iFirst_Diff_Inc = (($aFirstDiffCoords[1] * $tSizeSource.X) + $aFirstDiffCoords[0]) * 4
  If $iFirst_Diff_Inc < 0 Then $iFirst_Diff_Inc = 0
  Local $tCornerPixs = DllStructCreate('dword[3]')
  DllStructSetData($tCornerPixs, 1, DllStructGetData($tFind, 1, $tSizeFind.X), 1)
  DllStructSetData($tCornerPixs, 1, DllStructGetData($tFind, 1, $tSizeFind.X * ($tSizeFind.Y - 1) + 1), 2)
  DllStructSetData($tCornerPixs, 1, DllStructGetData($tFind, 1, $tSizeFind.X * $tSizeFind.Y), 3)
  Local $tCornerInc = DllStructCreate('dword[3]')
  DllStructSetData($tCornerInc, 1, ($tSizeFind.X - 1) * 4, 1)
  DllStructSetData($tCornerInc, 1, (($tSizeSource.X - $tSizeFind.X) + $tSizeSource.X * ($tSizeFind.Y - 2) + 1) * 4, 2)
  DllStructSetData($tCornerInc, 1, ($tSizeFind.X - 1) * 4, 3)
  Local $pStart = DllStructGetPtr($tSource)
  Local $iEndAddress = Int($pStart + DllStructGetSize($tSource))
  Local $tFound = DllStructCreate('dword[' & $iMax & ']')
  Local $ret = DllCallAddress('dword', DllStructGetPtr($tMem), 'struct*', $tSource, 'struct*', $tFind, _
      'dword', $tSizeFind.X, 'dword', $tSizeFind.Y, _
      'dword', $iEndAddress, 'dword', $iRowInc, 'struct*', $tFound, _
      'dword', $iFirstDiffPix, 'dword', $iFirst_Diff_Inc, _
      'struct*', $tCornerInc, 'struct*', $tCornerPixs, _
      'dword', $iMax)
  Local $aCoords[$ret[0] + 1][4] = [[$ret[0], Round(TimerDiff($iTime))]]
  If Not $ret[0] Then Return SetError(0, 0, $aCoords)
  For $i = 1 To $ret[0]
    $iFoundIndex = ((DllStructGetData($tFound, 1, $i) - $pStart) / 4) + 1
    $aCoords[$i][3] = Int(($iFoundIndex - 1) / $tSizeSource.X)
    $aCoords[$i][2] = ($iFoundIndex - 1) - ($aCoords[$i][3] * $tSizeSource.X)
    $aCoords[$i][0] = $tSizeFind.X
    $aCoords[$i][1] = $tSizeFind.Y
  Next
  $aCoords[0][1] = Round(TimerDiff($iTime))
  Return SetError(0, 0, $aCoords)
EndFunc  ;==>_BmpSearchEx

 

Edited January 18, 2022 by InnI
Fixed memory leak

[Beege]

3 hours ago, MaximusCZ said:

Also, its interesting that when I work with example, I select an area on screen and let it find, it reports the output on same coords, but size is -1 in ever direction than given example:

Sorry Im not following the example. The size is off by -1?

 

3 hours ago, MaximusCZ said:

btw, Are you thinking about adding some tolerance in variation? Sometimes (in some programs regulary) you cant find same bitmap twice because of very tiny variance in pixel colors

Yes I would love to add some extra functionality like that. If you or anyone can demonstrate the kinda math we would be talking about with the pixel values, even in straight autoit, that would be helpful. 

[MaximusCZ]

13 minutes ago, Beege said:

Sorry Im not following the example. The size is off by -1

In the screen you can see console output. First line (10,12..) is output of where I place the blue mark. Then it searches, and finds that exact spot, but marks the sie 11,13