Fitting rectangle to segments in image

Question

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.

Answer 1

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.

Answer 2

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.