|
摘要：从2D图像中估计出物体对象的几何模型一直是计算机视觉的重点研究领域，而多模型估计更是其中的关键所在。本文从技术原理、算法实现、估计效果及实际应用等多个角度，对Sequential RANSAC、MultiRANSAC、Residual Histogram Analysis、J-Linkage和Kernel Fitting等几种典型的多模型估计方案进行了综合分析与对比研究，指出了它们的优缺点和改进方向。 中国论文网 /8/view-6911466.htm 关键词：多模型估计 技术原理 算法流程 性能比较 中图分类号：TP13 文献标识码：A 文章编号：1007-9416（2015）05-0000-00 从2D图像中估计对象模型是计算机视觉的基本任务之一，正确拟合一个最佳模型，消除外点影响，是多模型估计的基本目标。目前有多重方法可用于多模型估计，但它们的数学原理、算法流程和实现效果各有千秋。 1 Sequential RANSAC Sequential RANSAC的本质是多次调用RANSAC过程，其算法框架如表1-1所示。 由表1-1可见，Sequential RANSAC的测试原理很直接，若某个模型被拒绝，则算法终止3。文献所提方案既没有测试步骤，也没有明确给定终止条件；而文献虽然也没确定可接受条件，但给出了终止条件，即当找到个模型后，算法终止。不难看出，Sequential RANSAC具有明显缺陷，若前期估计结果不理想必将降低后期估测的有效性。 造成这种现象的原因是由于RANSAC判断时采用的是最大化一致集。尽管一致集是模型验证的一种较好方法，但仅仅使用这一种准则则稍显不足。 例如有50个模型，不仅需要考察模型一致集大小，而且还要考虑一致集中的点是如何共享同一个模型的，这基于一个基本事实，即梯形数据中正确模型的一致集所含数据点比错误模型一致集所含数据点共享了更多的模型。这种不和谐特性在Sequential RANSAC中被进一步恶化。若初始模型选择是错误的，将导致后续模型估计的失效。 2 MultiRANSAC 文献指出Sequential RANSAC的缺陷来源于它的顺序执行，从而提出了一种并行执行的方案，即MultiRANSAC。MultiRANSAC搜索最好的个模型的集合，通过使用个极小样本模型反复更新这个模型的集合，使用一种融合技术归并一致集的集合。MultiRANSAC要求这个模型的一致集不相交，以确保得到个独立的模型。 每个梯形模型有两倍的数据点。如果有5个模型需要估计，可以通过选择其中两个模型来获得较大的一致集，从剩余的4个真实直线中只得到3个模型。而如果要求一致集不相交，则可完全避免。因为已经选择了估计最大的真实模型的两个模型中较大的那个，就无法再选择另一个与同一个真实模型相联系的那个模型，因为它与初始模型共享数据点，即一致集相交。一致集更新算法如表2-1所示。 UpdateCS的基本功能是用新的个一致集的集合，来更新当前个一致集的集合。MultiRANSAC的主体算法如表2-2所示。 MultiRANSAC显露了一致集导向方法的基本缺陷，即难以消除模型的二义性。因为MultiRANSAC和Sequential RANSAC都需要多个极小样本模型，每一个都不可避免地含有差异细微的参数，可能导致冗余模型。 MultiRANSAC和Sequential RANSAC为了避免这种现象，都要求一致集不相交。Sequential RANSAC是在找到每个模型后移除响应的内点，而MultiRANSAC是在函数中实现此目的。遗憾的是，真实模型不可能不相交，大量的点可能属于两个以上的真实模型。这就需要设计某种不相交度量方法，以从同一模型的两个具有不同参数的实例中辨别不同模型的相交性如果仅使用一致集，这是不可能实现的，因为不同的模型相交的点要比冗余模型相交的点多得多。这种不相交准则最终导致MultiRANSAC在梯形数据集中失效，再次表明了基于一致集的模型估计的不合理。 3 Residual Histogram Analysis 文献提出残值直方图分析法（Residual Histogram Analysis，RHA），避开了一致集方案的问题和数据集的先验知识的需求。它不是去搜索一个拥有大量一致集内点的模型，而是在残值直方图中根据峰值点来搜索健壮的模型。因为直方图中的模就对应于真实模型。RHA的基本原理是，计算每个模型与每个数据点之间的残值。对每个点计算关于所有模型的残值，经过平滑，得到该点的残值直方图。基于所有点找到模，再根据中位数，确定模型的数目。最后，从两个所选点的模仓中选出实际的模型。表3-1是RHA的算法框架。 可见，RHA不需要任何关于先验知识，但需要在含噪直方图中发现模。其关键步骤是模检测和模型估计。在对直方图进行模分析后，得到正确估计模型的有效点集，从其中选取波峰特异性最大的一个点，再任选一个点，由这两个点估计出正确的模型。 RHA算法除了构建了一种避开考虑一致集的模型估计途径外，还避免了使用数据集的先验知识。但是，RHA仍需要调谐参数。构造直方图的参数不同，将导致估计出不同数目的模型。文献指出，RHA寻找模的步骤是脆弱的。这意味着RHA与其他方法相比没有竞争力。 4 J-Linkage 文献提出的J-Linkage算法通过自底向上聚类数据点来来寻找模型，使用倾向集，虽然类似于一致集，但是颠倒了模型与数据点的角色。一个数据点的倾向集定义如下： J-Linkage不考察模型有哪些点与之匹配，而是考察一个数据点与哪些模型匹配。从而确定哪些数据点可能聚类在一起。如果有个极小样本集MSS，数据点可以描述为空间的维向量，称为概念空间。则对于模型，有下面的定义： 这种查看倾向集的方法可帮助理解下面的Kernel Fitting算法。表4-1是J-Linkage算法的基本流程。 上述算法使用了Jaccard距离。二个集合的Jaccard距离定义为： 显然，，且当重合时，为0；当不相交时，为1。当聚类操作终止后，每个类至少有一个模型估计了所有数据，而且，相当于真实模型的点位于最大类中，而外点位于较小的类中。这些类类似于一致集。较小的外点类被移除，或者通过一个预定义阈值，或者直接剔除较小类，直到剔除的点的数目等于预期的外点数。 显然，不同的采样策略将通过改变数据点的倾向集以及在概念空间的描述，来影响哪些点可能被聚类。J-Linkage不使用一致集，客服了RANSAC类方法的缺陷，但付出了聚类的代价，需要通过一致集阈值来辨别内点与外点。如果设置太小，将导致虚假模型。反之，若太大，又有可能排除真实模型。而且，其运行时间为，搜索空间太复杂。同时，J-Linkage要求一个聚类中的数据点至少有一个初选模型，将导致模型碎裂，即如果没有一个极小样本模型能正确估计真实模型，则真实模型可能被分化成多个分离的类。为此，文献都提出了Merging J-Linkage改良方案，给定数据点的两个类，计算出一个最佳估计的一个解，点到的误差均值为；归并误差最小的两个类，直到最小归并误差大于阈值。这将允许在某次采样中没有公共模型的点的聚类，但是，有公共模型的点被归并。不过，这种方法在处理平面之外的模型时具有很大局限性。 5 Kernel Fitting 文献提出的Kernel Fitting方案，既具有J-Linkage的执行效率，又像RHA一样不需要任何先验知识。Kernel Fitting有一个独特的优势，即仅依靠精密的数学技术。这种数学上的完善，使得Kernel Fitting不需要噪声比例、外点数量或模型数目等任何先验知识。 Kernel Fitting的核心是有序残值内核（Ordered Residual Kernel，ORK）。一个内核是一个对称函数，称为Mercer核，其与另一个函数配对。映射到一个特征空间。如果Mercer条件满足，则得到下式： 也就是说，不管的实际类型，完全应用来工作。设，则有： 因此，若已知个数据和个极小样本集，即可计算一个核矩阵。移除外点，得到一个简化的核矩阵。表5-1是ORK的基本框架。 虽然Kernel Fitting不需要任何先验知识，但仍然需要估计许多模型，需要步长以辨别内外点的阈值，且需要模型数目。 6结语 Sequential RANSAC是多模型估计的基准方法，对于大多数数据集，是快速有效的，而且在一致集空间消除模型二义性方面优于MultiRANSAC。J-Linkage对所有类型的数据集都有效，但设置聚类阈值很棘手，即如果阈值太小，出现虚假模型，如果太大，又会丢失模型，且时间复杂度为数据点数目的二次方。而Merging J-Linkage对于平面估计很高效，但在几何特征估计中易产生幻觉模型。MultiRANSAC需要一致集不相交假定，在平面检测情况下，劣于Merging J-Linkage。RHA虽然也有能力独立用于检测多模型，但在执行和性能上与其他算法相比没有竞争力。Kernel Fitting执行力强，且不需要数据集的任何先验知识，但也像J-Linkage一样，运行时间是数据点数目的二次方，实现起来很困难。 参考文献 [1] M. A. Fischler and R. C. Bolles. Random sample concensus：A paradigm for model fitting with applications to image analysis and automated cartography. Comm. of the ACM，24：381�C395， 1981 [2] R. O. Duda and P. E. Hart. Use of the hough transformation to detect lines and curves in pictures. Comm. of the ACM，15：11�C15， 1972. [3] Y. Kanazawa and H. Kawakami. Detection of planar regions with uncalibrated stereo using distributions of feature points. In Proc. British Machine Vision Conf.， pages 247-256， 2004. |
|
|
