Best-fit a rectangle over a 2D blob

Question

I have a binary blob (see image), and I want to fit a rectangle of known width and height over it.

How can I find the optimal fitting rectangle, i.e. the one where the maximum of foreground pixels are inside and the maximum amount of background pixels are outside?

(This is my preliminary definition of best-fit, I am open to other suggestions)

I am looking for rectangles of a known size, but if there is a solution for arbitrary sizes, that would be great too.

Example blobs:

I want to find these rectangles:

My ideas so far included

• start with the minimum enclosing rectangle; but that is not a good match for these blobs
• maximum enclosed rectangle; same problem, plus I do not have an algorithm for that
• find rectangle sides with hough transform; the data is too noisy for that.

I realize that there could be multiple rectangles for the same blob that fit my criteria, ideally I would want some algorithm that can find all candidates (thought since that is probably harder, I'd be happy with a way to find only one candidate):

I am using mostly opencv and cvBlobLib to process my data, but I am open for any general solution.

Answer 1

I have seen a thesis on a similar subject (circle covering on a RGB plane), based on an evolutionary approach.

• The objective function was clearly defined (How many squares? How big? Can they overlap? You'd probably want to penalize small or overlapping squares).
• You may start by running the k-means algorithm to preprocess the data, i.e. find potential center points of the squares.

As I recall, SGA, CGA and eCGA were compared (CGA started with initial, k-means-based covering), with SGA outperforming the others. They were ran on a per-image basis. There were around 30 individuals and 20 generations with runtimes around a couple of minutes.

As for the SGA, the crossover operator would take two parents at a time and pair up the closes/most similar circles from both of the parents. Then, for each pair, it would draw a children circle somewhere in between with a radius also in between that of the two circles'. (Though I would suggest not to take values exactly between those of the parents', but allow +/- 15% outside the range. It would keep the population from the premature convergence).

With rectangles, you'd have to slightly modify the approach; each rectangle could be a tuple (x, y, width, height, rotation), with x and y being the coordinates of the center.