(57)【要約】【課題】３次元コンピュータグラフィックスにおいて，より少ない演算量でレンダリングが可能な光線情報の生成または圧縮データの生成を実現する。【解決手段】画像光線情報設定部１０２は，３次元モデル上に分布する各３次元座標に関して，当該３次元座標から多視点画像中の画像が撮影された視点位置に向かう方向に対応した画像光線情報を設定する。また，格子点設定部１０４は，立方体の各面上に格子点を構成する３次元座標値群を設定する。圧縮データ設定部１０６は，基底データの重み付和で光線情報を近似するために，３次元モデル上に分布する各３次元座標に関して，画像光線情報設定部１０２が設定した画像光線情報に基づいて，当該立方体の重心から各格子点に向かう方向に対応した基底データの値を設定し，当該基底データに対応した重み係数を設定する。【選択図】図８
2006350678.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータグラフィックスのための，３次元モデル上に分布する３次元座標群に光線情報を対応付ける光線情報生成方法であって，
立方体の各面上に格子点を構成する３次元座標値群を設定し，その設定した格子点情報を格子点記憶手段に記憶する格子点設定ステップと，
３次元モデル上に分布する各３次元座標に関して，前記格子点記憶手段に記憶された格子点情報を用いて前記立方体の重心から各格子点に向かう方向に対応した光線情報を算出し設定する光線情報設定ステップと，
を有することを特徴とする光線情報生成方法。
【請求項２】
コンピュータグラフィックスのための，３次元モデル上に分布する３次元座標群に光線情報を対応付ける光線情報生成方法であって，
３次元モデル上に分布する各３次元座標に関して，当該３次元座標から多視点画像中の画像が撮影された視点位置に向かう方向に対応した画像光線情報を設定し，その設定した画像光線情報を画像光線情報記憶手段に記憶する画像光線情報設定ステップと，
立方体の各面上に格子点を構成する３次元座標値群を設定し，その設定した格子点情報を格子点記憶手段に記憶する格子点設定ステップと，
３次元モデル上に分布する各３次元座標に関して，前記格子点記憶手段に記憶された格子点情報を参照し，前記立方体の重心から各格子点に向かう方向に対応した光線情報を，前記画像光線情報記憶手段に記憶された画像光線情報で補間することにより算出し設定する光線情報設定ステップと，
を有することを特徴とする光線情報生成方法。
【請求項３】
コンピュータグラフィックスのための，３次元モデル上に分布する３次元座標群に光線情報を対応付け，基底データの重み付和で当該光線情報を近似するために基底データと重み係数を求めて圧縮データを生成する光線情報の圧縮データ生成方法であって，
立方体の各面上に格子点を構成する３次元座標値群を設定し，その設定した格子点情報を格子点記憶手段に記憶する格子点設定ステップと，
３次元モデル上に分布する各３次元座標に関して，前記格子点記憶手段に記憶された格子点情報を用いて前記立方体の重心から各格子点に向かう方向に対応した光線情報を算出し設定する光線情報設定ステップと，
３次元モデル上に分布する各３次元座標に関して，前記光線情報設定ステップで設定された光線情報に基づいて，前記立方体の重心から各格子点に向かう方向に対応した基底データの値を設定し，当該基底データに対応した重み係数を設定する圧縮データ設定ステップと，
を有することを特徴とする光線情報の圧縮データ生成方法。
【請求項４】
コンピュータグラフィックスのための，３次元モデル上に分布する３次元座標群に光線情報を対応付け，基底データの重み付和で当該光線情報を近似するために基底データと重み係数を求めて圧縮データを生成する光線情報の圧縮データ生成方法であって，
３次元モデル上に分布する各３次元座標に関して，当該３次元座標から多視点画像中の画像が撮影された視点位置に向かう方向に対応した画像光線情報を設定し，その設定した画像光線情報を画像光線情報記憶手段に記憶する画像光線情報設定ステップと，
立方体の各面上に格子点を構成する３次元座標値群を設定し，その設定した格子点情報を格子点記憶手段に記憶する格子点設定ステップと，
３次元モデル上に分布する各３次元座標に関して，前記画像光線情報記憶手段に記憶された画像光線情報に基づいて，前記格子点記憶手段に記憶された格子点情報を参照することにより当該立方体の重心から各格子点に向かう方向に対応した基底データの値を設定し，当該基底データに対応した重み係数を設定する圧縮データ設定ステップと，
を有することを特徴とする光線情報の圧縮データ生成方法。
【請求項５】
コンピュータグラフィックスのための，３次元モデル上に分布する３次元座標群に光線情報を対応付ける光線情報生成装置であって，
立方体の各面上に格子点を構成する３次元座標値群を設定する格子点設定手段と，
前記格子点設定手段が設定した格子点情報を記憶する格子点記憶手段と，
３次元モデル上に分布する各３次元座標に関して，前記格子点記憶手段に記憶された格子点情報を用いて前記立方体の重心から各格子点に向かう方向に対応した光線情報を算出し設定する光線情報設定手段と，
を備えることを特徴とする光線情報生成装置。
【請求項６】
コンピュータグラフィックスのための，３次元モデル上に分布する３次元座標群に光線情報を対応付ける光線情報生成装置であって，
３次元モデル上に分布する各３次元座標に関して，当該３次元座標から多視点画像中の画像が撮影された視点位置に向かう方向に対応した画像光線情報を設定する画像光線情報設定手段と，
前記画像光線情報設定手段が設定した画像光線情報を記憶する画像光線情報記憶手段と，
立方体の各面上に格子点を構成する３次元座標値群を設定する格子点設定手段と，
前記格子点設定手段が設定した格子点情報を記憶する格子点記憶手段と，
３次元モデル上に分布する各３次元座標に関して，前記格子点記憶手段に記憶された格子点情報を参照し，前記立方体の重心から各格子点に向かう方向に対応した光線情報を，前記画像光線情報記憶手段に記憶された画像光線情報で補間することにより算出し設定する光線情報設定手段と，
を備えることを特徴とする光線情報生成装置。
【請求項７】
コンピュータグラフィックスのための，３次元モデル上に分布する３次元座標群に光線情報を対応付け，基底データの重み付和で当該光線情報を近似するために基底データと重み係数を求めて圧縮データを生成する光線情報の圧縮データ生成装置であって，
立方体の各面上に格子点を構成する３次元座標値群を設定する格子点設定手段と，
前記格子点設定手段が設定した格子点情報を記憶する格子点記憶手段と，
３次元モデル上に分布する各３次元座標に関して，前記格子点記憶手段に記憶された格子点情報を用いて前記立方体の重心から各格子点に向かう方向に対応した光線情報を算出し設定する光線情報設定手段と，
３次元モデル上に分布する各３次元座標に関して，前記光線情報設定手段により設定された光線情報に基づいて，前記立方体の重心から各格子点に向かう方向に対応した基底データの値を設定し，当該基底データに対応した重み係数を設定する圧縮データ設定手段と，
を備えることを特徴とする光線情報の圧縮データ生成装置。
【請求項８】
コンピュータグラフィックスのための，３次元モデル上に分布する３次元座標群に光線情報を対応付け，基底データの重み付和で当該光線情報を近似するために基底データと重み係数を求めて圧縮データを生成する光線情報の圧縮データ生成装置であって，
３次元モデル上に分布する各３次元座標に関して，当該３次元座標から多視点画像中の画像が撮影された視点位置に向かう方向に対応した画像光線情報を設定する画像光線情報設定手段と，
前記画像光線情報設定手段が設定した画像光線情報を記憶する画像光線情報記憶手段と，
立方体の各面上に格子点を構成する３次元座標値群を設定する格子点設定手段と，
前記格子点設定手段が設定した格子点情報を記憶する格子点記憶手段と，
３次元モデル上に分布する各３次元座標に関して，前記画像光線情報記憶手段に記憶された画像光線情報に基づいて，前記格子点記憶手段に記憶された格子点情報を参照することにより当該立方体の重心から各格子点に向かう方向に対応した基底データの値を設定し，当該基底データに対応した重み係数を設定する圧縮データ設定手段と，
を備えることを特徴とする光線情報の圧縮データ生成装置。
【請求項９】
請求項１または請求項２記載の光線情報生成方法をコンピュータに実行させるための光線情報生成プログラム。
【請求項１０】
請求項３または請求項４記載の光線情報の圧縮データ生成方法をコンピュータに実行させるための光線情報の圧縮データ生成プログラム。
【請求項１１】
請求項１または請求項２記載の光線情報生成方法をコンピュータに実行させるための光線情報生成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１２】
請求項３または請求項４記載の光線情報の圧縮データ生成方法をコンピュータに実行させるための光線情報の圧縮データ生成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，３次元コンピュータグラフィックスにおいて用いる光線情報の生成，およびその圧縮データの生成に関するものである。
【背景技術】
【０００２】
３次元コンピュータグラフィックスの技術分野において，３次元モデルを利用して任意視点画像を作成する技術がある。この技術では，予め何らかの実物体を様々な視点から撮影した画像から，その実物体の形状を近似した３次元モデルに“光線情報”を対応付けておき，レンダリング時には３次元モデルと光線情報を利用して任意視点画像を作成する。ここで，光線情報とは，３次元モデル上のある位置において，ある方向に放たれる光線の色情報（例えばＲＧＢ強度）を表す。
【０００３】
光線情報の概念図を図１に示す。光線情報を対応付ける点（３次元座標）を３次元モデル上に一様に多数定義しておき，それらの各点において多方向の光線情報を取得しておけば，任意視点画像を作成することが可能である。このように，３次元モデルに対応付けられた光線情報の集合体を，Surface Light Fields（以下，ＳＬＦ）と呼ぶ。
【０００４】
ＳＬＦが得られれば任意視点画像を生成できるが，データ量が膨大であるため，データ圧縮が必要となる。下記の非特許文献１の圧縮手法では，任意視点画像を生成する際に，仮想カメラの視点位置・視線方向が指定されたときにＳＬＦを完全に復元せずに，圧縮データから任意視点画像を生成することができる。従い，レンダリング時にメモリの利用量が非常に小さい。
【０００５】
この手法では，次のような方法で圧縮データを生成する。まず，３次元モデル上の各サンプリング点において，多視点画像のうち当該サンプリング点が可視である画像において当該サンプリング点がとる色を求める。これにより，３次元モデル上の各サンプリング点において複数の色データが対応付けられることになる。ここでは，これらの色データを“画像光線情報”と呼ぶこととする。そして，次のようなメッシュを考える。
【０００６】
光線情報の方向を定義する球を生成する際に考えた正八面体の各エッジを２つのエッジに分割して頂点を一つ挿入し，図２に示してあるように３角形を４つのより小さな３角形に分割するようにエッジで他の頂点と連結する。このような処理を繰り返して作成したメッシュを方向メッシュと呼ぶこととする。そして，方向メッシュの中心から各頂点に向かう方向に関する光線情報を考え，この光線情報群をＳＬＦとする。ここで，ｉ番目のサンプリング点に対応した光線情報群をＬ（ｉ，ｊ），ｊ＝０，１，... ，Ｊ−１（球の頂点の数がＪ個あることを示している）と表すとする。この手法では，次式のような近似を考える。
【０００７】
【数１】
2006350678.tif 000003
ここで，ｖk,j を“基底”と呼び，ｓk,i を“重み係数”と呼ぶこととする。この手法では，少ないデータ量で近似を行えるように基底と重み係数を与える。少ないデータ量で近似を行えるようにということは，（１）式におけるＫを小さい値で抑えるようにということと等価である。基底と重み係数の導出は画像光線情報を用いて行われ，その導出方法は様々な方法が考えられるが，非特許文献１では，Principle function analysis という方法を提案している。
【０００８】
次に，非特許文献１に記載の手法における任意視点画像生成法について説明する。まず，仮想カメラにおける画像平面上の各ピクセルに入射する光線が発せられる３次元モデル上の位置および当該光線の方向が求められる。ここで，仮想平面上のあるピクセルに入射する光線が発せられる３次元モデル上の位置に，最も近い３次元モデル上のサンプリング点をｉとしたとき，当該ピクセルにはサンプリング点ｉに関する光線情報に基づいた補間値が与えられる。これは次の補間方法によって計算される。
【０００９】
当該ピクセルに入射する光線の方向ベクトルが，方向メッシュと交差する点をａと表す。ここで，点ａが含まれる方向メッシュの３角形の頂点をｗ0 ，ｗ1 ，ｗ2 とし，この３角形におけるａの前記の頂点に関する重心座標をｂ0 ，ｂ1 ，ｂ2 とし，前記の頂点に対応した（１）式のｋ番目の基底の値をｖk,j0，ｖk,j1，ｖk,j2と表す。そうすると，点ａに対応した値（つまり，当該ピクセルに与えられる値）ｖ′k は次式で計算される。
【００１０】
【数２】
2006350678.tif 000004
そして，当該ピクセルの値ｐは次式で計算される。
【００１１】
【数３】
2006350678.tif 000005
これらの（２）式，（３）式から明らかなように，上記の計算は３次元モデル上のサンプリング点ｉにおける方向メッシュの頂点ｗ0 ，ｗ1 ，ｗ2 に対応した光線情報に重心座標ｂ0 ，ｂ1 ，ｂ2 で重み付けして補間していることと等価である。なお，上記の計算において，点ａが含まれる方向メッシュの３角形を求める方法は非特許文献１に記載されていないが，点ａがある正八面体の面上で各３角形に関する内外判定を行う方法が容易に類推できる。
【００１２】
また，上記の任意視点画像の生成法は，ＳＬＦを圧縮しない場合にも応用できる。この場合は，方向メッシュ上で基底の値の補間を行うのでなく，光線情報そのものを補間することになる。
【００１３】
なお，以下では，上記のように３次元モデル上のあるサンプリング点においてある方向に向かう光線の値を求めるために，補間に利用する基底データの値（上記の説明では，ｖk,j0，ｖk,j1，ｖk,j2）もしくは光線情報の値（上記の説明では，重心座標ｂ0 ，ｂ1 ，ｂ2 ）を決定し，さらに補間で利用する重みも決定し，補間するプロセス全体を“光線方向上の補間”と呼ぶこととする。
【００１４】
また，光線方向のうち，３次元モデルの内側に向かう光線方向については，当該光線方向の光線情報は任意視点画像の生成に利用されない。従い，（１）式の基底と重み係数を求める際に，３次元モデルの外側に向かう光線方向についてのみ近似誤差を最小化するような主成分分析法を利用することで，任意視点画像の品質を向上させることが可能である。そのような主成分分析法としては，例えば非特許文献２の方法がある。
【非特許文献１】D.Wood et. al.，“Surface Light Fields for 3D Photography ”，SIGGRAPH 2000 Conference Proceedings，pp.287-296，2000.
【非特許文献２】B.Grung et. al.，“Missing values in principal component analysis”，Chemometrics and Intelligent Laboratory Systems ，pp.125-139，1998.
【発明の開示】
【発明が解決しようとする課題】
【００１５】
非特許文献１に記載の従来の圧縮データ生成方法によれば，メモリ利用量を小さく抑えながら高品質な任意視点画像を生成できる。
【００１６】
しかしながら，従来の圧縮データ生成方法では，正八面体を再帰分割した頂点に対応した方向に基底データを与えていたため，基底データを用いた補間の計算量が膨大であり，レンダリングに多大な時間を要するという問題があった。
【００１７】
基底データを用いた補間の計算量プロセスの中で，特に仮想カメラの各ピクセルに入射する光線の方向ベクトルが，方向メッシュ上と交差する点（点ａとする）が含まれる方向メッシュ上の３角形を求めるための内外判定計算の計算量が大きい。内外判定の計算には，通常は各３角形での外積ベクトルのノルム計算が行われる。
【００１８】
具体的には，頂点ｗ0 ，ｗ1 ，ｗ2 で構成される，ある３角形に点ａが含まれるか判定するためには，最悪のケースで４回（最低でも２回）の３次元ベクトル間の外積計算が必要となる。ある３角形の任意の２つの辺の外積ベクトルのノルムは当該３角形の面積と等価である。従い，頂点ｗ0 ，ｗ1 ，ｗ2 で構成される３角形の面積と，点ａと当該３角形を構成する２つの頂点で構成される３角形の面積の総和を比較して，後者が前者を超えた場合は点ａは当該３角形に含まれないことになる。方向メッシュの３角形の面積は全て同じなので，一つの３角形に関する判定には最低で１回の外積計算を要し，１回の外積計算とノルム計算に１４回の積和演算が必要になる。
【００１９】
３角形に点ａが含まれないことを判定するのに一回の外積計算しか生じない理想的なケースを想定すると，正八面体である方向メッシュの一つの面の３角形の数がＴであった場合，４２回（一つ目の３角形に点ａが含まれた場合）から１４（Ｔ−１）回の積和演算が必要になる。補間値の計算をも含めた場合の計算量は４５回から１４（Ｔ−１）＋４７回となる。
【００２０】
なお，ＳＬＦを圧縮しない場合においても，方向メッシュ上での光線情報の補間を行う処理は同様なので，同じ課題を有する。
【００２１】
本発明は，上記の課題に鑑み創作されたものであり，本発明の目的は，より少ない演算量でレンダリングが可能な光線情報の生成および圧縮データ生成方法を提供することである。
【課題を解決するための手段】
【００２２】
上記の課題を解決するため，第１の発明は，コンピュータグラフィックスのための，３次元モデル上に分布する３次元座標群に光線情報を対応付ける光線情報生成方法であって，立方体の各面上に格子点を構成する３次元座標値群を設定し，その設定した格子点情報を格子点記憶手段に記憶する格子点設定ステップと，３次元モデル上に分布する各３次元座標に関して，前記格子点記憶手段に記憶された格子点情報を用いて前記立方体の重心から各格子点に向かう方向に対応した光線情報を算出し設定する光線情報設定ステップとを有することを特徴とする。
【００２３】
また，第２の発明は，コンピュータグラフィックスのための，３次元モデル上に分布する３次元座標群に光線情報を対応付ける光線情報生成方法であって，３次元モデル上に分布する各３次元座標に関して，当該３次元座標から多視点画像中の画像が撮影された視点位置に向かう方向に対応した画像光線情報を設定し，その設定した画像光線情報を画像光線情報記憶手段に記憶する画像光線情報設定ステップと，立方体の各面上に格子点を構成する３次元座標値群を設定し，その設定した格子点情報を格子点記憶手段に記憶する格子点設定ステップと，３次元モデル上に分布する各３次元座標に関して，前記格子点記憶手段に記憶された格子点情報を参照し，前記立方体の重心から各格子点に向かう方向に対応した光線情報を，前記画像光線情報記憶手段に記憶された画像光線情報で補間することにより算出し設定する光線情報設定ステップとを有することを特徴とする。
【００２４】
また，第３の発明は，コンピュータグラフィックスのための，３次元モデル上に分布する３次元座標群に光線情報を対応付け，基底データの重み付和で当該光線情報を近似するために基底データと重み係数を求めて圧縮データを生成する光線情報の圧縮データ生成方法であって，立方体の各面上に格子点を構成する３次元座標値群を設定し，その設定した格子点情報を格子点記憶手段に記憶する格子点設定ステップと，３次元モデル上に分布する各３次元座標に関して，前記格子点記憶手段に記憶された格子点情報を用いて前記立方体の重心から各格子点に向かう方向に対応した光線情報を算出し設定する光線情報設定ステップと，３次元モデル上に分布する各３次元座標に関して，前記光線情報設定ステップで設定された光線情報に基づいて，前記立方体の重心から各格子点に向かう方向に対応した基底データの値を設定し，当該基底データに対応した重み係数を設定する圧縮データ設定ステップとを有することを特徴とする。
【００２５】
また，第４の発明は，コンピュータグラフィックスのための，３次元モデル上に分布する３次元座標群に光線情報を対応付け，基底データの重み付和で当該光線情報を近似するために基底データと重み係数を求めて圧縮データを生成する光線情報の圧縮データ生成方法であって，３次元モデル上に分布する各３次元座標に関して，当該３次元座標から多視点画像中の画像が撮影された視点位置に向かう方向に対応した画像光線情報を設定し，その設定した画像光線情報を画像光線情報記憶手段に記憶する画像光線情報設定ステップと，立方体の各面上に格子点を構成する３次元座標値群を設定し，その設定した格子点情報を格子点記憶手段に記憶する格子点設定ステップと，３次元モデル上に分布する各３次元座標に関して，前記画像光線情報記憶手段に記憶された画像光線情報に基づいて，前記格子点記憶手段に記憶された格子点情報を参照することにより当該立方体の重心から各格子点に向かう方向に対応した基底データの値を設定し，当該基底データに対応した重み係数を設定する圧縮データ設定ステップとを有することを特徴とする。
【００２６】
第１の発明および第２の発明に従って光線情報を生成すれば，任意視点画像生成の際の光線情報の方向に関する補間計算が少ない計算量で実行できる。以下に，第１の発明および第２の発明に関する詳細を説明する。
【００２７】
第１の発明では，まず，図３に示すような立方体の各面上に格子状の点を生成する。なお，ここでは説明を簡単にするため，この立方体は重心を原点とし，一辺の長さをＥとし，頂点の座標値が（Ｅ／２，Ｅ／２，Ｅ／２），（Ｅ／２，Ｅ／２，−Ｅ／２），（Ｅ／２，−Ｅ／２，Ｅ／２），（Ｅ／２，−Ｅ／２，−Ｅ／２），（−Ｅ／２，Ｅ／２，Ｅ／２），（−Ｅ／２，Ｅ／２，−Ｅ／２），（−Ｅ／２，−Ｅ／２，Ｅ／２），（−Ｅ／２，−Ｅ／２，−Ｅ／２）という値を取る。
【００２８】
格子状の点の生成法としては，２通りの方法が考えられる。図４に示されているように，この立方体のある面の４つの頂点をＣi ，ｉ＝０，１，２，３とし，Ｃ0 とＣ1 の組およびＣ2 とＣ3 の組をそれぞれある辺を構成する組であるとする（組の２つの頂点が対角線を構成しないということである）。また，縦および横の格子点の数をＲとする（一つの面に対し，Ｒ2 個の点を生成する）。
【００２９】
一つの方法では，その面上の格子点ｇ（ｖ，ｈ），ｖ＝０，１，... ，Ｒ−１，ｈ＝０，１，... ，Ｒ−１を次式で計算する。
【００３０】
【数４】
2006350678.tif 000006
この場合の格子点の概念図を図５に示す。
【００３１】
また，二つ目の方法では，その面上の格子点ｇ（ｖ，ｈ），ｖ＝０，１，... ，Ｒ−１，ｈ＝０，１，... ，Ｒ−１を次式で計算する。
【００３２】
【数５】
2006350678.tif 000007
この場合の格子点の概念図を図６に示す。
【００３３】
ここで，上記の方法で各面について計算された点を集め，それらの３次元座標をｇ（ｉ），ｉ＝０，１，... ，Ｇ−１と記述する。なお，Ｇは生成された点の総数である。式（４）に基づいて各面で計算された点は，異なる面で同じ座標を持つ点となる場合があるが，同じ座標値を持つ点は一つと数える。
【００３４】
次に，３次元モデル上の各点において，立方体の重心から各格子点に向かう方向に対応した光線情報を求める。つまり，ｇ（ｉ）を正規化したベクトルをｇ′（ｉ）としたとき，ｇ′（ｉ），ｉ＝０，１，... ，Ｇ−１の方向に関する光線情報を求める。なお，３次元モデル上の各点において，方向ｇ′（ｉ），ｉ＝０，１，... ，Ｇ−１を定義する座標系は任意である。つまり，例えば，３次元モデル上の各点で方向を定義する座標系が異なっても良い。また，光線情報を求める方法は既存の方法，もしくは既存の方法から容易に類推可能な方法のうちのいずれでも良い。
【００３５】
第２の発明では，立方体上の格子点を求めて，これらの格子点によって定義される方向について光線情報を求めるという点で第１の発明と同じである。ただし，第２の発明では，光線情報の求め方に関してより詳細である。具体的には，画像光線情報設定ステップにおいて画像光線情報を取得しておき，格子点で定義される方向に関して光線情報を求める際には画像光線情報を利用して補間する。なお，その際の補間方法については既存の方法，もしくは既存の方法から容易に類推可能な方法のうちのいずれでも良い。
【００３６】
第１および第２の発明に従って光線情報を生成すると，少ない積和演算回数で光線方向上で補間ができる。補間時の重み付け方法としては，画像処理で頻繁に利用される双一次補間を行うことになる。
【００３７】
図５の形で格子点を生成した場合の補間について説明する。仮想カメラのあるピクセルに入射する光線の方向ベクトルをｄ＝（ｄx ，ｄy ，ｄz ）とすると，この方向ベクトルが立方体と交差する点は次のように求められる。まず，（ｄx ，ｄy ，ｄz ）の中で絶対値が最大の軸をｍａｘ＿ａｘｉｓとし，ｄmax-axisの符号をｍａｘ＿ａｘｉｓ＿ｓｉｇｎとすると，交差する点はｍａｘ＿ａｘｉｓ軸に垂直でｍａｘ＿ａｘｉｓ＿ｓｉｇｎの方向にある面上にあることは自明である。そして，交差する点をａ＝（ａx ，ａy ，ａz ）と表すと，ａmax-axis＝Ｅ／２であり，ｍａｘ＿ａｘｉｓ以外の軸ａｘｉｘに関する座標値は次式で与えられることは自明である。
【００３８】
【数６】
2006350678.tif 000008
なお，双一次補間を行う場合，図７に示すように交差する点ａに隣接する４つの格子点の値を利用して補間する。この図では，点ａに隣接する４つの格子点をｇi ，ｉ＝０，１，２，３と表している。ｇi に対応する光線情報をｌ（ｉ）とすると，双一次補間による補間値ｌ＿ａは次の式で計算できる。
【００３９】
【数７】
2006350678.tif 000009
なお，双一次補間に利用する重みｗ0 ，ｗ1 は次のように計算できる。
【００４０】
【数８】
2006350678.tif 000010
ここで，ｆｌｏｏｒ（Ａ）は実数Ａの小数部分を切り捨てることを意味する。上記を踏まえて，３次元モデル上の一つのサンプリング点について，光線方向上の補間に要する積和演算回数は２０回となる（ただし，上記の式中のＥ／２と（Ｒ−１）／Ｅは，予め計算されているものとする）。
【００４１】
従って，第１の発明もしくは第２の発明の方法で光線情報を生成すれば，光線方向上の補間において，従来の技術で最も演算量がかからないケースの場合よりも積和演算回数が少ない上，光線の方向の数に依存しないことが分かる。図６の形で格子点を生成した場合も，上記とほぼ同様の計算をすることになる。
【００４２】
一方，第３の発明および第４の発明に従って光線情報を生成すれば，任意視点画像生成の際の光線情報の方向に関する補間計算が少ない計算量で実行できる。以下に第３の発明，第４の発明に関する詳細を説明する。
【００４３】
第３の発明では，まず格子点設定ステップと光線情報設定ステップがあるが，これは第１の発明の場合と同様である。圧縮データ設定ステップでは，光線情報設定ステップで求めた光線情報から，各格子点に対応する基底の値と，当該基底データに対応した重み係数を求める。
【００４４】
第４の発明は，基本的には第３の発明と同様に格子点設定ステップで求めた各格子点に対応する基底の値を求める点で同じであるが，これは画像光線情報設定ステップで求めた画像光線情報で補間を行う点で異なる。
【００４５】
なお，第３の発明，第４の発明に従って圧縮データを生成しておけば，光線方向上の補間において，第１の発明，第２の発明の場合と同様の効果があることが分かる。
【発明の効果】
【００４６】
本発明に従って光線情報もしくはその圧縮データを生成することにより，従来より少ない演算量で任意視点画像を生成できる。さらに，この演算量は従来とは異なって，光線情報の方向の数に依存しない。
【発明を実施するための最良の形態】
【００４７】
以下では，第４の発明を実現する圧縮データ生成装置の実施例を説明する。以下の実施例の説明から，上述した第１の発明を実現する光線情報生成装置，第２の発明を実現する光線情報生成装置，および第３の発明を実現する圧縮データ生成装置についても，同様に容易に実施できることは明らかである。
【００４８】
第４の発明を実現する圧縮データ生成装置の構成例を図８に示す。圧縮データ生成装置１は，データ入力部１０１，画像光線情報設定部１０２，画像光線情報記憶部１０３，格子点設定部１０４，格子点記憶部１０５，圧縮データ設定部１０６，データ出力部１０７により構成される。これらの各部は，圧縮データ生成装置１が備えるＣＰＵおよびメモリ等からなるコンピュータと，そのコンピュータを動作させるソフトウェアプログラム等によって実現される。
【００４９】
圧縮データ生成装置１の動作について説明する。動作フローを図９に示す。まず，データ入力部１０１により，多視点画像，３次元モデル，３次元モデル上に定義されたサンプリング点群の座標値，光線方向数（格子点解像度）が入力される［ステップＳ１］。ここで，光線方向数は３次元モデル上のサンプリング点一つあたりの光線方向数であり，ユーザによって人為的に与えられたものでも，多視点画像の視点数に基づいて計算された値のいずれでも良い。
【００５０】
本実施例では，立方体の面あたりの光線方向の数が同じであり，なおかつ格子の縦と横の長さが同一である場合を説明する。光線方向数を表す入力データとしては，一つの面の格子点の縦および横の数Ｒが与えられるとする。
【００５１】
次に，データ入力部１０１から格子点設定部１０４に立方体の面の縦および横の格子点の数Ｒが入力され，立方体の各面の上に格子上の点群の座標値が求められ，これらの座標値が格子点記憶部１０５に記憶される［ステップＳ２］。
【００５２】
本実施例においても前節と同様に，立方体は重心を原点とし，一辺の長さをＥとし，頂点の座標値が（Ｅ／２，Ｅ／２，Ｅ／２），（Ｅ／２，Ｅ／２，−Ｅ／２），（Ｅ／２，−Ｅ／２，Ｅ／２），（Ｅ／２，−Ｅ／２，−Ｅ／２），（−Ｅ／２，Ｅ／２，Ｅ／２），（−Ｅ／２，Ｅ／２，−Ｅ／２），（−Ｅ／２，−Ｅ／２，Ｅ／２），（−Ｅ／２，−Ｅ／２，−Ｅ／２）という値を取るものとする。従い，Ｒに基づいて（４）式もしくは（５）式により格子点群が計算される。ここで，上記の方法で各面について計算された点を集め，それらの３次元座標をｇ（ｉ），ｉ＝０，１，... ，Ｇ−１と記述する。なお，Ｇは生成された点の総数である。式（４）に基づいて各面で計算された点は，異なる面で同じ座標を持つ点となる場合があるが，同じ座標値を持つ点は一つと数える。
【００５３】
一方，データ入力部１０１から画像光線情報設定部１０２に多視点画像，３次元モデル，３次元モデル上のサンプリング点群の座標値が入力され，画像光線情報が求められ，画像光線情報記憶部１０３に記憶される［ステップＳ３］。３次元モデル上のあるサンプリング点が可視である各画像から，例えば非特許文献１にあるような方法で画像光線情報を取得する。つまり，３次元モデル上のあるサンプリング点が可視である画像がＬimg 枚であった場合，そのサンプリング点についてはＬimg 個の画像光線情報が得られることになる。
【００５４】
一方，格子点記憶部１０５から格子点群の座標値ｇ（ｉ），ｉ＝０，１，... ，Ｇ−１が，画像光線情報記憶部１０３から画像光線情報が，圧縮データ設定部１０６によって順次読み出され，３次元モデル上の各サンプリング点上における各光線サンプリング方向について，光線情報が求められ，この光線情報から基底と重み係数が求められる［ステップＳ４］。ここで，３次元モデル上のあるサンプリング点について入力されている画像光線情報をｌimg （ｉ），ｉ＝０，１，... ，Ｌimg と表し，これらの画像光線情報に対応した光線方向ベクトル（光線の方向に向かう正規ベクトルを３次元で表現したものとする）をｄ（ｉ），ｉ＝０，１，... ，Ｌimg と表す。
【００５５】
この実施例では，光線サンプリング方向に対応した光線情報として，方向ベクトル間の角度が最小の光線方向ベクトルを持つ画像光線情報の値を与えることによる補間を利用することとする。具体的には，ｇ′（ｉ）はｇ（ｉ）を正規化したものとした場合，内積ｇ′（ｉ）T ｄ（ｊ）を最大化するｄ（ｊ）に対応した画像光線情報の値を，ｇ（ｉ）に対応した光線情報とする（ベクトルは全て列ベクトルであり，Ｔはベクトルの転置を表すとする）。そして，主成分分析によって基底と重み係数が求められる。
【００５６】
最後に，圧縮データ設定部１０６からデータ出力部１０７に基底と重み係数が出力され，圧縮データ生成装置１から基底と重み係数が出力される［ステップＳ５］。
【００５７】
上記の実施例では，３次元モデルの各サンプリング点で，同じ光線方向について光線情報を取得しているが，３次元モデル上の各サンプリング点において，異なる座標系での光線方向について光線情報を取得しても良い。その一例としては，非特許文献１に記載のように，３次元モデル上の各サンプリング点における法線に依存した座標系を利用することが考えられる（これは，圧縮効率を高めるために行われている）。
【００５８】
具体的には，３次元モデル上のサンプリング点ｓ，ｓ＝０，１，２，... ，Ｓ−１（これはサンプリング点のインデックスである）における法線をｎs ，グローバル座標系の軸をＡl ，ｌ＝０，１，２としたとき，サンプリング点ｓにおける座標系の軸Ａl,s ，ｌ＝０，１，２を次式で求める。
【００５９】
【数９】
2006350678.tif 000011
そして，Ａl,s ，ｌ＝０，１，２を軸とした座標系において，ｇ（ｉ），ｉ＝０，１，... ，Ｇ−１の値を取る格子点について，光線情報を求めても良い。
【００６０】
上記の実施例では，主成分分析によって基底を求めたが，非特許文献１に記載のPrincipal function analysis によって基底を求めても良い。また，格子点に対応した光線方向のうち，３次元モデルの内側に向かう光線方向については，当該光線方向の光線情報は任意視点画像の生成に利用されない。従い，当該光線方向の光線情報を欠測値としてとらえ，非特許文献２に記載のような欠測値以外のデータに対して近似誤差を小さくするような主成分分析を利用しても良い。なお，上記の方法によって作成した圧縮データを用いたレンダリングについては，前節に記載の方法で行えば良い。
【００６１】
以上の光線情報の生成およびその圧縮データの生成に関する処理は，コンピュータとソフトウェアプログラムとによって実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも，ネットワークを通して提供することも可能である。
【図面の簡単な説明】
【００６２】
【図１】光線情報の概念図である。
【図２】方向メッシュの生成の概念図である。
【図３】格子点の設定を説明するための立方体の概念図である。
【図４】立方体上の面の概念図である。
【図５】格子点の概念図である。
【図６】格子点の概念図である。
【図７】立方体上での双一次補間の概念図である。
【図８】本発明の実施例の構成を示す図である。
【図９】本発明の実施例の動作フローを示す図である。
【符号の説明】
【００６３】
１      圧縮データ生成装置
１０１  データ入力部
１０２  画像光線情報設定部
１０３  画像光線情報記憶部
１０４  格子点設定部
１０５  格子点記憶部
１０６  圧縮データ設定部
１０７  データ出力部
【図１】
2006350678.tif 000012
【図２】
2006350678.tif 000013
【図３】
2006350678.tif 000014
【図４】
2006350678.tif 000015
【図５】
2006350678.tif 000016
【図６】
2006350678.tif 000017
【図７】
2006350678.tif 000018
【図８】
2006350678.tif 000019
【図９】
2006350678.tif 000020