【手続補正書】
【提出日】平成18年8月28日(2006.8.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
３次元メッシュ情報を漸進的に復元できるように符号化する方法において、
(ａ) ３次元メッシュを複数個の段階別メッシュ（MOL）で構成する段階と、
(ｂ) 前記段階別メッシュを各々複数の部分メッシュ（MCOM）に分割する段階と、
(ｃ) 前記部分メッシュ単位でビットストリームを形成して符号化する段階と、
(ｄ) 前記符号化された部分メッシュを圧縮されたビットストリームに統合する段階と、
を含み、前記部分メッシュ単位で形成されたビットストリームは、各部分メッシュ内のメッシュデータとして頂点２進ツリー情報と三角形２進ツリー情報とを含むことを特徴とする漸進３次元メッシュ情報の符号化方法。
【請求項２】
３次元メッシュ情報を漸進的に復元できるように符号化する方法において、
(ａ) 前記３次元メッシュを複数個の段階別メッシュ（MOL）で構成する段階と、
(ｂ) 前記段階別メッシュを各々複数個の部分メッシュ（MCOM）に分割する段階と、
(ｃ) 前記複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、所定の第１大きさ以下の部分メッシュを結合してあらゆる部分メッシュが一定の大きさを有するように再構成する段階と、
(ｄ) 再構成された部分メッシュのうち、各部分メッシュ内のメッシュを所定の第２大きさを有するビットストリーム単位で分割して符号化する段階と、
(ｅ) 前記符号化されたメッシュ情報を圧縮されたビットストリームに統合する段階と、
を含むことを特徴とする漸進３次元メッシュ情報の符号化方法。
【請求項３】
前記(ｃ)段階は、現在部分メッシュを構成する頂点２進ツリーにある頂点の総個数が所定の第１個数より少ない場合、前記現在の部分メッシュは符号化される次の部分メッシュと結合し、符号化される部分メッシュは、頂点の総個数が所定の第２個数より多い頂点からなる頂点２進ツリーを有するように再構成することを特徴とする請求項２に記載の漸進３次元メッシュ情報の符号化方法。
【請求項４】
前記(ｄ)段階は、前記各部分メッシュ内のメッシュ情報を構成する頂点２進ツリー情報及び三角形２進ツリー情報を、所定の第３個数の頂点と所定の第４個数の三角形とに分割することを特徴とする請求項３に記載の漸進３次元メッシュ情報の符号化方法。
【請求項５】
前記圧縮されたビットストリームは、再構成された各部分メッシュを構成する頂点２進ツリーのヘッダ及び三角形２進ツリーのヘッダと、前記（ｄ）段階で前記所定の第２大きさを有するビットストリーム単位で分割される複数の頂点２進ツリーからなる各ビットストリーム及び複数の三角形２進ツリーからなる各ビットストリームとを含むことを特徴とする請求項２に記載の漸進３次元メッシュ情報の符号化方法。
【請求項６】
３次元メッシュ情報が漸進的に復元できるように符号化する方法において、
(ａ) 前記３次元メッシュを複数個の段階別メッシュ（MOL）で構成する段階と、
(ｂ) 前記段階別メッシュを各々複数個の部分メッシュ（MCOM）に分割する段階と、
(ｃ) 前記各部分メッシュに三角形２進ツリーの分岐三角形（branch triangle）から分岐されるブランチの符号化順序を示す方向性情報を追加して符号化する段階と、
(ｄ) 符号化されたメッシュデータを圧縮されたビットストリームに統合する段階と、
を備えることを特徴とする漸進３次元メッシュ情報の符号化方法。
【請求項７】
前記(ｃ)段階は、
(ｃ１) 前記複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、所定の第１大きさ以下の部分メッシュを結合してあらゆる部分メッシュが一定の大きさを有するように再構成する段階と、
(ｃ２) 再構成された部分メッシュのうち、各部分メッシュ内のメッシュ情報を所定の第２大きさのビットストリーム単位で分割して符号化する段階と、
(ｃ３) 前記ビットストリームに前記方向性情報を追加して符号化する段階と、
含むことを特徴とする請求項６に記載の漸進３次元メッシュ情報の符号化方法。
【請求項８】
前記圧縮されたビットストリームは、再構成された各部分メッシュを構成する頂点２進ツリーのヘッダ及び三角形２進ツリーのヘッダと、前記(ｃ２)段階で所定の第２大きさを有するビットストリーム単位で分割される複数個の頂点２進ツリーからなる各ビットストリーム及び複数の三角形２進ツリーからなる各ビットストリームと、を含むことを特徴とする請求項７に記載の漸進３次元メッシュ情報の符号化方法。
【請求項９】
前記(ｃ１)段階で再構成された部分メッシュに対する三角形２進ツリーに含まれる分岐三角形にある２つのブランチの大きさと所定の基準三角形の個数とを考慮して、前記分岐三角形の個数が前記所定の基準三角形個数より多い場合、相対的に小さなブランチが先に符号化されるように前記方向性情報として示すことを特徴とする請求項８に記載の漸進３次元メッシュ情報の符号化方法。
【請求項１０】
前記(ｃ)段階は、各部分メッシュに対して三角形２進ツリー情報を構成し、三角形２進ツリーを構成する三角形の数がＮであり、Ｍは０以上でＮ以下である整数である場合、Ｎ個のtrun単位とＭ個のtleaf単位とを三角形マーチング情報（triangle marching information）と多角形エッジ情報（polygonal edge information）と分離して構成することによって、エントロピー符号化効率及びレンダリング効率を高めることを特徴とする請求項６に記載の漸進３次元メッシュ情報の符号化方法。
【請求項１１】
３次元メッシュ情報が漸進的に復元できるように符号化する装置において、
３次元メッシュを複数個の段階別メッシュ（MOL）で構成し、前記段階別メッシュを各々複数の部分メッシュ（MCOM）に分割する３次元データ分析部と、
前記部分メッシュ単位でビットストリームを形成して符号化する複数個の部分メッシュ符号化部と、
前記符号化された部分メッシュを圧縮されたビットストリームに統合するマルチプレクサと、
を備え、前記部分メッシュ単位で形成されたビットストリームは、各部分メッシュ内のメッシュデータとして頂点２進ツリー情報と三角形２進ツリー情報とを含むことを特徴とする漸進３次元メッシュ情報の符号化装置。
【請求項１２】
３次元メッシュを漸進的に復元できるように符号化する装置において、
前記３次元メッシュを複数個の段階別メッシュ（MOL）で構成し、前記段階別メッシュを各々複数個の部分メッシュ（MCOM）に分割する３次元データ分割部と、
前記複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、所定の第１大きさ以下の部分メッシュを結合してあらゆる部分メッシュが一定の大きさを有するように再構成する３次元データ分類/結合部と、
再構成された部分メッシュのうち、各部分メッシュ内のメッシュ情報を所定の第２大きさを有するビットストリーム単位で分割して符号化する複数個の部分別符号化部と、
前記符号化されたメッシュ情報を圧縮されたビットストリームに統合するマルチプレクサと、
を備えることを特徴とする漸進３次元メッシュ情報の符号化装置。
【請求項１３】
前記３次元データ分類/結合部は、現在部分メッシュを構成する頂点２進ツリーにある頂点の総個数が所定の第１個数より少ない場合、前記現在部分メッシュは符号化される次の部分メッシュと統合し、符号化される部分メッシュは頂点の総個数が所定の第２個数より多い頂点からなる頂点２進ツリーを有するように再構成することを特徴とする請求項１２に記載の漸進３次元メッシュ情報の符号化装置。
【請求項１４】
前記複数個の部分別符号化部は、前記各部分メッシュ内のメッシュ情報を構成する頂点２進ツリー情報及び三角形２進ツリー情報を所定の第３個数の頂点と所定の第４個数の三角形とに分割することを特徴とする請求項１２に記載の漸進３次元メッシュ情報の符号化装置。
【請求項１５】
３次元メッシュ情報を漸進的に復元できるように符号化する装置において、
前記３次元メッシュを複数個の段階別メッシュ（MOL）で構成し、前記段階別メッシュを各々複数個の部分メッシュ（MCOM）に分割する３次元データ分割部と、
前記複数個の部分メッシュを各部分メッシュの大きさ情報に従って分類し、所定の第１大きさ以下の部分メッシュを統合してあらゆる部分メッシュが一定の大きさを有するように再構成する３次元データ分類/結合部と、
再構成される部分メッシュに対して三角形２進ツリー情報の分岐三角形（branch triangle）から分岐されるブランチの符号化順序を示す方向性情報を追加する方向性情報決定部と、
再構成される部分メッシュに対して各部分メッシュ内のメッシュ情報を所定の第２大きさを有するビットストリーム単位で分割して符号化する複数個の部分別符号化部と、
符号化されたメッシュ情報を圧縮されたビットストリームに統合するマルチプレクサと、
を備えることを特徴とする漸進３次元メッシュ情報の符号化装置。
【請求項１６】
再構成された部分メッシュに対する三角形２進ツリーに含まれる分岐三角形にある２つのブランチの大きさと所定の基準三角形個数とを考慮して、前記分岐三角形の個数が前記所定の基準三角形個数より多い場合、相対的に小さいブランチが先に符号化されるように前記方向性情報として示すことを特徴とする請求項１５に記載の漸進３次元メッシュ情報の符号化装置。