(57)【要約】【課題】一般シーンにおいても、十分ロバストに物体を認識することができる物体認識装置を提供する。【解決手段】Target画像認識部２０は、カメラ２１で撮像された画像をフレームメモリ２２に蓄積し、フレームメモリ２２に蓄積した画像を元にEdge画像生成部２３でEdge画像を生成する。Target特徴量抽出部２４では、Edge点を元に局所特徴量を抽出する。最後にマッチング部２５で、Target特徴量抽出部２４にて抽出した特徴量とすでにModel辞書１５に登録してあるModelの特徴量を比較することで、モデルModelとターゲットTargetのマッチングペアを取得し、物体同定部２６で取得されたマッチングペア数をもとに、Target画像内の物体を同定する。【選択図】図３
2008077626.tif 000002
【特許請求の範囲】
【請求項１】
画像内に存在する物体を認識する物体認識装置において、
物体認識の対象となる物体を含むターゲット画像からエッジ画像を生成するエッジ画像生成部と、
上記エッジ画像生成部により生成されたエッジ画像上の各エッジ点の特徴量を抽出し、エッジ画像に設定した局所領域内の各エッジ点から当該局所領域内にて注目すべきベース点と、当該ベース点をサポートするサポート点とを決定する局所特徴量抽出部と、
予め上記物体に対応して生成されたエッジ画像に設定した局所領域周辺の各エッジ点から決定された当該局所領域周辺にて注目すべきベース点とその特徴量及び当該ベース点をサポートするサポート点とその特徴量と、上記ベース点と上記サポート点の幾何学位置関係を記憶している記憶部を参照して、上記局所特徴量抽出部により抽出された特徴量を持つベース点及びサポート点との特徴量マッチングを行ってマッチングペアを取得する特徴量マッチング部と、
上記特徴量マッチング部によって得られたマッチングペアから最もマッチングコストが高いものを採用することで、最終的なマッチングペアを決定するマッチングペア決定部とを備え、
上記マッチングペア決定部によって決定されたマッチングペアを基にターゲット画像内の物体を同定することを特徴とする物体認識装置。
【請求項２】
上記局所特徴量抽出部は、固定半径の円を角度方向、距離方向に分割し、分割による各ビンに存在するエッジ点の個数をヒストグラム化することにより全てのエッジ点について局所特徴量を抽出することを特徴とする請求項１記載の物体認識装置。
【請求項３】
上記局所特徴量抽出部は、抽出した特徴量の回転不変を実現するために基準軸方向を抽出し、回転正規化を行うことを特徴とする請求項１記載の物体認識装置。
【請求項４】
上記局所特徴量抽出部は、注目点を中心とした小領域内において、周辺のエッジ点の注目点からの角度を投票し、ヒストグラムを作成し、極大値に対応する角度が基準軸方向となる基準軸を抽出することを特徴とする請求項３記載の物体認識装置。
【請求項５】
上記局所特徴量抽出部は、各点において基準軸方向の角度を求め、角度分ヒストグラムを角度方向にシフトすることにより上記特徴量の回転正規化を行うことを特徴とする請求項４記載の物体認識装置。
【請求項６】
上記局所特徴量抽出部は、任意の半径の参照円を決定し、この参照円付近の上記エッジ点について上記ベース点、及び複数の上記サポート点を決定することを特徴とする請求項１記載の物体認識装置。
【請求項７】
上記局所特徴量抽出部は、多重解像度画像生成部により生成された解像度の異なる複数の多重解像度画像毎に適切な半径の参照円を決定し、この参照円付近の上記エッジ点について上記ベース点、及び複数の上記サポート点を決定することを特徴とする請求項１記載の物体認識装置。
【請求項８】
上記特徴量マッチング部は、ターゲット上の点の基準軸にあわせ、モデルのサポート点の位置補正を行い、モデルのベース点を上記ターゲット上の点の位置に合わせ、上記モデルのベース点と上記ターゲット上の点間の特徴量コストを算出し、各サポート点については、探索領域内で特徴量コストが最小となる点を探索することを特徴とする請求項１記載の物体認識装置。
【請求項９】
上記特徴量マッチング部によって得られたマッチングペアからミスマッチペアを除去するミスマッチペア除去部をさらに備えることを特徴とする請求項１記載の物体認識装置。
【請求項１０】
画像内に存在する物体を認識するための物体認識方法において、
物体認識の対象となる物体を含むターゲット画像からエッジ画像を生成するエッジ画像生成工程と、
上記エッジ画像生成工程により生成されたエッジ画像上の各エッジ点の特徴量を抽出し、エッジ画像に設定した局所領域内の各エッジ点から当該局所領域内にて注目すべきベース点と、当該ベース点をサポートするサポート点とを決定する局所特徴量抽出工程と、
予め上記物体に対応して生成されたエッジ画像に設定した局所領域周辺の各エッジ点から決定された当該局所領域周辺にて注目すべきベース点とその特徴量及び当該ベース点をサポートするサポート点とその特徴量と、上記ベース点と上記サポート点の幾何学位置関係を記憶している記憶部を参照して、上記局所特徴量抽出工程により抽出された特徴量を持つベース点及びサポート点との特徴量マッチングを行ってマッチングペアを取得する特徴量マッチング工程と、
上記特徴量マッチング工程によって得られたマッチングペアから最もマッチングコストが高いものを採用することで、最終的なマッチングペアを決定するマッチングペア決定工程とを備え、
上記マッチングペア決定工程によって決定されたマッチングペアを基にターゲット画像内の物体を同定することを特徴とする物体認識方法。
【請求項１１】
画像内に存在する物体を認識する物体認識装置として用いられるコンピュータによって実行される物体認識プログラムにおいて、
物体認識の対象となる物体を含むターゲット画像からエッジ画像を生成するエッジ画像生成工程と、
上記エッジ画像生成工程により生成されたエッジ画像上の各エッジ点の特徴量を抽出し、エッジ画像に設定した局所領域内の各エッジ点から当該局所領域内にて注目すべきベース点と、当該ベース点をサポートするサポート点とを決定する局所特徴量抽出工程と、
予め上記物体に対応して生成されたエッジ画像に設定した局所領域周辺の各エッジ点から決定された当該局所領域周辺にて注目すべきベース点とその特徴量及び当該ベース点をサポートするサポート点とその特徴量と、上記ベース点と上記サポート点の幾何学位置関係を記憶している記憶部を参照して、上記局所特徴量抽出工程により抽出された特徴量を持つベース点及びサポート点との特徴量マッチングを行ってマッチングペアを取得する特徴量マッチング工程と、
上記特徴量マッチング工程によって得られたマッチングペアから最もマッチングコストが高いものを採用することで、最終的なマッチングペアを決定するマッチングペア決定工程とを備え、
上記マッチングペア決定工程によって決定されたマッチングペアを基にターゲット画像内の物体を同定することを特徴とする物体認識プログラム。
【請求項１２】
画像内に存在する物体を認識する物体認識処理に用いられる特徴量を登録する特徴量登録装置であって、
予め物体のモデルのエッジ画像を生成するエッジ画像生成部と、
上記エッジ画像生成部により生成したエッジ画像上の各エッジ点の特徴量を抽出し、かつ上記エッジ画像に設定した局所領域内の各エッジ点から当該局所領域内にて注目すべきベース点と、当該ベース点をサポートするサポート点とを決定し、ベース点とその特徴量及びサポート点とその特徴量、さらにベース点とサポート点との幾何学位置関係を記憶部に記憶させるモデル特徴量抽出部と
を備えてなることを特徴とする特徴量登録装置。
【請求項１３】
上記モデル特徴量抽出部は、任意の半径の参照円を決定し、この参照円付近の上記エッジ点についてベース点、及び複数のサポート点を設定し、各サポート点の上記ベース点からの相対的な位置関係を算出することを特徴とする請求項１２記載の特徴量登録装置。
【請求項１４】
上記モデル特徴量抽出部は、上記相対的な位置関係として、上記各サポート点の上記ベース点からの相対距離、相対角度を算出することを特徴とする請求項１３記載の特徴量登録装置。
【請求項１５】
上記モデル特徴量抽出部は、上記参照円付近での円全体のエッジ点のばらつき度合いを評価することにより、参照円決定のための中心画素及び半径を決定することを特徴とする請求項１３記載の特徴量登録装置。
【請求項１６】
上記モデル特徴量抽出部は、上記エッジ点のばらつき度合いの評価を、参照円半径、参照円中心から各エッジ点までの距離、固定軸からの角度を用いて算出したエントロピー値に基づいて行うことを特徴とする請求項１３記載の特徴量登録装置。
【請求項１７】
上記モデル特徴量抽出部は、上記参照円を角度方向に複数に分割し、各分割領域にサンプリング領域を設定し、このサンプリング領域内で最も参照円に近い点をサンプリング点とし、サンプリング点群から前回までのベース点の位置の履歴を参照し、前回までのベース点としての画素の周辺に存在しない点を、サンプリング点から選択し、今回のベース点とし、他をサポート点とすることを特徴とする請求項１３記載の特徴量登録装置。
【請求項１８】
上記モデル特徴量抽出部は、上記エッジ画像生成部により生成したエッジ画像上の各エッジ点の特徴量を用いて上記参照円を決定することを特徴とする請求項１３記載の特徴量登録装置。
【請求項１９】
上記モデル特徴量抽出部は、参照円上のエッジ点がもつ各局所特徴量間の距離が大きくなる領域を抽出できるときに参照円を決定することを特徴とする請求項１８記載の特徴量登録装置。
【請求項２０】
上記モデル特徴量抽出部は、所定の参照円を局所特徴量の半径に応じて分割し、各分割した部分において局所特徴量を抽出し、次に相互の特徴量間の距離を算出して相互特徴量間の距離マップを作成し、この相互特徴量間の距離マップを用いて参照円を決定することを特徴とする請求項１９記載の特徴量登録装置。
【請求項２１】
上記モデル特徴量抽出部は、特徴間距離のエントロピー値を評価基準として用いることを特徴とする請求項２０記載の特徴量登録装置。
【請求項２２】
上記モデル特徴量抽出部は、多重解像度画像生成部により生成された解像度の異なる複数の多重解像度画像毎に、適切な半径の参照円を決定し、この参照円付近の上記エッジ点について上記ベース点、及び複数の上記サポート点を決定することを特徴とする請求項１２記載の特徴量登録装置。
【請求項２３】
画像内に存在する物体を認識するための物体認識処理に用いられる特徴量を登録する特徴量登録方法であって、
予め物体のモデルのエッジ画像を生成するエッジ画像生成工程と、
上記エッジ画像生成工程により生成したエッジ画像上の各エッジ点の特徴量を抽出し、かつ上記エッジ画像に設定した局所領域内の各エッジ点から当該局所領域内にて注目すべきベース点と、当該ベース点をサポートするサポート点とを決定し、ベース点とその特徴量及びサポート点とその特徴量、さらにベース点とサポート点との幾何学位置関係を記憶部に記憶させるモデル特徴量抽出工程と
を備えてなることを特徴とする特徴量登録方法。
【請求項２４】
画像内に存在する物体を認識するための物体認識処理に用いられる特徴量を登録する装置としてのコンピュータによって実行される特徴量登録プログラムであって、
予め物体のモデルのエッジ画像を生成するエッジ画像生成工程と、
上記エッジ画像生成工程により生成したエッジ画像上の各エッジ点の特徴量を抽出し、かつ上記エッジ画像に設定した局所領域内の各エッジ点から当該局所領域内にて注目すべきベース点と、当該ベース点をサポートするサポート点とを決定し、ベース点とその特徴量及びサポート点とその特徴量、さらにベース点とサポート点との幾何学位置関係を記憶部に記憶させるモデル特徴量抽出工程と
を備えてなることを特徴とする特徴量登録プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像内に存在する物体を認識する物体認識装置及び物体認識方法に関する。また、画像内に存在する物体を認識する物体認識装置によって実行される物体認識プログラムに関する。また、画像内に存在する物体を認識する物体認識装置に用いられる特徴量登録装置及び特徴量登録方法に関する。また、特徴量登録装置によって実行される特徴量登録プログラムに関する。
【背景技術】
【０００２】
カメラから取得した画像から、その画像内に存在する物体認識の研究は、古くから行われてきた。従来は、物体を大局的に記述、つまり物体全体のテクスチャのテンプレートを用意し、このテンプレートを物体全体にあてはめるように利用したマッチングにより、認識を行う方法が主流であった。しかし、この方法では、物体全体が見えていることが望ましく、例えば取得した画像内の物体の部分的な隠れや回転などに対して対応することは非常に困難であった。
【０００３】
しかし、近年では、下記非特許文献１に代表されるように、物体を局所的な特徴量で記述し、その局所特徴量同士のマッチングを行うことで、取得した画像内の物体の部分的な隠れや回転などに非常にロバストな方法が提案され、成功を収めている。しかしながら、上記の手法は物体にテクスチャが多い物体では非常に有効であるが、テクスチャが少ない
物体に関しては適用が困難である。
【０００４】
一方、テクスチャが少ない物体の認識に関しては、物体の輪郭形状、つまりエッジ（Edge）情報を用いる手法が数多く提案されてきた。Edge情報を利用した認識方法においても、大局的な記述方法が主流であったが、一般画像において、物体全体の輪郭を抽出することは非常に困難であり、また前述のように部分的な隠れに弱いといった問題が存在する。しかし、最近では前述したテクスチャベース局所特徴量での記述方法の成功を受け、下記非特許文献２、３のように、Edge情報を局所的に記述する方法が提案されてきた。
【０００５】
【非特許文献１】D.G.Lowe，“Object Recognitionfrom local scale-invariant features”， ICCV， 1999
【非特許文献２】S.Belongie， J.Malik， J.Puzicha， “Shape Matching and Object Recognition Using Shape Contexts”， PAMI， 2002
【非特許文献３】F.Jurie and C.Schmid， “Scale-invariant shape features for recognition of object categories”， CVPR， 2004
【非特許文献４】J.R.Parker， “Algorithms for Image Processing and Computer Vision”， John Wiley & Sons， Inc.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、上記非特許文献２、非特許文献３に記載の、Edge情報を局所的に記述する方法にあっても、一般シーンにおいて、十分ロバストな方法は確立されていないのが現状である。
【０００７】
本発明は、上記実情に鑑みてなされたものであり、一般シーンにおいても、十分ロバストに物体を認識することができる物体認識装置及び物体認識方法の提供を目的とする。
【０００８】
また、上記物体認識処理に用いられる特徴量を登録する特徴量登録装置及び特徴量登録方法の提供を目的とする。
【０００９】
また、上記物体認識装置にて実行される物体認識プログラム、上記特徴量登録装置にて実行される特徴量登録プログラムの提供を目的とする。
【課題を解決するための手段】
【００１０】
本発明に係る物体認識装置は、上記課題を解決するために、物体認識の対象となる物体を含むターゲット画像からエッジ画像を生成するエッジ画像生成部と、上記エッジ画像生成部により生成されたエッジ画像上の各エッジ点の特徴量を抽出し、エッジ画像に設定した局所領域内の各エッジ点から当該局所領域内にて注目すべきベース点と、当該ベース点をサポートするサポート点とを決定する局所特徴量抽出部と、予め上記物体に対応して生成されたエッジ画像に設定した局所領域周辺の各エッジ点から決定された当該局所領域周辺にて注目すべきベース点とその特徴量及び当該ベース点をサポートするサポート点とその特徴量と、上記ベース点と上記サポート点の幾何学位置関係を記憶している記憶部を参照して、上記局所特徴量抽出部により抽出された特徴量を持つベース点及びサポート点との特徴量マッチングを行ってマッチングペアを取得する特徴量マッチング部と、上記特徴量マッチング部によって得られたマッチングペアから最もマッチングコストが高いものを採用することで、最終的なマッチングペアを決定するマッチングペア決定部とを備え、上記マッチングペア決定部によって決定されたマッチングペアを基にターゲット画像内の物体を同定する。
【００１１】
この物体認識装置は、テクスチャの少ない物体の認識処理において、物体の輪郭から局所的な特徴量を抽出し、さらにその周辺の特徴量とその幾何学的位置関係を利用した、輪郭記述、及びそのマッチングを行う。
【００１２】
本発明に係る物体認識方法は、上記課題を解決するために、物体認識の対象となる物体を含むターゲット画像からエッジ画像を生成するエッジ画像生成工程と、上記エッジ画像生成工程により生成されたエッジ画像上の各エッジ点の特徴量を抽出し、エッジ画像に設定した局所領域内の各エッジ点から当該局所領域内にて注目すべきベース点と、当該ベース点をサポートするサポート点とを決定する局所特徴量抽出工程と、予め上記物体に対応して生成されたエッジ画像に設定した局所領域周辺の各エッジ点から決定された当該局所領域周辺にて注目すべきベース点とその特徴量及び当該ベース点をサポートするサポート点とその特徴量と、上記ベース点と上記サポート点の幾何学位置関係を記憶している記憶部を参照して、上記局所特徴量抽出工程により抽出された特徴量を持つベース点及びサポート点との特徴量マッチングを行ってマッチングペアを取得する特徴量マッチング工程と、上記特徴量マッチング工程によって得られたマッチングペアから最もマッチングコストが高いものを採用することで、最終的なマッチングペアを決定するマッチングペア決定工程とを備え、上記マッチングペア決定工程によって決定されたマッチングペアを基にターゲット画像内の物体を同定する。
【００１３】
本発明に係る物体認識プログラムは、上記課題を解決するために、画像内に存在する物体を認識する物体認識装置によって実行される物体認識プログラムにおいて、物体認識の対象となる物体を含むターゲット画像からエッジ画像を生成するエッジ画像生成工程と、上記エッジ画像生成工程により生成されたエッジ画像上の各エッジ点の特徴量を抽出し、エッジ画像に設定した局所領域内の各エッジ点から当該局所領域内にて注目すべきベース点と、当該ベース点をサポートするサポート点とを決定する局所特徴量抽出工程と、予め上記物体に対応して生成されたエッジ画像に設定した局所領域周辺の各エッジ点から決定された当該局所領域周辺にて注目すべきベース点とその特徴量及び当該ベース点をサポートするサポート点とその特徴量と、上記ベース点と上記サポート点の幾何学位置関係を記憶している記憶部を参照して、上記局所特徴量抽出工程により抽出された特徴量を持つベース点及びサポート点との特徴量マッチングを行ってマッチングペアを取得する特徴量マッチング工程と、上記特徴量マッチング工程によって得られたマッチングペアから最もマッチングコストが高いものを採用することで、最終的なマッチングペアを決定するマッチングペア決定工程とを備え、上記マッチングペア決定工程によって決定されたマッチングペアを基にターゲット画像内の物体を同定する。
【００１４】
本発明に係る特徴量登録装置は、上記課題を解決するために、画像内に存在する物体を認識する物体認識処理に用いられる特徴量を登録する特徴量登録装置であって、予め物体のモデルのエッジ画像を生成するエッジ画像生成部と、上記エッジ画像生成部により生成したエッジ画像上の各エッジ点の特徴量を抽出し、かつ上記エッジ画像に設定した局所領域内の各エッジ点から当該局所領域内にて注目すべきベース点と、当該ベース点をサポートするサポート点とを決定し、ベース点とその特徴量及びサポート点とその特徴量、さらにベース点とサポート点との幾何学位置関係を記憶部に記憶させるモデル特徴量抽出部とを備えてなる。
【００１５】
本発明に係る特徴量登録方法は、上記課題を解決するために、画像内に存在する物体を認識するための物体認識処理に用いられる特徴量を登録する特徴量登録方法であって、予め物体のモデルのエッジ画像を生成するエッジ画像生成工程と、上記エッジ画像生成工程により生成したエッジ画像上の各エッジ点の特徴量を抽出し、かつ上記エッジ画像に設定した局所領域内の各エッジ点から当該局所領域内にて注目すべきベース点と、当該ベース点をサポートするサポート点とを決定し、ベース点とその特徴量及びサポート点とその特徴量、さらにベース点とサポート点との幾何学位置関係を記憶部に記憶させるモデル特徴量抽出工程とを備えてなる。
【００１６】
本発明に係る特徴量登録プログラムは、上記課題を解決するために、画像内に存在する物体を認識するための物体認識処理に用いられる特徴量を登録する装置によって実行される特徴量登録プログラムであって、予め物体のモデルのエッジ画像を生成するエッジ画像生成工程と、上記エッジ画像生成工程により生成したエッジ画像上の各エッジ点の特徴量を抽出し、かつ上記エッジ画像に設定した局所領域内の各エッジ点から当該局所領域内にて注目すべきベース点と、当該ベース点をサポートするサポート点とを決定し、ベース点とその特徴量及びサポート点とその特徴量、さらにベース点とサポート点との幾何学位置関係を記憶部に記憶させるモデル特徴量抽出工程とを備えてなる。
【００１７】
とくに、本発明では、物体輪郭をベース点で抽出した局所的な特徴量とその周辺の点(サポート点)の局所的な特徴量、及びその幾何学的な位置関係によって記述している。
【００１８】
各局所特徴量は、回転不変である。局所的な輪郭に応じて、ベース点、サポート点を適応的に決定可能である。
【００１９】
また、各局所特徴量のマッチングとしてベース点及び、サポート点を利用したロバストで柔軟なマッチングが可能である。ベース点のマッチングコストを利用し、サポート点の対応点も取得することで、効率的にマッチングペアを取得できる。
【００２０】
また、物体間に存在する幾何拘束を利用することで、ミスマッチを効率的に除去可能である。
【発明の効果】
【００２１】
本発明によれば、局所的な特徴量記述を採用しているため、対象物体の部分的な隠れに対してロバストである。また、各局所特徴量は回転正規化することで、対象物体の回転に対応可能である。また、局所領域の特徴記述は、注目点の特徴量とその周辺の特徴量、及びその幾何学関係を利用しているため、対応点検出の精度が高く、ロバストである。また、局所的な輪郭形状に合わせ、適応的にサポートする点を選択できるため、対応点検出の精度が高く、ロバストである。また、対応点探索時に、サポート点については、小領域内での最も類似度の高い点の探索を行うため、サポート点位置補正で生じる誤差の吸収が可能であり、また対称物体の歪みにたいしても対応可能である。
【００２２】
また、Modelのベース点の対応点決定時のコストを、そのサポート点の対応点のコストとして利用することで、効率的、かつよりロバストにマッチングペアを取得可能である。また、物体間のマッチングペアに存在する幾何拘束を利用することで、ミスマッチを除去することができ、ロバストな認識が可能となる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明を実施するための最良の形態について図面を参照しながら説明する。第１の実施の形態は、画像内に存在する物体を認識する物体認識装置１であり、図１に示すように、モデル（Model）の特徴量を登録するモデル特徴量登録部１０と、モデル特徴量登録部１０で登録されたモデル特徴量に基づいて画像内のターゲット（Target）がどの物体であるかを認識するターゲット画像認識部２０という二つに分かれる。
【００２４】
モデル特徴量登録部１０は、あらかじめ、上記物体のモデルのエッジ画像を生成し、生成したエッジ画像上のエッジ点の局所特徴量、及びそれをサポートする点を抽出し、それらの幾何学的位置関係とともに辞書に登録する。
【００２５】
ターゲット画像認識部２０は、物体認識の対象となる物体を含むターゲット画像からエッジ画像を生成し、生成したエッジ画像上のエッジ点の局所特徴量を抽出し、抽出した特徴量と上記モデル特徴量登録部１０で辞書に登録されたモデル特徴量とを比較することで、モデルとターゲットのマッチングペアを取得し、取得されたマッチングペア数をもとに、Target画像内の物体を同定する。
【００２６】
モデル特徴量登録部１０は、図２に示すように、カメラ１１で撮像された画像をフレームメモリ１２に蓄積し、フレームメモリ１２に蓄積した画像を元にエッジ（Edge）画像生成部１３でEdge画像を生成する。Model特徴量抽出部１４では、Edge画像をもとに、局所特徴量、及びそれをサポートする点の抽出を行い、その幾何学的位置関係を算出し、ModelごとにModel辞書１５に登録する。モデル辞書１５に登録される、モデル毎の局所特徴量、それをサポートするサポート点、その幾何学的位置関係については詳細を後述する。
【００２７】
ターゲット（Target）画像認識部２０は、図３に示すように、カメラ２１で撮像された画像をフレームメモリ２２に蓄積し、フレームメモリ２２に蓄積した画像を元にEdge画像生成部２３でEdge画像を生成する。Target特徴量抽出部２４では、Edge点を元に局所特徴量を抽出する。最後にマッチング部２５で、Target特徴量抽出部２４にて抽出した特徴量とすでにModel辞書１５に登録してあるModelの特徴量を比較することで、モデルModelとターゲットTargetのマッチングペアを取得し、物体同定部２６で取得されたマッチングペア数をもとに、Target画像内の物体を同定する。
【００２８】
まず、モデル特徴量登録部１０における処理について説明する。図４は、モデル特徴量登録部１０におけるModel記述例（局所領域記述例）を示す図である。本発明では、物体形状を表すEdge画像の局所領域を、図４（Ａ）に示すように、参照円Ｒとし、この参照円Ｒ付近のEdge点について、ベース点ｂ、及びサポート点ｓ１，ｓ２，ｓ３を設定する。
【００２９】
そして、図４（Ｂ）に示すように、各サポート点ｓ１，ｓ２，ｓ３のベース点ｂからの相対的な位置関係を、相対距離ｒ１，ｒ２，ｒ３、相対角度θ１，θ２，θ３で記述する。但し、ベース点ｂ，サポート点ｓ１，ｓ２，ｓ３はそれぞれ特徴量を持つものとする。輪郭の局所領域を、注目点（ベース点ｂ）の特徴量、周辺の点（サポート点ｓ１，ｓ２，ｓ３）の特徴量及びその位置関係（相対距離r１，ｒ２，ｒ３、相対角度θ１，θ２，θ３）を拘束として用いることで、柔軟かつロバストな記述が可能となる。
【００３０】
以上の説明から、局所的なModel記述に必要な要素は、［１］Edge画像の生成、［２］Edge点の局所特徴量抽出、［３］参照円Ｒiの決定、［４］ベース点ｂi，サポート点ｓijの決定、［５］各サポート点の相対角度θij、相対距離ｒijの決定となる。
【００３１】
次に、上記各要素に基づいた処理について、図５に示すフローチャートを参照して説明する。ステップＳ１にてEdge画像を生成（Edge画像生成部１３）し、ステップＳ２にてEdge点の局所特徴量抽出（Model特徴量抽出部１４）し、ステップＳ３にて参照円Ｒiを決定し、ステップＳ４にてベース点ｂi及びサポート点ｓijを決定し、ステップＳ５にて各サポート点の相対角度θij、相対距離ｒijを決定することとなる。
【００３２】
以下、各処理について説明する。まず、ステップＳ１におけるEdge画像作成処理について説明する。ここでは、グレースケール画像からEdge画像を生成する方法を示す。Edge抽出は、様々な方法があるが、安定性、正確性の観点ではカニーエッジフィルタ（Canny-Edge Filter）が有名であり、ここでのEdge抽出処理にもカニーエッジフィルタを利用する。
【００３３】
カニーエッジフィルタは前記非特許文献４で詳しく説明されている。ここでは、図６を用いて処理手順を説明しておく。
【００３４】
まず、ステップＳ１１にてスムーシング（Smoothing）処理を行う。ガウスフィルタＧ(ｘ，ｙ)を画像ｆ(ｘ，ｙ)に適用することにより、画像内のノイズ及び細かなテクスチャの削減を行う。具体的には，以下の（１）式に示すようにガウスフィルタＧ(ｘ，ｙ)と画像ｆ(ｘ，ｙ)の畳み込みを行い、画像ｇ(ｘ，ｙ)を得る。ガウスフィルタＧ(ｘ，ｙ)は、（２）式で示される。
【００３５】
【数１】
2008077626.tif 000003
【００３６】
【数２】
2008077626.tif 000004
【００３７】
次に、ステップＳ１２にて、ｘ方向及びｙ方向の勾配ｇｘ(ｘ，ｙ)及びｇｙ(ｘ，ｙ)を算出する。ステップＳ１１で作成したSmooting画像ｇ(ｘ，ｙ)に、図７（Ａ）及び図７（Ｂ）に示す微分フィルタを適用し、勾配画像を作成する。つまり、ｇｘ(ｘ，ｙ)の作成には、図７（Ａ）のｘ方向フィルタを、ｇｙ(ｘ，ｙ)の作成には図７（Ｂ）に示すｙ方向フィルタを適用する。
【００３８】
次に、ステップＳ１３にて、Edge強度及びEdge角度を算出する。上記ステップＳ１２で作成した勾配画像ｇｘ(ｘ，ｙ)、ｇｙ(ｘ，ｙ)を用いて、Edge強度画像Ｍ(ｘ，ｙ)、Edge角度画像θ(ｘ，ｙ)を以下の（３）、（４）式により生成する。
【００３９】
【数３】
2008077626.tif 000005
【００４０】
【数４】
2008077626.tif 000006
【００４１】
次に、ステップＳ１４にて、Edgeの細線化を行う。これまで生成したEdge強度画像Ｍ(ｘ，ｙ)は部分的に数ピクセルの幅をもっている。これを１ピクセルの幅になるよう細線化処理を施す。具体的には、Ｍ(ｘ，ｙ)が０でない点(ｘ，ｙ)について、その点のEdge方向θ(ｘ，ｙ)にある点(ｘ１，ｙ１)、及び反対のEdge方向の点(ｘ２，ｙ２)が持つＭ(ｘ１，ｙ１)，Ｍ(ｘ２， ｙ２)の値とを比較する。点(ｘ，ｙ)の強度Ｍ(ｘ，ｙ)がＭ(ｘ１，ｙ１)，Ｍ(ｘ２，ｙ２)より小さい場合は、その点はEdge点ではないとして，Ｍ(ｘ，ｙ)を０とする。
【００４２】
そして、最後にステップＳ１５によりEdge検出を行う。ここでは、ステップＳ１４で生成した細線化されたEdge強度画像から閾値処理により、Edge画像を生成する。Canny Edge Filterでは、ここでの閾値処理に２つの閾値(T_high，T_low)を用いる。具体的には、点(ｘ，ｙ)のEdge強度Ｍ(ｘ，ｙ)がT_highより大きい場合、その点をスタート点とし、Edge強度がT_low以上の点をトレースしていき、その点はEdge点としていく。
【００４３】
Canny Edgeフィルタでのパラメータは、ステップＳ１１で用いるSmoothingの度合いσ，ステップＳ１５で用いるEdge検出のための２つの閾値、 T_high, T_lowとなる。これらを予め適切な値に設定しておくことで、高精度なEdge検出が可能となる。
【００４４】
以上、図５におけるステップＳ１でのEdge画像生成処理の具体例（例えばカニーエッジフィルタ）を説明した。次に、図５の処理手順のステップＳ２に進む。
【００４５】
ステップＳ２では、Edge点の局所特徴量抽出を行う。ステップＳ１にて抽出された全てのEdge点について、局所特徴量の抽出を行う。本発明で求める特徴量は、図８に示すように固定半径の円を角度方向、距離方向に分割し、各Binに存在するEdge点の個数をヒストグラム化したものである。局所特徴量抽出の半径、角度方向（円周方向）、距離方向（半径方向）の分割数は特に限定しない。
【００４６】
なお、このステップＳ２では、抽出した特徴量の回転不変を実現するために、基準軸方向を抽出し、回転正規化を行う。基準軸の抽出は、図９に示すように、注目点を中心とした小領域内において、周辺のEdge点の注目点からの角度を投票し、ヒスグラムを作成する。その極大値に対応する角度が基準軸方向となる。以上により、各点において基準軸の角度が求まれば、図１０に示すように、その角度分ヒストグラムを角度方向にシフトすることで、特徴量の回転正規化を行うことが可能となる。
【００４７】
ステップＳ２にて抽出した特徴量は、基準軸の角度とともにF_Mapに保存する。次に、ステップＳ３にて、参照円Ｒを決定する。参照円Ｒ決定の基本的な概念は、円の周辺にエッジ点が十分ばらついているかどうかを調べることである。
【００４８】
以下、参照円Ｒの決定方法を詳細に説明する。物体の輪郭は局所的に様々であり、前述した、幾何拘束を利用するためには、参照円の大きさは各局所領域で異なる必要がある。
【００４９】
図１１（Ａ）に示すように、円半径が一定である場合、参照円Ｒ１の領域では十分な幾何拘束を得ることができない。一方図１１（Ｂ）のように参照円Ｒ１の円半径を大きく変えた領域とすることで、参照円Ｒ１'に示すように十分な拘束を得ることが可能となる。ここでは、参照円Ｒ１'によりエッジ点が２つ増えている。もちろん物体の輪郭によっては、参照円の円半径を小さく変えた領域とすることによっても十分な拘束を得ることができる。
【００５０】
以下に、図１２及び図１３を用いて具体的な参照円Ｒの決定方法を説明する。参照円Ｒを決定するためには、その中心画素、及び半径を決定する必要がある。基本的な概念は、参照円周辺で十分な幾何拘束を得られる領域を抽出することである。そのために、参照円付近での円全体のEdge点のばらつき度合いを評価する。
【００５１】
具体的には、Edge点のばらつきの評価基準は、図１２に示すように、参照円半径ｒ、参照円中心ｃからの各Edge点ｐiの距離ｄとｘ軸からの角度φを用いて次の（５）式で示すエントロピー値で表す。
【００５２】
【数５】
2008077626.tif 000007
【００５３】
ここでは、参照円の角度をＭ段階に量子化し、ｋはｋ=１〜Ｍの値をとる。ｈ（k,c,r）は次の（６）式で示される。
【００５４】
【数６】
2008077626.tif 000008
【００５５】
但し、Ｋ(ｘ)はスムージングカーネルで、次の（７）式で表される。
【００５６】
【数７】
2008077626.tif 000009
【００５７】
エントロピー値Ｈ(ｃ，ｒ)は、参照円上付近のEdgeが円全体に十分なばらつきを持つ程大きくなる。エントロピー値が大きくなれば、円のなかで十分エッジ点がならんでいるだろうという評価である。
【００５８】
まず、エッジ点ではない点に注目して、徐々に円を大きくしていく。その都度エントロピー値を求めて、一番大きくなったエントロピー値のときの半径を保存しておく。すべての点についての半径を調べる。そのなかでエントロピー値の大きいものを選ぶと、その物体にエッジ点が多数乗っていることになる。
【００５９】
この指標を用いた画像上の任意点iにおける参照円抽出処理（参照円決定処理）の流れを図１３に示す。
【００６０】
まず、予め設定している、参照円の最小半径ｓｔ_ｒを半径として設定し、Ｈ_ｍａｘを０にしておく（ステップＳ２１）。次に、上記（５）式により、この半径でのエントロピーＨｉ=Ｈ(ｃｉ，ｒ)を算出する（ステップＳ２２）。
【００６１】
ステップＳ２３では、ステップＳ２２で算出したエントロピーＨｉがＨ_ｍａｘより大きいか否かをチェックする。エントロピーＨｉがＨ_ｍａｘより大きいと判定する（ＹＥＳ）とステップＳ２４に進み、小さいと判定する（ＮＯ）とステップＳ２５に進む。
【００６２】
ステップＳ２４では、Ｈ_ｍａｘ=Ｈｉとし、r_ｍａｘ=ｒとする。ステップＳ２５では、予め設定している半径の更新ステップｒ_ｓｔｅｐにより、順次半径を変更する。ステップＳ２６では、半径ｒがしきい値ｒ_ｔｈｒｅｓｈより大きいか否かをチェックする。半径ｒがしきい値ｒ_ｔｈｒｅｓｈより大きければ（ＹＥＳ）この処理手順を終了し、小さければ（ＮＯ）ステップＳ２２に戻る。
【００６３】
このように、ステップＳ２２〜Ｓ２６の繰り返しにより、予め設定している半径の更新ステップで、順次半径を変更しながら、エントロピーを算出し、最大エントロピーＨｉ_ｍａｘ、及びその時の参照円の半径ｒ_ｍａｘを保存する。
【００６４】
この処理を画像上のすべての点で行うことで、図１４に示すような、各画素におけるエントロピーの最大値Ｈ_ｍａｘ、及び参照円の半径ｒ_ｍａｘを保存したマップＥ_Ｍａｐを得ることができる。
【００６５】
続いて、マップＥ_Ｍａｐのエントロピー値を使って、ノンマキシマムサプレッションnon-maximum suppressionを行う。つまり、注目画素の近傍領域（８近傍、１６近傍など）において、注目画素が極大値でない場合は、マップＥ_Ｍａｐが保持するエントロピー値、半径値を０とする。
【００６６】
最後に事前に設定した最小エントロピー値により閾値処理をすることで、最終的なＥ_Ｍａｐが生成される。Ｅ＿Ｍａｐは、画像サイズと同様の大きさを持ち、各画素にはエントロピー値と円の半径を保持しているため、エントロピー値が０でない画素の位置が参照円の中心となり、これにより参照円Ｒiを決定することが可能となる。
【００６７】
上記図５のフローチャートにあってステップＳ３で参照円Ｒiを決定したあとには、ステップＳ４にてベース点とサポート点を決定する。以下、ステップＳ３にて得られた参照円Ｒｉ（ｉ＝１〜Ｎ）とEdge画像を用いて、ベース点ｂｉ、サポート点ｓｉｊを決定する方法について述べる。但し、参照円の選択順序は、ステップＳ３で得られるＥ＿Ｍａｐにおけるエントロピー値の降順とする。
【００６８】
まず、各点のサンプリングは、図１５に示すように参照円を角度方向にＭ分割する。分割数Ｍは、参照円の半径に応じて変化させる。さらに、分割した各Ｂｉｎにサンプリング領域を設定する。例えば、図１５に示すように、分割した円弧の中心付近にサンプリング領域Ａsamを設定する。このサンプリング領域内でもっとも参照円に近い点をサンプリング点ｍｉｊ（ｊ＝１〜Ｍ）とする。
【００６９】
続いて、サンプリング点群からベース点を決定する。本発明では、物体形状はベース点の集合によって記述することから、ベース点はEdge画像全体に広がっていることが望ましい。そこで、ここでは、ベース点として決定された位置の履歴を参照する方法を採用する。つまり、前回までのベース点の位置の履歴を参照し、その画素の周辺に存在しない点を、サンプリング点ｍｉｊ（ｊ＝１〜Ｍ）中から選択し、今回のベース点、その他をサポート点とする。また、逐次履歴は更新していく。
【００７０】
次に、図５のステップＳ５にて、各サポート点の相対角度θｉｊ、相対距離ｒｉｊを決定する。上記ステップＳ４により、ベース点ｂｉ（ｉ＝１〜Ｎ）、及びそのサポート点ｓｉｊ（ｊ＝１〜Ｍ）が決定されたので、ここでは、ベース点の基準軸方向を用いて、各サポート点ｓｉｊ（ｊ＝１〜Ｍ）のベース点ｂからの相対位置を決定する。図１６（Ａ）、図１６（Ｂ）に示す相対角度θｉｊ、相対距離ｒｉｊの決定は、ステップＳ２によりベース点の基準軸方向が算出されているため、容易に算出可能である。
【００７１】
以上の処理により、Model画像から得られる情報は、抽出されたベース点の数をＮとした場合、以下のようになり、Model特徴量として、辞書に登録される。
【００７２】
ｉ＝１〜Ｎとしたとき、ベース点の位置（ｂｘｉ、ｂｙｉ）、ベース点の特徴量ｂｆｉ、ベース点の基準軸方向ｂθｉが辞書に登録される。
【００７３】
また、ｊ＝１〜Ｍとしたとき、サポート点の相対位置（θｉｊ、ｒｉｊ）、サポート点の特徴量ｓfｉｊ、サポート点の基準軸方向ｓθｉｊが辞書に登録される。特にサポート点は、領域によって何個あるかは変わってくる。
【００７４】
次にTarget画像認識部２０における処理について説明する。ここでTarget画像の認識とは、Target画像が、Model辞書１５に登録されているどのModelに最も類似しているかを調べることである。
【００７５】
類似度を図る方法は様々な方法があるが、例えばModelが持つＮ個の特徴点と、Targetの各点について特徴量同士のコストを算出し、このコスト値が十分高い点をマッチングペアとして保存する。得られたマッチングペア数Ｍが十分に多ければ、Targetはそのモデルとして同定することができる。
【００７６】
図１７は、Target画像とModelでのマッチングペア取得処理の流れを示したフローチャートである。フレームメモリ２２に蓄積されたターゲット画像から、ステップＳ３１にてEdge画像生成部２３がEdge画像を生成する。次に、ステップＳ３２により、ステップＳ３１で生成したEdge画像の局所特徴量を抽出する。次に、ステップＳ３３にてModel特徴量を参照して特徴量マッチングを行う。最後にステップＳ３５によりマッチングペアが取得される。
【００７７】
以下、各処理について説明する。ステップＳ３１でのEdge画像生成処理は、Model特徴量抽出同様の処理（ステップＳ１）と同様である。ステップＳ３２の局所特徴量抽出は、ステップＳ３１で生成した、Target画像の各Edge点について、局所特徴量を抽出するものである。具体的には、Model特徴量抽出処理（ステップＳ２）と同様の処理を行う。なお、このステップＳ３２では、ベース点、サポート点について局所特徴量を抽出するのではなく、すべてのエッジ点について局所特徴量を抽出する。
【００７８】
次に、ステップＳ３３における特徴量マッチングについて説明する。ここでは、Model辞書に登録されているModel特徴量と局所特徴量抽出処理(ステップＳ３２)で抽出したTarget特徴量のマッチングを行い、ModelとTargetのマッチングペアを取得する。
【００７９】
以下具体的な特徴量同士のマッチング方法について説明する。上述したように、本発明でのModel特徴記述は、一つのベース点ｂｉに対し、複数のサポート点ｓｉｊを持つ。さらに、本発明では、Modelを大きさの異なる複数の領域で表現しているため、図１８に示すように、各ベース点、サポート点は、他のサポート点と重複する可能性がある。図１８にあって、Modelは３つのベース点ｂ１，ｂ２及びｂ３で表現されるものとする。Modelのベース点ｂ１のサポート点はｓ１１，ｓ１２，ｓ１３及びｓ１４である。また、Modelのベース点ｂ２のサポート点はｓ２１（ｂ１），ｓ２２及びｓ２３である。また、Modelのベース点ｂ３のサポート点はｓ３１（ｂ２），ｓ３２及びｓ３３（ｓ２２）である。ここで、ベース点ｂ２のサポート点ｓ２１は（）内に示したようにベース点ｂ１である（ｓ２１＝ｂ１）。また、ベース点ｂ３のサポート点ｓ３１は（）内に示したようにベース点ｂ２である（ｓ３１＝ｂ２）。また、サポート点ｓ２２は、ベース点ｂ２のサポート点であるとともに、ベース点ｂ３のサポート点ｓ３３でもある。まとめて示すと、ベース点ｂ１はベース点ｂ２のサポート点（ｂ１＝ｓ２１）、ベース点ｂ２はベース点ｂ３のサポート点（ｂ２＝ｓ３１）、点ｓ２２は、ベース点ｂ２及びベース点ｂ３のサポート点（ｓ２２＝ｓ３３）となっている。
【００８０】
図１９（Ａ）は、Modelのベース点ｂ１とTarget上の点ｐ’のマッチング方法を示したものである。まず、Target上の点ｐ'の基準軸にあわせ、Modelのサポート点ｓの位置補正を行う。具体的には、Modelのベース点ｂ1が持つ基準軸方向ｎθ、Target上の点ｐ'が持つ基準軸方向ｎ'θを用いて、図１９（Ｂ）に示すとおりの位置補正を行う。つまり、Modelのベース点ｂ１が持つ基準軸方向ｎθを、Targetの点ｐ’が持つ基準軸方向ｎ’θとの差ｄθ分だけ矢印方向に傾ける。
【００８１】
続いて、ベースｂ1を点ｐ'の位置にあわせ、ｂ1-ｐ'間の特徴量コストｄ(ｂ1，ｐ')を算出し、各サポート点については、図１９（Ｃ）に示す、探索領域内で特徴量コストｄ(ｓ1j，ｐ'k)が最小となる点を探索する。このように探索領域内で最もマッチする点を探すことで、サポート点の位置補正に用いる基準軸方向の誤差を吸収することができ、さらにTarget画像の歪みについても対応することが可能となる。
【００８２】
Model点をｍ、Target点をｔとすると、局所特徴量間の距離を表すｄ(m，t)は、次の（８）式で表せる。
【００８３】
【数８】
2008077626.tif 000010
【００８４】
ここで、hm(k)はModel点のヒストグラム特徴量、ht(k)はTarget点のヒストグラム特徴量を表す。
【００８５】
また、ベース点、及びサポート点をあわせたTotalのマッチングコストは、次の（９）式で表せる。
【００８６】
【数９】
2008077626.tif 000011
【００８７】
ここで、α1j、β1jはそれぞれ、角度、距離のペナルティコストであり、次の（１０）式となる。
【００８８】
【数１０】
2008077626.tif 000012
【００８９】
また、θｐ'k、ｒｐ'kは各サポート点に最もマッチする点ｐ’kのベース点ｂiからの角度、及び距離である。
【００９０】
以上の計算をTarget上の全ての点について行い、最大コストを持つ点をモデルのベース点ｂ１の対応点ｂ’１とする。例えば、前述の図１８を参照すると、ベース点ｂ１の各サポート点（ｓ１１，ｓ１２，ｓ１３、ｓ１４）についても対応点（ｓ’１１，ｓ’１２，ｓ’１３、ｓ’１４）が得られる。このため、ここでは、ベース点、サポート点の各対応点とともに、最大コスト値Cost(ｂ１，ｂ’１)、及び基準軸方向の差ｄθを保存する。
【００９１】
具体的な例を図２０〜図２３を参照して説明する。図２０は前記図１８と同様に各ベース点、サポート点は、他のサポート点と重複する可能性があることを示している。この図２０のModelとTargetにおいて、各ベース点のマッチング後に得られる結果を以下に説明する。図２１（Ａ）はModelの上記ベース点ｂ１とサポート点ｓ１１，ｓ１２，ｓ１３及びｓ１４に対応するTarget上の点を示す。また、図２１（Ｂ）はModelの上記ベース点ｂ２とサポート点ｓ２１，ｓ２２及びｓ２３に対応するTarget上の点を示す。また、図２１（Ｃ）はModelの上記ベース点ｂ３とサポート点ｓ３１，ｓ３２およびｓ３３に対応するTarget上の点を示す。
【００９２】
また、図２２にはModel上の点：Target上の点：コスト値で表現したマッチング後に得られる結果を符号４１、４２及び４３を付して示す。コスト値は前述の式（９）にて得られる。符号４１はコスト１が得られた結果を示している。上記ベース点ｂ１に対するTarget上の点ｂ‘１のとき、上記サポート点ｓ１１に対する点ｓ’１１のとき、上記サポート点ｓ１２に対する点ｓ’１２のとき、上記サポート点ｓ１３に対する点ｓ’１３のとき、上記サポート点ｓ１４に対する点ｓ’１４のときである。符号４２はコスト２が得られた結果を示している。上記ベース点ｂ２に対するTarget上の点ｂ‘２のとき、上記サポート点ｓ２１に対する点ｓ’２１のとき、上記サポート点ｓ２２に対する点ｓ’２２のとき、上記サポート点ｓ２３に対する点ｓ’２３のときである。符号４３はコスト３が得られた結果を示している。上記ベース点ｂ３に対するTarget上の点ｂ‘３のとき、上記サポート点ｓ３１に対する点ｓ’３１のとき、上記サポート点ｓ３２に対する点ｓ’３２のとき、上記サポート点ｓ３３に対する点ｓ’３３のときである。
【００９３】
前述したように、ｂ１＝ｓ２１、ｂ２＝ｓ３１、ｓ２２＝ｓ３３であることから、この３点については図２３に示すように２つの対応点を取得することが可能となる。符号５１はｂ１（＝ｓ２１）の二つの対応点を示している。二つの対応点のコストはｂ１：ｂ’１：Ｃｏｓｔ１、ｓ２１（ｂ１）：ｓ’２１：Ｃｏｓｔ２である。また、符号５２はｂ２（＝ｓ３１）の二つの対応点を示している。コストはｂ２：ｂ‘２：Ｃｏｓｔ２、ｓ３１（ｂ２）：ｓ’３１：Ｃｏｓｔ３である。また、符号５３はｓ２２（＝ｓ３３）の二つの対応点を示している。コストはｓ２２：ｓ‘２２：Ｃｏｓｔ２、ｓ２２（ｓ３３）：ｓ’３３：Ｃｏｓｔ３である。ここで、マッチング時のコスト計算は上記式（９）に示すように、ベース点、及びサポート点のセットに依存する。さらにTarget画像のオクルージョン（Occlusion）の影響などにより、Model上では、同一点であるｂ１，ｓ２１の対応点（ｂ’１，ｓ’２１）は異なる点（ｂ’１！＝ｓ’２１）になる可能性が大きい。
【００９４】
すなわち、同一のModel点が、そのModel点が対応するベース点とは異なるベース点、もしくは異なるベース点に対応するサポート点となる場合は、各々のベース点に応じて算出された対応点をそれぞれ取得する。この場合、ベース点とベース点に対応するサポート点を構成するModel点の集合が異なるため、上記（９）式で計算されるマッチングコストを最大とするTarget画像上の対応点は、たとえ同一のModel点に対応する対応点であったとしても、Model点の集合に応じて異なるマッチングコストを持つ異なる対応点となり得る。従って、これらの複数の異なる対応点をTarget点の候補とすることで、同一のModel点に対して複数の異なるマッチングコストを持つ異なるTarget点の候補を得ることができる。
【００９５】
以上のようにModelの各ベース点、サポート点は複数の対応点候補を得る可能性があるため、最終的に保存してあるコスト値から最もコスト値が高いものを各点の対応点、つまりマッチングペアとして決定する（ステップＳ３５）。つまり、ここでのマッチングペアは、ベース点に限定するものではなく、ベース点、サポート点をModel上の一つの点として考えたものとなる。
【００９６】
最終的なマッチングペアとして保存する内容は、ｉ＝１〜Ｎとするとき、Model画像の座標点（ｍｘｉ，ｍｙｉ）、Target画像の座標点（ｔｘｉ，ｔｙｉ）、基準軸の差ｄθiとなる。
【００９７】
これによるマッチングの効果を説明する。Model特徴量抽出時に、参照円Ｒから選択したベース点は必ずしも最適なものでない。例えば、図２４（Ｂ）に示すようにTargetに部分的な隠れが生じている場合、図２４（Ａ）に示すModel点ｂ１がTarget上での対応する点ｐ’１にマッチする可能性は非常に低くなる。しかし、図２４（Ａ）のModel点ｂ２は、図２４（Ｂ）におけるTarget上での対応点ｐ’２にマッチする可能性が高い。ここで、Model点ｂ１は、Model点ｂ２のサポート点でもあるため、上述したようにベース点の対応点決定時にベース点だけでなくサポート点についても、その対応点を保持することで、Model点ｂ１の対応点としてｐ’１を得ることができる可能性がある。
【００９８】
ところで、ステップＳ３３の特徴量マッチング処理により、ModelとTarget間のマッチングペアを取得することが可能になったが、ステップＳ３３のマッチング処理は、局所的な領域でのマッチングであるため、多くのOutiler(ミスマッチペア)が存在する。
【００９９】
そこで、図２５に示すように、ステップＳ３３の特徴量マッチング処理の後に、ステップＳ３４にてOutlier除去処理を行う。つまり、ステップＳ３３で得られたマッチングペアから、ステップＳ３４にてOutlierを除去してからステップＳ３５にて最終的なマッチングペアを取得する。ステップＳ３４では正しくないマッチングペアを除去して、ステップＳ３５では最終的にマッチングペアをとる。
【０１００】
以下にOutlier除去方法について述べる。ModelとTargetが同一物体である場合、マッチングペアは、以下の（１１）式に示す幾何拘束を満たす必要がある。
【０１０１】
Model点（ｍｘ，ｍｙ）、Target点（ｔｘ，ｔｙ）、相対角度ｄθとする。また、ｄｘ，ｄｙはｘ方向、ｙ方向の移動量である。
【０１０２】
【数１１】
2008077626.tif 000013
【０１０３】
この拘束条件を利用して、Outlierを除去する方法を図２６に示す。図２６におけるｔｉ−ｍ’ｉはマッチングペアを示す。各ペアについて、（１１）式を用いて回転正規化し、移動量ｄｘ、ｄｙを算出する。算出した移動量を予め用意した２次元空間（ｄｘ−ｄｙ）の対応するＢｉｎに投票する。
【０１０４】
全てのペアについて投票を行い、２次元空間（ｄｘ−ｄｙ）で最大値をもつＢｉｎを決定する。決定したＢｉｎに対応する移動量（ｄｘ、ｄｙ）をもたないペアは、Outlierとしマッチングペアから除去する。
【０１０５】
例えば図２６では、ｔ１−ｍ’１，ｔ２−ｍ’２，ｔ３−ｍ’３，ｔ４−ｍ’４は同一の移動量をもち、２次元空間の同一のＢｉｎに投票されるが、ｍ４−ｔ４は２次元空間の異なるＢｉｎに投票さるため、Outlierとして検出される。
【０１０６】
以上の手順を踏むことで、幾何学拘束を満たすペアのみを取得可能となる。最終的に得られたペア数が十分多ければ、入力のTarget画像は注目のModelと同定することが可能となる。
【０１０７】
ターゲット画像認識部により認識処理で重要なのは、マッチングと特徴量抽出である。マッチングの数が、十分信頼性の高いマッチング数であれば、それにより物体を同定することができる。特徴量がマッチングするということは、正しいマッチングがたくさん得られるということであるので、その物体であるという可能性が高くなる。
【０１０８】
なお、本発明では、局所的な参照円を定義してベース点、サポート点を定義したが、円のほか、局所的な閉曲線であることを条件とした他の形状としてもよい。ただし、回転正規化処理に関連すれば、円であることが有利である。
【０１０９】
次に、他の実施の形態について説明する。この他の実施の形態も、図１に示した物体認識装置１であり、画像内に存在する物体を認識するものであるが、モデル特徴量登録部１０の構成が異なる。図２７には、他の実施の形態におけるモデル特徴量登録部３０を示す。
【０１１０】
このモデル特徴量登録部３０も、モデル（Model）の特徴量を登録する部分であり、あらかじめ、上記物体のモデルのエッジ画像を生成し、生成したエッジ画像上のエッジ点の局所特徴量、及びそれをサポートする点を抽出し、それらの幾何学的位置関係とともに辞書に登録する。
【０１１１】
図２７にあって、モデル特徴量登録部３０は、カメラ１１で撮像された画像をフレームメモリ１２に蓄積し、フレームメモリ１２に蓄積した画像を元に多重解像度画像生成部３１で複数の多重解像度画像を生成する。多重解像度画像の生成については後述する。多重解像度画像生成部３１で生成された複数の多重解像度画像は、エッジ画像生成部１３に送られる。エッジ画像生成部１３は、複数の多重解像度画像毎にエッジ画像を生成する。
【０１１２】
モデル画像特徴量抽出部１４は、エッジ画像生成部１３にて複数の多重解像度画像毎に生成された複数のエッジ画像を基に、局所特徴量、及びそれをサポートする点の抽出を行い、その幾何学的位置関係を算出し、モデル毎にモデル辞書１５に登録する。
【０１１３】
ターゲット画像認識部２０については、図３を用いて既に説明した構成と同様であるので説明を省略する。
【０１１４】
モデル特徴量登録部３０における処理について説明する。モデル特徴量登録部３０におけるモデルｌ記述例（局所領域記述例）は、物体形状を表すEdge画像の局所領域を、前述の図４（Ａ）に示すように、参照円Ｒとし、この参照円Ｒ付近のEdge点について、ベース点ｂ、及びサポート点ｓ１，ｓ２，ｓ３を設定する。
【０１１５】
そして、図４（Ｂ）を参照して前述したように、各サポート点ｓ１，ｓ２，ｓ３のベース点ｂからの相対的な位置関係を、相対距離ｒ１，ｒ２，ｒ３、相対角度θ１，θ２，θ３で記述する。但し、ベース点ｂ，サポート点ｓ１，ｓ２，ｓ３はそれぞれ特徴量を持つものとする。輪郭の局所領域を、注目点（ベース点ｂ）の特徴量、周辺の点（サポート点ｓ１，ｓ２，ｓ３）の特徴量及びその位置関係（相対距離r１，ｒ２，ｒ３、相対角度θ１，θ２，θ３）を拘束として用いることで、柔軟かつロバストな記述が可能となる。
【０１１６】
以上の説明から、モデル特徴量登録部３０にあっても、前述したように、［１］Edge画像の生成、［２］Edge点の局所特徴量抽出、［３］参照円Ｒｉの決定、［４］ベース点ｂｉ，サポート点ｓｉｊの決定、［５］各サポート点の相対角度θｉｊ、相対距離ｒｉｊの決定が、局所的なモデル記述に必要な要素となることがわかる。ただし、モデル特徴量登録部３０では、［３］参照円Ｒiの決定、［４］ベース点ｂｉ，サポート点ｓｉｊの決定処理が前述のモデル特徴量登録部１０と異なる。
【０１１７】
先ず、モデル特徴量登録部３０にあって特徴的である、［３］参照円Ｒｉの決定について説明する。前述したように、物体の輪郭は局所的に様々であり、前述した幾何拘束を利用するためには、参照円の大きさは各局所領域で異なる必要がある。
【０１１８】
前述した図４に示すように、円半径が一定である場合、Ｒ１の領域では十分な幾何拘束を得ることができない。一方、このような領域で円半径を変えることで，Ｒ１’に示すように十分な拘束を得ることが可能となる。
【０１１９】
以後、具体的な参照円Ｒｉの決定方法を示す。参照円Ｒｉを決定するためには、その中心画素及び半径を決定する必要がある。基本的な概念は、前述の実施の形態のモデル特徴量登録部１０で用いたものと同様である。すなわち、参照円付近全体にEdge点がばらつき、かつ参照円上のEdge点がもつ各局所特徴量間の距離が大きくなる領域を抽出する。
【０１２０】
より具体的には、図２８に示すように参照円Ｒｉを局所特徴量の半径に応じて分割し、各分割した円弧付近の局所特徴量を抽出する。図２８に示した例では、参照円を８つに分割し、円弧付近の局所特徴量を、局所特徴量ａ、局所特徴量ｂ、局所特徴量ｃ・・・局所特徴量ｉのように抽出している。
【０１２１】
続いて、相互の特徴量間の距離を次式により算出し、図２９に示す相互特徴量間の距離マップを生成する。
【０１２２】
【数１２】
2008077626.tif 000014
【０１２３】
図２９にあって、局所特徴量ａと局所特徴量ｂの距離はｄ１、局所特徴量ａと局所特徴量ｃの距離はｄ２、以下局所特徴量aと局所特徴量ｃ，ｄ，ｅ，ｆ，ｇ，ｈ，ｉとの距離はｄ３，ｄ４，ｄ５，ｄ６，ｄ７，ｄ８となる。また、局所特徴量ｂと局所特徴量ｃ，ｄ，ｅ，ｆ，ｇ，ｈ，ｉとの距離はｄ９，ｄ１０，ｄ１１，ｄ１２，ｄ１３，ｄ１４となる。また、局所特徴量ｃと局所特徴量ｄ，ｅ，ｆ，ｇ，ｈ，ｉとの距離はｄ１６，ｄ１７，ｄ１８，ｄ１９，ｄ２０，ｄ２１となる。また、局所特徴量ｄと局所特徴量ｅ，ｆ，ｇ，ｈ，ｉとの距離はｄ２２，ｄ２３，ｄ２４，ｄ２５，ｄ２６となる。また、局所特徴量ｅと局所特徴量ｆ，ｇ，ｈ，ｉとの距離はｄ２７，ｄ２８，ｄ２９，ｄ３０となる。また、局所特徴量ｆと局所特徴量ｇ，ｈ，ｉとの距離はｄ３１，ｄ３２，ｄ３３となる。また、局所特徴量ｇと局所特徴量ｈ，ｉとの距離はｄ３４，ｄ３５となる。また、局所特徴量ｈと局所特徴量ｉとの距離はｄ３６となる。
【０１２４】
先に述べたように、ここでは各特徴量間の距離は互いに大きい領域を抽出するのが目標となるが、その評価基準として、具体的には、次式で示す特徴間距離（ｄ１・・・ｄｎ）のエントロピー値で表す。
【０１２５】
【数１３】
2008077626.tif 000015
【０１２６】
エントロピー値Ｈ（ｋ）は，各特徴間距離値が等しく分布する場合するほど大きくなる。これにより、１つの特徴点に対する各点への依存性はほぼ均一になることが期待できる。
【０１２７】
この指標を用いた画像上の画像上の任意点ｉにおける参照円抽出処理の流れを図３０に示す。まず、ステップＳ４１にて予め設定している、参照円Ｒｉの最小半径ｓｔ＿ｒを半径として設定し、最大エントロピーをＨ＿ｍａｘ＝０のように０にしておく。次に、ステップＳ４２にて、上記式により、この半径でのエントロピーＨｉを算出する。ステップＳ４３では、エントロピーＨｉが最大エントロピーＨ＿ｍａｘより大きくなったか否かを判断し、大きくなれば、ステップＳ４４にて、最大エントロピーＨｉ＿ｍａｘ，及びその時の参照円の半径ｒ＿ｍａｘを保存する。ステップＳ４５では、予め設定している半径の更新ステップｒ＿ｓｔｅｐにより、順次半径を変更する。ステップＳ４６では、半径ｒが半径の閾値ｒ＿ｔｈｒｅｓｈより大きくなったか否かをチェックする。ステップＳ４３にて、エントロピーＨｉが最大エントロピーＨ＿ｍａｘより大きくないうちは、ステップＳ４５に進む。また、ステップＳ４６にて半径ｒが半径の閾値ｒ＿ｔｈｒｅｓｈより大きくならないうちはステップＳ４２に進む。
【０１２８】
つまり、ステップＳ４２〜ステップＳ４６を繰り返しながら、予め設定している半径の更新ステップｒ＿ｓｔｅｐにより、順次半径を変更しエントロピーを算出し、最大エントロピーＨｉ＿ｍａｘ，及びその時の参照円の半径ｒ＿ｍａｘを保存する。
【０１２９】
この処理を画像上のすべての点で行うことで、各画素におけるエントロピーの最大値、及び参照円の半径を保存した、前述の図１４に示すようなＭａｐ（Ｅ＿Ｍａｐ）を得ることができる。
【０１３０】
続いて、Ｅ＿Ｍａｐのエントロピー値を使って、前述したノンマキシマムサプレッション（non-maximum suppression）を行う。つまり、注目画素の近傍領域（８近傍、１６近傍など）において、注目画素が極大値でない場合は、マップＥ_Ｍａｐが保持するエントロピー値、半径値を０とする。
【０１３１】
以上の処理を図３１に示すように、多重解像度生成部３１で生成した各解像度に対して行い、それぞれについてエントロピーマップを生成し、参照円の選択を行う。具体的には、各解像度で作成したエントロピー値を降順にソートし、その上位Ｎ点を選択する。それ以外のエントロピー値を持つＥ＿Ｍａｐの点はエントロピー値、半径を０とし，最終的なエントロピーマップＥ＿Ｍａｐｉ（ｉ＝１・・・３）を生成する。
【０１３２】
ここで、多重解像度画像生成部３１について説明しておく。多重解像度画像生成部３１は、解像度が異なった、つまり縮小率の異なる画像を図３１の（ａ）、（ｂ）及び（ｃ）のように作成する。例えば、モデル画像が（ａ）であった場合に、モデル画像を縮小した画像を（ｂ）、さらに縮小した画像を（ｃ）のように作成する。
【０１３３】
そして、多重解像度画像生成部３１は、上記解像度の異なる複数の画像毎にエントロピーマップを、Ｅ＿Ｍａｐ１，Ｅ＿Ｍａｐ２及びＥ＿Ｍａｐ３のように生成し、エントロピー値から参照円の半径を求める。この場合、エントロピー値の計算は、（ａ）の画像で３００点であれば、（ｂ）の画像では２５０点、さらに（ｃ）の画像では２００点というようにすることができる。このようにモデル特徴量登録部３０では、多重解像度画像生成部３１及びエッジ画像生成部１３を用いて縮小率の異なる画像に対応し、最適な参照円を決定することができる。
【０１３４】
つまり、各解像度で作成したＥ＿Ｍａｐは、画像サイズと同様の大きさを持ち、各画素にはエントロピー値と円の半径を保持しているため、エントロピー値が０でない画素の位置が参照円の中心となり、これにより参照円Ｒｉを決定することが可能となる。
【０１３５】
また、各解像度をエントロピー値によって統一的に扱い、参照円を決定することでより識別力の高い領域の局所領域の抽出が可能になる。
【０１３６】
参照円Ｒｉ（ｉ＝１・・・Ｎ）を決定した後は、上記図５のステップＳ３以降の処理と同様に、参照円ＲｉとEdge画像を用いて、ベース点ｂｉ，サポート点ｓｉｊを決定する。以下に各参照円Ｒｉ（ｉ＝１・・・Ｎ）におけるベース点ｂｉ，サポート点ｓｉｊの決定方法について簡単に述べる。但し、参照円の選択順序は、上述の処理で得られるＥ＿Ｍａｐにおけるエントロピー値の降順とする。
【０１３７】
まず、各点のサンプリングは、図１５に示すように参照円を角度方向にＭ分割する。分割した各Ｂｉｎにサンプリング領域を設定する。例えば、図１５に示すように、分割した円弧の中心付近に領域を設定する。このサンプリング領域内でもっとも参照円に近い点をサンプリング点ｍｉｊ（ｊ＝１・・・Ｍ）とする。サンプリング点群からベース点を決定する。前回までのベース点の位置の履歴を参照し、その画素の周辺に存在しない点をサンプリング点ｍｉｊ（ｊ＝１・・・Ｍ）中から選択し、今回のベース点、その他をサポート点とする。また、逐次履歴は更新していく。
【０１３８】
これ以降のモデル特徴量登録部３０の処理は、上記図５を参照して説明したのと同様であるので説明を省略する。また、ターゲット画像認識部２０の処理についても、図３、図１６〜図３１を参照して説明したとおりである。ただし、図３のマッチング部２５により実行される、図１７のステップＳ３３のマッチング処理で得られたペアは、モデル辞書１５に登録されているスケール比で正規化し、図２５のステップＳ３４にてアウトライア除去処理を行うのが望ましい。また、モデル登録の際には、参照円を、各局所特徴量間距離が大きく、かつ一様に分布するように決定できるため、１つの点への偏った依存性を回避可能となる。記述する局所領域では、ベース点からのサポート点へ対する依存性が偏っていないため、一部の隠れ領域がある場合でもロバストなマッチングが可能となる。
【０１３９】
以上に説明したように、本発明では、参照円のような局所的な領域抽出にマッチングに用いる局所特徴量を利用することから、より識別力の高い領域の抽出が可能となる。また、記述する局所領域では、各局所特徴量間距離が大きく、かつ一様に分布するため、１つの点への偏った依存性を回避可能となる。記述する局所領域では、ベース点からのサポート点へ対する依存性が偏っていないため、一部の隠れ領域がある場合でもロバストなマッチングが可能となる。
【０１４０】
また、多重解像度の中から局所領域を決定し、Model記述を行うため、ターゲットのスケール変化に対応可能となる。各解像度をエントロピー値によって統一的に扱い、局所領域決定することで、より識別力の高い領域の局所領域の抽出が可能となる。
【０１４１】
なお、多重解像度画像生成部は、図２におけるモデル特徴量登録部にあって、フレームメモリ１２とエッジ画像生成部１３との間に設けられても良い。
【図面の簡単な説明】
【０１４２】
【図１】第１の実施の形態である物体認識装置の概略構成図である。
【図２】モデル特徴量登録部のブロック図である。
【図３】ターゲット画像認識部のブロック図である。
【図４】局所領域の記述例である。
【図５】モデル特徴量登録部の処理手順を示すフローチャートである。
【図６】エッジ画像生成処理の詳細な処理手順を示すフローチャートである。
【図７】エッジ画像生成処理で用いる微分フィルタを示す図である。
【図８】局所特徴量を説明するための図である。
【図９】基準軸抽出を説明するための図である。
【図１０】回転正規化を説明するための図である。
【図１１】参照円の例を示す図である。
【図１２】参照円評価基準を示す図である。
【図１３】参照円決定処理の流れを示すフローチャートである。
【図１４】エントロピーマップを示す図である。
【図１５】サンプリング方法を説明するための図である。
【図１６】サポート点の相対位置を説明するための図である。
【図１７】ターゲット画像認識部の処理手順を示すフローチャートである。
【図１８】ベース点、サポート点が他のサポート点と重複することを説明するための図である。
【図１９】マッチ部の動作を説明するための図である。
【図２０】モデルとターゲットのマッチングを説明するための図である。
【図２１】モデルのベース点、サポート点に対応するターゲット上の点を示す図である。
【図２２】マッチング後に得られる結果を示す図である。
【図２３】重複したベース点、サポート点における二つの対応点を説明するための図である。
【図２４】対応点の決定を説明するための図である。
【図２５】ターゲット画像認識部の他の処理手順を示すフローチャートである。
【図２６】幾何学拘束を説明するための図である。
【図２７】第２の実施の形態の物体認識装置に用いられるモデル特徴量登録部のブロック図である。
【図２８】参照円の評価基準について説明するための図である。
【図２９】特徴量間距離マップを示す図である。
【図３０】参照円の決定処理の手順を示すフローチャートである。
【図３１】多重解像度画像を用いた参照円選択を説明するための図である。
【符号の説明】
【０１４３】
１  物体認識装置、１０  モデル特徴量登録部、１３  エッジ画像生成部、１４  モデル特徴量抽出部、１５  モデル辞書、２０  ターゲット画像認識部、２３  エッジ画像生成部、２４  ターゲット特徴量抽出部、２５  マッチング部、２６  物体同定部、３１  多重解像度画像生成部
【図１】
2008077626.tif 000016
【図２】
2008077626.tif 000017
【図３】
2008077626.tif 000018
【図４】
2008077626.tif 000019
【図５】
2008077626.tif 000020
【図６】
2008077626.tif 000021
【図７】
2008077626.tif 000022
【図８】
2008077626.tif 000023
【図９】
2008077626.tif 000024
【図１０】
2008077626.tif 000025
【図１１】
2008077626.tif 000026
【図１２】
2008077626.tif 000027
【図１３】
2008077626.tif 000028
【図１４】
2008077626.tif 000029
【図１５】
2008077626.tif 000030
【図１６】
2008077626.tif 000031
【図１７】
2008077626.tif 000032
【図１８】
2008077626.tif 000033
【図１９】
2008077626.tif 000034
【図２０】
2008077626.tif 000035
【図２１】
2008077626.tif 000036
【図２２】
2008077626.tif 000037
【図２３】
2008077626.tif 000038
【図２４】
2008077626.tif 000039
【図２５】
2008077626.tif 000040
【図２６】
2008077626.tif 000041
【図２７】
2008077626.tif 000042
【図２８】
2008077626.tif 000043
【図２９】
2008077626.tif 000044
【図３０】
2008077626.tif 000045
【図３１】
2008077626.tif 000046