一种基于灰度投影的中国象棋棋盘角点检测算法

段 汕，贺 兴，娄联堂，徐 文，罗 敬

(中南民族大学 数学与统计学学院，武汉 430074)

角点是图像上曲率足够高、并且位于图像中不同亮度区域交界处的点.它具有旋转不变性和不随光照条件变化而改变的优点，因而能够在图像匹配、摄像机标定、三维重建、运动物体的跟踪及模式识别等机器视觉诸多领域有着重要应用.通过提取象棋棋盘点的图像位置信息，可以确定机器视觉系统中像平面和空间坐标系之间的对应关系，从而可以通过空间平面的变化信息更新像平面中的信息，因此，象棋棋盘角点检测是摄像机校准和棋子识别以及跟踪的重要环节.现行的角点检测算法有很多种,大致可以分为两类:一类是基于边缘的角点检测算法，文献[1]通过先用Sobel算子求取棋盘格图像边缘，进而求取边缘和角点，再运用Susan算子来进行优化.另一类是基于灰度的角点检测算法，如文献[2]对Harris算子的棋盘格检测算法进行了改进，实现了对摄像机畸变较大的图像角点自动提取，文献[3]利用棋盘格图像对称和灰度值对比明显的独特性质，提出了SV算子检测方法.

上述文献提出的大部分方法在标定的图像上都要进行一些预处理，如滤波、增强等，而且在准确性和实时性上还有可以改进的地方.本文针对中国象棋棋盘角点的特点提出一种针对中国象棋棋盘基于直线检测和投影直方图检测相结合的角点检测方法.

1 棋盘图像的边缘检测和棋盘角点检测

根据对图像灰度的分析可以知道,象棋棋盘边线的灰度和周围像素的灰度不同,而且灰度变化较大,由此可以选择合适的边缘检测算子来检测出包含棋盘角点的棋盘边线.

通过对常用的各种边缘检测算子[4-6]，如Laplacian 算子、Prewitt 算子、Robert算子、Sobel 算子、Sobel 垂直算子、Sobel水平算子的比较,发现Sobel算子最适合用于对象棋棋盘边线的检测,实验表明，因为Sobel 算子可以最大程度的检测出棋盘边线,而且有相对较高的对比度和较少的噪声.

经过Sobel算子处理后发现，象棋棋盘格的格点实质上是两条棋盘直线的交点，所以只要能够正确检测出棋盘中的直线，然后求出这些直线的交点，就可以得到棋盘角点.

直线提取的算法也备受人们的关注,近20年来,人们提出了许多算法,它们各有优缺点.其中Hough变换[7]是应用最广泛的方法之一,其优点是抗噪性能好,且能连接共线短直线，但缺点是参数难以选择,且计算十分复杂,所以我们不能运用Hough变换去检测目标直线.针对这种情况文献[8]提出一种LSD算法.

通过LSD算法对二值化(图1(b))处理后的图像进行直线检测,将得到的直线标记在原图(图1(a))上，得到结果图1(c).

图1 LSD算法检测棋盘直线的结果

通过观察LSD算法的结果可以发现，棋盘角点大部分都是位于棋盘边线的交点或者交点附近，所以，可以通过检测出的直线求得这些直线的交点，从而确定象棋棋盘角点的位置.

首先，在LSD算法检测出的棋盘上的直线后，从直线方向的分布上知道棋盘中信息点(图1(a)中标出的两个点称之为信息点)处于一些斜线的交点处，而且棋盘上其他角点处于方向位于90度，180度左右直线的交点上，因此，可以通过对LSD算法检测出的直线进行分组，先求出这些斜线的交点即信息点的准确位置，然后，通过这两个点的位置可以大致确定棋盘其他角点的近似位置，由于这些直线的信息都是已知的，那么可以找到这些近似位置附近直线的交点，另外，由信息点得到的近似位置是比较接近真实棋盘角点的位置，所以，找到距离近似位置最近的交点的位置即为棋盘角点的位置.

2 改进算法—基于LSD算法和投影直方图相结合的棋盘角点检测

2.1 投影直方图检测原理

投影法是根据图像在指定方向上投影的分布特征来进行检测的.这种方法在本质上是一种统计方法.由于统计直方图是统计一幅图像中各像素点某个特征值出现的次数，只反映了图像某一个特征的频度，不包涵图像特征的空间分布关系，因此，不能准确地检测出棋盘角点的空间分布情况.

为了克服统计直方图所不能反映图像某一特征空间分布关系的缺点，本文在统计棋盘角点矩形内的灰度值的基础上，采用了投影直方图的方法，即把一幅图像的各像素点的某一个特征分别投影在水平x轴和垂直y轴上，得到这一特征信息在x方向和y方向上的分布情况，基于投影直方图的象棋角点检测是利用一个矩形窗口将棋盘格角点框在其中，通过x轴、y轴方向的投影得到其横纵坐标灰度值的和，然后求其x轴、y轴方向灰度期望，得到棋盘目标角点位置.

灰度值H在x方向、y方向上的投影分布能够反映出棋盘格角点在图像上的具体坐标位置，表示对于一幅图像在x方向、y方向的投影直方图定义如下：

(1)

(2)

其中，i表示x方向坐标，Ex(i)表示x方向投影，j表示y方向坐标，Ey(j)表示y方向投影.设P(x,y)表示算法检测出的棋盘角点，则：

(3)

图2(a)是一幅理想的象棋棋盘角点的示意图，由于只需要得到图像棋盘角点所在位置的信息，所以我们设计一个一定大小的矩形框(图2(a)中矩形边框)，对角点所在的位置进行覆盖如图2(a)，得到对应的x轴方向的投影和y轴方向的投影分别如图2(b)、(c).

图2 理想棋盘角点投影直方图

通过上述投影法，分别取x轴、y轴方向的灰度投影数组，然后计算其相应的期望值即可检测出角点所在位置的坐标.

2.2 本文方法及原理

图3说明了本文检测象棋棋盘格角点的基本原理.首先将摄像机采集的视频图像输入到计算机，由于待处理的对象必须是灰度图像，所以要先对象棋图像进行灰度化.通过观察可以发现，其实棋盘格的角点处于灰度变化明显的棋盘边线上，为了突出棋盘边线，再利用Sobel算子对其进行边缘检测，得到棋盘图像是棋盘格线明显的象棋灰度图像，然后再利用LSD算法检测出图像中的近似直线，由于棋盘中存在噪声影响，通过先对x轴、y轴方向的灰度投影进行类似平滑的处理以消除噪声的影响，最后求出x轴、y轴方向的灰度投影的最大值位置即为象棋棋盘角点的准确位置(图3为算法流程图，图4为实验效果图).

图3 算法流程

图4 算法实验结果

2.3 LSD算法和投影直方图相结合的棋盘角点检测方法

通过上述实验提出一种将两种方法结合起来的算法，步骤如下.

(1)对棋盘图像进行灰度化，边缘检测；

(2)运用LSD算法检测出棋盘中的直线；

(3)在第(2)步的基础上得到棋盘大部分直线的角度，然后通过求这些倾斜直线(方向为45度左右或者135度左右)的交点得到这两个信息点的位置(x1,y1),(x2,y2)；

(4)根据第(3)步得到的信息点的位置坐标可以得到棋盘角之间的大致距离(最近棋盘角点之间距离L=|x1-x2|/7),再通过信息点位置和棋盘角点之间的近似距离我们可以知道棋盘所有角点的近似位置；

(5)利用(x1,y1)得到它左边(右边，上方，下方)的近似坐标是(x1-L,y1)，然后以(x1-L,y1)为中心构造投影区域矩形R，长宽为L/2，选择一个一定大小的x方向或者y方向小矩形r(例如对于x方向小矩形长是L，宽是(2×radius+1)，本文radius取2)，将小矩形r在大矩形R上x方向(y方向)移动，计算出每一次移动时r中投影到x方向(y方向的)灰度值H,然后找到这样一组投影灰度值数组的最大值位置，此时x=i(y=j)，x(y)就是大矩形R中棋盘角点的行(列)位置；

(6)重复第(5)步的操作继续一步一步向周围选取棋盘角点，最终得到象棋棋盘上所有的角点坐标.

3 实验结果及分析

为了验证算法的有效性和正确性，本文通过对于摄像头采集的640 × 480大小的视频图像分别利用基于LSD算法检测的棋盘角点检测算法和本文算法进行检测.

下面分别是2种方法的实验结果，见图5和图6.

图5 基于LSD算法检测的棋盘角点检测算法结果

图6 基于投影直方图的棋盘角点检测算法结果

为了验证算法的精度，本文利用如下误差公式计算出两种算法的棋盘检测点与棋盘真实角点之间的误差：

(4)

‖P0(1,0)-P(1,0)‖,…,‖P0(x,y)-P(x,y)‖},

x=0,1,…，8，y=0,1,…，9.

(4)、(5)式中erroraver表示棋盘坐标点相对于相邻角点距离L的平均偏差距离， max{…}表示取{…}中的最大值,‖…‖表示两个点之间的距离，N表示棋盘角点个数，errormax表示棋盘坐标点相对于相邻角点距离L偏差的最大距离，P0(x,y)表示棋盘真实角点，P(x,y)表示算法检测出的棋盘角点.

经计算，棋盘相邻角点之间大致距离L=44.5714，基于LSD算法检测的棋盘角点检测算法误差结果errormax=17.95％，erroraver=5.57％，经过本文算法检测的误差结果errormax=8.97％，erroraver=3.35％.

通过基于直线交点检测的方法得到的结果(图5)及误差分析结果可以看出，与真实的棋盘角点之间误差较大，由于棋盘角点检测的准确与否关系到后续处理的准确性，所以这些误差是不允许的，通过分析图像和算法知道，之所以出现这样的误差一部分是由于象棋棋盘虽然角点周围的直线大部分都被检测出来，然而，由于棋盘角点的位置是处于检测出的直线交点附近，并不能代表棋盘点的准确位置.

通过对本文算法得到的结果(图6)及误差计算结果进行分析得到，象棋棋盘点的各个角点的位置都被较准确地检测出来，比基于LSD算法检测的棋盘角点检测算法检测的误差小了将近一倍，而且本算法在不需要其他的一些比如去噪、直方图均衡等预处理手段去增强图像的情况下可以得到较好的棋盘角点检测效果.

4 结语

本文提出了一种基于LSD算法和投影直方图相结合的针对中国象棋棋盘角点的检测算法，实验表明，该算法在棋盘点的检测精度上比通过直线交点检测的算法效果好，而且在不需要其他的一些比如去噪、直方图均衡等预处理手段去增强图像的情况下可以得到较好的棋盘角点检测效果 .

[1] 王忠石，徐心和.棋盘格模板角点的自动识别与定位[J]．中国图像图形学报,2007，12(4)：618-622．

[2] 侯建辉，林意．自适应的Harris棋盘格角点检测算法[J]．计算机工程与设计,2009，30(20)：4741-4801．

[3] 刘阳成，朱枫．一种新的棋盘格角点检测算法[J]．中国图像图形学报,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. 数字图像处理[M].北京: 电子工业出版社,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.