JP4132822B2 - 画像内のオブジェクトの発見 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、一般には画像処理の方法および装置に関し、詳細には画像内のオブジェクトを見つける高速な方法に関する。
【０００２】
【従来の技術】
多くの画像処理アプリケーションは、所与の画像内に１つまたは複数の一定のオブジェクトがあるかどうか、存在する場合にはそれが画像のどの位置にあるかを見出すことを必要とする。見つけようとするオブジェクトについて辞書が提供されている。しかし、画像内のオブジェクトの外観は辞書中の外観とは異なる可能性がある。オブジェクトの外観が変動する原因には、回転、拡大縮小、ノイズ、非線形の歪み、オブジェクト内およびオブジェクトと背景の間のコントラストの違い、およびわずかなトポロジの変動が挙げられる。実用的な画像処理法は、そのような変動がある場合でも大きな画像全体にわたって指定のオブジェクトを迅速に見つけることができなければならない。
【０００３】
当技術分野で知られる画像内のオブジェクトを見つける大抵の方法は、パターン・マッチングかトポロジ探索技術のいずれかを必要とする。これらの方法では、一般に、まず画像を前処理またはフィルタリングして、勾配や縁部など所望の特徴を強調することが必要とされる。パターン・マッチングは、上述のタイプの変動、特に非線形の変動の影響を受けやすい。トポロジ探索法は、膨張や、輪郭および骨格の発見といった操作を必要とするが、これらは非常に時間を要し、また大きな画像を迅速に処理するには計算的に非効率的である。
【０００４】
オブジェクトを探す前に画像を２値化することにより、特に画像をやはりデシメートする場合には計算時間を短縮することができる。しかし、２値化に基づく方法は特にコントラストの変動に弱い。２値化の方式と閾値の選択によっては、画像を２値化した際に画像内のオブジェクトの重要な特徴やオブジェクトと背景との区別が消失する可能性がある。画像内の輝度およびコントラストの変動のために、しばしば画像の異なる部分に異なる閾値が必要となる。
【０００５】
オブジェクト発見の応用例の中で特に困難なのは、自動化された郵便小包の仕分けである。小包の仕分け装置器は、様々な消印や小包に貼り付けられたステッカーを認識し、突き止めることができなければならない。一般には、大きな画像領域全体を走査するために非常に限られた処理時間しか割り当てられない。画像は小包運搬装置の上方にあるカメラによって取り込まれるので、小包の高さが異なることによって縮尺に大きな違いが生じる可能性がある。小包自体が物理的に歪むことにより、それに貼り付けられたステッカーが非線形に歪む。さらに、同じステッカーでも版が異なると、グレースケールのコントラストや、ストローク幅、フォント、特徴のトポロジが異なる場合がある。
【０００６】
【発明が解決しようとする課題】
本発明の目的は、画像内のオブジェクトを迅速に見つける方法および装置を提供することである。
【０００７】
本発明の一部の態様のさらなる目的は、非常に大きな画像上でも迅速に動作する、画像内のオブジェクトを見つける方法を提供することである。
【０００８】
本発明の一部の態様のさらなる目的は、オブジェクトの外観に変動がある場合でもロバストで正確な、画像内のオブジェクトを見つける方法を提供することである。
【０００９】
本発明の一部の態様のさらなる目的は、自動化された小包仕分けの用途で使用するのに適した画像内のオブジェクトを見つける方法を提供することである。
【００１０】
【課題を解決するための手段】
本発明の好ましい実施形態では、画像内で見つける関心のあるオブジェクトを、そのオブジェクトを構成する線、特にその線のストローク幅によって定義する。（本発明の応用例および特許請求の範囲に即すると、用語「線」とは、まっすぐであれ、曲がっているものであれ、あらゆる長く細い特徴を意味するものと理解されたい。）こうした線が画像に現れるときには、所定範囲内の幅を有するものと予測される。この範囲には、そのオブジェクトに属する線の既知のストローク幅が含まれるが、歪み、拡大縮小、コントラストの違い、あるいはその他の原因によって画像内の実際の線の幅に生じうる偏差をすべて反映するように拡張される。オブジェクトを見つけるために、その範囲内の幅を有するすべての特徴を求めて画像を迅速に探索する。この方法は、一般に、画像内の画素のうち少数のサブセットのみを走査することに基づいて少数の関心のある領域からなるセットを迅速に見つけることを可能にし、関心のあるオブジェクトはその領域の１つで見つかる確率が高い。
【００１１】
本発明のいくつかの好ましい実施形態では、一連の連続的な段階で関心のあるオブジェクトを求めてグレースケール画像を探索する。各段階で１つ前の段階に対して探索範囲を狭くし、求める特定オブジェクトに接近していく。最初の段階では、所定範囲内の幅を有する特徴上にあると思われる画素のクラスタを見つけることにより、関心のある領域を突き止める。次いで、関心のある領域を走査して、コントラスト・ピーク、すなわちその領域を通じて取り込まれる選択された走査線に沿って生じる大幅なグレースケールの変動を見つける。そのピークの大きさが所与の閾値を上回り、かつその幅が範囲内にあるとき、それは関心のあるオブジェクトを構成する線の１本の一部としての候補になる。領域を生成する手順において候補ピークを形態的に拡大して、「ステイン（stains）」、すなわちほぼ同じグレースケール値を有する結合された画素のグループを得る。そして、どの１つまたは複数のステインが関心のあるオブジェクトに対応するかを判定するために、各ステインに当技術分野で知られる高レベルの画像認識手順を適用する。この最終段階のみがオブジェクト自体に依存する唯一の段階であり、これは、ステインに含まれる全画素のうち非常に少数のサブセットのみに行われる。
【００１２】
本明細書に記載する方法は、特に郵便小包のラベル、記号、ステッカーを識別するのに適し、迅速な走査と仕分けの応用例で使用するのに適している。ただし、本発明の原理は、画像内の変動や歪みによる識別エラーを回避しつつ大きな画像内で関心のあるオブジェクトの位置を迅速に特定する、広範囲の他の状況にも応用することが可能である。
【００１３】
したがって、本発明の好ましい実施形態により、画像内の所定のオブジェクトを見つける方法が提供され、この方法は、
オブジェクトに属し、既知のストローク幅を有する線を選択することと、
そのストローク幅が含まれるある範囲の幅をそれら幅の間に共に定義する最大幅および最小幅を定義することと、
その範囲内の特徴幅を有する特徴を画像内で見つけることと、
その特徴を処理して、それがオブジェクトの一部であるかどうかを判定することと
を含む。
【００１４】
最大幅および最小幅の定義は、オブジェクトが画像内に現れる際にオブジェクトの線の幅に生じうる変動を判断することを含むことが好ましい。
【００１５】
好ましい実施形態では、画像内の特徴を見つけることは、
最大幅よりも狭い幅を有する画像の１つまたは複数の要素に属する画像内画素の第１の軌跡を見つけることと、
最小幅よりも狭い幅を有する画像の１つまたは複数の要素に属する画像内画素の第２の軌跡を見つけることと、
第１の軌跡と第２の軌跡の論理和を取ることと
を含む。
【００１６】
第１の軌跡を見つけることは、その画素から最大幅と等しい距離にある他の画素のグレースケール値と少なくとも所定のコントラスト閾値だけグレースケール値が異なる画素を見つけることを含むことが好ましい。これに代えて、あるいはこれに加えて、画像内の特徴を見つけることは、画像内の全画素のうちサブセットのみが軌跡への包含について検討されるように、軌跡を見つける前に画像をサブサンプリングすることを含む。さらに、これに代えて、あるいはこれに加えて、画像内の特徴を見つけることは、第１および第２の軌跡の論理和内の画素クラスタをその画像内の関心のある領域として識別することを含み、この領域はオブジェクトを含む候補となる。
【００１７】
別の好ましい実施形態では、画像内の特徴を見つけることは、
オブジェクトを含む候補である関心のある領域を画像内で識別することと、
その関心のある領域を通る走査線を選択することと、
その走査線に沿って配置された画素のグレースケール値を評価して、該範囲内の距離だけ互いから離隔しているコントラスト推移の対を見つけることと
を含む。
【００１８】
走査線を選択することは、オブジェクトの大きさに応じて決定される間隔を空けた複数の走査線を選択することを含むことが好ましい。これに代えて、あるいはこれに加えて、グレースケール値を評価することは、対のうち１つが推移のうち所与の１つのどちらか一方の側にある、走査線上の選択された画素の対の個々のグレースケール値の差が所定の閾値を超えるようにコントラストの推移を見つけることを含む。最も好ましくは、画素の対が、ストローク幅に応じて選択される距離だけ互いから離隔しているとよい。
【００１９】
特徴を処理することは、
その特徴に属する少なくとも１つの最初の画素の軌跡を見つけることと、
最も好ましくは、その少なくとも１つの最初の画素に隣接し、かつ、その少なくとも１つの最初の画素のグレースケール値に応じて設定される閾値を超えるグレースケール値を有する追加画素をその軌跡に加えることにより、その軌跡を拡大してオブジェクト中の線を再構成することと、
を含むことが好ましい。
【００２０】
軌跡に追加画素を加えることは、第１の追加画素を加えることを含むのが好ましく、軌跡を拡大することはさらに、
その軌跡中の画素に隣接し、閾値を超える個々のグレースケール値を有する追加画素をさらに加え続けることと、
軌跡がオブジェクトの大きさに応じて決定された最大サイズに達するとさらに追加画素の追加を中止することと
を含むことが好ましい。
【００２１】
特徴を処理することは、拡大した軌跡を処理してその軌跡をオブジェクトと照合することを含むことがさらに好ましい。
【００２２】
好ましい実施形態では、オブジェクトはアイテム表面の１つまたは複数のマークを含み、このマークに従って仕分けシステムによってアイテムが仕分けられ、また、特徴を処理することは、マークを識別することと、識別されたマークに応じてアイテムを仕分けることとを含む。
【００２３】
本発明の好ましい実施形態によると、画像内の所定のオブジェクトを見つける装置も提供され、この装置は、所定の最大幅と最小幅の間の範囲にある特徴幅を有する画像内の特徴を見つけるように動作可能な画像プロセッサを含み、この範囲は、オブジェクトに属する線の既知のストローク幅がその範囲内に入るように定義され、画像プロセッサはさらに、特徴を処理してそれがオブジェクトの一部であるかどうかを判定する機能を果たす。
【００２４】
この装置は、オブジェクトを含む画像を取り込み、その画像の電子的な再現を画像プロセッサに伝達するように構成された画像取り込みデバイスを含むことが好ましい。好ましい実施形態では、オブジェクトはアイテム表面上の１つまたは複数のマークを含み、このマークに従ってアイテムが仕分けられ、該装置はこのマークを読み取り、それに応じてアイテムを仕分けるように適合される。
【００２５】
本発明の好ましい実施形態によると、画像内の所定オブジェクトを見つけるためのコンピュータ・ソフトウェア製品がさらに提供され、この製品はプログラム命令が記憶されたコンピュータ可読媒体を含み、この命令はコンピュータによって読み込まれると、所定の最大幅と最小幅の間の範囲内にある特徴幅を有する画像内の特徴をコンピュータに見つけさせ、この範囲は、オブジェクトに属する線の既知のストローク幅がその範囲に入るように定義され、該命令はさらに、コンピュータにその特徴を処理させてそれがオブジェクトの一部であるかどうかを判定させる。
【００２６】
本発明は、図面と併せて解釈される、その好ましい実施形態についての以下の詳細な説明からより完全に理解されよう。
【００２７】
【発明の実施の形態】
図１は、本発明の好ましい実施形態による小包仕分けのシステム２０の概略的な図である。表面にラベル２４が貼られた小包２２は、運搬装置２６によって搬送される。好ましくはライン・カメラか、あるいはビデオまたはデジタル・スチール・カメラであるカメラ２８によって小包のグレースケール画像が取り込まれる。カメラによって取り込まれた画像はデジタル化されてプロセッサ３０に渡され、プロセッサは、下記で説明する方法を適用してラベル２４または小包２２上の他の特徴あるいはその両方を識別する。あるいは、プロセッサは、何らかの他のソースから画像を受け取るか、メモリ（図示せず）から画像を取り出すこともできる。識別されたラベルは次いで仕分け装置３２によって自動的に読み取られ、仕分け装置はそれに応じて小包の経路を決定する。
【００２８】
プロセッサ３０は、本発明の方法を実行するための適切なソフトウェアがプログラムされた汎用コンピュータを含むことが好ましい。このソフトウェアはネットワークを介してプロセッサにダウンロードすることができ、あるいは、プロセッサにインストールするためにＣＤ−ＲＯＭなどの有形の媒体によって供給することもできる。このようなソフトウェアは、他の画像処理アプリケーションでの使用のために同様に適合することができ、したがって同様の方式で他のコンピュータに供給し、インストールすることができる。あるいは、本明細書に述べる方法は、専用のハードウェアまたはプログラム可能なデジタル信号プロセッサを使用して、または、専用の要素またはプログラム可能な要素またはソフトウェアの組み合わせ、あるいはこれらすべての組み合わせを使用して実施することもできる。小包仕分けシステム２０におけるプロセッサ３０の使用はここでは例として述べており、限定ではない。
【００２９】
図２は、本発明の好ましい実施形態による画像内のオブジェクトを見つける方法を概略的に示すフロー・チャートである。この方法は特に、小包２２のラベル２４のようなオブジェクトの発見に応用することが可能である。説明が煩雑にならないように下記では画像内で単一のオブジェクトを見つけることを参照してこの方法を説明するが、この方法を単純な方式で拡張して、複数のオブジェクトを同時または連続的に見つけることが可能である。
【００３０】
カーネル発見ステップ４０で、画像全体の画素の少数のサブセットを走査して、所定範囲内の幅を有する画像の特徴上にある画素を見つける。この目的のために選択される範囲は、見つけようとするオブジェクト中の実際の線の幅に依存する。この画素をカーネルと呼ぶ。クラスタ化ステップ４２で、当技術分野で知られる任意の適切なクラスタ化アルゴリズムを使用してカーネルをグループ化してクラスタにする。例えば、画像をタイルに分割することが可能である。各タイル中のカーネルの数を数え、所与の閾値を上回る複数のカーネルを有するタイルを関心のある領域（region of interest: ROI）に属するものと識別する。
【００３１】
図３は、本発明の好ましい実施形態によるカーネル発見ステップ４０の詳細を概略的に表すフロー・チャートである。デシメート・ステップ５４で、元の画像を水平方向および垂直方向に係数Ｄによってデシメートし、したがって（ｎＤ、ｍＤ）によって与えられる（ｘ，ｙ）座標を有する画素のみを含むサブサンプリング画像を生成する。ｎおよびｍは整数である。したがって、この段階で走査すべき画素の数は元の画像よりもＤ²だけ減る。
【００３２】
画像内で求めるオブジェクトについて、画像内のそのオブジェクトを構成する線がその範囲内のストローク幅を有する可能性が高くなるように、ある範囲のストローク幅を定義する。この範囲は、最大幅ｗ₁と最小幅ｗ₂によって範囲を定める。最大幅テスト・ステップ５６で、デシメートした画像内の画素のグレースケール値Ｐ（ｘ，ｙ）を評価して、それらが次の複合条件を満たすかどうかを判定する。
ｐ（ｘ，ｙ）＜Ｔ
かつ
｛
［Ｐ（ｘ−ｗ₁，ｙ）−Ｐ（ｘ，ｙ）］＞ｔかつ［Ｐ（ｘ+ｗ₁，ｙ）−Ｐ（ｘ，ｙ）］＞ｔ
または
［Ｐ（ｘ，ｙ−ｗ₁）−Ｐ（ｘ，ｙ）］＞ｔかつ［Ｐ（ｘ，ｙ+ｗ₁）−Ｐ（ｘ，ｙ）］＞ｔ
または
［Ｐ（ｘ+ｄ₁，ｙ+ｄ₁）−Ｐ（ｘ，ｙ）］＞ｔかつ［Ｐ（ｘ−ｄ₁、ｙ−ｄ₁）−Ｐ（ｘ，ｙ）］＞ｔ
または
［Ｐ（ｘ+ｄ₁，ｙ−ｄ₁）−Ｐ（ｘ，ｙ）］＞ｔかつ［Ｐ（ｘ−ｄ₁，ｙ+ｄ₁）−Ｐ（ｘ，ｙ）］＞ｔ
｝
これらの数式で、Ｔはグレーレベルの閾値であり、ｔはコントラストの閾値であるが、これらはいずれも画像と関心のあるオブジェクトの特性に基づいて決定される。パラメータｄ₁は、ｗ₁／√２に等しい。不等式Ｐ（ｘ，ｙ）＜Ｔは、画素のグレースケール値が閾値Ｔよりも暗いかどうかをテストする。残りの不等式は、画素（ｘ，ｙ）と、その画素を中心とする直径ｗ₁の円の向かい合った側にある２点とのグレースケール・コントラストがｔより大きいかどうかをテストする。画素（ｘ，ｙ）はデシメートした画像から取られるが、円上の点はデシメートしていない元の画像から取ることができる。
【００３３】
上記の条件を満たす画素をステップ５６で「ＯＮ」とマークし、それらが最大ストローク幅ｗ₁よりも幅が狭い線上にある可能性があることを示す。最小幅テスト・ステップ５８で、今度は最小ストローク幅ｗ₂（およびそれに対応するパラメータｄ₂）を使用してこれと同じ手順をステップ５６で「ＯＮ」とマークされた画素に対して繰り返す。したがってこのステップでは、最小ストローク幅よりも幅が狭い線の上にある可能性のある画素を「ＯＮ」とマークする。ＸＯＲステップ６０で、ステップ５６および５８で「ＯＮ」とマークされた画素の論理和（排他的論理和）を取る。この論理和により、その幅が最大ストローク幅と最小ストローク幅の間である線の上にある可能性のある画素のリストが戻される。このリストは、ＲＯＩを見つけるためにステップ４２に入力する。
【００３４】
本特許出願の譲渡人に譲渡され、参照によりその開示を本明細書に組み込む米国特許出願０９／３１０，２８７は、図３のステップ５６で実施するアルゴリズムに類似のアルゴリズムを記載する。その応用例では、光学的な文字認識の実施に備えて画像を最適に２値化するためにテキスト画素を見つける目的で、所定の最大幅よりも幅が狭い線を画像内で識別する。しかし、この応用例では、より狭い最小幅以下の幅を有する線を排除するための措置は行われない。
【００３５】
図４は、本発明の好ましい実施形態によりシステム２０で取り込まれる小包２２の画像の再現であり、ステップ４２で見つけるＲＯＩ６６および６８を示している。この例では、画像内で求めるオブジェクトは三角形の郵便ステッカー６４であり、これはＲＯＩ６６に含まれている。ステップ４０で使用する最大幅と最小幅は、三角形の辺を形成する黒い境界線の幅に基づいて定義する。この段階で見つけられる他のＲＯＩ６８も、幅がステッカー６４の境界線とほぼ等しい線を含んでいる。
【００３６】
ここで図２に戻ると、コントラスト・ピーク抽出ステップ４４で、各ＲＯＩ中のグレースケール値を、そのＲＯＩを通る選択された走査線のセットに沿って走査する。走査線は水平でも、垂直でも、斜めであってもよい。１つのＲＯＩにつき１本の走査線で十分であると思われるが、探索をより堅牢なものにするために１つのＲＯＩにつき２本または３本の走査線を使用することが好ましい。最も好ましいのは、求めるオブジェクトのサイズと形状に基づいて、走査線間の相対的な方向と間隔を選択するものである。いずれの場合も、走査線はＲＯＩ中の全画素のうちわずか少数のみを含む。
【００３７】
図５は、ＲＯＩ６６を通る走査線の１本に沿ったグレースケールの画素値ｆ（ｘ）のグラフである。この図および以下の説明ではグレースケール値を反転するので、２５５が黒を表し、０が白を表す。グラフ中のピークは強いコントラストの変動に対応しており、この変動は特に、走査線が三角形のステッカー６４の暗い境界線の１つと交差する領域で見られる。こうしたピークの幅と大きさを評価するために、差分関数ｄ（ｘ）を次のように定義する。
ｄ（ｘ）＝ｆ（ｘ）−ｆ（ｘ−Ｌ）
Ｌは、求めるオブジェクト中の線の予想されるストローク幅の半分である。
【００３８】
図６は、図５の画素値ｆ（ｘ）から導出される差分関数ｄ（ｘ）のグラフである。画像内のコントラスト・ピーク（ＣＰ）は、ピーク７４および７６など、ｄ（ｘ）中の正のピークと負のピークの対の出現によって定義される。ＣＰとしての条件を満たすには、正のピークと負のピークの振幅が各自の所定の閾値を超えていなければならず、かつ、ピークとピークとの離隔が、そのオブジェクト中の線についての所定の最大幅と最小幅の制限内でなければならない。この離隔の基準に基づくと、ピーク７４と７６は１つのＣＰを表すことができ、ピーク７８と８０は別のＣＰを表すことができるが、ピーク８２と８４はＣＰを表すには離れすぎており、したがって破棄される。
【００３９】
振幅の閾値について見ると、ピーク７６と７８はピーク７４と８０に比べると相対的に弱いことが認められる。ピーク７６と７８は、ステッカー６４中の三角形の境界線と、三角形の内側の暗いグレー領域との間の推移を表している。この推移は、ピーク７４および８０によって表される、境界線間と三角形の外側の明るいグレー領域との間の推移に比べて低いコントラストによって特徴付けられる。この差に対処するために、内側のピーク７６および７８に適用する閾値は、外側のピーク７４および８０の閾値よりも低い値にすることが好ましい。求めるオブジェクトについての事前の知識に基づくこれらの閾値によって表されるコントラストの特性は、画像内のオブジェクトの向きや、走査線を左から右に分析するか、右から左に分析するかに関係なく一定である（pertain）。コントラストとピーク離隔の基準を満たすＣＰはいずれもステップ４４で候補ＣＰとしてマークする。このＣＰの位置は、対応する正のピークと負のピークの対の中心にある画素としてマークする。
【００４０】
半径テスト・ステップ４６で、ステップ４４で見つかったＣＰそれぞれについて半径を計算する。半径は、そのＣＰから最も近い「白い」画素までの距離として定義される。この目的のための白い画素は、そのグレースケール値がＣＰの中心にある画素のグレースケール値よりも所定の閾値以上明るい画素と定義する。ステップ４４では走査線に沿ってのみコントラストを測定したのに対し、ステップ４６では、ＣＰの中心画素の周囲のすべての方向でコントラストを測定する。中心画素から最も近い白い画素までの距離が所定の幅範囲の制限よりも短いか、または長い場合は、対応するＣＰを破棄する。半径の基準を満たすＣＰのみを通過させてステイン形成ステップ４８に進み、ＲＯＩ中のオブジェクトを再構成するための拡大操作をそれらのＣＰに施す。
【００４１】
図７は、本発明の好ましい実施形態によるステイン形成ステップ４８の詳細を概略的に示すフロー・チャートである。シード選択ステップ９０で、各ＲＯＩについて、拡大してステインにする際のシードとして機能させるために、ＲＯＩ中で見つかったＣＰのうち１つを選び出す。この時にコントラストの閾値も選択し、この閾値は、下記で説明するように、ＲＯＩ中の他の画素のどれをステインに属する画素のリストに追加するかを決定する際に適用される。この閾値は、例えばシードのグレースケール値（黒＝２５５）の所定の部分として、あるいは、シードとそれに近接する背景画素との画像内のコントラストに相関してなど、シードのグレースケール値に基づいて選択することが好ましい。この方式により、画像の異なる部分で生じうるコントラストまたは輝度の違いあるいはその両方の違いに対して、後に続くステイン拡大ステップを適合する。最も好ましいのは、ＲＯＩ中に複数のＣＰがある場合には、最も明るいＣＰを最初に選択してシードにすることである。この明るいＣＰに対して選択される比較的低い閾値は、同じステインに属するＲＯＩ中のより暗いＣＰをも取り込む。
【００４２】
ステインの拡大を開始するために、ポインタを初期化してそのステイン中の画素のリストにある最初の画素、すなわちシード自体（この時点ではリストにある唯一の画素）をポイントさせる。隣接画素チェック・ステップ９２で、現在ポインタによって示される画素に隣接する画素をすべて調べる。画素チェック・ステップ９４で、各隣接画素について、その画素がステインへの包含についてすでに検討されているかどうかを初めに判断する。まだ検討されていない場合は、グレースケール・チェック・ステップ９６でその隣接画素のグレースケール値を調べて、それがステップ９０で決定された閾値よりも暗いかどうかを判定する。閾値よりも暗い場合は、画素追加ステップ９８でその画素をステイン中の画素のリストに加える。隣接画素完了ステップ１００で、調べるべきシードの隣接画素がさらにあるかどうかを判定し、さらにある場合は次の隣接画素のステップ１０１で次の隣接画素を選択する。ステップ９４から１０１は、現在ポインタによって示されている画素の隣接画素すべてを調べ終わるまで繰り返される。
【００４３】
現在の画素に隣接する画素をすべて調べると、リスト・チェック・ステップ１０２で現在のステイン中画素のリストを調べて、リストに隣接画素を調べていない画素がさらにあるかどうかを判定する。リストにさらに画素がある場合は、ステインがすでに所定のサイズ制限を超えていないことを確かめるために、サイズ監視ステップ１０４でステインの現在のサイズを確認する。この制限は、画像内で求めるオブジェクトのサイズによって決まる。ステインのサイズがサイズ制限を超えている場合は、オブジェクトに対応する可能性がないステインに処理時間を浪費するのを避けるためにステインの拡大を終了する。ただしサイズ制限を超えない限りは、次の画素のステップ１０６でポインタを増分してリスト中の次の画素に進み、上記のステップを繰り返す。
【００４４】
ステップ１０２で、プロセスがリストの最後に到達したことが判明すると、ＣＰチェック・ステップ１０８で現在のＲＯＩに残りのＣＰがあればそれを調べて、その中で既存のリストに含まれなかったＣＰがあるかどうかを判定する。含まれなかったものがある場合は、ステップ９０でそのＣＰの１つを新しいシードに選択し、プロセス全体を繰り返す。画像内で複数の異なるオブジェクトを同時に求める場合は、そのオブジェクトのうち最大のオブジェクトに対応する可能性のあるＣＰを最初に拡大することが好ましい。このＣＰはステップ１０４でより大きなサイズ制限を有することになり、その結果得られる大きなステインは、より小さなオブジェクトに対応すると考えられるＣＰを拡大することによって生成されるより小さなステインを包摂することが可能なので、そのＲＯＩを完了するのに必要とされる合計処理時間が短縮されることになる。
【００４５】
図８は、図４の画像内で識別されるＲＯＩ６６および６８にステップ４４、４６、および４８（図２）を適用することによって生成されるステインのバイナリ画像の再現である。これらのステインを生成するには、間隔が三角形６４の高さの半分である走査線を使用して、ステップ４４で最初にＲＯＩ中のコントラスト・ピークを見つけた。三角形の暗い境界線は、対応するステイン中で明確に識別される。幅が三角形の境界線の幅にほぼ等しい線を偶然含んでいる他のステイン１１０および１１２も生成される。
【００４６】
最後に図２に示すオブジェクト認識ステップ５０で、ステイン画像を分析して、関心のあるオブジェクトと画像全体におけるその位置を識別する。このステップでは、バイナリのステイン画像のみか、または元の画像内の対応するグレースケール情報を使用して、当技術分野で知られる各種の画像認識アルゴリズムを適用することができる。この段階におけるアルゴリズムの最適な選択はオブジェクトの固有の特性に依存し、本発明の範囲外にある。しかし、オブジェクト認識アルゴリズムを画像全体にわたって適用しなければならない当技術分野で知られる画像処理法に比べて、このアルゴリズムを実行するのに必要とされる時間が著しく短縮し、オブジェクト識別の確率が大幅に向上することは明らかである。
【００４７】
上述の好ましい実施形態は特定タイプのグレースケール画像の処理に関連するが、カラー画像を含む実質的にあらゆるタイプの画像を処理するために本発明の原理を単純な方式で適合できることは理解されよう。したがって、上述の好ましい実施形態は例として引用したものであり、本発明は上記で具体的に示し、説明した内容には限定されないことが認識されよう。本発明の範囲には、上述の各種の特徴の組み合わせおよびサブコンビネーションと、また、前述の説明を読むことにより当業者に着想しうる、従来技術で開示されていないその変形形態と修正形態が含まれる。
【図面の簡単な説明】
【図１】 本発明の好ましい実施形態による小包仕分けシステムの概略的な図である。
【図２】 本発明の好ましい実施形態による画像内のオブジェクトを識別する方法を概略的にあらわすフロー・チャートである。
【図３】 本発明の好ましい実施形態による、特に図２のオブジェクト識別方法の状況で有用な画像内で関心のある領域を見つける方法を概略的にあらわすフロー・チャートである。
【図４】 図２および３の方法を使用して関心のある領域が識別された、図１のシステムで取り込まれる画像の再現である。
【図５】 図４の関心のある領域の１つを通る線に沿って取り込まれた画素位置に相関するグレースケール値のグラフである。
【図６】 本発明の好ましい実施形態による、図５のグレースケール値から導出される差分関数のグラフである。
【図７】 本発明の好ましい実施形態による、特に図２のオブジェクト識別方法の状況で有用な領域生長方法を概略的に表すフロー・チャートである。
【図８】 本発明の好ましい実施形態により、図４の画像に図２および図７の方法を適用することによって生成されるステインの画像の再現である。

Claims (15)

1. 画像内の所定のオブジェクトを見つける方法であって、
   前記オブジェクトに属し、既知のストローク幅を有する線を選択するステップと、
   前記ストローク幅を含むある範囲の幅を共に定義する最大幅および最小幅を定義するステップと、
   前記範囲内の特徴幅を有する特徴を前記画像内で見つけるステップと、
   前記オブジェクトの一部であるかどうかを判定するために前記特徴を処理するステップとを含み、
   前記特徴を前記画像内で見つけるステップが、
   前記最大幅よりも狭い幅を有する前記画像の１つまたは複数の要素に属する前記画像内の画素の第１の軌跡を見つけるステップと、
   前記最小幅よりも狭い幅を有する前記画像の１つまたは複数の要素に属する前記画像内の画素の第２の軌跡を見つけるステップと、
   前記第１の軌跡と第２の軌跡の排他的論理和を取るステップと
   を含む、方法。
2. 前記第１の軌跡を見つけるステップが、前記最大幅と等しい距離にある他の画素のグレースケール値から少なくとも所定のコントラスト閾値だけグレースケール値が異なる画素を見つけるステップを含む、請求項１に記載の方法。
3. 前記特徴を前記画像内で見つけるステップが、前記画像内の全画素のうちサブセットのみが前記軌跡への包含について検討されるように、前記軌跡を見つける前に前記画像をサブサンプリングするステップを含む、請求項１に記載の方法。
4. 前記特徴を前記画像内で見つけるステップが、前記第１および第２の軌跡の排他的論理和内の画素クラスタを前記画像内の関心のある領域として識別するステップを含み、
   前記領域は前記オブジェクトを含む候補である、
   請求項１に記載の方法。
5. 前記特徴を前記画像内で見つけるステップが、
   前記オブジェクトを含む候補である関心のある領域を前記画像内で識別するステップと、
   前記関心のある領域を通る走査線を選択するステップと、
   前記範囲内の距離だけ互いから離隔しているコントラスト推移の対を見つけるために、前記走査線に沿って配置された画素のグレースケール値を評価するステップと
   を含む、請求項１に記載の方法。
6. 前記走査線を選択するステップが、前記オブジェクトの大きさに応じて決定される間隔を空けた複数の走査線を選択するステップを含む、請求項５に記載の方法。
7. 前記グレースケール値を評価するステップが、対のうち１つが前記推移のうち所与の１つのどちらか一方の側にある、前記走査線上の選択された画素の対の個々のグレースケール値の差が所定の閾値を超えるように前記コントラストの推移を見つけるステップを含む、請求項５に記載の方法。
8. 前記画素の対が、前記ストローク幅に応じて選択される距離だけ互いから離隔している、請求項７に記載の方法。
9. 前記特徴を処理するステップが、
   前記特徴に属する少なくとも１つの最初の画素の軌跡を見つけるステップと、
   前記オブジェクト内の線を再構成するために、前記軌跡を拡大するステップと
   を含む、請求項１に記載の方法。
10. 前記軌跡を拡大するステップが、前記少なくとも１つの最初の画素に隣接し、かつ、前記少なくとも１つの最初の画素のグレースケール値に応じて設定される閾値を超えるグレースケール値を有する追加画素を前記軌跡に加えるステップを含む、請求項９に記載の方法。
11. 前記追加画素を前記軌跡に加えるステップが、第１の追加画素を加えるステップを含み、
    前記軌跡を拡大するステップがさらに、
    前記軌跡内の画素に隣接し、前記閾値を超える個々のグレースケール値を有する追加画素をさらに加えることを続けるステップと、
    前記軌跡が前記オブジェクトの大きさに応じて決定された最大サイズに達すると前記追加画素をさらに加えることを中止するステップと
    を含む、請求項１０に記載の方法。
12. 前記特徴を処理するステップが、前記軌跡を前記オブジェクトと照合するために前記拡大した軌跡を処理するステップを含む、請求項９に記載の方法。
13. 前記オブジェクトがアイテム上の１つまたは複数のマークを含み、このマークに従い仕分けシステムによって前記アイテムが仕分けられ、また、前記特徴を処理するステップが、前記マークを識別するステップと、前記識別されたマークに応じて前記アイテムを仕分けるステップとを含む、請求項１に記載の方法。
14. 画像内の所定のオブジェクトを見つける装置であって、所定の最大幅と最小幅の間の範囲内にある特徴幅を有する特徴を画像内で見つけるために動作可能な画像プロセッサを含み、前記範囲は前記オブジェクトに属する線の既知のストローク幅が前記範囲内に入るように定義され、前記画像プロセッサはさらに、前記特徴を処理してそれが前記オブジェクトの一部であるかどうかを判定するように動作可能であり、
    更に、前記最大幅よりも狭い幅を有する前記画像の１つまたは複数の要素に属する前記画像内の画素の第１の軌跡、および前記最小幅よりも狭い幅を有する前記画像の１つまたは複数の要素に属する前記画像内の画素の第２の軌跡を見つけて、前記第１の軌跡と第２の軌跡の排他的論理和を取るように動作可能である装置。
15. 画像内の所定のオブジェクトを見つけるために、コンピュータに、
    前記オブジェクトに属し、既知のストローク幅を有する線を選択する手順と、
    前記ストローク幅を含むある範囲の幅を共に定義する最大幅および最小幅を定義する手順と、
    前記最大幅よりも狭い幅を有する前記画像の１つまたは複数の要素に属する前記画像内の画素の第１の軌跡を見つける手順と、
    前記最小幅よりも狭い幅を有する前記画像の１つまたは複数の要素に属する前記画像内の画素の第２の軌跡を見つける手順と、
    前記第１の軌跡と第２の軌跡の排他的論理和を取る手順と
    前記オブジェクトの一部であるかどうかを判定するために前記特徴を処理する手順と、
    を実行させるためのコンピュータ・プログラム。

Images