# Fitting rectangle to segments in image

I have the task to fit a rotated rectangle of known size into an image like

This is a synthetic test case, in the real application, everything is rather blurred. The rectangle has to cover as much as possible of the black region, while covering as little as possible of the grey region while the white region is ignored. I don't always see all corners, it could e.g. be possible that I just have the upper half of the rectangle and a much larger white area.

I've so far implemented a straight forward gradient descent to search in the 3d space (x,y, rotation) and optimize for the difference of black and gray pixels within the current pose of the rectangle. This approach is not very fast so I'd like to ask for alternatives.

• How fast are you striving to make this run? Does it need to be real time? – spektr May 20 '16 at 19:35
• And is the white region always within the black? – spektr May 20 '16 at 19:42
• OpenCV is a commonly-used library that should be able to handle this problem directly, and it is probably much more robust than writing your own. I'm not familiar with it, but this looks close: docs.opencv.org/2.4/modules/imgproc/doc/… – Kirill May 21 '16 at 5:50
• how does findContours help in this case? It would only find the regions but I am looking for the rectangle that contains both black and the white region. – FooBar May 21 '16 at 11:20
• @FooBar Like I said, I haven't used it, but it seems like it would find the rectangles matching the contours (maybe separately), so that all you have to do is merge the rectangles. There are many tutorials online about OpenCV, so perhaps look there. (Btw, please use "@username" so that whoever you're replying to gets notified.) – Kirill May 21 '16 at 19:54

You might be able to do better than simple gradient descent using an algorithm like BFGS, which uses the history of the gradients as well as the approximate solutions to try and approximate the Hessian of the objective functional. A good explanation of how the algorithm works, modifications for large systems, modifications in the event of non-convexity, etc. can be found in Nocedal and Wright. BFGS is one of a more general family of quasi-Newton methods.

One of your parameters (the orientation) is defined not in a vector space but rather in the group $S^1$; moreover, you get the same fit for some orientation $\theta$ as for $\theta + \pi$. So there's some degeneracy in the solution due to the fact that the image you're fitting has a discrete symmetry, namely reflection in one axis. So the solution might not be quite as simple as just using BFGS instead of gradient descent, but it's a good place to start.

You can speed up your process by taking multi-scale approach, i.e. perform template matching on coarse scale, then upscale and refine parameters. Of course, the number of levels and step size depends on your problem and it may be tricky to determine.

You can take a more analytical approach by first extracting edges from the image (I guess Canny would work best in this case) and then use either Hough Transform or RANSAC (RANdom SAmple and Concensus) approach to extract all lines.

Using some assumptions about the rectangle color (black or white foreground to grey background), you can tell which side of each line goes inside the rectangle.

Finally, having at least 2 lines will constrain your optimization problem enough so that you can solve this without optimization.

Another approach may target for rectangle corners, i.e. using Harris Corner Detector and then determining rectangle orientation from patch around each corner.