Efficient Moment Computation over Polygonal Domains with an Application to Rapid Wedgelet Approximation

• Published in: SIAM journal on scientific computing 2007-01, Vol.29 (2), p.842-863
• Main Authors: Friedrich, F., Demaret, L., Führ, H., Wicker, K.
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation
• ISSN: 1064-8275; 1095-7197
• DOI: 10.1137/050646597

Many algorithms in image processing rely on the computation of sums of pixel values over a large variety of subsets of the image domain. This includes the computation of image moments for pattern recognition purposes, or adaptive smoothing and regression methods, such as wedgelets. In the first part of the paper, we present a general method which allows the fast computation of sums over a large class of polygonal domains. The approach relies on the idea of considering polygonal domains with a fixed angular resolution, combined with an efficient implementation of a discrete version of Green's theorem. The second part deals with the application of the new methodology to a particular computational problem, namely wedgelet approximation. Our technique results in a speedup of $O(10^3)$ by comparison to preexisting implementations. A further attractive feature of our implementation is the instantaneous access to the full scale of wedgelet minimizers. We introduce a new scheme that replaces the locally constant regression underlying wedgelets by basically arbitrary local regression models. Due to the speedup obtained by the techniques explained in the first part, this scheme is computationally efficient and at the same time much more flexible than previously suggested methods such as wedgelets or platelets. In the final section we present numerical experiments showing the increase in speed and flexibility.