C# Scanning an image for a certain block

Question

I have a picture:

size of 1000x1000 white with random black dots. (It may contain a black square (size 50x50))

Is there an easy way to know if the picture contains a black square (size 50x50)? I thought of scanning every pixel of the picture and if a black pixel was found, scan the one next to him till I get a 50x50 square or till I get a white pixel and keep scanning. but it will have to scan over a million pixel (if he hasn't found the square).

Thats the basically the code (no need to complete it, as I said before, it will take way too much time to scan it. million times if the whole picture is white and a lot more according to the number of black pixels.)

        for (int i = 0; i < pic.Width; i++)
        {
            for (int j = 0; j < pic.Height; j++)
            {
                if (pic.GetPixel(i, j) == Color.Black)
                {
                    //Search for the entire square at that area
                }
            }
        }

And yes, time is important (thats why I don't want to get pixel over a million times). Any ideas?

Answer 1

Like the Boyer-Moore string searching algorithm, if the item you are looking at is not part of what you are looking for, you can skip the whole size of the what you are looking for. In your case, you can check to see if a given pixel is black. If it's not, you can skip forward 50 pixels. If it is, you have a small box to look for your black square in.

In this case, though, you may not need anything so complicated. I'm guessing that if your algorithm is too slow it's because you're calling the GetPixel function a million times, and that is the slow part. If you can get your pixels into a 2D array, your algorithm will probably go fast enough to not need to be rewritten.

Assuming that you're using a System.Drawing.Bitmap check out the LockBits documentation to see a small sample that includes copying a bitmap to a 1D array for super-fast access.

Answer 2

If you are only looking for a square of a specific size, then you can optimise this by only scanning every 50th row (or column) of pixels, thereby cutting your workload dramatically.

Theoretically, you only need to check for a black/white in 1 pixel from every 50x50 block. If it's black, then you try spreading from there, if it's white then just skip to the next block: clearly there is a white pixel in this block so there isn't a black box here. Following this, you've already cut your work to 1 / 2500th of what it was originally, you are now only checking 400 pixels initially.

Usually the best optimisations, especially when first designing an algorithm, are around reducing work done rather than doing it more efficiently. Try to think of creative ways to reducing the input to a more manageable size.

Answer 3

check out AForge.net framework suite. It has imaging library with Blob and pattern searching. You can search shapes too. Its free.

You can find it here http://www.aforgenet.com/framework/

Here is the link that lists features

http://www.aforgenet.com/framework/features

Edit

Here is the sample for shape checking. I have used Aforge in a prototype and it worked for me.

http://www.aforgenet.com/articles/shape_checker/