Multigrid Convergence of Geometric Features

Reinhard Klette

April, 2001

Jordan, Peano and others introduced digitizations of sets in the plane and in the 3D space for the purpose of feature measurements. Features measured for digitized sets, such as perimeter, contents etc., should converge (for increasing grid resolution) towards the corresponding features of the given sets before digitization. This type of multigrid convergence is one option for performance evaluation of feature measurement in image analysis with respect to correctness.

The paper reviews work in multigrid convergence in the context of digital image analysis. In 2D, problems of area estimations and lower-order moment estimations do have "classical" solutions (Gauss, Dirichlet, Landau et al.). Estimates of moments of arbitrary order are converging with speed $f(r)=r^{-15/11}$. The linearity of convergence is known for three techniques for curve length estimation based on regular grids and polygonal approximations.

Piecewise Lagrange interpolants of sampled curves allow faster convergence speed. A first algorithmic solution for convergent length estimation for digital curves in 3D has been suggested quite recently. In 3D, for problems of volume estimations and lower-order moment estimations solutions are known for about one-hundred years (Minkowski, Scherrer et al.). But the problem of multigrid surface contents measurement is still a challenge, and there is recent progress in this field.

Download: CITR-TR-87.pdf (1.54 MB)

Back to Technical Report page.

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the CITR web site under terms that include this permission. All other rights are reserved by the author(s).

© CITR, The University of Auckland, 2002