Reconstruction of Binary Shapes from Blurred Images via Hankel-structured Low-rank Matrix Recovery

With the dominance of digital imaging systems, we are often dealing with discrete-domain samples of an analog image. Due to physical limitations, all imaging devices apply a blurring kernel on the input image before taking samples to form the output pixels. In this paper, we focus on the reconstruction of binary shape images from few blurred samples. This problem has applications in medical imaging, shape processing, and image segmentation. Our method relies on representing the analog shape image in a discrete grid much finer than the sampling grid. We formulate the problem as the recovery of a rank r matrix that is formed by a Hankel structure on the pixels. We further propose efficient ADMM-based algorithms to recover the low-rank matrix in both noiseless and noisy settings. We also analytically investigate the number of required samples for successful recovery in the noiseless case. For this purpose, we study the problem in the random sampling framework, and show that with O(r log4(n1n2)) random samples (where the size of the image is assumed to be n1 x n2) we can guarantee the perfect reconstruction with high probability under mild conditions. We further prove the robustness of the proposed recovery in the noisy setting by showing that the reconstruction error in the noisy case is bounded when the input noise is bounded. Simulation results confirm that our proposed method outperform the conventional total variation minimization in the noiseless settings.