电子货架标签图像压缩算法

陈 丽，夏兴隆，吴振英

(1.苏州工业职业技术学院 电子与通信工程系，江苏 苏州 215104；2.苏州易泰勒电子科技有限公司 研发部，江苏 苏州 215123)

采用E-ink等反射型显示技术的电子货架标签已在各个应用领域受到广泛关注。电子货架标签的使用既可以通过减少纸张的使用、减少人力来降低使用成本[1]，又便于后台对于信息的集中化管理[2]。反射型显示技术结合低功耗通信技术可以极大降低能源消耗[3-4]，是取代传统纸标签的最佳方案。

如何变更显示内容是使用者关注的重点，采用无线技术变更显示内容是最为便捷的方式之一，这也是电子货架标签优于纸标签的另一大优点。对于无线通信而言，信息传输的准确率和速度是评价无线通信效率的两大重要指标。采用合适的图像压缩算法，可以极大减少传输的信息量，提高传输效率。电子货架标签主要采用二值化的图像，且传输过程中不能有信息丢失或错误，这将直接关系到再现内容的准确性。因此，对电子货架标签二值化图像的无损压缩效果将直接影响电子货架标签的通信效率。

目前，已经有很多关于无损压缩的报道，最常见的算法二值图像无损压缩算法有游长编码[5]、Huffman编码[6]、LZ77[7]等。基于这些算法，也有很多人提出了一些优化算法，并通过硬件进行实现[8-9]。对于电子货架标签而言，由于其图像内容的特点，并不是所有方法都适合这种应用领域。Robin Kuivinen曾经比较了7种图像压缩算法在电子货架标签中的压缩效果，其中，LowPac和FEG两种算法表现较好。在评价过程中，采用了压缩率、编解码时间、内存占用量作为评价参数。但是，大部分情况下，编码过程是在电脑中进行的，而并不是在电子货架标签中。大部分电脑的配置已经足够在很短时间内对图像进行编码，而且电子货架标签使用的图像通常都不大，因此，编码时间并不是一个重要的评价参数。一般情况下，解压缩算法是在电子货架标签中执行的，解压缩时间将直接影响电子货架标签工作效率。在Robin Kuivinen的研究中，LowPac和FEG算法在图像压缩时间方面都表现较好，但是在解压缩时间方面的表现较一般。字符编码也是图像压缩的常见方法，该方法可以显著提高通信速度。对于大部分应用来说，字符编码的压缩率非常高，且解压缩时间很短，对图像压缩效果较好。但是，这种方法需要额外的flash来存储字库内容。受限于字库内容，对于未存储的外国语言、特殊符号等，该方法不适用。可以通过扩大字库内容，实现更好的效果，但是需要更大的flash容量来支持，且字符编码方式不适合压缩图片内容。考虑到不同的应用场合，最优的图像压缩算法并不一定完全相同。探索适合不同应用需求的最佳算法，对于有效提升无线通信效率，满足实际应用需求，有着重要的意义。本研究结合电子货架标签图像特点，研究了不同的图像压缩算法。

1 图像压缩算法

考虑到Huffman等编码方式的编码长度可变，不适合本研究所采用的通信方式。同时，电子货架标签单片机解压缩能力、对解压缩时间尽可能短等需求，要求解压缩算法尽可能简单。因此，主要研究了两种图像压缩算法，包括优化的游程编码和字符编码。并且结合电子货架标签图像特点和自有通信协议对游程编码进行优化。

1.1 优化游程编码

游程编码是二值图像最常用的图像压缩算法之一。这种压缩方法的编解码算法都比较简单，内存占用不大，适合电子货架标签的应用。普通游程编码采用两位进行编码，其中一位表示重复信息的具体内容，另一位表示重复的长度。两种不同图像内容的游程编码结果如表1所示。

表1 游程编码结果

由表1可知，这种压缩算法，对于内容简单、游程长度很长的图像可以起到很好的压缩效果。但是对于游程长度短、内容复杂的图像来说，可能会增加更多的冗余信息。

本研究所采用的电子货架标签图像内容如图1所示，大部分图像主要用于超市货架标签和生产线。

对于大部分电子货架标签图像来说，白色像素游程很长。以图1(a)为例，最大的游程长度为1 060，需要用10比特才能表示。对于其他区域，尤其是有图片信息的区域，游程长度很短。结合通信方式考虑，通信采用ASCII码进行传输，10比特需要两个字节表示，的确可以大大减少传输信息。但是，对于较短游程的信息，1个比特就可以反映游程长度，剩余的7个比特并没有利用。因此，如果对于整图都采用同样的编码方式，将会产生大量冗余信息。

本研究提出了一种优化的游程编码方式，在图像压缩之前，先对图像内容进行预判断。针对不同的情况，采用不同的压缩编码，4种不同情况下的编码规则如图2所示。当游程长度小于阈值6时，不对图像进行压缩，原始图像的像素信息将被直接传输。当游程长度较长时，图像会被压缩以获取较好的压缩效果。如果游程长度大于256，将采用长压缩方式，这种压缩方式可以压缩最大达到65 536的长度。考虑到图像中，大部分游程小于256，如果仅采用长压缩方式，会产生大量冗余信息。因此，当游程长度大于64，且小于256时，采用中压缩方式。中压缩方式在编码过程中会比长压缩少一个字节。当游程长度小于64时，采用短压缩来进一步减少冗余信息。

图2 编码规则

对于不压缩，第一比特表示不进行压缩，剩余7个比特表示图像像素信息。对短压缩，第一比特表示进行压缩，第二比特表示后续重复像素的具体内容，如果为1，则后续均为黑色；如果为0，则后续均为白色。剩余6位表示游程长度。对中压缩和长压缩，第一字节均为信息字节，第一比特表示进行压缩，第二比特表示后续重复像素的具体内容。后6个比特表示长压缩还是中压缩。对于长压缩，后续2个字节表示游程长度；对于中压缩，后续1个字节表示游程长度。

1.2 字符编码

在仓库管理、生产线等实际应用场合，电子货架标签显示内容基本为字符，如图1(d)所示。采用字符编码方式可以大大提高传输效率和解压缩时间。采用这种方法，首先要将字符进行编码，并储存到flash中。本研究中，字库主要包含了中文、英文、数字、特殊字符等，但是未包含诸如俄文等特殊语言文字。字符编码无法压缩图片内容，例如图1(a)中的西瓜，对于这部分无法压缩的内容，则直接传输图片内容，不进行任何压缩处理。

2 计算结果及讨论

在进行算法评估前，必须先选择合适的评价指标。采用以下指标对两种算法进行评价，包括：压缩率、flash、内存占用量和解压缩时间。

表2和图3给出了不同算法对不同图像压缩率的计算结果。压缩率F=xout/xin，其中，xout为输出的二进制长度；xin为输入的二进制长度。

由图3结果可以看出，字符编码对图像的压缩率明显优于优化游程编码。采用优化游程编码，对大部分图片可以获取较好的压缩效果，最好的可以获取34.2%的压缩率，图像可以压缩至1/3左右。对于复杂内容的图像，压缩率大于50%，最差的达到61.2%，压缩效果一般。对于字符编码，压缩率大大降低，即使包含复杂图片内容，压缩率也可以达到22.2%。对于仅包含字符的图像内容，压缩率可达到2%～3%。由表2可以看出，两种算法压缩率的比值均大于2.3，大的可以达到30.7。意味着，采用字符编码，传输效率将提高至少2.3倍，甚至达到30.7倍。但是，对于这种算法来说，需要额外的16 M flash来存储字库信息，而采用优化游程编码则不需要额外flash。额外的flash将增加约2%的成本。

表2 不同算法对图像的压缩率

图3 优化游程编码与字符编码两种算法压缩率对比

对于其他参数来说，这两种算法表现均较好。解压缩时间均在ms级，这个时间已经可以适合大部分应用的需求。本研究对两种算法的内存占用量均由图像大小决定。

在实际应用中，不同的应用场合，最重要的参数也不同。当应用场合为超市这类需求量很大的场所时，电子货架标签的成本往往是最重要的考虑因素。大的内存占用量会导致成本增加，因此，在SRAM中执行的解压缩算法必须尽量简单，同时，额外增加的flash也是导致成本增加的因素之一。综合考虑，优化的游程编码算法是较好的选择。在另外一些应用场合，例如工厂生产线，电子货架标签将直接指导生产。信号传输时间和解压缩时间比成本更重要，大部分消费者可以接受增加的flash成本。因此，压缩率应尽可能减小，以便缩短传输时间。解压缩算法应该尽量简单来缩短解码时间。同时，这类应用场合中，图像内容以字符为主。因此，字符编码算法有较短的解压缩时间和优异的压缩率表现，将成为最佳方案。

3 结论

本研究比较了两种不同的图像压缩算法。优化游程算法可以获取小于61.2%的压缩率。字符编码可以得到更小的压缩率及更好的压缩结果，但额外的flash会导致成本增加。对于不同的应用，有不同的评价标准。当成本为第一考虑因素时，优化游程编码较好。当电子货架标签应用于生产线这类的场合时，传输速度和解压缩时间更重要，字符编码会得到更好的效果。

[1]GARAUS M.Shoppers' acceptance and perceptions of electronic shelf labels[J].Journal of Business Research，2016，69(9)： 3687-3692.

[2]张柯.基于电子标签的物流信息管理系统设计与实现[J].物流技术，2015，34：272-274.

[3]申倩楠.低功耗电子货架标签系统设计[D].杭州：杭州电子科技大学，2014.

[4]丁磊.基于蓝牙4.0的低功耗电子货架标签设计[J].电子技术应用，2014(5)：28-30.

[5]SOLOMON W.Golomb.run-length encodings[J].IEEE Transactions on Information Theory，1966，12(3)：399-401.

[6]DAVID A.HUFFMAN A.Method for the construction of minimum-redundancy codes[J].Proceedings of the Institute of Radio Engineers，1952，40(9)：1098-1101.

[7]JOCOB Z，ABRAHAM L.A universal algorithm for sequential data compression[J].IEEE Transactions on Information Theory，1977，23(3)：337-343.

[8]WANG C.A new encryption-then-compression algorithm using the rate–distortion optimization[J].Signal Processing Image Communication，2015(39)：141-150.

[9]邵龙.一种基于改进型游程编码的FPGA动态重构方法[J].电子器件，2014(5)：1009-1012.