How to find a picture within a picture

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)

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.

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 :-)

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.

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

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