史志鋒

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

關鍵詞： QR碼提?。?霍夫變換； 圓柱面； 三維透視變換

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

1條碼定位

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

圖1 QR碼的符號結構

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

1.1定位圖形提取

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

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

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

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

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

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

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

因此當某點處的[λs]大于某預設值并比附近點的[λs]都大時認為該點是輪廓的一個角點。圖2說明定位圖形的提取結果：輪廓的重心使用+標出，角點使用*標出。

1.2條碼邊界提取

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

圖2 定位圖形的提取結果

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

圖3 提取出的輪廓

2條碼幾何校正

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

[kuv1=m11m12m13m14m21m22m23m24m31m32m33m34xyz1]（6）

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

2.1平面條碼的采樣點提取

當條碼打印在平面上時，式（6）中的z軸坐標全為0，可以化簡為式（7）：

[kuv1=m11m12m13m21m22m23m31m32m33xy1]（7）

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

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

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

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

2.2圓柱面條碼的采樣點提取

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

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

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

圖4 圓柱曲面條碼的坐標示意圖

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

3結果與分析

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

圖 5和圖 6都說明該算法能較好的得到平面或圓柱面條碼的模塊采樣點進而完成條碼的重構。

圖5 圓柱面條碼處理后的采樣點

圖6 圓柱面條碼的解碼結果

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

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

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

參考文獻

[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ù)字圖像處理——應用篇[M].北京：科學出版社， 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].電子科技大學學報，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ù)字圖像處理——應用篇[M].北京：科學出版社， 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].電子科技大學學報，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ù)字圖像處理——應用篇[M].北京：科學出版社， 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].電子科技大學學報，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.