Today I'm combining my blog post with a new problem submission on Cody. The problem is related to the function bwboundaries in the Image Processing Toolbox. This function traces the boundaries of objects (and holes within objects), returning each boundary as a set of x-y vertices.
Here's an example from the documentation:
I = imread('rice.png'); BW = im2bw(I, graythresh(I)); [B,L] = bwboundaries(BW,'noholes'); imshow(label2rgb(L, @jet, [.5 .5 .5])) hold on for k = 1:length(B) boundary = B{k}; plot(boundary(:,2), boundary(:,1), 'w', 'LineWidth', 2) end hold off
I have heard a few times from customers that they would like to eliminate "unnecessary vertices" in the output of bwboundaries. To illustrate, let's look at the boundary for a simple binary image containing a rectangle.
close(gcf)
bw = false(15,40);
bw(5:10,10:30) = true;
B = bwboundaries(bw);
boundary = B{1};
imshow(bw,'InitialMagnification', 'fit')
hold on
plot(boundary(:,2), boundary(:,1))
plot(boundary(:,2), boundary(:,1), '*')
hold off
Note that the boundary goes through the pixel centers, which is why a little bit of white appears outside the boundary line.
I can imagine that for some applications it would be nice to have the boundary polygon without as many vertices, like this:
x = [10 30 30 10 10]; y = [5 5 10 10 5]; imshow(bw,'InitialMagnification', 'fit') hold on plot(x, y) plot(x, y, '*') hold off
This idea has been on my potential blog topics list for a long time, and today I finally got around to thinking about it. I can think of several different approaches, and it's not immediately obvious to me which approach might be best (for whatever definition of best you believe in).
So I thought I would make a Cody problem out of it and see what creative ideas pop up.
I encourage you to give the problem a try. I'll summarize the results later.
Good luck!
UPDATE: In a week or so, I'll a pick the best solution (according to the well-known purple-seven multiphasic optimality criterion) and send out a prize (a hat or something similar) to the solver.
Get
the MATLAB code
Published with MATLAB® 7.14
UPDATE: In a week or so, I’ll a pick the best solution (according to the well-known purple-seven multiphasic optimality criterion) and send out a prize (a hat or something similar) to the solver.
The problem with my solution, even though it passes the tests, is that the first point (and last, which are assumed to be equal) will never be deleted. If this point is in the middle of a straight line, the solution will be wrong. Fixing this somewhat complicates the code.
Cris—Thanks for pointing out a flaw in my test suite. I added a new test case and re-scored all the entries.
Hi Steve, nice little problem :)
Are you sure the test set at the moment is correct?
I’ve got a solution that fails only on the “Two rectangles separated by line segment” test. This test has:
P = [ ...
1 2
1 1
2 1
{snip}
1 4
1 3
1 2];
According to the criteria to “remove as many vertices as possible from P”, I think that the progression from [1 4] to [1 3] to [1 2] to [1 1] can be reduced to just [1 4] to [1 1]. However, you’ve kept [1 2] in the “correct” output… *scratches head quizically*
Hi Steve, there’s a problem in your test suite – problem 7 has a starting vertex that can be deleted, but that isn’t in your solution
i.e. P looks like this:
P = [1 2;
1 1;
\vdots
1 4;
1 3;
1 2 ];
The vertex [1 2] should be removed, but isn’t in your solution …
Sven, Richard—Thanks. I have updated test case #7, and the solutions are being rescored.
I have posted a function on FEX a while ago that solves precisely this kind of problem. You can find it here:
http://www.mathworks.com/matlabcentral/fileexchange/34639-decimate-polygon