Robust nonparametric detection of objects in noisy images

Abstract

We propose a novel statistical hypothesis testing method for the detection of objects in noisy images. The method uses results from percolation theory and random graph theory. We present an algorithm that allows to detect objects of unknown shapes in the presence of nonparametric noise of unknown level and of unknown distribution. No boundary shape constraints are imposed on the object, only a weak bulk condition for the object's interior is required. The algorithm has linear complexity and exponential accuracy and is appropriate for real-time systems. We prove results on consistency and algorithmic complexity of our testing procedure. In addition, we address not only an asymptotic behaviour of the method, but also a finite sample performance of our test.

Keywords:

• image analysis
• signal detection
• image reconstruction
• percolation
• noisy image
• nonparametric noise
• robust testing
• finite sample performance

Acknowledgements

The authors would like to thank Laurie Davies and Remco van der Hofstad for helpful discussions, and the Associate Editor and the two referees for valuable suggestions that helped to greatly improve the presentation of the paper.