前回の宣言通りニッチな話をします。広い文脈で捉えるならばデコンボリューションの応用事例として考えることもできますが、あえてデコンボリューションを使わないアイデアを紹介します。

最小エレメント幅以上の径でぼやけたバーコードは、2 値化による読み取り困難です。バーコードの利用現場では、カメラの性能やオペレータの操作の不安定性から、しばしば最小エレメント幅以上のぼやけが発生します。このような状況でも安定してバーコードを読み取るためには、ぼやけに強い符号化が必要になります。

バーコードのラインセンシング画像を関数と見立てたとき、関数の表現を変えると聞いてピンとくるものは何でしょうか。おそらくフーリエ変換が思い浮かぶでしょう。

しかし、フーリエ変換は Blur に対して劣化が著しく、不安定です。Blur といえば、単純に積分してしまえは情報量は少ないですが安定しています。

\begin{align} \lambda_1=\dfrac{1}{L}\int_0^Lf_0(x)\,dx \end{align}

同様にして

\begin{align} &f_n(x)=\dfrac{1}{L}\int_0^xf_{n-1}(y)\,dy-\dfrac{\lambda_nx}{L},\\ &\lambda_{n+1}=\dfrac{1}{L}\int_0^Lf_n(x)\,dx \end{align}

で計算される数列 $\lambda$ も安定です。したがって数列 $\lambda$ が、バーコードの示す各キャラクタに対して良く分離しているのであれば、安定した符号化として使えます。実際に使う場合は以下のステップを実行します。

1. 理論的な各キャラクタから数列 $\lambda$ を算出(これを基準列と呼ぶ)
2. 実測されたキャラクタから数列 $\lambda$ を計算して各基準列と比較
3. 最も「近い」基準列のキャラクタを返す

最後の「近い」ことの定義には若干の癖があります。基準列との差分の $L_2$ をとったとしても、なかなか上手くいきません。その理由は、比較する基準列に依存して距離の縮尺が変わるからです。この縮尺も含めて最初のステップで計算しておけば良いです。

なお、実際に実装する場合には数列 $\lambda$ の計算を

\begin{align} (-1)^{n-1}\lambda_n=\dfrac{1}{(n-1)!L^n}\int_0^Lx^{n-1}f_0(x)\,dx-\dfrac{\lambda_1}{n!}+\dfrac{\lambda_2}{(n-1)!}+\dots+(-1)^{n-1}\dfrac{\lambda_{n-1}}{2!} \end{align}

のように実行すると計算量が少なくなります。PassMark 700 前後の環境で単位キャラクタ当たり 11μs 強で実行できます。この符号化を使うと、なんと最小エレメント幅の 2 倍の Blur に対しても安定してバーコードを読み取ることができます。次回もニッチな話です。(written by J.Nishigata)

その他11- バーコードの安定符号化技術