Hide/Show Apps

On the complexity of shapes embedded in ZN

Arslan, Mazlum Ferhat
Shape complexity is a hard-to-quantify quality, mainly due to its relative nature. In common view, circles are considered to be the simplest shapes. However, when implemented in computer, none of the circularity measures yield the expected scores for the circle. This is because digital domain (Z^n) realizations of circles are only approximations to the ideal form. Consequently, complexity orders computed in reference to circle are unstable. As a remedy, we consider squares to be the simplest shapes relative to which multi-scale complexity orders are to be constructed. Whereas measuring roundness is encountered more often in literature quantifying rectangularity emerges as a specific interest due to applications ranging from landscape ecology, urban planning, and computer-aided production. Using the connection between L^infty and squares we effectively encode squareness-adapted multi-scale simplification through which we obtain entropy-like multi-scale shape complexity measure. In contrast to usual diffusion based ones, our multi-scale simplification exhibits a local behavior where curves become locally flat instead of getting rounder. Proposed complexity measure is tested on binary images containing noisy shapes; Kendall-tau distances from the expected order are reported. The measure is compared against its L^2 counterpart in terms of robustness under noise and scale. Finally, partial orders are constructed on the shapes based on their complexities with respect to different scales and various complexity measures.