基于三維透視變換的圓柱面QR碼識別方法

史志鋒

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

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

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

1條碼定位

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

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

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

1.1定位圖形提取

定位圖形有很明顯的特征：三個閉合輪廓有相同的重心。輪廓的重心可以通過式（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）可以簡化為：

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

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

將重心重合的幾個輪廓作為候選輪廓，使用角點(diǎn)檢測[10]的方法得出輪廓中的角點(diǎn)位置：一個輪廓可以表述為n個點(diǎn)的集合[P={pi=(xi,yi),i=1,2,…,n}]，輪廓中的一定相鄰點(diǎn)構(gòu)成的線段有一個協(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的兩個特征值可以用來獲取線段的形狀信息，較小的特征值[λs]可以用來表述線段在某點(diǎn)處的尖銳程度[10]：

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

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

1.2條碼邊界提取

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

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

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

圖3 提取出的輪廓

2條碼幾何校正

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

[kuv1=m11m12m13m14m21m22m23m24m31m32m33m34xyz1]（6）

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

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

當(dāng)條碼打印在平面上時，式（6）中的z軸坐標(biāo)全為0，可以化簡為式（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]乘以某個系數(shù)），那么式（8）變成了有8個未知數(shù)的方程，因此只要得到4個點(diǎn)在兩個坐標(biāo)系中的對應(yīng)位置[(xi,yi)][(ui,vi)]，就可以解出射影矩陣[m11]~[m32]（這里可以利用條碼輪廓四個角對應(yīng)的坐標(biāo)），進(jìn)而獲得所有條碼采樣點(diǎn)對應(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)條碼被印刷在圓柱面上時，采樣點(diǎn)的提取過程和平面類似。不同的是，需要考慮世界坐標(biāo)系中z軸取值，此時射影矩陣的大小變?yōu)?×4，因而需要6個點(diǎn)的對應(yīng)關(guān)系來解出11個未知數(shù)的方程，在之前4個點(diǎn)的基礎(chǔ)上增加兩個定位圖形的角點(diǎn)作為輸入。類似的，u和v可以通過式（10）計(jì)算出來：

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

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

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

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

3結(jié)果與分析

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

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

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

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

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

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

圖7 圓柱面條碼和平面條碼的識別率比較

參考文獻(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碼自動識讀的圖像分析方法[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碼自動識讀的圖像分析方法[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碼自動識讀的圖像分析方法[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.