Statistica Sinica 19 (2009), 1439-1462

DETECTABILITY OF CONVEX-SHAPED OBJECTS

IN DIGITAL IMAGES, ITS FUNDAMENTAL LIMIT

AND MULTISCALE ANALYSIS

Xiaoming Huo and Xuelei (Sherry) Ni

Georgia Institute of Technology and Kennesaw State University

Abstract: Given a convex-shape inhomogeneous region embedded in a noisy image, we consider the conditions under which such an embedded region is detectable. The existence of low order-of-complexity detection algorithms is also studied. The main results are (1) an analytical threshold (of a statistic) that specifies what is detectable, and (2) the existence of a multiscale detection algorithm whose order of complexity is roughly the optimal $O(n^2 \log^2(n))$.

Our analysis has two main components. We first show that in a discrete image, the number of convex sets increases faster than any finite degree polynomial of the image size $n$. Hence the idea of generalized likelihood ratio test cannot be directly adopted to derive the asymptotic detectability bound. Secondly, we show that the maximally embedded hv-parallelogram is at least $2/9$ of the convex region (in area). We then apply the results of hv-parallelograms in Arias-Castro, Donoho, and Huo (2005) on detecting convex sets. Numerical examples are provided.

Our results have potential applications in several fields, which are described with corresponding references.

Key words and phrases: Convex sets, detectability, image detection, white-noises.