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

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,

[darova]

Are square highlighted in green correct?

[yusra Ch]

The green squares are not correct. I only need to detect the squares highlighted in red (include only violet cells) as they share the same diagonal (highlighted in green)

[Image Analyst]

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.

[yusra Ch]

Please find attach the matrix.

Answer 1

[Jon]

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

[Jon]

I just wanted to check back with you on this. Were you able to try this approach? Did it work for you?

[darova]

I want to know if this works

[yusra Ch]

Hello Jon and Drova, Thank you so much for helping me. Actually I still didn't test it yet due to exams. Once I will finish with them I will be back to this and give you my feedback. Many thanks.

[yusra Ch]

Hi Jon

I have tested the code you posted. It return this error for both codes. The matrix of my data is a double M-by-M that contains only zeros and ones which I have represented above in violet, yellow, respectively.

 Error using any Dimension argument must be a positive integer scalar within indexing range.

Error in maxbox (line 8)
    if any(A(1:k,1:k),'all')

[Jon]

Here is an example test script. I also give it an M by M double array of zeros and ones but don't get any error.

If you keep getting the error, please attach your test code.

% script to test empty boxes
A = rand(10)>0.95 % random logical array of trues and false
boxes = emptyBoxes(A)

% also works if A is a double
A = double(A)
boxes = emptyBoxes(A)

[Jon]

I think you may be running an earlier version of MATLAB where the any function does not accept the 'all' argument.

Note from documentation of the any function:

B = any(A,'all') tests over all elements of A. This syntax is valid for MATLAB® versions R2018b and later.

I have modified the code so that this won't be a problem, please use the function below instead

function n = maxbox(A,nMin)
% 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
% optional argument nMin, provides a starting value for n
% and can be used if it is already known that a square with n-1 elements on
% its side is empty (all false);

% set defaults
if nargin < 2
    nMin = 1;
end
k  = nMin;
n = size(A,1); % initally assume maximum size box
stillEmpty = true;
while k <= size(A,1) && stillEmpty
    Ab = A(1:k,1:k);
    if any(Ab(:))
        stillEmpty = false;
        n = k - 1;
    end
    k = k + 1;
end

[yusra Ch]

Thank you so much for helping me. This oneworks on my matlabR2017a it returns the cordination of the bottom right corner of the biggest square that contains only zeros and start from (1,1) .

This answer is correct but I still have other squares to determine. The ones that are highlited in red. In other words, the square sub-matrix that have the same diagonal of the mother matrix and where the values inside the sub-matrix are equal to 0 (violet).

[Jon]

I'm thinking that maybe you are only running the maxBox function, you should run the emptyBoxes function on your test matrx. Note emptyBoxes repeatedly calls the maxBox function.

[yusra Ch]

Now it works and it gives the values of the corners but not the maximum squares. The first maximun square is H(1:167,1:167) but emptyBox function return H(1:166,1:166). Try to run the code with the .mat I have attached before and you will see.

I have attached an other example of the matrix (this time is smaller so it runs faster) you can check it for the test.

[Jon]

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.

[yusra Ch]

Now I understand your answer. Thank you so much for helping me Jon, I really appreciate that.

Answer 2

[Image Analyst]

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

[yusra Ch]

Sorry, I have try you code with the small matrix I have uploaded above in Jon's comment. The code returns

Box radius at (row, column) = (1, 1) = 2.00.

Box radius at (row, column) = (9, 9) = 8.25.

Box radius at (row, column) = (20, 20) = 4.47.

Box radius at (row, column) = (26, 26) = 4.00.

Box radius at (row, column) = (49, 49) = 23.54.

I understand that the cordinates refers to cordinates of the lower right corner of the square. But How can the raduis be 8.25 , 4.47 , 23.54 ...?

[yusra Ch]

By the way it is not a homework, I an testing an hypothesis for my investigation

[Image Analyst]

The radius is along the diagonal so it's always a multiple of sqrt(2). You'd need to divide by sqrt(2) to get the half width then double the half width to get the full width.

[yusra Ch]

Thank you so much for you help. I would like to accept your answer. Unfortunetly matlab gives it only 1 time :/

[Image Analyst]

You can still "Vote" for my answer if you'd like to award me "Reputation points" as a thank you. ? Thanks in advance.