JP2000507727A

JP2000507727A - 高速画像捕捉システムおよび方法

Info

Publication number: JP2000507727A
Application number: JP10500750A
Authority: JP
Inventors: ヘクト、カート; ネスコビック、ミロラッド; シリーシャ、バサンス; コーヘン、エドワード
Original assignee: アキュー―ソート・システムズ・インコーポレーテッド
Priority date: 1996-06-03
Filing date: 1997-06-03
Publication date: 2000-06-20
Anticipated expiration: 2017-06-03
Also published as: AU3152897A; US20010006191A1; WO1997046965A3; EP1278151A2; US6015089A; CA2255576A1; EP0917685B1; EP1278151A3; WO1997046965A2; US6386454B2; JP3115610B2; CA2255576C; EP0917685A2; US6193158B1; DE69716087D1; ATE225539T1; US5969325A; DE69716087T2

Abstract

(57)【要約】バーコード記号を高速で捕捉してデコードするために、走査された画像中に可能性のあるバーコード候補の位置を決定し、無効なデータを取除くために候補をフィルタ処理するシステムが提供されている。このシステムによって、計算リソースは実際のバーコード記号になる可能性が最も高い情報のデコードに集中できる。一度、可能性のあるバーコード候補の位置が決定されると、バーコード記号はバーコードの方向および記号方式を決定するように処理される。次に、バーコード記号の各素子は、全ての素子が本来の画像において可視でなくとも位置が定められ、バーコード記号は特定の記号方式に従ってデコードされる。

Description

【発明の詳細な説明】高速画像捕捉システムおよび方法発明の背景発明の分野本発明は、一般的にコード化された情報記号の形態の画像を捕捉するためのシステムおよび方法に関する。特に、本発明は、特に不明瞭で不良に印刷されたあるいは汚れたバーコード記号の位置を決定し、デコードするシステムおよび方法に関する。従来技術の説明バーコード記号は、様々な幅を有する典型的に長方形のバーあるいは素子から形成されている。素子の特定の配置は、使用されたコードあるいは“記号方式” によって特定された１組の規則に従って文字を定める。所望の一連の文字をコード化するために、一群の素子配置がつなぎ合わされて完全なバーコード記号が形成され、メッセージの各文字は特有の素子のグループによって表される。幾つかの記号方式において、どこでバーコード記号が始まり、どこで終わるのかをそれぞれ示すために特有の“スタート”および“ストップ”文字が使用されることある。ＵＰＣ／ＥＡＮ、コード３９、コード１２８、コータバー、ＰＤＦ４１７および５のインターリーブされた２（５のＩ２）を含む多数の異なるバーコード記号方式がある。印刷物の表面上に表されたバーコード記号等の画像を捕捉し、捕捉されたバーコード記号を読み取ってデコードするために種々の光学式文字読取り装置および光走査システムが開発されてきた。走査システムは、典型的にバーコード記号を照射するためのレーザ光源と、その記号から反射された光を検出するための光検出器とを含んでいる。別の一般的なタイプの光走査装置は、非レーザ光源と、荷電結合素子（ＣＣＤ）検出器とを備えている。記号から反射された光の一部はＣＣＤ検出器によって検出され、走査されたバーコード信号のデジタル画像を与える電気信号に変換される。次に、デジタル画像は処理され、使用された特定のバーコード記号に従ってデコードされる。バーコード記号が静止しており、明瞭に見え、傷がない場合等の理想的な状態においては大抵のバーコード記号は容易に読取ることができる。しかしながら、バーコード記号が高速で動く物体上に位置されているとき、幅の狭いバーおよびスペースは容易に位置が決められない。バーが汚れて読めなくなるのは、低解像度の画像生成あるいはスキャナに関するバーコード記号の高速移動のために生じる。外部からのマーキングあるいは別の汚れによっても、バーコード記号が部分的に不明瞭になることがある。多数の現在のスキャナを持つ付加的な問題は、シーケンス中の１以上の文字（スタートおよびストップ文字を含む）が正規の文字として認識されない場合に走査をデコードする試みが失敗することである。典型的に、部分的なデコーディングの結果は保存されない。結果的に、高さが短い長いバーコード記号、不鮮明に印刷されたバーコード記号、あるいは外部からのマーキングによって損なわれたバーコード記号等を含む様々なバーコード記号は、記号上の走査線を新しい方向に向けるようにオペレータが繰り返し試みない限りデコードすることは不可能である。バーコード記号は印刷上の欠陥を有していることもあり、それによって１つの歪みもない走査を達成することは不可能となる。従来のデコーディング方法を使用すると、そのようなバーコード記号は読取り不可能となり、それは記号を通って任意の単一の走査線に沿って読取っても結果的に一連の有効な文字とはならないからである。従って、走査された画像が有効なバーコードの候補であるかどうかを迅速に決定し、有効なバーコードの候補を正確にデコードするスキャナが必要とされる。発明の概要本発明は、バーコード記号を高速で捕捉し、位置を決め、デコードするための装置および方法である。本発明によるシステムは、走査された画像内の可能性のある一連のバーコードの候補の位置を定め、無効のデータを取除くためにその候補をフィルタ処理する。この方法によって、実際のバーコード記号になる可能性が最も高い情報のデコーディングに計算に関するリソースを集中させることができる。一度、可能性のあるバーコードの候補の位置が定められると、バーコード記号はバーコード記号の方向および記号方式を決定するように処理される。次に、バーコード記号内の素子が検出され、バーコード記号は特定の記号方式に従ってデコードされる。本発明の目的は、バーコード記号の位置を正確に決定してデコードし、一方で計算に関するリソースを保全する記号の位置決定およびデコーディングシステムならびに方法を提供することである。本発明の別の目的および利点は、本明細書の好ましい実施形態の詳細な説明によって当業者に明らかとなるであろう。図面の簡単な説明図１は、本発明に従って製造されたバーコードスキャナの概略図である。図２Ａおよび図２Ｂは、本発明によるバーコード記号位置決定方法のフロー図である。図２Ｃ乃至図２Ｆは、本発明による追跡方法を示している。図２Ｇは、スピーカ反射を防ぐためにバーコードの端部にスキップする方法を示している。図２Ｈは、２倍幅と多数倍幅のバーコード記号の間の違いを決定する方法のフロー図である。図３は、水平および垂直グリッド線によって生成された等倍寸法の画像ブロックを示している。図４は、トリガ線の拡大図である。図５は、トリガ線からのデータを表した図である。図６は、近隣の走査線の選択およびトリガ線との比較を示している。図７Ａおよび図７Ｂは、本発明に従ってバーコード記号をデコードする好ましい方法のフロー図である。図８は、走査線データのピークおよび谷部を探す方法のフロー図である。図９は、ピークおよび谷部を示す概略図である。図１０は、トリガ線におけるデータのダイナミック・レンジの図である。図１１Ａ乃至図１１Ｃは、バーコード記号のスタートの例を示している。図１２は、幅の広いバーおよび幅の広い間隔の数の決定のフロー図である。図１３Ａおよび図１３Ｂは、バーコード記号の方向の決定方法のフロー図である。図１４は、本発明に従って幅の広いバーおよび幅の広い間隔の数を決定する方法のフロー図である。図１５Ａおよび図１５Ｂは、本発明によるバーコード記号情報の処理方法のフロー図である。図１６Ａは、複数の読取り不可能な領域を有するバーコード記号のグレースケール画像である。図１６Ｂは、選別前の選択された走査線からのグレースケール振幅のグラフ図である。図１６Ｃは、選別後の図１６Ａのグレースケール画像である。図１６Ｄは、選別後の図１６Ｂの走査線からのグレースケール振幅のグラフ図である。図１６Ｅは、画素の不整列のために生じたエイリアシングを示している。図１６Ｆは、画像に関連した選別されなかったグレースケール値の表である。図１６Ｇは、画像に関連した選別されたグレースケール値の表である。図１７Ａおよび図１７Ｂは、本発明によるバーコード記号の位置を決定するための別の方法のフロー図である。図１８Ａは、カラーブロブ解析後の偽のものである。図１８Ｂは、カラー解析後の有効なバーコード記号である。図１９は、Ｃｏｄｅ１２８バーコード記号のデコード方法である。図２０は、多数倍幅バーコード記号からのグレースケール振幅のグラフ図である。図２１は、本発明によるグレースケール組成を示している。実施例以下、本発明は図面を参照して説明され、そこにおいて同一の参照番号は全体を通して同じ素子を表している。図１を参照すると、本発明に従って製造されたバーコードスキャナ10が示されている。走査システム10は、主バーコード記号18 を照射する光源12を具備している。バーコード記号18から反射された光は、感光性検出器20によって検出される。検出器20は、バーコード記号18から反射された光を表す電気信号を生成し、それはプロセッサ22に出力される。プロセッサ22は信号を解読し、バーコード記号18にコード化された情報に対応する結果的に生じた情報を出力手段24に転送する。出力手段24は、当業者によく知られているようなプリンタ、ＣＲＴあるいは情報システムである。図１に示された走査システム10は、可搬式小型ユニットにおいて実施されるか、あるいは静止ユニットであってもよく、そこにおいてバーコード記号18を有する物体は手動あるいはコンベアのいずれかによって光源12の下を通される。好ましい実施形態において、検出器20は、荷電結合デバイス（ＣＣＤ）の一次元アレイ（ライン）検出器であり、それはバーコード記号18の電子画像を検出および記憶する。走査システム10に関する付加的な詳細は、本発明の出願人に譲渡された 1996年２月２３日に出願された現在出願継続中の米国特許出願（番号はまだ知られていない）明細書“HIGH SPEED IMAGING APPARATUS FOR CCDBASEDSCANNERS” を参照して得られる。走査システム10は、バーコード記号をデコードするために２つのステップによる方法を使用している。すなわち、１）物体上の有効なバーコードの候補の位置を決定し、２）検出されたバーコードの記号方式のタイプを決定し、その方式に従ってバーコード記号をデコードする。図２Ａおよび図２Ｂによれば、システム10は、図示されているようにバーコード記号位置決定手順40を実行する。バーコード記号18から反射された光は、ＣＣＤ検出器20内の光感知画素のアレイによって検出され、それによってバーコード記号18の電子画像を生成する。各画索は、画索によって検出された光の量を表す特定のグレースケール（中間調）値を有している。画像は、等しい寸法の画像ブロック74を有するグリッドに分割される（ステップ42）。ブロック74の寸法は、バーコード記号18の高さならびに画像の解像度に依存する。図３に示されているように、等しい寸法の画像ブロック74は水平グリッド線70および垂直グリッド線 72によって生成される。好ましい実施形態において、画素アレイは４０９６×１０２４個の画素であり、水平および垂直グリッド線70,72は垂直および水平方向それぞれにおいて３２画素だけ離れている。グリッド寸法が小さいと一層小さいバーコード記号の位置決定が容易になるが、それは計算コストが大きくなる。システム10は、一連のグリッド線解析を実行することによってバーコード記号のサーチを開始する。水平グリッド線（“ピケットフェンス”の方向）および垂直グリッド線（“ラダー”の方向）は、可能なバーコードの候補が存在するかどうかを決定するために解析される（ステップ43）。“トリガ線”と呼ばれ、例えば図３および図４においては線78で示されている第１のグリッド線が選択される（ステップ44）。典型的に、トリガ線78はグリッドの中央にある。トリガ線78は、トリガ線78に沿った転移パターンを捜す（速度を増すように１画素おきにスキップする）ことによって可能性のあるバーコードの候補に対して解析される。転移パターンは、（２５５のグレースケールレベルから）グレースケールの大きさの差が少なくとも２０ある２つの連続的に選択された画素として定義される。最初のバーコードの候補として採用するために、転移パターンは、バーコード記号の始まり等のような画素の数が最小であるクワイエット領域を有し、それに続いて選択された長さの画素内でしきい数の転移がある、あるいは、選択された長さの画素内でしきい数の転移があり、それに続いてバーコード記号の終わり等のようなクワイエット領域を有していなければならない。選択された画素の長さは、垂直方向に１４０、水平方向に９０、転移のしきい数が１６、しきいクワイエット領域は最小で２０画素であることが好ましい。グリッド線および画素の座標を構成する連続的なバーコードの候補の位置は、バーコード候補リストに配列される。候補の位置（水平方向のサーチの場合にはｘであり、垂直方向のサーチの場合にはｙ）の符号（正および負）は、転移の前に現れた候補のクワイエット領域がバーコード記号の始まりを示しているかどうか、あるいは転移後に現れた候補のクワイエット領域がバーコード記号の終わりを示しているかどうかを示す。１以上の可能性のあるバーコードの候補が検出された（ステップ46）後、許容されない候補を取除くために候補はフィルタ処理される（ステップ48）。候補をフィルタ処理する際（ステップ48）、システム10は、図５に示されているようにトリガ線78に沿った予め定められた数の画素を解析し、しきい数のバーおよびスペースがその領域内に存在しているかどうかを決定する。あるアプリケーションにおいて、しきい値は、６５画素長の領域で２本のバーと２つのスペースである。しかしながら、しきい値は特定のアプリケーションに依存する。システム10は、領域を解析し、以下の式を使用して黒および白のしきい値を決定することによってバーおよびスペースの数を決定する。中間点＝（（最大−最小）＊０．７５）＋最小（１）ドロップレベル＝（最大−最小）＊０．１８（２）黒レベルのしきい＝中間点−ドロップレベル（３）白レベルのしきい＝中間点＋ドロップレベル（４）バーは、連続した画素が黒レベルのしきいよりも小さいグレースケール値を有し、画素の数が予め定められた最小幅よりも大きい場合に決定される。スペースは、連続した画素が白レベルのしきいよりも大きいグレースケール値を有し、幅が予め定められた最小幅よりも大きい場合に決定される。次に、その領域中のバーおよびスペースの数が決定される。任意のバーが最大幅よりも幅が広い場合、その領域は誤である。その理由はバーコード記号中の幅の広いバーが最大幅よりも大きいことは不可能だからである。類似した理由がスペースに関しても当てはまるが、反射光の反射によって所定の領域中でＣＣＤ検出器20が“ウォッシュアウト”され、それによって検出器20がこれらのウォッシュアウトされた領域を幅の広すぎるスペースとして解釈してしまうことになる。従って、好ましい実施形態において、スペースの幅は可能性のある候補のフィルタ処理には使用されない。一度バーおよびスペースの数が決定されると、しきい値数と比較される。しきい値数のバーおよびスペースよりも少ない数のバーおよびスペースを有するバーコードの候補はいずれも廃棄される。バーコードの候補がフィルタ処理手順（ステップ48）を通過した後、隣接した走査線中の画素をトリガ線78中の画素に整合することによって照合が行われる（ステップ50）。システム10は、例えば図６における線98等の隣接した走査線、すなわち、トリガ線78から予め定められた数の走査線だけ離れた走査線を選択し、トリガ線78から８画素離れていることが好ましい。システム10は、点Ｘ₁の左に約１２画素オフセットされた点Ｚ₁において始まる画素を集収することによって整合プロセスを開始する。グレースケール値の差が２０である第１の転移は、Ｙ₁ において識別される。次に、Ｙ₁の右に４０画素（Ｙ₁…Ｙ₄₀）のグレースケール値が集収され、Ｘ₁の右に４０画素（Ｘ₁…Ｘ₄₀）のグレースケール値と比較される。差の絶対値の平均は次の式を使用して計算される。（Ｎ＝比較された画素数であり、好ましくはＮ＝４０である）この値がエラー定数である２５以下である場合、この候補は整合試験を合格したということである。隣接した走査線98がトリガ線78との整合に不合格であった場合、トリガ線78の反対側の第２の走査線100が選択される。この第２の走査線100 が整合試験に不合格であった場合（ステップ50）、候補は拒絶される。この時点において、バーコードの候補は選択され、検出されたバーコード記号18の始まりとして確認されている。次に、システム10は、第１の幅の広いバーを解析し、そのバーが高すぎず、短すぎないこと、またそのバーが湾曲していないことを保証しなければならない（ステップ52）。バーの前縁はバーの最上部まで、およびバーの底部まで追跡され、バーコード記号の第１の２つの角部を定める。追跡手順は、図２Ｃ乃至図２Ｆを参照して説明される。高さは予め定められたしきい値と比較され、バーが長すぎるか短すぎるかを決定する。図２Ｃを参照すると、システム10は点１において検出されたバーの追跡を開始する。移動の最初の方向は、バーコードの候補か水平方向のサーチと垂直方向のサーチのどちらから位置付けされたか、ならびにバーコードの候補の符号に依存する。例えば、負の符号を有する水平方向の候補について考えてみる。システム 10はクワイエット領域中にある点１において開始し、図２Ｄのマッピング表に示されているように、クワイエット領域から検出されたバーまでＤＲ０の方向に横断する。バー素子の２つの端部の点を追跡および決定するために、システム10は右回り（時計方向）（ＤＲ０、ＤＲ７、…ＤＲ１）および左回り（反時計方向）（ＤＲ０、ＤＲ１、…ＤＲ７）方向に移動しなければならない。図２Ｃを参照すると、システム10は最初にＤＲ０の方向に移動し、点２において黒画素を検出し、その画素は式３の黒レベルしきい値よりも低いグレースケール値を有している。最初に、システム10は左回りの方向に移動する。現在の画素が黒画素である場合、システム10はＤＲ１に向かって方向の番号を増分することによって白画素のサーチを続行する。従って、システム10は点３にあり、それは白画素である。グレースケール値および各画素の座標は、バッファ中に記憶される。次に、方向の番号は図２Ｅに示された表に基づいて再度マッピングされる。新しい方向の番号はＤＲ６であり、それは最後の方向がＤＲ１であったからである。次に、システム10は点３から点４へ横断する。５つの点がバッファ中に記憶されると直ちに、基準ベクトルの方向が計算される。追跡された全ての別の点に対して、システム10はベクトルの方向を計算する。ベクトルの方向がエラーしきい値によって基準ベクトルから逸脱する場合、バッファ中に記憶された第３の点乃至最後の点が選択され、角部の１つとしてマークされる。バーコード素子の反対の端部は、上述のものと同じ方法を使用して素子を追跡することによって見つけられるが、システム10は図２Ｆに示されたマッピング表を使用して右回りに動く。端部が追跡された後、システム10は、後の使用のためにバーコード記号の第１の２つの角部の座標を記憶する。システム10は、バーコード記号の反対側の端部のサーチを開始する（ステップ 54）。第１のエッジに垂直な線の座標が計算され、システム10はその垂直線に沿って移動しながら別のクワイエット領域をサーチする。クワイエット領域が合理的な距離内で見つからなかった場合、そのバーコードの候補は消去される。その距離は予め定められるか、あるいは第１のバーの高さに基づいていてもよく、それによって予め設定された高さ対幅の縦横比を維持する。クワイエット領域が検出されたとき、第２のエッジは高さおよび湾曲を検出するために追跡される（ステップ52）。次に、バーコード記号の長さが検査され（ステップ56）、それによってそれが予想された値以内にあり、第２の２つの角部の座標が記憶されることが確実にされる。図２Ｇを簡単に参照すると、鏡面反射のためにラベルがウォッシュアウトされ、点“１”は誤ってクワイエット領域として現れる可能性がある。固定長のバーコードの場合、バーコード記号の中央部内での鏡面反射を防ぐために予め定められた数の画素をスキップすることが好ましい。図２Ｇに示されているように、システム10は走査線に沿って点“２”にスキップし、それによって最後のバー（ｃ’ｄ’）をサーチする。この例において、最後のバー（ｃ’ｄ’）は検出されず、ステップ52および54は脱落する。しかしながら、コードのおおよその長さが知られている場合、バーコード記号領域（ａ’ｂ’ｃ’ｄ’）は人工的に境界を定められることができる。ステップ50は最後のバー上で実行され、それによってそれが有効なバーコードであるかどうかを確認する。バーコードの候補がステップ56の長さ検査手順に合格した場合、“境界のボックス”が定められ、それによってバーコード記号の４つの角部の座標が後の使用のために記憶される。この時点において、システム10は、２倍幅あるいは多数倍幅のバーコードのどちらが位置されているのかを決定しなければならず、それは、次のデコードステップが検出されたバーコードのタイプ（２倍幅あるいは多数倍幅）に依存しているからである。多数倍幅バーコード記号方式は、２つの異なる幅の素子よりも大きい幅の任意の記号方式として定められる。図２Ｈを参照すると、コードが２倍幅あるいは多数倍幅コードのどちらであるかを決定する手順が示されている。バーコードが位置決定された後（ステップ60 ）、システム10はバーコード記号のスタート／ストップ文字に対応するデータを抽出する（ステップ61）。これは、バーコード記号の始まりにおいて約４０画素、終わりにおいて４０画素を含む。各バーおよびスペースの幅が計算され（ステップ62）、システム10は記号方式がコード128であるかどうか（ステップ63）、ＰＤＦ417であるかどうか（ステップ65）、あるいは別のタイプの多数倍幅記号方式であるかどうか（ステップ67）を決定する。バーコードの候補が多数倍幅記号方式であることが決定された場合、それはそのそれぞれの記号方式に従って処理される（ステップ64,66,68）。候補が全ての多数倍幅記号方式の検査に不合格であった場合、検出されたバーコード記号方式は２倍幅コードであると仮定される。再び図２Ｂを参照すると、候補のタイプが決定された（ステップ57）後、各候補は詳細に後述されるようにデコードされる。当業者によって理解されるように、しばしば幾つかのバーコードラベルが単一の物体上に位置される。ラダー方向に垂直バーコードを位置させるために、システム10は、水平グリッド線解析が実行された（ステップ43）のと同じ方法で垂直グリッド線解析（ステップ59）を行うように進む。本発明は、１つの物体上に複数のバーコードラベルの座標を同時に位置させることができる。本発明による２倍幅バーコード記号をデコードする好ましい方法は、最初に図７Ａおよび図７Ｂを参照して手短に説明され、その後、詳細に説明される。図７Ａを参照すると、システム10はバーコード記号の座標および関連するデータを画像バッファから抽出する（ステップ200）。画像バッファは、画素形式のバーコード記号の電子画像を近似する問題となっている問題となっている領域に対する位置座標およびグレースケールデータを含んでいる。システム10は、必要に応じて処理するために各走査線の画素に対するグレースケール値をメモリの別々の部分にコピーする（ステッブ202）。ラインデータのピークおよび谷部が見つけられ（ステップ204）、バーコード記号の正確なスタートおよびストップ位置が決定される（ステップ206）。検出されたバーコード記号において使用されるバーコード記号方式のタイプを特定するために、幅の広いバーおよび幅の広いスペースの数が検出される（ステップ208）。次に、バーコード記号情報がステップ208 において決定された記号方式のタイプに従って処理される（ステップ10）。バーコード記号の処理が確認された後（ステップ212）、システム10は、バーコード記号が首尾よく読取られた（ステップ214）ことを示す信号を出力し、システム1 0はバーコード記号位置決定手順に戻る。ステップ212でバーコード記号の処理が確認されなかった場合、走査線の解析（ステップ216）が１０回まで反復される。１０回の反復の後にもバーコード記号の確認が行われなかった場合（ステップ216）、データは再構成され（ステップ220）、バーコード記号をデコードする試みがさらに５回行われる（ステップ2 22）。一度、バーコード記号をデコードおよび確認するための試みが成功せずに合計１５回行われると（ステップ222）、“読取りなし”信号がオペレータに戻され（ステップ224）、そのバーコード候補は廃棄される。試みの回数がアプリケーションに依存してオペレータによって設定されたパラメータであってもよいことは当業者によって認識されるべきである。以下、図７Ａおよび図７Ｂに示された２倍幅バーコード記号のデコード方法が詳細に説明される。図８を参照すると、走査線データのピークおよび谷部を捜す手順が示されている（ステップ204）。ピークおよび谷部は、ゼロの第１の導関数を有しているバーコード記号データの部分として定められているため、傾斜を有していない。図９に示されているように、ピークであると定められたバーコード記号の部分は正（＋）の識別子を与えられ、谷部であると定められた値は負（ −）の識別子を与えられる。システム10は、第１および第２の導関数を計算することによって点がピークと谷部のどちらであるかを決定する。点がゼロと等しい第１の導関数と、ゼロよりも小さい第２の導関数とを有している場合、点はピークとして分類される。点がゼロと等しい第１の導関数と、ゼロよりも大きい第２の導関数とを有している場合、点は谷部として分類される。本質的に、画素ｘの隣接した画素が画素ｘよりも小さい値を有している場合、画素ｘはピークである。画素ｘの隣接した画素が画素ｘよりも大きい値を有している場合、画素ｘは谷部である。次に、システム10は、１つのピーク／谷部から次のピーク／谷部への転移と比較するためにしきい値レベルを計算する（ステップ204B）。しきい値は、バーコード記号データのダイナミックレンジ内での転移の位置に依存している。説明のためのバーコード記号のダイナミックレンジは図１０に示されている。ダイナミックレンジは、各走査線の始まりにおいて計算され、次に、５つの別個の領域に分割される。ダイナミックレンジ300の中央近くにおいて、しきい値は“低い” 値に固定される。ダイナミックレンジの中央の上方および下方に位置されている２つのダイナミックレンジの領域であり、そこにおいて、可変のしきい値320,30 4が計算される。ダイナミックレンジの上限306および下限308において、しきい値は“高い”値に固定される。好ましい実施形態において、システム10は８ビットのグレースケール解像度を有しており、その結果、２５６のグレースケールレベル（０乃至２５５）が得られる。８ビットの解像度を使用して、ダイナミックレンジ300の中央においてしきい値が固定される。ダイナミックレンジの部分に対して可変のしきい値302.30 4が計算されたとき、線形近似が行われる。ピークに対する最も高いグレースケール値が２５０であり、谷部に対する最も低いグレースケール値が１００であり、平均的な画素値が１８０である例について考えてみる。ダイナミックレンジは２５０−１００＝１５０として計算され、１５０の１５％は２２である。従って、（１８０−２２）と（１８０＋２２）の間の全てのピークと谷部の差に対して、しきい値は最小のしきい値である５に固定される。ダイナミックレンジの上限 306および下限308におけるしきい値は、２０のグレースケールレベルに固定される。雑音は、印刷における変動およびラベルの反射特性によって高いグレースケールレベルおよび低いグレースケールレベルで大きくなる。典型的に熱によって生じたグレースケールの中央における雑音（ＣＣＤ雑音）は著しく低い。鏡面反射および別の変化は、ダイナミックレンジの上限および下限においてバーコード記号データに多大に作用する。これらの可変のしきい値は、有効なバーコード記号の転移を雑音および鏡面反射と区別する際に有効である。再び図８を参照すると、転移値が計算されたしきい値よりも大きい場合（ステップ204C）、データは記憶され（ステップ204D）、次の画素が解析される（ステップ204E）。転移値が計算されたしきい値よりも小さい場合（ステップ204C）、システム10は次の画素に直接進む（ステップ204E）。一度、走査線データの端部に到達すると（ステップ204F）、ルーチンから退出する（ステップ204G）。バーコード記号の始まりおよび終わりの位置は、しばしば確認することが困難であり、それは、幅の狭いバーおよびスペースは汚されることがあるからである。２倍幅バーコード記号を正確にデコードするために、バーコード記号の始まりおよび終わりのエッジ部の位置は正確に決定されなければならない。バーコード記号のエッジ部の位置決定方法（図７Ａに示されたステップ206）が以下、図１１Ａ乃至Ｃを参照して詳細に説明される。計算リソースを最小にし、バーコード記号の開始の位置決定の速度を増すようにするために、システム10は第１の幅の広いバーおよびクワイエット領域をサーチする。これによって、計算リソースが詳細な解析に集中される領域が設けられる。典型的に、幅の狭いバーおよびスペースは、クワイエット領域と第１の幅の広いバーとの間に存在している。システム10は、クワイエット領域と第１の幅の広いバーとの間で２画素おきに傾斜、すなわち第１の導関数を計算する。第１の導関数がゼロに近付いたとき、あるいは台地状の平らな頂部が存在しているとき、幅の狭いバーが検出されている。これは図１１Ａ乃至Ｃに示されている。図１１Ａを参照すると、幅の狭いバー153は明らかにクワイエット領域と第１の幅の広いバー152との間に存在している。図１１Ｂおよび図１１Ｃにおいて、明確な台地状の頂部は検出されていないが、わずかな傾斜が幅の狭いバー156,161の存在していることを示している。幅の広いバーおよび幅の広いスペースの数の決定（図７Ａのステップ208）は、図１２を参照して以下、詳細に説明される。最初に、システム10はＣｏｄｅ12 8記号方式（ステップ290）およびＰＤＦ４１７（ステップ292）に対する始まり／終わりパターンを試験する。これらの試験のいずれかが成功すれば、バーコード記号はその記号方式に従って処理される（ステップ294あるいは296）。そうでなければ、バーコード記号の方向が決定されなければならない（ステップ300）。これは図１３に詳細に示されている。システム10は、最初に基準となる幅の広いバー／スペースならびに幅の狭いバー／スペースを見つける（ステップ300A）。第１の１６個のピークおよび谷部を含む走査線データの領域が解析され、それによってダイナミックレンジおよびそのデータの最高値および最低値を決定する。最初に、最高値および最低値が廃棄され、最高のピークに次ぐ第２のものが基準となる幅の広いスペースとしてマークされ、最低の谷部に次ぐ第２のものが基準となる幅の広いバーとしてマークされる。次に、基準となる幅の狭いバーおよびスペースがピークおよび谷部の平均値と等しくなるように最初に設定される。システム10は、各ピークおよび谷部を順次解析する（ステップ300B）。転移がピーク（すなわちスペース）にあるとき、システム10はステップ300Cに進み、ピークが基準となる幅の広いスペースあるいは幅の狭いスペースに近いかどうかを決定する。ピークが基準となる幅の広いスペースに近い場合、それは幅の広いスペースであることが示され（ステップ300D）、基準となる幅の広いスペースは現在の幅の広いスペースと基準となる幅の広いスペースとを平均化することによって更新される（ステップ300E）。これによって幅の広いスペースの加重平均が与えられる。次にカウンタがステップ300Hにおいて増分される。ピークが幅の狭いカウンタに近い場合（ステップ300C）、カウンタは増分される（カウンタ300H）。谷部が検出された場合（ステップ300B）、システム10は、谷部（すなわちバー）が基準となる幅の広いバーと幅の狭いバーのどちらに近いかを決定する（ステップ300M）。谷部が基準となる幅の広いバーに近い場合、幅の広いバーからバーコード記号の端部までの距離Ｄ１が測定される（ステップ300G）。この手順は、第１の幅の広いバーからバーコード記号の端部までの距離Ｄ２を得るためにバーコード記号の反対の端部に対して反復される（ステップ300I）。一度、バーコード記号の両端部が解析されると（ステップ300N）、システム10は方向が前方向か後方向かを決定する（300j）。全ての幅広く使用されている２倍幅バーコード記号方式において、第１の幅の広いバーはさらに、バーコード記号の終わりに対して、最後の幅の広いバーよりもバーコード記号の始まりから遠い。従って、Ｄ１がＤ２よりも大きい場合、バーコード記号の方向は前方向であり（ステップ300K）、Ｄ２がＤ１よりも大きい場合には、バーコード記号の方向は逆である（ステップ300L）。バーコード記号の方向が決定された後（ステップ300）、システム10は図１４に示されている手順を使用して幅の広いバーおよび幅の広いスペースの数を決定する（ステップ302）。この手順は図１３に示された手順に類似しているが、システム10はバーおよびスペースの幅が狭いか広いかを決定するためにバー毎およびスペース毎に解析する。再び図１２を参照すると、一度バーコード記号の方向（ステップ300）および幅の広いバーおよび幅の広いスペースの数（ステップ302）が決定されると、システム10は使用されるバーコードの記号方式のタイプを決定する。幅の広いスペースの数が幅の広いバーの数とほぼ等しい場合（ステップ304）、バーコード記号方式は５のインターリーブされた２（５のＩ２）である（ステップ306）。幅の広いスベースの数が幅の広いバーの数の１／２とほぼ等しい場合（ステップ30 8）、バーコード記号方式はコード３９である（ステップ310）。幅の広いスペースの数が幅の広いバーの約２倍である場合（ステップ312）、バーコード記号方式はコーダバーである（ステップ314）。バーコード記号方式が５のＩ２、コード３９あるいはコーダバーに決定された場合、バーコード記号方式はその記号方式に従って処理される（ステップ318）。検出されたバーコード記号方式が全ての試験に不合格であった場合（ステップ304,308,312）、その記号方式は知られない（ステップ316）。別のタイプのバーコード記号方式を検出（ステップ315）およびデコード（ステップ317）するために付加的な試験が含まれていてもよいことが当業者によって理解されるであろう。図７Ａを再び参照すると、一度バーコード記号方式のタイプが決定されると（ステップ208）、バーコード記号情報がそのタイプの記号方式の構造の規則に従って処理される（ステップ210）。これは図１５Ａおよび図１５Ｂに詳細に示されている。図１５Ａを参照すると、簡単なデコード手順が開始される（ステップ600）。システム10は、走査線データにおけるピークおよび谷部の数が、特定の記号方式に対して予測されたピークおよび谷部の数と等しいかどうかを決定する。バーコード記号中の文字の数は、次のように幅の広いバーおよびスペースの数をカウントすることによって決定され、すなわち、コードがコード５のＩ２である場合、文字の数は幅の広いスペースの数と等しいか、あるいは幅の広いバーの数よりも１だけ少ない。コード３９の場合、文字の数は幅の広いスペースの数と等しいか、あるいは幅の広いバーの数の１／２から１引いたもの（ＷＢ／２−１）である。コーダバーの場合、文字の数は幅の広いバーの数と等しい。コード３９の文字の数は始まりおよび終わりの文字を含んでいることが理解されるべきである。ピークおよび谷部の数が特定の記号方式に対する文字の予測された数と等しい場合、走査線データはセグメントに分割される（ステップ604）。最も高いピークは幅の広いスペースとして指定され、最も低い谷部は幅の広いバーとして指定され、素子の残りは幅の狭い素子として指定される（ステップ606）。次に、各文字あるいは文字対がデコードされ（ステップ608）、それはバーコード記号の処理を完全なものにする（ステップ405）。ピークおよび谷部の数が特定の記号方式に対する文字の予測されたピークおよび谷部の数と等しくないことが決定された場合（ステップ602）、図１５Ｂに示されているようなより詳細なデコード手順が要求される。第１に、走査線全体が文字セグメントに分割され、最も高いピークは基準の幅の広いスペースとして指定され、最も低い谷部は基準の幅の広いバーとして指定される（ステップ401）。次に、システム10は幅の広い素子間の距離を測定し、幅の広い素子の間に位置している幅の狭い素子の数を計算する（ステップ402）。距離の測定は、記号方式の特徴に基づいて調整されてもよい。例えば、２つの文字の間の境界において、幅の広いバーあるいは幅の広いスペースが第１の文字あるいは第２の文字に適切であるかどうかは最初には明瞭ではない。本発明の手順によって、境界領域内に位置された１以上の幅の広い素子を使用して第１の文字をデコードする試みが許容される。この試みが不成功であった場合、幅の広い素子は第２の文字をデコードすることを試みる際に第２の文字と関連付けられてもよい。次に、システム10 は文字をデコードし、特定の記号方式が対のデコードを要求する場合には文字対をデコードする（ステップ403）。一度、全ての文字が処理されると（ステップ4 04）、バーコード記号はデコードされている。バーコード記号の処理は、図７Ａに示されているように確証されなければならない（ステップ212）。本発明の好ましい実施形態において、バーコード記号の処理の確証（ステップ212）は、後続した走査線のデコードしたものを先の走査線のデコードしたものと比較し、それによってそれらが同じであるかどうかを決定することを含んでいる。当業者によってよく知られているように、確証のしきい値は、“３つのうちの２つ”あるいは“４つのうちの３つ”の走査線が整合するようにオペレータによって所望されたように設定されてもよい。１０回の処理 (pass)の後にバーコード記号が確証されなかった場合（ステップ216）、データは鏡面前処理のために再構成される（ステップ220）。このプロセス（ステップ2 20）は、図１６Ａ乃至図１６Ｃを参照して以下説明される。ステップ220は、１次的あるいは２次的操作のいずれかであってもよい。例えば、走査されるパッケージ上で鏡面反射が予想される場合、システム10は十分な走査が捕捉された後にステップ220に直接進んでもよい。図１６Ａを参照すると、複数の読取り不可能な領域702,704,706,708を有するバーコード記号700のグレースケール画像が示されている。バーコード記号700のこのグレースケール画像の場合、システム10は読取り不可能な領域702,704,706, 708のために完全に読取り可能な確証走査線を得ることが不可能となる。領域702 ,704,706,708は、ＣＣＤ検出器20をウォッシュアウトする鏡面反射704,706,708 によって生じるか、あるいはバーコード記号700上に位置した汚れあるいはマーキング702によって生じる。複数の走査線705を示している関心のある問題の領域 703は以後説明される。図１６Ｂを参照すると、問題の領域703における走査線番号5に対するグレースケール振幅の曲線が示されている。鏡面反射およびバーコード記号700上の黒いマーキングによって、走査線に沿った画素のグレースケール値に大きな差が生成される。図１６Ｆに示されているように、鏡面反射によって選択された画素のグレースケール値が極端に高くなってしまう。同様に、バーコード記号700上の黒いマークによってグレースケール値が極端に低くなっていまう。これによって、バーコード記号700のデコードの際にエラーが生じる。好ましい実施形態において、バーコード記号700のデコードが実行されるようにデータが再構成される。各列中の画素は、各列中の最大値が最も上の行に表れ、最小値が底部の行に現れるように選別される。この技術を使用して、鏡面反射による画像の部分は最上部に浮かび、黒いマーキングによる画像の部分は底部に沈む。従って、中央の行は、完全なバーコード記号を正確に表す可能性のあるデータを含んでいる。データの選別は、画像に関する低域通過フィルタとして機能し、それは、画像を捕捉するために使用されたＣＣＤ画素グリッドの解像度が低く、整列がわずかに不規則であるためである。本発明に従って選別されたグレースケール画像が図１６Ｃに示されている。より高い（従ってより明るい）グレースケール値がグレースケール画像の最上部に位置し、より低い（従ってより暗い）値は画像709の底部に位置することが明確にわかる。画像709の中央部分は、バーコード記号を表す正確な情報を含んでいる。選別された画像709に関連したグレースケール値が図１６Ｇに示されている。図１６Ｄを参照すると、各画素に関連したデータの選別後の走査線5に沿った曲線が示されている。選別プロセスは、実際のバーコード記号を表す可能性のない極端なピークおよび谷部を排除することによってデータを標準化する。画素の選別はまた、画素のエイリアシングの影響を取除く。当業者によってよく知られているように、グレースケール値は、バーコード画像上での画素の整列の関数である。エイリアシングは、ＣＣＤ画素がバーおよびスペースに関して不整列であるときに生じる。例えば、図１６Ｅに示されているように、画素がスペースに関して不整列である場合、低い振幅のパルスが得られる。しかしながら、画素が正確に整列されると、より高い方形パルス出力が得られる。画素値の選別によって不整合性が標準化され、それによって走査線中の類似した幅の素子が類似したグレースケール値を有するようになる。一度、エイリアシングの影響が取除かれると、続いてコード化された情報を決定するために任意の多数倍幅の素子コードに対してグレースケール構成解析を行うことができる。グレースケール構成解析は、図１９を参照して以後詳細に説明される（ステップ914）。図１７Ａおよび図１７Ｂを参照すると、本発明によるバーコード記号の位置決定（ステップ800）の別の方法が示されている。まず、画像バッファは解析のためにメモリにコピーされる（ステップ802）。画像は２進化され（ステップ804）、それによって限界しきい値よりも大きいグレースケール値を有する画素は白として指定され、限界しきい値よりも小さいグレースケール値を有する画素は黒として指定される。画像はグリッドに分割され（ステップ806）、そこにおいて水平線および垂直線は画像全体に亘って配置される。グリッドラインは両方向に等しく間隔を隔てられるが（例えは、垂直方向および水平方向に３２画素おきに）、ブロックが正方形である必要はない。システム10は、各グリッド素子の中心付近における転移をサーチする（ステップ808）。この目的は、バーコード記号上の汚れあるいはその他の外部からのマークによる雑音（ノイズ）を取除くためにブロック中に最も長いスパンの線を位置することである。最初に、ブロックの中心上に“十字線”を配置することによってブロックが分割される。十字線の中心から開始して外方に向かって移動し、システム10はブロック内における第１の転移（黒から白へ、あるいは白から黒へ）をサーチする。水平方向あるいは垂直方向のいずれにおいても転移が発見されなかった場合（ステップ810）、ブロックはスパンの線を含んでいないと考えられる。より迅速な処理のために、システム10は十字線の中心近くの転移だけを考慮するのでもよい。転移が見られなかった場合、新しいグリッドブロックが選択され（ステップ812）、転移のサーチが再び開始される（ステップ808）。転移が発見された場合（ステップ810）、転移のエッジ部が追跡されなければならない。転移のエッジ部を追跡するとき（ステップ814）、次の２つのことが行われてもよい：１）エッジ部は結果的にグリッドブロックのエッジ部に到達する、または２）エッジ部はそれ自体の上で開始点と同じ点にラップアラウンドを行う。エッジ部がラップアラウンドを行った場合（ステップ816）、グリッドブロックはスパンの線を有しておらず、新しいグリッドブロックが試験される（ステップ812）。次に、システム10は、エッジ部が、最初の転移と最も遠いグリッド素子のエッジ部との間の直線に沿った画素の最大数を超過するかどうかを決定しなければならない。ブロックのエッジ部に到達する前に画素の最大数を超過した場合（ステップ818）、サーチは終了することができ、それは、転移のエッジ部がスパンの線に導かれることができないからである。最大数の画素を使用することによって、例えば螺旋等のブロックのエッジ部に到達する際の転移のふらつきを排除する。転移のエッジ部がブロックのエッジ部に到達した場合、システム10は最初の転移に戻り、反対方向にエッジ部を追跡する（ステップ822）。反対方向への追跡が最大数の画素内でブロックのエッジ部に到達できなかった場合、そのブロックはスパンの線を含んでいないものと考えられる。システム10が両方向での線の追跡に成功した場合（ステップ820）、その線が真のスパンの線であるかどうかを確証するために一連の試験が行われる。第１に、システム10は、スパンの線の両端部がブロックの同じ側に到達するかどうかを決定する（ステップ824）。そうである場合、スパンの線は無効である。次に、システム10は、スパンの線全体が画素の最大数を超過するかどうかを決定する（ステップ826）。超過しない場合、スパンの線は有効なスパンの線として確証される（ステップ830）。一度、有効なスパンの線が特定のブロックに対して決定されると、全てのブロックに対して同じ手順が行われる。各スパンの線の方向は、それぞれ追跡されたエッジ部の端部点によって形成された傾斜を使用して決定されてもよい。線の方向は、その特定の線の角度である。次に、方向を定められたブロックは集められてバーコードの候補にされなければならない。典型的な状況において、ブロックのほとんどはスパンの線を有さない。スパンの線のないブロックは方向を有しない。有効なバーコードの候補からのブロックは、所定の許容レベル内で同じスパンの線の方向を有するべきである。簡単な場合として、標準カラーブロブ（色染み）解析アルゴリズムが行われる。カラーブロブ解析において、線の各方向は特定の色を割当てられる。類似したカラーを有する全ての正方形は一緒のグループにされ、１つのブロブを形成する。従って、ブロブ中の全ての正方形は類似した角度方向を有する。所定の地理学的パターンは、類似して方向づけられたグリッド素子を有するブロブを有する。図１８Ａに示されているように、偽の(imposter)パターンが幾つかの長い線を有している場合、それは有効なバーコード記号であるように見える長細いブロブを生成することもある。しかしながら、偽のブロブはその長さに平行な方向を有している。図１８Ｂを参照すると、バーコード記号は類似したブロブを生成するが、カラーは異なっており、それは、その方向がその幅に平行だからである。この手順を使用すると、最終的な候補はフィルタ処理されるか、あるいは予備の候補が前もって選別される。好ましい多数倍幅バーコードのデコード方法が図１９に示されている。ステップ900を参照すると、システム10は多数倍幅バーコード記号のスタートおよびストップパターンを解析し、それによってどのタイプの記号方式が存在しているかを決定する。当業者によってよく知られているように、コード128、ＵＰＣおよびＥＡＮは４つの異なる幅（１、２、３および４つの素子幅）を有しているバーおよびスペースを含んでいる。それ以上の幅を有しているコードもあり、例えばＰＤＦ417は６つの幅を有している。グレースケール振幅レベルは、画素のエイリアシングの影響が除かれた後に異なる幅のバーおよびスペースのそれぞれに対して選択される。グレースケールレベルは、スタートおよびストップパターンを解析することによって計算されるか、あるいは問題となっている領域内に位置したグレースケール振幅を幅に関して格付けすることによって決定され、そこにおいて最長の継続期間を有する最も高い台地状の頂部は最も幅の広いスペースに対応し、最長の継続期間を有する最も低い台地状の底部は最も幅の広いバーに対応する。グレースケールレベルが例えば図２０の４Ｘの素子などの台地状部分に到達したとき、素子の幅は解像されたものと考えられる。グレースケールの構成の解折によって、解像されていない素子の幅の残りが検査される。これらの素子の幅は、図２０に示されているように比例して最も幅の広い素子（４Ｘ）の間に入る。システム10は、バーコード記号内のトリガ線に沿ってデータを順次抽出し（ステップ904）、各画素に対応するデータを数字的に選別し（ステップ906）、バーコード記号の鏡面反射および損傷したあるいは読取り不可能な部分をフィルタ処理して取除く。鏡面反射および損傷したバーコード記号がない場合でも、各画素に対応するデータの選別は、ピークおよび谷部の振幅を標準化することが要求される。選別の手順は、図１６Ａ乃至図１６Ｃを参照して先に詳細に説明されている。１組のデータが決定された後、システム10は基本的にバーあるいはスペースの幅であるラン長を計算する（ステップ908）。図２１を参照すると、幅は、次の式を使用してバーあるいはスペースに対応するグレースケール波形の選択された部分の下の面積を計算することによって決定され、ここにおいて最小面積はスタート／ストップパターンにおける最も幅の狭い素子の領域である。コード１２８のバーコードがこの例において使用されているが、この手順はいずれの多数倍幅記号方式にも等しく適用できることは理解されるべきである。コード１２８の場合、各文字は３つのバーおよび３つのスペースを有しており、各文字の幅は全ての文字に対して同一である。従って、６個の素子の幅の合計がコード１２８の文字の幅に対して予め定められた値を超過しないかどうかを決定するために文字の幅が評価される（ステップ910）。システム10は、文字がデコード可能かどうかをラン長データの解析だけに基づいて決定する（ステップ912）。文字がデコード可能である場合、その文字はデコードされる。文字がデコード可能でない場合、解像されなかった素子の幅はグレースケール構成解析を使用して解像される（ステップ914）。例えば、一緒に合わせられた１つの幅のスペースと１つの幅のバーが２つの幅のバーに先行している状況について考えてみる。これによって４つの幅の素子が与えられる。その４つの幅の素子のグレースケール値が解析されたとき、グレースケール値は４つの幅のバーよりも２つの幅のバーに近いことが明らかとなる。この方法において、システム10は２つの幅のバーが存在していることを決定する。残りの素子は、同じ方法で順次解析される。従って、式（７）を使用して、デコードされる文字の部分内に存在しているバーおよびスペースが次のように解像される。上述の例を使用して、解像されていない素子あるいは欠けている素子の数は次のように計算され、すなわち、解像されていない素子の数＝（４−２）／１＝２である。一度、グレースケール構成解析を使用して幅が解像されると（ステップ914）、文字がデコードされる（ステップ916）。幅を解像する際（ステップ914）、システム10は、存在している素子が多すぎると決定するかもしれない。この場合、一度、６個の素子を有する文字が解像され（ステップ914）、デコードされる（ステップ916）と、さらなる解析のために余分な素子が持ち越される（ステップ9 20）。より多くのデータが存在している場合（ステップ918）、システム10は次の文字を解析し（ステップ920）、その文字の評価は上述のように実行される。それ以上データが存在しない場合（ステップ918）、バーコード記号は首尾よくデコードされる（ステップ922）。本発明は好ましい実施形態を詳細に参照することによってある程度説明されてきたが、そのような詳細は本発明に制限を課すものではなく、むしろ説明的なものである。本明細書に開示された本発明の意図および技術的範囲から逸脱せずに、構造および動作モードにおいて多数の変更が行われることは当業者には明らかである。

【手続補正書】特許法第１８４条の８第１項【提出日】１９９８年８月２１日（１９９８．８．２１）【補正内容】明細書高速画像捕捉システムおよび方法発明の背景発明の分野本発明は、一般的にコード化された情報記号の形態の画像を捕捉するためのシステムおよび方法に関する。特に、本発明は、特に不明瞭で不良に印刷されたあるいは汚れたバーコード記号の位置を決定し、デコードするシステムおよび方法に関する。従来技術の説明バーコード記号は、様々な幅を有する典型的に長方形のバーあるいは素子から形成されている。素子の特定の配置は、使用されたコードあるいは“記号方式” によって特定された１組の規則に従って文字を定める。所望の一連の文字をコード化するために、一群の素子配置がつなぎ合わされて完全なバーコード記号が形成され、メッセージの各文字は特有の素子のグループによって表される。幾つかの記号方式において、どこでバーコード記号が始まり、どこで終わるのかをそれぞれ示すために特有の“スタート”および“ストップ”文字が使用されることある。ＵＰＣ／ＥＡＮ、コード３９、コード１２８、コーダバー、ＰＤＦ４１７および５のインターリーブされた２（５のＩ２）を含む多数の異なるバーコード記号方式がある。印刷物の表面上に表されたバーコード記号等の画像を捕捉し、捕捉されたバーコード記号を読み取ってデコードするために種々の光学式文字読取り装置および光走査システムが開発されてきた。走査システムは、典型的にバーコード記号を照射するためのレーザ光源と、その記号から反射された光を検出するための光検出器とを含んでいる。別の一般的なタイプの光走査装置は、非レーザ光源と、荷電結合素子（ＣＣＤ）検出器とを備えている。記号から反射された光の一部はＣＣＤ検出器によって検出され、走査されたバーコード信号のデジタル画像を与える電気信号に変換される。従来技術によるスキャナの例は、EP-A-0385478A2号およびEP-A-0582911A2号明細書に記載されている。バーコード記号が静止しており、明瞭に見え、傷がない場合等の理想的な状態においては大抵のバーコード記号は容易に読取ることができる。しかしながら、バーコード記号が高速で動く物体上に位置されているとき、幅の狭いバーおよびスペースは容易に位置が決められない。バーが汚れて読めなくなるのは、低解像度の画像生成あるいはスキャナに関するバーコード記号の高速移動のために生じる。外部からのマーキングあるいは別の汚れによっても、バーコード記号が部分的に不明瞭になることがある。多数の現在のスキャナを持つ付加的な問題は、シーケンス中の１以上の文字（スタートおよびストップ文字を含む）が正規の文字として認識されない場合に走査をデコードする試みが失敗することである。典型的に、部分的なデコーディングの結果は保存されない。結果的に、高さが短い長いバーコード記号、不鮮明に印刷されたバーコード記号、あるいは外部からのマーキングによって損なわれたバーコード記号等を含む様々なバーコード記号は、記号上の走査線を新しい方向に向けるようにオペレータが繰り返し試みない限りデコードすることは不可能である。バーコード記号は印刷上の欠陥を有していることもあり、それによって１つの歪みもない走査を達成することは不可能となる。従来のデコーディング方法を使用すると、そのようなバーコード記号は読取り不可能となり、それは記号を通って任意の単一の走査線に沿って読取っても結果的に一連の有効な文字とはならないからである。従って、走査された画像が有効なバーコードの候補であるかどうかを迅速に決定し、有効なバーコードの候補を正確にデコードするスキャナが必要とされる。発明の概要本発明は、バーコード記号を高速で捕捉し、位置を決め、デコードするための装置および方法である。本発明によるシステムは、走査された画像内の可能性のある一連のバーコードの候補の位置を定め、無効のデータを取除くためにその候補をフィルタ処理する。この方法によって、実際のバーコード記号になる可能性が最も高い情報のデコーディングに計算に関するリソースを集中させることかできる。一度、可能性のあるバーコードの候補の位置が定められると、バーコードを照射する光源12を具備している。バーコード記号18から反射された光は、感光性検出器20によって検出される。検出器20は、バーコード記号18から反射された光を表す電気信号を生成し、それはプロセッサ22に出力される。プロセッサ22は信号を解読し、バーコード記号18にコード化された情報に対応する結果的に生じた情報を出力手段24に転送する。出力手段24は、当業者によく知られているようなプリンタ、ＣＲＴあるいは情報システムである。図１に示された走査システム10は、可搬式小型ユニットにおいて実施されるか、あるいは静止ユニットであってもよく、そこにおいてバーコード記号18を有する物体は手動あるいはコンベアのいずれかによって光源12の下を通される。好ましい実施形態において、検出器20は、荷電結合デバイス（ＣＣＤ）の一次元アレイ（ライン）検出器であり、それはバーコード記号18の電子画像を検出および記憶する。走査システム10に関する付加的な詳細は、本発明の出願人に譲渡された 1996年２月２３日に出願された現在出願継続中の米国特許出願08/606,426号明細書“HIGH SPEED IMAGING APPARATUS F0R CCD BASED SCANNERS”を参照して得られる。走査システム10は、バーコード記号をデコードするために２つのステップによる方法を使用している。すなわち、１）物体上の有効なバーコードの候補の位置を決定し、２）検出されたバーコードの記号方式のタイプを決定し、その方式に従ってバーコード記号をデコードする。図２Ａおよび図２Ｂによれば、システム10は、図示されているようにバーコード記号位置決定手順40を実行する。バーコード記号18から反射された光は、ＣＣＤ検出器20内の光感知画素のアレイによって検出され、それによってバーコード記号18の電子画像を生成する。各画素は、画素によって検出された光の量を表す特定のグレースケール（中間調）値を有している。画像は、等しい寸法の画像ブロック74を有するグリッドに分割される（ステップ42）。ブロック74の寸法は、バーコード記号18の高さならびに画像の解像度に依存する。図３に示されているように、等しい寸法の画像ブロック74は水平グリッド線70および垂直グリッド線 72によって生成される。好ましい実施形態において、画素アレイは４０９６×１０２４個の画素であり、水平および垂直グリッド線70,72は垂直および水平方向請求の範囲１．一表面上の少なくとも一部分にコード化された記号を位置を決定する方法において、（ａ）前記一部分を走査してその電子的表示を生成し(20,800)、（ｂ）複数の転移に対する前記電子的表示を解析し(43,802,900)、（ｃ）複数の転移を有する表示を、その第１の転移を追跡してその高さおよび湾曲を決定することによって評価し(52,810,904,906)、（ｄ）前記第１の転移が湾曲を有することが決定されたときに前記表示を廃棄してステップ（ａ）を繰返し、（ｅ）前記第１の転移とは異なる端部の転移をサーチし(54,820)、（ｆ）前記第１の転移と前記端部の転移との間の距離を計算し(56,826,908,91 2)、（ｇ）前記高さを前記距離と比較して縦横比を決定し、（ｈ）前記縦横比が予め定められたしきい値を超過するときに前記表示を廃棄し、（ｉ）前記端部の転移を追跡してその端部の転移の高さおよび湾曲を決定し(5 2,810)、（ｊ）前記端部の転移が湾曲を有していることが決定されたときに前記表示を廃棄してステップ（ａ）を繰返し、（ｋ）さらに処理するために前記表示を保存するステップを含んでいる記号の位置決定方法。２．前記走査ステップは複数の画素を有するＣＣＤ検出器(20)を使用し、前記表示は各画素に対するグレースケール値を有している請求項１記載の方法。３．さらに、前記電子的表示と並列な第２の電子的表示を選択し、その整合部分を捜すことによって前記第２の電子的表示を有する前記電子的表示を確証するステップを含んでいる請求項２記載の方法。４．前記確証するステップはさらに、両方の前記電子的表示における各画素の値を決定し、前記第１の電子的表示における画素の値を前記第２の電子的表示における対応する画素の値と比較することを含んでいる請求項３記載の方法。５．前記電子的表示からの各画素は値Ｙ_Nを有しており、前記第２の電子的表示からの各画素は値Ｘ_Nを有しており、Ｎは画素の数を示し、Ｅは予め定められたエラー定数を表し、前記対応する画素は次の式を使用して前記予め定められたエラー定数に対して評価される請求項４記載の方法。６．コード化され、開始および終わりを有する電子的表示を解析することによってデコードする方法において、ピークを表す大きい相対値を有するデータ部分に対する前記電気的表示および谷部を表す小さい相対値を有するデータ部分に対する前記電気的表示を解析するステップ(43,802,900)を含んでおり、前記電子的表示は複数のＣＣＤ画素のそれぞれに対するグレースケールデータを有しており、前記解析ステップ(52,810,904,906)はさらに、前記ピークおよび谷部のそれぞれの大きさを決定し、前記各大きさに対するしきいを計算し、前記ピークおよび谷部のそれぞれとその計算されたしきいとを比較し、前記それぞれの比較の結果を記憶し、コード化された記号の前記開始および前記終わりの位置を前記ピークおよび谷部とに基づいて決定し(56,826,908,912)、前記ピークおよび谷部に基づいて幅の広いバーおよび幅の広いスペースの数および位置を決定するステップを含んでおり、前記位置を決定するステップはさらに、前記コード化された記号の方向を決定し、幅の広いバーおよび幅の広いスペースの前記数および位置に基づいてバーコード記号方式のタイプを決定するステップ(62,63,65,67)を含んでおり、前記方向を決定するステップはさらに、コード化された記号の始まりに最も近い幅の広いバーから前記始まりへの第１の距離を決定し、コード化された記号の終わりに最も近い幅の広いバーから前記終わりへの第２の距離を決定し、前記距離を比較し、前記第２の距離が前記第１の距離よりも大きい場合には方向は前方向であり、前記第２の距離が前記第１の距離よりも小さい場合には方向は逆であり、前記位置の決定および方向決定のステップの結果を使用して前記バーコード記号をデコードする(64,66,68)ステップを含んでいる方法。７．物体の表面から反射された光に基づいて物体上のコード化された記号の位置を決定するシステムにおいて、（ａ）物体表面の電子的表示を生成する手段(20,800)と、（ｂ）複数の転移に対する前記電子的表示を解析する手段(43,802,900)と、（ｃ）第１の転移を追跡して前記第１の転移の高さおよび湾曲を決定することによって複数の転移を有する表示を評価する手段(52,810,904,906)と、（ｄ）前記第１の転移が湾曲を有することが決定されたときに前記表示を廃棄し、ステップ（ａ）を繰り返すための手段と、（ｅ）前記第１の転移とは異なる端部の転移をサーチする手段(54,820)と、（ｆ）前記第１の転移と前記端部の転移との間の距離を計算する手段(56,826, 908,912)と、（ｇ）前記高さと前記距離とを比較して縦横比を決定する手段と、（ｈ）前記縦横比が予め定められたしきいを超過したときには前記表示を廃棄する手段と、（ｉ）前記最後の転移を追跡して前記端部の転移の高さおよび湾曲を決定する手段(52,810)と、（ｊ）前記端部の転移が湾曲を有することが決定されたときに前記表示を廃棄してステップ（ａ）を繰り返すための手段と、（ｋ）前記表示をさらに処理するために保存するための手段とを具備しているシステム。

───────────────────────────────────────────────────── フロントページの続き (81)指定国ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ，ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，ＬＵ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ，ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＧＨ，ＫＥ，ＬＳ，ＭＷ，ＳＤ，ＳＺ，ＵＧ)，ＵＡ(ＡＭ，ＡＺ，ＢＹ，ＫＧ，ＫＺ，ＭＤ，ＲＵ，ＴＪ，ＴＭ)，ＡＬ，ＡＭ，ＡＴ，ＡＵ，ＡＺ，ＢＡ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，ＣＨ，ＣＮ，ＣＵ，ＣＺ，ＤＥ，ＤＫ，ＥＥ，ＥＳ，ＦＩ，ＧＢ，ＧＥ，ＨＵ，ＩＬ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ，ＫＺ，ＬＣ，ＬＫ，ＬＲ，ＬＳ，ＬＴ，ＬＵ，ＬＶ，ＭＤ，ＭＧ，ＭＫ，ＭＮ，ＭＷ，ＭＸ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，ＲＯ，ＲＵ，ＳＤ，ＳＥ，ＳＧ，ＳＩ，ＳＫ，ＴＪ，ＴＭ，ＴＲ，ＴＴ，ＵＡ，ＵＧ，ＵＺ，ＶＮ (72)発明者ネスコビック、ミロラッドアメリカ合衆国、ペンシルバニア州 19446、ハットフィールド、メイプル・アベニュー 2058、アパートメントエル 28 (72)発明者シリーシャ、バサンスアメリカ合衆国、ペンシルバニア州 18951、クエイカータウン、サウス・テンス・ストリート 491、アパートメントディー 203 (72)発明者コーヘン、エドワードアメリカ合衆国、ニュージャージー州 08054、マウント・ローレル、ウインターベリー・コート 15

Claims

【特許請求の範囲】１．一表面上の少なくとも一部分にコード化された記号の位置を決定する方法において、（ａ）前記部分を走査してその電子的表示を生成し、（ｂ）複数の転移に対する前記電子的表示を解析し、（ｃ）複数の転移を有する表示を、その第１の転移を追跡してその高さおよび湾曲を決定することによって評価し、（ｄ）湾曲を有することが決定されたときに前記表示を廃棄してステップ（ａ）を繰返し、（ｅ）前記第１の転移とは異なる端部の転移をサーチし、（ｆ）前記第１の転移と前記端部の転移との間の距離を計算し、（ｇ）前記高さを前記距離と比較して縦横比を決定し、（ｈ）前記縦横比が予め定められたしきい値を超過するときに前記表示を廃棄し、（ｉ）前記最後の転移を追跡してその高さおよび湾曲を決定し、（ｊ）前記表示が湾曲を有していることを決定されたときに前記表示を廃棄してステップ（ａ）を繰返し、（ｋ）さらに処理するために前記表示を保存するステップを含んでいる方法。２．前記走査ステップは複数の画素を有するＣＣＤ検出器を使用し、前記表示は各画素に対するグレースケール値を有している請求項１記載の方法。３．さらに、前記電子的表示と並列な第２の電子的表示を選択し、その整合部分を捜すことによって前記第２の電子的表示を有する前記電子的表示を確証するステップを含んでいる請求項２記載の方法。４．前記確証するステップはさらに、両方の前記電子的表示における各画素の値を決定し、前記第１の電子的表示における画素の値を前記第２の電子的表示における対応する画素の値と比較することを含んでいる請求項３記載の方法。５．前記電子的表示からの各画素は値Ｙ_Nを有しており、前記第２の電子的表示からの各画素は値Ｘ_Nを有しており、Ｎは画素の数を示し、Ｅは予め定められたエラー定数として、前記対応する画素は次の式を使用して前記予め定められたエラー定数に対して評価される請求項４記載の方法。６．始まりおよび終わりを含むコード化された記号の電子的表示をデコードする方法において、大きい相対値を有し、ピークを有するデータ部分に対する前記電気的表示と、小さい相対値を有し、谷部を有するデータ部分に対する前記電気的表示を解析し、前記ピークおよび谷部に基づいてコード記号の前記始まりおよび前記終わりの位置を決定し、前記ピークおよび谷部に基づいて幅の広いバーおよび幅の広いスペースの数および位置を決定し、前記位置決定および決定のステップの結果を使用して前記バーコード記号をデコードすることを含んでいる方法。７．前記電子的表示は複数のＣＣＤ画素のそれぞれに対するグレースケールデータを含み、そこにおいて前記解析ステップはさらに、前記ピークおよび谷部のそれぞれの大きさを決定し、前記それぞれの大きさに対するしきいを計算し、前記ピークおよび谷部のそれぞれをその計算されたしきいと比較し、前記それぞれの比較の結果を記憶することを含んでいる請求項６記載の方法。８．前記位置決定ステップはさらに、前記コード化された記号の方向を決定し、幅の広いバーおよび幅の広いスペースの前記数および位置に基づいてバーコード記号のタイプを決定することを含んでいる請求項７記載の方法。９．前記方向の決定ステップはさらに、コード化された記号の始まりに最も近い幅の広いバーから前記始まりまでの第１の距離を決定し、コード化された記号の終わりに最も近い幅の広いバーから前記終わりまでの第２の距離を決定し、前記距離を比較し、そこにおいて方向は前記第２の距離が前記第１の距離よりも大きい場合には前方向であり、前記第２の距離が前記第１の距離よりも小さい場合には逆方向である請求項８記載の方法。