賈華國,袁遠松,劉 志

(浙江工業(yè)大學軟件學院,浙江 杭州 310032)

條碼技術是集編碼、印刷、識別、數(shù)據(jù)采集和處理于一體的綜合技術.目前,黑白二維條碼技術發(fā)展已經趨于成熟,美國國家標準協(xié)會(ANSI)制定了二維條碼國際標準[1-2],包括 Data Matrix,PDF417,QR碼等.但隨著社會信息量增加以及條碼應用領域的拓寬,需要條碼能表示更多信息,而當前黑白二維條碼只使用兩種顏色,較大程度上限制了條碼信息容量的提高,此背景下,人們開始展開對彩色二維條碼的研究[3-4].目前,彩碼的研究工作屬于起步階段.微軟研究院在自主研發(fā)一款彩色二維條碼,發(fā)明人是Gavin Jancke,有四色和八色兩種版本,其最小單元是三角形,相對于黑白二維條碼,大約可以提高2～3倍的數(shù)據(jù)密度.韓國ColorZip公司也正在推出“彩色條碼”業(yè)務.但我國表達信息的語言為中文,當前流行的二維條碼包括微軟等在研發(fā)的彩色二維條碼,主要是針對英文字母與數(shù)字編碼,對中文漢字則使用漢字內碼來表示,對中文文本來說,這種編碼方式效率偏低.再次,使用國外標準還存在專利許可權等問題.針對以上情況,筆者在參照了Data Matrix碼國際標準后,設計一種具有較高容量且適合漢字編碼的彩色二維條碼,并將其實現(xiàn).

1 彩色二維條碼原理

1.1 信息容量

因黑白二維條碼通過將數(shù)據(jù)轉化成二進制流,而后根據(jù)0,1值進行黑白符號表示.所以,具有n個模塊的黑白二維條碼,每個模塊可表示0或者1,即每個模塊能表示2種可能,n個模塊的信息容量為2n.對于彩色條碼,假設顏色總數(shù)為k,通過擴展黑白二維條碼的符號化表示方式,使用不同顏色的模塊標識k進制數(shù)中各個對應的0,1,2,…,k-1,k.此時,具有n個模塊的彩色二維條碼能表示的信息容量為kn.故只要彩色條碼中選取的顏色總數(shù)大于2種,通過一定的編碼規(guī)則,可較大提高二維條碼信息容量.因考慮選取相互之間對比較明顯的顏色有助于提高識別效率,根據(jù)RGB彩色空間模型,其中黑,白 ,紅 ,綠 ,黃 ,藍 ,青 ,品紅等 8 種顏色之間的對比最明顯,故選取其中的前6種作為彩色條碼的顏色值,漢字庫編碼模式小節(jié)中將對此進行分析.

1.2 條碼結構

彩色二維條碼結構可分為兩部分:功能圖像和數(shù)據(jù)圖像(見圖1).功能圖像用于條碼的定位、校正.數(shù)據(jù)圖像則用來表示編碼后具體的數(shù)據(jù)信息.彩碼圖像由各個規(guī)則排列的正方形模塊組成,其空白處即為數(shù)據(jù)圖像區(qū)域.該功能圖像可更準確、有效的對條碼進行定位,解碼階段將對此進行具體分析.

圖1 彩色二維條碼結構Fig.1 Structure of color two-dimensional barcode

2 編碼原理

彩色二維條碼編碼過程分為三個順序步驟:數(shù)據(jù)信息編碼,糾錯碼生成,符號化過程.首先根據(jù)數(shù)據(jù)信息編碼模式將數(shù)據(jù)信息轉化為數(shù)據(jù)位流,并在開始處添加表示數(shù)據(jù)位流長度數(shù)構成新數(shù)據(jù)流.其次,將形成的數(shù)據(jù)流按4位組成碼字由Reed-Solomon糾錯算法生成糾錯碼字[5],添加到數(shù)據(jù)碼字之后形成總的數(shù)據(jù)碼字.最后,對總的數(shù)據(jù)碼字進行符號化,同時添加功能圖像,生成彩色條碼圖像.因糾錯碼Reed-Solomon糾錯算法已是成熟算法,故在編碼原理中只對彩色條碼數(shù)據(jù)信息編碼模式及符號化過程進行介紹.編碼流程見圖2.

圖2 編碼流程圖Fig.2 Encoding flow diagram

2.1 數(shù)據(jù)信息編碼模式

(1)漢字庫編碼模式

國標字符集中共有6 763個漢字和682個非漢字圖形符號.但教育部、國家語委通過統(tǒng)計和分析漢字使用情況可知,日常生活中常用的漢字數(shù)只有3 500個左右,最常用的600個漢字就可以覆蓋語料的80%,通過計算可知5進制數(shù)中5位最大數(shù)為44 4445對應于十進制的3 12410,通過使用兩位標識符可將漢字庫容量擴充至15 624,但3 124個漢字已覆蓋日常生活中99%的漢字,故其容量為3 124,且需加一位作為標識,所以最終將采用6進制,對應與彩色條碼顏色,即需采用6種顏色.

編碼規(guī)則:據(jù)清華大學統(tǒng)計的漢字頻度表建立漢字編碼庫,見表1.

表1 漢字庫編碼規(guī)則Table 1 Chinese Character Encoding Rules

(2)內碼編碼模式

內碼編碼模式是對漢字庫編碼模式的補充.針對漢字庫外的低頻漢字以及不常用的標點符號,使用漢字內碼進行編碼.

(3)單個ASCII編碼模式

針對單個ASCII進行編碼,模式標識符‘50',長度為6位.

(4)連續(xù)數(shù)字編碼模式

針對數(shù)字編碼,處理完畢后,在開始處加模式指示符‘515',結尾加結束模式指示符‘5',見表2.

表2 編碼模式規(guī)則表Table 2 Encoding rules

(5)連續(xù)ASCII編碼模式

編碼規(guī)則:將ASCII分為兩個集合S與R,見表3.

表3 集合S與R中的元素Table 3 Elements in set S and R

如:對連續(xù)字符‘AB'進行編碼,設碼值分別為a,b,見表4.

表4 連續(xù)ASCII編碼規(guī)則Table 4 Continuous ASCII encoding rules

處理完畢后,在開始與結尾處分別加入模式指示符‘505'與結束模式指示符‘505'.

2.2 符號化

數(shù)字轉化為顏色值時遵循映射關系,見表5.

表5 數(shù)字-顏色對應表Table 5 Digital-color mapping table

且對于整個彩色圖像來講,符號化的過程為從左到右,從下到上.并且在每個數(shù)據(jù)區(qū)域,也遵循從左到右,從下到上的順序.該順序如圖3所示.

圖3 ‘3205'符號化與符號化順序圖Fig.3 Symbolic and the symbolic sequence diagram

2.3 性能對比

相比與黑白二色條碼,設計的彩色二維條碼主要在數(shù)據(jù)容量與數(shù)據(jù)信息壓縮比上有所提高.

對于數(shù)據(jù)容量,通過前文設計原理部分已知:假設顏色總數(shù)為k,具有n個模塊的彩色二維條碼能表示的信息容量為kn,故對于黑白條碼來說,其信息容量為2n,對于設計的彩色二維條碼,因其使用6種顏色,故信息容量為 6n,當n＞=1時,6n＞2n,故在理論上,彩色二維條碼在信息容量上對比與黑白二色條碼有較大優(yōu)勢.

對于數(shù)據(jù)信息壓縮比,下面通過對一段新聞進行不同編碼來比較:“12月13日(北京時間9時00分左右),全國第二屆省級示范性軟件學院院長聯(lián)席會在我校舉行.”

此新聞中漢字和中文標點一共36個,ASCII碼字字符:8個,根據(jù)彩色條碼數(shù)據(jù)信息編碼規(guī)則,編碼后總的碼字位數(shù)為194位,各種編碼模式統(tǒng)計如表6所示,表中只顯示其中需要用到的編碼模式.

表6 編碼模式統(tǒng)計Table 6 Encoding mode statistics

若采用Data Matrix進行編碼,按照其編碼模式計算編碼長度:漢字和中文標點一共36個,需采用Base 256編碼模式,每個字符編碼需占用16位,再加上兩個碼字的長度計數(shù),漢字的編碼長度需36×16+16=592位,對數(shù)字、ASCII的編碼,只計算其最優(yōu)編碼情況下的編碼長度,不考慮模式切換所需要的碼字耗費,也需要40位:2×4+5.33×6≈40位,總共需要632位,兩者所需位數(shù)-相差632÷194≈3.25倍,故可知彩色條碼編碼效率即信息壓縮比更高.

圖4是對該段新聞進行編碼形成的圖片,分別使用彩色條碼編碼與Data Matrix編碼.通過對比兩張圖片可知.相同模塊下,彩色二維條碼的信息數(shù)據(jù)容量近似3.5倍于黑白二色的二維條碼.其中,有彩色條碼具有6種顏色所帶來的信息容量優(yōu)勢,也有采取多種編碼方式來提高信息的壓縮比所帶來的信息容量優(yōu)勢,特別是彩色條碼編碼階段加入漢字庫,通過獨有的漢字庫編碼來專門對漢字進行處理,取得對中文漢字的高壓縮比而獲得的信息容量優(yōu)勢.

圖4 彩色條碼圖與Data Matrix圖片F(xiàn)ig.4 Color barcode and data matrix barcode

3 解碼原理

前文已將彩色條碼設計及編碼原理介紹完畢,經對比,可知彩色二維條碼在數(shù)據(jù)信息容量以及漢字壓縮比上有較大優(yōu)勢.但同時因條碼圖像中含有多種顏色,也提高了條碼圖像的復雜度,對解碼過程各步驟的準確性提出更高要求.解碼過程見圖5,將圖中解碼過程分為3個主要步驟.

圖5 解碼流程圖Fig.5 Decoding flow diagram

3.1 定 位

解碼過程中定位是非常重要的一步,只有定位準確,才能為順利讀取條碼信息創(chuàng)造先決條件,若無法準確定位條碼圖像,則無法進行條碼的解碼步驟.為準確定位圖中彩色條碼的位置,可通過功能圖像來實現(xiàn)此功能,如圖6所示.

圖6 功能圖像Fig.6 Function image

因彩色條碼圖像中復雜度有所增加,故設計的功能圖像需具有較強的定位能力.以上圖片分別為功能圖像以及其在不同顏色通道下的顯示.其中,紅色通道下的功能圖像與Data Matrix編碼中的功能圖像基本一致,可參照該編碼標準中的定位算法.從理論上說,通過對紅色通道下的功能圖像進行Hough直線檢測已可進行準確定位,對于綠色通道與藍色通道的功能圖像,可在通過紅色通道下功能圖像無法實現(xiàn)準確定位時候,將其加入到定位步驟中,是對Data Matrix編碼定位的一種改進與補充.

3.2 顏色信息轉化數(shù)據(jù)位流信息

此步驟需完成兩個功能:檢測條碼規(guī)格即行列數(shù)目以及通過轉換算法將顏色信息轉換為數(shù)據(jù)位流信息.條碼規(guī)格檢測可通過計算定位坐標內一行圖像中像素的變化次數(shù)來得到,因條碼設計時呈正方形排列,故對于行列數(shù)目只要計算其中一項即可.得到條碼規(guī)格后,通過如下方法將顏色信息進行轉化,見圖7.

圖7 顏色轉化數(shù)字流程圖Fig.7 Flow diagram of color translating into digital

假設定位過程中得到的頂點坐標,因彩色條碼圖像為正方形,可設各頂點坐標為左上角P1(x1,y1),右上角 P2(x2,y1),左下角P3(x1,y2),右下角P4(x2,y2),且條碼規(guī)格為n.

則各個模塊大小為:

e=(x2-x1)/n或e=(y2-y1)/n,對位于第 I行第J列的模塊來講,其邊界坐標:

X軸方向為

Y軸方向為

統(tǒng)計該模塊邊界范圍內各像素的個數(shù),并取其中像素值最多的顏色值作為該模塊的顏色值,將該顏色轉化成對應的數(shù)字,這是為提高讀取顏色信息的正確率采取的措施,若對效率要求較高,則可直接取各模塊中心點像素值作為該模塊的顏色值,但相比與統(tǒng)計的方法,正確率較低,故還是采用統(tǒng)計像素個數(shù)的方法.因符號化過程中,數(shù)據(jù)是由倒正方形方式進行排放,將圖像信息轉成數(shù)據(jù)矩陣后,需按照符號化時順序對矩陣中數(shù)字進行讀取排列,組成數(shù)據(jù)位流信息.

3.3 數(shù)據(jù)信息進行解碼

經糾錯碼運算無誤后,首先讀取數(shù)據(jù)信息前5位數(shù)據(jù),將其轉成十進制數(shù)后可知數(shù)據(jù)信息長度.此時,可根據(jù)不同識別符,確定使用的編碼規(guī)則,對其進行逆操作完成對數(shù)據(jù)的解碼.表7為各模式下的指示符.

表7 數(shù)據(jù)信息編碼模式識別符Table 7 Identifier of data coding mode

4 實驗結果

因前文編碼原理階段已將彩色條碼性能進行說明,故這里只是對編解碼結果進行顯示.以下為對浙江工業(yè)大學網(wǎng)址“http://www.zjut.edu.cn:80”及名稱“浙江工業(yè)大學”進行編解碼,見圖8,9.

從圖中可知,彩色二維條碼編解碼已成功實現(xiàn),并且通過編碼原理中性能對比可知彩碼在信息容量與壓縮比上具有較大優(yōu)勢,特別是對漢字信息的壓縮比,相比于其他條碼標準,有了大幅度的提升.

5 結 論

筆者設計了一種彩色二維條碼,介紹了該條碼的編碼原理及解碼方法,在與Data Matrix碼的性能對比中,得到了相當好的效果.目前,解碼過程只是針對計算機生成的標準圖像進行處理,對實際拍攝中,圖像中可能存在的變形和偏色以及提高定位效率等方面還有待進一步研究,同時,對編碼和解碼的速度也需進一步提升,以適應實際應用.

[1] International Organization for Standardization.ISO/IEC16022—2000 Information technology international symbology speciation-data matrix[S].Switzerland:ISO,2004.

[2] PAVLIDIS T,SWARTZ J.Fundamentals of barcode information theory[J].IEEE Computer,1990,23(4):74-86.

[3] STEPHEN B.Reed-solomon codes and applications[M].New York:IEEE Press,1994.

[4] 關濤.彩色Data Matrix條碼的設計及其若干問題的研究[D].北京:清華大學,2006.

[5] 劉寧鐘,楊靜宇.三維條碼的編碼理論和設計[J].計算機學報,2007,30(4):686-687.