Input
Output
Spherical Harmonics Basic Idea:
(1)Fouries transform can describe the distribution of a signal, and how the signal changes along time/space domain
(2)Spherical Harmonics can describe the distribution of a "signal" in space(sphere with certain radius), and how the "signal" changes along space domain
-
Pre-processing:
(1)Normalize
-make the center of mass of the model be at the point (R,R,R)
-scale so that the average distance from vertices to the center of mass is R/2
-(scale invariance and against outliers)
(2)Denoise
-use 3D bilateral filter to denoise
-(scanned noise invariance)
(3)Rasterize
-rasterize in to a 2R2R2R voxel grid (normally choose R to be ~32)
-(provide adequate granularity for discriminating shapes while filtering out high-freq noise) -
Descriptor:
Spherical harmonics descriptors(SH)
Distance histogram descriptors(DH) -
Retrieval: SH and DH database
Retrieval with same weight (with 0.5 on SH and DH respectively)
O(n) solution:
/* fill voxel grid and get rasterized points in O(n) */
bitmap = new bitmap(2R*2R*2R) //temporary bitmap
for each voxel to be filled
if(bitmap(voxel.x,voxel.y,voxel.z))==0 //has not been filled or registered
bitmap(voxel.x,voxel.y,voxel.z)=1
grid_point.push_back(voxel)
end
end
delete bitmap;
Pseudo code for spherical harmonics:
//SH is spherical harmonics descriptor
sort vertex according to radius
for each frequency l
for each rasterized vertex in one radius range r
calculate F_lr = F(theta,phi)
end
a_ml = sum of F_lr in one radius ragion
SH(l,r) += abs(a_ml)^2
end
SH = sqrt(SH)
*where F_lr is the following equation, l is m in the equation
Function: double gsl_sf_legendre_sphPlm (int l, int m, double x)
Function: int gsl_sf_legendre_sphPlm_e (int l, int m, double x, gsl_sf_result * result)
These routines compute the normalized associated Legendre polynomial \sqrt{(2l+1)/(4\pi)} \sqrt{(l-m)!/(l+m)!} P_l^m(x) suitable for use in spherical harmonics. The parameters must satisfy m >= 0, l >= m, |x| <= 1. Theses routines avoid the overflows that occur for the standard normalization of P_l^m(x).
The Legendre polynomial P(n,x) can be defined by:
P(0,x) = 1
P(1,x) = x
P(n,x) = (2*n-1)/n * x * P(n-1,x) - (n-1)/n * P(n-2,x)
1.database clustering
2.rasterization algorithm updates
3.Spherical Harmonics transform speed up
(1)divide and concour
http://www.ams.org/journals/mcom/2002-71-238/S0025-5718-01-01386-2/
(2)FFT to fourier then SH:
http://connection.ebscohost.com/c/articles/67655125/3d-objects-retrieval-using-spherical-harmonics-feature-vector-method
(3)O(n) solution for spherical harmonics:
http://liris.cnrs.fr/Documents/Liris-2276.pdf
4.New descriptors
- Spherical harmonics and Legendre polynomials ,involving solution when m is negative:
http://blog.sciencenet.cn/blog-548663-715825.html - Rodrigues' formula: equation dn/dxn = (d/dx)n:
http://wenku.baidu.com/view/72c151ef102de2bd960588f2 - Rotation Invariant Spherical Harmonic of 3D Shape:
http://www.chenkuantong.com/?p=1210 - An explaination of a_mn component(arbitrary constants?):
https://www.ngs.noaa.gov/PUBS_LIB/Geodesy4Layman/TR80003F.HTM - Spherical harmonics library:
http://www.cs.dartmouth.edu/~geelong/sphere/ - Spherical Harmonics Visual Representation:
http://afj-phd.blogspot.co.uk/2008/11/spherical-harmonics-visual.html - GSL library to calculate Spherical harmonics:
https://www.gnu.org/software/gsl/manual/html_node/Associated-Legendre-Polynomials-and-Spherical-Harmonics.html - Shape Descriptors from John Hopkins
http://www.cs.jhu.edu/~misha/Code/ShapeSPH/ShapeDescriptor/