電子貨架標簽圖像壓縮算法

陳 麗，夏興隆，吳振英

(1.蘇州工業(yè)職業(yè)技術學院 電子與通信工程系，江蘇 蘇州 215104；2.蘇州易泰勒電子科技有限公司 研發(fā)部，江蘇 蘇州 215123)

采用E-ink等反射型顯示技術的電子貨架標簽已在各個應用領域受到廣泛關注。電子貨架標簽的使用既可以通過減少紙張的使用、減少人力來降低使用成本[1]，又便于后臺對于信息的集中化管理[2]。反射型顯示技術結合低功耗通信技術可以極大降低能源消耗[3-4]，是取代傳統(tǒng)紙標簽的最佳方案。

如何變更顯示內容是使用者關注的重點，采用無線技術變更顯示內容是最為便捷的方式之一，這也是電子貨架標簽優(yōu)于紙標簽的另一大優(yōu)點。對于無線通信而言，信息傳輸的準確率和速度是評價無線通信效率的兩大重要指標。采用合適的圖像壓縮算法，可以極大減少傳輸的信息量，提高傳輸效率。電子貨架標簽主要采用二值化的圖像，且傳輸過程中不能有信息丟失或錯誤，這將直接關系到再現內容的準確性。因此，對電子貨架標簽二值化圖像的無損壓縮效果將直接影響電子貨架標簽的通信效率。

目前，已經有很多關于無損壓縮的報道，最常見的算法二值圖像無損壓縮算法有游長編碼[5]、Huffman編碼[6]、LZ77[7]等?；谶@些算法，也有很多人提出了一些優(yōu)化算法，并通過硬件進行實現[8-9]。對于電子貨架標簽而言，由于其圖像內容的特點，并不是所有方法都適合這種應用領域。Robin Kuivinen曾經比較了7種圖像壓縮算法在電子貨架標簽中的壓縮效果，其中，LowPac和FEG兩種算法表現較好。在評價過程中，采用了壓縮率、編解碼時間、內存占用量作為評價參數。但是，大部分情況下，編碼過程是在電腦中進行的，而并不是在電子貨架標簽中。大部分電腦的配置已經足夠在很短時間內對圖像進行編碼，而且電子貨架標簽使用的圖像通常都不大，因此，編碼時間并不是一個重要的評價參數。一般情況下，解壓縮算法是在電子貨架標簽中執(zhí)行的，解壓縮時間將直接影響電子貨架標簽工作效率。在Robin Kuivinen的研究中，LowPac和FEG算法在圖像壓縮時間方面都表現較好，但是在解壓縮時間方面的表現較一般。字符編碼也是圖像壓縮的常見方法，該方法可以顯著提高通信速度。對于大部分應用來說，字符編碼的壓縮率非常高，且解壓縮時間很短，對圖像壓縮效果較好。但是，這種方法需要額外的flash來存儲字庫內容。受限于字庫內容，對于未存儲的外國語言、特殊符號等，該方法不適用。可以通過擴大字庫內容，實現更好的效果，但是需要更大的flash容量來支持，且字符編碼方式不適合壓縮圖片內容?？紤]到不同的應用場合，最優(yōu)的圖像壓縮算法并不一定完全相同。探索適合不同應用需求的最佳算法，對于有效提升無線通信效率，滿足實際應用需求，有著重要的意義。本研究結合電子貨架標簽圖像特點，研究了不同的圖像壓縮算法。

1 圖像壓縮算法

考慮到Huffman等編碼方式的編碼長度可變，不適合本研究所采用的通信方式。同時，電子貨架標簽單片機解壓縮能力、對解壓縮時間盡可能短等需求，要求解壓縮算法盡可能簡單。因此，主要研究了兩種圖像壓縮算法，包括優(yōu)化的游程編碼和字符編碼。并且結合電子貨架標簽圖像特點和自有通信協(xié)議對游程編碼進行優(yōu)化。

1.1 優(yōu)化游程編碼

游程編碼是二值圖像最常用的圖像壓縮算法之一。這種壓縮方法的編解碼算法都比較簡單，內存占用不大，適合電子貨架標簽的應用。普通游程編碼采用兩位進行編碼，其中一位表示重復信息的具體內容，另一位表示重復的長度。兩種不同圖像內容的游程編碼結果如表1所示。

表1 游程編碼結果

由表1可知，這種壓縮算法，對于內容簡單、游程長度很長的圖像可以起到很好的壓縮效果。但是對于游程長度短、內容復雜的圖像來說，可能會增加更多的冗余信息。

本研究所采用的電子貨架標簽圖像內容如圖1所示，大部分圖像主要用于超市貨架標簽和生產線。

對于大部分電子貨架標簽圖像來說，白色像素游程很長。以圖1(a)為例，最大的游程長度為1 060，需要用10比特才能表示。對于其他區(qū)域，尤其是有圖片信息的區(qū)域，游程長度很短。結合通信方式考慮，通信采用ASCII碼進行傳輸，10比特需要兩個字節(jié)表示，的確可以大大減少傳輸信息。但是，對于較短游程的信息，1個比特就可以反映游程長度，剩余的7個比特并沒有利用。因此，如果對于整圖都采用同樣的編碼方式，將會產生大量冗余信息。

本研究提出了一種優(yōu)化的游程編碼方式，在圖像壓縮之前，先對圖像內容進行預判斷。針對不同的情況，采用不同的壓縮編碼，4種不同情況下的編碼規(guī)則如圖2所示。當游程長度小于閾值6時，不對圖像進行壓縮，原始圖像的像素信息將被直接傳輸。當游程長度較長時，圖像會被壓縮以獲取較好的壓縮效果。如果游程長度大于256，將采用長壓縮方式，這種壓縮方式可以壓縮最大達到65 536的長度。考慮到圖像中，大部分游程小于256，如果僅采用長壓縮方式，會產生大量冗余信息。因此，當游程長度大于64，且小于256時，采用中壓縮方式。中壓縮方式在編碼過程中會比長壓縮少一個字節(jié)。當游程長度小于64時，采用短壓縮來進一步減少冗余信息。

圖2 編碼規(guī)則

對于不壓縮，第一比特表示不進行壓縮，剩余7個比特表示圖像像素信息。對短壓縮，第一比特表示進行壓縮，第二比特表示后續(xù)重復像素的具體內容，如果為1，則后續(xù)均為黑色；如果為0，則后續(xù)均為白色。剩余6位表示游程長度。對中壓縮和長壓縮，第一字節(jié)均為信息字節(jié)，第一比特表示進行壓縮，第二比特表示后續(xù)重復像素的具體內容。后6個比特表示長壓縮還是中壓縮。對于長壓縮，后續(xù)2個字節(jié)表示游程長度；對于中壓縮，后續(xù)1個字節(jié)表示游程長度。

1.2 字符編碼

在倉庫管理、生產線等實際應用場合，電子貨架標簽顯示內容基本為字符，如圖1(d)所示。采用字符編碼方式可以大大提高傳輸效率和解壓縮時間。采用這種方法，首先要將字符進行編碼，并儲存到flash中。本研究中，字庫主要包含了中文、英文、數字、特殊字符等，但是未包含諸如俄文等特殊語言文字。字符編碼無法壓縮圖片內容，例如圖1(a)中的西瓜，對于這部分無法壓縮的內容，則直接傳輸圖片內容，不進行任何壓縮處理。

2 計算結果及討論

在進行算法評估前，必須先選擇合適的評價指標。采用以下指標對兩種算法進行評價，包括：壓縮率、flash、內存占用量和解壓縮時間。

表2和圖3給出了不同算法對不同圖像壓縮率的計算結果。壓縮率F=xout/xin，其中，xout為輸出的二進制長度；xin為輸入的二進制長度。

由圖3結果可以看出，字符編碼對圖像的壓縮率明顯優(yōu)于優(yōu)化游程編碼。采用優(yōu)化游程編碼，對大部分圖片可以獲取較好的壓縮效果，最好的可以獲取34.2%的壓縮率，圖像可以壓縮至1/3左右。對于復雜內容的圖像，壓縮率大于50%，最差的達到61.2%，壓縮效果一般。對于字符編碼，壓縮率大大降低，即使包含復雜圖片內容，壓縮率也可以達到22.2%。對于僅包含字符的圖像內容，壓縮率可達到2%～3%。由表2可以看出，兩種算法壓縮率的比值均大于2.3，大的可以達到30.7。意味著，采用字符編碼，傳輸效率將提高至少2.3倍，甚至達到30.7倍。但是，對于這種算法來說，需要額外的16 M flash來存儲字庫信息，而采用優(yōu)化游程編碼則不需要額外flash。額外的flash將增加約2%的成本。

表2 不同算法對圖像的壓縮率

圖3 優(yōu)化游程編碼與字符編碼兩種算法壓縮率對比

對于其他參數來說，這兩種算法表現均較好。解壓縮時間均在ms級，這個時間已經可以適合大部分應用的需求。本研究對兩種算法的內存占用量均由圖像大小決定。

在實際應用中，不同的應用場合，最重要的參數也不同。當應用場合為超市這類需求量很大的場所時，電子貨架標簽的成本往往是最重要的考慮因素。大的內存占用量會導致成本增加，因此，在SRAM中執(zhí)行的解壓縮算法必須盡量簡單，同時，額外增加的flash也是導致成本增加的因素之一。綜合考慮，優(yōu)化的游程編碼算法是較好的選擇。在另外一些應用場合，例如工廠生產線，電子貨架標簽將直接指導生產。信號傳輸時間和解壓縮時間比成本更重要，大部分消費者可以接受增加的flash成本。因此，壓縮率應盡可能減小，以便縮短傳輸時間。解壓縮算法應該盡量簡單來縮短解碼時間。同時，這類應用場合中，圖像內容以字符為主。因此，字符編碼算法有較短的解壓縮時間和優(yōu)異的壓縮率表現，將成為最佳方案。

3 結論

本研究比較了兩種不同的圖像壓縮算法。優(yōu)化游程算法可以獲取小于61.2%的壓縮率。字符編碼可以得到更小的壓縮率及更好的壓縮結果，但額外的flash會導致成本增加。對于不同的應用，有不同的評價標準。當成本為第一考慮因素時，優(yōu)化游程編碼較好。當電子貨架標簽應用于生產線這類的場合時，傳輸速度和解壓縮時間更重要，字符編碼會得到更好的效果。

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

[2]張柯.基于電子標簽的物流信息管理系統(tǒng)設計與實現[J].物流技術，2015，34：272-274.

[3]申倩楠.低功耗電子貨架標簽系統(tǒng)設計[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動態(tài)重構方法[J].電子器件，2014(5)：1009-1012.