一種基于灰度投影的中國(guó)象棋棋盤角點(diǎn)檢測(cè)算法

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

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

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

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

1 棋盤圖像的邊緣檢測(cè)和棋盤角點(diǎn)檢測(cè)

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

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

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

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

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

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

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

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

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

2.1 投影直方圖檢測(cè)原理

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

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

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

(1)

(2)

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

(3)

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

圖2 理想棋盤角點(diǎn)投影直方圖

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

2.2 本文方法及原理

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

圖3 算法流程

圖4 算法實(shí)驗(yàn)結(jié)果

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

通過(guò)上述實(shí)驗(yàn)提出一種將兩種方法結(jié)合起來(lái)的算法，步驟如下.

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

(2)運(yùn)用LSD算法檢測(cè)出棋盤中的直線；

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

為了驗(yàn)證算法的精度，本文利用如下誤差公式計(jì)算出兩種算法的棋盤檢測(cè)點(diǎn)與棋盤真實(shí)角點(diǎn)之間的誤差：

(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)點(diǎn)相對(duì)于相鄰角點(diǎn)距離L的平均偏差距離， max{…}表示取{…}中的最大值,‖…‖表示兩個(gè)點(diǎn)之間的距離，N表示棋盤角點(diǎn)個(gè)數(shù)，errormax表示棋盤坐標(biāo)點(diǎn)相對(duì)于相鄰角點(diǎn)距離L偏差的最大距離，P0(x,y)表示棋盤真實(shí)角點(diǎn)，P(x,y)表示算法檢測(cè)出的棋盤角點(diǎn).

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

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

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

4 結(jié)語(yǔ)

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

[1] 王忠石，徐心和.棋盤格模板角點(diǎn)的自動(dòng)識(shí)別與定位[J]．中國(guó)圖像圖形學(xué)報(bào),2007，12(4)：618-622．

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

[3] 劉陽(yáng)成，朱楓．一種新的棋盤格角點(diǎn)檢測(cè)算法[J]．中國(guó)圖像圖形學(xué)報(bào),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.