序列化足部压力图的最佳无损压缩技术

Question

我在做人脚压力感应，需要串口实时传帧

典型的框架如下所示，由平面背景和非平面数据块组成：

由于Serial.send命令导致微控制器开销，传输速度目前是一个瓶颈，所以工程师正在使用Run Length Encoding压缩图像，由于平面看起来不错，连续的背景，但我们想进一步压缩它。

我尝试了 "Coordinate List" 编码格式（List<i, j, val> 其中 val > 0），但大小与 RLE 足够相似，不会产生显着差异。

在对 SO 进行一些研究时，人们说 "don't reinvent the wheel, there are a lot of tried-and-tested compression algorithms for any kind of image"，所以我想知道下面显示的图像类型最好的是什么，考虑到：

压缩性能（因为它是由微控制器执行的）；
大小——因为要串口发送，目前是瓶颈（原文如此）。

其他方法是使用 "sparse-matrix" 概念（而不是 "image-compression" 概念），看起来有类似 CRS 或 CSR 的东西，我不能非常了解如何实现和如何正确序列化，更不用说它与图像压缩技术的比较了。

更新：我用我用来创建图像的数据创建了一个 Gist。这些是压缩方法的结果（每个条目一个字节）：

普通：（[n_rows, n_columns, *data]）：2290 字节；
坐标列表：（[*(i, j, val)]）：936字节；
运行长度编码：（[*(rowlength, rle-pairs)]）：846字节；
列表列表：690 字节；
列表的紧凑列表：（参见要点）498 字节；

Answer 1

提出的算法

下面是一个可能的算法，它只使用简单的操作^[1]，内存占用少（没有双关语意）。

它似乎工作得相当好，但是，当然，它应该在几个不同的数据集上进行测试，以便更准确地了解它的效率。

将矩阵分成 4x4 像素的 13x11 块
对于每个块：
- 如果块为空，则发出位“0”
- 如果方块不为空：
  1. 发出位“1”
  2. 在此块中发出非零像素的 16 位位掩码
  3. 发出 8 位值，表示在此块中找到的最小值（0 除外）
  4. 如果只有一个非零像素，到此为止^[2]
  5. 发出 3 位值，表示编码此块中每个非零像素所需的位数：b = ceil(log₂(max + 1 - min) )
  6. 以 N x b 位的形式发出非零像素数据

它基于以下观察：

矩阵中有很多块是空的
足迹边界的非空块通常有许多空单元格（传感器上的 'pressure' / 'no pressure' 过渡是突然的）

_{[1] 没有浮点运算。算法描述中使用的 log2() 操作可以很容易地替换为与 1, 2, 4, 8, 16, ... 最多 256 的简单比较。}

_{[2] 这是一个不会经常触发的小优化。解码器必须通过计算来检测位掩码中是否只设置了一位，例如：(msk & -msk) == msk.}

块编码示例

让我们考虑以下块：

 0,  0,  0,  0
12,  0,  0,  0
21, 20,  0,  0
28, 23,  0,  0

非零像素的位掩码是：

 0,  0,  0,  0
 1,  0,  0,  0  =  0000100011001100
 1,  1,  0,  0
 1,  1,  0,  0

最小值为12（00001100），编码每个非零像素所需的位数为5（101），如log₂(28 + 1 - 12) ~= 4.09.

最后，让我们对非零像素进行编码：

  [ 12, 21, 20, 28, 23 ]
- [ 12, 12, 12, 12, 12 ]
------------------------
= [  0,  9,  8, 16, 11 ] = [ 00000, 01001, 01000, 10000, 01011 ]

因此，此块的最终编码为：

1 0000100011001100 00001100 101 00000 01001 01000 10000 01011

长度为 53 位（相对于未压缩格式的 16 * 8 = 128 位）。

然而，最大的收益来自被编码为一位的空块。矩阵中有很多空块这一事实是该算法的一个重要假设。

演示

这是一些在您的原始数据集上运行的 JS 演示代码：

var nEmpty, nFilled;

function compress(matrix) {
  var x, y, data = '';

  nEmpty = nFilled = 0;
  
  for(y = 0; y < 44; y += 4) {
    for(x = 0; x < 52; x += 4) {
      data += compressBlock(matrix, x, y);
    }
  }
  console.log("Empty blocks: " + nEmpty);
  console.log("Filled blocks: " + nFilled);
  console.log("Average bits per block: " + (data.length / (nEmpty + nFilled)).toFixed(2));
  console.log("Average bits per filled block: " + ((data.length - nEmpty) / nFilled).toFixed(2));
  console.log("Final packed size: " + data.length + " bits --> " + ((data.length + 7) >> 3) + " bytes");
}

function compressBlock(matrix, x, y) {
  var min = 0x100, max = 0, msk = 0, data = [],
      width, v, x0, y0;
  
  for(y0 = 0; y0 < 4; y0++) {
    for(x0 = 0; x0 < 4; x0++) {
      if(v = matrix[y + y0][x + x0]) {
        msk |= 1 << (15 - y0 * 4 - x0);
        data.push(v);
        min = Math.min(min, v);
        max = Math.max(max, v);
      }
    }
  }
  if(msk) {
    nFilled++;
    width = Math.ceil(Math.log(max + 1 - min) / Math.log(2));
    data = data.map(function(v) { return bin(v - min, width); }).join('');
    return '1' + bin(msk, 16) + bin(min, 8) + ((msk & -msk) == msk ? '' : bin(width, 3) + data);
  }
  nEmpty++;
  return '0';
}

function bin(n, sz) {
  var b = n.toString(2);
  return Array(sz + 1 - b.length).join('0') + b;
}

compress([
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 10, 12,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  7,  0,  0, 10, 12,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 15, 15,  9,  0,  0,  7,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  7, 10,  9, 11,  7, 12, 21, 20,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 13, 15, 13,  0,  0, 15, 28, 23,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 10,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0, 12,  7,  8,  0,  0,  0,  0, 14,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 14, 12,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0, 11, 10,  0,  0, 11, 19, 12,  9,  8,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 10, 12, 12, 14, 24, 26, 21,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  7,  0,  0, 21, 33, 38, 30, 23, 26, 15,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  7, 15, 16, 17, 22, 29, 32, 26, 18,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  7,  0, 22, 38, 46, 47, 42, 33, 27, 28,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  7, 14, 18, 18, 23, 28, 32, 31, 23, 12,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  7,  7, 17, 31, 52, 54, 55, 48, 36, 34, 32,  9,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  9, 12, 12, 17, 22, 29, 28, 26, 17,  7,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0, 10, 26, 40, 50, 51, 48, 38, 28, 30, 25,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 14, 23, 22, 20, 16, 10,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0, 20, 30, 38, 40, 42, 37, 27, 19, 18, 10,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 11, 15, 13, 12, 10,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0, 13, 24, 27, 28, 30, 32, 26, 13,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  9, 12,  9, 11,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0, 14, 26, 27, 24, 24, 19, 10,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  7,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  7, 20, 22, 19, 17, 12,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0, 15, 16, 17, 14,  9,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0, 15, 14, 15, 11,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0, 10, 16, 18, 15,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 17, 19, 17,  9,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 19, 20, 20,  9,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 18, 20, 21, 12,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 12, 19, 16, 10,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 12, 11,  8,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  9,  8,  8,  7,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 10, 12, 12, 10,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  8, 10, 10, 13, 13,  8,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  9, 20, 25, 24, 17,  9,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 13, 20, 26, 25, 24, 11,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 20, 28, 32, 31, 24, 13,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 20, 28, 36, 39, 34, 26,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 11, 29, 36, 39, 37, 30, 18,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 22, 31, 43, 50, 58, 39, 15,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 19, 39, 46, 46, 40, 32, 20,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 24, 38, 51, 60, 64, 54, 26,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 25, 40, 49, 49, 44, 33, 20,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 25, 45, 59, 65, 68, 66, 32,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 21, 40, 46, 46, 42, 31, 11,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 22, 44, 56, 66, 70, 61, 32,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 11, 31, 35, 38, 31, 18,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 11, 31, 55, 66, 64, 52, 25,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  9, 17, 18, 11,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 17, 36, 50, 50, 32, 12,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 13, 22, 21, 12,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ],
  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 0 ]
]);

最终输出为 349 字节 长。

Empty blocks: 102
Filled blocks: 41
Average bits per block: 19.50
Average bits per filled block: 65.51
Final packed size: 2788 bits --> 349 bytes

Answer 2

我会测试 JPEG-LS。它是一种非常快速的算法，可为多种类型的图像提供最先进的无损压缩结果。特别是，它的预测算法将提供与平坦区域的 RLE 相当的结果，以及脚部区域更好的结果。

由于您正在传输多个帧，并且这些帧可能非常相似，因此您可能希望在应用 JPEG-LS 之前尝试从下一帧中减去一帧（您可能需要将像素重新映射到正不过，在使用 JPEG-LS 之前是整数）。

如果您不需要严格无损压缩（即，如果您可以容忍重建图像中的一些失真），您可以测试近乎无损模式，它限制了任何给定像素中引入的最大绝对误差。

你可以在这里找到一个非常好的和完整的实现 https://jpeg.org/jpegls/software.html。

序列化足部压力图的最佳无损压缩技术

Best lossless compression technique for serializing a foot pressure map

compression

sparse-matrix

run-length-encoding

image-compression

提出的算法

块编码示例

演示