(57)【要約】【課題】形状の内部領域を考慮した、形状の輪郭に対するマッチング処理を行うこと。【解決手段】情報処理装置は、第１形状データと第２形状データとを入力する入力部と、第１形状データ及び第２形状データの輪郭における各点をサンプリングするサンプリング部と、第１形状データにおいてサンプリングされた各点に対し、第１形状データの内部領域に基づく第１形状記述子と、第２形状データにおいてサンプリングされた各点に対し、第２形状データの内部領域に基づく第２形状記述子とを設定する設定部と、第１形状記述子と第２形状記述子とを比較して、第１形状データの輪郭における各点と、第２形状データの輪郭における各点とを対応付けるマッチング部と、対応付けられた第１形状データの輪郭における点と、第２形状データの輪郭における点とのセットを出力する出力部と、を備える。【選択図】図２
2015115047.tif 000002
【特許請求の範囲】
【請求項１】
第１形状データと第２形状データとを入力する入力部と、
前記第１形状データ及び前記第２形状データの輪郭における各点をサンプリングするサンプリング部と、
前記第１形状データにおいてサンプリングされた各点に対し、前記第１形状データの内部領域に基づく第１形状記述子と、前記第２形状データにおいてサンプリングされた各点に対し、前記第２形状データの内部領域に基づく第２形状記述子とを設定する設定部と、
前記第１形状記述子と前記第２形状記述子とを比較して、前記第１形状データの輪郭における各点と、前記第２形状データの輪郭における各点とを対応付けるマッチング部と、
対応付けられた前記第１形状データの輪郭における点と、前記第２形状データの輪郭における点とのセットを出力する出力部と、
を備える情報処理装置。
【請求項２】
前記設定部は、
前記第１形状記述子として、前記サンプリングされた点と前記第１形状データ内部の各点との、前記第１形状データ内部を通る距離を並べ替えた第１測地的距離プロファイルを生成し、
前記第２形状記述子として、前記サンプリングされた点と前記第２形状データ内部の各点との、前記第２形状データ内部を通る距離を並べ替えた第２測地的距離プロファイルを生成する、請求項１記載の情報処理装置。
【請求項３】
前記設定部は、
前記第１形状データ及び前記第２形状データを複数の領域に分割し、各領域内の点を前記内部の点とする、請求項２記載の情報処理装置。
【請求項４】
前記設定部は、
三角形メッシュ分割を用いて、前記第１形状データ及び前記第２形状データを複数の領域に分割し、前記各領域内の点を、分割された三角形の中心点とする、請求項３記載の情報処理装置。
【請求項５】
前記設定部は、
前記各領域の面積を考慮して前記距離を並べ替えることにより、前記第１測地的距離プロファイル及び前記第２測地的距離プロファイルを生成する、請求項３又は４記載の情報処理装置。
【請求項６】
前記マッチング部は、
前記第１測地的距離プロファイルの対数と前記第２測地的距離プロファイルの対数とを計算し、計算された対数同士の差分の合計が最も小さくなるように対応付け処理を行う、請求項２乃至５いずれか一項に記載の情報処理装置。
【請求項７】
前記マッチング部は、
前記第１測地的距離プロファイルと、前記第２測地的距離プロファイルとにフィルタ処理を行い、フィルタ処理後の各測地的距離プロファイルの差分が最も小さくなるように対応付け処理を行う、請求項２乃至５いずれか一項に記載の情報処理装置。
【請求項８】
前記第１形状データ内に第１閉領域があり、前記第２形状データ内に第２閉領域がある場合、
前記設定部は、
前記第１形状データと前記第１閉領域との間にある領域に基づいて、前記第１閉領域の輪郭における各点の第３形状記述子を設定し、
前記第２形状データと前記第２閉領域との間にある領域に基づいて、前記第２閉領域の輪郭における各点の第４形状記述子を設定する、請求項１記載の情報処理装置。
【請求項９】
前記サンプリング部は、
前記第１形状データの内部面積と前記第２形状データの内部面積とが一致するように、前記第１形状データ又は前記第２形状データを拡大又は縮小する、請求項１乃至８いずれか一項に記載の情報処理装置。
【請求項１０】
コンピュータが実行する情報処理方法であって、
第１形状データと第２形状データとを入力するステップと、
前記第１形状データ及び前記第２形状データの輪郭における各点をサンプリングするステップと、
前記第１形状データにおいてサンプリングされた各点に対し、前記第１形状データの内部領域に基づく第１形状記述子と、前記第２形状データにおいてサンプリングされた各点に対し、前記第２形状データの内部領域に基づく第２形状記述子とを設定するステップと、
前記第１形状記述子と前記第２形状記述子とを比較して、前記第１形状データの輪郭における各点と、前記第２形状データの輪郭における各点とを対応付けるステップと、
対応付けられた前記第１形状データの輪郭における点と、前記第２形状データの輪郭における点とのセットを出力するステップと、
を含む情報処理方法。
【請求項１１】
請求項１０に記載の情報処理方法をコンピュータに実行させるためのプログラム。
【請求項１２】
請求項１１に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マッチング処理を行う情報処理装置、情報処理方法、プログラム及び記録媒体に関する。
【背景技術】
【０００２】
従来、異なる形状データの輪郭に対してマッチングを行う技術が数多く研究されてきた。一般的に用いられる２次元形状の輪郭マッチング方法では、輪郭線上での曲がり具合、例えば曲率などを用いてマッチングを行う技術がある（非特許文献１）。
【０００３】
また、３次元形状においては、例えば、３次元形状の２点間の表面上の距離を用いてマッチングを行う技術や、３次元形状表面の２点間のユークリッド距離を用いてマッチングを行う技術がある（非特許文献２、３）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Thomas W. Sederberg and Eugene Greenwood. 1992. A physically based approach to 2-D shape blending. In Proceedings of the 19th annual conference on Computer graphics and interactive techniques (SIGGRAPH'92), pp.25-34
【非特許文献２】Masaki Hilaga, Yoshihisa Shinagawa, Taku Kohmura, and Tosiyasu L. Kunii. 2001. Topology matching for fully automatic similarity estimation of 3D shape descriptor. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques (SIGGRAPH'01), ACM, New York, NY, USA, 203-212
【非特許文献３】Michael Kazhdan, Thomas Funkhouser, and Szymon Rusinkiewicz. 2003. Rotation invariant spherical harmonic representation of 3D shape descriptors. In Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing (SGP'03)
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術では、輪郭の曲がり具合や表面形状などを用いてマッチングを行うため、マッチング後の輪郭を用いてテクスチャトランスフォームなどを行うと、内部領域が歪んでいることが多い。これは、内部領域を考慮せずに、輪郭線や表面形状の点を用いてマッチングを行うことに起因すると考えられる。
【０００６】
そこで、本発明の所定の態様は、上記課題に鑑みてなされたものであり、形状の内部領域を考慮した、形状の輪郭に対するマッチング処理を行うことができる情報処理装置、情報処理方法、プログラム及び記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一態様における情報処理装置は、第１形状データと第２形状データとを入力する入力部と、前記第１形状データ及び前記第２形状データの輪郭における各点をサンプリングするサンプリング部と、前記第１形状データにおいてサンプリングされた各点に対し、前記第１形状データの内部領域に基づく第１形状記述子と、前記第２形状データにおいてサンプリングされた各点に対し、前記第２形状データの内部領域に基づく第２形状記述子とを設定する設定部と、前記第１形状記述子と前記第２形状記述子とを比較して、前記第１形状データの輪郭における各点と、前記第２形状データの輪郭における各点とを対応付けるマッチング部と、対応付けられた前記第１形状データの輪郭における点と、前記第２形状データの輪郭における点とのセットを出力する出力部と、を備える。これにより、形状の内部領域を考慮した、形状の輪郭に対するマッチング処理を行うことができる。
【０００８】
また、前記設定部は、前記第１形状記述子として、前記サンプリングされた点と前記第１形状データ内部の各点との、前記第１形状データ内部を通る距離を並べ替えた第１測地的距離プロファイルを生成し、前記第２形状記述子として、前記サンプリングされた点と前記第２形状データ内部の各点との、前記第２形状データ内部を通る距離を並べ替えた第２測地的距離プロファイルを生成してもよい。これにより、形状記述子として適切な測地的距離プロファイルを生成することができる。
【０００９】
また、前記設定部は、前記第１形状データ及び前記第２形状データを複数の領域に分割し、各領域内の点を内部の点としてもよい。これにより、適切な内部点の設定を容易にすることができる。
【００１０】
また、前記設定部は、三角形メッシュ分割を用いて、前記第１形状データ及び前記第２形状データを複数の領域に分割し、前記各領域内の点を、分割された三角形の中心点としてもよい。これにより、領域と内部点との対応関係を明確にすることができる。
【００１１】
また、前記設定部は、前記各領域の面積を考慮して前記距離を並べ替えることにより、前記第１測地的距離プロファイル及び前記第２測地的距離プロファイルを生成してもよい。これにより、内部領域の特徴をより反映した測地的距離プロファイルを生成することができる。
【００１２】
また、前記マッチング部は、前記第１測地的距離プロファイルの対数と前記第２測地的距離プロファイルの対数とを計算し、計算された対数同士の差分の合計が最も小さくなるように対応付け処理を行ってもよい。これにより、マッチングの精度をさらに向上させることができる。
【００１３】
また、前記マッチング部は、前記第１測地的距離プロファイルと、前記第２測地的距離プロファイルとにフィルタ処理を行い、フィルタ処理後の各測地的距離プロファイルの差分が最も小さくなるように対応付け処理を行ってもよい。これにより、用途に応じた輪郭のマッチング処理を行うことができる。
【００１４】
また、前記第１形状データ内に第１閉領域があり、前記第２形状データ内に第２閉領域がある場合、前記設定部は、前記第１形状データと前記第１閉領域との間にある領域に基づいて、前記第１閉領域の輪郭における各点の第３形状記述子を設定し、前記第２形状データと前記第２閉領域との間にある領域に基づいて、前記第２閉領域の輪郭における各点の第４形状記述子を設定してもよい。これにより、形状データの内部に閉領域がある場合に、この閉領域の輪郭についても適切なマッチング処理を行うことができる。
【００１５】
また、前記サンプリング部は、前記第１形状データの内部面積と前記第２形状データの内部面積とが一致するように、前記第１形状データ又は前記第２形状データを拡大又は縮小してもよい。これにより、マッチング対象の形状データのサイズが異なる場合であっても、適切に輪郭マッチング処理を行うことができる。
【００１６】
また、本発明の他の態様における情報処理方法は、コンピュータが実行する情報処理方法であって、第１形状データと第２形状データとを入力するステップと、前記第１形状データ及び前記第２形状データの輪郭における各点をサンプリングするステップと、前記第１形状データにおいてサンプリングされた各点に対し、前記第１形状データの内部領域に基づく第１形状記述子と、前記第２形状データにおいてサンプリングされた各点に対し、前記第２形状データの内部領域に基づく第２形状記述子とを設定するステップと、前記第１形状記述子と前記第２形状記述子とを比較して、前記第１形状データの輪郭における各点と、前記第２形状データの輪郭における各点とを対応付けるステップと、対応付けられた前記第１形状データの輪郭における点と、前記第２形状データの輪郭における点とのセットを出力するステップと、を含む。これにより、上記の情報処理装置と同様に、形状の内部領域を考慮した、形状の輪郭に対するマッチング処理を行うことができる。
【発明の効果】
【００１７】
本発明の所定の態様によれば、形状の内部領域を考慮した、形状の輪郭に対するマッチング処理を行うことができる。
【図面の簡単な説明】
【００１８】
【図１】実施形態における情報処理装置の概略構成の一例を示すブロック図である。
【図２】実施形態における情報処理装置の機能の一例を示すブロック図である。
【図３】実施形態におけるＲＡＭに含まれる各記憶部の例を示す図である。
【図４】実子形態におけるサンプリング部の構成の一例を示すブロック図である。
【図５】実施形態における設定部の構成の一例を示すブロック図である。
【図６】実施形態における測地的距離プロファイルを説明するための図である。
【図７】実施形態におけるマッチング部の構成の一例を示すブロック図である。
【図８】形状データの一例を示す図である。
【図９】複数の内部点の一例を示す図である。
【図１０】輪郭点と内部点との距離の一例を示す図である。
【図１１】距離を並べ替えたリストの一例を示す図である。
【図１２】領域分割の一例を示す図である。
【図１３】各領域の面積を反映したリストの一例を示す図である。
【図１４】測地的距離プロファイルの最終結果の一例を示す図である。
【図１５】三角形メッシュ分割を用いた場合の距離の計算の一例を示す図である。
【図１６】実施形態におけるマッチング処理までの概要を、イメージを用いて説明するための図である。
【図１７】実施形態における形状データの入力からマッチングまでの処理の一例を示すフローチャートである。
【図１８】実施形態における測地的距離プロファイルの生成処理の一例を示すフローチャートである。
【図１９】実験１に用いた形状データの一例を示す図である。
【図２０】実験１における輪郭マッチングを行う際の内部領域の歪み具合を示す図である。
【図２１】実験１における輪郭マッチングによりテクスチャトランスフォームされたテクスチャを示す図である。
【図２２】実験２に用いた形状データの一例を示す図である。
【図２３】実験２における輪郭マッチングを行う際の内部領域の歪み具合を示す図である。
【図２４】実験２における輪郭マッチングによりテクスチャトランスフォームされたテクスチャを示す図である。
【図２５】実験３に用いる形状データの一例を示す図である。
【図２６】実験３の実験結果を示す図である。
【図２７】実験４の実験結果を示す図である。
【発明を実施するための形態】
【００１９】
以下、添付図面を参照しながら本発明の実施形態について詳細に説明する。
【００２０】
［実施形態］
＜構成＞
図１は、実施形態における情報処理装置１０の概略構成の一例を示すブロック図である。図１に示すように、情報処理装置１０は、ＣＰＵ（Central Processing Unit）１０２と、ＲＡＭ（Random Access Memory）１０４と、ＲＯＭ（Read only Memory）１０６と、ドライブ装置１０８と、ネットワークＩ／Ｆ（Interface）１１０と、入力装置１１２と、及び表示装置１１４とを有する。これら各構成は、バスを介して相互にデータ送受信可能に接続されている。
【００２１】
ＣＰＵ１０２は、コンピュータの中で、各装置の制御やデータの演算、加工を行う制御部である。また、ＣＰＵ１０２は、ＲＡＭ１０４又はＲＯＭ１０６に記憶されたマッチング処理のプログラムを実行する演算装置である。ＣＰＵ１０２は、入力装置１１２やネットワークＩ／Ｆ１１０などから形状データを受け取り、演算、加工した上で、演算結果を表示装置１１４や記憶装置などに出力する。
【００２２】
ＲＡＭ１０４は、例えば主記憶部などである。ＲＡＭ１０４は、ＣＰＵ１０２が実行する基本ソフトウェアであるＯＳ（Operating System）やアプリケーションソフトウェアなどのプログラムやデータを記憶又は一時保存する記憶装置である。
【００２３】
ＲＯＭ１０６は、例えばアプリケーションソフトウェアなどに関連するデータを記憶する記憶装置である。
【００２４】
ドライブ装置１０８は、記録媒体１１６、例えばＣＤ−ＲＯＭやＳＤカードなどからプログラムを読み出し、記憶装置にインストールする。
【００２５】
また、記録媒体１１６に、所定のプログラムを格納し、この記録媒体１１６に格納されたプログラムはドライブ装置１０８を介して情報処理装置１０にインストールされる。インストールされた所定のプログラムは、情報処理装置１０により実行可能となる。
【００２６】
ネットワークＩ／Ｆ１１０は、通信機能を有する周辺機器と情報処理装置１０とのインターフェースである。また、ネットワークＩ／Ｆ１１０は、例えば、有線及び／又は無線回線などのデータ伝送路により構築されたＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）などのネットワークを介して接続される。
【００２７】
入力装置１１２は、カーソルキー、数字入力及び各種機能キー等を備えたキーボード、表示装置１１４の表示画面上でキーの選択等を行うためのマウスやスライドパッド等を有する。また、入力装置１１２は、ユーザがＣＰＵ１０２に操作指示を与えたり、データを入力したりするためのユーザインターフェースである。
【００２８】
表示装置１１４は、ＬＣＤ（Liquid Crystal Display）等により構成され、ＣＰＵ１０２から入力される表示データに応じた表示が行われる。なお、入力装置１１２や表示装置１１４は、情報処理装置１０の外部に設けられてもよい。
【００２９】
＜機能＞
次に、情報処理装置１０の機能について説明する。図２は、実施形態における情報処理装置１０の機能の一例を示すブロック図である。図２に示す情報処理装置１０は、入力部２０２と、サンプリング部２０４と、設定部２０６と、マッチング部２０８と、出力部２１０とを少なくとも有する。
【００３０】
なお、図２に示す各部は、例えばＣＰＵ１０２やワークメモリとしてのＲＡＭ１０４などにより実現されうる。ＣＰＵ１０２は、マッチング処理のプログラムを実行することで、各部の機能を実行することができる。
【００３１】
入力部２０２は、ＲＡＭ１０４、ＲＯＭ１０６、ネットワークＩ／Ｆ１１０、又は入力装置１１２から、ソース（source）の形状データとターゲット（target）の形状データとを入力する。以下では、ソースの形状データを第１形状データとも称し、ターゲットの形状データを第２形状データとも称する。入力部２０２は、入力された第１形状データ及び第２形状データをサンプリング部２０４に出力する。入力部２０２は、ソースとなる第１形状データを先に入力し、ターゲットとなる第２形状データを後に入力するようにしてもよい。
【００３２】
サンプリング部２０４は、第１形状データ及び第２形状データの輪郭における各点をサンプリングする。サンプリング部２０４は、入力部２０２から第１形状データ及び第２形状データを取得すると、それぞれの形状データの輪郭において、複数の点をサンプリングする。
【００３３】
サンプリング部２０４は、例えば、第１形状データ及び第２形状データの輪郭において、等間隔となるように輪郭点をサンプリングしていく。輪郭点とは、輪郭における点をいう。サンプリング部２０４は、第１形状データにおいてサンプリングした輪郭点と、第２形状データにおいてサンプリングされた輪郭点とをマッチング部２０８に出力する。
【００３４】
設定部２０６は、第１形状データにおいてサンプリングされた各点に対し、第１形状データの内部領域に基づく第１形状記述子と、第２形状データにおいてサンプリングされた各点に対し、第２形状データの内部領域に基づく第２形状記述子とを設定する。内部領域に基づく形状記述子とは、例えば、輪郭点と、形状データ内にある複数の各点との距離の集合をいう。
【００３５】
設定部２０６は、例えば、形状データの内部領域に複数の点（以下、内部点ともいう）を設け、サンプリングされた輪郭点と各内部点との各距離を並べ替えた測地的距離プロファイル（geodesic distance profile）を、形状記述子（shape descriptor）とする。このとき、設定部２０６は、輪郭点と内部点との距離を求める際、直線距離などではなく、形状の内部を通る距離を求める。
【００３６】
設定部２０６は、第１形状データに対する第１測地的距離プロファイルを第１形状記述とし、第２形状データに対する第２測地的距離プロファイルを第２形状記述子とする。設定部２０６は、設定した第１形状記述子と、第２形状記述子とをマッチング部２０８に出力する。
【００３７】
マッチング部２０８は、第１形状記述子と第２形状記述子とを比較して、第１形状データの輪郭における各点と、第２形状データの輪郭における各点とを対応付ける処理を行う。本実施形態において、マッチング処理とは、このような対応付け処理を含む。
【００３８】
マッチング部２０８は、例えば、設定部２０６から取得した第１形状記述子と、第２形状記述子との差分が最も小さくなるように、第１形状データの輪郭点と第２形状データの輪郭点とのマッチング処理を行う。
【００３９】
効率よくマッチング処理を行うため、マッチング部２０８は、動的計画法を用いて、第１形状データの輪郭点とマッチングする第２形状データの輪郭点を求めていけばよい。マッチング部２０８は、マッチングされた第１形状データの輪郭点と第２形状データの輪郭点とを組（セット）にし、出力部２１０に出力する。輪郭点は、例えば座標データなどで表されていればよい。
【００４０】
出力部２１０は、マッチングされた第１形状データの輪郭点と、第２形状データの輪郭点とのセットを出力する。出力部２１０は、例えば、第１形状データの全ての輪郭点において、それぞれマッチングされた第２形状データの輪郭点をセットにし、後段の処理部やＲＡＭ２０４又はＲＯＭ２０６に出力する。
【００４１】
次に、ＲＡＭ１０４に記憶されるデータについて説明する。図３は、実施形態におけるＲＡＭ１０４に含まれる各記憶部の例を示す図である。図３に示すＲＡＭ１０４は、形状データ記憶部３０２と、プロファイル記憶部３０４と、結果記憶部３０６とを含む。
【００４２】
形状データ記憶部３０２は、入力部１０２により入力された第１形状データと、第２形状データとを記憶する。形状データ記憶部３０２は、第１形状データを有する第１画像と、第２形状データとを有する第２画像とを記憶してもよい。
【００４３】
プロファイル記憶部３０４は、第１形状データの各輪郭点に対する第１測地的距離プロファイルと、第２形状データの各輪郭点に対する第２測地的距離プロファイルとを記憶する。測地的距離プロファイルの詳細は後述する。
【００４４】
結果記憶部３０６は、マッチング処理の結果を記憶する。マッチング処理の結果とは、第１形状データの各輪郭点に対し、マッチングされた第２形状データの輪郭点をセットにしたものである。
【００４５】
以上、上述した処理を行う情報処理装置１０は、各輪郭点に測地的距離プロファイルを対応付けて、この測地的距離プロファイルを用いて輪郭点のマッチング処理を行うことで、内部領域の歪みを防止するマッチング処理を行うことができる。
【００４６】
＜各部の処理例＞
次に、サンプリング部２０４、設定部２０６、及びマッチング部２０８の処理の一例について説明する。
【００４７】
図４は、実施形態におけるサンプリング部２０４の構成の一例を示すブロック図である。図４に示すサンプリング部２０４は、拡大縮小部４０２を含む。拡大縮小部４０２は、第１形状データの内部面積と第２形状データの内部面積とが一致するように、第１形状データ又は第２形状データを拡大又は縮小する。
【００４８】
拡大縮小部４０２は、例えば、第１形状データ及び第２形状データの内部面積をそれぞれ計算し、第１形状データの面積と一致するように、第２形状データの面積を拡大又は縮小する。サンプリング部２０４は、拡大又は縮小された第２形状データに対して輪郭点のサンプリングを行う。
【００４９】
なお、拡大縮小部４０２は、サンプリング部２０４の一部として説明したが、サンプリング部２０４とは別の機能として入力部２０２と、サンプリング部２０４との間に設けてもよい。拡大縮小部４０２を設けることにより、情報処理装置１０は、マッチング対象の形状データのサイズが異なる場合であっても、適切に輪郭マッチング処理を行うことができる。また、拡大縮小部４０２で行った処理の逆処理は、後段の処理において必要であれば、適切なタイミングで実行されればよい。
【００５０】
図５は、実施形態における設定部２０６の構成の一例を示すブロック図である。図５に示すように、設定部２０６は、プロファイル生成部５０２を含み、プロファイル生成部５０２は、領域分割部５０４と、距離計算部５０６と、面積計算部５０８と、並べ替え部５１０とを含む。
プロファイル生成部５０２は、以下の処理を行うことで、形状記述子として、サンプリングされた輪郭点と形状データの各内部点との、形状内部を通る距離を並べ替えた測地的距離プロファイルを生成する。
【００５１】
領域分割部５０４は、取得した形状データを複数の領域に分割する。例えば、領域分割部５０４は、三角形メッシュ分割を用いて形状データを三角形メッシュに分割する。領域分割部５０４は、三角形メッシュ分割を用いることで、後述する領域の面積や距離が計算しやすくなる。領域分割部５０４は、分割した領域の情報を距離計算部５０６と、面積計算部５０８とに出力する。
【００５２】
距離計算部５０６は、第１形状データの輪郭点ごとに、各内部点との距離を計算する。距離計算部５０６は、距離を求める際、内部領域を考慮するため、形状の内部を通る距離を計算する。距離計算部５０６は、第２形状データの輪郭点においても、各内部点との距離を計算する。三角形メッシュ分割を用いる場合の距離の計算方法については図１５を用いて後述する。距離計算部５０６は、第１形状データ及び第２形状データにおいて計算した、輪郭点ごとの各内部点との各距離を並べ替え部５１０に出力する。
【００５３】
面積計算部５０８は、取得した形状データの各領域の面積を計算する。例えば、面積計算部５０８は、形状データが三角形メッシュ分割されている場合、形状データ内の各三角形の面積を計算する。面積計算部５０８は、第１形状データ内の各領域の面積と、第２形状データ内の各領域の面積とを並べ替え部５１０に出力する。
【００５４】
並べ替え部５１０は、各輪郭点において計算された各距離を所定の基準に従って並べ替える。例えば、並べ替え部５１０は、小さい（短い）順に各距離を並べ替えて、縦軸を距離、横軸を内部点数としてリストを生成する。このリストが、測地的距離プロファイルとなる。
【００５５】
また、並べ替え部５１０は、このリストに対し、内部点の面積に比例して、横軸の幅を調整する。横軸の幅が調整された場合、横軸は、形状データの内部面積を表す。各領域の面積に応じてリストが生成されることで、プロファイル生成部５０２は、内部領域をより考慮した測地的距離プロファイルを生成することができる。
【００５６】
ここで、プロファイル生成部５０２により生成される測地的距離プロファイルについて図６を用いて説明する。図６は、実施形態における測地的距離プロファイルを説明するための図である。図６（Ａ）は、形状データ、及び輪郭点の一例を示す図である。図６（Ａ）に示す点ａ１１、ａ１２、ａ１３、ａ１４は、形状データｓｄ１１の輪郭において、サンプリング部２０４によりサンプリングされた複数の輪郭点を表す。図６（Ａ）に示す形状データｓｄ１１の各輪郭点に、測地的距離プロファイルが設定される。図６（Ａ）には、測地的距離プロファイルを設定する際に設けられる複数の内部点は図示していない。
【００５７】
例えば、輪郭点ａ１１における測地的距離プロファイルは、輪郭点ａ１１から各内部点までの形状データｓｄ１１内部を通る各距離を並べ替えた集合である。上述したように、測地的距離プロファイルは、形状データｓｄ１１内部の各領域の面積を考慮して生成されるのが好適である。
【００５８】
図６（Ｂ）は、各領域の面積を考慮した測地的距離プロファイルの一例を示す図である。図６（Ｂ）に示す測地的距離プロファイルは、各距離が小さい順に並べ替えられている。図６（Ｂ）に示すプロファイルｐｒ１１は、図６（Ａ）に示す輪郭点ａ１４の測地的距離プロファイルであり、図６（Ｂ）に示すプロファイルｐｒ１２は、図６（Ａ）に示す輪郭点ａ１２の測地的距離プロファイルであり、図６（Ｂ）に示すプロファイルｐｒ１３は、図６（Ａ）に示す輪郭点ａ１１の測地的距離プロファイルであり、図６（Ｂ）に示すプロファイルｐｒ１４は、図６（Ａ）に示す輪郭点ａ１３の測地的距離プロファイルである。
【００５９】
図６（Ｂ）に示す測地的距離プロファイルを用いて、このプロファイルが持つ意味を説明する。面積（又は内部点数）の軸の値が小さい部分（図６（Ｂ）ではＬｏｃａｌと表記する。）において、距離の値が大きい場合は、輪郭点において凸になっていることを表し、Ｌｏｃａｌにおいて、距離の値が小さい場合は、輪郭点において凹になっていることを表す。これは、輪郭点において凸になっていれば、この輪郭点周辺の内部点は、この輪郭点から離れており、輪郭点において凹になっていれば、この輪郭点周辺の内部点は、この輪郭点から近いことに起因する。
【００６０】
また、面積の軸の値が大きい部分（図６（Ｂ）ではＧｌｏｂａｌと表記する。）において、距離の値が大きい場合は、輪郭点が形状データの中心（又は重心など）から離れた位置にあることを表し、Ｇｌｏｂａｌにおいて、距離の値が小さい場合は、輪郭点が形状データの中心から近い位置にあることを表す。これは、輪郭点が中心に近ければ近いほど、輪郭点が中心から離れている場合に比べて、輪郭点から一番離れた内部点までの距離が小さくなることに起因する。
【００６１】
これにより、上述した測地的距離プロファイルは、形状データの内部領域を考慮した輪郭点の形状記述子となる。本実施形態では、この測地的距離プロファイルを用いて輪郭点のマッチングを行うことにより、従来技術では考慮されていなかった内部領域を考慮したマッチング処理を行うことが可能になる。
【００６２】
なお、プロファイル生成部５０２は、形状データの内部領域に適切に複数の内部点を分散して設定することができれば、領域分割部５０４及び面積計算部５０８を設けなくてもよい。したがって、並べ替え部５１０において、各領域の面積に応じてリストを調整する処理は、行われなくてもよい。
【００６３】
また、プロファイル生成部５０２は、形状データ内部に閉領域が存在する場合は、閉領域の輪郭点における測地的距離プロファイルを生成する際、形状データと閉領域との間にある内部領域に内部点を設ける。これにより、形状データ内部にある閉領域に対しても、後述する図２５に示すように、適切な輪郭マッチングを行うことができる。
【００６４】
図７は、実施形態におけるマッチング部２０８の構成の一例を示すブロック図である。図７に示すマッチング部２０８は、対数計算部６０２と、フィルタ処理部６０４とを含む。なお、対数計算部６０２と、フィルタ処理部６０４とは、マッチング部２０８とは別の機能として設けてもよい。
【００６５】
対数計算部６０２は、測地的距離プロファイルの各距離に対して対数を計算する。マッチング部２０８は、第１形状データにおいて対数が計算された各距離と、第２形状データにおいて対数が計算された各距離との差分に基づいて、第１形状データの輪郭点と、第２形状データの輪郭点とのマッチング処理を行う。
【００６６】
対数を計算することにより、マッチング部２０８がマッチング処理を行う際、距離が短い場合の差分と比べて、距離が長い場合の差分の影響を小さくすることができる。すなわち、マッチング部２０８は、対数が計算された距離を用いてマッチング処理を行うことで、より適切なマッチング結果を得ることができる。
【００６７】
フィルタ処理部６０４は、測地的距離プロファイルに含まれる各距離に対し、フィルタ処理を実行する。フィルタ処理部６０４は、例えばローパスフィルタ又はハイパスフィルタを用いる。マッチング部２０８は、ローパスフィルタを適用することで、Ｌｏｃａｌの影響を大きくし、形状の角部分を尊重するのに適したマッチング処理を行うことができる。Ｌｏｃａｌは、人間の視覚が敏感な部分であるため、マッチング部２０８は、より直感的なマッチング処理を行うことができる。また、マッチング部２０８は、ハイパスフィルタを適用することで、Ｇｌｏｂａｌの影響を大きくし、ノイズの影響を抑圧するのに適したマッチング処理を行うことができる。
【００６８】
フィルタ処理部２０８は、ローパスフィルタ、ハイパスフィルタのいずれを用いるかについて、用途に応じてユーザに適宜選択させるようにすればよい。
【００６９】
＜具体例＞
次に、具体的な例を用いて、測地的距離プロファイルの生成、距離計算、及びマッチング処理までの概要について説明する。まず、図８〜図１４を用いて測地的距離プロファイルの生成を説明する。
【００７０】
図８は、形状データの一例を示す図である。プロファイル生成部５０２は、図８に示す形状データｓｄ２１を入力したとする。
【００７１】
図９は、複数の内部点の一例を示す図である。図９に示すように、プロファイル生成部５０２は、所定のアルゴリズムに従って、形状データｓｄ２１の内部に複数の内部点を設定する。このとき、プロファイル生成部５０２は、内部点同士ができるだけ近づき過ぎないように分散して設定するとよい。
【００７２】
図１０は、輪郭点と内部点との距離の一例を示す図である。距離計算部５０６は、輪郭点ａ２１と内部点ｂ２１との距離ｄ２１、輪郭点ａ２１と内部点ｂ２２との距離ｄ２２、輪郭点ａ２１と内部点ｂ２３との距離ｄ２３、輪郭点ａ２１と内部点ｂ２４との距離ｄ２４を計算する。図１０に示すように、距離計算部５０６は、距離は、形状データｓｄ２１の内部を通る距離を計算する。これは、距離が形状データのｓｄ２１の内部領域の特徴を表すようにするためである。
【００７３】
図１１は、距離を並べ替えたリストの一例を示す図である。図１１に示すように、並べ替え部５１０は、距離計算部５０６により計算された各距離を、例えば小さい順に並べ替える。並べ替え部５１０により並べ替えられた各距離のリストが、測地的距離プロファイルとなる。
【００７４】
次に、内部領域の特徴をより反映させた測地的距離プロファイルについて説明する。図１２は、領域分割の一例を示す図である。図１２に示すように、領域分割部５０４は、形状データｓｄ２１を複数の領域ａｒ２１、ａｒ２２、ａｒ２３、ａｒ２４に分割する。領域分割部５０４は、各領域に１つの内部点が含まれるように分割する。なお、プロファイル生成部５０２は、領域分割部５０４により複数の領域に分割して内部点を設定するようにしてもよい。
【００７５】
面積計算部５０８は、分割された各領域の面積を計算する。ここで、領域ａｒ２１の面積をｓ１、領域ａｒ２２の面積をｓ２、領域ａｒ２３の面積をｓ３、領域ａｒ２４の面積をｓ４とする。
【００７６】
図１３は、各領域の面積を反映したリストの一例を示す図である。図１３に示すように、並べ替え部５１０は、各内部点に対し、各内部点を有する領域の面積に応じて横軸の幅を調整する。すなわち、各内部点の横軸の幅は、各内部点を有する面積の大きさに比例した長さになる。
【００７７】
図１４は、測地的距離プロファイルの最終結果の一例を示す図である。図１４に示すプロファイルｐｒ２１が、輪郭点ａ２１に対応付けられる形状記述子としての最終的な測地的距離プロファイルとなる。
【００７８】
次に、距離の計算方法について説明する。図１５は、三角形メッシュ分割を用いた場合の距離の計算の一例を示す図である。図１５に示す（１）では、形状データｓｄ３１が、領域分割部５０４により三角形メッシュ分割されている。
【００７９】
図１５に示す（２）では、領域分割部５０４により、各三角形の中心が各内部点ｂ３１、ｂ３２、ｂ３３、ｂ３４に設定される。三角形の中心を内部点とする理由は、内部点と領域との関係が１対１で対応しやすくなるからである。
【００８０】
図１５に示す（３）では、距離計算部５０６により、各三角形の中心から、その中心を含む三角形の各頂点及び隣接する他の三角形の中心までのパスが設定される。なお、各三角形の辺もパスとして設定される。
【００８１】
図１５に示す（４）では、距離計算部５０６により、輪郭点ａ３１から各内部点までの最短のパスの長さが距離として計算される。
【００８２】
このとき、距離計算部５０６は、輪郭点ａ３１と内部点ｂ３１との距離をパスｐｓ３１の長さとし、輪郭点ａ３１と内部点ｂ３２との距離をパスｐｓ３１とパスｐｓ３２との長さとし、輪郭点ａ３１と内部点ｂ３３との距離をパスｐｓ３３とパスｐｓ３４との長さとし、輪郭点ａ３１と内部点ｂ３４との距離をパスｐｓ３３とパスｐｓ３５との長さとする。これにより、距離計算部５０６は、形状データの内部を通る距離を比較的容易に計算することができる。
【００８３】
次に、マッチング処理までの概要について図１６を用いて説明する。図１６は、実施形態におけるマッチング処理までの概要を、イメージを用いて説明するための図である。図１６に示す（１）では、入力部２０２は、形状データｓｄ３１と、形状データｓｄ４１とを入力する。
【００８４】
図１６に示す（２）では、設定部２０６は、サンプリングされた輪郭点ごとに、測地的距離プロファイルを設定する。プロファイルｐｒ３１は、形状データｓｄ３１の輪郭点ａ３１の測地的距離プロファイルを表す。また、プロファイルｐｒ４１は、形状データｓｄ４１の輪郭点ａ４１の測地的距離プロファイルを表す。
【００８５】
図１６に示す（３）では、マッチング部２０８は、測地的距離プロファイルの距離（ｄ）に対し、対数を計算する。プロファイルｐｒ３２は、対数計算後の測地的距離プロファイルを表し、プロファイルｐｒ４２は、対数計算後の測地的距離プロファイルを表す。
【００８６】
図１６に示す（４）では、マッチング部２０８は、対数計算後の測地的距離プロファイル同士の差分を計算し、この差分を基に、２つの形状データにおける輪郭点のマッチング処理を行う。差分は、例えば二乗誤差などがある。マッチング部２０８は、１つの形状データの所定の輪郭点において、測地的距離プロファイルの差分が最も小さくなる他の形状データの輪郭点を求める。
【００８７】
以上のマッチング処理を行うことで、形状データの内部領域を考慮した輪郭点のマッチング処理が行われる。さらに、内部点を含む領域の面積や、距離（ｄ）の対数を計算することにより、情報処理装置１０は、マッチングの精度を向上させることができる。
【００８８】
＜動作＞
次に、情報処理装置１０の動作について説明する。図１７は、実施形態における形状データの入力からマッチングまでの処理の一例を示すフローチャートである。図１７に示すステップＳ１０２で、入力部２０２は、第１形状データと第２形状データとを入力する。入力部２０２は、ソースとなる第１形状データを先に入力し、ターゲットとなる第２形状データを後に入力するようにしてもよい。
【００８９】
ステップＳ１０４で、サンプリング部２０４は、第１形状データにおける輪郭点、及び第２形状データにおける輪郭点をサンプリングする。サンプリング部２０４は、なるべく等間隔になるように輪郭点をサンプリングする。
【００９０】
ステップＳ１０６で、設定部２０６は、第１形状データの輪郭点において第１形状記述子を設定し、第２形状データの輪郭点において第２形状記述子を設定する。ここで、形状記述子とは、例えば、上述したような形状データの内部領域を考慮した測地的距離プロファイルである。測地的距離プロファイルの生成については、図１８を用いて説明する。
【００９１】
ステップＳ１０８で、マッチング部２０８は、第１形状記述子と第２形状記述子とを比較して、第１形状データの輪郭における各点と、第２形状データの輪郭における各点との対応付けを行う。例えば、マッチング部２０８は、第１形状データの輪郭点に対し、対数が計算された距離を有する測地的距離プロファイル同士の二乗誤差が最も小さくなる第２形状データの輪郭点を求める。マッチング部２０８は、第１形状データの全ての輪郭点に対し、マッチングする第２形状データの輪郭点を求める。
【００９２】
ステップＳ１１０で、出力部２１０は、マッチング処理により求められた第１形状データの輪郭点と、第２形状データの輪郭点との組を出力する。
【００９３】
以上の処理を行うことで、情報処理装置１０は、形状の内部領域を考慮した、形状の輪郭に対するマッチング処理を行うことができる。
【００９４】
図１８は、実施形態における測地的距離プロファイルの生成処理の一例を示すフローチャートである。図１８に示す処理は、１つの形状データでサンプリングされた全輪郭点において、測地的距離プロファイルを生成する処理を示す。
【００９５】
ステップＳ２０２で、領域分割部５０４は、形状データを複数の領域に分割する。例えば、領域分割部５０４は、三角形メッシュ分割を用いて形状データを複数の領域に分割する。
【００９６】
ステップＳ２０４で、面積計算部５０８は、分割された各領域の面積を計算する。例えば、面積計算部５０８は、三角形メッシュ分割された各三角形の面積を計算する。
【００９７】
ステップＳ２０６で、距離計算部５０６は、形状データの任意の１つの輪郭点と、形状データの各内部点との距離を計算する。距離計算部５０６は、形状データの内部を通る距離を計算する。
【００９８】
ステップＳ２０８で、並べ替え部５１０は、１つの輪郭点における各距離を小さい順に並べ替えてリストを生成する。このリストが、測地的距離プロファイルとなる。
【００９９】
ステップＳ２１０で、並べ替え部５１０は、各領域の面積を測地的距離プロファイルに反映する。反映の仕方は、図１３を用いて説明したように、リストにおける内部点の軸の幅を、その内部点を含む領域の面積に比例して調整する。これにより、各領域の面積が反映された測地的距離プロファイルが生成される。
【０１００】
ステップＳ２１２で、プロファイル生成部５０２は、全ての輪郭点において測地的距離プロファイルを生成したかを判定する。全輪郭点において測地的距離プロファイルが生成されていれば（ステップＳ２１２−ＹＥＳ）プロファイル生成処理が終了する。全輪郭点において測地的距離プロファイルが生成されていなければ（ステップＳ２１２−ＮＯ）別の輪郭点における測地的距離プロファイルを生成するため、ステップＳ２０６の処理が再び実行される。
【０１０１】
以上の処理を行うことで、プロファイル生成部５０２は、形状データの内部の特徴を好適に反映する測地的距離プロファイルを生成することができる。
【０１０２】
＜実験結果＞
次に、本実施形態における方法と、従来の輪郭マッチングでよく用いられる非特許文献１の方法（curved based method）との実験結果を以下に示す。本実施形態の方法は、三角形メッシュ分割、各領域の面積を反映した測地的距離プロファイルを用いる。従来の方法は、輪郭の長さのパラメータと角度のパラメータとを用いてマッチングを行う。角度のパラメータには、重みｗが乗算される。なお、この重みｗは、ユーザにより適切な値が設定される必要がある。
【０１０３】
（実験１）
図１９は、実験１に用いた形状データの一例を示す図である。図１９（Ａ）は、ソースとなる第１形状データを示し、図１９（Ｂ）は、ターゲットとなる第２形状データを示す。図１９に示す形状データは、三角形メッシュ分割された状態の形状データである。情報処理装置１０は、第１形状データの輪郭点が、第２形状データのどの輪郭点にマッチングするかを求める。
【０１０４】
図２０は、実験１における輪郭マッチングを行う際の内部領域の歪み具合を示す図である。図２０（Ａ）は、第１形状データの内部領域の状態を示す。図２０（Ｂ）は、本実施形態によりマッチングされた輪郭点に基づく内部領域を示す。図２０（Ａ）と図２０（Ｂ）とを参照すると、第１形状データの頭や足などは、第２形状データにおいても適切に対応付けられている。よって、内部領域の歪の防止を図ることができる。
【０１０５】
図２０（Ｃ）は、ｗ＝１とした場合の従来方法によりマッチングされた輪郭点に基づく内部領域を示す。図２０（Ｃ）に示す矢印の部分は、本来は第１形状データの目部分の輪郭が対応付けられるはずが、実際は首部分の輪郭が対応付けられている。これは、マッチング処理が適切ではなく、このマッチング処理が用いられると内部領域が歪んでしまうことを示している。
【０１０６】
図２０（Ｄ）は、ｗ＝１０とした場合の従来方法によりマッチングされた輪郭点に基づく内部領域を示す。図２０（Ｄ）に示す矢印の部分は、本来は第１形状データの前足部分の輪郭が対応付けられるはずが、実際は尾部分の輪郭が対応付けられている。これは、マッチング処理が適切ではなく、このマッチング処理が用いられると内部領域が歪んでしまうことを示している。
【０１０７】
図２１は、実験１における輪郭マッチングによりテクスチャトランスフォームされたテクスチャを示す図である。図２１（Ａ）は、第１形状データに動物Ａ（例えば猫）を貼り付けた状態を示す。図２１（Ｂ）は、本実施形態によりテクスチャトランスフォームされた動物Ａを示す。図２１（Ａ）と図２１（Ｂ）とを参照すると、第１形状データの輪郭は、第２形状データの輪郭において適切に対応付けられている。よって、内部領域の歪の防止を図ることができる。
【０１０８】
図２１（Ｃ）は、ｗ＝１とした場合の従来方法によりテクスチャトランスフォームされた動物Ａ（例えば猫）を示す。図２１（Ｄ）は、ｗ＝１０とした場合の従来方法によりテクスチャトランスフォームされた動物Ａを示す。図２１（Ｃ）と図２１（Ｄ）とに示す矢印部分は、図２０同様、輪郭点のマッチングが適切に行われなかった箇所を示す。特に、図２１（Ｄ）に示す例では、ほとんどの輪郭点のマッチングが適切に行われていない。
【０１０９】
（実験２）
図２２は、実験２に用いた形状データの一例を示す図である。図２２（Ａ）は、ソースとなる第１形状データを示し、図２２（Ｂ）は、ターゲットとなる第２形状データを示す。図２２に示す形状データは、三角形メッシュ分割された状態の形状データである。情報処理装置１０は、第１形状データの輪郭点が、第２形状データのどの輪郭点にマッチングするかを求める。
【０１１０】
図２３は、実験２における輪郭マッチングを行う際の内部領域の歪み具合を示す図である。図２３（Ａ）は、第１形状データの内部領域の状態を示す。図２３（Ｂ）は、本実施形態によりマッチングされた輪郭点に基づく内部領域を示す。図２３（Ａ）と図２３（Ｂ）とを参照すると、第１形状データの頭や足などは、第２形状データにおいても適切に対応付けられている。よって、内部領域の歪の防止を図ることができる。
【０１１１】
図２３（Ｃ）は、ｗ＝１とした場合の従来方法によりマッチングされた輪郭点に基づく内部領域を示す。図２３（Ｃ）に示す矢印の部分は、本来は第１形状データの足先部分の輪郭が対応付けられるはずが、実際は尾部分の輪郭が対応付けられている。これは、マッチング処理が適切ではなく、このマッチング処理が用いられると内部領域が歪んでしまうことを示している。
【０１１２】
図２３（Ｄ）は、ｗ＝１０とした場合の従来方法によりマッチングされた輪郭点に基づく内部領域を示す。図２３（Ｄ）に示す矢印の部分は、本来は第１形状データの後足の一部分の輪郭が対応付けられるはずが、実際は後足の先部分の輪郭が対応付けられている。これは、マッチング処理が適切ではなく、このマッチング処理が用いられると内部領域が歪んでしまうことを示している。
【０１１３】
図２４は、実験２における輪郭マッチングによりテクスチャトランスフォームされたテクスチャを示す図である。図２４（Ａ）は、第１形状データに動物Ｂ（例えば犬）のテクスチャを貼り付けた状態を示す。図２４（Ｂ）は、本実施形態によりテクスチャトランスフォームされた動物Ｂ）を示す。図２４（Ａ）と図２４（Ｂ）とを参照すると、第１形状データの輪郭は、第２形状データの輪郭において適切に対応付けられている。よって、内部領域の歪の防止を図ることができる。
【０１１４】
図２４（Ｃ）は、ｗ＝１とした場合の従来方法によりテクスチャトランスフォームされた動物Ｂ（例えば犬）を示す。図２４（Ｄ）は、ｗ＝１０とした場合の従来方法によりテクスチャトランスフォームされた動物Ｂを示す。図２４（Ｃ）と図２４（Ｄ）とに示す矢印部分は、図２３同様、輪郭点のマッチングが適切に行われなかった箇所を示す。
【０１１５】
上記実験１及び実験２に示すとおり、本実施形態の輪郭マッチングによれば、内部領域の歪みを防止することができる。また、従来方法では、重みによってマッチングされた輪郭点は大きく異なる。この重みは、ユーザにより入力されるため、ユーザは、何度も重みを入力し、最適な重みを見つけなければならない。一方で、本実施形態における方法では、ユーザにより設定されるパラメータはなく、自動で適切な輪郭のマッチング処理を行うことができる。
【０１１６】
（実験３）
次に、形状データの内部に閉領域がある場合に、本実施形態の方法と、上記従来方法との実験結果について説明する。図２５は、実験３に用いる形状データの一例を示す図である。図２５（Ａ）は、ソースとなる第１形状データを示し、図２５（Ｂ）は、ターゲットとなる第２形状データを示す。図２５に示すように、形状データ内部には、閉領域が存在する。
【０１１７】
図２６は、実験３の実験結果を示す図である。図２６（Ａ）は、従来方法によりマッチングされた輪郭点に基づく内部領域を示す。図２５（Ａ）と図２６（Ａ）とに示すとおり、矢印が異なる部分を指すので、閉領域の輪郭マッチングは適切に行われていないことが分かる。この理由は、従来方法では、形状データの輪郭と、内部の閉領域の輪郭とが独立してマッチング処理が行われるからである。
【０１１８】
図２６（Ｂ）は、本実施形態の方法によりマッチングされた輪郭点に基づく内部領域を示す。図２５（Ａ）と図２６（Ｂ）とに示すとおり、矢印はほぼ同じ部分を指すので、閉領域の輪郭マッチングは適切に行われていることが分かる。この理由は、閉領域の輪郭において、形状データと閉領域との間にある内部領域の特徴が形状記述子としてマッチングに用いられるからである。
【０１１９】
（実験４）
次に、マッチング処理を行う際に、測地的距離プロファイルにフィルタ処理を施す場合の実験結果について説明する。図２７は、実験４の実験結果を示す図である。図２７（Ａ）は、ソースとなる形状データ及び内部領域を示す。
【０１２０】
図２７（Ｂ）は、ターゲットとなる形状データと、フィルタ処理なしの測地的距離プロファイルを用いた場合の内部領域を示す。図２７（Ｂ）に示す矢印によれば、ソース形状データとターゲット形状データとは、左右逆の輪郭にマッチングされている。
【０１２１】
図２７（Ｃ）は、ターゲットとなる形状データと、ローパスフィルタ処理ありの測地的距離プロファイルを用いた場合の内部領域を示す。図２７（Ｃ）に示す矢印によれば、ソースとなる形状データと、ターゲットとなる形状データとは、適切に輪郭マッチングが行われている。これは、測地的距離プロファイルにローパスフィルタを通すことで、マッチング処理において、Ｌｏｃａｌ部分が示す輪郭の凹凸の影響が強くなるからである。
【０１２２】
以上、本実施形態によれば、形状の内部領域を考慮した、形状の輪郭に対するマッチング処理を行うことができる。また、本実施形態によれば、内部領域を考慮した形状記述子として、測地的距離プロファイルを用いることにより、内部領域を考慮した輪郭マッチング処理を適切に行うことができる。
【０１２３】
なお、上記の情報処理装置１０で実行されるプログラムについて、実際のハードウェアとしては、ＣＰＵ１０２がＲＯＭ１０６からプログラムを読み出して実行することにより、上記各部のうち１又は複数の各部がＲＡＭ１０４上にロードされ、１又は複数の各部がＲＡＭ１０４上に生成されるようになっている。
【０１２４】
このように、上述した実施形態で説明したマッチング処理は、コンピュータに実行させるためのプログラムとして実現されてもよい。このプログラムをサーバ等からインストールしてコンピュータに実行させることで、前述したマッチング処理を実現することができる。
【０１２５】
また、このプログラムを記録媒体１１６に記録し、このプログラムが記録された記録媒体１１６をコンピュータに読み取らせて、前述したマッチング処理を実現させることも可能である。
【０１２６】
なお、記録媒体１１６は、ＣＤ−ＲＯＭ、フレキシブルディスク、光磁気ディスク等の様に情報を光学的，電気的或いは磁気的に記録する記録媒体、ＲＯＭ、フラッシュメモリ等の様に情報を電気的に記録する半導体メモリ等、様々なタイプの記録媒体を用いることができる。
【０１２７】
以上、実施形態について詳述したが、上記実施形態に限定されるものではなく、特許請求の範囲に記載された範囲内において、上記実施形態以外にも種々の変形及び変更が可能である。
【０１２８】
例えば、上記実施形態では、２次元の形状データを例にして説明したが、３次元の形状データについても、内部領域を考慮した形状記述子を輪郭点に設定することができる。よて、本実施形態は、３次元の形状データ同士の輪郭マッチングにも適用することができる。
【０１２９】
また、本実施形態により処理されたマッチング結果は、アニメーションにおいて、例えば最初のフレームと最後のフレームとのキーフレームが与えられたときに、キーフレーム間のフレーム内にある形状データの補間処理に適用することができる。
【０１３０】
また、このマッチング結果は、形状データの模様を移すテクスチャトランスフォームや、写真編集又は形状変形などのデフォーメーションにも適用することができる。さらに、このマッチング結果は、データベースに形状データが数多くある場合に、検索のキーとして適用することができたり、形状分類の分類識別子として適用することができたりする。
【０１３１】
また、このマッチング結果は、アニメの彩色にも適用することができる。例えば、１フレーム目の形状データに色を塗り、２フレーム目以降の形状データには、マッチング結果を用いてどこの輪郭部分にどの色を塗るかを自動的に判別することができる。
【符号の説明】
【０１３２】
１０  情報処理装置
１０２  ＣＰＵ
１０４  ＲＡＭ
１０６  ＲＯＭ
２０２  入力部
２０４  サンプリング部
２０６  設定部
２０８  マッチング部
２１０  出力部
４０２  拡大縮小部
５０２  プロファイル生成部
５０４  領域分割部
５０６  距離計算部
５０８  面積計算部
５１０  並べ替え部
６０２  対数計算部
６０４  フィルタ処理部
【図１】
2015115047.tif 000003
【図２】
2015115047.tif 000004
【図３】
2015115047.tif 000005
【図４】
2015115047.tif 000006
【図５】
2015115047.tif 000007
【図６】
2015115047.tif 000008
【図７】
2015115047.tif 000009
【図８】
2015115047.tif 000010
【図９】
2015115047.tif 000011
【図１０】
2015115047.tif 000012
【図１１】
2015115047.tif 000013
【図１２】
2015115047.tif 000014
【図１３】
2015115047.tif 000015
【図１４】
2015115047.tif 000016
【図１５】
2015115047.tif 000017
【図１６】
2015115047.tif 000018
【図１７】
2015115047.tif 000019
【図１８】
2015115047.tif 000020
【図１９】
2015115047.tif 000021
【図２２】
2015115047.tif 000022
【図２５】
2015115047.tif 000023
【図２６】
2015115047.tif 000024
【図２７】
2015115047.tif 000025
【図２０】
2015115047.tif 000026
【図２１】
2015115047.tif 000027
【図２３】
2015115047.tif 000028
【図２４】
2015115047.tif 000029