Jiro's pick this week is Decimate Polygon by Anton Semechko.

Just a little over a year ago, I wrote a blog post on downsampling polygons. I highlighted Peter's Polygon Simplification. 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 File Exchange contributor letting me know about another entry for accomplishing the task of downsampling polygons. I appreciate 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 on similar entries, but I don't always catch them all.

Let's see how DecimatePoly works. I'm going to use the same image I used for my previous post.

im = imread('amoeba.png');
imshow(im)

As before, I will convert this to black and white and trace out the boundaries using bwboundaries from the Image Processing Toolbox. Then I will overlay the largest boundary onto the original image.

im2 = im2bw(im);
boundaries = bwboundaries(~im2,'noholes')

largest = boundaries{1};
hold on
plot(largest(:,2),largest(:,1),'r','LineWidth',2)
hold off

boundaries = 
    [1696x2 double]
    [  30x2 double]
    [  33x2 double]
    [ 111x2 double]
    [  31x2 double]
    [  34x2 double]

Currently, the boundary has 1696 vertices.

size(largest)

ans =
        1696           2

With DecimatePoly, I can downsample this polygon by specifying either the maximum acceptable offset from the original boundary or the fraction of the total number of points to retain. For example, if I want to ensure the downsampled boundary to be off by maximum of .1 pixels,

b1 = DecimatePoly(largest, [.1 1]);

		# of verts		perimeter		area
in		1695 			1948.91			27992.50
out		926  			1948.91			27992.50
-----------------------------------------------------
change	-45.37%			-0.00%			0.00 %

I can see that I have about 45% fewer points while maintaining the same perimeter and area. If I loosen my constraint,

b2 = DecimatePoly(largest, [1 1]);

		# of verts		perimeter		area
in		1695 			1948.91			27992.50
out		473  			1863.07			28046.00
-----------------------------------------------------
change	-72.09%			-4.40%			0.19 %

I have over 70% fewer points while not sacrificing much change in perimeter or area.

figure
subplot(1,2,1)
plot(largest(:,2),largest(:,1))
axis image ij

subplot(1,2,2)
plot(b2(:,2),b2(:,1))
axis image ij

So why is having fewer points preferred? Well, Anton has included a nice demo with his entry that shows improved performance in in-polygon tests. This is one of the plots from the demo.

He looked at how different number of polygon points affected the computation time and the accuracy of in-polygon tests. The horizontal axis (Percent simplification) represents the degree of downsampling. The lower the percent simplification, the greater the downsampling. The Dice coefficient (blue) shows how similar the results are between the downsampled polygon and the full polygon. The closer the value is to 1, the more similar the results. The right axis (red) shows the relative speed up of the computation time compared to the full polygon. We can see that even at around 10% simplification (downsampled by 90%), we are able to get over 98% similarity and 10x speed up.

Comments

Do you have a need to downsample polygons? What is your use case? Let us know here or leave a comment for Anton.

Get the MATLAB code

Published with MATLAB® R2014b