On multigrid convergence of local algorithms for intrinsic volumes (Q2251260)

The analysis of digital output data from e.g. microscopes and scanners is a very important task. Many different features are analysed and one of them are intrinsic volumes. They include many of the quantities in which scientists are most frequently interested in, e.g. volume, surface area, integrated mean curvature, Euler characteristic. The paper deals with the analysis of the convergence of local algorithms for estimating the intrinsic volumes. In the considered algorithms a digital image of an object \(X\) is modelled by a binary image, i.e., a set \(X \cap L\), where \(L\) is a lattice in a \(d\)-dimensional real space. The intrinsic volumes \(V_q\) (\(q = 0, \dots, d\)) are estimated as a weighted sum of configuration counts. The author starts with some necessary definitions and gives various convergence criteria from which the most natural criterion is the multigrid convergence, i.e., the estimator converges to the true value when the resolution of the lattice goes to infinity. The analysis of the algorithms is taken in two cases. In the first case the estimation of \(V_q\) is done on the class \(P^d\) of compact convex polytopes with non-empty interior, and in the second case on the \(r\)-regular sets. In the analysis of the first case the author proves that for \(1 \leq q \leq d-1\) any local algorithm for \(V_q\) is asymptotically biased (and hence not multigrid convergent) for \(\nu\)-almost all \(P \in P^d\) if \(d - q\) is odd, and for a subset of \(P^d\) of positive \(\nu\)-measure if \(d - q\) is even. Next, the author proves that any local algorithm for \(V_0\) is asymptotically biased on \(P^d\) if \(d > 1\). Finally, the proof of a theorem that for \(0 \leq q \leq d - 2\) any local algorithm for \(V_q\) has an asymptotic worst case bias of at least \(100\%\) on \(P^d\) is given. In the second case the author proves that for \(q = d - 1\) and, if \(d \geq 3\), also for \(q = d - 2\) any local algorithm for \(V_q\) with homogeneous weights is asymptotically biased on the class of \(r\)-regular sets.