(57)【要約】【課題】漸進三次元メッシュ情報の符号化方法及びその装置を提供する。【解決手段】(ａ) 三次元メッシュを一つ以上の段階別メッシュで構成する段階と、(ｂ)一つ以上の段階別メッシュを各々複数個の部分メッシュに分割する段階と、(ｃ)複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、一定の大きさ以下の部分メッシュを結合して全ての部分メッシュの大きさを所定の大きさ以上に再構成する段階と、(ｄ) 再構成された部分メッシュに対して各部分メッシュ内のメッシュ情報を所定の大きさのビットストリーム単位に分割して各々符号化する段階と、(ｅ) 符号化されたメッシュ情報を圧縮されたビットストリームに統合して伝送する段階とを具備する。【選択図】      図７
2006136020.tif 000002
【特許請求の範囲】
【請求項１】
３次元メッシュ情報を漸進的に復元できるように符号化する方法において、
(ａ) ３次元メッシュを複数個の部分メッシュで構成する段階と、
(ｂ) 前記複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、第１大きさ以下の部分メッシュを次の部分メッシュに統合して全ての部分メッシュの大きさを第１大きさ以上に再構成する段階と、
(ｃ) 再構成された部分メッシュに対して各部分メッシュ内のメッシュ情報を第２大きさのビットストリーム単位に分割してそれぞれ符号化する段階と、
(ｄ) 各々符号化された部分メッシュを圧縮されたビットストリームに統合して伝送する段階とを具備することを特徴とする漸進３次元メッシュ情報の符号化方法。
【請求項２】
前記各部分メッシュ単位より構成されたビットストリームは、各部分メッシュ内のメッシュ情報として頂点２進ツリー情報と三角形２進ツリー情報を具備し、
前記複数個の部分メッシュのビットストリームで一番最初に符号化する部分メッシュの頂点２進ツリー情報に部分メッシュの総個数情報が追加されることを特徴とする請求項１に記載の漸進３次元メッシュ情報の符号化方法。
【請求項３】
３次元メッシュ情報を漸進的に復元できるように符号化する方法において、
(ａ) ３次元メッシュを複数個の段階別メッシュで構成する段階と、
(ｂ) 前記複数個の段階別メッシュを各々複数個の部分メッシュに分割する段階と、
(ｃ) 前記複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、第１大きさ以下の部分メッシュを次の部分メッシュに統合して全ての部分メッシュの大きさを第１大きさ以上に再構成する段階と、
(ｄ) 再構成された部分メッシュに対して各部分メッシュ内のメッシュ情報を所定の第２大きさのビットストリーム単位で分割して各々符号化する段階と、
(ｅ) 符号化されたメッシュ情報を圧縮されたビットストリームに統合して伝送する段階とを具備することを特徴とする漸進３次元メッシュ情報の符号化方法。
【請求項４】
前記(ｃ)段階は、
一つの部分メッシュを構成する頂点２進ツリーでの頂点の総個数が基準頂点の個数より少なければ、次に符号化する部分メッシュと結合して、符号化する全ての部分メッシュが所定の第１基準頂点の個数より多くの頂点を有する頂点２進ツリーを有するように再構成することを特徴とする請求項３に記載の漸進３次元メッシュ情報の符号化方法。
【請求項５】
前記(ｄ)段階は、
前記各部分メッシュ内のメッシュ情報を構成する頂点２進ツリー情報及び三角形２進ツリー情報を、各々所定の第２基準頂点の個数及び所定の基準三角形の個数単位に分割して前記第２ビットストリーム単位で構成することを特徴とする請求項３または請求項４に記載の漸進３次元メッシュ情報の符号化方法。
【請求項６】
前記圧縮されたビットストリームは、
前記(ｃ)段階で再構成された部分メッシュの総個数と、
再構成された各部分メッシュを構成する頂点２進ツリーのヘッダ情報及び三角形２進ツリーのヘッダ情報と、
前記(ｄ)段階で所定大きさのビットストリーム単位に分割されて再構成された複数個の頂点２進ツリーの各ビットストリーム及び複数個の三角形２進ツリーの各ビットストリームとを含むことを特徴とする請求項３に記載の漸進３次元メッシュ情報の符号化方法。
【請求項７】
前記圧縮されたビットストリームは、
２進ツリーの分岐点から一定方向への連結性情報を提供するY-頂点情報をさらに含み、
前記Y-頂点情報は、前記再構成された各部分メッシュ内に存在するY-頂点の総個数及び前記Y-頂点の各々に対して三角形２進ツリーの分岐点から右側に位置したツリー内に存在する三角形の総個数で示すY-頂点の位置情報を具備し、
前記Y-頂点情報は、前記複数個の頂点２進ツリーのビットストリームまたは前記複数個の三角形２進ツリーのビットストリームに示されることを特徴とする請求項６に記載の漸進３次元メッシュ情報の符号化方法。
【請求項８】
前記圧縮されたビットストリームは、
２進ツリーの分岐点から一定方向への連結性情報を提供するY-頂点情報をさらに含み、
前記Y-頂点情報は、
前記再構成された各部分メッシュ内に存在するY-頂点の総個数、各頂点２進ツリーの分岐と端情報を示すシンボルに１ビットとして追加に示されるY-頂点の位置情報及び、Y-頂点の順序情報を２進ツリー形態で示すY-頂点の２進ツリー情報を含むことを特徴とする請求項６に記載の漸進３次元メッシュ情報の符号化方法。
【請求項９】
３次元メッシュ情報が漸進的に復元できるように符号化する方法において、
(ａ) ３次元メッシュを複数個の段階別メッシュで構成する段階と、
(ｂ) 前記複数個の段階別メッシュを各々複数個の部分メッシュに分割する段階と、
(ｃ) 各部分メッシュに三角形２進ツリーの分岐三角形から分岐されるブランチの符号化順序を示す方向性情報を追加して符号化する段階と、
(ｄ) 各々符号化された部分メッシュを圧縮されたビットストリームに統合して伝送する段階とを具備することを特徴とする漸進３次元メッシュ情報の符号化方法。
【請求項１０】
前記(ｃ)段階は、
(ｃ.１) 複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、第１大きさ以下の部分メッシュを次の部分メッシュと統合して全ての部分メッシュの大きさを所定の第１大きさ以上に再構成する小段階と、
(ｃ.２) 再構成された部分メッシュに対して各部分メッシュ内のメッシュ情報を所定の第２大きさのビットストリーム単位で分割する小段階と、
(ｃ.３) 前記ビットストリームに方向性情報を追加して符号化する小段階とを具備することを特徴とする請求項９に記載の漸進３次元メッシュ情報の符号化方法。
【請求項１１】
前記圧縮されたビットストリームは、
前記(ｃ.１)小段階で再構成された部分メッシュの総個数と、
再構成された各部分メッシュを構成する頂点２進ツリーのヘッダ情報及び三角形２進ツリーのヘッダ情報と、
前記(ｃ．２) 小段階で所定の第２大きさのビットストリーム単位に分割されて再構成された複数個の頂点２進ツリーの各ビットストリーム及び複数個の三角形2進ツリーの各ビットストリームを具備し、
前記複数個の三角形２進ツリーの各ビットストリームに方向性情報を含むことを特徴とする請求項１０に記載の漸進３次元メッシュ情報の符号化方法。
【請求項１２】
前記方向性情報は、
前記(ｃ.１)小段階で再構成された部分メッシュに対する三角形２進ツリーに含まれた分岐三角形で、２つのブランチの大きさ及び所定の基準三角形の個数を考慮して、いずれか１つのブランチに含まれた三角形の個数が前記基準三角形の個数に比べて大きい場合、相対的にブランチに含まれた三角形の個数が少ないもう１つのブランチ
が先に符号化されるように示されることを特徴とする請求項１０または請求項１１に記載の漸進３次元メッシュ情報の符号化方法。
【請求項１３】
前記(ｃ)段階は各部分メッシュ別に三角形２進ツリー情報を構成することにおいて、
前記三角形２進ツリーを構成する三角形の数をNとする時、N個のtrunとM(0≦M≦N)個のtleafをtmarching及びpolygonedge情報とは分離して構成することを特徴とする請求項９に記載の漸進３次元メッシュ情報の符号化方法。
【請求項１４】
３次元メッシュを複数個の部分メッシュに分割し、前記複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、第１大きさ以下の部分メッシュを次の部分メッシュに統合して全ての部分メッシュの大きさを第１大きさ以上に再構成する３次元データ分析部と、
前記再構成される部分メッシュ内のメッシュ情報を第２大きさのビットストリーム単位で各々符号化する複数個の部分別符号化部と、
各々符号化された部分メッシュを圧縮されたビットストリームに統合して伝送するマルチプレクサとを具備することを特徴とする漸進３次元メッシュ情報の符号化装置。
【請求項１５】
３次元メッシュを複数個の段階別メッシュで構成し、各段階別メッシュを複数個の部分メッシュに分割する３次元データ分割部と、
前記複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、第１大きさ以下の部分メッシュを次の部分メッシュと統合して全ての部分メッシュの大きさを所定の第１大きさ以上に再構成する３次元データ分類/結合部と、
再構成された部分メッシュに対して各部分メッシュ内のメッシュ情報を所定の第２大きさのビットストリーム単位で分割して各々符号化する複数個の部分別符号化部と、
各々符号化された部分メッシュを圧縮されたビットストリームに統合して伝送するマルチプレクサとを具備することを特徴とする漸進３次元メッシュ情報の符号化装置。
【請求項１６】
前記３次元データ分類/結合部は、
一つの部分メッシュを構成する頂点２進ツリーでの頂点の総個数が第１基準頂点の個数より少なければ、次に符号化する部分メッシュと結合して、符号化する全ての部分メッシュが第１基準頂点の個数より多くの頂点を有する頂点２進ツリーを有するように再構成することを特徴とする請求項１５に記載の漸進３次元メッシュ情報の符号化装置。
【請求項１７】
前記複数個の部分別符号化は、
前記各部分メッシュ内のメッシュ情報を構成する頂点２進ツリー情報及び三角形２進ツリー情報を各々所定の第２基準頂点の個数及び所定の基準三角形の個数単位に分割して、前記第２ビットストリーム単位で構成して各々符号化することを特徴とする請求項１５または請求項１６に記載の漸進３次元メッシュ情報の符号化装置。
【請求項１８】
３次元メッシュを複数個の段階別メッシュで構成し、各段階別メッシュを複数個の部分メッシュに分割する３次元データ分割部と、
前記複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、第１大きさ以下の部分メッシュを次の部分メッシュと統合して全ての部分メッシュの大きさを一定の大きさ以上に再構成する３次元データ分類/結合部と、
再構成された部分メッシュに対して各部分メッシュ内のメッシュ情報に前記メッシュ情報を構成する三角形２進ツリー情報から二つの方向に分岐される分岐三角形での符号化順序を示す方向性情報を追加する方向性情報決定部と、
再構成された部分メッシュに対して各部分メッシュ内のメッシュ情報を所定の大きさのビットストリーム単位で分割して各々符号化する複数個の部分別符号化部と、
各々符号化された部分メッシュを圧縮されたビットストリームに統合して伝送するマルチプレクサとを具備することを特徴とする漸進３次元メッシュ情報の符号化装置。
【請求項１９】
前記方向性情報決定部は、
前記複数個の部分別符号化部で、所定大きさのビットストリーム単位に分割されて再構成されたメッシュ情報に対する三角形２進ツリーで、分岐三角形での２つのブランチの大きさを考慮して、その小さいブランチが先に符号化されるように前記方向性情報を決定することを特徴とする請求項１８に記載の漸進３次元メッシュ情報の符号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は三次元メッシュ情報符号化に係り、特にMPEG-4 SNHC(Synthetic and Natural Hybrid Coding)分野とVRML(Virtual Reality Modeling Language)で使われている三次元メッシュデータに対してトポロジカルサーザリ(Topological Surgery)を用いた漸進三次元メッシュ情報の符号化方法及びその装置に関する。
【背景技術】
【０００２】
三次元メッシュよりなる三次元客体の伝送は、メッシュデータの効率的な符号化だけでなく、伝送されるメッシュデータの漸進復元が重要な必要条件として認識されている。漸進復元は、伝送途中で線路上のエラーによってメッシュデータに損失が発生した場合に、それ自体だけでなく、既に伝送されたメッシュデータだけによっても一部復元可能にすることによって、再伝送されるべきメッシュデータの量を最小化できる。このような線路エラーに対して強いという特徴のため、今後の無線通信または低伝送率通信等で効果的に使われうる技術と展望されている。
【０００３】
既存の三次元メッシュデータに対する符号化は、メッシュデータ全体に対して符号化しているため、符号化されたデータを伝送する際に全体のビットストリームを全て受ける前に一部のみ復元することがほとんど不可能であった。また、伝送時に発生する線路上のエラーにより極く一部のデータが損失されても、全体を再び受けなければならないという非効率が存在していた。その例として現在MPEG-4 SNHC三次元メッシュ符号化に技術として採択されているIBM社で提案された符号化方式が挙げられる(ISO/IEC JTC1/SC29/WG11 MPEG98/W2301、"MPEG-4 SNHC Verification Model 9.0")。
【０００４】
MPEG-SNHCではVRMLを基盤としてメッシュ符号化/復号化をデザインしている。VRMLでメッシュはIndexedFaceSetというノード型で記述される。メッシュデータをコーディングするための主な技術中の一つは、IBMのトポロジカルサーザリ技術である。この技術は与えられたメッシュを球と位相幾何学的に同一と仮定した後、与えられた切断エッジに沿ってメッシュを切ることによって2進ツリー構造の三角形スパングラフを形成している。この際メッシュを切るために定められた切断エッジは頂点(vertex)と頂点とをつなぐ形態に与えられ、これもまたループを有するツリー構造に与えられる。これを頂点スパングラフという。従ってこの二つのツリーを符号化/復号化すれば元のメッシュを損失することなしに再生できる。
【０００５】
MPEG4-SNHCでは、一つのVRMLファイルにはいくつかのIndexedFaceSetがありうるが、基本的に一つのIndexedFaceSetだけを基準として圧縮方法をテストする。しかし一つのIndexedFaceSetはいくつかのメッシュより構成されることができる。即ち、頂点と頂点との間が連結できる多角形の集合を一つの連結成分といえば、IndexedFaceSetはいくつかの連結成分より構成されることを許す。
【０００６】
一般に、グラフィックの速い処理のためにはモデリングされる単位が三角形で、この三角形がランダムに構成されることでない、ストリップやファンの形態に三角形相互間に連結されていることが望ましい。またシンボルが反復して表現されている程圧縮率は良い。IBMはこのような圧縮とグラフィックの処理という観点でメッシュをできるだけ一つの長い三角形ストリップで作る。
【０００７】
図１（Ａ）〜図１（Ｆ）はIBM社の三角形スパングラフを頂点スパングラフに沿って切って生成するトポロジカルサーザリ技術過程を示す。図１（Ａ）及び図１（Ｄ）はメッシュを太線で定義された切断エッジに沿って切る方法を示す。図１（Ｂ）は切断エッジの全体形態を示す。図１（Ｅ）は図１（Ｂ）に沿ってメッシュを切る時発生するエッジと頂点の構成形態を示す。図１（Ｃ）は切る基準点である頂点を連結して構成した頂点スパングラフを示す。図１（Ｆ）は頂点スパングラフに沿ってメッシュを切って一つの連結された三角形の集合であるストリップを定義した三角形スパングラフを示す。三角形スパングラフを図１（Ａ）〜図１（Ｆ）のような方法で生成すれば、一般に三角形スパングラフの分岐する二つのラン(run)中、一方向のランの長さは他方向のランの長さに比べてだいぶ短く表現されうる。
【０００８】
図２（Ａ）〜図２（Ｄ）は実際メッシュにトポロジカルサーザリ技術を適用した例を示す。一方、頂点スパングラフは一つのブランチからいくつかのブランチに分かれうるが、図３は頂点ランが再び以前の頂点中一つの位置に戻る形態、即ち、ループを有する頂点スパングラフの一例を示す。そして、一つのメッシュはいくつかの連結成分よりなり得、実際にはメッシュをなす構成成分当り図１（Ｃ）のような頂点スパングラフと図１（Ｆ）のような三角形スパングラフの対を生成する。一般に一つのIndexedFaceSetはいくつかの連結成分で構成されるので、一つのIndexedFaceSetをコーディングすればいくつかの三角形スパングラフと頂点スパングラフの対が得られる。
【０００９】
この方法で符号化されたデータを復元する方法は次のような順序で構成される。
１. 頂点スパングラフを用いてバウンドループを生成する。
２. 三角形スパングラフにおいて分岐する三角形の第三の頂点をY-頂点というが、三角形スパングラフのビットストリームを用いてY-頂点を計算する。
三角形スパングラフの三角形マーチングビットパターン(triangle marching bit pattern)を用いて三角形または多角形を生成する。IBM社が提示した方法は、頂点スパングラフと三角形スパングラフをエントロピー算術符号化方法を用いて無損失圧縮する。しかし、IBM社が提示した方法で元来の構造を再生成するためには、その構造を構成する全てのビットストリームが入力されるべきなので次のような短所を有する。
【００１０】
１. データのデコーディングのためには全てのビットストリームが入力される必要があるので、伝送中にエラーが発生した場合、全てのビットストリームを再伝送する必要がある。
２. 圧縮されたデータサイズが大きい場合、データが全て伝送されるには長時間がかかり、使用者はその時間だけ待機する必要がある。
【００１１】
既存技術の短所を克服するためには次のような点が解決されるべきである。
１. データ全体が入らなくても部分的に復元が可能で、エラーが発生した部分だけ再伝送することによってネットワークの負担と伝送時間を縮めることができるべきである。
２. データの一部分だけの復元が可能で、その一部分のデータによる三角形ないしは多角形が処理されてディスプレー上に示されうるべきである。
【００１２】
前記の二つの機能を既存のIBM社が提示した方法の基本構造上で提供するためには、まず図４で示したようなバウンドループとY-頂点を効率的に処理する方法からその性能差が発生する。図１（Ｆ）で番号１０、１４、１８に該当する点がY-頂点であって、このY-頂点は分岐する二つの三角形ランの中で少なくとも一方のランが全て処理されていてこそ計算できる。即ち、三角形ラン内に位置する三角形に対してはマーチングビットパターンとバウンドループによってその三角形の三つの頂点に対するインデックスが決定されうるが、分岐三角形の３番目の頂点であるY-頂点はつながる二つのラン中いずれか一ランに対する全てのビットストリームがあってこそそのインデックスが決定されうる。従って、分岐三角形につながるビットストリームが全て入るまでは分岐三角形以後のいかなる三角形も復元されてディスプレーできない。IBM社が提示した方法では全てのビットストリームが入力されていると仮定するのでこのような問題が発生しないが、復号化器に入力される順番で三角形を復元してディスプレーするためにはこのような問題が解決されるべきである。
【００１３】
既存のMPEG４で使用する三次元メッシュ情報符号化/復号化方式は図５と同様である。符号化部１０１に入力された三次元メッシュデータ１００は連結情報と幾何情報に分けられて、各々連結情報符号化器１０２と幾何情報符号化器１０３を用いて符号化される。この時、頂点構造に対する情報１０５は連結情報符号化器１０２から幾何情報符号化器１０３に伝えられる。連結情報符号化器１０２と幾何情報符号化器１０３から圧縮された結果として発生した情報は、再びエントロピー符号化器１０４を通じて圧縮されたビットストリーム１１１に置換される。
【００１４】
その後に圧縮されたビットストリーム１１１は再び復号化部１１４に入力される。圧縮されたビットストリーム１１１はエントロピー復号化器１０６を経て連結情報及び幾何情報に分けられ、この情報に対する復号は連結情報復号化器１０７と幾何情報復号化器１０８で各々遂行される。符号化部１０１と同じように頂点構造に対する情報１０９が連結情報復号化器１０７から幾何情報復号化器１０８に伝えられる。復号化された連結情報と幾何情報を用いて復元された三次元メッシュ１１０が構成できる。
【００１５】
また、選択的に色相情報、法線情報及びテクスチャー座標などの画像情報は画像情報符号化器１１２を通じて符号化され、画像情報復号化器１１３により復号化される。
図５に示したように、一つの三次元メッシュは通信上で圧縮されたビットストリームの形態で伝送される。しかし、既存のMPEGデータ圧縮方式はエントロピー符号化器１０４を使用するので通信路で発生する伝送エラーに対して脆弱だといえる。
【００１６】
以下、３次元メッシュ符号化方法で用いられる用語を整理する。
◆ VRML- Virtual Reality Modeling Language、インターネットで仮想空間を記述し、伝送するために作られたグラフィック標準フォーマットである。
◆ MPEG- Moving Picture Expert Group、ビデオなどの多様なメディアの伝送のための圧縮フォーマットを標準化するための国際標準化活動である。
【００１７】
◆ メッシュ- 客体をいくつかの多角形より構成して表現したことである。
◆ ノード- 頂点スパングラフで一つの頂点、またはVRMLで使用する描写の最小単位である。
◆ トポロジカルサーザリ- メッシュを三角形のストリップ形態に作るために与えられた経路に沿ってメッシュを切るIBM社のメッシュコーディングのための方法である。
【００１８】
◆ 頂点スパングラフ- トポロジカルサーザリでメッシュを切る経路である。
◆ 三角形スパングラフ- トポロジカルサーザリで頂点スパングラフに沿って切った際現れる三角形ストリップであって、２進ツリー構造である。
◆ vlast- vlastは現在のランがブランチの中で最後のブランチかどうかを示す。ブランチの中で最後であれば１、そうでなければ０を付与する。
【００１９】
◆ vrun- 連結された頂点の集合であって、ブランチ(branch)や葉(leaf)に終わる。
◆ vleaf- 現在のvrunの終了が葉に終わるか分岐ノードに終わるかを示す。葉に終われば１、でなければ０の値が付与される。
◆ loopstart- 頂点ランの中で一部は葉が再び他の頂点ランに会う場合が発生するが、その場合の開始を示す。
【００２０】
◆ loopend- 頂点ランの葉がループを形成する場合、その端点を示す。
◆ loopmap- loopstartとloopendの相互連関性を示す。loopendからloopstartへのエッジを関連づけるインデックスの集合である。
◆ trun- 連続される三角形の集合であって、その終了はleaf三角形または分岐する三角形よりなる。
【００２１】
◆ tleaf- 三角形のランがleaf三角形に終わるか、分岐する三角形に終わるかを示す。leaf三角形であれば１、そうでなくて分岐する三角形であれば０の値が付与される。
◆ tmarching- 三角形の前進様子を記述する。ストリップから右側境界にエッジを有すれば１、左側境界にエッジを有すれば０の値が付与される。
◆ ispolygonedge- 現在のエッジが元来のメッシュモデルから与えられたモデルか、でなければ多角形を三角形の集合で表現するために入れたエッジかどうかを示す。元来与えられたエッジであれば１、そうでなければ０が付与される。
【発明の開示】
【発明が解決しようとする課題】
【００２２】
本発明が解決しようとする技術的課題は、部分メッシュを処理単位としてビットストリームを再構成することによって、漸進三次元メッシュの復元と段階別区分を可能にし、頂点２進ツリーと三角形２進ツリー情報を用いることによって一つの三角形単位でメッシュの再現を可能にする、トポロジカルサーザリを用いた漸進三次元メッシュ情報の符号化方法及びその装置を提供することにある。
【課題を解決するための手段】
【００２３】
前記課題を達成するために、本発明に係る三次元メッシュ情報を漸進的に復元できるように符号化する方法の一実施例は、(ａ) 三次元メッシュを一つ以上の段階別メッシュで構成する段階と、(ｂ) 前記一つ以上の段階別メッシュを各々複数個の部分メッシュに分割する段階と、(ｃ) 前記複数個の部分メッシュを各部分メッシュ単位でビットストリームを構成して各々符号化する段階と、(ｄ) 各々符号化された部分メッシュを圧縮されたビットストリームに統合して伝送する段階とを具備する。
【００２４】
また、前記課題を達成するために、本発明に係る三次元メッシュ情報を漸進的に復元できるように符号化する方法の他の実施例は、(ａ) 三次元メッシュを一つ以上の段階別メッシュで構成する段階と、(ｂ) 前記一つ以上の段階別メッシュを各々複数個の部分メッシュに分割する段階と、(ｃ) 前記複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、一定の大きさ以下の部分メッシュを結合して全ての部分メッシュの大きさを所定の大きさ以上に再構成する段階と、(ｄ) 再構成された部分メッシュに対して各部分メッシュ内のメッシュ情報を所定の大きさのビットストリーム単位で分割して各々符号化する段階と、(ｅ) 符号化されたメッシュ情報を圧縮されたビットストリームに統合して伝送する段階とを具備する。
【００２５】
また、前記課題を達成するために、本発明に係る三次元メッシュ情報を漸進的に復元できるように符号化する方法の他の実施例は、(ａ) 三次元メッシュを一つ以上の段階別メッシュで構成する段階と、(ｂ) 前記一つ以上の段階別メッシュを各々複数個の部分メッシュに分割する段階と、(ｃ) 各部分メッシュに三角形２進ツリーの分岐三角形から分岐されるブランチの符号化順序を示す方向性情報を追加して符号化する段階と、(ｄ) 各々符号化された部分メッシュを圧縮されたビットストリームに統合して伝送する段階とを具備する。
【００２６】
また、前記課題を達成するために、本発明に係る漸進三次元メッシュ情報の符号化装置の一実施例は、三次元メッシュを一つ以上の段階別メッシュで構成し、各段階別メッシュを複数個の部分メッシュに分割して分類する三次元データ分析部と、前記複数個の部分メッシュを各部分メッシュ単位でビットストリームを構成して各々符号化する複数個の部分別符号化部と、各々符号化された部分メッシュを圧縮されたビットストリームに統合して伝送するマルチプレクサとを具備する。
【００２７】
また、前記課題を達成するために、本発明に係る漸進三次元メッシュ情報の符号化装置の他の実施例は、三次元メッシュを一つ以上の段階別メッシュで構成し、各段階別メッシュを複数個の部分メッシュに分割する三次元データ分割部と、前記複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、一定の大きさ以下の部分メッシュを結合して全ての部分メッシュの大きさを一定の大きさ以上に再構成する三次元データ分類/結合部と、再構成された部分メッシュに対して各部分メッシュ内のメッシュ情報を所定の大きさのビットストリーム単位で分割して各々符号化する複数個の部分別符号化部と、各々符号化された部分メッシュを圧縮されたビットストリームに統合して伝送するマルチプレクサとを具備する。
【００２８】
また、前記課題を達成するために、本発明に係る漸進三次元メッシュ情報の符号化装置のさらに他の実施例は、三次元メッシュを一つ以上の段階別メッシュで構成し、各段階別メッシュを複数個の部分メッシュに分割する三次元データ分割部と、前記複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、一定の大きさ以下の部分メッシュを結合して全ての部分メッシュの大きさを一定の大きさ以上に再構成する三次元データ分類/結合部と、再構成された部分メッシュに対して各部分メッシュ内のメッシュ情報に前記メッシュ情報を構成する三角形２進ツリー情報から二つの方向に分岐される分岐三角形での符号化順序を示す方向性情報を追加する方向性情報決定部と、再構成された部分メッシュに対して各部分メッシュ内のメッシュ情報を所定の大きさのビットストリーム単位で分割して各々符号化する複数個の部分別符号化部と、各々符号化された部分メッシュを圧縮されたビットストリームに統合して伝送するマルチプレクサとを具備する。
【発明を実施するための最良の形態】
【００２９】
以下、添付した図面を参照して本発明の望ましい実施例に対して詳細に説明する。
まず漸進三次元メッシュの処理のために本発明では新たなメッシュ構造を提案する。三次元メッシュ(Mesh Object: MO)はメッシュの情報をいろいろな段階で分類した段階別メッシュ(Mesh Object Layer: MOL)より構成されうる。この時、各MOLは一つまたはそれ以上の部分メッシュ(MCOM:Mesh COMponent)を含む。一つのMCOMは自らの復元に必要な連結情報、幾何情報、そして画像情報を含む。即ち、MOは符号化する三次元メッシュ客体単位で定義され、このメッシュ情報の多様な画質と機能側面に従っていろいろな段階で分類し、この分類された各段階を段階別メッシュMOLで定義する。合わせて位相幾何学的サーザリ方法を用いて一つの三次元メッシュ客体を相互連結性のないいろいろな独立したメッシュ情報(即ち、連結成分)より構成した時、符号化するデータの大きさやその他の特性に従って相互独立したメッシュ情報を統合したり分割して構成したものを部分メッシュと定義する。
【００３０】
図６は本発明に係る漸進三次元メッシュ情報符号化/復号化方式を概念的に示すブロック図である。図６によれば、符号化部２００は三次元データ分析器２０１、複数個の部分別符号化器１〜Ｎ２０２及びマルチプレクサ(MUX)２０４を具備し、復号化部２０９はデマルチプレクサ(DEMUX)２０５、複数個の部分別復号化器１〜Ｎ２０６及び三次元データ合成器２０８を具備する。
【００３１】
まず、三次元メッシュ１００がデータ分析器２０１で一つ以上の段階別メッシュより再構成され、各段階別メッシュMOLは再び部分メッシュMCOMより再構成される。段階別メッシュMOLまたは部分メッシュMCOMは部分別符号化器１〜Ｎ２０２に入力され、この符号化器１〜Ｎ２０２を通じて圧縮され、圧縮されたビットストリームはMUX２０４を通じて伝送される。この時、既に符号化が遂行された上位符号化器から生成された情報２０３はまだ符号化が遂行されない下位符号化器で使われる。
【００３２】
復号化部２０９に伝送されたビットストリームはデマルチプレクサ２０５を通じて各段階別メッシュMOLに分類され、再び部分メッシュMCOMに分類されて部分別復号化器１〜Ｎ２０６を通して復号化される。この時、既に遂行された復号化器で生成された情報２０７はまだ遂行されない復号化器で再使用される。復号化された部分メッシュ(MCOM)はデータ合成器２０８を通して三次元メッシュ１１０に復元される。
【００３３】
いくつかの頂点で表示された多角形よりなる三次元メッシュを三つの頂点を有する三角形メッシュより構成する場合に、各頂点とそれに対応する三角形の構成情報-幾何及び連結情報-を符号化する三次元メッシュ情報符号化方法に漸進符号化機能を付与した方法を以下で具体的に説明する。
図７は本発明に係るトポロジカルサーザリを用いた漸進三次元メッシュ情報符号化部の望ましい実施例であって、部分メッシュ単位による漸進符号化を遂行する場合の構成を具体的に示すブロック図である。
【００３４】
三次元メッシュデータ分析器７１０は符号化する三次元メッシュ７００を入力し、これを相互連結情報の必要なく相互独立的に構成できる三次元２進メッシュツリーを含む複数個の三次元部分メッシュに分割する(７１１段階)。このように分割された各部分メッシュ７２０はメッシュツリーの深度とノード数に従ってその大きさが変わる。各部分メッシュ単位で構成されたビットストリーム７３０は各部分メッシュ内のメッシュ情報であって、頂点２進ツリー情報７３２と三角形２進ツリー情報７３４を具備する。この時、一つの部分メッシュを構成する頂点２進ツリーと三角形２進ツリーは符号化器７４０、７４２により圧縮及び符号化が遂行される。次に、マルチプレクサ７５０が符号化された部分メッシュを圧縮されたビットストリームに統合して伝送する。
【００３５】
図８は本発明に係るトポロジカルサーザリを用いた漸進三次元メッシュ情報符号化方法の望ましい一実施例のための文法を示す。複数個の部分メッシュのビットストリームで最初に符号化する部分メッシュC1の頂点２進ツリーのヘッダ情報８０２に、符号化する三次元メッシュ内に存在する全ての部分メッシュの総個数(nComponents)８０１が追加で表示される。全ての各部分メッシュC1〜CNの構成要素である頂点２進ツリー７３２と三角形２進ツリー７３４を復号化部で復元するために、ツリーの構成情報を有するヘッダ情報８０２、８０４と、各ツリー別圧縮化/符号化されたビットストリーム８０３、８０５が伝送される。
【００３６】
部分メッシュ単位で漸進符号化を遂行する場合に、符号化複雑度は低めうるが、符号化効率及び伝送エラーによる再復元効率は低くなる短所を有する。
一方、符号化効率が要求される応用分野に前述した部分メッシュ単位の漸進符号化方法を適用すれば、段階別メッシュMOLを構成する部分メッシュが少さなサイズで多数存在する場合に、実際符号化する情報量よりヘッダ情報量がさらに大きくなって全体符号化効率が低下する問題点が発生する恐れがある。従って、三次元データ分析段階で小さなサイズで構成された部分メッシュを、制限された伝送路の容量や復号化器の貯蔵容量に合わせて一つの単一部分メッシュに結合する処理過程が要求される。
【００３７】
図９は本発明に係るトポロジカルサーザリを用いた漸進三次元メッシュ情報符号化部の望ましい他の実施例であって、部分メッシュ内で連結情報を有する均等サイズのビットストリームを構成する漸進符号化を遂行する場合の構成を具体的に示すブロック図である。
図９によれば、三次元メッシュデータ分析器９０１は入力された三次元メッシュ９００を複数個の部分メッシュ９０２に分割する。次に、複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し(９０３段階)、一定の大きさ以下の部分メッシュを結合して(９０４段階)、全ての部分メッシュが所定の大きさ以上になるように再構成する。次に、再構成された部分メッシュに対して各部分メッシュ内のメッシュ情報９０８、９１０を所定の大きさのビットストリーム単位９０９、９１１に分割し、各々符号化器９１２、９１３により符号化する。次に、各々符号化された部分メッシュを圧縮されたビットストリームに統合してマルチプレクサ９１４を通じて伝送する。
【００３８】
ここで、部分メッシュ間の結合９０４は、前述したように部分メッシュが相互連結性のない独立的な構造を有しているので、単純に各部分メッシュ内にあるツリーをルート情報に従って連結する方法で処理できる。このような方法で所定の大きさを満足するように各部分メッシュを再構成した後、制限された伝送路の容量や復号化器の貯蔵容量特性を考慮して各部分メッシュの三次元メッシュ情報を特定の大きさに分割する過程を遂行する。これに従って、エラーを有するビットストリームをさらに効率的に再び伝送し復元できる。
【００３９】
本発明では基準頂点の個数と基準三角形の個数を用いて部分メッシュ内の三次元メッシュ情報を特定の大きさに分割する方法を使用する。
まず、部分メッシュ間の結合段階で、一つの部分メッシュを構成する頂点２進ツリーでの頂点の総個数が基準頂点の個数より少なければ、一つの部分メッシュを次に符号化する部分メッシュと結合させる(９０４段階)。これに従って、符号化する全ての部分メッシュが基準頂点の個数より多くの頂点を有する頂点２進ツリーを有するように再構成される。
【００４０】
このように再構成されれば、各部分メッシュ内のメッシュ情報を構成する頂点２進ツリー情報及び三角形２進ツリー情報を、各々基準頂点の個数の大きさ単位及び基準三角形の個数の大きさ単位に分割する。この時、一定の方向性(例えば、逆時計回り方向)を有して各ツリーに沿って各々分割させる(９０９、９１１段階)。
このような方法で分割された三次元メッシュ情報は９１２と９１３のように構成された符号化器を通じて圧縮化/符号化されるが、この時復号化器に送られる圧縮されたビットストリームは図１０のように構成される。図９の結合過程９０４により再構成された部分メッシュC1〜CNの総個数１０１０と、再構成された各部分メッシュを構成する頂点２進ツリーV1〜VNのヘッダ情報及び三角形２進ツリーV1〜VNのヘッダ情報１０１１、１０１４、１０１７、１０２０は図８と同一に構成される。各部分メッシュ内で分割された三次元メッシュ情報は１０１３、１０１６、１０１９、１０２２のように構成される。即ち、分割過程により所定の大きさのビットストリーム単位に分割されて再構成された三次元メッシュ情報は、複数個の頂点２進ツリーV1、1〜V1、n1、...、VN、1〜VN、nNの各々のビットストリーム及び複数個の三角形２進ツリーT1、1〜T1、m1、...、TN、1〜TN、mNの各々のビットストリームよりなる。ここでN、m、nは各々１以上の整数である。
【００４１】
かつ、一定の大きさ単位に伝送して漸進レンダリングを支援するために、三角形２進ツリーの構成情報の中でＮ個の三角形を構成するためのビットストリームはローカルエントロピーの符号化効率を考慮して構成される。例えば、Ｎ個のtrunデータと１個のtleafデータはＮ-1個のtmarchingとＮ個のpolygonedge情報と分離して構成される。これに従って、エントロピー符号化効率が向上し、レンダリング効果も向上できる。
【００４２】
一方、このように部分メッシュ内の三次元メッシュ情報を特定大きさに分割して符号化する場合に、復号化器の側面から考慮すべき情報が発生する。復号化器で分割された三次元メッシュビットストリームの一部を伝送されて漸進的に復元しながらレンダリングさせる時、復元されるツリーの方向が一定方向にだけ固定されていて問題が発生する恐れがある。復元過程で、三角形２進ツリー内で分岐する位置にある三角形の右側と左側方向に接する三角形の全てが共有する一つの頂点であるY-頂点に会う場合に、右側方向にある三角形２進ツリーの構成情報が分からないので、伝送されない三次元メッシュ情報を全て得るまでレンダリングはこれ以上出来なくなる。従って、漸進符号化に対応して漸進復号化がうまくなされない問題が発生する。
【００４３】
これに、漸進的に三次元メッシュ情報を符号化/復号化するために、２進ツリーの分岐点から一定方向への連結性情報、即ち、本発明では右側ツリーへの連結性情報が提供できるY-頂点情報を、参照番号１０１２、１０１５、１０１８、１０２１のような形態でビットストリーム内にさらに含めて復号化器へ伝送すべきである。
これを解決するための最初の方法は、図１１のように頂点２進ツリーと三角形２進ツリーでY-頂点情報を生成することである。図１１で頂点２進ツリーのY-頂点情報及び三角形２進ツリーのY-頂点情報は、再構成された各部分メッシュ内に存在する各Y-頂点の総個数１０３１、１０３３、各Y-頂点に対して三角形２進ツリーの分岐点から右側に位置するツリー内に存在する三角形の総個数で示すY-頂点の位置情報１０３２、１０３４を整数形態に具備する。このようなY-頂点情報は、複数個の頂点２進ツリーのビットストリームまたは複数個の三角形２進ツリーのビットストリームに追加で示される。即ち、図１０で参照番号１０１２、１０１８及び参照番号１０１５、１０２１中いずれか一側情報だけをビットストリーム内に追加させる形態になる。
【００４４】
２番目の方法は最初の方法に比べてビット量を減らしてY-頂点情報が伝送できる方法である。図１２のY-頂点生成表に示したように、頂点２進ツリーの分岐と端情報を示すシンボルにY-頂点の位置情報が追加されて示される。頂点２進ツリーで(vrun==１&&vleaf==０)であればツリーの分岐点を、(vrun==１&&vleaf==１)であれば端点を示す。図１２はY-頂点(==１)が現れればvrunを１と示し、vleafは分岐点とか端点の場合を除いては0と示し、Y-頂点の発生有無及びvrunの個数を用いて位置情報を共に提供する。この時、Y-頂点の個数は参照番号１０１２、１０１８のように各部分メッシュ毎に整数値で示される。これに従って、頂点２進ツリー情報で変更されるビットストリーム形態は図１３及び図１４と同一である。
【００４５】
一方、三角形２進ツリーでは分割されて復号化器に伝送される三次元メッシュ情報の単位順序に従ってY-頂点の順序情報を図１５に例示された２進ツリーとして生成する。このように２進ツリー形態で示す２進ツリー情報は一連の０と１のリスト形態よりなり、(2*Y−vertex数＋１)個のビットが発生される。即ち、図１５に例示された２進ツリーによれば"11110011100000"が生成され、このように構成された２進ツリー情報が符号化器を通じて圧縮化/符号化されて符号化効率をさらに高められる。
【００４６】
要するに、図１３に示したように再構成された各部分メッシュ内に存在するY-頂点の個数が、複数個の頂点２進ツリーのビットストリーム１０１３、１０１９に対してY-頂点情報として参照番号１０１２、１０１８のように追加で示される。また、図１４に示したようにY-頂点の位置情報１０４７が、複数個の頂点２進ツリーの各ビットストリームで各頂点２進ツリーの分岐と端情報を示すシンボル１０４５、１０４６に追加で示される。
【００４７】
三角形２進ツリーに対するY-頂点情報として、Y-頂点の順序情報を２進ツリー形態で示すY-頂点の２進ツリー情報が複数個の三角形２進ツリーのビットストリーム１０１６、１０２２に対して参照番号１０１５、１０２１のように追加で示される。
いままで説明したように部分メッシュ内の三次元メッシュ情報を特定の大きさに分割し、合わせてレンダリングのためにY-頂点の連結性情報を共に構成して符号化する漸進符号化方法は、Y-頂点の位置情報と順序情報を追加することによって符号化効率の低下をもたらす恐れがある。このように漸進符号化方法で連結性情報の追加発生は、一定に決まった方向にだけツリーが構成され、これを一定の方向性に従って符号化する方式からもたらされる問題である。これは分割された三次元メッシュ情報でY-頂点に会った時、連結性情報が必要ないとか最小化される方向に符号化方向を適応的に可変させることによって解決できる。
【００４８】
図１６〜図１９は本発明に係るトポロジカルサーザリを用いた漸進三次元メッシュ情報符号化方法の望ましいさらに他の実施例のための文法であって、部分メッシュ内で方向性を有する均等な大きさのビットストリームを構成する漸進符号化方法を示す。
図１７のように三角形２進ツリーで二つの方向に分岐するY-頂点を有する三角形に会った時(１１１１段階)、部分メッシュ内の三角形２進ツリーを特定の大きさ単位に均等分割する時使用した基準三角形個数と、右側ブランチにある三角形２進ツリーに対する符号化優先順位を基準として三角形２進ツリーの符号化順序を順次に決定する。これに従う符号化方向を図１６のように三角形２進ツリービットストリームに方向性表示子(torientation)１１００を含めて示させる。torientationは復号化器で三角形２進ツリーが二つの方向に分岐される場合、左側ブランチに位置した三角形ツリーを先に処理するように０を示し、右側ブランチに位置した三角形ツリーを先に処理するように１を示す。
【００４９】
例えば、Y-頂点を有する三角形に会った時(１１１１段階)、まず右側ブランチにある三角形２進ツリーの三角形の個数(triangles＿per＿right＿tree)が基準三角形の個数(triangles＿per＿data)と同じかまたはそれより少ないかを判断して(１１１２段階)、そうであればtorientationを１と示す(１１１３段階)。そうでなければ、左側ブランチにある三角形２進ツリーの三角形の個数(triangles＿per＿left＿tree)がtriangles＿per＿dataと同じかまたはそれより少ないかを判断して(１１１４段階)、そうであればtorientationを０と示す(１１１５段階)。そうでなければtriangles＿per＿right＿treeがtriangles＿per＿left＿treeより少ないかを判断して(１１１６段階)、そうであればtorientationを１と示し(１１１７段階)、そうでなければ０と示す(１１１８段階)。
【００５０】
ここで、torientation＝０は、ルートが上側にある状態で三角形２進ツリーが二つの方向に分岐される場合に左側方向(逆時計回り方向)のブランチに位置した従属三角形ツリーをまず符号化することを意味し、torientation＝１は右側方向(時計方向)のブランチに位置した従属三角形ツリーをまず符号化するとことを意味する。一方、符号化方向性が決定された従属三角形ツリー内ではY-頂点を有する三角形に再び会っても符号化方向を示さない。このような符号化方向性決定方法に従って、方向性表示子を生成する過程の一例を図１８のように示す。
【００５１】
図１８で１１２０と１１２１は既に方向性表示子が決定された従属三角形ツリー内に位置したY-頂点を有する三角形であるので、方向性表示子が定義されない。１１２５は三次元メッシュ情報の圧縮されたビットストリームを伝送する順序及びレンダリングする順序を復号化器に報知する。
図１９は本発明の望ましいさらに他の実施例に係る圧縮されたビットストリームであって、方向性情報を有するビットストリームの構成図である。圧縮されたビットストリームは図１０と同じように再構成された部分メッシュの総個数１１３０、各部分メッシュを構成する頂点２進ツリーのヘッダ情報１１３１、１１２５及び三角形２進ツリーのヘッダ情報１１３３、１１３７及び所定大きさのビットストリーム単位に分割されて再構成された複数個の頂点２進ツリーの各ビットストリーム１１３２、１１３６及び複数個の三角形２進ツリーの各ビットストリーム１１３４、１１３８を具備する。付加的に、複数個の三角形２進ツリーの各ビットストリームTi、jに、三角形２進ツリーで二つの方向に分岐される分岐三角形での符号化順序を示す方向性情報１１００をさらに含む。
【００５２】
復号化器で方向性表示子の表示情報有無は、従属三角形ツリー内で全ての端三角形が復元されたかどうかを検査する方法で分かる。即ち、従属三角形ツリー内で端三角形の総数は、方向性表示を有する三角形と、方向性表示がなくてY-頂点を有する三角形の総数と同じだという特性を判別条件として使用してこれを判別する。
一方、三角形ツリーの構成要素の中で三角形の前進様子を定義するtmarching情報は重複性がほとんどなくてエントロピー符号化効率が低い。従って、本発明では上記のように特定の大きさ単位で三次元メッシュのビットストリームを構成する時、構成単位内のtmarching情報の符号化エントロピーを高め、漸進レンダリングをより効率的に支援するために、重複性の高いシンボルと重複性の低いシンボルを分離して三角形ツリーのビットストリームを構成することによって符号化効率を向上させる。即ち、N個の三角形を構成するためにN個のtrunとM(０≦M≦N)個(Mは、三角形２進ツリーを構成するブランチと葉の個数である)のtleafをN-M個のtmarchingとN個のpolygonedge情報単位とは分離して構成することによってtmarchingとtrun情報の低いエントロピー符号化効率を向上させ、レンダリング効率も向上できるようにする。図２０は一般的な方法に従ってビットストリームを構成した例であり、図２１は本発明で提案した方法より構成したビットストリームを示す。図２１でtleafはtrun＝1の場合、即ち、分岐三角形の場合にだけtrunの次に発生する。tmarchingは分岐三角形でない場合、即ちtrun＝０の場合にだけ発生する。そしてispolygonedgeは三角形でない多角形が少なくとも一つ以上存在する場合にだけ発生し、これを満足しない場合にはこの情報はビットストリーム内に構成させない。
【産業上の利用可能性】
【００５３】
以上、説明したように、本発明に係るトポロジカルサーザリを用いた漸進三次元メッシュ情報の符号化方法及びその装置は、既存のトポロジカルサーザリ方式で支援されなかった漸進メッシュの復元と段階別区分を可能にし、既存の方式を用いる場合に全体のビットストリームを全て伝送エラーなしに受ける前には復元が始まられなかったが、本発明は部分メッシュ単位のビットストリームが伝送されれば連結情報の頂点２進ツリーと三角形２進ツリー情報を用いて部分ッシュ単位でメッシュの再現を可能にする。従って、既存の方式は全体遅延が全体ビットストリームが全て伝送された時までであれば、本発明は全体遅延が一つの部分メッシュの長さに該当し、一つの部分メッシュが全て伝送される前にも頂点２進ツリー等核心情報が到達すればその以後には三角形単位の復元ができる。伝送時発生する伝送エラーに対しても部分メッシュ単位でビットストリームが生成された状態でエラーの局所化ができる。
【図面の簡単な説明】
【００５４】
【図１】図1Ａ乃至図1Ｆは三角形メッシュの一例に対する頂点スパングラフと三角形スパングラフの生成方法を示すことである。
【図２】図２Ａ乃至図２Ｄはトポロジカルサーザリ技術の適用例を示すことである。
【図３】ループを有する頂点スパングラフの一例を示すことである。
【図４】バウンドループの構成方法を示すことである。
【図５】従来の三次元メッシュ情報符号化/復号化方式を概念的に示すブロック図である。
【図６】本発明に係る漸進三次元メッシュ情報符号化/復号化方式を概念的に示すブロック図である。
【図７】本発明に係る漸進三次元メッシュ情報符号化装置の望ましい実施例に従う構成を示すブロック図である。
【図８】図７に示した符号化装置に従う漸進三次元メッシュ情報符号化方法の望ましい一実施例を説明するための文法の一例を示す。
【図９】本発明に係る漸進三次元メッシュ情報符号化装置の望ましい他の実施例に従う構成を示すブロック図である。
【図１０】図９に示した符号化装置に従う漸進三次元メッシュ情報の符号化方法の望ましい他の実施例を説明するための文法の一例を示す。
【図１１】図９に示した符号化装置に従う漸進三次元メッシュ情報の符号化方法の望ましい他の実施例を説明するための文法の一例を示す。
【図１２】図９に示した符号化装置に従う漸進三次元メッシュ情報の符号化方法の望ましい他の実施例を説明するための文法の一例を示す。
【図１３】図９に示した符号化装置に従う漸進三次元メッシュ情報の符号化方法の望ましい他の実施例を説明するための文法の一例を示す。
【図１４】図９に示した符号化装置に従う漸進三次元メッシュ情報の符号化方法の望ましい他の実施例を説明するための文法の一例を示す。
【図１５】図９に示した符号化装置に従う漸進三次元メッシュ情報の符号化方法の望ましい他の実施例を説明するための文法の一例を示す。
【図１６】本発明に係る漸進三次元メッシュ情報符号化方法の望ましいさらに他の実施例を説明するための文法の一例を示す。
【図１７】本発明に係る漸進三次元メッシュ情報符号化方法の望ましいさらに他の実施例を説明するための文法の一例を示す。
【図１８】本発明に係る漸進三次元メッシュ情報符号化方法の望ましいさらに他の実施例を説明するための文法の一例を示す。
【図１９】本発明に係る漸進三次元メッシュ情報符号化方法の望ましいさらに他の実施例を説明するための文法の一例を示す。
【図２０】本発明に係る三角形２進ツリー情報のビットストリーム構成方法を説明するための文法の一例を示す。
【図２１】本発明に係る三角形２進ツリー情報のビットストリーム構成方法を説明ｓるための文法の一例を示す。
【符号の説明】
【００５５】
７００  三次元メッシュ
７１０  三次元メッシュデータ分析器
７３０  ビットストリーム
７３２  頂点２進ツリー情報
７３４  三角形２進ツリー情報
７４０、７４２  符号化器
７５０  マルチプレクサ
【図１】
2006136020.tif 000003
【図２】
2006136020.tif 000004
【図３】
2006136020.tif 000005
【図４】
2006136020.tif 000006
【図５】
2006136020.tif 000007
【図６】
2006136020.tif 000008
【図７】
2006136020.tif 000009
【図８】
2006136020.tif 000010
【図９】
2006136020.tif 000011
【図１０】
2006136020.tif 000012
【図１１】
2006136020.tif 000013
【図１２】
2006136020.tif 000014
【図１３】
2006136020.tif 000015
【図１４】
2006136020.tif 000016
【図１５】
2006136020.tif 000017
【図１６】
2006136020.tif 000018
【図１７】
2006136020.tif 000019
【図１８】
2006136020.tif 000020
【図１９】
2006136020.tif 000021
【図２０】
2006136020.tif 000022
【図２１】
2006136020.tif 000023