基于DSP的人工路标识别算法的实现

刘纪红，张 璐，赵东升

(东北大学信息科学与工程学院，沈阳110819)

基于DSP的人工路标识别算法的实现

刘纪红*，张 璐，赵东升

(东北大学信息科学与工程学院，沈阳110819)

针对以人工路标作为引导标识的视觉导航技术，提出了一种基于导引灯的人工路标识别算法。首先利用基于灰度信息的识别算法对路标上导引灯进行识别与定位;然后，利用交比不变性进行数字的初步定位;最后用投影法进行数字分割，主成分分析法(PCA)和最小距离分类器的模式识别方法对数字进行识别。算法在ICETEK-DM6437-B评估板上实现。实验表明，该算法具有很高的稳定性并能较好地满足实时性的要求。

视觉导航;人工路标;交比不变性;PCA;最小距离分类器

视觉导航［1-2］是未来导引技术中的主要发展方向，而路标识别是实现各种导航系统众多功能中的基础性技术。为了降低模式识别的难度，以及克服一些识别算法实时性差的不足，人们开始研究设计特殊的人工路标。因此，设计合理巧妙的人工路标系统是关键技术之一［3］。目前，这种基于人工路标的导行系统［4］也引起了世界各国学者关注。

随着嵌入式计算机的快速发展，DSP的功能越来越强，速度越来越快，性价比也越来越高，可以满足视频处理技术中视频信号的大运算量和实时性等要求;CCD(Charge Coupled Device)摄像头的性能在不断提高，成本也在不断降低。这些因素给机器视觉导航提供了硬件基础。

本文参考郭阳［5］提出的基于交比不变性的人工路标模式，在一定理论研究基础上，讨论在DSP系统中实现的人工路标识别算法，并进行硬件测试。

1 人工路标识别硬件平台

本设计中人工路标识别采用以TI达芬奇系列单核DSP TMS320DM6437为核心芯片的ICETEKDM6437-B评估板［6］为硬件平台。ICETEK-DM6437 -B评估模块是独立的开发平台，包括各种板上外设，是专为视频和图像应用开发的处理平台。核心芯片DM6437是一款专用于数字图像处理的高性能32 bit定点DSP处理器，工作主频高达600 MHz，处理性能达4800 MI/S。DM6437可通过片上视频输入/输出接口，即视频子系统VPSS(Video Processing Subsystem)进行视频的输入和输出。VPSS包括视频处理前端VPFE (Video Processing Front End)和视频处理后端VPBE (Video Processing Back End)，分别负责视频的输入和输出。

人工路标识别的硬件系统结构框图如图1所示。

(1)视频采集模块:CCD摄像头采集图像;板载TVP5146视频解码芯片，用于将CCD摄像头采集到的模拟视频格式数字化和译码成数字视频分量格式，并送到核心处理器。

(2)DSP核心处理模块:接收解码图像，并进行图像处理

(3)显示模块:TFT彩色显示器用于显示结果。

图1 人工路标识别硬件系统结构框图

2 人工路标设计

2.1 参考的人工路标模式

一个好的人工路标应具备可探测性、可定位性和可识别性。本文通过广泛调研，决定参考郭阳［5］提出的基于交比不变性［7-8］的人工路标(图2)，并对其进行改进，以适应嵌入式平台上有限的资源以及对实时性的要求。

由图2可以看出，人工路标由3部分构成:两个垂直的同宽度的长黑带;4个水平的同宽度的长黑带;还有两个数字。实际路标中没有编号，6个黑带上的数字是为方便说明而加上去的。

图2 基于交比不变性的新型人工路标模式

图2中的6个黑带用来计算交比值，从而对数字进行初步定位。对于不同的路标模式，6个黑带无论大小还是位置都是完全相同的。而用两个不同的数字来区别不同的路标模式。由于每个数字可从0到9来选择，因此从00到99可以组成100种不同的路标模式。利用黑带构造交比的优点是在倾斜状态下，交比值仍不变。从而保证路标倾斜时也能成功探测和识别路标，这样大大的提高了路标探测的稳定性。

实际上图2中的这些黑带是用来构造两个不同方向交比的。用扫描线与路标中两个垂直的黑条的4个交点就可以得到一个水平方向上的交比值，如图3(a)所示。同样用扫描线与路标中两个数字左或右两个横着的黑条的4个交点就可以得到一个垂直方向上的交比值(图3(b)所示)。

图3 黑带构造交比

路标设计完成之后，水平和垂直方向的交比值是已知的。如果在采集到的图像中得到了相同的交比值，那么就可以记录下黑带关键点的坐标，同时分割出两个数字的小矩形，进而识别不同的数字。

2.2 改进的人工路标模式

郭阳在其论文中指出，此路标在过于复杂的背景环境中很难快速分离出来，有时甚至会造成误判［5］。于是，为适应复杂背景下对路标的快速搜索，本文对其结构做了一定的改进，即在此基础上加入了引导灯，即一个高亮度圆形发光体，非常容易从复杂背景中分离出来。同时，将右侧黑带的高度做了一定的调整，使其交比值与左侧不同。这样的结构有利于导引车摄像头的校准。例如，当摄像头仅仅采集了路标的右半部分时(图4)，导引车可已通过摄像头检测到的交比值迅速确定该怎样调整摄像头，来获得全部的人工路标。

图4 人工路标的右半部分

综合以上考虑，得出如图5所示的人工路标结构模型。引入导引灯之后，将算法分成了两部分。相比于在复杂背景下搜索黑带，搜索导引灯的算法简单，而且速度要快得多，从而提高嵌入式DSP系统实时性。

图5 改进的人工路标

导引灯下方的部分是借鉴了郭阳所提出的新型人工路标模式。而对左侧的黑带做了一定的改进。3号黑带和4号黑带所确定的交比值，不同于1号黑带和2号黑带所确定的交比值。这样嵌入式DSP平台可根据检测到的交比值，来识别左右黑带，进而校准摄像头。

3 人工路标识别软件流程

人工路标识别系统的总体工作流程如图6所示。

图6 人工路标识别系统总体工作流程图

首先通过CCD摄像头获取图像，检测导引灯，然后利用交比不变性进行字符的初步定位，利用投影法进行字符分割，最后用主成分分析法(PCA)和最小距离分类器完成字符与人工路标的识别。

3.1 人工路标导引灯的识别与定位

人工路标的初步定位是利用导引灯作为导向。本文对各种算法进行了测试，并不断改进，最终获得了一个识别率与实时性都符合要求的算法，即基于灰度信息的识别算法。该算法不需要进行连通域标记，已经通过仿真器在DM6437评估模块上测试运行，并得到了良好的效果，满足实时性要求。

基于灰度信息的识别算法利用导引灯在形状和像素上的特点，即规则的圆形和较高的灰度值。这里，计算各个亮区的高度和宽度，作为初步判断依据。具体步骤如下:

(1)采集图像，并进行灰度变换及二值化(目标像素为255，背景为0);

(2)从左向右，逐行扫描图像，遇到目标像素则停止。如果它是导引灯的边缘，则肯定是圆面的最上端。于是，其正下方的若干个连续的目标像素应为圆面直径。这若干个像素中间的位置应为圆心，其左右也应该有若干个连续的目标像素，且其数目应与垂直的像素数接近。不满足以上任意条件，则肯定不是导引灯。因此，有以下各步。

(3)向下检测是否有连续的目标像素，并记录像素数和中间的位置及最下方像素的坐标。若像素数少于某一阈值，则认为此点不是导引灯的边缘，回到最初位置，继续检测。

(4)回到中间的位置，检测其左右是否有连续的目标像素，并记录像素数和左右两端的坐标。判断像素数是否大于阈值，同时与上一步的像素数比较，如果相差很大，则不是导引灯，回到最初的位置，继续检测。

(5)通过上下左右4个位置的坐标，可以确定一个接近正方形的区域，即导引灯的外接正方形。他与导引灯的面积之比应该在一定范围内。如果同样满足这一条件，即可确定这是导引灯，进而通知导引车向这个方向靠近。

系统找到目标，它会在导引灯的中心输出一个粉红色的方格，表示完成定位。硬件测试结果如图7所示。算法可实现视频的实时播放，速度满足嵌入式系统的要求。

图7 基于灰度信息的算法测试效果

3.2 人工路标数字的定位

找到导引灯之后，即完成了人工路标的初步定位，可通知嵌入式DSP平台将评估模块上的摄像头锁定在其下方的黑带和数字。此时还需精确分割数字所在的区域。这里利用交比不变性原理确定数字的边界，其程序的具体步骤如下:

(1)对导引灯下方的区域进行逐列扫描，找到黑带的边缘，记录纵坐标。边缘的确定是找黑白像素的交界处。

(2)计算交比值。如果接近预先设定的左侧黑带的交比值，则进行下一步;否则与右侧黑带的交比值比较，如果两个值接近，则通知导引车校准摄像头，否则返回(1)步。

(3)以左侧黑带最下方的纵坐标为界，对其下方的区域逐行扫描，找到黑带边缘，记录横坐标。

(4)计算交比值。如果接近预先设定的下方黑带的交比值，进行下一步。否则返回上一步。

(5)根据得到的横纵坐标确定数字的区域。假设得到的4个点坐标为(a，m)、(a，n)、(b，m)、(b，n)，其所确定的区域如图8所示。

图8 人工路标的精确定位原理图

该算法简单，计算量小，易实现，适合于嵌入式DSP系统。在CCS3.3集成开发环境中，利用C语言完成了上述算法编写，并成功编译。利用硬件仿真器XDS560将编译生成的.out文件，下载到DM6437评估模块，并运行测试。测试过程中，将0到9这十个数码每两个一组，打印在A4纸上，各人工路标如图9所示。测试结果如图10和图11所示。

图9 实验使用的人工路标

图10 正视定位效果图

图11 侧视定位效果图

图10是正视人工路标时得到的测试结果。从图中可以看到绿线确定的区域即人工路标中数字的区域，实现了良好的分割。而交比不变性原理的特点是即使摄像机在侧面观察人工路标，也能检测到黑带。于是让摄像头从侧面对人工路标进行拍摄，并做算法测试，结果如图11所示。由图可见，在侧面拍摄情况下，仍能对数字区域进行分割，且效果良好。

综上所述，利用交比不变性原理进行人工路标中数字的分割可以得到良好的效果，满足系统的要求。

3.3 人工路标数字的分割与调整大小

前面已得到人工路标中数字区域的坐标，现假设为(m，a)、(m，b)、(n，a)和(n，b)，如图12所示。由图可见，可通过计算横坐标m，n的中点，先将两个数字分割开来，划分出左右两个区域。然后，分别在这两个区域中利用投影法进行数字的精确分割。

图12 数字的分割

投影法的原理如图13所示。当对数字从侧面投影时，可以得到数字的高度及上下边界的坐标;对数字从上向下投影时，可以得到数字的宽度和左右边界坐标。这样，就得到了数字所在的区域，实现了更加精确的分割。其分割算法具体过程如下:

(1)根据得到的坐标，从分割区域的左上角按行扫描;

(2)若遇到目标像素，即0像素值的点，则高度值H加1;若H等于1，说明当前行是数字的上边界，记录当前的行数并赋给Row_U;

(3)重复(1)和(2)，如果遇到没有目标像素行，并且H不等于0;说明已经到数字的下边界。数字的下边界Row_D=Row_U+H。

(4)回到分割区域的左上角，按列扫描，按照以上方法可得数字的左右边界。这样就完成了数字的投影法分割。

图13 投影法原理

但是，由于拍摄角度和距离的不同，这样确定的区域并不总是具有相同的大小。而大小不一的图片对后面的识别是不利的。这里可以先说明，本设计中使用的训练样本的图片大小均为65×35像素，它要求采集的图片也应为65×35像素。因此，必须对图像的宽度和高度进行调整。采用的方法为线性插值方法，即从图像中均匀的去除多余的像素点或添加所需的像素点，使图像的高度和宽度满足要求。程序中，调整之后的图像灰度值保存在了一个的二维数组Fig_num［65］［35］中。通过CCS3.3开发环境下View-＞Graph-＞image读取数组Fig_num［65］［35］中的数据并显示出来。图14显示了除“1”之外的其他数码分割和调整大小的效果。数字“1”不需要进行调整大小，因为“1”具有一个明显区别于其他数码的特点，它的宽和高的比例非常小。因此，通过测试宽高比例就可判断是否为“1”。

图14 数字分割和调整大小效果图

3.4 人工路标数字的识别

完成对人工路标中数字的分割之后，就要对各个数字进行识别。本文考虑了嵌入式DSP环境下资源的限制及其对实时性的要求，决定使用基于主成分分析(PCA)［9-10］和最小距离分类器［11］的识别方法。其主要过程如下:

(1)对所要识别的路标(即数字)进行样本采集;

(2)对采集到的样本进行样本训练，得到训练样本的特征向量、均值向量与投影矩阵;

(3)使用均值向量与投影矩阵对测试样本(即DM6437评估模块上摄像头采集到的图像)进行降维;

(4)计算降维后的向量与特征向量的欧氏距离，最小距离对应的特征向量所表示的模式就是测试样本的模式。

主成分分析［9-10］主要用于数据降维。对于一系列样本的特征组成的多维向量，其内的某些元素本身没有区分性，比如某个元素在所有的例子中都为1，或者与1差距不大，那么这个元素本身就没有区分性，用它来做特征区分各个模式，贡献会非常小。所以，我们要找那些变化大的元素，即方差大的那些维，而去除掉那些变化不大的维。我们的做法就是求得一个的投影矩阵，这个投影矩阵可以将特征从高维降到低维。新的低维特征的每一维向量必须相互正交，即特征向量都是正交的。通过求样本矩阵的协方差矩阵，然后求出协方差矩阵的特征向量，这些特征向量就可以构成这个投影矩阵了。特征向量的选择取决于协方差矩阵的特征值的大小。

PCA的实现过程是先对样本进行训练，训练是在MATLAB下进行的，得到训练样本的均值向量和投影矩阵。硬件测试时，在DM6437评估模块上直接用训练得到的数据对测试图像数据进行降维。这里在MATLAB上的样本训练不作详细介绍。PCA降维过程如下:

(1)将目标图像表示成向量的数据形式Fig_ Vector;

(2)将Fig_Vector与训练样本均值向量进行做差，为PCA降维做准备;

(3)利用投影矩阵的转置左乘第2步得到的差，即得到降维后的测试样本特征向量。

PCA降维后，则利用最小距离分类器［11-12］进行数字识别。在考虑了硬件资源和实时性的情况下，决定采用最小距离分类器。最小距离分类器原理如图15所示。

图15 最小距离分类器

图15展示了最小距离分类器的判决方法，其中方块的各种形状表示训练样本，星形的形状表示测试样本。实线和虚线表示各测试样本与训练样本之间的距离，实线是最小距离。这种分类器简单直观，便于硬件实现。

本文没有利用欧氏距离的概念进行距离计算，而是用绝对值距离公式，其含义是:假如有N维向量V1(Xi)和V2(Yi)，则其绝对值距离为:

其中D表示距离。利用此距离公式，计算测试样本特征向量与各个训练样本特征向量的距离，找出其最小距离所对应的训练样本特征向量，该特征向量所对应的样本代表的信息就是测试图形的信息，至此就完成了对目标的识别。之后自动导引车或机器人便可根据位置和方向信息进行导航。

下面介绍其在DM6437评估模块上的实现过程。使用MATLAB对样本进行训练，得到了投影矩阵和训练样本特征向量和均值向量。将这3个数据分别以数组的形式定义在一个头文件里，等待系统检测到目标并完成分割之后，直接调用这些数据进行降维，计算距离并识别。

通过查阅DM6437评估模块的技术参考手册可知，它具有128 Mbyte DDR2 DRAM，无论程序是通过XDS560仿真器进行硬件仿真运行，还是从NAND Flash读入并运行，都会将所有数据和程序代码存储在DDR2 DRAM中。而通过计算，128 Mbyte DDR2 DRAM的内存绰绰有余。

为方便读者理解，将以上过程展示在图16中。

图16中，Vi是训练样本经过PCA降维之后的特征向量，即训练样本特征向量;Vt是测试样本通过投影矩阵降维后的特征向量，即测试样本特征向量。以上算法完成程序开发，并编译通过后，进行了硬件仿真。图17为DM6437评估模块上测试的情况。其中图(a)为左视情况下的识别效果，(b)图为正视情况下的识别效果，(c)图为右视情况下的识别效果。各图中右下角为识别结果。由图可见，该算法的识别效果良好。图中右下角显示的数字利用了DM6437的OSD(On Screen Display)图片叠加功能。

图17 数字识别效果

4 硬件测试结果与数据分析

为验证系统的性能，本文对整体算法进行了硬件测试，并统计其识别率。测试方案是在0.8 m和1.2 m两种距离下分别对正视、路标倾斜和斜视等7种情况进行测试，测试结果如表1和表2所示。

表1 识别率统计表(0.8 m)

表2 识别率统计表(1.2 m)

表中，正视是指从正面拍摄人工路标;左侧视是指摄像头从左向右拍摄;右侧视是指摄像头从右向左拍摄;倾斜一是指路标左低右高，倾斜角度10°;倾斜二是指路标左高右低，倾斜角度10°。摄像头对每个数字在每个角度拍摄了20次，并记录识别结果，进而计算识别率。

计算0.8 m和1.2 m两种情况下总的识别率，分别是79.500%和80.357%。若将拍摄角度限制在20°以内，则两种情况下的识别率分别为94.700%和93.700%。因此，本文所设计的人工路标识别算法在一定角度和距离内可以达到很高的识别率。当然，也存在一定误差，分析其原因主要是在斜视的角度较大时，采集到的数字会发生形变，对数字区域分割也出现了误差，有时甚至将数码的一部分分割了出去，同时将黑带划入了数字区域。这也是系统有待改进的地方。

5 结论

本文以ICETEK-DM6437-B评估模块作为硬件开发平台，利用人工路标作为导引标识，实现了基于导引灯的人工路标识别算法。首先利用基于灰度信息识别算法完成对导引灯的识别与定位，满足了对实时性的要求，同时，利用交比不变原理进行数字的初步定位;然后利用投影法进行数字分割，以及主成分分析法(PCA)和最小距离分类器的模式识别方法对数字进行识别。本设计对人工路标识别算法在一定角度和距离内进行了大量的测试，通过分析测试结果，充分验证了本次设计思想的可行性。

［1］ 王先敏，曾庆化，熊智，等.视觉导航技术的发展及其研究分析［J］.信息与控制，2012，39(5):607-613.

［2］ 张伟.视觉导航关键技术及应用研究［J］.价值工程，2010:171.

［3］ 李光辉，蒋志坚.基于移动机器人定位和导航的人工路标设计［J］.北京建筑工程学院学报，2010，26(4):50-52.

［4］ Li Guanghui，Jiang Zhijian.An Artificial Landmark Design Based on Mobile Robot Localization and Navigation［J］.Fourth International Conference on Intelligent Computation Technology and Automation，2011(1):588-591.

［5］ 郭阳.基于新型人工路标的自主移动机器人单目视觉导航相关问题研究［D］.沈阳:东北大学，2006.

［6］ 瑞泰创新科技有限责任公司.ICETEK-DM6437-B实验手册［S］.北京:瑞泰创新科技有限责任公司，2011.

［7］ 李进明，林意.基于交比不变性的摄像机标定方法［J］.计算机工程与设计，2011，32(3):1126-1129.

［8］ Zhang G，He J，Yang X.Calibrating Camera Radial Distortion with Cross-Ratio Onvariability［J］.Optics and Laser Technology，2003 (35):457-461.

［9］ 朱艳伟.基于主成分分析的支持向量机划分地震相［D］.西安科技大学，2006.

［10］ Desale R P，Verma S V.Study and Analysis of PCA，DCT and DWT Based Image Fusion Techniques［C］//International Conference on Signal Processing Image Processing and Pattern Recognition，2013:66-69.

［11］桑农，张荣，张天序.一类改进的最小距离分类器的增量学习算法［J］.模式识别与人工智能，2007，20(3):358-364.

［12］段薇，马丽，路向阳.基于信息增益和最小距离分类的决策树改进算法［J］.科学技术与工程，2013，13(6):1643-1646，1652.

刘纪红(1969- )，女，辽宁省沈阳市东北大学，电子科学与技术研究所副教授，研究方向为智能信息处理等，liujihong@ise.neu.edu.cn;

张 璐(1989- )，女，汉族，辽宁省沈阳市东北大学，硕士，研究方向为智能信息处理，zhanglu890508@163.com。

Realization of Artificial Landmark Recognition Algorithm Based on DSP

LIU Jihong*，ZHANG Lu，ZHAO Dongsheng
(School of Information science and Engineering，Northeastern University，Shenyang 110819，China)

In view of the vision navigation technology of using artificial landmark as the guiding identification，one recognition algorithm of artificial landmark based on the guiding light was proposed.Firstly，the algorithm based on gray information is used to recognize and locate the guiding light in the landmark.Then，the algorithm based on invariance of cross-ratio realizes the localization to characters in the artificial landmark.At last，projection method is used to segment characters，meanwhile，both principal component analysis(PCA)method and minimum distance classifier are used to recognize the character.The algorithm is realized on the ICETEK-DM6437-B system board. The experiment shows the algorithm has high stability and meets the requirements of real-time well.

vision navigation;artificial landmark;invariance of cross-ratio;PCA;minimum distance classifier

10.3969/j.issn.1005－9490.2014.02.032

TP391

A

1005－9490(2014)02－0315－07

2013-06-03修改日期:2013-07-09

EEACC:6330