★ FEATURED ARTICLE 1.J-Linkage算法的简介J-Linkage算法是一种自底向上的一种层次聚类的算法当然还有很多评价每个聚类距离的算法例如simple linkage, complete linkage and average linkage这些感兴趣的小伙伴可以自己查阅相关的资料。原文题目’Robust Multiple Structures Estimation with J-linkage’。以论文中的例子说明算法要达到的效果这里就以三维点的平面拟合进行举例分析我们的目标是要拟合出三维空间点对应的三个平面能实现该功能的算法也有不少这里介绍下J-linkage算法是如何实现的介绍J-linkage算法之前需要了解Ransac算法的原理具体内容可参考LZ的另外一篇文章http://blog.csdn.net/felaim/article/details/76422803或者这一篇http://grunt1223.iteye.com/blog/961063。其实思想也很简单ransac算法是要找到样本数据中满足某种模型的最大数据集合。这里的最大是指集合的数据个数。J-linkage算法是要找到多个数据集合以上图为例目的是要找到3个数据集合每个数据集合能拟合出一个平面。首先提出一个定义Jaccard distance给定两个集合A和Bthe jaccard distance是dJ(A,B)∣A⋃B∣−∣A⋂B∣∣A⋃B∣d_J(A, B) \frac {|A\bigcup B|-|A\bigcap B|}{|A\bigcup B|}dJ(A,B)∣A⋃B∣∣A⋃B∣−∣A⋂B∣jaccard distance评价了两个集合的重叠程度范围是从0同一个集合到1完全独立的集合这里截止的值被设为1这也就意味着算法把有重叠部分的preference setPS link起来。所以聚类的点有以下两个性质1对于每个聚类至少存在一个模型包含所有在PS的点i.e.,一个可以拟合所有数据的模型2一个模型不可能存在于PS中两个不同聚类的点集否则他们就会被link。每个聚类的点定义至少一个模型如果更多的模型拟合一个聚类的所有点那么他们肯定很相似。最后利用最小二乘算法估计每个聚类的模型。异常点会融合成比较小的聚类通常情况下会根据不同的应用可以设置不同的阈值。如果异常点所占的百分比是已知的或者是可以估计的正如RANSAC假设的一样我们是可以拒绝所有最小的聚类直到把异常点全部剔除。J-linkage算法的流程是输入数据点的集合每个点被表示成它的preference setPS输出属于相同模型的点集的聚类1把每个点看成是自己的一个聚类2把PS的一个聚类定义为其点的PS的交集3在所有的聚类中在各自PS中选择两个Jaccard distance最小的聚类计算其模型参数4合并这两个模型并重新计算得到最小Jaccard距离的两模型(5)重复3~4过程知道最小Jaccard距离为1为止。算法最终得到若干个分类有些分类属于弱分类就是说集合内的样本个数太少不能算是一类本例只要取前3个分类结果即可这3个分类结果的样本数量也是最多的3类。2.具体算法的实现理解程序首先输入的是三维点云的坐标XYZ将三维数据可视化如下图所示% Generate an exponential Cumulative distribution function(cdf)% needed to generate a non-uniform sampling[nearPtsTab]calcNearPtsTab(CastelVecchio,exp,sigmaExp);% Generate Hypothesis(random sampling)[totm,totd]generateHypothesis(CastelVecchio,getfn_plane,distfn_plane,degenfn_plane,3,4,100,numberOfTrials,nearPtsTab);% Perform J-Linkage clusterization[T,Z,Y,totdbin]clusterPoints(totd,inliersThreshold);因为主要考虑的J-Linkage的算法所以直接说最后的那一行代码吧function[T,Z,Y,totdbin]clusterPoints(totd,inliersThreshold)#先按照设定的阈值把PS映射到只有{01}的空间集合中 corMfind(totdinliersThreshold);totdbinfalse(size(totd));totdbin(corM)true;#计算jaccard distance YpDistJaccard(totdbin);#对每个聚类进行连接相交 ZlinkageIntersect(Y,totdbin);#最后进行聚类 Tcluster(Z,cutoff,1-(1/(size(totdbin,1)))eps,criterion,distance);最后就得到了博客一开始放的那张效果图先说这么多啦O(∩_∩)O哈哈~参考文献[1]Toldo R, Fusiello A. Robust Multiple Structures Estimation with J-Linkage[C]// European Conference on Computer Vision. Springer-Verlag, 2008:537-547.
阅读完成 · 觉得有帮助？
)
