# Stable Evaluation of 3D Zernike Moments for Surface Meshes
## 6 Numerical Results
### Computational Complexity for Geometric Moments and 3D Zernike Moments  
The algorithm (Algorithm 2) introduced in Section 3 for the exact computation of the Zernike moments of a shape represented by a triangular mesh of its boundary is of order \(O(M\times N^{5})\) where \(M\) is the number of facets in the surface mesh, and \(N\) is the maximum order considered. The linear complexity with respect to the total number of facets coincides with the complexity of discrete algorithms that approximate the moments by applying a summation over the 3D image grid instead of computing an integral (considering constant value for the function over each grid cell). The second algorithm (Algorithm 3), which computes the Zernike moments with a finite precision is also of order \(M\) with respect to the number of facets. We implemented the two algorithms in a C++ program, ShapeZernike, using double precision float arithmetics and tested their computational complexities on the simple case of a discrete sphere with radius 0.75, centered on the origin. We computed the Zernike moments for this sphere up to order 100 for the exact algorithm and for the finite precision algorithm, with the boundary of the sphere being represented with meshes with up to 1.3 million triangles. The experiments were run on an AMD Ryzen Threadripper PRO 3975 WX processor with 193 GB of memory; each calculation was run as a single thread. Results are shown in Figures 12 and 13. The running time for the exact algorithm is found to be strictly linear with respect to the number of triangles in the mesh, as expected. The finite precision algorithm deviates from the linearity for meshes with small number of meshes. This is not unexpected. Indeed, the triangles of such meshes have larger surface area, requiring higher quadrature strengths for computing accurately the Zernike moments (see Figure 4). The finite precision algorithm remains significantly faster than the exact algorithm. Figure 12: CPU times required to compute the Zernike moments of a sphere as a function of the number of triangles in the meshes that represent this sphere. We compare the exact algorithm (**left**) with the finite precision algorithm (**right**), while the time complexity for the former is found to be strictly linear with respect to the number of triangles, it deviates from linearity for the latter. We observe the same behavior for different maximum order \(N\) (20, 50 and 100) at which the Zernike moments are computed. Similar trends are observed as we analyze the running time with respect to the maximum order of the Zernike moments (Figure 13). The apparent complexity of the exact algorithm with respect to the maximum order \(N\) of the Zernike moments are \(O(N^{4.2})\), different from the theoretical order \(O(N^{5})\). This can be understood as follows. For a given facet in the mesh, we sum the \(g_{nl}^{m}\) over \(O(N^{2})\) points (i.e., the number of points needed for the strength of the quadrature that provides an exact integration on the facet). Computations of the \(g_{nl}^{m}\) for each point proceed in two main steps. First, we need to compute the integrals \(Q_{nl}\) and the spherical harmonics \(Y_{l}^{m}\), both of complexity \(O(N^{2})\), and second, we need to assemble the \(g_{nl}^{m}\) from those numbers. The second step is order \(O(N^{3})\), corresponding to the number of moments. Computing one \(Q_{nl}\) or one \(Y_{l}^{m}\) is significantly slower than assembling one \(g_{nl}^{m}\), however. For small enough \(N\) the two steps take similar computing times. Hence at small \(N\) the apparent complexity is close to \(O(N^{4})\). At larger values of \(N\) (i.e., \(N\gg 100\)), the \(O(N^{5})\) complexity would be recovered. This situation does not occur as the maximum strength of the quadratures on a facet is 101, i.e., corresponds to \(N\) at most 100. The apparent complexity of the finite algorithm is significantly better, of order \(O(N^{24})\).