A theory of Coprime Blurred Pairs

Feng Li, Zijia Li, David Saunders, Jingyi YuICCV 2011 · DOI

Abstract

This paper introduces Coprime Blurred Pairs (CBP), a novel framework for image deblurring that utilizes two images of the same scene blurred by distinct "coprime" kernels. By representing images as bivariate polynomials, the authors leverage algebraic properties—specifically the Greatest Common Divisor (GCD) and Bezout matrices—to recover the latent sharp image. This approach offers a more accurate and computationally efficient alternative to traditional blind deconvolution methods that rely on restrictive statistical priors.

Introduction: The Blind Deconvolution Challenge

In computer vision, blind deconvolution is the ill-posed task of recovering a sharp image from a blurred observation when the blur kernel is unknown. Because multiple combinations of images and kernels can yield the same blurred result, the problem is inherently under-constrained.

Standard solutions typically employ priors—assumptions about the statistical properties of images or kernels (e.g., edge density or kernel sparsity). However, these priors often fail in practice; for example, sparsity priors can "shrink" the estimated kernel, resulting in the loss of fine details and the introduction of "ringing" artifacts. This research shifts the focus from statistical estimation to algebraic constraints: if two different blurs share no common factors (i.e., they are coprime), the original image can be mathematically isolated.

Example of a blurred input image with its corresponding blur kernel inset.

Methodology

The authors propose a three-step algebraic approach to deblurring:

  1. Polynomial Mapping: Blurred images are mapped into the $z$-transform domain, treated as bivariate polynomials. In this domain, convolution simplifies to multiplication: $B = I \times K$, where $B$ is the blurred image, $I$ is the sharp image, and $K$ is the kernel.
  2. Kernel Degree Estimation: Determining the size of the blur kernel is a significant hurdle. The authors utilize the Bezout Matrix, an algebraic tool for finding the GCD of polynomials. They demonstrate that the rank of this matrix directly corresponds to the kernel size, eliminating the need for iterative "guess-and-check" procedures.
  3. Efficient 2D GCD Computation: Computing the GCD of large 2D polynomials is computationally intensive and noise-sensitive. The authors address this by sampling the 2D polynomials on a unit circle to create 1D "slices," solving these efficiently, and then reconstructing the 2D kernels from the results.

Experimental Evaluation

The CBP framework was evaluated across several scenarios:

  • Synthetic Tests: Blurred versions of "garden" and "campus" scenes were used to compare the method against Gaussian and sparsity-based priors.
  • Video Surveillance: Real-world data from the EC Funded CAVIAR project demonstrated the method's utility in privacy-preserving encryption.
  • Flutter Shutter: Emulated sequences of moving objects tested the physical implementation of the theory.

Key Insights: Coprimality and Encryption

A central insight of this work is that two randomly chosen blur kernels are almost always coprime, making the CBP theory widely applicable to multi-image systems. Furthermore, the authors draw a parallel between CBP and RSA encryption. One blurred stream can serve as a "public" version (low detail for general monitoring), while a second stream acts as a "private key." Only an authorized user with access to both streams can reconstruct the high-resolution, sharp image.

Results and Performance

The CBP algorithm demonstrates high efficiency; for a $1024 \times 768$ image with a $51 \times 51$ kernel, the estimation and deblurring process takes approximately 9.17 seconds using unoptimized Matlab code.

The sharp garden scene successfully recovered using the CBP algebraic framework.

Qualitatively, the method preserves high-frequency details—such as facial features in surveillance footage—that are often smoothed away by sparsity-based methods. It also significantly reduces ringing artifacts compared to state-of-the-art single-image deblurring techniques. By employing Singular Value Decomposition (SVD) to analyze the Bezout matrix, the method maintains robustness against moderate noise levels.

Limitations and Future Directions

While more robust than previous algebraic methods, GCD-based approaches remain sensitive to high sensor noise, which can disrupt polynomial relationships. Additionally, the method assumes strict coprimality; any common factor shared by the kernels will persist as residual blur in the recovered image. Future work will focus on applying the theory to "wild" dual-camera systems where registration errors and misalignments may occur.

Summary updated

BibTeX
@inproceedings{li2011theory,
  author = {Feng Li and Zijia Li and David Saunders and Jingyi Yu},
  title = {{A theory of Coprime Blurred Pairs}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2011},
  doi = {10.1109/iccv.2011.6126245},
}
Figure