轻量级嵌入式压缩算法

Question

我有一个低资源的嵌入式系统，带有图形用户界面。界面需要字体数据。为了节省只读存储器（flash），字体数据需要被压缩。我正在寻找一种算法来实现这一目的。

要压缩的数据属性:

- 8位每像素的矩形像素映射的透明度数据 - 一个字体中通常有大约200到300个字形（在某个特定大小的字体中取样） - 每个字形通常从6x9到15x20个像素不等 - 因为抗锯齿的本质，有很多零（"无墨迹"）和略少于255（"完全墨迹"），否则八位组分布相当平均

压缩算法的要求:

- 解压算法的重要指标是数据大小加算法大小（因为它们将驻留在同样有限的内存中）。 - 解压缩可用的RAM非常少；可以解压缩单个字形的数据，但不能解压缩更多。 - 为使事情更加困难，该算法必须在32位微控制器（ARM Cortex-M内核）上非常快，因为需要在将字形绘制到显示器时解压缩字形。每个八位组十到二十个机器周期是可以接受的，一百个肯定太多了。 - 为使事情变得更容易，在压缩阶段期间有很多处理能力和内存可用，并且已知完整的数据语料库。

结论和想法:

- 由于相对较高的熵值，简单打包每个八位组的朴素方法效果不佳。 - 利用先前解压缩的数据的任何算法似乎行不通，因为无法存储其他字形的解压缩数据。这使得LZ算法的效率较低，因为它们只能参考少量的数据。 - 处理功率的限制似乎排除了大多数按位运算，即解压缩应逐个八位组进行处理。这使得哈夫曼编码困难，算术编码不可能。 - 问题似乎是静态字典编码的一个好候选人，因为所有数据都是预先知道的，并且数据在某种程度上具有重复性质（不同的字形共享相同的形状）。

问题:

- 如何构建一个好的词典？我知道找到某些数据的最优词典是一个np完全问题，但是否有合理好的近似值？我尝试过zstandard的词典生成器，但结果并不太好。 - 我的结论中是否有误？（我是否在错误的轨道上并漏掉了一些显而易见的东西？）

到目前为止最好的算法:

只是为了提供一些背景信息，我能够想出的最好的有用算法如下:

• 在单个字形的字体数据中，所有样本都被连接（展开）成一个一维数组（向量，表）。
• 每个样本有三种可能的状态：0、255和“其他”。
• 这些信息被连续的五个样本一组打包成一个5位三进制数（0..3^5）。
• 由于八位字节中有一些额外的值可用（2^8 = 256，3^5 = 243），它们被用来表示更长的0和255串。
• 对于每个“其他”值，实际值（1..254）存储在单独的向量中。

这些数据解压缩速度很快，因为基于3的值可以通过小型（243 x 3 = 729个八位字节）查找表解码为基于4的值。压缩比率高度依赖于字体大小，但对于我的典型数据，我可以获得大约1:2的比率。虽然这明显比LZ变体差一些（它们可以达到1:3左右），但我想尝试静态字典方法。

当然，通常的LZ变体使用Huffman或算术编码，这自然会使压缩后的数据更小。另一方面，我拥有所有的数据，并且压缩速度不是问题。这应该使寻找更好的字典成为可能。

由于数据的性质，我可以使用有损算法，但在这种情况下，最有可能的有损算法是减少像素数据中的量化级别。这不会很大程度上改变基本的压缩问题，而且我想避免由此产生的位对齐问题。

- DrV

Answer 1

我承认这个回答可能有点勉强算是对我的问题的好答案，但是由于我已经对这个问题进行了一些研究，这个回答描述了我选择的方法，并提供了更多关于该问题性质的信息，这对于遇到类似问题的人来说非常有用。

“正确的答案”即最终算法

我最终采用了与我在问题中描述的方法略有不同的变体。首先，每个字形被分成三个trits：0、1和中间值。然后，这个三进制信息被压缩到一个256个槽位的静态字典中。字典（或查找表）中的每个项目都是一个二进制编码的字符串（0=0，10=1，11=中间值），其最高有效位添加了一个1。

灰度数据（用于中间值的trits）被插入到对查找表的引用之间。因此，数据实际上看起来像这样：

<LUT reference><gray value><gray value><LUT reference>...

灰度值的数量自然取决于从静态字典中查找到的三进制数据中间trit的数量。

解压缩代码非常短，可以轻松地编写成一个状态机，只需要一个指针和一个32位变量即可确定状态。类似这样：

static uint32_t trits_to_decode;
static uint8_t *next_octet;

/* This should be called when starting to decode a glyph
   data : pointer to the compressed glyph data */
void start_glyph(uint8_t *data)
{
    next_octet = data;        // set the pointer to the beginning of the glyph
    trits_to_decode = 1;      // this triggers reloading a new dictionary item
}


/* This function returns the next 8-bit pixel value */
uint8_t next_pixel(void)
{
    uint8_t return_value;

    // end sentinel only? if so, we are out of ternary data
    if (trits_to_decode == 1)
        // get the next ternary dictionary item
        trits_to_decode = dictionary[*next_octet++];

    // get the next pixel from the ternary word
    // check the LSB bit(s)
    if (trits_to_decode & 1)
    {
        trits_to_decode >>= 1;
        // either full value or gray value, check the next bit
        if (trits_to_decode & 1)
        {
            trits_to_decode >>= 1;
            // grayscale value; get next from the buffer
            return *next_octet++; 
        }
        // if we are here, it is a full value
        trits_to_decode >>= 1;
        return 255;
    }

    // we have a zero, return it
    trits_to_decode >>= 1;
    return 0;
}

这段代码并没有以完全相同的形式测试过，所以可能会有错别字或其他小错误。

在移位操作中有很多重复。我不太担心，因为编译器应该能够清理它们。(实际上，左移可能更好，因为然后可以在移位后使用进位位。但由于在C中没有直接的方法来做到这一点，所以我不去烦恼。)

还有一种优化与字典(查找表)的大小有关。可能存在短和长的项，因此可以构建支持32位、16位或8位项的字典。在这种情况下，字典必须按照小数值引用32位项、中间值引用16位项和大数值引用8位项的顺序进行排序，以避免对齐问题。然后查找代码看起来像这样:

static uint8_t dictionary_lookup(uint8_t octet)
{
    if (octet < NUMBER_OF_32_BIT_ITEMS)
        return dictionary32[octet];
    if (octet < NUMBER_OF_32_BIT_ITEMS + NUMBER_OF_16_BIT_ITEMS)
        return dictionary16[octet - NUMBER_OF_32_BIT_ITEMS];
    return dictionary8[octet - NUMBER_OF_16_BIT_ITEMS - NUMBER_OF_32_BIT_ITEMS];
}

当然，如果每种字体都有其自己的词典，常量将变成从字体信息中查找的变量。由于该函数仅被调用一次，任何半靠谱的编译器都会内联该函数。

如果减少量化级别的数量，也可以处理。最简单的情况是使用4位灰度级(1..14)。这需要一个8位状态变量来保存灰度级别。那么，灰度级分支将变为：

// new state value
static uint8_t gray_value;
...

    // new variable within the next_pixel() function
    uint8_t return_value;

    ...

            // there is no old gray value available?
            if (gray_value == 0)
                gray_value = *next_octet++;
            // extract the low nibble
            return_value = gray_value & 0x0f;
            // shift the high nibble into low nibble
            gray_value >>= 4;
            return return_value;

实际上，这允许使用15个中间灰度级别（总共17个级别），这非常好地映射到线性的255值系统中。

三位或五位数据更容易打包成16位半字，并设置MSB始终为1。然后可以使用与三进制数据相同的技巧（移位直到获取1）。

应注意，在某些点处压缩比开始恶化。三进制数据的压缩量不取决于灰度级数。灰度级别数据未经压缩，八位情况下的八位数据数量（几乎）呈线性变化。对于典型字体，8位灰度级别数据占总数据的1/2..2/3，但这高度依赖于字体和大小。

因此，从8位降至4位（在大多数情况下在视觉上几乎不可感知）通常将压缩大小缩小1/4..1/3，而进一步降低至三位所提供的减小则明显较少。这种压缩算法不适用于两位数据。

如何构建字典？

如果解压缩算法非常简单快捷，则真正的难点在于字典构建。很容易证明存在最佳字典（对于给定字体提供最少的压缩八位数），但比我更聪明的人似乎已经证明了找到这样的字典是 NP-完全问题。

在我所欠缺的领域理论知识下，我认为会有很好的工具提供合理的好近似值。可能有这样的工具，但我找不到，所以我自己编写了一个 Mickey Mouse 版本。 编辑：早期算法相当幼稚；找到了一种更简单、更有效的方法

1. 从 '0'、'g' 和 '1' 的静态字典开始
2. 将每个字形的三进制数据拆分成 trits 列表
3. 查找最常见的连续项目组合（在第一次迭代中，它可能是 '0'、'0'）
4. 用该组合替换所有出现的组合，并将该组合添加到字典中（例如，如果将 '0','0' 替换为 '00'，则数据 '0'，'1'，'0'，'0'，'g' 将变为 '0'，'1'，'00'，'g'）
5. 删除字典中未使用的任何项（理论上它们可能出现）
6. 重复步骤3-5，直到字典满为止（即至少253轮）

这仍然是一种非常简单的方法，可能会产生非常次优的结果。它的唯一优点是它可行。

它的效果如何？

一个回答是足够好，但为了更详细地说明，下面是一些数字。这是一个包含864个字形、典型字形大小为14x11像素和每像素8位的字体。

• 原始未压缩大小：127101字节
• 中间值数量：46697
• Shannon熵（逐字节）：
  • 总共：528914位=66115字节
  • 三进制数据：176405位=22051字节
  • 中间值：352509位=44064字节
• 简单压缩的三进制数据（0=0，10=1，11=中间值）（127101个三进制数）：207505位=25939字节
• 字典压缩的三进制数据：18492字节
  • 熵：136778位=17097字节
• 字典大小：647字节
• 完整压缩数据：647+18492+46697=65836字节
• 压缩率：48.2%

与逐字节熵的比较非常有启示性。中间值数据的熵很高，而三进制数据可以被压缩。这也可以解释为原始数据中0和255的值很高（相对于任何中间值）。

我们没有做任何事情来压缩中间值，因为似乎没有任何有意义的模式。然而，我们通过三进制数据明显击败了熵，即使总数据量低于熵限制。所以，我们可以做得更好。

将量化级别降低到17会将数据大小减小到约42920字节（压缩率超过66%）。此时熵为41717字节，因此算法会略微变差，这是可以预料的。

在实践中，较小的字体大小很难压缩。这并不奇怪，因为灰度信息占据了更大的信息比例。非常大的字体大小使用这种算法可以高效地压缩，但是跑长压缩是一个更好的选择。

有什么更好的方法吗？

如果我知道，我会使用它！但我仍然可以推测。

Jubatian认为字体中会有很多重复。对于变音符号来说，这是正确的，因为aàäáâå在几乎所有字体中都有很多共同之处。然而，在大多数字体中，像p和b这样的字母似乎并不是如此。虽然基本形状接近，但还不够。（谨慎的逐像素字体设计则是另一回事。）

不幸的是，这种必然的重复在较小的字体大小中并不容易利用。我尝试创建一个包含所有可能扫描行的字典，然后仅引用这些扫描行。不幸的是，不同扫描行的数量很高，因此引用所添加的开销超过了好处。如果扫描行本身可以压缩，则情况会有所改变，但是每个扫描行的少量字节使得有效压缩变得困难。当然，这个问题取决于字体大小。

我的直觉告诉我，如果使用比完整扫描线更长或更短的运行方式，这仍然是正确的方法。使用4位像素结合这种方法可能会产生非常好的结果——只要有一种方法可以创建那个最佳字典。

朝着这个方向的一个提示是，完整字体数据（127101个八位字节）的LZMA2压缩文件（用xz进行最高压缩）仅占36720个八位字节。当然，这种格式不满足其他要求（快速解压缩，可以逐字解压缩，低内存需求），但它仍然显示出数据中存在比我的简单算法能够利用的更多冗余。

字典编码通常在字典步骤之后与Huffman或算术编码相结合。我们无法在这里这样做，但如果我们可以，将再节省4000个八位字节。

- DrV

---

感谢您抽出时间撰写这篇文章。非常有趣的阅读。我还想将其他人引导到这篇文章 https://dev59.com/VG865IYBdhLWcg3wivGi - Peter Gibson

Answer 2

您可以考虑使用已经为类似情境开发的工具。以下是相关链接供您参考： https://github.com/atomicobject/heatshrink https://spin.atomicobject.com/2013/03/14/heatshrink-embedded-data-compression/

- Marcin Gałczyński

---

我喜欢这个想法！有很多参数需要考虑。不幸的是，该算法似乎更适合处理较长的数据。如果我只能参考最后的1024个八位字节，那么我会错过数据中很多重复的部分（例如，字符a、á、à、å和ä尽管在字符表中位置不同，但它们有很多共同之处）。此外，我很可能需要逐个压缩字符以使我能够解压缩单个字符。 - DrV

Answer 3

我会选择Clifford的答案，即先将字体转换为每像素4位，这对于此任务已足够。由于这是一种字体，所以有许多行重复，即定义一个字符的行与另一个字符的行匹配时。例如，取字母'p'和'b'，这些字母的中间部分应该是相同的（如果目标语言使用大量变音符号，则会有更多的匹配）。然后，您的编码器可以首先收集字体的所有不同行，存储这些行，然后每个字符图像由指向这些行的指针列表组成。效率当然取决于字体，根据来源，您可能需要一些预处理才能更好地压缩它。如果您想要更多，您可能会选择每像素3位甚至每像素2位，这取决于您的目标（以及手动调整字体图像的一些需求），这些仍然可能令人满意。总的来说，这种方法对于实时显示非常有效（您只需要遍历指向行数据的指针）。

- Jubatian

---

请看我的回答结尾。静态字典很棒，只要有实际的构建方法... - DrV

Answer 4

你可以尝试使用自定义字典的稀疏表示进行有损压缩。每个字形的输出是字典中1-N个块的叠加；大部分CPU时间花费在预处理上；解码时间预先确定（最大、平均或固定N）每像素增加次数；可控制的压缩大小（字典大小+xyn个代码每个字形）。

- Aki Suihkonen

---

这是一个有趣的问题！如果我理解正确，这个想法是找到一组（字典）字形部件，这些部件可以逐像素地组合成最终的字形。在某种意义上，我会有一个“笔画”库，然后将它们组合成字形。虽然在线性领域中事情最简单，但我可以想象在过程中使用一些饱和算术。不幸的是，我对此进行的初步试验并不令人鼓舞，但是否有任何工具可以尝试？ - DrV

这似乎是一个完整的工具--http://www.ux.uis.no/~karlsk/ICTools/ictools.html 无论如何，适用性基本取决于用于组合字母的算法--而我没有第一手经验。 - Aki Suihkonen

谢谢！我会看一下的！ - DrV

Answer 5

似乎最简单的有损方法是减少每像素的位数。对于这种大小的字形，16个级别可能足够了。这将立即使数据减半，然后您可以在值为0、16或“其他值”上应用现有算法，进一步将其减半。

- Clifford

---

这正是我在问题结尾所说的。特别是4位像素会更容易处理。然而，虽然灰度数据量减半，但暗/灰/亮三元组的数量仍然相同。这使得我的自制算法不太高效。字典压缩不会遇到同样的问题，但大多数字典压缩算法都使用八位字节（而不是4位实体）。 - DrV