(57)【特許請求の範囲】
【請求項１】
特徴量を表す要素群であるパタンと特徴量を表す要素群である対象データと前記パタンの特徴量の空間と変換係数から前記対象データの特徴量の空間への変換関数とから、前記パタンを前記変換関数で変換した要素群が前記対象データの要素群と高い類似度となるように前記変換関数の変換係数を算出する検索方法において、
前記パタンに含まれる要素に順に付加されたインデックスの値に対して単調非減少の値となる移動閾値を計算する閾値計算ステップと、
前記パタンの最初とされた要素と前記対象データの所定の要素とから暫定の変換係数Ｔを計算する変換係数計算ステップと、
前記変換係数Ｔを用いて、前記パタンの要素毎に、前記変換関数で変換された前記パタンの要素と前記対象データとのマッチングの度合いを配慮して、スコアと行列Ｂと行列Ｄを更新する対応関係効果計算ステップと、
前記スコアが更新されたときの前記パタンの要素の前記移動閾値より、更新された前記スコアが小さいか否かを判定する判定ステップと、
更新された前記スコアが前記パタンの要素の前記移動閾値以上であると判定された場合、更新係数ベクトルＵおよび前記変換係数Ｔを更新する変換係数更新ステップと、
前記行列Ｂと前記行列Ｄを更新する前に、前記更新係数ベクトルＵの係数の間の柔軟性を示す前記行列Ｂに初期値として対角行列を設定する設定ステップと
を含み、
更新された前記スコアが前記移動閾値より小さいと判定された場合、前記対象データの次の要素に対して、または前記の次の暫定の変換係数Ｔに対して、前記検索方法の手順を施し、
前記変換係数更新ステップにおいて、更新された前記スコアが前記移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立するとき、前記更新係数ベクトルＵおよび前記変換係数Ｔが更新されるとともに、
前記行列Ｂに前記対角行列が設定され、誤差の小さくなる位置を示す行列Ｄに０が設定されるか、
前記行列Ｂがそのままとされ、誤差の小さくなる位置を示す行列Ｄに０が設定されるか、
または前記行列Ｂがそのままとされ、誤差の小さくなる位置を示す行列Ｄに、前記行列Ｂに前記係数ベクトルＵを乗算して得られた積をそれまでの行列Ｄから引き算して得られた差が設定される
ことを特徴とする検索方法。
【請求項２】
請求項１項に記載の検索方法において、
対応関係効果計算ステップの前に、対応関係効果計算ステップまたは判定ステップにおいて使われる前記パタンとして、前記変換係数Ｔの値によって複数のパタンの中から一つを選ぶパタン選択ステップをさらに含む
ことを特徴とする検索方法。
【請求項３】
特徴量を表す要素群であるパタンと特徴量を表す要素群である対象データと前記パタンの特徴量の空間と変換係数から前記対象データの特徴量の空間への変換関数とから、前記パタンを前記変換関数で変換した要素群が前記対象データの要素群と高い類似度となるように前記変換関数の変換係数を算出する検索方法を実行する検索装置において、
前記パタンに含まれる要素に順に付加されたインデックスの値に対して単調非減少の値となる移動閾値を計算する閾値計算手段と、
前記パタンの最初とされた要素と前記対象データの所定の要素とから暫定の変換係数Ｔを計算する変換係数計算手段と、
前記変換係数Ｔを用いて、前記パタンの要素毎に、前記変換関数で変換された前記パタンの要素と前記対象データとのマッチングの度合いを配慮して、スコアと行列Ｂと行列Ｄを更新する対応関係効果計算手段と、
前記スコアが更新されたときの前記パタンの要素の前記移動閾値より、更新された前記スコアが小さいか否かを判定する判定手段と、
更新された前記スコアが前記パタンの要素の前記移動閾値以上であると判定された場合、更新係数ベクトルＵおよび前記変換係数Ｔを更新する変換係数更新手段と、
前記行列Ｂと前記行列Ｄを更新する前に、前記更新係数ベクトルＵの係数の間の柔軟性を示す前記行列Ｂに初期値として対角行列を設定する設定手段と
を有し、
更新された前記スコアが前記移動閾値より小さいと判定された場合、前記対象データの次の要素に対して、または前記の次の暫定の変換係数Ｔに対して、前記検索方法の手順を施し、
前記変換係数更新手段において、更新された前記スコアが前記移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立するとき、前記更新係数ベクトルＵおよび前記変換係数Ｔが更新されるとともに、
前記行列Ｂに前記対角行列が設定され、誤差の小さくなる位置を示す行列Ｄに０が設定されるか、
前記行列Ｂがそのままとされ、誤差の小さくなる位置を示す行列Ｄに０が設定されるか、
または前記行列Ｂがそのままとされ、誤差の小さくなる位置を示す行列Ｄに、前記行列Ｂに前記係数ベクトルＵを乗算して得られた積をそれまでの行列Ｄから引き算して得られた差が設定される
ことを特徴とする検索装置。
【請求項４】
特徴量を表す要素群であるパタンと特徴量を表す要素群である対象データと前記パタンの特徴量の空間と変換係数から前記対象データの特徴量の空間への変換関数とから、前記パタンを前記変換関数で変換した要素群が前記対象データの要素群と高い類似度となるように前記変換関数の変換係数を算出する検索方法の処理をコンピュータに実行させるプログラムにおいて、
前記パタンに含まれる要素に順に付加されたインデックスの値に対して単調非減少の値となる移動閾値を計算する閾値計算ステップと、
前記パタンの最初とされた要素と前記対象データの所定の要素とから暫定の変換係数Ｔを計算する変換係数計算ステップと、
前記変換係数Ｔを用いて、前記パタンの要素毎に、前記変換関数で変換された前記パタンの要素と前記対象データとのマッチングの度合いを配慮して、スコアと行列Ｂと行列Ｄを更新する対応関係効果計算ステップと、
前記スコアが更新されたときの前記パタンの要素の前記移動閾値より、更新された前記スコアが小さいか否かを判定する判定ステップと、
更新された前記スコアが前記パタンの要素の前記移動閾値以上であると判定された場合、更新係数ベクトルＵおよび前記変換係数Ｔを更新する変換係数更新ステップと、
前記行列Ｂと前記行列Ｄを更新する前に、前記更新係数ベクトルＵの係数の間の柔軟性を示す前記行列Ｂに初期値として対角行列を設定する設定ステップと
を含み、
更新された前記スコアが前記移動閾値より小さいと判定された場合、前記対象データの次の要素に対して、または前記の次の暫定の変換係数Ｔに対して、前記検索方法の手順を施し、
前記変換係数更新ステップにおいて、更新された前記スコアが前記移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立するとき、前記更新係数ベクトルＵおよび前記変換係数Ｔが更新されるとともに、
前記行列Ｂに前記対角行列が設定され、誤差の小さくなる位置を示す行列Ｄに０が設定されるか、
前記行列Ｂがそのままとされ、誤差の小さくなる位置を示す行列Ｄに０が設定されるか、
または前記行列Ｂがそのままとされ、誤差の小さくなる位置を示す行列Ｄに、前記行列Ｂに前記係数ベクトルＵを乗算して得られた積をそれまでの行列Ｄから引き算して得られた差が設定される
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は検索方法および検索装置、並びにプログラムに関する。
【背景技術】
【０００２】
従来から、形状を示す点群であるパタン（以下、パタンと称する）と、形状を示す点群である対象データ（以下、対象データと称する）とから、対象データで示される形状の中から、パタンで示される形状と同じ形状の位置および角度を検索する技術が提案されている。例えば、２次元点群で構成されている対象データ（以下、２Ｄ対象データと称する）の中から、２次元点群で構成されているパタン（以下、２Ｄパタンと称する）と同じ形状の位置および角度を検索する技術が提案されている（特許文献１参照）。また、検索結果を表す位置および角度の精度を向上させる技術（以下、この技術をICPと称する）が提案されている（非特許文献１参照）。更に、２Ｄパタンと２Ｄ対象データを対象とするＩＣＰ（以下、2D-ICPと称する）の他に、３次元点群で構成されている対象データ（以下、３Ｄ対象データと称する）と３次元点群で構成されているパタン（以下、３Ｄパタンと称する）を対象とし、検索結果を表す位置および角度の精度を向上させるＩＣＰ（以下、3D-ICPと称する）も提案されている（非特許文献２参照）。
【０００３】
更に、２次元点群の点毎に法線ベクトルを表す２次元ベクトルと言う特徴量が付いている事もあり、法線ベクトル付きの２次元点群を２Ｄパタンまたは２Ｄ対象データとして用いられる場合もある。また、３次元点群の点毎にノーマルベクトルを表す３次元ベクトルと言う特徴量が付いている事もあり、ノーマルベクトル付きの３次元点群を３Ｄパタンまたは３Ｄ対象データとして用いられる場合もある。法線ベクトルまたはノーマルベクトルと言う特徴量がパタンまたは対象データに含まれている場合は、そのベクトル特徴量を検索の際に配慮する技術が存在する。更に、３次元形状を２次元のデータに変換するプロセス（例えばカメラで３次元形状を撮影すれば得られる２次元の画像）が用いられる場合もあり、その時に、２次元対象データと、２次元点群に投影される３Ｄパタンが重なる様に、３Ｄパタンの位置および角度の精度を向上する技術（以下3D-2D-ICPと称する）も提案されている（非特許文献３参照）。抽象化すると、パタンまたは対象データが、特徴量を表す複数のベクトル（例えば、２次元点）で出来ている。以下で、パタンが持つ複数のベクトルの一つを要素とも称する。
【０００４】
以下、3D-ICPにおいて用いられる技術について説明する。
【０００５】
まず、３次元相似座標変換について説明する。
【０００６】
パタンに含まれる点に、式（１）に示す行列を、式（２）に示すようにかけることにより、パタンの３次元座標から検索空間の３次元座標に変換することができる。式（１）に示す行列のＴ１４，Ｔ２４，Ｔ３４は、式（３）に示すようにＸ，Ｙ，Ｚの移動量を示す。
【数１】
0005476343.tif 000002
・・・（１）
【０００７】
【数２】
0005476343.tif 000003
・・・（２）
【０００８】
【数３】
0005476343.tif 000004
・・・（３）
【０００９】
ここで、３次元の座標変換を相似変換に制限する。式（１）に示す行列の左上の３×３の行列は、式（４）に示すように、回転行列Ｒとスケール係数ｓの積になる。回転行列Ｒは、式（５）に示す行列であって、式（６）および式（７）の要件を満たす行列である。すなわち変換行列Ｔを、式（８）に示すように、移動量Ｖで示される移動、回転行列Ｒで示される回転、およびスケール係数ｓで示されるスケール変換が組み合わされた３次元の座標変換とすることができる。
【数４】
0005476343.tif 000005
・・・（４）
【００１０】
【数５】
0005476343.tif 000006
・・・（５）
【００１１】
【数６】
0005476343.tif 000007
・・・（６）
【００１２】
【数７】
0005476343.tif 000008
・・・（７）
【００１３】
る。
【数８】
0005476343.tif 000009
・・・（８）
【００１４】
ここで、式（９）〜式（１２）に示されるように、微分回転行列Ｈを導入する。その結果、式（１３）に示す座標変換式が得られる。
【数９】
0005476343.tif 000010
・・・（９）
【００１５】
【数１０】
0005476343.tif 000011
・・・（１０）
【００１６】
【数１１】
0005476343.tif 000012
・・・（１１）
【００１７】
【数１２】
0005476343.tif 000013
・・・（１２）
【００１８】
【数１３】
0005476343.tif 000014
・・・（１３）
【００１９】
次に、座標変換に微妙に変換を加える。
ここでは、式（１３）を式（１４）で表し、式（１５）および式（１６）に示すように微分を行い、式（１７）に示す微分の行列である微分行列Ｊと式（１８）に示す微分の係数のベクトルである更新係数ベクトルＵを得る。
【数１４】
0005476343.tif 000015
・・・（１４）
【数１５】
0005476343.tif 000016
・・・（１５）
【００２０】
【数１６】
0005476343.tif 000017
・・・（１６）
【数１７】
0005476343.tif 000018
・・・（１７）
【００２１】
【数１８】
0005476343.tif 000019
・・・（１８）
【００２２】
次に、３次元の点のマッチングおよび座標変換Ｔの最適化について説明する。
【００２３】
前述のように、パタンは、形状を示す３次元の点群であり、対象データは、形状を示す３次元の点群である。パタンの点毎に、対象データの対応する点を知ることが出来るのが最も好ましい。式（１９）および式（２０）に示されるように、対象データの点群の中で、パタンの点に対応すると判断された点の座標を座標Ｘｃｏｒｒと称し、変換行列Ｔの最適化前の誤差を誤差Ｘｅｒｒと称する。
【数１９】
0005476343.tif 000020
・・・（１９）
【００２４】
【数２０】
0005476343.tif 000021
・・・（２０）
【００２５】
ここで、式（２１）に示されるように、微分行列Ｊ（式（１７））と微分の係数のベクトルである更新係数ベクトルＵ（式（１８））を導入する。
【数２１】
0005476343.tif 000022
・・・（２１）
【００２６】
式（２２）に示されるように、A*U=Cの様に線形な数式となるので最小二乗法により更新係数ベクトルＵを求めることができる。
【数２２】
0005476343.tif 000023
・・・（２２）
【００２７】
より速く精度良く計算するためにノーマルベクトルと接触平面を利用する方法もある。ここでは、パタンは３次元の点群にノーマルベクトルを加えたものとし、対象データは３次元の点群にノーマルベクトルを加えたものとする。式（２３）に示されるように、対象データの点毎に、平面（p1，p2，p3，p4）が計算される。
【数２３】
0005476343.tif 000024
・・・（２３）
【００２８】
式（２４）に示されるように、変換条件として、変換後の点が平面の上にあることとする。
【数２４】
0005476343.tif 000025
・・・（２４）
【００２９】
誤差ｅは、式（２５）で示される。
【数２５】
0005476343.tif 000026
・・・（２５）
【００３０】
式（２６）に示されるように、微分を使用して誤差ｅが０になるような係数ベクトルＵを求めることができる。
【数２６】
0005476343.tif 000027
・・・（２６）
【００３１】
そこで、式（２７）に示されるように、A*U=Cの様に線形な数式となるので最小二乗法により更新係数ベクトルＵを求めることができる。
【数２７】
0005476343.tif 000028
・・・（２７）
【００３２】
以上を纏めると、式（２２）や式（２７）の様に、対応関係（＝パタン点と対象データの点が対応していると判断されている点ペア）毎に、Ａ＊Ｕ＝Ｃの様な線形的な式を得ることができる。すなわちそれらの式を組み合わせて、つまりそれらの行列Ａを縦方向でくっつけ、そしてそれらのベクトルＣを縦方向でくっつける事で、より大きな行列ＡとベクトルＣを作り、それらのすべての対応関係に対してＡ＊Ｕ＝Ｃの式を作る事ができる。
【００３３】
次に、更新係数ベクトルＵの使い方について考える。上述の方法では、式（２２）や式（２７）に示したように、式（２８）に示されるように線形的な式が得られるので、式（２９）および式（３０）に示されるように、最小二乗法など標準的な解法を利用することができる。
【数２８】
0005476343.tif 000029
・・・（２８）
【００３４】
【数２９】
0005476343.tif 000030
・・・（２９）
【００３５】
【数３０】
0005476343.tif 000031
・・・（３０）
【００３６】
その結果、式（３１）に示されるように、更新係数ベクトルＵから変換行列Ｔを最適化することができる。すなわち微分回転行列ＨからＲsmallが求められ、Ｒsmallから回転行列Ｒが求められる。そして移動量Ｖｘ，Ｖｙ，Ｖｚおよびスケールｓが求められる。その結果、最適化された相似座標変換Ｔが求められる（式（８））。
【数３１】
0005476343.tif 000032
・・・（３１）
【００３７】
ここで、makeRotation(H)は、回転行列の条件（式（６）や式（７））を満たさない３×３の行列Ｈから、最も近い正確な３×３の回転行列を求める関数である。SVD（特異値分析）など標準的な解法がある。
【００３８】
次に、対応点の検索について説明する。３次元の点（x,y,z,特徴量）、３次元の対象データ点群（x,y,z,特徴量）、および最大距離や特徴量を使うなどの対応条件を入力とし、対象データの点群の中で３次元の点に最も近い、対応条件を満たす点を検索する対応点検索として、３Ｄセル配列、ハッシュ、K-d trees、またはOctreesなどを使用する標準的な手法がある。
【００３９】
また、パタンマッチスコア計算として、変換行列Ｔ、３次元のパタン、３次元の対象データ、変換後の最大距離などの対応条件を入力とし、スコア値を出力する手法が用いられている。そのアルゴリズムは、まず、スコア値に０を設定して初期化し、パタンの点毎に、変換行列Ｔを掛けて、変換後の座標を計算し、対応する点を検索し、対応点の有無や距離や対応条件等を配慮して、検索結果によってスコアを更新する手続きを繰り返し、最終的にスコアを返すものである。
【００４０】
さらにまた、３次元のパタンの位置、回転、スケールを調整して、対象データに合わせる、いわゆる、微調整または精サーチと称する手法も用いられている。この場合、入力は、変換行列Ｔ、３次元のパタン、および３次元の対象データであり、出力は、最適化された変換行列Ｔとスコアとからなるポーズである。
【００４１】
そのアルゴリズムは、式（３０）に示す行列Ｂおよび行列Ｄを初期化し、スコアに０を設定して初期化し、パタン点毎にスコアを更新し、最小二乗法にて係数ベクトルＵの更新を計算して、変換行列Ｔを更新する処理を、最大ループ数となるまで、または収束するまで繰り返し、最終的に変換行列Ｔを出力するものである。ここで、パタン点毎にスコアを更新する手続きは、具体的には、現在の変換行列Ｔを使ってパタンの点を変換し、変換後の座標の近くに対象データの対応点を検索し、対応点が見つかれば、これを用いて行列Ｂおよび行列Ｄを更新し、さらにスコアを更新するものである。
【００４２】
また、変換行列Ｔが不明である場合に行われる、祖サーチ（Global Search）の手法がある。この場合、入力は、３次元のパタン、３次元の対象データ、検索空間、およびスコア閾値であり、出力は、変換行列Ｔとスコアとからなるポーズのリストである。各出力ポーズのスコアは、閾値より高い特性がある。また、各出力ポーズは、変換行列Ｔを微妙に代えてもスコア値が上がらない極値であると言う特性がある。出力データに含まれていない変換行列Ｔではスコアが入力のスコア閾値以下であるかスコアが極値でない。
【００４３】
祖サーチの手法として、検索空間をサンプリングして変換行列Ｔ毎に上述したようにパタンマッチスコアを計算し、スコアが局所的に最大で閾値より高い場合、変換行列Ｔをリストに追加し、リストの変換行列Ｔ毎に精サーチを実行して、リストを返すというものも存在する。
【先行技術文献】
【特許文献】
【００４４】
【特許文献１】特開２００６−２７７７１８号公報
【非特許文献】
【００４５】
【非特許文献１】http://en.wikipedia.org/wiki/Iterative_Closest_Point
【非特許文献２】Z.Zhang, “Iterative PointMatching for Registration of Free-Form Curves”, InriaSophia Antipolis, Programme4 - Robotique, Image et Vision, ResearchReport Nr.1658, March 1992,ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-1658.pdf
【非特許文献３】J.Feldmar, N.Ayache, F.Betting, ”3D-2D projectiveregistration of free-form curves and surfaces”, InriaSophia Antipolis, Programme4 - Robotique, Image et Vision, ResearchReport Nr.2434, December 1994,http://hal.inria.fr/docs/00/07/42/41/PDF/RR-2434/pdf
【発明の概要】
【発明が解決しようとする課題】
【００４６】
しかしながら、祖サーチにおいて、サンプリングの刻みを充分細かくしないと解答を見落としてしまい、サンプリングの刻みを充分細かくすると、実行時間が非常に長くなる。隠蔽、ノイズ、背景などの影響もある。さらに、産業的には、数秒以内の実行時間が求められている。
【００４７】
そこで、本発明は、上記課題を解決すること、すなわち、マッチングしながら微調整を行い、サンプリングの刻みをできるだけ大きくして、実行時間を短くしながら、解答を見つけることができる検索方法および検索装置、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【００４８】
上記課題を解決するために、本発明の検索方法の一側面は、それぞれ、対象データとパタンと変換関数とから、変換関数で対象データ空間へ変換されたパタンが対象データと高い類似度を占める様に、変換関数の係数を算出する検索方法であって、パタンに含まれる要素に順に付加されたインデックスの値に対して単調非減少の値となる移動閾値を計算する閾値計算ステップと、パタンの最初とされた要素と対象データの所定の要素と、検索空間のサンプリング係数とから変換関数の係数Ｔを計算する変換係数計算ステップと、変換係数Ｔを用いて、パタンの要素毎に、変換されたパタン要素と対応する対象データの要素を計算する対応要素計算ステップと、対応要素とのマッチングの度合いを配慮して、スコアと行列Ｂと行列Ｄを更新する対応関係効果計算ステップと、スコアが更新されたときのパタンの要素の移動閾値より、更新されたスコアが小さいか否かを判定する判定ステップと、更新されたスコアがパタンの要素の移動閾値以上であると判定された場合、更新係数ベクトルＵおよび変換係数Ｔを更新する変換係数更新ステップとを含み、更新されたスコアが移動閾値より小さいと判定された場合、対象データの所定の要素を次の対象データ要素として、スコアを初期化して、パタンの最初の要素から上述の処理を続けるものとされている。
【００４９】
また、本発明の検索方法の一側面は、上述の構成に加えて、パタンの最初の要素に対して対応要素計算する前に、更新係数ベクトルＵの係数の間の柔軟性を示す行列Ｂに初期値として対角行列を設定する設定ステップをさらに含み、変換係数更新ステップにおいて、更新されたスコアが移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立する時だけに、更新係数ベクトルＵおよび変換係数Ｔが更新されるものとされている。
【００５０】
さらに、本発明の検索方法の一側面は、上述の構成に加えて、変換係数更新ステップにおいて、更新されたスコアが移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立する時に、更新係数ベクトルＵおよび変換係数Ｔを更新した後で、行列Ｂに対角行列が設定され、誤差の小さくなる位置を示す行列Ｄに０が設定されるものとされている。
【００５１】
さらにまた、本発明の検索方法の一側面は、上述の構成に加えて、変換係数更新ステップにおいて、更新されたスコアが移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立するときに、更新係数ベクトルＵおよび変換係数Ｔを更新した後で、行列Ｂがそのままとされ、誤差の小さくなる位置を示す行列Ｄに０が設定されるものとされている。
【００５２】
また、本発明の検索方法の一側面は、上述の構成に加えて、変換係数更新ステップにおいて、更新されたスコアが移動閾値以上であると判定された場合、予め定められた微調整をすべき条件が成立するときに、更新係数ベクトルＵおよび変換係数Ｔを更新した後で、行列Ｂがそのままとされ、誤差の小さくなる位置を示す行列Ｄに、行列Ｂに更新係数ベクトルＵを乗算して得られた積をそれまでの行列Ｄから引き算して得られた差が設定されるものとされている。
【００５３】
上記課題を解決するために、本発明の検索装置の一側面は、それぞれ、対象データとパタンと変換関数とから、変換関数で対象データ空間へ変換されたパタンが対象データと高い類似度を占める様に、変換関数の係数を算出する検索方法を実行する検索装置であって、この検索方法は、パタンに含まれる要素に順に付加されたインデックスの値に対して単調非減少の値となる移動閾値を計算する閾値計算ステップと、パタンの最初とされた要素と対象データの所定の要素と、検索空間のサンプリング係数とから変換関数の係数Ｔを計算する変換係数計算ステップと、変換係数Ｔを用いて、パタンの要素毎に、変換されたパタン要素と対応する対象データの要素を計算する対応要素計算ステップと、対応要素とのマッチングの度合いを配慮して、スコアと行列Ｂと行列Ｄを更新する対応関係効果計算ステップと、スコアが更新されたときのパタンの要素の移動閾値より、更新されたスコアが小さいか否かを判定する判定ステップと、更新されたスコアがパタンの要素の移動閾値以上であると判定された場合、更新係数ベクトルＵおよび変換係数Ｔを更新する変換係数更新ステップとを含み、更新されたスコアが移動閾値より小さいと判定された場合、対象データの所定の要素を次の対象データ要素として、スコアを初期化して、パタンの最初の要素から上述の処理を続けるものとされている。
【００５４】
上記課題を解決するために、本発明のプログラムの一側面は、それぞれ、対象データとパタンと変換関数とから、変換関数で対象データ空間へ変換されたパタンが対象データと高い類似度を占める様に、変換関数の係数を算出する処理をコンピュータに実行させるプログラムであって、この処理は、パタンに含まれる要素に順に付加されたインデックスの値に対して単調非減少の値となる移動閾値を計算する閾値計算ステップと、パタンの最初とされた要素と対象データの所定の要素と、検索空間のサンプリング係数とから変換関数の係数Ｔを計算する変換係数計算ステップと、変換係数Ｔを用いて、パタンの要素毎に、変換されたパタン要素と対応する対象データの要素を計算する対応要素計算ステップと、対応要素とのマッチングの度合いを配慮して、スコアと行列Ｂと行列Ｄを更新する対応関係効果計算ステップと、スコアが更新されたときのパタンの要素の移動閾値より、更新されたスコアが小さいか否かを判定する判定ステップと、更新されたスコアがパタンの要素の移動閾値以上であると判定された場合、更新係数ベクトルＵおよび変換係数Ｔを更新する変換係数更新ステップとを含み、更新されたスコアが移動閾値より小さいと判定された場合、対象データの所定の要素を次の対象データ要素として、スコアを初期化して、パタンの最初の要素から上述の処理を続けるものとされている。
【発明の効果】
【００５５】
本発明の一側面によれば、サンプリングの刻みをできるだけ大きくして、実行時間を短くしながら、解答を見つけることができる検索方法および検索装置、並びにプログラムを提供することができる。
【図面の簡単な説明】
【００５６】
【図１】検索装置の機能の構成の例を示すブロック図である。
【図２】検索の処理の例を説明するフローチャートである。
【図３】移動閾値を説明する図である。
【図４】検索の処理の他の例を説明するフローチャートである。
【図５】コンピュータのハードウェアの構成例を示すブロック図である。
【発明を実施するための形態】
【００５７】
以下、本発明の一実施の形態の検索方法および検索装置について、図１〜図５を参照しながら説明する。
【００５８】
図１は、検索装置の機能の構成の例を示すブロック図である。検索装置は、プログラムを実行するコンピュータまたは専用の機器であり、移動閾値計算部１１、変換係数計算部１２、初期値設定部１３、対応要素計算部１４、対応関係効果計算部１５、パラメータ／変換係数更新部１６、およびポーズリスト生成部１７を含む。
【００５９】
移動閾値計算部１１は、移動閾値を計算する。移動閾値については後述する。変換係数計算部１２は、パタンの最初の要素（パタンが持つ複数のベクトルの一つ）であるパタン要素０と対象データの要素と、検索空間サンプリングから変換係数Ｔを計算する。初期値設定部１３は、行列Ｂや行列Ｄなどを初期化する。対応要素計算部１４は、変換係数Ｔを使って変換されたパタンの要素と類似度の高い、対象データの要素を計算する。
【００６０】
対応関係効果計算部１５は、対応要素計算部１４から対象データの対応要素が渡された場合、行列Ｂおよび行列Ｄを更新し、スコアを更新する。パラメータ／変換係数更新部１６は、最小二乗法により更新係数ベクトルＵを更新して、変換係数Ｔを更新する。パラメータ／変換係数更新部１６は、判定部３１を含む。判定部３１は、スコアが更新されたときのパタンの要素の移動閾値より、更新されたスコアが小さいか否かを判定する。
【００６１】
ポーズリスト生成部１７は、変換係数Ｔとスコアとからなるポーズリストを生成する。
【００６２】
図２は、検索の処理の例を説明するフローチャートである。このフローチャートを参照して、検索処理を説明する。ステップＳ１１において、検索装置は、変換係数Ｔの入力変換係数リスト、パタン、対象データ、およびスコア閾値を入力する。
【００６３】
ステップＳ１２において、移動閾値計算部１１は、パタンに含まれる要素に、検索順に付加されたインデックスであるパタン要素インデックスの値に対して単調非減少の値となる移動閾値を計算する。
【００６４】
図３は、移動閾値を説明する図である。図３において、実線は移動閾値を示し、点線は移動閾値の上限を示す。なお点線は全てのパタン要素（Ｎ個のパタン要素）について検索された対象データがそのパタン要素との対応関係が完全な場合のスコアの推移を示すものとなっている。
【００６５】
移動閾値は、パタン要素インデックスの値に対して単調非減少の値となるのが好ましい。例えば、概ね、０からパタン要素数Ｎの３分の１の範囲のパタン要素インデックスが小さい範囲（すなわち最初の方で検索されるパタン要素）については、移動閾値は単調増加し、パタン要素インデックスが中程度の範囲（概ね、パタンの要素数Ｎの３分の１からパタンの要素数Ｎの３分の２の範囲）で、移動閾値は一定の値となり、パタン要素インデックスが大きい範囲（概ね、パタンの要素数Ｎの３分の２からパタンの要素数Ｎの範囲）で、移動閾値は単調増加するようにしてもよい。また、例えば、パタン要素インデックスがパタンの要素数Ｎの半分以下の範囲で、移動閾値はパタン要素インデックスと同じ値とされ、パタン点インデックスがパタンの要素数Ｎの半分以上の範囲で、移動閾値は一定の値とするようにしてもよい。
【００６６】
ステップＳ１３とステップＳ３０とは、ループ１の処理とされ、入力変換関数リストの変換係数Ｔを全て選択するまで、ステップＳ１４〜ステップＳ２９の処理が繰り返される。
【００６７】
ステップＳ１４において、検索装置は、入力変換係数リストの変換係数Ｔを１つ選ぶ。
【００６８】
ステップＳ１５とステップＳ２９とは、ループ２の処理とされ、対象データの全ての要素が選択されるまで、ステップＳ１６〜ステップＳ２８の処理が繰り返される。
【００６９】
ステップＳ１６において、検索装置は、対象データの要素を１つ選ぶ。
【００７０】
ステップＳ１７において、変換係数計算部１２は、パタンの最初の要素であるパタン要素０と選択された対象データの要素と選択された変換係数Ｔから、パタン要素０が選択された対象データの要素と類似度の高い要素に変換される様に、変換係数Ｔを計算する（例えば、変換係数Ｔの中で移動量を表す移動量Ｖを計算してＴに設定する）。
【００７１】
ステップＳ１８とステップＳ２７とは、ループ３の処理とされ、予め定められた最大ループ数まで、ステップＳ１９〜ステップＳ２６の処理が繰り返される。なお、収束するまで、ステップＳ１９〜ステップＳ２６の処理が繰り返されるようにしてもよい。
【００７２】
ステップＳ１９において、初期値設定部１３は、行列Ｂおよび行列Ｄ（式（３０））を初期化し、スコアを０に初期化する。
【００７３】
ステップＳ２０とステップＳ２５とは、ループ４の処理とされ、すべてのパタン要素に対して、ステップＳ２１〜ステップＳ２４の処理が行われる。
【００７４】
ステップＳ２１において、対応要素計算部１４は、現在選択されているパタン要素を、現在の変換係数Ｔを用いて、対象データ要素の空間に変換し、変換した要素と類似度の高い対象データ要素を計算する。ステップＳ２２において、対応関係効果計算部１５は、対応要素との類似度を配慮し、行列Ｂおよび行列Ｄを更新する。
【００７５】
ステップＳ２３において、対応関係効果計算部１５は、対応要素との類似度を配慮し、スコアを更新する（たとえば、値１を加算する）。ステップＳ２４において、判定部３１は、スコアがパタン要素に対応する移動閾値より、スコアが小さいか否かを判定し、スコアが移動閾値より低ければ（小さいと判定された場合）、ループ４とループ３を中断して処理はステップＳ２９に進む。
【００７６】
ステップＳ２６において、パラメータ／変換係数更新部１６は、最小二乗法にて係数ベクトルＵを更新して、変換係数Ｔを更新する。
【００７７】
ステップＳ２８において、計算されたスコアが入力スコア閾値以上の場合、ポーズリスト生成部１７は、（変換係数Ｔ、スコア）を出力リストに追加する。
【００７８】
ステップＳ３１において、ポーズリスト生成部１７は、ポーズのリストとして出力リストを返して、検索の処理は終了する。
【００７９】
なお、ステップＳ２３のスコアの更新は、足し算に限られるものではない。例えば、通常のパタン要素の場合、類似度の高い対応要素があれば、スコアを引き上げ、類似度の高い対応要素が無ければ、変更しないとする。また、例えば、マッチング機能において重要性の高いパタン要素の場合、類似度の高い対応点があれば、スコアを変更せず、類似度の高い対応点が無ければスコアを０とする。また、例えば他のパタンと識別するためのパタン要素であれば、類似度の高い対応要素があれば、スコアを引き下げて、類似度の高い対応要素が無ければ、変更しないようにしてもよい。
【００８０】
以上のように、スコアがパタンの要素の移動閾値より、スコアが小さいか否かを判定し（たとえば、図２のＳ２４の処理）、スコアが移動閾値より小さいと判定された場合、ループ４とループ３を中断するようにしたので、処理を迅速に行うことができる。
【００８１】
図４は、検索の処理の他の例を説明するフローチャートである。
【００８２】
ステップＳ５１において、検索装置は、変換係数Ｔの入力変換係数リスト、パタン、対象データ、およびスコア閾値を入力する。ステップＳ５２において、移動閾値計算部１１は、パタンに含まれる要素に順に付加されたインデックスであるパタン要素インデックスの値に対して単調非減少の値となる移動閾値を計算する。
【００８３】
ステップＳ５３とステップＳ７１とは、ループ１の処理とされ、入力変換係数リストの変換係数Ｔを全て選択するまで、ステップＳ５４〜ステップＳ７０の処理が繰り返される。
【００８４】
ステップＳ５４において、検索装置は、入力変換係数リストの変換係数Ｔを１つ選ぶ。
【００８５】
ステップＳ５５とステップＳ７０とは、ループ２の処理とされ、対象データの全ての要素が選択されるまで、ステップＳ５６〜ステップＳ６９の処理が繰り返される。
【００８６】
ステップＳ５６において、検索装置は、対象データの要素を選ぶ。
【００８７】
ステップＳ５７において、変換係数計算部１２は、パタンの最初の要素であるパタン要素０と選択された対象データの要素と選択された変換係数Ｔから、パタン要素０が選択された対象データの要素と類似度の高い要素に変換される様に、変換係数Ｔを計算する（例えば、変換係数Ｔの中で移動量を表す移動量Ｖを計算してＴに設定する）。
【００８８】
ステップＳ５８において、初期値設定部１３は、行列Ｂおよび行列Ｄを初期化する。
この場合、行列Ｂには、対角行列が設定されて初期化される。対角行列の要素は更新係数ベクトルＵの要素の重みである。例えば、式（１）から式（３１）を参照して上述したように３Ｄ対象データの中から３Ｄパタンを検索する場合は、式（３２）に示されるように対角行列が設定される。式（３２）において、ｗａ，ｗｂ，ｗｃは回転の重み、ｗｘ，ｗｙ，ｗｚは移動量の重み、ｗｓは、スケールについての重みであり、それらの値を調整することにより、たとえば、回転を制限することもできる。
【数３２】
0005476343.tif 000033
・・・（３２）
【００８９】
更に、ステップＳ５８において、初期値設定部１３は、スコアを０に初期化し、パタン要素インデックスを示すパタン要素インデックス変数i を０に初期化し、整数である変数 N を０に初期化する。
【００９０】
ステップＳ５９とステップＳ６８とは、ループ３の処理とされ、ステップＳ６７でパタン要素インデックスｉが変数Ｎより高い値となるまで、ステップＳ６０〜ステップＳ６７の処理が繰り返される。
【００９１】
ステップＳ６０において、対応要素計算部１４は、パタン要素インデックスiで選択されているパタン要素を、現在の変換係数Ｔを用いて、対象データ要素の空間に変換し、変換した要素と類似度の高い対象データ要素を計算する。
【００９２】
ステップＳ６１において、対応関係効果計算部１５は、対応要素との類似度を配慮し、行列Ｂおよび行列Ｄを更新する。ステップＳ６２において、対応関係効果計算部１５は、対応要素との類似度を配慮し、スコアを更新する（たとえば、値１を加算する）。
【００９３】
ステップＳ６３において、判定部３１は、スコアがパタン要素に対応する移動閾値より、スコアが小さいか否かを判定し、スコアが移動閾値より低ければ（小さいと判定された場合）、ループ３を中断して処理はステップＳ７０に進む。
【００９４】
ステップＳ６４において、判定部３１は、予め定められた微調整条件が満たされたか否かを判定する。例として、微調整条件は、最後の微調整から類似度の高い対応要素が見つかった事と、パタン要素インデックスｉが変数Ｎに等しい事である。
【００９５】
ステップＳ６４において、微調整条件が満たされたと判定された場合、手続きはステップＳ６５に進み、パラメータ／変換係数更新部１６は、最小二乗法にて更新係数ベクトルＵを更新して、変換係数Ｔを更新する。ステップＳ６６において、パラメータ／変換係数更新部１６は、行列Ｂ、行列Ｄ、変数Ｎを更新し、手続きはステップＳ６７に進む。
【００９６】
ここで、行列Ｂは、係数ベクトルＵの係数の間の柔軟性を示し、行列Ｄは、誤差の小さくなる位置を示す。ステップＳ６６における、行列Ｂおよび行列Ｄの更新方法は、例えば、行列Ｂおよび行列Ｄが先ず初期化され、そしてパタン要素０から微調整時のパタン要素インデックスｉのパタン要素、現在の変換係数Ｔを用いて、パタン要素を対象データ空間に変換して、類似度の高い対象データ要素を計算して、その類似度を配慮して行列Ｂおよび行列Ｄが更新される。すなわち、更新された変換係数Ｔを用いて、行列Ｂと行列Ｄが正確に再計算される。なお詳細に、この再計算の処理に、対応要素計算のステップにおいて、対応要素を探索しても良いし、前回の微調整時に見つけた対象データの対応要素を使っても良い。また、行列Ｂおよび行列Ｄの再計算に、更新された変換係数Ｔの微分を計算して使用しても良いし、更新される前の変換係数Ｔの微分を使用しても良い。
【００９７】
また、ステップ６６における行列Ｂおよび行列Ｄの更新方法の例として、行列Ｂに、式（３２）に示される様な対角行列を設定し、行列Ｄに、０を設定するようにしてもよい。すなわち、微調整までのマッチング情報を捨てて、初期化された状態に今後のマッチング情報を格納する。
【００９８】
さらに、ステップ６６における行列Ｂおよび行列Ｄの更新方法の例として、行列Ｂをそのままとし、行列Ｄに０を設定するようにしてもよい。すなわち、微調整までの誤差情報を捨てて、柔軟性の情報を今後のマッチングで使用するものである。
【００９９】
さらにまた、ステップ６６における行列Ｂおよび行列Ｄの更新方法の例として、行列Ｂをそのままとし、行列Ｄに、行列Ｂに更新係数ベクトルＵを乗算して得られた積をそれまでの行列Ｄから引き算して得られた差を設定するようにしても良い。すなわち、微調整までの柔軟性の情報を保ち、誤差情報を更新された更新係数ベクトルＵに合わせるものである。
【０１００】
ステップＳ６４において、微調整条件が満たされていないと判定された場合、ステップＳ６５およびステップＳ６６の手続きはスキップされて、手続きはステップＳ６７に進む。
【０１０１】
ステップＳ６７において、パラメータ／変換係数更新部１６は、変数Ｎを更新する。具体的には、変数Ｎがパタン要素の数より小さい場合、１だけインクリメントされるように、変数Ｎが更新される。なお、例えば２または３だけインクリメントされるように、変数Ｎが更新されるようにしてもよい。
【０１０２】
またパラメータ／変換係数更新部１６は、パタン要素インデックスｉを更新する。より具体的には、微調整が行われた場合、パタン要素インデックスｉが０とされ、他の場合、パタン要素インデックスｉが１だけインクリメントされるように、パタン要素インデックスｉが更新される。なお、パタン要素インデックスｉのインクリメントは、例えば２または３だけインクリメントされるようにしてもよい。
【０１０３】
ステップＳ６９において、ポーズリスト生成部１７は、スコアが入力スコア閾値以上である場合、（変換係数Ｔ、スコア）を出力リストに追加する。ステップＳ７２において、ポーズリスト生成部１７は、ポーズのリストとして出力リストを返す。
【０１０４】
ループ１から抜けた場合、検索の処理は終了する。
【０１０５】
この様に、この例でループ３の最初のループでは、Ｎ＝０、i ＝０、最初のパタン要素がマッチされる。ステップＳ６４で微調整が行われたとする。するとステップＳ６７で、Ｎ＝１、i＝０に更新が行われるので、次に、ループ３では、パタンの最初の二つの要素（i=0とi=1）がマッチされる。ステップＳ６４で微調整が行われたとする。するとステップＳ６８で  Ｎ＝２，i＝０に更新が行われるので、次に、ループ３では、パタンの最初の三つの要素（i=0..2)がマッチされる。すなわち、段々微調整に使われるパタン要素数を増やしながら微調整が続けられる。
【０１０６】
なお、ステップＳ５８において、変数Ｎが、パタン要素数に初期化され、ステップＳ６４における微調整条件を、パタン要素インデックスｉがある整数kの倍数である事とし、ステップＳ６７において、１だけインクリメントされるようにパタン要素インデックスｉが更新されるようにし、ステップＳ６７において変数Ｎを変更しない様にしてもよい。この場合、パタン要素を１つずつ処理して、パタン要素インデックスiがkの倍数になっている時のみに微調整が行われる。全てのパタン要素は１回だけ処理されるので処理速度は速い。なお、この場合、ステップＳ６４における微調整条件を、パタン要素インデックスｉがパタン作成時に決まった微調整パタン要素インデックスの１つとするようにしてもよい。例えば、形状を現すパタンの場合、パタンの曲率の高い部分では、低い部分より頻繁に微調整を行う必要があると考えられ、曲率をパタン作成時に計算して、曲率が高いパタン要素のパタン要素インデックスｉを微調整インデックスリストに追加して、微調整条件を、パタン要素インデックスｉが、微調整インデックスリストに含まれていることとする。
【０１０７】
さらに、ステップＳ５９において、変数Ｎが、パタン要素数に初期化され、ステップＳ６４における微調整条件を、最初の微調整から集めた対応する要素ペアの最小類似度または平均類似度が閾値を下回ることとし、ステップＳ６７において変数Ｎを更新しない様にし、さらに、ステップ６７において、１だけインクリメントされるようにパタン要素インデックスｉが更新されるようにしてもよい。この場合、対応要素との類似度が低すぎると微調整を行い、必要な時だけに微調整を行うというアプローチである。なお、この場合、微調整を行ったとき、微調整時のパタン要素インデックスｉを保存して、パタン要素インデックスｉを０に更新し、パタン要素インデックスｉが保存した値を超えるまで微調整を無効にするようにしてもよい。
【０１０８】
以上で説明した、微調整条件の具体例と更新処理とを組み合わせるようにしてもよい。
【０１０９】
また、パタン要素の順番を付ける方法には、例えば、未だ選択されていない要素の中からパタン要素０に最も類似度の高い要素をパタン要素ｉとするものがある。さらに、パタン要素の順番を付ける方法には、未だ選択されていない要素の中からパタン要素ｉ−１に最も類似度の高い要素をパタン要素ｉとする方法もある。
【０１１０】
パタン要素の順番付けと移動閾値の採用により、仮に、パタン要素０に対応する要素が対象データに含まれていればパタンが検索される可能性は高い。しかし、パタン要素０に対応する要素が対象データに含まれていない場合、検索される可能性は低くなる。そこで、オーバーサンプリングの手法を採用する。すなわち、１つのパタンを複数のパタンとして扱う。但し、複数のパタンのそれぞれの最初の要素であるパタン要素０を異なる要素とする。これにより、隠蔽の影響により検索が失敗してしまう可能性が低くなる。
【０１１１】
オーバーサンプリングの手法における複数のパタン（以下、オーバーサンプリングパタンと称する）からのパタン要素０の決定は次のように行われる。すなわち、オーバーサンプリングパタンの数の削減を目指し、オーバーサンプリングパタンのパタン要素０を、対象データに含まれている可能性が高い要素にする。例えば、３Ｄ点から出来ているパタンの場合は、オーバーサンプリングパタンのパタン点０を、出来るだけ沢山の方向から見えるパタン点にすれば良い。また、パタンリンク法（以下で説明する）にて形の相似を利用し、出来るだけ他の部分に似ている部分の中心に近い点をパタン点０とするようにしてもよい。さらに、マッチングフェースで場所が違えばすぐにスコアが移動閾値を下回るように、出来るだけ特殊な形の部分の中心に近い点をパタン点０とするようにしてもよい。
【０１１２】
また、３Ｄパタンの場合は、計測器（例えばカメラや距離センサー）とワークの位置関係により、対象データに穴や隠蔽があることがある。これを配慮しないと、仮に綺麗な計測データがあっても、スコアが下がって、安定した検索が不可能になる。この場合、計測器とワークの位置関係依存のパタンを定義する。すなわち、パタンの中に沢山の視点パタンを設ける。より詳細には、計測器とワークの位置関係をサンプリングして隠蔽のない３Ｄパタンから見える部分を計算して視点パタンに保存する。
【０１１３】
また変換係数Ｔによって視点パタンが選択されるようにすることもできる。すなわち、変換係数Ｔと計測器位置Ｐから暫定の位置関係を計算し、その位置関係に最も近い位置関係の視点パタンを選択することができる。
【０１１４】
また、オーバーサンプリングパタンの導入により、パタンの数が増えて実行時間が長くなってしまうこともある。仮に、複数のパタンでパタン要素０の周りが似れば、それを１回だけマッチングすれば十分のはずである。
【０１１５】
仮に、視点パタン１のオーバーサンプリングパタン２の要素０〜要素１０が視点パタン３のオーバーサンプリングパタン４の要素０〜要素１０とほとんど同じだとする。視点パタン１のオーバーサンプリングパタン２から視点パタン３のオーバーサンプリングパタン４の間の変換Ｇが計算される。視点パタン３のオーバーサンプリングパタン４を祖サーチの中でパタン要素０から使わないようにする。祖サーチで視点パタン１のオーバーサンプリングパタン２でパタン要素１０までマッチングされたポーズがあれば、そのポーズに計算した変換Ｇをかけて、祖サーチの中で視点パタン３のオーバーサンプリングパタン４でもマッチングを続けるようにする。すなわち、視点パタン１のオーバーサンプリングパタン２のパタン要素インデックス１０に視点パタン３のオーバーサンプリングパタン４へのリンクが付けられ、そのリンクに対応付けて計算した変換Ｇが保存される。
【０１１６】
なお、以上においては、図２のステップＳ１１または図４のステップＳ５１で入力される変換係数リストについて言及しなかったが、その作成方法について説明する。例えば、検索空間が３次元空間の場合は、３Ｄ回転空間とスケールはサンプリングされる。移動量Ｖは０に初期化され、実際にマッチングの時に（図２のステップＳ１７または図４のステップＳ５７）パタン要素０の３Ｄ座標と対象データの対応する要素の３Ｄ座標から移動量Ｖが計算される。このように得られたパラメータにより変換係数リストが作成される。サンプリングの刻みを大きくすることができたので、リストの長さが短くなる。
【０１１７】
更に、実行時間を改良するためピラミッドの概念を導入する事が可能である。マルチレベルピラミッドとして、パタンの要素群と対象データの要素群をサブサンプリングして、ピラミッドを作成する。祖サーチは、ピラミッドのうち、圧縮率が高いレベルで実行される。精サーチは、各ポーズを圧縮率が高いレベルから段々に圧縮率が低いレベルまで検索される。ピラミッドレベルを変える時にポーズのフィルタリングを行う事ができる。例えば、ほとんど同じポーズがあれば（たとえば、変換係数の移動量等、間の角度をみて、あれが近いと判断したら消す）、その中で一番スコアの高いポーズ以外のポーズを削除する。
【０１１８】
以上のように、サンプリングの刻みをできるだけ大きくして、実行時間を短くしながら、解答を見つけることができる。
【０１１９】
上述した一連の処理は、ハードウェアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、プログラム記録媒体からインストールされる。
【０１２０】
図５は、上述した一連の処理をプログラムにより実行するコンピュータのハードウェアの構成例を示すブロック図である。
【０１２１】
コンピュータにおいて、CPU（Central Processing Unit）１０１，ROM（Read Only Memory）１０２，RAM（Random Access Memory）１０３は、バス１０４により相互に接続されている。
【０１２２】
バス１０４には、さらに、入出力インタフェース１０５が接続されている。入出力インタフェース１０５には、キーボード、マウス、カメラなどよりなる入力部１０６、ディスプレイ、スピーカなどよりなる出力部１０７、ハードディスクや不揮発性のメモリなどよりなる記憶部１０８、ネットワークインタフェースなどよりなる通信部１０９、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア１１１を駆動するドライブ１１０が接続されている。
【０１２３】
以上のように構成されるコンピュータでは、CPU１０１が、例えば、記憶部１０８に記憶されているプログラムを、入出力インタフェース１０５及びバス１０４を介して、RAM１０３にロードして実行することにより、上述した一連の処理が行われる。
【０１２４】
コンピュータ（CPU１０１）が実行するプログラムは、例えば、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory),DVD(Digital Versatile Disc)等）、光磁気ディスク、もしくは半導体メモリなどよりなるパッケージメディアであるリムーバブルメディア１１１に記録して、あるいは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供される。
【０１２５】
そして、プログラムは、リムーバブルメディア１１１をドライブ１１０に装着することにより、入出力インタフェース１０５を介して、記憶部１０８に記憶することで、コンピュータにインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部１０９で受信し、記憶部１０８に記憶することで、コンピュータにインストールすることができる。その他、プログラムは、ROM１０２や記憶部１０８にあらかじめ記憶しておくことで、コンピュータにあらかじめインストールしておくことができる。
【０１２６】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０１２７】
また、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。また、式（１）〜式（３１）は３Ｄパタンを３Ｄ対象データから検索する場合使用出来る式だが、本発明は式（１）〜式（３１）の使用に限定されていない、また３Ｄパタンを３Ｄ対象データから検出する場合に限定されるものではない。変換係数とパタンの要素から出来ている空間から、対象データの要素の空間への変換関数がある場合、そして検索範囲が限られているなら、本発明にてパタンを対象データから検出する事が可能である。また、パタンを構成する要素群は、複数の種類の要素が使われる事が可能である。同じ様に、対象データを構成する要素群は、複数の種類の要素が使われる事が可能である。例えば、３Ｄパタンの場合、パタンが面を表すノーマルベクトル付の３次元点群と縁を表す３Ｄ点群で構成されている場合、それらの要素の種類に基づいて、対応要素検索や対応関係効果計算が行われる。
【符号の説明】
【０１２８】
１１…移動閾値計算部、１２…変換係数計算部、１３…初期値設定部、１４…対応点検索部、１５…スコア更新部、１６…パラメータ／変換係数更新部、１７…ポーズリスト生成部、３１…判定部、１０１…CPU、１０２…ROM、１０３…RAM、１０８…記憶部、１１１…リムーバブルメディア
【図１】
0005476343.tif 000034
【図２】
0005476343.tif 000035
【図３】
0005476343.tif 000036
【図４】
0005476343.tif 000037
【図５】
0005476343.tif 000038