  We propose a novel statistical hypothesis testing method for 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. In this paper, we develop further the mathematical formalism of our
method and explore important connections to the mathematical theory of
percolation and statistical physics. We prove results on consistency and
algorithmic complexity of our testing procedure. In addition, we address not
only an asymptotic behavior of the method, but also a finite sample performance
of our test.
