# Rectangular Image Segmentation?

I'd like to segment an image such that the components are rectangles. Is this possible out of the box? For example:

img = CloudGet[CloudObject["https://www.wolframcloud.com/obj/1e937fa7-80d2-4db2-8e47-80fe376c0e8f"]]
Colorize @ WatershedComponents[ ColorConvert[img, "Grayscale"] ]


You can imagine the output being something like the above but with rectangles instead of polygons, the fewer the better, could look something like this (a poor approximation drawn using Canvas[]):

A follow-up would be to specify thresholds and control min and max size/aspects of the rectangles.

Update

Here are a few additional examples to test solutions:

moreTests = CloudGet["https://www.wolframcloud.com/obj/"<>#]&/@
{"04b63372-f4cb-4c4f-9161-a8ca581b01fa","68b066cb-9775-44de-aba4-717449293713",
"cb413bbb-56ac-40b3-92dd-2029c0c40b2e","3f4b3af3-ce6e-4512-b917-17b0efa80fc9",

• The principal singular vectors make an interesting first approximation, but I don't where to go from here: {uu, ss, vv} = SingularValueDecomposition[ImageData@RemoveAlphaChannel@ColorConvert[img0, "Grayscale"]]; Colorize@ WatershedComponents[Image[uu[[All, {1}]] . Transpose@vv[[All, {1}]]], Method -> {"MinimumSaliency", 0.07}]. Needs something like a follow-up routine to combine some adjacent rectangles. But image-processing is not my thing. Mar 19 at 3:07
• It looks like a superpixels problem, I haven't seen a square superpixel algorithm yet, a similar effect is: epfl.ch/labs/ivrl/research/slic-superpixels May 17 at 2:35
• Do you have any guidance on the criteria you want for your segmentation? As stated, the problem is too unconstrained to really come up with a meaningful solution. Let's say your image is a rectangle, split along the diagonal such that on one side of the diagonal it's solid red and the other side of the diagonal is solid blue. What would you want this algorithm to do with that? May 17 at 15:17

Modification 2

I have significantly improved the code to get even closer to what M.R. was looking for. Rectangles now grow in width and height, reducing the number of narrow slices. Also, they grow from the four corners of the image. The function has two options:

1. "RectCount" allows you to specify the number of rectangles drawn, so you can get a partial result superimposed on the original image.
2. "Collage" (true or false) indicates if a collage of the image covered with rectangles with the original image is desired (default is false).
(* ===== The function ======= *)
growRects[img_, OptionsPattern[]] :=
Module[{image, pixelBlockSize, colorDiffLimit, subimages,
subColorList, pixelBlockCoordinates, pixelBlockCoordinatesLinear,
blocksInRect, initialBlockCoordinate, initialBlockColor, maxWidth,
maxHeight, lastColumn, lastRow, newColumn,
initialBlockCoordinateLinear, linearIndex, available, colorMatched,
withinBounds, newColumnAllowed, newRowAllowed, rectsList, lb,
newRow, rectColor, t, rt, initialBlockCoordinateLinear2,
initialBlockCoordinateLinear3, initialBlockCoordinateLinear4,
linearIndex2, linearIndex3, linearIndex4},

(* Users may modify the following to see the effect *)

pixelBlockSize = 10;
colorDiffLimit = 0.15;

(* Create block size images and a corresponding list of mean color \
for each subimage *)
subimages = ImagePartition[img, pixelBlockSize];
subColorList =
Table[
ImageMeasurements[subimages[[i]], "Mean"], {i, 1,
Length[subimages]}];

(* Reassemble the image -
image partition may have introduced some cropping *)

image = ImageAssemble[subimages];

(* get the coordinates in terms of pixel blocks -
we will grow rectangles by adding rows or columns of blocks *)
(*
we need four versions to facilitate dealing with four coordinate \
systems (one to draw from each corner) *)
pixelBlockCoordinates = {
Table[{i, j}, {i, 1, Length[subimages]}, {j, 1,
Length[subimages[[1]]]}],
Table[{i, j}, {i, Length[subimages], 1, -1}, {j, 1,
Length[subimages[[1]]]}],
Table[{i, j}, {i, 1, Length[subimages]}, {j,
Length[subimages[[1]]], 1, -1}],
Table[{i, j}, {i, Length[subimages], 1, -1}, {j,
Length[subimages[[1]]], 1, -1}]
};

(* The equivalent linear list of coordinates for each of the four \
systems *)

pixelBlockCoordinatesLinear =
Flatten[#, 1] & /@ pixelBlockCoordinates;

(* area to fill in pixelBlocksSize *)
{maxWidth, maxHeight} = Dimensions[subimages];
areaPoints = maxWidth*maxHeight;

(* number of blocks filled *)
blocksInRect = 0;

(* Using a rectangle counter *)

If[IntegerQ[count = OptionValue["RectCount"]], useCounter = True;
counter = 1, useCounter = False];

(* refers to our four modes of filling rectangles from each corner \
- we will rotate later*)
seedArray = {1, 2, 3, 4};

(* Start the rectangle loop -
each rectangle starts at the first point of \
pixelBlockCoordinatesLinear that is not 0 *)

While[areaPoints > blocksInRect,
If[useCounter && (counter++ > count), Break[]];

(* Each mode has different directions to grow rectangles *)

s = First[seedArray];
Which[
];
seedArray = RotateLeft[seedArray];

(* color assigned to the next rectangle *)

rectColor = RandomColor[];
im = Image[
RandomChoice[{rectColor}, {pixelBlockSize, pixelBlockSize}]];

(* the algorithm ensure that the first non zero element of each \
list of coordinates is the one we want *)
initialBlockCoordinate =
FirstCase[pixelBlockCoordinatesLinear[[s]], Except[0]];

(* find the linear position in each list of coordinate \
corresponding to our starting point *)

initialBlockCoordinateLinear =
maxHeight*(initialBlockCoordinate[[1]] -
1) + (initialBlockCoordinate[[2]]);
initialBlockCoordinateLinear2 =
maxHeight*(maxWidth -
initialBlockCoordinate[[1]]) + (initialBlockCoordinate[[2]]);
initialBlockCoordinateLinear3 =
maxHeight*(initialBlockCoordinate[[1]] - 1) + {maxHeight -
initialBlockCoordinate[[2]] + 1};
initialBlockCoordinateLinear4 =
maxHeight*(maxWidth - initialBlockCoordinate[[1]]) + {maxHeight -
initialBlockCoordinate[[2]] + 1};

(* remove used blocks from availability in all list *)

pixelBlockCoordinatesLinear[[1]][[initialBlockCoordinateLinear]] =
0;
pixelBlockCoordinatesLinear[[2]][[initialBlockCoordinateLinear2]] =
0;
pixelBlockCoordinatesLinear[[3]][[initialBlockCoordinateLinear3]] =
0;
pixelBlockCoordinatesLinear[[4]][[initialBlockCoordinateLinear4]] =
0;

(* color the initial block with the random color *)

subimages[[initialBlockCoordinate[[1]]]][[
initialBlockCoordinate[[2]]]] = im;

(* this is the color of the subimage at this location *)

initialBlockColor =
subColorList[[initialBlockCoordinate[[1]]]][[\
initialBlockCoordinate[[2]]]];

(* the first block in our rectangle *)

lastColumn = {initialBlockCoordinate};
lastRow = {initialBlockCoordinate};
blocksInRect = blocksInRect + 1;

(* Now we can alternate between adding rows and columns *)
newColumnAllowed = True;
newRowAllowed = True;

(* Start the rectangle growing loop *)

While[newColumnAllowed || newRowAllowed,

(* Attempt to add a column - extend the X coordinate -
test validity (available blocks, color) *)
If[newColumnAllowed,
(* create new column from existing last column *)

newColumn = {#[[1]] + cadd, #[[2]]} & /@ lastColumn;

(* is the new column within bounds *)

withinBounds = AllTrue[newColumn, 1 <= #[[1]] <= maxWidth &];
If[withinBounds,
(* get position ou the points in our four list of coordinates *)

linearIndex = maxHeight*(#[[1]] - 1) + (#[[2]]) & /@ newColumn;
linearIndex2 =
maxHeight*(maxWidth - #[[1]]) + (#[[2]]) & /@ newColumn;
linearIndex3 =
maxHeight*(#[[1]] - 1) + {maxHeight - #[[2]] + 1} & /@
newColumn;
linearIndex4 =
maxHeight*(maxWidth - #[[1]]) + {maxHeight - #[[2]] + 1} & /@
newColumn;

(* verifiy that coordinates have not been used before *)

available =
NoneTrue[
pixelBlockCoordinatesLinear[[1]][[#]] & /@ linearIndex,
IntegerQ];
If[available,
(* check color *)

colorMatched =
AllTrue[subColorList[[#[[1]], #[[2]]]] & /@ newColumn,
Max@Abs[Take[#, 3] - Take[initialBlockColor, 3]] <
colorDiffLimit &];
If[colorMatched,
(* keep the new column,
replacing the last column and adding a point to last row *)

blocksInRect = blocksInRect + Length[newColumn];
lastColumn = newColumn;
lastRow = AppendTo[lastRow, Last[lastRow] + {cadd, 0}];

(*
Mark column coordinates as not available in all four lists by \
setting coordinate to 0 *)
(pixelBlockCoordinatesLinear[[
1]][[#]] = 0) & /@ linearIndex;
(pixelBlockCoordinatesLinear[[2]][[#]] = 0) & /@
linearIndex2;
(pixelBlockCoordinatesLinear[[3]][[#]] = 0) & /@
linearIndex3;
(pixelBlockCoordinatesLinear[[4]][[#]] = 0) & /@
linearIndex4;

(* convert new column to full size colored blocks *)

For[i = 1, i <= Length[newColumn], i++,

subimages[[newColumn[[i]][[1]]]][[newColumn[[i]][[2]]]] =
im;
]

, newColumnAllowed = False (* not color matched *)]
, newColumnAllowed = False (* not available *)]
, newColumnAllowed = False (* not within bounds *)]
];

(* Attempt to add a row - extend the Y coordinate -
test validity (available blocks, color) *)
If[newRowAllowed,
(* create new row from existing last row *)

newRow = {#[[1]], #[[2]] + radd} & /@ lastRow;

(* is the new row within bounds *)

withinBounds = AllTrue[newRow, 1 <= #[[2]] <= maxHeight &];
If[withinBounds ,
(* get position ou the points in our four list of coordinates *)

linearIndex = maxHeight*(#[[1]] - 1) + (#[[2]]) & /@ newRow;
linearIndex2 =
maxHeight*(maxWidth - #[[1]]) + (#[[2]]) & /@ newRow;
linearIndex3 =
maxHeight*(#[[1]] - 1) + {maxHeight - #[[2]] + 1} & /@ newRow;
linearIndex4 =
maxHeight*(maxWidth - #[[1]]) + {maxHeight - #[[2]] + 1} & /@
newRow;

(* verifiy that coordinates have not been used before *)

available =
NoneTrue[
pixelBlockCoordinatesLinear[[1]][[#]] & /@ linearIndex,
IntegerQ];
If[available,
(* check color *)

colorMatched =
AllTrue[subColorList[[#[[1]], #[[2]]]] & /@ newRow,
Max@Abs[Take[#, 3] - Take[initialBlockColor, 3]] <
colorDiffLimit &];
If[colorMatched,
(* keep the new row,
replacing the last row and adding a point to last column *)

blocksInRect = blocksInRect + Length[newRow];
lastRow = newRow;
lastColumn =

(*
Mark row coordinates as not available in all four lists by \
setting coordinate to 0 *)
(pixelBlockCoordinatesLinear[[
1]][[#]] = 0) & /@ linearIndex;
(pixelBlockCoordinatesLinear[[2]][[#]] = 0) & /@
linearIndex2;
(pixelBlockCoordinatesLinear[[3]][[#]] = 0) & /@
linearIndex3;
(pixelBlockCoordinatesLinear[[4]][[#]] = 0) & /@
linearIndex4;

(* convert new row to full size colored blocks *)

For[i = 1, i <= Length[newRow], i++,
subimages[[newRow[[i]][[1]]]][[newRow[[i]][[2]]]] = im;
];
, newRowAllowed = False (* not color matched *)]
, newRowAllowed = False (* not available *)]
, newRowAllowed = False (* not within bounds *)]
]
];

];
assembly = ImageAssemble[subimages];
If[OptionValue["Collage"], ImageCollage[{image, assembly}], assembly]
]
Options[growRects] = {"RectCount" -> Infinity, "Collage" -> False};


Here are function calls with examples of results:

growRects[img1]
growRects[img1,"RectCount"->10]
growRects[img1,"Collage"->True]
... and a few more collages



Modification (original post, now replaced by the above)

In the various examples provided, some have 4 channels, some 3 channels. The code now tests for this, so all the examples work. Also, the variable subsize was set at 16 pixels before, but the optimal value depends on the size of the file. It is now set to 1/100 of the width of the image, but you can play with it to optimize a particular image. Unfortunately, this code produces narrow rectangles, which is not exactly what was required.

(* Get the image *)

img = CloudGet[
CloudObject[
"https://www.wolframcloud.com/obj/1e937fa7-80d2-4db2-8e47-\
80fe376c0e8f"]];

(* Partition the image *)
subsize = 1/100*ImageDimensions[img][[1]];
subimages = ImagePartition[img, subsize];

(* Measure average color of subimages *)

t = Table[
ImageMeasurements[subimages[[i]], "Mean"], {i, 1,
Length[subimages], 1}];

(* Get positions where color change greater than 0.1 in one direction \
*)

channels = ImageMeasurements[img, "Channels"];
Which[channels == 4, ch1 = {0., 0., 0., _}; ch2 = {_, _, _, _},
channels == 3, ch1 = {0., 0., 0.}; ch2 = {_, _, _}];

pv = Reverse[
Position[
Table[
Threshold[Differences[t[[i]]], {"Hard", 0.1}] /. ch1 -> " " /.
ch2 -> "|", {i, 1, Length[t], 1}], "|"], 2];

(* Get positions where color change greater than 0.1 in the other \
direction *)

trt = Transpose[t];
ph = Position[
Table[
Threshold[Differences[trt[[i]]], {"Hard", 0.1}] /. ch1 -> " " /.
ch2 -> "_", {i, 1, Length[trt], 1}], "_"];

(* Find intersection *)
inter = Intersection[pv, ph];

(* Convert the list to image coordinates and add missing points \
(where y=0) *)

interS = {#[[1]], ImageDimensions[img][[2]] - #[[2]]} & /@ (subsize*
inter);
final = {};
AppendTo[final, {#[[1]], 0}] & /@ interS;
p = SortBy[DeleteDuplicates@Join[interS, final], {First, Greater}];

(* Function to process list p of coordinates and draw rectangles. h \
is the height *)

rectangleSegments[h_, p_List] :=
Module[{rects, anchor, prevCol, prevRow},
rects = {};
anchor = {0, h};
prevCol = 0;
prevRow = 0;

i = 1;
While[i <= Length[p],
If[
p[[i]][[1]] != prevCol,
anchor = {prevCol, h},
anchor = {anchor[[1]], prevRow};
];
AppendTo[rects, {anchor, p[[i]]}];
prevCol = p[[i]][[1]];
prevRow = p[[i]][[2]];
i++;
];
rects
]

(* Calling function *)

rseg = rectangleSegments[ImageDimensions[img][[2]], p];
Show[Graphics[{EdgeForm[Black], FaceForm[RandomColor[]],
Rectangle[#[[1]], #[[2]]]}] & /@ rseg]


• I like this approach, if you can make it do the right thing for the additional few test images I posted above, I will accept!
– M.R.
May 20 at 21:23
• In the six examples I added, whenever there is a big clear space (constant or perhaps a smooth gradient) the algo should produce a larger rectangle that "fills that space", not just lots of tiny ones...
– M.R.
May 20 at 21:27
• Also, the big yellow rect on the left in your example should not have three short ones below it (because the image is all white down to the bottom edge)
– M.R.
May 20 at 21:32
• I made some modifications (see main window), but I am afraid that the problem filling big clear spaces is not solved. May 20 at 22:59
• Have you considered using something like ColorQuantize or DominantColors in preprocessing May 20 at 23:07