{"id":5114,"date":"2014-02-07T09:00:52","date_gmt":"2014-02-07T14:00:52","guid":{"rendered":"https:\/\/blogs.mathworks.com\/pick\/?p=5114"},"modified":"2014-02-06T09:11:09","modified_gmt":"2014-02-06T14:11:09","slug":"downsampling-polygons","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/pick\/2014\/02\/07\/downsampling-polygons\/","title":{"rendered":"Downsampling polygons"},"content":{"rendered":"\r\n\r\n

Jiro<\/a>'s pick this week is Polygon simplification<\/a> by Peter Bone<\/a>.<\/p>

Continuing from one of my recent posts on \"Connecting points with smooth curves\"<\/a>, I came across this new entry by Peter that would work nicely with the hobbysplines<\/tt><\/a> function in tracing objects.<\/p>

Here's how I would use it. Let's start with the original amoeba image.<\/p>

im = imread('amoeba.png'<\/span>);\r\nimshow(im)\r\n<\/pre>\"\" 
I'll convert this grayscale image to black and white, and use a function called bwboundaries<\/tt><\/a> from the Image Processing Toolbox<\/a> to automatically trace out the boundaries.<\/p>
im2 = im2bw(im);\r\nboundaries = bwboundaries(~im2, 'noholes'<\/span>)\r\n<\/pre>
boundaries = \r\n    [1696x2 double]\r\n    [  30x2 double]\r\n    [  33x2 double]\r\n    [ 111x2 double]\r\n    [  31x2 double]\r\n    [  34x2 double]\r\n<\/pre>
Notice that bwboundaries<\/tt> returned a cell array of points for each boundary it found. In this case, it found 6 boundaries. For this discussion, I'll just focus on the largest boundary, i.e. the boundary with the most number of points. I can see that it is the first element. Question for everyone: how would I programmatically find the largest boundary? There are multiple ways of doing it, from basic MATLAB programming to advanced image processing. Post your response below<\/a>.<\/i><\/p>
largest = boundaries{1};\r\nhold on<\/span>\r\nplot(largest(:,2),largest(:,1),'r'<\/span>,'LineWidth'<\/span>,2)\r\nhold off<\/span>\r\n<\/pre>\"\" 
Now, suppose that I don't care for the details (e.g. the individual hairs) and would like to get just the general shape of the amoeba. I can do some filtering or smoothing of the data, or simply down-sample the boundary points. Peter's reduce_poly<\/tt> reduces the points by automatically removing the \"least important\" points. For example, I can ask for 100 points.<\/p>
numpts = 100;\r\nlargest2 = reduce_poly(largest', numpts)';\r\n\r\nimshow(im)\r\nhold on<\/span>\r\nplot(largest2(:,2),largest2(:,1),'r'<\/span>,'LineWidth'<\/span>,2)\r\nhold off<\/span>\r\n<\/pre>\"\" 
\"\" <\/p>
I'll go with numpts = 20<\/tt> for this case.<\/p>
numpts = 20;\r\nlargest2 = reduce_poly(largest', numpts)';\r\n\r\nimshow(im)\r\nhold on<\/span>\r\nplot(largest2(:,2),largest2(:,1),'r'<\/span>,'LineWidth'<\/span>,2)\r\nhold off<\/span>\r\n<\/pre>\"\" 
% Convert the boundary points to the format required by hobbysplines<\/span>\r\npts = fliplr(largest2(1:end-1,:));\r\n\r\nimshow(im)\r\nhobbysplines(num2cell(pts,2), ...<\/span>\r\n    'linestyle'<\/span>,{'linewidth'<\/span>,2}, ...<\/span>\r\n    'color'<\/span>,'red'<\/span>);\r\n<\/pre>\"\" 
Comments<\/b><\/p>
Let us know what you think here<\/a> or leave a comment<\/a> for Peter.<\/p>
Now, I'll use Will<\/a>'s hobbysplines<\/tt><\/a> to connect the points with smooth splines.<\/p>
That's better, but it's still too many points for my taste. I can modify numpts<\/tt> and rerun the block of code. Or<\/i>, I can increment a value and run the section<\/a> interactively.<\/p>