A Physicist’s View on Partial 3D Shape Matching
A new algorithm is presented to compute nonrigid, possibly partial comparisons of shapes defined by unstructured triangulations of their surfaces. The algorithm takes as input a pair of surfaces with each surface given by a distinct and unrelated triangulation. Its goal is to define a possibly parti...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-07-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/16/7/346 |
| _version_ | 1797590619680407552 |
|---|---|
| author | Patrice Koehl Henri Orland |
| author_facet | Patrice Koehl Henri Orland |
| author_sort | Patrice Koehl |
| collection | DOAJ |
| description | A new algorithm is presented to compute nonrigid, possibly partial comparisons of shapes defined by unstructured triangulations of their surfaces. The algorithm takes as input a pair of surfaces with each surface given by a distinct and unrelated triangulation. Its goal is to define a possibly partial correspondence between the vertices of the two triangulations, with a cost associated with this correspondence that can serve as a measure of the similarity of the two shapes. To find this correspondence, the vertices in each triangulation are characterized by a signature vector of features. We tested both the LD-SIFT signatures, based on the concept of spin images, and the wave kernel signatures obtained by solving the Shrödinger equation on the triangulation. A cost matrix <i>C</i> is constructed such that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>C</mi><mo>(</mo><mi>k</mi><mo>,</mo><mi>l</mi><mo>)</mo></mrow></semantics></math></inline-formula> is the norm of the difference of the signature vectors of vertices <i>k</i> and <i>l</i>. The correspondence between the triangulations is then computed as the transport plan that solves the optimal transport or optimal partial transport problem between their sets of vertices. We use a statistical physics approach to solve these problems. The presentation of the proposed algorithm is complemented with examples that illustrate its effectiveness and manageable computing cost. |
| first_indexed | 2024-03-11T01:23:04Z |
| format | Article |
| id | doaj.art-f1b75d790f1d4b72a886f8bedc358da2 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-11T01:23:04Z |
| publishDate | 2023-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-f1b75d790f1d4b72a886f8bedc358da22023-11-18T17:59:21ZengMDPI AGAlgorithms1999-48932023-07-0116734610.3390/a16070346A Physicist’s View on Partial 3D Shape MatchingPatrice Koehl0Henri Orland1Department of Computer Science, University of California, Davis, CA 95616, USAInstitut de Physique Théorique, CEA, CNRS, Université Paris-Saclay, 91191 Gif-sur-Yvette, FranceA new algorithm is presented to compute nonrigid, possibly partial comparisons of shapes defined by unstructured triangulations of their surfaces. The algorithm takes as input a pair of surfaces with each surface given by a distinct and unrelated triangulation. Its goal is to define a possibly partial correspondence between the vertices of the two triangulations, with a cost associated with this correspondence that can serve as a measure of the similarity of the two shapes. To find this correspondence, the vertices in each triangulation are characterized by a signature vector of features. We tested both the LD-SIFT signatures, based on the concept of spin images, and the wave kernel signatures obtained by solving the Shrödinger equation on the triangulation. A cost matrix <i>C</i> is constructed such that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>C</mi><mo>(</mo><mi>k</mi><mo>,</mo><mi>l</mi><mo>)</mo></mrow></semantics></math></inline-formula> is the norm of the difference of the signature vectors of vertices <i>k</i> and <i>l</i>. The correspondence between the triangulations is then computed as the transport plan that solves the optimal transport or optimal partial transport problem between their sets of vertices. We use a statistical physics approach to solve these problems. The presentation of the proposed algorithm is complemented with examples that illustrate its effectiveness and manageable computing cost.https://www.mdpi.com/1999-4893/16/7/346optimal transportshape matchingstatistical physics |
| spellingShingle | Patrice Koehl Henri Orland A Physicist’s View on Partial 3D Shape Matching Algorithms optimal transport shape matching statistical physics |
| title | A Physicist’s View on Partial 3D Shape Matching |
| title_full | A Physicist’s View on Partial 3D Shape Matching |
| title_fullStr | A Physicist’s View on Partial 3D Shape Matching |
| title_full_unstemmed | A Physicist’s View on Partial 3D Shape Matching |
| title_short | A Physicist’s View on Partial 3D Shape Matching |
| title_sort | physicist s view on partial 3d shape matching |
| topic | optimal transport shape matching statistical physics |
| url | https://www.mdpi.com/1999-4893/16/7/346 |
| work_keys_str_mv | AT patricekoehl aphysicistsviewonpartial3dshapematching AT henriorland aphysicistsviewonpartial3dshapematching AT patricekoehl physicistsviewonpartial3dshapematching AT henriorland physicistsviewonpartial3dshapematching |