画像符号化方法，画像符号化装置および画像符号化プログラム
【課題】交互射影法におけるエネルギーコンパクションを向上させ，特定成分への情報の集約を図ることで，符号化効率を向上させる。
【解決手段】係数選択処理部２０は，画像の領域を分割する複数の分割候補となる位置のそれぞれについて分割位置を設定し，設定された分割位置で画像の領域を分割する。その領域分割の候補の中で，全分割領域の係数の総数が一定という条件下で，全領域の歪み量の総和またはさらに分割領域の境界部の不連続性を最小化する最適な領域分割を選択し，その各分割領域に対する変換係数の選択を行う。
【解決手段】係数選択処理部２０は，画像の領域を分割する複数の分割候補となる位置のそれぞれについて分割位置を設定し，設定された分割位置で画像の領域を分割する。その領域分割の候補の中で，全分割領域の係数の総数が一定という条件下で，全領域の歪み量の総和またはさらに分割領域の境界部の不連続性を最小化する最適な領域分割を選択し，その各分割領域に対する変換係数の選択を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，高能率画像信号符号化方法に関し，特に交互射影法におけるエネルギーコンパクションを向上させて符号化効率を向上させるための画像符号化方法に関する。
【背景技術】
【０００２】
画像符号化における重要な要素技術の一つに，離散コサイン変換（ＤＣＴ：Discrete Cosine Transform ）に代表される変換符号化がある。画像符号化における変換符号化の役割は，空間的な画素間相関の除去を行うことにある。符号化器の全体の位置づけとしては，変換符号化により少数の変換係数に情報を集中させ，変換係数に対する量子化により情報の集中度の低い変換係数を切り捨てることで，符号化対象信号に対する情報量の削減に寄与する。
【０００３】
図７に，映像信号を符号化する一般的な符号化装置１００の例を示す。符号化装置１００は映像信号を入力すると，予測部１０６により予測された予測信号との差分から予測残差信号を求め，変換部１０１により予測残差信号を直交変換する。その出力である変換係数を量子化部１０２にて量子化し，その量子化値をエントロピ符号化部１０７にて可変長符号化し，符号化ストリームとして出力する。一方，量子化部１０２の出力は，逆量子化部１０３で逆量子化され，さらに逆変換部１０４で逆直交変換される。その変換結果に予測信号を加えることにより復号信号が生成される。復号信号は，歪除去フィルタ１０５によりノイズ除去処理がなされ，参照復号信号として予測部１０６に入力される。予測部１０６では，動き探索などにより次の映像信号の符号化のための予測信号を生成する。
【０００４】
これまで，画像符号化への応用では，離散コサイン変換（ＤＣＴ）を始めとして，重複直交変換離散ウェーブレット変換（ＤＷＴ：Discrete Wavelet Transform）といった多くの変換符号化方式が検討されてきた。例えば，変換符号化として，ＪＰＥＧでは，離散コサイン変換（ＤＣＴ），ＪＰＥＧ ２０００では，離散ウェーブレット変換（ＤＷＴ）が採用されている。また，直交変換は完備な基底（complete basis）を用いるため，変換前後のデータ数が不変である。このため，直交変換は非冗長変換（non-redundant transform ）である。動画像符号化装置においては，図７における変換部１０１が上記の技術に該当する。
【０００５】
一方で，基底数が原信号のサンプル数よりも多い過完備な基底（overcomplete basis）を用いた冗長変換（redudant transform）と呼ばれる変換がある。このため，冗長変換は直交変換になり得ないが，変換後のデータに冗長性を持たせることで非冗長変換では実現できない特性をもつことができる。例えば，ダウンサンプリング処理を行わないＤＷＴである離散定常ウェーブレット変換（ＳＷＴ：Stationary Wavelet Transform）は変換後の冗長性により，ＤＷＴで失われるシフト不変性を成立させることができる。
【０００６】
また，画像処理分野では，“方向分離特性をもつ変換”が注目されている。このような変換は，一般的に冗長変換であり，代表例としてＣｕｒｖｅｌｅｔ変換がある。並列木複素ウェーブレット変換（ＤＴＣＷＴ：Dual Tree Complex Wavelet Transform ）も同様の特性をもつ変換である。方向分離特性をもつ変換は，画像信号中に含まれるエッジ等の曲線を２次元で定義される方向基底を用いて表現する変換である。方向基底を用いて２次元構造を高い精度で近似するため，ＤＷＴのような方向分離特性の乏しい変換と比較し，雑音除去や特徴抽出に対して，有効である。
【０００７】
しかし，方向分離特性をもつ変換は，変換後のデータ数が増加するという問題がある。ｘを変換符号化への入力信号，Ψを変換行列とすると，変換により得られる変換係数ｙは，次式のように表わされる。
【０００８】
ｙ＝Ψｘ (1)
一方，変換係数から信号領域での値を復号する処理は，過完備な基底系からなる変換の逆変換を表す行列をΦとすると，次式のように表わされる。
【０００９】
ｘ＝Φｙ (2)
ＤＴＣＷＴの場合，ｘがｎ次元ベクトルであるとすると，変換により得られる変換係数ｙは２ｎ次元ベクトルとなる。このため，同変換を画像符号化へ応用する場合，データ数の削減の観点から，変換係数を適切に選択する必要がある。この変換係数の選択は，以下の制約条件付き最小化問題として定式化できる。
【００１０】
ｍｉｎy ‖ｙ‖0 ｓｕｂｊｅｃｔ ｔｏ Φｙ＝ｘ (3)
ここで，‖・‖0 は，Ｌ0 ノルムであり，非ゼロ係数の個数を表している。上記の制約条件付きの最小化問題は，ラグランジュの未定乗数法により以下の最小化問題に帰着される。
【００１１】
ｍｉｎy ‖ｙ‖0 ＋λ‖Φｙ−ｘ‖2 2 (4)
ここでλは，外部から与えられる重みパラメータである。第一項は，選択された変換係数の個数であり，変換係数の情報量を近似した値である。第二項は変換係数の選択に伴う再構成誤差を表しており，符号化歪みを表している。‖・‖2 2 は，Ｌ2 ノルムの二乗値であり，二乗和を表す。しかし，上記の最小化問題はＮＰ困難であるため，従来，以下のようなＬ1 ノルムに最小化問題として近似する方法がとられてきた。
【００１２】
ｍｉｎy ‖ｙ‖1 ＋λ‖Φｙ−ｘ‖2 2 (5)
ここで，‖・‖は，Ｌ1 ノルムであり，ベクトルの要素の絶対値和を表している。
【００１３】
式(5) の最小化問題の準最適解を与える手法として，交互射影法と呼ばれる手法が提案されている（非特許文献１参照）。
【００１４】
式(3) は，以下の条件付最小化問題
【００１５】
【数１】
【００１６】
と等価であることに着目すると，上式はｘとのユークリッド距離を最小化するＫ個の非ゼロ係数を持つｙを探していると解釈することができる。上式の最小化を実現する解を求めるため，式(2) の解としての集合（アフィン集合）Ｓ（Φ，ｘ）とＣ（Ｋ）の間の交互直交射影を繰り返す。Ｃ（Ｋ）からＳ（Φ，ｘ）への直交射影は，
【００１７】
【数２】
【００１８】
で与えられる。ここで，ｙLSは二乗誤差最小化の規範の基づき，
ｙLS＝ΦT ［ΦΦT ］-1ｘ
により求められた係数ベクトルである。また，Ｓ（Φ，ｘ）からＣ（Ｋ）への直交射影は，ｈｔ（ｙ，Ｋ）により与えられる。ここで，ｈｔ（ｙ，Ｋ）は，Ｃ（Ｋ）へのユークリッド距離を最小にする射影であり，最も大きい値からＫ個の係数を選択する操作に相当する。
【００１９】
係数の初期ベクトルをｙ(0) とおき，次の漸化式に従い，繰り返し処理を行う。
【００２０】
【数３】
【００２１】
なお，この繰り返し処理は，以下の終了条件を満たすまで繰り返す。
【００２２】
‖ｙ(n+1) −ｙ(n) ‖2 ＜ε
このような過完備系を用いた変換は，画像信号にｓｐａｒｓｅｎｅｓｓを仮定し，少数の変換係数で画像を表現するｓｐａｒｓｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎの一種である。
【先行技術文献】
【非特許文献】
【００２３】
【非特許文献１】L. Mancera and J. Portilla, “ L0-norm-based sparse representation through alternate projections”，IEEE ICIP, Oct., 2006.
【発明の概要】
【発明が解決しようとする課題】
【００２４】
画像信号は空間的な局所性を有しており，その性質は一様ではない。つまり，画像信号を一定の精度で表現するために必要な変換係数の個数，あるいは，一定の個数の変換係数で表現可能な画像信号の表現精度は，画像内の領域の性質に応じて変動する。しかし，交互射影法は，画像全体に対して適用されている。このため，画像内の局所性を考慮できておらず，符号化効率の向上に改善の余地を残す。
【００２５】
本発明はかかる事情に鑑みてなされたものであって，過完備な基底を用いた冗長変換において，変換係数間の冗長性を除去する交互射影法において，符号化効率の向上を実現する画像分割手法に基づく画像符号化方法を確立することを目的とする。
【課題を解決するための手段】
【００２６】
本発明は，上記課題を解決するため，入力された映像信号に対して，冗長系の変換基底を用いた変換を行い，得られた変換係数に対して，符号化に用いる係数の絞り込みを行う画像符号化において，画像の局所的な性質に応じて，画面内の係数総数が一定（全分割領域の係数総数が一定）という条件下で全領域の歪み量の総和を最小化するための領域分割，および，各分割領域に対する変換係数の選択を行うことを特徴とする。
【００２７】
本発明は，画面内を性質の類似した領域に分割し，分割領域ごとにコストが小さくなる変換係数の選択を行うことにより，符号化効率を向上させることができる。
【００２８】
また，本発明は，入力された映像信号に対して，冗長系の変換基底を用いた変換を行い，得られた変換係数に対して，符号化に用いる係数の絞り込みを行う画像符号化において，画像の局所的な性質に応じて，画面内の係数総数が一定（全分割領域の係数総数が一定）という条件下で全領域の歪み量の総和および分割領域の境界部の不連続性を最小化するための領域分割，および，各分割領域に対する変換係数の選択を行うことを特徴とする。
【００２９】
また，本発明は，上記発明において，分割領域の係数の個数を，同分割領域の画素数に応じて設定することを特徴とする。
【００３０】
また，本発明は，上記発明において，選択された領域分割における各分割領域に対して，所定の分割の終了条件が満たされるまで，領域分割および変換係数を選択する処理を再帰的に繰り返すことを特徴とする。分割の終了条件は，例えば一方の分割領域の画素数が所定の閾値以下となること，または一方の分割領域の変換係数の個数が所定の閾値以下となることである。また，分割を行わないほうが最適な場合も分割の終了条件となる。
【発明の効果】
【００３１】
本発明により，画像の局所性を考慮して係数選択を行うことで，交互射影法におけるエネルギーコンパクションを向上させ，特定成分への情報の集約を図ることで，符号化効率の向上を実現することができる。
【図面の簡単な説明】
【００３２】
【図１】本発明の実施形態に係る画像符号化装置の構成例を示す図である。
【図２】係数選択処理部が実行する係数選択処理フローを示す図である。
【図３】最適分割処理部が実行する最適分割処理フローを示す図である。
【図４】最適分割処理部が実行する最適分割処理フローを示す図である。
【図５】コスト算出部が実行するコスト関数算出処理フローを示す図である。
【図６】ソフトウェアプログラムより実現するときのシステム構成図である。
【図７】一般的な符号化装置の構成図である。
【発明を実施するための形態】
【００３３】
以下，本発明の実施の形態について，図面を用いて説明する。
【００３４】
本発明の基本方針は，画面内を性質の類似した領域に分割し，分割領域ごとにｓｐａｒｓｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎを適用することである。以下，４種類の処理を示す。
【００３５】
［領域分割方法１］は，画面内の係数総数が一定（全分割領域の係数総数が一定）という条件下で全領域の歪み量の総和を最小化するための分割，およびパラメータ選択方法を示す。
【００３６】
［領域分割方法２］は，各分割領域において画素当りの係数の個数が一定という条件下で，各領域の歪み量を最小化するための分割，およびパラメータ選択方法を示す。
【００３７】
［領域分割方法３］は，［領域分割方法１］におけるコスト関数に対して領域境界の不連続性の影響を加味した修正を行ったものである。
【００３８】
同様に，［領域分割方法４］は，［領域分割方法２］におけるコスト関数に対して領域境界の不連続性の影響を加味した修正を行ったものである。
【００３９】
画像信号の存在領域を０≦ｓ≦Ｗ，０≦ｔ≦Ｈとし，同領域内の画素値を一次元ベクトルとして並べ替えたものをｘとする。さらに，同領域内から，左上角の座標値を（ｓ0 ，ｔ0 ），水平方向・垂直方向の辺長をｗ，ｈとする矩形領域内の画素値を抽出し，一次元ベクトルとして並べ替えたベクトルをｘ（ｓ0 ，ｔ0 ，ｗ，ｈ）とする。
【００４０】
ｘ（ｓ0 ，ｔ0 ，ｗ，ｈ）に対して，交互射影法を用いてｋ個の変換係数｛ｃ0 ，…，ｃk-1 ｝を選択し，選択された基底信号を用いてｘ（ｓ0 ，ｔ0 ，ｗ，ｈ）を表現した場合の近似誤差をＥ［ｘ，ｓ0 ，ｔ0 ，ｗ，ｈ，ｋ，Ｃ］とおく。ここで，Ｃは，ｋ個の変換係数Ｃ＝｛ｃ0 ，…，ｃk-1 ｝を表す。例えば，ＤＴＣＷＴの場合，総数２ｎ個の係数の中からｋ個の係数を選択したことになり，この選択に交互射影法を用いることができる。
【００４１】
［領域分割方法１］
画面内の係数総数が一定（全分割領域の係数総数が一定）という条件下で全領域の歪み量の総和を最小化するための分割を考える。さらに，垂直に２分割する場合と水平に２分割する場合の結果を比較し，上記歪み量最小化の規範に基づき，垂直分割・水平分割のいずれかを選択する。
【００４２】
歪み量の尺度として次の近似誤差を用いる。
【００４３】
Ξhor ［ｘ，０，ｈ，Ｗ，Ｈ，ｋh ，ｋ−ｋh ，Ｃu ，Ｃd ］＝Ｅ［ｘ，０，０，Ｗ，ｈ，ｋh ，Ｃd ］＋Ｅ［ｘ，０，ｈ，Ｗ，Ｈ−ｈ，ｋ−ｋh ，Ｃu ］
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，上側領域０≦ｓ≦Ｗ，０≦ｔ≦ｈ−１と，下側領域０≦ｓ≦Ｗ，ｈ≦ｔ≦Ｈに分割し，上側領域および下側領域を各々，ｋh 個の係数およびｋ−ｋh 個の係数で表現した場合の近似誤差和を表している。
【００４４】
Ξver ［ｘ，ｗ，０，Ｗ，Ｈ，ｋw ，ｋ−ｋw ，Ｃl ，Ｃr ］＝Ｅ［ｘ，０，０，ｗ，Ｈ，ｋw ，Ｃl ］＋Ｅ［ｘ，ｗ，０，Ｗ−ｗ，Ｈ，ｋ−ｋw ，Ｃr ］
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，左側領域０≦ｓ≦ｗ−１，０≦ｔ≦Ｈと，右側領域ｗ≦ｓ≦Ｗ，０≦ｔ≦Ｈに分割し，左側領域および右側領域を各々，ｋw 個の係数およびｋ−ｋw 個の係数で表現した場合の近似誤差和を表している。
【００４５】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，垂直方向に２分割する場合，次式に基づき分割位置，および分割後の各領域へ割り当てられる係数の個数を決定する。垂直方向に２分割する場合の分割位置ｈ0 ，および上側の分割領域で用いる変換係数の個数ｋ0,h は，次式で与えられる（下側の分割領域で用いる変換係数の個数はｋ−ｋ0,h となる）。
【００４６】
【数４】
【００４７】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，水平方向に２分割する場合，次式に基づき分割位置，および分割後の各領域へ割り当てられる係数の個数を決定する。水平方向に２分割する場合の分割位置ｗ0 ，および左側の分割領域で用いる変換係数の個数ｋ0,w は次式で与えられる（なお，右側の分割領域で用いる変換係数の個数は，ｋ−ｋ0,w となる）。
【００４８】
【数５】
【００４９】
このとき，
Ξhor ［ｘ，０，ｈ0 ，Ｗ，Ｈ，ｋ0,h ，ｋ−ｋ0,h ，Ｃu ，Ｃd ］
≦Ξver ［ｘ，ｗ0 ，０，Ｗ，Ｈ，ｋ0,w ，ｋ−ｋ0,w ，Ｃl ，Ｃr ］
となる場合には，ｔ＝ｈ0 の位置で垂直方向に分割を行うこととし，それ以外の場合には，ｓ＝ｗ0 の位置で水平方向に分割を行うこととする。なお，ｈ0 ＝０あるいはｗ0 ＝０となる場合，分割を行わないほうが最適であるので分割は行われない。
【００５０】
上式は，分割位置および各分割領域へ割り当てられる変換係数の個数を求めている。
【００５１】
分割により得られた矩形領域の中で近似誤差が最大の領域（分割対象領域）に対して，分割対象領域に含まれる係数の個数を上式におけるｋとみなして，上記と同様の分割処理を施す。選択した領域に対して分割が行われなかった場合には，先に選択された領域の次に近似誤差が大きな領域に対して，上記と同様の分割処理を施す。この繰り返しは，全ての分割領域に対して分割が行われなくなるまで続ける。または，分割領域内の画素数の下限値を設定しておき，分割の結果，この下限値を下回るような領域は生成されないように制限を設けることも可能である。
【００５２】
［領域分割方法２］
２つの分割領域において画素当りの係数の個数が一定という条件下で，各領域の歪み量を最小化するための分割を考える。さらに，垂直に２分割する場合と水平に２分割する場合の結果を比較し，上記加重和最小化の規範に基づき，垂直分割・水平分割のいずれかを選択する。
【００５３】
前記［領域分割方法１］との違いは，分割領域への係数割当てを分割領域内の画素数に応じて設定している点にある。このため，近似誤差最小化という観点から見た場合，［領域分割方法１］で求まる解を最適解とすれば，本方法で求まる方法は準最適解であるが，解を求める演算コストを低減することができる。
【００５４】
歪み量の尺度として次の近似誤差を用いる。
【００５５】
【数６】
【００５６】
この式中，Ｌ字型の記号と左右反転Ｌ字型の記号で挟まれる値（ｋ・ｈ／Ｈ）は，その値を超えない最大の整数を表す（以下，同様）。なお，以下の説明では，int(ｘ) とも表記する。すなわち，int(ｘ) は，実数ｘを超えない最大の整数を意味する。
【００５７】
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，上側領域０≦ｓ≦Ｗ，０≦ｔ≦ｈ−１と，下側領域０≦ｓ≦Ｗ，ｈ≦ｔ≦Ｈに分割し，上側領域および下側領域を各々，int(ｋ・ｈ／Ｈ) 個の係数およびｋ−int(ｋ・ｈ／Ｈ) 個の係数で表現した場合の近似誤差和を表している。
【００５８】
【数７】
【００５９】
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，左側領域０≦ｓ≦ｗ−１，０≦ｔ≦Ｈと，右側領域ｗ≦ｓ≦Ｗ，０≦ｔ≦Ｈに分割し，左側領域および右側領域を各々，int(ｋ・ｗ／Ｗ) 個の係数およびｋ−int(ｋ・ｗ／Ｗ) 個の係数で表現した場合の近似誤差和を表している。
【００６０】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，垂直方向に２分割する場合，次式に基づき分割位置を決定する。次式では，領域の画素数に応じて係数を配分するアプローチをとっている。
【００６１】
【数８】
【００６２】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，水平方向に２分割する場合，次式に基づき分割位置を決定する。次式では，領域の画素数に応じて係数を配分するアプローチをとっている。
【００６３】
【数９】
【００６４】
ここで，Ｍh ，Ｍw は最小変更幅として予め与えられる自然数である。このとき，
【００６５】
【数１０】
【００６６】
となる場合には，ｔ＝ｈ0 の位置で垂直方向に分割を行うこととし，それ以外の場合には，ｓ＝ｗ0 の位置で水平方向に分割を行うこととする。なお，ｈ0 ＝０あるいはｗ0 ＝０となる場合，分割を行わないほうが最適であるので分割は行われない。
【００６７】
上式は，領域の画素数に応じて係数を配分する枠組みにおいて，最適な分割位置を求めている。
【００６８】
分割により得られた矩形領域の中で近似誤差が最大の領域（分割対象領域）に対して，分割対象領域に含まれる係数の個数を上式におけるｋとみなして，上記と同様の分割処理を施す。選択した領域に対して分割が行われなかった場合には，先に選択された領域の次に近似誤差が大きな領域に対して，上記と同様の分割処理を施す。この繰り返しは，全ての分割領域に対して分割が行われなくなるまで続ける。または，分割領域内の画素数の下限値を設定しておき，分割の結果，この下限値を下回るような領域は生成されないように制限を設けることも可能である。
【００６９】
［領域分割方法３］
画面内の係数総数が一定（全分割領域の係数総数が一定）という条件下で分割後の歪み量の総和および分割境界の不連続性の評価尺度（後述）の加重和（分割コストと呼ぶ）を最小化する分割を考える。さらに，垂直に２分割する場合と水平に２分割する場合の結果を比較し，上記分割コスト最小化の規範に基づき，垂直分割・水平分割のいずれかを選択する。
【００７０】
歪み量の尺度として次の近似誤差を用いる。
【００７１】
【数１１】
【００７２】
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，上側領域０≦ｓ≦Ｗ，０≦ｔ≦ｈ−１と，下側領域０≦ｓ≦Ｗ，ｈ≦ｔ≦Ｈに分割し，上側領域および下側領域を各々，ｋh 個の係数およびｋ−ｋh 個の係数で表現した場合の近似誤差和を表している。
【００７３】
【数１２】
【００７４】
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，左側領域０≦ｓ≦ｗ−１，０≦ｔ≦Ｈと，右側領域ｗ≦ｓ≦Ｗ，０≦ｔ≦Ｈに分割し，左側領域および右側領域を各々，ｋw 個の係数およびｋ−ｋw 個の係数で表現した場合の近似誤差和を表している。
【００７５】
領域分割の尺度として前述の有意係数の個数および分割境界の不連続性の評価尺度（不連続尺度）を用いる。不連続尺度は，以下の境界領域に対して定義する。上側と下側の２つの領域に分割する垂直分割の場合，上側領域（ｋh 個の係数Ｃu で表現）内の下部０≦ｓ≦Ｗ，ｈ−Ｌ≦ｔ≦ｈ−１と下側領域（ｋ−ｋh 個の係数Ｃd で表現）内の上部０≦ｓ≦Ｗ，ｈ≦ｔ≦ｈ＋Ｌからなる矩形領域０≦ｓ≦Ｗ，ｈ−Ｌ≦ｔ≦ｈ＋Ｌを対象とし，同矩形領域に対する不連続尺度を次のように表す。
【００７６】
【数１３】
【００７７】
ここで，第２，３引数は，分割前後の領域に対する水平方向の存在領域０≦ｓ≦Ｗの下限・上限を示している。第４，５引数は，境界領域に対する垂直方向の存在領域の下限ｈ−Ｌおよび同領域の垂直方向の幅２Ｌ＋１を示している。第６，７引数ｋh ，ｋ−ｋh は，上側領域および下側領域における係数の個数である。第８，９引数Ｃu ，Ｃd は，上側領域および下側領域における係数である。
【００７８】
左側と右側の２つの領域に分割する水平分割の場合，左側領域（ｋw 個の係数Ｃl で表現）内の右端部ｗ−Ｌ≦ｓ≦ｗ−１，０≦ｔ≦Ｈと右側領域（ｋ−ｋw 個の係数Ｃr で表現）内の左端部ｗ≦ｓ≦ｗ＋Ｌ，０≦ｔ≦Ｈからなる矩形領領域ｗ−Ｌ≦ｓ≦ｗ＋Ｌ，０≦ｔ≦Ｈを対象とし，同矩形領域に対する不連続尺度を次のように表す。
【００７９】
【数１４】
【００８０】
ここで，第２，３引数は，分割前後の領域に対する垂直方向の存在領域０≦ｔ≦Ｈの下限・上限を示している。第４，５引数は，境界領域に対する水平方向の存在領域の下限ｗ−Ｌおよび同領域の水平方向の幅２Ｌ＋１を示している。第６，７引数ｋw ，ｋ−ｋw は，左側領域および右側領域における係数の個数である。第８，９引数Ｃl ，Ｃr は，左側領域および右側領域における係数である。
【００８１】
不連続尺度としては，例えば，近似誤差の乖離度を用いる。これは，垂直分割の場合，上側領域（ｋh 個の係数Ｃu で表現）内の下部０≦ｓ≦Ｗ，ｈ−Ｌ≦ｔ≦ｈ−１における近似誤差と，下側領域（ｋ−ｋh 個の係数Ｃd で表現）内の上部０≦ｓ≦Ｗ，ｈ−Ｌ≦ｔ≦Ｈ＋Ｌにおける近似誤差の差分値であり，水平分割の場合，左側領域（ｋw 個の係数Ｃl で表現）内の右端部ｗ−Ｌ≦ｓ≦ｗ−１，０≦ｔ≦Ｈにおける近似誤差と，右側領域（ｋ−ｋw 個の係数Ｃr で表現）内の左端部ｗ≦ｓ≦ｗ＋Ｌ，０≦ｔ≦Ｈにおける近似誤差との差分値である。あるいは，上記の近似誤差の差分値に対して，一定の重みを乗じた値を用いることも可能である。
【００８２】
また，分割境界領域におけるＳＳＩＭ（参考文献１参照）の符号を反転した値を用いることも可能である。
［参考文献１］：Z. Wang and E. P. Simoncelli, “Translation insensitive image similarity in complex wavelet domain”, IEEE International Conference on Acoustics, Speech & Signal Processing, vol. II, pp. 573-576, Philadelphia, PA, March 2005。
【００８３】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，垂直方向に２分割する場合，次式に基づき分割位置，および分割後の各領域へ割り当てられる係数の個数を決定する。垂直方向に２分割する場合の分割位置ｈ0 および上側の分割領域で用いる変換係数の個数ｋ0,h は，次式で与えられる（下側の分割領域で用いる変換係数の個数はｋ−ｋ0,h となる）。
【００８４】
【数１５】
【００８５】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，水平方向に２分割する場合，次式に基づき分割位置，および分割後の各領域へ割り当てられる係数の個数を決定する。水平方向に２分割する場合の分割位置ｗ0 ，および左側の分割領域で用いる変換係数の個数ｋ0,w は，次式で与えられる（なお，右側の分割領域で用いる変換係数の個数はｋ−ｋ0,w となる）。
【００８６】
【数１６】
【００８７】
このとき，
Ξhor ［ｘ，０，ｈ0 ，Ｗ，Ｈ，ｋ0,h ，ｋ−ｋ0,h ，Ｃu ，Ｃd ］＋
λΘhor ［ｘ，０，Ｗ，ｈ0 −Ｌ，２Ｌ＋１，ｋ0,h ，ｋ−ｋ0,h ，Ｃu ，Ｃd ］
≦ Ξver ［ｘ，ｗ0 ，０，Ｗ，Ｈ，ｋ0,w ，ｋ−ｋ0,w ，Ｃl ，Ｃr ］＋
λΘver ［ｘ，０，Ｈ，ｗ0 −Ｌ，２Ｌ＋１，ｋ0,w ，ｋ−ｋ0,w ，Ｃl ，Ｃr ］
となる場合には，ｔ＝ｈ0 の位置で垂直方向に分割を行うこととし，それ以外の場合には，ｓ＝ｗ0 の位置で水平方向に分割を行うこととする。なお，ｈ0 ＝０あるいはｗ0 ＝０となる場合，分割を行わないほうが最適であるので分割は行われない。
【００８８】
上式は，分割位置および各分割領域へ割り当てられる変換係数の個数を求めている。
【００８９】
分割により得られた矩形領域の中で近似誤差が最大の領域（分割対象領域）に対して，分割対象領域に含まれる係数の個数を上式におけるｋとみなして，上記と同様の分割処理を施す。選択した領域に対して分割が行われなかった場合には，先に選択された領域の次に近似誤差が大きな領域に対して，上記と同様の分割処理を施す。この繰り返しは，全ての分割領域に対して分割が行われなくなるまで続ける。または，分割領域内の画素数の下限値を設定しておき，分割の結果，この下限値を下回るような領域は生成されないように制限を設けることも可能である。
【００９０】
［領域分割方法４］
２つの分割領域において画素当りの係数の個数が一定という条件下で，分割後の歪み量の総和および分割境界の不連続性の評価尺度（後述）の加重和（分割コストと呼ぶ）を最小化する分割を考える。さらに，垂直に２分割する場合と水平に２分割する場合の結果を比較し，上記加重和最小化の規範に基づき，垂直分割・水平分割のいずれかを選択する。前記［領域分割方法３］との違いは，分割領域への係数割当てを分割領域内の画素数に応じて設定している点にある。このため，分割コスト最小化という観点から見た場合，［領域分割方法３］で求まる解を最適解とすれば，本方法で求まる方法は準最適解であるが，解を求める演算コストを低減することができる。
【００９１】
歪み量の尺度として次の近似誤差を用いる。
【００９２】
【数１７】
【００９３】
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，上側領域０≦ｓ≦Ｗ，０≦ｔ≦ｈ−１と，下側領域０≦ｓ≦Ｗ，ｈ≦ｔ≦Ｈに分割し，上側領域および下側領域を各々，int(ｋ・ｈ／Ｈ) 個の係数およびｋ−int(ｋ・ｈ／Ｈ) 個の係数で表現した場合の近似誤差和を表している。
【００９４】
【数１８】
【００９５】
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，左側領域０≦ｓ≦ｗ−１，０≦ｔ≦Ｈと，右側領域ｗ≦ｓ≦Ｗ，０≦ｔ≦Ｈに分割し，左側領域および右側領域を各々，int(ｋ・ｗ／Ｗ) 個の係数およびｋ−int(ｋ・ｗ／Ｗ) 個の係数で表現した場合の近似誤差和を表している。
【００９６】
分割境界の不連続尺度として，例えば，分割境界領域におけるＳＳＩＭを用いる。上側領域内の下部０≦ｓ≦Ｗ，ｈ−Ｌ≦ｔ≦ｈ−１と下側領域内の上部０≦ｓ≦Ｗ，ｈ≦ｔ≦ｈ＋Ｌからなる矩形領域０≦ｓ≦Ｗ，ｈ−Ｌ≦ｔ≦ｈ＋Ｌに対する不連続尺度を次のように表す。
【００９７】
【数１９】
【００９８】
左側領域内の右端部ｗ−Ｌ≦ｓ≦ｗ−１，０≦ｔ≦Ｈと右側領域内の左端部ｗ≦ｓ≦ｗ＋Ｌ，０≦ｔ≦Ｈからなる矩形領域ｗ−Ｌ≦ｓ≦ｗ＋Ｌ，０≦ｔ≦Ｈに対する不連続尺度を次のように表す。
【００９９】
【数２０】
【０１００】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，垂直方向に２分割する場合，次式に基づき分割位置を決定する。次式では，領域の画素数に応じて係数を配分するアプローチをとっている。
【０１０１】
【数２１】
【０１０２】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，水平方向に２分割する場合，次式に基づき分割位置を決定する。次式では，領域の画素数に応じて係数を配分するアプローチをとっている。
【０１０３】
【数２２】
【０１０４】
なお，Ｍh ，Ｍw は，最小変更幅として予め与えられる自然数である。このとき，
【０１０５】
【数２３】
【０１０６】
となる場合には，ｔ＝ｈ0 の位置で垂直方向に分割を行うこととし，それ以外の場合には，ｓ＝ｗ0 の位置で水平方向に分割を行うこととする。なお，ｈ0 ＝０あるいはｗ0 ＝０となる場合，分割を行わないほうが最適であるので分割は行われない。
【０１０７】
上式は，領域の画素数に応じて係数を配分する枠組みにおいて，最適な分割位置を求めている。
【０１０８】
分割により得られた矩形領域の中で分割コストが最大の領域（分割対象領域）に対して，分割対象領域に含まれる係数の個数を上式におけるｋとみなして，上記と同様の分割処理を施す。選択した領域に対して分割が行われなかった場合には，先に選択された領域の次に分割コストが大きな領域に対して，上記と同様の分割処理を施す。この繰り返しは，全ての分割領域に対して分割が行われなくなるまで続ける。または，分割領域内の画素数の下限値を設定しておき，分割の結果，この下限値を下回るような領域は生成されないように制限を設けることも可能である。
【０１０９】
［画像符号化装置の構成例］
図１は，本発明の実施形態に係る画像符号化装置の構成例を示す。画像符号化装置１０は映像信号を入力すると，予測部１４により予測された予測信号との差分から予測残差信号を求め，その予測残差信号を変換部１１により冗長系の変換基底を用いて変換する。係数選択処理部２０は，変換部１１の出力である変換係数の絞り込みを行うために，画面内を性質の類似した領域に分割し，分割領域ごとにコストが小さくなる変換係数を符号化対象として選択する。エントロピ符号化部１５は，選択された変換係数を可変長符号化し，符号化ストリームとして出力する。
【０１１０】
一方，係数選択処理部２０の出力は，逆変換部１２で逆変換され，その変換結果に予測信号が加えられて復号信号が生成される。復号信号は，歪除去フィルタ１３によりノイズ除去処理がなされ，参照復号信号として予測部１４に入力される。予測部１４では，次の映像信号の符号化のための予測信号の生成を行う。
【０１１１】
係数選択処理部２０における変換係数の選択は，次のように行われる。まず，最適分割処理部２２は，画像の領域を分割する複数の分割候補となる位置のそれぞれについて分割位置を設定し，領域分割を行い，係数選択部２２１により，全分割領域の係数の総数が一定という条件下で，全分割領域の歪み量の総和が最小となる最適な領域分割，または歪み量の総和と分割領域の境界部の不連続性を最小化する領域分割を求め，その各分割領域に対する変換係数の選択を行う。コスト算出部２２２により，領域分割に応じた符号化のコスト，すなわち，全分割領域の歪み量の総和（変換係数の切り捨てにより生じる誤差の和），または，分割領域の境界部における不連続性をコストとして考慮する場合には，その不連続性のコストを算出する。その結果をもとに，最適分割処理部２２は，コストが最も小さくなる領域分割を最適分割として選択する。
【０１１２】
領域分割形状設定部２１は，最適分割処理部２２によって決定された領域分割を示す情報と，その領域分割に対して係数選択部２２１によって選択された変換係数とを符号化対象情報として，エントロピ符号化部１５に出力する。
【０１１３】
［係数選択処理フロー］
図２は，係数選択処理部２０が実行する係数選択処理フローを示す図である。ここでは，主に［領域分割方法４］により領域分割を行う場合の実施例を説明するが，この方法は，［領域分割方法１］〜［領域分割方法３］の方法を包含しており，以下の説明から［領域分割方法１］〜［領域分割方法３］の領域分割による係数選択処理についても同様に実施することができることは明らかである。
【０１１４】
この例では，係数選択処理部２０は，分割対象領域の係数の総数Ｋと，処理対象画像の領域（最初は入力画像信号の全領域）とを引数とするＳｅｇｍｅｎｔ関数によって呼び出され，以下の処理を行う。
［ステップＳ１］：領域を領域１と領域２とに分割するとした場合の領域１の係数の個数ｋ１をループインデックスとして，初期値をｋ１＝０，増分を１とし，ｋ１＜Ｋの間，ステップＳ１〜Ｓ３の処理を繰り返す。なお，領域２の係数の個数ｋ２は，ｋ２＝Ｋ−ｋ１となる。
［ステップＳ２］：領域１の係数の個数ｋ１と，領域２の係数の個数ｋ２（＝Ｋ−ｋ１）と，入力領域とを引数として，Ｏｐｔ＿ｓｕｂ＿ｄｉｖ関数（最適分割処理関数）を呼び出す。この関数によって，最適分割処理部２２により，図３，図４に示す最適分割処理が実行される。
［ステップＳ３］：ループインデックスｋ１に１を加算し，ステップＳ１以降の処理を繰り返す。ｋ１がＫ以上になったならばループを終了する。
［ステップＳ４］：ステップＳ２の処理結果から領域１，領域２の最適な係数個数を算出する。
［ステップＳ５］：分割無しラベルを持たない領域の有無を判定し，分割無しラベルを持たない領域がある場合には，ステップＳ６へ進む。すべての領域が分割無しラベルを持つ領域になった場合には，ステップＳ８へ進む。
［ステップＳ６］：コスト関数値が最大の領域を同定する。この領域の係数の個数をＫ′とする。
［ステップＳ７］：係数の個数Ｋ′とコスト関数値が最大となる領域とを引数とするＳｅｇｍｅｎｔ関数を呼び出し，係数選択処理部２０による処理を，分割無しラベルを持つ領域が無くなるまで，再帰的に繰り返す。
［ステップＳ８］：コスト関数値が最大の領域を同定し，Ｓｅｇｍｅｎｔ関数の呼び出し元へ戻る。
【０１１５】
［最適分割処理フロー］
図３および図４に，最適分割処理部２２が実行する最適分割処理フローを示す。最適分割処理部２２は，図２に示すステップＳ２におけるＯｐｔ＿ｓｕｂ＿ｄｉｖ関数（最適分割処理関数）によって呼び出される。入力は，領域１の係数の個数ｋ１と，領域２の係数の個数ｋ２と，最適分割対象の領域である。
［ステップＳ１０］：縦分割位置（領域を垂直方向に２分割する位置）をループインデックスとして，初期値を０，増分をＭとし，縦分割位置＜画面縦幅の間，ステップＳ１０〜Ｓ１２の処理を繰り返す。
［ステップＳ１１］：係数の個数ｋ１，ｋ２および縦分割位置を引数として，コスト関数算出関数を呼び出す。この関数によって，コスト算出部２２２により，図５に示すコスト関数算出処理が実行される。
［ステップＳ１２］：ループインデックスの縦分割位置にＭを加算し，ステップＳ１０以降の処理を繰り返す。縦分割位置が画面縦幅以上になったならばループを終了する。
［ステップＳ１３］：コスト関数算出の処理結果から最適縦分割位置を算出し，図４のステップＳ２０へ進む。
［ステップＳ１４］：横分割位置（領域を水平方向に２分割する位置）をループインデックスとして，初期値を０，増分をＭとし，横分割位置＜画面横幅の間，ステップＳ１４〜Ｓ１６の処理を繰り返す。
［ステップＳ１５］：係数の個数ｋ１，ｋ２および横分割位置を引数として，コスト関数算出関数を呼び出す。この関数によって，コスト算出部２２２により，図５に示すコスト関数算出処理が実行される。
［ステップＳ１６］：ループインデックスの横分割位置にＭを加算し，ステップＳ１４以降の処理を繰り返す。横分割位置が画面横幅以上になったならばループを終了する。
［ステップＳ１７］：コスト関数算出の処理結果から最適横分割位置を算出し，図４のステップＳ２０へ進む。なお，ステップＳ１０〜Ｓ１３とステップＳ１４〜Ｓ１７の処理は，パラレルに実行してもシリアルに実行してもどちらでもよい。
［ステップＳ２０］：最適縦分割位置を用いたコストと最適横分割位置を用いたコストとの大小を比較し，最適縦分割位置を用いたコストのほうが小さい場合には，ステップＳ２１へ進み，そうでない場合には，ステップＳ２５へ進む。
［ステップＳ２１］：一方の分割領域の画素数が０か，または一方の分割領域の変換係数の個数が０の場合，ステップＳ２２へ進み，そうでない場合には，ステップＳ２４へ進む。
［ステップＳ２２］：入力された領域に対して，領域の分割は行わないことを示す分割無しラベルを付与する。
［ステップＳ２３］：Ｏｐｔ＿ｓｕｂ＿ｄｉｖ関数の呼び出し元へ分割無しラベルを返し，処理を終了する。
［ステップＳ２４］：最適縦分割位置の情報，各分割領域の変換係数，各分割領域の近似誤差，コスト関数値を，Ｏｐｔ＿ｓｕｂ＿ｄｉｖ関数の呼び出し元へ返し，処理を終了する。
［ステップＳ２５］：一方の分割領域の画素数が０か，または一方の分割領域の変換係数の個数が０の場合，ステップＳ２６へ進み，そうでない場合には，ステップＳ２８へ進む。
［ステップＳ２６］：入力された領域に対して，領域の分割は行わないことを示す分割無しラベルを付与する。
［ステップＳ２７］：Ｏｐｔ＿ｓｕｂ＿ｄｉｖ関数の呼び出し元へ分割無しラベルを返し，処理を終了する。
［ステップＳ２８］：最適横分割位置の情報，各分割領域の変換係数，各分割領域の近似誤差，コスト関数値を，Ｏｐｔ＿ｓｕｂ＿ｄｉｖ関数の呼び出し元へ返し，処理を終了する。
【０１１６】
［コスト関数算出処理フロー］
図５に，コスト算出部２２２が実行するコスト関数算出処理フローを示す。コスト算出部２２２は，図３に示すステップＳ１１およびＳ１５におけるコスト関数算出関数によって呼び出される。入力は，領域１の係数の個数ｋ１，領域２の係数の個数ｋ２，縦分割位置または横分割位置である。
［ステップＳ３０］：領域１に対して，ｋ１個の係数を選択する係数選択処理を行う。
［ステップＳ３１］：領域１に対して，上記の係数選択処理により選択されたｋ１個の係数で近似した場合の近似誤差を算出する。
［ステップＳ３２］：領域１に対して，上記の係数選択処理により選択されたｋ１個の係数で近似した場合の復号信号を得る。その後，ステップＳ３６へ進む。
［ステップＳ３３］：領域２に対して，ｋ２個の係数を選択する係数選択処理を行う。
［ステップＳ３４］：領域２に対して，上記の係数選択処理により選択されたｋ２個の係数で近似した場合の近似誤差を算出する。
［ステップＳ３５］：領域２に対して，上記の係数選択処理により選択されたｋ２個の係数で近似した場合の復号信号を得る。なお，ステップＳ３０〜Ｓ３２とステップＳ３３〜Ｓ３５とは，パラレルに実行してもシリアルに実行してもどちらでもよい。
［ステップＳ３６］：領域１，２の復号信号の境界領域に対して，不連続尺度を算出する。
［ステップＳ３７］：領域１，２の近似誤差和にλ×不連続尺度を加算して，コスト関数値を算出する。算出したコスト関数値を，関数の呼び出し元へ返し，処理を終了する。
【０１１７】
以上の画像符号化の処理は，コンピュータとソフトウェアプログラムとによっても実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録することも，ネットワークを通して提供することも可能である。
【０１１８】
図６は，本発明をソフトウェアプログラムを用いて実現する場合のシステムの構成例を示している。メモリ５２には，本発明の画像符号化処理を行うための画像符号化プログラム５３が格納される。ＣＰＵ５０は，メモリ５２に格納された画像符号化プログラム５３の命令を逐次フェッチして実行する。映像記憶装置５１は，符号化対象の映像信号を記憶する装置である。映像信号は，図示省略したカメラ等から入力するようにしてもよい。画像符号化プログラム５３によって生成された符号化ストリームは，符号化ストリーム記憶装置５４に格納される。または，ネットワークアダプタ等のインタフェースを介して，符号化ストリームを外部装置に出力してもよい。システムバス５５は，ＣＰＵ５０，映像記憶装置５１，メモリ５２，符号化ストリーム記憶装置５４を接続するバスである。
【符号の説明】
【０１１９】
１０ 画像符号化装置
１１ 変換部
１２ 逆変換部
１３ 歪除去フィルタ
１４ 予測部
１５ エントロピ符号化部
２０ 係数選択処理部
２１ 領域分割形状設定部
２２ 最適分割処理部
２２１ 係数選択部
２２２ コスト算出部
【技術分野】
【０００１】
本発明は，高能率画像信号符号化方法に関し，特に交互射影法におけるエネルギーコンパクションを向上させて符号化効率を向上させるための画像符号化方法に関する。
【背景技術】
【０００２】
画像符号化における重要な要素技術の一つに，離散コサイン変換（ＤＣＴ：Discrete Cosine Transform ）に代表される変換符号化がある。画像符号化における変換符号化の役割は，空間的な画素間相関の除去を行うことにある。符号化器の全体の位置づけとしては，変換符号化により少数の変換係数に情報を集中させ，変換係数に対する量子化により情報の集中度の低い変換係数を切り捨てることで，符号化対象信号に対する情報量の削減に寄与する。
【０００３】
図７に，映像信号を符号化する一般的な符号化装置１００の例を示す。符号化装置１００は映像信号を入力すると，予測部１０６により予測された予測信号との差分から予測残差信号を求め，変換部１０１により予測残差信号を直交変換する。その出力である変換係数を量子化部１０２にて量子化し，その量子化値をエントロピ符号化部１０７にて可変長符号化し，符号化ストリームとして出力する。一方，量子化部１０２の出力は，逆量子化部１０３で逆量子化され，さらに逆変換部１０４で逆直交変換される。その変換結果に予測信号を加えることにより復号信号が生成される。復号信号は，歪除去フィルタ１０５によりノイズ除去処理がなされ，参照復号信号として予測部１０６に入力される。予測部１０６では，動き探索などにより次の映像信号の符号化のための予測信号を生成する。
【０００４】
これまで，画像符号化への応用では，離散コサイン変換（ＤＣＴ）を始めとして，重複直交変換離散ウェーブレット変換（ＤＷＴ：Discrete Wavelet Transform）といった多くの変換符号化方式が検討されてきた。例えば，変換符号化として，ＪＰＥＧでは，離散コサイン変換（ＤＣＴ），ＪＰＥＧ ２０００では，離散ウェーブレット変換（ＤＷＴ）が採用されている。また，直交変換は完備な基底（complete basis）を用いるため，変換前後のデータ数が不変である。このため，直交変換は非冗長変換（non-redundant transform ）である。動画像符号化装置においては，図７における変換部１０１が上記の技術に該当する。
【０００５】
一方で，基底数が原信号のサンプル数よりも多い過完備な基底（overcomplete basis）を用いた冗長変換（redudant transform）と呼ばれる変換がある。このため，冗長変換は直交変換になり得ないが，変換後のデータに冗長性を持たせることで非冗長変換では実現できない特性をもつことができる。例えば，ダウンサンプリング処理を行わないＤＷＴである離散定常ウェーブレット変換（ＳＷＴ：Stationary Wavelet Transform）は変換後の冗長性により，ＤＷＴで失われるシフト不変性を成立させることができる。
【０００６】
また，画像処理分野では，“方向分離特性をもつ変換”が注目されている。このような変換は，一般的に冗長変換であり，代表例としてＣｕｒｖｅｌｅｔ変換がある。並列木複素ウェーブレット変換（ＤＴＣＷＴ：Dual Tree Complex Wavelet Transform ）も同様の特性をもつ変換である。方向分離特性をもつ変換は，画像信号中に含まれるエッジ等の曲線を２次元で定義される方向基底を用いて表現する変換である。方向基底を用いて２次元構造を高い精度で近似するため，ＤＷＴのような方向分離特性の乏しい変換と比較し，雑音除去や特徴抽出に対して，有効である。
【０００７】
しかし，方向分離特性をもつ変換は，変換後のデータ数が増加するという問題がある。ｘを変換符号化への入力信号，Ψを変換行列とすると，変換により得られる変換係数ｙは，次式のように表わされる。
【０００８】
ｙ＝Ψｘ (1)
一方，変換係数から信号領域での値を復号する処理は，過完備な基底系からなる変換の逆変換を表す行列をΦとすると，次式のように表わされる。
【０００９】
ｘ＝Φｙ (2)
ＤＴＣＷＴの場合，ｘがｎ次元ベクトルであるとすると，変換により得られる変換係数ｙは２ｎ次元ベクトルとなる。このため，同変換を画像符号化へ応用する場合，データ数の削減の観点から，変換係数を適切に選択する必要がある。この変換係数の選択は，以下の制約条件付き最小化問題として定式化できる。
【００１０】
ｍｉｎy ‖ｙ‖0 ｓｕｂｊｅｃｔ ｔｏ Φｙ＝ｘ (3)
ここで，‖・‖0 は，Ｌ0 ノルムであり，非ゼロ係数の個数を表している。上記の制約条件付きの最小化問題は，ラグランジュの未定乗数法により以下の最小化問題に帰着される。
【００１１】
ｍｉｎy ‖ｙ‖0 ＋λ‖Φｙ−ｘ‖2 2 (4)
ここでλは，外部から与えられる重みパラメータである。第一項は，選択された変換係数の個数であり，変換係数の情報量を近似した値である。第二項は変換係数の選択に伴う再構成誤差を表しており，符号化歪みを表している。‖・‖2 2 は，Ｌ2 ノルムの二乗値であり，二乗和を表す。しかし，上記の最小化問題はＮＰ困難であるため，従来，以下のようなＬ1 ノルムに最小化問題として近似する方法がとられてきた。
【００１２】
ｍｉｎy ‖ｙ‖1 ＋λ‖Φｙ−ｘ‖2 2 (5)
ここで，‖・‖は，Ｌ1 ノルムであり，ベクトルの要素の絶対値和を表している。
【００１３】
式(5) の最小化問題の準最適解を与える手法として，交互射影法と呼ばれる手法が提案されている（非特許文献１参照）。
【００１４】
式(3) は，以下の条件付最小化問題
【００１５】
【数１】
【００１６】
と等価であることに着目すると，上式はｘとのユークリッド距離を最小化するＫ個の非ゼロ係数を持つｙを探していると解釈することができる。上式の最小化を実現する解を求めるため，式(2) の解としての集合（アフィン集合）Ｓ（Φ，ｘ）とＣ（Ｋ）の間の交互直交射影を繰り返す。Ｃ（Ｋ）からＳ（Φ，ｘ）への直交射影は，
【００１７】
【数２】
【００１８】
で与えられる。ここで，ｙLSは二乗誤差最小化の規範の基づき，
ｙLS＝ΦT ［ΦΦT ］-1ｘ
により求められた係数ベクトルである。また，Ｓ（Φ，ｘ）からＣ（Ｋ）への直交射影は，ｈｔ（ｙ，Ｋ）により与えられる。ここで，ｈｔ（ｙ，Ｋ）は，Ｃ（Ｋ）へのユークリッド距離を最小にする射影であり，最も大きい値からＫ個の係数を選択する操作に相当する。
【００１９】
係数の初期ベクトルをｙ(0) とおき，次の漸化式に従い，繰り返し処理を行う。
【００２０】
【数３】
【００２１】
なお，この繰り返し処理は，以下の終了条件を満たすまで繰り返す。
【００２２】
‖ｙ(n+1) −ｙ(n) ‖2 ＜ε
このような過完備系を用いた変換は，画像信号にｓｐａｒｓｅｎｅｓｓを仮定し，少数の変換係数で画像を表現するｓｐａｒｓｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎの一種である。
【先行技術文献】
【非特許文献】
【００２３】
【非特許文献１】L. Mancera and J. Portilla, “ L0-norm-based sparse representation through alternate projections”，IEEE ICIP, Oct., 2006.
【発明の概要】
【発明が解決しようとする課題】
【００２４】
画像信号は空間的な局所性を有しており，その性質は一様ではない。つまり，画像信号を一定の精度で表現するために必要な変換係数の個数，あるいは，一定の個数の変換係数で表現可能な画像信号の表現精度は，画像内の領域の性質に応じて変動する。しかし，交互射影法は，画像全体に対して適用されている。このため，画像内の局所性を考慮できておらず，符号化効率の向上に改善の余地を残す。
【００２５】
本発明はかかる事情に鑑みてなされたものであって，過完備な基底を用いた冗長変換において，変換係数間の冗長性を除去する交互射影法において，符号化効率の向上を実現する画像分割手法に基づく画像符号化方法を確立することを目的とする。
【課題を解決するための手段】
【００２６】
本発明は，上記課題を解決するため，入力された映像信号に対して，冗長系の変換基底を用いた変換を行い，得られた変換係数に対して，符号化に用いる係数の絞り込みを行う画像符号化において，画像の局所的な性質に応じて，画面内の係数総数が一定（全分割領域の係数総数が一定）という条件下で全領域の歪み量の総和を最小化するための領域分割，および，各分割領域に対する変換係数の選択を行うことを特徴とする。
【００２７】
本発明は，画面内を性質の類似した領域に分割し，分割領域ごとにコストが小さくなる変換係数の選択を行うことにより，符号化効率を向上させることができる。
【００２８】
また，本発明は，入力された映像信号に対して，冗長系の変換基底を用いた変換を行い，得られた変換係数に対して，符号化に用いる係数の絞り込みを行う画像符号化において，画像の局所的な性質に応じて，画面内の係数総数が一定（全分割領域の係数総数が一定）という条件下で全領域の歪み量の総和および分割領域の境界部の不連続性を最小化するための領域分割，および，各分割領域に対する変換係数の選択を行うことを特徴とする。
【００２９】
また，本発明は，上記発明において，分割領域の係数の個数を，同分割領域の画素数に応じて設定することを特徴とする。
【００３０】
また，本発明は，上記発明において，選択された領域分割における各分割領域に対して，所定の分割の終了条件が満たされるまで，領域分割および変換係数を選択する処理を再帰的に繰り返すことを特徴とする。分割の終了条件は，例えば一方の分割領域の画素数が所定の閾値以下となること，または一方の分割領域の変換係数の個数が所定の閾値以下となることである。また，分割を行わないほうが最適な場合も分割の終了条件となる。
【発明の効果】
【００３１】
本発明により，画像の局所性を考慮して係数選択を行うことで，交互射影法におけるエネルギーコンパクションを向上させ，特定成分への情報の集約を図ることで，符号化効率の向上を実現することができる。
【図面の簡単な説明】
【００３２】
【図１】本発明の実施形態に係る画像符号化装置の構成例を示す図である。
【図２】係数選択処理部が実行する係数選択処理フローを示す図である。
【図３】最適分割処理部が実行する最適分割処理フローを示す図である。
【図４】最適分割処理部が実行する最適分割処理フローを示す図である。
【図５】コスト算出部が実行するコスト関数算出処理フローを示す図である。
【図６】ソフトウェアプログラムより実現するときのシステム構成図である。
【図７】一般的な符号化装置の構成図である。
【発明を実施するための形態】
【００３３】
以下，本発明の実施の形態について，図面を用いて説明する。
【００３４】
本発明の基本方針は，画面内を性質の類似した領域に分割し，分割領域ごとにｓｐａｒｓｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎを適用することである。以下，４種類の処理を示す。
【００３５】
［領域分割方法１］は，画面内の係数総数が一定（全分割領域の係数総数が一定）という条件下で全領域の歪み量の総和を最小化するための分割，およびパラメータ選択方法を示す。
【００３６】
［領域分割方法２］は，各分割領域において画素当りの係数の個数が一定という条件下で，各領域の歪み量を最小化するための分割，およびパラメータ選択方法を示す。
【００３７】
［領域分割方法３］は，［領域分割方法１］におけるコスト関数に対して領域境界の不連続性の影響を加味した修正を行ったものである。
【００３８】
同様に，［領域分割方法４］は，［領域分割方法２］におけるコスト関数に対して領域境界の不連続性の影響を加味した修正を行ったものである。
【００３９】
画像信号の存在領域を０≦ｓ≦Ｗ，０≦ｔ≦Ｈとし，同領域内の画素値を一次元ベクトルとして並べ替えたものをｘとする。さらに，同領域内から，左上角の座標値を（ｓ0 ，ｔ0 ），水平方向・垂直方向の辺長をｗ，ｈとする矩形領域内の画素値を抽出し，一次元ベクトルとして並べ替えたベクトルをｘ（ｓ0 ，ｔ0 ，ｗ，ｈ）とする。
【００４０】
ｘ（ｓ0 ，ｔ0 ，ｗ，ｈ）に対して，交互射影法を用いてｋ個の変換係数｛ｃ0 ，…，ｃk-1 ｝を選択し，選択された基底信号を用いてｘ（ｓ0 ，ｔ0 ，ｗ，ｈ）を表現した場合の近似誤差をＥ［ｘ，ｓ0 ，ｔ0 ，ｗ，ｈ，ｋ，Ｃ］とおく。ここで，Ｃは，ｋ個の変換係数Ｃ＝｛ｃ0 ，…，ｃk-1 ｝を表す。例えば，ＤＴＣＷＴの場合，総数２ｎ個の係数の中からｋ個の係数を選択したことになり，この選択に交互射影法を用いることができる。
【００４１】
［領域分割方法１］
画面内の係数総数が一定（全分割領域の係数総数が一定）という条件下で全領域の歪み量の総和を最小化するための分割を考える。さらに，垂直に２分割する場合と水平に２分割する場合の結果を比較し，上記歪み量最小化の規範に基づき，垂直分割・水平分割のいずれかを選択する。
【００４２】
歪み量の尺度として次の近似誤差を用いる。
【００４３】
Ξhor ［ｘ，０，ｈ，Ｗ，Ｈ，ｋh ，ｋ−ｋh ，Ｃu ，Ｃd ］＝Ｅ［ｘ，０，０，Ｗ，ｈ，ｋh ，Ｃd ］＋Ｅ［ｘ，０，ｈ，Ｗ，Ｈ−ｈ，ｋ−ｋh ，Ｃu ］
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，上側領域０≦ｓ≦Ｗ，０≦ｔ≦ｈ−１と，下側領域０≦ｓ≦Ｗ，ｈ≦ｔ≦Ｈに分割し，上側領域および下側領域を各々，ｋh 個の係数およびｋ−ｋh 個の係数で表現した場合の近似誤差和を表している。
【００４４】
Ξver ［ｘ，ｗ，０，Ｗ，Ｈ，ｋw ，ｋ−ｋw ，Ｃl ，Ｃr ］＝Ｅ［ｘ，０，０，ｗ，Ｈ，ｋw ，Ｃl ］＋Ｅ［ｘ，ｗ，０，Ｗ−ｗ，Ｈ，ｋ−ｋw ，Ｃr ］
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，左側領域０≦ｓ≦ｗ−１，０≦ｔ≦Ｈと，右側領域ｗ≦ｓ≦Ｗ，０≦ｔ≦Ｈに分割し，左側領域および右側領域を各々，ｋw 個の係数およびｋ−ｋw 個の係数で表現した場合の近似誤差和を表している。
【００４５】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，垂直方向に２分割する場合，次式に基づき分割位置，および分割後の各領域へ割り当てられる係数の個数を決定する。垂直方向に２分割する場合の分割位置ｈ0 ，および上側の分割領域で用いる変換係数の個数ｋ0,h は，次式で与えられる（下側の分割領域で用いる変換係数の個数はｋ−ｋ0,h となる）。
【００４６】
【数４】
【００４７】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，水平方向に２分割する場合，次式に基づき分割位置，および分割後の各領域へ割り当てられる係数の個数を決定する。水平方向に２分割する場合の分割位置ｗ0 ，および左側の分割領域で用いる変換係数の個数ｋ0,w は次式で与えられる（なお，右側の分割領域で用いる変換係数の個数は，ｋ−ｋ0,w となる）。
【００４８】
【数５】
【００４９】
このとき，
Ξhor ［ｘ，０，ｈ0 ，Ｗ，Ｈ，ｋ0,h ，ｋ−ｋ0,h ，Ｃu ，Ｃd ］
≦Ξver ［ｘ，ｗ0 ，０，Ｗ，Ｈ，ｋ0,w ，ｋ−ｋ0,w ，Ｃl ，Ｃr ］
となる場合には，ｔ＝ｈ0 の位置で垂直方向に分割を行うこととし，それ以外の場合には，ｓ＝ｗ0 の位置で水平方向に分割を行うこととする。なお，ｈ0 ＝０あるいはｗ0 ＝０となる場合，分割を行わないほうが最適であるので分割は行われない。
【００５０】
上式は，分割位置および各分割領域へ割り当てられる変換係数の個数を求めている。
【００５１】
分割により得られた矩形領域の中で近似誤差が最大の領域（分割対象領域）に対して，分割対象領域に含まれる係数の個数を上式におけるｋとみなして，上記と同様の分割処理を施す。選択した領域に対して分割が行われなかった場合には，先に選択された領域の次に近似誤差が大きな領域に対して，上記と同様の分割処理を施す。この繰り返しは，全ての分割領域に対して分割が行われなくなるまで続ける。または，分割領域内の画素数の下限値を設定しておき，分割の結果，この下限値を下回るような領域は生成されないように制限を設けることも可能である。
【００５２】
［領域分割方法２］
２つの分割領域において画素当りの係数の個数が一定という条件下で，各領域の歪み量を最小化するための分割を考える。さらに，垂直に２分割する場合と水平に２分割する場合の結果を比較し，上記加重和最小化の規範に基づき，垂直分割・水平分割のいずれかを選択する。
【００５３】
前記［領域分割方法１］との違いは，分割領域への係数割当てを分割領域内の画素数に応じて設定している点にある。このため，近似誤差最小化という観点から見た場合，［領域分割方法１］で求まる解を最適解とすれば，本方法で求まる方法は準最適解であるが，解を求める演算コストを低減することができる。
【００５４】
歪み量の尺度として次の近似誤差を用いる。
【００５５】
【数６】
【００５６】
この式中，Ｌ字型の記号と左右反転Ｌ字型の記号で挟まれる値（ｋ・ｈ／Ｈ）は，その値を超えない最大の整数を表す（以下，同様）。なお，以下の説明では，int(ｘ) とも表記する。すなわち，int(ｘ) は，実数ｘを超えない最大の整数を意味する。
【００５７】
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，上側領域０≦ｓ≦Ｗ，０≦ｔ≦ｈ−１と，下側領域０≦ｓ≦Ｗ，ｈ≦ｔ≦Ｈに分割し，上側領域および下側領域を各々，int(ｋ・ｈ／Ｈ) 個の係数およびｋ−int(ｋ・ｈ／Ｈ) 個の係数で表現した場合の近似誤差和を表している。
【００５８】
【数７】
【００５９】
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，左側領域０≦ｓ≦ｗ−１，０≦ｔ≦Ｈと，右側領域ｗ≦ｓ≦Ｗ，０≦ｔ≦Ｈに分割し，左側領域および右側領域を各々，int(ｋ・ｗ／Ｗ) 個の係数およびｋ−int(ｋ・ｗ／Ｗ) 個の係数で表現した場合の近似誤差和を表している。
【００６０】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，垂直方向に２分割する場合，次式に基づき分割位置を決定する。次式では，領域の画素数に応じて係数を配分するアプローチをとっている。
【００６１】
【数８】
【００６２】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，水平方向に２分割する場合，次式に基づき分割位置を決定する。次式では，領域の画素数に応じて係数を配分するアプローチをとっている。
【００６３】
【数９】
【００６４】
ここで，Ｍh ，Ｍw は最小変更幅として予め与えられる自然数である。このとき，
【００６５】
【数１０】
【００６６】
となる場合には，ｔ＝ｈ0 の位置で垂直方向に分割を行うこととし，それ以外の場合には，ｓ＝ｗ0 の位置で水平方向に分割を行うこととする。なお，ｈ0 ＝０あるいはｗ0 ＝０となる場合，分割を行わないほうが最適であるので分割は行われない。
【００６７】
上式は，領域の画素数に応じて係数を配分する枠組みにおいて，最適な分割位置を求めている。
【００６８】
分割により得られた矩形領域の中で近似誤差が最大の領域（分割対象領域）に対して，分割対象領域に含まれる係数の個数を上式におけるｋとみなして，上記と同様の分割処理を施す。選択した領域に対して分割が行われなかった場合には，先に選択された領域の次に近似誤差が大きな領域に対して，上記と同様の分割処理を施す。この繰り返しは，全ての分割領域に対して分割が行われなくなるまで続ける。または，分割領域内の画素数の下限値を設定しておき，分割の結果，この下限値を下回るような領域は生成されないように制限を設けることも可能である。
【００６９】
［領域分割方法３］
画面内の係数総数が一定（全分割領域の係数総数が一定）という条件下で分割後の歪み量の総和および分割境界の不連続性の評価尺度（後述）の加重和（分割コストと呼ぶ）を最小化する分割を考える。さらに，垂直に２分割する場合と水平に２分割する場合の結果を比較し，上記分割コスト最小化の規範に基づき，垂直分割・水平分割のいずれかを選択する。
【００７０】
歪み量の尺度として次の近似誤差を用いる。
【００７１】
【数１１】
【００７２】
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，上側領域０≦ｓ≦Ｗ，０≦ｔ≦ｈ−１と，下側領域０≦ｓ≦Ｗ，ｈ≦ｔ≦Ｈに分割し，上側領域および下側領域を各々，ｋh 個の係数およびｋ−ｋh 個の係数で表現した場合の近似誤差和を表している。
【００７３】
【数１２】
【００７４】
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，左側領域０≦ｓ≦ｗ−１，０≦ｔ≦Ｈと，右側領域ｗ≦ｓ≦Ｗ，０≦ｔ≦Ｈに分割し，左側領域および右側領域を各々，ｋw 個の係数およびｋ−ｋw 個の係数で表現した場合の近似誤差和を表している。
【００７５】
領域分割の尺度として前述の有意係数の個数および分割境界の不連続性の評価尺度（不連続尺度）を用いる。不連続尺度は，以下の境界領域に対して定義する。上側と下側の２つの領域に分割する垂直分割の場合，上側領域（ｋh 個の係数Ｃu で表現）内の下部０≦ｓ≦Ｗ，ｈ−Ｌ≦ｔ≦ｈ−１と下側領域（ｋ−ｋh 個の係数Ｃd で表現）内の上部０≦ｓ≦Ｗ，ｈ≦ｔ≦ｈ＋Ｌからなる矩形領域０≦ｓ≦Ｗ，ｈ−Ｌ≦ｔ≦ｈ＋Ｌを対象とし，同矩形領域に対する不連続尺度を次のように表す。
【００７６】
【数１３】
【００７７】
ここで，第２，３引数は，分割前後の領域に対する水平方向の存在領域０≦ｓ≦Ｗの下限・上限を示している。第４，５引数は，境界領域に対する垂直方向の存在領域の下限ｈ−Ｌおよび同領域の垂直方向の幅２Ｌ＋１を示している。第６，７引数ｋh ，ｋ−ｋh は，上側領域および下側領域における係数の個数である。第８，９引数Ｃu ，Ｃd は，上側領域および下側領域における係数である。
【００７８】
左側と右側の２つの領域に分割する水平分割の場合，左側領域（ｋw 個の係数Ｃl で表現）内の右端部ｗ−Ｌ≦ｓ≦ｗ−１，０≦ｔ≦Ｈと右側領域（ｋ−ｋw 個の係数Ｃr で表現）内の左端部ｗ≦ｓ≦ｗ＋Ｌ，０≦ｔ≦Ｈからなる矩形領領域ｗ−Ｌ≦ｓ≦ｗ＋Ｌ，０≦ｔ≦Ｈを対象とし，同矩形領域に対する不連続尺度を次のように表す。
【００７９】
【数１４】
【００８０】
ここで，第２，３引数は，分割前後の領域に対する垂直方向の存在領域０≦ｔ≦Ｈの下限・上限を示している。第４，５引数は，境界領域に対する水平方向の存在領域の下限ｗ−Ｌおよび同領域の水平方向の幅２Ｌ＋１を示している。第６，７引数ｋw ，ｋ−ｋw は，左側領域および右側領域における係数の個数である。第８，９引数Ｃl ，Ｃr は，左側領域および右側領域における係数である。
【００８１】
不連続尺度としては，例えば，近似誤差の乖離度を用いる。これは，垂直分割の場合，上側領域（ｋh 個の係数Ｃu で表現）内の下部０≦ｓ≦Ｗ，ｈ−Ｌ≦ｔ≦ｈ−１における近似誤差と，下側領域（ｋ−ｋh 個の係数Ｃd で表現）内の上部０≦ｓ≦Ｗ，ｈ−Ｌ≦ｔ≦Ｈ＋Ｌにおける近似誤差の差分値であり，水平分割の場合，左側領域（ｋw 個の係数Ｃl で表現）内の右端部ｗ−Ｌ≦ｓ≦ｗ−１，０≦ｔ≦Ｈにおける近似誤差と，右側領域（ｋ−ｋw 個の係数Ｃr で表現）内の左端部ｗ≦ｓ≦ｗ＋Ｌ，０≦ｔ≦Ｈにおける近似誤差との差分値である。あるいは，上記の近似誤差の差分値に対して，一定の重みを乗じた値を用いることも可能である。
【００８２】
また，分割境界領域におけるＳＳＩＭ（参考文献１参照）の符号を反転した値を用いることも可能である。
［参考文献１］：Z. Wang and E. P. Simoncelli, “Translation insensitive image similarity in complex wavelet domain”, IEEE International Conference on Acoustics, Speech & Signal Processing, vol. II, pp. 573-576, Philadelphia, PA, March 2005。
【００８３】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，垂直方向に２分割する場合，次式に基づき分割位置，および分割後の各領域へ割り当てられる係数の個数を決定する。垂直方向に２分割する場合の分割位置ｈ0 および上側の分割領域で用いる変換係数の個数ｋ0,h は，次式で与えられる（下側の分割領域で用いる変換係数の個数はｋ−ｋ0,h となる）。
【００８４】
【数１５】
【００８５】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，水平方向に２分割する場合，次式に基づき分割位置，および分割後の各領域へ割り当てられる係数の個数を決定する。水平方向に２分割する場合の分割位置ｗ0 ，および左側の分割領域で用いる変換係数の個数ｋ0,w は，次式で与えられる（なお，右側の分割領域で用いる変換係数の個数はｋ−ｋ0,w となる）。
【００８６】
【数１６】
【００８７】
このとき，
Ξhor ［ｘ，０，ｈ0 ，Ｗ，Ｈ，ｋ0,h ，ｋ−ｋ0,h ，Ｃu ，Ｃd ］＋
λΘhor ［ｘ，０，Ｗ，ｈ0 −Ｌ，２Ｌ＋１，ｋ0,h ，ｋ−ｋ0,h ，Ｃu ，Ｃd ］
≦ Ξver ［ｘ，ｗ0 ，０，Ｗ，Ｈ，ｋ0,w ，ｋ−ｋ0,w ，Ｃl ，Ｃr ］＋
λΘver ［ｘ，０，Ｈ，ｗ0 −Ｌ，２Ｌ＋１，ｋ0,w ，ｋ−ｋ0,w ，Ｃl ，Ｃr ］
となる場合には，ｔ＝ｈ0 の位置で垂直方向に分割を行うこととし，それ以外の場合には，ｓ＝ｗ0 の位置で水平方向に分割を行うこととする。なお，ｈ0 ＝０あるいはｗ0 ＝０となる場合，分割を行わないほうが最適であるので分割は行われない。
【００８８】
上式は，分割位置および各分割領域へ割り当てられる変換係数の個数を求めている。
【００８９】
分割により得られた矩形領域の中で近似誤差が最大の領域（分割対象領域）に対して，分割対象領域に含まれる係数の個数を上式におけるｋとみなして，上記と同様の分割処理を施す。選択した領域に対して分割が行われなかった場合には，先に選択された領域の次に近似誤差が大きな領域に対して，上記と同様の分割処理を施す。この繰り返しは，全ての分割領域に対して分割が行われなくなるまで続ける。または，分割領域内の画素数の下限値を設定しておき，分割の結果，この下限値を下回るような領域は生成されないように制限を設けることも可能である。
【００９０】
［領域分割方法４］
２つの分割領域において画素当りの係数の個数が一定という条件下で，分割後の歪み量の総和および分割境界の不連続性の評価尺度（後述）の加重和（分割コストと呼ぶ）を最小化する分割を考える。さらに，垂直に２分割する場合と水平に２分割する場合の結果を比較し，上記加重和最小化の規範に基づき，垂直分割・水平分割のいずれかを選択する。前記［領域分割方法３］との違いは，分割領域への係数割当てを分割領域内の画素数に応じて設定している点にある。このため，分割コスト最小化という観点から見た場合，［領域分割方法３］で求まる解を最適解とすれば，本方法で求まる方法は準最適解であるが，解を求める演算コストを低減することができる。
【００９１】
歪み量の尺度として次の近似誤差を用いる。
【００９２】
【数１７】
【００９３】
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，上側領域０≦ｓ≦Ｗ，０≦ｔ≦ｈ−１と，下側領域０≦ｓ≦Ｗ，ｈ≦ｔ≦Ｈに分割し，上側領域および下側領域を各々，int(ｋ・ｈ／Ｈ) 個の係数およびｋ−int(ｋ・ｈ／Ｈ) 個の係数で表現した場合の近似誤差和を表している。
【００９４】
【数１８】
【００９５】
上式は，領域０≦ｓ≦Ｗ，０≦ｔ≦Ｈを，左側領域０≦ｓ≦ｗ−１，０≦ｔ≦Ｈと，右側領域ｗ≦ｓ≦Ｗ，０≦ｔ≦Ｈに分割し，左側領域および右側領域を各々，int(ｋ・ｗ／Ｗ) 個の係数およびｋ−int(ｋ・ｗ／Ｗ) 個の係数で表現した場合の近似誤差和を表している。
【００９６】
分割境界の不連続尺度として，例えば，分割境界領域におけるＳＳＩＭを用いる。上側領域内の下部０≦ｓ≦Ｗ，ｈ−Ｌ≦ｔ≦ｈ−１と下側領域内の上部０≦ｓ≦Ｗ，ｈ≦ｔ≦ｈ＋Ｌからなる矩形領域０≦ｓ≦Ｗ，ｈ−Ｌ≦ｔ≦ｈ＋Ｌに対する不連続尺度を次のように表す。
【００９７】
【数１９】
【００９８】
左側領域内の右端部ｗ−Ｌ≦ｓ≦ｗ−１，０≦ｔ≦Ｈと右側領域内の左端部ｗ≦ｓ≦ｗ＋Ｌ，０≦ｔ≦Ｈからなる矩形領域ｗ−Ｌ≦ｓ≦ｗ＋Ｌ，０≦ｔ≦Ｈに対する不連続尺度を次のように表す。
【００９９】
【数２０】
【０１００】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，垂直方向に２分割する場合，次式に基づき分割位置を決定する。次式では，領域の画素数に応じて係数を配分するアプローチをとっている。
【０１０１】
【数２１】
【０１０２】
分割後の２つの領域での変換係数の総和をｋに保つ条件下で，水平方向に２分割する場合，次式に基づき分割位置を決定する。次式では，領域の画素数に応じて係数を配分するアプローチをとっている。
【０１０３】
【数２２】
【０１０４】
なお，Ｍh ，Ｍw は，最小変更幅として予め与えられる自然数である。このとき，
【０１０５】
【数２３】
【０１０６】
となる場合には，ｔ＝ｈ0 の位置で垂直方向に分割を行うこととし，それ以外の場合には，ｓ＝ｗ0 の位置で水平方向に分割を行うこととする。なお，ｈ0 ＝０あるいはｗ0 ＝０となる場合，分割を行わないほうが最適であるので分割は行われない。
【０１０７】
上式は，領域の画素数に応じて係数を配分する枠組みにおいて，最適な分割位置を求めている。
【０１０８】
分割により得られた矩形領域の中で分割コストが最大の領域（分割対象領域）に対して，分割対象領域に含まれる係数の個数を上式におけるｋとみなして，上記と同様の分割処理を施す。選択した領域に対して分割が行われなかった場合には，先に選択された領域の次に分割コストが大きな領域に対して，上記と同様の分割処理を施す。この繰り返しは，全ての分割領域に対して分割が行われなくなるまで続ける。または，分割領域内の画素数の下限値を設定しておき，分割の結果，この下限値を下回るような領域は生成されないように制限を設けることも可能である。
【０１０９】
［画像符号化装置の構成例］
図１は，本発明の実施形態に係る画像符号化装置の構成例を示す。画像符号化装置１０は映像信号を入力すると，予測部１４により予測された予測信号との差分から予測残差信号を求め，その予測残差信号を変換部１１により冗長系の変換基底を用いて変換する。係数選択処理部２０は，変換部１１の出力である変換係数の絞り込みを行うために，画面内を性質の類似した領域に分割し，分割領域ごとにコストが小さくなる変換係数を符号化対象として選択する。エントロピ符号化部１５は，選択された変換係数を可変長符号化し，符号化ストリームとして出力する。
【０１１０】
一方，係数選択処理部２０の出力は，逆変換部１２で逆変換され，その変換結果に予測信号が加えられて復号信号が生成される。復号信号は，歪除去フィルタ１３によりノイズ除去処理がなされ，参照復号信号として予測部１４に入力される。予測部１４では，次の映像信号の符号化のための予測信号の生成を行う。
【０１１１】
係数選択処理部２０における変換係数の選択は，次のように行われる。まず，最適分割処理部２２は，画像の領域を分割する複数の分割候補となる位置のそれぞれについて分割位置を設定し，領域分割を行い，係数選択部２２１により，全分割領域の係数の総数が一定という条件下で，全分割領域の歪み量の総和が最小となる最適な領域分割，または歪み量の総和と分割領域の境界部の不連続性を最小化する領域分割を求め，その各分割領域に対する変換係数の選択を行う。コスト算出部２２２により，領域分割に応じた符号化のコスト，すなわち，全分割領域の歪み量の総和（変換係数の切り捨てにより生じる誤差の和），または，分割領域の境界部における不連続性をコストとして考慮する場合には，その不連続性のコストを算出する。その結果をもとに，最適分割処理部２２は，コストが最も小さくなる領域分割を最適分割として選択する。
【０１１２】
領域分割形状設定部２１は，最適分割処理部２２によって決定された領域分割を示す情報と，その領域分割に対して係数選択部２２１によって選択された変換係数とを符号化対象情報として，エントロピ符号化部１５に出力する。
【０１１３】
［係数選択処理フロー］
図２は，係数選択処理部２０が実行する係数選択処理フローを示す図である。ここでは，主に［領域分割方法４］により領域分割を行う場合の実施例を説明するが，この方法は，［領域分割方法１］〜［領域分割方法３］の方法を包含しており，以下の説明から［領域分割方法１］〜［領域分割方法３］の領域分割による係数選択処理についても同様に実施することができることは明らかである。
【０１１４】
この例では，係数選択処理部２０は，分割対象領域の係数の総数Ｋと，処理対象画像の領域（最初は入力画像信号の全領域）とを引数とするＳｅｇｍｅｎｔ関数によって呼び出され，以下の処理を行う。
［ステップＳ１］：領域を領域１と領域２とに分割するとした場合の領域１の係数の個数ｋ１をループインデックスとして，初期値をｋ１＝０，増分を１とし，ｋ１＜Ｋの間，ステップＳ１〜Ｓ３の処理を繰り返す。なお，領域２の係数の個数ｋ２は，ｋ２＝Ｋ−ｋ１となる。
［ステップＳ２］：領域１の係数の個数ｋ１と，領域２の係数の個数ｋ２（＝Ｋ−ｋ１）と，入力領域とを引数として，Ｏｐｔ＿ｓｕｂ＿ｄｉｖ関数（最適分割処理関数）を呼び出す。この関数によって，最適分割処理部２２により，図３，図４に示す最適分割処理が実行される。
［ステップＳ３］：ループインデックスｋ１に１を加算し，ステップＳ１以降の処理を繰り返す。ｋ１がＫ以上になったならばループを終了する。
［ステップＳ４］：ステップＳ２の処理結果から領域１，領域２の最適な係数個数を算出する。
［ステップＳ５］：分割無しラベルを持たない領域の有無を判定し，分割無しラベルを持たない領域がある場合には，ステップＳ６へ進む。すべての領域が分割無しラベルを持つ領域になった場合には，ステップＳ８へ進む。
［ステップＳ６］：コスト関数値が最大の領域を同定する。この領域の係数の個数をＫ′とする。
［ステップＳ７］：係数の個数Ｋ′とコスト関数値が最大となる領域とを引数とするＳｅｇｍｅｎｔ関数を呼び出し，係数選択処理部２０による処理を，分割無しラベルを持つ領域が無くなるまで，再帰的に繰り返す。
［ステップＳ８］：コスト関数値が最大の領域を同定し，Ｓｅｇｍｅｎｔ関数の呼び出し元へ戻る。
【０１１５】
［最適分割処理フロー］
図３および図４に，最適分割処理部２２が実行する最適分割処理フローを示す。最適分割処理部２２は，図２に示すステップＳ２におけるＯｐｔ＿ｓｕｂ＿ｄｉｖ関数（最適分割処理関数）によって呼び出される。入力は，領域１の係数の個数ｋ１と，領域２の係数の個数ｋ２と，最適分割対象の領域である。
［ステップＳ１０］：縦分割位置（領域を垂直方向に２分割する位置）をループインデックスとして，初期値を０，増分をＭとし，縦分割位置＜画面縦幅の間，ステップＳ１０〜Ｓ１２の処理を繰り返す。
［ステップＳ１１］：係数の個数ｋ１，ｋ２および縦分割位置を引数として，コスト関数算出関数を呼び出す。この関数によって，コスト算出部２２２により，図５に示すコスト関数算出処理が実行される。
［ステップＳ１２］：ループインデックスの縦分割位置にＭを加算し，ステップＳ１０以降の処理を繰り返す。縦分割位置が画面縦幅以上になったならばループを終了する。
［ステップＳ１３］：コスト関数算出の処理結果から最適縦分割位置を算出し，図４のステップＳ２０へ進む。
［ステップＳ１４］：横分割位置（領域を水平方向に２分割する位置）をループインデックスとして，初期値を０，増分をＭとし，横分割位置＜画面横幅の間，ステップＳ１４〜Ｓ１６の処理を繰り返す。
［ステップＳ１５］：係数の個数ｋ１，ｋ２および横分割位置を引数として，コスト関数算出関数を呼び出す。この関数によって，コスト算出部２２２により，図５に示すコスト関数算出処理が実行される。
［ステップＳ１６］：ループインデックスの横分割位置にＭを加算し，ステップＳ１４以降の処理を繰り返す。横分割位置が画面横幅以上になったならばループを終了する。
［ステップＳ１７］：コスト関数算出の処理結果から最適横分割位置を算出し，図４のステップＳ２０へ進む。なお，ステップＳ１０〜Ｓ１３とステップＳ１４〜Ｓ１７の処理は，パラレルに実行してもシリアルに実行してもどちらでもよい。
［ステップＳ２０］：最適縦分割位置を用いたコストと最適横分割位置を用いたコストとの大小を比較し，最適縦分割位置を用いたコストのほうが小さい場合には，ステップＳ２１へ進み，そうでない場合には，ステップＳ２５へ進む。
［ステップＳ２１］：一方の分割領域の画素数が０か，または一方の分割領域の変換係数の個数が０の場合，ステップＳ２２へ進み，そうでない場合には，ステップＳ２４へ進む。
［ステップＳ２２］：入力された領域に対して，領域の分割は行わないことを示す分割無しラベルを付与する。
［ステップＳ２３］：Ｏｐｔ＿ｓｕｂ＿ｄｉｖ関数の呼び出し元へ分割無しラベルを返し，処理を終了する。
［ステップＳ２４］：最適縦分割位置の情報，各分割領域の変換係数，各分割領域の近似誤差，コスト関数値を，Ｏｐｔ＿ｓｕｂ＿ｄｉｖ関数の呼び出し元へ返し，処理を終了する。
［ステップＳ２５］：一方の分割領域の画素数が０か，または一方の分割領域の変換係数の個数が０の場合，ステップＳ２６へ進み，そうでない場合には，ステップＳ２８へ進む。
［ステップＳ２６］：入力された領域に対して，領域の分割は行わないことを示す分割無しラベルを付与する。
［ステップＳ２７］：Ｏｐｔ＿ｓｕｂ＿ｄｉｖ関数の呼び出し元へ分割無しラベルを返し，処理を終了する。
［ステップＳ２８］：最適横分割位置の情報，各分割領域の変換係数，各分割領域の近似誤差，コスト関数値を，Ｏｐｔ＿ｓｕｂ＿ｄｉｖ関数の呼び出し元へ返し，処理を終了する。
【０１１６】
［コスト関数算出処理フロー］
図５に，コスト算出部２２２が実行するコスト関数算出処理フローを示す。コスト算出部２２２は，図３に示すステップＳ１１およびＳ１５におけるコスト関数算出関数によって呼び出される。入力は，領域１の係数の個数ｋ１，領域２の係数の個数ｋ２，縦分割位置または横分割位置である。
［ステップＳ３０］：領域１に対して，ｋ１個の係数を選択する係数選択処理を行う。
［ステップＳ３１］：領域１に対して，上記の係数選択処理により選択されたｋ１個の係数で近似した場合の近似誤差を算出する。
［ステップＳ３２］：領域１に対して，上記の係数選択処理により選択されたｋ１個の係数で近似した場合の復号信号を得る。その後，ステップＳ３６へ進む。
［ステップＳ３３］：領域２に対して，ｋ２個の係数を選択する係数選択処理を行う。
［ステップＳ３４］：領域２に対して，上記の係数選択処理により選択されたｋ２個の係数で近似した場合の近似誤差を算出する。
［ステップＳ３５］：領域２に対して，上記の係数選択処理により選択されたｋ２個の係数で近似した場合の復号信号を得る。なお，ステップＳ３０〜Ｓ３２とステップＳ３３〜Ｓ３５とは，パラレルに実行してもシリアルに実行してもどちらでもよい。
［ステップＳ３６］：領域１，２の復号信号の境界領域に対して，不連続尺度を算出する。
［ステップＳ３７］：領域１，２の近似誤差和にλ×不連続尺度を加算して，コスト関数値を算出する。算出したコスト関数値を，関数の呼び出し元へ返し，処理を終了する。
【０１１７】
以上の画像符号化の処理は，コンピュータとソフトウェアプログラムとによっても実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録することも，ネットワークを通して提供することも可能である。
【０１１８】
図６は，本発明をソフトウェアプログラムを用いて実現する場合のシステムの構成例を示している。メモリ５２には，本発明の画像符号化処理を行うための画像符号化プログラム５３が格納される。ＣＰＵ５０は，メモリ５２に格納された画像符号化プログラム５３の命令を逐次フェッチして実行する。映像記憶装置５１は，符号化対象の映像信号を記憶する装置である。映像信号は，図示省略したカメラ等から入力するようにしてもよい。画像符号化プログラム５３によって生成された符号化ストリームは，符号化ストリーム記憶装置５４に格納される。または，ネットワークアダプタ等のインタフェースを介して，符号化ストリームを外部装置に出力してもよい。システムバス５５は，ＣＰＵ５０，映像記憶装置５１，メモリ５２，符号化ストリーム記憶装置５４を接続するバスである。
【符号の説明】
【０１１９】
１０ 画像符号化装置
１１ 変換部
１２ 逆変換部
１３ 歪除去フィルタ
１４ 予測部
１５ エントロピ符号化部
２０ 係数選択処理部
２１ 領域分割形状設定部
２２ 最適分割処理部
２２１ 係数選択部
２２２ コスト算出部
【特許請求の範囲】
【請求項１】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い，得られた変換係数を絞り込み，絞り込んだ結果の変換係数を符号化する画像符号化方法において，
画像の領域を分割する複数の分割候補となる位置のそれぞれについて，分割位置を設定する過程と，
前記設定された分割位置で画像の領域を分割し，全分割領域の係数の総数が一定という条件下で各分割領域の変換係数を選択する過程と，
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で，全領域の変換係数の選択による歪み量の総和が最小となる領域分割を選択するとともに，各分割領域における符号化に用いる変換係数を選択する過程とを有する
ことを特徴とする画像符号化方法。
【請求項２】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い，得られた変換係数を絞り込み，絞り込んだ結果の変換係数を符号化する画像符号化方法において，
画像の領域を分割する複数の分割候補となる位置のそれぞれについて，分割位置を設定する過程と，
前記設定された分割位置で画像の領域を分割し，全分割領域の係数の総数が一定という条件下で各分割領域の変換係数を選択する過程と，
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で，全領域の変換係数の選択による歪み量の総和および分割領域の境界部の不連続性を最小化する領域分割を選択するとともに，各分割領域における符号化に用いる変換係数を選択する過程とを有する
ことを特徴とする画像符号化方法。
【請求項３】
請求項１または請求項２記載の画像符号化方法において，
分割領域の係数の個数を，分割領域の画素数に応じて設定する
ことを特徴とする画像符号化方法。
【請求項４】
請求項１から請求項３までのいずれか１項に記載の画像符号化方法において，
前記選択された領域分割における各分割領域に対して，所定の分割の終了条件が満たされるまで，前記領域分割および変換係数を選択する処理を再帰的に繰り返す
ことを特徴とする画像符号化方法。
【請求項５】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い，得られた変換係数を絞り込み，絞り込んだ結果の変換係数を符号化する画像符号化装置において，
画像の領域を分割する複数の分割候補となる位置のそれぞれについて，分割位置を設定する手段と，
前記設定された分割位置で画像の領域を分割し，全分割領域の係数の総数が一定という条件下で各分割領域の変換係数を選択する手段と，
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で，全領域の変換係数の選択による歪み量の総和が最小となる領域分割を選択するとともに，各分割領域における符号化に用いる変換係数を選択する手段とを備える
ことを特徴とする画像符号化装置。
【請求項６】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い，得られた変換係数を絞り込み，絞り込んだ結果の変換係数を符号化する画像符号化装置において，
画像の領域を分割する複数の分割候補となる位置のそれぞれについて，分割位置を設定する手段と，
前記設定された分割位置で画像の領域を分割し，全分割領域の係数の総数が一定という条件下で各分割領域の変換係数を選択する手段と，
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で，全領域の変換係数の選択による歪み量の総和および分割領域の境界部の不連続性を最小化する領域分割を選択するとともに，各分割領域における符号化に用いる変換係数を選択する手段とを備える
ことを特徴とする画像符号化装置。
【請求項７】
請求項５または請求項６記載の画像符号化装置において，
分割領域の係数の個数を，分割領域の画素数に応じて設定する
ことを特徴とする画像符号化装置。
【請求項８】
請求項１から請求項４までのいずれか１項に記載の画像符号化方法を，コンピュータに実行させるための画像符号化プログラム。
【請求項１】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い，得られた変換係数を絞り込み，絞り込んだ結果の変換係数を符号化する画像符号化方法において，
画像の領域を分割する複数の分割候補となる位置のそれぞれについて，分割位置を設定する過程と，
前記設定された分割位置で画像の領域を分割し，全分割領域の係数の総数が一定という条件下で各分割領域の変換係数を選択する過程と，
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で，全領域の変換係数の選択による歪み量の総和が最小となる領域分割を選択するとともに，各分割領域における符号化に用いる変換係数を選択する過程とを有する
ことを特徴とする画像符号化方法。
【請求項２】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い，得られた変換係数を絞り込み，絞り込んだ結果の変換係数を符号化する画像符号化方法において，
画像の領域を分割する複数の分割候補となる位置のそれぞれについて，分割位置を設定する過程と，
前記設定された分割位置で画像の領域を分割し，全分割領域の係数の総数が一定という条件下で各分割領域の変換係数を選択する過程と，
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で，全領域の変換係数の選択による歪み量の総和および分割領域の境界部の不連続性を最小化する領域分割を選択するとともに，各分割領域における符号化に用いる変換係数を選択する過程とを有する
ことを特徴とする画像符号化方法。
【請求項３】
請求項１または請求項２記載の画像符号化方法において，
分割領域の係数の個数を，分割領域の画素数に応じて設定する
ことを特徴とする画像符号化方法。
【請求項４】
請求項１から請求項３までのいずれか１項に記載の画像符号化方法において，
前記選択された領域分割における各分割領域に対して，所定の分割の終了条件が満たされるまで，前記領域分割および変換係数を選択する処理を再帰的に繰り返す
ことを特徴とする画像符号化方法。
【請求項５】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い，得られた変換係数を絞り込み，絞り込んだ結果の変換係数を符号化する画像符号化装置において，
画像の領域を分割する複数の分割候補となる位置のそれぞれについて，分割位置を設定する手段と，
前記設定された分割位置で画像の領域を分割し，全分割領域の係数の総数が一定という条件下で各分割領域の変換係数を選択する手段と，
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で，全領域の変換係数の選択による歪み量の総和が最小となる領域分割を選択するとともに，各分割領域における符号化に用いる変換係数を選択する手段とを備える
ことを特徴とする画像符号化装置。
【請求項６】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い，得られた変換係数を絞り込み，絞り込んだ結果の変換係数を符号化する画像符号化装置において，
画像の領域を分割する複数の分割候補となる位置のそれぞれについて，分割位置を設定する手段と，
前記設定された分割位置で画像の領域を分割し，全分割領域の係数の総数が一定という条件下で各分割領域の変換係数を選択する手段と，
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で，全領域の変換係数の選択による歪み量の総和および分割領域の境界部の不連続性を最小化する領域分割を選択するとともに，各分割領域における符号化に用いる変換係数を選択する手段とを備える
ことを特徴とする画像符号化装置。
【請求項７】
請求項５または請求項６記載の画像符号化装置において，
分割領域の係数の個数を，分割領域の画素数に応じて設定する
ことを特徴とする画像符号化装置。
【請求項８】
請求項１から請求項４までのいずれか１項に記載の画像符号化方法を，コンピュータに実行させるための画像符号化プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１２−８９９６４（Ｐ２０１２−８９９６４Ａ）
【公開日】平成２４年５月１０日（２０１２．５．１０）
【国際特許分類】
【出願番号】特願２０１０−２３３２３０（Ｐ２０１０−２３３２３０）
【出願日】平成２２年１０月１８日（２０１０．１０．１８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
【公開日】平成２４年５月１０日（２０１２．５．１０）
【国際特許分類】
【出願日】平成２２年１０月１８日（２０１０．１０．１８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
[ Back to top ]