３Ｄメッシュ・モデルの法線をエンコードする方法、３Ｄメッシュ・モデルの法線をデコードする方法、エンコーダおよびデコーダ
3Dメッシュ・モデルの、法線成分としても知られる頂点配向をエンコードする方法が、法線成分の第一のクラスタリングの段階と、各第一クラスターについて、その要素の大半が属する球セクターを決定する段階と、法線成分をあらかじめ定義されたセクターにマッピングする段階と、あらかじめ定義されたセクターにおける法線成分を第二クラスターにクラスタリングし直す段階と、前記第二クラスターについての予測子を決定し、法線成分をその残差、その予測子への参照および前記ミラー・マッピング動作のどれが実行されたかを示すデータによってエンコードする段階とを含む。球セクターは、球をm個の等しい球セグメントに分割し、前記球セグメントのそれぞれをn個の等しいセクターに分割することによって得られる。セクター・マッピングのための第一のクラスタリングおよび予測符号化のための第二のクラスタリングの結果、改善された圧縮比が得られる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、3Dメッシュ・モデルの法線のエンコードおよびデコードに関する。具体的には、本発明はそのような法線をエンコードする方法およびデコードする方法、対応するエンコーダおよびデコーダならびにエンコードされた3Dモデルに関する。
【背景技術】
【０００２】
3Dメッシュ・モデルは通例、三角形から構成され、各三角形は関連付けられた位置、色および法線成分によって表現される。位置は、その三つの角または頂点の浮動小数点座標によって与えられる。各頂点には法線成分が関連付けられており、これも浮動小数点値である。法線成分は空間的な頂点配向を与える。そのような3Dメッシュ・モデルを圧縮する際、位置、色および法線成分のそれぞれは別個に圧縮される。[D95]1はそのような圧縮を記載している。[D95]では、単位法線の終点が載る法線球が八つの八分象限（octant）に分割され、各八分象限は六つの六分区（sextant）からなる。六分区をさらに細分して、法線は1/48の球上での法線の平均によって参照される。しかしながら、[D95]によって与えられるアプローチが好適なのは、モデル法線が球状に一様分布しているときのみである。3Dメッシュ・モデルの法線が通例は均一に分布していないという観察に基づき、[DYH02]2は改善された圧縮のために法線のk平均クラスタリングを提案している。しかしながら、このアプローチでは、クラスターの数kは固定である。さらに、kを前もって決めるのは常に困難な課題である。さらに、[D95]において得られる法線エンコード・パラメータ化のような利点が[DYK02]ではもはや得られない。
【０００３】
複雑な3Dメッシュ・モデルは、連結成分（connected component）と呼ばれるいくつかの成分から構成される。連結成分は、SBM013において次のように定義されている。二つのポリゴンは、辺を共有する場合に隣り合うポリゴンである。ポリゴンpiとpjの間には、隣り合うポリゴンのシーケンスがあれば、経路が存在する。メッシュ・モデルOの部分集合Ocは、Oc内の任意の二つのポリゴンの間に経路が存在する場合に、連結成分と呼ばれる。そのようなメッシュ・モデルは多連結モデルと呼ばれる。さらに、多連結モデルについて、効果的な圧縮方式は反復する特徴を発見し、次いで変換データを圧縮しうる。配向は変換データの重要な部分の一つである。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
多くの3Dモデルにおいて、法線の分布は不均一である。したがって、法線は可変数のクラスターにソートされるべきである。法線が可変数のクラスターに分布している場合を含む現実的なモデルのための効率的な法線圧縮方法が望ましい。
【課題を解決するための手段】
【０００５】
本発明は、大規模3Dエンジニアリング・モデルの連結成分の配向を圧縮する効率的な方法を提供する。我々の圧縮方法は、マッピング動作とクラスタリング、特にk平均クラスタリングのパワーを組み合わせる。
【０００６】
ある側面では、3Dメッシュ・モデルの、法線成分としても知られる頂点配向をエンコードする方法は、法線成分の第一のクラスタリングの段階と、各第一クラスターについて、その要素の大半が属する球セクターを決定する段階と、法線成分をあらかじめ定義されたセクターにマッピングする段階と、あらかじめ定義されたセクターにおける法線成分を第二クラスターにクラスタリングし直す段階と、前記第二クラスターについての予測子を決定し、法線成分をその残差、その予測子への参照および前記ミラー・マッピング動作のどれが実行されたかを示すデータによってエンコードする段階とを含む。球セクターは、球をm個の等しい球セグメントに分割し、前記球セグメントのそれぞれをn個の等しいセクターに分割することによって得られる。セクター・マッピングのための第一のクラスタリングおよび予測符号化のための第二のクラスタリングの結果、改善された圧縮比が得られる。
【０００７】
原理的には、本発明のある側面は、法線のエンコードにおいて、法線の第一のクラスタリングが実行され、次いでクラスターが単位球のあらかじめ定義されたセクター中にマッピングされ、その結果に対して第二のクラスタリングが実行されるというものである。第一のクラスタリングの目的はマッピング動作を最適化することであり、第二のクラスタリングの目的は、法線の予測符号化を最適化することである。
【０００８】
本発明のある側面によれば、3Dメッシュ・モデルの法線成分をエンコードする方法であって、法線成分は単位球上でのその位置によって定義可能である、方法は、3Dメッシュ・モデルの法線成分をクラスタリングする段階であって、一つまたは複数の第一クラスターが得られ、各法線成分は前記第一クラスターの少なくとも一つのクラスターの要素である、段階と、法線成分の前記第一クラスターのそれぞれについて、その要素の大半が属する球セクターを決定する段階であって、球セクターは、球をm個の等しい球セグメントに分割し、前記球セグメントのそれぞれをn個の等しいセクターに分割することによって得られる、段階と、前記決定する段階によれば前記セクターのあらかじめ定義されたものにない法線成分を前記あらかじめ定義されたセクター中にマッピングする段階と、法線成分をクラスタリングし直す段階であって、一つまたは複数の第二クラスターが得られ、各法線成分は前記第二クラスターの少なくとも一つのクラスターの要素である、段階と、法線成分を量子化する段階と、前記第二クラスターのそれぞれについて、代表予測子要素を決定する段階と、前記法線成分のための残差を決定する段階であって、残差とは法線成分とその対応する予測子要素との間の差である、段階と、法線成分をその残差、その予測子要素への参照および前記ミラー・マッピング動作のうちのどれが実行されたかを示すデータによってエンコードする段階とを含む。
【０００９】
一般に、マッピングはint(log2(m)＋log2(n)＋1)個までのミラー・マッピング動作を含む。
【００１０】
本発明のある側面によれば、エンコードされたビットストリームから3Dメッシュ・モデルの法線成分をデコードする方法であって、法線成分は単位球上のその位置によって定義可能であり、エンコードされたビットストリームから予測子である法線成分のデータを抽出し、該予測子についての識別子を抽出する段階と、エンコードされたビットストリームからエンコードされた法線成分に関係するデータを抽出する段階であって、該データは残差データ、予測子識別データおよびマッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがそのエンコードされた法線成分について実行されるべきか否かを示す、段階と、法線成分をデコードする段階であって、前記残差データが前記予測子識別データに従って前記予測子に加えられ、結果として得られる法線成分が前記あらかじめ定義されたミラー・マッピング動作に従ってマッピングされる、段階とを含む、方法。
【００１１】
デコードする方法のある実施形態では、前記マッピング・データは、法線成分のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを含む。クラスター識別データは法線成分をクラスターに関連付ける。クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている法線要素のために実行されるべきか否かを示す。
【００１２】
本発明のある側面によれば、3Dメッシュ・モデルの法線成分をエンコードする装置であって、法線成分は単位球上でのその位置によって定義可能である、装置は、3Dメッシュ・モデルの法線成分をクラスタリングする第一のクラスタリング手段であって、一つまたは複数の第一クラスターが得られ、各法線成分は前記第一クラスターの少なくとも一つのクラスターの要素である、手段と、法線成分の前記第一クラスターのそれぞれについて、その要素の大半が属する球セクターを決定する決定手段であって、球セクターは、球をm個の等しい球セグメントに分割し、前記球セグメントのそれぞれをn個の等しいセクターに分割することによって得られる、手段と、前記決定によれば前記セクターのあらかじめ定義されたものにない法線成分を前記あらかじめ定義されたセクター中にマッピングするマッピング手段と、法線成分をクラスタリングし直す第二のクラスタリング手段であって、一つまたは複数の第二クラスターが得られ、各法線成分は前記第二クラスターの少なくとも一つのクラスターの要素である、手段と、法線成分を量子化する量子化器と、前記第二クラスターのそれぞれについて、代表予測子要素を決定し、前記法線成分のための残差を決定する予測符号化器であって、残差とは法線成分とその対応する予測子要素との間の差である、予測符号化器と、法線成分をその残差、その予測子要素への参照および前記ミラー・マッピング動作のうちのどれが実行されたかを示すデータによってエンコードするエンコーダとを有する装置。さらに、その後エントロピー符号化器が使われてもよい。
【００１３】
本発明のある側面によれば、エンコードされたビットストリームから3Dメッシュ・モデルの法線成分をデコードする装置であって、法線成分は単位球上のその位置によって定義可能であり、エンコードされたビットストリームから予測子である法線成分のデータを抽出する第一の抽出手段と、該予測子についての識別子を抽出する第二の抽出手段と、エンコードされたビットストリームからエンコードされた法線成分に関係するデータを抽出する第三の抽出手段であって、該データは残差データ、予測子識別データおよびマッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがそのエンコードされた法線成分について実行されるべきか否かを示す、手段と、法線成分をデコードするデコード手段であって、前記残差データが前記予測子識別データに従って前記予測子に加えられ、結果として得られる法線成分が前記あらかじめ定義されたミラー・マッピング動作に従ってマッピングされる、手段とを有する、装置。
【００１４】
デコードする装置のある実施形態では、当該装置は、前記マッピング・データから、法線成分のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを抽出する手段を有する。クラスター識別データは法線成分をクラスターに関連付ける。クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている法線要素のために実行されるべきか否かを示す。この実施形態では、デコードする装置はさらに、あらかじめ定義されたミラー・マッピング動作に従って法線成分をマッピングするマッピング手段を有する。
【００１５】
本発明のある側面によれば、データ構造は、3Dメッシュ・モデルの頂点データおよびエンコードされた頂点配向データを含む。ここで、エンコードされた頂点配向データは少なくとも予測子、該予測子に関連付けられた識別子およびエンコードされた頂点配向に関係するデータを含み、エンコードされた頂点配向に関係するデータは残差データ、予測子識別データおよびマッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがエンコードされた頂点配向をデコードするために実行されるべきか否かを示す。
【００１６】
データ構造のある実施形態では、前記マッピング・データは頂点配向のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを含む。クラスター識別データは頂点配向をクラスターに関連付ける。クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている頂点配向のために実行されるべきか否かを示す。
本発明の有利な実施形態は、従属請求項、以下の記述および図面において開示される。
【図面の簡単な説明】
【００１７】
本発明の例示的な実施形態について、付属の図面を参照しつつ述べる。
【図１】単位球のセグメント分割を示す図である。
【図２】円筒である3Dメッシュ・モデルの配向軸を示す図である。
【図３】例示的な3Dメッシュ・モデルの配向軸の分布を単位球上に示す図である。
【図４】クラスタリングおよびマッピング後の、単位球上の配向軸の分布を示す図である。
【図５】第一のクラスタリング、マッピングおよび再クラスリング後のクラスター代表を示す図である。
【図６】（ａ）マッピング前および（ｂ）マッピング後の、配向と平均配向の間の最大誤差を示す図である。
【図７】エンコードのブロック図である。
【図８】デコードのブロック図である。
【図９】単位球についての代替的なセグメント分割方法を示す図である。
【図１０】枝付き燭台照明の例示的な3Dモデル、その連結成分の第一の配向軸の分布およびマッピング後の第一の配向軸の分布を示す図である。
【発明を実施するための形態】
【００１８】
図１は、その上に単位法線ベクトルが載る単位球のセクターを示している。球セクターは、球をm個の等しい球セグメントS1に分割し、前記球セグメントのそれぞれをn個の等しいセクター000,…,101に分割することによって得ることができる。簡単のため、球の球セグメントへの分割は三つのデカルト座標の軸、X、YおよびZ軸に沿ってできる。この結果、23＝8個のセグメントが生じる。他の分割方法、たとえば図９に似たものも可能である。m個のセクターとn個のセグメントの間のマッピングはint(log2(m)＋log2(n)＋1)個までのミラー・マッピング動作を含むことができる。たとえば、八個のセグメントS1および六個のセクター001,…,101については、セグメント間の三通りのマッピング動作が生じ、法線の大半（ほぼ全部）は単一のあらかじめ定義されたセグメント中にマッピングされ、前記あらかじめ定義されたセグメント内のさらに三通りのマッピング動作が生じ、法線の大半（ほぼ全部）は単一のあらかじめ定義されたセクター000中にマッピングされる。
【００１９】
好ましくは、法線のマッピングは一対一ではなく、法線はマッピングの前に第一のクラスタリング段階においてクラスタリングされる。このクラスタリング段階はk平均クラスタリングを使ってもよい。その目的は、マッピングを単純化することである。あるクラスターのすべての法線に対して同じマッピングが実行されるのである。異なるクラスターは（必須ではないが）異なるマッピングを使ってもよい。これは、利用可能なマッピングの異なる組み合わせを意味する。
【００２０】
マッピング後にさらなるクラスタリングを実行することが有利である。通例、マッピング後には、法線はより近くに密集しているからである。したがって、通例新しい、より大きなクラスターが生じる。この第二のクラスタリングは本稿では再クラスタリングとも呼ばれる。前の、第一のクラスタリングは、単にマッピングのために使われていた。再クラスタリング後、（クラスターにおいて代表を見出す既知の諸方法を使って）代表法線が決定され、諸法線はそのクラスター（すなわち、第二クラスター）の代表に対してエンコードされる。そのため、代表は予測子である。法線をエンコードする際、各法線は、その代表予測子、その予測誤差（残差）およびそのマッピングについての情報をもつ必要がある。代表予測子および残差から、法線は再構成されることができ、マッピング情報から、そのもとの位置が決定できる。マッピング情報は、第一のクラスタリングのクラスター識別子と、当該クラスターのすべての法線についてのクラスター・マッピング情報とを使ってエンコードされることができる。これは、マッピング情報がエンコードされ、伝送され、デコードされる必要があるのが、すべてのクラスター要素について一度だけであるという利点をもつ。
【００２１】
本発明の開示は、マッピング動作および適応k平均クラスタリング方法の力を組み合わせることのできる、配向を圧縮する効率的な方法を提案する。我々のアルゴリズムは、マッピング動作を使うかどうかを適応的に決定できる。第一に、すべての配向が、非常に効率的な適応k平均クラスタリング法を使ってクラスタリングされる。第二に、それらのクラスターがマッピングされる必要があるかどうかが判断される。異なる複数の六分区画に分布するデータ点をもつクラスターについては、我々はマッピング動作を実行する。マッピング動作は配向軸を、ラベル000をもつ1/48球ラベルにマッピングする。マッピング後は、すべてのデータが同じ六分区画にマッピングされているため、それらのクラスターの分散（variance）が減らされることができ、我々は、圧縮比をさらに改善するためにそれらをより少数のビットを用いて量子化できる。このことは図５および図６に示されている。次いで、「000」の1/48球部分およびそのすべての隣接1/48球部分にはいるすべての配向軸が、適応k平均クラスタリング方法を使って再クラスタリングされる。いまだに他の1/48球部分にはいる配向軸については、再クラスタリングされる必要はない。
【００２２】
図５は、マッピング前の第一クラスターの配向と平均配向との間の最大誤差５ｖを示している。図６は、マッピングおよび再クラスタリング後の第一クラスターの配向と平均配向との間の最大誤差６ｖを示している。見て取れるように、マッピングおよび再クラスタリングの前よりも、最大誤差はずっと小さくなっている。
【００２３】
モデルの配向は二つの軸によって効率的に表現されることができる。第一の軸は二つの自由度をもち、第二の軸は一つの自由度しかもたない。我々のアプローチは、第二の軸を圧縮するためにも使われることができる。違いは、第二の軸は円上に分布するということだけである。
【００２４】
配向軸は、それがはいる（第二）クラスターの代表によって予測される。予測誤差または残差が量子化される。
【００２５】
マッピング配向のため、図４に示すように、法線のクラスターの分散は大幅に小さくできる。
【００２６】
エンコーダおよびデコーダのブロック図は図７および図８に示されている。
【００２７】
「適応k平均クラスタリング」ブロック５２は次のように機能する。
【００２８】
初期化：n＝0
（１）kを小さな数に設定する。たとえば、k＝4。
（２）データ・セットをk平均クラスタリングによって分類する。
（３）n＝0;
（４）各クラスターについて
if（クラスターの分散がαより大きい） n++;
（５）if（n＝0） END
（６）αより大きな分散をもつ各クラスターについて、
該クラスターを2平均クラスタリング手順によって二つに分離する。
（７）Goto（３）。
【００２９】
ここで、αは閾値である。これは固定でもいいし、ユーザー定義されてもよい。
【００３０】
判断ブロック５３は、適応k平均クラスタリング・ブロック５２後に結果として得られる各クラスターを検査する。セクター・マッピング・ブロック５４では、異なる複数の「1/48球」部分にはいる法線を含むクラスターは「000」の1/48球（これが今の例ではあらかじめ定義されたターゲット・セクターである）にマッピングされる。
【００３１】
ある実施形態では、圧縮された配向軸情報のビットストリームは二つの部分を含む：
いくつかのビットはクラスターの数を示す。
・各クラスターについて：
・その代表を示すいくつかの浮動小数点値
・各配向軸の残差を量子化するために使われるビット数を示すいくつかのビット
・マッピング動作を用いて圧縮された配向軸の数を示すいくつかのビット
・マッピングされた各配向軸について：
・マッピング手順を示す6ビット
・それが属するクラスターのIDを示すいくつかのビット
・量子化された残差を示すいくつかのビット
・マッピングなしに圧縮された配向軸の数を示すいくつかのビット
・各配向軸について
・それが属するクラスターのIDを示すいくつかのビット
・量子化された残差を示すいくつかのビット。
【００３２】
ある実施形態では、異なるクラスターは通例異なる分散をもつので、圧縮された配向軸の数がエンコード／伝送される。分散は異なるビット数によって量子化されることができる。よって、この実施形態では、各法線成分の残差を量子化するのに使われているビット数を示すことにする。また、この実施形態では、マッピングされた各法線成分について「マッピングなしで圧縮された配向軸の数」を示すいくつかのビットが含められる。これは、この場合、マッピングありおよびマッピングなしで圧縮された配向軸の数を知る必要があるからである。理由は主として、圧縮解除のために、軸のためのスペースを割り当てることができるよう、圧縮された軸の数を知る必要があるということである。
【００３３】
ある実施形態では、3Dメッシュ・モデルの法線成分をエンコードする方法は、
3Dメッシュ・モデルの法線成分をクラスタリングする段階であって、一つまたは複数の第一クラスターが得られ、各法線成分は前記第一クラスターのうちの少なくとも一つのクラスターの要素である、段階と、
法線成分の前記第一クラスターのそれぞれについて、その要素の大半が属する球セクターを決定する段階であって、球セクターは、球をm個の等しい球セグメントに分割し、前記球セグメントのそれぞれをn個の等しいセクターに分割することによって得られる、段階と、
前記決定する段階によれば前記セクターのあらかじめ定義されたものにない法線成分を前記あらかじめ定義されたセクター中にマッピングする段階であって、前記マッピングはint(log2(m)＋log2(n)＋1)個までのミラー・マッピング動作を含む、段階と、
法線成分を再クラスタリングする段階であって、一つまたは複数の第二クラスターが得られ、各法線成分は前記第二クラスターのうちの少なくとも一つのクラスターの要素である、段階と、
法線成分を量子化する段階と、
前記第二クラスターのそれぞれについて、代表予測子要素を決定する段階と、
前記法線成分のための残差を決定する段階であって、残差とは法線成分とその対応する予測子要素との間の差である、段階と、
法線成分をその残差、その予測子要素への参照および前記ミラー・マッピング動作のうちのどれが実行されたかを示すデータによってエンコードする段階とを含む。
【００３４】
ある実施形態では、第一および／または第二のクラスタリング動作は適応k平均クラスタリングを使う。
【００３５】
ある実施形態では、球セグメントの数はm＝8であり、各セグメント内のセクターの数はn＝6である。ある実施形態では、前記球セグメントは球面三角形である。
【００３６】
ある実施形態では、本エンコード方法はさらに、前記マッピング後に、3Dメッシュ・モデルを回転させ、マッピングされた第一クラスターのより多くの要素が前記あらかじめ定義されたセクターにはいるようにする段階を含む。
【００３７】
ある実施形態では、第二クラスターの前記代表予測子要素は、前記クラスターの実際の要素である前記法線成分の一つである。別の実施形態では、それは仮想的な（存在しない）予測子要素である。
【００３８】
ある実施形態では、前記ミラー・マッピング動作のうちのどれが実行されたかを示す前記データは、その法線成分がどの第一クラスターに属するかを同定するデータと、その第一クラスターについて前記ミラー・マッピング動作のうちのどれが実行されたかを示すマッピング指標データとを含む。
【００３９】
ある実施形態では、前記ミラー・マッピング動作のうちのどれが実行されたかを示す前記データは、球のm個の等しい球セグメントへの分割および前記球セグメントのそれぞれのn個の等しいセクターへの分割を定義するデータを含む。
【００４０】
ある実施形態では、エンコードされたビットストリームから3Dメッシュ・モデルの法線成分をデコードする方法は、
エンコードされたビットストリームから予測子である法線成分のデータを抽出し、該予測子についての識別子を抽出する段階と、
エンコードされたビットストリームからエンコードされた法線成分に関係するデータを抽出する段階であって、該データは残差データ、予測子識別データおよびマッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがそのエンコードされた法線成分について実行されるべきか否かを示す、段階と、
法線成分をデコードする段階であって、前記残差データが前記予測子識別データに従って前記予測子に加えられ、結果として得られる法線成分が前記あらかじめ定義されたミラー・マッピング動作に従ってマッピングされる、段階とを含む。
【００４１】
デコードする方法のある実施形態では、前記マッピング・データは、法線成分のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを含む。クラスター識別データは法線成分をクラスターに関連付ける。クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている法線要素のために実行されるべきか否かを示す。
【００４２】
ある実施形態では、本デコード方法はさらに、ビットストリームからミラー動作データを抽出する段階を含む。ここで、前記あらかじめ決定されたミラー動作は前記ミラー動作データによって定義される。
【００４３】
ある実施形態では、3Dメッシュ・モデルの法線成分をエンコードする装置は図７に示される機能ブロックに対応するモジュールを有する。
【００４４】
ある実施形態では、3Dメッシュ・モデルの法線成分をデコードする装置は図８に示される機能ブロックに対応するモジュールを有する。
【００４５】
ある実施形態では、データ構造は、3Dメッシュ・モデルの頂点データおよびエンコードされた頂点配向データを含む。ここで、エンコードされた頂点配向データは少なくとも予測子、該予測子に関連付けられた識別子およびエンコードされた頂点配向に関係するデータを含み、エンコードされた頂点配向に関係するデータは、
残差データ、予測子識別データおよびマッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがエンコードされた頂点配向をデコードするために実行されるべきか否かを示す。
【００４６】
データ構造のある実施形態では、前記マッピング・データは頂点配向のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを含む。クラスター識別データは頂点配向をクラスターに関連付ける。クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている頂点配向のために実行されるべきか否かを示す。
【００４７】
本発明は、原理的には、あらゆる現実的な3Dメッシュ・モデルにとって有利である。本発明は、法線が均一に分布していない3Dメッシュ・モデルにとって特に有利である。3Dメッシュ・モデルがより多くの頂点をもつほど（つまり、モデルがより大きいほど）、本発明はより効果的である。また、モデルが法線の第一クラスターをより多くもつほど、マッピング後に結果として得られる第二クラスターがより大きくなるので、本発明はより効果的である。
【００４８】
図２は、例示的に、円筒形の3Dメッシュ・モデルの配向軸を示している。見て取れるように、法線はXY平面のまわりにはあらゆる方向に分布しているが、XY平面内では二つの方向、すなわち上下のみに分布している。このように、少なくともXY平面の法線は簡単にクラスタリングでき、そのエンコードにおいてビットを節約できる。ある実施形態では、法線についての開示されるエンコード方法は、3Dメッシュ・モデルのすべてではなく一部の法線のみに使われる。
【００４９】
図３は、もう一つの例示的な3Dメッシュ・モデルの配向軸の位置を示している。このモデル形状によれば、法線は単位球３１上のグループ３１ａ〜３１ｄに位置される。各グループはクラスタリングされることができ、各クラスターは、すでにターゲット・セグメントまたはセクター内にあるのでない限り、あらかじめ定義されたターゲット・セグメントおよびセクターにマッピングされる。クラスターがすでにターゲット・セグメント内にある場合、セクター・マッピングのみを実行するので十分である。それでも、各マッピング段階が実行される必要があるか否かをエンコード／デコードする必要がある。たとえばエンコードおよびマッピング情報。
【００５０】
図４は、クラスタリングおよびマッピング後の単位球上での配向軸の分布を示している。見て取れるように、図３のクラスターのうちの二つ３１ａ、３１ｂが同じ領域にマッピングされている。したがって、再クラスタリング段階において新しいクラスター４１ａｂが生成される。この新しいクラスター４１ａｂのすべての要素は、この新しいクラスターについての予測子のはたらきをするクラスター代表４１ａｂｒから予測できる。
【００５１】
図１０は、多数の円筒状の連結成分を有する枝付き燭台照明の例示的な3Dモデルを示している。各連結成分は図２のモデルのような法線分布をもつ。図１０のｂ）は、モデルの第一の配向軸の分布を示す。多くの配向軸が円上に載っているので、連結成分の配向軸が優勢であることが見て取れる。図１０のｃ）は、マッピング後の第一の配向軸の分布を示している。見て取れるように、主として、非常に密な二つのクラスターだけが残っており、よって予測を使って有利にエンコードできる。
【００５２】
本発明は、（完全な3Dモデルの単なる部分である）連結成分の配向軸／法線ならびに完全な3Dモデルの配向軸／法線の圧縮に関するいかなるシナリオにも適用できる。
【００５３】
当業者には明白であろうが、図１に示したもの以外の他の型の単位球セグメンテーションが構築されてもよいことを注意しておく。そのすべては本発明の精神および範囲内と考えられる。図９は、いくつかの代替的な可能性の一つを示しており、８つのセクターのそれぞれがいくつかのスライス７１ｎ、７１ｓに分離されている。
【００５４】
本発明の好ましい実施形態に適用される本発明の基本的な新たな特徴を示し、説明し、指摘してきたが、本発明の精神から外れることなく、開示される装置の形および詳細においてまたその動作において、記載される装置および方法においてさまざまな省略および代替および変更が当業者によってなされてもよいことは理解されるであろう。さらに、すべての実施形態は、明白に互いに相反するのでない限り、自由に組み合わせることができる。同じ結果を達成するために実質的に同じ仕方で実質的に同じ機能を実行する要素のあらゆる組み合わせは本発明の範囲内であることが明白に意図されている。記載されるある実施形態から別の実施形態への要素の転用も完全に意図されており、考えられている。
【００５５】
本発明は純粋に例として記載されてきたのであり、本発明の範囲から外れることなく細部の修正ができることは理解されるであろう。
【００５６】
本明細書および適切な場合には請求項および図面において開示される各特徴は、独立して、または任意の適切な組み合わせにおいて設けられてもよい。諸特徴は、適切な場合には、ハードウェア、ソフトウェアまたは両者の組み合わせとして実装されてもよい。請求項に参照符号が現れたとしても、単に例解のためであって、特許請求の範囲を限定する効果はもたないものとする。
【技術分野】
【０００１】
本発明は、3Dメッシュ・モデルの法線のエンコードおよびデコードに関する。具体的には、本発明はそのような法線をエンコードする方法およびデコードする方法、対応するエンコーダおよびデコーダならびにエンコードされた3Dモデルに関する。
【背景技術】
【０００２】
3Dメッシュ・モデルは通例、三角形から構成され、各三角形は関連付けられた位置、色および法線成分によって表現される。位置は、その三つの角または頂点の浮動小数点座標によって与えられる。各頂点には法線成分が関連付けられており、これも浮動小数点値である。法線成分は空間的な頂点配向を与える。そのような3Dメッシュ・モデルを圧縮する際、位置、色および法線成分のそれぞれは別個に圧縮される。[D95]1はそのような圧縮を記載している。[D95]では、単位法線の終点が載る法線球が八つの八分象限（octant）に分割され、各八分象限は六つの六分区（sextant）からなる。六分区をさらに細分して、法線は1/48の球上での法線の平均によって参照される。しかしながら、[D95]によって与えられるアプローチが好適なのは、モデル法線が球状に一様分布しているときのみである。3Dメッシュ・モデルの法線が通例は均一に分布していないという観察に基づき、[DYH02]2は改善された圧縮のために法線のk平均クラスタリングを提案している。しかしながら、このアプローチでは、クラスターの数kは固定である。さらに、kを前もって決めるのは常に困難な課題である。さらに、[D95]において得られる法線エンコード・パラメータ化のような利点が[DYK02]ではもはや得られない。
【０００３】
複雑な3Dメッシュ・モデルは、連結成分（connected component）と呼ばれるいくつかの成分から構成される。連結成分は、SBM013において次のように定義されている。二つのポリゴンは、辺を共有する場合に隣り合うポリゴンである。ポリゴンpiとpjの間には、隣り合うポリゴンのシーケンスがあれば、経路が存在する。メッシュ・モデルOの部分集合Ocは、Oc内の任意の二つのポリゴンの間に経路が存在する場合に、連結成分と呼ばれる。そのようなメッシュ・モデルは多連結モデルと呼ばれる。さらに、多連結モデルについて、効果的な圧縮方式は反復する特徴を発見し、次いで変換データを圧縮しうる。配向は変換データの重要な部分の一つである。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
多くの3Dモデルにおいて、法線の分布は不均一である。したがって、法線は可変数のクラスターにソートされるべきである。法線が可変数のクラスターに分布している場合を含む現実的なモデルのための効率的な法線圧縮方法が望ましい。
【課題を解決するための手段】
【０００５】
本発明は、大規模3Dエンジニアリング・モデルの連結成分の配向を圧縮する効率的な方法を提供する。我々の圧縮方法は、マッピング動作とクラスタリング、特にk平均クラスタリングのパワーを組み合わせる。
【０００６】
ある側面では、3Dメッシュ・モデルの、法線成分としても知られる頂点配向をエンコードする方法は、法線成分の第一のクラスタリングの段階と、各第一クラスターについて、その要素の大半が属する球セクターを決定する段階と、法線成分をあらかじめ定義されたセクターにマッピングする段階と、あらかじめ定義されたセクターにおける法線成分を第二クラスターにクラスタリングし直す段階と、前記第二クラスターについての予測子を決定し、法線成分をその残差、その予測子への参照および前記ミラー・マッピング動作のどれが実行されたかを示すデータによってエンコードする段階とを含む。球セクターは、球をm個の等しい球セグメントに分割し、前記球セグメントのそれぞれをn個の等しいセクターに分割することによって得られる。セクター・マッピングのための第一のクラスタリングおよび予測符号化のための第二のクラスタリングの結果、改善された圧縮比が得られる。
【０００７】
原理的には、本発明のある側面は、法線のエンコードにおいて、法線の第一のクラスタリングが実行され、次いでクラスターが単位球のあらかじめ定義されたセクター中にマッピングされ、その結果に対して第二のクラスタリングが実行されるというものである。第一のクラスタリングの目的はマッピング動作を最適化することであり、第二のクラスタリングの目的は、法線の予測符号化を最適化することである。
【０００８】
本発明のある側面によれば、3Dメッシュ・モデルの法線成分をエンコードする方法であって、法線成分は単位球上でのその位置によって定義可能である、方法は、3Dメッシュ・モデルの法線成分をクラスタリングする段階であって、一つまたは複数の第一クラスターが得られ、各法線成分は前記第一クラスターの少なくとも一つのクラスターの要素である、段階と、法線成分の前記第一クラスターのそれぞれについて、その要素の大半が属する球セクターを決定する段階であって、球セクターは、球をm個の等しい球セグメントに分割し、前記球セグメントのそれぞれをn個の等しいセクターに分割することによって得られる、段階と、前記決定する段階によれば前記セクターのあらかじめ定義されたものにない法線成分を前記あらかじめ定義されたセクター中にマッピングする段階と、法線成分をクラスタリングし直す段階であって、一つまたは複数の第二クラスターが得られ、各法線成分は前記第二クラスターの少なくとも一つのクラスターの要素である、段階と、法線成分を量子化する段階と、前記第二クラスターのそれぞれについて、代表予測子要素を決定する段階と、前記法線成分のための残差を決定する段階であって、残差とは法線成分とその対応する予測子要素との間の差である、段階と、法線成分をその残差、その予測子要素への参照および前記ミラー・マッピング動作のうちのどれが実行されたかを示すデータによってエンコードする段階とを含む。
【０００９】
一般に、マッピングはint(log2(m)＋log2(n)＋1)個までのミラー・マッピング動作を含む。
【００１０】
本発明のある側面によれば、エンコードされたビットストリームから3Dメッシュ・モデルの法線成分をデコードする方法であって、法線成分は単位球上のその位置によって定義可能であり、エンコードされたビットストリームから予測子である法線成分のデータを抽出し、該予測子についての識別子を抽出する段階と、エンコードされたビットストリームからエンコードされた法線成分に関係するデータを抽出する段階であって、該データは残差データ、予測子識別データおよびマッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがそのエンコードされた法線成分について実行されるべきか否かを示す、段階と、法線成分をデコードする段階であって、前記残差データが前記予測子識別データに従って前記予測子に加えられ、結果として得られる法線成分が前記あらかじめ定義されたミラー・マッピング動作に従ってマッピングされる、段階とを含む、方法。
【００１１】
デコードする方法のある実施形態では、前記マッピング・データは、法線成分のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを含む。クラスター識別データは法線成分をクラスターに関連付ける。クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている法線要素のために実行されるべきか否かを示す。
【００１２】
本発明のある側面によれば、3Dメッシュ・モデルの法線成分をエンコードする装置であって、法線成分は単位球上でのその位置によって定義可能である、装置は、3Dメッシュ・モデルの法線成分をクラスタリングする第一のクラスタリング手段であって、一つまたは複数の第一クラスターが得られ、各法線成分は前記第一クラスターの少なくとも一つのクラスターの要素である、手段と、法線成分の前記第一クラスターのそれぞれについて、その要素の大半が属する球セクターを決定する決定手段であって、球セクターは、球をm個の等しい球セグメントに分割し、前記球セグメントのそれぞれをn個の等しいセクターに分割することによって得られる、手段と、前記決定によれば前記セクターのあらかじめ定義されたものにない法線成分を前記あらかじめ定義されたセクター中にマッピングするマッピング手段と、法線成分をクラスタリングし直す第二のクラスタリング手段であって、一つまたは複数の第二クラスターが得られ、各法線成分は前記第二クラスターの少なくとも一つのクラスターの要素である、手段と、法線成分を量子化する量子化器と、前記第二クラスターのそれぞれについて、代表予測子要素を決定し、前記法線成分のための残差を決定する予測符号化器であって、残差とは法線成分とその対応する予測子要素との間の差である、予測符号化器と、法線成分をその残差、その予測子要素への参照および前記ミラー・マッピング動作のうちのどれが実行されたかを示すデータによってエンコードするエンコーダとを有する装置。さらに、その後エントロピー符号化器が使われてもよい。
【００１３】
本発明のある側面によれば、エンコードされたビットストリームから3Dメッシュ・モデルの法線成分をデコードする装置であって、法線成分は単位球上のその位置によって定義可能であり、エンコードされたビットストリームから予測子である法線成分のデータを抽出する第一の抽出手段と、該予測子についての識別子を抽出する第二の抽出手段と、エンコードされたビットストリームからエンコードされた法線成分に関係するデータを抽出する第三の抽出手段であって、該データは残差データ、予測子識別データおよびマッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがそのエンコードされた法線成分について実行されるべきか否かを示す、手段と、法線成分をデコードするデコード手段であって、前記残差データが前記予測子識別データに従って前記予測子に加えられ、結果として得られる法線成分が前記あらかじめ定義されたミラー・マッピング動作に従ってマッピングされる、手段とを有する、装置。
【００１４】
デコードする装置のある実施形態では、当該装置は、前記マッピング・データから、法線成分のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを抽出する手段を有する。クラスター識別データは法線成分をクラスターに関連付ける。クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている法線要素のために実行されるべきか否かを示す。この実施形態では、デコードする装置はさらに、あらかじめ定義されたミラー・マッピング動作に従って法線成分をマッピングするマッピング手段を有する。
【００１５】
本発明のある側面によれば、データ構造は、3Dメッシュ・モデルの頂点データおよびエンコードされた頂点配向データを含む。ここで、エンコードされた頂点配向データは少なくとも予測子、該予測子に関連付けられた識別子およびエンコードされた頂点配向に関係するデータを含み、エンコードされた頂点配向に関係するデータは残差データ、予測子識別データおよびマッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがエンコードされた頂点配向をデコードするために実行されるべきか否かを示す。
【００１６】
データ構造のある実施形態では、前記マッピング・データは頂点配向のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを含む。クラスター識別データは頂点配向をクラスターに関連付ける。クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている頂点配向のために実行されるべきか否かを示す。
本発明の有利な実施形態は、従属請求項、以下の記述および図面において開示される。
【図面の簡単な説明】
【００１７】
本発明の例示的な実施形態について、付属の図面を参照しつつ述べる。
【図１】単位球のセグメント分割を示す図である。
【図２】円筒である3Dメッシュ・モデルの配向軸を示す図である。
【図３】例示的な3Dメッシュ・モデルの配向軸の分布を単位球上に示す図である。
【図４】クラスタリングおよびマッピング後の、単位球上の配向軸の分布を示す図である。
【図５】第一のクラスタリング、マッピングおよび再クラスリング後のクラスター代表を示す図である。
【図６】（ａ）マッピング前および（ｂ）マッピング後の、配向と平均配向の間の最大誤差を示す図である。
【図７】エンコードのブロック図である。
【図８】デコードのブロック図である。
【図９】単位球についての代替的なセグメント分割方法を示す図である。
【図１０】枝付き燭台照明の例示的な3Dモデル、その連結成分の第一の配向軸の分布およびマッピング後の第一の配向軸の分布を示す図である。
【発明を実施するための形態】
【００１８】
図１は、その上に単位法線ベクトルが載る単位球のセクターを示している。球セクターは、球をm個の等しい球セグメントS1に分割し、前記球セグメントのそれぞれをn個の等しいセクター000,…,101に分割することによって得ることができる。簡単のため、球の球セグメントへの分割は三つのデカルト座標の軸、X、YおよびZ軸に沿ってできる。この結果、23＝8個のセグメントが生じる。他の分割方法、たとえば図９に似たものも可能である。m個のセクターとn個のセグメントの間のマッピングはint(log2(m)＋log2(n)＋1)個までのミラー・マッピング動作を含むことができる。たとえば、八個のセグメントS1および六個のセクター001,…,101については、セグメント間の三通りのマッピング動作が生じ、法線の大半（ほぼ全部）は単一のあらかじめ定義されたセグメント中にマッピングされ、前記あらかじめ定義されたセグメント内のさらに三通りのマッピング動作が生じ、法線の大半（ほぼ全部）は単一のあらかじめ定義されたセクター000中にマッピングされる。
【００１９】
好ましくは、法線のマッピングは一対一ではなく、法線はマッピングの前に第一のクラスタリング段階においてクラスタリングされる。このクラスタリング段階はk平均クラスタリングを使ってもよい。その目的は、マッピングを単純化することである。あるクラスターのすべての法線に対して同じマッピングが実行されるのである。異なるクラスターは（必須ではないが）異なるマッピングを使ってもよい。これは、利用可能なマッピングの異なる組み合わせを意味する。
【００２０】
マッピング後にさらなるクラスタリングを実行することが有利である。通例、マッピング後には、法線はより近くに密集しているからである。したがって、通例新しい、より大きなクラスターが生じる。この第二のクラスタリングは本稿では再クラスタリングとも呼ばれる。前の、第一のクラスタリングは、単にマッピングのために使われていた。再クラスタリング後、（クラスターにおいて代表を見出す既知の諸方法を使って）代表法線が決定され、諸法線はそのクラスター（すなわち、第二クラスター）の代表に対してエンコードされる。そのため、代表は予測子である。法線をエンコードする際、各法線は、その代表予測子、その予測誤差（残差）およびそのマッピングについての情報をもつ必要がある。代表予測子および残差から、法線は再構成されることができ、マッピング情報から、そのもとの位置が決定できる。マッピング情報は、第一のクラスタリングのクラスター識別子と、当該クラスターのすべての法線についてのクラスター・マッピング情報とを使ってエンコードされることができる。これは、マッピング情報がエンコードされ、伝送され、デコードされる必要があるのが、すべてのクラスター要素について一度だけであるという利点をもつ。
【００２１】
本発明の開示は、マッピング動作および適応k平均クラスタリング方法の力を組み合わせることのできる、配向を圧縮する効率的な方法を提案する。我々のアルゴリズムは、マッピング動作を使うかどうかを適応的に決定できる。第一に、すべての配向が、非常に効率的な適応k平均クラスタリング法を使ってクラスタリングされる。第二に、それらのクラスターがマッピングされる必要があるかどうかが判断される。異なる複数の六分区画に分布するデータ点をもつクラスターについては、我々はマッピング動作を実行する。マッピング動作は配向軸を、ラベル000をもつ1/48球ラベルにマッピングする。マッピング後は、すべてのデータが同じ六分区画にマッピングされているため、それらのクラスターの分散（variance）が減らされることができ、我々は、圧縮比をさらに改善するためにそれらをより少数のビットを用いて量子化できる。このことは図５および図６に示されている。次いで、「000」の1/48球部分およびそのすべての隣接1/48球部分にはいるすべての配向軸が、適応k平均クラスタリング方法を使って再クラスタリングされる。いまだに他の1/48球部分にはいる配向軸については、再クラスタリングされる必要はない。
【００２２】
図５は、マッピング前の第一クラスターの配向と平均配向との間の最大誤差５ｖを示している。図６は、マッピングおよび再クラスタリング後の第一クラスターの配向と平均配向との間の最大誤差６ｖを示している。見て取れるように、マッピングおよび再クラスタリングの前よりも、最大誤差はずっと小さくなっている。
【００２３】
モデルの配向は二つの軸によって効率的に表現されることができる。第一の軸は二つの自由度をもち、第二の軸は一つの自由度しかもたない。我々のアプローチは、第二の軸を圧縮するためにも使われることができる。違いは、第二の軸は円上に分布するということだけである。
【００２４】
配向軸は、それがはいる（第二）クラスターの代表によって予測される。予測誤差または残差が量子化される。
【００２５】
マッピング配向のため、図４に示すように、法線のクラスターの分散は大幅に小さくできる。
【００２６】
エンコーダおよびデコーダのブロック図は図７および図８に示されている。
【００２７】
「適応k平均クラスタリング」ブロック５２は次のように機能する。
【００２８】
初期化：n＝0
（１）kを小さな数に設定する。たとえば、k＝4。
（２）データ・セットをk平均クラスタリングによって分類する。
（３）n＝0;
（４）各クラスターについて
if（クラスターの分散がαより大きい） n++;
（５）if（n＝0） END
（６）αより大きな分散をもつ各クラスターについて、
該クラスターを2平均クラスタリング手順によって二つに分離する。
（７）Goto（３）。
【００２９】
ここで、αは閾値である。これは固定でもいいし、ユーザー定義されてもよい。
【００３０】
判断ブロック５３は、適応k平均クラスタリング・ブロック５２後に結果として得られる各クラスターを検査する。セクター・マッピング・ブロック５４では、異なる複数の「1/48球」部分にはいる法線を含むクラスターは「000」の1/48球（これが今の例ではあらかじめ定義されたターゲット・セクターである）にマッピングされる。
【００３１】
ある実施形態では、圧縮された配向軸情報のビットストリームは二つの部分を含む：
いくつかのビットはクラスターの数を示す。
・各クラスターについて：
・その代表を示すいくつかの浮動小数点値
・各配向軸の残差を量子化するために使われるビット数を示すいくつかのビット
・マッピング動作を用いて圧縮された配向軸の数を示すいくつかのビット
・マッピングされた各配向軸について：
・マッピング手順を示す6ビット
・それが属するクラスターのIDを示すいくつかのビット
・量子化された残差を示すいくつかのビット
・マッピングなしに圧縮された配向軸の数を示すいくつかのビット
・各配向軸について
・それが属するクラスターのIDを示すいくつかのビット
・量子化された残差を示すいくつかのビット。
【００３２】
ある実施形態では、異なるクラスターは通例異なる分散をもつので、圧縮された配向軸の数がエンコード／伝送される。分散は異なるビット数によって量子化されることができる。よって、この実施形態では、各法線成分の残差を量子化するのに使われているビット数を示すことにする。また、この実施形態では、マッピングされた各法線成分について「マッピングなしで圧縮された配向軸の数」を示すいくつかのビットが含められる。これは、この場合、マッピングありおよびマッピングなしで圧縮された配向軸の数を知る必要があるからである。理由は主として、圧縮解除のために、軸のためのスペースを割り当てることができるよう、圧縮された軸の数を知る必要があるということである。
【００３３】
ある実施形態では、3Dメッシュ・モデルの法線成分をエンコードする方法は、
3Dメッシュ・モデルの法線成分をクラスタリングする段階であって、一つまたは複数の第一クラスターが得られ、各法線成分は前記第一クラスターのうちの少なくとも一つのクラスターの要素である、段階と、
法線成分の前記第一クラスターのそれぞれについて、その要素の大半が属する球セクターを決定する段階であって、球セクターは、球をm個の等しい球セグメントに分割し、前記球セグメントのそれぞれをn個の等しいセクターに分割することによって得られる、段階と、
前記決定する段階によれば前記セクターのあらかじめ定義されたものにない法線成分を前記あらかじめ定義されたセクター中にマッピングする段階であって、前記マッピングはint(log2(m)＋log2(n)＋1)個までのミラー・マッピング動作を含む、段階と、
法線成分を再クラスタリングする段階であって、一つまたは複数の第二クラスターが得られ、各法線成分は前記第二クラスターのうちの少なくとも一つのクラスターの要素である、段階と、
法線成分を量子化する段階と、
前記第二クラスターのそれぞれについて、代表予測子要素を決定する段階と、
前記法線成分のための残差を決定する段階であって、残差とは法線成分とその対応する予測子要素との間の差である、段階と、
法線成分をその残差、その予測子要素への参照および前記ミラー・マッピング動作のうちのどれが実行されたかを示すデータによってエンコードする段階とを含む。
【００３４】
ある実施形態では、第一および／または第二のクラスタリング動作は適応k平均クラスタリングを使う。
【００３５】
ある実施形態では、球セグメントの数はm＝8であり、各セグメント内のセクターの数はn＝6である。ある実施形態では、前記球セグメントは球面三角形である。
【００３６】
ある実施形態では、本エンコード方法はさらに、前記マッピング後に、3Dメッシュ・モデルを回転させ、マッピングされた第一クラスターのより多くの要素が前記あらかじめ定義されたセクターにはいるようにする段階を含む。
【００３７】
ある実施形態では、第二クラスターの前記代表予測子要素は、前記クラスターの実際の要素である前記法線成分の一つである。別の実施形態では、それは仮想的な（存在しない）予測子要素である。
【００３８】
ある実施形態では、前記ミラー・マッピング動作のうちのどれが実行されたかを示す前記データは、その法線成分がどの第一クラスターに属するかを同定するデータと、その第一クラスターについて前記ミラー・マッピング動作のうちのどれが実行されたかを示すマッピング指標データとを含む。
【００３９】
ある実施形態では、前記ミラー・マッピング動作のうちのどれが実行されたかを示す前記データは、球のm個の等しい球セグメントへの分割および前記球セグメントのそれぞれのn個の等しいセクターへの分割を定義するデータを含む。
【００４０】
ある実施形態では、エンコードされたビットストリームから3Dメッシュ・モデルの法線成分をデコードする方法は、
エンコードされたビットストリームから予測子である法線成分のデータを抽出し、該予測子についての識別子を抽出する段階と、
エンコードされたビットストリームからエンコードされた法線成分に関係するデータを抽出する段階であって、該データは残差データ、予測子識別データおよびマッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがそのエンコードされた法線成分について実行されるべきか否かを示す、段階と、
法線成分をデコードする段階であって、前記残差データが前記予測子識別データに従って前記予測子に加えられ、結果として得られる法線成分が前記あらかじめ定義されたミラー・マッピング動作に従ってマッピングされる、段階とを含む。
【００４１】
デコードする方法のある実施形態では、前記マッピング・データは、法線成分のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを含む。クラスター識別データは法線成分をクラスターに関連付ける。クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている法線要素のために実行されるべきか否かを示す。
【００４２】
ある実施形態では、本デコード方法はさらに、ビットストリームからミラー動作データを抽出する段階を含む。ここで、前記あらかじめ決定されたミラー動作は前記ミラー動作データによって定義される。
【００４３】
ある実施形態では、3Dメッシュ・モデルの法線成分をエンコードする装置は図７に示される機能ブロックに対応するモジュールを有する。
【００４４】
ある実施形態では、3Dメッシュ・モデルの法線成分をデコードする装置は図８に示される機能ブロックに対応するモジュールを有する。
【００４５】
ある実施形態では、データ構造は、3Dメッシュ・モデルの頂点データおよびエンコードされた頂点配向データを含む。ここで、エンコードされた頂点配向データは少なくとも予測子、該予測子に関連付けられた識別子およびエンコードされた頂点配向に関係するデータを含み、エンコードされた頂点配向に関係するデータは、
残差データ、予測子識別データおよびマッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがエンコードされた頂点配向をデコードするために実行されるべきか否かを示す。
【００４６】
データ構造のある実施形態では、前記マッピング・データは頂点配向のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを含む。クラスター識別データは頂点配向をクラスターに関連付ける。クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている頂点配向のために実行されるべきか否かを示す。
【００４７】
本発明は、原理的には、あらゆる現実的な3Dメッシュ・モデルにとって有利である。本発明は、法線が均一に分布していない3Dメッシュ・モデルにとって特に有利である。3Dメッシュ・モデルがより多くの頂点をもつほど（つまり、モデルがより大きいほど）、本発明はより効果的である。また、モデルが法線の第一クラスターをより多くもつほど、マッピング後に結果として得られる第二クラスターがより大きくなるので、本発明はより効果的である。
【００４８】
図２は、例示的に、円筒形の3Dメッシュ・モデルの配向軸を示している。見て取れるように、法線はXY平面のまわりにはあらゆる方向に分布しているが、XY平面内では二つの方向、すなわち上下のみに分布している。このように、少なくともXY平面の法線は簡単にクラスタリングでき、そのエンコードにおいてビットを節約できる。ある実施形態では、法線についての開示されるエンコード方法は、3Dメッシュ・モデルのすべてではなく一部の法線のみに使われる。
【００４９】
図３は、もう一つの例示的な3Dメッシュ・モデルの配向軸の位置を示している。このモデル形状によれば、法線は単位球３１上のグループ３１ａ〜３１ｄに位置される。各グループはクラスタリングされることができ、各クラスターは、すでにターゲット・セグメントまたはセクター内にあるのでない限り、あらかじめ定義されたターゲット・セグメントおよびセクターにマッピングされる。クラスターがすでにターゲット・セグメント内にある場合、セクター・マッピングのみを実行するので十分である。それでも、各マッピング段階が実行される必要があるか否かをエンコード／デコードする必要がある。たとえばエンコードおよびマッピング情報。
【００５０】
図４は、クラスタリングおよびマッピング後の単位球上での配向軸の分布を示している。見て取れるように、図３のクラスターのうちの二つ３１ａ、３１ｂが同じ領域にマッピングされている。したがって、再クラスタリング段階において新しいクラスター４１ａｂが生成される。この新しいクラスター４１ａｂのすべての要素は、この新しいクラスターについての予測子のはたらきをするクラスター代表４１ａｂｒから予測できる。
【００５１】
図１０は、多数の円筒状の連結成分を有する枝付き燭台照明の例示的な3Dモデルを示している。各連結成分は図２のモデルのような法線分布をもつ。図１０のｂ）は、モデルの第一の配向軸の分布を示す。多くの配向軸が円上に載っているので、連結成分の配向軸が優勢であることが見て取れる。図１０のｃ）は、マッピング後の第一の配向軸の分布を示している。見て取れるように、主として、非常に密な二つのクラスターだけが残っており、よって予測を使って有利にエンコードできる。
【００５２】
本発明は、（完全な3Dモデルの単なる部分である）連結成分の配向軸／法線ならびに完全な3Dモデルの配向軸／法線の圧縮に関するいかなるシナリオにも適用できる。
【００５３】
当業者には明白であろうが、図１に示したもの以外の他の型の単位球セグメンテーションが構築されてもよいことを注意しておく。そのすべては本発明の精神および範囲内と考えられる。図９は、いくつかの代替的な可能性の一つを示しており、８つのセクターのそれぞれがいくつかのスライス７１ｎ、７１ｓに分離されている。
【００５４】
本発明の好ましい実施形態に適用される本発明の基本的な新たな特徴を示し、説明し、指摘してきたが、本発明の精神から外れることなく、開示される装置の形および詳細においてまたその動作において、記載される装置および方法においてさまざまな省略および代替および変更が当業者によってなされてもよいことは理解されるであろう。さらに、すべての実施形態は、明白に互いに相反するのでない限り、自由に組み合わせることができる。同じ結果を達成するために実質的に同じ仕方で実質的に同じ機能を実行する要素のあらゆる組み合わせは本発明の範囲内であることが明白に意図されている。記載されるある実施形態から別の実施形態への要素の転用も完全に意図されており、考えられている。
【００５５】
本発明は純粋に例として記載されてきたのであり、本発明の範囲から外れることなく細部の修正ができることは理解されるであろう。
【００５６】
本明細書および適切な場合には請求項および図面において開示される各特徴は、独立して、または任意の適切な組み合わせにおいて設けられてもよい。諸特徴は、適切な場合には、ハードウェア、ソフトウェアまたは両者の組み合わせとして実装されてもよい。請求項に参照符号が現れたとしても、単に例解のためであって、特許請求の範囲を限定する効果はもたないものとする。
【特許請求の範囲】
【請求項１】
3Dメッシュ・モデルの法線成分をエンコードする方法であって、法線成分は単位球上でのその位置により定義可能であり、当該方法は、
・前記3Dメッシュ・モデルの法線成分をクラスタリングする段階であって、一つまたは複数の第一クラスターが得られ、各法線成分は前記第一クラスターのうちの少なくとも一つのクラスターの要素である、段階と、
・法線成分の前記第一クラスターのそれぞれについて、その要素の大半が属する球セクターを決定する段階であって、球セクターは、球をm個の等しい球セグメントに分割し、前記球セグメントのそれぞれをn個の等しいセクターに分割することによって得られる、段階と、
・前記決定する段階によれば前記セクターのあらかじめ定義されたものにない法線成分を前記あらかじめ定義されたセクター中にマッピングする段階であって、前記マッピングはint(log2(m)＋log2(n)＋1)個までのミラー・マッピング動作を含む、段階と、
・法線成分を再クラスタリングする段階であって、一つまたは複数の第二クラスターが得られ、各法線成分は前記第二クラスターのうちの少なくとも一つのクラスターの要素である、段階と、
・法線成分を量子化する段階と、
・前記第二クラスターのそれぞれについて、代表予測子要素を決定する段階と、
・前記法線成分のための残差を決定する段階であって、残差とは法線成分とその対応する予測子要素との間の差である、段階と、
・法線成分をその残差、その予測子要素への参照および前記ミラー・マッピング動作のうちのどれが実行されたかを示すデータによってエンコードする段階とを含む、
方法。
【請求項２】
前記第一および／または前記第二のクラスタリング動作は適応k平均クラスタリングを使う、請求項１記載の方法。
【請求項３】
m＝8かつn＝6であり、前記球セグメントは球面三角形である、請求項１または２記載の方法。
【請求項４】
前記マッピング後に、3Dメッシュ・モデルを回転させ、マッピングされた第一クラスターのより多くの要素が前記あらかじめ定義されたセクターにはいるようにする段階を含む、請求項１ないし３のうちいずれか一項記載の方法。
【請求項５】
前記第二クラスターの前記代表予測子要素は、前記法線成分の一つである、請求項１ないし４のうちいずれか一項記載の方法。
【請求項６】
前記ミラー・マッピング動作のうちのどれが実行されたかを示す前記データは、その法線成分がどの第一クラスターに属するかを同定するデータと、その第一クラスターについて前記ミラー・マッピング動作のうちのどれが実行されたかを示すマッピング指標データとを含む、請求項１ないし５のうちいずれか一項記載の方法。
【請求項７】
前記ミラー・マッピング動作のうちのどれが実行されたかを示す前記データは、球のm個の等しい球セグメントへの分割および前記球セグメントのそれぞれのn個の等しいセクターへの分割を定義するデータを含む、請求項１ないし５のうちいずれか一項記載の方法。
【請求項８】
エンコードされたビットストリームから3Dメッシュ・モデルの法線成分をデコードする方法であって、法線成分は単位球上でのその位置により定義可能であり、当該方法は、
・エンコードされたビットストリームから、予測子である法線成分のデータを抽出し、該予測子についての識別子を抽出する段階と、
・エンコードされたビットストリームから、エンコードされた法線成分に関係するデータを抽出する段階であって、該データは残差データ、予測子識別データおよびマッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがそのエンコードされた法線成分について実行されるべきか否かを示す、段階と、
・法線成分をデコードする段階であって、前記残差データが前記予測子識別データに従って前記予測子に加えられ、結果として得られる法線成分が前記あらかじめ定義されたミラー・マッピング動作に従ってマッピングされる、段階とを含む、
方法。
【請求項９】
前記マッピング・データは、法線成分のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを含み、前記クラスター識別データは法線成分をクラスターに関連付け、前記クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている法線要素のために実行されるべきか否かを示す、請求項８記載の方法。
【請求項１０】
前記ビットストリームからミラー動作データを抽出する段階をさらに含み、前記あらかじめ決定されたミラー動作は前記ミラー動作データによって定義される、請求項８または９記載の方法。
【請求項１１】
請求項１ないし７のうちいずれか一項記載の方法を使って3Dメッシュ・モデルの法線成分をエンコードする装置。
【請求項１２】
請求項８ないし１０のうちいずれか一項記載の方法を使って3Dメッシュ・モデルの法線成分をデコードする装置。
【請求項１３】
3Dメッシュ・モデルの頂点データおよびエンコードされた頂点配向データを含むデータ構造であって、前記エンコードされた頂点配向データは少なくとも予測子、該予測子に関連付けられた識別子およびエンコードされた頂点配向に関係するデータを含み、エンコードされた頂点配向に関係する前記データは、
・残差データ、
・予測子識別データおよび
・マッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれが前記エンコードされた頂点配向をデコードするために実行されるべきか否かを示す、
データ構造。
【請求項１４】
前記マッピング・データは頂点配向のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを含み、前記クラスター識別データは頂点配向をクラスターに関連付け、前記クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている頂点配向のために実行されるべきか否かを示す、請求項１３記載のデータ構造。
【請求項１】
3Dメッシュ・モデルの法線成分をエンコードする方法であって、法線成分は単位球上でのその位置により定義可能であり、当該方法は、
・前記3Dメッシュ・モデルの法線成分をクラスタリングする段階であって、一つまたは複数の第一クラスターが得られ、各法線成分は前記第一クラスターのうちの少なくとも一つのクラスターの要素である、段階と、
・法線成分の前記第一クラスターのそれぞれについて、その要素の大半が属する球セクターを決定する段階であって、球セクターは、球をm個の等しい球セグメントに分割し、前記球セグメントのそれぞれをn個の等しいセクターに分割することによって得られる、段階と、
・前記決定する段階によれば前記セクターのあらかじめ定義されたものにない法線成分を前記あらかじめ定義されたセクター中にマッピングする段階であって、前記マッピングはint(log2(m)＋log2(n)＋1)個までのミラー・マッピング動作を含む、段階と、
・法線成分を再クラスタリングする段階であって、一つまたは複数の第二クラスターが得られ、各法線成分は前記第二クラスターのうちの少なくとも一つのクラスターの要素である、段階と、
・法線成分を量子化する段階と、
・前記第二クラスターのそれぞれについて、代表予測子要素を決定する段階と、
・前記法線成分のための残差を決定する段階であって、残差とは法線成分とその対応する予測子要素との間の差である、段階と、
・法線成分をその残差、その予測子要素への参照および前記ミラー・マッピング動作のうちのどれが実行されたかを示すデータによってエンコードする段階とを含む、
方法。
【請求項２】
前記第一および／または前記第二のクラスタリング動作は適応k平均クラスタリングを使う、請求項１記載の方法。
【請求項３】
m＝8かつn＝6であり、前記球セグメントは球面三角形である、請求項１または２記載の方法。
【請求項４】
前記マッピング後に、3Dメッシュ・モデルを回転させ、マッピングされた第一クラスターのより多くの要素が前記あらかじめ定義されたセクターにはいるようにする段階を含む、請求項１ないし３のうちいずれか一項記載の方法。
【請求項５】
前記第二クラスターの前記代表予測子要素は、前記法線成分の一つである、請求項１ないし４のうちいずれか一項記載の方法。
【請求項６】
前記ミラー・マッピング動作のうちのどれが実行されたかを示す前記データは、その法線成分がどの第一クラスターに属するかを同定するデータと、その第一クラスターについて前記ミラー・マッピング動作のうちのどれが実行されたかを示すマッピング指標データとを含む、請求項１ないし５のうちいずれか一項記載の方法。
【請求項７】
前記ミラー・マッピング動作のうちのどれが実行されたかを示す前記データは、球のm個の等しい球セグメントへの分割および前記球セグメントのそれぞれのn個の等しいセクターへの分割を定義するデータを含む、請求項１ないし５のうちいずれか一項記載の方法。
【請求項８】
エンコードされたビットストリームから3Dメッシュ・モデルの法線成分をデコードする方法であって、法線成分は単位球上でのその位置により定義可能であり、当該方法は、
・エンコードされたビットストリームから、予測子である法線成分のデータを抽出し、該予測子についての識別子を抽出する段階と、
・エンコードされたビットストリームから、エンコードされた法線成分に関係するデータを抽出する段階であって、該データは残差データ、予測子識別データおよびマッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがそのエンコードされた法線成分について実行されるべきか否かを示す、段階と、
・法線成分をデコードする段階であって、前記残差データが前記予測子識別データに従って前記予測子に加えられ、結果として得られる法線成分が前記あらかじめ定義されたミラー・マッピング動作に従ってマッピングされる、段階とを含む、
方法。
【請求項９】
前記マッピング・データは、法線成分のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを含み、前記クラスター識別データは法線成分をクラスターに関連付け、前記クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている法線要素のために実行されるべきか否かを示す、請求項８記載の方法。
【請求項１０】
前記ビットストリームからミラー動作データを抽出する段階をさらに含み、前記あらかじめ決定されたミラー動作は前記ミラー動作データによって定義される、請求項８または９記載の方法。
【請求項１１】
請求項１ないし７のうちいずれか一項記載の方法を使って3Dメッシュ・モデルの法線成分をエンコードする装置。
【請求項１２】
請求項８ないし１０のうちいずれか一項記載の方法を使って3Dメッシュ・モデルの法線成分をデコードする装置。
【請求項１３】
3Dメッシュ・モデルの頂点データおよびエンコードされた頂点配向データを含むデータ構造であって、前記エンコードされた頂点配向データは少なくとも予測子、該予測子に関連付けられた識別子およびエンコードされた頂点配向に関係するデータを含み、エンコードされた頂点配向に関係する前記データは、
・残差データ、
・予測子識別データおよび
・マッピング・データを含み、該マッピング・データは、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれが前記エンコードされた頂点配向をデコードするために実行されるべきか否かを示す、
データ構造。
【請求項１４】
前記マッピング・データは頂点配向のためのクラスター識別データおよび各クラスターについてのクラスター・マッピング・データを含み、前記クラスター識別データは頂点配向をクラスターに関連付け、前記クラスター・マッピング・データは特定のクラスターに関係し、複数のあらかじめ定義されたミラー・マッピング動作のそれぞれがその特定のクラスターに関連付けられている頂点配向のために実行されるべきか否かを示す、請求項１３記載のデータ構造。
【図１】
【図２】
【図３】
【図４ａ）】
【図４ｂ）】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０ａ）】
【図１０ｂ）】
【図１０ｃ）】
【図２】
【図３】
【図４ａ）】
【図４ｂ）】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０ａ）】
【図１０ｂ）】
【図１０ｃ）】
【公表番号】特表２０１３−５１８３１５（Ｐ２０１３−５１８３１５Ａ）
【公表日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【出願番号】特願２０１２−５４９２２６（Ｐ２０１２−５４９２２６）
【出願日】平成２２年１月２５日（２０１０．１．２５）
【国際出願番号】ＰＣＴ／ＣＮ２０１０／０００１０９
【国際公開番号】ＷＯ２０１１／０８８５９５
【国際公開日】平成２３年７月２８日（２０１１．７．２８）
【出願人】（５０１２６３８１０）トムソン ライセンシング (2,848)
【氏名又は名称原語表記】Ｔｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ
【住所又は居所原語表記】１−５， ｒｕｅ Ｊｅａｎｎｅ ｄ’Ａｒｃ， ９２１３０ ＩＳＳＹ ＬＥＳ ＭＯＵＬＩＮＥＡＵＸ， Ｆｒａｎｃｅ
【Ｆターム（参考）】
【公表日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【出願日】平成２２年１月２５日（２０１０．１．２５）
【国際出願番号】ＰＣＴ／ＣＮ２０１０／０００１０９
【国際公開番号】ＷＯ２０１１／０８８５９５
【国際公開日】平成２３年７月２８日（２０１１．７．２８）
【出願人】（５０１２６３８１０）トムソン ライセンシング (2,848)
【氏名又は名称原語表記】Ｔｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ
【住所又は居所原語表記】１−５， ｒｕｅ Ｊｅａｎｎｅ ｄ’Ａｒｃ， ９２１３０ ＩＳＳＹ ＬＥＳ ＭＯＵＬＩＮＥＡＵＸ， Ｆｒａｎｃｅ
【Ｆターム（参考）】
[ Back to top ]