(57)【特許請求の範囲】
【請求項１】
3次元体積データ符号化装置における3次元体積データ符号化方法であって、
(a)適応的オクトツリー変換部が、3次元体積データを、ノードに所定のラベルが付与された適応的オクトツリーデータに変換する段階と、
(b)ノード符号化部が前記ラベルを参照して、前記適応的オクトツリーのノードを、子ノード間に優先順位を付与する幅優先探索方式により、ルートノードからリーフノードまで符号化する段階と、
(c)ビットストリーム生成部が、所定のヘッダー情報と前記符号化されたノードデータとによりビットストリームを生成する段階と、を含み、
前記ノードに所定のラベルが付与された適応的オクトツリーデータ変換は、
3次元データを8個の領域に分割して、オクトツリーを生成する段階と、
前記オクトツリーの各ノードに所定のラベルを付与しつつ、ノードの大きさが一つのボクセルになるまで、前記オクトツリーの各ノードが示す３次元領域を８個の領域に分割し、子ノードの数が８個ではない場合には、８個にするために仮想のボクセルを付加し、各ノードが示す３次元領域を構成する下位ボクセルが、すべてオブジェクトを含まないボクセルより構成される場合（Ｗ）と、ノードが示す３次元領域の下位ボクセルが、オブジェクトを含むボクセルより構成される場合（Ｂ）には、あらゆる下位ボクセルを、オブジェクトを含むボクセルとして臨時処理し、そのボクセルに含まれる次位のノードの詳細情報を示すＤＩＢ情報と、８個の下位ノードに細分されるＳノードかノード内の体積素がＰＰＭ復号化によって復号化されるＰノードかを示す情報とにより定義することを含み、
前記分割は、
前記３次元データの幅、高さ、深さのそれぞれを、前記各ボクセル数が偶数である場合には、半分ずつになるように、奇数である場合には、１ボクセル差になるように分割し、前後、左右、上下の各方向のうち、何れか一方のみが１ボクセル多くなるように行われ、
前記(c)段階のビットストリームは、
3次元オブジクトに対する幅、高さ及び深さ情報からなる解像度情報を含むヘッダと、符号化されたオクトツリーのノードデータと、を含むことを特徴とする3次元体積データ符号化方法。
【請求項２】
前記（ａ）段階は、
（ａ１）３次元体積データがポイントテクスチャデータであれば、３次元バウンディングボリュームを使用してボクセルデータに変換する段階と、
（ａ２）ボクセルデータまたはオクトツリーデータを、ノードに所定のラベルが付与された適応的オクトツリーに変換する段階と、を含むことを特徴とする請求項１に記載の３次元体積データ符号化方法。
【請求項３】
前記所定のラベルは、
前記３次元体積データがオクトツリーで表現されるとき、前記オクトツリーの各ノードに対し、前記ノードが示す３次元領域をノード領域であるとするとき、
ノード領域の下位ボクセルが、すべてオブジェクトを含まないボクセルより構成されるノードである場合（Ｗ）と、
ノード領域の下位ボクセルが、オブジェクトを含むボクセルより構成されるノードである場合（Ｂ）と、
ノード領域の下位ボクセルの値が、ＰＰＭアルゴリズムにより符号化されるノードである場合（Ｐ）と、
ラベルで表示された下位ノードを有するノードである場合（Ｓ）と、
子ノードの数が８個ではない場合に、８個にするために付加された仮想のボクセルである場合（Ｅ）と、を区分することを特徴とする請求項１に記載の３次元体積データ符号化方法。
【請求項４】
前記ラベルが‘Ｅ’であるノードは、符号化されていないことを特徴とする請求項３に記載の３次元体積データ符号化方法。
【請求項５】
前記（ｂ）段階のオクトツリーのノードデータ符号化は、
Ｓノード符号化であるかＰノード符号化であるかを選択して、その符号化種類情報を生成する段階と、
前記符号化種類情報がＳノード符号化であれば、Ｓノードの詳細情報を符号化する段階と、
前記符号化種類情報がＰノード符号化であれば、Ｐノードの詳細情報を符号化することを特徴とする請求項３に記載の３次元体積データ符号化方法。
【請求項６】
前記Ｓノード詳細情報は、
子ノードの色情報平均値と、
８個の子ノードがそれぞれ存在するか否かを示すフラグ情報と、を含むことを特徴とする請求項５に記載の３次元体積データ符号化方法。
【請求項７】
前記色情報平均値は、
ＤＰＣＭ符号化およびエントロピ符号化されたものであることを特徴とする請求項６に記載の３次元体積データ符号化方法。
【請求項８】
前記フラグ情報は、
エントロピ符号化されることを特徴とする請求項６に記載の３次元体積データ符号化方法。
【請求項９】
前記Ｐノード詳細情報は、
該当ノードのボクセルの色情報と、
所定個数のコンテクストを使用して定義される該当ノードのボクセルの深さ情報と、を含むことを特徴とする請求項５に記載の３次元体積データ符号化方法。
【請求項１０】
前記色情報は、
ＤＰＣＭ符号化およびエントロピ符号化されることを特徴とする請求項９に記載の３次元体積データ符号化方法。
【請求項１１】
前記深さ情報は、
ＰＰＭ符号化されることを特徴とする請求項１０に記載の３次元体積データ符号化方法。
【請求項１２】
前記（ｃ）段階は、
前記符号化されたノードデータをエントロピ符号化し、前記所定のヘッダ情報を符号化することを特徴とする請求項１に記載の３次元体積データ符号化方法。
【請求項１３】
前記ヘッダは、
ノード符号化時に、ルートノードからリーフノードまでのすべてのノードを符号化する無損失符号化、および、開始ノードから特定のノードのみまでを符号化する損失符号化を示すための復号化率情報を更に備えることを特徴とする請求項１に記載の３次元体積データ符号化方法。
【請求項１４】
前記ヘッダは、
深さ映像基盤表現データのバージョン情報を更に備えることを特徴とする請求項１に記載の３次元体積データ符号化方法。
【請求項１５】
ボクセルデータまたはオクトツリーデータを、ノードに所定のラベルが付与された適応的オクトツリーに変換する適応的オクトツリー変換部と、
前記ラベルを参照して、前記適応的オクトツリーのノードを、子ノード間に優先順位を付与する幅優先探索方式により、ルートノードからリーフノードまで符号化するノード符号化部と、
前記符号化されたノードデータと所定のヘッダ情報とを利用して、ビットストリームを生成するビットストリーム生成部と、を含み、
前記適応的オクトツリー変換部は、
３次元データを８個の領域に分割して、オクトツリーを生成するオクトツリー生成部と、前記オクトツリーの各ノードに所定のラベルを付与しつつ、ノードの大きさが一つのボクセルになるまで、前記オクトツリーの各ノードが示す３次元領域を８個の領域に分割し、子ノードの数が８個ではない場合には、８個にするために仮想のボクセルを付加し、ノードが示す３次元領域を構成する下位ボクセルが、すべてオブジェクトを含まないボクセルより構成される場合（Ｗ）と、ノードが示す３次元領域の下位ボクセルが、オブジェクトを含むボクセルより構成される場合（Ｂ）には、あらゆる下位ボクセルを、オブジェクトを含むボクセルとして臨時処理し、そのボクセルに含まれる次位のノードの詳細情報を示すＤＩＢ情報と、８個の下位ノードに細分されるＳノードかノード内の体積素がＰＰＭ復号化によって復号化されるＰノードかを示す情報とにより定義する適応的オクトツリー生成部と、を含み、
前記分割は、
前記３次元データの幅、高さ、深さのそれぞれを、前記各ボクセル数が偶数である場合には、半分ずつになるように、奇数である場合には、１ボクセル差になるように分割し、前後、左右、上下の各方向のうち、何れか一方のみが１ボクセル多くなるように行われ、前記ビットストリーム生成部は、
３次元オブジェクトに対する幅、高さおよび深さ情報からなる解像度情報を含むヘッダと、符号化されたオクトツリーのノードデータと、により、ビットストリームを生成することを特徴とする３次元体積データ符号化装置。
【請求項１６】
３次元体積データがポイントテクスチャデータであれば、３次元バウンディングボリュームを使用して、ボクセルデータに変換する体積素生成部を更に備えることを特徴とする請求項１５に記載の３次元体積データ符号化装置。
【請求項１７】
前記所定のラベルは、
前記３次元体積データがオクトツリーで表現されるとき、前記オクトツリーの各ノードに対し、前記ノードが示す３次元領域をノード領域であるとするとき、
ノード領域の下位ボクセルが、すべてオブジェクトを含まないボクセルより構成されるノードである場合（Ｗ）と、
ノード領域の下位ボクセルが、オブジェクトを含むボクセルより構成されるノードである場合（Ｂ）と、
ノード領域の下位ボクセルの値が、ＰＰＭアルゴリズムによって符号化されるノードである場合（Ｐ）と、
ラベルで表示された下位ノードを有するノードである場合（Ｓ）と、
子ノードの数が８個ではない場合に、８個にするために付加された仮想のボクセルである場合（Ｅ）と、を区分することを特徴とする請求項１５に記載の３次元体積データ符号化装置。
【請求項１８】
前記ラベルが‘Ｅ’であるノードは、符号化されていないことを特徴とする請求項１５に記載の３次元体積データ符号化装置。
【請求項１９】
前記ノード符号化部は、
Ｓノード符号化であるかＰノード符号化であるかを選択して、符号化種類情報を生成するＳＯＰ情報選択部と、
前記符号化種類情報がＳノード符号化であれば、Ｓノードの詳細情報を符号化するＳノード符号化部と、
前記符号化種類情報がＰノード符号化であれば、Ｐノードの詳細情報を符号化するＰノード符号化部と、を含むことを特徴とする請求項１７に記載の３次元体積データ符号化装置。
【請求項２０】
前記Ｓノード符号化部は、
子ノードの色情報平均値と、
８個の子ノードがそれぞれ存在するか否かを示すフラグ情報と、を符号化することを特徴とする請求項１９記載の３次元体積データ符号化装置。
【請求項２１】
前記色情報平均値は、
ＤＰＣＭ符号化およびエントロピ符号化されることを特徴とする請求項２０に記載の３次元体積データ符号化装置。
【請求項２２】
前記フラグ情報は、
エントロピ符号化されることを特徴とする請求項２０に記載の３次元体積データ符号化装置。
【請求項２３】
前記Ｐノード符号化部は、
所定個数のコンテクストを使用して、該当ノードのボクセルの深さ情報と、該当ノードのボクセルの色情報と、を符号化することを特徴とする請求項１９に記載の３次元体積データ符号化装置。
【請求項２４】
前記色情報は、
ＤＰＣＭ符号化およびエントロピ符号化することを特徴とする請求項２３に記載の３次元体積データ符号化装置。
【請求項２５】
前記深さ情報は、
ＰＰＭ符号化することを特徴とする請求項２３に記載の３次元体積データ符号化装置。
【請求項２６】
前記ビットストリーム生成部は、
前記ノードデータをエントロピ符号化するエントロピ符号化部と、
前記所定のヘッダ情報を符号化するヘッダ符号化部と、を備えることを特徴とする請求項１５に記載の３次元体積データ符号化装置。
【請求項２７】
前記ヘッダは、
ノード符号化時に、ルートノードから最後のノードまでのすべてのノードを符号化する無損失符号化、および、開始ノードから特定ノードまで符号化する損失符号化を示すための復号化率情報を更に備えることを特徴とする請求項１５に記載の３次元体積データ符号化装置。
【請求項２８】
前記ヘッダは、
深さ映像基盤表現データのバージョン情報を更に備えることを特徴とする請求項２７に記載の３次元体積データ符号化装置。
【請求項２９】
３次元体積データ復号化装置における３次元データ復号化方法であって、
（ａ）ヘッダ復号化部が、ビットストリームから少なくともオブジェクトの解像度情報を含むヘッダ情報を抽出して復号化する段階と、
（ｂ）ノード復号化部が、前記ヘッダの解像度情報を利用してノードの数を計算し、子ノード間に優先順位を付与する幅優先探索方式により、優先順位キューを用いてルートノードからリーフノードまでツリーの各ノードを復号化する段階と、
（ｃ）適応的ツリー復号化部が、前記復号化されたノードを利用して適応的ツリーを復元する段階と、を含み、
前記（ａ）段階の解像度は、
３次元オブジェクトの幅、高さおよび深さデータからなることを特徴とする3次元体積データ復号化方法。
【請求項３０】
前記（ａ）段階は、
ノード復号化時に、ツリーのルートノードから特定ノードまで復号化する損失復号化程度、およびルートノードから最後のノードまでのすべてのノードを復号化する無損失復号化を示す復号化率情報を抽出して復号化する段階を更に備えることを特徴とする請求項２９に記載の３次元体積データ復号化方法。
【請求項３１】
前記（ａ）段階は、
ビットストリームから少なくとも、オブジェクトの解像度情報および深さ映像基盤表現データのバージョン情報を含むヘッダ情報を抽出して復号化することを特徴とする請求項２９に記載の３次元体積データ復号化方法。
【請求項３２】
前記（ａ）段階は、
ビットストリームからノード情報を抽出してエントロピ復号化する段階を更に備えることを特徴とする請求項２９に記載の３次元体積データ復号化方法。
【請求項３３】
前記（ｂ）段階は、
前記解像度情報を利用して計算されたノードの数と、前記復号化率情報を利用して復号化するノードの数とを計算し、子ノード間に優先順位を付与する変形された幅優先探索方式により、ルートノードから始まってリーフノード方向に前記復号化するノードの数ほどツリーのノードを復号化することを特徴とする請求項３０に記載の３次元体積データ復号化方法。
【請求項３４】
前記幅優先探索方式は、
優先順位キューを利用して、前記優先順位キューに復号化するノードのインデックスをプッシュおよびポップすることにより行われることを特徴とする請求項２９に記載の３次元体積データ復号化方法。
【請求項３５】
前記優先順位は、
ノードの１番目の子ノードは２番目の子ノードより優先順位が高く、２番目の子ノードは３番目の子ノードより高く、最後の子ノードは優先順位が最も低いことを特徴とする請求項３４に記載の３次元体積データ復号化方法。
【請求項３６】
前記（ｂ）段階のツリーノードの復号化は、
ツリーのノードが、８個の下位ノードに細分されるＳノードのＳノード符号化であるかノード内の体積素がＰＰＭ復号化によって復号化されるＰノードのＰノード符号化であるかを示す符号化種類情報を復号化する段階と、
前記符号化種類情報が、Ｓノード符号化であることを示せば、前記復号化しようとするノードがＳノードであると判断し、前記Ｓノードを復号化する段階と、
前記符号化種類情報が、Ｐノード符号化であることを示せば、前記復号化しようとするノードがＰノードであると判断し、前記Ｐノードを復号化する段階と、を含むことを特徴とする請求項３５に記載の３次元体積データ復号化方法。
【請求項３７】
前記Ｓノード復号化は、
前記Ｓノードの色情報をエントロピ復号化する段階と、
前記Ｓノードの子ノードのそれぞれに対して、各ノードに付与されているノードラベルが、オブジェクトを含まないボクセルより構成されるノードである場合を示すＷであるか、オブジェクトを含むボクセルより構成されるノードである場合を示すＢであるかを判断する段階と、
前記子ノードのラベルがＷであれば、サブツリーノードの数を計算して前記サブツリーノードの数以上は復号化しない段階と、
前記子ノードのラベルがＢであれば、前記優先順位キューに前記子ノードのインデックスをプッシュする段階と、を含むことを特徴とする請求項３６に記載の３次元体積データ復号化方法。
【請求項３８】
前記Ｐノード復号化は、
ツリーノードのインデックスから幅、高さ、深さデータからなる３次元ボリューム領域を計算する段階と、
前記ボリューム領域に対し、ボクセルが存在するか否かをチェックして、ボクセルが存在すれば、前記ボクセルの色情報をエントロピ復号化する段階と、を含むことを特徴とする請求項３６に記載の３次元体積データ復号化方法。
【請求項３９】
前記復元された適応的ツリーデータをボクセルデータに変換する段階を更に備えることを特徴とする請求項２９に記載の３次元体積データ復号化方法。
【請求項４０】
ビットストリームから少なくともオブジェクトの解像度情報を含むヘッダ情報を抽出して復号化するヘッダ復号化部と、
前記ヘッダの解像度情報を利用してノードの数を計算し、子ノード間に優先順位を付与する幅優先探索方式により、優先順位キューを用いてルートノードからリーフノードまでツリーの各ノードを復号化するノード復号化部と、
前記復号化されたノードを利用して適応的ツリーを復元する適応的ツリー復元部と、を含み、
前記ヘッダの解像度情報は、
３次元オブジェクトの幅、高さおよび深さデータからなることを特徴とする3次元体積データ復号化装置。
【請求項４１】
前記ヘッダ復号化部は、
前記ヘッダがノード復号化時に、ツリーのルートノードから特定ノードまで復号化する損失復号化程度、およびルートノードからリーフノードまでのすべてのノードを復号化する無損失復号化を示す復号化率情報を更に備えるとき、ビットストリームから前記復号化率情報を抽出して復号化することを特徴とする請求項４０に記載の３次元体積データ復号化装置。
【請求項４２】
前記ヘッダ復号化部は、
ビットストリームから少なくとも、オブジェクトの解像度情報および深さ映像基盤表現データのバージョン情報を含むヘッダ情報を抽出して復号化することを特徴とする請求項４０に記載の３次元体積データ復号化装置。
【請求項４３】
ビットストリームからノード情報を抽出してエントロピ復号化するエントロピ復号化部を更に備えることを特徴とする請求項４０に記載の３次元体積データ復号化装置。
【請求項４４】
前記ノード復号化部は、
前記解像度情報を利用して計算されたノードの数と、前記復号化率情報を利用して復号化するノードの数とを計算し、子ノード間に優先順位を付与する変形された幅優先探索方式により、ルートノードから始まってリーフノード方向に前記計算された復号化するノードの数ほどツリーのノードを復号化することを特徴とする請求項４１に記載の３次元体積データ復号化装置。
【請求項４５】
前記幅優先探索方式は、
優先順位キューを利用して、前記優先順位キューに復号化するノードのインデックスをプッシュおよびポップすることにより行うことを特徴とする請求項４０に記載の３次元体積データ復号化装置。
【請求項４６】
前記優先順位は、
ノードの１番目の子ノードが２番目の子ノードより高く、２番目の子ノードが３番目の子ノードより高く、最後の子ノードが最も低いことを特徴とする請求項４４に記載の３次元体積データ復号化装置。
【請求項４７】
前記ノード復号化部は、
ツリーのノードが、８個の下位ノードに細分されるＳノードのＳノード符号化であるかノード内の体積素がＰＰＭ復号化によって復号化されるＰノードのＰノード符号化であるかを示す符号化種類情報（ＳＯＰ）を抽出して復元するＳＯＰ復元部と、
前記符号化種類情報がＳノード符号化であることを示せば、前記復号化しようとするノードがＳノードであると判断し、前記Ｓノードを復号化するＳノード復号化部と、
前記符号化種類情報がＰノード符号化であることを示せば、前記復号化しようとするノードがＰノードであると判断し、前記Ｐノードを復号化するＰノード復号化部と、を含むことを特徴とする請求項４６に記載の３次元体積データ復号化装置。
【請求項４８】
前記Ｓノード復号化部は、
前記Ｓノードの色情報をエントロピ復号化する色情報復号化部と、
前記Ｓノードの子ノードのそれぞれに対して、各ノードに付与されているノードラベルが、オブジェクトを含まないボクセルより構成されるノードである場合を示すＷであるか、オブジェクトを含むボクセルより構成されるノードである場合を示すＢであるかを判断するＷＯＢ判断部と、
前記子ノードのラベルがＷであれば、サブツリーノードの数を計算して、前記サブツリーノードの数以上は復号化しないＷノード処理部と、
前記子ノードのラベルがＢであれば、前記優先順位キューに前記子ノードのインデックスをプッシュするＢノード処理部と、を含むことを特徴とする請求項４７に記載の３次元体積データ復号化装置。
【請求項４９】
前記Ｐノード復号化部は、
ツリーノードのインデックスから幅、高さ、深さデータからなる３次元ボリューム領域を計算して、前記領域内にボクセルが存在するか否かを検査するボクセルＰＰＭ復号化部と、
前記検査結果ボクセルが存在すれば、前記ボクセルの色情報をエントロピ復号化するボクセル色復号化部と、を含むことを特徴とする請求項４７に記載の３次元体積データ復号化装置。
【請求項５０】
前記復元された適応的ツリーを利用して、ボクセルデータを復元するボクセルデータ復元部を更に備えることを特徴とする請求項４０に記載の３次元体積データ復号化装置。
【請求項５１】
請求項１ないし１４、２９ないし３９のうち何れか１項に記載の発明をコンピュータで実行させるためのプログラムを記録したコンピュータ可読記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元体積データの符号化および復号化に係り、更に詳細には、ポイントテクスチャ、体積素（ボクセル：voxel）、オクトツリー（oct-tree or octree）データのうち、何れか一つからなる３次元体積データを符号化／復号化する方法および装置に関する。
【背景技術】
【０００２】
３次元オブジェクト（object：物体）を表現する手法のうち、多角形メッシュモデル（polygonal mesh model）を使用する方法が、近年、広く用いられている。一方、３次元オブジェクトを多角形メッシュモデルではない現実映像や合成映像により構成された参照映像の集合を利用して表現する手法に、深さ映像基盤表現（Depth Image-Based Representation：以下、ＤＩＢＲ）という手法があり、２００３年にＭＰＥＧ−４のアニメーションフレームワーク拡張規格（Animation Framework eXtension：ＡＦＸ）として採択されている。図１に、３次元オブジェクトを取り囲む六面体の各面に投影される映像で構成される参照映像の例を示す。各参照映像には、それぞれ対応する色映像および深さ映像が存在するが、色映像は、３次元オブジェクトの表面の各ポイントの色を示し、深さ映像は、各面から３次元オブジェクトの表面の各ポイントまでの距離値を示す。図１では、各面で見られる６個の深さ映像と６個の色映像の全部で１２個の参照映像が図示されている。
【０００３】
ＤＩＢＲ手法の長所は、複雑な多角形メッシュモデルを使用しなくともよいという点と、映像を利用するため、高画質で３次元オブジェクトを視覚化できるという点にある。ＤＩＢＲのためのフォーマットには３種類がある。単純テクスチャ、ポイントテクスチャおよびオクトツリー映像フォーマットである。そのうち、ポイントテクスチャフォーマットは、図２のように、３次元オブジェクトをサンプリングするすべての点（ポイント）を、一平面上の各スキャンラインに並べて表現する。ポイントテクスチャの各ポイントは、色（color）と深さ（depth）で表現する。ここで、深さとは、平面からポイントまでの距離である。更に、ポイントのその他の属性を含めることもできる。
【０００４】
図２のように、３次元オブジェクトの表面を構成するポイントを、一平面に投影して平面の各深さラインに沿って並べ得るため、ポイントテクスチャフォーマットは、一般に、複数の階層より構成される。そのような理由で、ポイントテクスチャフォーマットは、多様な表面により構成される複雑な３次元オブジェクトを表現できるという長所を有する。しかし、高いサンプリング密度で写実的に３次元オブジェクトを表現せねばならない場合、データの量が多くなる。したがって、それを効率的に圧縮できる方法が必要である。そして、ポイントテクスチャフォーマットデータを圧縮できる方法が必要である。
【０００５】
従来の圧縮方法は、伝送される情報の量によって最適化する必要があり、そのサイズをさらに減小させる余地がある。また、圧縮されたビットストリームを復元するとき、より自然な映像に視覚化する方法が必要である。
【０００６】
２００３年７月に開催されたＭＰＥＧ会議のＭＰＥＧ−４ ＡＦＸ部会において、ＰＰＭ（Prediction by Partial Matching）法を利用したオクトツリー圧縮方法が提案された。しかし、この方法では、プログレッシブなビットストリームを読み取って復元するとき、滑らかな視覚化を生成することができない。そして、この方法では、オクトツリー圧縮方法を使用するため、体積データの解像度は、幅、高さ、深さの値が、それぞれ同じでなければならないという制約があり、固定された解像度のデータしか圧縮できないという短所がある。すなわち、幅、高さ、深さが、それぞれ異なる任意の解像度を有するデータを圧縮することはできないのである。
【０００７】
したがって、任意の解像度を有する３次元オブジェクトデータを効率的に圧縮することはもとより、プログレッシブな伝送および復元時に、より自然な映像へと視覚化することが可能な方法が必要とされている。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明が達成しようとする技術的課題は、任意の解像度を有する３次元体積データを符号化するために、適応的クワッドツリー、オクトツリーおよび２n進ツリーの生成方法を提供することである。
【０００９】
また、本発明が達成しようとする技術的課題は、３次元体積データを効率的に符号化し、任意の解像度を有する３次元体積データの符号化と、プログレッシブな圧縮とを可能とする機能を有する、３次元体積データ符号化方法および３次元体積データ符号化装置を提供することである。
【００１０】
本発明が達成しようとする他の技術的課題は、３次元体積データの解像度に関係なく、任意の解像度を有する３次元体積データを復号（化）できる機能と、適応的オクトツリーを使用してプログレッシブな圧縮に対する復元とを可能とする、３次元体積データ復号化方法および３次元体積データ復号化装置を提供することである。
【課題を解決するための手段】
【００１１】
前記技術的課題を達成するための本発明による適応的クワッドツリーの生成方法は、（ａ）２次元データを分割し、４個の領域より構成されるクワッドツリーを生成する段階と、（ｂ）前記クワッドツリーに分割された２次元データの４個の領域をそれぞれノードとして、分割された４個の領域の大きさが１ピクセルになるまで、順次、下位クワッドツリーに分割する段階と、を含む。そして、前記（ａ）段階および（ｂ）段階のクワッドツリーへの分割は、前記２次元データの縦または横のピクセル数が、偶数である場合には、半分ずつになるように、奇数である場合には、１ピクセル差になるように分割し、前記分割された４個の領域がすべて、４個のピクセルにならない場合には、仮想のピクセルを付加して、それぞれ４個のピクセルより構成される下位クワッドツリーを生成する。前記１ピクセル差とする分割は、左右に分割される場合には、左右のうち、何れか一方のみが１ピクセル多く、上下に分割される場合には、上下のうち、何れか一方のみが１ピクセル多くなる。
【００１２】
前記技術的課題を達成するための本発明による適応的オクトツリーの生成方法は、（ａ）３次元データを分割し、８個の領域より構成されるオクトツリーを生成する段階と、（ｂ）前記オクトツリーに分割された３次元データの８個の領域をそれぞれノードとして、分割された８個の領域の大きさが１ボクセルになるまで、順次、下位オクトツリーに分割する段階と、を含む。そして、前記（ａ）段階および（ｂ）段階のオクトツリーへの分割は、前記３次元データの縦、横、または高さのボクセル数が、偶数である場合には、半分ずつになるように、奇数である場合には、１ボクセル差になるように分割する。さらに、前記分割された８個の領域がすべて８個のボクセルにならない場合には、仮想のボクセルを付加して、それぞれ８個のボクセルより構成される下位オクトツリーを生成する。このとき、前記１ボクセル差の（前後、左右、上下の各方向の）分割は、前後、左右、上下の各方向のうち、（常に）何れか一方のみが１ボクセル多くなる（かつ、一定の方向に追加される）ように行われる。
【００１３】
前記技術的課題を達成するための本発明による適応的２n進ツリーの生成方法は、（ａ）ｎ次元データを、２n個の領域より構成される２n進ツリーに分割する段階と、（ｂ）前記２n進ツリーに分割されたｎ次元データの２n個の領域をそれぞれノードとして、分割された２n個の領域の大きさが一つの単位体になるまで、順次、下位２n進ツリーに分割する段階と、を含む。前記（ａ）段階および（ｂ）段階の２n進ツリーへの分割は、前記ｎ次元データの各方向での単位体数が、偶数である場合には、半分ずつになるように、奇数である場合には、１単位体数差になるように分割する。そして、前記２n個の領域がすべて２n個の単位体にならない場合には、仮想の単位体を付加して、２n個の単位体より構成される下位２n進ツリーを生成し、前記１単位体数差の各方向の分割は、各方向のうち、（常に）何れか一方のみが１単位体多くなる（かつ、一定の方向に追加される）ように行われる。
【００１４】
前記他の技術的課題を達成するための本発明による３次元体積データ符号化方法は、（ａ）３次元体積データを、ノードに所定のラベルが付与された適応的オクトツリーデータに変換する段階と、（ｂ）前記ラベルを参照して、前記適応的オクトツリーのノードを、子ノード間に優先順位を付与する幅優先探索方式（Breadth-First Search：以下、ＢＦＳ）により、ルートノードからリーフノード（末端ノード）まで符号化する段階と、（ｃ）所定のヘッダ情報と前記符号化されたノードデータとによりビットストリームを生成する段階と、を含むことを特徴とする。
【００１５】
前記（ａ）段階は、（ａ１）３次元体積データがポイントテクスチャデータであれば、３次元バウンディングボリュームを使用して体積素（ボクセル）データに変換する段階と、（ａ２）体積素データまたはオクトツリーデータを、ノードに所定のラベルが付与された適応的オクトツリーに変換する段階と、を含むことが好ましい。
【００１６】
前記（ａ２）段階（における前記ノードに所定のラベルが付与された適応的オクトツリーデータ変換）は、３次元データを８個の領域に分割してオクトツリーを生成する段階と、前記オクトツリーの各ノードに所定のラベルを付与しつつ、ノードの大きさが一つのボクセルになるまで、前記オクトツリーの各ノードが示す３次元領域を８個の領域に分割し、子ノードの数が８個ではない場合には、８個にするために仮想の体積素を付加し、各ノードが示す３次元領域を構成する下位体積素が、すべてオブジェクトを含まない体積素より構成される場合（Ｗ）と、ノードが示す３次元領域の下位体積素が、オブジェクトを含む体積素より構成される場合（Ｂ）には、あらゆる下位体積素が、オブジェクトを含む体積素として臨時処理し、その体積素に含まれる次位のノードのＤＩＢ情報と、ＳノードかＰノード化を示す情報と、により定義することを含む。また、前記分割は、前記３次元データの幅、高さ、深さのそれぞれを、前記各ボクセル数が偶数である場合には、半分ずつになるように、奇数である場合には、１ボクセル差になるように分割し、前後、左右、上下の各方向のうち、（常に）何れか一方のみが１ボクセル多くなる（かつ、一定の方向に追加される）ように行われる。
【００１７】
前記所定のラベルは、前記３次元体積データがオクトツリーで表現されるとき、前記オクトツリーの各ノードに対し、前記ノードが示す３次元領域をノード領域であるとするとき、ノード領域の下位体積素が、すべてオブジェクトを含まない体積素より構成されるノードである場合（Ｗ）と、ノード領域の下位体積素が、オブジェクトを含む体積素より構成されるノードである場合（Ｂ）と、ノード領域の下位体積素の値が、ＰＰＭアルゴリズムにより符号化されるノードである場合（Ｐ）と、ラベルで表示された下位ノードを有するノードである場合（Ｓ）と、子ノードの数が８個ではない場合に８個にするために付加された仮想の体積素である場合（Ｅ）と、を区分することが好ましい。前記ラベルが‘Ｅ’であるノードは、符号化しないことが好ましい。
【００１８】
前記（ｂ）段階のオクトツリーのノードデータ符号化は、Ｓノード符号化であるかＰノード符号化であるかを選択して、その符号化種類情報（ＳＯＰ）を生成する段階と、前記符号化種類情報がＳノード符号化であれば、Ｓノードの詳細情報を符号化する段階と、前記符号化種類情報がＰノード符号化であれば、Ｐノードの詳細情報を符号化することが好ましい。
【００１９】
前記Ｓノード詳細情報は、子ノードの色情報平均値と、８個の子ノードがそれぞれ存在するか否かを示すフラグ情報（Ｃｈ１−Ｃｈ８）を含むことが好ましい。前記色情報平均値は、ＤＰＣＭ（Differential Pulse Code Modulation）符号化およびエントロピ符号化されることが好ましい。前記フラグ情報は、エントロピ符号化されることが好ましい。
【００２０】
前記Ｐノード詳細情報は、該当ノードの体積素の色情報と、所定個数のコンテクストを使用して定義される該当ノードの体積素の深さ情報と、を含むことが好ましい。前記色情報は、ＤＰＣＭ符号化およびエントロピ符号化されることが好ましい。前記深さ情報は、ＰＰＭ符号化されることが好ましい。
【００２１】
前記（ｃ）段階のビットストリームは、３次元オブジェクトに対する幅、高さおよび深さ情報からなる解像度情報を含むヘッダと、符号化されたオクトツリーのノードデータを含むことが好ましい。前記ヘッダは、ノード符号化時に、ルートノードからリーフノード（末端のノード）までのすべてのノードを符号化する無損失符号化、および開始ノードから特定のノードまでを符号化する損失符号化を示すための復号化率情報を更に備えることが好ましい。前記ヘッダは、ＤＩＢＲデータのバージョン情報を更に備えることが好ましい。
【００２２】
前記他の技術的課題を達成するための本発明による３次元体積データ符号化装置は、体積素データまたはオクトツリーデータに対し、ノードに所定のラベルが付与された適応的オクトツリーに変換する適応的オクトツリー変換部と、前記ラベルを参照して、前記適応的オクトツリーのノードを、子ノード間に優先順位を付与するＢＦＳにより、ルートノードからリーフノードまで符号化するノード符号化部と、前記符号化されたノードデータと所定のヘッダ情報とを利用して、ビットストリームを生成するビットストリーム生成部と、を含むことを特徴とする。
【００２３】
前記符号化装置は、３次元体積データがポイントテクスチャデータであれば、３次元バウンディングボリュームを使用して、体積素データに変換する体積素生成部を更に備えることが好ましい。
【００２４】
前記適応的オクトツリー変換部は、３次元データを８個の領域に分割してオクトツリーを生成するオクトツリー生成部と、前記オクトツリーの各ノードに所定のラベルを付与しつつ、ノードの大きさが一つのボクセルになるまで、前記オクトツリーの各ノードが示す３次元領域を８個の領域に分割し、子ノードの数が８個ではない場合には、８個にするために仮想の体積素を付加し、ノードが示す３次元領域を構成する下位体積素が、すべてオブジェクトを含まない体積素より構成される場合（Ｗ）と、ノードが示す３次元領域の下位体積素が、オブジェクトを含む体積素より構成される場合（Ｂ）には、あらゆる下位体積素を、オブジェクトを含む体積素として臨時処理し、その体積素に含まれる次位のノードのＤＩＢ情報と、ＳノードかＰノードかを示す情報とにより定義する適応的オクトツリー生成部と、を含む。前記分割は、前記３次元データの幅、高さ、深さのそれぞれを、前記各ボクセル数が偶数である場合には、半分ずつになるように、奇数である場合には、１ボクセル差になるように分割し、前後、左右、上下の各方向のうち、（常に）何れか一方のみが１ボクセル多くなる（かつ、一定の方向に追加される）ように行われる。
【００２５】
前記所定のラベルは、前記３次元体積データがオクトツリーで表現されるとき、前記オクトツリーの各ノードに対し、前記ノードが示す３次元領域をノード領域であるとするとき、ノード領域の下位体積素が、すべてオブジェクトを含まない体積素より構成されるノードである場合（Ｗ）と、ノード領域の下位体積素が、オブジェクトを含む体積素より構成されるノードである場合（Ｂ）と、ノード領域の下位体積素の値が、ＰＰＭアルゴリズムにより符号化されるノードである場合（Ｐ）と、ラベルで表示された下位ノードを有するノードである場合（Ｓ）と、子ノードの数が８個ではない場合、８個にするために付加された仮想の体積素である場合（Ｅ）と、を区分することが好ましい。前記ラベルが‘Ｅ’であるノードは、符号化しないことが好ましい。
【００２６】
前記ノード符号化部は、Ｓノード符号化であるかＰノード符号化であるかを選択して、符号化種類情報（ＳＯＰ）を生成するＳＯＰ情報選択部と、前記符号化種類情報がＳノード符号化であれば、Ｓノードの詳細情報を符号化するＳノード符号化部と、前記符号化種類情報がＰノード符号化であれば、Ｐノードの詳細情報を符号化するＰノード符号化部と、を含むことが好ましい。前記Ｓノード符号化部は、子ノードの色情報平均値と、８個の子ノードがそれぞれ存在するか否かを示すフラグ情報（Ｃｈ１−Ｃｈ８）とを符号化することが好ましい。前記色情報平均値は、ＤＰＣＭ符号化およびエントロピ符号化されることが好ましい。前記フラグ情報は、エントロピ符号化されることが好ましい。前記Ｐノード符号化部は、所定個数のコンテクストを使用して、該当ノードの体積素の深さ情報と、該当ノードの体積素の色情報とを符号化することが好ましい。前記色情報は、ＤＰＣＭ符号化およびエントロピ符号化することが好ましい。前記深さ情報は、ＰＰＭ符号化することが好ましい。
【００２７】
前記ビットストリーム生成部は、３次元オブジェクトに対する幅、高さおよび深さ情報からなる解像度情報を含むヘッダと、符号化されたオクトツリーのノードデータとにより、ビットストリームを生成することが好ましい。前記ヘッダは、ノード符号化時に、ルートノードからリーフノードまでのすべてのノードを符号化する無損失符号化、および開始ノードから特定ノードまで符号化する損失符号化を示すための復号化率情報を更に備えることが好ましい。前記ヘッダは、ＤＩＢＲデータのバージョン情報を更に備えることが好ましい。
【００２８】
前記更に他の技術的課題を達成するための本発明による３次元体積データ復号化方法は、（ａ）ビットストリームから少なくともオブジェクトの解像度情報を含むヘッダ情報を抽出して復号化する段階と、（ｂ）前記ヘッダの解像度情報を利用してノードの数を計算し、子ノード間に優先順位を付与するＢＦＳにより、ルートノードからリーフノードまでツリーの各ノードを復号化する段階と、（ｃ）前記復号化されたノードを利用して適応的ツリーを復元する段階と、を含むことを特徴とする。
【００２９】
前記（ａ）段階の解像度は、３次元オブジェクトの幅、高さおよび深さデータからなることが好ましい。前記（ａ）段階は、ノード復号化時に、ツリーのルートノードから特定ノードまでのみ復号化する損失復号化程度、およびルートノードからリーフノードまでのすべてのノードを復号化する無損失復号化を示す復号化率情報を抽出して復号化する段階を更に備えることが好ましい。
【００３０】
前記（ａ）段階は、ビットストリームから少なくとも、オブジェクトの解像度情報およびＤＩＢＲデータのバージョン情報を含むヘッダ情報を抽出して復号化することが好ましい。前記（ｂ）段階は、前記解像度情報を利用して計算されたノードの数と、前記復号化率情報を利用して復号化するノードの数とを計算し、子ノード間に優先順位を付与する変形されたＢＦＳにより、ルートノードから始まってリーフノード方向に、前記復号化するノードの数ほどツリーのノードを復号化することが好ましい。前記変形されたＢＦＳは、優先順位キューを利用して、前記優先順位キューに復号化するノードのインデックスをプッシュおよびポップすることにより行われることが好ましい。前記優先順位は、ノードの１番目の子ノードが２番目の子ノードより高く、２番目の子ノードが３番目の子ノードより高く、同様に、最後の子ノードは最も低いことが好ましい。
【００３１】
前記（ｂ）段階のツリーノードの復号化は、ツリーのノードが、Ｓノード符号化であるかＰノード符号化であるかを示す符号化種類情報（ＳＯＰ）を復号化する段階と、前記ＳＯＰがＳノード符号化であることを示せば、前記復号化しようとするノードがＳノードであると判断して、前記Ｓノードを復号化する段階と、前記ＳＯＰがＰノード符号化であることを示せば、前記復号化しようとするノードがＰノードであると判断して、前記Ｐノードを復号化する段階と、を含むことが好ましい。前記Ｓノード復号化は、前記Ｓノードの色情報をエントロピ復号化する段階と、前記Ｓノードの子ノードのそれぞれに対して、ノードラベルがＷであるかＢであるかを判断する段階と、前記子ノードのラベルがＷであれば、サブツリーノードの数を計算して、前記サブツリーノードの数ほどは復号化せずに飛ばす段階と、前記子ノードのラベルがＢであれば、前記優先順位キューに前記子ノードのインデックスをプッシュする段階と、を含むことが好ましい。前記Ｐノード復号化は、ツリーノードのインデックスから幅、高さ、深さデータからなる３次元ボリューム領域を計算する段階と、前記ボリューム領域に対してボクセルが存在しているか否かをチェックして、ボクセルが存在すれば、前記ボクセルの色情報をエントロピ復号化する段階と、を含むことが好ましい。
【００３２】
前記復号化方法は、前記復元された適応的ツリーデータをボクセルデータに変換する段階を更に備えることが好ましい。
【００３３】
前記更に他の技術的課題を達成するための本発明による３次元体積データ復号化装置は、ビットストリームから少なくとも、オブジェクトの解像度情報を含むヘッダ情報を抽出して復号化するヘッダ復号化部と、前記ヘッダの解像度情報を利用してノードの数を計算し、子ノード間に優先順位を付与するＢＦＳにより、ルートノードからリーフノードまでツリーの各ノードを復号化するノード復号化部と、前記復号化されたノードを利用して適応的ツリーを復元する適応的ツリー復元部と、を含むことを特徴とする。
【００３４】
前記ヘッダの解像度情報は、３次元オブジェクトの幅、高さおよび深さデータからなることが好ましい。前記ヘッダ復号化部は、前記ヘッダが、ノード復号化時に、ツリーのルートノードから特定ノードまで復号化する損失復号化程度、およびルートノードからリーフノードまでのすべてのノードを復号化する無損失復号化を示す復号化率情報を更に備えるとき、ビットストリームから前記復号化率情報を抽出して復号化することが好ましい。前記ヘッダ復号化部は、ビットストリームから少なくとも、オブジェクトの解像度情報およびＤＩＢＲデータのバージョン情報を含むヘッダ情報を抽出して復号化することが好ましい。
【００３５】
前記ノード復号化部は、前記解像度情報を利用して計算されたノードの数と、前記復号化率情報を利用して復号化するノードの数とを計算し、子ノード間に優先順位を付与する変形されたＢＦＳにより、ルートノードから始まってリーフノード方向に、前記計算された復号化するノードの数ほどツリーのノードを復号化することが好ましい。前記変形されたＢＦＳは、優先順位キューを利用して、前記優先順位キューに復号化するノードのインデックスをプッシュおよびポップすることにより行うことが好ましい。前記優先順位は、ノードの１番目の子ノードが２番目の子ノードより高く、２番目の子ノードが３番目の子ノードより高く、同様に、最後の子ノードが最も低いことが好ましい。
【００３６】
前記ノード復号化部は、ツリーのノードが、Ｓノード符号化であるかＰノード符号化であるかを示す符号化種類情報を抽出して復元するＳＯＰ復元部と、前記ＳＯＰがＳノード符号化であることを示せば、前記復号化しようとするノードがＳノードであると判断して、前記Ｓノードを復号化するＳノード復号化部と、前記ＳＯＰがＰノード符号化であることを示せば、前記復号化しようとするノードがＰノードであると判断して、前記Ｐノードを復号化するＰノード復号化部と、を含むことが好ましい。前記Ｓノード復号化部は、前記Ｓノードの色情報をエントロピ復号化する色情報復号化部と、前記Ｓノードの子ノードの何れに対しても、ノードラベルがＷであるかＢであるかを判断するＷＯＢ（Ｗ ＯＲ Ｂ）判断部と、前記子ノードのラベルがＷであれば、サブツリーノードの数を計算して、前記サブツリーノードの数ほどは復号化せずに飛ばすＷノード処理部と、前記子ノードのラベルがＢであれば、前記優先順位キューに前記子ノードのインデックスをプッシュするＢノード処理部と、を含むことが好ましい。前記Ｐノード復号化部は、ツリーノードのインデックスから幅、高さ、深さデータからなる３次元ボリューム領域を計算して、前記領域内にボクセルが存在するか否かを検査するボクセルＰＰＭ復号化部と、前記検査結果ボクセルが存在すれば、前記ボクセルの色情報をエントロピ復号化するボクセル色復号化部と、を含むことが好ましい。
【００３７】
前記復号化装置は、前記復元された適応的ツリーを利用して、ボクセルデータを復元するボクセルデータ復元部を更に備えることが好ましい。
【００３８】
そして、前記記載された発明をコンピュータで実行させるためのプログラムを記録したコンピュータ可読記録媒体を提供する。
【発明の効果】
【００３９】
本発明による３次元体積データを符号化／復号化する方法および装置は、莫大な量の３次元体積データを高効率に符号化でき、固定された解像度の体積データだけでなく、任意の解像度の体積データも高効率に符号化できるため、少量のデータで高画質の３次元体積データを復元できる。また、本発明による３次元体積データの符号化では、プログレッシブなビットストリームを生成するため、デコーディング（復号）および再生時に３次元体積データをプログレッシブに示すことができる。
【発明を実施するための最良の形態】
【００４０】
以下、添付図面を参照して、本発明に係るポイントテクスチャ、体積素、オクトツリーのデータのうち、何れか一つからなる３次元体積データ符号化／復号化方法および３次元体積データ符号化／復号化装置について詳細に説明する。
【００４１】
まず、本発明による適応的２n進ツリーの生成方法を説明する。ｎ次元データを２n個の領域より構成される２n進ツリーに分割する。その後、前記２n進ツリーに分割されたデータの２n個の領域をそれぞれノードとして、分割された２n個の領域の大きさが一つの単位体になるまで、順次、下位２n進ツリーに分割する。前記２n進ツリー分割は、前記ｎ次元データの各方向での単位体数が偶数である場合には、半分ずつになるように、奇数である場合には、１単位体数差になるように分割する。そのとき、前記２n個の分割された領域のそれぞれが２n個の単位体にならない場合には、仮想の単位体を付加して２n個の単位体より構成される下位２n進ツリーを生成する。前記１単位体数差の各方向の分割は、各方向のうち、常に何れか一方のみが一定の方向に１単位体多くなるように行われる。
【００４２】
前記適応的２n進ツリーの生成方法の一例として、ｎ＝３である場合、すなわち適応的オクトツリーについて説明する。適応的オクトツリーを生成するには、まず、３次元データを８個の領域より構成されるオクトツリーに分割する。前記オクトツリーに分割されたデータの８個の領域をそれぞれノードとして、分割された８個の領域の大きさが一つの単位体、すなわち１ボクセルになるまで、順次、下位オクトツリーに分割する。このオクトツリーへの分割は、前記３次元データの幅、高さ、深さのそれぞれのボクセル数が偶数である場合には、半分ずつになるように、奇数である場合には、１ボクセル差になるように分割する。そのとき、前記８個の分割された領域がすべて８個のボクセルにならない場合には、仮想のボクセルを付加して、それぞれ８個のボクセルより構成される下位オクトツリーに生成する。そして、前記１ボクセル差の前後、左右、上下の各方向の分割は、前後、左右、上下の各方向のうち、常に何れか一方のみが一定の方向に１ボクセル多くなるように行われる。
【００４３】
図３に、ツリー構造における親子関係を示す。図３（ａ）は、クワッドツリーの例であり、図３（ｂ）は、オクトツリーの例である。オクトツリーは、一つのルートノードから８個の子ノードを有するが、各子ノードは、下位の更に他の８個の子ノードを有するか、または、リーフノードを有するものとすることができる。
【００４４】
前記適応的オクトツリー生成を更に詳細に説明すれば、次の通りである。前記適応的オクトツリーは、一つのルートノードから８個の子ノードを有するが、各子ノードは、下位の更に他の８個の子ノードを有するか、または、リーフノードを有するものとすることができる。そのノードには、５種類のラベルがつく。
【００４５】
前記適応的オクトツリーは、通常のオクトツリーとその構造が類似しているが、相違点は、中間ノードにラベルがつくということである。前記５種類のラベルは、Ｓノード（Ｓｐｌｉｔ）、Ｐノード（ＰＰＭ）、Ｂノード（Ｂｌａｃｋ）、Ｗノード（Ｗｈｉｔｅ）、Ｅノード（Ｅｍｐｔｙ）として定義される。
【００４６】
前記オクトツリーの各ノードに対し、前記ノードが示す３次元領域をノード領域であるとするとき、ノード領域の下位体積素が、すべてオブジェクトを含まない体積素より構成されるノードである場合に、そのようなノード領域を有するノードをＷノードと言い、ノード領域の下位体積素が、すべてオブジェクトを含む体積素より構成されるノードである場合に、そのようなノード領域を有するノードをＢノードと言う。そして、ノード領域の下位体積素の値が、ＰＰＭアルゴリズムにより符号化されるノードである場合に、そのようなノード領域を有するノードをＰノードと言い、ラベルで表示された下位ノードを有するノードである場合に、そのようなノード領域を有するノードをＳノードと言う。また、子ノードの数が８個ではない場合に８個にするために付加された仮想の体積素を、Ｅノードという。表１は、前記オクトツリーノードの５種類のラベルを表している。
【００４７】
【表１】
0004759291.tif 000002
【００４８】
３次元オブジェクトに対するバウンディングボリュームがオブジェクトを含んでいれば、ルートノードはＳノードと表示され、ボリュームは、８個の下位ボリュームに細分される。細分されたボリュームが、Ｗｈｉｔｅ体積素のみを含んでいれば、相応するノードは、Ｗノードと表示され、細分されたボリュームが、Ｂｌａｃｋ体積素を一つでも含んでいれば、相応するノードは、臨時でＢノードと表示される。細分されたボリュームが、Ｗｈｉｔｅ体積素のみを含んでいるか、またはＰＰＭ符号化されたものでなければ、そのノードは、Ｓノードに設定される。すなわち、特性ノードがＳ、Ｗ、Ｂ、Ｐ、Ｅなどのようなラベルで表示された子ノードを有すれば、そのノードのラベルはＳに設定する。前記Ｓノードのボリュームは、８個の更に小さいボリュームに再び細分される。その過程は、ツリーがあらかじめ設定された深さになるまで繰り返される。そのような深さで、もし特定ノードをＰＰＭ方式で符号化することが効率的である場合は、ラベルをＰに設定する。
【００４９】
一方、バウンディングボリュームを８個のボリュームに分けるとき、一軸で長さを同じ長さに半分に分けることができない場合には、分けられる一方の方向を、他方の方向に対して一体積素ほど更に長く規則的に分ける。ところが、もし他方、すなわち、一体積素の長さほど短く分ける部分で、体積素の空間がない場合、すなわち、オクトツリーでは、下位体積素が８個ではない場合、空いている所を判断して、空いているノードは、Ｅｍｐｔｙ体積素と定義し、前記Ｅｍｐｔｙ体積素のラベルを、Ｅノードと表示する。もし、あるノードがＥノードを含みつつ、ＢノードとＷノードのみからなる場合にも、前記ノードをＰノードとして取り扱い、その体積素値をＰＰＭ方法により符号化できる。
【００５０】
オクトツリーの場合、親ノードは、なるべく同じサイズの８個の子ノードに分ける。親ノードを分けるときの順序は、図４のように、前左上、前右上、前左下、前右下、後左上、後右上、後左下、後右下と決めておくことができる。
【００５１】
説明を更に容易にするために、クワッドツリーを使用して、具体的な例を挙げて前記を説明する。図５および図６は、適応的オクトツリーの概念を更に容易に説明するための、適応的クワッドツリーを示したものである。図５（ａ）は、幅が３（ピクセル）、高さが４（ピクセル）の２次元イメージであり、解像度が３×４である２次元イメージについてのクワッドツリーを示したものである。色のない白いピクセル（ポイント）は、空いている（empty）ピクセルを示し、色のある体積素は、満たされている（full）体積素を示す。図５および図６において、色の違いは、異なる網掛けパタンによって示されている。図５（ｃ）で、色のあるノードは、図５（ａ）で、同じ色がある体積素と対応する。
【００５２】
ルートノードで、下位４個のノードに細分するとき、幅は３ピクセルであるため、一方は２ピクセル、他方は１ピクセルに分けられる。高さは４ピクセルであるため、それぞれ２ピクセルずつに分けられる。図５（ｃ）の適応的クワッドツリーで、ルートノードがＳであるのは、下位ノードがオブジェクトを含んでいるためである。ルートノードで、すぐ下位の４個の子ノードは、それぞれ、Ｓ、Ｓ、Ｗ、Ｂノードである。１番目のノードと２番目のノードが、Ｓノードであるのは、ピクセルの情報が下位の子ノードで表現されるためである。１番目のＳノードの子ノードは、それぞれ、Ｗ、Ｂ、Ｂ、Ｂノードであり、図５（ｂ）の左上端の４個のピクセル領域に該当する。２番目のＳノードの子ノードは、それぞれ、Ｗ、Ｅ、Ｂ、Ｅノードであり、図５（ｂ）の右上端の４個のピクセル領域に該当する。Ｂノードは、ピクセルが満たされていることを示し、Ｗノードは、ピクセルが空いていることを示す。符号化対象になる情報は、ＢノードとＷノードで表現されるピクセルである。Ｅノードは、ピクセルの空間がないことを示し、符号化対象から除かれる情報である。したがって、Ｅノードは、仮想のノードであって、全体バウンディングボリュームの解像度情報を利用して、その位置が特定されるノードである。図５（ｂ）で、右上端に４個のピクセルで、点線で表現された２個のピクセルがＥノードであり、元来の図５（ａ）にはない領域である。そのように、仮想のＥノードを表現することは、１番目のＳノードが下位の４個の子ノードを有するように、仮想のクワッドツリーを作るためのである。
【００５３】
そのように、適応的オクトツリーでも、Ｓノードで、下位８個の子ノードを表現するにあたって、体積素の空間がある子ノードである場合は、ＢノードまたはＷノードで表示し、体積素の空間がない子ノードである場合は、Ｅノードで表示する。下位８個の子ノードに空間を分けるときに、適応的クワッドツリーと同様に、一方の方向を他方の方向に比べて、一体積素の長さほど更に長く規則的に分ける。すなわち、３次元体積空間を、Ｘ、Ｙ、Ｚの３軸で表現するときに、−Ｘ方向、−Ｙ方向、−Ｚ方向を、＋Ｘ方向、＋Ｙ方向、＋Ｚ方向より一体積素の長さほど更に割り当てる。その逆の場合も可能であるが、本発明では、前者の規則を使用し、全体ノードに対して同じ規則を適用する。
【００５４】
図５（ｃ）で、ルートノードの３番目の子ノードであるＷノードは、図５（ｂ）の左下端の４個のピクセル領域に該当するものであって、あらゆるピクセルが空いているため、Ｗノードと表示する。図５（ｃ）のルートノードの４番目の子ノードであるＢノードは、図５（ｂ）の右下端の４個のピクセル領域に該当するものであって、仮想のＥノードを除いたあらゆるピクセルが満たされているため、Ｂノードと表示する。図６でも適応的ツリーの例を示し、図６（ａ）は、解像度が５×７である２次元イメージを示したものである。図６（ｂ）では、Ｘ軸で、３列のポイントと２列のポイントの長さに分け、Ｙ軸では、４行のポイントと３行のポイントの長さに分ける。分けられる他の部分より、一つのポイントの長さほど短い部分の行と列を、空いているノードであるＥノードで満たし得る領域と判断する。そのような方法を利用することで、既存の方法とは違って、３５２×２８８×１５，１２３×４５６×５１２などのように、任意の解像度を有する３次元オブジェクトデータを適応的オクトツリーより構成できる。図６（ｃ）は、前記図６（ａ）に相応する適応的クワッドツリーを示している。
【００５５】
以下、前記した適応的オクトツリーの生成方法を利用して３次元オブジェクトデータの符号化を行う、本発明による３次元体積データ符号化装置および３次元体積データ符号化方法を説明する。図７Ａは、本発明による３次元オブジェクトデータ符号化装置の構成を示したブロック図である。本発明による３次元体積データ符号化装置は、体積素生成部７００と、適応的オクトツリー変換部７２０と、ノード符号化部７４０と、ビットストリーム生成部７６０と、を含んでなる。図７Ｂは、本発明による３次元体積データ符号化方法を示すフローチャートである。
【００５６】
前記体積素生成部７００は、３次元体積データがポイントテクスチャであれば、３次元バウンディングボリュームを使用して体積素データに変換する。
【００５７】
ＭＰＥＧ−４ ＡＦＸに標準として採択されたポイントテクスチャフォーマットは、次の通りである。
【００５８】
【表２】
0004759291.tif 000003
【００５９】
ポイントテクスチャデータが入力されれば、前記体積素生成部７００により体積素データに変換される（段階７０）。ポイントテクスチャの深さ情報を体積素データに変換するには、まず、バウンディングボリュームを作る。バウンディングボリュームは、ポイントテクスチャと同じ解像度を有する。例えば、もし、ポイントテクスチャがＸ×Ｙ解像度の映像を有し、各ピクセルの深さ情報の解像度がＺであれば、Ｘ×Ｙ×Ｚバウンディングボリュームが生成される。バウンディングボリュームの原点は、正面の左下端コーナーに位置する。右側の体積素は、左側の体積素より大きいｘ値を有し、上端体積素は、下端体積素より大きいｙ値を有し、背面の体積素は、正面の体積素より大きいｚ値を有する。深さ情報を２進ボリュームデータに変換することは、すぐできる。ボリュームデータのあらゆる体積素は、Ｗｈｉｔｅ（０）と初期化される。その後、体積素の位置がポイントテクスチャにあるボクセルにより満たされていれば、体積素は、Ｂｌａｃｋ（１）に設定される。
【００６０】
オクトツリーは、一つのルートノードから８個の子ノードを有するが、各子ノードは、下位の更に他の８個の子ノードを有するか、または、リーフノードを有するものとすることができる。ノードは、ＢｌａｃｋまたはＷｈｉｔｅの値を有するものとすることができる。リーフノードがＢｌａｃｋである場合は、体積素が満たされている場合であり、Ｗｈｉｔｅである場合は、体積素が空いている場合である。リーフノードではない中間ノードで、Ｂｌａｃｋである場合は、下位のノードのうち、体積素が満たされているノードがあるということを示し、Ｗｈｉｔｅである場合は、下位のあらゆるノードが空いているということを示す。そのようなオクトツリーは、３次元体積データを示すのに使用される典型的な構造である。
【００６１】
前記適応的オクトツリー変換部７２０は、前記体積素データまたはオクトツリーデータを、ノードに所定のラベルが付与された適応的オクトツリーに変換する。ポイントテクスチャで表現された３次元オブジェクトデータが、前記体積素生成部７００で体積素に変換されるか、そのまま入力されたオクトツリーデータを入力として、適応的オクトツリーを生成する（段階７２）。
【００６２】
図８は、前記適応的オクトツリー変換部７２０の細部構成を示したブロック図である。図８に示すように、適応的オクトツリー変換部７２０は、オクトツリー生成部８００および適応的オクトツリー生成部８５０を備える。
【００６３】
前記オクトツリー生成部８００は、３次元体積素データを入力として８個の領域に分割してオクトツリーに生成する。前記適応的オクトツリー生成部８５０は、前記オクトツリーの各ノードに所定のラベルを付与しつつ、ノードの大きさが一つのボクセルになるまで８個の領域に分割して、所定のラベルが付与されたオクトツリーに生成する。そのとき、Ｗノードである場合には、その体積素を下位８個の領域に分割して下位オクトツリーを生成する処理を中止する。
【００６４】
前記８個の領域分割は、前記３次元データの幅、高さ、深さのそれぞれを、前記各ボクセル数が偶数である場合には、半分ずつになるように、奇数である場合には、１ボクセル差になるように分割するが、前記８個の分割された領域のそれぞれが８個のボクセルにならない場合には、仮想のボクセルを付加して８個のボクセルになるように生成する。そして、前記１ボクセル差の前後、左右、上下の各方向の分割は、前後、左右、上下の各方向のうち、常に何れか一方のみが一定の方向に１ボクセル多くなるように行われる。前記適応的オクトツリーの詳細な説明は、本発明による適応的オクトツリーの生成方法で、前記と同じであるため省略する。
【００６５】
前記ノード符号化部７４０は、前記適応的オクトツリー変換部７２０で生成された適応的オクトツリーのノードを、ノードのラベルを参照して符号化する（段階７４）。前記ノード符号化部７４０でノード符号化をするときには、ノード間の符号化順序は、変形されたＢＦＳ（Modified Breadth First Search：以下、ＭＢＦＳ）を使用して定める。
【００６６】
前記ＭＢＦＳを使用した符号化は、前記適応的オクトツリー構造で前記ノードのラベルを参照して、Ｔｏｐ−ｄｏｗｎ方式でルートノードからリーフノードまでＢＦＳで符号化するが、子ノード間には優先順位を付与して、前記優先順位によって符号化する方式である。ここで、ラベルが‘Ｅ’であるノードは符号化しない。前記ＭＢＦＳ方式によれば、図５（ｃ）に示されたクワッドツリーのノードは、図９に示された順序でノードを参照し、この順序によって各ノードを符号化する。すなわち、子ノード間には優先順位が付与されるが、ここでは、子ノード間には左側のノードの優先順位を高くした。そして、Ｅノードは参照しない。同様に、図６（ｃ）に示されたクワッドツリーのノードは、図１０に示された順序で符号化する。
【００６７】
前記ノード符号化部７４０は、図１１に示すように、ＳＯＰ情報生成部１１００、Ｓノード符号化部１１２０およびＰノード符号化部１１４０からなる。
【００６８】
前記ＳＯＰ情報生成部１１００は、前記ＭＢＦＳ方式により定められたノードを、Ｓノードとして符号化するか、またはＰノードとして符号化するかを選択して、そのＳＯＰを生成する。すなわち、前記ＳＯＰ情報生成部１１００は、符号化するノードを、Ｓノードとして符号化するか、Ｐノードとして符号化するかを判断する。Ｓノードとして符号化するときと、Ｐノードとして符号化するときの各エントロピを計算して、エントロピが小さい場合を選択した後、前記選択されたＳノードまたはＰノードのラベルをＡＡＣ（Adaptive Arithmetic Coding）符号化する。
【００６９】
前記Ｓノード符号化部１１２０は、Ｓｐｌｉｔノード符号化する。すなわち、前記Ｓノード符号化部１１２０は、子ノードの色情報平均値、および、８個の子ノードがそれぞれ存在するか否かを示すフラグ情報（Ｃｈ１−Ｃｈ８）を符号化する。すなわち、前記符号化するＳノードの色情報の平均値を求めて、ＤＰＣＭ符号化およびエントロピ符号化、好ましくはＡＡＣで符号化する。また、前記符号化するＳノードのフラグ情報は、エントロピ符号化する。ここで、場合によっては、前記ＤＰＣＭ符号化およびエントロピ符号化のうち、少なくとも一つを省略することもある。
【００７０】
図１２（ａ）で、ルートノードをＳノードとして符号化するとき、その下位子ノードのラベルは、Ｓ、Ｓ、Ｗ、Ｂであり、これは符号化する実際値である。下位子ノードのラベルのうち、Ｓは、Ｂに置換して符号化する。したがって、図１２（ｂ）で、太線からなる四角形内にあるノードのように、Ｂ、Ｂ、Ｗ、Ｂで符号化される。この値は、復号化器で復元される値と同じである。
【００７１】
前記Ｐノード符号化部１１４０は、ＰＰＭノード符号化する。前記Ｐノード符号化部１１４０は、所定個数のコンテクストを使用して、該当ノードの体積素の深さ情報および色情報を符号化する。前記色情報は、ＤＰＣＭ符号化およびエントロピ符号化することが好ましい。場合によっては、前記ＤＰＣＭ符号化およびエントロピ符号化のうち、少なくとも一つを省略しうる。そして、前記深さ情報は、ＰＰＭ符号化することが好ましい。すなわち、前記Ｐノード符号化は、まず、そのノードのボリューム領域にある深さ情報をＰＰＭ符号化し、該当ノードの色情報をＤＰＣＭとＡＡＣで符号化する。
【００７２】
図１３は、体積素をＰＰＭ符号化するとき、使用するコンテクストを示したものである。右側のＤｅｐｔｈがｋである２次元平面が、以前に符号化された体積素と現在符号化する体積素がある一断面であり、左側のＤｅｐｔｈがｋ−１である２次元平面が、以前に符号化された体積素がある隣接断面である。効率的に符号化するために、Ｘで表示された位置の体積素は、コンテクストとして使用せず、残りの円状の１０個の体積素をコンテクストとして使用してＰＰＭ符号化する。したがって、この場合にコンテクストは、‘００１１１０１００００１１’から‘０１１１００００１１’に減る。コンテクストの配列順序は、ラスタースキャン順序に従う。
【００７３】
一方、前記図７Ａに示されたビットストリーム生成部７６０は、前記ノード符号化部７４０で符号化されたノードとヘッダ情報とを利用して、ビットストリームを生成し（段階７６）、ヘッダ符号化部７６２およびエントロピ符号化部７６４を備える。
【００７４】
前記ヘッダ符号化部７６２は、前記所定のヘッダ情報を符号化する。前記エントロピ符号化部７６４は、前記符号化されたノードデータをエントロピ符号化する。
【００７５】
適応的オクトツリーの各ノードがＳノードであるときは、Ｓｐｌｉｔノード符号化されたビットストリームを生成し、Ｐノードであるときは、ＰＰＭノード符号化されたビットストリームを生成する。
【００７６】
図１４（ａ）のヘッダは、３次元オブジェクトに対する幅、高さ、深さ情報からなる解像度情報を含む。また、前記ヘッダは、ノード符号化時に、ルートノードからリーフノードまでのすべてのノードを符号化する無損失符号化、および開始ノードから特定ノードまで符号化する損失符号化を示すための復号化率情報を更に備えることが好ましい。また、前記ヘッダは、ＤＩＢＲデータのバージョン情報を更に備えることが好ましい。例えば、前記バージョン情報は、フラグで示し、前記フラグの値が０であれば、バージョンが１であり、フラグ値が１であれば、バージョンが２である。
【００７７】
前記ヘッダ情報と前記ルートノードから、ＭＢＦＳ方式によって定められる順序で、ノードを一つずつ符号化しつつ、ビットストリームを生成する。もし、全体符号化するノードの個数がＮ個であるとすれば、図１４（ａ）のように、Ｎｏｄｅ−１、Ｎｏｄｅ−２、…、Ｎｏｄｅ−Ｎで表現できる。それらの各ノードのビットストリームは、図１４（ｂ）のように、ＳＯＰ（‘Ｓ’または‘Ｐ’）と、ＤＩＢ（Detailed information bits）より構成される。
【００７８】
もし、ＳＯＰがＳノードであると示されれば、図１４（ｃ）のように、ＤＩＢは、そのノード領域の平均色と、子ノードがＷノードであるかの如何を示す最大８個のフラグとにより構成される。８個のフラグを、Ｃｈ１、Ｃｈ２、…、Ｃｈ８で表現できるが、これは、それぞれ、８個の体積素の空間がある場合を示す。体積素の空間がないノードがあれば、ない個数ほどフラグの個数も減り、符号化対象から除かれる。符号化するフラグの値は、ＡＡＣで符号化できる。
【００７９】
もし、ＳＯＰがＰノードであると示されれば、図１４（ｄ）のように、そのノード領域内にある体積素の値、すなわち、深さ情報がＰＰＭ符号化され、Ｂ体積素の色情報は、順にＤＰＣＭされ、ＡＡＣで符号化される。ＰＰＭ符号化を説明する。前記のように、深さ情報は、２進体積素値で表現される。Ｗ体積素は、透明な背景を表現し、Ｂ体積素は、３次元オブジェクトの体積素を示す。Ｐノード内の２進体積素値は、隣接する体積素値をコンテクストとして使用してＰＰＭ符号化される。ラスタースキャン順序により、１３個の隣接する体積素のコンテクストを使用して演算し、且つデータを処理するのに、そのデータ量が多すぎる。したがって、コンテクストの数を効率的に減らす必要があるが、全体エントロピにほとんど影響を与えない３個の体積素を除去する。除去された体積素は、図１３に示されたように、‘Ｘ’でマーキングされた。そのコンテクストを利用して、体積素は、コンテクスト基盤ＡＡＣにより符号化される。
【００８０】
深さ情報を符号化した後、ノード領域内にあるＢ体積素のＲＧＢ色の値は、ラスタースキャン順にＤＰＣＭされ、ＡＡＣ符号化される。符号化するＢ体積素のＲ、Ｇ、Ｂ値は、以前順序の符号化されたＢ体積素の各Ｒ、Ｇ、Ｂ値から予測され、その予測誤差値は、ＡＡＣで符号化される。
【００８１】
次いで、本発明による３次元体積データの復号化方法および復号化装置について説明する。図１５は、本発明による３次元体積データ復号化装置を示したブロック図である。３次元体積データ復号化装置は、ビットストリーム読み取り部１５０と、ノード復号化部１５２０と、適応的ツリー復元部１５４０と、を含んでなる。前記ビットストリーム読み取り部１５０は、ヘッダ復号化部１５００を備え、エントロピ復号化部１５１０を更に備えることが好ましい。また、前記復号化装置、ボクセルデータ復元部１５６０を更に備えることが好ましい。
【００８２】
本発明による３次元体積データ復号化装置は、基本的にビットストリームを受けて、ヘッダ情報とツリーノード情報とを復号化する。ビットストリームを読み取るために、コンテクスト基盤適応的算術復号化器をエントロピ復号化部１５１０として使用できる。
【００８３】
前記ビットストリーム読み取り部１５０は、ビットストリームを受けてヘッダ情報を抽出し、ビットストリームが、符号化時にエントロピ符号化された場合、前記ビットストリームに対してエントロピ復号化する。前記ヘッダ復号化部１５００は、ビットストリームから少なくともオブジェクトの解像度情報を含むヘッダ情報を抽出して復号化する。前記ヘッダの解像度情報は、３次元オブジェクトの幅、高さおよび深さデータからなることが好ましい。前記ヘッダが、復号化率情報を更に備える場合には、前記ヘッダ復号化部１５００は、ビットストリームから前記復号化率情報を抽出して復号化する。前記復号化率情報は、ノード復号化時に、ツリーのルートノードから特定ノードまで復号化する損失復号化程度、およびルートノードからリーフノードまでのすべてのノードを復号化する無損失復号化を示す。また、前記ヘッダには、ＤＩＢＲデータのバージョン情報を含むものとすることができる。
【００８４】
前記エントロピ復号化部１５１０は、入力されるビットストリームが、符号化時にエントロピ符号化された場合、前記ビットストリームに対してエントロピ復号化し、好ましくは、算術復号化を使用する。
【００８５】
前記ノード復号化部１５２０は、前記ヘッダが、復号化率情報を含んでいない場合には、前記ヘッダの解像度情報を利用してノードの数を計算し、前記エントロピ復号化されたノードデータに対して、子ノード間に優先順位を付与するＭＢＦＳによる順序で、ルートノードからリーフノードまでツリーの各ノードを復号化する。また、前記ヘッダが復号化率情報を含んでいる場合には、前記ノード復号化部１５２０は、前記解像度情報を利用して計算されたノードの数と、前記復号化率情報を利用して復号化するノードの数とを計算し、前記ＭＢＦＳ方式による順序で、ルートノードから始まってリーフノード方向に、前記計算された復号化するノードの数ほどツリーのノードを復号化する。
【００８６】
前記ＭＢＦＳは、優先順位キューを利用して、前記優先順位キューに復号化するノードのインデックスをプッシュおよびポップすることで行われることが好ましい。そして、前記優先順位は、ノードの１番目の子ノードが２番目の子ノードより高く、２番目の子ノードが３番目の子ノードより高く、同様に、最後の子ノードが最も低いことが好ましい。
【００８７】
前記ＭＢＦＳをアルゴリズムとして示せば、次の通りである。
【００８８】
【表３】
0004759291.tif 000004
【００８９】
図１６は、前記ノード復号化部１５２０の更に詳細な内部構成を示したブロック図である。ノード復号化部１５２０は、ＳＯＰ抽出部１６００と、Ｓノード復号化部１６２０と、Ｐノード復号化部１６４０と、を含んでなる。前記ＳＯＰ抽出部１６００は、ツリーのノードが、Ｓノード符号化であるかＰノード符号化であるかを示すＳＯＰを抽出して復元する。
【００９０】
前記Ｓノード復号化部１６２０は、前記ＳＯＰがＳノード符号化であることを示せば、前記復号化しようとするノードがＳノードであると判断し、前記Ｓノードを復号化する。図１７は、前記Ｓノード復号化部１６２０の細部構成を示したブロック図である。Ｓノード復号化部１６２０は、色情報復号化部１７００と、ＷＯＢ判断部１７２０と、Ｗノード処理部１７４０と、Ｂノード処理部１７６０と、を含んでなる。前記色情報復号化部１７００は、前記Ｓノードの色情報をエントロピ復号化する。前記ＷＯＢ判断部１７２０は、前記Ｓノードのすべての子ノードについて、ノードラベルがＷであるかＢであるかを判断する。前記Ｗノード処理部１７４０は、前記子ノードのラベルがＷであれば、サブツリーノードの数を計算して、前記サブツリーノードの数ほどは復号化せずに飛ばす。前記Ｂノード処理部１７６０は、前記子ノードのラベルがＢであれば、前記優先順位キューに前記子ノードのインデックスをプッシュする。
【００９１】
前記Ｐノード復号化部１６４０は、前記ＳＯＰがＰノード符号化であることを示せば、前記復号化しようとするノードがＰノードであると判断し、前記Ｐノードを復号化する。図１８は、前記Ｐノード復号化部１６２０の細部構成を示したブロック図である。Ｐノード復号化部１６２０は、ボクセルＰＰＭ復号化部１８００およびボクセル色復号化部１８２０を含んでなる。前記ボクセルＰＰＭ復号化部１８００は、ツリーノードのインデックスから幅、高さ、深さデータからなる３次元ボリューム領域を計算して、前記ボリューム領域内にボクセルが存在しているかを検査する。前記ボクセル映像復号化部１８２０は、前記検査結果、ボクセルが存在すれば、前記ボクセルの色情報をエントロピ復号化する。
【００９２】
図１５に示された前記適応的ツリー復元部１５４０は、前記復号化されたノードを利用して適応的ツリーを復元する。前記ボクセルデータ復元部１５６０は、前記復元された適応的ツリーを利用してボクセルデータを復元する。
【００９３】
図１９は、本発明による３次元体積データ復号化方法を示したフローチャートである。図１９を参照して、本発明による３次元体積データ復号化方法および装置の動作を説明する。
【００９４】
まず、ビットストリームが入力されると、ヘッダ復号化部１５００によってヘッダ情報が復元される。前記ヘッダ情報は解像度情報を備え、好ましくは、復号化率情報を更に備える（１９００段階）。また、前記ヘッダ情報には、ＤＩＢＲデータのバージョン情報を更に備え得る。例えば、前記バージョン情報は、フラグで表現され、フラグ値が０であれば、ｖｅｒｓｉｏｎ１であり、フラグ値が１であれば、ｖｅｒｓｉｏｎ２であることを示すものとすることができる。
【００９５】
例えば、ポイントテクスチャビットストリームを読み取るための最上位クラスの構文を示せば、次の通りである。
【００９６】
【表４】
0004759291.tif 000005
【００９７】
ここで、ＰｏｉｎｔＴｅｘｔｕｒｅＨｅａｄｅｒは、ビットストリームからヘッダ情報を読み取るためのクラスである。そして、ＰｏｉｎｔＴｅｘｔｕｒｅＴｒｅｅＮｏｄｅｓは、低解像度から高解像度までプログレッシブにツリーノードを読み取るためのクラスである。
【００９８】
そして、ＰｏｉｎｔＴｅｘｔｕｒｅＨｅａｄｅｒクラスの構文を示せば、次の通りである。
【００９９】
【表５】
0004759291.tif 000006
【０１００】
ここで、ｎＢｉｔＳｉｚｅＯｆＷｉｄｔｈは、ｎＷｉｄｔｈビットの大きさを示し、ｎＷｉｄｔｈは、ＰｏｉｎｔＴｅｘｔｕｒｅのｗｉｄｔｈを示す。ｎＢｉｔＳｉｚｅＯｆＨｅｉｇｈｔは、ｎＨｅｉｇｈｔのビットの大きさを示し、ｎＨｅｉｇｈｔは、ＰｏｉｎｔＴｅｘｔｕｒｅの高さを示す。ｎＤｅｐｔｈＮｂＢｉｔｓは、元来の深さデータを示すために使用されたビットの数を示す。ｎＤｅｐｔｈＮｂＢｉｔｓの値は、０から３１までの範囲を有する。そして、元来の深さデータを示すために使用されたビットの数は、ｎＤｅｐｔｈＮｂＢｉｔｓ＋１である。ｎＰｅｒｃｅｎｔＯｆＤｅｃｏｄｉｎｇは、復号化されるツリーノードの百分率である。この値が最大値（１００）であり、無損失復号化が行われ、もしくは損失復号化が行われる。
【０１０１】
一方、ＰｏｉｎｔＴｅｘｔｕｒｅＴｒｅｅＮｏｄｅｓのクラスについての構文を示せば、次の通りである。
【０１０２】
【表６】
0004759291.tif 000007
【０１０３】
ここで、ｎＮｕｍｂｅｒＯｆＴｒｅｅＮｏｄｅｓは、オクトツリーでのツリーノードの数を示す。ｉｎｉｔｉａｌｉｚｅＯｃｔｒｅｅ関数は、ｎＷｉｄｔｈ、ｎＨｅｉｇｈｔおよびｎＤｅｐｔｈＮｂＢｉｔｓで表現される解像度値を初期化し、オクトツリーでのツリーノードの数を得る。
【０１０４】
ｎＮｕｍｂｅｒＬｉｍｉｔは、復号化されるツリーノードの限界を示す。ｐｕｓｈＱ関数は、キューに値を挿入する。ｎＣｏｕｎｔは、ツリーノードを復号化する現在の数を示す。
【０１０５】
ｉｓＱｕｅｕｅＥｍｐｔｙ関数は、キューが空いているかをチェックする。ｎＩｎｄｅｘは、復号化するツリーノードのインデックスを示す。ｐｏｐＱ関数は、キューから値を抽出する。
【０１０６】
ｎＳＯＰは、ツリーノードがｓｐｌｉｔノードまたはＰＰＭノードであるかを示す。もし、値が０であれば、ｓｐｌｉｔノードであり、もしくはｐｐｍノードを意味する。ｄｅｃｏｄｅＡＡＣ関数は、与えられたコンテクストでＡＡＣ復号化を行う。
【０１０７】
ｎＲｅｇｉｏｎＲｅｄは、ボクセル領域でのｒｅｄ ｃｏｌｏｒ範囲を、ｎＲｅｇｉｏｎＧｒｅｅｎは、ｇｒｅｅｎ ｃｏｌｏｒ範囲を、ｎＲｅｇｉｏｎＢｌｕｅは、ｂｌｕｅ ｃｏｌｏｒ範囲を示す。ｎＣｈｉｌｄは、ｓｐｌｉｔノードを復号化する８ｃｈｉｌｄｒｅｎ ｎｏｄｅｓのインデックスを示す。ｎＢＯＷは、ｃｈｉｌｄ ｎｏｄｅがｂｌａｃｋであるかｗｈｉｔｅであるかを示す。
【０１０８】
ｇｅｔＣｏｕｎｔＯｆＴｒｅｅＳｉｚｅ関数は、ツリーノードからサブツリーノードの数を計算する。ｇｅｔＲｅｇｉｏｎ関数は、ツリーノードのインデックスからボリューム領域（ｓｔａｒｔｉｎｇ ｘ， ｙ，ｚ ａｎｄ ｅｎｄｉｎｇ ｘ， ｙ， ｚ）を計算する。ｎＳｔａｒｔＸ、ｎＳｔａｒｔＹ、ｎＳｔａｒｔＺは、ボリューム領域の出発点を示し、ｎＥｎｄＸ、ｎＥｎｄＹ、ｎＥｎｄＺは、ボリューム領域が終点を示す。
【０１０９】
ｎＩｎｄｅｘＯｆＣｏｎｔｅｘｔは、ｘ、ｙ、ｚ値からツリーノードのインデックスコンテクストを示し、ｇｅｔＩｎｄｅｘＯｆＣｏｎｔｅｘｔ関数は、ｘ、ｙ、ｚ値からツリーノードコンテクストのインデックスを得る。ｎＶｏｘｅｌは、ボクセルノードが、ｂｌａｃｋであるかｗｈｉｔｅであるかを示す。
【０１１０】
ｎＤｅｌｔａＲｅｄは、ボクセルでのｒｅｄ ｃｏｌｏｒのｄｉｆｆｅｒｅｎｔｉａｔｅｄ ｖａｌｕｅを、ｎＤｅｌｔａＧｒｅｅｎは、ボクセルでのｇｒｅｅｎ ｃｏｌｏｒのｄｉｆｆｅｒｅｎｔｉａｔｅｄ ｖａｌｕｅを、ｎＤｅｌｔａＢｌｕｅ：ボクセルでのｂｌｕｅ ｃｏｌｏｒのｄｉｆｆｅｒｅｎｔｉａｔｅｄ ｖａｌｕｅを示す。
【０１１１】
一方、もし、ヘッダ情報に解像度情報のみあり、復号化率情報がなければ、前記ノード復号化部１５２０は、前記解像度情報を利用して復号化するノードの数を計算し、前記ＭＢＦＳ方式による順序で、ルートノードからリーフノードまでツリーの各ノードを復号化する（段階１９２０）。
【０１１２】
そして、ヘッダ情報に解像度情報と復号化率情報とがあれば、前記ノード復号化部１５２０で、ＭＢＦＳ方式による順序で、ルートノードから始まってリーフノード方向に、前記計算された復号化するノードの数ほどツリーのノードを復号化する。前記ＭＢＦＳ方式は、優先順位キューを利用して、前記優先順位キューに復号化するノードのインデックスをプッシュおよびポップすることで行われる。
【０１１３】
それを更に詳細に説明すれば、前記ノード復号化部１６２０は、まず、３次元オブジェクトの幅×高さ×深さ解像度情報を利用して、初期飽和オクトツリーノードを生成した後、０（ｗｈｉｔｅ）値で初期化する。ツリーノードの個数がＮであるときに復号化されるノードは、ノード−１、ノード−２、ノード−３、…、ノード−Ｎのようである。
【０１１４】
前記ＭＢＦＳ方式を利用して生成されたビットストリームを受ける場合、ルートノードからリーフノードまでの復号化順序が分かるため、符号化装置が伝送するノードの位置が容易に分かる。また、解像度情報を利用すれば、全体ノードの数が分かるため、伝送されたノードが最後であるかを確認できる。３次元オブジェクトを復号化する場合、もし、復号化装置がＢＦＳアルゴリズムを使用すれば、プログレッシブな復号化が不可能であり、単に順次の復号化のみが可能であるが、この場合、オブジェクト視覚化が不自然になるという短所がある。したがって、ＭＢＦＳを利用すれば、３次元オブジェクトをプログレッシブに視覚化できるため、更に自然に３次元オブジェクトを表現できるという長所がある。
【０１１５】
ＭＢＦＳ方式を利用して復号化されるノードの順序を定める場合、子ノードのうち、あらゆる１番目の子ノードは、他の子ノードより高い優先順位を有する。あらゆる２番目の子ノードは、その次の高い優先順位を有し、３番目から８番目のノードより高い。そのような方法で、最後のあらゆる８番目のノードは、以前の子ノードより最も低い優先順位を有する。親ノードから、そのような子ノードの優先順位によって符号化および復号化されるノードの現在順序が復号化器から分かる。
【０１１６】
Ｅノードは、符号化および復号化対象ではない。図２０は、ノード復号化部１５２０でのノード復号化過程を示したフローチャートである。まず、ＳＯＰ抽出部１６００によりＳＯＰフラグ情報が復号化されれば（段階２０００）、ツリーノードがＳノードであるかＰノードであるかを検査する（段階２０２０）。前記検査結果、Ｓノードであれば、Ｓノード復号化部１６２０によってＳノード復号化される（段階２０４０）。もし、前記検査結果、Ｐノードであれば、Ｐノード復号化部１６４０によってＰノード復号化される（段階２０６０）。
【０１１７】
前記Ｓノード復号化は、Ｓノード詳細情報（Detailed Information Bits：ＤＩＢ）を読んで、エントロピ復号化（好ましくは、ＡＡＣ復号化）を行って、色情報および子ノードの有無が分かる。Ｓノードである場合、符号化装置によって設定された平均色情報を利用して表現する。現在ノード後に、各子ノードの色が受信されるごとに、それを利用して更新して反映する。すなわち、もし、ＳＯＰがＳノードであると示されれば、ＤＩＢは、そのノード領域の平均色を復号化し、子ノードがＷノードであるかの如何を示すフラグの値を復号化する。体積素の空間がないノードがあれば、ない個数ほどフラグの個数も減り、復号化対象から除かれる。そのようなＥノードは、仮想のノードであり、全体バウンディングボリュームの解像度の情報により、計算して位置を探し得るノードである。
【０１１８】
Ｐノード復号化では、逆ＰＰＭアルゴリズムを利用して、復号化されるＰノードが示すボクセル領域の深さ情報を復元する。Ｐノードの色情報は、エントロピ復号化（好ましくは、ＡＡＣ復号化）および逆−ＤＰＣＭを利用して復元される。更に詳細に説明すれば、もし、ＳＯＰがＰノードであると示されれば、そのノード領域内にある体積素の値、すなわち、深さ情報がＰＰＭ復号化され、Ｂ体積素の色情報は、順に逆ＡＡＣと逆ＤＰＣＭで復号化される。例えば、Ｐノード内の復号化する２進体積素値は、図１３に示された符号化を行うときと同様に、既に復号化された隣接する１０個の体積素値をコンテクストとして使用してＰＰＭ復号化する。深さ情報を復号化した後、ノード領域内にあるＢ体積素のＲＧＢ色の値は、ラスタースキャン順に逆ＡＡＣと逆ＤＰＣＭで復号化する。復号化するＢ体積素のＲ、Ｇ、Ｂ値は、逆ＡＡＣで復号化された予測誤差値を、以前順序の復号化されたＢ体積素の各Ｒ、Ｇ、Ｂ値から逆に予測して求める。
【０１１９】
そのような方法で、ビットストリームをノード単位で復号化した後は、ラベルが付加された適応的オクトツリー復元が行われる（段階１９４０）。
【０１２０】
図２１は、３×４の解像度での適応的オクトツリー復元の簡単な例を示したものである。図２１の（ｂ）、（ｄ）、（ｆ）は、復号化の側面で、ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ過程を示したものであり、（ａ）、（ｃ）、（ｅ）は、符号化の側面で、ｃｏｎｓｔｒｕｃｔｉｏｎを示したものである。図２１の（ｂ）、（ｄ）、（ｆ）で、四角形で囲まれているノードは、現在復号化されているノードおよび子ノードを表す。図２１の（ｂ）で、現在復号化されているノードは、ｓｐｌｉｔノードを示し、子ノードは、Ｂ、Ｂ、Ｗ、Ｂである。図２１の（ｄ）で、現在復号化されているノードは、ＰＰＭノードを示し、子ノードは、Ｗ、Ｂ、Ｂ、Ｂである。図２１の（ｆ）で、現在復号化されているノードは、ｓｐｌｉｔノードを示し、子ノードは、Ｗ、Ｂである。その場合、Ｅノードは、復号化されていない。
【０１２１】
ラベルが付与された適応的オクトツリーを復元すれば、ボクセルデータに変換する（段階１９６０）。前記ボクセルデータの解像度は、広さ×高さ×深さとなる。そして、前記ボクセルデータが復元されれば、元来のポイントテクスチャデータへ容易に変換することができる。すなわち、変換されたポイントテクスチャは、深さ情報と色情報とを利用して、復元された３次元オブジェクトを表現する。そのように、適応的オクトツリーと効率的な圧縮方式で、プログレッシブな復元が可能である。
【０１２２】
本発明は、コンピュータ可読記録媒体に、コンピュータ可読コードとして具現できる。コンピュータ可読記録媒体は、コンピュータシステムによって読み取られ得るデータが保存されるあらゆる種類の記録装置を含む。コンピュータ可読記録媒体の例としては、ＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ−Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＣＤ−ＲＯＭ、磁気テープ、フロッピーディスク、光データ保存装置などがあり、更にキャリアウェーブ（例えば、インターネットによる伝送）の形態で具現されるものも含む。また、コンピュータ可読記録媒体は、ネットワークに連結されたコンピュータシステムに分散されて、分散方式でコンピュータ可読コードを保存および実行するように構成することも可能である。
【０１２３】
本発明による３次元体積データ符号化／復号化方法および３次元体積データ符号化／復号化装置の性能をテストするために、図２２のように、８個のポイントテクスチャテストモデルを利用した。表７ないし表９は、普遍的なＬｅｍｐｅｌ−Ｚｉｖ圧縮方式であるＷｉｎＺｉｐ、従来方法で使用した圧縮方式、そして、本発明による方式の圧縮率を比較して示す。
【０１２４】
【表７】
0004759291.tif 000008
【０１２５】
【表８】
0004759291.tif 000009
【０１２６】
【表９】
0004759291.tif 000010
【０１２７】
データのサイズを見れば、Ａｖａｔａｒデータの場合、１５２，１２８Ｂｙｔｅｓと最も小さく、Ｒｏｂｏｔｓデータの場合、２，４２６，５３８Ｂｙｔｅｓと最も大きい。また、ほとんどのデータが、深さ情報と色情報が類似したサイズであった。圧縮実験結果、Ｆｌｏｗｅｒデータの場合、Ｗｉｎｚｉｐと比較する場合、６０％の性能が向上した。また、Ｐｌａｎｅデータの場合、既存の研究と比較する場合、５２％の性能が向上することが分かった。
【０１２８】
深さ情報の場合、本発明による方法は、従来の方式と比較するとき、３２〜５２％の圧縮率が向上した。すなわち、本発明による方法は、不要な情報を除去し、それを補完するために、変形されたＢＦＳアルゴリズムを使用することで圧縮率を向上させ得た。ＷｉｎＺｉｐ圧縮方法は、プログレッシブな伝送および復号化を支援できないのに対し、本発明による方法は、プログレッシブな伝送および復号化を支援し、圧縮性能面でも優れていることが分かる。
【０１２９】
図２３は、伝送されるビットストリームによる歪曲程度を意味するＲＤ（Rate-Distortion）カーブを示したものである。伝送されたビットストリームに対する歪曲程度は、数式１のようにHamming Distance公式を利用した。その場合、Ｖ（ｘ， ｙ， ｚ）は、元来、３次元オブジェクトのポイントの有無を意味し、０である場合には、ポイントが無いことを意味し、１である場合には、ポイントがあることを意味する。
【０１３０】
【数１】
0004759291.tif 000011
【０１３１】
実験結果、同じビットを伝送したとき、提案する方法が歪曲率側面で非常に改善されたことが分かる。図２４は、Ａｎｇｅｌデータに対する歪曲程度を画質で表現したものである。
【０１３２】
同様の量のビットストリームを伝送する場合、本発明による方法が画質面で優れていることが確認できる。本発明による方法の場合、１５９，７３６ビットの情報を伝送するとき、歪曲率が０であったが、従来方法の場合は、１７０，５０４ビットを伝送しても、相変らず約１，１１４，４３８の歪曲が発生することが分かる。従来方法では、ＲＤカーブで歪曲を最小化するノードを優先的に符号化して伝送する。そのために、ＲＤカーブの傾きを小さくするノードが選択されて伝送され、それと共に、ノードの位置情報も共に伝送される。本研究で、そのような付加情報を除去してＲＤカーブを改善し、向上した結果が得られた。
【０１３３】
そのように、符号化および復号化の実験結果、本発明による方法が、圧縮率および画質面で向上した結果を示した。ビットストリームの生成時の位置情報およびノードの継続如何を知らせる情報を除去し、それを補完するために、優先順位キューを使用する変形されたＢＦＳアルゴリズムを利用することで、圧縮率面で向上した結果が得られた。結果的に既存研究と比較すれば、同じ量のビットを伝送しても、歪曲程度を減らすことでより良い結果が得られた。
【０１３４】
結局、本発明による方法は、既存方法に比べてポイントテクスチャ深さデータを更に効果的に圧縮でき、また、プログレッシブな伝送時に、３次元オブジェクトを視覚的に更に自然に表現できる。効率的な圧縮のために、ビットストリームを構成する情報の量を減らしうる方法を提案し、以後変形されたＢＦＳや解像度情報を利用して情報が除去されても、デコーディングおよび表現するのに問題が無いようにした。実験結果、深さデータに対して、３２〜５２％の圧縮率を向上させることができた。また、変形されたＢＦＳアルゴリズムは、プログレッシブな視覚化を支援することで、３Ｄオブジェクトの視覚的な質の面で更に自然な結果が得られた。
【０１３５】
本発明は、図面に示された実施例を参考して説明されたが、これは例示的なものに過ぎず、当業者ならば、これから多様な変形および均等な他の実施例が可能であるという点が理解できるであろう。したがって、本発明の真の技術的範囲は、特許請求の範囲の技術的思想によって決まらねばならない。
【産業上の利用可能性】
【０１３６】
本発明は、莫大な量の３次元体積データを高効率で符号化および復号化するのに有効に使用される。また、固定された解像度の体積データだけでなく、任意の解像度の体積データも高効率で符号化でき、少量のデータで高画質の３次元体積データを復元できる３次元データ処理分野に有効に利用できる。また、プログレッシブなビットストリームを生成するため、デコーディング時に３次元体積データをプログレッシブに示し、多様な３次元データの処理環境で使用できる。
【図面の簡単な説明】
【０１３７】
【図１】３次元オブジェクトを取り囲む六面体の各面で見られる参照映像を示した図面である。
【図２】３次元オブジェクトの表面を構成するポイントを、一平面に投影して平面の各深さラインに沿って配列したものを示した図面である。
【図３】ツリー構造における親子関係を示す図面である。
【図４】オクトツリーの場合、親ノードを、同じ大きさを有する８個の子ノードに分ける順序の一例を示した図面である。
【図５】適応的オクトツリーの概念を更に容易に説明するための、適応的クワッドツリーを示した図面である。
【図６】適応的オクトツリーの概念を更に容易に説明するための、適応的クワッドツリーを示した図面である。
【図７Ａ】本発明による３次元体積データ符号化装置の構成を示したブロック図である。
【図７Ｂ】本発明による３次元体積データ符号化方法を示したフローチャートである。
【図８】前記適応的オクトツリー変換部７２０の細部構成を示したブロック図である。
【図９】図５（ｃ）に示されたクワッドツリーのノードの符号化のためのノード訪問順序を示した図面である。
【図１０】図６（ｃ）に示されたクワッドツリーのノードの符号化のためのノード訪問順序を示した図面である。
【図１１】ノード符号化部の細部構成を示したブロック図である。
【図１２】ルートノードをＳノードとして符号化するとき、その下位子ノードのラベルを示した図面である。
【図１３】体積素をＰＰＭ符号化するとき、使用するコンテクストを示した図面である。
【図１４】符号化された結果、生成されるビットストリームのフォーマットを示した図面である。
【図１５】本発明による３次元体積データ復号化装置を示したブロック図である。
【図１６】ノード復号化部の更に詳細な内部構成を示したブロック図である。
【図１７】Ｓノード復号化部の細部構成を示したブロック図である。
【図１８】Ｐノード復号化部の細部構成を示したブロック図である。
【図１９】本発明による３次元体積データ復号化方法を示したフローチャートである。
【図２０】ノード復号化部におけるノード復号化過程を示したフローチャートである。
【図２１】３×４の解像度における適応的オクトツリー復元の簡単な例を示した図面である。
【図２２】本発明による３次元体積データ符号化および復号化方法、ならびに装置の性能を、テストに利用される８個のポイントテクスチャテストモデルを示した図面である。
【図２３】Ａｎｇｅｌデータから伝送されるビットストリームによる歪曲程度を意味するＲＤカーブを示した図面である。
【図２４】Ａｎｇｅｌデータに対する伝送されるビットストリームによる歪曲程度を画質で表現した図面である。
【符号の説明】
【０１３８】
１５０    ビットストリーム読み取り部
１５００  ヘッダ復号化部
１５１０  エントロピ復号化部
１５２０  ノード復号化部
１５４０  適応的ツリー復元部
１５６０  ボクセルデータ復元部
【図２】
0004759291.tif 000012
【図３】
0004759291.tif 000013
【図４】
0004759291.tif 000014
【図５】
0004759291.tif 000015
【図６】
0004759291.tif 000016
【図７Ａ】
0004759291.tif 000017
【図７Ｂ】
0004759291.tif 000018
【図８】
0004759291.tif 000019
【図９】
0004759291.tif 000020
【図１０】
0004759291.tif 000021
【図１１】
0004759291.tif 000022
【図１２】
0004759291.tif 000023
【図１３】
0004759291.tif 000024
【図１４】
0004759291.tif 000025
【図１５】
0004759291.tif 000026
【図１６】
0004759291.tif 000027
【図１７】
0004759291.tif 000028
【図１８】
0004759291.tif 000029
【図１９】
0004759291.tif 000030
【図２０】
0004759291.tif 000031
【図２１】
0004759291.tif 000032
【図２３】
0004759291.tif 000033
【図１】
0004759291.tif 000034
【図２２】
0004759291.tif 000035
【図２４】
0004759291.tif 000036