（通信与信息系统专业论文）图像角点检测和匹配算法的研究.pdf

摘要 摘要 本文主要研究基于灰度图像的角点检测算法和图像的匹配算法。角点的信息 含量很高，可以对视觉处理提供足够的约束，极大地提高运算速度，在图像之f 叫 进行可靠的匹配。这些特点使得角点检测在机器视觉和图像处理的许多方面都起 着卜分重要的作用。本文首先介绍了一些经典的自相关角点检测算法并分析了各 算法的优缺点，并在最小亮度变化算法( m i c ) 的基础f = 提出了改进的m i c 角点提 取方法。实验结果证明浚方法比改进前的m i c 算法具有更好的效果。 计算机视觉和图像处理中另一个重要的研究内容是图像的匹配。它是许多计 算机视觉应用的基础。本文对图像匹配算法进行了分类和比较，并详细介绍了一 些经典的图像匹配方法，同时给出算法的匹配结果。 关键词：计算机视觉角点最小亮度变化( m i c ) 图像匹配 a b s t r a c t a b s t r a c t f e c h n i q u e s o nc o r n e rp o i n t sd e t e c t jo nb a s e dn n g r a y 一 e v e l im a g ea n d i m a g em a t c h i n gm e t h u da r ep r e s e n t e di nt h i st h e s i s c o r n e r sa r ei m a g ep o i n t st h a ts h o wa s t r o n gi n t e n s i t yc h a n g e t h e d e t e c t i o no fc o r n e rp o i n t si nj m a g e si se s s e n t i a lf o rm a n yt a s k ss u c ha s m a c h i m ev is i o r i m a g ep r o c e s s i n g t h er e a s o nt h a tt h i s a p p r o a c h i ss o p o p u l a rt h a tc o r n e rp o i n t sh a v ear i c hc o n t e n to fi n f o r m a t i o r ，p r o v i d ea s u f f i c i e n tc o n s t r a i n tt ov i g i o np r o c e s s i n ga n dar e j a b lem a t c hb e t w e e n i m a g e s ，h a v e a g r e a t l yi m p r o v e m e n t o n c o m p u t a t i o ns p e e d i h i s t h e s i s d e s c r i b e ss o m e p r e y i o u sa l g o r i t h m s o na u t o c o r r e l a t i o nc o r n e r p o i n t s d e t e c t i o n t h e nt h ep e r f o r m a n c ea n a l y s i so ft h e s ea l g o r i t h m sa r eg i y e n a nj m p r o v e da p p r o a c hi sp r e s e n t e djnt h i sp a p e ro nt h eb a s i so fm i c ( m i n i m u m i n t e l l s i t yc h a n g e ) a l g o r i t h m e x p e r i m e n t a lr e s u 】t ss h o wt h a t t h ep r o p o s e d a l g e r it h mh a sab e t t e rp e r f o r m a n c et h a nt h eo r i g i n a l o n e i m a g em a t c h i n g i sa n o t h e ri m p o r t a n tc o n t e n to fc o m p u t e rv is i o na n d i m a g ep r o c e s s i n g j th a sb e e na p p i i e dt om a n yc o m p u t e rv i s i o nt a s k s t h i s t h e sfsh a sm a d eac o m p a r i s o na n d1is to fm a n y i m a g em a t c h i n ga l g o r it h m s a n djn t r o d u c e ds o m ec l a s s i ci m a g em a t c h i n gm e t h o d si n ad o t a l1 fjn a ll y t h er e s u t so f i m a g em a t c h i n ga r eg i v e n i naf o r mo f e x p e r i m e n t s k e y w o r d s ：c o m p u t e r v i s i o nc o m e r p o i n ti m a g em a t c h i n g m i n i m u m i n t e n s i t yc h a n g e ( m i c ) ? 6 9 5 8 4 0 创新性声明 本人声明所里交的论文是我个人在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文c t ： 不包含其它人己经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任何 贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名日期：兰! ：! ：兰! 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布沦文f 门令 部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。( 保密的 论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 日期： 2 口口j 、2 、乞乙 日期：主竺! ! ，皇墨 第一章绪论 第一章绪论 1 1 计算机视觉概述 人类正在进入信息时代，计算机将越来越广泛的进入几乎所有的领域。一方 面是更多未经计算机专业训练的人需要应用计算机，而另方面是计算机的功能 越来越强，使用方法越来越复杂。这就使人在进行交谈和通讯时的灵活性与目前 使用计算机时所要求严格和死板之间产生了失锐的矛盾。为了使更多的人能够使 用复杂的计算机，必须改变过去那种让人来适应计算机，来死记硬背计算机使用 规则的情况。而是反过来让计算机来适应人的习惯和要求，以人所习惯的方式与 人进行信息交换，也就是让计算机具有视觉、听觉和说话的能力。 计算机视觉是人类视觉的模拟。现实世界中的物体都是三维的，而人眼所获 得的景物图像都是二维的。但是人类的视觉系统能从二维图像中感受三维世界， 获得三维信息。信息处理理论与计算机出现以后，人们用摄像机获耿环境图像并 转换成数字信号，用计算机通过数字图像处理的方法模拟人类对视觉信息处理的 全过程，这样，就形成了一门新兴的学科一计算机视觉( c o m p u t e rv i s i o n ，c v ) 。 作为人类视觉模拟的计算机视觉是利用计算机从二维图像中提取景物的二维或者 i 维结构和属性的描述加以理解。 计算机视觉，四十多年的发展至今仍然没有统一的理论。计算机视觉的研究 丌始于5 0 年代中期，当时的研究重要集中在二维景物图像的分析。利用二维图像 解释三维目标和景物的研究开始于1 9 6 5 年r o b e , s 刘多面体识别中提出“积木世 界的概念”。在这之后，随着研究的深入，计算机视觉的各种理论框架相继被提出。 其中，从7 0 年代中期到8 0 年代初期，m a r r 教授通过在美国麻省理工学院进行的 视觉理论方面的研究，提出了第一个计算机视觉领域的理论框架一计算机视觉理 论。这一理论把视觉过程看作一个信息处理的过程，并提出对于信息处理过程的 研究应该分为三个不同的层次，即计算理论层次，表达与算法层次，硬件实现层 次。这一理论强调视觉的目的是从图像中建立物体形状和位置的描述，把视觉过 程主要规定为从二维图像信息中定量地恢复出图像所反映场景中的三维物体的形 状和空间位置，即3 d 重建( r e c o n s t r u c t i o n ) 。m a r t 将这一重建过程分为三个阶段： ( 1 ) 要素图：它包含图像边缘亮度变化率，边缘的几何特征，或者纹理元的排列、 描述等：( 2 ) 2 5 维图：它是要素图和三维图像模型之问的中间表示层次，包含物 体表面的局部内在特征；f 3 ) z 维图：以物体为中心的三维描述，它是由要素罔和 削像角点检测雨l 匹配算法的研究 2 5 维图得到的。m a r r 视觉计算理论立足于计算机科学，系统地概括了心理 生理学、神经生理学等方面已耿得的所有重要成果，是视觉研究中迄今为j h 最为 完善的视觉理论。m a r r 建立的视觉训。算理论，使训算机视觉研究有了一个比较明 确的体系，大大推动了计算机视觉研究的发展。人们普遍认为，计算机视觉这门 科学的形成与m a w 的视觉理论有着密切的关系。 按照m a r r 的理论，视觉过程分为三个阶段：早期阶段、中期阶段和后期阶段。 对应这三个视觉过程阶段，产生了计算机视觉中的三个层次研究内容：( 1 ) 低层次 视觉( i 。o wl e v e l ) ：表示二维图像中的重要信息，主要是图像中的亮度变化位置及 其几何分布和组织结构。( 2 ) 中间层次视觉( i m m e d i a t el e v e l ) ：在以观察者为中心 的坐标系中，表示可见表面的方向、深度值和不连续的轮廓。f 3 ) 高层次视觉( h i g h l e v e l ) ：在以物体为中心的坐标系中，用由体积基元和面积基元构成的模块化多 层次表示，描述形状及其空问组织形式。 其中，低层次视觉主要对输入的原始图像进行处理，这一过程借用大量的图 像处理技术和算法，如图像滤波图像增强、边缘检测、线条检测、角点检测，从 图像中提取如角点、边缘、线条、线条端点、边界及色彩等关于场景的基本特征 要素。这一过程还包括了各种图像变换、图像纹理检测、图像运动检测等。本论 文对二_ 二维图像角点检测算法、序列图像匹配算法的研究主要属于低层次视觉部分。 作为计算机视觉研究内容中三个层次的基层，对低层次视觉处理的准确性和有效 性将直接影响到中高层次视觉处理的难易及好坏，其在计算机视觉理论体系中的 作用将不言而喻。因此对二维图像角点检测算法和序列图像匹配算法进行研究， 不仅具有深远的理论意义也具有广泛的实用意义。 1 2 本课题的研究现状 1 2 1 二维图像角点检测 二维图像角点检测在计算机视觉和图像理解领域起着很重要的作用。如在立 体视觉、图像配准与匹配、目标识别及运动分析中应用。 早期的角点检测方法是首先对图像进行区域分割，通过链码提耿边界，然后 在边界上寻找方向变化较快的点，这种方法在很大程度上依赖于图像分割的效果， 而后者本身就是一项比较复杂的工作。同时这类算法的计算复杂度很高。 m o k h t a r i a n 和s u o m e l a 基于尺度空间( c u r v a t u r es c a l es p a c e ，c s s ) 描述提出一种 新的角点检测算法。他们首先使用c a n n y 检测器从原始图像中检测边缘，先使用 高尺度得到候选角点，然后逐步减少尺度，在多个低尺度处跟踪改善角点位置的 第一章绪论 方法提高角点检测的精度。为了降低角点检测过程中对噪声的敏感性，b i t a l 和 r a v 提出了一种基于多尺度滤波的角点检测方法，其思想是使用大小不同的高斯 窗对边界进行卷积运算，然后计算各边界点曲率值，并查询极值点，从而确定角 点的位置。r o s i n 提出在角点检测前，大部分基于曲率估计的角点检测器会使用 固定截止频率的滤波器对图像进行滤波，只有不被滤波器影响到的角点才能被检 测到。为了解决这个问题，b e u s 通过迭代的方式，每次迭代中改变检测参数， b a n d e r a 则利用轮廓的局部属性，采用可适应方法滤波轮廓。r e c h e 提出一种更加 稳定的可适应角点检测方法，使得滤波器的截止频率适应轮廓特征，即角点尺度， 获得较好的结果。近年来提出的角点检测方法大多是基于灰度图像的角点检测。 主要分为两类：基于模板的角点检测算法和基于几何特征的角点检测算法。基于 模板的角点检测算法，一般首先建立一系列具有不同角度的角点模板，然后在 定的窗口内比较待测图像与标准模板之涮的相似程度，以此来检测图像中的角点。 由于角点结构的复杂性，不可能设计覆盖所有方向和角点的模板，这。类角点检 测方法计算量大且比较复杂。基于几何特征的角点检测方法主要是通过计算象素 的微分几何特征来进行角点检测。其中较为典型的有k i t c h e n 和r o s e n e f e l d 提出 的基于局部梯度幅值和边界上梯度方向改变率的角点检测算法。但他们的角点检 测算法使用了图像亮度二阶导数，对噪声敏感。w a n g 和b r a d y 提出了一种基于 表面曲率的角点检测算法。为了改善角点检测的稳定性，首先将图像与高斯滤波 器卷积，然后计算整个图像的表面曲率，当曲率高丁_ 二一定闽值，并为局部最大值 的点被认为是候选角点。w a n g 的算法性能满足实时算法的需求，可用于运动估 计的实时角点检测。另外一类基于几何特征的检测方法为自相关角点检测算法。 这类算子不同于一般角点的直观定义，它们认为与邻域有较大的亮度差，或其局 部自相关亮度值较大的象素点为角点。m o r a v e c 认为在角点的某个邻域内，亮度 的变化在任意一条通过该点的直线上都很大，但他只考虑了八个方向，角点检测 算子误差很大。h a r r i s 算法由h a r r i s 和s t e p h e n s 发表，该算法在每个象素位置计 算2 2 的自相关矩阵爿，定义c r f 为d e t ( a ) k ( t r a c e 似) ) ：，k 是一个给定的常数， 具有大于某一门限值且为局部最大c r f 值的象素点认为是角点。这种算法效果 好，但计算量很大。最小亮度变化( m i n i m u mi n t e n s i t yc h a n g e ，m i c ) ，是t r a j k o v i c 等人在c r f 基础上提出的一种新的角点检测算法。该算法对每个象素基于其邻 域的图像亮度采用插值的方法计算c r f 值，具有大于某一门限值且为局部最大 c r f 值的象素点认为是角点。这种新的角点检测算法精度高、稳定性好，对噪声 具有鲁棒性且计算迅速。1 9 9 7 年，牛津大学的s m i t h 和b r a d y 提出了一种低层 次图像处理小核值相似区的方法，称为s u s a n 算法( s m a l l u n i v a l u es e g m e n t a s s i m i l a t i n g n u c l e u s ，s u s a n ) ，经过大量的实际应用，证明该算法对低层次图像 处理有较好的适用性和可靠性。 幽像角点检测平p 刚算法的研究 1 2 2 序列图像匹配算法 同场景在不同条件下投影所得到的二维图像会有很大的差异，这主要是由 以下的原因引起的：传感器噪声，成像过程中视角改变引起的图像变化、目标移 动和变形、光照或者环境的改变带来的图像变化以及多种传感器的使用等。为了 解决卜述图像畸变带来的匹配困难，人们提出了许多匹配算法，而它们都是由以 下的四个要素组合而成： ( 1 ) 特征空l i 白j ：特征空间是由参与匹配的图像特征组成的，选择好的特征 可以提高匹配性能、降低搜索空间、减小噪声等不确定性因素对匹配算法的影响。 匹配过程可以使用全局特征或者局部特征以及两者的结合。 ( 2 ) 相似性度量：相似性度量是指用什么度量来确定待匹配特征之间的相 似性，它通常定义为某种代价函数或者是距离函数的形式。经典的相似性度量包 括相关函数和m i n k o w s k i 距离，近年来人们提出了h a u s d o r f f 距离和互信息作为 匹配度量。h a u s d o r f f 距离对于噪声非常敏感，分数h a u s d o r f f 距离能处理当目标 存在遮挡和出格点的情况，但计算费时；基于互信息的方法因为埘于照明的改变 的不敏感性已经在医学等图像的匹配中得到了广泛应用，它也存在计算量大的问 题，而且要求图像之间有较大的重叠区域。 ( 3 ) 图像匹配变换类型：图像几何变换用来解决两幅图像之间的几何位置 差别，它包括平移变化，仿射变换、投影变换等。 ( 4 ) 变化参数的搜索：搜索策略是用合适的搜索方法在搜索空间中找出平 移、旋转等变换参数的最优估计，使得图像之间经过变换后的相似性最大。搜索 策略有穷尽搜索、分层搜索、p o w e l l 方向加速法、遗传算法和神经网络等。在成 像过程中，由于噪声和遮挡等原因，导致一幅图像中的特征基元在另一幅图像中 有几个候选特征基元或者无对应基元，这些都是初级视觉的不适定问题。通常在 丁f 则化框架下用各种约束条件来解决。同时，人们还采用最小平方中值法来有效 的消除假配点和误配点。 1 3 本论文研究内容和章节安排 本文详细介绍了各种二维图像角点检测方法，并主要针对自相关角点检测方 法，对其进行了归纳和分类。对m i c 角点检测算法进行深入探讨，针对基于多 格算法的m i c 角点检测方法容易混淆边缘点和角点、遗漏角点和角点定位不够精 确等缺点，提出了改进的m i c 角点提取算法。该算法先对低分辨率图像进行运算 并提取出候选角点，在恢复图像的高分辨率后，对候选角点周围的2 2 的象素点 第章绪论 进行进一步计算，将遗漏的象素点也列入候选角点，这样明显减少了原m i c 算法 由低分辨率到高分辨率的变化过程中角点的漏检概率。其次用梯度的概念对候选 角点进行筛选，减少了角点的虚报概率。将改进后的算法与以上各种经典的自相 关角点检测算法进行了对比，实验证明其执行效果良好。同时，本文对图像匹配 算法进行了分类和比较，并详细介绍了一些经典的匹配方法，同时给出算法的匹 配结果。 论文章节安排如下； 第一章在绪论中介绍了计算机视觉和本课题的研究现状。 第二章介绍二维图像角点检测准则和检测技术。 第三章介绍各种经典的自相关角点检测算法和本文的算法，同时也给出了改 进的算法与其他自相关角点检测算法的实验和比较结果。 第四章介绍了图像匹配算法，并进行了分类和比较。同时给出了其中几种算 法的匹配结果。 最后，作为本文的结束语，对全文的工作进行了总结，概括了其主要意义， ：牛提出了今后的研究和发展方向。 蚓像角点检测和匹配算法的研究 第二章二维图像角点检测准则和检测技术 2 1 二维图像角点检测准则 角点定义为二维图像亮度变化剧烈的点或图像边缘曲线上具有曲率极大值的 点。角点的信息含量很高，可以对视觉处理提供足够的约束，极大地提高运算速 度，在图像之f 自j 进行可靠的匹配。这些特点使得角点检测在机器视觉和图像处理 的许多方面都起着十分重要的作用。衡量角点检测算法性能的准则主要有以下四 个：( 1 ) 检测准确性：不计噪声，即使最细小的角点，角点检测算法也应浚可以 检测的到。( 2 ) 定位性：检测到的角点应尽可能接近它们的真实位置。( 3 ) 稳定 性：对相同场景拍多幅照片时，每一个角点的位置都不应该移动。( 4 ) 复杂性： 检测算法的复杂性越小，运行速度就越快，自动化程度就越高。 2 2 二维图像角点检测技术 已提出的关于角点检测的方法很多，基本上可以分为两类：基于图像边界信 息和直接分析图像局部亮度值的方法。基于图像边界信息方法的最早的途径之一 为基f 边缘轮廓链码的角点检测方法。这一类方法需对图像进行预处理，主要分 为三个步骤：首先，对图像进行预分割；然后，对预分割后得到的图像中的边界 轮廓点进行顺序编码，得到边缘轮廓链码；最后，根据边缘轮廓链码对图像中的 角点进行描述和提取。如通过链码的象素坐标寻找具有最大曲率值的点；对链码 进行多边形估训，寻找线段的交点或被描述成两条直线的交叉点等。这种方法过 多的依赖二f 图像分割及边缘检测的效果，而且图像分割复杂，计算量大，不适于 实时处理。m o k h t a r i a n 和s u o m e l a 基于尺度空间( c u r v a t u r es c a l es p a c e ，c s s ) 描 述提出一种新的角点检测算法。他们首先使用c a n n y 检测器从原始图像中检测边 缘，角点定义为具有最大绝对曲率的边缘点。在非常小的尺度，由于存在许多噪 声，具有最大绝对曲率的边缘点很多，而当尺度增加时，噪声被平滑，只有对应 真实角点的最大值保留下来，但角点的位置也在变化，这时角点的定位很差。所 以m o k h t a r i a n 算法首先在图像中用高尺度检测角点，然后逐步减少尺度，在多个 低尺度处跟踪改善角点定位。因为在降低尺度的过程中只需要计算候选角点，计 算量大大降低。为了降低角点检测过程中对噪声的敏感性，b i t a l 和r a y 提出了 第一章二维幽像角点检测准则和检测技术 一利，基丁| 多尺度滤波的角点检测方法，其思想是使用人小不同的高斯窗对边界进 行卷积运算，然后计算各边界点曲率值，并查询极值点，从而确定角点的位置。 针对图像中相同的特征点由于离场景的距离不同而具有不同的尺度，o l s o n 提出 使用立体相机来估计场景距离，并根据不同的距离列备个特征采用不同的尺度进 行滤波来进行角点检测。r o s i n 提出在角点检测前，大部分基于曲率估计的角点检 测器会使用固定截止频率的滤波器对图像进行滤波，只有不被滤波器影响到的角 点才能被检测到。为了解决这个问题，l ；e u s 通过迭代的方式，每次迭代中改变榆 测参数。b a n d e r a 则利用轮廓的局部属性，采用可适应方法滤波轮廓。 采用小波快速算法进行多尺度角点检测近年来也得到广泛研究。如沿着尺度 变化最大值的轨迹，在不同的尺度下检测拉普拉斯过零点，可以得到子象素精度 的检测结果。h u a 和l i a o 认为大部分的角点检测算法基于单尺度空间，而实际 图像中大部分的轮廓曲线是在不同的尺度上。比如，小尺度上的+ 个圆弧，大尺 度上可能认为是一个角点：而小尺度上的角点，大尺度上则可能被认为只是一个 噪声点。因此，单尺度角点检测会遗漏小的角点，并且忽视比较粗糙的特征点。 他们基于小波变换及其快速算法提出的角点检测算法，可以在大尺度上检测大的 特征点，也可以在小尺度上检测小角点，由于采用了快速算法，计算效率高。 基于图像边界信息的角点检测算法需要一定的预处理过程，复杂性高，容易 引入误差。因此，近年来提出的角点检测方法大多是直接基于坎度图像的角点检 测卡要分为两类：基于模板的角点检测算法和基于几何特征的角点检测算法。 基于模板的角点检测，般首先建立一系列具有不同角度的角点模板，然后 在+ 定的窗口内比较待测图像与标准模板之间的类似程度，以此来检测图像中的 角点。例如，s i n g h 等建立了一个方形模板，模板大小 = 2 k + 1 ，每次将模板旋 转j r 4 ，形成八个模板。对每一个象素，设p 。，q 。表示模板p 和图像q 中( f ， ，j ，位置处的象素值，定义模板均值a ，方差。淀义图像中以( f ，) 为中心，大小 为7 1 n 的窗口均值为口，方差9 i 3 。利用八个模板计算此窗口和模板的广义相关 一陛： 盯，= ；窆壹( 叫吼吐， r 一 盯( p ) 盯( g ) u ( 2 1 ) 最后，认为具有局部最大广义相关性的象素为角点。由于角点结构的复杂性， 模板不可能覆盖所有方向的角点，这一类角点检测方法计算量大且比较复杂。 基于几何特征的角点检测方法主要是通过讨算象素的微分几何特征来进行 角点检测，其中较为典型的有k i t c h e n 和r o s e n e f e l d 提出的基于局部梯度幅值和 边界上梯度方向改变率的角点检测算法。即令，= o i & ，j ，= 8 j 卸为图像一阶 导数，。= o2 i o x x 、，= a 2 ，a 砂、，。= a2 i a y y 为图像二阶导数，y j 处的 幽像角点检测利匹配掉法的研究 梯度方向o ( x ，y ) = t a n ( o ) = ，。1 。则角点检测函数定义为： 卜型i 型! 二堡丝( 2 - 2 ) l ，一：= 一 ， ( ，：+ ? ：) 式中，。，。，。，。，。为图像亮度的一阶和二阶导数。 k i t c h e n 和r o s e n e f e l d 角点检测算法使用了图像亮度二阶导数，对噪声敏 感，并且小能类似于x ，y 和t 类型的二维特征。 w a n g 和b r a d y 提出了一种基于表面曲率的角点检测算法。为了改善角点检 测的稳定性，首先将图像与高斯滤波器卷积，然后计算整个图像的表面曲率： 壮志警j 即| 1 ( 2 - 3 ) 其中，图像定义为堆，纠，梯度矢量v i = ( i x 。) ，边缘法线方向”= v ，i v ，i ， 掣为沿着图像梯度切线方向的方向导数。曲率高于一定特定值，并为局部最 o t 。 大值的点被认为是候选角点。最后，当下述情况满足时，候选角点被确认为角 点： 刮警v 州 堡：0( 2 。4 ) a 。 l v f j2 ra l 式中s ，f ，正为用户自己定义的特定值。 w a n g 和b r a d y 简化了角点检测过程，当图像大小为m m 时，算法仅需要 m 2 ( 4 n2 + 2 ) 次操作，性能也满足实时算法的需求，可用于运动估计的实时角点 检测。 b e a u d e r 基于h e s s i a n 矩阵提出了一种循环不变量的角点检测算法，命名为 d e t 算法。他认为可以门限化这个算子的极大值进行角点检测。d e r i c h e 和 g i r a u d o n 认为使用上述算子不能精确定位角点位置。因为角点的确切位置在尺度 空间中拉普拉斯过零点处，他们将拉普拉斯算子和d e t 算子相结合，提出了一科一 新的角点检测算法，但这种算法计算非常复杂。 另外类基于几何特征的角点检测算法为自相关角点检测算法。这类算子不 同于一般角点的直观定义，它们认为与领域有较大的亮度差，或者其局部自相关 亮度值较大的象素点为角点。m o r a v e c 认为在角点的某个领域内，亮度的变化在 任意一条通过该点的直线上都很大。他对每一个等待检测的象素取窗口，从八个 方向计算这个象素的非征则化自相关值，并且选择最小值作为这个象素的角点响 应函数( c o r n e rr e s p o n s ef u n c t i o n ，c r y ) 。由于只考虑t j 个方向，m o r a v e c 角点 第一章一维图像角点检测准则和检洲技术 检测算子的误差很大。h a r r i s 和s e t p h e n s 也使用卜述思想进行角点检测，但他们 采用一阶导数来估计自相关性。对每个象素，汁算2 2 自相关矩阵： a ：+ lr w ) c v l ) 7j ，是高斯平滑模板。如果二个特征值都很大，此象素点为角 点。为了避免爿的特征值分解，定义c r f 为：d e t ( a ) k ( t r a c e ( a ) ) 2 ，其中，k 为 给定的常数。h a r r i s 算法检测效果较好，但由于进行r 三次高斯滤波，计算量很 大。s m i t h 和b r a d y 提出了一种低层次图像处理小核值相似区的方法，称为s u s a n 算法( s m a l lu n i v a l u es e g m e n ta s s i m i l m i n gn u c l e u s ，s u s a n ) ，经过大量的实际 应用，证明浚算法对低层次图像处理有较好的适用性和可靠性。最小亮度变化 ( m i n i m u m i n t e n s i t yc h a n g e m i c ) ，是t r a j k o v i c 等人在c r f 的基础上提出的一 种新的角点检测算法。该算法对每个象素基于其领域的图像亮度采用插值的方法 计算c r f 值，具有大于某一特定值并且为局部最大c r f 值的象素点认为是角点。 这种角点检测算法精度高、稳定性好、对噪声具有鲁棒性且计算迅速。 以上对大量的角点检测算法进行了回顾和分析，以下本文选择检测效果比较 好，运算比较简单的几种自相关角点检测算法进行具体研究，分析它们的优点和 存在的一些问题，并在研究的基础上提出本文的新算法，最后给出比较结果。 幽像角点检测和匹配算法的研究 第三章自相关角点检测算法 3 1h a r r i s 角点检测算法 l t a r r i s 角点检测算法由c h r i sh a r r i s 和m i k es t e p h e n s 在1 9 8 8 年提出。本 文先介绍m o r a v e c 角点检测算子。l l l o r & v e c 角点检测算子研究图像中的一个局部 窗口在不同方向进行少量的偏移后，窗口内的图像亮度值的平均变化。需要考虑 如下三种情况： 1 假如窗口内的图像块的亮度值是恒定的，那么所有不同方向的偏移仅导致 一个小的变化。 2 假如窗口跨越一条边，那么沿着边的偏移将导致一个小的变化，但是与边 垂直的偏移将导致一个大的变化。 3 ，假如窗口块包含角点或者是一个孤立的点，那么所有不同方向的偏移将导 致个大的变化。因此，定义由任意方向的偏移而引起的最小变化值大于某一个 特定值的那个点是角点。 m o r ；l v e c 角点检测算子可以简单描述为：在角点的某个领域内，亮度的变化 在任意一条通过该点的直线上都很大。对每个待检测的象素点取窗口，从各个 方向来计算这个象素的非正则化自相关值，并且选择最小值作为这个象素点的角 点响应函数。 以下将给出m o y a v e e 算子存在的一些问题和h a r r i s 等人给出相应的解决措 施。 l _ 在计算象素点的非正则化自相关值时只考虑了象素点的八个方向( 每隔 4 5 度取一个方向) 。可以通过将区域变化式f 扩展，将所有方向的小的偏移表现 出来： e = w 。k 。+ 。一，。】2 = w 。畔+ y y + d ( 工2 + y 2 ) 】2 ( 3 一1 ) 这里一阶导数近似为：x = i 9 ( - 1 ，0 ，1 ) = 酬反y = ， ( 一l ，0 ，1 ) 7 = 别锣 因此，对于小的偏移，变化f 能够写成： t 。= a x 2 + 2 c x y + 缈2 ( 3 2 ) 式中a = x2 wb = y2 固w c = ( 妤) 固w 2 m o r a v e c 算子没有对图像进行降噪处理，所以响应对噪声敏感。可以使用 第三章自相关角点检测算法 平滑的圆形窗口先对图像进行预处理来降低噪声影响，比如高斯窗口： 。= e x p 一02 + v 2 ) 2 g 2 ( 3 - 3 ) 3 因为仅仪考虑了f 的最小值，所以m o r a v e c 算子对边缘响应很敏感。解决 方法：蘑新定义角点准则。对于小的偏移阢y ) ，变化f 能够精确的写成： e 。= ( x ，y ) m ( x ，y ) 7 ( 3 - 4 ) 式巾矩阵吖为2 2 的对称矩阵： m = 罢翻 注意变化f 与局部自相关函数密切相关，矩阵m 描述了f 在原点的形状。设 定口，卢是 的二个的特征值。口和与局部自相关函数的主要曲率成比例，都可 以用来描述m 的旋转不变性。正如以h 所言，有三种情况需要考虑： a 假如二个特征值都是小的，以致于局部自相关函数是平的，那么图像中的 窗口区域为近似不变的亮度。 b 假如一个特征值是高的，而另一个是低的，以致于局部自相关函数呈现山 脊的形状，那么这显示是一条边。 c 假如二个特征值都是高的，以致于局部自相关函数是突变的山峰形状，那 么在任何方向的偏移都将增加f 的值，显示这是一个角点。 为了避免求解m 矩阵的特征值，使用公式r ( m ) 和d e t ( 肋： n ( m ) 2 口+ 卢= 爿枷( 3 5 ) d e t ( m ) = 柏= a b c 2 定义下式来计算h a r r i s 算法的角响应函数 r = d e t ( m ) 一i n ( 肘) 2 ( 3 6 ) 式中角响应准则斤在角的区域是个j 下值，在边的区域是负值，在不变化的区 域是个很小的值。在实际应用中，计算图像窗口中心点的r 值，如果大于某一个 给定的门限值，则这个点为角点。 h a r r i s 算法稳定性高，对噪声不敏感，对l 形状的角点检测准确性高，但出 于采用了三次高斯滤波，运算速度慢。 3 2 s u s a n 角点检测算法 s u s a n 算法是1 9 9 7 年英国牛津大学的s m i t h 等人提出的一种处理灰度图 像的方法。首先介绍u s a n 角点检测准则。 j g - 位于圆形窗口模板中心等待检测的象素点称为核心点。假设图像为非纹理， 核心点的邻域被划分为两个区域：亮度值等于( 相似于) 核心点亮度的区域即核 值相似区( u n i v a l u es e g m e n ta s s i m i l a t i n gn u c l e u s ，u s a n ) 和亮度值不相似于 幽像角点检测汞i 匹配算法的研究 核心点亮度的区域。u s a n 的概念是s u s a n 算法的准则。它包含了图像结构中大量 的信息。如图3 1 给出了u s a n 的三种典型形状： ( a ) 核心点托u s a n 区域内( b ) 核心点是一个边缘点( c ) 核心点是柏点 图3 iu s a n 的3 种典型形状 考虑上述三种情况，对于核心点在u s a n 区域内，其u s a n 区域最大；核心 点位于边缘，其u s a n 区域为整个邻域面积的1 2 ；而角点附近u s a n 区最小。 基于这一原理，s m i t h 提出了最小核值相似区( s m a l l e s tu n i v a l u es e g m e n t a s s i m i f a t i n gn u c l e u s ，s u s a n ) 角点检测算法。 将模板中的各点与核心点( 当前点) 的亮度值用下面的相似比较函数来进行 比较( 这聃采用的是3 7 象素的模板，最小的模板为3 3 的模板) 。 。( ；，i ) ：i l l 他) ( 吵 ( ：j _ 7 ) 。3 1 0 矿i 币) 一丽) p f h 卜 式中i 为二二维图像中核心点的位置，+ r 是模板其他点的位置，( ；) 是模板中任意 象紊点的亮度值，f 是表示亮度差值的一个门限值，c 是一个用来比较输出的函数。 c 由模板中所有象素参与运算得出。u s a n 的大小可由下式计算出： n ( x o ，y 。) = c ( x ，y ) ( t ，y ) ( u ，h 一 ( 3 8 ) 式中n 是u s a n 区域内象素的个数。 参数，决定了u s a n 区域各点之间最大的亮度差值。将h 与一个特定的门限值 占进行比较，s u s a n 角点检测算法将g 设定为h 。( 定义n 。为u s a n 的最大面积) 大小的一半，通过下式来产生角点初始响应函数。 r 一 一 r ( i ) ： g - n ( r 0 ) n ( r o ) 0 ；角点响应函数在正方形上 有最小值，则x 的极大点必须在( o ，1 ) 范围内，并且必须保证o b a 1 。由以 二条件得到b 0 ，则令c r f 值为： 幽像角点检测雨j 匹配算法的研究 r = c b2 a ( 3 - 2 0 ) 假如这个值不符合要求，那么c r f 值直接由式( 3 一1 4 ) 得出。 t r a j k o v i c 等人义提出了多格算法进一步改进了m i c 算法，采用这种算法可以 减少计算时问；并提高了被检测角点的质量。 以下将简单介绍多格算法如何用于m i c 中柬找到角点，其步骤为： ( 1 ) 首先在一个低分辨率的图像的每个象素点处利用式( 3 1 4 ) 计算简单的 c r f ，把c r y 大于门限z 的象素点标志为候选角点。 ( 2 ) 在图像恢复高分辨率后，对步骤l 中的每个候选角点： ( i ) 再利用式( 3 1 4 ) 计算c r f ，假如角点响应值低于门限，那么该 候选角点不是捕点。 ( 1 i ) 若i 中的角点响应值大于门限l ，则进步使用在前面介绍过的线 形内部象素插值方法来得到一个新的c r f 值，如果小于门限t ，那么该候选角点 不是角点。 ( 3 ) 用n m s ( n o n m a x i m u ms u p p r e s s i o n ) 方法找到具有局部最大角点响应 值的候选角点点，并把它们确认为角点。 t r a j k o v i c 等人认为m i c 角点检测算法具有精度高，运算速度快，稳定性好， 对噪声具有鲁棒性的特点，但仍有不足，如图像的量化结果，插值不能达到很好 的效果，致使有些边缘点和角点区分不出来；不使用大的模板进行c r f 运算，会 遗漏很多角点，但对于对比度明显的边缘，使用大的模板又会造成角点定位不够 准确。同时，在多格算法中，当图像从低分辨率由高分辨率转化，必将丢失一部 分候选的角点，从而增加了角点漏检的概率。 3 4 改进的m i c 的角点检测算法 本文针对基于多格算法的m i c 角点检测方法容易遗漏角点及角点定位不够 精确等缺点，提出一种改进的m i c 角点提取算法，相对于原m i c 多格算法而言， 有二个优点：( 1 ) 先对低分辨率图像进行运算并提取出候选角点，在恢复图像的 高分辨率后，对候选角点周围的2 2 的象素点进行进一步计算，将遗漏的象素点 也列入候选角点，这样明显减少了原m i c 算法由低分辨率到高分辨率的变化过程 中角点的漏检概率。( 2 ) 用梯度的概念对候选角点作进一步的筛选，减少了角点 虚报的概率。 具体算法如下： ( 1 ) 采用m i c 多格算法的步骤1 来找到候选角点，其中门限值g = 5 0 0 ，采 用直径为7 的模板； ( 2 ) 对候选角点恢复其高分辨率位置后，对每一个高分辨率下的候选角点来 第三章臼相芙角点检测算法 汁算它周围2 2 个象素点的简单c r f ( 采用式( 3 1 4 ) ) ，如果象素点的c r f 大十 门限g ，则也将这个点标为候选角点，采用这种方法将明显减少了原m i c 算法 由低分辨率到高分辨率的变化过程中角点漏检的概率。其中门限值g ，= 2 0 0 ，采用 茸径为3 的模板； ( 3 ) 对高分辨率图像下的所有候选角点，采用7 7 线形内部象素插值，用 m i c 多格算法的步骤2 来滤除一些伪角点，进一步定位角点位置，这时候由于使 用了大窗口进行c r f 运算，获得的候选角点比较多，很难作到精确定位，因此对 于一些边缘清楚的候选角点，应该使用3 3 的小窗口模板进行线形插值，将使用 大窗口得到的真正角点附近的伪角点滤除。这里采用梯度的概念，即对每一个候 选角点测定其水平和垂直二个方向上梯度绝对值的和，如果这个值大于门限值 g ，则认为足够清楚，使用小窗口插值，精确其位置。其中门限值g ，= 1 0 0 0 ： ( 4 ) 对候选角点而言，如果处在一个对比度比较明显的边界上，则一般它与 其邻域的亮度差值或者比较大，或者很小。由梯度的概念可知，其值是与相邻象 索的亮度差值成f 比。在图像轮廓上，象素的亮度有陡然变化，梯度值很大；在 图像亮度变化相对平缓的区域梯度值比较小；而在等亮度区域，梯度值为零。采 用了梯度的概念进行判定，避免了大窗口在对比度明显的区域中进行角点检测而 造成的候选角点过多、角点定位不准确等缺点；又避免了小窗口在对比度不明显 的情况下的漏检现象，在进行大小窗口选择时，不需要人工判定，可以自适应进 行，大大提高了准确性； ( 5 ) 采用m i c 多格算法中的步骤( 3 ) 来获得最终的角点。 下一节将介绍改进的m i c 算法角点检测算法和h a r r i s ，s u s a n 和m i c 角点检 测算法的比较，同时给出实验结果。 3 5 实验结果 这一节里，本文给出h a r r i s ，s u s a n ，m i c 和改进的m i c 角点检测算法的 实验结果。并从以下四个准则来进行理论和实验上的检测和对比。 ( 1 ) 准确性：这是一个主观的评价一主要从检测的角点位置来看。 ( 2 ) 计算代价：这将通过理论和确定的实验来解释。 ( 3 ) 稳定性：这将通过从区分质地角点和几何角点来看。 ( 4 ) 抗噪声性：通过对图3 6 来观测 3 5 1 检测图像 这- - + 节，首先描述一下用来评价角点检测算法执行效果的图像。如图3 5 幽像角点检测和匹配算法的研究 和图3 - 6 所示。罔3 5 是一张真实的场景图像，主体是某一建筑物。它包含了火 曼的儿何角点信息，如窗户的角点。在图像的非主体地方含有大量的纹理角点(