Universal minimax binary image denoising under channel uncertainty

We consider the problem of denoising a binary image corrupted by a noisy medium which flips each component in the original image, independently, to its complementary value with some fixed but unknown probability δ<1/2. We propose a denoiser which assumes no knowledge of statistical properties of the image, yet asymptotically attains the performance of the scheme that knows the noisy image statistics and operates optimally in a minimax sense. The proposed scheme is implementable, with complexity linear in the image size. Preliminary experimental results are presented which indicate that the scheme has the potential to do well on real data.