第  卷第  期  年  月 计 算 机 应 用 研 究 0 0 551$10 *&"&$3 0(045#&" &5% 基于极线约束的 61特征匹配算法 秦晓飞 皮军强 李峰   上海理工大学 光电信息与计算机工程学院 上海  摘要 图像匹配是机器视觉领域的基础核心课题针对当前 A*, 01& &' .$ ' 0$&' ,*:C 图像特征 匹配算法虽然执行速度快但是匹配质量不高的问题提出一种通过极线约束来改进 A*,匹配的算法 通过合 理设计 $441 2阈值大小来提高初始匹配点数量采用 *( $ '04"$45&0 "& "#" 和  点改进法计算 基本矩阵应用极线约束剔除误匹配保留大量优质匹配点 仿真实验结果证明算法改进后的优质匹配点数量 可达原始算法的   倍同时极大地提高了匹配点的质量证明了算法的有效性 关键词 特征匹配 阈值 *(  点改进算法 基本矩阵 极线约束 中图分类号 ./文献标志码 文章编号  '01% %1"" %%%% A*,&$#&4$31 2-$"&' 0 &5150$0 "$1  1 61$0&1 /19# 1$ 2 B1& 2   -2-3--"21 $% &--"-&     :4$2&4$31 21"3&0&03&1&' 04$31 &1"10 %''&""1 23&50-&4 3$3&&1"1 2A*,&$#& 4$31 2$201341"$"-#00!4$31 2#$1; 31"5$5&5050"&' $ 1450&' &"10 03&A*,$20134014 501 24$31 2$#$;#3&-;& 01 23&&5150$0 "$1 %,;&$"0 $-;'&"12 1 23&$441 23&"30' 02& $$2&00121 $4$31 2501 "$ ' #"1 2*($ ' 501 1450&' $2013402&# '$4& $4$1 3&$20134 1450&' 3& #4-&04$31 2501 "%@"1 2&5150$0 "$1 0&141 $&3&!0 24$3 1!$"$-&0&$1 $$2& #4-&03123 #$1;4$31 2501 "%C5&14& &"#""30!3$3&5050"&' $20134$ 1 &$"&3& #4-&04$ 31 2501 "0  14&"03&0121 $$20134$ ' 2&$;1450&3&#$1;04$31 2501 " !313 50&"3&&& 1& &""03&$20134%   &$#&4$31 2 3&"30' *( 501 1450&' $20134 # '$4& $4$1 &5150$0 "$1  引言 图像特征匹配是指寻找两幅图像之间对应于同一三维点 的两个二维像素点这两个点具有相同或者相似的某种性质 通过一定算法将两个点的性质进行正确配对的过程 图像特  目标跟 征匹配算法是机器视觉研究的热点 在人脸识别  踪   中起 着至关重要的作用它是后续算法能继续开展的基础 三维重建  和 B) 缺陷检测  图像拼接   目前图像特征匹配算法有多种最早由 )0$&于  年提出角点检测算子通过计算水平垂直正反对角线的灰度 方差来获取角点响应值后来由 $1"等人  经过改进采用微 分思想和高斯窗口函数等提出 $1"角点检测算子 B0!& 提出著名的尺度不变特征变换的 :. "$&1 $1$ &$#& $ "04 匹配算法并于  年完善 该算法对旋转缩放 亮度等保持不变对视角变换仿射变换噪声污染也有很强的 稳定性由 于 其 精 度 高 匹 配 量 大 一 直 作 为 主 流 算 法 在  年,$;等人  参照 :.算法在执行效率上进行改进 提出 @* "5&&'&'#5 0-#"&$#&" 算法在保留其优良的 特性的基础上解决其计算复杂度高和耗时长的缺点 随着机 器视觉技术的不断发展对图像特征匹配的实时性要求越来越 高*#-&&等人  提出 A*,算法 该算法是一种新的角点检 测与特征描述算法是 .角点检测与 ,*:C特征描述的改 进结合具有匹配速度快质量高的优点 随着研究的不断推 进一些经典算法被不断完善刘佳等人  提出对图像进行小 波变换和采用回字形邻域方法来改进 :.使其匹配精度和匹 配时间上得到提高李红波等人  提出在 @*算法检测阶 段构建高斯金字塔图层在匹配阶段使用 E&&索引能有效 减少匹配时 间 和 匹 配 误 差 任 克 强 等 人  将 彩 色 信 息 融 入 @*算子使其有效地提高算子对彩色图像的敏感度 大量 研究表明采用 A*,进行图像特征匹配在时间上比 :.快两 个数量级比 @*快一个数量级 但是原始的 A*,算法依 然存在以下不足 $ 采用汉明距离筛选匹配点速度快但是由于考虑的信 息少在阈值高的时候误匹配点数很多在阈值低的时候匹配 点数很少 - A*,不具备尺度不变性 对于 A*,尺度不变性问题许宏科等人  采用混合算法 提出 :*,解决而对于问题 $ 目前依然没有提出切实有效 的方法 本文针对问题 $ 引入极线约束进行改进  在保 留 A*,算法快速性的特点的同时获取大量优质匹配时间代 价小方法简单稳定 传统 61算法 传统 A*,算法采用 .进行特征提取使用 ,*:C作 为特征描述子特征之间利用 $441 2距离进行匹配筛选 4(特征提取 .是 由 *0"& 等 人 于  年 发 表 的 论 文  &$#&" 04$&&$&' "&24& &" 中提出的 算法的核心思想是利 收稿日期   修回日期 基金项目 上海高校青年教师培训计划资助项目 88"  作者简介秦晓飞  男河北石家庄人高级工程师工学博士主要研究方向为机器视觉智能控制皮军强   男硕士研究生 主要研究方向为机器视觉图像处理李峰  男 通信作者 讲师工学博士主要研究方向为机器人 1& 220'%04 % 

   计 算 机 应 用 研 究  第  卷 用特征点周围的像素灰度进行比较简单有效 算法实现步骤 如下 $ 在检测的目标像素 4周围以检测点为中心画半径为  个像素的圆圆周经过  个像素块 对像素块进行编号以正 上方为  顺时针方向编号    - 定义一个阈值 采用快速筛选的方法先检测   两 个像素与中心像素 4的灰度差若偏差的绝对值小于 则判 定该检测点为非特征点否则进行下一步判定  满足条件 - 计算     的灰度值与中心灰度值之 差如果满足灰度值差的绝对值大于 的少于  个点则判定 该点为非特征点否则进行下一步判定 ' 满足条件  计算   个编号像素与中心像素的偏 差若偏差满足大于 4像素灰度且个数大于 个则判定 4为 特征点否则为非特征点 & 得到特征点后采用非极大值抑制的方法增强其鲁棒 性 计算以 4为中心的  个像素点的得分值 +若在 4的  =  或者  = 的邻域内 4的分值最高即特征点响应最大那就 保留 4为特征点抑制邻域内的其他特征点 如果邻域内除 了 4外无其他特征点则直接保留 4为特征点 得分计算公 式  为编号像素灰度值2为中心点像素灰度值 为   取 的第一列置于新矩阵 计算下一列向量与 中 所有列向量的相关系数若满足相关系数小于规定阈值则放 入 中 ' 重复执行直到 中向量数为  个 $,,% *距离匹配 汉明距离是一个概念表示的是相同长度的数码对应位 不相同的位的数量常用于二进制比较中 对比较后获得的汉 明距离设置一个恰当的阈值即可筛选出正确的匹配对 该方 法简单可用异或操作计算速度很快 采用极线约束的 61匹配算法 算法总体框架 对于原始 A*,算法存在特征匹配点数量和质量不高的问 题本文提出一种极线约束的特征匹配方法对其性能进行改 进 算法流程如图  所示 $ 采用 A*,算法检测并描述两幅图像特征点 - 对得到的特征点选择最优阈值进行 $441 2匹配将 匹配点集记为粗略匹配点集  在粗略匹配点集上使用 *(和  点改进算法计算 { +4$    <2   <2 >     2<   2<  >    基本矩阵 并剔除部分点    ' 对剩余点集应用极线约束剔除误匹配点得到大量优 根据 取值不同.可分为 . . . 和 .  #1特征描述 ,*:C是  年 由 ($0 '&等 人 发 表 的 一 篇 名 为  ,*:C-1 $;0-#"1 '&5& '& &&4& $;&$#&" 的论文中 提出的 ,*:C用于特征点描述通过一种简单的二进制编码 的描述子来大大加速特征点的描述过程比采用灰度直方图或 者梯度描述的传统描述方法快了几个数量级是一种潜力巨大 的特征点描述算法 算法实现步骤如下 $ 先对 需 要 处 理 的 图 像 进 行 高 斯 滤 波 减 少 图 像 噪 声 干扰 - 以特征点为中心取大小为  = 的邻域在邻域内以 一定的随机算法选取一对  = 的子窗口 和 &求出各子窗口 的灰度和进行比较得到响应值 为  {  03&!1"&  1 2  ?2 &    2&      重复在邻域中选取子窗口对进行比较将得到的所有 响应值采用二进制编码这个编码即为 ,*:C描述子当描述 子长度为  时停止比较得到长度为  的二进制描述子 由于在比较时区域灰度和可以采用积分图来完成所以算 法运行非常快 A*,算法主要解决的是 ,*:C算法没有旋转不变性的问 题 在计算 ,*:C描述子的时候先对邻域灰度求质心定义 一个 4的邻域像素矩  5 质匹配点 算法详细步骤 采用 A*,进行特征匹配中阈值 对最终匹配结果影响 很大取值过大则保留的错误匹配点过多后续工作误差过 大取值过小则剩余匹配点数目过少不利于后续图像处理 因此设计一个合理的阈值是图像特征匹配的关键一步 本文根据 $441 2距离的定义对于任意一个阈值 所 定义一 与最小距离 7 4$ 41 得到的匹配结果中求得最大距离 7 个比例系数 0和正确率 2为 0 7 <7     4$ 41  #& 2     $  和其中的正确匹配数   通过实验采用控制变量法改变系数 0的值统计匹配点总 数   将统计结果绘制折线图 并分析确定最佳系数 0 采用该系数重新进行 $441 2筛选 将所获得的匹配点记为粗略匹配点进行极线约束 #& $ 极线约束属于对极几何  &5150$2&04&; 范畴 如图  所示/点为空间一三维点该点在两台摄像机成像平面位置 与 /共同构成一 为   个极平面该平面与两成像面交线为极线 其中点 2的极线 为   极线与两摄像机中心连线的交点为极 点  点 8的极线为  和   基本矩阵 # '$4& $4$1 约束方程为 为相机中心于是有  和           其中为基本矩阵反映了图像对应点之间的约束关系 .          &  &    其中 & 即为点 & 处的灰度值 于是本文可以求得当 前邻域质心坐标为 5 &                    将当前点 4与质心的连线作为特征点的方向 将坐标轴 旋转使 轴位于该方向取点此时所获得的二进制描述子就 具备了旋转不变性称为 ,*:C 由于旋转导致描述子区分度 减少采用统计学方法重新选择点对集合实现方法如下 $ 选 取  D 个 特 征 点 集 按 照 6 种 方 法 取 点 得 到 图 本文算法流程  图 极线与匹配像素点关系  D =6的矩阵  - 对矩阵 每列求均值按照与 % 距离的大小对矩阵 列重排序重排后的矩阵记为  基本矩阵将一个平面的二维坐标映射到另一个平面对应 点上已知其中一个点 的齐次坐标  &  可以得到它在 另一个平面的搜索域即极线 

第  期 秦晓飞等基于极线约束的 A*,特征匹配算法                !                   &    因此得到这样一个关系如果两点为匹配点则必定满足 ! ( &(        其中 (&(  为 &  点对应的匹配点 由于极线函数只 是单纯考虑图像点和极限函数的几何距离对于三维空间点信 息并未充分利用 因此这里采用一种更加准确的几何距离直 接计算三维点在图像内投影 具体步骤如下 $ 使用改进  点法和 *(估计基本矩阵 通过排除 外点求得含有最多内点的点集再用该点集重新计算基本矩 阵  - 采用定义在基本矩阵约束方程上的一次几何距离近似 的 $45"0 距离定义代价函数 有误匹配而图像复杂度增加给匹配带来困难只有在 为  的情况下才能保证误匹配的最大减少 所以取   %%匹配数目比较 随机选取  组不同环境的图像对按照图形复杂程度由 小到大对图像编组 分别比较原始 A*,算法和改进 A*,算 法的匹配数量结果列在表  中 表 原始 A*,算法和本文改进算法匹配质量比较 A*, 改进 A*, 正确匹配集数目 正确匹配集数目 *(剔除数目 极线剔除数目 组 别                                    7         .  .                     .               由表  可知改进 A*,算法所匹配的结果明显高于原始 A*,算法是原始 A*,算法的   倍在图像简单的  组中 甚至达到  倍而即使图像复杂的  组也有 % 倍 在对 图像处理求基本矩阵时 *(也能剔除一部分外点从表 后两列可以看出处理简单图像时 *(剔除效果较好有 效地剔除了大量外点而图像复杂时极线约束起到主要作用 图  是采用两种匹配的结果图其中  $ 为原始 A*,算 法 - 为本文改进的 A*,算法正确匹配点都用圆进行标 注并将匹配点用不同颜色的线连接 从图中可明显看出采 用改进 A*,算法能有效地增加正确匹配点获取的数目提高 匹配质量 其中 表示取向量的第 0个元素 0  考虑到实际计算中的误差定义阈值 当 7 小于  时保留该匹配点否则剔除该匹配点 将所有点计算后得到最 优匹配集 实验结果分析 结果分析 实验采用的操作系统为 71 '0!"  位: &  .) (0& 1  (/@ % +  +,内 存 笔 记 本 电 脑 运 行 环 境 为 1"#$#'10 和 ).B,* - 双平台 将待匹配图像进行随机分组实验0取值为 % %  观 察折线趋势确定 0的值 0值确定的目标是保证在获取匹配 点数较多的情况下能最大化正确匹配率 实验中对九组  张 不同场景的图片进行匹配图  为 0值变化曲线 从图  可看出随着系数 0的不断增加匹配结果 2当 0 在   改变很小普遍在 *以上0在   下降 趋势开始明显0在  之后迅速降低因此取 0 作为最 优值 取测试组  进行阈值测试结果在图中用虚线表示测 试组结果表示当 0取 % 时正确率高达 %满足要求 为确定极线约束代价函数阈值 求出 后对所有组图 图 原始 A*,算法与本文改进 A*,算法匹配效果对比 像特征匹配内点代入代价函数进行测试结果如图  所示 %%运行时间比较 从图  可以看出误匹配点对应代价函数值比较大而正 确匹配点代价函数很小由于误差原因不可能完全为   大 部分正确匹配点位于距离  内在  附近优质匹配非常多 为了更精确地确定阈值 随机取七组图片按照由简单图像 到复杂图像排列分别取 7 为    进行实验验证将结果列 在表  中 图像特征匹配算法的好坏判断标准中算法执行的速度和 匹配的质量同样重要实验中随机抽取九组图像对它们匹配 执行时间进行记录分别比较了原始 A*,算法改进 A*,算 法和 @*算法的执行时间结果如表  所示 表 A*,原始算法与本文改进算法同 @*算法运行时间比较 4" 组别 原始 A*, 改进 A*, @*                                         图 不同图像组的 0与 2的关系 图 各匹配点代价函数值 表 不同阈值误匹配数目比较 组别 误匹配数目 组别 误匹配数目                                        平均值 % %  % 从表  中可以看出原始 A*,算法运行时间最短速度最 快改进 A*,算法运行时间大约为原始 A*,算法的一倍而 @*算法运行时间最长大约为改进 A*,算法消耗时间的  倍比 A*,算法时间消耗上高了一个数量级 经过分析指 出改进 A*,时间消耗很小 匹配数目却非常多 采用 改 进 A*,算法对后续图像计算分析以及实时计算都非常有利 %%算法鲁棒性分析 由表  可以看出对于简单的图像在 值为  时几乎没 鲁棒性是衡量匹配算法的重要指标之一是算法在干扰下 

   计 算 机 应 用 研 究  第  卷 能稳定计算匹配结果的性能特征 因此对算法的鲁棒性分析 很有必要 本文分别从以下四个方面分析所提出的改进 A*, 算法的抗干扰能力 $ 针对光照变化选取六组不同场合明暗图片进行两两 匹配测试按照变化由弱到强排序结果如表  所示 表 不同光照强度图片匹配数目比较 组别 正确匹配数 总匹配数 正确率                 %    %    % 从表  中可看出随着光照变化加大匹配正确率先保持 不变后慢慢下降原因是光照变化导致匹配算法在描述子形成 过程中同一个点的差异增大超过了可接收阈值导致误匹配 光照变化增大匹配数量减少是因为光照变化使原来纹理清晰 的图像由于暗光导致模糊失去匹配点或亮光导致图像过度曝 光丢失细节 - 针对图像旋转匹配选取六组随机图片进行两两配对 按照旋转角度 内由小到大进行测试结果如表  所示 表 不同旋转角度图片匹配数目比较 组别 正确匹配数 总匹配数 正确率                      图 改进 A*,三维重建结果 对于物体轮廓简单的图像改进 A*,算法能提取大量正 确匹配点进行后续计算使得重建效果非常好而对于场景复 杂的图像算法也能保证提取出足够多的点证明了改进 A*, 算法的实用性和稳定性 结束语 本文将 A*,算法与极线约束相结合通过 $441 2阈值 的恰当选取和极线约束代价函数阈值的动态优化消除了直接 比较二进制描述子方法中难以消除的误匹配且对不同光照 旋转噪声的图像都能达到较好的匹配效果具有一定的鲁棒 性 该方法实现了在减少特征点误匹配数量的同时极大地提 高正确匹配特征点的数量 文中选取不同场景的物体对匹配 方法进行了测试实验结果证明了改进方法的有效性 实验过 程同时也发现A*,算法对于纹理较少的区域敏感程度很低 提取的特征点大多在富含纹理的图案上对于弱纹理场合匹配 效果较差这也是下一步需要研究的方向 参考文献    -$& $551) *110E E$ ' E$&&02 110      $"#&; 9 %0$!!"# 1"&* %!%& "!!"#.        从表  中可以看出旋转对于本文提出的算法没有影响 六组匹配结果都完全正确无误匹配且数目较多  针对仿射变换采用六组不同角度拍摄的相同物体图 片进行匹配测试按角度变化由小到大将结果列于表   表 不同角度拍摄图片匹配数目比较 组别 正确匹配数 总匹配数 正确率  %    赵欣 陈峰 吴立知%一种改进的 )&$ 31运动目标跟踪算法  9 %通信技术      %    孙雪晨 姜肖楠 傅瑶 等%基于机器视觉的凸轮轴表面缺陷检 测系统 9 %红外与激光工程      %    # 83$01$ 7$ 2B141 2%A5141&' '&"12 0$#04$114$2&40 "$1 9 %'!%,"%$(&&'. $ 4--'%$!%& .          %    % %    %    83$ 2.1$  B1# 91$ 3#$ B1# 3$01  E &0 "#10     4&30' 0515&1 &1 "5&10 -$"&' 0 4#11"10  9 %"$.#"    % ," !   7 %     从表  看出改进算法不具备仿射变换不变性 在小角度 仿射变换时由于图片变化较小检测精度得以保证随着角度 增加大量匹配点无法对应匹配效果直线下降这也是由于 A*,不具备尺度不变性所导致的 可以结合许宏科等人的混 合算法 :*,改进仿射抗性 ' 针对图像噪声设计实验选取六组随机图片对其加入 噪声本文采 用 高 斯 噪 声 按 照 图 片 所 含 噪 声 比 率 由    等间隔分组将结果列于表  中    艾青林 余杰 胡克用 等%基于 A*,关键帧匹配算法的机器人 B)实现 9 %机电工程      %    $1"( + &53& ") 9% 04-1 &' 0 &$ ' &'2&'&&0  ( /003&3 &;1"10 (0 && &%  %    B0!&E+%E1"1 1&14$2&&$#&"04 "$&1 $1$ D&;501 "  9 % !"# $!%& $'&# $'&&,-!"#%.%&        %    ,$; C"" .#;&$$.  5&&'&'#5 0-#"&$#&  @*  9 % &,-!"#%.%& $  ,$*" 8 "#.!$ % * 表 不同噪声比率图片匹配数目比较       % 组别 正确匹配数 总匹配数 正确率     *#-&&C *$-$#'  0 012& A*, $ &11& $& $ 1&0:.0@* ( /00:CCC: & $10 $(0 && &                         从表  可以看出高斯噪声对本文提出的改进 A*,匹配 算法没有影响 改进 A*,匹配算法对噪声抗干扰性比较强 算法应用效果 将改进的 A*,算法应用在 )的 E重建中获得良好的 效果 图像采用不同视角拍摄的七幅图像序列进行点云重建 图   $   为原始图片 -  ' 为点云截图 0 (045#&1"10 %B0"$410" :CCC (045#&01&;/&""   %    刘佳 傅卫平 王雯 等%基于改进 :.算法的图像特征匹配  9 %仪器仪表学报      %    李红波 赵永耀 吴渝 等%一种基于距离约束的改进 @*算 法 9 %系统仿真学报        %    任克强 胡梦云%基于改进 @*算子的彩色图像配准算法 9 % 电子测量与仪器学报       %    许宏科 秦严严 陈 会 茹%基 于 改 进 A*,的 图 像 特 征 点 匹 配  9 %科学技术与工程       %    陈洁 高志强 密保秀 等%引入极线约束的 @*特征匹配算 法 9 %中国图象图形学报      %