请选择 进入手机版 | 继续访问电脑版
设为首页收藏本站

 找回密码
 立即注册

QQ登录

只需一步,快速开始

Fuzzy Correspondences的相关整理

热度 2已有 3899 次阅读2014-11-25 14:54 |个人分类:论文感想总结|系统分类:模式识别与机器学习| FuzzyCorr, 3D检索, PaperReading

Exploring Collections of 3D Models using Fuzzy Correspondences
http://www.cs.princeton.edu/~vk/projects/CorrsFuzzy/
运行结果:

以下是我的一些感想:
  • 仔细看了论文的细节后感觉还有很多地方很模糊,要进一步根据代码解决我的疑惑吧,其中的数学虽然知道怎么做,但为什么这么做不是很明白。其中可能也有错误的理解,希望指正~
  • 接触了很多新的概念(太多知识欠缺):谱嵌入、流形学习、球谐函数、特征值和特征向量的意义和用途(大学时只知道算)。
  • 要学的东西太多了,有点不知道从何下手。
论文主要的目标是:重建模糊对应函数f(pi,pj)
1.     一个shape采样K个离散的点;N个shape的f函数为一个NK*NK的矩阵
        离散样本点pi:1)随机在shape上取一点
                              2)迭代增加离前一个点最远的点,直到取到点数为K=128【Eldar et al. 1997】
                              3)只计算这K个点的f(pi,pj),其余用最近邻插补
2.     生成一个初始对准图G0(S,A0);S为shape,A0为edge(只连接相似度高可自动匹配的shape;每对shape间多通路)
         G(S,A0):1)G0连接所有的shape
                      2)计算每个shape的球谐函数spherical harmonics shape descriptor【GEDT function,Kazhdan et al.2003】
                            一个比如32*16的矩阵,其中行代表半径为1-32的球面,16分别为各个L2范数(旋转不变性)
                      3)令参数间的L2距离为edge weight,weight越小,相似度越高(参数越相近)
                      4)更新G0为最小生成树
                      5)对每个节点,选择3M个weight最小的edges为candidates
                      6)计算每个candidates的edge rank【Heath et al 2010】(对整个图的连通性的贡献性)
                      7)在G0中增加最高的ranking NM个edge(大约每个shapeM个edges);M=5
                      
3a.     外在对准shapes---仿射变形针对差异大的数据集
                    1)对于两个shape:Sk、Sl定义对准score:a(sk,sl,fai)
                    2)a=L*B;L为局部对准值,B为全局对准值;La(pi,pj)取决于pi与Sl经过T变形后的pj的欧氏距离;B为整体shape之间对准的程度

                       

                       

                        Diam(sl)=是Sl中所有点pj与Sk中一点pi的距离平均值,越大越模糊

                    3)初设假设4个主要成分的对准,然后用ICP(迭代最近点)优化,选取使全局对准值最大的那个变形T
3b.      本征对准---混合共形保角映射blended comformal maps针对平滑、几乎等距、流形表面更有效(另一篇论文)
                    1)
                      
4.     嵌入对应矩阵C:NK*NK
          1)用对准score:a,进行行归一化后形成C*(C是N*N?)
               
          2)取该矩阵的K个特征向量,用对角矩阵D归一化
               
          3)
               这是个线性变换,即一个NK*NK的矩阵,其中pi,pj在这个嵌入空间embedded space中的欧氏距离即为其的扩散距离diffusion distance
*一个变换可由一个矩阵乘法表示,一个空间坐标系也可以视为一个矩阵,这个坐标系可由矩阵所有特征向量表示,用图来表示,就是一个空间张开的各个坐标角度,这一组
向量可以完全表示一个矩阵表示的空间的特征,而他们的特征值就表示了各个角度上的能量(想成各个角度伸出的长短,越长的轴越能代表这个空间,显性)
Spectral theorem核心:一个线性变换(用矩阵乘法表示)可表示为它的所有的特征向量的一个线性组合,其中的线性系数为一个向量对应的特征值。
5.     计算模糊对应函数
          1)15%个最近点中最远点与pi的距离
          2)所有pi,pj之间距离大于上面值得归零,只考虑最大的K个特征向量(快速计算近似最近邻域flann)
6.     优化对准图
          1)删除噪声样本根据fuzzy correspondeces fi和每一条边的consistency score
          
          选择可以产生更加一致consistency score的变形参数,如果一条边低于其两端点最好score的30%,那么这连个shape相似度太低,可删除
          2)增加对应数量的边
               对应那些被长路径分离的shapes,把所有边中,图中shapes间路径大于3中最短的路径加入candidate set,然后用integrated fuzzy corresponece value IFC(Sk,Sl),选3NEadd个最高的ranking边,然后又用edge rank对他们排序,选择最高的NEadd个边加入到图中。
          3)以上过程不断迭代,优化fuzzy correspondences 函数
               
------------------------------------------------------------------------------------------------------------------------
觉得对我的理解有帮助的一段话:
 Spectral Clustering 的几个优点:
1)只需要数据的相似度矩阵就可以了。这个是显然的,因为 Spectral Clustering 所需要的所有信息都包含在W中。不过一般W并不总是等于最初的相似度矩阵——回忆一下, 是我们构造出来的 Graph 的邻接矩阵表示,通常我们在构造 Graph 的时候为了方便进行聚类,更加强到“局部”的连通性,亦即主要考虑把相似的点连接在一起,比如,我们设置一个阈值,如果两个点的相似度小于这个阈值,就把他们看作是不连接的。另一种构造 Graph 的方法是将 n 个与节点最相似的点与其连接起来。
2)抓住了主要矛盾,忽略了次要的东西,Performance 比传统的 K-means 要好。实际上 Spectral Clustering 是在用特征向量的元素来表示原来的数据,并在这种“更好的表示形式”上进行 K-means 。
3)计算复杂度比 K-means 要小。这个在高维数据上表现尤为明显。例如文本数据,通常排列起来是维度非常高(比如,几千或者几万)的稀疏矩阵,对稀疏矩阵求特征值和特征向量有很高效的办法,得到的结果是一些 k 维的向量(通常 k 不会很大),在这些低维的数据上做 K-means 运算量非常小。但是对于原始数据直接做 K-means 的话,虽然最初的数据是稀疏矩阵,但是 K-means 中有一个求 Centroid 的运算,就是求一个平均值:许多稀疏的向量的平均值求出来并不一定还是稀疏向量,事实上,在文本数据里,很多情况下求出来的 Centroid 向量是非常稠密,这时再计算向量之间的距离的时候,运算量就变得非常大,直接导致普通的 K-means 巨慢无比,而 Spectral Clustering 等工序更多的算法则迅速得多的结果。

路过

鸡蛋
2

鲜花

握手

雷人

刚表态过的朋友 (2 人)

发表评论 评论 (1 个评论)

回复 okwhut 2014-12-13 08:21
[em:2:

facelist doodle 涂鸦板

您需要登录后才可以评论 登录 | 立即注册

Archiver|手机版|视觉计算研究论坛 ( 京ICP备09019267号 )  

GMT+8, 2017-11-19 16:49 , Processed in 0.198559 second(s), 30 queries , Gzip On.

Powered by SIGVC.org

© 2012- , Beijing, China

回顶部