(57)【要約】【課題】一般にはマシンビジョン、特に物体認識における自動パラメータ決定のシステムおよび方法を提供する。【解決手段】多くのマシンビジョンシステムは、現在のアプリケーションに依存するアルゴリズムの挙動に適応するために、１以上のパラメータを指定するようにユーザに要求するアルゴリズムを使用する。イメージ内の物体のコントラストを自動的に決定する方法は、物体の電子イメージを提供するステップ、前記物体のエッジ振幅を識別するステップ１０２、前記エッジ振幅に適用される閾値の範囲に関する前記物体のエッジ領域を識別するステップ１０６、より高い評価結果がよりよい評価を示す、閾値の前記範囲について得られる前記エッジ領域を評価するステップ１０８、最大エッジ領域値に対応する最適閾値を決定するステップ１１２、前記物体の前記コントラストを表す、最大エッジ領域値に対応する前記最適閾値を提供するステップ１１６を含む。【選択図】図２
2007257601.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）前記物体の電子イメージを提供するステップと、
（ｂ）前記物体のエッジ振幅を識別するステップと、
（ｃ）前記エッジ振幅に適用される閾値の範囲に関する前記物体のエッジ領域を識別するステップと、
（ｄ）より高い評価結果がよりよい評価を示す、閾値の前記範囲について得られる前記エッジ領域を評価するステップと、
（ｅ）最大エッジ領域値に対応する最適閾値を決定するステップと、
（ｆ）前記物体の前記コントラストを表す、前記最大エッジ領域値に対応する前記最適閾値を提供するステップと、
を含むイメージ内の物体のコントラストを自動的に決定する方法。
【請求項２】
ステップ（ｄ）は、物体エッジの平均負曲率を識別するステップを含む、請求項１に記載の方法。
【請求項３】
ステップ（ｄ）は、
（ｄ１）８接続されているエッジ画素を識別するステップと、
（ｄ２）強い曲率のエッジ画素を決定するステップと、
（ｄ３）差領域を形成するために前記エッジ領域から強い曲率の前記エッジ画素を削除するステップと、
（ｄ４）前記差領域の接続された成分を識別するステップと、
（ｄ５）前記エッジ領域値を識別するために前記接続された成分の平均長を提供するステップと、
を含む、請求項１に記載の方法。
【請求項４】
ステップ（ｄ２）は、フィルタマスクを使用して前記エッジ画素に４つの侵食を適用するステップを含む、請求項３に記載の方法。
【請求項５】
ステップ（ｃ）は、前記エッジ振幅にヒステリシス閾値を適用することによってより低いヒステリシス閾値およびより高いヒステリシス閾値の組合せに関してエッジ領域を識別するステップを含み、ステップ（ｆ）が、前記物体の前記コントラストを決定するために前記エッジ領域値の最大値に対応する前記ヒステリシス閾値を提供するステップを含む、請求項１に記載の方法。
【請求項６】
ステップ（ｆ）は、
（ｆ１）低ヒステリシス閾値および高ヒステリシス閾値を、ステップ（ｅ）から得られた前記エッジ領域値の最大値に対応する前記閾値に初期化するステップと、
（ｆ２）前記高ヒステリシス閾値を連続して増分し、前記低ヒステリシス閾値および前記高ヒステリシス閾値を前記エッジ振幅に適用することによって前記エッジ領域値を識別するステップと、
（ｆ３）増分された高閾値ごとに得られる前記エッジ領域値を決定するステップと、
（ｆ４）前記エッジ領域値が最高の得られた値のある比率未満に減るまでステップ（ｆ２）から（ｆ３）を繰り返すステップと、
（ｆ５）前記低ヒステリシス閾値を連続して減分し、前記低ヒステリシス閾値および前記高ヒステリシス閾値を前記エッジ振幅に適用することによって前記エッジ領域値を識別するステップと、
（ｆ６）減分された低閾値ごとに得られる前記エッジ領域値を決定するステップと、
（ｆ７）前記エッジ領域値が最高の得られた値のある比率未満に減るまでステップ（ｆ５）から（ｆ６）を繰り返すステップと、
（ｆ８）前記物体の前記コントラストを表す最適の低ヒステリシス閾値および高ヒステリシス閾値を提供するステップと、
によって置換される、請求項１に記載の方法。
【請求項７】
前記最小コントラストは、自動的に決定され、
（ｇ）イメージ雑音の標準偏差を推定するステップと、
（ｈ）前記推定された標準偏差に所定の係数をかけることによって最小エッジ振幅を決定するステップと、
（ｉ）前記最小コントラストとして前記最小エッジ振幅を使用するステップと、
を含む、請求項１に記載の方法。
【請求項８】
（ａ）物体の電子イメージを提供するステップと、
（ｂ）前記イメージのエッジ振幅を識別するステップと、
（ｃ）閾値を前記エッジ振幅に適用することによって前記物体のエッジ領域を識別するステップと、
（ｄ）前記エッジ領域の接続された成分を識別し、成分の長さを決定するステップと、
（ｅ）前記成分の長さの累積ヒストグラムを識別するステップと、
（ｆ）事前定義の比率を超えるヒストグラムビンを識別するステップと、
（ｇ）物体部分の前記最小サイズを表す、前記ヒストグラムビンに関連するエッジ長さを提供するステップと、
を含む物体部分の最小サイズを自動的に決定する方法。
【請求項９】
ステップ（ｃ）で、前記閾値が、請求項１に記載の方法を使用して自動的に得られる、請求項８に記載の方法。
【請求項１０】
（ａ）物体の電子イメージを提供するステップと、
（ｂ）前記イメージのエッジ振幅を識別するステップと、
（ｃ）閾値を前記エッジ振幅に適用することによって前記物体のエッジ領域を識別するステップと、
（ｄ）所定の堅牢さおよび精度を達成するのに少なくとも必要なモデル点の最適個数を識別するステップと、
（ｅ）ステップ（ｄ）で決定されたモデル点の前記最適個数が残されるように、モデル点のうちの個々の分数を除去するステップと、
を含むモデル点の個数に関する削減要因を自動的に決定する方法。
【請求項１１】
ステップ（ｃ）において、前記閾値が、請求項１に記載の方法を使用して自動的に得られる、請求項１０に記載の方法。
【請求項１２】
ステップ（ｄ）で決定されたモデル点の前記最適個数が、現在の物体に基づき、
（ｄ１）前記物体の少なくとも１つの電子テストイメージを提供するステップと、
（ｄ２）テストイメージごとに、認識されなければならない物体実例の個数を提供するステップと、
（ｄ３）所望の認識手法を使用する前記物体のモデル表現を提供するステップと、
（ｄ４）前記モデル表現および前記所望の認識手法を使用して各テストイメージ内の前記物体を認識し、すべてのテストイメージにわたる平均認識時間を決定するステップと、
（ｄ５）モデル点の個数を所定の係数だけ減らすステップと、
（ｄ６）前記平均認識時間が増えない限り、かつステップ（ｄ２）で提供された前記個数の物体実例が各テストイメージ内で見つかる限り、ステップ（ｄ４）から（ｄ５）を繰り返すステップと、
（ｄ７）ステップ（ｄ２）で提供された前記個数の物体実例が見つかり、前記平均認識時間が最小である、モデル点の最適個数を使用するステップと、
を含む、請求項１０に記載の方法。
【請求項１３】
ステップ（ｄ１）〜（ｄ７）で決定されたモデル点の前記最適個数が、多数の物体についてステップ（ｄ１）から（ｄ７）を繰り返し、モデル点の最適個数の平均値を提供することによって、前記現在の物体と独立である、請求項１２に記載の方法。
【請求項１４】
（ａ）物体の電子イメージを提供するステップと、
（ｂ）前記物体のサイズに基づいて前記離散化ステップ長の初期値を提供するステップと、
（ｃ）現在の離散化ステップ長に関連する最小類似性測度を識別するステップと、
（ｄ）結果の離散化ステップ長を決定するために、関連する最小類似性測度がある閾値を超えるまで、前記離散化ステップ長を半分にするステップと、
（ｅ）物体認識のモデル変換を決定するために、前記結果の離散化ステップ長を使用するステップと、
を含むモデル点の組を含む物体モデルの離散化ステップ長を自動的に決定する方法。
【請求項１５】
ステップ（ｂ）は、
（ｂ１）前記変換の固定点からの前記モデル点の最大距離を計算するステップと、
（ｂ２）最大の許容される画素変位を仮定するステップと、
（ｂ３）前記最大距離および前記許容される画素変位に基づいて前記離散化ステップ長の前記初期値を計算するステップと、
を含む、請求項１４に記載の方法。
【請求項１６】
ステップ（ｃ）の前記最小類似性測度は、変換されない物体モデルと、前記離散化ステップ長の半分だけ変換されたモデルイメージとの間の類似性測度に対応する、請求項１４に記載の方法。
【請求項１７】
（ａ）物体の電子イメージを提供するステップと、
（ｂ）現在のステップ長を０に初期化するステップと、
（ｃ）十分に小さい値だけ前記現在のステップ長を増分するステップと、
（ｄ）変換されないモデルと前記現在のステップ長に従って変換されたモデルイメージとの間の類似性測度を識別するステップと、
（ｅ）前記類似性測度がある閾値未満になるまで前記ステップ（ｃ）および（ｄ）を繰り返すステップと、
（ｆ）前記類似性測度が前記閾値を超える最後のステップ長の２倍として最適ステップ長を提供するステップと、
を含む物体モデルの離散化ステップ長を自動的に決定する方法。
【請求項１８】
（ａ）前記物体の電子イメージを提供する手段と、
（ｂ）前記物体のエッジ振幅を識別する手段と、
（ｃ）前記エッジ振幅に適用される閾値の範囲に関する前記物体のエッジ領域を識別する手段と、
（ｄ）より高い評価結果がよりよい評価を示す、閾値の前記範囲について得られる前記エッジ領域を評価する手段と、
（ｅ）最大エッジ領域値に対応する最適閾値を決定する手段と、
（ｆ）前記物体の前記コントラストを表す、前記最大エッジ領域値に対応する前記最適閾値を提供する手段と、
を含むイメージ内の物体のコントラストを自動的に決定するデータ処理システム。
【請求項１９】
（ａ）物体の電子イメージを提供する手段と、
（ｂ）前記イメージのエッジ振幅を識別する手段と、
（ｃ）自動的に得られた閾値を使用することによって前記物体のエッジ領域を識別する手段と、
（ｄ）前記エッジ領域の接続された成分を識別し、成分の長さを決定する手段と、
（ｅ）前記成分の長さの累積ヒストグラムを識別する手段と、
（ｆ）事前定義の比率を超えるヒストグラムビンを識別する手段と、
（ｇ）物体部分の前記最小サイズを表す、前記ヒストグラムビンに関連するエッジ長さを提供する手段と、
を含む物体部分の最小サイズを自動的に決定するデータ処理システム。
【請求項２０】
（ａ）物体の電子イメージを提供する手段と、
（ｂ）前記イメージのエッジ振幅を識別する手段と、
（ｃ）自動的に得られた閾値を適用することによって前記物体のエッジ領域を識別する手段と、
（ｄ）所定の堅牢さおよび精度を達成するのに少なくとも必要なモデル点の最適個数を識別する手段と、
（ｅ）手段（ｄ）によって決定されたモデル点の前記最適個数が残されるように、モデル点のうちの個々の分数を除去する手段と
を含むモデル点の個数に関する削減要因を自動的に決定するデータ処理システム。
【請求項２１】
（ａ）物体の電子イメージを提供する手段と、
（ｂ）前記物体のサイズに基づいて前記離散化ステップ長の初期値を提供する手段と、
（ｃ）現在の離散化ステップ長に関連する最小類似性測度を識別する手段と、
（ｄ）結果の離散化ステップ長を決定するために、関連する最小類似性測度がある閾値を超えるまで、前記離散化ステップ長を半分にする手段と、
（ｅ）物体認識のモデル変換を決定するために、前記結果の離散化ステップ長を使用する手段と、
を含む物体モデルの離散化ステップ長を自動的に決定するデータ処理システム。
【請求項２２】
（ａ）前記物体の電子イメージを提供するステップと、
（ｂ）前記物体のエッジ振幅を識別するステップと、
（ｃ）前記エッジ振幅に適用される閾値の範囲に関する前記物体のエッジ領域を識別するステップと、
（ｄ）閾値の前記範囲について得られる前記エッジ領域を評価するステップであって、より高い評価結果がよりよい評価を示すステップと、
（ｅ）最大エッジ領域値に対応する最適閾値を決定するステップと、
（ｆ）前記物体の前記コントラストを表す、前記最大エッジ領域値に対応する前記最適閾値を提供するステップと、
を含む、イメージ内の物体のコントラストを決定するプログラム命令を含むデータ記憶媒体。
【請求項２３】
物体部分の最小サイズを自動的に決定するプログラム命令を含むデータ記憶媒体であって、プログラムステップが、
（ａ）前記物体の電子イメージを提供するステップと、
（ｂ）前記イメージのエッジ振幅を識別するステップと、
（ｃ）自動的に得られた閾値を使用することによって前記物体のエッジ領域を識別するステップと、
（ｄ）前記エッジ領域の接続された成分を識別し、成分の長さを決定するステップと、
（ｅ）前記成分の長さの累積ヒストグラムを識別するステップと、
（ｆ）事前定義の比率を超えるヒストグラムビンを識別するステップと、
（ｇ）物体部分の前記最小サイズを表す、前記ヒストグラムビンに関連するエッジ長さを提供するステップと、
を含む、データ記憶媒体。
【請求項２４】
モデル点の個数に関する削減要因を自動的に決定するプログラム命令を含むデータ記憶媒体であって、プログラムステップが、
（ａ）物体の電子イメージを提供するステップと、
（ｂ）前記イメージのエッジ振幅を識別するステップと、
（ｃ）自動的に得られた閾値を適用することによって前記物体のエッジ領域を識別するステップと、
（ｄ）所定の堅牢さおよび精度を達成するのに少なくとも必要なモデル点の最適個数を識別するステップと、
（ｅ）ステップ（ｄ）で決定されたモデル点の前記最適個数が残されるように、モデル点のうちの個々の分数を除去するステップと、
を含む、データ記憶媒体。
【請求項２５】
物体モデルの離散化ステップ長を自動的に決定するプログラム命令を含むデータ記憶媒体であって、プログラムステップが、
（ａ）物体の電子イメージを提供するステップと、
（ｂ）前記物体のサイズに基づいて前記離散化ステップ長の初期値を提供するステップと、
（ｃ）現在の離散化ステップ長に関連する最小類似性測度を識別するステップと、
（ｄ）結果の離散化ステップ長を決定するために、関連する最小類似性測度がある閾値を超えるまで、前記離散化ステップ長を半分にするステップと、
（ｅ）物体認識のモデル変換を決定するために、前記結果の離散化ステップ長を使用するステップと、
を含むデータ記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的にはマシンビジョンシステムに関し、具体的には、物体の視覚認識に関する。
【背景技術】
【０００２】
物体認識は、多くのコンピュータビジョンアプリケーションの一部である。これは、しばしば物体のイメージを物体のモデルと位置合せしなければならない産業検査作業に特に有用である。物体認識プロセスから得られる変換（ポーズ）を、さまざまな作業、たとえばロボット制御、ピックアンドプレース動作、品質制御、または検査などの作業に使用することができる。ほとんどの場合に、物体のモデルは、物体のイメージから生成される。さらに、しばしば、モデル生成プロセスが、ユーザによって指定されなければならないパラメータの組によって影響を受ける可能性がある。自動化の度合を高め、認識システムの使いやすさを改善するためには、これらのパラメータを自動的に決定することが非常に望ましい。
【非特許文献１】Ｌｉｓａ  Ｇｏｔｔｅｓｆｅｌｄ  Ｂｒｏｗｎ、「Ａ  ｓｕｒｖｅｙ  ｏｆ  ｉｍａｇｅ  ｒｅｇｉｓｔｒａｔｉｏｎ  ｔｅｃｈｎｉｑｕｅｓ（画像記録技術の探査）」、ＡＣＭ  Ｃｏｍｐｕｔｉｎｇ  Ｓｕｒｖｅｙｓ（ＡＣＭコンピューティング探査）、２４（４）：３２５〜３７６ページ、１９９２年１２月
【非特許文献２】Ｗｉｌｌｉａｍ  Ｊ．Ｒｕｃｋｌｉｄｇｅ、「Ｅｆｆｉｃｉｅｎｔｌｙ  ｌｏｃａｔｉｎｇ  ｏｂｊｅｃｔｓ  ｕｓｉｎｇ  ｔｈｅ  Ｈａｕｓｄｏｒｆｆ  ｄｉｓｔａｎｃｅ（ハウスドロフ距離を使用して物体を効果的に配置する）」、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ、２４（３）：２５１〜２７０ページ、１９９７年
【特許文献１】米国特許第６００５９７８号
【特許文献２】欧州特許第ＥＰ−Ａ−１１９３６４２号
【非特許文献３】Ｍａｒｋｕｓ  Ｕｌｒｉｃｈ、Ｃａｒｓｔｅｎ  Ｓｔｅｇｅｒ、Ａｌｂｅｒｔ  Ｂａｕｍｇａｒｔｎｅｒ、「Ｒｅａｌ−ｔｉｍｅ  ｏｂｊｅｃｔ  ｒｅｃｏｇｎｉｔｉｏｎ  ｕｓｉｎｇ  ａ  ｍｏｄｉｆｉｅｄ  ｇｅｎｅｒａｌｉｚｅｄ  Ｈｏｕｇｈ  ｔｒａｎｓｆｏｒｍ（修正され一般化されたハフ変換を用いる実時間物体認識）」、Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ、３６（１１）：２５５７〜２５７０ページ、２００３年
【非特許文献４】Ｇｕｎｉｌｌａ  Ｂｏｒｇｅｆｏｒｓ、「Ｈｉｅｒａｒｃｈｉｃａｌ  ｃｈａｍｆｅｒ  ｍａｔｃｈｉｎｇ（階層マッチング）：Ａ  ｐａｒａｍｅｔｒｉｃ  ｅｄｇｅ  ｍａｔｃｈｉｎｇ  ａｌｇｏｒｉｔｈｍ（パラメトリックエッジ・マッチングアルゴリズム）」、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ、１０（６）：８４９〜８６５ページ、１９８８年１１月、
【非特許文献５】Ｊ．Ｃａｎｎｙ、「Ｆｉｎｄｉｎｇ  Ｅｄｇｅｓ  ａｎｄ  Ｌｉｎｅｓ  ｉｎ  Ｉｍａｇｅｓ（画像におけるエッジおよびラインを探査）」：Ｒｅｐｏｒｔ、ＡＩ−ＴＲ−７２０、Ｍ．Ｉ．Ｔ．Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  Ｌａｂ．、米国マサチューセッツ州ケンブリッジ、１９８３年
【非特許文献６】Ｓｔｅｖｅｎ  Ｌ．Ｔａｎｉｍｏｔｏ、「Ｔｅｍｐｌａｔｅ  ｍａｔｃｈｉｎｇ  ｉｎ  ｐｙｒａｍｉｄｓ（ピラミッドにおけるテンプレートマッチング）」、Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ  ａｎｄ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ、１６：３５６〜３６９ページ、１９８１年、
【非特許文献７】Ｒａｆａｅｌ  Ｃ．Ｇｏｎｚａｌｅｓ、Ｒｉｃｈａｒｄ  Ｅ．Ｗｏｏｄｓ、「Ｄｉｇｉｔａｌ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ（デジタル画像処理）」、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏｍｐａｎｙ、１９９２年
【非特許文献８】Ｃａｎｎｙ（１９８３年）、Ｕ．Ｅｃｋａｒｄｔ、Ｖｅｒｄｕｎｎｕｎｇ  ｍｉｔ  Ｐｅｒｆｅｋｔｅｎ  Ｐｕｎｋｔｅｎ、Ｐｒｏｃｅｅｄｉｎｇｓ  １０．  ＤＡＧＭ−Ｓｙｍｐｏｓｉｕｍ、ＩＦＢ  １８０、Ｚｕｒｉｃｈ、１９８８年
【非特許文献９】Ｗ．Ｆｏｒｓｔｎｅｒ、「Ｉｍａｇｅ  Ｐｒｅｐｒｏｃｅｓｓｉｎｇ  ｆｏｒ  Ｆｅａｔｕｒｅ  Ｅｘｔｒａｃｔｉｏｎ  ｉｎ  Ｄｉｇｉｔａｌ  Ｉｎｔｅｎｓｉｔｙ，Ｃｏｌｏｒ  ａｎｄ  Ｒａｎｇｅ  Ｉｍａｇｅｓ（デジタル輝度、色および範囲イメージ）」、Ｓｐｒｉｎｇｅｒ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｏｎ  Ｅａｒｔｈ  Ｓｃｉｅｎｃｅｓ、Ｓｕｍｍｅｒ  Ｓｃｈｏｏｌ  ｏｎ  Ｄａｔａ  Ａｎａｌｙｓｉｓ  ａｎｄ  ｔｈｅ  Ｓｔａｔｉｓｔｉｃａｌ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｇｅｏｍａｔｉｃｓ、１９９９年
【非特許文献１０】Ｊ．Ｉｍｍｅｒｋａｅｒ、「Ｆａｓｔ  Ｎｏｉｓｅ  Ｖａｒｉａｎｃｅ  Ｅｓｔｉｍａｔｉｏｎ（高速雑音変化評価）」、Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｉｍａｇｅ  Ｕｎｄｅｒｓｔａｎｄｉｎｇ、６４（２）、３００〜３０２ページ、１９９６年
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、全般的にはマシンビジョン、具体的には物体認識における自動パラメータ決定の方法を提供する。多くのマシンビジョンシステムが、現在のアプリケーションに依存するアルゴリズムの挙動に適応するために、１つまたは複数のパラメータを指定するようにユーザに要求するアルゴリズムを使用する（たとえば、Ｌｉｓａ  Ｇｏｔｔｅｓｆｅｌｄ  Ｂｒｏｗｎ、「Ａ  ｓｕｒｖｅｙ  ｏｆ  ｉｍａｇｅ  ｒｅｇｉｓｔｒａｔｉｏｎ  ｔｅｃｈｎｉｑｕｅｓ（画像記録技術の探査）」、ＡＣＭ  Ｃｏｍｐｕｔｉｎｇ  Ｓｕｒｖｅｙｓ、２４（４）：３２５〜３７６ページ、１９９２年１２月、Ｗｉｌｌｉａｍ  Ｊ．Ｒｕｃｋｌｉｄｇｅ、「Ｅｆｆｉｃｉｅｎｔｌｙ  ｌｏｃａｔｉｎｇ  ｏｂｊｅｃｔｓ  ｕｓｉｎｇ  ｔｈｅ  Ｈａｕｓｄｏｒｆｆ  ｄｉｓｔａｎｃｅ（ハウスドロフ距離を使用して物体を効果的に配置する）」、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ、２４（３）：２５１〜２７０ページ、１９９７年、米国特許第６００５９７８号、欧州特許第ＥＰ−Ａ−１１９３６４２号、およびＭａｒｋｕｓ  Ｕｌｒｉｃｈ、Ｃａｒｓｔｅｎ  Ｓｔｅｇｅｒ、Ａｌｂｅｒｔ  Ｂａｕｍｇａｒｔｎｅｒ、「Ｒｅａｌ−ｔｉｍｅ  ｏｂｊｅｃｔ  ｒｅｃｏｇｎｉｔｉｏｎ  ｕｓｉｎｇ  ａ  ｍｏｄｉｆｉｅｄ  ｇｅｎｅｒａｌｉｚｅｄ  Ｈｏｕｇｈ  ｔｒａｎｓｆｏｒｍ（修正され一般化されたハフ変換を用いる実時間物体認識）」、Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ、３６（１１）：２５５７〜２５７０ページ、２００３年を参照されたい）。これは、複数の理由から望ましくない。第１に、ユーザが、妥当なパラメータ値を選択できるために、アルゴリズムの機能性に関する詳細を知らなければならない。しかし、多くの場合に、アルゴリズムの複雑さは、専門家以外でもシステムを簡単に操作できることを保証するために、ユーザから隠蔽されなければならない。第２に、入力パラメータの個数が増えたならば、多くの場合に、専門家であってもパラメータの組の最適値を見つけることがむずかしくなる。これは、パラメータの一部が相互作用する場合があり、あるいは、結果に対する一部のパラメータの影響を明確に予測できないからである。その結果、ユーザは、最適値を見つけるために異なる組合せを試さなければならず、これは、ユーザが１つまたは２つを超える入力パラメータを指定することを必要とするシステムを扱う時には実現可能でない。アルゴリズムのパラメータ値の自動決定のもう１つの理由は、その柔軟性を高めることである。たとえば、産業界で、生産プロセスは、しばしば、条件変更を必要とし、新しい条件によるパラメータの適合を必要とする。したがって、時間のかかる手動適合は、生産プロセスの中断を防ぐために回避されなければならない。本発明は、入力イメージ自体だけに基づいて、マシンビジョンの最も頻繁に使用されるパラメータを自動的に決定する方法を提供する。この方法を、一例として物体認識システム（たとえば、欧州特許第ＥＰ−Ａ−１１９３６４２号、Ｕｌｒｉｃｈ他（２００３年））を使用して詳細に説明する。具体的には、物体のモデルイメージに基づくモデル生成プロセスを説明する。しかし、たとえばエッジ抽出��ルゴリズムを使用する他のシステムも、本発明から利益を得ることができる。その結果、次の説明は、例示的にすぎず、本発明の範囲を制限するものと解釈されてはならない。
【０００４】
本発明のさまざまな態様による方法に、次のパラメータの決定が含まれる。
【０００５】
・イメージ内の物体のコントラスト。多くの物体認識システムでは、物体が、そのエッジによって記述される（たとえば、Ｇｕｎｉｌｌａ  Ｂｏｒｇｅｆｏｒｓ、「Ｈｉｅｒａｒｃｈｉｃａｌ  ｃｈａｍｆｅｒ  ｍａｔｃｈｉｎｇ（階層食いつき部マッチング）：Ａ  ｐａｒａｍｅｔｒｉｃ  ｅｄｇｅ  ｍａｔｃｈｉｎｇ  ａｌｇｏｒｉｔｈｍ」、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ、１０（６）：８４９〜８６５ページ、１９８８年１１月、Ｒｕｃｋｌｉｄｇｅ（１９９７年）、米国特許第６００５９７８号、欧州特許第ＥＰ−Ａ−１１９３６４２号、Ｕｌｒｉｃｈ他（２００３年））。コントラストパラメータの決定は、モデルイメージ内でエッジ振幅の最適閾値を見つけることに対応する。最適値は、物体のすべての重要な特有の詳細が閾値を超えるが、雑音およびより重要でない詳細が閾値未満であり、したがってモデルに含まれない場合に見つかる。時々、より洗練された閾値化動作が、エッジ振幅に適用され、高閾値パラメータおよび低閾値パラメータの指定が要求される。この動作を、ヒステリシス閾値化（ｈｙｓｔｅｒｅｓｉｓ  ｔｈｒｅｓｈｏｌｄｉｎｇ）と呼ぶ（Ｊ．Ｃａｎｎｙ、「Ｆｉｎｄｉｎｇ  Ｅｄｇｅｓ  ａｎｄ  Ｌｉｎｅｓ  ｉｎ  Ｉｍａｇｅｓ（イメージにおけるエッジおよびラインを探索）」：Ｒｅｐｏｒｔ、ＡＩ−ＴＲ−７２０、Ｍ．Ｉ．Ｔ．Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  Ｌａｂ．、米国マサチューセッツ州ケンブリッジ、１９８３年を参照されたい）。高閾値を超えるエッジ振幅を有するすべての点が、即座に受け入れられる（「セキュア点」）。逆に、低閾値未満のエッジ振幅を有するすべての点が、即座に拒絶される。両方の閾値の間のエッジ振幅を有する「潜在的」点は、「潜在的」点の経路によって「セキュア」点に接続されている場合に受け入れられる。本発明は、従来の閾値化動作を使用しなければならない場合に１つの閾値を自動的に決定する方法を提供し、ヒステリシス閾値化を使用しなければならない場合に２つの閾値を自動的に決定する方法を提供する。
【０００６】
・物体部分の最小サイズ。認識プロセスの堅牢性を高めるために、しばしば、小さい物体部分をモデルから除去することが有用である。小さい物体部分は、イメージ雑音をより受けやすく、したがって、安定した認識をよりむずかしくする。本発明は、モデルに含まれる物体部分の最小サイズを自動的に決定する方法を提供する。
【０００７】
・モデル点削減。ほとんどの認識手法では、認識プロセスの速度が、物体モデルに保管された点の個数に依存する。したがって、認識プロセスを高速化するために、多数のモデル点につながる大きい物体を扱う時には、モデル点の個数を減らさなければならない。点削減の度合は、本発明による方法によって自動的に計算される。
【０００８】
・イメージ構造の最小コントラスト。最小コントラスト未満のエッジ振幅を有するイメージ構造は、イメージ雑音と解釈されなければならず、モデルに含めてはならず、認識プロセスに影響してもならない。通常、最小コントラストは、物体のコントラストよりかなり低い。本発明は、モデルイメージ内の雑音を自動的に決定し、推定されたイメージ雑音に基づいて最小コントラストを導出する方法を提供する。
【０００９】
・離散化ステップ長。物体認識手法は、しばしば、ポーズ空間を離散化し、各離散ポーズに従ってモデルを変換する。類似性測度を使用して、その中で物体が認識されなければならないランタイムイメージとモデルの離散ポーズを比較することができる。物体が所与のポーズで見つかるのは、このポーズの類似性が閾値を超える場合である。ポーズ空間の次元数は、物体がランタイムイメージで受ける可能性がある変換に依存する。２Ｄ変換の場合に、ポーズ空間は、２次元を有し、リジッド変換の場合に、３次元（＋１回転）を有し、類似性変換の場合に、４次元（＋１スケーリング）を有するなどである。変換の離散化ステップ長に、画素グリッドに従って１画素を簡単にセットできることは明白である。残念ながら、残りの次元（たとえば、回転、スケーリング）に関して、匹敵する自然な離散化ステップ長は、入手可能でない。本発明では、回転、スケーリング、さらには物体モデルの変換に関する、最適の離散化ステップ長を自動的に決定するのに使用できる方法を説明する。
【００１０】
これらのパラメータのすべてを、物体の単一のモデルイメージだけに基づいて、本発明による方法によって自動的に決定することができる。
【課題を解決するための手段】
【００１１】
本発明は、全般的にはマシンビジョン、具体的には物体認識での自動パラメータ決定のシステムおよび方法を提供する。
イメージ内の物体のコントラスト
第１の態様によれば、本発明は、イメージ内の物体のコントラストを自動的に決定する方法を提供する。これは、エッジ振幅の最適閾値の決定と同等である。得られたエッジは、物体を最適に記述する、すなわち、物体のすべての重要なエッジが、記述に含まれると同時に、雑音またはテクスチャから生じるエッジが、記述から除外される。最適記述は、たとえば、物体認識の分野で重要であり、この場合に、認識プロセスの堅牢性および速度は、モデルに使用される物体記述に強く依存する。
【００１２】
本発明の好ましい実施形態で、エッジは、エッジ振幅のすべての可能な閾値を使用して、所与のモデルイメージから抽出される。閾値ごとに、結果のエッジが、エッジ領域値を作る、ある評価基準を使用して評価される。エッジ領域値の極値に対応する閾値が、最適閾値として採用される。
【００１３】
複数の評価基準が可能である。しかし、本発明の好ましい実施形態では、エッジの曲率が、評価に使用される。エッジの曲率の計算は、高価なので、その代わりに異なる手法が採用される。エッジを、高い曲率の部分の点で分割するが、高い曲率の点は、領域形態学を使用することによって非常に効率的に計算することができる。最後に、最大化されなければならない評価基準は、分割されたエッジの接続された成分の平均長である。
【００１４】
好ましい実施形態によれば、ヒステリシス閾値化動作が、低閾値パラメータおよび高閾値パラメータの指定を必要とするエッジ振幅に適用される。本発明の一実施形態で、エッジが、２つの閾値のすべての可能な組合せについて抽出され、評価される。可能な組合せの個数は、効率的に計算するには多すぎるので、本発明の好ましい実施形態では、その代わりに異なる手法が選択される。第１に、１つの最適閾値を、上で説明したように決定する。この最適閾値に基づいて、評価基準が減りすぎるまで、高閾値パラメータを増やす。同一のことを、低閾値パラメータについて行う。したがって、高価な２Ｄ問題が３つの１Ｄ問題に縮小され、１Ｄ問題は効率的に解くことができるので、最適閾値を非常に効率的に決定することができる。
【００１５】
第１の態様によれば、本発明は、イメージ内の物体のコントラストを自動的に決定する方法であって、
（ａ）前記物体の電子イメージを提供するステップと、
（ｂ）前記物体のエッジ振幅を識別するステップと、
（ｃ）前記エッジ振幅に適用される閾値の範囲に関する前記物体のエッジ領域を識別するステップと、
（ｄ）閾値の前記範囲について得られる前記エッジ領域を評価するステップであって、より高い評価結果がよりよい評価を示す、ステップと、
（ｅ）最大エッジ領域値に対応する最適閾値を決定するステップと、
（ｆ）前記物体の前記コントラストを表す、前記最大エッジ領域値に対応する前記最適閾値を提供するステップと、
を含む方法を提供する。
【００１６】
ステップ（ｄ）が、物体エッジの平均負曲率を識別するステップを含むことが好ましい。さらに、ステップ（ｄ）が、
（ｄ１）８接続されているエッジ画素を識別するステップと、
（ｄ２）強い曲率のエッジ画素を決定するステップと、
（ｄ３）差領域を形成するために前記エッジ領域から強い曲率の前記エッジ画素を削除するステップと、
（ｄ４）前記差領域の接続された成分を識別するステップと、
（ｄ５）前記エッジ領域値を識別するために前記接続された成分の平均長を提供するステップと、
を含むことが好ましい。
【００１７】
ステップ（ｄ２）が、フィルタマスクを使用して前記エッジ画素に４つの侵食を適用するステップを含むことがより好ましい。
【００１８】
好ましい実施形態によれば、ステップ（ｃ）が、前記エッジ振幅にヒステリシス閾値を適用することによってより低いヒステリシス閾値およびより高いヒステリシス閾値の組合せに関してエッジ領域を識別するステップを含み、ステップ（ｆ）が、前記物体の前記コントラストを決定するために前記エッジ領域値の最大値に対応する前記ヒステリシス閾値を提供するステップを含む。
【００１９】
好ましい実施形態では、ステップ（ｆ）が、
（ｆ１）低ヒステリシス閾値および高ヒステリシス閾値を、ステップ（ｅ）から得られた前記エッジ領域値の最大値に対応する前記閾値に初期化するステップと、
（ｆ２）前記高ヒステリシス閾値を連続して増分し、前記低ヒステリシス閾値および前記高ヒステリシス閾値を前記エッジ振幅に適用することによって前記エッジ領域値を識別するステップと、
（ｆ３）増分された高閾値ごとに得られる前記エッジ領域値を決定するステップと、
（ｆ４）前記エッジ領域値が最高の得られた値のある比率未満に減るまでステップ（ｆ２）から（ｆ３）を繰り返すステップと、
（ｆ５）前記低ヒステリシス閾値を連続して減分し、前記低ヒステリシス閾値および前記高ヒステリシス閾値を前記エッジ振幅に適用することによって前記エッジ領域値を識別するステップと、
（ｆ６）減分された低閾値ごとに得られる前記エッジ領域値を決定するステップと、
（ｆ７）前記エッジ領域値が最高の得られた値のある比率未満に減るまでステップ（ｆ５）から（ｆ６）を繰り返すステップと、
（ｆ８）前記物体の前記コントラストを表す最適の低ヒステリシス閾値および高ヒステリシス閾値を提供するステップと、
によって置換される。
【００２０】
最小コントラスト（以下を参照されたい）が、自動的に決定され、
（ｇ）イメージ雑音の標準偏差を推定するステップと、
（ｈ）前記推定された標準偏差に所定の係数をかけることによって最小エッジ振幅を決定するステップと、
（ｉ）前記最小コントラストとして前記最小エッジ振幅を使用するステップと、
を含むことが好ましい。
【００２１】
本発明の第１の態様によるイメージ内の物体のコントラストを自動的に決定するデータ処理システムは、
（ａ）前記物体の電子イメージを提供する手段と、
（ｂ）前記物体のエッジ振幅を識別する手段と、
（ｃ）前記エッジ振幅に適用される閾値の範囲に関する前記物体のエッジ領域を識別する手段と、
（ｄ）閾値の前記範囲について得られる前記エッジ領域を評価する手段であって、より高い評価結果がよりよい評価を示す、手段と、
（ｅ）最大エッジ領域値に対応する最適閾値を決定する手段と、
（ｆ）前記物体の前記コントラストを表す、前記最大エッジ領域値に対応する前記最適閾値を提供する手段と、
を含む。
【００２２】
第１の態様によれば、本発明は、イメージ内の物体のコントラストを決定するプログラム命令を含むデータ記憶媒体であって、プログラムステップが、
（ａ）前記物体の電子イメージを提供するステップと、
（ｂ）前記物体のエッジ振幅を識別するステップと、
（ｃ）前記エッジ振幅に適用される閾値の範囲に関する前記物体のエッジ領域を識別するステップと、
（ｄ）閾値の前記範囲について得られる前記エッジ領域を評価するステップであって、より高い評価結果がよりよい評価を示す、ステップと、
（ｅ）最大エッジ領域値に対応する最適閾値を決定するステップと、
（ｆ）前記物体の前記コントラストを表す、前記最大エッジ領域値に対応する前記最適閾値を提供するステップと、
を含む、データ記憶媒体も提供する。
物体部分の最小サイズ
第２の態様によれば、本発明は、モデルに含まれる物体部分の最小サイズを自動的に決定する方法を提供する。物体部分の最小サイズは、エッジ画素のうちの多くともある比率（たとえば、５％）が除去されるように計算される。このために、接続された成分のサイズの累積ヒストグラムを計算する。最小サイズは、この累積ヒストグラムの、所与の比率を超える最初の項目に対応する。
【００２３】
第２の態様によれば、物体部分の最小サイズを自動的に決定する方法は、
（ａ）前記物体の電子イメージを提供するステップと、
（ｂ）前記イメージのエッジ振幅を識別するステップと、
（ｃ）閾値を適用することによって前記物体のエッジ領域を識別するステップと、
（ｄ）前記エッジ領域の接続された成分を識別し、成分の長さを決定するステップと、
（ｅ）前記成分の長さの累積ヒストグラムを識別するステップと、
（ｆ）事前定義の比率を超えるヒストグラムビンを識別するステップと、
（ｇ）物体部分の前記最小サイズを表す、前記ヒストグラムビンに関連するエッジ長さを提供するステップと、
を含む。
【００２４】
ステップ（ｃ）において、前記閾値が、本発明の第１の態様の方法を使用して自動的に得られることが好ましい。
【００２５】
さらに、第２の態様によれば、物体部分の最小サイズを自動的に決定するデータ処理システムは、
（ａ）前記物体の電子イメージを提供する手段と、
（ｂ）前記イメージのエッジ振幅を識別する手段と、
（ｃ）自動的に得られた閾値を使用することによって前記物体のエッジ領域を識別する手段と、
（ｄ）前記エッジ領域の接続された成分を識別し、成分の長さを決定する手段と、
（ｅ）前記成分の長さの累積ヒストグラムを識別する手段と、
（ｆ）事前定義の比率を超えるヒストグラムビンを識別する手段と、
（ｇ）物体部分の前記最小サイズを表す、前記ヒストグラムビンに関連するエッジ長さを提供する手段と、
を含む。
【００２６】
第２の態様によれば、本発明は、物体部分の最小サイズを自動的に決定するプログラム命令を含むデータ記憶媒体であって、プログラムステップが、
（ａ）前記物体の電子イメージを提供するステップと、
（ｂ）前記イメージのエッジ振幅を識別するステップと、
（ｃ）自動的に得られた閾値を使用することによって前記物体のエッジ領域を識別するステップと、
（ｄ）前記エッジ領域の接続された成分を識別し、成分の長さを決定するステップと、
（ｅ）前記成分の長さの累積ヒストグラムを識別するステップと、
（ｆ）事前定義の比率を超えるヒストグラムビンを識別するステップと、
（ｇ）物体部分の前記最小サイズを表す、前記ヒストグラムビンに関連するエッジ長さを提供するステップと、
を含む、データ記憶媒体も提供する。
モデル点削減
第３の態様によれば、点削減の度合は、本発明による方法によって自動的に計算される。大きいモデルについて、モデル点の個数は、堅牢さまたは精度を減らさずに減らすことができる。これは、最適の個数のモデル点が残るように、十分な個数のモデル点を除去することによって行うことができる。一般に、モデル点の最適の個数を決定する２つの可能な形がある。第１の形は、ユーザが供給する複数の物体の例のイメージに基づいて最適個数を自動的に見つけることである。したがって、個々の物体ごとに、特有の最適個数を決定することができる。残念ながら、多くの場合に、そのような例のイメージが入手可能でない。したがって、第２の形は、ほとんどの物体に良く適する最適個数を自動的に見つけることである。これは、多数の異なる物体の複数の例のイメージを使用することによって行うことができる。この場合に、モデル点の最適個数は、物体認識手法だけに依存し、実装中に１回、経験的に決定されなければならない。その結果、ユーザは、例のイメージを提供する必要がない。
【００２７】
第３の態様によれば、エッジ点の個数に関する削減要因を自動的に決定する方法は、
（ａ）前記物体の電子イメージを提供するステップと、
（ｂ）前記イメージのエッジ振幅を識別するステップと、
（ｃ）閾値を適用することによって前記物体のエッジ領域を識別するステップと、
（ｄ）所定の堅牢さおよび精度を達成するのに少なくとも必要なモデル点の最適個数を識別するステップと、
（ｅ）ステップ（ｄ）で決定されたモデル点の前記最適個数が残されるように、モデル点のうちのめいめいの分数を除去するステップと、
を含む。
【００２８】
ステップ（ｃ）において、前記閾値が、本発明の第１の態様の方法を使用して自動的に得られることが好ましい。
【００２９】
ステップ（ｄ）で決定されたエッジ点の前記最適個数が、現在の物体に基づいて計算され、
（ｄ１）前記物体の少なくとも１つの電子テストイメージを提供するステップと、
（ｄ２）テストイメージごとに、認識されなければならない物体実例の個数を提供するステップと、
（ｄ３）所望の認識手法を使用する前記物体のモデル表現を提供するステップと、
（ｄ４）前記モデル表現および前記所望の認識手法を使用して各テストイメージ内の前記物体を認識し、すべてのテストイメージにわたる平均認識時間を決定するステップと、
（ｄ５）モデル点の個数を所定の係数だけ減らすステップと、
（ｄ６）前記平均認識時間が増えない限り、かつステップ（ｄ２）で提供された前記個数の物体実例が各テストイメージ内で見つかる限り、ステップ（ｄ４）から（ｄ５）を繰り返すステップと、
（ｄ７）ステップ（ｄ２）で提供された前記個数の物体実例が見つかり、前記平均認識時間が最小である、モデル点の最適個数を使用するステップと、
を含むことが好ましい。
【００３０】
ステップ（ｄ１）〜（ｄ７）で決定されたモデル点の前記最適個数が、多数の物体についてステップ（ｄ１）から（ｄ７）を繰り返し、モデル点の最適個数の平均値を提供することによって、前記現在の物体と独立であることがより好ましい。
【００３１】
本発明の第３の態様によるモデル点の個数に関する削減要因を自動的に決定するデータ処理システムは、
（ａ）前記物体の電子イメージを提供する手段と、
（ｂ）前記イメージのエッジ振幅を識別する手段と、
（ｃ）自動的に得られた閾値を適用することによって前記物体のエッジ領域を識別する手段と、
（ｄ）所定の堅牢さおよび精度を達成するのに少なくとも必要なモデル点の最適個数を識別する手段と、
（ｅ）手段（ｄ）によって決定されたモデル点の前記最適個数が残されるように、モデル点のうちの個々の分数を除去する手段と、
を含む。
【００３２】
第３の態様によれば、本発明は、モデル点の個数に関する削減要因を自動的に決定するプログラム命令を含むデータ記憶媒体であって、プログラムステップが、
（ａ）前記物体の電子イメージを提供するステップと、
（ｂ）前記イメージのエッジ振幅を識別するステップと、
（ｃ）自動的に得られた閾値を適用することによって前記物体のエッジ領域を識別するステップと、
（ｄ）所定の堅牢さおよび精度を達成するのに少なくとも必要なモデル点の最適個数を識別するステップと、
（ｅ）ステップ（ｄ）で決定されたモデル点の前記最適個数が残されるように、モデル点のうちの個々の分数を除去するステップと、
を含む、データ記憶媒体も提供する。
イメージ構造の最小コントラスト
第４の態様によれば、本発明は、モデルイメージ内の雑音を自動的に決定し、推定されたイメージ雑音に基づいて最小コントラストを導出する方法を提供する。最小コントラストは、モデルをイメージ内の雑音から分離するので、よい選択は、イメージ内の雑音によって引き起こされるグレイ値変化の範囲である。したがって、本発明の好ましい実施形態では、複数の既存の方法のうちの１つを使用して、モデルイメージ内の雑音の標準偏差を推定する。次に、推定された標準偏差にある係数をかけたもの未満のエッジ振幅を有するすべてのエッジ点が、さらなる処理について除去される。この係数が大きいほど、雑音によって引き起こされたエッジが誤って受け入れられる可能性が少なくなる。
離散化ステップ長
本発明の第５の態様によれば、回転、スケーリング、および物体モデルのさらなる変換に関する、最適の離散化ステップ長を自動的に決定する方法が説明される。角度ステップ長は、物体がランタイムイメージ内に現れるユーザ指定の角度範囲内のステップ長を決定する。角度ステップ長が小さすぎる場合に、認識時間ならびにモデルを格納するのに必要なメモリが増える。その一方で、大きすぎる角度ステップ長が選択される場合に、認識の堅牢さが減る。というのは、ランタイムイメージ内の物体のある方位を見つけることができないからである。本発明の１実施形態では、まず、角度ステップ長の最初の推測が、欧州特許第ＥＰ−Ａ−１１９３６４２号で提案されているように、物体のサイズに基づいて計算される。第２ステップで、最初の推測を半分にすることによってモデルイメージを回転し、物体と回転されたモデルイメージの間の類似性を計算することによって、最初の推測を評価する。類似性測度が、ある閾値未満である場合に、角度ステップ長を半分にする。この処理は、類似性測度が閾値を超え、最適の角度ステップ長がもたらされるまで繰り返される。
【００３３】
第５の態様によれば、第１の実施形態に従って物体モデルの離散化ステップ長を自動的に決定する方法は、
（ａ）前記物体の電子イメージを提供するステップと、
（ｂ）前記物体のサイズに基づいて前記離散化ステップ長の初期値を提供するステップと、
（ｃ）現在の離散化ステップ長に関連する最小類似性測度を識別するステップと、
（ｄ）結果の離散化ステップ長を決定するために、関連する最小類似性測度がある閾値を超えるまで、前記離散化ステップ長を半分にするステップと、
（ｅ）物体認識のモデル変換を決定するために、前記結果の離散化ステップ長を使用するステップと、
を含む。
【００３４】
ステップ（ｂ）は、
（ｂ１）前記変換の固定点からの前記モデル点の最大距離を計算するステップと、
（ｂ２）最大の許容される画素変位を仮定するステップと、
（ｂ３）前記最大距離および前記許容される画素変位に基づいて前記離散化ステップ長の前記初期値を計算するステップと、
を含むことが好ましい。
【００３５】
ステップ（ｃ）の前記最小類似性測度が、変換されない物体モデルと、前記離散化ステップ長の半分だけ変換されたモデルイメージとの間の類似性測度に対応することが好ましい。
【００３６】
本発明の第４の態様のこの実施形態に従って物体モデルの離散化ステップ長を自動的に決定するデータ処理システムは、
（ａ）前記物体の電子イメージを提供する手段と、
（ｂ）前記物体のサイズに基づいて前記離散化ステップ長の初期値を提供する手段と、
（ｃ）現在の離散化ステップ長に関連する最小類似性測度を識別する手段と、
（ｄ）結果の離散化ステップ長を決定するために、関連する最小類似性測度がある閾値を超えるまで、前記離散化ステップ長を半分にする手段と、
（ｅ）物体認識のモデル変換を決定するために、前記結果の離散化ステップ長を使用する手段と、
を含む。
【００３７】
さらに、本発明は、物体モデルの離散化ステップ長を自動的に決定するプログラム命令を含むデータ記憶媒体であって、プログラムステップは、
（ａ）前記物体の電子イメージを提供するステップと、
（ｂ）前記物体のサイズに基づいて前記離散化ステップ長の初期値を提供するステップと、
（ｃ）現在の離散化ステップ長に関連する最小類似性測度を識別するステップと、
（ｄ）結果の離散化ステップ長を決定するために、関連する最小類似性測度がある閾値を超えるまで、前記離散化ステップ長を半分にするステップと、
（ｅ）物体認識のモデル変換を決定するために、前記結果の離散化ステップ長を使用するステップと、
を含むデータ記憶媒体を提供する。
【００３８】
代替実施形態によれば、物体モデルの離散化ステップ長を自動的に決定する方法が、
（ａ）前記物体の電子イメージを提供するステップと、
（ｂ）現在のステップ長を０に初期化するステップと、
（ｃ）十分に小さい値だけ前記現在のステップ長を増分するステップと、
（ｄ）変換されないモデルと前記現在のステップ長に従って変換されたモデルイメージとの間の類似性測度を識別するステップと、
（ｅ）前記類似性測度がある閾値未満になるまで前記ステップ（ｃ）および（ｄ）を繰り返すステップと、
（ｆ）前記類似性測度が前記閾値を超える最後のステップ長の２倍として最適ステップ長を提供するステップと、
を含む。
【００３９】
本発明のさらなる特徴および長所は、添付図面と組み合わせて解釈される次の詳細な説明から明白になる。
【発明を実施するための最良の形態】
【００４０】
イメージ内の物体のコントラスト
イメージ内の物体のコントラストは、さまざまな影響、たとえば、実世界の物体の実際のコントラスト、照明（強度、位置、方位）、カメラセッティング（シャッタ、絞り、ガンマ訂正など）、物体に関するカメラの視角、物体の反射特性などに依存する。イメージ内の物体のコントラストを計算するために、これらのパラメータのすべてを含むイメージングプロセスをモデル化することは、明らかに実現可能でない。その代わりに、物体の単一のイメージに基づいて、コントラストを自動的に導出しなければならない。このコントラスト値に基づいて、物体を最適に記述するエッジを抽出することができる。一方で、最適の記述には、イメージ内の、物体に属するエッジだけが含まれる。他のイメージ構造、たとえば雑音、テクスチャ付き背景、または他のイメージ擾乱から生じるエッジは、この記述から排除されなければならない。その一方で、最適の記述は、すべての関連する物体部分が含まれることも保証する、すなわち、物体が完全に記述されなければならない。
【００４１】
たとえば、物体認識用のモデルを作成するために物体のエッジをモデルイメージ内で決定しなければならない場合には、通常、エッジ振幅を計算し、この振幅に閾値を適用する。最適閾値を適用した後の長方形物体の結果のエッジ領域を、図１Ａに示す。この図では、イメージの画素が、正方形によって表され、暗い画素が、抽出されたエッジ領域を示す。小さすぎる閾値が選択された場合に、雑音または背景テクスチャに起因するエッジが、抽出され（図１Ｂ）、これには、ほとんどの場合に、有用な情報が含まれない。ほとんどの物体認識手法は、ある類似性測度を使用して、モデルをランタイムイメージと比較することによって物体を見つけることを試みる。その結果、雑音および背景テクスチャが、モデルイメージと比較されるランタイムイメージと異なるので、検索の堅牢性が減る。その一方で、大きすぎる閾値が選択された場合に、物体エッジの一部が、モデル記述から失われ、情報の消失がもたらされる（図１Ｃ）。したがって、モデル記述の区別する力が減り、より多くの誤った肯定の一致につながる。その結果、イメージ内の物体のコントラストの決定は、エッジ振幅に関する最適閾値を見つけることと同等である。
【００４２】
イメージピラミッド（ｉｍａｇｅ  ｐｙｒａｍｉｄ）を使用する時に、追加の問題が生じる。マシンビジョンの多くのアルゴリズムが、計算を高速化するためにイメージピラミッドを使用する粗から微細へのフレームワークに組み込まれている（たとえば、Ｓｔｅｖｅｎ  Ｌ．Ｔａｎｉｍｏｔｏ、「Ｔｅｍｐｌａｔｅ  ｍａｔｃｈｉｎｇ  ｉｎ  ｐｙｒａｍｉｄｓ（テンプレートマッチングピラミッド）」、Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ  ａｎｄ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ、１６：３５６〜３６９ページ、１９８１年、Ｂｏｒｇｅｆｏｒｓ（１９８８年）、Ｂｒｏｗｎ（１９９２年）、欧州特許第ＥＰ−Ａ−１１９３６４２号、またはＵｌｒｉｃｈ他（２００３年）を参照されたい）。イメージピラミッドは、徐々により小さいイメージにつながる、スムージングおよびサブサンプリング動作をオリジナルイメージに連続して適用することによって計算される。イメージピラミッドを利用する物体認識システムでは、検索が、通常は粗（高）ピラミッドレベルで開始され、次により精（低い）レベルの、粗レベルでの類似性測度が有望である局所区域で継続される。したがって、しばしば、計算時間をできる限り減らすために、ピラミッドレベルの個数を最大にすることが望ましい。イメージピラミッドを作成する時に適用される連続したスムージングのゆえに、エッジ振幅は、より高いピラミッドレベルで減る。したがって、あるレベルで、エッジ振幅が、閾値未満になる。これによって、使用できるピラミッドレベルの個数の上限が自然に定義される。高すぎるコントラストが選択された場合に、これが、より低いピラミッドレベルで既に発生し、したがって、使用可能なピラミッドレベルの個数が減るが、これは望ましくない。
【００４３】
次で、最適閾値の自動計算を容易にする方法を説明する。図２を参照すると、本発明の方法は、入力イメージのエッジ振幅を計算する（ステップ１０２）。これは、標準エッジフィルタを適用することによって行うことができる。本発明の好ましい実施形態では、行方向および列方向の一次導関数ｄｒおよびｄｃの計算にＳｏｂｅｌフィルタを使用する（Ｒａｆａｅｌ  Ｃ．Ｇｏｎｚａｌｅｓ、Ｒｉｃｈａｒｄ  Ｅ．Ｗｏｏｄｓ、「Ｄｉｇｉｔａｌ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ（デジタル画像処理）」、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏｍｐａｎｙ、１９９２年）。エッジ振幅は、最終的に、
【００４４】
【数１】
2007257601.tif 000003
を計算することによってｄｒおよびｄｃから得られる。第２ステップ（ステップ１０４）で、閾値Ｔに、当初は最小値をセットする。本発明の１実施形態で、この最小値は、ユーザが指定することができ、自動的に計算されるコントラスト値の下限を決定する。他の情報が入手可能でない場合には、最小値を１にすることができる。その代わりに、好ましい実施形態では、イメージの雑音レベルをセットすることができ、これも、後で示すように自動的に決定することができる。最後に、閾値をエッジ振幅に適用し、エッジ振幅が閾値を超えるイメージ領域を得る（ステップ１０６）。このエッジ領域（たとえば、図１を参照されたい）は、通常は１画素幅の構造からなるが、これをある判断基準に基づいて評価する（ステップ１０８）。異なる種類の判断基準が、エッジ領域の評価について可能であるが、判断基準は、結果のエッジ領域値が最適閾値Ｔｏｐｔの位置で極値を示すように選択されなければならない（たとえば、図８を参照されたい）。評価の結果は、通常はスカラエッジ領域値によって表されるが、現在の閾値の位置の関数配列ｆ（Ｔ）に保管される（ステップ１１０）。たとえば、現在の閾値が２０であり、エッジ領域値が０．３である場合に、ｆ（２０）に０．３をセットする。このステップの後に、閾値がある最大値を超えない限り（ステップ１１２）、現在の閾値Ｔを増分し（ステップ１１４）、ステップ１０６〜１１４を繰り返す。この最大値は、ユーザが指定することができ、自動的に計算されるコントラスト値の上限を決定する。好ましい実施形態で、最大値に、イメージ内で発生し得る最大の可能なエッジ振幅がセットされる。好ましい実施形態で、ステップ１１４で閾値を増分するステップサイズに、１がセットされる。他の実施形態で、最適のコントラストの自動計算を高速化するために、ステップサイズに、より大きい値（たとえば、２、３、または４）がセットされる。最大閾値に達した後に、関数ｆ（Ｔ）に、評価された閾値ごとに、図１に示された対応するエッジ領域値が含まれる。最後のステップで、関数ｆ（Ｔ）のグローバル極値を堅牢に抽出する（ステップ１１６）。これは、さまざまな標準的な方法の１つを適用することによって行うことができる。本発明の好ましい実施形態では、異なるサイズのスムージングフィルタを使用し、十分に大きいフィルタサイズから開始して、この関数を複数回スムージングする。スムージングは、ある一貫性検査を満足する単一の極値だけが残るまで、徐々に減らされる。１つの可能な一貫性検査は、極値が、領域の境界にないことすなわち、極値が、最大のまたは最小のテストされた閾値と異なることである。もう１つの可能な一貫性検査は、結果のエッジ画素の個数が、ある適当な限度内にあることである。最後に、極値の位置が、最適閾値Ｔｏｐｔの値に対応し、これが物体のコントラストを表す。
【００４５】
次に、本発明の好ましい実施形態で使用される、異なる可能な評価基準の１つを詳細に説明する。物体に属するエッジは、エッジの曲率を検討することによって、雑音またはテクスチャによって引き起こされるエッジから区別することができる。通常、物体を記述するエッジは、雑音またはテクスチャによって引き起こされるエッジより小さい曲率を有する。したがって、本発明の１実施形態では、平均エッジ曲率を、評価基準として使用する。曲率は、たとえば、抽出されたエッジ領域にエッジリンキングアルゴリズムを適用し、連続するエッジ点に基づいて曲率を導出することによって計算することができる。残念ながら、エッジリンキングプロセスの計算および曲率計算は、高価である。したがって、本発明の好ましい実施形態では、異なる手法を適用する。この手法のアルゴリズムを、図３に示す。この流れ図は、図２で示されたものとはステップ２００〜２０８だけが異なり、これらのステップは、図２のステップ１０８の特定の一実施形態を表す。
【００４６】
基本的なアイデアは、高い曲率の点でエッジを分割することである。通常、物体に属する、分割されたエッジセグメントの長さは、長く、イメージの雑音またはテクスチャに属する、分割されたエッジセグメントの長さは、短い。その結果、よい評価基準は、高い曲率の点で分割した後のエッジセグメントの平均長である。この判断基準は、低すぎる閾値が選択された場合に低いエッジ領域値を返す。というのは、多数の雑音によるエッジが存在し、多数の短いエッジセグメントにつながるからである。閾値が増やされる場合に、この判断基準は、より高いエッジ領域値を返し、最適閾値で最大値に達する。閾値がさらに増やされる場合に、物体エッジが分割され、やはりより短いエッジセグメントにつながり、したがって評価結果の減少につながる。
【００４７】
エッジ領域を高い曲率の点で分割するために、エッジ領域を１画素幅構造まで細線化する必要がある（ステップ２００）。このステップは、エッジ領域の計算が既に１画素幅構造を返している場合には省略することができる。そうでない場合に、複数の使用可能なエッジ細線化アルゴリズムの１つを適用することができる（たとえば、Ｃａｎｎｙ（１９８３年）、Ｕ．Ｅｃｋａｒｄｔ、Ｖｅｒｄｕｎｎｕｎｇ  ｍｉｔ  Ｐｅｒｆｅｋｔｅｎ  Ｐｕｎｋｔｅｎ、Ｐｒｏｃｅｅｄｉｎｇｓ  １０．  ＤＡＧＭ−Ｓｙｍｐｏｓｉｕｍ、ＩＦＢ  １８０、Ｚｕｒｉｃｈ、１９８８年、またはＧｏｎｚａｌｅｓ  ａｎｄ  Ｗｏｏｄｓ（１９９２年）を参照されたい）。例を、図４に示す。エッジ振幅に閾値を適用した後に得られたエッジ領域を、図４Ａに示す。隣接するエッジ画素は、４つ接続され、２画素幅の斜めのエッジになる。細線化ステップの後に、エッジは、８つ接続され、望みの１画素幅の斜めのエッジがもたらされる（図４Ｂを参照されたい）。次のステップに、高い曲率のエッジ画素の検出が含まれる（ステップ２０２）。これのために、４つの形態学的フィルタマスクを、細線化されたエッジ画素に適用する。フィルタマスクを、図５に示す。各フィルタマスクは、高い曲率または強い曲率を有する３つの隣接エッジ画素からなるエッジセグメントの４つの可能な方位のうちの１つを表す。フィルタマスクごとに、細線化されたエッジ領域の侵食（ｅｒｏｓｉｏｎ）（たとえば、Ｇｏｎｚａｌｅｓ  ａｎｄ  Ｗｏｏｄｓ、１９９２年を参照されたい）が適用され、ここで、フィルタマスクは、侵食の構造化要素として使用される。４つの構造化要素の基準点は、図５では白い丸によって表されている。侵食の結果は、エッジ画素に平行移動された基準点を有する構造化要素がオリジナルエッジ領域に完全に含まれるエッジ画素の組である。図１に示された３つの例に侵食を適用する時に、図６で白い丸によって示されたエッジ画素が得られる。図６Ａおよび図６Ｃでは、高い曲率のエッジ画素が返されないが、図６Ｂでは、合計１０個の高い曲率のエッジ画素が見つかっている。高い曲率の点でエッジ領域を分割するために、高い曲率の抽出された画素を、それぞれエッジ領域から減算または削除する（ステップ２０４）。最終結果を、図７に示す。結果の分割されたエッジ領域について、接続された成分を計算する（ステップ２０６）。２つのエッジ画素ｐおよびｑが接続されていると言われるのは、ｑがｐの８つの近傍に含まれる場合である（詳細については、Ｇｏｎｚａｌｅｓ  ａｎｄ  Ｗｏｏｄｓ、１９９２年を参照されたい）。この例について得られた接続された成分を視覚化するために、例示のために、小さい斜めの灰色のストリップが、図７で接続を示す。したがって、図７Ａでは、１つの接続された成分だけが得られ、図７Ｂでは、合計１４個の接続された成分が返され、図７Ｃでは、合計６つの接続された成分が見つかっている。最後のステップに、接続された成分の評価が含まれる（ステップ２０８）。これに関して、接続された成分の平均長を計算する。成分の長さは、その画素数によって近似される。その結果、成分の結果の平均長は、図７Ａでは２０．０、図７Ｂでは２．９、図７Ｃでは２．０である。この例では、評価関数の最大値が２０．０であり、したがって、対応する閾値が、最適量として選択される。次に、この最適閾値が、最終的にイメージ内の物体のコントラストを表す。
【００４８】
時々、ヒステリシス閾値化動作が、エッジ振幅に適用され、低閾値パラメータおよび高閾値パラメータを指定する必要が生じる場合がある。したがって、物体のコントラストが、２つのパラメータＴｌｏｗおよびＴｈｉｇｈによって表される。本発明の１実施形態で、この２つの閾値の、Ｔｌｏｗ≦Ｔｈｉｇｈであるすべての可能な組合せについて、エッジ領域が、上で説明したように計算され、評価される。したがって、得られる関数ｆ（Ｔｌｏｗ，Ｔｈｉｇｈ）は、２変数の関数である。１Ｄの場合に似て、ＴｌｏｗおよびＴｈｉｇｈの最適値を見つけるために、この関数の極値が抽出される。残念ながら、この手法に従う時には、最適閾値の組合せが、非常に時間を消費するものになる。というのは、一般に、ＴｌｏｗおよびＴｈｉｇｈの可能な組合せの個数が非常に多いからである。たとえば、２００個の閾値をテストする場合に、それについてエッジを抽出し、評価しなければならない、２０１００個の可能な組合せがある。したがって、本発明の好ましい実施形態では、この２Ｄ問題を、図９に示されているように３つの１Ｄ問題に還元する。第１に、１つの最適閾値Ｔｏｐｔを、図２または図３の流れ図に従って１Ｄの場合について説明したものと同一の形で決定する。閾値ＴｌｏｗとＴｈｉｇｈの両方が、Ｔｏｐｔを用いて初期化される。第２ステップで、Ｔｈｉｇｈを連続して増分する。各増分の後に、閾値ＴｌｏｗおよびＴｈｉｇｈを用いるヒステリシス閾値化動作を使用してエッジを抽出する。結果のエッジを評価する。Ｔｈｉｇｈは、評価の結果が、それまでに見つかった最良の評価に関してある比率（たとえば、９５％）まで下がるまで増分される。この後に、最適高閾値Ｔｏｐｔｈｉｇｈに、最良の評価結果に対応する閾値Ｔｈｉｇｈをセットする。第３ステップでは、Ｔｌｏｗを連続して減らす。やはり、結果のエッジを、ＴｌｏｗおよびＴｏｐｔｈｉｇｈごとに評価する。Ｔｌｏｗは、評価の結果が、それまでに見つかった最良の評価に関してある比率（たとえば、９５％）まで下がるまで減らされる。この後に、最適低閾値Ｔｏｐｔｌｏｗに、最良の評価結果に対応する閾値Ｔｌｏｗをセットする。
物体部分の最小サイズ
本発明の第２の態様による物体部分の最小サイズは、多くともエッジ画素のうちのある比率（たとえば、５％）が除去されるように計算される。このために、ユーザによって与えられるか自動的に計算されるのいずれかである閾値を使用して、エッジを抽出する。次に、エッジの接続された成分を抽出し、そのサイズすなわち長さを計算する。本発明の好ましい実施形態では、最小サイズが、成分サイズのヒストグラムを使用して決定される。図１０に、例のヒストグラムを示す。このヒストグラムは、成分サイズごとに、成分のうちで個々のサイズを有する分数を示す。たとえば、すべての成分のうちの１１％が、４画素のサイズを有する。このヒストグラムに基づいて、項目を左から右に合計することによって、累積ヒストグラムを計算することができる。図１０のヒストグラムの累積ヒストグラムを、図１１に示す。この累積ヒストグラムは、成分ごとに、成分のうちで多くとも個々のサイズを有する分数を示す。たとえば、すべての成分のうちの１１．３％が、多くとも３画素のサイズを有する。最小サイズは、所与の比率を超える、累積ヒストグラム内の最初（左から始めて）の項目に対応する。本発明の好ましい実施形態では、この比率に５％がセットされる。この比率に基づけば、図１１に示された例の最小サイズは、３になる。したがって、３未満のサイズを有するすべての接続された成分が、モデルから除去される。これは、減らされた計算時間および物体認識のより高い堅牢さにつながる。
モデル点削減
モデル点の数を、本発明の第３の態様に従って、大きいモデルについてさらに減らすことができる。しばしば、物体認識手法の堅牢さおよび精度は、モデル点の個数に伴って増える。残念ながら、計算時間も増える。しかし、一般に、ある大きい数Ｎ個のモデル点で、精度および堅牢さは、モデル点の個数がさらに増やされた場合に大きくは増えなくなる。この個数Ｎは、主に、使用される物体認識手法に依存し、次に、それについてモデルを作成しなければならない物体に依存する。その結果、最適個数Ｎを決定する２つの可能な形があり、これを次で説明する。
【００４９】
本発明の１実施形態は、両方の影響を考慮に入れる、すなわち、物体認識手法への依存ならびに物体自体への依存が考慮される。これについて、ユーザは、モデルイメージのほかに、物体のいくつかの例のイメージを提供しなければならない。さらに、ユーザは、各例のイメージで見つけなければならない物体実例の個数を指定しなければならない。次に、自動評価を開始する。第１に、モデルを、モデル点の数を減らさずに、モデルイメージに基づいて作成する。第２に、モデルを、各例のイメージ内で検索する。ユーザ指定の個数の実例が、各例のイメージ内で見つかった場合には、平均認識時間を、モデル点の個数の関数として保管する。その後に、モデル点の個数を、ある比率、たとえば２０％だけ減らす。この（減らされた）モデルを、各例のイメージ内でもう一度検索する。この手順は、平均認識時間が増えず、ユーザ指定の個数の実例が各例のイメージ内で見つかる限り、繰り返される。モデル点の最適個数Ｎは、すべてのユーザ指定の実例が見つかり、平均認識時間が最小である個数に対応する。この手法は、計算時間がモデル点の個数に依存する認識手法（たとえば、欧州特許第ＥＰ−Ａ−１１９３６４２号、Ｕｌｒｉｃｈ他（２００３年））に適用可能である。他の手法は、他の最適化判断基準を必要とする場合があるが、類似する形で最適化することができる。
【００５０】
説明した手法の短所は、ユーザがいくつかの例のイメージを提供しなければならないことである。残念ながら、多くの場合に、そのような例のイメージが、入手可能でないか、少なくとも入手がむずかしい。したがって、本発明の好ましい実施形態では、２つの影響のうちの１つだけを考慮に入れる、すなわち、物体自体への依存ではなく物体認識手法への依存を考慮する。短所は、結果の最適個数が、実際の最適量ではなく近似にすぎないことである。しかし、ほとんどの物体について、この近似は十分に正確である。したがって、目的は、ほとんどの物体に良く適する最適個数を経験的に見つけることである。これは、たとえば大きいデータベースに保管された、多数の異なる物体の十分な個数の例のイメージを使用して、経験的テストを実行することによって実行することができる。物体ごとに、上で説明した最適化プロセスが実行される。最後に、モデル点の平均最適個数が、すべてのテストされた物体にまたがって計算される。平均最適値が、この認識手法のモデル点の最適個数Ｎとして使用される。この経験的決定は、ある認識手法について１回だけ実行される必要があり、したがって、実装後にシステム開発者が行うことができる。その結果、ユーザは、例のイメージを提供する必要がない。
【００５１】
最後に、Ｎがわかった後に、Ｎ個を超える点を有する大きい物体モデルを、十分な個数のモデル点を除去することによって間引くことができる。これは、たとえば２つおき、３つおき、４つおきなどの点だけを受け入れることによって、Ｎ個のモデル点だけが残される形で行うことができる。それを行う際に、モデル全体にわたって均一に分布する形で点を選択することが賢明である。そうでなければ、通常は不均一な形で物体に影響するオクルージョンに対する物体認識の堅牢さが、下がる可能性がある。
イメージ構造の最小コントラスト
最小コントラストは、モデルをイメージ内の雑音から分離する。したがって、よい選択は、イメージ内の雑音によって引き起こされるグレイ値変化の範囲である。たとえば、グレイ値が、１０グレイレベルの範囲内で変動する場合に、最小コントラストに１０をセットしなければならない。
【００５２】
本発明は、モデルイメージ内の雑音に基づいて最小コントラストを自動的に導出する方法を提供する。イメージ雑音を推定するために、複数の周知の手法のうちの１つを適用することができる（たとえば、Ｗ．Ｆｏｒｓｔｎｅｒ、「Ｉｍａｇｅ  Ｐｒｅｐｒｏｃｅｓｓｉｎｇ  ｆｏｒ  Ｆｅａｔｕｒｅ  Ｅｘｔｒａｃｔｉｏｎ  ｉｎ  Ｄｉｇｉｔａｌ  Ｉｎｔｅｎｓｉｔｙ，Ｃｏｌｏｒ  ａｎｄ  Ｒａｎｇｅ  Ｉｍａｇｅｓ（デジタル輝度、色および範囲イメージにおける特徴抽出のための画像処理）」、Ｓｐｒｉｎｇｅｒ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｏｎ  Ｅａｒｔｈ  Ｓｃｉｅｎｃｅｓ、Ｓｕｍｍｅｒ  Ｓｃｈｏｏｌ  ｏｎ  Ｄａｔａ  Ａｎａｌｙｓｉｓ  ａｎｄ  ｔｈｅ  Ｓｔａｔｉｓｔｉｃａｌ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｇｅｏｍａｔｉｃｓ、１９９９年、Ｊ．Ｉｍｍｅｒｋａｅｒ、「Ｆａｓｔ  Ｎｏｉｓｅ  Ｖａｒｉａｎｃｅ  Ｅｓｔｉｍａｔｉｏｎ（高速雑音分散評価）」、Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｉｍａｇｅ  Ｕｎｄｅｒｓｔａｎｄｉｎｇ、６４（２）、３００〜３０２ページ、１９９６年）。これらの方法は、イメージ内容と独立にイメージ雑音の標準グレイ値偏差σの値を返す。したがって、複数のイメージまたは同種のグレイ値を有するイメージを獲得する必要はなく、雑音を、モデルイメージ自体から直接に推定することができる。雑音によって引き起こされる可能性があるエッジ振幅は、雑音の標準偏差に依存する。本発明の好ましい実施形態では、雑音によって引き起こされるエッジのほとんどを考慮に入れることを保証するために、標準偏差に２．５という係数をかける。一般に、この係数が大きいほど、雑音によって引き起こされたエッジが誤って受け入れられる確率が低くなる。最後に、２．５σ未満のエッジ振幅を有するすべてのエッジ画素が、さらなる処理から除去される。
【００５３】
一般に、最小コントラストを、最小コントラスト未満のエッジ振幅を有するエッジをさらなる処理から排除するのに使用することができる。特に、最小コントラストを使用して、自動コントラスト決定中に計算されるすべての可能な閾値の範囲を、最小コントラストを超える閾値だけに制限することができる。
離散化ステップ長
次では、離散化ステップ長を自動的に計算する第５の態様の方法を、モデル回転だけについて説明する。しかし、この方法は、本発明の範囲から外れずに、たとえばスケーリングなどの他の変換に簡単に適用することができる。角度ステップ長は、物体がランタイムイメージに現れる可能性がある、角度のユーザ指定の範囲内のステップ長を決定する。一般に、角度ステップは、物体のサイズに基づいて選択しなければならない。より小さいモデルは、イメージ内に多数の異なる離散回転を有することがなく、したがって、角度ステップ長は、より小さいモデルについてより大きいものを選択することができる。モデルを保管するのに必要なメモリは、角度ステップの個数に比例する。したがって、小さすぎる角度ステップがセットされた場合に、モデルがもはや（仮想）メモリにおさまらないことが発生する場合がある。しかし、モデルが完全に主メモリにおさまることが望ましい。というのは、これによって、オペレーティングシステムによるページングがなくなり、したがって、物体を見つける時間がはるかに短くなるからである。さらに、ランタイムイメージ内で物体を認識する計算時間は、より小さい角度ステップについて増える。その一方で、大きすぎる角度ステップ長が選択された場合に、認識の堅牢さが減る。というのは、ランタイムイメージ内の物体のある方位が、最も近いモデル方位から遠すぎ、したがって、その物体を見つけられなくなるからである。
【００５４】
最適ステップ長は、適用される物体認識手法に強く依存する。ほとんどの認識手法は、物体が所与のポーズで存在するかどうかを判断するために、モデルとランタイムイメージの間の類似性測度を計算する。しばしば、見つかった一致のポーズのほかに、類似性測度の結果が、一致の品質を記述するスコア値に関してユーザに返される（たとえば、欧州特許第ＥＰ−Ａ−１１９３６４２号、Ｕｌｒｉｃｈ他（２００３年）を参照されたい）。一般性を失わずに、完全な一致が、１のスコア値を返し、１未満のスコア値が、モデルとランタイムイメージの間のより低い類似性を示すと仮定することができる。本発明の好ましい実施形態では、最適離散化ステップ長の計算が、ほとんどすべての認識手法によって返されるスコア値に基づく。
【００５５】
まず、ステップ長に関する最初の推測を、モデルに基づいて計算する。１つの可能な形が、単一のモデル方位を計算するのに使用される回転の中心からのすべてのモデル点の最大距離を計算することである（欧州特許第ＥＰ−Ａ−１１９３６４２号を参照されたい）。図１２に、Ｒによって表される、回転中心からのすべてのモデル点の最大距離を有する単純な長方形の物体を示す。回転ステップ長φに関する最初の推測を計算するために、物体がφだけ回転された場合に、最も遠いモデル点が２画素だけ変位すると仮定する。その結果、最初の推測は、φ＝２ａｒｃｓｉｎ（１／Ｒ）として計算することができる。選択される変位は、認識手法に依存する。小さい方位変化により鈍感な手法について、変位を大きくすることができ、逆も同様である。
【００５６】
本発明の好ましい実施形態では、最適角度ステップ長が、最初の推測に基づいて洗練される。これに関して、物体モデルが、角度ステップ長φという最初の推測を使用して作成されたと仮定する。したがって、このモデルは、０°、φ、２φ、３φなどのサンプリングされた方位で作成される。物体が、ランタイムイメージ内で、これらの方位のうちの１つと正確に同一の方位で現れる場合に、完全な一致が返される（雑音またはオクルージョンなどのイメージ擾乱をすべて無視して）。例を、図１３Ａに示す。ここで、角度ステップ長の最初の推測が、２°として計算されている。ランタイムイメージ内の物体方位に関してスコア値をプロットする時に、サンプリングされた方位０°、φ、２φ、３φなどで１のスコア値が得られ、２つのサンプリングされた方位の間で１未満のスコア値が得られる。物体の方位がこれらのサンプリングされた方位から多く外れるほど、スコアが減る。最小のスコア値は、正確に２つのサンプリングされた方位の間の中央で得られる。図１３Ａの例では、最小の得られたスコアが、約０．９である。適用される認識手法に応じて、受け入れることのできる最小スコア値、たとえば０．８５を定義しなければならない。最小の得られたスコアが、図１３Ａの例のように最小スコアを超える場合に、角度ステップの最初の推測が、受け入れられる。図１３Ｂに、別の物体の例を示す。ここで、最小の得られたスコア値は、約０．７３であり、これは０．８５という最小スコアより小さい。本発明の好ましい実施形態では、その場合に、ステップ長を半分にする。その結果を、図１３Ｃに示す。ここで、最小の得られたスコア値が、約０．９３であり、これは、最小スコアを超える。角度ステップ長を半分にする処理は、最小の得られたスコア値が最小スコアを超えるまで繰り返される。本発明の好ましい実施形態では、スコアが、０°とφの間のすべての物体方位について計算されるのではなく、φ／２の方位でのみ計算される。というのは、最小スコアが、２つのサンプリングされた方位の中央にあると期待されるからである。これに関して、モデルイメージを、φ／２だけ回転し、回転されたモデルイメージと回転されないモデルの間の類似性測度を計算する。
【００５７】
本発明の代替実施形態では、ステップ長の最初の推測が計算されない。その代わりに、類似性測度が、回転されないモデルと、増分的に回転されるモデルイメージの間で計算される。最適ステップ長が見つかるのは、現在のモデルイメージ回転について得られるスコアが最小スコアと同等である場合である。最後に、最適ステップ長の値は、現在の回転角度の２倍である。
【００５８】
本発明の複数の特定の態様および実施形態を詳細に説明したが、好ましい実施形態のさまざまな変更を、本発明の趣旨および範囲から外れずに行うことができる。したがって、上の説明は、添付請求項に示されたものを除いて本発明を制限することを意図されていない。
【図面の簡単な説明】
【００５９】
【図１Ａ】エッジ振幅に関する異なる閾値を使用する長方形の例の物体のエッジを示す図である。
【図１Ｂ】エッジ振幅に関する異なる閾値を使用する長方形の例の物体のエッジを示す図である。
【図１Ｃ】エッジ振幅に関する異なる閾値を使用する長方形の例の物体のエッジを示す図である。
【図２】エッジ振幅すなわち物体のコントラストの最適閾値の計算の主要なステップを示す流れ図である。
【図３】抽出されたエッジを評価する単一ステップが示されている、エッジ振幅の最適閾値の計算の主要なステップを示す流れ図である。
【図４Ａ】４接続されたエッジを示す図である。
【図４Ｂ】８接続されたエッジを示す図である。
【図５】高い曲率のエッジ画素を決定するために侵食動作の構造化要素として使用される形態学的フィルタマスクを示す図である。
【図６Ａ】図１Ａのエッジの白い丸に関する侵食動作の結果を示す図である。
【図６Ｂ】図１Ｂのエッジの白い丸に関する侵食動作の結果を示す図である。
【図６Ｃ】図１Ｃのエッジの白い丸に関する侵食動作の結果を示す図である。
【図７Ａ】図６Ａに示された高い曲率の点でエッジを分割した後の、図１Ａのエッジの接続された成分を示す図である。
【図７Ｂ】図６Ｂに示された高い曲率の点でエッジを分割した後の、図１Ｂのエッジの接続された成分を示す図である。
【図７Ｃ】図６Ｃに示された高い曲率の点でエッジを分割した後の、図１Ｃのエッジの接続された成分を示す図である。
【図８】最適閾値を決定するのに必要なエッジ振幅の閾値に関する、エッジ領域値すなわち、物体エッジの評価の結果を示す図である。
【図９】ヒステリシス閾値化動作の最適閾値を決定するのに必要なエッジ振幅の閾値に関する、エッジ領域値すなわち、物体エッジの評価の結果を示す図である。
【図１０】成分サイズのヒストグラムを示す図、すなわち成分サイズごとに個々のサイズを有する成分の分数が可視化されている図である。
【図１１】成分サイズの累積ヒストグラムを示す図、すなわち成分サイズごとに多くとも個々のサイズを有する成分の分数が可視化されている図である。
【図１２】モデル回転の角度ステップ長φの最初の推測の計算を示す図である。
【図１３Ａ】最初の推測を受け入れることができるある物体の物体方位に関するスコアを示す図である。
【図１３Ｂ】最初の推測を半分にしなければならない第２物体の物体方位に関するスコアを示す図である。
【図１３Ｃ】最初の推測を半分にしなければならない物体方位に関するスコアを示す図である。
【符号の説明】
【００６０】
１０２  エッジ振幅を計算するステップ
１０３  閾値Ｔに最小値をセットするステップ
１０６  現在の閾値Ｔを使用してエッジ領域を計算するステップ
１０８  エッジ領域を評価するステップ
１１０  評価結果を関数ｆ（Ｔ）に保管するステップ
１１２  閾値Ｔ＜最大値であるかどうかを決定するかステップ
１１４  閾値Ｔを増分するステップ
１１６  関数ｆ（Ｔ）の極値を見つけるステップ
２００  エッジ細線化を適用するステップ
２０２  侵食マスクを適用することによって、強い曲率のエッジ画素を見つけるステップ
２０４  強い曲率のエッジ画素をエッジ領域から減算するステップ
２０６  接続された成分を計算するステップ
２０８  接続された成分を評価するステップ
【図１Ａ】
2007257601.tif 000004
【図１Ｂ】
2007257601.tif 000005
【図１Ｃ】
2007257601.tif 000006
【図２】
2007257601.tif 000007
【図３】
2007257601.tif 000008
【図４Ａ】
2007257601.tif 000009
【図４Ｂ】
2007257601.tif 000010
【図５】
2007257601.tif 000011
【図６Ａ】
2007257601.tif 000012
【図６Ｂ】
2007257601.tif 000013
【図６Ｃ】
2007257601.tif 000014
【図７Ａ】
2007257601.tif 000015
【図７Ｂ】
2007257601.tif 000016
【図７Ｃ】
2007257601.tif 000017
【図８】
2007257601.tif 000018
【図９】
2007257601.tif 000019
【図１０】
2007257601.tif 000020
【図１１】
2007257601.tif 000021
【図１２】
2007257601.tif 000022
【図１３Ａ】
2007257601.tif 000023
【図１３Ｂ】
2007257601.tif 000024
【図１３Ｃ】
2007257601.tif 000025