{"id":5859,"date":"2015-02-20T09:00:22","date_gmt":"2015-02-20T14:00:22","guid":{"rendered":"https:\/\/blogs.mathworks.com\/pick\/?p=5859"},"modified":"2015-02-22T20:04:34","modified_gmt":"2015-02-23T01:04:34","slug":"downsampling-polygons-part-2","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/pick\/2015\/02\/20\/downsampling-polygons-part-2\/","title":{"rendered":"Downsampling polygons (Part 2)"},"content":{"rendered":"
\r\n

Jiro<\/a>'s pick this week is Decimate Polygon<\/a> by Anton Semechko<\/a>.\r\n <\/p>\r\n

Just a little over a year ago, I wrote a blog post on downsampling polygons<\/a>. I highlighted Peter's Polygon Simplification<\/a>. His entry helped me out in one of my side projects I was working on at the time. Soon after, I received an email from a\r\n File Exchange contributor letting me know about another entry for accomplishing the task of downsampling polygons. I appreciate\r\n people letting me know about these entries I've overlooked. When I select a file to highlight in my posts I try to do a search\r\n on similar entries, but I don't always catch them all.\r\n <\/p>\r\n

Let's see how DecimatePoly<\/tt> works. I'm going to use the same image I used for my previous post.\r\n <\/p>

im = imread('amoeba.png'<\/span>);\r\nimshow(im)<\/pre> 
As before, I will convert this to black and white and trace out the boundaries using bwboundaries<\/tt><\/a> from the Image Processing Toolbox<\/a>. Then I will overlay the largest boundary onto the original image.\r\n   <\/p>
im2 = im2bw(im);\r\nboundaries = bwboundaries(~im2,'noholes'<\/span>)\r\n\r\nlargest = boundaries{1};\r\nhold on<\/span>\r\nplot(largest(:,2),largest(:,1),'r'<\/span>,'LineWidth'<\/span>,2)\r\nhold off<\/span><\/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> 
Currently, the boundary has 1696 vertices.<\/p>
size(largest)<\/pre>
ans =\r\n        1696           2\r\n<\/pre>
With DecimatePoly<\/tt>, I can downsample this polygon by specifying either the maximum acceptable offset from the original boundary or the fraction\r\n      of the total number of points to retain. For example, if I want to ensure the downsampled boundary to be off by maximum of\r\n      .1 pixels,\r\n   <\/p>
b1 = DecimatePoly(largest, [.1 1]);<\/pre>
\t\t# of verts\t\tperimeter\t\tarea\r\nin\t\t1695 \t\t\t1948.91\t\t\t27992.50\r\nout\t\t926  \t\t\t1948.91\t\t\t27992.50\r\n-----------------------------------------------------\r\nchange\t-45.37%\t\t\t-0.00%\t\t\t0.00 %\r\n\r\n<\/pre>
I can see that I have about 45% fewer points while maintaining the same perimeter and area. If I loosen my constraint,<\/p>
b2 = DecimatePoly(largest, [1 1]);<\/pre>
\t\t# of verts\t\tperimeter\t\tarea\r\nin\t\t1695 \t\t\t1948.91\t\t\t27992.50\r\nout\t\t473  \t\t\t1863.07\t\t\t28046.00\r\n-----------------------------------------------------\r\nchange\t-72.09%\t\t\t-4.40%\t\t\t0.19 %\r\n\r\n<\/pre>
I have over 70% fewer points while not sacrificing much change in perimeter or area.<\/p>
figure\r\nsubplot(1,2,1)\r\nplot(largest(:,2),largest(:,1))\r\naxis image<\/span> ij<\/span>\r\n\r\nsubplot(1,2,2)\r\nplot(b2(:,2),b2(:,1))\r\naxis image<\/span> ij<\/span><\/pre> 
So why is having fewer points preferred? Well, Anton has included a nice demo with his entry that shows improved performance\r\n      in in-polygon tests. This is one of the plots from the demo.\r\n   <\/p>\r\n   
 <\/p>\r\n   
He looked at how different number of polygon points affected the computation time and the accuracy of in-polygon tests. The\r\n      horizontal axis (Percent simplification) represents the degree of downsampling. The lower the percent simplification, the\r\n      greater the downsampling. The Dice coefficient<\/a> (blue) shows how similar the results are between the downsampled polygon and the full polygon. The closer the value is to\r\n      1, the more similar the results. The right axis (red) shows the relative speed up of the computation time compared to the\r\n      full polygon. We can see that even at around 10% simplification (downsampled by 90%), we are able to get over 98% similarity\r\n      and 10x speed up.\r\n   <\/p>\r\n   
Comments<\/b><\/p>\r\n   
Do you have a need to downsample polygons? What is your use case? Let us know here<\/a> or leave a comment<\/a> for Anton.\r\n   <\/p>