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

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

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5561611号 (P5561611)
公開番号 特開2012-089963 (P2012-089963A)
登録日 平成26年6月20日(2014.6.20)
発行日 平成26年7月30日(2014.7.30)
公開日 平成24年5月10日(2012.5.10)
発明の名称または考案の名称 画像符号化方法,画像符号化装置および画像符号化プログラム
国際特許分類 H04N  19/60        (2014.01)
H03M   7/30        (2006.01)
FI H04N 19/60
H03M 7/30 Z
請求項の数または発明の数 10
全頁数 19
出願番号 特願2010-233229 (P2010-233229)
出願日 平成22年10月18日(2010.10.18)
審査請求日 平成25年7月22日(2013.7.22)
特許権者または実用新案権者 【識別番号】000004226
【氏名又は名称】日本電信電話株式会社
【識別番号】899000068
【氏名又は名称】学校法人早稲田大学
発明者または考案者 【氏名】坂東 幸浩
【氏名】高村 誠之
【氏名】如澤 裕尚
【氏名】石川 孝明
【氏名】渡辺 裕
個別代理人の代理人 【識別番号】100087848、【弁理士】、【氏名又は名称】小笠原 吉義
【識別番号】100103827、【弁理士】、【氏名又は名称】平岡 憲一
審査官 【審査官】堀井 啓明
参考文献・文献 特開2010-199959(JP,A)
特開平05-276499(JP,A)
特開2003-299100(JP,A)
特開平09-074561(JP,A)
特開2002-077568(JP,A)
調査した分野 H04N19/00-19/98
H03M3/00-11/00
特許請求の範囲 【請求項1】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い,得られた変換係数を絞り込み,絞り込んだ結果の有意変換係数を符号化する画像符号化方法において,
画像の領域を分割する複数の分割候補となる位置のそれぞれについて,分割位置を設定する過程と,
前記設定された分割位置で画像の領域を分割し,閾値一定の条件下で,各分割領域における前記閾値以下の変換係数を切り捨てる過程と,
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で,全領域の有意変換係数の個数または変換係数の切り捨てによる誤差の和が最小となる領域分割を選択するとともに,各分割領域における符号化に用いる有意変換係数を選択する過程とを有する
ことを特徴とする画像符号化方法。
【請求項2】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い,得られた変換係数を絞り込み,絞り込んだ結果の有意変換係数を符号化する画像符号化方法において,
画像の領域を分割する複数の分割候補となる位置のそれぞれについて,分割位置を設定する過程と,
前記設定された分割位置で画像の領域を分割し,閾値の変動を一定範囲内許容するという条件下で,各分割領域における前記閾値以下の変換係数を切り捨てる過程と,
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で,全領域の有意変換係数の個数または変換係数の切り捨てによる誤差の和が最小となる領域分割を選択するとともに,各分割領域における符号化に用いる有意変換係数を選択する過程とを有する
ことを特徴とする画像符号化方法。
【請求項3】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い,得られた変換係数を絞り込み,絞り込んだ結果の有意変換係数を符号化する画像符号化方法において,
画像の領域を分割する複数の分割候補となる位置のそれぞれについて,分割位置を設定する過程と,
前記設定された分割位置で画像の領域を分割し,閾値一定の条件下で,各分割領域における前記閾値以下の変換係数を切り捨てる過程と,
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で,全領域の有意変換係数の個数または変換係数の切り捨てによる誤差の和と,分割領域の境界部に接する所定幅の二つの境界領域における変換係数の絞り込みに基づく近似誤差の乖離度との重み付き和を最小化する領域分割を選択するとともに,各分割領域における符号化に用いる有意変換係数を選択する過程とを有する
ことを特徴とする画像符号化方法。
【請求項4】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い,得られた変換係数を絞り込み,絞り込んだ結果の有意変換係数を符号化する画像符号化方法において,
画像の領域を分割する複数の分割候補となる位置のそれぞれについて,分割位置を設定する過程と,
前記設定された分割位置で画像の領域を分割し,閾値の変動を一定範囲内許容するという条件下で,各分割領域における前記閾値以下の変換係数を切り捨てる過程と,
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で,全領域の有意変換係数の個数または変換係数の切り捨てによる誤差の和と,分割領域の境界部に接する所定幅の二つの境界領域における変換係数の絞り込みに基づく近似誤差の乖離度との重み付き和を最小化する領域分割を選択するとともに,各分割領域における符号化に用いる有意変換係数を選択する過程とを有する
ことを特徴とする画像符号化方法。
【請求項5】
請求項1から請求項4までのいずれか1項に記載の画像符号化方法において,
前記選択された領域分割における各分割領域に対して,所定の分割の終了条件が満たされるまで,前記領域分割および有意変換係数を選択する処理を再帰的に繰り返す
ことを特徴とする画像符号化方法。
【請求項6】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い,得られた変換係数を絞り込み,絞り込んだ結果の有意変換係数を符号化する画像符号化装置において,
画像の領域を分割する複数の分割候補となる位置のそれぞれについて,分割位置を設定する手段と,
前記設定された分割位置で画像の領域を分割し,閾値一定の条件下で,各分割領域における前記閾値以下の変換係数を切り捨てる手段と,
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で,全領域の有意変換係数の個数または変換係数の切り捨てによる誤差の和が最小となる領域分割を選択するとともに,各分割領域における符号化に用いる有意変換係数を選択する手段とを備える
ことを特徴とする画像符号化装置。
【請求項7】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い,得られた変換係数を絞り込み,絞り込んだ結果の有意変換係数を符号化する画像符号化装置において,
画像の領域を分割する複数の分割候補となる位置のそれぞれについて,分割位置を設定する手段と,
前記設定された分割位置で画像の領域を分割し,閾値の変動を一定範囲内許容するという条件下で,各分割領域における前記閾値以下の変換係数を切り捨てる手段と,
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で,全領域の有意変換係数の個数または変換係数の切り捨てによる誤差の和が最小となる領域分割を選択するとともに,各分割領域における符号化に用いる有意変換係数を選択する手段とを備える
ことを特徴とする画像符号化装置。
【請求項8】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い,得られた変換係数を絞り込み,絞り込んだ結果の有意変換係数を符号化する画像符号化装置において,
画像の領域を分割する複数の分割候補となる位置のそれぞれについて,分割位置を設定する手段と,
前記設定された分割位置で画像の領域を分割し,閾値一定の条件下で,各分割領域における前記閾値以下の変換係数を切り捨てる手段と,
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で,全領域の有意変換係数の個数または変換係数の切り捨てによる誤差の和と,分割領域の境界部に接する所定幅の二つの境界領域における変換係数の絞り込みに基づく近似誤差の乖離度との重み付き和を最小化する領域分割を選択するとともに,各分割領域における符号化に用いる有意変換係数を選択する手段とを備える
ことを特徴とする画像符号化装置。
【請求項9】
入力された画像信号に対して冗長系の変換基底を用いた変換を行い,得られた変換係数を絞り込み,絞り込んだ結果の有意変換係数を符号化する画像符号化装置において,
画像の領域を分割する複数の分割候補となる位置のそれぞれについて,分割位置を設定する手段と,
前記設定された分割位置で画像の領域を分割し,閾値の変動を一定範囲内許容するという条件下で,各分割領域における前記閾値以下の変換係数を切り捨てる手段と,
前記複数の分割候補となる位置でそれぞれ分割したすべての領域分割の中で,全領域の有意変換係数の個数または変換係数の切り捨てによる誤差の和と,分割領域の境界部に接する所定幅の二つの境界領域における変換係数の絞り込みに基づく近似誤差の乖離度との重み付き和を最小化する領域分割を選択するとともに,各分割領域における符号化に用いる有意変換係数を選択する手段とを備える
ことを特徴とする画像符号化装置。
【請求項10】
請求項1から請求項5までのいずれか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】
miny ∥y∥0 +λ∥Φy-x∥2 2 (4)
ここでλは,外部から与えられる重みパラメータである。第一項は,選択された変換係数の個数であり,変換係数の情報量を近似した値である。第二項は変換係数の選択に伴う再構成誤差を表しており,符号化歪みを表している。∥・∥2 2 は,L2 ノルムの二乗値であり,二乗和を表す。しかし,上記の最小化問題はNP困難であるため,従来,以下のような1 ノルムに最小化問題として近似する方法がとられてきた。
【0012】
miny ∥y∥1 +λ∥Φy-x∥2 2 (5)
ここで,∥・∥1 は,1 ノルムであり,ベクトルの要素の絶対値和を表している。
【0013】
式(5) の最小化問題の準最適解を与える手法として,図8に示すノイズ・シェイピング(noise shaping) 処理と呼ばれる手法が提案されている(非特許文献1参照)。
【0014】
使用する記号を整理する。入力信号x(N画素)に対する順変換後の変換係数を以下のように定義する。
【0015】
0 =Ψx
Iを単位行列として,Ps ≡ΨΦ,P⊥≡I-ΨΦなる2種類の射影を定義する。なお,“P⊥”における“⊥”は,Pの右肩に付く上添字である。前者の射影により得られる出力を有効成分,後者の射影により得られる出力を無効成分と呼ぶ。
【0016】
ノイズ・シェイピング処理における繰り返し回数を表すインデックスをiで表し,ノイズ・シェイピング処理における第i回目の出力をyi とする。yi に対して,絶対値が閾値θi 以下となる係数を零値に切り捨てるクリッピング処理を行う。yi に対するクリッピング処理後の出力を^yi (^はyの上に付く記号)として,次式のように表す。
【0017】
^yi (θi )=yi +εi (θi
ここで,εi (θi )は,クリッピング処理に伴い重畳する誤差である。k=1の場合,ノイズ・シェイピング処理における補正信号であるwi (θi )(図8に示すwi )は,次式となる。
【0018】
i (θi )=y0 -ΨΦ^yi (θi
この^yi (θi ),wi (θi )を用いて,yi+1 は,次式のように表せる。
【0019】
i+1 (θi ,^yi (θi ))=^yi (θi )+wi (θi
クリッピングの閾値θi は,Δi (>0)を用いて,次のように定められ,
θi+1 =θi -Δi (6)
繰り返し回数の増加とともに,小さく設定される。
【0020】
図8に示すノイズ・シェイピング処理装置200の動作について簡単に説明する。変換部201では,入力信号xに対して冗長系の変換基底を用いた変換を行い,変換係数y0 を算出する。クリッピング処理部202では,変換係数yi (初期値はi=0)と予め定められた閾値θi との大小比較を行い,yi がθi より小さければ,yi を0に置き換える。このクリッピング処理後の出力を^yi とする。逆変換部203では,^yi を逆変換して逆変換結果の^xi を求める。入力信号xと^xi との差が,画素領域での誤差ei となる。
【0021】
重み係数乗算部204では,ei に所定の重み係数kを乗算し,乗算結果に対して,変換部205において順変換することにより,誤差の帰還信号wi を算出する。クリッピング処理部202の出力^yi に誤差の帰還信号wi を加算することにより,更新変換係数yi+1 を算出する。遅延部206にて一定時間遅延させた後,更新変換係数yi+1 をクリッピング処理部202の入力として,更新変換係数yi+1 に対して同様に処理を繰り返す。終了条件判定部207では,ei+1 とei との差がある一定の微小値より小さくなったかどうかをチェックし,その差が微小値より小さい値になったときに,そのときの^yi を変換結果として出力する。
【0022】
このような過完備系を用いた変換は,画像信号にsparsenessを仮定し,少数の変換係数で画像を表現するsparse representationの一種である。
【先行技術文献】
【0023】

【非特許文献1】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
【発明の概要】
【発明が解決しようとする課題】
【0024】
画像信号は,空間的な局所性を有しており,その性質は一様ではない。つまり,画像信号を一定の精度で表現するために必要な変換係数の個数,あるいは,一定の個数の変換係数で表現可能な画像信号の表現精度は,画像内の領域の性質に応じて変動する。しかし,上述したノイズ・シェイピング法は,画像全体に対して適用されている。このため,画像内の局所性を考慮できておらず,符号化効率の向上に改善の余地を残す。
【0025】
本発明はかかる事情に鑑みてなされたものであって,過完備な基底を用いた冗長変換において,変換係数間の冗長性を除去するノイズ・シェイピング法において,符号化効率の向上を実現する画像分割手法に基づく画像符号化方法を確立することを目的とする。
【課題を解決するための手段】
【0026】
本発明は,上記課題を解決するため,入力された画像信号に対して,冗長系の変換基底を用いた変換を行い,得られた変換係数に対して,符号化に用いる係数の絞り込みを行う画像符号化において,画像の局所的な性質に応じて,閾値一定の条件下で,同閾値以下の係数を切り捨て,全領域の有意係数の個数を最小化するための領域分割,および,各分割領域に対する変換係数の選択を行うことを特徴とする。
【0027】
また,本発明は,入力された画像信号に対して,冗長系の変換基底を用いた変換を行い,得られた変換係数に対して,符号化に用いる係数の絞り込みを行う画像符号化において,画像の局所的な性質に応じて,閾値の変動を一定範囲内許容するという条件下で,同閾値以下の係数を切り捨て,全領域の有意係数の個数を最小化するための領域分割,および,各分割領域に対する変換係数の選択を行うことを特徴とする。
【0028】
また,本発明は,入力された画像信号に対して,冗長系の変換基底を用いた変換を行い,得られた変換係数に対して,符号化に用いる係数の絞り込みを行う画像符号化において,画像の局所的な性質に応じて,閾値一定の条件下で,同閾値以下の係数を切り捨て,全領域の有意係数の個数および分割領域の境界部の不連続性を最小化するための領域分割,および,各分割領域に対する変換係数の選択を行うことを特徴とする。
【0029】
また,本発明は,入力された画像信号に対して,冗長系の変換基底を用いた変換を行い,得られた変換係数に対して,符号化に用いる係数の絞り込みを行う画像符号化において,画像の局所的な性質に応じて,閾値の変動を一定範囲内許容するという条件下で,同閾値以下の係数を切り捨て,全領域の有意係数の個数および分割領域の境界部の不連続性を最小化するための領域分割,および,各分割領域に対する変換係数の選択を行うことを特徴とする。
【0030】
また,本発明は,上記発明においてさらに,選択された領域分割における各分割領域に対して,所定の分割の終了条件が満たされるまで,領域分割および有意変換係数を選択する処理を再帰的に繰り返すことを特徴とする。分割の終了条件は,例えば一方の分割領域の画素数が所定の閾値以下となること,または一方の分割領域の有意変換係数の個数が所定の閾値以下となることである。また,さらに分割を行わないほうが最適である場合も分割の終了条件となる。
【発明の効果】
【0031】
本発明は,画像の局所性を考慮して,係数選択を行うことで,ノイズ・シェイピングにおけるエネルギーコンパクションを向上させ,特定成分への情報の集約を図ることで,符号化効率の向上を実現することができる。
【図面の簡単な説明】
【0032】
【図1】本発明の実施形態に係る画像符号化装置の構成例を示す図である。
【図2】係数選択処理部が実行する係数選択処理フローを示す図である。
【図3】最適分割処理部が実行する最適分割処理フローを示す図である。
【図4】最適分割処理部が実行する最適分割処理フローを示す図である。
【図5】コスト算出部が実行するコスト関数算出処理フローを示す図である。
【図6】ソフトウェアプログラムより実現するときのシステム構成図である。
【図7】一般的な符号化装置の構成図である。
【図8】従来のノイズ・シェイピング処理装置の例を示す図である。
【発明を実施するための形態】
【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)に対して,ノイズ・シェイピング法を用いて閾値δ以上の変換係数を選択する。このとき選択された変換係数の個数を,R[x,s0 ,t0 ,w,h,δ]とおく。さらに,k=R[x,s0 ,t0 ,w,h,δ]と略記し,変換係数として,{c0 ,…,c k-1 }が選択されたものとする。選択された基底信号を用いてx(s0 ,t0 ,w,h)を表現した場合の近似誤差を,E[x,s0 ,t0 ,w,h,k,C(δ)]とおく。ここで,C(δ)は,閾値δ以上の変換係数C(δ)={c0 ,…,c k-1 }を表す。例えば,DTCWTの場合,総数2n個の係数の中からk個の係数を選択したことになる。

【0041】
[領域分割方法1]
画面内において,閾値一定の条件下で,同閾値以下の係数を切り捨て(零値とし),全領域の有意係数の個数を最小化するための分割を考える。さらに,垂直に2分割する場合と水平に2分割する場合の結果を比較し,上記有意係数の個数最小化の規範に基づき,垂直分割・水平分割のいずれかを選択する。

【0042】
領域分割の尺度として,次の有意係数の個数を用いる。

【0043】
Ξhor [x,0,h,W,H,δu δd
=R[x,0,0,W,h,δu ]+R[x,0,h,W,H-h,δd
上式は,領域0≦s≦W,0≦t≦Hを,上側領域0≦s≦W,0≦t≦h-1と,下側領域0≦s≦W,≦t≦Hに分割し,上側領域・下側領域を各々,閾値δu 以上の振幅値の係数,閾値δd 以上の振幅値の係数で表現した場合の変換係数の個数の和を表している。


【0044】
Ξver [x,w,0,W,H,δl ,δr
=R[x,0,0,w,H,δl ]+R[x,w,0,W-w,H,δr
上式は,領域0≦s≦W,0≦t≦Hを,左側領域0≦s≦w-1,0≦t≦Hと,右側領域w≦s≦W,0≦t≦Hに分割し,左側領域・右側領域を各々,閾値δl 以上の振幅値の係数,閾値δr 以上の振幅値の係数で表現した場合の変換係数の個数の和を表している。

【0045】
閾値としてδが与えられるものとして,垂直方向に2分割する場合,次式に基づき分割位置を決定する。垂直方向に2分割する場合の分割位置h0 は,次式で与えられる。

【0046】
【数1】
JP0005561611B2_000002t.gif

【0047】
同様に,閾値としてδが与えられるものとして,水平方向に2分割する場合,次式に基づき分割位置を決定する。水平方向に2分割する場合の分割位置w0 は,次式で与えられる。

【0048】
【数2】
JP0005561611B2_000003t.gif

【0049】
上記式において,Mh ,Mw は,分割位置を指定する粒度を決定するパラメータであり,予め与えられるものとする。このとき,
Ξhor [x,0,h0 ,W,H,δ,δ]
≦ Ξver [x,w0 ,0,W,H,δ,δ]
となる場合には,t=h0 の位置で垂直方向に分割を行うこととし,それ以外の場合には,s=w0 の位置で水平方向に分割を行うこととする。なお,h0 =0あるいはw0 =0となる場合,分割を行わないほうが最適であるので分割は行われない。

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

【0051】
[領域分割方法2]
画面内において,画面内の領域毎に閾値を設定し,かつ,領域間の閾値の差分値が一定範囲内であるという条件下で,閾値以下の係数を切り捨て(零値とし),全領域の有意係数の個数を最小化するための分割を考える。さらに,垂直に2分割する場合と水平に2分割する場合の結果を比較し,上記有意係数の個数最小化の規範に基づき,垂直分割・水平分割のいずれかを選択する。領域分割の尺度として,前述の有意係数の個数を用いる。

【0052】
閾値としてδが与えられるものとして,分割後の2つの領域での閾値の差を閾値ζ以内に保つ条件下で,垂直方向に2分割する場合,次式に基づき分割位置を決定する。垂直方向に2分割する場合の分割位置h0 は,次式で与えられる。

【0053】
【数3】
JP0005561611B2_000004t.gif

【0054】
分割後の2つの領域での閾値の差を閾値ζ以内に保つ条件下で,水平方向に2分割する場合,次式に基づき分割位置を決定する。水平方向に2分割する場合の分割位置w0 は,次式で与えられる。

【0055】
【数4】
JP0005561611B2_000005t.gif

【0056】
ここで,βは,係数選択の閾値を指定する粒度を決定するパラメータであり,予め与えられるものとする。このとき,
Ξhor [x,0,h0 ,W,H,δ,δ+βjd,0
≦ Ξver [x,w0 ,0,W,H,δ,δ+βjr,0
となる場合には,t=h0 の位置で垂直方向に分割を行うこととし,それ以外の場合には,s=w0 の位置で水平方向に分割を行うこととする。なお,h0 =0あるいはw0 =0となる場合,分割を行わないほうが最適であるので分割は行われない。

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

【0058】
[領域分割方法3]
画面内において,閾値一定の条件下で,同閾値以下の係数を切り捨て(零値とし),全領域の有意係数の個数を最小化するための分割を考える。さらに,垂直に2分割する場合と水平に2分割する場合の結果を比較し,上記有意係数の個数最小化の規範に基づき,垂直分割・水平分割のいずれかを選択する。

【0059】
領域分割の尺度として,前述の有意係数の個数および分割境界の不連続性の評価尺度(不連続尺度)を用いる。不連続尺度は,以下の境界領域に対して定義する。垂直分割の場合,上側領域(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を対象とし,同矩形領域に対する不連続尺度を次のように表す。

【0060】
Θhor [x,0,W,h-L,2L+1,δu ,δd ,Cu ,Cd
ここで,第2,3引数は,分割前後の領域に対する水平方向の存在領域0≦s≦Wの下限・上限を示している。第4,5引数は,境界領域に対する垂直方向の存在領域の下限h-Lおよび同領域の垂直方向の幅2L+1を示している。第6,7引数δu ,δd は,上側領域および下側領域における係数の切り捨てに用いる閾値である。同閾値以下の係数は切り捨て,零値とする。第8,9引数Cu ,Cd は,閾値以下の係数を切り捨てた後に得られる上側領域および下側領域における係数である。

【0061】
水平分割の場合,左側領域(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を対象とし,同矩形領域に対する不連続尺度を次のように表す。

【0062】
Θver [x,0,H,w-L,2L+1,δl ,δr ,Cl ,Cr
ここで,第2,3引数は,分割前後の領域に対する垂直方向の存在領域0≦t≦Hの下限・上限を示している。第4,5引数は,境界領域に対する水平方向の存在領域の下限w-Lおよび同領域の水平方向の幅2L+1を示している。第6,7引数δl ,δr は,左側領域および右側領域における係数の切り捨てに用いる閾値である。同閾値以下の係数は切り捨て,零値とする。第8,9引数Cl ,Cr は,閾値以下の係数を切り捨てた後に得られる左側領域および右側領域における係数である。

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

【0064】
また,分割境界領域におけるSSIM(下記の参考文献1参照)の符号を反転した値を用いることも可能である。
〔参考文献1〕:Z. Wang and E. P. Simoncelli,“Translation insensitive image similarity in complex wavelet domain”,IEEE International Conference on Acoustics, Speech and Signal Processing, vol. II, pp. 573-576, Philadelphia, PA, Mar. 2005 .
閾値としてδが与えられるものとして,垂直方向に2分割する場合,次式に基づき分割位置を決定する。垂直方向に2分割する場合の分割位置h0 は,次式で与えられる。

【0065】
【数5】
JP0005561611B2_000006t.gif

【0066】
同様に,閾値としてδが与えられるものとして,水平方向に2分割する場合,次式に基づき分割位置を決定する。水平方向に2分割する場合の分割位置w0 は,次式で与えられる。

【0067】
【数6】
JP0005561611B2_000007t.gif

【0068】
上記式において,Mh ,Mw は,分割位置を指定する粒度を決定するパラメータであり,予め与えられるものとする。このとき,
Ξhor [x,0,h0 ,W,H,δ,δ]+λΘhor [x,0,W,h0 -L,2L+1,δ,δ,Cu ,Cd
≦ Ξver [x,w0 ,0,W,H,δ,δ]+λΘver [x,0,H,w0 -L,2L+1,δ,δ,Cl ,Cr
となる場合には,t=h0 の位置で垂直方向に分割を行うこととし,それ以外の場合には,s=w0 の位置で水平方向に分割を行うこととする。なお,h0 =0あるいはw0 =0となる場合,分割を行わないほうが最適であるので分割は行われない。

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

【0070】
[領域分割方法4]
画面内において,画面内の領域毎に閾値を設定し,かつ,領域間の閾値の差分値が一定範囲内であるという条件下で,閾値以下の係数を切り捨て(零値とし),全領域の有意係数の個数を最小化するための分割を考える。さらに,垂直に2分割する場合と水平に2分割する場合の結果を比較し,上記有意係数の個数最小化の規範に基づき,垂直分割・水平分割のいずれかを選択する。

【0071】
領域分割の尺度として前述の有意係数の個数および分割境界の不連続性の評価尺度(不連続尺度)を用いる。

【0072】
閾値としてδが与えられるものとして,分割後の2つの領域での閾値の差を閾値ζ以内に保つ条件下で,垂直方向に2分割する場合,次式に基づき分割位置を決定する。垂直方向に2分割する場合の分割位置h0 は,次式で与えられる。

【0073】
【数7】
JP0005561611B2_000008t.gif

【0074】
分割後の2つの領域での閾値の差を閾値ζ以内に保つ条件下で,水平方向に2分割する場合,次式に基づき分割位置を決定する。水平方向に2分割する場合の分割位置w0 は,次式で与えられる。

【0075】
【数8】
JP0005561611B2_000009t.gif

【0076】
ここで,βは,係数選択の閾値を指定する粒度を決定するパラメータであり,予め与えられるものとする。このとき,
Ξhor [x,0,h0 ,W,H,δ,δ+βjd,0 ]+λΘhor [x,0,W,h0 -L,2L+1,δ,δ+βjd,0 ,Cu ,Cd
≦ Ξver [x,w0 ,0,W,H,δ,δ+βjr,0 ]+λΘver [x,0,H,w0 -L,2L+1,δ,δ+βjr,0 ,Cl ,Cr
となる場合には,t=h0 の位置で垂直方向に分割を行うこととし,それ以外の場合には,s=w0 の位置で水平方向に分割を行うこととする。なお,h0 =0あるいはw0 =0となる場合,分割を行わないほうが最適であるので分割は行われない。

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

【0078】
次に,以上説明した領域分割方法を用いて最適な領域分割を行い,変換係数の絞り込みを行って有意変換係数を符号化する画像符号化装置と,その処理フローの例について説明する。

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

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

【0081】
係数選択処理部20における有意変換係数の選択は,次のように行われる。まず,最適分割処理部22は,画像の領域を分割する複数の分割候補となる位置のそれぞれについて分割位置を設定し,領域分割を行い,係数選択部221により,各分割領域で閾値以下の変換係数を切り捨てることにより有意変換係数を選択する。また,コスト算出部222により,領域分割に応じた符号化のコスト,例えば全領域の有意変換係数の個数,変換係数の切り捨てにより生じる誤差の和,または,分割領域の境界部における不連続性をコストとして考慮する場合には,その不連続性のコストを算出する。その結果をもとに,最適分割処理部22は,コストが最も小さくなる領域分割を最適分割として選択する。

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

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

【0084】
この例では,係数選択処理部20は,閾値δと,閾値の変動を一定範囲内許容する場合の変動範囲の閾値ζと,係数選択の閾値を指定する粒度を決定するパラメータであるβと,処理対象画像の領域(最初は入力画像信号の全領域)とを引数とするSegment関数によって呼び出され,以下の処理を行う。
[ステップS1]:領域を領域1と領域2とに分割するとした場合の領域2の係数選択の閾値δ2をループインデックスとして,初期値をδ2=δ-ζβとし,増分をβとし,δ2≦δ+βζの間,ステップS1~S5の処理を繰り返す。
[ステップS2]:領域1の係数選択の閾値δ1をループインデックスとして,初期値をδ1=δ-ζβとし,増分をβとし,δ1≦δ+βζの間,ステップS2~S4の処理を繰り返す。
[ステップS3]:δ1,δ2および入力領域を引数として,Opt_sub_div関数を呼び出す。この関数によって,最適分割処理部22により,図3,図4に示す最適分割処理が実行される。
[ステップS4]:ループインデックスδ1にζβを加算し,ステップS2以降の処理を繰り返す。δ1がδ+ζβ以上になったならばループを終了する。
[ステップS5]:ループインデックスδ2にζβを加算し,ステップS1以降の処理を繰り返す。δ2がδ+ζβ以上になったならばループを終了する。
[ステップS6]:ステップS3の処理結果から最適な係数個数を算出する。
[ステップS7]:分割無しラベルを持たない領域の有無を判定し,分割無しラベルを持たない領域がある場合には,ステップS8を実行する。すべての領域が分割無しラベルを持つ領域になった場合には,処理を終了する。
[ステップS8]:分割無しラベルを持つ領域の中でコスト関数が最大となる領域を選択し,δと,ζと,βと,コスト関数が最大となる領域とを引数とするSegment関数を呼び出し,係数選択処理部20による処理を,分割無しラベルを持つ領域が無くなるまで,再帰的に繰り返す。

【0085】
[最適分割処理フロー]
図3および図4に,最適分割処理部22が実行する最適分割処理フローを示す。最適分割処理部22は,図2に示すステップS3におけるOpt_sub_div関数(最適分割処理関数)によって呼び出される。入力は,領域1の係数選択の閾値δ1,領域2の係数選択の閾値δ2,最適分割対象の領域である。
[ステップS10]:縦分割位置(領域を垂直方向に2分割する位置)をループインデックスとして,初期値を0,増分をMとし,縦分割位置<画面縦幅の間,ステップS10~S12の処理を繰り返す。
[ステップS11]:δ1,δ2および縦分割位置を引数として,コスト関数算出関数を呼び出す。この関数によって,コスト算出部222により,図5に示すコスト関数算出処理が実行される。
[ステップS12]:ループインデックスの縦分割位置にMを加算し,ステップS10以降の処理を繰り返す。縦分割位置が画面縦幅以上になったならばループを終了する。
[ステップS13]:コスト関数算出の処理結果から最適縦分割位置を算出し,図4のステップS20へ進む。
[ステップS14]:横分割位置(領域を水平方向に2分割する位置)をループインデックスとして,初期値を0,増分をMとし,横分割位置<画面横幅の間,ステップS14~S16の処理を繰り返す。
[ステップS15]:δ1,δ2および横分割位置を引数として,コスト関数算出関数を呼び出す。この関数によって,コスト算出部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関数の呼び出し元へ返し,処理を終了する。

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

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

【0088】
図6は,本発明をソフトウェアプログラムを用いて実現する場合のシステムの構成例を示している。メモリ52には,本発明の画像符号化処理を行うための画像符号化プログラム53が格納される。CPU50は,メモリ52に格納された画像符号化プログラム53の命令を逐次フェッチして実行する。映像記憶装置51は,符号化対象の映像信号を記憶する装置である。映像信号は,図示省略したカメラ等から入力するようにしてもよい。画像符号化プログラム53によって生成された符号化ストリームは,符号化ストリーム記憶装置54に格納される。または,ネットワークアダプタ等のインタフェースを介して,符号化ストリームを外部装置に出力してもよい。システムバス55は,CPU50,映像記憶装置51,メモリ52,符号化ストリーム記憶装置54を接続するバスである。
【符号の説明】
【0089】
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
【図8】
7