TOP > 国内特許検索 > 画像符号化方法,画像符号化装置および画像符号化プログラム > 明細書

明細書 :画像符号化方法,画像符号化装置および画像符号化プログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5626728号 (P5626728)
公開番号 特開2012-089964 (P2012-089964A)
登録日 平成26年10月10日(2014.10.10)
発行日 平成26年11月19日(2014.11.19)
公開日 平成24年5月10日(2012.5.10)
発明の名称または考案の名称 画像符号化方法,画像符号化装置および画像符号化プログラム
国際特許分類 H04N   1/41        (2006.01)
H04N  19/645       (2014.01)
H03M   7/30        (2006.01)
FI H04N 1/41 B
H04N 19/645
H03M 7/30 A
請求項の数または発明の数 8
全頁数 20
出願番号 特願2010-233230 (P2010-233230)
出願日 平成22年10月18日(2010.10.18)
審査請求日 平成25年7月22日(2013.7.22)
特許権者または実用新案権者 【識別番号】000004226
【氏名又は名称】日本電信電話株式会社
【識別番号】899000068
【氏名又は名称】学校法人早稲田大学
発明者または考案者 【氏名】坂東 幸浩
【氏名】高村 誠之
【氏名】如澤 裕尚
【氏名】石川 孝明
【氏名】渡辺 裕
個別代理人の代理人 【識別番号】100087848、【弁理士】、【氏名又は名称】小笠原 吉義
【識別番号】100103827、【弁理士】、【氏名又は名称】平岡 憲一
審査官 【審査官】堀井 啓明
参考文献・文献 特開2010-199959(JP,A)
特開平06-178118(JP,A)
調査した分野 H04N1/41-1/419
H04N19/00-19/98
H03M3/00-11/00
特許請求の範囲 【請求項1】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い,得られた変換係数を絞り込み,絞り込んだ結果の変換係数を符号化する画像符号化方法において,
画像の領域を分割する複数の分割候補となる位置のそれぞれについて,分割位置を設定する過程と,
前記設定された分割位置で画像の領域を分割し,全分割領域の係数の総数が一定という条件下で各分割領域の変換係数を選択する過程と,
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で,全領域の変換係数の選択による歪み量の総和が最小となる領域分割を選択するとともに,各分割領域における符号化に用いる変換係数を選択する過程とを有する
ことを特徴とする画像符号化方法。
【請求項2】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い,得られた変換係数を絞り込み,絞り込んだ結果の変換係数を符号化する画像符号化方法において,
画像の領域を分割する複数の分割候補となる位置のそれぞれについて,分割位置を設定する過程と,
前記設定された分割位置で画像の領域を分割し,全分割領域の係数の総数が一定という条件下で各分割領域の変換係数を選択する過程と,
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で,全領域の変換係数の選択による歪み量の総和と,分割領域の境界部に接する所定幅の二つの境界領域における変換係数の絞り込みに基づく近似誤差の乖離度との重み付き和を最小化する領域分割を選択するとともに,各分割領域における符号化に用いる変換係数を選択する過程とを有する
ことを特徴とする画像符号化方法。
【請求項3】
請求項1または請求項2記載の画像符号化方法において,
分割領域の係数の個数を,分割領域の画素数に応じて設定する
ことを特徴とする画像符号化方法。
【請求項4】
請求項1から請求項3までのいずれか1項に記載の画像符号化方法において,
前記選択された領域分割における各分割領域に対して,所定の分割の終了条件が満たされるまで,前記領域分割および変換係数を選択する処理を再帰的に繰り返す
ことを特徴とする画像符号化方法。
【請求項5】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い,得られた変換係数を絞り込み,絞り込んだ結果の変換係数を符号化する画像符号化装置において,
画像の領域を分割する複数の分割候補となる位置のそれぞれについて,分割位置を設定する手段と,
前記設定された分割位置で画像の領域を分割し,全分割領域の係数の総数が一定という条件下で各分割領域の変換係数を選択する手段と,
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で,全領域の変換係数の選択による歪み量の総和が最小となる領域分割を選択するとともに,各分割領域における符号化に用いる変換係数を選択する手段とを備える
ことを特徴とする画像符号化装置。
【請求項6】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い,得られた変換係数を絞り込み,絞り込んだ結果の変換係数を符号化する画像符号化装置において,
画像の領域を分割する複数の分割候補となる位置のそれぞれについて,分割位置を設定する手段と,
前記設定された分割位置で画像の領域を分割し,全分割領域の係数の総数が一定という条件下で各分割領域の変換係数を選択する手段と,
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で,全領域の変換係数の選択による歪み量の総和と,分割領域の境界部に接する所定幅の二つの境界領域における変換係数の絞り込みに基づく近似誤差の乖離度との重み付き和を最小化する領域分割を選択するとともに,各分割領域における符号化に用いる変換係数を選択する手段とを備える
ことを特徴とする画像符号化装置。
【請求項7】
請求項5または請求項6記載の画像符号化装置において,
分割領域の係数の個数を,分割領域の画素数に応じて設定する
ことを特徴とする画像符号化装置。
【請求項8】
請求項1から請求項4までのいずれか1項に記載の画像符号化方法を,コンピュータに実行させるための画像符号化プログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は,高能率画像信号符号化方法に関し,特に交互射影法におけるエネルギーコンパクションを向上させて符号化効率を向上させるための画像符号化方法に関する。
【背景技術】
【0002】
画像符号化における重要な要素技術の一つに,離散コサイン変換(DCT:Discrete Cosine Transform )に代表される変換符号化がある。画像符号化における変換符号化の役割は,空間的な画素間相関の除去を行うことにある。符号化器の全体の位置づけとしては,変換符号化により少数の変換係数に情報を集中させ,変換係数に対する量子化により情報の集中度の低い変換係数を切り捨てることで,符号化対象信号に対する情報量の削減に寄与する。
【0003】
図7に,映像信号を符号化する一般的な符号化装置100の例を示す。符号化装置100は映像信号を入力すると,予測部106により予測された予測信号との差分から予測残差信号を求め,変換部101により予測残差信号を直交変換する。その出力である変換係数を量子化部102にて量子化し,その量子化値をエントロピ符号化部107にて可変長符号化し,符号化ストリームとして出力する。一方,量子化部102の出力は,逆量子化部103で逆量子化され,さらに逆変換部104で逆直交変換される。その変換結果に予測信号を加えることにより復号信号が生成される。復号信号は,歪除去フィルタ105によりノイズ除去処理がなされ,参照復号信号として予測部106に入力される。予測部106では,動き探索などにより次の映像信号の符号化のための予測信号を生成する。
【0004】
これまで,画像符号化への応用では,離散コサイン変換(DCT)を始めとして,重複直交変換離散ウェーブレット変換(DWT:Discrete Wavelet Transform)といった多くの変換符号化方式が検討されてきた。例えば,変換符号化として,JPEGでは,離散コサイン変換(DCT),JPEG 2000では,離散ウェーブレット変換(DWT)が採用されている。また,直交変換は完備な基底(complete basis)を用いるため,変換前後のデータ数が不変である。このため,直交変換は非冗長変換(non-redundant transform )である。動画像符号化装置においては,図7における変換部101が上記の技術に該当する。
【0005】
一方で,基底数が原信号のサンプル数よりも多い過完備な基底(overcomplete basis)を用いた冗長変換(redudant transform)と呼ばれる変換がある。このため,冗長変換は直交変換になり得ないが,変換後のデータに冗長性を持たせることで非冗長変換では実現できない特性をもつことができる。例えば,ダウンサンプリング処理を行わないDWTである離散定常ウェーブレット変換(SWT:Stationary Wavelet Transform)は変換後の冗長性により,DWTで失われるシフト不変性を成立させることができる。
【0006】
また,画像処理分野では,“方向分離特性をもつ変換”が注目されている。このような変換は,一般的に冗長変換であり,代表例としてCurvelet変換がある。並列木複素ウェーブレット変換(DTCWT:Dual Tree Complex Wavelet Transform )も同様の特性をもつ変換である。方向分離特性をもつ変換は,画像信号中に含まれるエッジ等の曲線を2次元で定義される方向基底を用いて表現する変換である。方向基底を用いて2次元構造を高い精度で近似するため,DWTのような方向分離特性の乏しい変換と比較し,雑音除去や特徴抽出に対して,有効である。
【0007】
しかし,方向分離特性をもつ変換は,変換後のデータ数が増加するという問題がある。xを変換符号化への入力信号,Ψを変換行列とすると,変換により得られる変換係数yは,次式のように表わされる。
【0008】
y=Ψx (1)
一方,変換係数から信号領域での値を復号する処理は,過完備な基底系からなる変換の逆変換を表す行列をΦとすると,次式のように表わされる。
【0009】
x=Φy (2)
DTCWTの場合,xがn次元ベクトルであるとすると,変換により得られる変換係数yは2n次元ベクトルとなる。このため,同変換を画像符号化へ応用する場合,データ数の削減の観点から,変換係数を適切に選択する必要がある。この変換係数の選択は,以下の制約条件付き最小化問題として定式化できる。
【0010】
miny ∥y∥0 subject to Φy=x (3)
ここで,∥・∥0 は,L0 ノルムであり,非ゼロ係数の個数を表している。上記の制約条件付きの最小化問題は,ラグランジュの未定乗数法により以下の最小化問題に帰着される。
【0011】
min ∥y∥ +λ∥Φy-x∥ 2 (4)
ここでλは,外部から与えられる重みパラメータである。第一項は,選択された変換係数の個数であり,変換係数の情報量を近似した値である。第二項は変換係数の選択に伴う再構成誤差を表しており,符号化歪みを表している。∥・∥ 2 は,L2 ノルムの二乗値であり,二乗和を表す。しかし,上記の最小化問題はNP困難であるため,従来,以下のような1 ノルムに最小化問題として近似する方法がとられてきた。
【0012】
min ∥y∥ +λ∥Φy-x∥ 2 (5)
ここで,∥・∥は,1 ノルムであり,ベクトルの要素の絶対値和を表している。
【0013】
式(5) の最小化問題の準最適解を与える手法として,交互射影法と呼ばれる手法が提案されている(非特許文献1参照)。
【0014】
式(3) は,以下の条件付最小化問題
【0015】
【数1】
JP0005626728B2_000002t.gif

【0016】
と等価であることに着目すると,上式はxとのユークリッド距離を最小化するK個の非ゼロ係数を持つyを探していると解釈することができる。上式の最小化を実現する解を求めるため,式(2) の解としての集合(アフィン集合)S(Φ,x)とC(K)の間の交互直交射影を繰り返す。C(K)からS(Φ,x)への直交射影は,
【0017】
【数2】
JP0005626728B2_000003t.gif

【0018】
で与えられる。ここで,yLSは二乗誤差最小化の規範の基づき,
LS=ΦT [ΦΦT -1
により求められた係数ベクトルである。また,S(Φ,x)からC(K)への直交射影は,ht(y,K)により与えられる。ここで,ht(y,K)は,C(K)へのユークリッド距離を最小にする射影であり,最も大きい値からK個の係数を選択する操作に相当する。
【0019】
係数の初期ベクトルをy(0) とおき,次の漸化式に従い,繰り返し処理を行う。
【0020】
【数3】
JP0005626728B2_000004t.gif

【0021】
なお,この繰り返し処理は,以下の終了条件を満たすまで繰り返す。
【0022】
∥y(n+1) -y(n) 2 <ε
このような過完備系を用いた変換は,画像信号にsparsenessを仮定し,少数の変換係数で画像を表現するsparse representationの一種である。
【先行技術文献】
【0023】

【非特許文献1】L. Mancera and J. Portilla, “ L0-norm-based sparse representation through alternate projections”,IEEE ICIP, Oct., 2006.
【発明の概要】
【発明が解決しようとする課題】
【0024】
画像信号は空間的な局所性を有しており,その性質は一様ではない。つまり,画像信号を一定の精度で表現するために必要な変換係数の個数,あるいは,一定の個数の変換係数で表現可能な画像信号の表現精度は,画像内の領域の性質に応じて変動する。しかし,交互射影法は,画像全体に対して適用されている。このため,画像内の局所性を考慮できておらず,符号化効率の向上に改善の余地を残す。
【0025】
本発明はかかる事情に鑑みてなされたものであって,過完備な基底を用いた冗長変換において,変換係数間の冗長性を除去する交互射影法において,符号化効率の向上を実現する画像分割手法に基づく画像符号化方法を確立することを目的とする。
【課題を解決するための手段】
【0026】
本発明は,上記課題を解決するため,入力された映像信号に対して,冗長系の変換基底を用いた変換を行い,得られた変換係数に対して,符号化に用いる係数の絞り込みを行う画像符号化において,画像の局所的な性質に応じて,画面内の係数総数が一定(全分割領域の係数総数が一定)という条件下で全領域の歪み量の総和を最小化するための領域分割,および,各分割領域に対する変換係数の選択を行うことを特徴とする。
【0027】
本発明は,画面内を性質の類似した領域に分割し,分割領域ごとにコストが小さくなる変換係数の選択を行うことにより,符号化効率を向上させることができる。
【0028】
また,本発明は,入力された映像信号に対して,冗長系の変換基底を用いた変換を行い,得られた変換係数に対して,符号化に用いる係数の絞り込みを行う画像符号化において,画像の局所的な性質に応じて,画面内の係数総数が一定(全分割領域の係数総数が一定)という条件下で全領域の歪み量の総和と,分割領域の境界部に接する所定幅の二つの境界領域における変換係数の絞り込みに基づく近似誤差の乖離度との重み付き和を最小化するための領域分割,および,各分割領域に対する変換係数の選択を行うことを特徴とする。
【0029】
また,本発明は,上記発明において,分割領域の係数の個数を,同分割領域の画素数に応じて設定することを特徴とする。
【0030】
また,本発明は,上記発明において,選択された領域分割における各分割領域に対して,所定の分割の終了条件が満たされるまで,領域分割および変換係数を選択する処理を再帰的に繰り返すことを特徴とする。分割の終了条件は,例えば一方の分割領域の画素数が所定の閾値以下となること,または一方の分割領域の変換係数の個数が所定の閾値以下となることである。また,分割を行わないほうが最適な場合も分割の終了条件となる。
【発明の効果】
【0031】
本発明により,画像の局所性を考慮して係数選択を行うことで,交互射影法におけるエネルギーコンパクションを向上させ,特定成分への情報の集約を図ることで,符号化効率の向上を実現することができる。
【図面の簡単な説明】
【0032】
【図1】本発明の実施形態に係る画像符号化装置の構成例を示す図である。
【図2】係数選択処理部が実行する係数選択処理フローを示す図である。
【図3】最適分割処理部が実行する最適分割処理フローを示す図である。
【図4】最適分割処理部が実行する最適分割処理フローを示す図である。
【図5】コスト算出部が実行するコスト関数算出処理フローを示す図である。
【図6】ソフトウェアプログラムより実現するときのシステム構成図である。
【図7】一般的な符号化装置の構成図である。
【発明を実施するための形態】
【0033】
以下,本発明の実施の形態について,図面を用いて説明する。

【0034】
本発明の基本方針は,画面内を性質の類似した領域に分割し,分割領域ごとにsparse representationを適用することである。以下,4種類の処理を示す。

【0035】
[領域分割方法1]は,画面内の係数総数が一定(全分割領域の係数総数が一定)という条件下で全領域の歪み量の総和を最小化するための分割,およびパラメータ選択方法を示す。

【0036】
[領域分割方法2]は,各分割領域において画素当りの係数の個数が一定という条件下で,各領域の歪み量を最小化するための分割,およびパラメータ選択方法を示す。

【0037】
[領域分割方法3]は,[領域分割方法1]におけるコスト関数に対して領域境界の不連続性の影響を加味した修正を行ったものである。

【0038】
同様に,[領域分割方法4]は,[領域分割方法2]におけるコスト関数に対して領域境界の不連続性の影響を加味した修正を行ったものである。

【0039】
画像信号の存在領域を0≦s≦W,0≦t≦Hとし,同領域内の画素値を一次元ベクトルとして並べ替えたものをxとする。さらに,同領域内から,左上角の座標値を(s0 ,t0 ),水平方向・垂直方向の辺長をw,hとする矩形領域内の画素値を抽出し,一次元ベクトルとして並べ替えたベクトルをx(s0 ,t0 ,w,h)とする。

【0040】
x(s0 ,t0 ,w,h)に対して,交互射影法を用いてk個の変換係数{c0 ,…,ck-1 }を選択し,選択された基底信号を用いてx(s0 ,t0 ,w,h)を表現した場合の近似誤差をE[x,s0 ,t0 ,w,h,k,C]とおく。ここで,Cは,k個の変換係数C={c0 ,…,ck-1 }を表す。例えば,DTCWTの場合,総数2n個の係数の中からk個の係数を選択したことになり,この選択に交互射影法を用いることができる。

【0041】
[領域分割方法1]
画面内の係数総数が一定(全分割領域の係数総数が一定)という条件下で全領域の歪み量の総和を最小化するための分割を考える。さらに,垂直に2分割する場合と水平に2分割する場合の結果を比較し,上記歪み量最小化の規範に基づき,垂直分割・水平分割のいずれかを選択する。

【0042】
歪み量の尺度として次の近似誤差を用いる。

【0043】
Ξhor [x,0,h,W,H,kh ,k-kh ,Cu ,Cd ]=E[x,0,0,W,h,kh ,Cd ]+E[x,0,h,W,H-h,k-kh ,Cu
上式は,領域0≦s≦W,0≦t≦Hを,上側領域0≦s≦W,0≦t≦h-1と,下側領域0≦s≦W,h≦t≦Hに分割し,上側領域および下側領域を各々,kh 個の係数およびk-kh 個の係数で表現した場合の近似誤差和を表している。

【0044】
Ξver [x,w,0,W,H,kw ,k-kw ,Cl ,Cr ]=E[x,0,0,w,H,kw ,Cl ]+E[x,w,0,W-w,H,k-kw ,Cr
上式は,領域0≦s≦W,0≦t≦Hを,左側領域0≦s≦w-1,0≦t≦Hと,右側領域w≦s≦W,0≦t≦Hに分割し,左側領域および右側領域を各々,kw 個の係数およびk-kw 個の係数で表現した場合の近似誤差和を表している。

【0045】
分割後の2つの領域での変換係数の総和をkに保つ条件下で,垂直方向に2分割する場合,次式に基づき分割位置,および分割後の各領域へ割り当てられる係数の個数を決定する。垂直方向に2分割する場合の分割位置h0 ,および上側の分割領域で用いる変換係数の個数k0,h は,次式で与えられる(下側の分割領域で用いる変換係数の個数はk-k0,h となる)。

【0046】
【数4】
JP0005626728B2_000005t.gif

【0047】
分割後の2つの領域での変換係数の総和をkに保つ条件下で,水平方向に2分割する場合,次式に基づき分割位置,および分割後の各領域へ割り当てられる係数の個数を決定する。水平方向に2分割する場合の分割位置w0 ,および左側の分割領域で用いる変換係数の個数k0,w は次式で与えられる(なお,右側の分割領域で用いる変換係数の個数は,k-k0,w となる)。

【0048】
【数5】
JP0005626728B2_000006t.gif

【0049】
このとき,
Ξhor [x,0,h0 ,W,H,k0,h ,k-k0,h ,Cu ,Cd
≦Ξver [x,w0 ,0,W,H,k0,w ,k-k0,w ,Cl ,Cr
となる場合には,t=h0 の位置で垂直方向に分割を行うこととし,それ以外の場合には,s=w0 の位置で水平方向に分割を行うこととする。なお,h0 =0あるいはw0 =0となる場合,分割を行わないほうが最適であるので分割は行われない。

【0050】
上式は,分割位置および各分割領域へ割り当てられる変換係数の個数を求めている。

【0051】
分割により得られた矩形領域の中で近似誤差が最大の領域(分割対象領域)に対して,分割対象領域に含まれる係数の個数を上式におけるkとみなして,上記と同様の分割処理を施す。選択した領域に対して分割が行われなかった場合には,先に選択された領域の次に近似誤差が大きな領域に対して,上記と同様の分割処理を施す。この繰り返しは,全ての分割領域に対して分割が行われなくなるまで続ける。または,分割領域内の画素数の下限値を設定しておき,分割の結果,この下限値を下回るような領域は生成されないように制限を設けることも可能である。

【0052】
[領域分割方法2]
2つの分割領域において画素当りの係数の個数が一定という条件下で,各領域の歪み量を最小化するための分割を考える。さらに,垂直に2分割する場合と水平に2分割する場合の結果を比較し,上記加重和最小化の規範に基づき,垂直分割・水平分割のいずれかを選択する。

【0053】
前記[領域分割方法1]との違いは,分割領域への係数割当てを分割領域内の画素数に応じて設定している点にある。このため,近似誤差最小化という観点から見た場合,[領域分割方法1]で求まる解を最適解とすれば,本方法で求まる方法は準最適解であるが,解を求める演算コストを低減することができる。

【0054】
歪み量の尺度として次の近似誤差を用いる。

【0055】
【数6】
JP0005626728B2_000007t.gif

【0056】
この式中,L字型の記号と左右反転L字型の記号で挟まれる値(k・h/H)は,その値を超えない最大の整数を表す(以下,同様)。なお,以下の説明では,int(x) とも表記する。すなわち,int(x) は,実数xを超えない最大の整数を意味する。

【0057】
上式は,領域0≦s≦W,0≦t≦Hを,上側領域0≦s≦W,0≦t≦h-1と,下側領域0≦s≦W,h≦t≦Hに分割し,上側領域および下側領域を各々,int(k・h/H) 個の係数およびk-int(k・h/H) 個の係数で表現した場合の近似誤差和を表している。

【0058】
【数7】
JP0005626728B2_000008t.gif

【0059】
上式は,領域0≦s≦W,0≦t≦Hを,左側領域0≦s≦w-1,0≦t≦Hと,右側領域w≦s≦W,0≦t≦Hに分割し,左側領域および右側領域を各々,int(k・w/W) 個の係数およびk-int(k・w/W) 個の係数で表現した場合の近似誤差和を表している。

【0060】
分割後の2つの領域での変換係数の総和をkに保つ条件下で,垂直方向に2分割する場合,次式に基づき分割位置を決定する。次式では,領域の画素数に応じて係数を配分するアプローチをとっている。

【0061】
【数8】
JP0005626728B2_000009t.gif

【0062】
分割後の2つの領域での変換係数の総和をkに保つ条件下で,水平方向に2分割する場合,次式に基づき分割位置を決定する。次式では,領域の画素数に応じて係数を配分するアプローチをとっている。

【0063】
【数9】
JP0005626728B2_000010t.gif

【0064】
ここで,Mh ,Mw は最小変更幅として予め与えられる自然数である。このとき,

【0065】
【数10】
JP0005626728B2_000011t.gif

【0066】
となる場合には,t=h0 の位置で垂直方向に分割を行うこととし,それ以外の場合には,s=w0 の位置で水平方向に分割を行うこととする。なお,h0 =0あるいはw0 =0となる場合,分割を行わないほうが最適であるので分割は行われない。

【0067】
上式は,領域の画素数に応じて係数を配分する枠組みにおいて,最適な分割位置を求めている。

【0068】
分割により得られた矩形領域の中で近似誤差が最大の領域(分割対象領域)に対して,分割対象領域に含まれる係数の個数を上式におけるkとみなして,上記と同様の分割処理を施す。選択した領域に対して分割が行われなかった場合には,先に選択された領域の次に近似誤差が大きな領域に対して,上記と同様の分割処理を施す。この繰り返しは,全ての分割領域に対して分割が行われなくなるまで続ける。または,分割領域内の画素数の下限値を設定しておき,分割の結果,この下限値を下回るような領域は生成されないように制限を設けることも可能である。

【0069】
[領域分割方法3]
画面内の係数総数が一定(全分割領域の係数総数が一定)という条件下で分割後の歪み量の総和および分割境界の不連続性の評価尺度(後述)の加重和(分割コストと呼ぶ)を最小化する分割を考える。さらに,垂直に2分割する場合と水平に2分割する場合の結果を比較し,上記分割コスト最小化の規範に基づき,垂直分割・水平分割のいずれかを選択する。

【0070】
歪み量の尺度として次の近似誤差を用いる。

【0071】
【数11】
JP0005626728B2_000012t.gif

【0072】
上式は,領域0≦s≦W,0≦t≦Hを,上側領域0≦s≦W,0≦t≦h-1と,下側領域0≦s≦W,h≦t≦Hに分割し,上側領域および下側領域を各々,kh 個の係数およびk-kh 個の係数で表現した場合の近似誤差和を表している。

【0073】
【数12】
JP0005626728B2_000013t.gif

【0074】
上式は,領域0≦s≦W,0≦t≦Hを,左側領域0≦s≦w-1,0≦t≦Hと,右側領域w≦s≦W,0≦t≦Hに分割し,左側領域および右側領域を各々,kw 個の係数およびk-kw 個の係数で表現した場合の近似誤差和を表している。

【0075】
領域分割の尺度として前述の有意係数の個数および分割境界の不連続性の評価尺度(不連続尺度)を用いる。不連続尺度は,以下の境界領域に対して定義する。上側と下側の2つの領域に分割する垂直分割の場合,上側領域(kh 個の係数Cu で表現)内の下部0≦s≦W,h-L≦t≦h-1と下側領域(k-kh 個の係数Cd で表現)内の上部0≦s≦W,h≦t≦h+Lからなる矩形領域0≦s≦W,h-L≦t≦h+Lを対象とし,同矩形領域に対する不連続尺度を次のように表す。

【0076】
【数13】
JP0005626728B2_000014t.gif

【0077】
ここで,第2,3引数は,分割前後の領域に対する水平方向の存在領域0≦s≦Wの下限・上限を示している。第4,5引数は,境界領域に対する垂直方向の存在領域の下限h-Lおよび同領域の垂直方向の幅2L+1を示している。第6,7引数kh ,k-kh は,上側領域および下側領域における係数の個数である。第8,9引数Cu ,Cd は,上側領域および下側領域における係数である。

【0078】
左側と右側の2つの領域に分割する水平分割の場合,左側領域(kw 個の係数Cl で表現)内の右端部w-L≦s≦w-1,0≦t≦Hと右側領域(k-kw 個の係数Cr で表現)内の左端部w≦s≦w+L,0≦t≦Hからなる矩形領領域w-L≦s≦w+L,0≦t≦Hを対象とし,同矩形領域に対する不連続尺度を次のように表す。

【0079】
【数14】
JP0005626728B2_000015t.gif

【0080】
ここで,第2,3引数は,分割前後の領域に対する垂直方向の存在領域0≦t≦Hの下限・上限を示している。第4,5引数は,境界領域に対する水平方向の存在領域の下限w-Lおよび同領域の水平方向の幅2L+1を示している。第6,7引数kw ,k-kw は,左側領域および右側領域における係数の個数である。第8,9引数Cl ,Cr は,左側領域および右側領域における係数である。

【0081】
不連続尺度としては,例えば,近似誤差の乖離度を用いる。これは,垂直分割の場合,上側領域(k 個の係数C で表現)内の下部0≦s≦W,h-L≦t≦h-1における近似誤差と,下側領域(k-k 個の係数Cで表現)内の上部0≦s≦W,h≦t≦h+Lにおける近似誤差の差分値であり,水平分割の場合,左側領域(k個の係数Cで表現)内の右端部w-L≦s≦w-1,0≦t≦Hにおける近似誤差と,右側領域(k-k 個の係数C で表現)内の左端部w≦s≦w+L,0≦t≦Hにおける近似誤差との差分値である。あるいは,上記の近似誤差の差分値に対して,一定の重みを乗じた値を用いることも可能である。


【0082】
また,分割境界領域におけるSSIM(参考文献1参照)の符号を反転した値を用いることも可能である。
[参考文献1]: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。

【0083】
分割後の2つの領域での変換係数の総和をkに保つ条件下で,垂直方向に2分割する場合,次式に基づき分割位置,および分割後の各領域へ割り当てられる係数の個数を決定する。垂直方向に2分割する場合の分割位置h0 および上側の分割領域で用いる変換係数の個数k0,h は,次式で与えられる(下側の分割領域で用いる変換係数の個数はk-k0,h となる)。

【0084】
【数15】
JP0005626728B2_000016t.gif

【0085】
分割後の2つの領域での変換係数の総和をkに保つ条件下で,水平方向に2分割する場合,次式に基づき分割位置,および分割後の各領域へ割り当てられる係数の個数を決定する。水平方向に2分割する場合の分割位置w0 ,および左側の分割領域で用いる変換係数の個数k0,w は,次式で与えられる(なお,右側の分割領域で用いる変換係数の個数はk-k0,w となる)。

【0086】
【数16】
JP0005626728B2_000017t.gif

【0087】
このとき,
Ξhor [x,0,h0 ,W,H,k0,h ,k-k0,h ,Cu ,Cd ]+
λΘhor [x,0,W,h0 -L,2L+1,k0,h ,k-k0,h ,Cu ,Cd
≦ Ξver [x,w0 ,0,W,H,k0,w ,k-k0,w ,Cl ,Cr ]+
λΘver [x,0,H,w0 -L,2L+1,k0,w ,k-k0,w ,Cl ,Cr
となる場合には,t=h0 の位置で垂直方向に分割を行うこととし,それ以外の場合には,s=w0 の位置で水平方向に分割を行うこととする。なお,h0 =0あるいはw0 =0となる場合,分割を行わないほうが最適であるので分割は行われない。

【0088】
上式は,分割位置および各分割領域へ割り当てられる変換係数の個数を求めている。

【0089】
分割により得られた矩形領域の中で近似誤差が最大の領域(分割対象領域)に対して,分割対象領域に含まれる係数の個数を上式におけるkとみなして,上記と同様の分割処理を施す。選択した領域に対して分割が行われなかった場合には,先に選択された領域の次に近似誤差が大きな領域に対して,上記と同様の分割処理を施す。この繰り返しは,全ての分割領域に対して分割が行われなくなるまで続ける。または,分割領域内の画素数の下限値を設定しておき,分割の結果,この下限値を下回るような領域は生成されないように制限を設けることも可能である。

【0090】
[領域分割方法4]
2つの分割領域において画素当りの係数の個数が一定という条件下で,分割後の歪み量の総和および分割境界の不連続性の評価尺度(後述)の加重和(分割コストと呼ぶ)を最小化する分割を考える。さらに,垂直に2分割する場合と水平に2分割する場合の結果を比較し,上記加重和最小化の規範に基づき,垂直分割・水平分割のいずれかを選択する。前記[領域分割方法3]との違いは,分割領域への係数割当てを分割領域内の画素数に応じて設定している点にある。このため,分割コスト最小化という観点から見た場合,[領域分割方法3]で求まる解を最適解とすれば,本方法で求まる方法は準最適解であるが,解を求める演算コストを低減することができる。

【0091】
歪み量の尺度として次の近似誤差を用いる。

【0092】
【数17】
JP0005626728B2_000018t.gif

【0093】
上式は,領域0≦s≦W,0≦t≦Hを,上側領域0≦s≦W,0≦t≦h-1と,下側領域0≦s≦W,h≦t≦Hに分割し,上側領域および下側領域を各々,int(k・h/H) 個の係数およびk-int(k・h/H) 個の係数で表現した場合の近似誤差和を表している。

【0094】
【数18】
JP0005626728B2_000019t.gif

【0095】
上式は,領域0≦s≦W,0≦t≦Hを,左側領域0≦s≦w-1,0≦t≦Hと,右側領域w≦s≦W,0≦t≦Hに分割し,左側領域および右側領域を各々,int(k・w/W) 個の係数およびk-int(k・w/W) 個の係数で表現した場合の近似誤差和を表している。

【0096】
分割境界の不連続尺度として,例えば,分割境界領域におけるSSIMを用いる。上側領域内の下部0≦s≦W,h-L≦t≦h-1と下側領域内の上部0≦s≦W,h≦t≦h+Lからなる矩形領域0≦s≦W,h-L≦t≦h+Lに対する不連続尺度を次のように表す。

【0097】
【数19】
JP0005626728B2_000020t.gif

【0098】
左側領域内の右端部w-L≦s≦w-1,0≦t≦Hと右側領域内の左端部w≦s≦w+L,0≦t≦Hからなる矩形領域w-L≦s≦w+L,0≦t≦Hに対する不連続尺度を次のように表す。

【0099】
【数20】
JP0005626728B2_000021t.gif

【0100】
分割後の2つの領域での変換係数の総和をkに保つ条件下で,垂直方向に2分割する場合,次式に基づき分割位置を決定する。次式では,領域の画素数に応じて係数を配分するアプローチをとっている。

【0101】
【数21】
JP0005626728B2_000022t.gif

【0102】
分割後の2つの領域での変換係数の総和をkに保つ条件下で,水平方向に2分割する場合,次式に基づき分割位置を決定する。次式では,領域の画素数に応じて係数を配分するアプローチをとっている。

【0103】
【数22】
JP0005626728B2_000023t.gif

【0104】
なお,Mh ,Mw は,最小変更幅として予め与えられる自然数である。このとき,

【0105】
【数23】
JP0005626728B2_000024t.gif

【0106】
となる場合には,t=h0 の位置で垂直方向に分割を行うこととし,それ以外の場合には,s=w0 の位置で水平方向に分割を行うこととする。なお,h0 =0あるいはw0 =0となる場合,分割を行わないほうが最適であるので分割は行われない。

【0107】
上式は,領域の画素数に応じて係数を配分する枠組みにおいて,最適な分割位置を求めている。

【0108】
分割により得られた矩形領域の中で分割コストが最大の領域(分割対象領域)に対して,分割対象領域に含まれる係数の個数を上式におけるkとみなして,上記と同様の分割処理を施す。選択した領域に対して分割が行われなかった場合には,先に選択された領域の次に分割コストが大きな領域に対して,上記と同様の分割処理を施す。この繰り返しは,全ての分割領域に対して分割が行われなくなるまで続ける。または,分割領域内の画素数の下限値を設定しておき,分割の結果,この下限値を下回るような領域は生成されないように制限を設けることも可能である。

【0109】
[画像符号化装置の構成例]
図1は,本発明の実施形態に係る画像符号化装置の構成例を示す。画像符号化装置10は映像信号を入力すると,予測部14により予測された予測信号との差分から予測残差信号を求め,その予測残差信号を変換部11により冗長系の変換基底を用いて変換する。係数選択処理部20は,変換部11の出力である変換係数の絞り込みを行うために,画面内を性質の類似した領域に分割し,分割領域ごとにコストが小さくなる変換係数を符号化対象として選択する。エントロピ符号化部15は,選択された変換係数を可変長符号化し,符号化ストリームとして出力する。

【0110】
一方,係数選択処理部20の出力は,逆変換部12で逆変換され,その変換結果に予測信号が加えられて復号信号が生成される。復号信号は,歪除去フィルタ13によりノイズ除去処理がなされ,参照復号信号として予測部14に入力される。予測部14では,次の映像信号の符号化のための予測信号の生成を行う。

【0111】
係数選択処理部20における変換係数の選択は,次のように行われる。まず,最適分割処理部22は,画像の領域を分割する複数の分割候補となる位置のそれぞれについて分割位置を設定し,領域分割を行い,係数選択部221により,全分割領域の係数の総数が一定という条件下で,全分割領域の歪み量の総和が最小となる最適な領域分割,または歪み量の総和と分割領域の境界部の不連続性を最小化する領域分割を求め,その各分割領域に対する変換係数の選択を行う。コスト算出部222により,領域分割に応じた符号化のコスト,すなわち,全分割領域の歪み量の総和(変換係数の切り捨てにより生じる誤差の和),または,分割領域の境界部における不連続性をコストとして考慮する場合には,その不連続性のコストを算出する。その結果をもとに,最適分割処理部22は,コストが最も小さくなる領域分割を最適分割として選択する。

【0112】
領域分割形状設定部21は,最適分割処理部22によって決定された領域分割を示す情報と,その領域分割に対して係数選択部221によって選択された変換係数とを符号化対象情報として,エントロピ符号化部15に出力する。

【0113】
[係数選択処理フロー]
図2は,係数選択処理部20が実行する係数選択処理フローを示す図である。ここでは,主に[領域分割方法4]により領域分割を行う場合の実施例を説明するが,この方法は,[領域分割方法1]~[領域分割方法3]の方法を包含しており,以下の説明から[領域分割方法1]~[領域分割方法3]の領域分割による係数選択処理についても同様に実施することができることは明らかである。

【0114】
この例では,係数選択処理部20は,分割対象領域の係数の総数Kと,処理対象画像の領域(最初は入力画像信号の全領域)とを引数とするSegment関数によって呼び出され,以下の処理を行う。
[ステップS1]:領域を領域1と領域2とに分割するとした場合の領域1の係数の個数k1をループインデックスとして,初期値をk1=0,増分を1とし,k1<Kの間,ステップS1~S3の処理を繰り返す。なお,領域2の係数の個数k2は,k2=K-k1となる。
[ステップS2]:領域1の係数の個数k1と,領域2の係数の個数k2(=K-k1)と,入力領域とを引数として,Opt_sub_div関数(最適分割処理関数)を呼び出す。この関数によって,最適分割処理部22により,図3,図4に示す最適分割処理が実行される。
[ステップS3]:ループインデックスk1に1を加算し,ステップS1以降の処理を繰り返す。k1がK以上になったならばループを終了する。
[ステップS4]:ステップS2の処理結果から領域1,領域2の最適な係数個数を算出する。
[ステップS5]:分割無しラベルを持たない領域の有無を判定し,分割無しラベルを持たない領域がある場合には,ステップS6へ進む。すべての領域が分割無しラベルを持つ領域になった場合には,ステップS8へ進む。
[ステップS6]:コスト関数値が最大の領域を同定する。この領域の係数の個数をK′とする。
[ステップS7]:係数の個数K′とコスト関数値が最大となる領域とを引数とするSegment関数を呼び出し,係数選択処理部20による処理を,分割無しラベルを持つ領域が無くなるまで,再帰的に繰り返す。
[ステップS8]:コスト関数値が最大の領域を同定し,Segment関数の呼び出し元へ戻る。

【0115】
[最適分割処理フロー]
図3および図4に,最適分割処理部22が実行する最適分割処理フローを示す。最適分割処理部22は,図2に示すステップS2におけるOpt_sub_div関数(最適分割処理関数)によって呼び出される。入力は,領域1の係数の個数k1と,領域2の係数の個数k2と,最適分割対象の領域である。
[ステップS10]:縦分割位置(領域を垂直方向に2分割する位置)をループインデックスとして,初期値を0,増分をMとし,縦分割位置<画面縦幅の間,ステップS10~S12の処理を繰り返す。
[ステップS11]:係数の個数k1,k2および縦分割位置を引数として,コスト関数算出関数を呼び出す。この関数によって,コスト算出部222により,図5に示すコスト関数算出処理が実行される。
[ステップS12]:ループインデックスの縦分割位置にMを加算し,ステップS10以降の処理を繰り返す。縦分割位置が画面縦幅以上になったならばループを終了する。
[ステップS13]:コスト関数算出の処理結果から最適縦分割位置を算出し,図4のステップS20へ進む。
[ステップS14]:横分割位置(領域を水平方向に2分割する位置)をループインデックスとして,初期値を0,増分をMとし,横分割位置<画面横幅の間,ステップS14~S16の処理を繰り返す。
[ステップS15]:係数の個数k1,k2および横分割位置を引数として,コスト関数算出関数を呼び出す。この関数によって,コスト算出部222により,図5に示すコスト関数算出処理が実行される。
[ステップS16]:ループインデックスの横分割位置にMを加算し,ステップS14以降の処理を繰り返す。横分割位置が画面横幅以上になったならばループを終了する。
[ステップS17]:コスト関数算出の処理結果から最適横分割位置を算出し,図4のステップS20へ進む。なお,ステップS10~S13とステップS14~S17の処理は,パラレルに実行してもシリアルに実行してもどちらでもよい。
[ステップS20]:最適縦分割位置を用いたコストと最適横分割位置を用いたコストとの大小を比較し,最適縦分割位置を用いたコストのほうが小さい場合には,ステップS21へ進み,そうでない場合には,ステップS25へ進む。
[ステップS21]:一方の分割領域の画素数が0か,または一方の分割領域の変換係数の個数が0の場合,ステップS22へ進み,そうでない場合には,ステップS24へ進む。
[ステップS22]:入力された領域に対して,領域の分割は行わないことを示す分割無しラベルを付与する。
[ステップS23]:Opt_sub_div関数の呼び出し元へ分割無しラベルを返し,処理を終了する。
[ステップS24]:最適縦分割位置の情報,各分割領域の変換係数,各分割領域の近似誤差,コスト関数値を,Opt_sub_div関数の呼び出し元へ返し,処理を終了する。
[ステップS25]:一方の分割領域の画素数が0か,または一方の分割領域の変換係数の個数が0の場合,ステップS26へ進み,そうでない場合には,ステップS28へ進む。
[ステップS26]:入力された領域に対して,領域の分割は行わないことを示す分割無しラベルを付与する。
[ステップS27]:Opt_sub_div関数の呼び出し元へ分割無しラベルを返し,処理を終了する。
[ステップS28]:最適横分割位置の情報,各分割領域の変換係数,各分割領域の近似誤差,コスト関数値を,Opt_sub_div関数の呼び出し元へ返し,処理を終了する。

【0116】
[コスト関数算出処理フロー]
図5に,コスト算出部222が実行するコスト関数算出処理フローを示す。コスト算出部222は,図3に示すステップS11およびS15におけるコスト関数算出関数によって呼び出される。入力は,領域1の係数の個数k1,領域2の係数の個数k2,縦分割位置または横分割位置である。
[ステップS30]:領域1に対して,k1個の係数を選択する係数選択処理を行う。
[ステップS31]:領域1に対して,上記の係数選択処理により選択されたk1個の係数で近似した場合の近似誤差を算出する。
[ステップS32]:領域1に対して,上記の係数選択処理により選択されたk1個の係数で近似した場合の復号信号を得る。その後,ステップS36へ進む。
[ステップS33]:領域2に対して,k2個の係数を選択する係数選択処理を行う。
[ステップS34]:領域2に対して,上記の係数選択処理により選択されたk2個の係数で近似した場合の近似誤差を算出する。
[ステップS35]:領域2に対して,上記の係数選択処理により選択されたk2個の係数で近似した場合の復号信号を得る。なお,ステップS30~S32とステップS33~S35とは,パラレルに実行してもシリアルに実行してもどちらでもよい。
[ステップS36]:領域1,2の復号信号の境界領域に対して,不連続尺度を算出する。
[ステップS37]:領域1,2の近似誤差和にλ×不連続尺度を加算して,コスト関数値を算出する。算出したコスト関数値を,関数の呼び出し元へ返し,処理を終了する。

【0117】
以上の画像符号化の処理は,コンピュータとソフトウェアプログラムとによっても実現することができ,そのプログラムをコンピュータ読み取り可能な記録媒体に記録することも,ネットワークを通して提供することも可能である。

【0118】
図6は,本発明をソフトウェアプログラムを用いて実現する場合のシステムの構成例を示している。メモリ52には,本発明の画像符号化処理を行うための画像符号化プログラム53が格納される。CPU50は,メモリ52に格納された画像符号化プログラム53の命令を逐次フェッチして実行する。映像記憶装置51は,符号化対象の映像信号を記憶する装置である。映像信号は,図示省略したカメラ等から入力するようにしてもよい。画像符号化プログラム53によって生成された符号化ストリームは,符号化ストリーム記憶装置54に格納される。または,ネットワークアダプタ等のインタフェースを介して,符号化ストリームを外部装置に出力してもよい。システムバス55は,CPU50,映像記憶装置51,メモリ52,符号化ストリーム記憶装置54を接続するバスである。
【符号の説明】
【0119】
10 画像符号化装置
11 変換部
12 逆変換部
13 歪除去フィルタ
14 予測部
15 エントロピ符号化部
20 係数選択処理部
21 領域分割形状設定部
22 最適分割処理部
221 係数選択部
222 コスト算出部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6