How can I divide a region into rectangles, so that the sum of elements in each rectangle is approximately equal?

Hello,

I have a matrix (55x400) which contains the object appearance density in each point. It is based on a traffic and infrastructure study and represents the view from the center of a vehicle, at a height of 0.75 m. Using imagesc i was able to represent my data with an x-axis range from -20 to 20 degrees horizontally and an y-axis range from -0.5 to 5 degrees vertically. What I need to do is to divide this region into segments (for a so-called "matrix beam" or "pixel light" system). The sum of the appearance densities in each rectangle should be approximately equal, so as to have a proportional division of the segments (regions with more object density should be smaller and vice versa). Until now I was only able to divide separately into vertical segments or into horizontal segments by searching the widths or the heights of the segments until the sums would be approximately equal. I would like to do this by creating random rectangles inside my area of interest and then calculate the sum inside the rectangles until the sums are approximately equal and some conditions are met (for example: maximum number of rectangles, minimum and maximum size of rectangles). I have to add that I'm pretty new to MATLAB and my programming skills are not the best. What I managed to do until now is the following:

In the above image I created the vertical segments first, so that the the sums of the densities contained inside each segment are equal. Then I did the same for the horizontal segments and I overlapped the results. The problem is that the sums inside the overlapped rectangles aren't equal by using this method and I would like to know how I could generate these rectangles randomly until some given conditions are met.

Your help would be much appreciated.

Many thanks, Dan

[Walter Roberson]

There was a question earlier this year that had a similar request for a quite different purpose. We did not get very far; the user requirements were not really precise enough. I recommend that you scan through it and the follow up to it,

https://www.mathworks.com/matlabcentral/answers/282996-an-uniform-grid-where-each-pixel-voxel-got-is-own-value-i-want-to-create-a-new-grid-where-each-pix and http://www.mathworks.com/matlabcentral/answers/283012-an-uniform-grid-where-each-pixel-voxel-got-is-own-value-i-want-to-create-a-new-grid-where-each-pix and note the reference to Gerrymandering (you want to divide the area into "districts" which have equal "votes")

[Walter Roberson]

I would expect that random decomposition would be very inefficient for this kind of task.

Answer 1

[Dan Bursasiu]

I managed to solve my issue: after refining my data matrix by using interp2 I divided the sum of all matrix elements by the number of segments and then proceeded to find this value by summing between the indices of my matrix (horizontally and vertically) until I found the same value. It might sound somewhat ambiguous but the attached image should explain it better:

In this case I have 84 "pixels" (28 columns and 3 rows). The sum of all the elements of my matrix is 2.5453e+08. If I divide it by 84 I get a value of 3.0301e+06. First I sum horizontally from left to right until I find the value sum(sum(data))/28 to get proportionally wide columns. Then I proceed to sum inside each column, starting from the bottom, until I find the value of 3.0301e+06 or sum(sum(data))/84. In the end I get rectangles with roughly the same sum inside them, which was my initial goal.

Answer 2

[Image Analyst]

My first attempt would be to use quadtree decomposition. See qtdecomp().

[Dan Bursasiu]

I have read about quadtree decomposition, as you also suggested this in the posts referenced by Walter Roberson. Firstly, the qtdecomp() function only works on square images and creates sub-squares, but I need rectangles and my image is not square (it is stretched in the picture I attached, but actually it would have a large width and a small height; with a size of 55x400 you get an aspect ratio of 1:7). The second problem with qtdecomp is that it needs a black and white image as an input. I currently work directly with my data matrix and sum the elements vertically and horizontally. The image created with imagesc doesn't accurately show the whole range of values, as there are, for example, many values between 0 and 0.1, but you can't distinguish them because of the blue shade used in this colormap (i have tried other colormaps but to no extent). So when I convert the image to black and white with rgb2gray() the shades of gray don't represent my data accurately.

[Image Analyst]

Dan, you don't need to convert to an 8 bit gray scale image. From the help: "For the syntaxes that do not include a function, the input image can be of class logical, uint8, uint16, int16, single, or double." So leave your data as double if you want.

It does not matter if your matrix is square - I believe it will work with a 55x400 array of doubles. After it's squares, you could merge adjacent squares if you want, but you'd have to custom program that region merging operation since I don't think there is a built in function for that.

[Dan Bursasiu]

You're right about the input image types, I made a confusion. But still, the documentation clearly states that it works on square images ("qtdecomp divides a square image into four equal-sized square blocks"), even the two examples are of a square matrix and a square image. If I try to add another column to the example matrix, I get the error:

Error using qtdecomp>ParseInputs (line 205) Size of A is not a multiple of the maximum block dimension.

I get the same error if I try to apply the function to my matrix.

Answer 3

[Walter Roberson]

If you stay with rectangles, then what you ask is not generally possible, except with the degenerate case of leaving everything in a single rectangle.

Consider a grid such as

       o o

   o o

where the o are point sources. If you divide equally horizontally you need to do it between the top and bottom

       o o
   -------
   o o

If you divide equally vertically you need to do it between left and right

      |o o
      |
   o o|

Put those together...

      |o o
   ---|---
   o o|

and you clearly end up with empty rectangles.

You would have to move the vertical divider to the right to include something in the upper left rectangle, but doing that would cause the left half to add to 3 and the right to 1, which is not "approximately equal", and you would still end up with an empty lower-right rectangle. If you try to get something into the upper left by moving the dividing line down, you end up with no horizontal dividing lines.

Consider too the arrangement

   X

   X   X

where the X's are equal blobs. You can divide,

   X |
   -----
   X | X

but you end up with the empty upper right.