c# Low performance in for-loop while searching pixels in image

Question

When I use the following code, it takes around 3-5 seconds before the loop is done if the image I am searching for in the image is not found. While this is searching the rest of the program is paused, my timers gets out of sync and it looks like the program freezes for a few seconds. The images are not very big, "printscreen" is around 344x354 and "Ok" is around 15x7. I know it is because of the for-loops, but is there a better way to do this or can I runt his part of the program besides the rest of the program in some way, so the program won't freeze for a few seconds.

// Ok is the image I am searching for.
// printscreen is the image I am searching in.

Bitmap Ok = new Bitmap(Properties.Resources.popupok1);
int Count = 0;
for (int x = 0; x < printscreen.Width; x++)
{
    for (int y = 0; y < printscreen.Height; y++)
    {
        Count = 0;
        if (printscreen.GetPixel(x, y) == Ok.GetPixel(0, 0) && 
            printscreen.GetPixel(x + 1, y) == Ok.GetPixel(1, 0))
        {
            for (int OkX = 0; OkX <= Ok.Width; OkX++)
            {
                for (int OkY = 0; OkY <= Ok.Height; OkY++)
                {
                    try
                    {
                        if (printscreen.GetPixel(x + OkX, y + OkY) != Ok.GetPixel(OkX, OkY))
                        {
                            OkX = Ok.Width;
                            OkY = Ok.Height;
                        }
                        else
                        {
                            Count += 1;
                        }
                        if (Count == 105)
                        {
                            X = x;
                            Y = y;
                            OkX = Ok.Width;
                            OkY = Ok.Height;
                            x = printscreen.Width - 1;
                            y = printscreen.Height - 1;
                            Console.Add("Ok button found.");
                            Console.Add("");
                            ConsoleUpdate();
                        }
                    }
                    catch { }
                }
            }
        }
    }
}

Answer 1

I have put some beginners' tutorials on http://www.tmorley.net. These explain image processing using C#. The first thing that is done is that the image file (jpg, bmp, etc) immediately has the pixel data extracted into an array. Processing can be done on this quickly and then the results are put back into a Bitmap for display or saving to disc.

Answer 2

The performance issue is caused by GetPixels/SetPixels, which is an extraordinarily slow way to access the data in an .NET Bitmap. Instead, I would look into the Bitmap.LockBits method to get a pointer to the bitmap and manipulate data directly. It will be an order of magnitude faster.

See MSDN:

The following code example demonstrates how to use the PixelFormat, Height, Width, and Scan0 properties; the LockBits and UnlockBits methods; and the ImageLockMode enumeration. This example is designed to be used with Windows Forms. To run this example, paste it into a form and handle the form's Paint event by calling the LockUnlockBitsExample method, passing e as PaintEventArgs.

private void LockUnlockBitsExample(PaintEventArgs e)
{

    // Create a new bitmap.
    Bitmap bmp = new Bitmap("c:\\fakePhoto.jpg");

    // Lock the bitmap's bits.  
    Rectangle rect = new Rectangle(0, 0, bmp.Width, bmp.Height);
    System.Drawing.Imaging.BitmapData bmpData = 
        bmp.LockBits(rect, System.Drawing.Imaging.ImageLockMode.ReadWrite,
        bmp.PixelFormat);

    // Get the address of the first line.
           IntPtr ptr = bmpData.Scan0;

    // Declare an array to hold the bytes of the bitmap.
    // This code is specific to a bitmap with 24 bits per pixels.
    int bytes = bmp.Width * bmp.Height * 3;
    byte[] rgbValues = new byte[bytes];

    // Copy the RGB values into the array.
    System.Runtime.InteropServices.Marshal.Copy(ptr, rgbValues, 0, bytes);

    // Set every red value to 255.  
    for (int counter = 2; counter < rgbValues.Length; counter+=3)
        rgbValues[counter] = 255;

    // Copy the RGB values back to the bitmap
    System.Runtime.InteropServices.Marshal.Copy(rgbValues, 0, ptr, bytes);

    // Unlock the bits.
    bmp.UnlockBits(bmpData);

    // Draw the modified image.
    e.Graphics.DrawImage(bmp, 0, 150);

}

If you want to go even faster rather than copy the array out, manipulate it and copy it back, you can operate on the bitmap in place using an unsafe pointer. In this case, the inner part would change as follows:

    // Lock the bitmap's bits.  
    Rectangle rect = new Rectangle(0, 0, bmp.Width, bmp.Height);
    System.Drawing.Imaging.BitmapData bmpData = 
        bmp.LockBits(rect, System.Drawing.Imaging.ImageLockMode.ReadWrite,
        bmp.PixelFormat);

    // Get the address of the first line.
    IntPtr ptr = bmpData.Scan0;

    // Declare an array to hold the bytes of the bitmap.
    // This code is specific to a bitmap with 24 bits per pixels.
    int bytes = bmp.Width * bmp.Height * 3;
    unsafe
    {
        byte* rgbValues = (byte*)ptr;

        // Set every red value to 255.  
        for (int counter = 2; counter < bytes counter+=3)
            rgbValues[counter] = 255;
    } 

    // Unlock the bits.
    bmp.UnlockBits(bmpData);

Just take care to note the PixelFormat of the bitmap. The example above assumes its 24 bits per pixel BGR. In actual fact many bitmaps are BGRA (32bits per pixel) so you will need to modify four bytes for Blue, Gree, Red, Alpha in that order per pixel.

Answer 3

I don't know anything about image processing and your problem seems general enough that someone probably must have developed a specific algorithm. However, in case not, here is my two cents: It is not surprising that your algorithm runs slowly, if two images are of size W1xH1 and W2xH2 your run time is O(W1.H1.W2.H2) at the worst case. The average case is much less but still not fast enough.

Searching a substring inside a string is the one dimensional analogue of your task and it is well researched problem. You may want to check Boyer-Moore string searching algorithm and see if you can adapt the basic idea to your problem.

Answer 4

This looks like hungry algorytm. Think about it once more and define points, where you can safely leave the function. e.g. add return after

Console.Add("Ok button found.");
Console.Add("");
ConsoleUpdate();
return;

I believe you can find more points where you can leave, because you can be sure, there is nothing more to find, or why you're finishing your cycles even you already found what you are looking for?

Or maybe you can set it up in a different way. You can start with scanning the picture for the first pixel, and after you find it, you can check second one, third, etc and if e.g. third pixel is not correct you'll need to return back and continue.

So if not even one pixel will be correct, then you'll go through the picture only once.

In other words, do not try to compare two x*y areas, try to compare pixels first, areas later. you should be able to reduce the time significantly.

Answer 5

use new new thread for proccesing image and your program will not freeze while proccesing Threading