数字摄影测量论文典型点特征提取算法研究.docx

典型点特征提取算法研究摘要： 立体像对的自动匹配和目标的自动识别是当代摄影测量研究的一大热点，而特征提取是自动匹配和目标识别的前提。特征提取包含点特征提取、线特征提取和面特征提取，本文主要研究和实现了Moravec算子、 Forstner算子和Harris算子这三种基本的点特征提取算法。通过编程实现，对三种点特征提取算子的效果和优缺点做了比较分析。关键词： 点特征提取，Moravec算子，Fostner算子，Harris算子0. 前言当代摄影测量与传统摄影测量的根本区别在于数据处理的自动化或半自动化，如：数据的自动获取，影像自动纠正，影像自动匹配和影像自动拼接等【1】。这些自动化的前提是对影像特征的自动提取。影像的特征一般可以分为点特征、线特征、面特征三类。在同名点匹配、DEM（和DSM）密集点云生成中最重要的是点特征的提取和精度定位。点特征是指在影像上最基本的特征，是一种表征影像局部特性的位置度量，可以用来作为影像中具有一定特征的局部区域的位置标示【2】。通俗来讲点特征可以定义为那些灰度在多个方向都有较大变化的点，如圆点、角点等。提取点特征的算子一般被称为兴趣算子或有利算子。在各种文献中，人们根据不同的出发点和目的提出了多种特征提取的兴趣算子。而这些兴趣算子根据它们性质又大致可以分为三类【3】【4】。第一类是基于模板匹配的算子：通过计算一个固定的特征点模板与所有图像子窗口的相似性，以相似程度来判断某一象元是否为特征点，这种方法计算量较大，比较耗费时间。第二类是基于图像边缘特征的算子：通过先对图像的边缘轮廓进行提取，然后通过边界上方向变化的快慢来判断特征点，这种方法的效果依赖于图像边缘提取的效果，计算复杂度高。第三类是基于影像灰度的算子：影像的灰度是对地物的反射信号的数字化记录，因此类比于信号处理，通过对影像局部灰度变化的计算来找到信号有较大变化的点，这样的点就是所寻找的特征点，这种基于灰度的方法计算简单，因而使用较为普遍。角点在特征点中更为常见，在实际图像中一般位于轮廓的拐角、直线的交点、直线的端点等位置。其类型大致可分为：L型交叉点、T型交叉点、Y型交叉点、X型交叉点、箭型交叉点（如下图0.1所示）。本文中主要研究和实现了几种最常见的点特征提取算子：Moravec算子、Forstner算子和Harris算子。主要的提取目标为角点，并通过标准图像（如下图0.2所示）来对三种点特征提取算子的提取效果作比较。（图0.1 典型角点）1. 算法原理和实现1.1 Moravec算子Moravec于1977年提出利用灰度方差提取点特征，这就是Moravec算子，它属于第三类基于影像灰度的算子。Moravec算子通过计算各像素四个主要方向（即：0度方向、45度方向、90度方向、145度方向（如图1.1所示）上面灰度的差平方和，并且选取灰度差平方和中的最小值为该点的角点响应函数值或称兴趣值（IV），然后通过一定的阈值判断，选取兴趣值IV中大于阈值的点做为候选点，最后通过一定的窗口，选择窗口中备选点里的极大值点做为该窗口中的特征点。（图1.1 Moravec算子的四个方向）具体的实现步骤如下：（1）计算各象元的兴趣值IV。在以像素（c，r）为中心的w*w的窗口中，计算该像素四个主要方向相邻像素的灰度差平方和：其中k = INT（w/2），即计算窗口的一半大小。然后取上述四个值的最小值作为该像素的（c，r）的兴趣值：（2）通过经验阈值选取候选点。给定一个经验阈值，将上一步中的到的兴趣值大于该阈值的点作为候选点。此时阈值越小，结果中提取到的特征点越多；阈值越大，结果中提取到的特征点越少。（3）极大值滤波，选出特征点。在一定大小的窗口内（一般不同于兴趣值计算的窗口大小）选取兴趣值中最大的点作为特征点。1.2 Forstner算子Forstner算子也是属于第三类利用灰度选取特征点的算子，作为一个可以用于精确定位的特征提取算子，Forstner算子的理论更偏向于误差处理，整体计算过程比Moravec算子要复杂一些。在本文中只考虑算子在提取特征点（即选取最佳窗口）的过程的实现。Forstner算子通过计算各像素的Robert梯度和以像素为中心的一个窗口的灰度协方差矩阵，在影像中寻找尽可能小而接近于圆的误差椭圆的点作为特征点。算法的具体实现步骤如下：（1）计算窗口中灰度的协方差矩阵。其中：分别表示窗口中各像素点的Robert梯度值。（2）计算兴趣值q和w。其中： DetN 表示矩阵N的行列式；trN表示矩阵N的迹。（3）确定候选点。根据经验阈值，选取出候选点。这里的对q和w分别有阈值。（4）选取极值点。在一个适当的窗口里做极大值滤波，以权值w为依据选取极值点，则这样的点就是我们提取的特征点。1.2 Harris算子Harris算子也属于第三类利用灰度选取特征点的算子，通过计算与自相关函数相联系的的矩阵M，M矩阵的两个特征值是自相关函数的一阶曲率，然后计算两个曲率值，如果两个曲率值都大，则认为该点为特征点。Harris算子的思想是通过自相关矩阵来提取角点。本文中，对经典的Harris算法加入了一个阈值选择的步骤。具体算法步骤如下：（1）一阶差分，计算梯度。首先确定n*n的影像窗口，对窗口中像素点进行一阶差分运算，求得梯度值。（2）高斯滤波，计算I值。计算出与自相关函数相联系的矩阵M，M阵的特征值是自相关函数的一阶曲率。按如下公式计算I值：（3）确定候选点。给定一定的阈值，选取候选点。（4）选取特征点。在一定大小的窗口内（一般不同于兴趣值计算的窗口大小）选取 I 值中最大的点作为特征点。2 效果分析2.1 Moravec算子2.1.1 提取效果对测试图像进行特征点提取，得到结果如下图2.1所示。（图2.1 Moravec算子提取效果）从图中可以发现在高对比度处的几种基本类型的角点都被提取出来，但在一些低对比度的小区域中典型的角点没有被提取出来。特别是在测试图像的左方的灰度梯度区域，没有提取出任何的角点。还可以发现Moravec对图中某些斜向的边缘非常敏感，在实心形体的几条近45度和135度的边缘上面提取出了很多特征点。2.1.2 效果分析Moravec算子通过计算象元的四个方向的灰度差平方和来作为判断是否特征点的条件。通过上面的提取效果图我们可以发现Moravec算子的如下特点：（1）经验阈值影响大。通过算法的原理可以知道，Moravec算子提取的特征点是大于阈值的兴趣值中的最大值点，阈值是会直接影响到做极大值滤波时的候选点数目。从上面的提取效果中也可以发现，图像中灰度对比度较小的区域里的非常明显的特征点也没有提取出来。这并不是因为Morave算子本身的缺陷，而是由于阈值设定所产生的问题。但是在Moravec算子的机制下，要想找到一个通用的阈值选择方法是很麻烦的，所以一般需要人工不断的更改阈值以得到对于一幅影像较为合理的阈值。（2）噪声敏感。在提取的结果中还有一个明显的特点：对某些斜向的边缘线敏感。通过对比可以发现，在图像中一个像素大小的斜向边缘并不能引起Moravec算子的高敏感性。所以，可以得到结论：Moravec算子并不是具有斜向边缘敏感性的特征提取算子。通过对图像放大，可以看到提取了很多特征点的倾斜边缘实际上是由锯齿状的结构构成，而这些锯齿结构就像一个一个独立的噪声点，使得计算出的IV值有极大值出现，也即是引起了Moravec的敏感性，最终提取出了很多的特征点。（3）不能准确定位。Moravec算子在计算四个方向灰度差平方和值时是将窗口中某一方向相邻像素的差值直接平方相加，也即等权的相加。这样做的结果就是角点的定位不准确（一般最大会偏移一个像素）。可以通过下图2.2来说明这种局限性。（图2.2 假设局部灰度图）上图假设为某影像上的一个小区域示意，可以知道最好的角点提取结果是图中蓝色五角星所在的位置。采用5*5的窗口（如1.2图中的红色框和蓝色框）来计算IV值，根据计算四方向值的原理可以知道，红色点处的 IV = 255*255 ，蓝色点处的 IV = 255*255。假设阈值取值为255，那么也就是说图中的红色点和蓝色点在Moravec算子的机制下都可以成为候选点，甚至于图中的绿色点和黄色点也可以成为候选点。在极大值滤波的过程中，如果按照顺序搜索最大的情况来选择最大值，那么无论怎样计算都不可能正确的选择出蓝色点，而红色点却很容易被选当做特征点提取出来（偏移量为1个像素）。通过上述分析，可以清楚的看到Moravec算子的定位不够精确，特征点会被错误提取。因此，在很多论文中提到了通过增加Moravec算子计算的方向的个数来提高结果的正确率，但增加方向的度量不好确定，而且增加方向会几何倍数的增加计算量，例如：增加30度方向，那么就必然会增加60度、120度、150度、210度、240度、300度、330度这几个方向。考虑到图像是一种信号的记录，而离中心点不同距离的信号对中心点的影响是不同的。那么我们可以考虑距离加权的方式来计算这四个方向的灰度差平方和，这样在计算值时只需要乘上一个权值（权值可以定义为）就可以将不同距离的像素最中心位置的灰度影响表现出来。对于上图而言，蓝色点处的IV值就会大于其余三个点处的IV值，最终就可以准确的定位出红色点的特征点。2.2 Forstner算子2.2.1 提取效果对测试图像进行特征点提取，得到结果如下图2.2所示。（图2.3 Forstner算子提取效果）从图中可以看到，在对比度较大的区域里明显的特征点都成功提取出来，但在对比度较小的图像区域（左方的灰度梯度区域）也没有任何的特征点被提取出来还可以看到提取结果中并没有像Moravec算子一样在倾斜边缘上出现很多的提取结果。2.2.2 效果分析Forstner算子通过计算Robert梯度值组成的灰度协方差矩阵来判断特征点。通过上面的结果可以看到Forstner算子有以下特点：（1）经验阈值影响大。同Moravec算子一样，需要通过阈值判断来确定候选点，阈值的选择合理性会影响到最后的提取特征点的数目。（2）一定程度的抗噪能力。Forstner算子通过对灰度的协方差矩阵的计算，选择出那些接近于圆的误差椭圆的点，因此Forstner算子不像Moravec算子仅仅考虑了某几个方向的灰度变化量，还考虑到了整体的误差椭圆的分布。最终表现的结果就是对于锯齿状的边缘而产生的伪特征点有一定的抗噪能力。2.3 Harris算子2.3.1 提取效果对测试图像进行特征点提取，得到结果如下图2.3所示。（图2.4 Harris算子提取效果）从图中可以看到，Harris算子对图中的特征点基本上全部提取出来了。而且不同于在Moravec算子和Fostner算子提取结果，Harris算子在图像左方的灰度梯度区域也提取出了特征点，但其定位效果不如Forstner算子。在图中某些倾斜的边缘上也有一些点被提取出来，但特征点的数量少于Moravec算子提取出来的结果。2.3.2 效果分析Harris算子通过自相关矩阵来提取角点。通过上面的效果图可以发现Harris算子有以下特点：（1）经验阈值影响大。在本文中，对Harris算子添加了一个阈值判断步骤。因此，同前面两个算子一样，需要通过阈值判断来确定候选点，阈值的选择合理性会影响到最后的提取特征点的数目。（2）对L型角点定位较好。在结果图中可以看到Harris提取的特征点在L型角点处定位准确，都是在最佳的角点位置处；包括在倾斜的边缘处提取出来的那些特征点很多也是因为L型的角点而被提取出来的。2.4 三种算子的分析比较三种特征提取算子都是属于第三类通过影像灰度来提取特征点的算子，但是由于不同的提出目的和理论，它们的理论、复杂程度和提取结果都有所差异。Moravec算子基于灰度差平方和作为特征点提取的测度；Forstner算子基于Robert梯度构成的灰度协方差矩阵，引入误差椭圆的概念作为特征点提取的测度；而Harris算子则是通过相关矩阵作为点特征的提取测度。在影像灰度的基础上都根据提出者各自的领域和目的加入了一些相关的专业特点。三种算子对测试图像提取的耗费时间如下表：表一 三种算子特征提取情况统计特征提取算子耗费时间（ms）提取点数（个）Morave125280Forstner9451Harris561152整体上来讲，Moravec算子是三种算子最简单的，在提取结果中会对锯齿状噪声非常敏感；Forstner算子整个结构比较复杂，但是在本文中，只是考虑了其确定最佳窗口的实现，因而整个算法被简化，它对噪声有一定的抵抗，提取的特征点结果都是非常典型的角点，定位精度比Moravec算子高；Harris算子比本文中前两个算子都要复杂一些，因为多了一个高斯滤波的步骤，计算时间是三个算子中最长的一个，提取结果中L型角点的定位精度是三种算子里面最好的，但是其它角点定位误差较大，对噪声的抵抗性也较差。但在实际的应用中，可以发现Harris更加可靠，提取出来的点分布较为均匀，数量也比较适中；而Moravec由于对锯齿状的边缘非常敏感往往会产生很多的无效特征点的提取，Forstner提取的特征点会比较少而不满足于如DEM密集点生成等任务。3 结束语在本次试验中，对三种常见的点特征提取算法进行了讨论，由于某些原因本文只是按照最原始的理论对三种算子做了算法的实现。通过对测试图像的提取结果分析，对三种算子各自的特点做了描述，并做了简单的横向分析比较。在试验中还发现了一些问题：（1）对于Moravec算子的灰度差平方和可以做加权改进，这样可以提高算子定位的准确度。（2）在实现三种算法时，发现先做极大值滤波再判断阈值和先判断阈值再做极大值滤波两种方法提取的效果差别很大，但具体原因未作分析。（3）对于三种