(57)【特許請求の範囲】
【請求項１】
エンコード装置によって実行される、シンボル・シーケンスを圧縮する方法であって、各シンボルは三つ以上の可能なシンボル値のうちの一つをもち、当該方法は：
・最も高頻度のシンボル値のシンボルの第一のランの直後に二番目に最も高頻度のシンボル値のシンボルの第二のランを含むラン対のそれぞれを、前記三つ以上の可能なシンボル値に含まれないさらなるシンボル値によって置換することによって前記シンボル・シーケンスを修正する段階と、
・すべての置換されたラン対を含む二値シーケンスを生成する段階と、
・前記二値シーケンスおよび前記修正されたシンボル・シーケンスを圧縮エンコードする段階とを含む、
方法。
【請求項２】
請求項１記載の方法を実行するエンコード装置。
【請求項３】
デコード装置によって実行される、圧縮されたシンボル・シーケンスを圧縮解除する方法であって、各シンボルは三つ以上の可能なシンボル値のうちの一つをもち、当該方法は：
・前記三つ以上の可能なシンボル値に含まれないさらなるシンボル値のシンボルを含む異なるシンボル・シーケンスをデコードし、二値シーケンスに含まれるラン対のシーケンスをデコードし、前記ラン対のシーケンスにおけるラン対の数は前記異なるシンボル・シーケンスにおける前記さらなるシンボル値のシンボルの数に等しい、段階と、
・前記異なるシーケンスにおいて、前記さらなるシンボル値のシンボルを、前記ラン対によって置換する段階であって、前記ラン対の順序は維持される、段階とを含む、
方法。
【請求項４】
請求項３記載の方法を実行するデコード装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、各シンボルが三つ以上の可能なシンボル値のうちの一つをもちうる場合のシンボル・シーケンスのエンコードおよびデコードの技術分野においてなされたものである。
【背景技術】
【０００２】
３Ｄオブジェクトを表現するためのさまざまなアプリケーションにおいて三次元（３Ｄ）メッシュが広く使われてきた。そうしたアプリケーションはゲーム、エンジニアリング・デザイン、建築のウォークスルー、仮想現実感、電子商取引および科学的視覚化を含む。それらの生の表現は通例、大量のデータを必要とし、特に近年における３Ｄスキャナの急速な成長とともにそうなっている。しかしながら、たいていのアプリケーションは記憶および伝送のために３Ｄメッシュのコンパクトな表現を要求する。
【０００３】
典型的には、３Ｄメッシュは三つの型のデータによって表現される：
トポロジー・データは頂点〔バーテックス〕間の隣接関係を記述し、他所では接続性データとも呼ばれる。幾何学データは頂点位置を指定する。プロパティー・データは、法線ベクトル、素材反射率およびテクスチャー座標のような属性〔アトリビュート〕を指定する。
【０００４】
トポロジー・データおよび幾何学データは共通してまたは別個に圧縮されうる。幾何学データの符号化順序は、根底にあるトポロジー符号化によって決定される。幾何学データは通例、量子化、予測およびエントロピー符号化の三つの主要なステップによって圧縮される。３Ｄメッシュ・プロパティー・データは通例、幾何学的圧縮の同様の方法によって圧縮される。
【０００５】
３Ｄ三角形メッシュのトポロジー・データをエンコードする方法のなかでも、非特許文献１によって提案されるエッジブレーカー（Edgebreaker）はきわめて効率的であり、広く使用されているものである。
【０００６】
大きめのメッシュについては、エッジブレーカーおよびエントロピー符号化の出力は、三角形当たり1.5ビット未満にできる。エッジブレーカーの圧縮および圧縮解除プロセスは、ある三角形から隣接する三角形への、メッシュの同一の通過（traversals）を実行する。各段において、圧縮は、現在の三角形と、メッシュのすでにエンコードされた部分の境界との間のトポロジー関係を記述するためのビットを生じる。圧縮解除は、これらのビットをデコードしてトポロジー・グラフ全体を再構成する。エッジブレーカー・アルゴリズムを使うことにより、３Ｄ三角形メッシュの全トポロジー・データは五つの可能なモード・シンボルC、R、L、EおよびSの系列となる。たとえば、エッジブレーカー・アルゴリズムの最終的な出力は「CCRRRSLCRSERRELCRRRCRRRE……」のように見える。
【０００７】
エッジブレーカーによる３Ｄメッシュの五つの可能なモード・シンボルのうち三つ――L、E、S――は他の二つのシンボル――C、R――ほど頻繁には現れない。たとえば、
CRCRCRCRCLRECCRCRCRRCRLCCRRCRCRRCCRCRCCRSRCRCRCRRCRCR……
たとえば、いくつかの３Ｄメッシュ・モデルにおける５つのモードの生起は次のようになる。
0005536193.tif 000002
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】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」のランを異なるコンテキスト・モデルによってエンコードする。
【００２４】
このステップは、ステップ（１）と連結することができる。それにより、エンコードはシンボル系列を１パスだけでエンコードできる。また、デコーダはビット・ストリームを１パスでデコードできる。
【００２５】
上記の二つのステップの擬似コードは状態機械として表現できる。
0005536193.tif 000003
0005536193.tif 000004
0005536193.tif 000005
0005536193.tif 000006
実験結果：
0005536193.tif 000007
表２は前記の例のトポロジー・データの圧縮結果を掲げている。ここで、VLC符号化はハフマン符号が使われることを意味する。提案される方法は、上記の擬似コードに従って開発されている。
【００２６】
この表から、提案される方法は、既存の算術符号化に対して、圧縮率で6.4%〜47.1%の改善を達成できることが見て取れる。
【００２７】
二レベルでシンボルをエンコードする方法が提案される。
【００２８】
まず、いくつかのシンボルの何らかの組み合わせ（たとえばC…CR…R）を新しいシンボル（たとえばA）として扱い、新しいシンボルを既存の他のシンボルと一緒に（たとえばCRLESA）ある種のコンテキスト・モデル（たとえばコンテキスト・モデル０）によってエンコードする。
【００２９】
新しいシンボル（たとえばA）が現れる場合の第二レベル、該新しいシンボルに続いて、その対応するもとのシンボル組み合わせ（C…CR…R）が他のコンテキスト・モデル（たとえばコンテキスト・モデル2*i＋1、コンテキスト・モデル2*i＋2）の系列によってエンコードされる。
【００３０】
したがって、組み合わせ（たとえばCRCRCCRCRCRCRR…）におけるシンボルの「ラン」に存する冗長性が除去される。
【００３１】
エントロピー符号化方法はデータ圧縮における基本プロセスである。提案される方法は、実際上、たとえば伝送規格の定義のために使うことができる。
【００３２】
上記の例示的な実施形態は単に例解のためであって、いかなる仕方であれ保護が求められる本発明の精神および範囲を限定するものと解釈してはならないことは理解しておくべきである。本発明の範囲は請求項によってのみ定義される。
【００３３】
特に、本発明は、決して、空間的なデータに限定されるものではなく、たとえばファイル・データまたは測定データを含むあらゆる種類のデータに適用可能である。