Image position in other image c# ? [modified]

[sodevrom]

Hello, I searched all over the internet but didn't find a very good answer on this. I know this is a very helpful forum so maybe I will get lucky. The question is pretty simple : How can I get the position (x,y) of a small image in a large image ? The ideea is that the large image contains the small image, but I want to find out where exactly it is. I know it can be done by converting the images to bmp and after that going to each pixel at a time and checking if it exists. Is there another way ? Can someone help ? Thanks PS: The big image is black and white (not monochrome, but only black and white) and the small image is also only black and white.

modified on Saturday, September 19, 2009 6:59 PM

[Dave Kreskowiak]

sodevrom wrote:

Is there another way ?

The simplest method to start with is pretty simple. You pretty much get the pixel from the top left corner of the small image, then start scanning the big image, row-by-row, pixel-by-pixel, looking for a pixel of that color. When you find it, then you start getting each pixel in the small image for the rest of the top row and comparing those to the next pixels in the big image. If they match, you go to the next rows and start comparing those pixels, until your done. If not, go back and keep scanning for the top left corn pixel.

A guide to posting questions on CodeProject[^]
Dave Kreskowiak Microsoft MVP Visual Developer - Visual Basic
     2006, 2007, 2008
But no longer in 2009...

[sodevrom]

Hello, I thought that maybe there is a faster way to do this. Something like convert the image (this is a stupid idea, but something siliar :) ) to a string and use seomthing like image.indexof ... Maybe something to do with bytes . Any ideas are well appreciated

[Dave Kreskowiak]

Which, when you write that method, would do the exact same thing. Search the Articles for Christian Graus' Image Processing articles for examples on scanning an image quickly.

A guide to posting questions on CodeProject[^]
Dave Kreskowiak Microsoft MVP Visual Developer - Visual Basic
     2006, 2007, 2008
But no longer in 2009...

[Alan Balkany]

Actually you're on the right track. Looking at the images as long strings allows you to do Boyer-Moore String Searching (http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm[^]). This can be tens to hundreds of times faster than pixel-by-pixel comparisons. The basic idea is this: Say the small image is length n. You build a dictionary of all the pixel values that occur in the small image. If you look at pixel (n-1) in the larger image, and this pixel is NOT in your dictionary, you can conclude that the smaller image cannot occur at any point in the larger image from position 0 to (n-1). If n is 1000, you can step through the larger image 1000 times as fast as searching pixel-by-pixel. One approach is to construct pixel dictionaries for both the small and large image, then find a sequence of pixels in the smaller image that are rare in the larger image. Then search for this sequence in the larger image. Since this sequence has rare pixels, you'll be able to do more Boyer-Moor "jumps", speeding up your processing. You may want to only look for one row of the smaller image to avoid having to skip pixels to reach the row underneath this in the larger image.

[Albond]

Here's my method. Maybe someone need. Works quickly.

Point IndexOfImage(Bitmap bmp1, Bitmap bmp2)
{
Point retP = new Point(-1, -1);

        int bw = bmp1.Width;
        int bh = bmp1.Height;
        int bw2 = bmp2.Width;
        int bh2 = bmp2.Height;
        if ((bw < bw2) || (bh < bh2)) return retP;


        //------------------------------------

        Bitmap bmp = new Bitmap(bw2, bh2);

        Rectangle rect = new Rectangle(0, 0, bmp1.Width, bmp1.Height);
        System.Drawing.Imaging.BitmapData bmpData = bmp1.LockBits(rect, System.Drawing.Imaging.ImageLockMode.ReadOnly, PixelFormat.Format24bppRgb);

        IntPtr ptr = bmpData.Scan0;

        int bytes = bmpData.Stride \* bmp1.Height;

        byte\[\] rgbValues = new byte\[bytes\];

        System.Runtime.InteropServices.Marshal.Copy(ptr, rgbValues, 0, bytes);

        //------------------------------------

        Rectangle rect2 = new Rectangle(0, 0, bmp2.Width, bmp2.Height);
        System.Drawing.Imaging.BitmapData bmpData2 = bmp2.LockBits(rect2, System.Drawing.Imaging.ImageLockMode.ReadOnly, PixelFormat.Format24bppRgb);

        IntPtr ptr2 = bmpData2.Scan0;

        int bytes2 = bmpData2.Stride \* bmp2.Height;

        int bm = bytes2;
        byte\[\] rgbValues2 = new byte\[bytes2\];

        System.Runtime.InteropServices.Marshal.Copy(ptr2, rgbValues2, 0, bytes2);

        //------------------------------------

        int i = -1, j = 0, i2 = -1, j2 = 0, ind\_f = 0;
        int f = 0;
        int realx, realx2;
        i = -1;
        j = 0;

        for (int y = 0; y < bh - bh2 + 1; y++)
        {
            j = 0;
            realx = 0;
            for (int x = 0; x < bw \* 3 - bw2 \* 3; x++)
            {
                i++;
                j++;
                if (j == 4)
                {
                    j = 1;
                    realx++;
                }
                if (j == 1)
                {
                    bm = 0;
                    i2 = -1;
                    j2 = 0;
                    int y2 = 0;
                    realx2 = 0;
                    f = 0;
                    while (y2 < bh2)
                    {
                        i2++;
                        j2++;
                        if (j2