Merging uniform boxes into larger ones

2 ビュー (過去 30 日間)
Pete sherer
Pete sherer 2024 年 11 月 11 日
コメント済み: Image Analyst 2024 年 11 月 15 日
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,
  2 件のコメント
Stephen23
Stephen23 2024 年 11 月 11 日
"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
Pete sherer 2024 年 11 月 11 日
Ideally would like to minimize number of boxes.

サインインしてコメントする。

サインインしてこの質問に回答する。

採用された回答

Stephen23
Stephen23 2024 年 11 月 12 日
編集済み: Stephen23 2024 年 11 月 12 日
Ran in:
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>
  2 件のコメント
Pete sherer
Pete sherer 2024 年 11 月 14 日
This one seems to do the job, but definitely can be more optimized.
Image Analyst
Image Analyst 2024 年 11 月 15 日
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?

サインインしてコメントする。

その他の回答 (2 件)

Umar
Umar 2024 年 11 月 12 日

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!

Image Analyst
Image Analyst 2024 年 11 月 12 日
Ran in:
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.

カテゴリ

Help Center および File Exchange で Econometrics Toolbox についてさらに検索

タグ

製品


リリース

R2023b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by