A piecewise constant levelset approach for semi-blind deconvolution: Application to barcode decoding

Technical Summary: A Piecewise Constant Levelset Approach for Semi-Blind Deconvolution in Barcode Decoding

Problem Statement
This work addresses the semi-blind deconvolution problem inherent in decoding blurred linear barcodes. In a typical optical scanning setup, a laser beam illuminates a barcode, and the reflected light is converted into a 1D electrical signal. This process is modeled as a convolution $y = K * u$, where $u$ is the unknown piecewise constant barcode function (taking values 0 for black bars and 1 for white spaces) and $K$ is a point-spread function (PSF).

The problem is "semi-blind" because the PSF $K$ is not fully known; while its functional form (a Gaussian kernel) is assumed, its variance $\sigma^2$ (related to the scanner distance) and amplitude $\gamma$ are unknown or partially known. Furthermore, the observed signal $y_\delta$ is corrupted by noise. The objective is to simultaneously identify the barcode $u$ and the variance $\sigma^2$ from noisy measurements, a task complicated by the non-convex nature of the constraint that $u$ must be piecewise constant and the ill-posedness of the inverse problem.

Methodology
The authors propose a regularization strategy based on the Piecewise Constant Level Set (PCLS) framework and Augmented Lagrangian methods.

1. PCLS Representation: Instead of directly optimizing for the binary function $u$, the barcode is represented via a level-set function $\phi$. The binary constraint $u(x) \in \{0, 1\}$ is enforced by requiring $\phi$ to satisfy a double-well potential constraint $W(\phi) = \phi^n(\phi-1)^n = 0$ (where $n \in \{1, 2, \dots\}$). This transforms the identification of $u$ into the identification of $\phi$.
2. Slack Variable Introduction: To handle the semi-blind nature of the problem (where $K$ is also unknown), a slack variable $\tilde{K}$ is introduced. This allows the separation of the convolution kernel in the data fidelity term from the kernel in the regularization term, converting the problem into one with equality constraints on both the kernel and the level-set function.
3. Augmented Lagrangian Formulation: The constrained optimization problem is solved using an augmented Lagrangian functional. This functional incorporates the data fidelity term, Tikhonov-type regularization (including $H^1$ for the kernel and Total Variation for the level-set function), and penalty terms for the constraints $W(\phi)=0$ and $M(K, \tilde{K})=0$.
4. Iterative Algorithm: An ADMM-type (Alternating Direction Method of Multipliers) algorithm is developed to minimize the augmented Lagrangian. The algorithm alternates between:
   • Updating the primal variables ($\phi$, $\sigma$, and the slack kernel) using BFGS and Conjugate Gradient methods.
   • Updating the dual variables (Lagrange multipliers) and the penalty parameter using gradient-based updates.

Key Contributions
The paper makes both theoretical and algorithmic contributions:

• Theoretical Foundations: The authors establish the existence of generalized multipliers for the augmented Lagrangian functional and prove the absence of duality gaps for the non-convex optimization problem. These results rely on abstract convexity frameworks and provide the necessary theoretical basis to prove the regularization properties (stability and convergence) of the proposed method.
• Convergence and Stability: Under specific assumptions (including the existence of a true solution and bounded domains), the authors prove that the sequence of minimizers generated by the augmented Lagrangian approach converges to a solution of the inverse problem as the regularization parameter tends to zero and noise levels decrease.
• Algorithmic Implementation: A practical ADMM-type iterative scheme is presented for the explicit computation of approximate barcodes, handling the non-convex double-well constraint and the semi-blind kernel identification simultaneously.

Numerical Results
Numerical experiments were conducted on synthetic data simulating linear barcodes with varying degrees of blur (standard deviation $\sigma \in \{0.024, 0.026, 0.028\}$) and noise levels ($\delta \in \{0.5\%, 5\%, 10\%\}$).

• Effectiveness: The method successfully recovers both the barcode structure (widths and positions of bars) and the variance parameter in scenarios with moderate noise and blur.
• Convergence Speed: The algorithm demonstrates rapid convergence, often producing a reasonably accurate approximation of the barcode structure within just 3 iterations. The authors note that subsequent iterations primarily serve to enforce the binary constraint ($0$ or $1$) rather than correcting the structural shape.
• Limitations: The method's performance degrades as the blur variance $\sigma$ increases beyond approximately $0.028$ or when noise levels exceed $10\%$. In these extreme regimes, the algorithm may fail to recover thin bars or introduce spurious artifacts. The authors observe that accurate reconstruction of the barcode is possible even if the recovered variance $\sigma$ is not perfectly accurate.

Significance and Claims
The paper claims that its primary significance lies in providing a rigorous theoretical framework for solving the semi-blind deconvolution of linear barcodes using PCLS and augmented Lagrangians. By proving the existence of multipliers and the zero duality gap, the authors validate the stability of their approach against noisy measurements.

The authors position this work as an advancement over standard image deblurring or blind deconvolution techniques, specifically tailored to the unique constraints of barcode symbologies (piecewise constant, binary nature). While acknowledging that the method has limitations regarding severe blurring and high noise, the results validate the effectiveness of the proposed strategy for practical barcode decoding scenarios where the scanner distance (and thus blur) is within a reasonable operational range. The paper concludes by suggesting future work could extend this framework to 2D barcodes (e.g., QR codes) and non-Gaussian kernels.