基于Gzip壓縮算法的彩色QR碼生成與識別方法*

陳元枝 ，鄧 艷 ，史紹亮 ，姜文英

（1.桂林電子科技大學 電子工程與自動化學院，廣西 桂林 541004；2.中國科技開發院廣西分院，廣西 南寧 530022）

0 引言

傳統的黑白條碼由于其較強的解碼魯棒性和儲存容量，迅速成為自動識別領域的重要分支，國內外學者為了提高條形碼的數據容量進行了大量的研究。在一個有限的空間內增加信息密度的需求促進了彩色條碼的發展。ColorCode[1]首次使用顏色信息來提高數據容量，但ColorCode僅作為后臺數據庫的索引，不屬于信息攜帶型的條碼。內存碼[2](Paper Memory，PM)通過同一空間位置疊加多層QR碼來提高數據容量，但對解碼軟件顏色識別的要求過高。高容量的彩色條碼[3](High Capacity Color Barcode，HCCB)通過編碼 4色或8色的三角形符號集來提高數據容量，但HCCB碼掃描的魯棒性較差，缺乏明確的模式來支持檢測和定位過程。移動多彩色符合碼(Mobile Multi-Colour Composite，MMCC)[4]將編碼顏色增加為10種，數據容量增加至黑白QR碼的4倍，但MMCC碼無法正確解碼褶皺或邊緣彎曲的失真符號。Bulan[5]利用半色調點的方向模型在同一空間位置嵌入2種或3種不同顏色的獨立數據，再根據RGB和CMYK顏色空間光譜的互補特性將不同顏色的數據分離，數據容量為黑白QR碼的2倍或3倍。高容量的彩色二維條碼(High Capacity Colored Two Dimensional Codes，HCC2D)[6]在黑白 QR碼的基礎上，利用 Zxing[7]和 Libqrencode[8]兩個開源的庫實現了4色、8色和16色的彩色 QR碼，數據容量分別為黑白QR碼的2倍、3倍和4倍。

現存的彩色碼一般通過增加編碼顏色種類或在同一空間位置疊加多層彩色碼來提高數據容量，卻很少有彩色碼利用無損壓縮算法來提高數據容量。本文在Gzip壓縮算法的基礎上設計了一種彩色QR碼的生成和識別方法，通過增加編碼顏色種類和Gzip壓縮算法來提高數據容量。實驗證明了4色和16色QR碼在數據容量和計算復雜度方面的優越性。

1 彩色QR碼的生成與識別

1.1 彩色QR碼的設計思路

每個模塊可容納的比特數取決于使用的編碼顏色種類，用4種顏色編碼信息時，一個顏色模塊可容納2 bit，用8種顏色編碼信息時，一個顏色模塊可容納3 bit。以此類推，當編碼顏色數為2k種時，每個顏色模塊可容納kbit，即碼字總數、剩余位、數據碼字數、糾錯碼字數、糾錯的塊數等均變為黑白QR碼的k倍。

1.2 彩色QR碼尋像圖形的定位

彩色QR碼解碼過程中，檢測并定位尋像圖形是最開始也是最關鍵的步驟。檢測尋像圖形時，隔行遍歷彩色QR碼圖像，先在水平方向上統計彩色QR碼圖像中5種顏色的相對寬度比例是否為1:1:3:1:1，此處比例允許小于50%的偏差；滿足上述比例條件后，再垂直檢測彩色QR碼圖像中5種顏色的相對寬度比例是否為1:1:3:1:1，此處比例允許小于40%的偏差；滿足上述兩個比例條件后，再次檢測水平方向上彩色QR碼圖像中5種顏色的相對寬度比例是否為1:1:3:1:1，此處比例允許小于20%的偏差。偏差的存在主要是為了檢測扭曲、變形等失真的彩色QR碼。

1.3 彩色QR碼編碼

彩色QR碼的主要編碼過程如下：(1)輸入待編碼數據，生成源數據信息流；(2)用Gzip壓縮算法對源數據信息流進行壓縮；(3)根據黑白QR碼的編碼規則進行數據分析，形成數據碼字流；(4)根據數據碼字流的字節數，利用最小尺寸原則初始化彩色 QR碼；(5)在步驟(3)和步驟(4)的基礎上，用理德-所羅門碼(Reed-Solomon,RS)算法對數據碼字流進行分塊糾錯，形成糾錯碼字流；(6)將糾錯碼字流添加到數據碼字序列后，構成總碼字流；(7)填充尋像圖形、分隔符、定位圖形和校正圖形區域；(8)填充格式信息和版本信息區域；(9)用默認的掩膜圖形參考000對編碼區域的模塊圖形進行掩膜；(10)根據黑白QR碼符號字符的排列規則，在步驟(8)和步驟(9)的基礎上填充數據碼字和糾錯碼字區域；(11)根據預先設定的顏色映射表，將彩色QR碼保存為PNG格式。

1.4 彩色QR碼解碼

彩色QR碼的主要解碼過程如下：(1)加載并遍歷PNG格式的彩色QR碼圖像，獲得每個像素點的RGB值；(2)用尋像圖形的定位算法檢測3個位置探測圖形，若成功檢測到尋像圖形，則進入步驟(3)，否則進入步驟(11)；(3)返回3個位置探測圖形中心點的坐標值，若存在校正圖形，則返回校正圖形中心點的坐標值；(4)利用尋像圖形和校正圖形中心點的坐標，進行透視變換，柵格化彩色QR碼的顏色模塊；(5)根據預先設定的顏色映射表，識讀格式信息和版本信息；(6)去除掩膜，恢復數據碼字序列和糾錯碼字序列；(7)用RS算法進行錯誤檢查，若發現錯誤，則進入步驟(8)；否則進入步驟(9)；(8)用 RS算法分塊糾錯；(9)將數據解壓縮，恢復源數據信息流；(10)根據模式指示符和字符計數指示符，進行數據碼字譯碼，恢復編碼數據；(11)結束本次解碼。

2 仿真實驗

文章中的實驗是基于C#版Zxing庫進行的，測試QR碼的數據容量時，數字模式采用的數據集為“0123456789”共10個數字，字母數字模式采用的數據集為26個大寫字母，8位字節模式采用的數據集為26個小寫字母，中國漢字采用的數據集為GB2312第16區的94個漢字。該仿真實驗主要分析比較了2色、4色和16色QR碼數據容量和計算復雜度。

2.1 數據容量

增加彩色條碼的數據容量主要有兩種方式：(1)增加顏色塊的密度；(2)增加顏色種類。這兩種方法都有其局限性。當顏色塊的密度超過相機分辨率的極限以后，相鄰的顏色塊就無法區分了；而當顏色種類過多時，某種顏色可由多種顏色混疊得到。相鄰顏色塊之間的顏色混疊改變了原始顏色塊的顏色，因此顏色聚類的方法在存在顏色混疊時效果不佳。為了提高彩色條碼單位面積的信息嵌入率和解碼魯棒性，本文設計的彩色QR碼不進行偏色處理，提高數據容量主要通過Gzip的壓縮算法。

圖1列出了數字模式、字母數字模式、8位字節模式和中國漢字模式2色、4色和16色QR碼壓縮前后數據容量的曲線圖。由圖1可知，壓縮后2色、4色、16色QR碼分別從版本8、版本5、版本3開始有值，這是因為Gzip在尋找匹配串時利用哈希表來減小壓縮時間，Gzip的最小匹配長度為3 B，如果匹配串小于3 B的話，使用（匹配長度，相隔距離）對進行替換，不但沒有壓縮，反而還會增大[9]。而隨著編碼顏色的增加，單位面積的數據嵌入率逐漸提高，而Gzip的最大匹配長度是恒定的，所以16色QR碼僅需3個版本就足以容納哈希表的表頭。從圖1的曲線趨勢可看出，隨著版本號逐漸增加，數據容量增加的速度顯著提高，且隨著編碼顏色的增加，壓縮算法的優勢會更加明顯。

圖1 QR碼壓縮前后的數據容量

表1 黑白QR碼和彩色QR碼版本40-L壓縮前后的數據容量

由表1可知，Gzip的壓縮算法是本文提高數據容量最有效、最直接的方法。當編碼顏色分別為4種、16種時，壓縮前4色、16色QR碼的數據容量為黑白QR碼的2倍、4倍。采用Gzip壓縮算法后，中國漢字模式2色、4色、16色的數據容量分別為 85 081、191 775、405 149，與之對應的壓縮比分別為 46.82、52.77、55.74。8位字節模式2色、4色、16色的數據容量分別為 199 189、412 035、839 210，與之對應的壓縮比分別為 67.45、69.77、71.05。充分說明了該壓縮算法的有效性，且隨著編碼顏色的增多，壓縮比逐漸增大，即彩色QR碼的數據容量逐漸增加。

由表 2可知，常見黑白二維碼（Data Matrix、PDF417、QR碼）中QR碼的數據容量最大，而關濤[10]設計的 4色、8色、16色彩色DM碼的數據容量分別是黑白DM碼的2倍、3倍、4倍，16色DM碼跟黑白QR碼相比較，字母數字模式的容量擴充倍數最大，為黑白QR碼的2.17倍，袁遠松[11]設計的6色DM碼采取漢字的編碼長度與使用頻率成反比的編碼規則，使得中國漢字的數據容量高于16色DM碼，但壓縮比例最大的中國漢字模式的數據容量也僅為黑白QR碼的1.76倍。HCCB碼由于利用調色板來糾正彩色碼的偏色問題，調色板作為彩色碼的組成部分卻不能用來編碼數據信息，因此4色、8色的HCCB碼的數據容量略小于黑白QR碼的2倍、3倍。10色MMCC碼的數據容量也僅為黑白QR碼的4倍。4色、8色、16色的HCC2D碼的數據容量分別是黑白QR碼的2倍、3倍、4倍。而本文經過GZIP壓縮算法后4色QR碼的數據容量與黑白QR碼相比較，數字模式、字母數字模式、8位字節模式、中國漢字模式的數據容量分別擴充了 58.38倍、95.83倍、139.53倍、105.54倍。16色QR碼的數據容量與黑白QR碼相比較，數字模式、字母數字模式、8位字節模式、中國漢字模式的數據容量分別擴充了118.57倍、195.16倍、284.19倍、222.98倍。

表2 多種二維碼最大數據容量比較

由此可見，本文設計的彩色QR碼的數據容量與同類型的彩色碼相比，數據容量有明顯的優勢，且隨著顏色種類的增多，數據容量方面的優勢會更加明顯。

2.2 計算復雜度

彩色條碼相同的顏色模塊在不同光照下呈現的顏色不一樣，主流的彩色條碼為了解決偏色問題，將包含所有編碼顏色的調色板嵌入到條碼本身，并假定調色板和顏色模塊在不同光照下的顏色變化是相對一致的，解碼時將每一個顏色模塊與調色板中的顏色相比較，將歐式距離最小的顏色值視為最終解碼的顏色值，因此計算復雜度大幅增加。當調色板出現損毀、調色板和顏色模塊處于不均勻的光照下時，均會導致解碼失敗。

為了降低計算復雜度，提高數據容量和解碼正確率，本文設計的彩色QR碼不進行偏色處理。將編碼后的彩色QR碼保存為PNG格式，無損壓縮的圖片格式才能確保遍歷彩色QR碼時，精確識別每一個顏色模塊的RGB值，也正是因為如此，編碼顏色可以任意選取，才能利用Gzip的無損壓縮算法來提高數據容量。主流的彩色碼為了支持紙質檔的掃描，將編碼后的彩色碼保存為JPEG的有損壓縮格式，而壓縮算法在量化過程中會造成顏色信息的丟失，導致解碼魯棒性大幅降低。

3 總結

本文設計的彩色QR碼通過增加編碼顏色和Gzip的壓縮算法來提高數據容量，實驗表明，16色QR碼數字模式、字母數字模式、8位字節模式、中國漢字模式的數據容量分別為黑白QR碼的118.57倍、195.16倍、284.19倍、222.98倍，數據容量跟同類型的彩色碼相比有明顯的優勢，且編碼顏色可以任意選取，解碼魯棒性不會隨著環境光照的變化而降低，省去了主流彩色碼的顏色糾正步驟，因此計算量大幅降低。

[1]CHEOL-HO C，EUN-DONG S，NAM-KYU L，et al．Machine readable code image and method of encoding and decoding the same：United States，7020327[P].2002-03-07.

[2]ONODA T，MIWA K.Hierarchised two-dimensional code，creation method thereof，and read method thereof[J].Available at Japan Patent Office，2005，213336.

[3]Microsoft Research.High Capacity Color Barcodes.[EB/OL].(2007-03-19)[2010-5-15].http：//research.microsoft.com/projects/hccb/.

[4]KATO H，TAN K T，CHAI D.Novel colour selection scheme for 2D barcode[C].Proceedings of the 2009 Inter national Symposium on Intelligent Signal Processing and Communication Systems(ISPACS 2009).Kanazawa，2009：529-532.

[5]BULAN O，MONGA V，SHARMA G.High capacity color barcodes using dot orientation and color separability[C].Proceedings of SPIE on Media Forensics and Security.San Jose，2009：725417.

[6]QUERINI M，GRILLO A，LENTINI A，et al.2D color barcodes for mobile phones[J].International Journal of Computer Science and Applications(IJCSA)，2011，8(1)：136-155.

[7]CROSSING Z.Multi-format 1d/2d barcode image processing library with clients for android[EB/OL].[2012-03-21].http：//code.google.com/p/zxing/.

[8]FUKUCHI K.Libqrencode，a c library for encoding data in a qr code symbol[EB/OL].[2010-10-18].http：//megaui.net/fukuchi/works/qrencode/.

[9]湯維.32位壓縮程序在64位平臺上優化的研究與實現[D].西安：西安電子科技大學，2006.

[10]關濤.彩色Data Matrix條碼的設計以及若干問題的研究[D].北京：清華大學，2007.

[11]賈華國，袁遠松，劉志.一種面向漢字的高壓縮比彩色二維條碼的設計與實現[J].浙江工業大學學報，2010，38(05)：561-565.