段 汕，賀 興，婁聯(lián)堂，徐 文，羅 敬

(中南民族大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)學(xué)院，武漢 430074)

角點是圖像上曲率足夠高、并且位于圖像中不同亮度區(qū)域交界處的點.它具有旋轉(zhuǎn)不變性和不隨光照條件變化而改變的優(yōu)點，因而能夠在圖像匹配、攝像機標(biāo)定、三維重建、運動物體的跟蹤及模式識別等機器視覺諸多領(lǐng)域有著重要應(yīng)用.通過提取象棋棋盤點的圖像位置信息，可以確定機器視覺系統(tǒng)中像平面和空間坐標(biāo)系之間的對應(yīng)關(guān)系，從而可以通過空間平面的變化信息更新像平面中的信息，因此，象棋棋盤角點檢測是攝像機校準(zhǔn)和棋子識別以及跟蹤的重要環(huán)節(jié).現(xiàn)行的角點檢測算法有很多種,大致可以分為兩類:一類是基于邊緣的角點檢測算法，文獻(xiàn)[1]通過先用Sobel算子求取棋盤格圖像邊緣，進(jìn)而求取邊緣和角點，再運用Susan算子來進(jìn)行優(yōu)化.另一類是基于灰度的角點檢測算法，如文獻(xiàn)[2]對Harris算子的棋盤格檢測算法進(jìn)行了改進(jìn)，實現(xiàn)了對攝像機畸變較大的圖像角點自動提取，文獻(xiàn)[3]利用棋盤格圖像對稱和灰度值對比明顯的獨特性質(zhì)，提出了SV算子檢測方法.

上述文獻(xiàn)提出的大部分方法在標(biāo)定的圖像上都要進(jìn)行一些預(yù)處理，如濾波、增強等，而且在準(zhǔn)確性和實時性上還有可以改進(jìn)的地方.本文針對中國象棋棋盤角點的特點提出一種針對中國象棋棋盤基于直線檢測和投影直方圖檢測相結(jié)合的角點檢測方法.

1 棋盤圖像的邊緣檢測和棋盤角點檢測

根據(jù)對圖像灰度的分析可以知道,象棋棋盤邊線的灰度和周圍像素的灰度不同,而且灰度變化較大,由此可以選擇合適的邊緣檢測算子來檢測出包含棋盤角點的棋盤邊線.

通過對常用的各種邊緣檢測算子[4-6]，如Laplacian 算子、Prewitt 算子、Robert算子、Sobel 算子、Sobel 垂直算子、Sobel水平算子的比較,發(fā)現(xiàn)Sobel算子最適合用于對象棋棋盤邊線的檢測,實驗表明，因為Sobel 算子可以最大程度的檢測出棋盤邊線,而且有相對較高的對比度和較少的噪聲.

經(jīng)過Sobel算子處理后發(fā)現(xiàn)，象棋棋盤格的格點實質(zhì)上是兩條棋盤直線的交點，所以只要能夠正確檢測出棋盤中的直線，然后求出這些直線的交點，就可以得到棋盤角點.

直線提取的算法也備受人們的關(guān)注,近20年來,人們提出了許多算法,它們各有優(yōu)缺點.其中Hough變換[7]是應(yīng)用最廣泛的方法之一,其優(yōu)點是抗噪性能好,且能連接共線短直線，但缺點是參數(shù)難以選擇,且計算十分復(fù)雜,所以我們不能運用Hough變換去檢測目標(biāo)直線.針對這種情況文獻(xiàn)[8]提出一種LSD算法.

通過LSD算法對二值化(圖1(b))處理后的圖像進(jìn)行直線檢測,將得到的直線標(biāo)記在原圖(圖1(a))上，得到結(jié)果圖1(c).

圖1 LSD算法檢測棋盤直線的結(jié)果

通過觀察LSD算法的結(jié)果可以發(fā)現(xiàn)，棋盤角點大部分都是位于棋盤邊線的交點或者交點附近，所以，可以通過檢測出的直線求得這些直線的交點，從而確定象棋棋盤角點的位置.

首先，在LSD算法檢測出的棋盤上的直線后，從直線方向的分布上知道棋盤中信息點(圖1(a)中標(biāo)出的兩個點稱之為信息點)處于一些斜線的交點處，而且棋盤上其他角點處于方向位于90度，180度左右直線的交點上，因此，可以通過對LSD算法檢測出的直線進(jìn)行分組，先求出這些斜線的交點即信息點的準(zhǔn)確位置，然后，通過這兩個點的位置可以大致確定棋盤其他角點的近似位置，由于這些直線的信息都是已知的，那么可以找到這些近似位置附近直線的交點，另外，由信息點得到的近似位置是比較接近真實棋盤角點的位置，所以，找到距離近似位置最近的交點的位置即為棋盤角點的位置.

2 改進(jìn)算法—基于LSD算法和投影直方圖相結(jié)合的棋盤角點檢測

2.1 投影直方圖檢測原理

投影法是根據(jù)圖像在指定方向上投影的分布特征來進(jìn)行檢測的.這種方法在本質(zhì)上是一種統(tǒng)計方法.由于統(tǒng)計直方圖是統(tǒng)計一幅圖像中各像素點某個特征值出現(xiàn)的次數(shù)，只反映了圖像某一個特征的頻度，不包涵圖像特征的空間分布關(guān)系，因此，不能準(zhǔn)確地檢測出棋盤角點的空間分布情況.

為了克服統(tǒng)計直方圖所不能反映圖像某一特征空間分布關(guān)系的缺點，本文在統(tǒng)計棋盤角點矩形內(nèi)的灰度值的基礎(chǔ)上，采用了投影直方圖的方法，即把一幅圖像的各像素點的某一個特征分別投影在水平x軸和垂直y軸上，得到這一特征信息在x方向和y方向上的分布情況，基于投影直方圖的象棋角點檢測是利用一個矩形窗口將棋盤格角點框在其中，通過x軸、y軸方向的投影得到其橫縱坐標(biāo)灰度值的和，然后求其x軸、y軸方向灰度期望，得到棋盤目標(biāo)角點位置.

灰度值H在x方向、y方向上的投影分布能夠反映出棋盤格角點在圖像上的具體坐標(biāo)位置，表示對于一幅圖像在x方向、y方向的投影直方圖定義如下：

(1)

(2)

其中，i表示x方向坐標(biāo)，Ex(i)表示x方向投影，j表示y方向坐標(biāo)，Ey(j)表示y方向投影.設(shè)P(x,y)表示算法檢測出的棋盤角點，則：

(3)

圖2(a)是一幅理想的象棋棋盤角點的示意圖，由于只需要得到圖像棋盤角點所在位置的信息，所以我們設(shè)計一個一定大小的矩形框(圖2(a)中矩形邊框)，對角點所在的位置進(jìn)行覆蓋如圖2(a)，得到對應(yīng)的x軸方向的投影和y軸方向的投影分別如圖2(b)、(c).

圖2 理想棋盤角點投影直方圖

通過上述投影法，分別取x軸、y軸方向的灰度投影數(shù)組，然后計算其相應(yīng)的期望值即可檢測出角點所在位置的坐標(biāo).

2.2 本文方法及原理

圖3說明了本文檢測象棋棋盤格角點的基本原理.首先將攝像機采集的視頻圖像輸入到計算機，由于待處理的對象必須是灰度圖像，所以要先對象棋圖像進(jìn)行灰度化.通過觀察可以發(fā)現(xiàn)，其實棋盤格的角點處于灰度變化明顯的棋盤邊線上，為了突出棋盤邊線，再利用Sobel算子對其進(jìn)行邊緣檢測，得到棋盤圖像是棋盤格線明顯的象棋灰度圖像，然后再利用LSD算法檢測出圖像中的近似直線，由于棋盤中存在噪聲影響，通過先對x軸、y軸方向的灰度投影進(jìn)行類似平滑的處理以消除噪聲的影響，最后求出x軸、y軸方向的灰度投影的最大值位置即為象棋棋盤角點的準(zhǔn)確位置(圖3為算法流程圖，圖4為實驗效果圖).

圖3 算法流程

圖4 算法實驗結(jié)果

2.3 LSD算法和投影直方圖相結(jié)合的棋盤角點檢測方法

通過上述實驗提出一種將兩種方法結(jié)合起來的算法，步驟如下.

(1)對棋盤圖像進(jìn)行灰度化，邊緣檢測；

(2)運用LSD算法檢測出棋盤中的直線；

(3)在第(2)步的基礎(chǔ)上得到棋盤大部分直線的角度，然后通過求這些傾斜直線(方向為45度左右或者135度左右)的交點得到這兩個信息點的位置(x1,y1),(x2,y2)；

(4)根據(jù)第(3)步得到的信息點的位置坐標(biāo)可以得到棋盤角之間的大致距離(最近棋盤角點之間距離L=|x1-x2|/7),再通過信息點位置和棋盤角點之間的近似距離我們可以知道棋盤所有角點的近似位置；

(5)利用(x1,y1)得到它左邊(右邊，上方，下方)的近似坐標(biāo)是(x1-L,y1)，然后以(x1-L,y1)為中心構(gòu)造投影區(qū)域矩形R，長寬為L/2，選擇一個一定大小的x方向或者y方向小矩形r(例如對于x方向小矩形長是L，寬是(2×radius+1)，本文radius取2)，將小矩形r在大矩形R上x方向(y方向)移動，計算出每一次移動時r中投影到x方向(y方向的)灰度值H,然后找到這樣一組投影灰度值數(shù)組的最大值位置，此時x=i(y=j)，x(y)就是大矩形R中棋盤角點的行(列)位置；

(6)重復(fù)第(5)步的操作繼續(xù)一步一步向周圍選取棋盤角點，最終得到象棋棋盤上所有的角點坐標(biāo).

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

為了驗證算法的有效性和正確性，本文通過對于攝像頭采集的640 × 480大小的視頻圖像分別利用基于LSD算法檢測的棋盤角點檢測算法和本文算法進(jìn)行檢測.

下面分別是2種方法的實驗結(jié)果，見圖5和圖6.

圖5 基于LSD算法檢測的棋盤角點檢測算法結(jié)果

圖6 基于投影直方圖的棋盤角點檢測算法結(jié)果

為了驗證算法的精度，本文利用如下誤差公式計算出兩種算法的棋盤檢測點與棋盤真實角點之間的誤差：

(4)

‖P0(1,0)-P(1,0)‖,…,‖P0(x,y)-P(x,y)‖},

x=0,1,…，8，y=0,1,…，9.

(4)、(5)式中erroraver表示棋盤坐標(biāo)點相對于相鄰角點距離L的平均偏差距離， max{…}表示取{…}中的最大值,‖…‖表示兩個點之間的距離，N表示棋盤角點個數(shù)，errormax表示棋盤坐標(biāo)點相對于相鄰角點距離L偏差的最大距離，P0(x,y)表示棋盤真實角點，P(x,y)表示算法檢測出的棋盤角點.

經(jīng)計算，棋盤相鄰角點之間大致距離L=44.5714，基于LSD算法檢測的棋盤角點檢測算法誤差結(jié)果errormax=17.95％，erroraver=5.57％，經(jīng)過本文算法檢測的誤差結(jié)果errormax=8.97％，erroraver=3.35％.

通過基于直線交點檢測的方法得到的結(jié)果(圖5)及誤差分析結(jié)果可以看出，與真實的棋盤角點之間誤差較大，由于棋盤角點檢測的準(zhǔn)確與否關(guān)系到后續(xù)處理的準(zhǔn)確性，所以這些誤差是不允許的，通過分析圖像和算法知道，之所以出現(xiàn)這樣的誤差一部分是由于象棋棋盤雖然角點周圍的直線大部分都被檢測出來，然而，由于棋盤角點的位置是處于檢測出的直線交點附近，并不能代表棋盤點的準(zhǔn)確位置.

通過對本文算法得到的結(jié)果(圖6)及誤差計算結(jié)果進(jìn)行分析得到，象棋棋盤點的各個角點的位置都被較準(zhǔn)確地檢測出來，比基于LSD算法檢測的棋盤角點檢測算法檢測的誤差小了將近一倍，而且本算法在不需要其他的一些比如去噪、直方圖均衡等預(yù)處理手段去增強圖像的情況下可以得到較好的棋盤角點檢測效果.

4 結(jié)語

本文提出了一種基于LSD算法和投影直方圖相結(jié)合的針對中國象棋棋盤角點的檢測算法，實驗表明，該算法在棋盤點的檢測精度上比通過直線交點檢測的算法效果好，而且在不需要其他的一些比如去噪、直方圖均衡等預(yù)處理手段去增強圖像的情況下可以得到較好的棋盤角點檢測效果 .

[1] 王忠石，徐心和.棋盤格模板角點的自動識別與定位[J]．中國圖像圖形學(xué)報,2007，12(4)：618-622．

[2] 侯建輝，林意．自適應(yīng)的Harris棋盤格角點檢測算法[J]．計算機工程與設(shè)計,2009，30(20)：4741-4801．

[3] 劉陽成，朱楓．一種新的棋盤格角點檢測算法[J]．中國圖像圖形學(xué)報,2006，11(5):606-611．

[4] Shanmugan K S,Dickey F M,Green J A,et al. An optimal frequency domain filter for edge detection in digital images[J] . IEEE Trans on Pattern Analysis and Machine Intelligence,1979 (1): 39- 47 .

[5] Prewitt J M S,Menclelsohn M L. The analysis of cell images[J] . Annals of the N Y Academy of Sciences,1966 ,128: 1035- 1053.

[6] Rafael C ,Richard E. 數(shù)字圖像處理[M].北京: 電子工業(yè)出版社,2003:463- 474.

[7] Lllingworth J,Kittler J. A survey of the hough transform[J] . Compute Vision Graphics Image Process,1988 ,44(1): 87- 116 .

[8] Grompone R,Jakubowicz J,Morel J,et al. LSD: a line segment detector[J]. Image Processing On Line,2012(1):4-10.