# How can I find all the rectangles in an image when they overlap?

When I apply MorphologicalComponents to images like the one below (which consist of white rectangles laid on a black background), I get a single object returned, as opposed to the two rectangles (since they happen to be "connected", as the two rectangles overlap):

Test image:

Output after applying MorphologicalComponents:

However I would like to obtain them as different components; if possible also obtaining the two full rectangles in other cases where they overlap more, such as in the unfortunate case of the following image:

I have tried simple transformations such as finding the perimeter:

from where I think shouldn't be too difficult to close the rectangles and retrieve them, but haven't managed so far... I have also tried more exotic ideas and transformations such as applying MorphologicalTransform to obtain the vertical and horizontal edges in two separate images, to them add them together, but again I have the problem of closing the different rectangles separately. I really need some help at this point, would appreciate any input.

• Perhaps "Overlay" will be helpful. It keeps the pictures apart. – Daniel Huber Oct 3 '20 at 10:00

A simple idea is to identify the corners and then create all possible rectangles that can be created from those corners:

img = ColorConvert[
Import["https://i.stack.imgur.com/i0HUj.png"],
"Grayscale"
];
corners = ImageCorners[img];
HighlightImage[img, corners]


A rectangle can be created using three points, so we simply create groups of points and attempt to create rectangles from them. We are then going to rate the rectangles using the following scoring function:

calculateScore[rectangle1_, rectangle2_] := Module[{union, intersection, outside},
outside = ImageMultiply[union, ColorNegate@img];
ImageMeasurements[ImageSubtract[union, ColorNegate@img], "Total"] - ImageMeasurements[outside, "Total"]
]


This scoring function is going to benefit solutions that cover as much as possible of the rectangles in the image, and it is going to penalize solutions that cover parts of the image that are not covered by the rectangles.

The rest of the code looks like this:

cornerSubsets = Subsets[corners, {3}];
candidateRectangles = Map[
renderRectangle[createRectangle[#], ImageDimensions[img]] &,
cornerSubsets
];
dist = DistanceMatrix[candidateRectangles, DistanceFunction -> calculateScore];
{idx1, idx2} = First@Position[dist, Max[dist]];
HighlightImage[
img, {
Red, createRectangle@cornerSubsets[[idx1]],
Blue, createRectangle@cornerSubsets[[idx2]]
}]


For your image where the rectangles don't have clearly defined corners, I would suggest merging nearby corners by taking their average before proceeding with the approach given above.

img = Import["https://i.stack.imgur.com/i0HUj.png"];

imgmesh = ImageMesh[img];

tworects = imgmesh //
MeshCoordinates //
Sort //
Subsets[#, {2}] & //
Select[VectorLess] //
Rectangle @@@ # &  //
Select[RegionWithin[imgmesh, #] &] //
Subsets[#, {2}] & //
Select[RegionEqual[RegionUnion @@ #, imgmesh] &] //
First

Show[img,
Graphics[{FaceForm[], Thread[{EdgeForm[{Thick, #}] & /@ {Red, Green}, tworects}]}]]


To find multiple rectangles that cover the image change the second Subsets[#, {2}]& to Subsets[#, {2, ∞}] & and remove First:

subrects = imgmesh // MeshCoordinates // Sort // Subsets[#, {2}] & //
Select[VectorLess] // Rectangle @@@ # & //
Select[RegionWithin[imgmesh, #] &] //
Subsets[#, {2, ∞}] & //
Select[RegionEqual[RegionUnion @@ #, imgmesh] &];

Show[img, Graphics[{{FaceForm[Opacity[.3, rc = RandomColor[]]],
EdgeForm[{Thick, rc}], #} & /@ #}],
PlotLabel -> Row[{Length@#, " rectangles"}], ImageSize -> 100] & /@
subrects // Multicolumn[#, 10] &