ISSN 
Research on Precise Location Based on Graphic Landmark Features
-
摘要: 定位系统是智能移动机器人中一项重要的基础性工作，精确定位对机器人的实时导航具有重要的意义。随着计算机图像处理技术的发展，基于图像的定位技术也在不断地进步。该文提出一种基于图形路标的精确定位算法。首先对采集图像进行数据压缩处理，去除图像中冗余的信息，减少计算量、提高运算效率；其次通过SIFT算法对不同尺度空间下的图像进行特征提取，使得不同背景下的图形路标依然能够匹配；最后通过三角定位法来实现移动机器人的精确定位。实验结果表明，该算法是移动机器人实现精确定位和自主导航的一种可行方法。Abstract: Position system is an important and foundational part of intelligent mobile robots, precise position is indispensable to real-time navigation of robots. With the development of computer image processing technology, image-based position technology is improving constantly. In this paper, we proposed a precise position algorithm based on pattern signpost. Firstly, the data of image is compressed to remove the redundant information, reduce the computational complexity, and improve the operation efficiency. Then we use scale invariant feature transform (SIFT) algorithm to extract the feature of image in different scale spaces. Finally we apply the triangular positioning method to achieve the precise positioning of moving robots. The experiment result proves that the proposed method is feasible for fast and accurate autonomous navigation of moving robots.
-
Keywords:
- computer vision /
- image recognition /
- mobile location /
- robustness /
- SIFT algorithm
-
随着科技发展日新月异，移动机器人的应用[1]也越来越广泛。精确定位一直是移动机器人实现自主导航的重要部分。机器人定位技术大致分为两种：1)基于航位推算法[2]的相对定位；机器人无需感知外界信息，通过统计自身位姿来推算位置信息。缺点是随着时间不断累积误差造成定位精度较低。2)绝对定位[3]，通过信号检测，确定周围环境，实现定位；如GPS定位[4]，超声定位[5]，电磁定位[6]，视觉定位[7]等定位方法。由于设备或算法自身的缺陷，精度和实时性不能达到机器人的要求。其中以GPS定位为例，该技术容易受到周围环境、信号误差、噪声等因素的影响，通过磁罗盘、光码盘等器具进行辅助定位时，代价较大，实现成本较高；电磁定位技术中，需要较多的辅助手段，使得环境因素较为重要，实现较为困难。
随着机器视觉的图像处理技术[8]的不断进步，图形路标定位算法的高速度、高精度的特点，能够将其顺利地应用到机器人定位系统[9]中。
提高图像匹配精度是能够实现精确定位的一个重要方法。SIFT算法在复杂的环境中能够较好地识别出图像特征，但传统的SIFT算法在特征提取过程中相对耗时较多。为了改进这一缺点，达到机器人的实时性要求，本文将SIFT算法与基于OTSU的自定义图像二值化算法[10-11]相结合，从而将SIFT算法更好地应用在机器人定位中。
本文主要研究基于图形路标特征的精确定位算法，通过结合二值化图像信息来减少SIFT特征提取时间，达到机器人定位的实时性要求。再运用三角定位法计算机器人的当前位置和位姿，进行全局定位。实验证明，基于图形路标特征的定位算法能较好的识别图形路标，并提供较为精确的位置信息。
1. 改进的SIFT算法
SIFT特征匹配算法是局部特征匹配算法[12]，当有较强的光照，旋转，遮挡等外界因素对图像造成影响时，通过SIFT特征进行图像匹配有着良好的实验效果和鲁棒性[13]。
针对图形路标识别定位的情况，路标与背景相差较大时，将图像二值化后，将图形路标进一步凸显，加强路标与背景的对比度，简化SIFT的计算量，提高计算效率。
算法步骤如下所示。
1.1 基于OTSU的自适应二值化预处理
OTSU算法是对图像进行二值化处理，能够较好的区分前景与后景图像。其基本思想是对图像中的灰度值进行分类，通过不断变换阈值，使得相同类内灰度值差异较小，不同类之间的灰度值差异较大。整个图像的均值为：
$$ u = {w_0}{u_0} + {w_1}{u_1} $$ (1) 建立目标函数：
$$ g(t) = {w_0}{(u{}_0 - u)^2} + {w_1}{(u{}_0 - u)^2} $$ (2) 式(2)所得即为类间方差表达式，取得区间内的最大值，达到最大值时，t即为二值化阈值。
经上述处理得到二值化图像后，进行滤波处理剔除噪声，得到建立尺度空间的初始图像。
1.2 生成SIFT特征描述子
1.2.1 尺度空间极值检测
尺度空间理论[14]的主要思想是对原始图像进行卷积运算，进而得到不同尺度的图像，如图 1所示。将这些图像按生成顺序进行排序，即为高斯差分尺度空间[15]。
1) 建立尺度空间
尺度空间定义为：
$$ L(x, y, \sigma ) = G(x, y, \sigma ) \times I(x, y) $$ (3) $$ G(x, y, \sigma ) = \frac{1}{{2\pi {\sigma ^2}}}{{\rm{e}}^{ - 1({x^2} + {y^2})/2{\sigma ^2}}} $$ (4) 式中，G为尺度可变高斯函数；x为尺度空间横坐标；y为尺度空间纵坐标；σ是尺度系数。当σ调小时，用于查看图像细节处的变化；反之，用于查看整幅图像的变化程度。
2) 高斯差分尺度空间极值提取
判断图像生成的各个空间中的像素点是否为局部极值，并记录极值点的位置和对应尺度，即金字塔的i阶和j层，如图 2所示。
1.2.2 精确定位特征点位置
从上述得到的二维空间局部极值是离散空间的极值，存在着较多误差。在不受关键点边缘响应的影响下，减少稳定性不好的特征点，进而提高运算效率和减小实验结果的误差。
利用高斯差分函数的泰勒展开式：
$$ D(X) = D + \frac{{\partial {D^{\rm{T}}}}}{{\partial X}}X + \frac{1}{2}{X^{\rm{T}}}\frac{{{\partial ^2}D}}{{\partial {X^2}}}X $$ (5) 式中，$X = {(x, y, \sigma )^{\rm{T}}}$，对D(X)求导等于0，可得
$$ \mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\frown$}} \over X} = - {\left( {\frac{{{\partial ^2}D}}{{\partial {X^2}}}} \right)^{ - 1}}\frac{{\partial D}}{{\partial X}} $$ (6) 将上式带入D(X)中可得：
$$ D(\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\frown$}} \over X} ) = D + \frac{1}{2}{\frac{{\partial D}}{{\partial X}}^{\rm{T}}}\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\frown$}} \over X} $$ (7) 由式(7)确定对比度；若对比度超过某个阈值，该特征点就保留下来；否则视为对比度低的关键点。
1.2.3 SIFT特征点描述子[10]
得到每幅图的特征点后，需要为每个特征点计算主方向。
建立梯度直方图：
$$ m(x,y) = \sqrt {\begin{array}{*{20}{l}} {{{(L(x + 1,y) - L(x - 1,y))}^2} + }\\ {{{(L(x,y + 1) - L(x,y - 1))}^2}} \end{array}} $$ (8) $$ \theta (x, y) = a\tan 2\left( {\frac{{(L(x, y + 1) - L(x, y - 1))}}{{(L(x + 1, y) - L(x - 1, y))}}} \right) $$ (9) 直方图以θ为x轴，每45°为一个区间，则0~360°之间分为8个区间。再通过高斯下降函数对其分配权重，该点分配权重与该点在尺度空间与特征点的距离成正比。
对图 3数据进行统计，并生成直方图，其直方图峰值所在方向为该特征点的主方向。
首先，旋转坐标轴指向特征点主方向，特征点具有旋转不变性。其次，对每个特征点建立一个特征描述子。将以特征点为中心的区域(除去包含特征点的行和列)等分为16个小的区域，并对每个区域计算主方向，其中以45°划分一个区间，由此产生一个向量，每个特征点存在一个16*8维向量，即为特征点的特征描述子。
1.3 特征向量匹配
由1.2得到带有SIFT特征描述子的特征点后，对路标和预处理得到的图像进行特征点匹配；通过计算两个特征点的欧氏距离来判断，欧式距离越小，则X, Y的相似度越高。
$$ D(x, y) = \left\| {X - Y} \right\| = \sqrt {\sum\limits_{i = 1}^n {{{({x_i} - {y_i})}^2}} } $$ (10) 1.4 定位算法
选取三角定位进行定位；当机器人运动到当前位置时，路标和机器人的位置如图 4所示。
1) 得到ΔRIJ中角I和角J的角度及边IJ的长度；
2) 通过路标的两点组合计算机器人当前的坐标。
初始化所有图形路标的位置信息和与虚线方向的夹角(小角度)。通过角度信息计算三角形的三个角的大小。机器人到达任务点位置，如图 5所示。以45°角为间隔收集周围的环境信息，找到路标时，通过摄像头偏转角度和图像中图标的像素点信息来计算机器人与图标之间的偏角，其公式如下：
$$ {\alpha _i} = {V_{{\rm{cam}}}} + \frac{{x_{{\rm{Fea}}}^i - {x_{{\rm{center}}}}}}{{{x_{{\rm{pic}}}}}} \times t $$ (11) 式中，$V_{{\rm{cam}}}$是摄像头水平转动的角度；t为采集图片宽度与偏移角度的比值。
$$ \begin{array}{l} \beta = {\alpha _1} - {V_I}\\ \gamma = {\alpha _2} + {V_J} \end{array} $$ (12) 由上可得边IJ的相邻两角的角度。
由坐标信息计算边IJ的长度；
$$ {L_{{\rm{IJ}}}} = \sqrt {{{({x_I} - {x_J})}^2} + {{({y_I} - {y_J})}^2}} $$ (13) 最后根据坐标变换，确定机器人的坐标。
由三角定位法，可得d和边RI的计算公式：
$$ d = {L_{{\rm{IJ}}}}\frac{{\sin \gamma \sin \beta }}{{\sin (\beta + \gamma )}} $$ (14) $$ {L_{{\rm{RI}}}} = \frac{d}{{\sin \beta }} = \frac{{\sin (\beta + \gamma )}}{{{L_{{\rm{IJ}}}}\sin \gamma }} $$ (15) 由图 4可得R点的全局坐标：
$$ \begin{array}{l} {x_R} = {x_I} - {L_{{\rm{RI}}}}\sin {\alpha _1}\\ {y_R} = {y_I} - {L_{{\rm{RI}}}}\cos {\alpha _1} \end{array} $$ (16) 实验中，特征点位置和夹角的测量误差均在可控范围之内。路标均匀分布在机器人周围，机器人不考虑不存在路标或无法识别路标的情况。
2. 实验过程
2.1 算法流程
实验步骤如图 6所示。
机器人是双轮差速移动平台，摄像机和激光雷达相结合的方式作为机器人的避障传感系统，通过单目视觉作为机器人的传感器系统。
首先进行二值化处理，图像处理结果如图 7。
对路标进行特征点提取。
用SIFT算法进行匹配，得到路标中心对应位置如图 8所示，即为匹配成功。图 9为改进的SIFT算法的特征匹配与标准SIFT算法效果对比图。
图像匹配结果对比如表 1所示。
表 1 匹配结果比较算法 标准SIFT算法 改进SIFT算法 图标特征点 103 79 匹配特征点数 76 66 匹配次数 20 20 平均误匹配 11 5 平均匹配率/% 86.4 92.4 平均计算时间/s 1.09 0.72 经过图像处理后的进行定位的二值图像如图 10所示，O为机器人对应天花板的位置；A、B分别为两个路标的中心点位置。
从数据库中提取相应的路标A，B的全局信息，包括A，B的全局坐标和AB连线与机器人初始方向的夹角。数据信息如表 2所示。
表 2 数据库中保存图标信息MODEL_ID A B C D E X Y A — 135 45 27 56 650 500 B 135 — 0 39 58 660 490 C 45 0 — 37 55 660 510 D 27 39 37 — 3 340 100 E 56 58 55 3 — 350 300 由三角定位法求出同一平面机器人中心和路标的位置关系，通过路标的坐标信息得到机器人的全局坐标。
2.2 实验结果分析
在不同的场景下进行测试，将机器人的起点固定，通过指令移动到达目标点后计算坐标。结果如表 3所示。
表 3 坐标结果比较cm 场景 计算坐标 实际坐标 误差 办公室 (262, 355) (270, 350) 9.4(max) (498, 405) (500, 400) 5.2(min) 走廊 (31, 982) (30, 1 000) 18.0(max) (5, 510) (0, 500) 11.2(min) 篮球场 (714, 235) (700, 230) 16.0(max) (493, 652) (500, 650) 7.3(min) 实际坐标由卷尺直接测量。实验证明，精确定位的结果与实际坐标的误差不超过20 cm。
3. 结束语
针对机器人定位效率不高、精度不足的问题，本文从改进的SIFT算法出发，提出了一种基于图形路标的精确定位算法，提高了机器人识别路标的效率和精度。初步实现了基于视觉的机器人实时定位算法，但仍然存在着以下不足：
1) 采用改进的SIFT算法进行图像特征的提取，在大多数情况下效果较好，但在进一步复杂的环境下进行特征提取时，如光照不足，背景特征较为复杂时，效果较差。
2) 该算法是在能够识别路标的情况下实现的，即实验中路标不存在无匹配的情况，背景图中不存在相似图像；同时，实验中有较多的路标来保证机器人行驶过程中能够有足够的路标去识别环境；当路标减少时，需要考虑更多情况。
-
表 1 匹配结果比较
算法 标准SIFT算法 改进SIFT算法 图标特征点 103 79 匹配特征点数 76 66 匹配次数 20 20 平均误匹配 11 5 平均匹配率/% 86.4 92.4 平均计算时间/s 1.09 0.72 
下载: 导出CSV
表 2 数据库中保存图标信息
MODEL_ID A B C D E X Y A — 135 45 27 56 650 500 B 135 — 0 39 58 660 490 C 45 0 — 37 55 660 510 D 27 39 37 — 3 340 100 E 56 58 55 3 — 350 300
下载: 导出CSV
表 3 坐标结果比较
cm 场景 计算坐标 实际坐标 误差 办公室 (262, 355) (270, 350) 9.4(max) (498, 405) (500, 400) 5.2(min) 走廊 (31, 982) (30, 1 000) 18.0(max) (5, 510) (0, 500) 11.2(min) 篮球场 (714, 235) (700, 230) 16.0(max) (493, 652) (500, 650) 7.3(min)
下载: 导出CSV
-
[1] 赵霞, 袁家政, 刘宏哲.基于视觉的目标定位技术的研究进展[J].计算机科学, 2016, 43(6):10-16. http://d.old.wanfangdata.com.cn/Periodical/jsjkx201606002 ZHAO Xia, YUAN Jia-zheng, LIU Hong-zhe. Advances in vision-based target location technology[J]. Computer Science, 2016, 43(6):10-16. http://d.old.wanfangdata.com.cn/Periodical/jsjkx201606002
[2] 冯子龙, 刘健, 刘开周. AUV自主导航行为推算算法的研究[J].机器人, 2005, 27(2):168-172. DOI: 10.3321/j.issn:1002-0446.2005.02.015 FENG Zi-long, LIU Jian, LIU Kai-zhou. Dead reckoning method for autonomous navigation of autonomous underwater vehicles[J]. Robot, 2005, 27(2):168-172. DOI: 10.3321/j.issn:1002-0446.2005.02.015
[3] 黄康, 何春生, 甄圣超, 等.基于区间分析的机器人绝对定位精度分析方法[J].中国机械工程, 2016, 27(11):1467-1473. DOI: 10.3969/j.issn.1004-132X.2016.11.009 HUANG Kang, HE Chun-sheng, ZHEN Sheng-chao, et al. An absolute positioning accuracy analysis method for robot based on interval analysis[J]. China Mechanical Engineering, 2016, 27(11):1467-1473. DOI: 10.3969/j.issn.1004-132X.2016.11.009
[4] 刘美生.全球定位系统及其应用综述(一)——导航定位技术发展的沿革[J].中国测量技术, 2006, 32(5):1-7. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=zgcsjs200605001 LIU Mei-sheng. Global positioning system and its application (1)-history of development for navigation and positioning technology[J]. China Measurement Technology, 2006, 32(5):1-7. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=zgcsjs200605001
[5] 孟勃, 曹蕾.基于Kinect的机器人辅助超声扫描系统研究[J].计算机工程与科学, 2016, 38(3):494-500. DOI: 10.3969/j.issn.1007-130X.2016.03.015 MENG Bo, CAO Le. Robot-assisted ultrasound scanning system based on Kinect[J]. Computer Engineering & Science, 2016, 38(3):494-500. DOI: 10.3969/j.issn.1007-130X.2016.03.015
[6] 李雪丽, 王毅.电磁定位系统中的定位算法研究[J].微计算机信息, 2009(7):298-299. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=Y741634 LI Xue-li, WANG Yi. The quaternion solution in the remote object position and orientation determining system[J]. Microcomputer Information, 2009(7):298-299. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=Y741634
[7] 朱莹莹, 谢明, 王德明, 等.基于天花板的移动机器人视觉定位方法的研究[J].现代电子技术, 2016, 39(23):129-132. http://d.old.wanfangdata.com.cn/Periodical/xddzjs201623032 ZHU Ying-ying, XIE Ming, WANG De-ming, et al. Research on ceiling-based visual location method of mobile robot[J]. Modern Electronics Technique, 2016, 39(23):129-132. http://d.old.wanfangdata.com.cn/Periodical/xddzjs201623032
[8] ALGAWDA M, BEIJI Z, MOHAMMED N. Yemeni mobile counterfeit detection system using support vector machines, fuzzy logic and image processing techniques[J]. Journal of Computational and Theoretical Nanoscience, 2016, 13(5):2965-2977. https://www.ingentaconnect.com/content/asp/jctn/2016/00000013/00000005/art00039;jsessionid=2sdl06quoi91u.x-ic-live-03
[9] KOTA I, RYOTA M. Feature descriptor encoding apparatus, feature descriptor encoding method, and program: US9239850[P/OL]. (2011-11-18). https://patents.google.com/patent/US9239850.
[10] DAVID G L. Object Recognition from local scale- invariant features[C]//The 7th International Conference on Computer Vision. Kerkyra: IEEE Computer Society, 1999: 1150-1157.
[11] GUO H T, WANG L Y, TIAN T, et al. Automatic thresholding using the Otsu algorithm based on the two-dimensional bound histogram[J]. Journal of Optoelectronics Laser, 2005, 16(6):739-742. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=gdzjg200506026
[12] BETKE M, GURVITS L. Mobile robot localization using landmarks[J]. IEEE Tran Robot Automat, 1997, 13(2):251-263; http://d.old.wanfangdata.com.cn/Periodical/zjdxxb-e200606002
[13] 林陶, 黄国荣, 郝顺义, 等.尺度不变特征转换算法在图像特征提取中的应用研究[J].计算机应用, 2016, 36(6):1688-1691, 1698. http://cdmd.cnki.com.cn/Article/CDMD-10456-1016138817.htm LIN Tao, HUANG Guo-rong, HAO Shun-yi, et al. Application of scale-invariant feature transform algorithm in image feature extraction[J]. Journal of Computer Applications, 2016, 36(6):1688-1691, 1698. http://cdmd.cnki.com.cn/Article/CDMD-10456-1016138817.htm
[14] BABAUD J, WITKIN A P, BAUDIN M, et al. Uniqueness of the gaussian kernel for scale-space filtering[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1986, 8(1):26-33. DOI: 10.1109-TPAMI.1986.4767749/
[15] SPORRING J, NIELSEN M, FLORACK L, et al. Gaussian scale-space theory[M].[S.l.]:Springer, 1997.
-
期刊类型引用(4)
1. 关展旭，刘俊，潘春茹，李松五，高书礼，李波. 图像识别在发动机加工装配过程中的应用研究. 内燃机与配件. 2022(07): 22-24 . 
百度学术
2. 邓朝阳，陆静平，苏文桂，肖威. 基于虚拟标志的移动机器人导航方法. 装备制造技术. 2022(01): 60-63+94 . 百度学术
3. 黄旭，张世义，李军. 图像分割技术研究综述. 装备机械. 2021(02): 6-9 . 百度学术
4. 陈成，钱东海，赵伟，刘洋，孙林林. 基于人工路标的AGV识别与定位技术研究. 自动化与仪表. 2020(10): 73-77+91 . 百度学术
其他类型引用(16)
计量
- 文章访问数:
- HTML全文浏览量:
- PDF下载量:
- 被引次数: 20