智能抽取：折线简化和光滑

ADMGNS

5.00/5 (4投票s)

2021年6月28日

BSD

3分钟阅读

14549

348

一种新的 2D 折线简化和光滑方法，可替代 Douglas-Peucker 和基于曲率的简化算法

下载源代码 - 500.3 KB

Main Screen

引言

在这篇文章中，我将介绍一种新的二维折线简化和平滑方法，我将其命名为智能抽取。很明显，有很多已知的方法可以使用不同的方法来获得简化的曲线。例如，在信号处理中，使用FFT通过添加零或移除相同样本进行多速率重采样。

总而言之，以下是这些方法：

道格拉斯-普克算法
Visvalingam-Whyatt算法
基于曲率的简化算法
最大平方距离算法
Reumann-Witkam算法
Opheim算法
Lang算法
第N个点
点与点之间的距离
垂直距离

在你继续之前，我建议你首先查看这篇CodeProject文章"多段线简化"，作者是Elmar de Koning。

方法

假设我们有3个点，我们想得到5个点（即插值）。或者，我们有5个点，我们想得到3个点（即抽取）。此方法可用于这两种情况。在这里，我们将其用于降维。

此方法实际上与双线性插值非常相似，但完全不同。我们知道，在图像处理中，有一些著名的图像大小调整算法。

最近邻，即直接复制
双线性插值
双三次插值
Sinc/Lanczos插值

在视觉上，对于图像来说，该算法的质量优于双线性插值，但不如双三次插值。在放大时，它比其他方法具有更少或没有伪影（例如，混叠、模糊、边缘光晕）。

解释其底层逻辑的最佳方法是使用逐步说明的图形。

另一种解释（一维数据）

例如，假设我们有11个值：41、79、9、36、11、33、23、46、36、88、89。现在，我们只想得到3个值，而不会丢失数据集的主要特征。

Smart Decimation (1D)

步骤非常简单：克罗内克积，然后重新分组数据，最后计算这些数据组的平均值。

如果我们应用这些步骤，我们将得到结果为41.7273、25.7273、66.4545。

注意：需要明确的是，输入值的数量和输出值的数量必须是伪素数。否则，它只会重复输入值，结果将与（双）线性方法相同。

实现

这是为二维点数组改编的实现代码。

type
  TPointArr = array of TPoint;
....

procedure SmartDecimation(source: TPointArr; mSource: integer; 
                          var dest: TPointArr; nDest: integer);
// (c) Copyright AG 2021. ademgunes@yahoo.com
// Not allowed to use for commercial apps without permissions.
var
  m, n, k, p, q: integer;
  t1, t2: double;
begin
  if ( (mSource < 3) or (nDest < 3) ) then Exit;
  t1 := 0;
  t2 := 0;
  for m:=0 to mSource-1 do
  begin
    for n:=0 to nDest-1 do
    begin
      k := m * nDest + n;
      t1 := t1 + source[m].X;
      t2 := t2 + source[m].Y;
      p := k div mSource;
      q := k mod mSource;
      if (q = mSource-1) then
      begin
        dest[p].X := trunc(t1 / mSource + 0.5);
        dest[p].Y := trunc(t2 / mSource + 0.5);
        t1 := 0;
        t2 := 0;
      end;
    end;
  end;
end;