(57)【要約】輪郭マッチングに基づく高速物体検出に有用な物体輪郭画像（１００）を分析する方法は、輪郭画像（１００）のほとんどすべての画素を処理するための注目領域（３０３）の輪郭画像（１００）内での位置（ｘR、ｙR）の走査経路（３０６）を特定し、少なくとも１個の非ゼロ値を持つ位置座標（ｘ）の輪郭イメージ（１００）内の各画素から成る第１テーブルを構築し、注目領域（３０３）の位置に対応した第４テーブル（３１１）であって、注目領域（３０３）を通過する画素の少なくとも各平行ラインに対して、所定の走査方向に見てそれぞれの平行ライン上かつ注目領域（３０３）の内側に存在する輪郭画像（１００）の第1非ゼロ値画素に関する第１テーブル（１１１）内のエントリー（１２１）のインデックス（３１２）を含む該第４テーブル（３１１）を構築し、注目領域（３０３）の位置に対応した第５テーブル（３１３）であって、注目領域（３０３）を通過する画素の少なくとも各平行ラインに対して、所定の走査方向に見てそれぞれの平行ライン上かつ注目領域（３０３）の内側に存在する輪郭画像（１００）の最終非ゼロ値画素に関する第１テーブル（１１１）内のエントリー（１２１）のインデックス（３１４）を含む該第５テーブル（３１３）を構築することより成る。
2007508633.tif 000002
【特許請求の範囲】
【請求項１】
輪郭画像を解析する方法において、
‐輪郭画像内での、それぞれ注目領域に対応する位置の走査経路を特定し、
‐輪郭画像の各非ゼロ値画素に関する少なくとも１個の位置座標を含む第1テーブルを構築し、
‐注目領域の位置に対応するエントリーを有する第４テーブルであって、所定の向きを持ち注目領域を通過する画素の少なくとも各平行ラインを含み、所定の走査方向に見てそれぞれの平行ライン上かつ注目領域の内側に存在する輪郭画像の最初の非ゼロ値画素に関する第１テーブル内のエントリーのインデックスを含む該第４テーブルを構築し、
‐注目領域の位置に対応するエントリーを有する第５テーブルであって、所定の向きを持ち注目領域を通過する画素の少なくとも各平行ラインを含み、所定の走査方向に見てそれぞれの平行ライン上かつ注目領域の内側に存在する輪郭画像の最終非ゼロ値画素に関する第１テーブル内のエントリーのインデックスを含む該第５テーブルを構築する
ことよりなることを特徴とする画像解析方法。
【請求項２】
輪郭画像を解析する請求項１に記載の方法において、
‐列に沿って下方に移行し、その後は次の列にジャンプするよう連続して位置をたどる走査経路を特定し、
‐少なくとも１個の位置座標において非ゼロ値を持つような輪郭画像内の画素を記憶する第１テーブルを構成し、
‐注目領域を通過する画素の各水平ラインに対して、第１テーブル内のエントリーのインデックスであり、注目領域内部にあるそれぞれの水平ライン上の輪郭画像における最左端の非ゼロ値画素を記憶する第４テーブルを構築し、
‐注目領域を通過する画素の各水平ラインに対して、第１テーブル内のエントリーのインデックスであり、注目領域内部にあるそれぞれの水平ライン上の輪郭画像における最右端の非ゼロ値画素を記憶する第５テーブルを構築する
ことよりなる画像解析方法。
【請求項３】
輪郭画像を解析する請求項２に記載の方法において、
‐輪郭画像のほぼ各水平ラインに関して第1テーブル内のエントリーのインデックスであって、輪郭画像のそれぞれの水平ライン上における最左端の非ゼロ値画素を記憶する第２テーブルを構築し、
‐輪郭画像のほぼ各水平ラインに関して第1テーブル内のエントリーのインデックスであって、輪郭画像のそれぞれの水平ライン上における最右端の非ゼロ値画素を記憶する第３テーブルを構築し、
‐第４テーブル、第５テーブルを第１テーブル、第２テーブル、第３テーブルに基づいて構築する
ことよりなる画像解析方法。
【請求項４】
請求項１，２または３のうちいずれか１項に記載の画像解析方法により輪郭画像内の物体を検出する方法において、
‐第４テーブル、第５テーブルに基づいて、走査経路に沿った連続点における注目領域内部の非ゼロ値画素のカウント数を計算し、
‐テンプレート輪郭と、注目領域内部の輪郭画像の画素とのマッチング度を得るために、カウント数が所定画素量よりも大きいかまたは等しい場合に注目領域内の画素およびテンプレート輪郭窓内の画素を引数としたマッチ関数を評価し、
‐カウント数が所定画素量よりも小さい場合は走査経路に沿った他の位置へとジャンプさせる
ことよりなる物体検出方法。
【請求項５】
検証すべきテンプレート輪郭が、テンプレート輪郭窓における幾何学的変換であるとした輪郭画像内の物体を検出する請求項４に記載の方法において、
‐テンプレート輪郭窓の画素のために、テンプレート輪郭窓の画素位置および幾何学的変換により決定される位置における輪郭画像の対応画素をフェッチし、
‐テンプレート輪郭窓内の画素と対応画素と間の類似性に基いてマッチ関数を評価する
ことよりなる物体検出方法。
【請求項６】
輪郭画像内の物体を検出する請求項１〜５のうちいずれか１項に記載の方法において、
輪郭画像を得るために画像に輪郭検出を適用する
ことよりなる物体検出方法。
【請求項７】
輪郭画像を解析するための画像処理装置において、
‐注目領域の輪郭画像内の走査経路上の位置を特定するよう構成した第１ユニットと、
‐ａ）輪郭画像の各非ゼロ値画素に関して少なくとも１個の位置座標を含む第1テーブル、
ｂ）注目領域の位置に対応した第４テーブルであって、注目領域を通過する画素の少なくとも各平行ラインに対して、所定の走査方向に見てそれぞれの平行ライン上かつ注目領域の内側に存在する輪郭画像の最初の非ゼロ値画素に関する第１テーブル内のエントリーのインデックスを含む該第４テーブル、
ｃ）注目領域の位置に対応した第５テーブルであって、注目領域を通過する画素の少なくとも各平行ラインに対して、所定の走査方向に見てそれぞれの平行ライン上かつ注目領域の内側に存在する輪郭イメージの最終非ゼロ値画素に関する第１テーブル内のエントリーのインデックスを含む該第５テーブル
を構築してメモリに記憶するよう構成した第２ユニットと
を備えたことを特徴とする画像処理装置。
【請求項８】
請求項７記載の画像処理装置を有して輪郭画像内の物体を検出するための画像処理装置において、さらに、
注目領域内の画素およびテンプレート輪郭窓内の画素を引数とするマッチ関数を評価するよう構成した照合ユニットと、
‐注目領域内部の非ゼロ値画素のカウント数を計算するよう構成し、第４テーブルおよび第５テーブルに基づき、所定画素量よりもカウント数が小さい場合には走査経路に沿ってさらに次の位置にジャンプするように第１ユニットに指示し、かつ、所定画素量よりもカウント数が大きいかまたは等しい場合に、現在の注目領域においてマッチ関数を評価するように照合ユニットに指示するよう構成した決定ユニットと
を備えた画像処理装置。
【請求項９】
請求項７記載の画像処理装置または請求項８記載の画像処理装置を備えた産業用視覚装置において、さらに、
‐カメラから受信可能な画像から輪郭画像を生成するよう構成した輪郭生成ユニットと、
‐マッチ関数の結果に依存して信号を出力するよう構成した制御ユニットと
を備えたことを特徴とする産業用視覚装置。
【請求項１０】
請求項７記載の画像処理装置、または請求項８記載の画像処理装置を備えるスマートカメラにおいて、さらに、
‐カメラがキャプチャーした画像から輪郭画像を生成するよう構成した輪郭生成ユニットと、
‐カメラがキャプチャーし、画像処理装置により検出した物体に基づき決定される画像領域に対して、画像変換を適用するよう構成した画像処理ユニットと
を備えたことを特徴とするスマートカメラ。
【請求項１１】
請求項７記載の画像処理装置、または請求項８記載の画像処理装置を備えた画像ディスプレイにおいて、さらに、
‐画像ディスプレイから受信する画像から輪郭画像を生成するよう構成した輪郭生成ユニットと、
‐画像処理装置により検出された物体に基づき決定される受信画像領域に、画像変換を適用するよう構成した画像処理ユニットと、
を備えたことを特徴とする画像ディスプレイ。
【請求項１２】
請求項９に記載の産業用視覚装置を備えたことを特徴とするセキュリティシステム。
【請求項１３】
請求項１〜６のいずれか１項に記載の方法をプロセッサに実行させることができるプログラムコードを備えたことを特徴とするコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、輪郭画像を解析する方法に関する。
本発明はまた、画像内の物体を検出する方法に関する。
本発明はまた、物体輪郭画像を解析する画像処理装置に関する。
本発明はまた、画像内の物体を検出する画像処理装置に関する。
本発明はまた、１個またはそれ以上の該画像処理装置を備える産業用視覚装置に関する。
本発明はまた、１個またはそれ以上の該画像処理装置を備える高性能スマートカメラに関する。
本発明はまた、１個またはそれ以上の該画像処理装置を備える画像ディスプレイに関する。
本発明はまた、１個またはそれ以上の該産業用視覚装置を備えるセキュリティシステムに関する。
本発明はまた、少なくとも１個の該方法をプロセッサに実行させることができるコードを備えるコンピュータプログラム製品に関する。
【背景技術】
【０００２】
従来、画像、特にそれら画像内の物体検出を目的とした解析方法は、数多く存在する。例えば、生産ライン上の欠陥製品は、カメラキャプチャー画像の解析により、自動的にメインラインから手動修理ユニットに向かうようルート変更しなければならない。物体は、グレー値テンプレートとキャプチャー画像と間の相関をとることにより検出できる。このグレー値相関方法には、例えば照明効果、特にハイライト効果の影響により、しばしば不正確な検出結果を生ずるという欠点がある。こういった問題を克服するように考案された他の物体検出方法として、物体の輪郭に基づき物体を検出するものがある。輪郭の形状が十分に特徴的で、ふさがれていない部分が十分に広ければ、この方法は有効である。代表的には、キャプチャー画像は、エッジ検出のような処理を行うことで輪郭画像に変換する。輪郭はその後（例えばマルチスケール曲率表示として）表示し、解析する。輪郭を検出するための簡単な方法は、探索する物体の輪郭上にあると予想される輪郭画像の画素と、テンプレート輪郭窓の画素とを、マッチ関数を用いて照合（マッチング）することである。テンプレート輪郭上に輪郭画像内の画素数が多くあれば、マッチ関数は、テンプレート輪郭を検出したことを示す高い値を発生する。全ての値が所定許容閾値よりも低い場合は、検証している輪郭画像内の現在位置には所望の形の物体が存在しそうにないことを示す。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
物体輪郭照合（マッチング）に基づく従来の物体検出方法の欠点は、輪郭画像内の相当数の各画素に対して、各テンプレートの存在を照合（マッチング）により検証しなければならないことである。単に１個の物体の探索でも、その物体は例えば１０通りの異なる向きと１０通りの異なる縮尺で存在するかもしれず、その場合はすなわち輪郭画像内の各画素（例えば４０００×３０００画素を含む産業用視覚装置内）に対して、１００通りものテンプレートを照合（マッチング）しなければならない。もしマッチ関数がテンプレート内と輪郭画像内の画素との差の絶対値を加算し、かつテンプレート輪郭窓が例えば５０００個もの画素（輪郭画像の大部分が正常に画像化された物体の輪郭ではあり得ないことではない）を含む場合、これら１００通りの各テンプレート照合（マッチング）は、それぞれ５０００回もの引算処理が必要とする。これは輪郭照合（マッチング）に基づく物体検出処理を遅くし、多くの実時間的用途には適さない。例えば多種多様の物体間を自ら進路をみつけて進んでいくロボット装置といった産業用視覚システムが一般家庭で用いられるような近い将来には、数個の物体のを同時にチェックしなければならない。
【０００４】
本発明の目的は、物体検出のための比較的高速な輪郭イメージ解析方法を提供することにある。
【課題を解決するための手段】
【０００５】
この目的を達成するため本発明輪郭画像解析方法は、
‐輪郭イメージ内の位置での、それぞれ注目領域に対応する各々の位置の走査経路を特定し、
‐輪郭画像の各非ゼロ値画素に関する、少なくとも１個の位置座標を含む第1テーブルを構築し、
‐注目領域の位置に対応するエントリーを有する第４テーブルであって、所定の向きを持ち注目領域を通過する画素の少なくとも各平行ラインを含み、所定の走査方向に見てそれぞれの平行ライン上かつ注目領域の内側に存在する輪郭画像の最初の非ゼロ値画素に関する第１テーブル内のエントリーのインデックスを含む該第４テーブルを構築し、
‐注目領域の位置に対応するエントリーを有する第５テーブルであって、所定の向きを持ち注目領域を通過する画素の少なくとも各平行ラインを含み、所定の走査方向に見てそれぞれの平行ライン上かつ注目領域の内側に存在する輪郭画像の最終非ゼロ値画素に関する第１テーブル内のエントリーのインデックスを含む該第５テーブルを構築する
ことを特徴とする。
【発明の効果】
【０００６】
物体検出に用いる方法では、所望物体の存在に対して輪郭画像全体にわたるチェックを回避できない。たとえ輪郭画像の小さい部分でもチェックされずに残っていると、まさにその部分に所望物体がある状況が起こり得、その場合、行ったすべての操作は無駄になる。しかしながら、本発明方法によれば、できるだけ見当違いの労力を少なくするように、最適化できる。本発明は、テンプレート輪郭における画素数に関する領域が十分な画素を含んでいなければ、それ以降のコストのかかる照合（マッチング）による検証を回避できるという洞察に基づいている。さらに、画像は連続性を有しているため、多くの照合（マッチング）位置はスキップできうる。これは、必要な画素数に達するまでには多くの行（または列）があるためである。しかしながら、正確な構造と輪郭画素数を求めて輪郭領域を解析することは、コストのかかる操作を一層必要としうる。本発明による方法ではその操作数を少なく抑えられる。本発明による物体輪郭画像解析方法は、物体検出方法に用いるよう設計し、テーブルのシンプルなデータ構造を構築し、このデータ構造によれば、輪郭画素、あるいは一般的な注目画素を迅速にカウントできる（例えば、輪郭画像上での距離変換によって他の画素を生成する）。
【０００７】
従って、窓内で、例えばジグザグ対角線方向、またはヒルベルトフラクタル線に沿う、または上下かつ左右方向といった走査経路を導入できる。そのような走査経路の場合、輪郭画像内の実質全ての画素が対応する注目領域内で解析される。カメラでキャプチャーされた画像の１部分のみが所望の物体を含んでいる場合は、この１部分を輪郭画像と称することができる。第1テーブル内に、全ての非ゼロ値（輪郭画素または一般的に注目する画素）画素が記憶され、少なくとも1個の座標が与えられる。「非ゼロ値」という言葉には特別重要性がないことに注意を要する。というのは、これは本発明による方法の最も容易な場合を反映しており、本方法をより分かり易く記述するためのものだからである。一般的に、非ゼロとは、所定の値と等しくないものと読み取ることができ、例えばわずかな変化を補償するために、輪郭画像の全ての値に３などの一定値を加える変更例もカバーする。
【０００８】
例えば、テレビジョンシステムのように画像を行方向に走査する場合、全ての画素が1次元的に自然な並びで存在し、それゆえ、例えばｘ座標だけで十分であり（言うまでもなく、ｙ座標にも同じ方法が使え、これは、輪郭画像をあらかじめ９０度回転させたものに対応する）、ただし、全ての行を考慮に入れるものとする（本発明による実施例では、列に非ゼロ値がない場合には「非数値（NaN）」コードを挿入することによって行う）。
【０００９】
（照合のためのテンプレート輪郭窓のサイズに対応する）注目領域を通過する少なくとも全平行ライン上における最初と最後の非ゼロ値インデックスのテーブルを作ることで、画素のカウントが容易になる。注目領域が下方に４５゜傾斜している向きを有するラインから構成される場合、例えば最初のラインはまず注目領域内のただ1画素上を通過し、２番目のラインは２画素、それ以降も同様に続く。走査方向は例えば左上から右下に向かう方向となる。最初に遭遇する非ゼロ値画素は例えば５番目のライン上における２番目の画素で、最後の画素は５番目の画素となる。画素の座標ではなく第１テーブル内のインデックスを使えば、より速くカウントできる。このことは、注目領域が水平方向の行に分割されている場合により理解しやすい。最初の画素はこのとき第１行の画素３となり、最後の画素は画素１０となる。単に１０から３を引くだけでは、最初と最後の画素の間にゼロ値の画素がある可能性もあるため、この行上に８個の非ゼロ値画素があることにはならない。第１テーブル（全ての非ゼロ値画素のみを有する）内エントリーのインデックスを引くことで、対象とする行上の正味の画素数が得られる。全ての行のカウント数を足すことで、注目領域内部の総画素数が得られる。第４、第５テーブルはそれぞれ、最初と最後の画素を与え、通過する全ての通過するライン上の画素（この場合は行上の）部分的カウント数を得る。注目領域の位置は、本明細書の以後の部分で、該注目領域の左上（ｘ，ｙ）座標で定義しているが、言うまでもなく他の、例えば中心画素の座標でも定義しうる。
【発明を実施するための最良の形態】
【００１０】
本発明による輪郭画像解析方法の実施の形態においては、
‐列に沿って下方に移行し、その後は次の列にジャンプするよう連続的して位置をたどる走査経路を特定し、
少なくとも１個の位置座標において非ゼロ値を持つような輪郭画像内の画素を記憶する第１テーブルを構築し、
注目領域を通過する画素の各水平ラインに対して、第１テーブル内のエントリーインデックスであり、注目領域内部にあるそれぞれの水平ライン上の輪郭イメージにおける最左端の非ゼロ値画素を記憶する第４テーブルを構築し、
注目領域を通過する画素の各水平ラインに対して、第１テーブル内のエントリーインデックスであり、注目領域内部にあるそれぞれの水平ライン上の輪郭イメージにおける最右端の非ゼロ値画素を記憶する第５テーブルを構築する。
【００１１】
上述したように、例えば連続する列を下方に走査するテレビジョンのように輪郭画像を走査する方法は、輪郭画像全体を確実に処理するのに概念的に最も単純な方法である。その上、テーブル処理がシンプルである。いくつかの用途ではしかしながら、他の走査経路が好ましい場合がある。例えば、イメージを行ごとに右方向に走査し、次の行ではその行の先頭にジャンプする走査は現行のテレビジョン走査標準と互換性があり、したがって、例えばこのような受信テレビジョン信号の実時間（リアルタイム）処理に有利にはたらく。
【００１２】
本発明による輪郭画像解析方法における他の実施の形態においては、
‐輪郭画像のほぼ各水平ラインに対する第1テーブル内のエントリーのインデックスであって、輪郭画像のそれぞれの水平ライン上における最左端画素を記憶する第２テーブルを構築し、
輪郭画像のほぼ各水平ラインに対する第1テーブル内のエントリーインデックスであって、輪郭イメージのそれぞれの水平ライン上における最右端画素を記憶する第３テーブルを構築し、
第４テーブル、第５テーブルを第１テーブル、第２テーブル、第３テーブルに基づいて構築する。
【００１３】
上述したように、連続する列に沿って走査を行う場合、さらなる速度の最適化を実現できる。注目領域の各（縦方向の）位置に対して新たな第４、第５テーブルを計算する代わりに（これら列が現注目領域内部最左端および最右端の点のみを有する場合）、各連続する列の走査毎に、すなわち現在の列位置における全ての行に対して、第４、第５テーブルを１度に計算する。さらに、全輪郭画像の各行の最左端、最右端画素を記憶する第２、第３テーブルからこれら第４、第５テーブルを容易に得ることができる。
【００１４】
上述の画像解析方法を有効に利用する輪郭画像内の物体を検出する方法においては、
‐第４テーブル、第５テーブルに基づいて、走査経路に沿った連続点における注目領域内部の非ゼロ値画素のカウント数を計算し、
テンプレート輪郭と注目領域内部の輪郭画像画素とのマッチング度を得るために、カウント数が所定画素量よりも大きいかまたは等しい場合に注目領域内の画素およびテンプレート輪郭窓内の画素を引数としたマッチ関数を評価し、
カウント数が所定画素量よりも小さい場合は走査経路に沿った他の位置へとジャンプさせる。
【００１５】
上述したように、ほんのわずかしか画素を含まない領域は考慮する必要がなく、すなわち連続する位置にジャンプすることによりコストのかかる照合を回避できる。連続する位置とは走査経路に沿って１個づつ異なるということではない。走査線に沿う他の位置であり、３座標先にジャンプしてもよい。
【００１６】
輪郭画像内のテンプレート輪郭ウィンドウが検出する物体が、検証すべきテンプレート輪郭が、テンプレート輪郭窓における幾何学的変換である輪郭画像内の物体を検出するような本発明に係る検出方法の実施の形態によれば、画像処理速度がさらに高速化でき、この実施の形態においては、
‐‐テンプレート輪郭窓の画素のために、テンプレート輪郭窓の画素位置および幾何学的変換により決定される位置における輪郭画像の対応画素をフェッチし、
‐テンプレート輪郭窓内の画素と対応する画素と間の類似性に基づいてマッチ関数を評価する。
【００１７】
輪郭におけるサブセットのみを検証すればよく、さらに精密な照合（例えば、物体の正確な向きの角度を知りたいときなど）は、用途で必要とされた場合に行う。
【００１８】
本物体検出方法は、輪郭画像の解析に先立ち輪郭画像を得るために画像に輪郭検出を適用することにより、例えばカメラから直接得られる画像に直接適用できる。
【００１９】
本発明の第２の目的は、比較的高速な、物体検出のための物体輪郭画像解析用画像処理装置を得るにある。
【００２０】
この画像処理装置は、
‐注目領域の輪郭画像内の走査経路上の位置を特定するよう構成した第１ユニットと、
‐ａ）輪郭画像の各非ゼロ値画素に関して少なくとも１個の位置座標を含む第1テーブル、
ｂ）注目領域の位置に対応した第４テーブルであって、所定の向きを持ち注目領域を通過する画素の少なくとも各平行ラインに対して、所定の走査方向に見てそれぞれの平行ライン上かつ注目領域の内側に存在する輪郭画像の最初の非ゼロ値画素に関する第１テーブル内のエントリーのインデックスを含む該第４テーブル、
ｃ）注目領域の位置に対応した第５テーブルであって、所定の向きを持ち注目領域を通過する画素の少なくとも各平行ラインに対して、所定の走査方向に見てそれぞれの平行ライン上かつ注目領域の内側に存在する輪郭イメージの最終非ゼロ値画素に関する第１テーブル内のエントリーのインデックスを含む該第５テーブル
を構築してメモリに記憶するよう構成した第２ユニットと
を備えたことを特徴とする。
【００２１】
輪郭画像内の物体検出用画像処理装置に使用できる本発明画像処理装置はさらに以下のものより成る。すなわち、
‐注目領域内の画素およびテンプレート輪郭窓内の画素を引数とするマッチ関数を評価するよう構成した照合ユニットと、
‐注目領域内部の非ゼロ値画素カウント数を計算するよう構成し、第４、および第５テーブルに基づき、所定画素量よりもカウント数が小さい場合には走査経路に沿ってさらに次の位置にジャンプするように第１ユニットに指示し、かつ、既定の画素量よりもカウント数が大きいかまたは等しい場合に、現在の注目領域においてマッチ関数を評価するように照合ユニットに指示するよう構成した決定ユニットと
を備える。
【００２２】
また、画像処理装置は産業用視覚装置にも使用でき、この産業用視覚装置においては、
‐カメラから受信可能な画像から輪郭画像を生成するよう構成した輪郭生成ユニットと、
‐マッチ関数の結果に依存して信号を出力するよう構成した制御ユニットと
を備える。
【００２３】
また、画像処理装置はスマートカメラにも使用でき、このスマートカメラは、
‐カメラがキャプチャーした画像から輪郭画像を生成するよう構成した輪郭生成ユニットと、
‐カメラによりキャプチャーし、画像処理装置により検出した物体に基づき決定される画像領域に対して、画像変換を適用するよう構成した輪郭処理ユニットと
を備える。
【００２４】
また、画像処理装置は画像ディスプレイにも使用でき、この画像ディスプレイは、
‐画像ディスプレイから受信する画像から輪郭画像を生成するよう構成した輪郭生成ユニットと、
‐画像処理装置により検出された物体に基づき決定される受信画像領域に、画像変換を適用するよう構成した画像処理ユニットと
を備える。
【００２５】
本発明による方法および画像処理装置のこれらまたは他の態様は、これに限定するものではない以下に記載の実施態様および実施例、ならびに添付図面につき説明することに明らかになるであろう。
【実施例】
【００２６】
図１は、例示のための単純化した輪郭画像１００を示し、物体輪郭１０１の物体輪郭画素は１の値（黒の正方形です）を持ち、非輪郭画素は０の値（白の正方形です）を持つ。
【００２７】
グレー値画像（例えば、カメラから得られる画像）から輪郭画素を取出すために、グレー値画像に対して加える第１処理としてエッジ検出を行うのが一般的である。従来既知の代表的なエッジ検出器はキャニー(Canny)エッジ検出器であり、この検出器では、グレー値画像に次式のエッジ検出器カーネル K（ｘ）の離散化マトリックスを畳み込む。
K（ｘ）＝ｄ／ｄｘ（G(x)）    （１）
【００２８】
ｘは水平方向の相対画素座標であり、Gはガウスの平滑化関数である。他の代表的なエッジ検出フィルタとして例えばプレウィット(Prewitt)、デリヒェ(Deriche)、キルシュ(Kirsh)、マール(Marr)等を利用できる。式（１）のカーネルは水平方向のエッジのみ検出するが、垂直方向をも考慮にいれた従来方法も多い（例えば、水平方向と垂直方向でのエッジ検出結果を組み合わせる方法、または両方向を感知するカーネルもしくはカーネル集合を用いる方法がある）。
【００２９】
グレー値画像にエッジ検出カーネルを畳み込む結果、第２次グレー値画像となり、この第２次グレー値画像では、エッジは大きいグレー値（例えば、２５５）となり、非エッジ（例えば、物体の平滑な内部）は小さいグレー値（例えば、０）となる。代表的なエッジ検出の第２段階はクリッピングもしくは最大値探索である。クリッピングは、既定の値（例えば、１２８）よりも大きい値を持つ全てのグレー値を１にセットし、他の全てのグレー値を０にセットする。単位画素の輪郭幅は決められているため、第２段階としては最大値探索が好ましいものであり、この最大値探索は、第２次グレー値画像内の稜線の最大値を１にセットし、他の全ての画素を０にセットする。
【００３０】
解析のために輪郭を得る次段階としては、エッジ結合、不要エッジ削除そして隙間埋め込みである。最終的に、エッジを、ある特定モデルで表し、例えば、直線ラインの多角形に照合させるか、または輪郭に沿った円弧位置に対する正接角の関数として表す。輪郭は、その後例えば、物体の輪郭画像の曲率特徴(curvature signature)と、例えば学習段階で得られる、検出すべき物体の代表的形状に対応したモデルの特徴(curvature signature)とを比較することで照合（マッチング）する。
【００３１】
物体の輪郭は、さらに、色情報、材質感(texture)情報等の情報にも基づいて、例えば１９９７年のＩＥＥＥにおけるマーテンス(M. Mertens)氏およびコーネリス(J. Cornelis)氏による非線形信号および画像処理(Nonlinear Signal and Image Processing)研究会議事録「エラーに強い非線形セグメントエッジファインダ(A robust nonlinear segment-edge finder)」に記載されたエッジ検出器によって得られる。本発明による方法では２次元（２Ｄ）のサンプル画像で説明するが、１次元、３次元、またはより高次元（＞３）の画像にも同様に適用できることに注意されたい。
【００３２】
所定の輪郭画像１００に関して、従来の代表的な照合（マッチング）方法では、輪郭画像１００内の物体輪郭の画素が、輪郭画像１００内で検出したい形状を有するテンプレート輪郭の画素における画素に照合するかをチェックしなければならない。テンプレート輪郭は通常、所望の輪郭から切り出した小断片画像であり、例えば輪郭画像１００の物体輪郭１０１に対して、テンプレート輪郭を“逆Ｕ字”形状を含む４×４の窓とする。
【００３３】
この４×４のウィンドウを、輪郭画像１００にわたりあらゆる画素位置（例えば、輪郭画像１００の画素（ｘ，ｙ）にオーバーラップするテンプレート輪郭窓の最左端画素）にシフトし、例えば次式のマッチ (match)関数を計算する。
【数１】
2007508633.tif 000003
【００３４】
式（２）においてｉとｊは輪郭テンプレート窓内で移動する座標、例えば、それぞれ０からＩ、０からＪ（ＩとＪは図１の例では４）の連続値まで移動す座標であり、ｘとｙは輪郭画像１００においてマッチングする位置を示す座標であり、ｔは輪郭テンプレート窓における位置（ｉ，ｊ）での画素値であり、ｐは輪郭画像１００における画素値、Ｎは正規化定数である。他のマッチ関数、例えば、絶対差分平準化、または次式により表されるブールマッチ関数も使用できる。
【数２】
2007508633.tif 000004
【００３５】
式（３）では、テンプレートおよびイメージ画像の双方が特定位置で値が１の画素を有する場合に積算結果をカウントに加える。
【００３６】
照合値Ｍは、全ての画素が照合すれば最大、すなわち高い値（適切に正規化されれば１に等しい）となり、照合する画素がない場合０、幾つかの画素が照合すれば０から１の中間値となる。後者の状況はテンプレートパターンが画像輪郭の近傍に位置するが、適正に整列していないとき、または異なる形状に対する照合を試みるときに起こる。実際のコンピュータバージョンの用途では、人為的画像生成、雑音、等の要因により、通常は輪郭画像１００の適正位置に全ての画素を含んではいない。代表的な不具合としては以下のものがある。
１）いくつかの輪郭画素の消失
２）余分な、いわゆる不要輪郭ポイントの存在
３）例えば使用するエッジ検出器により、輪郭ポイントが理論上の位置からの微小なオフセット僅かにオフセットすること
である。
【００３７】
それゆえ、マッチング方法を改善するために、図２に示すような平滑化テンプレート輪郭窓２００が通常用いられる。このような窓はテンプレート輪郭の周囲の輪郭では、中間値（０と１との間、あるいは全てが８ビット表現に置換できるのであれば０と２５５との間の値）を有し、この値は、厳密な理論上のテンプレート輪郭位置での最大値（例えば１）からゼロに向かって単調に減少する。
【００３８】
このような平滑化輪郭テンプレート窓２００は、理論的な２値テンプレートを含むテンプレート輪郭窓に距離変換を行うことによって得られる。例えば図２において、マンハッタン距離｜（ｉ−ａ）｜＋｜（ｊ−ｂ）｜が（ａとｂは、最も近傍にある２値テンプレート画素の座標）１である場合、画素には最大値の５０％の値を付与し、２値テンプレート画素からのマンハッタン距離が２である場合、画素には２０％の値を付与する。テンプレートに使いやすい輪郭(profile)はガウス輪郭(Gaussian profile)である。このような平滑化テンプレート輪郭窓２００を使用すると、上述した‐３のポイント下にある若干不揃いの輪郭画素の取扱いにおいて特に有利である。マッチ関数は式（２）、もしくは実数または整数を引数とする関数とすることができる。０もしくは１とは異なる他の値を有するテンプレート輪郭窓を用いるのには他の理由がある。例えば、もしテンプレートモデルが、ある列において（グレー値が１の）３画素の（かつ両端は０である）ラインセグメントであれば、式（３）のマッチング基準によりこのような構成体の有無をチェックする。もし輪郭画像１００内に１０画素で成る水平方向のラインがあれば、３画素セグメントはそのイメージに沿っていたるところで、すなわち１０‐２に後続する位置で検出されてしまう。しかし、厳密に３画素長のラインだけを検出することが要求される用途があり、このことは、例えば、テンプレート輪郭窓２００内の３画素セグメントの両端に、０ではなく−１の値を付加することによって実現でき、このときマッチ関数は、テンプレートの値−１がイメージ内の０ではない１の値に照合するときに低い値を返し、３画素のラインを検出できる。
【００３９】
輪郭マッチングに基づくこのような従来の物体検出方法は、これらの用途では良好に動作するが、コンピュータ計算に係わるコストが極めて高価になる。その理由は、ある特定の輪郭（または多くの考えられる輪郭、例えば同時に複数個、あるいは回転した特異形態を検出すべき場合）の存在に対して、輪郭画像１００内の全ての画素を検査しなけれならず、さらに、テンプレート輪郭窓２００の相当数の画素にわたって複雑なマッチング関数を使わなければならないためである。今日のより高速なコンピュータや強力なＩＣを用いてさえ、多くの用途で実現不能であり、特に、実時間で行うべき用途（例えば、郵便物分配センターにおける郵便切手の自動検出では、経済的に可能である１秒あたり複数枚のレターを処理する必要がある）や、大形の産業用画像（代表的には、７２０×５７６のテレビ画像よりも大きい、例えば１００００×８０００の画像）では実現できない。
【００４０】
本発明による輪郭に基づく物体検出方法によれば、できるだけ少ない操作で作動し、しかも全体検出能力を保持しつつかつ、アルゴリズムをより複雑にする過度の画像解析操作を付加することなく物体検出を達成する。
【００４１】
物体検出方法の好適な実施例では、第１操作として、輪郭画像１００全体に対して、画素位置構造１１０（図１ｂ）を構築し、この構造は、輪郭画像１００内の注目画素（上述の実施例では輪郭検出から得られる値１を持つ画素）に関する情報を示す３つのテーブルを含む。すなわち、
‐非ゼロ値画素のｘ位置座標を含む第１テーブル１１１、
‐輪郭画像１００における各列内での最左端画素の第１テーブル内における個所を示すインデックスを含む第２テーブル１１３、
‐輪郭画像１００における各列内での最右端画素の第１テーブル内における個所を示すインデックスを含む第３のテーブル１１５
である。
【００４２】
まず、第１テーブルを得るために、通常は輪郭画像１００内を、左右かつ上下方向に最初の画素に遭遇するまで走査する。図１の実施例では、この最初の画素は位置（１０，１１）である。この位置「１０」のｘ座標を、第１テーブル１１１の先頭位置（例ではインデックス０の位置）に書き込む。次に遭遇する画素は位置（１１，１１）であり、第１テーブル１１１のインデックス１に数字１１を書き込む。その他の画素についても同様である。
【００４３】
順次にもしくは並列的に、画像内の全ての列を解析し、最左端、最右端の画素を得る。輪郭画像１００の第１列は非ゼロ値を含まないため、第２テーブル１１３および第３テーブル１１５の双方で有効な画素のインデックスは書き込まず、予め定義した値、例えば“非数値（ＮａＮ）”を書き込む。列１１に到達すると、物体輪郭１０１の最左端の画素は位置（１０、１１）であり最右端の画素は位置（１３、１１）となる。第２もしくは第３のテーブルにはｘ座標ではなく、対応する素子のインデックスを書き込む。位置（１０、１１）は第１テーブル１１１の先頭位置であるため、インデックス０が第２テーブル１１３内の位置１２３に書き込む。最右端の位置は４番目の位置であるため、第３テーブル１１５内の位置１２５にインデックス３を書き込む。座標ではなくインデックスで取扱えば、ある列内の画素数が最右端のインデックスと最左端のインデックスの単純な引き算によって得られるという利点がある。もしｘ座標だけを引けば、最左端と最右端の画素間にあるゼロ値が考慮されない。
【００４４】
次に、輪郭画像１００をテンプレート輪郭窓２００で走査するが、本発明による方法では、輪郭画像１００内の全ての画素位置（ｘ，ｙ）において所望の物体輪郭の存在をマッチ関数の評価でチェックするのではなく、関連する候補領域（照合またはマッチングする可能性がある領域、すなわち、予備処理によりマッチングを含み得ないとして無条件に排除されない領域）をマッチ関数で検証する。この走査は、頂部から底部に向かってまた左から右に向かって行うのが好ましい。したがって、テンプレート輪郭窓２００は、まず、テンプレート輪郭窓２００の最左端画素が輪郭ウィンドウ１００の最左端画素にオーバーラップするよう位置決めし（実際には、走査は、部分的に輪郭画像１００の窓の外側からスタートする）、輪郭画像１００窓における、図２の実施例では８列目から始まる（輪郭画像１００の高さ全体に沿う）垂直区域３０１に対して照合（マッチング）を行い、輪郭画像１００内におけるテンプレート輪郭窓２００の最左端コーナーに対応する位置に所望の輪郭が存在するかどうかをチェックする。
【００４５】
照合（マッチング）の高速化のため、本発明による方法では画素位置構造１１０に関する、さらに他の２個のテーブル、すなわち、第４テーブル３１１（図３ｂ参照）および第５テーブル３１３を計算する。第４テーブル３１１は、輪郭画像１００全体におけるラインではなく、垂直区域３０１内の、最左端画素に関する第１テーブル１１１内での位置を示すインデックスを有する。同様に、第５テーブル３１３は、垂直区域３０１内における最右端画素の第１テーブル１１１内での位置を示すインデックスを有する。図３ａの実施例では、１個の輪郭しかなく、例示した垂直区域３０１内に輪郭がすべて含まれるため、輪郭画像１００の窓におけるこの水平方向走査位置に関しては、第２および第３のテーブルは、それぞれ第４、第５のテーブルと全く同一の値を有する。もし走査中に垂直区域３０１の右境界線３０５が物体輪郭の半分位置にくる場合（すなわち右に５画素、左に５画素存在する位置になった場合）、垂直区域３０１に関する第４テーブル３１１は図３ｂで示したものとなるが、第５テーブルは｛ＮａＮ，…，ＮａＮ，１，４，６，８，ＮａＮ，ＮａＮ，ＮａＮ｝となる。すなわち、これは、列１１上での最右端画素は第２番目に遭遇した画素であり、後続の列では、垂直区域３０１はこれら列上に１個の輪郭画素しか含んでいないために、最右端画素のインデックスは、最左端画素のインデックスと等しくなるからである。
【００４６】
第４テーブル３１１および第５テーブル３１３は、画像全体における重要画素に関する情報を示すテーブル、例えば第１テーブル１１１から簡単に構築できる。垂直区域３０１のある特定の列上の最左端画素は、垂直区域３０１の左境界線３０７における既知のｘ座標ＸＬに対して、ＸＬ以上で最小のｘ値を持つ第１テーブル内の画素のインデックスとして見いだすことができる。同様に、最右端画素は、垂直区域３０１の右境界線３０５におけるｘ座標ＸＲ以下で最大のｘ座標値をもつ画素のインデックスとなる。
【００４７】
しかし、第４、第５テーブルのような適切なインデックスは、第２、第３テーブルを用いればより早く見つけることができる。すなわち、例えば列１２に関して第２テーブル１１３（輪郭画像１００全体に関する）での最左端画素インデックスはインデックス４である。よって垂直区域３０１の最左端画素は４あるいはそれ以上のインデックス数しか持ちえず、同様に第３テーブル１１５の列１２のインデックスを調べると、輪郭画像１００全体において最右端画素は５よりも大きい数のインデックスは持ちえない。よって、第１テーブルの全エントリーをチェックする必要はなく、多くても列１２上にあるだけの画素、または他の注目する列をチェックするだけでよい。他にも、輪郭画像の列に沿う下方走査経路３０６を使えば、第４、第５テーブルを、注目領域３０３の各位置に対してではなく、各下方走査によりいちどに計算できるという利点がある。
【００４８】
画素位置構造１１０のテーブル内容を解析することにより、決定される輪郭画像１００内領域での照合（マッチング）をスキップ（省略）できうるところが、本発明による物体検出方法の高速化要因の一部である。第４テーブル３１１および第５テーブル３１３内のインデックスを用いて、各列の画素列の数は２つのインデックスの単純な減算によって計算できる。例えば、列１１に関して、第５テーブル３１３は３という最右端画素のインデックスを示し、第４テーブル３１１は０という最右端画素のインデックスを示しており、これは、垂直区域３０１内における列１１の全画素数は４であることを示している。したがって、注目領域３０３（マッチ関数により評価される、輪郭画像１０１内のテンプレート輪郭窓２００の現在位置）内にある全画素数は、注目領域３０３に含まれる各列において垂直区域３０１に含まれる画素数の総和をとることにより得られる。物体輪郭がテンプレート輪郭に照合（マッチング）して、輪郭画像１００内の注目領域３０３に対応する部分に存在する場合、注目領域３０３内に輪郭テンプレートの必要な画素総量のうち高いパーセンテージで存在していることになる。例えば、図６のテンプレートに関しては、もし２０％の非検出輪郭ポイントが許容される場合、少なくとも３２個の８０％にあたる２６個の画素が注目領域３０３に存在することになる。パーセンテージ−代表的には所定画素量として表される−は、輪郭照合（マッチ）を示す最小マッチ関数値に基づいて決まり、最小マッチ関数値は画像内のノイズ量、認識すべきテンプレート輪郭との数値および形状の差、許容されるかみ合わせの最大許容パーセンテージ、などの要因に左右される。画像処理において代表的な他の理論的解析方法を使用して、所定の画素量を得ることもできる。アルゴリズムの説明を分かり易くするため、必要なパーセンテージを１００％と仮定し、本発明による物体検出方法の高速化手法を、図６の曲りくねった形状の物体輪郭６００を用いて説明する。輪郭画像１００内におけるこの輪郭、したがって、テンプレートのほとんどの部分（２値テンプレートでは全画素が１、平滑に距離変換されたテンプレートでは通常最高のグレー値の画素）を、４×８の画素で構成する。注目領域３０３におけるある特定の垂直位置ｙRに関して、注目領域３０３の内部には８画素しか存在しないと仮定する。これはすなわち、３×８画素列の欠損があることを示す。垂直区域３０１の垂直方向走査を高速化するための第１の法則は以下のことを示している。垂直区域３０１内部の次の各列上には多くとも８個の画素が存在し得るため、注目領域３０３は少なくとも３列分下方向に移動しなければならない（最良ケース）。テンプレート輪郭６００の形状を観察すると言うまでもなく、それら２４個の余分の画素は特定ライン上に存在しなければならない。輪郭画像１００内の８画素の３列は、図６の輪郭６００に照合（マッチ）しない。したがって、マッチ関数評価をスキップ（省略）できる列数はより賢明に計算できる。輪郭６００の第１列６０１を形成する８画素列は、座標ｙRに位置する注目領域３０３の底辺の列に位置しており、注目領域３０３の上部の領域は輪郭６００の残りに存在する（もしポイントがマッチ関数により評価される領域外に位置している場合には、輪郭画像１００内の物体輪郭は所望のテンプレート輪郭６００ではないことを示すことになる）。パターンは第１列以下６列にわたって続いているため、注目領域３０３を６列分ジャンプさせ、第１列６０１が注目領域３０３の第１列に整列する状態にパターンを完全にオーバーラップさせる。
【００４９】
まとめると、２つの手法がある。
すなわち、注目領域３０３内の各垂直位置ｙRに関して、注目領域３０３内の総画素数をカウントし（３２０）、カウントした後、このカウントが照合すべきテンプレートに対して所定画素数よりも大きいか等しいときに、マッチ関数を評価する。
あるいは、（垂直区域３０１の幅とテンプレート輪郭の形状の両方またはいずれか一方を考慮にいれて）注目領域３０３内の現垂直位置ｙRにおける現カウント数と、所定画素量との差異に応じた相当数の列をスキップ（省略）する。
【００５０】
第１の手法では、現垂直位置ｙRにおける注目領域３０３内の総画素カウント数は、直上位置ｙR−１でのカウント数に新たな列のカウント数を加算し、これまでの列のうち最大カウント数を減算して求められる。すなわち次式の操作を行う。
Ｃ（ｙＲ）＝Ｃ（ｙＲ−１）＋ＣＬ（ｙＲ＋Ｈ−１）−ＣＬ（ｙＲ−１）    （４）
【００５１】
式（４）において、Cは注目領域３０３内の左上の画素（例えば、ｙR）である、特定の位置での注目領域３０３全領域での総カウント数、CLは１個の列のカウント数、Hは注目領域３０３の高さ、すなわちテンプレート輪郭窓２００（６００）の高さを示す。
【００５２】
言うまでもなく、不要輪郭画素が多数存在する場合、輪郭画像１００における注目領域３０３内にテンプレート輪郭位置上の位置をとる画素がない場合であっても、カウント数は所定画素量を超えてしまう。しかし、全領域は、明らかにテンプレート輪郭で検出する物体と異なる物体に属する微小な不要輪郭を含み、輪郭画像１００の大部分の空領域において、割高なマッチ関数の評価を行う代わりにスキップ（省略）する。
【００５３】
同様の理由で、多くの行の評価をスキップ（省略）する。例えば、もし図３ａにおいて、最初の８列に画素が全く存在しない場合、最初の垂直区域３０１の走査完了後に、注目領域３０３は他の８画素走査を開始する。一般的に、現在垂直区域の各列における画素総数に依存して、ジャンプする列数を指示する。例えば、上部の行に画素が全くないが、下部の行には画素がある、注目領域３０３のある特定の位置での総カウントが例えば４である場合を考える。この４個の画素は輪郭窓６００の第１列６０３に対応するパターン上に正確に位置していて、８列ではなく７列分ジャンプすることを指示する。ジャンプする実際の列数は、注目領域３０３の各垂直位置ｙＲに対してジャンプするよう指示した列数の最小値となる。（最悪のケースでは、非照合（マッチングしない）位置がはっきりきない場合、後半の走査中にすべてを検証しなければならない。）しかし言うまでもなく、水平方向の列ジャンプが僅かであるために予め処理しなければならない輪郭画像１００の頂部における空領域は、垂直方向のスキップによって迅速に移行する。
【００５４】
５個のテーブルの変化が非常に速くても、等価な画素位置構成１１０を構築できる。例えば、最初から３個のテーブルの代わりに、注目画素の（ｘ，ｙ）タプルから成る１個の（第６の）テーブルが構築される。この第６テーブルでは、連続する輪郭画像１００の列、すなわち、連続するｙ値に対応する連続するグループに（ｘ，ｙ）タプルを含ませる。上述の第４、第５テーブルは、２値探索基準を使用し、所望の行値ｙのタプルが第６テーブル内で検出されるまで探索を行うことで求められる。垂直区域３０１内の最左端、最右端画素の正確なインデックスは、第６テーブル内で昇順、または降順方向に、例えば、ＸＬ以上で最小ｘ値を持つタプルに遭遇するまでインデックスを移動させることによって求められる。
【００５５】
上述の２値ではなく、輪郭画像１００は０でも１でもない画素値、例えば図４に示すような０．５という値を含むこともある。このような輪郭画像を採用する理由は幾つか考えられるが、例えば以下の理由がある。すなわち、
‐輪郭画像が２個の異なるエッジ検出操作の結果として得られたものであり、２個の検出器がある特定の画素位置における輪郭エッジを検出した場合には値１を、エッジを検出した検出器が２個のうち１個であった場合には値０．５を示すようにしたとき。
‐または、画像が上述の距離変換を２値輪郭画像１００に適用することにより得られたものであるとき。
【００５６】
後者の例は幾つかの用途（アプリケーション）において有効である。マッチ関数はある閾値、例えば０．２や０以上の、輪郭画像１００における全ての画素値に対して評価する。閾値は、画素が重要かどうかを決める。テンプレートは２値または他の複数個値も持ちうる。２値テンプレートは記憶装置の観点からみると有利である。すなわち、多くの異なるテンプレートを記憶しチェックしなくてはならないとき（例えば、１個の物体形状が回転または縮尺（スケール）変更された場合）、テンプレート輪郭窓２００の画素値が２値ではなく整数か実数であるとすると、少ないメモリでは記憶するのに不十分となるからである。さらに、両者には実行するオペレーション数に差異があり、この差異もまた有用である。例えば、もしマッチングすべきテンプレートが２つの画素ラインセグメントである場合、２値テンプレートではただ２つの画素の比較のみが各評価位置で行われる（しかしながら距離変換された輪郭画像１００では、一般的により多くの範囲での評価が必要である）、一方で、距離変換されたテンプレートではより多くの比較を行わなければならない。２つのオプション−テンプレートまたは輪郭画像上の距離変換−のうちどちらがより経済的か、というのは、テンプレート形状そして輪郭画像１００に依存する、すなわち注目領域３０３の予想されるジャンプ距離に依存する。高速化はまた、動的決定アルゴリズムによっても実現できる。
【００５７】
プロセッサアーキテクチャのプロパティ（例えばＭＭＸといった１つの命令で複数のデータを扱う演算方式）を開発することによっても処理速度を高速化できる。テンプレート輪郭窓２００と同程度の幅を有する注目領域３０３を用いる代わりに、注目領域３０３を、例えば８画素分広くする。このとき、８列を並列的にマッチングテンプレートによりチェックできる。この場合、水平方向の最小移動は８行となる最小水平方向ジャンプは８列となる。
【００５８】
異なるサイズ、回転、または微小透視図的変換された物体輪郭を照合（マッチング）しなければならない場合、輪郭テンプレートマッチング手法では、通常、特定のサイズ、向き等他の異なる組合せのそれぞれに対して、多数のテンプレート輪郭窓２００を使用する。このことは、すなわち、極めて多数のテンプレートを記憶しなければならず、大きいメモリ、および照合（マッチング）に使用すべきそれぞれのテンプレートを必要とすることを意味する。本発明の図示の実施例によれば、幾何学的変換（例えば回転）に関連する輪郭を効率的にマッチングするために、これら全テンプレートのうち１個のサブセットのみを記憶するだけである。図５は回転の場合における本原理の説明図である。向き変化の各度合いに対応する異なるテンプレートを記憶している場合、大部分のテンプレートに大きな差異はなく、ただ回転の両極限位置においてのみテンプレート輪郭窓２００の値が大きく変化する。そこで、例えば基準向きに対して１０゜毎の各回転に対して１個のテンプレート輪郭窓２００を用意する。中間の向き−例えば９゜の向き−を持つテンプレート５０３は、近傍のテンプレート輪郭５０１（例えば、中間向きの向き角度より小さい最大向き角度、例えば、図５におけるゼロ度で記憶したテンプレート輪郭）の画素値と、テンプレート輪郭５０１の対象画素値と同位置にある画素ではなく、変換から計算されるオフセット位置（ｄｘ、ｄｙ）での輪郭画像１００の画素とを比較することにより照合（マッチング）を行うことができる。同様の結果は、輪郭画像１００の代わりに、テンプレート輪郭窓２００におけるオフセット位置に注目することによっても得られるが、この場合テンプレート輪郭窓２００は通常より大きいものとし、さらに、距離変換によって長い距離に対しては非ゼロの画素値が生成される可能性がある。例えば、輪郭画像１００のどの画素が図５の例にマッチするかを示すオフセット位置（ｄｘ、ｄｙ）は、
ｄｘ＝ｒ［ｃｏｓ（α＋β）−ｃｏｓ（α）］    
ｄｙ＝ｒ［ｓｉｎ（α＋β）−ｓｉｎ（α）］    （５）
となる。
【００５９】
式（５）において、ｒは回転原点までの距離を表し、αはテンプレート輪郭窓２００における画素の垂直ラインが見込む角度、βは中間向きと近傍テンプレート輪郭５０１の向きとの差である。異なるテンプレートのオフセットはあらかじめ計算し、参照用（ルックアップ）テーブルに記憶しておく。オーバーラップ誤差は距離変換により補償し、すなわち、照合（マッチング）するように形状類似性をトレードオフする。２次サンプリングした向き（この場合全幾何的変形の２次的サンプリングした組）によるマッチングは、より正確な向き、サイズ、その他の情報をすでにおおまかに示唆しているため、処理速度が向上する。このようにして、高速探索技術を使用できる。
【００６０】
他の実施の形態では、照合（マッチング）は一般的には、例えばガウスフィルタを用いてまず平滑化された後に、二次サンプリングした輪郭画像１００に対して行う。または、縮尺（スケール）変換した空間において階層的照合（マッチング）を使用する。精細化手法、または多段階照合（マッチング）手法もまた可能である。例えば、物体は、小さなフックまたはノッチの存在に関して異なる。第１段階で物体の位置を突き止め、第２段階で予想される位置でフックの存在を検証する。
【００６１】
図７は、物体輪郭画像１００を解析する画像処理装置７３１を示す。第１ユニット７２１は、注目領域３０３における輪郭イメージ１００内の走査（スキャン）経路３０６上のある特定の位置（ｘＲ、ｙＲ）を特定するためのもので、例えば上述したように、輪郭画像１００の列に沿った連続位置を生成する。この位置情報（上述の実施例においては、走査すべき、現在の列における少なくとも１個のｙ座標）を第２ユニット７２３に送る構成とする。この第２ユニットは、第１テーブル１１１、第４テーブル３１１、第５テーブル３１３、そして上述の方法に対応した実現化要求があれば、第２テーブル１１３および第３テーブル１１５を構築するよう構成する。第２ユニット７２３をメモリ７１５に接続し、テーブルをメモリ７１５に記憶するよう構成する。メモリは通常はメモリチップであるが、ディスケットのような着脱可能なメモリ、またはネットワークを介して接続した遠隔装置におけるメモリとすることができ、したがって、生成したテーブルは、他の処理用に別個の画像処理装置にも使用できる。
【００６２】
物体検出のための画像処理装置７３２は、さらに、上述したように注目領域３０３内の画素とテンプレート輪郭窓２００内の画素を引数とするマッチ関数を評価するための照合（マッチング）ユニット７２７を有し、この照合ユニット７２７は、照合（マッチング）の結果を保存するためのメモリへのアクセス機能を有する。決定ユニット７２５は、走査経路３０６に沿う現在位置もしくは現在の注目領域３０３にアクセスし、またメモリ７１５にアクセスする。決定ユニット７２５は、上述した１つのまたはそれ以上の方法によって、注目領域３０３内部の非ゼロ値画素の数であるカウント３２０を計算する。カウントの値に基づいて、第１ユニット７２１に対して走査経路３０６上での次の位置へジャンプ、例えば、１個の画素分または１個以上の画素分だけ下方にジャンプするよう指示するか、また照合（マッチング）ユニット７２７に対して注目領域３０３の現在位置においてマッチ関数を評価するよう指示する。
【００６３】
輪郭生成ユニット７１１はグレー値画素またはカラー画素の画像から、または数学的にもしくは他の方法で生成した画像から、輪郭画像１００を生成するよう構成する。代表的な用途では、画像はカメラ７０１から得る。
【００６４】
制御ユニットは画像処理装置７３２によって得られた物体輪郭照合結果に基づいて、他の関数を評価し、少なくとも１つの信号Ｓを導き出すよう構成する。この信号Ｓは、例えば、検出される物体をピックアップするように指示さるロボットなどに出力する。セキュリティシステムにおいては、検出される物体は、例えば車両ライセンスプレートとすることができ、信号をバリアまたは警報機に出力する。
【００６５】
例えば画像処理装置７３１のような全ての処理コンポーネントは、例えばＡＳＩＣ、ＦＰＧＡもしくは専用回路ボードといったハードウェアにより、または専用もしくは汎用のプロセッサ上で動作するソフトウェアにより実現できる。図示のユニットは複数個のもしくは単独の物理的デバイスにより実現できる。
【００６６】
図７に例示した用途は、製造ライン監視である。物体７０３、７０４はコンベヤーベルト７０５上に沿って移動している。画像処理装置７３２は、例えば回路上にコンポーネントがきれいにはんだ付けされているか否かをチェックする。
【００６７】
画像処理装置７３２はまたスマートカメラにも搭載されるすることができ、画像処理装置は、例えば検出した物体に基づいて色修正やレンズゆがみ補正、画像内の物体のみの補正、といった変換を加えるよう構成する。他の用途としては、ヨーロッパ特許出願第０２０７９８１６．１号に記載のように、このようなスマートカメラを有する遠隔制御がある。
【００６８】
より消費者に関連した装置としては、受信した画像を処理できるディスプレイを有するテレビもしくはコンピュータがある。例えば、ロゴもしくはサブタイトルを、テレビジョン信号内で変換する。
【００６９】
コンピュータプログラム製品の下で、（汎用もしくは専用の）プロセッサに対して一連のローディングステップ後に命令を与え、本発明の特徴的な機能のいずれかを実行させることができる命令の集合を物理的に実現できると理解されたい。特に、コンピュータプログラム製品は、ディスクもしくはテープ、メモリ内に存在するデータ、有線または無線のネットワーク上を行き来するデータ、または紙上のプログラムコードといったキャリア上のデータとして実現される。プログラムコードとは別に、プログラムに必要な特定データをコンピュータプログラム製品として埋め込むこともできる。
【００７０】
これまでに言及した実施例は本発明を限定するものではないことに注意されたい。請求項内で組み合わされたような発明の要素の組合せ以外に、他の要素の組合せも可能である。特定の目的のための１個の要素内でもあらゆる要素の組合せが可能である。
【００７１】
請求項内の括弧間のどの参照符号も請求の範囲を制限することを意図していない。「備える」という言葉は請求項で記載されていない要素や見解を排除するものではない。要素の前の「ａ」や「ａｎ」という単語はこのような要素が複数存在することを排除するものではない。
【００７２】
本発明は、ハードウェア、またはプロセッサ上で動作するソフトウェアにより実施できる。
【図面の簡単な説明】
【００７３】
【図１ａ】簡単な輪郭画像を示す線図的説明図である。
【図１ｂ】本発明による注目画素に関するテーブルである。
【図２】輪郭窓テンプレートを示す線図的説明図である。
【図３ａ】輪郭画像に沿って注目領域を走査する状況を示す線図的説明図である。
【図３ｂ】本発明による注目画素に関する他のテーブルである。
【図３ｃ】図３ａに示す注目領域の位置の画素カウントである。
【図４】０または１以外の値を有する輪郭画像を示す線図的説明図である。
【図５】基準テンプレートに関連するテンプレートを回転させてマッチングするときの輪郭画像における対応画素をフェッチするためのオフセットを示す線図的説明図である。
【図６】輪郭テンプレートの線図的説明図である。
【図７】ある用途における画像処理装置を示す線図的説明図である。
【図１ａ】
2007508633.tif 000005
【図１ｂ】
2007508633.tif 000006
【図２】
2007508633.tif 000007
【図３ａ】
2007508633.tif 000008
【図３ｂ】
2007508633.tif 000009
【図３ｃ】
2007508633.tif 000010
【図４】
2007508633.tif 000011
【図５】
2007508633.tif 000012
【図６】
2007508633.tif 000013
【図７】
2007508633.tif 000014
【国際調査報告】
2007508633.tif 000015
2007508633.tif 000016