计算机视觉
图像处理

图形处理(七)基于热传播的测地距离计算-Siggraph 2013

这里要跟大家分享的是2013年Siggraph上面的一篇paper,名为 《Geodesics in Heat:A New Approach to Computing Distance Based on Heat Flow》,这篇paper没有提供源代码,但是因为算法的 思想相当新颖,如果你之前有研究过其它的测地三角网格曲面上的测地距离算法,那么看到这篇paper后,你会非常的激动,觉得这个算法相当神奇,网格曲面 上测地距离的计算方法又有了新的突破。因为看到这篇paper非常激动,以至于我兴奋得马上去把代码写了一遍,虽然测地距离的计算方法,对于我来说没什么 用,但它的想法,它的思想值得我们学习。

《Geodesics in Heat:A New Approach to Computing Distance Based on Heat Flow》 算法主要是通过向量场的方法,通过求解热流,求解泊松方程。这篇paper我觉得应该把它归类为向量场类型的文献,曲面上向量场的应用非常广泛,可以用于 网格优化重建、参数化纹理映射、网格变形……等,如今这篇paper又让我明白向量场也可以求解测地距离。通过热量传播的方法,去求解测地距离,真是大牛 啊

一、理论知识

在很早之前对于测地距离,大牛们就推导出了测地距离的求解归结为求解eikonal equation(程函方程):

且满足边界约束条件为:

上面符号Φ就是测地距离。

也就是不管是欧式空间还是曲面空间,其测地距离的梯度模长恒等于1,然后边界条件:源点的测地距离值为0。

因 此很多大牛,都是针对上面的程函方程的求解进行研究,然而所提出的算法都是非线性的方法,因为上面的方程就是非线性方程,在网格曲面上计算量非常大。而这 篇paper作者的真正贡献在于把非线性问题转换为线性问题,到最后只需要求解一个泊松方程就可以了。开始这个算法之前,建议先看一下《Mesh Editing with Poisson-Based Gradient Field Manipulation》这篇利用泊松方程进行三角网格模型编辑,其实这篇paper的思想应该是借用了《Poisson Image Editing》,如果你已经很熟悉《Mesh Editing with Poisson-Based Gradient Field Manipulation》那么看这篇paper将事半功倍。

1、时间离散化,热传播方程时间离散化为:

2、空间离散化,在网格曲面上,离散的拉普拉斯坐标定义为:

Ai表示三角面片的面积的三份之一,j表示顶点i的邻接顶点。对于有V个顶点的网格模型,我们可以列出上面的V个方程,写出矩阵形式为:

其中,Lc为拉普拉矩阵,A为包含每个顶点面积的对角矩阵。

代入公式(3)可得:

在网格曲面上,对于一个给定的三角面片平面上,标量场的梯度计算公式如下:



Af表示三角形的面积,N表示三角面片的法矢,ui就是标量场,我们可以把网格曲面每个顶点的测地距离看成是一个标量场。

顶点i的散度离散形式为:

懒得多说废话了,总之到最后归结为求解如下方程:


其中b我们需要先通过求解标量场u,然后根据散度的计算公式,计算出顶点测地距离的散度。

二、算法实现

算法总流程:

示意图:

其中,Φ就是我们要求的测地距离,t是一个无穷小的数,趋近于0

算法具体实现,先说明一下,我下面自己写的代码很乱,懒得整理,因为我只是为了学习:

1、求解u

根据公式:

求解u,因此我们需要先算出A,t,Lc,还有δ。接着我将逐渐讲解着四个参数的求解:

a、时间t计算:见文献3.2.4,时间理论上来说是一个非常小的数,文中作者给出了其合适的值为:网格平均边长的平方

代码实现如下:

  1. //计算时间步长,文献中时间步长为:网格模型的边长平均,然后平方
  2. void CHeatGeodesics::Set_Time()
  3. {
  4.     m_BaseMesh->need_edge();
  5.     int en=m_BaseMesh->m_edges.size();
  6.     float sumlength=0;
  7.     for (int i=0;i<en;i++)
  8.     {
  9.         sumlength+=m_BaseMesh->m_edges[i].length();
  10.     }
  11.     sumlength=sumlength/en;//边长的平均长度
  12.     sumlength=sumlength*sumlength;
  13.     m_Time_Step=sumlength;
  14. }

b、面积对角矩阵A的计算:

  1. //计算Geodesics in Heat 文献中的包含顶点Vi的面积矩阵
  2. void CHeatGeodesics::Get_Matrix_A_areas()
  3. {
  4.     m_BaseMesh->need_adjacentfaces();
  5.     gsi::SparseMatrix &A=m_A_areas;
  6.     A.Resize(m_NumberV,m_NumberV);
  7.     //计算每个三角面片的面积
  8.     int fn=m_BaseMesh->faces.size();
  9.     vector<float>&face_area=m_Faces_Area;
  10.     face_area.resize(fn);
  11.     for (int i=0;i<fn;i++)
  12.     {
  13.         TriMesh::Face &f=m_BaseMesh->faces[i];
  14.         vec vij=m_BaseMesh->vertices[f[1]]-m_BaseMesh->vertices[f[0]];
  15.         vec vik=m_BaseMesh->vertices[f[2]]-m_BaseMesh->vertices[f[0]];
  16.         float areaf=0.5*len(vij CROSS vik);
  17.         face_area[i]=areaf;
  18.     }
  19.     //计算拉普拉斯算子中每个顶点所占据的面积,即邻接三角面片面积总和的三分之一
  20.     for (int i=0;i<m_NumberV;i++)
  21.     {
  22.         vector<int>&af=m_BaseMesh->adjacentfaces[i];
  23.         int n_af=af.size();
  24.         float sumarea=0.0;
  25.         for (int j=0;j<n_af;j++)
  26.         {
  27.             sumarea+=face_area[af[j]];
  28.         }
  29.         //包含顶点的面积为:邻接三角面片面积总和的三分之一
  30.         sumarea=sumarea/3.0;
  31.         A(i,i) =sumarea;
  32.     }
  33. }

C、拉普拉斯矩阵Lc计算:

  1. //计算Geodesics in Heat 文献中的Lc矩阵,即拉普拉斯算子
  2. void CHeatGeodesics::Get_Matrix_Lc()
  3. {
  4.     Ls.resize(m_NumberV,m_NumberV);
  5.     int m_nEdges=10000 ;
  6.     Ls.reserve(m_nEdges+m_NumberV);
  7.     for (int i = 0;i<m_NumberV;++i)
  8.     {
  9.         VProperty & vi = m_vertices[i];
  10.         int nNbrs = vi.VNeighbors.size();
  11.         for (int k = 0;k<nNbrs;++k)
  12.         {
  13.             Ls.insert(i, vi.VNeighbors[k]) = vi.VNeiWeight[k];
  14.         }
  15.         Ls.insert(i, i) = -vi.VSumWeight;
  16.     }
  17.     Ls.finalize();
  18.     gsi::SparseMatrix &A=m_Lc;
  19.     A.Resize(m_NumberV,m_NumberV);
  20.     for(int k=0;k<m_NumberV;++k)
  21.     {
  22.         for ( SparseMatrixType::InnerIterator it(Ls,k); it; ++it)
  23.         {
  24.             A.Set( it.row(), it.col(), it.value() );
  25.         }
  26.     }
  27. }

邻接顶点的余切cot权重计算:

  1. //邻接顶点的余切权重计算
  2. void CHeatGeodesics::CotangentWeights(TriMesh*TMesh,int vIndex,vector<float>&vweight,float &WeightSum,bool bNormalize)//计算一阶邻近点的各自cottan权重
  3. {
  4.     int NeighborNumber=TMesh->neighbors[vIndex].size();
  5.     vweight.resize(NeighborNumber);
  6.     WeightSum=0;
  7.     vector<int>&NeiV=TMesh->neighbors[vIndex];
  8.     for (int i=0;i<NeighborNumber;i++)
  9.     {
  10.         int j_nei=NeiV[i];
  11.         vector<int>tempnei;
  12.         Co_neighbor(TMesh,vIndex,j_nei,tempnei);
  13.         float cotsum=0.0;
  14.         for (int j=0;j<tempnei.size();j++)
  15.         {
  16.             vec vivo=TMesh->vertices[vIndex]-TMesh->vertices[tempnei[j]];
  17.             vec vjvo=TMesh->vertices[j_nei]-TMesh->vertices[tempnei[j]];
  18.             float dotvector=vivo DOT vjvo;
  19.             dotvector=dotvector/sqrt(len2(vivo)*len2(vjvo)-dotvector*dotvector);
  20.             cotsum+=dotvector;
  21.         }
  22.         vweight[i]=cotsum/2.0;
  23.         WeightSum+=vweight[i];
  24.     }
  25.     if ( bNormalize )
  26.     {
  27.         for (int k=0;k<NeighborNumber;++k)
  28.         {
  29.             vweight[k]/=WeightSum;
  30.         }
  31.         WeightSum=1.0;
  32.     }
  33. }
  34. void CHeatGeodesics:: UniformWeights(TriMesh*TMesh,int vIndex,vector<float>&vweight,float &WeightSum,bool bNormalize)
  35. {
  36.     int NeighborNumber=TMesh->neighbors[vIndex].size();
  37.     vweight.resize(NeighborNumber);
  38.     WeightSum = 0;
  39.     for (int j = 0; j <NeighborNumber; ++j )
  40.     {
  41.         vweight[j] = 1;
  42.         WeightSum += vweight[j];
  43.     }
  44.     if ( bNormalize )
  45.     {
  46.         for ( int k = 0; k < NeighborNumber; ++k )
  47.             vweight[k] /= WeightSum;
  48.         WeightSum=1.0;
  49.     }
  50. }
  51. //获取两顶点的共同邻接顶点
  52. void CHeatGeodesics::Co_neighbor(TriMesh *Tmesh,int u_id,int v_id,vector<int>&co_neiv)
  53. {
  54.     Tmesh->need_adjacentedges();
  55.     vector<int>&u_id_ae=Tmesh->adjancetedge[u_id];
  56.     int en=u_id_ae.size();
  57.     Tedge Co_Edge;
  58.     for (int i=0;i<en;i++)
  59.     {
  60.         Tedge &ae=Tmesh->m_edges[u_id_ae[i]];
  61.         int opsi=ae.opposite_vertex(u_id);
  62.         if (opsi==v_id)
  63.         {
  64.             Co_Edge=ae;
  65.             break;
  66.         }
  67.     }
  68.     for (int i=0;i<Co_Edge.m_adjacent_faces.size();i++)
  69.     {
  70.         TriMesh::Face af=Co_Edge.m_adjacent_faces[i];
  71.         for (int j=0;j<3;j++)
  72.         {
  73.             if((af[j]!=u_id)&&(af[j]!=v_id))
  74.             {
  75.                 co_neiv.push_back(af[j]);
  76.             }
  77.         }
  78.     }
  79. }

最后求解方程组,就可以把u求出来了。

2、求解三角网格曲面的热量场▽u (Heat flow):

这一步直接根据公式:

求解就可以了。然后对▽u进行归一化,并取热量场的反方向,即求测地距离的梯度场:

  1. for (int i=0;i<fn;i++)
  2. {
  3.     TriMesh::Face &f=m_BaseMesh->faces[i];
  4.     for (int j=0;j<3;j++)
  5.     {
  6.         vec ei=m_BaseMesh->vertices[f[(j+2)%3]]-m_BaseMesh->vertices[f[(j+1)%3]];
  7.         vec FNormal=normalize(m_BaseMesh->FaceNormal[i]);
  8.         vec gradient=float(m_vertices[f[j]].VU*0.5/m_Faces_Area[i])*(FNormal CROSS ei);
  9.         FGradient[i]=FGradient[i]+gradient;
  10.     }
  11.     normalize(FGradient[i]);//文献的重要两步 即梯度单位化和梯度反向
  12.     FGradient[i]=float(-1.0)*FGradient[i];
  13.     //length0[i]=len(FGradient[i]);
  14. }

3、对测地距离的梯度场X,求取散度。根据公式:

求解测地距离标量场梯度场的散度。

  1. //计算顶点的散度
  2. for (int i=0;i<vn;i++)
  3. {
  4.     vector<int>&adjacentface=m_BaseMesh->adjacentfaces[i];
  5.     for (int j=0;j<adjacentface.size();j++)
  6.     {
  7.         TriMesh::Face &f=m_BaseMesh->faces[adjacentface[j]];
  8.         for (int k=0;k<3;k++)
  9.         {
  10.             if (f[k]==i)
  11.             {
  12.                 vec ei=m_BaseMesh->vertices[f[(k+2)%3]]-m_BaseMesh->vertices[f[(k+1)%3]];
  13.                 /*vec gradient=float(0.5/m_Faces_Area[adjacentface[j]])*(m_BaseMesh->FaceNormal[adjacentface[j]] CROSS ei);
  14.                 //计算散度
  15.                 m_vertices[i].VDivergence+=(FGradient[adjacentface[j]] DOT gradient)*m_Faces_Area[adjacentface[j]];*/
  16.                 vec e1=m_BaseMesh->vertices[f[(k+1)%3]]-m_BaseMesh->vertices[f[k]];
  17.                 vec e2=m_BaseMesh->vertices[f[(k+2)%3]]-m_BaseMesh->vertices[f[k]];
  18.                 float cot_angle1=Cot_angle(e2,ei);
  19.                 float cot_angle2=Cot_angle(float(-1.0)*e1,ei);
  20.             m_vertices[i].VDivergence+=0.5*(cot_angle1*(e1 DOT FGradient[adjacentface[j]])+cot_angle2*(e2 DOT FGradient[adjacentface[j]]));
  21.                 break;
  22.             }
  23.         }
  24.     }
  25. }

4、最后求解通过求解泊松方程,求取网格曲面上每个顶点的测地距离。

  1. gsi::SparseLinearSystem *pSystemPos2 = new gsi::SparseLinearSystem();
  2.     gsi::Solver_TAUCS * pSolverPos2 = new gsi::Solver_TAUCS(pSystemPos2);
  3.     pSystemPos2->Resize(m_NumberV, m_NumberV);
  4.     pSystemPos2->ResizeRHS(1);
  5.     //由于以下解方程组使用Solver_TAUCS::TAUCS_LLT ,即半正定矩阵模式
  6.     m_Lc.Multiply(-1.0);
  7.     m_Lc(0,0) =m_Lc(0,0) +10;
  8.     pSystemPos2->SetMatrix(m_Lc);
  9.     if ( ! pSystemPos2->Matrix().IsSymmetric() )assert(0);
  10.     pSolverPos2->OnMatrixChanged();
  11.     pSolverPos2->SetStoreFactorization(true);
  12.     pSolverPos2->SetSolverMode( gsi::Solver_TAUCS::TAUCS_LLT );
  13.     pSolverPos2->SetOrderingMode( gsi::Solver_TAUCS::TAUCS_METIS );
  14.     gsi::Vector pRHSPos2 ;
  15.     pRHSPos2.Resize(m_NumberV);
  16.     // 右边项约束添加
  17.     for (int i=0;i<m_NumberV;i++)
  18.     {
  19.         pRHSPos2[i]=float(-1.0)*m_vertices[i].VDivergence;
  20.     }
  21.      //初始条件为方程热源的测地距离为0
  22.     pRHSPos2[0]=pRHSPos2[0]+10;
  23.     pSystemPos2->SetRHS(0, pRHSPos2);
  24.     bool boksoveLs2=pSolverPos2->Solve();
  25.     if (!boksoveLs2)assert(0);
  26.     m_GeodesicsDistance.resize(m_NumberV);
  27.     for ( int i=0;i<m_NumberV;++i)
  28.     {
  29.        m_GeodesicsDistance[i]=(float)pSystemPos2->GetSolution(i,0);
  30.     }

可以说到了这里算法已经结束了,当然paper后面还有后续的处理,比如距离光顺,还有边界条件的等问题。但都属于后处理,你如果要实现跟paper一模一样的效果,还是得好好看一看后面的边界条件问题。

边界条件对于结果的影响还是蛮大的。

OK,做一下简单的总结:算法整个过程就说白了就是求解一个泊松方程,说的更白一点,就是求解一个大型的方程组AX=b,因此我们的目标就是先算出A、b,其中对于一个给定的网格曲面模型来说,A就是拉普拉斯矩阵,是固定的。b的求解就是整个算法成功的关键。

参考文献:

1、《Geodesics in Heat:A New Approach to Computing Distance Based on Heat Flow》

2、《Mesh Editing with Poisson-Based Gradient Field Manipulation》

3、《Poisson Image Editing》

转载注明来源:CV视觉网 » 图形处理(七)基于热传播的测地距离计算-Siggraph 2013

分享到:更多 ()
扫描二维码,给作者 打赏
pay_weixinpay_weixin

请选择你看完该文章的感受:

0不错 0超赞 0无聊 0扯淡 0不解 0路过

评论 2

评论前必须登录!