Fast and robust shape diameter function

PLoS One. 2018 Jan 26;13(1):e0190666. doi: 10.1371/journal.pone.0190666. eCollection 2018.

Abstract

The shape diameter function (SDF) is a scalar function defined on a closed manifold surface, measuring the neighborhood diameter of the object at each point. Due to its pose oblivious property, SDF is widely used in shape analysis, segmentation and retrieval. However, computing SDF is computationally expensive since one has to place an inverted cone at each point and then average the penetration distances for a number of rays inside the cone. Furthermore, the shape diameters are highly sensitive to local geometric features as well as the normal vectors, hence diminishing their applications to real-world meshes which often contain rich geometric details and/or various types of defects, such as noise and gaps. In order to increase the robustness of SDF and promote it to a wide range of 3D models, we define SDF by offsetting the input object a little bit. This seemingly minor change brings three significant benefits: First, it allows us to compute SDF in a robust manner since the offset surface is able to give reliable normal vectors. Second, it runs many times faster since at each point we only need to compute the penetration distance along a single direction, rather than tens of directions. Third, our method does not require watertight surfaces as the input-it supports both point clouds and meshes with noise and gaps. Extensive experimental results show that the offset-surface based SDF is robust to noise and insensitive to geometric details, and it also runs about 10 times faster than the existing method. We also exhibit its usefulness using two typical applications including shape retrieval and shape segmentation, and observe a significant improvement over the existing SDF.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms
  • Computer Simulation
  • Imaging, Three-Dimensional / methods*
  • Pattern Recognition, Automated / methods*

Associated data

  • figshare/10.6084/m9.figshare.5677861

Grants and funding

The work described in this paper was partially supported by grants from K.C. Wong Magna Fund in Ningbo University to SC, the National Natural Science Foundation of China (61772016 to SX, 61571251 to TL, 61772318 to CT), the Public Technical Application Research Project of Zhejiang (2015C34004) to TL, the Natural Science Foundation of Zhejiang (LY17F020018) to ZS, the Open Project Program of the State Key Lab of CAD&CG (A1702) to ZS, the key project of NSFC (61332015) to CT, and Ministry of Education (RG26/17) to YH.