# A Cody problem: simplify a polygon7

Posted by Steve Eddins,

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:

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.

Cris Luengo replied on : 2 of 7

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.

Sven replied on : 4 of 7

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*

Richard Brown replied on : 5 of 7

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.

These postings are the author's and don't necessarily represent the opinions of MathWorks.