Steve on Image Processing and MATLAB

Concepts, algorithms & MATLAB

This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the Original version of the page.

Comparing the geometries of bwboundaries and poly2mask 5

Posted by Steve Eddins,

MATLAB user Meshooo asked a question on MATLAB Answers about a problem with the createMask function associated with impoly. Meshooo observed a discrepancy between the output of bwboundaries and the mask created by createMask.

I want to describe the issue in more general terms here as a conflict between the geometry of the bwboundaries function and the geometry of the poly2mask function (which is used by createMask).

Here's a simple example that illustrates the discrepancy. Start by creating a small binary image.

BW = [ ...
    0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0
    0 0 0 0 1 1 1 0 0
    0 0 1 1 1 1 1 0 0
    0 0 1 1 1 1 1 0 0
    0 0 1 1 1 1 1 0 0
    0 0 1 1 1 1 1 0 0
    0 0 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 ];

Call bwboundaries, which traces the perimeter pixels of all the objects (and holes) in the image.

B = bwboundaries(BW);

There's only one boundary in this case. Extract and plot it.

B = B{1};
Bx = B(:,2);
By = B(:,1);
plot(Bx,By)
axis ij
axis equal
axis([.5 9.5 .5 10.5])

If we now pass Bx and By to poly2mask, we don't get exactly the same binary mask image that we started with.

BW2 = poly2mask(Bx,By,10,9)
BW2 =

     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     1     0     0
     0     0     0     1     1     1     1     0     0
     0     0     0     1     1     1     1     0     0
     0     0     0     1     1     1     1     0     0
     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

To understand the reason for the discrepancy, it helps to understand that bwboundaries treats the foreground pixels of the input image as points in space. Here's a plot to illustrate:

plot(Bx,By)
axis ij
axis equal
axis([.5 9.5 .5 10.5])
hold on
[yy,xx] = find(BW);
plot(xx,yy,'*')
hold off
legend('Boundary polygon','Foreground pixels')

Now let's do a plot that shows the pixels as squares of unit area. I'll include some code to overlay the pixel edges as gray lines.

imshow(BW,'InitialMagnification','fit')
hold on

x = [.5 9.5];
for k = .5:10.5
    y = [k k];
    plot(x,y,'Color',[.7 .7 .7]);
end

y = [.5 10.5];
for k = .5:9.5
    x = [k k];
    plot(x,y,'Color',[.7 .7 .7]);
end

plot(Bx,By,'r')

plot(xx,yy,'*')
hold off

Now you can see that the polygon produced by bwboundaries does not completely contain the pixels along the border of the object. In fact, most of those pixels are only half inside the polygon (or less).

That's the clue needed to explain the discrepancy with poly2mask. That function treats images pixels not as points, but as squares having unit area. Its algorithm is carefully designed to treat partially covered pixels in a geometrically consistent way. I wrote several blog posts (POLY2MASK and ROIPOLY Part 1, Part 2, and Part 3) about this back in 2006. Here's a diagram from Part 3 that illustrates a bit of the algorithm for handling partially covered pixels.

It turns out that there is a way to get boundary polygons from bwboundaries that are consistent with the poly2mask geometry. The idea is to upsample the binary image so that the polygon produced by bwboundaries is outside the pixel centers instead of running directly through the centers.

BW3 = imresize(BW,3,'nearest');
B3 = bwboundaries(BW3);
B3 = B3{1};

Now shift and scale the polygon coordinates back into the coordinate system of the original image.

Bx = (B3(:,2) + 1)/3;
By = (B3(:,1) + 1)/3;

imshow(BW,'InitialMagnification','fit')
hold on

x = [.5 9.5];
for k = .5:10.5
    y = [k k];
    plot(x,y,'Color',[.7 .7 .7]);
end

y = [.5 10.5];
for k = .5:9.5
    x = [k k];
    plot(x,y,'Color',[.7 .7 .7]);
end

plot(Bx,By,'r')

plot(xx,yy,'*')
hold off

You can see that the pixel centers are now clearly inside the modified polygon (Bx,By). That means that when we try poly2mask again, we'll get the same mask as the original image.

BWout = poly2mask(Bx,By,10,9)
BWout =

     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0
     0     0     0     0     1     1     1     0     0
     0     0     1     1     1     1     1     0     0
     0     0     1     1     1     1     1     0     0
     0     0     1     1     1     1     1     0     0
     0     0     1     1     1     1     1     0     0
     0     0     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

isequal(BW,BWout)
ans =

     1

To everyone in the Northern Hemisphere: Happy Spring!


Get the MATLAB code

Published with MATLAB® R2014a

Note

Comments are closed.

5 CommentsOldest to Newest

Meshoo replied on : 1 of 5
Thank you Steve. I added one more example here after your correction that works very well: https://www.mathworks.com/matlabcentral/answers/122981-serious-problem-with-createmask-function
Sven replied on : 2 of 5
Hi Steve, someone recently wanted to use bwboundaries and poly2mask as a kind of conversion. This works fine (with the caveats you pointed out in this post) when there are no holes in your BW image. However, if there are holes then bwboundaries can produce fully descriptive output (ie, it gives inner and outer boundaries along with their nesting in the extra output arguments), but poly2mask only takes a single outline at a time. I was considering making a function that extends poly2mask such that it can accept those extra bwboundaries outputs and try to recreate a fully "holed" mask via looped binary unions and subtractions. Any thoughts on the "best" way to approach this problem?
Sven replied on : 3 of 5
Righto, I've got something that faithfully reproduces a mask in terms of its topology (including the enclosed/enclosing regions). I think I'll package it up with some nice input handling (including the option to use your resample trick above for exact pixel recovery) and add it to the FEX.
BW = imread('blobs.png');
[B,L,N,A] = bwboundaries(BW);

[m,n] = size(BW);
newBW = false([m,n]);

% Start with any enclosing boundaries not enclosed by others
[rr,~] = find(A);
listToAdd = false(1,length(B));
listToAdd(setdiff(1:length(B),rr)) = true;
while any(listToAdd)
    % Add the next enclosing mask
    nextAdd = find(listToAdd,1);
    newBW = newBW | poly2mask(B{nextAdd}(:,2),B{nextAdd}(:,1),m,n);
    listToAdd(nextAdd) = false;
    % Subtract any enclosed masks (and then add their children)
    for nextSub = find(A(:,nextAdd))'
        newBW = newBW & ~poly2mask(B{nextSub}(:,2),B{nextSub}(:,1),m,n);
        % Add any children 
        listToAdd(A(:,nextSub)) = true;
    end
end
Sven replied on : 4 of 5
Hi Steve, I've just added mpoly2mask to the file exchange: https://www.mathworks.com/matlabcentral/fileexchange/46428-mpoly2mask-convert-multiple-polygons-to-a-mask Any thoughts? I went with combining X and Y into XY as it seemed to simplify the input and remove ambiguity from optional inputs. I also went with the enclosing/enclosed style association matrix as per the output from bwboundaries. I think this is the most flexible, although it may not be immediately intuitive for setting up a hierarchy (although I doubt any particular syntax would be, except maybe some kind of string input such as '(1 | 4) & 3 & ~2' which would then need to be parsed by the mpoly2mask function.
Steve Eddins replied on : 5 of 5
Sven—That's a very nice contribution to the File Exchange, thanks! There's not an easy answer to the "X, Y" versus "XY" question. For functions in our shipping products, we try hard to design syntaxes that support both styles unambiguously because neither style is perfectly convenient for all use cases. But for my own work that isn't in a product, I don't think too hard about it.