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

matrix manipulation

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,

Best Answer

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
Related Question