{"id":639,"date":"2012-07-09T15:02:29","date_gmt":"2012-07-09T19:02:29","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=639"},"modified":"2019-10-31T14:51:53","modified_gmt":"2019-10-31T18:51:53","slug":"a-cody-problem-simplify-a-polygon","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2012\/07\/09\/a-cody-problem-simplify-a-polygon\/","title":{"rendered":"A Cody problem: simplify a polygon"},"content":{"rendered":"

Today I'm combining my blog post with a new problem submission<\/a> on Cody<\/a>. The problem is related to the function bwboundaries<\/tt> 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.<\/p>

Here's an example from the documentation:<\/p>

I = imread('rice.png'<\/span>);\r\nBW = im2bw(I, graythresh(I));\r\n[B,L] = bwboundaries(BW,'noholes'<\/span>);\r\nimshow(label2rgb(L, @jet, [.5 .5 .5]))\r\nhold on<\/span>\r\nfor<\/span> k = 1:length(B)\r\n    boundary = B{k};\r\n    plot(boundary(:,2), boundary(:,1), 'w'<\/span>, 'LineWidth'<\/span>, 2)\r\nend<\/span>\r\nhold off<\/span>\r\n<\/pre>\"\" 
I have heard a few times from customers that they would like to eliminate \"unnecessary vertices\" in the output of bwboundaries<\/tt>. To illustrate, let's look at the boundary for a simple binary image containing a rectangle.<\/p>
close(gcf)\r\nbw = false(15,40);\r\nbw(5:10,10:30) = true;\r\nB = bwboundaries(bw);\r\nboundary = B{1};\r\nimshow(bw,'InitialMagnification'<\/span>, 'fit'<\/span>)\r\nhold on<\/span>\r\nplot(boundary(:,2), boundary(:,1))\r\nplot(boundary(:,2), boundary(:,1), '*'<\/span>)\r\nhold off<\/span>\r\n<\/pre>\"\" 
Note that the boundary goes through the pixel centers, which is why a little bit of white appears outside the boundary line.<\/p>
I can imagine that for some applications it would be nice to have the boundary polygon without as many vertices, like this:<\/p>
x = [10 30 30 10 10];\r\ny = [5 5 10 10 5];\r\nimshow(bw,'InitialMagnification'<\/span>, 'fit'<\/span>)\r\nhold on<\/span>\r\nplot(x, y)\r\nplot(x, y, '*'<\/span>)\r\nhold off<\/span>\r\n<\/pre>\"\" 
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<\/i> you believe in).<\/p>
So I thought I would make a Cody problem<\/a> out of it and see what creative ideas pop up.<\/p>
I encourage you to give the problem<\/a> a try. I'll summarize the results later.<\/p>
Good luck!<\/p>\r\n\r\n
\r\nUPDATE: 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.\r\n<\/em>\r\n<\/p>