(57)【要約】２つの３Ｄマルチコンポーネントモデル間の誤差メトリックを計算するために、第１の３Ｄモデルの３Ｄコンポーネントのファセットが一様にサンプリングされる。第１の３Ｄモデル中の各サンプリング点と、第２の３Ｄモデルの表面との間で、点−面間誤差が計算される。次いで、点−面間誤差を処理して、第１と第２の３Ｄモデル間の誤差メトリックが生成される。算出を加速させるために、第２の３Ｄモデルをセルに区分化することができ、第１の３Ｄモデル中の特定のサンプリング点に最も近いセルのみを使用して、点−面間誤差が計算される。３Ｄモデル中の個々の３Ｄコンポーネントについての誤差メトリックを算出するとき、同じ一様サンプリングおよびセル区分化が利用される。したがって、３Ｄモデル全体の誤差は、ほぼ、個々のコンポーネントについて算出された誤差の重み付き平均である。
2015517154.tif 000002
【特許請求の範囲】
【請求項１】
第１の３Ｄモデルと第２の３Ｄモデルとの間の誤差メトリックを決定する方法であって、
前記第１の３Ｄモデルおよび前記第２の３Ｄモデルにアクセスするステップであって、前記第１の３Ｄモデルは第１の３Ｄコンポーネントおよび少なくとも１つの別の３Ｄコンポーネントを含む、ステップと、
前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントおよび前記少なくとも１つの別の３Ｄコンポーネントのファセット中でサンプリング点を決定するステップであって、前記サンプリング点は、前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントおよび前記少なくとも１つの別の３Ｄコンポーネントの前記ファセット中で一様に分布する、ステップと、
前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネント中の各サンプリング点と、前記第２の３Ｄモデル中の第１の３Ｄコンポーネントの表面との間の、点−面間誤差を決定する（５５０）ステップであって、前記第２の３Ｄモデル中の前記第１の３Ｄコンポーネントは前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントに対応する、ステップと、
前記決定された点−面間誤差に応じて、前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントと前記第２の３Ｄモデル中の前記第１の３Ｄコンポーネントとの間の誤差メトリックを決定する（５６０）ステップと、
を含む、前記方法。
【請求項２】
前記第１の３Ｄモデル中の前記少なくとも１つの別の３Ｄコンポーネント中の各サンプリング点と、前記第２の３Ｄモデル中の少なくとも１つの別の３Ｄコンポーネントの表面との間の、第２の点−面間誤差を決定する（５５０）ステップであって、前記第２の３Ｄモデル中の前記少なくとも１つの別の３Ｄコンポーネントは前記第１の３Ｄモデル中の前記少なくとも１つの別の３Ｄコンポーネントに対応する、ステップと、
前記決定された第２の点−面間誤差に応じて、前記第１の３Ｄモデル中の前記少なくとも１つの別の３Ｄコンポーネントと前記第２の３Ｄモデル中の前記少なくとも１つの別の３Ｄコンポーネントとの間の誤差メトリックを決定する（５６０）ステップと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記第１の３Ｄモデル中の各サンプリング点と前記第２の３Ｄモデルの表面との間の第３の点−面間誤差を決定する（５５０）ステップと、
前記決定された第３の点−面間誤差に応じて、前記第１の３Ｄモデルと前記第２の３Ｄモデルとの間の前記誤差メトリックを決定する（５６０）ステップであって、前記第１の３Ｄモデルについての前記誤差メトリックは、前記第１の３Ｄコンポーネントについての前記誤差メトリックと、前記少なくとも１つの別の３Ｄコンポーネントについての前記誤差メトリックとの重み付き合計に対応する、ステップと、
をさらに含む、請求項２に記載の方法。
【請求項４】
前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネント中のサンプリング点の数は、前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントの前記ファセットのサイズにほぼ比例する、請求項１に記載の方法。
【請求項５】
前記サンプリング点は前記第１の３Ｄモデル中のエッジの平均長さに応じて決定される、請求項１に記載の方法。
【請求項６】
前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネント中の特定の１つのサンプリング点について、
前記第２の３Ｄモデルを、前記第２の３Ｄモデル中の前記第１の３Ｄコンポーネントに対応する１組のセルを含む複数のセルに区分化する（５４０）ステップと、
前記１組のセルから、前記特定の１つのサンプリング点に最も近いセルを決定するステップと、
前記特定の１つのサンプリング点と前記最も近いセル内のそれぞれのファセットとの間のそれぞれの距離を決定するステップと、
前記決定されたそれぞれの距離のうちの最も短い距離を、前記特定の１つのサンプリング点と前記第２の３Ｄモデル中の前記第１の３Ｄコンポーネントの表面との間の点−面間誤差として決定する（５５０）ステップと、
をさらに含む、請求項１に記載の方法。
【請求項７】
符号化器におけるレート歪み最適化と、前記第２の３Ｄモデルが品質要件を満たすかどうかの検証と、のうちの少なくとも一方を実行するステップをさらに含む、請求項１に記載の方法。
【請求項８】
第１の３Ｄモデルと第２の３Ｄモデルとの間の法線変化量を決定する方法であって、
前記第１の３Ｄモデルおよび前記第２の３Ｄモデルからの複数のファセット対にアクセスする（８１０）ステップであって、各ファセット対は前記第１の３Ｄモデルからのファセットと前記第２の３Ｄモデルからの対応するファセットとに対応する、ステップと、
前記複数のファセット対の各々についてファセット法線ベクトルの内積を決定する（８２０）ステップと、
前記内積に応じて前記第１の３Ｄモデルと前記第２の３Ｄモデルとの間の前記法線変化量を決定する（８２０）ステップと、
を含む、前記方法。
【請求項９】
第１の３Ｄモデルと第２の３Ｄモデルとの間の誤差メトリックを決定するための装置（９００）であって、
前記第１の３Ｄモデルおよび前記第２の３Ｄモデルにアクセスするプロセッサーであって、前記第１の３Ｄモデルは第１の３Ｄコンポーネントおよび少なくとも１つの別の３Ｄコンポーネントを含む、プロセッサーと、
前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントおよび前記少なくとも１つの別の３Ｄコンポーネントのファセット中でサンプリング点を決定するサンプラ（９２０）であって、前記サンプリング点は、前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントおよび前記少なくとも１つの別の３Ｄコンポーネントの前記ファセット中で一様に分布する、サンプラと、
前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネント中の各サンプリング点と、前記第２の３Ｄモデル中の第１の３Ｄコンポーネントの表面との間の、点−面間誤差を決定する誤差メトリック推定器（９４０）であって、前記第２の３Ｄモデル中の前記第１の３Ｄコンポーネントは前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントに対応し、前記決定された点−面間誤差に応じて、前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントと前記第２の３Ｄモデル中の前記第１の３Ｄコンポーネントとの間の誤差メトリックを決定する、誤差メトリック推定器と、
を備える、前記装置。
【請求項１０】
前記誤差メトリック推定器は、前記第１の３Ｄモデル中の前記少なくとも１つの別の３Ｄコンポーネント中の各サンプリング点と、前記第２の３Ｄモデル中の少なくとも１つの別の３Ｄコンポーネントの表面との間の、第２の点−面間誤差をさらに決定し、前記第２の３Ｄモデル中の前記少なくとも１つの別の３Ｄコンポーネントは前記第１の３Ｄモデル中の前記少なくとも１つの別の３Ｄコンポーネントに対応し、前記誤差メトリック推定器は、前記決定された第２の点−面間誤差に応じて、前記第１の３Ｄモデル中の前記少なくとも１つの別の３Ｄコンポーネントと前記第２の３Ｄモデル中の前記少なくとも１つの別の３Ｄコンポーネントとの間の誤差メトリックを決定する、請求項９に記載の装置。
【請求項１１】
前記誤差メトリック推定器は、前記第１の３Ｄモデル中の各サンプリング点と前記第２の３Ｄモデルの表面との間の第３の点−面間誤差をさらに決定し、前記決定された第３の点−面間誤差に応じて前記第１の３Ｄモデルと前記第２の３Ｄモデルとの間の前記誤差メトリックを決定し、前記第１の３Ｄモデルについての前記誤差メトリックは、前記第１の３Ｄコンポーネントについての前記誤差メトリックと、前記少なくとも１つの別の３Ｄコンポーネントについての前記誤差メトリックとの重み付き合計に対応する、請求項１０に記載の装置。
【請求項１２】
前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネント中のサンプリング点の数は、前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントの前記ファセットのサイズにほぼ比例する、請求項９に記載の装置。
【請求項１３】
前記サンプリング点は前記第１の３Ｄモデル中のエッジの平均長さに応じて決定される、請求項９に記載の装置。
【請求項１４】
セル区分化モジュール（９３０）をさらに備え、前記セル区分化モジュールは、前記第２の３Ｄモデルを、前記第２の３Ｄモデル中の前記第１の３Ｄコンポーネントに対応する１組のセルを含む複数のセルに区分化し、前記１組のセルから、前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネント中の特定の１つのサンプリング点に最も近いセルを決定し、前記特定の１つのサンプリング点と前記最も近いセル内のそれぞれのファセットとの間のそれぞれの距離を決定し、前記決定されたそれぞれの距離のうちの最も短い距離を、前記特定の１つのサンプリング点と前記第２の３Ｄモデル中の前記第１の３Ｄコンポーネントの表面との間の点−面間誤差として決定する、請求項９に記載の装置。
【請求項１５】
レート歪み最適化と、前記第２の３Ｄモデルが品質要件を満たすかどうかの検証と、のうちの少なくとも一方を実行する符号化器（２００）をさらに備える、請求項９に記載の装置。
【請求項１６】
第１の３Ｄモデルと第２の３Ｄモデルとの間の法線変化量を決定するための装置（９００）であって、
前記第１の３Ｄモデルおよび前記第２の３Ｄモデルからの複数のファセット対にアクセスするプロセッサーであって、各ファセット対は前記第１の３Ｄモデルからのファセットと前記第２の３Ｄモデルからの対応するファセットとに対応する、プロセッサーと、
前記複数のファセット対の各々についてファセット法線ベクトルの内積を決定し、前記内積に応じて前記第１の３Ｄモデルと前記第２の３Ｄモデルとの間の前記法線変化量を決定する法線変化量推定器（９１０）と、
を備える、前記装置。
【請求項１７】
請求項１乃至７のいずれか一項により第１の３Ｄモデルと第２の３Ｄモデルとの間の誤差メトリックを決定するための命令が記憶された、コンピュータ読取可能記憶媒体。
【請求項１８】
請求項８により第１の３Ｄモデルと第２の３Ｄモデルとの間の法線変化量を決定するための命令が記憶された、コンピュータ読取可能記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３Ｄモデルについての誤差メトリックを推定するための方法および装置に関する。
【背景技術】
【０００２】
関連出願
本出願は、参照により本明細書に組み込まれる２０１２年４月１９日に出願された国際特許出願第ＰＣＴ／ＣＮ２０１２／０７４３７０号の利益を主張するものである。
【０００３】
実用例で、多くの３Ｄモデルは、多数のコンポーネントからなる。図１に示すように、これらのマルチコンポーネント３Ｄモデルは普通、様々な変換において多くの反復構造を含む。
【０００４】
入力されたモデル中の反復構造を利用する、マルチコンポーネント３Ｄモデルに対する圧縮アルゴリズムが知られている。３Ｄモデルの反復構造が、様々な位置、配向、および倍率で発見される。次いで３Ｄモデルは、「パターン−インスタンス」表現に編成される。パターンは、対応する反復構造の代表的な幾何形状を指すのに使用される。反復構造に属するコンポーネントは、対応するパターンのインスタンスと呼ばれ、これは、パターンＩＤと、変換情報（例えば、パターンに対する反射、平行移動、回転、および可能なスケーリング）とによって表すことができる。インスタンス変換情報は、例えば、反射部分、平行移動部分、回転部分、および可能なスケーリング部分に編成することができる。３Ｄモデルの反復的でないコンポーネントがいくつかある場合もあり、これらは固有コンポーネントと呼ばれる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｎ．Ａｓｐｅｒｔ，Ｄ．Ｓａｎｔａ−Ｃｒｕｚ，ａｎｄ  Ｔ．Ｅｂｒａｈｉｍｉ，“ＭＥＳＨ：Ｍｅａｓｕｒｉｎｇ  ｅｒｒｏｒｓ  ｂｅｔｗｅｅｎ  ｓｕｒｆａｃｅｓ  ｕｓｉｎｇ  ｔｈｅ  Ｈａｕｓｄｏｒｆｆ  ｄｉｓｔａｎｃｅ，”Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｉｎ  Ｍｕｌｔｉｍｅｄｉａ  ａｎｄ  Ｅｘｐｏ（ＩＣＭＥ），ｐｐ．７０５−７０８，２００２
【発明の概要】
【０００６】
本原理は、第１の３Ｄモデルと第２の３Ｄモデルとの間の誤差メトリックを決定する方法を提供する。この方法は、前記第１の３Ｄモデルおよび前記第２の３Ｄモデルにアクセスするステップであって、前記第１の３Ｄモデルは第１の３Ｄコンポーネントおよび少なくとも１つの別の３Ｄコンポーネントを含む、ステップと、前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントおよび前記少なくとも１つの別の３Ｄコンポーネントのファセット中でサンプリング点を決定するステップであって、前記サンプリング点は、前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントおよび前記少なくとも１つの別の３Ｄコンポーネントの前記ファセット中で一様に分布する、ステップと、前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネント中の各サンプリング点と、前記第２の３Ｄモデル中の第１の３Ｄコンポーネントの表面との間の、点−面間（point-to-surface）誤差を決定するステップであって、前記第２の３Ｄモデル中の前記第１の３Ｄコンポーネントは前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントに対応する、ステップと、前述の前記決定された点−面間誤差に応じて、前記第１の３Ｄモデル中の前記第１の３Ｄコンポーネントと前記第２の３Ｄモデル中の前記第１の３Ｄコンポーネントとの間の誤差メトリックを決定するステップとを含む。本原理はまた、これらのステップを実施するための装置も提供する。
【０００７】
本原理はまた、前述の方法に従って第１の３Ｄモデルと第２の３Ｄモデルとの間の誤差メトリックを決定するための命令が記憶されたコンピュータ読取可能記憶媒体も提供する。
【０００８】
本原理はまた、第１の３Ｄモデルと第２の３Ｄモデルとの間の法線変化量を決定する方法も提供する。この方法は、前記第１の３Ｄモデルおよび前記第２の３Ｄモデルからの複数のファセット対にアクセスするステップであって、各ファセット対は前記第１の３Ｄモデルからのファセットと前記第２の３Ｄモデルからの対応するファセットとに対応する、ステップと、前記複数のファセット対の各々についてファセット法線ベクトルの内積を決定するステップと、前述の前記内積に応じて前記第１の３Ｄモデルと前記第２の３Ｄモデルとの間の前記法線変化量を決定するステップとを含む。本原理はまた、これらのステップを実施するための装置も提供する。
【０００９】
本原理はまた、前述の方法に従って第１の３Ｄモデルと第２の３Ｄモデルとの間の法線変化量を決定するための命令が記憶されたコンピュータ読取可能記憶媒体も提供する。
【図面の簡単な説明】
【００１０】
【図１】多数のコンポーネントと反復構造とを有する例示的な３Ｄモデルを示す図である。
【図２】本原理による３Ｄモデルの例示的な符号化器を示す図である。
【図３】本原理による３Ｄモデルの例示的な復号器を示す図である。
【図４Ａ】図４Ｂおよび４Ｃにそれぞれ示される２つの３Ｄコンポーネントからなる別の例示的な３Ｄモデルを示す図である。
【図４Ｂ】３Ｄコンポーネントを示す図である。
【図４Ｃ】３Ｄコンポーネントを示す図である。
【図５】本原理の実施形態による、２つの３Ｄモデル間の誤差メトリックを推定するための例を示す流れ図である。
【図６Ａ】図４のリンゴコンポーネントの３Ｄメッシュを示す絵画例の図である。
【図６Ｂ】図４のマルチコンポーネント３Ｄモデルの３Ｄメッシュを示す絵画例の図である。
【図６Ｃ】図４の葉コンポーネントの３Ｄメッシュを示す絵画例の図である。
【図６Ｄ】リンゴコンポーネントの一部を示す絵画例の図である。
【図６Ｅ】葉コンポーネントの一部を示す絵画例の図である。
【図６Ｆ】本原理の実施形態による、三角形のサンプリング点および内部三角形を示す絵画例の図である。
【図７Ａ】本原理の実施形態による、３Ｄモデルのセル区分化を示す絵で示した例の図である。
【図７Ｂ】本原理の実施形態による、セルに含まれる三角形およびファセットを示す絵画例の図である。
【図８】本原理の実施形態による、２つの３Ｄモデルの表面間の法線変化量を推定するための例を示す流れ図である。
【図９】本原理による例示的な品質推定器を示す図である。
【発明を実施するための形態】
【００１１】
図１に示すように、３Ｄモデル中には、多くの反復構造がある場合がある。３Ｄモデルを効率的に符号化するために、反復構造をパターンおよびインスタンスに編成することができる。インスタンスは、例えば対応するパターンのパターンＩＤと変換マトリックス（平行移動、回転、およびスケーリングに関する情報を含む）とを使用して、対応するパターンの変換として表される。
【００１２】
インスタンスがパターンＩＤおよび変換マトリックスによって表されるとき、パターンＩＤおよび変換マトリックスは、インスタンスの圧縮時に圧縮されることになる。したがって、インスタンスは、パターンＩＤおよび復号された変換マトリックスを介して再構築することができる。すなわち、インスタンスは、パターンＩＤによって索引付けされた復号済みパターンの変換（復号された変換マトリックスからの）として再構築することができる。
【００１３】
図２に、例示的な３Ｄモデル符号化器２００のブロック図を示す。装置２００の入力は、３Ｄモデルと、３Ｄモデルを符号化するための品質パラメータと、他のメタデータとを含み得る。まず、３Ｄモデルは、反復構造発見モジュール２１０を通る。反復構造発見モジュール２１０は、３Ｄモデルを、パターン、インスタンス、および固有コンポーネントで表して出力する。パターン符号化器２２０を利用してパターンが圧縮され、固有コンポーネント符号化器２５０を使用して固有コンポーネントが符号化される。例えば、インスタンスコンポーネント情報は、ユーザによって選択されたモードに基づいて符号化される。インスタンス情報グループモードが選択された場合は、インスタンス情報は、グループ化インスタンス情報符号化器２４０を使用して符号化される。そうでない場合は、基本インスタンス情報符号化器２３０を使用して符号化される。符号化されたコンポーネントはさらに、反復構造検証器２６０中で検証される。符号化されたコンポーネントがその品質要件を満たさない場合、そのコンポーネントは固有コンポーネント符号化器２５０によって符号化されることになる。ビットストリームアセンブラ２７０において、パターン、インスタンス、および固有コンポーネントのビットストリームが組み立てられる。
【００１４】
図３に、例示的な３Ｄモデル復号器３００のブロック図を示す。装置３００の入力は、３Ｄモデルのビットストリーム、例えば符号化器２００によって生成されたビットストリームを含みうる。圧縮ビットストリーム中のパターンに関する情報は、パターン復号器３２０によって復号される。固有コンポーネントに関する情報は、固有コンポーネント復号器３５０によって復号される。インスタンス情報の復号もまた、ユーザによって選択されたモードに依存する。インスタンス情報グループモードが選択された場合は、インスタンス情報は、グループ化インスタンス情報復号器３４０を使用して復号される。そうでない場合は、基本インスタンス情報復号器３３０を使用して復号される。復号されたパターン、インスタンス情報、および固有コンポーネントを使用して、モデル再構築モジュール３６０において、出力復号済み３Ｄモデルが生成される。
【００１５】
３Ｄモデル符号化器２００の反復構造検証器２６０中では、元のインスタンスコンポーネントと再構築されたコンポーネントとの間の誤差が比較される。誤差が、品質要件によって設定されたものよりも大きい場合は、インスタンスは固有コンポーネントとして符号化されることになる。本出願において、「距離」と「誤差」は両方とも、２つのモデル間の歪みを指すことができ、用語「距離」、「誤差」、および「歪み」は交換可能に使用される。
【００１６】
２つの３Ｄモデル間、例えば元の３Ｄモデルと圧縮解除された３Ｄモデルとの間の誤差を測定するために、いくつかの既存の方法は、表面サンプリング方法を採用して表面間の誤差を測定する。すなわち、２つの３Ｄモデルの表面間の誤差が、個々のサンプリング点ごとの、点−面間距離に基づいて算出される。これらの既存の方法では、サンプリング密度は、３Ｄモデルのバウンディングボックスのサイズに依存する。したがって、バウンディングボックスのサイズが様々である可能性のある個々のインスタンスコンポーネントの品質を検証するとき、サンプリング密度もまた個々のコンポーネントにより異なる。
【００１７】
表１に、図４Ａに示す例示的な３Ｄモデルについて、非特許文献１で述べられているようなＭＥＳＨによって推定される平均誤差を示す。この例では、図４Ｂおよび４Ｃにそれぞれ示すようなリンゴおよび葉は、２つの個別３Ｄコンポーネントと見なされ、図４Ａに示すようなリンゴと葉は共に、マルチコンポーネント３Ｄモデルと見なされる。３Ｄモデルが圧縮された後、元の３Ｄモデルと圧縮３Ｄモデルの表面間の誤差が測定される。
【００１８】
２つのサンプリング点間の距離を、サンプリング密度に基づいて決定することができる。例えば、サンプリング距離は、サンプリング密度とバウンディングボックスの対角線長さとの積として計算することができる。サンプリング密度に応じて、リンゴ、葉、およびリンゴと葉について測定される誤差は、かなり異なる。したがって、コンポーネントが異なるサンプリング密度を有する場合、誤差は比較可能でないことがあり、したがって、実際の誤差を正しく反映しないことがある。
【００１９】
【表１】
2015517154.tif 000003
【００２０】
上に論じたように、符号化器２００中では、マルチコンポーネント３Ｄモデルがコンポーネントごとに符号化される。各インスタンスコンポーネントにつき、再構築されたコンポーネントの品質が測定されて、そのコンポーネントをパターン−インスタンスモードによって表すことができるかどうかがチェックされる。異なるコンポーネントにまたがって一貫した品質を得るために、品質尺度は、個々のコンポーネント間で比較可能である必要があり、個々のコンポーネントの品質と３Ｄモデル全体との間の何らかの関連を提供する。したがって、我々は、３Ｄモデル全体についての誤差尺度が、個々のコンポーネントについての誤差の重み付き合計となるはずであるような、誤差メトリックを設計することを試みる。
【００２１】
すなわち、本原理は、２つの３Ｄモデル間の誤差を推定するためのメトリックを提供する。一実施形態では、３Ｄモデル全体またはその個々のコンポーネントについて誤差メトリックを算出するとき、統合されたサンプリングステップとセル区分化とを利用して誤差を推定することができる。したがって、３Ｄモデル全体の誤差を、その個々のコンポーネントについて算出された誤差の重み付き平均によって近似することができ、重みは、誤差の特定の定義に依存する場合がある。例えば、重みは、３Ｄコンポーネントの表面面積またはサンプリング点の数に基づくことができる。反転表面（すなわち、２つの３Ｄモデルからの対応する表面が、反対方向の法線を有する）が存在するときは、追加の誤差メトリックが法線ベクトルで定義される。
【００２２】
図５に、２つの３ＤモデルＭ1とＭ2との間の誤差メトリックを推定するための例示的な方法５００を示す。歪みは、地理的距離の平均誤差（ＭＥ）または２乗平均平方根誤差（ＲＭＳＥ）を使用して測定することができる。方法５００はステップ５１０で開始し、３Ｄモデル（Ｍ1およびＭ2）が入力される。モデルＭ1とＭ2との間の距離を算出するために、ステップ５２０でサンプリングステップ長さ（Ｓｔｅｐ＿ｌｅｎ）が計算され、ステップ５３０で、Ｍ1の表面がサンプリングされていくつかのサンプリング点が得られる。
【００２３】
ステップ５４０で、例えば計算を加速させるために、Ｍ2の空間がセルに分割される。ステップ５４０は任意選択とすることができる。ステップ５５０で、Ｍ1上の個別サンプリング点からＭ2の表面までの距離が計算される。５６０で、モデルＭ1とＭ2との間の全体的な誤差メトリックが計算される。ステップ５９９で方法５００は終了する。
【００２４】
以下に、サンプリングステップ長さを計算するステップ（５２０）、サンプリング点を決定するステップ（５３０）、セル区分化ステップ（５４０）、および点−面間誤差を計算するステップ（５５０）についてさらに詳細に述べる。
【００２５】
サンプリング
モデルＭ1の表面上でサンプリングするために、サンプリングステップ長さ（Ｓｔｅｐ＿ｌｅｎ）を、モデルＭ1の平均エッジ長さで定義することができ、これは以下のように計算することができる。
【００２６】
Ｓｔｅｐ＿ｌｅｎ＝Ａｖｅｒ＿ｅｄｇｅ＊Ｓａｍｐｌｉｎｇ＿ｆｒｅｑ  （１）
上式で、Ａｖｅｒ＿ｅｄｇｅは、モデルＭ1の平均エッジ長さであり、Ｓａｍｐｌｉｎｇ＿ｆｒｅｑは、定数、例えば一実装形態では０．０５であり、この定数を使用して、サンプリング密度を調整しサンプリング点の数を制御することができる。Ａｖｅｒ＿ｅｄｇｅはまた、他のソース、例えば入力されたメタデータから決定されてもよい。
【００２７】
上で算出されたサンプリングステップ長さを使用して、サンプリングプロセス中にサンプリング点の数を決定することができる。Ｍ1の表面上の個別ファセット（例えば三角形）について、各辺エッジ上のサンプリング点の数を以下のように計算することができる。
【００２８】
【数１】
2015517154.tif 000004
【００２９】
上式で、Ａｒｅａiは、三角形ｉの面積である。
【００３０】
図４Ａに示す３Ｄモデルを例に使用して、図６Ａ〜６Ｆにサンプリング点を示す。図６Ａ、６Ｂ、および６Ｃに、それぞれリンゴコンポーネント、マルチコンポーネント３Ｄモデル、および葉コンポーネントの３Ｄメッシュを示す。リンゴコンポーネント中の三角形６０１、および葉コンポーネント中の三角形６０２について、図６Ｄおよび６Ｅに、サンプリング点および囲んでいる三角形をより大きい縮尺で示す。三角形６０１と６０２は、異なるコンポーネントに属するが、これらはほぼ同じサンプリングステップ長さを有する。したがって、三角形６０２は三角形６０１よりも大きいので、三角形６０２ではより多くのサンプリング点がある。
【００３１】
図６Ｆに、三角形６０１のサンプリング点をさらに示す。図６Ｆに示すように、エッジを一様にサンプリングして、ｎspl個のサンプリング点（例えば、左エッジ上の点６１０、６２０、６４０、および６７０）を得ることができ、この結果、三角形中で総計ｎspl＊（ｎspl＋１）／２個のサンプリング点が得られる。一実装形態では、ｎspl＜２ならば、ｎsplは２に設定される。サンプリング点の数をファセットのサイズと関連付けることにより、サンプリング点は、２次元空間でほぼ一様に分布する。加えて、モデルＭ1中に複数のコンポーネントがあるとき、サンプリング点は、３Ｄモデル中の異なるコンポーネントにわたって一様に分布する。
【００３２】
セル区分化、および点−面間誤差計算
３ＤモデルＭ1中のサンプリング点と、別の３ＤモデルＭ2の表面と間の、点−面間誤差を計算するために、貪欲法を使用することができる。貪欲法は、１つの点と全ての面との間の誤差から最小を見つける。
【００３３】
算出を加速させるために、３ＤモデルＭ2のオブジェクト空間をいくつかのセルに分割することができる。個別セルは、１組の三角形ファセットを含む。例えば、図７Ａに示すように、モデルＭ2を、セル７１０、７２０、７３０、７４０、および他のセルに区分化することができる。図７Ｂに、セル７１０に囲まれた頂点および三角形を示す。各セル立方体の辺の長さは、以下のように平均エッジ長さ（Ａｖｅｒ＿ｌｅｎ）を使用して決定することができる。
【００３４】
Ｃ＿ｓｚ＝Ｃｅｌｌ＿Ｔｒｉ＿Ｒａｔｉｏ＊Ａｖｅｒ＿ｅｄｇｅ  （３）
上式で、Ｃｅｌｌ＿Ｔｒｉ＿Ｒａｔｉｏは、定数である。したがって、モデルＭ2に複数の３Ｄコンポーネントがあるときは、Ｍ2のバウンディングボックスによって包囲される空間が、マルチコンポーネントモデル全体とそのコンポーネントとについて同じサイズのセルに分割される。
【００３５】
Ｍ1上のサンプリング点（例えば点６０５）からＭ2の表面までの距離を素早く算出するために、まず、サンプリング点からセルの中心までの最も近い距離が算出される。最も近いセル、例えば図７Ａのセル７１０が見つかると、サンプリング点と、セル７１０内のあらゆる三角形との間の距離が計算され、最も近い距離が、Ｍ1上の点６０５から表面Ｍ2への点−面間誤差として使用される。
【００３６】
モデルＭ1上の個々のサンプリング点とモデルＭ2の表面との間の点−面間誤差を算出した後、それに従って、２つの３Ｄモデル間の平均誤差または２乗平均平方根誤差を計算することができる。例えばＭ1上のｊ番目の三角形を用いると、この三角形は各辺エッジ上にｎj個のサンプリング点を含み、この三角形の面積はＡjである。一様サンプリングの後、図６Ｆに示すように、（ｎj−１）2個の内部三角形（例えば、点｛６１０，６２０，６３０｝、｛６２０，６４０，６５０｝、｛６２０，６３０，６５０｝、｛６３０，６５０，６６０｝、｛６４０，６７０，６８０｝、｛６４０，６５０，６８０｝、｛６５０，６８０，６９０｝、｛６５０，６６０，６９０｝、および｛６６０，６９０，６９５｝によって形成される三角形が内部三角形である）が得られる。内部三角形ｉの場合、その頂点とモデルＭ2の表面との間の点−面間誤差は、それぞれ
【００３７】
【数２】
2015517154.tif 000005
【００３８】
として表される。内部三角形ｉにおいて、この場合、平均誤差を以下のように算出することができ、
【００３９】
【数３】
2015517154.tif 000006
【００４０】
平均平方根誤差を以下のように算出することができる。
【００４１】
【数４】
2015517154.tif 000007
【００４２】
その後、モデルＭ1とＭ2との間の平均誤差を以下のように算出することができ、
【００４３】
【数５】
2015517154.tif 000008
【００４４】
２乗平均平方根誤差を以下のように計算することができる。
【００４５】
【数６】
2015517154.tif 000009
【００４６】
３Ｄモデル内の個々のコンポーネントについて誤差が測定されるとき、同じ一様サンプリングが使用される。例えば、葉コンポーネントについて誤差メトリックが測定されるときは、マルチコンポーネントモデル（リンゴと葉のモデル）について誤差メトリックを測定するのに使用されるのと同じサンプリングが使用される。すなわち、葉コンポーネントについて誤差メトリックを測定するときは、三角形６０２に対して、図６Ｅに示すようなサンプリング点が再び使用される。したがって、本実施形態では、誤差を測定する際、３Ｄモデル全体とその中の個々のコンポーネントとの両方に対して、一様サンプリングが使用される。加えて、３Ｄモデル全体と個々のコンポーネントとについて誤差を測定するとき、３Ｄマルチコンポーネントモデル全体のバウンディングボックスに基づくセル区分化が使用される。したがって、区分化されたセルは、マルチコンポーネントモデルとその個々のコンポーネントとについて誤差を測定する間、一貫している。
【００４７】
有利なことに、本原理は、マルチコンポーネント３Ｄモデル中の異なる３Ｄコンポーネントにわたって一様サンプリングを使用して、異なるサンプリングステップ長さによって引き起こされる影響を回避し、したがって、より正確な品質メトリックを提供する。本原理は、マルチコンポーネントモデル全体の情報に基づいてサンプリング密度を決定する。加えて、セル区分化ステップが、マルチコンポーネントモデルのバウンディングボックスを区分化する。サンプリングステップとセル区分化ステップの両方でコンポーネント全体の情報を使用することによって、マルチコンポーネントモデルについての結果的な誤差測定値は、その個々のコンポーネントについての誤差測定値の重み付き合計である。このプロパティは、例えば図２に示すような、歪み評価のための我々の３Ｄ圧縮方法にとって非常に重要である。
【００４８】
図４Ａ、４Ｂ、および４Ｃに示す３Ｄモデルおよびコンポーネントについて、我々は、元の３Ｄモデルおよびコンポーネントと再構築された３Ｄモデルおよびコンポーネントとの間の誤差を計算する。式（１）でＳａｍｐｌｉｎｇ＿ｆｒｅｑ＝０．５に設定し、リンゴコンポーネント、葉コンポーネント、およびモデル全体についての平均誤差を表２にリストする。
【００４９】
【表２】
2015517154.tif 000010
【００５０】
リンゴコンポーネントおよび葉コンポーネントの平均誤差をそれらの面積で重み付けすると、個々のコンポーネントについての平均誤差の重み付き合計は、以下のように計算される。
【００５１】
重み付き合計＝（０．０３２１４ｅ−６＊５．９３４＋０．００１３３ｅ−６＊３．１４５）／（０．０３２１４＋０．００１３３）＝５．８２３ｅ−６
すなわち、マルチコンポーネントモデルの平均誤差は、個々のコンポーネントの平均誤差の重み付き平均と同じである。
【００５２】
誤差測定値がマルチコンポーネント３Ｄモデル中の個々のコンポーネントごとに独立して計算されるときには、すなわち、３Ｄモデル全体についてのサンプリング密度およびセル区分化はモデル全体に基づいて決定され、個々のコンポーネントについてのサンプリング密度およびセル区分化は対応する個々のモデルに基づいて独立して決定されるときには、我々は実験から、誤差測定値が前述のプロパティを有さないことを観察した。
【００５３】
反転表面が中に存在する３Ｄモデルもあるので、地理的距離を用いて２つの３Ｄモデルの表面間の差を測定するだけでは常に十分とは限らない。例えば、法線変化量は、２つの表面間の配向差を反映することができ、これは、対応するファセット間の平均法線変化量を使用して測定することができる。
【００５４】
対応するファセット対を決定するために、モデルＭ1上の三角形ファセットｆ1,iの重心から、モデルＭ2の表面までの距離が算出される。最小距離を有するＭ2上の三角形ファセットｆ2,j（例えば、２つのモデル上の最も類似するファセットである２つのファセット）が、ファセットｆ1,iの対応する三角形である。
【００５５】
図８に、法線変化量を推定するための例示的な方法８００を示す。ステップ８１０で、モデルＭ1上の個々のファセットに対して、モデルＭ2上の対応するファセットが見つけられる。ステップ８２０で、法線変化量を、ファセット対（ｆ1,i，ｆ2,j）間の法線差の平均として計算することができる。例えば、対応する三角形ファセット（ｆ1,i，ｆ2,j）間の法線変化量は、以下のように算出することができる。
【００５６】
【数７】
2015517154.tif 000011
【００５７】
上式で、
【００５８】
【数８】
2015517154.tif 000012
【００５９】
および
【００６０】
【数９】
2015517154.tif 000013
【００６１】
は、それぞれ、三角形ｆ1,iおよびｆ2,jの面法線ベクトルを表す。したがって、２つの３Ｄモデルの表面間の平均の法線変化量は、以下のように算出することができる。
【００６２】
【数１０】
2015517154.tif 000014
【００６３】
ハウスドルフ距離と同様、提案する誤差メトリックは、概して非対称である。すなわちＥｒｒ（Ｍ1，Ｍ2）≠Ｅｒｒ（Ｍ2，Ｍ1）である。対称誤差は、この２つの誤差間の最大誤差として計算することができる。
【００６４】
Ｅｒｒ＝ｍａｘ［Ｅｒｒ（Ｍ1，Ｍ2），Ｅｒｒ（Ｍ2，Ｍ1）］  （１０）
上式で、Ｅｒｒ（）は、式（６）、（７）、および（９）で定義されるＭＥ、ＲＭＳＥ、ＭＮＥとすることができる。
【００６５】
誤差メトリックを使用して、３Ｄモデル符号化器２００の反復構造検証器２６０において、例えば元のインスタンスをＭ1として使用し再構築済みインスタンスをＭ2として使用して、再構築済みインスタンスコンポーネントが品質要件を満たすかどうか検証することができる。誤差メトリックはまた、符号化器におけるレート歪み最適化に使用することもできる。本原理により定義される誤差メトリックを用いて、マルチコンポーネント３Ｄモデルに対する圧縮アルゴリズムの性能を適正に評価することができる。再構築されたモデルと元のモデルとの間の距離を算出するとき、マルチコンポーネントオブジェクト全体とその個々のコンポーネントとのいずれに対しても、サンプリング密度とオブジェクト空間の分割とが統合された。実装形態はまた、マルチコンポーネントモデル全体についての誤差がその個々のコンポーネントについての誤差の重み付き平均と等価であるという観察も証明している。
【００６６】
誤差メトリックはまた、例えば、３Ｄ形状検索において類似性を測定することや、３Ｄモデル単純化および変形においてエネルギー関数を定義することのために、他の応用例で使用することもできる。
【００６７】
図９に、例示的な品質推定器９００のブロック図を示す。装置９００の入力は、一対の３Ｄモデル、例えば、元の３Ｄモデルと再構築された３Ｄモデルとを含みうる。サンプラ９２０が、３Ｄモデルの表面上で一様サンプリングを実施することができる。任意選択のセル区分化モジュール９３０が、別の３Ｄモデルをセルに区分化することができる。一様サンプリングおよび／またはセル区分化に基づいて、誤差メトリック推定器９４０が、例えば方法５００を使用して、一対の３Ｄモデル間の誤差メトリックを推定する。他方、法線変化量推定器９１０が、例えば方法８００を使用して、一対の３Ｄモデル間の法線変化量を推定する。９４０から計算された誤差メトリック、および９１０から計算された法線変化量は、全体品質推定器９５０において全体品質尺度に統合されてもよく、またはこれらは別々に使用されてもよい。
【００６８】
本明細書に述べた実装形態は、例えば、方法もしくはプロセス、装置、ソフトウェアプログラム、データストリーム、または信号において実現することができる。論じられる特徴の実装形態は、たとえ単一の形の実装形態のコンテキストのみで論じられる（例えば方法としてのみ論じられる）としても、他の形（例えば装置またはプログラム）で実現することもできる。装置は、例えば、適切なハードウェア、ソフトウェア、およびファームウェアにおいて実現することができる。方法は、例えば、例としてプロセッサーなどの装置中で実現することができ、プロセッサーは、処理デバイス一般（例えばコンピュータ、マイクロプロセッサー、集積回路、またはプログラム可能論理デバイスを含む）を指す。プロセッサーは通信デバイスも含み、通信デバイスは、例えばコンピュータ、セルフォン、ポータブル／パーソナルディジタルアシスタント（ＰＤＡ）、および、エンドユーザ間の情報通信を容易にする他のデバイスなどである。
【００６９】
本原理の「一実施形態」または「実施形態」または「一実装形態」または「実装形態」、ならびにこれらの他の変形への言及は、実施形態との関連で記述される特定の機能、構造、特性などが、本原理の少なくとも１つの実施形態に含まれることを意味する。したがって、本明細書の全体を通して様々な場所に現れる語句「一実施形態で」または「実施形態で」または「一実装形態で」または「実装形態で」、ならびにいずれか他の変形の出現は、必ずしも全てが同じ実施形態を指しているとは限らない。
【００７０】
加えて、本出願またはその特許請求の範囲は、様々な情報を「決定する」ことに言及する場合がある。情報を決定することは、例えば、情報を推定すること、情報を計算すること、情報を予測すること、情報をメモリから取り出すことのうちの１つまたは複数を含みうる。
【００７１】
さらに、本出願またはその特許請求の範囲は、様々な情報に「アクセスする」ことに言及する場合がある。情報にアクセスすることは、例えば、情報を受け取ること、情報を（例えばメモリから）取り出すこと、情報を記憶すること、情報を処理すること、情報を伝送すること、情報を移動すること、情報をコピーすること、情報を消去すること、情報を計算すること、情報を決定すること、情報を予測すること、情報を推定することのうちの１つまたは複数を含みうる。
【００７２】
加えて、本出願またはその特許請求の範囲は、様々な情報を「受け取る」ことに言及する場合がある。受け取ることは、「アクセスする」ことと同様、広範な用語であるものとする。情報を受け取ることは、例えば、情報にアクセスすること、情報を（例えばメモリから）取り出すことのうちの一方または複数を含みうる。さらに、「受け取る」ことは通常、例えば、情報を記憶すること、情報を処理すること、情報を伝送すること、情報を移動すること、情報をコピーすること、情報を消去すること、情報を計算すること、情報を決定すること、情報を予測すること、または情報を推定することなどの操作中に、何らかの形で関係する。
【００７３】
当業者には明白であろうが、実装形態は、情報（例えば記憶または伝送されうる）を搬送するようにフォーマットされた様々な信号を生成する場合がある。情報は、例えば、方法を実施するための命令、または述べた実装形態のうちの１つによって生成されたデータを含みうる。例えば、信号は、述べた実施形態のビットストリームを搬送するようにフォーマットされてよい。このような信号は、例えば、電磁波として（例えばスペクトルの無線周波数部分を使用して）、またはベースバンド信号としてフォーマットされてよい。フォーマットすることは、例えば、データストリームを符号化して、符号化済みデータストリームで搬送波を変調することを含みうる。信号が搬送する情報は、例えば、アナログまたはディジタル情報とすることができる。信号は、知られているように、様々な異なる有線またはワイヤレスリンクを介して伝送されてよい。信号は、プロセッサー読取可能媒体に記憶されてよい。
【図１】
2015517154.tif 000015
【図２】
2015517154.tif 000016
【図３】
2015517154.tif 000017
【図４Ａ】
2015517154.tif 000018
【図４Ｂ】
2015517154.tif 000019
【図４Ｃ】
2015517154.tif 000020
【図５】
2015517154.tif 000021
【図６Ａ】
2015517154.tif 000022
【図６Ｂ】
2015517154.tif 000023
【図６Ｃ】
2015517154.tif 000024
【図６Ｄ】
2015517154.tif 000025
【図６Ｅ】
2015517154.tif 000026
【図６Ｆ】
2015517154.tif 000027
【図７Ａ】
2015517154.tif 000028
【図７Ｂ】
2015517154.tif 000029
【図８】
2015517154.tif 000030
【図９】
2015517154.tif 000031
【国際調査報告】
2015517154.tif 000032
2015517154.tif 000033