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

Question

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

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

由于命令引起的微控制器开销，传输速度目前是一个瓶颈Serial.send，因此工程师正在使用Run Length Encoding压缩图像，由于平坦，连续的背景看起来不错，但我们希望将其压缩均匀更远。

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

在对 SO 进行一些研究时，人们说“不要重新发明轮子，对于任何类型的图像都有很多久经考验的压缩算法”，所以我想知道哪种图像最适合显示的图像类型下面，考虑：

压缩性能（因为它是由微控制器执行的）；
大小 - 因为它是通过串行发送的，这目前是一个瓶颈（原文如此）。

其他方法是使用“稀疏矩阵”概念（而不是“图像压缩”概念），看起来有类似CRS或 CSR 的东西，我不太明白如何实现以及如何序列化正确地，甚至更少与图像压缩技术相比。

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

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

score 1 · Accepted Answer

提出的算法

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

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

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

它基于以下观察：

矩阵中的许多块是空的
足迹边界处的非空块通常有许多空单元（传感器上的“压力”/“无压力”转换是突然的）

_{[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

score 1 · Accepted Answer

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

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

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

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

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

2 回答 2

提出的算法

块编码示例

演示

Related

Reference