Topologically-Robust 3D Shape Matching Based on Diffusion Geometry and Seed Growing

CVPR 2011
Avinash Sharma, Radu Horaud and Jan Cech Edmond Boyer
PERCEPTION Team, INRIA - Grenoble Rhone-Alpes


Abstract

Algorithm

Video

Paper

Results

Data

Code



Abstract

3D Shape matching is an important problem in computer vision. One of the major difficulties in finding dense correspondences between 3D shapes is related to the topological discrepancies that often arise due to complex kinematic motions. In this paper we propose a shape matching method that is robust to such changes in topology. The algorithm starts from a sparse set of seed matches and outputs dense matching. We propose to use a shape descriptor based on properties of the heat-kernel and which provides an intrinsic scale-space representation. This descriptor incorporates (i) heat-flow from already matched points and (ii) self-diffusion. At small scales the descriptor behaves locally and hence it is robust to global changes in topology. Therefore, it can be used to build a vertex-to-vertex matching score conditioned by an initial correspondence set. This score is then used to iteratively add new correspondences based on a novel seed-growing method that iteratively propagates the seed correspondences to nearby vertices. The matching is farther densified via an EM-like method that explores the congruency between the two shape embeddings. Our method is compared with two recently proposed algorithms and we show that we can deal with substantial topological differences between the two shapes.

Algorithm

The main contribution of this paper is a dense 3D shape matching method that is robust to topological changes in the shape. The method starts from sparse one-to-one correspondences and produces as output dense correspondences. We analyze a recently proposed shape-matching descriptor that is based on the heat-kernel matrix that may well be viewed as a shape operator. The eigenvalues and eigen- vectors of this matrix/operator provide a scale-space intrinsic shape representation. The descriptor incorporates both (i) heat flows from the already matched points and (ii) self diffusion. At small scales this descriptor is fairly local and hence it is robust to changes in topology.
Figure: Visualization of heat diffusion on 3D shapes. The color at each vertex of 3D shape encodes the value of the heat kernel at scale t, where the blue dot on the torso represents point heat source. (a): For small values of t, the heat diffusion map is very similar on both shapes and it is not affected by their topological differences (hand merging with body). (b): For large values of t, the behavior of the diffusion process drasti- cally depends on the shape's topology.
It can therefore be used to build a matching score between a point on the first shape and a point of the second shape conditioned by the initial correspondences. This score is then used to iteratively add new point-to-point correspondences based on a novel seed-growing algorithm that propagates current correspondences to nearby ones.
The final set of dense correspondences is obtained via a point registration method that uses a variant of the EM algorithm.

Video

Paper

Please download the pdf version of paper at :

Topologically-Robust 3D Shape Matching Based on Diffusion Geometry and Seed Growing

or here

Cite using the following reference: 

 
@InProceedings\{SHCB11,
  author       = "Sharma, Avinash and Horaud, Radu P. and Cech, Jan and Boyer, Edmond",
  title        = "Topologically-Robust 3D Shape Matching Based on Diffusion Geometry and Seed Growing",
  booktitle    = "Proceeding of the IEEE Conference on Computer Vision and Pattern Recognition",
  year         = "2011",
  address      = "Colorado Springs, CO",
  url          = "http://perception.inrialpes.fr/Publications/2011/SHCB11"
}

The interested readers may also be interested in the following related publications:

Learning Shape Segmentation Using Constrained Spectral Clustering and Probabilistic Label Transfer 
 
@InProceedings{SVH10,
  author       = "Sharma, Avinash and von Lavante, Etienne and Horaud, Radu P.",
  title        = "Learning Shape Segmentation Using Constrained Spectral Clustering and Probabilistic Label Transfer",
  booktitle    = "Proceedings of the Eleventh European Conference on Computer Vision",
  series       = "LNCS",
  month        = "September",
  year         = "2010",
  editor       = "Kostas Daniilidis, Petros Maragos, Nikos Paragios",
  publisher    = "Springer",
  address      = "Heraklion, Greece",
  url          = "http://perception.inrialpes.fr/Publications/2010/SVH10"
}

Articulated Shape Matching Using Laplacian Eigenfunctions and Unsupervised Point Registration 

 
 @InProceedings{MHKCB08,
  author       = "Mateus, Diana and Horaud, Radu P. and Knossow, David and Cuzzolin, Fabio and Boyer, Edmond",
  title        = "Articulated Shape Matching Using Laplacian Eigenfunctions and Unsupervised Point Registration",
  booktitle    = "Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition",
  year         = "2008",
  url          = "http://perception.inrialpes.fr/Publications/2008/MHKCB08"
}

Rigid and Articulated Point Registration with Expectation Conditional Maximization 

 
@Article\{HFYDZ10,
  author       = "Horaud, Radu P. and Forbes, Florence and Yguel, Manuel and Dewaele, Guillaume and Zhang, Jian",
  title        = "Rigid and Articulated Point Registration with Expectation Conditional Maximization",
  journal      = "IEEE Transactions on Pattern Analysis and Machine Intelligence",
  year         = "2010",
  note         = "in press",
  url          = "http://perception.inrialpes.fr/Publications/2010/HFYDZ10"
}

Inexact Matching of Large and Sparse Graphs Using Laplacian Eigenvectors 

 
@InProceedings{KSMH09,
  author       = "Knossow, David and Sharma, Avinash and Mateus, Diana and Horaud, Radu P.",
  title        = "Inexact Matching of Large and Sparse Graphs Using Laplacian Eigenvectors",
  booktitle    = "Proceedings 7th Workshop on Graph-based Representations in Pattern Recognition",
  month        = "May",
  year         = "2009",
  publisher    = "Springer",
  address      = "Venice, Italy",
  url          = "http://perception.inrialpes.fr/Publications/2009/KSMH09"
}

Results

Topologically-robust dense shape matching

(a): Initial sparse matches; (b): Matches obtained with seed growing; (c): Final matching after EM.

Dense algorithm applied to other data.

Comparison with other methods.

Data

Code

  • Specmatch: A software package for Spectral Graph Matching.
  • Topologically-robust dense matching code is available on request.

Inquiries should be addressed to avinash DOT sharma AT inrialpes DOT fr

 

^^Top