(57)【要約】  予め定められた順序によって各々のデータ要素を処理して、データ要素の格子を有している画像のパターンを検出する方法を開示する。  データ要素に、予め定められた局所的特徴が存在するか否かがチェック（１００）され、存在する場合には、この局所的特徴に関する情報が生成される。  伝播方向（４２）は、生成された情報と関連している。伝播方向に沿ったデータ要素がまだ処理しなければならない場合に、その伝播方向が選択される。  生成された情報は、それぞれの情報と関連しているそれぞれの伝播方向に沿って、そのデータ要素に最も近いそれぞれのデータ要素に伝播される（１１０）。  予め定められたパターンが存在するかどうかがチェックされる（１０４）。予め定められたパターンには、画像の各場所における局所的特徴のデータ要素に伝播した情報に基づく複数の特徴（３２）を含む。そして、そのパターンが発見された場合には、パターンに関する情報が出力される（１０８）。
2009540416.tif 000002
【特許請求の範囲】
【請求項１】
データ要素の格子を有している画像のパターンを検出する方法であって、予め定められた順序で各々のデータ要素を処理するステップを有し、かつ前記データ要素のうちの１つを処理するときに：
前記データ要素におけるあらかじめ定められた局所的特徴の存在をチェックするステップ、および前記局所的特徴が存在する場合に前記局所的特徴に関する情報を生成するステップ、および伝播方向を前記生成された情報と結びつけるステップであって、前記伝播方向に沿ったデータ要素がまだ処理されなければならないように、前記伝播方向が選択されるところの結びつけるステップ；
前記それぞれの情報に関連する前記それぞれの伝播方向に沿って前記データ要素に最も近いそれぞれのデータ要素に、前記生成された情報および前記データ要素に伝播した前記情報を伝播するステップ；および
前記画像のいずれかの場所で確証した局所的特徴に関する前記データ要素に伝播された情報に基づき、複数の特徴を含む予め定められたパターンの存在をチェックするステップ；および
パターンが見つかった場合に、前記パターンに関する情報を出力するステップ；
を有する方法。
【請求項２】
前記データ要素を処理することの前記予め定められた順序は、格子線の全てのデータ要素が処理されてから次の隣接した格子線のデータ要素の処理へ進むようになされる、
請求項１に記載の方法。
【請求項３】
前記予め定められた順序に従って並列に複数のそれぞれのデータ要素を処理するための複数の処理要素を使用するステップを更に有する方法であって、かつ
前記情報を伝播するステップは、前記情報が伝播される前記それぞれのデータ要素を予定に従って処理する前記処理要素が利用できる前記情報を作るステップを有する、
請求項１に記載の方法。
【請求項４】
前記データ要素を処理する前記予め定められた順序は、
予定に従って並列に処理される複数のデータ要素が単一の格子線の一部分で、かつ全ての前記格子線のデータ要素が処理されてから、次の隣接した格子線のデータ要素の処理へ進む、
請求項３に記載の方法。
【請求項５】
前記パターンの存在をチェックするステップは、前記生成された情報に基づいて同様に実行される、
請求項１に記載の方法。
【請求項６】
前記処理要素は、単一命令多重データタイプのプロセッサの処理要素である、
請求項３に記載の方法。
【請求項７】
前記パターンは、定義済タイプのオブジェクトに対応する、
請求項１に記載の方法。
【請求項８】
前記情報を伝播するステップは、前記情報が伝播する前記それぞれのデータ要素を予定に従って処理する前記処理要素がアクセスできるメモリに前記情報を保存するステップを有する、
請求項３に記載の方法。
【請求項９】
前記パターンが存在する場合に前記パターンに関する情報を生成するステップ、および前記局所的特徴が存在する場合に前記局所的特徴に関する情報を生成するステップ、および伝播方向を前記生成された情報と結びつけるステップであって、前記伝播方向に沿ったデータ要素がまだ処理されなければならないように、前記伝播方向が選択されるところの結びつけるステップを更に有する方法であって、かつ
前記パターンの存在をチェックするステップは、同様に、前記画像のいずれかの場所で確証したパターンに関する前記データ要素に伝播される前記情報に基づく、
請求項１に記載の方法。
【請求項１０】
前記生成された情報および前記データ要素に伝播された前記情報は、予め定められた扇角度の範囲内で前記画像に沿って全方向に伝播する、
請求項１に記載の方法。
【請求項１１】
前記伝播方向は、前記画像の軸のうちの少なくとも１本と４５度または０度の角度を含む、
請求項１に記載の方法。
【請求項１２】
前記局所的特徴は、少なくとも以下の一つに関する請求項１に記載の方法：
前記画像のエッジまたは勾配；
前記画像の点；
前記画像の局所エントロピー；
前記画像の局所的な色。
【請求項１３】
情報が生成された第１の局所的特徴と関連する第１の伝播方向と、情報が生成された第２の特徴と関連する第２の伝播方向との交点の存在を確証するステップであって、前記交点が前記画像の前記境界の外に位置するところのステップ；および
前記第１の局所的特徴に関する前記情報および前記第２の局所的特徴に関する前記情報および前記パターンが見つかった場合に前記パターンに関して出力される情報に基づき、複数の特徴を含むパターンの存在をチェックするステップ；
を更に有する請求項１に記載の方法。
【請求項１４】
データ要素の格子を有している画像のパターンを検出するシステムであって、請求項１に記載の方法に従って、予め定められた順序でデータ要素を処理するための少なくとも一つの処理要素を有するシステム。
【請求項１５】
前記予め定められた順序に従って並列に複数のそれぞれのデータ要素を処理するための複数の前記処理要素；および
予定に従って前記情報が伝播される前記それぞれのデータ要素を予定に従って処理する前記処理要素が利用できる前記情報を作るための手段；
を有する請求項１４に記載のシステム。
【請求項１６】
プロセッサが請求項１に記載の方法を実行することを可能にするためのコンピュータ命令を有するコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ要素の格子を有している画像のパターンを検出する方法に関する。本発明は、システムに、そして、コンピュータプログラム製品に関する。
【背景技術】
【０００２】
例えば、画像の対象物およびパターン認識は、ロボティックビジョンにおいて重要である。結果がリアルタイムで必要な場合であって、計算資源が制限される場合には特に、パターン認識タスクの計算の複雑性のため、並行処理が望ましい。ピクセルごとのタスクにおける低消費電力と共に比較的高いパフォーマンスを提供する（単一命令多重データ）ＳＩＭＤプロセッサが画像処理のために用いられてもよい。いくつかのビデオ改良技術は、これらの機械によってうまく実装された。しかし、異なった大きさを持つ、たとえば変形可能なオブジェクトのための画像解析を実行するには、ローカル、ラインベースの画像に対するリニアなＳＩＭＤは利用が難しい。
【０００３】
特許文献１には、オブジェクトおよびオブジェクトモデルのイメージの類似性の程度を示している特徴値を算出するための画像認識アルゴリズムが記載されている。算出は、階層的な並列処理によって実行される。この方法は、能率的に予め定められたカテゴリおよびサイズのパターンを検出するために、またはさまざまなサイズのために、小規模の回路を使用して認識を実行することができるパターン認識処理を提供している。装置は、時系列的な入力パターンでもって複数回データを入力するための時分割データ入力手段、位置入力手段および特徴抽出を有している。この特許出願は、異なるスキャニング位置で検出される複数の特徴を統合して、その統合結果を基礎として、特定パターンの存在の可能性を決定することを有する方法を開示している。
【０００４】
特許文献２は、ニューラルネットワーク等の並行オペレーションによって、パターン認識、指定されたオブジェクトの検出その他を実行するパターン認識装置の回路構成を開示している。従来は、画像認識または音声認識の方法は、時系列的な実行によって特定のオブジェクトをコンピュータソフトウェアによって認識プロセスアルゴリズムを実行するもの、および排他的な並列画像処理プロセッサ（ＳＩＭＤ、ＭＩＭＤ機械その他）によってこの種のタイプのアルゴリズムを実行し認識する、２つのタイプに分けられる。例えば、物体認識装置については、この種のプロセッサユニットで提供されるＤＳＰによって処理を実行するために、複数のイメージ・プロセッサー・ユニットが使用されることは公知である。この特許出願は、以下の事項を開示している。入力信号に含まれる所定パターンを検出するパターン認識装置において、同じ入力のためのそれぞれ別の特徴を検出するための複数の検出処理手段；各々の処理結果のために、前記複数の検出処理手段によって検出した特徴を空間的に統合する複数の統合処理手段；前記検出処理手段の処理結果を保持するための複数の検出メモリ；前記統合処理手段の処理結果を保持するための複数の統合メモリ；全ての前記予め定められた検出処理手段および全ての前記予め定められた統合メモリが特定のタイミングで連結される共通データライン；および予め定められた前記検出処理手段、前記統合処理手段および前記検出メモリの集合を各々に連結する複数の局所データライン；を有し、前記検出メモリにおいて保持されている前記検出処理手段の処理結果を前記統合処理手段に入力する際、前記複数の検出メモリの同じアドレスのデータは、読み込まれて、前記統合処理手段に入力され；かつ前記統合メモリにおいて保持されている前記統合処理手段の処理結果を前記検出処理手段に入力する際、前記複数の検出メモリの同じアドレスのデータは、読み込まれて、前記検出処理手段に入力されるパターン認識装置が開示されている。
【０００５】
従来技術で開示されるシステムは、比較的複雑である。従来技術は、複数回のデータ入力とデータ処理を必要とする。ニューラルネットワークは計算機として高価で、広範な訓練手順を必要とする。そして、開発に労力を要する。
【０００６】
【特許文献１】米国特許出願公開第２００２／０１８１７７５号明細書
【特許文献２】米国特許出願公開第２００２／０１８１７６５号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、より複雑でなく信頼性が高い物体認識を提供することである。本発明は、独立クレームによって定義される。従属クレームは、有利な実施例を定める。方法は、多数の特徴を持つパターンに対して、効率的なワンパスパターン認識用アルゴリズムを提供する。特徴に関する情報は画像に沿って所定の関連した方向に伝播される。このようにして、伝播の方向に沿ってデータ要素を処理するときに、この情報が処理要素に利用される。シングルパスによるデータ処理ではあるが、処理要素が、特徴に関する情報を他の情報と結合して、パターンに関する情報を決定することができる。
【課題を解決するための手段】
【０００８】
２つ以上の特徴は、異なる方向へ伝播される。第一および第二の両方の特徴に関する情報が処理要素で利用できるようになる。この２つの伝播方向が交差する所でデータ要素を処理する。複数の特徴を有しているオブジェクトは、このようにそれぞれの伝播方向の交点で検出されてもよい。伝播する特徴が交点で交わる確率を増やすために、第１のおよび／または第２の特徴は同様に二つ以上の方向または、扇角度の範囲内で全方向に伝播してもよい。
【０００９】
パターンの存在をチェックするステップの場合には、伝播された情報を局所的特徴に関する情報と結合することも同様に可能である。
【００１０】
実施例においては、データ要素を処理する際の予め定められた順序は、格子線の全てのデータ要素が処理された後に、次の隣接した格子線のデータ要素の処理へ進むようにする。データ要素を処理するこの順序を用いると、伝播方向に沿ったデータ要素の処理が残っていても、伝播方向を見つけることが非常に容易になる。
【００１１】
実施例は、複数のそれぞれのデータ要素を、平行して予め定められた順序で処理するための複数の処理要素を使用するステップであって、情報を伝播するステップは、それぞれの情報が伝播されるデータ要素を予定に従って処理するために処理要素が利用できる情報を作るステップを含んでいる。本発明は、並列処理アーキテクチャで効果的に使われてもよい。
【００１２】
実施例においては、平行的に処理される予定の複数のデータ要素は、単一の格子線の要素であり、その格子線の全てのデータ要素が処理された後、次の隣接した格子線のデータ要素の処理に進むよう、予め定められた順序でデータ要素が処理される。例えば、データ要素は処理される一つの格子線のうちの少なくとも１つに対して垂直に分離された細長い片に分けられる。そして、各々の処理要素は、それぞれの一片のデータ要素を処理するために配置される。格子線は、画像の一方から始めて画像の反対側の方へ、一列ずつに処理されてもよい。伝播方向は、まだ処理しておらず、これから処理を必要とするデータ要素の方へ向かう。
【００１３】
一連のプロセッサが画像の別の列を各々処理することは、本発明にとって効率的である。完全に別の一連のプロセッサであれば、１つのステップで画像の中の直線全体を処理してもよい。次の段階において、次の行が処理される。第１の処理要素からその隣接した処理要素（画像の中の隣の列）まで情報を伝播することによって、隣の列の処理要素において、および、次の行に存在するデータ要素を処理するときに、その隣接した処理要素は、その見つかった特徴に関する情報を考慮してもよい。
【００１４】
実施例において、パターンの存在確認のステップは、生成された情報に基づいて同様に実行される。このステップでは、現在処理しているデータ要素で見つかる特徴と、画像のどこか他の所における伝播した特徴の情報とを結合することができる。実施例において、処理要素は、単一命令多重データ（ＳＩＭＤ）タイプのプロセッサである。この種のプロセッサは、特に上述したデータ処理に適している。
【００１５】
実施例において、パターンは、定義済タイプのオブジェクトに対応する。
【００１６】
オブジェクトは、オブジェクトと関連している多くの異なった特徴を検出することによって認識されてもよい。特徴は、一緒に画像のパターンを形成する。特徴およびそれらの相対的位置は、オブジェクトを特定するために用いてもよい。特徴に関する情報は、同様に特徴に係るそれぞれの画像中の位置に関する情報を含むことも好適である。これにより、より正確に特徴の相対的位置を決定することが可能となる。
【００１７】
実施例においては、情報を伝播するステップは、情報が伝播するそれぞれのデータ要素を予定に基づいて処理する処理要素がアクセスできるメモリ内の情報を保存するステップを有する。これは、パラレル計算を使用した本発明による方法を実現する上で特に効率的な手法である。
【００１８】
他の実施例は、パターンに関する情報が存在する場合、これを生成するステップ、および伝播方向を生成された情報と結びつけるステップを有する方法であって、伝播方向に沿ったデータ要素がまだ処理しなければならない場合に、伝播方向が選択され、パターンの存在のためのチェックのステップは、画像の他で決められるパターンについてデータ要素に伝播される情報に基づく方法である。この実施例は、それぞれの伝播方向の交点とは別の場所におけるいくつかの特徴の情報を使用することを可能にする。交点に達した後、複合された情報が更に伝播してゆく。その結果、情報は画像の他の場所で検出された特徴と結合されてもよい。
【００１９】
ある実施例において、生成された情報およびデータ要素に伝播される情報は、予め定められた扇角度の範囲内で画像に沿って全方向に伝播される。このことはパターンが発見できる確率を増やす。なぜなら、特徴に関する情報が、より多くのデータ要素で利用できるようになるからである。
【００２０】
また、実施例において、伝播方向は、画像の軸のうちの少なくとも１本と４５度または０度の角度を有する。この実施例は、正方形のピクセルまたは立方体ボクセルの場合、特に接続された処理要素が、隣接しているデータ要素の片を処理する場合に比較的効率的である。データ要素が処理されるたびに、決定された特徴および伝播によって得られた特徴は隣接したデータ要素および／または隣接した処理要素に伝播される。
【００２１】
実施例において、局所的特徴は、エッジまたは画像の勾配、画像の点、画像の局所エントロピー、および画像の局所的な色のうちの少なくとも１つに関する。これらの特徴のいくつかは、オブジェクトに共通にみられる。上述したように、オブジェクトはこの種の特徴のいくつかを結合することによって確実に検出され得る。他のタイプの特徴が、同様に本発明で用いられてもよい。
【００２２】
実施例は、情報が生成された第１の局所的特徴と関連する第１の伝播方向と、情報が生成された第２の特徴と関連する第２の伝播方向との交点の存在を確証するステップであって、交点は画像の境界の外に設置されるところのステップ；および第１の局所的特徴に関する情報および第２の局所的特徴に関する情報およびパターンが発見できればパターンに関して出力される情報に基づき、複数の特徴を含むパターンの存在をチェックするステップを有する。伝播線の交点が画像の外にある場合であっても、この実施例によってパターンを検出することができる。
【００２３】
これらの、そしてまた他の本発明の態様は図面に基づいて説明される。
【発明を実施するための最良の形態】
【００２４】
ＳＩＭＤプロセッサは、画像処理の用途に非常に有利である。なぜなら、ＳＩＭＤは、高性能および低い電源消費をピクセル毎のタスクに対して提供できるからである。ピクセル処理は、通常並列的処理であって、したがって、Ｘｅｔａｌのような単純なＳＩＭＤマシンの利用に合致する。いくつかのビデオの改良技術では、これらのマシンの実装が適切になされている。しかし、異なる大きさを有する画像処理を行うためには、おそらく変形可能なオブジェクトへの利用は難しい。なぜなら、リニアなＳＩＭＤは、局所用であり、線ベースであるためである。リニアなＳＩＭＤマシン、または、リニアプロセッサアレイ（ＬＰＡ）は、ハードウェアにおいて有利である。なぜなら、これらは容易に直列につなげることができ、プロセッサは、レイアウトや書込の問題なしに、広いメモリを使うことができるからである。画像解析において、自然界のオブジェクトは、オブジェクトの中と外の特徴を特定することによってしばしば認識される。なぜなら、オブジェクトが、変形可能で、大きさにおいて異なることがあるからである。特徴の相対位置およびそれらの存在は、完全なオブジェクトを認識するために用いてもよい。
【００２５】
簡単な実例は、ジェスチャ認識のための手の検出である。この場合に、例えば、以下の特徴が使われる：
１．  皮膚の色
２．  輝度：暗い手は低輝度レベルを有し、白い手は高輝度レベルを有する。
３．  エッジ：指の回りに、比較的高い数のエッジが、画像の比較的小さい領域に現れる。
４．  動き：ジェスチャのために、手は横へ移動する。
【００２６】
これらの特徴は、単純なフィルタ技術によって画像中で抽出してもよい。これらの特徴の１つだけでは、手を特定するのに十分でない。しかし、重み付けした組合せは非常に強力で認識力がある。それぞれの特徴の相対的な位置は、把握できるが、絶対位置は変形可能なオブジェクトのサイズ差のために把握できない。ＬＰＡ−ＳＩＭＤプロセッサでは、限られた範囲の画像が処理できるだけで（例えば１列、２列、は処理できるが、３列、４列は処理できず）、２〜３のラインしか記憶できない。これは、キャッシュメモリの制限のためである。画像データからのレスポンスのデータが、いずれかと結びつくということを、ブロードキャストすることによって、全ての特徴が十分な確実性をもって把握できる特定の点が画像において存在する。実施例において、特徴をブロードキャストすることは、画像を走査する方向に実行されてもよい。画像の１つの領域で、全ての検出された特徴メッセージが一緒に到来し、そして、積極的な識別がなされてもよい。
【００２７】
本発明の実施例を実現するために非常に適しているアーキテクチュアは、Ｘｅｔａｌ  ＬＰＡ−ＳＩＭＤである。図２にアーキテクチュアを図式的に示す。これには、ラインメモリ２６およびコントローラ２８が含まれる。処理配列２０は、コントローラ２８の制御で命令を実行する処理要素ＰＥ０、ＰＥ１、．．．ＰＥｎを有する。ラインメモリの情報は、周辺機器、例えばコントローラ２８の制御下の画像データを含んでいるメインメモリと交信される。ラインメモリは、データ要素（例えば画素（ピクセル）または体積要素（ボクセル））を含む。接続２１によって、ラインメモリ２６の各々のデータ要素は、それぞれの処理要素２４に連結される。処理要素は、同様に交差接続２２によって隣接したデータ要素にアクセスする。プロセッサアレイ２０（ＰＥ０．．．ＰＥｎ）は、特徴（上記の実例の項番１〜４）の必要な集合の検出のために必要な全ての単純なフィルタリングをすることができる。交差接続２２を有することによって、隣接した要素に連結し、４５度および０度のデータブロードキャストが非常に能率的に実行されてもよい。接続２１および交差接続２２は、各々の処理要素２４が左、右または直上のラインメモリ２４の記憶素子から情報を得るために、マルチプレクサによって実現される。
【００２８】
各々の処理要素２４は、ブール演算子ＯＲを持つ。ＯＲ素子は、以前に検出されている特徴を示すためにブロードキャストされたメモリ内容を対応するビットプレーンにセットする。これは、例えばフレームの開始時にまたはオブジェクトが検出された後に、ブロードキャストされた信号をクリアするために、操作命令ＣＬＥＡＲを有する。この融合したフィルタリング、下方へのブロードキャストおよびＬＰＡ−ＳＩＭＤの組合せは、低コストの物体認識を実現する。
【００２９】
別の実施例は、図１において図式的に表されるように、ハードウェアテンプレートとして直線形状（ＬＰＡ）に接続されたＳＩＭＤプロセッサである。処理要素１２（ＰＥ０〜ＰＥｎ）は、コントローラ（図示せず）の制御下で命令を実行する。処理要素１２は、入力１０を経てデータ要素を受信して、出力１４に対して検出された特徴に関する情報を書き込む。情報は、接続１６を使用して隣接した処理要素の間で交換される。
【００３０】
画像の各々の処理要素（またはプロセッサ）は、一つ以上の列を処理する。各々のプロセッサが２列以上を処理する場合、それらは好ましくは、インターリーブ形式で処理される。行の全てのデータ要素を処理してから、次の行へ進む。したがって、画像の行はトップダウンスキャンで処理される。各々の（ＳＩＭＤ）命令は、画像の一列全部を処理する。このハードウェアは、画像（例えば色、エッジ）の特徴を検出するために、容易に全ての種類の畳み込みフィルタを実現する。更に、垂直に下って次の処理状態にもブロードキャストする：
ｉｆ（ｆｉｌｔｅｒ“Ｘ”ｒｅｓｐｏｎｄｅｄ）ｔｈｅｎ
ｓｔａｔｅ（０）＝ｓｔａｔｅ（０）ＯＲ“Ｘ”；
ｅｌｓｅ
ｓｔａｔｅ（０）＝ｓｔａｔｅ（０）；
ｅｎｄｉｆ；
または、４５度左（−１）または右（＋１）：
ｉｆ（ｆｉｌｔｅｒ“Ｙ”ｒｅｓｐｏｎｄｅｄ）ｔｈｅｎ
ｓｔａｔｅ（＋／−１）＝ｓｔａｔｅ（＋／−１）ＯＲ“Ｙ”；
ｅｌｓｅ
ｓｔａｔｅ（＋／−１）＝ｓｔａｔｅ（＋／−１）；
ｅｎｄｉｆ．
換言すれば、４５度の情報の伝播は、左および／または右の隣接した処理要素に情報を送ることによって実現される。このことは、直接コネクション１６を用いて、または交差接続２２を用いて、ラインメモリ２６の隣接したデータ要素を変えることによってなされてもよい。事実上、左に対するまたは右に対する１つの処理要素の状態ベクトルは、修正される。単純で効果がある実施例においては、３つの伝播方向が使われる。このような実施例では、「垂直」伝播方向または０度の伝播方向は、ステート（０）を修正することを意味する；−４５度の伝播方向は、状態（−１）を修正することを意味する；＋４５度の伝播方向は、ステート（＋１）を修正することを意味する。各々の特定の状態ベクトルにおいて、たとえば、ビットプレーンにセットすることによって、所望の方向にブロードキャストすべきフィルタの結果が書き込まれる。
【００３１】
画像の行を処理するときに、オブジェクトが検出されたことを決定するために、十分な特徴が検出されたかどうか、それぞれの処理要素と関連している状態ベクトルがチェックされる。
【００３２】
本発明の実施例は、図３−６において例示される。図３は、処理しているカラーイメージの概略図である。画像は、エッジ３１、カラーイメージとして赤く見える尾灯３２および３４、ナンバープレート３６、および陰３８を含む車３０の図を有する。尾灯３２および３４は、画像の赤い点の存在を検出する比較的単純なフィルタによって、特徴として検出することができる。例えば、ナンバープレート３６は、ナンバープレートが比較的小さい領域のエッジの比較的高い密度を含むという仮定をすることによって検出されてもよい。これらのエッジは、ナンバープレート数字を形成している文字、およびナンバープレート自体のエッジに関係する。このように、ナンバープレートは、エッジの高密度を検出することによって検出される。周知のように、ナンバープレートを検出する他の考えられる方法としては、光学的文字認識技術が含まれる。同様に、例えば画像の比較的暗い（低輝度）域を検出することによって、陰３８が検出されてもよい。これらの、そしてまた他の特徴は、区別されて、車の自動物体認識のために、自動的に検出される。他の可能な特徴には、時間帯、タイヤ、車輪、ドア、その他が含まれる。この例では、我々は、『尾灯』、『ナンバープレート』および『陰』の特徴の使用について述べる。より好ましい実施例において、特徴は、認識されて、既に述べた実施例に類似した方法で伝播される。より多くの特徴を検出することによって、物体認識は、より安定する。好ましくは単一の行の処理に複数の処理要素を使用して、画像は、行毎に処理される。画像は、上から下に処理される。列または列の集合に沿った全てのデータ要素は、単一の処理要素によって処理される。別の実施例では、画像は、左から右に、右から左に、下から上に、または他のいかなる方向にも処理される。データ要素の処理要素の配置は、異なってもよい。
【００３３】
図４に進むと、尾灯３２を含んでいる画像の行を処理するときに、尾灯３２を含んでいる行のデータ要素を処理することを担当する処理要素は赤い点として尾灯３２を検出する。それは、下に２つの方向（すなわち、４５度下方左（矢印４０によって示される）および４５度下方右（矢印４２によって示される））の特徴『赤い点』を伝播する。このことは、処理要素に赤ランプに関する情報を伝播することによってなされる。処理要素は、データ要素（例えばピクセル）を、方向４０または方向４２のいずれの方向にも沿って処理する。尾灯を表している赤い点を検出する処理要素は、右のおよび左の２つの隣接した列のデータ要素を処理することを担当する処理要素にフラグを立てる。同様に、例えば特徴が検出された確度およびそれが検出された場所についての追加情報が、２つの処理要素に提供される。次の画像行を処理するときに、フラグおよび追加情報が、２つの上述したフラグ集合を有する処理要素によって考慮される。フラグおよび追加情報は、他の処理要素によってセットされた他のフラグに関する情報、および、処理要素によって現在処理しているデータ要素に関する情報と結合される。もし、オブジェクトが検出されなかった場合には、特徴は、線４０および４２に沿って、更に伝播される。同様に、尾灯３４は処理要素によって検出される。そして、この特徴に関する情報は線４４および４６に沿って伝播される。方向４２および４４は、交点４８を有する。交点４８のデータ要素を処理する処理要素は、両方の尾灯の情報を結合する。好ましい実施例においては、同様に、少なくとも一つの隣接した処理要素またはデータ要素に伝播される情報が考慮される。このことは、２本の伝播線４４および４６の交差ポイントにデータ要素がない状況を扱うことを可能にする。
【００３４】
図５は、ナンバープレート３６が多数の処理要素によって検出されることを示している。ナンバープレートの特徴に関する情報は、下に垂直に伝播される。これは、処理要素の中でフラグをセットして、フラグ集合を保つことによって実現されてもよい。特徴について保たれる情報は単純なフラグに限られる必要はなく、たとえば画像のその場所にナンバープレートが存在することの確度のような詳細な情報が保存されてもよい。下方へ垂直に情報を伝播することによって、交点４８で、２つの尾灯に関する情報だけでなく、同様にナンバープレートの検出に関する情報も得られる。これらの状況下では、ある程度の確率で画像中に車があるということを判断することが可能である。交点で、第４の特徴として、車の影３８は同様に検出されてもよい。そして、それは車が画像に示されるという確率を増加させる。
【００３５】
図６は、別の画像が表示されている。同じ車６０を別の角度で示している。特徴伝播の方向が４５度で固定されているので、尾灯６２および６４の伝播方向の交点６１は図５の状況と比較して、車と関連して別の場所にある。交点６１では、陰６８がなく、ナンバープレート６６に関する情報は交点６１に伝播されない。オブジェクトを認識することを可能とするために、交点６０（これは、尾灯６２および６４に関する情報である）で利用できる特徴の組合せは、方向６５および６７において更に伝播される。その結果、交点６３で、両方の尾灯に関する伝播された情報、ナンバープレートに関する伝播された情報および陰に関する局所情報すべてが、交点６３でデータ要素を処理している処理要素で利用できるということである。この処理要素は、全ての情報を結合して、車の存在の信号を発する。都合のよいことに、各々の特徴が画像において検出される場所も、同様に伝播される。情報を結合する処理要素は、オブジェクトの位置、方向づけおよび／またはサイズを決定することが可能である。
【００３６】
図７は、本発明の実施例の処理フローである。特に、多数の処理要素のうちの１つの処理要素のフローが例示されている。ステップ１００において、処理要素はデータ要素を処理する。おそらく、エッジまたは特定色または強度のような、定義済み特徴が検出される。ステップ１０４において、処理要素は、処理要素の近くのデータにアクセスすることによって、他の特徴に関する情報があるかどうか調べる。この情報は、他の処理要素から得られた（伝播された）情報であってもよい。または、この情報は、画像の他の場所で同じ処理要素によって検出される特徴であってもよい。ステップ１０４において、処理要素が、入手可能な情報を結合し、これに基づいて、定義済みオブジェクトが検出されたか否かを決定する。このため、処理要素は、特徴が認識される各々の種類のオブジェクトになければならない情報を使用する。この情報は、オブジェクトモデルに基づく。オブジェクトが検出された場合（ステップ１０６）、ステップ１０８において報告される。この報告は、フラグをセットするか、または信号を他のプロセッサに送信することを含んでもよい。オブジェクトを報告するかまたは検出した後においては、結びつけられた特徴は、通常は更に伝播される必要はない。ステップ１０６において、オブジェクトが検出されなかった場合、関連した特徴はステップ１１０の他の処理要素に伝播される。この目的で、処理要素は、得られた情報を各々の特徴が伝播されなければならない処理要素に対して維持する。オブジェクトがステップ１０６において検出された場合であっても、いくつかの特徴（通常オブジェクトと関連していない特徴）に関する情報をステップ１１０において更に伝播させることは可能である。
【００３７】
報告ステップ１０８および／または伝播ステップ１１０の後、終了基準が、ステップ１１２において評価される。例えば、オブジェクトがステップ１０８において検出された場合、または、画像の列の全てのデータ要素を処理した場合、処理を終了させることができる。終了基準が満たされない場合、フローは次の処理要素を処理するためのステップ１００に戻る。
【００３８】
データ要素の格子を有している画像の特徴を検出する方法の実施例は、第１の場所で画像の第１の特徴３２に関する情報を決めるステップ；第１の場所から第１の方向４２に沿って設置されるデータ要素を処理するときに、処理要素２４に対して、第１の特徴３２に関する情報を考慮させるステップ；第１の場所および第１の方向によって定義される線４２に沿ってデータ要素を処理するときに、第１の特徴３２に関する情報および第２の特徴３４に関する情報に基づき、画像のオブジェクト３０に関する情報を認識するステップ；を有する。第２の特徴３４は第２の方向４４に伝播される、そして、オブジェクトは第１の線４２および第２の線４４の交点４８で認識される。
【００３９】
本発明は、同様に本発明を実行するコンピュータプログラム、特にキャリア上のコンピュータプログラムに及ぶことはいうまでもない。プログラムは、ソースコード、オブジェクトコード、ソースコードおよびオブジェクトコードの中間の形式、例えば部分的にコンパイルされた形式、あるいは本発明による方法の実装のために適切な他のいかなる形式であってもよい。キャリアは、プログラムを蓄積できるいかなる物体または装置であってもよい。例えば、キャリアは、ＲＯＭ、例えばＣＤＲＯＭまたは半導体ＲＯＭのような、記憶媒体または磁気記録装置、例えばフロッピー（登録商標）ディスクまたはハードディスクであってもよい。更に、キャリアは電気的か光学的信号のような、送ることのできるキャリアでもよい。そして、それは電気に関するか光学ケーブルを経てまたは無線通信または他の手段によって伝達される。プログラムがこの種の信号に表現されるときに、キャリアはこの種のケーブルであるか他の装置または手段によって構成される。あるいは、キャリアは、プログラムが埋め込まれた集積回路であってもよい。集積回路は発明を実施するため、あるいは関連した方法を実行するために構成される。
上述の実施例が本発明を制限するよりはむしろ、実例を示す点に留意する必要がある。そして、その当業者は添付の請求の範囲の範囲内において、多くの別の実施例を設計することが可能である。請求項において、括弧の中に配置されるいかなる参照符号も請求項を制限するように解釈されない。動詞「Ｃｏｍｐｒｉｓｅ（有する）」、およびその活用形は、請求項においてそれら以外の要素またはステップの存在を除外しない。「ａ」または「ａｎ」は、複数のこの種の要素の存在を除外しない。本発明は、いくつかの異なった要素を有しているハードウェアによって、そして、最適にプログラムされたコンピュータによって実行される。装置クレームにおいて、いくつかの手段が列挙されているとき、これらの手段のいくつかは全く同一のハードウェアによって実施される。特定の手段が相互に別の従属クレームにおいて詳述されるという単なる事実は、これらの計測の組合せが有効に使われることができないことを示すものではない。
【図面の簡単な説明】
【００４０】
【図１】本発明の実施例を表す図である。
【図２】本発明の他の実施例を表す図である。
【図３】本発明の使用法を例示する図である。
【図４】本発明の使用法を例示する図である。
【図５】本発明の使用法を例示する図である。
【図６】本発明の使用法を例示する図である。
【図７】本発明の実施例を表す図である。
【図１】
2009540416.tif 000003
【図２】
2009540416.tif 000004
【図３】
2009540416.tif 000005
【図４】
2009540416.tif 000006
【図５】
2009540416.tif 000007
【図６】
2009540416.tif 000008
【図７】
2009540416.tif 000009
【手続補正書】
【提出日】平成20年12月9日(2008.12.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ要素の格子を有している画像のパターンを検出する方法であって、予め定められた順序で各々のデータ要素を処理するステップを有し、かつ前記データ要素のうちの１つを処理するときに：
前記データ要素における予め定められた局所的特徴の存在をチェックするステップ、および前記局所的特徴が存在する場合に前記局所的特徴に関する情報を生成するステップ、
伝播方向を前記情報と結びつけるステップであって、前記伝播方向に沿ったデータ要素がまだ処理されなければならないように、前記伝播方向が選択されるところの結びつけるステップ；
前記伝播方向に沿って前記データ要素に最も近いデータ要素の前記方向に、前記情報を伝播するステップ；および
前記画像のいずれかの場所で確証した局所的特徴に関する前記データ要素に伝播された情報に基づき、複数の特徴を含む予め定められたパターンの存在をチェックするステップ；および
前記パターンが見つかった場合に、前記パターンに関する情報を出力するステップ；
を有する方法。
【請求項２】
前記データ要素を処理することの前記予め定められた順序は、格子線の全てのデータ要素が処理されてから次の隣接した格子線のデータ要素の処理へ進むようになされる、
請求項１に記載の方法。
【請求項３】
前記予め定められた順序に従って並列に複数のそれぞれのデータ要素を処理するための複数の処理要素を使用するステップを更に有する方法であって、かつ
前記情報を伝播するステップは、前記情報が伝播される前記それぞれのデータ要素を予定に従って処理する前記処理要素が利用できる前記情報を作るステップを有する、
請求項１に記載の方法。
【請求項４】
前記データ要素を処理する前記予め定められた順序は、
予定に従って並列に処理される複数のデータ要素が単一の格子線の一部分で、かつ全ての前記格子線のデータ要素が処理されてから、次の隣接した格子線のデータ要素の処理へ進む、
請求項３に記載の方法。
【請求項５】
前記パターンの存在をチェックするステップは、前記処理要素に伝播される前記情報に基づいて同様に処理要素によって実行される、
請求項１に記載の方法。
【請求項６】
前記処理要素は、単一命令多重データタイプのプロセッサの処理要素である、
請求項３に記載の方法。
【請求項７】
前記パターンは、定義済タイプのオブジェクトに対応する、
請求項１に記載の方法。
【請求項８】
前記情報を伝播するステップは、前記情報が伝播する前記それぞれのデータ要素を予定に従って処理する前記処理要素がアクセスできるメモリに前記情報を保存するステップを有する、
請求項３に記載の方法。
【請求項９】
前記パターンが存在する場合に前記パターンに関する情報を生成するステップ、および伝播方向を前記情報と結びつけるステップであって、前記伝播方向に沿ったデータ要素がまだ処理されなければならないように、前記伝播方向が選択されるところの結びつけるステップを更に有する方法であって、かつ
前記パターンの存在をチェックするステップは、同様に、前記画像のいずれかの場所で確証したパターンに関する前記データ要素に伝播される前記情報に基づく、
請求項１に記載の方法。
【請求項１０】
前記情報および前記データ要素の前記方向に伝播され受け取られた情報は、予め定められた角度の範囲内で前記画像に沿って全方向に伝播する、
請求項１に記載の方法。
【請求項１１】
前記伝播方向は、前記画像の軸のうちの少なくとも１本と４５度または０度の角度を含む、
請求項１に記載の方法。
【請求項１２】
情報が生成された第１の局所的特徴と関連する第１の伝播方向と、情報が生成された第２の特徴と関連する第２の伝播方向との交点の存在を確証するステップであって、前記交点が前記画像の境界の外に位置するところのステップ；および
前記第１の局所的特徴に関する前記情報および前記第２の局所的特徴に関する前記情報および前記パターンが見つかった場合に前記パターンに関して出力される情報に基づき、複数の特徴を含むパターンの存在をチェックするステップ；
を更に有する請求項１に記載の方法。
【請求項１３】
データ要素の格子を有している画像のパターンを検出するシステムであって、請求項１に記載の方法に従って、予め定められた順序でデータ要素を処理するための少なくとも一つの処理要素を有するシステム。
【請求項１４】
前記予め定められた順序に従って並列に複数のそれぞれのデータ要素を処理するための複数の前記処理要素；および
前記情報が伝播される前記それぞれのデータ要素を予定に従って処理する前記処理要素が利用できる前記情報を作るための手段；
を有する請求項１３に記載のシステム。
【請求項１５】
プロセッサが請求項１に記載の方法を実行することを可能にするためのコンピュータ命令を有するコンピュータプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明はデータ要素の格子を有している画像のパターンの検出に関する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００２
【補正方法】変更
【補正の内容】
【０００２】
関連する従来技術が、下記非特許文献１および非特許文献２に開示されている。
例えば、画像の対象物およびパターン認識は、ロボティックビジョンにおいて重要である。結果がリアルタイムで必要な場合であって、計算資源が制限される場合には特に、パターン認識タスクの計算の複雑性のため、並行処理が望ましい。ピクセルごとのタスクにおける低消費電力と共に比較的高いパフォーマンスを提供する（単一命令多重データ）ＳＩＭＤプロセッサが画像処理のために用いられてもよい。いくつかのビデオ改良技術は、これらの機械によってうまく実装された。しかし、異なった大きさを持つ、たとえば変形可能なオブジェクトのための画像解析を実行するには、ローカル、ラインベースの画像に対するリニアなＳＩＭＤは利用が難しい。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
【非特許文献１】ＲＥＵＶＥＲＳ  Ｍ：“Ｆａｃｅ  Ｄｅｔｅｃｔｉｏｎ  Ｏｎ  Ｔｈｅ  ＩＮＣＡ＋”
【非特許文献２】ＫＹＯ  Ｓ  ＥＴ  ＡＬ：“Ａ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｐａｒａｌｌｅｌ  Ｐｒｏｃｅｓｓｏｒ  ＬＳＩ  ｆｏｒ  Ｖｉｄｅｏ−ｂａｓｅｄ  Ｄｒｉｖｅｒ  Ａｓｓｉｓｔａｎｃｅ  Ｓｙｓｔｅｍｓ”
【非特許文献３】“Ｓｍａｒｔ  Ｃａｍｅｒａｓ：Ａｒｃｈｉｔｅｃｔｕｒａｌ  Ｃｈａｌｌｅｎｇｅｓ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ＡＣＩＶＳ  ２００２，  Ｇｈｅｎｔ，  Ｂｅｌｇｉｕｍ）
【特許文献１】米国特許出願公開第２００２／０１８１７７５号明細書
【特許文献２】米国特許出願公開第２００２／０１８１７６５号明細書
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】変更
【補正の内容】
【００２７】
本発明の実施例を実現するために非常に適しているアーキテクチュアは、Ｘｅｔａｌ  ＬＰＡ−ＳＩＭＤであり（上述の非特許文献３を参照）、これを図２に示す。これには、ラインメモリ２６およびコントローラ２８が含まれる。処理配列２０は、コントローラ２８の制御で命令を実行する処理要素ＰＥ０、ＰＥ１、．．．ＰＥｎを有する。ラインメモリの情報は、周辺機器、例えばコントローラ２８の制御下の画像データを含んでいるメインメモリと交信される。ラインメモリは、データ要素（例えば画素（ピクセル）または体積要素（ボクセル））を含む。接続２１によって、ラインメモリ２６の各々のデータ要素は、それぞれの処理要素２４に連結される。処理要素は、同様に交差接続２２によって隣接したデータ要素にアクセスする。プロセッサアレイ２０（ＰＥ０．．．ＰＥｎ）は、特徴（上記の実例の項番１〜４）の必要な集合の検出のために必要な全ての単純なフィルタリングをすることができる。交差接続２２を有することによって、隣接した要素に連結し、４５度および０度のデータブロードキャストが非常に能率的に実行されてもよい。接続２１および交差接続２２は、各々の処理要素２４が左、右または直上のラインメモリ２４の記憶素子から情報を得るために、マルチプレクサによって実現される。
【国際調査報告】
2009540416.tif 000010
2009540416.tif 000011
2009540416.tif 000012