基于凸包的棋盤格角點自動識別與定位方法*

熊會元，宗志堅，余 志，陳承鶴

(中山大學(xué)工學(xué)院, 廣東 廣州 510275)

基于棋盤格的攝像機標定中，角點提取的精度與物像坐標的匹配是該算法的重要環(huán)節(jié)?，F(xiàn)有角點提取方法可分為三類[1]：一是根據(jù)圖像邊緣特征，由邊緣夾角[2]或曲率[3]來判斷是否為角點；二是利用圖像的灰度信息，如Susan算法[4]；三是利用圖像的灰度變化率，如Harris算法[5]。Schmid等[6]認為, Harris算法是目前最好的一種方法。該方法使用圖像的一階差分，計算每個像素的平均平方梯度矩陣，通過特征值分析得出角點的響應(yīng)；不受攝像機姿態(tài)、光照、噪聲等影響，具有效率高和較強的穩(wěn)定性及魯棒性。 但該算法的不足是提取的精度只有像素級，角點集包含外圈角點與格單元邊緣上的偽點(圖1所示綠色箭頭所指)，且點集中角點排序混亂。這樣標定時，需手動完成角點像與物坐標匹配。

本文在Harris算法基礎(chǔ)上，利用棋盤格內(nèi)角點的對稱性，設(shè)計對稱算子，剔除外圈角點與偽角點。在此基礎(chǔ)上，應(yīng)用角點處灰度梯度算法，獲取棋盤格亞像素角點。最后，在角點集中應(yīng)用凸包算法分層識別并自動定位角點，實現(xiàn)角點物與像坐標的自動匹配，進而可實現(xiàn)攝像機精確快速標定。

圖1 Harris 提取角點圖

1 棋盤格內(nèi)部角點識別與亞像素提取

1.1 基于對稱算子的內(nèi)部角點識別

Harris提取的角點集中，外圈角點受邊界環(huán)境影響，角點提取的精度不高，不易作為標定點，因而應(yīng)從點集中剔除。從棋盤格布局中可以看出，棋盤格內(nèi)部角點具有以角點為中心，周圍的灰度分布具有對稱性特點；而外圈角點與格單元邊緣上偽角點則不具備，據(jù)此原理定義如下式的對稱算子[7]：

(1)

其中,I(i,j)為角點(i,j)處的灰度值，w為以(i,j)為中心的窗口，可根據(jù)圖像中棋盤格單元大小設(shè)定，n為w中角點對稱對的數(shù)量。

可通過設(shè)定cs的域值來區(qū)分角點是否為內(nèi)部角點，其中小于域值的角點則認為是內(nèi)部角點。圖2為w取15×7，cs域值取65，對圖1中棋盤格進行的識別結(jié)果圖。

1.2 亞像素角點精確提取

為得到更高的角點精度，在Harris算法提取角點后，利用角點處灰度梯度獲得亞像素級角點精度。文獻[8]提到兩種算法，其中基于灰度梯度的算法精度更高，應(yīng)用較廣，其原理如下：

設(shè)Harris算法提取的角點為p，則p指向領(lǐng)域內(nèi)任意一點qi的向量都與qi的灰度梯度垂直。其表達式如下：

圖2 應(yīng)用對稱算子識別內(nèi)部角點圖

(2)

2 基于凸包的角點分層識別與自動定位

攝像機標定的另一個環(huán)節(jié)是棋盤格角點的空間坐標與圖像坐標的匹配。文獻[9]應(yīng)用平行線共滅點的原理，先確定中心格四角點，作直線求滅點，后由滅點與角點的距離來排序，依次確定其他柵格線上角點；文獻[10]提出由中心角點出發(fā)，以圖像x與y方向的動態(tài)增量dx與dy來預(yù)測和遞推其他角點；上述算法受攝像機畸變影響較大，操作較復(fù)雜。由于棋盤格角點具有柵格排列與分層排列的特征，作者發(fā)現(xiàn)凸包算法能很好的識別與定位角點集中外層凸點；在凸包中，應(yīng)用凸度識別并定位轉(zhuǎn)角點，進而可識別與定位整個棋盤格角點。

圖3 凸包概念圖

2.1 凸包的概念

平面點集的凸包定義為對平面上一個點集S，或一個多邊形P，其凸包是指包含S或P的最小凸多邊形。如下圖中線段表示的多邊形就是點集S={p0,p1,...,p12}的凸包。

定義1 設(shè)P為逆時針排序的凸多邊形，其頂點的序列為{p0,p1,...pn-1}，計T(P)為P的凸包，L(pi,pi+1)為頂點pi與pi+1的直線連接，TL(p0,pn-1)={L(p0,p1),…,L(pi-1,pi),…,L(pn-1,p0)}為凸包T(P)的直線集。

2.2 角點分層識別與自動排序

基于凸包的角點分層識別與自動排序包括角點集凸包的識別、凸包中的四個轉(zhuǎn)角點識別與定位、同層角點的全識別與排序，以及角點全識別與排序等四個步驟。具體如下：

步驟一角點集凸包的識別

① 設(shè)Q0為m×n棋盤格角點的點集，取點p0(p0∈Q0且p0的x坐標最小，如有多個相等的最小值，則取其中y坐標最小的點)；

② 以p0為中心，計算pi(pi∈(Q0-p0)，i=1,...,m×n-1)相對于p0的極角，并以逆時針方向?qū)O角排序，若極角相等，取離p0最遠的點，則可得點集P(P={p0,...,pi,...,pr}，其中r≤m×n-1)；

最后得到點集P={p0,...,pi,...,pk}(其中k≤r)所構(gòu)成的多邊形即為點集Q0的凸包T(P)。圖4為應(yīng)用本算法獲得圖2棋盤格點集的凸包圖，由9個頂點組成。

步驟二凸包中棋盤格轉(zhuǎn)角點識別與定位

② 求p0、p1、p2與p3的質(zhì)心pc(x,y);

,

(3)

圖4 棋盤格角點集凸包

步驟三同層角點的識別與排序

依次取凸包T′(P)直線集上直線L(pi,pi+1)(L(pi,pi+1)∈T′L(p0,pk)；i=0，1，…，k)，任取角點ql∈(Q0-P′)(l=0,1,...,m×n-1-k)，求到直線L(pi,pi+1)的垂足fl與距離dl。設(shè)判斷點在直線上的距離域值為εd，若dl≤εd且fl在直線段L(pi,pi+1)的pi與pi+1點之間，則認為點ql為直線L(pi,pi+1)上的點，并將ql按|pi-ql|距離由近至遠的次序插入點集P′,遍歷T′(P)上的直線集后可得以左上角點p0為起始點，逆時針存儲的棋盤格同層角點的點序集P′(P′={p0,...,pi,ql,pi+1,...,pk})。

步驟四角點的全識別與排序

圖5 按凸包次序排序圖

圖6 行列次序排序圖

3 實驗與結(jié)果分析

用Visual C++6.0編程實現(xiàn)了上述算法，用圖7示數(shù)控實驗平臺，采用Watec 902B攝像機，f=25 mm鏡頭，拍攝15位置棋盤格圖像(見圖8)，用本文算法完成角點精確提取與分層識別排序，用Zhang[11]完成標定；為進行對比實驗，同時應(yīng)用經(jīng)典的基于Matlab攝像機標定程序[12]，實現(xiàn)角點手動提取與定位，并標定，其標定對比結(jié)果如表1。

圖7 實驗圖

表1 對比實驗結(jié)果表

圖8 拍攝15位置標定圖像

由上述實驗可以看出，兩種方法標定結(jié)果焦距fx,fy,主點u0,v0以及畸變系數(shù)(k1,k2,p1,p2)十分接近，誤差較小。但本文方法可全自動實現(xiàn)，整個標定時間僅為21.6 s，而文獻[12]需要手動提取，所需時間需要298 s。

4 結(jié) 語

本文應(yīng)用Harris算子與基于角點處灰度梯度方法提取棋盤格角點，角點精度達亞像素。采用對稱算子剔除棋盤格外圈角點與偽角點，實現(xiàn)棋盤格內(nèi)角點的識別方法有效。提出的基于凸包的棋盤格角點的分層識別與自動定位方法可快速自動地實現(xiàn)物像坐標的匹配，進而實現(xiàn)攝像機自動標定。實驗結(jié)果證明了方法的正確性與可靠性，適用于攝像機在線自標定。

參考文獻：

[1] 張兆偉,趙字明,胡福喬,等. 基于樣條小波的增強算法在角點提取中的應(yīng)用[J].計算機工程與應(yīng)用,2006,15:56-58.

ZHANG Z W,ZHAO Y M, HU F Q,et al .Corner extraction based on spline wavelet enhancement[J].Computer Engineering and Applications,2006, 15：56-58.

[2] HSIN T, HU W C. A rotationally invariant two-phase scheme for corner detection [J]. Pattern Recognition, 1996,28(5):819-829.

[3] MEDIONI G, YASUMOTO Y. Corner detection and curve representation using cubic B-spline[J]. Computer Vision Graphics Image Process, 1987, 39(3):267-278.

[4] SMITH S, BRANDY J M. SUSAN—a new approach to low level image processing[J]. Journal of Computer Vision,1997, 23(1): 45-78.

[5] HARRIS C, STEPHENS M.A combined corner and edge detector[C].Proceedings of the Fourth Alvey Vision Conference, Manchester, England, 1988: 147-151.

[6] SCHIMID C, MOHR R, BAUCKHAGE C. Evaluation of interest point detectors [J].International Journal of Computer Vision, 2000, 37(2): 151-172.

[7] 劉陽成,朱楓. 一種新的棋盤格圖像角點檢測算法[J].中國圖象圖形學(xué)報,2006,11(5):656-660.

LIU Y C, ZHU F. A new algorithm for X-corner detection[J]. Journal of Image and Graphics,2006,11(5):656-660.

[8] 梁志敏,高洪明．?dāng)z像機標定中亞像素級角點檢測算法[J].焊接學(xué)報,2006,27(2):102-105.

LIANG Z M,GGO H M. Sub-pixels corner detection for cam era calibration[J]. Transactions of the China Welding Institution, 2006,27(2):102-105.

[9] 王忠石,徐心和. 棋盤格模版的自動識別與定位[J].中國圖象圖形學(xué)報,2007,12(4):618-622.

WANG Z S, XU X H. Auto-recognition and auto-location of the checkerboard pattern corner[J]. Journal of Image and Graphics,2007,12(4):618-622.

[10] 劉群根. 基于梯度與對稱度提取棋盤格角點及角點遞推定位[J]. 測控技術(shù),2008,27(1):7-9.

LIU Q G. Extracting checkerboard corners based on gradient& symmetry and locating with Iteration[J]. Measurement& Control Technology, 2008,27(1):7-9.

[11] ZHANG Z．A flexible new technique for camera calibration[J]．IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22(11)：1330-1334.

[12] BOUGUET J Y.Camera calibration toolbox for Matlab [EB/OL]. http://www.vision.caltech.edu/bouguetj/calib_doc/htmls/example.html.