Finding islands of ones with zeros boundary

Question

I am trying to find islands of numbers in a matrix. By an island, I mean a rectangular area where ones are connected with each other either horizontally, vertically or diagonally including the boundary layer of zeros

Suppose I have this matrix:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1
0 0 0 1 1 1 0 1 1 0 0 0 1 1 1 1 0
0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1
0 0 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0
0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

By boundary layer, I mean row 2 and 7, and column 3 and 10 for island#1.

This is shown below:

I want the row and column indices of the islands. So for the above matrix, the desired output is:

isl{1}= {[2 3 4 5 6 7];          % row indices of island#1
       [3 4 5 6 7 8 9 10]}       % column indices of island#1

isl{2}= {[2 3 4 5 6 7];          % row indices of island#2
       [12 13 14 15 16 17]};     % column indices of island#2

isl{3} ={[9 10 11 12];           % row indices of island#3
       [2 3 4 5 6 7 8 9 10 11];} % column indices of island#3

It doesn't matter which island is detected first.

While I know that the [r,c] = find(matrix) function can give the row and column indices of ones but I have no clues on how to detect the connected ones since they can be connected in horizontal, vertical and diagonal order. Any ideas on how to deal with this problem?

Answer 1

You should look at the BoundingBox and ConvexHull stats returned by regionprops:

a = imread('circlesBrightDark.png');
bw = a < 100;
s = regionprops('table',bw,'BoundingBox','ConvexHull')

https://www.mathworks.com/help/images/ref/regionprops.html

Answer 2

Finding the connected components and their bounding boxes is the easy part. The more difficult part is merging the bounding boxes into islands.

Bounding Boxes

First the easy part.

function bBoxes = getIslandBoxes(lMap)
   % find bounding box of each candidate island
   % lMap is a logical matrix containing zero or more connected components
   bw = bwlabel(lMap);   % label connected components in logical matrix
   bBoxes = struct2cell(regionprops(bw, 'BoundingBox'));   % get bounding boxes
   bBoxes = cellfun(@round, bBoxes, 'UniformOutput', false);   % round values
end

The values are rounded because the bounding boxes returned by regionprops lies outside its respective component on the grid lines rather than the cell center, and we need integer values to use as subscripts into the matrix. For example, a component that looks like this:

0   0   0
0   1   0
0   0   0

will have a bounding box of

[ 1.5000   1.5000   1.0000   1.0000 ]

which we round to

[ 2  2  1  1]

Merging

Now the hard part. First, the merge condition:

• We merge bounding box b2 into bounding box b1 if b2 and the island of b1 (including the boundary layer) have a non-null intersection.

This condition ensures that bounding boxes are merged when one component is wholly or partially inside the bounding box of another, but it also catches the edge cases when a bounding box is within the zero boundary of another. Once all of the bounding boxes are merged, they are guaranteed to have a boundary of all zeros (or border the edge of the matrix), otherwise the nonzero value in its boundary would have been merged.

Since merging involves deleting the merged bounding box, the loops are done backwards so that we don't end up indexing non-existent array elements.

Unfortunately, making one pass through the array comparing each element to all the others is insufficient to catch all cases. To signal that all of the possible bounding boxes have been merged into islands, we use a flag called anyMerged and loop until we get through one complete iteration without merging anything.

function mBoxes = mergeBoxes(bBoxes)
   % find bounding boxes that intersect, and merge them
   mBoxes = bBoxes;
   % merge bounding boxes that overlap
   anyMerged = true;   % flag to show when we've finished
   while (anyMerged)
      anyMerged = false;   % no boxes merged on this iteration so far...
      for box1 = numel(mBoxes):-1:2
         for box2 = box1-1:-1:1
            % if intersection between bounding boxes is > 0, merge
            % the size of box1 is increased b y 1 on all sides...
            %    this is so that components that lie  within the borders
            %    of another component, but not inside the bounding box,
            %    are merged
            if (rectint(mBoxes{box1} + [-1 -1 2 2], mBoxes{box2}) > 0)
               coords1 = rect2corners(mBoxes{box1});
               coords2 = rect2corners(mBoxes{box2});

               minX = min(coords1(1), coords2(1));
               minY = min(coords1(2), coords2(2));
               maxX = max(coords1(3), coords2(3));
               maxY = max(coords1(4), coords2(4));

               mBoxes{box2} = [minX, minY, maxX-minX+1, maxY-minY+1];   % merge
               mBoxes(box1) = [];   % delete redundant bounding box

               anyMerged = true;   % bounding boxes merged: loop again
               break;
            end
         end
      end
   end
end

The merge function uses a small utility function that converts rectangles with the format [x y width height] to a vector of subscripts for the top-left, bottom-right corners [x1 y1 x2 y2]. (This was actually used in another function to check that an island had a zero border, but as discussed above, this check is unnecessary.)

function corners = rect2corners(rect)
   % change from rect = x, y, width, height
   %       to corners = x1, y1, x2, y2
   corners = [rect(1), ...
              rect(2), ...
              rect(1) + rect(3) - 1, ...
              rect(2) + rect(4) - 1];
end

Output Formatting and Driver Function

The return value from mergeBoxes is a cell array of rectangle objects. If you find this format useful, you can stop here, but it's easy to get to the format requested with ranges of rows and columns for each island:

function rRanges = rect2range(bBoxes, mSize)
   % convert rect = x, y, width, height to
   %        range = y:y+height-1; x:x+width-1
   % and expand range by 1 in all 4 directions to include zero border,
   % making sure to stay within borders of original matrix
   rangeFun = @(rect) {max(rect(2)-1,1):min(rect(2)+rect(4),mSize(1));...
                       max(rect(1)-1,1):min(rect(1)+rect(3),mSize(2))};
   rRanges = cellfun(rangeFun, bBoxes, 'UniformOutput', false);
end

All that's left is a main function to tie all of the others together and we're done.

function theIslands = getIslandRects(m)
   % get rectangle around each component in map
   lMap = logical(m);

   % get the bounding boxes of candidate islands
   bBoxes = getIslandBoxes(lMap);

   % merge bounding boxes that overlap
   bBoxes = mergeBoxes(bBoxes);

   % convert bounding boxes to row/column ranges
   theIslands = rect2range(bBoxes, size(lMap));

end

Here's a run using the sample matrix given in the question:

M =
   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   1   1   0   0   0   0   0   0   0   0   1
   0   0   0   1   1   1   0   1   1   0   0   0   1   1   1   1   0
   0   0   0   0   0   0   1   0   1   0   0   0   0   1   1   1   1
   0   0   0   1   0   1   0   1   1   0   0   0   1   0   0   0   0
   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
   0   0   0   1   0   1   0   1   1   1   0   0   0   0   0   0   0
   0   0   1   0   1   1   1   1   1   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
>> getIslandRects(M)
ans =
{
  [1,1] =
  {
    [1,1] =
        9   10   11   12
    [2,1] =
        2    3    4    5    6    7    8    9   10   11
  }
  [1,2] =
  {
    [1,1] =
       2   3   4   5   6   7
    [2,1] =
        3    4    5    6    7    8    9   10
  }
  [1,3] =
  {
    [1,1] =
       2   3   4   5   6   7
    [2,1] =
       12   13   14   15   16   17
  }
}