logo标签列表

在Java中压缩字节数组并在C中解压缩

javacembeddedcompression
6
我目前在Java程序中拥有以下数组：
byte[] data = new byte[800];

我想在通过串口（115200波特率）发送到微控制器之前压缩它。我想在C中在微控制器上解压缩数组。然而，我不太确定最佳的方法是什么。由于微控制器只是一个Arduino，因此性能是一个问题，不能占用太多内存/ CPU。数据更或多或少是随机的（编辑我想这不是真正的随机，见下面的编辑），因为它表示每16位的RGB颜色值。
您有什么好的方法来压缩这些数据吗？您认为我可能会获得多少压缩？ 编辑 抱歉缺乏信息。我需要压缩是无损的，并且我确实打算一次发送800个字节。我的问题是800个字节不足以以我使用的115200波特率的速度传输。我希望我可以稍微缩小大小以提高速度。
每两个字节看起来像：
0RRRRRGGGGGBBBBB
其中R、G和B位分别表示颜色通道红色、绿色和蓝色的值。然后，每两个字节是20x20网格中的单个LED。我想许多组两个字节将是相同的，因为我经常将相同的颜色代码分配给多个LED。RGB值也可能经常> 15，因为我通常在可以使用明亮颜色时使用它们（但是，这可能是一个无关紧要的问题，因为它们通常不会全部> 15）。
1
800字节并不是很多的数据……那只是为了举例，还是你将永远只发送这么少的数据？ - Rooke
3
良好的压缩非常取决于要压缩的数据的特性。如果您可以链接到一些代表性的数据样本，那么您将得到更好的答案。 - caf
这个问题的信息远远不足以合理地回答。如果您的数据确实是随机的，那么它是不可压缩的。如果您的数据代表某种图像，那么您可能会有好运。但是您没有指定什么类型的图像，也没有说明您是否准备容忍损失等因素。 - Oliver Charlesworth
我没有特别想法，但如果你有一个平台，在一端运行Java，另一端运行Arduino，并且你只发送Java到C，那么你可能在发送端有一个台式机/笔记本电脑，这种情况下你不需要对称压缩，但可以承受更高的CPU成本来压缩，而解压缩则可以像许多数字视频编解码器一样。 - Pete Kirkham
@Rook 他可能正在使用串行链接；在9600波特率下，800字节相当于三分之四秒的时间，这是一个相当长的时间。如果你在9600波特率的无线电链接上发送1.5K数据，第一个字节会在你完成传输之前到达月球。 - Pete Kirkham
额外的信息让我更有信心run-length编码适用于您。 您可以利用16位数据的ms位始终为0这一事实，以在此位上使用1有效地编码哨兵/魔术值。一个不错的改进可能是对LED地址进行修改。也就是说，不一定要将左上角的LED放在单词0处，将右下角的LED放在单词399处。使用不同的方案可能会更有利，使相邻的单词具有相同的值（颜色）。 - Bill Forster
7个回答
6
如果数据是“比较随机”的话，恐怕压缩它的成功率不高。 更新 根据新信息，我敢打赌你的LED显示屏不需要32k种颜色。我想一个1024或256种颜色的调色板可能就足够了。因此，你可以使用一个简单的压缩方案（只需通过查找表映射每个单词，或者可能只需丢弃每个组件的最低有效位），即使对于完全不相关的像素值也能起作用。
下投票者：请解释一下？这个答案非常认真；大多数其他答案都是基于假设数据有某种结构的建议。 - Oliver Charlesworth
我已经放弃了最低有效位，但不幸的是，最后一位非常明显（粉色变成了红色等）。我将尝试限制颜色数量，也许这样会更好运。 - Anon
1
@William：这很奇怪。我不会想到每个通道32种颜色的情况下，将值改变1会有任何明显的差异！（在MS Paint或其他软件中尝试一下...）你的显示器可能有一个奇怪的伽马曲线。 - Oliver Charlesworth
1
我认为您可能不小心丢失了最高有效位（MSB）。 大多数LED具有相当线性的特性。 - SurDin
哦，伙计，我刚刚才看到你的评论，但是回头看代码，这正是我在蓝色和绿色通道上所做的。我向左移了一个太多，并且同时删除了最高位和最低位。现在颜色看起来正确了！ - Anon
2
一个非常简单的压缩/解压算法是行程长度编码，它在微型嵌入式环境中实用且易于自定义。基本上，这意味着用（计数，值）对替换重复值的一串。当然，您需要一个特殊值（魔法值）来引入该对，然后需要一种机制来允许魔法值出现在正常数据中（通常可以使用转义序列来完成两项工作）。在您的示例中，最好使用16位值（2字节）。
但自然而然，这都取决于数据。根据定义，足够随机的数据是不可压缩的。您最好先收集一些示例数据，然后评估压缩选项。
额外信息发布后进行编辑：
仅为了好玩并展示行程长度编码有多容易，我编写了一些代码。由于我不是Java程序员，所以我使用C语言进行压缩。为保持简单，我完全使用16位数据。一种优化方法是在（计数，值）对中使用8位计数。我还没有尝试编译或测试此代码。另请参阅我在问题中关于搞乱LED地址可能带来的潜在好处的评论。
#define NBR_16BIT_WORDS 400
typedef unsigned short uint16_t;

// Return number of words written to dst (always
//  less than or equal to NBR_16BIT_WORDS)
uint16_t compress( uint16_t *src, uint16_t *dst )
{
    uint16_t *end = (src+NBR_16BIT_WORDS);
    uint16_t *dst_begin = dst;
    while( src < end )
    {
        uint16_t *temp;
        uint16_t count=1;
        for( temp=src+1; temp<end; temp++ )
        {
            if( *src == *temp )
                count++;
            else
                break;
        }
        if( count < 3 )
            *dst++ = *src++;
        else
        {
            *dst++ = (*src)|0x8000;
            *dst++ = count;
            *src += count;
        }
    }  
    return dst-dst_begin;
}

void decompress( uint16_t *src, uint16_t *dst )
{
    uint16_t *end_src = (src+NBR_16BIT_WORDS);
    uint16_t *end_dst = (dst+NBR_16BIT_WORDS);
    while( src<end_src && dst<end_dst )
    {
        data = *src++;
        if( (data&0x8000) == 0 )
            *dst++ = data;
        else
        {
            data  &= 0x7fff;
            uint16_t count = *src++;
            while( dst<end_dst && count-- )
                *dst++ = data;
        }
    }
}
1
运行长度编码对于16位图像数据来说可能不是非常有用，除非图像本身是由计算机生成的。 - caf
+1 .. 为了更好的压缩：将16位“高色深”像素拆分为红、绿、蓝三个部分。然后对每个部分进行简单的一阶预测，并单独对每个部分进行行程长度编码。这将给出三个比特流，它们容易解压缩。 - Nils Pipenbrinck
@caf 我在推荐时说了先收集一些数据来限定条件。有了一些数据，就很容易判断是否值得使用运行长度编码。基本上，我同意你对问题本身的评论。 - Bill Forster
当然，我发布的代码假定电线两端的CPU都是小端或大端。 - Bill Forster
2
2
首先需要做的一件事是将RGB转换为YUV或YCrCb等格式。完成后，通常可以将U和V（或Cr / Cb）通道的采样率降低到一半。这在大多数图像类型（例如JPEG和MPEG）中都很常见，并且大多数数码相机的传感器也会这样做。
实际上，从只有800字节的数据开始，大多数其他形式的压缩都将是浪费时间和精力。在取得任何成果之前，您需要付出相当多的努力（并且在Arduino上保持其相对较快也不容易）。
如果您绝对确定不能修改数据，则情况会变得非常困难。此时真正的问题是您正在处理什么类型的输入。其他人已经提到了类似于预测性增量压缩的可能性 - 例如，基于先前的像素，预测下一个像素可能是什么，然后仅编码预测值与实际值之间的差异。然而，要充分利用它，通常需要通过某种基于熵的算法（如Shannon-Fanno或Huffman压缩）运行结果。但是，它们通常不是最快的解压缩方法。
如果您的数据大多是图表或图形之类的东西，其中可以预期具有大面积相同像素，则运行长度编码可以很好地工作。这确实有一个优点，即解压缩非常简单。
我怀疑LZ压缩不会很好地工作。LZ压缩（通常）的工作原理是构建已看到的字节字符串的字典，并且当/如果再次看到相同的字节字符串时，传输分配给先前实例的代码，而不是重新传输整个字符串。问题在于您无法传输未压缩的字节-您首先发送表示该字节的代码字。在您的情况下，您可以使用（例如）10位代码字。这意味着第一次发送任何特定字符时，您需要将其作为10位发送，而不仅仅是8位。只有在字典中建立了一些更长的（两个字节，三个字节等）字符串并在输入中找到匹配字符串后，才开始获得一些压缩。
这意味着LZ压缩通常在前几百个字节左右的压缩效果相当差，然后在一段时间内达到平衡，只有在它跨越一些输入运行一段时间后，它才真正开始压缩得很好。在每次处理只有800字节的数据时，我不确定您是否会看到很多压缩-实际上，如果数据非常随机，则在相当规律的基础上看到数据膨胀也不会特别令人惊讶。
1
数据我觉得更或多或少是随机的，因为它代表了每16位的RGB颜色值。您有什么好的方法来压缩这些数据吗？您认为可能会获得多少压缩率呢？
理想情况下，如果整个图像都是相同的颜色，那么您可以将800字节的颜色数据压缩到一个字节。但正如Oli Charlesworth所提到的，数据越随机，您就越无法压缩它。如果您的图像看起来像电视上的静态画面，那么祝您好运，因为您很难从中获得任何压缩效果。
1

一定要考虑Oli Charlesworth的答案。在一个20x20的网格中，我不知道您是否需要完整的32k色彩调色板。

此外，在您之前所提出的问题中，您说您试图以20毫秒的周期（50赫兹）运行此程序。您真的需要这么快的显示速度吗？在115200 bps下，您可以传输约11520字节/秒 - 取10KBps作为安全裕量（例如，您的微控制器可能会在字节之间有延迟，您应该进行一些实验来查看“真实”带宽是多少）。在50 Hz下，这只允许您每个数据包约200个字节 - 您正在寻找75%以上的压缩比，这在任何情况下都可能无法实现。您似乎很满意您的要求，但现在也许是时候进行一次尴尬的交流了。

如果您确实想采用压缩方法，那么您可能需要尝试使用几种不同的算法来处理“真实”的数据，正如其他人所说，并尝试不同的编码方式。我敢打赌，在接收串行链接字节时（您将在字节之间有大约80微秒的时间），通过进行矩阵运算等操作，您可以找到一些额外的处理时间。如果您使用中断来读取串行数据而不是轮询，则可以使用双缓冲区，在读入当前缓冲区的同时处理/显示先前的缓冲区，这样您就可以做得相当不错。

编辑： 是否可能将串行端口速度提高到115200以上？亚马逊上的USB-serial adapter称其速度可达1 Mbps（实际上可能为921600 bps）。根据您的硬件和环境，您可能需要担心数据错误，但如果您增加速度足够快，您可能可以添加校验和甚至有限的纠错。

我对Arduino不熟悉，但我有一个8位的FreeScale HCS08驱动器，速度为1.25 Mbps，尽管总线实际上是运行RS-485而不是RS-232（485使用差分信号以获得更好的抗干扰性能），我没有任何噪声误差的问题。如果您可以将其连接到Arduino，则甚至可以考虑使用USB RS-485适配器（您需要转换硬件将485信号转换为Arduino的电平）。

编辑2： 如果您有可用的I2C或SPI接口，并且可以处理布线，则还可以考虑使用 USB-SPI/I2C适配器。它说它可以达到400 kHz的I2C或200 kHz的SPI，这仍然不够，但是您可以在SPI/I2C和您已经拥有的串行链接之间分割数据。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接