How do I crop to largest interior bounding box in OpenCV?

Question

I have some images on a black background where the images don't have square edges (see bottom right of image below). I would like to crop them down the largest rectangular image (red border). I know I will potentially lose from of the original image. Is it possible to do this in OpenCV with Python. I know there are are functions to crop to a bounding box of a contour but that would still leave me with black background in places.

Bradybradycardia

What more can you tell besides 'images don't have square edges'? is it always like in the example - where you need to crop from bottom and right? (in that case it is pretty simple) – Wanitawanneeickel

The image (none black area) can have any shape, an I want to convert it to be rectangular while losing the minimum amount of the image. – Bradybradycardia

Answer 1

ok, I've played with an idea and tested it (it's c++ but you'll probably be able to convert that to python):

1. assumption: background is black and the interior has no black boundary parts
2. you can find the external contour with findContours
3. use min/max x/y point positions from that contour until the rectangle that is built by those points contains no points that lie outside of the contour

I can't guarantee that this method always finds the "best" interior box, but I use a heuristic to choose whether the rectangle is reduced at top/bottom/left/right side.

Code can certainly be optimized, too ;)

using this as a testimage, I got that result (non-red region is the found interior rectangle):

regard that there is one pixel at top right that shouldnt containt to the rectangle, maybe thats from extrascting/drawing the contour wrong?!?

and here's code:

cv::Mat input = cv::imread("LenaWithBG.png");

cv::Mat gray;
cv::cvtColor(input,gray,CV_BGR2GRAY);

cv::imshow("gray", gray);

// extract all the black background (and some interior parts maybe)
cv::Mat mask = gray>0;
cv::imshow("mask", mask);

// now extract the outer contour
std::vector<std::vector<cv::Point> > contours;
std::vector<cv::Vec4i> hierarchy;

cv::findContours(mask,contours,hierarchy, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_NONE, cv::Point(0,0));

std::cout << "found contours: " << contours.size() << std::endl;


cv::Mat contourImage = cv::Mat::zeros( input.size(), CV_8UC3 );;

//find contour with max elements
// remark: in theory there should be only one single outer contour surrounded by black regions!!

unsigned int maxSize = 0;
unsigned int id = 0;
for(unsigned int i=0; i<contours.size(); ++i)
{
    if(contours.at(i).size() > maxSize)
    {
        maxSize = contours.at(i).size();
        id = i;
    }
}

std::cout << "chosen id: " << id << std::endl;
std::cout << "max size: " << maxSize << std::endl;

/// Draw filled contour to obtain a mask with interior parts
cv::Mat contourMask = cv::Mat::zeros( input.size(), CV_8UC1 );
cv::drawContours( contourMask, contours, id, cv::Scalar(255), -1, 8, hierarchy, 0, cv::Point() );
cv::imshow("contour mask", contourMask);

// sort contour in x/y directions to easily find min/max and next
std::vector<cv::Point> cSortedX = contours.at(id);
std::sort(cSortedX.begin(), cSortedX.end(), sortX);

std::vector<cv::Point> cSortedY = contours.at(id);
std::sort(cSortedY.begin(), cSortedY.end(), sortY);


unsigned int minXId = 0;
unsigned int maxXId = cSortedX.size()-1;

unsigned int minYId = 0;
unsigned int maxYId = cSortedY.size()-1;

cv::Rect interiorBB;

while( (minXId<maxXId)&&(minYId<maxYId) )
{
    cv::Point min(cSortedX[minXId].x, cSortedY[minYId].y);
    cv::Point max(cSortedX[maxXId].x, cSortedY[maxYId].y);

    interiorBB = cv::Rect(min.x,min.y, max.x-min.x, max.y-min.y);

// out-codes: if one of them is set, the rectangle size has to be reduced at that border
    int ocTop = 0;
    int ocBottom = 0;
    int ocLeft = 0;
    int ocRight = 0;

    bool finished = checkInteriorExterior(contourMask, interiorBB, ocTop, ocBottom,ocLeft, ocRight);
    if(finished)
    {
        break;
    }

// reduce rectangle at border if necessary
    if(ocLeft)++minXId;
    if(ocRight) --maxXId;

    if(ocTop) ++minYId;
    if(ocBottom)--maxYId;


}

std::cout <<  "done! : " << interiorBB << std::endl;

cv::Mat mask2 = cv::Mat::zeros(input.rows, input.cols, CV_8UC1);
cv::rectangle(mask2,interiorBB, cv::Scalar(255),-1);

cv::Mat maskedImage;
input.copyTo(maskedImage);
for(unsigned int y=0; y<maskedImage.rows; ++y)
    for(unsigned int x=0; x<maskedImage.cols; ++x)
    {
        maskedImage.at<cv::Vec3b>(y,x)[2] = 255;
    }
input.copyTo(maskedImage,mask2);

cv::imshow("masked image", maskedImage);
cv::imwrite("interiorBoundingBoxResult.png", maskedImage);

with reduction function:

bool checkInteriorExterior(const cv::Mat&mask, const cv::Rect&interiorBB, int&top, int&bottom, int&left, int&right)
{
// return true if the rectangle is fine as it is!
bool returnVal = true;

cv::Mat sub = mask(interiorBB);

unsigned int x=0;
unsigned int y=0;

// count how many exterior pixels are at the
unsigned int cTop=0; // top row
unsigned int cBottom=0; // bottom row
unsigned int cLeft=0; // left column
unsigned int cRight=0; // right column
// and choose that side for reduction where mose exterior pixels occured (that's the heuristic)

for(y=0, x=0 ; x<sub.cols; ++x)
{
    // if there is an exterior part in the interior we have to move the top side of the rect a bit to the bottom
    if(sub.at<unsigned char>(y,x) == 0)
    {
        returnVal = false;
        ++cTop;
    }
}

for(y=sub.rows-1, x=0; x<sub.cols; ++x)
{
    // if there is an exterior part in the interior we have to move the bottom side of the rect a bit to the top
    if(sub.at<unsigned char>(y,x) == 0)
    {
        returnVal = false;
        ++cBottom;
    }
}

for(y=0, x=0 ; y<sub.rows; ++y)
{
    // if there is an exterior part in the interior
    if(sub.at<unsigned char>(y,x) == 0)
    {
        returnVal = false;
        ++cLeft;
    }
}

for(x=sub.cols-1, y=0; y<sub.rows; ++y)
{
    // if there is an exterior part in the interior
    if(sub.at<unsigned char>(y,x) == 0)
    {
        returnVal = false;
        ++cRight;
    }
}

// that part is ugly and maybe not correct, didn't check whether all possible combinations are handled. Check that one please. The idea is to set `top = 1` iff it's better to reduce the rect at the top than anywhere else.
if(cTop > cBottom)
{
    if(cTop > cLeft)
        if(cTop > cRight)
            top = 1;
}
else
    if(cBottom > cLeft)
        if(cBottom > cRight)
            bottom = 1;

if(cLeft >= cRight)
{
    if(cLeft >= cBottom)
        if(cLeft >= cTop)
            left = 1;
}
else
    if(cRight >= cTop)
        if(cRight >= cBottom)
            right = 1;



return returnVal;
}

bool sortX(cv::Point a, cv::Point b)
{
    bool ret = false;
    if(a.x == a.x)
        if(b.x==b.x)
            ret = a.x < b.x;

    return ret;
}

bool sortY(cv::Point a, cv::Point b)
{
    bool ret = false;
    if(a.y == a.y)
        if(b.y == b.y)
            ret = a.y < b.y;


    return ret;
}

Quadratic

The algorithm is not correct. Is fails for instance with the following polygon and returns a zero height bounding box: {x=186 y=205 } {x=464 y=43 } {x=378 y=427 } {x=3 y=325 } – Outsmart

@Outsmart yes, for such a contour, the heuristic will not work at all. – Quadratic

maybe have a look at this, too: #2478947 – Quadratic

Answer 2

A solution inspired by @micka answer, in python.

This is not a clever solution, and could be optimized, but it worked (slowly) in my case.

I modified you image to add a square, like in your example: see

At the end, this code crops the white rectangle in this

Hope you will find it helpful!

import cv2

# Import your picture
input_picture = cv2.imread("LenaWithBG.png")

# Color it in gray
gray = cv2.cvtColor(input_picture, cv2.COLOR_BGR2GRAY)

# Create our mask by selecting the non-zero values of the picture
ret, mask = cv2.threshold(gray,0,255,cv2.THRESH_BINARY)

# Select the contour
mask , cont, _ = cv2.findContours(mask, cv2.RETR_CCOMP, cv2.CHAIN_APPROX_SIMPLE)
# if your mask is incurved or if you want better results, 
# you may want to use cv2.CHAIN_APPROX_NONE instead of cv2.CHAIN_APPROX_SIMPLE, 
# but the rectangle search will be longer

cv2.drawContours(gray, cont, -1, (255,0,0), 1)
cv2.imshow("Your picture with contour", gray)
cv2.waitKey(0)

# Get all the points of the contour
contour = cont[0].reshape(len(cont[0]),2)

# we assume a rectangle with at least two points on the contour gives a 'good enough' result
# get all possible rectangles based on this hypothesis
rect = []

for i in range(len(contour)):
    x1, y1 = contour[i]
    for j in range(len(contour)):
        x2, y2 = contour[j]
        area = abs(y2-y1)*abs(x2-x1)
        rect.append(((x1,y1), (x2,y2), area))

# the first rect of all_rect has the biggest area, so it's the best solution if he fits in the picture
all_rect = sorted(rect, key = lambda x : x[2], reverse = True)

# we take the largest rectangle we've got, based on the value of the rectangle area
# only if the border of the rectangle is not in the black part

# if the list is not empty
if all_rect:
    
    best_rect_found = False
    index_rect = 0
    nb_rect = len(all_rect)
    
    # we check if the rectangle is  a good solution
    while not best_rect_found and index_rect < nb_rect:
        
        rect = all_rect[index_rect]
        (x1, y1) = rect[0]
        (x2, y2) = rect[1]
        
        valid_rect = True
        
        # we search a black area in the perimeter of the rectangle (vertical borders)
        x = min(x1, x2)
        while x <max(x1,x2)+1 and valid_rect:
            if mask[y1,x] == 0 or mask[y2,x] == 0:
                # if we find a black pixel, that means a part of the rectangle is black
                # so we don't keep this rectangle
                valid_rect = False
            x+=1
        
        y = min(y1, y2)
        while y <max(y1,y2)+1 and valid_rect:
            if mask[y,x1] == 0 or mask[y,x2] == 0:
                valid_rect = False
            y+=1
            
        if valid_rect:
            best_rect_found = True
        
        index_rect+=1
        
    if best_rect_found:
        
        cv2.rectangle(gray, (x1,y1), (x2,y2), (255,0,0), 1)
        cv2.imshow("Is that rectangle ok?",gray)
        cv2.waitKey(0)

        # Finally, we crop the picture and store it
        result = input_picture[min(y1, y2):max(y1, y2), min(x1,x2):max(x1,x2)]

        cv2.imwrite("Lena_cropped.png",result)
    else:
        print("No rectangle fitting into the area")
    
else:
    print("No rectangle found")

If your mask is incurved or simply if you want better results, you may want to use cv2.CHAIN_APPROX_NONE instead of cv2.CHAIN_APPROX_SIMPLE, but the rectangle search will take more time (because it's a quadratic solution in the best case).

Mymya

Answer 3

In ImageMagick 6.9.10-30 (or 7.0.8.30) or higher, you can use the -trim function with a new define.

Input:

convert image.png -fuzz 5% -define trim:percent-background=0% -trim +repage result.png

Or for the image presented below:

Input:

convert image2.png -bordercolor black -border 1 -define trim:percent-background=0% -trim +repage result2.png

Henning

Answer 4

You can compute the largest interior bounding box with the largestinteriorrectangle package. They come as [x, y, width, height].

To crop the inner bounding box use the following code

import cv2 as cv
import numpy as np
import largestinteriorrectangle as lir

img = cv.imread("LenaWithBG.png")
gray = cv.cvtColor(img, cv.COLOR_BGR2GRAY)
_, mask = cv.threshold(gray, 0, 255, cv.THRESH_BINARY)
contours, _ = cv.findContours(mask, cv.RETR_TREE, cv.CHAIN_APPROX_NONE)

contour = np.array([contours[0][:, 0, :]])
inner_bb = lir.lir(contour)

cropped_img = img[inner_bb[1]:inner_bb[1] + inner_bb[3],
                  inner_bb[0]:inner_bb[0] + inner_bb[2]]

Let's plot this:

cv.imshow('Lena', img)

plot = img.copy()
cv.polylines(plot, [contour], True, (0, 0, 255))
cv.rectangle(plot, lir.pt1(inner_bb), lir.pt2(inner_bb), (255, 0, 0))

cv.imshow('Inner Bounding Box', plot)
cv.waitKey(0)
cv.destroyAllWindows()

cv.imshow('Cropped Image', cropped_img)
cv.waitKey(0)
cv.destroyAllWindows()

Caldarium