(57)【特許請求の範囲】
【請求項１】
トポロジカルサーザリを通じた幾何学的構成により１つの３次元メッシュ客体を三角形ストリップで構成する際の３次元メッシュ情報のプログレッシブ符号化方法であって、
（ａ）前記３次元メッシュ客体に対する三角形ストリップを、符号化するデータのサイズに基づいて複数個の部分メッシュに分割するステップと、
（ｂ）前記複数個の部分メッシュをそれぞれ符号化するステップと、
（ｃ）複数個の符号化済みの部分メッシュを圧縮されたビットストリームに組み合わせて伝送するステップとを備えることを特徴とする３次元メッシュ情報のプログレッシブ符号化方法。
【請求項２】
トポロジカルサーザリを通じた幾何学的構成により１つの３次元メッシュ客体を三角形ストリップで構成する際の３次元メッシュ情報を、符号化するデータのサイズに基づいて複数個の部分メッシュに分割し、この複数個の部分メッシュをそれぞれ符号化して圧縮されたビットストリームに組み合わせて伝送するプログレッシブ符号化方法により符号化され伝送されたビットストリームのプログレッシブ復号化方法において、
（ａ）前記伝送されたビットストリームを複数個の符号化済みの部分メッシュに分割するステップと、
（ｂ）前記複数個の符号化済みの部分メッシュをそれぞれ復号化するステップと、
（ｃ）複数個の復号化済みの部分メッシュを合成して、３次元メッシュを復元するステップとを備えることを特徴とする３次元メッシュ情報のプログレッシブ復号化方法。
【請求項３】
トポロジカルサーザリを通じた幾何学的構成により１つの３次元メッシュ客体を三角形ストリップで構成する際の３次元メッシュ情報のプログレッシブ符号化装置であって、
３次元メッシュ客体が入力され、入力された３次元メッシュ客体に対する三角形ストリップを、符号化するデータのサイズに基づいて複数個の部分メッシュに分割する３次元データ分析部と、
前記複数個の部分メッシュをそれぞれ符号化する複数個の部分別符号化部と、
複数個の符号化済みの部分メッシュを圧縮されたビットストリームに組み合わせて伝送するマルチプレクサと、
を備えることを特徴とする３次元メッシュ情報のプログレッシブ符号化装置。
【請求項４】
トポロジカルサーザリを通じた幾何学的構成により１つの３次元メッシュ客体を三角形ストリップで構成する際に、符号化するデータのサイズに基づいて複数個の部分メッシュに分割し、この複数個の部分メッシュをそれぞれ符号化して圧縮されたビットストリームに組み合わせて伝送する３次元メッシュ情報のプログレッシブ符号化装置により符号化され伝送されたビットストリームのプログレッシブ復号化装置において、
前記伝送されたビットストリームを複数個の符号化済みの部分メッシュに分離するデマルチプレクサと、
前記複数個の符号化済みの部分メッシュをそれぞれ復号化する複数個の部分別復号化部と、
複数個の復号化済みの部分メッシュを合成して、３次元メッシュを復元する３次元データ合成部と、
を備えることを特徴とする３次元メッシュ情報のプログレッシブ復号化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、３次元メッシュ（mesh）情報の符号化／復号化に係り、特に、MPEG-4 SNHC（Synthetic and Natural Hybrid Coding）分野及びVRML（Virtual Reality Modeling Language）等で用いられる３次元メッシュ情報のプログレッシブ符号化／復号化方法及びその装置に関する。
【０００２】
【従来の技術】
３次元メッシュからなる３次元客体の伝送にあたっては、メッシュデータの有効な符号化だけでなく、伝送されるメッシュデータのプログレッシブ復元が重要なものとして認識されつつある。プログレッシブ復元により、伝送中に、線路上の誤りが原因となってメッシュデータにロスが生じた場合、既に伝送されたメッシュデータだけでロスの生じたデータの一部が復元可能なことから、再送されるべきメッシュデータ量が最小化する。プログレッシブ復元技術は、このように線路誤りに強い特性を有するので、これからの無線通信または低伝送率通信などで有効に利用できると期待を集めている。
【０００３】
図１は、従来の３次元メッシュ情報の符号化／復号化装置を示す概念的なブロック図である。図１を参照すると、符号化部１０１は、連結情報符号化器１０２、位置情報符号化器１０３及びエントロピー符号化器１０４から構成され、復号化部１１２は、エントロピー復号化器１０６、連結情報復号化器１０７及び位置情報復号化器１０８から構成される。
【０００４】
以下、図１に基づきMPEGで用いる従来の３次元メッシュデータの圧縮方式について説明する。符号化部１０１に入力された３次元メッシュデータ１００は連結情報及び位置情報に分けられ、かつそれぞれ連結情報符号化器１０２及び位置情報符号化器１０３により符号化される。このとき、頂点構造に関する情報１０５は、連結情報符号化器１０２から位置情報符号化器１０３へ送られる。連結情報符号化器１０２及び位置情報符号化器１０３により圧縮された情報はさらにエントロピー符号化器１０４を介して圧縮されたビットストリーム１１１に変換される。
【０００５】
圧縮されたビットストリーム１１１は、復号化部１１２に入力され、次のような復元過程を経る。圧縮されたビットストリーム１１１は、エントロピー復号化器１０６を介して連結情報及び位置情報に分けられ、かつそれぞれ連結情報復号化器１０７及び位置情報復号化器１０８により復号化される。このとき、符号化部１０１でのように、頂点構造に関する情報１０９は、連結情報復号化器１０７から位置情報復号化器１０８へ送られる。復号化済みの連結情報及び復号化済みの位置情報を用いて復元された３次元メッシュデータ１１０を得ることができる。
【０００６】
図1に示されたように、一つの３次元メッシュは、通信線路上において圧縮されたビットストリームの形で伝送される。ところが、従来の方式はエントロピー符号化器を用いるため、通信線路上で発生しうる伝送誤りに弱いという不都合があった。
要するに、従来の３次元メッシュデータの符号化は、メッシュデータ全体を単位として符号化を行うがゆえに、符号化済みのデータを伝送するにあたって、全体のビットストリームを全て伝送しない限り、その一部を復元できないという問題がある。さらに、伝送にあたって発生する通信線路上の誤りが原因となって僅かなデータのロスが生じた場合にも、メッシュデータ全体を再送しなければならない問題があった。その例として、現在MPEG-4 SNHC３次元メッシュを符号化する技術として採られている、IBM社により提案された符号化方式（ISO／IEC JTC1／SC29／WG11 MPEG98／W2301, "MPEG-4 SNHC Verification Model 9.0）がある。
【０００７】
【発明が解決しようとする課題】
本発明は、上記のような問題点に着目してなされたものであり、その目的は、モデルを部分別に処理できるように再構成することにより、部分別区分及び部分別復元が可能となり、これにより映像のプログレッシブ再現ができ、かつ伝送誤りに対処できる３次元メッシュ情報のプログレッシブ符号化／復号化方法及びその装置を提供するところにある。
【０００８】
さらに、本発明の他の目的は、モデルを相互独立的な段階別メッシュまたは部分メッシュに分離することにより、独立的な符号化及び復号化が可能となり、これにより映像のプログレッシブ再現ができ、かつ伝送誤りに対処できる３次元メッシュ情報のプログレッシブ符号化／復号化方法及びその装置を提供するところにある。
【０００９】
【課題を解決するための手段】
前記目的を達成するために、本発明の望ましい一実施例による３次元メッシュ情報のプログレッシブ符号化方法は、（ａ）３次元メッシュを複数個の部分メッシュで再構成するステップと、（ｂ）複数個の部分メッシュをそれぞれ符号化するステップと、（ｃ）複数個の符号化済みの部分メッシュを圧縮されたビットストリームに組み合わせて伝送するステップとを備える。
【００１０】
さらに、前記目的を達成するために、３次元メッシュ情報のプログレッシブ符号化方法により符号化され伝送されたビットストリームのプログレッシブ復号化方法は、（ａ）前記伝送されたビットストリームを複数個の符号化済みの部分メッシュに分割するステップと、（ｂ）前記複数個の符号化済みの部分メッシュをそれぞれ復号化するステップと、（ｃ）複数個の復号化済みの部分メッシュを合成して、３次元メッシュを復元するステップとを備える。
【００１１】
さらに、前記目的を達成するために、本発明の望ましい一実施例による３次元メッシュ情報のプログレッシブ符号化装置は、３次元メッシュを複数個の部分メッシュで再構成する３次元データ分析部と、複数個の部分メッシュをそれぞれ符号化する複数個の部分別符号化部と、複数個の符号化済みの部分メッシュを圧縮されたビットストリームに組み合わせて伝送するマルチプレクサとを備える。
【００１２】
さらに、前記目的を達成するために、３次元メッシュ情報のプログレッシブ符号化装置により符号化され伝送されたビットストリームのプログレッシブ復号化装置は、前記伝送されたビットストリームを複数個の符号化済みの部分メッシュに分離するデマルチプレクサと、複数個の符号化済みの部分メッシュをそれぞれ復号化する複数個の部分別復号化部と、複数個の復号化済みの部分メッシュを合成して、３次元メッシュを復元する３次元データ合成部とを備える。
【００１３】
前記他の目的を達成するために、本発明の他の望ましい実施例による３次元メッシュ情報のプログレッシブ符号化／復号化方法は、（ａ）３次元メッシュから相互独立的な一つ以上の段階別メッシュを抽出するステップと、（ｂ）前記一つ以上の段階別メッシュをそれぞれ相互独立的に符号化し、かつそれぞれ独立的に伝送するステップと、（ｃ）相互独立的に符号化されて伝送された一つ以上の段階別メッシュをそれぞれ復号化して、相互独立的な一つ以上の段階別メッシュを得るステップとを備え、さらに（ｄ）相互独立的な段階別メッシュを集め、かつ重複する情報を除去して元の３次元メッシュを復元するステップを備える。
【００１４】
さらに、前記他の目的を達成するために、本発明の望ましい他の実施例による３次元メッシュ情報のプログレッシブ符号化／復号化装置は、３次元メッシュを入力し、かつ入力された３次元メッシュから相互独立的な一つ以上の段階別メッシュを抽出する３次元段階別メッシュ分析部と、前記一つ以上の段階別メッシュをそれぞれ相互独立的に符号化し、かつ相互独立的に伝送する一つ以上の３次元段階別メッシュ分析部と、相互独立的に符号化され伝送された一つ以上の段階別メッシュをそれぞれ復号化して、相互独立的な一つ以上の段階別メッシュを得る一つ以上の段階別メッシュ復号化部とを備え、さらに相互独立的な一つ以上の段階別メッシュを集め、かつ重複する情報を除去して元の３次元メッシュを復元する３次元段階別メッシュ合成部を備える。
【００１５】
さらに、前記他の目的を達成するために、本発明のさらに他の望ましい実施例による３次元メッシュ情報のプログレッシブ符号化／復号化方法は、（ａ）３次元メッシュから一つ以上の段階別メッシュを抽出し、かつ抽出された段階別メッシュを相互独立的な複数個の部分メッシュに分割するステップと、（ｂ）複数個の部分メッシュをそれぞれ相互独立的に符号化し、かつ相互独立的に伝送するステップと、（ｃ）相互独立的に符号化されて伝送された複数個の部分メッシュをそれぞれ復号化して、相互独立的な複数個の部分メッシュを得るステップとを備え、さらに（ｄ）相互独立的な部分メッシュを集め、かつ相隣接する部分メッシュ間に重なり合う情報を除去して元の３次元メッシュを復元するステップを備える。
【００１６】
さらに、前記他の目的を達成するために、本発明のさらに他の望ましい実施例による３次元メッシュ情報のプログレッシブ符号化／復号化装置は、３次元メッシュを入力して一つ以上の段階別メッシュを抽出し、かつ抽出された段階別メッシュを相互独立的な複数個の部分メッシュに分割する３次元データ分析部と、複数個の段階別メッシュをそれぞれ相互独立的に符号化し、かつ相互独立的に伝送する複数個の部分メッシュ符号化部と、相互独立的に符号化され伝送された複数個の部分メッシュをそれぞれ復号化して、相互独立的な複数個の部分メッシュを得る複数個の部分メッシュ復号化部とを備え、さらに相互独立的な複数個の部分メッシュを集め、かつ相隣接する部分メッシュ間に重なり合う情報を除去して元の３次元メッシュを復元する３次元データ合成部を備える。
【００１７】
【発明の実施の形態】
以下、添付された図面に基づき本発明にかかる３次元メッシュ情報のプログレッシブ符号化／復号化方法及び装置について説明する。
図２は、本発明にかかる３次元メッシュ情報の構造を示す概念図である。先ず、３次元メッシュのプログレッシブ処理のために、本発明では、新しいメッシュ構造を図２のように提案する。図２を参照すると、３次元メッシュ（Mesh Object：ＭＯ）は、メッシュ情報を幾つかの段階に分割した段階別メッシュ（ＭＯＬ：Mesh Object Layer）から構成できる。このとき、各ＭＯＬは、一つあるいはそれ以上の部分メッシュ（ＭＣＯＭ：Mesh COMponent）を含むことになる。一つのＭＣＯＭは、それ自体の復元に必要な連結情報（Connectivity information）、位置情報（Geometry information）、及びその他の情報として画像情報（Photometry Information）などを含む。すなわち、ＭＯは符号化すべき３次元メッシュ客体として定義でき、これらのメッシュ情報を各種の画質及び機能に応じて幾つかの段階に分割したものを段階別メッシュ（ＭＯＬ）として定義できる。また、トポロジー的処方による幾何学的構成（Geometric Composition through Topological Surgery）により、一つの３次元メッシュ客体を相互連結性のない幾つかの独立的なメッシュ情報（即ち、連結成分）で構成したとき、符号化すべきデータの大きさやその他の特性に応じて、相互独立的なメッシュ情報を組み合せるあるいは分割して構成したものを部分メッシュ（ＭＣＯＭ）と定義できる。
【００１８】
図３は、本発明にかかる３次元メッシュ情報のプログレッシブ符号化／復号化装置を示す概念図である。本発明の望ましい一実施例による３次元メッシュ情報のプログレッシブ符号化／復号化装置は、符号化部２００及び復号化部２０９から構成される。また符号化部２００は３次元データ分析器２０１、複数個の部分別符号化器１〜Ｎ ２０２及びマルチプレクサ（ＭＵＸ）２０４から構成され、復号化部２０９はデマルチプレクサ（ＤＥＭＵＸ）２０５、複数個の部分別復号化器１〜Ｎ ２０６及び３次元データ合成器２０８から構成される。
【００１９】
図３を参照すると、先ず、３次元メッシュ（ＭO） １００が３次元データ分析器２０１において複数個の部分メッシュ（ＭＣＯＭ）で再構成され、複数個の部分メッシュ（ＭＣＯＭ）はそれぞれ複数個の部分別符号化器１〜Ｎ ２０２に入力される。このとき、部分メッシュ（ＭＣＯＭ）は、幾つかのものが集まって一つの段階別メッシュ（ＭＯＬ）を成すことができる。それぞれの部分メッシュ（ＭＣＯＭ）は、相当する部分別符号化器２０２を介して圧縮され、それぞれの圧縮されたビットストリームはＭＵＸ ２０４によって組み合せられ、かつ伝送される。このとき、既に行われた１つの段階別メッシュ（ＭＯＬ）または部分メッシュ（ＭＣＯＭ）の部分別符号化器において用いられた情報２０３は、まだ行っていない部分別符号化器において用いることができる。例えば、上位の部分別符号化器となる部分別符号化器１で用いられた情報２０３は、下位の部分別符号化器となる部分別符号化器２に送られて利用できる。
【００２０】
復号化部２０９に伝送された圧縮済みのビットストリームは、ＤＥＭＵＸ ２０５を介して各段階別メッシュ（ＭＯＬ）に分離され、段階別メッシュ（ＭＯＬ）はさらに部分メッシュ（ＭＣＯＭ）に分離され、かつそれぞれの部分メッシュ（ＭＣＯＭ）は複数個の部分別復号化器１〜Ｎ ２０６を介して復号化される。復号化部２０９においても、既に行われた部分別復号化器において生成された情報２０７は、まだ行っていない部分別復号化器において再使用される。例えば、上位の部分別復号化器となる部分別復号化器１において生成された情報２０７は、下位の部分別復号化器となる部分別復号化器２に送られて再使用される。段階別に復号化された部分メッシュ（ＭＣＯＭ）は、３次元データ合成器２０８により３次元メッシュ１１０に復元される。
【００２１】
先ず、３次元メッシュ（ＭＯ）を一つ以上の段階別メッシュ（ＭＯＬ）で構成してから、これらをそれぞれ部分メッシュ（ＭＣＯＭ）に分割する場合、３次元データ分析器２０１は、図４のように構成できる。
図４を参照すると、図３に示された３次元データ分析器２０１の望ましい実施例は、３次元段階別メッシュ（ＭＯＬ）分析器３０１及び複数個の部分メッシュ（ＭＣＯＭ）分析器１〜ｎ ３０３から構成される。
【００２２】
３次元メッシュ（ＭＯ）１００が３次元データ分析器３００に入力されると、まず、３次元段階別メッシュ（ＭＯＬ）分析器３０１においては、入力された３次元メッシュ（ＭＯ）から各段階別メッシュ（ＭＯＬ１〜ＭＯＬｎ）３０２を抽出する。次いで、抽出された各段階別メッシュ（ＭＯＬ１〜ＭＯＬｎ）３０２は、部分メッシュ（ＭＣＯＭ）分析器１〜ｎ ３０３を介して部分メッシュ３０４に分割され、かつ出力される。各部分メッシュ３０４は、部分別符号化器１-１〜部分別符号化器１-ｍ、部分別符号化器２-１〜部分別符号化器２-ｍ、．．．のうち相当する部分別符号化器に入力される。
【００２３】
各部分メッシュ（ＭＣＯＭ）分析器は別の部分メッシュ（ＭＣＯＭ）分析器と情報を共用し、また各部分別符号化器は部分メッシュ（ＭＣＯＭ）分析器間の情報を共用するが、このとき、相異なる段階別メッシュ間の情報３０５は、部分メッシュ（ＭＣＯＭ）分析器間において共用されない場合もある。この場合、独立的な段階別メッシュ情報の符号化／復号化方法は、図５のように行われる。
【００２４】
図５を参照すると、本発明の他の望ましい実施例による３次元メッシュ情報のプログレッシブ符号化／復号化装置は、３次元段階別メッシュ（ＭＯＬ）分析器４０１及び複数個の独立的な符号化器／復号化器１〜ｎ ４０３から構成できる。
図5に示された実施例においては、ある符号化器において生成された情報を他の符号化器が用いない。即ち、３次元メッシュ（ＭＯ）１００が３次元段階別メッシュ（ＭＯＬ）分析器４０１を介して段階別メッシュ（ＭＯＬ１〜ＭＯＬｎ）４０２に分離された後、それぞれ独立的な符号化器／復号化器１〜ｎ ４０３を介して圧縮、伝送、復号化され、復元される。ここで用いる符号化器／復号化器はそれぞれＭＣＯＭ分析器を含めて、段階別メッシュをさらに部分メッシュに分割してそれぞれ符号化及び復号化を行うことができる。各復号化器を介して復号化された各情報４０４は、相互独立的な段階別メッシュデータであるため、これらを単に集めることで復元された３次元メッシュ４０５が得られる。ところが、この場合、３次元段階別メッシュ（ＭＯＬ）分析器４０１において３次元メッシュ（ＭＯ）１００を段階別メッシュ（ＭＯＬ１〜ＭＯＬｎ）４０２に分割する過程で生成された付加的な情報も復元された３次元メッシュ４０５に含まれる。
【００２５】
図6を参照すると、図５に示された３次元メッシュ情報のプログレッシブ符号化／復号化装置の他の望ましい実施例は、３次元段階別メッシュ（ＭＯＬ）合成器４０６をさらに含んで構成される。復元された３次元メッシュ１１０に含まれた付加的な情報を除去して、元の３次元メッシュ（ＭＯ）１００と同様に復元された３次元メッシュ１１０を得るためには、３次元段階別メッシュ（ＭＯＬ）合成器406を追加すれば良い。３次元段階別メッシュ（ＭＯＬ）合成器４０６は、各復号化器によって復号化された情報４０４を集め、かつ重なり合う情報を除去することにより、復元された元の３次元メッシュ１１０が得られる。
【００２６】
一方、図４において、各部分別符号化器は、他の部分別符号化器で使用済みの情報を用いるが、このとき、部分メッシュ間でも、既に行われた部分別符号化器で生成された情報をまだ行っていない部分別符号化器において用いない場合がある。このとき、独立的な部分メッシュ情報の符号化／復号化方法は、図７のように行われる。
【００２７】
図７を参照すると、本発明のさらに他の望ましい実施例による３次元メッシュ情報のプログレッシブ符号化／復号化装置は、３次元データ分析器５０１、複数個の独立的な部分メッシュ（ＭＣＯＭ）符号化器／復号化器１〜ｎ ５０３から構成される。
図７に示された実施例によると、既に行われた符号化器の情報をまだ行っていない符号化器で用いない。すなわち、３次元メッシュ（ＭＯ）１００が３次元データ分析器５０１（３次元ＭＯＬ分析器及びＭＣＯＭ分析器で構成）を介して部分メッシュ（ＭＣＯＭ１〜ＭＣＯＭｎ）５０２で再構成され、次いでそれぞれ独立的にＭＣＯＭ符号化器／復号化器１〜ｎ５０３を介して圧縮、伝送、復号化され、復元される。各復号化器を介して復号化された各情報５０４は相互独立的な部分メッシュデータであるため、これらを単に集めることで復元された３次元メッシュ５０５が得られる。しかし、３次元データ分析器５０１において一つの段階別メッシュを複数個の独立的な部分メッシュに分割する場合、各部分メッシュは境界当りの情報（例えば、エッジ、点の座標及び点単位の属性など）をそれぞれ共有している。したがって、復元された３次元メッシュ５０５には、重複する情報が多い。
【００２８】
図８を参照すると、図７に示された本発明にかかる３次元メッシュ情報のプログレッシブ符号化／復号化装置は、３次元データ合成器５０６をさらに含んで構成される。復元された３次元メッシュ５０５に含まれている重複する情報を除去し、符号化効率を高めるために、図８のように、３次元データ合成器５０６が追加される。３次元データ合成器５０６は、各復号化器により復号化された情報５０４を集め、かつ重複する情報を除去することにより、復元された３次元メッシュ１１０が得られる。
【００２９】
図９は、本発明への理解を容易にするために、一つの段階別メッシュ（ＭＯＬ）から構成された簡単な３次元メッシュ（ＭＯ）を例示したものであり、図１０は、図９に示された段階別メッシュ（ＭＯＬ）を３つに分割した部分メッシュ（ＭＣＯＭ０〜ＭＣＯＭ２）を例示したものである。図１０において、相互独立的な部分メッシュ間の境界は太線で示してある。この境界に相当する情報（例えば、エッジ、点の座標及び点単位の属性など）は、以前の部分メッシュに共有してある。従って、次の部分メッシュは、以前の部分メッシュの復号化／符号化過程で生成された情報を一部または全て用いて復号化／符号化できる。
【００３０】
図１１（Ａ)〜図１１(Ｃ)は、段階別メッシュ（ＭＯＬ）を部分メッシュ（ＭＣＯＭ０〜ＭＣＯＭ２）に分割するとき、各部分メッシュに含まれる情報の例を説明するための図面である。
図１１（Ａ）は、段階別メッシュ（ＭＯＬ）を部分メッシュ（ＭＣＯＭ０〜ＭＣＯＭ２）に分割するとき、部分メッシュ間の境界当りに存する情報が共有されることを示す。境界当りに存する情報のうち一部または全ての情報が複写され、相隣接する部分メッシュが同一の情報をそれぞれ持つことができる。図１１（Ｂ）は、相隣接する部分メッシュ間に共有される情報をそれぞれ有する場合の部分メッシュ（ＭＣＯＭ０〜ＭＣＯＭ２）を示す。このように、各部分メッシュ毎に共有する情報の重複を可とすると、全ての部分メッシュが独立的に処理できるものの、圧縮効率が低下する問題がある。
【００３１】
一方、図１１（Ｃ）は、相隣接する部分メッシュ間に共有される情報を先に符号化される部分メッシュでのみ有する場合の部分メッシュ（ＭＣＯＭ０〜ＭＣＯＭ２）を示す。既に符号化済みの部分メッシュと共有する情報が存する場合、既に符号化済みの部分メッシュにより生成された情報がまだ符号化していない部分メッシュのために用いられるので、重複する情報はないものの、各部分メッシュは独立的に処理できない。
【００３２】
図１２（Ａ）〜図１２（Ｃ）は、２つの部分メッシュ間に共有される情報を処理する方法の例を説明するための図面である。
図１２（Ａ）は、２つの部分メッシュが相互独立的に分割されている例を示す。ここで、２つの部分メッシュは同じ辺、同じ点及び同じ点の属性を有している。これらの情報が両側ともに複写され、２つの部分メッシュは分離された後、それぞれ独立的に処理される。このとき、処理中に各部分メッシュに複写された情報はそれぞれ別々の情報として認識されるので、復号化部でそれぞれ復号化された各情報を集めて段階別メッシュを復元すると、元の段階別メッシュの形態が変わり、その結果ファイルの大きさが増大する。図５または図７を参照すると、図１２（Ａ）のように、相互独立的な部分メッシュは相互独立的な符号化器／復号化器により独立的に処理される。
【００３３】
図１２（Ｂ）は、各部分メッシュを完全に分離せず、共有される情報のうち一部の情報のみ重ね合わせて符号化する例を示す。以前の部分メッシュは共有される情報を全て有しているが、次の部分メッシュは共有される情報のうち以前の部分メッシュと同じ点に関する情報のみ有している。この場合、共有された同じ点が２つ以上の部分メッシュで定義されているが、これが同じ点として認識されるため、復元後に元の段階別メッシュの形が保持される。また、以前の部分メッシュが復元されない場合には、次の部分メッシュにより境界部分の復元が可能となる。図３を参照すると、既に行われる部分別符号化器で生成された情報がまだ行っていない部分別符号化器で用いられるとき、その情報は共有される情報の一部である。まだ行っていない部分別符号化器は既に行われた部分別符号化器と共有された同じ点に関する情報を重ね合わせて符号化する。
【００３４】
図１２（Ｃ）は、以前の部分メッシュにのみ共有される情報が存し、次の部分メッシュでは以前の部分メッシュで生成された情報を全て用いる例を示す。この場合、重ね合わせて符号化する情報が存しないので、圧縮効率は高まるが、各部分メッシュに独立性がないため、以前の部分メッシュが復元されない場合には、次の部分メッシュにより境界部分の復元が不可能である。図3を参照すると、既に行われた部分別符号化器で生成された情報がまだ行っていない部分別符号化器で用いられるとき、その情報は共有される情報の全てである。まだ行っていない部分別符号化器は、既に行われた部分別符号化器と共有された全ての情報を重ね合わせて復号化しない。
【００３５】
以下、本発明にかかる３次元メッシュ情報のプログレッシブ符号化を具現したISO／IEC JTC1／SC29／WG11 MPEG-4 SNHC３次元メッシュ符号化の文法表を示す。
▲3D#Mesh#Object
MO#start#code：これは、同期の目的で用いられる固有の16ビットコードである。このコードの値は、常時'0000 0000 0010 0000'である。
【００３６】
▲3D#Mesh#Object#Layer
MOL#start#code：これは、同期の目的で用いられる固有の16ビットコードである。このコードの値は、常時'0000 0000 0011 0000'である。
mol#id：この8ビットの無符号整数は、段階別メッシュ（mesh object layer：ＭＯＬ）に対する唯一の識別子を表す。値0はベース段階（base layer）を表し、0よりも大きい値は精密段階（refinement layer）を表す。3D#Mesh#Object#Headerに続く最初の3D#Mesh#Object#Layerはmol#id=0でなければならず、同一の3D#Mesh#Object内で次の3D#Mesh#Object#Layerはmol#id＞0でなければならない。
【００３７】
N#Verticesは、３次元メッシュの現在解像度における頂点の個数である。計算を減らすために用いられる。
N#Trianglesは、３次元メッシュの現在解像度における三角形の個数である。計算を減らすために用いられる。
N#Edgesは、３次元メッシュの現在解像度におけるエッジの個数である。計算を減らすために用いられる。
【００３８】
▲3D#Mesh#Object#Base#Layer
MOBL#start#code：これは、同期の目的で用いられる固有の16ビットコードである。このコードは常時'0000 0000 0011 0001'である。
mobl#id:この8ビットの無符号整数は部分メッシュ（mesh object component：ＭＣＯＭ）に対する唯一の識別子を表す。
【００３９】
last#component：このブール値（boolean value）は、復号化すべき連結成分（connected component）がさらに存するかどうかを表す。もし、last#componentが真理（true）であれば、最後の成分は復号化された。そうでなければ、復号化すべき成分がさらに存する。このフィールドは算術的に符号化される。
▲3D#Mesh#Object#Header
ccw：このブール値は、復号化される面（face）の頂点順序が反時計方向の順序に従うかどうかを表す。
【００４０】
convex：このブール値は、モデルが凸かどうかを表す。
solid：このブール値は、モデルが堅いかどうかを表す。
creaseAngle：この6ビットの無符号整数は、クリース角（crease angle）かどうかを表す。
▲coord#header
coord#binding：この2ビットの無符号整数は、３次元メッシュに対する頂点座標の結合を表す。唯一に認められる値は'01'である。
【００４１】
coord#bbox：このブール値は、幾何情報（geometry）にバウンディング箱（bounding  box）が与えられるかどうかを表す。バウンディング箱が与えられないと、デフォルトが用いられる。
coord#xmin、coord#ymin、coord#zmin：この不動少数点値は、幾何情報の置かれたバウンディング箱の左下側の隅を表す。
【００４２】
coord#size：この不動少数点値は、バウンディング箱の寸法を表す。
coord#quant：この5ビットの無符号整数は、幾何情報に対する量子化ステップ（quantization step）を表す。
coord#pred#type：この2ビットの無符号整数は、メッシュの頂点座標を再生するために用いられる予測の形態を表す。
【００４３】
【表１】
0004295866.tif 000002
coord#nlambda：この2ビットの無符号整数は、幾何情報を予測するために用いられる先祖（ancestor）の個数を表す。coord#nlambdaに対して許容可能な値は1と3である。表2は、normal#pred#typeの機能として許容可能な値を示す。
【００４４】
【表２】
0004295866.tif 000003
coord#lambda：この無符号整数は、予測のための先祖に与えられる重み付け値を表す。このフィールドで用いられるビットの数はcoord#quant+3に等しい。
【００４５】
▲normal#header
normal#binding：この2ビットの無符号整数は、３次元メッシュに対するノーマル（normal）の結合を表す。許容可能な値は表3に記される。
【００４６】
【表３】
0004295866.tif 000004
normal#bbox：このブール値は、常時偽'0'でなければならない。
normal#quant：この5ビットの無符号整数は、ノーマルに対して用いられる量子化ステップを表す。
【００４７】
normal#pred#type：この2ビットの無符号整数は、いかにノーマル値が予測されるかを表す。
【００４８】
【表４】
0004295866.tif 000005
【００４９】
【表５】
0004295866.tif 000006
normal#nlambda：この2ビットの無符号整数は、ノーマルを予測するために用いられる先祖の個数を表す。normal#nlambdaに対して許容可能な値は1と3である。表6は、normal#pred#typeの機能として許容可能な値を示す。
【００５０】
【表６】
0004295866.tif 000007
normal#lambda：この無符号整数は、予測のための先祖に与えられる重み付け値を表す。このフィールドで用いられるビット数はnormal#quant+3に等しい。
【００５１】
▲color#header
color#binding：この2ビットの無符号整数は、３次元メッシュに対する色相の結合を表す。許容可能な値は表7に記される。
【００５２】
【表７】
0004295866.tif 000008
color#bbox：このブール値は、色相に対してバウンディング箱が与えられるかどうかを表す。
color#rmin、color#gmin、color#bmin：この不動少数点値は、ＲＧＢ空間内のバウンディング箱の左下側コーナーの位置を表す。
【００５３】
color#size：この不動少数点値は、色相バウンディング箱の寸法を表す。
color#quant：この5ビットの無符号整数は、色相に対して用いられる量子化ステップを表す。
color#pred#type：この2ビットの無符号整数は、いかに色相が予測されるかを表す。
【００５４】
【表８】
0004295866.tif 000009
【００５５】
【表９】
0004295866.tif 000010
color#nlambda：この2ビットの無符号整数は、色相を予測するために用いられる先祖の個数を表す。color#nlambdaに対して許容可能な値は1と3である。表10は、normal#pred#typeの機能として許容可能な値を示す。
【００５６】
【表１０】
0004295866.tif 000011
color#lambda:この無符号整数は、予測のための先祖に与えられる重み付け値を表す。このフィールドで用いられるビット数はcolor#quant+3に等しい。
【００５７】
▲texCoord#header
texCoord#binding：この2ビットの無符号整数は、3次元メッシュに対するテクスチャーの結合を表す。許容可能な値は表11に記される。
【００５８】
【表１１】
0004295866.tif 000012
texCoord#bbox：このブール値は、テクスチャーに対してバウンディング箱が与えられるかどうかを表す。
texCoord#umin、texCoord#vmin：この不動少数点値は、2次元空間内のバウンディング箱の左下側コーナーの位置を表す。
【００５９】
texCoord#size：この不動少数点値は、テクスチャーバウンディング箱の寸法を表す。
texCoord#quant：この5ビットの無符号整数は、テクスチャーに対して用いられる量子化ステップを表す。
texCoord#pred#type：この2ビットの無符号整数は、texCoord#bindingが'01'であれば常時'10'であり、そうでなければ'01'である。
【００６０】
texCoord#nlambda：この2ビットの無符号整数は、テクスチャーを予測するために用いられる先祖の個数を表す。texCoord#nlambdaに対して許容可能な値は1と3である。表12は、texCoord#pred#typeの機能として許容可能な値を示す。
【００６１】
【表１２】
0004295866.tif 000013
texCoord#lambda：この無符号整数は、予測のための先祖に与えられる重み付け値を表す。このフィールドで用いられるビットの数はtexCoord#quant+3に等しい。
【００６２】
▲Cgd#header
N#Proj#surface#Spheresは、射出された表面球（Projected Surface Spheres）の個数である。典型的に、この個数は1に等しい。
x#coord#Center#Pointは、射出された表面球の中心点（典型的に、客体の重心点）のx座標である。
【００６３】
y#coord#Center#Pointは、射出された表面球の中心点（典型的に、客体の重心点）のy座標である。
z#coord#Center#Pointは、射出された表面球の中心点（典型的に、客体の重心点）のz座標である。
Normalized#Screen#Distance#Factorは、射出された表面球の半径に比べて仮想スクリーンがどこに位置づけられるかを表す。射出された表面球の中心点と仮想スクリーンとの距離は、Radius／（Normalized#Screen#Distance#Factor+1）に等しい。Radiusは、各射出された表面球に対して述られるのに対し、Normalized#Screen#Distance#Factorは一回に限って述べられる。
【００６４】
Radiusは、射出された表面球の半径である。
Min#Proj#Surfaceは、対応づけられる射出された表面球に関する最小の射出された表面値である。この値はしばしば（しかし、必ずしもそうであるとは限らない）Proj#Surface値の一つに等しい。
N#Proj#Pointsは、射出された表面が伝送される射出された表面球上の点の個数である。他のすべての点に対して、射出された表面は線形補間により決定される。N#Proj#Pointsは、典型的に最初の射出された表面球よりは小さく（例えば、20）、追加の射出された表面球よりは極めて小さい（たとえば、3）。
【００６５】
Sphere#Point#Coordは、八面体内の点位置に対するインデックスである。
Proj#Surfaceは、Sphere#Point#Coordにより記された点内の射出された表面である。
▲vertex#graph
vg#simple：このブール値は、現在の頂点グラフが簡単であるかどうかを指定する。簡単な頂点グラフは、いかなるループも含めない。このフィールドは、算術的に符号化される。
【００６６】
vg#last：このブール値は、現在のランが現在の分岐頂点から始まる最後のランであるかどうかを表す。このフィールドは、各分岐頂点の最初のラン、すなわち、skip#last変数が真のときには符号化されない。現在の頂点ランに対してvg#lastの値が符号化されない場合には、偽のことと見なされる。このフィールドは、算術符号化される。
【００６７】
vg#forward#run：このブールフラグは、現在のランが新しいランであるかどうかを表す。もし、それが新しいランでなければ、それはグラフ内のループを表す前もって訪問された（traversed）ランでなければならない。このフィールドは、算術符号化される。
vg#loop#inx：この無符号整数は、現在のループが結ばれたランに対するインデックスを表す。その単一（unary）の表現（表13参照）は算術符号化される。もし、変数openloopsがvg#loop#inxに等しければ、その単一の表現に続く'1'は消される。
【００６８】
【表１３】
0004295866.tif 000014
vg#run#length：この無符号整数は、現在の頂点ランの長さを表す。その単一の表現（表14参照）は、算術符号化される。
【００６９】
【表１４】
0004295866.tif 000015
vg#leaf：このブールフラグは、現在のランの最後の頂点が末端頂点であるかどうかを表す。もし、それがリーフ頂点でなければ、それは分岐頂点である。このフィールドは、算術符号化される。
【００７０】
vg#loop：このブールフラグは、現在のランの葉がループを表し、かつそのグラフの分岐頂点に結ばれたかどうかを表す。このフィールドは、算術符号化される。
▲triangle#tree
tt#run#length：この無符号整数は、現在の三角形ランの長さを表す。その単一の表現（表15参照）は算術符号化される。
【００７１】
【表１５】
0004295866.tif 000016
tt#leaf：このブールフラグは、現在のランの最後の三角形が葉三角形であるかどうかを表す。もし、それが葉三角形でなければ、それは分岐三角形である。このフィールドは、算術符号化される。
【００７２】
triangulated：このブール値は、現在の成分が三角形のみ含むかどうかを表す。このフィールドは、算術符号化される。
marching#triangle：このブール値は、三角形木における三角形の位置により決定される。三角形が葉または分枝であれば、marching#triangle=0であり、そうでなければmarching#triangle=1である。
【００７３】
marching#pattern：このブールフラグは、三角形ランの内部のエッジのマーチング（marching）パターンを表す。0は左からのマーチを表し、1は右からのマーチを表す。このフィールドは、算術符号化される。
polygon#edge：このブールフラグは、現在三角形のベースが3次元メッシュ客体の再生時に維持されるべきエッジであるかどうかを表す。もし現在三角形のベースが維持されないと、それは捨てられる。このフィールドは、算術符号化される。
【００７４】
▲triangle
coord#bit：このブール値は、幾何情報ビットの値を表す。このフィールドは、算術符号化される。
coord#heading#bit：このブール値は、ヘッディング幾何情報ビットの値を表す。このフィールドは、算術符号化される。
【００７５】
coord#sign#bit：このブール値は、幾何情報サンプルの符号を表す。このフィールドは、算術符号化される。
coord#trailing#bit：このブール値は、トレーリング幾何情報ビットの値を表す。このフィールドは、算術符号化される。
normal#bit：このブール値は、ノーマルビットの値を表す。このフィールドは、算術符号化される。
【００７６】
normal#heading#bit：このブール値は、ヘッディングノーマルビットの値を表す。このフィールドは、算術符号化される。
normal#sign#bit：このブール値は、ノーマルサンプルの符号を表す。このフィールドは、算術符号化される。
normal#trailing#bit：このブール値は、トレーリングノーマルビットの値を表す。このフィールドは、算術符号化される。
【００７７】
color#bit：このブール値は、色相ビットの値を表す。このフィールドは、算術符号化される。
color#heading#bit：このブール値は、ヘッディング色相ビットの値を表す。このフィールドは、算術符号化される。
color#sign#bit：このブール値は、色相サンプルの符号を表す。このフィールドは、算術符号化される。
【００７８】
color#trailing#bit：このブール値は、トレーリング色相ビットの値を表す。このフィールドは、算術符号化される。
texCoord#bit：このブール値は、テクスチャービットの値を表す。このフィールドは、算術符号化される。
texCoord#heading#bit：このブール値は、ヘッディングテクスチャービットの値を表す。このフィールドは、算術符号化される。
【００７９】
texCoord#sign#bit：このブール値は、テクスチャーサンプルの符号を表す。このフィールドは、算術符号化される。
texCoord#trailing#bit：このブール値は、トレーリングテクスチャービットの値を表す。このフィールドは、算術符号化される。
▲3D#Mesh#Object#Forest#Split
MOFS#start#co：これは同期の目的で用いられる固有の16ビットコードである。このコードの値は常時'0000 0000 0011 0010'である。
【００８０】
mofs#id：この8ビットの無符号整数は、フォレスト分割成分に対する唯一の識別子である。
pre#smoothing：このブール値は、現在のフォレスト分割動作が総体的に頂点位置を予測するための事前平滑化段階（pre-smoothing step）を用いるかどうかを表す。
【００８１】
pre#smoothing#n：この整数値は、事前平滑化フィルター（pre-smoothing filter）の繰返し数を表す。
pre#smoothing#lambda：この不動少数点値は、事前平滑化フィルター（pre-smoothing filter）の最初の媒介変数である。
pre#smoothing#mu：この不動少数点値は、事前平滑化フィルターの二番目の媒介変数である。
【００８２】
post#smoothing：このブール値は、現在のフォレスト分割動作が量子化加工物を除去するための事後平滑化段階（post-smoothing  step）を用いているかどうかを表す。
post#smoothing#n：この整数値は、事後平滑化フィルターの繰返し数を表す。
【００８３】
post#smoothing#lambda：この不動少数点値は、事後平滑化フィルターの最初の媒介変数である。
post#smoothing#mu：この不動少数点値は、事後平滑化フィルターの二番目の媒介変数である。
sharp#edges：このブール値は、平滑化不連続エッジ（smoothing  discontinuity  edges）を表示するデータがビットストリームに含まれたかどうかを表す。もし、sharp#edges==0であれば、いかなるエッジも平滑化不連続エッジ（smoothing discontinuity edge）として表示していない。もし、平滑化不連続エッジが表示してあれば、事前平滑化フィルター及び事後平滑化フィルターはこれらを考慮する。
【００８４】
fixed#vertices：このブール値は、平滑化過程中に不動データがビットストリームに含まれたかどうかを表す。もし、fixed#vertices==0であれば、いかなる頂点も動くことが許容されない。もし、固定された頂点が表示してあれば、事前平滑化フィルター及び事後平滑化フィルターはこれらを考慮する。
edge#mark：このブール値は、対応づけられたエッジが平滑化不連続エッジで表示してあるかどうかを表す。
【００８５】
vertext#mark：このブール値は、対応づけられた頂点が固定された頂点であるかどうかを表す。
tree#edge：このブール値は、エッジが今まで作られてきたフォレストに追加される必要があるかどうかを表す。
other#update：このブール値は、頂点座標に対する更新及びフォレストのいかなる木にも伴わない面に係わる特性がビットストリームに従うかどうかを表す。
【００８６】
【表１６】
0004295866.tif 000017
【００８７】
【表１７】
0004295866.tif 000018
【００８８】
【表１８】
0004295866.tif 000019
【００８９】
【表１９】
0004295866.tif 000020
【００９０】
【表２０】
0004295866.tif 000021
【００９１】
【表２１】
0004295866.tif 000022
【００９２】
【表２２】
0004295866.tif 000023
【００９３】
【表２３】
0004295866.tif 000024
【００９４】
【表２４】
0004295866.tif 000025
【００９５】
【表２５】
0004295866.tif 000026
【００９６】
【表２６】
0004295866.tif 000027
【００９７】
【表２７】
0004295866.tif 000028
【００９８】
【表２８】
0004295866.tif 000029
【００９９】
【発明の効果】
以上述べたように、本発明にかかる３次元メッシュ情報のプログレッシブ符号化／復号化方法及び装置は、部分メッシュ（MCOM）として処理されるデータの構造を有することから、圧縮されたビットストリーム上においても部分別区分が可能となり、これにより、復号化部は部分別に復号化が済み次第、各部分を容易に再現することができる。これは、従来の３次元メッシュ情報の符号化方式に比べて、映像のプログレッシブ再現及び伝送誤りへの対処能が大幅に高まったものである。さらに、モデルを、まず段階別メッシュ（MOL）または部分メッシュ（MCOM）に分割すると、これらの独立的な符号化及び復号化が可能となる。また、この構造は簡単であり、必要あれば重なり合う情報も手軽に除去可能のように具現できる。
【図面の簡単な説明】
【図１】従来の３次元メッシュ情報符号化／復号化方法を示す概念的なブロック図である。
【図２】本発明にかかる３次元メッシュ情報の構造を示す概念図である。
【図３】本発明の望ましい一実施例による３次元メッシュ情報のプログレッシブ符号化／復号化方法の概念的なブロック図である。
【図４】図３に示された３次元データ分析器の望ましい実施例を示すブロック図である。
【図５】本発明の他の望ましい実施例による３次元メッシュ情報のプログレッシブ符号化／復号化方法を示す概念的なブロック図である。
【図６】図５に３次元段階別メッシュ（MOL）合成器がさらに含まれたブロック図である。
【図７】本発明のさらに他の望ましい実施例による３次元メッシュ情報のプログレッシブ符号化／復号化方法を示すブロック図である。
【図８】図７に３次元データ合成器がさらに含まれたブロック図である。
【図９】本発明への理解を容易にするために、一つの段階別メッシュ（MOL）から構成された簡単な３次元メッシュ（MO）の一例を示す図面である。
【図１０】図9に示された段階別メッシュ（MOL）を三つに分割した部分メッシュ（MCOM0〜MCOM2）の一例を示す図面である。
【図１１】図１１Ａ、図１１Ｂ及び図１１Ｃは、段階別メッシュ（MOL）を部分メッシュ（MCOM0〜MCOM2）に分割するとき、各部分メッシュに含まれる情報の例を説明するための図面である。
【図１２】図１２Ａ、図１２Ｂ及び図１２Ｃは、２つの部分メッシュ（ＭＣＯＭ）間に共有される情報を処理する方法の例を説明するための図面である。
【符号の説明】
２００    符号化部
２０９    復号化部
【図１】
0004295866.tif 000030
【図２】
0004295866.tif 000031
【図３】
0004295866.tif 000032
【図４】
0004295866.tif 000033
【図５】
0004295866.tif 000034
【図６】
0004295866.tif 000035
【図７】
0004295866.tif 000036
【図８】
0004295866.tif 000037
【図９】
0004295866.tif 000038
【図１０】
0004295866.tif 000039
【図１１】
0004295866.tif 000040
【図１２】
0004295866.tif 000041