结合NNDR与霍夫变换的匹配方法.docx

结合NNDR与霍夫变换的匹配方法
在建立两幅图像之间局部特征的匹配关系时，可以参照Marr等人Error! Reference source not found.提出的匹配应该满足唯一性、相似性、连续性三个基本约束条件，即物体表面任意一点到观察点的距离是唯一的，因此其视差是唯一的，给定一幅图像中的一点，其在另一幅图像中对应的匹配点最多只有一个；对应的特征应有相同的属性，在某种度量下，同一物理特征在两幅图像中具有相似的描述符；与观察点的距离相比，物体表面因凹凸不平引起的深度变化是缓慢的，因而视差变化是缓慢的，或者说视差具有连续性。
1 基于NNDR的匹配策略
目前常用的目标匹配策略有两种：一种是距离阈值法（Threshold-based Matching），即待匹配目标与模型之间的距离小于某个阈值，则认为匹配上了，该方法非常简单，但是阈值的确定非常困难，而且目标很容易匹配上多个模型，从而产生大量的误匹配；另一种是最小距离法(Minimum Distance)，即目标只匹配与其距离最近的模型，实际应用中一般还需要满足距离小于某个阈值的条件，该方法只有一个最佳的匹配结果，相对于距离阈值法来说，正确率要高。
由于图像的内容千差万别，加上场景中的运动物体、不重叠内容以及图像质量等因素的存在，一幅图像中的局部特征并不一定能够在另一幅图像中找到相似的特征，这就需要采取措施剔除那些产生干扰的噪声点，通常把这样的点称为“外点”。许多图像的背景比较相似并不具有区分性，如天空、旷野之类，它们的局部特征之间的距离要小于有用的特征之间的距离，但是它们并不能描述图像的主要内容，所以设置一个全局性的距离阈值来决定局部特征匹配与否显然是不合适的。
对SIFT特征的研究Error! Reference source not found.表明，可以通过比较最近邻（First Nearest Neighbor）特征和次近邻（Second Nearest Neighbor）特征的距离可以有效地甄别局部特征是否正确匹配。这就是最邻近距离比值法（Nearest Neighbor Distance Ratio, NNDR），其表述如下，如果待匹配特征为，其最邻近特征为，次邻近特征为，那么判断该特征匹配的条件为：
（5-1）
该方法理论来源是，如果一个特征在一幅图像中与两个特征的距离都很相近，那么该特征的区分度较低，也违背了Marr提出的“匹配应该满足唯一性”的原则，会对图像相似度的判断产生干扰。如图5.1所示，进行SIFT特征匹配的实验结果也证实了这一点，当剔除与最近邻点和次近邻点距离比值大于0.8的特征对时，排除了90%的干扰而仅仅误删了5%的正确特征对。

图Error! No text of specified style in document..1 特征点匹配的概率分布
该实验从图像数据库中选取的待匹配图像，共提取了40000个SIFT特征，对这些待匹配的图像进行了随机数值的尺度变化和平面旋转，并进行了深度小于的视角变化处理，同时也加入2%的高斯噪声。
2 邻近特征点的搜索算法
用穷举法搜寻最邻近点以及次邻近点，可以得到最精确的结果。但是由于本书所用的特征空间一般都高达128维以上，加之复杂图像的局部特征数量比较多，搜索算法的效率显然成为了整个系统的一个瓶颈。
1. K-D树搜索策略
标准K-D树是Friedman等人Error! Reference source not found.提出的一种高维二叉树，K表示空间的维数，在其上可实现对给定特征点的快速最近邻查找。若某K-D树的结点数目为N，则在它上面的最邻近节点的平均计算复杂度为。其后又相继提出了K-D树的近似最近邻搜索算法(ANNS)，其主要思想是在搜索时只查询那些与给定特征点的距离小于当前最近距离倍的点，此时搜索完成时返回的点未必是真实的最近邻点（除非），但是即使当取的较大（如时），所返回的点仍然有50%的机会是真实的最近邻点，而且在平均意义上它们到目标点的距离只是真实最近邻点到目标点的距离的11.5倍，取得的加速比却可以达到50倍以上。
在数据维数较低的时候，K-D树搜索方法比较有效。在更高维的数据空间中将会有更多的分类结果接近目标真实数据，此时使用K-D树进行搜索的话，效率将会急剧下降。本书所用的特征空间一般都高达128维以上，为此本书使用了Beis和Lowe提出的Best-Bin-First（BBF）算法Error! Reference source not found.提对常规的K-D树搜索方法进行改进，从而实现较快的匹配点搜索。
2. 基于BBF算法的搜索策略
在高维数据搜索空间中，K-D树搜索的结果仅仅只有很少的一部分满足邻近原则，为了加快搜索速度，可以通过减少搜索节点来缩小搜索范围。这需要使用一个基于堆的优先级队列，将搜索空间的节点按照与待查询节点的距离来进行排序。当搜索到的节点符合设定的约束条件，则记录到优先级队列中去，从而获取下一个候选节点的信息（包括该节点在当前树的位置和到待查询节点的距离）。当一个最邻近点被搜索到后，则从队列的队首删除一项，然后继续搜索包含最近邻节点的其他分支。
如图5.2所示，对于特征点数量达到10000、维度为5到25的数据检索中，按照BBF算法改进的搜索策略很大程度上提高了检索效率，而标准的K-D树搜索策略在数据维度达到10后其效率便明显下降了。

图Error! No text of specified style in document..2 BBF算法与K-D树的搜索时间代价
本书设定的约束条件是检查前200个最邻近候选节点，该算法在搜索速度提高了2个数量级的同时，平均只丢失5%的特征对，这对于一般的图像检索来说是可以容忍的。当距离非常相近的特征点需要进一步甄别的时候，BBF算法的搜效率会受到制约，但是本书剔除了与最近邻点和次近邻点距离比值大于0.8的特征对，这就基本上避免了这一困境。
3 基于霍夫变换的目标检测
一幅图像往往可以提取出超过2000个局部特征，而这些局部特征很可能来自场景中的多个物体或背景。如何从这些特征中寻找到只属于待识别目标的局部特征子集，这是进行目标匹配识别所必须解决的问题。霍夫变换（Hough Transform）为此提供了一条高效的途径。
基本的霍夫变换最初是用来进行直线检测的，而广义霍夫变换则可以在所需检测的曲线或目标轮廓没有或不易用解析表达式时，利用表格来建立曲线或轮廓点与参考点间的关系，进而检测出目标Error! Reference source not found.。霍夫变换的基本思想是将原图像变换到参数空间，用大多数边界点满足某种参数形式来描述图像中的线，通过设置累加器进行累积，求得峰值对应的点所需要的信息。霍夫变换以其对局部缺损的不敏感，对随机噪声的鲁棒性以及适于并行处理等优良特性，备受图像处理、模式识别和计算机视觉领域学者的青睐。霍夫变换的突出优点就是可以将图像中较为困难的全局检测问题转换为参数空间中相对容易解决的局部峰值检测问题。
霍夫变换利用点线对偶性原理进行坐标变换，原理如图5.3所示，在直角坐标系下，利用公式（5-2）表示过点(x, y)的直线L0的方程：
（5-2）
其中，k0为斜率，b0为截距。将其变换为参数空间中过点(k0, b0)的直线方程：
（5-3）
可以看出，直线L0上的两个点(x1, y1)和(x2, y2)，在参数空间中表示为两条直线不同的直线L1和L2，而它们在参数空间中相交于(k0, b0)点。也就是说，原图像空间中同一条直线上的不同点在参数空间中被变换为一组相交于同一点的直线。

图Error! No text of specified style in document..3 直线检测中的霍夫变换
使用公式（5-2）表示一条直线带来的一个问题是，当直线接近垂直时，直线的斜率接近无限大。解决这一难点的一种方法是使用极坐标方程来表示直线：
（5-4）
其中为原点到直线的距离（即原点到直线的垂直线的长度），确定了直线的方向（即原点到直线的垂直线与x轴方向的夹角）。如果对位于同一直线上的n个点进行霍夫变换，则原图像空间中的这n个点在参数空间中对应得到n条正弦曲线，并且这些曲线相交于同一点了，若能确定参数空间中的P0点（局部最大值），也就实现了直线的检测。
本书对目标姿态建立一个参数空间，将目标的2D坐标、尺度、方向参数等坐标轴按照一定的步长划分为若干等份；然后将所有匹配的特征点向这个参数空间投票；对参数空间每个点的投票累加值进行分析，累加值大的点所对应的目标姿态有更高的概率出现在图像中。在实际应用中，对于参数空间坐标轴步长，一般2D坐标为训练集中目标最大尺寸的0.25倍，尺度因子为2，方向参数为。累加值和预设的阈值进行比较，当大于阈值时，则判定该点所对应的目标姿态存在于图像中。
在图5.4中，左图所示的两个目标——玩具火车和玩具青蛙，由于其他物体（包和箱子等）的存在，在中间的图像里都产生了局部遮挡，而采用上述的目标匹配方法都可以将这些目标识别出来，识别效果图如右图所示。大的矩形框中是识别出的目标，小的矩形框代表识别所用到的局部特征。

图Error! No text of specified style in document..4 局部遮挡目标检测（来源: Lowe, 2004）