An Edge-Based Formulation for the Exact Computation of High-Order Zernike Moments of 2D Shapes and Images

Technical Summary: An Edge-Based Formulation for the Exact Computation of High-Order Zernike Moments of 2D Shapes and Images

Problem Statement
Zernike moments are established rotation-invariant descriptors used extensively in shape analysis, pattern recognition, and medical imaging. However, their standard computation relies on a pixel-based quadrature that approximates the continuous image integral as a Riemann sum over pixel centers, treating each pixel as a point mass (Dirac $\delta$-function). This approximation introduces two critical limitations:

1. Spatial Aliasing: As the moment order increases, the radial polynomials oscillate on scales comparable to or smaller than a single pixel. The point-mass model fails to capture this spatial extent, leading to significant discretization errors.
2. Numerical Instability: At high orders (typically $n \gtrsim 50$), the accumulation of floating-point errors and aliasing degrades the accuracy of the moments. This manifests in image reconstruction as "ghost pixels" (spurious values at antipodal locations) and reduces the discriminative power of the descriptors in classification tasks.

While previous work has addressed the numerical stability of radial polynomial evaluation via recurrence relations, the fundamental error source—the geometric mismatch between the continuous basis functions and the discrete pixel grid—remains unaddressed in standard implementations.

Methodology
The authors propose a fundamentally different approach that eliminates discretization error by applying Green's theorem to transform the two-dimensional area integral defining a Zernike moment into a sum of one-dimensional line integrals along image boundaries.

1. Green's Theorem Transformation:
   Instead of summing over pixel centers, the method treats the image (or shape) as a domain bounded by piecewise-linear contours. The area integral over a domain $D$ is converted into a line integral along the boundary $\partial D$. For a polygonal shape or a raster image decomposed into constant-intensity regions, the total moment is the sum of contributions from each edge.

2. Exact Edge Integration:
   The integrand along an edge is shown to be a polynomial function of the edge parameter $t$. Specifically, the radial primitive $Q_n^m(r)$ and the angular component are combined such that the resulting integrand $A_n^m(t)$ is a polynomial of degree at most $n$.

   • Recurrence Relations: The authors derive recurrence relations for the radial primitives $Q_n^m(r)$, $S_n^m(r)$, and the radial polynomials $R_n^m(r)$ to compute these values efficiently without catastrophic cancellation.
   • Quadrature: Because the transformed integrand is a polynomial, the line integral can be evaluated exactly using numerical quadrature. The authors utilize Clenshaw–Curtis quadrature, which allows for efficient adaptive refinement and the reuse of function evaluations across different moment orders.

3. Applicability:

   • Contour Data: The method applies directly to vector shapes defined by closed polygonal contours, computing moments without any reference to a pixel grid.
   • Raster Images: For digital images, the method treats the image as a mesh of square cells. The integration is performed along the edges between pixels. Crucially, edges shared by adjacent pixels with identical intensity cancel out ($\Delta I = 0$), meaning the computation effectively scales with the number of active boundaries (edges with intensity gradients) rather than the total number of pixels.
   • Color Images: The framework extends to color images by representing pixels as pure quaternions and computing Quaternion Zernike Moments (QZM), capturing correlations between RGB channels.

Key Contributions

1. Exact Contour-Based Formulation: The derivation of an exact formula for Zernike moments of regions enclosed by piecewise-linear contours, expressed as a sum of line integrals. This formulation introduces no discretization or quadrature error.
2. Extension to Raster Images: An adaptation of the formalism to compute exact Zernike moments for piecewise-constant raster images. This provides the exact integral of the piecewise-constant image, contrasting with the standard point-mass approximation.
3. Algorithmic Efficiency: The reduction of the 2D area integral to 1D line integrals reduces the theoretical computational complexity of exact integration from $O(N^4)$ (for exact 2D area quadrature) to $O(N^3)$ (where $N$ is the maximum order). In practice, adaptive quadrature often yields near-linear scaling with the number of moments.
4. Comprehensive Validation: The authors provide experimental evidence across image reconstruction, shape analysis, and character classification.

Results
Numerical experiments on images of varying complexity (natural color images, geometric gears, single-pixel tests, QR codes, and Chinese characters) demonstrate:

• Low/Moderate Orders: The edge-based method matches the accuracy of classical pixel-based methods for low orders ($M \le 100$).
• High-Order Stability: At high orders ($M = 500$), the pixel-based method suffers from severe aliasing.
  • Reconstruction: Pixel-based reconstructions of simple shapes (e.g., a single white pixel) exhibit "ghost pixels" at antipodal locations due to symmetry breaking. Edge-based reconstructions remain artifact-free.
  • QR Codes: Pixel-based reconstructions of QR codes degrade significantly at high orders, becoming unrecognizable, whereas edge-based reconstructions remain sharp and readable.
  • Classification: In a classification task involving 5 Chinese characters, pixel-based Zernike invariants showed a drop in accuracy from 96.9% ($M=100$) to 90.1% ($M=500$). In contrast, edge-based invariants maintained and slightly improved accuracy, reaching 97.3% at $M=500$.
• Computational Cost: The edge-based method is currently slower (37–74 times) than the pixel-based method for standard image sizes due to the evaluation of line integrals. However, the method is trivially parallelizable, and the computational burden is proportional to the image perimeter (active edges) rather than the area.

Significance and Claims
The paper claims that the proposed edge-based formulation resolves the long-standing issue of spatial aliasing in high-order Zernike moment computation. By treating the image as a continuous piecewise-constant field and integrating exactly over boundaries, the method achieves mathematical exactness that pixel-based approximations cannot.

The authors emphasize that while deep learning has become dominant in image analysis, moment-based descriptors remain vital for applications requiring explainability, limited training data, and precise geometric characterization. The proposed method ensures that these descriptors remain stable and discriminative even at high orders, where traditional methods fail. The work suggests that this framework is not only a theoretical improvement but a practical necessity for high-fidelity shape analysis and reconstruction tasks involving high-order moments. Future directions mentioned include generalizing the approach to other orthogonal moments (Legendre, Chebyshev) and extending the formulation to 3D Zernike moments computed from polygonal surface meshes.