(57)【要約】【課題】分離近似とベクトル量子化を用いた情報源の符号化において，圧縮誤差をより小さくして圧縮効率を向上させる。【解決手段】信号群入力部１６は，符号化対象信号群を入力信号群として入力信号群メモリ１１に記録する。選択部１３は，コードブックメモリ１２に記録されたインデックス情報が対応付けられた信号の集合から入力信号群に対する基底信号と重み係数信号を一組選択する。近似信号生成部１４は，選択された基底信号に重み係数信号の各重み係数を乗じて近似信号群を生成し，誤差信号生成部１５は，前記入力信号群の各信号と前記近似信号群の各信号の間の誤差信号群を生成する。生成した誤差信号群は，入力信号群として信号群入力部１６に入力され，同様に処理が繰り返される。インデックス符号化部１７は，選択部１３が選択した基底信号と重み係数信号に対応するインデックス情報を符号化する。【選択図】    図３
2004229100.tif 000002
【特許請求の範囲】
【請求項１】
符号化対象の，複数の信号の集合である符号化対象信号群に対して，符号化対象信号群の各々の信号を基底信号の重み付け和で近似，あるいは誤差なく表現するため，インデックス情報が対応付けられた信号の集合から基底信号と，重み係数で構成される重み係数信号を選択し，選択された基底信号と重み係数信号に対応するインデックス情報を符号化する，情報源の符号化方法であって，
符号化対象信号群または生成された誤差信号群を入力信号群とし，入力信号群に対する基底信号と重み係数信号とを一組選択する選択ステップと，
前記選択ステップで選択した基底信号に重み係数信号の各重み係数を乗じて作成される，複数の信号によって構成される近似信号群を生成する近似信号生成ステップと，
入力信号群の各信号と近似信号群の各信号間の誤差信号によって構成される誤差信号群を生成する誤差信号生成ステップとを有し，
生成された誤差信号群を入力信号群として，前記選択ステップ，前記近似信号生成ステップ，前記誤差信号生成ステップを所定の条件が満たされるまで繰り返す
ことを特徴とする情報源の符号化方法。
【請求項２】
請求項１記載の情報源の符号化方法において，
前記選択ステップでは，入力信号群の各信号と，基底信号に重み係数信号の各重み係数を乗じて作成される信号との間の二乗誤差の和を最小にするように，基底信号と重み係数信号とを一組選択する
ことを特徴とする情報源の符号化方法。
【請求項３】
符号化対象の，複数の信号の集合である符号化対象信号群に対して，符号化対象信号群の各々の信号を基底信号の重み付け和で近似，あるいは誤差なく表現するため，インデックス情報が対応付けられた信号の集合から基底信号と，重み係数で構成される重み係数信号とを選択し，選択された基底信号と重み係数信号に対応するインデックス情報を符号化する，情報源の符号化方法であって，
符号化対象信号群または生成された誤差信号群を入力信号群とし，入力信号群に対する基底信号を１つ選択する基底信号選択ステップと，
重み係数信号を，前記基底信号選択ステップで選択した基底信号に固定したもとで選択する重み係数信号選択ステップと，
前記基底信号選択ステップで選択した基底信号に，前記重み係数信号選択ステップで選択した重み係数信号の各重み係数を乗じて作成される，複数の信号によって構成される近似信号群を生成する近似信号生成ステップと，
入力信号群の各信号と近似信号群の各信号間の誤差信号によって構成される誤差信号群を生成する誤差信号生成ステップとを有し，
生成された誤差信号群を入力信号群として，前記基底信号選択ステップ，前記重み係数信号選択ステップ，前記近似信号生成ステップ，前記誤差信号生成ステップを所定の条件が満たされるまで繰り返す
ことを特徴とする情報源の符号化方法。
【請求項４】
請求項３記載の情報源の符号化方法において，
前記基底信号選択ステップでは，入力信号群の各信号と基底信号とをそれぞれベクトルとして入力信号群の各信号と基底信号の内積を計算し，これらの内積値の二乗和を最大化する基底信号を選択し，
前記重み係数信号選択ステップでは，前記基底信号選択ステップで求められた基底信号に重み係数信号の各重み係数を乗じて作成される信号と入力信号群の各信号に対する二乗誤差の和を最小にするように重み係数信号を選択する
ことを特徴とする情報源の符号化方法。
【請求項５】
請求項１から請求項４までのいずれか１項に記載の情報源の符号化方法において，
複数の符号化対象信号群を学習データとし，基底信号と重み係数信号とを選択する，インデックス情報が対応付けられた信号の集合であるコードブックを作成するための手順として，
複数の符号化対象信号群または求められた誤差信号群を入力学習データとし，入力学習データによって基底信号のコードブックと重み係数信号のコードブックとを学習する学習ステップと，
前記学習ステップで作成されたコードブックを利用して，入力学習データに含まれる各信号群に対し，請求項１または請求項２のいずれかの選択ステップ，近似信号生成ステップ，誤差信号生成ステップを，あるいは，請求項３または請求項４のいずれかの基底信号選択ステップ，重み係数信号選択ステップ，近似信号生成ステップ，誤差信号生成ステップを，順に行うことによって入力学習データに含まれる各信号群に対する誤差信号群を求める誤差学習データ生成ステップとを有し，
前記誤差学習データ生成ステップで求められた誤差信号群を入力学習データとして，前記学習ステップと前記誤差学習データ生成ステップとを所定の条件を満たすまで繰り返すことでコードブックを作成する
ことを特徴とする情報源の符号化方法。
【請求項６】
請求項１から請求項４までのいずれか１項に記載の情報源の符号化方法において，
複数の符号化対象信号群を学習データとし，基底信号と重み係数信号とを選択する，インデックス情報が対応付けられた信号の集合であるコードブックを作成するための手順として，
複数の符号化対象信号群または求められた誤差信号群を入力学習データとし，入力学習データによって基底信号のコードブックと重み係数信号のコードブックを学習する際に，入力学習データに対する平均二乗誤差を最適化の評価関数として学習する学習ステップと，
前記学習ステップで作成されたコードブックを利用して，入力学習データに含まれる各信号群に対し，請求項１または請求項２のいずれかの選択ステップ，近似信号生成ステップ，誤差信号生成ステップを，あるいは，請求項３または請求項４のいずれかの基底信号選択ステップ，重み係数信号選択ステップ，近似信号生成ステップ，誤差信号生成ステップを，順に行うことによって入力学習データに含まれる各信号群に対する誤差信号群を求める誤差学習データ生成ステップとを有し，
前記誤差学習データ生成ステップで求められた誤差信号群を入力学習データとして，前記学習ステップと前記誤差学習データ生成ステップとを所定の条件を満たすまで繰り返すことでコードブックを作成する
ことを特徴とする情報源の符号化方法。
【請求項７】
符号化対象の，複数の信号の集合である符号化対象信号群に対して，符号化対象信号群の各々の信号を基底信号の重み付け和で近似，あるいは誤差なく表現するため，インデックス情報が対応付けられた信号の集合から基底信号と，重み係数で構成される重み係数信号とを選択し，選択された基底信号と重み係数信号に対応するインデックス情報を符号化する，情報源の符号化装置であって，
符号化対象信号群，あるいは後述の誤差信号生成部で生成される誤差信号群を入力信号群とし，入力信号群を入力する信号群入力部と，
入力信号群を記録する入力信号群メモリと，
基底信号と重み係数信号とを選択する，信号の集合を記録するコードブックメモリと，
入力信号群に対する基底信号と重み係数信号とを一組選択する選択部と，
前記選択部で選択した基底信号に重み係数信号の各重み係数を乗じて作成される，複数の信号によって構成される近似信号群を生成する近似信号生成部と，
入力信号群の各信号と近似信号群の各信号の間の誤差信号によって構成される誤差信号群を生成する誤差信号生成部と，
前記選択部で選択された基底信号と重み係数信号に対応するインデックス情報を符号化するインデックス符号化部とを備える
ことを特徴とする情報源の符号化装置。
【請求項８】
請求項７記載の情報源の符号化装置において，
前記選択部は，入力信号群の各信号と，基底信号に重み係数信号の各重み係数を乗じて作成される信号との間の二乗誤差の和を最小にするように，基底信号と重み係数信号を一組選択する
ことを特徴とする情報源の符号化装置。
【請求項９】
符号化対象の，複数の信号の集合である符号化対象信号群に対して，符号化対象信号群の各々の信号を基底信号の重み付け和で近似，あるいは誤差なく表現するため，インデックス情報が対応付けられた信号の集合から基底信号と，重み係数で構成される重み係数信号とを選択し，選択された基底信号と重み係数信号に対応するインデックス情報を符号化する，情報源の符号化装置であって，
符号化対象信号群，あるいは後述の誤差信号生成部で生成される誤差信号群を入力信号群とし，入力信号群を入力する信号群入力部と，
入力信号群を記録する入力信号群メモリと，
基底信号と重み係数信号とを選択する，信号の集合を記録するコードブックメモリと，
入力信号群に対する基底信号を選択する基底信号選択部と，
重み係数信号を，基底信号選択部で求められた基底信号に固定したもとで選択する重み係数信号選択部と，
前記基底信号選択部で選択した基底信号に，前記重み係数信号選択部で選択した重み係数信号の各重み係数を乗じて作成される，複数の信号によって構成される近似信号群を生成する近似信号生成部と，
入力信号群の各信号と近似信号群の各信号の間の誤差信号によって構成される誤差信号群を生成する誤差信号生成部と，
前記選択部で選択された基底信号と重み係数信号に対応するインデックス情報を符号化するインデックス符号化部とを備える
ことを特徴とする情報源の符号化装置。
【請求項１０】
請求項９記載の情報源の符号化装置において，
前記基底信号選択部は，入力信号群の各信号と基底信号とをそれぞれベクトルとして入力信号群の各信号と基底信号の内積を計算し，これらの内積値の二乗和を最大化する基底信号を選択し，
前記重み係数信号選択部は，前記基底信号選択部で求められた基底信号に重み係数信号の各重み係数を乗じて作成される信号と入力信号群の各信号に対する二乗誤差の和を最小にするように重み係数信号を選択する
ことを特徴とする情報源の符号化装置。
【請求項１１】
請求項７から請求項１０までのいずれか１項に記載の情報源の符号化装置において，
複数の符号化対象信号群を学習データとし，基底信号と重み係数信号とを選択する，インデックス情報が対応付けられた信号の集合であるコードブックを作成するための手段として，
複数の符号化対象信号群または前記誤差信号生成部で求められた全ての誤差信号群を入力学習データとして，学習データを入力する入力学習データ入力部と，
入力学習データを記録する入力学習データメモリと，
入力学習データによって基底信号のコードブックと重み係数信号のコードブックとを学習する学習部とを備える
ことを特徴とする情報源の符号化装置。
【請求項１２】
請求項７から請求項１０までのいずれか１項に記載の情報源の符号化装置において，
複数の符号化対象信号群を学習データとし，基底信号と重み係数信号とを選択する，インデックス情報が付加された信号の集合であるコードブックを作成するための手段として，
複数の符号化対象信号群または前記誤差信号生成部で求められた全ての誤差信号群を入力学習データとして，学習データを入力する入力学習データ入力部と，
入力学習データを記録する入力学習データメモリと，
入力学習データによって基底信号のコードブックと重み係数信号のコードブックとを，入力学習データに対する平均二乗誤差を最適化の評価関数として，学習する学習部とを備える
ことを特徴とする情報源の符号化装置。
【請求項１３】
請求項１から請求項６までのいずれか１項に記載の情報源の符号化方法をコンピュータに実行させるための情報源の符号化プログラム。
【請求項１４】
請求項１から請求項６までのいずれか１項に記載の情報源の符号化方法をコンピュータに実行させるための情報源の符号化プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，音声や画像などのデジタル信号を効率的に符号化する技術に関するものである。特に，波形が似ている複数の信号を効率的に符号化し，かつ符号化データがプログレッシブ性を有する情報源の符号化方法に関するものである。
【０００２】
【従来の技術】
音声や画像のようなデジタル信号が複数与えられたときの有効な符号化方法として，  Ｓｅｐａｒａｂｌｅ  Ａｐｐｒｏｘｉｍａｔｉｏｎ（分離近似）とベクトル量子化を組み合わせた手法がある。例えば，非特許文献１では，この符号化方法によって，Ｓｕｒｆａｃｅ  Ｌｉｇｈｔ  Ｆｉｅｌｄ  データという，３次元オブジェクトの形状の表面の輝度データの圧縮を行っている。この方法によれば，データ圧縮が行われると同時に，符号化データはプログレッシブ性を有する。また，復号化が高速に実行でき，Ｓｕｒｆａｃｅ  Ｌｉｇｈｔ  Ｆｉｅｌｄ  に用いた場合はレンダリングが高速に行える，という特徴を持っている。
【０００３】
以下では，まず  Ｓｅｐａｒａｂｌｅ  Ａｐｐｒｏｘｉｍａｔｉｏｎ（分離近似）とベクトル量子化のそれぞれについて説明し，次にそれを組み合わせた従来の技術について説明する。以下の説明において，有限長のデジタル信号をベクトルとして表記して説明を行う場合がある。ベクトルは全て列ベクトルであり，ＡＴ  のようにベクトルや行列を表す記号Ａの右上にＴが付けられた場合は，そのベクトルあるいは行列の転置を表すとする。
【０００４】
分離近似では，符号化対象の，複数の有限長のデジタル信号（これらの信号の集合を符号化対象信号群と呼ぶ）に対して１つ以上の基底信号を定める。そして，符号化対象信号群の各々の信号を，その基底信号の重み付け和で近似する。これは次式のような近似を意味する。
【０００５】
【数１】
2004229100.tif 000003
【０００６】
ただし，Ｘは行に符号化対象信号群の各信号が入ったＮ行Ｍ列の行列であり，Ｓｋ  はＭ次元ベクトルの基底信号である（ここでは，符号化信号群に対してＫ個の基底信号を定めている）。−方，Ｖｋ  は近似の際に基底信号に乗じられる重み係数を要素としたＮ次元ベクトルであり，重み係数信号と呼ぶこととする。
【０００７】
数少ない基底信号で近似によって生じる誤差を小さくできれば，大幅な情報量の削減が可能である。また，特定の基底信号と重み係数信号の組み（（１）式での，同じｋに対応した基底信号と重み係数信号の組を，以下では近似項と呼ぶ）にエネルギーが集中するように基底信号を構成できれば，プログレッシブなデータ構造を得ることが可能である。つまり，エネルギーが集中している近似項のみで符号化対象信号群を近似しても，良好な近似が可能である。
【０００８】
以上のような，情報量の削減とプログレッシブ性の意味で最適な基底信号と重み係数信号の組みを求める古典的な方法として特異値分解法があり，従来から用いられている。特異値分解では，以下のような再帰的な処理によって分離近似を構成するための基底信号と重み係数信号を求めていく。
【０００９】
まず，一つの近似項のみで近似した際の，符号化対象信号群の各信号に対する二乗誤差の総和を最小にするように基底信号と重み係数信号を求める。そして，ここで求まった基底信号と重み係数信号で近似信号を生成し，符号化対象信号群の各信号に対する誤差信号を求める。そして，これらの誤差信号の集まりを誤差信号群とし，次は誤差信号群の各信号に対する二乗誤差の総和を最小にするように基底信号と重み係数信号を一つずつ求める。
【００１０】
これにより，２つの近似項分の基底信号と重み係数信号が求まる。以降は，これまでに求まった基底信号と重み係数信号で近似信号を生成し，符号化対象信号群の各信号に対する誤差信号を求め，誤差信号群に対して基底信号と重み係数信号を一つずつ求める，という処理を繰り返していくことによって，所望の数の近似項による分離近似を構成する。
【００１１】
一方，ベクトル量子化は，デジタル信号の符号化法である。ベクトル量子化に関する詳細な説明は，例えば，非特許文献３などにある。ベクトル量子化では，符号化側と復号化側がコードブックと呼ばれる，デジタル信号の集合を保持している。そして，コードブック内の信号はコードワードと呼ばれ，各コードワードにはインデックスが割り振られている。符号化側は符号化対象の信号に対してコードワードを選択し，そのインデックスを符号化する。
【００１２】
なお，コードワードの選択は，符号化対象の信号とコードワードの間の二乗誤差など，何らかの評価関数に基づいて行われる。つまり，評価関数が二乗誤差の場合，符号化対象の信号に対する二乗誤差が最小になるようなコードワードを選択し，そのインデックスを符号化する。復号化側はインデックスを復号化し，そのインデックスに対応したコードワードをコードブックから参照することによって復号化信号を得る。
【００１３】
ベクトル量子化で効率的な符号化を行うには，実際にベクトル量子化を行った際に良好な符号化を行えるコードブックを作成しておく必要がある。つまり，符号化対象の信号の統計的な性質を反映したコードブックが必要である。これには，多数のデータを学習データとして与え，ベクトル量子化で利用する評価関数（例えば二乗誤差）に関するコードブックの最適化を行う学習アルゴリズムを適用する。このような学習アルゴリズムの代表的なものとしては，例えば，非特許文献２に記載されたＬＢＧアルゴリズムが挙げられる。
【００１４】
なお，学習データは必ずしも符号化対象のデータである必要はない。しかし，符号化対象の信号と同様の統計的な性質を持ったデータで学習を行ったほうが，良好な符号化が可能である。符号化対象の信号が多数ある場合，これら（あるいは，その一部）を学習データとしてコードブックを作成することが考えられるが，この場合はインデックスの符号化データとコードブックを復号化に渡す必要がある。一方，コードブックは符号化対象の信号とは別のデータで作成されており，符号化側と復号化側で互いに予め同じコードブックを持つ場合がある。この場合には，インデックスの符号化データのみ復号化側に送られる。
【００１５】
非特許文献１に記載された従来の技術では，特異値分解法による分離近似とベクトル量子化を組み合わせて符号化対象信号群の符号化を行う。つまり，まず特異値分解法によって良好な分離近似が可能な基底信号と重み係数信号を求めて分離近似を構成しておく。そして，これらの基底信号と重み係数信号をベクトル量子化する。ここでのベクトル量子化は，具体的には以下の方法で行われる。
【００１６】
コードブックは各近似項について，そして重み係数信号と基底信号について個別のものが利用される。それぞれのコードブックの作成は，多数の符号化対象信号群の各々に対して特異値分解法を適用し，各々の基底信号と重み係数信号を求める。そして，これらの基底信号と重み係数を学習データとし，基底信号と重み係数のそれぞれに対する二乗誤差を評価関数としたコードブックの最適化を，ＬＢＧアルゴリズムで行う。
【００１７】
コードワードの選択も基底信号と重み係数のそれぞれに対する二乗誤差を評価関数として行われる。つまり，従来の技術では，分離近似の構成とベクトル量子化を２つの異なる最適化問題（符号化対象信号群に対する二乗誤差の総和を最小にする分離近似を求める問題と基底信号と重み係数信号に対する誤差を小さくするベクトル量子化の問題）としてとらえて符号化を行うことが大きな特徴である。
【００１８】
一方，復号化側では符号化データを受け取ると，インデックス情報を復号化してインデックスに対応した基底信号と重み係数信号をコードブックから読み出す。そして，このようにして得た基底信号と重み係数信号を用いて（１）式に基づいて復号化信号を得る。なお，上記コードブックの作成に関する従来技術には，例えば下記の非特許文献４に記載されている技術もある。
【００１９】
【非特許文献１】
Ｗｅｉ−Ｃｈａｏ  Ｃｈｅｎ，Ｊｅａｎ−Ｙｖｅｓ  Ｂｏｕｇｕｅｔ，Ｍｉｃｈａｅｌ  Ｈ．Ｃｈｕ，Ｒａｄｅｋ  Ｇｒｚｅｓｚｃｚｕｋ，Ｌｉｇｈｔ  Ｆｉｅｌｄ  Ｍａｐｐｉｎｇ：Ｅｆｆｉｃｉｅｎｔ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ａｎｄ  Ｈａｒｄｗａｒｅ  Ｒｅｎｄｅｒｉｎｇ  ｏｆ  Ｓｕｒｆａｃｅ  Ｌｉｇｈｔ  Ｆｉｅｌｄｓ．ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｇｒａｐｈｉｃｓ．２１（３），ｐｐ．４４７−４５６，２００２
【非特許文献２】
Ｙ．Ｌｉｎｄｅ，Ａ．Ｂｕｚｏ．ａｎｄ  Ｒ．Ｍ．Ｇｒａｙ，Ａｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｖｅｃｔｏｒ  Ｑｕａｎｔｉｚｅｒ  Ｄｅｓｉｇｎ，  ＩＥＥＥ  Ｔｒａｎｓ．Ｃｏｍｍｕｎ．，ｖｏｌ．２８，ｐｐ．８４−９５，Ｊａｎ．１９８０
【非特許文献３】
Ａ．Ｇｅｒｓｈｏ  ａｎｄ  Ｒ．Ｍ．Ｇｒａｙ：Ｖｅｃｔｏｒ  Ｑｕａｎｔｉｚａｔｉｏｎ  ａｎｄ  Ｓｉｇｎａｌ  Ｃｏｍｐｒｅｓｓｉｏｎ，Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ，１９９２
【非特許文献４】
Ｇ．Ｒ．Ｃａｎｔａ，Ｇ．Ｐｏｇｇｉ，Ｋｒｏｎｅｃｋｅｒ−ｐｒｏｄｕｃｔ  ｇａｉｎ−ｓｈａｐｅ  ｖｅｃｔｏｒ  ｑｕａｎｔｉｚａｔｉｏｎ  ｆｏｒｍｕｌｔｉｓｐｅｃｔｒａｌ  ａｎｄ  ｈｙｐｅｒｓｐｅｃｔｒａｌ  ｉｍａｇｅ  ｃｏｄｉｎｇ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  ＩｍａｇｅＰｒｏｃｅｓｓｉｎｇ，ｖｏｌ．７，ｐｐ．６６８−６７８，Ｍａｙ  １９９８
【００２０】
【発明が解決しようとする課題】
従来の技術は，分離近似の構成とベクトル量子化を２つの異なる独立な最適化問題としてとらえて符号化を行うことが大きな特徴である。従い，ベクトル量子化を行う前に分離近似を特異値分解によって構成しておく。このような処理が行われることによって，従来の技術には以下の２点の課題が生じる。
【００２１】
一つ目の課題（従来技術の課題▲１▼）は，ベクトル量子化によって生じる誤差を考慮せずに，特異値分解の再帰的な処理によって全ての基底信号と重み係数信号を求める点にある。
【００２２】
具体的には，特異値分解の再帰的な処理ループのｋ回目のループで求まった基底信号と重み係数信号は，それ以前に求められた基底信号と重み係数信号をベクトル量子化した際の誤差を考慮していない。つまり，ｋ回目のループでは，それ以前に求められた基底信号と重み係数信号にベクトル量子化されていない状態で符号化対象信号を近似した際の誤差信号を生成し，これらの誤差信号に対して二乗誤差を小さくするような基底信号と重み係数信号を求める。
【００２３】
前述の通り，特異値分解の性質上，一回目，二回目に求まる近似項には大きなエネルギーが集中する。従い，これらの近似項のベクトル量子化で大きな誤差を生じた場合には，全体の圧縮誤差に大きなウェイトを占める。ベクトル量子化で生じる誤差を補償するように近似項を求めることによって，より圧縮誤差を小さくでき，圧縮効率の向上を実現できると考えられる。
【００２４】
二つ目の課題（従来技術の課題▲２▼）は，ベクトル量子化の適用方法にある。ベクトル量子化において圧縮誤差を小さくするうえで最大の効果を得るには，コードワードの選択とコードブックの学習のいずれにおいても圧縮誤差（例えば，符号化対象信号群と，基底信号と重み係数信号で生成した近似信号の間の二乗誤差）を評価関数として最適化を行う必要がある。しかし，従来法におけるベクトル量子化，すなわちコードワードの選択とコードブックの学習は，特異値分解で求まった重み係数信号と基底信号のそれぞれに対する二乗誤差を評価関数として行われる。圧縮誤差そのものを評価関数としてベクトル量子化を適用するような仕組みを構成したほうが，圧縮誤差を小さくできると考えられる。
【００２５】
本発明は上記の問題の解決を図り，分離近似とベクトル量子化を用いた情報源の符号化において，圧縮誤差をより小さくして圧縮効率を向上させることを目的とする。
【００２６】
【課題を解決するための手段】
本発明は上記目的を達成するために，以下に述べるような方法を採用している。
【００２７】
第１の発明は，符号化対象の，複数の信号の集合である符号化対象信号群に対して，符号化対象信号群の各々の信号を基底信号の重み付け和で近似，あるいは誤差なく表現するため，インデックス情報が対応付けられた信号の集合から基底信号と，重み係数で構成される重み係数信号とを選択し，選択された基底信号と重み係数信号に対応するインデックス情報を符号化する，情報源の符号化方法であって，符号化対象信号群を入力信号群とし，入力信号群に対する基底信号と重み係数信号を一組選択する，選択ステップと，選択ステップで選択した基底信号に重み係数信号の各重み係数を乗じて作成される，複数の信号によって構成される近似信号群を生成する近似信号生成ステップと，入力信号群の各信号と近似信号群の各信号間の誤差信号によって構成される誤差信号群を生成する誤差信号生成ステップと，誤差信号群を入力信号群として，選択ステップ，近似信号生成ステップ，誤差信号生成ステップを順に行うことを，予め設定した条件が満たされるまで繰り返すことを特徴とした情報源の符号化方法である。
【００２８】
第２の発明は，第１の発明の選択ステップにおいて，入力信号群の各信号と，基底信号に重み係数信号の各重み係数を乗じて作成される信号との間の二乗誤差の和を最小にするように，基底信号と重み係数信号を一組選択することを特徴とした情報源の符号化方法である。
【００２９】
第３の発明は，符号化対象の，複数の信号の集合である符号化対象信号群に対して，符号化対象信号群の各々の信号を基底信号の重み付け和で近似，あるいは誤差なく表現するため，インデックス情報が対応付けられた信号の集合から基底信号と，重み係数で構成される重み係数信号とを選択し，選択された基底信号と重み係数信号に対応するインデックス情報を符号化する，情報源の符号化方法であって，符号化対象信号群を入力信号群とし，入力信号群に対する基底信号を選択する基底信号選択ステップと，重み係数信号を，基底信号選択ステップで求まった基底信号に固定したもとで選択する重み係数信号選択ステップと，前記の基底信号選択ステップと重み係数信号選択ステップで求まった基底信号に重み係数信号の各重み係数を乗じて作成される，複数の信号によって構成される近似信号群を生成する近似信号生成ステップと，入力信号群の各信号と近似信号群の各信号間の誤差信号によって構成される誤差信号群を生成する誤差信号生成ステップと，誤差信号群を入力信号群として，基底信号選択ステップ，重み係数信号選択ステップ，近似信号生成ステップ，誤差信号生成ステップを順に行うことを，予め設定した条件が満たされるまで繰り返すことを特徴とした情報源の符号化方法である。
【００３０】
第４の発明は，第３の発明の基底信号選択ステップにおいて，入力信号群の各信号と基底信号をそれぞれベクトルとみなしたとき，入力信号群の各信号と基底信号の内積を計算し，これらの内積値の二乗和を最大化する基底信号を選択し，重み係数信号選択ステップにおいて，基底信号選択ステップで求まった基底信号に重み係数信号の各重み係数を乗じて作成される信号と入力信号群の各信号に対する二乗誤差の和を最小にするように重み係数信号を選択することを特徴とした情報源の符号化方法である。
【００３１】
第５の発明は，第１から第４までのいずれかの発明において，基底信号と重み係数信号とを選択する，インデックス情報が対応付けられた信号の集合であるコードブックを作成するために，複数の符号化対象信号群を入力学習データとし，入力学習データによって基底信号のコードブックと重み係数信号のコードブックを学習する学習ステップと，前記学習ステップで作成されたコードブックを利用して，入力学習データに含まれる各信号群に対し，第１の発明，第２の発明のいずれかの選択ステップ，近似信号生成ステップ，誤差信号生成ステップを，あるいは，第３の発明，第４の発明のいずれかの基底信号選択ステップ，重み係数信号選択ステップ，近似信号生成ステップ，誤差信号生成ステップを，順に行うことによって入力学習データに含まれる各信号群に対する誤差信号群を求める誤差学習データ生成ステップとを有し，前記誤差学習データ生成ステップで求まった誤差信号群を入力学習データとして，前記学習ステップと前記誤差学習データ生成ステップとを予め設定した条件を満たすまで繰り返すことでコードブックを作成することを特徴とした情報源の符号化方法である。
【００３２】
第６の発明は，第１から第４までのいずれかの発明において，基底信号と重み係数信号とを選択する，インデックス情報が対応付けられた信号の集合であるコードブックを作成するために，複数の符号化対象信号群を入力学習データとし，入力学習データによって基底信号のコードブックと重み係数信号のコードブックを，入力学習データに対する平均二乗誤差を最適化の評価関数として，学習する学習ステップと，前記学習ステップで作成されたコードブックを利用して，入力学習データに含まれる各信号群に対し，第１の発明，第２の発明のいずれかの選択ステップ，近似信号生成ステップ，誤差信号生成ステップを，あるいは，第３の発明，第４の発明のいずれかの基底信号選択ステップ，重み係数信号選択ステップ，近似信号生成ステップ，誤差信号生成ステップを，順に行うことによって入力学習データに含まれる各信号群に対する誤差信号群を求める誤差学習データ生成ステップとを有し，前記誤差学習データ生成ステップで求まった誤差信号群を入力学習データとして，前記学習ステップと前記誤差学習データ生成ステップを予め設定した条件を満たすまで繰り返すことでコードブックを作成することを特徴とした情報源の符号化方法である。
【００３３】
第７の発明は，符号化対象の，複数の信号の集合である符号化対象信号群に対して，符号化対象信号群の各々の信号を基底信号の重み付け和で近似，あるいは誤差なく表現するため，インデックス情報が対応付けられた信号の集合から基底信号と，重み係数で構成される重み係数信号とを選択し，選択された基底信号と重み係数信号に対応するインデックス情報を符号化する，情報源の符号化装置であって，符号化対象信号群，あるいは後述の誤差信号生成部で生成される誤差信号群を入力信号群とし，入力信号群を入力する信号群入力部と，入力信号群を記録する入力信号群メモリと，基底信号と重み係数信号とを選択する，信号の集合を記録するコードブックメモリと，入力信号群に対する基底信号と重み係数信号を一組選択する，選択部と，選択部で選択した基底信号に重み係数信号の各重み係数を乗じて作成される，複数の信号によって構成される近似信号群を生成する，近似信号生成部と，入力信号群の各信号と近似信号群の各信号の間の誤差信号によって構成される誤差信号群を生成する，誤差信号生成部と，前記の選択部で選択された基底信号と重み係数信号に対応するインデックス情報を符号化するインデックス符号化部とを備えることを特徴とした情報源の符号化装置である。
【００３４】
第８の発明は，第７の発明の選択部において，入力信号群の各信号と，基底信号に重み係数信号の各重み係数を乗じて作成される信号との間の二乗誤差の和を最小にするように，基底信号と重み係数信号を一組選択することを特徴とした情報源の符号化装置である。
【００３５】
第９の発明は，符号化対象の，複数の信号の集合である符号化対象信号群に対して，符号化対象信号群の各々の信号を基底信号の重み付け和で近似，あるいは誤差なく表現するため，インデックス情報が対応付けられた信号の集合から基底信号と，重み係数で構成される重み係数信号とを選択し，選択された基底信号と重み係数信号に対応するインデックス情報を符号化する，情報源の符号化装置であって，符号化対象信号群，あるいは後述の誤差信号生成部で生成される誤差信号群を入力信号群とし，入力信号群を入力する信号群入力部と，入力信号群を記録する入力信号群メモリと，基底信号と重み係数信号とを選択する，信号の集合を記録するコードブックメモリと，入力信号群に対する基底信号を選択する基底信号選択部と，重み係数信号を，基底信号選択部で求まった基底信号に固定したもとで選択する重み係数信号選択部と，基底信号選択部と重み係数信号選択部で選択した基底信号に重み係数信号の各重み係数を乗じて作成される，複数の信号によって構成される近似信号群を生成する，近似信号生成部と，入力信号群の各信号と近似信号群の各信号の間の誤差信号によって構成される誤差信号群を生成する，誤差信号生成部と，前記の選択部で選択された基底信号と重み係数信号に対応するインデックス情報を符号化するインデックス符号化部とを備えることを特徴とした情報源の符号化装置である。
【００３６】
第１０の発明は，第９の発明の基底信号選択部において，入力信号群の各信号と基底信号をそれぞれベクトルとみなしたとき，入力信号群の各信号と基底信号の内積を計算し，これらの内積値の二乗和を最大化する基底信号を選択し，重み係数信号選択部において，基底信号選択部で求まった基底信号に重み係数信号の各重み係数を乗じて作成される信号と入力信号群の各信号に対する二乗誤差の和を最小にするように重み係数信号を選択することを特徴とした情報源の符号化装置である。
【００３７】
第１１の発明は，第７から第１０までのいずれかの発明において，基底信号と重み係数信号とを選択する，インデックス情報が対応付けられた信号の集合をコードブックと呼び，複数の符号化対象信号群を学習データとし，学習データ，あるいは誤差信号生成部で求まった全ての誤差信号群を入力学習データとして，入力学習データを入力する，入力学習データ入力部と，入力学習データを記録する入力学習データメモリと，入力学習データによって基底信号のコードブックと重み係数信号のコードブックを学習する学習部とを備えることを特徴とした情報源の符号化装置である。
【００３８】
第１２の発明は，第７から第１０までのいずれかの発明において，基底信号と重み係数信号とを選択する，インデックス情報が付加された信号の集合をコードブックと呼び，複数の符号化対象信号群を学習データとし，学習データ，あるいは誤差信号生成部で求まった全ての誤差信号群を入力学習データとして，入力学習データを入力する，入力学習データ入力部と，入力学習データを記録する入力学習データメモリと，入力学習データによって基底信号のコードブックと重み係数信号のコードブックを，入力学習データに対する平均二乗誤差を最適化の評価関数として，学習する学習部とを備えることを特徴とした情報源の符号化装置である。
【００３９】
第１，及び第７の発明はコードワードの選択とそのインデックス情報の符号化に関するものであり，従来技術の課題▲１▼に関する改善を得ることができる。具体的には，基底信号と重み係数信号を追加する際に，これまでコードブックから選択してきた基底信号と重み係数信号で近似信号を生成し，これによって符号化対象信号群を近似した際の誤差を入力信号群にフィードバックできる。つまり，ある近似項に関する基底信号と重み係数信号をコードブックから選択するときは，これまでに生じた全ての誤差を含んだ誤差信号に対して行う。
【００４０】
これにより，圧縮誤差を従来の技術より小さくすることを期待できる。また，従来の技術と同様に圧縮データはプログレッシブな性質を有する。つまり，再帰的な処理ループで先に求まった近似項ほど大きなエネルギーが集中する傾向がある。しかし，従来の技術と異なり，最初の１，２回目のループで大きな誤差が生じても後に求められる近似項でその誤差を補償できる。なお，この符号化方法を実現するには，適切なコードブックが必要となるが，これは第５，第６，第１１，第１２の発明で実現可能である。第５，第６，第１１，第１２の発明によれば，各近似項に対応したコードブックは，それぞれが利用対象となる入力信号群の統計的な性質を反映したものとなる。
【００４１】
第２，及び第８の発明はコードワードの選択とそのインデックス情報の符号化に関するものであり，圧縮誤差の評価関数として二乗誤差を採用した場合の，従来技術の課題▲２▼に関する改善を，コードワードの選択とそのインデックス情報の符号化に関して得ることができる。第１，及び第７の発明の符号化方法において符号化対象群の各信号に対する二乗誤差の総和を最小にする基底信号と重み係数をコードブックから選択するには，これまで選択された基底信号と重み係数信号による誤差信号に対する二乗誤差の総和を最小にする基底信号と重み係数をコードブックから選択すればよい。第２，及び第８の発明では，これを行う。なお，コードブックの作成は前記のとおり，第５，第６，第１１，第１２の発明で実現可能である。
【００４２】
第３，及び第９の発明はコードワードの選択とそのインデックス情報の符号化に関するものであり，重み係数信号とは独立に基底信号のコードブックからの選択を行えるため，重み係数信号と基底信号のコードブックからの選択を両者の全組み合わせを考慮して選択を行うよりも，少ない計算量で従来技術の課題▲１▼と▲２▼に関する改善を実現できる。コードブックの作成は前記のとおり，第５，第６，第１１，第１２の発明で実現可能である。
【００４３】
第４，及び第１０の発明はコードワードの選択とそのインデックス情報の符号化に関するものであり，重み係数信号とは独立に，近似の際に符号化対象信号群に対する平均二乗誤差を小さくするような基底信号を選択するように，第３，及び第９の発明を実行できる。これは，入力信号群の各信号に対する内積値の二乗和を最大にするということは，その基底信号で近似を行った際の二乗誤差の総和を最小にすることと同じことだからである。また，重み係数信号の選択に関しては，符号化対象信号の各信号に対する二乗誤差の総和を最小にするような重み係数信号を選択するように，第３，及び第９の発明を実行できる。コードブックの作成は前記のとおり，第５，第６，第１１，第１２の発明で実現可能である。
【００４４】
第１から第４の発明，第７から第１０の発明はコードワードの選択とそのインデックス情報の符号化に関するものであるが，これらの発明で利用するコードブックは第５，第６の発明及び第１１，第１２の発明で実現できる。これらの発明によれば，各近似項に対応したコードブックは，それぞれが利用対象となる入力信号群の統計的な性質を反映したものとなる。特に，第６，第１２の発明では，符号化対象のデータに対する平均二乗誤差を評価関数として各近似項に対応したコードブックを学習できる。
【００４５】
【発明の実施の形態】
ここでは複数の画像ブロックで構成される画像ブロック群を符号化する際の本発明の実施の形態を示す。画像ブロックは矩形である必要はなく，ピクセルの集合であれば良い。この画像ブロック群の一例としては，Ｓｕｒｆａｃｅ  Ｌｉｇｈｔ  Ｆｉｅｌｄ  （ＳＬＦ）が挙げられる。Ｓｕｒｆａｃｅ  Ｌｉｇｈｔ  Ｆｉｅｌｄ  とは，物体（物理的に存在する物体，あるいはＣＧで作成された仮想的な物体）に光源からの光が当り，反射した光線の輝度データのことである。つまり，物体を様々な方向から見たときの輝度データである。
【００４６】
具体的には，ｆ（ｍ，ｎ，θ，φ）のような，４つのパラメータの関数として表わされる。ｍ，ｎとは物体の表面上での位置を表すパラメータで（通常は物体の形状はポリゴンモデルなどの幾何モデルで与えられている），θ，φはそれぞれ光線が放たれる方向を方位角と仰角で表したパラメータである。簡単な概念図を図１に示す。実際には，Ｓｕｒｆａｃｅ  Ｌｉｇｈｔ  Ｆｉｅｌｄ  は，ｆ（ｍ，ｎ，θ，φ）を位置ｍ，ｎと方向θ，φに関して標本化した４次元の離散信号として扱われ，対象オブジェクトを様々な方向から撮影した画像に対して位置と方向に関する補間を行うことによって各標本点に光線データがマッピングされる。
【００４７】
なお，この形状を小さな領域に分割すると（形状がポリゴンモデルの場合には，例えばポリゴンに分割することが考えられる），分割されたある領域の関数値ｆ（ｍ，ｎ，θ，φ）は，θ，φを固定すると２次元の関数になる。これは，一つの（ある領域の）画像ブロックと考えることができる。これを全てのθ，φの組み合わせに関して集めると，多数の画像ブロックを得られ，画像ブロック群を得る。この概念図を図２に示す。つまり，Ｓｕｒｆａｃｅ  Ｌｉｇｈｔ  Ｆｉｅｌｄ  では，形状の分割された各領域について一つの画像ブロック群を得る。本発明は，このような画像ブロック群を符号化するために利用されうる。
【００４８】
なお，本発明ではベクトル量子化を用いるが，ベクトル量子化は，符号化（コードワードを選択してインデックスを符号化する処理）とコードブックの作成という２つの処理で構成される。前述の通り，コードブックの学習は，符号化対象のデータそのものを学習データとして行われる場合と，そうでない場合がある。Ｓｕｒｆａｃｅ  Ｌｉｇｈｔ  Ｆｉｅｌｄ  を扱った上記非特許文献１に記載された従来技術では，物体全体に渡る全ての画像ブロック群を学習データとしてコードブックを作成する。本発明では特に指定しないが，いずれの場合であっても符号化法とコードブックの作成方法は変わらない。また，発明の効果はいずれの場合も同様である。
【００４９】
さらに，符号化対象のデータでコードブックを作成してコードブックも復号化側に渡されるような場合，コードブック自体に何らかの符号化が行われると考えられるが，これは本発明での処理に対して本質的な関連性はないため，この処理に関する説明は省略する。なお，以下の実施の形態では従来の技術と同様に，近似項，基底信号，重み係数信号について個別のコードブックを用意する。つまり，近似項の数をＫとしたとき，基底信号と重み係数信号の各々に対してＫ個のコードブックを利用する。これらのコードブックに対するコードワード数の割り振りは，本発明の効果には関わらないため，これに関しては説明しない。
【００５０】
画像ブロック群に含まれる画像ブロックは，Ｍ個のピクセルで構成されるとし，画像ブロック数はＮ個であるとする。また，画像ブロックの各ピクセル値を並べたＭ次元ベクトルをｘｎ  ，ｎ＝１，２，…，Ｎとし，画像ブロック群を以下の行列として表す。
【００５１】
【数２】
2004229100.tif 000004
【００５２】
本実施の形態では，画像ブロック群Ｘを符号化することを考える。
【００５３】
図３に本発明の符号化装置の概要を示す。符号化装置１は，符号化対象の画像ブロック群Ｘ，あるいは後述の誤差ブロック群Ｘ（ｋ）  ，ｋ＝２，３，…，Ｎを記録して読み出す入力信号群メモリ１１と，基底信号と重み係数信号のコードブックを記録して読み出すコードブックメモリ１２と，基底信号コードワードと重み係数信号コードワードの選択を行う選択部１３と，再帰的に基底信号コードワードと重み係数コードワードを選択していく中，これまでに選択された基底信号コードワードと重み係数信号コードワードを用いて近似画像ブロック群を生成する近似信号生成部１４と，近似画像ブロック群と画像ブロック群Ｘの間の誤差画像ブロック群Ｘ（ｋ）  ，ｋ＝２，３，…，Ｎを生成する誤差信号生成部１５と，画像ブロック群Ｘ，あるいは誤差画像ブロック群Ｘ（ｋ）  ，ｋ＝２，３，…，Ｎを入力信号群メモリ１１に書き込む信号群入力部１６と，選択された基底信号コードワードと重み係数信号コードワードのインデックス情報を符号化するインデックス符号化部１７とを備える。
【００５４】
以下に符号化装置１の動作例を示す。図４におおまかな処理フローが示されている。なお，この符号化装置１は，基底信号コードワードと重み係数信号コードワードとを一組ずつ，再帰的に選択していく。つまり，同じ処理を繰り返すようなループ構造を有しており，ループのたびに基底信号コードワードと重み係数信号コードワードとが一組選択される仕組みになっている。また，近似項の数Ｋは予め決められているとする。ここでは，基底信号と重み係数信号が選択される順番に基づき，第ｋ基底信号，第ｋ重み係数信号と呼ぶ（ただし，ｋ＝１，２，…，ｋ）。
【００５５】
コードブックは予め作成されており，コードブックメモリ１２に記録されている。ここでは，前記の繰り返し処理における，ｋ回目のループにおける処理（第ｋ基底信号，第ｋ重み係数信号に関するコードワード選択とインデックスの符号化を行う処理）について示す。まず，ｋ−１回目の，ループの最後の処理において信号群入力部１６に入力された画像ブロック群Ｘ（ｋ）  （この行列は符号化対象の画像ブロック群Ｘと同次元の行列であり，後述の誤差画像ブロック群にあたる）が入力信号群メモリ１１に記録される。なお，ｋ＝１の場合には，ステップＳ１により，符号化対象の画像ブロック群ＸがＸ（１）  として入力信号群メモリ１１に予め入力されている。
【００５６】
次に，ｋ＞Ｋになるまで，以下のステップＳ３〜Ｓ６を繰り返す（ステップＳ２）。ステップＳ３では，選択部１３は画像ブロック群Ｘ（ｋ）  を入力信号群メモリ１１から読み出し，コードブックメモリ１２に格納されたコードブックを利用して基底信号コードワードと重み係数信号コードワードの選択を行う。
【００５７】
なお，この選択処理に関しては２種類の方法（方法Ａ，Ｂ）を示す。方法Ａ，Ｂのいずれにおいても基底信号のコードブックはＫ個あり，それぞれのコードブックはＢＡＳＩＳ＿ＣＢｋ  個（ただし，ｋ＝１，２，…，Ｋ）のコードワードを格納している。一方，重み係数信号のコードブックも同様にＫ個あり，それぞれのコードブックはＣＯＥＦ＿ＣＢｋ  個（ただし，ｋ＝１，２，…，Ｋ）のコードワードを格納している。
【００５８】
まず，方法Ａにおける処理を示す。方法Ａでは，画像ブロック群Ｘ（ｋ）  に対して二乗誤差の総和を最小にするように基底信号コードワードと重み係数信号コードワードの選択を行う。この処理は，画像ブロック群Ｘ（ｋ）  を符号化対象のデータとしたときの，上記非特許文献４に記載されたＫｒｏｎｅｃｋｅｒ−Ｄｅｌｔａ  ＶＱと同様の処理になる。なお，二乗誤差の総和は次式で与えられる。
【００５９】
【数３】
2004229100.tif 000005
【００６０】
ただし，Ｖｋ  は第ｋ重み係数信号に対応したコードブック内の任意のコードワードで，ｖｋ  （ｎ）はＶｋ  のｎ番目の要素（スカラ）であり，Ｓｋ  は第ｋ基底信号に対応したコードブック内の任意のコードワードである。また，ｘｎ  （ｋ）  はＸ（ｋ）  のｎ行目を列ベクトルとして表したものであり，（誤差）画像ブロック群を構成する一つの誤差画像ブロックのデータが入っている。
【００６１】
すなわち，選択部１３はコードブックメモリ１２の重み係数信号と基底信号のコードブックから一つずつコードワードを読み出してＭＳＥ（Ｘ（ｋ）  ，Ｖｋ  ，Ｓｋ  ）を計算する処理を，Ｖｋ  とＳｋ  の全組み合わせについて行う。そして，ＭＳＥ（Ｘ（ｋ）  ，Ｖｋ  ，Ｓｋ  ）を最小にした重み係数信号コードワードと基底信号コードワード（  ＊Ｖｋ  と  ＊Ｓｋ  ）を見つけ出すことによってコードワードの選択を行う。
【００６２】
一方，方法Ｂでは，画像ブロック群Ｘ（ｋ）  に対する基底信号コードワードを重み係数コードワードとは独立に選択する。つまり，組み合わせ的に最適な基底信号コードワードを探索しない。なお，基底信号は画像ブロック群Ｘ（ｋ）  内の各画像ブロックとの内積の二乗和を最大化するようにして選択する。つまり，次式で与えられる評価関数に基づいた最大化を第ｋ基底信号のコードブック内の全てのコードワードに関して行う。
【００６３】
【数４】
2004229100.tif 000006
【００６４】
これは，二乗誤差の総和ＭＳＥ（Ｘ（ｋ）  ，Ｖｋ  ，Ｓｋ  ）が次式のように展開でき，内積の二乗和（次式の第３項）を大きくするような基底信号コードワードが二乗誤差の総和ＭＳＥ（Ｘ（ｋ）  ，Ｖｋ  ，Ｓｋ  ）を小さくする，という考察に基づいて導かれた。
【００６５】
【数５】
2004229100.tif 000007
【００６６】
このようにして選択された基底信号コードワードを  ＊Ｓｋ  とし，重み係数信号コードワードは，基底信号コードワードを  ＊Ｓｋ  に固定した二乗誤差の総和ＭＳＥ（Ｘ（ｋ）  ，Ｖｋ  ，  ＊Ｓｋ  ）を最小化するようにベクトル量子化され，  ＊Ｖｋ  が求まる。
【００６７】
なお，以降の処理は方法Ａ，Ｂにおいて共通である。  ＊Ｖｋ  と  ＊Ｓｋ  に対応したコードブック内でのインデックス情報は，インデックス符号化部１７に入力され，ここでインデックス情報の固定長符号化あるいは可変長符号化が行われる。一方，  ＊Ｖｋ  と  ＊Ｓｋ  は近似信号生成部１４に入力され，  ＊Ｖｋ  と  ＊Ｓｋ  をもとに近似画像ブロック  ＊Ｘ（ｋ）  ＝  ＊Ｖｋ    ＊Ｓｋ  Ｔ  が生成され（ステップＳ４），これが誤差信号生成部１５に入力される。誤差信号生成部１５では，誤差画像ブロックＸ（ｋ＋１）  ＝Ｘ（ｋ）  −  ＊Ｘ（ｋ）  を生成する（ステップＳ５）。すなわち，誤差画像ブロックＸ（ｋ＋１）  は，
【００６８】
【数６】
2004229100.tif 000008
【００６９】
によって得られる。
【００７０】
次に，誤差画像ブロック群Ｘ（ｋ＋１）  は信号群入力部１６に入力され（ステップＳ６），第Ｋ基底信号と第Ｋ重み係数信号に対するコードワード選択とインデックス情報の符号化が完了するまでこの処理ループが繰り返される。
【００７１】
以上の例では，予め定められた近似項の数であるＫ回ループを繰り返すものとしたが，ループの終了条件として，他の条件を設定することもできる。例えば，誤差信号生成部１５が生成する誤差信号の大きさが所定の閾値以下になったときに，ループを終了するようにしてもよい。
【００７２】
図５に本発明で用いるコードブック作成装置の概要を示す。コードブック作成装置２は，多数の画像ブロック群，あるいは後述の誤差画像ブロック群で構成される学習データを記録して読み出す入力学習データメモリ２１と，作成したコードブックを記録して読み出すコードブックメモリ２２と，入力学習データを利用してコードブックの学習を実行する学習部２３と，ｋ−１回目（ただし，ｋ＝２，３，…，Ｎ）のコードブックの作成ループで作成されているコードブックを利用して学習データを近似した際の誤差画像ブロック群を計算する誤差信号学習データ生成部２４と，多数の画像ブロック群，あるいは誤差画像ブロック群で構成されるデータを入力学習データメモリ２１に書き込む入力学習データ入力部２５とを備える。
【００７３】
次に，本発明で利用するコードブックの作成の実施例を示す。図６におおまかな処理フローが示されている。コードブックの作成も再帰的に同じ処理を繰り返すようなループ構造を有しており，ループのたびに基底信号と重み係数信号のコードブックが一組作成される仕組みになっている。その順序は，最初は第１基底信号と第１重み係数信号のコードブックが作成され，次は第２基底信号と第２重み係数信号のコードブックが作成されるなど，以下同様に続く。Ｋ組のコードブックを作成する場合はＫループ繰り返すこととなる。
【００７４】
なお，これらのコードブックは学習データを用いた学習によって作成されるが，各ループで学習データが更新される。学習データの更新については，後述する。ここで，学習データは，Ｐ個の画像ブロック群で構成されるとし，ｋ回目のループにおける学習データをＸｐ  （ｋ）  ，ｐ＝１，２，…，Ｐと記述する。１回目の処理ループで用いられる学習データＸｐ  （１）  ，  ｐ＝１，２，…，Ｐは元のデータであり，いかなる処理も施されていない。
【００７５】
以下では，ｋ回目のループでの処理について説明する。まず，ｋ−１回目のループの処理で入力学習データ入力部２５に入力された学習データＸｐ  （ｋ）  ，ｐ＝１，２，…，Ｐは，入力学習データ入力部２５によって入力学習データメモリ２１に記録される。ただし，１回目の処理ループの場合は，ステップＳ１１により，Ｘｐ  （１）  ，  ｐ＝１，２，…，Ｐが入力学習データ入力部２５に先立って入力されている。
【００７６】
次に，ｋ＞Ｋになるまで，ステップＳ１３〜Ｓ１７を繰り返す（ステップＳ１２）。ステップＳ１３では，学習部２３が学習データを入力学習データメモリ２１から読み出し，第ｋ基底信号のコードブックと第ｋ重み係数信号のコードブックを作成する。
【００７７】
なお，前述の符号化処理と同様に，ある一つの近似項に対応した基底信号のコードブックと重み係数信号コードブックの組の学習（すなわち，学習データに対する平均二乗誤差を評価関数としたコードブックの最適化）は，非特許文献４に記載されたＫｒｏｎｅｃｋｅｒ−Ｐｒｏｄｕｃｔ  ＶＱにおけるコードブックの学習と同様の方法で実行できる。詳細は非特許文献４にあるので，ここでは概要の説明のみにとどめる。
【００７８】
基底ベクトルと重み係数ベクトルのいずれのコードブックの学習も，繰り返しループ構造を有した学習アルゴリズムである。そして，いずれのアルゴリズムも次のような性質を持つ。初期コードブックを予め作成しておき，ループのたびにコードブックが更新されていき，更新されるたびに学習データに対してベクトル量子化を行った際の平均二乗誤差が小さくなる。繰り返しは，平均二乗誤差の減少率がある関値より小さくなったときに終了される。初期コードブックの作成方法などは，従来のベクトル量子化で用いられている例えば非特許文献３に記載されているような方法を採用する。
【００７９】
学習部２３でコードブックの組が作成されると，学習データＸｐ  （ｋ）  ，ｐ＝１，２，…，Ｐと学習部２３で作成されたコードブックが誤差信号学習データ生成部２４に入力される。すると，学習データの各画像ブロック群Ｘｐ  （ｋ）  に対して，学習部２３で作成されたコードブックを利用し，符号化装置１の選択部１３と同様の処理（方法Ａ，Ｂのいずれか）が行われる。つまり，学習データの各画像ブロック群Ｘｐ  （ｋ）  に対して一組の基底信号コードワードと重み係数コードワードが選択される（ステップＳ１４）。これらを，それぞれ  ＊Ｖｋ，ｐ  ，ｐ＝１，２，…，Ｐと，  ＊Ｓｋ，ｐ  ，ｐ＝１，２，…，Ｐと表す。
【００８０】
そして，選択されたコードワードによって，学習データの各画像ブロック群に対する近似画像ブロック群  ＊Ｘｐ  （ｋ）  ＝  ＊Ｖｋ，ｐ    ＊Ｓｋ，ｐ  Ｔ  が生成され（ステップＳ１５），次のループにおいての学習データとなる誤差画像ブロック群Ｘｐ  （ｋ＋１）  が作成される（ステップＳ１６）。これは次式で計算される。
【００８１】
Ｘｐ  （ｋ＋１）  ＝Ｘｐ  （ｋ）  −  ＊Ｘｐ  （ｋ）                  （７）
次に，Ｘｐ  （ｋ＋１）  ，ｐ＝１，２，…，Ｐが入力学習データ入力部２５に入力され（ステップＳ１７），ｋ＋１回目のループで学習データとして利用される。
【００８２】
〔従来方法と本発明との比較〕
以下では，本発明の有効性を検証するため，非特許文献１に記載されているＣｈｅｎらの研究による従来技術，すなわち，特異値分解法による分離近似（分離展開）とベクトル量子化を組み合わせて  Ｓｕｒｆａｃｅ  Ｌｉｇｈｔ  Ｆｉｅｌｄ（ＳＬＦ）の圧縮を行う従来方法と，本発明とを比較して説明する。
【００８３】
従来方法では，まず特異値分解法によって良好な分離近似が可能な基底画像と重み係数画像を求めて分離近似を構成しておく。そして，これらの基底画像と重み係数画像をベクトル量子化する。ここでのベクトル量子化は，具体的には以下の方法で行われる。本発明の場合と同様に，コードブックは各近似項について，そして重み係数画像と基底画像について個別のものが利用される。
【００８４】
それぞれのコードブックの作成は，対象オブジェクト全体にわたる各々のＳＬＦデータ（形状が小領域に分割されている）に対して特異値分解法を適用し，各々の基底画像と重み係数画像を求める。そして，これらの基底画像と重み係数画像を学習データとし，基底画像と重み係数画像のそれぞれに対する二乗誤差を評価関数としたコードブックの最適化を，ＬＢＧアルゴリズムによって行う。そして，コードワードの選択も基底信号と重み係数のそれぞれに対する二乗誤差を評価関数として行う。
【００８５】
つまり従来方法では，分離近似の構成とベクトル量子化を２つの異なる最適化問題（符号化対象信号群に対する二乗誤差の総和を最小にする分離近似を求める問題と基底信号と重み係数信号に対する誤差を小さくするベクトル量子化の問題）としてとらえて圧縮を行うことが大きな特徴である。これにより，従来方法では，以下のような問題が生じる。
【００８６】
従来方法は，特異値分解を利用しているため，本発明と同様に基底画像と重み係数画像を再帰的に求めることによってプログレッシブな圧縮データを得ている。しかし，従来方法では，ベクトル量子化の前に特異値分解で分離近似を構成してしまうため，第ｋ近似項に対応した基底画像と重み係数画像は第１から第ｋ−１近似項においてべクトル量子化で生じた誤差を考慮して求めることができない。
【００８７】
一方，本発明では，分離近似とベクトル量子化を統一的に行うことによって，近似項を追加する際には，これまでの近似項で生じた誤差は全て補償する仕組みになっている。
【００８８】
ベクトル量子化において圧縮誤差を小さくするうえで最大の効果を得るには，コードワードの選択とコードブックの学習のいずれにおいても圧縮誤差（例えば，符号化対象信号群と，基底信号と重み係数信号で生成した近似信号の間の二乗誤差）を評価関数として最適化を行う必要がある。しかし，従来方法におけるべクトル量子化，すなわちコードワードの選択とコードブックの学習は，特異値分解で求まった重み係数信号と基底信号のそれぞれに対する二乗誤差を評価関数として行われる。圧縮誤差そのものを評価関数としてべクトル量子化を適用するような仕組みを構成したほうが，圧縮誤差を小さくできると考えられる。
【００８９】
なお，すでに求められたｋ個の近似項に対する基底画像と重み係数画像を固定して，第ｋ＋１近似項に対応した基底画像と重み係数画像を求めるという前提のもとでは，誤差信号（前述の行列Ｘ（ｋ）  の各列に対応する）に対する二乗誤差を最小にすることと，ＳＬＦに対する二乗誤差を最小にすることとは等価である。そこで，本発明では，誤差信号に対する二乗誤差の最小化に基づくベクトル量子化を導入することで，ベクトル量子化の効果を高めるというアプローチを取っている。
【００９０】
本発明におけるこれらの改善の効果を，従来方法との性能比較を行う実験によって確認し，本発明のアプローチの有効性を検証した。
【００９１】
実験は，約４０００個および約７０００個の頂点からなり，３角形ポリゴンで構成される２つのモデルに対して行った。同様な結果が得られたので，以下では，約４０００個のモデルに対して行った例を取り上げて説明する。ＳＬＦは２８１枚の画像により生成され，方向と位置パラメータの標本化方法と各標本点におけるＳＬＦの値を求めるための補間は，非特許文献１に示されているＣｈｅｎらの方法を用いた。なお，ここでは各３角形パッチは３〜１５個の標本点からなり，方向パラメータに関する標本点は６４点からなる。
【００９２】
形状の小領域への分割は，Ｃｈｅｎらの研究におけるｖｅｒｔｅｘ−ｃｅｎｔｅｒｅｄという方法で行った。この分割法では，各分割がオーバーラップするが，圧縮後のポリゴン間での境界が見えにくいというメリットがある。具体的には，頂点を共有する３角形によって構成される領域を一つの小領域とする。つまり，各頂点において小領域が作成され，各々についてＳＬＦ−Ｘが取得される。より詳細な説明に関しては非特許文献１を参照されたい。なお，このような分割を行うと，小領域内の位置パラメータの数（つまり，Ｍの大きさ）は複数存在する。したがって，各頂点を位置パラメータの数に応じて分類し，各々の分類に対して個別の基底画像のコードブックを利用した。データ形式としては，各原色（Ｒ，Ｇ，Ｂ）に関して８ビットの精度で輝度を表現しており，各原色に対して独立に，本発明および従来方法を適用する。
【００９３】
なお，従来方法では，特異値分解に先立ち次式で与えられる平均画像ｘＡ  ，
ｘＡ  ＝Σｘｉ  ／Ｎ    （Σはｉ＝１からＮまでの和）
を各ｘｉ  から引いておく。この処理は本発明では不要であるが，本実験では基底画像を求めるプロセスの比較をより簡単にするため，本発明と従来方法のいずれにおいても平均画像を算出し，これに通常のベクトル量子化を適用する。ただし，本発明においては圧縮誤差を補償していくアプローチをとるため，ベクトル量子化された平均画像による残差信号に対して本発明を適用する。
【００９４】
圧縮性能の評価尺度としては，ＳＬＦに対するＰＳＮＲを次式で定義し，各原色について計算する。ただし，ｍｓｅは全データに関する圧縮誤差信号の二乗平均である。
【００９５】
【数７】
2004229100.tif 000009
【００９６】
実験結果は，図７および図８に示すとおりであった。図７に示されている実験結果は，第１近似項（従来方法では，最も特異値が大きい近似項）のみを利用して圧縮を行った場合のものである。
【００９７】
横軸の圧縮率は，圧縮データの情報量をＳＬＦの情報量で割った値であり，縦軸は，Ｒ信号のＰＳＮＲである。圧縮データの情報量は，コードブックの情報量（各コードワードの要素はＳＬＦと同様に８ビット精度の輝度で表現されている）と選択されたコードワードのインデックスの情報量（インデックスは固定長符号化されている）の和である。Ｇ信号，Ｂ信号に関しては同様の傾向が見られたために省略してある。
【００９８】
一方，図８は，近似項を増やした際のＰＳＮＲの振る舞いを示す実験結果を示している。これは，従来方法と本発明のいずれも同じ圧縮率での比較になっている。各コードブックに対するコードワード数の割り振りを変更しながら様々な実験を行ったが，いずれの場合も同様の傾向が見られたため，ここでは結果の一例を示した。横軸が近似項の数で，縦軸がＲ信号のＰＳＮＲである（ここでも，Ｇ信号，Ｂ信号については，同様の結果が得られたので省略している）。
【００９９】
図７，図８のいずれにおいても圧縮効率の向上が見られていることが確認できた。図８では，近似項を増やすごとにＰＳＮＲの差が開く傾向がある。これは，従来方法では近似項を追加する際にベクトル量子化で生じた誤差を補償しないが，本発明では以前に生じた誤差の全てを補償するためである。
【０１００】
【発明の効果】
本発明では，特異値分解などの方法によって予め分離近似を構成せず，基底信号と重み係数のコードワードの選択とコードブックの学習を符号化対象信号群に対する圧縮誤差を評価関数として行う。これにより，従来技術の課題▲１▼と，課題▲２▼によって生じる問題は，本発明では生じない。したがって，本発明によれば，圧縮誤差をより小さくすることができ，圧縮効率の向上を得ることを期待できる。
【図面の簡単な説明】
【図１】Ｓｕｒｆａｃｅ  Ｌｉｇｈｔ  Ｆｉｅｌｄ  の説明図である。
【図２】Ｓｕｒｆａｃｅ  Ｌｉｇｈｔ  Ｆｉｅｌｄ  での画像ブロック群を示す図である。
【図３】符号化装置の構成を示す図である。
【図４】符号化方法のフローチャートである。
【図５】コードブック作成装置の構成を示す図である。
【図６】コードブック作成方法のフローチャートである。
【図７】本発明と従来方法とを比較するための実験結果を示す図である。
【図８】本発明と従来方法とを比較するための実験結果を示す図である。
【符号の説明】
１  符号化装置
２  コードブック作成装置
１１  入力信号群メモリ
１２  コードブックメモリ
１３  選択部
１４  近似信号生成部
１５  誤差信号生成部
１６  信号群入力部
１７  インデックス符号化部
２１  入力学習データメモリ
２２  コードブックメモリ
２３  学習部
２４  誤差信号学習データ生成部
２５  入力学習データ入力部
【図１】
2004229100.tif 000010
【図２】
2004229100.tif 000011
【図３】
2004229100.tif 000012
【図４】
2004229100.tif 000013
【図５】
2004229100.tif 000014
【図６】
2004229100.tif 000015
【図７】
2004229100.tif 000016
【図８】
2004229100.tif 000017