(青島大學(xué) 自動化學(xué)院，山東 青島 266071)

中國象棋歷史悠久，經(jīng)過幾千年的發(fā)展，如今已在社會各階層廣泛普及,不僅是一種消遣娛樂形式，也是智力開發(fā)的一種手段。如今，中國象棋機(jī)器人等娛樂型機(jī)器人已成為機(jī)器人研究領(lǐng)域的熱點(diǎn)方向。中國象棋機(jī)器人的研究開始于本世紀(jì)初，目前中國象棋機(jī)器人在人機(jī)博弈算法方面的研究已經(jīng)日趨成熟。在棋子定位與識別方面的研究也正在深入，早期主要是利用反射光[1]、磁性原理以及射頻[2]等方法來制作電子棋盤的方式實(shí)現(xiàn)棋子的定位與識別。但是這些方法都存在棋盤制作工藝復(fù)雜、適應(yīng)性不強(qiáng)等缺點(diǎn)。如今，隨著計(jì)算機(jī)技術(shù)的發(fā)展，機(jī)器視覺技術(shù)已經(jīng)開始運(yùn)用到棋子的定位與識別中。

在棋子定位問題上，文獻(xiàn)[3]提出一種基于投影直方圖和基于LSD算法的直線交點(diǎn)檢測方法相結(jié)合的中國象棋棋盤角點(diǎn)檢測算法，該算法效果較好但是程序復(fù)雜。文獻(xiàn)[4]使用的是一種基于最小外接圓二次定位棋子的定位方法，存在個別字符定位誤差較大的問題。

在棋子識別問題上，主要是運(yùn)用漢字字符識別的方法，與傳統(tǒng)字符識別方法不同，象棋棋子在擺放時具有旋轉(zhuǎn)的任意性，針對旋轉(zhuǎn)不變性問題，Hu[5]首先于1962年提出了連續(xù)函數(shù)矩的定義，可以用來識別旋轉(zhuǎn)性目標(biāo)[6]。Khotanzad和Hong[7]在1990年提出Zernike矩方法。Hu和Zernike方法有一定的實(shí)用性，但也存在缺點(diǎn)：Hu矩方法其核函數(shù)的非正交性和在離散化的過程中仍存在一定誤差，對于紋理特征復(fù)雜的圖像識別率比較低；基于Zernike矩的方法計(jì)算復(fù)雜。文獻(xiàn)[8]提出使用基于文字連通數(shù)與孔數(shù)的方法和年輪統(tǒng)計(jì)的方法，該方法僅從理想情況下字符識別的角度進(jìn)行考慮，受實(shí)際情況中攝像頭分辨率、光照等外部因素影響較大。文獻(xiàn)[9]采用目前較為常見的神經(jīng)網(wǎng)絡(luò)文字識別算法，存在新加入樣本需重新對全體樣本進(jìn)行訓(xùn)練的問題，實(shí)時性不強(qiáng)。

針對以上問題，本文充分考慮實(shí)際應(yīng)用場景，結(jié)合中國象棋人機(jī)博弈算法，使用圖像剪切方法和基于對數(shù)極坐標(biāo)變換&傅里葉變換的模板匹配方法實(shí)現(xiàn)了棋子的定位與識別。并且通過調(diào)用中國象棋人機(jī)博弈算法，搭建中國象棋機(jī)器人硬件平臺，實(shí)現(xiàn)了中國象棋人機(jī)博弈系統(tǒng)的研制。

1 系統(tǒng)總體設(shè)計(jì)

基于機(jī)器視覺的中國象棋人機(jī)博弈系統(tǒng)主要包括三部分：① 中國象棋棋盤、棋子圖像識別部分，主要過程為將攝像頭采集模塊采集的圖像傳入計(jì)算機(jī)，通過棋子識別算法識別出棋盤信息；② 中國象棋人機(jī)博弈算法部分，通過調(diào)用中國象棋人機(jī)博弈算法，搜索得出系統(tǒng)下一步應(yīng)進(jìn)行的走法；③ 機(jī)械臂執(zhí)行部分，在上一步得到的走法的指導(dǎo)下，通過單片機(jī)控制機(jī)械臂，實(shí)現(xiàn)取子、移動、落子等操作，完成對弈過程。

2 中國象棋棋盤、棋子圖像識別部分設(shè)計(jì)

2.1 圖像預(yù)處理

(1) 桶形畸變矯正。

本系統(tǒng)圖像采集模塊采用的是普通家用USB網(wǎng)絡(luò)攝像頭，成像分辨率為1280像素×1024像素，在采集圖像的過程中，由于鏡頭凸透鏡對光線的折射作用，采集的圖像會以鏡頭中心為圓心，呈圓形向外擴(kuò)展失真，即桶形畸變現(xiàn)象，如圖1(a)所示，因此首先應(yīng)對圖像進(jìn)行桶形畸變矯正。圖1(b)為桶形畸變矯正后的圖像。

(2) 圖像剪切。

由于棋子在棋盤中的位置是相對固定的，只會出現(xiàn)在橫直線交叉點(diǎn)上，不會雜亂無章地出現(xiàn)在任意位置，因此各棋子的位置就比較容易確定。只要將攝像頭固定，然后依次測出90個交點(diǎn)的坐標(biāo)，按照坐標(biāo)值將整張圖片剪切成90張小圖片，分別識別每張小圖片中的內(nèi)容。

(3) 棋子有無及棋子顏色的判斷。

圖1 桶形畸變矯正

由于HSV顏色空間更符合人類的視覺特征，因此在HSV顏色空間進(jìn)行顏色的判斷。先將圖片從RGB顏色空間轉(zhuǎn)換到HSV顏色空間，其中顏色的類別主要由色調(diào)H和飽和度S所決定，通過設(shè)定H、S、V各分量的閾值就可以實(shí)現(xiàn)棋子顏色及棋子有無的判斷。

(4) 棋子的提取及處理。

經(jīng)過以上棋子有無的判斷之后，將含有棋子的圖片進(jìn)行灰度化、二值化、濾波等一系列操作，經(jīng)過Hough變換圓檢測算法將圖片中的棋子提取出來。

然后再對棋子圖像進(jìn)行腐蝕填充等形態(tài)學(xué)濾波操作，消除圖像上細(xì)小的噪聲，并將其統(tǒng)一處理為50像素×50像素大小，以待后面的操作。提取并處理的11種棋子圖片如圖2所示。

圖2 棋子圖片

2.2 棋子類型識別算法

本系統(tǒng)棋子類型識別算法采用的是對數(shù)極坐標(biāo)變換&傅里葉變換的模板匹配算法。

首先圖像經(jīng)過對數(shù)極坐標(biāo)變換，將旋轉(zhuǎn)變化量轉(zhuǎn)化為易于處理的平移變化量，再與傅里葉變換模值的平移不變性相結(jié)合，就實(shí)現(xiàn)了旋轉(zhuǎn)的不變性。

(1) 對數(shù)極坐標(biāo)變換。

一幅二維圖像中的每一像素的位置，可以用笛卡爾坐標(biāo)表示，也可以用極坐標(biāo)表示，它們之間存在著對應(yīng)關(guān)系[10]：

(1)

對數(shù)極坐標(biāo)就是在極坐標(biāo)的基礎(chǔ)上增加log運(yùn)算。轉(zhuǎn)換關(guān)系為

(2)

式中，k和l是為了讓變換后的圖不至于太小而人為加入的調(diào)整參數(shù)。笛卡爾坐標(biāo)與對數(shù)極坐標(biāo)的對應(yīng)關(guān)系如圖3所示。

圖3 笛卡爾坐標(biāo)系—對數(shù)極坐標(biāo)系變換

當(dāng)原圖像旋轉(zhuǎn)φ弧度時，有

Ψ1=Ψ+φ

(3)

其中Ψ和Ψ1分別為旋轉(zhuǎn)前后對數(shù)極坐標(biāo)中的橫坐標(biāo)?？梢?，通過坐標(biāo)變換，可以將笛卡爾坐標(biāo)下的旋轉(zhuǎn)量轉(zhuǎn)化為對數(shù)極坐標(biāo)下的平移量。如圖4所示，將棋子“兵”依次旋轉(zhuǎn)45°和90°，則其變換后的圖也依次平移一定的值。

圖4 圖像的旋轉(zhuǎn)及其對數(shù)極坐標(biāo)變換

(2) 離散傅里葉變換。

眾所周知，傅里葉變換具有其模值在時域空間的平移不變性，由于圖像是二維離散信號，所以應(yīng)當(dāng)使用二維離散傅里葉變換[11]。一個圖像尺寸為M×N的函數(shù)f(x,y)的二維離散傅里葉變換F(u,v)為

(4)

若將其平移一段距離，則f(x-x0,y-y0)的傅里葉變換為

F(u,v)e-j2π(ux0+vy0)/N

(5)

其模值為

|fft2[f(x,y)]|=|fft2[f(x-x0,y-y0)]|

(6)

可以看出離散傅里葉變換的時域平移不變性，將它與對數(shù)極坐標(biāo)變換相結(jié)合就可以實(shí)現(xiàn)圖像的旋轉(zhuǎn)不變性。

(3) 驗(yàn)證有效性。

為了驗(yàn)證此算法的有效性，隨機(jī)選取了6張不同棋子的圖片，將每張圖片依次旋轉(zhuǎn)一定角度，然后計(jì)算變換后的圖像與原圖像的相關(guān)系數(shù)。表1列出了經(jīng)不同的角度旋轉(zhuǎn)后的圖像與原圖像的相關(guān)系數(shù)。

表1 旋轉(zhuǎn)一定角度后的圖像與原圖像的相關(guān)系數(shù)

從表中可以看出，旋轉(zhuǎn)角度為90°、180°、270°時相關(guān)系數(shù)比較大，而在其他角度時效果不太理想，這可能是由于受實(shí)際環(huán)境中的光線、位置等的影響。因此在這里選取每張棋子圖片旋轉(zhuǎn)0°、10°、20°、30°、40°、50°、60°、70°、80°時的狀態(tài)，將車、黑將、黑士、黑象、黑卒、紅兵、紅仕、紅帥、紅相、馬、炮，11種棋子圖片，每種圖片的9個旋轉(zhuǎn)狀態(tài)，共99張圖片作為模板庫。由于黑車和紅車、黑炮和紅炮、黑馬和紅馬只是顏色的差異，變換是相同的，所以把它們作為一種。

2.3 識別算法與結(jié)果

總結(jié)以上過程，本系統(tǒng)棋子識別的一般流程如下。

① 將剪切的90張小圖片依次進(jìn)行有無棋子及棋子顏色的識別，然后將有棋子的圖片經(jīng)過灰度化、二值化、濾波及Hough變換將棋子提取出來。

② 創(chuàng)建模板庫。

③ 將待識別圖像與模板庫圖像經(jīng)過變換后作二維相關(guān)，最后將待識別的目標(biāo)歸入相關(guān)系數(shù)最大的那一類。將識別結(jié)果以數(shù)字的形式表示，例如：“0”表示空白，“1”表示黑將，“2”表示黑車，依此類推。

④ 將90張圖片的識別結(jié)果以10×9的矩陣形式表示出來，以方便將識別結(jié)果傳入中國象棋人機(jī)博弈算法中。

本文采集100張棋盤圖像，其中每個棋子位置、角度任意，并且每張圖片都各不相同，在Matlab環(huán)境下，運(yùn)用此方法識別棋盤信息。經(jīng)檢測，識別結(jié)果正確率在98%左右。在對弈過程中，由于在每次棋子移動后，棋盤中僅有兩個位置的內(nèi)容會發(fā)生變化，因此不必再重復(fù)識別所有小圖片中的內(nèi)容，僅識別發(fā)生變化的小圖片中的內(nèi)容即可。在本系統(tǒng)中，使用差分法判斷每張小圖片中的內(nèi)容是否發(fā)生變化，然后依次識別發(fā)生變化的小圖片中的內(nèi)容，之后將識別結(jié)果組成一個新的矩陣。這樣極大地提高了系統(tǒng)的反應(yīng)速度及可靠性。

3 中國象棋人機(jī)博弈算法設(shè)計(jì)

中國象棋人機(jī)博弈算法的主要作用是對一個棋盤局面列出所有合理的走法，并在其中搜索出最佳走法。該算法主要包括棋盤表示、走法產(chǎn)生、估值核心、搜索技術(shù)4個部分。

在棋盤的表示方法中，使用一個10×9個字節(jié)的二維數(shù)組來表示中國象棋的棋盤信息，數(shù)組中每一個字節(jié)代表棋盤上的一個交點(diǎn)[12]，其值表明這個交點(diǎn)上有無棋子或棋子類型。形式如下：

unsigned char position[10][9] =

{

{ 2,3,6,5,1,5,6,3,2 },

{ 0,0,0,0,0,0,0,0,0 },

{ 0,4,0,0,0,0,0,4,0 },

{ 7,0,7,0,7,0,7,0,7 },

{ 0,0,0,0,0,0,0,0,0 },

{ 0,0,0,0,0,0,0,0,0 },

{ 14,0,14,0,14,0,14,0,14 },

{ 0,11,0,0,0,0,0,11,0 },

{ 0,0,0,0,0,0,0,0,0 },

{ 9,10,13,12,8,12,13,10,9 }

};

之后通過走法產(chǎn)生程序羅列出一個局面的所有可能的走法，通過估值程序評估一個局面的優(yōu)劣程度。搜索算法采用的是Alpha_Bate剪枝搜索算法。Alpha_Bate剪枝搜索算法相較于傳統(tǒng)的極大-極小值搜索算法減少了不必要節(jié)點(diǎn)的搜索，極大地提高了搜索效率和系統(tǒng)的反應(yīng)時間。

通過中國象棋人機(jī)博弈算法，將搜索產(chǎn)生的下一步走法以一個4位數(shù)的形式表示出來，例如“abcd”，即表示將棋盤中第“a”行第“b”列的棋子，移動到第“c”行第“d”列。中國象棋人機(jī)博弈算法通過C++程序語言實(shí)現(xiàn)，開發(fā)平臺為Visual Studio 2017。將此算法在Visual Studio 2017中調(diào)試好之后，在Matlab中使用mex命令將其轉(zhuǎn)換為Matlab可識別的文件。在圖像識別部分產(chǎn)生識別結(jié)果矩陣后直接將矩陣傳入中國象棋人機(jī)博弈算法中，經(jīng)過搜索產(chǎn)生下一步的走法，之后調(diào)用串口將下一步走法發(fā)送到下位機(jī)單片機(jī)中，以指導(dǎo)機(jī)械臂的動作。

4 機(jī)械臂執(zhí)行部分設(shè)計(jì)

這一部分核心控制器采用的是基于ARM CortexTM-M3內(nèi)核的32位RISC處理器STM32F103ZET6單片機(jī)[13]，機(jī)械臂為4自由度機(jī)械臂，共5個數(shù)字舵機(jī)。在機(jī)械臂頂端安裝一個電磁鐵，通過控制電磁鐵的得失電實(shí)現(xiàn)對鐵質(zhì)棋子的拿起和放置操作。

單片機(jī)控制的機(jī)械臂的運(yùn)動主要是通過控制舵機(jī)來實(shí)現(xiàn)的。舵機(jī)的控制信號為周期是20 ms的脈寬調(diào)制(PWM)信號，其中脈沖寬度為0.5～2.5 ms，對應(yīng)舵機(jī)的旋轉(zhuǎn)角度為-90°～90°[14]，呈線性變化。也就是說，給它提供一定寬度的PWM信號，它的輸出軸就對應(yīng)一個固定的角度，無論外界轉(zhuǎn)矩怎樣改變。

因此在本系統(tǒng)中將棋盤上每個點(diǎn)對應(yīng)的機(jī)械臂上每個舵機(jī)應(yīng)轉(zhuǎn)動的角度，即對應(yīng)的脈寬量存入一個數(shù)組。當(dāng)單片機(jī)接收到串口發(fā)送的走法信息后，就會給各個舵機(jī)發(fā)送相應(yīng)寬度的脈沖，實(shí)現(xiàn)將目標(biāo)棋子移動到目標(biāo)位置。因?yàn)楸鞠到y(tǒng)中舵機(jī)數(shù)量較多，需要的電流較大，因此各舵機(jī)采用單獨(dú)供電，以提高系統(tǒng)的穩(wěn)定性，同時舵機(jī)應(yīng)與單片機(jī)系統(tǒng)共地。

5 系統(tǒng)測試

本系統(tǒng)實(shí)物圖如圖5所示。

圖5 系統(tǒng)實(shí)物圖

本系統(tǒng)使用的計(jì)算機(jī)CPU為Intel Core i5-3230M，主頻2.6 GHz，系統(tǒng)運(yùn)行環(huán)境為Matlab 2014a，將系統(tǒng)搭建完成后，對該系統(tǒng)進(jìn)行測試，測試內(nèi)容主要包括棋子位置與類型的識別，機(jī)械臂取子、移動、落子等動作。經(jīng)過測試，各功能模塊都能很好地實(shí)現(xiàn)各自的功能，之后對各模塊進(jìn)行聯(lián)機(jī)調(diào)試，挑選幾名象棋愛好者，同機(jī)器人進(jìn)行對弈測試，在真實(shí)的對弈環(huán)境中，各模塊配合良好，運(yùn)行穩(wěn)定，很好地實(shí)現(xiàn)了棋子的識別，以及機(jī)械臂取子、移動和落子等操作。

6 結(jié)束語

本文設(shè)計(jì)的基于機(jī)器視覺的中國象棋人機(jī)博弈系統(tǒng)，能夠良好地實(shí)現(xiàn)人機(jī)對弈的過程，克服了電腦象棋軟件對游戲者長時間下棋帶來的眼睛疲勞及枯燥乏味感，增強(qiáng)了趣味性，特別適合兒童和老年人。并且象棋機(jī)器人經(jīng)過改造更可以應(yīng)用于其他領(lǐng)域，前景非常廣闊。另外，本系統(tǒng)還偶爾存在棋子識別不準(zhǔn)確影響系統(tǒng)運(yùn)行的情況，因此，進(jìn)一步提高棋子識別的準(zhǔn)確率將是以后研究的重點(diǎn)。