基于機器視覺的中國象棋人機博弈系統(tǒng)設計

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

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

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

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

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

1 系統(tǒng)總體設計

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

2 中國象棋棋盤、棋子圖像識別部分設計

2.1 圖像預處理

(1) 桶形畸變矯正。

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

(2) 圖像剪切。

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

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

圖1 桶形畸變矯正

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

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

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

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

圖2 棋子圖片

2.2 棋子類型識別算法

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

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

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

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

(1)

對數(shù)極坐標就是在極坐標的基礎上增加log運算。轉換關系為

(2)

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

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

當原圖像旋轉φ弧度時，有

Ψ1=Ψ+φ

(3)

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

圖4 圖像的旋轉及其對數(shù)極坐標變換

(2) 離散傅里葉變換。

眾所周知，傅里葉變換具有其模值在時域空間的平移不變性，由于圖像是二維離散信號，所以應當使用二維離散傅里葉變換[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ù)極坐標變換相結合就可以實現(xiàn)圖像的旋轉不變性。

(3) 驗證有效性。

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

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

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

2.3 識別算法與結果

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

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

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

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

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

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

3 中國象棋人機博弈算法設計

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

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

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é)點的搜索，極大地提高了搜索效率和系統(tǒng)的反應時間。

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

4 機械臂執(zhí)行部分設計

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

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

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

5 系統(tǒng)測試

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

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

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

6 結束語

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