基于改進(jìn)凸包算法的移動端條碼圖像定位與校正

魯 劍,劉 志

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

Data Matrix條碼屬于矩陣式二維條碼,其尺寸與編入資料量相互獨(dú)立,最小尺寸達(dá)到所有條碼之最,由此特別適合標(biāo)識小物品;同時它采用 Reed-Solomon交織交叉編碼,編碼時加入糾錯碼,最少只需讀取20%圖像信息,即使大面積受損仍不影響準(zhǔn)確識別.

Data Matrix條碼是由黑白相間的小方格(模塊)組成的正方形或長方形.Data Matrix符號由排列規(guī)則的正方形模塊組構(gòu)成的資料區(qū)組成,資料區(qū)的四周由定位圖形(Finder Pattern)所包圍,定位圖形的四周再由空白區(qū)包圍.定位圖形是資料區(qū)域的一個周界,為一個模組寬度.其中兩條“L”形鄰邊為暗實(shí)線,主要用于限定物理尺寸、定位和符號失真.另兩條鄰邊由交替的黑色和白色模塊(Module)組成,主要用于限定符號的單元結(jié)構(gòu),但也能幫助確定物理尺寸及失真[1].Data Matrix以資料區(qū)中的模塊來表示信息,每個模塊代表一個位信息0或1,其中黑色模塊代表1,白色信息代表0.Data Matrix可編碼字元集包括全部的ASCII字元及擴(kuò)充ASCII字元,可表示字母、漢字、圖像等信息.Data Matrix條碼最大可以容納3 116個數(shù)字信息,2 335個文字?jǐn)?shù)字信息,1 556個位信息.

1 移動端基于改進(jìn)凸包的條碼圖像定位

1.1 凸包相關(guān)內(nèi)容

1.1.1 上、下凸包

所謂的上凸包(upper hull),就是從最左端頂點(diǎn)P1出發(fā),沿著凸包順時針行進(jìn)到最右端頂點(diǎn)Pn之間的那段,換言之,組成上凸包的,就是從上方界定凸包的那些邊,此后,再自右向左進(jìn)行一次掃描,計算出凸包的剩余部分——下凸包(lower hull),如圖1所示.

圖1 上、下凸包Fig.1 Right turn

1.1.2 右拐

對三個點(diǎn)進(jìn)行比較,判斷它們是構(gòu)成左拐還是右拐的時候,有可能它們恰好共線.在這種情況下,居中的那些點(diǎn)不應(yīng)該出現(xiàn)在最后的凸包上,因此只有在三個點(diǎn)的確構(gòu)成一個右拐的時候本文才認(rèn)可為右拐[2],如圖 2所示.

圖2 右拐Fig.2 Upper and lower hull

1.2 凸包檢測前的點(diǎn)集簡化處理

針對手機(jī)端實(shí)時性要求和硬件限制[3],通過手機(jī)攝像頭捕獲的初始二維條碼圖像(圖3),經(jīng)加權(quán)平均法灰度化,快速自適應(yīng)閾值Otsu法二值化(圖4),然后經(jīng)Sobel算子分別用水平和垂直檢測模板圖像進(jìn)行卷積,邊緣檢測效果見圖5.

智能手機(jī)(Smart phone)相比傳統(tǒng)PC普遍存在主頻不高、內(nèi)存有限等問題[4],由此篩選邊緣檢測后的條碼像素點(diǎn),只提取黑色像素點(diǎn)加入凸包檢測點(diǎn)集,減輕運(yùn)算量.

由于凸包內(nèi)部點(diǎn)集顯然不可能成為最后的凸包頂點(diǎn),并且這部分往往數(shù)目巨大,剔除內(nèi)部點(diǎn)集可以大大減少后續(xù)計算量,提高手機(jī)處理效率.

首先引入叉乘:兩個向量進(jìn)行叉乘得到的是一個向量,方向垂直于這兩個向量構(gòu)成的平面,大小等于這兩個向量組成的平行四邊形的面積,因此對任何三點(diǎn)構(gòu)成的兩個向量取模后再取1/2即得到由此三角形面積.

(1)在經(jīng)邊緣檢測后的二維條碼圖像上不難找到如下四個最值點(diǎn):最左端點(diǎn),最右端點(diǎn),最頂端點(diǎn),最底端點(diǎn),分別記為 minPx,maxP x,minPy,maxPy.

(2)任何一點(diǎn)P與此四最值點(diǎn)構(gòu)成的四個三角形面積之和如果等于四最值點(diǎn)構(gòu)成的四邊形面積,那么點(diǎn)P位于四邊形內(nèi)部或者在四邊形邊上,否則點(diǎn)P位于四邊形之外.

(3)通過此方法我們?nèi)コ钪邓倪呅蝺?nèi)部點(diǎn)和邊點(diǎn)集,將四個最值點(diǎn)和界外剩余點(diǎn)加入點(diǎn)集進(jìn)行凸包檢測.

通過叉乘方式刪除這部分非凸包頂點(diǎn)序列,可以大大減少進(jìn)行凸包運(yùn)算的點(diǎn)集數(shù)目.如圖6所示,由a,b,c,d四邊所構(gòu)成的四邊形上以及其內(nèi)部點(diǎn)將被刪除,進(jìn)行凸包運(yùn)算只有四邊形外的點(diǎn)集以及四邊形四頂點(diǎn),這部分點(diǎn)集數(shù)目相對不處理前大為縮減.

圖6 刪除內(nèi)部和邊上的點(diǎn)集Fig.6 Delete interior and edge points

1.3 Graham凸包頂點(diǎn)檢測

為避免實(shí)際二維條碼圖像可能存在的毛刺等問題,使用字典序排列點(diǎn)集,即不僅僅根據(jù)各點(diǎn)的x坐標(biāo)來確定先后次序,首先按照x坐標(biāo)排序;如果存在多個x坐標(biāo)相同點(diǎn),進(jìn)而按照y坐標(biāo)為它們排序 .

凸包算法通常分為增量方法(incremental method)、包裹法(Jarvis march)及分治法(divide-and-conquer method)等,這里采用Graham掃描法(Graham's scan),其應(yīng)用“旋轉(zhuǎn)掃除”(rotational sweep)技術(shù),通過判斷各個頂點(diǎn)相對參照頂點(diǎn)的極角值大小依次處理,Graham掃描法運(yùn)行時間為O(nlgn).

經(jīng)過上述步驟簡化處理的條碼圖像,設(shè)其點(diǎn)集序列為p1,p2,… ,pn.

(1)將最左端點(diǎn)p1及其鄰點(diǎn)p2加入lupper.

(2)把p3,… ,pn逐個加入lupper,通過判斷末尾三點(diǎn)末是否構(gòu)成右拐的方式得到上凸包點(diǎn)集lupper.

(3)采用相似方法從相反方向掃描點(diǎn)集,得到下凸包點(diǎn)集llow er,將其與上凸包合并,去除重復(fù),得到凸包頂點(diǎn)序列∑(P).

1.4 精簡凸包頂點(diǎn)

標(biāo)準(zhǔn)Data Matrix條碼圖像經(jīng)過凸包檢測必將得到5個凸包頂點(diǎn),但是對于實(shí)際條碼圖像來講情況并非如此,圖6經(jīng)過凸包檢測后的頂點(diǎn)集中就存在22個頂點(diǎn),其原因?yàn)閷?shí)際條碼圖像很難達(dá)到標(biāo)準(zhǔn)圖的精準(zhǔn)程度,5個頂點(diǎn)周邊存在干擾點(diǎn)的現(xiàn)象以及邊框上存在凸起像素點(diǎn)的現(xiàn)象不在少數(shù),去除這些干擾點(diǎn)可以大大提高條碼定位精準(zhǔn)度.

對于凸包頂點(diǎn)集∑(P)中任何一點(diǎn)Pi,分別找到其相鄰兩點(diǎn),記為last和next,其本身設(shè)為current(圖7).通過計算斜率值并由反三角函數(shù)分別得到相鄰兩邊的角度值,記為t1和t2,如若兩角度差值|t1-t2|小于某一閾值,則可將三點(diǎn)認(rèn)為近似共線.經(jīng)統(tǒng)計分析,得到閾值 13,記為 minimunDifference.同時得到current,next兩點(diǎn)之間的距離,記為sideLength.如若同時滿足條件:角度差值|t1-t2|＜minimunDifference以及sideLength＜10,閾值10為經(jīng)統(tǒng)計分析所得,則排除該點(diǎn).由此排除實(shí)際條碼圖像頂點(diǎn)附近存在的干擾點(diǎn)以及各條邊上存在的凸起像素點(diǎn).

圖7 通過角度篩選凸包頂點(diǎn)Fig.7 Delete points through angle

1.5 擬合條碼圖像

(1)得到二維條碼圖像的凸包頂點(diǎn)序列后,依次連接Pi,Pi+1點(diǎn),首尾相接形成多邊形.

(2)計算Pi,Pi+1所成邊的邊長,保留長度值最大的四條邊記為edge0,edge1,edge2,edge3.

(3)依次將四條邊edge0,edge1,edge2,edge3與其余各邊相交得交點(diǎn)(intersaction),排除重復(fù)交點(diǎn),最終得到偽四邊形(Fake quadrilateral)的四個頂點(diǎn)(圖8).

圖8 “偽四邊形”形成過程Fig.8 The procedure of“Fake quadrilateral” creation

圖3經(jīng)上述處理后,其擬合四邊形的四個頂點(diǎn)分別為P1(0,75),P2(85,231),P3(232,164),P4(171,2),擬合的“偽四邊形”如圖9所示.

圖9 原始圖像的擬合四邊形Fig.9 Fake quadrilateral of original image

2 條碼圖像畸變矯正

2.1 幾何校正模型

二維條碼圖像在經(jīng)手機(jī)攝像頭或掃描系統(tǒng)獲取過程中都可能發(fā)生畸變,尤其是輕微畸變在所難免,由此導(dǎo)致幾何失真.廣泛采用的幾何坐標(biāo)校正模型包括:雙線性模型、多項(xiàng)式模型和三次卷積模型等[5].三次卷積模型雖然具有較高精準(zhǔn)度,但其計算量巨大,運(yùn)算效率低,很難適應(yīng)移動端運(yùn)行環(huán)境,同時也不能滿足系統(tǒng)實(shí)時性要求.一般情況下,條碼圖象發(fā)生的畸變屬于雙線性范疇,故筆者采用雙線性模型.f(x,y)表示校正后的無失真圖象,g(x′,y′)表示待校正的畸變圖象;f(x,y)=g(x′,y′),即:點(diǎn)(x,y)經(jīng)過畸變坐標(biāo)值變?yōu)?x′,y′):

2.2 條碼圖像幾何校正

針對移動端屏幕尺寸特征,通過設(shè)置200×200正方形區(qū)域,條碼內(nèi)各像素點(diǎn)映射其中即完成畸變校正(圖10).

圖10 條碼控制點(diǎn)變換圖Fig.10 Position changing of the control points

首先取條碼圖象“偽四邊形”四頂點(diǎn)作為控制點(diǎn) ,設(shè) T1,T2,T3,T4 的坐標(biāo)分別為(x′1,y′1),(x′2,y′2),(x′3,y′3),(x′4,y′4);P1,P2,P3,P4的坐標(biāo)分別為(x1,y1),(x2,y2),(x3,y3),(x4,y4);則由式(1,2)可得到x,y,x′,y′的雙線性方程組:

由于校正前后8控制點(diǎn)P1,P2,P3,P4,T1,T2,T3,T4為已知,通過雙線性方程式(3,4)即可確定雙線性映射的映射系數(shù).因此通過以上映射系數(shù),校正圖像中的任意一點(diǎn)(x,y)的灰度值 f(x,y)都可由對應(yīng)的畸變點(diǎn)(x′,y′)的灰度值 g(x′,y′)得到.

2.3 像素點(diǎn)灰度值校正

由于輸入圖像只在整數(shù)位置定義灰度值,變換后的輸出圖像中與其對應(yīng)的點(diǎn)坐標(biāo)值并不能確保為整數(shù),即空間變換后的點(diǎn)不可能總是落在實(shí)際圖像的像素點(diǎn)上,所以實(shí)際圖像上各點(diǎn)的灰度值是根據(jù)附近各像素點(diǎn)的灰度值得到.

常用的灰度插值算法包括最近鄰插值、雙線性插值及高階插值等.最近鄰插值簡單地通過取浮點(diǎn)坐標(biāo)最鄰近的像素點(diǎn)得到對應(yīng)的灰度值,校正后的圖像亮度有明顯的不連續(xù)性;雙線性插值法是利用四相鄰點(diǎn)的灰度在縱橫雙向做線性內(nèi)插,所以其算法產(chǎn)生的圖像質(zhì)量較好,不存在灰度不連續(xù)的情況.

對條碼圖象的灰度計算采用雙線性插值(Bilinear interpolation approach)校正法恢復(fù),根據(jù)點(diǎn)所在的單元正方形4個頂點(diǎn)坐標(biāo)來計算其灰度值(圖11).

圖11 雙線性插值示意圖Fig.11 Bilinear interpolation approach

d(x,y)=(1-q){(1-p)×d([x],[y])+p×d([x]+1,y)}+q{(1-p)×d([x],[y]+1)+p×d([x]+1,[y]+1)},d(x,y)表示坐標(biāo)(x,y)處的灰度值,[x],[y]分別為不超過x和 y的整數(shù)值.二值化后的條碼圖象,經(jīng)畸變校正后的結(jié)果如圖12所示.

圖12 校正前后的條碼二值化圖像Fig.12 Images before and after correction

3 實(shí)驗(yàn)結(jié)果

測試所用手機(jī)為Nokia N73,其硬件配置:ARM 9 CPU,處理器的時脈(Clock Rate)220 MHz;64 MB內(nèi)存,軟件環(huán)境:Symbian OS 9.1 Series 60 3rd Edition.

圖13為二維條碼圖像經(jīng)過自適應(yīng)閾值分割后的二值圖像,在手機(jī)端經(jīng)過Sobel算子邊緣檢測后分別進(jìn)行Hough直線檢測[6]和改進(jìn)凸包定位及校正的效果圖.實(shí)驗(yàn)中調(diào)用自編寫的由無窮級數(shù)近似的三角函數(shù),其運(yùn)行時間對照如表1所示.

圖13 文中算法與傳統(tǒng)算法實(shí)驗(yàn)效果Fig.13 Results for the two methods

表1 筆者算法與傳統(tǒng)算法處理時間對比Table 1 Time compare between two algorithms

4 結(jié) 論

通過預(yù)處理以差乘方式排除大量內(nèi)部無效點(diǎn)集,采用算法復(fù)雜度為O(nlgn)的Graham掃描法得到凸包頂點(diǎn)集,最后通過角度、長度等方式準(zhǔn)確篩選凸包頂點(diǎn)減少計算量,提高效率.實(shí)驗(yàn)表明:筆者方法對實(shí)際Data Matrix二維條碼圖像的定位和校正效果明顯,并且適應(yīng)手機(jī)端軟硬件環(huán)境,但是對于畸變幅度較大的條碼定位和校正處理效果并非很理想,有待進(jìn)一步提高.

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

[2] 潘金貴,顧鐵成.算法導(dǎo)論[M].北京:機(jī)械工業(yè)出版社,2006.

[3] 楊常青,彭木根.Sy mbian S60手機(jī)程序開發(fā)與實(shí)用教程機(jī)械工業(yè)出版社[M].3版.北京:機(jī)械工業(yè)出版社,2008.

[4] EDW ARDS L,BARKER R.Developing series 60 applications[M].北京:人民郵電出版社,2005.

[5] 蔡文婷.移動端二維條碼圖像增強(qiáng)及應(yīng)用研究[D].杭州:浙江工業(yè)大學(xué),2008.

[6] 陳媛媛,施鵬飛.二維條形碼的識別及應(yīng)用[J].測控技術(shù),2006,25(12):17-19.