?
Solved

How to find a picture within a picture

Posted on 2009-04-21
7
Medium Priority
?
649 Views
Last Modified: 2012-05-06
The problem to solve is as follow:

I need to:
-  take a snapshot of area (rectangle) currently on screen and put it to a variable (VarA)
-  load another picture from a file into a variable (VarB)
- find out, if the VarB is a part of VarA, and at which position (x,y)

An example:
I have a picture that contains many photos (PicA). I cut out a photo and save it as PicB.
Now I need to find out if and where PicB is in PicA.

This should be done directly in Visual Basic 6 or at least in a bindable DLL.

Any idea how I can do this?

Thanks
0
Comment
Question by:Gryzn
  • 4
  • 3
7 Comments
 
LVL 18

Expert Comment

by:mdougan
ID: 24203959
There might be more efficient ways to do this, but if I were to approach it, I wouldn't put the pictures into variables, but rather into pictureboxes.  Then, I would use the pictureboxes GetPixel method to get the color of the pixel in the upper left corner of PicB, then, I would start getting pixels from the upper left corner of PicA moving from left to right, then down to the next row of pixels, left to right until I found a pixel of the same color.  Then, I would see if the second pixel of PicB matched the second pixel to the right of the one found in PicA, if not, then continue searching for the first pixel color again in PicA.

It would help if you set the ScaleMode of the pictureboxes to Pixel before you loaded the pictures into them, and also set the auto-redraw property to true.

So, the algorithm would look something like:

Dim x as long
Dim y as long
Dim m as long
Dim p as long

' Search every line of pixels in PicA
For y = 0 to (PicA.ScaleHeight - PicB.ScaleHeight)
   ' Search every column of pixels in PicA
   For x = 0 to (PicA.ScaleWidth - PicB.ScaleWidth)
      ' Search every row of pixels in PicB
      For m = 0 to PicB.ScaleHeight
         ' Search every column of pixels in PicB
         For p = 0 to PicB.ScaleWidth
               ' if any one pixel doesn't match, then you haven't found PicB in PicA
               ' so, move on to the next pixel in PicA
               IF PicA.GetPixel(x + p, y + m) <> PicB.GetPixel(p, m) Then
                   GoTo Continue
               ELSE IF ((m = PicB.ScaleHeight) AND (p = PicB.ScaleWidth)) Then
                     ' if you have compared every pixel in PicB with PicA and they have all matched
                     ' then X and Y are the coordinates of where the upper left corner of PicB appears in PicA
                    GoTo Succeeded
               End If
          Next p
      Next m
Continue:
   Next x
Next y

' If it falls through here, you didn't find the picture
Failed:
msgbox "Failed to find picture"
exit sub

' if you goto here, you were successful
Succeeded:
msgbox "PicB was found at coordinates X:" & CStr(x) & " Y:" & Cstr(y)
exit sub

Some caveats... wherever I mention ScaleHeight and ScaleWidth, you might need to use ScaleHeight - 1 and ScaleWidth - 1, I can't remember how the indexing works.  You'll know if you do this:

Dim c as long
c = PicB.GetPixel(PicB.ScaleWidth, PicB.ScaleHeight)

If you do that and get an Index out of bounds... then you need to use ScaleWidth - 1 and ScaleHeight - 1

Also, you note that I'm only searching PicA from 0 to PicA.ScaleHeight - PicB.ScaleHeight (same for width), that is because if PicB is 100 pixels tall, and I'm less than 100 pixels from the bottom of PicA, I'm not going to find the image, because PicB won't fit in the space below.

Again, you might need to double-check what the limit should be... it could be any of these:

For Y = 0 to (PicA.ScaleHeight - PicB.ScaleHeight)
For Y = 0 to ((PicA.ScaleHeight - PicB.ScaleHeight) - 1)
For Y = 0 to ((PicA.ScaleHeight - 1) - (PicB.ScaleHeight - 1)
0
 

Author Comment

by:Gryzn
ID: 24204944
Thank you for your appraoch.

The reason because I was thinking about variables are two things:

Frist, the PicA is not a file, it's has to be taken as a snapshot of the current screen (i.e. flash in a webbrowser control).
Second, I assume it is faster to compare such huge data on a byte level rather than using the  GetPixel function (but I could be wrong).

I will check out the performance of your solution and report.
0
 
LVL 18

Accepted Solution

by:
mdougan earned 2000 total points
ID: 24204976
I tried this out and got it to work with a few modifications.  Sure enough, in at least one place I had to search PicB.ScaleHeight - 1 and PicB.ScaleWidth - 1.

I thought GetPixel was a method belonging to the Picturebox, but, I found I had to declare the Windows API GetPixel instead.

To test this code, create a VB6 project, put a large picturebox on the form and name it PicA, set the ScaleMode to 3 (Pixel), Autosize = True, AutoRedraw = True, then load a picture into it.

Create a smaller picturebox, call it PicB, set the same 3 properties, don't load a picture into it.

Optionally create a third picturebox, exactly the same size as PicB and set the same 3 properties, call it PicC -- this is if you would like to see the part of PicA that is being compared to PicB, but if you uncomment that code, it really slows the process down.

Optionally, put a label on the form and name it lblCoord, this will display the current X,Y coordinate that is being used in the compare.

Put a command button on the form and call it cmdFind.

Paste the code below into the code behind the form.

You'll notice that at the top of the routine, I am calling an API called BitBlt.  This copies a section of PicA into the PicB picturebox.  I'm doing this to ensure that we have an exact copy of part of the image in PicA in PicB.  I tried cropping a picture in PhotoShop and loading separate pictures into the two pictureboxes, but apparantly, PhotoShop must have altered at least one pixel when saving the crop.

You'll also notice that once I've compared about half the picture, if all the pixels have matched up to that point, I consider it a match... you can play with that and make it more or less exact.

Make sure that the X Y coordinate in the BitBlt at the top of the routine is an actual coordinate somewhere in the middle of your PicA (in other words, if your PicA is only 200 pixels wide, maybe pick a smaller number like 50)

If it runs successfully, the X Y coordinate where it finds PicB in PicA should match the coordinates you hard-coded in the first BitBlt at the top of the routine.
Option Explicit
Private Declare Function BitBlt Lib "gdi32" (ByVal hDestDC As Long, ByVal X As Long, ByVal Y As Long, ByVal nWidth As Long, ByVal nHeight As Long, ByVal hSrcDC As Long, ByVal xSrc As Long, ByVal ySrc As Long, ByVal dwRop As Long) As Long
Private Declare Function GetPixel Lib "gdi32" (ByVal hdc As Long, ByVal X As Long, ByVal Y As Long) As Long
 
Private Const SRCCOPY = &HCC0020 ' (DWORD) dest = source
 
Private Sub cmdFind_Click()
Dim X As Long
Dim Y As Long
Dim m As Long
Dim p As Long
      
' To test the code, we ensure that PicB has an exact copy of a part of PicA
BitBlt PicB.hdc, 0, 0, PicB.ScaleWidth, PicB.ScaleHeight, PicA.hdc, 366, 181, SRCCOPY
PicB.Refresh
 
' Search every line of pixels in PicA
For Y = 0 To (PicA.ScaleHeight - PicB.ScaleHeight)
   ' Search every column of pixels in PicA
   For X = 0 To (PicA.ScaleWidth - PicB.ScaleWidth)
      ' Search every row of pixels in PicB
      lblCoord.Caption = "X:" & CStr(X) & " Y:" & CStr(Y)
      lblCoord.Refresh
 
' If you want to see what is currently being compared to PicB
'        BitBlt PicC.hdc, 0, 0, PicC.ScaleWidth, PicC.ScaleHeight, PicA.hdc, X, Y, SRCCOPY
'        PicC.Refresh
'        Me.Refresh
      
      For m = 0 To PicB.ScaleHeight - 1
         ' Search every column of pixels in PicB
         For p = 0 To PicB.ScaleWidth - 1
               ' if any one pixel doesn't match, then you haven't found PicB in PicA
               ' so, move on to the next pixel in PicA
               If GetPixel(PicA.hdc, X + p, Y + m) <> GetPixel(PicB.hdc, p, m) Then
                   GoTo Continue
               ElseIf ((m > (PicB.ScaleHeight / 2)) And (p > (PicB.ScaleWidth / 2))) Then
                     ' if you have compared half the pixels in PicB with PicA and they have all matched
                     ' then X and Y are the coordinates of where the upper left corner of PicB appears in PicA
                    GoTo Succeeded
               End If
          Next p
      Next m
Continue:
   Next X
Next Y
 
' If it falls through here, you didn't find the picture
Failed:
MsgBox "Failed to find picture"
Exit Sub
 
' if you goto here, you were successful
Succeeded:
MsgBox "PicB was found at coordinates X:" & CStr(X) & " Y:" & CStr(Y)
Exit Sub
End Sub

Open in new window

0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 18

Expert Comment

by:mdougan
ID: 24205249
If PicA is a snapshot of a window, that can be copied to the PicA picturebox, either with PaintPicture or BitBlt.  To capture a window, all you need is to get the handle to the windows Device Context.  You can do this by first getting a handle to the window using the FindWindow API, then taking the resulting window handle and calling the API  GetDC (passing the window handle).  Then, you can BitBlt that into PicA the way I've done in the code to PicB or PicC.  If you are capturing the desktop window, that window handle is zero, so, you can just call GetDC passing 0&.

It probably would be more efficient to compare at a byte level, but you would need a different algorithm.

This algorithm works because it treats the two pictures as two dimensional arrays, where PicB is a subset of the dimensions in PicA.  If you were to string all the data for both PicA and PIcB out in a one dimensional byte array, then you'd have trouble because you would have to skip parts of the PicA array in the comparison.

For example, let's say that PicA is 100 pixels wide and 100 pixels tall, and PicB is 10 pixels wide and 10 pixels tall, and that PicB is found in PicA at coordinates 15, 15

For the sake of ease, let's just assume that each pixel can be represented by a byte (I don' think it is, but bear with me).

PicB's elements of 0-9 would appear in PicA's elements starting at around 1514-1524, then picB's elements of 10-19 would appear in PicA's  elements at around 1614-1624, so, your algorithm would have to know how many elements of PicA to ignore in the compare to account for the difference in picture widths.

In any event, there are probably much better pattern matching algorithms out there... I just gave you one simple approach :-)
0
 

Author Comment

by:Gryzn
ID: 24209190
First, let me thank you for your effort.

I tried it out, and although it works, it is definitly too slow.

I have to find a picture of 10 x 100 in a picture of 600 x 1000 whithin a second. Loop thru the y,x array seems too slow, therefore I was thinking about the string representation (or whatever else fits) at first. With a string, I could search for the first pixel row of PicB (1 x 100) as a pattern. This will bring me quicky to the first position that makes sense  to investigate further or tells me immediately that it is not in the picture at all.
0
 
LVL 18

Expert Comment

by:mdougan
ID: 24210092
That sounds like an interesting approach, as long as the first pixel row doesn't contain all the same value (white, black etc)  :-)

I'd be interested to hear about whatever you come up with, but if you'd prefer, you are welcome to delete this question and ask that your points be refunded.

Cheers!
Mike
0
 

Author Comment

by:Gryzn
ID: 24210912
Yes, you are right. It requires some optimation :)

We do not have to use the first row. We can first check for the row with the most significant variations and use this for the pattern search. If we use a second string, that represents the picture verticaly, we can do this even for a column of pixels. Finally, this will give us some kind of a crosshair to find the right point with a high probability. I think that split() or InStr() will be fast enough for that.

But building such a string representation by using GetPixel is too slow. The remaining question is: How to convert a picture into a string as fast as possible?

However, there is no reason to delete the question, because the "need for speed" was not part of the original request :D
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction While answering a recent question (http://www.experts-exchange.com/Q_27402310.html) in the VB classic zone, I wrote some VB code in the (Office) VBA environment, rather than fire up my older PC.  I didn't post completely correct code o…
Article by: Martin
Here are a few simple, working, games that you can use as-is or as the basis for your own games. Tic-Tac-Toe This is one of the simplest of all games.   The game allows for a choice of who goes first and keeps track of the number of wins for…
As developers, we are not limited to the functions provided by the VBA language. In addition, we can call the functions that are part of the Windows operating system. These functions are part of the Windows API (Application Programming Interface). U…
Get people started with the process of using Access VBA to control Excel using automation, Microsoft Access can control other applications. An example is the ability to programmatically talk to Excel. Using automation, an Access application can laun…
Suggested Courses

612 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question