嵌入式使用的轻量级(de)压缩算法

您可以考虑使用已经为类似您的场景开发的东西

https://github.com/atomicobject/heatshrink

https://spin.atomicobject.com/2013/03/14/heatshrink-embedded-data-compression/

“正确答案”即最终算法

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

解压代码非常短,可以很容易地写成状态机,只有一个指针和一个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值系统。

应注意的是,压缩比在某个点开始恶化。三值数据的压缩量不取决于灰度级的数量。灰度数据是未压缩的,八位字节数(几乎)与位数成线性关系。对于典型字体,8位的灰度数据为1/2。。占总数的2/3,但这在很大程度上取决于字体和大小。

因此,从8位减少到4位(在大多数情况下,视觉上很难察觉)通常会将压缩大小减少1/4。。1/3,而降低到三位所提供的进一步减少要少得多。对于这种压缩算法,两位数据没有意义。

如何建立字典?

可以说,我在这个领域缺乏理论知识,因此我认为会有很好的工具提供相当好的近似值。可能有这样的工具,但我找不到,所以我推出了自己的米老鼠版本。 编辑:早期的算法相当愚蠢;发现了一种更简单、更有效的方法

1. 从静态字典“0”、g、“1”开始(其中“g”表示中间值)
2. 将每个图示符的三元数据拆分为Trit列表
3. 找到最常见的项目连续组合(在第一次迭代时很可能是“0”、“0”)
4. 用组合替换所有出现的组合,并将组合添加到字典中(例如,如果“0”、“0”替换为“00”,则数据“0”、“1”、“0”、“0”、“g”将变为“0”、“1”、“00”、“g”)
5. 删除词典中任何未使用的项目(至少在理论上可能出现)

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

它工作得怎么样?

一个答案就足够了,但为了详细说明这一点,这里有一些数字。这是一种864字形的字体,典型字形大小为14x11像素,每像素8位。

• 香农熵(逐八位元):
  • 总计:528914位=66115个八位字节
  • 三值数据:176405位=22051个八位字节
  • 中间值:352509位=44064个八位字节
• 简单压缩三值数据(0=0,10=1,11=中间)(127101 trits):207505位=25939个八位字节
• 字典大小:647个八位字节
• 全压缩数据:647+18492+46697=65836个八位字节
• 压缩:48.2%

我们不做任何事情来压缩中间值,因为似乎没有任何有意义的模式。然而,我们用三元数据以明显的幅度击败了熵,甚至数据总量也低于熵极限。所以,我们可以做得更糟。

实际上,较小的字体很难压缩。这并不奇怪,因为大部分信息都在灰度信息中。使用该算法可以有效压缩超大字体,但游程压缩是一种更好的选择。

如果我知道,我会用它!但我仍然可以推测。

Jubatian 表明字体中会有很多重复。这对于发音符号来说一定是正确的,因为几乎所有的字体都有很多共同点。然而,在大多数字体中,像p和b这样的字母似乎不是这样。虽然基本形状很接近,但这还不够。(仔细的逐像素字体设计则是另一回事。)

不幸的是,这种不可避免的重复在较小尺寸的字体中并不容易利用。我试着创建一个包含所有可能扫描行的字典,然后只引用那些扫描行。不幸的是,不同扫描线的数量很高,因此引用增加的开销超过了好处。如果扫描线本身可以压缩,情况会有所改变,但每个扫描线的八位字节数很小,因此很难进行有效压缩。当然,这个问题取决于字体大小。

我的直觉告诉我,如果使用比全扫描线更长和更短的扫描线,这仍然是正确的方法。只有在有办法创建最佳字典的情况下,结合使用4位像素可能会产生非常好的结果。

这个方向的一个提示是LZMA2压缩文件(带有 xz 在最高压缩时,完整字体数据(127101个八位字节)只有36720个八位字节。当然,这种格式不满足任何其他要求(解压缩速度快,可以一个字形一个字形地解压缩,RAM要求低),但它仍然表明数据中存在比我的廉价算法能够利用的更多冗余。

每个字形的输出是字典中1-N个块的叠加;

• 预处理花费的cpu时间最多
• 每像素的预定解码时间(最大、平均或恒定N)增加
• 可控压缩大小(字典大小+x

有损

我会选择Clifford的答案,也就是说,首先将字体转换为每像素4位,这足以完成这项任务。

然后,因为这是一种字体,所以有很多行重复,即定义一个字符的行与另一个字符的行匹配。以字母“p”和“b”为例,这些字母的中间部分应该是相同的(如果目标语言使用大量的发音符号,则会有更多的匹配项)。然后,编码器可以首先收集字体的所有不同行,存储这些行,然后每个字符图像由指向这些行的指针列表组成。

效率取决于字体。当然,根据来源,您可能需要一些预处理,以便使用此方法更好地压缩。

如果你想要更多,你可能宁愿选择每像素3位,甚至每像素2位,这取决于你的目标(有些人会手动调整字体图像),这些可能仍然是令人满意的。

总的来说,这种方法对于实时显示效果很好(只需遍历指针即可获得行数据)。