algorithm - 如何为任何二维形状(或曲线)生成阶梯曲线(轮廓)？

Question

如果我有任意 2D 形状轮廓上的点坐标，如何找到组成阶梯曲线轮廓的点坐标，它最能代表原始轮廓，但只使用一组已知坐标(xi, i=1,...,n 和 yi, i=1,...,m)。例如，原始三角形由蓝色粗实线表示。如果我的理解是正确的话，它与 matlab stairs 函数不同。matlab代码会很好，但用其他语言也可以，算法最重要。谢谢。

Answer 1

我将首先根据您的绘图定义一组样本数据。假设像素中心以整数值对齐(遵循 MATLAB 约定)并且左下角位于 (0.5, 0.5)，这是我们得到的数据:

vx = [1.5; 9.7; 3.7; 1.5];  % X values of triangle vertices
vy = [8.3; 6.0; 1.7; 8.3];  % Y values of triangle vertices
x = 1:10;                   % X pixel center coordinates
y = 1:9;                    % Y pixel center coordinates

请注意，顶点坐标从三角形的左上角开始按顺时针方向排列，在末尾重复第一个顶点以闭合多边形。

获取面具(简单的部分):

如果您有Image Processing Toolbox，有一种计算深灰色 mask 的简单方法。 : 使用 poly2mask :

mask = poly2mask(vx, vy, numel(y), numel(x));

讨论了此函数使用的算法 here .但是，如果您想使用不需要特殊工具箱的纯 MATLAB 方法，您可以使用 inpolygon相反:

[cx, cy] = meshgrid(x, y);         % Generate a grid of x and y values
mask = inpolygon(cx, cy, vx, vy);

在这种情况下，只要像素的中心点位于多边形内，该像素就会包含在 mask 中。在此特定示例中，这两种方法产生相同的结果掩码，但由于决定是否包含像素的标准不同，它们并不总是如此。

获取轮廓坐标:

获取蒙版轮廓的坐标有点复杂，在周边周围适当排序。为此，我们可以将掩码表示为一系列顶点和三角形面(使用 triangulation 函数)，然后计算 free boundary (即仅出现在一个三角形面上的边):

% Create raw triangulation data:
[cx, cy] = meshgrid(x, y);
xTri = bsxfun(@plus, [0; 1; 1; 0], cx(mask).');
yTri = bsxfun(@plus, [0; 0; 1; 1], cy(mask).');
V = [xTri(:) yTri(:)];
F = reshape(bsxfun(@plus, [1; 2; 3; 1; 3; 4], 0:4:(4*nnz(mask)-4)), 3, []).';

% Trim triangulation data:
[V, ~, Vindex] = unique(V, 'rows');
V = V-0.5;
F = Vindex(F);

% Create triangulation and find free edge coordinates:
TR = triangulation(F, V);
freeEdges = freeBoundary(TR).';
xOutline = V(freeEdges(1, [1:end 1]), 1);  % Ordered edge x coordinates
yOutline = V(freeEdges(1, [1:end 1]), 2);  % Ordered edge y coordinates

我们可以这样画:

imagesc(x, y, mask);
axis equal
set(gca, 'XLim', [min(x)-0.5 max(x)+0.5], ...
         'YLim', [min(y)-0.5 max(y)+0.5], ...
         'XTick', x, 'YTick', y, 'YDir', 'normal');
colormap([0.9 0.9 0.9; 0.6 0.6 0.6]);
hold on;
plot(xOutline, yOutline, 'b', 'LineWidth', 2);
plot(xOutline(1), yOutline(1), 'go', 'LineWidth', 2);
plot(vx, vy, 'r', 'LineWidth', 2);

xOutline 和 yOutline 中的轮廓坐标从围绕 mask 区域逆时针方向的绿色圆圈开始排序。