Maximum size squares sub-matrixe with all zeros (having the same diagonal of the mother matrix )

5 views (last 30 days)
Hello,
I have a matrix of M-by-M full that contains only zeros and ones. As shown in the image, the violet suqares corresponds to 0 and the yellow squares corresponds to 1. I would like to create an algorithm that detects the squares highlited in red (the 4 cordinates of the square). In other words the squares that have the same diagonal of the matrix and all the values inside the square are equal to 0 (just violet cell).
Does anyone have an dea how to start this?
Thank you in advance,
  4 Comments
Image Analyst
Image Analyst on 25 Feb 2020
I'm thinking you can do this by calling bwdist() to get the distance transform, then calling imregionalmax() to find peaks that lie along the diagonal. Please help us help you by attaching the binary image/matrix in a .mat file.

Sign in to comment.

Accepted Answer

Jon
Jon on 17 Feb 2020
Edited: Jon on 18 Feb 2020
I think this may be do what you want, or if not is close enough that you can modify it from here.
The function emptyBoxes returns an a number of empty boxes by 2 array, boxes, with the first column giving the upper left corner index, and the second column giving the width (or height they are equal) of the empty box.
You can compute the x and y coordinates for the kth box corners using:
x = [boxes(k,1), boxes(k,1)+boxes(k,2), boxes(k,1), boxes(k,1)+boxes(k,2)]
y = [boxes(k,1), boxes(k,1),boxes(k,1)+boxes(k,2), boxes(k,1)+boxes(k,2)]
If performance were crucial, the code could certainly be further optimized, to avoid searching over boxes areas that are already known to be empty, but I wanted to just keep it as simple as possible to start.
function boxes = emptyBoxes(A)
% find all the emptyBoxes along main diagonal of square matrix A
% preallocate array to hold results
boxes = zeros(size(A,1),2);
prevBox = [1 0];
numBoxes = 0;
for k = 1:size(A,1)
% find max box size for box with upper left corner on current position
% k along main diagonal
n = maxbox(A(k:end,k:end));
% check if this box fits inside current box
if k + (n-1) > prevBox(1) + prevBox(2)
% this box doesn't nest inside previous one
% add it to list
numBoxes = numBoxes + 1;
boxes(numBoxes,:) = [k,n-1];
prevBox = boxes(numBoxes,:);
end
end
% just return the used portion of boxes
boxes = boxes(1:numBoxes,:);
function n = maxbox(A)
% find largest square with upper left corner at A(1,1),that has no true elements
% n is the number of elements on a side of the square
k = 1;
n = size(A,1); % initally assume maximum size box
stillEmpty = true;
while k <= size(A,1) && stillEmpty
if any(A(1:k,1:k),'all')
stillEmpty = false;
n = k - 1;
end
k = k + 1;
end
  11 Comments
Jon
Jon on 26 Feb 2020
Edited: Jon on 26 Feb 2020
When I load your 49 by 49 logical matrix H from the attached file and run
boxes = emptyBoxes(H)
I get
>> boxes =
1 1
2 15
16 5
17 6
23 6
30 0
31 18
So there are 7 empty squares with their upper left corners located on the following elements of the main diagonal 1,2,16 17,23 30 and 31 (first column of boxes) and the corresponding "width/height" of the squares is 1,15,5,6,6,0,18
So for example the second square, with boxes(2,1) = 2 and boxes(2,2) = 15, using the formula I gave you earlier, with k = 2
x = [boxes(k,1), boxes(k,1)+boxes(k,2), boxes(k,1), boxes(k,1)+boxes(k,2)]
y = [boxes(k,1), boxes(k,1),boxes(k,1)+boxes(k,2), boxes(k,1)+boxes(k,2)]
Gives a box with coordinates
x =
2 17 2 17
y =
2 2 17 17
I think this is doing what you want, but maybe I am still missing something.
Note that my definition of the box width/height, second column of the boxes array returned by emptyBoxes may be a little confusing. It is one less than the side length, of the box you would draw. Use the formulas above to compute the coordinates of the squares you would actually draw.

Sign in to comment.

More Answers (1)

Image Analyst
Image Analyst on 26 Feb 2020
Here's a start. Sounds like homework maybe so I'll let you finish it:
clc;
clearvars;
close all;
workspace;
fontSize = 16;
fileName = 'd3urban_Hmatrix_T106_F6_slidingBalt.mat';
s = load(fileName)
h = s.H;
whos h
% Display the image.
subplot(2, 2, 1);
imshow(h)
title('Original Logical Image', 'FontSize', fontSize);
% Get the distance transform
edtImage = bwdist(h);
% Display the image.
subplot(2, 2, 2);
imshow(edtImage, [])
title('Distance Transform Image', 'FontSize', fontSize);
hp = impixelinfo();
% Get the regional maxima of the distance transform
rMax = imregionalmax(edtImage);
% Display the image.
subplot(2, 2, 3);
imshow(rMax, [])
title('Regional Maxima', 'FontSize', fontSize);
% Erase maxima off the main diagonal from upper left to lower right.
diagonalMask = eye(size(h, 1));
rMax(~diagonalMask) = 0;
% Display the image.
subplot(2, 2, 3);
imshow(rMax, [])
title('Regional Maxima', 'FontSize', fontSize);
% Find out where they are
[rows, columns] = find(rMax)
% Find the size of the box at each location
for k = 1 : length(rows)
fprintf('Box radius at (row, column) = (%d, %d) = %.2f.\n',...
rows(k), columns(k), edtImage(rows(k), columns(k)));
end
% The original image has them subsampled away when it shrinks down for display.
% Plot bigger so we can see them.
hold on;
for k = 1 : length(rows)
plot(columns(k), rows(k), 'r.', 'MarkerSize', 20);
end
  5 Comments
yusra Ch
yusra Ch on 27 Feb 2020
Thank you so much for you help. I would like to accept your answer. Unfortunetly matlab gives it only 1 time :/
Image Analyst
Image Analyst on 27 Feb 2020
You can still "Vote" for my answer if you'd like to award me "Reputation points" as a thank you. ? Thanks in advance.

Sign in to comment.

Categories

Find more on Resizing and Reshaping Matrices in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!