"比較対象の特徴量に対応する第1のインデックスの次元を削減して第2のインデックスを生成するための変換行列を形成する方法であって、標準データベースに含まれる標準対象の特徴量に対応する前記第1のインデックスにつきガウスカーネル行列を求めるステップと、前記ガウスカーネル行列を正規化するステップと、前記正規化されたガウスカーネル行列から異方性遷移カーネル行列を求めるステップと、を含む、ことを特徴とする変換行列の形成方法。前記ガウスカーネル行列Wは次のようにあらわされ、ただし、Wi,jは行列の要素、||Xi-Xj||2はサンプル点Xi,Xjのユークリッド距離、σはカーネル幅を表わすパラメータである、前記ガウスカーネル行列の正規化は次のように行なわれ、ここでDは、であり、前記異方性遷移カーネル行列は次のようにして求められる、ここで、である、ことを特徴とする請求項1に記載の変換行列の形成方法。被検索対象データベースに含まれる被検索対象につき夫々の特徴量に対応する第1のインデックスD-1を第1の方法により特定するステップと、前記被検索対象の第1のインデックスD-1の次元を請求項1又は請求項2に記載の方法により得られた変換行列により削減して、第2のインデックスD-2を特定するステップと、検索対象につきその特徴量に対応する第1のインデックスC-1を前記第1の方法により特定し、前記特定された検索対象の第1のインデックスC-1の次元を前記変換行列により削減して、第2のインデックC-2を特定するステップと、前記検索対象の第2のインデックスC-2を前記データベースに含まれる各被検索対象の第2のインデックスD-2と比較するステップと、を含むデータ検索方法。前記被検索対象及び前記検索対象は三次元モデルであり、前記第1の方法はMFSD法である、ことを特徴とする請求項3に記載のデータ検索方法。比較対象の特徴量に対応する第1のインデックスの次元を削減して第2のインデックスを生成するための変換行列を形成する装置であって、標準データベースに含まれる標準対象の特徴量に対応する前記第1のインデックスにつきガウスカーネル行列を求める手段と、前記ガウスカーネル行列を正規化する手段と、前記正規化されたガウスカーネル行列から異方性遷移カーネル行列を求める手段と、を含む、ことを特徴とする変換行列の形成装置。前記ガウスカーネル行列Wは次のようにあらわされ、ただし、Wi,jは行列の要素、||Xi-Xj||2はサンプル点Xi、Xjのユークリッド距離、σはカーネル幅を表わすパラメータである、前記ガウスカーネル行列の正規化は次のように行なわれ、ここでDは、であり、前記異方性遷移カーネル行列は次のようにして求められる、ここで、である、ことを特徴とする請求項5に記載の変換行列の形成装置。被検索対象データベースに含まれる被検索対象につき夫々の特徴量に対応する第1のインデックスD-1を第1の方法により特定する手段と、前記被検索対象の第1のインデックスD-1の次元を請求項5又は請求項6に記載の装置により得られた変換行列により削減して、第2のインデックスD-2を特定する手段と、検索対象につきその特徴量に対応する第1のインデックスC-1を前記第1の方法により特定し、前記特定された検索対象の第1のインデックスC-1の次元を前記変換行列により削減して、第2のインデックC-2を特定し、前記検索対象の第2のインデックスC-2を前記データベースに含まれる各被検索対象の第2のインデックスD-2と比較する手段と、を備えるデータ検索装置。前記被検索対象及び前記検索対象は三次元モデルであり、前記第1の方法はMFSD法である、ことを特徴とする請求項7に記載のデータ検索装置。比較対象の特徴量に対応する第1のインデックスの次元を削減して第2のインデックスを生成するための変換行列を形成するためのコンピュータプログラムであって、コンピュータを、標準データベースに含まれる標準対象の特徴量に対応する前記第1のインデックスにつきガウスカーネル行列を求める手段と、前記ガウスカーネル行列を正規化する手段と、前記正規化されたガウスカーネル行列から異方性遷移カーネル行列を求める手段と、として機能させる、ことを特徴とするコンピュータプログラム。前記ガウスカーネル行列Wは次のようにあらわされ、ただし、Wi,jは行列の要素、||Xi-Xj||2はサンプル点Xi、Xjのユークリッド距離、σはカーネル幅を表わすパラメータである、前記ガウスカーネル行列の正規化は次のように行なわれ、ここでDは、であり、前記異方性遷移カーネル行列は次のようにして求められる、ここで、である、ことを特徴とする請求項9に記載の変換行列の形成装置。データ検索のためのコンピュータプログラムであって、コンピュータを、被検索対象データベースに含まれる被検索対象につき夫々の特徴量に対応する第1のインデックスD-1を第1の方法により特定する手段と、前記被検索対象の第1のインデックスD-1の次元を請求項5又は請求項6に記載の装置により得られた変換行列により削減して、第2のインデックスD-2を特定する手段と、検索対象につきその特徴量に対応する第1のインデックスC-1を前記第1の方法により特定し、前記特定された検索対象の第1のインデックスC-1の次元を前記変換行列により削減して、第2のインデックC-2を特定し、前記検索対象の第2のインデックスC-2を前記データベースに含まれる各被検索対象の第2のインデックスD-2と比較する手段と、として機能させる、ことを特徴とするコンピュータプログラム。前記被検索対象及び前記検索対象は三次元モデルであり、前記第1の方法はMFSD法である、ことを特徴とする請求項11に記載のコンピュータプログラム請求項9~請求項12のいずれかに記載のコンピュータプログラムを記録する記録媒体。三次元物体モデルのMFSD特徴量は3500程度の次元をもつインデックスで表わされる。かかる高次元のインデックスをベースに比較を実行するには、処理装置に大きな記憶容量が要求され、また比較のための演算にも長時間を要する。そこでインデックスの次元を削減する必要があり、従来より、主成分分析や特異値分解を用いてインデックスの次元を削減することが提案されている。かかるインデックスの次元削減方法によれば、確かにデータ数が圧縮されるので処理装置にかかる負担が小さくなり、短時間での演算が可能になる。しかしながら、検索の精度の点に不安があった。そこでこの発明は比較対象の特徴量のインデックスを削減する新たな方法を提案する。この発明の第1の局面は次のように規定される。即ち、比較対象の特徴量に対応する第1のインデックスの次元を削減して第2のインデックスを生成するための変換行列を形成する方法であって、標準データベースに含まれる標準対象の特徴量に対応する前記第1のインデックスにつきガウスカーネル行列を求めるステップと、前記ガウスカーネル行列を正規化するステップと、前記正規化されたガウスカーネル行列から異方性遷移カーネル行列を求めるステップと、を含む、ことを特徴とする変換行列の形成方法。この発明の第1の局面の方法により得られる変換行列を用いると、被比較対象の特徴量に対応する第1のインデックスの次元が削減される。次元の削減された第2のインデックスに基づき比較を実行することにより、処理装置の負担が軽減される。更には、実施例に示すとおり、MFDS特徴量に関してはその検索精度も向上した。第1の局面で規定する変換行列の適用はMFDS特徴量のインデックスのみに限定されるものではなく、その他各種のデータ二次元図形データ、テキストデータ等にも適用可能である。変換行列を求めるアルゴリズムについて更に詳細に説明する。1線形次元削減例:主成分分析による次元削減n次元のm個の点X=[x1,x2,,xm]∈Rnが与えられた、と仮定する。一般的な線形次元削減の問題は、これらm個の点をd次元の点Y=[y1,y2,,ym]∈Rdd≪nへと射影する変換行列Fを求めることであり、Y=FTXと表せる。多様体学習における線形次元削減は、Xがn次元の非線形の多様体Mnにある場合の問題となる。2線形拡散射影による次元削減のアルゴリズム線形拡散射影のアルゴリズムは以下の通りである。ステップ1ガウスカーネル行列の計算ガウスカーネル行列Wを求める。この求め方は、行列の要素Wijを以下のように決める。サンプル点xiとxjとのユークリッド距離、カーネルの幅を表すパラメータσから、以下の数式でもとめられる。ステップ2カーネル行列の正規化以下のようにして、ガウスカーネル行列を正規化する。ここでDは、である。ステップ3異方性遷移カーネル行列の計算異方性遷移カーネル行列を、以下のようにして求める。ここで、である。ステップ4固有値分解固有値をλ、それに対応する固有ベクトルをfとして以下の固有値問題を解く。固有値に対応するd個の固有ベクトルfから、n×dの変換行列Fを求める。ここでyiは、xiを次元削減したd次元のベクトルである。上記のアルゴリズムを予め準備された標準データベースに含まれる標準対象の特徴量に対して実行して変換行列Fを準備する。標準データベースに含まれる標準対象は、検索対象クエリとなることが予想される対象と同種の対象において任意に選択できる。ここに同種の対象とは、その特徴量が同一のインデックスで特定できるものいう。例えば、検索対象が三次元物体モデルであれば標準対象も三次元物体モデルである。標準データベースに含まれる標準対象はアトランダムに選択することができる。例えば、三次元物体が比較対象であるとき、標準データベースに含まれる標準対象として自動車、家、機械部品、テレビ、おもちゃ等、相互の関連性のない三次元物体の形状を選択することができる。検査対象クエリ及び被検索対象データベースが予め限定されているとき、例えば、検索対象が椅子であり、検索対象データベースが家具のときは、標準データベースに含ませるべき標準対象を椅子及び/又は家具に限定することもできる。このような場合には、被検索対象データベースから標準データベースに含ませるべき標準対象を任意に又はアトランダムに抽出することができる。標準データベースに含ませるべき標準対象の数は、変換行列の実行により得られる第2のインデックスの次元の数以上とすることが好ましい。検索対象データベースに含まれるデータ数によっては処理装置が処理可能な範囲内において、検索対象データベース自体を標準データベースとして使用することもできる。このようにして得られた変換行列Fを検索対象の特徴量に対応する第1のインデックスC-1に掛け合わせてより次元の小さい第2のインデックスC-2を求める。同様にして、変換行列Fを被検索対象データベースに含まれる全ての被検索対象の特徴量に対応する第1のインデックスD-1に掛け合わせてより次元に小さい第2のインデックスD-2を求める。検索対象の第2のインデックスC-2と各被検索対象の第2のインデックスD-2とを比較する。このように次元数の小さいインデックスどうしでの比較により、検索システム処理装置にかかる負担が小さく、検索時間も短縮される。上記のインデックス削減方法、即ち変換行列Fを三次元物体モデルの検索に適用した例を以下に説明する。図1は三次元物体モデルの検索装置1の構成を示すブロック図である。検索システムのハードディスク等により構成される標準データベース3に任意のデータベースを保存可能である。MFSD特徴量特定部5は標準データベースに含まれる三次元物体の特徴量を、MFSD法に基づき特定する。ここに、特定されたMFSD特徴量は3584の次元を有する第1のインデックスS。変換行列作成部7では線形拡散射影を用いた既述のアルゴリズム1~4を実行し、変換行列Fを特定する。この変換行列Fを第1のインデックス3584次元に掛け合わせると次元数が約1/10に圧縮された第2のインデックス350次元が得られる。被検索対象データベース13には既知の三次元物体の形状が保存され、各三次元物体についてMFSD特徴量特定部15によりそのMFSD特徴量第1のインデックスD-1が特定され、図示しないメモリに保存される。次元削減部18では各三次元物体のMFSD特徴量第1のインデックスD-1へ変換行列Fが掛け合わされる。これにより、3584次元の第1のインデックスD-1が350次元の第2のインデックスに変換される。この第2のインデックスも図示しないメモリへ保存される。ユーザにより指定された検索対象20のMFSD特徴量第1のインデックスC-1がMFSD特徴量特定部25で特定され、更に、次元削減部28において変換行列Fが掛け合わされる。これにより、3584次元の第1のインデックスC-1が350次元の第2のインデックスC-2に変換される。比較手段としての距離計算部30では、検索対象の第2のインデックスC-2と被検索データベースの各検索対象の第2のインデックスD-2とのマンハッタン距離が比較され、その距離が小さいものから類似性が高いと評価される。図1のシステムの有効性を確認するため、被検索対象データベースとして、PrincetonShapeBenchmarkTestSetsPSB、Konstanz3DObjectDatabaseKOD、NTU3DModelBenchmarkNMB、McGillShapeBenchmarkMSB、EngineeringShapeBenchmarkESBの5種類の三次元物体データベースを準備した。また、標準データベースにはNationalTaiwanUniversity3DModelDatabaseNTU用いた。NTUには10,911個の未分類の三次元物体が含まれている。ここからランダムに選択した5,000個の三次元物体を訓練データとして使用した。検索対象には各被検索対象デーベースに含まれるもの全てを選択し、各被検索対象データベースごとにマイクロ平均をとった。検索精度の評価尺度には、FirstTier1-Tier、SecondTier2-Tier、NearestNeighborNN、DiscountedCumulativeGainDCG、および再現率Recall、適合率Precisionを用いた。ここで、1-Tier、2-Tierは、検索結果上位での検索精度を示す値である。1-Tier、2-Tier、NN、DCGは値が大きいほど検索精度が高く、再現率-適合率のグラフではカーブが右上に近づくほど検索精度が高い。各評価尺度は、各検索対象三次元物体の評価尺度の平均を、全体の平均評価尺度とするマイクロ平均で表す。クラスごとに評価尺度の平均を計算し、それらの平均を全体の平均評価尺度とするマクロ平均では、各クラスが少数の三次元物体で構成される場合に、評価尺度の計算結果に偏りが生じる。評価実験に使用する三次元物体データベースは、いずれも、各クラスが少数の三次元物体で構成されるためマイクロ平均を選択した。2パラメータの設定この発明にかかる線形拡散射影LDPは、カーネルの近傍幅を表すパラメータσを持つ。他手法との比較実験を行う前に、パラメータσの最適値を、テストデータベースにPrincetonShapeBenchmarkTestSetsPSBを用いて、実験により求めた。MFSDにおいて、正対処理にPointSVDを用いたデプスバッファ特徴量をLDPを用いて100次元に次元削減し、評価尺度1-Tierが最大となるパラメータ値を求めた。線形拡散射影はガウスカーネルの近傍幅σがパラメータとなるσを{1.0,2.0,...,10.0}と変化させて最適値を求めた。実験結果から、σ=4としたものが41.5ともっとも高い検索精度となった。また、遷移確率行列Pを用いた場合では13.4となった。異方性遷移カーネルを導入する有効性がわかった。3次元削減数の検討既知の次元削減法であるLocalityPreservingProjectionsLPP、NeighborhoodPreservingEmbeddingNPE、IsometricProjectionsISOはパラメータとして近傍数をもつ。さらに、重みにガウスカーネルを選択したLPPではパラメータとして近傍幅σをもつ。近傍数を{10,20,...}と変化させて最適値を求めた。また、σを{1.0,2.0,...,10.0}と変化させて最適値を求めた。LPPは近傍数を10、近傍幅σのガウスカーネルを重みに選択したものが28.57と最も高い検索精度となった。また、LPPは近傍数を大きくするほど検索精度が低下した。NPEの近傍数は110、120と大きくしていくごとに検索精度が高くなり、近傍数360で41.0と最も高い検索精度となった。ISOでは、近傍数を90としたものが28.46と最も高い検索精度となった。以降の実験ではパラメータにこれら最適値を使用する。各特徴量において、次元削減数を{10,20,...,150}と変化させ、評価尺度1-Tierが最大となる値を求めた。各特徴量の正対処理にはPointSVDを用いた。被検索対象データベース、標準データベースは2と同様である。最も高い検索精度を得た次元削減数は表1に示すように、デプスバッファ特徴量で120次元、シルエット特徴量で100次元、輪郭特徴量で70次元、ボクセル特徴量で60次元となった。4様々なデータベースでの検索精度の比較複数の検索対象データベースで、LDPで次元削減した特徴量と、次元削減を行わない元の特徴量MFSD、PCA、LPP、NPE、ISOで次元削減した特徴量とで検索精度の比較実験を行った。標準データベースは2と同じものを用いた。次元削減数やパラメータについては実験で最も高い検索精度を得られた値を用いた。4-APrincetonShapeBenchmarkTestSetsPSBPSBは人間、自動車、植物などの特定の分野に偏らない907個の三次元物体が90個のクラスに分類されている。三次元物体の形状類似検索の研究において、基本的な検索性能を評価するベンチマークとして、広く用いられている。図2は、PSBにおける各次元削減手法での検索精度を再現率-適合率の曲線で表したものである。LDPで次元削減したものが、最も高い検索精度となった。また、LDP、PCA、NPEでは次元削減しないMFSDよりも高い検索精度を得た。再現率{0.05,0.10,...,1.0}での平均適合率は次元削減しないMFSDが0.5564なのに対し、次元削減したものはLDPで0.5983、PCAで0.5667、LPPで0.5155、NPEで0.5896、ISOで0.5471となった。表2は、PSBにおける各次元削減手法での検索精度を1-Tier、2-Tier、NN、DCGで表したものである。全ての評価尺度で、LDPで次元削減したものが最も高い検索精度となった。また、LDPで次元削減したものが次元削減しないMFSDよりも高い検索精度となった。LDPによる次元削減が、他の手法に比べ、MFSDがなす非線形構造をとらえ次元削減できたと考える。4-BKonstanz3DObjectDatabaseKODKODは、Bustosらの研究で評価実験に用いられたデータベースである。473個の三次元物体が55個のクラスに分類されている。PSBと同様に、データベースに含まれる三次元物体は特定の分野によらず基本的な検索性能を評価することができる。図3は、KODにおける各次元削減手法での検索精度を再現率-適合率の曲線で表したものである。LDPで次元削減したものが最も高い検索精度となった。また、LDPで次元削減したものは次元削減しないMFSDよりも高い検索精度を得た。平均適合率は、次元削減しないMFSDが0.7278なのに対し、次元削減したものは、LDPで0.7578、PCAで0.7263、LPPで0.6910、NPEで0.7443、ISOで0.7216となった。表3は、KODにおける各次元削減手法での検索精度を1-Tier、2-Tier、NN、DCGで表したものである。全ての評価尺度で、LDPで次元削減したものが、最も高い検索精度となった。また、LDPで次元削減したものは、次元削減しないMFSDにくらべ、検索精度が向上した。4-CNTU3DModelBenchmarkNMBNMBは、Chenらの研究で評価実験に用いられたデータベースである。549個の物体が47個のクラスに分類されている。PSBと同様に特定の分野への偏りがないため、基本的な検索性能を評価できる。また、標準データベースに用いたNationalTaiwanUniversity3DModelDatabaseとは、異なるデータベースである。図4は、NMBにおける各次元削減手法での検索精度を再現率-適合率の曲線で表したものである。LDPで次元削減したものが他の次元削減手法で次元削減したものよりも高い検索精度となった。平均適合率は、次元削減しないMFSDが0.5439なのに対し、次元削減したものはLDPで0.5464、PCAで0.5282、LPPで0.4952、NPEで0.5371、ISOで0.5109となった。表4は、NMBにおける、各次元削減手法での検索精度を1-Tier、2-Tier、NN、DCGで表したものである。1-Tier、NNでは次元削減しないMFSDが、2-Tier、DCGではLDPで次元削減したものが、それぞれ最も高い検索精度となった。LDPでは、次元削減したものが他の次元削減手法に比べ高い検索精度となった。PSB、KODでの実験結果とあわせて、LDPで次元削減することで、基本的な検索精度が向上することがわかる。4-4McGill3DShapeBenchmarkMSBMSBは、ボクセル化された457個の三次元物体が19個のクラスに分類されているデータベースである。PSBが馬クラス犬クラスと分類されているのに対し、MSBでは四本足の動物は全て同じ四本足動物クラスに分類されるなど、他のデータベースと比較すると、多少、大雑把なクラス分類となっている。図5は、MSBにおける各次元削減手法での検索精度を再現率-適合率の曲線で表したものである。LDPで次元削減したものが最も高い検索精度となった。また、LDP、PCAで次元削減したものは、次元削減しないMFSDよりもそれぞれ高い検索精度を得た。平均適合率は、次元削減しないMFSDが0.6010なのに対し、次元削減したものは、LDPで0.6493、PCAで0.6132、LPPで0.5130、NPEで0.6309、ISOで0.5370となった。表5は、MSBにおける各次元削減手法での検索精度を1-Tier、2-Tier、NN、DCGで表したものである。全ての評価尺度で、LDPで次元削減したものが最も高い検索精度となった。また、LDP、PCAにより次元削減したものは、全ての評価尺度で、次元削減しないMFSDにくらべ検索精度が向上した。4-EEngineeringShapeBenchmarkESBESBは、801個の三次元物体が42個のクラスに分類されているデータベースである。機械部品の三次元物体から構成され、3DCADにおける部品検索などの応用における検索精度を評価することができる。図6は、ESBにおける各次元削減手法での検索精度を再現率-適合率の曲線で表したものである。LDPで次元削減したものが他の次元削減手法で次元削減したものよりも高い検索精度となった。平均適合率は、次元削減しないMFSDが0.5683なのに対し、次元削減したものは、LDPで0.5715、PCAで0.5625、LPPで0.5360、NPEで0.5694、ISOで0.5396となった。表6は、ESBにおける、各次元削減手法での検索精度を、1-Tier、2-Tier、NN、DCGで表したものである。1-Tierでは、NPEで次元削減したものが、2-Tierでは、次元削減しないMFSDが、NN、DCGでは、LDPで次元削減したものが、最も高い検索精度となった。また、全ての評価尺度でLDPで次元削減したものが他の次元削減手法に比べ高い検索精度となった。自動車製造業に代表される機械部品の製造業では、三次元物体の形状モデルを三次元CAD/CAMシステムで製作するのが通常業務として行われている。また、建設業界でも建物の外観内装や建物周辺の風景を建立前にCGを使ってシミュレーションするために、三次元の建物モデル、部屋のモデル、家具や樹木などのモデルを作成することが広く行われている。さらに、アニメーションや映画、コマーシャルフィルムなどの作成にも、今では三次元CG技術は欠かせないものとなっている。しかしながら、このような応用分野で、精緻な三次元モデルを最初に作成する場合、2次元の図形描画よりもはるかに多くの労力と時間を要する。そこで、これらの応用分野で、一度人手や三次元スキャナなどの補助手段で入力し作成した三次元モデルを、三次元物体モデルデータベースに保存しておき、類似した三次元物体の形状モデルを作成する場合に、類似した形状の物体モデルを再利用することで大幅なコスト削減がはかれると考えられる。本発明は、このような環境下で、作成したい三次元形状に類似した三次元物体を、三次元モデルデータベースから、できるだけ正確に検索でき、かつ検索用のインデックスを提案手法の線形拡散射影で次元削減し、圧縮することで、実用的な三次元物体形状の検索エンジンとしての利用を可能とするものである。この発明は、上記発明の実施の形態及び実施例の説明に何ら限定されるものではない。特許請求の範囲の記載を逸脱せず、当業者が容易に想到できる範囲で種々の変形態様もこの発明に含まれる。"