Algorithm to best fit a rectangle

Question

I'm writing an application which measures boxes from pictures. A sample picture after manipulation is shown below:

My application has identified pixels that are part of the box and changed the color to red. You can see that the image is pretty noisy and therefore creates pretty rough looking edges on the rectangle.

I've been reading about edge/corner detection algorithms, but before I pursue one of them I wanted to step back and see if such a complicated algorithm is really necessary. It seems like there probably is a simpler way to go about this, considering I have a few conditions that simplify things:

• The image only contains a rectangle, not any other shape.
• Each image only has 1 rectangle.
• I do not need to be exact, though I'd like to achieve as best fit as I can.

My first go at a simple algorithm involved finding the top most, bottom most, left most and right most points. Those are the 4 corners. That works OK, but isn't super accurate for noisy edges like this. It is easy to eye ball a much better point as the corner.

Can anyone point me towards an algorithm for this?

Answer 1

You have already identified the region of the image that you are interested in(red region).

• Using this same logic you should be able to binarize the image. Say the red region then results in white pixels and the rest is black.
• Then trace the external contour of the white region using a contour tracing algorithm.
• Now you have a point set that represents the external contour of the region.
• Find the minimum-area-rectangle that bounds this point set.

You can easily do this using the OpenCV library. Take a look at threshold, findContours, and minAreaRect if you are planning to use OpenCV. Hope this information helps.