{"id":393,"date":"2011-10-04T22:07:16","date_gmt":"2011-10-05T02:07:16","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2011\/10\/04\/binary-image-convex-hull-algorithm-notes\/"},"modified":"2019-10-29T16:57:27","modified_gmt":"2019-10-29T20:57:27","slug":"binary-image-convex-hull-algorithm-notes","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2011\/10\/04\/binary-image-convex-hull-algorithm-notes\/","title":{"rendered":"Binary image convex hull – algorithm notes"},"content":{"rendered":"
\r\n

Today I want to tell a little image processing algorithm story related to my post last week<\/a> about the new bwconvhull<\/tt><\/a> function in the Image Processing Toolbox.\r\n <\/p>\r\n

The developer (Brendan<\/a>) who worked on this function came to see me sometime last year to find out how the 'ConvexImage' measurement offered by regionprops<\/tt><\/a> was computed so that he could use the same procedure for bwconvhull<\/tt>. I believed that I knew the answer off the top of my head, so without looking at the code I rattled off the following steps:\r\n <\/p>\r\n

\r\n
    \r\n
  1. Compute the x- and y-coordinates for the four corners of all the foreground pixels in the binary image.<\/li>\r\n
  2. Use convhull<\/tt><\/a> to compute the convex hull of the (x,y) pairs from step 1.\r\n <\/li>\r\n
  3. Use poly2mask<\/tt><\/a> to convert the convex hull polygon to a binary image mask.\r\n <\/li>\r\n <\/ol>\r\n <\/div>\r\n

    A few days later Brendan came back to tell me that, although my description was clear, the code that I wrote ten years ago\r\n for regionprops<\/tt> actually does something else.\r\n <\/p>\r\n

    Oops.<\/p>\r\n

    I looked at the code and realized that Brendan was right, and I started to remember that I had actually made this same mistake\r\n many years before.\r\n <\/p>\r\n

    In fact, I did originally implement 'ConvexImage' in regionprops<\/tt> using the procedure outlined above. Before it shipped, though, I discovered (and fixed) a big problem with it.\r\n <\/p>\r\n

    Let me show you the problem using a small example. Here's a tiny binary image.<\/p>

    bw = [...<\/span>\r\n    0 0 0 0 0 0 0 0 0\r\n    0 0 0 0 1 0 0 0 0\r\n    0 0 0 1 0 1 0 0 0\r\n    0 0 1 0 0 0 1 0 0\r\n    0 1 0 0 0 0 0 1 0\r\n    0 0 0 0 0 0 0 0 0 ];\r\nimshow(bw, 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
    Now here's the convex image as computed by bwconvhull<\/tt>. The \"filled-in\" pixels are shown in light gray.\r\n   <\/p>
    bwch = bwconvhull(bw)\r\nhold on<\/span>\r\nh = imshow(bwch);\r\nset(h, 'AlphaData'<\/span>, 0.8);\r\nhold off<\/span><\/pre>
    \r\nbwch =\r\n\r\n     0     0     0     0     0     0     0     0     0\r\n     0     0     0     0     1     0     0     0     0\r\n     0     0     0     1     1     1     0     0     0\r\n     0     0     1     1     1     1     1     0     0\r\n     0     1     1     1     1     1     1     1     0\r\n     0     0     0     0     0     0     0     0     0\r\n\r\n<\/pre> 
    Now I'll graphically illustrate the computational procedure above. First, compute the set of corner locations for all the\r\n      foreground pixels.\r\n   <\/p>
    [y,x] = find(bw);\r\ndx = [-0.5 -0.5  0.5  0.5];\r\ndy = [-0.5  0.5 -0.5  0.5];\r\nx_corners = bsxfun(@plus, x, dx);\r\ny_corners = bsxfun(@plus, y, dy);\r\nx_corners = x_corners(:);\r\ny_corners = y_corners(:);<\/pre>
    Visualize step 1 by superimposing those corner locations on the input image.<\/p>
    imshow(bw, 'InitialMagnification'<\/span>, 'fit'<\/span>)\r\nhold on<\/span>\r\nplot(x_corners, y_corners, 'og'<\/span>)\r\nhold off<\/span><\/pre> 
    Step 2: Compute the convex hull of all the corner points. Visualize by superimposing the convex hull in red.<\/p>
    k = convhull(x_corners, y_corners);\r\nx_hull = x_corners(k);\r\ny_hull = y_corners(k);\r\nhold on<\/span>\r\nplot(x_hull, y_hull, 'r'<\/span>, 'LineWidth'<\/span>, 4)\r\nhold off<\/span><\/pre> 
    Step 3: Use poly2mask<\/tt> to convert the convex hull to a binary image mask.\r\n   <\/p>
    mask = poly2mask(x_hull, y_hull, 6, 9);\r\n\r\nimshow(bw, 'InitialMagnification'<\/span>, 'fit'<\/span>)\r\nhold on<\/span>\r\nh = imshow(mask);\r\nset(h, 'AlphaData'<\/span>, 0.8)\r\nplot(x_hull, y_hull, 'r'<\/span>, 'LineWidth'<\/span>, 4)\r\nhold off<\/span><\/pre> 
    You can see that there are extra pixels along the diagonal edges that got put into the mask. That's not good. If you repeat\r\n      the operation, those diagonals will keep filling out until you're left with a rectangle. That's not supposed to happen with\r\n      repeated application of the convex hull.\r\n   <\/p>\r\n   
    The solution that I settled on ten years ago, and which is now also used in bwconvhull<\/tt>, was to modify the first step of the procedure. Instead of collecting the set of corner<\/b> points of each foreground pixel, the correct procedure collects points along the center of each edge of each foreground pixel.\r\n   <\/p>\r\n   
    Here's what that looks like.<\/p>
    dx = [0.0  0.0  0.5 -0.5];\r\ndy = [0.5 -0.5  0.0  0.0];\r\nx_edges = bsxfun(@plus, x, dx);\r\ny_edges = bsxfun(@plus, y, dy);\r\nx_edges = x_edges(:);\r\ny_edges = y_edges(:);\r\n\r\nk = convhull(x_edges, y_edges);\r\nx_hull = x_edges(k);\r\ny_hull = y_edges(k);\r\n\r\nimshow(bw, 'InitialMagnification'<\/span>, 'fit'<\/span>)\r\nhold on<\/span>\r\nplot(x_edges, y_edges, 'og'<\/span>)\r\nplot(x_hull, y_hull, 'r'<\/span>, 'LineWidth'<\/span>, 4)\r\nhold off<\/span><\/pre> 
    mask = poly2mask(x_hull, y_hull, 6, 9);\r\nimshow(mask, 'InitialMagnification'<\/span>, 'fit'<\/span>)\r\nhold on<\/span>\r\nplot(x_hull, y_hull, 'r'<\/span>, 'LineWidth'<\/span>, 4)\r\nplot(x_edges, y_edges, 'og'<\/span>)\r\nhold off<\/span><\/pre> 
    Much better!<\/p>\r\n   
    I have been fooled more often than I would like to admit by sometimes nonintuitive digital image geometry. For you image processing\r\n      algorithm people out there, I hope seeing these pictures and techniques will help you avoid similar pitfalls someday.\r\n   <\/p>
    The reason this is happening is that the convex hull goes exactly through the center of pixels that are along the diagonal\r\n      but \"outside\" the original set of foreground pixels. Because of the tie-breaking rules applied by poly2mask<\/tt><\/a>, all (in this case) of those outside pixels got included in the output mask.\r\n   <\/p>\r\n