by Libor Tinka, 3/17/2013

Digital images are usually rectangles, but such rectangular boxes may contain "actual" image with arbitrary boundary. This article discusses a generic algorithm for finding largest rectangle that can still fit within the boundaries. Examples of such non-rectangular images are digital panoramas, projected images, scans and old photographs.

The shape of such images can be described by a mask (some image formats support such extra layer as an alpha mask). We will work with a simple binary mask, where white color represents "image" and black color represents "background". Such mask can be computed by thresholding the original image:

photo by Dominik Herman

Now the problem can be stated as follows:

Find the largest rectangle containing only white pixels.

We will call this rectangle the largest inscribed rectangle.

Largest Inscribed Square

Let's first take a look on squares. Squares are simpler as they possess just a single property: size.

A possible straightforward algorithm for finding largest inscribed square is to iterate over mask pixels and for every white pixel, increase square sizes from 1 until black pixel is encountered. This algorithm will work, but is very slow. Consider a white mask of size N by N pixels. Such mask will require to check N3 squares leading to a cubic time complexity in image size. Most checks are unnecessary since for each large square checked, all its sub-squares are checked as well. These obviously cannot be larger than the original square.

The problem actually consists of smaller sub-problems and can be solved conveniently by first finding smaller squares and then combining them into larger ones, re-using already known. This approach is commonly known as dynamic programming.

Instead of scanning the image from top-left to bottom-right corner, we will scan it from bottom-right to the top-left corner. The first pixel scanned will be the bottom right corner of the image. If the pixel is white, we know for sure that the largest square having top left corner at this position is 1 pixel large:

The square-searching algorithm is filling a two-dimensional array called squares which contains largest inscribed square size for any given location. The array is of the same size as the image since its entries correspond to image pixels. The array is progressively filled with positive integers as the algorithm scans through the image.

Notice that squares[x,y] is 1 for any white pixel at the position (x, y) that have black pixel (0) as neighbor at position (x+1, y), (x, y+1) or (x+1, y+1):

What about other white pixels? We can actually compute size of the largest square at given position when we know square sizes at the three neighboring positions mentioned:

The 1×1 square at position on which the three arrows point can stretch two pixels to the right, two pixels to the bottom and just one pixel diagonally. Since width and height of the square must be equal, the largest square size is restricted by the smallest neighbor:

squares[x,y] = min(squares[x+1,y], squares[x,y+1], squares[x+1,y+1]) + 1

Of course, this formula applies only when we are scanning the image in a bottom-up, right-left fashion, which ensures all three neighbors are always known.

The formula cannot be applied on the very boundary of the image where neighbors are not defined. The right and bottom edges of the image must be treated separately by simply going through the boundary pixels and setting square[x,y] to 1 on white pixel. Another approach is to ensure there are no white pixels on the boundary.

Consider the mask:

Computing squares for this mask results in the following map on the left (lighter color means larger square). The position with maximum value reveals top left corner of the largest inscribed square and the value itself represents its size. From this we can obtain the square:

Here is a sample code for finding the largest inscribed square for any position in the given binary mask:

int[,] squares = new int[height, width];

int row;
int col;

// process bottom boundary of the mask
row = (height - 1);

for (col = 0; col < width; col++)
{
    if (mask[row, col])
    {
        squares[row, col] = 1;
    }
}

// process right boundary of the mask
col = (width - 1);

for (row = 0; row < height; row++)
{
    if (mask[row, col])
    {
        squares[row, col] = 1;
    }
}

// process internal pixels of the mask
for (
    row = (height - 2);
    row >= 0;
    row--)
{
    for (
        col = (width - 2);
        col >= 0;
        col--)
    {
        if (mask[row, col])
        {
            int a = squares[row, col + 1];
            int b = squares[row + 1, col];
            int c = squares[row + 1, col + 1];

            squares[row, col] = (Math.Min(Math.Min(a, b), c) + 1);
        }
    }
}

Largest Inscribed Rectangle

Now we are ready to extend our knowledge to searching rectangles.

Rectangles are a bit trickier because we cannot always tell which one is larger than another. Let's define a simple GetSize function that returns rectangle size for a given dimensions:

int GetSize(int width, int height)
{
    return (width * height);
}

Of course this function will return the same value for some pairs of rectangles (e.g. 3×2 and 2×3).

One may wish to emphasize rectangles approaching a given aspect ratio. The following implementation of GetSize will emphasize rectangles with aspect ratio of 16:9:

int GetSize(int width, int height)
{
    return (16 * width + 9 * height);
}

Width and height properties are independent and so have to be treated as two separate dimensions. Look at the following picture - the largest inscribed square for a point marked by circle is marked by blue color:

Two inscribed rectangles at the same point are marked by grey color. The inscribed rectangle can have greater area than the inscribed square at the same point although its width or height is smaller.

However, knowing the largest inscribed square here is useful since no rectangle can have both width and height greater than this square.

The largest inscribed square hence allows us to divide inspected rectangles into two classes:

  • width greater than square's size (and height possibly smaller)
  • height greater than square's size (and width possibly smaller)

Instead of keeping just one array (squares), we will add three new arrays:

widths - widths of the largest inscribed rectangles
heights - heights of the largest inscribed rectangles
sizes - sizes of the largest inscribed rectangles according to GetSize

The search algorithm consists of three stages:

  • Compute squares array containing largest inscribed square size for each pixel (using the algorithm described in the previous section).
  • Scan rows of the mask; for each row, scan columns from right to left. Update widths, heights and sizes arrays with the largest inscribed rectangle with width >= height for each pixel.
  • Scan columns of the mask; for each column scan rows from bottom to top. Update widths, heights and sizes arrays with the largest inscribed rectangle with width < height for each pixel.

Let's analyze the second stage in more detail.

When scanning a new row, we will initialize a vector (1D array) called height2width with length equal to maximum square size found in the mask. The array is filled with zeros and will help us mapping queried rectangle height to maximum width found so far.

Consider a simple shape displayed in the table below. We will go through scanning its first row - the numbers are sizes of largest inscribed squares found on each position (these are pre-computed in the first stage of the algorithm). The circle marks currently inspected pixel and the shaded area represents currently considered rectangle:

The largest square is 1×1. Set height2width[1] to 1 since this is the largest rectangle width found so far for height = 1.
The largest square is 1×1. We can consider only rectangles of height 1. height2width[1] is 1, so we can increment it to 2 and consider rectangle of size 2×1.
The largest square is 2×2. We can consider rectangles of height 2 and 1.
Considering rectangles of height 2.
height2width[2] is 0, set it to 2 because 2 is the largest width found so far for height 2.
Considering rectangles of height 1.
height2width[1] is 2 so we can increment it to 3 and consider rectangle of size 3×1.
The largest square is 1×1.
height2width[1] is 3 so we can increment it to 4 and consider rectangle of size 4×1.
Set all entries of height2width with index 2 and larger to zero because these will not be available for other columns.

Each step is basically updating height2width this way for each rectangle height:

height2width[height] = max(square size, height2width[height] + 1)

After all heights are searched, all entries with indices above square size are set to zero as such widths will not be reachable from columns to the left.

The following code searches the largest inscribed rectangle given the binary mask and the squares array computed in the previous sample:

int[,] sizes = new int[height, width];
int square;
int maxSquare = 0;

for (row = 0; row < height; row++)
{
    for (col = 0; col < width; col++)
    {
        square = squares[row, col];

        sizes[row, col] = GetSize(square, square);

        if (square > maxSquare)
        {
            maxSquare = square;
        }
    }
}

// find largest rectangles with width >= height
int[] height2width = new int[maxSquare + 1];

int[,] widths = new int[height, width];
int[,] heights = new int[height, width];

int maxSize;
int rectWidth;
int rectHeight;
int size;

for (
    row = 0;
    row < height;
    row++)
{
    for (int s = 0; s <= maxSquare; s++)
    {
        height2width[s] = 0;
    }

    for (
        col = (width - 1);
        col >= 0;
        col--)
    {
        square = squares[row, col];

        if (square > 0)
        {
            maxSize = sizes[row, col];

            for (rectHeight = square; rectHeight > 0; rectHeight--)
            {
                rectWidth = height2width[rectHeight];

                rectWidth = Math.Max(
                    rectWidth + 1,
                    square);

                height2width[rectHeight] = rectWidth;

                size = GetSize(rectWidth, rectHeight);

                if (size >= maxSize)
                {
                    maxSize = size;
                    widths[row, col] = rectWidth;
                    heights[row, col] = rectHeight;
                }
            }

            sizes[row, col] = maxSize;
        }

        for (
            int s = (square + 1);
            s <= maxSquare;
            s++)
        {
            // widths larger that 'square' will not be available
            height2width[s] = 0;
        }
    }
}

// find largest rectangles with width < height
int[] width2height = new int[maxSquare + 1];

for (
    col = 0;
    col < width;
    col++)
{
    for (int s = 0; s <= maxSquare; s++)
    {
        width2height[s] = 0;
    }

    for (
        row = (height - 1);
        row >= 0;
        row--)
    {
        square = squares[row, col];

        if (square > 0)
        {
            maxSize = sizes[row, col];

            for (rectWidth = square; rectWidth > 0; rectWidth--)
            {
                rectHeight = width2height[rectWidth];

                rectHeight = Math.Max(
                    rectHeight + 1,
                    square);

                width2height[rectWidth] = rectHeight;

                size = GetSize(rectWidth, rectHeight);

                if (size > maxSize)
                {
                    maxSize = size;
                    widths[row, col] = rectWidth;
                    heights[row, col] = rectHeight;
                }
            }

            sizes[row, col] = maxSize;
        }

        for (
            int s = (square + 1);
            s <= maxSquare;
            s++)
        {
            // heights larger that 'square' will not be available
            width2height[s] = 0;
        }
    }
}

// find the largest rectangle
maxSize = 0;
rectWidth = 0;
rectHeight = 0;

int rectRow = 0;
int rectCol = 0;

for (row = 0; row < height; row++)
{
    for (col = 0; col < width; col++)
    {
        size = sizes[row, col];

        if (size > maxSize)
        {
            maxSize = size;
            rectRow = row;
            rectCol = col;
            rectWidth = widths[row, col];
            rectHeight = heights[row, col];
        }
    }
}

return (new Rectangle(rectCol, rectRow, rectWidth, rectHeight));

Let's take a look on outputs from this algorithm.

The following images show how widths, heights and sizes arrays look like:

Again, position of the maximum in the sizes array corresponds to the top left corner of the maximum inscribed rectangle. Dimensions of this rectangle are to be found at the same position in the widths and heights arrays.

Here is the maximum inscribed rectangle visualized:

The largest inscribed rectangle depends on GetSize function implenetation. The following image shows such a largest inscribed rectangle that emphasizes aspect ratio of 1:3:

Finally, we will apply the algorithm on the photograph mask displayed in the beginning of the article:

Here is the original photograph and the cropped version using the largest inscribed rectangle:

Additional Criteria

There may be more than one solution to the problem. The following picture shows a shape with just few of many largest inscribed rectangles to be found:

The search algorithm can be updated so that it returns all suitable rectangles. A list of rectangles with maximum size can be kept instead of remembering just the best one. A new entry is added to the list whenever a rectangle with matching size is found. When larger rectangle is found, the list is cleared and the rectangle is added as its first entry.

Another approach is to impose additional criteria on the rectangle, such as:

  • Conformity to given aspect ratio
  • Distance from image center
  • Distance from shape center (can be computed from binary mask using Distance Transform)
  • Information content within rectangle (this requires some measure from image data, such as entropy)

Evaluating additional criteria can be time-consuming, so these should be used only when comparing rectangles of the same size just to further distinguish them.

Algorithm Improvements

The CPU and memory demands can be lowered considerably with the following tweaks:

  • widths, heights and sizes arrays are unnecessary - I have used them in the sample just for visualizing the results. The arrays can be replaced by local variables storing just the best rectangle found so far.
  • Adding limits (minimum/maximum width/height) will speed up the search.
  • When the GetSize function is known and grows monotonically when either width or height (or both) values grow, one can predict if further searching is necessary (since he can answer the question: What is the next higher value of width/height so that GetSize will return larger value than current best?).
  • Searching for rectangles can be conveniently parallelized, at least to 2 threads (one for each loop / class of rectangles).

Automatic Cropping with SharpStitch

The SharpStitch library provides autocrop implementation mainly for the purpose of cropping panoramic image mosaics.

The SharpStitch package contains C# sample called AutoCropSample showing how to compute crop rectangle and do the actual cropping:

The library provides following extension methods to Picture type (used in SharpStitch to store images - this object can be converted to Image object and vice versa):

FindCrop(this Picture mask)
FindCrop(this Picture mask, Func<int, int, int> getSize)
FindCrop(this Picture mask, Func<int, int, int> getSize, Func<int, int, int, int, double> getCriteria)

The simplest usage is to just load the picture and call FindCrop:

Picture mask = Picture.FromFile(&quot;mask.png&quot;);

Rectangle cropRectangle = mask.FindCrop();

The FindCrop method returns Rectangle.Empty if no rectangle have been found.

Rectangle size is computed simply as the rectangle's area by default. You can specify custom metric providing a getSize delegate:

mask.FindCrop((width, height) => (width + height)); // use circumference as a measure of rectangle size

There can be more than one "largest" rectangle (as discussed earlier) and you can further distinguish these by providing additional criteria based on both rectangle location and dimensions:

mask.FindCrop(
    // use area as a measure of rectangle size
    (width, height) => (width * height),
    // from largest rectangles, select one that is nearest to the top-left corner of the image
    (left, top, width, height) => (-left * left - top * top));

The Picture object can be cropped and stored in image file or converted to .NET Image object:

// load input image and mask
Picture pictureInput = Picture.FromFile(&quot;input.png&quot;);
Picture pictureMask = Picture.FromFile(&quot;mask.png&quot;);

// find crop rectangle and crop the input picture
Rectangle rectCrop = mask.FindCrop();

Picture pictureCropped = mask.Crop(rectCrop);

// save the image right away
pictureCropped.SaveImage(&quot;output.png&quot;, SupportedImageFormat.Png);

// convert Picture to Image object
Image imageCropped = pictureInput.ToBitmap();

// save Image object
imageCropped.Save(&quot;output2.jpg&quot;, ImageFormat.Jpeg);

References

Inscribed_Rectangle by Jaroslaw Tuszynski - MATLAB Central
Original code in MATLAB

Download SharpStitch library Learn more about SharpStitch