(57)【要約】  本発明の第１の例証的な実施形態において、画像の照明境界を決定する自動化およびコンピュータ化された方法を提供する。本方法は、画像の予め選択された局所領域において動的サンプリングを実行して、予め選択された局所領域の各々において当該画像のスペクトル比情報を決定するステップと、スペクトル比情報を用いて照明境界を識別するステップとを含んでいる。
2008529169.tif 000002
【特許請求の範囲】
【請求項１】
画像内の照明光束を決定する、自動化およびコンピュータ化された方法であって、
前記画像の予め選択された局所領域で動的サンプリングを実行して、前記予め選択された局所領域の各々での前記画像のスペクトル比情報を決定するステップと、
前記スペクトル比情報を用いて照明光束を識別するステップとを含む方法。
【請求項２】
前記動的サンプリングのステップが、前記画像内のトークン領域を識別し、かつ、前記トークン領域の隣接関係の解析を実行するステップにより実施されて前記スペクトル比情報を決定する、請求項１に記載の方法。
【請求項３】
前記トークン領域の隣接関係の解析を実行するステップが実施されて、前記画像内のＸ接合を識別し、前記Ｘ接合を用いて前記スペクトル比情報を決定する、請求項２に記載の方法。
【請求項４】
前記トークン領域の隣接関係の解析を実行するステップが、トークン領域グラフを生成するステップにより実施される、請求項３に記載の方法。
【請求項５】
前記スペクトル比情報がＳ＝暗部／（明部−暗部）を含む、請求項１の方法。
【請求項６】
前記スペクトル比がＳの正規化された値を含む、請求項５に記載の方法。
【請求項７】
前記画像内のトークン領域を識別するステップが、ピクセルのシード領域を選択して、色特性の類似性の有無についてシード領域のピクセルをテストし、良好なシードであると判定された場合、前記シード領域のピクセルの良好な隣接ピクセルを識別するステップにより実施される、請求項２に記載の方法。
【請求項８】
前記トークン領域グラフを生成するステップが、各トークン領域の周辺ピクセルを識別し、各周辺ピクセルについて、最大距離以内にある他の各トークン領域に最も近い周辺ピクセルを検出して、前記検出ステップにおいて前記最大距離以内で検出されたピクセルに対応する全てのトークン領域のリストを編集するステップにより実施される、請求項４に記載の方法。
【請求項９】
前記画像内のＸ接合を識別するステップが、隣接トークンの一連の反復的な選択を実行して、Ｘ接合パラメータに関係する隣接特性のテストを実行するステップにより実施される、請求項３に記載の方法。
【請求項１０】
前記Ｘ接合を用いて前記スペクトル比情報を決定するステップが、各Ｘ接合の各々の明部／暗部ピクセル対についてスペクトル比を計算して、各Ｘ接合について計算されたスペクトル比に対して平均シフト・アルゴリズムを実行するステップにより実施される、請求項３に記載の方法。
【請求項１１】
前記スペクトル比が暗部／（明部−暗部）に等しい、請求項１０に記載の方法。
【請求項１２】
前記スペクトル比情報を用いて照明光束を識別するステップが、境界における選択された色値の対のスペクトル比を、前記計算されたスペクトル比に対して平均シフト・アルゴリズムを実行するステップから得られた平均スペクトル比と比較して合致の有無を判定するステップにより実施される、請求項１０に記載の方法。
【請求項１３】
画像内の照明境界を決定する自動化およびコンピュータ化された方法であって、
前記画像内のＸ接合を識別するステップと、
前記識別されたＸ接合により定義される前記画像の領域のスペクトル比を決定するステップと、
前記スペクトル比を用いて照明境界を識別するステップとを含む方法。
【請求項１４】
前記Ｘ接合を識別するステップが、前記画像内のトークン領域を識別し、トークン領域の隣接関係の解析を実行して前記画像内のＸ接合を識別するステップにより実施される、請求項ｌ３に記載の方法。
【請求項１５】
前記トークン領域の隣接関係の解析を実行するステップが、隣接トークンの一連の反復的な選択およびＸ接合パラメータに関係する隣接特性のテストを実行するステップにより実施される、請求項１４に記載の方法。
【請求項１６】
前記識別されたＸ接合により定義される前記画像の領域のスペクトル比を決定するステップが、前記Ｘ接合の各々の明部／暗部ピクセル対についてスペクトル比を計算し、前記Ｘ接合について計算されたスペクトル比に対して平均シフト・アルゴリズムを実行するステップにより実施される、請求項１３に記載の方法。
【請求項１７】
前記スペクトル比が暗部／（明部−暗部）に等しい、請求項１６に記載の方法。
【請求項１８】
前記スペクトル比がＳの正規化された値を含む、請求項１７に記載の方法。
【請求項１９】
前記スペクトル比を用いて照明境界を識別するステップが、境界における選択された色値の対のスペクトル比を、前記計算されたスペクトル比に対して平均シフト・アルゴリズムを実行するステップから得られた平均スペクトル比と比較して合致の有無を判定するステップにより実施される、請求項１６に記載の方法。
【請求項２０】
画像内の照明境界を決定する自動化およびコンピュータ化された方法であって、
前記画像の空間スペクトル情報を識別するステップと、
前記空間スペクトル情報を用いてスペクトル比情報を計算するステップと、
前記スペクトル比情報を用いて照明光束を識別するステップとを含む方法。
【請求項２１】
前記空間スペクトル情報を識別するステップが、トークンの隣接関係の解析を実行するステップにより実施される、請求項２０に記載の方法。
【請求項２２】
前記トークンの隣接関係の解析を実行するステップが、Ｘ接合を識別すべく実施される、請求項２１に記載の方法。
【請求項２３】
前記トークンの隣接関係の解析を実行するステップが、前記画像の複数の予め選択された局所領域の各々で実施される、請求項２１に記載の方法。
【請求項２４】
前記画像の空間スペクトル情報を識別するステップが、前記画像の複数の予め選択された局所領域の各々で実施される、請求項２０に記載の方法。
【請求項２５】
前記空間スペクトル情報を識別するステップが、隣接トークン間での反射率とスペクトル比の関係の解析を実行するステップにより実施される、請求項２０に記載の方法。
【請求項２６】
前記トークンの隣接関係の解析を実行するステップが、Ｎ次トークンを識別して、前記Ｎ次トークンの隣接トークン間での反射率とスペクトル比の関係を比較するステップにより実施される、請求項２１に記載の方法。
【請求項２７】
前記スペクトル比情報がＳ＝暗部／（明部−暗部）を含む、請求項２０に記載の方法。
【請求項２８】
前記スペクトル比がＳの正規化された値を含む、請求項２７に記載の方法。
【請求項２９】
前記空間スペクトル情報を用いてスペクトル比情報を計算するステップが、前記画像の特徴的照明光強度比を決定することにより実施され、前記スペクトル比情報を用いて照明光束を識別するステップが、暗部／明部色対のスペクトル比を前記特性照明光強度比と比較して合致の有無を判定するステップにより実施される、請求項２０に記載の方法。
【請求項３０】
ＣＰＵと、
画像ファイルを保存するメモリとを含み、
前記ＣＰＵが、前記画像から空間スペクトル情報を識別するルーチンを実行し、前記空間スペクトル情報を用いてスペクトル比情報を計算して、前記計算スペクトル比を用いて前記画像内の照明光束を識別すべく構成および設定されている、コンピュータシステム。
【請求項３１】
前記ＣＰＵが、隣接トークン間での反射率とスペクトル比の関係の解析により空間スペクトル情報を識別する、請求項３０のコンピュータシステム。
【請求項３２】
前記ＣＰＵが、Ｘ接合の解析により前記空間スペクトル情報を識別する、請求項３０に記載のコンピュータシステム。
【請求項３３】
前記ＣＰＵが、前記画像の複数の予め選択された局所領域の各々で前記空間スペクトル情報を識別する、請求項３０に記載のコンピュータシステム。
【請求項３４】
前記スペクトル比情報がＳ＝暗部／（明部−暗部）を含む、請求項３０に記載のコンピュータシステム。
【請求項３５】
前記スペクトル比がＳの正規化された値を含む、請求項３４に記載のコンピュータシステム。
【請求項３６】
画像内の照明情報を決定する自動化およびコンピュータ化された方法であって、
前記画像の空間スペクトル情報を識別するステップと、
前記空間スペクトル情報を用いて前記画像のスペクトル比情報を計算するステップとを含む方法。
【請求項３７】
前記空間スペクトル情報を識別するステップが、トークンの隣接関係の解析を実行するステップにより実施される、請求項３６に記載の方法。
【請求項３８】
前記トークンの隣接関係の解析を実行するステップが、Ｘ接合を識別すべく実施される、請求項３７に記載の方法。
【請求項３９】
前記トークンの隣接関係の解析を実行するステップが、前記画像の複数の予め選択された局所領域の各々で実施される、請求項３７に記載の方法。
【請求項４０】
前記画像の空間スペクトル情報を識別するステップが、前記画像の複数の予め選択された局所領域の各々で実施される。請求項３６に記載の方法。
【請求項４１】
前記空間スペクトル情報を識別するステップが、隣接トークン間での反射率とスペクトル比の関係の解析を実行するステップにより実施される、請求項３６に記載の方法。
【請求項４２】
前記スペクトル比情報がＳ＝暗部／（明部−暗部）を含む、請求項３６に記載の方法。
【請求項４３】
前記スペクトル比がＳの正規化された値を含む、請求項４２に記載の方法。
【請求項４４】
画像内の照明情報を決定する自動化およびコンピュータ化された方法であって、
前記画像のスペクトル比情報を計算するステップと、
前記画像のスペクトル比情報を用いて前記画像の照明情報を識別するステップとを含む方法。
【請求項４５】
前記スペクトル比情報が、スペクトル比Ｓ＝暗部／（明部−暗部）を含む、請求項４４に記載の方法。
【請求項４６】
前記照明情報が前記画像内の照明光束を含む、請求項４４に記載の方法。
【請求項４７】
前記照明光束が照明境界を含む、請求項４６に記載の方法。
【発明の詳細な説明】
【関連出願の相互参照】
【０００１】
本出願は、２００５年１月２７日に出願された米国仮出願第６０／６４８，２２８号および２００５年２月３日に出願された米国仮出願第６０／６５０，３００号を優先権主張するものであり、それらを本明細書に引用している。
【背景技術】
【０００２】
最新のコンピュータ技術の顕著且つ商業的に重要な利用の多くは画像関連のものである。これらには画像処理、画像解析、およびコンピュータ視覚のアプリケーションが含まれる。画像関連の動作を厳密且つ正確に実行するためのコンピュータ利用において、視覚的世界で生じている物理的現象を真に反映および表現するアルゴリズムの開発が課題である。例えば、画像内で影と有体物のエッジを正確且つ厳密に区別する能力をコンピュータに持たせることが科学者にとって長年の課題であった。有形物のエッジを厳密且つ正確に検出しないことには画像に対して他の処理が一切不可能なため、エッジの検出は画像処理の基本的作業である。生じた影と、その影を生じさせる対象とが区別できなければ、コンピュータが対象を認識することは不可能であろう。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
対象のエッジ検出における当初の、且つ従来の方式には、画像における明度境界の解析が含まれる。そのような解析において、有形物により生じる境界が鮮明であるのに対し、影により生じた境界は影の半影効果に起因してぼやけているかまたは段階的であると仮定される。この方式は、コンピュータが正確に実行できるアルゴリズムにより実装可能であるが、往々にして結果は正しくない。現実世界では、影が鮮明な境界を形成し、逆に有形物のエッジがぼやけた境界を形成する例が多くある。このように、影およびエッジの認識に従来の技術を利用する際に、影の認識に対して偽陽画および偽陰画が生じる可能性が高い。すなわち、例えば、影を模倣している物体のエッジが、このためにコンピュータにより影または鮮明な影の境界として誤認され、対象の境界として誤って解釈されてしまう。従って、画像に関するコンピュータの動作で利用できる厳密且つ正確な技術の開発が常に必要とされている。
【課題を解決するための手段】
【０００４】
本発明は、視覚的世界で生じている物理的現象を厳密且つ正確に反映および表現する画像技術を含む方法およびシステムを提供する。
【０００５】
本発明の第１の例証的な実施形態において、画像の照明光束を決定すべく自動化およびコンピュータ化された方法を提供する。本方法は、画像の予め選択された局所領域において動的サンプリングを実行して、予め選択された当該局所領域の各々における画像のスペクトル比情報を決定するステップと、当該スペクトル比情報を用いて照明光束を識別するステップを含んでいる。
【０００６】
本発明の第２の例証的な実施形態において、画像の照明境界を決定すべく自動化およびコンピュータ化された更なる方法を提供する。本発明の第２の例証的な実施形態による方法は、画像内でＸ接合を識別するステップと、識別されたＸ接合により定められる画像の領域に対するスペクトル比を決定するステップと、スペクトル比を用いて照明境界を識別するステップとを含んでいる。
【０００７】
本発明の第３の例証的な実施形態において、画像の照明光束を決定すべく自動化およびコンピュータ化された方法は、画像の空間スペクトル情報を識別するステップと、空間スペクトル情報を用いてスペクトル比情報を計算するステップと、スペクトル比情報を用いて照明光束を識別するステップとを含んでいる。
【０００８】
本発明の第４の例証的な実施形態において、コンピュータシステムを提供する。本コンピュータシステムは、ＣＰＵと、画像ファイルを保存しているメモリとを含んでいる。本発明の特徴に従い、ＣＰＵは、画像から空間スペクトル情報を識別するルーチンを実行し、空間スペクトル情報を用いてスペクトル比情報を計算し、計算されたスペクトル比情報を用いて画像の照明光束を識別すべく構成および設定されている。
【０００９】
本発明の第５の例証的な実施形態において、画像における照明情報を決定する自動化およびコンピュータ化された方法は、画像の空間スペクトル情報を識別するステップと、当該空間スペクトル情報を用いて画像のスペクトル比情報を計算するステップとを含んでいる。
【００１０】
本発明の第６の例証的な実施形態において、画像の照明情報を決定する自動化およびコンピュータ化された方法は、画像のスペクトル比情報を計算するステップと、当該画像のスペクトル比情報を用いて画像の照明情報を識別するステップとを含んでいる。
【００１１】
本発明の更に他の実施形態に従い、上述の方法を実行すべく構成された１個以上のコンピュータ（例えば、プログラムされたもの）を含むコンピュータシステムを提供する。本発明の他の実施形態に従い、上述の実施形態を実行すべく実装されたコンピュータ（群）を制御すべく動作可能である、コンピュータが実行可能な処理ステップを保存したコンピュータ可読媒体を提供する。自動化およびコンピュータ化された方法は、デジタル・コンピュータ、アナログ・コンピュータ、光学センサ、状態機械、シーケンサ、あるいは本発明の方法のステップを実行すべく設計またはプログラム可能な任意の機器または装置により実行することができる。
【発明を実施するための最良の形態】
【００１２】
ここで図面、最初に図１を参照するに、画像に関する処理を実行すべく構成および設定されたコンピュータシステム１０のブロック図を示す。ＣＰＵ１２は、例えばＵＳＢポートを介してデジタル・カメラ１４等の装置に接続されている。デジタル・カメラ１４は、カメラ１４にローカルに保存されている画像をＣＰＵ１２にダウンロードすべく動作する。ＣＰＵ１２は、ダウンロードされた画像を画像ファイル１８としてメモリ１６に保存する。画像ファイル１８は、モニター２０に表示すべく、またはプリンタ２２に印刷出力すべくＣＰＵ１２からアクセスすることができる。
【００１３】
代替的に、ＣＰＵは、例えばデジタル・カメラ１４またはロボット等の機器に組み込まれたマイクロプロセッサとして実装することができる。ＣＰＵはまた、ロボット動作またはユーザーとの対話的動作と連携して、画像関連のリアルタイム動作を行なうべくリアルタイム・オペレーティングシステムを備えることができる。
【００１４】
図２に示すように、各画像ファイル１８はｎ×ｍピクセル配列を含んでいる。各ピクセルｐは、画像全体の離散的部分に対応する画素である。全てのピクセルが共に画像ファイル１８により表現される画像を定義する。各ピクセルは、色帯域の集合、例えば画素の赤、緑、青色要素（ＲＧＢ）に対応するデジタル値を含んでいる。本発明は、各帯域が電磁気スペクトルの一部に対応する任意の多帯域画像に適用可能である。本発明はまた、単一のパンクロマティック帯域を用いて、グレイスケール画像（単一帯域）と連携して利用することもできる。ピクセル配列は、各々ｍ列を有するｎ行を含んでおり、ピクセルｐ（１，１）から始まってピクセルｐ（ｎ，ｍ）で終わる。画像の表示または印刷に際して、ＣＰＵ１２はメモリ１６から対応する画像ファイル１８を取り出し、一般に知られる通り画像ファイル１８のピクセルのデジタル値の関数として、場合に応じてモニター２０またはプリンタ２２を動作させる。
【００１５】
画像動作において、ＣＰＵ１２は、例えば被写体画像の有形物エッジ検出等、各種の目的を達成すべく、保存されている画像ファイル１８のピクセルのＲＧＢ値を解析すべく動作する。本発明の基本的発見の根本をなす基本的所見は、画像が２個の成分、すなわち物体および照明を含んでいる点である。画像における全ての変化は、これらの成分の一方または他方により生じる。これらの成分の一方、例えば照明を検出する方法は、対象のエッジ等、物体または対象の形状を照明から区別する仕組みを提供する。
【００１６】
ＣＰＵ１２により保存された画像ファイル１８を表示した際に肉眼に見えるものは、例えばデジタル・カメラ１４により撮影されたシーン内にある有形物の鏡面反射および内部反射特性と、その写真が撮影された時点に存在した照明光束との相互作用により生じるピクセル・カラー値である。照明光束は、周辺照明光および入射照明光を含んでいる。入射照明光は、影を生じる光であって、影の周辺部の外側に見られる。周辺照明光は、影の明るい側と暗い側の両方に存在する光であるが、暗い領域の方でより認知しやすい。
【００１７】
画像が２個の成分、すなわち物体および照明を含むという本発明の基本的所見に基づいて、コンピュータシステム１０は、例えば対象のエッジと、照明における入射照明光と周辺照明光との間の相互作用により生じるスペクトル・シフトの認識を介した照明光束のように、当該画像の有形態様を区別すべく動作することができる。画像において物体および照明の一方が既知である場合、もう一方を容易に推定することができる。入射照明光と周辺照明光のスペクトルは互いに異なっていてよい。影により生じたスペクトル・シフト、すなわち入射照明光の光度減少は、画像内で描かれたシーンに存在する異なる物体について実質的に不変である。本発明の特徴に従い、このスペクトル・シフト情報は、照明光強度比、すなわち入射照明光と周辺照明光の相互作用により形成されるスペクトル比の測定により検出される。スペクトル比は、画像内で描かれたシーンの２個の領域間における色または光度の違いに基づく比率であり、これは物体の差違、照明の変化、またはその両方により生じ得る。
【００１８】
本発明の基本的発見を実装する一般的なアルゴリズムとして、境界の両側からの画素値が、例えば赤、緑および青である長、中、短波長の３種の光度または色帯域においてサンプリングされる。境界の一方が、全ての色帯域において、もう一方の側より暗い場合、色光度シフトが可能な照明境界であると見なされる。他の色帯域が減少する間、いずれかの色帯域の光度が増加したならば、影は単に照明を遮るだけであるため、当該境界は有形物境界でなければならない。影で生じるような入射から周辺へのシフトは、色帯域を明るくすることとは同時に生起できない。モノクロまたはグレイスケール画像において、単一帯域の光度を用いることができる。
【００１９】
色光度シフトが識別された後で、シフトのスペクトル比が決定される。スペクトル比は多くの方法、例えば、Ｂ／Ｄ、Ｂ／（Ｂ−Ｄ）、およびＤ／（Ｂ−Ｄ）等、多くの方法により定義することができる。ここに、Ｂはシフトの明るい側の色であり、Ｄは暗い側の色である。スペクトル比を用いる照明境界の識別の視覚的正確さは、本願と同日出願された、本明細書に引用している同時係属出願第  号（代理人整理番号５９０．１００３）「画像操作のための２照明光２色性反射モデル（Ｂｉ−ｉｌｌｕｍｉｎａｎｔ  Ｄｉｃｈｒｏｍａｔｉｃ  Ｒｅｆｌｅｃｔｉｏｎ  Ｍｏｄｅｌ  Ｆｏｒ  Ｉｍａｇｅ  Ｍａｎｉｐｕｌａｔｉｏｎ，）」に開示されているように、画像の双照明光２色性反射モデルに基づく解析により決定される。
【００２０】
本発明の好適な実施形態において、比率Ｄ／（Ｂ−Ｄ）の正規化された値が、有形物の向きが様々に異なっていても不変であり、従って異なる向きにある対象の照明境界を越えて比率が一定であることが本発明の開発に際して見出されたため、スペクトル比Ｓ＝Ｄ／（Ｂ−Ｄ）を用いる。更に、完全に影で覆われたピクセルおよび半影ピクセルにより生じた比率Ｄ／（Ｂ−Ｄ）の正規化された値は、完全に影で覆われたピクセルおよび完全に照らされたピクセルにより生じた正規化された値に等しい。これらの関係は、Ｂ／ＤおよびＢ／（Ｂ−Ｄ）の正規化された値には現れない。従って、比率Ｄ／（Ｂ−Ｄ）は、精度および正確さの最適な組合せを提供する。
【００２１】
Ｂｒｅｄが入射またはシフトの明るい側のカラー測定の赤色チャネルであり、一方Ｄｒｅｄは暗い側の赤色チャネル値である。同様に、ＢｇｒｅｅｎおよびＢｂｌｕｅは各々、シフトの明るい側の緑およい青色チャネル光度を表わし、ＤｇｒｅｅｎおよびＤｂｌｕｅは暗い側の緑および青色光度を表わす。シフトのスペクトル比は従ってＮ次元のベクトル、本例では３次元ベクトルを含んでいる。
Ｖ  ＝（Ｄｒｅｄ／（Ｂｒｅｄ−Ｄｒｅｄ），Ｄｇｒｅｅｎ／（Ｂｇｒｅｅｎ−Ｄｇｒｅｅｎ），Ｄｂｌｕｅ／（Ｂｂｌｕｅ−Ｄｂｌｕｅ））
【００２２】
上述のように、本発明の特徴によれば、当該ベクトルは当該ベクトルをベクトル長のスカラー値で除算することにより正規化される。画像の特性スペクトル比または照明光強度比が決定される。入射照明光と周辺照明光との相互作用により照明境界が生じる故に、照明の変化に付随する画像全体にわたるスペクトル比は、明るい側の色または境界の有形物特徴とは無関係に、一貫してほぼ等しい筈である。このように、本解析におけるスペクトル比がシーンの特性スペクトル比にほぼ等しい場合、境界は照明境界として分類される。
【００２３】
画像の特性比の精度および正確さを向上させるべく、照明境界のスペクトル比情報が局所レベルで決定される。すなわち画像内で表現されるシーンの予め選択された数個の局所領域の各々について照明比率が決定される。次いで境界の解析が、画像内の境界の特定の位置のスペクトル比を利用して実行される。局所的に関連するスペクトル比の決定には、現実世界の画像において起こり得る複雑さ、例えば室内のいくつかの異なる光源による相互作用や相互反射等を包含している。
【００２４】
本発明の特徴によれば、画像の空間スペクトル特徴、すなわち照明光束を示す条件を含む特徴を識別すべく、画像の局所領域の動的サンプリングにより、局所スペクトル比がコンピュータシステム１０により自動的に決定される。空間スペクトル特徴の例として、Ｘ接合がある。Ｘ接合とは、有形エッジおよび照明境界が互いに交差する画像の領域である。Ｘ接合は、照明光強度比を正確に決定するために最適な位置である。
【００２５】
本発明の更なる特徴によれば、画像のトークン解析を用いて空間スペクトル特徴を識別する。トークンとは、領域のピクセルが空間スペクトル特徴の識別に関連するように互いに関係付けられた画像の連結領域である。トークンのピクセルは、例えばピクセルの色の密な相互関係等の均一要素、またはＲＧＢ空間等の色空間において幾何学的に関係付けられた異なる色値等の非均一要素のいずれかの観点から関連付けることができる。個々のピクセルではなくトークンを用いることにより、画像処理における複雑さやノイズが減り、コンピュータシステム１０にとってより効率的で負荷が軽減された計算動作を提供する。
【００２６】
本発明の例証的な実施形態において、一様トークン解析を用いて画像内のＸ接合を識別する。一様トークンとは、領域全体にわたりほぼ一定の画素値（例えば、記録装置の期待ノイズマージンまたは物体における通常の変動により決定される範囲内）を有する画像の連結領域を含んでいる均一なトークンである。１次の一様トークンは、画像の隣接ピクセルのうち単一の安定した色測定値を含んでいる。以下により詳しく述べるように、解析は画像の空間スペクトル特徴を表わすトークンの隣接関係の検査を含んでいてよい。
【００２７】
ここで図３Ａを参照するに、本発明の特徴による、図２の画像ファイル内の一様トークン領域を識別するフロー図を示す。識別ルーチンの開始時に、ＣＰＵ１２はメモリの領域マップを設定する。ステップ１００において、ＣＰＵ１２は領域マップをクリアして、領域ＩＤを割り当て、その初期値を１に設定する。ピクセル番号に対応するルーチンの反復回数ｉ＝０で設定され、トークンを決定するシード（seed）として用いるＮ×Ｎピクセル配列の番号の初期値としてＮ＝Ｎｓｔａｒｔが設定される。Ｎｓｔａｒｔは任意の整数＞０であってよく、例えば１１または１５ピクセルに設定することができる。
【００２８】
ステップ１０２において、シードテストが開始される。ＣＰＵ１２は、第１のピクセル、例えばｉ＝（１、１）、すなわち第１のＮ×Ｎサンプルの左上角のピクセルを選択する。当該ピクセルは次いで、選択されたピクセルが良好なシードの一部であるか否か決定すべく決定ブロック１０４においてテストされる。当該テストは、選択されたピクセルの色値を、シードとして自身の隣接ピクセルの予め選択された個数の色値、例えばＮ×Ｎ配列と比較することを含んでいてよい。比較の結果が当該シード内のピクセルにほぼ等しい値とならなかった場合、ＣＰＵ１２は次のＮ×Ｎシードサンプルについてｉの値を、例えばｉ＝（１、２）増やし（ステップ１０６）、次いでｉ＝ｉｍａｘであるか否かを判定する（決定ブロック１０８）。
【００２９】
画素値がｉｍａｘであり、結果を向上させるべくシードサイズを減らすことを決定するための閾値として選択された値、すなわちシードサイズＮが、例えばＮ＝１５からＮ＝１２まで減らされる（ステップ１１０）。本発明の例証的な実施形態において、ｉｍａｘをｉ＝（ｎ、ｍ）に設定することができる。このように、図３Ａのルーチンは、Ｎの減らされた値について当該ルーチン繰り返す前に、Ｎが第一の値であるときに画像全体を走査する。
【００３０】
シードサイズを減少させた後で、当該ルーチンはステップ１０２へ戻り、トークンシードに対するテストへ続ける。Ｎｓｔｏｐ値（例えばＮ＝２）もまた、解析が終了したか否か決定すべくステップ１１０で調べられる。Ｎの値がＮｓｔｏｐである場合、ＣＰＵ１２は画像ピクセル配列の調査を完了して、当該ルーチンを出る。
【００３１】
ｉの値がｉｍａｘより小さく、且つＮがＮｓｔｏｐより大きい場合、当該ルーチンはステップ１０２へ戻り、トークンシードに対するテストを続ける。
【００３２】
良好なシード（ほぼ等しい画素値を有するＮ×Ｎ配列）が見つかった（ブロック１０４）場合、トークンはシードから成長する。ステップ１１２において、ＣＰＵ１２はピクセルをシードから待ち行列へ入れる。待ち行列内の全てのピクセルに領域マップ内の現在の領域ＩＤがマーク付けされる。ＣＰＵ１２は次いで、待ち行列が空か否かを問い合わせる（決定ブロック１１４）。待ち行列が空でない場合、当該ルーチンはステップ１１６へ進む。
【００３３】
ステップ１１６において、ＣＰＵ１２は先頭ピクセルを待ち行列から取り出して、ステップ１１８へ進む。ステップ１１８において、ＣＰＵ１２は被写体ピクセル周辺の「良好な」隣接ピクセル、すなわち被写体ピクセルと色値がほぼ等しい隣接ピクセルに現在の領域ＩＤをマーク付けする。マーク付けされた全ての良好な隣接ピクセルが領域マップに配置され、また待ち行列列に入れられる。ＣＰＵは次いで、決定ブロック１１４へ戻る。待ち行列が空になるまで、ステップ１１４、１１６、１１８のルーチンが繰り返される。その時点で、現在の領域内のトークンを形成しているピクセルの全てが識別され、且つ領域マップにマーク付けがなされている。
【００３４】
待ち行列が空の場合、ＣＰＵはステップ１２０へ進む。ステップ１２０において、ＣＰＵは次のトークンの識別に用いるべく、領域ＩＤを増やす。ＣＰＵは次いで、ステップ１０６へ戻って、新規な現行トークン領域に関して当該ルーチンを繰り返す。
【００３５】
図３Ａのフロー図のステップ１１０でＮ＝Ｎｓｔｏｐ、または画像に一致する領域マップの完成に到達したならば、当該ルーチンはトークン生成作業を完了した。図３Ｂは、トークン識別の例として用いる原画像である。当該画像は、青色と影に入っている青色の領域、およびティール色と影に入っているティール色の領域を示す。図３Ｃは、図３Ａの画像内のトークン領域を示す。トークン領域には色コードが付与されていて、画像のフルカラー青色およびティール領域および彩色領域の影との間の半影領域を含む図３Ｂの画像のトークン構造を例示する。
【００３６】
その後ＣＰＵ１２は、画像内のＸ接合を識別すべく使用できるトークン・グラフを生成するルーチンを開始する。図４Ａを参照するに、本発明の特徴に従い、図３Ａに示すルーチンの実行により識別されたトークン領域からトークン領域グラフを生成するためのフロー図を示す。
【００３７】
当初、ＣＰＵ１２には、前のルーチンで識別されたトークンのリスト、およびトークン間の最大距離Ｄの値が与えられる（ステップ２００）。本発明の例証的な実施形態において、Ｄ＝２０ピクセルである。ステップ２０２において、ＣＰＵ１２は、全てのトークンの全ての周辺ピクセルを識別すべく、各トークンのピクセル情報を走査する。図４Ｂは、図３Ｂの画像のトークン周辺ピクセルを示す。ＣＰＵは次いで、ステップ２０４へ進む。
【００３８】
ステップ２０４において、ＣＰＵ１２はトークン・リストからトークン領域を選択し、当該ルーチンのために、現行トークンＡとして、選択されたトークンを識別する。トークンＡ内の各周辺ピクセルについて、ＣＰＵ１２は、トークンＡの周辺からの最大距離Ｄ以内にある他の全てのトークンの中で最も近い周辺ピクセルを検出する（ステップ２０６）。
【００３９】
ステップ２０８において、ＣＰＵ１２は、先のピクセルマッチングのステップ２０６で検出された全てのトークンＩＤを編集することによりトークンＡに隣接するトークンのリストを生成する。ステップ２１０において、ＣＰＵ１２は、トークンＡの隣接トークンのリストを保存して、決定ブロック２１２へ進む。決定ブロック２１２において、ＣＰＵ１２は、トークン・リストの終端に達したか否かを調べる。達していない場合、ＣＰＵ１２はステップ２０４に戻り、トークンＡをトークン・リストの次のトークンに設定して、次のトークンに対してステップ２０６〜２１２を繰り返す。ＣＰＵ１２がトークン・リストの終端に達した場合、ＣＰＵはステップ２１４へ進み、ここでＣＰＵ１２は画像のトークン・グラフを返す。図４Ｃに、図３Ｂの画像の一部のトークン続グラフを示す。
【００４０】
トークン・グラフが完成したならば、ＣＰＵ１２はトークン領域グラフを用いて画像内のＸ接合を識別すべく図５Ａのルーチンへ進む。トークン・リストの各トークンに対して、ＣＰＵ１２は、スペクトル比が照明と有形物境界の交差を示す領域を識別すべく隣接関係全体にわたって繰り返し実行する。
【００４１】
入力（ステップ３００）としてＣＰＵ１２は、図３Ａ、４Ａのルーチンの実行中にＣＰＵ１２が各々準備したトークン・リストＴおよびトークン・グラフＧを受信する。Ｔ（トークン・リスト）内の全てのトークンＴｊにわたる主ループの反復において、ＣＰＵ１２は以下に示すように隣接トークンにわたりサブループを繰り返し実行する。ステップ３０２において、ＣＰＵ１２はトークン・リストからトークンＡを選択し、Ｔｊ＝Ａ（現行トークン）、次いで、Ａについて全ての隣接トークン、Ｘ＝ＧＡを選択（トークン・グラフから）する。
【００４２】
現行トークンＡについてサブループの１回目の実行として、ＣＰＵ１２はステップ３０２で検出されたＸ内の全ての隣接トークンＸｊを走査する。ステップ３０４において、ＣＰＵ１２は次いで、Ｂ＝Ｘｊとして設定された各隣接トークンを考慮する。決定ブロック３０６において、ＣＰＵ１２は現行トークンの隣接トークンＢについて色Ａの全て色帯域＞色Ｂの全ての色帯域であるか否か、をテストする。色Ａが全ての色帯域において色Ｂより大きくない場合、ＣＰＵ１２はステップ３０４に戻ってＸ（Ａの隣接トークンＧＡ）から次の隣接トークンＢを選択する。
【００４３】
色Ａが色Ｂより大きい場合、ＣＰＵ１２はステップ３０８へ進み、Ｙ＝ＧＢとして設定されたトークン・グラフからＢの隣接トークンを選択する。ＣＰＵ１２は次いで、Ｙ内の全ての隣接トークンＹｋにわたりサブループの次の実行へ進む。ステップ３１０において、ＣＰＵ１２は次いで、Ｃ＝Ｙｋとして設定された各隣接トークンを考慮する。決定ブロック３１２において、ＣＰＵ１２はＡ＝Ｃであるか否かをテストする。ＡがＣに等しい場合、ＣＰＵ１２はステップ３１０に戻ってＹから次の隣接トークンＣ（Ｂの隣接トークンＧＢ）を選択する。
【００４４】
ＣがＡとは異なるトークンである場合、ＣＰＵはステップ３１４へ進んで、Ｚ＝Ｇｃとして設定されているＣの隣接トークンを選択する。ＣＰＵ１２は次いで、Ｚ内の全ての隣接トークンＺｌに対するサブループの最後の実行へ進む。ステップ３１６において、ＣＰＵ１２は次いで、Ｄ＝Ｚｌとして設定されている各隣接トークンを考慮する。決定ブロック３１８において、ＣＰＵは、ＤがＸに存在するか否か、またＤ！＝Ｂであるか否かをテストする。テスト結果がＮＯの場合、ＣＰＵ１２はステップ３１６へ戻り、Ｚ（Ｃの隣接トークンＧｃ）から次の隣接トークンＤを選択する。
【００４５】
ブロック３１８のテスト結果がＹＥＳ（はい）の場合、ＣＰＵ１２はステップ３２０へ進み、図５Ａのルーチンの反復において識別された隣接トークン集合｛Ａ、Ｂ、Ｃ、Ｄ｝がＸ接合基準を満たすか否かをテストする。図５Ｂに、図３Ｂの画像を隣接トークン集合｛Ａ、Ｂ、Ｃ、Ｄ｝と共に示す。反復実行の仮説は、トークン集合｛Ａ、Ｂ、Ｃ、Ｄ｝が特定の隣接関係、またはＸ接合を示す空間スペクトル条件を実現するというものであり、トークンＡおよびＢが物体１で構成され、ＡがＢの照らされたバージョンであり、トークンＤおよびＣが物体２で構成され、ＤがＣの照らされたバージョンである。当該仮説を検証すべく実行されるいくつかのテストがある。
【００４６】
図６Ａに、Ｘ接合テスト実行サブルーチン、すなわち図５のフロー図のステップ３２０のフロー図を示す。ステップ３２６において、隣接トークン集合｛Ａ、Ｂ、Ｃ、Ｄ｝は、ルーチンの開始点として設定されている。図からわかるように、図６Ｂの画像に示す仮説は、ＡとＢが同一物体１であり、ＤとＣが同一物体２であり（３２８）、且つＢとＣは影の中にある。
【００４７】
第１のテスト、すなわちステップ３３０において、ＣＰＵ１２は、各色帯域においてトークンＡのピクセル＞トークンＢおよびピクセル、且つトークンＤのピクセル＞トークンＣのピクセルであるか否かを判定する。色ＢおよびＣには、１より大きいスカラー値である係数ｆが乗算される。ステップ３３２において、ＡおよびＤトークンの明度測定値が最小閾値より明るいか否かが判定される。
【００４８】
次のテスト（ステップ３３４）は、各々の明部トークンＡおよびＤが色空間、例えばＲＧＢ空間において大幅に異なるか否かの判定を含んでいる。この点に関して、色空間距離（Ａ、Ｄ）＞閾値であるか否かに関する判定が行なわれる。
【００４９】
ステップ３３６において、ＣＰＵ１２は、ＡとＤの間の反射率がＢとＣの間の反射率にほぼ等しいか否かを判定する。比率の境界が定められたバージョンを用いることができる。すなわちＲ１＝（Ａ−Ｄ）／（Ａ＋Ｄ）、Ｒ２＝（Ｂ−Ｃ）／（Ｂ＋Ｃ）、但しＲ１＝Ｒ２である。ステップ３３８において、スペクトル比Ｓ１＝Ｂ／（Ａ−Ｂ）とＳ２＝Ｃ／（Ｄ−Ｃ）が比較されて、これらが互いに（所定の差の範囲内で）類似しているか否かを判定する。
【００５０】
ステップ３４０において、ＣＰＵ１２は、スペクトル比が合理的な照明の先験的なモデルに合致するか否かを判定する。制約に対するバリエーションとして、例えば、ＢおよびＣトークンの暗度測定値が、対応する明部測定値の割合より小さいことを必要とする場合が含まれていてよい。更に、ＣＰＵ１２は、飽和レベルについてステップ３３８で決定されたスペクトル比をテストすることができる。飽和は、飽和＝１（最小色帯域／最大色帯域）として定義される。飽和に関してスペクトル比に上界を定めることができる。例えば、飽和＞０．９であるスペクトル比はいかなる場合も不合理であると考えられる。上述の制約の全てが満たされていれば、Ｘ接合基準が満足されていると考えられる（ステップ３４２）。
【００５１】
トークン集合｛Ａ、Ｂ、Ｃ、Ｄ｝がステップ３２０のＸ接合テストに合格しない場合、ＣＰＵ１２は決定ブロック３２２においてステップ３１６へ戻ってＺ（Ｃの隣接トークンＧｃ）から次の隣接トークンＤを選択する。トークン集合｛Ａ、Ｂ、Ｃ、Ｄ｝が合格したならば、ＣＰＵ１２はステップ３２４へ進んでトークン集合｛Ａ、Ｂ、Ｃ、Ｄ｝に正当なＸ接合としてマーク付けする。ＣＰＵは次いで、ステップ３０２へ戻り、Ｘ接合解析のために、トークン・リストＴから次のトークン（集合｛Ａ、Ｂ、Ｃ、Ｄ｝とは別の）を選択する。
【００５２】
ここで図７を参照するに、本発明の特徴に従い、Ｘ接合を用いて局所スペクトル比を識別するフロー図を示す。ＣＰＵ１２には、ステップ４００において画像ファイル１８およびＸ接合パラメータが与えられる。ＣＰＵ１２は次いでステップ４０２へ進み、所与の画像全体にわたり、画像内のＸ接合を識別する図３〜５の処理の実行を行なう。
【００５３】
ステップ４０２の終了後、ＣＰＵはステップ４０４へ進み、各Ｘ接合内の各々の明部／暗部ピクセル対についてスペクトル比を計算し、結果をメモリアレイに保存する。ステップ４０６において、ＣＰＵは、スペクトル比の配列に対して平均シフト・アルゴリズムを実行する。平均シフト・アルゴリズムは、例えば、コマニシウ（Comaniciu）、Ｄ．、ミーア（Meer）、Ｐ．「平均シフト解析およびアプリケーション（Mean-shift analysis and applications）」、コンピュータビジョン、１９９９、第７回ＩＥＥＥ国際会議報告書、第２巻、１９９９年９月２０〜２７日、１１９７〜１２０３ページに記載されているアルゴリズムを含んでいてよい。平均シフト・アルゴリズムの実行の出力（ステップ４０８）は、当該画像の全体または特定の局所領域に対するスペクトル比である。ステップ４０６の実行には、当該画像全体にわたるスペクトル比の値の調査が含まれていてよい。
【００５４】
スペクトル比が、量＞閾値変動だけ変化した場合、照明境界を決定する際に用いたスペクトル比情報に対して局所的アプローチが実装される。すなわち、ＣＰＵ１２が、特定のＸ接合の近傍にある画像の領域の照明境界を決定する際に、当該特定Ｘ接合に対する平均シフト値がスペクトル比として用いられる。画像全体における全てのスペクトル比の変化が閾値変動より小さい場合、全ての照明境界の決定において用いたのと同じ平均シフトスペクトル比と共に大域的な方法を用いることができる。
【００５５】
ここで図８を参照するに、本発明の特徴に従い、比率マッチングを用いて物体と照明を識別するフロー図を示す。より具体的には、図８のルーチンは、照明境界を含んでいる照明光束を識別する。ステップ５００において、ＣＰＵ１２には、図７のルーチンの実行を通じて決定された画像についてスペクトル比情報、および画像の標準明度エッジ境界セグメント情報が与えられる。画像の各々の明度エッジ部分に対して、ＣＰＵ１２はステップ５０２において、ピクセルまたはトークン対を選択することによりエッジを走査し、各対は、エッジ部分の明るい側からのピクセルまたはトークン、およびエッジ部分の暗い側からのピクセルまたはトークンを含んでいる。
【００５６】
ステップ５０４において、ピクセルまたはトークンの各対について、ＣＰＵ１２はスペクトル比、Ｓ＝暗部／（明部−暗部）を計算して、Ｓ値を対応するエッジ部分に沿った全て対について累積する。ステップ５０６において、ＣＰＵ１２は、エッジ部分のＳ値の累積された集合が所与のスペクトル比情報に合致するか否かを判定する。上述のように、所与のスペクトル比情報は、画像の大域的な値またはエッジ部分が位置する画像の一部の局所的な値であり得る。スペクトル比が合致した場合、ＣＰＵ１２は当該エッジ部分に照明境界としてマーク付けする（ステップ５０８）。合致していない場合、ＣＰＵ１２は当該エッジに物体エッジとしてマーク付けする（ステップ５１０）。
【００５７】
ここで図９を参照するに、固定サイズのマスクを用いて画像のＸ接合を識別する代替的なルーチンのフロー図を示す。ＣＰＵ１２によりメモリ１６から画像ファイル１８にアクセスする（ステップ６００）。マスクは、画像の解析に用いるべくピクセルのＮ×Ｍ行列（ピクセルの正方すなわちＮ×Ｎ行列であってよい）として定義される（６０２）。マスクは、画像のある領域を覆って配置される。ステップ６０４において、ＣＰＵ１２はＸ接合内の位置を近似すべく、マスクの領域内から４個の色測定値を選択する。４個の点は、図６Ｂに示すように、集合｛Ａ、Ｂ、Ｃ、Ｄ｝として指定することができる。ステップ６０６において、集合｛Ａ、Ｂ、Ｃ、Ｄ｝は、図６Ａのフロー図のサブルーチンをテストするＸ接合を用いてＸ接合制約についてテストされる。
【００５８】
テスト・サブルーチンを実行した後で、ＣＰＵ１２は決定ブロック６０８へ進む。決定ブロックにおいて、ＣＰＵ１２は集合｛Ａ、Ｂ、Ｃ、Ｄ｝がＸ接合テストに合格したか否か判定する。判定結果がＹＥＳの場合、ＣＰＵ１２は集合｛Ａ、Ｂ、Ｃ、Ｄ｝の点間の中心ピクセルにＸ接合としてマーク付けを行ない（ステップ６１０）、ステップ６１２へ進む。判定結果がＮＯ（いいえ）の場合、ＣＰＵは直接ステップ６１２へ進む。
【００５９】
ステップ６１２において、ＣＰＵ１２はマスクを画像上の新たな位置へ移動させて、画像の新たな領域にわたり再びルーチンを開始すべく、ステップ６０４へ進む。ＣＰＵ１２は、画像全体がテストされるまでマスクを移動し続ける。ステップ６１４において、オプションの追加的ルーチンが提供される。画像内で、多くの異なるサイズの半影部が存在し得る。いくつかの影は非常に鮮明な半影部を有する一方、他のものはぼやけた半影部を投射する。ステップ６０４〜６１２のルーチンが例えば２０ピクセル×２０ピクセルのマスクを用いる場合、これはぼやけた半影部の幅より小さい場合がある。この状況に対処すべく、且つ画像内の全てのＸ接合を確実に識別すべく、ステップ６０４〜６１２のルーチンは、より大きなマスクを用いるか、異なる向きまたは形状のマスクを用いるか、あるいは同一サイズのマスクに対し画像のサイズを縮小して再実行することができる。
【００６０】
縮小した画像に対して同一サイズのマスクの適用する方法は、尺度空間解析として知られている。一般に、マスク・サイズを大きくするよりも、画像を縮小する方がより効率的であるため、尺度空間解析が好ましい。ステップ６１４において、画像が縮小され（部分サンプル）、例えば半分にされる。これは、ピクセルの各２ピクセル×２ピクセルのブロックを取り出し、当該ブロックの平均色値を計算して、当該画像の新たな縮小バージョンにおける単一ピクセルとすることにより行なわれる。その後、ステップ６０４〜６１２は減少する画像のために繰り返される。
【００６１】
図１０に、確率的サンプリングを用いて画像のＸ接合を識別するフロー図を示す。ＣＰＵ１２には、画像、当該画像の選択された領域、サンプリング方法、選択された領域に対するサンプリング・ルーチンＮの最大数、および反復回数ｉ＝０（ステップ７００）が与えられる。ステップ７０２において、ＣＰＵ１２はサンプリング方法を実行して、調査対象の画像の領域内から、色値｛Ａ、Ｂ、Ｃ、Ｄ｝の集合を選択する。ステップ７０４において、集合｛Ａ、Ｂ、Ｃ、Ｄ｝は図の６ａフロー図のサブルーチンをテストするＸ接合を用いてＸ接合制約についてテストされる。
【００６２】
テスト・サブルーチンを実行した後で、ＣＰＵ１２は決定ブロック７０６へ進む。決定ブロックにおいて、ＣＰＵ１２は集合｛Ａ、Ｂ、Ｃ、Ｄ｝がＸ接合テストに合格したか否か判定する。判定結果がＮＯの場合、ＣＰＵ１２は決定ブロック７０８へ進み、反復回数ｉがＮすなわち選択された領域において実行される最大反復回数より少ないか否かをテストする。判定結果がＮＯの場合、ＣＰＵ１２はステップ７１０へ進み、反復回数ｉを０に再設定して、当該画像の次に選択された領域について継続する。ＣＰＵ１２は次いで、ステップ７０２へ戻って新たな領域について当該ルーチンを繰り返す。
【００６３】
ｉ＜Ｎのテスト結果がＹＥＳの場合、ＣＰＵ１２はステップ７１２へ進み、同一サンプル領域についてｉの値を増やし、ステップ７０２へ戻って同一領域のサンプリングを繰り返す。Ｘ接合テストの結果がＹＥＳの場合（７０６）、ＣＰＵ１２はステップ７１４へ進み、領域の中心ピクセルにＸ接合としてマーク付けする。ＣＰＵ１２は次いで、上述のようにステップ７１０へ進む。ステップ７１６において、図９のステップ６１４の部分サンプルルーチンが実行されて、サイズが縮小された画像に対して確率的サンプリングを繰り返す。
【００６４】
本発明の別の特徴によれば、トークンの隣接関係を直接用いることにより画像の空間スペクトル特徴が決定される。Ｎ次トークンは、選択された色空間、例えばＲＧＢ、色相、または色度において測定された色が異なり、且つ画像内で互いに近傍にあるＮ個の１次トークンの集合である。例えば、画像内で互いに隣接する赤色１次トークンおよび青色１次トークンは、２次トークンを形成することができる。
【００６５】
図１１Ａに、Ｎ次トークンを生成する第１の方法のフロー図を示す。ＣＰＵ１２には、例えば図３Ａのルーチンの実行を通じて識別されたトークンのリスト、入力画像領域Ａおよび１０ピクセルに設定された最大距離Ｄｍａｘが与えられている（ステップ８００）。ステップ８０２において、ＣＰＵ１２は、画像領域Ａ内の各１次トークンについて、画像位置またはピクセルＸ＝ｐ（ｉ、ｊ）を選択し、次いでＮ個のトークンの全ての一意の集合、すなわち各位置ＸからＤｍａｘ以内にある異なる色の全てのトークンを検出する。ステップ８０４において、ＣＰＵ１２は、重複の有無を確認しつつ、ステップ８０２で検出されたＮ個のトークンの各集合をＮ次トークン集合に追加する。ステップ８０６において、ＣＰＵ１２は、画像部分のＮ次トークン集合を出力する。図１１ＡＢは、図１１Ａの方法を用いて生成されたＮ次トークンを示す画像である。
【００６６】
図ｌ１ｂに、Ｎ次トークンを生成する第２の方法のフロー図を示す。第２の方法において、ＣＰＵ１２は、例えば図４Ａのルーチンの実行を通じて作成されたトークン・グラフを用いる。ステップ８０８において、ＣＰＵ１２には、画像ファイル１８のトークン・リスト、対応するトークン・グラフ、および最大距離Ｄｍａｘが与えられる。ステップ８１０において、トークン・リスト内の各トークンＴｉについて、ＣＰＵ１２は、ＴｉからＤｍａｘ以内にあるトークンの全ての一意な集合をトークン・グラフから検出する、ステップ８１２において、ＣＰＵは、重複の有無を確認しつつ、ステップ８１０で検出されたＮ個のトークンの各集合をＮ次トークン集合に追加する。ステップ８１４において、ＣＰＵ１２は、当該画像領域のＮ次トークン集合を出力する。図１１ＢＢは、図１１Ｂの方法を用いて生成されたＮ次トークンを示す画像である。
【００６７】
本発明の更に別の特徴によれば、図１１Ａおよび１１Ｂの方法のうち一つの実行を通じて生成されたＮ次トークンを用いて、画像の局所スペクトル比を識別する。再び、空間スペクトル特徴を調べて、照明光束を表わす特性スペクトル比情報を確認する。この例では、空間スペクトル特徴は、Ｎ次トークンの隣接トークン間の反射率とスペクトル比の関係を含んでいる。これらの関係はＣＰＵ１２により調べられる。
【００６８】
図１２を参照するに、Ｎ次トークンを用いて局所スペクトル比を識別するフロー図を示す。ステップ９００において、画像ファイル１８のＮ次トークンの集合が最初にＣＰＵ１２に与えられる。ＣＰＵ１２は、Ｎ次トークン内の一様トークンを、例えば単一の色チャネルの明度の順に配置する（ステップ９０２）。図１２に示すように、ステップ９０２に隣接して、Ｎ次トークンＡおよびＮ次トークンＢの各々の中でトークンのサンプル順序を示す。Ｎ次トークンＡは順序付けられたトークンＡ１，Ａ２，．．ＡＮを含み、Ｎ次トークンＢは順序付けられたトークンＢ１，Ｂ２，．．ＢＮを含んでいる。本発明の特徴によれば、ＣＰＵ１２は各々のＮ次トークンに対して、反射率およびスペクトル比が合致する他の全てのＮ次トークンを検出すべく動作する（ステップ９０４）。
【００６９】
ステップ９０４（図１２）に隣接して、トークン対Ａ、Ｂの反射率およびスペクトル比を比較するアルゴリズムは示す。Ｎ次トークンＡ内の各トークン対Ａｉ、Ａｊ、およびＮ次トークンＢ内の対応するトークン対Ｂｉ、Ｂｊについて、ＣＰＵ１２はこれらの対の反射率とスペクトル比との等価関係を判定する。反射率は、比率の境界を定められたバージョン、すなわちＲ（Ａｉ、Ａｊ）＝（Ａｉ−Ａｊ）／（Ａｉ＋Ａｊ）、およびＲ（Ｂｉ、Ｂｊ）＝（Ｂｉ−Ｂｊ）／（Ｂｉ＋Ｂｊ）を用いて、Ｒ（Ａｉ、Ａｊ）＝Ｒ（Ｂｉ、Ｂｊ）であるか否かを判定することにより決定できる。同様に、スペクトル比は、スペクトル比の好適な形式、すなわちＳ（Ａｉ、Ｂｉ）＝（（Ａｉ、Ｂｉ）の暗い方／（Ａｉ、Ｂｉ）の明るい方−（Ａｉ、Ｂｉ）の暗い方））、およびＳ（Ａｊ、Ｂｊ）＝（（Ａｊ、Ｂｊ）の暗い方）／（Ａｊ、Ｂｊ）の明るい方−（Ａｊ、Ｂｊ）の暗い方））を用いて、Ｓ（Ａｉ、Ｂｉ）＝Ｓ（Ａｊ、Ｂｊ）であるか否かを判定することにより計算することができる。この解析および関係判定では、Ｎ次トークンの一方が影の中にあって、Ｎ次トークンの他方が照られているものと仮定する。
【００７０】
ステップ９０６においてＣＰＵ１２は、合致する、すなわちステップ９０４において等価を示すＮ次トークンの対からの全てのスペクトル比を累積して、それらを配列にリストする。ＣＰＵは次いで、累積されたスペクトル比の配列に対して平均シフト・アルゴリズムを実行（ステップ９０８）し、その結果を局所領域の特性スペクトル比または画像全体として出力する（ステップ９１０）。
【００７１】
特性スペクトル比は、上述の方法のうち一つ以上を用いて決定されることができる。例えば、Ｘ接合およびＮ次トークンの各々を解析して局所スペクトル比を決定することができる。累積された比率は、信頼性の経験則に基づき重み付けされ、平均シフト・アルゴリズムにより処理されて特性スペクトル比を抽出することができる。
【００７２】
ここで図１３を参照するに、本発明の特徴によるトークン領域マップ上のＸ接合を識別すべく追加的ルーチンのフロー図を示す。ステップ１０００において、ＣＰＵ１２には、例えば、図４Ａのルーチンの実行を通じて生成されたトークン領域マップ、およびＮ×Ｍマスク、例えば２０ピクセル×２０ピクセルマスクが与えられる。ステップ１００２において、ＣＰＵ１２はマスクをトークン領域マップ上で移動させる。
【００７３】
各々のマスク位置について、ＣＰＵ１２は、シード容積Ｋ、例えば３ピクセルを以ってトークンをフィルタリングにより除去しながら、マスク内で全てのトークンのリストを計算する（ステップ１００４）。ＣＰＵ１２は次いで、トークン領域マップで示すように、トークンのリストから、４個の合理的な隣接トークン｛Ａ、Ｂ、Ｃ、Ｄ｝の各集合を選択する（ステップ１００６）。集合｛Ａ、Ｂ、Ｃ、Ｄ｝の合理性は、集合内の各トークンの明度を測定することによりＣＰＵ１２で判定されて、トークンの１個が明るい領域となるのに十分明るいか否か（予め選択された明度のレベルに基づいて）決定する。当該トークンは次いで、ラベルＡが付けられる。次いで、Ａ以外の集合のトークンが測定されて、残りのトークンのいずれかが全ての色帯域においてＡより暗いかか否が判定される。そのようなトークンはＢとラベル付けされる。その後で、ＣＰＵ１２は、所定のレベルの明度より明るく、且つＡとは異なる色を有する残りのトークンを測定する。当該トークンはＤとラベル付けされる。次いで、残りのトークンが全ての色帯域においてＤより暗いか否かが判定される。判定結果がＹＥＳならば残りのトークンはＣとラベル付けされる。
【００７４】
例えば図６Ａのルーチン等のテストがＣＰＵ１２により実行されて、集合｛Ａ、Ｂ、Ｃ、Ｄ｝がＸ接合であるか否が判定される。ステップ１００８において、ＣＰＵ１２は、各マスク位置について、ステップ１００４〜１００６の実行を通じて識別されたＸ接合のリストを出力する。
【００７５】
以上述べた明細書において、本発明を特定の例証的な実施形態および実施例に関して記述してきた。しかし、添付の請求項に開示している本発明の主旨と範囲から逸脱することなく、各種の修正や変更がなされ得る点が明らかである。明細書および図面は従って、限定的な意味ではなく、説明目的であると理解されたい。
【図面の簡単な説明】
【００７６】
【図１】画像関連の動作を実行すべく構成および設定されたコンピュータシステムのブロック図である。
【図２】図１のコンピュータシステムに保存された画像のｎ×ｍピクセル配列画像ファイルを示す。
【図３Ａ】本発明の特徴による、図２の画像ファイルのトークン領域を識別するフロー図である。
【図３Ｂ】トークンの識別の例として用いる原画像である。
【図３Ｃ】図３Ａの画像内のトークン領域を示す。
【図４Ａ】本発明の特徴に従い、図３Ａで識別されたトークン領域からトークン領域グラフを生成するフロー図である。
【図４Ｂ】図３Ｂの画像のトークン周辺部を示す。
【図４Ｃ】図３Ｂの画像のトークン続グラフを示す。
【図５Ａ】本発明の特徴に従い、図４Ａのトークン領域グラフを用いて画像のＸ接合を識別するフロー図である。
【図５Ｂ】図３Ｂの画像内のＸ接合を示す。
【図６Ａ】図５のフロー図のサブルーチンをテストするＸ接合のフロー図である。
【図６Ｂ】Ｘ接合を有する画像を示す。
【図７】本発明の特徴に従い、図５のＸ接合を用いる局所スペクトル比を識別するフロー図である。
【図８】本発明の特徴に従い、比率のマッチングを用いて物体および照明エッジを識別するフロー図である。
【図９】大きさが固定されたマスクを用いて画像内のＸ接合を識別するフロー図である。
【図１０】確率的サンプリングを用いて画像のＸ接合を識別するフロー図である。
【図１１Ａ】Ｎ次トークンを生成する第１の方法のフロー図である。
【図１１ＡＢ】図１１Ａの方法を用いて生成された第ｎ次トークンを示す画像である。
【図１１Ｂ】第ｎ次トークンを生成する第２の方法のフロー図である。
【図１１ＢＢ】図１１Ｂの方法を用いて生成された第ｎ次トークンを示す画像である。
【図１２】図ｌｌＡおよび１１Ｂの方法のうち一方を用いて生成された第ｎ次トークンを用いて局所スペクトル比を識別するフロー図である。
【図１３】本発明の特徴に従い、トークン領域マップ上のＸ接合を識別する追加的なルーチンのフロー図である。
【図１】
2008529169.tif 000003
【図２】
2008529169.tif 000004
【図３Ａ】
2008529169.tif 000005
【図３Ｂ】
2008529169.tif 000006
【図３Ｃ】
2008529169.tif 000007
【図４Ａ】
2008529169.tif 000008
【図４Ｂ】
2008529169.tif 000009
【図４Ｃ】
2008529169.tif 000010
【図５Ａ】
2008529169.tif 000011
【図５Ｂ】
2008529169.tif 000012
【図６Ａ】
2008529169.tif 000013
【図６Ｂ】
2008529169.tif 000014
【図７】
2008529169.tif 000015
【図８】
2008529169.tif 000016
【図９】
2008529169.tif 000017
【図１０】
2008529169.tif 000018
【図１１Ａ】
2008529169.tif 000019
【図１１ＡＢ】
2008529169.tif 000020
【図１１Ｂ】
2008529169.tif 000021
【図１１ＢＢ】
2008529169.tif 000022
【図１２】
2008529169.tif 000023
【図１３】
2008529169.tif 000024
【国際調査報告】
2008529169.tif 000025
2008529169.tif 000026