(57)【要約】  符号化対象の画素の値を、復号済み画像から空間予測または時間予測により生成される予測値を用いて符号化する画像信号の符号化方法。符号化対象の画素の値の予測を行い、予測値を得、前記得られた予測値に対し、原画素値がどのような値をとっているのかという確率分布のデータを、予め蓄積されている予測符号化における原画素値と予測値との差分の分布データを予測値に応じてシフトさせることにより算出し、前記得られた確率分布のデータを原画素値が取り得る下限値から上限値までの範囲にクリッピングし、クリッピングされた原画素値の下限値から上限値までの確率分布のデータを用いて、符号化対象の画素の値を符号化する。
2009057506.tif 000002
【特許請求の範囲】
【請求項１】
符号化対象の画素の値を、復号済み画像から空間予測または時間予測により生成される予測値を用いて符号化する画像信号の符号化方法であって、
符号化対象の画素の値の予測を行い、予測値を得るステップと、
前記得られた予測値に対し、原画素値がどのような値をとっているのかという確率分布のデータを、予め蓄積されている予測符号化における原画素値と予測値との差分の分布データを予測値に応じてシフトさせることにより算出するステップと、
前記得られた確率分布のデータを原画素値が取り得る下限値から上限値までの範囲にクリッピングするステップと、
前記クリッピングされた原画素値の下限値から上限値までの確率分布のデータを用いて、符号化対象の画素の値を符号化するステップとを有する
ことを特徴とする画像符号化方法。
【請求項２】
請求項１に記載の画像符号化方法であって、
前記符号化対象の画素の値が所定の画素ブロックに対応づけられるように、前記予測を画素ブロック単位で行い、
前記画素値を符号化するステップでは、ブロック予測による画素ブロック値に対して求められた前記確率分布のデータをもとに、量子化代表ベクトルを定め、前記画素ブロック値をベクトル量子化することにより符号化する
ことを特徴とする画像符号化方法。
【請求項３】
復号対象の画素の値を、復号済み画像から空間予測または時間予測により生成される予測値を用いて復号する画像信号の復号方法であって、
復号対象の画素の値の予測を行い、予測値を得るステップと、
前記得られた予測値に対し、原画素値がどのような値をとっているのかという確率分布のデータを、予め蓄積されている予測符号化における原画素値と予測値との差分の分布データを予測値に応じてシフトさせることにより算出するステップと、
前記得られた確率分布のデータを原画素値が取り得る下限値から上限値までの範囲にクリッピングするステップと、
前記クリッピングされた原画素値の下限値から上限値までの確率分布のデータを用いて、復号対象の画素の値を復号するステップとを有する
ことを特徴とする画像復号方法。
【請求項４】
請求項３に記載の画像復号方法であって、
前記復号対象の画素の値が所定の画素ブロックに対応づけられるように、前記予測を画素ブロック単位で行い、
前記画素値を復号するステップでは、ブロック予測による画素ブロック値に対して求められた前記確率分布のデータをもとに量子化代表ベクトルを定め、復号対象のベクトル量子化された画素ブロック値を、前記定められた量子化代表ベクトルに従って復号する
ことを特徴とする画像復号方法。
【請求項５】
符号化対象の画素の値を、復号済み画像から空間予測または時間予測により生成される予測値を用いて符号化する画像信号の符号化装置であって、
符号化対象の画素の値の画素値予測を行い、予測値を得る予測手段と、
前記得られた予測値に対し、原画素値がどのような値をとっているのかという確率分布のデータを、予め蓄積されている予測符号化における原画素値と予測値との差分の分布データを予測値に応じてシフトさせることにより算出する手段と、
前記得られた確率分布のデータを原画素値が取り得る下限値から上限値までの範囲にクリッピングする手段と、
前記クリッピングされた原画素値の下限値から上限値までの確率分布のデータを用いて、符号化対象の画素の値を符号化する符号化手段とを備える
ことを特徴とする画像符号化装置。
【請求項６】
請求項５に記載の画像符号化装置であって、
前記予測手段は、前記符号化対象の画素の値が所定の画素ブロックに対応づけられるように、前記予測を画素ブロック単位で行い、
前記符号化手段は、ブロック予測による画素ブロック値に対して求められた前記確率分布のデータをもとに、量子化代表ベクトルを定め、前記画素ブロック値をベクトル量子化することにより符号化する
ことを特徴とする画像符号化装置。
【請求項７】
復号対象の画素の値を、復号済み画像から空間予測または時間予測により生成される予測値を用いて復号する画像信号の復号装置であって、
復号対象の画素の値のの画素値予測を行い、予測値を得る予測手段と、
前記得られた予測値に対し、原画素値がどのような値をとっているのかという確率分布のデータを、予め蓄積されている予測符号化における原画素値と予測値との差分の分布データを予測値に応じてシフトさせることにより算出する手段と、
前記得られた確率分布のデータを原画素値が取り得る下限値から上限値までの範囲にクリッピングする手段と、
前記クリッピングされた原画素値の下限値から上限値までの確率分布のデータを用いて、復号対象の画素の値を復号する復号手段とを備える
ことを特徴とする画像復号装置。
【請求項８】
請求項７に記載の画像復号装置であって、
前記予測手段は、前記復号対象の画素の値が所定の画素ブロックに対応づけられるように、前記予測を画素ブロック単位で行い、
前記復号手段では、ブロック予測による画素ブロック値に対して求められた前記確率分布のデータをもとに量子化代表ベクトルを定め、復号対象のベクトル量子化された画素ブロック値を、前記定められた量子化代表ベクトルに従って復号する
ことを特徴とする画像復号装置。
【請求項９】
請求項１に記載された画像符号化方法を、コンピュータに実行させるための画像符号化プログラム。
【請求項１０】
請求項３に記載された画像復号方法を、コンピュータに実行させるための画像復号プログラム。
【請求項１１】
請求項１に記載された画像符号化方法を、コンピュータに実行させるための画像符号化プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１２】
請求項３に記載され画像復号方法を、コンピュータに実行させるための画像復号プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像（静止画像もしくは映像(動画像)）を効率よく符号化・復号する高能率画像符号化方式の技術に関する。
本願は、２００７年１０月３０日に出願された特願２００７−２８１５５６号に基づき優先権を主張し、その内容をここに援用する。
【背景技術】
【０００２】
画像（静止画像もしくは映像）の符号化においては、既に復号された画素を用いて、符号化対象の画素値を、空間方向の予測や時間方向の予測方法により予測する予測符号化方式が主流である。【０００３】
例えばＨ．２６４／ＡＶＣでは、４×４ブロックのイントラ水平予測において、符号化対象のＡからＰまで（以下、Ａ...Ｐと表記する。他も同様）の４×４ブロックを、既に復号済みの左隣の画素ａ...ｄを使い、
→  →  →  →
ａ｜Ａ  Ｂ  Ｃ  Ｄ
ｂ｜Ｅ  Ｆ  Ｇ  Ｈ
ｃ｜Ｉ  Ｊ  Ｋ  Ｌ
ｄ｜Ｍ  Ｎ  Ｏ  Ｐ
すなわち、
Ａ＝Ｂ＝Ｃ＝Ｄ＝ａ
Ｅ＝Ｆ＝Ｇ＝Ｈ＝ｂ
Ｉ＝Ｊ＝Ｋ＝Ｌ＝ｃ
Ｍ＝Ｎ＝Ｏ＝Ｐ＝ｄ
のように水平方向に予測し、次いで予測残差を、
Ａ−ａ  Ｂ−ａ  Ｃ−ａ  Ｄ−ａ
Ｅ−ｂ  Ｆ−ｂ  Ｇ−ｂ  Ｈ−ｂ
Ｉ−ｃ  Ｊ−ｃ  Ｋ−ｃ  Ｌ−ｃ
Ｍ−ｄ  Ｎ−ｄ  Ｏ−ｄ  Ｐ−ｄ
のように計算し、その後に直交変換・量子化・エントロピ符号化を施して圧縮符号化することが行われている。【０００４】
動き補償予測においても同様に、４×４ブロックの動き補償では、Ａ...Ｐを別フレームにより予測した４×４ブロックＡ′...Ｐ′を
Ａ′  Ｂ′  Ｃ′  Ｄ′
Ｅ′  Ｆ′  Ｇ′  Ｈ′
Ｉ′  Ｊ′  Ｋ′  Ｌ′
Ｍ′  Ｎ′  Ｏ′  Ｐ′
のように作成し、次いで予測残差を、
Ａ−Ａ′  Ｂ−Ｂ′  Ｃ−Ｃ′  Ｄ−Ｄ′
Ｅ−Ｅ′  Ｆ−Ｆ′  Ｇ−Ｇ′  Ｈ−Ｈ′
Ｉ−Ｉ′  Ｊ−Ｊ′  Ｋ−Ｋ′  Ｌ−Ｌ′
Ｍ−Ｍ′  Ｎ−Ｎ′  Ｏ−Ｏ′  Ｐ−Ｐ′
と計算し、その後に直交変換・量子化・エントロピ符号化を施して圧縮符号化することが行われている。【０００５】
復号器は、復号済みの画素値から、例えばブロック左上の位置については、予測値Ａ′および予測残差の復号値（Ａ−Ａ′）を得て、それらの和として原画素値Ａを得る。これは可逆な場合であるが、非可逆の場合にも、復号器は予測残差復号値（Ａ−Ａ′＋Δ）（Δは符号化雑音）を得て、予測値Ａ′との和として（Ａ＋Δ）を得る。【０００６】
以上は画素値が４×４の１６個の場合であったが、以下、概念的に単純化し一次元で考える。また以下、一般的な８ｂｉｔ画素値の場合を考える。画素値は０から２５５までの２５６通りの整数値をとる。なお、８ｂｉｔ以外の画素値についても、以降の議論は同様に適用できる。【０００７】
符号化対象の画素値をｘとし、予測値をｘ′とする。ｘ′はｘの値に近いため、予測残差（ｘ−ｘ′）は−２５５...２５５の値を取り得るが、０に近い値に集中し、絶対値の大きな値は相対的に少ない。この関係をグラフにより図１に示す。【０００８】
偏りのある分布の情報量は、一様な分布の情報量より小さいため、符号化後圧縮が期待できる。従来は、この分布の偏りを利用し、高効率圧縮を実現していた。【０００９】
なお、非特許文献１には、本発明の実施例の説明で用いるベクトル符号化において、代表ベクトルが空間内に規則的に位置するピラミッドベクトル量子化の技術が記載されている。
また、非特許文献２には、ベクトル量子化において代表ベクトルを学習により最適化し、結果としてそれらを空間的に不規則に配置するＬＢＧアルゴリズムに基づくベクトル量子化の技術が記載されている。
【非特許文献１】T.R.Fischer,“A pyramid vector quantizer”, IEEE Trans. Inform. Theory, vol.IT-32, no.4, pp.568-583, July, 1986.
【非特許文献２】Y.Linde, A.Buzo and R.M.Gray,“An algorithm for vector quantizer design, ”IEEE Trans. on Communications, vol.com-28, no.1, pp.84-95, Jan., 1980
【発明の開示】
【発明が解決しようとする課題】
【００１０】
従来の方法において、例えば予測値がｘ′＝２５５であったとする。画素値ｘは、０...２５５の値であるので、予測残差はｘ−ｘ′＝−２５５...０と、０以下の値しか取り得ない。【００１１】
したがって、予測残差分布において、正方向のほぼ右半分の分布は使われることがない。分布の端（生起確率が極めて低い）を無視して定性的に述べれば、分布は左右対称であるので「右か左のどちらか」という情報に１ｂｉｔ（例えば０が右、１が左）を要する。右半分の分布が使われない（とり得る値の範囲からはみだす部分がある）場合、その１ｂｉｔは元来不要である。予測値がｘ′＝０の場合も、予測誤差分布の負方向のほぼ左半分は使われることがなく、同様に１ｂｉｔが元来不要となる。【００１２】
これらの関係を図２に示す。なお、以下の図において、画素値または予測誤差などの値が取り得る範囲を図中に斜線を付けて表す。【００１３】
定量的に述べれば、まず左右に広がっている確率分布をｐw （ｄ）とする。【００１４】
【数１】
2009057506.tif 000003
【００１５】
である。実際には右半分の値は取り得ないので、誤差ｄの正しい分布はｐw の二倍となる。【００１６】
ｐc （ｄ）＝２ｐw （ｄ）      （ｄ≦０のとき）
ｐc （ｄ）＝０                （ｄ＞０のとき）        （２）【００１７】
【数２】
2009057506.tif 000004
【００１８】
生起確率をｐw としたときの平均エントロピＨw を見積もると、次のようになる。【００１９】
【数３】
2009057506.tif 000005
【００２０】
正しい生起確率を用いた場合の平均エントロピは、以下のとおりである。【００２１】
【数４】
2009057506.tif 000006
【００２２】
しかしながら、従来は差分値（ｘ−ｘ′）のみを対象として符号化を行っていたので、この不要な１ｂｉｔの削減が不可能であった。【００２３】
この理由として、
・（ｘ−ｘ′）からは予測値（ｘ′）の情報が失われていること、
・（多次元の場合であるが）差分値（ｘ−ｘ′）に直交変換を施すため、変換後の空間におけるｘの取り得る範囲も同時に変換したものを考慮しなければならず、多次元分布における「（取り得る値の範囲からの）はみだし」の判定が極めて困難となること、
が挙げられる。【００２４】
以上のような問題に鑑み、本発明は、従来と同様の時間・空間的予測は行うが、原画素値と予測値との差分を求めずに、上述のような分布に関する「はみだし」を考慮した原画素値に対応した分布により原画素値を符号化することにより、予測符号化における符号化効率を改善することを目的とする。
【課題を解決するための手段】
【００２５】
本発明は、上記課題を解決するため、符号化対象の画素の値（画素ブロックに対応づけられる値の場合もある）を、復号済み画像から空間予測や時間予測（動き補償）により生成される予測値を用いて符号化する予測符号化において、画素値の取り得る上下限値を考慮した、画素値の該予測値における条件付き分布を用いて、符号化対象画素（または画素ブロック）の値を、符号化することを主要な特徴とする。【００２６】
画素値の取り得る上下限とは、デジタル画像における画素の取り得る値の上限と下限である。もっとも広範に用いられている８ｂｉｔ画像では、それぞれ２５５と０であり、１０ｂｉｔ画像では、１０２３と０となる。
この上限より大きな値（２０００など）や下限より小さい値（−１）などを取るような画素は、原画像に存在していないと仮定して問題ない。上下限値の考慮とはこのことを意味しており、本発明はこのような事実を用いて符号化を効率化している。【００２７】
画素値の該予測値における条件付き分布とは、予測値がｘ′であるような画素において、原画素値ｘが実際にはどのような値をとっているのかという確率分布である。
条件付きとは、ここでは予測値がｘ′であるということと等価である。
数学では、Ｐr （ｘ｜ｘ′）とも書かれる。通常、この形状はｘ′をピークとする釣鐘状となる。【００２８】
予測値がｘ′であるという条件の下でのｘの分布も、（当然ながら）そのような条件がない場合のｘの分布も、常に画素の上下限内の値（８ｂｉｔ画像では０から２５５の整数値）しか取らない。【００２９】
また、本発明は、上記発明において予測を画素ブロック単位で行う場合に、ブロック予測による画素ブロック値の条件付き分布の符号化にベクトル量子化を用いることが可能である。
【発明の効果】
【００３０】
本発明によれば、従来の、予測値と原画素値の差分を扱う場合の「予測値という重要な情報の欠落」を発生させることなく、余すことなく符号化に利用し、結果としてより少ない符号量で画像（静止画像もしくは映像）を符号化することができるようになる。
【図面の簡単な説明】
【００３１】
【図１】画素値差分の分布を示す図である。
【図２】予測値が２５５の場合の画素値差分の分布を示す図である。
【図３】単純なベクトル量子化の場合（差分あり）を示す図である。
【図４】単純なベクトル量子化の場合（差分なし）を示す図である。
【図５】Ｌ∞ノルム＝４に対応する代表ベクトルを示す図である。
【図６】Ｌ∞ノルム＝４に対応する代表ベクトル（異なる予測値の例）を示す図である。
【図７】ピラミッドベクトル量子化の場合（差分あり）を示す図である。
【図８】ピラミッドベクトル量子化の代表ベクトルの計数を示す図である。
【図９】ＬＢＧアルゴリズムによる差分ベクトル量子化の模式図である。
【図１０】特定の予測値（ｘ1 ′，ｘ2 ′）における差分ベクトル量子化の模式図である。
【図１１】特定の予測値（ｘ1 ′，ｘ2 ′）における、本発明による手法によるベクトル量子化の模式図である。
【図１２】本願発明の実施形態における符号化時の処理の流れを示す図である。
【図１３Ａ】原画素値の生起確率が一様である概念を示す図である。
【図１３Ｂ】原画素値と予測値の差分分布を示す概念図である。
【図１３Ｃ】差分分布を原画素値に対応するものにシフトさせた分布を示す概念図である。
【図１３Ｄ】原画素値のとり得る値にクリッピングした分布を示す概念図である。
【図１４】本実施形態における符号化装置のブロック図である。
【図１５】本実施形態における復号時の処理の流れを示す図である。
【図１６】代表ベクトルのはみだし個数が正確に求まらない例を示す図である。
【符号の説明】
【００３２】
３００  信号端子
３０１  画素値予測器
３０２  予測値蓄積メモリ
３０３  差分分布蓄積メモリ
３０４  加算・クリッピング器
３０５  代表ベクトル設計器
３０６  原画素値蓄積メモリ
３０７  ベクトル量子化器
３０８  量子化インデックス符号化器
３０９  出力端子
【発明を実施するための最良の形態】
【００３３】
まず、本発明の概要を具体例かつ簡単に説明する。【００３４】
例えば、信号ｄが｛−２，−１，１，２｝の４通りのいずれをとるかわからない場合（２５％で等確率を仮定）、この信号を符号化するには２［ｂｉｔ］が必要である。これを確率分布で表したのが図１（二次元の例は図９）である。【００３５】
もし「信号ｄが正である」とわかっているとすると、｛１，２｝の二通りしか可能性がないので１［ｂｉｔ］で符号化ができてしまう。これを確率分布で表したのが図２（二次元の例は図１１）である。【００３６】
同じことが、静止画像もしくは映像の予測符号化でも起きる。
画像信号ｘ（０≦ｘ）の予測値がｘ′であったとすると、予測誤差ｄ＝ｘ−ｘ′の分布は予測値ｘ′により変化する。
例えば、もしｘ′＝０であれば、０≦ｄ0 つまりｄは負の値をとらない。一方、ｘ′＝２５５であれば、ｄ0 ≦０つまりｄは正の値をとらない（概念は同じく図２を参照）。【００３７】
このように、予測値ｘ′の値を手がかりに、符号化・復号の前にｄの存在範囲を絞り込んでおくことができる。これはとりもなおさず符号化効率の改善につながる。
ｄの存在範囲を絞り込む処理は、ｘ′＋ｄの範囲を（８ｂｉｔ画像の場合）０...２５５に規格化することと等価である。
これは符号化方法では、図１２のフローチャートのクリッピングステップ１０５に、復号方法では、図１５のフローチャートのクリッピングステップ４０５に相当する。【００３８】
さらに、予測単位のブロック毎に代表ベクトルを設計することで、適応的に最適な代表ベクトルを設計できる（符号化方法では図１２のフローチャートの代表ベクトル設計ステップ１０６に、復号方法では図１５のフローチャートの代表ベクトル設計ステップ４０６に相当する）。【００３９】
こうして符号化対象信号を狭めた後、通常の符号化を経て従来よりも短い（符号化効率の高い）符号が出力される（図１２のフローチャートの量子化インデックス符号化ステップ１０９）。【００４０】
画素値の予測は、既存の符号化技術ＭＰＥＧ−１、ＭＰＥＧ−２、ＭＰＥＧ−４、Ｈ．２６４／ＡＶＣにおいて「動き補償」あるいは「イントラ予測」として用いられており（符号化方法では図１２のフローチャートのステップ１０１、復号方法では図１５のフローチャートのステップ４０１）、本発明はこのような予測が用いられる場面に広範に適用でき、符号化効率の改善に寄与するものである。【００４１】
なお、既存の予測符号化技術においては、予測誤差は常に正負いずれも取り得るものとして符号化している（概念図は図９）。【００４２】
次に、本発明の実施形態における原理的な仕組みについて詳細に説明する。
予測を画素ブロック単位で行い、ブロック予測による画素ブロック値の条件付き分布の符号化にベクトル量子化を用いる例を説明するが、予測値がｘ′であるような画素において、原画素値ｘが実際にはどのような値をとっているのかという確率分布を用いて符号化を行うという基本的な考え方は、画素単位で符号化する場合も同様である。【００４３】
［距離尺度がＬ∞ノルムの場合］
図３を用い、二次元での量子化・符号化を例にとり説明する。これは二次元の最も単純な格子量子化の模式図である。原点からの距離尺度は、Ｌ∞ノルム（座標絶対値の最大値）に基づき計算される。
例えば点（０，３）と点（−２，−３）は、同一のＬ∞ノルムを持つ。
図中、点線でつながれた点（ベクトル量子化後、離散データが属する代表ベクトルである）同士が同一のＬ∞ノルムを持ち、同一ノルムの点同士は同確率で生起することを仮定する。【００４４】
この図では、隣り合う二画素の原画素値がそれぞれｘ1 ＝２５３、ｘ2 ＝１０２であり、予測値がｘ1 ′＝２５５、ｘ2 ′＝１００であったとしている。差分値はｘ1 −ｘ1 ′＝−２、ｘ2 −ｘ2 ′＝２となる。【００４５】
原画素値に対応する差分ベクトル（−２，２）が属するＬ∞ノルム＝２の生起確率が、０．３であったとする。
Ｌ∞ノルムが２となる代表ベクトルは全部で１６個あるので、原画素値を符号化するのに必要な情報量は、
−ｌｏｇ2 ０．３＋ｌｏｇ2 １６＝５．７３７［ｂｉｔ］        （９）
となる。【００４６】
次に、本発明により、予測誤差を計算しない場合の符号量を見積もる。概念図を図４に示す。
図中に斜線を付けた部分に属する白丸で示される代表ベクトル（○）は、原画素値の可能性があり、斜線の外側に属する黒丸で示される代表ベクトル（●）は、原画素値の可能性がない。
中心は予測値（ｘ1 ′，ｘ2 ′）＝（２５５，１００）であり、先と同様に、中心からのＬ∞ノルムが２となる確率は、０．３であるとする。
これに属する代表ベクトルは９個であるので、原画素値を符号化するのに必要な情報量は、
−ｌｏｇ2 ０．３＋ｌｏｇ2 ９＝４．９０７［ｂｉｔ］        （１０）
と、差分を計算した場合（第９式）よりも０．８３ｂｉｔ低い値で収まっている。【００４７】
［ノルム一定面上の代表ベクトル点数］
図５に、二次元、Ｌ∞ノルム＝４に対応する代表ベクトルを示す。
次元をＬ、ノルムをＫとすると、代表ベクトルの個数Ｎ（Ｌ，Ｋ）は次式で与えられる：
Ｎ（Ｌ，Ｋ）＝（２Ｋ＋１）L −（２Ｋ−１）L         （１１）
図５に示す例では、
Ｎ（２，４）＝９2 −７2 ＝８１−４９＝３２
となる。【００４８】
符号化において、ノルムが特定された後に、さらに代表ベクトルを特定するために、以下の情報量が必要となる。【００４９】
ｌｏｇ2 Ｎ（Ｌ，Ｋ）［ｂｉｔ］        （１２）
さらに、図５では、黒丸（●）で示される「はみだし部分」（原画素値の可能性がない部分）が存在する。この個数を差し引いた白丸（○）の個数を求めるには、（ｘ1 、ｘ2 、... 、ｘL ）の各次元において、上限を（ pＫ1 、 pＫ2 、... 、 pＫL ）、下限を（− nＫ1 、− nＫ2 、... 、− nＫL ）とすると、
０≦ nＫi 、 pＫi ≦Ｋ（ｉ＝１... Ｌ）
である。はみだしがない場合、Ｋi （上限、下限）≡Ｋである。【００５０】
○の個数をＮ′（Ｌ， Ｋ， nＫ1 ，... ， nＫL ， pＫ1 ，... ， pＫL ）
とすると、【００５１】
【数５】
2009057506.tif 000007
【００５２】
として求められる。ただし、
ｆ（Ｋ，Ｋ′）＝Ｋ′−１      （Ｋ′＝Ｋのとき）
ｆ（Ｋ，Ｋ′）＝Ｋ′          （Ｋ′＜Ｋのとき）        （１４）
となる。
図５の例では、Ｌ＝２、Ｋ＝４、 nＫ1 ＝４、 nＫ2 ＝４、 pＫ1 ＝２、 pＫ2 ＝４なので、
Ｎ′（２，４，４，４，２，４）
＝（４＋２＋１）（４＋４＋１）−（４−１＋２＋１）（４−１＋４−１＋１）
＝６３−４２＝２１
となる。【００５３】
本発明の手法によるエントロピ削減の度合いを見積もると、
ｌｏｇ2 ３２−ｌｏｇ2 ２１＝０．６０８［ｂｉｔ］
となる。【００５４】
次に、異なる予測値の例として、図６の場合を考える。
Ｌ＝２、Ｋ＝４、 nＫ1 ＝４、 nＫ2 ＝３、 pＫ1 ＝２、 pＫ2 ＝３なので、
Ｎ′（２，４，４，３，２，３）
＝（２＋４＋１）（３＋３＋１）−（２＋４−１＋１）（３＋３＋１）
＝４９−４２＝７
となり、はみだし部分が大幅に削除されている。【００５５】
［距離尺度がＬ1 ノルムの場合］
次に、原点からの距離がＬ1 ノルムに従う、いわゆるピラミッドベクトル量子化の場合を、図７を用いて説明する。先と同様に、点線は等確率面、斜線部は画素値が取り得る範囲（０...２５５）を示している。
大きな円で示された（ｘ1 ，ｘ2 ）が原画素であり、このノルム（図では４）に属する代表ベクトルは、範囲外も含めると１６個、範囲内は１０個である。
この場合、原画素値と予測値との差分をとらないとき（本発明）のエントロピは、とったとき（従来法）に比べ、
ｌｏｇ2 １６−ｌｏｇ2 １０＝０、６７８［ｂｉｔ］        （１５）
低くなる。【００５６】
［ノルム一定面上の代表ベクトル点数］
図７のＬ1 ノルム＝４の部分を抜き出したものが図８である。【００５７】
Ｌ次元のピラミッドベクトル量子化の、Ｌ1 ノルム＝Ｋである代表ベクトルの点の個数を、先と同様にＮ（Ｌ，Ｋ）とする。これは次のように漸化的に求められる（非特許文献１参照）。【００５８】
・Ｋ＝１のとき
Ｎ（Ｌ，Ｋ）＝２Ｌ
・Ｌ＝１のとき
Ｎ（Ｌ，Ｋ）＝２
・それ以外
Ｎ（Ｌ，Ｋ）＝Ｎ（Ｌ，Ｋ−１）＋Ｎ（Ｌ−１，Ｋ−１）＋Ｎ（Ｌ−１，Ｋ）
…（１６）
従って、
Ｎ（２，４）＝Ｎ（２，３）＋Ｎ（１，３）＋Ｎ（１，４）
＝Ｎ（２，２）＋Ｎ（１，２）＋Ｎ（１，３）＋２＋２
＝Ｎ（２，２）＋２＋２＋４
＝Ｎ（２，１）＋Ｎ（１，１）＋Ｎ（１，２）＋８
＝４＋２＋２＋８
＝１６
となる。
次に、「はみだし部分」の個数を考える。例えばpＫ1＝１により５個、pＫ２＝３により１個の「はみだし」代表ベクトル（●）が生じている。【００５９】
まず、簡単のため、pＫ1のみがpＫ1＜Ｋであり、残りは
ｎＫ1，Ｋi ＝Ｋ（ｉ＝２，... ，Ｌ）
である場合を考える。【００６０】
そのような場合のはみ出し代表ベクトル（●）の個数Ｍ（Ｌ，Ｋ）は、第１６式のＮを用いて、
Ｋ＝０のとき：Ｍ（Ｌ，Ｋ）＝１
Ｌ＝１のとき：Ｍ（Ｌ，Ｋ）＝１
それ以外    ：Ｍ（Ｌ，Ｋ）＝（Ｎ（Ｌ，Ｋ）＋Ｎ（Ｌ−１，Ｋ））／２
…（１７）
において、
Ｍ（Ｌ，Ｋ−pＫ1 −１）
から求められる。【００６１】
図８のようなＬ＝２、Ｋ＝４、pＫ1＝１の場合、
Ｍ（２，４−１−１）＝Ｍ（２，２）
＝（Ｎ（２，２）＋Ｎ（１，２））／２
＝（８＋２）／２＝５
となる。【００６２】
同様の手法は他の次元にも適用でき、例えばpＫ2 ＝３の場合、
Ｍ（２，４−３−１）＝Ｍ（２，０）＝１
のように求められる。【００６３】
こうして、代表ベクトル総数Ｎとはみ出し個数Ｍから、○の個数がＮ−Ｍとして求められる。【００６４】
なお、上記のようにはみ出し量が正確に求まるには、以下の条件を満たしている必要がある：
・ｉ番の座標軸に垂直なｘi ＝Ｋi 面の、全端点のＬ1 ノルムが常にＫ以上であること、
・すなわち、｜Ｋj ｜、｜２５５−Ｋj ｜（ｊ≠ｉ）のうち、最小値を与える座標軸ｊを残し、それ以外の座標値が全て０であるような点のＬ1 ノルム（これが全端点の中で最小のＬ1 ノルムを与える）がＫ以上であること、
・すなわち、【００６５】
【数６】
2009057506.tif 000008
【００６６】
具体例として、図８における斜線を施した四角部分の４つの角が「全端点」となり、この場合は全ての短点がＬ1 ノルム＝４のライン上もしくはその外側にあり、はみ出し量が正確に求まる。
仮に、この斜線部分が図１６のように設定されていると、Ｌ1 ノルム＝４のラインの内側に存在する端点があり（（ｘ1 ，ｘ2 ）＝（１，１）に存在する端点）、重複カウントされる「はみだし」代表ベクトルが存在してしまう（（ｘ1 ，ｘ2 ）＝（２，２）に存在する代表ベクトル）。
この場合、はみ出し量が正確に求まらない。【００６７】
［一般のベクトル量子化の場合］
よく知られたＬＢＧアルゴリズム（非特許文献２）などによる、代表ベクトルの配置が規則的でない、一般のベクトル量子化においては、本発明は次のように適用される。【００６８】
図９が、通常の差分信号（二次元）に対するベクトル量子化の模式図である。差分信号は、各次元−２５５...２５５の値をとるため、代表ベクトルの設計においてもこの範囲を網羅するようになされる。画像予測差分信号のように原点（０，０）付近に信号が生起する確率が高い場合、この図のように代表ベクトルも原点付近において密になり、周辺において疎となる。【００６９】
図１０は、従来の符号化方法に対応するもので、予測値（ｘ1 ′，ｘ2 ′）における原信号の符号化を行っている。原信号は０..２５５の値しか取り得ないため、代表ベクトルはその外にも存在してしまう。したがって、一次元の符号化議論のときと同様に、符号量の無駄が発生する。【００７０】
図１１は、本発明の符号化方法に対応するもので、予測値（ｘ1 ′，ｘ2 ′）に応じて代表ベクトルを設計する。
当然ながら各次元０...２５５の範囲内で設計するため（即ち、０≦ｘ1 ，ｘ2 ≦２５５）、従来方法（図１０）で生じていたような代表ベクトルの「はみだし」は起きず、符号量の無駄のない符号化が行える。【００７１】
以下では、本発明の実施形態の一例として、予測を画素ブロック単位で行い、ブロック予測による画素ブロック値の条件付き分布の符号化にベクトル量子化を用いる場合の例を説明する。
本実施形態では、事前の学習用データをもとに、ベクトル量子化の代表ベクトルを作成する。
符号化対象ブロックの予測値ｘ′に対応した学習データのみを用いてもよいが、次元が高い場合にはデータ数が少なくなるので、例えば原画素値との差分値（ｘ−ｘ′）を記憶しておき、学習には差分値に予測値を加えた値を用いる、という構成も可能である。【００７２】
図１２に、本実施形態のフローチャートを示す。実線矢印は処理の流れ、波線矢印はデータの流れを示す。【００７３】
画素値予測ステップ１０１において、ブロック単位に動き補償あるいは画面内予測などにより、符号化対象ブロックの画素値予測を行い、予測値１０２（ベクトル量）を得る。
シフトステップ１０４において、別途蓄積しておいた差分分布データ１０３（ベクトル量）における差分値に予測値を加算（シフト）し、次いでクリッピングステップ１０５において、ベクトルの各要素を０...２５５にクリッピングする。これが学習の元データとなる。【００７４】
代表ベクトル設計ステップ１０６において、例えばＬＢＧアルゴリズムにより、学習の元データを用いて代表ベクトルを設計する（例えば図１１のような結果を得る）。【００７５】
次に、符号化対象ブロックの原画素値１０８（ベクトル量）を、ベクトル量子化ステップ１０７により、原画素値最近傍の代表ベクトルへ対応づける。【００７６】
得られた代表ベクトルのインデックス情報を、その生起確率に基づき、量子化インデックス符号化ステップ１０９において、算術符号などのエントロピ符号化により符号化し、符号を出力し、終了する。【００７７】
図１３Ａ〜１３Ｄを用いて、図１２に示す符号化の処理による作用を簡単な例で説明する。わかりやすく図示するため、図１３Ａ〜１３Ｄでは一次元の画素値で示す。原画素値ｘは０から２５５までの値を取るものとする。
もし、これらの値の生起確率が一様であるとすると、図１３Ａに示すように、各値は１／２５６の確率で生じることになる。このような等確率分布で生じる値の符号化コストは大きい。
しかし、もしこの原画素値ｘの予測値ｘ′が得られた場合、原画素値ｘの取り得る確率分布を、既知の予測誤差値の分布から等確率分布ではないものとすることができる。本方式は、この点に着目して符号化効率を改善するものである。【００７８】
原画素値ｘと予測値ｘ′の差分である予測誤差ｘ−ｘ′の値（差分値）は、−２５５から２５５までの値を取り得るが、この差分分布は、多くのサンプル画像の予測符号化実験などにより求めることができる。この差分分布のデータを予め蓄積し、保持しておく。
差分分布は各予測誤差の値の頻度値もしくは確率値の分布であり、例えば図１３Ｂのような分布となっている。図１２の差分分布データ１０３が、図１３Ｂのような分布を示すデータ（ただしベクトル量）である。【００７９】
原画素値ｘを符号化するときに、画素値予測ステップ１０１では、まず予測値ｘ′を求める。
シフトステップ１０４では、差分分布データ１０３の各差分値、すなわち図１３Ｂに示す差分分布における横軸の各予測誤差ｘ−ｘ′の値に予測値ｘ′を加算（シフト）し、この差分分布を、図１３Ｃに示すように原画素値ｘに対応するものにシフトさせる。
これが、予測値ｘ′が既知の場合の原画素値ｘの取り得る確率分布に相当するものになる。【００８０】
図１３Ｃの分布では、原画素値ｘが−２５５＋ｘ′から２５５＋ｘ′の範囲まで分布するものになっている。しかし、原画素値ｘは、ここでは０から２５５までの値しか取らないという前提であるので、続くクリッピングステップ１０５では、図１３Ｄに示すように、原画素値ｘの分布における０未満と２５５の値を超える部分を切り捨て、これにより得られた分布を必要に応じて正規化し、確率分布とする。
この図１３Ｄに示す分布に基づいて原画素値ｘを符号化すれば、図１３Ａに示すような等確率分布の下で符号化するよりも高い符号化効率が得られることはもちろん、図１３Ｂに示すような裾の広い確率分布の下で符号化する（従来法に対応）よりも効率は高くなる。【００８１】
このような確率分布の下で効率よく符号化する一例としてはベクトル量子化があり、さらに本実施形態では、図１３Ｄに示すような確率分布に基づいて、図１２に示すステップ１０６〜１０９により、量子化代表ベクトルの配置を決め、ベクトル量子化を行っている。【００８２】
図１４に、本実施形態の符号化装置のブロック図を示す。【００８３】
信号端子３００より、映像原信号および復号済み映像信号が入力される。
符号化対象ブロックの原画素値は、原画素値蓄積メモリ３０６に蓄積される。
画素値予測器３０１において、ブロック単位に動き補償あるいは画面内予測などにより、符号化対象ブロックの画素値予測を行い、予測値（ベクトル量）を得、予測値蓄積メモリ３０２に記憶する。
加算・クリッピング器３０４において、差分分布蓄積メモリ３０３に別途蓄積しておいた差分分布データベクトルと予測値を加算し、ベクトルの各要素を０...２５５にクリッピングする。これが学習の元データとなる。【００８４】
代表ベクトル設計器３０５において、例えばＬＢＧアルゴリズムにより、学習の元データを用いて代表ベクトルを設計する。【００８５】
次に、メモリ３０６に蓄えられた符号化対象ブロックの原画素値（ベクトル量）を、ベクトル量子化器３０７により、原画素値最近傍の代表ベクトルへ対応づける。【００８６】
得られた代表ベクトルのインデックス情報を、その生起確率に基づき、量子化インデックス符号化器３０８において、算術符号などのエントロピ符号化により符号化し、符号を出力端子３０９へ出力し、終了する。【００８７】
図１５に、本実施形態における復号時のフローチャートを示す。実線矢印は処理の流れ、波線矢印はデータの流れを示す。【００８８】
画素値予測ステップ４０１において、ブロック単位に動き補償あるいは画面内予測などにより、符号化対象ブロックの画素値予測を行い、予測値４０２（ベクトル量）を得る。
加算ステップ４０４において、別途蓄積しておいた差分分布データベクトルと予測値を加算し、次いでクリッピングステップ４０５においてベクトルの各要素を０...２５５にクリッピングする。これが学習の元データとなる。【００８９】
代表ベクトル設計ステップ４０６において、例えばＬＢＧアルゴリズムにより、学習の元データを用いて代表ベクトルを設計する。【００９０】
得られた代表ベクトルのインデックス情報の生起確率に基づき、量子化インデックス復号ステップ４０７において、インデックスを復号する。【００９１】
次に、ベクトル逆量子化ステップ４０８において、インデックスに対応する代表ベクトル値を求めてこれを出力し終了する。【００９２】
なお、本実施形態の復号装置のブロック構成については、図１４に示す符号化装置のブロック図の説明と、図１５に示す復号時のフローチャートの説明から容易に類推できるので、図面を用いた説明は省略する。
復号装置の構成も、基本的には図１４に示す符号化装置のブロック図と同様であり、図１４における原画素値蓄積メモリ３０６が、復号装置では量子化インデックス符号化データ蓄積メモリになり、ベクトル量子化器３０７が、復号装置では量子化インデックス復号器になり、量子化インデックス符号化器３０８が、復号装置ではベクトル逆量子化器になる。【００９３】
以上の画像・映像符号化および復号の処理は、コンピュータとソフトウェアプログラムとによっても実現することができ、そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも、ネットワークを通して提供することも可能である。
【産業上の利用可能性】
【００９４】
本発明によれば、従来の、予測値と原画素値の差分を扱う場合の「予測値という重要な情報の欠落」を発生させることなく、余すことなく符号化に利用し、結果としてより少ない符号量で画像（静止画像もしくは映像）を符号化することができるようになる。
【図１】
2009057506.tif 000009
【図２】
2009057506.tif 000010
【図３】
2009057506.tif 000011
【図４】
2009057506.tif 000012
【図５】
2009057506.tif 000013
【図６】
2009057506.tif 000014
【図７】
2009057506.tif 000015
【図８】
2009057506.tif 000016
【図９】
2009057506.tif 000017
【図１０】
2009057506.tif 000018
【図１１】
2009057506.tif 000019
【図１２】
2009057506.tif 000020
【図１３Ａ】
2009057506.tif 000021
【図１３Ｂ】
2009057506.tif 000022
【図１３Ｃ】
2009057506.tif 000023
【図１３Ｄ】
2009057506.tif 000024
【図１４】
2009057506.tif 000025
【図１５】
2009057506.tif 000026
【図１６】
2009057506.tif 000027
【国際調査報告】
2009057506.tif 000028
2009057506.tif 000029