メッシュ・モデルを符号化する方法及び装置、符号化されたメッシュ・モデル、並びに、メッシュ・モデルを復号化する方法及び装置
大半の大規模３Ｄエンジニアリング・モデルの場合、連結成分の反復インスタンスのインスタンス位置は、複数のかなりの空間集約を示す。本発明は、空間集約された一点クラスタ毎にいくつかのＫＤツリーを使用する。複数のＫＤツリーは、比較的短いデータ・ストリームを生成し、よって、全体圧縮率を向上させる。３Ｄメッシュ・モデルの点を符号化する方法は、メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定するステップと、少なくとも１つの参照点を反復インスタンス毎に判定するステップと、反復インスタンスの参照点を１つ又は複数のクラスタにクラスタ化するステップと、ＫＤツリー符号化を使用して、クラスタ化された参照点を符号化するステップとを含み、クラスタ毎に、別個のＫＤツリーが生成される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッシュ・モデルを符号化する方法及び装置、符号化されたメッシュ・モデル、及びメッシュ・モデルを復号化する方法及び装置に関する。
【背景技術】
【０００２】
機械ＣＡＤ（コンピュータ援用設計）の設計、化学プラント、及び建築設計のような大規模３Ｄエンジニアリング・モデルの、セカンド・ライフ（商標）やグーグル・アース（商標）などの種々の仮想世界アプリケーションにおける展開はますます増えてきている。大半のエンジニアリング・モデルでは、平均で最大数百の多角形をそれぞれが有する小型乃至中型の多数の連結成分が存在している。メッシュ・モデルの部分集合は、非特許文献１に規定されているように、その中の何れかの２つの多角形間に経路が存在している場合、連結成分である。更に、このタイプのモデルは、種々の位置、尺度、及び向きで繰り返される幾何特徴をいくつか有する。
【０００３】
西暦１９９０年代初頭より、３Ｄメッシュを効率的に圧縮するための種々のアルゴリズムが提案されている。しかし、初期の研究は大半が、平滑な表面及び小型の三角形により、単一の連結３Ｄモデルを圧縮することに注力している。大規模３Ｄエンジニアリング・モデルなどの多重連結３Ｄモデル（複数の連結成分を含む３Ｄモデル）は別個に圧縮される。これにより、圧縮の相対的な効果が小さくなる。実際に、種々の連結成分間の冗長度をなくすことにより、圧縮性能を大きく増加させることが可能である。
【０００４】
大規模３Ｄエンジニアリング・モデルにおける反復幾何特徴を自動的に発見する方法は、非特許文献１において提案されている。しかし、３Ｄエンジニアリング・モデルの圧縮の効率の向上には、まだ余裕が残されている。例えば、元のモデルを回復するために必要な、反復インスタンスの変換情報を包含する圧縮ソリューションは提供されていない。３Ｄエンジニアリング・モデルが通常有している連結成分の規模が大きいことを考慮すれば、前述の種類の情報は、記憶容量を多く消費することになる。更に、成分の頂点の位置のＰＣＡ（主成分分析）が使用された場合、同じ幾何構造及び異なる連結性を有する成分は同じ平均及び同じ方向軸を有することになる。従来技術は、種々の尺度における反復パターンの検出及び／又は圧縮に適していない。尺度（すなわち、サイズ）においてのみ異なる２つの成分は、同じ等価クラスの反復した特徴として認識されていない。更に、非特許文献１に記載されたものよりも高い圧縮率を実現することが望ましい。
【０００５】
非特許文献２には、メッシュ・モデルの連結成分全ての平均を符号化するためのＫＤツリー・ベースの圧縮アルゴリズムが開示されている。前述のアルゴリズムは、反復毎に、セルを２つの子セルに分割し、２つの子セルの一方における頂点の数を符号化する。親セルがｐ個の頂点を含む場合、子セルのうちの１つにおける頂点の数は、算術符号化器により、ｌｏｇ２（ｐ＋１）個のビットを使用して符号化することが可能である。この分割は、空きでないセルそれぞれが、１つの頂点のみを含めるのに十分小さい状態になるまで反復して施され、頂点の位置の十分に正確な再構成を可能にする。非特許文献２には、非均一分布の場合に最も効率が高く、正規分布が、最も悪いケースであると記載されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｄ． Ｓｈｉｋｈａｒｅ、Ｓ． Ｂｈａｋａｒ、及び Ｓ． Ｐ． Ｍｕｄｕｒ著、「Ｃｏｍｐｒｅｓｓｉｏｎ ｏｆ Ｌａｒｇｅ ３Ｄ Ｅｎｇｉｎｅｅｒｉｎｇ Ｍｏｄｅｌｓ ｕｓｉｎｇ Ａｕｔｏｍａｔｉｃ Ｄｉｓｃｏｖｅｒｙ ｏｆ Ｒｅｐｅａｔｉｎｇ Ｇｅｏｍｅｔｒｉｃ Ｆｅａｔｕｒｅｓ」、 西暦２００１年１１月２１乃至２３日発行（Ｓｔｕｔｔｇａｒｔ、Ｇｅｒｍａｎｙ）
【非特許文献２】Ｄｅｖｉｌｌｅｒｓ， Ｐ． Ｇａｎｄｏｉｎ著、「Ｇｅｏｍｅｔｒｉｃ ｃｏｍｐｒｅｓｓｉｏｎ ｆｏｒ ｉｎｔｅｒａｃｔｉｖｅ ｔｒａｎｓｍｉｓｓｉｏｎ（ＩＥＥＥ Ｖｉｓｕａｌｉｚａｔｉｏｎ）」、２０００年発行， ｐｐ． ３１９−３２６
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、大半の大規模３Ｄエンジニアリング・モデルの場合、連結成分の反復インスタンスのインスタンス位置は複数のかなりの空間集約を示し、この場合、非特許文献２に表されたアルゴリズムの効率を向上させることが可能であるということの認識に基づく。すなわち、大規模３Ｄメッシュ・モデル内の反復インスタンスは多くの場合、いくつかのインスタンスが１つ又は少数の小領域内にある一方で他の比較的大きな領域ではインスタンスが存在しないというように分布している。非特許文献２に提案されているように、前述のタイプの点データ・セットを編成し、圧縮するために単一のＫＤツリーが使用された場合、ＬＤツリーの深度は不合理にも高くなり、これにより、出力データ・ストリームが、必要な長さよりも長くなる。
【０００８】
本発明は、この場合に対する改良をもたらす。本発明によれば、空間集約された一点クラスタ毎にいくつかのＫＤツリーが使用される。前述のＫＤツリーは、比較的短いデータ・ストリームを生成し、よって、全体圧縮率を向上させることになる。
【課題を解決するための手段】
【０００９】
一局面では、本発明はメッシュ・モデルの点を符号化する方法を提供する。方法は、メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定するステップと、少なくとも１つの参照点を反復インスタンス毎に判定するステップと、反復インスタンスの参照点を１つ又は複数のクラスタにクラスタ化するステップと、ＫＤツリー符号化を使用して、クラスタ化された参照点を符号化するステップとを含み、クラスタ毎に、別個のＫＤツリーが生成される。
【００１０】
本発明の別の局面によれば、メッシュ・モデルの点を符号化する装置は、メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定する解析手段と、少なくとも１つの参照点を反復インスタンス毎に判定する判定手段と、１つ又は複数のクラスタに反復インスタンスの参照点をクラスタ化するクラスタ化手段と、ＫＤツリー符号化を使用して、クラスタ化された参照点を符号化する符号化手段とを備え、クラスタ毎に、別個のＫＤツリーが生成される。
【００１１】
本発明の更なる局面によれば、符号化されたメッシュ・モデルの点を復号化する方法は、反復連結成分のインスタンスのデータを抽出するステップと、抽出されたデータを使用して、連結成分のインスタンスを復号化するステップと、クラスタの数」を規定する第１のデータを抽出するステップであって、第２のデータは空間分解能を規定し、第３のデータは、反復連結成分の複数の反復の位置であり、第３のデータは、ＫＤツリーとして符号化されるステップと、メッシュ・モデル内の一部分を規定する第４のデータを抽出するステップと、第３のデータ及び第４のデータから反復連結成分の複数の反復の位置を判定するステップとを含み、第３のデータが、第４のデータによって規定されるメッシュ・モデルの一部分に施される。
【００１２】
本発明の更に別の局面によれば、符号化されたメッシュ・モデルの点を復号化する装置は、符号化されたメッシュ・モデルから反復連結成分のインスタンスのデータを抽出する第１の抽出手段と、抽出されたデータを使用して連結成分のインスタンスを復号化する復号化手段と、クラスタの数を規定する第１のデータを抽出する第２の抽出手段であって、第２のデータが空間分解能を規定し、第３のデータが反復連結成分の複数の反復の位置であり、第３のデータはKDツリーとして符号化される第２の抽出手段とを備え、更に、メッシュ・モデル内の一部分を規定する第４のデータを抽出する第３の抽出手段と、第３のデータ及び第４のデータから、反復する接続された構成部分の複数の反復の位置を判定する判定手段とを備え、第３のデータは、第４のデータによって規定されたメッシュ・モデルの一部分に施される。
【００１３】
本発明の一局面によれば、符号化されたメッシュ・モデルは、複数の反復連結成分を備え、前記符号化されたメッシュ・モデルは、反復連結成分それぞれの少なくとも１つのインスタンスの符号化データ、反復連結成分の複数の反復の位置であって、ＫＤツリーとして符号化される位置、及びメッシュ・モデル内の境界領域を含み、ＫＤツリーは領域を表す。
【図面の簡単な説明】
【００１４】
【図１】２Ｄの例におけるＫＤツリー符号化の原理を示す図である。
【図２】反復連結成分の複数のインスタンスの位置、及び反復連結成分の複数のインスタンスの位置の従来のＫＤツリー符号化の結果を示す図である。
【図３】クラスタ化後のクラスタ位置を示す図である。
【図４】クラスタに基づいた符号化メッシュ・モデルのデータ構造を示す図である。
【図５】５５７４個の連結成分を含む、会議室の例示的な３Ｄメッシュ・モデルの２Ｄ表現を示す図である。
【図６】符号化方法及び復号化方法を示す例示的なフローチャートである。
【図７】クラスタ化方法を示す例示的なフローチャートである。
【発明を実施するための形態】
【００１５】
本発明の効果的な実施例は、従属請求項、明細書の以下の説明、及び図に記載している。
【００１６】
本発明の例示的な実施例は、添付図面を参照して説明する。
【実施例】
【００１７】
図１は、２Ｄケースにおける従来のＫＤツリー符号化の原理を例示的に示す。２Ｄモデルは、親セルと呼ばれるバウンディング・ボックス１０によって囲まれる。７個の頂点が親セル内に配置される。ＫＤツリー符号化アルゴリズムは、所定数のビットを用いた、頂点の合計数の符号化に始まり、次いで、セルを反復して分割する。親セルを２つの子セルに分割する都度、２つの子セルの一方における頂点の数を符号化する。約束ごととして、これは、（垂直方向の分割後の）左子セル又は（水平方向の分割後の）上位セルであり得る。
親セルがｐ個の頂点を含む場合、子セルのうちの１つにおける頂点の数は、算術符号化器により、ｌｏｇ２（ｐ＋１）ビットを使用して符号化することが可能である。空きでないセルそれぞれが、１つの頂点のみを含み、頂点の位置の十分に正確な再構成を可能にするのに十分小さい状態になるまで、この分割が反復的に施される。反復インスタンス全ての位置を圧縮するために、位置全てのバウンディング・ボックス１０全体は最初は親セルとみなされる。図１の例では、頂点の合計数（７）は３２ビットを使用して符号化される。次いで、垂直方向の分割が施され、よって、左子セルＶ１及び右子セルＶ２が得られる。次の符号化ステップでは、左子セルＶ１内の頂点数（すなわち、４）が符号化される。符号化に使用されるビットの数は、親セル内の頂点数によって求められる。これは、ｌｏｇ２（７＋ｌ）＝３ビットである。親セル内の頂点数、及び左子セルＶ１内の頂点数から、右子セルＶ２内の頂点数を推論することが可能であり、したがって、符号化する必要はない。
【００１８】
次のステップでは、水平方向の分割が施される。親セルＶ１である左子セルＶ１は、上位子セルＶ１Ｈ１及び下位子セルＶ１Ｈ２に分割される。親セルＶ２である右子セルＶ２は、上位子セルＶ２Ｈ１及び下位子セルＶ２Ｈ２に分割される。符号化は、２つの頂点を有する上位左子セルＶ１Ｈ１に続く。よって、２という数が次に符号化され、ｌｏｇ２（４＋１）＝２．３ビットが、算術符号化器において使用される。上述の通り、低位左子セルＶ１Ｈ２内の頂点の数は、左セルＶ１内、及び上位左子セルＶ１Ｈ１内の頂点の数から推論することが可能であるため、符号化しなくてよい。次いで、同じ手順が右セルＶ２に施され、それにより、２つのビットを使用してゼロが符号化される。図１に示すように、各頂点が別個のセルに収まる状態になるまで、分離ステップが更に２つ必要であり、各頂点がそのセル内で十分に局所化された状態になるまで、更に多くのステップが必要である。各ステップは、１又はゼロの増加する数を符号化することを必要とする。要求された精度に応じて、更なるステップの数は高いことがあり得る。
【００１９】
非特許文献２は、単一のＫＤツリーが、最適な圧縮をもたらすということを示唆している。しかし、空間的に集約された点の場合、更なる冗長度が存在しており、これを本発明によって削減することができるということが明らかになっている。点の空間的な集約は、後続する複数の分割動作の場合、子セルのうちの１つが常に空きであるということを意味している。したがって、点が空間的に集約されている場合、何れのレベル（ｋ＋１）も、その親レベルｋと同じビット数を消費する。基本的には、ＫＤツリーの従来の使用では、ＫＤツリーの各レベルを狭くすることにより、圧縮率を向上させる。本発明は、複数のＫＤツリーを使用し、各ＫＤツリーに持たせるレベルをより少なくすることにより、圧縮率を向上させる。
【００２０】
本発明は、頂点の位置の符号化にのみならず、反復連結成分の位置の符号化にもＫＤツリー符号化アルゴリズムを施す。図２のａ）は、複数の反復連結成分２１乃至２４が３Ｄメッシュ・モデルのバウンディング・ボックス２０内に配置される例を示す。多くの大きな３Ｄメッシュ・モデルの場合と同様に、位置はバウンディング・ボックス内で非常に不規則に配置される。ＫＤツリー符号化アルゴリズムが、位置を符号化するために施された場合、例示的な結果を図２のｂ）に示す。クラスタが局所化された状態になる前に５つの初期分割ステップが必要であるということが分かる。すなわち、図２の例では、符号は以下の通りになる。
１２（合計数）−６（左子セル、１代目）−６−３（上位子セル、２代目）−２−３−０（Ｌ，３代目）−２−０−０−０（上位、４代目）−２−４−０−３（Ｌ、５代目）−２−０−３−０（上位、６代目）であり、それにより、１２−６−６−３−２−３−０−２−０−０−０−２−４−０−３−２−０−３−０がもたらされる。ビットの数の割り当ては上記の通りである。より正確な位置については、更なるデータが必要であり得る。よって、符号は、ゼロ、又は先行値の数多くの反復を含む。
【００２１】
本発明では、手順も、結果として生じる符号もかなり短い。本発明の一局面によれば、点はクラスタ化される、すなわち、クラスタが作成され、場合によっては、点がクラスタに割り当てられる。図２に示す点は、図３に示すようなやり方で効果的にクラスタ化することが可能である。この例では、４つのクラスタ３１乃至３４が、バウンディング・ボックス３０内に存在している。一般に、クラスタ化は、まだクラスタ化されておらず、１つ又は複数の点を含む第１のセルを選択するステップと、第１のセル内の１つ又は複数の点、若しくは第１のセルを含むクラスタを規定するステップとを含む。
【００２２】
一実施例では、図６のａ）に示すように、メッシュ・モデルの点を符号化する方法は、メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定するステップ（Ｅ１）と、少なくとも１つの参照点を反復インスタンス毎に判定するステップ（Ｅ２）と、反復インスタンスの参照点を１つ又は複数のクラスタにクラスタ化するステップ（Ｅ３）と、ＫＤツリー符号化を使用して、クラスタ化された参照点を符号化するステップ（Ｅ４）とを含み、クラスタ毎に、別個のＫＤツリーが生成される。
【００２３】
一実施例では、クラスタ化するステップは、メッシュ・モデルの周りのバウンディング・ボックスを画定するステップと、バウンディング・ボックスをセルに分割するステップであって、セルが最小空間分解能単位であるステップと、まだクラスタ化されておらず、反復インスタンスの１つ又は複数の参照点を含む第１のセルを選択するステップと、第１のセル内の１つ又は複数の参照点、若しくは第１のセルを含むクラスタを画定するステップとを含む。一般に、第１のセルは、新たなクラスタを作成するための候補である。一実施例では、一セルは、クラスタの作成に十分である。別の実施例では、それぞれが１つ又は複数の点を含む少なくとも２つの隣接セルが、クラスタを作成するために必要である。更に別の実施例では、何れかの数の隣接セル内の所定の最小数の点が、クラスタを作成するために必要である。
【００２４】
一実施例では、第１のセルは、まだクラスタ化されておらず、かつ、少なくともＭ個の点（例えば、Ｍ個の反復インスタンスの参照点）を含む場合にのみ選択される。一実施例では、Ｍはユーザ定義可能なパラメータである。対応する符号化方法はパラメータＭを規定するステップであり、Ｍは、新たなクラスタを作成するためのソースとしてセルを選択するための、セル内の点の最小数である。
【００２５】
一実施例では、クラスタ化は更に、１つ又は複数の更なるセルを判定するステップであって、更なるセルが、選択された第１のセルの近傍セル、又は反復的に近傍（すなわち、近傍の近傍等）のセルであり、判定された更なるセルそれぞれが、反復インスタンスの少なくとも１つの参照点を含むステップと、判定された１つ又は複数の近傍セルをクラスタに加えるステップとを更に含み得る。
【００２６】
一実施例では、クラスタ化は更に、各セルにおける参照点の数の昇順又は降順でセル全てをソートするステップを含み、第１のセル（新たなクラスタを作成するための候補）は、上述の順に応じて選択される。
【００２７】
図５に示す例示的な会議室などの多くの大規模３Ｄエンジニアリング・モデルの場合、インスタンス位置は、複数のかなりの空間集約を示す。１つの単一のＫＤツリーが、前述のタイプの点データ・セットを編成し、圧縮するために使用された場合、ＫＤツリーの深度は不合理に高くなる。他方で、空間的に集約された一点クラスタ毎にいくつかのＫＤツリーが使用された場合、ＫＤツリーは相対的に短いデータ・ストリームを生成し、よって、合計圧縮率を向上させる。例えば、図５に示すように、５５７４個の連結成分を含む会議室の３Ｄモデルでは、複数の反復連結成分は椅子ＲＣＣ１、カーペットの反復テクスチャ要素ＲＣＣ２、又は枝付き燭台の反復構造要素ＲＣＣ３である。大規模３Ｄエンジニアリング・モデルのコンパクトな格納及び高速伝送を可能にするために、本発明は、反復インスタンス全ての位置を符号化するために特に効果的な効率的な圧縮ストラテジを提供する。一局面では、本発明は、離散的な点に対する、特に、複数のかなりの空間集約を示す点に対する効率的な圧縮手法を提供する。大規模３Ｄエンジニアリング・モデルにおける反復インスタンスの位置は多くの場合、前述の種類の特性を有する。
【００２８】
本発明は、複数のかなりの空間集約を備えた離散的な点のデータ・セットを効率的に圧縮するためのクラスタ化されたＫＤツリー・ベースの圧縮アルゴリズムを提供する。入力点は、まず、その空間位置に応じてクラスタ化される。各クラスタは、空間集約された点の組を含む。次いで、各クラスタは、１つのＫＤツリーにより、それに属する点全てを編成することによって圧縮される。
【００２９】
以下に、符号化するための例示的なクラスタ化方法を説明する。Ｃ＿Ｐｏｉｎｔが点クラスタ全てを表すものとする。最初に、Ｃ＿Ｐｏｉｎｔは空きである。
【００３０】
ステップ１： Ｎ＊Ｎ＊Ｎ個のセルに圧縮される対象の点全てのバウンディング・ボックス全体を分割する。
【００３１】
ステップ２： 各セルに収まる点の数の昇順に応じてキューＱ＿Ｃｅｌｌにセル全てをソートする。
【００３２】
ステップ３: Ｑ＿Ｃｅｌｌが空でない場合、
Ｑ＿ＣｅｌｌからセルＰをポップする。空のセルを飛ばす。ステップ４に進む。
【００３３】
さもなければ、ステップ６に進む。
【００３４】
ステップ４： ＰがＣ＿Ｐｏｉｎｔにおける何れのクラスタにも属しない場合、
Ｐのみを含む新たなクラスタＣを生成し、
ＣをＣ＿Ｐｏｉｎｔに加える
ステップ５に進む
さもなければ、ステップ３に進む。
【００３５】
ステップ５： Ｃにおけるセル全ての近傍セル全てを検査する。
【００３６】
Ｐ１は、Ｃにおける何れかのセルの何れかの近傍セルを表す。
【００３７】
Ｐ１に収まる点の数＞Ｂであり、かつ、Ｐ１がＣ＿Ｐｏｉｎｔにおける何れのクラスタにも属さない場合、Ｐ１をＣに加える。（Ｂはユーザ定義された閾値である。）
近傍セル全てについて検査を終了した後、ステップ３に進む。
【００３８】
ステップ６： Ｃ＿Ｐｏｉｎｔにおける同じクラスタに属するセルに収まる点を独立的に圧縮する。各クラスタは、別個のＫＤツリーを使用して、対応する点を編成し、例えば、非特許文献２に基づいて圧縮することにより、圧縮される。
【００３９】
ユーザ定義されたパラメータＢは、クラスタの近傍としてセルが加えられるためにセル内に存在していければならない点の数を規定する。一実施例ではＢ＝１である一方、他の実施例では、Ｂのより高い値を必要とし得る。クラスタ化方法のフローチャートを図７に示す。
【００４０】
結果として生じるビットストリームの構文は表１に示すようなものであり得る。ａｅ（ｖ）は、Ｈ．２６４／ＡＶＣにおける算術符号化と同様な算術符号化を意味する。
【００４１】
【表１】
例示的なビットストリームの意味論は以下の通りである：
ＢｏｕｎｄａｒｙＢｏｘ＿Ｏｆ＿Ａｌｌ＿Ｉｎｓｔａｎｃｅ＿Ｐｏｓｉｔｉｏｎｓは、インスタンス位置全てのバウンディング・ボックスを示す。
【００４２】
Ｎｕｍ＿Ｏｆ＿Ｃｌｕｓｔｅｒｓは、クラスタの数を示す。
【００４３】
Ｎ（すなわち、上記符号化手順のステップ１におけるＮ）は、セルの分解能を示す。
【００４４】
Ｉｎｄｉｃｅｓ＿ｏｆ＿Ｔｗｏ＿Ｂｏｕｎｄａｒｙ＿Ｃｅｌｌｓ＿ｏｆ＿ｃｌｕｓｔｅｒ［ｉ］は、ｃｌｕｓｔｅｒ［ｉ］のバウンディング・ボックスを規定する２つのセルのインデクスを示し、２＊Ｌｏｇ２（ｎ＊ｎ＊ｎ）個のビットを有する。
【００４５】
ＫＤ−ｔｒｅｅ＿ｏｆ＿ｃｕｒｒｅｎｔ＿ｃｌｕｓｔｅｒは、現在のクラスタのＫＤツリーを記録するためのビットを表す。
【００４６】
一実施例では、符号化中、各クラスタの境界、及び対応する２つの境界セルを判定するステップが、実際のクラスタ化後に存在している。境界は、２つの境界セルのインデクスによって表すことが可能である。現在のクラスタの境界セルは、各寸法の最小インデクス及び最大インデクスを備えたセルである。例えば、２Ｄのケースにおいて、クラスタに属する点が｛ｘｍｉｎ，ｘｍａｘ｝及び｛ｙｍｉｎ，ｙｍａｘ｝の範囲内にある場合、境界セルは、実際にクラスタ内になくても、ｘｍｉｎ，ｘｍａｘ、及びｙｍｉｎ，ｙｍａｘにある。しかし、前述のインデクスは、現在のクラスタの局所のバウンディング・ボックスを定義するために使用される。局所バウンディング・ボックス内では、局所座標を使用し、これにより、ビット数が削減され得る。
【００４７】
一実施例では、現在のクラスタのＫＤツリーを算出するステップは、現在のクラスタ［ｉ］に収まるインスタンスの相対位置を算出するステップと、バウンディング・ボックスの世界座標系における対応するインスタンス位置を算出するステップとを含む。
一実施例では、符号化方法は更に、メッシュ・モデルの空間分解能（例えば、表１中のＮ）を規定するステップを更に含む。この場合、セルは、規定された空間分解能に応じた最小空間分解能単位である。符号化中の特定のセル内のどこかである位置は、復号化後、セル内の所定の位置においてのみ、例えば、セルの中心においてのみ、再生することが可能である。位置がより正確であるためには、より高い空間分解能が必要である。一実施例では、Ｎは予め規定されている。別の実施例では、Ｎは品質要件に応じて選択することが可能である（例えば、低分解能ディスプレイ上での再生のために縮小することが可能である）。
【００４８】
上述のように、従来技術の方法は、点が非常に不均一に分布している場合、効果がない。一実施例では、符号化方法は更に、点の空間的均一性の尺度を判定するステップ（空間的均一性の尺度は、点が均一に分布している場合に高く、分布がより不規則な場合に低い）と、空間的均一性を閾値と比較するステップと、空間的均一性が閾値未満である場合にのみ、クラスタ化を行うステップとを含む。例えば、符号化方法は、反復インスタンスの参照点の空間的均一性の尺度を判定するステップと、空間的均一性を閾値と比較するステップと、空間的均一性が閾値未満である場合（すなわち、点の分布が非常に不均一である場合）にのみクラスタ化を行うステップとを含む。
【００４９】
一実施例では、符号化方法は、空間的均一性が閾値未満である場合、空間分解能を修正するステップと、空間的均一性を測定するステップと、空間的均一性が閾値未満でない状態になるまで前述のステップを反復するステップとを更に含む。
【００５０】
図４は、クラスタに基づいた符号化メッシュ・モデルのデータ構造を示す。完全な３Ｄメッシュ・モデル及び連結成分の特定のタイプを表すルートは、反復連結成分を表し、ＫＤツリー ＫＤ−Ｔ１、…、ＫＤ−Ｔ３として表される少なくとも１つのクラスタを備える。
【００５１】
図４の例では、連結成分ルートＣＣｒは、特定の連結成分の略である。例えば、連結成分は、３Ｄエンジニアリング・モデルにおける特定のタイプのねじであり得る。上記例では、このタイプのねじが非常に多く使用される、３Ｄモデル内の領域は３つ存在している。領域それぞれは、別個のＫＤツリー ＫＤ−Ｔ１、…、ＫＤ−Ｔ３によって表されるクラスタとして表す。連結成分の少数のインスタンス又は単一のインスタンスは、他の領域にも現れ得る。一実施例では、前述のインスタンスはクラスタ化されていない一方、その位置は、別個の構造Ｔ４（例えば、特別なＫＤツリー、又は座標のリストのみ）において表される。３つのクラスタＫＤツリー ＫＤ−Ｔ１、…、ＫＤ−Ｔ３はそれぞれ、連結成分の複数のインスタンスの一クラスタを表し、位置情報、例えば、クラスタの境界セルのインデクスを含む。
【００５２】
以下では、本発明の更なる実施例を説明する。
【００５３】
一実施例では、メッシュ・モデルの点を符号化する装置は、メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定する判定手段と、少なくとも１つの参照点を反復インスタンス毎に判定する判定手段と、反復インスタンスの参照点を１つ又は複数のクラスタにクラスタ化するクラスタ化手段と、ＫＤツリー符号化を使用して、クラスタ化された参照点を符号化する符号化手段とを備え、クラスタ毎に、別個のＫＤツリーが生成される。
【００５４】
一実施例では、クラスタ化手段は、メッシュ・モデル周りのバウンディング・ボックスを画定する画定手段と、バウンディング・ボックスをセルに分割する分割手段であって、セルが最小空間分解能単位である分割手段と、まだクラスタ化されておらず、反復インスタンスの１つ又は複数の参照点を含む第１のセルを選択する選択手段と、第１のセル内の１つ又は複数の参照点、若しくは第１のセルを含むクラスタを画定する画定手段とを備える。
【００５５】
一実施例では、装置は、１つ又は複数の更なるセルを判定する判定手段であって、更なるセルは、選択された第１のセルの近傍セル、又は反復的な近傍のセルであり、判定された更なるセルはそれぞれ、反復インスタンスの少なくとも１つの参照点を備える判定手段と、判定された１つ又は複数の近傍セルをクラスタに付加する付加手段とを更に備える。
一実施例では、クラスタ化手段は更に、各セルにおける参照点の数の昇順又は降順にセル全てをソートする編成手段を更に備え、第１のセル（すなわち、クラスタの初期セル）は、上述の順序に応じて選択される。
【００５６】
一実施例では、クラスタ化手段は、現在のクラスタの境界セル（各寸法の最小インデクス及び最大インデクスを備えたセルである）を判定する手段を備える。
【００５７】
一実施例では、符号化装置は、空間分解能を規定する手段を更に備え、セルは、規定された空間分解能に応じた、最小の空間分解能単位である。
【００５８】
一実施例では、符号化装置は、反復インスタンスの参照点の空間的均一性の尺度を判定する解析手段であって、空間的均一性の尺度は参照点が均一に分布している場合に高く、分布がより不規則である場合に低い解析手段と、空間的均一性を閾値と比較する比較器手段と、空間的均一性が閾値を下回る場合にのみ、クラスタ化が行われるよう制御する制御手段とを備える。
【００５９】
一実施例では、符号化されたメッシュ・モデルは複数の反復連結成分を備え、符号化されたメッシュ・モデルは、反復連結成分それぞれの少なくとも１つのインスタンスの符号化データ、反復連結成分の複数の反復の位置であって、ＫＤツリーとして符号化された位置、及び、メッシュ・モデル内の境界領域を含み、ＫＤツリーは領域を表す。
【００６０】
一実施例では、符号化されたメッシュ・モデルの境界領域のデータは、境界セルのインデクスを備える。
【００６１】
図６のｂ）に示す一実施例では、符号化されたメッシュ・モデルの点を復号化する方法は、反復連結成分のインスタンスのデータを抽出するステップ（Ｄ１）と、抽出されたデータを使用して連結成分のインスタンスを復号化するステップ（Ｄ２）と、クラスタ数を規定する第１のデータ（Ｎｕｍ＿Ｏｆ＿Ｃｌｕｓｔｅｒｓ）を抽出するステップ（Ｄ３）であって、第２のデータ（Ｎ）が空間分解能を規定し、第３のデータ（ＫＤ−Ｔ１、…、ＫＤ−Ｔ３）が反復連結成分の複数の反復の位置であり、第３のデータがＫＤツリーとして符号化されるステップと、第４のデータ（Ｉｎｄｅｘ＿Ｂｏｕｎｄａｒｙ＿Ｃｌｕｓｔｅｒ）を抽出するステップ（Ｄ４）と、第３のデータ及び第４のデータから反復連結成分の複数の反復の位置を判定するステップ（Ｄ５）とを含み、第３のデータは、第４のデータによって規定されるメッシュ・モデルの部分に施される。
【００６２】
復号化のための方法の一実施例では、第４のデータ（Ｉｎｄｅｘ＿Ｂｏｕｎｄａｒｙ＿Ｃｌｕｓｔｅｒ）はメッシュ・モデル内の２つのセルのインデクスを備え、セルは、第２のデータによって規定される空間分解能に応じた最小空間分解能単位である。
【００６３】
パターン位置データの場合、本発明によるクラスタ・ベースのＫＤツリー圧縮は、従来のＫＤツリー・ベースの圧縮と比較して、約５０％の記憶空間（Ｃｌｕｓ＿Ｃｏｍｐ／Ｃｏｏｒ＿Ｃｏｍｐ）を節減することが可能である。
【００６４】
表２では、＃Ｃは連結成分の数であり、＃Ｐは反復成分の数であり、Ｃｏｏｒ．（Ｋ）は、未処理インスタンス位置のサイズ（単位：Ｋバイト）であり、Ｃｏｏｒ＿Ｃｏｍｐ（Ｋ）は１つのＫＤツリーを使用した圧縮インスタンス位置のサイズであり、＃Ｃｌｕはクラスタの数であり、Ｃｌｕ＿Ｃｏｏｒ＿Ｃｏｍｐ（Ｋ）は、クラスタ化されたＫＤツリー・ベースの圧縮方法による圧縮インスタンス位置のサイズである。
【００６５】
【表２】
好ましい実施例に施された、本発明の新しい基本構成を示し、説明し、指摘してきたが、開示された装置の形式及び詳細、並びに、その動作において、上述の装置及び方法における種々の割愛、置換、及び変更を、本発明の趣旨から逸脱しない限り、当業者によって行い得る。本発明は反復連結成分のインスタンス位置に関して開示してきたが、本明細書及び特許請求の範囲記載の方法及び装置は基本的には、離散点の群の圧縮に関する何れかのシナリオに施し得るということを当業者は認識するであろう。同じ結果を達成するために実質的に同じやり方で実質的に同じ機能を行う構成要素の組合せは全て、本発明の範囲内にあることを明示的に意図している。上述の一実施例から別の実施例に要素を置き換えることも、完全に意図され、想定されている。
【００６６】
本発明は例として表しているに過ぎず、本発明の範囲から逸脱しない限り、詳細の修正を行うことが可能である。明細書に記載された特徴それぞれ、及び（請求項及び図面に記載されている場合には）請求項及び図面に記載された特徴それぞれは、独立して、又は何れかの適切な組み合わせで提供し得る。特徴は、適宜、ハードウェア、ソフトウェア、又はそれらの２つの組合せで実現し得る。請求項記載の参照符号は、例証のみの目的に過ぎず、請求項の範囲を限定する制限的な効果を有しない。
【技術分野】
【０００１】
本発明は、メッシュ・モデルを符号化する方法及び装置、符号化されたメッシュ・モデル、及びメッシュ・モデルを復号化する方法及び装置に関する。
【背景技術】
【０００２】
機械ＣＡＤ（コンピュータ援用設計）の設計、化学プラント、及び建築設計のような大規模３Ｄエンジニアリング・モデルの、セカンド・ライフ（商標）やグーグル・アース（商標）などの種々の仮想世界アプリケーションにおける展開はますます増えてきている。大半のエンジニアリング・モデルでは、平均で最大数百の多角形をそれぞれが有する小型乃至中型の多数の連結成分が存在している。メッシュ・モデルの部分集合は、非特許文献１に規定されているように、その中の何れかの２つの多角形間に経路が存在している場合、連結成分である。更に、このタイプのモデルは、種々の位置、尺度、及び向きで繰り返される幾何特徴をいくつか有する。
【０００３】
西暦１９９０年代初頭より、３Ｄメッシュを効率的に圧縮するための種々のアルゴリズムが提案されている。しかし、初期の研究は大半が、平滑な表面及び小型の三角形により、単一の連結３Ｄモデルを圧縮することに注力している。大規模３Ｄエンジニアリング・モデルなどの多重連結３Ｄモデル（複数の連結成分を含む３Ｄモデル）は別個に圧縮される。これにより、圧縮の相対的な効果が小さくなる。実際に、種々の連結成分間の冗長度をなくすことにより、圧縮性能を大きく増加させることが可能である。
【０００４】
大規模３Ｄエンジニアリング・モデルにおける反復幾何特徴を自動的に発見する方法は、非特許文献１において提案されている。しかし、３Ｄエンジニアリング・モデルの圧縮の効率の向上には、まだ余裕が残されている。例えば、元のモデルを回復するために必要な、反復インスタンスの変換情報を包含する圧縮ソリューションは提供されていない。３Ｄエンジニアリング・モデルが通常有している連結成分の規模が大きいことを考慮すれば、前述の種類の情報は、記憶容量を多く消費することになる。更に、成分の頂点の位置のＰＣＡ（主成分分析）が使用された場合、同じ幾何構造及び異なる連結性を有する成分は同じ平均及び同じ方向軸を有することになる。従来技術は、種々の尺度における反復パターンの検出及び／又は圧縮に適していない。尺度（すなわち、サイズ）においてのみ異なる２つの成分は、同じ等価クラスの反復した特徴として認識されていない。更に、非特許文献１に記載されたものよりも高い圧縮率を実現することが望ましい。
【０００５】
非特許文献２には、メッシュ・モデルの連結成分全ての平均を符号化するためのＫＤツリー・ベースの圧縮アルゴリズムが開示されている。前述のアルゴリズムは、反復毎に、セルを２つの子セルに分割し、２つの子セルの一方における頂点の数を符号化する。親セルがｐ個の頂点を含む場合、子セルのうちの１つにおける頂点の数は、算術符号化器により、ｌｏｇ２（ｐ＋１）個のビットを使用して符号化することが可能である。この分割は、空きでないセルそれぞれが、１つの頂点のみを含めるのに十分小さい状態になるまで反復して施され、頂点の位置の十分に正確な再構成を可能にする。非特許文献２には、非均一分布の場合に最も効率が高く、正規分布が、最も悪いケースであると記載されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｄ． Ｓｈｉｋｈａｒｅ、Ｓ． Ｂｈａｋａｒ、及び Ｓ． Ｐ． Ｍｕｄｕｒ著、「Ｃｏｍｐｒｅｓｓｉｏｎ ｏｆ Ｌａｒｇｅ ３Ｄ Ｅｎｇｉｎｅｅｒｉｎｇ Ｍｏｄｅｌｓ ｕｓｉｎｇ Ａｕｔｏｍａｔｉｃ Ｄｉｓｃｏｖｅｒｙ ｏｆ Ｒｅｐｅａｔｉｎｇ Ｇｅｏｍｅｔｒｉｃ Ｆｅａｔｕｒｅｓ」、 西暦２００１年１１月２１乃至２３日発行（Ｓｔｕｔｔｇａｒｔ、Ｇｅｒｍａｎｙ）
【非特許文献２】Ｄｅｖｉｌｌｅｒｓ， Ｐ． Ｇａｎｄｏｉｎ著、「Ｇｅｏｍｅｔｒｉｃ ｃｏｍｐｒｅｓｓｉｏｎ ｆｏｒ ｉｎｔｅｒａｃｔｉｖｅ ｔｒａｎｓｍｉｓｓｉｏｎ（ＩＥＥＥ Ｖｉｓｕａｌｉｚａｔｉｏｎ）」、２０００年発行， ｐｐ． ３１９−３２６
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、大半の大規模３Ｄエンジニアリング・モデルの場合、連結成分の反復インスタンスのインスタンス位置は複数のかなりの空間集約を示し、この場合、非特許文献２に表されたアルゴリズムの効率を向上させることが可能であるということの認識に基づく。すなわち、大規模３Ｄメッシュ・モデル内の反復インスタンスは多くの場合、いくつかのインスタンスが１つ又は少数の小領域内にある一方で他の比較的大きな領域ではインスタンスが存在しないというように分布している。非特許文献２に提案されているように、前述のタイプの点データ・セットを編成し、圧縮するために単一のＫＤツリーが使用された場合、ＬＤツリーの深度は不合理にも高くなり、これにより、出力データ・ストリームが、必要な長さよりも長くなる。
【０００８】
本発明は、この場合に対する改良をもたらす。本発明によれば、空間集約された一点クラスタ毎にいくつかのＫＤツリーが使用される。前述のＫＤツリーは、比較的短いデータ・ストリームを生成し、よって、全体圧縮率を向上させることになる。
【課題を解決するための手段】
【０００９】
一局面では、本発明はメッシュ・モデルの点を符号化する方法を提供する。方法は、メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定するステップと、少なくとも１つの参照点を反復インスタンス毎に判定するステップと、反復インスタンスの参照点を１つ又は複数のクラスタにクラスタ化するステップと、ＫＤツリー符号化を使用して、クラスタ化された参照点を符号化するステップとを含み、クラスタ毎に、別個のＫＤツリーが生成される。
【００１０】
本発明の別の局面によれば、メッシュ・モデルの点を符号化する装置は、メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定する解析手段と、少なくとも１つの参照点を反復インスタンス毎に判定する判定手段と、１つ又は複数のクラスタに反復インスタンスの参照点をクラスタ化するクラスタ化手段と、ＫＤツリー符号化を使用して、クラスタ化された参照点を符号化する符号化手段とを備え、クラスタ毎に、別個のＫＤツリーが生成される。
【００１１】
本発明の更なる局面によれば、符号化されたメッシュ・モデルの点を復号化する方法は、反復連結成分のインスタンスのデータを抽出するステップと、抽出されたデータを使用して、連結成分のインスタンスを復号化するステップと、クラスタの数」を規定する第１のデータを抽出するステップであって、第２のデータは空間分解能を規定し、第３のデータは、反復連結成分の複数の反復の位置であり、第３のデータは、ＫＤツリーとして符号化されるステップと、メッシュ・モデル内の一部分を規定する第４のデータを抽出するステップと、第３のデータ及び第４のデータから反復連結成分の複数の反復の位置を判定するステップとを含み、第３のデータが、第４のデータによって規定されるメッシュ・モデルの一部分に施される。
【００１２】
本発明の更に別の局面によれば、符号化されたメッシュ・モデルの点を復号化する装置は、符号化されたメッシュ・モデルから反復連結成分のインスタンスのデータを抽出する第１の抽出手段と、抽出されたデータを使用して連結成分のインスタンスを復号化する復号化手段と、クラスタの数を規定する第１のデータを抽出する第２の抽出手段であって、第２のデータが空間分解能を規定し、第３のデータが反復連結成分の複数の反復の位置であり、第３のデータはKDツリーとして符号化される第２の抽出手段とを備え、更に、メッシュ・モデル内の一部分を規定する第４のデータを抽出する第３の抽出手段と、第３のデータ及び第４のデータから、反復する接続された構成部分の複数の反復の位置を判定する判定手段とを備え、第３のデータは、第４のデータによって規定されたメッシュ・モデルの一部分に施される。
【００１３】
本発明の一局面によれば、符号化されたメッシュ・モデルは、複数の反復連結成分を備え、前記符号化されたメッシュ・モデルは、反復連結成分それぞれの少なくとも１つのインスタンスの符号化データ、反復連結成分の複数の反復の位置であって、ＫＤツリーとして符号化される位置、及びメッシュ・モデル内の境界領域を含み、ＫＤツリーは領域を表す。
【図面の簡単な説明】
【００１４】
【図１】２Ｄの例におけるＫＤツリー符号化の原理を示す図である。
【図２】反復連結成分の複数のインスタンスの位置、及び反復連結成分の複数のインスタンスの位置の従来のＫＤツリー符号化の結果を示す図である。
【図３】クラスタ化後のクラスタ位置を示す図である。
【図４】クラスタに基づいた符号化メッシュ・モデルのデータ構造を示す図である。
【図５】５５７４個の連結成分を含む、会議室の例示的な３Ｄメッシュ・モデルの２Ｄ表現を示す図である。
【図６】符号化方法及び復号化方法を示す例示的なフローチャートである。
【図７】クラスタ化方法を示す例示的なフローチャートである。
【発明を実施するための形態】
【００１５】
本発明の効果的な実施例は、従属請求項、明細書の以下の説明、及び図に記載している。
【００１６】
本発明の例示的な実施例は、添付図面を参照して説明する。
【実施例】
【００１７】
図１は、２Ｄケースにおける従来のＫＤツリー符号化の原理を例示的に示す。２Ｄモデルは、親セルと呼ばれるバウンディング・ボックス１０によって囲まれる。７個の頂点が親セル内に配置される。ＫＤツリー符号化アルゴリズムは、所定数のビットを用いた、頂点の合計数の符号化に始まり、次いで、セルを反復して分割する。親セルを２つの子セルに分割する都度、２つの子セルの一方における頂点の数を符号化する。約束ごととして、これは、（垂直方向の分割後の）左子セル又は（水平方向の分割後の）上位セルであり得る。
親セルがｐ個の頂点を含む場合、子セルのうちの１つにおける頂点の数は、算術符号化器により、ｌｏｇ２（ｐ＋１）ビットを使用して符号化することが可能である。空きでないセルそれぞれが、１つの頂点のみを含み、頂点の位置の十分に正確な再構成を可能にするのに十分小さい状態になるまで、この分割が反復的に施される。反復インスタンス全ての位置を圧縮するために、位置全てのバウンディング・ボックス１０全体は最初は親セルとみなされる。図１の例では、頂点の合計数（７）は３２ビットを使用して符号化される。次いで、垂直方向の分割が施され、よって、左子セルＶ１及び右子セルＶ２が得られる。次の符号化ステップでは、左子セルＶ１内の頂点数（すなわち、４）が符号化される。符号化に使用されるビットの数は、親セル内の頂点数によって求められる。これは、ｌｏｇ２（７＋ｌ）＝３ビットである。親セル内の頂点数、及び左子セルＶ１内の頂点数から、右子セルＶ２内の頂点数を推論することが可能であり、したがって、符号化する必要はない。
【００１８】
次のステップでは、水平方向の分割が施される。親セルＶ１である左子セルＶ１は、上位子セルＶ１Ｈ１及び下位子セルＶ１Ｈ２に分割される。親セルＶ２である右子セルＶ２は、上位子セルＶ２Ｈ１及び下位子セルＶ２Ｈ２に分割される。符号化は、２つの頂点を有する上位左子セルＶ１Ｈ１に続く。よって、２という数が次に符号化され、ｌｏｇ２（４＋１）＝２．３ビットが、算術符号化器において使用される。上述の通り、低位左子セルＶ１Ｈ２内の頂点の数は、左セルＶ１内、及び上位左子セルＶ１Ｈ１内の頂点の数から推論することが可能であるため、符号化しなくてよい。次いで、同じ手順が右セルＶ２に施され、それにより、２つのビットを使用してゼロが符号化される。図１に示すように、各頂点が別個のセルに収まる状態になるまで、分離ステップが更に２つ必要であり、各頂点がそのセル内で十分に局所化された状態になるまで、更に多くのステップが必要である。各ステップは、１又はゼロの増加する数を符号化することを必要とする。要求された精度に応じて、更なるステップの数は高いことがあり得る。
【００１９】
非特許文献２は、単一のＫＤツリーが、最適な圧縮をもたらすということを示唆している。しかし、空間的に集約された点の場合、更なる冗長度が存在しており、これを本発明によって削減することができるということが明らかになっている。点の空間的な集約は、後続する複数の分割動作の場合、子セルのうちの１つが常に空きであるということを意味している。したがって、点が空間的に集約されている場合、何れのレベル（ｋ＋１）も、その親レベルｋと同じビット数を消費する。基本的には、ＫＤツリーの従来の使用では、ＫＤツリーの各レベルを狭くすることにより、圧縮率を向上させる。本発明は、複数のＫＤツリーを使用し、各ＫＤツリーに持たせるレベルをより少なくすることにより、圧縮率を向上させる。
【００２０】
本発明は、頂点の位置の符号化にのみならず、反復連結成分の位置の符号化にもＫＤツリー符号化アルゴリズムを施す。図２のａ）は、複数の反復連結成分２１乃至２４が３Ｄメッシュ・モデルのバウンディング・ボックス２０内に配置される例を示す。多くの大きな３Ｄメッシュ・モデルの場合と同様に、位置はバウンディング・ボックス内で非常に不規則に配置される。ＫＤツリー符号化アルゴリズムが、位置を符号化するために施された場合、例示的な結果を図２のｂ）に示す。クラスタが局所化された状態になる前に５つの初期分割ステップが必要であるということが分かる。すなわち、図２の例では、符号は以下の通りになる。
１２（合計数）−６（左子セル、１代目）−６−３（上位子セル、２代目）−２−３−０（Ｌ，３代目）−２−０−０−０（上位、４代目）−２−４−０−３（Ｌ、５代目）−２−０−３−０（上位、６代目）であり、それにより、１２−６−６−３−２−３−０−２−０−０−０−２−４−０−３−２−０−３−０がもたらされる。ビットの数の割り当ては上記の通りである。より正確な位置については、更なるデータが必要であり得る。よって、符号は、ゼロ、又は先行値の数多くの反復を含む。
【００２１】
本発明では、手順も、結果として生じる符号もかなり短い。本発明の一局面によれば、点はクラスタ化される、すなわち、クラスタが作成され、場合によっては、点がクラスタに割り当てられる。図２に示す点は、図３に示すようなやり方で効果的にクラスタ化することが可能である。この例では、４つのクラスタ３１乃至３４が、バウンディング・ボックス３０内に存在している。一般に、クラスタ化は、まだクラスタ化されておらず、１つ又は複数の点を含む第１のセルを選択するステップと、第１のセル内の１つ又は複数の点、若しくは第１のセルを含むクラスタを規定するステップとを含む。
【００２２】
一実施例では、図６のａ）に示すように、メッシュ・モデルの点を符号化する方法は、メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定するステップ（Ｅ１）と、少なくとも１つの参照点を反復インスタンス毎に判定するステップ（Ｅ２）と、反復インスタンスの参照点を１つ又は複数のクラスタにクラスタ化するステップ（Ｅ３）と、ＫＤツリー符号化を使用して、クラスタ化された参照点を符号化するステップ（Ｅ４）とを含み、クラスタ毎に、別個のＫＤツリーが生成される。
【００２３】
一実施例では、クラスタ化するステップは、メッシュ・モデルの周りのバウンディング・ボックスを画定するステップと、バウンディング・ボックスをセルに分割するステップであって、セルが最小空間分解能単位であるステップと、まだクラスタ化されておらず、反復インスタンスの１つ又は複数の参照点を含む第１のセルを選択するステップと、第１のセル内の１つ又は複数の参照点、若しくは第１のセルを含むクラスタを画定するステップとを含む。一般に、第１のセルは、新たなクラスタを作成するための候補である。一実施例では、一セルは、クラスタの作成に十分である。別の実施例では、それぞれが１つ又は複数の点を含む少なくとも２つの隣接セルが、クラスタを作成するために必要である。更に別の実施例では、何れかの数の隣接セル内の所定の最小数の点が、クラスタを作成するために必要である。
【００２４】
一実施例では、第１のセルは、まだクラスタ化されておらず、かつ、少なくともＭ個の点（例えば、Ｍ個の反復インスタンスの参照点）を含む場合にのみ選択される。一実施例では、Ｍはユーザ定義可能なパラメータである。対応する符号化方法はパラメータＭを規定するステップであり、Ｍは、新たなクラスタを作成するためのソースとしてセルを選択するための、セル内の点の最小数である。
【００２５】
一実施例では、クラスタ化は更に、１つ又は複数の更なるセルを判定するステップであって、更なるセルが、選択された第１のセルの近傍セル、又は反復的に近傍（すなわち、近傍の近傍等）のセルであり、判定された更なるセルそれぞれが、反復インスタンスの少なくとも１つの参照点を含むステップと、判定された１つ又は複数の近傍セルをクラスタに加えるステップとを更に含み得る。
【００２６】
一実施例では、クラスタ化は更に、各セルにおける参照点の数の昇順又は降順でセル全てをソートするステップを含み、第１のセル（新たなクラスタを作成するための候補）は、上述の順に応じて選択される。
【００２７】
図５に示す例示的な会議室などの多くの大規模３Ｄエンジニアリング・モデルの場合、インスタンス位置は、複数のかなりの空間集約を示す。１つの単一のＫＤツリーが、前述のタイプの点データ・セットを編成し、圧縮するために使用された場合、ＫＤツリーの深度は不合理に高くなる。他方で、空間的に集約された一点クラスタ毎にいくつかのＫＤツリーが使用された場合、ＫＤツリーは相対的に短いデータ・ストリームを生成し、よって、合計圧縮率を向上させる。例えば、図５に示すように、５５７４個の連結成分を含む会議室の３Ｄモデルでは、複数の反復連結成分は椅子ＲＣＣ１、カーペットの反復テクスチャ要素ＲＣＣ２、又は枝付き燭台の反復構造要素ＲＣＣ３である。大規模３Ｄエンジニアリング・モデルのコンパクトな格納及び高速伝送を可能にするために、本発明は、反復インスタンス全ての位置を符号化するために特に効果的な効率的な圧縮ストラテジを提供する。一局面では、本発明は、離散的な点に対する、特に、複数のかなりの空間集約を示す点に対する効率的な圧縮手法を提供する。大規模３Ｄエンジニアリング・モデルにおける反復インスタンスの位置は多くの場合、前述の種類の特性を有する。
【００２８】
本発明は、複数のかなりの空間集約を備えた離散的な点のデータ・セットを効率的に圧縮するためのクラスタ化されたＫＤツリー・ベースの圧縮アルゴリズムを提供する。入力点は、まず、その空間位置に応じてクラスタ化される。各クラスタは、空間集約された点の組を含む。次いで、各クラスタは、１つのＫＤツリーにより、それに属する点全てを編成することによって圧縮される。
【００２９】
以下に、符号化するための例示的なクラスタ化方法を説明する。Ｃ＿Ｐｏｉｎｔが点クラスタ全てを表すものとする。最初に、Ｃ＿Ｐｏｉｎｔは空きである。
【００３０】
ステップ１： Ｎ＊Ｎ＊Ｎ個のセルに圧縮される対象の点全てのバウンディング・ボックス全体を分割する。
【００３１】
ステップ２： 各セルに収まる点の数の昇順に応じてキューＱ＿Ｃｅｌｌにセル全てをソートする。
【００３２】
ステップ３: Ｑ＿Ｃｅｌｌが空でない場合、
Ｑ＿ＣｅｌｌからセルＰをポップする。空のセルを飛ばす。ステップ４に進む。
【００３３】
さもなければ、ステップ６に進む。
【００３４】
ステップ４： ＰがＣ＿Ｐｏｉｎｔにおける何れのクラスタにも属しない場合、
Ｐのみを含む新たなクラスタＣを生成し、
ＣをＣ＿Ｐｏｉｎｔに加える
ステップ５に進む
さもなければ、ステップ３に進む。
【００３５】
ステップ５： Ｃにおけるセル全ての近傍セル全てを検査する。
【００３６】
Ｐ１は、Ｃにおける何れかのセルの何れかの近傍セルを表す。
【００３７】
Ｐ１に収まる点の数＞Ｂであり、かつ、Ｐ１がＣ＿Ｐｏｉｎｔにおける何れのクラスタにも属さない場合、Ｐ１をＣに加える。（Ｂはユーザ定義された閾値である。）
近傍セル全てについて検査を終了した後、ステップ３に進む。
【００３８】
ステップ６： Ｃ＿Ｐｏｉｎｔにおける同じクラスタに属するセルに収まる点を独立的に圧縮する。各クラスタは、別個のＫＤツリーを使用して、対応する点を編成し、例えば、非特許文献２に基づいて圧縮することにより、圧縮される。
【００３９】
ユーザ定義されたパラメータＢは、クラスタの近傍としてセルが加えられるためにセル内に存在していければならない点の数を規定する。一実施例ではＢ＝１である一方、他の実施例では、Ｂのより高い値を必要とし得る。クラスタ化方法のフローチャートを図７に示す。
【００４０】
結果として生じるビットストリームの構文は表１に示すようなものであり得る。ａｅ（ｖ）は、Ｈ．２６４／ＡＶＣにおける算術符号化と同様な算術符号化を意味する。
【００４１】
【表１】
例示的なビットストリームの意味論は以下の通りである：
ＢｏｕｎｄａｒｙＢｏｘ＿Ｏｆ＿Ａｌｌ＿Ｉｎｓｔａｎｃｅ＿Ｐｏｓｉｔｉｏｎｓは、インスタンス位置全てのバウンディング・ボックスを示す。
【００４２】
Ｎｕｍ＿Ｏｆ＿Ｃｌｕｓｔｅｒｓは、クラスタの数を示す。
【００４３】
Ｎ（すなわち、上記符号化手順のステップ１におけるＮ）は、セルの分解能を示す。
【００４４】
Ｉｎｄｉｃｅｓ＿ｏｆ＿Ｔｗｏ＿Ｂｏｕｎｄａｒｙ＿Ｃｅｌｌｓ＿ｏｆ＿ｃｌｕｓｔｅｒ［ｉ］は、ｃｌｕｓｔｅｒ［ｉ］のバウンディング・ボックスを規定する２つのセルのインデクスを示し、２＊Ｌｏｇ２（ｎ＊ｎ＊ｎ）個のビットを有する。
【００４５】
ＫＤ−ｔｒｅｅ＿ｏｆ＿ｃｕｒｒｅｎｔ＿ｃｌｕｓｔｅｒは、現在のクラスタのＫＤツリーを記録するためのビットを表す。
【００４６】
一実施例では、符号化中、各クラスタの境界、及び対応する２つの境界セルを判定するステップが、実際のクラスタ化後に存在している。境界は、２つの境界セルのインデクスによって表すことが可能である。現在のクラスタの境界セルは、各寸法の最小インデクス及び最大インデクスを備えたセルである。例えば、２Ｄのケースにおいて、クラスタに属する点が｛ｘｍｉｎ，ｘｍａｘ｝及び｛ｙｍｉｎ，ｙｍａｘ｝の範囲内にある場合、境界セルは、実際にクラスタ内になくても、ｘｍｉｎ，ｘｍａｘ、及びｙｍｉｎ，ｙｍａｘにある。しかし、前述のインデクスは、現在のクラスタの局所のバウンディング・ボックスを定義するために使用される。局所バウンディング・ボックス内では、局所座標を使用し、これにより、ビット数が削減され得る。
【００４７】
一実施例では、現在のクラスタのＫＤツリーを算出するステップは、現在のクラスタ［ｉ］に収まるインスタンスの相対位置を算出するステップと、バウンディング・ボックスの世界座標系における対応するインスタンス位置を算出するステップとを含む。
一実施例では、符号化方法は更に、メッシュ・モデルの空間分解能（例えば、表１中のＮ）を規定するステップを更に含む。この場合、セルは、規定された空間分解能に応じた最小空間分解能単位である。符号化中の特定のセル内のどこかである位置は、復号化後、セル内の所定の位置においてのみ、例えば、セルの中心においてのみ、再生することが可能である。位置がより正確であるためには、より高い空間分解能が必要である。一実施例では、Ｎは予め規定されている。別の実施例では、Ｎは品質要件に応じて選択することが可能である（例えば、低分解能ディスプレイ上での再生のために縮小することが可能である）。
【００４８】
上述のように、従来技術の方法は、点が非常に不均一に分布している場合、効果がない。一実施例では、符号化方法は更に、点の空間的均一性の尺度を判定するステップ（空間的均一性の尺度は、点が均一に分布している場合に高く、分布がより不規則な場合に低い）と、空間的均一性を閾値と比較するステップと、空間的均一性が閾値未満である場合にのみ、クラスタ化を行うステップとを含む。例えば、符号化方法は、反復インスタンスの参照点の空間的均一性の尺度を判定するステップと、空間的均一性を閾値と比較するステップと、空間的均一性が閾値未満である場合（すなわち、点の分布が非常に不均一である場合）にのみクラスタ化を行うステップとを含む。
【００４９】
一実施例では、符号化方法は、空間的均一性が閾値未満である場合、空間分解能を修正するステップと、空間的均一性を測定するステップと、空間的均一性が閾値未満でない状態になるまで前述のステップを反復するステップとを更に含む。
【００５０】
図４は、クラスタに基づいた符号化メッシュ・モデルのデータ構造を示す。完全な３Ｄメッシュ・モデル及び連結成分の特定のタイプを表すルートは、反復連結成分を表し、ＫＤツリー ＫＤ−Ｔ１、…、ＫＤ−Ｔ３として表される少なくとも１つのクラスタを備える。
【００５１】
図４の例では、連結成分ルートＣＣｒは、特定の連結成分の略である。例えば、連結成分は、３Ｄエンジニアリング・モデルにおける特定のタイプのねじであり得る。上記例では、このタイプのねじが非常に多く使用される、３Ｄモデル内の領域は３つ存在している。領域それぞれは、別個のＫＤツリー ＫＤ−Ｔ１、…、ＫＤ−Ｔ３によって表されるクラスタとして表す。連結成分の少数のインスタンス又は単一のインスタンスは、他の領域にも現れ得る。一実施例では、前述のインスタンスはクラスタ化されていない一方、その位置は、別個の構造Ｔ４（例えば、特別なＫＤツリー、又は座標のリストのみ）において表される。３つのクラスタＫＤツリー ＫＤ−Ｔ１、…、ＫＤ−Ｔ３はそれぞれ、連結成分の複数のインスタンスの一クラスタを表し、位置情報、例えば、クラスタの境界セルのインデクスを含む。
【００５２】
以下では、本発明の更なる実施例を説明する。
【００５３】
一実施例では、メッシュ・モデルの点を符号化する装置は、メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定する判定手段と、少なくとも１つの参照点を反復インスタンス毎に判定する判定手段と、反復インスタンスの参照点を１つ又は複数のクラスタにクラスタ化するクラスタ化手段と、ＫＤツリー符号化を使用して、クラスタ化された参照点を符号化する符号化手段とを備え、クラスタ毎に、別個のＫＤツリーが生成される。
【００５４】
一実施例では、クラスタ化手段は、メッシュ・モデル周りのバウンディング・ボックスを画定する画定手段と、バウンディング・ボックスをセルに分割する分割手段であって、セルが最小空間分解能単位である分割手段と、まだクラスタ化されておらず、反復インスタンスの１つ又は複数の参照点を含む第１のセルを選択する選択手段と、第１のセル内の１つ又は複数の参照点、若しくは第１のセルを含むクラスタを画定する画定手段とを備える。
【００５５】
一実施例では、装置は、１つ又は複数の更なるセルを判定する判定手段であって、更なるセルは、選択された第１のセルの近傍セル、又は反復的な近傍のセルであり、判定された更なるセルはそれぞれ、反復インスタンスの少なくとも１つの参照点を備える判定手段と、判定された１つ又は複数の近傍セルをクラスタに付加する付加手段とを更に備える。
一実施例では、クラスタ化手段は更に、各セルにおける参照点の数の昇順又は降順にセル全てをソートする編成手段を更に備え、第１のセル（すなわち、クラスタの初期セル）は、上述の順序に応じて選択される。
【００５６】
一実施例では、クラスタ化手段は、現在のクラスタの境界セル（各寸法の最小インデクス及び最大インデクスを備えたセルである）を判定する手段を備える。
【００５７】
一実施例では、符号化装置は、空間分解能を規定する手段を更に備え、セルは、規定された空間分解能に応じた、最小の空間分解能単位である。
【００５８】
一実施例では、符号化装置は、反復インスタンスの参照点の空間的均一性の尺度を判定する解析手段であって、空間的均一性の尺度は参照点が均一に分布している場合に高く、分布がより不規則である場合に低い解析手段と、空間的均一性を閾値と比較する比較器手段と、空間的均一性が閾値を下回る場合にのみ、クラスタ化が行われるよう制御する制御手段とを備える。
【００５９】
一実施例では、符号化されたメッシュ・モデルは複数の反復連結成分を備え、符号化されたメッシュ・モデルは、反復連結成分それぞれの少なくとも１つのインスタンスの符号化データ、反復連結成分の複数の反復の位置であって、ＫＤツリーとして符号化された位置、及び、メッシュ・モデル内の境界領域を含み、ＫＤツリーは領域を表す。
【００６０】
一実施例では、符号化されたメッシュ・モデルの境界領域のデータは、境界セルのインデクスを備える。
【００６１】
図６のｂ）に示す一実施例では、符号化されたメッシュ・モデルの点を復号化する方法は、反復連結成分のインスタンスのデータを抽出するステップ（Ｄ１）と、抽出されたデータを使用して連結成分のインスタンスを復号化するステップ（Ｄ２）と、クラスタ数を規定する第１のデータ（Ｎｕｍ＿Ｏｆ＿Ｃｌｕｓｔｅｒｓ）を抽出するステップ（Ｄ３）であって、第２のデータ（Ｎ）が空間分解能を規定し、第３のデータ（ＫＤ−Ｔ１、…、ＫＤ−Ｔ３）が反復連結成分の複数の反復の位置であり、第３のデータがＫＤツリーとして符号化されるステップと、第４のデータ（Ｉｎｄｅｘ＿Ｂｏｕｎｄａｒｙ＿Ｃｌｕｓｔｅｒ）を抽出するステップ（Ｄ４）と、第３のデータ及び第４のデータから反復連結成分の複数の反復の位置を判定するステップ（Ｄ５）とを含み、第３のデータは、第４のデータによって規定されるメッシュ・モデルの部分に施される。
【００６２】
復号化のための方法の一実施例では、第４のデータ（Ｉｎｄｅｘ＿Ｂｏｕｎｄａｒｙ＿Ｃｌｕｓｔｅｒ）はメッシュ・モデル内の２つのセルのインデクスを備え、セルは、第２のデータによって規定される空間分解能に応じた最小空間分解能単位である。
【００６３】
パターン位置データの場合、本発明によるクラスタ・ベースのＫＤツリー圧縮は、従来のＫＤツリー・ベースの圧縮と比較して、約５０％の記憶空間（Ｃｌｕｓ＿Ｃｏｍｐ／Ｃｏｏｒ＿Ｃｏｍｐ）を節減することが可能である。
【００６４】
表２では、＃Ｃは連結成分の数であり、＃Ｐは反復成分の数であり、Ｃｏｏｒ．（Ｋ）は、未処理インスタンス位置のサイズ（単位：Ｋバイト）であり、Ｃｏｏｒ＿Ｃｏｍｐ（Ｋ）は１つのＫＤツリーを使用した圧縮インスタンス位置のサイズであり、＃Ｃｌｕはクラスタの数であり、Ｃｌｕ＿Ｃｏｏｒ＿Ｃｏｍｐ（Ｋ）は、クラスタ化されたＫＤツリー・ベースの圧縮方法による圧縮インスタンス位置のサイズである。
【００６５】
【表２】
好ましい実施例に施された、本発明の新しい基本構成を示し、説明し、指摘してきたが、開示された装置の形式及び詳細、並びに、その動作において、上述の装置及び方法における種々の割愛、置換、及び変更を、本発明の趣旨から逸脱しない限り、当業者によって行い得る。本発明は反復連結成分のインスタンス位置に関して開示してきたが、本明細書及び特許請求の範囲記載の方法及び装置は基本的には、離散点の群の圧縮に関する何れかのシナリオに施し得るということを当業者は認識するであろう。同じ結果を達成するために実質的に同じやり方で実質的に同じ機能を行う構成要素の組合せは全て、本発明の範囲内にあることを明示的に意図している。上述の一実施例から別の実施例に要素を置き換えることも、完全に意図され、想定されている。
【００６６】
本発明は例として表しているに過ぎず、本発明の範囲から逸脱しない限り、詳細の修正を行うことが可能である。明細書に記載された特徴それぞれ、及び（請求項及び図面に記載されている場合には）請求項及び図面に記載された特徴それぞれは、独立して、又は何れかの適切な組み合わせで提供し得る。特徴は、適宜、ハードウェア、ソフトウェア、又はそれらの２つの組合せで実現し得る。請求項記載の参照符号は、例証のみの目的に過ぎず、請求項の範囲を限定する制限的な効果を有しない。
【特許請求の範囲】
【請求項１】
メッシュ・モデルの点を符号化する方法であって、
前記メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定し、少なくとも１つの参照点を反復インスタンス毎に判定するステップと、
前記反復インスタンスの前記参照点を１つ又は複数のクラスタにクラスタ化するステップと、
ＫＤツリー符号化を使用して、前記クラスタ化された参照点を符号化するステップと
を含み、クラスタ毎に別個のＫＤツリーが生成される、前記方法。
【請求項２】
請求項１記載の方法であって、前記クラスタ化するステップは、
前記メッシュ・モデル周りにバウンディング・ボックスを画定するステップと、
前記バンディング・ボックスをセルに分割するステップであって、セルが最小空間分解能単位であるステップと、
まだクラスタ化されておらず、反復インスタンスの１つ又は複数の参照点を含む第１のセルを選択するステップと、
前記第１のセルを含み、前記第１のセル内の前記１つ又は複数の参照点を含むクラスタを画定するステップと
を含む、前記方法。
【請求項３】
請求項２記載の方法であって、まだクラスタ化されておらず、Ｍ個の反復インスタンスの少なくともＭ個の参照点を含んでいる場合にのみ、前記第１のセルが選択されるに過ぎず、Ｍはユ―ザ定義可能なパラメータである、前記方法。
【請求項４】
請求項２又は３に記載の方法であって、
１つ又は複数の更なるセルを判定するステップであって、前記更なるセルは、前記選択された第１のセルの近傍セル、又は反復的に近傍のセルであり、前記判定された更なるセルそれぞれは反復インスタンスの少なくとも１つの参照点を含むステップと、
前記判定された１つ又は複数の近傍セルを前記クラスタに付加するステップと
を更に含む、前記方法。
【請求項５】
請求項２乃至４の何れか一項に記載の方法であって、
各セルにおける参照点の数の昇順又は降順でセル全てをソートするステップを更に含み、前記第１のセルは当該順に応じて選択される、前記方法。
【請求項６】
請求項１乃至５の何れか一項に記載の方法であって、前記クラスタ化するステップは、現在のクラスタの境界セルを判定するステップを含み、前記セルは、各寸法の最小インデクス及び最大インデクスを備えたセルである、前記方法。
【請求項７】
請求項１乃至６の何れか一項に記載の方法であって、
空間分解能を規定するステップを更に含み、セルは、規定された空間分解能に応じた最小空間分解能単位である、前記方法。
【請求項８】
請求項１乃至７の何れか一項に記載の方法であって、
前記反復インスタンスの参照点の空間的均一性の尺度を判定するステップであって、前記空間的均一性の尺度は、前記参照点が均一に分布している場合に高く、前記分布がより不規則である場合に低いステップと、
前記空間的均一性を閾値と比較するステップと、
前記空間的均一性が閾値未満である場合にのみ、前記クラスタ化を行うステップと
を更に含む、前記方法。
【請求項９】
請求項８記載の方法であって、前記空間的均一性が前記閾値未満である場合に、前記空間分解能を修正するステップと、
空間的均一性の尺度を判定するステップを反復するステップとを更に含む、前記方法。
【請求項１０】
メッシュ・モデルの点を符号化する装置であって、
前記メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定する手段、及び、少なくとも１つの参照点を反復インスタンス毎に判定する手段と、
前記反復インスタンスの前記参照点を１つ又は複数のクラスタにクラスタ化する手段と、
ＫＤツリー符号化を使用して前記クラスタ化された参照点を符号化する手段とを備え、
クラスタ毎に別個のＫＤツリーが生成される、前記装置。
【請求項１１】
請求項１０記載の装置であって、前記クラスタ化する手段は、
前記メッシュ・モデル周りのバウンディング・ボックスを画定する手段と、
前記バウンディング・ボックスをセルに分割する手段であって、セルが最小空間分解能単位である手段と、
まだクラスタ化されておらず、反復インスタンスの１つ又は複数の参照点を含む第１のセルを選択する手段と、
前記第１のセルを含み、又は、前記第１のセル内の前記１つ又は複数の参照点を含むクラスタを画定する手段と
を含む、前記装置。
【請求項１２】
請求項１０記載の装置であって、
更なる１つ又は複数のセルを判定する手段であって、
前記更なるセルは前記選択された第１のセルの近傍セル又は反復的に近傍のセルであり、前記判定された更なるセルそれぞれは反復インスタンスの少なくとも１つの参照点を含む手段と、
前記判定された近傍セルを前記クラスタに付加する手段とを備える、前記装置。
【請求項１３】
請求項１０乃至１２の何れか一項に記載の装置であって、前記クラスタ化する手段は、各セルにおける参照点の番号の昇順又は降順にセル全てをソートする手段を更に備え、前記第１のセルは当該順に応じて選択される、前記装置。
【請求項１４】
請求項１０乃至１３の何れか一項に記載の装置であって、
前記クラスタ化手段は、現在のクラスタの境界セルを判定する手段を備え、各寸法の最小インデクス及び最大インデクスを備えたセルである、前記装置。
【請求項１５】
請求項１０乃至１４の何れか一項に記載の装置であって、空間分解能を規定する手段を更に備え、セルは、前記規定された空間分解能に応じた、最小の空間分解能単位である、前記装置。
【請求項１６】
請求項１０乃至１５の何れか一項に記載の装置であって、
前記反復インスタンスの参照点の空間的均一性の尺度を判定する手段であって、前記空間的均一性の尺度は、前記参照点が均一に分布している場合、高く、当該分布がより不規則な場合、より低い手段と、
前記空間的均一性を閾値と比較する手段と、
前記空間的均一性が前記閾値未満である場合にのみ、前記クラスタ化を行う手段と
を備える、前記装置。
【請求項１７】
複数の反復連結成分を備えた符号化メッシュ・モデルであって、
前記符号化メッシュ・モデルは、少なくとも
各反復連結成分の１つのインスタンス、
前記反復連結成分の複数の反復の位置であって、前記位置はＫＤツリーとして符号化された位置、及び
前記メッシュ・モデル内の境界領域であって、前記ＫＤツリーが前記領域を表す境界領域
の符号化データを備える、前記符号化メッシュ・モデル。
【請求項１８】
請求項１７記載の符号化メッシュ・モデルであって、前記境界領域の前記データは、境界セルのインデクスを備える、前記符号化メッシュ・モデル。
【請求項１９】
符号化メッシュ・モデルの点を復号化する方法であって、
反復連結成分のインスタンスのデータを抽出するステップと、
前記抽出されたデータを使用して前記連結成分の前記インスタンスを復号化するステップと、
クラスタの数を規定する第１のデータを抽出するステップであって、第２のデータは空間分解能を規定し、第３のデータは前記反復連結成分の複数の反復の位置であり、前記第３のデータはＫＤツリーとして符号化されるステップと、
前記メッシュ・モデル内の部分を規定する第４のデータを抽出するステップと、
前記第３のデータ及び前記第４のデータから前記反復連結成分の前記複数の反復の前記位置を判定するステップと
を含み、前記第３のデータが前記第４のデータによって規定される前記メッシュ・モデルの前記部分に施される、前記方法。
【請求項２０】
請求項１９記載の方法であって、前記第４のデータは、前記メッシュ・モデル内の２つのセルのインデクスを備え、セルは、前記第２のデータによって規定される前記空間分解能に応じた最小空間分解能である、前記方法。
【請求項１】
メッシュ・モデルの点を符号化する方法であって、
前記メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定し、少なくとも１つの参照点を反復インスタンス毎に判定するステップと、
前記反復インスタンスの前記参照点を１つ又は複数のクラスタにクラスタ化するステップと、
ＫＤツリー符号化を使用して、前記クラスタ化された参照点を符号化するステップと
を含み、クラスタ毎に別個のＫＤツリーが生成される、前記方法。
【請求項２】
請求項１記載の方法であって、前記クラスタ化するステップは、
前記メッシュ・モデル周りにバウンディング・ボックスを画定するステップと、
前記バンディング・ボックスをセルに分割するステップであって、セルが最小空間分解能単位であるステップと、
まだクラスタ化されておらず、反復インスタンスの１つ又は複数の参照点を含む第１のセルを選択するステップと、
前記第１のセルを含み、前記第１のセル内の前記１つ又は複数の参照点を含むクラスタを画定するステップと
を含む、前記方法。
【請求項３】
請求項２記載の方法であって、まだクラスタ化されておらず、Ｍ個の反復インスタンスの少なくともＭ個の参照点を含んでいる場合にのみ、前記第１のセルが選択されるに過ぎず、Ｍはユ―ザ定義可能なパラメータである、前記方法。
【請求項４】
請求項２又は３に記載の方法であって、
１つ又は複数の更なるセルを判定するステップであって、前記更なるセルは、前記選択された第１のセルの近傍セル、又は反復的に近傍のセルであり、前記判定された更なるセルそれぞれは反復インスタンスの少なくとも１つの参照点を含むステップと、
前記判定された１つ又は複数の近傍セルを前記クラスタに付加するステップと
を更に含む、前記方法。
【請求項５】
請求項２乃至４の何れか一項に記載の方法であって、
各セルにおける参照点の数の昇順又は降順でセル全てをソートするステップを更に含み、前記第１のセルは当該順に応じて選択される、前記方法。
【請求項６】
請求項１乃至５の何れか一項に記載の方法であって、前記クラスタ化するステップは、現在のクラスタの境界セルを判定するステップを含み、前記セルは、各寸法の最小インデクス及び最大インデクスを備えたセルである、前記方法。
【請求項７】
請求項１乃至６の何れか一項に記載の方法であって、
空間分解能を規定するステップを更に含み、セルは、規定された空間分解能に応じた最小空間分解能単位である、前記方法。
【請求項８】
請求項１乃至７の何れか一項に記載の方法であって、
前記反復インスタンスの参照点の空間的均一性の尺度を判定するステップであって、前記空間的均一性の尺度は、前記参照点が均一に分布している場合に高く、前記分布がより不規則である場合に低いステップと、
前記空間的均一性を閾値と比較するステップと、
前記空間的均一性が閾値未満である場合にのみ、前記クラスタ化を行うステップと
を更に含む、前記方法。
【請求項９】
請求項８記載の方法であって、前記空間的均一性が前記閾値未満である場合に、前記空間分解能を修正するステップと、
空間的均一性の尺度を判定するステップを反復するステップとを更に含む、前記方法。
【請求項１０】
メッシュ・モデルの点を符号化する装置であって、
前記メッシュ・モデルが連結成分の反復インスタンスを含んでいると判定する手段、及び、少なくとも１つの参照点を反復インスタンス毎に判定する手段と、
前記反復インスタンスの前記参照点を１つ又は複数のクラスタにクラスタ化する手段と、
ＫＤツリー符号化を使用して前記クラスタ化された参照点を符号化する手段とを備え、
クラスタ毎に別個のＫＤツリーが生成される、前記装置。
【請求項１１】
請求項１０記載の装置であって、前記クラスタ化する手段は、
前記メッシュ・モデル周りのバウンディング・ボックスを画定する手段と、
前記バウンディング・ボックスをセルに分割する手段であって、セルが最小空間分解能単位である手段と、
まだクラスタ化されておらず、反復インスタンスの１つ又は複数の参照点を含む第１のセルを選択する手段と、
前記第１のセルを含み、又は、前記第１のセル内の前記１つ又は複数の参照点を含むクラスタを画定する手段と
を含む、前記装置。
【請求項１２】
請求項１０記載の装置であって、
更なる１つ又は複数のセルを判定する手段であって、
前記更なるセルは前記選択された第１のセルの近傍セル又は反復的に近傍のセルであり、前記判定された更なるセルそれぞれは反復インスタンスの少なくとも１つの参照点を含む手段と、
前記判定された近傍セルを前記クラスタに付加する手段とを備える、前記装置。
【請求項１３】
請求項１０乃至１２の何れか一項に記載の装置であって、前記クラスタ化する手段は、各セルにおける参照点の番号の昇順又は降順にセル全てをソートする手段を更に備え、前記第１のセルは当該順に応じて選択される、前記装置。
【請求項１４】
請求項１０乃至１３の何れか一項に記載の装置であって、
前記クラスタ化手段は、現在のクラスタの境界セルを判定する手段を備え、各寸法の最小インデクス及び最大インデクスを備えたセルである、前記装置。
【請求項１５】
請求項１０乃至１４の何れか一項に記載の装置であって、空間分解能を規定する手段を更に備え、セルは、前記規定された空間分解能に応じた、最小の空間分解能単位である、前記装置。
【請求項１６】
請求項１０乃至１５の何れか一項に記載の装置であって、
前記反復インスタンスの参照点の空間的均一性の尺度を判定する手段であって、前記空間的均一性の尺度は、前記参照点が均一に分布している場合、高く、当該分布がより不規則な場合、より低い手段と、
前記空間的均一性を閾値と比較する手段と、
前記空間的均一性が前記閾値未満である場合にのみ、前記クラスタ化を行う手段と
を備える、前記装置。
【請求項１７】
複数の反復連結成分を備えた符号化メッシュ・モデルであって、
前記符号化メッシュ・モデルは、少なくとも
各反復連結成分の１つのインスタンス、
前記反復連結成分の複数の反復の位置であって、前記位置はＫＤツリーとして符号化された位置、及び
前記メッシュ・モデル内の境界領域であって、前記ＫＤツリーが前記領域を表す境界領域
の符号化データを備える、前記符号化メッシュ・モデル。
【請求項１８】
請求項１７記載の符号化メッシュ・モデルであって、前記境界領域の前記データは、境界セルのインデクスを備える、前記符号化メッシュ・モデル。
【請求項１９】
符号化メッシュ・モデルの点を復号化する方法であって、
反復連結成分のインスタンスのデータを抽出するステップと、
前記抽出されたデータを使用して前記連結成分の前記インスタンスを復号化するステップと、
クラスタの数を規定する第１のデータを抽出するステップであって、第２のデータは空間分解能を規定し、第３のデータは前記反復連結成分の複数の反復の位置であり、前記第３のデータはＫＤツリーとして符号化されるステップと、
前記メッシュ・モデル内の部分を規定する第４のデータを抽出するステップと、
前記第３のデータ及び前記第４のデータから前記反復連結成分の前記複数の反復の前記位置を判定するステップと
を含み、前記第３のデータが前記第４のデータによって規定される前記メッシュ・モデルの前記部分に施される、前記方法。
【請求項２０】
請求項１９記載の方法であって、前記第４のデータは、前記メッシュ・モデル内の２つのセルのインデクスを備え、セルは、前記第２のデータによって規定される前記空間分解能に応じた最小空間分解能である、前記方法。
【図１】
【図２ａ）】
【図２ｂ）】
【図３】
【図４】
【図５】
【図６ａ）】
【図６ｂ）】
【図７】
【図２ａ）】
【図２ｂ）】
【図３】
【図４】
【図５】
【図６ａ）】
【図６ｂ）】
【図７】
【公表番号】特表２０１３−５０７７０１（Ｐ２０１３−５０７７０１Ａ）
【公表日】平成２５年３月４日（２０１３．３．４）
【国際特許分類】
【出願番号】特願２０１２−５３３４５０（Ｐ２０１２−５３３４５０）
【出願日】平成２１年１０月１５日（２００９．１０．１５）
【国際出願番号】ＰＣＴ／ＣＮ２００９／００１１４３
【国際公開番号】ＷＯ２０１１／０４４７１３
【国際公開日】平成２３年４月２１日（２０１１．４．２１）
【出願人】（５０１２６３８１０）トムソン ライセンシング (2,848)
【氏名又は名称原語表記】Ｔｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ
【住所又は居所原語表記】１−５， ｒｕｅ Ｊｅａｎｎｅ ｄ’Ａｒｃ， ９２１３０ ＩＳＳＹ ＬＥＳ ＭＯＵＬＩＮＥＡＵＸ， Ｆｒａｎｃｅ
【Ｆターム（参考）】
【公表日】平成２５年３月４日（２０１３．３．４）
【国際特許分類】
【出願日】平成２１年１０月１５日（２００９．１０．１５）
【国際出願番号】ＰＣＴ／ＣＮ２００９／００１１４３
【国際公開番号】ＷＯ２０１１／０４４７１３
【国際公開日】平成２３年４月２１日（２０１１．４．２１）
【出願人】（５０１２６３８１０）トムソン ライセンシング (2,848)
【氏名又は名称原語表記】Ｔｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ
【住所又は居所原語表記】１−５， ｒｕｅ Ｊｅａｎｎｅ ｄ’Ａｒｃ， ９２１３０ ＩＳＳＹ ＬＥＳ ＭＯＵＬＩＮＥＡＵＸ， Ｆｒａｎｃｅ
【Ｆターム（参考）】
[ Back to top ]