Measure of circularity for parts of digital boundaries and its fast computation
This paper focuses on the design of an effective method that computes the measure of circularity of a part of a digital boundary. An existing circularity measure of a set of discrete points, which is used in computational metrology, is extended to the case of parts of digital boundaries. From a single digital boundary, two sets of points are extracted so that the circularity measure computed from these sets is representative of the circularity of the digital boundary. Therefore, the computation consists of two steps. First, the inner and outer sets of points are extracted from the input part of a digital boundary using digital geometry tools. Next, the circularity measure of these sets is computed using classical tools of computational geometry. It is proved that the algorithm is linear in time in the case of convex parts thanks to the specificity of digital data, and is in O(n log n) otherwise. Experiments done on synthetic and real images illustrate the interest of the properties of the circularity measure. (C) 2009 Elsevier Ltd. All rights reserved
circularity computational geometry compactness digital circle discrete geometry