画像処理装置および方法、記録媒体、並びにプログラム
【課題】画像の拡大縮小に拘らず、物体を確実に認識することができるようにする。
【解決手段】 多重解像度生成部２１により、モデル画像から多重解像度画像を生成し、特徴量抽出部２３により各解像度の特徴点の特徴量を抽出し、モデル辞書登録部２４に登録する。入力されたオブジェクト画像の多重解像度を多重解像度生成部３１により生成し、その特徴点と特徴量を特徴量比較部３５において、モデル辞書登録部２４に登録されている特徴量と比較する。この比較は、kdツリー構築部３４により構築されたkdツリーを利用して行われる。モデル姿勢推定部３６は、特徴量比較部３５による特徴量の比較結果に基づいて、オブジェクト画像に含まれるモデル画像の姿勢を推定し、その物体の姿勢パラメータを出力する。本発明は、ロボットに適用することができる。
【解決手段】 多重解像度生成部２１により、モデル画像から多重解像度画像を生成し、特徴量抽出部２３により各解像度の特徴点の特徴量を抽出し、モデル辞書登録部２４に登録する。入力されたオブジェクト画像の多重解像度を多重解像度生成部３１により生成し、その特徴点と特徴量を特徴量比較部３５において、モデル辞書登録部２４に登録されている特徴量と比較する。この比較は、kdツリー構築部３４により構築されたkdツリーを利用して行われる。モデル姿勢推定部３６は、特徴量比較部３５による特徴量の比較結果に基づいて、オブジェクト画像に含まれるモデル画像の姿勢を推定し、その物体の姿勢パラメータを出力する。本発明は、ロボットに適用することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置および方法、記録媒体、並びにプログラムに関し、特に、視点変化、明度変化に強く、画像の拡大縮小に拘らず、物体を確実に認識することができるようにした画像処理装置および方法、記録媒体、並びにプログラムに関する。
【背景技術】
【０００２】
例えば、ロボットにより対象物体を認識するための実用化されている対象物体認識技術の多くは、残差逐次検定法や相互相関係数によるテンプレートマッチング手法を用いている。しかしテンプレートマッチング手法は、検出対象物体が入力画像中に変形なく出現すると仮定できる特殊な場合には有効であるが、視点や照明状態の一定でない一般的な画像からの物体認識環境においては有効でない。
【０００３】
他方、対象物体の形状特徴と、画像分割手法によって切り出された入力画像中の各領域の形状特徴とをマッチングする形状マッチング手法も提案されているが、上述のような一般的な物体認識環境においては、領域分割の結果が安定せず、入力画像中の物体の良質な形状記述が難しくなる。特に、検出対象物体が、他の物体に部分的に隠されている場合などは認識が非常に困難になる。
【０００４】
以上のような、入力画像全体あるいは領域の全体的な特徴を用いたマッチング手法に対し、画像から特徴的な点やエッジを抽出し、それらが構成する線分集合やエッジ集合の空間的位置関係を線図形やグラフとして表現し、線図形間やグラフ間の構造類似性に基づいてマッチングを行う方法も提案されている。しかし、これらの手法は、ある特化した対象物に対してはうまく作用するが、画像の変形により、時として安定した特徴点間構造が抽出されず、特に前に述べたような部分的に隠されている物体の認識は困難となる。
【０００５】
そこで、画像から特徴的な点（特徴点）を抽出し、特徴点とその局所近傍の画像情報から得られる特徴量を用いたマッチング手法が提案されている。このような特徴点の部分的画像変形に対して不変な局所特徴量を用いるマッチング手法では、前述の手法に比べ画像の変形に対しても、検出対象が部分的に隠されるような場合にも安定した検出が可能となる。拡大縮小変換に対して不変性を持つ特徴点の抽出法として、画像のスケールスペースを構築し、各スケール画像のDifference of Gaussian（DoG）フィルタ出力の局所極大点及び局所極小点のうち、スケール方向の変化によっても位置が変化しない点をスケール特徴点として抽出する方法（非特許文献１または非特許文献２）や、画像のスケールスペースを構築し、各スケール画像からHarrisコーナー検出器により抽出されたコーナー点のうち、スケールスペース画像のLaplacian of Gaussian（LoG）フィルタ出力の局所極大を与える点を特徴点として抽出する方法（非特許文献３）などが提案されている。
【０００６】
さらに、このように抽出された特徴点において、視線変化に対して不変な特徴量を選ぶことが好ましい。例えば、 Schmid & Mohr は、 Harris コーナー検出器を用いて検出されたコーナーを特徴点とし、その特徴点付近の回転不変特徴量を用いたマッチング手法を提案している（非特許文献４）。
【非特許文献１】D. Lowe, “Object recognition from local scale-invariant features,” in Proc. International Conference on Computer Vision, Vol. 2, pp. 1150-1157, September 20-25, 1999, Corfu, Greece.
【非特許文献２】D. Lowe, “Distinctive image features from scale-invariant keypoints,” accepted for publication in the International Journal of Computer Vision, 2004. K. Mikolajczyk, C. Schmid, “Indexing based on scale invariant interest points,” International Conference on Computer Vision, 525-531, July 2001.
【非特許文献３】K. Mikolajczyk, C. Schmid, “Indexing based on scale invariant interest points,” International Conference on Computer Vision, 525-531, July 2001. Schmid, C., and R. Mohr, “Local grayvalue invariants for image retrieval,” IEEE PAMI, 19, 5, 1997, pp. 530-534.
【非特許文献４】Schmid, C., and R. Mohr, “Local grayvalue invariants for image retrieval,” IEEE PAMI, 19, 5, 1997, pp. 530-534.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、コーナーの特徴量は、画像の拡大縮小変換に対しては不変性を持たないため、拡大縮小変換のある場合には、正確な認識が困難となる課題がある。
【０００８】
本発明は、このような状況に鑑みてなされたものであり、画像が拡大縮小されている場合にも、視点変化や明度変化による影響を軽減し、物体を確実に認識することができるようにするものである。
【課題を解決するための手段】
【０００９】
請求項１の画像処理装置は、入力された画像から予め登録されているモデル画像を認識する画像処理装置において、入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成手段と、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出手段と、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出手段と、入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較手段と、前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定手段とを備えることを特徴とする。
【００１０】
前記特徴量抽出手段は、第１のタイプの特徴量として特徴点近傍の濃度勾配の方向ヒストグラムを抽出し、第２のタイプの特徴量として次元縮退濃度勾配ベクトルを抽出するようにすることができる。
【００１１】
前記比較手段は、タイプ毎にkdツリーとされたモデル画像の特徴量群を、入力された画像の特徴量に基づいてk Nearest Neighbor (k-NN) 探索することで、候補対応特徴点組を生成するようにすることができる。
【００１２】
前記比較手段は、各タイプにおいて共通に抽出された特徴量を有する特徴点を候補対応特徴点組とするようにすることができる。
【００１３】
前記候補対応特徴点組を、モデル画像の位置姿勢を決める画像変換パラメータで規定されるパラメータ空間上に投票し、その最大投票数を閾値と比較することで絞り込む絞り込み手段をさらに備え、姿勢推定手段は、絞り込まれた候補対応特徴点組に基づいて、入力された画像の姿勢を推定するようにすることができる。
【００１４】
前記姿勢推定手段は、ランダムに選択したＮ組の候補対応特徴点組により決定されるモデル画像の位置姿勢を決める画像変換パラメータをパラメータ空間に投射し、パラメータ空間上で形成されるクラスタのうち、最多メンバ数を有するクラスタを求め、そのメンバから最小自乗法により求まる前記モデル画像の位置姿勢を決める画像変換パラメータをモデル画像を認識する認識結果として出力するようにすることができる。
【００１５】
前記姿勢推定手段は、最多メンバ数を有するクラスタのセントロイドを検出し、セントロイドからなるモデル画像の位置姿勢を決める画像変換パラメータをモデル画像を認識する認識結果として出力するようにすることができる。
【００１６】
前記多重解像度画像生成手段は、学習時における場合より粗い精度で多重解像度画像を生成するようにすることができる。
【００１７】
請求項９の画像処理方法は、入力された画像から予め登録されているモデル画像を認識する画像処理装置の画像処理方法において、入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成ステップと、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップと、前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップとを含むことを特徴とする。
【００１８】
請求項１０の記録媒体のプログラムは、入力された画像から予め登録されているモデル画像を認識する画像処理装置のプログラムであって、入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成ステップと、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップと、前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップとを含むことを特徴とする。
【００１９】
請求項１１のプログラムは、入力された画像から予め登録されているモデル画像を認識する画像処理装置のプログラムであって、入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成ステップと、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップと、前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップとをコンピュータに実行させることを特徴とする。
【００２０】
請求項１２の画像処理装置は、認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置において、前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成手段と、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出手段と、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出手段と、前記モデル画像の前記特徴量を登録する登録手段とを備えることを特徴とする。
【００２１】
前記特徴量抽出手段は、第１のタイプの特徴量として特徴点近傍の濃度勾配の方向ヒストグラムを抽出し、第２のタイプの特徴量として次元縮退濃度勾配ベクトルを抽出するようにすることができる。
【００２２】
前記登録手段は、モデル画像の特徴量群を、タイプ毎にkdツリーとして登録するようにすることができる。
【００２３】
請求項１５の画像処理方法は、認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置の画像処理方法において、前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップと、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、前記モデル画像の前記特徴量を登録する登録ステップとを含むことを特徴とする。
【００２４】
請求項１６の記録媒体のプログラムは、認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置のプログラムであって、前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップと、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、前記モデル画像の前記特徴量を登録する登録ステップとを含むことを特徴とする。
【００２５】
請求項１７のプログラムは、認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置のプログラムであって、前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップと、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、前記モデル画像の前記特徴量を登録する登録ステップとをコンピュータに実行させることを特徴とする。
【００２６】
本発明においては、入力された画像から多重解像度画像が生成され、その多重解像度画像のそれぞれの解像度の画像について特徴点が抽出される。特徴点における少なくとも２つの局所的な特徴量が抽出され、その特徴量とモデル画像の特徴量が比較され、類似する特徴量を有する特徴点の組としての候補対応特徴点組が生成され、それに基づいて、入力された画像の姿勢が推定される。
【００２７】
また、本発明においては、認識時における場合より細かい精度で多重解像度画像が生成される。多重解像度画像のそれぞれの解像度の画像について特徴点が抽出され、特徴点における少なくとも２つの局所的な特徴量が抽出され、登録される。
【発明の効果】
【００２８】
本発明によれば、物体を認識することができる。特に、本発明によれば、画像が拡大縮小されている場合にも、視点変化や明度変化に伴う画像の変化に拘らず、また物体が部分的に隠されてしまっているような場合でも、物体を確実に認識することが可能となる。
【００２９】
また、本発明によれば、物体を認識することが可能な特徴量を登録することができる。特に、本発明によれば、登録画像に対して認識対象物体の画像が拡大縮小されている場合にも、視点変化や明度変化に伴う画像の変化に拘らず、姿勢変化による画像変化に対してロバストに認識ができるような特徴点および特徴量を抽出し、登録することができる。
【発明を実施するための最良の形態】
【００３０】
以下に本発明の最良の形態を説明するが、開示される発明と実施の形態との対応関係を例示すると、次のようになる。明細書中には記載されているが、発明に対応するものとして、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その発明に対応するものではないことを意味するものではない。逆に、実施の形態が発明に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その発明以外の発明には対応しないものであることを意味するものでもない。
【００３１】
さらに、この記載は、明細書に記載されている発明の全てを意味するものではない。換言すれば、この記載は、明細書に記載されている発明であって、この出願では請求されていない発明の存在、すなわち、将来、分割出願されたり、補正により出現し、追加される発明の存在を否定するものではない。
【００３２】
請求項１の画像処理装置は、入力された画像から予め登録されているモデル画像を認識する画像処理装置（例えば、図１の認識部１２を有する画像処理装置１）において、入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像（例えば、図４の多重解像度画像）を生成する多重解像度画像生成手段（例えば、図１３のステップS132の処理を実行する図１の多重解像度生成部31）と、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出手段（例えば、図１３のステップS136の処理を実行する図１の特徴点抽出部32）と、前記特徴点における少なくとも２つの局所的な特徴量（例えば、図８の特徴点近傍の濃度勾配の方向ヒストグラム（タイプ１の特徴量）、図１１の最下段の線形補間リサンプリングされたタイプ2の特徴量）を抽出する特徴量抽出手段（例えば、図１３のステップS138乃至S142、図１４のステップS143乃至S145の処理を実行する図１の特徴量抽出部33）と、入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較手段（例えば、図１４のステップS150,S151の処理を実行する図１の特徴量比較部35）と、前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定手段（例えば、図１５のステップS158の処理を実行する図１のモデル姿勢推定部36）とを備えることを特徴とする。
【００３３】
前記特徴量抽出手段は、第１のタイプの特徴量として前記特徴点近傍の濃度勾配の方向ヒストグラム（例えば、図８の特徴点近傍の濃度勾配の方向ヒストグラム）を抽出し、第２のタイプの特徴量として次元縮退濃度勾配ベクトル（例えば、図１１の最下段の線形補間リサンプリングされたタイプ2の特徴量）を抽出する。
【００３４】
前記比較手段は、前記タイプ毎にkdツリーとされた前記モデル画像の特徴量群を、入力された画像の前記特徴量に基づいてk Nearest Neighbor (k-NN) 探索することで、前記候補対応特徴点組を生成する（例えば、図１７の処理）。
【００３５】
前記比較手段は、各タイプにおいて共通に抽出された前記特徴量を有する前記特徴点を前記候補対応特徴点組とする（例えば、図１７の四角形と円のペア、並びに四角形と十字図形のペア、ただし図中の四角形、五角形、三角形、円、または十字の図形は特徴点を表す）。
【００３６】
前記画像処理装置は、前記候補対応特徴点組を、前記モデル画像の位置姿勢を決める画像変換パラメータで規定されるパラメータ空間（例えば、画像変換パラメータ（scl，θ，dX，dY）で規定されるパラメータ空間）上に投票し、その最大投票数を閾値と比較することで絞り込む絞り込み手段（例えば、図２２のステップS301乃至S310の処理を実行する図２１の対応特徴点ペア絞込み部６１）をさらに備え、前記姿勢推定手段は、絞り込まれた前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する。
【００３７】
前記姿勢推定手段は、ランダムに選択したＮ組の前記候補対応特徴点組により決定される前記モデル画像の位置姿勢を決める画像変換パラメータ（例えば、ユークリッド変換、相似変換、アフィン変換、射影変換）をパラメータ空間に投射し、前記パラメータ空間上で形成されるクラスタのうち、最多メンバ数を有するクラスタを求め、そのメンバ（すなわち対応特徴点組群）から最小自乗法により求まる前記モデル画像の位置姿勢を決める画像変換パラメータを前記モデル画像を認識する認識結果として出力する（例えば、図１９のステップS201乃至S206の処理）。
【００３８】
前記多重解像度画像生成手段は、学習時における場合より粗い精度で前記多重解像度画像を生成する（例えば、図１３のステップS132の処理）。
【００３９】
請求項９の画像処理方法、請求項１０の記録媒体のプログラム、請求項１１のプログラムは、入力された画像から予め登録されているモデル画像を認識する画像処理装置（例えば、図１の認識部１２を有する画像処理装置1）の画像処理方法またはプログラムにおいて、入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像（例えば、図４の多重解像度画像）を生成する多重解像度画像生成ステップ（例えば、図１３のステップS132）と、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップ（例えば、図１３のステップS136）と、前記特徴点における少なくとも２つの局所的な特徴量（例えば、図８の特徴点近傍の濃度勾配の方向ヒストグラム、図１１の最下段の線形補間リサンプリングされたタイプ2の特徴量）を抽出する特徴量抽出ステップ（例えば、図１３のステップS138乃至S142、図１４のステップS143乃至S145）と、入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップ（例えば、図１４のステップS150,S151）と、前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップ（例えば、図１５のステップS158）とを含むことを特徴とする。
【００４０】
請求項１２の画像処理装置は、認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置（例えば、図１の学習部11を有する画像処理装置1）において、前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像（例えば、図４の多重解像度画像）を、認識時における場合より細かい精度で生成する多重解像度画像生成手段（例えば、図２のステップS12の処理を実行する図１の多重解像度生成部21）と、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出手段（例えば、図２のステップS16の処理を実行する図１の特徴点抽出部22）と、前記特徴点における少なくとも２つの局所的な特徴量（例えば、図８の特徴点近傍の濃度勾配の方向ヒストグラム、図１１の最下段の線形補間リサンプリングされたタイプ2の特徴量）を抽出する特徴量抽出手段（例えば、図２のステップS19、図３のステップS25の処理を実行する図１の特徴量抽出部23）と、前記モデル画像の前記特徴量を登録する登録手段（例えば、図３のステップS29の処理を実行する図１のモデル辞書登録部24）とを備えることを特徴とする。
【００４１】
前記特徴量抽出手段は、第１のタイプの特徴量として前記特徴点近傍の濃度勾配の方向ヒストグラム（例えば、図８の特徴点近傍の濃度勾配の方向ヒストグラム）を抽出し、第２のタイプの特徴量として次元縮退濃度勾配ベクトル（例えば、図１１の最下段の線形補間リサンプリングされたタイプ2の特徴量）を抽出する。
【００４２】
前記登録手段は、前記モデル画像の特徴量を、前記タイプ毎にkdツリーとして登録する（例えば、図１のkdツリー構築部34の処理）。
【００４３】
請求項１５の画像処理方法、請求項１６の記録媒体のプログラム、請求項１７のプログラムは、認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置（例えば、図１の学習部11を有する画像処理装置1）の画像処理方法またはプログラムにおいて、前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像（例えば、図４の多重解像度画像）を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップ（例えば、図２のステップS12）と、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップ（例えば、図２のステップS16）と、前記特徴点における少なくとも２つの局所的な特徴量（例えば、図８の特徴点近傍の濃度勾配の方向ヒストグラム、図１１の最下段の線形補間リサンプリングされたタイプ2の特徴量）を抽出する特徴量抽出ステップ（例えば、図２のステップS19、図３のステップS25）と、前記モデル画像の前記特徴量を登録する登録ステップ（例えば、図３のステップS29）とを含むことを特徴とする。
【００４４】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。この実施の形態は、本発明を、複数のオブジェクトを含む入力画像であるオブジェクト画像と、検出対象となるモデルを含むモデル画像（予め登録されている）とを比較し、オブジェクト画像からモデルを抽出する画像処理装置に適用したものである。
【００４５】
本実施の形態における画像処理装置の概略構成を図１に示す。この画像処理装置１はモデルの学習処理を行う学習部１１と、入力画像中の物体を認識する認識部１２の２つの部分から構成される。
【００４６】
学習部１１は、多重解像度生成部２１、特徴点抽出部２２、特徴量抽出部２３、およびモデル辞書登録部２４により構成されている。
【００４７】
多重解像度生成部２１は、入力されたモデル画像から多重解像度画像を生成する。特徴点抽出部２２は、多重解像度生成部２１により生成された多重解像度の各画像から特徴点を抽出する。特徴量抽出部２３は、特徴点抽出部２２により抽出された各特徴点の特徴量を抽出する。モデル辞書登録部２４は、特徴量抽出部２３により抽出されたモデル画像の特徴量群を登録する。
【００４８】
認識部１２は、多重解像度生成部３１、特徴点抽出部３２、特徴量抽出部３３、kdツリー構築部３４、特徴量比較部３５、およびモデル姿勢推定部３６により構成される。
【００４９】
多重解像度生成部３１は、入力されたオブジェクト画像から、各多重解像度の画像を生成する。特徴点抽出部３２は、多重解像度生成部３１により生成された多重解像度の画像から特徴点を抽出する。特徴量抽出部３３は、特徴点抽出部３２により抽出された各特徴点の特徴量を抽出する。これらの多重解像度生成部３１、特徴点抽出部３２、および特徴量抽出部３３により行われる処理は、学習部１１における多重解像度生成部２１、特徴点抽出部２２、および特徴量抽出部２３において行われる処理と同様の処理である。
【００５０】
kdツリー構築部３４は、モデル辞書登録部２４に登録されている特徴量からkdツリーを構築する。特徴量比較部３５は、特徴量抽出部３３により抽出された特徴量と、kdツリー構築部３４により構築されたkdツリーとして表現された認識対象となる全モデル画像（またはモデル毎処理を行う場合には各モデル画像）の特徴量群を比較する。モデル姿勢推定部３６は、特徴量比較部３５による比較結果に基づいて、オブジェクト画像に含まれるモデルの有無とその姿勢（モデル姿勢）を推定し、そのモデルの姿勢を表すパラメータ（物体姿勢パラメータ）を出力する。
【００５１】
なお、学習部１１と認識部１２は、常に両方が同時に存在する必要はない。学習部１１により予め学習された結果、必要な情報が登録されたモデル辞書登録部２４を認識部１２に搭載するか、或いは無線で利用できるようにするようにしてもよい。
【００５２】
次に、図２と図３のフローチャートを参照して、学習部１１における学習処理について説明する。
【００５３】
多重解像度生成部２１は、後述するステップＳ２８において、全モデルを処理したと判定するまで、ステップＳ１１乃至Ｓ２７の処理を繰り返す。そこで、ステップＳ１１において、多重解像度生成部２１は、１つの未処理モデルを選択する。ステップＳ１２において、多重解像度生成部２１は、多重解像度群を生成する。具体的には、多重解像度生成部２１は、入力された学習対象のモデル画像を所定の倍率に従って縮小し、多重解像度画像群を生成する。例えば、最低解像度の画像である原画像からの縮小率をα、出力する多重解像度画像の数をＮ（原画像を含む）とするとき、ｋ番目（原画像をｋ＝０とする）の多重解像度の解像度画像Ｉ[k]は、原画像Ｉ[0]を縮小率α×（Ｎ−ｋ）で、線形補間縮小することで生成される。
【００５４】
あるいは他の方法としては、解像度の一段階低い画像を生成するための縮小率をγ（固定値）とする、つまりＩ[0]を縮小率γkで、線形補間縮小することでＩ[k]を生成する方法も考えられる。
【００５５】
図４は、パラメータＮ＝１０，α＝0.1とした場合に生成される多重解像度画像群を示す。図４の例においては、原画像Ｉ[0]を縮小率0.9で縮小した画像Ｉ[1]、縮小率0.8で縮小した画像Ｉ[2]、・・・、縮小率0.1で縮小した画像Ｉ[9]の合計１０段階の多重解像度画像が生成されている。縮小率を規定する係数ｋの値が大きくなるほど画像がより小さい大きさに縮小される結果、各フレームの画枠自体も、係数ｋの値が大きい程小さくなる。
【００５６】
次に、特徴点抽出部２２は、後述するステップＳ２７において、全解像度画像を処理したと判定するまで、ステップＳ１３乃至Ｓ２６の処理を繰り返し、多重解像度生成部２１により生成された各解像度画像Ｉ[k]（ｋ＝０，・・・，Ｎ−１）から、画像の拡大縮小変換（スケール変換）があってもロバストに抽出されるような特徴点（スケール不変特徴点）を抽出するのであるが、スケール不変特徴点の抽出法としては、画像のスケールスペースを構築し、各スケール画像のDifference of Gaussian（DoG）フィルタ出力の局所極大点（局所的な所定の範囲の最大点）及び局所極小点（局所的な所定の範囲の最小点）のうち、スケール方向の変化によっても位置が変化しない点をスケール特徴点として抽出する方法（D. Lowe, “Object recognition from local scale-invariant features,” in Proc. International Conference on Computer Vision, Vol. 2, pp. 1150-1157, September 20-25, 1999, Corfu, Greece.）や、画像のスケールスペースを構築し、各スケール画像からHarrisコーナー検出器により抽出されたコーナー点のうち、スケールスペース画像のLaplacian of Gaussian（LoG）フィルタ出力の局所極大を与える点を特徴点として抽出する方法（K. Mikolajczyk, C. Schmid, “Indexing based on scale invariant interest points,” International Conference on Computer Vision, 525-531, July 2001.）などがある。スケール不変特徴点が抽出できる手法であれば、どのような抽出法でも特徴点抽出部２２に適用が可能である。
【００５７】
ここでは発明の一実施の形態として、スケール不変特徴点の抽出法として、D.ロー（D. Lowe）が提案する方法（“Distinctive image features from scale-invariant keypoints,” accepted for publication in the International Journal of Computer Vision, 2004.）を基礎とした方法を説明する。この手法では、スケール不変特徴点抽出対象画像のスケールスペース表現（T. Lindeberg, “Scale-space: A framework for handling image structures at multiple scales.”, Journal of Applied Statistics, vol. 21, no. 2, pp. 224-270, 1994”）を介して、当該画像のDoGフィルタ出力から、スケール方向も考慮に入れた局所極大点及び局所極小点が特徴点として抽出される。
【００５８】
そこで、ステップＳ１３において、特徴点抽出部２２は、各解像度画像のうちの未処理解像度画像を選択する。そして、ステップＳ１４において、特徴点抽出部２２は、スケールスペースの解像度画像を生成する。すなわち、スケール不変特徴点抽出対象画像Ｉ（多重解像度生成部２１で生成された各解像度画像（ｋ＝０，１，２，・・・，９の各解像度画像）のうちの１つの解像度画像が特徴点抽出対象画像となる）のスケールスペースが生成される。スケールスペースのｓ番目（ｓ＝０,・・・，Ｓ−１）の解像度画像Ｌsは、対象画像Ｉを式（１）に示される２次元ガウス関数を用いて、σ＝ｋs σ0で畳み込み積分（ガウスフィルタリング）することで生成される。
【００５９】
【数１】
【００６０】
ここでσ0は、対象画像Ｉのノイズ除去を目的としたぼかし度を決めるパラメータであり、ｋはスケールスペースの各解像度間で共通のぼかし度に関するコンスタントファクタであり、解像度画像Ｉ[k]のｋとは別のファクタである。なお、画像の水平方向をＸ軸、垂直方向をＹ軸としている。
【００６１】
図５は、このようにして生成されたスケールスペースの例を表している。この例においては、画像Ｉにそれぞれ以下の５個の２次元ガウス関数を用いて生成された解像度画像Ｌ0乃至Ｌ4を表している。
【００６２】
【数２】
【００６３】
なお、式（２）乃至式（６）の右辺の畳み込み積分の記号の右辺の項は、次式を表す。すなわち、実質的に式（１）と同一である。
【００６４】
【数３】
【００６５】
図５では、解像度レベル数Ｓ＝５とされている。
【００６６】
次に、ステップＳ１５で、特徴点抽出部２２は、DoGフィルタ出力画像を演算する。すなわち、このように得られた特徴点抽出対象のスケールスペースの各解像度画像ＬsのDoGフィルタ出力画像が求められる。このDoGフィルタは、画像の輪郭強調のために用いられる２次微分フィルタの一種であり、人間の視覚系で網膜から外側膝状体で中継されるまでに行われている処理の近似モデルとして、LoGフィルタと共によく用いられるものである。DoGフィルタの出力は、２つのガウスフィルタ出力画像の差分を取ることで効率よく得られる。すなわち、図５の中央の列に示されるように、ｓ番目（ｓ＝０,・・・，Ｓ−２）の解像度のDoGフィルタ出力画像Ｄsは、解像度画像Ｌsを、その１段上の階層の解像度画像Ｌs+1から減算する（Ｌs+1−Ｌsを演算する）ことで得られる。
【００６７】
次に、ステップＳ１６で、特徴点抽出部２２は、スケール不変特徴点を抽出する。具体的には、DoGフィルタ出力画像Ｄs（ｓ＝１,・・・，Ｓ−３）上のピクセルのうち、DoGフィルタ出力画像Ｄsの直接近傍領域（本実施の形態の場合、所定の位置の３×３個の画素の領域）、それより１段下位のDoGフィルタ出力画像Ｄs-1、並びにそれより１段上位のDoGフィルタ出力画像Ｄs+1上の同位置（対応する位置）の直接近傍領域の合わせて２７ピクセルにおいて、局所極大（２７ピクセルのうちの最大値）、局所極小（２７ピクセルのうちの最小値）となるピクセルがスケール不変特徴点として抽出され、特徴点群Ｋs（ｓ＝１,・・・，Ｓ−３）として保持される。図５の右側の列に、この特徴点群Ｋsが示されている。こうして抽出された特徴点はファクタがｋ2の解像度変化（つまりスケール変化）に対して、位置の不変性を持つスケール不変特徴点である。
【００６８】
特徴点抽出部２２は、後述するステップＳ２７で、全解像度画像を処理したと判定するまで、ステップＳ１３乃至Ｓ１６の処理を繰り返し、多重解像度生成部２１により生成された多重解像度レベル画像Ｉ[k]のそれぞれに対し、スケール不変特徴点群を抽出する。
【００６９】
次に、特徴量抽出部２３は、ステップＳ１７乃至Ｓ２５の処理を、ステップＳ２６で全特徴点を処理したと判定するまで繰り返し、各多重解像度レベル画像Ｉ[k]から抽出された各特徴点における特徴量を抽出する。以下においては、特徴点における特徴量を、文脈に応じて、特徴点特徴量または単に特徴量と呼ぶ。
【００７０】
特徴点特徴量としては、画像の回転変換、明度変化に対して不変な特徴量が用いられる。１つの特徴点に対して、複数の特徴量をあててもかまわない。その場合には、後段の特徴量比較部３５において、異なる特徴量での比較結果を統合する処理が必要となる。この実施の形態の場合、特徴量として、当該特徴点が抽出された画像の特徴点近傍領域の濃度勾配情報（各点における濃度勾配強度及び濃度勾配方向）から導出される２つの特徴量が用いられる。１つは、当該特徴点近傍領域における支配的な濃度勾配方向（以下、カノニカル方向と呼ぶ）で補正された方向ヒストグラムであり、他の１つは、カノニカル方向で補正された低次元縮退された濃度勾配ベクトルである。
【００７１】
第１の特徴量（タイプ１の特徴量）は、特徴点近傍の濃度勾配方向に関するヒストグラム（方向ヒストグラム）を、その支配的方向でゼロ補正したものである。この第１の特徴量を抽出するために、特徴量抽出部２３は、ステップＳ１７において、１つの未処理特徴点を選択する。そして、ステップＳ１８で、特徴量抽出部２３は、濃度勾配強度Ｍx,yと方向Ｒx,yを求める。すなわち、図６に示されるように、特徴点近傍（本実施の形態では、当該特徴点Ｐを中心として直径７ピクセル（半径3.5ピクセル）の範囲に入るピクセル群）の濃度勾配強度Ｍx,y、及び方向Ｒx,yが、それぞれ式（８）と式（９）により求められる。同式中のｘ，ｙは、濃度勾配を求めるピクセルの画像上の座標であり、Ｉx,yは、その画素値である。
【００７２】
【数４】
【００７３】
次に、ステップＳ１９で、特徴量抽出部２３は方向ヒストグラムを生成する。具体的には、特徴点近傍中の各ピクセルの方向Ｒx,yに基づいて、階級幅Δθ、階級数360°／Δθの方向ヒストグラム（本実施の形態では、Δθ＝１０°）の該当する階級に、各ピクセルの度数が累積される。このとき、図７に示されるように階級の量子化誤差の影響を小さくするため、度数（図７における縦軸）としては、階級（図７における横軸）の中心値から方向Ｒx,yへの距離の近さに比例した値が累積される。つまり、方向Ｒx,yから最も近い２つの階級をｇ，ｇ＋１とし、それぞれの中心値と方向Ｒx,yとの距離をｄ1，ｄ2とすると、階級ｇ，ｇ＋１に加算する度数値は、それぞれｄ2／（ｄ1＋ｄ2），ｄ1／（ｄ1＋ｄ2）となる。これにより、量子化誤差が少なくなる。
【００７４】
次に、ステップＳ２０で、特徴量抽出部２３は度数を正規化する。すなわち、得られた方向ヒストグラムの度数が、特徴点近傍ピクセル数（直径７ピクセルの範囲に入るピクセル数）で割算することにより正規化される。このように、勾配方向のみを累積することで、明度変化に対して強い特徴量を得ることができる。
【００７５】
さらに、特徴量抽出部２３は、ステップＳ２１でカノニカル方向を抽出し、ステップＳ２２で角度をカノニカル方向で正規化する。具体的には、回転変換に不変な特徴量とするために、得られた方向ヒストグラムの強いピークを与える角度としてのカノニカル方向が抽出され、そのカノニカル方向としての角度が０度になるようにヒストグラムをシフトすることで、角度の正規化が行われる。コーナー付近に抽出された特徴点に関するヒストグラムでは、そのエッジに垂直な方向に複数の強いピークが現れるため、このような場合は、強いピークごとにその角度が０度になるように補正した（正規化した）方向ヒストグラムが生成される。つまり、カノニカル方向の数だけ、別々に特徴量が生成される。ピークがカノニカル方向であるための基準は、例えば、最大累積値の８０％以上の累積値を与えるピーク方向とされる。
【００７６】
例えば、図８に示される方向ヒストグラムにおいては、角度80度の度数Ｖ80と角度200度の度数Ｖ200の２つのピークが存在する。すなわち、角度80度と角度200度が、カノニカル方向となる。この場合、図９に示されるように、カノニカル方向としての角度80度が０度となるように正規化されたヒストグラムと、図１０に示されるように、カノニカル方向としての角度200度が０度になるように正規化されたヒストグラムが生成される。
【００７７】
以上の処理で得られるタイプ１の特徴量は、方向ヒストグラムの階級数と同じ次元の特徴ベクトル（本実施の形態では、３６（＝360°／10°）次元ベクトル、すなわち、３６個の階級の度数を表わす数字からなるベクトル）となる。
【００７８】
次に、第２の特徴量（タイプ２の特徴量）として、低次元縮退濃度勾配ベクトルが求められる。タイプ１の特徴量が、特徴点近傍内ピクセルの空間的配置を無視し、特徴点近傍局所領域での濃度勾配ベクトルの方向の傾向（頻度）のみに注目しているのに対し、タイプ２の特徴量は、特徴点近傍の各濃度勾配ベクトルの空間的配置に注目する。この２種類の特徴量を後述する手法で特徴量比較に用いることで、視点変化、明度変化に強い認識を実現する。
【００７９】
タイプ２の特徴量の抽出のために、まず、ステップＳ２３で、特徴量抽出部２３は、特徴点近傍画像を回転補正する。すなわち、上述の処理で得られた特徴点近傍のカノニカル方向が０度になるように特徴点近傍画像が回転補正される。さらに、ステップＳ２４で、特徴量抽出部２３は、濃度勾配ベクトル群を演算する。例えば、図１１の上段に示されている特徴点近傍のピクセルの濃度勾配が、図８に示されるように分布している場合、上述したように、カノニカル方向は、80度と200度の方向となる。そこで、図１１の中段の左側の図に示されるように、上段の画像をカノニカル方向80度が０度になるように、特徴点近傍画像が、この例の場合時計方向に回転される。そして、その濃度勾配ベクトル群が演算される。このことは、結局、図８の角度80度のカノニカル方向を０度として正規化して得られた図９の方向ヒストグラムの濃度勾配ベクトル群を得ることに等しい。
【００８０】
また、同様に、図１１の中段の右側に示されるように、特徴点近傍画像が、200度のカノニカル方向が０度になるように回転補正される。そして、その画像の濃度勾配ベクトル群が演算される。このことは、図８の角度200度のカノニカル方向を０度として正規化することで得られた図１０の方向ヒストグラムの濃度勾配ベクトル群を得ることに等しい。
【００８１】
次に、ステップＳ２５において、特徴量抽出部２３は、濃度勾配ベクトル群を次元縮退する。すなわち、数ピクセル程度の特徴点抽出位置のずれを吸収できるようにするために、この濃度勾配ベクトル群が、図１１の下段の左右に示されているように、例えば、直径７ピクセルの円の内側にほぼ内接する四角形内の５×５ピクセルのベクトル群から、３×３個のベクトル群に線形補間リサンプルすることで次元縮退される。
【００８２】
線形補間リサンプルは、具体的には、図１２に示されるように、リサンプル画像のピクセル値を、その近傍４個の元画像ピクセルからの距離の比率で以下の式により演算することで行われる。
【００８３】
ｆ（Ｘ，Ｙ）＝（１−ｑ）・｛（１−ｐ）・ｆ（ｘ，ｙ）＋ｐ・ｆ（ｘ＋１，ｙ）｝
＋ｑ・｛（１−ｐ）・ｆ（ｘ，ｙ＋１）＋ｐ・ｆ（ｘ＋１，ｙ＋１）｝
・・・（１０）
【００８４】
上記式において、（Ｘ，Ｙ）はリサンプル画像のピクセル、（ｘ，ｙ），（ｘ＋１，ｙ），（ｘ，ｙ＋１），（ｘ＋１，ｙ＋１）は、リサンプル画像（Ｘ，Ｙ）近傍の元画像ピクセル、ｆ（ａ，ｂ）は座標（ａ，ｂ）のピクセル値、ｐ，ｑは、図１２に示されるように、近傍ピクセルからリサンプル画像（Ｘ，Ｙ）へのｘ座標方向とｙ座標方向の距離比である。
【００８５】
こうして、次元縮退されたベクトルのｘ，ｙ各成分を特徴ベクトルの各次元にあてることで、タイプ２の特徴量が得られる。線形補間リサンプルにより、３×３ベクトル群にリサンプルした場合には、１８（＝３×３×２）次元の特徴量となる。
【００８６】
なお、リサンプル後の目標の画像サイズが元画像サイズの半分以下の場合には、元画像を0.5倍づつ縮小していき、目標サイズより大きい最小の0.5倍乗数サイズの画像が得られたら、その画像から式（１０）のリサンプリングを行うことでリサンプリング時の誤差を小さくすることが可能である。例えば元画像の0.2倍サイズの画像を線形補間リサンプリングで作る場合には、0.5倍リサンプルを２回かけて得られる元画像の0.25倍サイズ画像に式（１０）の線形補間リサンプリングを行う。
【００８７】
ステップＳ２６において、特徴量抽出部２３は、全特徴点を処理したかを判定し、まだ処理していない特徴点が存在する場合には、処理をステップＳ１７に戻し、それ以降の処理を繰り返し実行する。ステップＳ２６において、全特徴点を処理したと判定された場合（ステップＳ１７乃至ステップＳ２５の処理が、全ての特徴点について行われた場合）、ステップＳ２７において、特徴点抽出部２２は、全解像度画像を処理したかを判定する。まだ処理していない解像度画像が存在する場合には、処理はステップＳ１３に戻り、それ以降の処理が繰り返し実行される。ステップＳ１３乃至ステップＳ２５の処理が、全ての解像度画像について行われたと判定された場合、ステップＳ２８において、多重解像度生成部２１は、全モデルを処理したかを判定する。まだ処理していないモデルが存在する場合には、処理はステップＳ１１に戻り、それ以降の処理が繰り返し実行される。ステップＳ１１乃至ステップＳ２５の処理が、全てのモデルについて実行されたと判定された場合、処理はステップＳ２９に進む。
【００８８】
モデル辞書登録部２４は、ステップＳ２９において、以上のように抽出された特徴点特徴量をラベル付けし、登録する。この場合、どのモデルの多重解像度画像群の、どの画像の、どのスケールから抽出された、どの特徴点の特徴量なのか、が参照できるようにラベル付けされ、モデル辞書に登録される。
【００８９】
以上のようにして、モデル辞書登録部２４には、認識させたい対象物体としてのモデル画像が特徴量として予め登録される。
【００９０】
学習部１１と認識部１２の両方を画像処理装置１が有する場合には、認識部１２は、このモデル辞書登録部２４をそのまま利用することが可能である。学習部１１と認識部１２が別の画像処理装置として構成される場合には、以上のようにして必要な情報が登録されたモデル辞書登録部２４が、認識部１２を有する画像処理装置に搭載されるか、或いは無線通信により利用可能とされる。
【００９１】
次に、認識部１２における入力画像の物体認識時の処理について、図１３乃至図１５のフローチャートを参照して説明する。
【００９２】
多重解像度生成部３１、特徴点抽出部３２、および特徴量抽出部３３は、ステップＳ１３１乃至Ｓ１４７において、入力されたオブジェクト画像に対して、ステップＳ１１乃至Ｓ２７における学習部１１の多重解像度生成部２１、特徴点抽出部２２、および特徴量抽出部２３と同様の処理を行う。その説明は繰り返しになるので省略する。但し、パラメータＮとαで決まる多重解像度画像の構成が、認識時では学習時と異なっている。
【００９３】
多重解像度生成部２１は、学習時の多重解像度画像を広い倍率レンジで細かい精度で生成するのに対し、多重解像度生成部３１は、認識時において、粗い精度で多重解像度画像を生成する。具体的に、本実施の形態で適用しているパラメータは、ステップＳ１２の学習時がＮ＝１０，α＝0.1であるのに対し、ステップＳ１３２の認識時はＮ＝２，α＝0.5である。その理由は、次の通りである。
【００９４】
１）認識精度を上げるには、より多くの特徴点特徴量情報を用いて特徴量比較を行うのが望ましい。つまり、より多くの多重解像度画像から特徴点抽出するのが望ましい。
２）スケール変化のロバスト性を得るために、多重解像度画像の構成はなるべくスケールレンジを広くするのが望ましい。
３）モデル学習時にはリアルタイム性をそれほど重視しなくても良いので、モデル画像の多重解像度画像数を多くし、スケールレンジを広くして特徴点特徴量抽出し、保持することが可能である。
４）本実施の形態では、オブジェクト画像から抽出された各特徴点特徴量を、全モデルの全特徴点特徴量から構築されるkdツリーの k-Nearest Neighbor（k-NN）探索（後述する）を用いて特徴量の比較を行っているため、特徴量比較にかかる計算コストは、オブジェクト画像から抽出された特徴点数に対して比例して増加するが、モデル特徴点数に対しては、全認識対象モデルからkdツリーを構築した場合には全モデル特徴点をｎとすると、計算コストをlognのオーダー（つまりＯ(logn)）に抑えることができる。
５）また一方で、認識時はリアルタイム性が重視されるため、多重解像度画像数をなるべく減らすことで計算コストを小さくする必要が有る。
６）かといって、入力されたオブジェクト画像から多重解像度画像を生成せず、原画像のみを用いてしまうと、モデル画像の原画像のサイズよりもオブジェクト画像中の認識対象物体のサイズが大きい場合には、その物体の認識が不可能となってしまう。
【００９５】
以上の理由から、図１６に示されるように、学習時のモデル画像からは、より多くの（ｋ＝０乃至９の）多重解像度画像群をより広いレンジで生成し（Ｎ＝１０，α＝0.1）、より多くの特徴点を抽出する一方、認識時には、オブジェクト画像から、認識に最小限必要な（ｋ＝０，１の）多重解像度画像群を生成し（Ｎ＝２，α＝0.5）、それから特徴点を抽出し、特徴量比較をkdツリー上でk-NN探索を適用することで行い、計算コストを少なくかつ精度の良い認識を実現することを可能とする。図１６には、原画像は大き過ぎて対応する大きさのスケールの階層のモデル画像は存在しないが、原画像（ｋ＝０）を0.5倍に縮小する（ｋ＝１）ことで、対応する大きさのスケールの階層のモデル画像が見い出されるようになることが示されている。
【００９６】
ステップＳ１３１乃至ステップＳ１４５の処理が、全特徴点並びに全解像度画像について行われた場合、処理はステップＳ１４８に進む。
【００９７】
後述するように、オブジェクト画像から抽出された各特徴点特徴量（次元縮退された濃度勾配ベクトル群）は、登録されている認識対象モデルの各特徴点特徴量と比較され、類似するモデル特徴点特徴量と候補対応特徴点組として組み合わされる。最も単純な特徴量比較方法は全探索である。つまり、オブジェクト画像の各特徴点特徴量に対して、全認識対象モデルの全特徴点特徴量との特徴量間類似度の計算を行い、その類似度により対応特徴点組を選択するのが最も単純な方法である。しかし、全探索による方法は、計算コスト的に実用的でない。そこで本発明の実施の形態では、大量のデータ群からデータを高速に探索するために、kdツリーというデータ構造を用いたツリー探索手法（J. H. Friedman, J. L. Bentley, R. A. Finkel, “An algorithm for finding best matches in logarithmic expected time,” ACM Transactions on Mathematical Software, Vol. 3, No. 3, pp. 209-226, September 1977.）が用いられる。Kdツリーは、ｋ次元の木構造の意味である。
【００９８】
kdツリー構築部３４は、これまでの学習過程でモデル辞書中に登録されたモデルのうち一部のモデルに関して認識させれば良い場合には、ステップＳ１４８において、認識対象となるモデルについてのみ、その全特徴点特徴量からkdツリーを構築する。本実施の形態の場合は、タイプ１の特徴量の36ｄツリー（ｋ＝３６）とタイプ２の特徴量の18ｄツリー（ｋ＝１８）が、それぞれ構築される。ツリーの各リーフ（終端ノード）には、１つの特徴点特徴量が、その特徴量がどのモデルの多重解像度画像群の、どの画像の、どのスケールから抽出された、どの特徴点の特徴量なのか、が参照できるようなラベルとともに保持される。
【００９９】
一方、モデル辞書に登録された全モデルを認識させる場合には、モデルの追加学習の度にツリーを構築し直し、ツリー自体がモデル辞書に登録される。この場合には、ステップＳ１４８におけるkdツリーの構築処理は省略される。
【０１００】
特徴量比較部３５は、ステップＳ１４９で、オブジェクト画像の未処理特徴点を選択する。そして、ステップＳ１５０において、特徴量比較部３５は、オブジェクト画像のタイプ１の特徴点特徴量と、類似するｋ個のモデルの特徴点特徴量をペア組みする。同様に、ステップＳ１５１で、特徴量比較部３５は、オブジェクト画像のタイプ２の特徴点特徴量と、類似するｋ個のモデルの特徴点特徴量をペア組みする。すなわち、特徴点抽出部３２と特徴量抽出部３３により抽出されたオブジェクト画像の各特徴点特徴量は、特徴量比較部３５により、k-NN探索により特徴量が類似するｋ個（図１７の例の場合、４個）のモデル特徴点特徴量とペア組みされる（k-NN探索のｋの値と、kdツリーのｋの値は、同じｋの文字を使用してはいるが、任意の別の値とし得る（もちろん、同じ値としてもよい））。本実施の形態では、タイプ１の特徴量のk-NN探索に用いる非類似度として、式（１１）のユークリッド距離（その値が大きい程、類似していないことを表す）が、タイプ２の特徴量の類似度として、式（１２）に示すコサイン相関値（その値が大きい程、類似していることを表す）が、それぞれ用られる。
【０１０１】
【数５】
【０１０２】
但し、式（１１）において、ｕV，ｖVは非類似度を計算する対象の特徴量ベクトル、ｕn，ｖnはそれぞれｕV，ｖVのｎ次元における値、ＮはｕV，ｖVベクトルの次元数を、それぞれ表わす。
【０１０３】
式（１２）において、ｕV，ｖVは類似度を計算する対象の特徴量ベクトルであり、ｕV・ｖVはベクトルの内積を表す。特徴量が類似するｋ個のペア（組）を抽出する際に、非類似度（タイプ１特徴量に対して）、類似度（タイプ２特徴量に対して）に対する閾値判定を入れてもよい。タイプ２の特徴量に対する類似度計算尺度にコサイン相関値を用いる理由は、明度変化による局所濃度勾配ベクトルの強度の変化に特徴量が影響されないようにするためである。また、コサイン相関値による類似度のかわりに、ｕV，ｖVをベクトル長を１で正規化し、それらのユークリッド距離を非類似度としてタイプ２の特徴量としてもよい。この場合も明度変化による局所濃度勾配ベクトルの強度の変化に特徴量が影響されないようになる。
【０１０４】
特徴量比較部３５は、ステップＳ１４９乃至ステップＳ１５１の処理を、各オブジェクト画像の特徴点に対して実行する。そして、ステップＳ１５２において、特徴量比較部３５は、全特徴点を処理したかを判定し、まだ処理していない特徴点が存在する場合には、処理をステップＳ１４９に戻し、それ以降の処理を繰り返し実行する。ステップＳ１５２において、全特徴点を処理したと判定された場合には、処理はステップＳ１５３に進む。
【０１０５】
タイプ１とタイプ２の２つのタイプの特徴量を用いるので、特徴量比較部３５は、入力されたオブジェクト画像の特徴点に対する特徴点ペアを特徴量タイプごとに上述の方法で求めた後、ステップＳ１５３で、タイプ１とタイプ２の両方で共通して抽出された特徴点ペアのみを候補対応特徴点組として選択し、モデル毎に分類する。そして、この候補対応特徴点組は、後段のモデル姿勢推定部３６に供給される。モデル姿勢推定部３６では、モデルごとの処理を行うため、抽出された候補対応特徴点組をモデルごとに分類して渡すことで、処理の効率化を図ることができる。
【０１０６】
図１７は、以上の処理を模式的に表している。kdツリー構築部３４により、タイプ１の特徴量の36ｄツリー構造と、タイプ２の特徴量の18ｄツリー構造が生成される。オブジェクト画像の特徴量群から、k-NN探索（いまの場合、ｋ＝４）によりタイプ１の特徴量の36ｄツリー構造からタイプ１の特徴量の４個の類似ペア群が探索される。この例においては、オブジェクト画像の四角形で表されている特徴点特徴量（図中の四角形、五角形、三角形、円、または十字の図形は特徴点特徴量を表す）が、タイプ１の特徴量の36ｄツリー構造の五角形、三角形、円、または十字と類似するとして探索される。また、タイプ２の特徴量の18ｄツリー構造からk-NN探索によりタイプ２の特徴量の４個の類似ペア群が探索される。この例では、オブジェクト画像の四角形が、タイプ２の特徴量の18dツリー構造の平行四辺形、十字、円、またはひし形と類似するとして探索されている。
【０１０７】
タイプ１の特徴量の４個の類似ペア群と、タイプ２の特徴量の４個の類似ペア群の中から、共通する類似ペア群が選択される。この例の場合、タイプ１の特徴量の類似ペア群は、四角形と五角形、四角形と三角形、四角形と円、四角形と十字の４個である。これに対して、タイプ２の特徴量の類似ペア群は、四角形と平行四辺形、四角形と十字、四角形と円、四角形とひし形の４個である。したがって、四角形と円、並びに四角形と十字の類似ペア群が、２つのタイプに共通する特徴点ペアであるので、それが候補対応特徴点ペア（組）として、選択される。
【０１０８】
なお、以上に説明したように、特徴量タイプ毎、認識対象の全モデルの全特徴点特徴量から１つのkdツリーを構築し、入力画像の各特徴点特徴量のk-NNを探索するのではなく、特徴量タイプ毎、モデル毎にkdツリーを構築し、モデル毎に入力画像各特徴点特徴量のk-NNを探索するようにしてもよい。いずれの場合でも、出力はモデル毎に分類された候補対応特徴点組群であり、後述する後段の処理は共通となる。
【０１０９】
以上の処理により、特徴点近傍の局所的な濃度勾配情報が類似するペア群（モデル特徴点とオブジェクト特徴点のペア群）を抽出することができるが、巨視的に見ると、このように得られたペア群は、対応特徴点間の空間的位置関係がモデルのオブジェクト画像（入力画像）上での姿勢（モデル姿勢）と矛盾しない「真の特徴点ペア（インライヤ）」だけでなく、矛盾するような「偽の特徴点ペア（アウトライヤ）」を含んでいる。
【０１１０】
図１８は、インライヤとアウトライヤを模式的に表している。同図に示されるように、図中左側に示される三角形のモデル画像と、図中右側に示されるオブジェクト画像の三角形の検出対象物体（オブジェクト）が対応するとすると、モデル画像の三角形の頂点近傍の特徴点Ｐ１乃至Ｐ４は、検出対象物体の特徴点Ｐ11乃至Ｐ14とそれぞれ対応する。すなわち、特徴点Ｐ１が特徴点Ｐ11と、特徴点Ｐ２が特徴点Ｐ12と、特徴点Ｐ３が特徴点Ｐ13と、特徴点Ｐ４が特徴点Ｐ14とそれぞれ対応する。したがって、これらの候補対応特徴点組はインライヤを構成する。なお、図１８において、インライヤは実線で示されている。
【０１１１】
これに対して、モデル画像の特徴点Ｐ５は三角形の内部のほぼ中央に位置し、特徴点Ｐ６は三角形の周辺の近傍の外部に位置する。これに対して、特徴点Ｐ５とペア組されたオブジェクト画像の特徴点Ｐ15と、特徴点Ｐ６とペア組されたオブジェクト画像の特徴点Ｐ16は、それぞれ、検出対象物体とは遠く離れた点である。すなわち、特徴点Ｐ５と特徴点Ｐ15の候補対応特徴点組、並びに特徴点Ｐ６と特徴点Ｐ16の候補対応特徴点組はアウトライヤである。なお、図１８において、アウトライヤは破線で示されている。
【０１１２】
候補対応特徴点組群からモデル画像の入力画像中の位置姿勢を決める画像変換パラメータを導出する方法として、最小自乗推定により推定画像変換パラメータを求める手法が考えられる。結果の推定モデル姿勢と空間的位置関係の矛盾する対応ペアを排除し、残ったペアで再び最小自乗推定による推定画像変換パラメータ導出を行うという処理を繰り返すことで、より精度の良いモデル姿勢を求めることができる。
【０１１３】
しかしながら、候補対応特徴点組群中のアウトライヤの数が多い場合や、真の画像変換パラメータから極端に逸脱したアウトライヤが存在する場合には、上記最小自乗推定による推定結果は一般的に満足のいくものではないことが知られている（Hartley R., Zisserman A.,“Multiple View Geometry in Computer Vision.”, Chapter 3, pp.69-116, Cambridge University Press, 2000）。そこで、本実施の形態におけるモデル姿勢推定部３６は、ある画像変換の拘束の下、候補対応特徴点組群の空間的位置関係から「真の特徴点ペア（インライヤ）」を抽出し、抽出されたインライヤを用いてモデルの位置姿勢を決める画像変換パラメータを推定する。
【０１１４】
このモデル姿勢推定部３６によるモデル姿勢推定処理は、認識対象モデルごとに行われ、モデルごとにその有無、有る場合には姿勢の推定が行われる。以下の説明で出てくる候補対応特徴点組は、特徴量比較部３５の出力である候補対応特徴点組のうち、当該モデルに関するペアのみをまとめたペア群を意味する。
【０１１５】
画像変換としてはユークリッド変換、相似変換、アフィン変換、射影変換などが挙げられるが、本実施の形態においては、アフィン変換の拘束の下、姿勢推定を行う場合について詳細説明を行う。アフィン変換は、平行移動及び回転変換（ユークリッド変換）に拡大縮小変換を加えた相似変換に、せん断変形を許すような変換で、元の図形で直線上に並ぶ点は変換後も直線上に並び、平行線は変換後も平行線であるなど、幾何学的性質が保たれる変換である。アフィン変換パラメータを決定するためには候補対応特徴点組が３組以上必要となる。
【０１１６】
上述したように、候補対応特徴点組が３組以上なければ、アフィン変換パラメータを決定できない。そこで、モデル姿勢推定部３６は、ステップＳ１５４で１つの未処理モデルを選択した後、ステップＳ１５５で候補対応特徴点ペア（組）が３組以上あるかを判定する。候補対応特徴点組が２組以下の場合、モデル姿勢推定部３６は、ステップＳ１５６で、オブジェクト画像（入力画像）中にモデルが存在しない、又はモデル姿勢検出に失敗したとして、「認識不可」を出力する。一方、候補対応特徴点組が３組以上ある場合、モデル姿勢推定部３６は、モデル姿勢を検出可能であるので、アフィン変換パラメータの推定を行う。このため、モデル姿勢推定部３６は、ステップＳ１５７で座標変換を行う。すなわち、候補対応特徴点組のモデル特徴点位置座標が、モデル原画像上の位置座標に変換されるとともに、オブジェクト画像特徴点位置座標が、オブジェクト原画像の位置座標に変換される。そして、ステップＳ１５８で、モデル姿勢推定部３６は、姿勢推定処理を行う。
【０１１７】
ここで、アフィン変換パラメータについて説明する。モデル特徴点［ｘ ｙ］Tのオブジェクト特徴点［ｕ ｖ］Tへのアフィン変換は、以下の式（１３）で与えられる。
【０１１８】
【数６】
【０１１９】
この式（１３）において、ａi（ｉ＝１，…，４）は回転、拡大縮小、せん断変形を決定するパラメータを表し、［ｂ1 ｂ2］Tは、平行移動パラメータを表す。決定すべきアフィン変換パラメータはａ1，…，ａ4及びｂ1，ｂ2の６つであるため、候補対応特徴点組が３組あれば、アフィン変換パラメータを決定することができる。
【０１２０】
３組の候補対応特徴点組で構成されるペア群Ｐを、（[ｘ1 ｙ1]T，[ｕ1 ｖ1]T），（[ｘ2 ｙ2]T，[ｕ2 ｖ2]T），（[ｘ3 ｙ3]T，[ｕ3 ｖ3]T）とすると、ペア群Ｐとアフィン変換パラメータとの関係は、以下の式（１４）に示す線形システムで表現することができる。
【０１２１】
【数７】
【０１２２】
この式（１４）を、ＡｘV＝ｂVのように書き直すと（下付のＶは、添えられている文字（例えばｘVのｘ）がベクトルであることを表わす。以下、同様である）、アフィン変換パラメータｘVの最小自乗解は、以下の式（１５）で与えられる。
【０１２３】
ｘV＝Ａ-1ｂV ・・・（１５）
【０１２４】
候補対応特徴点組群から、アウトライヤが１つ以上混入するように、ランダムにペア群Ｐを繰り返し選択した場合、そのアフィン変換パラメータは、パラメータ空間上に散らばって投射される。一方、インライヤのみから構成されるペア群Ｐをランダムに繰り返し選択した場合、そのアフィン変換パラメータは、何れもモデル姿勢の真のアフィン変換パラメータに極めて類似した、すなわちパラメータ空間上で距離の近いものとなる。したがって、候補対応特徴点組群から、ランダムにペア群Ｐを選択し、そのアフィン変換パラメータをパラメータ空間上に投射していく処理を繰り返すと、インライヤはパラメータ空間上で密度の高い（メンバ数の多い）クラスタを形成し、アウトライヤは散らばって出現することになる。すなわち、パラメータ空間上でクラスタリングを行えば、最多メンバ数を持つクラスタの要素がインライヤとなる。
【０１２５】
モデル姿勢推定部３６における姿勢推定処理の詳細を図１９のフローチャートを用いて説明する。なお、このモデル姿勢推定部３６におけるクラスタリング手法としては、NN（Nearest Neighbor）法が用いられる。この際、上述したパラメータｂ1，ｂ2は、認識対象画像により様々な値を取り得るため、ｘ空間でもクラスタリングにおいてクラスタリング閾値の選択が認識対象に依存してしまう。そこで、モデル姿勢推定部３６では、「真のパラメータとａ1，…，ａ4は類似するが、ｂ1，ｂ2が異なるようなアフィン変換パラメータを与えるペア群Ｐは、殆ど存在しない」という仮定の下、パラメータａ1，…，ａ4（以下、ａVと表記する）で規定されるパラメータ空間上のみでクラスタリングを行う。なお、上記仮定が成り立たない状況が生じたとしても、ａV空間とは独立に、パラメータｂ1，ｂ2で規定されるパラメータ空間でクラスタリングを行い、その結果を考慮することで、容易に問題を回避することができる。
【０１２６】
先ず、ステップＳ２０１において、モデル姿勢推定部３６は初期化を行う。具体的には、繰り返し数を表す変数としてのカウント値cntがcnt＝１とされ、候補対応特徴点組群からランダムに３組のペアをペア群Ｐ1として選択し、アフィン変換パラメータａV1が求められる。また、モデル姿勢推定部３６は、クラスタ数を表す変数ＮをＮ＝１とし、アフィン変換パラメータ空間ａV上でａV1を中心とするクラスタＺ1を作る。モデル姿勢推定部３６は、このクラスタＺ1のセントロイドｃV1をｃV1＝ａV1とし、クラスタのメンバ数を表す変数ｎz1をｎz1＝１とし、カウンタ値cntをcnt＝２に更新する。
【０１２７】
次に、ステップＳ２０２において、モデル姿勢推定部３６は、候補対応特徴点組群からランダムに３組のペアをペア群Ｐcntとして選択し、アフィン変換パラメータａVcntを計算する。そして、モデル姿勢推定部３６は、計算されたアフィン変換パラメータａVcntをパラメータ空間に投射する。
【０１２８】
次に、ステップＳ２０３において、モデル姿勢推定部３６は、NN法によりアフィン変換パラメータ空間をクラスタリングする。具体的には、モデル姿勢推定部３６は、先ず以下の式（１６）に従って、アフィン変換パラメータａVcntと各クラスタＺiのセントロイドｃVi（ｉ＝１，…，Ｎ）との距離ｄ（ａVcnt, ｃVi）のうち、最小の距離ｄminを求める。
【０１２９】
ｄmin = ｍｉｎ 1≦i≦N ｛ ｄ(ａVcnt, ｃVi) ｝ ・・・（１６）
【０１３０】
そして、モデル姿勢推定部３６は、所定の閾値τ（例えばτ＝0.1）に対してｄmin＜τであればｄminを与えるクラスタＺiにａVcntを属させ、ａVcntを含めた全メンバでクラスタＺiのセントロイドｃiを更新する。また、クラスタＺiのメンバ数ｎziはｎzi＝ｎzi＋１とされる。一方、ｄmin≧τであれば、モデル姿勢推定部３６は、アフィン変換パラメータ空間ａV上でａVcntをセントロイドｃVN+1とする新しいクラスタＺN+1を作り、そのクラスタのメンバ数ｎzN+1をｎzN+1＝１とし、クラスタ数ＮをＮ＝Ｎ＋１とする。
【０１３１】
続いて、ステップＳ２０４で、モデル姿勢推定部３６は、繰り返し終了条件を満たすか否かを判別する。繰り返し終了条件は、例えば最多メンバ数が所定の閾値（例えば１５）を超え、且つ最多メンバ数と２番目に多いメンバ数との差が所定の閾値（例えば３）を超える場合、或いは繰り返し数カウンタのカウント値cntが、所定の閾値（例えば5000回）を超える場合のように設定することができる。ステップＳ２０４において、繰り返し終了条件が満たされないと判定された場合（Noと判定された場合）には、モデル姿勢推定部３６は、ステップＳ２０５で繰り返し数のカウント値cntをcnt＝cnt＋１とした後、処理をステップＳ２０２に戻し、それ以降の処理を繰り返す。
【０１３２】
一方、ステップＳ２０４で、繰り返し終了条件を満たすと判定された場合（Yesと判定された場合）には、ステップＳ２０６において、モデル姿勢推定部３６は、以上の処理で得られたインライヤが３ペアに満たない場合には、アフィン変換パラメータが決定できないため、認識結果を「認識対象モデル非検出」と出力し、インライヤが３ペア以上抽出された場合には、インライヤに基づいて、最小自乗法によりモデル姿勢を決定するアフィン変換パラメータを推定し、認識結果として出力する。
【０１３３】
インライヤを（[ｘIN1 ｙIN1]T，[ｕIN1 ｖIN1]T），（[ｘIN2 ｙIN2]T，[ｕIN2 ｖIN2]T），…とすると、インライヤとアフィン変換パラメータとの関係は、以下の式（１７）に示す線形システムで表現することができる。
【０１３４】
【数８】
【０１３５】
この式（１７）を、ＡINｘVIN＝ｂVINのように書き直すと、アフィン変換パラメータｘVINの最小自乗解は以下の式（１８）で与えられる。
【０１３６】
ｘVIN ＝ (ＡINT ＡIN) 1 ＡINTｂVIN ・・・（１８）
【０１３７】
ステップＳ２０６で、モデル姿勢推定部３６は、このアフィン変換パラメータｘVINで決定されるモデル姿勢をモデル認識結果として出力する。
【０１３８】
図１５に戻り、ステップＳ１５８またはステップＳ１５６の処理の後、ステップＳ１５９において、モデル姿勢推定部３６は、全モデルを処理したかを判定する。まだ処理していないモデルが存在する場合には、処理はステップＳ１５４に戻り、それ以降の処理が繰り返し実行される。ステップＳ１５９において、全てのモデルについて処理したと判定された場合、処理は終了される。
【０１３９】
以上の図１５のステップＳ１５４乃至Ｓ１５９の処理は、認識対象モデルごとに行なわれる。この処理が、図２０に模式的に示されている。この例においては、候補対応特徴点組群ｐ１乃至ｐ６から最初にランダムに３個の候補対応特徴点組群ｐ１,ｐ３,ｐ４が選択され、それに基づき計算されたアフィンパラメータがパラメータ空間に投射される。次に、ランダムに３個の候補対応特徴点組群ｐ３,ｐ４,ｐ６が選択され、それらに基づき、計算されたアフィンパラメータがパラメータ空間に投射される。同様の処理がさらに繰り返され、この例においては、３個の候補対応特徴点組群ｐ５,ｐ４,ｐ１が選択され、それに基づきアフィンパラメータが計算され、パラメータ空間に投射される。そして、パラメータ空間上において、近接するアフィンパラメータが、クラスタリングされ、そのクラスタリングされたアフィン変換パラメータに最小自乗法を適用することで、モデル姿勢が決定される。
【０１４０】
上記の手法を用いることにより、アウトライヤが候補対応特徴点組群中に多数含まれてしまっている場合でも、アウトライヤを排除し、高精度に姿勢推定（変換パラメータ導出）が可能となる。
【０１４１】
以上の実施の形態では、アフィン変換拘束の下での姿勢推定の詳細を述べた。アフィン変換拘束の下では、平面領域が支配的な、例えば箱や本などの３次元物体であれば、その支配平面についての視点変化に対してロバストな姿勢推定が可能となる。しかし、曲面や凹凸が支配的な３次元物体のロバストな姿勢推定を行うには、アフィン変換拘束を投影変換拘束に拡張する必要がある。ただし、この場合においても、推定すべき変換パラメータの次元が増えるだけで、上記手法を簡単に拡張することが可能である。
【０１４２】
このようにして、決定されたモデル姿勢は、例えば、図１６や図１８において破線で示されている。これらの図に示されるように、本実施の形態においては、単にモデル画像に対応する検出対象物体の存在の有無が検出されるだけでなく、その検出対象物体が存在する場合には、その姿勢までも推定され、出力される。
【０１４３】
なお、モデル姿勢推定部３６が推定するこのモデル姿勢は、オブジェクト画像の検出対象物体に対する相対的な姿勢を意味するから、モデル姿勢を基準の姿勢として考えた場合には、モデル姿勢推定部３６は、モデル画像に対する検出対象物体の姿勢を推定することを意味する。
【０１４４】
なお、以上の説明では、閾値τが定数値であるものとしたが、ステップＳ２０３乃至ステップＳ２０６の繰り返し処理を行う際に、始めは比較的大きな閾値τを用いて大雑把なインライヤ抽出を行い、繰り返し回数が増える毎に次第に小さい閾値τを用いる、いわゆる「焼きなまし法」のような手法を適用してもよい。これにより、精度よくインライヤを抽出することができる。
【０１４５】
また、以上の説明では、候補対応特徴点組群からランダムにペア群Ｐを選択し、そのアフィン変換パラメータをパラメータ空間上に投射していく処理を繰り返し、パラメータ空間上で最多メンバ数を持つクラスタの要素をインライヤとして、最小自乗法によりモデル姿勢を決定するアフィン変換パラメータを推定したが、これに限定されるものではなく、例えば最多メンバ数を持つクラスタのセントロイドを、モデル姿勢を決定するアフィン変換パラメータとしても構わない。さらに、組は３個以上の特徴点で構成してもよい。
【０１４６】
以上、オブジェクト画像の物体認識時において、多重解像度生成部３１、特徴点抽出部３２、特徴量抽出部３３、特徴量比較部３５、およびモデル姿勢推定部３６が、オブジェクト画像が更新される毎にそれを逐次処理するので、リアルタイムでの物体認識が可能になる。また、モデル毎に特徴量比較部３５により抽出された特徴点ペアは、モデル毎分類されモデル姿勢推定部３６においてモデル毎に姿勢推定が行われるので、入力画像中に複数のモデル物体が含まれているような画像でもモデル物体の認識が可能となる。
【０１４７】
ところで、特徴量比較部３５で生成された候補対応特徴点ペア群中のアウトライヤの比率が大きくなるほどモデル姿勢推定部３６におけるインライヤの選択確率が低下し、モデル姿勢を推定する際に多くの繰り返し回数が必要となるため、計算時間が増大する。したがって、このモデル姿勢推定部３６に入力される候補対応特徴点ペア群から、できる限りアウトライヤを排除しておくことが望ましい。そこで、本実施の形態における画像処理装置１では、図２１に示されるように、特徴量比較部３５とモデル姿勢推定部３６との間に、対応特徴点ペアの絞込みを行う対応特徴点ペア絞込み部６１を挿入することができる。この対応特徴点ペア絞込み部６１では、モデル姿勢推定部３６のモデル姿勢推定処理で仮定した画像変換拘束よりもパラメータ次元の少ない画像変換拘束の下（例えばモデル姿勢推定部３６でアフィン変換拘束を用いた場合には、対応特徴点ペア絞込み部６１で相似変換拘束を用いる）、各モデルについて一般化ハフ変換を行うことで、粗い画像変換パラメータ推定及びそれをサポートする対応特徴点ペア群の抽出を行う。
【０１４８】
次に、図２２のフローチャートを参照して、画像変換拘束に相似変換拘束を用いた場合の対応特徴点ペア絞込み部６１による候補対応特徴点ペアの絞込み処理について説明する。相似変換は平行移動（２次元画像上なのでＸ軸方向の変位dXとＹ軸方向の変位dY）及び回転変換（θ）に拡大縮小変換（scl）を加えた変換である。
【０１４９】
ステップＳ３０１において、対応特徴点ペア絞込み部６１は、上記相似変換パラメータdX，dY，θ,sclで規定される４次元パラメータ空間の各軸について、レンジを規定し、そのレンジ内で規定したステップ幅でビンを切ることで、一般化ハフ変換の投票空間を作る。例えば、dX軸、dY軸に関してレンジを±200、ステップ幅を20（単位はピクセル）、θ軸に関してレンジを０から360、ステップ幅を15（単位は度）、scl軸に関してレンジを0.4から1.6、ステップ幅を0.3（単位は拡大縮小率）とすると、20 × 24 × 5 = 2400個の投票ビンができる。
【０１５０】
ステップＳ３０２以降は、モデル毎の処理になる。対応特徴点ぺア絞込み部６１は、ステップＳ３０２において投票空間を初期化し、未処理モデルを選択する。すなわち、例えば各投票ビンの値が０に設定され、１つのモデルが選択される。
【０１５１】
ステップＳ３０３乃至ステップＳ３０９は当該モデルの候補対応特徴点ペア（組）毎の処理となるので、ステップＳ３０３において対応特徴点ぺア絞込み部６１は、未処理候補対応特徴点ペアを選択する。すなわち、１つの未処理候補対応特徴点ペアが処理対象として選択される。
【０１５２】
続いて、ステップＳ３０４において、対応特徴点ぺア絞込み部６１は、回転変換角度θを求める。例えば、図２３Ａに示されるように、モデル画像の特徴点Ｐのカノニカル方向がＤPであり、特徴点Ｐとペア（組）となるオブジェクト画像の特徴点Ｑのカノニカル方向が図２３Ｂに示されるように、ＤQである場合、図２４に示されるように、特徴点Ｐと特徴点Ｑを、対応する位置に配置させた場合に得られるカノニカル方向ＤQとＤPの差が回転変換角度θとなる。
【０１５３】
ステップＳ３０５乃至ステップＳ３０９はscl軸で規定したビンの代表scl値（上記例の場合、scl軸で切られた５ビンの代表scl値はそれぞれ0.4, 0.7, 1.0, 1.3, 1.6となる）それぞれに関して行われる処理となる。そこで、対応特徴点ぺア絞込み部６１は、まず、ステップＳ３０５において、未処理scl値を選択する。すなわち、１つの未処理scl値が選択される。
【０１５４】
次に、ステップＳ３０６において、対応特徴点ペア絞込み部６１は、図２５に示されるように、モデル画像を当該scl値で拡大あるいは縮小した場合の平行移動変換量dX，dYを求める。この平行移動変換量dX，dYはステップＳ３０４で求めた回転変換角度θ、オブジェクト画像上の当該特徴点Ｑの座標Xi，Yi、モデル画像上の当該特徴点Ｐの極座標における原点からの距離γと軸からの角度αにより、以下の式（１９）と式（２０）により導出できる。
【０１５５】
ｄＸ＝Ｘｉ−ｓｃｌ・γ・ｃｏｓ（α＋θ） ・・・（１９）
ｄＹ＝Ｙｉ−ｓｃｌ・γ・ｓｉｎ（α＋θ） ・・・（２０）
【０１５６】
相似変換を決定する４つのパラメータ（scl，θ，dX，dY）が求まったので、ステップＳ３０７において、対応特徴点ペア絞込み部６１は、そのパラメータを投票空間上に投票する。具体的には、パラメータが投票空間の該当するビンに投票される。
【０１５７】
対応特徴点ペア絞込み部６１は、ステップＳ３０８、Ｓ３０９の分岐処理に従い、以上のステップＳ３０３からの処理を当該モデルに関する全対応特徴点ペア、全scl値に関して行う。すなわち、ステップＳ３０８において、対応特徴点ペア絞込み部６１は、全scl値について処理したかを判定し、まだ処理していないscl値が存在する場合には、処理をステップＳ３０５に戻し、それ以降の処理を繰り返す。そしてステップＳ３０８において、全scl値について処理したと判定された場合、ステップＳ３０９において、対応特徴点ペア絞込み部６１は、全対応特徴点ペアを処理したかを判定し、まだ処理していない対応特徴点ペアが存在する場合には処理をステップＳ３０３に戻し、それ以降の処理を繰り返す。
【０１５８】
ステップＳ３０９で全対応特徴点ペアを処理したと判定された場合、ステップＳ３１０で、対応特徴点ペア絞込み部６１は、最多得票ビン及びその得票数を求める。すなわち、ステップＳ３０７の処理による投票の結果、最も得票数の多かったビンとその得票数が求められる。ステップＳ３１１で、対応特徴点ペア絞込み部６１は、ステップＳ３１０で求められた最大得票数が閾値以上かを判定する。この閾値は予め設定されている。最大得票数が閾値以上である場合には、ステップＳ３１２において、対応特徴点ペア絞込み部６１は、モデル有りと判定し、最多得票ビンに投票された候補対応特徴点ペアを出力する。すなわち、最多投票ビンの示す相似変換パラメータが、そのモデルのオブジェクト画像上での相似変換拘束の下での推定モデル姿勢となり、最多投票ビンに投票された候補対応特徴点ペア群が、相似変換拘束の下での推定モデル姿勢をサポートするインライヤ（極少数のアウトライヤを含む可能性もある）となる。ステップＳ３１１において、最大得票数が閾値以上ではないと判断された場合、ステップＳ３１３において、対応特徴点ペア絞込み部６１は、モデル無しと判定する。すなわち、オブジェクト画像中に存在しないモデルに対しては、得票にばらつきが生じるため、各モデルの一般化ハフ変換の結果に対して最大得票数が閾値以下となる。この場合には、モデルが検出されなかったと判定される。
【０１５９】
以上、ステップＳ３０２乃至ステップＳ３１３の処理はステップＳ３１４の分岐処理に従い全ての認識対象モデルに関して行われる。すなわち、ステップＳ３１２またはステップＳ３１３の処理の後、ステップＳ３１４において、対応特徴点ペア絞込み部６１は、全モデルを処理したかを判定する。まだ処理していないモデルが存在する場合には、処理はステップＳ３０２に戻り、それ以降の処理が繰り返し実行される。ステップＳ３１４において、全モデルを処理したと判定された場合には、候補対応特徴点ペアの絞込み処理は終了される。
【０１６０】
ステップＳ３１２で、モデル有りの判定がされたモデルについては、そのモデルに対するインライヤがモデル姿勢推定部３６に供給され、前述の手法によりさらに厳密なモデルの姿勢推定が行われる。
【０１６１】
以上詳述した対応特徴量ペア絞込み部６１による処理では、モデル姿勢推定部３６のモデル姿勢推定処理で仮定した画像変換拘束よりもパラメータ次元の少ない画像変換拘束の下で粗い画像変換パラメータ推定を行うことにより、高速に候補対応特徴点ペア絞込みを行うことができる。絞り込まれた特徴点ペアを用いてモデル姿勢推定部３６で画像変換パラメータの推定を行うことで、モデル姿勢推定部３６の前段に対応特徴点ペア絞込み部６１を挿入しない場合と比べ、より高速な画像変換パラメータの高精度推定が可能となる。対応特徴量ペア絞込み部６１による処理では、画像変換パラメータの次元を少なくしたことにより実際の変換と推定の変換との誤差が生じるが、投票空間の各ビンのサイズを、その誤差を許容できるくらい大きくとることによりその問題は解決される。
【０１６２】
以上説明したように、本実施の形態における画像処理装置１によれば、次のことが可能になる。
【０１６３】
１． 解像度画像群を構成するようにしたので、結果としてノイズが除去され、ノイズに対してもロバストな認識が可能となる。
２． 特徴点の局所領域濃度勾配のカノニカル方向を０度に正規化した特徴量を用いるようにしたので、回転変化にロバストな認識が可能となる。
３． 明度変化に影響されやすい局所領域濃度勾配の強度情報ではなく、方向情報を特徴量及びそのマッチングに用いたので、明度変化に対してロバストな認識が可能となる。
４． 全ての解像度間で特徴量間マッチングを行うようにしたので、拡大縮小変化に対してロバストな認識が可能となる。
５． 特徴点ペア抽出後、アフィン拘束及び一般化ハフ変換を用いるようにしたので、アフィン変換に対してロバストな認識が可能になる。
６． 局所特徴量間マッチングを用いるようにしたので、認識対象物体が部分的に隠されているような場合にも認識が可能となる。
７． モデル毎に特徴点ペアを抽出し、モデル毎に姿勢推定を行うようにしたので、入力画像中に複数のモデル物体が含まれているような画像でもモデル物体の認識が可能となる。
８． 学習時に、特徴点、特徴量をより広いスケールレンジでより細かいスケールサンプリングで抽出する一方で、認識時には粗いスケールレンジ、粗いスケールサンプリングで特徴点、特徴量を抽出し、特徴量比較をkdツリーによるk-NN探索法を用いることにより、認識精度を落とさずに認識計算コストを減少させることが可能となる。つまり、リアルタイムに精度よく物体の認識が可能となる。
【０１６４】
上述した一連の処理は、ハードウエアにより実行させることもできるし、ソフトウエアにより実行させることもできる。この場合、例えば、画像処理装置１は、図２６に示されるようなパーソナルコンピュータにより構成される。
【０１６５】
図２６において、CPU（Central Processing Unit）１２１は、ROM（Read Only Memory）１２２に記憶されているプログラム、または記憶部１２８からRAM（Random Access Memory）１２３にロードされたプログラムに従って各種の処理を実行する。RAM１２３にはまた、CPU１２１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１６６】
CPU１２１、ROM１２２、およびRAM１２３は、バス１２４を介して相互に接続されている。このバス１２４にはまた、入出力インタフェース１２５も接続されている。
【０１６７】
入出力インタフェース１２５には、キーボード、マウスなどよりなる入力部１２６、CRT(Cathode Ray Tube)、LCD(Liquid Crystal display)などよりなるディスプレイ、並びにスピーカなどよりなる出力部１２７、ハードディスクなどより構成される記憶部１２８、モデムなどより構成される通信部１２９が接続されている。通信部１２９は、インターネットを含むネットワークを介しての通信処理を行う。
【０１６８】
入出力インタフェース１２５にはまた、必要に応じてドライブ１３０が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア１３１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部１２８にインストールされる。
【０１６９】
一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、専用のハードウエアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、ネットワークや記録媒体からインストールされる。
【０１７０】
この記録媒体は、図２６に示されるように、装置本体とは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク（フロッピディスクを含む）、光ディスク（CD-ROM(Compact Disk-Read Only Memory),DVD(Digital Versatile Disk)を含む）、光磁気ディスク（MD（Mini-Disk）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア１３１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに提供される、プログラムが記録されているROM１２２や、記憶部１２８に含まれるハードディスクなどで構成される。
【０１７１】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１７２】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【産業上の利用可能性】
【０１７３】
本発明は、ロボット装置に適用することが可能である。
【図面の簡単な説明】
【０１７４】
【図１】本発明を適用した画像処理装置の構成例を示すブロック図である。
【図２】図１の学習部の学習処理を説明するフローチャートである。
【図３】図１の学習部の学習処理を説明するフローチャートである。
【図４】解像度画像を説明する図である。
【図５】DoGフィルタのスケールスペースを説明する図である。
【図６】特徴点近傍の濃度勾配方向を説明する図である。
【図７】ヒストグラムの度数の演算方法を説明する図である。
【図８】方向ヒストグラムの例を示す図である。
【図９】方向ヒストグラムの例を示す図である。
【図１０】方向ヒストグラムの例を示す図である。
【図１１】特徴量抽出の処理を説明する図である。
【図１２】リサンプリングの例を示す図である。
【図１３】図１の認識部の認識処理を説明するフローチャートである。
【図１４】図１の認識部の認識処理を説明するフローチャートである。
【図１５】図１の認識部の認識処理を説明するフローチャートである。
【図１６】学習時と認識時の多重解像度を説明する図である。
【図１７】特徴量の比較処理を説明する図である。
【図１８】インライヤとアウトライヤを説明する図である。
【図１９】姿勢推定処理の詳細を説明するフローチャートである。
【図２０】図１９の姿勢推定処理を説明する図である。
【図２１】本発明を適用した画像処理装置の他の構成例を示すブロック図である。
【図２２】図２１の対応特徴点ペア絞込み部の処理を説明するフローチャートである。
【図２３】モデル画像とオブジェクト画像の対応する特徴点を説明する図である。
【図２４】モデル画像とオブジェクト画像の特徴点の回転変換角度を説明する図である。
【図２５】平行移動変換量を説明する図である。
【図２６】パーソナルコンピュータの構成例を示すブロック図である。
【符号の説明】
【０１７５】
１ 画像処理装置， １１ 学習部， １２ 認識部， ２１ 多重解像度生成部， ２２ 特徴点抽出部， ２３ 特徴量抽出部， ２４ モデル辞書登録部， ３１ 多重解像度生成部， ３２ 特徴点抽出部， ３３ 特徴量抽出部， ３４ kdツリー構築部， ３５ 特徴量比較部， ３６ モデル姿勢推定部
【技術分野】
【０００１】
本発明は、画像処理装置および方法、記録媒体、並びにプログラムに関し、特に、視点変化、明度変化に強く、画像の拡大縮小に拘らず、物体を確実に認識することができるようにした画像処理装置および方法、記録媒体、並びにプログラムに関する。
【背景技術】
【０００２】
例えば、ロボットにより対象物体を認識するための実用化されている対象物体認識技術の多くは、残差逐次検定法や相互相関係数によるテンプレートマッチング手法を用いている。しかしテンプレートマッチング手法は、検出対象物体が入力画像中に変形なく出現すると仮定できる特殊な場合には有効であるが、視点や照明状態の一定でない一般的な画像からの物体認識環境においては有効でない。
【０００３】
他方、対象物体の形状特徴と、画像分割手法によって切り出された入力画像中の各領域の形状特徴とをマッチングする形状マッチング手法も提案されているが、上述のような一般的な物体認識環境においては、領域分割の結果が安定せず、入力画像中の物体の良質な形状記述が難しくなる。特に、検出対象物体が、他の物体に部分的に隠されている場合などは認識が非常に困難になる。
【０００４】
以上のような、入力画像全体あるいは領域の全体的な特徴を用いたマッチング手法に対し、画像から特徴的な点やエッジを抽出し、それらが構成する線分集合やエッジ集合の空間的位置関係を線図形やグラフとして表現し、線図形間やグラフ間の構造類似性に基づいてマッチングを行う方法も提案されている。しかし、これらの手法は、ある特化した対象物に対してはうまく作用するが、画像の変形により、時として安定した特徴点間構造が抽出されず、特に前に述べたような部分的に隠されている物体の認識は困難となる。
【０００５】
そこで、画像から特徴的な点（特徴点）を抽出し、特徴点とその局所近傍の画像情報から得られる特徴量を用いたマッチング手法が提案されている。このような特徴点の部分的画像変形に対して不変な局所特徴量を用いるマッチング手法では、前述の手法に比べ画像の変形に対しても、検出対象が部分的に隠されるような場合にも安定した検出が可能となる。拡大縮小変換に対して不変性を持つ特徴点の抽出法として、画像のスケールスペースを構築し、各スケール画像のDifference of Gaussian（DoG）フィルタ出力の局所極大点及び局所極小点のうち、スケール方向の変化によっても位置が変化しない点をスケール特徴点として抽出する方法（非特許文献１または非特許文献２）や、画像のスケールスペースを構築し、各スケール画像からHarrisコーナー検出器により抽出されたコーナー点のうち、スケールスペース画像のLaplacian of Gaussian（LoG）フィルタ出力の局所極大を与える点を特徴点として抽出する方法（非特許文献３）などが提案されている。
【０００６】
さらに、このように抽出された特徴点において、視線変化に対して不変な特徴量を選ぶことが好ましい。例えば、 Schmid & Mohr は、 Harris コーナー検出器を用いて検出されたコーナーを特徴点とし、その特徴点付近の回転不変特徴量を用いたマッチング手法を提案している（非特許文献４）。
【非特許文献１】D. Lowe, “Object recognition from local scale-invariant features,” in Proc. International Conference on Computer Vision, Vol. 2, pp. 1150-1157, September 20-25, 1999, Corfu, Greece.
【非特許文献２】D. Lowe, “Distinctive image features from scale-invariant keypoints,” accepted for publication in the International Journal of Computer Vision, 2004. K. Mikolajczyk, C. Schmid, “Indexing based on scale invariant interest points,” International Conference on Computer Vision, 525-531, July 2001.
【非特許文献３】K. Mikolajczyk, C. Schmid, “Indexing based on scale invariant interest points,” International Conference on Computer Vision, 525-531, July 2001. Schmid, C., and R. Mohr, “Local grayvalue invariants for image retrieval,” IEEE PAMI, 19, 5, 1997, pp. 530-534.
【非特許文献４】Schmid, C., and R. Mohr, “Local grayvalue invariants for image retrieval,” IEEE PAMI, 19, 5, 1997, pp. 530-534.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、コーナーの特徴量は、画像の拡大縮小変換に対しては不変性を持たないため、拡大縮小変換のある場合には、正確な認識が困難となる課題がある。
【０００８】
本発明は、このような状況に鑑みてなされたものであり、画像が拡大縮小されている場合にも、視点変化や明度変化による影響を軽減し、物体を確実に認識することができるようにするものである。
【課題を解決するための手段】
【０００９】
請求項１の画像処理装置は、入力された画像から予め登録されているモデル画像を認識する画像処理装置において、入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成手段と、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出手段と、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出手段と、入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較手段と、前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定手段とを備えることを特徴とする。
【００１０】
前記特徴量抽出手段は、第１のタイプの特徴量として特徴点近傍の濃度勾配の方向ヒストグラムを抽出し、第２のタイプの特徴量として次元縮退濃度勾配ベクトルを抽出するようにすることができる。
【００１１】
前記比較手段は、タイプ毎にkdツリーとされたモデル画像の特徴量群を、入力された画像の特徴量に基づいてk Nearest Neighbor (k-NN) 探索することで、候補対応特徴点組を生成するようにすることができる。
【００１２】
前記比較手段は、各タイプにおいて共通に抽出された特徴量を有する特徴点を候補対応特徴点組とするようにすることができる。
【００１３】
前記候補対応特徴点組を、モデル画像の位置姿勢を決める画像変換パラメータで規定されるパラメータ空間上に投票し、その最大投票数を閾値と比較することで絞り込む絞り込み手段をさらに備え、姿勢推定手段は、絞り込まれた候補対応特徴点組に基づいて、入力された画像の姿勢を推定するようにすることができる。
【００１４】
前記姿勢推定手段は、ランダムに選択したＮ組の候補対応特徴点組により決定されるモデル画像の位置姿勢を決める画像変換パラメータをパラメータ空間に投射し、パラメータ空間上で形成されるクラスタのうち、最多メンバ数を有するクラスタを求め、そのメンバから最小自乗法により求まる前記モデル画像の位置姿勢を決める画像変換パラメータをモデル画像を認識する認識結果として出力するようにすることができる。
【００１５】
前記姿勢推定手段は、最多メンバ数を有するクラスタのセントロイドを検出し、セントロイドからなるモデル画像の位置姿勢を決める画像変換パラメータをモデル画像を認識する認識結果として出力するようにすることができる。
【００１６】
前記多重解像度画像生成手段は、学習時における場合より粗い精度で多重解像度画像を生成するようにすることができる。
【００１７】
請求項９の画像処理方法は、入力された画像から予め登録されているモデル画像を認識する画像処理装置の画像処理方法において、入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成ステップと、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップと、前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップとを含むことを特徴とする。
【００１８】
請求項１０の記録媒体のプログラムは、入力された画像から予め登録されているモデル画像を認識する画像処理装置のプログラムであって、入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成ステップと、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップと、前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップとを含むことを特徴とする。
【００１９】
請求項１１のプログラムは、入力された画像から予め登録されているモデル画像を認識する画像処理装置のプログラムであって、入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成ステップと、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップと、前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップとをコンピュータに実行させることを特徴とする。
【００２０】
請求項１２の画像処理装置は、認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置において、前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成手段と、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出手段と、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出手段と、前記モデル画像の前記特徴量を登録する登録手段とを備えることを特徴とする。
【００２１】
前記特徴量抽出手段は、第１のタイプの特徴量として特徴点近傍の濃度勾配の方向ヒストグラムを抽出し、第２のタイプの特徴量として次元縮退濃度勾配ベクトルを抽出するようにすることができる。
【００２２】
前記登録手段は、モデル画像の特徴量群を、タイプ毎にkdツリーとして登録するようにすることができる。
【００２３】
請求項１５の画像処理方法は、認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置の画像処理方法において、前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップと、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、前記モデル画像の前記特徴量を登録する登録ステップとを含むことを特徴とする。
【００２４】
請求項１６の記録媒体のプログラムは、認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置のプログラムであって、前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップと、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、前記モデル画像の前記特徴量を登録する登録ステップとを含むことを特徴とする。
【００２５】
請求項１７のプログラムは、認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置のプログラムであって、前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップと、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、前記モデル画像の前記特徴量を登録する登録ステップとをコンピュータに実行させることを特徴とする。
【００２６】
本発明においては、入力された画像から多重解像度画像が生成され、その多重解像度画像のそれぞれの解像度の画像について特徴点が抽出される。特徴点における少なくとも２つの局所的な特徴量が抽出され、その特徴量とモデル画像の特徴量が比較され、類似する特徴量を有する特徴点の組としての候補対応特徴点組が生成され、それに基づいて、入力された画像の姿勢が推定される。
【００２７】
また、本発明においては、認識時における場合より細かい精度で多重解像度画像が生成される。多重解像度画像のそれぞれの解像度の画像について特徴点が抽出され、特徴点における少なくとも２つの局所的な特徴量が抽出され、登録される。
【発明の効果】
【００２８】
本発明によれば、物体を認識することができる。特に、本発明によれば、画像が拡大縮小されている場合にも、視点変化や明度変化に伴う画像の変化に拘らず、また物体が部分的に隠されてしまっているような場合でも、物体を確実に認識することが可能となる。
【００２９】
また、本発明によれば、物体を認識することが可能な特徴量を登録することができる。特に、本発明によれば、登録画像に対して認識対象物体の画像が拡大縮小されている場合にも、視点変化や明度変化に伴う画像の変化に拘らず、姿勢変化による画像変化に対してロバストに認識ができるような特徴点および特徴量を抽出し、登録することができる。
【発明を実施するための最良の形態】
【００３０】
以下に本発明の最良の形態を説明するが、開示される発明と実施の形態との対応関係を例示すると、次のようになる。明細書中には記載されているが、発明に対応するものとして、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その発明に対応するものではないことを意味するものではない。逆に、実施の形態が発明に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その発明以外の発明には対応しないものであることを意味するものでもない。
【００３１】
さらに、この記載は、明細書に記載されている発明の全てを意味するものではない。換言すれば、この記載は、明細書に記載されている発明であって、この出願では請求されていない発明の存在、すなわち、将来、分割出願されたり、補正により出現し、追加される発明の存在を否定するものではない。
【００３２】
請求項１の画像処理装置は、入力された画像から予め登録されているモデル画像を認識する画像処理装置（例えば、図１の認識部１２を有する画像処理装置１）において、入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像（例えば、図４の多重解像度画像）を生成する多重解像度画像生成手段（例えば、図１３のステップS132の処理を実行する図１の多重解像度生成部31）と、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出手段（例えば、図１３のステップS136の処理を実行する図１の特徴点抽出部32）と、前記特徴点における少なくとも２つの局所的な特徴量（例えば、図８の特徴点近傍の濃度勾配の方向ヒストグラム（タイプ１の特徴量）、図１１の最下段の線形補間リサンプリングされたタイプ2の特徴量）を抽出する特徴量抽出手段（例えば、図１３のステップS138乃至S142、図１４のステップS143乃至S145の処理を実行する図１の特徴量抽出部33）と、入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較手段（例えば、図１４のステップS150,S151の処理を実行する図１の特徴量比較部35）と、前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定手段（例えば、図１５のステップS158の処理を実行する図１のモデル姿勢推定部36）とを備えることを特徴とする。
【００３３】
前記特徴量抽出手段は、第１のタイプの特徴量として前記特徴点近傍の濃度勾配の方向ヒストグラム（例えば、図８の特徴点近傍の濃度勾配の方向ヒストグラム）を抽出し、第２のタイプの特徴量として次元縮退濃度勾配ベクトル（例えば、図１１の最下段の線形補間リサンプリングされたタイプ2の特徴量）を抽出する。
【００３４】
前記比較手段は、前記タイプ毎にkdツリーとされた前記モデル画像の特徴量群を、入力された画像の前記特徴量に基づいてk Nearest Neighbor (k-NN) 探索することで、前記候補対応特徴点組を生成する（例えば、図１７の処理）。
【００３５】
前記比較手段は、各タイプにおいて共通に抽出された前記特徴量を有する前記特徴点を前記候補対応特徴点組とする（例えば、図１７の四角形と円のペア、並びに四角形と十字図形のペア、ただし図中の四角形、五角形、三角形、円、または十字の図形は特徴点を表す）。
【００３６】
前記画像処理装置は、前記候補対応特徴点組を、前記モデル画像の位置姿勢を決める画像変換パラメータで規定されるパラメータ空間（例えば、画像変換パラメータ（scl，θ，dX，dY）で規定されるパラメータ空間）上に投票し、その最大投票数を閾値と比較することで絞り込む絞り込み手段（例えば、図２２のステップS301乃至S310の処理を実行する図２１の対応特徴点ペア絞込み部６１）をさらに備え、前記姿勢推定手段は、絞り込まれた前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する。
【００３７】
前記姿勢推定手段は、ランダムに選択したＮ組の前記候補対応特徴点組により決定される前記モデル画像の位置姿勢を決める画像変換パラメータ（例えば、ユークリッド変換、相似変換、アフィン変換、射影変換）をパラメータ空間に投射し、前記パラメータ空間上で形成されるクラスタのうち、最多メンバ数を有するクラスタを求め、そのメンバ（すなわち対応特徴点組群）から最小自乗法により求まる前記モデル画像の位置姿勢を決める画像変換パラメータを前記モデル画像を認識する認識結果として出力する（例えば、図１９のステップS201乃至S206の処理）。
【００３８】
前記多重解像度画像生成手段は、学習時における場合より粗い精度で前記多重解像度画像を生成する（例えば、図１３のステップS132の処理）。
【００３９】
請求項９の画像処理方法、請求項１０の記録媒体のプログラム、請求項１１のプログラムは、入力された画像から予め登録されているモデル画像を認識する画像処理装置（例えば、図１の認識部１２を有する画像処理装置1）の画像処理方法またはプログラムにおいて、入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像（例えば、図４の多重解像度画像）を生成する多重解像度画像生成ステップ（例えば、図１３のステップS132）と、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップ（例えば、図１３のステップS136）と、前記特徴点における少なくとも２つの局所的な特徴量（例えば、図８の特徴点近傍の濃度勾配の方向ヒストグラム、図１１の最下段の線形補間リサンプリングされたタイプ2の特徴量）を抽出する特徴量抽出ステップ（例えば、図１３のステップS138乃至S142、図１４のステップS143乃至S145）と、入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップ（例えば、図１４のステップS150,S151）と、前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップ（例えば、図１５のステップS158）とを含むことを特徴とする。
【００４０】
請求項１２の画像処理装置は、認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置（例えば、図１の学習部11を有する画像処理装置1）において、前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像（例えば、図４の多重解像度画像）を、認識時における場合より細かい精度で生成する多重解像度画像生成手段（例えば、図２のステップS12の処理を実行する図１の多重解像度生成部21）と、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出手段（例えば、図２のステップS16の処理を実行する図１の特徴点抽出部22）と、前記特徴点における少なくとも２つの局所的な特徴量（例えば、図８の特徴点近傍の濃度勾配の方向ヒストグラム、図１１の最下段の線形補間リサンプリングされたタイプ2の特徴量）を抽出する特徴量抽出手段（例えば、図２のステップS19、図３のステップS25の処理を実行する図１の特徴量抽出部23）と、前記モデル画像の前記特徴量を登録する登録手段（例えば、図３のステップS29の処理を実行する図１のモデル辞書登録部24）とを備えることを特徴とする。
【００４１】
前記特徴量抽出手段は、第１のタイプの特徴量として前記特徴点近傍の濃度勾配の方向ヒストグラム（例えば、図８の特徴点近傍の濃度勾配の方向ヒストグラム）を抽出し、第２のタイプの特徴量として次元縮退濃度勾配ベクトル（例えば、図１１の最下段の線形補間リサンプリングされたタイプ2の特徴量）を抽出する。
【００４２】
前記登録手段は、前記モデル画像の特徴量を、前記タイプ毎にkdツリーとして登録する（例えば、図１のkdツリー構築部34の処理）。
【００４３】
請求項１５の画像処理方法、請求項１６の記録媒体のプログラム、請求項１７のプログラムは、認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置（例えば、図１の学習部11を有する画像処理装置1）の画像処理方法またはプログラムにおいて、前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像（例えば、図４の多重解像度画像）を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップ（例えば、図２のステップS12）と、前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップ（例えば、図２のステップS16）と、前記特徴点における少なくとも２つの局所的な特徴量（例えば、図８の特徴点近傍の濃度勾配の方向ヒストグラム、図１１の最下段の線形補間リサンプリングされたタイプ2の特徴量）を抽出する特徴量抽出ステップ（例えば、図２のステップS19、図３のステップS25）と、前記モデル画像の前記特徴量を登録する登録ステップ（例えば、図３のステップS29）とを含むことを特徴とする。
【００４４】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。この実施の形態は、本発明を、複数のオブジェクトを含む入力画像であるオブジェクト画像と、検出対象となるモデルを含むモデル画像（予め登録されている）とを比較し、オブジェクト画像からモデルを抽出する画像処理装置に適用したものである。
【００４５】
本実施の形態における画像処理装置の概略構成を図１に示す。この画像処理装置１はモデルの学習処理を行う学習部１１と、入力画像中の物体を認識する認識部１２の２つの部分から構成される。
【００４６】
学習部１１は、多重解像度生成部２１、特徴点抽出部２２、特徴量抽出部２３、およびモデル辞書登録部２４により構成されている。
【００４７】
多重解像度生成部２１は、入力されたモデル画像から多重解像度画像を生成する。特徴点抽出部２２は、多重解像度生成部２１により生成された多重解像度の各画像から特徴点を抽出する。特徴量抽出部２３は、特徴点抽出部２２により抽出された各特徴点の特徴量を抽出する。モデル辞書登録部２４は、特徴量抽出部２３により抽出されたモデル画像の特徴量群を登録する。
【００４８】
認識部１２は、多重解像度生成部３１、特徴点抽出部３２、特徴量抽出部３３、kdツリー構築部３４、特徴量比較部３５、およびモデル姿勢推定部３６により構成される。
【００４９】
多重解像度生成部３１は、入力されたオブジェクト画像から、各多重解像度の画像を生成する。特徴点抽出部３２は、多重解像度生成部３１により生成された多重解像度の画像から特徴点を抽出する。特徴量抽出部３３は、特徴点抽出部３２により抽出された各特徴点の特徴量を抽出する。これらの多重解像度生成部３１、特徴点抽出部３２、および特徴量抽出部３３により行われる処理は、学習部１１における多重解像度生成部２１、特徴点抽出部２２、および特徴量抽出部２３において行われる処理と同様の処理である。
【００５０】
kdツリー構築部３４は、モデル辞書登録部２４に登録されている特徴量からkdツリーを構築する。特徴量比較部３５は、特徴量抽出部３３により抽出された特徴量と、kdツリー構築部３４により構築されたkdツリーとして表現された認識対象となる全モデル画像（またはモデル毎処理を行う場合には各モデル画像）の特徴量群を比較する。モデル姿勢推定部３６は、特徴量比較部３５による比較結果に基づいて、オブジェクト画像に含まれるモデルの有無とその姿勢（モデル姿勢）を推定し、そのモデルの姿勢を表すパラメータ（物体姿勢パラメータ）を出力する。
【００５１】
なお、学習部１１と認識部１２は、常に両方が同時に存在する必要はない。学習部１１により予め学習された結果、必要な情報が登録されたモデル辞書登録部２４を認識部１２に搭載するか、或いは無線で利用できるようにするようにしてもよい。
【００５２】
次に、図２と図３のフローチャートを参照して、学習部１１における学習処理について説明する。
【００５３】
多重解像度生成部２１は、後述するステップＳ２８において、全モデルを処理したと判定するまで、ステップＳ１１乃至Ｓ２７の処理を繰り返す。そこで、ステップＳ１１において、多重解像度生成部２１は、１つの未処理モデルを選択する。ステップＳ１２において、多重解像度生成部２１は、多重解像度群を生成する。具体的には、多重解像度生成部２１は、入力された学習対象のモデル画像を所定の倍率に従って縮小し、多重解像度画像群を生成する。例えば、最低解像度の画像である原画像からの縮小率をα、出力する多重解像度画像の数をＮ（原画像を含む）とするとき、ｋ番目（原画像をｋ＝０とする）の多重解像度の解像度画像Ｉ[k]は、原画像Ｉ[0]を縮小率α×（Ｎ−ｋ）で、線形補間縮小することで生成される。
【００５４】
あるいは他の方法としては、解像度の一段階低い画像を生成するための縮小率をγ（固定値）とする、つまりＩ[0]を縮小率γkで、線形補間縮小することでＩ[k]を生成する方法も考えられる。
【００５５】
図４は、パラメータＮ＝１０，α＝0.1とした場合に生成される多重解像度画像群を示す。図４の例においては、原画像Ｉ[0]を縮小率0.9で縮小した画像Ｉ[1]、縮小率0.8で縮小した画像Ｉ[2]、・・・、縮小率0.1で縮小した画像Ｉ[9]の合計１０段階の多重解像度画像が生成されている。縮小率を規定する係数ｋの値が大きくなるほど画像がより小さい大きさに縮小される結果、各フレームの画枠自体も、係数ｋの値が大きい程小さくなる。
【００５６】
次に、特徴点抽出部２２は、後述するステップＳ２７において、全解像度画像を処理したと判定するまで、ステップＳ１３乃至Ｓ２６の処理を繰り返し、多重解像度生成部２１により生成された各解像度画像Ｉ[k]（ｋ＝０，・・・，Ｎ−１）から、画像の拡大縮小変換（スケール変換）があってもロバストに抽出されるような特徴点（スケール不変特徴点）を抽出するのであるが、スケール不変特徴点の抽出法としては、画像のスケールスペースを構築し、各スケール画像のDifference of Gaussian（DoG）フィルタ出力の局所極大点（局所的な所定の範囲の最大点）及び局所極小点（局所的な所定の範囲の最小点）のうち、スケール方向の変化によっても位置が変化しない点をスケール特徴点として抽出する方法（D. Lowe, “Object recognition from local scale-invariant features,” in Proc. International Conference on Computer Vision, Vol. 2, pp. 1150-1157, September 20-25, 1999, Corfu, Greece.）や、画像のスケールスペースを構築し、各スケール画像からHarrisコーナー検出器により抽出されたコーナー点のうち、スケールスペース画像のLaplacian of Gaussian（LoG）フィルタ出力の局所極大を与える点を特徴点として抽出する方法（K. Mikolajczyk, C. Schmid, “Indexing based on scale invariant interest points,” International Conference on Computer Vision, 525-531, July 2001.）などがある。スケール不変特徴点が抽出できる手法であれば、どのような抽出法でも特徴点抽出部２２に適用が可能である。
【００５７】
ここでは発明の一実施の形態として、スケール不変特徴点の抽出法として、D.ロー（D. Lowe）が提案する方法（“Distinctive image features from scale-invariant keypoints,” accepted for publication in the International Journal of Computer Vision, 2004.）を基礎とした方法を説明する。この手法では、スケール不変特徴点抽出対象画像のスケールスペース表現（T. Lindeberg, “Scale-space: A framework for handling image structures at multiple scales.”, Journal of Applied Statistics, vol. 21, no. 2, pp. 224-270, 1994”）を介して、当該画像のDoGフィルタ出力から、スケール方向も考慮に入れた局所極大点及び局所極小点が特徴点として抽出される。
【００５８】
そこで、ステップＳ１３において、特徴点抽出部２２は、各解像度画像のうちの未処理解像度画像を選択する。そして、ステップＳ１４において、特徴点抽出部２２は、スケールスペースの解像度画像を生成する。すなわち、スケール不変特徴点抽出対象画像Ｉ（多重解像度生成部２１で生成された各解像度画像（ｋ＝０，１，２，・・・，９の各解像度画像）のうちの１つの解像度画像が特徴点抽出対象画像となる）のスケールスペースが生成される。スケールスペースのｓ番目（ｓ＝０,・・・，Ｓ−１）の解像度画像Ｌsは、対象画像Ｉを式（１）に示される２次元ガウス関数を用いて、σ＝ｋs σ0で畳み込み積分（ガウスフィルタリング）することで生成される。
【００５９】
【数１】
【００６０】
ここでσ0は、対象画像Ｉのノイズ除去を目的としたぼかし度を決めるパラメータであり、ｋはスケールスペースの各解像度間で共通のぼかし度に関するコンスタントファクタであり、解像度画像Ｉ[k]のｋとは別のファクタである。なお、画像の水平方向をＸ軸、垂直方向をＹ軸としている。
【００６１】
図５は、このようにして生成されたスケールスペースの例を表している。この例においては、画像Ｉにそれぞれ以下の５個の２次元ガウス関数を用いて生成された解像度画像Ｌ0乃至Ｌ4を表している。
【００６２】
【数２】
【００６３】
なお、式（２）乃至式（６）の右辺の畳み込み積分の記号の右辺の項は、次式を表す。すなわち、実質的に式（１）と同一である。
【００６４】
【数３】
【００６５】
図５では、解像度レベル数Ｓ＝５とされている。
【００６６】
次に、ステップＳ１５で、特徴点抽出部２２は、DoGフィルタ出力画像を演算する。すなわち、このように得られた特徴点抽出対象のスケールスペースの各解像度画像ＬsのDoGフィルタ出力画像が求められる。このDoGフィルタは、画像の輪郭強調のために用いられる２次微分フィルタの一種であり、人間の視覚系で網膜から外側膝状体で中継されるまでに行われている処理の近似モデルとして、LoGフィルタと共によく用いられるものである。DoGフィルタの出力は、２つのガウスフィルタ出力画像の差分を取ることで効率よく得られる。すなわち、図５の中央の列に示されるように、ｓ番目（ｓ＝０,・・・，Ｓ−２）の解像度のDoGフィルタ出力画像Ｄsは、解像度画像Ｌsを、その１段上の階層の解像度画像Ｌs+1から減算する（Ｌs+1−Ｌsを演算する）ことで得られる。
【００６７】
次に、ステップＳ１６で、特徴点抽出部２２は、スケール不変特徴点を抽出する。具体的には、DoGフィルタ出力画像Ｄs（ｓ＝１,・・・，Ｓ−３）上のピクセルのうち、DoGフィルタ出力画像Ｄsの直接近傍領域（本実施の形態の場合、所定の位置の３×３個の画素の領域）、それより１段下位のDoGフィルタ出力画像Ｄs-1、並びにそれより１段上位のDoGフィルタ出力画像Ｄs+1上の同位置（対応する位置）の直接近傍領域の合わせて２７ピクセルにおいて、局所極大（２７ピクセルのうちの最大値）、局所極小（２７ピクセルのうちの最小値）となるピクセルがスケール不変特徴点として抽出され、特徴点群Ｋs（ｓ＝１,・・・，Ｓ−３）として保持される。図５の右側の列に、この特徴点群Ｋsが示されている。こうして抽出された特徴点はファクタがｋ2の解像度変化（つまりスケール変化）に対して、位置の不変性を持つスケール不変特徴点である。
【００６８】
特徴点抽出部２２は、後述するステップＳ２７で、全解像度画像を処理したと判定するまで、ステップＳ１３乃至Ｓ１６の処理を繰り返し、多重解像度生成部２１により生成された多重解像度レベル画像Ｉ[k]のそれぞれに対し、スケール不変特徴点群を抽出する。
【００６９】
次に、特徴量抽出部２３は、ステップＳ１７乃至Ｓ２５の処理を、ステップＳ２６で全特徴点を処理したと判定するまで繰り返し、各多重解像度レベル画像Ｉ[k]から抽出された各特徴点における特徴量を抽出する。以下においては、特徴点における特徴量を、文脈に応じて、特徴点特徴量または単に特徴量と呼ぶ。
【００７０】
特徴点特徴量としては、画像の回転変換、明度変化に対して不変な特徴量が用いられる。１つの特徴点に対して、複数の特徴量をあててもかまわない。その場合には、後段の特徴量比較部３５において、異なる特徴量での比較結果を統合する処理が必要となる。この実施の形態の場合、特徴量として、当該特徴点が抽出された画像の特徴点近傍領域の濃度勾配情報（各点における濃度勾配強度及び濃度勾配方向）から導出される２つの特徴量が用いられる。１つは、当該特徴点近傍領域における支配的な濃度勾配方向（以下、カノニカル方向と呼ぶ）で補正された方向ヒストグラムであり、他の１つは、カノニカル方向で補正された低次元縮退された濃度勾配ベクトルである。
【００７１】
第１の特徴量（タイプ１の特徴量）は、特徴点近傍の濃度勾配方向に関するヒストグラム（方向ヒストグラム）を、その支配的方向でゼロ補正したものである。この第１の特徴量を抽出するために、特徴量抽出部２３は、ステップＳ１７において、１つの未処理特徴点を選択する。そして、ステップＳ１８で、特徴量抽出部２３は、濃度勾配強度Ｍx,yと方向Ｒx,yを求める。すなわち、図６に示されるように、特徴点近傍（本実施の形態では、当該特徴点Ｐを中心として直径７ピクセル（半径3.5ピクセル）の範囲に入るピクセル群）の濃度勾配強度Ｍx,y、及び方向Ｒx,yが、それぞれ式（８）と式（９）により求められる。同式中のｘ，ｙは、濃度勾配を求めるピクセルの画像上の座標であり、Ｉx,yは、その画素値である。
【００７２】
【数４】
【００７３】
次に、ステップＳ１９で、特徴量抽出部２３は方向ヒストグラムを生成する。具体的には、特徴点近傍中の各ピクセルの方向Ｒx,yに基づいて、階級幅Δθ、階級数360°／Δθの方向ヒストグラム（本実施の形態では、Δθ＝１０°）の該当する階級に、各ピクセルの度数が累積される。このとき、図７に示されるように階級の量子化誤差の影響を小さくするため、度数（図７における縦軸）としては、階級（図７における横軸）の中心値から方向Ｒx,yへの距離の近さに比例した値が累積される。つまり、方向Ｒx,yから最も近い２つの階級をｇ，ｇ＋１とし、それぞれの中心値と方向Ｒx,yとの距離をｄ1，ｄ2とすると、階級ｇ，ｇ＋１に加算する度数値は、それぞれｄ2／（ｄ1＋ｄ2），ｄ1／（ｄ1＋ｄ2）となる。これにより、量子化誤差が少なくなる。
【００７４】
次に、ステップＳ２０で、特徴量抽出部２３は度数を正規化する。すなわち、得られた方向ヒストグラムの度数が、特徴点近傍ピクセル数（直径７ピクセルの範囲に入るピクセル数）で割算することにより正規化される。このように、勾配方向のみを累積することで、明度変化に対して強い特徴量を得ることができる。
【００７５】
さらに、特徴量抽出部２３は、ステップＳ２１でカノニカル方向を抽出し、ステップＳ２２で角度をカノニカル方向で正規化する。具体的には、回転変換に不変な特徴量とするために、得られた方向ヒストグラムの強いピークを与える角度としてのカノニカル方向が抽出され、そのカノニカル方向としての角度が０度になるようにヒストグラムをシフトすることで、角度の正規化が行われる。コーナー付近に抽出された特徴点に関するヒストグラムでは、そのエッジに垂直な方向に複数の強いピークが現れるため、このような場合は、強いピークごとにその角度が０度になるように補正した（正規化した）方向ヒストグラムが生成される。つまり、カノニカル方向の数だけ、別々に特徴量が生成される。ピークがカノニカル方向であるための基準は、例えば、最大累積値の８０％以上の累積値を与えるピーク方向とされる。
【００７６】
例えば、図８に示される方向ヒストグラムにおいては、角度80度の度数Ｖ80と角度200度の度数Ｖ200の２つのピークが存在する。すなわち、角度80度と角度200度が、カノニカル方向となる。この場合、図９に示されるように、カノニカル方向としての角度80度が０度となるように正規化されたヒストグラムと、図１０に示されるように、カノニカル方向としての角度200度が０度になるように正規化されたヒストグラムが生成される。
【００７７】
以上の処理で得られるタイプ１の特徴量は、方向ヒストグラムの階級数と同じ次元の特徴ベクトル（本実施の形態では、３６（＝360°／10°）次元ベクトル、すなわち、３６個の階級の度数を表わす数字からなるベクトル）となる。
【００７８】
次に、第２の特徴量（タイプ２の特徴量）として、低次元縮退濃度勾配ベクトルが求められる。タイプ１の特徴量が、特徴点近傍内ピクセルの空間的配置を無視し、特徴点近傍局所領域での濃度勾配ベクトルの方向の傾向（頻度）のみに注目しているのに対し、タイプ２の特徴量は、特徴点近傍の各濃度勾配ベクトルの空間的配置に注目する。この２種類の特徴量を後述する手法で特徴量比較に用いることで、視点変化、明度変化に強い認識を実現する。
【００７９】
タイプ２の特徴量の抽出のために、まず、ステップＳ２３で、特徴量抽出部２３は、特徴点近傍画像を回転補正する。すなわち、上述の処理で得られた特徴点近傍のカノニカル方向が０度になるように特徴点近傍画像が回転補正される。さらに、ステップＳ２４で、特徴量抽出部２３は、濃度勾配ベクトル群を演算する。例えば、図１１の上段に示されている特徴点近傍のピクセルの濃度勾配が、図８に示されるように分布している場合、上述したように、カノニカル方向は、80度と200度の方向となる。そこで、図１１の中段の左側の図に示されるように、上段の画像をカノニカル方向80度が０度になるように、特徴点近傍画像が、この例の場合時計方向に回転される。そして、その濃度勾配ベクトル群が演算される。このことは、結局、図８の角度80度のカノニカル方向を０度として正規化して得られた図９の方向ヒストグラムの濃度勾配ベクトル群を得ることに等しい。
【００８０】
また、同様に、図１１の中段の右側に示されるように、特徴点近傍画像が、200度のカノニカル方向が０度になるように回転補正される。そして、その画像の濃度勾配ベクトル群が演算される。このことは、図８の角度200度のカノニカル方向を０度として正規化することで得られた図１０の方向ヒストグラムの濃度勾配ベクトル群を得ることに等しい。
【００８１】
次に、ステップＳ２５において、特徴量抽出部２３は、濃度勾配ベクトル群を次元縮退する。すなわち、数ピクセル程度の特徴点抽出位置のずれを吸収できるようにするために、この濃度勾配ベクトル群が、図１１の下段の左右に示されているように、例えば、直径７ピクセルの円の内側にほぼ内接する四角形内の５×５ピクセルのベクトル群から、３×３個のベクトル群に線形補間リサンプルすることで次元縮退される。
【００８２】
線形補間リサンプルは、具体的には、図１２に示されるように、リサンプル画像のピクセル値を、その近傍４個の元画像ピクセルからの距離の比率で以下の式により演算することで行われる。
【００８３】
ｆ（Ｘ，Ｙ）＝（１−ｑ）・｛（１−ｐ）・ｆ（ｘ，ｙ）＋ｐ・ｆ（ｘ＋１，ｙ）｝
＋ｑ・｛（１−ｐ）・ｆ（ｘ，ｙ＋１）＋ｐ・ｆ（ｘ＋１，ｙ＋１）｝
・・・（１０）
【００８４】
上記式において、（Ｘ，Ｙ）はリサンプル画像のピクセル、（ｘ，ｙ），（ｘ＋１，ｙ），（ｘ，ｙ＋１），（ｘ＋１，ｙ＋１）は、リサンプル画像（Ｘ，Ｙ）近傍の元画像ピクセル、ｆ（ａ，ｂ）は座標（ａ，ｂ）のピクセル値、ｐ，ｑは、図１２に示されるように、近傍ピクセルからリサンプル画像（Ｘ，Ｙ）へのｘ座標方向とｙ座標方向の距離比である。
【００８５】
こうして、次元縮退されたベクトルのｘ，ｙ各成分を特徴ベクトルの各次元にあてることで、タイプ２の特徴量が得られる。線形補間リサンプルにより、３×３ベクトル群にリサンプルした場合には、１８（＝３×３×２）次元の特徴量となる。
【００８６】
なお、リサンプル後の目標の画像サイズが元画像サイズの半分以下の場合には、元画像を0.5倍づつ縮小していき、目標サイズより大きい最小の0.5倍乗数サイズの画像が得られたら、その画像から式（１０）のリサンプリングを行うことでリサンプリング時の誤差を小さくすることが可能である。例えば元画像の0.2倍サイズの画像を線形補間リサンプリングで作る場合には、0.5倍リサンプルを２回かけて得られる元画像の0.25倍サイズ画像に式（１０）の線形補間リサンプリングを行う。
【００８７】
ステップＳ２６において、特徴量抽出部２３は、全特徴点を処理したかを判定し、まだ処理していない特徴点が存在する場合には、処理をステップＳ１７に戻し、それ以降の処理を繰り返し実行する。ステップＳ２６において、全特徴点を処理したと判定された場合（ステップＳ１７乃至ステップＳ２５の処理が、全ての特徴点について行われた場合）、ステップＳ２７において、特徴点抽出部２２は、全解像度画像を処理したかを判定する。まだ処理していない解像度画像が存在する場合には、処理はステップＳ１３に戻り、それ以降の処理が繰り返し実行される。ステップＳ１３乃至ステップＳ２５の処理が、全ての解像度画像について行われたと判定された場合、ステップＳ２８において、多重解像度生成部２１は、全モデルを処理したかを判定する。まだ処理していないモデルが存在する場合には、処理はステップＳ１１に戻り、それ以降の処理が繰り返し実行される。ステップＳ１１乃至ステップＳ２５の処理が、全てのモデルについて実行されたと判定された場合、処理はステップＳ２９に進む。
【００８８】
モデル辞書登録部２４は、ステップＳ２９において、以上のように抽出された特徴点特徴量をラベル付けし、登録する。この場合、どのモデルの多重解像度画像群の、どの画像の、どのスケールから抽出された、どの特徴点の特徴量なのか、が参照できるようにラベル付けされ、モデル辞書に登録される。
【００８９】
以上のようにして、モデル辞書登録部２４には、認識させたい対象物体としてのモデル画像が特徴量として予め登録される。
【００９０】
学習部１１と認識部１２の両方を画像処理装置１が有する場合には、認識部１２は、このモデル辞書登録部２４をそのまま利用することが可能である。学習部１１と認識部１２が別の画像処理装置として構成される場合には、以上のようにして必要な情報が登録されたモデル辞書登録部２４が、認識部１２を有する画像処理装置に搭載されるか、或いは無線通信により利用可能とされる。
【００９１】
次に、認識部１２における入力画像の物体認識時の処理について、図１３乃至図１５のフローチャートを参照して説明する。
【００９２】
多重解像度生成部３１、特徴点抽出部３２、および特徴量抽出部３３は、ステップＳ１３１乃至Ｓ１４７において、入力されたオブジェクト画像に対して、ステップＳ１１乃至Ｓ２７における学習部１１の多重解像度生成部２１、特徴点抽出部２２、および特徴量抽出部２３と同様の処理を行う。その説明は繰り返しになるので省略する。但し、パラメータＮとαで決まる多重解像度画像の構成が、認識時では学習時と異なっている。
【００９３】
多重解像度生成部２１は、学習時の多重解像度画像を広い倍率レンジで細かい精度で生成するのに対し、多重解像度生成部３１は、認識時において、粗い精度で多重解像度画像を生成する。具体的に、本実施の形態で適用しているパラメータは、ステップＳ１２の学習時がＮ＝１０，α＝0.1であるのに対し、ステップＳ１３２の認識時はＮ＝２，α＝0.5である。その理由は、次の通りである。
【００９４】
１）認識精度を上げるには、より多くの特徴点特徴量情報を用いて特徴量比較を行うのが望ましい。つまり、より多くの多重解像度画像から特徴点抽出するのが望ましい。
２）スケール変化のロバスト性を得るために、多重解像度画像の構成はなるべくスケールレンジを広くするのが望ましい。
３）モデル学習時にはリアルタイム性をそれほど重視しなくても良いので、モデル画像の多重解像度画像数を多くし、スケールレンジを広くして特徴点特徴量抽出し、保持することが可能である。
４）本実施の形態では、オブジェクト画像から抽出された各特徴点特徴量を、全モデルの全特徴点特徴量から構築されるkdツリーの k-Nearest Neighbor（k-NN）探索（後述する）を用いて特徴量の比較を行っているため、特徴量比較にかかる計算コストは、オブジェクト画像から抽出された特徴点数に対して比例して増加するが、モデル特徴点数に対しては、全認識対象モデルからkdツリーを構築した場合には全モデル特徴点をｎとすると、計算コストをlognのオーダー（つまりＯ(logn)）に抑えることができる。
５）また一方で、認識時はリアルタイム性が重視されるため、多重解像度画像数をなるべく減らすことで計算コストを小さくする必要が有る。
６）かといって、入力されたオブジェクト画像から多重解像度画像を生成せず、原画像のみを用いてしまうと、モデル画像の原画像のサイズよりもオブジェクト画像中の認識対象物体のサイズが大きい場合には、その物体の認識が不可能となってしまう。
【００９５】
以上の理由から、図１６に示されるように、学習時のモデル画像からは、より多くの（ｋ＝０乃至９の）多重解像度画像群をより広いレンジで生成し（Ｎ＝１０，α＝0.1）、より多くの特徴点を抽出する一方、認識時には、オブジェクト画像から、認識に最小限必要な（ｋ＝０，１の）多重解像度画像群を生成し（Ｎ＝２，α＝0.5）、それから特徴点を抽出し、特徴量比較をkdツリー上でk-NN探索を適用することで行い、計算コストを少なくかつ精度の良い認識を実現することを可能とする。図１６には、原画像は大き過ぎて対応する大きさのスケールの階層のモデル画像は存在しないが、原画像（ｋ＝０）を0.5倍に縮小する（ｋ＝１）ことで、対応する大きさのスケールの階層のモデル画像が見い出されるようになることが示されている。
【００９６】
ステップＳ１３１乃至ステップＳ１４５の処理が、全特徴点並びに全解像度画像について行われた場合、処理はステップＳ１４８に進む。
【００９７】
後述するように、オブジェクト画像から抽出された各特徴点特徴量（次元縮退された濃度勾配ベクトル群）は、登録されている認識対象モデルの各特徴点特徴量と比較され、類似するモデル特徴点特徴量と候補対応特徴点組として組み合わされる。最も単純な特徴量比較方法は全探索である。つまり、オブジェクト画像の各特徴点特徴量に対して、全認識対象モデルの全特徴点特徴量との特徴量間類似度の計算を行い、その類似度により対応特徴点組を選択するのが最も単純な方法である。しかし、全探索による方法は、計算コスト的に実用的でない。そこで本発明の実施の形態では、大量のデータ群からデータを高速に探索するために、kdツリーというデータ構造を用いたツリー探索手法（J. H. Friedman, J. L. Bentley, R. A. Finkel, “An algorithm for finding best matches in logarithmic expected time,” ACM Transactions on Mathematical Software, Vol. 3, No. 3, pp. 209-226, September 1977.）が用いられる。Kdツリーは、ｋ次元の木構造の意味である。
【００９８】
kdツリー構築部３４は、これまでの学習過程でモデル辞書中に登録されたモデルのうち一部のモデルに関して認識させれば良い場合には、ステップＳ１４８において、認識対象となるモデルについてのみ、その全特徴点特徴量からkdツリーを構築する。本実施の形態の場合は、タイプ１の特徴量の36ｄツリー（ｋ＝３６）とタイプ２の特徴量の18ｄツリー（ｋ＝１８）が、それぞれ構築される。ツリーの各リーフ（終端ノード）には、１つの特徴点特徴量が、その特徴量がどのモデルの多重解像度画像群の、どの画像の、どのスケールから抽出された、どの特徴点の特徴量なのか、が参照できるようなラベルとともに保持される。
【００９９】
一方、モデル辞書に登録された全モデルを認識させる場合には、モデルの追加学習の度にツリーを構築し直し、ツリー自体がモデル辞書に登録される。この場合には、ステップＳ１４８におけるkdツリーの構築処理は省略される。
【０１００】
特徴量比較部３５は、ステップＳ１４９で、オブジェクト画像の未処理特徴点を選択する。そして、ステップＳ１５０において、特徴量比較部３５は、オブジェクト画像のタイプ１の特徴点特徴量と、類似するｋ個のモデルの特徴点特徴量をペア組みする。同様に、ステップＳ１５１で、特徴量比較部３５は、オブジェクト画像のタイプ２の特徴点特徴量と、類似するｋ個のモデルの特徴点特徴量をペア組みする。すなわち、特徴点抽出部３２と特徴量抽出部３３により抽出されたオブジェクト画像の各特徴点特徴量は、特徴量比較部３５により、k-NN探索により特徴量が類似するｋ個（図１７の例の場合、４個）のモデル特徴点特徴量とペア組みされる（k-NN探索のｋの値と、kdツリーのｋの値は、同じｋの文字を使用してはいるが、任意の別の値とし得る（もちろん、同じ値としてもよい））。本実施の形態では、タイプ１の特徴量のk-NN探索に用いる非類似度として、式（１１）のユークリッド距離（その値が大きい程、類似していないことを表す）が、タイプ２の特徴量の類似度として、式（１２）に示すコサイン相関値（その値が大きい程、類似していることを表す）が、それぞれ用られる。
【０１０１】
【数５】
【０１０２】
但し、式（１１）において、ｕV，ｖVは非類似度を計算する対象の特徴量ベクトル、ｕn，ｖnはそれぞれｕV，ｖVのｎ次元における値、ＮはｕV，ｖVベクトルの次元数を、それぞれ表わす。
【０１０３】
式（１２）において、ｕV，ｖVは類似度を計算する対象の特徴量ベクトルであり、ｕV・ｖVはベクトルの内積を表す。特徴量が類似するｋ個のペア（組）を抽出する際に、非類似度（タイプ１特徴量に対して）、類似度（タイプ２特徴量に対して）に対する閾値判定を入れてもよい。タイプ２の特徴量に対する類似度計算尺度にコサイン相関値を用いる理由は、明度変化による局所濃度勾配ベクトルの強度の変化に特徴量が影響されないようにするためである。また、コサイン相関値による類似度のかわりに、ｕV，ｖVをベクトル長を１で正規化し、それらのユークリッド距離を非類似度としてタイプ２の特徴量としてもよい。この場合も明度変化による局所濃度勾配ベクトルの強度の変化に特徴量が影響されないようになる。
【０１０４】
特徴量比較部３５は、ステップＳ１４９乃至ステップＳ１５１の処理を、各オブジェクト画像の特徴点に対して実行する。そして、ステップＳ１５２において、特徴量比較部３５は、全特徴点を処理したかを判定し、まだ処理していない特徴点が存在する場合には、処理をステップＳ１４９に戻し、それ以降の処理を繰り返し実行する。ステップＳ１５２において、全特徴点を処理したと判定された場合には、処理はステップＳ１５３に進む。
【０１０５】
タイプ１とタイプ２の２つのタイプの特徴量を用いるので、特徴量比較部３５は、入力されたオブジェクト画像の特徴点に対する特徴点ペアを特徴量タイプごとに上述の方法で求めた後、ステップＳ１５３で、タイプ１とタイプ２の両方で共通して抽出された特徴点ペアのみを候補対応特徴点組として選択し、モデル毎に分類する。そして、この候補対応特徴点組は、後段のモデル姿勢推定部３６に供給される。モデル姿勢推定部３６では、モデルごとの処理を行うため、抽出された候補対応特徴点組をモデルごとに分類して渡すことで、処理の効率化を図ることができる。
【０１０６】
図１７は、以上の処理を模式的に表している。kdツリー構築部３４により、タイプ１の特徴量の36ｄツリー構造と、タイプ２の特徴量の18ｄツリー構造が生成される。オブジェクト画像の特徴量群から、k-NN探索（いまの場合、ｋ＝４）によりタイプ１の特徴量の36ｄツリー構造からタイプ１の特徴量の４個の類似ペア群が探索される。この例においては、オブジェクト画像の四角形で表されている特徴点特徴量（図中の四角形、五角形、三角形、円、または十字の図形は特徴点特徴量を表す）が、タイプ１の特徴量の36ｄツリー構造の五角形、三角形、円、または十字と類似するとして探索される。また、タイプ２の特徴量の18ｄツリー構造からk-NN探索によりタイプ２の特徴量の４個の類似ペア群が探索される。この例では、オブジェクト画像の四角形が、タイプ２の特徴量の18dツリー構造の平行四辺形、十字、円、またはひし形と類似するとして探索されている。
【０１０７】
タイプ１の特徴量の４個の類似ペア群と、タイプ２の特徴量の４個の類似ペア群の中から、共通する類似ペア群が選択される。この例の場合、タイプ１の特徴量の類似ペア群は、四角形と五角形、四角形と三角形、四角形と円、四角形と十字の４個である。これに対して、タイプ２の特徴量の類似ペア群は、四角形と平行四辺形、四角形と十字、四角形と円、四角形とひし形の４個である。したがって、四角形と円、並びに四角形と十字の類似ペア群が、２つのタイプに共通する特徴点ペアであるので、それが候補対応特徴点ペア（組）として、選択される。
【０１０８】
なお、以上に説明したように、特徴量タイプ毎、認識対象の全モデルの全特徴点特徴量から１つのkdツリーを構築し、入力画像の各特徴点特徴量のk-NNを探索するのではなく、特徴量タイプ毎、モデル毎にkdツリーを構築し、モデル毎に入力画像各特徴点特徴量のk-NNを探索するようにしてもよい。いずれの場合でも、出力はモデル毎に分類された候補対応特徴点組群であり、後述する後段の処理は共通となる。
【０１０９】
以上の処理により、特徴点近傍の局所的な濃度勾配情報が類似するペア群（モデル特徴点とオブジェクト特徴点のペア群）を抽出することができるが、巨視的に見ると、このように得られたペア群は、対応特徴点間の空間的位置関係がモデルのオブジェクト画像（入力画像）上での姿勢（モデル姿勢）と矛盾しない「真の特徴点ペア（インライヤ）」だけでなく、矛盾するような「偽の特徴点ペア（アウトライヤ）」を含んでいる。
【０１１０】
図１８は、インライヤとアウトライヤを模式的に表している。同図に示されるように、図中左側に示される三角形のモデル画像と、図中右側に示されるオブジェクト画像の三角形の検出対象物体（オブジェクト）が対応するとすると、モデル画像の三角形の頂点近傍の特徴点Ｐ１乃至Ｐ４は、検出対象物体の特徴点Ｐ11乃至Ｐ14とそれぞれ対応する。すなわち、特徴点Ｐ１が特徴点Ｐ11と、特徴点Ｐ２が特徴点Ｐ12と、特徴点Ｐ３が特徴点Ｐ13と、特徴点Ｐ４が特徴点Ｐ14とそれぞれ対応する。したがって、これらの候補対応特徴点組はインライヤを構成する。なお、図１８において、インライヤは実線で示されている。
【０１１１】
これに対して、モデル画像の特徴点Ｐ５は三角形の内部のほぼ中央に位置し、特徴点Ｐ６は三角形の周辺の近傍の外部に位置する。これに対して、特徴点Ｐ５とペア組されたオブジェクト画像の特徴点Ｐ15と、特徴点Ｐ６とペア組されたオブジェクト画像の特徴点Ｐ16は、それぞれ、検出対象物体とは遠く離れた点である。すなわち、特徴点Ｐ５と特徴点Ｐ15の候補対応特徴点組、並びに特徴点Ｐ６と特徴点Ｐ16の候補対応特徴点組はアウトライヤである。なお、図１８において、アウトライヤは破線で示されている。
【０１１２】
候補対応特徴点組群からモデル画像の入力画像中の位置姿勢を決める画像変換パラメータを導出する方法として、最小自乗推定により推定画像変換パラメータを求める手法が考えられる。結果の推定モデル姿勢と空間的位置関係の矛盾する対応ペアを排除し、残ったペアで再び最小自乗推定による推定画像変換パラメータ導出を行うという処理を繰り返すことで、より精度の良いモデル姿勢を求めることができる。
【０１１３】
しかしながら、候補対応特徴点組群中のアウトライヤの数が多い場合や、真の画像変換パラメータから極端に逸脱したアウトライヤが存在する場合には、上記最小自乗推定による推定結果は一般的に満足のいくものではないことが知られている（Hartley R., Zisserman A.,“Multiple View Geometry in Computer Vision.”, Chapter 3, pp.69-116, Cambridge University Press, 2000）。そこで、本実施の形態におけるモデル姿勢推定部３６は、ある画像変換の拘束の下、候補対応特徴点組群の空間的位置関係から「真の特徴点ペア（インライヤ）」を抽出し、抽出されたインライヤを用いてモデルの位置姿勢を決める画像変換パラメータを推定する。
【０１１４】
このモデル姿勢推定部３６によるモデル姿勢推定処理は、認識対象モデルごとに行われ、モデルごとにその有無、有る場合には姿勢の推定が行われる。以下の説明で出てくる候補対応特徴点組は、特徴量比較部３５の出力である候補対応特徴点組のうち、当該モデルに関するペアのみをまとめたペア群を意味する。
【０１１５】
画像変換としてはユークリッド変換、相似変換、アフィン変換、射影変換などが挙げられるが、本実施の形態においては、アフィン変換の拘束の下、姿勢推定を行う場合について詳細説明を行う。アフィン変換は、平行移動及び回転変換（ユークリッド変換）に拡大縮小変換を加えた相似変換に、せん断変形を許すような変換で、元の図形で直線上に並ぶ点は変換後も直線上に並び、平行線は変換後も平行線であるなど、幾何学的性質が保たれる変換である。アフィン変換パラメータを決定するためには候補対応特徴点組が３組以上必要となる。
【０１１６】
上述したように、候補対応特徴点組が３組以上なければ、アフィン変換パラメータを決定できない。そこで、モデル姿勢推定部３６は、ステップＳ１５４で１つの未処理モデルを選択した後、ステップＳ１５５で候補対応特徴点ペア（組）が３組以上あるかを判定する。候補対応特徴点組が２組以下の場合、モデル姿勢推定部３６は、ステップＳ１５６で、オブジェクト画像（入力画像）中にモデルが存在しない、又はモデル姿勢検出に失敗したとして、「認識不可」を出力する。一方、候補対応特徴点組が３組以上ある場合、モデル姿勢推定部３６は、モデル姿勢を検出可能であるので、アフィン変換パラメータの推定を行う。このため、モデル姿勢推定部３６は、ステップＳ１５７で座標変換を行う。すなわち、候補対応特徴点組のモデル特徴点位置座標が、モデル原画像上の位置座標に変換されるとともに、オブジェクト画像特徴点位置座標が、オブジェクト原画像の位置座標に変換される。そして、ステップＳ１５８で、モデル姿勢推定部３６は、姿勢推定処理を行う。
【０１１７】
ここで、アフィン変換パラメータについて説明する。モデル特徴点［ｘ ｙ］Tのオブジェクト特徴点［ｕ ｖ］Tへのアフィン変換は、以下の式（１３）で与えられる。
【０１１８】
【数６】
【０１１９】
この式（１３）において、ａi（ｉ＝１，…，４）は回転、拡大縮小、せん断変形を決定するパラメータを表し、［ｂ1 ｂ2］Tは、平行移動パラメータを表す。決定すべきアフィン変換パラメータはａ1，…，ａ4及びｂ1，ｂ2の６つであるため、候補対応特徴点組が３組あれば、アフィン変換パラメータを決定することができる。
【０１２０】
３組の候補対応特徴点組で構成されるペア群Ｐを、（[ｘ1 ｙ1]T，[ｕ1 ｖ1]T），（[ｘ2 ｙ2]T，[ｕ2 ｖ2]T），（[ｘ3 ｙ3]T，[ｕ3 ｖ3]T）とすると、ペア群Ｐとアフィン変換パラメータとの関係は、以下の式（１４）に示す線形システムで表現することができる。
【０１２１】
【数７】
【０１２２】
この式（１４）を、ＡｘV＝ｂVのように書き直すと（下付のＶは、添えられている文字（例えばｘVのｘ）がベクトルであることを表わす。以下、同様である）、アフィン変換パラメータｘVの最小自乗解は、以下の式（１５）で与えられる。
【０１２３】
ｘV＝Ａ-1ｂV ・・・（１５）
【０１２４】
候補対応特徴点組群から、アウトライヤが１つ以上混入するように、ランダムにペア群Ｐを繰り返し選択した場合、そのアフィン変換パラメータは、パラメータ空間上に散らばって投射される。一方、インライヤのみから構成されるペア群Ｐをランダムに繰り返し選択した場合、そのアフィン変換パラメータは、何れもモデル姿勢の真のアフィン変換パラメータに極めて類似した、すなわちパラメータ空間上で距離の近いものとなる。したがって、候補対応特徴点組群から、ランダムにペア群Ｐを選択し、そのアフィン変換パラメータをパラメータ空間上に投射していく処理を繰り返すと、インライヤはパラメータ空間上で密度の高い（メンバ数の多い）クラスタを形成し、アウトライヤは散らばって出現することになる。すなわち、パラメータ空間上でクラスタリングを行えば、最多メンバ数を持つクラスタの要素がインライヤとなる。
【０１２５】
モデル姿勢推定部３６における姿勢推定処理の詳細を図１９のフローチャートを用いて説明する。なお、このモデル姿勢推定部３６におけるクラスタリング手法としては、NN（Nearest Neighbor）法が用いられる。この際、上述したパラメータｂ1，ｂ2は、認識対象画像により様々な値を取り得るため、ｘ空間でもクラスタリングにおいてクラスタリング閾値の選択が認識対象に依存してしまう。そこで、モデル姿勢推定部３６では、「真のパラメータとａ1，…，ａ4は類似するが、ｂ1，ｂ2が異なるようなアフィン変換パラメータを与えるペア群Ｐは、殆ど存在しない」という仮定の下、パラメータａ1，…，ａ4（以下、ａVと表記する）で規定されるパラメータ空間上のみでクラスタリングを行う。なお、上記仮定が成り立たない状況が生じたとしても、ａV空間とは独立に、パラメータｂ1，ｂ2で規定されるパラメータ空間でクラスタリングを行い、その結果を考慮することで、容易に問題を回避することができる。
【０１２６】
先ず、ステップＳ２０１において、モデル姿勢推定部３６は初期化を行う。具体的には、繰り返し数を表す変数としてのカウント値cntがcnt＝１とされ、候補対応特徴点組群からランダムに３組のペアをペア群Ｐ1として選択し、アフィン変換パラメータａV1が求められる。また、モデル姿勢推定部３６は、クラスタ数を表す変数ＮをＮ＝１とし、アフィン変換パラメータ空間ａV上でａV1を中心とするクラスタＺ1を作る。モデル姿勢推定部３６は、このクラスタＺ1のセントロイドｃV1をｃV1＝ａV1とし、クラスタのメンバ数を表す変数ｎz1をｎz1＝１とし、カウンタ値cntをcnt＝２に更新する。
【０１２７】
次に、ステップＳ２０２において、モデル姿勢推定部３６は、候補対応特徴点組群からランダムに３組のペアをペア群Ｐcntとして選択し、アフィン変換パラメータａVcntを計算する。そして、モデル姿勢推定部３６は、計算されたアフィン変換パラメータａVcntをパラメータ空間に投射する。
【０１２８】
次に、ステップＳ２０３において、モデル姿勢推定部３６は、NN法によりアフィン変換パラメータ空間をクラスタリングする。具体的には、モデル姿勢推定部３６は、先ず以下の式（１６）に従って、アフィン変換パラメータａVcntと各クラスタＺiのセントロイドｃVi（ｉ＝１，…，Ｎ）との距離ｄ（ａVcnt, ｃVi）のうち、最小の距離ｄminを求める。
【０１２９】
ｄmin = ｍｉｎ 1≦i≦N ｛ ｄ(ａVcnt, ｃVi) ｝ ・・・（１６）
【０１３０】
そして、モデル姿勢推定部３６は、所定の閾値τ（例えばτ＝0.1）に対してｄmin＜τであればｄminを与えるクラスタＺiにａVcntを属させ、ａVcntを含めた全メンバでクラスタＺiのセントロイドｃiを更新する。また、クラスタＺiのメンバ数ｎziはｎzi＝ｎzi＋１とされる。一方、ｄmin≧τであれば、モデル姿勢推定部３６は、アフィン変換パラメータ空間ａV上でａVcntをセントロイドｃVN+1とする新しいクラスタＺN+1を作り、そのクラスタのメンバ数ｎzN+1をｎzN+1＝１とし、クラスタ数ＮをＮ＝Ｎ＋１とする。
【０１３１】
続いて、ステップＳ２０４で、モデル姿勢推定部３６は、繰り返し終了条件を満たすか否かを判別する。繰り返し終了条件は、例えば最多メンバ数が所定の閾値（例えば１５）を超え、且つ最多メンバ数と２番目に多いメンバ数との差が所定の閾値（例えば３）を超える場合、或いは繰り返し数カウンタのカウント値cntが、所定の閾値（例えば5000回）を超える場合のように設定することができる。ステップＳ２０４において、繰り返し終了条件が満たされないと判定された場合（Noと判定された場合）には、モデル姿勢推定部３６は、ステップＳ２０５で繰り返し数のカウント値cntをcnt＝cnt＋１とした後、処理をステップＳ２０２に戻し、それ以降の処理を繰り返す。
【０１３２】
一方、ステップＳ２０４で、繰り返し終了条件を満たすと判定された場合（Yesと判定された場合）には、ステップＳ２０６において、モデル姿勢推定部３６は、以上の処理で得られたインライヤが３ペアに満たない場合には、アフィン変換パラメータが決定できないため、認識結果を「認識対象モデル非検出」と出力し、インライヤが３ペア以上抽出された場合には、インライヤに基づいて、最小自乗法によりモデル姿勢を決定するアフィン変換パラメータを推定し、認識結果として出力する。
【０１３３】
インライヤを（[ｘIN1 ｙIN1]T，[ｕIN1 ｖIN1]T），（[ｘIN2 ｙIN2]T，[ｕIN2 ｖIN2]T），…とすると、インライヤとアフィン変換パラメータとの関係は、以下の式（１７）に示す線形システムで表現することができる。
【０１３４】
【数８】
【０１３５】
この式（１７）を、ＡINｘVIN＝ｂVINのように書き直すと、アフィン変換パラメータｘVINの最小自乗解は以下の式（１８）で与えられる。
【０１３６】
ｘVIN ＝ (ＡINT ＡIN) 1 ＡINTｂVIN ・・・（１８）
【０１３７】
ステップＳ２０６で、モデル姿勢推定部３６は、このアフィン変換パラメータｘVINで決定されるモデル姿勢をモデル認識結果として出力する。
【０１３８】
図１５に戻り、ステップＳ１５８またはステップＳ１５６の処理の後、ステップＳ１５９において、モデル姿勢推定部３６は、全モデルを処理したかを判定する。まだ処理していないモデルが存在する場合には、処理はステップＳ１５４に戻り、それ以降の処理が繰り返し実行される。ステップＳ１５９において、全てのモデルについて処理したと判定された場合、処理は終了される。
【０１３９】
以上の図１５のステップＳ１５４乃至Ｓ１５９の処理は、認識対象モデルごとに行なわれる。この処理が、図２０に模式的に示されている。この例においては、候補対応特徴点組群ｐ１乃至ｐ６から最初にランダムに３個の候補対応特徴点組群ｐ１,ｐ３,ｐ４が選択され、それに基づき計算されたアフィンパラメータがパラメータ空間に投射される。次に、ランダムに３個の候補対応特徴点組群ｐ３,ｐ４,ｐ６が選択され、それらに基づき、計算されたアフィンパラメータがパラメータ空間に投射される。同様の処理がさらに繰り返され、この例においては、３個の候補対応特徴点組群ｐ５,ｐ４,ｐ１が選択され、それに基づきアフィンパラメータが計算され、パラメータ空間に投射される。そして、パラメータ空間上において、近接するアフィンパラメータが、クラスタリングされ、そのクラスタリングされたアフィン変換パラメータに最小自乗法を適用することで、モデル姿勢が決定される。
【０１４０】
上記の手法を用いることにより、アウトライヤが候補対応特徴点組群中に多数含まれてしまっている場合でも、アウトライヤを排除し、高精度に姿勢推定（変換パラメータ導出）が可能となる。
【０１４１】
以上の実施の形態では、アフィン変換拘束の下での姿勢推定の詳細を述べた。アフィン変換拘束の下では、平面領域が支配的な、例えば箱や本などの３次元物体であれば、その支配平面についての視点変化に対してロバストな姿勢推定が可能となる。しかし、曲面や凹凸が支配的な３次元物体のロバストな姿勢推定を行うには、アフィン変換拘束を投影変換拘束に拡張する必要がある。ただし、この場合においても、推定すべき変換パラメータの次元が増えるだけで、上記手法を簡単に拡張することが可能である。
【０１４２】
このようにして、決定されたモデル姿勢は、例えば、図１６や図１８において破線で示されている。これらの図に示されるように、本実施の形態においては、単にモデル画像に対応する検出対象物体の存在の有無が検出されるだけでなく、その検出対象物体が存在する場合には、その姿勢までも推定され、出力される。
【０１４３】
なお、モデル姿勢推定部３６が推定するこのモデル姿勢は、オブジェクト画像の検出対象物体に対する相対的な姿勢を意味するから、モデル姿勢を基準の姿勢として考えた場合には、モデル姿勢推定部３６は、モデル画像に対する検出対象物体の姿勢を推定することを意味する。
【０１４４】
なお、以上の説明では、閾値τが定数値であるものとしたが、ステップＳ２０３乃至ステップＳ２０６の繰り返し処理を行う際に、始めは比較的大きな閾値τを用いて大雑把なインライヤ抽出を行い、繰り返し回数が増える毎に次第に小さい閾値τを用いる、いわゆる「焼きなまし法」のような手法を適用してもよい。これにより、精度よくインライヤを抽出することができる。
【０１４５】
また、以上の説明では、候補対応特徴点組群からランダムにペア群Ｐを選択し、そのアフィン変換パラメータをパラメータ空間上に投射していく処理を繰り返し、パラメータ空間上で最多メンバ数を持つクラスタの要素をインライヤとして、最小自乗法によりモデル姿勢を決定するアフィン変換パラメータを推定したが、これに限定されるものではなく、例えば最多メンバ数を持つクラスタのセントロイドを、モデル姿勢を決定するアフィン変換パラメータとしても構わない。さらに、組は３個以上の特徴点で構成してもよい。
【０１４６】
以上、オブジェクト画像の物体認識時において、多重解像度生成部３１、特徴点抽出部３２、特徴量抽出部３３、特徴量比較部３５、およびモデル姿勢推定部３６が、オブジェクト画像が更新される毎にそれを逐次処理するので、リアルタイムでの物体認識が可能になる。また、モデル毎に特徴量比較部３５により抽出された特徴点ペアは、モデル毎分類されモデル姿勢推定部３６においてモデル毎に姿勢推定が行われるので、入力画像中に複数のモデル物体が含まれているような画像でもモデル物体の認識が可能となる。
【０１４７】
ところで、特徴量比較部３５で生成された候補対応特徴点ペア群中のアウトライヤの比率が大きくなるほどモデル姿勢推定部３６におけるインライヤの選択確率が低下し、モデル姿勢を推定する際に多くの繰り返し回数が必要となるため、計算時間が増大する。したがって、このモデル姿勢推定部３６に入力される候補対応特徴点ペア群から、できる限りアウトライヤを排除しておくことが望ましい。そこで、本実施の形態における画像処理装置１では、図２１に示されるように、特徴量比較部３５とモデル姿勢推定部３６との間に、対応特徴点ペアの絞込みを行う対応特徴点ペア絞込み部６１を挿入することができる。この対応特徴点ペア絞込み部６１では、モデル姿勢推定部３６のモデル姿勢推定処理で仮定した画像変換拘束よりもパラメータ次元の少ない画像変換拘束の下（例えばモデル姿勢推定部３６でアフィン変換拘束を用いた場合には、対応特徴点ペア絞込み部６１で相似変換拘束を用いる）、各モデルについて一般化ハフ変換を行うことで、粗い画像変換パラメータ推定及びそれをサポートする対応特徴点ペア群の抽出を行う。
【０１４８】
次に、図２２のフローチャートを参照して、画像変換拘束に相似変換拘束を用いた場合の対応特徴点ペア絞込み部６１による候補対応特徴点ペアの絞込み処理について説明する。相似変換は平行移動（２次元画像上なのでＸ軸方向の変位dXとＹ軸方向の変位dY）及び回転変換（θ）に拡大縮小変換（scl）を加えた変換である。
【０１４９】
ステップＳ３０１において、対応特徴点ペア絞込み部６１は、上記相似変換パラメータdX，dY，θ,sclで規定される４次元パラメータ空間の各軸について、レンジを規定し、そのレンジ内で規定したステップ幅でビンを切ることで、一般化ハフ変換の投票空間を作る。例えば、dX軸、dY軸に関してレンジを±200、ステップ幅を20（単位はピクセル）、θ軸に関してレンジを０から360、ステップ幅を15（単位は度）、scl軸に関してレンジを0.4から1.6、ステップ幅を0.3（単位は拡大縮小率）とすると、20 × 24 × 5 = 2400個の投票ビンができる。
【０１５０】
ステップＳ３０２以降は、モデル毎の処理になる。対応特徴点ぺア絞込み部６１は、ステップＳ３０２において投票空間を初期化し、未処理モデルを選択する。すなわち、例えば各投票ビンの値が０に設定され、１つのモデルが選択される。
【０１５１】
ステップＳ３０３乃至ステップＳ３０９は当該モデルの候補対応特徴点ペア（組）毎の処理となるので、ステップＳ３０３において対応特徴点ぺア絞込み部６１は、未処理候補対応特徴点ペアを選択する。すなわち、１つの未処理候補対応特徴点ペアが処理対象として選択される。
【０１５２】
続いて、ステップＳ３０４において、対応特徴点ぺア絞込み部６１は、回転変換角度θを求める。例えば、図２３Ａに示されるように、モデル画像の特徴点Ｐのカノニカル方向がＤPであり、特徴点Ｐとペア（組）となるオブジェクト画像の特徴点Ｑのカノニカル方向が図２３Ｂに示されるように、ＤQである場合、図２４に示されるように、特徴点Ｐと特徴点Ｑを、対応する位置に配置させた場合に得られるカノニカル方向ＤQとＤPの差が回転変換角度θとなる。
【０１５３】
ステップＳ３０５乃至ステップＳ３０９はscl軸で規定したビンの代表scl値（上記例の場合、scl軸で切られた５ビンの代表scl値はそれぞれ0.4, 0.7, 1.0, 1.3, 1.6となる）それぞれに関して行われる処理となる。そこで、対応特徴点ぺア絞込み部６１は、まず、ステップＳ３０５において、未処理scl値を選択する。すなわち、１つの未処理scl値が選択される。
【０１５４】
次に、ステップＳ３０６において、対応特徴点ペア絞込み部６１は、図２５に示されるように、モデル画像を当該scl値で拡大あるいは縮小した場合の平行移動変換量dX，dYを求める。この平行移動変換量dX，dYはステップＳ３０４で求めた回転変換角度θ、オブジェクト画像上の当該特徴点Ｑの座標Xi，Yi、モデル画像上の当該特徴点Ｐの極座標における原点からの距離γと軸からの角度αにより、以下の式（１９）と式（２０）により導出できる。
【０１５５】
ｄＸ＝Ｘｉ−ｓｃｌ・γ・ｃｏｓ（α＋θ） ・・・（１９）
ｄＹ＝Ｙｉ−ｓｃｌ・γ・ｓｉｎ（α＋θ） ・・・（２０）
【０１５６】
相似変換を決定する４つのパラメータ（scl，θ，dX，dY）が求まったので、ステップＳ３０７において、対応特徴点ペア絞込み部６１は、そのパラメータを投票空間上に投票する。具体的には、パラメータが投票空間の該当するビンに投票される。
【０１５７】
対応特徴点ペア絞込み部６１は、ステップＳ３０８、Ｓ３０９の分岐処理に従い、以上のステップＳ３０３からの処理を当該モデルに関する全対応特徴点ペア、全scl値に関して行う。すなわち、ステップＳ３０８において、対応特徴点ペア絞込み部６１は、全scl値について処理したかを判定し、まだ処理していないscl値が存在する場合には、処理をステップＳ３０５に戻し、それ以降の処理を繰り返す。そしてステップＳ３０８において、全scl値について処理したと判定された場合、ステップＳ３０９において、対応特徴点ペア絞込み部６１は、全対応特徴点ペアを処理したかを判定し、まだ処理していない対応特徴点ペアが存在する場合には処理をステップＳ３０３に戻し、それ以降の処理を繰り返す。
【０１５８】
ステップＳ３０９で全対応特徴点ペアを処理したと判定された場合、ステップＳ３１０で、対応特徴点ペア絞込み部６１は、最多得票ビン及びその得票数を求める。すなわち、ステップＳ３０７の処理による投票の結果、最も得票数の多かったビンとその得票数が求められる。ステップＳ３１１で、対応特徴点ペア絞込み部６１は、ステップＳ３１０で求められた最大得票数が閾値以上かを判定する。この閾値は予め設定されている。最大得票数が閾値以上である場合には、ステップＳ３１２において、対応特徴点ペア絞込み部６１は、モデル有りと判定し、最多得票ビンに投票された候補対応特徴点ペアを出力する。すなわち、最多投票ビンの示す相似変換パラメータが、そのモデルのオブジェクト画像上での相似変換拘束の下での推定モデル姿勢となり、最多投票ビンに投票された候補対応特徴点ペア群が、相似変換拘束の下での推定モデル姿勢をサポートするインライヤ（極少数のアウトライヤを含む可能性もある）となる。ステップＳ３１１において、最大得票数が閾値以上ではないと判断された場合、ステップＳ３１３において、対応特徴点ペア絞込み部６１は、モデル無しと判定する。すなわち、オブジェクト画像中に存在しないモデルに対しては、得票にばらつきが生じるため、各モデルの一般化ハフ変換の結果に対して最大得票数が閾値以下となる。この場合には、モデルが検出されなかったと判定される。
【０１５９】
以上、ステップＳ３０２乃至ステップＳ３１３の処理はステップＳ３１４の分岐処理に従い全ての認識対象モデルに関して行われる。すなわち、ステップＳ３１２またはステップＳ３１３の処理の後、ステップＳ３１４において、対応特徴点ペア絞込み部６１は、全モデルを処理したかを判定する。まだ処理していないモデルが存在する場合には、処理はステップＳ３０２に戻り、それ以降の処理が繰り返し実行される。ステップＳ３１４において、全モデルを処理したと判定された場合には、候補対応特徴点ペアの絞込み処理は終了される。
【０１６０】
ステップＳ３１２で、モデル有りの判定がされたモデルについては、そのモデルに対するインライヤがモデル姿勢推定部３６に供給され、前述の手法によりさらに厳密なモデルの姿勢推定が行われる。
【０１６１】
以上詳述した対応特徴量ペア絞込み部６１による処理では、モデル姿勢推定部３６のモデル姿勢推定処理で仮定した画像変換拘束よりもパラメータ次元の少ない画像変換拘束の下で粗い画像変換パラメータ推定を行うことにより、高速に候補対応特徴点ペア絞込みを行うことができる。絞り込まれた特徴点ペアを用いてモデル姿勢推定部３６で画像変換パラメータの推定を行うことで、モデル姿勢推定部３６の前段に対応特徴点ペア絞込み部６１を挿入しない場合と比べ、より高速な画像変換パラメータの高精度推定が可能となる。対応特徴量ペア絞込み部６１による処理では、画像変換パラメータの次元を少なくしたことにより実際の変換と推定の変換との誤差が生じるが、投票空間の各ビンのサイズを、その誤差を許容できるくらい大きくとることによりその問題は解決される。
【０１６２】
以上説明したように、本実施の形態における画像処理装置１によれば、次のことが可能になる。
【０１６３】
１． 解像度画像群を構成するようにしたので、結果としてノイズが除去され、ノイズに対してもロバストな認識が可能となる。
２． 特徴点の局所領域濃度勾配のカノニカル方向を０度に正規化した特徴量を用いるようにしたので、回転変化にロバストな認識が可能となる。
３． 明度変化に影響されやすい局所領域濃度勾配の強度情報ではなく、方向情報を特徴量及びそのマッチングに用いたので、明度変化に対してロバストな認識が可能となる。
４． 全ての解像度間で特徴量間マッチングを行うようにしたので、拡大縮小変化に対してロバストな認識が可能となる。
５． 特徴点ペア抽出後、アフィン拘束及び一般化ハフ変換を用いるようにしたので、アフィン変換に対してロバストな認識が可能になる。
６． 局所特徴量間マッチングを用いるようにしたので、認識対象物体が部分的に隠されているような場合にも認識が可能となる。
７． モデル毎に特徴点ペアを抽出し、モデル毎に姿勢推定を行うようにしたので、入力画像中に複数のモデル物体が含まれているような画像でもモデル物体の認識が可能となる。
８． 学習時に、特徴点、特徴量をより広いスケールレンジでより細かいスケールサンプリングで抽出する一方で、認識時には粗いスケールレンジ、粗いスケールサンプリングで特徴点、特徴量を抽出し、特徴量比較をkdツリーによるk-NN探索法を用いることにより、認識精度を落とさずに認識計算コストを減少させることが可能となる。つまり、リアルタイムに精度よく物体の認識が可能となる。
【０１６４】
上述した一連の処理は、ハードウエアにより実行させることもできるし、ソフトウエアにより実行させることもできる。この場合、例えば、画像処理装置１は、図２６に示されるようなパーソナルコンピュータにより構成される。
【０１６５】
図２６において、CPU（Central Processing Unit）１２１は、ROM（Read Only Memory）１２２に記憶されているプログラム、または記憶部１２８からRAM（Random Access Memory）１２３にロードされたプログラムに従って各種の処理を実行する。RAM１２３にはまた、CPU１２１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１６６】
CPU１２１、ROM１２２、およびRAM１２３は、バス１２４を介して相互に接続されている。このバス１２４にはまた、入出力インタフェース１２５も接続されている。
【０１６７】
入出力インタフェース１２５には、キーボード、マウスなどよりなる入力部１２６、CRT(Cathode Ray Tube)、LCD(Liquid Crystal display)などよりなるディスプレイ、並びにスピーカなどよりなる出力部１２７、ハードディスクなどより構成される記憶部１２８、モデムなどより構成される通信部１２９が接続されている。通信部１２９は、インターネットを含むネットワークを介しての通信処理を行う。
【０１６８】
入出力インタフェース１２５にはまた、必要に応じてドライブ１３０が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア１３１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部１２８にインストールされる。
【０１６９】
一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、専用のハードウエアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、ネットワークや記録媒体からインストールされる。
【０１７０】
この記録媒体は、図２６に示されるように、装置本体とは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク（フロッピディスクを含む）、光ディスク（CD-ROM(Compact Disk-Read Only Memory),DVD(Digital Versatile Disk)を含む）、光磁気ディスク（MD（Mini-Disk）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア１３１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに提供される、プログラムが記録されているROM１２２や、記憶部１２８に含まれるハードディスクなどで構成される。
【０１７１】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１７２】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【産業上の利用可能性】
【０１７３】
本発明は、ロボット装置に適用することが可能である。
【図面の簡単な説明】
【０１７４】
【図１】本発明を適用した画像処理装置の構成例を示すブロック図である。
【図２】図１の学習部の学習処理を説明するフローチャートである。
【図３】図１の学習部の学習処理を説明するフローチャートである。
【図４】解像度画像を説明する図である。
【図５】DoGフィルタのスケールスペースを説明する図である。
【図６】特徴点近傍の濃度勾配方向を説明する図である。
【図７】ヒストグラムの度数の演算方法を説明する図である。
【図８】方向ヒストグラムの例を示す図である。
【図９】方向ヒストグラムの例を示す図である。
【図１０】方向ヒストグラムの例を示す図である。
【図１１】特徴量抽出の処理を説明する図である。
【図１２】リサンプリングの例を示す図である。
【図１３】図１の認識部の認識処理を説明するフローチャートである。
【図１４】図１の認識部の認識処理を説明するフローチャートである。
【図１５】図１の認識部の認識処理を説明するフローチャートである。
【図１６】学習時と認識時の多重解像度を説明する図である。
【図１７】特徴量の比較処理を説明する図である。
【図１８】インライヤとアウトライヤを説明する図である。
【図１９】姿勢推定処理の詳細を説明するフローチャートである。
【図２０】図１９の姿勢推定処理を説明する図である。
【図２１】本発明を適用した画像処理装置の他の構成例を示すブロック図である。
【図２２】図２１の対応特徴点ペア絞込み部の処理を説明するフローチャートである。
【図２３】モデル画像とオブジェクト画像の対応する特徴点を説明する図である。
【図２４】モデル画像とオブジェクト画像の特徴点の回転変換角度を説明する図である。
【図２５】平行移動変換量を説明する図である。
【図２６】パーソナルコンピュータの構成例を示すブロック図である。
【符号の説明】
【０１７５】
１ 画像処理装置， １１ 学習部， １２ 認識部， ２１ 多重解像度生成部， ２２ 特徴点抽出部， ２３ 特徴量抽出部， ２４ モデル辞書登録部， ３１ 多重解像度生成部， ３２ 特徴点抽出部， ３３ 特徴量抽出部， ３４ kdツリー構築部， ３５ 特徴量比較部， ３６ モデル姿勢推定部
【特許請求の範囲】
【請求項１】
入力された画像から予め登録されているモデル画像を認識する画像処理装置において、
入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成手段と、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出手段と、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出手段と、
入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較手段と、
前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定手段と
を備えることを特徴とする画像処理装置。
【請求項２】
前記特徴量抽出手段は、第１のタイプの特徴量として前記特徴点近傍の濃度勾配の方向ヒストグラムを抽出し、第２のタイプの特徴量として次元縮退濃度勾配ベクトルを抽出する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記比較手段は、前記タイプ毎にkdツリーとされた前記モデル画像の特徴量群を、入力された画像の前記特徴量に基づいてk Nearest Neighbor (k-NN) 探索することで、前記候補対応特徴点組を生成する
ことを特徴とする請求項２に記載の画像処理装置。
【請求項４】
前記比較手段は、各タイプにおいて共通に抽出された前記特徴量を有する前記特徴点を前記候補対応特徴点組とする
ことを特徴とする請求項３に記載の画像処理装置。
【請求項５】
前記候補対応特徴点組を、前記モデル画像の位置姿勢を決める画像変換パラメータで規定されるパラメータ空間上に投票し、その最大投票数を閾値と比較することで絞り込む絞り込み手段をさらに備え、
前記姿勢推定手段は、絞り込まれた前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する
ことを特徴とする請求項４に記載の画像処理装置。
【請求項６】
前記姿勢推定手段は、ランダムに選択したＮ組の前記候補対応特徴点組により決定される前記モデル画像の位置姿勢を決める画像変換パラメータをパラメータ空間に投射し、前記パラメータ空間上で形成されるクラスタのうち、最多メンバ数を有するクラスタを求め、そのメンバから最小自乗法により求まる前記モデル画像の位置姿勢を決める画像変換パラメータを前記モデル画像を認識する認識結果として出力する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項７】
前記姿勢推定手段は、前記最多メンバ数を有するクラスタのセントロイドを検出し、前記セントロイドからなる前記モデル画像の位置姿勢を決める画像変換パラメータを前記モデル画像を認識する認識結果として出力する
ことを特徴とする請求項６に記載の画像処理装置。
【請求項８】
前記多重解像度画像生成手段は、学習時における場合より粗い精度で前記多重解像度画像を生成する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項９】
入力された画像から予め登録されているモデル画像を認識する画像処理装置の画像処理方法において、
入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成ステップと、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、
入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップと、
前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップと
を含むことを特徴とする画像処理方法。
【請求項１０】
入力された画像から予め登録されているモデル画像を認識する画像処理装置のプログラムであって、
入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成ステップと、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、
入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップと、
前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項１１】
入力された画像から予め登録されているモデル画像を認識する画像処理装置のプログラムであって、
入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成ステップと、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、
入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップと、
前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップと
をコンピュータに実行させることを特徴とするプログラム。
【請求項１２】
認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置において、
前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成手段と、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出手段と、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出手段と、
前記モデル画像の前記特徴量を登録する登録手段と
を備えることを特徴とする画像処理装置。
【請求項１３】
前記特徴量抽出手段は、第１のタイプの特徴量として前記特徴点近傍の濃度勾配の方向ヒストグラムを抽出し、第２のタイプの特徴量として次元縮退濃度勾配ベクトルを抽出する
ことを特徴とする請求項１２に記載の画像処理装置。
【請求項１４】
前記登録手段は、前記モデル画像の特徴量群を、前記タイプ毎にkdツリーとして登録する
ことを特徴とする請求項１３に記載の画像処理装置。
【請求項１５】
認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置の画像処理方法において、
前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップと、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、
前記モデル画像の前記特徴量を登録する登録ステップと
を含むことを特徴とする画像処理方法。
【請求項１６】
認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置のプログラムであって、
前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップと、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、
前記モデル画像の前記特徴量を登録する登録ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項１７】
認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置のプログラムであって、
前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップと、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、
前記モデル画像の前記特徴量を登録する登録ステップと
をコンピュータに実行させることを特徴とするプログラム。
【請求項１】
入力された画像から予め登録されているモデル画像を認識する画像処理装置において、
入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成手段と、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出手段と、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出手段と、
入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較手段と、
前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定手段と
を備えることを特徴とする画像処理装置。
【請求項２】
前記特徴量抽出手段は、第１のタイプの特徴量として前記特徴点近傍の濃度勾配の方向ヒストグラムを抽出し、第２のタイプの特徴量として次元縮退濃度勾配ベクトルを抽出する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記比較手段は、前記タイプ毎にkdツリーとされた前記モデル画像の特徴量群を、入力された画像の前記特徴量に基づいてk Nearest Neighbor (k-NN) 探索することで、前記候補対応特徴点組を生成する
ことを特徴とする請求項２に記載の画像処理装置。
【請求項４】
前記比較手段は、各タイプにおいて共通に抽出された前記特徴量を有する前記特徴点を前記候補対応特徴点組とする
ことを特徴とする請求項３に記載の画像処理装置。
【請求項５】
前記候補対応特徴点組を、前記モデル画像の位置姿勢を決める画像変換パラメータで規定されるパラメータ空間上に投票し、その最大投票数を閾値と比較することで絞り込む絞り込み手段をさらに備え、
前記姿勢推定手段は、絞り込まれた前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する
ことを特徴とする請求項４に記載の画像処理装置。
【請求項６】
前記姿勢推定手段は、ランダムに選択したＮ組の前記候補対応特徴点組により決定される前記モデル画像の位置姿勢を決める画像変換パラメータをパラメータ空間に投射し、前記パラメータ空間上で形成されるクラスタのうち、最多メンバ数を有するクラスタを求め、そのメンバから最小自乗法により求まる前記モデル画像の位置姿勢を決める画像変換パラメータを前記モデル画像を認識する認識結果として出力する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項７】
前記姿勢推定手段は、前記最多メンバ数を有するクラスタのセントロイドを検出し、前記セントロイドからなる前記モデル画像の位置姿勢を決める画像変換パラメータを前記モデル画像を認識する認識結果として出力する
ことを特徴とする請求項６に記載の画像処理装置。
【請求項８】
前記多重解像度画像生成手段は、学習時における場合より粗い精度で前記多重解像度画像を生成する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項９】
入力された画像から予め登録されているモデル画像を認識する画像処理装置の画像処理方法において、
入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成ステップと、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、
入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップと、
前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップと
を含むことを特徴とする画像処理方法。
【請求項１０】
入力された画像から予め登録されているモデル画像を認識する画像処理装置のプログラムであって、
入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成ステップと、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、
入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップと、
前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項１１】
入力された画像から予め登録されているモデル画像を認識する画像処理装置のプログラムであって、
入力された画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を生成する多重解像度画像生成ステップと、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、
入力された画像の前記特徴量を前記モデル画像の特徴量と比較し、類似する特徴量を有する特徴点の組としての候補対応特徴点組を生成する比較ステップと、
前記候補対応特徴点組に基づいて、入力された画像の姿勢を推定する姿勢推定ステップと
をコンピュータに実行させることを特徴とするプログラム。
【請求項１２】
認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置において、
前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成手段と、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出手段と、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出手段と、
前記モデル画像の前記特徴量を登録する登録手段と
を備えることを特徴とする画像処理装置。
【請求項１３】
前記特徴量抽出手段は、第１のタイプの特徴量として前記特徴点近傍の濃度勾配の方向ヒストグラムを抽出し、第２のタイプの特徴量として次元縮退濃度勾配ベクトルを抽出する
ことを特徴とする請求項１２に記載の画像処理装置。
【請求項１４】
前記登録手段は、前記モデル画像の特徴量群を、前記タイプ毎にkdツリーとして登録する
ことを特徴とする請求項１３に記載の画像処理装置。
【請求項１５】
認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置の画像処理方法において、
前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップと、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、
前記モデル画像の前記特徴量を登録する登録ステップと
を含むことを特徴とする画像処理方法。
【請求項１６】
認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置のプログラムであって、
前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップと、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、
前記モデル画像の前記特徴量を登録する登録ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項１７】
認識の対象とされる画像と比較するためのモデル画像を学習する画像処理装置のプログラムであって、
前記モデル画像の解像度を、予め定められている割合で低下させることで、複数の異なる解像度の画像からなる多重解像度画像を、認識時における場合より細かい精度で生成する多重解像度画像生成ステップと、
前記多重解像度画像のそれぞれの解像度の画像について特徴点を抽出する特徴点抽出ステップと、
前記特徴点における少なくとも２つの局所的な特徴量を抽出する特徴量抽出ステップと、
前記モデル画像の前記特徴量を登録する登録ステップと
をコンピュータに実行させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【公開番号】特開２００６−６５３９９（Ｐ２００６−６５３９９Ａ）
【公開日】平成１８年３月９日（２００６．３．９）
【国際特許分類】
【出願番号】特願２００４−２４４０１８（Ｐ２００４−２４４０１８）
【出願日】平成１６年８月２４日（２００４．８．２４）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成１８年３月９日（２００６．３．９）
【国際特許分類】
【出願日】平成１６年８月２４日（２００４．８．２４）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]