有没有适合GPS压缩的算法waypoints？

Question

我正在寻找坐标为 EPSG:4326 CRS 的 GPS 轨道 waypoints 有损压缩的任何算法（通常的度数如 (75.223423,-10.123123))

简而言之，在删除元信息并使用 Ramer–Douglas–Peucker 算法进行简化后，我有一个有序的航点坐标序列，每个航点占用 16 个字节（2 x 8 字节 double).

利用知识waypoints是有序的，waypoints之间的距离在大多数情况下小于0.01°（~赤道1公里 ), 我做了一个假设，对于这样的序列可能存在某种有损压缩算法。

能帮我查一下吗

UPD: 根据真实轨迹（分析~800），点与点之间的距离（以度为单位）如下所示。 P95 是所有距离的第 95 个百分位数。

LON    
    avg: 0,000334560520818109
    p95: 0,001239999999999240 # ~138 meters
    max: 0,307273900000000000
LAT    
    avg: 0,000221987685948093
    p95: 0,000839999999996621
    max: 0,309625799999999000

Answer 1

您不需要 eight-byte 浮点格式来表示您期望的有效数字数量和可能值的有限范围。我首先将数据转换为一系列具有适当长度的整数，这些整数可以表示您的值的准确性和范围。看起来两个 four-byte 整数就足够了。那里有一个 factor-of-two 压缩。

然后用该点与前一个点的差异替换每个点，除了第一个点。现在整数应该更小，允许任何通用无损压缩器进一步减少。如果差异仅在 0.1° 左右，您可以得到另一个两倍。

这是一个简单的例子，这个点的预测是最后一个点。如果您的点序列代表一条路径，您可以在建模速度时做一些更复杂的事情。在这种情况下，您使用最后建模的速度传播最后一个点，并从当前点中减去它。

修正案

我发现WGS84参考系本身只能精确到2-5米。使用 three-byte 个整数，您可以获得赤道 2.4 米的分辨率。在差分和压缩之前，这提供了 62.5% 的减少。它还为您提供了纬度的自由位，因为它的范围是经度的一半。该位可用于标记这是绝对坐标还是根据最后一个坐标预测的。

Answer 2

如果您需要自己编写代码，这里有一个简单的 'delta' 编码方案的技巧，可以避免不必要地损失准确性。

这个想法是，压缩器不应该计算当前数据点和最后一个数据点之间的增量，而是计算当前数据点和解压缩器为最后一个计算的数据点之间的增量。这意味着量化误差不会累加。

作为一个简单的示例，您可能希望 peruse/experiment 使用以下 C 代码将双精度压缩为（开始双精度）和一系列浮点数：

typedef struct
{   double  start;
    int n;
    float*  delta;
} compT;

compT   compress( int n, const double* data)
{
compT   c = (compT){ data[0], n-1, malloc( (n-1)*sizeof *c.delta)};
double  r = c.start;
    for( int i=1; i<n; ++i)
    {
    float   d = (float)(data[i]-r);
        c.delta[i-1] = d;
        r += d;
    }
    return c;
}

static  double* uncompress( compT c)
{
double* d = malloc( (c.n+1)*sizeof *d);
double  r = c.start;
    d[0] = r;
    for( int i=1; i<=c.n; ++i)
    {   r += c.delta[i-1];
        d[i] = r;
    }
    return d;
}
compT   bad_compress( int n, const double* data)
{
compT   c = (compT){ data[0], n-1, malloc( (n-1)*sizeof *c.delta)};
    for( int i=1; i<n; ++i)
    {
    float   d = (float)(data[i]-data[i-1]);
        c.delta[i-1] = d;
    }
    return c;
}

当使用浮点数时，量化误差的累积实际上只在长（数百万）数据序列上才明显。

但是当希望压缩更多时，效果更明显。下面的代码使用 int_16t 作为增量。我在数据值保证在 1Km 左右的情况下使用了它，所以我使用了 16 的比例（在下面的代码中），因此可以应对 2km 的差异。

typedef struct
{   float   scale;
    double  start;
    int n;
    int16_t*    delta;
} compiT;

compiT  compressi( int n, const double* data, float scale)
{
compiT  c = (compiT){ scale, data[0], n-1, malloc( (n-1)*sizeof *c.delta)};
double  r = c.start;
    for( int i=1; i<n; ++i)
    {
    int16_t d = (int16_t)round(c.scale*(data[i]-r));
        c.delta[i-1] = d;
        r += ((double)d)/c.scale;
    }
    return c;
}

compiT  bad_compressi( int n, const double* data, float scale)
{
compiT  c = (compiT){ scale, data[0], n-1, malloc( (n-1)*sizeof *c.delta)};
    for( int i=1; i<n; ++i)
    {
    int16_t d = (int16_t)round(c.scale*(data[i]-data[i-1]));
        c.delta[i-1] = d;
    }
    return c;
}

static  double* uncompressi( compiT c)
{
double* d = malloc( (c.n+1)*sizeof *d);
double  r = c.start;
    d[0] = r;
    for( int i=1; i<=c.n; ++i)
    {
    double  delta = ((double)c.delta[i-1])/c.scale;
        r += delta;
        d[i] = r;
    }
    return d;
}

在任意长度的运行中，最大误差（即原始数据和解压后的压缩数据之间的差异）应该在 3 厘米左右，而使用 bad_compressor 误差约为1000 次运行 0.5m，10000 次运行 2.5m

当然，如果您无法保证差异的有限性，则需要进行某种重启。

Answer 3

我找到了一个现有的解决方案：TinyWKB or TWKB or Tiny Well-known Binary 数据格式适合我的需要。

它存储几何图元（它 LineString 支持我当前的需求）。
它使用增量存储数据。
它支持浮点精度（+2 到 -2）。
它支持 ID-data 几何。
可以使用NetTopologySuite.Net模块编写。

TinyWKB 从 WKT -> WKB -> TWKB 发展而来，用于存储几何图元（Points、LineStrings、Polygons、MultiPoints、MultiLineStrings、MultiPolygons、GeometryCollections）

有没有适合GPS压缩的算法waypoints？

Is there any algorithm suitable for compression of GPS waypoints?

compression

floating-point

gps

coordinates

gpx