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 .
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 . 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 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.