(57)【要約】【課題】  量子化歪みを拡散することにより、主観的悪影響を軽減する。【解決手段】  変換処理部５０４は、Ｎ個のデータブロックそれぞれの予測残差、若しくは符号化済みのブロックを用いた予測処理を行っていないブロックに対してはデータブロック生成部５０１が生成したデータブロックそれぞれに対して、変換行列Ａによる変換処理をおこなってＭ個のデータに変換する。変換行列Ａを用いると、変換前のデータに比べて、変換後のデータが滑らかに変化するようになる。【選択図】  図１
2010057129.tif 000002
【特許請求の範囲】
【請求項１】
データ系列を符号化する符号化装置であって、
入力データ系列からＮ個のデータを有する１次元のデータ列Ｘであるデータブロックを生成するデータブロック生成手段と、
Ｍ≧ＮであるＭ行Ｎ列の変換行列Ａのi行ｊ列の要素をａi,ｊとし、前記変換行列Ａの逆変換を表す逆変換行列Ｂのi行j列の要素をｂi,ｊとした場合、前記変換行列Ａの行列成分の行の番号を示すｋに対して、不等式
【数１】
2010057129.tif 000023
を満たす前記変換行列Ａを前記データ列Ｘに対し乗じ、Ｍ個のデータを有する変換データを得る変換手段と、
前記変換データを符号化する符号化手段と、
を有することを特徴とする符号化装置。
【請求項２】
前記データブロック生成手段は、前記入力データ系列のデータの配列とは異なる配列に各データを並べ替え、並べ替えた後のデータ系列の配列に基づき前記データブロックを生成することを特徴とする請求項１記載の符号化装置。
【請求項３】
前記データブロック生成部は、生成する同じ前記データブロックに、前記入力データ系列の配列に基づきデータブロックを生成した場合に複数のブロックに分類されるデータが含まれるように前記入力データ系列を並べ替えることを特徴とする請求項２記載の符号化装置。
【請求項４】
前記変換データを関数に近似する近似関数を算出する近似関数算出手段をさらに有し、
前記符号化手段は、前記近似関数と、前記変換データの差分のデータに基づき符号化を行うことを特徴とする請求項１記載の符号化装置。
【請求項５】
データ系列を符号化する符号化装置であって、
入力された時間的な系列、空間的な系列、あるいはそれらの複数のチャンネルを有する入力データ系列からＮ個のデータを有するＮ１行Ｎ２列の２次元のデータ列Ｘであるデータブロックを生成するデータブロック生成手段と、
Ｍ１行Ｎ１列の変換行列Ａ１、Ｍ２行Ｎ２列の変換行列Ａ２のそれぞれi行ｊ列の要素をａi,ｊとし、前記変換行列Ａ１、Ａ２の逆変換を表す逆変換行列Ｂ１、Ｂ２のi行j列の要素をそれぞれｂi,ｊとした場合、前記変換行列Ａの行列成分の行の番号を示すｋに対して、不等式
【数２】
2010057129.tif 000024
を満たす前記変換行列Ａ１、Ａ２を用いてＡ１ＸＡ２Ｔを算出し、Ｍ１行Ｍ２列の２次元のデータ列Ｙである変換データを得る変換手段と、
前記変換データを符号化する符号化手段と、
を有することを特徴とする符号化装置。
【請求項６】
データ系列を復号する復号装置であって、
入力された符号化済みデータを復号し、変換データＹを得る復号手段と、
符号化された際のＭ行Ｎ列の変換行列Ａのi行ｊ列の要素をａi,ｊとし、前記変換行列Ａの逆変換を表す逆変換行列Ｂのi行j列の要素をｂi,ｊとした場合、前記変換行列Ａの行列成分の行の番号を示すｋに対して、不等式
【数３】
2010057129.tif 000025
を満たす前記逆変換行列Ｂを前記変換データＹに対し乗じることで、１次元のデータ列Ｘであるデータブロックを得る逆変換手段と、
１次元のデータ列Ｘであるデータブロックから、時間的な系列、空間的な系列、あるいはそれらの複数のチャンネルを有する入力データ系列を再生する再生手段と、
を有することを特徴とする復号装置。
【請求項７】
データ系列を復号する復号装置であって、
入力された符号化済みデータを復号し、変換データＹを得る復号手段と、
符号化されたＭ１行Ｎ１列の変換行列Ａ１、Ｍ２行Ｎ２列の変換行列Ａ２のそれぞれi行ｊ列の要素をａi,ｊとし、前記変換行列Ａ１、Ａ２の逆変換を表す逆変換行列Ｂ１、Ｂ２のi行j列の要素をそれぞれｂi,ｊとした場合、前記変換行列Ａの行列成分の行の番号を示すｋに対して、不等式
【数４】
2010057129.tif 000026
を満たす前記変換行列Ｂ１、Ｂ２を用いてＢ１ＹＢ２Ｔを算出し、Ｎ個のデータを有する２次元のＮ１行Ｎ２列のデータ列である変換データを得る変換手段と、
２次元のデータ列Ｘであるデータブロックから、時間的な系列、空間的な系列、あるいはそれらの複数のチャンネルを有する入力データ系列を再生する再生手段と、
を有することを特徴とする符号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化装置及び復号装置に関する。
【背景技術】
【０００２】
映像や音声といった、時間系列、空間系列をなすデータを、空間的な小領域に、または、周波数空間で複数の異なる帯域に分割し、予測、変換、量子化等の処理を行うことで高い符号化効率を得ていた。
【０００３】
動画像を符号化する方法として、H.264が用いられている。H.264においては、ブロック単位（マクロブロック、サブマクロブロック）の大きさで、ブロック歪みや、モスキート歪みが生じていた。また、ブロックのモード切り替えによる画質の変化といった画質劣化が発生することがあった（例えば特許文献１）。
【０００４】
また、静止画像の符号化方法では、JPEG2000が高い符号化効率が得られる方式として用いられている。これらの、ウェーブレット符号化を用いた方式では、高域の帯域の量子化により、焦点ボケのような画質劣化が生じ、また、低域の帯域の量子化により、画像の広範囲に渡るうねり状の歪みが生じていた。被写体の構造を損なうような劣化が発生することがあった（例えば特許文献２）。
【０００５】
これらの手法では、非可逆な符号化を行った場合、量子化誤差に起因する量子化歪みが、分割した小領域や帯域内に局在するため、知覚されやすい主観的な劣化が生じていた。
【特許文献１】特開２００１−１４５１０４号  公報
【特許文献２】特開２０００−３０８０５８号  公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、ブロック内で隣接するデータ間の相関の低いデータ配列であっても効率的な符号化が可能な、符号化装置、及び復号装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために本発明は、データ系列を符号化する符号化装置であって、入力データ系列からＮ個のデータを有する１次元のデータ列Ｘであるデータブロックを生成するデータブロック生成手段と、Ｍ≧ＮであるＭ行Ｎ列の変換行列Ａのi行ｊ列の要素をａi,ｊとし、前記変換行列Ａの逆変換を表す逆変換行列Ｂのi行j列の要素をｂi,ｊとした場合、前記変換行列Ａの行列成分の行の番号を示すｋに対して、不等式（式１）を満たす前記変換行列Ａを前記データ列Ｘに対し乗じ、Ｍ個のデータを有する変換データを得る変換手段と、前記変換データを符号化する符号化手段と、を有することを特徴とする符号化装置を提供する。また、それに対応する復号装置を提供する。
【０００８】
また、データ系列を符号化する符号化装置であって、入力された時間的な系列、空間的な系列、あるいはそれらの複数のチャンネルを有する入力データ系列からＮ個のデータを有するＮ１行Ｎ２列の２次元のデータ列Ｘであるデータブロックを生成するデータブロック生成手段と、Ｍ１行Ｎ１列の変換行列Ａ１、Ｍ２行Ｎ２列の変換行列Ａ２のそれぞれi行ｊ列の要素をａi,ｊとし、前記変換行列Ａ１、Ａ２の逆変換を表す逆変換行列Ｂ１、Ｂ２のi行j列の要素をそれぞれｂi,ｊとした場合、前記変換行列Ａの行列成分の行の番号を示すｋに対して、不等式（式２）を満たす前記変換行列Ａ１、Ａ２を用いてＡ１ＸＡ２Ｔを算出し、Ｍ１行Ｍ２列の２次元のデータ列Ｙである変換データを得る変換手段と、前記変換データを符号化する符号化手段と、を有することを特徴とする符号化装置を提供する。また、それに対応する復号装置を提供する。
【発明の効果】
【０００９】
本発明によれば、ブロック内で隣接するデータ間の相関の低いデータ配列であっても効率的な符号化が可能となる。
【発明を実施するための最良の形態】
【００１０】
以下、本発明の実施形態について図面を参照しながら詳細に説明する。なお、同じ構成には同じ符号を付し、重複する説明は省略する。
【００１１】
（第１の実施形態）
本実施形態の符号化装置は、２次元の動画像のデータ系列を符号化する例である。本実施形態では、符号化対象のデータが画素の輝度値である場合について例示する。
【００１２】
図１は、本実施形態の符号化装置５の構成を示す図である。
【００１３】
符号化装置５は、データブロック生成部５０１、予測データブロック生成部５０２、メモリ５０３、変換処理部５０４、逆変換処理部５０５、符号化部５０６、局所復号部５０７、加算部５０９、減算部５０８を有する。
【００１４】
データブロック生成部５０１は、入力された動画像の各画素から、複数のデータブロックを生成する。データブロック生成部５０１が生成するデータブロックの例を図３に示す。図３では、２次元の入力された１フレームの画像である入力データ列６０１を破線で区切る４×４の小領域に分割し、その各小領域からデータを一つずつ順に取り出して出力データブロック群として新たな出力データブロック６０２１を順次生成している。この場合、出力データブロック６０２１はデータ数Ｎ＝１６のデータブロックである。なお、各出力データブロック６０２１内のデータは図３では模式的に２次元で示しているが、ラスタスキャン等により１次元のデータ列に並べ替えられる。
【００１５】
１つの出力データブロック群６０２に含まれるデータが、複数の入力データ列６０１の小領域から順次選択されるように出力データブロック群６０２を生成する。
【００１６】
なお、本実施形態では、入力データ列６０１の小領域に分類されるデータと出力データブロック６０２１に含まれるデータとが異なるように並べ替えを行うことで、ブロック歪等の影響を抑える構成にしているが、入力データ列６０１の小領域をそのまま出力データブロック６０２１としてもよい。入力データ列６０１の小領域に含まれるデータと出力データブロック６０２１に含まれるデータとの相違度が大きいほど、ブロック歪の局所的な集中を抑えることが出来るが、その分必要なメモリ量や処理の遅延が増える。
【００１７】
データブロック生成部５０１が生成した[k,l]番目のデータブロックＸ[k,l]に含まれるデータは、図３に示す例では、（A4,B4,C4,D4,E4,F4,G4,H4,I4,J4,K4,L4,M4,N4,O4,P4）である。これを、Ｘ[k,l]＝(x1,…,xN)Tと記載する。[k,l]番目のデータブロックとはフレーム内でブロックをラスタスキャンした場合の順番を模式的に示すものである。データブロック生成部５０１は、フレームの入力データ系列６０１についてデータブロックを生成する。なお、本実施形態では、入力されたフレーム内のデータを全て出力データブロック６０２１に分割してから、予測データブロックの生成処理を行う例について示したが、１つの出力データブロック６０２１を生成する毎に予測を行っても良い。
【００１８】
予測データブロック生成部５０２は、データブロック生成部５０１が生成したデータブロックに対して、符号化済みの近接データブロックの局所復号データから予測データを生成する。予測データブロック生成部５０２が行う処理を、図３を参照して説明する。
【００１９】
予測データブロック生成部５０２は出力データブロック６０２１をラスタスキャン順に順次予測処理を行う。そうすると、データブロックＸ[k,l]の予測データを生成する場合、データブロックＸ[k-1,l]、Ｘ[k,l-1]、Ｘ[k-1,l-1]は既に予測処理済みである。局所復号部５０７が局所復号化し、その後逆変換処理部５０５が逆変換処理することにより、データブロックＸ[k-1,l]、Ｘ[k,l-1]、Ｘ[k-1,l-1]に関する局所復号データＸLD[k-1,l]、ＸLD[k,l-1]、ＸLD[k-1,l-1]が得られる。局所復号データＸLD[k-1,l]、ＸLD[k,l-1]、ＸLD[k-1,l-1]を用いてデータブロックＸ[k,l]に対する予測処理が行われる。データブロックＸ[k,l]の予測データＸp [k,l]は、例えば（式１）によって生成される。
【数１】
2010057129.tif 000003
【００２０】
ここで、ｓi,jは適当な重み係数であり、n,mは、予測に用いる処理済みデータブロックの範囲を表す。なお、この和の計算ではi=j=0の場合は除外する。重み係数ｓi,jは、入力データの性質により決める。これは、目的に応じてあらかじめ決めておいてもよいし、あるいは、適当なデータ期間ごとに、XとXpの二乗誤差が最小になるように設定して、その設定した値も符号化して出力するようにしてもよい。また、重み係数ｓi,jをスカラー値とした場合には、予測に使うデータブロックごとに一つの重み係数を使うことになるが、重み係数ｓi,jをＮ×Ｎの対角行列とすると、予測に使うデータブロック内の各データに個別の重み係数を設定できるようになる。
【００２１】
減算部５０８は、入力データと予測データとの差をとった予測残差を変換処理部５０４に出力する。
【００２２】
変換処理部５０４は、データブロックのＮ個の予測残差、若しくは符号化済みのブロックを用いた予測処理を行っていないブロックに対してはデータブロック生成部５０１が生成したデータブロックそれぞれに対して、変換行列Ａによる変換処理をおこなってＭ個のデータに変換する。なお、変換行列Ａは、（式２）の条件を満たす変換行列である。行列Ａのi行j列の要素をai,j、逆変換行列Ｂのi行j列の要素をｂi,jと記す。なお、ＭはＮと等しいか、Ｎよりも大きな整数である。また変換行列Ａによる変換処理は、Ｍ行Ｎ列の行列Ａとの行列演算として表現することがでる。
【数２】
2010057129.tif 000004
【００２３】
（式２）の条件を満たす変換行列Ａを用いると、変換前のデータに比べて、変換後のデータが滑らかに変化するようになる。（式２）の条件を満たす行列による変換処理を行うことで、変換後のデータが滑らかになる効果の説明は後述する。
【００２４】
符号化部５０６は、差分パルス符号変調(DPCM)、あるいは、離散的コサイン変換(DCT)等の直交変換をブロック毎に行う。直交変換後に、量子化、エントロピー符号化といった符号化処理を行う。
【００２５】
局所復号部５０７は、符号化部５０６が符号化した符号化済のデータをブロック毎に復号する。
【００２６】
逆変換処理部５０５は、変換処理部５０４が行った変換処理と対になる逆変換を行う。逆変換処理部５０５は、局所復号部５０７が復号化したデータに対して、先に説明した変換行列Ａに対応する逆変換行列Ｂを用いて逆変換を行う。Ｍ＝Ｎの場合には、逆変換行列Ｂは変換行列Ａの逆行列となり、Ｂ＝Ａ−１である。Ｍ＞Ｎの場合には、変換行列Ａの一般逆行列を用いて、Ｂ＝（ＡＴＡ）−１ＡＴと表すことができる。
【００２７】
メモリ５０３は、局所復号部５０７で復号化され、その後逆変換処理部５０５で逆変換処理されたローカルデコード画像を別のデータブロックの予測に用いるために記憶する。
【００２８】
加算部５０９は、予測データに、局所復号された予測残差の値を加えて符号化の結果である局所復号された画素値を得る。
【００２９】
図２は、本実施形態の符号化部５０６と、局所復号部５０７の構成を抜き出して示す図である。
【００３０】
符号化部５０６は、直交変換部５０６１、量子化部５０６２、エントロピー符号化部５０６３を有する。
【００３１】
局所復号部５０７は、逆量子化部５０７１、逆直交変換部５０７２を有する。
【００３２】
直交変換部５０６１は、離散直交変換（DCT）やKurhunen-Loeve変換（KL変換）といった直交変換を行う。
【００３３】
量子化部５０６２は、直交変換後の係数値を量子化する。
【００３４】
エントロピー符号化部５０６３は、量子化された係数値に対してエントロピー符号化を行う。
【００３５】
逆量子化部５０７１は、エントロピー符号化が行われる前の量子化された係数値を逆量子化する。
【００３６】
逆直交変換部５０７２は、逆量子化後のデータを直交変換部５０６１が行った直交変換に対応する逆直交変換を行う。
【００３７】
図２に示す構成は、画像符号化方式として広く使われているものであり、その構成要素を利用し、実施をすることができる。
【００３８】
次に、変換処理部５０４による（式２）の条件を満たす変換行列Ａによる変換処理を行うことで、変換後のデータが変換前のデータと比較して滑らかになる効果について説明する。
【００３９】
データブロック生成部５０１が生成したデータブロックをＸ＝（ｘ１，…，ｘＮ）Ｔ、変換行列Ａを用いた変換処理後のデータをＹ＝（ｙ１，…，ｙＭ）Ｔと表す。変換処理部５０４が行う変換処理は、Ｙ＝ＡＸのＹを求める処理である。ＹがＸよりも滑らかに変化するとは、Ｙの隣接するデータｙｋ、ｙｋ＋１の差分を量子化幅Ｑyで量子化した値の分散が、Ｘの隣接するデータｘｋ、ｘｋ＋１の差分を量子化幅Ｑxで量子化した値の分散よりも小さくなる、ということである。すなわち、V[.]を分散を表す演算子として、取り得る任意のｋに対して、
【数３】
2010057129.tif 000005
【００４０】
を満たす必要がある。Ｘを量子化幅Ｑxで量子化した場合の量子化誤差と、Ｘを変換行列Ａで変換して得られるＹを量子化幅Ｑyで量子化した場合の量子化誤差とが等しくなるように、量子化幅ＱxおよびＱyを仮定する。
【００４１】
分散について、Ｖ[ａｘ１＋ｂｘ２]＝ａ２Ｖ［ｘ１]＋２ａｂＶ[ｘ１，ｘ２]＋ｂ２Ｖ [ｘ２]が成り立つ。Ｖ[ｘ１，ｘ２]はｘ１とｘ２の共分散を表し、ｘ１とｘ２が独立ならばゼロとなる。Ｘ＝（ｘ１，…，ｘＮ）Ｔの各データは独立であるとすると、
【数４】
2010057129.tif 000006
【００４２】
となるので、（式３）の条件は、（式５）に書き換えることが出来る。
【数５】
2010057129.tif 000007
【００４３】
次に、ＱＸとＱＹの関係を求める。まず、変換行列Ａによる変換後のデータＹの隣接するデータの差分ｙｋ−ｙｋ＋１に対して、量子化幅Ｑyで量子化したときの量子化誤差の大きさの期待値を考える。ここで、変換行列Ａによる変換後のデータＹの、隣接データの差分をＹｄ＝（ｙ１−ｙ２，…，ｙi−ｙi+1，…，ｙM−ｙ１）Ｔとする。この各要素に量子化Ｑyによる量子化誤差ＥＹ＝（ε１，…，εＭ）が加わり、Ｙｄ’＝Ｙｄ＋Ｅｙ’となったとする。このとき、逆変換Ｂにより、Ｘｄ’＝ＢＹｄ’となる。これと、量子化誤差が無い場合の値Ｘｄ＝ＢＹｄとの差が復号側でみたときの誤差となる。その誤差の大きさは、（式６）に示す値となる。
【数６】
2010057129.tif 000008
【００４４】
よって、量子化誤差の期待値は、
【数７】
2010057129.tif 000009
【００４５】
となる。Ｅ［・］は期待値を取る演算子で、p(ε)は量子化誤差に対する確率密度関数である。量子化誤差の分散Ｖ［ε］は量子化幅Ｑyの２乗と比例する。例えば、p(ε)が一様分布となる場合、Ｖ［ε］＝Ｑy２／１２となる。一方、変換行列Ａによる変換を行わずに、入力Ｘの隣接データの差分を直接量子化幅Ｑyで量子化した場合の量子化誤差の期待値は、
【数８】
2010057129.tif 000010
【００４６】
となる。Ｘに加わる量子化誤差の分散Ｖ［ε］は、今度はＱＸの２乗に比例し、たとえば、p(ε)が一様分布となる場合では、Ｖ［ε］＝Ｑｘ２／１２となる。これより、（式３）で求めた量子化誤差の大きさの期待値と、（式４）で求めた量子化誤差の大きさの期待値が等しくなるようにするには、
【数９】
2010057129.tif 000011
【００４７】
とすればよい。最終的に、（式９）を用いて、（式２）の条件が求められる。（式２）が、取り得る全てのｋに対して、成り立てばよい。この条件を満たすような変換行列Ａは、（式３）を満たす。したがって、変換行列Ａを用いると、変換前のデータに比べて、変換後のデータが滑らかに変化することが期待できる。変換行列Ａによる変換後に、DPCMやDCT等による符号化を行う際に効率的な符号化が行えるようになる。
【００４８】
次に、（式２）の条件を満たす変換行列の例を（式１０）〜（式１５）に示す。（式１０）および（式１４）はＮ＝Ｍ＝４の例である。（式１１）および（式１２）はＮ＝Ｍ＝８の例である。（式１３）はＮ＝Ｍ＝１６の例である。（式１５）はＮ＝８，Ｍ＝１６の例である。（式１０）から（式１３）に示した例は、いずれも行列の形を巡回行列としたものである。また、（式１５）に示した例では、行列の奇数行目、あるいは、偶数行目だけを取り出した場合に、それぞれが巡回行列となる行列である。一方、（式１４）に示した例は、行列の形を巡回行列に限らずに、行列の各要素を自由に設定して（式２）を満たすように作成したものである。参考として、（式２）の左辺を右辺で除した値をｒとして、変換行列Ａの例と一緒に記しておく。ｒが１未満の行列は、（式２）の条件を満たす行列である。
【数１０】
2010057129.tif 000012
【数１１】
2010057129.tif 000013
【数１２】
2010057129.tif 000014
【数１３】
2010057129.tif 000015
【数１４】
2010057129.tif 000016
【数１５】
2010057129.tif 000017
【００４９】
以上、変換行列Ａの具体的な例を示したが、（式２）を満たす変換行列Ａはここで示した例に限らず、様々なバリエーションが存在する。
【００５０】
次に、データブロック生成部５０１がデータブロックを生成する際のデータの並べ替えの規則の例を示す。図４および図５は１次元のデータ列を並べ替える例を示す。
【００５１】
図４に示した例は、Ｎ＝４の例であり、連続する４個の入力データを並べ替えて１つのデータブロックとしているが、その並べ替えの規則を４種類用意し、データブロックごとに並べ替えの規則を順に変えていくものである。
【００５２】
図５に示した例は、Ｎ＝４の例であり、連続する４個の入力データは、それぞれ別のデータブロックに入るようにデータブロック生成部５０１の方式が定められている。
【００５３】
図４、図５で示した例、または例示していない別の規則の中から、どの規則を利用するかについては、入力データの性質と出力データに要求される要件から、適切なものを選択すればよい。図４で示した例では、入力データで近傍であった範囲でデータの並べ替えを行っているため、図５示した例に比べると歪みの拡散効果は少ない。しかし、並べ替えを入力データ列の狭い範囲内で行うため、並べ替えに要する遅延やメモリ量を少なくすることができる。
【００５４】
図６は、本実施形態の符号化装置の変形例である符号化装置６の構成を示す図である。
【００５５】
符号化装置６は、予測は変換処理部５０４による変換処理を行った後のデータに対して行う点が特徴である。符号化装置５は、（式１６）に示す、処理対象のブロックのデータＸとその予測データＸＰの差分の残差データに対して変換行列Ａによる変換処理を行っていた。
【数１６】
2010057129.tif 000018
【００５６】
変換処理部５０４が行う変換処理が線形であるため、重み係数ｓi,jがスカラー値の場合は、変換処理の前後どちらに予測を行ってもよい。重み係数をＮ×Ｎの対角行列とした場合は、一般にｓi,jとは異なる行列となるが、適当な重み係数行列ｒi,jを用いることにより、各データに個別の重み係数を設定できるようになる。
【００５７】
符号化装置６では、変換処理部５０４で変換処理を行った後に予測を行うため、逆変換処理部５０５による逆変換を行う必要がない。
【００５８】
本実施形態の符号化装置では、データブロック生成部が生成するデータ列が１次元である例について示したが、２次元のデータ列を生成してもよい。その場合、入力されたデータブロック内のデータをＮ１×Ｎ２の２次元データ行列とすると、２次元データ行列Ｘに対して、Ｍ１行Ｎ１列の変換行列Ａ１と、Ｍ２行Ｎ２列の変換行列Ａ２を用いて、変換処理部５０４は、行列演算Ａ１ＸＡ２Ｔを行う。Ａ１、Ａ２共に、（式２）を満たす行列である。
【００５９】
本実施形態の符号化装置では、変換処理部５０４が連続するデータが滑らかに変化するようなデータ列へと変換をする変換行列Ａによる変換処理を行う。そのため、データブロック生成部５０１が入力された画像のデータ列を並べ替え、隣接データ間の相関が低いブロックを生成した場合であっても、その後の変換処理によって隣接データが滑らかに変化するデータブロックに変換することが可能である。その後に符号化部５０６が行う直交変換による符号量の増加を抑えることができる。したがって、量子化歪みの固有パターンや伝送路でのバーストエラーが、元の並びに戻した際に局在化させず画面内に拡散させることができ、歪みが知覚されにくく、かつ符号量を抑えた符号化処理が可能となる。
【００６０】
図７は、H.264動画像符号化方式で用いられているイントラ予測方式の例を示す図である。H.264イントラ予測方式では、入力画像データに対して、入力されたデータ配列で小領域（ブロック）に分割している。あるブロックの予測を行う際に、有効な予測を行うために用いる参照画素データは符号化済みのブロックと処理対象のブロックとの境界に位置するデータのみであった。また、処理対象のブロック内のデータのうち、符号化済みブロックから離れた位置のデータは、参照画素データとの相関が低いため、予測効率の低下が生じていた。
【００６１】
これに対して、本実施形態の符号化方法では、入力されたデータ配列の並べ替えを行い新たなブロックを生成し、生成されたブロック毎に符号化処理が行われる。そのため、符号化済みのデータが入力されたデータ配列の位置上で点在するため、処理対象のデータの近くに処理済みのデータが存在し、多くのデータの予測を有効に行うことができる。よって、効率の良い予測が可能となる。
【００６２】
（第２の実施形態）
図８は、本実施形態の符号化装置７の構成を示す図である。符号化装置７では、変換行列Ａによる変換処理後のデータを波形に近似する波形近似部５０８がさらに加えられている。
【００６３】
波形近似部５０８は、変換処理部５０４による変換行列Ａによる変換処理後のデータを波形に近似する。近似する波形は、あらかじめ定められた周期（例えば２π）を持つ正弦波であり、近似波形の振幅と位相とバイアスを求める。また、変換行列Ａによる変換処理後のデータと、求めた近似波形をＭ個の等間隔にサンプリングした値との差分データを求める。また、この近似波形をＭ個にサンプリングした値は、局所復号部５０７で局所復号されたデータに加えられ、逆変換処理部５０５へと送られる。
【００６４】
波形近似部５０８は、データブロックごとに近似波形の振幅と位相とバイアスの値を求め復号側に送る。この際、振幅・位相およびバイアスの情報は、適当な方法で符号化を行って、符号化処理後のデータに多重化しても良い。
【００６５】
図９は、変換行列Ａによる変換処理後のデータと、その近似波形との例を２つ示した図である。図９中の離散的な棒グラフの値は、Ｍ＝６４の変換処理後のデータである。また、同図での連続した波形が、波形近似部５０８が求めた近似波形である。図９では、２つのデータブロックの近似波形について示しているが、それぞれ異なる振幅と位相とバイアスの波で近似されている。
【００６６】
変換行列Ａによる変換処理後のデータ系列に波形近似を行う効果を説明する。変換行列Ａとして、（式１０）〜（式１３）のような巡回行列を用いた場合、あるいは、（式１５）のように２つの巡回行列を併せて一つの行列としたような場合、変換行列Ａによる変換処理後のデータ列は、そのエンベロープが比較的滑らかな１周期分の波形となる。このような波形近似を行うと、近似を行わなかった場合と比較して、その後の符号化部５０６で、より少ない符号量での符号化が可能となる。
【００６７】
波形近似では、変換処理部の出力Ｙ=(y1, …,yM)Tに対して、ｋ＝１，…，Ｍとして、たとえば、（式１７）に示す形で近似する。
【数１７】
2010057129.tif 000019
【００６８】
ここで、周期ωは、変換行列Ａの形から決まり、巡回行列の場合には、ω＝２π／Ｍとなる。バイアスｂは、Ｙの平均値より、ｂ＝Σｋｙｋ／Ｍとなる。振幅Ａと位相φは、例えば
【数１８】
2010057129.tif 000020
【００６９】
として、
【数１９】
2010057129.tif 000021
【００７０】
と求めればよい。波形近似は、巡回行列に限らず、周期構造を持つ行列を変換行列Ａとして用いた場合、Ａから決まる周期を用い、近似波形の振幅、位相、バイアスをデータブロック毎に求めればよい。
【００７１】
このように、本実施形態の符号化方法によれば、より少ない符号量での効率的な符号化が可能となる。
【００７２】
（第３の実施形態）
図１０は、本実施形態のデータブロック生成部５０１の構成を抜き出して示す図である。本実施形態のデータブロック生成部５０１は、複数のデータ並べ替え方法を持ち、入力されたデータに対してその内の１つの方法で並べ替えを順次行っていく。
【００７３】
（式２０）に、Ｎ＝４で、方法の数ｋ＝５の場合の並べ替え方法の例を示す。
【数２０】
2010057129.tif 000022
【００７４】
この並べ替え方法の内、どの方法を用いるかは、入力されたデータブロックの順番に応じて適宜採用すればよい。例えば、(1)から(5)までを順に繰り返し適用する決まりとする。
【００７５】
データブロック生成部５０１で、このような複数の並べ替え方法を順次切り替えて用いることにより、その後の符号化処理で量子化誤差が発生した場合であっても、復号側で元のデータの並びに戻すと、量子化誤差の固有パターンが特定の小領域に集中しないようにすることができる。量子化誤差の固有パターンとは、例えば、ＤＣＴ係数の量子化が行なわれた場合、ＤＣＴ基底の形状が歪みとして現れる。
【００７６】
並べ替え方法をどのように設定するか、あるいは、データブロックの入力順から並べ替え方法を選択する方法をどのように設定するかは、量子化誤差の固有パターンの発生傾向等を考慮して、適切に設定を行えばよい。
【００７７】
（第４の実施形態）
図１１は、本実施形態の変換処理部５０４の構成を抜き出して示す図である。
【００７８】
本実施形態の、変換処理部５０４は、変換行列Ａを複数（図１１ではｋ個）用意し、データブロックの入力順から一意に定まる方法で、用いる変換行列Ａを順次変更するものである。
【００７９】
行列演算部５０９は、選択された変換行列Ａを用いてデータブロックに対して変換処理を行う。
【００８０】
量子化歪みの固有パターンは、引き続く符号化処理で発生する量子化歪みのパターンと、逆変換処理部５０５で逆変換処理に用いる逆行列Ｂとで、どのデータ位置に固有パターンが現れるかが決まる。そのため、変換行列Ａとそれに対応する逆変換行列Ｂを複数用意して切り替えることにより、最終的に元のデータ位置に並べ直した際に、特定の小領域に量子化歪みの固有パターンが発生することを避けることが可能となる。
【００８１】
（第５の実施形態）
図１２は、データブロック生成部が生成するデータブロックの例を示す図である。図１２では、隣接する入力データ列をあらかじめ定められた大きさのデータブロックに分割する。分割されたブロック内をさらに２つに分け、ブロックＰとブロックＳを生成する。
【００８２】
ブロックＰのデータ列は、後でブロックＳのデータ列を予測するために用いるため、この予測が効率よく行われるように、入力されたデータ系列の中で広範囲に分布し、データブロックＳのデータにできるだけ多く隣接するように配置されている。図に示した例では、規則正しく四分の一サブサンプルしブロックＰの配置を定めているが、この配置に限ない。例えば、ブロックＰに属するデータの数を少なく、あるいは、多く取るように定めても良い。あるいは、ランダムな配置によってブロックＰを出力するような構成でも良い。
【００８３】
ブロックＰは先ほど述べたように、ブロックＳのデータとより多く隣接するように配置されているため、ブロックＰ自身のデータは、元のデータ列で見たときには必ずしも隣接していない。そのため、ブロックＰの隣接するデータの相関は低くなっている。そのような互いに相関の低いデータ系列であっても、変換処理部５０４の変換処理により、データが滑らかになる。
【００８４】
一方、ブロックＳは、データブロックＰの局所復号データを用いて生成された予測ブロックＳとの差分が計算され、その予測残差データが符号化部５０６でデータ圧縮が行われる。
【００８５】
なお、ブロックＰは、そのまま変換処理部５０４による変換処理および符号化部５０６での圧縮を行う構成ではなく、符号化済みのデータブロックのデータからブロックＰのデータを予測し、その予測残差データに対して、変換処理および符号化を行う構成でもよい。この場合は、ブロックＳの予測にも、ブロックＰの局所復号データだけではなく、符号化済みのデータブロックのデータを同様に使うことができる。
【００８６】
また、ブロックＳについては、予測残差データの符号化処理の前に、変換行列Ａにより、予測残差データを滑らかにする処理を行うことも効果的である。
【００８７】
さらに、変換処理Ａの後に、第4の実施形態で説明した、波形近似データブロック生成部による波形近似を行うことも効果的である。
【００８８】
（第６の実施形態）
本実施形態の復号装置１０は、第１の実施形態の画像符号化装置が行った符合化済みのデータを復号する装置である。
【００８９】
図１３は、本実施形態の復号装置１０の構成を示す図である。
【００９０】
復号部７０１は、入力された符合化済みのデータに対して、符号化部５０６に対応する復号処理を行う。
【００９１】
逆変換処理部７０２は、変換行列Ａの逆変換を行う逆変換行列Ｂによる逆変換を復号部７０１が復号したデータに行う。
【００９２】
予測データブロック生成部７０５は、予測データブロック生成部５０２と同じ処理によって、予測データブロックを生成する。
【００９３】
加算器７０３は、逆変換がなされたデータと、予測データブロック生成部が生成した予測データブロックとを加算する。
【００９４】
メモリ７０４は、加算されたデータを記憶する。
【００９５】
データ列再生部７０６は、データブロック生成部５０１と対応する並べ替えを行い、元のデータの並びに戻し出力する。
【００９６】
図１４は、復号部７０１の構成を抜き出して示す図である。
【００９７】
復号部７０１は、エントロピー復号部７０１１、逆量子化部７０１２、逆直交変換部７０１３を有する。
【００９８】
エントロピー復号部７０１１は、エントロピー符号化部５０６３が行ったエントロピー符号化処理と対応する復号処理を行う。
【００９９】
逆量子化部７０１２は、量子化部５０６２が行った量子化処理と対応する逆量子化を、エントロピー復号がなされたデータに行う。
【０１００】
逆直交変換部７０１３は、逆量子化後のデータに対して直交変換部５０６１が行った直行変換に対応する逆直交変換を行う。
【０１０１】
（第７の実施形態）
図１５は、第２の実施形態の符号化装置７が行った符合化済みのデータを復号する復号装置１１の構成を示す図である。
【０１０２】
復号装置１１は、波形近似データブロック生成部７０７をさらに有する。
【０１０３】
波形近似データブロック生成部７０７は、波形近似部５０８が求めた近似波形の位相と振幅とバイアスの情報を用いて、あらかじめ定められた周期を持つサイン波をＭ個の等間隔にサンプリングした値を出力する。その後サンプリングした値は、復号処理が行われた後のデータに加算されて、逆変換処理される。
【０１０４】
なお、上記の各実施形態で用いている変換行列Ａと、本実施例における直交変換を表現する行列の積をあらかじめ用意しておき、別々に行列演算せずに一度の行列演算にまとめて処理を行っても良い。逆変換処理部についても同様である。また、本発明を画像符号化に用いる場合は、画面内符号化のみならず、画面間符号化として、動き補償予測残差画像を入力とすることも可能である。
【０１０５】
上記の各実施形態では、符号化の対象のデータが画像データである場合について例示したが、データ系列は、時間的な系列、あるいは、空間的な系列、あるいは、一つ以上の複数のチャンネルからなる系列、あるいは、時間的・空間的・複数チャンネルの任意の組み合わせからなる系列であってよい。例えば、音声データ等も本発明の符号化方法によって符号化することができる。
【０１０６】
本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。
【図面の簡単な説明】
【０１０７】
【図１】第１の実施形態の符号化装置の構成を示す図。
【図２】符号化部、局所復号部の構成を示す図。
【図３】データブロックを生成する動作を説明する図。
【図４】データブロックを生成する動作を説明する図。
【図５】データブロックを生成する動作を説明する図。
【図６】第１の実施形態の符号化装置の別の構成を示す図。
【図７】H.264イントラ予測の例を示す図。
【図８】第２の実施形態の符号化装置の構成を示す図。
【図９】変換行列Ａによる変換処理後のデータと、その近似波形との例を示す図。
【図１０】第３の実施形態の符号化装置のデータブロック生成部の構成を示す図。
【図１１】第４の実施形態の符号化装置の変換処理部の構成を示す図。
【図１２】第５の実施形態の符号化装置の構成を示す図。
【図１３】第６の実施形態の復号装置の構成を示す図。
【図１４】第６の実施形態の復号部の構成を示す図。
【図１５】第７の実施形態の復号装置の構成を示す図。
【符号の説明】
【０１０８】
５，６，７・・・符号化装置
５０１・・・データブロック生成部
５０２・・・予測データブロック生成部
５０３・・・メモリ
５０４・・・変換処理部
５０５・・・逆変換処理部
５０６・・・符号化部
５０７・・・局所復号部
５０８・・・波形近似部
５０６１・・・直交変換部
５０６２・・・量子化部
５０６３・・・エントロピー符号化部
５０７１・・・逆量子化部
５０７２・・・逆直交変換部
６０３・・・行列演算部
１０，１１・・・復号装置
７０１・・・復号部
７０２・・・逆変換処理部
７０３・・・加算器
７０４・・・メモリ
７０５・・・予測データブロック生成部
７０６・・・データ列再生部
７０７・・・波形近似データブロック生成部
７０１１・・・エントロピー復号部
７０１２・・・逆量子化部
７０１３・・・逆直交変換部
６０１・・・入力データ列
６０２・・・出力データブロック群
６０２１・・・出力データブロック
【図１】
2010057129.tif 000027
【図２】
2010057129.tif 000028
【図３】
2010057129.tif 000029
【図４】
2010057129.tif 000030
【図５】
2010057129.tif 000031
【図６】
2010057129.tif 000032
【図７】
2010057129.tif 000033
【図８】
2010057129.tif 000034
【図９】
2010057129.tif 000035
【図１０】
2010057129.tif 000036
【図１１】
2010057129.tif 000037
【図１２】
2010057129.tif 000038
【図１３】
2010057129.tif 000039
【図１４】
2010057129.tif 000040
【図１５】
2010057129.tif 000041