(57)【要約】【課題】隠れマルコフモデル（ＨＭＭ）を用いて遠方からバーコード情報を取り出す。【解決手段】入力装置（ＣＣＤ１０３）で撮影された入力画像はデコード基板１０６上に設けられるメモリ１０７の入力画像バッファ１７１に記憶される。このメモリ１０７の入力画像バッファ１７１、抽出バーコード画像バッファ１７２、抽出特徴量バッファ１７３、読み込みバッファ１７４に記憶されるデータがＣＰＵ部１０５のバーコード領域抽出部１５１、特徴量抽出部１５２、ＨＭＭデコード部１５３に供給される。そして、デコードされたキャラクタがメモリ１０７のバーコード読み取り結果バッファ１７５に記憶され、出力装置１０９に取り出される。【選択図】図２
2009031857.tif 000002
【特許請求の範囲】
【請求項１】
画像の明部及び／または暗部の配列により情報を形成する画像コードを読み取る光学的情報読取装置であって、
検出枠を前記情報の配列方向に徐々に変化させて得られる信号の特徴量を検出する特徴量検出手段と、
前記検出された特徴量の変化に基づいて隠れマルコフモデルを用いて情報を取り出す情報抽出手段と、
を設けることを特徴とする光学的情報読取装置。
【請求項２】
前記特徴量は、検出枠を前記情報の配列方向に徐々に変化させて得られる信号の周波数パターンである
ことを特徴とする請求項１に記載の光学的情報読取装置。
【請求項３】
前記情報抽出手段は、前記画像の明部及び／または暗部の任意の配列により形成された画像コードにおける前記隠れマルコフモデルのパラメータを学習する学習手段を有する
ことを特徴とする請求項１記載の光学的情報読取装置。
【請求項４】
前記画像コードには複数の規格が設けられ、
前記情報抽出手段は、前記画像コードの規格における前記隠れマルコフモデルのパラメータを、対象とされる前記画像コードの規格ごとに予め記憶した記憶手段を有する
ことを特徴とする請求項１記載の光学的情報読取装置。
【請求項５】
画像の明部及び／または暗部の配列により情報を形成する画像コードを読み取るための光学的情報読取方法であって、
検出枠を前記情報の配列方向に徐々に変化させて得られる信号の特徴量を検出するステップと、
前記検出された特徴量の変化に基づいて隠れマルコフモデルを用いて情報を取り出すステップと、
を備えることを特徴とする光学的情報読取方法。
【請求項６】
前記特徴量は、検出枠を前記情報の配列方向に徐々に変化させて得られる信号の周波数パターンである
ことを特徴とする請求項５記載の光学的情報読取方法。
【請求項７】
前記情報を取り出すステップは、前記画像の明部及び/または暗部の任意の配列により形成された画像コードにおける前記隠れマルコフモデルのパラメータを学習するステップを含む
ことを特徴とする請求項５記載の光学的情報読取方法。
【請求項８】
前記画像コードには複数の規格が設けられ、
前記画像コードの規格における前記隠れマルコフモデルのパラメータを、対象とされる前記画像コードの規格ごとに予め記憶した記憶手段を有する
ことを特徴とする請求項５記載の光学的情報読取方法。
【請求項９】
画像の明部及び／または暗部の配列により情報を形成する画像コードを読み取る機能を実現する光学的情報読取プログラムであって、
検出枠を前記情報の配列方向に徐々に変化させて得られる信号の特徴量を検出する機能と、
前記検出された特徴量の変化に基づいて隠れマルコフモデルを用いて情報を取り出す機能と、
をコンピュータで実現することを特徴とする光学的情報読取プログラム。
【請求項１０】
前記特徴量は、検出枠を前記情報の配列方向に徐々に変化させて得られる信号の周波数パターンである
ことを特徴とする請求項９記載の光学的情報読取プログラム。
【請求項１１】
前記情報を取り出す機能は、前記画像の明部及び／または暗部の任意の配列により形成された画像コードにおける前記隠れマルコフモデルのパラメータを学習する機能を含む
ことを特徴とする請求項９記載の光学的情報読取プログラム。
【請求項１２】
前記画像コードには複数の規格が設けられ、
前記画像コードの規格における前記隠れマルコフモデルのパラメータを、対象とされる前記画像コードの規格ごとに予め記憶した記憶手段を用いる
ことを特徴とする請求項９記載の光学的情報読取プログラム。
【請求項１３】
請求項９〜１２のいずれか一つに記載の機能をコンピュータで実現するための光学的情報読取プログラムを、コンピュータで読み取り可能に記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えばバーコードリーダーに使用して好適な光学的情報読取装置、光学的情報読取方法、光学的情報読取プログラム及び記録媒体に関する。詳しくは、隠れマルコフモデル（Hidden Markov Model：ＨＭＭと略称）を用いることによって、特に読み取り距離の問題への対処を可能とし、より良好な読み取りを行うことができるようにするものである。
【背景技術】
【０００２】
バーコードの利点として、高い読取率と高い信頼性、非接触で読み取れること、ハードウェアの種類が豊富で安いこと、メディアの作成が容易で安い上に紙以外の材質でも使用できること、バーコードの内容を別に表示することによって人間も読めることなどが挙げられる。特に読取率と信頼性に関しては、レーザースキャンなどで多少品質の悪いラベルでも100％近い読取が可能であり、Code39と呼ばれる規格においてはチェックデジットなしで300万文字に１文字、チェックデジットありで１億4900万文字に１文字という誤読率のデータも存在する。
【０００３】
しかしながらバーコードの使用状況においては、バーコードそれ自体の汚れや傷、あるいは読み取り距離等が原因で、バーコードの信号が乱れたり、細バー・スペースの信号がつぶれたりする場合が生じる。これに対して従来の方法では、二値化後にバー・スペースの太さを判定することでデコードが行われている。従って、正しくバー・スペースの太さを判定することができない場合には、読取不能になったり、あるいは誤読をしたりしてしまう恐れがある。
【０００４】
そこで、従来の技術としては、例えばハイパスフィルタとローパスフィルタとを組み合わせて用いることにより、ノイズを除去する技術が開発されている（例えば、特許文献１参照。）。あるいは、フィルタリングの際に、ラプラス演算子等を用いた伝達関数を実現することにより、紙面ノイズを除去しているものも提案されている（例えば、特許文献２参照。）。
【０００５】
なおＨＭＭは、音源分離（例えば、特許文献３参照。）や音声認識（例えば、特許文献４，５参照。）、文字認識（例えば、特許文献６，７，８，９参照。）等の分野では従来から利用されているものである。しかしながら、ＨＭＭをバーコードの読み取りに応用した例は見出すことができなかった。
【０００６】
【特許文献１】特許第２７５２８７０号公報
【特許文献２】特開２００５−２９３３２７号公報
【特許文献３】特開２００３−９９０８５号公報
【特許文献４】特表２００４−５０９３６４号公報
【特許文献５】特開２００３−２８０６８６号公報
【特許文献６】特開平７−１６８９１３号公報
【特許文献７】特開２００７−７２７１８号公報
【特許文献８】特開平１１−２５０１８６号公報
【特許文献９】特許第３８９３０２２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来から光学的情報読取装置においては、特許文献１，２にも開示されているように、情報の正確な読み取りを行うための種々の技術が開発されている。しかしながら、これら特許文献１，２に開示された技術の目的は、いずれも汚損や表示面の状態によって生じるノイズの除去であって、例えば読み取り距離が原因となる細バー・スペースの信号のつぶれ等に対して正確な情報の取り出しを行うものではない。一方、より多くの情報を一度に読み込むためには、より遠くからバーコードが正確に読み取れる必要がある。
【０００８】
この発明は、このような問題点に鑑みて成されたものであって、本発明の目的は、より遠くからバーコードの読み取りを行う場合にも、正確な情報の取り出しを可能とするものであり、特に、隠れマルコフモデルを用いることによって、より正確な情報の取り出しが可能になるものである。
【課題を解決するための手段】
【０００９】
上記の課題を解決し、本発明の目的を達成するため、請求項１に記載された発明は、画像の明部及び／または暗部の配列により情報を形成する画像コードを読み取る光学的情報読取装置であって、検出枠を前記情報の配列方向に徐々に変化させて得られる信号の特徴量を検出する特徴量検出手段と、検出された特徴量の変化に基づいて隠れマルコフモデルを用いて情報を取り出す情報抽出手段と、を設けることを特徴とする光学的情報読取装置である。
【００１０】
請求項２に記載の光学的情報読取装置においては、特徴量は、検出枠を情報の配列方向に徐々に変化させて得られる信号の周波数パターンであることを特徴とするものである。
【００１１】
請求項３に記載の光学的情報読取装置においては、情報抽出手段は、画像の明部及び／または暗部の任意の配列により形成された画像コードにおける隠れマルコフモデルのパラメータを学習する学習手段を有することを特徴とするものである。
【００１２】
請求項４に記載の光学的情報読取装置においては、画像コードには複数の規格が設けられ、情報抽出手段は、画像コードの規格における隠れマルコフモデルのパラメータを、対象とされる画像コードの規格ごとに予め記憶した記憶手段を有することを特徴とするものである。
【００１３】
また、請求項５に記載された発明は、画像の明部及び／または暗部の配列により情報を形成する画像コードを読み取るための光学的情報読取方法であって、検出枠を情報の配列方向に徐々に変化させて得られる信号の特徴量を検出するステップと、検出された特徴量の変化に基づいて隠れマルコフモデルを用いて情報を取り出すステップと、を備えることを特徴とする光学的情報読取方法である。
【００１４】
請求項６に記載の光学的情報読取方法においては、特徴量は、検出枠を情報の配列方向に徐々に変化させて得られる信号の周波数パターンであることを特徴とするものである。
【００１５】
請求項７に記載の光学的情報読取方法においては、情報を取り出すステップは、画像の明部及び／または暗部の任意の配列により形成された画像コードにおける隠れマルコフモデルのパラメータを学習するステップを含むことを特徴とするものである。
【００１６】
請求項８に記載の光学的情報読取方法においては、画像コードには複数の規格が設けられ、画像コードの規格における隠れマルコフモデルのパラメータを、対象とされる画像コードの規格ごとに予め記憶した記憶手段を有することを特徴とするものである。
【００１７】
さらに、請求項９に記載された発明は、画像の明部及び／または暗部の配列により情報を形成する画像コードを読み取る機能を実現する光学的情報読取プログラムであって、検出枠を情報の配列方向に徐々に変化させて得られる信号の特徴量を検出する機能と、検出された特徴量の変化に基づいて隠れマルコフモデルを用いて情報を取り出す機能と、をコンピュータで実現することを特徴とする光学的情報読取プログラムである。
【００１８】
請求項１０に記載の光学的情報読取プログラムにおいては、特徴量は、検出枠を情報の配列方向に徐々に変化させて得られる信号の周波数パターンであることを特徴とするものである。
【００１９】
請求項１１に記載の光学的情報読取プログラムにおいては、情報を取り出す機能は、画像の明部及び／または暗部の任意の配列により形成された画像コードにおける隠れマルコフモデルのパラメータを学習する機能を含むことを特徴とするものである。
【００２０】
請求項１２に記載の光学的情報読取プログラムにおいては、画像コードには複数の規格が設けられ、画像コードの規格における隠れマルコフモデルのパラメータを、対象とされる画像コードの規格ごとに予め記憶した記憶手段を用いることを特徴とするものである。
【００２１】
請求項１３は、請求項９〜１２のいずれか一つに記載の機能をコンピュータで実現するための光学的情報読取プログラムを、コンピュータで読み取り可能に記録した記録媒体である。
【発明の効果】
【００２２】
本発明の光学的情報読取装置、光学的情報読取方法、光学的情報読取プログラム及び記録媒体によれば、バーコードの読み取りを行う場合に正確な情報の取り出しを可能とすることができ、特に隠れマルコフモデルを用いることによって、より遠くからの情報の取り出しをより正確に行うことができる。
【発明を実施するための最良の形態】
【００２３】
最初に、本発明に利用する隠れマルコフモデル（ＨＭＭ）、期待値最大化（Expectation Maximization：ＥＭと略称）アルゴリズム、Viterbiアルゴリズムの原理について予め説明する。
【００２４】
まず、今回利用する１次元ＨＭＭの構成について述べる。図３に示しているように、１次元ＨＭＭの構成は、大雑把に丸と線で表される。丸が状態であり、線が状態遷移を表すアークである。これが確率的に切り替わることで信号を表現することができる。ＨＭＭの構造である状態数や接続の仕方は自由であるが、対象の信号を考慮して経験的に判断するのが一般的である。図３の接続の仕方は、左から右への一方向の状態遷移のみ許されているタイプleft−to−rightのＨＭＭである。
【００２５】
各状態では、その状態に停留した際に信号を出力する。その各状態は出力確率を持っており、どのような値を出力するかはその確率分布に依存する。出力が有限な離散シンボルであれば、出力確率は各シンボルとその出力確率の表となる。一方、出力が連続な値である場合はガウス（正規）分布を用いる。より複雑な確率密度分布を表現するためには、ガウス混合分布を用いるのが一般的である。また、状態遷移は確率に従って生じる。よって、各アークには状態を遷移する際の確率が割り振られており、これを遷移確率と呼ぶ。
【００２６】
以上により、ＨＭＭを構成するパラメータは、各状態の出力確率（ｂi：ガウス分布であれば平均と分散）、状態遷移確率（ａij）、初期状態確率（タイプleft−to−rightのＨＭＭを使用する場合の状態１に遷移する確率は１）となる。これらのパラメータは、学習データからＥＭアルゴリズムを用いて推定することが可能であり、これがＨＭＭの学習である。そして、ひとたび全てのパラメータが決定すれば、入力時系列がそのＨＭＭから出力される確率（尤度）と最も確率の高い状態遷移（最尤パス）をViterbiアルゴリズムによって効率よく計算することが可能となる。
【００２７】
次に、ＥＭアルゴリズムについて説明する。先に述べたように、学習データから各状態遷移確率と出力確率（平均と分散）の２つを求める必要がある。ここでは、観測信号系列は与えられているが、状態系列は与えられていない場合にはＨＭＭのパラメータを推定する方法を説明する。まず、初期モデルλと観測された観測信号系列（Ｏ）を手がかりに、全ての状態系列（ＳT）についてその出力確率（Ｐ(ＳT｜Ｏ,λ)）を計算し、期待値に基づいて最尤パラメータを持つモデル▲∧λ（∧はλの上）▼の推定を行う。さらに、得られたモデルを初期モデルとして学習を繰り返すことで、より高い確率で学習データを出力しうるモデルの学習を行う。
【００２８】
しかし、実際に全ての状態系列に対して（Ｐ(ＳT｜Ｏ,λ)）を求めるためには、膨大な計算量が必要とされる。そこで、効率的に期待値を計算する前向き・後ろ向きアルゴリズム（ＦＢアルゴリズム）を用いることが一般的である。ＦＢアルゴリズムは、モデルと出力信号が与えられた下で、時間ｔにおいて、状態ｉに至る確率、α(t,i)（前向き確率(状態停留確率)）と、時間ｔに状態ｊを出発して時刻Ｔ＋１に状態Ｍ（終了状態）に到達する確率β(t,j)（後ろ向き確率）とを、あらかじめ計算しておくことで、計算量の削減を図る。
【００２９】
前向き確率α(t,i)は以下の漸化式で与えられる。
(1) 初期化
α(0,0)＝1.0                                                            (2.1)
α(t,i)＝0.0（1≦i≦M,1≦t≦T）                                         (2.2)
(2) 初期遷移
α(1,i)＝α0i（i＝1,...,M-1）                                            (2.3)
(3) 漸化式計算
【数１】
2009031857.tif 000003
(4) 最終遷移
【数２】
2009031857.tif 000004
【００３０】
後ろ向き確率β(t,j)は以下の漸化式で与えられる。
(1) 初期化
β(T+1,M)＝1.0                                                           (2.6)
(2) 漸化式計算
【数３】
2009031857.tif 000005
(3) 初期遷移
【数４】
2009031857.tif 000006
【００３１】
そして、前向き・後ろ向き確率の関係から、両者の積を求めることで時刻t において、状態m に停留する状態系列から信号系列O が出力される確率が計算される。
Ｐ(O,s(t)＝m｜λ)＝α(t,m)β(t,m)                                        (2.9)
さらに、同時確率と条件つき確率の関係より状態系列の出現確率は
【数５】
2009031857.tif 000007
となる。
【００３２】
ただし、系列の出現確率の和に関して
【数６】
2009031857.tif 000008
が成立しないので、期待値の計算の際には状態系列の出現確率の和で正規化を行う必要がある。
【００３３】
この状態の出現確率を元に、新たに最尤パラメータ推定を行うことで得られる新しいモデル▲∧λ（∧はλの上）▼は、初期モデルλに対して常に
【数７】
2009031857.tif 000009
が証明されている。
【００３４】
したがって、繰返し処理によってＨＭＭの学習を行うアルゴリズムは以下にまとめられる。
(1) 前向き確率、後ろ向き確率の計算
(2) 状態ごとの統計量の期待値を計算
【数８】
2009031857.tif 000010
【数９】
2009031857.tif 000011
【数１０】
2009031857.tif 000012
【００３５】
(3) 状態ごとのパラメータ更新
状態遷移確率は
【数１１】
2009031857.tif 000013
と与えられる。
【００３６】
また、たとえば出力確率が正規分布で与えられる場合、平均は
【数１２】
2009031857.tif 000014
分散は
【数１３】
2009031857.tif 000015
とパラメータが更新される。
【００３７】
(4) 収束の判定
あらかじめ定めた収束判定のしきい値ε に対して
【数１４】
2009031857.tif 000016
または、あらかじめ定めた繰返し回数以上学習を行うことが成立すれば終了。成立しなければ、(1)の処理に戻る。
【００３８】
以上のようにしてＨＭＭの学習が行われる。そこで以下には、上述のようにして与えられた信号系列を最も高い確率で生成する状態遷移系列を求める方法を説明する。
【００３９】
すなわち、最も高い確率で生成する状態遷移系列を求めるには、前向き確率α(t,i)と遷移元の状態を記憶するためのバックポインタＢ(t,i)を用いて、以下のように漸化的に行うことができる。
(1) 初期化
α(0,0)＝1.0                                                             (2.31)
(2) 初期遷移
Ｂ(1,i)＝0
α(1,i)＝a0i（1≦i≦M-1）                                                (2.32)
(3) 漸化式計算
【数１５】
2009031857.tif 000017
(4) 最終遷移
【数１６】
2009031857.tif 000018
【００４０】
また、バックポインタをたどることで、最大確率（尤度）状態系列ＳML＝ｓML(1),...,ｓML(T)は以下により求められる。
ｓML(T)＝Ｂ(T+1,M) 
ｓML(t-1)＝Ｂ(t,ｓML(t))   （t＝T,...,2）                                  (2.35)
ここで、求められた系列ＳMLはビタビ系列と呼ばれ、最大確率を与える状態系列に沿って確率を求める上述のアルゴリズムはViterbiアルゴリズムと呼ばれる。
【００４１】
本発明の光学的情報読取装置、光学的情報読取方法、光学的情報読取プログラム及び記録媒体は、以上に述べた隠れマルコフモデル（ＨＭＭ）、期待値最大化（ＥＭ）アルゴリズム、Viterbiアルゴリズムを利用してバーコードの読み取りを行う。以下には、その具体的な処理について説明する。
【００４２】
なお、以下の説明では、Code39と呼ばれる１次元のバーコードを取り扱う場合について詳解する。Code39は、図４に示すように、左クワイエットゾーン、スタートキャラクタ（スタートコード）、データを表すシンボルキャラクタ、ストップキャラクタ（ストップコード）、右クワイエットゾーンから構成される。データキャラクタ間にはキャラクタ間ギャップを設ける。
【００４３】
Code39の各シンボルは一連のシンボルキャラクタで構成され、そのキャラクタは９本（５本のバーとそれに挟まれた４本のスペース）からなる。各エレメント（バーとスペース）は「太(wide)」と「細(narrow)」の二種類の幅いずれかで表される。また、各キャラクタは、３個の太エレメントと６個の細エレメントによって構成され、３６種の全英数字と７種の記号の計４３種類の文字を表すことができる。図５に、Code39のキャラクタ割り当てを表す。
【００４４】
このようなCode39について、具体的な処理の流れを、図６を参照して説明する。
(1)ＨＭＭの基本パラメータを決める（ステップＳ１０１）
・状態数、混合数（混ぜる正規分布の数）、フレーム長とシフト幅（学習データを切り取る長さとフレームをずらす幅）、ｄｃｔ（直流を除いた低域側のＤＣＴ（Discrete Cosine Transform：離散コサイン変換）係数を取り出す数）を決める。これらの値は、上述の１次元ＨＭＭの構成について最初に述べたように観測信号を考慮して経験的に決定する。
【００４５】
(2)学習データの読み込み（ステップＳ１０２）
・取得し、４５種類のキャラクタ（スタート・ストップコード含む）ごとに切り分けた学習データを読み込む。
(3)学習データの正規化（ステップＳ１０３）
・スタートコードのクワイエットゾーン１００個分の平均値を元に、学習データを正規化する。
(4)フレーム化処理（ステップＳ１０４）
・学習データをシフトさせながら、フレームごとに分割する。分割した後、各フレームのエネルギーで正規化をする。
【００４６】
学習データｓ(n) にフレーム長Ｎごとに切り分けると、フレームごとの学習データｓW (m;l)は以下のように与えられる。
【数１７】
2009031857.tif 000019
ここでは、Ｔがシフト幅、ｌがサンプルの切り出し位置に対応している。ｌを一定間隔Ｔ増加させることで、定常とみなされる長さＮのフレームごとの学習データｓW(n) （n=0,…,N-1）が間隔Ｔで得られる。
【００４７】
正規化は以下のように与えられる。
【数１８】
2009031857.tif 000020
【００４８】
(5)ＤＣＴ変換（ステップＳ１０５）
・フレーム化処理をした学習データをＤＣＴ変換する。特徴量として、ｄｃｔの値分だけ取り出した直流を除いた低域側のＤＣＴ係数とその差分、計２×ｄｃｔ次元の特徴ベクトルを使用する。
【００４９】
(6)初期モデルのパラメータを決める（ステップＳ１０６）
・初期モデルのパラメータは、特徴量、状態数、混合数からランダムに決める。
初期確率：状態１に遷移する確率１になる。
状態遷移確率：同じ状態に遷移する確率を0.99、次の状態に遷移する確率を0.01、最終状態で遷移し続ける確率を１とする。なお、確率は合計が１であれば任意の値でよい。
【００５０】
分散：特徴量を転置させ、その行列の共分散行列を求める。さらに対角行列にして、0.5をかける。その値を分散とする。
平均：特徴量の列に入っている値をランダムに入れ替えた行列を平均とする。
混合重み：混合重みは（2.28）の条件を満たしつつ、ランダムに値を入れたものを混合重みとする。
【００５１】
(7)ＥＭアルゴリズム（ステップＳ１０７）
・(6)の処理で求めた初期モデルと前述のＥＭアルゴリズム、Viterbiアルゴリズムより、平均・分散・混合重み・状態遷移確率・尤度を求める。収束条件は、ＥＭアルゴリズムの繰り返し回数が１００回になるか、更新した尤度と前の尤度との差を更新した尤度と前の尤度との平均で割った値がしきい値exp-4より下になるかである。
【００５２】
【数１９】
2009031857.tif 000021
上式のlog-likは更新した尤度、pre-log-lik は前の尤度、Δlog-likは更新した尤度と前の尤度との差、ave-log-lik は更新した尤度と前の尤度との平均で割った値である。
【００５３】
(8)ＨＭＭモデル生成（ステップＳ１０８）
・求めたパラメータ（平均・分散・混合重み・状態遷移確率・初期確率・状態数・混合数・フレーム長とシフト幅・dct）をＨＭＭモデルとする。その後、(6)の処理まで戻り、同様の処理を繰り返す。再び求めたＨＭＭモデルの尤度と前のＨＭＭモデルの尤度を比較し、尤度が高いＨＭＭモデルのほうを更新させる。繰り返し回数は事前に設定される。
【００５４】
さらに、(6)〜(8)の処理をキャラクタデータ（学習）ごとに行い、全てのキャラクタＨＭＭモデルを生成する（注：どのキャラクタＨＭＭモデルから生成するかは自由であるが、最初のキャラクタＨＭＭモデルはスタートコードである必要がある。また、スタートコードとストップコードは別のデータとして分けている）。
【００５５】
次に読み取り(デコード)処理について、図７を参照して説明する。
(1)ＨＭＭモデルと認識データの読み込み（ステップＳ１１１）
・生成したキャラクタごとのＨＭＭモデルと認識データを読み込む。
(2)認識データの正規化（ステップＳ１１２）
(3)フレーム化処理（ステップＳ１１３）
(4)ＤＣＴ変換（ステップＳ１１４）
・ＨＭＭモデル生成処理のときと同様に認識データの正規化、フレーム化処理、ＤＣＴ変換を行う。
【００５６】
(5)認識データの尤度を求める（ステップＳ１１５）
・Viterbiアルゴリズムを用いて、キャラクタＨＭＭモデルごとにキャラクタデータ（認識）の尤度を求める。
(6)キャラクタデータ（認識）のデコード（ステップＳ１１６）
・(5)の処理で求めたキャラクタＨＭＭモデルごとの尤度の中で最も高い尤度をそのキャラクタであるとデコードする。
そして(5)〜(6)の処理を全てのキャラクタデータ（認識）で行う。
【００５７】
(7)バーコードのデコード（ステップＳ１１７）
・求めた各キャラクタデータ（認識）のデコード結果を組み合わせて、バーコード全体の内容を表現する。
なお、図８にはキャラクタ単位の認識手法の概念を示し、図９にはキャラクタＨＭＭによるバーコード全体の表現の概念を示す。
【００５８】
さらに、本発明で特徴量として使用したＤＣＴについて説明する。ＤＣＴとは、離散フーリエ変換の一種であり、実数になる信号から実数からなる係数への変換を行う。ＤＣＴでは元の関数に対し鏡像部分を加え、偶関数に変換した上で処理するので、係数が実数になる上、特定の成分への集中度が上がる（特に低域側に集中する傾向にある）。そのため、ＤＣＴは画像圧縮、音声圧縮、デジタルフィルタ等広い範囲で用いられている。
【００５９】
そこで、バーコードの信号ではＤＣＴがどのように働くかを見る。図１０、図１１は実際に実験で使用したキャラクタ「Ｏ」「Ｊ」のバーコードの信号を波形にしたものと、ＤＣＴ2nd（フレーム長：８０、シフト幅：８）を波形にしたものである。どちらのキャラクタを比べてみても、４５cmのほうが解像度は高いので、５０cmの波形が乱れていたり、細バー、スペースの信号がつぶれたりしていることがわかる。
【００６０】
それでも、ＤＣＴ2ndの波形では共に似た傾向になることが見て取れる。また、キャラクタ「Ｏ」とキャラクタ「Ｊ」のように似た波形でも、ＤＣＴ2ndの波形に違い（係数の特徴の違い）が現れることが理解できる。以上のことより、ＤＣＴ係数による特徴量を元にＨＭＭで学習させることによって、キャラクタごとの特徴を保持し、正しく読み取ることが期待できる。
【００６１】
以上の点を踏まえて、以下には、図面を参照しながら本発明による光学的情報読取装置の具体的な構成を説明する。
【００６２】
図１にはスキャナ部１００の具体的な構成を示す。ここでは発光素子１０１からの光線がバーコード３００に照射され、その反射光がレンズ１０２を介してＣＣＤ１０３で撮像される。また、これらの発光素子１０１、レンズ１０２、ＣＣＤ１０３が筐体１０４内に設けられる。さらに、ＣＣＤ１０３によって得られた情報は、ＣＰＵ部１０５を含むデコード基板１０６に供給される。
【００６３】
すなわち、このＣＣＤ１０３によって得られた情報をＣＰＵ部１０５で処理する手法も本発明の主要な点となるものである。この処理は、バーコード３００の情報を、ＨＭＭ等を用いて高密度化するものであり、バーコードの読み取りをより遠距離から高精度に行うことを可能とする。なお、バーコードには様々な種類が存在するが、本発明は、基本的には既存のどの種類のバーコードに対しても適用可能とされる。
【００６４】
図２には、上述したデコード基板１０６の構成を模式的なブロック図で示す。図２において、入力装置としてのＣＣＤ１０３で撮影された入力画像はデコード基板１０６上に設けられるメモリ１０７の入力画像バッファ１７１に記憶される。
【００６５】
この入力画像バッファ１７１に記憶された入力画像がＣＰＵ部１０５のバーコード領域抽出部１５１に供給される。バーコード領域抽出部１５１では、例えば画像の二値化（ステップＳ１）、エッジの抽出（ステップＳ２）、画像をブロックに分割（ステップＳ３）、ブロック内のエッジ数カウント（ステップＳ４）、バーコードの存在領域候補決定（ステップＳ５）、ラベリングによるバーコード領域抽出（ステップＳ６）等の処理が行われる。そして抽出されたバーコード領域の画像が、メモリ１０７の抽出バーコード画像バッファ１７２に記憶される。
【００６６】
抽出バーコード画像バッファ１７２に記憶された抽出バーコード画像は、ＣＰＵ部１０５の特徴抽出部１５２に供給される。特徴抽出部１５２では、例えばクワイエットゾーンによる正規化（ステップＳ７）、フレーム化（ステップＳ８）、ＤＴＣの計算（ステップＳ９）などの処理が行われる。そして抽出された特徴量が、メモリ１０７の抽出特徴量バッファ１７３に記憶される。
【００６７】
抽出特徴量バッファ１７３に記憶された抽出特徴量は、ＣＰＵ部１０５のＨＭＭデコード部１５３に供給される。また、例えば外部記憶装置１０８にあらかじめ設定されている学習済み（キャラクタ）モデル（ＨＭＭ）の情報が読み込みバッファ１７４に記憶され、読み込みバッファ１７４に記憶された学習済み（キャラクタ）モデル（ＨＭＭ）の情報が、ＣＰＵ部１０５のＨＭＭデコード部１５３に供給される。
【００６８】
そして、ＨＭＭデコード部１５３では、まず、抽出特徴量バッファ１７３からの抽出特徴量、及び読み込みバッファ１７４からの学習済み（キャラクタ）モデル（ＨＭＭ）の情報に基づいてスタートコードのビタビアルゴリズムによるデコード（ステップＳ１０）を行う。次に、ビームサーチと状態継続長による枝狩りを行いながらビタビアルゴリズムとキャラクタの接続による仮説生成を繰り返す（ステップＳ１１）。
【００６９】
このステップＳ１１の繰り返しは、ストップコードのビタビアルゴリズムによるデコード（ステップＳ１２）まで行う。さらに、尤度が閾値より小さい場合は結果を破棄し読み取り不能とする（ステップＳ１３）。そしてデコードされたキャラクタが、メモリ１０７のバーコード読み取り結果バッファ１７５に記憶される。さらに、バーコード読み取り結果バッファ１７５に記憶された情報が出力装置１０９に取り出される。
【００７０】
このようにして、本発明の光学的情報読取装置によれば、検出枠を情報の配列方向に徐々に変化させて得られる信号の周波数パターンを検出し、検出された周波数パターンの変化に基づいて隠れマルコフモデルを用いて情報を取り出すことによって、読み取り距離が原因となる細バー・スペースの信号のつぶれ等に対しても正確な情報の取り出しを行うことができ、より遠くからバーコードの読み取りを行う場合にも、正確な情報の取り出しを可能とすることができる。
【００７１】
なお、上述のデコード基板１０６の構成において、バーコード領域抽出部１５１及びＨＭＭデコード部１５３の手法は図示のものに限られない。また入力装置はカメラでなく、レーザースキャナでもよい。
【００７２】
さらに、モデル単位はキャラクタに限定されるものではない。すなわち、キャラクタを構成しているバー・スペースの組み合わせを複数に分解し、それぞれの分解された部分をモデル単位としてＨＭＭによるデコードを行うことができる。そこで、例えば上述のCode39について考察すると、コードは９本のバー・スペースによって構成され、それによって表されるキャラクタの種類は４４であり、モデル単位をキャラクタとした場合には、これら４４通りについてそれぞれＨＭＭの学習や解析を行う必要がある。
【００７３】
これに対し、９本のバー・スペースを３本ずつに分解して３本をモデル単位とすると、３本の組み合わせはバー（Ｂ）・スペース（Ｓ）・バー（Ｂ）と、スペース（Ｓ）・バー（Ｂ）・スペース（Ｓ）の２通りであり、さらにワイドを１、ナローを０で表すと、図１２に示すようになる。ここで、図５のパターン表によればスペース（Ｓ）・バー（Ｂ）・スペース（Ｓ）の組み合わせが全てワイドとなることはないので、デコードすべき３本のモデル単位の組み合わせは１５通りである。
【００７４】
このように、上述のCode39は、９本のバー・スペースを３本ずつに分解して３本をモデル単位とすることで、モデル単位をキャラクタとした場合には４４通りについて必要であったＨＭＭの学習や解析を１５通りに減少させることができる。ただし、本来Code39は可変長コードであるが、その場合に複数キャラクタが結合していると、３本ずつの分解では対応できないことになる。
【００７５】
そこで、複数キャラクタが結合している場合にも適応させるためには、キャラクタ間のギャップを含めて１０本のバー・スペースで検討しなければならない。このような１０本のバー・スペースに対してこれを分解するには、まず５本ずつの分解が考えられる。しかしその場合のモデル数は３３通りであり、モデル単位をキャラクタとした場合の４４通りからそれほど減少しないことになる。
【００７６】
これに対して、モデル単位を３−３−４本とするとモデル数は２３通りとなり、ＨＭＭの学習や解析を行う計算量をかなり減少させることができる。このように、キャラクタを構成しているバー・スペースの組み合わせを複数に分解し、それぞれの分解された部分をモデル単位としてＨＭＭによるデコードを行うことで、学習や解析を行う計算量を減少させることができる。
【００７７】
さらに、モデル単位を４−４−２本とするとモデル数は１５通りとなるが、右端の２本の部分でモデル内での変化が少ないので特徴量の算出が困難であると考えられる。同様に、モデル単位を２−２−２−２−２本とするとモデル数は４通りとなるが、特徴量の算出が困難であると考えられる。ただし、２本での特徴量の算出が可能であれば、これらの分解も有効である。なお、モデル単位を１本とした場合には、モデル数は２通りとなるが、モデル内での変化が生じないので特徴量の算出は不可能である。
【００７８】
一方、上述の実施形態例では、主に１次元のバーコードの読み取りについて説明してきたが、近年バーコードにおいては２次元のものも用いられている。そのような２次元バーコードに対しても、本発明を適用することが可能である。すなわち、例えば図１３Ａに示すような２次元バーコードをＣＣＤカメラ等で撮影すると、その撮影距離が長い場合や解像度が低いときには図１３Ｂに示すような画像になってしまう。
【００７９】
ここで、２次元コードをデコードするためには、バーコードを構成する最も小さい単位（モジュール）の黒白を判定すればよい。この最小単位であるモジュールのサイズは２次元コードの中では同じであるから、縦もしくは横のラインをモジュールサイズ毎にスキャンすることによって、１次元のパターン（スキャンライン）に分解することができる。モジュールのサイズは、画素値をｘ軸もしくはｙ軸に射影しその微分がゼロとなる点を抽出することで計算できる。
【００８０】
そしてこのような１次元スキャンラインに分解後は、ＨＭＭを用いた１次元バーコードのデコード手法をそのまま利用することが可能である。但しモデルの単位は、キャラクタ単位ではなく、例えば４ビット分の白黒のパターン（計１６通り）などを用いる。さらに、図１４にこの手法の概念図を示す。
【００８１】
すなわち、例えば図１４Ａに示すような２次元バーコードに対して、ｘ軸方向への画素値射影は図１４Ｂに示すようになる。この射影を微分すると、モジュールの位置で微分値はゼロとなる。そこで、この微分値がゼロとなる位置のスキャンラインの波形は図１４Ｃに示すようになり、このスキャンラインを用いてデコードを行うことができる。なお、図１４では、縦方向に分解しているが、横方向の分解も可能であり、両方向を併用してより精度を向上させることができる。
【００８２】
また別の方法として、２次元をコード２次元のブロックに分解し、２次元ＨＭＭを用いて認識することもできる。この際にも、まずピクセル値のｘ軸方向とｙ軸方向への射影を利用して、１モジュールのサイズを判定する。１モジュールのサイズが分かればあとは、ＨＭＭのモデル化を行ったブロックサイズで２次元コードをブロック化し、各々のブロックを２次元ＨＭＭでパターン認識すればよい。
【００８３】
２次元のパターン認識では、特徴の抽出として２次元ＤＣＴやＦＦＴを用いる。ＨＭＭは横方向と縦方向それぞれが１次元ＨＭＭで構成される擬似的な２次元ＨＭＭを用いる。モデルの単位は、１次元分解のときと同様に、キャラクタ単位ではなく、例えば４×２のブロックに分解するのであれば、８ビット分のパターンとなる。
【００８４】
すなわち、図１５にはブロック分解によるデコードの概念図を示す。図１５Ａは撮影された２次元バーコードの画像であって、この画像から図１５Ｂに示すように４×２のブロックに分解する。そして２次元ＨＭＭによるデコードを行うことにより、図１５Ｃに示すような８ビット分のモデルで最も尤度の高いパターンを得ることができる。
【００８５】
さらに、分解した４×２のブロックに対しては、例えば図１６Ａに示すように窓をジグザグに移動して特徴量の算出を行う。そして、図１６Ｂに示すように、この特徴ベクトルの２次元配列に対して２次元ＨＭＭを適用して、分解した各ブロックの擬似２次元ＨＭＭによる認識を行うことができる。
【００８６】
なお、上述の説明では、ＭＨＨの演算を行う特徴量として周波数パターンを用いたが、その他にも、例えば実際のバーコードデータに対して主成分分析をすることで得られる基底関数を利用して、その基底関数による展開係数を特徴量とする。あるいは、フレーム内のゼロクロスの数や微分値のヒストグラムなどの特徴をとることも考えられる。
【００８７】
こうして本発明の光学的情報読取装置、光学的情報読取方法、光学的情報読取プログラム及び記録媒体によれば、隠れマルコフモデル（ＨＭＭ）を用いることによって、特に読み取り距離の問題への対処を可能とし、より良好な読み取りを行うことができるようになる。
【００８８】
そして本発明によれば、実際に入力されるパターンを学習しておくことでどのような距離のものでも対処が可能となる。ＨＭＭを用いた確率的手法によりノイズや距離の変動によるばらつきに強くなる。波形を直接用いるのではなく、特徴量を用いることでノイズへの対処や次元の削減を行うことができ、パターン識別の精度が向上する等の、従来の技術にはない作用効果を生むことができる。
【００８９】
さらに本発明においては、ＨＭＭを用いることで、既存のバーコードでなくても、ユーザが任意のパターンと正解コードの組を学習データとして与えることで、簡単に読み取り器を構成することができる。また、本発明に係る装置を考えた場合には、従来と全く同じ構成のままでも実行プログラムを変更すれば、本発明の内容を実現することが可能となるものである。
【００９０】
なお、本発明は、上述の説明した実施形態に限定されるものではなく、特許請求の範囲の記載を逸脱しない範囲において、種々の変形が可能とされる。
【図面の簡単な説明】
【００９１】
【図１】本発明の適用される光学的情報読取装置のスキャナ部１００の具体的な構成を示す図である。
【図２】そのデコード基板１０６の構成を示す模式的なブロック図である。
【図３】隠れマルコフモデル（ＨＭＭ）の説明のための図である。
【図４】バーコードの一例であるCode39の説明のための図である。
【図５】その説明のための図である。
【図６】本発明の説明のためのフローチャート図である。
【図７】本発明の説明のためのフローチャート図である。
【図８】隠れマルコフモデル（ＨＭＭ）の説明のための図である。
【図９】隠れマルコフモデル（ＨＭＭ）の説明のための図である。
【図１０】ＤＣＴ（離散コサイン変換）の説明のための図である。
【図１１】ＤＣＴ（離散コサイン変換）の説明のための図である。
【図１２】バーコードを分解して処理を行う場合の説明のための図である。
【図１３】２次元バーコードの場合の説明のための図である。
【図１４】２次元バーコードの場合の説明のための図である。
【図１５】２次元バーコードの場合の説明のための図である。
【図１６】２次元バーコードの場合の説明のための図である。
【符号の説明】
【００９２】
１００…スキャナ部、２００…端末、３００…バーコード、１０１…発光素子、１０２…レンズ、１０３…ＣＣＤ、１０４…筐体、１０５…ＣＰＵ部、１０６…デコード基板、１０７…メモリ、１０８…外部記憶装置、１０９…出力装置
【図１】
2009031857.tif 000022
【図２】
2009031857.tif 000023
【図３】
2009031857.tif 000024
【図４】
2009031857.tif 000025
【図５】
2009031857.tif 000026
【図６】
2009031857.tif 000027
【図７】
2009031857.tif 000028
【図８】
2009031857.tif 000029
【図９】
2009031857.tif 000030
【図１０】
2009031857.tif 000031
【図１１】
2009031857.tif 000032
【図１２】
2009031857.tif 000033
【図１３】
2009031857.tif 000034
【図１４】
2009031857.tif 000035
【図１５】
2009031857.tif 000036
【図１６】
2009031857.tif 000037