JPH0812681B2

JPH0812681B2 - バーコードを認識する方法

Info

Publication number: JPH0812681B2
Application number: JP3060763A
Authority: JP
Inventors: ピーター・ジョン・サマヴイル
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1990-03-29
Filing date: 1991-02-12
Publication date: 1996-02-07
Anticipated expiration: 2011-02-07
Also published as: JPH04225485A; EP0448945A3; EP0448945A2; US4992650A

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はデータ処理システムに係
り、更に詳細に説明すれば、バーコード認識の改良に係
る。

【０００２】

【従来の技術】ディジタル画像技術の分野では、ディジ
タル・イメージ・ファイル中のビット・パターンを走査
して、このディジタル・イメージに関連するコード化情
報を生成するという一般的な要請が存在する。このコー
ド化情報は、後に記憶装置からのピクチャの検索を容易
にするように、ディジタル・イメージを分類するために
使用されるものである。

【０００３】最近のディジタル走査機構は、１秒以下の
時間で１ページの文書を走査することができる。もっと
も、オペレータがこのイメージ表示を観察した上で、関
係するコード情報をキー入力しなければならない場合に
は、実効的な捕捉速度は１５−２０秒の程度になる。こ
れではオペレータの生産性が低下するだけでなく、画像
アプリケーションの運用費用が著しく高価になってしま
う。

【０００４】光学文字認識（ＯＣＲ）は、イメージ中の
ノイズに極めて感じやすく、しかもテキスト文字を表す
そのディジタル・イメージ・データには冗長性が殆どな
いために、９８％よりも高い認識精度を実現することは
困難である。このことは、例えばファクシミリ装置から
生ずる低分解能のディジタル・イメージについて、特に
当てはまる。

【０００５】光学式マーク読取（ＯＭＲ）は、相当長い
期間にわたって、高い信頼性を以てイメージを機械的に
分類するのに使用されてきた。この技術の欠点は、イメ
ージ全体がＯＭＲデータであるという理由で、ＯＭＲペ
ージを含むセット内の関連するイメージを分類するため
にのみ、コード化データを使用できるに過ぎないという
点にある。

【０００６】今日では、１５−２０種類もあるバーコー
ドが、多くの物品（食品雑貨類、化粧品、文房具、等）
で利用されている。バーコードは、汎用の印刷装置を使
用して容易に印刷することができる。バーコードを十分
に控え目に印刷した文書を走査して、これをディジタル
画像システムへ取り込む場合、かかるバーコードは当該
ページの一部を構成することになるから、そのコード化
データを別途抽出する必要がある。

【０００７】解決すべき問題は、ディジタル・イメージ
を表すデータに含まれているバーコードの存在を見つ
け、これを対応するコード化データに変換することであ
る。この場合の要件は、１００％の認識精度を得るか又
は認識失敗の表示を与えることである。このコード化デ
ータは分類のために使用されるから、各文字の部分的な
認識又は代用は許されない（“ＴＨＥＲＥ”の代りに
“ＨＥＲＥ”を認識することは受け入れられない）。

【０００８】この要件を満足するには、（バーコードが
現われる文書上に何かが書き込まれる場合のように）偶
然又は故意の損傷が生じた場合であっても、バーコード
の認識を可能にしなければならない。また、イメージ捕
捉プロセス中に生ずることがある相当な量のスキュー
も、許容しなければならない。

【０００９】

【発明が解決しようとする課題】本発明の目的は、ディ
ジタル・イメージを表わすデータに含まれているバーコ
ードの存在を見つけるための改良された方法を提供する
ことにある。本発明の他の目的は、ディジタル・イメー
ジを表わすデータに含まれているバーコードの存在を見
つけて、これを対応するコード化データに変換するため
の改良された方法を提供することにある。本発明の他の
目的は、ディジタル・イメージを表わすデータに含まれ
ているバーコードの存在を見つけて、これをほぼ１００
％の精度で認識するための改良された方法を提供するこ
とにある。本発明の目的は、ディジタル・イメージを表
すデータに含まれているバーコードの特徴が不明瞭であ
っても、当該バーコードの存在を見つけて、これを対応
するコード化データに変換することにある。本発明の他
の目的は、ディジタル・イメージを表すデータに含まれ
ているバーコードにかなりのスキューがあっても、当該
バーコードの存在を見つけて、これを対応するコード化
データに変換することにある。

【００１０】

【課題を解決するための手段】本発明の処理対象は、個
々のバーコード・エレメントを識別可能なスペース分解
能でディジタル的に走査した、ハード・コピーのページ
である。ディジタル的に走査した当該ページのイメージ
は、このページ上の黒マークと白マークを表す２レベル
のビット・ストリングによって表される。このビット・
ストリングを、標準的な圧縮アルゴリズムを使用して圧
縮する。本発明の１つの特徴は、認識モジュールと呼び
出し環境との組み合わせにある。この呼び出し環境は、
認識すべきバーコードのタイプと、このバーコードを識
別して解読する際に使用すべき戦略とに関する情報を供
給する。

【００１１】大きさ“ｘ”のＮラスタ・ラインについ
て、大きさ“ｘ”の１バイト和（ｓｕｍ）のアレイを生
成する。これらの和は、当該イメージのＮラインにある
矩形２値イメージ入力アレイ中の“１”ビットを合計し
たものである。ここで、「大きさ」とは、行方向の大き
さ（ディメンション、長さ又は幅）を意味するものとす
る。

【００１２】黒又は白スペースの各ランの長さ（ラン・
レングス）を決定するために、一のスレッショルド値を
設定する。もし、前記和アレイからの一のエレメントの
値が当該スレッショルド値よりも大きければ、このエレ
メントが黒であると推定する。一方、このエレメントの
値が当該スレッショルド値よりも小さければ、このエレ
メントが白であると推定する。次に、当初の“ｘ−ｙ”
ディジタル・イメージにおける黒から白への遷移の数に
等しい大きさを有する、新しいアレイを生成する。この
アレイ中のそれぞれのエレメントの値は、同じ色のペル
（画素）を持つ各ラン・レングスを表す。

【００１３】次に、これらのランを、処理中の特定のバ
ーコード規格の規則に従って正規化する。例えば、この
バーコードが９者択３コードであれば、バーコード化し
た各文字ごとに、（９個のエレメント＋１個の文字分離
記号）がある。また、有効な各バーコードを区切るため
の、１個の開始文字と１個の終了文字もある。９者択３
コードの正規化プロセスは、前のステップで生成したア
レイからの最初の黒のランで開始して、最初の１０個の
エレメントの値を合計する。もし、個別的な任意のエレ
メントの値が、呼び出し環境で定義したスレッショルド
値の範囲外にあれば、これらのランは、有効なバーコー
ドのイメージを表さない。一方、これらの１０個のエレ
メントの値の和が、呼び出し環境で定義したスレッショ
ルド値の範囲内になければ、この場合も、これらのラン
は有効なバーコードを表さない。もし、最初の１０個の
エレメントの値の和がこれらのテストに合格すれば、こ
の和を、処理中のバーコードのスペース・エレメントの
総数に関係する一の値で除算する。例えば、９者択３コ
ードでは、１６個のスペース・エレメント、すなわち７
個のシングル幅と３個のトリプル幅があるから、除数と
して１６を用いることができる。この被除数は、このバ
ーコードにおける各スペース・エレメントのペル幅を表
す。

【００１４】この被除数から２個のスレッショルド値を
計算して、これらの値を正規化プロセスのために使用す
る。

【００１５】正規化プロセスの最後の部分は、ラン・レ
ングスを表す前記アレイと同じ大きさを有する、新しい
アレイを生成するものである。このアレイにおける各エ
レメントは、それぞれのラン・レングスを、黒又は白の
スレッショルド値で除算した被除数に相当する。

【００１６】正規化プロセスの最後のステップは、正規
化済みのＭエレメントの表示から成る１６ビット・ワー
ド内に、一の索引値を生成することを含む。但し、Ｍ
は、各バーコード文字における物理エレメントの数であ
る。次に、この索引値を、当該バーコード・タイプ用の
有効な値のテーブルと突き合わせる。もし、有効な値が
見つかれば、、次のセットのエレメントについて、正規
化プロセスを反復する。一方、有効な値が見つからなけ
れば、正規化プロセスを、ラン・アレイにおける次の黒
のラン・エレメントの箇所で再開し、そして完全に有効
なバーコードが見つかるか又は当該イメージ・アレイが
完全に処理されるまで、正規化プロセスを反復する。

【００１７】

【実施例】図１は、９者択３バーコードの１つの例とし
て、３文字の“ＩＢＭ”をコード化したデータを示して
いる。開始／終了文字として、アステリスク（“＊”）
記号を使用する。４本の縦線が文字間スペースの位置を
示し、“＊”を“Ｉ”から分離し、同様に“Ｉ”を
“Ｂ”から、“Ｂ”を“Ｍ”から、“Ｍ”を“＊”から
分離する。図１のバーコードの上部と左側にある小さな
黒の四角形は、当該ページ・イメージ中の他の情報を表
している。図１の例は、全ての黒のバーが完全であり且
つ白のスペースには黒のノイズが存在しないという意味
で、良好で明瞭なイメージに相当する。図１は、一のバ
ーコードを含む一のイメージ・ページの内容を表すもの
である。

【００１８】図２は、走査オペレーションの後のディジ
タル・イメージを、ペルの“行”と“列”によって表し
たものを示している。図２には、１−６と表記した６個
の連続するバーコード“行”と、行−１０とが示されて
いる。行−１０は、当該イメージ中の先行する点におけ
るイメージ・データを示すものである。“列”について
は、列１００−列３００からの２００個の列が取られて
いる。

【００１９】図３は、図２のディジタル・イメージが
“損傷”している場合の１つの例を示している。垂直の
黒のバーでは、幾つかの“黒”の領域が欠落しており、
また白のスペースには、黒のノイズがある。図５は、図
３の行１−６及び列１００−１４１の拡大図を示してい
る。図６は、図５のイメージが“スキュー”した場合の
１つの例を示している。列１２１からは、ペルが１行分
だけ上がっている（５％のスキューに相当）。行４から
は、ペルが１列分だけ右に寄っている（３３％のスキュ
ーに相当）。

【００２０】本発明は、ＩＢＭシステムで走行するソフ
トウェアを使用して、この問題を解決するものとして説
明されている。その実現形態は、インテル製のｘ８６プ
ロセッサ上で走行する。もっとも、本発明の手法は、ビ
ット・ストリングを処理可能な全てのプログラム式計算
機（例えば、６８０００、ＰＣ／ＲＴ、システム／３７
０、ＡＳ／４００）にも適用することができる。

【００２１】最初のイメージ・ピックアップ段階では、
個々のバーコード・エレメント（黒／白の遷移）を識別
可能なスペース分解能で、一のページをディジタル的に
走査する。これは、少なくとも２００ペル／インチの
（水平方向バーコード用の）水平分解能を暗示する。以
下で詳述するプロセスが、当該イメージ・ページを表す
２レベルのビット・ストリングに作用する。ＩＢＭＭ
ＭＲ圧縮アルゴリズム又はＣＣＩＴＴＧ４ＭＭＲ方
法を使用して、このビット・ストリングを圧縮する。ビ
ット・ストリングの適切な圧縮手法は、米国特許第４６
４６３５６号明細書に記載されている。

【００２２】本発明の１つの特徴は、バーコード認識用
のカーネル・コンピュータ・プログラム方法と、認識す
べきバーコードのタイプ及び使用すべき戦略パラメータ
に関する情報を供給する呼び出し環境との組み合わせに
ある。本発明は、このカーネルに対し、圧縮済みイメー
ジのバッファをも提供する。

【００２３】以下では、カーネル・コンピュータ・プロ
グラム方法と呼び出し環境とを説明する。

【００２４】バーコード認識カーネル入力 − 大きさ（“ｘ”ペル）×（“ｙ”ペル）を有する圧縮済
みの２レベルのイメージ・データを保持する処の、バッ
ファに対するポインタ。この説明の対象となる例は、図
３のバーコードの一部分として図５に示されている。＊図４の表に示されている一連の戦略値。

【００２５】出力 − ＊文字値＊成功又は失敗を示す戻りコード。

【００２６】プロセス − １．圧縮済みイメージの一のラスタ・ラインを、ラン・
エンドへ部分的に圧縮解除する（図７はこの圧縮解除の
典型的な結果を示している）。２．このラインが、有効なバーコードを含むか否かを判
定する。図４は、この例で使用すべき幾つかの戦略値を
示している。ａ．このラインには、少なくとも定義された数のラン・
エンドが存在しなければならない。作業中の例について
は、バーコード中の最小の文字数が４と定義されてい
て、その各文字が１０個のエレメントを有すると定義さ
れているから、考察中の領域には少なくとも４＊１０
（＝４０）個のラン・エンドが存在しなければならな
い。ｂ．この数のラン・エンドによって囲まれたペルは、或
る範囲内に入らなければならない。作業中の例について
は、４＊１０のラン・エンドによって囲まれた最小数の
ペルが（１＊１６＊４＝６４）であり、最大数のペルが
（６＊１６＊４＝３８４）でなければならない。

【００２７】図７のラン・エンド＃４０はこれらの要件
に適合するので、このラインは、以後の処理を受けるこ
とになる。もし、このテストに成功しなければ、ステッ
プ１に戻る。

【００２８】図５の例は、当該イメージ・ページの残り
の部分から分離されたバーコードだけを示しているに過
ぎない。実際には、このバーコードは圧縮解除済みの表
（図７）におけるラスタ・ラインの開始点にはないの
で、前記ステップ２でこのラインの探索が行われる。こ
れが非常に速い検査である所以は、この表が２バイト・
ワードの対（白のラン・エンド、黒のラン・エンド）か
ら成り、そしてｎ番目とｎ＋（４０＊２）番目との間の
差が、前記のスレッショルド値（例えば、６４と３８
４）と比較されるからである。各バーコードの開始点
は、白のラン・エンド（黒の開始点）によって表される
ことが知られている。この点において、潜在的に有効な
バーコードを有する行が存在する。

【００２９】３．大きさ“ｘ”の“ｎ”ラスタ・ライン
について、大きさ“ｘ”の１バイト和のアレイを生成す
る。これらの和は、当該イメージの“ｎ”ラインにおけ
る矩形２値イメージ入力アレイ中の“１”ビットを合計
したものである。図８は６ラインの部分的なラン・エン
ドを示し、そしてこれらのラン・エンドが図９に示すよ
うに合計される。

【００３０】４．合計されたラインの数から導かれた一
のスレッショルド値を使用して、黒又は白の各ラン・レ
ングスを決定する。もし、前記和アレイの一のエレメン
トの値が当該スレッショルド値よりも大きいか又はそれ
に等しければ、このエレメントが黒であると推定する。
一方、当該スレッショルド値よりも小さければ、このエ
レメントが白であると推定する。この段階で、新しいア
レイを生成する（図１０）。このアレイは、元の“ｘ”
幅のディジタル・イメージにおける黒から白への遷移の
数に等しい大きさを有する。このアレイ内のそれぞれの
エレメントの値は、同じ色を持つペルの各ラン・レング
スを表す（図１０参照）。

【００３１】５．次に、これらのランを、処理中の特定
のバーコード規格に特有の規則に従って正規化する。９
者択３コードの場合、各バーコード文字ごとに９個のエ
レメントと、文字分離記号とがある。また、有効な各バ
ーコードを区切る１個の開始文字と、１個の終了文字も
ある。９者択３コードの正規化プロセスは、前のステッ
プで生成したラン・レングスを表すアレイからの最初の
黒のランで開始して、最初の１０個のエレメントの値を
合計する。もし、個々のエレメントの値が、呼び出し環
境で定義した値（２４）の範囲外にあれば、これらのラ
ンは有効なバーコードのイメージを表さない。一方、こ
れらの１０個のエレメントの値の和が、呼び出し環境で
定義したスレッショルド値（１＊１６，６＊１６）の範
囲内にない場合も、これらのランは有効なバーコードを
表さない。これらのテストに合格する和を、処理中のバ
ーコードのスペース・エレメント（実際のエレメントで
はない）の総数に関係する値、例えば１６によって除算
する。（９者択３コードの場合、１６個のスペース・エ
レメント、すなわち７個のシングル幅と３個のトリプル
幅がある。）この被除数は、このバーコード中に存在す
る各スペース・エレメントのペル幅を表す。この例で
は、この計算結果は（２．５を丸めた）３である。

【００３２】６．この被除数から、正規化プロセスに使
用する、狭幅／広幅を判定するための２つのスレッショ
ルド値を計算する。かかるスレッショルド値の計算は、
認識中のバーコードのタイプに依存する。この例では、
かかる２つのスレッショルド値が、３及び５として計算
される。

【００３３】７．正規化プロセスの最後の部分は、ラン
・レングスを表す前記アレイと同じ大きさを有する新し
いアレイを生成することである。このアレイ中の各エレ
メントは、狭幅か広幅かを表す０又は１として計算され
る。黒又は白のスレッショルド値を使用して、各ラン・
レングスが黒又は白のランのどちらを表すかを判定す
る。もし、一のラン・レングスが白のランに相当し且つ
その長さが３以上であれば、これを広幅の白とみなし、
３未満であれば、狭幅の白とみなす。一方、一のラン・
レングスが黒のランに相当し且つその長さが５以上であ
れば、これを広幅の黒とみなし、５未満であれば、狭幅
の黒とみなす。図１０は、図５のバーコード部分につい
ての結果を示している。これと同様に、図１１は、図６
の過度にスキューされたバーコード部分についての結果
を示している。黒と白のスレッショルド値の差は、スキ
ュー及び印刷の不鮮明に対する許容度を与える。

【００３４】８．最後のプロセスは、正規化済みの
“ｍ”エレメントの表示を構成する１６ビット・ワード
内に、一の索引値を生成することを含んでいる。ここ
で、“ｍ”は、各バーコード文字中の物理的なエレメン
トの数（１０）である。実際には、これは、９個のエレ
メントと狭幅の文字間ギャップとから成る。次に、この
索引値を、当該バーコードのタイプに関連する有効な値
の表と突き合わせる。この例では、９者択３バーコード
表中の文字“＊”に対応する、１６進値（０１２８）を
生成する。もし、有効な値が見つかれば、このプロセス
は、次のセットのエレメントについて反復する。一方、
有効な値が見つからなければ、この正規化プロセスを、
ラン・アレイにおける次の黒のラン・エレメントの箇所
で再開し、そして完全に有効なバーコードが見つかるか
又は当該イメージ・アレイが完全に処理されるまで、正
規化プロセスを反復する。

【００３５】もし、有効な開始文字が見つかっても、当
該コード中の以後の文字を見つける際に誤りが検出され
るならば、このルーチンは、追加セットの行を既に合計
されたものと合計する（この例では、１０個の行の値を
使用する）。こうすると、多くの場合、ノイズを除去す
ることができる。これを２ステップで実行することによ
り、高い品質のイメージを非常に速やかに認識すること
ができる。追加の処理を必要とするのは、低い品質のイ
メージだけである。

【００３６】プロセスＡの説明（図１２）ステップ２０は、圧縮済みのイメージから１ラスタ・ラ
インを獲得して、これを図７に示すようなラン・エンド
のアレイへ圧縮解除する。もし、当該イメージの終わり
が処理済みであれば、圧縮解除ルーチンは状況コードを
戻す。

【００３７】ステップ２２は、この標識を検査してイメ
ージの終わりを検出すると、このルーチンを“未発見”
標識で以て終了させる。

【００３８】ステップ２４は、圧縮解除したばかりの行
（ライン）の数を検査する。もし、これが“ｍ”番目の
ラインであれば、ステップ２６に進み、さもなければ、
このラインを無視して次のラインを圧縮解除する（ステ
ップ２０）。但し、ｍ＝（スキップすべきライン数）＊
（整数）である。

【００３９】ステップ２６は、このイメージ行で検出し
たラン・エンドの数に関係する値を保持する、ラン・エ
ンド・バッファの最初の記憶ワードを検査する。もし、
この値が、（最小の文字数）＊（文字当たりのエレメン
ト数）として計算された一のスレッショルド値よりも小
さければ、このラインを破棄して次のラインを圧縮解除
する（ステップ２０）。一方、この値が当該スレッショ
ルド値よりも大きければ、ステップ２８に進む。この例
では、行−１０は１０個のラン・エンドを有するに過ぎ
ないから、４個のコード化文字を表すべき４＊１０個の
ラン・エンドを有するという最小限の要件を満足してい
ない。

【００４０】次に、ステップ２８は、前記スレッショル
ド値に等しい数のラン・エンドにより分離され且つ白の
ラン・エンド（黒の開始）で開始する処の、２つのラン
・エンドの間の差を検査して、この差が、有効なバーコ
ードの最小のスレッショルド値と最大のスレッショルド
値との間にあるか否かを判定する。この例では、もしラ
ン・エンド１とラン・エンド４０との間の差が６４と３
８４の間にあれば、この差はテストに合格する。もし、
この差がテストに合格しなければ、ラン・エンドのアレ
イが使い尽くされるまで、ラン・エンド３とラン・エン
ド４２の間の差や、これと同様の差について、このテス
トを反復する。もし、その行全体がこのテストに合格し
なければ、次のラインを圧縮解除する（ステップ２
０）。一方、このラインがテストに合格すれば、このラ
インは、（図１３の）ステップ３０でプロセスＢに渡さ
れる。

【００４１】プロセスＢの説明（図１３）ステップ３０は、複数の作業アレイをゼロにクリアす
る。

【００４２】ステップ３２では、プロセスＡから渡され
た行を新しいアレイｄに合計する。アレイｄは、一のイ
メージ行におけるペルの数ｅに等しい大きさを有する。

【００４３】この合計プロセスは、当該イメージ行中の
黒のペルに対応するアレイｄの各エレメントに１を加え
ることを含んでいる。例えば、もし１０１番目のペルが
黒であれば、アレイｄの１０１番目のエレメントを１だ
け増加（インクレメント）する。この合計プロセスを次
のｃ−１行について実行し、これらの行をラン・エンド
へ部分的に圧縮解除して、ｃ行の合計操作を完了させ
る。この結果、アレイｄのｅ個のエレメントは、それぞ
れ０（純然たる白）とｃ（純然たる黒）との間の値を有
することになる。

【００４４】ステップ３４及び３６は、このアレイｄを
処理して、新しいアレイｆを生成する。新しいアレイｆ
の各エレメントは、アレイｄで見つけられた黒又は白の
ランのラン・レングスをそれぞれ表す。このラン・レン
グスは、ｃ／２よりも小さいか又はそれに等しい
（白）、或いはｃ／２よりも大きい（黒）、連続するエ
レメントの数を表す。アレイｆは、ノイズとドロップア
ウトを考慮した後の、正規化済みイメージの表示を保持
する。

【００４５】ステップ４２は、アレイｆの最初の１０個
（バーコード文字中のエレメントの数）のエレメントの
値を合計し、この和が２つのスレッショルド値の間にあ
るか否かを検査する。もし、この和がこれらのスレッシ
ョルド値の間にあれば、ステップ４６に進み、さもなけ
れば、ステップ４４に進む。

【００４６】ステップ４４は、アレイｆのポインタを増
加して、次の黒のラン・レングスをステップ４２の“最
初”として指定する。アレイｆの終わりでなければ、ス
テップ４２の操作を継続する。一方、アレイｆの終わり
であれば、プロセスＡに戻って終了する。

【００４７】ステップ４６は、アレイｆから新しいアレ
イｇを計算する。アレイｇのエレメントは、アレイｆの
エレメントと１対１で対応する。この関係を計算するた
め、ステップ４２からの和を取り、これをバーコード文
字中のスペース・エレメントの数で除算する。認識中の
バーコードのタイプに依存して、アレイｆ中のラン・レ
ングスに対応する白／黒及び広幅／狭幅のエレメントを
判定するための、スレッショルド値を計算する。かく
て、アレイｇ中のエレメントは、広幅／狭幅の標識を保
持する。

【００４８】ステップ４８は、（バーコードのタイプに
依存して）１０個の広幅／狭幅の標識を組み合わせるこ
とにより、バーコードのタイプに依存する表内の文字コ
ードを索引するのに使用する１０ビット値を生成する。
もし、有効なコードが見つからなければ、ステップ５０
を実行する。一方、有効なコードが見つかれば、ステッ
プ５４を実行する。

【００４９】ステップ５０は、既に有効なコードが見つ
かっているか否かを検査する。もし、見つかっていれ
ば、処理中のイメージは損傷している蓋然性が高いの
で、（追加の行を合計する）追加の処理を実行して、良
好なバーコードを識別できるようにする。もし、かかる
追加の合計がまだ行われていなければ、呼び出しオプシ
ョンとして供給される次の和の値に等しくなるようにｃ
をセットし、ステップ３２でそれ以上の行を処理すると
ともに、ステップ３２−４８を反復する。一方、かかる
追加の処理が既に行われていれば、ステップ４４を実行
して、当該イメージ行について同様の処理を試みる。

【００５０】ステップ５４は、有効なバーコード文字が
見つかった場合に開始する。もし、当該イメージが左端
の箇所で下方にスキューされていれば、開始文字を解読
する前に、有効な文字が見つかることもある。ステップ
５４は、開始コードが見つかったか否かを検査する。も
し、見つかっていなければ、当該文字は文脈上は有効で
はないので、ステップ４４を実行する。

【００５１】ステップ５６が開始するのは、現在の文字
が有効であり且つ開始文字が解読されている場合であ
る。もし、当該コードが終了文字でなければ、これは有
効コードとみなされ、ステップ５８に進む。一方、これ
が終了文字であれば、ステップ６０に進む。

【００５２】ステップ５８では、有効な文字が見つかっ
ているから、これを出力バッファにセットし、ステップ
４４を経由して解読プロセスに進む。

【００５３】ステップ６０が開始するのは、開始文字、
終了文字及び幾つかのデータ文字が解読されている場合
である。指定した最小数の文字が見つかったか否かを検
査する。もし、見つかっていれば、良好なバーコードが
見つかっているので、呼び出し元に対し、成功を表す状
況コードを戻すことができる。さもなければ、ステップ
６２に進む。

【００５４】ステップ６２は、バーコードが最小限の要
件を満足しなかったという理由で、出力バッファをクリ
アした後に、ステップ４４に進む。

【００５５】呼び出し環境認識プロセスのこの部分は、ディジタル・イメージ・フ
ァイルを見つけて、カーネル・ルーチンに渡すために圧
縮済みの２レベルのイメージ・データのバッファを用意
する。

【００５６】幾つかのアプリケーションは、イメージ・
ページ全体の中でバーコードが見つかりそうな場所を知
っているので、かかる矩形の座標に関する情報をカーネ
ルに渡すことができる。こうすると、潜在的なバーコー
ドについてのカーネルの探索を、圧縮解除済みの行の或
る範囲に限定することができる（開始行に達するまで探
索を始めなくてもよく、しかも最大の垂直エクステント
に達すると、直ちに終了することができる）。他のアプ
リケーションは、バーコードがイメージ内のどこかに現
われることだけを知っているに過ぎない。この呼び出し
環境は、バーコード探索用の戦略を制御するものであ
る。この戦略は、特に以下の事項に依存する。

【００５７】＊バーコードの高さ＊バーコードのスキューの予想最大レベル＊黒と白を識別するための走査機構のコントラストの
セッティング−これはカーネルに渡すべきスレッショル
ド値のセッティングを決定する＊バーコードが存在する確度が高い位置（探索を行う
順序に配列）＊バーコードが（例えば、走査対象の文書ページ上に
ある手書き注釈によって）汚れている確率。

【００５８】カーネルに渡される重要なパラメータは、
次の通りである。＊処理すべき圧縮済みのイメージ・データを指定する
ポインタ＊スレッショルド値。

【００５９】バーコードの明瞭なイメージを処理すると
いう第１の前提事項と、失敗の表示が得られる場合に
は、（実際のイメージ処理で生ずる）ノイズ、スキュー
及びその他の無関係の情報を識別するために、同じイメ
ージ矩形を一層綿密に処理するという第２の前提事項を
基礎として、これらの２つの機能を分離すると、各ルー
チンの処理速度を最適化することが可能である。

【００６０】

【発明の効果】本発明の方法によれば、良好なラスタ・
イメージを高速で解読することができるだけでなく、低
い品質の不明瞭なイメージであっても、これを若干長い
処理時間を要するだけで処理することができる。更に、
アプリケーションや、認識すべきバーコードのタイプ
や、処理対象とする文書イメージに従って、識別パラメ
ータをセットすることができる。本発明は、イメージの
走査分解能とは無関係であるばかりでなく、バーコード
の幾何的形状（例えば、バーの絶対幅）とも無関係であ
る。

【図面の簡単な説明】

【図１】文書ラインに垂直なバーコード・エレメントを
持つ完全なバーコードを示す図である。

【図２】図１のバーコードをディジタル・イメージの形
式で表す図である。

【図３】バーコードのディジタル・イメージ・データが
損傷している実際の例を示す図である。

【図４】本発明を説明するために使用する解読制約表の
内容を示す図である。

【図５】不明瞭なバーコードにおけるペルの拡大図であ
る。

【図６】スキューの存在によって図５のバーコードがど
のように見えるかを示す図である。

【図７】走査済みの行をラン・エンドへ部分的に圧縮解
除することから得られる表の内容を示す図である。

【図８】行１−６をペル列１４０まで部分的に圧縮解除
することから得られる表の内容を示す図である。

【図９】行１−６の和アレイが図８の表からどのように
生成されるかを示す図である。

【図１０】新しいアレイがどのように生成されるを示す
図である。

【図１１】図６のスキューされたイメージから得られる
和アレイを示す図である。

【図１２】ラスタ・ラインを最初に評価するための、バ
ーコード認識方法の第１の段階を示す流れ図である。

【図１３】図１２の流れ図から続く、バーコード認識方
法の第２の段階を示す流れ図である。

フロントページの続き (56)参考文献特開平１−156885（ＪＰ，Ａ) 特開平２−76087（ＪＰ，Ａ) 特開昭58−189773（ＪＰ，Ａ)

Claims

【特許請求の範囲】

【請求項１】次の各ステップからなる、ディジタル・
イメージを表すデータに含まれるバーコードを認識する
方法。（ａ）長さｘのＮラスタ・ラインのディジタル・イメー
ジを表すデータをバッファするステップ。但し、ｘとＮ
はいずれも２より大きい正の整数である。（ｂ）前記Ｎラスタ・ラインのバッファ・データから、
長さがｘで高さがＮラインに相当する当該ディジタル・
イメージの矩形２値イメージ入力アレイにおける１ビッ
トを各ペル列ごとに合計することにより、ｘ個の和を有
する第１のアレイを生成するステップ。（ｃ）前記和の各々を、第１のスレッショルド値と比較
し、当該和が第１のスレッショルド値よりも大きけれ
ば、当該和に関連するペル列が黒の領域を表すものと判
定し、当該和が第１のスレッショルド値よりも小さけれ
ば、当該和に関連するペル列が白の領域を表すものと判
定するステップ。（ｄ）前記黒の領域と前記白の領域のラン・レングスを
それぞれ表す一連のレングス・データ・エレメントを有
する第２のアレイを生成するステップ。（ｅ）前記黒の領域と前記白の領域を正規化するため、
前記第２のアレイのレングス・データ・エレメントのう
ち処理中のバーコードのタイプに従って定められた個数
のレングス・データ・エレメントを合計するステップ。（ｆ）前記ステップ（ｅ）から得られた一の和を、処理
中のバーコードのタイプに従って定められたスペース・
エレメントの総数に関係する一の値によって除算するス
テップ。（ｇ）前記除算結果に応じて計算された第２のスレッシ
ョルド値と、前記定められた個数のレングス・データ・
エレメントを比較することにより、前記黒の領域と前記
白の領域のラン・レングスを広幅又は狭幅としてそれぞ
れ特徴づけるための標識データ・エレメントを生成する
ステップ。（ｈ）前記標識データ・エレメントに応答して、一のバ
ーコード文字を解読し且つ前記バーコードによって表さ
れる一の文字ストリングを生成するステップ。
【請求項２】次の各ステップからなる、ディジタル・
イメージを表すデータに含まれるバーコードを認識する
方法。（ａ）ディジタル・イメージのＭラスタ・ラインを表す
データを入力するステップ。但し、Ｍは、２より大きい
正の整数である。（ｂ）前記Ｍラスタ・ラインのうち一のラスタ・ライン
が有効なバーコードを含むか否かを判定するステップ。（ｃ）前記一のラスタ・ラインを、前記ディジタル・イ
メージの複数のペル列の２値状態を表すための複数のエ
レメントを有する、一のラン・エンド・アレイに変換す
るステップ。（ｄ）前記一のラスタ・ラインに関連する前記ラン・エ
ンド・アレイ内に、少なくともＮエレメントがあるか否
かを判定するステップ。但し、Ｎは、処理中のバーコー
ドのタイプによって定まる、２より大きい正の整数であ
る。（ｅ）前記Ｍラスタ・ラインのうち前記一のラスタ・ラ
インを除く残りのラスタ・ラインについて、前記ステッ
プ（ｂ）ないし（ｄ）を反復するステップ。（ｆ）前記Ｍラスタ・ラインに関連するＭ個の前記ラン
・エンド・アレイ内の前記複数のペル列の２値状態を、
各ペル列ごとに合計するステップ。（ｇ）前記ステップ（ｆ）から得られた和の各々を、Ｍ
の一の算術関数値である第１のスレッショルド値と比較
し、当該和が第１のスレッショルド値よりも大きけれ
ば、当該和に関連するペル列を黒と判定するステップ。（ｈ）前記複数のペル列のうち黒と判定されたペル列の
ラン・レングスをそれぞれ表すレングス・データ・エレ
メントを計算するステップ。（ｉ）前記計算されたレングス・データ・エレメントの
うち、処理中のバーコードのタイプに従って定められた
個数のレングス・データ・エレメントを合計するステッ
プ。（ｊ）前記ステップ（ｉ）から得られた一の和を、処理
中のバーコードのタイプに従って定められたスペース・
エレメントの総数に関係する一の値によって除算するス
テップ。（ｋ）前記除算結果に応じて計算された第２のスレッシ
ョルド値と、前記定められた個数のレングス・データ・
エレメントを比較することにより、黒と判定されたペル
列のラン・レングスを広幅又は狭幅としてそれぞれ特徴
づけるための標識データ・エレメントを生成するステッ
プ。（ｌ）前記標識データ・エレメントに応答して、一のバ
ーコード文字を解読し且つ前記バーコードによって表さ
れる一の文字ストリングを生成するステップ。
【請求項３】前記ステップ（ｂ）が、前記一のラスタ
・ラインに少なくとも処理中のバーコードのタイプに従
って定められた所定数のラン・エンドが生ずるか否かを
判定することを含む、請求項２記載のバーコードを認識
する方法。
【請求項４】前記ステップ（ａ）が、処理中のバーコ
ードの予想された高さに基づいて、Ｍの値を選択するこ
とを含む、請求項２記載のバーコードを認識する方法。
【請求項５】前記ステップ（ａ）が、処理中のバーコ
ードの予想された最大レベルのスキューに基づいて、Ｍ
の値を選択することを含む、請求項２記載のバーコード
を認識する方法。