Main > Laser & Optoelectronics Progress >  Volume 56 >  Issue 8 >  Page 081007 > Article
  • View Full Text
  • Abstract
  • View Summary
  • Figures (11)
  • Tables (4)
  • Equations (0)
  • References (19)
  • Get PDF(in Chinese)
  • Paper Information
  • Received: Oct. 17, 2018

    Accepted: Nov. 22, 2018

    Posted: Apr. 1, 2019

    Published Online: Jul. 26, 2019

    The Author Email: Han Xie (290949559@qq.com), Zhao Rong (tm_zhaorong@126.com), Sun Fusheng (sfs2699@163.com)

    DOI: 10.3788/LOP56.081007

  • Get Citation
  • Copy Citation Text

    Xie Han, Rong Zhao, Fusheng Sun. Methods for Location and Recognition of Chess Pieces Based on Convolutional Neural Network[J]. Laser & Optoelectronics Progress, 2019, 56(8): 081007

    Download Citation

  • Category
  • Image Processing
  • Share
Laser & Optoelectronics Progress, Vol. 56, Issue 8, 081007 (2019)

Methods for Location and Recognition of Chess Pieces Based on Convolutional Neural Network

Han Xie*, Zhao Rong**, and Sun Fusheng***

Author Affiliations

  • Department of Data Science and Technology, North University of China, Taiyuan, Shanxi 030051, China

Abstract

The traditional image processing algorithms used for the location of Chinese chess pieces have high complexity and the traditional character recognition methods used for the recognition of chess pieces have low generalization and accuracy. A segmentation method based on chess piece color features and an improved binary image filtering algorithm are proposed to achieve the fast location of chess pieces, and the second correction of positions is not needed. A recognition method of chess pieces based on a convolutional neural network is proposed, which can be used for the recognition of chess pieces with different fonts. In the case of chess piece replacement, this method can still recognize chess pieces quickly and accurately. The experimental results show that as for the proposed method, the location error is 0.51 mm, the average location time is 0.212 s, and the average recognition accuracy of chess pieces with four types of fonts is about 98.59%. The effectiveness and practicability of this method are confirmed.

keywords

1 引言

中国象棋是一款经典游戏,其变化多端,趣味无穷,是中华文化的精粹之一。随着机器人技术的快速发展,象棋机器人的智能化程度不断提高。针对象棋机器人的视觉部分,棋子定位和识别尤为重要。

棋子定位决定了机器人是否可以准确地抓取棋子,完成走子。Li等[1]采用传感器模式,以棋盘作为传感器来定位棋子,这种模式响应快,准确度高,但智能性低、通用性差。类似的还有刘飞等[2]的射频方法。许丰磊等[3-5]均依靠棋盘直线检测或交点检测,无法脱离棋盘定位棋子,且定位精度不高。娄联堂等[6]通过图像减法定位棋子,但该方法对相机和棋盘的稳定性要求高。Wu等[7]利用形态学滤波和Hough圆检测定位棋子,该方法在光照的强干扰下, Hough检测的时间增加,效率降低。朱一峰[8]对图像去噪后,根据像素特征统计每一个棋子的像素累加值,再通过调整阈值来分割棋子,该方法在光照不断变化的环境下,需要频繁调整阈值,适应性较差。郭晓峰等[9]利用像素特征粗定位,再利用Hough圆检测二次定位,该方法在提高准确度的同时,增加了算法运行时间,而且棋子在选材上突出了棋子边缘,不是生活中对弈的棋子,降低了方法的普适性。

棋子识别决定智能博弈算法是否可以准确地计算走棋策略。棋子上的文字具有角度任意性,而且不同的字体,其特征也不同,这样加大了棋子识别的难度。目前,针对象棋文字的识别研究不多。郭晓峰等[9]利用旋转差分法识别棋子。翟乃强[10]使用过轮数法统计文字特征。冯元华等[11]使用文字连通数统计文字特征。党宏社等[12]利用ORB(ORiented Brief)提取文字特征识别棋子。郭建欣等[13]利用Hu的7个不变距作为文字特征进行训练,识别棋子。文献[ 9-13]中,由于棋子文字的复杂性,特征提取方法不能较好地处理字体多变的棋子文字,在棋子字体发生变化时,需要人工定义重要的特征点位置或调整文字旋转角度,极大地降低了对不同棋子字体的适用性。王殿君等[14-15]采用BP(back propagation)神经网络对棋子进行识别,但该网络收敛速度慢,网络结构的选择依靠经验,权值不能共享,具有网络训练失败的可能性。

Sign up for Laser & Optoelectronics Progress TOC

Get the latest issue of Laser & Optoelectronics Progress delivered right to you!

Sign up now

针对上述问题,从棋子定位和棋子分类识别两方面入手进行优化。首先,在棋子定位上,由于传统的图像处理方法从速度和算法复杂度上优于卷积神经网络的目标检测,且准确度高,故本文根据文字像素特征,将棋子按颜色分别二值化,再应用本文提出的二值图像滤波算法对图像进行去噪,并绘制轮廓、寻找最小外接圆,定位棋子。在棋子的分类识别上,与传统的文字识别方法相比,卷积神经网络的目标分类算法准确度高,在字体样本不同的情况下,不需要人工反复定义文字特征,而且在模型训练完成后,可以对多种常见棋子的文字字体进行识别,泛化能力更好。卷积神经网络应用局部感知野降低参数,收敛速度快,而且权值共享,优于BP神经网络。所以本文选择传统图像处理和卷积神经网络相结合的新方法对棋子定位和识别。

2 整体结构

首先,对采集的棋局图像进行棋子的分割和定位;其次,将定位后的棋子图像作为数据输入,输入至本文的卷积神经网络进行棋子的分类和识别,并将识别结果标注在图像上。整体算法流程图,如图1所示。

Flow chart of whole algorithm

Figure 1. Flow chart of whole algorithm

Download full sizeView all figures

3 棋子定位

棋子定位算法流程,如图2所示。

Flow chart of algorithm for location of chess pieces

Figure 2. Flow chart of algorithm for location of chess pieces

Download full sizeView all figures

3.1 图像预处理

由于受空间的限制,相机的光轴不垂直于棋盘,为了降低棋子的定位误差,需要对图像进行预处理。

首先,采用双线性插值法对图像进行密集透视变换,保持承影面上投影几何图形不变。双线性插值是在x,y方向上分别进行一次线性插值。因此,可以准确得到变换后图像上某点P(x,y)的像素值f(P),如(1)式、(2)式所示,先在x方向上进行线性插值:

f(R1)x2-xx2-x1f(Q11)+x-x1x2-x1f(Q21),whereR1=(x,y1),(1)f(R2)x2-xx2-x1f(Q12)+x-x1x2-x1f(Q22),whereR2=(x,y2)(2)

再在y方向上进行线性插值,得到点P(x,y)的值,即

f(x,y)=f(P)y2-yy2-y1f(R1)+y-y1y2-y1f(R2),(3)

式中:Q11(x1,y1),Q12(x1,y2),Q21(x2,y1),Q22(x2,y2)为源图像上的4个点,R1(x,y1),R2(x,y2)为根据源图像上点的坐标而定义的两个点。

其次,消除背景对棋子分割的干扰,减少处理时间,增加定位精度,对透视变换后的图像设置ROI(Region of Interest),如图3所示。

Chessboard pretreatment. (a) Perspective transformation picture; (b) ROI picture

Figure 3. Chessboard pretreatment. (a) Perspective transformation picture; (b) ROI picture

Download full sizeView all figures

3.2 棋子定位

3.2.1 棋子分割

象棋棋子具有两个显著特征:形状和文字颜色。若直接用Hough圆检测分割棋子,则计算量大,且检测不准确。所以选择文字颜色特征作为分割依据。

本文采用HSV颜色模型,其中H表示色调、S表示饱和度、V表示明度,经过实验后得到红、绿棋子的HSV分量值为:红色H(1-15)、S(60-225)、V(0-93),绿色H(0-95)、S(0-255)、V(0-93)。确定SV值的范围,可以使棋子在不同光照条件下的分割稳健性更好。

3.2.2 改进二值图像滤波算法

根据某一种颜色特征分割棋子后,在二值图像上会产生另一种颜色的噪声,造成过分割。因此需要对二值图像进行滤波,所提滤波算法如下。

1) 标记图像中的各个连通区域。假如当前像素值为0,就移动到下一个位置扫描。假如当前像素值为1,检查它左边和上边的两个邻接像素(这两个像素一定会在当前像素之前被扫描到)。考虑两个像素值和标记的组合有4种情况:(a)它们的像素值都为0,此时给当前像素一个新的标记(表示一个新的连通域的开始);(b)它们中间只有一个像素值为1,此时当前像素的标记等于像素值为1的标记;(c)它们的像素值都为1且标记相同,此时当前像素的标记等于该标记;(d)它们的像素值为1且标记不同。将其中的较小的值赋给当前像素,之后从另一边回溯到区域的开始像素为止,每次回溯再执行上述4个判断步骤。这样可以保证所有的连通域都被标记出来。

2) 设定阈值T,对所有标记的连通域计算其像素累加值S。令P(x,y)为二值图像上的某个像素值,则

P(x,y)=255,S<T0,S>T(4)

根据(4)式,如果S<T时,则认为此连通域为噪声,将其剔除,反之,则保留。这样,就可将棋子的二值图像滤波到理想的分割效果。

3.2.3 棋子定位

棋盘进行滤波后,需要定位棋子的像素坐标。因此,本文提出了一种棋子定位算法。

1) 图像线性混合。将棋子分割并滤波后的两幅二值图像叠加,如图4所示。

Linear mixture picture

Figure 4. Linear mixture picture

Download full sizeView all figures

2) 棋子膨胀运算。将棋子所在区域与10×10的核进行卷积,求局部最大值,即

dst(x,y)=max(x',y') src(x+x',y+y'),s.t. element(x',y')0,(5)

式中:dst为目标图像,src为源图像,element(·)为自定义卷积核,参数包含核的形状、大小和参考点,(x',y')为核覆盖区域的像素点的最大值点,并把这个最大值赋值给参考点(x+x',y+y')指定的像素,最终得到目标图像。

3) 寻找最小外接圆。由于圆具有唯一确定性,因此用最小外接圆包围膨胀运算后的棋子轮廓,从而得到用绿色标识的棋子圆心坐标,即棋子的像素位置,如图5所示。

Location picture of chess pieces

Figure 5. Location picture of chess pieces

Download full sizeView all figures

通过上述棋子定位算法,可以简单、高效、准确地快速确定棋子的像素坐标,不需要多次修正棋子坐标。

4 基于卷积神经网络(CNN)的棋子识别

因为棋子上字符的复杂性,其传统特征提取方法不能处理多变的汉字外形,而且需要专业人工定义特征点位置,没有统一标准,所以本文选择基于CNN的棋子识别方法,自动生成其特征,进行网络训练,完成棋子的识别。

在第3节中,已经用红色圆准确定位出棋子。本节将图5中棋盘上的所有棋子提取出来,放入本文训练好的CNN中进行棋子的分类和识别。本节识别算法流程如图6所示。

Flow chart of recognition algorithm

Figure 6. Flow chart of recognition algorithm

Download full sizeView all figures

4.1 卷积神经网络(CNN)

卷积神经网络(CNN)是一种多层的有监督的特征学习网络,具有极强的适应性,善于挖掘数据的局部特征,提取全局训练特征和分类。CNN利用局部感知和神经元之间的权值共享来降低网络模型的复杂度,降低权值的数量,从而加快网络的训练和学习速度,并且使用反向传播算法,使得网络更加收敛,得到更好的训练模型。

CNN的卷积层和池化层是实现卷积神经网络特征提取功能的核心模块。该网络模型通过采用梯度下降法优化损失函数,找到全局最优解。通过频繁的迭代训练可以提高网络精度。CNN的低层由卷积层和最大池化层交替组成,高层是全连接层中对应传统多层感知器的隐含层和逻辑回归分类器。其中,第一个全连接层的输入是由卷积层和子采样层进行特征提取得到的特征图像;最后一层输出层是一个分类器,可以采用逻辑回归、Softmax回归,甚至支持向量机(SVM),对图像进行分类。

4.2 网络结构设计

目前常用的CNN模型有AlexNet[16]、VGG[17]、LeNet[18]、GoogleNet[19]等。其中AlexNet网络模型网络数较少,精度高;使用Dropout、Data augmentation(数据扩充),避免过拟合;使用局部归一化(LRN),有助于增加泛化能力。因为本文的数据集相对较少,每类的样本相对单一,要尽量避免过拟合,所以,本文选择AlexNet模型,对其改进并用于象棋棋子的分类识别。本文网络结构如图7所示。

网络结构配置信息和数据,如表1表2所示。表中conv为卷积层,Num_Filter为滤波器数量,LRN为局部响应归一化,FC为全连接,ReLu为激活函数。

Network structure

Figure 7. Network structure

Download full sizeView all figures

  • Table 1. Configuration information and data of network structure (Conv1-Conv4 layout data)

    View tableView all Tables

    Table 1. Configuration information and data of network structure (Conv1-Conv4 layout data)

    ConvConv1Conv2Conv3Conv4
    Data_Size100×100×348×48×3224×24×6424×24×128
    Conv: Num_Filter3264128128
    Conv: padding0211
    Conv: Filter_Size5×5×35×5×323×3×6424×24×128
    Conv: stride1111
    Data_Size after convolution96×96×3248×48×6424×24×12824×24×128
    ActivationReLUReLUReLUReLU
    Data_Size after activation96×96×3248×48×6424×24×12824×24×128
    Pooling: Kernel_Size2×22×22×2
    Pooling: stride222
    Data_Size after pooling48×48×3224×24×6424×24×12812×12×128
    LRN(Data_Size)48×48×3224×24×6424×24×12812×12×128
  • Table 2. Configuration information and data of network structure(FC1-FC3 layout data)

    View tableView all Tables

    Table 2. Configuration information and data of network structure(FC1-FC3 layout data)

    FCFC1FC2FC3
    Data12×12×1281024512
    Data after FC1024102414
    ActivationReLUReLU
    Data after activation10241024
    Dropout Kept_prob0.50.5
    Data after dropout fitting1024512

最后选择Softmax分类器进行棋子分类识别。它是以多项式分布为模型进行建模。假如网络输出为x1x2、…、xn,经过Softmax函数进行回归处理,Softmax函数可表示为 softmaxxi=x'i=exp(xi)j=1nexp(xj),(6)式中:i,j表示类别索引(i=1,2,…,n);n为分类数(n=14)。将网络的原始输出用作置信度来生成新的输出,其满足概率分布。Softmax分类器的损失函数可表示为 J(x,y,θ)=-1Ni=1Nj=1n1yi=jlogexp(θTjxi)j=1nexp(θTjxi),(7)式中:N为图像数量;θ∈Rn+1为Softmax分类器的模型参数;yi为每幅图像的标记;j为类别;1 yi=j为指示性函数。指示性函数规则为:1{值为真的表达式}=1,1{值为假的表达式}=0。最后通过随机梯度下降法最小化误差函数。

5 实验与结果分析

5.1 棋子数据集

Examples of chess data

Figure 8. Examples of chess data

Download full sizeView all figures

5.2 实验结果与分析

5.2.1 棋子定位实验利用本文的棋子定位方法,在HSV值不变的情况下[红色H(1-15)、S(60-225)、V(0-93),绿色H(0-95)、S(0-255)、V(0-93)]对棋子定位,实验结果如表3所示,定位平均误差为0.51 mm。将所提棋子定位方法与许丰磊等[3-14]的实验数据进行对比,结果如表4所示。由实验结果可知,所提棋子定位方法在时间和误差上都优于其他两种方法,可以更准确地抓取棋子。

  • Table 3. Location experiment of chess pieces

    View tableView all Tables

    Table 3. Location experiment of chess pieces

    PieceTime ofsegmentation /sCoordinate of imageCalculated coordinateActual coordinateError /mm
    Col /pixelRow /pixelX /mmY /mmX' /mmY' /mm
    Red_Car0.1731292.88972.66-56.816-101.251-56.7-100.21.09
    Red_House0.1771286.983921.603-57.532-32.759-57.5-61.61.15
    Red_Ele0.1911279.039869.282-57.568-21.625-57.4-21.50.2
    Red_Knight0.2071273.411824.562-57.6515.628-57.515.60.15
    Marshal0.1821266.772777.076-57.10756.284-57.156.40.12
    Red_Gun0.1861189.585919.27320.505-62.27920.5-61.70.58
    Red_Pawn0.181128.461776.13261.96455.66761.755.80.29
    Green_Pawn0.185986.305614.135185.19210.372186.2210.81.1
    Green_Gun0.182943.496979.248219.448-64.996219.6-650.15
    General0.179854.364771.18299.64657.123299.557.50.4
    Green_Knight0.184850.955814.87300.59719.501300.119.20.36
    Green_Ele0.183849.73863.732298.672-21.476299.1-21.60.45
    Green_House0.183845.265918.192298.95-65.306298.8-65.90.61
    Green_Car0.186843.988956.32298.05-101.029297.6-101.30.53
    Total piece0.208------0.51
  • Table 4. Comparison of experimental results

    View tableView all Tables

    Table 4. Comparison of experimental results

    Experimental dataProposed methodRef. [3]Ref. [14]
    Location time /s0.2120.484-
    Location error /mm0.51-0.87

5.2.2 棋子识别实验

使用本文的CNN网络结构对22400个样本进行训练,迭代次数为20;对5600个样本进行验证,其训练和验证准确率、训练和验证损失值,如图9(a)、(b)所示。

任意抽取4类字体的棋子,任意角度的摆放在棋盘上,进行识别,并将识别结果标注在指定位置。所提方法的识别准确率平均在98.59%左右。4类字体棋子的部分实验结果,如图10所示,矩形框中表示识别结果和识别概率。

选取杜俊利等[5]中的实验样本为字体一,郭晓峰等[9]中的实验样本为字体二,字体三、四为4类字体中的其他两种。应用杜俊利等[5]、郭晓峰等[9]中给出的实验参数,与本文方法作比较,棋子识别准确率的结果如图11所示,对于不同的字体在文字特征没有被人工反复定义的情况下,本文可以很好地保持棋子识别的准确率,提高了识别的效率。

Training and verification results of proposed method. (a) Training accuracy and validation accuracy; (b) training loss and verification loss

Figure 9. Training and verification results of proposed method. (a) Training accuracy and validation accuracy; (b) training loss and verification loss

Download full sizeView all figures

Recognition results of chess pieces based on CNN. (a) Partial experimental results 1; (b) partial experimental results 2

Figure 10. Recognition results of chess pieces based on CNN. (a) Partial experimental results 1; (b) partial experimental results 2

Download full sizeView all figures

Comparison of experimental results

Figure 11. Comparison of experimental results

Download full sizeView all figures

6 结论

采用传统的图像处理和文字识别方法时,中国象棋棋子的定位算法复杂,识别方法泛化能力较差、精确度较低,为此提出一种基于棋子颜色特征的分割方法和改进的二值图像滤波算法,以及一种基于卷积神经网络的棋子识别方法。实验表明,该方法的平均定位误差为0.51 mm,平均定位误差为0.212 s;对4类字体棋子的识别正确率达到98.59%。实验证实了本文方法在棋子识别和定位中的有效性和泛化性。

References

[1] Li S G, Yang X L. Design of intelligent line-tracking chess robot based on STM32[J]. Journal of Measurement Science and Instrumentation, 5, 59-63(2014).

[2] Liu F, Lü X G. Effects of drug and its packaging on the performance of UHF RFID tag[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 29, 563-568(2017).

[3] Xu F L. The research of the vision algorithm and intelligent control software for chess robot[D]. Haerbin: Harbin Institute of Technology, 9-13(2006).

[4] Xiao K X. Research and development of embedded vision system of chess robot[D]. Beijing: North China University of Technology, 15-26(2010).

[5] Du J L, Zhang J F, Huang X H. Chess-board recognition based on vision[J]. Computer Engineering and Applications, 43, 220-222, 232(2007).

[6] Lou L T, Qian L, Duan S, et al. Chessman recognition of Chinese chess based on video image understanding[J]. Journal of South-Central University for Nationalities (Natural Science Edition), 33, 117-122(2014).

[7] Wu G, Tao J. Chinese chess recognition algorithm based on computer vision. [C]∥China Control and Decision-Making Conference, 31 May-2 June 2014, Changsha, China. New York: IEEE, 3375-3379(2014).

[8] Zhu Y F. Visual recognition algorithm of Chinese chess robot[J]. Journal of Jianghan University (Natural Science Edition), 41, 51-56(2013).

[9] Guo X F, Wang Y N, Zhou X E, et al. Chess-piece localization and recognition method for Chinese chess robot[J]. CAAI Transactions on Intelligent Systems, 13, 517-523(2018).

[10] Zhai N Q. Improved Chinese chessboard recognition method[J]. Journal of Computer Applications, 30, 980-981(2010).

[11] Feng Y H, Wang S H, Liu N, et al. Application of machine vision technology in design of chess playing intelligent robot[J]. Computer Engineering and Design, 30, 3371-3373, 3379(2009).

[12] Dang H S, Zhang C, Pang Y, et al. Research of fast recognition and positioning system of chess based on ORB algorithm[J]. Science Technology and Engineering, 17, 52-57(2017).

[13] Guo J X, Chen W Y. Chesslocation and recognition by screening the feature of polar coordinates projection amplitude[J]. Science Technology and Engineering, 18, 268-275(2018).

[14] Wang D J. Recognition andpositioning technique of Chinese chess based on vision[J]. Journal of Tsinghua University(Science and Technology), 53, 1145-1149(2013).

[15] Duan Y T, Li Q, Shen W. Chess identification & location in the system of human-machine interaction based on vision[J]. Computer and Digital Engineering, 43, 1416-1418, 1485(2015).

[16] Panteley E, Loria A. On global uniform asymptotic stability of nonlinear time-varying systems in cascade[J]. Systems & Control Letters, 33, 131-138(1998).

[17] Cao K C, Yang H, Jiang B. Formation tracking control of nonholonomic chained form systems. [C]∥2013 10th IEEE International Conference on Control and Automation (ICCA), 12-14 June 2013, Hangzhou, China. New York: IEEE, 846-851(2013).

[18] Zhou Y, Dong X W, Lu G. et al. Time-varying formation control for unmanned aerial vehicles with switching interaction topologies. [C]∥2014 International Conference on Unmanned Aircraft Systems (ICUAS), 27-30 May 2014, Orlando, FL, USA. New York: IEEE, 1203-1209(2014).

[19] Hua M D, Hamel T, Morin P. et al. Introduction to feedback control of underactuated VTOL vehicles[J]. IEEE Control Systems Magazine, 33, 61-75(2013).

Please Enter Your Email: