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

Resumo Técnico: Uma Abordagem de Nível de Conjunto de Constância por Partes para Desconvolução Semi-Cega em Decodificação de Códigos de Barras

Enunciado do Problema
Este trabalho aborda o problema de desconvolução semi-cega inerente à decodificação de códigos de barras lineares borrados. Em uma configuração típica de leitura óptica, um feixe de laser ilumina um código de barras e a luz refletida é convertida em um sinal elétrico 1D. Esse processo é modelado como uma convolução $y = K * u$, onde $u$ é a função desconhecida do código de barras de constância por partes (assumindo valores 0 para barras pretas e 1 para espaços brancos) e $K$ é uma função de espalhamento de ponto (PSF).

O problema é "semi-cego" porque a PSF $K$ não é totalmente conhecida; embora sua forma funcional (um núcleo gaussiano) seja assumida, sua variância $\sigma^2$ (relacionada à distância do scanner) e sua amplitude $\gamma$ são desconhecidas ou parcialmente conhecidas. Além disso, o sinal observado $y_\delta$ é corrompido por ruído. O objetivo é identificar simultaneamente o código de barras $u$ e a variância $\sigma^2$ a partir de medições ruidosas, uma tarefa complicada pela natureza não convexa da restrição de que $u$ deve ser de constância por partes e pela natureza mal posta do problema inverso.

Metodologia
Os autores propõem uma estratégia de regularização baseada na estrutura de Conjunto de Nível de Constância por Partes (PCLS) e métodos de Lagrangiana Aumentada.

1. Representação PCLS: Em vez de otimizar diretamente pela função binária $u$, o código de barras é representado via uma função de conjunto de nível $\phi$. A restrição binária $u(x) \in \{0, 1\}$ é imposta exigindo que $\phi$ satisfaça uma restrição de potencial de poço duplo $W(\phi) = \phi^n(\phi-1)^n = 0$ (onde $n \in \{1, 2, \dots\}$). Isso transforma a identificação de $u$ na identificação de $\phi$.
2. Introdução de Variável de Folga: Para lidar com a natureza semi-cega do problema (onde $K$ também é desconhecido), uma variável de folga $\tilde{K}$ é introduzida. Isso permite a separação do núcleo de convolução no termo de fidelidade dos dados do núcleo no termo de regularização, convertendo o problema em um com restrições de igualdade tanto no núcleo quanto na função de conjunto de nível.
3. Formulação da Lagrangiana Aumentada: O problema de otimização restrito é resolvido usando um funcional de Lagrangiana aumentada. Este funcional incorpora o termo de fidelidade dos dados, regularização do tipo Tikhonov (incluindo $H^1$ para o núcleo e Variação Total para o conjunto de nível) e termos de penalidade para as restrições $W(\phi)=0$ e $M(K, \tilde{K})=0$.
4. Algoritmo Iterativo: Um algoritmo do tipo ADMM (Método de Multiplicadores de Direção Alternada) é desenvolvido para minimizar a Lagrangiana aumentada. O algoritmo alterna entre:
   • Atualizar as variáveis primárias ($\phi$, $\sigma$ e o núcleo de folga) usando métodos BFGS e de Gradiente Conjugado.
   • Atualizar as variáveis duais (multiplicadores de Lagrange) e o parâmetro de penalidade através de atualizações baseadas em gradiente.

Principais Contribuições
O artigo apresenta contribuições tanto teóricas quanto algorítmicas:

• Fundamentos Teóricos: Os autores estabelecem a existência de multiplicadores generalizados para o funcional da Lagrangiana aumentada e provam a ausência de lacunas de dualidade para o problema de otimização não convexo. Esses resultados baseiam-se em estruturas de convexidade abstrata e fornecem a base teórica necessária para provar as propriedades de regularização (estabilidade e convergência) do método proposto.
• Convergência e Estabilidade: Sob suposições específicas (incluindo a existência de uma solução real e domínios limitados), os autores provam que a sequência de minimizadores gerada pela abordagem da Lagrangiana aumentada converge para uma solução do problema inverso conforme o parâmetro de regularização tende a zero e os níveis de ruído diminuem.
• Implementação Algorítmica: Um esquema iterativo prático do tipo ADMM é apresentado para o cálculo explícito de códigos de barras aproximados, lidando com a restrição não convexa de poço duplo e a identificação simultânea do núcleo semi-cego.

Resultos Numéricos
Experimentos numéricos foram conduzidos em dados sintéticos simulando códigos de barras lineares com diferentes graus de desfoque (desvio padrão $\sigma \in \{0.024, 0.026, 0.028\}$) e níveis de ruído ($\delta \in \{0.5\%, 5\%, 10\%\}$).

• Eficácia: O método recupera com sucesso tanto a estrutura do código de barras (larguras e posições das barras) quanto o parâmetro de variância em cenários com ruído e desfoque moderados.
• Velocidade de Convergência: O algoritmo demonstra convergência rápida, produzindo frequentemente uma aproximação razoavelmente precisa da estrutura do código de barras em apenas 3 iterações. Os autores observam que as iterações subsequentes servem principalmente para impor a restrição binária ($0$ ou $1$) em vez de corrigir a forma estrutural.
• Limitações: O desempenho do método degrada-se conforme a variância do desfoque $\sigma$ aumenta além de aproximadamente $0.028$ ou quando os níveis de ruído excedem $10\%$. Nesses regimes extremos, o algoritmo pode falhar em recuperar barras finas ou introduzir artefatos espúrios. Os autores observam que a reconstrução precisa do código de barras é possível mesmo se a variância $\sigma$ recuperada não for perfeitamente exata.

Significância e Alegações
O artigo alega que sua principal significância reside em fornecer um arcabouço teórico rigoroso para resolver a desconvolução semi-cega de códigos de barras lineares usando PCLS e Lagrangianas aumentadas. Ao provar a existência de multiplicadores e a lacuna de dualidade zero, os autores validam a estabilidade de sua abordagem contra medições ruidosas.

Os autores posicionam este trabalho como um avanço sobre as técnicas padrão de deblurring de imagem ou desconvolução cega, especificamente adaptadas às restrições únicas das simbologias de códigos de barras (natureza de constância por partes, binária). Embora reconheçam que o método possui limitações quanto ao desfoque severo e ruído elevado, os resultados validam a eficácia da estratégia proposta para cenários práticos de decodificação de códigos de barras onde a distância do scanner (e, portanto, o desfoque) está dentro de um intervalo operacional razoável. O artigo conclui sugerindo que trabalhos futuros podem estender este arcabouço para códigos de barras 2D (ex: QR codes) e núcleos não gaussianos.