reduce side-count of a polygon

Question

Suppose we have image of a simple graphic, and we know it is a polygon, slightly distorted. Is there an image processing way to approximate the original parameters of the graphic object?

The matrix below was created by code and then reduced in size to show the fifth area of interest:

EnumeratedMask=bwlabel(Zdata<-.06);

0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   5   5   5   0   0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   5   5   5   5   0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   5   5   5   5   5   5   5   0   0   0   0   0   0   0   0
0   0   0   5   5   5   5   5   5   5   5   5   0   0   0   0   0   0   0
0   0   0   5   5   5   5   5   5   5   5   5   5   5   0   0   0   0   0
0   0   0   5   5   5   5   5   5   5   5   5   5   5   5   5   0   0   0
0   0   0   5   5   5   5   5   5   5   5   5   5   5   5   5   5   0   0
0   0   0   5   5   5   5   5   5   5   5   5   5   5   5   0   0   0   0
0   0   0   5   5   5   5   5   5   5   5   5   0   0   0   0   0   0   0
0   0   0   5   5   5   5   5   5   5   5   0   0   0   0   0   0   0   0
0   0   0   0   5   5   5   5   5   5   5   0   0   0   0   0   0   0   0
0   0   0   0   5   5   5   5   5   5   5   0   0   0   0   0   0   0   0
0   0   0   5   5   5   5   5   5   5   0   0   0   0   0   0   0   0   0
0   0   0   5   5   5   5   0   0   0   0   0   0   0   0   0   0   0   0
0   0   0   5   5   5   5   0   0   0   0   0   0   0   0   0   0   0   0
0   0   0   5   5   5   5   5   0   0   0   0   0   0   0   0   0   0   0
0   0   0   5   5   0   0   0   0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0

For next step I need the ABC/ABCD coordinates to get z-profile across lines further defined by those points.

Answer 1

Here is an implemetation of the Ramer–Douglas–Peucker algorithm as suggested in the comment by Cris Luengo above.

This is a full edit of the first version of the answer, which used edge to find the boundaries of the object. As Cris Luengo pointed out in a comment, bwboundaries is a better choice for binary images. bwboundaries returns the points sorted, which simplifies the code a lot.

The following code does the following:

1) find the edges of your object using bwboundaries. They are already sorted.

2) Use the Ramer–Douglas–Pecker algorithm to simplify the point list.

Since I needed some visual cues for debugging, the code opens a figure that shows what is going on.

Please note that the code is far from being properly tested.

img = [...
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 5 5 5 5 5 5 5 0 0 0 0 0 0 0 0
    0 0 0 5 5 5 5 5 5 5 5 5 0 0 0 0 0 0 0
    0 0 0 5 5 5 5 5 5 5 5 5 5 5 0 0 0 0 0
    0 0 0 5 5 5 5 5 5 5 5 5 5 5 5 5 0 0 0
    0 0 0 5 5 5 5 5 5 5 5 5 5 5 5 5 5 0 0
    0 0 0 5 5 5 5 5 5 5 5 5 5 5 5 0 0 0 0
    0 0 0 5 5 5 5 5 5 5 5 5 0 0 0 0 0 0 0
    0 0 0 5 5 5 5 5 5 5 5 0 0 0 0 0 0 0 0
    0 0 0 0 5 5 5 5 5 5 5 0 0 0 0 0 0 0 0
    0 0 0 0 5 5 5 5 5 5 5 0 0 0 0 0 0 0 0
    0 0 0 5 5 5 5 5 5 5 0 0 0 0 0 0 0 0 0
    0 0 0 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 5 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];

watch = true;

if watch
    f = figure;
    subplot(1,2,1);
    imagesc(img);
end


% first, find the edges

b = bwboundaries(img);

% note that the first and the last point are the same.
% However they are already sorted.
x = b{1}(:,1);
y = b{1}(:,2);

edges = zeros(size(img));
edges(sub2ind(size(e), x,y)) = 1;

if watch
    ax = subplot(1,2,2);

    img_h = imagesc(edges);
    hold on;

end 

title('Performing Douglas-Peucker algorithm');

% Omit the last point for the algorithm.

points = l_DouglasPeucker( [x(1:end-1), y(1:end-1)], 1, watch);

title('Final result');
plot([points(:,2); points(1,2)], [points(:,1); points(1,1)]);



function res = l_DouglasPeucker( points, ep, watch )

    if nargin < 3
        watch = false;
    end

    if watch
        subplot(1,2,2);
        hold on;
        hp = plot(points(:,2), points(:,1), 'ko-');
        hp2 = plot([points(1,2) points(end,2)], [points(1,1) points(end,1)], 'r-');
    end
    distances = zeros(size(points,1),1);
    for i = 1:size(points,1)
        distances(i) = l_distance_to_line(points(1,:), points(end,:), points(i,:));
    end

    idx = find(distances == max(distances),1);


    if watch
        hp4 = plot(points(idx,2), points(idx,1), 'mo', 'MarkerFaceColor', [1,1,1]);
        pause(.5);
        delete(hp);
        delete(hp2);
        delete(hp4);
    end

    if max(distances) > ep
        res = [l_DouglasPeucker(points(1:idx,:), ep, watch); l_DouglasPeucker(points(idx:end,:), ep, watch)];
    else
        res = [points(1,:); points(end,:)];
    end


end

function d = l_distance_to_line(p1,p2,p)
% computes the distance of p to the line through by p1 and p2
% There might be much better implementations of this...

% we need 3-dimensional data for this

p1 = [p1(1), p1(2), 0];
p2 = [p2(1), p2(2), 0];
p = [p(1,1) p(1,2) 0];

a = p2 - p1;
b = p - p1;

d = norm(cross(a,b)) ./ norm(a);
end