Merging uniform boxes into larger ones

Hi,

I have codes below that merging uniform boxes into fewer, larger boxes. Any suggestions where I can improve it to try to group them more efficiently with fewer, larger boxes.

1 indicates box position.

boxGrid= [...
    0   0   0   1   1   0   0   0   0   0   0   0   0   1   1   0   0   0
    0   0   1   1   1   1   1   0   0   0   0   0   0   1   1   1   0   0
    0   0   0   1   1   1   1   1   0   0   0   0   0   0   0   0   0   0
    0   0   0   0   0   1   1   1   0   0   0   0   0   0   0   0   0   0
    0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0
    0   1   1   1   0   0   1   0   0   0   1   0   0   0   0   0   0   0
    1   1   1   1   1   1   1   1   0   1   1   1   1   1   0   0   0   0
    0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   0   0   0
    0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   0   0
    0   0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   0
    0   0   0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
    0   0   0   0   1   1   1   1   1   1   1   1   1   1   1   1   1   1
    0   0   0   0   0   0   1   1   1   1   1   1   1   1   1   1   1   0
    0   0   0   0   0   0   0   0   1   0   0   0   0   1   1   1   0   0];

[rows, cols]= size( boxGrid);
visited     = false( rows, cols);  % Matrix to track visited cells
mergedBoxes = NaN( rows*cols, 4);  % Initialize array to store merged boxes
boxNewMask  = zeros( rows, cols);
% Iterate through each cell in the grid
grpLabel = 0;
cntn     = 0;
for iRow= 1:rows
    for jCol= 1:cols
        cntn = cntn+ 1;
        if boxGrid( iRow, jCol)== 1 && ~visited( iRow, jCol)
            grpLabel = grpLabel+ 1;
            % If this cell is part of a box and not yet visited
            [ height, width] = find_max_rectangle( boxGrid, visited, iRow, jCol);
            
            % Mark the rectangle as visited
            idxRow= iRow:iRow+height-1;
            idxCol= jCol:jCol+width-1;
            boxNewMask( idxRow, idxCol) = grpLabel;
            visited( idxRow, idxCol)= true;
        end % if boxGrid
    end % for jCol
end % for iRow

function [ height, width] = find_max_rectangle( boxGrid, visited, startRow, startCol)
    % Helper function to find the maximum rectangle starting at (startRow, startCol)
    [ rows, cols] = size( boxGrid);
    
    % Find the maximum width
    width = 0;
    for col = startCol:cols
        if boxGrid(startRow, col) == 1 && ~visited(startRow, col)
            width = width + 1;
        else
            break;
        end % if
    end % for
    
    % Find the maximum height
    height = 0;
    for row = startRow:rows
        if all(boxGrid(row, startCol:startCol+width-1) == 1) && all(~visited(row, startCol:startCol+width-1))
            height = height + 1;
        else
            break;
        end % if
    end % for 
end % sub function

% the boxNewMask is below, which there could be larger box grouped.
boxNewMask = [...
    0     0     0     1     1     0     0     0     0     0     0     0     0     2     2     0     0     0
    0     0     3     1     1     4     4     0     0     0     0     0     0     2     2     5     0     0
    0     0     0     1     1     4     4     6     0     0     0     0     0     0     0     0     0     0
    0     0     0     0     0     4     4     6     0     0     0     0     0     0     0     0     0     0
    0     0     0     0     0     0     7     0     0     0     0     0     0     0     0     0     0     0
    0     8     8     8     0     0     7     0     0     0     9     0     0     0     0     0     0     0
    10     8     8     8    11    11     7    12     0    13     9    14    14    14     0     0     0     0
    0     8     8     8    11    11     7    12    15    13     9    14    14    14    16     0     0     0
    0     8     8     8    11    11     7    12    15    13     9    14    14    14    16    17     0     0
    0     0    18    18    11    11     7    12    15    13     9    14    14    14    16    17    19     0
    0     0     0    20    11    11     7    12    15    13     9    14    14    14    16    17    19    21
    0     0     0     0    11    11     7    12    15    13     9    14    14    14    16    17    19    21
    0     0     0     0     0     0     7    12    15    13     9    14    14    14    16    17    19     0
    0     0     0     0     0     0     0     0    15     0     0     0     0    22    16    17     0     0];

Thanks,

[Stephen23]

"Any suggestions where I can improve it to try to group them more efficiently with fewer, larger boxes"

This is likely an NP hard optimization problem, which means in general the most efficient approach would be to apply some heuristic-based algorithm to it. Precisely what specific metric do you wish to optimize:

• minimize the number of boxes
• maximum box area/side-length/...
• minimum box area/side-length/...
• range/mean/mode/standard distribution of box size
• some weighted function of several metrics (if so, what metrics and what weights).

[Pete sherer]

Ideally would like to minimize number of boxes.

Answer 1

[Stephen23]

You could download this FEX submssion:

https://www.mathworks.com/matlabcentral/fileexchange/28155-inscribed_rectangle

and use it with a simple greedy algorithm, e.g.:

G = [0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0; 0,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,0,0; 0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0; 0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0; 0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0; 0,1,1,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0; 1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,0,0,0; 0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0; 0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0; 0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0; 0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1; 0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1; 0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0; 0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0,0];
X = 0;
for k = 1:numel(G)
    [~,~,~,M] = FindLargestRectangles(G, [1,1,0], [1,1]);
    if any(M(:))
        X = X+k*M;
        G = G-M;
    else
        break
    end
end
max(X(:)) % number of rectangles

ans = 19

display(X)

X = 14×18

0 0 0 14 14 0 0 0 0 0 0 0 0 12 12 0 0 0 0 0 7 7 7 7 7 0 0 0 0 0 0 12 12 18 0 0 0 0 0 8 8 8 8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 11 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 10 10 10 0 0 15 0 0 0 17 0 0 0 0 0 0 0 6 6 6 6 6 6 6 6 0 9 9 9 9 9 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 19 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

[Pete sherer]

This one seems to do the job, but definitely can be more optimized.

[Image Analyst]

From the labeling, it appears that all the rectangles are horizontal. I suppose another labeling could be done where they're mostly vertical. Might need to do it both ways to see which uses fewer rectangles. But even then, I'm sure there are other divisions that could product both vertical and horizontal rectangles?

Have you thought to try bwdist to find the largest rectangle that can fit in an arbitrary shape?

What is your use case? Why do you need to do this splitting up into individual component rectangles? What are you going to do with the matrix once it's accomplished?

Answer 2

[Umar]

Hi @Pete sherer,

To enhance your existing code for merging boxes more efficiently, you can consider a more sophisticated approach. Below is an updated version of your code with an added heuristic method that attempts to minimize the number of resulting boxes while preserving their uniformity.

function [boxNewMask] = optimizeBoxMerging(boxGrid)
  [rows, cols] = size(boxGrid);
  visited = false(rows, cols);  % Track visited cells
  boxNewMask = zeros(rows, cols);  % Initialize new box mask
  grpLabel = 0;  % Group label initialization

    % Iterate through each cell in the grid
    for iRow = 1:rows
        for jCol = 1:cols
            if boxGrid(iRow, jCol) == 1 && ~visited(iRow, jCol)
                grpLabel = grpLabel + 1;
                % Merge boxes using a breadth-first search (BFS) approach
                [height, width] = mergeBoxes(boxGrid, visited, iRow, jCol);

                % Mark the merged area as visited
                idxRow = iRow:iRow+height-1;
                idxCol = jCol:jCol+width-1;
                boxNewMask(idxRow, idxCol) = grpLabel;
                visited(idxRow, idxCol) = true;
            end
        end
    end
  end

function [height, width] = mergeBoxes(boxGrid, visited, startRow, startCol)
  [rows, cols] = size(boxGrid);

    % Initialize dimensions
    height = 0;
    width = 0;

    % Find maximum width
    for col = startCol:cols
        if boxGrid(startRow, col) == 1 && ~visited(startRow, col)
            width = width + 1;
        else
            break;
        end
    end

    % Find maximum height while maintaining width
    for row = startRow:rows
        if all(boxGrid(row, startCol:startCol+width-1) == 1) && ...
           all(~visited(row, startCol:startCol+width-1))
            height = height + 1;
        else
            break;
        end
    end

    % Optional improvement: Attempt to expand horizontally if possible 
    for extraWidth = 1:min(width, cols - (startCol + width))
        if all(boxGrid(startRow:startRow+height-1, startCol + extraWidth) == 1)
            width = width + 1; % Expand width if possible
        else
            break;
        end
    end  
  end

% Example usage:
boxGrid = [1 1 0 0 1; 
         1 1 0 1 1; 
         0 0 0 1 1; 
         1 0 0 0 0]; % Your original grid here.
boxNewMask = optimizeBoxMerging(boxGrid);
disp(boxNewMask);

Please see attached.

A new function mergeBoxes is created to find and merge contiguous boxes more effectively. This function includes logic to expand horizontally where possible. The merging process is structured to resemble Breadth First Search (BFS). This method allows exploring all potential expansions of a box before marking it as merged. As mentioned in the comments you received, considering heuristics or algorithms like genetic algorithms or simulated annealing could provide better solutions for larger datasets.

This updated implementation should give you a good starting point toward achieving your goal of minimizing the number of boxes while still accurately reflecting their positions in the grid.

If you have specific scenarios or datasets you'd like to test against this code further, please let me know!

Answer 3

[Image Analyst]

How about just using the convex hull?

boxGrid= [...
    0   0   0   1   1   0   0   0   0   0   0   0   0   1   1   0   0   0
    0   0   1   1   1   1   1   0   0   0   0   0   0   1   1   1   0   0
    0   0   0   1   1   1   1   1   0   0   0   0   0   0   0   0   0   0
    0   0   0   0   0   1   1   1   0   0   0   0   0   0   0   0   0   0
    0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0
    0   1   1   1   0   0   1   0   0   0   1   0   0   0   0   0   0   0
    1   1   1   1   1   1   1   1   0   1   1   1   1   1   0   0   0   0
    0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   0   0   0
    0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   0   0
    0   0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   0
    0   0   0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
    0   0   0   0   1   1   1   1   1   1   1   1   1   1   1   1   1   1
    0   0   0   0   0   0   1   1   1   1   1   1   1   1   1   1   1   0
    0   0   0   0   0   0   0   0   1   0   0   0   0   1   1   1   0   0];
subplot(2, 1, 1);
imshow(boxGrid, []);
output = bwconvhull(boxGrid);
subplot(2, 1, 2);
imshow(output, []);

Or you could use regionprops to get the bounding box of that so the output is just one large rectangle.