(57)【要約】【課題】画像符号化における過完備な基底を用いた冗長変換において，エネルギーコンパクションが向上する変換係数の再構成によって符号化効率を向上させる。【解決手段】符号化対象信号に対して，冗長変換部１によって冗長系の変換基底を用いた変換を行い，更新変換係数算出部２による変換係数に対するノイズ・シェイピング処理により更新変換係数を算出する。変換係数再計算部３は，更新変換係数を逆変換した復号信号を近似するための冗長系の変換基底の数を一つずつ増加させながら，近似に用いる変換基底とその変換基底に対する変換係数を，近似誤差が所定値以下になるまで算出する処理を繰り返し，エネルギーコンパクションが最大化する変換係数の再計算を行う。【選択図】図４
2011029860.tif 000002
【特許請求の範囲】
【請求項１】
入力された映像信号に対して，冗長系の変換基底を用いた変換を行い，変換結果の変換係数を符号化する画像符号化装置であって，
前記冗長系の変換基底を用いた変換により得られた変換係数のうち，所定の閾値以下の変換係数を零値とするクリッピング処理によって更新変換係数を算出する更新変換係数算出手段と，
前記更新変換係数算出手段により算出された更新変換係数を逆変換し，得られた復号信号と前記冗長系の変換基底との内積を算出し，内積が最大となる変換基底を選び，その変換基底に対する変換係数を前記内積の最大値とし，その変換基底と変換係数とによって前記復号信号を近似し，さらにその近似誤差に対して，前記冗長系の変換基底における残りの変換基底との内積を算出して，その最大値とその最大値を与える変換基底とにより近似誤差を近似する処理を，所定の終了条件が満たされるまで繰り返し，前記更新変換係数を再計算する変換係数再計算手段と，
前記再計算された変換係数を符号化する符号化手段とを備える
ことを特徴とする画像符号化装置。
【請求項２】
請求項１記載の画像符号化装置において，
前記変換係数再計算手段における終了条件の一つは，前記近似誤差が予め与えられた誤差以下になった場合であり，前記変換係数再計算手段は，その終了条件が満たされた時点で近似に使用されていない変換基底の変換係数を零値に設定する
ことを特徴とする画像符号化装置。
【請求項３】
入力された映像信号に対して，冗長系の変換基底を用いた変換を行い，変換結果の変換係数を符号化する画像符号化方法であって，
前記冗長系の変換基底を用いた変換により得られた変換係数のうち，所定の閾値以下の変換係数を零値とするクリッピング処理によって更新変換係数を算出する更新変換係数算出過程と，
前記更新変換係数算出過程により算出された更新変換係数を逆変換し，得られた復号信号と前記冗長系の変換基底との内積を算出し，内積が最大となる変換基底を選び，その変換基底に対する変換係数を前記内積の最大値とし，その変換基底と変換係数とによって前記復号信号を近似し，さらにその近似誤差に対して，前記冗長系の変換基底における残りの変換基底との内積を算出して，その最大値とその最大値を与える変換基底とにより近似誤差を近似する処理を，所定の終了条件が満たされるまで繰り返し，前記更新変換係数を再計算する変換係数再計算過程と，
前記再計算された変換係数を符号化する符号化過程とを有する
ことを特徴とする画像符号化方法。
【請求項４】
請求項３記載の画像符号化方法において，
前記変換係数再計算過程における終了条件の一つは，前記近似誤差が予め与えられた誤差以下になった場合であり，前記変換係数再計算過程は，その終了条件が満たされた時点で近似に使用されていない変換基底の変換係数を零値に設定する
ことを特徴とする画像符号化方法。
【請求項５】
請求項３または請求項４記載の画像符号化方法を，コンピュータに実行させるための画像符号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，高能率画像信号符号化方法に関し，特にノイズ・シェイピングにおけるエネルギーコンパクションを向上させ, 符号化効率を向上させる画像符号化装置，画像符号化方法および画像符号化プログラムに関する。
【背景技術】
【０００２】
画像符号化における重要な要素技術の一つに，離散コサイン変換（ＤＣＴ：Discrete Cosine Transform ）に代表される変換符号化がある。画像符号化における変換符号化の役割は，空間的な画素間相関の除去を行うことにある。これは，符号化器の全体の位置づけとしては，変換符号化により少数の変換係数に情報を集中させ，変換係数に対する量子化により情報の集中度の低い変換係数を切り捨てることで，符号化対象信号に対する情報量の削減を図るものである。
【０００３】
図８に，映像信号を符号化する一般的な符号化装置１００の例を示す。符号化装置１００は映像信号を入力すると，予測部１０６により予測された予測信号との差分から予測残差信号を求め，変換部１０１により予測残差信号を直交変換する。その出力である変換係数を量子化部１０２にて量子化し，その量子化値をエントロピ符号化部１０７にて可変長符号化し，符号化ストリームとして出力する。一方，量子化部１０２の出力は，逆量子化部１０３で逆量子化され，さらに逆変換部１０４で逆直交変換される。その変換結果に予測信号を加えることにより復号信号が生成される。復号信号は，歪除去フィルタ１０５によりノイズ除去処理がなされ，参照復号信号として予測部１０６に入力される。予測部１０６では，動き探索などにより次の映像信号の符号化のための予測信号を生成する。
【０００４】
これまで，画像符号化への応用では，離散コサイン変換（ＤＣＴ）を始めとして，重複直交変換離散ウェーブレット変換（ＤＷＴ：Discrete Wavelet Transform）といった多くの変換符号化方式が検討されてきた。
【０００５】
例えば，変換符号化として，ＪＰＥＧでは離散コサイン変換（ＤＣＴ），ＪＰＥＧ２０００では離散ウェーブレット変換（ＤＷＴ）が採用されている。また，直交変換は完備な基底（complete basis）を用いるため，変換前後のデータ数が不変である。このため，直交変換は非冗長変換（non-redundant transform ）である。動画像符号化装置においては，図８における変換部１０１が上記の技術に該当する。
【０００６】
一方で，基底数が原信号のサンプル数よりも多い過完備な基底（overcomplete basis）を用いた冗長変換（redundant transform ）と呼ばれる変換がある。このため，冗長変換は直交変換になり得ないが，変換後のデータに冗長性を持たせることで，非冗長変換では実現できない特性を持つことができる。例えば，ダウンサンプリング処理を行わないＤＷＴである離散定常ウェーブレット変換（ＳＷＴ：Stationary Wavelet Transform）は変換後の冗長性より，ＤＷＴで失われるシフト不変性を成立させることができる。
【０００７】
また，画像処理分野では“方向分離特性をもつ変換”が注目されている。このような変換は，一般的に冗長変換であり，代表例としてＣｕｒｖｅｌｅｔ変換がある。並列木複素ウェーブレット変換（ＤＴＣＷＴ：Dual Tree Complex Wavelet Transform ）も同様の特性をもつ変換である。
【０００８】
方向分離特性をもつ変換は，画像信号中に含まれるエッジ等の曲線を２次元で定義される方向基底を用いて表現する変換である。方向基底を用いて２次元構造を高い精度で近似するため，ＤＷＴのような方向分離特性の乏しい変換と比較し，雑音除去や特徴抽出に対して有効である。
【０００９】
しかし，方向分離特性をもつ変換は，変換後のデータ数が増加するという問題がある。ｘを変換符号化への入力信号，Ψを変換行列とすると，変換により得られる変換係数ｙは，次式のように表わされる。
【００１０】
ｙ＝Ψｘ          (1) 
ＤＴＣＷＴの場合，ｘがｎ次元ベクトルだとすると，変換により得られる変換係数ｙは，２ｎ次元ベクトルとなる。このため，同変換を画像符号化へ応用する場合，データ数の削減の観点から，変換係数を適切に選択する必要がある。この変換係数の選択は，以下の制約条件付き最小化問題として定式化できる。
【００１１】
ｍｉｎy ‖ｙ‖0    subject to Φｙ＝ｘ        (2) 
ここで，ｍｉｎy は，後続する式の最小値を求める関数である。‖・‖0 はＬ0 ノルムであり，非ゼロ係数の個数を表している。Φは過完備な基底系からなる変換の逆変換を表す行列である。上記の制約条件付きの最小化問題は，ラグランジュの未定乗数法により以下の最小化問題に帰着される。
【００１２】
ｍｉｎy ‖ｙ‖0 ＋λ‖Φｙ−ｘ‖2 2         (3) 
ここで，λは外部から与えられる重みパラメータである。‖・‖2 2 はＬ2 ノルムの二乗値であり，二乗和を表す。第一項は選択された変換係数の個数であり，変換係数の情報量を近似した値である。第二項は変換係数の選択に伴う再構成誤差を表しており，符号化歪みを表している。しかし，上記の最小化問題はＮＰ困難であるため，従来，以下のようなＬ1 ノルムに最小化問題として近似する方法が採られてきた。
【００１３】
ｍｉｎy ‖ｙ‖1 ＋λ‖Φｙ−ｘ‖2 2         (4) 
ここで，‖・‖1 はＬ1 ノルムであり，ベクトルの要素の絶対値和を表している。
【００１４】
式(4) の最小化問題の準最適解を与える手法として，図９に示すノイズ・シェイピング(noise shaping) 処理と呼ばれる手法が提案されている（非特許文献１参照）。
【００１５】
使用する記号を整理する。入力信号ｘ（Ｎ画素）に対する順変換後の変換係数を，以下のように定義する。
【００１６】
ｙ0 ＝Ψｘ
Ｉを単位行列として，Ｐs ≡ΨΦ，Ｐ⊥≡Ｉ−ΨΦなる２種類の射影を定義する（なお，⊥はＰの右肩に付く添字である）。
【００１７】
前者の射影により得られる出力を有効成分，後者の射影により得られる出力を無効成分と呼ぶ。ノイズ・シェイピング処理における繰り返し回数を表すインデックスをｉで表し，ノイズ・シェイピング処理における第ｉ回目の出力をｙi とする。ｙi に対して，絶対値が閾値θi 以下となる係数を零値に切り捨てるクリッピング処理を行う。ｙi に対するクリッピング処理後の出力を＾ｙi （＾はｙの上に付く記号）として，次式のように表す。
【００１８】
＾ｙi （θi ) ＝  ｙi ＋εi （θi ）
ここで，εi （θi ）はクリッピング処理に伴い重畳する誤差（クリッピング誤差と呼ぶ）である。
【００１９】
図９におけるｗi （θi ）は  ノイズ・シェイピング処理における誤差の帰還信号であり，次式となる。
【００２０】
ｗi （θi ）＝ｋｙ0 −ｋΨΦ＾ｙi （θi ) 
この＾ｙi （θi ) ，ｗi （θi ）を用いて，ｙi+1 は，次式のように表される。
【００２１】
ｙi+1 （θi ，＾ｙi （θi ））＝＾ｙi （θi ) ＋ｗi （θi ）
図９に示すノイズ・シェイピング処理装置２００の動作について簡単に説明する。変換部２０１では，入力信号ｘに対して冗長系の変換基底を用いた変換を行い，変換係数ｙ0 を算出する。クリッピング処理部２０２では，変換係数ｙi （初期値はｉ＝０）と予め定められた閾値θi との大小比較を行い，ｙi がθi より小さければ，ｙi を０に置き換える。このクリッピング処理後の出力を＾ｙi とする。逆変換部２０３では，＾ｙi を逆変換して逆変換結果の＾ｘi を求める。入力信号ｘと＾ｘi との差が，画素領域での誤差ｅi となる。
【００２２】
重み係数乗算部２０４では，ｅi に所定の重み係数ｋを乗算し，乗算結果に対して，変換部２０５において順変換することにより，誤差の帰還信号ｗi を算出する。クリッピング処理部２０２の出力＾ｙi に誤差の帰還信号ｗi を加算することにより，更新変換係数ｙi+1 を算出する。遅延部２０６にて一定時間遅延させた後，更新変換係数ｙi+1 をクリッピング処理部２０２の入力として，更新変換係数ｙi+1 に対して同様に処理を繰り返す。終了条件判定部２０７では，ｅi+1 とｅi との差がある一定の微小値より小さくなったかどうかをチェックし，その差が微小値より小さい値になったときに，そのときの＾ｙi を変換結果として出力する。
【先行技術文献】
【非特許文献】
【００２３】
【非特許文献１】T.Reeves and N.Kingsbury,“Overcomplete image coding using iterative projection-based noise shaping”, Proc. IEEE Conf. on Image Processing, vol.3, pp.597-600, 2002.
【発明の概要】
【発明が解決しようとする課題】
【００２４】
ノイズ・シェイピングにおける誤差の帰還処理は，再構成信号に含まれるクリッピング誤差電力の低減を目的としたものである。このため，帰還処理前の信号と比べて，クリッピング誤差は低減するが，帰還処理後の変換係数に対するエネルギーコンパクションを直接的に最適化した処理ではないため，このエネルギーコンパクションの向上に改善の余地を残す。
【００２５】
本発明はかかる事情に鑑みてなされたものであって，過完備な基底を用いた冗長変換において，変換係数間の冗長性を除去するノイズ・シェイピング処理において，エネルギーコンパクションの向上を実現する変換係数の構成方法に基づく画像符号化方法を確立することを目的とする。
【課題を解決するための手段】
【００２６】
本発明は，上記課題を解決するため，入力された映像信号に対して，冗長系の変換基底を用いた変換を行い，得られた変換係数に対して，符号化誤差を低減する補正処理を行い，その結果を符号化する画像符号化において，同一の符号化誤差を保持しつつ，変換係数の再計算により，エネルギーコンパクションを最大化する変換係数を設定することを，もっとも主要な特徴とする。
【００２７】
変換係数の再計算により変換係数を設定する際には，変換係数の逆変換により復号信号（ベクトル値）を得て，使用する基底関数の中で方向が復号信号ともっとも近似するものを選んで復号信号を近似し，さらにその近似誤差に対して，使用する基底関数の数を一つずつ増加させながら近似誤差を近似する処理を繰り返し，近似誤差が，予め与えられた誤差以下になった場合に，その時点で近似に使用されていない，基底関数の変換係数を零値に設定する。
【発明の効果】
【００２８】
本発明により，ノイズ・シェイピング（noise shaping ）処理におけるエネルギーコンパクションを向上させ，特定成分への情報の集約を図ることで，符号化効率の向上を実現することができる。
【図面の簡単な説明】
【００２９】
【図１】冗長な信号表現と再構成誤差を説明する図である。
【図２】Ｏｖｅｒｃｏｍｐｌｅｔｅ系の基底を用いる場合の効率的な信号表現を説明する図である。
【図３】複数の係数ベクトルの中で情報量が小さくなる係数ベクトルを求める方法を説明する図である。
【図４】本発明の実施の形態に係る符号化装置の構成例を示す図である。
【図５】更新変換係数の算出処理のフローチャートである。
【図６】変換係数の再計算処理のフローチャートである。
【図７】ソフトウェアプログラムより実現するときのシステム構成図である。
【図８】一般的な符号化装置の構成図である。
【図９】従来のノイズ・シェイピング処理装置の例を示す図である。
【発明を実施するための形態】
【００３０】
本発明の実施形態を説明するに先立ち，本発明の基本的な技法の概要について説明する。［背景技術］で説明したノイズ・シェイピング処理におけるクリッピング処理に伴い重畳するクリッピング誤差εi （θi ）の有効成分，および無効成分を各々，
εi （θi ）s ＝Ｐs εi （θi ）
εi （θi ）⊥＝Ｐ⊥εi （θi ）
とする（⊥は右上に付く添字）。ｉ＋１回の繰返し処理の結果，得られる変換係数ｙi+1 （θi ，＾ｙ（θi ））は，εj （θj ）⊥および〜εj,i （θj ）s （なお，〜はεの上に付く記号）を用いて，次式のように表される。
【００３１】
【数１】
2011029860.tif 000003
【００３２】
ここで，〜εj,i （θj ）s は，次式のように定義する。
【００３３】
〜εj,i （θj ）s ＝（１−ｋ）i-j+1 εj （θj ）s             (5) 
なお，ｋ＝１の場合，                                                                〜εj,i （θj ）s ＝０
となることから，変換係数ｙi+1 （θi ，＾ｙ（θi ））は，次式となる。
【００３４】
【数２】
2011029860.tif 000004
【００３５】
変換係数ｙi+1 （θi ，＾ｙ（θi ））は，エネルギーコンパクションに関して，最適な構成となってはいない。そこで，同変換係数ｙi+1 （θi ，＾ｙ（θi ））と同一の再構成誤差を保持しつつ，エネルギーコンパクションを向上させる変換係数を算出する。
【００３６】
まず，ｙi+1 （θi ，＾ｙ（θi ））を逆変換して，再構成画素信号を算出する。
【００３７】
ｘi+1 ＝Φｙi+1 （θi ，＾ｙ（θi ））
次に，ＤＴＣＷＴの変換基底をψn （ｎ＝１，…，２Ｎ）とし，同基底を用いた変換係数の構成法を以下に述べる。なお，ψn はΨの第ｎ行ベクトルにあたる。以下では，簡単のため，ｘi+1 をｘと略記する。ｘとψn （ｎ＝１，…，２Ｎ）との内積を計算し，２Ｎ個の基底の中で，内積が最大となる基底ψm1を求める。次に，ψm1に対する変換係数をｃm1＝＜ｘ，ψm1＞として，ψm1を用いてｘを近似した場合の誤差ｒ1 を，
ｒ1 ＝ｘ−ｃm1ψm1
とする。なお，＜ｘ，ψm1＞は，ｘとψm1との内積を表す。
【００３８】
このｒ1 に対して，ψn （ｎ＝１，…，２Ｎ，ｎ≠ｍ1 ) との内積を計算し，２Ｎ−１個の基底の中で，内積が最大となる基底ψm2を求める。ψm2に対する変換係数をｃm2＝＜ｒ1 , ψm2＞として，ψm2を用いてｒ1 を近似した場合の誤差ｒ2 を，
ｒ2 ＝ｒ1 −ｃm2ψm2
として，同様の処理を繰り返す。
【００３９】
繰り返しの終了条件は，ｋ≠１の場合とｋ＝１の場合とで異なる。
【００４０】
ｋ≠１の場合，
【００４１】
【数３】
2011029860.tif 000005
【００４２】
を満たすか，もしくはｎ＝２Ｎとなるまで繰り返す。
【００４３】
ｋ＝１の場合，ｒn ＝０（ｎ＝１，…，２Ｎ）を満たすか，もしくはｎ＝２Ｎとなるまで繰り返す。
【００４４】
以上の処理によって，変換係数が同一の再構成誤差を保ったまま，エネルギーコンパクションの大きな変換係数に変換される理由について簡単に説明する。
【００４５】
図１は，冗長な信号表現と再構成誤差を説明する図である。冗長変換としてＤＴＣＷＴを例にして説明する。
【００４６】
ＤＴＣＷＴでは，図１（Ａ）に示すように，Ｎ個の入力画素数に対して，ＤＴＣＷＴにより２Ｎ個の変換係数が出力される。図１（Ｂ）に示すように，画素領域をＸとし，ＣＷＴ係数領域をＹとする。原画像を表すベクトルは，ＣＷＴによってＣＷＴ係数領域の係数ベクトルに変換されるが，この変換は冗長変換であるため，逆ＣＷＴの変換例に示すように，一枚の画像を表す係数ベクトルが複数存在することになる。すなわち，Ｙ領域における点線枠内のどの係数ベクトルを用いても，逆ＣＷＴによって同一の復号画像が生成され，この復号画像と原画像との誤差は一定になる。
【００４７】
したがって，同一の復号画像を生成することができる複数の係数ベクトルの中で，情報量が最小となる係数ベクトルを求めることができれば，符号化効率を向上させることができる。この目標を達成するための方策は，係数間の偏りが大きくなるように係数ベクトルを構成することである。すなわち，係数間の偏りが大きくなるように係数ベクトルを構成することによって，エネルギーコンパクションが大きくなり，符号化効率の向上につながる。
【００４８】
図２は，Ｏｖｅｒｃｏｍｐｌｅｔｅ系の基底を用いる場合の効率的な信号表現を説明する図である。ベクトルｘを２つの基底関数（基底ベクトル）ψ１，ψ２を用いて表すと，図２（Ａ）に示すようになる。なお，δは量子化の影響で丸められる値を示している。
【００４９】
Ｏｖｅｒｃｏｍｐｌｅｔｅな基底系の場合，信号の次元数より多い基底関数が用意される。図２（Ｂ）にその例を示す。図２（Ａ）と図２（Ｂ）とを比較すれば明らかなように，図２（Ｂ）のほうが，図２（Ａ）の場合よりも少ない情報量で表現することができることがわかる。
【００５０】
図３は，複数の係数ベクトルの中で情報量が小さくなる係数ベクトルを求める方法を説明する図である。
【００５１】
本発明では，図９で説明したような従来のノイズ・シェインピング処理で算出された変換係数ｙi+1 （θi ，＾ｙ（θi ））と同一の再構成誤差を保持しつつ，エネルギーコンパクションを向上させる変換係数を算出するため，まず，変換係数ｙi+1 （θi ，＾ｙ（θi ））を逆変換し，その逆変換結果をベクトルｘとして，ｘとΨの第ｎ行ベクトルにあたる変換基底ψn （ｎ＝１，…，２Ｎ）との内積を計算する。これはｘをψ方向へ射影し，ψを用いてｘを表現した場合の近似ベクトルを求めるためである。
【００５２】
二つのベクトルｘ，ψの内積をとる処理は，原信号ベクトルｘをψ方向に射影し，そのψ方向での振幅を求めることに相当する。つまり，内積ｃは，ｘが持つψ方向の成分と言える。このことから，図３（Ａ）に示すようにしてｘの近似ベクトルを求める。同図で，ψは単位ベクトルとする。ｘをψ方向へ射影したベクトルの長さは，ｘとψとの内積であり，これをｃとすれば，ｃ＝＜ｘ，ψ＞である。このベクトルは，ｃψである。このようなψn の中で，内積が最大となる基底ψを求めることは，原信号ベクトルｘを各ψn 方向（ｎ＝１，…，２Ｎ）へ射影した中で，ｘに最も近似するベクトルｃψを求めることに相当する。
【００５３】
このようにして近似したベクトルｃψと原信号ベクトルｘとの誤差ベクトルｒは，図３（Ｂ）に示すようなベクトルｒ（ｒ＝ｘ−ｃψ）となる。この内積が最大となるψをψm1とすると，次にψm1を除いた変換基底ψn （ｎ＝１，…，２Ｎ）の中で，誤差ベクトルｒ（ｒ1 とする）に最も近似するものを求めるため，ｒ1 とψn （ψm1を除く）との内積を計算し，それが最大となる基底ψm2を求める。その内積は，ｃm2＝＜ｒ1 , ψm2＞であり，ψm2を用いてｒ1 を近似した場合の誤差ｒ2 は，
ｒ2 ＝ｒ1 −ｃm2ψm2
となる。同様に，この近似誤差をψn の一つの基底を用いて近似する処理を，近似誤差が０またはある値より小さくなるなどの所定の終了条件が満たされるまで繰り返すことにより，同一の復号画像を生成することができる複数の係数ベクトルの中で，係数間の偏りが大きくなる係数ベクトルが選択されることになり，エネルギーコンパクションが向上することになる。
【００５４】
以下，本発明の実施の形態の具体例を，図面を用いて説明する。図４は，本発明の実施の形態に係る符号化装置の構成例を示す図である。
【００５５】
本発明の実施の形態に係る符号化装置は，例えば図８に示すような符号化装置１００において，変換部１０１の部分を，図１に示す冗長変換部１，更新変換係数算出部２，変換係数再計算部３に置き換えたものである。
【００５６】
図１における冗長変換部１および更新変換係数算出部２は，図９で説明したようなノイズ・シェイピング処理装置２００の処理機能を実現する部分である。すなわち，冗長変換部１は，冗長系の変換基底を用いて符号化対象信号を変換係数に変換する。更新変換係数算出部２は，クリッピング処理部２０によって所定の閾値より小さい変換係数を零値とするクリッピングを行い，そのクリッピング誤差の帰還処理によって，クリッピング誤差が低減するように変換係数を更新する。
【００５７】
変換係数再計算部３は，本発明の特徴的な部分であり，更新変換係数算出部２が算出した更新変換係数を，同一の符号化誤差を保持しつつ，エネルギーコンパクションが大きくなるように再計算する。
【００５８】
変換係数再計算部３における逆変換部３０は，更新変換係数算出部２が出力した更新変換係数を逆変換し，逆変換した結果の再構成画素信号をバッファ３１に格納する。
【００５９】
内積最大基底算出部３２は，バッファ３１に格納された信号（ベクトル）について，変換基底ψn との内積を算出し，２Ｎ−ｉ個（ｉは０，１，２，…と順次増加）の基底の中で，内積が最大となる基底ψm を求め，その基底ψm とそのときの内積（変換係数ｃm ）を，変換係数・基底記憶部３３に格納する。
【００６０】
バッファ更新部３４は，変換係数・基底記憶部３３に格納された変換基底ψm を用いて，バッファ３１に格納されている信号ベクトルを近似したときの誤差を計算し，その誤差の値をバッファ３１に上書きする。
【００６１】
内積最大基底算出部３２は，バッファ３１に書き込まれた誤差ベクトルに対して，既に誤差ベクトルの算出に用いた基底を除いた変換基底との内積を計算し，同様に最大のものを算出する処理を繰り返す。バッファ更新部３４も，内積最大基底算出部３２の算出結果からバッファ３１の更新を繰り返す。
【００６２】
終了条件判定部３５は，繰り返しの終了条件を判定する。繰り返しの終了条件は，例えば次のようにする。誤差の帰還信号に対する所定の重み係数ｋ（図９参照）が１の場合，バッファ３１に格納された誤差ベクトルの要素ｒn がすべて０になったか，すべての変換基底ψn に対する処理が終わったときとする。重み係数ｋが１ではない場合，誤差ベクトルの要素ｒn の二乗和がクリッピング誤差の有効成分の二乗和Ｓ以下になったか，すべての変換基底ψn に対する処理が終わったときとする。
【００６３】
以上の終了条件が満たされた場合，変換係数出力部３６は，変換係数・基底記憶部３３に格納された変換係数を，再構成後の変換係数として出力する。
【００６４】
この再構成後の変換係数は，量子化部４によって量子化され，エントロピ符号化部５によって可変長符号化されて，符号化ストリームとして出力される。
【００６５】
図５は，更新変換係数の算出処理のフローチャートである。図４に示す更新変換係数算出部２が図５に示すステップＳ１〜Ｓ７を実行し，変換係数再計算部３がステップＳ８を実行する。ステップＳ８の詳細については，図６に示す。
【００６６】
更新変換係数算出部２は，冗長変換部１が符号化対象信号を変換した結果の変換係数を読み込む（ステップＳ１）。また，クリッピング処理部２０で用いるクリッピングの閾値を読み込む（ステップＳ２）。
【００６７】
クリッピング処理部２０で，閾値以下の変換係数の値を零値とするクリッピング処理を行い，修正変換係数を得る（ステップＳ３）。次に，そのクリッピング処理で得られた修正変換係数を逆変換し，復号信号を得る（ステップＳ４）。続いて，復号信号と原信号の差分信号を算出する。この差分信号は，レジスタに格納しておく（ステップＳ５）。
【００６８】
差分信号を順変換し，補正係数を得る（ステップＳ６）。この補正係数を修正変換係数に加算して，更新変換係数を書き出す（ステップＳ７）。以上の処理は，図９で説明したノイズ・シェイピング処理による変換係数の更新と同様であり，復号信号と原信号との差分信号の変化が微小値以下になるまで繰り返す。
【００６９】
次に，変換係数再計算部３は，変換係数のエネルギーコンパクションを向上させるために，更新変換係数算出部２が算出した更新変換係数を逆変換し，復号信号を得て，同復号信号に対して変換係数を再計算する（ステップＳ８）。以下，この処理の詳細を図６を用いて説明する。
【００７０】
図６は，変換係数の再計算処理のフローチャートである。変換係数再計算部３は，逆変換部３０によって更新変換係数を逆変換し，逆変換結果の復号信号をバッファ３１に格納する（ステップＳ１０）。以下，バッファ３１に格納された信号をｒと表す。
【００７１】
次に，参照マップＭ［ｎ］（ｎ＝１，２，…，２Ｎ）を，１に初期化する（ステップＳ１１）。この参照マップＭ［ｎ］は，変換基底（基底関数ともいう）ψn （ｎ＝１，…，２Ｎ）に対するｒの射影が行われたかどうかを示すものであり，“１”は未処理，“０”は処理済みを表す。
【００７２】
まず，ｎ＝１，２，…，２Ｎのうち，Ｍ［ｎ］＝１を満たすｎに対して，ステップＳ１３以下の処理を実行する（ステップＳ１２）。Ｍ［ｎ］がすべて０になったら処理終了とする。
【００７３】
バッファ３１内の信号ｒに対して，Ｍ［ｎ］＝１である基底関数ψn との内積を算出し，内積が最大となる基底関数を求める。その内積の最大値および内積の最大値を実現する基底関数を，ｃmi+1およびψmi+1として，変換係数・基底記憶部３３に格納する（ステップＳ１３）。ｃmi+1は，信号ｒのベクトルが持つψmi+1方向の成分を意味する。
【００７４】
バッファ更新部３４は，バッファ３１内の信号ｒと，ｃmi+1ψmi+1との差分（誤差）を算出し，結果を新たな信号ｒとしてバッファ３１に格納する（ステップＳ１４）。そして，参照マップＭ［ｎ］中のＭ［ｍi+1 ］を０に更新する（ステップＳ１５）。
【００７５】
次に，終了条件の判定のために，信号ｒの要素ｒn の二乗和‖ｒ‖を算出する（ステップＳ１６）。誤差の帰還信号に対する重み係数ｋが１かどうかを判定し（ステップＳ１７），１の場合にはステップＳ１８へ進み，１でない場合にはステップＳ２０へ進む。
【００７６】
ｋ＝１の場合，信号ｒの要素の二乗和‖ｒ‖が０かどうかを判定し（ステップＳ１８），０でなければ，ステップＳ１２へ戻って，同様に処理を繰り返す。０であれば，ｎ＝１，２，…，２Ｎのうち，Ｍ［ｎ］＝１を満たすｎに対して，変換係数ｃn ＝０とし（ステップＳ１９），処理を終了する。
【００７７】
また，ｋ≠１の場合，クリッピング誤差の有効成分の二乗和Ｓを算出し（ステップＳ２０），信号ｒの要素の二乗和‖ｒ‖がＳ以下かどうかを判定する（ステップＳ２１）。Ｓ以下でなければ，ステップＳ１２へ戻って，同様に処理を繰り返す。Ｓ以下であれば，ｎ＝１，２，…，２Ｎのうち，Ｍ［ｎ］＝１を満たすｎに対して，変換係数ｃn ＝０とし（ステップＳ２２），処理を終了する。
【００７８】
以上の画像符号化の処理は，コンピュータとソフトウェアプログラムとによっても実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録することも，ネットワークを通して提供することも可能である。
【００７９】
図７は，本発明をソフトウェアプログラムを用いて実現する場合のシステムの構成例を示している。メモリ５２には，本発明の画像符号化処理を行うための画像符号化プログラム５３が格納される。ＣＰＵ５０は，メモリ５２に格納された画像符号化プログラム５３の命令を逐次フェッチして実行する。映像記憶装置５１は，符号化対象の映像信号を記憶する装置である。映像信号は，図示省略したカメラ等から入力するようにしてもよい。画像符号化プログラム５３によって生成された符号化ストリームは，符号化ストリーム記憶装置５４に格納される。または，ネットワークアダプタ等のインタフェースを介して，符号化ストリームを外部装置に出力してもよい。システムバス５５は，ＣＰＵ５０，映像記憶装置５１，メモリ５２，符号化ストリーム記憶装置５４を接続するバスである。
【符号の説明】
【００８０】
１    冗長変換部
２    更新変換係数算出部
２０  クリッピング処理部
３    変換係数再計算部
３０  逆変換部
３１  バッファ
３２  内積最大基底算出部
３３  変換係数・基底記憶部
３４  バッファ更新部
３５  終了条件判定部
３６  変換係数出力部
４    量子化部
５    エントロピ符号化部
【図１】
2011029860.tif 000006
【図２】
2011029860.tif 000007
【図３】
2011029860.tif 000008
【図４】
2011029860.tif 000009
【図５】
2011029860.tif 000010
【図６】
2011029860.tif 000011
【図７】
2011029860.tif 000012
【図８】
2011029860.tif 000013
【図９】
2011029860.tif 000014