How to decrease the number of points in a shape?

Hi, I would like to know if it is possible to decrease the number of points (x,y) in a shape , using Matlab, in order to obtain the minimum number of points needed to plot/describe exactly the same shape. How to automate this process via Matlab? Thanks

[Massimo Zanetti]

Is it you shape convex? In this case your shape just coincide with its convex hull.

[Johnny A]

My shape is similar to an ellipsoid,but it's not convex. I'd like to delete some points of that boundary in order to describe the shape with a small number of points.

Answer 1

[Massimo Zanetti]

Since your shape is not convex, you cannot use convexhull trick. Here is the piece of code to eliminate collinear points.

a=x(:)';
b=y(:)';
before=numel(a);
after=before+1;
tol=1e-5;
while after~=before
    fprintf('before: %d   after: %d \n',before,after);
    before=numel(a);
    X=[a(1:end-1);a(2:end);[a(3:end),a(1)]];
    Y=[b(1:end-1);b(2:end);[b(3:end),b(1)]];
    A=polyarea(X,Y);
    I=[false,abs(A)<tol];
    a(I)=[];
    b(I)=[];
    after=numel(a);
end
plot(x,y,'b.',a,b,'ro');

It exploits the fact that 3 (almost) collinear points define a very small area. See result in the image.

If you want to only remove the points that are "perfectly" collinear, then replace

I=[false,abs(A)<tol];

with

I=[false,A==0];

But in your case you would just erase a few points.

[Jun Liu]

Neat! thanks.

Answer 2

[Image Analyst]

You want what's called "the minimum perimeter polygon". I think this paper discussing it will help you : http://dip.sun.ac.za/~hanno/tw444/lesings/lesing_19.pdf

It will also be interesting to try Massimo's clever algorithm. Adjust "tol" to adjust the amount of departure from a straight line you'd like to tolerate.

Answer 3

[Image Analyst]

There is now a function called reducepoly in the Image Processing Toolbox.

reducepoly

Reduce density of points in ROI using Ramer–Douglas–Peucker algorithm

Syntax

P_reduced = reducepoly(P)

P_reduced = reducepoly(P,tolerance)

Description

example

P_reduced = reducepoly(P) reduces the density of points in array P. The reducepoly function uses the Ramer-Douglas-Peucker line simplification algorithm, removing points along straight lines and leaving only knickpoints (points where the line curves).

P_reduced = reducepoly(P,tolerance) reduces the density of points in array P, where tolerance specifies how much a point can deviate from a straight line.