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

Resumen Técnico: Un enfoque de nivel de conjunto de constante por tramos para la deconvolución semi-ciega en la decodificación de códigos de barras

Planteamiento del Problema
Este trabajo aborda el problema de la deconvolución semi-ciega inherente a la decodificación de códigos de barras lineales desenfocados. En una configuración típica de escaneo óptico, un haz de luz láser ilumina un código de barras y la luz reflejada se convierte en una señal eléctrica de 1D. Este proceso se modela como una convolución $y = K * u$, donde $u$ es la función de código de barras de constante por tramos desconocida (que toma valores 0 para barras negras y 1 para espacios blancos) y $K$ es una función de dispersión de punto (PSF, por sus siglas en inglés) de tipo punto.

El problema es "semi-ciego" porque la PSF $K$ no se conoce completamente; aunque se asume su forma funcional (un núcleo gaussiano), su varianza $\sigma^2$ (relacionada con la distancia del escáner) y su amplitud $\gamma$ son desconocidas o parcialmente conocidas. Además, la señal observada $y_\delta$ está corrompida por ruido. El objetivo es identificar simultáneamente el código de barras $u$ y la varianza $\sigma^2$ a partir de mediciones con ruido, una tarea complicada por la naturaleza no convexa de la restricción de que $u$ debe ser de constante por tramos y la naturaleza mal planteada del problema inverso.

Metodología
Los autores proponen una estrategia de regularización basada en el marco de Nivel de Conjunto de Constante por Tramos (PCLS) y métodos de Lagrangiano Aumentado.

1. Representación PCLS: En lugar de optimizar directamente para la función binaria $u$, el código de barras se representa mediante una función de nivel de conjunto $\phi$. La restricción binaria $u(x) \in \{0, 1\}$ se impone requiriendo que $\phi$ satisfaga una restricción de potencial de doble pozo $W(\phi) = \phi^n(\phi-1)^n = 0$ (donde $n \in \{1, 2, \dots\}$). Esto transforma la identificación de $u$ en la identificación de $\phi$.
2. Introducción de Variables de Holgura: Para manejar la naturaleza semi-ciega del problema (donde $K$ también es desconocido), se introduce una variable de holgura $\tilde{K}$. Esto permite la separación del núcleo de convolución en el término de fidelidad de los datos del núcleo en el término de regularización, convirtiendo el problema en uno con restricciones de igualdad tanto en el núcleo como en la función de nivel de conjunto.
3. Formulación del Lagrangiano Aumentado: El problema de optimización restringida se resuelve utilizando un funcional de Lagrangiano aumentado. Este funcional incorpora el término de fidelidad de los datos, la regularización de tipo Tikhonov (incluyendo $H^1$ para el núcleo y Variación Total para la función de nivel de conjunto), y términos de penalización para las restricciones $W(\phi)=0$ y $M(K, \tilde{K})=0$.
4. Algoritmo Iterativo: Se desarrolla un algoritmo de tipo ADMM (Método de Multiplicadores de Dirección Alterna) para minimizar el Lagrangiano aumentado. El algoritmo alterna entre:
   • Actualizar las variables primarias ($\phi$, $\sigma$ y el núcleo de holgura) utilizando métodos BFGS y de Gradiente Conjugado.
   • Actualizar las variables duales (multiplicadores de Lagrange) y el parámetro de penalización mediante actualizaciones basadas en el gradiente.

Contribuciones Clave
El artículo presenta contribuciones tanto teóricas como algorítmicas:

• Fundamentos Teóricos: Los autores establecen la existencia de multiplicadores generalizados para el funcional del Lagrangiano aumentado y demuestran la ausencia de brechas de dualidad para el problema de optimización no convexo. Estos resultados se basan en marcos de convexidad abstracta y proporcionan la base teórica necesaria para demostrar las propiedades de regularización (estabilidad y convergencia) del método propuesto.
• Convergencia y Estabilidad: Bajo supuestos específicos (incluyendo la existencia de una solución verdadera y dominios acotados), los autores demuestran que la secuencia de minimizadores generada por el enfoque de Lagrangiano aumentado converge a una solución del problema inverso a medida que el parámetro de regularización tiende a cero y los niveles de ruido disminuyen.
• Implementación Algorítmica: Se presenta un esquema iterativo práctico de tipo ADMM para el cómputo explícito de aproximaciones de códigos de barras, manejando la restricción no convexa de doble pozo y la identificación simultánea del núcleo semi-ciego.

Resultados Numéricos
Se realizaron experimentos numéricos con datos sintéticos que simulan códigos de barras lineales con diversos grados de desenfoque (desviación estándar $\sigma \in \{0.024, 0.026, 0.028\}$) y niveles de ruido ($\delta \in \{0.5\%, 5\%, 10\%\}$).

• Efectividad: El método recupera con éxito tanto la estructura del código de barras (anchos y posiciones de las barras) como el parámetro de varianza en escenarios con ruido y desenfoque moderados.
• Velocidad de Convergencia: El algoritmo demuestra una convergencia rápida, produciendo a menudo una aproximación razonablemente precisa de la estructura del código de barras en tan solo 3 iteraciones. Los autores señalan que las iteraciones posteriores sirven principalmente para imponer la restricción binaria ($0$o$1$) más que para corregir la forma estructural.
• Limitaciones: El rendimiento del método se degrada a medida que la varianza del desenfoque $\sigma$ aumenta más allá de aproximadamente $0.028$ o cuando los niveles de ruido superan el $10\%$. En estos regímenes extremos, el algoritmo puede fallar al recuperar barras delgadas o introducir artefactos espurios. Los autores observan que la reconstrucción precisa del código de barras es posible incluso si la varianza $\sigma$ recuperada no es perfectamente exacta.

Significancia y Reivindicaciones
El artículo afirma que su principal significancia radica en proporcionar un marco teórico riguroso para resolver la deconvolución semi-ciega de códigos de barras lineales utilizando PCLS y Lagrangianos aumentados. Al demostrar la existencia de multiplicadores y la brecha de dualidad cero, los autores validan la estabilidad de su enfoque frente a mediciones ruidosas.

Los autores posicionan este trabajo como un avance sobre las técnicas estándar de desenfoque de imágenes o deconvolución ciega, adaptado específicamente a las restricciones únicas de las simbologías de códigos de barras (naturaleza de constante por tramos, binaria). Aunque reconocen que el método tiene limitaciones respecto al desenfoque severo y al ruido alto, los resultados validan la efectividad de la estrategia propuesta para escenarios prácticos de decodificación de códigos de barras donde la distancia del escáner (y, por tanto, el desenfoque) se encuentra dentro de un rango operativo razonable. El artículo concluye sugiriendo que trabajos futuros podrían extender este marco a códigos de barras 2D (por ejemplo, códigos QR) y núcleos no gaussianos.