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

Question

我正在研究人脚的压力传感，我需要通过串行实时传输帧。

典型的框架如下所示，由平坦的背景和非平坦的数据 Blob 组成:

由于Serial.send引起的微 Controller 开销，传输速度目前是一个瓶颈。命令，因此工程师使用 Run Length Encoding压缩图像，由于平坦、连续的背景，这看起来不错，但我们想进一步压缩它。

我尝试了“坐标列表”编码格式( List<i, j, val> 其中 val > 0)，但大小与 RLE 足够相似，不会产生显着差异。

在对 SO 进行一些研究时，人们说“不要重新发明轮子，对于任何类型的图像都有很多经过尝试和测试的压缩算法”，所以我想知道什么是最适合该类型的下面显示的图像，考虑到:

1. 压缩性能(因为它由微 Controller 执行)；
2. 大小 - 因为它是通过串行发送的，目前这是一个瓶颈(原文如此)。

其他方法是使用“稀疏矩阵”概念(而不是“图像压缩”概念)，看起来像CRS ，或 CSR，我不太明白如何实现以及如何正确序列化，更不明白它如何与图像压缩技术进行比较。

更新: 我创建了一个Gist以及我用来创建图像的数据。这些是压缩方法的结果(每个条目一个字节):

• 普通:( [n_rows, n_columns, *data] ):2290 字节；
• 坐标列表:( [*(i, j, val)] ):936 字节；
• 游程编码:( [*(rowlength, rle-pairs)] ):846 字节；
• 列表列表:690 字节；
• 紧凑的列表列表:(参见要点)498 字节；

Answer 1

提出的算法

下面是一种可能的算法，仅使用简单的操作 ^[1]，内存占用较低(无双关语)。

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

1. 将矩阵划分为 4x4 像素的 13x11 block

2. 对于每个 block :

   • 如果 block 为空，则发出位“0”
   • 如果 block 不为空:
     1. 发出位“1”
     2. 发出此 block 中非零像素的 16 位位掩码
     3. 发出 8 位值，表示此 block 中找到的最小值(0 除外)
     4. 如果只有一个非零像素，则在此停止 ^[2]
     5. 发出 3 位值，表示对该 block 中的每个非零像素进行编码所需的位数:b = ceil(log₂(max + 1 - min))
     6. 以 N x b 位的形式发出非零像素数据

它基于以下观察:

• 矩阵中的许多 block 都是空的
• 足迹边界的非空 block 通常有许多空单元(传感器上的“压力”/“无压力”转换是突然的)

---

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

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

block 编码示例

让我们考虑以下 block :

 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 ]

因此，该 block 的最终编码将是:

1 0000100011001100 00001100 101 00000 01001 01000 10000 01011

长度为 53 位(未压缩格式的长度为 16 * 8 = 128 位)。

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

演示

这里是一些在原始数据集上运行的 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