уменьшить количество сторон многоугольника

Question

Предположим, у нас есть изображение простой графики, и мы знаем, что это многоугольник, слегка искаженный. Есть ли способ обработки изображения для аппроксимации исходных параметров графического объекта?

Приведенная ниже матрица была создана кодом, а затем уменьшена в размере, чтобы показать пятую область интереса:

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

Для следующего шага мне нужны координаты ABC / ABCD, чтобы получить z-профиль по линиям, дополнительно определенным этими точками.

Answer 1

Я начал работать до того, как Патрик опубликовал свой образовательный ответ, и я столкнулся с одной «проблемой» с алгоритмом Рамера-Дугласа-Пейкера: он, по определению, сохраняет первый и последний пункты.Функции convhull и boundary начинаются где-то и не всегда в углу, что приведет к ложному срабатыванию.Третий и четвертый этапы решают эту проблему. Другая точка, скорее всего, является истинным углом.

Алгоритм:

1. обнаружение выпуклой оболочки / внешних точек.
2. Применение алгоритма Рамера-Дугласа-Пекера (RDP) с более плотной подгонкой
3. Перемотка петли
4. Применение алгоритма RDP для удаления ложноположительного угла с более свободной подгонкой

Код:

eps1=2;
eps2=4;
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];

[X,Y]=find(matr==5); % // find image coordinates of points of interest
is=boundary(X,Y,1);  % // find points on the boundary

xy=[X(is),Y(is)];    % // boundary points (step 1)

% // apply RDP algorithm (step 2)
xy=RDP(xy,eps1);

% // rewind the loop (step 3)
xy=xy([2:end-1 1:2],:);

% // apply the DRP algorithm (step 4)
xy=RDP(xy,eps2);

function[hull]=RDP(hull,eps)
    sp=hull(1,:);
    ep=hull(end,:);
    ip=hull(2:end-1,:);
    % // calculate distances of inner points from the first-last line
    dst=PerpDist(sp,ep,ip);
    % // find the point furthest from the f-l line
    [mx,mi]=max(dst);
    if mx>eps % // furthest point does not fit in - split and apply RDP recursively
        lp=[sp;ip(1:mi,:)];
        if size(lp,1)>2 % // there are points left to assess
            lp=RDP(lp,eps);
        end
        rp=[ip(mi:end,:);ep];
        if size(rp,1)>2 % // there are points left to assess
            rp=RDP(rp,eps);
        end
        hull=[lp;rp(2:end,:)]; % // concatenate the branches
    else % // the furthest poit fits in the limit, drop all inner points
        hull=[sp;ep];
    end
end

function[D]=PerpDist(A,B,C)
    D=nan(size(C,1),1);
    if A==B % // edge is defined by one point, use euclidean distance between points
        for PDi=1:size(C,1)
            D(PDi)=norm(C(PDi,:)-A);
        end
    else % // edge is a line, use eucleidean distance from a line
        for PDi=1:size(C,1)
            D(PDi)=abs(A(1)*(B(2)-C(PDi,2))+B(1)*(C(PDi,2)-A(2))+C(PDi,1)*(A(2)-B(2)))/norm(B-A);
        end
    end
end

Точки: точки внутри фигуры.
Красный квадрат:Первая и последняя точки возвращаются из функции boundary.
зеленая линия: результат первого моделирования RDP.
Пурпурная линия: конечный треугольник (исходная форма была треугольником).

Редактирование:

1. Оставляя идею найти две самые дальние точки для разбиения цикла, потому что это вызвало ложные срабатывания даже для треугольников.Начните с произвольной точки и дважды используйте RDP.

Кредиты:

Стив Эддинс для max_feret диаметр
КрисLuengo для алгоритм Рамера-Дугласа-Пекера комментарий

Answer 2

Вот реализация алгоритма Рамера – Дугласа – Пекера, предложенная выше в комментарии Криса Луенго.

Это полное редактирование первой версии ответа , в которой edge использовалось для определения границ объекта. Как отметил Крис Луенго в комментарии, bwboundaries - лучший выбор для двоичных изображений. bwboundaries возвращает отсортированные точки, что значительно упрощает код.

Следующий код выполняет следующие действия:

1) найдите края вашего объекта, используя bwboundaries. Они уже отсортированы.

2) Используйте алгоритм Рамера – Дугласа – Пекера, чтобы упростить список точек.

Поскольку для отладки мне потребовались визуальные подсказки, код открывает рисунок, который показывает, что происходит.

Обратите внимание, что код далек от надлежащего тестирования.

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