JP5536193B2 - 各シンボルが三つ以上の可能なシンボル値のうちの一つをもちうる場合のシンボル・シーケンスのエンコードおよびデコードの方法および装置 - Google Patents

Description

本発明は、各シンボルが三つ以上の可能なシンボル値のうちの一つをもちうる場合のシンボル・シーケンスのエンコードおよびデコードの技術分野においてなされたものである。

３Ｄオブジェクトを表現するためのさまざまなアプリケーションにおいて三次元（３Ｄ）メッシュが広く使われてきた。そうしたアプリケーションはゲーム、エンジニアリング・デザイン、建築のウォークスルー、仮想現実感、電子商取引および科学的視覚化を含む。それらの生の表現は通例、大量のデータを必要とし、特に近年における３Ｄスキャナの急速な成長とともにそうなっている。しかしながら、たいていのアプリケーションは記憶および伝送のために３Ｄメッシュのコンパクトな表現を要求する。

典型的には、３Ｄメッシュは三つの型のデータによって表現される：
トポロジー・データは頂点〔バーテックス〕間の隣接関係を記述し、他所では接続性データとも呼ばれる。幾何学データは頂点位置を指定する。プロパティー・データは、法線ベクトル、素材反射率およびテクスチャー座標のような属性〔アトリビュート〕を指定する。

トポロジー・データおよび幾何学データは共通してまたは別個に圧縮されうる。幾何学データの符号化順序は、根底にあるトポロジー符号化によって決定される。幾何学データは通例、量子化、予測およびエントロピー符号化の三つの主要なステップによって圧縮される。３Ｄメッシュ・プロパティー・データは通例、幾何学的圧縮の同様の方法によって圧縮される。

３Ｄ三角形メッシュのトポロジー・データをエンコードする方法のなかでも、非特許文献１によって提案されるエッジブレーカー（Edgebreaker）はきわめて効率的であり、広く使用されているものである。

大きめのメッシュについては、エッジブレーカーおよびエントロピー符号化の出力は、三角形当たり1.5ビット未満にできる。エッジブレーカーの圧縮および圧縮解除プロセスは、ある三角形から隣接する三角形への、メッシュの同一の通過（traversals）を実行する。各段において、圧縮は、現在の三角形と、メッシュのすでにエンコードされた部分の境界との間のトポロジー関係を記述するためのビットを生じる。圧縮解除は、これらのビットをデコードしてトポロジー・グラフ全体を再構成する。エッジブレーカー・アルゴリズムを使うことにより、３Ｄ三角形メッシュの全トポロジー・データは五つの可能なモード・シンボルC、R、L、EおよびSの系列となる。たとえば、エッジブレーカー・アルゴリズムの最終的な出力は「CCRRRSLCRSERRELCRRRCRRRE……」のように見える。

エッジブレーカーによる３Ｄメッシュの五つの可能なモード・シンボルのうち三つ――L、E、S――は他の二つのシンボル――C、R――ほど頻繁には現れない。たとえば、
CRCRCRCRCLRECCRCRCRRCRLCCRRCRCRRCCRCRCCRSRCRCRCRRCRCR……
たとえば、いくつかの３Ｄメッシュ・モデルにおける５つのモードの生起は次のようになる。

Edgebreaker: Connectivity compression for triangle meshes、IEEE Transactions on Visualization and Computer Graphics、Vol.5、No.1、pp.47-61、January-March 1999

本発明は、たとえばエッジブレーカー・アルゴリズム後の３Ｄメッシュ・モデルのトポロジー・データを表す多シンボル・シーケンス内の統計的な冗長性を除去する方法を提案する。

本発明はまず、いくつかのシンボルを新しいシンボルに組み合わせ、次いである種のコンテキスト・モデルを使って新しいシンボルを他のシンボルと一緒にエンコードする。新しいシンボルがエンコードされる場合、組み合わせの詳細が次にエンコードされ、ここで、各シンボルの「ラン〔連続〕（runs）」における異なる位置についていくつかのコンテキスト・モデルが使用される。

シンボル・シーケンスを圧縮する方法が提案される。各シンボルは、三つ以上の可能なシンボル値のうちの一つをもちうる。当該方法は、最も高頻度のシンボル値のシンボルの第一のランと二番目に最も高頻度のシンボル値のシンボルの第二のランを含む各ラン対を、前記三つ以上の可能なシンボル値に含まれないさらなるシンボル値によって置換することによって前記シンボル・シーケンスを修正する段階と、すべての置換されたラン対を含む二値シーケンスを生成する段階と、前記二値シーケンスおよび前記修正されたシンボル・シーケンスを圧縮エンコードする段階とを含む。

さらに、シンボル・シーケンスの二値表現が提案される。各シンボルはn個の可能なシンボル値のうちの一つをもちうる。n＞2である。前記シンボル・シーケンスは、修正されたシンボル・シーケンスの二値表現および二値シーケンスの二値表現によって表される。修正されたシンボル・シーケンスのシンボルは、(n−1)個の可能なシンボル値のうちの一つをもちうる。

そのようなビット・ストリームを担持する記憶媒体が提案される。

ある実施形態では、次の方法が二値シーケンスを圧縮エンコードするために適用される：
前記二値シーケンスのビットを反転させることによって別のビット・シーケンスを生成する。ここで、前記二値シーケンスにおいて直前に、二つの可能なビット値のうちの第一のものを有するそれぞれの先行ビットがあるビットのみが反転される。前記別のビット・シーケンスをエンコードする。

もう一つの実施形態では、前記二値シーケンスの圧縮エンコードは、「１」のランの長さの単進（unary）表現の第一のシーケンスを生成し、「０」のランの長さの単進（unary）表現の第二のシーケンスを生成し、生成された単進表現の第一および第二のシーケンスをビット平面エンコードすることを含む。

シンボル・シーケンスをデコードするためには、修正されたシンボル・シーケンスがデコードされ、二値シーケンスがデコードされる。次いで、前記修正されたシンボル・シーケンス中の前記さらなるシンボルの各生起が、前記二値シーケンスに含まれるラン対によって置換される。ここで、前記二値シーケンスにおけるラン対の順序は、前記修正されたシンボル・シーケンス中の前記さらなるシンボルの置換後のラン対の順序に等しい。

二値シーケンスのデコードは、別のビット・シーケンスをデコードし、前記別のビット・シーケンスのビットを反転させることによって前記二値シーケンスを生成することによってできる。ここで、反転される各ビットは、前記二値シーケンスにおいて直前に、二つの異なるビット値のうちの第一のものを有するそれぞれの先行ビットがあるものである。

例示的なエンコーダは、二つのステップでエンコードするよう適応される。

ステップ１――第一レベル：
まず、語とも呼ばれるすべての「C…CR…R」の組み合わせをみつける。各語は、「C」のランに「R」のランが続いたものからなる（または各語は「C」のランに「R」のランが先行するものからなる）。次いで、各語が、個々の語が有するランの長さとは独立に、同じシンボル、たとえば「A」によって置換される。結果として得られるシンボル・シーケンスがその後エンコードされる。

たとえば、
CRCRCRCRCLRECCRCRCRRCRLCCRRCRCRRCCRCRCCRSRCRCRCRRCRCR……
は
AAAACLREAAAALAAAAAASRAAAAA……
に変えられる。

注：グループ分けの仕方は次のとおり：
(CR)(CR)(CR)(CR)CLRE(CCR)(CR)(CRR)(CR)L(CCRR)(CR)(CRR)(CCR)(CR)(CCR)SR(CR)(CR)(CRR)(CR)(CR)……
ここで、「A」は単に「C…CR…R」のグループを意味し、「C」の数および「R」の数は固定されていないが、0よりは大きい。分離した「C」、たとえば「L」の前の「C」があれば、「C」はそのまま保持する。分離した「R」、たとえば「E」の前の「R」および「S」のあとの「R」があれば、それも保持する。

このステップにおいて、６個のシンボル「C」「R」「L」「E」「S」「A」を用いた新たな系列がエントロピー符号化方法によってエンコードされる。

ステップ２――第二レベル：
「A」がエンコードされる場合、「C…CR…R」の組み合わせが次いでエンコードされる。これは、「C」のランおよび「R」のランを異なるコンテキスト・モデルによってエンコードする。

このステップは、ステップ（１）と連結することができる。それにより、エンコードはシンボル系列を１パスだけでエンコードできる。また、デコーダはビット・ストリームを１パスでデコードできる。

上記の二つのステップの擬似コードは状態機械として表現できる。

実験結果：

表２は前記の例のトポロジー・データの圧縮結果を掲げている。ここで、VLC符号化はハフマン符号が使われることを意味する。提案される方法は、上記の擬似コードに従って開発されている。

この表から、提案される方法は、既存の算術符号化に対して、圧縮率で6.4%〜47.1%の改善を達成できることが見て取れる。

二レベルでシンボルをエンコードする方法が提案される。

まず、いくつかのシンボルの何らかの組み合わせ（たとえばC…CR…R）を新しいシンボル（たとえばA）として扱い、新しいシンボルを既存の他のシンボルと一緒に（たとえばCRLESA）ある種のコンテキスト・モデル（たとえばコンテキスト・モデル０）によってエンコードする。

新しいシンボル（たとえばA）が現れる場合の第二レベル、該新しいシンボルに続いて、その対応するもとのシンボル組み合わせ（C…CR…R）が他のコンテキスト・モデル（たとえばコンテキスト・モデル2*i＋1、コンテキスト・モデル2*i＋2）の系列によってエンコードされる。

したがって、組み合わせ（たとえばCRCRCCRCRCRCRR…）におけるシンボルの「ラン」に存する冗長性が除去される。

エントロピー符号化方法はデータ圧縮における基本プロセスである。提案される方法は、実際上、たとえば伝送規格の定義のために使うことができる。

上記の例示的な実施形態は単に例解のためであって、いかなる仕方であれ保護が求められる本発明の精神および範囲を限定するものと解釈してはならないことは理解しておくべきである。本発明の範囲は請求項によってのみ定義される。

特に、本発明は、決して、空間的なデータに限定されるものではなく、たとえばファイル・データまたは測定データを含むあらゆる種類のデータに適用可能である。

Claims (4)

1. エンコード装置によって実行される、シンボル・シーケンスを圧縮する方法であって、各シンボルは三つ以上の可能なシンボル値のうちの一つをもち、当該方法は：
   ・最も高頻度のシンボル値のシンボルの第一のランの直後に二番目に最も高頻度のシンボル値のシンボルの第二のランを含むラン対のそれぞれを、前記三つ以上の可能なシンボル値に含まれないさらなるシンボル値によって置換することによって前記シンボル・シーケンスを修正する段階と、
   ・すべての置換されたラン対を含む二値シーケンスを生成する段階と、
   ・前記二値シーケンスおよび前記修正されたシンボル・シーケンスを圧縮エンコードする段階とを含む、
   方法。
2. 請求項１記載の方法を実行するエンコード装置。
3. デコード装置によって実行される、圧縮されたシンボル・シーケンスを圧縮解除する方法であって、各シンボルは三つ以上の可能なシンボル値のうちの一つをもち、当該方法は：
   ・前記三つ以上の可能なシンボル値に含まれないさらなるシンボル値のシンボルを含む異なるシンボル・シーケンスをデコードし、二値シーケンスに含まれるラン対のシーケンスをデコードし、前記ラン対のシーケンスにおけるラン対の数は前記異なるシンボル・シーケンスにおける前記さらなるシンボル値のシンボルの数に等しい、段階と、
   ・前記異なるシーケンスにおいて、前記さらなるシンボル値のシンボルを、前記ラン対によって置換する段階であって、前記ラン対の順序は維持される、段階とを含む、
   方法。
4. 請求項３記載の方法を実行するデコード装置。