(57)【要約】【課題】人間にとって良好な品質の復号結果を得る。【解決手段】大ブロック化部３２は、データを第１のブロックに分割し、小ブロック化部３３は、第１のブロックのそれぞれを、第１のブロックよりデータ数の少ない第２のブロックに分割し、小ブロック相関判定部３４は、第１のブロック毎に、第１のブロックを構成する第２のブロック同士の相関を判定し、直交変換基底生成部３５は、第２のブロック同士の相関の判定の結果に応じて、第２のブロックの直交変換の基底の生成に用いる生成用データを決定し、その生成用データから直交変換の基底を生成し、直交変換部３６は、直交変換の基底を用いて、データを直交変換する。本発明は、例えば、画像データの符号化の処理を行う装置に適用することができる。【選択図】図１
2008312082.tif 000002
【特許請求の範囲】
【請求項１】
データを符号化する符号化装置において、
前記データを第１のブロックに分割する第１の分割手段と、
前記第１のブロックのそれぞれを、前記第１のブロックよりデータ数の少ない第２のブロックに分割する第２の分割手段と、
前記第１のブロック毎に、前記第１のブロックを構成する前記第２のブロック同士の相関を判定する判定手段と、
前記第２のブロック同士の相関の判定の結果に応じて、前記第２のブロックの直交変換の基底の生成に用いる生成用データを決定し、その生成用データから直交変換の基底を生成する直交変換基底生成手段と、
直交変換の前記基底を用いて、前記データを直交変換する直交変換手段と
を備える符号化装置。
【請求項２】
前記第１の分割手段は、画像データを前記第１のブロックに分割し、
前記第２の分割手段は、前記第１のブロックのそれぞれを、Ｎ個の画素からなるＭ個の前記第２のブロックに分割し、
前記判定手段は、前記第２のブロックの画素の画素値から、前記第２のブロック同士の相関を判定し、
前記直交変換基底生成手段は、前記第２のブロック同士の相関が低いと判定された場合、前記第１のブロックに含まれる前記第２のブロックと、前記第２のブロックの近傍に位置し、かつ前記第２のブロックとは異なる、Ｎ個の画素からなる第３のブロックとの画素の画素値を、前記生成用データに決定し、その生成用データから直交変換の基底を生成する
請求項１に記載の符号化装置。
【請求項３】
前記直交変換基底生成手段は、前記第２のブロック同士の相関が低いと判定された場合、前記第１のブロックに含まれる前記第２のブロックと、前記第２のブロックをずらした位置の前記第３のブロックとの画素の画素値を、前記生成用データに決定し、その生成用データから直交変換の基底を生成する
請求項２に記載の符号化装置。
【請求項４】
前記直交変換基底生成手段は、前記第２のブロック同士の相関が低いと判定された場合、前記第１のブロックに含まれる前記第２のブロックと、前記第１のブロックの周囲に隣接して位置する前記第３のブロックとの画素の画素値を、前記生成用データに決定し、その生成用データから直交変換の基底を生成する
請求項２に記載の符号化装置。
【請求項５】
前記判定手段は、前記第１のブロックを構成する前記第２のブロックの画素の画素値から算出される、その第２のブロック同士の相関を表す相関判定特徴量と、予め設定された所定の閾値とを比較することで、前記第２のブロック同士の相関を判定する
請求項２に記載の符号化装置。
【請求項６】
データを符号化する符号化装置の符号化方法において、
前記データを第１のブロックに分割し、
前記第１のブロックのそれぞれを、前記第１のブロックよりデータ数の少ない第２のブロックに分割し、
前記第１のブロック毎に、前記第１のブロックを構成する前記第２のブロック同士の相関を判定し、
前記第２のブロック同士の相関の判定の結果に応じて、前記第２のブロックの直交変換の基底の生成に用いる生成用データを決定し、その生成用データから直交変換の基底を生成し、
直交変換の前記基底を用いて、前記データを直交変換する
ステップを含む符号化方法。
【請求項７】
データを符号化する符号化装置として、コンピュータを機能させるプログラムにおいて、
前記データを第１のブロックに分割する第１の分割手段と、
前記第１のブロックのそれぞれを、前記第１のブロックよりデータ数の少ない第２のブロックに分割する第２の分割手段と、
前記第１のブロック毎に、前記第１のブロックを構成する前記第２のブロック同士の相関を判定する判定手段と、
前記第２のブロック同士の相関の判定の結果に応じて、前記第２のブロックの直交変換の基底の生成に用いる生成用データを決定し、その生成用データから直交変換の基底を生成する直交変換基底生成手段と、
直交変換の前記基底を用いて、前記データを直交変換する直交変換手段と
として、コンピュータを機能させるプログラム。
【請求項８】
請求項７に記載のプログラムが記録されている記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化装置および方法、プログラム、並びに記録媒体に関し、特に、例えば、人間の視覚にとって良好な画像を得ること等ができるようにする符号化装置および方法、プログラム、並びに記録媒体に関する。
【背景技術】
【０００２】
例えば、画像データの符号化に用いられる直交変換としては、直交変換後の電力集中度が理論的に最も高いカルーネン・レーベ変換（以下、KL変換と称する）がある。KL変換においては、直交変換の基底（KL変換の基底）が、符号化対象の画像データに依存するため、直交変換の基底の情報を伝送しなければならず、基底の情報を伝送する必要のない、例えば、DCT（Discrete Cosine Transform）等の直交変換と比較して、基底の情報の分だけ、情報量が多くなる。
【０００３】
そこで、KL変換の基底を算出する前に求められる自己相関行列の対称性を利用し、KL変換の基底を伝送する代わりに、自己相関行列の要素を、基底の情報として伝送することで、情報量を削減する手法が提案されている（例えば、特許文献１参照）。
【０００４】
また、画像データをブロックに分割し、ブロック毎に動き補償を行い、動き補償のなされたブロックについてKL変換を行うことで、直交変換の基底の情報を伝送せずに、かつ、相関の高いブロックを用いて基底を生成する手法がある（例えば、特許文献２参照）。
【０００５】
【特許文献１】特開２００１−３０９３８０号公報
【特許文献２】特開２００２−３１４４２８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、KL変換を利用した画像データの符号化では、KL変換によって得られる変換係数が量子化されるが、その量子化後の変換係数を復号して得られる復号画像の画質が、人間の視覚にとって良好なものになるとは限らない。特に、KL変換によって直交変換の基底を生成するのに用いるデータ群同士の相関が低い場合、人間の視覚にとって良好な画質の復号画像が得られないことがある。
【０００７】
本発明は、このような状況に鑑みてなされたものであり、例えば、人間の視覚にとってより良好な画質の復号画像等の復号結果を得ることができるようにするものである。
【課題を解決するための手段】
【０００８】
本発明の一側面の符号化装置、またはプログラムは、データを符号化する符号化装置、または符号化装置として、コンピュータを機能させるプログラムであって、前記データを第１のブロックに分割する第１の分割手段と、前記第１のブロックのそれぞれを、前記第１のブロックよりデータ数の少ない第２のブロックに分割する第２の分割手段と、前記第１のブロック毎に、前記第１のブロックを構成する前記第２のブロック同士の相関を判定する判定手段と、前記第２のブロック同士の相関の判定の結果に応じて、前記第２のブロックの直交変換の基底の生成に用いる生成用データを決定し、その生成用データから直交変換の基底を生成する直交変換基底生成手段と、直交変換の前記基底を用いて、前記データを直交変換する直交変換手段とを備える符号化装置、または符号化装置として、コンピュータを機能させるプログラムである。
【０００９】
前記第１の分割手段には、画像データを前記第１のブロックに分割させ、前記第２の分割手段には、前記第１のブロックのそれぞれを、Ｎ個の画素からなるＭ個の前記第２のブロックに分割させ、前記判定手段には、前記第２のブロックの前記画素の画素値から、前記第２のブロック同士の相関を判定させ、前記直交変換基底生成手段には、前記第２のブロック同士の相関が低いと判定された場合、前記第１のブロックに含まれる前記第２のブロックと、前記第２のブロックの近傍に位置し、かつ前記第２のブロックとは異なる、Ｎ個の画素からなる第３のブロックとの画素の画素値を、前記生成用データに決定し、その生成用データから直交変換の基底を生成させることができる。
【００１０】
前記直交変換基底生成手段には、前記第２のブロック同士の相関が低いと判定された場合、前記第１のブロックに含まれる前記第２のブロックと、前記第２のブロックをずらした位置の前記第３のブロックとの画素の画素値を、前記生成用データに決定し、その生成用データから直交変換の基底を生成させることができる。
【００１１】
前記直交変換基底生成手段には、前記第２のブロック同士の相関が低いと判定された場合、前記第１のブロックに含まれる前記第２のブロックと、前記第１のブロックの周囲に隣接して位置する前記第３のブロックとの画素の画素値を、前記生成用データに決定し、その生成用データから直交変換の基底を生成させることができる。
【００１２】
前記判定手段には、前記第１のブロックを構成する前記第２のブロックの画素の画素値から算出される、その第２のブロック同士の相関を表す相関判定特徴量と、予め設定された所定の閾値とを比較することで、前記第２のブロック同士の相関を判定させることができる。
【００１３】
本発明の一側面の符号化方法は、データを符号化する符号化装置の符号化方法であって、前記データを第１のブロックに分割し、前記第１のブロックのそれぞれを、前記第１のブロックよりデータ数の少ない第２のブロックに分割し、前記第１のブロック毎に、前記第１のブロックを構成する前記第２のブロック同士の相関を判定し、前記第２のブロック同士の相関の判定の結果に応じて、前記第２のブロックの直交変換の基底の生成に用いる生成用データを決定し、その生成用データから直交変換の基底を生成し、直交変換の前記基底を用いて、前記データを直交変換するステップを含む。
【００１４】
本発明の一側面においては、データが第１のブロックに分割され、第１のブロックのそれぞれが、第１のブロックよりデータ数の少ない第２のブロックに分割され、第１のブロック毎に、第１のブロックを構成する第２のブロック同士の相関が判定され、第２のブロック同士の相関の判定の結果に応じて、第２のブロックの直交変換の基底の生成に用いる生成用データが決定され、その生成用データから直交変換の基底が生成され、直交変換の基底を用いて、データが直交変換される。
【００１５】
なお、プログラムは、記録媒体に記録することができる。
【発明の効果】
【００１６】
本発明の一側面によれば、人間にとって良好な品質の復号結果を得ることができるように、データを、直交変換の基底を用いて符号化することができる。
【発明を実施するための最良の形態】
【００１７】
以下に本発明の実施の形態を説明するが、本発明の構成要件と、明細書又は図面に記載の実施の形態との対応関係を例示すると、次のようになる。この記載は、本発明をサポートする実施の形態が、明細書又は図面に記載されていることを確認するためのものである。従って、明細書又は図面中には記載されているが、本発明の構成要件に対応する実施の形態として、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その構成要件に対応するものではないことを意味するものではない。逆に、実施の形態が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００１８】
本発明の一側面の符号化装置、またはプログラムは、データを符号化する符号化装置、または符号化装置として、コンピュータを機能させるプログラムであって、前記データを第１のブロックに分割する第１の分割手段（例えば、図１の大ブロック化部３２）と、前記第１のブロックのそれぞれを、前記第１のブロックよりデータ数の少ない第２のブロックに分割する第２の分割手段（例えば、図１の小ブロック化部３３）と、前記第１のブロック毎に、前記第１のブロックを構成する前記第２のブロック同士の相関を判定する判定手段（例えば、図１の小ブロック相関判定部３４）と、前記第２のブロック同士の相関の判定の結果に応じて、前記第２のブロックの直交変換の基底の生成に用いる生成用データを決定し、その生成用データから直交変換の基底を生成する直交変換基底生成手段（例えば、図１の直交変換基底生成部３５）と、直交変換の前記基底を用いて、前記データを直交変換する直交変換手段（例えば、図１の直交変換部３６）とを備える符号化装置（例えば、図１の符号化装置１１）、または符号化装置として、コンピュータを機能させるプログラムである。
【００１９】
前記第１の分割手段には、画像データを前記第１のブロックに分割させ（例えば、図６のステップＳ１１２）、前記第２の分割手段には、前記第１のブロックのそれぞれを、Ｎ個の画素からなるＭ個の前記第２のブロックに分割させ（例えば、図６のステップＳ１１３）、前記判定手段には、前記第２のブロックの画素の画素値から、前記第２のブロック同士の相関を判定させ（例えば、図６のステップＳ１１４）、前記直交変換基底生成手段には、前記第２のブロック同士の相関が低いと判定された場合、前記第１のブロックに含まれる前記第２のブロックと、前記第２のブロックの近傍に位置し、かつ前記第２のブロックとは異なる、Ｎ個の画素からなる第３のブロックとの画素の画素値を、前記生成用データに決定し、その生成用データから直交変換の基底を生成させることができる（例えば、図６のステップＳ１１５）。
【００２０】
前記直交変換基底生成手段には、前記第２のブロック同士の相関が低いと判定された場合、前記第１のブロックに含まれる前記第２のブロックと、前記第２のブロックをずらした位置の前記第３のブロックとの画素の画素値を、前記生成用データに決定し、その生成用データから直交変換の基底を生成させることができる（例えば、図６のステップＳ１１５）。
【００２１】
前記直交変換基底生成手段には、前記第２のブロック同士の相関が低いと判定された場合、前記第１のブロックに含まれる前記第２のブロックと、前記第１のブロックの周囲に隣接して位置する前記第３のブロックとの画素の画素値を、前記生成用データに決定し、その生成用データから直交変換の基底を生成させることができる（例えば、図６のステップＳ１１５）。
【００２２】
前記判定手段には、前記第１のブロックを構成する前記第２のブロックの画素の画素値から算出される、その第２のブロック同士の相関を表す相関判定特徴量と、予め設定された所定の閾値とを比較することで、前記第２のブロック同士の相関を判定させることができる（例えば、図６のステップＳ１１４）。
【００２３】
本発明の一側面の符号化方法は、データを符号化する符号化装置の符号化方法であって、前記データを第１のブロックに分割し（例えば、図６のステップＳ１１２）、前記第１のブロックのそれぞれを、前記第１のブロックよりデータ数の少ない第２のブロックに分割し（例えば、図６のステップＳ１１３）、前記第１のブロック毎に、前記第１のブロックを構成する前記第２のブロック同士の相関を判定し（例えば、図６のステップＳ１１４）、前記第２のブロック同士の相関の判定の結果に応じて、前記第２のブロックの直交変換の基底の生成に用いる生成用データを決定し、その生成用データから直交変換の基底を生成し（例えば、図６のステップＳ１１５）、直交変換の前記基底を用いて、前記データを直交変換するステップ（例えば、図６のステップＳ１１６）を含む。
【００２４】
以下、本発明の実施の形態について図を参照して説明する。
【００２５】
図１は、本発明を適用した符号化装置の一実施の形態の構成例を示すブロック図である。
【００２６】
図１の符号化装置１１は、例えば、図示せぬ再生装置等から入力された画像データを符号化対象として符号化し、その符号化によって得られる符号化データを、例えば、図示せぬ記録装置等に出力する。
【００２７】
図１の符号化装置１１は、入力部３１、大ブロック化部３２、小ブロック化部３３、小ブロック相関判定部３４、直交変換基底生成部３５、直交変換部３６、量子化部３７、符号割当部３８、多重化部３９、および出力部４０から構成される。
【００２８】
入力部３１には、例えば、再生装置からの符号化対象の入力データとしての入力画像データVinが、例えば１フレーム単位で入力される。入力部３１に入力された１フレームの入力画像データVinは、大ブロック化部３２、直交変換基底生成部３５、および直交変換部３６に供給される。
【００２９】
大ブロック化部３２は、入力部３１から供給された入力画像データVinを所定の大きさの大ブロックに分割し、小ブロック化部３３に供給する。
【００３０】
小ブロック化部３３は、大ブロック化部３２から供給された大ブロックのそれぞれを、Ｎ個の画素からなるＭ個の小ブロックに分割し、小ブロック相関判定部３４に供給する。
【００３１】
小ブロック相関判定部３４は、小ブロック化部３３から供給された小ブロック同士の相関を、大ブロック毎に判定し、その相関の判定結果を直交変換基底生成部３５に供給する。
【００３２】
より具体的には、小ブロック相関判定部３４は、大ブロックを構成する小ブロックの画素の画素値から、大ブロック毎の小ブロック同士の相関を表す相関判定特徴量を算出する。小ブロック相関判定部３４は、相関判定特徴量と予め設定された所定の閾値とを比較し、相関判定特徴量が閾値より小さい（または、以下である）場合、小ブロック同士の相関が高いと判定し、小ブロック同士の相関が高いことを示す判定結果を直交変換基底生成部３５に供給する。また、小ブロック相関判定部３４は、相関判定特徴量が閾値以上である（または、より大きい）場合、小ブロック同士の相関が低いと判定し、小ブロック同士の相関が低いことを示す判定結果を直交変換基底生成部３５に供給する。
【００３３】
例えば、１つの大ブロックを構成する小ブロックの数をＭと、１つの小ブロックを構成する画素の画素数をＮと、大ブロックを構成する小ブロックのうちの、ｉ個目の小ブロックを構成するｊ番目の画素の画素値をｘijと、それぞれ表すこととすると、小ブロック相関判定部３４は、例えば、式（１）にしたがって、相関判定特徴量ｒを求める。
【００３４】
【数１】
2008312082.tif 000003
【００３５】
なお、式（１）において、ｍjは、小ブロックを構成するｊ番目の画素の画素値ｘijの、大ブロックを構成するＭ個の小ブロックについての平均値を表し、式（２）で表される。
【００３６】
【数２】
2008312082.tif 000004
【００３７】
なお、相関判定特徴量ｒは、小ブロック同士の輝度値（直流成分）の影響を除くために、例えば、式（３）に従って求めることもできる。
【００３８】
【数３】
2008312082.tif 000005
【００３９】
式（３）において、Ｌiはｉ個目の小ブロックにおける画素値の平均値を表し、式（４）で表される。
【００４０】
【数４】
2008312082.tif 000006
【００４１】
また、式（３）において、ｍLjは、小ブロックのｊ番目の画素の画素値の偏差の、大ブロックを構成するＭ個の小ブロックについての平均値を表し、式（５）で表される。
【００４２】
【数５】
2008312082.tif 000007
【００４３】
直交変換基底生成部３５は、小ブロック相関判定部３４における小ブロック同士の相関の判定結果に応じて、直交変換の基底の生成に用いる小ブロックを、大ブロック毎に決定する。さらに、直交変換基底生成部３５は、入力部３１から供給される入力画像データVinのうちの、大ブロックについて決定した小ブロックを用いて、その大ブロックについての直交変換の基底を生成し、その基底を表す直交変換基底データVcdcを、直交変換部３６および多重化部３９に供給する。
【００４４】
例えば、ある大ブロックを注目大ブロックとして注目すると、直交変換基底生成部３５は、小ブロック相関判定部３４から、注目大ブロックを構成する小ブロック同士の相関が高いことを示す判定結果が供給された場合、注目大ブロックを構成する小ブロックのみを、基底の生成に用いる小ブロック（以下、適宜、生成用ブロックという）に決定し、その生成用ブロックの分散共分散行列Ｓを生成する。さらに、直交変換基底生成部３５は、分散共分散行列Ｓの固有値および固有ベクトルを算出し、その固有値および固有ベクトルを用いて、注目大ブロックについての直交変換の基底を生成する。
【００４５】
ここで、小ブロックについて分散共分散行列Ｓの、第ａ行第ｂ列の要素をＳabと表すこととすると、直交変換基底生成部３５は、式（６）で表される分散共分散行列Ｓを生成する。
【００４６】
【数６】
2008312082.tif 000008
【００４７】
式（６）において、サフィックスａとｂは、１乃至Ｎのいずれかの値をとる。また、式（６）において、要素Ｓabは、式（７）で表される。
【００４８】
【数７】
2008312082.tif 000009
【００４９】
式（７）において、Ｍは、直交変換の基底を求めるのに用いられる小ブロックの数を表し、ｍa（ｍb）は、Ｍ個の小ブロックの画素値ｘia（ｘib）の平均値を表す。
【００５０】
そして、直交変換基底生成部３５は、式（６）で示される分散共分散行列Ｓの固有ベクトルｅ1＝（ｅ11，ｅ12，・・・，ｅ1N），ｅ2＝（ｅ21，ｅ22，・・・，ｅ2N），・・・，ｅN＝（ｅN1，ｅN2，・・・，ｅNN）を算出することで、式（８）で示される直交変換の基底（の行列）Ｅを生成する。なお、直交変換基底生成部３５で生成される直交変換の基底は、KL変換において生成される直交変換の基底と同様のものである。
【００５１】
【数８】
2008312082.tif 000010
【００５２】
ここで、注目大ブロックを構成する小ブロックを構成する画素の画素値ｘ1，ｘ2，…，ｘNの、行列Ｅによる直交変換後の画素値ｘ'1，ｘ'2，・・・，ｘ'Nは、式（９）で表される。
【００５３】
【数９】
2008312082.tif 000011
【００５４】
また、直交変換基底生成部３５は、小ブロック相関判定部３４から、注目大ブロックを構成する小ブロック同士の相関が低いことを示す判定結果が供給された場合、注目大ブロックを構成する小ブロックと、その小ブロックの近傍に位置し、かつ注目大ブロックを構成する小ブロックとは異なる他の小ブロックとを、生成用ブロックに決定し、その生成用ブロックを用いて、小ブロック同士の相関が高い場合と同様に、注目大ブロックについての直交変換の基底を生成する。
【００５５】
直交変換部３６は、直交変換基底生成部３５から供給された直交変換基底データVcdcで表される大ブロックについての直交変換の基底を用いて、入力部３１からの入力画像データVinの注目大ブロックを構成する小ブロックの直交変換を行い、その直交変換によって得られた変換係数を量子化部３７に供給する。
【００５６】
量子化部３７は、直交変換部３６から供給された変換係数の量子化を行う。より具体的には、量子化部３７は、直交変換部３６からの変換係数を所定の量子化テーブルで除算し、符号割当部３８に供給する。
【００５７】
符号割当部３８は、量子化部３７からの変換係数（量子化後の変換係数）（変換係数の量子化値）をエントロピー符号化する。すなわち、符号割当部３８は、量子化部３７からの変換係数のうちの、電力集中度の最も高い変換係数については、隣接するデータ群から得られた変換係数どうしの差分を算出し、その差分に対して、ハフマン符号化等による符号の割当を行う。また、符号割当部３８は、その他の変換係数については、電力集中度の高い順に、ゼロの数とゼロ以外の数とを組にし、その組に対して、２次元のハフマン符号化等による符号の割当を行う。符号割当部３８は、符号の割当により得られるエントロピー符号Vcdoを、多重化部３９に供給する。
【００５８】
多重化部３９は、直交変換基底生成部３５から供給された直交変換基底データVcdcと、符号割当部３８から供給されたエントロピー符号Vcdo（直交変換基底生成部３５からの直交変換基底データVcdcが表す基底を用いての直交変換によって得られた変換係数のエントロピー符号Vcdo）とを多重化し、その結果得られる符号化データVcdを出力部４０に供給する。
【００５９】
出力部４０は、多重化部３９から供給された符号化データVcdを、例えば、記録装置に出力する。
【００６０】
図２は、図１の大ブロック化部３２が出力する大ブロックを示す図である。
【００６１】
例えば、大ブロック化部３２においては、入力画像データVinが、例えば図２に示されるように、水平方向に６４画素分で垂直方向に６４画素分の大きさの大ブロックに分割される。なお、以下、水平方向にｈ画素分で垂直方向にｖ画素分の大きさを、（ｈ×ｖ）画素の大きさと称することとすると、図２の例では、大ブロックは、（６４×６４）画素の大きさとされている。
【００６２】
ここで、大ブロックの大きさは、（６４×６４）画素の大きさに限定されるものではない。
【００６３】
図３は、図１の小ブロック化部３３が出力する小ブロックを示す図である。
【００６４】
例えば、図２における（６４×６４）画素の大きさの大ブロックが、大ブロック化部３２から小ブロック化部３３に供給された場合には、小ブロック化部３３は、図３に示されるように、その１つの大ブロックを、（８×８）画素の大きさの６４個の小ブロックに分割する。
【００６５】
ここで、小ブロックの大きさは、（８×８）画素の大きさに限定されるものではない。
【００６６】
次に、図４および図５を参照して、図１の小ブロック相関判定部３４で決定される、基底の生成に用いられる小ブロック（生成用ブロック）について説明する。
【００６７】
図４は、注目大ブロックを構成する小ブロック同士の相関が低いと判定された場合に、生成用ブロックに決定される小ブロックの第１の例を示している。
【００６８】
直交変換基底生成部３５は、例えば、図４において太線で示されるように、注目大ブロックを構成する小ブロックを水平方向に、例えば４画素分ずらした位置の小ブロックであって、注目大ブロック内にある５６個の小ブロックを他の小ブロックとして、その５６個の小ブロックと、注目大ブロックを構成する６４個の小ブロックとを、生成用ブロックに決定する。
【００６９】
なお、他の小ブロックとしては、注目大ブロックを構成する小ブロックを、水平方向以外の、任意の方向にずらした位置の小ブロックであって、注目大ブロック内にある小ブロックを採用することができる。また、他の小ブロックとしては、注目大ブロック内の小ブロックに限らず、注目大ブロックの外側と内側とに跨った位置の小ブロックを採用することもできる。
【００７０】
図５は、注目大ブロックを構成する小ブロック同士の相関が低いと判定された場合に、生成用ブロックに決定される小ブロックの第２の例を示している。
【００７１】
直交変換基底生成部３５は、例えば、図５に示されるように、注目大ブロックの周囲に隣接して位置する３６個の小ブロックと、注目大ブロックを構成する６４個の小ブロックとの、合計で１００個の小ブロックを、生成用ブロックに決定する。
【００７２】
以上のように、直交変換基底生成部３５は、注目大ブロックを構成する小ブロック同士の相関が低い場合には、その注目大ブロックを構成する小ブロックの他、他の小ブロックをも、生成用ブロックに決定し、その生成用ブロック、すなわち、注目大ブロックを構成する小ブロック同士の相関が高い場合に生成用ブロックに決定される小ブロックよりも多数の小ブロックを用いて、注目大ブロックの直交変換に用いる基底を生成する。
【００７３】
ここで、一般に、より多くの画素の画素値を用いて、KL変換の基底を生成すると、そのKL変換の基底は、多くの種類の画像に対して、人間の視覚にとって影響のない変換を行うことができる。そのKL変換の基底は、DCTの基底に近づくことが知られている。
【００７４】
したがって、注目大ブロックを構成する小ブロックのKL変換に用いる基底を、その注目大ブロックを構成する小ブロックの他、他の小ブロックをも用いて生成することにより、その基底は、DCTの基底に近づくことになる。
【００７５】
ただし、KL変換の対象となる注目大ブロックの小ブロックとは全く関係のない小ブロックを用いて基底を生成した場合、その基底は、注目大ブロックの小ブロックにとって効率の悪いKL変換を行うものとなるおそれがある。
【００７６】
そこで、直交変換基底生成部３５は、注目大ブロックの小ブロックとの相関が比較的ある、その小ブロックの近傍に位置する他の小ブロック、すなわち、具体的には、図４および図５に示すような、注目大ブロックの小ブロックと重複する小ブロックや、注目大ブロックの周囲に隣接する小ブロックなどの、注目大ブロックを構成する小ブロックとの間の相関が高い小ブロックをも用いて、注目大ブロックを構成する小ブロックのKL変換に用いる基底を生成することにより、DCTの基底に近づきつつ、かつ、KL変換の効率を低下させない基底を得る。
【００７７】
次に、図６のフローチャートを参照して、図１の符号化装置１１の符号化処理について説明する。
【００７８】
ステップＳ１１１において、入力部３１に、例えば、１フレームの入力画像データVinが入力され、その１フレームの入力画像データVinは、入力部３１から、大ブロック化部３２、直交変換基底生成部３５、および直交変換部３６に供給される。
【００７９】
その後、処理はステップＳ１１１からステップＳ１１２に進み、大ブロック化部３２は、入力部３１から供給された入力画像データVinを大ブロックに分割し、小ブロック化部３３に供給し、処理はステップＳ１１３に進む。
【００８０】
ステップＳ１１３において、小ブロック化部３３は、大ブロック化部３２から供給された大ブロックのうちの、まだ、注目大ブロックとしていない大ブロックの１つを注目大ブロックとして、その注目大ブロックを小ブロックに分割し、小ブロック相関判定部３４に供給し、処理はステップＳ１１４に進む。
【００８１】
ステップＳ１１４において、小ブロック相関判定部３４は、小ブロック化部３３から供給された、注目大ブロックを構成する小ブロック同士の相関を判定し、その相関の判定結果を直交変換基底生成部３５に供給し、処理はステップＳ１１５に進む。
【００８２】
ステップＳ１１５において、直交変換基底生成部３５は、小ブロック相関判定部３４における小ブロック同士の相関の判定結果に応じて、注目大ブロックを構成する小ブロックの直交変換の基底の生成に用いる小ブロック（生成用ブロック）を決定し、その小ブロックを用いて、直交変換の基底を生成する。直交変換基底生成部３５は、その基底を表す直交変換基底データVcdcを、直交変換部３６および多重化部３９に供給し、処理はステップＳ１１６に進む。
【００８３】
ステップＳ１１６において、直交変換部３６は、入力部３１からの１フレームの入力画像データVinのうちの、注目大ブロックを構成する小ブロック（の画素の画素値（ｘ1，ｘ2，…，ｘN））を、直交変換基底生成部３５から供給された直交変換の基底（直交変換基底データVcdc）を用い、式（９）にしたがって直交変換する。そして、直交変換部３６は、直交変換によって得られた変換係数を、量子化部３７に供給して、処理は、ステップＳ１１６からステップＳ１１７に進む。
【００８４】
ステップＳ１１７において、量子化部３７は、直交変換部３６から供給された変換係数を量子化し、符号割当部３８に供給して、処理はステップＳ１１８に進む。
【００８５】
ここで、ステップＳ１１６およびステップＳ１１７では、例えば、MPEG（Moving Picture Experts Group）符号化で行われるDCTおよび量子化と同様に、直交変換および量子化が行われる。
【００８６】
ステップＳ１１８において、符号割当部３８は、量子化部３７からの変換係数を対象に、ハフマン符号化等のエントロピー符号化を行い、その結果得られるエントロピー符号Vcdoを、多重化部３９に供給して、処理はステップＳ１１９に進む。
【００８７】
ステップＳ１１９において、多重化部３９は、直交変換基底生成部３５から供給された直交変換基底データVcdcと、符号割当部３８から供給されたエントロピー符号Vcdoとを多重化することにより、符号化データVcdを生成し、出力部４０に供給して、処理はステップＳ１２０に進む。
【００８８】
ステップＳ１２０において、出力部４０は、多重化部３９から供給された符号化データVcdを、記録装置に出力して、処理はステップＳ１２１に進む。
【００８９】
ステップＳ１２１において、小ブロック化部３３は、大ブロック化部３２からの入力画像データVinを構成する大ブロックの全てを注目大ブロックとして、処理を行ったか否かを判定する。
【００９０】
ステップＳ１２１において、大ブロック化部３２からの入力画像データVinを構成する大ブロックの全てを、まだ、注目大ブロックとしていないと判定された場合、処理はステップＳ１１３に戻り、小ブロック化部３３は、大ブロック化部３２からの入力画像データVinを構成する大ブロックのうちの、まだ、注目大ブロックとしていない大ブロックの１つを、新たに、注目大ブロックとして、以下、同様の処理を繰り返す。
【００９１】
一方、ステップＳ１２１において、大ブロック化部３２からの入力画像データVinを構成する大ブロックの全てを、注目大ブロックとしたと判定された場合、符号化処理は終了する。
【００９２】
なお、図６の符号化処理は、入力部３１に１フレームの入力画像データVinが入力される毎に行われる。
【００９３】
図７は、図１の符号化装置１１が出力する符号化データVcdを復号する復号装置の構成例を示すブロック図である。
【００９４】
図７の復号装置５１は、入力部７１、データ分解部７２、復号部７３、逆量子化部７４、逆直交変換部７５、ブロック分解部７６、および出力部７７から構成され、図１の符号化装置１１が出力する符号化データVcdを、復号対象として復号し、例えば、図示せぬ表示装置等に出力する。
【００９５】
入力部７１には、例えば、図示せぬ記録装置から供給される、符号化装置１１が出力した符号化データVcdが入力される。入力部７１に入力された符号化データVcdは、データ分解部７２に供給される。
【００９６】
データ分解部７２は、入力部７１から供給された符号化データVcdを、大ブロックについてのエントロピー符号Vcdoと直交変換基底データVcdcとに分解し、それぞれ復号部７３と逆直交変換部７５とに供給する。
【００９７】
復号部７３は、データ分解部７２から供給されたエントロピー符号Vcdoの復号を行う。例えば、復号部７３は、図１の符号割当部３８における符号の割当に対応するハフマン復号等を行う。復号部７３は、復号の結果得られる、変換係数の量子化値（量子化後の変換係数）を逆量子化部７４に供給する。
【００９８】
逆量子化部７４は、復号部７３から供給された、変換係数の量子化値を、図１の量子化部３７において用いられた量子化テーブルに対応する逆量子化テーブルを用いて逆量子化する。逆量子化部７４は、逆量子化によって得られる変換係数を逆直交変換部７５に供給する。
【００９９】
逆直交変換部７５は、データ分解部７２から供給された直交変換基底データVcdcで表される直交変換の基底を用いて、逆量子化部７４から供給された変換係数を逆直交変換し、これにより、大ブロックを構成する小ブロックを得て、ブロック分解部７６に供給する。
【０１００】
ブロック分解部７６は、逆直交変換部７５から１フレーム分の大ブロックを構成する小ブロックが供給されるのを待って、その１フレーム分の小ブロックから、１フレームの復号画像データVoutを構成し、出力部７７に供給する。
【０１０１】
出力部７７は、ブロック分解部７６から供給された復号画像データVoutを、例えば、表示装置に出力する。
【０１０２】
次に、図８のフローチャートを参照して、図７の復号装置５１の復号処理について説明する。
【０１０３】
入力部７１には、大ブロックの単位で、符号化データVcdが供給され、その符号化データVcdは、入力部３１からデータ分解部７２に供給される。
【０１０４】
データ分解部７２は、ステップＳ１３１において、入力部７１からの大ブロックについての符号化データVcdを、エントロピー符号Vcdoと直交変換基底データVcdcとに分解し、エントロピー符号Vcdoを復号部７３に供給するとともに、直交変換基底データVcdcを逆直交変換部７５に供給して、処理はステップＳ１３２に進む。
【０１０５】
ステップＳ１３２では、復号部７３が、データ分解部７２からのエントロピー符号Vcdoを、変換係数の量子化値に復号し、逆量子化部７４に供給して、処理はステップＳ１３３に進む。
【０１０６】
ステップＳ１３３では、逆量子化部７４が、復号部７３からの変換係数の量子化値を逆量子化し、その結果得られる、大ブロックを構成する小ブロックの変換係数を、逆直交変換部７５に供給して、処理はステップＳ１３４に進む。
【０１０７】
ステップＳ１３４では、逆直交変換部７５が、逆量子化部７４からの大ブロックを構成する小ブロックの変換係数を、データ分解部７２からの直交変換基底データVcdcが表す基底を用いて、逆直交変換し、その結果得られる、大ブロックを構成する小ブロック（の画素値）を、ブロック分解部７６に供給し、処理はステップＳ１３５に進む。
【０１０８】
ステップＳ１３５では、ブロック分解部７６が、１フレーム分の大ブロックを構成する小ブロックが、逆直交変換部７５から供給されたか否かを判定する。
【０１０９】
ステップＳ１３５において、１フレーム分の大ブロックを構成する小ブロックが、逆直交変換部７５からブロック分解部７６に供給されていないと判定された場合、入力部７１からデータ分解部７２に対して、大ブロックについての符号化データVcdが新たに供給されるのを待って、処理は、ステップＳ１３１に戻り、その新たに供給された符号化データVcdを対象として、以下、同様の処理が繰り返される。
【０１１０】
また、ステップＳ１３５において、１フレーム分の大ブロックを構成する小ブロックが、逆直交変換部７５からブロック分解部７６に供給されたと判定された場合、処理はステップＳ１３６に進み、ブロック分解部７６は、逆直交変換部７５からの、１フレーム分の大ブロックを構成する小ブロックを用いて、１フレームの復号画像データVoutを構成して、出力部７７を介して出力し、処理はステップＳ１３７に進む。
【０１１１】
ステップＳ１３７では、データ分解部７２が、まだ、復号すべき符号化データVcdがあるか否かを判定する。
【０１１２】
ステップＳ１３７において、復号すべき符号化データVcdがあると判定された場合、すなわち、入力部７１からデータ分解部７２に対して、大ブロックについての符号化データVcdが新たに供給された場合、処理は、ステップＳ１３１に戻り、その新たに供給された符号化データVcdを対象として、以下、同様の処理が繰り返される。
【０１１３】
また、ステップＳ１３７において、復号すべき符号化データVcdがないと判定された場合、すなわち、入力部７１からデータ分解部７２に対して、大ブロックについての符号化データVcdが供給されてこない場合、復号処理は終了する。
【０１１４】
以上のように、符号化装置１１では、入力画像データVinを大ブロックに分割し、大ブロックのそれぞれを、大ブロックよりデータ数の少ない小ブロックに分割し、大ブロック毎に、大ブロックを構成する小ブロック同士の相関を判定し、小ブロック同士の相関の判定の結果に応じて、小ブロックの直交変換の基底の生成に用いるデータを決定し、そのデータから直交変換の基底を生成し、直交変換の基底を用いて、データを直交変換するので、例えば、小ブロック同士の相関が低い場合には、大ブロックを構成する小ブロックのKL変換に用いる基底を、その大ブロックを構成する小ブロックの他、その小ブロックの近傍の他の小ブロックをも用いて生成することができ、その結果、DCTの基底に近い基底を得て、人間にとって良好な品質の復号結果を得ることができ、かつ、効率が良いKL変換およびその逆変換を行うことができる。
【０１１５】
なお、以上においては、直交変換としてKL変換を用いたが、KL変換に限らず、変換の対象を用いて基底を生成する変換（直交変換）を用いることができる。
【０１１６】
また、以上においては、画像データを符号化対象（復号対象）とする例について説明したが、符号化対象としては、画像データに限らず、例えば、音声データ等、非可逆圧縮が許されるデータを採用することが可能である。
【０１１７】
さらに、大ブロックは、空間方向に並ぶ画素ではなく、時間方向に並ぶ画素から構成されることが可能である。小ブロックについても、同様である。
【０１１８】
また、生成用ブロックとなる他の小ブロックとしては、大ブロックを構成する小ブロックに対して、空間方向の近傍にある小ブロックの他、時間方向の近傍にある小ブロックを採用することが可能である。
【０１１９】
上述した符号化処理などの一連の処理は、ハードウェアにより実行することもできるし、ソフトウェアにより実行することもできる。一連の処理をソフトウェアにより実行する場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、プログラム記録媒体からインストールされる。
【０１２０】
図９は、上述した一連の処理をプログラムにより実行するコンピュータのハードウェアの構成例を示すブロック図である。
【０１２１】
コンピュータにおいて、CPU（Central Processing Unit）２０１，ROM（Read Only Memory）２０２，RAM（Random Access Memory）２０３は、バス２０４により相互に接続されている。
【０１２２】
バス２０４には、さらに、入出力インターフェース２０５が接続されている。入出力インターフェース２０５には、キーボード、マウス、マイクロホンなどよりなる入力部２０６、ディスプレイ、スピーカなどよりなる出力部２０７、ハードディスクや不揮発性のメモリなどよりなる記憶部２０８、ネットワークインタフェースなどよりなる通信部２０９、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア２１１を駆動するドライブ２１０が接続されている。
【０１２３】
以上のように構成されるコンピュータでは、CPU２０１が、例えば、記憶部２０８に記憶されているプログラムを、入出力インターフェース２０５およびバス２０４を介して、RAM２０３にロードして実行することにより、上述した一連の処理が行われる。
【０１２４】
コンピュータ（CPU２０１）が実行するプログラムは、例えば、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory),DVD(Digital Versatile Disc)など）、光磁気ディスク、もしくは半導体メモリなどよりなるパッケージメディアであるリムーバブルメディア２１１に記録して、あるいは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供される。
【０１２５】
そして、プログラムは、リムーバブルメディア２１１をドライブ２１０に装着することにより、入出力インターフェース２０５を介して、記憶部２０８にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部２０９で受信し、記憶部２０８にインストールすることができる。その他、プログラムは、ROM２０２や記憶部２０８に、あらかじめインストールしておくことができる。
【０１２６】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０１２７】
また、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【図面の簡単な説明】
【０１２８】
【図１】本発明を適用した符号化装置の一実施の形態の構成例を示すブロック図である。
【図２】大ブロック化部が出力する大ブロックを示す図である。
【図３】小ブロック化部が出力する小ブロックを示す図である。
【図４】基底の生成に用いられる生成用ブロックの例を説明する図である。
【図５】基底の生成に用いられる生成用ブロックの他の例を説明する図である。
【図６】符号化処理を説明するフローチャートである。
【図７】復号装置の構成例を示すブロック図である。
【図８】復号処理を説明するフローチャートである。
【図９】本発明が適用される符号化装置として機能するコンピュータのハードウェアの構成例を示すブロック図である。
【符号の説明】
【０１２９】
１１  符号化装置，  ３１  入力部，  ３２  大ブロック化部，  ３３  小ブロック化部，  ３４  小ブロック相関判定部，  ３５  直交変換基底生成部，  ３６  直交変換部，  ３７  量子化部，  ３８  符号割当部，  ３９  多重化部，  ４０  出力部，  ５１  復号装置，  ７１  入力部，  ７２  データ分解部，  ７３  復号部，  ７４  逆量子化部，  ７５  逆直交変換部，  ７６  ブロック分解部，  ７７  出力部，  ２０１  CPU，  ２０２  ROM，  ２０３  RAM，  ２０８  記憶部，  ２１１  リムーバブルメディア
【図１】
2008312082.tif 000012
【図２】
2008312082.tif 000013
【図３】
2008312082.tif 000014
【図４】
2008312082.tif 000015
【図５】
2008312082.tif 000016
【図６】
2008312082.tif 000017
【図７】
2008312082.tif 000018
【図８】
2008312082.tif 000019
【図９】
2008312082.tif 000020