(57)【要約】【課題】  深さ画像基盤の３次元グラフィックデータの高速視覚化方法及び装置を提供する。【解決手段】  （ａ）画像基盤グラフィックデータで表現された３次元客体を読み取る段階と、（ｂ）所定の視点で、シンプルテクスチャーデータのそれぞれの参照画像について３次元ワーピングを行って複数のワーピング画像を得る段階と、（ｃ）ワーピング画像について、各画素別に深さテスト及びスプラッティングを行って最終カラーデータを得る段階と、（ｄ）最終カラーデータを利用して客体を視覚化する段階と、を含むことを特徴とする深さ画像基盤の３次元グラフィックデータの高速視覚化方法。これにより、画像基盤で表現された３次元グラフィック客体の可視化を容易にし、メモリの使用量を減らしつつ秒当たり可視化できる回数を増加させることができる。特に、移動端末機器に利用される場合、非常に効果的に３次元グラフィック客体の視覚化を行える。【選択図】  図１１
2005228320.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）複数の参照画像よりなるシンプルテクスチャーデータをメモリに割り当てる段階と、
（ｂ）所定の視点で、前記シンプルテクスチャーデータのそれぞれの参照画像について３次元ワーピングを行って複数のワーピング画像を得る段階と、
（ｃ）前記複数のワーピング画像を構成する画素について、画素別に深さテストを行って深さデータ及びカラーデータを得る段階と、
（ｄ）前記深さデータ及びカラーデータを利用して客体を視覚化する段階と、を含むことを特徴とする深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項２】
前記（ａ）段階の参照画像は、
客体を含む最小サイズの四角形の外側に存在する背景データを除外することを特徴とする請求項１に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項３】
前記（ｂ）複数のワーピング画像を得る段階は、
（ｂ１）所定の視点での目座標系の中心を前記シンプルテクスチャーデータの参照画像に投影してエピポーラ点を探す段階と、
（ｂ２）前記エピポーラ点が投影された領域が、参照画像に定義された９個の領域のどこに属するかによって参照画像画素のワーピング順序を決定する段階と、
（ｂ３）前記ワーピング順序によって、シンプルテクスチャーが定義された基準座標系での各座標を目座標系に変換してワーピング画像を得る段階と、
（ｂ４）前記（ｂ１）段階ないし（ｂ３）段階を、前記シンプルテクスチャーデータの参照画像について反復して行う段階と、を具備することを特徴とする請求項１に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項４】
前記（ｂ）段階において、３次元ワープを、浮動小数点演算を固定小数点演算することにより行い、
前記固定小数点演算は、
浮動小数点を固定小数点に変換する段階と、
変換された固定小数点を利用して座標変換する段階と、
前記演算結果を浮動小数点変換の表現に変える段階と、を具備することを特徴とする請求項１に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項５】
前記（ｃ）段階の画素別深さテストは、
（ｃ１）第１の参照画像についてワーピングを行って生成された深さ値及びカラー値を、前面深さバッファ及び前面カラーバッファに保存する段階と、
（ｃ２）第２の参照画像についてワーピングを行って生成された深さ値及びカラー値を、背面深さバッファと背面カラーバッファに保存する段階と、
（ｃ３）前記前面深さバッファに保存された深さ値と、前記背面深さバッファに保存された深さ値とを比較する段階と、
（ｃ４）前記比較結果、前面深さバッファの値が背面深さバッファの値より大きい場合、前面深さバッファの値及び前面カラーバッファの値を背面深さバッファの値及び背面カラーバッファの値に更新する段階と、
（ｃ５）前記（ｃ１）ないし（ｃ４）段階を全てのワーピング画像について行う段階と、を具備することを特徴とする請求項１に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項６】
前記（ｃ）段階は、
（ｃｃ）所定の視点から３次元客体までの距離によってスプラットサイズを適応調節する段階をさらに具備し、
前記（ｄ）段階は、
前記深さデータ及びカラーデータ及び大きさが調節されたスプラットを利用して客体を視覚化することを特徴とする請求項１に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項７】
前記（ｃｃ）段階は、
（ｃｃ１）基準画像の解像度と目的画像の解像度とを比較して初期スプラットサイズを定める段階と、
（ｃｃ２）初期スプラットサイズをズームイン／ズームアウト時の拡大／縮少比率に合わせて変更して目的画像を生成する段階と、を含むことを特徴とする請求項６に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項８】
前記（ｃｃ１）段階は、
目的画像の解像度が基準画像の解像度と同一またはそれより小さい場合、スプラットサイズを１と設定し、目的画像の解像度が基準画像の解像度より大きい場合、横／縦の拡大比率の平均値としてスプラットサイズを設定することを特徴とする請求項７に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項９】
前記（ｃｃ２）段階は、
拡大比率を利用して、ズームインの際には穴の生成を防止できるようにズーム比率によりスプラットサイズを拡大し、ズームアウトの際には所定の視覚化品質が維持されるように、ズーム比率によりスプラットサイズを縮少することを特徴とする請求項７に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項１０】
（ａ）３次元客体をポイントテクスチャーデータとして読み取る段階と、
（ｂ）所定の視点で前記ポイントテクスチャーの参照画像について、エピポーラ点の位置及び深さ座標値の符号によってピクセルのワーピング順序を決定する段階と、
（ｃ）前記ワーピング順序を利用して３次元客体を視覚化する段階と、を含むことを特徴とする深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項１１】
前記（ａ）段階は、
８進ツリー構造で表現された３次元客体データをポイントテクスチャーデータに変換して読み取る段階であることを特徴とする請求項１０に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項１２】
前記（ａ）段階は、
８進ツリー構造で表現された３次元客体データを復号化する段階と、
前記復号化された８進ツリーを含む六面体の所定の面を基準面として、前記基準面の垂直方向に、基準面の特定ピクセル位置に前記８進ツリーの体積素を投影する段階と、
体積素から、前記基準面に投影された体積素の基準面上のピクセルまでの距離を深さ値とする段階と、
前記体積素の色相をカラー値で表示する段階と、を含むことを特徴とする請求項１１に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項１３】
前記（ｂ）段階は、
投影されたエピポーラ点に向かう方向に参照画像画素の横及び縦方向のワーピング順序を決定する段階と、
エピポーラ点の深さ軸（ｚ）座標が正数であれば後方から前方に、負数であれば前方から後方に参照画像画素の深さ軸（ｚ）方向のワーピング順序が決定される段階と、を具備することを特徴とする請求項１０に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項１４】
前記座標変換は、
浮動小数点演算を固定小数点演算することにより行われ、
前記固定小数点演算は、
浮動小数点を固定小数点に変換する段階と、
変換された固定小数点を利用して座標変換する段階と、
前記演算結果を浮動小数点変換の表現に変える段階と、を具備することを特徴とする請求項１３に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項１５】
前記（ｂ）段階は、
（ｂｂ）所定の視点から３次元客体までの距離によってスプラットサイズを適応調節する段階をさらに具備し、
前記（ｃ）段階は、
ワーピング順序及び大きさが調節されたスプラットを利用して３次元客体を視覚化することを特徴とする請求項１０に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項１６】
前記（ｂｂ）段階は、
（ｂｂ１）基準画像の解像度と目的画像の解像度とを比較して初期スプラットサイズを定める段階と、
（ｂｂ２）初期スプラットサイズを、ズームイン／ズームアウト時の拡大／縮少比率に合わせて変更して目的画像を生成する段階と、を含むことを特徴とする請求項１５に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項１７】
前記（ｂｂ１）段階は、
目的画像の解像度が基準画像の解像度と同一またはそれより小さい場合、スプラットサイズを１と設定し、目的画像の解像度が基準画像の解像度より大きい場合、横／縦の拡大比率の平均値としてスプラットサイズを設定することを特徴とする請求項１６に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項１８】
前記（ｂｂ２）段階は、
拡大比率を利用して、ズームインの際には穴の生成を防止できるようにズーム比率によりスプラットサイズを拡大し、ズームアウトの際には所定の視覚化品質が維持されるように、ズーム比率によりスプラットサイズを縮少することを特徴とする請求項１６に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法。
【請求項１９】
複数の参照画像よりなるシンプルテクスチャーデータをメモリに割り当てるシンプルテクスチャーデータメモリ割り当て部と、
所定の視点で、前記シンプルテクスチャー初期化部のシンプルテクスチャーそれぞれの参照画像について３次元ワーピングを行って、複数のワーピング画像を生成するワーピング部と、
前記ワーピング部で生成された複数のワーピング画像を構成する画素について、画素別に深さテストを行って深さデータ及びカラーデータを得る深さテスト部と、
前記深さデータ及びカラーデータを利用して３次元客体を視覚化する視覚化部と、を含むことを特徴とする深さ画像基盤の３次元グラフィックデータの高速視覚化装置。
【請求項２０】
前記シンプルテクスチャーの各参照画像は、
客体を含む最小サイズの四角形の外側に存在する背景データを除外することを特徴とする請求項１９に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化装置。
【請求項２１】
前記ワーピング部は、
シンプルテクスチャーの各参照画像について、所定の視点での目座標系の中心を前記シンプルテクスチャーデータの参照画像に投影してエピポーラ点を探すエピポーラ変換部と、
シンプルテクスチャーの各参照画像について、前記エピポーラ点が投影された領域が参照画像に定義された９個の領域のどこに属するかによって参照画像画素のワーピング順序を決定するワーピング順序決定部と、
シンプルテクスチャーの各参照画像について、前記ワーピング順序によってシンプルテクスチャーが定義された基準座標系での各座標を目座標系に変換して、ワーピング画像を得る画素ワーピング部と、を具備することを特徴とする請求項１９に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化装置。
【請求項２２】
前記ワーピング部で行われる演算は、
浮動小数点を固定小数点に変換して座標変換した後、再び浮動小数点変換の表現に変換することであることを特徴とする請求項１９に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化装置。
【請求項２３】
前記深さテスト部は、
第１の参照画像についてワーピングを行って、生成された深さ値を保存する前面深さバッファと、
第１の参照画像についてワーピングを行って、生成されたカラー値を保存する前面カラーバッファと、
第２の参照画像についてワーピングを行って、生成された深さ値を保存する背面深さバッファと、
第２の参照画像についてワーピングを行って、生成されたカラー値を保存する背面カラーバッファと、
前記前面深さバッファに保存された深さ値と、前記背面深さバッファに保存された深さ値とを比較する深さ比較部と、
前記比較結果、前面深さバッファの値が背面深さバッファの値より大きい場合、全ての参照画像について前面深さバッファの値及び前面カラーバッファの値を背面深さバッファの値及び背面カラーバッファの値に更新する深さ値更新部と、
を具備することを特徴とする請求項１９に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化装置。
【請求項２４】
前記深さテスト部は、
所定の視点から３次元客体までの距離によってスプラットサイズを適応調節するスプラット部をさらに具備し、
前記視覚化部は、
前記深さデータ及びカラーデータ及び大きさが調節されたスプラットを利用して３次元客体を視覚化することを特徴とする請求項１９に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化装置。
【請求項２５】
前記スプラット部は、
基準画像の解像度と目的画像の解像度とを比較して初期スプラットサイズを定めるスプラットサイズ設定部と、
初期スプラットサイズを、ズームイン／ズームアウト時の拡大／縮少比率に合わせて変更して、目的画像を生成する適応的スプラット部と、を含むことを特徴とする請求項２４に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化装置。
【請求項２６】
３次元客体をポイントテクスチャーデータとして読み取るポイントテクスチャー初期化部と、
所定の視点で、前記ポイントテクスチャーの参照画像について、エピポーラ点の位置及び深さ座標値の符号によってピクセルを描くワーピング順序を決定するワーピング順序決定部と、
所定の視点から３次元客体までの距離によってスプラットサイズを適応調節するポイントテクスチャースプラット部と、
前記ワーピング順序及び大きさが調節されたスプラットを利用して、３次元客体を視覚化するポイントテクスチャー視覚化部と、を含むことを特徴とする画像基盤３次元グラフィックデータの高速視覚化装置。
【請求項２７】
前記ポイントテクスチャー初期化部は、
８進ツリー構造で表現された３次元客体データをポイントテクスチャーデータに変換することを特徴とする請求項２６に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化装置。
【請求項２８】
前記ポイントテクスチャー初期化部は、
８進ツリー構造で表現された３次元客体データを復号化する８進ツリー復号化部と、
前記復号化された８進ツリーを含む六面体の所定の面を基準面として前記基準面の垂直方向に、基準面の特定ピクセル位置に前記８進ツリーの体積素を投影して、前記体積素から、記基準面に投影された体積素の基準面上のピクセルまでの距離を深さ値とする深さ値計算部と、
前記体積素の色相をカラー値として表示するカラー値生成部と、を含むことを特徴とする請求項２７に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化装置。
【請求項２９】
前記ワーピング順序決定部のワーピング順序は、
投影されたエピポーラ点に向かう方向に参照画像画素の横及び縦方向のワーピング順序を決定し、エピポーラ点の深さ軸（ｚ）座標が正数である場合後方から前方に、負数である場合前方から後方に参照画像画素の深さ軸（ｚ）方向のワーピング順序を決定する請求項２６に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化装置。
【請求項３０】
前記ワーピング順序決定部で発生するワーピング演算は、
浮動小数点を固定小数点に変換して座標変換した後、再び浮動小数点変換の表現に変換することを特徴とする請求項２６に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化装置。
【請求項３１】
請求項１ないし１８のうちいずれか１項に記載の深さ画像基盤の３次元グラフィックデータの高速視覚化方法をコンピュータに実行させるためのプログラムを記録したコンピュータ可読記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は３次元グラフィックに係り、より詳細には深さ画像基盤の３次元グラフィックデータの高速視覚化方法、装置及びプログラムを記録したコンピュータ可読記録媒体に関する。
【背景技術】
【０００２】
３次元グラフィックに関する研究の初期から研究者の究極的な目標は、実世界のような現実的なグラフィック画面を生成することである。現在コンピュータグラフィックにおける３次元客体表現の主要な方法は、多角形モデルである。任意の形状を色相多角形の集合、すなわち、三角形により概略的に表現できる。現在ソフトウェアアルゴリズムの著しい進歩及びグラフィックハードウェアの発展により、複雑な客体及び場面をリアルタイムで現実に近い静止及びアニメーションモデルに視覚化することができる。
【０００３】
最近携帯電話や個人情報端末機（Personal Data Assistant: PDA)のような移動端末機器が急速に普及し、キャラクターサービス、動画像、音楽、ゲームなど各種マルチメディアサービスを移動機器を通じて供給する環境が構築されつつあり、３次元グラフィック客体を移動機器で再生しようとする試みが進んでいる。しかし、一般のパソコンとは違って、移動機器は、中央演算処理装置(Central Processing Unit: CPU)の性能が低く、浮動小数点の演算を支援せず、３次元グラフィック加速器を装着していないために、パソコンと同レベルの視覚化性能を確保することが非常に困難である。
【０００４】
一方、深さイメージ基盤表現（Depth Image-Based Representation: DIBR)は、複雑な幾何学的構造を持つ客体を容易に表現し、かつ視覚化する新たな表現方法である（非特許文献１及び２参照）。前記ＤＩＢＲは、ＭＰＥＧ−４ ＡＦＸ(Animation Framework eXtension)に採択されている（非特許文献３参照）。コンピュータグラフィックでは多角形メッシュで客体を表現するのが代表的であるが、ＤＩＢＲの表現方法のうちシンプルテクスチャーは、３次元グラフィック客体を目に見える客体の表面を包む参照画像の集合で表している。各参照イメージは相応する深さマップで表現され、前記深さマップは、イメージ平面のピクセルから客体表面までの距離を配列で表したものである。シンプルテクスチャーの利点のうち一つは、多角形モデルを直接使用しなくても参照イメージが客体についての良質の視覚化を提供できるということである。さらに、新たなビュー(view)を作り出すための視覚化の計算量の複雑性は、シーン(scene)の複雑性には関係なくビューのピクセル数（すなわち、ビューの解像度）のみに関連する。このような特徴は、スクリーンの解像度が低い移動機器での視覚化に対して多大な寄与することができる。前記シンプルテクスチャーは、図１のように３次元客体をＮ個のカメラで観測したカラー及び深さ画像で表現する。
【０００５】
ＤＩＢＲファミリーのさらに他の形式は、ポイントテクスチャー及び８進ツリー画像である。前記ポイントテクスチャーは、図２のように一つのカメラ位置から見たピクセルの配列で客体を表現する。それぞれのポイントテクスチャーピクセルは色、ピクセルからカメラまでの距離に該当する深さ及びポイントテクスチャー視覚化を補助する複数の他の属性により表現される。各視線に沿って物体との交点で複数のピクセルがあり得、したがって、ポイントテクスチャーは普通複数の層で構成される。８進ツリー画像は、図３のように８進ツリーで物体の形体を表現し、各面での画像を基準画像として持つ表現方式である。
【０００６】
ＭｃＭｉｌｌａｎは１枚の参照画像を持っている場合、深さテストの実行なしに新たな視点での視覚化されたビューを生成できるワーピングアルゴリズムを開発した（非特許文献４参照）。前記ＭｃＭｉｌｌａｎの方法を説明すれば次の通りである。図４のように、参照画像の幾何情報に基いてワールド座標系を作る。例えば、基準座標系の点Ｐ１がワールド座標系の点Ｐ２を作る。新たな視点から点Ｐ２を眺めれば点Ｐ３となり、点Ｐ３は、点Ｐ１に変換Ｔを適用して作られる。参照画像での点を、新たな視点から眺めた時の点に整列するために、新たな視点の中心（新たなカメラ中心）が参照画像に投影される地点であるエピポーラ点を探す。そして、この点が存在する投射地点が図５のような９つの領域のうちいかなる領域に属するかを調べ、ｚ座標の符号によって参照画像のピクセルをスプラッティングする順序を変えるアルゴリズムである。このように設定された順に、格子構造の行及び列に沿って１ピクセルずつ新たなビューに投影させる順次的視覚化を行えば、常に以後に描かれる画素がさらに近い地点を表すので、深さテストが不要になる。
【０００７】
Ｓｈａｄｅは、単純な深さ画像を拡張して一つのピクセル位置に多重のピクセルが対応している階層化深さ画像を提案した（非特許文献５参照）。単純な深さ画像は、視点が変わる時にデータが存在していない物体の表面に対して歪曲が発生するのに対し、階層化深さ画像は、視点で観測されていない物体の背面までいずれも３次元座標情報を持っているために、このような歪曲が発生しない長所を有している。階層化深さ画像の視覚化はＭｃＭｉｌｌａｎのアルゴリズムとほぼ類似しているが、新たな視点の参照画像でのエピポーラ点の位置及びｚ座標の符号によって、図５のように新たな画像でピクセルを描く順序、すなわち、方向を決定する。このような方法で常に視覚化のｂａｃｋ−ｔｏ−ｆｒｏｎｔ順序が成立して深さテストなしに視覚化が可能である。
【０００８】
一方、移動機器で、３次元グラフィック客体の視覚化を画像基盤表現技法を利用して高速化する以前の研究はほとんどなされなかった。
【非特許文献１】ＩＳＯ／ＩＥＣ ＪＴＣ１／ＳＣ２９／ＷＧ１１ １４４９６−１６，Ｃｏｄｉｎｇ ｏｆ Ａｕｄｉｏ−Ｖｉｓｕａｌ Ｏｂｊｅｃｔｓ：Ａｎｉｍａｔｉｏｎ Ｆｒａｍｅｗｏｒｋ ｅＸテンション（ＡＦＸ）
【非特許文献２】Ｍ．Ｏｌｉｖｅｉｒａ，Ｇ．Ｂｉｓｈｏｐ，ａｎｄ Ｄ．ＭａｃＡｌｌｉｓｔｅｒ，“Ｒｅｌｉｅｆ ｔｅｘｔｕｒｅｓ ｍａｐｐｉｎｇ，” Ｐｒｏｃ．ＳＩＧＧＲＡＰＨ’００，ｐｐ．３５９−３６８，Ｊｕｌｙ ２０００．
【非特許文献３】Ｙｕｒｉ Ｂａｙａｋｏｖｓｋｉ，Ｌｅｏｎｉｄ Ｌｅｖｋｏｖｉｃｈ−Ｍａｓｌｙｕｋ，Ａｌｅｘｅｙ Ｉｇｎａｔｅｎｋｏ，Ａｎｔｏｎ Ｋｏｎｕｓｈｉｎ，Ｄｍｉｔｒｉ Ｔｉｍａｓｏｖ，Ａｌｅｘａｎｄｅｒ Ｚｈｉｒｋｏｖ，Ｍａｈｎｊｉｎ Ｈａｎ，ａｎｄ Ｉｎ Ｋｙｕ Ｐａｒｋ，“Ｄｅｐｔｈ ｉｍａｇｅ−ｂａｓｅｄ ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ ｆｏｒ ｓｔａｔｉｃ ａｎｄ ａｎｉｍａｔｅｄ ３Ｄ ｏｂｊｅｃｔｓ，”Ｐｒｏｃ．ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，ｖｏｌ．ＩＩＩ，ｐｐ．２５−２８，Ｒｏｃｈｅｓｔｅｒ，ＵＳＡ，Ｓｅｐｔｅｍｂｅｒ ２００２．
【非特許文献４】Ｌ．ＭｃＭｉｌｌａｎ，Ａｎ ｉｍａｇｅ−ｂａｓｅｄ ａｐｐｒｏａｃｈ ｔｏ ｔｈｒｅｅ−ｄｉｍｅｎｓｉｏｎａｌ ｃｏｍｐｕｔｅｒ ｇｒａｐｈｉｃｓ，Ｐｈ．Ｄ Ｄｉｓｓｅｒｔａｔｉｏｎ，Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｎｏｒｔｈ Ｃａｒｏｌｉｎａ ａｔ Ｃｈａｐｅｌ Ｈｉｌｌ，１９９７．
【非特許文献５】Ｊ．Ｓｈａｄｅ，Ｓ．Ｇｏｒｔｌｅｒ，Ｌ．Ｈｅ，ａｎｄ Ｒ．Ｓｚｅｌｉｓｋｉ，Ｌａｙｅｒｅｄ ｄｅｐｔｈ ｉｍａｇｅｓ，Ｐｒｏｃ．ｏｆ ＳＩＧＧＲＡＰＨ’９８，ｐｐ．２３１−２４２，Ｊｕｌｙ １９９８．
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明が解決しようとする技術的課題は、既存の視覚化に比べてメモリの使用量を減らして視覚化速度を高めるために、シンプルテクスチャー、ポイントテクスチャー、８進ツリー画像のうちいずれか一つで表現された深さ画像基盤の３次元グラフィックデータの高速視覚化方法、装置及びプログラムを記録したコンピュータ可読記録媒体を提供することである。
【課題を解決するための手段】
【００１０】
前述した技術的課題を解決するための、本発明による深さ画像基盤の３次元グラフィックデータのうち、シンプルテクスチャーデータの高速視覚化方法は、（ａ）複数の参照画像よりなるシンプルテクスチャーデータをメモリに割り当てる段階と、（ｂ）所定の視点で、前記シンプルテクスチャーデータのそれぞれの参照画像について３次元ワーピングを行って複数のワーピング画像を得る段階と、（ｃ）前記複数のワーピング画像を構成する画素について、画素別に深さテストを行って深さデータ及びカラーデータを得る段階と、（ｄ）前記深さデータ及びカラーデータを利用して客体を視覚化する段階と、を含むことを特徴とする。
【００１１】
前記（ａ）段階の参照画像は、客体を含む最小サイズの四角形の外側に存在する背景データを除外することが望ましい。
前記（ａ）段階の参照画像は、客体を含む最小サイズの四角形の外側に存在する背景データを除外した深さデータ及びカラーデータを備えることが望ましい。
【００１２】
前記（ｂ）段階の３次元ワーピングは、前記シンプルテクスチャーデータを構成する複数の参照画像のうち、所定の視線ベクトルと参照画像の法線ベクトルとがなす角が所定の値以下である参照画像についてのみ行うことが望ましい。前記（ｂ）段階のワーピングは、（ｂ１）所定の視点での目座標系の中心を前記シンプルテクスチャーデータの参照画像に投影してエピポーラ点を探す段階と、（ｂ２）前記エピポーラ点が投影された領域が、参照画像に定義された９個の領域のどこに属するかによって参照画像画素のワーピング順序を決定する段階と、（ｂ３）前記ワーピング順序によって、シンプルテクスチャーが定義された基準座標系での各座標を目座標系に変換してワーピング画像を得る段階と、（ｂ４）前記（ｂ１）段階ないし（ｂ３）段階を、前記シンプルテクスチャーデータの参照画像について反復して行う段階と、を含む。
【００１３】
前記座標変換は、浮動小数点演算を固定小数点演算することによって行うことがが望ましい。前記固定小数点演算は、浮動小数点を固定小数点に変換する段階と、変換された固定小数点を利用して座標変換する段階と、前記演算結果を浮動小数点変換の表現に変える段階と、を具備することが望ましい。
【００１４】
前記（ｃ）段階の画素別深さテストは、（ｃ１）第１の参照画像についてワーピングを行って生成された深さ値及びカラー値を、前面深さバッファ及び前面カラーバッファに保存する段階と、（ｃ２）第２の参照画像についてワーピングを行って生成された深さ値及びカラー値を、背面深さバッファと背面カラーバッファに保存する段階と、（ｃ３）前記前面深さバッファに保存された深さ値と、前記背面深さバッファに保存された深さ値とを比較する段階と、（ｃ４）前記比較結果、前面深さバッファの値が背面深さバッファの値より大きい場合、前面深さバッファの値及び前面カラーバッファの値を背面深さバッファの値及び背面カラーバッファの値に更新する段階と、（ｃ５）前記（ｃ１）ないし（ｃ４）段階を全てのワーピング画像について行う段階と、を具備することが望ましい。
【００１５】
前記（ｃ）段階は、（ｃｃ）所定の視点から３次元客体までの距離によってスプラットサイズを適応調節する段階をさらに具備し、前記（ｄ）段階は、前記深さデータ及びカラーデータ及び大きさが調節されたスプラットを利用して客体を視覚化することが望ましい。前記（ｃｃ）段階は、（ｃｃ１）基準画像の解像度と目的画像の解像度とを比較して初期スプラットサイズを定める段階と、（ｃｃ２）初期スプラットサイズをズームイン／ズームアウト時の拡大／縮少比率に合わせて変更して目的画像を生成する段階と、を含むことが望ましい。前記（ｃｃ１）段階は、目的画像の解像度が基準画像の解像度と同一またはそれより小さい場合、スプラットサイズを１と設定し、目的画像の解像度が基準画像の解像度より大きい場合、横／縦の拡大比率の平均値としてスプラットサイズを設定することが望ましい。前記（ｃｃ２）段階は、拡大比率を利用して、ズームインの際には穴の生成を防止できるようにズーム比率によりスプラットサイズを拡大し、ズームアウトの際には所定の視覚化品質が維持されるように、ズーム比率によりスプラットサイズを縮少することが望ましい。
【００１６】
前述した技術的課題を解決するための本発明による深さ画像基盤の３次元グラフィックデータのうちポイントテクスチャーデータの高速視覚化方法は、（ａ）３次元客体をポイントテクスチャーデータとして読み取る段階と、（ｂ）所定の視点で前記ポイントテクスチャーの参照画像について、エピポーラ点の位置及び深さ座標値の符号によってピクセルのワーピング順序を決定する段階と、（ｃ）前記ワーピング順序を利用して３次元客体を視覚化する段階と、を含むことを特徴とする。
【００１７】
前記本発明によるポイントテクスチャーデータの高速視覚化方法において、前記（ａ）段階は、８進ツリー構造で表現された３次元客体データをポイントテクスチャーデータに変換して読み取る段階である。前記ポイントテクスチャーデータの高速視覚化方法において、前記（ａ）段階は、８進ツリー構造で表現された３次元客体データを復号化する段階と、前記復号化された８進ツリーを含む六面体の所定の面を基準面として、前記基準面の垂直方向に、基準面の特定ピクセル位置に前記８進ツリーの体積素を投影する段階と、体積素から、前記基準面に投影された体積素の基準面上のピクセルまでの距離を深さ値とする段階と、前記体積素の色相をカラー値で表示する段階と、を含むことが望ましい。
【００１８】
前記ポイントテクスチャーデータの高速視覚化方法において、前記（ｂ）段階は、視点が変わった場合、前記ポイントテクスチャーが定義された基準座標系での各座標を目座標系に座標変換した後に行うことが望ましい。ポイントテクスチャーデータの高速視覚化方法において、前記座標変換は、浮動小数点演算を固定小数点演算することより行うことが望ましい。ポイントテクスチャーデータの高速視覚化方法において、前記（ｃ）段階は、前記ワーピング順序と適応調節されたスプラットサイズを利用して３次元客体を視覚化することが望ましい。ポイントテクスチャーデータの高速視覚化方法において、前記（ｃ）段階は、基準画像の解像度と目的画像の解像度とを比較して初期スプラットサイズを定める段階と、初期スプラットサイズを、ズームイン／ズームアウト時の拡大／縮少比率に合わせて変更して目的画像を生成する段階と、を含むことが望ましい。
【００１９】
前述した技術的課題を解決するための本発明による深さ画像基盤の３次元グラフィックデータのうちシンプルテクスチャーデータの高速視覚化装置は、複数の参照画像よりなるシンプルテクスチャーデータをメモリに割り当てるシンプルテクスチャーデータメモリ割り当て部と、所定の視点で、前記シンプルテクスチャー初期化部のシンプルテクスチャーそれぞれの参照画像について３次元ワーピングを行って、複数のワーピング画像を生成するワーピング部と、前記ワーピング部で生成された複数のワーピング画像を構成する画素について、画素別に深さテストを行って深さデータ及びカラーデータを得る深さテスト部と、前記深さデータ及びカラーデータを利用して３次元客体を視覚化する視覚化部と、を含むことを特徴とする。
【００２０】
前記ワーピング部は、シンプルテクスチャーの各参照画像について、所定の視点での目座標系の中心を前記シンプルテクスチャーデータの参照画像に投影してエピポーラ点を探すエピポーラ変換部と、シンプルテクスチャーの各参照画像について、前記エピポーラ点が投影された領域が参照画像に定義された９個の領域のどこに属するかによって参照画像画素のワーピング順序を決定するワーピング順序決定部と、シンプルテクスチャーの各参照画像について、前記ワーピング順序によってシンプルテクスチャーが定義された基準座標系での各座標を目座標系に変換して、ワーピング画像を得る画素ワーピング部と、を具備することが望ましい。
【００２１】
前記深さテスト部は、第１の参照画像についてワーピングを行って、生成された深さ値を保存する前面深さバッファと、第１の参照画像についてワーピングを行って、生成されたカラー値を保存する前面カラーバッファと、第２の参照画像についてワーピングを行って、生成された深さ値を保存する背面深さバッファと、第２の参照画像についてワーピングを行って、生成されたカラー値を保存する背面カラーバッファと、前記前面深さバッファに保存された深さ値と、背面深さバッファに保存された深さ値とを比較する深さ比較部と、前記比較結果、前面深さバッファの値が背面深さバッファの値より大きい場合、全ての参照画像について前面深さバッファの値及び前面カラーバッファの値を背面深さバッファの値及び背面カラーバッファの値に更新する深さ値更新部と、を具備することが望ましい。
【００２２】
前記深さテスト部は、所定の視点から３次元客体までの距離によってスプラットサイズを適応調節するスプラット部をさらに具備し、前記視覚化部は、前記深さデータ及びカラーデータ及び大きさが調節されたスプラットを利用して３次元客体を視覚化することを特徴とする。前記スプラット部は、基準画像の解像度と目的画像の解像度とを比較して初期スプラットサイズを定めるスプラットサイズ設定部と、初期スプラットサイズを、ズームイン／ズームアウト時の拡大／縮少比率に合わせて変更して、目的画像を生成する適応的スプラット部と、を含むことが望ましい。
【００２３】
前述した技術的課題を解決するための本発明による深さ画像基盤の３次元グラフィックデータのうちポイントテクスチャーデータの高速視覚化装置は、３次元客体をポイントテクスチャーデータとして読み取るポイントテクスチャー初期化部と、所定の視点で、前記ポイントテクスチャーの参照画像について、エピポーラ点の位置及び深さ座標値の符号によってピクセルを描くワーピング順序を決定するワーピング順序決定部と、所定の視点から３次元客体までの距離によってスプラットサイズを適応調節するポイントテクスチャースプラット部と、前記ワーピング順序及び大きさが調節されたスプラットを利用して、３次元客体を視覚化するポイントテクスチャー視覚化部と、を含むことが望ましい。
【００２４】
前記ポイントテクスチャー初期化部は、８進ツリー構造で表現された３次元客体データをポイントテクスチャーデータに変換することが望ましい。前記ポイントテクスチャー初期化部は、８進ツリー構造で表現された３次元客体データを復号化する８進ツリー復号化部と、前記復号化された８進ツリーを含む六面体の所定の面を基準面として前記基準面の垂直方向に、基準面の特定ピクセル位置に前記８進ツリーの体積素を投影して、前記体積素から、記基準面に投影された体積素の基準面上のピクセルまでの距離を深さ値とする深さ値計算部と、前記体積素の色相をカラー値として表示するカラー値生成部と、を含むことが望ましい。
【００２５】
前記ワーピング順序決定部の参照画像は、客体を含む最小サイズの四角形の外側に存在する背景データを除外した深さ及びカラーデータを具備することが望ましい。前記ワーピング順序決定部は、前記視点が変われば、前記ポイントテクスチャーが定義された基準座標系での各座標を目座標系に座標変換する座標変換部をさらに具備することが望ましい。前記ワーピング順序決定部のワーピング順序は、投影されたエピポーラ点に向かう方向に参照画像画素の横及び縦方向のワーピング順序が決定され、エピポーラ点の深さ軸（ｚ）座標が正数である場合後方から前方に、負数である場合前方から後方に参照画像画素の深さ軸（ｚ）方向のワーピング順序が決定することが望ましい。
【００２６】
そして、前記本発明の深さ画像基盤の３次元グラフィックデータの高速視覚化方法をコンピュータで実行させるためのプログラムを記録したコンピュータ可読記録媒体を提供する。
【発明の効果】
【００２７】
本発明による深さ画像基盤の３次元客体データの高速視覚化方法及び装置によれば、画像基盤で表現された３次元グラフィック客体の可視化を容易にし、メモリの使用量を減らし、なおかつ秒当たり可視化できる回数を増加させることができる。特に、移動端末機器に本発明による深さ画像基盤の３次元客体データの高速視覚化方法及び装置を適用した場合に、非常に効果的に３次元グラフィック客体の視覚化を行える。
【００２８】
また、メモリ使用量が減ってメモリアクセスに消耗される電力の量も減少するため、移動端末機器に本発明による深さ画像基盤の３次元客体データの高速視覚化方法及び装置を適用した場合に、その移動端末機器の使用時間を延長でき、パソコンだけでなくＣＰＵ性能やメモリが制限されたＰＤＡあるいは携帯電話などの移動端末機器でも高速で視覚化できる。
【発明を実施するための最良の形態】
【００２９】
以下、添付された図面を参照して本発明による深さ画像基盤の３次元グラフィックデータの高速視覚化方法及び装置について詳細に説明する。本発明の深さ画像基盤の３次元グラフィックデータの高速視覚化方法及び装置は、シンプルテクスチャー視覚化及びポイントテクスチャー視覚化、８進ツリー画像視覚化に大別される。そして、前記シンプルテクスチャー視覚化、ポイントテクスチャー視覚化及び８進ツリー画像視覚化は、共通的に固定小数点演算を利用した高速視覚化、適応的スプラッティング、基準画像での背景データの除去に関する技術が使われる。
【００３０】
まず、シンプルテクスチャー視覚化について説明する。図６は、本発明による深さ画像基盤の３次元グラフィックデータの高速視覚化装置についての一実施例の構成を示すブロック図であり、シンプルテクスチャーデータメモリ割り当て部６００、ワーピング部６１０、深さテスト部６２０、スプラット部６３０及び視覚化部６４０から主として構成されている。
【００３１】
前記シンプルテクスチャーデータメモリ割り当て部６００は、複数の参照画像よりなるシンプルテクスチャーデータをメモリに割り当てる。
【００３２】
前記ワーピング部６１０は、所定の視点で、前記シンプルテクスチャーデータメモリ割り当て部６００のシンプルテクスチャー参照画像について３次元ワーピングを行って複数のワーピング画像を生成し、図７に示すように、エピポーラ変換部７００、ワーピング順序決定部７２０及び画素ワーピング部７４０から主として構成されている。
【００３３】
前記エピポーラ変換部７００は、所定の視点での目座標系の中心を前記シンプルテクスチャーデータの参照画像に投影してエピポーラ点を探す。前記ワーピング順序決定部７２０は、エピポーラ点が投影された領域が参照画像に定義された９個の領域のどこに属するかによって参照画像画素のワーピング順序を決定する。前記画素ワーピング部７４０は、ワーピング順序によってシンプルテクスチャーが定義された基準座標系での各座標を目座標系に変換してワーピング画像を得る。
【００３４】
前記ワーピング部６１０で行われる演算は、前記図８に示すように、固定小数点変換部８００、座標演算部８１０及び浮動小数点変換部８２０よりなる演算装置により行われる。前記固定小数点変換部８００は、浮動小数点を固定小数点に変換する。前記座標演算部８１０は、固定小数点変換部８００で変換された固定小数点を利用して座標変換する。前記浮動小数点変換部８２０は、前記座標演算部８１０で座標変換して演算した結果を浮動小数点の表現に変える。
【００３５】
前記深さテスト部６２０は、前記ワーピング部６１０で生成された複数のワーピング画像を構成する画素について画素別に深さテストを行って最終カラーデータを得る。図９は、前記深さテスト部の構成を示すブロック図であり、前面深さバッファ９００、背面深さバッファ９１０、深さ値比較部９２０、更新部９３０、前面カラーバッファ９４０及び背面カラーバッファ９５０から主として構成されている。
【００３６】
前記前面深さバッファ９００は、最初の参照画像についてワーピングを行って生成された深さ値を保存する。前記前面カラーバッファ９４０は、最初の参照画像についてワーピングを行って生成されたカラー値を保存する。前記背面深さバッファ９１０は、第２の参照画像についてワーピングを行って生成された深さ値を保存する。背面カラーバッファ９５０は、第２の参照画像についてワーピングを行って生成されたカラー値を保存する。前記深さ比較部９２０は、前記前面深さバッファに保存された深さ値と背面深さバッファに保存された深さ値とを比較する。前記更新部９３０は、前記比較結果、前面深さバッファの値が背面深さバッファ値より小さい場合、前面深さバッファ値及び前面カラーバッファの値をそのまま置き、前面深さバッファの値が背面深さバッファの値より大きいければ、前面深さバッファの値及び前面カラーバッファの値を背面深さバッファの値及び背面カラーバッファの値に更新し、それをあらゆる参照画像について反復して行う。
【００３７】
前記スプラット部６３０は、所定の視点から３次元客体までの距離によってスプラットサイズを適応調節し、スプラットサイズ設定部１０００及び適応的スプラット部１０５０を具備する。前記スプラットサイズ設定部１０００は、基準画像の解像度と目的画像の解像度とを比較して初期スプラットサイズを定める。前記適応的スプラット部１０５０は、初期スプラットサイズをズームイン／ズームアウト時の拡大／縮少比率に合わせて変更し、目的画像を生成する。
【００３８】
前記視覚化部６４０は、前記深さデータ及びカラーデータ及び大きさが調節されたスプラットを利用して３次元客体を視覚化する。
【００３９】
図１１は、深さ画像基盤の３次元グラフィックデータのうちシンプルテクスチャーデータの高速視覚化装置の動作を示すフローチャートであり、図１１を参照してシンプルテクスチャーデータの高速視覚化装置の動作を説明する。
【００４０】
まず、「ワーピング」を簡略に説明すれば、基準視点について表現された参照画像を任意の視点での参照画像に変換する画像処理技法をいう。
【００４１】
ＭｃＭｉｌｌａｎが開発した既存の３次元ワーピングアルゴリズムは、ただ１枚の参照画像から新たなビューでの視覚化された３次元客体データを生成する方法である（非特許文献３参照）。本発明の対象となるシンプルテクスチャーは、３次元客体データを表現するためにＮ枚の参照画像を利用する。したがって、既存のＭｃＭｉｌｌａｎアルゴリズムを直接利用できない。そこで本発明では、Ｎ枚の参照画像からワーピングして３次元客体データを生成し、画像を形成する方法を提案する。ここで、前記参照画像は、１対のカラー画像及び深さ画像で表現される。したがって、まず、シンプルテクスチャーデータメモリ割り当て部６００で、シンプルテクスチャーデータをメモリに割り当てる（１１００段階）。
【００４２】
次いで、ワーピング部６１０でワーピングを行ってワーピング画像を生成する（１１１０段階）。それをさらに詳細に説明すれば次の通りである。１枚の参照画像についてワーピングを行えば、それに相応する深さ情報及びカラー情報を持つ画像が生成される。もちろん、この場合、ＭｃＭｉｌｌａｎのアルゴリズムによって深さテストは行わず、常に深さバッファ及びカラーバッファに記録する。
【００４３】
前記ＭｃＭｉｌｌａｎアルゴリズムを利用してＮ枚に反復してワーピングを適用する。しかし、このようにＭｃＭｉｌｌａｎアルゴリズムを利用してＮ枚に反復してワーピングを適用すると、Ｎ枚それぞれについてはワーピングにより深さ値を決定できるが、Ｎ枚の参照画像相互間のワーピングによる深さ相互間の前後関係は不明である。そのため、本発明において、深さテスト部６２０は、参照画像相互間に深さデータの遠近関係を決定するための深さテストを行う（１１２０段階）。そして、最終的に視覚化された３次元客体データの任意の位置でのピクセルのカラー値は、Ｎ枚の参照画像を各々ワーピングして、その結果生成されたＮ個の深さデータのうち視点に最も近い深さを持つ深さデータに対応するカラー値となる。そして、視覚化部６４０で前記カラー値を画面に表す。
【００４４】
ここで、Ｎ個の深さ値のうちどれが視点に最も近い深さ値であるを調べる方法は次の通りである。
まず、第１の参照画像についてワーピングを行って生成された深さ値及びカラー値を、前面深さバッファ９００及び前面カラーバッファ９４０に各々保存する。第２の参照画像についても、ワーピングを行った後、その結果値を背面深さバッファ９１０及び背面カラーバッファ９５０に保存する。
【００４５】
次いで、前記背面深さバッファ９１０及び前面深さバッファ９００に保存された深さ値を、深さ値比較部９２０で互いに比較する。背面深さバッファ９１０に保存された深さ値が前面深さバッファ９００に保存された深さ値より小さい場合には、更新部９３０は、背面カラーバッファ９５０の該当ピクセル位置のカラー値で、前面カラーバッファ９４０の該当ピクセル位置のカラー値を取り替える。背面深さバッファの深さ値が前面深さバッファの深さ値より大きい場合には、カラーバッファを変更しない。前記のような過程を第２の参照画像からＮ番目参照画像まで行えば、常に視点から見られる面のみを画面に表すことができる。
【００４６】
一方、前記過程を行うに必要な計算量を減らすために次のような過程を経る。前記過程は、Ｎ枚の参照画像についていずれもワーピングを行ったが、本過程は、ユーザー相互作用による任意の視線ベクトルと参照画像の法線ベクトルとがなす角度が所定の角度以上になった場合には、該当参照画像はワーピングの対象として考慮しない。例えば、任意の視点と参照画像とが互いに正反対方向に位置していれば、前記角度は１８０°になり、このようになった場合には、正反対方向にある参照画像についてはワーピングを行わない。このような方法で計算量を減らして、結局視覚化速度を向上させることが可能となる。
【００４７】
以下、前述したワーピング方法が、従来の深さバッファを使用した方法より深さテストの数をどれだけ減らすことができるかについて述べる。参照画像の解像度をＩR＊ＪRと仮定し、新たなビューの画像についての解像度をＩN＊ＪNと仮定する。そして、平均して参照画像の１／２が背景でない客体領域と仮定する。
【００４８】
この時、従来の深さバッファを使用する方法は、一つの参照画像を構成しているピクセル数が１／２＊ＩR＊ＪRとなり、前記各ピクセルについて深さテストを行う。そして、従来方法では、それをＮ枚の参照画像について深さテストを行わねばならない。そのため、結局Ｎ＊１／２＊ＩR＊ＪR回の深さテストを行うようになる。これに対して、本発明のようにワーピング技法を利用すれば、一つのビュー画像を構成しているピクセル数はＩN＊ＪNとなり、Ｎ枚の参照画像についての深さテストは（Ｎ−１）＊１／２＊（ＩN＊ＪN）回ですむ。
【００４９】
画像の解像度は、参照画像数Ｎより非常に大きい値であるのが一般的であるので、結局深さテストの実行回数は（ＩR＊ＪR）と（ＩN＊ＪN）値と近似している。したがって、本発明によるワーピング技法の深さテストの回数は一定なので、参照画像の解像度が新たなビュー画像の解像度より大きければ大きいほど、深さテストの回数は相対的に少なくなる。
【００５０】
図１６は、Ｎ＝６、ＩR＝ＪR、ＩN＝ＪNである場合を仮定した場合の、深さテストの回数をグラフで図示したものである。図１６のグラフに示すように、本発明による方法は、入力（参照）画像の解像度に関係なく出力（目的）画像の解像度に依存している。ところが、大部分の３次元アプリケーションでは、３次元物体を視覚化する時に拡大／縮少などの視点変化が頻繁に起きるため、３次元物体や場面を最大限精巧に視覚化するために高解像度の入力画像が必要である。したがって、このような場合、本発明による方法は、高解像度の入力画像について深さテストを行う従来の方法より少ない計算量で高品質のレンダリングが可能であるという長所を有している。
【００５１】
一般的に浮動小数点演算は、固定小数点演算に比べてさらに正確な演算が可能であるが、固定小数点演算の数十倍以上のＣＰＵクロック数を必要とする。特にＰＤＡまたは携帯電話のような移動端末機に採用されるＣＰＵは浮動小数点演算を支援していない場合が多い。ところが、３次元グラフィックス視覚化に必要な大部分の演算は浮動小数点演算を必要とするので、このような浮動小数点演算を支援していない環境では高速視覚化が難しいという制限がある。これに対して、本発明では、移動端末機を含む多様な環境で画像基盤モデルの高速視覚化を可能にするために、視覚化アルゴリズムの主要部分の浮動小数点演算を固定小数点演算化し、視覚化アルゴリズムの主要部分の演算を固定小数点演算により実行するので、視覚化速度を向上させる。さらに視覚化アルゴリズムの主要部分の浮動小数点演算を固定小数点演算化は、ＣＰＵの負荷を軽減するので、消費電力を抑えるという効果もある
【００５２】
固定小数点加算及び乗算よりなる固定小数点算術演算を行う間、オーバーフローを避ける必要がある。したがって、要求される精密度だけでなく同時に行われる加算及び乗算の回数を考慮して、固定小数点データフォーマットは注意して設計せねばならない。このような点を考慮して最悪の場合におけるビット割り当て方法を分析すれば、次の通りである。
【００５３】
一般的に３次元幾何パイプラインでのアフィン（ａｆｆｉｎｅ）変換は、次のようなフォーマットを持つ。
【００５４】
【数１】
2005228320.tif 000003
【００５５】
本発明による方法では、Ｒ行列はスケーリングなしに回転のみ表し、Ｔベクトルは変換を表す。Ｒ行列が回転を表し、単位立方体積内の客体を正規化するために、Ｒ及びＴの各構成要素の値は−１と１の間にある。
【００５６】
ここで、Ｍ．Ｎフォーマットが固定小数点数のために使われると仮定する。演算子の絶対値は１以下であるため、０ビットが整数パートに割り当てられる。すなわち、１．Ｎフォーマットが使われる。ここで、Ｎの最大値を探す。かかるフォーマットを持つ２つの値が乗算されかつ保存される場合には、オーバーフローを避けるために符号ビットを除いて２Ｎビットが必要である。同様に、２つの値が加算されかつ保存される場合には、Ｎ＋１ビットが必要である。
【００５７】
数式１により表現される３次元アフィン変換では、オペランド（operand)の間の乗算回数は略２倍に制限される。一方、同時に行われる加算の回数は３となる。この場合に、結果を保存するためのメモリ空間は２Ｎ＋３ビットである。ここで、付加的な符号ビットを考慮すると、２（Ｎ＋２）ビットが必要である。
【００５８】
全体的な結果を整数フォーマットにより表現する必要があるので、２（Ｎ＋２）は整数フォーマットでのビット数より少なくなければならない。本発明による方法で３２ビット整数が使われる。したがって、Ｎの最大値、すなわち、Ｎmaxは１４である。この場合に、精度(precision)は２-14（６×１０-5）であり、十分に小さい値である。
【００５９】
アフィン変換前に、各座標値は、固定小数点変換部８００で２Nmaxが乗算されて固定小数点数に変換される。次いで、３次元ワーピングを行うために座標変換部８１０で、固定小数点算術演算を使用して座標変換が行われる。前述したように、オーバーフローはその場合には発生しない。３次元ワーピングを行った後、最終座標値は浮動小数点変換部８２０で、整数結果を２Nmaxで割って浮動小数点数に変換することによって得られる。
【００６０】
固定小数点算術演算が適用された部分は、視覚化過程中にシンプルテクスチャーが定義された基準座標系での各座標を目座標系に変えるワーピング部６１０である。
【００６１】
次に、本発明の一実施形態によると、スプラットサイズを適応決定するが、以下にこれを説明する。前記１１２０段階で深さテストを行い、次いで、全ての参照画像について前記ワーピング及び深さテストが行われたかを検査する（１１３０段階）。全ての参照画像についててワーピング及び深さテストが行われていた場合、直ちに視覚化（１１５０段階）できるが、本発明の実施例ではスプラットサイズを調節することが望ましい（１１４０段階）。画像基盤視覚化は、三角形を視覚化の要素として利用する従来の技法とは違って、３次元空間の点自体を、特定形状及び大きさを持つスプラットとして画像にスプラッティングすることで視覚化を行う。ユーザーの視点変化によってズームインまたはズームアウトが頻繁に発生するが、この時、均一なサイズのスプラットを利用する場合、ズームインの場合には穴が発生し、ズームアウトの場合には非常に粗い形態の低品質の視覚化が行われる。一方、それを補完するために、初期３次元画像モデルの点の密度と視点とモデルまでの距離及び視線角度を利用して最適のスプラットサイズを計算できるが、これは非常に複雑な計算を必要とし、したがって高速の視覚化には適していない。
【００６２】
したがって、本発明の一実施形態では直交投影の特徴を利用してズームイン及びズームアウトに対して適応的サイズのスプラットを少ない計算で具現する方法を提案する。本発明による方法は、２段階に分けられる。第１段階では、スプラットサイズ設定部１００で、基準画像の解像度と目的画像の解像度とを比較して、初期スプラットサイズを定める。第２段階では、適応的スプラット部１５００で、初期スプラットサイズをズームイン／ズームアウト時の拡大／縮少比率に合わせて変更して、目的画像を生成する。各段階の細部説明は次の通りである。
【００６３】
第１段階の目的は、穴のない初期ビューを生成することである。目的画像の解像度が基準画像の解像度と同一またはそれより小さい場合には、スプラットサイズを１と設定し、目的画像の解像度が基準画像の解像度より大きい場合には、横／縦の拡大比率の平均値としてスプラットサイズを設定して初期ビューを生成する。このように生成された初期ビューは穴を持っていない。
【００６４】
第２段階は、直交投影の特徴を利用する。すなわち、射影投影である場合には、物体へ／物体から視点が近づく／遠ざかる比率と、目的画像に投影される物体の拡大／縮少比率とが相異なるが、直交画像はその比率が同一である。したがって、投影された画像での座標を、その比率と同一に拡大／縮少すれば、ズームイン／ズームアウトが具現される。そして、この過程の実際具現は、物体の３次元座標を同一割合で拡大／縮少させることによって拡大／縮少を１回だけで行うようになる。本発明では、その比率を利用してスプラットサイズを拡大／縮少させることによって、ズームイン時に適応的に穴の生成を防止し、ズームアウト時にも非常に粗い形態の低品質の視覚化を避けることができる。
【００６５】
一方、本発明では視覚化の速度を高めるために、基準画像で背景データ除去技法を使用する。一般的に、基準画像の一部分だけが客体データとして利用され、残りは背景データとして意味のない部分を構成している。これは、図１７によく現れている。本発明では、３次元ワーピングのためのメモリ割り当て及びワーピング自体でこのような背景データを除外して、メモリ使用量を減らしつつ視覚化速度を向上させる。
【００６６】
参照画像を保存する際に、客体を含む最小サイズの四角形の外側に存在する背景データを除外した後、参照画像を保存してメモリ使用量を減らしつつ視覚化速度を向上させる。また、参照画像を保存する過程で、客体を含む最小サイズの四角形の外側に存在する背景データを除外して保存し、メモリ使用量をさらに減らしつつ視覚化速度を向上させる。
【００６７】
次いで、ポイントテクスチャー視覚化について説明する。図１２は、本発明による深さ画像基盤の３次元グラフィックデータのうちポイントテクスチャーデータの高速視覚化装置の一実施例についての構成を示すブロック図であり、ポイントテクスチャー初期化部１２００、ワーピング順序決定部１２１０、ポイントテクスチャースプラット部１２２０及びポイントテクスチャー視覚化部１２３０から主として構成されている。
【００６８】
前記ポイントテクスチャー初期化部１２００は、３次元客体をポイントテクスチャーデータとして生成する。
【００６９】
前記ワーピング順序決定部１２１０は、所定の視点で前記ポイントテクスチャーの参照画像について、エピポーラ点の位置及び深さ座標値の符号によってピクセルを描くワーピング順序を決定する。ＭｃＭｉｌｌａｎのワーピング方法と違って、ここでは直交投影の特性を考慮するため、エピポーラ点の深さ座標値の符号によってそのワーピング順序が変わらない。前記参照画像は、客体を含む最小サイズの四角形の外側に存在する背景データを除外する。前記ワーピング順序決定部１２１０は、視点が変わる時は座標変換部１２をさらに具備することが望ましい。前記座標変換部１２は、視点が変われば、前記ポイントテクスチャーが定義された基準座標系での各座標を目座標系に座標変換する。前記座標変換部１２は、前述したシンプルテクスチャーの座標変換部７１０と同一であり、図１４に示すように、浮動小数点を固定小数点に変換する固定小数点変換部１４００、変換された固定小数点を利用して座標変換する座標演算部１４１０及び、前記演算結果を浮動小数点表現に変える浮動小数点変換部１４２０から主として構成されている。
【００７０】
前記ポイントテクスチャースプラット部１２２０は、所定の視点から３次元客体までの距離によってスプラットサイズを適応的に調節する。前記ポイントテクスチャースプラット部１２２０は、前記シンプルテクスチャーのスプラット部６３０と、その機能及び構成が同一である。
【００７１】
前記ポイントテクスチャー視覚化部１２３０は、前記ワーピング順序及びサイズが調節されたスプラットを利用して３次元客体を視覚化する。
【００７２】
一方、前記ポイントテクスチャー初期化部１２００は、８進ツリー構造で表現された３次元客体データをポイントテクスチャーデータに変換することもある。図１３は、８進ツリー構造で表現された３次元客体データをポイントテクスチャーデータに変換するための前記ポイントテクスチャー初期化部１２００の構成を、８進ツリー構造についてのブロック図として再図示したものであり、８進ツリー復号化部１３００、深さ値計算部１３１０及びカラー値生成部１３２０から主として構成されている。
【００７３】
一方、前記８進ツリー復号化部１３００は、８進ツリー構造で表現された３次元客体データを復号化する。前記深さ値計算部１３１０は、前記復号化された８進ツリーを含む六面体の所定面を基準面として前記基準面の垂直方向に、基準面の特定ピクセル位置に前記８進ツリーの体積素を投影して、前記体積素から、前記基準面に投影された体積素の基準面上のピクセルまでの距離を深さ値とする。前記カラー値生成部１３２０は、前記体積素の色相をカラー値と表示する。
【００７４】
図１５は、本発明による深さ画像基盤の３次元グラフィックデータのうちポイントテクスチャー高速視覚化装置の一実施例の動作を示すフローチャートであり、図１５を参照して本発明の動作を説明する。
【００７５】
３次元グラフィック客体を高速で視覚化するためには、少ないメモリ使用量及び少ない演算量を具現できるデータ構造が必要である。既存の多角形で表現されたモデルは、表現が遅くて多くのメモリを必要とするために、移動端末機のような機器で実写のような高解像度の画像を示すための方法としては決して適していない。これと違って、ポイントテクスチャーは、格子形態の画像構造を持ちつつも客体の表面３次元座標情報をいずれも持っているために、少ない計算量で新たな視点で画像を再構成することができる。すなわち、多角形モデルでのような複雑な計算量が不要なので、性能及び容量が制限されている移動端末機器で効果的に処理が可能である。
【００７６】
まずポイントテクスチャー初期化部１２００で、３次元客体データのポイントテクスチャーデータを生成する（１５００段階）。ポイントテクスチャーの参照画像は、客体を含む最小サイズの四角形の外側に存在する背景データを除外した深さ及びカラーデータから主として構成されている。
【００７７】
ワーピング順序決定部１２１０を通じて、所定の視点で前記ポイントテクスチャーの参照画像について、エピポーラ点の位置によってピクセルを描くワーピング順序を決定する（１５１０段階）。
【００７８】
次いで、ポイントテクスチャースプラット部１２２０を通じて所定の視点から３次元客体までの距離によってスプラットサイズを適応的に調節する（１５２０段階）。前記適応的スプラットサイズの調節は、基準画像の解像度と目的画像の解像度とを比較して初期スプラットサイズを定め、初期スプラットサイズをズームイン／ズームアウト時の拡大／縮少比率に合わせて変更し、目的画像を生成することにより行われる。
【００７９】
目的画像の解像度が基準画像の解像度と同一またはそれ以下であれば、目的画像をその比率に合わせて縮少させ、スプラットサイズを１と設定し、拡大比率を利用して、ズームイン時には穴の生成を防止できるようにスプラットサイズを拡大させ、ズームアウト時には所定の視覚化品質が保持されるようにスプラットサイズを縮少させる。
【００８０】
３次元客体視覚化は、ポイントテクスチャー視覚化部１２３０で、前記ワーピング順序及び大きさが調節されたスプラットを利用することによりなされる（１５３０段階）。ポイントテクスチャーの視覚化は、Ｓｈａｄｅのアルゴリズムを利用するが、直交投影の特性を利用するために、Ｓｈａｄｅが使用したＭｃＭｉｌｌａｎのワーピングアルゴリズムとは違って、エピポーラポイントの深さ座標値の符号に関係なくエピポーラポイントを向かう方向にワーピング順序を決定する。
【００８１】
一方、前記ポイントテクスチャー初期化部１２００は、２つの選択可能なルーチンを持っている。そのうち一つは、８進ツリー構造を持つ３次元客体データをポイントテクスチャーデータに変換するものであり、他の一つは、ポイントテクスチャーその自体が変換されないことを確認するものである。図１３に８進ツリー構造で表現された３次元客体データをポイントテクスチャーデータに変換する過程を示す。
【００８２】
詳しく述べると、３次元体積素構造は、客体が存在していない空いている空間にもカラー値を付与するので、非効率的なデータ構造を持っている。階層的データ構造を具現してメモリ使用量を減らすために、一般的に体積素構造を８進ツリーに結合して３次元８進ツリーの体積素構造を利用する。しかし、このような３次元８進ツリーの体積素構造構造は、依然としてデータ量が多いために、それを高速で視覚化するためにはメモリ利用及び計算量の最適化が必要である。この時、８進ツリーの体積素構造をポイントテクスチャーに変換すれば、データが存在する領域の情報だけを保存すればよいので、データの量が減り、しかもデータ管理も容易になる。
【００８３】
図１８は、８進ツリー構造の視覚化順序を示すフローチャートである。まず、８進ツリー構造を受け入れて（１８００段階）、前記８進ツリーデータを復号化してカラー値及び位置値を捜し出す（１８１０段階）。この過程を行うことによって、８進ツリーの特定基準面を画像と見なす時、特定地点に必要な深さ情報の個数が分かり、この個数は結局、生成されたポイントテクスチャーの該当地点での階層の数となる。したがって、メモリは但しこの階層の数ほどのみ割り当てられるようになり、さらに生成されたポイントテクスチャーデータ構造に深さ値及びカラー値を保存させる（１８２０段階）。
【００８４】
８進ツリー画像の視覚化は、このようにポイントテクスチャー構造に変換した後、ポイントテクスチャー視覚化方式をそのまま利用してワーピング（１８３０段階）及びスプラッティング（１８４０段階）を行うことによって、メモリ使用量及び視覚化速度を向上させることができる。
【００８５】
一方、本発明を実際に具現した場合、その結果のデータは次の通りである。図１９に、シンプルテクスチャーで表現されたＢＯＯデータについての視覚化結果を表す。図１９Ａないし図１９Ｃに示すようにズームインを行うことによって、スプラットサイズが漸進的に増加し、なおかつ発生しうる穴を抑制することが分かる。しかし、基準画像で、１画素当り目標スクリーンには複数の画素を満たす必要があるために、平均視覚化速度は減少することが分かる。これは、図２２に示したシンプルテクスチャー基盤モデルについての定量的な視覚化結果によく現れている。
【００８６】
図２０Ａないし図２０Ｃには、ポイントテクスチャーで表現されたＦＬＯＷＥＲデータについての視覚化結果を図示した。また、図２１Ａ及び図２１Ｂには、８進ツリー画像で表現されたＡＮＧＥＬデータについての視覚化結果を図示した。
【００８７】
図２２及び図２３には、種々の画像基盤モデルについての定量的な視覚化結果を図示している。モデルの種類及びスプラットサイズの変化によって視覚化速度が変わるが、ポイントテクスチャー及び８進ツリー画像の場合、秒当たり約５０万個の点を処理できる。このことは、多角形基盤視覚化で秒当たり１００万個の三角形を処理することと同じ効果を奏し、このような性能は、多角形基盤視覚化を利用しては現在まで移動機器で具現できない速度である。
【００８８】
本発明は、コンピュータ可読記録媒体にコンピュータ（情報処理機能を持つ装置をいずれも含む）可読コードとして具現することが可能である。コンピュータ可読記録媒体は、コンピュータシステムによって読み取られうるデータが保存されるあらゆる種類の記録装置を含む。コンピュータ可読記録装置の例には、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピーディスク、光データ保存装置などがある。
【００８９】
本発明を、図面に図示された実施例を参考として説明したが、これは例示的なものに過ぎず、当業者ならばこれより多様な変形及び均等な他の実施例が可能であるという点を理解できる。したがって、本発明の真の技術的保護範囲は、特許請求の範囲の技術的思想により決まらねばならない。
【産業上の利用可能性】
【００９０】
本発明は画像基盤で表現された３次元グラフィック分野で好適に用いられる。
【図面の簡単な説明】
【００９１】
【図１】シンプルテクスチャー基盤モデルの視覚化結果を示す図面である。
【図２】１次元に図式化されたポイントテクスチャーの一例を示す図面である。
【図３】Ａ、Ｂは、２次元の４進ツリーで図式化された８進ツリー画像の一例を示す図面である。
【図４】新たな視点が参照画像に投影される地点であるエピポーラ点を探す一例を示す図面である。
【図５】エピポーラ点が属することができる９つの領域と、領域５に属する場合、ｚ座標の符号によって参照画像のピクセル訪問順序が変わることを示す図面である。
【図６】本発明による深さ画像基盤の３次元グラフィックデータの高速視覚化装置についての構成を示すブロック図である。
【図７】ワーピング部の細部構成を示すブロック図である。
【図８】座標変換部の細部構成を示すブロック図である。
【図９】本発明の実施例による深さテスト部の構成を示すブロック図である。
【図１０】スプラット部の細部構成を示すブロック図である。
【図１１】深さ画像基盤の３次元グラフィックデータのうちシンプルテクスチャーデータの高速視覚化装置の動作を示すフローチャートである。
【図１２】本発明による深さ画像基盤の３次元グラフィックデータのうち、ポイントテクスチャーデータの高速視覚化装置の構成を示すブロック図である。
【図１３】８進ツリー構造で表現された３次元客体データをポイントテクスチャーデータに変換するための、前記ポイントテクスチャー初期化部の構成を示すブロック図である。
【図１４】ポイントテクスチャーデータ高速視覚化装置の座標変換部の細部構成を示すブロック図である。
【図１５】本発明による深さ画像基盤の３次元グラフィックデータのうち、ポイントテクスチャー高速視覚化装置の動作を示すフローチャートである。
【図１６】シンプルテクスチャーで目的解像度が一定した時、既存方式と新たに考案した方式との計算量を比較したグラフである。
【図１７】背景データ除去方法を示す図面である。
【図１８】８進ツリー画像の高速視覚化方法を示すフローチャートである。
【図１９】Ａ、Ｂ、Ｃは、各々シンプルテクスチャーで表現されたＢＯＯモデルの個人情報端末上での視覚化例を示す図面である。
【図２０】Ａ、Ｂ、Ｃは、各々ポイントテクスチャーに表現されたＦＬＯＷＥＲモデルの個人情報端末上での視覚化例を示す図面である。
【図２１】Ａ、Ｂは各々８進ツリー画像で表現されたＡＮＧＥＬモデルの個人情報端末上での視覚化例を示す図面である。
【図２２】シンプルテクスチャーのいろいろなモデルについての個人情報端末上での視覚化例を示すテーブルである。
【図２３】ポイントテクスチャー、８進ツリー画像の図２０及び図２１についてのレンダリング速度を示すテーブルである。
【図２】
2005228320.tif 000004
【図３】
2005228320.tif 000005
【図４】
2005228320.tif 000006
【図５】
2005228320.tif 000007
【図６】
2005228320.tif 000008
【図７】
2005228320.tif 000009
【図８】
2005228320.tif 000010
【図９】
2005228320.tif 000011
【図１０】
2005228320.tif 000012
【図１１】
2005228320.tif 000013
【図１２】
2005228320.tif 000014
【図１３】
2005228320.tif 000015
【図１４】
2005228320.tif 000016
【図１５】
2005228320.tif 000017
【図１６】
2005228320.tif 000018
【図１７】
2005228320.tif 000019
【図１８】
2005228320.tif 000020
【図２２】
2005228320.tif 000021
【図２３】
2005228320.tif 000022
【図１】
2005228320.tif 000023
【図１９】
2005228320.tif 000024
【図２０】
2005228320.tif 000025
【図２１】
2005228320.tif 000026