algorithm - 压缩/打包 "don' t care"位到 3 个状态

Question

目前我正在处理一个带有黑色、白色和透明像素的屏幕显示项目。 (这是一个开源项目:http://code.google.com/p/super-osd；它显示了正在开发中的 256x192 像素设置/透明 OSD，但我正在迁移到白色/黑色/透明 OSD。)

由于每个像素都是黑色、白色或透明的，我可以使用简单的 2 位/4 状态编码来存储黑色/白色选择和透明选择。所以我会有这样的真值表(x = 不关心):

B/W  T      
 x   0    pixel is transparent
 0   1    pixel is black
 1   1    pixel is white

然而，可以清楚地看到，当像素是透明时，这会浪费一位。我正在设计一个内存受限的微 Controller ，所以只要我能节省内存就很好。

所以我正在想办法将这 3 种状态打包成一些更大的单元(例如，一个字节。)我愿意使用查找表来解码和编码数据，因此可以使用复杂的算法，但它不能依赖于当前单位/字节之前或之后的像素状态(这排除了任何适当的数据压缩算法)并且大小必须一致；也就是说，具有所有透明像素的场景必须与具有随机噪声的场景相同。我想象的是密集十进制级别的东西，它仅将 3 x 4 位 (0-9) BCD 数字打包成 10 位，而 1024 中还剩下 24 种状态，这很棒。那么有人有什么想法吗？

有什么建议吗？谢谢!

Answer 1

在一个字节(256 个可能的值)中，您可以存储 5 个三位值。一种看待它的方式:3 的 5 次方是 243，略小于 256。它略微的事实也表明你没有浪费太多的一点点(几乎没有任何一个)。

为了将您的 3 位“数字”中的五个编码为一个字节，请考虑连续取一个由您的五个“数字”组成的基数为 3 的数字——结果值保证小于 243，因此直接可存储在一个字节中。同样，对于解码，对字节值进行 base-3 转换。