(57)【要約】【課題】３次元物体を撮影した画像から物体認識を高速に実行する。【解決手段】登録用画像データを入力する手段１１と、その登録用画像データから第１特徴点を抽出する手段１２と、その第１特徴点の位置情報を蓄積手段に蓄積する手段１３と、認識用画像データを入力する手段１４と、その認識用画像データから第２特徴点を抽出する手段１５と、その認識用画像データに関して距離参照テーブルを作成する手段１６と、その学習マップ記憶部から呼び出された第１特徴点の位置の情報、距離参照テーブルに基づいて類似度を算出し、その類似度に基づいて前記物体に関して最も類似している特徴点を求める識別手段１７と、その最も類似している特徴点を出力する手段１８と、を用いてパターン認識を行う。【選択図】図１
2007299364.tif 000002
【特許請求の範囲】
【請求項１】
画像データに含まれる物体を識別するパターン認識装置であって、
画像取得手段から取得した画像データを登録用画像データと見做し、該登録用画像データを入力する登録用画像データ入力手段と、
その登録用画像データに撮像された物体に関する第１特徴点を、その登録用画像データから抽出する第１特徴点抽出手段と、
その第１特徴点の位置情報を蓄積手段に蓄積する学習マップ記憶手段と、
画像データを認識用画像データと見做し、該認識用画像データを入力する認識用画像データ入力手段と、
その認識用画像データから第２特徴点を抽出する第２特徴点抽出手段と、
前記認識用画像データ上の任意位置から最も近い第２特徴点までの距離を計算し、該任意位置，最も近い第２特徴点，任意位置から最も近い第２特徴点までの距離を含むデータをテーブル化する距離参照テーブル作成手段と、
前記学習マップ記憶手段で蓄積された第１特徴点の位置の情報を呼び出し、その第１特徴点の位置の情報に基づいて最小の第１類似度を計算し、その距離参照テーブル作成手段で作成された距離参照テーブルを用いて、最小の第２類似度を計算し、その第１類似度と第２類似度に基づいて第３類似度を算出し、その第３類似度に基づいて、前記物体に関して最も類似している特徴点を求める識別手段と、
その最も類似している特徴点を認識結果と見做し、その認識結果を出力する出力手段と、
を有することを特徴とするパターン認識装置。
【請求項２】
前記距離参照テーブル作成手段において、
前記第２特徴点に基づいてボロノイ図を作成し、
前記認識用画像データ上の任意位置から最も近い第２特徴点までの距離を該ボロノイ図を用いて計算する、
ことを特徴とする請求項１に記載のパターン認識装置。
【請求項３】
前記識別手段において、
前記認識用画像データ上の任意位置から最も近い第２特徴点までの距離が、登録用画像データから抽出された第１特徴点の総数ｎ，第２類似度Ｓ1，類似度閾値Ｓthreに基づいた以下の式で表される距離ｐより短くなる場合、その第２類似度Ｓ1に関する第３類似度の計算をスキップしつつ、第２類似度Ｓ1が最小となる位置を探索し、
その第２類似度Ｓ1が最小となる位置における第１類似度を求める、
ことを特徴とする請求項１または２に記載のパターン認識装置。
【数１】
2007299364.tif 000018
【請求項４】
前記学習マップ記憶手段が、さらに、該第１特徴点の位置情報を任意の幾何的変形に基づいて変形し、その変形された複数の第１特徴点の位置情報も、前記蓄積手段に蓄積し、
学習マップａ及びｂ間の距離を以下の式［２］で計算される学習マップ間距離Ｓm（ａ，ｂ）と見做し、全ての学習マップ間の組合せを計算して相互学習マップ間テーブルを作成する相互学習マップ間テーブル作成手段を備え、
前記識別手段が、学習マップａから抽出された第１特徴点の総数ｎ，第２類似度Ｓ1，類似度閾値Ｓthreに基づいた以下の式［３］で表される距離ｐaを計算し、その計算された距離ｐaに基づいた以下の式［４］で計算して距離値ｑa,bを求め、その距離値ｑa,bが正になる場合に、
前記学習マップｂを用いた前記第２類似度が最小となる位置の探索を省略し、更に、前記第３類似度を算出する計算も省略する、
ことを特徴とする請求項１乃至３のいずれかに記載のパターン認識装置。
【数２】
2007299364.tif 000019
【数３】
2007299364.tif 000020
【数４】
2007299364.tif 000021
【請求項５】
画像データに含まれる物体を識別するパターン認識方法であって、
画像取得手段から取得した画像データを登録用画像データと見做し、該登録用画像データを入力する登録用画像データ入力ステップと、
その登録用画像データに撮像された物体に関する第１特徴点を、その登録用画像データから抽出する第１特徴点抽出ステップと、
その第１特徴点の位置情報を蓄積手段に蓄積する学習マップ記憶ステップと、
画像データを認識用画像データと見做し、該認識用画像データを入力する認識用画像データ入力ステップと、
その認識用画像データから第２特徴点を抽出する第２特徴点抽出ステップと、
前記認識用画像データ上の任意位置から最も近い第２特徴点までの距離を計算し、該任意位置，最も近い第２特徴点，任意位置から最も近い第２特徴点までの距離を含むデータをテーブル化する距離参照テーブル作成ステップと、
前記学習マップ記憶ステップで蓄積された第１特徴点の位置の情報を呼び出し、その第１特徴点の位置の情報に基づいて最小の第１類似度を計算し、その距離参照テーブル作成ステップで作成された距離参照テーブルを用いて、最小の第２類似度を計算し、その第１類似度と第２類似度に基づいて第３類似度を算出し、その第３類似度に基づいて、前記物体に関して最も類似している特徴点を求める識別ステップと、
その最も類似している特徴点を認識結果と見做し、その認識結果を出力する出力ステップと、
を含むことを特徴とするパターン認識方法。
【請求項６】
前記距離参照テーブル作成ステップにおいて、
前記第２特徴点に基づいてボロノイ図を作成し、
前記認識用画像データ上の任意位置から最も近い第２特徴点までの距離を該ボロノイ図を用いて計算する、
ことを特徴とする請求項５に記載のパターン認識方法。
【請求項７】
前記識別ステップにおいて、
前記認識用画像データ上の任意位置から最も近い第２特徴点までの距離が、登録用画像データから抽出された第１特徴点の総数ｎ，第２類似度Ｓ1，類似度閾値Ｓthreに基づいた以下の式で表される距離ｐより短くなる場合、その第２類似度Ｓ1に関する第３類似度の計算をスキップしつつ、第２類似度Ｓ1が最小となる位置を探索し、
その第２類似度Ｓ1が最小となる位置における第１類似度を求める、
ことを特徴とする請求項５または６に記載のパターン認識方法。
【数５】
2007299364.tif 000022
【請求項８】
前記学習マップ記憶ステップが、さらに、該第１特徴点の位置情報を任意の幾何的変形に基づいて変形し、その変形された複数の第１特徴点の位置情報も、前記蓄積手段に蓄積し、
学習マップａ及びｂ間の距離を以下の式［２］で計算される学習マップ間距離Ｓm（ａ，ｂ）と見做し、全ての学習マップ間の組合せを計算して相互学習マップ間テーブルを作成する相互学習マップ間テーブル作成ステップを備え、
前記識別ステップが、学習マップａから抽出された第１特徴点の総数ｎ，第２類似度Ｓ1，類似度閾値Ｓthreに基づいた以下の式［３］で表される距離ｐaを計算し、その計算された距離ｐaに基づいた以下の式［４］で計算して距離値ｑa,bを求め、その距離値ｑa,bが正になる場合に、
前記学習マップｂを用いた前記第２類似度が最小となる位置の探索を省略し、更に、前記第３類似度を算出する計算も省略する、
ことを特徴とする請求項５乃至７のいずれかに記載のパターン認識方法。
【数６】
2007299364.tif 000023
【数７】
2007299364.tif 000024
【数８】
2007299364.tif 000025
【請求項９】
請求項５乃至８のいずれかに記載のパターン認識方法を、コンピュータで実行可能なコンピュータプログラムとして記述し、そのコンピュータプログラムを記録したことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン認識装置，パターン認識方法及びその方法を実現したプログラムを格納した記録媒体であって、例えば、画像認識技術に関するものである。
【背景技術】
【０００２】
近年、携帯電話にカメラ機能が搭載され、いつでも手軽に画像データを取得または保存できるようになった。このカメラ機能をさらに活用するサービスとして、画像データに記録された３次元物体を該画像データから認識し、その３次元物体に関連したデータを提供するというサービスが知られている。
【０００３】
例えば、３次元物体を効率よく画像認識するために、特徴点を利用した手法がよく使われる。特徴ある点（例えば、コーナーなど）を画像から自動抽出し、予め３次元物体から抽出しておいた特徴点を３次元マップに対応付けし、その対応付けの妥当性を検証して一定以上の妥当性を持つ物体を適合物体として認識する手法（例えば、特許文献１参照）である。この手法は、特別なパーツ（例えば、マーカなど）を物体に付与する必要がない上に、特徴点の対応関係が未知の場合にも対処できる。
【０００４】
画像認識技術では、幾つかの方法が広く知られており、それらを以下に挙げておく。
【０００５】
画像認識処理では、ボロノイ図作成処理が利用されることがある。このボロノイ図作成処理を高速化する方法として、例えば、逐次添加法など（例えば、非特許文献１参照）が知られている。
【０００６】
また、画像認識技術における特徴点抽出方法には、Ｈａｒｒｉｓ作用素、Ｋａｎａｄｅ−Ｌｕｃａｓ−Ｔｏｍａｓｉ法、Ｍｏｒａｖｅｃ作用素、など様々な方法（例えば、非特許文献２参照）が知られている。
【特許文献１】特開２００２−１０９５３９号公報（段落［００２１］〜［００２５］等）。
【非特許文献１】Ｘｕｅｈｏｕ  Ｔａｎ，平田富夫、「計算幾何学入門」、森北出版、２００１年１０月２５日。
【非特許文献２】金澤靖，金谷健一、「コンピュータビジョンのための画像の特徴点の抽出」、電子情報通信学会誌、２００４年、Ｖｏｌ．８７、Ｎｏ．１２、ｐｐ．１０４３−１０４８。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
前述のような手法は、対応点探索を積極的に行うものではなく、３次元物体から予め抽出しておいた特徴点と新たに入力された特徴点からそれぞれランダムに数点ずつ選択し、それらの点が対応していると仮定した上で、妥当性評価（即ち、妥当性評価処理）まで一気に行う手法である。
【０００８】
前記手法では、仮定が正しいと見做されるのは、対応の妥当性が高く評価されたときのみのため、高い妥当性が算出されるまで何回も、前記妥当性評価処理を繰り返さなくてはならない。
【０００９】
また、一般に対応点探索は不安定な処理となりがちなため、その不安定さを回避できる前記手法は高い安定性を保てる。
【００１０】
しかし、結果の信頼性向上のためには、妥当性評価処理の回数を出来る限り増やさねばならないため、非常に時間のかかる作業となる。
【００１１】
本発明は、前記課題に基づいてなされたものであって、３次元物体を撮影した画像から特徴点を自動抽出し、予め蓄えられた物体の特徴点と照合し、物体認識を高速に実行するパターン認識装置，パターン認識方法及びその方法を実現したプログラムを格納した記録媒体を提供する。
【課題を解決するための手段】
【００１２】
本発明は、前記課題の解決を図るために、請求項１記載の発明は、画像データに含まれる物体を識別するパターン認識装置であって、画像取得手段から取得した画像データを登録用画像データと見做し、該登録用画像データを入力する登録用画像データ入力手段と、その登録用画像データに撮像された物体に関する第１特徴点を、その登録用画像データから抽出する第１特徴点抽出手段と、その第１特徴点の位置情報を蓄積手段に蓄積する学習マップ記憶手段と、画像データを認識用画像データと見做し、該認識用画像データを入力する認識用画像データ入力手段と、その認識用画像データから第２特徴点を抽出する第２特徴点抽出手段と、前記認識用画像データ上の任意位置から最も近い第２特徴点までの距離を計算し、該任意位置，最も近い第２特徴点，任意位置から最も近い第２特徴点までの距離を含むデータをテーブル化する距離参照テーブル作成手段と、前記学習マップ記憶手段で蓄積された第１特徴点の位置の情報を呼び出し、その第１特徴点の位置の情報に基づいて最小の第１類似度を計算し、その距離参照テーブル作成手段で作成された距離参照テーブルを用いて、最小の第２類似度を計算し、その第１類似度と第２類似度に基づいて第３類似度を算出し、その第３類似度に基づいて、前記物体に関して最も類似している特徴点を求める識別手段と、その最も類似している特徴点を認識結果と見做し、その認識結果を出力する出力手段と、を有することを特徴とする。
【００１３】
請求項２記載の発明は、請求項１記載の発明において、前記距離参照テーブル作成手段が、前記第２特徴点に基づいてボロノイ図を作成し、前記認識用画像データ上の任意位置から最も近い第２特徴点までの距離を該ボロノイ図を用いて計算する、ことを特徴とする。
【００１４】
請求項３記載の発明は、請求項１または２記載の発明において、前記識別手段が、前記認識用画像データ上の任意位置から最も近い第２特徴点までの距離が、登録用画像データから抽出された第１特徴点の総数ｎ，第２類似度Ｓ1，類似度閾値Ｓthreに基づいた以下の式で表される距離ｐより短くなる場合、その第２類似度Ｓ1に関する第３類似度の計算をスキップしつつ、第２類似度Ｓ1が最小となる位置を探索し、その第２類似度Ｓ1が最小となる位置における第１類似度を求める、ことを特徴とする。
【００１５】
【数９】
2007299364.tif 000003
【００１６】
請求項４記載の発明は、請求項１乃至３のいずれかに記載の発明において、前記学習マップ記憶手段が、さらに、該第１特徴点の位置情報を任意の幾何的変形に基づいて変形し、その変形された複数の第１特徴点の位置情報も、前記蓄積手段に蓄積し、学習マップａ及びｂ間の距離を以下の式［２］で計算される学習マップ間距離Ｓm（ａ，ｂ）と見做し、全ての学習マップ間の組合せを計算して相互学習マップ間テーブルを作成する相互学習マップ間テーブル作成手段を備え、前記識別手段が、学習マップａから抽出された第１特徴点の総数ｎ，第２類似度Ｓ1，類似度閾値Ｓthreに基づいた以下の式［３］で表される距離ｐaを計算し、その計算された距離ｐaに基づいた以下の式［４］で計算して距離値ｑa,bを求め、その距離値ｑa,bが正になる場合に、前記学習マップｂを用いた前記第２類似度が最小となる位置の探索を省略し、更に、前記第３類似度を算出する計算も省略する、ことを特徴とする。
【００１７】
【数１０】
2007299364.tif 000004
【００１８】
【数１１】
2007299364.tif 000005
【００１９】
【数１２】
2007299364.tif 000006
【００２０】
請求項５記載の発明は、画像データに含まれる物体を識別するパターン認識方法であって、画像取得手段から取得した画像データを登録用画像データと見做し、該登録用画像データを入力する登録用画像データ入力ステップと、その登録用画像データに撮像された物体に関する第１特徴点を、その登録用画像データから抽出する第１特徴点抽出ステップと、その第１特徴点の位置情報を蓄積手段に蓄積する学習マップ記憶ステップと、画像データを認識用画像データと見做し、該認識用画像データを入力する認識用画像データ入力ステップと、その認識用画像データから第２特徴点を抽出する第２特徴点抽出ステップと、前記認識用画像データ上の任意位置から最も近い第２特徴点までの距離を計算し、該任意位置，最も近い第２特徴点，任意位置から最も近い第２特徴点までの距離を含むデータをテーブル化する距離参照テーブル作成ステップと、前記学習マップ記憶ステップで蓄積された第１特徴点の位置の情報を呼び出し、その第１特徴点の位置の情報に基づいて最小の第１類似度を計算し、その距離参照テーブル作成ステップで作成された距離参照テーブルを用いて、最小の第２類似度を計算し、その第１類似度と第２類似度に基づいて第３類似度を算出し、その第３類似度に基づいて、前記物体に関して最も類似している特徴点を求める識別ステップと、その最も類似している特徴点を認識結果と見做し、その認識結果を出力する出力ステップと、を含むことを特徴とする。
【００２１】
請求項６記載の発明は、請求項５記載の発明において、前記距離参照テーブル作成ステップが、前記第２特徴点に基づいてボロノイ図を作成し、前記認識用画像データ上の任意位置から最も近い第２特徴点までの距離を該ボロノイ図を用いて計算する、ことを特徴とする。
【００２２】
請求項７記載の発明は、請求項５または６記載の発明において、前記識別ステップにおいて、前記認識用画像データ上の任意位置から最も近い第２特徴点までの距離が、登録用画像データから抽出された第１特徴点の総数ｎ，第２類似度Ｓ1，類似度閾値Ｓthreに基づいた以下の式で表される距離ｐより短くなる場合、その第２類似度Ｓ1に関する第３類似度の計算をスキップしつつ、第２類似度Ｓ1が最小となる位置を探索し、その第２類似度Ｓ1が最小となる位置における第１類似度を求める、ことを特徴とする。
【００２３】
【数１３】
2007299364.tif 000007
【００２４】
請求項８記載の発明は、請求項５乃至７のいずれかに記載の発明において、前記学習マップ記憶ステップが、さらに、該第１特徴点の位置情報を任意の幾何的変形に基づいて変形し、その変形された複数の第１特徴点の位置情報も、前記蓄積手段に蓄積し、学習マップａ及びｂ間の距離を以下の式［２］で計算される学習マップ間距離Ｓm（ａ，ｂ）と見做し、全ての学習マップ間の組合せを計算して相互学習マップ間テーブルを作成する相互学習マップ間テーブル作成ステップを備え、前記識別ステップが、学習マップａから抽出された第１特徴点の総数ｎ，第２類似度Ｓ1，類似度閾値Ｓthreに基づいた以下の式［３］で表される距離ｐaを計算し、その計算された距離ｐaに基づいた以下の式［４］で計算して距離値ｑa,bを求め、その距離値ｑa,bが正になる場合に、前記学習マップｂを用いた前記第２類似度が最小となる位置の探索を省略し、更に、前記第３類似度を算出する計算も省略する、ことを特徴とする。
【００２５】
【数１４】
2007299364.tif 000008
【００２６】
【数１５】
2007299364.tif 000009
【００２７】
【数１６】
2007299364.tif 000010
【００２８】
請求項９記載の発明は、記録媒体であって、請求項５乃至８のいずれかに記載のパターン認識方法を、コンピュータで実行可能なコンピュータプログラムとして記述し、そのコンピュータプログラムを記録したことを特徴とする。
【００２９】
前記の請求項１，５の発明によれば、物体の特徴点を蓄積（即ち、学習マップを蓄積）できる。距離参照テーブルを作成し用いることができる。
【００３０】
前記の請求項２，６の発明によれば、第２特徴点に基づいたボロノイ図を取得できる。
【００３１】
前記の請求項３，７の発明によれば、前記類似度閾値に基づいた距離を条件に処理をスキップできる。
【００３２】
前記の請求項４，８の発明によれば、前記距離値を条件に第３類似度を求める処理をスキップできる。
【００３３】
前記の請求項９の発明によれば、請求項５乃至８のいずれかに記載のパターン認識方法をコンピュータプログラムとして記載できる。
【発明の効果】
【００３４】
以上示したように請求項１，５の発明によれば、３次元物体を撮影した画像から特徴点を自動抽出し、予め蓄えられた物体の特徴点（即ち、学習マップ）と照合する物体認識方式を、距離参照テーブルを用いて高速に実行できる。即ち、距離参照テーブルを用いないパターン認識装置よりも、パターン認識処理を高速に実行できる。
【００３５】
請求項２，６の発明によれば、前記ボロノイ図に基づいて第２類似度を高速に算出できる。
【００３６】
請求項３，７の発明によれば、類似度の計算処理をスキップできるため、第３類似度を高速に算出できる。
【００３７】
請求項４，８の発明によれば、物体の平面上に存在する記号等に関する特徴点を高速に識別できる。
【００３８】
請求項９の発明によれば、パターン認識方法を実装したコンピュータプログラムを記録した記録媒体を提供できる。
【００３９】
これらを以って画像認識技術分野に貢献できる。
【発明を実施するための最良の形態】
【００４０】
以下、本発明の実施形態を図面等に基づいて詳細に説明する。
【００４１】
本発明における基本画像認識（或いは、基本的なパターン認識）手法を図７に基づいて以下に説明する。
【００４２】
まず、予め物体をさまざまな方向から撮影した画像（即ち、登録用画像）から特徴点を抽出し、その特徴点の２次元マップ（以下、学習マップと称する）群１を用意しておく。
【００４３】
次に、入力画像（即ち、認識用画像）２から特徴点３を抽出し、前記学習マップが含まれているか否かを、ずらしマッチング処理によって探索し画像認識を行う。
【００４４】
なお、そのずらしマッチング処理に基づく類似度は、学習マップと入力画像の一部分（例えば、図７中の符号４の部分）から切り出された特徴点の位置関係が近いほど高くなるように設定するものとする。
【００４５】
前記探索はナイーブに解けば時間のかかるものであるが、ずらしマッチング時のスキップ処理（或いは、枝刈り処理）及びボロノイ図作成アルゴリズムの利用によって高速化できる。
【００４６】
ずらしマッチング時のスキップ処理は、特定の場所で類似度を算出した後、どの程度まで次の位置をスキップさせることができるかを先回りして計算するというものである。
【００４７】
ボロノイ図作成アルゴリズムは、入力画像から特徴点を抽出した後、それらの特徴点をノードと見做したボロノイ図を描画し、その結果であるボロノイ図を利用して任意の位置の最近点までの距離を計算しテーブルを作成するものである。
【００４８】
なお、ボロノイ図作成処理は、前述の逐次添加法など、さまざまな高速化法が提案されているものである。また、前記テーブルを参照することによって、類似度算出の速度を劇的に向上できる。
【００４９】
［第１実施形態］
第１実施形態を図１乃至図３に基づいて以下に説明する。
【００５０】
なお、図１は、第１実施形態におけるパターン認識装置の構成図である。図２Ａは、第１実施形態における登録用画像データの登録過程を示すフローチャートである。図２Ｂは、第１実施形態におけるパターン認識方法を示すフローチャートである。図３は、第１実施形態における最小の類似度を計算する処理（以下、単に、最小類似度計算処理という）の手順を示すフローチャートである。
【００５１】
図１中の登録用画像データ入力部１１は、認識対象の登録に用いるため、画像取得（例えば、撮像装置（例えば、デジタルカメラ等）によって撮像する）手段によって３次元物体の画像データ（即ち、登録用画像データ）を取得し、３次元物体の画像データ（即ち、登録用画像データ）を入力し、特徴点抽出部１２に伝送する。なお、その３次元物体の撮像では、さまざまな見え方の画像（例えば、アングルや大きさを変えた画像）を撮像するものとする。例えば、撮像する対象が２次元的な物体である場合、計算機内で透視投影変換によって擬似的に画像を作ることも出来る。
【００５２】
特徴点抽出部１２は、登録用画像データ入力部１１から伝送された登録用画像データから特徴点を抽出する。なお、特徴点を抽出する方法には、前述の特徴点抽出方法を利用できる。
【００５３】
学習マップ記憶部１３は、抽出された特徴点の位置（即ち、学習マップ）を蓄積手段（例えば、メモリ，ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）装置）に全て蓄積する。なお、前記学習マップは、一つの登録物体（即ち、登録用画像に撮像された３次元物体）に対し、撮像した画像の枚数分保存される。
【００５４】
認識用画像データ入力部１４は、認識したい物体を撮像した画像データ（即ち、認識用画像データ）を特徴点抽出部１５に伝送する。
【００５５】
特徴点抽出部１５は、認識用画像データ入力部１４から伝送された認識用画像データから特徴点を抽出する。
【００５６】
距離参照テーブル作成部１６は、次の手順を実行する。
【００５７】
まず、特徴点抽出部１５で抽出された特徴点を使って、ボロノイ図を作成する。なお、ボロノイ図作成には、前述の逐次添加法などが利用できる。
【００５８】
そして、任意位置から最も近い特徴点（即ち、最近傍特徴点）までの距離を参照できるテーブル（以下、距離参照テーブルと称する）を作成する。なお、前記距離参照テーブルは、例えば、任意位置，最近傍特徴点，任意位置から最近傍特徴点までの距離を１データと見做すテーブルである。また、前記距離参照テーブルの要素数は、認識用画像の画素数と同じものとする。
【００５９】
先ほどのボロノイ図を参照することによって、最近傍の特徴点を瞬時に知ることができるため、距離参照テーブルの作成処理は非常に高速に処理できる。なお、前記距離参照テーブルに対し高速にアクセスするために、例えば、該距離参照テーブルを高速アクセス可能な記憶領域（例えば、バッファ）に格納しても良い。
【００６０】
識別部１７は、学習マップ記憶部１３で蓄積した特徴点位置の情報を呼出し、距離参照テーブル作成部１６で作成した距離参照テーブルを利用して物体識別（即ち、物体に関する特徴点の識別）を行う。
【００６１】
第１実施形態では、物体識別に利用する物体の類似度Ｓを以下の式で表すことにする。なお、類似度Ｓは「０」に近いほど類似しているといえる。
【００６２】
【数１７】
2007299364.tif 000011
【００６３】
【数１８】
2007299364.tif 000012
【００６４】
【数１９】
2007299364.tif 000013
【００６５】
ただし、Ｖは登録用画像データから抽出された特徴点の集合、ｘkはｋ番目の特徴点の２次元位置座標ベクトル、ｎは登録用画像データから抽出された特徴点の総数、Ｕは認識用画像データから抽出された特徴点の集合、ｙlは所定範囲から抽出されたｌ番目の特徴点の２次元位置座標ベクトル、ｍは認識用画像データの所定範囲から抽出された特徴点の総数である。
【００６６】
また、Ｓ1は登録用画像データの各特徴点を起点と見做し、その起点から最近傍点までの距離の和を類似度と見做したもの（以後、類似度Ｓ1と称する）である。Ｓ2は認識用画像データの各特徴点を起点と見做し、その起点から最近傍点までの距離の和を類似度と見做したもの（以後、類似度Ｓ2と称する）である。
【００６７】
従って、類似度Ｓは、次のように言える。認識用画像データ領域内で登録用画像データ領域（テンプレートと見做しても良い）と重なっている部分の領域において、認識用画像データの特徴点と登録用画像データの特徴点を合わせた数を総特徴点数と見做す。そして、その総特徴点数当たりの平均類似度をＳと見做すことができる。
【００６８】
なお、所定範囲とは、登録用画像データから特徴点を抽出したときの画像上の範囲を、認識用画像データ上で任意に移動させたときの範囲を示す。この範囲は、図７に示すように、認識用画像データより小さいものとする。
【００６９】
類似度Ｓ1を計算するとき、距離参照テーブルを参照すれば、最近点までの距離計算が瞬時に行えるため、非常に高速に類似度を計算できる。
【００７０】
所定範囲を所定量ずらしながら最小となる類似度Ｓを求める処理（以下、最小類似度計算処理と称する）を高速化するために、次の手順を行う。
【００７１】
まず、類似度Ｓ1が最小となる位置を探索する。
【００７２】
次に、その類似度Ｓ1が最小となる位置における類似度Ｓ2を求めて類似度Ｓを算出する。なお、最小の類似度Ｓ1となる位置を探索するときに特定の位置の類似度を求めた場合、その特定の位置を起点とした距離ｐの範囲内は、類似度Ｓthreより小さくならないことが保証されるものとする。
【００７３】
【数２０】
2007299364.tif 000014
【００７４】
従って、類似度Ｓthre（即ち、類似度閾値）を適切に設定することによって、この距離ｐより近い位置は全て類似度計算をスキップできる。
【００７５】
次に、画像の探索範囲と同じ大きさのテーブルを用意する。
【００７６】
前記テーブルは、２次元配列のフラグＦＬＡＧ(ｘ，ｙ)であって、ＯＮ（例えば、値「１」）かＯＦＦ（例えば、値「０」）が設定される。
【００７７】
前記テーブルの初期状態は、全てのフラグＦＬＡＧ(ｘ，ｙ)をＯＦＦにしておき、式（４）で計算された範囲（即ち、距離ｐ）のフラグＦＬＡＧ(ｘ，ｙ)はＯＮに切り替えるようにする。
【００７８】
また、該当するテーブル位置のフラグＦＬＡＧ(ｘ，ｙ)が、ＯＮに設定されている場合、類似度計算を行わないものとする。
【００７９】
そして、最終的に得られる最小の類似度Ｓ1の位置で類似度Ｓ2を計算し、両者を足し合わせて類似度Ｓを算出する。
【００８０】
以上の手順によって、最小類似度計算処理を高速化できる。
【００８１】
なお、最小類似度計算処理の手順は、後で詳述する。また、前記最小類似度計算処理において、最小の類似度Ｓ1の位置は必ずしも最小の類似度Ｓの位置と一致しないが、第１実施形態では、近似として最小の類似度Ｓ1の位置で求められた類似度Ｓを最小の類似度Ｓと見做すことにする。
【００８２】
類似度Ｓは、一つの登録物体に対し、撮像した画像の枚数分算出できる。そのため、一つの登録物体の類似度は、その撮像した画像中で最小の類似度を採用することにする。
【００８３】
そして、類似度Ｓcの最も小さい登録物体ｃに関する特徴点をパターン識別の結果と見做し、さらに、登録物体ｃを識別物体ｃと見做す。
【００８４】
出力部１８は、識別部１７で決定された識別物体ｃに関する特徴点をパターン認識結果と見做し、そのパターン認識結果を表示装置（例えば、ディスプレイ装置）に出力する。あるいは、識別物体ｃに関連する情報へのＵＲＬ（Ｕｎｉｆｏｒｍ  Ｒｅｓｏｕｒｃｅ  Ｌｏｃａｔｏｒ）にリンクづけされたＨＴＭＬ（ＨｙｐｅｒＴｅｘｔ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）ファイルを出力する部である。
【００８５】
第１実施形態における画像の登録過程，画像認識過程，最小類似度計算処理の手順を以下に説明する。なお、以下の説明で、図１及び図７中の符号と同じものの説明は省略する。
【００８６】
前記画像の登録過程を図２Ａに基づいて以下に説明する。
【００８７】
まず、登録用画像データ入力部１１によって、登録用画像データを入力する（Ｓ１０１）。
【００８８】
次に、特徴点抽出部１２によって、前記登録用画像データから特徴点を抽出する（Ｓ１０２）。
【００８９】
そして、学習マップ記憶部１３によって、抽出された特徴点の位置（即ち、学習マップ）を蓄積手段に全て蓄積する（Ｓ１０３）。
【００９０】
前記画像認識過程を図２Ｂに基づいて以下に説明する。
【００９１】
まず、認識用画像データ入力部１４によって、認識用画像データを入力する（Ｓ１０４）。
【００９２】
次に、特徴点抽出部１５によって、認識用画像データから特徴点を抽出する（Ｓ１０５）。
【００９３】
次に、距離参照テーブル作成部１６によって、距離参照テーブルを作成する（Ｓ１０６）。
【００９４】
次に、識別物体番号（以後、クラスと称する）ｉを「１」に初期化する。（Ｓ１０６１）。
【００９５】
次に、識別部１７によって、類似度を計算し、識別物体に関する特徴点を取得する（Ｓ１０７）。
【００９６】
次に、クラスｉの類似度計算が完了しているか否かをチェックする（Ｓ１０８）。クラスｉの類似度計算が完了している場合、ステップＳ１０８１へ進む。クラスｉの類似度計算が完了していない場合、ステップＳ１０７へ戻る。
【００９７】
ステップＳ１０８１では、クラスｉに「１」を加算する。
【００９８】
次に、全登録データの類似度計算が完了したか否かをチェックする（Ｓ１０９）。全登録データの類似度計算が完了した場合、ステップＳ１１０へ進む。全登録データの類似度計算が完了していない場合、ステップＳ１０７へ戻る。
【００９９】
そして、出力部１８によって、画像認識結果を表示装置に出力する（Ｓ１１０）。
【０１００】
前記最小類似度計算処理の手順を図３に基づいて以下に詳細説明する。
【０１０１】
まず、２次元の配列のフラグＦＬＡＧ(ｘ，ｙ)（以下、単にＦＬＡＧ(ｘ，ｙ)という）の全要素をＯＦＦに設定し初期化する（Ｓ２０１）。
【０１０２】
次に、ｘ，ｙを「０」に設定する（Ｓ２０１１）。
【０１０３】
次に、ＦＬＡＧ(ｘ，ｙ)の値をチェックする（Ｓ２０２）。ＦＬＡＧ(ｘ，ｙ)の値がＯＦＦの場合、ステップＳ２０３に進む。ＦＬＡＧ(ｘ，ｙ)の値がＯＮの場合、ステップＳ２０５１に進む。
【０１０４】
ステップＳ２０３では、類似度Ｓ1が最小となる位置を探索し、類似度Ｓ1を求める。
【０１０５】
次に、式（４）によって範囲ｐを計算する（Ｓ２０４）。
【０１０６】
次に、前記範囲ｐ内のＦＬＡＧ(ｘ，ｙ)をＯＮに設定する（Ｓ２０５）。
【０１０７】
次に、ｘに「１」を加算する（Ｓ２０５１）。
【０１０８】
次に、前記ｘが、画像の横幅（横画素数）以上が否かをチェックする（Ｓ２０６）。
【０１０９】
前記ｘが画像の横幅以上の場合、ステップＳ２０６１へ進む。前記ｘが画像の横幅より小さい場合、ステップＳ２０２に戻る。
【０１１０】
次に、ｙに「１」を加算する（Ｓ２０６１）。
【０１１１】
次に、ステップＳ２０７では、前記ｙが、画像の縦幅（縦画素数）以上か否かをチェックする。
【０１１２】
前記ｙが画像の縦幅以上の場合、ステップＳ２０８へ進む。前記ｙが画像の縦幅より小さい場合、ステップＳ２０２に戻る。
【０１１３】
そして、最終的に得られる最小の類似度Ｓ1の位置で類似度Ｓ2を計算し、両者を足し合わせて類似度Ｓを算出する（Ｓ２０８）。
【０１１４】
以上のように、第１実施形態は、登録用画像（即ち、パターン認識を行うためのパターン画像）データに撮像された物体に関する第１特徴点を、その登録用画像データから抽出し、その第１特徴点の位置情報を蓄積手段に蓄積する。また、認識用画像（即ち、物体が撮像された認識対象画像）データを入力し、その認識用画像データから第２特徴点を抽出し、その認識用画像データから距離参照テーブル（例えば、任意の位置，最も近い第２特徴点，任意の位置から最も近い第２特徴点までの距離を含むデータをテーブル）を作成する。その第１特徴点の位置の情報に基づいて最小の第１類似度を計算し、距離参照テーブルを用いて、最小の第２類似度を計算し、その第１類似度と第２類似度に基づいて第３類似度を算出し、前記物体に関して最も類似している特徴点を求める。そして、その最も類似している特徴点を認識結果と見做し、その認識結果を出力するものである。
【０１１５】
［第２実施形態］
第２実施形態を図４乃至図６に基づいて以下に説明する。
【０１１６】
なお、図４は、第２実施形態におけるパターン認識装置の構成図である。図５Ａは、第２実施形態における登録用画像データの登録過程を示すフローチャートである。図５Ｂは、第２実施形態におけるパターン認識方法を示すフローチャートである。図６は、第２実施形態における最小の類似度を計算する処理（以下、単に、最小類似度計算処理という）の手順を示すフローチャートである。
【０１１７】
図４中のパターン認識装置の構成と図１中のパターン認識装置の違いは、学習マップ記憶部２３，相互学習マップ間距離テーブル作成・記憶部２４，識別部２８である。
【０１１８】
学習マップ記憶部２３は、抽出された特徴点の位置（即ち、学習マップ）を蓄積手段（例えば、メモリ，ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）装置）に全て蓄積する。また、その学習マップを特定の方法で幾何的変形（あるいは、幾何的変換）し、その変形されて複数に増えた学習マップも蓄積する。例えば、対象が平面上に存在する記号等の場合は、アフィン変換や射影変換等を用いて新たな学習マップを追加できる。なお、前記学習マップは、一つの登録物体（即ち、登録用画像に撮像された３次元物体）に対し、撮像した画像の枚数分保存される。学習マップ記憶部２３は、前記幾何的変形方法を選択する手段を備えていても良い。
【０１１９】
相互学習マップ間距離テーブル作成・記憶部２４は、学習マップ記憶部２３に記憶された学習マップから相互学習間距離テーブルＴを作成し記憶する。なお、作成した相互学習間距離テーブルＴは、例えば、前記蓄積手段に蓄積（記憶）して良い。
【０１２０】
相互学習間距離テーブルＴは、次のように作成する。
【０１２１】
対象が平面上に存在する記号等の場合、相互の学習マップ同士の距離を以下の式で計算できる。
【０１２２】
【数２１】
2007299364.tif 000015
【０１２３】
ここで、２つの学習マップａ，ｂ間の距離をＳm（ａ，ｂ）、学習マップａにおけるｋ番目の特徴点の２次元位置座標ベクトルをｘa,k、学習マップｂにおけるｋ番目の特徴点の２次元位置座標ベクトルをｘb,k、学習マップａ及びｂの特徴点の数をｎとする。
【０１２４】
この距離Ｓm（ａ，ｂ）を全ての学習マップ間の組み合わせで求めたテーブルＴを利用して、さらに識別処理を高速化できる。
【０１２５】
なお、前記テーブルＴには、全ての学習マップ間までの距離Ｓm（ａ，ｂ）が格納される。
【０１２６】
識別部２８は、学習マップ記憶部１３で蓄積した特徴点位置の情報を呼出し、距離参照テーブル作成部１６で作成した距離参照テーブルと相互学習マップ間距離テーブル作成・記憶部２４で作成した相互学習マップ間距離テーブルを利用して、物体に関する特徴点の識別を行う。
【０１２７】
まず、上述のＦＬＡＧ（ｘ，ｙ）と別にもう一つのテーブルＦＬＡＧ２（ｚ）を用意する。このテーブルは、ＦＬＡＧ（ｘ，ｙ）と同様に、ＯＮまたはＯＦＦが設定され、ｚは学習マップの通し番号に相当する。
【０１２８】
初期状態として、全てのフラグＦＬＡＧ２（ｚ）をＯＦＦにしておき、以下の式で計算された距離ｑa,bが正となる学習マップｂのフラグＦＬＡＧ２（ｂ）は全てＯＮにする。
【０１２９】
【数２２】
2007299364.tif 000016
【０１３０】
ここで、学習マップａによる式４にて定義された距離ｐをｐaとする（以下の式４’を参照）。ｍｉｎ（ｐa）は、学習マップを用いて画像上の最小類似度Ｓ1を求めたときの距離Ｐaである。Ｓm（ａ，ｂ）は、予め作成された相互学習マップ間テーブルＴから参照できる。
【０１３１】
【数２３】
2007299364.tif 000017
【０１３２】
また、該当する学習マップのフラグＦＬＡＧ２（ｚ）がＯＮに設定されている場合は、学習マップｚの類似度計算を行わなくても良い。なぜなら、学習マップｚを用いたときの類似度Ｓ1は、類似度Ｓthreより小さくならないことが保証されるからである。即ち、類似度Ｓ2を求める計算も行わなくて良い。
【０１３３】
従って、学習マップｚによる類似度計算Ｓを省略することによって、識別部２８における処理を識別部１７より高速化できる。
【０１３４】
第２実施形態における登録用画像データの登録過程を図５Ａに基づいて説明する。なお、図５Ａで図２Ａ中と同じステップ番号の説明は省略する。
【０１３５】
ステップＳ１０２に続いて、学習マップ記憶部２３を用いて、抽出された特徴点の位置（即ち、学習マップ）を蓄積手段に全て蓄積する。また、その学習マップを特定の方法で幾何的変形（あるいは、幾何的変換）し、変形し増えた学習マップも蓄積する。（Ｓ１０３１）。
【０１３６】
そして、相互学習マップ間距離テーブル作成・記憶部２４を用いて、学習マップ記憶部２３に記憶された学習マップから相互学習間距離テーブルＴを作成し記憶する（Ｓ１０３２）。
【０１３７】
第２実施形態におけるパターン認識方法を図５Ｂに基づいて説明する。なお、図５Ｂで図２Ｂ中と同じステップ番号の説明は省略する。
【０１３８】
ステップＳ１０６１に続いて、識別部２８によって、類似度を計算し、識別物体に関する特徴点を取得する（Ｓ１０７１）。
【０１３９】
第２実施形態における最小類似度計算処理の手順を図６に基づいて説明する。なお、図６で図３と同じステップ番号の説明は省略する。
【０１４０】
まず、配列のフラグＦＬＡＧ２(ｚ)（以下、単にＦＬＡＧ２(ｚ)という）の全要素をＯＦＦに設定し、その後、式６で計算された距離ｑa,bが正となる学習マップｂのフラグＦＬＡＧ２（ｂ）を全てＯＮに設定する（Ｓ３０１）。
【０１４１】
次に、ｚを「０」に設定する（Ｓ３０２）。
【０１４２】
次に、ＦＬＡＧ２(ｚ)の値をチェックする（Ｓ３０３）。ＦＬＡＧ２(ｚ)の値がＯＦＦの場合、ステップＳ２０１〜Ｓ２０８の処理を行う。ＦＬＡＧ２(ｚ)の値がＯＮの場合、ステップＳ３０４に進む。
【０１４３】
ステップＳ３０４では、ｚに「１」を加算する。
【０１４４】
そして、前記ｚが所定の学習マップ数以上か否かをチェックする（Ｓ３０５）。前記ｚが所定の学習マップ数以上の場合、当該処理を終了する。前記ｚが所定の学習マップ数より小さい場合、ステップＳ３０３に戻る。
【０１４５】
第１及び第２実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）（ＭＰＵ（Ｍｉｃｒｏｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ））が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、実現できる。
【０１４６】
その場合、記憶媒体から読み出されたプログラムコード自体が上述した第１及び第２実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体、例えば、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ−ＲＯＭ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＣＤ−Ｒ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅｃｏｒｄａｂｌｅ）、ＣＤ−ＲＷ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  ＲｅＷｒｉｔａｂｌｅ）、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｋ）、ＨＤＤ等は、第１及び第２実施形態を構成する。
【０１４７】
以上のように、第２実施形態においては、対象が平面上に存在する記号等の場合に、２つの学習マップ間で、特徴量の数が変わらず、１対１に対応付けられているため、式４’が適応できる。そのため、対象が平面上に存在する記号等の場合に、物体に関する特徴点を高速に識別できる。
【０１４８】
また、第１及び第２実施形態によれば、３次元物体をさまざまな方向から予め撮影した画像から特徴点を自動抽出した学習マップを蓄積し、認識用画像から抽出した特徴点に該当する学習マップが含まれているか否かを探索処理できる。
【０１４９】
さらに、前記探索処理は高速化が可能であり、結果として、特徴点照合による物体認識を高速に実行できる。
【０１５０】
以上、本発明において、記載された具体例に対してのみ詳細に説明したが、本発明の技術思想の範囲で多彩な変形および修正が可能であることは、当業者にとって明白なことであり、このような変形および修正が特許請求の範囲に属することは当然のことである。
【０１５１】
例えば、第１及び第２実施形態の変形例としては、登録用画像データに関する特徴抽出と認識用画像データに関する特徴抽出を１つの特徴抽出部で行っても良い。
【図面の簡単な説明】
【０１５２】
【図１】第１実施形態におけるパターン認識装置の構成図。
【図２】第１実施形態における登録用画像データの登録過程（Ａ）及びパターン認識方法（Ｂ）を示すフローチャート。
【図３】第１実施形態における最小類似度計算処理の手順を示すフローチャート。
【図４】第２実施形態におけるパターン認識装置の構成図。
【図５】第２実施形態における登録用画像データの登録過程（Ａ）及びパターン認識方法（Ｂ）を示すフローチャート。
【図６】第２実施形態における最小類似度計算処理の手順を示すフローチャート。
【図７】基本的なパターン認識の原理説明図。
【符号の説明】
【０１５３】
１…２次元マップ
２…入力画像
３…特徴点
４…学習マップと入力画像の一部分であって、学習マップに最も類似している位置
１１…登録用画像データ入力部
１２…特徴点抽出部
１３…学習マップ記憶部
１４…認識用画像データ入力部
１５…特徴点抽出部
１６…距離参照テーブル作成部
１７…識別部
１８…出力部
２３…学習マップ記憶部
２４…相互学習マップ間距離テーブル作成・記憶部
２８…識別部
【図１】
2007299364.tif 000026
【図２】
2007299364.tif 000027
【図３】
2007299364.tif 000028
【図４】
2007299364.tif 000029
【図５】
2007299364.tif 000030
【図６】
2007299364.tif 000031
【図７】
2007299364.tif 000032