The rectangle above the 2D blob works best

Question

I have a binary blob (see image) and I want to place a rectangle with a known width and height above it.

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

(This is my preliminary determination of the 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, this is also great.

Blobs example:

I want to find these rectangles:

My ideas are still included

• start with a minimal rectangle; but it is not very suitable for these blobs
• maximum closed rectangle; same problem, plus I don't have an algorithm for this
• find rectangular sides with hough transform; Too noisy data for this.

I understand that there may be several rectangles for the same blob that meet my criteria, ideally I would like some algorithm to find all the candidates (thought it was probably harder, I would be happy to find way to find only one candidate):

I mainly use opencv and cvBlobLib to process my data, but I am open to any general solution.

Answer 1

I saw a thesis on a similar topic (circular coverage on the RGB plane), based on an evolutionary approach.

• The objective function has been clearly defined (How many squares? How big? Can they intersect? You probably want to fine small or overlapping squares).
• You can start by launching the k-means data preprocessing algorithm, i.e. find the potential center points of the squares.

As I recall, SGA, CGA and eCGA were compared (CGA started with initial coverage based on k-means), and SGA was superior to the rest. They were launched based on the image. Within a few minutes there were about 30 people and 20 generations with lead times.

For SGA, the crossover operator will take two parents at a time and pair closed / most similar circles from both parents. Then, for each pair, he will draw a children's circle somewhere in the middle with a radius also between the two circles. (Although I would advise not to take the values ​​exactly between the parents, but to allow +/- 15% outside the range, which will save the population from premature convergence).

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