３次元動画像の圧縮に用いる基本単位及び当該基本単位の生成方法、当該基本単位を用いた３次元動画像の圧縮方法
【課題】
３次元動画データ、特に実写３次元映像に対して、頂点の座標情報だけでなく、頂点が持つその他の属性データを効率よく圧縮でき、かつ、フレーム内圧縮、フレーム間圧縮両方に対応できる基本単位を提供する。
【解決手段】
３次元動画像の各フレームの３次元画像はポリゴン・メッシュ・モデルによって表現されており、各頂点は多次元座標系で表現される属性データを持っており、基本単位は、各フレームを表現するポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数に分割してなる小領域であって、各小領域に含まれる複数の頂点が持つ複数の属性データにＰＣＡ（主成分分析）を適用することで、前記複数の属性データの重心が前記多次元座標系の原点に、かつ前記複数の属性データが２次元平面上に沿って分布するように各属性データが移動されており、前記多次元座標系における各属性データの移動後の値及び移動情報が記憶されている。
３次元動画データ、特に実写３次元映像に対して、頂点の座標情報だけでなく、頂点が持つその他の属性データを効率よく圧縮でき、かつ、フレーム内圧縮、フレーム間圧縮両方に対応できる基本単位を提供する。
【解決手段】
３次元動画像の各フレームの３次元画像はポリゴン・メッシュ・モデルによって表現されており、各頂点は多次元座標系で表現される属性データを持っており、基本単位は、各フレームを表現するポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数に分割してなる小領域であって、各小領域に含まれる複数の頂点が持つ複数の属性データにＰＣＡ（主成分分析）を適用することで、前記複数の属性データの重心が前記多次元座標系の原点に、かつ前記複数の属性データが２次元平面上に沿って分布するように各属性データが移動されており、前記多次元座標系における各属性データの移動後の値及び移動情報が記憶されている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元動画像データの圧縮に係り、より具体的な態様例では、複数のカメラを用いて多視点で撮影された画像から取得された実写３次元映像の圧縮に関するものである。
【背景技術】
【０００２】
近年、多視点で撮影された映像から実世界の３次元モデル・シーケンスを生成する技術の研究が盛んになっている（非特許文献１）。具体的には、動く３次元被写体を複数の同期カメラから撮影し、その動画像群から時間と共に形状が変化する３次元映像を再構成する技術であり、いわば実写３次元映像を生成する技術である。実写３次元映像は、３６０度どこからでも閲覧できる映像であり、２Ｄ＋奥行からなる３次元の実写映像とは区別されるものである。実写３次元映像システムを用いると、実空間での被写体を仮想空間上で容易に再構成することができ、ユーザが視点を変えながら見ることができるインタラクティブなコンテンツとしての応用が期待されている。
【０００３】
実写３次元映像は、各フレームがポリゴン・メッシュ・モデルにより記述された３次元モデルのシーケンスで表現されており、多数の頂点、頂点同士の結線関係、色情報など、多数のデータから構成されているため、データ量が非常に大きい。したがって、実写３次元映像をＤＶＤなどに収録して流通させたり、インターネット上で配信したりするためには、データの圧縮技術が必要不可欠である。
【０００４】
これまで、実写３次元映像を圧縮しようとする試みは、ほとんどなされていない。これは、実写３次元映像を生成する技術自体がまだ広く普及していないばかりでなく、実写３次元映像の各フレームで当該フレーム内の頂点の数や結線情報が毎回変わることが多いため、処理が極端に困難なためである。尚、本明細書では、実写３次元映像をTVMｓ（Time−Varying Meshes）とも記載する。
【０００５】
従来の実写３次元映像の研究としては、Skin-Off法（特許文献１、非特許文献２）、拡張３次元ブロックマッチング法（非特許文献３）、多段階ＲＬＥ法（非特許文献４）などがある。Skin-Off法は３次元モデルに切れ目を入れて２次元映像として表現し直すことで、現在広く使われている２次元映像圧縮技術を適用しようとするものである。拡張３次元ブロックマッチング法、多段階ＲＬＥ法は、実写３次元映像のデータのうち、頂点の座標データのフレーム間圧縮（フレーム間にある時間的な冗長性の圧縮）のみを対象としており、フレーム内圧縮（１フレーム内にある空間的な冗長性の圧縮）、及び、結線情報や色情報など、他のデータには対処できない。
【０００６】
また、３次元ＣＧ映像圧縮のための技術は古くから研究されているが、ＣＧではほとんどの場合において頂点数、結線関係などは全てのフレームに亘って一定で、頂点の位置のみが変わるだけであるため、データの性質が実写３次元映像と異なる。３次元ＣＧは人間が専用のソフトウェアを用いて作成するため、メッシュのデータ構造なども数学的に扱いやすい構造になっているのに対して、実写３次元映像では多視点映像から自動的に生成するため、ノイズや数学的に扱いにくい結線構造などが多数存在してしまう。そのため、３次元ＣＧ映像圧縮のための技術はそのまま実写３次元映像に適用することはできない。
【０００７】
したがって、実写３次元映像に対して、頂点の座標情報だけでなく、頂点に帰属する様々なデータを効率よく圧縮でき、さらにフレーム内圧縮、フレーム間圧縮両方に対応できる手法が求められる。
【０００８】
３次元映像データの圧縮において、３次元映像の圧縮や処理に必要なデータの「基本単位」をどう定めるかは重要である。２次元画像や２次元映像には、「ピクセル」という概念があり、画像や映像は予め決められた格子状の細かい点列で表現されている。よって、２次元画像や映像はデータが規則正しく並んでおり、それを４×４や８×８のブロックに細かく分割し、それを処理の基本単位としている。それに対して、実写３次元映像では、ピクセルに相当する概念が存在しない。ポリゴン・メッシュを表現する頂点は、３次元空間の任意の場所に存在できるため、格子状に並んでいるわけではない。また、空間を無理矢理格子状に区切ったとしても、全ての格子点上に頂点が存在するわけではない。また、２次元映像には存在しない、結線情報も問題を複雑にしている。そのため、実写３次元映像を効率的に処理できるようにするための「基本単位」をいかに定めるかが重要である。また、映像の圧縮にはフレーム内圧縮とフレーム間圧縮の２つの圧縮が存在する。それぞれの処理で異なる基本単位を用いたのでは、処理、開発コストの面で効率が悪いため、フレーム内・フレーム間圧縮両方で共通に利用できる基本単位が望ましい。
【０００９】
「基本単位」については、３次元CGアニメーションに対して、頂点数と結線の数を略等しくするようにメッシュを分割してそれを基本単位とする手法（非特許文献５）、同じ動きをする頂点群を自動的に抽出して基本単位とする手法（非特許文献６）が提案されている。実写３次元映像に対して、３次元空間を一定間隔で賽の目状に切断し、その中に含まれる頂点を基本単位とする手法（非特許文献３）もある。これらの文献に開示された基本単位は、後述する本発明の基本単位とは構造が異なる。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】ＷＯ２００６／０６２１９９
【非特許文献】
【００１１】
【非特許文献１】K. Tomiyama, Y. Orihara, M.Katayama, and Y. Iwadate, “Algorithm for dynamic 3Dobject generation from multi-viewpoint images,” Proc. SPIE, vol. 5599, pp.153-161, 2004.
【非特許文献２】H. Habe, Y. Katsura, and T.Matsuyama,“Skin-off: representation and compression scheme for 3D video,” PCS, pp.301306, 2004.
【非特許文献３】S.R. Han, T. Yamasaki, and K. Aizawa,“Time-varying mesh compression using extended block matching algorithm,” IEEETCSVT, vol. 17, no. 11, pp. 1506-1518, 2008.
【非特許文献４】S.R. Han, T. Yamasaki, and K.Aizawa, “Geometry compression for time-varying mesh using coarse and finelevels of quantization and run-length encoding,” IEEE ICIP, pp. 10451048, 2008.
【非特許文献５】Z. Karni and C. Gotsman,“Spectral compression of mesh geometry,” ACM SIGGRAPH, pp. 279-286, 2000.
【非特許文献６】S. Gupta, K. Sengupta, and A.Kassim, “Registration and partitioning-based compression of 3-D dynamic data,”IEEE TCSVT, vol. 13, no. 11, pp. 1144-1155, 2003.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明は、３次元動画データ、特に実写３次元映像に対して、頂点の座標情報だけでなく、頂点が持つその他の属性データを効率よく圧縮でき、かつ、フレーム内圧縮、フレーム間圧縮両方に対応できる基本単位及び当該基本単位を用いた圧縮法を提供することを目的とするものである。
【課題を解決するための手段】
【００１３】
本発明が採用した技術手段は、
３次元動画像の圧縮に用いる基本単位であって、
３次元動画像の各フレームの３次元画像はポリゴン・メッシュ・モデルによって表現されており、各頂点は多次元座標系で表現される属性データを持っており、
前記基本単位は、各フレームを表現するポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数に分割してなる小領域であって、
各小領域に含まれる複数の頂点が持つ複数の属性データにＰＣＡ（主成分分析）を適用することで、前記複数の属性データの重心が前記多次元座標系の原点に、かつ前記複数の属性データが２次元平面上に沿って分布するように各属性データが移動されており、前記多次元座標系における各属性データの移動後の値及び移動情報が記憶されている、基本単位、である。
典型的な態様では、前記属性データには位置情報、色情報が含まれる。前記属性データとしては、法線情報や反射特性等の他のデータを含み得る。
基本単位は、属性データの種類毎に独立して用意される。
【００１４】
１つの態様では、前記３次元動画像は、被写体を多視点から撮影した複数の画像を統合してなる実写３次元動画像である。各フレームの３次元画像がポリゴン・メッシュ・モデルによって表現されている実写３次元動画像は、例えば、非特許文献１に開示された方法で生成されるが、本発明において、実写３次元動画像の生成方法は限定されない。
【００１５】
本発明が採用した他の技術手段は、
３次元動画像の圧縮に用いる基本単位の生成方法であって、
３次元動画像の各フレームの３次元画像はポリゴン・メッシュ・モデルによって表現されており、各頂点は多次元座標系で表現される属性データを持っており、
各フレームを表現するポリゴン・メッシュ・モデルを、ほぼ等面積になるように分割して複数の小領域を取得し、
各小領域に含まれる複数の頂点が持つ複数の属性データにＰＣＡ（主成分分析）を適用することで、前記複数の属性データの重心が前記多次元座標系の原点に、かつ前記複数の属性データが２次元平面上に沿って分布するように各属性データを移動させると共に、前記多次元座標系における各属性データの移動後の値及び移動情報を記憶してなる、基本単位の生成方法、である。
【００１６】
１つの態様では、ポリゴン・メッシュ・モデルの複数の小領域への分割は、測地線距離に基づいて行う。
【００１７】
本発明は、さらに、上記基本単位の生成方法をコンピュータに実行させるためのコンピュータプログラム、あるいは、当該コンピュータプログラムが記録された記録媒体としても定義される。
本発明に係る基本単位はデータ構造であり、基本単位の生成は１つあるいは複数のコンピュータによって実行される。本発明に係る圧縮方法も１つあるいは複数のコンピュータによって実行される。１つの態様では、コンピュータは、各種計算を行う演算処理部、３Dメッシュデータや計算結果等の各種データを格納する記憶部、３次元動画像を表示する表示部、コンピュータを操作するための入力部、計算結果等のデータを出力する出力部、を備えている。
【００１８】
本発明が採用した他の技術手段は、上記基本単位を用いてフレーム間圧縮を行う３次元動画像の圧縮方法であって、
ターゲットフレームにおけるポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数の小領域に分割すると共に、PCA（主成分分析）を適用して基本単位を生成し、
参照フレームにおけるポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数の小領域に分割すると共に、PCA（主成分分析）を適用して基本単位を生成し、
ターゲットフレームにおけるある基本単位と、参照フレームにおける各基本単位との距離を各頂点が持つ属性データに基づいて計算し、最も距離が近い基本単位を参照基本単位として選択するステップと、
ターゲットフレームにおける各基本単位と当該基本単位に対応する参照フレームにおける参照基本単位との差分情報を取得するステップと、
前記差分情報を圧縮するステップと、を備えている圧縮方法、である。
１つの態様では、前記参照フレームのポリゴン・メッシュ・モデルは、上記基本単位の属性データに対して圧縮処理を適用することでフレーム内圧縮が行われたポリゴン・メッシュ・データを復号してなるデータであり、当該参照フレームポリゴン・メッシュ・モデルの基本単位は、フレーム内圧縮時に生成されている。
参照フレームのフレーム内圧縮を基本単位を用いない手法で行った場合には、フレーム間圧縮の時に参照フレームにおけるポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数の小領域に分割すると共に、PCA（主成分分析）を適用して基本単位を生成すればよい。
【００１９】
本発明が採用した他の技術手段は、上記基本単位の属性データに対して圧縮処理を適用することでフレーム内圧縮を行う３次元動画像の圧縮方法、である。
【００２０】
差分情報の圧縮、フレーム内圧縮において、頂点の属性データ（位置情報、色情報等）の圧縮には、既存の圧縮手法（不可逆圧縮、可逆圧縮を問わない）を広く適用できることが当業者に理解される。
具体的に例示すると、スカラー量子化、VQ(ベクトル量子化)、BTC（Block Truncation Coding）、ラプラシアン行列によるメッシュの周波数解析（Spectral compression）、DCT(離散コサイン変換、Discrete Cosine Transform)、ウェーブレット変換、エントロピー符号化（ハフマン符号、算術符号、CABAC(Context-based Adaptive Binary Arithmetic Coding)など）から選択された１つ以上の圧縮方式を用いて圧縮を行うことができる。
【発明の効果】
【００２１】
本発明に係る３次元動画像圧縮のための基本単位は、フレーム間圧縮、フレーム内圧縮で用いられる従来の圧縮手法を適用できるデータ構造になっており、しかも、頂点の座標情報、および色情報等の頂点の属性データの分布は非常に局所的になり、圧縮前のデータのばらつきが小さいため、効率良くデータを圧縮することができる。また、本発明の基本単位は、頂点の位置情報のみならず、頂点が持つ他の属性データの圧縮を行うことができる。
【００２２】
基本単位において、基本単位のサイズがほぼ一定であり、かつ、頂点が持つ属性データの値の重心がほぼ一致し、属性データ（頂点の位置情報、色情報等）の広がりもほぼ一致しているので、小領域同士のマッチングを容易に行うことができる。
【００２３】
本発明の効果は上記記載に限定されるものではなく、その他の効果は、本明細書の記載から明らかになる。
【図面の簡単な説明】
【００２４】
【図１】本発明に係る圧縮方法の概要を示す全体ブロック図である。
【図２】３次元映像の一般的な表現方法を示す図である。
【図３】ポリゴン・メッシュ・モデルを、ほぼ等面積になるように分割した状態を示す概念図、及び、分割した小領域の頂点の座標値にPCA（主成分分析）を適用した基本単位の生成を示す概念図である。
【図４】VQ(ベクトル量子化)を用いたフレーム内圧縮の処理の流れを示す概念図である。
【図５】PCA（主成分分析）適用後のあるフレームにおける各小領域内の頂点の座標情報の分布を示す図である。
【図６】PCA（主成分分析）適用後のあるフレームにおける各小領域内の頂点の色情報の分布を示す図である。
【図７】フレーム間圧縮における参照フレーム内の小領域（基本単位）とターゲットフレーム内の小領域（基本単位）とのマッチングを示す概念図である。
【図８】ターゲット小領域（基本単位）と参照小領域（基本単位）との距離計算及び差分情報の記録方法を示す概念図である。
【図８Ａ】従来の差分情報の記録を説明する図である。
【図８Ｂ】本実施形態に係る差分情報の記録を説明する図である。
【図９】ターゲットフレームと参照フレーム間の頂点の位置情報の差分情報の分布を示す図である。
【図１０】ターゲットフレームと参照フレーム間の頂点の色情報の差分情報の分布を示す図である。
【図１１】Kimono-Ladyシーケンスに対するフレーム内圧縮の性能を示す図であり、左図は頂点の位置情報の圧縮、右図は頂点の色情報の圧縮を示す。
【図１２】Kimono-Ladyシーケンスに対するフレーム間圧縮の性能を示す図であり、左図は頂点の位置情報の圧縮、右図は頂点の色情報の圧縮を示す。
【発明を実施するための形態】
【００２５】
［Ａ］３次元動画像圧縮の概要
図１に本実施形態に係る３次元動画像圧縮のアルゴリズムを示す。先ず、オリジナルの３ＤメッシュモデルＭｉを複数の小領域（図１では、patchと表現されている）に分割する。小領域への分割は、各小領域の面積が略同じ面積となるように行う。次いで、各小領域の頂点が持つ属性データ（頂点の位置情報、頂点が有する色情報等）に対してPCA（主成分分析）を適用して圧縮のための基本単位を生成する。属性データが位置情報であれば、各小領域の頂点の座標値の重心が世界座標系（x,y,z）の原点となるように、各座標値を変換することで、各小領域の向き・姿勢を調整する。属性データが色情報の場合、R,G,B座標系の原点に重心が来るように色値を変換する。
【００２６】
フレーム内圧縮では、各頂点に帰属する冗長な空間情報を利用する。頂点の位置情報は空間的にコヒーレントな情報であるため、本実施形態ではラプラシアン行列によるメッシュの周波数解析であるSpectral compression（非特許文献５、または、R. Ohbuchi, A. Mukaiyama, and S. Takahashi, “A Frequency-domain
approach to watermarking 3D shapes,” Computer Graphics Forum, vol. 21, pp.
373-382, 2002.）と量子化を組み合わせることで頂点の座標の圧縮を行う。一方、頂点が持つ色情報は空間的にコヒーレントではないため、本実施形態ではＶＱあるいはスカラー量子化が色情報の圧縮に用いられる。圧縮によって得られたデータはエントロピー符号化される。
【００２７】
フレーム間圧縮においては、フレーム内圧縮からデコードされた参照フレーム（Ｍ＾ｒｅｆ）の３Ｄメッシュモデルから生成された基本単位と、ターゲットフレーム（Ｍｊ）の３Ｄメッシュモデルから生成された基本単位と、を用いる。本実施形態では、参照フレームの基本単位については、フレーム内圧縮を行う時に生成されて、記憶されている。したがって、フレーム間圧縮にあたっては、ターゲットフレームの３Ｄメッシュモデルのみを小領域に分割して、基本単位を生成すればよい。そして、ターゲットフレームにおける小領域（基本単位）と参照フレームにおける小領域（基本単位）との間で小領域同士のマッチングを実行し、参照フレームから最も近い小領域（基本単位）を探索する。差分情報、すなわち、頂点の座標情報においては（△x, △y, △z）、頂点が持つ色情報においては（△R, △G, △B）をスカラー量子化あるいはＶＱ等の圧縮手段を用いて圧縮する。圧縮によって得られたデータはエントロピー符号化される。
【００２８】
連結情報の圧縮においては、静的３Ｄメッシュモデルに用いられている高性能アルゴリズムを適用することができる。また、各小領域における頂点数は比較的少ないので、各小領域の頂点ＩＤの番号を振り直すことによっても連結情報のビットレートを低減することができる。
【００２９】
［Ｂ］圧縮対象となる３次元動画像データ
３次元動画像データは、２Ｄビデオと同様に、連続するフレームのシーケンスから構成されており、各フレームは、ポリゴン・メッシュ・モデルによって表されている。すなわち、各フレームは、頂点座標、頂点の連結（トポロジー）、色情報の３つの情報によって表現されている。ここで、多くの場合、Marching cubes アルゴリズム（W.E. Lorensen and H.E.
Cline, “Marching cubes: A high resolution 3D surface construction algorithm,”
ACM SIGGRAPH, pp. 163-169, 1987.）等によって３Ｄボクセルモデルを３Ｄメッシュ（表面）モデルに変換するため、メッシュは規則的とは限らない。
【００３０】
データの概要を表１に示す。３次元動画像データは、非特許文献１に関連するデータである。３次元動画像データは、２２個の同期カメラを用いた多視点映像から生成されたものである。
【表１】
また、３次元映像の一般的な表現方法（データ構造）を図２に示す。各フレームにおいて、各頂点にはIDが順に割り当てられ、各頂点の属性データ（座標値、色値）がコンピュータの記憶部に記憶されている。また、どのIDにより三角パッチが形成されているかの情報も記憶部に記憶されている。この基本的な表現方法は、小領域（基本単位）においても同様である。
【００３１】
［Ｃ］基本単位の生成
データ圧縮のための基本単位の生成について説明する。
［Ｃ−１］小領域の形成
先ず、圧縮対象となる実写３次元映像フレームが与えられたとき、オリジナルの３Ｄメッシュモデルの表面形状を各小領域の面積が略等面積になるような条件下で、複数の小領域に分割する。本実施形態では、小領域の半径をr=sqrt(0.001xArea(M))と設定した。ここで、Area(M)は３Ｄメッシュモデルの総面積である。この条件において、本実施形態では各小領域には１００〜２００の頂点が含まれることになる。
【００３２】
３Dメッシュモデルを略等面積の小領域に分割するためには、測地線距離が計算できればよく、例えば、Dijkstraアルゴリズムを用いてメッシュモデルを小領域に分割することができる。Dijkstra法自体は当業者によく知られた手法でありるので、詳細な説明は省略する。また、dijkstra法を用いて測地線距離を近似することは、M. Hilaga, Y. Shinagawa, T. Kohmura, T.L. Kunii: Topology matching
for fully automatic similarity estimation of 3D shapes. Proceedings SIGGRAPH,
203-212(2001).に開示されており、当該文献に開示された手法を用いて３Dメッシュモデルを略等面積の小領域に分割してもよい。なお、この文献は、３Dメッシュモデルを略等面積の小領域に分割する点において、本発明と共通する部分があるが、３次元メッシュモデルから骨格構造を抽出するための中間処理として用いているだけで、実写３次元映像圧縮のための基本単位として用いるものではない。また、本手法は、メッシュを一定面積の小領域に分割した後、PCA(主成分分析）を用いて小領域に含まれる頂点が持つ属性データを変換しており（属性データが位置情報の場合には、小領域の姿勢・方向補正を行うことになる）、この変換の結果までを含めて基本単位としている。小領域の頂点が持つ属性データを、属性データの重心及び属性データ（頂点の位置情報、色情報等）の広がりがほぼ一致するように変換することは、小領域同士を対応させて距離を計算したり差分を計算したりする上で、有利である。
【００３３】
本発明のアプローチは、メッシュを略同じ面積の小領域に分割することによって小領域間での空間的対応付けを容易に行うものである。メッシュを略等面積の小領域に分割することで、結果として、比較的同じような頂点の数、結線数が各小領域に含まれることになり、小領域同士のマッチングが容易となる。小領域の寸法は、圧縮効率を考慮することで決定されるが、典型的には、小領域は概ねフラットディスク様の形状である程度に小さいものである。
【００３４】
各小領域はポリゴン・メッシュの三角パッチの群であり、三角パッチ群の面積がほぼ同じあると考えることができる。また、三角パッチ群の周縁に位置する三角パッチは三角パッチの部分（分割する時に三角パッチが切断される）であってもよく、三角パッチ群を形成する三角パッチには完全でない三角パッチも含まれ得る。すなわち、小領域の縁の部分に存在する三角形は、不完全なものとなっており、圧縮されたデータを完全に元に戻すためには、「どこを切った」という情報を記憶しておく。切断される結線情報は、全体の結線の中の一部なので、それを記憶しておくためのデータ量はそれほど大きくない。
【００３５】
［Ｃ−２］PCA(主成分分析)の適用
各フレームを表現するポリゴン・メッシュ・モデルを、ほぼ等面積になるように分割して得られた小領域の各頂点が持つ各属性データ（位置情報や色情報）に対してPCA（主成分分析）を適用することで、各属性データ毎に独立した基本単位を生成する。
【００３６】
小領域に含まれる頂点が持つ位置情報については、各小領域に対してPCA（主成分分析）を行うことで、各小領域に含まれる多数の頂点の座標値の平均値である重心にｘｙｚ座標の原点が移動すると共に、各頂点の座標が回転する。頂点の位置情報は重心が原点に位置すると共に、例えばｘｙ平面近傍に沿って分布することになる。すなわち、各小領域の重心が世界座標系の原点となり、分布方向が概ね２次元平面（例えば、ｘｙ平面）となるように各小領域の向き・姿勢が補正され、様々な方向を向いている小領域の方向を合わされる。図３に示すように、フラット状の小領域（基本単位）はｘｙ平面に沿って配向されることになり、ｚ軸寸法は小さい。
【００３７】
小領域に含まれる頂点が持つ色情報については、各小領域に対してPCA（主成分分析）を行うことで、各小領域に含まれる多数の頂点の色値（R,G,B）の平均値である重心にRGB座標の原点が移動すると共に、各頂点の座標が回転する。色情報についての「基本単位」は、頂点の位置情報の基本単位と独立して用意される。
【００３８】
３次元メッシュモデルを小領域に分割すると共に、小領域内の頂点が持つ属性データにPCA（主成分分析）を施すことで基本単位を生成することによって、頂点の座標情報、および色情報の分布は非常に局所的になり、圧縮に適したデータ構造となる。図５、図６に示すように、頂点が持つ属性データ（位置情報、色情報）はそれぞれ２次元平面に沿って分布している。基本単位の向きを２次元平面（典型的にはxy平面であるが、yz, zx平面でもよい）に沿うように局所的に分布させることで、効率よくデータを圧縮することができる。例えば、０〜７の間に分布する整数だと3ビットで表現できるのに対して、０〜２５６の間に分布する整数だと8ビット必要となる。向きを考慮せずに適当な方向で小領域を配置すると、x, y, zそれぞれに大きな幅をもって分布するのに対して、xy平面上に沿って分布するように方向補正をするとz方向の分布は殆どないことが予めわかるので、必要なデータ量を小さくすることができる。
【００３９】
また、基本単位において、頂点が持つ属性データの値の重心がほぼ一致し、属性データ（頂点の位置情報、色情報等）の広がりもほぼ一致していることは、少領域同士を対応させて比較する場合に有利である。小領域のサイズや頂点が持つ属性データの分布は小領域間で互いに略同じなので、小領域同士のマッチングを容易に行うことができる。
【００４０】
また、元々の位置・姿勢から上記補正をするために行った平行移動、回転移動のパラメータを記憶部に記憶しておく。１つの態様では、３次元メッシュモデルを分割してなる各小領域にIDが付されており、かつ、小領域毎に、当該小領域に含まれる頂点にIDが付されており、頂点の各IDに対応して元の属性データ（位置情報や色情報）の値、移動後の属性データ（位置情報や色情報）の値、及び、平行移動、回転移動のパラメータが記憶されている。
【００４１】
その後、それぞれの基本単位の頂点が持つ属性データに対して、フレーム内圧縮、フレーム間圧縮の処理を行う。頂点の座標情報、および色情報の具体的な圧縮には様々な従来の圧縮手法が利用可能である。例えば、ベクトル量子化（ＶＱ）、Spectral Compression, Block Truncation Coding (BTC)などで優れた圧縮性能が得られることが実験の結果わかっている。
【００４２】
［Ｄ］フレーム内圧縮
図５、図６に示すように、３次元メッシュモデルを小領域に分割すると共に、小領域内の頂点が持つ属性データにPCA（主成分分析）を適用して基本単位を生成することによって、頂点の座標情報、および色情報の分布は非常に局所的になり、圧縮に適したデータ構造となる。
【００４３】
フレーム内圧縮については、各小領域内にある頂点の位置情報の空間的相関が高いことを利用して、頂点の位置情報を効率よく圧縮できる。頂点座標は空間的に互いに相関しているので、１つの態様では、Spectral compression（非特許文献５）を用いて圧縮を行うことができる。本実施形態では、Kirchhoff行列を用いる（非特許文献５、R. Ohbuchi, A. Mukaiyama, and S. Takahashi, “A Frequency-domain
approach to watermarking 3D shapes,” Computer Graphics Forum, vol. 21,
pp. 373-382, 2002.）。Kirchhoff行列は以下のように定義される。
ここで、Ａはｎ頂点メッシュトポロジー
によって定義される隣接行列であり、
ＤはＤii=diとなるような対角行列、diは頂点iの次元である。
【００４４】
行列Ｋの固有ベクトルは基底関数の集合を形成する直交ベクトルである。関連する固有値は周波数に対応しており、ある小領域の頂点の座標ベクトル（ｘ、ｙ、ｚ）の投影は入力ベクトルのスペクトルとみなすことができる。そして、１０〜５０％のより低い周波数のスペクトル値のみを用いる。残りの高周波成分は単純化のため０とする。量子化されたスペクトル値はハフマンエンコーダを用いてエントロピー符号化される。
【００４５】
各頂点に帰属する色情報を圧縮するためには、ＶＱ（ベクトル量子化）あるいはスカラー量子化を用いることができる。ＶＱは頂点の色情報を構成する３次元ベクトル（Ｒ，Ｇ，Ｂ）に適用される。コードブック及びベクトルのインデックスはさらにハフマンエンコーダによって圧縮される。スカラー量子化を用いる場合には、最小値及び最大値が抽出され、座標ベクトルがスカラー量子化される。
【００４６】
表２に、頂点の座標情報、および色情報の圧縮のために必要な情報と、それぞれに必要なデータ量を簡単に記載したものを示す。各フレーム間で基本単位（小領域）の寸法はほぼ同じなので、コードブック設計は最初のフレームについて行えばよく、コードブックの一部を省略することが可能である。
【表２】
【００４７】
本実施形態では、圧縮に用いられる基本単位が、フレーム間圧縮およびフレーム内圧縮の両方に適用できる。これは例えば電子機器での実装やハードウェア化など、特定の制約の下でシステムを設計したいときには有利である。なお、フレーム内圧縮及びフレーム間圧縮を行う場合に、フレーム内圧縮に既存の圧縮手法を用い、フレーム間圧縮に本発明の基本単位を用いてもよい。
【００４８】
［Ｅ］フレーム間圧縮
フレーム間圧縮については、処理対象となるターゲット小領域（基本単位）と、参照フレームから生成される小領域（基本単位）群とのマッチングを行い、もっとも似ている参照小領域（基本単位）を探索する。その後、どの小領域に最も近かったかという情報、小領域間の頂点の対応関係を記憶すると共に、ターゲット小領域と参照小領域との対応する頂点の属性データ間の差分を取ることにより、頂点の座標情報、および色情報の分布範囲を小さくすることができる。それによって、ベクトル量子化やその他様々な圧縮処理を適用することによって頂点情報、及び色情報を効率よく圧縮できる。
【００４９】
効率的な圧縮をするためには、データのばらつきの範囲が小さいことが重要である。今回の場合、差分の値はできるだけ値が小さく、また、ばらつきの範囲（ダイナミックレンジ）も小さいほど圧縮の効率はよくなる。基本単位を用いないと、そもそも小領域の位置や方向がそろってないので、結果として得られる差分値は値が大きく、またばらつきも大きいためにほとんど圧縮ができない。そのため、基本単位を定義して位置合わせがほぼなされていると仮定した上で似ている小領域（基本単位）を探し、差分情報を取得することが有利である。
【００５０】
フレーム間における時間的相関を除去するために、小領域同士のマッチングが用いられる。ターゲットフレームにおけるある小領域と、参照フレームにおける全ての小領域との類似度は、以下の式によって評価される。
ここで、d(Pref,m, Pj,n)は参照フレームにおけるｍ番目の基本単位Pref,mとｊ番目フレームにおけるｎ番目の基本単位(Pj,n)との非類似度である。Euclideanは、ユークリッド距離である。vs、vtはPref,mのｓ番目の頂点の座標値あるいは色値、Pj,nのｔ番目の頂点の座標値あるいは色値である。参照フレームにおける最小のd(Pref,m, Pj,n)を生成する最も近い小領域が参照小領域として用いられる。
【００５１】
より具体的に説明すると、ターゲットフレームにおけるある小領域（基本単位）内の、ある１つの頂点座標に注目する。参照フレームにおけるある小領域（基本単位）の全ての頂点の属性値（座標や色）とユークリッド距離を計算し、距離が最小となる頂点を探す。頂点が保有する情報として位置情報と色情報があるが、小領域間の類似度を計算する場合には、位置情報の類似度、色情報の類似度は属性の種類ごとに独立して別個に計算される。距離が最小となる頂点を「対応のとれた」頂点とする。この処理を、ターゲットフレームにおけるある小領域（基本単位）内の全ての頂点に対して行う。距離の総和がターゲットフレームにおけるある小領域（基本単位）と参照フレームにおけるある小領域（基本単位）の「小領域同士の距離」となる。ターゲットフレームにおけるいま注目している小領域（基本単位）に対する参照小領域（基本単位）は、この「小領域同士の距離」が最小となる参照領域のことを指す。なお、ターゲットフレームにおけるある小領域の頂点と参照フレームにおけるある小領域の頂点同士の一対一対応をとっているわけではなく、「どれが一番近いか」というのを計算しているだけなので、それぞれの領域に含まれる頂点の個数は関係ない。
【００５２】
圧縮のための他の重要な情報は、ターゲットフレームにおける小領域（基本単位）内の頂点と参照フレームにおける小領域（基本単位）内の頂点との対応データである。すなわち、差分情報を計算するには、圧縮対象であるターゲット小領域のある頂点が、参照小領域のどの頂点と差分を計算したか、ということを記憶しておく必要がある。非特許文献３では、参照フレームのどの頂点と差分を計算したかを記憶するために、ブロックの中に含まれる頂点に順に0, 1, 2・・・とID番号を振って、何番目の頂点と差分を計算したか、ということを記憶している（図８A参照）。ブロックには平均的に数十個程度の頂点が含まれていたために、IDを表現するために頂点当たり6ビット程度(ID: 0-63)のデータが必要となる。さらに、それぞれのIDの使用頻度はほぼ同じなので、エントロピー符号化などさらなる圧縮はあまり有効でない。これに対して、本実施形態では、圧縮対象であるターゲット小領域に含まれる頂点が、まず参照小領域のどのIDの頂点に対応するか判別し、対応するIDの小さい順に並べ直す（ソートする）。ここで、「並べ直す」というのは、頂点の3次元空間上の位置は変化しないので、データを保存するときの順番を並び替える、という意味である。そうすると、記憶すべき情報は、ターゲット小領域内のそれぞれの頂点が参照小領域内のどのIDの頂点との差分を計算したか、ではなく、参照小領域のIDがxx番の頂点と差分を計算したターゲット小領域内の頂点はいくつあったか、ということになる（図８B参照）。すなわち、頂点の個数を記憶するだけなので、０〜５くらいの数字が頻繁に現れることになる。したがって、6bitは必要なく、例えば3bitあれば０〜５の数字は表現できるため、6bitは必要なく、それだけデータ量は少なくて済み、また、使用頻度を表現する数字は全て同じ頻度で現れるのではなく、典型的には０〜２が頻繁に現れる。そのため、エントロピー符号器を用いて効率的に符号化できる。
【００５３】
表３に、圧縮に必要な情報とそのデータ量を示す。
【表３】
【００５４】
ターゲット小領域における属性データと、参照小領域におけるそれらに対応する属性データとの差である差分データセットはさらに圧縮される。差分データの圧縮には、スカラー量子化手法やVQ（ベクトル量子化）を用いることができる。VQを用いる場合には、コードブック設計は最初のフレームと２番目のフレームとの間で一度だけ行えばよい。小領域の寸法が変わらない限り、残りのフレームに対して同じコードブックを用いることができる。差分データは図１０、図１１に示すように、図５、図６に示した元々のデータの分布に比べてさらに局所的になる。そのため、フレーム間圧縮はフレーム内圧縮よりもさらに効率的になる。
【００５５】
基本単位（小領域）を用いたマッチングの利点の一つは、フレーム内圧縮をシーケンスの最初のフレームにおいて行えば、他のフレームは最初のフレームを参照としてフレーム間圧縮できるということである。基本単位はPCA（主成分分析）によって空間的対応付けを取るように配向されている。なお、圧縮対象となっているターゲット小領域と最も「似通っている」小領域を、参照小領域群（前後フレームから生成）から効率的に探索するためには、例えばIterative closest point (ICP)と呼ばれるような、3次元の形状合わせのための手法なども使うことも可能である（P.J. Besl and N.D. McKay, “A method for registration of 3-D shapes,”
IEEE TPAMI, vol. 14, no. 2, pp. 239-256, 1992.）。しかしながら、ICPなどの形状あわせのための手法では、小領域同士がどれだけ似ているか、という計算をするたびに位置合わせを行う必要があり（小領域によって方向や位置が異なるため）、ICPは極めて計算コストが高い処理である。これに対して、予めPCAをかけておく本手法は、1度計算してしまうと位置や方向は全ての小領域で揃っているため、位置合わせのための計算は必要なく、位置合わせがほぼなされていると仮定した上で似ている小領域を探すだけの作業でよいため効率がよい。
【００５６】
何フレームに1回フレーム内圧縮を行うかについては、当業者において経験的に決定される。フレーム間圧縮は、フレーム内圧縮されたフレーム（画像）を参照データとして、圧縮対象のフレームとの差分だけを計算し、それを符号化することで高い圧縮率を実現する。ここで重要なのは、「圧縮対象のフレームは参照フレームとあまり変わっていない」という点である。変化が激しければ、それだけ差分情報が大きくなり、圧縮がしにくいデータとなってしまうため、参照フレームと圧縮対象のフレームの間はあまり時間的な差がない、すなわち参照フレームはできるだけ頻繁にある方がフレーム間圧縮の効率は上がる。一方、フレーム内圧縮はそれ自体あまり圧縮効率がよくないので、あまり頻繁にフレーム内圧縮を行うとフレーム内圧縮、フレーム間圧縮全体として見たときの圧縮効率は落ちてしまう。本実施形態との関連で言うと、3次元映像の圧縮、特に幾何情報（頂点情報）の圧縮では、頂点情報の空間的な広がりについて、参照フレームとの差分を計算する。小領域内の頂点の空間的な広がりはそれほど激しく変化することはない。また、色情報も同一物体を対象としている限り、物体が動きはするものの、色はそれほど変わらない。したがって、２次元動画像に比べて参照フレームの頻度が比較的少なくて良いと考えられる。
【００５７】
［Ｆ］実験結果
幾つかの異なる圧縮手法を用いてKimono-Ladyシーケンスに対して、フレーム内圧縮、フレーム間圧縮を実行して性能を比較した。以下の評価尺度を用いて圧縮性能を評価した。
ここで、Nは３Dメッシュモデルの頂点の数、Vi、Vi´は、それぞれ、i番目の元頂点座標、復号化された頂点座標である。
【００５８】
図１１は、Kimono-Ladyシーケンスに対するフレーム内圧縮の性能を示す図であり、左図は頂点の位置情報の圧縮、右図は頂点の色情報の圧縮を示す。頂点の位置情報の圧縮においては、Spectral compressionが効率的であることがわかる。色情報の圧縮においては、VQ（ベクトル量子化）やスカラー量子化が効率的であることがわかる。
【００５９】
図１２は、Kimono-Ladyシーケンスに対するフレーム間圧縮の性能を示す図であり、左図は頂点の位置情報の圧縮、右図は頂点の色情報の圧縮を示す。左図において、[3]、[4]はそれぞれ非特許文献３、非特許文献４に開示された手法による圧縮結果である。差分情報の圧縮にはVQ（ベクトル量子化）やスカラー量子化が効率的であることがわかる。
【００６０】
［Ｇ］連結情報の圧縮
最後に連結情報の圧縮について言及する。連結情報の圧縮については従来の手法を用いることができる。通常のCGデータの連結情報の圧縮手法として、以下のようなものが知られており、これらの手法を実写３次元画像用に修正して用い得ることが当業者に理解される。
DEERING, M. 1995. Geometry compression. In ACM SIGGRAPH 1995, 13−20.
ROSSIGNAC, J. 1999. Edgebreaker:
connectivity compression for triangle meshes. IEEE Trans. Visualization and
Computer Graphics 5, 1, 47−61.
TAUBIN, G., AND ROSSIGNAC, J. 1998. Geometric compression through topological surgery. ACM Transaction
on Graphics 17, 2 (April), 84−115.
また、それ以外にも下記の文献に網羅的に静止三次元モデルの圧縮手法についてはまとめられており、このうち、結線情報を圧縮する手法を用いることができる。
PENG, J., KIM, C.-S., AND KUO, C.-C. J. 2005. Technologies for 3d mesh compression: A survey. Journal of
Visual Communication and Image Representation 16, 688−733.
上記文献に開示された圧縮手法をフレーム内圧縮に適用してもよい。
【００６１】
また、Intra-ID compressionにより連結情報を圧縮してもよい。各小領域は数十〜200程度の頂点から成り立っており、それぞれの頂点に0からIDを付け、それぞれの三角形ポリゴンがどのIDの頂点同士を結んで成り立っているのかを表現する。元々の3次元モデル全体だと10万個程度の頂点があり、１つの頂点を表すIDは16〜17ビット必要となる、すなわち、3角形の３つの頂点を表現するのに約50ビット必要となる。これに対して、200程度の頂点であればIDを表現するために8ビットあれば十分なので3角形１つあたり24ビットで済む。
【技術分野】
【０００１】
本発明は、３次元動画像データの圧縮に係り、より具体的な態様例では、複数のカメラを用いて多視点で撮影された画像から取得された実写３次元映像の圧縮に関するものである。
【背景技術】
【０００２】
近年、多視点で撮影された映像から実世界の３次元モデル・シーケンスを生成する技術の研究が盛んになっている（非特許文献１）。具体的には、動く３次元被写体を複数の同期カメラから撮影し、その動画像群から時間と共に形状が変化する３次元映像を再構成する技術であり、いわば実写３次元映像を生成する技術である。実写３次元映像は、３６０度どこからでも閲覧できる映像であり、２Ｄ＋奥行からなる３次元の実写映像とは区別されるものである。実写３次元映像システムを用いると、実空間での被写体を仮想空間上で容易に再構成することができ、ユーザが視点を変えながら見ることができるインタラクティブなコンテンツとしての応用が期待されている。
【０００３】
実写３次元映像は、各フレームがポリゴン・メッシュ・モデルにより記述された３次元モデルのシーケンスで表現されており、多数の頂点、頂点同士の結線関係、色情報など、多数のデータから構成されているため、データ量が非常に大きい。したがって、実写３次元映像をＤＶＤなどに収録して流通させたり、インターネット上で配信したりするためには、データの圧縮技術が必要不可欠である。
【０００４】
これまで、実写３次元映像を圧縮しようとする試みは、ほとんどなされていない。これは、実写３次元映像を生成する技術自体がまだ広く普及していないばかりでなく、実写３次元映像の各フレームで当該フレーム内の頂点の数や結線情報が毎回変わることが多いため、処理が極端に困難なためである。尚、本明細書では、実写３次元映像をTVMｓ（Time−Varying Meshes）とも記載する。
【０００５】
従来の実写３次元映像の研究としては、Skin-Off法（特許文献１、非特許文献２）、拡張３次元ブロックマッチング法（非特許文献３）、多段階ＲＬＥ法（非特許文献４）などがある。Skin-Off法は３次元モデルに切れ目を入れて２次元映像として表現し直すことで、現在広く使われている２次元映像圧縮技術を適用しようとするものである。拡張３次元ブロックマッチング法、多段階ＲＬＥ法は、実写３次元映像のデータのうち、頂点の座標データのフレーム間圧縮（フレーム間にある時間的な冗長性の圧縮）のみを対象としており、フレーム内圧縮（１フレーム内にある空間的な冗長性の圧縮）、及び、結線情報や色情報など、他のデータには対処できない。
【０００６】
また、３次元ＣＧ映像圧縮のための技術は古くから研究されているが、ＣＧではほとんどの場合において頂点数、結線関係などは全てのフレームに亘って一定で、頂点の位置のみが変わるだけであるため、データの性質が実写３次元映像と異なる。３次元ＣＧは人間が専用のソフトウェアを用いて作成するため、メッシュのデータ構造なども数学的に扱いやすい構造になっているのに対して、実写３次元映像では多視点映像から自動的に生成するため、ノイズや数学的に扱いにくい結線構造などが多数存在してしまう。そのため、３次元ＣＧ映像圧縮のための技術はそのまま実写３次元映像に適用することはできない。
【０００７】
したがって、実写３次元映像に対して、頂点の座標情報だけでなく、頂点に帰属する様々なデータを効率よく圧縮でき、さらにフレーム内圧縮、フレーム間圧縮両方に対応できる手法が求められる。
【０００８】
３次元映像データの圧縮において、３次元映像の圧縮や処理に必要なデータの「基本単位」をどう定めるかは重要である。２次元画像や２次元映像には、「ピクセル」という概念があり、画像や映像は予め決められた格子状の細かい点列で表現されている。よって、２次元画像や映像はデータが規則正しく並んでおり、それを４×４や８×８のブロックに細かく分割し、それを処理の基本単位としている。それに対して、実写３次元映像では、ピクセルに相当する概念が存在しない。ポリゴン・メッシュを表現する頂点は、３次元空間の任意の場所に存在できるため、格子状に並んでいるわけではない。また、空間を無理矢理格子状に区切ったとしても、全ての格子点上に頂点が存在するわけではない。また、２次元映像には存在しない、結線情報も問題を複雑にしている。そのため、実写３次元映像を効率的に処理できるようにするための「基本単位」をいかに定めるかが重要である。また、映像の圧縮にはフレーム内圧縮とフレーム間圧縮の２つの圧縮が存在する。それぞれの処理で異なる基本単位を用いたのでは、処理、開発コストの面で効率が悪いため、フレーム内・フレーム間圧縮両方で共通に利用できる基本単位が望ましい。
【０００９】
「基本単位」については、３次元CGアニメーションに対して、頂点数と結線の数を略等しくするようにメッシュを分割してそれを基本単位とする手法（非特許文献５）、同じ動きをする頂点群を自動的に抽出して基本単位とする手法（非特許文献６）が提案されている。実写３次元映像に対して、３次元空間を一定間隔で賽の目状に切断し、その中に含まれる頂点を基本単位とする手法（非特許文献３）もある。これらの文献に開示された基本単位は、後述する本発明の基本単位とは構造が異なる。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】ＷＯ２００６／０６２１９９
【非特許文献】
【００１１】
【非特許文献１】K. Tomiyama, Y. Orihara, M.Katayama, and Y. Iwadate, “Algorithm for dynamic 3Dobject generation from multi-viewpoint images,” Proc. SPIE, vol. 5599, pp.153-161, 2004.
【非特許文献２】H. Habe, Y. Katsura, and T.Matsuyama,“Skin-off: representation and compression scheme for 3D video,” PCS, pp.301306, 2004.
【非特許文献３】S.R. Han, T. Yamasaki, and K. Aizawa,“Time-varying mesh compression using extended block matching algorithm,” IEEETCSVT, vol. 17, no. 11, pp. 1506-1518, 2008.
【非特許文献４】S.R. Han, T. Yamasaki, and K.Aizawa, “Geometry compression for time-varying mesh using coarse and finelevels of quantization and run-length encoding,” IEEE ICIP, pp. 10451048, 2008.
【非特許文献５】Z. Karni and C. Gotsman,“Spectral compression of mesh geometry,” ACM SIGGRAPH, pp. 279-286, 2000.
【非特許文献６】S. Gupta, K. Sengupta, and A.Kassim, “Registration and partitioning-based compression of 3-D dynamic data,”IEEE TCSVT, vol. 13, no. 11, pp. 1144-1155, 2003.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明は、３次元動画データ、特に実写３次元映像に対して、頂点の座標情報だけでなく、頂点が持つその他の属性データを効率よく圧縮でき、かつ、フレーム内圧縮、フレーム間圧縮両方に対応できる基本単位及び当該基本単位を用いた圧縮法を提供することを目的とするものである。
【課題を解決するための手段】
【００１３】
本発明が採用した技術手段は、
３次元動画像の圧縮に用いる基本単位であって、
３次元動画像の各フレームの３次元画像はポリゴン・メッシュ・モデルによって表現されており、各頂点は多次元座標系で表現される属性データを持っており、
前記基本単位は、各フレームを表現するポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数に分割してなる小領域であって、
各小領域に含まれる複数の頂点が持つ複数の属性データにＰＣＡ（主成分分析）を適用することで、前記複数の属性データの重心が前記多次元座標系の原点に、かつ前記複数の属性データが２次元平面上に沿って分布するように各属性データが移動されており、前記多次元座標系における各属性データの移動後の値及び移動情報が記憶されている、基本単位、である。
典型的な態様では、前記属性データには位置情報、色情報が含まれる。前記属性データとしては、法線情報や反射特性等の他のデータを含み得る。
基本単位は、属性データの種類毎に独立して用意される。
【００１４】
１つの態様では、前記３次元動画像は、被写体を多視点から撮影した複数の画像を統合してなる実写３次元動画像である。各フレームの３次元画像がポリゴン・メッシュ・モデルによって表現されている実写３次元動画像は、例えば、非特許文献１に開示された方法で生成されるが、本発明において、実写３次元動画像の生成方法は限定されない。
【００１５】
本発明が採用した他の技術手段は、
３次元動画像の圧縮に用いる基本単位の生成方法であって、
３次元動画像の各フレームの３次元画像はポリゴン・メッシュ・モデルによって表現されており、各頂点は多次元座標系で表現される属性データを持っており、
各フレームを表現するポリゴン・メッシュ・モデルを、ほぼ等面積になるように分割して複数の小領域を取得し、
各小領域に含まれる複数の頂点が持つ複数の属性データにＰＣＡ（主成分分析）を適用することで、前記複数の属性データの重心が前記多次元座標系の原点に、かつ前記複数の属性データが２次元平面上に沿って分布するように各属性データを移動させると共に、前記多次元座標系における各属性データの移動後の値及び移動情報を記憶してなる、基本単位の生成方法、である。
【００１６】
１つの態様では、ポリゴン・メッシュ・モデルの複数の小領域への分割は、測地線距離に基づいて行う。
【００１７】
本発明は、さらに、上記基本単位の生成方法をコンピュータに実行させるためのコンピュータプログラム、あるいは、当該コンピュータプログラムが記録された記録媒体としても定義される。
本発明に係る基本単位はデータ構造であり、基本単位の生成は１つあるいは複数のコンピュータによって実行される。本発明に係る圧縮方法も１つあるいは複数のコンピュータによって実行される。１つの態様では、コンピュータは、各種計算を行う演算処理部、３Dメッシュデータや計算結果等の各種データを格納する記憶部、３次元動画像を表示する表示部、コンピュータを操作するための入力部、計算結果等のデータを出力する出力部、を備えている。
【００１８】
本発明が採用した他の技術手段は、上記基本単位を用いてフレーム間圧縮を行う３次元動画像の圧縮方法であって、
ターゲットフレームにおけるポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数の小領域に分割すると共に、PCA（主成分分析）を適用して基本単位を生成し、
参照フレームにおけるポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数の小領域に分割すると共に、PCA（主成分分析）を適用して基本単位を生成し、
ターゲットフレームにおけるある基本単位と、参照フレームにおける各基本単位との距離を各頂点が持つ属性データに基づいて計算し、最も距離が近い基本単位を参照基本単位として選択するステップと、
ターゲットフレームにおける各基本単位と当該基本単位に対応する参照フレームにおける参照基本単位との差分情報を取得するステップと、
前記差分情報を圧縮するステップと、を備えている圧縮方法、である。
１つの態様では、前記参照フレームのポリゴン・メッシュ・モデルは、上記基本単位の属性データに対して圧縮処理を適用することでフレーム内圧縮が行われたポリゴン・メッシュ・データを復号してなるデータであり、当該参照フレームポリゴン・メッシュ・モデルの基本単位は、フレーム内圧縮時に生成されている。
参照フレームのフレーム内圧縮を基本単位を用いない手法で行った場合には、フレーム間圧縮の時に参照フレームにおけるポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数の小領域に分割すると共に、PCA（主成分分析）を適用して基本単位を生成すればよい。
【００１９】
本発明が採用した他の技術手段は、上記基本単位の属性データに対して圧縮処理を適用することでフレーム内圧縮を行う３次元動画像の圧縮方法、である。
【００２０】
差分情報の圧縮、フレーム内圧縮において、頂点の属性データ（位置情報、色情報等）の圧縮には、既存の圧縮手法（不可逆圧縮、可逆圧縮を問わない）を広く適用できることが当業者に理解される。
具体的に例示すると、スカラー量子化、VQ(ベクトル量子化)、BTC（Block Truncation Coding）、ラプラシアン行列によるメッシュの周波数解析（Spectral compression）、DCT(離散コサイン変換、Discrete Cosine Transform)、ウェーブレット変換、エントロピー符号化（ハフマン符号、算術符号、CABAC(Context-based Adaptive Binary Arithmetic Coding)など）から選択された１つ以上の圧縮方式を用いて圧縮を行うことができる。
【発明の効果】
【００２１】
本発明に係る３次元動画像圧縮のための基本単位は、フレーム間圧縮、フレーム内圧縮で用いられる従来の圧縮手法を適用できるデータ構造になっており、しかも、頂点の座標情報、および色情報等の頂点の属性データの分布は非常に局所的になり、圧縮前のデータのばらつきが小さいため、効率良くデータを圧縮することができる。また、本発明の基本単位は、頂点の位置情報のみならず、頂点が持つ他の属性データの圧縮を行うことができる。
【００２２】
基本単位において、基本単位のサイズがほぼ一定であり、かつ、頂点が持つ属性データの値の重心がほぼ一致し、属性データ（頂点の位置情報、色情報等）の広がりもほぼ一致しているので、小領域同士のマッチングを容易に行うことができる。
【００２３】
本発明の効果は上記記載に限定されるものではなく、その他の効果は、本明細書の記載から明らかになる。
【図面の簡単な説明】
【００２４】
【図１】本発明に係る圧縮方法の概要を示す全体ブロック図である。
【図２】３次元映像の一般的な表現方法を示す図である。
【図３】ポリゴン・メッシュ・モデルを、ほぼ等面積になるように分割した状態を示す概念図、及び、分割した小領域の頂点の座標値にPCA（主成分分析）を適用した基本単位の生成を示す概念図である。
【図４】VQ(ベクトル量子化)を用いたフレーム内圧縮の処理の流れを示す概念図である。
【図５】PCA（主成分分析）適用後のあるフレームにおける各小領域内の頂点の座標情報の分布を示す図である。
【図６】PCA（主成分分析）適用後のあるフレームにおける各小領域内の頂点の色情報の分布を示す図である。
【図７】フレーム間圧縮における参照フレーム内の小領域（基本単位）とターゲットフレーム内の小領域（基本単位）とのマッチングを示す概念図である。
【図８】ターゲット小領域（基本単位）と参照小領域（基本単位）との距離計算及び差分情報の記録方法を示す概念図である。
【図８Ａ】従来の差分情報の記録を説明する図である。
【図８Ｂ】本実施形態に係る差分情報の記録を説明する図である。
【図９】ターゲットフレームと参照フレーム間の頂点の位置情報の差分情報の分布を示す図である。
【図１０】ターゲットフレームと参照フレーム間の頂点の色情報の差分情報の分布を示す図である。
【図１１】Kimono-Ladyシーケンスに対するフレーム内圧縮の性能を示す図であり、左図は頂点の位置情報の圧縮、右図は頂点の色情報の圧縮を示す。
【図１２】Kimono-Ladyシーケンスに対するフレーム間圧縮の性能を示す図であり、左図は頂点の位置情報の圧縮、右図は頂点の色情報の圧縮を示す。
【発明を実施するための形態】
【００２５】
［Ａ］３次元動画像圧縮の概要
図１に本実施形態に係る３次元動画像圧縮のアルゴリズムを示す。先ず、オリジナルの３ＤメッシュモデルＭｉを複数の小領域（図１では、patchと表現されている）に分割する。小領域への分割は、各小領域の面積が略同じ面積となるように行う。次いで、各小領域の頂点が持つ属性データ（頂点の位置情報、頂点が有する色情報等）に対してPCA（主成分分析）を適用して圧縮のための基本単位を生成する。属性データが位置情報であれば、各小領域の頂点の座標値の重心が世界座標系（x,y,z）の原点となるように、各座標値を変換することで、各小領域の向き・姿勢を調整する。属性データが色情報の場合、R,G,B座標系の原点に重心が来るように色値を変換する。
【００２６】
フレーム内圧縮では、各頂点に帰属する冗長な空間情報を利用する。頂点の位置情報は空間的にコヒーレントな情報であるため、本実施形態ではラプラシアン行列によるメッシュの周波数解析であるSpectral compression（非特許文献５、または、R. Ohbuchi, A. Mukaiyama, and S. Takahashi, “A Frequency-domain
approach to watermarking 3D shapes,” Computer Graphics Forum, vol. 21, pp.
373-382, 2002.）と量子化を組み合わせることで頂点の座標の圧縮を行う。一方、頂点が持つ色情報は空間的にコヒーレントではないため、本実施形態ではＶＱあるいはスカラー量子化が色情報の圧縮に用いられる。圧縮によって得られたデータはエントロピー符号化される。
【００２７】
フレーム間圧縮においては、フレーム内圧縮からデコードされた参照フレーム（Ｍ＾ｒｅｆ）の３Ｄメッシュモデルから生成された基本単位と、ターゲットフレーム（Ｍｊ）の３Ｄメッシュモデルから生成された基本単位と、を用いる。本実施形態では、参照フレームの基本単位については、フレーム内圧縮を行う時に生成されて、記憶されている。したがって、フレーム間圧縮にあたっては、ターゲットフレームの３Ｄメッシュモデルのみを小領域に分割して、基本単位を生成すればよい。そして、ターゲットフレームにおける小領域（基本単位）と参照フレームにおける小領域（基本単位）との間で小領域同士のマッチングを実行し、参照フレームから最も近い小領域（基本単位）を探索する。差分情報、すなわち、頂点の座標情報においては（△x, △y, △z）、頂点が持つ色情報においては（△R, △G, △B）をスカラー量子化あるいはＶＱ等の圧縮手段を用いて圧縮する。圧縮によって得られたデータはエントロピー符号化される。
【００２８】
連結情報の圧縮においては、静的３Ｄメッシュモデルに用いられている高性能アルゴリズムを適用することができる。また、各小領域における頂点数は比較的少ないので、各小領域の頂点ＩＤの番号を振り直すことによっても連結情報のビットレートを低減することができる。
【００２９】
［Ｂ］圧縮対象となる３次元動画像データ
３次元動画像データは、２Ｄビデオと同様に、連続するフレームのシーケンスから構成されており、各フレームは、ポリゴン・メッシュ・モデルによって表されている。すなわち、各フレームは、頂点座標、頂点の連結（トポロジー）、色情報の３つの情報によって表現されている。ここで、多くの場合、Marching cubes アルゴリズム（W.E. Lorensen and H.E.
Cline, “Marching cubes: A high resolution 3D surface construction algorithm,”
ACM SIGGRAPH, pp. 163-169, 1987.）等によって３Ｄボクセルモデルを３Ｄメッシュ（表面）モデルに変換するため、メッシュは規則的とは限らない。
【００３０】
データの概要を表１に示す。３次元動画像データは、非特許文献１に関連するデータである。３次元動画像データは、２２個の同期カメラを用いた多視点映像から生成されたものである。
【表１】
また、３次元映像の一般的な表現方法（データ構造）を図２に示す。各フレームにおいて、各頂点にはIDが順に割り当てられ、各頂点の属性データ（座標値、色値）がコンピュータの記憶部に記憶されている。また、どのIDにより三角パッチが形成されているかの情報も記憶部に記憶されている。この基本的な表現方法は、小領域（基本単位）においても同様である。
【００３１】
［Ｃ］基本単位の生成
データ圧縮のための基本単位の生成について説明する。
［Ｃ−１］小領域の形成
先ず、圧縮対象となる実写３次元映像フレームが与えられたとき、オリジナルの３Ｄメッシュモデルの表面形状を各小領域の面積が略等面積になるような条件下で、複数の小領域に分割する。本実施形態では、小領域の半径をr=sqrt(0.001xArea(M))と設定した。ここで、Area(M)は３Ｄメッシュモデルの総面積である。この条件において、本実施形態では各小領域には１００〜２００の頂点が含まれることになる。
【００３２】
３Dメッシュモデルを略等面積の小領域に分割するためには、測地線距離が計算できればよく、例えば、Dijkstraアルゴリズムを用いてメッシュモデルを小領域に分割することができる。Dijkstra法自体は当業者によく知られた手法でありるので、詳細な説明は省略する。また、dijkstra法を用いて測地線距離を近似することは、M. Hilaga, Y. Shinagawa, T. Kohmura, T.L. Kunii: Topology matching
for fully automatic similarity estimation of 3D shapes. Proceedings SIGGRAPH,
203-212(2001).に開示されており、当該文献に開示された手法を用いて３Dメッシュモデルを略等面積の小領域に分割してもよい。なお、この文献は、３Dメッシュモデルを略等面積の小領域に分割する点において、本発明と共通する部分があるが、３次元メッシュモデルから骨格構造を抽出するための中間処理として用いているだけで、実写３次元映像圧縮のための基本単位として用いるものではない。また、本手法は、メッシュを一定面積の小領域に分割した後、PCA(主成分分析）を用いて小領域に含まれる頂点が持つ属性データを変換しており（属性データが位置情報の場合には、小領域の姿勢・方向補正を行うことになる）、この変換の結果までを含めて基本単位としている。小領域の頂点が持つ属性データを、属性データの重心及び属性データ（頂点の位置情報、色情報等）の広がりがほぼ一致するように変換することは、小領域同士を対応させて距離を計算したり差分を計算したりする上で、有利である。
【００３３】
本発明のアプローチは、メッシュを略同じ面積の小領域に分割することによって小領域間での空間的対応付けを容易に行うものである。メッシュを略等面積の小領域に分割することで、結果として、比較的同じような頂点の数、結線数が各小領域に含まれることになり、小領域同士のマッチングが容易となる。小領域の寸法は、圧縮効率を考慮することで決定されるが、典型的には、小領域は概ねフラットディスク様の形状である程度に小さいものである。
【００３４】
各小領域はポリゴン・メッシュの三角パッチの群であり、三角パッチ群の面積がほぼ同じあると考えることができる。また、三角パッチ群の周縁に位置する三角パッチは三角パッチの部分（分割する時に三角パッチが切断される）であってもよく、三角パッチ群を形成する三角パッチには完全でない三角パッチも含まれ得る。すなわち、小領域の縁の部分に存在する三角形は、不完全なものとなっており、圧縮されたデータを完全に元に戻すためには、「どこを切った」という情報を記憶しておく。切断される結線情報は、全体の結線の中の一部なので、それを記憶しておくためのデータ量はそれほど大きくない。
【００３５】
［Ｃ−２］PCA(主成分分析)の適用
各フレームを表現するポリゴン・メッシュ・モデルを、ほぼ等面積になるように分割して得られた小領域の各頂点が持つ各属性データ（位置情報や色情報）に対してPCA（主成分分析）を適用することで、各属性データ毎に独立した基本単位を生成する。
【００３６】
小領域に含まれる頂点が持つ位置情報については、各小領域に対してPCA（主成分分析）を行うことで、各小領域に含まれる多数の頂点の座標値の平均値である重心にｘｙｚ座標の原点が移動すると共に、各頂点の座標が回転する。頂点の位置情報は重心が原点に位置すると共に、例えばｘｙ平面近傍に沿って分布することになる。すなわち、各小領域の重心が世界座標系の原点となり、分布方向が概ね２次元平面（例えば、ｘｙ平面）となるように各小領域の向き・姿勢が補正され、様々な方向を向いている小領域の方向を合わされる。図３に示すように、フラット状の小領域（基本単位）はｘｙ平面に沿って配向されることになり、ｚ軸寸法は小さい。
【００３７】
小領域に含まれる頂点が持つ色情報については、各小領域に対してPCA（主成分分析）を行うことで、各小領域に含まれる多数の頂点の色値（R,G,B）の平均値である重心にRGB座標の原点が移動すると共に、各頂点の座標が回転する。色情報についての「基本単位」は、頂点の位置情報の基本単位と独立して用意される。
【００３８】
３次元メッシュモデルを小領域に分割すると共に、小領域内の頂点が持つ属性データにPCA（主成分分析）を施すことで基本単位を生成することによって、頂点の座標情報、および色情報の分布は非常に局所的になり、圧縮に適したデータ構造となる。図５、図６に示すように、頂点が持つ属性データ（位置情報、色情報）はそれぞれ２次元平面に沿って分布している。基本単位の向きを２次元平面（典型的にはxy平面であるが、yz, zx平面でもよい）に沿うように局所的に分布させることで、効率よくデータを圧縮することができる。例えば、０〜７の間に分布する整数だと3ビットで表現できるのに対して、０〜２５６の間に分布する整数だと8ビット必要となる。向きを考慮せずに適当な方向で小領域を配置すると、x, y, zそれぞれに大きな幅をもって分布するのに対して、xy平面上に沿って分布するように方向補正をするとz方向の分布は殆どないことが予めわかるので、必要なデータ量を小さくすることができる。
【００３９】
また、基本単位において、頂点が持つ属性データの値の重心がほぼ一致し、属性データ（頂点の位置情報、色情報等）の広がりもほぼ一致していることは、少領域同士を対応させて比較する場合に有利である。小領域のサイズや頂点が持つ属性データの分布は小領域間で互いに略同じなので、小領域同士のマッチングを容易に行うことができる。
【００４０】
また、元々の位置・姿勢から上記補正をするために行った平行移動、回転移動のパラメータを記憶部に記憶しておく。１つの態様では、３次元メッシュモデルを分割してなる各小領域にIDが付されており、かつ、小領域毎に、当該小領域に含まれる頂点にIDが付されており、頂点の各IDに対応して元の属性データ（位置情報や色情報）の値、移動後の属性データ（位置情報や色情報）の値、及び、平行移動、回転移動のパラメータが記憶されている。
【００４１】
その後、それぞれの基本単位の頂点が持つ属性データに対して、フレーム内圧縮、フレーム間圧縮の処理を行う。頂点の座標情報、および色情報の具体的な圧縮には様々な従来の圧縮手法が利用可能である。例えば、ベクトル量子化（ＶＱ）、Spectral Compression, Block Truncation Coding (BTC)などで優れた圧縮性能が得られることが実験の結果わかっている。
【００４２】
［Ｄ］フレーム内圧縮
図５、図６に示すように、３次元メッシュモデルを小領域に分割すると共に、小領域内の頂点が持つ属性データにPCA（主成分分析）を適用して基本単位を生成することによって、頂点の座標情報、および色情報の分布は非常に局所的になり、圧縮に適したデータ構造となる。
【００４３】
フレーム内圧縮については、各小領域内にある頂点の位置情報の空間的相関が高いことを利用して、頂点の位置情報を効率よく圧縮できる。頂点座標は空間的に互いに相関しているので、１つの態様では、Spectral compression（非特許文献５）を用いて圧縮を行うことができる。本実施形態では、Kirchhoff行列を用いる（非特許文献５、R. Ohbuchi, A. Mukaiyama, and S. Takahashi, “A Frequency-domain
approach to watermarking 3D shapes,” Computer Graphics Forum, vol. 21,
pp. 373-382, 2002.）。Kirchhoff行列は以下のように定義される。
ここで、Ａはｎ頂点メッシュトポロジー
によって定義される隣接行列であり、
ＤはＤii=diとなるような対角行列、diは頂点iの次元である。
【００４４】
行列Ｋの固有ベクトルは基底関数の集合を形成する直交ベクトルである。関連する固有値は周波数に対応しており、ある小領域の頂点の座標ベクトル（ｘ、ｙ、ｚ）の投影は入力ベクトルのスペクトルとみなすことができる。そして、１０〜５０％のより低い周波数のスペクトル値のみを用いる。残りの高周波成分は単純化のため０とする。量子化されたスペクトル値はハフマンエンコーダを用いてエントロピー符号化される。
【００４５】
各頂点に帰属する色情報を圧縮するためには、ＶＱ（ベクトル量子化）あるいはスカラー量子化を用いることができる。ＶＱは頂点の色情報を構成する３次元ベクトル（Ｒ，Ｇ，Ｂ）に適用される。コードブック及びベクトルのインデックスはさらにハフマンエンコーダによって圧縮される。スカラー量子化を用いる場合には、最小値及び最大値が抽出され、座標ベクトルがスカラー量子化される。
【００４６】
表２に、頂点の座標情報、および色情報の圧縮のために必要な情報と、それぞれに必要なデータ量を簡単に記載したものを示す。各フレーム間で基本単位（小領域）の寸法はほぼ同じなので、コードブック設計は最初のフレームについて行えばよく、コードブックの一部を省略することが可能である。
【表２】
【００４７】
本実施形態では、圧縮に用いられる基本単位が、フレーム間圧縮およびフレーム内圧縮の両方に適用できる。これは例えば電子機器での実装やハードウェア化など、特定の制約の下でシステムを設計したいときには有利である。なお、フレーム内圧縮及びフレーム間圧縮を行う場合に、フレーム内圧縮に既存の圧縮手法を用い、フレーム間圧縮に本発明の基本単位を用いてもよい。
【００４８】
［Ｅ］フレーム間圧縮
フレーム間圧縮については、処理対象となるターゲット小領域（基本単位）と、参照フレームから生成される小領域（基本単位）群とのマッチングを行い、もっとも似ている参照小領域（基本単位）を探索する。その後、どの小領域に最も近かったかという情報、小領域間の頂点の対応関係を記憶すると共に、ターゲット小領域と参照小領域との対応する頂点の属性データ間の差分を取ることにより、頂点の座標情報、および色情報の分布範囲を小さくすることができる。それによって、ベクトル量子化やその他様々な圧縮処理を適用することによって頂点情報、及び色情報を効率よく圧縮できる。
【００４９】
効率的な圧縮をするためには、データのばらつきの範囲が小さいことが重要である。今回の場合、差分の値はできるだけ値が小さく、また、ばらつきの範囲（ダイナミックレンジ）も小さいほど圧縮の効率はよくなる。基本単位を用いないと、そもそも小領域の位置や方向がそろってないので、結果として得られる差分値は値が大きく、またばらつきも大きいためにほとんど圧縮ができない。そのため、基本単位を定義して位置合わせがほぼなされていると仮定した上で似ている小領域（基本単位）を探し、差分情報を取得することが有利である。
【００５０】
フレーム間における時間的相関を除去するために、小領域同士のマッチングが用いられる。ターゲットフレームにおけるある小領域と、参照フレームにおける全ての小領域との類似度は、以下の式によって評価される。
ここで、d(Pref,m, Pj,n)は参照フレームにおけるｍ番目の基本単位Pref,mとｊ番目フレームにおけるｎ番目の基本単位(Pj,n)との非類似度である。Euclideanは、ユークリッド距離である。vs、vtはPref,mのｓ番目の頂点の座標値あるいは色値、Pj,nのｔ番目の頂点の座標値あるいは色値である。参照フレームにおける最小のd(Pref,m, Pj,n)を生成する最も近い小領域が参照小領域として用いられる。
【００５１】
より具体的に説明すると、ターゲットフレームにおけるある小領域（基本単位）内の、ある１つの頂点座標に注目する。参照フレームにおけるある小領域（基本単位）の全ての頂点の属性値（座標や色）とユークリッド距離を計算し、距離が最小となる頂点を探す。頂点が保有する情報として位置情報と色情報があるが、小領域間の類似度を計算する場合には、位置情報の類似度、色情報の類似度は属性の種類ごとに独立して別個に計算される。距離が最小となる頂点を「対応のとれた」頂点とする。この処理を、ターゲットフレームにおけるある小領域（基本単位）内の全ての頂点に対して行う。距離の総和がターゲットフレームにおけるある小領域（基本単位）と参照フレームにおけるある小領域（基本単位）の「小領域同士の距離」となる。ターゲットフレームにおけるいま注目している小領域（基本単位）に対する参照小領域（基本単位）は、この「小領域同士の距離」が最小となる参照領域のことを指す。なお、ターゲットフレームにおけるある小領域の頂点と参照フレームにおけるある小領域の頂点同士の一対一対応をとっているわけではなく、「どれが一番近いか」というのを計算しているだけなので、それぞれの領域に含まれる頂点の個数は関係ない。
【００５２】
圧縮のための他の重要な情報は、ターゲットフレームにおける小領域（基本単位）内の頂点と参照フレームにおける小領域（基本単位）内の頂点との対応データである。すなわち、差分情報を計算するには、圧縮対象であるターゲット小領域のある頂点が、参照小領域のどの頂点と差分を計算したか、ということを記憶しておく必要がある。非特許文献３では、参照フレームのどの頂点と差分を計算したかを記憶するために、ブロックの中に含まれる頂点に順に0, 1, 2・・・とID番号を振って、何番目の頂点と差分を計算したか、ということを記憶している（図８A参照）。ブロックには平均的に数十個程度の頂点が含まれていたために、IDを表現するために頂点当たり6ビット程度(ID: 0-63)のデータが必要となる。さらに、それぞれのIDの使用頻度はほぼ同じなので、エントロピー符号化などさらなる圧縮はあまり有効でない。これに対して、本実施形態では、圧縮対象であるターゲット小領域に含まれる頂点が、まず参照小領域のどのIDの頂点に対応するか判別し、対応するIDの小さい順に並べ直す（ソートする）。ここで、「並べ直す」というのは、頂点の3次元空間上の位置は変化しないので、データを保存するときの順番を並び替える、という意味である。そうすると、記憶すべき情報は、ターゲット小領域内のそれぞれの頂点が参照小領域内のどのIDの頂点との差分を計算したか、ではなく、参照小領域のIDがxx番の頂点と差分を計算したターゲット小領域内の頂点はいくつあったか、ということになる（図８B参照）。すなわち、頂点の個数を記憶するだけなので、０〜５くらいの数字が頻繁に現れることになる。したがって、6bitは必要なく、例えば3bitあれば０〜５の数字は表現できるため、6bitは必要なく、それだけデータ量は少なくて済み、また、使用頻度を表現する数字は全て同じ頻度で現れるのではなく、典型的には０〜２が頻繁に現れる。そのため、エントロピー符号器を用いて効率的に符号化できる。
【００５３】
表３に、圧縮に必要な情報とそのデータ量を示す。
【表３】
【００５４】
ターゲット小領域における属性データと、参照小領域におけるそれらに対応する属性データとの差である差分データセットはさらに圧縮される。差分データの圧縮には、スカラー量子化手法やVQ（ベクトル量子化）を用いることができる。VQを用いる場合には、コードブック設計は最初のフレームと２番目のフレームとの間で一度だけ行えばよい。小領域の寸法が変わらない限り、残りのフレームに対して同じコードブックを用いることができる。差分データは図１０、図１１に示すように、図５、図６に示した元々のデータの分布に比べてさらに局所的になる。そのため、フレーム間圧縮はフレーム内圧縮よりもさらに効率的になる。
【００５５】
基本単位（小領域）を用いたマッチングの利点の一つは、フレーム内圧縮をシーケンスの最初のフレームにおいて行えば、他のフレームは最初のフレームを参照としてフレーム間圧縮できるということである。基本単位はPCA（主成分分析）によって空間的対応付けを取るように配向されている。なお、圧縮対象となっているターゲット小領域と最も「似通っている」小領域を、参照小領域群（前後フレームから生成）から効率的に探索するためには、例えばIterative closest point (ICP)と呼ばれるような、3次元の形状合わせのための手法なども使うことも可能である（P.J. Besl and N.D. McKay, “A method for registration of 3-D shapes,”
IEEE TPAMI, vol. 14, no. 2, pp. 239-256, 1992.）。しかしながら、ICPなどの形状あわせのための手法では、小領域同士がどれだけ似ているか、という計算をするたびに位置合わせを行う必要があり（小領域によって方向や位置が異なるため）、ICPは極めて計算コストが高い処理である。これに対して、予めPCAをかけておく本手法は、1度計算してしまうと位置や方向は全ての小領域で揃っているため、位置合わせのための計算は必要なく、位置合わせがほぼなされていると仮定した上で似ている小領域を探すだけの作業でよいため効率がよい。
【００５６】
何フレームに1回フレーム内圧縮を行うかについては、当業者において経験的に決定される。フレーム間圧縮は、フレーム内圧縮されたフレーム（画像）を参照データとして、圧縮対象のフレームとの差分だけを計算し、それを符号化することで高い圧縮率を実現する。ここで重要なのは、「圧縮対象のフレームは参照フレームとあまり変わっていない」という点である。変化が激しければ、それだけ差分情報が大きくなり、圧縮がしにくいデータとなってしまうため、参照フレームと圧縮対象のフレームの間はあまり時間的な差がない、すなわち参照フレームはできるだけ頻繁にある方がフレーム間圧縮の効率は上がる。一方、フレーム内圧縮はそれ自体あまり圧縮効率がよくないので、あまり頻繁にフレーム内圧縮を行うとフレーム内圧縮、フレーム間圧縮全体として見たときの圧縮効率は落ちてしまう。本実施形態との関連で言うと、3次元映像の圧縮、特に幾何情報（頂点情報）の圧縮では、頂点情報の空間的な広がりについて、参照フレームとの差分を計算する。小領域内の頂点の空間的な広がりはそれほど激しく変化することはない。また、色情報も同一物体を対象としている限り、物体が動きはするものの、色はそれほど変わらない。したがって、２次元動画像に比べて参照フレームの頻度が比較的少なくて良いと考えられる。
【００５７】
［Ｆ］実験結果
幾つかの異なる圧縮手法を用いてKimono-Ladyシーケンスに対して、フレーム内圧縮、フレーム間圧縮を実行して性能を比較した。以下の評価尺度を用いて圧縮性能を評価した。
ここで、Nは３Dメッシュモデルの頂点の数、Vi、Vi´は、それぞれ、i番目の元頂点座標、復号化された頂点座標である。
【００５８】
図１１は、Kimono-Ladyシーケンスに対するフレーム内圧縮の性能を示す図であり、左図は頂点の位置情報の圧縮、右図は頂点の色情報の圧縮を示す。頂点の位置情報の圧縮においては、Spectral compressionが効率的であることがわかる。色情報の圧縮においては、VQ（ベクトル量子化）やスカラー量子化が効率的であることがわかる。
【００５９】
図１２は、Kimono-Ladyシーケンスに対するフレーム間圧縮の性能を示す図であり、左図は頂点の位置情報の圧縮、右図は頂点の色情報の圧縮を示す。左図において、[3]、[4]はそれぞれ非特許文献３、非特許文献４に開示された手法による圧縮結果である。差分情報の圧縮にはVQ（ベクトル量子化）やスカラー量子化が効率的であることがわかる。
【００６０】
［Ｇ］連結情報の圧縮
最後に連結情報の圧縮について言及する。連結情報の圧縮については従来の手法を用いることができる。通常のCGデータの連結情報の圧縮手法として、以下のようなものが知られており、これらの手法を実写３次元画像用に修正して用い得ることが当業者に理解される。
DEERING, M. 1995. Geometry compression. In ACM SIGGRAPH 1995, 13−20.
ROSSIGNAC, J. 1999. Edgebreaker:
connectivity compression for triangle meshes. IEEE Trans. Visualization and
Computer Graphics 5, 1, 47−61.
TAUBIN, G., AND ROSSIGNAC, J. 1998. Geometric compression through topological surgery. ACM Transaction
on Graphics 17, 2 (April), 84−115.
また、それ以外にも下記の文献に網羅的に静止三次元モデルの圧縮手法についてはまとめられており、このうち、結線情報を圧縮する手法を用いることができる。
PENG, J., KIM, C.-S., AND KUO, C.-C. J. 2005. Technologies for 3d mesh compression: A survey. Journal of
Visual Communication and Image Representation 16, 688−733.
上記文献に開示された圧縮手法をフレーム内圧縮に適用してもよい。
【００６１】
また、Intra-ID compressionにより連結情報を圧縮してもよい。各小領域は数十〜200程度の頂点から成り立っており、それぞれの頂点に0からIDを付け、それぞれの三角形ポリゴンがどのIDの頂点同士を結んで成り立っているのかを表現する。元々の3次元モデル全体だと10万個程度の頂点があり、１つの頂点を表すIDは16〜17ビット必要となる、すなわち、3角形の３つの頂点を表現するのに約50ビット必要となる。これに対して、200程度の頂点であればIDを表現するために8ビットあれば十分なので3角形１つあたり24ビットで済む。
【特許請求の範囲】
【請求項１】
３次元動画像の圧縮に用いる基本単位であって、
３次元動画像の各フレームの３次元画像はポリゴン・メッシュ・モデルによって表現されており、各頂点は多次元座標系で表現される属性データを持っており、
前記基本単位は、各フレームを表現するポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数に分割してなる小領域であって、
各小領域に含まれる複数の頂点が持つ複数の属性データにＰＣＡ（主成分分析）を適用することで、前記複数の属性データの重心が前記多次元座標系の原点に、かつ前記複数の属性データが２次元平面上に沿って分布するように各属性データが移動されており、前記多次元座標系における各属性データの移動後の値及び移動情報が記憶されている、基本単位。
【請求項２】
前記属性データには位置情報が含まれる、請求項１に記載の基本単位。
【請求項３】
前記属性データには色情報が含まれる、請求項１、２いずれかに記載の基本単位。
【請求項４】
前記３次元動画像は、被写体を多視点から撮影した複数の画像を統合してなる実写３次元動画像である、請求項１〜３いずれかに記載の基本単位。
【請求項５】
３次元動画像の圧縮に用いる基本単位の生成方法であって、
３次元動画像の各フレームの３次元画像はポリゴン・メッシュ・モデルによって表現されており、各頂点は多次元座標系で表現される属性データを持っており、
各フレームを表現するポリゴン・メッシュ・モデルを、ほぼ等面積になるように分割して複数の小領域を取得し、
各小領域に含まれる複数の頂点が持つ複数の属性データにＰＣＡ（主成分分析）を適用することで、前記複数の属性データの重心が前記多次元座標系の原点に、かつ前記複数の属性データが２次元平面上に沿って分布するように各属性データを移動させると共に、前記多次元座標系における各属性データの移動後の値及び移動情報を記憶してなる、基本単位の生成方法。
【請求項６】
前記属性データには位置情報が含まれる、請求項５に記載の基本単位の生成方法。
【請求項７】
前記属性データには色情報が含まれる、請求項５、６いずれかに記載の基本単位の生成方法。
【請求項８】
ポリゴン・メッシュ・モデルの複数の小領域への分割は、測地線距離に基づいて行う、請求項５〜７いずれかに記載の基本単位の生成方法。
【請求項９】
前記３次元動画像は、被写体を多視点から撮影した複数の画像を統合してなる実写３次元動画像である、請求項５〜８いずれかに記載の基本単位の生成方法。
【請求項１０】
請求項５〜８いずれかに記載の基本単位の生成方法をコンピュータに実行させるためのコンピュータプログラム。
【請求項１１】
請求項５〜８いずれかに記載の基本単位の生成方法をコンピュータに実行させるためのコンピュータプログラムが記録された記録媒体。
【請求項１２】
請求項１〜４いずれかに記載の基本単位を用いてフレーム間圧縮を行う３次元動画像の圧縮方法であって、
ターゲットフレームにおけるポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数の小領域に分割すると共に、PCA（主成分分析）を適用して基本単位を生成し、
参照フレームにおけるポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数の小領域に分割すると共に、PCA（主成分分析）を適用して基本単位を生成し、
ターゲットフレームにおけるある基本単位と、参照フレームにおける各基本単位との距離を各頂点が持つ属性データに基づいて計算し、最も距離が近い基本単位を参照基本単位として選択するステップと、
ターゲットフレームにおける各基本単位と当該基本単位に対応する参照フレームにおける参照基本単位との差分情報を取得するステップと、
前記差分情報を圧縮するステップと、を備えている圧縮方法。
【請求項１３】
前記参照フレームのポリゴン・メッシュ・モデルは、請求項１〜４いずれかに記載の基本単位の属性データに対して圧縮処理を適用することでフレーム内圧縮が行われたポリゴン・メッシュ・データを復号してなるデータであり、当該参照フレームポリゴン・メッシュ・モデルの基本単位は、フレーム内圧縮時に生成されている、請求項１２に記載の圧縮方法。
【請求項１４】
ターゲットフレームの基本単位を形成する頂点、参照フレームの基本単位を形成する頂点にはそれぞれIDが順番に付与されており、
ターゲットフレームの基本単位の各頂点IDの差分情報と参照基本単位の頂点IDとの対応関係を、参照基本単位の頂点ID順に並び替えることで当該参照基本単位の頂点IDの対応するターゲットフレームの基本単位の頂点数を取得し、
各差分情報を、前記頂点数に関連付けて記憶する、請求項１２、１３いずれかに記載の圧縮方法。
【請求項１５】
請求項１〜４いずれかに記載の基本単位の属性データに対して圧縮処理を適用することでフレーム内圧縮を行う３次元動画像の圧縮方法。
【請求項１】
３次元動画像の圧縮に用いる基本単位であって、
３次元動画像の各フレームの３次元画像はポリゴン・メッシュ・モデルによって表現されており、各頂点は多次元座標系で表現される属性データを持っており、
前記基本単位は、各フレームを表現するポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数に分割してなる小領域であって、
各小領域に含まれる複数の頂点が持つ複数の属性データにＰＣＡ（主成分分析）を適用することで、前記複数の属性データの重心が前記多次元座標系の原点に、かつ前記複数の属性データが２次元平面上に沿って分布するように各属性データが移動されており、前記多次元座標系における各属性データの移動後の値及び移動情報が記憶されている、基本単位。
【請求項２】
前記属性データには位置情報が含まれる、請求項１に記載の基本単位。
【請求項３】
前記属性データには色情報が含まれる、請求項１、２いずれかに記載の基本単位。
【請求項４】
前記３次元動画像は、被写体を多視点から撮影した複数の画像を統合してなる実写３次元動画像である、請求項１〜３いずれかに記載の基本単位。
【請求項５】
３次元動画像の圧縮に用いる基本単位の生成方法であって、
３次元動画像の各フレームの３次元画像はポリゴン・メッシュ・モデルによって表現されており、各頂点は多次元座標系で表現される属性データを持っており、
各フレームを表現するポリゴン・メッシュ・モデルを、ほぼ等面積になるように分割して複数の小領域を取得し、
各小領域に含まれる複数の頂点が持つ複数の属性データにＰＣＡ（主成分分析）を適用することで、前記複数の属性データの重心が前記多次元座標系の原点に、かつ前記複数の属性データが２次元平面上に沿って分布するように各属性データを移動させると共に、前記多次元座標系における各属性データの移動後の値及び移動情報を記憶してなる、基本単位の生成方法。
【請求項６】
前記属性データには位置情報が含まれる、請求項５に記載の基本単位の生成方法。
【請求項７】
前記属性データには色情報が含まれる、請求項５、６いずれかに記載の基本単位の生成方法。
【請求項８】
ポリゴン・メッシュ・モデルの複数の小領域への分割は、測地線距離に基づいて行う、請求項５〜７いずれかに記載の基本単位の生成方法。
【請求項９】
前記３次元動画像は、被写体を多視点から撮影した複数の画像を統合してなる実写３次元動画像である、請求項５〜８いずれかに記載の基本単位の生成方法。
【請求項１０】
請求項５〜８いずれかに記載の基本単位の生成方法をコンピュータに実行させるためのコンピュータプログラム。
【請求項１１】
請求項５〜８いずれかに記載の基本単位の生成方法をコンピュータに実行させるためのコンピュータプログラムが記録された記録媒体。
【請求項１２】
請求項１〜４いずれかに記載の基本単位を用いてフレーム間圧縮を行う３次元動画像の圧縮方法であって、
ターゲットフレームにおけるポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数の小領域に分割すると共に、PCA（主成分分析）を適用して基本単位を生成し、
参照フレームにおけるポリゴン・メッシュ・モデルを、ほぼ等面積になるように複数の小領域に分割すると共に、PCA（主成分分析）を適用して基本単位を生成し、
ターゲットフレームにおけるある基本単位と、参照フレームにおける各基本単位との距離を各頂点が持つ属性データに基づいて計算し、最も距離が近い基本単位を参照基本単位として選択するステップと、
ターゲットフレームにおける各基本単位と当該基本単位に対応する参照フレームにおける参照基本単位との差分情報を取得するステップと、
前記差分情報を圧縮するステップと、を備えている圧縮方法。
【請求項１３】
前記参照フレームのポリゴン・メッシュ・モデルは、請求項１〜４いずれかに記載の基本単位の属性データに対して圧縮処理を適用することでフレーム内圧縮が行われたポリゴン・メッシュ・データを復号してなるデータであり、当該参照フレームポリゴン・メッシュ・モデルの基本単位は、フレーム内圧縮時に生成されている、請求項１２に記載の圧縮方法。
【請求項１４】
ターゲットフレームの基本単位を形成する頂点、参照フレームの基本単位を形成する頂点にはそれぞれIDが順番に付与されており、
ターゲットフレームの基本単位の各頂点IDの差分情報と参照基本単位の頂点IDとの対応関係を、参照基本単位の頂点ID順に並び替えることで当該参照基本単位の頂点IDの対応するターゲットフレームの基本単位の頂点数を取得し、
各差分情報を、前記頂点数に関連付けて記憶する、請求項１２、１３いずれかに記載の圧縮方法。
【請求項１５】
請求項１〜４いずれかに記載の基本単位の属性データに対して圧縮処理を適用することでフレーム内圧縮を行う３次元動画像の圧縮方法。
【図１】
【図２】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図３】
【図４】
【図８Ａ】
【図８Ｂ】
【図２】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図３】
【図４】
【図８Ａ】
【図８Ｂ】
【公開番号】特開２０１２−６８８８１（Ｐ２０１２−６８８８１Ａ）
【公開日】平成２４年４月５日（２０１２．４．５）
【国際特許分類】
【出願番号】特願２０１０−２１２８３７（Ｐ２０１０−２１２８３７）
【出願日】平成２２年９月２２日（２０１０．９．２２）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２１年度、独立行政法人情報通信研究機構「高度通信・放送研究開発委託研究／革新的な三次元映像技術による超臨場感コミュニケーション技術の研究開発」、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（５０４１３７９１２）国立大学法人 東京大学 (1,942)
【Ｆターム（参考）】
【公開日】平成２４年４月５日（２０１２．４．５）
【国際特許分類】
【出願日】平成２２年９月２２日（２０１０．９．２２）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２１年度、独立行政法人情報通信研究機構「高度通信・放送研究開発委託研究／革新的な三次元映像技術による超臨場感コミュニケーション技術の研究開発」、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（５０４１３７９１２）国立大学法人 東京大学 (1,942)
【Ｆターム（参考）】
[ Back to top ]