3D Shape Descriptors: 4D Hyperspherical Harmonics

“An Exploration into the Fourth Dimension”


As the number of three dimensional shapes on the internet continue to increase, an effective method of matching and retrieval is needed for people to obtain their wanted shapes. Traditionally 3D image retrieval has been done with text-based searches.  In development are efficient ways of matching shapes based upon geometrical characteristics that place objects with similar functionalities and categories together.  Ideally they would function as though an actual human had searched through the database.

Shape descriptors are computational representations of 3D objects. Shape descriptors should provide an insensitivity to noise, an easy comparison between objects, and concise storage. The translation, scale, and rotation of objects pose major challenges for robust shape descriptors. Shape descriptors can be develop such that they are invariant to translation, scale, or rotation. The shape must have some normalization algorithms applied for those properties that are not invariant.

Our method stems from the method of using 3D spherical harmonics over an object. 3D spherical harmonics are invariant to rotation and translation, and the objects are normalized to scale before harmonics are applied. 3D spherical harmonics are computationally faster than most algorithms, they are relatively invertible, and they have a high precision to recall measurement. Although methods that use 3D spherical harmonics are the most popular, there are still several problems that should be addressed. Spherical harmonic methods have three-dimensional storage, which is not concise to store. There is also a significant amount of error caused by taking cuts of inner spheres. This error is compounded with each cut by a truncation of harmonics for each radii.  Creating cuts radially outward (creating the inner spheres) also introduces the problem of ignoring inside rotations between objects.  This may result in objects matching which are quite obviously not the same to the human eye.

Our project attempts to solve these problems by using 4D hyperspherical harmonics. A 3D object can be mapped to the 4D unit hypersphere. Doing so will eliminate the error due to radii cuts.  Harmonics may be taken over the entire (mapped) shape of the object.  Since the mappings are unique and invertible, the harmonics are still accurate over the mapped 4D image. The 4D hyperspherical harmonics only have two-dimensional storage as a vector.  This theory was developed with the understanding that higher dimensional harmonics exist, that a 2D area may be easily mapped to the 3D unit sphere, and that a generalization of said mapping should give a 3D volume mapped to the 4D unit sphere. The visualization and testing of 2D to 3D mapping is done in Matlab while the rest of the programming will be done in C/C++ and OpenGL.