(57)【要約】【課題】　三次元物体の安定的、汎用的な形状比較技術はほとんどないといってよい。【解決手段】　形状解析器１０は、オブジェクトの三次元データを入力する。点集合生成器１４は、三次元データ上に注目すべき点を設定する。モース評価器はこれらの点のモース値を検出し、その結果に応じてＭＲＧ生成器１８が多重解像度の位相グラフを生成する。モース関数はオブジェクトの幾何操作に対して不変になるよう定義され、オブジェクトの姿勢に関係なくオブジェクト間の形状の近さが計算される。【選択図】　　　　図１６
2004118876.tif 000002
【特許請求の範囲】
【請求項１】
　オブジェクトの形状を表す三次元データを受け取るインタフェイスと、
　受け取られた三次元データの中で、処理すべき複数の点を定義する点集合生成器と、
　定義にされた点について、オブジェクトに対する所定の幾何的操作について不変となるよう選択されたモース関数のモース値を得る評価器と、
　得られたモース値に基づいて、三次元データの大域的な位相グラフを生成するグラフ生成器と、
　を含むことを特徴とする形状解析器。
【請求項２】
　前記位相グラフはノード間を結び付けるエッジを含み、
　前記ノードは、モース値を使用しオブジェクトを分割することにより定義される各領域に対し与えられる請求項１に記載の形状解析器
【請求項３】
　前記位相グラフはノード間を結び付けるエッジを含み、
　それらノードはモース関数の特異点に対して与えられる請求項１に記載の形状解析器。
【請求項４】
　前記幾何的操作は回転を含む請求項１に記載の形状解析器。
【請求項５】
　前記モース関数はオブジェクトの変形に対し敏感でないように選択される請求項１に記載の形状解析器。
【請求項６】
　前記三次元データはメッシュデータであり、
　前記モース関数はメッシュを形成するエッジの長さを利用して定義される請求項１に記載の形状解析器。
【請求項７】
　前記グラフ生成器によって生成される第一のオブジェクトの第一の大域的な位相グラフと、第二のオブジェクトの第二の大域的な位相グラフとの近似を、所定の近似判断基準に基づき計算するプロセッサを含む請求項１に記載の形状解析器。
【請求項８】
　前記グラフ生成器は、三次元データのトポロジに着目した計算結果に基づき、オブジェクトの大域的な位相グラフを多重化された解像度にわたり生成する請求項１に記載の形状解析器。
【請求項９】
　前記グラフ生成器は、粗いレベルの大域的な位相グラフを生成する場合、オブジェクトを複数の領域に粗く分割し、前記領域と前記グラフのノードを関連付ける請求項８に記載の形状解析器。
【請求項１０】
　前記グラフ生成器は、細かなレベルのグラフの細部を削除することにより、粗いレベルの大域的な位相グラフを生成する請求項８に記載の形状解析器。
【請求項１１】
　前記グラフ生成器により生成される第１のオブジェクトの第１の大域的な位相グラフと、第２のオブジェクトの第２の大域的な位相グラフの近似度を解像度レベルの中で計算するプロセッサを含む請求項８に記載の形状解析器。
【請求項１２】
　オブジェクトの形状を表す三次元データを受け取るインタフェイスと、
　受け取られた三次元データに対して適用される、トポロジを考慮した計算結果に基づいてオブジェクトの複数の解像度レベルにわたる大域的な位相グラフを生成するグラフ生成器と、
　を含むことを特徴とする形状解析器。
【請求項１３】
　前記グラフ生成器は、三次元データに含まれる特異点を探索し、探索された特異点を用いて細かなレベルのグラフのノードを定義することにより、細かなレベルの大域的な位相グラフを生成する請求項１２に記載の形状解析器。
【請求項１４】
　前記グラフ生成器は、粗いレベルの大域的な位相グラフを生成する場合、オブジェクトを複数の領域に粗く分割し、それらの領域をグラフの要素に関連付ける請求項１２に記載の形状解析器。
【請求項１５】
　前記グラフ生成器は、細かなレベルのグラフの細部を削除することによって、粗いレベルの大域的な位相グラフを生成する請求項１２に記載の形状解析器。
【請求項１６】
　グラフ生成器によって生成された第１のオブジェクトの第１の大域的な位相グラフと、第２のオブジェクトの第２の大域的な位相グラフとの間の近似度を、所定の基準に基づき、解像度レベルの中で計算するプロセッサを含む請求項１２に記載の形状解析器。
【請求項１７】
　オブジェクトの形状を表す三次元データの大域的な位相グラフを入力するグラフインタフェイスと、
　前記グラフインタフェイスを通して入力される第１のオブジェクトの第１の大域的な位相グラフと第２のオブジェクトの第２の大域的な位相グラフを保存するワークメモリと、
　所定の近似判断基準に基づいて前記ワークメモリに保存された第１および第２の大域的な位相グラフの近似度を計算するプロセッサと、
　を含むことを特徴とする形状解析器。
【請求項１８】
　前記プロセッサは、近似度評価のため第１および第２の大域的な位相グラフの要素間の対応を探索し、前記探索された対応している要素間のマッチングを計算する請求項１７に記載の形状解析器。
【請求項１９】
　前記要素は、第１および第２の大域的な位相グラフのノード含む請求項１８に記載の形状解析器。
【請求項２０】
　前記プロセッサは、探索された対応しているノードの属性間のマッチングを計算する請求項１９に記載の形状解析器。
【請求項２１】
　前記属性は、第１および第２の大域的な位相グラフに対する所定の幾何操作に対して敏感でないように選ばれる請求項２０に記載の形状解析器。
【請求項２２】
　前記位相グラフは回転に不変であるように生成される請求項２１に記載の形状解析器。
【請求項２３】
　前記プロセッサは、第１および第２の大域的な位相グラフに含まれるノードの属性に基づいて近似度を計算する請求項１７に記載の形状解析器。
【請求項２４】
　前記プロセッサは、第１および第２の大域的な位相グラフの種数に基づいて近似度を計算する請求項１７に記載の形状解析器。
【請求項２５】
　前記プロセッサは、第１と第２の大域的な位相グラフの近似度を複数の解像度レベルにおいて計算する請求項１７に記載の形状解析器。
【請求項２６】
　前記プロセッサは、第１と第２の大域的な位相グラフの各解像度レベルに含まれるノードの属性に基づく計算を行う請求項２５に記載の形状解析器。
【請求項２７】
　前記プロセッサは、第１および第２の大域的な位相グラフの各解像度レベルにおける種数に基づいて近似度を計算する請求項２５に記載の形状解析器。
【請求項２８】
　オブジェクトの形状を表す３次元データを取得するインタフェイスと、
　オブジェクトに対する所定の幾何操作に対して不変となるモース関数の値に基づき前記３次元データを複数の領域に分割し、それらの領域をグラフのノードと関連付けることによりオブジェクトの大域的な位相グラフを生成するグラフ生成器と、
　を含むことを特徴とする形状解析器。
【請求項２９】
　オブジェクトの形状を表す３次元データを受け取る工程と、
　受け取られた３次元データの中で処理の対象とすべき複数の点を定義する工程と、
　前記定義された点におけるオブジェクトに対する所定の幾何操作について不変となるよう選ばれたモース関数のモース値を評価する工程と、
　評価されたモース値に基づき３次元データの大域的な位相グラフを生成する工程と、
　を含むことを特徴とする形状解析方法
【請求項３０】
　生成された第１のオブジェクトの第１の大域的な位相グラフと、第２のオブジェクトの第２の大域的な位相グラフの近似度を、所定の近似判断基準に基づいて評価する工程を含む請求項２９に記載の形状解析方法。
【請求項３１】
　３次元データに適用されたトポロジ処理計算に基づいて、オブジェクトの複数の解像度にわたる大域的な位相グラフが生成される請求項２９に記載の形状解析方法。
【請求項３２】
　生成された第１および第２の大域的な位相グラフの近似度を所定の近似判断基準に基づいて評価する工程を含むことを特徴とする請求項３１に記載の形状分析方法。
【請求項３３】
　オブジェクトの形状を表す３次元データを受け取る工程と、
　受け取られた３次元データに適用された、トポロジを考慮した計算処理に基づいて複数の解像度にわたるオブジェクトの大域的な位相グラフを生成する工程と、
　を含むことを特徴とする形状解析方法。
【請求項３４】
　粗いレベルの大域的な位相グラフは、前記オブジェクトを複数の領域に分割し、それらの領域を粗いレベルのグラフの要素と関連付けることによって生成される請求項３３に記載の形状解析方法。
【請求項３５】
　生成された第１のオブジェクトの第１の大域的な位相グラフグラフと、第２のオブジェクトの第２の大域的な位相グラフとの間の近似度を所定の基準に基づき前記解像度レベルの中で計算する工程を含む請求項３３に記載の形状分析方法。
【請求項３６】
　オブジェクトの形状を表す３次元データの大域的な位相グラフであって、所定の幾何操作に対し不変となるよう生成されているものを受け取る工程と、
　受け取られた第１のオブジェクトの第１の大域的な位相グラフと、第２のオブジェクトの第２の大域的な位相グラフとを保存する工程と、
　所定の判断基準に基づいて、保存された第１及び第２の大域的な位相グラフの近似度を評価する工程と、
　を含むことを特徴とする形状解析方法。
【請求項３７】
　第１と第２の大域的な位相グラフの要素間の対応を検出する工程と、前記近似度を評価するために前記検出された対応している要素間のマッチングを計算する工程とを含む請求項３６に記載の形状解析方法。
【請求項３８】
　前記近似度は、解像度レベルの第１と第２の大域的な位相グラフにより評価される請求項３６に記載の形状分析方法。
【請求項３９】
　オブジェクトの形状を表す３次元データを受け取る工程と、
　前記オブジェクトに対する所定の幾何的操作に対し不変であるモース関数の値に基づき、受け取られた３次元データを複数の領域に分割する工程と、
　前記領域を大域的な位相グラフのノードと置き換えることにより前記オブジェクトの位相グラフを生成する工程と、
　を含むことを特徴とする形状解析方法。
【請求項４０】
　サーバとデータベースと少なくともひとつのユーザ端末を含むネットワークシステムであって、
　前記データベースは、商品に関する情報とその商品に関連付けられている形状の大域的な位相グラフを保存するために構築され、
　前記サーバは、マッチングプログラムを利用し、前記データベースにアクセスして商品の形状間のマッチングを評価するものであり、
　前記ユーザ端末は、その端末を使用するユーザが興味を有する商品を前記サーバへ通知し、
　前記サーバは前記データベースを検索し、前記通知された商品と比較的マッチングの程度が高い他の商品を検出し、検出された商品に関する情報を前記ユーザ端末へ送信することを特徴とするネットワークシステム。
【請求項４１】
　オブジェクトの形状を表す３次元データを受け取る機能と、
　受け取られた３次元データの中で処理の対象となる複数の点を定義する機能と、
　前記定義された点におけるオブジェクトに対する所定の幾何操作に対し不変であるように選ばれているモース関数のモース値を評価する機能と、
　前記評価されたモース値に基づき、前記３次元データの大域的な位相グラフを生成する機能と、
　をコンピュータに実行せしめるコンピュータプログラム。
【請求項４２】
　オブジェクトの形状を表す３次元データを受け取る機能と、
　受け取った３次元データに対する、トポロジを考慮した計算処理に基づいて複数の解像度レベルにわたる大域的な位相グラフを生成する機能と、
　をコンピュータに実行せしめるコンピュータプログラム。
【請求項４３】
　オブジェクトの形状を表す３次元データの大域的な位相グラフを受け取る機能と、
　受け取った第１のオブジェクトの第１の大域的な位相グラフと、第２のオブジェクトの第２の大域的な位相グラフとを保存する機能と、
　保存された第１及び第２の大域的な位相グラフの近似度を所定の基準に基づいて評価する機能と、
　をコンピュータに実行せしめるコンピュータプログラム。
【請求項４４】
　オブジェクトの形状を表す３次元データを受け取る機能と、
　前記オブジェクトに対する所定の幾何操作に対し不変であるモース関数の値に基づき前記３次元データを複数の領域に分割する機能と、
　前記領域を大域的な位相グラフのノードと置き換え、前記オブジェクトの位相グラフを生成する機能と、
　をコンピュータに実行せしめるコンピュータプログラム。
【請求項４５】
　オブジェクトの形状を表す３次元データの大域的な位相グラフを入力するグラフインタフェイスと、
　そのグラフインタフェイスを介して入力された３次元データの第１の大域的な位相グラフと、前記グラフインタフェイスを介して入力された他の大域的な位相グラフとの近似度を計算し、前記他のオブジェクトから前記近似度の高い少なくともひとつのオブジェクトを検出するプロセッサと、
　を含むことを特徴とする形状解析器。
【請求項４６】
　前記プロセッサは、前記第１のオブジェクトに関して計算された近似度に基づき他のオブジェクトを配列しなおす請求項４５に記載の形状解析器。
【請求項４７】
　前記近似度は、数値としてスクリーン上に表示される請求項４６に記載の形状解析器。
【請求項４８】
　前記近似度の計算に先立ち、目標とするオブジェクトを示唆するキーワードに基づいて前記他のオブジェクトの範囲が限定される請求項４５に記載の形状解析器。
【請求項４９】
　第１のオブジェクトを指定する工程と、
　第１のオブジェクトの第１の大域的な位相グラフを準備する工程と、
　所定の基準に基づいて、処理されるべきオブジェクトの範囲を制限する工程と、
　前記範囲に存在する目標とするオブジェクトの大域的な位相グラフを準備する工程と、
　準備された第１の大域的な位相グラフと、目標とするオブジェクトの準備された大域的な位相グラフのマッチングを計算する工程と、
　を含むことを特徴とする形状解析方法。
【請求項５０】
　前記範囲の制限は、テキスト情報を用いて行われる請求項４９に記載の形状分析方法。
【請求項５１】
　複数のオブジェクトの形状に基づく情報を準備する工程と、
　マッチングの対象とすべきオブジェクトの範囲を制限するためのテキスト情報を特定する工程と、
　前記テキスト情報によって制限された範囲にあるオブジェクトの間から、形状に基づく情報に基づいて行われるマッチングの結果から互いに近似度の高いオブジェクトを決定する工程と、
　を含むことを特徴とする形状解析方法。
【発明の詳細な説明】
【技術分野】
【０００１】
　この発明は、形状解析技術に関する。この発明は、三次元オブジェクトの形状を解析する装置と方法に関する。
【背景技術】
【０００２】
　近年、モデリングやデジタル化の技術により３次元形状の生成が比較的容易にできるようになった。電子商取引に使用されるデータベースにおいて、３次元オブジェクトの検索を効率よく行うことは非常に重要である。近年の米国民間組織の調査によると、オンラインショッピングにおいて、商品を３次元表示することで従来の２次元及び静止画による表示した場合と比べ、売り上げは数倍になることが明らかになっている。
【０００３】
　インターネットやそれ以外で利用可能な３次元モデルの蓄積が増え続けることにより、大規模データベースから特定のまたは類似のオブジェクトを検索する技術の開発要求が高まってきている。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
　２次元画像を扱う場合、輪郭を認識するために曲率などの形状特性や、色やテクスチャなどの画像特性を利用する方法が提案されている。これらの技術は、２次元マルチメディアデータベースにおいて使用されている。それらデータベースは、以下の文献で詳述されている。"The Query By Image and Video Content: The QBIC System", M.Flickner, H.Sawhney, W.Niblack, J.Ashley, Q.Huang, B.Dom, M.Gorkani, J.Hafner, D.Lee, D.Petkovic, D.Steele and P. Yanker. IEEE Computer, Vol.28, No.9, pp.23-32, September 1995, and in "Fast Multiresolution Image Querying", C.Jacobs, A.Finkelsten and D.Salesin, Proc. SIGGRAPH'95, pp.277-286。
【０００５】
　３次元形状の分野において、表面の輪郭分布を使用する方法は、一般的形状やその姿勢を決定する際良好な結果を示す。これに関し、下記文献に詳述されている。"The Complex EGI: New Representation for 3-D Pose Determination", S.Kang and K.Ikeuchi, IEEE Trans. PAMI,Vol. 15, No. 7, pp. 707-721, July 1993。
【０００６】
　限られた視点から得られる不完全な形のオブジェクトと、あるデータベース中の完全な形の３次元モデルをマッチングさせる技術も存在する。（"A Spherical Representation for Recognition of Free-form Surfaces", M.Hebert, K.Ikeuchi and H.Delingette, IEEE Trans. PAMI, Vol.17, No.7, pp.681-690, 1995.）
　しかし、これらの方法は計算負荷が大きく、どちらかといえば遅く、ノイズや小さな起伏に敏感である。
【０００７】
　したがって本発明の目的は、データベースなどにおける３次元オブジェクトの効率的な検索を実現する技術を提供することにある。本発明の別の目的は、比較的小さな計算負荷で、３次元オブジェクトを検索する技術を提供することにある。本発明のさらに別の目的は、３次元オブジェクト検索に対し、比較的ノイズに強い技術を提供することである。
【０００８】
　本発明のさらに別の目的は、例えば前述の目的に有用である、３次元オブジェクトを効果的に符号化する技術を提供することである。本発明のさらに別の目的は、任意の次元を持つオブジェクトを効果的に符号化する技術の提供にある。
【課題を解決するための手段】
【０００９】
　本発明のある態様は、形状解析器である。この形状解析器は、オブジェクト形状を表す３次元データが受け取られるインタフェイスと、受け取られた３次元データの中において、処理されるべき複数の点を定義する点集合生成器と、定義された点に対し、モース関数のモース値を得る評価器、オブジェクトに対する所定の幾何学操作対し不変であるように選択されたモース関数と、得られたモース値に基づき３次元データの大域的な位相グラフを生成するグラフ生成器を含む。
【００１０】
　モース関数は本来、特異点全てが非縮退である連続関数と定義される。しかし、この明細書ではモース関数は形状の特徴を検出するために使われる関数であり、縮退については特に問題にしない。さらに、ある関数が縮退している特異点を持つときでさえ、それをわずかに変化させることでモース関数に変換されうることが知られている。例えば高さ関数において、縮退している特異点は、わずか高さ軸方向を変えることで消滅する。
【００１１】
　モース値は注目されている点でのモース関数の値である。大域的な位相グラフでは、ポリゴンデータにおける頂点の連結性のようなきわめて局所的なトポロジは除かれ、オブジェクトの全体的な構造により注視する。
【００１２】
　この態様おいて、生成される大域的な位相グラフは、回転、平行移動、その他、例えばアフィン変換などの所定の幾何操作に対し不変である。この特徴は、オブジェクトが回転した時でさえ同一オブジェクトより生成されたグラフであれば同じグラフとなるため、オブジェクトにインデックスを付与するのに好適である。さらに、仮にモース関数がオブジェクトの変形に敏感でないとすると、前記特徴はオブジェクトの検索に好適である。
【００１３】
　位相グラフはノード間を連結するエッジを含んでもよい。ノードは各領域に与えられてもよい。さらに、ノードはモース値またはモース関数に関する特異点に与えられてもよい。
【００１４】
　形状解析器は、更に所定の近似判断基準に基づき、同じグラフ生成器により作られた第１のオブジェクトの第１の大域的な位相グラフと第２のオブジェクトの第２の大域的な位相グラフの近似度を計算する処理器を含んでもよい。この特徴によると、データベースなどの中に存在する類似の形状を探し出すことが容易になる。
【００１５】
　本発明の別の態様も形状解析器に関する。この形状解析器は３次元データのトポロジを考慮した計算処理に基づき、オブジェクトの大域的な位相グラフをの複数解像度により生成するグラフ生成器を含んでもよい。前記生成されたグラフは、粗いものから細かいものへ遡る手順に基づき、２つのオブジェクトをマッチングするの為に使用されてもよい。
【００１６】
　本発明のさらにまた別な態様も、形状解析器に関する。この形状解析器は、オブジェクトの形状表す３次元データの大域的な位相グラフを入力するグラフインタフェイスと、前記インタフェイスにより入力された第１のオブジェクトの第１の大域的な位相グラフと第２のオブジェクトの第２の大域的な位相グラフを保存するワークメモリと所定の近似判断基準をもとに、前記保存された第１と第２の大域的な位相グラフの近似度を計算する処理装置を含む。
【００１７】
　前記近似度を評価するために、前記処理装置は第１と第２の大域的な位相グラフの要素間の対応を検出してもよく、また、前記検出された対応している要素間、例えば前記検出された対応しているノードの特性間のような、要素間のマッチングの程度を計算してもよい。前記特性は面積、ノードの密度、特に前記各ノード間に関連づけられるより細かな解像度のグラフに含まれる特性であってもよい。前記特性は、例えば大域的な位相グラフ上のスケーリングのような所定の幾何操作に対し敏感でなくてもよい。
【００１８】
　本発明の更に別の態様もまた、形状解析器に関する。これはモース関数の値に基づき３次元データを複数の領域に分割し、さらに前記領域をグラフのノードと関連づけることによりオブジェクトの大域的な位相グラフ生成するグラフ生成器を含む。
【００１９】
　以上の各構成、処理内容を任意に入れ替えたり、装置を方法またはコンピュータプログラムと言い換えた物もまた本発明として有効である。
【００２０】
　本発明の更に別の態様は、サーバ、データベース、および少なくとも一つのユーザ端末を含むネットワークシステムに関する。ネットワークはワイヤレスでもよい。データベースは商品とその商品の形状の大域的な位相グラフを保存する。前記サーバはデータベースにアクセスすることで、インストールされているプログラムにより、前記商品の形状に関するマッチングの程度を評価する。
【００２１】
　この形態において、ユーザ端末を利用するユーザが興味のある商品をサーバに電気的に通知した場合、サーバはその商品と相対的にマッチングの程度が高い商品を前記データベースから検索し、その結果を前記ユーザ端末へ送信する。このようにユーザが購入の候補を見つけたとき、ユーザは最初の候補と形状が似ている別の候補を検索する旨を要求することができる。
【００２２】
　上記態様とそれについての要素は、技術的にリーズナブルな時組み合わせ、または置き換え、または組み合わせおよび置き換えが可能である。上記形状解析器の様態または機能は、全てハードウェア機器のみにより、または部分的にハードウェア、部分的にコンピュータプログラムにより、または、全てコンピュータプログラムにより実行可能である。プログラムとして認識される部分は、コンピュータが読み取り可能な媒体に記録することが可能である。
【００２３】
　最後に、本発明は、３次元以上の次元のデータに対し適用可能である。というのは、そのようなデータに対する基本的操作も３次元データの場合の拡張だからである。ｎ次元データの場合、「形状」はｎ次元で規定される。
【発明を実施するための最良の形態】
【００２４】
　最初に数学に基づき理論に関し要素技術を詳述し、続いて実施の形態を示す。
【００２５】
[理論説明]
序論
　３次元オブジェクトを検索するためのトポロジマッチングという新しい技術に関して説明する。この技術において、多面体モデル間の近似度がそれらのレーブグラフを比較することで計算される。
【００２６】
　レーブグラフは、３次元形状のスケルトン構造を表し、検索キーとして使用可能である。この例に使用されているレーブグラフは、それぞれ平行移動や回転に対して不変である測地線とユークリッド距離の関数を使用して生成される。これらのレーブグラフはメッシュの簡素化や細分化による接続性の変化に対しロバスト性を示す。
【００２７】
　多重解像度レーブグラフは、種数の違いも考慮し、近似度を効果的に評価するするために導入される。トポロジマッチングは、予め回転など３次元形状について特別な姿勢を決めておく必要がないため、３次元形状どうしの近似度を素早く計算することができる。
【００２８】
　トポロジマッチングでは、あらかじめ姿勢を登録することなしに回転や平行移動により異なる姿勢をとるモデルどうしのマッチングが可能である。トポロジマッチングは、検索結果が人間の感覚によく合うので、相互作用的に大きなデータ集合からオブジェクトを検索するのに有効である。
【００２９】
　トポロジマッチングは２つの側面を持つ。第一の側面は３次元形状の特徴を表すキーを定義または生成することである。このキーは、データベースに容易に保存できるよう十分単純であり、同時に良い近似度評価を行うために十分に形状の特徴を表す必要がある。第２の側面は、データベースから所望のオブジェクトを検索するために、生成されたキーを効果的に使い近似度を計算することである。
【００３０】
　第一の側面であるキーの定義において、スケルトン構造であるレーブグラフが注目される。レーブ博士により定義されたレーブグラフスケルトンは、オブジェクトまたは形状の骨格構造とトポロジ構造を表し、そのオブジェクトにたいし定義されるモース関数という連続関数を使用し生成される。
【００３１】
　レーブグラフは下記の理由により、３次元形状のキーとして選択される。　
（１）レーブグラフは常に１次元グラフ構造をなし、近似度推定のアルゴリズム作るのことが比較的容易となる。　
（２）オブジェクトに対し定義された様々な連続関数（モース関数）を使用することで、１つのオブジェクトに対し、多くの異なるレーブグラフを作ることが可能である。また、モース関数を適切に定義することでレーブグラフは３次元形状の回転、平行移動、スケーリングに対し不変となるため、形状を識別するのに適したものができる。　
（３）レーブグラフはモース関数の値と関連づけられており、多重解像度構造をレーブグラフに導入可能となる。多重解像度レーブグラフ（ＭＲＧ）を使用することで、３次元形状の近似度がより効果的に計算可能となる。
【００３２】
　トポロジマッチングの第２の側面は、レーブグラフで表されたキーを使用することで、３次元形状間の近似度を計算することである。前記レーブグラフはグラフ構造の形態をとるので、仮に単純に計算すると、NP−Complexityの計算負荷が必要とされる。この難点を回避するため、トポロジマッチングは多重解像度レーブグラフを利用する「粗いものから細かいものへ遡る手順」を使用し、近似度を計算する。
【００３３】
　下に説明するように、種数の違いは、正確性向上のため近似度評価において考慮される。種数はあるオブジェクトの穴の数を表す。異なる種数を持つ２つのオブジェクトはトポロジを変えることなくモーフィングすることは不可能なため、種数の違いは、近似度の評価に有効である。
【００３４】
１．レーブグラフとその多重解像度の拡張　
　レーブグラフは、任意の次元を持つオブジェクトのトポロジ構造、または骨格構造を表すグラフである。レーブグラフは常に１次元グラフ構造の形態をとる。トポロジマッチングにおいて、レーブグラフは３次元形状の特徴を表すキーとして使用される。レーブグラフの正式な定義は次の通りである。関数ｍは、オブジェクト表面（ＣＷ−複体）Ｃ上に定義される連続関数であり、
　　　ｍ：Ｃ→Ｒ
が、成り立つ。　
　仮定１：ｍ（Ｘ１）＝ｍ（Ｘ２）
　仮定２：Ｘ１とＸ２がｍ−１（ｍ（Ｘ１））の同一連結成分である
が成り立つとき、同値関係（Ｘ１，ｍ（Ｘ１））〜（Ｘ２，ｍ（Ｘ２））により、レーブグラフはＣＲ空間中の関数ｍのグラフの商空間となる。
【００３５】
　数学的厳格さはさておき、簡単に言うと、レーフグラフは関数ｍに関するオブジェクトの各同値横断面中で連結している要素を一点に集約することにより生成される。
【００３６】
　前記連続関数ｍはモース関数と言われる。モース関数が変化すると、対応するレーブグラフも変化する。様々なタイプのモース関数やレーブグラフの中で、最も簡単な例は、２次元多様体上の高さ関数がモース関数として定義されるグラフである。つまりモース関数ｍは、２次元多様体上の点ｖのｚ軸上の値を返す。
　　　ｍ（ｖ（ｘ，ｙ，ｚ））＝ｚ
　図１はトーラス表面上の高さ関数の分布と対応するレーブグラフを表している。この場合、同じ値を結んだ線は横断面の等高線を作る。レーブグラフは等高線の連結情報と見なすことが可能である。
【００３７】
１．１　多重解像度レーブグラフ
　このサブセクションは新しい多重解像度レーブグラフ（ＭＲＧ: Multiresolutional Reeb Graph）に関し説明をする。新しいＭＲＧの基本的考えは次の通りである。あるレベル（解像度）のレーブグラフを生成するため、オブジェクトはモース関数に基づきいくつかの領域に分割される。レーブグラフのノードは各領域の連結成分を表し、隣接するノードは、前記オブジェクトの対応する部分がお互い接すると仮定した場合、エッジにより連結される。より細かなレベルのレーブグラフは、各領域を再度分割することで生成される。トポロジマッチングにおいて、再分割は、簡単にするためバイナリ的な手法でなされる。図２ａ〜図２ｃは、説明を簡単にするために、モース関数として高さ関数が適応された例を示している。
【００３８】
　図２ａにおいて、一つの領域ｒa0と一つの連結成分sa0,0のみが存在する。図２ｂにおいて、領域ｒa0はｒｂ0とｒｂ1に再分割される。ｒｂ0には連結成分sb0,0を、ｒｂ1にはsb1,0、sb1,1を与える。
【００３９】
　対応するノードは、それそれnb0,0, nb1,0, nb1,1である。sb0,0、sb1,0、sb1,1の連結性により、エッジはnb0,0,とnb1,0の間、nb0,0とnb1,1の間に生成される。
【００４０】
　同様にして、より高い解像度のレーブグラフが生成される。ＭＲＧは以下の特性を持つ。
　特性１：隣接レベルのノード間に親子関係が存在する。図２において、na0,0,は nb0,0, nb1,0, nb1,1の親になる。
　特性２：再分割を繰り返すことで、ＭＲＧはレーブにより定義された本来のレーブグラフに収束する。つまり、解像度が高いほどは、本来のものをより正確に近似する。　
　特性３：あるレベルのレーブグラフは暗示的に、それより粗いレベルの情報を全て含有する。一旦レーブグラフが生成されると、隣接ノードを統合することでより粗いレベルのレーブグラフを生成可能である。図２ｃから図２ｂのレーブグラフを生成することを考える。ノード{nc0,0，nc1,0, nc1,1}はnb0,0,に統合され、{nc2,0,nc3,0}はnb1,0,に統合される。これは親子関係を満足することを示している。
【００４１】
　これらの特性を使用することで、ＭＲＧは容易に生成され、オブジェクト同士の近似度は「粗いものから細かいもの」への手順により計算される。
【００４２】
２．トポロジマッチングのためのモース関数の定義
　モース関数として高さ関数を使用して生成されるレーブグラフは理解が容易であり、断面図に基づく３次元形状のモデリングに有効であるが、３次元形状を識別するためのキーとしては適切ではないかもしれない。オブジェクトが回転すると、レーブグラフ構造が変化するためである。レーブグラフをオブジェクトの識別に適したグラフとして生成するため、回転に関して不変であるモース関数を定義することが必要となる。
【００４３】
　トポロジマッチングにおいて、モース関数は測地線距離を組み入れた形で選択される。測地線距離の使用は回転にたいし不変になり、図３ａに見られるような変形にたいし敏感でないという有効な特性を示す。前記関数を利用することでトポロジマッチングは、１つのオブジェクトが２つ姿勢や２つの変形形態をとる場合、それらを同一オブジェクトェクトとして認識する人間の能力に近づく。トポロジマッチングに使われるモース関数を定義する。
【００４４】
　まず関数morsegを表面Ｓ上の点ｖの測地線距離の和とし次式で表す。
【数１】
2004118876.tif 000003
　ここで関数gdistsは表面Ｓ上の測地線距離を表す。連続関数morsegは回転に関して不変であり、形状の変形に関しよい振る舞いを示す。さらに、修正関数morseg'を式（２）により定義する。　
【００４５】
【数２】
2004118876.tif 000004
　図４ａと図４ｂに、この修正モース関数の効果を示す。図４ａに示すように、morsegの密度が２次曲線の形式におけるオブジェクト中心に集中する傾向がある。仮にmorsegが修正なしに直接モース関数として使用される場合、生成されるレーブグラフは形状の特徴を表すのにその能力に偏りがでる。つまり、かど部分の形状が中央部の形状より細かく表される。前記修正は、前記偏りを図４ｂように改善する。
【００４６】
　修正関数morseg'は変形を扱うのによいが、図３ｂの２つのオブジェクトを区別することができないという欠点を持つ。これら２つオブジェクトは、同じ修正関数morseg'の分布を持つ。
【００４７】
　この問題を扱うためにトポロジマッチングでは式（３）で示されるmorseeが導入され、それはユークリッド距離の和を返す。
【数３】
2004118876.tif 000005
　ここで、関数edists=|v-p| はユークリッド距離を表す。更に、morseg'と同じように修正関数morsee'が導入される。
【数４】
2004118876.tif 000006
　最終的にトポロジマッチングで使用されるトータルのモース関数 morse(v)は次に定義される。
　　morse(v) = wm morse'g(v) + (1-wm)morse'e(v)　(5)
　ここでwm　は重み係数であり、生成されるレーブグラフはwmが大きい場合、形状の変形に対しより敏感でなくなる。
【００４８】
３．多重解像度レーブグラフの計算と生成
　前述の通り、トポロジマッチングの定義と特性に関し説明した。この章ではモース関数morse(v)の計算方法、および実際のＭＲＧの生成方法に関し説明する。
【００４９】
３．１　測地線とユークリッド距離の積分計算法
　この章では、トポロジマッチングのためのモース関数morse(v)の計算方法に関して説明する。計算速度改善のため、測地線距離はエッジ長に基づくDijkstraアルゴリズムで近似される。この目的のため、メッシュの各エッジは、特性または属性としてその長さが割り当てられる。トポロジマッチングにおいて、モース関数の値がメッシュの各頂点に割り振られる。この理由により、頂点の分布は測地線距離を近似するため、さらにモース関数の分布を正確にするのに十分精細であることが望ましい。それゆえ、閾値ρによるメッシュ頂点の再サンプリングが必要となる。図５ａと図５ｄに再サンプリングの手順を示す。ρより長いエッジに頂点が追加され（図５ｂ）、各三角形は前記追加された頂点を使用して細分される（図５ｃ）。前記手順は全てのエッジがρより短くなるまで繰り返される（図５ｄ）。
【００５０】
　次に、ショートカットエッジという特別なエッジがメッシュに追加される。メッシュのエッジの向きが一様であると、測地線距離の計算が不正確になる。それ故、ショートカットエッジはエッジの方向を等方性にすることで一様性を修正するために導入される。図６ａおよび図６ｂは、ショートカットエッジを付け加える手順のアルゴリズムを示す。三角形t1，t2はエッジe(p1,p2)により隣接している。三角形t1，t2はそれぞれe(p1,p2)に触れない頂点v1，v2を持つ。
【００５１】
　次の基準、
【数５】
2004118876.tif 000007
が満足されると、v1とv2を結ぶショートカットエッジes(v1,v2)が追加される。ここで、関数　gdist t1Ut2は表面t1∪t2の表面の測地線距離を返す。このショートカットエッジは、その長さ特性としてgdist t1Ut2(v1,v2)を持つ。
【００５２】
　頂点の再サンプリングとショートカットエッジ生成後、ベース頂点から各頂点までの距離は図７に記載のDijkstra手法により計算される。
【００５３】
　式(１)は、式(７)により近似される。
【数６】
2004118876.tif 000008
　ここで、｛pi｝i＝｛p0,p1,・・・｝は表面Ｓに均等に分布されたDijkstra理論の為のベース頂点である。前記area（pi）はpiが占める面積であり、Σiarea（pi）はＳの全面積を表すarea（S）に等しい。｛pi｝iは若干修正されたDijkstra手順を使用し選択される。
【００５４】
　この修正手順において、Vciは、gtempp（Vci）が閾値dpより小さいときステップ６でｌに挿入されるだけである。ステップ７でｌが無い時、任意の接続のない頂点が新たなpiとして選択される。閾値ｄpが小さい場合、多くの頂点が｛pi｝iとして選択される。頂点の数が増加すると、morse(V)の正確な計算が可能となる。しかし、計算時間が伸びる。前記手順実行において、前記閾値dpは、（area(S)）0.5に比例して定義される。
【００５５】
　これは、
【数７】
2004118876.tif 000009
とする場合、150のベース頂点｛pi｝Iが生成され、morse(v)を十分な正確さで表すことが出来た。図８ｂは前記｛pi｝i（白点）と占められる面積　area(pi)を示す１例である。｛pi｝i選択後、前記morse(v)は上記Dijkstra手順により計算される。
【００５６】
　前記morsee(v)は、morseg(v)に使用されている同一のベース頂点｛pi｝iを使用する式３の近似により計算される。
【００５７】
【数８】
2004118876.tif 000010
　ここで、edist(v,pi)は、vとpｉ間のユークリッド距離であり、Dijkstragdistの手順を使わずに直接計算することも可能である。最後に、関数morse(v)は、第２章の式に記述されているようにmorseg(v)とmorsee(v)から計算される。
【００５８】
３．２　多重解像度レーブグラフの生成
　多重解像度レーブグラフ（ＭＲＧ）の生成を説明するため、次の定義をする。　
{Rl}={R0,R1,R2…,Rl,…,Rlmax }:　lmax+1のレーブグラフから成るＭＲＧ　
{rli}i={r10,r11,…,r12l-1}:　レーブグラフRlにおいて分割された2lの領域　
{nli,k}k={n1i,0,n1i,1,…}:　　レーブグラフRlの領域rli中のノード　
　ＭＲＧの生成は、最も細かなレーブグラフRlmaxを生成することから始める。その後、第１章で述べたＭＲＧの特性３を利用し、より粗いレーブグラフが生成される。Rlmaxを生成するとき、頂点が再サンプリングされモース関数morse(p)が下記に述べる手順でそれら頂点に割り当てられる。関数morse(v)の値は、第２章の定義に従い、０から１の間に正規化される。
【００５９】
　各領域rlmaxiは、その値がmin(rlmaxi)とmax(rlmaxi)の間である要素に対応する。ここで 、min(rlmaxi)=i/2lmax 、max(rlmaxi)=(i+1)/2lmax
前記2lmax の領域 {rlmaxi}i ={rlmax0, rlmax1,…, rlmax2lmax-1}は、バイナリ的手法により、一様に分割される。
【００６０】
　つづいて、次の条件を満たすメッシュの三角形{ti,j}j = {ti,0,ti,1, ... }は、各領域rilmaxに対応する三角形として抽出される。
【００６１】
【数９】
2004118876.tif 000011
　ここでmin(ti,j) と max(ti,j)は、それぞれti,jが持つ頂点の最小および最大モース値である。各領域rilmaxにおける連結成分は、ti,jに基づき探索される。次の２つの条件のいずれかを満足する場合、前記探索において隣接する三角形ti,j1 と ti,j2がrilmaxにおいて結び付けられる。
【００６２】
条件１：
【数１０】
2004118876.tif 000012
ここで、min(ej1,j2 ) と max(ej1,j2)　は　ej1,j2の２つの頂点のモース値であるか、min(ej1,j2) ＜＝ max(ej1,j2)　を満足する。　
条件２：
　前記 ti,j1 とti,j2　は一般的な頂点 vj1,j2 を持ち、それらは次式を満足する。
【数１１】
2004118876.tif 000013
　前記連結成分 である{ti,j}j は、次のように上記の条件を使用して分割される。　
　{ti,j}j = {ti,0,m}m　U {ti,1,m}m　U … U {ti,k,m}m　 U…　
　各連結成分 {ti,k,m}m ={ti,k,0,ti,k,0,…} は最も細かなレーブグラフ中のノードnlmaxi,kとして表される。最後にレーブグラフのエッジが生成される。領域 rlmaxi-1の前記連結成分{ti,k,m}mと {ti-1,k2,m}m が同一の三角形を含む場合、対応するノード nlmaxi,k1 と nlmaxi,k2 は、一つのエッジによりリンクされる。 図８ｃ は最も精かなレーブグラフを示す。
【００６３】
　最も細かなレーブグラフ Rlmaxの生成後、より粗いレーブグラフRls がＭＲＧの特性３を使用して Rlmax から生成される。図８ｄは図８ｃに見られる最も細かなレーブグラフから始まるＭＲＧの生成を示す。
【００６４】
４．マッチングアルゴリズム
　本章では、ＭＲＧを用いてどのようにして近似度を計算するのかを説明する。マッチングの正確性と効率性を確保するため、各lレベルのレーブグラフR11 と R12 の間で、ノードによる近似度simnodes(Rl1,Rl2)と種数による近似度simgenus(Rl1,Rl2)の２種類の近似度が計算される。両近似度とも０から１の値で示され、この値が大きいほどレーブグラフの近似度が高い。これらの計算することで、ＭＲＧである　R1 と R2間の、つまり３次元オブジェクトどうし間のトータルの近似度sim(R1,R2)が次式で求められる。
【００６５】
【数１２】
2004118876.tif 000014
　次のサブセクションは、ＭＲＧ中のノードの寄与とsimnodes と simgenusの計算方法について説明する。
【００６６】
４．１　ＭＲＧ中のノードの属性
　トポロジマッチングにおいてＭＲＧ中の各ノードnli,k は、近似度計算中で使用される属性または特性であるモース関数のモース値morse(nli,k)と、nli,k　に対応している部分を示す{ti,k,m}mの面積area(nli,k)と、最も細かなレーブグラフのｎから下降するノード密度leaf(nli,k)を持つ。前記属性leaf(nli,k)は、nli,k の解像度の落ちたグラフの複雑度を表す。
【００６７】
　前記面積を使用している基本的な概念は、オブジェクトの全体面積における与えられたノードに対応している面積の比率が各レベルの多重解像度で二つのレーブグラフの間で互いに比較されることにある。上記比率が互いに近いとき、マッチングの程度が高いと評価される。
【００６８】
　前記最も細かなレーブグラフの属性area(nlmaxi,k)は生成されるとき式（10）により計算される。
【数１３】
2004118876.tif 000015
仮にti,k,m が領域ri　にのみ存在する場合、areari はti,k,mの全面積を返す。それ以外は areariにおけるモース関数の分布の割合に応じて分けられた値を返す。iとkに関するarea(nlmaxi,k)の合計は正規化すると 1になり、オブジェクトのスケーリングに対してarea(nlmaxi,k)は不変となる。前記area(nlmaxi,k)の計算後、より粗いレーブグラフにおける関数area(nli,k) がノードを統合したものとして計算される。
【００６９】
【数１４】
2004118876.tif 000016
　ここで、nli,kは{nl+12i,k2i}k2iと{nl+12i+1,k2i+1}k2i+1の親である。
【数１５】
2004118876.tif 000017
はいかなる解像度レベルｌにおいても満足される。
【００７０】
　leaf(nli,k) が area(nli,k) と同様に計算される。最初、leaf(nlmax) は初期化された最も細かなレーブグラフである。
【００７１】
【数１６】
2004118876.tif 000018
　上記の式は、概念上前記leafに関するノードに対応している表面の割合におけるモース値の最大と最小の間の差異である。
【００７２】
　次の式（１２）で、粗い値が計算される。
【数１７】
2004118876.tif 000019
　ここで、
【数１８】
2004118876.tif 000020
は一定である。
【００７３】
４．２　ノードの属性による近似度　
　前記simnodes は「粗いものから細かいものへ」の手順により計算される。　まずある特定レベルのレーブグラフにおけるノードがマッチングされる。それらノードの子ノード同士のみがより細かなレベルにおけるマッチングの候補となる。例えば、図９ａにおいて、マッチングされたノードは一緒に色が変化する。そしてノード nl1,0 と ml1,1 はレベルｌでマッチングがとられる。次のレベルの図９ｂにおいて、nl1,0 c の子ノードはml1,1, の子ノードとのみマッチングが可能である。つまり、{nl+12,0, nl+13,0} だけが{ml+12,1,ml+13,0}とのマッチングをする候補となる。
【００７４】
　さらに簡単ため、トポロジマッチングはモース関数の同じ値を持つノードのみマッチング可能であるという制限を課す。したがい、nl+12,0 は ml+12,1 とマッチマッチングし、 nl+13,0 は ml+13,0とマッチングする。シングルノードｎとマッチングできる候補として多くのノード {mi}i が存在する場合、トポロジマッチング は次式が最大値をとる候補間でマッチンッグ行う。
【００７５】
【数１９】
2004118876.tif 000021
ここで ws (0 ＜＝ ws ＜＝ 1) は前記areaの属性と前記leafの属性の重みを制御する。式１３は前記面積の近似度と、複雑性の近似度、もしくは最も細かなレベルにおいて存在する子の数を考慮に入れる。
【００７６】
　マッチングするノードの選択において、レーブグラフの構造がモース関数の領域境界の配置に敏感であるという問題がある。
【００７７】
　図１０（ａ） と図１０（ b） は領域境界がわずかに異なるため同じオブジェクトが異なる結果になった例を示している。この問題を解決するために、トポロジマッチングは次のようノードを与える 
　全ノード∈｛mi,kl｝klが上の解像度レベルの同一ノードmi-1,k　もしくは下の解像度レベルの同一ノードmi+1,kと接続すると仮定すると、ノードni,k0は同時にノード｛mi,kl｝klとマッチングする。例えば、図１０（ａ）と図１０（ｂ）において, m1,0 と m1,1 は上位において同じノードm0,0 と接続しているので、n1,0 は同時に {m1,0 ,m1,1 } とマッチング可能である。この場合、n1,0　とマッチング可能な３候補m1,0, m1,1 および {m1,0 ,m1,1}が存在する。前記n1,0 と{m1,0 ,m1,1}の選択されたマッチングは 、{m1,0 ,m1,1 }を新しいノードm1,0Ｕ1 と見なすことで計算される。ここで 、area(m1,0Ｕ1) = area(m1,0) + area(m1,1) 
かつ、leaf(m1,0Ｕ1) = leaf(m1,0) + leaf(m1,1)である。
【００７８】
　実際の実施においては、計算速度を考え、前記ノードマッチングはストレートフォワードであり、工程を戻ることはない。前記処理は、次に述べる各モース値の整列関数order(n) を使用し下降の順序で実行される。
【００７９】
【数２０】
2004118876.tif 000022
　例えば, レーブグラフRn のノードni,0, とレーブグラフRmのノードmi,0のマッチングを考える。ノードが、
　　　order(ni,0)>order(mi,0)>order(mi,1)>order(ni,1)
を満足すると仮定すると、最初のステップは n1,0に関するマッチングを計算することである。次は、仮にまだマッチングなされないとき、m1,0 に関するマッチングを計算する。
【００８０】
　レベルｌの２つのレーブグラフにおけるノードのマッチング計算後、近似度simnodes が次の式で計算される。　
【数２１】
2004118876.tif 000023
　ここで、｛nlx,mlx｝は前記計算されたマッチングである。
【００８１】
４．３　種数の差異による近似度
　異なる種数における近似度は、オブジェクトの分類において重要な要素かもしれない。したがい、関数 simgenus は、この近似度計算手法が、上記計算されたノードの属性による近似度と結び付けられるように計算される。一般に、 特異点の縮退がない限り、オブジェクトの種数ｇはレーブグラフにおける要素の数を使用して計算されうる。　
　g＝#(edge)-#(node)+1
　この式を使用し、図１１の手順 Difgenus は２つのＭＲＧ間における各レベルｌの種数の違いを表す△(l)を計算するために使用される。
【００８２】
　粗いレベルの前記△(l)は、simgenusの結果にたいし影響をあたえるように見えるかもしれない。結果として、simgenusは次のように定式化される。　
【数２２】
2004118876.tif 000024
　level　l=0　or　1では, △(l)　は常に０であるからsimgenusは1を返す。この式の基本的概念は、仮に「粗いものから細かいもの」への手順において、１つの種数または穴が現れるタイミングが近ければ、２つのレーブグラフは似ていると評価される。図１２は種数の違いに関する計算方法を示す。
【００８３】
５．実験
　トポロジマッチングの手順を評価するため、以下の実験を行った。この実験は、the Viewpoint models　(http://www.viewpoint.com)、the 3DCAFE free stuff　(http://www.3dcafe.com), the Stanford University　(http://www-graphics.stanford.edu/data/3Dscanrep)、および本実験用に作られたオリジナルデータから、計１６０の異なるポリゴンメッシュを選び利用した。使用したパーソナルコンピュータ環境は、オペレーティングシステムがLinux、CPUがPentium（登録商標）ＩＩ333MHzである。
【００８４】
　実験を通して,使用されたパラメータは、ws=0.5 、lmax +1 = 8 である。上述の通り、ws はsimnodes,の計算時、属性areaと属性leafの重みを制御し、 前記 lmax +1 はＭＲＧの解像度レベルの数字を示す。
５．１　多重解像度レーブグラフの生成　
　近似度の計算時、最初に各メッシュのためのＭＲＧを生成する必要がある。これら生成の際、Dijkstragdist の手順を使用しモース値を計算する段階が全計算処理時間の約９０％を占める。前記手順 Dijkstragdist はＯ(V log v)の計算コストである。ここで、vは前記メッシュ中の頂点の数である。実験によると、測地線距離を十分に近似するため、Dijkstragdistに１５０のベース頂点を使用することで、１００００頂点のメッシュのためのＭＲＧが１５分以内で計算可能である。
【００８５】
５．２　測地線距離とユークリッド距離
　パラメータwm は、計算における測地線距離とユークリッド距離使用の重み、つまり、形状変形に対する敏感さ（第２章参照）を制御する。 wmが大きいほど、つまり測地線距離の重みが大きいほど、形状変形に対しより敏感になる。前記wm が 0.5以下の場合、近似度は不安定になり一様には変化しない。
【００８６】
小さい wm は他の目的、例えばオブジェクトの変形があるかどうかを探すの効果的である。しかしながら、トポロジマッチングには比較的大きなwm が適当である。以下の実験では、wm=0.7 を使用した。
【００８７】
５．３　マッチングと検索
　マッチング実験は図１３（ａ）〜（ｆ）の６つのモデルを使い行われた。メッシュペア {13a, 13b}, {13c, 13d} および {13e, 13f} は同じオブジェクトを表し、メッシュ１３ｂ は１３ａにたいし回転、平行移動、スケーリングなどのユークリッド変換を施すことで生成された。メッシュ１３ｄはメッシュ１３ｃのメッシュの単純化モデルである。メッシュ １３ｆ もまたユークリッド変換よるメッシュ１３ｅの単純化モデルである。各メッシュの頂点の数と計算された近似度の結果を図１４に示す。この結果によると、接続性が変わり（単純化）かつユークリッド変換に従うメッシュでさえ正確に認識可能である。
【００８８】
　最後に、全１６０メッシュの中からオブジェクトを探索する実験を行った。この場合、各１６０のメッシュのＭＲＧは前もって生成された。前記検索では、１６０のモデルから１モデルが選ばれ、それと他のモデルの間の近似度が計算され、モデルは生じた近似度に従い保存される。図１５に実験結果例を示す。
【００８９】
　与えられたモデルはキーとして示される。さらに最も近似度が高いと評価され探索されたモデルから順に所定のモデル数だけ表示される。
【００９０】
　前記結果は人間の一般的な感覚によく一致するといえる。あるモデルと残り160のモデルとの間の近似度の計算時間は、0.87秒から3.69秒の間であり、平均は2.11秒である。つまり、平均1.31 x 10-2 sec. で１つの近似度を計算する。
【００９１】
6．まとめ
　トポロジマッチングと呼ばれる新しい手法を、三次元形状間の近似度の効率的な計算に対して提案した。形状を識別するためのキーとして、測地線およびユークリッド距離に基づいて多重解像度レーブグラフ（ＭＲＧ）が生成される。近似度は、レーブグラフのノードの特性と種数の違いを使用する「粗いものから細かいもの」への手順を用いて計算される。トポロジマッチングによると、素早く効果的な近似度の計算処理が可能となり、またその結果は人間の直感によく一致するという結果を示している。
【００９２】
　トポロジマッチングは、ＭＲＧを生成または近似度を計算するために、いかなるタイプの複数のメッシュにて対しても使用できる。つまり、それはいかなる二次元のCW-複体を取り扱うことが可能であることを意味する。
【００９３】
　しかし、前記メッシュが不正確の場合、予想と異なるマッチングが発生する可能性がある。例えば、イレギュラーな部分が大きい場合や、接近していない場合、または多様体形状でない表面を持つ場合、間違った結果を示す傾向がある。接続性をメッシュの外観にたいし適合させることにより、さらに、より多くの特性を付け加えすることによって。例えば、曲率やテクスチャをトポロジマッチングに付加することにより正確なマッチングが可能となる。
【００９４】
　トポロジマッチングは、近似度の効率的評価が重要であるさまざまなアプリケーションに適用出来る。例えば、インターネットを通して自動的に三次元形状を検索するために使用可能である。電子商取引において、ＭＲＧを含む三次元カタログを準備することにより、顧客はある特定の設計に類似の商品を検索することが可能となる。
【００９５】
［具体的な適用例］
　以上の理論を使い、詳細な例を説明する。図１６は本発明の実施の形態である形状解析器のブロック図を示す。形状解析器１０は、パーソナルコンピュータにより実現される。形状解析器１０は、主制御部８０、ユーザインタフェイス８２、データ保持部２４を含む。データ保持部２４は、３Ｄデータベース６０、ＦＲＧ保持部６２、ＭＲＧ保持部６４、および、マッチング結果保持部６６を含む。３Ｄデータベース６０は、オブジェクトの３Ｄメッシュデータを保存する。ＦＲＢ保持部６２は、オブジェクトの最も細かなレーブクラブを保存する。ＭＲＧ保持部６４は、オブジェクトの多重解像度レーブクラブ、すなわちＭＲＧを保存する。マッチング結果保持部６６はマッチング結果を保存する。データ保持部２４はハードディスク、ＭＯ、その他記録媒体によりＰＣの内部または外部で実現される。データ保持部２４と任意の部品は遠隔ドライブやネットワークによりアクセス可能な装置により実施される。
【００９６】
　主制御部８０はＣＰＵ、形状分析のプログラムモジュールが実装されたメモリ、ストレージ制御部、画像およびディスプレイ制御部、その他ディバイスの協働により実現される。この説明において、図１６では、各ブロックは機能に基づいて描かれており、各ブロックはハードウェアとソフトウェアの柔軟な組み合わせにより実現される。
【００９７】
　ユーザはマウス、キーボード、他の入力装置であるユーザインタフェイスをコントロールする。　
　３次元データインタフェイス１２はユーザの指示により３次元データベース６０からオブジェクトの３次元データを入力する。前記ユーザの指示は３次元データインタフェイス１２を経由し、オブジェクトデータベース管理部３８に送られ、そこですべてのデータ保持部２４の操作がなされる。入力データは点集合生成器１４に送られる。データが離散点のデータの集合として表現されるときは、点集合生成器１４は最初に、後述のグラフ生成の処理の為の離散点の集合部分を定義もしくは選択する。点集合生成器１４は、計算処理能力が十分である場合、定義点としてすべての離散点を選んでもよい。オリジナルの表現において、入力データがすでにメッシュデータや多面体データであるとき、点集合生成器１４は、定義されたデータをモース評価器１６に移すだけでよい。
【００９８】
　モース評価器１６は、前処理器３０と測地線距離計算器３２とユークリッド距離計算器３４とを含む。測地線距離計算器３２とユークリッド距離計算器３４は、測地線距離およびユークリッド距離関数をそれぞれモース関数として扱う。前処理器３０は再サンプリング、細分化、および点集合生成器１４から移されたデータメッシュに基づいてショートカットエッジの生成を行う。これらは前述の理論説明の第３章と図５（ａ）〜５（ｄ）、６（ａ）と６（ｄ）に記述されている。
【００９９】
　前処理器３０の処理後、測地線距離計算器３２とユークリッド距離計算器３４はモース関数を式２と式４に基づき計算する。これらの式の計算において式7と式8の近似がそれぞれ使用される。最後にモース評価器１６はＭＲＧ生成器１８に対し第２章の式５に基づき、メッシュ頂点のモース関数の統合された値を出力する。
【０１００】
　統合されたモース値morse(v)の値に基づき、ＭＲＧ生成器１８はオブジェクトのＭＲＧを生成する。最初に、表面分割器４０は、オブジェクトの表面の値に基づいて、第３章に記述の最も細かなレベルｌmaxで２lmax領域に均等に分割する。
【０１０１】
　最も細かなレーブグラフ生成器であるＦＲＧＧ（Finest Reeb Graph Generator）４２は、前記メッシの三角形ti,jの連結性を調べることで、連結成分をレベルlmaxで探索し、最も細かなレベルのレーブグラフＦＲＧを生成する。
【０１０２】
　前記ＦＲＧは、より粗いレーブグラフ生成器であるＣＲＧＧ（Coarse Reeb Graph Generator）４６へ移され、さらにグラフインタフェイス４４を経由してＦＲＧ保持部６２に送られ保存される。ＣＲＧＧ４６は第１章に記述してある特性３を使用し、前記ＦＲＧからより粗いレーブグラフを生成する。ＣＲＧＧ４６は、完全なＭＲＧをＦＲＧと前記一連の粗いレーブグラフを結び付けることによりＭＲＧ保持部６４へ送る。前記ＭＲＧは、また後のマッチングプロセスのバッファとしてのワークメモリ２０へ送られる。ＭＲＧはオブジェクトがマッチングプロセッサ２２でマッチングされるたびに生成されてもよく、この場合ＭＲＧ保持部６４は必ずしも必要はない。
【０１０３】
　しかし、ＭＲＧはむしろ生成のための計算処理を軽減するために保存される。実施の形態において、ＦＲＧはＦＲＧ保持部６２に保存されるため、前記ＭＲＧ自体はワークメモリ２０にコピーされた後廃棄されてもよい。これは、ＦＲＧからＭＲＧを生成するのは比較的ストレートフォワードであり計算負荷をほとんど必要としないためである。新しいオブジェクトの生成が開始されたとき、ＣＲＧＧ４６は最初に、新しいオブジェクトのＦＲＧがすでにＦＲＧ保持部６２に保存されているか否か検索する。新しいオブジェクトがＦＲＧ保持部６２中に検出されたとき、ＣＲＧＧ４６はグラフインタフェイス４４を通して、新しいオブジェクトのＦＲＧを読み出して入力する。前記ＦＲＧはＭＲＧ保持部６４から取り出されて、ＭＲＧ保持部６４に保存された後、ＦＲＧ保持部６２にコピーされてもよい。
【０１０４】
　ワークメモリ２０は、現在のオブジェクトのＭＲＧを保存し、それは後述のように第１のＭＲＧとなる。マッチングのため、第２のオブジェクトのＭＲＧまたは第２のＭＲＧが用意される必要がある。これを実現するために、第２のオブジェクトの３Ｄデータは、３Ｄデータベース６０から取り出されてもよく、また第１のオブジェクトに対しなされた同じプロセスが繰り返されてもよい。第２のＦＲＧまたはＭＲＧは、適切な時に、それぞれＦＲＧ保持部６２またはＭＲＧ保持部６４から取り出されてもよい。いずれにせよ、一連のプロセスの後、ワークメモリ２０に第２のＭＲＧは保存される。
【０１０５】
　マッチングプロセッサ２２はワークメモリ２０から第１及び第２のＭＲＧを読み出す。対応検出器５０は、トータルの計算処理量を減らすと同時に、マッチング結果を適切なものにするため、第１と第２のＭＲＧの間でマッチングされるノードの組み合わせ、または候補の数を限定するために働く。対応検出器５０は、第４章、特に式１３及び式１４において 「ノード属性の近似度」に説明されている特性により、互いに対応してもよいノードの組み合わせを特定する。前記対応検出器５０は、得られた対応に関する内容をマッチング評価器であるマッチング計算器５２に出力する。
【０１０６】
　マッチング計算器５２は、第１及び第２のＭＲＧ間に関するマッチングの程度を評価する。それはまず、前記グラフまたはノードの対応要素に対する近似計算を行う。マッチング計算器５２は、式１０、１１、１２を使用し、近似度に基づく最終的な値の獲得のために式９に順次入力される２つの値、式１５及び式１６のために計算を行う。前記最終的な値は、マッチングの結果としてマッチング結果保持部６６に保存される。最終値はまた、ディスプレイ２６に送られる。そこでは、例えば図１５のように、オブジェクトの近似度が表示される。
【０１０７】
　上記処理は、図１５に示されるごとく多くの近似結果を与えるために、次のオブジェクトに対し繰り返してもよい。
【０１０８】
　本実施の形態によると、ユーザは、選定したオブジェクトと類似の形状をもつオブジェクトを容易に見つけることができる。図１５に見られる近似度に基づいて、マッチングプロセッサ２２がオブジェクト再配列すると非常に便利である。このように形状解析器１０は、設計におけるパーツ検索、キャプチャーされた離散データの科学的な解析、形状に基づくデータベース構築および電子商取引における商品検索など、さまざまなオブジェクト検索目的に使用可能である。
【０１０９】
　本発明の別の態様ではネットワークシステムに関する。図１７に電子商取引における利用に適したネットワークシステムを示す。ネットワークシステム１００はオブジェクト検索サイト１２０、ショッピングサイト１０８、および複数のユーザ端末の１０４、１０６を備え、それらすべてがネットワーク１０２（一般にはインターネットであるが、いかなるタイプのネットワークでも構わない）に接続している。この形態においてユーザはオンラインショッピングのサービスを受けることが可能である。
【０１１０】
　ショッピングサイト１０８は、ＷＷＷショッピングサーバ１１０とサイトがユーザに提供する商品やその他の情報のデータを保存するデータ保持部１１２を含む。商品の三次元表現のため、データ保持部１１２は分割された領域もしくは３Ｄデータベース６０を含む。
【０１１１】
　オブジェクト検索サイト１２０は、ＷＷＷ検索サーバ１２２と、そのコントロール下におかれるデータ保持部１２４を含む。検索サーバ１２２にはオブジェクトマッチングのため主機能または主ユニット８０が実装される。ユーザ端末１０４は通常マッチング機能を持たない。前記マッチングは、そのサービスとしてオブジェクト検索サーバ１２０において実行される。データ保持部１２４は、商品のＦＲＧを保存するため内部に分割された領域であるＦＲＧ保持部６２を持つ。これらＦＲＧは、ショッピングサイト１０８と、オブジェクト探索サイト１２０の間のサービス契約その他に基づき、ショッピングサイト１０８の様々な商品のために保存される。
【０１１２】
　検索サーバ１２２は、ショッピングサイト１０８のウェブページの１つにおいて、購入候補としてユーザが選ぶ商品と類似の商品を検索するためにユーザが要求するとき初期化されるＣＧＩプログラム等を含む。ＣＧＩの機能は、ユーザが、検索サービスを要求したページからリンクされている。
【０１１３】
　具体的には、ユーザ端末１０４のユーザは最初に、ディスプレイ２６の左上に表示されている候補領域２００の中から、例えばおもちゃの車の候補を選ぶ。表示されるべきＨＴＭＬページは、ショッピングサイト１０８から送信される。ＣＧＩをコールする機能は候補領域２００とボタン２１０により実現される。類似の車の検索を要求する時、ユーザはボタン２１０を押す。
【０１１４】
　前記要求は前記候補とともにオブジェクト探索サイト１２２へ送信される。次に検索サーバ１２２、特に主制御部８０は、データ保持部１２４の中に候補のＦＲＧがすでに保存されているかどうか確認する。仮に、保存されている場合、検索サーバ１２２はその候補のＭＲＧと別の商品のＭＲＧを生成する。検索サーバ１２２は、検索する商品範囲をおもちゃに限定するために、ユーザ側で表示されるショッピングページは、ユーザが検索のためのいくつかのキーワードを入力する領域でもよい。形状およびテキスト情報の組み合わせを使用する検索は、通常より良好なまたは効率的な検索結果を示す。
【０１１５】
　仮に、候補のＦＲＧが、データ保持部１２４に保存されていない場合、検索サーバ１２２は、ショッピングサイト１０８にたいし候補の三次元データを送るように要求する。３次元データを受け取った後、検索サーバ１２２は形状解析器１０と同手順で候補のＭＲＧを生成する。
【０１１６】
　検索サーバ１２２は、候補のＭＲＧと他のおもちゃの車のＭＲＧの間の近似評価器として働く。その結果は、ユーザ端末１０４へウェブページとして送られ、類似の車がディスプレイ２６の下部に表示される。この場合、最も似ている車、２番目に似ている車および３番目に似ている車が順位付けされたウィンド２０２，２０４，２０６にそれぞれ順番に表示される。
【０１１７】
　上記具体例のいくつかの変形例を説明する。上記具体例において、レーブグラフはオブジェクトの大域的な位相グラフとして使用されたが、オブジェクトの大域的な位相またはオブジェクトの構造の少なくとも一部を示す限り、他のグラフを採用してもよい。オブジェクトのレーブクラブの変形、メディアルアクシス表現およびその変形、および他のスケルトン表現が使われてもよい。
【０１１８】
　他のタイプの関数がモース関数として採用されてもよい。前記モース関数は処理される点間の距離ｒを使い、ｒaタイプである任意の次元の距離関数として、別の距離関数の特徴を含んでもよい。式１，３，７，８同様の手法により、オブジェクトの表面上の点に関して、距離が総和されてもよい。総和することや回転などの幾何操作に対し不変である関数はオブジェクトの符号化に好適である。
【０１１９】
　前記モース関数は、点間のベクトルを使う「ｒタイプ」のベクトル関数の特徴を含んでもよい。この関数は、ある参照点とオブジェクト上の点との距離を定義する距離関数の特徴を呈する。参照点は例えばオブジェクトの重心であってもよく、また回転に不変であるオブジェクトの外接球の中心であってもよい。
【０１２０】
　関数は、オブジェクト上の点の３次元座標に対する特性を定義する４次元関数としての特徴を含んでもよい。特性は色、テクスチャ座標、法線または曲率であってもよい。
【０１２１】
　４次元関数を用いることで、ボクセルデータなどのボリュームデータを扱うことができる。このとき、第４の次元はオブジェクトにおける点の密度を表す。この場合、オブジェクトの表面だけでなくボリュームも扱うことができる。ボリュームは固体だけでなく大気や雲などのように離散的な点であってもよい。式１０、１１などで使われている「面積」は、「３次元における面積」、つまり「ボリューム」に置き換え可能である。各ボリュームは、モース関数の値によって、例えば同じ大きさの領域に分割された一連の点として定義される。ボリュームデータがすべて同じボクセルとして表現されるとき、隣接するボクセル間のエッジを結び付けることで３次元メッシュを作ることが可能となる。ボクセルサイズが同一でないとき、各ボクセルはそれが親ボクセルとなって、同一密度を持つ複数のボクセルに細分化されてもよい。前述の３角形の代わりに、３次元メッシュが含まれてもよく、また３次元メッシュが使われてもよい。ボリュームデータのための測地線関数は、オブジェクト上にとられた経路に沿った、またはオブジェクトの内部にとった経路に沿った最短の距離を与える。
【０１２２】
　上記４次元の例にみられるように、本発明は任意の次元に適用できる。　
　前述の実施例において、ＭＲＧの粗いグラフは、最も細かなレーブグラフの隣接するノードを統合して得られる。前記粗いグラフは例えば、最も細かなグラフの比較的短いエッジを削除するように、細部を削除することで生成できる。
【０１２３】
　実施の形態では、モース関数はオブジェクトを分割するために使用された。しかし、モース関数は本来の定義により、特異点の検出に使用されてもよい。検出された特異点とそれらの接続性はそれぞれ、最も細かなレーブグラフのノードとエッジとして使用されてもよい。特異点がノードとして使用されるとき、最も細かなレーブグラフは　より粗いレーブグラフを作るため終点ノードを削除することで単純化してもよい。
【０１２４】
　実施の形態においてＭＲＧの代わりにＦＲＧが保存された。しかし、ＦＲＧは比較的簡単に前記モース値から生成できるため、ＦＲＧの代わりにモース値が保存されてもよい。
【０１２５】
　種数は、実施の形態において、マッチング計算において考慮される。しかし、特にオブジェクトのトポロジが変化するとき、この側面は無視されてもよい。人間の場合、腕が腰の上に置かれているとき、腕と胴体が一つ穴を作り、一方それ以外ではトポロジが変化するため穴は存在しない。
【０１２６】
　オブジェクトの３次元データは、３次元デジタイザ（それらはステレオカメラや奥行き検出器や、撮られた離散点をメッシュデータに変換するプログラムもつカメラを含んでもよい）を利用し、オブジェクト検索サイト１２０等へ入力されてもよい。
【０１２７】
　ネットワークシステム１００はさらに、ユーザとショップを認証するため、またユーザが購入した商品の代金支払いのために課金サイトを含んでもよい。　
　ネットワークシステム１００はＣＡＬＳ（Continuous Acquisition and Lifecycle Support）、ＣＡＤ（Computer aided design）／ＣＡＭ（Computer Aided Manufacturing）における設計や部品標準化に適用してもよい。ユーザ端末１０４は、設計者のＣＡＤマシンであってもよい。そこから設計者は部品データベース管理サーバへ要求を出す。これは、前記設計者が管理サーバへ送った候補と類似の部品を検索したり送信したりするために、オブジェクト探索サイト１２０の機能を含んでもよい。テキストのキーワードのみを使用し部品の形状を効果的に表現するのは時として困難を伴い、実施の形態によれば設計がより簡単になる。
【０１２８】
　他のオブジェクトとマッチングされるべき最初のオブジェクトは、必ずしもユーザによって選ばれる必要はない。検索サーバ１２２や他の本発明の形状解析器は、操作中いかなる時であっても任意の２つのオブジェクトの近似度を計算してもよい。類似のオブジェクトは、ユーザの要求がないときであっても表示され、再配列されてもよい。
【０１２９】
　オブジェクト探索サイト１２０は、ショッピングサイト１０８に保存されているオブジェクト以外を検索してもよい。オブジェクト探索サイト１２０は、ユーザの利便性を考慮して複数のショッピングサイトから類似のオブジェクトを選んでもよい。
【０１３０】
　上記説明において、様々な実験上の値が参考として得られた。実際の結果は使われるシステムにより変わる。例えば、ハードウェアにより実行された場合、より速い計算処理速度が得られる。
【０１３１】
　以上、本発明を、実施の形態をもとに説明した。この実施の形態は例示であり、それら各構成要素や各処理プロセスの組み合わせに変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者には理解されるところである。
【図面の簡単な説明】
【０１３２】
【図１】トーラスとそのレーブグラフを示す図である。
【図２】図２（ａ）、図２（ｂ）、図２（ｃ）はオブジェクトとその多重解像度レーブグラフを示す図である。
【図３】図３（ａ）、図３（ｂ）はオブジェクトの三次元データの例を示す図である。
【図４】図４（ａ）、図４（ｂ）は測地線距離によるモース関数の修正を示す図である。
【図５】図５（ａ）〜５（ｅ）はメッシュデータの再サンプリングと再分割の方法を示す図である。
【図６】図６（ａ）、図６（ｂ）はショートカットエッジの生成方法を示す図である。
【図７】Dijkstraのアルゴリズムを示す図である。
【図８】図８（ａ）〜８（ｄ）はオブジェクトのレーブグラフの生成を示す図である。
【図９】図９（ａ）、図９（ｂ）はオブジェクトのレーブグラフのノードのマッチング手順を示す図である。
【図１０】図１０（ａ）、図１０（ｂ）はオブジェクトの境界付近で分割した際に生じる不安定な解を示す図である。
【図１１】ふたつの多重解像度レーブグラフの各レベル間で種数の違いを示す数値を計算する手順を示す図である。
【図１２】図１２（ａ）〜１２（ｈ）は、種数の違いを計算するためのテーブルを示す図である。
【図１３】図１３（ａ）〜１３（ｆ）は、マッチングの実験に投入されたオブジェクトを示す図である。
【図１４】図１４（ａ）〜１４（ｆ）に示されるオブジェクトに関するマッチングの度合いを示す図である。
【図１５】実施の形態により、１６０のオブジェクトについて実験されたマッチングの結果、すなわち近似度を示す図である。
【図１６】実施の形態に係る形状解析器の機能ブロック図である。
【図１７】実施の形態に係る形状解析器を含むネットワークシステムの構成図である。
【符号の説明】
【０１３３】
１０　形状解析器
１４　点集合生成器
１６　モース評価器
１８　ＭＲＧ生成器
２０　ワークメモリ
２２　マッチングプロセッサ
３２　測地線距離計算器
３４　ユークリッド距離計算器
４６　ＣＲＧＧ（Coarse Reeb Graph Generator）
５０　対応検出器
５２　マッチング計算器
６０　３Ｄデータベース
６２　ＦＲＧ保持部
６４　ＭＲＧ保持部
６６　マッチング結果保持部
８０　主制御部
８２　ユーザインタフェイス
１００　ネットワークシステム
１０４，１０６　ユーザ端末
１０８　ショッピングサイト
１１０　ＷＷＷショッピングサーバ
１１２　データ保持部
１２０　オブジェクト検索サイト
１２２　ＷＷＷ検索サーバ
【図１】
2004118876.tif 000025
【図２】
2004118876.tif 000026
【図３】
2004118876.tif 000027
【図４】
2004118876.tif 000028
【図５】
2004118876.tif 000029
【図６】
2004118876.tif 000030
【図７】
2004118876.tif 000031
【図８】
2004118876.tif 000032
【図９】
2004118876.tif 000033
【図１０】
2004118876.tif 000034
【図１１】
2004118876.tif 000035
【図１２】
2004118876.tif 000036
【図１３】
2004118876.tif 000037
【図１４】
2004118876.tif 000038
【図１５】
2004118876.tif 000039
【図１６】
2004118876.tif 000040
【図１７】
2004118876.tif 000041