Bitmap Bounding Rectangle Algorithm C++

Question

I currently have my bitmap pixel data stored in an array of chars. I was wondering what would be the most effective algorithm to crop my image based on my image's bounding box.

I've included a relatively accurate example of what I'd like to achieve below. Based on a base "pixel colour".

Bounding Box Example

Answer 1

Brute force is fine, but you can do better using accelerated StretchBlt to calculate the horizontal and vertical projections.

Take the bitmap, draw it onto a 1 pixel high, full width rectangle.

Take the bitmap, draw it onto a 1 pixel wide, full height rectangle.

Both of those will have to process the entire image, but will do so using highly-parallel GPU-accelerated rendering.

Calculate bounds from these.

Ok, you could have errors in the result if the average of the entire column is exactly the background color.

Answer 2

Well, for something so simple with a known input format (i.e., only a circle in the image with high contrast between it and the background) you could brute force it pretty easily. Simply loop through the image data and look for these contrast differences. Save the top-most, left-most, right-most, and bottom-most positions and you're done.

If the image is not in such a simple format then you will need something more advanced, like a blob detection algorithm.

EDIT: Just for reference, I wrote this brute force algorithm to do something very similar some time ago. It is far from perfect and not highly optimized, though it is simple and the method should be clear. I'll just post the entire thing here (don't judge me too harshly; I wrote this years ago when I was teaching myself C#). This algorithm uses an intensity threshold to find the circle (as opposed to contrast, my input was very well defined).

/// <summary>
/// Locates the spot of light on the image and returns an AnalysisResults object.
/// </summary>        
unsafe private Rectangle AnalyzeImage( )
{
    // function assumes 24bpp RGB format
    Bitmap image = m_originalImage;
    if ( image.PixelFormat != PixelFormat.Format24bppRgb )
    {
        throw new ArgumentException( "Image format must be 24bpp RGB" );
    }

    // using the GDI+ GetPixel method is too slow for a 
    // 1280x1024 image, so get directly at the image buffer instead.                    
    GraphicsUnit unit = GraphicsUnit.Pixel;
    imageRect = Rectangle.Truncate( image.GetBounds( ref unit ) );                

    BitmapData data = image.LockBits( imageRect, ImageLockMode.ReadWrite, image.PixelFormat );

    int intensityThreshold = IntensityThreshold;
    // initialize 'top' to -1 so that we can check if it has been set before setting it.
    // once a valid value for 'top' is found we don't need to set it again.
    int top = -1;

    // search for the left point starting at a high value so that we can simply
    // pull it towards the left as we find pixels inside of the spot.
    int left = imageRect.Right;
    int bottom = 0;
    int right = 0;

    // locate the circle in the image by finding pixels with average
    // intesity values above the threshold and then performing
    // some edge checks to set the top, left, right, and bottom values.
    int height = imageRect.Height + imageRect.Y;
    int width = imageRect.Width + imageRect.X;
    byte* pSrc = ( byte* ) data.Scan0;

    int rowOffset = 1;            
    for ( int y = imageRect.Y ; y < height ; ++y, ++rowOffset )
    {
        for ( int x = imageRect.X ; x < width ; ++x )
        {
            // windows stores images in memory in reverse byte order ( BGR )
            byte b = *pSrc++;
            byte g = *pSrc++;
            byte r = *pSrc++;                    

            // get the average intensity and see if it is above the threshold
            int intensity = GetIntensity( r, g, b );
            if ( intensity > intensityThreshold )
            {
                if ( !StrayPixel( pSrc, data, intensityThreshold ) )
                {
                    // found a point in the circle
                    if ( top == -1 ) top = y;
                    if ( x < left ) left = x;
                    if ( y > bottom ) bottom = y;
                    if ( x > right ) right = x;
                }
            }                    
        }

        // next row
        pSrc = ( ( byte* ) data.Scan0 ) + ( rowOffset * data.Stride );
    }

    image.UnlockBits( data );            

    // bounding rectangle of our spot
    return Rectangle.FromLTRB( left, top, right, bottom );
}                   

/// <summary>
/// Returns true if the pixel at (x,y) is surrounded in four 
/// directions by pixels that are below the specified intesity threshold.
/// This method only checks the first pixel above, below, left, and right
/// of the location currently pointed to by 'pSrc'.
/// </summary>        
private unsafe bool StrayPixel( byte* pSrc, BitmapData data, int intensityThreshold )
{
    // this method uses raw pointers instead of GetPixel because
    // the original image is locked and this is the only way to get at the data.

    // if we have a pixel with a relatively high saturation 
    // value we can safely assume that it is a camera artifact.
    if ( Color.FromArgb( pSrc[ 2 ], pSrc[ 1 ], *pSrc ).GetSaturation( ) > MAX_PIXEL_SAT )
    {
        return true;
    }

    byte* pAbove = pSrc - data.Stride;
    int above = GetIntensity( pAbove[ 2 ], pAbove[ 1 ], *pAbove );

    byte* pRight = pSrc + 3;
    int right = GetIntensity( pRight[ 2 ], pRight[ 1 ], *pRight );

    byte* pBelow = pSrc + data.Stride;
    int below = GetIntensity( pBelow[ 2 ], pBelow[ 1 ], *pBelow );

    byte* pLeft = pSrc - 3;
    int left = GetIntensity( pLeft[ 2 ], pLeft[ 1 ], *pLeft );

    // if all of the surrounding pixels are below the threshold we have found a stray
    return above < intensityThreshold &&
           right < intensityThreshold &&
           below < intensityThreshold &&
           left  < intensityThreshold;
}

/// <summary>
/// Returns the average of ( r, g, b )
/// </summary>  
private int GetIntensity( byte r, byte g, byte b )
{
    return GetIntensity( Color.FromArgb( r, g, b ) );
}

/// <summary>
/// Returns the average of ( c.r, c.g, c.b )
/// </summary>
private int GetIntensity( Color c )
{
    return ( c.R + c.G + c.B ) / 3;
}

Answer 3

Nice game for the evening! Thank you! Quickly wrote some C# Code to do this brute force:

public class Dimensions
{
    public int left = 0;
    public int right = 0;
    public int top = 0;
    public int bottom = 0;
}

public class ImageDetection
{
    private const int xSize = 2000;
    private const int ySize = 2000;

    private const int xMin = 1800;
    private const int yMin = 1800;
    private const int defaultPixelColor = 0;


    public void GetArray(out char[,] arr)
    {
        arr = new char[xSize, ySize];
        Random rand = new Random();

        for (int i=0; i<xSize; ++i)
        {
            for (int j=0; j<ySize; ++j)
            {
                var d = rand.NextDouble();

                if (d < 0.5)
                {
                    arr[i, j] = Convert.ToChar(defaultPixelColor);
                }
                else
                {
                    int theInt = Convert.ToInt32(255 * d);
                    arr[i, j] = Convert.ToChar(theInt);
                }
            }
        }

        // cut top
        for (int k = 0; k < (xSize - xMin); k++)
        {
            for (int l = 0; l < ySize; l++)
            {
                arr[k, l] = Convert.ToChar(defaultPixelColor);
            }
        }

        // cut bottom
        for (int k = xMin; k < xSize; k++)
        {
            for (int l = 0; l < ySize; l++)
            {
                arr[k, l] = Convert.ToChar(defaultPixelColor);
            }
        }

        // cut left
        for (int k = 0; k < xSize; k++)
        {
            for (int l = 0; l < (ySize - xMin); l++)
            {
                arr[k, l] = Convert.ToChar(defaultPixelColor);
            }
        }

        // cut right 
        for (int k = 0; k < xSize; k++)
        {
            for (int l = xMin; l < ySize; l++)
            {
                arr[k, l] = Convert.ToChar(defaultPixelColor);
            }
        }

    }

    public void WriteArr(ref char[,] arr)
    {
        char[] line = new char[xSize];

        // all lines
        for (int i=0; i<ySize; ++i)
        {
            // build one line
            for (int j = 0; j < xSize; ++j)
            {
                char curChar = arr[i, j];

                if (curChar == '\0')
                {
                    line[j] = '.';
                }
                else
                {
                    line[j] = curChar;
                }
            }

            string s = new string(line);
            s += "\r\n";
            //FileIO.WriteFileText
            System.IO.File.AppendAllText("Matrix.txt", s);
         }
    }

    public void DetectSize(ref char[,] arr, out Dimensions dim)
    {
        dim = new Dimensions();

        dim.left = xSize;
        dim.top = ySize;
        dim.right = 0;
        dim.bottom = 0;

        for (int i = 0; i < xSize; ++i)
        {
            for (int j = 0; j < ySize; ++j)
            {
                if (!arr[i, j].Equals(Convert.ToChar(defaultPixelColor)))
                {
                    if (i < dim.left)
                    {
                        dim.left = i;
                    }

                    if (j < dim.top)
                    {
                        dim.top = j;
                    }

                    if (i > dim.right)
                    {
                        dim.right = i;
                    }

                    if (j > dim.bottom)
                    {
                        dim.bottom = j;
                    }
                }
            }
        }
    }
}