朱晨曦，高軍偉，房國(guó)棟，孔德帥

（青島大學(xué) 自動(dòng)化學(xué)院，青島 266071）

0 引言

作為娛樂(lè)機(jī)器人的一個(gè)分支，人機(jī)象棋正逐漸成為人們研究的熱點(diǎn)。早期，人們通過(guò)設(shè)計(jì)和制作電子棋盤傳感器的方式定位和識(shí)別人機(jī)象棋棋子，但制作電子棋盤的過(guò)程繁瑣；伴隨機(jī)器視覺(jué)的發(fā)展，圖像處理相關(guān)算法被廣泛應(yīng)用，人機(jī)象棋在視覺(jué)定位和識(shí)別方面正深入研究。

象棋定位方面，傳統(tǒng)字符[1]的定位方法需要不斷調(diào)整每個(gè)閾值,過(guò)程繁瑣。文獻(xiàn)[2]使用依據(jù)圓檢測(cè)和棋子修正的二次定位方法，存在流程運(yùn)算時(shí)間和個(gè)別字符識(shí)別準(zhǔn)確度的問(wèn)題；象棋識(shí)別方面，關(guān)于年輪統(tǒng)計(jì)[3]的識(shí)別方法雖可避免文字任意性，但特征值與字體有關(guān)，王殿君等[4]提出采用BP神經(jīng)網(wǎng)絡(luò)對(duì)棋子進(jìn)行識(shí)別，但算法過(guò)程存在局部極值和擬合現(xiàn)象，收斂速度慢，出現(xiàn)新加樣本需對(duì)整體重新訓(xùn)練。文獻(xiàn)[5]提出的使用文字連通數(shù)與孔數(shù)的方法，在非理想情況下進(jìn)行字符識(shí)別，受實(shí)際光線等因素影響較大。

故針對(duì)以上問(wèn)題，本文以三自由度機(jī)械臂為例，以人機(jī)象棋平面博弈為任務(wù)，通過(guò)剪切法和對(duì)數(shù)極坐標(biāo)&傅里葉變換的模板匹配法定位與識(shí)別棋子，后續(xù)調(diào)用博弈算法和蟻群算法，結(jié)合機(jī)械臂運(yùn)動(dòng)學(xué)的模型分析，給出了人機(jī)象棋平面博弈的實(shí)現(xiàn)方法。

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

系統(tǒng)總體設(shè)計(jì)主要由棋子定位和識(shí)別、走法產(chǎn)生、路徑規(guī)劃、機(jī)械臂控制四部分組成。

1）攝像頭捕捉棋盤圖像并傳進(jìn)計(jì)算機(jī)，計(jì)算機(jī)使用象棋識(shí)別算法識(shí)別棋盤信息。

2）結(jié)合圖像識(shí)別結(jié)果，通過(guò)調(diào)用博弈算法獲得棋局下一步走法。

3）將走法賦給蟻群算法規(guī)劃走法間路徑并得出坐標(biāo)信息。

4）根據(jù)坐標(biāo)信息，結(jié)合運(yùn)動(dòng)學(xué)逆解，Arduino控制機(jī)械臂實(shí)現(xiàn)棋子起落及平面移動(dòng)，完成人機(jī)對(duì)弈，系統(tǒng)框圖如圖1所示。

圖1 人機(jī)博弈系統(tǒng)框圖

2 象棋類型定位和識(shí)別

2.1 圖像預(yù)處理

1）桶形畸變矯正 系統(tǒng)使用分辨率1280×1024的攝像頭捕捉圖像，因鏡頭使用凸透鏡，故需對(duì)圖像進(jìn)行桶形矯正，如圖2所示。

圖2 桶形畸變矯正

2）圖像區(qū)域裁剪

對(duì)于定位問(wèn)題，由棋盤本身布局所決定，棋子僅會(huì)在90個(gè)固定交叉點(diǎn)位置起落，故攝像頭固定后，利用image viewer分別測(cè)出圖片90個(gè)交叉點(diǎn)坐標(biāo)值，再根據(jù)坐標(biāo)值依次將整張圖片裁剪成以各個(gè)交叉點(diǎn)為中心的90張小區(qū)域圖片，并對(duì)這些裁剪圖片進(jìn)行內(nèi)容識(shí)別即可。

3）象棋有無(wú)與顏色判斷

已知RGB顏色模型，轉(zhuǎn)換成HSV彩色空間后通過(guò)調(diào)整其分量閾值[6]，可對(duì)交叉點(diǎn)區(qū)域內(nèi)的象棋有無(wú)與顏色進(jìn)行判斷。

4）棋子提取及處理

判斷90張小區(qū)域圖片中存在棋子后，通過(guò)中值濾波保存邊緣信息；通過(guò)灰度二值化和hough變換圓檢測(cè)法提取圖片中棋子，通過(guò)腐蝕膨脹使棋子平滑，并統(tǒng)一成50×50尺寸。如圖3所示。

圖3 提取的棋圖

2.2 棋子種類識(shí)別

面對(duì)棋子在移動(dòng)時(shí)存在的旋轉(zhuǎn)變化量問(wèn)題，本系統(tǒng)使用對(duì)數(shù)極坐標(biāo)&傅里葉的模板匹配法[7]識(shí)別旋轉(zhuǎn)量棋子。將棋子圖像的旋轉(zhuǎn)變化經(jīng)對(duì)數(shù)極坐標(biāo)變換轉(zhuǎn)化為平移變化，再結(jié)合Fourier平移變換的模值不變性，實(shí)圖像的旋轉(zhuǎn)不變性。

2.2.1 對(duì)數(shù)極坐標(biāo)變換

在圖像處理中，對(duì)數(shù)極坐標(biāo)變換是將圖像從笛卡爾坐標(biāo)系（x，y）經(jīng)極坐標(biāo)系（ρ，θ）過(guò)渡后,轉(zhuǎn)換至對(duì)數(shù)坐標(biāo)系（u，v）[8]，轉(zhuǎn)換公式為：

式中，（xc，yc）為坐標(biāo)變換中心，k1，k2為如需放大圖像所引入的細(xì)化常量。圖4為笛卡爾-對(duì)數(shù)極坐標(biāo)對(duì)應(yīng)示意圖。

圖4 笛卡爾-對(duì)數(shù)極坐標(biāo)對(duì)應(yīng)示意圖

根據(jù)式(1)，當(dāng)原圖像旋轉(zhuǎn)βrad時(shí)，有：

式中，v和v1表示對(duì)數(shù)極坐標(biāo)中圖像轉(zhuǎn)動(dòng)前后對(duì)應(yīng)的橫坐標(biāo)。由此可知，笛卡爾坐標(biāo)系中旋轉(zhuǎn)變化可轉(zhuǎn)化成對(duì)數(shù)極坐標(biāo)系中平移變化。圖5為棋子“車”在不同旋轉(zhuǎn)角度下的平移變化。

圖5 圖像旋轉(zhuǎn)及對(duì)數(shù)極坐標(biāo)變換

2.2.2 傅立葉變換

在時(shí)域空間中，傅里葉變換的模值具有平移不變特性。在圖像處理時(shí)，圖像給出的信號(hào)為二維離散型，所以采用二維離散傅里葉變換[9]。則尺寸M×N的圖像函數(shù)f（x，y）對(duì)應(yīng)二維離散傅里葉變換f（u，v）為：

得到平移前后的模值為：

由此模值知，其時(shí)域平移不變的特性，故圖像通過(guò)式(1)～式(5)實(shí)現(xiàn)自身旋轉(zhuǎn)不變性。

2.3 算法檢驗(yàn)與結(jié)果

為檢驗(yàn)算法效果，本文利用11張各類型的棋子圖片進(jìn)行測(cè)試，分別對(duì)這些圖片做出一定的角度轉(zhuǎn)動(dòng)，并計(jì)算轉(zhuǎn)動(dòng)前后兩張圖像間相關(guān)系數(shù)。計(jì)算如表1所示。

表1 棋子轉(zhuǎn)動(dòng)前后兩圖像間相關(guān)系數(shù)

表中數(shù)據(jù)知，部分角度如90°270°時(shí)相關(guān)系數(shù)良好，部分角度如45°、135°時(shí)相關(guān)系數(shù)稍低點(diǎn)，其主要是受亮度、位置等實(shí)際因素的影響。

為建立模板庫(kù)，對(duì)11種棋子類型的每種圖片（對(duì)于顏色不同但變換相同的棋子，黑車和紅車，黑炮和紅炮，黑馬和紅馬則歸為一類），每張依次選擇0°、10°、20°、30°、40°、50°、60°、70°、80°各9個(gè)不同旋轉(zhuǎn)狀態(tài)的圖片，共 99張圖片作為模板儲(chǔ)存和調(diào)用。

綜上過(guò)程，本系統(tǒng)棋子識(shí)別流程為：

1）建立模板庫(kù)。

2）判斷裁剪的90張小圖片中有無(wú)棋子及顏色，再經(jīng)灰度、二值化等步驟提取棋子。

3）將待識(shí)棋子圖像和模板庫(kù)里的圖像作對(duì)算法變換并得到相關(guān)系數(shù)，最后將其匹配至模板庫(kù)中相關(guān)系數(shù)最大的一類。匹配結(jié)果如空白、黑將、黑車等分別用0、1、2等數(shù)字表示。

4）以10×9的矩陣形式呈現(xiàn)出所識(shí)別的90張小圖片數(shù)字結(jié)果，以利于后續(xù)博弈及蟻群算法對(duì)識(shí)別結(jié)果的調(diào)用。

5）下次識(shí)別重復(fù)步驟2）～4）。

為測(cè)試識(shí)別方法的有效性，本文選取100張棋子位置、旋轉(zhuǎn)方向皆不同的棋盤圖像在MATLAB環(huán)境下運(yùn)用，經(jīng)檢測(cè)，識(shí)別后正確率約為98%。

每當(dāng)棋子完成移動(dòng)，棋盤出現(xiàn)變化的位置，有且僅有兩處，所以不需對(duì)全部90張區(qū)域小圖片進(jìn)行重復(fù)識(shí)別，只需對(duì)位置發(fā)生變化的小圖片進(jìn)行識(shí)別。故系統(tǒng)選用差分法[10]對(duì)每張小圖片信息是否發(fā)生變化進(jìn)行判斷，之后對(duì)信息變化的小

圖片按序識(shí)別其內(nèi)容，并以新的10×9數(shù)字矩陣顯示結(jié)果，可有效提高系統(tǒng)識(shí)別速度與可靠性，圖6為棋子識(shí)別結(jié)果。

圖6 棋子識(shí)別結(jié)果

3 中國(guó)象棋人機(jī)博弈算法

博弈算法的作用是列出棋局當(dāng)前所有可能走法，并在可能走法中搜索得出最優(yōu)走法，最后用四個(gè)數(shù)字，如1234的形式（1行2列移至3行4列）將走法表示出來(lái)，其共有四個(gè)核心部分。

棋盤表示部分，通過(guò)使用[10]×[9]的二維數(shù)組方式來(lái)存取棋盤信息，在棋盤上每一個(gè)交點(diǎn)[11]都對(duì)應(yīng)數(shù)組中一個(gè)字節(jié)，所呈現(xiàn)的數(shù)值則代表在此交點(diǎn)有無(wú)棋子或種類。

走法部分列出棋局當(dāng)前所有可能走法，由估值部分對(duì)局面當(dāng)前情況進(jìn)行優(yōu)劣評(píng)估，后經(jīng)搜索部分搜索出最佳走法。搜索部分選用Alpha_Bate剪枝搜索算法，具有減少不必要節(jié)點(diǎn)搜索的優(yōu)勢(shì)。

c++為人機(jī)博弈算法編程語(yǔ)言，Visual Studio 2017為其開(kāi)發(fā)平臺(tái)，先在開(kāi)發(fā)平臺(tái)中調(diào)試好該博弈算法，然后再通過(guò)MATLAB軟件的mex功能使MATLAB能對(duì)其進(jìn)行讀取。將視覺(jué)識(shí)別所得的數(shù)字矩陣傳入象棋人機(jī)博弈算法，通過(guò)節(jié)點(diǎn)搜索，擇優(yōu)得到棋局下一步走法，之后調(diào)用蟻群算法，對(duì)棋子走法間平面移動(dòng)路徑進(jìn)行規(guī)劃。

4 路徑規(guī)劃

棋子存在兩種移動(dòng)，一種按走法移動(dòng)，另一種被吃掉后放在指定位置的移動(dòng)。蟻群算法的作用是對(duì)棋子平面移動(dòng)路徑進(jìn)行避障規(guī)劃，避免棋子在平面移動(dòng)中受其他棋子的阻礙。

4.1 路徑產(chǎn)生

系統(tǒng)對(duì)博弈算法當(dāng)前調(diào)用的10×9棋盤數(shù)字矩陣進(jìn)行實(shí)時(shí)擴(kuò)充并柵格化，有棋子位置置1，其余位置置0，最終得到一個(gè)20×20的01矩陣。

在棋盤柵格中，粒子和障礙物面積應(yīng)都按照象棋半徑大小膨化，即將粒子視為一個(gè)質(zhì)點(diǎn)時(shí)，粒子只能沿柵格水平或豎直方向移動(dòng)，即滿足：

式中，i為質(zhì)點(diǎn)當(dāng)前柵格，j為質(zhì)點(diǎn)下一柵格，a為柵格邊長(zhǎng)，map（j）為非障礙柵格，dij為柵格i和j間距離。

棋局柵格化后，經(jīng)蟻群算法得出的轉(zhuǎn)移概率為相鄰柵格中心節(jié)點(diǎn)間的選擇概率[12]，在t時(shí)刻，螞蟻k從xi轉(zhuǎn)移至xj的概率公式如下：

式中，α為信息素濃度相對(duì)重要程度，τij（t）為信息素濃度，β為啟發(fā)性因子相對(duì)重要程度ηij（t）為實(shí)際距離倒數(shù)。圖7為棋子被吃掉后從當(dāng)前位置移至棋局外指定位置的路徑仿真圖。

圖7 路徑圖

將博弈算法所得走法起止點(diǎn)換算成柵格號(hào)，賦給蟻群算法后得到一條由起止柵格編號(hào)及無(wú)障礙柵格編號(hào)結(jié)合的路徑，可用一維數(shù)組表示，并保存在文本中，以備坐標(biāo)轉(zhuǎn)換。

4.2 坐標(biāo)定位及轉(zhuǎn)換

柵格坐標(biāo)系中坐標(biāo)，并不能直接作為機(jī)械臂起落棋子的定位坐標(biāo)，須將其從柵格坐標(biāo)系{B}轉(zhuǎn)換到機(jī)械臂基底坐標(biāo)系{A}下表示。

如圖8所示，{B}為柵格坐標(biāo)系，{A}為基坐標(biāo)系。xB、yB表示棋子在柵格坐標(biāo)系OB下的位置，xA、yA表示棋子在基坐標(biāo)系OA下的位置。

圖8 坐標(biāo)系

棋子位置及移動(dòng)路徑皆對(duì)應(yīng)一個(gè)小柵格編號(hào)，每個(gè)小柵格號(hào)都可換算成直角坐標(biāo)下小柵格中心位置[13]，換算公式如下：

式中，a為小柵格邊長(zhǎng)，i為柵格編號(hào)，為每行柵格個(gè)數(shù)，mod()為取余，ceil()為正方向舍入，（ix，iy）為柵格中心直角坐標(biāo)。

根據(jù)式(8)可得到棋子在柵格坐標(biāo)系中位置，但要作為機(jī)械臂末端最終用來(lái)抓取的定位坐標(biāo)，還需要將其轉(zhuǎn)換至基坐標(biāo)系{A}下表示。對(duì)本系統(tǒng)三自由度機(jī)械臂而言，末端執(zhí)行器只需要描述其位置，通過(guò)式(9)進(jìn)行旋轉(zhuǎn)變換和平移變換二者的相加，可得點(diǎn)p相對(duì)于基坐標(biāo){A}的最終定位坐標(biāo)Ap。

將蟻群算法得到的路徑柵格號(hào)代入式(8)、式(9)可得棋子在基坐標(biāo){A}下的最終定位坐標(biāo)。將其橫縱坐標(biāo)值分別放入px，py向量中，機(jī)械臂在抓取棋子時(shí)，需確定棋子在三維空間下的坐標(biāo)[14]，故令設(shè)一組定值向量pz，表示棋子在空間中的高度。

5 機(jī)械臂控制

三自由度機(jī)械臂結(jié)構(gòu)，如圖9所示，腰部作水平方向旋轉(zhuǎn)運(yùn)動(dòng)，大臂和小臂作垂直于基座水平旋轉(zhuǎn)平面的俯仰運(yùn)動(dòng)。小臂尾部裝配一個(gè)電磁鐵，通過(guò)控制其電磁得失來(lái)控制對(duì)棋子的取置。圖10為本系統(tǒng)實(shí)物圖。

圖9 機(jī)械臂結(jié)構(gòu)圖

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

要想使機(jī)械臂末端準(zhǔn)確的運(yùn)動(dòng)到棋子上方，需要控制好每個(gè)機(jī)械臂關(guān)節(jié)轉(zhuǎn)動(dòng)的角度。為此，系統(tǒng)需要通過(guò)已解算得的定位坐標(biāo)代入機(jī)械臂逆運(yùn)算，求取每個(gè)機(jī)械連桿的轉(zhuǎn)動(dòng)角度。對(duì)本系統(tǒng)的機(jī)械臂建立如圖11所示的連桿坐標(biāo)系，然后結(jié)合表2中連桿參數(shù)，通過(guò)D-H法[15]建立三軸機(jī)械臂運(yùn)動(dòng)學(xué)模型。

圖11 機(jī)械臂連桿坐標(biāo)系

根據(jù)表2和式(10)所示的相鄰兩連桿坐標(biāo)系間變換法則求取機(jī)械臂正解，可到機(jī)械臂末端與基坐標(biāo)系{A}之間的變換矩陣，如式(11)所示。

表2 各關(guān)節(jié)D-H參數(shù)表

式中，nx、ny、nz，ox、oy、oz，ax、ay、az分別為機(jī)械臂末端坐標(biāo)系x、y、z軸在A坐標(biāo)系中的方向矢量，px、py、pz表示機(jī)械臂末端位置在基坐標(biāo)系中的坐標(biāo)。

然后求取機(jī)械臂逆解，用未知的連桿逆變換同時(shí)左乘式(11)兩端，把關(guān)節(jié)變量分離[16]出來(lái)，從而得到即：

令方程兩邊元素(4)、(5)、(6)分別對(duì)應(yīng)相等得：

此時(shí)，只需要知道機(jī)械臂末端即將運(yùn)行到目標(biāo)位置的情況[17]，即知道工件的定位坐標(biāo)px、py、pz，便可得到每個(gè)機(jī)械連桿的轉(zhuǎn)動(dòng)角度。

6 系統(tǒng)測(cè)試

本系統(tǒng)機(jī)械臂核心處理器采用Arduino控制板及Arduino IDE編程環(huán)境，機(jī)械臂為三自由度機(jī)械臂，控制機(jī)械臂運(yùn)動(dòng)的步進(jìn)電機(jī)通過(guò)A4988驅(qū)動(dòng)模塊控制，Arduino與A4988之間為脈沖寬度調(diào)制。為保證精度選用1/16步進(jìn)模式，搭配自身10:1減速比，步進(jìn)電機(jī)轉(zhuǎn)動(dòng)一圈需32000個(gè)步進(jìn)脈沖，即每個(gè)脈沖驅(qū)動(dòng)電機(jī)轉(zhuǎn)動(dòng)0.01125°。攝像頭捕捉棋盤圖像后，經(jīng)計(jì)算機(jī)處理得到棋子及路徑坐標(biāo)值，將其代入運(yùn)動(dòng)學(xué)逆解[14]得出轉(zhuǎn)動(dòng)角度，根據(jù)公式steps=θ/0.01125得到每個(gè)機(jī)械臂轉(zhuǎn)動(dòng)步進(jìn)值，之后將步進(jìn)值經(jīng)串口通信發(fā)送給下位單片機(jī)，下位單片機(jī)得到上位機(jī)的控制命令后，通過(guò)控制每個(gè)機(jī)械臂的步進(jìn)電機(jī)實(shí)現(xiàn)機(jī)械臂平面運(yùn)動(dòng)。

最后對(duì)系統(tǒng)進(jìn)行整體測(cè)試。馬的實(shí)驗(yàn)測(cè)試數(shù)據(jù)如表3所示，圖11為對(duì)弈中馬的執(zhí)行過(guò)程。

圖11 對(duì)弈棋子執(zhí)行過(guò)程

表3 實(shí)驗(yàn)測(cè)試數(shù)據(jù)

7 結(jié)語(yǔ)

本文設(shè)計(jì)基于機(jī)器視覺(jué)的人機(jī)象棋平面控制系統(tǒng)，棋子正確識(shí)別率約為98%，得出棋子當(dāng)前走法并規(guī)劃走法間路徑后，對(duì)棋子和路徑所在坐標(biāo)的定位誤差約3.5mm，方向誤差小于3°。系統(tǒng)各模塊聯(lián)機(jī)后進(jìn)行人機(jī)博弈，各模塊間穩(wěn)定配合，能對(duì)棋盤上棋子在平面移動(dòng)中實(shí)現(xiàn)良好的人機(jī)對(duì)弈，提高了棋子識(shí)別率，減小機(jī)械臂作業(yè)空間，基本達(dá)到其設(shè)計(jì)要求。