(57)【特許請求の範囲】
【請求項１】
複数の画素から構成される単位ブロックの各画素に対して、直交変換、量子化および符号化を順次行って単位ブロック毎に符号化を行う画像符号化装置において、
符号化済画素の情報を受け取り、符号化対象ブロックに対する変換基底関数を構成し、直交変換手段に送出する基底関数構成手段を具備し、
該基底関数構成手段は前記符号化済画素の領域から前記符号化対象ブロックの類似領域を、前記符号化対象ブロックの画素を用いずに符号化済み画素のみを用いることで探索して、該探索された類似領域を入力として用いて、且つ、前記符号化対象ブロックの画素を入力として用いずに、前記変換基底関数を構成することにより、前記探索された類似領域の情報の符号化を省略させることを特徴とする画像符号化装置。
【請求項２】
複数の画素から構成される単位ブロックの各画素に対して、符号化済画素から予測される各画素との間で差分処理を行って得られた予測残差について直交変換、量子化および符号化を順次行って単位ブロック毎に符号化を行う画像符号化装置において、
前記符号化済画素の情報と、前記各画素を予測する予測情報と、を受け取り、符号化対象ブロックに対する変換基底関数を構成し、直交変換手段に送出する基底関数構成手段を具備し、
該基底関数構成手段は前記符号化済画素の領域から前記符号化対象ブロックの類似領域を探索して、該類似領域に対して前記予測情報を適用して得られる予測残差を入力として用いて前記変換基底関数を構成し、
前記基底関数構成手段は、前記符号化済画素の領域から前記符号化対象ブロックの類似領域を探索するに際して、前記符号化対象ブロックの同一フレーム内の近傍に位置し且つ前記符号化済画素に含まれる画素からなる所定領域を探索用近傍領域とし、該探索用近傍領域の類似領域を前記符号化済画素の領域から探索して近傍領域類似領域とし、前記探索用近傍領域を前記近傍領域類似領域に平行移動するのに等しい平行移動を前記符号化対象ブロックに施すことで移される領域を前記符号化対象ブロックに対して探索された類似領域とすることを特徴とする画像符号化装置。
【請求項３】
前記基底関数構成手段は、前記符号化済画素の領域から前記符号化対象ブロックの類似領域を探索するに際して、前記符号化済画素の領域に含まれる前記符号化された単位ブロック毎に探索することを特徴とする請求項１または２に記載の画像符号化装置。
【請求項４】
前記基底関数構成手段は、前記符号化済画素の領域から前記符号化対象ブロックの類似領域を探索するに際して、前記符号化対象ブロックの同一フレーム内の近傍に位置し且つ前記符号化済画素に含まれる画素からなる所定領域を探索用近傍領域とし、該探索用近傍領域の類似領域を前記符号化済画素の領域から探索して近傍領域類似領域とし、前記探索用近傍領域を前記近傍領域類似領域に平行移動するのに等しい平行移動を前記符号化対象ブロックに施すことで移される領域を前記符号化対象ブロックに対して探索された類似領域とすることを特徴とする請求項１または２に記載の画像符号化装置。
【請求項５】
前記探索用近傍領域が、前記符号化対象ブロックに接する隣接領域のみからなることを特徴とする請求項４に記載の画像符号化装置。
【請求項６】
前記基底関数構成手段は、前記符号化済画素の領域から前記符号化対象ブロックの類似領域を探索するに際して、前記符号化対象ブロックの同一フレーム内の近傍に位置し且つ前記符号化済画素に含まれる画素からなる所定領域を探索用近傍領域とし、該探索用近傍領域の類似領域を前記符号化済画素の領域から探索して近傍領域類似領域とし、前記探索用近傍領域を前記近傍領域類似領域に平行移動するのに等しい平行移動を前記符号化対象ブロックに施すことで移される領域を前記符号化対象ブロックに対して探索された類似領域とし、
前記探索用近傍領域が、前記予測情報に含まれる画面内予測の参照画素からなることを特徴とする請求項２に記載の画像符号化装置。
【請求項７】
前記符号化対象ブロックに対して探索される類似領域が、前記予測情報に含まれる画面内予測の種類が一致する領域とブロック単位で一致するよう、前記近傍領域類似領域を探索する範囲を限定することを特徴とする請求項６に記載の画像符号化装置。
【請求項８】
前記基底関数構成手段は、前記近傍領域類似領域を探索するに際して、画素に含まれる第１の色空間座標に対して前記探索された前記近傍領域類似領域を、画素に含まれる第２の色空間座標及び第３の色空間座標の少なくとも一方における前記近傍領域類似領域として採用することを特徴とする請求項４ないし７のいずれかに記載の画像符号化装置。
【請求項９】
前記基底関数構成手段は、前記近傍領域類似領域を探索するに際して、領域画素間の差分二乗和に基づいて探索することを特徴とする請求項４ないし７のいずれかに記載の画像符号化装置。
【請求項１０】
前記基底関数構成手段は、前記近傍領域類似領域を探索するに際して、探索元領域および該探索元領域を移動させて一致させる探索先領域の各領域において各領域の画素の平均値を減算してから算出する領域画素間の差分二乗和、または領域画素間の相関値に基づいて探索することを特徴とする請求項４ないし７のいずれかに記載の画像符号化装置。
【請求項１１】
前記基底関数構成手段は、前記入力を特異値分解して直交行列を算出し、該直交行列に基づいて前記変換基底関数を構成することを特徴とする請求項１ないし１０のいずれかに記載の画像符号化装置。
【請求項１２】
複数の画素から構成される単位ブロックの各画素が符号化された符号情報に対して、復号、逆量子化及び逆直交変換を順次行って単位ブロック毎に復号を行う画像復号装置において、
復号済画素の情報を受け取り、復号対象ブロックに対する逆変換基底関数を構成し、逆直交変換手段に送出する基底関数構成手段を具備し、
該基底関数構成手段は前記復号済画素の領域から前記復号対象ブロックの類似領域を、前記復号対象ブロックより復号される情報を用いずに復号済画素のみを用いることで探索して、該探索された類似領域を入力として用いて、且つ、前記復号対象ブロックより復号される情報を入力として用いずに、前記逆変換基底関数を構成することを特徴とする画像復号装置。
【請求項１３】
複数の画素から構成される単位ブロックの各画素が符号化された符号情報に対して、符号化済画素から予測される各画素との間で差分処理を行って得られた予測残差の符号情報について復号、逆量子化および逆直交変換を順次行って単位ブロック毎に復号を行う画像復号装置において、
復号済画素の情報と、前記各画素を予測する予測情報と、を受け取り、復号対象ブロックに対する逆変換基底関数を構成し、逆直交変換手段に送出する基底関数構成手段を具備し、
該基底関数構成手段は前記復号済画素の領域から前記復号対象ブロックの類似領域を探索して、該類似領域に対して前記予測情報を適用して得られる予測残差を入力として用いて前記逆変換基底関数を構成し、
前記基底関数構成手段は、前記復号済画素の領域から前記復号対象ブロックの類似領域を探索するに際して、前記復号対象ブロックの同一フレーム内の近傍に位置し且つ前記復号済画素に含まれる画素からなる所定領域を探索用近傍領域とし、該探索用近傍領域の類似領域を前記復号済画素の領域から探索して近傍領域類似領域とし、前記探索用近傍領域を前記近傍領域類似領域に平行移動するのに等しい平行移動を前記復号対象ブロックに施すことで移される領域を前記復号対象ブロックに対して探索された類似領域とすることを特徴とする画像復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像符号化装置及び画像復号装置に関し、特に、直交変換の基底関数を適応的に変化させることで、符号化効率を向上させる画像符号化装置及び画像復号装置に関するものである。
【背景技術】
【０００２】
従来の画像符号化において、ブロック単位で処理される画素は、局所的な相互相関が高いことを利用して、周波数変換が適用されてきた。周波数変換そのものには圧縮の機能はないが、変換によって画素情報が低周波係数に集中しやすいこと、及び人の視覚特性が高周波係数の誤差に比較的敏感ではないことを利用して、量子化で高周波係数の情報を排除しやすくした上で、効率的に符号化される。このとき、周波数変換の性能が画質に影響するため、低周波係数への集中度合いに優れた様々な変換基底関数が検討されてきた。また一方で、変換に要する計算量の観点からも、簡便な変換基底関数が検討されてきた。
【０００３】
以下の非特許文献１で示される画像符号化方式では、直交変換にDCTが利用されている。また、以下の非特許文献２で示されるＨ．２６４では、計算量削減及び浮動小数点のミスマッチの回避を目的として、DCTを整数で近似した基底関数を採用している。また、複数のブロック単位に対応するため、変換基底関数の次数も複数用意している。
【０００４】
また以下の非特許文献３では、Ｈ．２６４のIntra予測モードに応じて、異なる変換基底関数を用意している。あるブロックでIntra予測モードが選択されると、該モードと一対一対応した変換基底関数によってIntra予測残差が周波数領域に変換される。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】上符他，「最新ＭＰＥＧ教科書ポイント図解式」，アスキー，１９９４年
【非特許文献２】角野他，「Ｈ．２６４／ＡＶＣ教科書インプレス標準教科書シリーズ」，インプレスネットビジネスカンパニー，２００４年
【非特許文献３】M. Budagavi, et al. , " Orthogonal MDDT and Mode Dependent DCT," ITU-TSG16 Q.6 VCEG, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１及び非特許文献２は、ある符号化対象ブロックに対して一通りの変換基底関数しか用意していないため、様々な画素分布を取り得るブロックに対して変換基底関数が最適であるとは限らないという問題がある。また、複数の予測モードによって誤差の分布が変化する場合に対応できないという問題がある。例えば、Ｈ．２６４のIntra予測は符号化済みの近接する画素を基準として対象ブロックの予測値を生成するので、予測の基準となる画素から離れるほど大きな予測誤差が生じるという問題が指摘されている。Intra予測は9種類の予測方法で構成されているので、大きな予測誤差の発生しやすい場所は予測方法毎に異なる。よって、非特許文献１及び非特許文献２では、符号化効率を十分に高めることができないという問題がある。
【０００７】
一方、非特許文献３は、それぞれ複数の異なる変換基底関数をIntra予測モードに応じて変化させるため、非特許文献１及び非特許文献２の問題を一部解決できる。しかし、いずれもIntra予測モードに対して、固有の変換基底関数を割り当てているため、固定的であることに変わりはない。ブロック単位の画素若しくは予測残差が取り得る組み合わせは多岐に渡るため、該モードに割り当てられた変換基底関数が最適であるとは限らないという問題は依然として残る。
【０００８】
本発明の目的は前述した従来技術の問題点を解消し、変換基底関数を改善して符号化効率の高い画像符号化装置を提供することにある。
【課題を解決するための手段】
【０００９】
上記した従来技術の課題を解決するために、本発明は、複数の画素から構成される単位ブロックの各画素に対して、直交変換、量子化および符号化を順次行って単位ブロック毎に符号化を行う画像符号化装置において、符号化済画素の情報を受け取り、符号化対象ブロックに対する変換基底関数を構成し、直交変換手段に送出する基底関数構成手段を具備し、該基底関数構成手段は前記符号化済画素の領域から前記符号化対象ブロックの類似領域を探索して、該類似領域を入力として用いて前記変換基底関数を構成することを第１の特徴とする
【００１０】
また本発明は、複数の画素から構成される単位ブロックの各画素に対して、符号化済画素から予測される各画素との間で差分処理を行って得られた予測残差について直交変換、量子化および符号化を順次行って単位ブロック毎に符号化を行う画像符号化装置において、前記符号化済画素の情報と、前記各画素を予測する予測情報と、を受け取り、符号化対象ブロックに対する変換基底関数を構成し、直交変換手段に送出する基底関数構成手段を具備し、該基底関数構成手段は前記符号化済画素の領域から前記符号化対象ブロックの類似領域を探索して、該類似領域に対して前記予測情報を適用して得られる予測残差を入力として用いて前記変換基底関数を構成することを第２の特徴とする。
【００１１】
前記基底関数構成手段は、前記符号化済画素の領域から前記符号化対象ブロックの類似領域を探索するに際して、前記符号化済画素の領域に含まれる前記符号化された単位ブロック毎に探索することを第３の特徴とする。
【００１２】
前記画像符号化装置は、画素に含まれる第１の色空間座標に対して前記符号化対象ブロックを符号化して符号化済第１色ブロックとし、前記基底関数構成手段は、前記符号化済画素の領域から画素に含まれる第２の色空間座標及び第３の色空間座標の少なくとも一方に対して当該符号化対象ブロックの類似領域を探索するに際して、前記符号化済第１色ブロックの前記第１の色空間座標における領域を当該探索結果として採用することを第４の特徴とする
【００１３】
また、前記基底関数構成手段は、前記符号化済画素の領域から前記符号化対象ブロックの類似領域を探索するに際して、前記予測情報に含まれるフレーム間動き情報を用いて、前記符号化対象ブロックに対する前記フレーム間動き情報の参照先を前記探索された類似領域とすることを第５の特徴とする。
【００１４】
また、前記基底関数構成手段は、前記符号化済画素の領域から前記符号化対象ブロックの類似領域を探索するに際して、前記符号化対象ブロックの同一フレーム内の近傍に位置し且つ前記符号化済画素に含まれる画素からなる所定領域を探索用近傍領域とし、該探索用近傍領域の類似領域を前記符号化済画素の領域から探索して近傍領域類似領域とし、前記探索用近傍領域を前記近傍領域類似領域に平行移動するのに等しい平行移動を前記符号化対象ブロックに施すことで移される領域を前記符号化対象ブロックに対して探索された類似領域とすることを第６の特徴とする。
【００１５】
また、前記探索用近傍領域が、前記符号化対象ブロックに接する隣接領域のみからなることを第７の特徴とする。
【００１６】
また、前記基底関数構成手段は、前記符号化済画素の領域から前記符号化対象ブロックの類似領域を探索するに際して、前記符号化対象ブロックの同一フレーム内の近傍に位置し且つ前記符号化済画素に含まれる画素からなる所定領域を探索用近傍領域とし、該探索用近傍領域の類似領域を前記符号化済画素の領域から探索して近傍領域類似領域とし、前記探索用近傍領域を前記近傍領域類似領域に平行移動するのに等しい平行移動を前記符号化対象ブロックに施すことで移される領域を前記符号化対象ブロックに対して探索された類似領域とし、前記探索用近傍領域が、前記予測情報に含まれる画面内予測の参照画素からなることを第８の特徴とする。
【００１７】
また、前記符号化対象ブロックに対して探索される類似領域が、前記予測情報に含まれる画面内予測の種類が一致する領域とブロック単位で一致するよう、前記近傍領域類似領域を探索する範囲を限定することを第９の特徴とする。
【００１８】
また、前記基底関数構成手段は、前記近傍領域類似領域を探索するに際して、画素に含まれる第１の色空間座標に対して前記探索された前記近傍領域類似領域を、画素に含まれる第２の色空間座標及び第３の色空間座標の少なくとも一方における前記近傍領域類似領域として採用することを第１０の特徴とする。
【００１９】
また、前記基底関数構成手段は、前記近傍領域類似領域を探索するに際して、領域画素間の差分二乗和に基づいて探索することを第１１の特徴とする。
【００２０】
また、前記基底関数構成手段は、前記近傍領域類似領域を探索するに際して、探索元領域および該探索元領域を移動させて一致させる探索先領域の各領域において各領域の画素の平均値を減算してから算出する領域画素間の差分二乗和、または領域画素間の相関値に基づいて探索することを第１２の特徴とする。
【００２１】
また、前記基底関数構成手段は、前記入力を特異値分解して直交行列を算出し、該直交行列に基づいて前記変換基底関数を構成することを第１３の特徴とする。
【発明の効果】
【００２２】
前記第１、第２の特徴によれば、当該符号化対象単位ブロックに対する変換基底関数を適応的に構成でき、かつ符号化対象単位ブロックからではなく符号化済の画素情報から変換基底関数を構成するため変換基底関数自体の符号量が不要であるので、効率的な符号化を行うことができる。
【００２３】
前記第３の特徴によれば、類似領域の探索が画素単位ではなくブロック単位で行われるため、探索を高速に行うことができる。
【００２４】
前記第４の特徴によれば、符号化済第１色ブロックの当該第１の色空間座標における画素値の領域をそのまま第２の色空間座標及び第３の色空間座標の少なくとも一方における探索結果として採用するので、探索に要する計算量を削減できる。
【００２５】
前記第５の特徴によれば、動き情報の参照先をそのまま探索領域として決定するので、探索に要する計算量を削減できる。
【００２６】
前記第６の特徴によれば、符号化対象ブロックの画素との相関が大きい可能性が高い、符号化対象ブロックの近傍画素を用いて探索を行うので、符号化対象ブロックの類似領域の探索精度が高まる。
【００２７】
前記第７の特徴によれば、符号化対象ブロックの画素との相関が大きい可能性が高い、符号化対象ブロックの隣接画素を用いて探索を行うので、符号化対象ブロックの類似領域の探索精度が高まる。
【００２８】
前記第８の特徴によれば、符号化対象ブロックの画素との相関が大きい可能性が高い、符号化対象ブロックの画素に対する画面内予測の参照画素を用いて探索を行うので、符号化対象ブロックの類似領域の探索精度が高まる。
【００２９】
前記第８の特徴に加えてさらに第９の特徴によれば、符号化対象ブロックと画面内予測の種類が一致するブロックが類似領域として選ばれるので、該類似領域において予測残差の算出を省略できる。
【００３０】
前記第１０の特徴によれば、第１の色空間座標に対する探索結果を第２の色空間座標及び第３の色空間座標の少なくとも一方における探索結果として採用するので、探索計算が省略できる。
【００３１】
前記第１１の特徴によれば、画素間の差分二乗和に基づいて探索を行うことで符号化対象ブロックの類似領域の探索精度が高まる。
【００３２】
前記第１２の特徴によれば、平均値を除去した上での画素間の差分二乗和又は相関値に基づいて探索を行うことにより、前記第１１の特徴における場合よりも多くの候補領域から探索することとなり、符号化対象ブロックの類似領域の探索精度が高まる。さらに前記第１２の特徴および前記第１３の特徴によれば、平均値を除去した上での画素間の差分二乗和又は相関値に基づいて探索を行っても、適切な変換基底関数を構成することができる。
【００３３】
前記第１３の特徴によれば、特異値分解を用いることによって任意の符号化対象ブロックに対する適応的な変換基底関数を構成することができる。
【図面の簡単な説明】
【００３４】
【図１】本発明の一実施形態に係る画像符号化装置のブロック図である。
【図２】図１の画像符号化装置に対応する画像復号装置の一実施形態のブロック図である。
【図３】基底関数構成手段における変換基底関数算出のフロー図である。
【図４】符号化対象ブロックと同一フレームからの符号化対象ブロックの類似領域探索の模式図である。
【図５】色空間を利用して類似領域を探索する一実施形態を模式的に示す図である。
【図６】色空間を利用して類似領域を探索する一実施形態を模式的に示す図である。
【図７】類似領域に対して符号化対象ブロックと同様の画面内予測を適用して予測残差を算出することを模式的に示す図である。
【図８】類似領域に対して符号化対象ブロックと同様の動き予測を適用して予測残差を算出することを模式的に示す図である。
【発明を実施するための形態】
【００３５】
以下に、図面を参照して本発明の実施形態について詳細に説明する。本発明の一実施形態における画像符号化装置のブロック図および対応する画像復号装置のブロック図をそれぞれ図１、図２に示す。
【００３６】
図１に示す本発明の一実施形態における画像符号化装置は、複数の画素から構成される単位ブロックの各画素に対して、符号化済画素から予測される各画素との間で差分処理を行って得られた予測残差について直交変換・量子化・符号化を行って単位ブロック毎に符号化を行う画像符号化装置に対して、前記単位ブロックを効率的に直交変換できる基底関数を適応的に構成する機能を付加した構成を特徴とするものである。
【００３７】
すなわち、本発明の画像符号化装置は図１に示すように、符号化済画素から入力画素を予測する予測情報を算出する予測手段９と、予測情報および符号化済画素から予測画素を生成する補償手段１０と、入力画像の単位ブロックの各画素（入力画素）から予測画素を減算し予測残差を出力する差分器１と、後述の基底関数構成手段８で構成された変換基底関数を用いて予測誤差を周波数領域の変換係数に変換する変換手段２と、変換係数を量子化する量子化手段３と、量子化された変換係数（量子化値）を可変長符号化する符号化手段４と、量子化値を逆量子化する逆量子化手段５と、逆量子化された変換係数を逆変換する逆変換手段６と、予測画素と逆変換された予測残差とを加算し復号画素を再構成する加算器７と、画素又は予測残差に応じて適応的に変換基底関数及び逆変換基底関数を構成する基底関数構成手段８とを備える。
【００３８】
一方、本発明の一実施形態の画像復号装置は図２に示すように、可変長復号で量子化値などに逆変換する復号手段２１と、量子化されている変換係数を逆量子化する逆量子化手段２２と、逆量子化された変換係数を逆変換する逆変換手段２３と、予測情報及び復号済画素から予測画素を生成する補償手段２４と、予測画素と再構成された予測残差とを加算して復号画素を再構成する加算器２５と、画素又は予測残差に応じて適応的に逆変換基底関数を構成する基底関数構成手段２６とを備える。該画像復号装置の動作については後述する。
【００３９】
以下に、図１の画像符号化装置の動作を説明する。
【００４０】
入力画像ａである符号化対象領域の入力画素は、差分器１と予測手段９に入力する。差分器１は、入力画素と補償手段１０から送られる符号化済画素（に対応する復号画素）から予測された予測画素との差分を予測残差として算出し、算出された予測残差は変換手段２および基底関数構成手段８に送られる。
【００４１】
変換手段２は、差分器１から送られる予測残差を、基底関数構成手段８から導出された変換基底関数又は所定の直交変換を用いて周波数領域に変換し、該変換基底関数による変換によって得られた変換係数を量子化手段３に出力する。
【００４２】
変換手段２において所定の直交変換を用いる場合には、直交変換としてはDCT（離散コサイン変換）、DCTの近似変換またはDWT（離散ウェーブレット変換）などを利用することができる。
【００４３】
入力画素の各ピクチャ（フレーム）は、あらかじめ規定された数の画素（例えば３２×３２画素、１６×１６画素、８×８画素、４×４画素あるいはそれらの組み合わせ）から構成される単位ブロックに分割され、単位ブロック毎に基底関数構成手段８から導出された直交変換基底関数による変換又は所定の直交変換が行われる。
【００４４】
なお、変換手段２において基底関数構成手段８が導出する適応的な変換基底関数を用いるか、所定の直交変換を用いるかの切替は、フレームの種類（Intra予測か動き予測か）およびフレーム中の単位ブロックに応じて決まり、該切替情報はフラグ情報として基底関数構成手段８で与えられ変換手段２から符号化手段４に送られるものとする。
【００４５】
量子化手段３は、変換手段２から送られた変換係数を量子化する。量子化によって得られた量子化値は符号化手段４および逆量子化手段５に出力される。量子化処理に用いられる量子化パラメータは、定数値の組み合わせとして設定することが可能である。または、変換係数の情報量に応じて制御することで、出力するビットレートを一定に保つこと可能である。
【００４６】
符号化手段４は、変換手段２より送られた切替情報、量子化手段３より送られた量子化値および予測手段９から送られた予測情報を符号化し、符号情報ｂとして出力する。符号化は、符号間の冗長性を取り除く可変長符号又は算術符号などを利用することができる。
【００４７】
一方、逆量子化手段５は、量子化手段３における量子化の逆の手順を行うことで、量子化手段から送られた量子化値を変換係数に逆量子化する。逆量子化により得られた変換係数は逆変換手段６に送られる。
【００４８】
なお、入力画像の画素のうち差分器１、変換手段２、量子化手段３および符号化手段４を経た画素は符号化済画素であり、まだ処理されていない画素と区別される。符号化済画素は量子化手段３から符号化手段４と同時に逆変換手段５以降の各手段にも入力されるので、逆変換手段５以降の各手段においても、まだ処理されていない画素と区別して符号化済画素と呼ぶこととする。
【００４９】
逆変換手段６は、変換手段２の逆の手順を行うことで、逆量子化手段５から送られた変換係数を逆直交変換する。該逆直交変換にあたっては変換手段２において用いた、所定の直交関数の逆関数、または基底関数構成手段８で導出した基底関数の逆関数を用いる。逆変換によって得られた予測残差は加算器７に送られる。
【００５０】
加算器７には、逆変換手段６から送られる予測残差と、補償手段１０から送られる符号化済画素から予測された予測画素とが入力される。加算器７は入力された予測誤差と予測画素との和を復号画素として算出する。算出された復号画素は基底関数構成手段８、予測手段９および補償手段１０に送られる。
【００５１】
基底関数構成手段８は、差分器１から送られる予測残差と加算器７から送られる復号画素とが入力される。基底関数構成手段８では後述の手順によって、復号画素内から予測残差のブロック領域の入力画素（差分器１を経て予測残差となる前の入力画素）との類似領域を探索し、該類似領域の予測残差に対応する量を求めて、差分器１から送られた予測残差に適した変換基底を算出し、変換手段２に変換基底を、逆変換手段７に逆変換基底を送る。
【００５２】
予測手段９は、画像の冗長性を削減する予測情報を決定するものであり、加算器７から送られた復号画素をもとに、入力画像ａの各画素を近似するための方法を予測情報として決定する。決定された予測情報は符号化手段４および補償手段１０に送られる。
【００５３】
予測方法については、従来技術の各種方法が利用できる。例えば、Ｈ．２６４ではIntra予測（画面内予測）や動き予測が利用されている。このとき、予測情報の決定については、各予測モードで個別に符号化し、符号量と歪量から算出される符号化コストを最小化する予測モードを選択する。符号化コストを最小化する方法の詳細については、非特許文献１に記載されているので説明を省略する。
【００５４】
さらに、補償手段１０は、加算器７から送られた復号画素及び予測手段９で決定された予測情報に基づいて、入力画素の近似値としての予測画素を生成する。生成された予測画素は、差分器１および加算器７へ送られる。
【００５５】
なお、図１において入力がIntra予測フレーム内の最初のブロックなどであって予測画素、復号画素及び予測情報が利用できないような場合、差分器１において入力画素から減算される量はゼロであり、予測残差ではなく入力画素が変換手段２に入力され、以降は予測残差に対して行われたのと同様の処理である。よってこのような場合の入力画素も予測残差の特別な場合に含まれるものとしてよい。また変換手段２などではブロック単位で処理を行っているが、加算器７や予測手段９や補償手段１０などでは適宜符号化済みブロックの蓄積情報を利用する。該情報は図１に不図示のフレームメモリなどに格納して適宜利用することは明らかである。
【００５６】
なお、図１の構成はＨ．２６４の符号化装置を想定しているが、本発明はこれに限定されず、MPEG、JPEGなどの符号化装置にも適用できることは明らかである。MPEGの符号化装置は図１において予測手段９として動き予測が適用される構成である。JPEGの符号化装置は、図１の予測手段９、補償手段１０が省略された構成であり、この構成において差分器１、加算器７は減算、加算を行う必要がない。
【００５７】
JPEGの符号化装置の構成では予測残差ではなく入力画素がそのまま変換手段２で変換係数となり、量子化手段３で量子化され符号化手段４で符号化される。また量子化値は逆量子化手段５、逆変換手段６を経て復号画素となり、基底関数構成手段８に入力される。基底関数構成手段８は予測残差ではなく入力画素に適した基底関数を算出して変換手段２と逆変換手段６に送る。
【００５８】
本発明の画像符号化装置の特徴的構成である基底関数構成手段８で変換基底関数を算出する手順について説明する。
【００５９】
基底関数構成手段８の目的は、後段の変換手段及び逆変換手段において符号化対象ブロックを周波数領域へ変換・逆変換するに際して、当該符号化対象ブロックに最適な変換基底関数及び逆変換基底関数を導出して変換手段２及び逆変換手段６に送ることにある。ただし、当該符号化対象ブロックから最適な変換基底関数を導出すると、基底関数そのものを符号化する必要が生じてしまうため、符号化効率を改善できないという問題がある。この問題を解決するため、準最適解として符号化済領域から当該符号化対象ブロックに類似した領域を探索し、探索結果の最適な変換基底関数を当該符号化対象ブロックの変換基底関数として代用するという手順を取る。
【００６０】
図３に、基底関数構成手段８における変換基底関数算出の手順のフロー図を示す。
【００６１】
なお、図３の手順を開始するにあたっては所定量の復号画素領域（類似領域探索対象）が既に存在していることが前提である。よって例えばIntra予測のフレームにおいてはフレーム内の最初の所定量の符号化対象ブロックに関しては、基底関数構成手段８にて個別に算出する基底関数ではなくDCT等の所定の固定基底関数を用いることとし、復号画素領域を確保しておくものとする。該固定基底関数の利用は基底関数構成手段８から変換手段２に対して、前述の切替情報として指定することができる。
【００６２】
なおまた当該切替情報は切替フラグであるので、その符号量は、前述の符号化対象ブロックから最適関数を算出して基底関数そのものを符号化したと仮定した場合に要する符号量と比べてわずかであり、符号化効率への影響はほとんどない。また例えば前述のようなIntra予測フレーム内の最初の所定数のブロックのみ固定基底関数を利用するとあらかじめ定めておけば、切替情報を省略してフレームの種類とブロック位置の情報のみから切替判断を行うこともできる。
【００６３】
まずステップＳ１では、基底関数構成手段８は、加算器７から送られる復号画素と差分器１から送られる予測残差とを入力する。予測残差からは、符号化対象ブロックの領域（どのフレームのどの位置であるか）の情報を把握する。入力された復号画素は、異なる時刻のフレームに限らず、同一時刻のフレームであっても良い。
【００６４】
次にステップＳ２では、復号画素からは符号化対象ブロックと最も類似していると判定される領域を探索する。類似領域を探索する各種の実施形態を以下に説明するが、各実施形態では画素信号を記述する時間（フレーム時刻）、空間（フレーム画面内での位置）および信号（画素信号を構成する色空間信号）のいずれか（又は複数）に注目して探索を行う。まず空間に注目して探索する実施形態として、符号化対象ブロックと同一のフレームから類似領域を探索する一実施形態を説明する。
【００６５】
該実施形態を図４に模式的に示す。図４は符号化対象ブロックＢが存在するある時刻のフレーム全体を示している。符号化対象ブロックＢは例として４×４画素の場合を示している。フレームにおいてラスタースキャン順（スキャンは画素ではなくブロック単位）に符号化が行われ、符号化対象ブロックＢの手前まで符号化が終わったとすると、該符号化対象ブロックＢの手前までの領域が符号化済画素からなる復号画素領域である。該復号画素領域がステップＳ１にて入力された復号画素であり、類似領域を探索する領域全体となる。また符号化対象ブロックＢ以降のラスタースキャン順の領域（符号化対象ブロックＢ自体を含む）はまだ符号化されていない符号化前領域である。
【００６６】
符号化対象ブロックＢに隣接して且つ符号化済画素領域である探索用隣接領域Ｐを利用して、隣接領域Ｐを復号画素領域内で平行移動しながら類似した領域を探索する。隣接領域Ｐと最も類似した領域からは、符号化対象ブロックＢと隣接領域Ｐとの相対位置関係かつ大きさが同等となる領域を、符号化対象ブロックＢと類似した領域として抽出する。
【００６７】
例えば図４に示すように隣接領域Ｐに最も類似した領域の探索結果（ａ）として領域ａ１が得られたならば、符号化対象ブロックＢの類似領域は同サイズ（図４なら４×４画素サイズ）でかつ領域a1との相対位置関係が領域PとブロックＢとの相対的位置関係と一致する領域ａ２となり、隣接領域Ｐに最も類似した領域の探索結果が（ｂ）の領域ｂ１であれば符号化対象ブロックＢの類似領域は同様に領域ｂ２となる。
【００６８】
なお隣接領域Ｐによる類似領域の探索対象は復号画像領域内であって且つ、その探索結果として抽出される符号化対象ブロックＢの類似領域が全て復号画素領域に含まれるような範囲において行われるものとする。例えば図４に示す例では隣接領域Ｐの１画素上段の領域が類似領域として探索されると、符号化対象ブロックＢの類似領域として縦３画素×横４画素の領域が符号化済画素でない領域となってしまうので、このような領域は探索対象としない。
【００６９】
隣接領域Ｐは符号化対象ブロックＢの左隣に位置する一列以上の画素、あるいは上隣に位置する一行以上の画素、あるいは両者の全て若しくは一部を利用することができる。図４に示す例では、隣接領域Ｐは４×４画素の符号化対象ブロックＢの隣接左隣１列４画素と、隣接上隣１行４画素と、該行および列の交点でブロックＢの対角位置にあたる１画素と、の計９画素となっているが、例えばブロックＢの隣接左隣２列を用いて４画素×２列の計８画素を隣接領域とするなどしてもよい。（なお図４における領域Ｐ２は後述のテンプレートマッチングの説明において用いる。）
【００７０】
また隣接領域Ｐの一実施形態として、Ｈ．２６４におけるIntra予測のように画面内で予測が行われる場合は、予測画素を生成するのに使われる参照画素を用いても良い。該参照画素はＨ．２６４の４×４Intra予測であれば周知のように、符号化対象ブロックの左隣１列の画素、上隣１列の画素、又はそれら両者を含む。
【００７１】
また隣接領域Ｐによる探索範囲の一実施形態として、符号化対象ブロックＢに画面内予測が採用されている場合は、符号化済領域（復号画素領域）においてブロックＢと同一の画面内予測モードが採用されている領域内に、ブロックＢの類似領域として判定される領域がブロック単位で一致するような探索範囲に限定することができる。該実施形態の場合、隣接領域Ｐによる探索範囲はブロックＢの大きさ分の離散格子状の領域のうち、対応領域がブロックＢと同一の画面内予測が採用されている一部となるので探索範囲が少なくなり処理時間の短縮が図れる。また該実施形態によれば、このように探索回数を限定するだけでなく類似領域における予測残差の算出を省略できることから処理時間の短縮を図ることもできる。すなわち後述のステップＳ３において算出する、対応する予測残差が、既に類似領域の符号化にあたって用いられた予測残差と一致するので、算出を省略できる。
【００７２】
また隣接領域Ｐによる探索範囲の一実施形態として、探索範囲を当該フレーム内の復号画素領域の全体とするのではなく、符号化対象ブロックＢから所定の距離以内にある領域又は符号化対象ブロックＢ付近の所定の領域に限定することができる。
【００７３】
また隣接領域Ｐによる探索範囲の一実施形態として、探索結果として得られる符号化対象ブロックＢの類似領域が、変換手段２にて変換される単位ブロックに一致するような領域に探索範囲を限定することができる。例えば符号化対象ブロックＢが４×４画素であれば、該探索範囲は復号画素領域において４画素毎の格子点領域となる。なお該実施形態は別時刻フレームに探索範囲がある場合にも適用できる。また前述の同一画面内予測モードが採用されている領域に探索範囲を限定する実施形態は、該実施形態の１つである。
【００７４】
なお、図４を用いて説明したような隣接領域Ｐは、より一般には符号化対象ブロックＢの近傍領域（必ずしも符号化対象ブロックＢに接している必要はない領域）すなわち探索用近傍領域Ｐを用いる場合における一実施形態とみなせる。この場合、上記の符号化対象ブロックＢの類似領域は、探索用近傍領域Ｐの類似領域の探索結果として得られたａ１やｂ１を近傍領域類似領域と呼ぶことにすると、探索用近傍領域Ｐを近傍領域類似領域に平行移動するのと等しい平行移動を符号化対象ブロックＢに対して適用することで移される領域、と表現することもできる。
【００７５】
また同一フレームから符号化対象領域と類似した領域を探索し且つ構築する別の実施形態として、以下の非特許文献４に開示されたテンプレートマッチングを用いることができる。テンプレートマッチングでは図４に示す符号化対象領域Ｂの類似領域の探索且つ構築のために、図４の隣接領域ＰのうちＢの左上側２×２画素領域に隣接する領域Ｐ２（縦２画素＋横２画素＋対角１画素）を探索に用いる。
【００７６】
テンプレートマッチングにおいてはＰ２の類似領域の探索結果から抽出する領域は図４のａ２やｂ２（４×４画素の領域）のうち左上の２×２画素の領域であり、Ｐ２の類似領域を上位４個探索して、該探索結果から得られる４個の２×２画素の領域を所定の順（例えばラスタースキャン順）に並べることによって、４×４画素の符号化対象ブロックＢの類似領域を構築する。符号化対象ブロックＢが４×４以外のサイズであっても同様に４分割ブロック上位４個によって類似領域を構築する。該テンプレートマッチングによれば符号化対象ブロックＢのテクスチャを考慮した類似領域を得ることができる等の効果がある。
【００７７】
（非特許文献４）T. K. Tan, C. S. Boon, and Y. Suzuki, "Intra prediction by template matching," IEEE International Conference on Image Processing, pp.1693--1696, 2006.
【００７８】
一方、図４では特に空間に注目して探索する各実施形態を説明したが、時間に注目して探索する、すなわち符号化対象ブロックが属するフレームとは時刻が異なるフレームから類似領域を探索する場合を説明する。この場合、予測手段９が符号化対象ブロックに対する予測情報としてフレーム間動き情報を算出していれば、動き情報の参照先（当該参照先は予測情報が与えられているので符号化済フレーム内の領域となる）をそのまま類似領域とする。
【００７９】
該動き情報の参照先の利用によれば、図４の実施形態におけるような近傍領域を用いた探索が不要なため、計算量を削減することができる。予測手段９が動き情報を算出していない場合は、前述の図４の実施形態によって同一フレーム上近傍画素によって同一フレーム上から類似領域探索を実行する。
【００８０】
さらに、類似領域探索の別実施形態として、画素信号の色空間に注目して探索する場合（色空間による実施形態その１）を説明する。該実施形態を模式的に図５に示す。なお、同図では同一時刻フレーム内に類似領域を探索した例を示すが、別時刻フレームで類似領域が探索されていてもよい。例えばＲ（赤）、Ｇ（緑）、Ｂ（青）の３つの色信号で画素が表現されている場合に所定時刻フレームの所定位置の符号化対象ブロックの類似領域を探索するとする。この場合、同図（Ａ）のＲ信号フレームにおける探索結果（ａ）に示すようにＲ信号のフレームにおいては上述の各実施形態のいずれか、すなわち空間又は時間に注目した探索によって類似領域が既に探索されているならば、残りのＧ、Ｂ信号において同一フレームおよび同位置の符号化対象ブロックの類似領域として、同図（Ｂ）、（Ｃ）の各探索結果（ｂ）、（ｃ）に示すようにＲ信号において探索された類似領域と同じ位置（フレーム内の空間位置およびフレーム間の時間位置）であって且つ各Ｇ、Ｂ信号に属する領域を用いる。
【００８１】
なお色空間による実施形態その１では、Ｇ信号、Ｂ信号における符号化対象ブロックに対して後述のステップＳ３ではＲ信号利用による各Ｇ信号、Ｂ信号内の探索結果を用いて、各Ｇ信号、Ｂ信号フレーム内で（図７、図８のような）処理を行う。
【００８２】
また色空間をさらに積極的に利用した別実施形態（色空間による実施形態その２）を説明する。該実施形態を模式的に図６に示す。例えばＲ、Ｇ、Ｂの３つの色信号で画素が表現されているとし、Ｒ信号のフレームにおいていずれかの実施形態（色空間利用以外の実施形態）により類似領域が探索され符号化が済んでいるとする。この場合、残りのＧ、Ｂ信号における符号化対象ブロックの類似領域を、同図の矢印（ａ）、（ｂ）に示すように同一フレーム同一ブロック位置の符号化済Ｒ信号のブロック自身とする。すなわちＧ信号、Ｂ信号の類似領域がＲ信号の画素値によって与えられる。
【００８３】
なお色空間による実施形態その２において、Ｇ信号、Ｂ信号における符号化対象ブロックに対して後述のステップＳ３、Ｓ４では、その類似領域をＲ信号としたのでＲ信号フレーム内で処理を行って基底を算出する。この場合、前もって色空間利用以外の実施形態でＲ信号に対して基底を算出した処理とは異なり、Ｇ信号、Ｂ信号における基底算出処理では、類似領域として符号化対象ブロックと同位置のＲ信号画素（符号化済）がそのまま利用でき、かつステップＳ３で当該同位置のブロックを対象として対応する予測残差算出等を行い、ステップＳ４で基底を求める。またこの場合、Ｇ信号、Ｂ信号における処理は一致するので、Ｇ信号に対して求めた基底をＢ信号で用いることで計算を省略できる。
【００８４】
以上の色空間による実施形態その１、その２では信号間の高い相関を利用することにより符号化性能を上げ、かつ探索などを省いて計算量を抑制する。Ｒ信号の結果をＧ信号、Ｂ信号に用いるとしたが、その両方に用いてもいずれか一方のみに用いてもよい。これら実施形態はRGB信号を変換したその他の信号、例えばＹ（輝度信号）、Ｃｂ（色差信号）、Ｃｒ（色差信号）などにおいても同様に適用できる。
【００８５】
なお、以上説明した図３のステップＳ２の各実施形態において、探索範囲の中での画素との類似度判定には、画素値そのものの一致性として、差分二乗和を利用できる。ただし、後述するステップＳ４における最適な変換基底関数の導出に際しては、平均値の相違は許容できるため、平均値の影響を除く処理として、隣接画素の平均値を減算した後の数値と探索対象の平均値を減算した後の数値との差分二乗和を利用しても良い。あるいは、該隣接画素と探索対象との相関も利用できる。
【００８６】
この平均値の影響を除いた後の差分二乗和又は相関を利用する実施形態においては、差分二乗和を用いる場合よりも類似と判定される領域が増えるため、より符号化対象ブロックに対する類似度の高い領域が選出される傾向が強くなる。且つ平均値の差などがあっても前述のようにステップＳ４では符号化対象ブロックに対して適切な基底を算出できるので符号化効率が高まる。
【００８７】
また前述の色空間による実施形態その１、その２では探索が省略される色空間に関しては、上述のようにステップＳ４において平均値の相違が許容されることから、特に色空間による実施形態その２において別の色空間の値を類似領域として採用する場合であって画素値の平均値自体に各色空間で差があるような場合であっても一般に各色空間の画素値間に相関はあるので、別の色空間の値による類似領域からも最適な基底関数を算出できるという効果がある。
【００８８】
ステップＳ２に続いてステップＳ３では、変換手段２で変換する符号化対象ブロックに相当する情報を前記探索結果から算出する。符号化対象ブロック領域に画素値上で類似しているとしてステップＳ２で探索された類似領域であるが、変換手段２で変換するのは入力画像そのままの画素値ではなく符号化対象ブロック領域の画素から予測画素を差分器１で引いた予測残差である。変換手段２では該予測残差に対する適切な基底関数を用いる必要がある。よって探索結果の類似領域から基底関数構成手段８が基底関数を算出するにあたって、類似領域の画素からも対応する予測画像を減算して、対応する予測残差を求めておくのがステップＳ３である。
【００８９】
すなわちステップＳ３ではステップＳ２の探索結果得られた類似領域に対して符号化対象ブロックと同等の予測及び補償によって対応する予測残差を算出する。なお、前述のJPEGの実施形態のような場合には、入力画素からそのまま基底関数が算出されるので、ステップＳ３での処理は必要ない。
【００９０】
例えば、予測手段９による予測情報を利用する場合、符号化対象ブロックが予測情報としてIntra予測を採用していれば、類似領域でも同様のIntra予測を適用し予測残差を算出する。これを模式的に図７に示す。
【００９１】
図７に示すように、あるフレームにおいて符号化対象ブロックＢ１の類似領域がＢ２である。ブロックＢ１にはＨ．２６４の４×４Intra予測のモード０〜８のうち、例えば予測モード０が適用されており、ブロックＢ１の上部隣接１行の４×１画素領域Ｐ１０によってＢ１を予測する。よって符号化対象ブロックＢ１の予測残差は次の減算[式A]
（Ｂ１の画素）−（対応するＰ１０の画素）    [式A]
により得られる。これに対応する類似領域Ｂ２から算出する予測残差は、ブロックＢ２における予測モード０の領域である、ブロックＢ２の上部隣接１行の４×１画素領域Ｐ２０の画素を用いて次[式B]で与えられる。
（Ｂ２の画素）−（対応するＰ２０の画素）    [式B]
上記[式B]の値が、次のステップＳ４に送られる。なお前述のように、同一画面内予測モードが採用されている領域に探索範囲を限定する実施形態では、各予測モードにおける[式Ｂ]に対応する量が既に符号化にあたって算出済みであるため、本ステップＳ３にて改めて算出する必要がない。
【００９２】
あるいはステップＳ３において、符号化対象ブロックが予測手段９による予測情報として動き予測を採用し、動き予測の参照先を類似領域とする実施形態においては、参照先である類似領域においても同様に動き予測を適用し予測残差を算出する。これを模式的に図８に示す。
【００９３】
図８では時系列順のフレームＦ１、Ｆ２、Ｆ３が存在し、各フレームのブロック間には動き予測の参照関係がある。符号化対象ブロックはフレームＦ３のブロックＦ３Ｂであり、フレームＦ１、Ｆ２は符号化済みである。符号化対象ブロックＦ３Ｂは動き予測（ａ）で過去フレームＦ２のブロックＦ２Ｂを参照している。この場合、符号化対象ブロックＦ３Ｂの予測残差は次[式Ｃ]
（Ｆ３Ｂの画素）−（Ｆ２Ｂの画素）    [式Ｃ]
で与えられる。これに対応する、類似領域Ｆ２Ｂの予測残差は、Ｆ２Ｂにおける同様の（Ｆ２Ｂを符号化するに際して適用された）動き予測（ｂ）で参照されるフレームＦ１のブロックをＦ１Ｂとして、次[式Ｄ]
（Ｆ２Ｂの画素）−（Ｆ１Ｂの画素）    [式Ｄ]
で与えられる。上記[式Ｄ]の値が、次のステップＳ４に送られる。
【００９４】
なお、図８の説明の例では動き予測としてフレーム間の順方向予測の例を示したが、双方向の場合で別時刻の２枚のフレームを参照している場合には、そのうち１枚のみを選択して利用することで図８の順方向予測の例と同様に対応する予測残差を算出できる。この場合、参照先は未来のフレームであってもよい。
【００９５】
なお、図７、図８の説明における、又は図３のステップＳ２で用いられるような予測情報は、図１において入力画像ａが直接に予測手段９へ入力され、加算器７経由の符号化済画素と比較して算出され、符号化手段４や補償手段１０以降に入力される。よって符号化対象ブロックの予測残差を差分器１が算出する時点で、当該符号化対象ブロックに対する予測情報は既に算出され符号化手段４にも入力されているので、上記の図７、図８、図３の説明におけるような利用（符号化対象ブロックを符号化する段階における当該ブロックの予測情報の利用）が可能となる。対応する図２の復号装置においても復号対象ブロックが復号手段２１で可変長復号された時点で対応する予測情報が利用可能となり、補償手段２４に送られる。
【００９６】
なおまた、図７、図８の説明の例で類似領域として用いた予測情報の参照先において、符号化対象ブロックに適用されているIntra予測又は動き予測が利用できず、従って対応する予測残差を算出できない場合には、当該符号化対象ブロックにおける適用基底フラグ（切替情報）を所定の固定基底利用に設定し、次のステップＳ４による最適変換基底算出は行わない。また、参照先でこのように動き予測が利用できない場合は固定基底を用いるとあらかじめ決めておけば切替情報は省略してもよく、対応する画像復号装置側でも同様の判断が行われる。
【００９７】
図３に戻り、ステップＳ３の次の最後のステップＳ４において、類似領域の探索結果若しくはその予測残差に対する最適な変換基底関数をKL（カルーネン・レーベ、Karhunen-Loeve）変換や特異値分解によって算出する。本発明では前述のように符号化済画素から類似領域の予測誤差対応量を求めてこれを符号化対象ブロックの予測誤差該当量として変換基底を求めるため、変換基底を符号化する必要がない。よってこれらKL変換や特異値分解の他にも（DCTなどと異なり）任意の入力に対して入力毎に最適な変換を算出できるような技術を用いることができる。
【００９８】
例えば、特異値分解によって変換基底関数を算出する場合は、類似領域の探索結果若しくはその予測残差をm行n列の行列Aで表すとき、行列Aを次式のように行列の積に分解することに相当する。
A=UΣVt
なお、Uはm行m列の直交行列、Vはn行n列の直交行列、tは転置操作(VtはVの転置行列)を表す。また、ΣはAの特異値σi(1≦i≦rank A)を降順に並べたm行n列の対角行列を表す。特異値σiは、m<nの場合はAAt、m≧nの場合はAtAの固有値λiの平方である。具体的にm≧nの場合の手順は、まずAtAの固有値を求め、特異値を算出する。次に、直交行列U及びVはその定義からUtU=I、VtV=Iであることを利用して（Iは単位行列）、
AtAV=VΣ2
が得られるので、次式で示すようにVの列ベクトルviはAtAの固有値σi2に対応する固有ベクトルとして求められる。
AtAvi=σi2vi
一方、UはAVΣ−１で求められる。
【００９９】
直交行列Ut及びVは基底関数として変換手段２に送られ、直交行列U及びVtは逆基
底関数として逆変換手段６に送られる。
【０１００】
なお、この基底関数による周波数変換では対角成分に非0値が出現しやすいので、量子化後のスキャン順序は対角成分を優先するようにすることが望ましい。あるいは、特許文献（特願2010-090392）による適応的スキャン順序と組み合わせても良い。
【０１０１】
以上説明した図１の構成の画像符号化装置（前述のJPEGやMPEGの構成の場合を含む）によれば、各単位ブロックの周波数領域変換に際して、符号化済領域から類似領域を探索し、探索結果の最適な変換基底関数を符号化対象ブロックの変換基底関数として利用することで、符号化効率が向上する。また、変換基底関数が適応的に変化しうるにも関わらず、変換基底関数に関する追加的な情報を格納する必要がないことから高い符号化効率が可能となる。
【０１０２】
次に、図１の画像符号化装置に対応する図２の画像復号装置の動作を説明する。図１の符号化手段４にて符号化された符号情報ｂは、図２の復号手段２１に入力し、復号手段２１は符号化手段４の逆の手順としての可変長復号を行うことで量子化値、予測情報および切替情報を出力する。可変長復号により得られた量子化値は逆量子化手段２２に、予測情報は補償手段２４に、切替情報は基底関数構成手段２６に送られる。
【０１０３】
逆量子化手段２２は量子化値を量子化手段３の逆の手順によって逆量子化して変換係数とし、逆変換手段２３へ送る。逆変換手段２３は基底関数構成手段２６から逆変換基底関数の情報を受け取って変換係数を予測残差に変換して基底関数構成手段２６および加算器２５に送る。補償手段２４は予測情報および復号済画素の情報から復号対象ブロックの予測画素を求め、加算器２５に送る。加算器２５は予測画素と予測残差とを加算して当該復号対象ブロックの復号画像ｃを得て、補償手段２４および基底関数構成手段２６に送る。
【０１０４】
基底関数構成手段２６（図２）は基底関数構成手段８（図１）と同様に、復号対象ブロックの変換係数を逆変換手段２３で予測残差に変換する逆変換基底関数を求める。加算器２５から送られる復号画像領域内を、図１の説明と同様にして復号対象ブロックの類似領域を求め、対応する予測残差を算出して逆変換基底関数を求める。また適宜切替情報を参照して固定基底を用いる。
【０１０５】
なお、図１の説明と同様に、補償手段２４や加算器２５などでは不図示のフレームメモリなどを参照して適宜復号済画素の情報を利用する。また図２でも図１と同様に、Ｈ．２６４の復号装置を想定しているが、MPEG、JPEGなどの復号装置にも適用できることは明らかである。
【符号の説明】
【０１０６】
２…変換手段、３…量子化手段、４…符号化手段、５…逆量子化手段、６…逆変換手段、８…基底関数構成手段、９…予測手段、１０…補償手段、２１…復号手段、２２…逆量子化手段、２３…逆変換手段、２４…補償手段、２６…基底関数構成手段
【図１】
0005455229.tif 000002
【図２】
0005455229.tif 000003
【図３】
0005455229.tif 000004
【図４】
0005455229.tif 000005
【図５】
0005455229.tif 000006
【図６】
0005455229.tif 000007
【図７】
0005455229.tif 000008
【図８】
0005455229.tif 000009