史志鋒

摘要： 傳統(tǒng)的QR碼識(shí)別算法只適用于打印在平面上的條碼，提出了一種有效識(shí)別打印在飲料瓶等圓柱面上的QR碼。通過(guò)對(duì)圖像輪廓進(jìn)行角點(diǎn)檢測(cè)確定回字定位圖形，在此基礎(chǔ)上篩選條碼關(guān)鍵輪廓并對(duì)其進(jìn)行霍夫變換提取圓柱面上的透視橢圓信息，同時(shí)結(jié)合透視橢圓的參數(shù)和三維透視變換，有效構(gòu)建了圓柱面條碼像素從二維圖像平面直接映射到三維圖像空間的變換矩陣，重構(gòu)打印在平面或圓柱面上的QR碼目標(biāo)。實(shí)驗(yàn)結(jié)果表明，該算法對(duì)平面或圓柱面QR條碼的識(shí)別有較高的準(zhǔn)確率。

關(guān)鍵詞： QR碼提??； 霍夫變換； 圓柱面； 三維透視變換

中圖分類(lèi)號(hào)： TN919?34 文獻(xiàn)標(biāo)識(shí)碼： A文章編號(hào)： 1004?373X（2014）08?0015?04

Recognition of QR codes on cylindrical surface based on 3D perspective transformation

SHI Zhi?feng

（Department of Electronic Engineering， Xiamen University， Xiamen 361005， China）

Abstract： Traditional QR code recognition algorithm is usually applied to the barcode printed on flat surface only. A low?cost approach to recognize the curved QR codes printed on bottles or cans is proposed in this paper. The width proportion and corners of image contours are extracted to confirm the positioning patterns and an efficient Hough transformation ellipse fitting method is employed to extract the elliptic information. In combination with the parameters of perspective ellipse and 3D perspective transformation， the transformation matrix of barcode pixels on a cylindrical surface is constructed by direct mapping from the 2D image plane to 3D image space. The experiment result proves the algorithm has the high?accuracy recognition ability of barcodes no matter on the flat or the cylindrical surface.

Keywords： QR code extraction； Hough transform； cylindrical surface； 3D perspective transformation

QR碼作為一種成本低廉、識(shí)別率高的二維條碼，在智能的系統(tǒng)中發(fā)揮著重大的作用[1]。識(shí)別QR碼的關(guān)鍵問(wèn)題就是定位和校正，QR碼通常被打印在平面或圓柱面上，對(duì)于平面QR碼。文獻(xiàn)[2]利用霍夫變換定位出條碼的四個(gè)角，但該方法要求圖像中只存在一個(gè)條碼并且條碼背景簡(jiǎn)單；文獻(xiàn)[3]將條碼圖像分拆成多塊并使用邊界檢測(cè)的方法找出條碼的四角；文獻(xiàn)[4]通過(guò)Candy邊界檢測(cè)提取條碼的外部輪廓；文獻(xiàn)[5]利用條碼的梯度特征獲得條碼區(qū)域。但這些方法只能識(shí)別平面QR碼。當(dāng)條碼被打印在瓶子等圓柱面上時(shí)，使用傳統(tǒng)透視變換方法將導(dǎo)致條碼信息定位錯(cuò)誤。文獻(xiàn)[1]通過(guò)檢測(cè)尋像圖形（timing pattern）來(lái)獲取采樣點(diǎn)信息，但這種方法對(duì)尋像圖形的清晰度十分敏感。本文利用定位圖形（finder pattern）的輪廓特征，通過(guò)改進(jìn)的霍夫變換提取條碼的輪廓，并通過(guò)三維透視變換的方法將條碼采樣點(diǎn)的信息映射到原圖，針對(duì)平面和圓柱面的條碼提取有較好的效果。

1條碼定位

QR碼的結(jié)構(gòu)如圖 1所示， 包含回字型的定位圖形（finder pattern）以及黑白相間的尋像圖形（timing pattern），還包含版本、格式等信息[6]。

圖1 QR碼的符號(hào)結(jié)構(gòu)

在圖像預(yù)處理階段，利用自適應(yīng)門(mén)限提取[7]的方法將灰度源圖像轉(zhuǎn)換為二值圖像，并通過(guò)輪廓追蹤[8]記錄所有的輪廓點(diǎn)信息，經(jīng)過(guò)這些處理后，利用每個(gè)閉合輪廓的重心位置和角點(diǎn)信息獲得定位圖形的位置及其對(duì)應(yīng)的輪廓。

1.1定位圖形提取

定位圖形有很明顯的特征：三個(gè)閉合輪廓有相同的重心。輪廓的重心可以通過(guò)式（1）計(jì)算得出[9]：

[gx=xyx?f(x,y)xyf(x,y)???，????????????gy=xyy?f(x,y)xyf(x,y)] （1）

式中：[gx]和[gy]分別代表重心點(diǎn)的x，y軸坐標(biāo)；[f(x,y)]是[(x,y)]處圖像的灰度值。在輪廓圖像中取邏輯值0或1，因此式（1）可以簡(jiǎn)化為：

[gx=1ni=1nxi，?????????????gy=1ni=1nyi] （2）

式中：n為輪廓上的像素個(gè)數(shù)。

將重心重合的幾個(gè)輪廓作為候選輪廓，使用角點(diǎn)檢測(cè)[10]的方法得出輪廓中的角點(diǎn)位置：一個(gè)輪廓可以表述為n個(gè)點(diǎn)的集合[P={pi=(xi,yi),i=1,2,…,n}]，輪廓中的一定相鄰點(diǎn)構(gòu)成的線(xiàn)段有一個(gè)協(xié)方差矩陣：

[C=c11c12c21c22] （3）

[c11=[12k+1i=-kkxi2]-[12k+1i=-kkxi]2?c12=[12k+1i=-kkxi?yi]-[12k+1i=-kkxi]?[12k+1i=-kkyi]c21=c12c22=[12k+1i=-kkyi2]-[12k+1i=-kkyi]2] （4）

矩陣C的兩個(gè)特征值可以用來(lái)獲取線(xiàn)段的形狀信息，較小的特征值[λs]可以用來(lái)表述線(xiàn)段在某點(diǎn)處的尖銳程度[10]：

[λs=12[c11+c22-(c11-c22)2+4c212]] （5）

因此當(dāng)某點(diǎn)處的[λs]大于某預(yù)設(shè)值并比附近點(diǎn)的[λs]都大時(shí)認(rèn)為該點(diǎn)是輪廓的一個(gè)角點(diǎn)。圖2說(shuō)明定位圖形的提取結(jié)果：輪廓的重心使用+標(biāo)出，角點(diǎn)使用*標(biāo)出。

1.2條碼邊界提取

在定位圖形輪廓已知的基礎(chǔ)上使用霍夫變換[11]用于提取條碼的邊界?；舴蜃儞Q將線(xiàn)上的點(diǎn)變換到參數(shù)空間，并投票計(jì)算最有可能的直線(xiàn)或曲線(xiàn)方程。以直線(xiàn)為例，直線(xiàn)可以描述為[ρi=xcosθi+ysinθi]，其中[ρi]表示直線(xiàn)到原點(diǎn)的距離，而[θi]表示直線(xiàn)與y軸的夾角。通過(guò)計(jì)算每個(gè)點(diǎn)（x，y）對(duì)應(yīng)的參數(shù)空間（ρ，θ）的可能值進(jìn)行累加比較最終得出（ρ，θ）的取值并確定直線(xiàn)。霍夫變換同樣適用于曲線(xiàn)的提取[12]。

圖2 定位圖形的提取結(jié)果

傳統(tǒng)的霍夫變換計(jì)算量較大，可以通過(guò)縮小參數(shù)空間的方法來(lái)減小計(jì)算量[13]，由于本文的定位圖形的輪廓已知，可以利用該信息計(jì)算出可能的參數(shù)空間取值組合，再針對(duì)該縮小的參數(shù)空間使用霍夫變換，最終得到輪廓的方程，大大減小計(jì)算量。使用上述方法提取出的輪廓如圖 3所示。

圖3 提取出的輪廓

2條碼幾何校正

當(dāng)攝像頭的角度或方向不是正對(duì)條碼時(shí)，捕獲的圖像就存在失真，利用反透視變換[14]可以校正條碼實(shí)際采樣點(diǎn)的位置以重構(gòu)條碼。在使用線(xiàn)性攝像頭拍攝條碼的場(chǎng)景中，可以使用3×4的矩陣來(lái)建模從世界坐標(biāo)到圖像坐標(biāo)的變換，這個(gè)矩陣稱(chēng)為射影矩陣[14]：

[kuv1=m11m12m13m14m21m22m23m24m31m32m33m34xyz1]（6）

式中：u和v代表一個(gè)點(diǎn)在圖像平面中的坐標(biāo)值； （x，y，z） 描述了這個(gè)點(diǎn)在世界坐標(biāo)系中的位置；k為比例系數(shù)；[m11]~[m34]構(gòu)成了射影矩陣。

2.1平面條碼的采樣點(diǎn)提取

當(dāng)條碼打印在平面上時(shí)，式（6）中的z軸坐標(biāo)全為0，可以化簡(jiǎn)為式（7）：

[kuv1=m11m12m13m21m22m23m31m32m33xy1]（7）

將式中的k消去，可以得到式（8）所描述的關(guān)系：

[x1y11000-u1x1-u1y1…………………………………………xnyn1000-unxn-unyn000x1y11-u1x1-u1y1…………………………………………000xnyn1-unxn-unynm11m12m13m21m22m23m31m32=m33u1u2…unv1v2…vn] （8）

可以令[m33=1]（[k]乘以某個(gè)系數(shù)），那么式（8）變成了有8個(gè)未知數(shù)的方程，因此只要得到4個(gè)點(diǎn)在兩個(gè)坐標(biāo)系中的對(duì)應(yīng)位置[(xi,yi)][(ui,vi)]，就可以解出射影矩陣[m11]~[m32]（這里可以利用條碼輪廓四個(gè)角對(duì)應(yīng)的坐標(biāo)），進(jìn)而獲得所有條碼采樣點(diǎn)對(duì)應(yīng)到圖像平面的坐標(biāo)，其映射關(guān)系可以描述為：

[u=m11x+m12y+m13m31x+m32y+1??,????v=m21x+m22y+m23m31x+m32y+1]（9）

2.2圓柱面條碼的采樣點(diǎn)提取

當(dāng)條碼被印刷在圓柱面上時(shí)，采樣點(diǎn)的提取過(guò)程和平面類(lèi)似。不同的是，需要考慮世界坐標(biāo)系中z軸取值，此時(shí)射影矩陣的大小變?yōu)?×4，因而需要6個(gè)點(diǎn)的對(duì)應(yīng)關(guān)系來(lái)解出11個(gè)未知數(shù)的方程，在之前4個(gè)點(diǎn)的基礎(chǔ)上增加兩個(gè)定位圖形的角點(diǎn)作為輸入。類(lèi)似的，u和v可以通過(guò)式（10）計(jì)算出來(lái)：

[u=m11x+m12y+m13z+m14m31x+m32y+m33z+1??,??v=m21x+m22y+m23z+m24m31x+m32y+m33z+1]（10）

為了獲取6個(gè)點(diǎn)在世界坐標(biāo)系中的坐標(biāo)，將世界坐標(biāo)系的三個(gè)軸定為圖 4所示的位置，將條碼的輪廓邊長(zhǎng)歸一化，于是圓柱面上點(diǎn)的坐標(biāo)值x，y，z可以通過(guò)半徑r計(jì)算出來(lái)，將r作為一個(gè)未知數(shù)代入，可以得到一個(gè)12元方程，并解出射影矩陣。

圖4 圓柱曲面條碼的坐標(biāo)示意圖

將歸一化的條碼圖像中的采樣點(diǎn)反向映射到原圖中得到二進(jìn)制值，并按照QR碼的解碼規(guī)則提取出條碼中的信息。

3結(jié)果與分析

使用本文算法對(duì)平面和圓柱面條碼處理的效果如圖 5和圖 6所示，圖 5中打印在條碼上點(diǎn)標(biāo)記了使用本文算法后獲得圓柱表面條碼的各模塊采樣點(diǎn)。而圖 6則分別顯示了使用本文算法對(duì)平面、圓柱面條碼處理之后重構(gòu)出的新條碼。

圖 5和圖 6都說(shuō)明該算法能較好的得到平面或圓柱面條碼的模塊采樣點(diǎn)進(jìn)而完成條碼的重構(gòu)。

圖5 圓柱面條碼處理后的采樣點(diǎn)

圖6 圓柱面條碼的解碼結(jié)果

為進(jìn)一步驗(yàn)證算法的效果，針對(duì)平面和圓柱表面分別獲取在各種不同大小的圖像進(jìn)行處理識(shí)別，并和文獻(xiàn)[1]的BSE算法以及開(kāi)源QR碼識(shí)別庫(kù)libqrencode比較。

圖7解碼結(jié)果表明，算法不僅對(duì)平面條碼具有很好的識(shí)別能力，對(duì)圓柱面條碼也具有較強(qiáng)的適應(yīng)性。與文獻(xiàn)[1]相比，識(shí)別圓柱面條碼的準(zhǔn)確率不依賴(lài)尋像圖形的清晰度，能提高識(shí)別系統(tǒng)的魯棒性。

圖7 圓柱面條碼和平面條碼的識(shí)別率比較

參考文獻(xiàn)

[1] CHU C H， YANG D N， PAN Ya?lan， et al. Stabilization and extraction of 2D barcodes for camera phones [J]. ACM Multimedia System Journal， 2011， 2： 113?133.

[2] WANG Hao， ZOU Yan?ming. Camera readable 2D bar codes design and decoding for mobile phones [C]// Proceedings of International Conference on Image Processing. [S.l.]： ICIP， 2006： 469?472.

[3] CHANG Yu?Hsuan， CHU Chung?Hua， CHEN Ming?Syan. A general scheme for extracting QR code from a non?uniform background in Camre phones and applications [C]// Ninth IEEE International Symposium on Multimedia. [S.l.]： IEEE， 2007： 123?130.

[4] SUN Ai?dong， SUN Yan， LIU Cai?xing. The QR?code reorganization in illegible snapshots taken by mobile phone [C]// International Conference on Computational Science and its Applications. S.l.]： ICCSA， 2007： 532?538.

[5] OUAVIANI E， PAVAN A， BOTTAZZI M， et al. A common image processing framework for 2D barcode reading [C]// Seventh International Conference on Image Processing and Its Applications.[S.l.]： ICIPA， 1999： 652?655.

[6] ISO. International Standard ISO/IEC 18004 [S/OL]. [2013?12?06]. http：//www.eweima.com/thread?8293?1?1.

[7] BRADLEY Derek， ROTH Gerhard. Adaptive thresholding using the integral image [J]. Journal of Graphics， GPU & Game Tools， 2007， 2： 13?21.

[8] CHANG Fu， CHEN Chun?Jen. A component?labeling algorithm using contour tracing technique [C]// Seventh International Conference on Document Analysis and Recognition. [S.l.]： ICDAR， 2003： 741?745.

[9] 谷口慶治.數(shù)字圖像處理——應(yīng)用篇[M].北京：科學(xué)出版社， 2002.

[10] TSAI Du?ming， HOU H T， SU H J. Boundary?based corner detection using eigenvalues of covariance matrices [J]. Pattern Recognition Letters， 1999， 1： 31?40.

[11] DUDA R O， HART P E. Use of the hough transformation to detect lines and curves in pictures [J]. Comm， ACM， 1972， 15： 11?15.

[12] GONZALEZ R C，WOODS R E.數(shù)字圖像處理[M].2版.北京： 電子工業(yè)出版社，2007.

[13] 孫明，傅隆生，楊信廷，等.用于QR碼自動(dòng)識(shí)讀的圖像分析方法[J].電子科技大學(xué)學(xué)報(bào)，2009（6）：123?126.

[14] SONKA Milan， HLAVAC Vaclav， BOYLE Roger. Image processing， analysis and machine vision [M]. Third Edition. [S.l.]： Thomson Learning， 2008.

[15] LIAO Zhao?lai， HUANG Ting?lei， WANG Rui， et al. A method of image analysis for QR code recognition [C]// 2010 International Conference on Intelligent Computing and Integrated Systems. [S.l.]： ICISS， 2010： 250?253.

[7] BRADLEY Derek， ROTH Gerhard. Adaptive thresholding using the integral image [J]. Journal of Graphics， GPU & Game Tools， 2007， 2： 13?21.

[8] CHANG Fu， CHEN Chun?Jen. A component?labeling algorithm using contour tracing technique [C]// Seventh International Conference on Document Analysis and Recognition. [S.l.]： ICDAR， 2003： 741?745.

[9] 谷口慶治.數(shù)字圖像處理——應(yīng)用篇[M].北京：科學(xué)出版社， 2002.

[10] TSAI Du?ming， HOU H T， SU H J. Boundary?based corner detection using eigenvalues of covariance matrices [J]. Pattern Recognition Letters， 1999， 1： 31?40.

[11] DUDA R O， HART P E. Use of the hough transformation to detect lines and curves in pictures [J]. Comm， ACM， 1972， 15： 11?15.

[12] GONZALEZ R C，WOODS R E.數(shù)字圖像處理[M].2版.北京： 電子工業(yè)出版社，2007.

[13] 孫明，傅隆生，楊信廷，等.用于QR碼自動(dòng)識(shí)讀的圖像分析方法[J].電子科技大學(xué)學(xué)報(bào)，2009（6）：123?126.

[14] SONKA Milan， HLAVAC Vaclav， BOYLE Roger. Image processing， analysis and machine vision [M]. Third Edition. [S.l.]： Thomson Learning， 2008.

[15] LIAO Zhao?lai， HUANG Ting?lei， WANG Rui， et al. A method of image analysis for QR code recognition [C]// 2010 International Conference on Intelligent Computing and Integrated Systems. [S.l.]： ICISS， 2010： 250?253.

[7] BRADLEY Derek， ROTH Gerhard. Adaptive thresholding using the integral image [J]. Journal of Graphics， GPU & Game Tools， 2007， 2： 13?21.

[8] CHANG Fu， CHEN Chun?Jen. A component?labeling algorithm using contour tracing technique [C]// Seventh International Conference on Document Analysis and Recognition. [S.l.]： ICDAR， 2003： 741?745.

[9] 谷口慶治.數(shù)字圖像處理——應(yīng)用篇[M].北京：科學(xué)出版社， 2002.

[10] TSAI Du?ming， HOU H T， SU H J. Boundary?based corner detection using eigenvalues of covariance matrices [J]. Pattern Recognition Letters， 1999， 1： 31?40.

[11] DUDA R O， HART P E. Use of the hough transformation to detect lines and curves in pictures [J]. Comm， ACM， 1972， 15： 11?15.

[12] GONZALEZ R C，WOODS R E.數(shù)字圖像處理[M].2版.北京： 電子工業(yè)出版社，2007.

[13] 孫明，傅隆生，楊信廷，等.用于QR碼自動(dòng)識(shí)讀的圖像分析方法[J].電子科技大學(xué)學(xué)報(bào)，2009（6）：123?126.

[14] SONKA Milan， HLAVAC Vaclav， BOYLE Roger. Image processing， analysis and machine vision [M]. Third Edition. [S.l.]： Thomson Learning， 2008.

[15] LIAO Zhao?lai， HUANG Ting?lei， WANG Rui， et al. A method of image analysis for QR code recognition [C]// 2010 International Conference on Intelligent Computing and Integrated Systems. [S.l.]： ICISS， 2010： 250?253.