22 November, 2013

Find the biggest empty box: example of two dimensional convolution

  • How can I find the biggest empty box in a matrix?
  • Can you show me an example on two dimensional convolution through a MATLAB Cody problem?
  • What algorithms can be used to solve MATLAB Cody problem #658?

ASEE Challenge problem set in MATLAB Cody consists of really challenging tasks needing more complex way of thinking. These problems are worth to have the effort to solve them.

One of the favourites is Find the biggest empty box:

You are given a matrix that contains only ones and zeros. Think of the ones as columns in an otherwise empty floor plan. You want to fit a big square into the empty space (denoted by zeros). What is the largest empty square sub-matrix you can find in the given matrix? You will return the row and column extent of the sub-matrix. The answer may not be unique. We will test that your sub-matrix is square, that it is empty, and that it contains the correct number of elements.

An example input and output pair:

a = [1 0 0;
0 0 0;
0 0 0] s = [2 3 2 3]

The skeleton of the function is:

function [r1, r2, c1, c2] = biggest_box(a)
  r1 = 1;
  r2 = 1;
  c1 = 1;
  c2 = 1;
end

That means that we have to return the indices of the first and last row and the first and last column of the sub-matrix respectively.

The straightforward solution

The straightforward solution is to try all possible squares to all possible positions.

  • We start with a square having same size as the input: this can be positioned only to the top-left corner.
  • If there is a one value in the square, we suppose a smaller sub-matrix, and put it to all possible positions again.
  • We repeat these steps, until we find a square fitting our needs having no one value in it.
  • Once we have found it, we can return it immediately, since we started from the maximal size and we are counting down: this way the first solution will be the best. For example if we have found a good sub-matrix having size of five, there is no need to search an other four-by-four square.

A code example doing the algorithm described above is the following:

function [r1, r2, c1, c2] = biggest_box(A)
% get the size (s) of the input square
s = length(A);

% loop through all possible square sizes (n) and positions (r1, c1)
for n = s - 1 : -1 : 0 
  for r1 = 1 : s - n
    for c1 = 1 : s - n
      % calculate the position of the lower-right corner
      r2 = r1 + n;
      c2 = c1 + n;
      % return if the summary in the current square is zero
      if sum(sum(A(r1 : r2, c1 : c2))) == 0
        return
      end
    end
  end
end
end

The most outer loop is for decreasing the square-size, while the inner ones are for the positioning. In each iteration the indices are recalculated: if the summary in the current square is zero, we return the coordinates and finish running.

The indexing is a bit complex, but drawing it on piece of paper can help a lot. Maybe this line can be the most confusing:

for n = s - 1 : -1 : 0

Why is this used instead of:

for n = s : -1 : 1

There are two reasons of it:

  • Suppose that the input is a four-by-four matrix. We want to get the indices of the lower-right corner of a sub-matrix having size of four placed on the top-left corner on the input. The index of its last row can not be simply 1 + 4 = 5, because this would cause overindexing, but it should be 1 + (4 - 1) = 4.
  • Suppose that the input is a four-by-four matrix. We have a sub-matrix having size of two, and we want to calculate the maxima of the possible row positions of its top-left corner. It can not be simply 4 - 2 = 2, because a two-by-two sub-matrix can be put onto the third row too, so it should be 4 - (2 - 1) = 3.

In both cases we have to calculate by the actual square size minus one. If the substraction is done it the for cycle already, it will make our life easier.

For more better understanding here is a debug variation of the skeleton of the program. In each iteration matrix D of zeros is created, while the current square is marked by ones:

function [r1, r2, c1, c2] = biggest_box_debug(A)
s = length(A);
for n = s - 1 : -1 : 0 
  for r1 = 1 : s - n
    for c1 = 1 : s - n
      r2 = r1 + n;
      c2 = c1 + n;
      D = zeros(s);
D(r1 : r2, c1 : c2) = 1 end end end end biggest_box_debug(zeros(4))

A part of the output is:

D =
   1   1   1   1
   1   1   1   1
   1   1   1   1
   1   1   1   1
D =
   1   1   1   0
   1   1   1   0
   1   1   1   0
   0   0   0   0
D =
   0   1   1   1
   0   1   1   1
   0   1   1   1
   0   0   0   0
D =
   0   0   0   0
   1   1   1   0
   1   1   1   0
   1   1   1   0
D =
   0   0   0   0
   0   1   1   1
   0   1   1   1
   0   1   1   1
D =
   1   1   0   0
   1   1   0   0
   0   0   0   0
   0   0   0   0
D =
   0   1   1   0
   0   1   1   0
   0   0   0   0
   0   0   0   0
D =
   0   0   1   1
   0   0   1   1
   0   0   0   0
   0   0   0   0
D =
   0   0   0   0
   1   1   0   0
   1   1   0   0
   0   0   0   0
D =
   0   0   0   0
   0   1   1   0
   0   1   1   0
   0   0   0   0
...

As you can see, the size of the supposed square is decreasing and is put to all possible positions. Here comes the trick: this operation is exactly the same as two dimensional convolution. A window is slid along the input matrix, and the elements in it are examined. If you are not familiar with this operation, please read the tutorial on it.

A solution using convolution

The basic idea to solve this task by two dimensional convolution is the following: if we convolve the input by an n-by-n square of ones, and there is any zero value in the result, it means that there is an n-by-n block containing only zeros.

The algorithm is the following:

  • Suppose the maximal possible square size and convolve the input by this square of ones.
  • If there is any point, where the result of the convolution is zero, it means that we have found an appropriate block, so we only have to calculate its coordinates and return.
  • If there is no point in the output having zero value, decrease the supposed square size, and do the convolution again.

The only remaining question is: how to calculate the coordinates of the resulting block? Suppose a four-by-four input matrix convolved by a three-by-three square. Do the convolution only for those elements, where the convolving window is fully covered. See the following code example below:

% the input matrix
A = [1 1 0 1;
     0 0 0 0;
     0 0 0 0;
     0 0 0 1];

% do convolution for those elements where the window is fully covered
B = conv2(A, ones(3), 'valid')

The output is:

B =
   2   2
   0   1

To explain this result a bit more, please have a look the following figure, which demonstrates the valid positions of the window during convolution:

1 1 0 1      1 1 0 1      1 1 0 1      1 1 0 1      1 1 0 1      
0 0 0 0      0 0 0 0      0 0 0 0      0 0 0 0      0 0 0 0      2 2
0 0 0 0      0 0 0 0      0 0 0 0      0 0 0 0      0 0 0 0      0 1
0 0 0 1      0 0 0 1      0 0 0 1      0 0 0 1      0 0 0 1      

As it can be seen, the position of the elements in the output equals to the position of the upper-left corner of its generator window. This way the position of the found zero value equals to the upper-left corner of the needed block.

The full, commented MATLAB code example of this approach:

function [r1, r2, c1, c2] = biggest_box(A)
% start from the maximal possible size for n = length(A) : -1 : 1
% doing convolution for valid values R = conv2(A, ones(n), 'valid');

% coordinates of the first zero [r1, c1] = find(R == 0, 1);

% if the resulting coordinate is not empty: there is an appropriate box if r1
% coordinates of the lower-right corner r2 = r1 + n - 1; c2 = c1 + n - 1;
% return: we do not need to continue searching return; end end

This code is not fully optimized to help understanding and keep its simplicity for being a good demonstration on two dimensional convolution.

         

New comment

comments powered by Disqus