JP5456903B2 - メッシュ・モデルを符号化する方法及び装置、符号化されたメッシュ・モデル、並びに、メッシュ・モデルを復号化する方法及び装置 - Google Patents

Description

本発明は、メッシュ・モデルを符号化する方法及び装置、符号化されたメッシュ・モデル、及びメッシュ・モデルを復号化する方法及び装置に関する。

機械ＣＡＤ（コンピュータ援用設計）の設計、化学プラント、及び建築設計のような大規模３Ｄエンジニアリング・モデルの、セカンド・ライフ（商標）やグーグル・アース（商標）などの種々の仮想世界アプリケーションにおける展開はますます増えてきている。大半のエンジニアリング・モデルでは、平均で最大数百の多角形をそれぞれが有する小型乃至中型の多数の連結成分が存在している。メッシュ・モデルの部分集合は、非特許文献１に規定されているように、その中の何れかの２つの多角形間に経路が存在している場合、連結成分である。更に、このタイプのモデルは、種々の位置、尺度、及び向きで繰り返される幾何特徴をいくつか有する。

西暦１９９０年代初頭より、３Ｄメッシュを効率的に圧縮するための種々のアルゴリズムが提案されている。しかし、初期の研究は大半が、平滑な表面及び小型の三角形により、単一の連結３Ｄモデルを圧縮することに注力している。大規模３Ｄエンジニアリング・モデルなどの多重連結３Ｄモデル（複数の連結成分を含む３Ｄモデル）は別個に圧縮される。これにより、圧縮の相対的な効果が小さくなる。実際に、種々の連結成分間の冗長度をなくすことにより、圧縮性能を大きく増加させることが可能である。

大規模３Ｄエンジニアリング・モデルにおける反復幾何特徴を自動的に発見する方法は、非特許文献１において提案されている。しかし、３Ｄエンジニアリング・モデルの圧縮の効率の向上には、まだ余裕が残されている。例えば、元のモデルを回復するために必要な、反復インスタンスの変換情報を包含する圧縮ソリューションは提供されていない。３Ｄエンジニアリング・モデルが通常有している連結成分の規模が大きいことを考慮すれば、前述の種類の情報は、記憶容量を多く消費することになる。更に、成分の頂点の位置のＰＣＡ（主成分分析）が使用された場合、同じ幾何構造及び異なる連結性を有する成分は同じ平均及び同じ方向軸を有することになる。従来技術は、種々の尺度における反復パターンの検出及び／又は圧縮に適していない。尺度（すなわち、サイズ）においてのみ異なる２つの成分は、同じ等価クラスの反復した特徴として認識されていない。更に、非特許文献１に記載されたものよりも高い圧縮率を実現することが望ましい。

非特許文献２には、メッシュ・モデルの連結成分全ての平均を符号化するためのＫＤツリー・ベースの圧縮アルゴリズムが開示されている。前述のアルゴリズムは、反復毎に、セルを２つの子セルに分割し、２つの子セルの一方における頂点の数を符号化する。親セルがｐ個の頂点を含む場合、子セルのうちの１つにおける頂点の数は、算術符号化器により、ｌｏｇ_２（ｐ＋１）個のビットを使用して符号化することが可能である。この分割は、空きでないセルそれぞれが、１つの頂点のみを含めるのに十分小さい状態になるまで反復して施され、頂点の位置の十分に正確な再構成を可能にする。非特許文献２には、非均一分布の場合に最も効率が高く、正規分布が、最も悪いケースであると記載されている。

Ｄ． Ｓｈｉｋｈａｒｅ、Ｓ． Ｂｈａｋａｒ、及び Ｓ． Ｐ． Ｍｕｄｕｒ著、「Ｃｏｍｐｒｅｓｓｉｏｎ ｏｆ Ｌａｒｇｅ ３Ｄ Ｅｎｇｉｎｅｅｒｉｎｇ Ｍｏｄｅｌｓ ｕｓｉｎｇ Ａｕｔｏｍａｔｉｃ Ｄｉｓｃｏｖｅｒｙ ｏｆ Ｒｅｐｅａｔｉｎｇ Ｇｅｏｍｅｔｒｉｃ Ｆｅａｔｕｒｅｓ」、 西暦２００１年１１月２１乃至２３日発行（Ｓｔｕｔｔｇａｒｔ、Ｇｅｒｍａｎｙ） Ｄｅｖｉｌｌｅｒｓ， Ｐ． Ｇａｎｄｏｉｎ著、「Ｇｅｏｍｅｔｒｉｃ ｃｏｍｐｒｅｓｓｉｏｎ ｆｏｒ ｉｎｔｅｒａｃｔｉｖｅ ｔｒａｎｓｍｉｓｓｉｏｎ（ＩＥＥＥ Ｖｉｓｕａｌｉｚａｔｉｏｎ）」、２０００年発行， ｐｐ． ３１９−３２６

本発明は、大半の大規模３Ｄエンジニアリング・モデルの場合、連結成分の反復インスタンスのインスタンス位置は複数のかなりの空間集約を示し、この場合、非特許文献２に表されたアルゴリズムの効率を向上させることが可能であるということの認識に基づく。すなわち、大規模３Ｄメッシュ・モデル内の反復インスタンスは多くの場合、いくつかのインスタンスが１つ又は少数の小領域内にある一方で他の比較的大きな領域ではインスタンスが存在しないというように分布している。非特許文献２に提案されているように、前述のタイプの点データ・セットを編成し、圧縮するために単一のＫＤツリーが使用された場合、ＬＤツリーの深度は不合理にも高くなり、これにより、出力データ・ストリームが、必要な長さよりも長くなる。

本発明は、この場合に対する改良をもたらす。本発明によれば、空間集約された一点クラスタ毎にいくつかのＫＤツリーが使用される。前述のＫＤツリーは、比較的短いデータ・ストリームを生成し、よって、全体圧縮率を向上させることになる。

一局面では、本発明はメッシュ・モデルの点を符号化する方法を提供する。方法は、メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定するステップと、少なくとも１つの参照点を反復インスタンス毎に判定するステップと、反復インスタンスの参照点を１つ又は複数のクラスタにクラスタ化するステップと、ＫＤツリー符号化を使用して、クラスタ化された参照点を符号化するステップとを含み、クラスタ毎に、別個のＫＤツリーが生成される。

本発明の別の局面によれば、メッシュ・モデルの点を符号化する装置は、メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定する解析手段と、少なくとも１つの参照点を反復インスタンス毎に判定する判定手段と、１つ又は複数のクラスタに反復インスタンスの参照点をクラスタ化するクラスタ化手段と、ＫＤツリー符号化を使用して、クラスタ化された参照点を符号化する符号化手段とを備え、クラスタ毎に、別個のＫＤツリーが生成される。

本発明の更なる局面によれば、符号化されたメッシュ・モデルの点を復号化する方法は、反復連結成分のインスタンスのデータを抽出するステップと、抽出されたデータを使用して、連結成分のインスタンスを復号化するステップと、クラスタの数」を規定する第１のデータを抽出するステップであって、第２のデータは空間分解能を規定し、第３のデータは、反復連結成分の複数の反復の位置であり、第３のデータは、ＫＤツリーとして符号化されるステップと、メッシュ・モデル内の一部分を規定する第４のデータを抽出するステップと、第３のデータ及び第４のデータから反復連結成分の複数の反復の位置を判定するステップとを含み、第３のデータが、第４のデータによって規定されるメッシュ・モデルの一部分に施される。

本発明の更に別の局面によれば、符号化されたメッシュ・モデルの点を復号化する装置は、符号化されたメッシュ・モデルから反復連結成分のインスタンスのデータを抽出する第１の抽出手段と、抽出されたデータを使用して連結成分のインスタンスを復号化する復号化手段と、クラスタの数を規定する第１のデータを抽出する第２の抽出手段であって、第２のデータが空間分解能を規定し、第３のデータが反復連結成分の複数の反復の位置であり、第３のデータはKDツリーとして符号化される第２の抽出手段とを備え、更に、メッシュ・モデル内の一部分を規定する第４のデータを抽出する第３の抽出手段と、第３のデータ及び第４のデータから、反復する接続された構成部分の複数の反復の位置を判定する判定手段とを備え、第３のデータは、第４のデータによって規定されたメッシュ・モデルの一部分に施される。

本発明の一局面によれば、符号化されたメッシュ・モデルは、複数の反復連結成分を備え、前記符号化されたメッシュ・モデルは、反復連結成分それぞれの少なくとも１つのインスタンスの符号化データ、反復連結成分の複数の反復の位置であって、ＫＤツリーとして符号化される位置、及びメッシュ・モデル内の境界領域を含み、ＫＤツリーは領域を表す。

２Ｄの例におけるＫＤツリー符号化の原理を示す図である。 反復連結成分の複数のインスタンスの位置、及び反復連結成分の複数のインスタンスの位置の従来のＫＤツリー符号化の結果を示す図である。 クラスタ化後のクラスタ位置を示す図である。 クラスタに基づいた符号化メッシュ・モデルのデータ構造を示す図である。 ５５７４個の連結成分を含む、会議室の例示的な３Ｄメッシュ・モデルの２Ｄ表現を示す図である。 符号化方法及び復号化方法を示す例示的なフローチャートである。 クラスタ化方法を示す例示的なフローチャートである。

本発明の効果的な実施例は、従属請求項、明細書の以下の説明、及び図に記載している。

本発明の例示的な実施例は、添付図面を参照して説明する。

図１は、２Ｄケースにおける従来のＫＤツリー符号化の原理を例示的に示す。２Ｄモデルは、親セルと呼ばれるバウンディング・ボックス１０によって囲まれる。７個の頂点が親セル内に配置される。ＫＤツリー符号化アルゴリズムは、所定数のビットを用いた、頂点の合計数の符号化に始まり、次いで、セルを反復して分割する。親セルを２つの子セルに分割する都度、２つの子セルの一方における頂点の数を符号化する。約束ごととして、これは、（垂直方向の分割後の）左子セル又は（水平方向の分割後の）上位セルであり得る。
親セルがｐ個の頂点を含む場合、子セルのうちの１つにおける頂点の数は、算術符号化器により、ｌｏｇ_２（ｐ＋１）ビットを使用して符号化することが可能である。空きでないセルそれぞれが、１つの頂点のみを含み、頂点の位置の十分に正確な再構成を可能にするのに十分小さい状態になるまで、この分割が反復的に施される。反復インスタンス全ての位置を圧縮するために、位置全てのバウンディング・ボックス１０全体は最初は親セルとみなされる。図１の例では、頂点の合計数（７）は３２ビットを使用して符号化される。次いで、垂直方向の分割が施され、よって、左子セルＶ１及び右子セルＶ２が得られる。次の符号化ステップでは、左子セルＶ１内の頂点数（すなわち、４）が符号化される。符号化に使用されるビットの数は、親セル内の頂点数によって求められる。これは、ｌｏｇ_２（７＋ｌ）＝３ビットである。親セル内の頂点数、及び左子セルＶ１内の頂点数から、右子セルＶ２内の頂点数を推論することが可能であり、したがって、符号化する必要はない。

次のステップでは、水平方向の分割が施される。親セルＶ１である左子セルＶ１は、上位子セルＶ１Ｈ１及び下位子セルＶ１Ｈ２に分割される。親セルＶ２である右子セルＶ２は、上位子セルＶ２Ｈ１及び下位子セルＶ２Ｈ２に分割される。符号化は、２つの頂点を有する上位左子セルＶ１Ｈ１に続く。よって、２という数が次に符号化され、ｌｏｇ_２（４＋１）＝２．３ビットが、算術符号化器において使用される。上述の通り、低位左子セルＶ１Ｈ２内の頂点の数は、左セルＶ１内、及び上位左子セルＶ１Ｈ１内の頂点の数から推論することが可能であるため、符号化しなくてよい。次いで、同じ手順が右セルＶ２に施され、それにより、２つのビットを使用してゼロが符号化される。図１に示すように、各頂点が別個のセルに収まる状態になるまで、分離ステップが更に２つ必要であり、各頂点がそのセル内で十分に局所化された状態になるまで、更に多くのステップが必要である。各ステップは、１又はゼロの増加する数を符号化することを必要とする。要求された精度に応じて、更なるステップの数は高いことがあり得る。

非特許文献２は、単一のＫＤツリーが、最適な圧縮をもたらすということを示唆している。しかし、空間的に集約された点の場合、更なる冗長度が存在しており、これを本発明によって削減することができるということが明らかになっている。点の空間的な集約は、後続する複数の分割動作の場合、子セルのうちの１つが常に空きであるということを意味している。したがって、点が空間的に集約されている場合、何れのレベル（ｋ＋１）も、その親レベルｋと同じビット数を消費する。基本的には、ＫＤツリーの従来の使用では、ＫＤツリーの各レベルを狭くすることにより、圧縮率を向上させる。本発明は、複数のＫＤツリーを使用し、各ＫＤツリーに持たせるレベルをより少なくすることにより、圧縮率を向上させる。

本発明は、頂点の位置の符号化にのみならず、反復連結成分の位置の符号化にもＫＤツリー符号化アルゴリズムを施す。図２のａ）は、複数の反復連結成分２１乃至２４が３Ｄメッシュ・モデルのバウンディング・ボックス２０内に配置される例を示す。多くの大きな３Ｄメッシュ・モデルの場合と同様に、位置はバウンディング・ボックス内で非常に不規則に配置される。ＫＤツリー符号化アルゴリズムが、位置を符号化するために施された場合、例示的な結果を図２のｂ）に示す。クラスタが局所化された状態になる前に５つの初期分割ステップが必要であるということが分かる。すなわち、図２の例では、符号は以下の通りになる。
１２（合計数）−６（左子セル、１代目）−６−３（上位子セル、２代目）−２−３−０（Ｌ，３代目）−２−０−０−０（上位、４代目）−２−４−０−３（Ｌ、５代目）−２−０−３−０（上位、６代目）であり、それにより、１２−６−６−３−２−３−０−２−０−０−０−２−４−０−３−２−０−３−０がもたらされる。ビットの数の割り当ては上記の通りである。より正確な位置については、更なるデータが必要であり得る。よって、符号は、ゼロ、又は先行値の数多くの反復を含む。

本発明では、手順も、結果として生じる符号もかなり短い。本発明の一局面によれば、点はクラスタ化される、すなわち、クラスタが作成され、場合によっては、点がクラスタに割り当てられる。図２に示す点は、図３に示すようなやり方で効果的にクラスタ化することが可能である。この例では、４つのクラスタ３１乃至３４が、バウンディング・ボックス３０内に存在している。一般に、クラスタ化は、まだクラスタ化されておらず、１つ又は複数の点を含む第１のセルを選択するステップと、第１のセル内の１つ又は複数の点、若しくは第１のセルを含むクラスタを規定するステップとを含む。

一実施例では、図６のａ）に示すように、メッシュ・モデルの点を符号化する方法は、メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定するステップ（Ｅ１）と、少なくとも１つの参照点を反復インスタンス毎に判定するステップ（Ｅ２）と、反復インスタンスの参照点を１つ又は複数のクラスタにクラスタ化するステップ（Ｅ３）と、ＫＤツリー符号化を使用して、クラスタ化された参照点を符号化するステップ（Ｅ４）とを含み、クラスタ毎に、別個のＫＤツリーが生成される。

一実施例では、クラスタ化するステップは、メッシュ・モデルの周りのバウンディング・ボックスを画定するステップと、バウンディング・ボックスをセルに分割するステップであって、セルが最小空間分解能単位であるステップと、まだクラスタ化されておらず、反復インスタンスの１つ又は複数の参照点を含む第１のセルを選択するステップと、第１のセル内の１つ又は複数の参照点、若しくは第１のセルを含むクラスタを画定するステップとを含む。一般に、第１のセルは、新たなクラスタを作成するための候補である。一実施例では、一セルは、クラスタの作成に十分である。別の実施例では、それぞれが１つ又は複数の点を含む少なくとも２つの隣接セルが、クラスタを作成するために必要である。更に別の実施例では、何れかの数の隣接セル内の所定の最小数の点が、クラスタを作成するために必要である。

一実施例では、第１のセルは、まだクラスタ化されておらず、かつ、少なくともＭ個の点（例えば、Ｍ個の反復インスタンスの参照点）を含む場合にのみ選択される。一実施例では、Ｍはユーザ定義可能なパラメータである。対応する符号化方法はパラメータＭを規定するステップであり、Ｍは、新たなクラスタを作成するためのソースとしてセルを選択するための、セル内の点の最小数である。

一実施例では、クラスタ化は更に、１つ又は複数の更なるセルを判定するステップであって、更なるセルが、選択された第１のセルの近傍セル、又は反復的に近傍（すなわち、近傍の近傍等）のセルであり、判定された更なるセルそれぞれが、反復インスタンスの少なくとも１つの参照点を含むステップと、判定された１つ又は複数の近傍セルをクラスタに加えるステップとを更に含み得る。

一実施例では、クラスタ化は更に、各セルにおける参照点の数の昇順又は降順でセル全てをソートするステップを含み、第１のセル（新たなクラスタを作成するための候補）は、上述の順に応じて選択される。

図５に示す例示的な会議室などの多くの大規模３Ｄエンジニアリング・モデルの場合、インスタンス位置は、複数のかなりの空間集約を示す。１つの単一のＫＤツリーが、前述のタイプの点データ・セットを編成し、圧縮するために使用された場合、ＫＤツリーの深度は不合理に高くなる。他方で、空間的に集約された一点クラスタ毎にいくつかのＫＤツリーが使用された場合、ＫＤツリーは相対的に短いデータ・ストリームを生成し、よって、合計圧縮率を向上させる。例えば、図５に示すように、５５７４個の連結成分を含む会議室の３Ｄモデルでは、複数の反復連結成分は椅子ＲＣＣ１、カーペットの反復テクスチャ要素ＲＣＣ２、又は枝付き燭台の反復構造要素ＲＣＣ３である。大規模３Ｄエンジニアリング・モデルのコンパクトな格納及び高速伝送を可能にするために、本発明は、反復インスタンス全ての位置を符号化するために特に効果的な効率的な圧縮ストラテジを提供する。一局面では、本発明は、離散的な点に対する、特に、複数のかなりの空間集約を示す点に対する効率的な圧縮手法を提供する。大規模３Ｄエンジニアリング・モデルにおける反復インスタンスの位置は多くの場合、前述の種類の特性を有する。

本発明は、複数のかなりの空間集約を備えた離散的な点のデータ・セットを効率的に圧縮するためのクラスタ化されたＫＤツリー・ベースの圧縮アルゴリズムを提供する。入力点は、まず、その空間位置に応じてクラスタ化される。各クラスタは、空間集約された点の組を含む。次いで、各クラスタは、１つのＫＤツリーにより、それに属する点全てを編成することによって圧縮される。

以下に、符号化するための例示的なクラスタ化方法を説明する。Ｃ＿Ｐｏｉｎｔが点クラスタ全てを表すものとする。最初に、Ｃ＿Ｐｏｉｎｔは空きである。

ステップ１： Ｎ^＊Ｎ^＊Ｎ個のセルに圧縮される対象の点全てのバウンディング・ボックス全体を分割する。

ステップ２： 各セルに収まる点の数の昇順に応じてキューＱ＿Ｃｅｌｌにセル全てをソートする。

ステップ３: Ｑ＿Ｃｅｌｌが空でない場合、
Ｑ＿ＣｅｌｌからセルＰをポップする。空のセルを飛ばす。ステップ４に進む。

さもなければ、ステップ６に進む。

ステップ４： ＰがＣ＿Ｐｏｉｎｔにおける何れのクラスタにも属しない場合、
Ｐのみを含む新たなクラスタＣを生成し、
ＣをＣ＿Ｐｏｉｎｔに加える
ステップ５に進む
さもなければ、ステップ３に進む。

ステップ５： Ｃにおけるセル全ての近傍セル全てを検査する。

Ｐ１は、Ｃにおける何れかのセルの何れかの近傍セルを表す。

Ｐ１に収まる点の数＞Ｂであり、かつ、Ｐ１がＣ＿Ｐｏｉｎｔにおける何れのクラスタにも属さない場合、Ｐ１をＣに加える。（Ｂはユーザ定義された閾値である。）
近傍セル全てについて検査を終了した後、ステップ３に進む。

ステップ６： Ｃ＿Ｐｏｉｎｔにおける同じクラスタに属するセルに収まる点を独立的に圧縮する。各クラスタは、別個のＫＤツリーを使用して、対応する点を編成し、例えば、非特許文献２に基づいて圧縮することにより、圧縮される。

ユーザ定義されたパラメータＢは、クラスタの近傍としてセルが加えられるためにセル内に存在していければならない点の数を規定する。一実施例ではＢ＝１である一方、他の実施例では、Ｂのより高い値を必要とし得る。クラスタ化方法のフローチャートを図７に示す。

結果として生じるビットストリームの構文は表１に示すようなものであり得る。ａｅ（ｖ）は、Ｈ．２６４／ＡＶＣにおける算術符号化と同様な算術符号化を意味する。

例示的なビットストリームの意味論は以下の通りである：
ＢｏｕｎｄａｒｙＢｏｘ＿Ｏｆ＿Ａｌｌ＿Ｉｎｓｔａｎｃｅ＿Ｐｏｓｉｔｉｏｎｓは、インスタンス位置全てのバウンディング・ボックスを示す。

Ｎｕｍ＿Ｏｆ＿Ｃｌｕｓｔｅｒｓは、クラスタの数を示す。

Ｎ（すなわち、上記符号化手順のステップ１におけるＮ）は、セルの分解能を示す。

Ｉｎｄｉｃｅｓ＿ｏｆ＿Ｔｗｏ＿Ｂｏｕｎｄａｒｙ＿Ｃｅｌｌｓ＿ｏｆ＿ｃｌｕｓｔｅｒ［ｉ］は、ｃｌｕｓｔｅｒ［ｉ］のバウンディング・ボックスを規定する２つのセルのインデクスを示し、２^＊Ｌｏｇ_２（ｎ^＊ｎ^＊ｎ）個のビットを有する。

ＫＤ−ｔｒｅｅ＿ｏｆ＿ｃｕｒｒｅｎｔ＿ｃｌｕｓｔｅｒは、現在のクラスタのＫＤツリーを記録するためのビットを表す。

一実施例では、符号化中、各クラスタの境界、及び対応する２つの境界セルを判定するステップが、実際のクラスタ化後に存在している。境界は、２つの境界セルのインデクスによって表すことが可能である。現在のクラスタの境界セルは、各寸法の最小インデクス及び最大インデクスを備えたセルである。例えば、２Ｄのケースにおいて、クラスタに属する点が｛ｘ_ｍｉｎ，ｘ_ｍａｘ｝及び｛ｙ_ｍｉｎ，ｙ_ｍａｘ｝の範囲内にある場合、境界セルは、実際にクラスタ内になくても、ｘ_ｍｉｎ，ｘ_ｍａｘ、及びｙ_ｍｉｎ，ｙ_ｍａｘにある。しかし、前述のインデクスは、現在のクラスタの局所のバウンディング・ボックスを定義するために使用される。局所バウンディング・ボックス内では、局所座標を使用し、これにより、ビット数が削減され得る。

一実施例では、現在のクラスタのＫＤツリーを算出するステップは、現在のクラスタ［ｉ］に収まるインスタンスの相対位置を算出するステップと、バウンディング・ボックスの世界座標系における対応するインスタンス位置を算出するステップとを含む。
一実施例では、符号化方法は更に、メッシュ・モデルの空間分解能（例えば、表１中のＮ）を規定するステップを更に含む。この場合、セルは、規定された空間分解能に応じた最小空間分解能単位である。符号化中の特定のセル内のどこかである位置は、復号化後、セル内の所定の位置においてのみ、例えば、セルの中心においてのみ、再生することが可能である。位置がより正確であるためには、より高い空間分解能が必要である。一実施例では、Ｎは予め規定されている。別の実施例では、Ｎは品質要件に応じて選択することが可能である（例えば、低分解能ディスプレイ上での再生のために縮小することが可能である）。

上述のように、従来技術の方法は、点が非常に不均一に分布している場合、効果がない。一実施例では、符号化方法は更に、点の空間的均一性の尺度を判定するステップ（空間的均一性の尺度は、点が均一に分布している場合に高く、分布がより不規則な場合に低い）と、空間的均一性を閾値と比較するステップと、空間的均一性が閾値未満である場合にのみ、クラスタ化を行うステップとを含む。例えば、符号化方法は、反復インスタンスの参照点の空間的均一性の尺度を判定するステップと、空間的均一性を閾値と比較するステップと、空間的均一性が閾値未満である場合（すなわち、点の分布が非常に不均一である場合）にのみクラスタ化を行うステップとを含む。

一実施例では、符号化方法は、空間的均一性が閾値未満である場合、空間分解能を修正するステップと、空間的均一性を測定するステップと、空間的均一性が閾値未満でない状態になるまで前述のステップを反復するステップとを更に含む。

図４は、クラスタに基づいた符号化メッシュ・モデルのデータ構造を示す。完全な３Ｄメッシュ・モデル及び連結成分の特定のタイプを表すルートは、反復連結成分を表し、ＫＤツリー ＫＤ−Ｔ１、_…、ＫＤ−Ｔ３として表される少なくとも１つのクラスタを備える。

図４の例では、連結成分ルートＣＣｒは、特定の連結成分の略である。例えば、連結成分は、３Ｄエンジニアリング・モデルにおける特定のタイプのねじであり得る。上記例では、このタイプのねじが非常に多く使用される、３Ｄモデル内の領域は３つ存在している。領域それぞれは、別個のＫＤツリー ＫＤ−Ｔ１、_…、ＫＤ−Ｔ３によって表されるクラスタとして表す。連結成分の少数のインスタンス又は単一のインスタンスは、他の領域にも現れ得る。一実施例では、前述のインスタンスはクラスタ化されていない一方、その位置は、別個の構造Ｔ４（例えば、特別なＫＤツリー、又は座標のリストのみ）において表される。３つのクラスタＫＤツリー ＫＤ−Ｔ１、_…、ＫＤ−Ｔ３はそれぞれ、連結成分の複数のインスタンスの一クラスタを表し、位置情報、例えば、クラスタの境界セルのインデクスを含む。

以下では、本発明の更なる実施例を説明する。

一実施例では、メッシュ・モデルの点を符号化する装置は、メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定する判定手段と、少なくとも１つの参照点を反復インスタンス毎に判定する判定手段と、反復インスタンスの参照点を１つ又は複数のクラスタにクラスタ化するクラスタ化手段と、ＫＤツリー符号化を使用して、クラスタ化された参照点を符号化する符号化手段とを備え、クラスタ毎に、別個のＫＤツリーが生成される。

一実施例では、クラスタ化手段は、メッシュ・モデル周りのバウンディング・ボックスを画定する画定手段と、バウンディング・ボックスをセルに分割する分割手段であって、セルが最小空間分解能単位である分割手段と、まだクラスタ化されておらず、反復インスタンスの１つ又は複数の参照点を含む第１のセルを選択する選択手段と、第１のセル内の１つ又は複数の参照点、若しくは第１のセルを含むクラスタを画定する画定手段とを備える。

一実施例では、装置は、１つ又は複数の更なるセルを判定する判定手段であって、更なるセルは、選択された第１のセルの近傍セル、又は反復的な近傍のセルであり、判定された更なるセルはそれぞれ、反復インスタンスの少なくとも１つの参照点を備える判定手段と、判定された１つ又は複数の近傍セルをクラスタに付加する付加手段とを更に備える。
一実施例では、クラスタ化手段は更に、各セルにおける参照点の数の昇順又は降順にセル全てをソートする編成手段を更に備え、第１のセル（すなわち、クラスタの初期セル）は、上述の順序に応じて選択される。

一実施例では、クラスタ化手段は、現在のクラスタの境界セル（各寸法の最小インデクス及び最大インデクスを備えたセルである）を判定する手段を備える。

一実施例では、符号化装置は、空間分解能を規定する手段を更に備え、セルは、規定された空間分解能に応じた、最小の空間分解能単位である。

一実施例では、符号化装置は、反復インスタンスの参照点の空間的均一性の尺度を判定する解析手段であって、空間的均一性の尺度は参照点が均一に分布している場合に高く、分布がより不規則である場合に低い解析手段と、空間的均一性を閾値と比較する比較器手段と、空間的均一性が閾値を下回る場合にのみ、クラスタ化が行われるよう制御する制御手段とを備える。

一実施例では、符号化されたメッシュ・モデルは複数の反復連結成分を備え、符号化されたメッシュ・モデルは、反復連結成分それぞれの少なくとも１つのインスタンスの符号化データ、反復連結成分の複数の反復の位置であって、ＫＤツリーとして符号化された位置、及び、メッシュ・モデル内の境界領域を含み、ＫＤツリーは領域を表す。

一実施例では、符号化されたメッシュ・モデルの境界領域のデータは、境界セルのインデクスを備える。

図６のｂ）に示す一実施例では、符号化されたメッシュ・モデルの点を復号化する方法は、反復連結成分のインスタンスのデータを抽出するステップ（Ｄ１）と、抽出されたデータを使用して連結成分のインスタンスを復号化するステップ（Ｄ２）と、クラスタ数を規定する第１のデータ（Ｎｕｍ＿Ｏｆ＿Ｃｌｕｓｔｅｒｓ）を抽出するステップ（Ｄ３）であって、第２のデータ（Ｎ）が空間分解能を規定し、第３のデータ（ＫＤ−Ｔ１、_…、ＫＤ−Ｔ３）が反復連結成分の複数の反復の位置であり、第３のデータがＫＤツリーとして符号化されるステップと、第４のデータ（Ｉｎｄｅｘ＿Ｂｏｕｎｄａｒｙ＿Ｃｌｕｓｔｅｒ）を抽出するステップ（Ｄ４）と、第３のデータ及び第４のデータから反復連結成分の複数の反復の位置を判定するステップ（Ｄ５）とを含み、第３のデータは、第４のデータによって規定されるメッシュ・モデルの部分に施される。

復号化のための方法の一実施例では、第４のデータ（Ｉｎｄｅｘ＿Ｂｏｕｎｄａｒｙ＿Ｃｌｕｓｔｅｒ）はメッシュ・モデル内の２つのセルのインデクスを備え、セルは、第２のデータによって規定される空間分解能に応じた最小空間分解能単位である。

パターン位置データの場合、本発明によるクラスタ・ベースのＫＤツリー圧縮は、従来のＫＤツリー・ベースの圧縮と比較して、約５０％の記憶空間（Ｃｌｕｓ＿Ｃｏｍｐ／Ｃｏｏｒ＿Ｃｏｍｐ）を節減することが可能である。

表２では、＃Ｃは連結成分の数であり、＃Ｐは反復成分の数であり、Ｃｏｏｒ．（Ｋ）は、未処理インスタンス位置のサイズ（単位：Ｋバイト）であり、Ｃｏｏｒ＿Ｃｏｍｐ（Ｋ）は１つのＫＤツリーを使用した圧縮インスタンス位置のサイズであり、＃Ｃｌｕはクラスタの数であり、Ｃｌｕ＿Ｃｏｏｒ＿Ｃｏｍｐ（Ｋ）は、クラスタ化されたＫＤツリー・ベースの圧縮方法による圧縮インスタンス位置のサイズである。

好ましい実施例に施された、本発明の新しい基本構成を示し、説明し、指摘してきたが、開示された装置の形式及び詳細、並びに、その動作において、上述の装置及び方法における種々の割愛、置換、及び変更を、本発明の趣旨から逸脱しない限り、当業者によって行い得る。本発明は反復連結成分のインスタンス位置に関して開示してきたが、本明細書及び特許請求の範囲記載の方法及び装置は基本的には、離散点の群の圧縮に関する何れかのシナリオに施し得るということを当業者は認識するであろう。同じ結果を達成するために実質的に同じやり方で実質的に同じ機能を行う構成要素の組合せは全て、本発明の範囲内にあることを明示的に意図している。上述の一実施例から別の実施例に要素を置き換えることも、完全に意図され、想定されている。

本発明は例として表しているに過ぎず、本発明の範囲から逸脱しない限り、詳細の修正を行うことが可能である。明細書に記載された特徴それぞれ、及び（請求項及び図面に記載されている場合には）請求項及び図面に記載された特徴それぞれは、独立して、又は何れかの適切な組み合わせで提供し得る。特徴は、適宜、ハードウェア、ソフトウェア、又はそれらの２つの組合せで実現し得る。請求項記載の参照符号は、例証のみの目的に過ぎず、請求項の範囲を限定する制限的な効果を有しない。

Claims (15)

1. メッシュ・モデルの点を符号化する方法であって、
   判定手段が、前記メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定し、少なくとも１つの参照点を反復インスタンス毎に判定するステップと、
   クラスタ化手段が、前記反復インスタンスの前記参照点を１つ又は複数のクラスタにクラスタ化するステップと、
   符号化手段が、ＫＤツリー符号化を使用して、前記クラスタ化された参照点を符号化するステップと
   を含み、クラスタ毎に別個のＫＤツリーが生成され、前記クラスタ化手段が前記クラスタ化するステップは、
   前記メッシュ・モデル周りにバウンディング・ボックスを画定するステップと、
   
   前記バンディング・ボックスを複数のセルに分割するステップであって、セルが最小空間分解能単位であるステップと、
   まだクラスタ化されておらず、反復インスタンスの１つ又は複数の参照点を含む第１のセルを選択するステップと、
   前記第１のセルを含み、又は、前記第１のセル内の前記１つ又は複数の参照点を含むクラスタを画定するステップと
   を含む、前記方法。
2. 請求項１記載の方法であって、まだクラスタ化されておらず、Ｍ個の反復インスタンスの少なくともＭ個の参照点を含んでいる場合にのみ、前記第１のセルが選択されるに過ぎず、Ｍはユ―ザ定義可能なパラメータである、前記方法。
3. 請求項１又は２に記載の方法であって、
   １つ又は複数の更なるセルを判定するステップであって、前記更なるセルは、前記選択された第１のセルの近傍セル、又は反復的に近傍のセルであり、前記判定された更なるセルそれぞれは反復インスタンスの少なくとも１つの参照点を含むステップと、
   前記判定された１つ又は複数の近傍セルを前記クラスタに付加するステップと
   を更に含む、前記方法。
4. 請求項１乃至３の何れか一項に記載の方法であって、
   各セルにおける参照点の数の昇順又は降順でセル全てをソートするステップを更に含み、前記第１のセルは当該順に応じて選択される、前記方法。
5. 請求項１乃至４の何れか一項に記載の方法であって、前記クラスタ化するステップは、現在のクラスタの境界セルを判定するステップを含み、前記境界セルは、各寸法の最小インデクス及び最大インデクスを備えたセルである、前記方法。
6. 請求項１乃至５の何れか一項に記載の方法であって、
   空間分解能を規定するステップを更に含み、セルは、規定された空間分解能に応じた最小空間分解能単位である、前記方法。
7. 請求項１乃至６の何れか一項に記載の方法であって、
   前記反復インスタンスの参照点の空間的均一性の尺度を判定するステップであって、前記空間的均一性の尺度は、前記参照点が均一に分布している場合に高く、前記分布がより不規則である場合に低いステップと、
   前記空間的均一性を閾値と比較するステップと、
   前記空間的均一性が閾値未満である場合にのみ、前記クラスタ化を行うステップと
   を更に含む、前記方法。
8. 請求項７記載の方法であって、前記空間的均一性が前記閾値未満である場合に、前記空間分解能を修正するステップと、
   空間的均一性の尺度を判定するステップを反復するステップとを更に含む、前記方法。
9. メッシュ・モデルの点を符号化する装置であって、
   前記メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定し、少なくとも１つの参照点を反復インスタンス毎に判定する判定手段と、
   前記反復インスタンスの前記参照点を１つ又は複数のクラスタにクラスタ化するクラスタ化手段と、
   ＫＤツリー符号化を使用して前記クラスタ化された参照点を符号化する符号化手段とを備え、
   クラスタ毎に別個のＫＤツリーが生成され、前記クラスタ化手段は、
   前記メッシュ・モデル周りのバウンディング・ボックスを画定するバウンディング・ボックス画定手段と、
   前記バウンディング・ボックスを複数のセルに分割するバウンディング・ボックス分割手段と、
   まだクラスタ化されておらず、反復インスタンスの１つ又は複数の参照点を含む第１のセルを選択する選択手段と、
   前記第１のセルを含み、又は、前記第１のセル内の前記１つ又は複数の参照点を含むクラスタを画定するクラスタ画定手段と
   を含む、前記装置。
10. 請求項９記載の装置であって、
    更なる１つ又は複数のセルを判定するセル判定手段であって、
    前記更なるセルは前記選択された第１のセルの近傍セル又は反復的に近傍のセルであり、前記判定された更なるセルそれぞれは反復インスタンスの少なくとも１つの参照点を含むセル判定手段と、
    前記判定された近傍セルを前記クラスタに付加する手段とを備える、前記装置。
    
11. 請求項９又は１０に記載の装置であって、前記クラスタ化手段は、各セルにおける参照点の番号の昇順又は降順にセル全てをソートするソート手段を更に備え、前記第１のセルは当該順に応じて選択される、前記装置。
12. 請求項９乃至１１の何れか一項に記載の装置であって、
    前記クラスタ化手段は、現在のクラスタの境界セルを判定する境界セル判定手段を備え、前記境界セルは、各寸法の最小インデクス及び最大インデクスを備えたセルである、前記装置。
13. 請求項９乃至１２の何れか一項に記載の装置であって、空間分解能を規定する空間分解能規定手段を更に備え、セルは、前記規定された空間分解能に応じた、最小の空間分解能単位である、前記装置。
14. 請求項９乃至１３の何れか一項に記載の装置であって、
    前記反復インスタンスの参照点の空間的均一性の尺度を判定する空間的均一性判定手段であって、前記空間的均一性の尺度は、前記参照点が均一に分布している場合、高く、当該分布がより不規則な場合、より低い空間的均一性判定手段と、
    前記空間的均一性を閾値と比較する比較手段と、
    前記空間的均一性が前記閾値未満である場合にのみ、前記クラスタ化を行う条件付きクラスタ化手段と
    を備える、前記装置。
15. 符号化メッシュ・モデルの点を復号化する方法であって、
    第１データ抽出手段が反復連結成分のインスタンスのデータを抽出するステップと、
    復号化手段が、前記抽出されたデータを使用して前記連結成分の前記インスタンスを復号化するステップと、
    第２データ抽出手段が、クラスタの数を規定する第１のデータを抽出するステップであって、第２のデータは空間分解能を規定し、第３のデータは前記反復連結成分の複数の反復の位置であり、前記第３のデータはＫＤツリーとして符号化されるステップと、
    前記第２データ抽出手段が、前記メッシュ・モデル内の部分を規定する第４のデータを抽出するステップと、
    位置判定手段が、前記第３のデータ及び前記第４のデータから前記反復連結成分の前記複数の反復の前記位置を判定するステップと
    を含み、前記第３のデータが前記第４のデータによって規定される前記メッシュ・モデルの前記部分に施され、前記第４のデータは、前記メッシュ・モデル内の２つのセルのインデクスを備え、セルは、前記第２のデータによって規定される前記空間分解能に応じた最小空間分解能である、前記方法。

Images