(57)【特許請求の範囲】
【請求項１】
画像データをＢ画素毎にブロック分割して各ブロック平均値からなるＤＣ画像を生成し、該ＤＣ画像の一部を抽出した各ＤＣ画素の下位ｎ（ｎ＝log2Ｂ）ビットを０にしてＤＣネストとするステップと、
符号対象の画素ブロックからそのブロック平均値を分離した後の残差ベクトルの大きさが所定の許容値を超えると判定した場合に、前記ＤＣネストより順次基底候補ブロックを抽出し、該ブロックからブロック平均値を分離して基底候補ベクトルを生成し、該基底候補ベクトルを使用した適応的直交変換処理により前記残差ベクトルを許容値以下に近似するための１又は２以上の基底ベクトルを求めるステップと、
を備えることを特徴とする画像符号方法。
【請求項２】
画像データをＢ画素毎にブロック分割して各ブロック平均値からなるＤＣ画像を生成し、その一部をＤＣネストとするステップと、
符号対象の画素ブロックからそのブロック平均値を分離した後の残差ベクトルの大きさが所定の許容値を超えると判定した場合に、前記ＤＣネストより順次基底候補ブロックを抽出し、該ブロックを構成する各ＤＣ画素の下位ｎ（ｎ＝log2Ｂ）ビットを０にしてからそのブロック平均値を分離して基底候補ベクトルを生成し、該基底候補ベクトルを使用した適応的直交変換処理により前記残差ベクトルを許容値以下に近似するための１又は２以上の基底ベクトルを求めるステップと、
を備えることを特徴とする画像符号方法。
【請求項３】
適応的直交変換処理は  ＤＣネストを使用して最初の残差ベクトル〈ｄ〉との差の大きさを最小とするための第１基底ベクトル〈ｕ１〉を探査する処理を含み、該処理は、ＤＣネストから順次抽出した基底候補ベクトルを〈ｕｉ〉とするときに、
ｈi＝〈ｄ・ｕi〉2／‖ｕi‖2
を最大とする前記基底候補ベクトル〈ｕｉ〉を第１基底ベクトル〈ｕ１〉として抽出するステップと、
該第１基底ベクトル〈ｕ1〉をその大きさで正規化して第１正規化基底ベクトル〈ｖ1〉となし、これを保持するステップと、
第１スカラー係数α1を残差ベクトル〈ｄ〉の第１正規化基底ベクトル〈ｖ1〉への射影分として求め、これを保持するステップと、
を備えることを特徴とする請求項１又は２に記載の画像符号方法。
【請求項４】
適応的直交変換処理は  最初の残差ベクトル〈ｄ〉を第１スカラー係数α1と第１正規化基底ベクトル〈ｖ1〉とのスカラー積α１〈ｖ１〉により近似した後の
第１残差ベクトル〈ｄ１〉が所定の許容値を超えると判定した場合に、ＤＣネストを使用して第１残差ベクトル〈ｄ１〉との差の大きさを最小とするための第２基底ベクトル〈ｕ２〉を探査する処理を含み、該処理は、ＤＣネストから順次抽出した基底候補ベクトルを〈ｕｉ〉とするときに、
ｈi＝｛〈ｄ・ｕi〉−（〈ｄ・ｕ1〉〈ｕ1・ｕi〉）／‖ｕ1‖2｝2
／｛‖ｕi‖2−（〈ｕ1・ｕi〉）／‖ｕ1‖）2｝
を最大とする前記基底候補ベクトル〈ｕｉ〉を第２基底ベクトル〈ｕ２〉として抽出するステップと、
該第２基底ベクトル〈ｕ２〉を正規化及び第１正規化基底ベクトル〈ｖ1〉に直交化して第２正規化基底ベクトル〈ｖ２〉となし、これを保持するステップと、
第２スカラー係数α２を第１残差ベクトル〈ｄ１〉の第２正規化基底ベクトル〈ｖ２〉への射影分として求め、これを保持するステップと、
を備えることを特徴とする請求項３に記載の画像符号方法。
【請求項５】
適応的直交変換処理は  第１残差ベクトル〈ｄ１〉を第２スカラー係数α２と第２正規化基底ベクトル〈ｖ２〉とのスカラー積α2〈ｖ2〉により近似した後の第２残差ベクトル〈ｄ２〉が所定の許容値を超えると判定した場合に、ＤＣネストを使用して第２残差ベクトル〈ｄ２〉との差の大きさを最小とするための第３基底ベクトル〈ｕ３〉を探査する処理を含み、該処理は、ＤＣネストから順次抽出した基底候補ベクトルを〈ｕｉ〉とするときに、
ｈi＝
（〈ｄ・ｕi〉−〈ｄ・ｖ1〉〈ｖ1・ｕi〉−〈ｄ・ｖ2〉〈ｖ2・ｕi〉）2
／｛‖ｕi‖2−〈ｖ1・ｕi〉2−〈ｖ2・ｕi〉2｝
を最大とする前記基底候補ベクトル〈ｕｉ〉を第３基底ベクトル〈ｕ３〉として抽出するステップと、
該第３基底ベクトル〈ｕ３〉を正規化及び第１正規化基底ベクトル〈ｖ1〉と第２正規化基底ベクトル〈ｖ２〉とに直交化して第３正規化基底ベクトル〈ｖ３〉となし、これを保持するステップと、
第３スカラー係数α３を第２残差ベクトル〈ｄ２〉の第３正規化基底ベクトル〈ｖ３〉への射影分として求め、これを保存するステップと、
を備えることを特徴とする請求項４に記載の画像符号方法。
【請求項６】
適応的直交変換処理は  最初の残差ベクトル〈ｄ〉＝（d１,d２…，dｎ）との差の大きさを最小とする基底候補ベクトル〈ｕi〉＝（u１,u２,…，uｎ）を探査すべく両者の内積〈ｄ・ｕi〉を求める演算を含み、該演算は、基底候補ベクトル〈ｕi〉の任意要素（例えばｕｑ）を残りの要素の一次結合で置き換えると共に、残差ベクトル〈ｄ〉と基底候補ベクトル〈ｕi〉との内積〈ｄ・ｕi〉を、
〈ｄ・ｕi〉＝（ｄ1−ｄｑ）ｕ1＋（ｄ2−ｄｑ）ｕ2＋，
…，＋（ｄｎ−ｄｑ）ｕｎ
但し、（ｄｑ−ｄｑ）ｕｑの項を除く
の積和演算により求めることを特徴とする請求項３乃至５の何れか一つに記載の画像符号方法。
【請求項７】
ｍ個のスカラー係数αk(ｋ＝１〜ｍ）とｍ個の正規化基底ベクトル〈ｖk〉(ｋ＝１〜ｍ）とからなる正規直交基底系の組をｍ個のスカラー展開計数βk(ｋ＝１〜ｍ）と前記各正規化基底ベクトルの元となったｍ個の基底候補ベクトル〈ｕk〉(ｋ＝１〜ｍ）とからなる非直交基底系の組に変換するステップと、
該変換したｍ個のスカラー展開計数βkと、ＤＣネストからｍ個の基底候補ベクトル〈ｕk〉を抽出するための抽出情報とからなる組と、ＤＣ画像とをそれぞれ符号化して符号データを出力するステップと、
を更に備えることを特徴とする請求項３乃至５の何れか一つに記載の画像符号方法。
【請求項８】
ｍ個のスカラー展開係数β1〜βｍのノルムをその大きさ順に並べ替え、０を含む隣接ノルム間の各差分を求め、得られた各差分につき所定ビット数の下位ビットを除く残りの上位ビットにハフマン符号化を適用することを特徴とする請求項７に記載の画像符号方法。
【請求項９】
適応的直交変換処理で求めた基底ベクトルの数が所定以上の場合は、基底系の符号化に代えて、符号対象ブロックの画像データそのものを符号化することを特徴とする請求項１，２又は５に記載の画像符号方法。
【請求項１０】
請求項７に記載の符号データからＢ画素毎の各ブロック平均値に相当するＤＣ画像を再生し、該ＤＣ画像の一部を抽出した各ＤＣ画素の下位ｎ（ｎ＝log2Ｂ）ビットを０にしてＤＣネストとするステップと、
前記符号データからｍ個のスカラー展開計数と、ｍ個の抽出情報とからなる組を復号するステップと、
ターゲットブロックに対するｍ個のスカラー展開計数と、ｍ個の抽出情報によりＤＣネストから抽出した各基底候補ブロックとのスカラー積βk〈Ｕk〉(ｋ＝１〜ｍ）を生成してこれらをブロック毎に累積加算すると共に、該加算結果からそのブロック平均値を分離して残差ベクトル〈ｄｊ〉を生成し、これをターゲットブロックのＤＣ値に合成して画像データを再生するステップと、
を備えることを特徴とする画像復号方法。
【請求項１１】
請求項７に記載の符号データからＢ画素毎の各ブロック平均値に相当するＤＣ画像を再生し、その一部をＤＣネストとするステップと、
前記符号データからｍ個のスカラー展開計数と、ｍ個の抽出情報とからなる組を復号するステップと、
ターゲットブロックに対するｍ個のスカラー展開計数βk(ｋ＝１〜ｍ）と、ｍ個の抽出情報によりＤＣネストから抽出した各基底候補ブロック〈Ｕk〉(ｋ＝１〜ｍ）につき各ＤＣ画素の下位ｎ（ｎ＝log2Ｂ）ビットを０にしたもの、とのスカラー積βk〈Ｕk〉(ｋ＝１〜ｍ）を生成してこれらをブロック毎に累積加算すると共に、該加算結果からそのブロック平均値を分離して残差ベクトル〈ｄｊ〉を生成し、これをターゲットブロックのＤＣ値に合成して画像データを再生するステップと、
を備えることを特徴とする画像復号方法。
【請求項１２】
画像データをＢ画素毎にブロック分割して各ブロック平均値からなるＤＣ画像を生成すると共に、該ＤＣ画像の一部を抽出した各ＤＣ画素の下位ｎ（ｎ＝log2Ｂ）ビットを０にしてＤＣネストを生成し、メモリに記憶するＤＣネスト生成手段と、
符号対象の画素ブロックからそのブロック平均値を分離した後の残差ベクトルの大きさが所定の許容値を超えると判定した場合に、前記ＤＣネストより順次基底候補ブロックを抽出し、該ブロックからブロック平均値を分離して基底候補ベクトルを生成し、該基底候補ベクトルを使用した適応的直交変換処理により前記残差ベクトルを許容値以下に近似するための１又は２以上の基底ベクトルを求める演算手段と、
を備えることを特徴とする画像符号装置。
【請求項１３】
請求項７に記載の符号データからＢ画素毎の各ブロック平均値に相当するＤＣ画像を再生すると共に、該ＤＣ画像の一部を抽出した各ＤＣ画素の下位ｎ（ｎ＝log2Ｂ）ビットを０にしてＤＣネストを再生し、メモリに記憶するＤＣネスト再生手段と、
前記符号データからｍ個のスカラー展開計数と、ｍ個の抽出情報とからなる組を復号する復号手段と、
ターゲットブロックに対するｍ個のスカラー展開計数と、ｍ個の抽出情報によりＤＣネストから抽出した各基底候補ブロックとのスカラー積βk〈Ｕk〉(ｋ＝１〜ｍ）を生成してこれらをブロック毎に累積加算すると共に、該加算結果からそのブロック平均値を分離して残差ベクトル〈ｄｊ〉を生成し、これをターゲットブロックのＤＣ値に合成して画像データを再生する画像再生手段と、
を備えることを特徴とする画像復号装置。
【請求項１４】
請求項１乃至１１の何れか一つに記載の処理をコンピュータに実行させるためのプログラムを記録したコンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像符号／復号方法及びその装置並びにそのプログラムを記録した記録媒体に関し、更に詳しくはハイブリッドベクトル量子化（ＨＶＱ：Hybrid Vector Quantization)方式による画像符号／復号方法及びその装置並びにそのプログラムを記録した記録媒体に関する。
【０００２】
今日、静止画圧縮の国際標準であるＪＰＥＧ（Joint Photographic Expert Group)方式では、８×８の画素ブロックを２次元ＤＣＴによりＤＣ値及び基本〜６３倍周波数の各係数値に変換すると共に、自然画の周波数成分が低周波領域に集中していることを利用して画品質が低下しない範囲内で各係数値を異なる量子化幅で量子化し、情報量の削減を行ってからハフマン符号化を行っている。
【０００３】
これに対してＨＶＱ方式は、ＪＰＥＧと同様に平均値分離型ブロック符号化の一種であるが、ベクトル量子化と直交変換符号化の中間方式である適応的直交変換（ＡＯＴ：Adaptive Orthogonal Transform)をその圧縮原理としている。ここで、ＡＯＴはベクトル量子化のコードブックに相当する基底の巣（ネスト）から必要最少数の非直交基底系を選択し、対象ブロックを所望の許容誤差Ｚ以内に近似する方式である。ＨＶＱ方式では復号演算を整数型で行えるため、復号が高速である。またＪＰＥＧに特有なモスキート及びブロックノイズ、ＧＩＦに特有な擬似輪郭が発生しないため自然画像，人工画像（アニメーション画像，ＣＧ画像）を高画質で高圧縮できる。本発明はこのようなＨＶＱ方式における画質の更なる改善及び符号化演算の高速化に関する。
【０００４】
【従来の技術】
本件出願人は画像の自己相似性を利用したＨＶＱ方式による画像符号／復号方法を既に提案している（特願平１０-１８９２３９）。以下その内容を説明する。なお、本明細書を通して記号〈ａ〉はベクトルａ又はブロックａ、記号‖ａ‖はベクトルａの大きさ（ノルム）、記号〈ａ・ｂ〉はベクトルａ，ｂの内積を表す。また図や［数］中のベクトルやブロックを太文字で表す。
【０００５】
図１３は従来の画像符号装置（エンコーダ）のブロック図で、図において、１１は原画像データを記憶する原画像メモリ、１２は原画像データの各画素ブロック（４×４画素）につきブロック平均（ＤＣ）値を求めるＤＣ値生成部、１３は各ＤＣ値につき差分予測符号化を行う差分ＰＣＭ符号部（ＤＰＣＭ）、１４は差分ＰＣＭ符号から各ＤＣ値を復号する逆ＤＰＣＭ符号部（ＩＤＰＣＭ）、１５は復号ＤＣ画像を記憶するＤＣ画像メモリ、１６はＤＣ画像の一部から所定サイズのＤＣネストを切り出すＤＣネスト生成部、１７はＤＣネストを記憶するＤＣネストメモリである。
【０００６】
更に、１８は符号対象であるターゲット画像ブロック〈Ｒj〉から対応する復号ＤＣ値ＤＣJを分離する減算器、１９はＤＣ分離された残差ベクトル〈ｄj〉を記憶する残差ベクトルバッファ、２０はＤＣネストからダウンサンプルされた４×４画素の基底候補ブロック〈Ｕi〉を記憶する候補ブロックバッファ、２１は基底候補ブロック〈Ｕi〉のブロック平均値ａiを求める平均器、２２は基底候補ブロック〈Ｕi〉からブロック平均値ａiを分離する減算器、２３は平均値分離された基底候補ベクトル〈ｕi〉を記憶する候補ベクトルバッファ、２４は、残差ベクトルの二乗ノルム‖ｄj‖2が許容誤差Ｚを超える場合に、ＤＣネストを探索して残差ベクトル〈ｄj〉を許容誤差Ｚ以内に近似するための直交基底系αk〈ｕk'〉（ｋ＝1〜ｍ）を生成する適応的直交変換処理部（ＡＯＴ）、２５は生成された直交基底系αk〈ｕk'〉（ｋ＝1〜ｍ）につき、各対応する非直交基底ベクトル〈ｕk〉（ｋ＝1〜ｍ）に掛けて等価な非直交基底系βk〈ｕk〉（ｋ＝1〜ｍ）を生成するための展開係数βｋを求める係数変換部、２６は上記ＤＣ値のＤＰＣＭ符号や非直交基底系βk〈ｕk〉等の情報を更に圧縮符号化するためのハフマン，ランレングス，固定長符号等による符号部である。
【０００７】
ＤＣ値生成部１２は４×４画素のブロック平均値を求め、小数点以下を四捨五入（又は切り捨て等）する。ＤＰＣＭ１３は、図示しないが、Ｊ行，Ｉ列のＤＣ値をＤＣJ,I とする時に、該ＤＣJ,I の予測値ＤＣJ,I'を例えばＤＣJ,I'＝（ＤＣJ,I-1 ＋ＤＣJ-1,I ）／２により求め、その予測誤差ΔＤＣJ,I ＝ＤＣJ,I −ＤＣJ,I'を量子化係数Ｑ（Ｚ） により線形量子化して出力する。この量子化係数Ｑ（Ｚ）は許容誤差Ｚと対応付けられており、許容誤差Ｚに応じて１〜８の範囲で変化する。
【０００８】
ＤＣネスト生成部１６はＤＣ画像から例えば縦３９×横７１の領域をそのまま切り出（コピー）してＤＣネストとする。ＤＣネストはコードブックとして使用されるため、交流成分を多く含むものが望ましい。そこで、複数の候補領域につき、各領域内で隣り合うＤＣ値の差分をとってこれらの絶対値等の総和を求め、総和が最大となるような領域を切り出してＤＣネストとする。
【０００９】
また基底候補ブロック〈Ｕi〉のダウンサンプルは、縦横１ＤＣ値毎に頂点（ｐｘ，ｐｙ）∈［０，６３］×［０，３１］を設定し、かつそのサブサンプル間隔は（ｓｘ，ｓｙ）∈｛（１，１），（１，２），（２，１），（２，２）｝の計４種類とする。従って、トータルではＮ（＝８１９２）個の基底候補ブロック〈Ｕi〉が存在し、これらはＡＯＴ２４からのインデクスカウンタｉで参照される。以下、従来の適応的直交変換処理部２４の動作を説明する。
【００１０】
図１４は従来の適応的直交変換処理のフローチャート、図１５で該処理のイメージ図である。図１４において、残差ベクトルの二乗ノルム‖〈ｄj〉‖2＞Ｚであるとこの処理に入力する。ステップＳ１２１ではレジスタＥに残差ベクトルの二乗ノルム‖〈ｄj〉‖2をセットする。また基底数カウンタｋ＝１に初期化する。ステップＳ１２２では最小値保持レジスタＥ’に大きな値（例えば１０００００）をセットする。ステップＳ１２３では基底候補ブロック〈Ｕi〉のインデクスカウンタｉ＝０に初期化する。これはＤＣネストの開始アドレス（ｐｘ，ｐｙ）＝（０，０），サブサンプル間隔（ｓｘ，ｓｙ）＝（１，１）に対応する。
【００１１】
ステップＳ１２４では基底候補ブロック〈Ｕi〉からそのブロック平均値ａｉを分離して基底候補ベクトル〈ｕi〉を生成する。この演算は整数精度で行われるため、ブロック平均値ａiに小数点以下の値が発生した場合はこれを四捨五入（又は切り捨て等）する。ステップＳ１２５では必要（ｋ＞１）なら基底候補ベクトル〈ｕi〉をそれ以前の直交基底ベクトル〈ｕk'〉に直交化する。
【００１２】
図１５（Ａ），（Ｂ）に直交化処理のイメージ図を示す。図１５（Ａ）において、まず第１基底候補ベクトル〈ｕ1〉はそのままで第１基底ベクトル〈ｕ1'〉となり得る。次に第２基底候補ベクトル〈ｕ2〉は以下の方法により第１基底ベクトル〈ｕ1'〉に直交化される。即ち、第２基底候補ベクトル〈ｕ2〉の第１基底ベクトル〈ｕ1'〉への射影は（１）式の関係で得られる。
【００１３】
【数１】
0003932244.tif 000002
【００１４】
従って、第２直交ベクトル〈ｕ2'〉は第２基底候補ベクトル〈ｕ2〉から前記射影分のベクトルを引くことで得られる。
【００１５】
【数２】
0003932244.tif 000003
【００１６】
図１５（Ｂ）において、次に第３基底候補ベクトル〈ｕ3〉を第１，第２の基底ベクトル〈ｕ1'〉，〈ｕ2'〉に直交化する。この図は３次元的に描かれている。まず第３基底候補ベクトル〈ｕ3〉を第１基底ベクトル〈ｕ1'〉に直交化すると上記同様にして中間の直交ベクトル〈ｕ3''〉が得られる。
【００１７】
【数３】
0003932244.tif 000004
【００１８】
更にこの中間直交ベクトル〈ｕ3''〉を第２基底ベクトル〈ｕ2'〉に直交化すると第３基底ベクトル〈ｕ3'〉が得られる。
【００１９】
【数４】
0003932244.tif 000005
【００２０】
図１３に戻り、ステップＳ１２６では得られた直交ベクトル〈ｕi'〉を使用し、残差ベクトル〈ｄk〉（但し、最初は〈ｄj〉）との距離を最小とする様なスカラー係数αiを求める。
【００２１】
図１５（Ｃ）にその処理イメージを示す。図において、ある時点の残差ベクトルを〈ｄk〉とする時に、これを直交ベクトル〈ｕi'〉で近似した後の残差ベクトルの二乗ノルムｅｉ＝‖〈ｄk〉−αi〈ｕｉ'〉‖2が最小となるのは、図より明らかなように、直交ベクトル〈ｕｉ'〉にスカラー係数αiを掛けたものと、残差ベクトル｛〈ｄk〉−αi〈ｕｉ'〉｝とが直交する時（内積＝０）である。従って、スカラー係数αiは（５）式の関係により求まる。
【００２２】
【数５】
0003932244.tif 000006
【００２３】
なお、図には残差ベクトル〈ｄk〉（但し、ｋ＝０）を他の第１基底候補ベクトル〈ｕj'〉で近似した場合が描かれている。第１基底候補ベクトル〈ｕj'〉は任意方向をとり得るから、図示のようなイメージとなる。
【００２４】
図１４に戻り、ステップＳ１２７では残差ベクトル〈ｄk〉を基底候補ベクトルαi〈ｕi'〉で近似した後の誤差ベクトルの二乗ノルムｅiを求める。この演算は（６）式により得られる。
【００２５】
【数６】
0003932244.tif 000007
【００２６】
ステップＳ１２８ではｅi＜Ｅ'か否かを判別する。ｅi＜Ｅ'の場合はステップＳ１２９でＥ'の内容をｅiで更新する。またその時のαi，〈ｕi'〉，〈ｕi〉等に係る情報を配列［αk］，［ｕk'］，［ｕk］に保持する。またｅi＜Ｅ'でない場合は上記ステップＳ１２９の処理をスキップする。
【００２７】
ステップＳ１３０ではカウンタｉに＋１し、更にステップＳ１３１ではｉ≧Ｎ（＝８１９２）か否かを判別する。ｉ≧Ｎでない場合はステップＳ１２４に戻り、次の基底候補ベクトル〈ｕi〉につき上記同様の処理を行う。以下同様にして進み、やがて、ステップＳ１３１の判別でｉ≧Ｎになるとこの段階における全基底候補ベクトル〈ｕi〉が試されたことになる。この時、レジスタＥ'は最小の二乗ノルムｅiを保持している。
【００２８】
ステップＳ１３２ではＥ’≦Ｚか否かを判別し、Ｅ’≦Ｚでない場合はステップＳ１３３でＥ＝Ｅ'とする。即ち、残差ベクトルの二乗ノルムを更新する。ステップＳ１３４ではｋに＋１し、ステップＳ１２２に戻る。またＥ’≦Ｚの場合はこの処理を抜ける。こうして、最初の残差ベクトル〈ｄj〉との差を許容誤差Ｚ以下に近似するための直交基底系αk〈ｕk'〉（ｋ＝１〜ｍ）が得られる。
【００２９】
【発明が解決しようとする課題】
しかし、上記従来方式では基底候補ブロック〈Ｕi〉のブロック平均値ａiにつきその小数点以下を四捨五入（又は切り捨て等）していたため、画質の改善が頭打ちとなる不都合があった。これを図１６に従って説明する。
【００３０】
図１６（ａ）は基底候補ブロック〈Ｕi〉のある行の画素値を列（ｘ）方向に見た場合を示している。実際は１６画素分のブロック平均値であるが、ここでは説明の簡単のため４画素で説明する。図１６（ａ）において、各画素値は「５，２，４，３」からなりそのブロック平均値ａi＝３．５である。今、例えばこの小数点以下を切り捨てるとすると、図１６（ｂ）に示す如く、基底候補ベクトル〈ｕi〉のブロック平均値ａi＝０．５となる。図１６（ｃ）において、復号ブロックのＤＣ値ＤＣJに基底ベクトルβk〈ｕk〉を加算すると、復号画像のターゲットブロック〈Ｒj〉にはＤＣ成分（ａi＝０．５）が重畳されてしまう。しかも、基底数が複数の場合は、このようなＤＣ成分は０＜ａi＜１の範囲の様々な値でＤＣJに重畳される結果、復号画像ではブロック毎に一種の雑音が重畳された形となり、このため画質の改善が図れなかった。以上のことは小数点以下を四捨五入又は切り上げする場合も同様である。
【００３１】
また、従来のＡＯＴ処理では各基底候補ベクトル〈ｕi〉を一々前の基底ベクトル〈ｕk'〉に直交化していたため、ＡＯＴ処理に多大の演算と時間を要していた。
【００３２】
本発明は上記従来技術の問題点に鑑み成されたもので、その目的とする所は、より高画質かつ高速の符号／復号が得られる画像符号／復号方法及びその装置並びにそのプログラムを記録した記録媒体を提供することにある。
【００３３】
【課題を解決するための手段】
上記の課題は例えば図１の構成により解決される。即ち、本発明（１）の画像符号方法は、画像データをＢ画素毎にブロック分割して各ブロック平均値からなるＤＣ画像を生成し、該ＤＣ画像の一部を抽出した各ＤＣ画素の下位ｎ（ｎ＝log2Ｂ）ビットを０にしてＤＣネストとするステップと、符号対象の画素ブロック〈Ｒj〉からそのブロック平均値ＤＣJを分離した後の残差ベクトル〈ｄj〉の大きさが所定の許容値Ｚを超えると判定した場合に、前記ＤＣネストより順次基底候補ブロック〈Ｕｉ〉を抽出し、該ブロックからブロック平均値ａiを分離して基底候補ベクトル〈ｕi〉を生成し、該基底候補ベクトルを使用した適応的直交変換（ＡＯＴ）処理により前記残差ベクトルを許容値以下に近似するための１又は２以上の基底ベクトルを求めるステップと、を備えるものである。従って、ブロック平均値ａiに小数点以下の端数は生ぜず、整数精度のブロック平均値ａiが高速に得られる。また、１回のネスト生成処理でその下位ｎビットを０にされたＤＣネストが効率よく得られる。
【００３４】
また、本発明（２）の画像符号方法は、画像データをＢ画素毎にブロック分割して各ブロック平均値からなるＤＣ画像を生成し、その一部をＤＣネストとするステップと、符号対象の画素ブロックからそのブロック平均値を分離した後の残差ベクトルの大きさが所定の許容値を超えると判定した場合に、前記ＤＣネストより順次基底候補ブロックを抽出し、該ブロックを構成する各ＤＣ画素の下位ｎ（ｎ＝log2Ｂ）ビットを０にしてからそのブロック平均値を分離して基底候補ベクトル〈ｕi〉を生成し、該基底候補ベクトルを使用した適応的直交変換処理により前記残差ベクトルを許容値以下に近似するための１又は２以上の基底ベクトルを求めるステップと、を備えるものである。
【００３６】
上記本発明（１），（２）のような基底候補ベクトル〈ｕi〉はその全要素の和（ブロック平均値）が常に０であり、ＤＣ成分が完全に分離されている。従って、復号側でこのような基底ベクトル〈ｕk〉を幾つ重ねても不要なＤＣ成分（雑音）は生じない。そして、これにより本ＨＶＱ方式の画質が大幅に改善された。
【００３９】
また好ましくは本発明（３）においては、上記本発明（１）又は（２）において、適応的直交変換処理は  ＤＣネストを使用して最初の残差ベクトル〈ｄ〉との差の大きさを最小とするための第１基底ベクトル〈ｕ１〉を探査する処理を含み、該処理は、ＤＣネストから順次抽出した基底候補ベクトルを〈ｕｉ〉とするときに、
ｈi＝〈ｄ・ｕi〉2／‖ｕi‖2
を最大とする前記基底候補ベクトル〈ｕｉ〉を第１基底ベクトル〈ｕ１〉として抽出するステップと、該第１基底ベクトル〈ｕ1〉をその大きさで正規化して第１正規化基底ベクトル〈ｖ1〉となし、これを保持するステップと、第１スカラー係数α1を残差ベクトル〈ｄ〉の第１正規化基底ベクトル〈ｖ1〉への射影分として求め、これを保持するステップと、を備えるものである。
【００４０】
本発明（３）によれば、図１４の従来のステップＳ１２６，Ｓ１２７で行っていたような最初の残差ベクトル〈ｄ〉との差の二乗ノルム‖〈ｄ〉−αi〈ｕi〉‖2を最小とするような条件を上記簡単な演算及び条件で探索できる。従って、ＡＯＴ処理を高速化できる。例えば第１スカラー係数α1の演算は、抽出された第１正規化基底ベクトル〈ｖ1〉への射影分として一回求めれば良く、演算が大幅に簡略化される。
【００４１】
また好ましくは本発明（４）においては、上記本発明（３）において、適応的直交変換処理は  最初の残差ベクトル〈ｄ〉を第１スカラー係数α1と第１正規化基底ベクトル〈ｖ1〉とのスカラー積α１〈ｖ１〉により近似した後の第１残差ベクトル〈ｄ１〉が所定の許容値を超えると判定した場合に、ＤＣネストを使用して第１残差ベクトル〈ｄ１〉との差の大きさを最小とするための第２基底ベクトル〈ｕ２〉を探査する処理を含み、該処理は、ＤＣネストから順次抽出した基底候補ベクトルを〈ｕｉ〉とするときに、
ｈi＝｛〈ｄ・ｕi〉−（〈ｄ・ｕ1〉〈ｕ1・ｕi〉）／‖ｕ1‖2｝2
／｛‖ｕi‖2−（〈ｕ1・ｕi〉）／‖ｕ1‖）2｝
を最大とする前記基底候補ベクトル〈ｕｉ〉を第２基底ベクトル〈ｕ２〉として抽出するステップと、該第２基底ベクトル〈ｕ２〉を正規化及び第１正規化基底ベクトル〈ｖ1〉に直交化して第２正規化基底ベクトル〈ｖ２〉となし、これを保持するステップと、第２スカラー係数α２を第１残差ベクトル〈ｄ１〉の第２正規化基底ベクトル〈ｖ２〉への射影分として求め、これを保持するステップと、を備えるものである。
【００４２】
本発明（４）によれば、上記本発明（３）の効果に加え、上式分子の〈ｄ・ｕ1〉，‖ｕ1‖及び分母の‖ｕi‖2，‖ｕ1‖については既に第１基底探索で行った演算結果を利用できるため、ＡＯＴ処理を更に効率化、高速化できる。また、ベクトルの直交化演算も抽出した第２基底ベクトル〈ｕ２〉につき第１正規化基底ベクトル〈ｖ1〉に対して１回行えば良く、演算が大幅に簡略化される。
【００４３】
また好ましくは本発明（５）においては、上記本発明（４）において、適応的直交変換処理は  第１残差ベクトル〈ｄ１〉を第２スカラー係数α２と第２正規化基底ベクトル〈ｖ２〉とのスカラー積α2〈ｖ2〉により近似した後の第２残差ベクトル〈ｄ２〉が所定の許容値を超えると判定した場合に、ＤＣネストを使用して第２残差ベクトル〈ｄ２〉との差の大きさを最小とするための第３基底ベクトル〈ｕ３〉を探査する処理を含み、該処理は、ＤＣネストから順次抽出した基底候補ベクトルを〈ｕｉ〉とするときに、
ｈi＝
（〈ｄ・ｕi〉−〈ｄ・ｖ1〉〈ｖ1・ｕi〉−〈ｄ・ｖ2〉〈ｖ2・ｕi〉）2
／｛‖ｕi‖2−〈ｖ1・ｕi〉2−〈ｖ2・ｕi〉2｝
を最大とする前記基底候補ベクトル〈ｕｉ〉を第３基底ベクトル〈ｕ３〉として抽出するステップと、該第３基底ベクトル〈ｕ３〉を正規化及び第１正規化基底ベクトル〈ｖ1〉と第２正規化基底ベクトル〈ｖ２〉とに直交化して第３正規化基底ベクトル〈ｖ３〉となし、これを保持するステップと、第３スカラー係数α３を第２残差ベクトル〈ｄ２〉の第３正規化基底ベクトル〈ｖ３〉への射影分として求め、これを保存するステップと、
を備えるものである。
【００４４】
本発明（５）によれば、上記本発明（３），（４）の効果に加え、上式分子の（〈ｄ・ｕｉ〉−〈ｄ・ｖ１〉〈ｖ１・ｕｉ〉）及び分母の（‖ｕｉ‖２−〈ｖ１・ｕｉ〉２）については既に第１，第２の基底探索で行った演算結果を利用できるため、こうしてＡＯＴ処理を更に効率化、高速化できる。
【００４５】
また好ましくは本発明（６）においては、上記本発明（３）〜（５）において、適応的直交変換処理は  最初の残差ベクトル〈ｄ〉＝（d１,d２…，dｎ）との差の大きさを最小とする基底候補ベクトル〈ｕi〉＝（u１,u２,…，uｎ）を探査すべく両者の内積〈ｄ・ｕi〉を求める演算を含み、該演算は、基底候補ベクトル〈ｕi〉の任意要素（例えばｕｑ）を残りの要素の一次結合で置き換えると共に、残差ベクトル〈ｄ〉と基底候補ベクトル〈ｕi〉との内積〈ｄ・ｕi〉を、
〈ｄ・ｕi〉＝（ｄ1−ｄｑ）ｕ1＋（ｄ2−ｄｑ）ｕ2＋，
…，＋（ｄｎ−ｄｑ）ｕｎ
但し、（ｄｑ−ｄｑ）ｕｑの項を除く
の積和演算により求めるものである。
【００４６】
本発明（６）においては、上記基底候補ベクトル〈ｕi〉の全要素の和が常に０であることにより、その任意要素（例えばｕｑ）を残りの要素の一次結合で表せる。従って、最初の残差ベクトル〈ｄ〉との内積演算〈ｄ・ｕi〉は上式のような積和演算に展開でき、こうして面倒な積和演算の回数を１回分省略できる。ＨＶＱ方式による画像符号処理ではベクトルの内積演算が大量に行われるため、各１回の省略は全体としての符号処理の高速化に大きく貢献する。
【００４７】
また好ましくは本発明（７）においては、上記本発明（３）〜（５）において、ｍ個のスカラー係数αk(ｋ＝１〜ｍ）とｍ個の正規化基底ベクトル〈ｖk〉(ｋ＝１〜ｍ）とからなる正規直交基底系の組をｍ個のスカラー展開計数βk(ｋ＝１〜ｍ）と前記各正規化基底ベクトルの元となったｍ個の基底候補ベクトル〈ｕk〉(ｋ＝１〜ｍ）とからなる非直交基底系の組に変換するステップと、該変換したｍ個のスカラー展開計数βkと、ＤＣネストからｍ個の基底候補ベクトル〈ｕk〉を抽出するための抽出情報とからなる組と、ＤＣ画像とをそれぞれ符号化して符号データを出力するステップと、を更に備えるものである。
このように正規直交基底系αk，〈ｖk〉(ｋ＝１〜ｍ)の組を非直交基底系βk，〈ｕk〉(ｋ＝１〜ｍ)の組に変換することにより、復号側では各基底候補ベクトル〈ｕk〉を一々直交化する必要は無く、夫々にβkを掛けて加算することにより残差ベクトル〈ｄj〉を近似できる。従って、復号処理を簡単かつ高速に行える。
また本発明（８）の画像符号方法は、上記本発明（７）において、ｍ個のスカラー展開係数β1〜βｍのノルムをその大きさ順に並べ替え、０を含む隣接ノルム間の各差分を求め、得られた各差分につき所定ビット数の下位ビットを除く残りの上位ビットにハフマン符号化を適用するものである。
【００４８】
一般にスカラー展開係数β１〜βｍのノルムは様々な値をとり得るが、これらを大きさ順に並べて０を含む隣接ノルム間の各差分をとると、各差分の大きさは互いに近似（又は同一）となる場合が少なくない。そこで、これらの差分値につき所定ビット数の下位ビットを除く残りの上位ビットにハフマン符号を適用することで更なる符号圧縮が可能となる。
【００４９】
また好ましくは本発明（９）においては、上記本発明（１），（３）又は（５）において、適応的直交変換処理で求めた基底ベクトルの数が所定以上の場合は、基底系の符号化に代えて、符号対象ブロックの画像データそのものを符号化するものである。従って、復号画質の改善が図れる。また実際上このような状況は極めて少ないので符号圧縮率に与える影響は極めて少ない。
【００５０】
また上記の課題は例えば図１０の構成により解決される。即ち，本発明（１０）の画像復号方法は、本発明（７）に記載の符号データからＢ画素毎の各ブロック平均値に相当するＤＣ画像を再生し、該ＤＣ画像の一部を抽出した各ＤＣ画素の下位ｎ（ｎ＝log2Ｂ）ビットを０にしてＤＣネストとするステップと、前記符号データからｍ個のスカラー展開計数と、ｍ個の抽出情報とからなる組を復号するステップと、ターゲットブロックに対するｍ個のスカラー展開計数と、ｍ個の抽出情報によりＤＣネストから抽出した各基底候補ブロックとのスカラー積βk〈Ｕk〉(ｋ＝１〜ｍ）を生成してこれらをブロック毎に累積加算すると共に、該加算結果からそのブロック平均値を分離して残差ベクトル〈ｄｊ〉を生成し、これをターゲットブロックのＤＣ値に合成して画像データを再生するステップと、を備えるものである。従って、ブロック平均値に小数点以下の端数は生ぜず、整数精度のブロック平均値が高速に得られる。
【００５１】
また本発明（１１）の画像復号方法は、本発明（７）に記載の符号データからＢ画素毎の各ブロック平均値に相当するＤＣ画像を再生し、その一部をＤＣネストとするステップと、前記符号データからｍ個のスカラー展開計数と、ｍ個の抽出情報とからなる組を復号するステップと、ターゲットブロックに対するｍ個のスカラー展開計数βk(ｋ＝１〜ｍ）と、ｍ個の抽出情報によりＤＣネストから抽出した各基底候補ブロック〈Ｕk〉(ｋ＝１〜ｍ）につき各ＤＣ画素の下位ｎ（ｎ＝log2Ｂ）ビットを０にしたもの、とのスカラー積βk〈Ｕk〉(ｋ＝１〜ｍ）を生成してこれらをブロック毎に累積加算すると共に、該加算結果からそのブロック平均値を分離して残差ベクトル〈ｄｊ〉を生成し、これをターゲットブロックのＤＣ値に合成して画像データを再生するステップと、を備えるものである。
【００５２】
本発明（１０），（１１）においては、各選択ブロック〈Ｕk〉の下位ｎビットが０にされていることにより、これらを予め累積加算しても、その加算結果はブロックサイズＢ（例えば１６）の整数倍となる。なお、展開係数βkは整数精度とする。従って、最後にこの累積加算結果をブロック画素数Ｂで除算すれば１回の除算でブロック平均値Ａjが効率よく求まる。従って、基底ブロックβk〈Ｕk〉（ｋ＝１〜ｍ）を重ね合わせる演算を効率よく行える。
【００５４】
また本発明（１２）の画像符号装置は、画像データをＢ画素毎にブロック分割して各ブロック平均値からなるＤＣ画像を生成すると共に、該ＤＣ画像の一部を抽出した各ＤＣ画素の下位ｎ（ｎ＝log2Ｂ）ビットを０にしてＤＣネストを生成し、メモリに記憶するＤＣネスト生成手段と、符号対象の画素ブロック〈Ｒj〉からそのブロック平均値ＤＣJを分離した後の残差ベクトル〈ｄj〉の大きさが所定の許容値Ｚを超えると判定した場合に、前記ＤＣネストより順次基底候補ブロックを抽出し、該ブロックからブロック平均値を分離して基底候補ベクトルを生成し、該基底候補ベクトルを使用した適応的直交変換（ＡＯＴ）処理により前記残差ベクトル〈ｄj〉を許容値以下に近似するための１又は２以上の基底ベクトルを求める演算手段と、を備えるものである。
【００５５】
また本発明（１３）の画像復号装置は、本発明（７）に記載の符号データからＢ画素毎の各ブロック平均値に相当するＤＣ画像を再生すると共に、該ＤＣ画像の一部を抽出した各ＤＣ画素の下位ｎ（ｎ＝log2Ｂ）ビットを０にしてＤＣネストを再生し、メモリに記憶するＤＣネスト再生手段と、前記符号データからｍ個のスカラー展開計数と、ｍ個の抽出情報とからなる組を復号する復号手段と、ターゲットブロックに対するｍ個のスカラー展開計数と、ｍ個の抽出情報によりＤＣネストから抽出した各基底候補ブロックとのスカラー積βk〈Ｕk〉(ｋ＝１〜ｍ）を生成してこれらをブロック毎に累積加算すると共に、該加算結果からそのブロック平均値を分離して残差ベクトル〈ｄｊ〉を生成し、これをターゲットブロックのＤＣ値に合成して画像データを再生する画像再生手段と、を備えるものである。
【００５６】
また本発明（１４）の記録媒体は、上記本発明（１）乃至（１１）の何れか１つに記載の処理をコンピュータに実行させるためのプログラムを記録したコンピュータ読取り可能な記録媒体である。
【００５７】
【発明の実施の形態】
以下、添付図面に従って本発明に好適なる実施の形態を詳細に説明する。なお、全図を通して同一符号は同一又は相当部分を示すものとする。
【００５８】
図２は実施の形態による画像符号装置のブロック図で、図において、３１は復号ＤＣ画像から本発明によるＤＣネストを生成するＤＣネスト生成部、１７は生成されたＤＣネストを記憶するＤＣネストメモリ、３２はＡＯＴ処理を効率よくかつ高速に行う適応的直交変換処理部（ＡＯＴ）、３３は係数変換部、３４は展開係数βkの更に高圧縮を可能とする符号部である。その他の構成については上記図１３で述べたものと同様でよい。なお、上記各部の特徴は以下の動作説明によって明らかとなる。
【００５９】
図３は実施の形態による画像符号（メイン）処理のフローチャートである。ステップＳ１では原画像メモリ１１に原画像データを読み込む。例えばＲＧＢ系の対象画像をＹＵＶ系に変換して読み込む。Ｙは輝度データ、Ｕ，Ｖは色差データに相当し、Ｕ，Ｖは横２画素の輝度平均を用いてダウンサンプリングされる。一例の輝度データＹは縦９６０×横１２８０画素からなり、画素毎に例えば８ビットが割り付けられている。なお、以下は輝度データＹの処理を中心に述べるが、Ｕ，Ｖについても同様に処理できる。
【００６０】
ステップＳ２では全画像データにつき４×４画素毎のブロック平均（ＤＣ）値を求める。このとき小数点以下は例えば四捨五入される。ステップＳ３では全ＤＣ値を公知の２次元ＤＰＣＭ法等により符号化して出力する。ステップＳ４では全ＤＰＣＭ出力をＩＤＰＣＭ復号してＤＣ画像を再生し、ＤＣ画像メモリ１５に格納する。これは符号側／復号側のＡＯＴ処理条件を同一にするためである。ステップＳ５ではＤＣネスト生成部３１がＤＣ画像からＤＣネストを生成し、ＤＣネストメモリ１７に格納する。なお、ＤＣネストを切り出す領域の選択等は従来と同様でよい。
【００６１】
図７にＤＣネストの生成イメージを示す。図７（ａ）において、本実施の形態ではＤＣ画像メモリ１５から切り出した各ＤＣ画素ＤＣJの下位４ビットをマスク（＝０）してこれをＤＣネストメモリ１７のネスト画素Ｎjに記憶する。下位４ビットは２4＝Ｂ（Ｂ＝ブロックサイズ１６）又は４＝log2Ｂの関係にある。下位４ビットをマスクした結果、基底候補ブロック〈Ｕi〉の総和は常に１６の整数倍となり、よってこれを１／１６したブロック平均値ａiは常に整数となる。従って、基底候補ブロック〈Ｕi〉からブロック平均値ａiを分離した基底候補ベクトル〈ｕi〉のブロック平均値は常に０となる。
【００６２】
図７（ａ），（ｂ）に具体的な数値例をグラフで示す。但し、ここでは説明の簡単のため４画素分の平均をとっている。図７（ｃ）において、復号ブロック〈Ｒj〉のＤＣ値ＤＣJに複数の基底ベクトルβk〈ｕk〉を累積加算しても、各基底ベクトルβk〈ｕk〉のブロック平均値は常に０であるため、従来のような雑音は重畳されない。これにより画質の大幅な改善が図れた。
【００６３】
図８（ａ）に図７の数値例を表で示す。ＤＣ画素Ａ〜Ｄの合計ＳＵＭ＝２５１であり、その平均値ＡＶ＝２５１／４＝６２．７５（非整数）である。これらのＤＣ画素Ａ〜Ｄをネスト画素Ａ〜Ｄに転送する際に下位４ビットをマスクする。これによりネスト画素Ａ〜Ｄの合計ＳＵＭ＝２２４となり、その平均値ＡＶ＝２２４／４＝５６（整数）となる。更に、ネスト画素Ａ〜Ｄからその平均値ＡＶ＝５６を分離した基底候補ベクトル〈ｕi〉の各要素ａ〜ｄは「２４，−２４，８，−８」となり、これらの総和ｓｕｍ＝０（完全平均値分離）となっている。
【００６４】
図８（ｂ）は図８（ａ）と同じ数値例を示している。但し、ＤＣ画素Ａ〜Ｄをそのままネスト画素Ａ〜Ｄにコピーし、ネスト画素Ａ〜Ｄの総和ＳＵＭから下位４ビットをマスク（＝０）する点で異なっている。この方法でも総和ＳＵＭは１６の倍数になるから、ブロック平均値ＡＶ＝６０（整数）となる。しかしこの方法によると、ネスト画素Ａ〜Ｄからその平均値ＡＶ＝６０を分離した基底候補ベクトル〈ｕi〉の各要素ａ〜ｄは「３３，−２５，１３，−１０」となり、必ずしもその総和ｓｕｍ＝０（完全平均値分離）とはならない。
【００６５】
なお、図８（ｂ）に示す如くＤＣ画像の一部をそのままＤＣネストにコピーしておき、該ＤＣネストから基底候補ブロック〈Ｕi〉をダウンサンプルする時に各画素から下位４ビットをマスク（＝０）しても良い。
【００６６】
図３に戻り、ステップＳ６では原画像メモリ１１及びＤＣ画像メモリ１５に対する各インデクスカウンタｊ，Ｊを共に０に初期化する。但し、ｊは符号対象のターゲットブロック〈Ｒj〉のインデクスカウンタ、ＪはＤＣ画素のインデクスカウンタを夫々表す。ステップＳ７ではターゲットブロック〈Ｒj〉から対応する復号ＤＣ値ＤＣJを分離して残差ベクトル〈ｄj〉を求める。ステップＳ８では残差ベクトルの二乗ノルム‖ｄj‖2が許容誤差Ｚより大きいか否かを判別する。‖ｄj‖2＞Ｚでない場合はステップＳ１７で基底数「０」を符号出力する。この場合のターゲットブロック〈Ｒj〉は後述の交流成分予測法により復号される。また‖ｄj‖2＞Ｚの場合はステップＳ９で後述の適応的直交変換処理を行う。
【００６７】
ステップＳ１０では適応的直交変換で生成された基底数ｋ＞４か否かを判別する。因みに、実測ではほとんどの場合にｋ＝１〜３程度の統計結果が得られている。そこで、ｋ＞４の場合はステップＳ１８で基底数「５」を符号出力し、かつターゲットブロック〈Ｒj〉の各画素値を符号出力する。またｋ＞４でない場合はステップＳ１１で後述の展開係数βkへの変換を行う。ステップＳ１２では基底数「ｍ」，展開係数βk及び非直交基底ベクトル〈ｕi〉のインデクス情報ｉを夫々符号出力する。
【００６８】
ステップＳ１３ではカウンタｊ，Ｊに夫々＋１する。但し、カウンタｊに対する＋１は１画素ブロック分の更新を意味する。ステップＳ１４ではｊ≧Ｍ（＝全画像ブロック数）か否かを判別する。ｊ≧Ｍでない場合はステップＳ７に戻り、次のターゲットブロック〈Ｒj〉につき上記同様の符号処理を行う。以下同様にして進み、やがて、ステップＳ１４の判別でｊ≧Ｍになると、ステップＳ１５ではハフマン等による符号化を行う。この符号化については後述する。こうして１画像分の符号処理を終了する。
【００６９】
図４〜図６は実施の形態による適応的直交変換処理のフローチャート（１）〜（３）で、必要最少数の直交基底系αk〈ｖk〉（ｋ＝１〜ｍ）を効率よくかつ高速に求め得る場合を示している。なお、以下の説明では上記ステップＳ７で求められた最初の残差ベクトル〈ｄj〉を〈ｄ〉で表し、その後に更新される残差ベクトルを〈ｄk〉（ｋ＝１〜ｍ）で表す。
【００７０】
図４は第１基底の探索処理を示している。この処理の説明前に、該処理を高速に行うために行った計算上の工夫を説明する。即ち、通常なら第１基底は残差ベクトル〈ｄ〉との差の二乗ノルムｅiを最小とする基底候補ベクトル〈ｕi〉として求められるが、この関係式を更に展開すると（７）式が得られる。
【００７１】
【数７】
0003932244.tif 000008
【００７２】
ところで、（７）式右辺第１項の‖d‖2＞０は基底候補によらず一定であるから、同右辺第２項を最大にする〈ｕi〉が第１基底となり得る。そこで、この右辺第２項をｈiとおく。
【００７３】
【数８】
0003932244.tif 000009
【００７４】
以下は、ｈiを最大とするような第１基底αk〈ｖk〉を探索・決定する処理である。ステップＳ２１では後述の内積演算〈ｄ・ｕi〉の前処理として〈ｄ〉の第１６成分を残りの各成分の値から差し引いた１５次元ベクトル〈ｄ'〉を求める。ステップＳ２２ではｉ＝０〜（Ｎ−１）につきｈi分子の内積〈ｄ'・ｕi〉を求め、これらを配列［Ｐi］｛ｉ＝０〜（Ｎ−１）｝に格納する。
【００７５】
この内積演算を具体的に言うと、〈ｕi〉は本来１６次元ベクトルであるが、本実施の形態ではそのブロック平均値（全要素の和）＝０により、その第１６成分ｕ16は残りの１５成分の一次結合で表せる。
【００７６】
【数９】
0003932244.tif 000010
【００７７】
従って、ｈi分子の内積〈ｄ・ｕi〉をこれと等価な〈ｄ'・ｕi〉により求め、こうして積和演算を１回分（全ｉでは８１９２回分）省略できる。
【００７８】
【数１０】
0003932244.tif 000011
【００７９】
ステップＳ２３ではｉ＝０〜（Ｎ−１）につきｈi分母の二乗ノルム‖ｕi‖2を求め、これらを配列［Ｌi］｛ｉ＝０〜（Ｎ−１）｝に格納する。
【００８０】
【数１１】
0003932244.tif 000012
【００８１】
配列［Ｌi］は一度求めておけば後に結果を利用できる。ステップＳ２４ではｈiの最大値を保持するレジスタＥ＝０，基底候補ベクトル〈ｕi〉のインデクスカウンタｉ＝０，基底数カウンタｋ＝１に夫々初期化する。
【００８２】
ステップＳ２５ではｈi＝Ｐi2／Ｌiを求める。ステップＳ２６ではｈi＞Ｅか否かを判別する。ｈi＞Ｅの場合はステップＳ２７でＥをｈiで更新し、かつその時のｉを配列［Ｉk］（ｋ＝１）に保持する。またｈi＞Ｅでない場合は上記ステップＳ２７の処理をスキップする。
【００８３】
ステップＳ２８ではｉに＋１し、更にステップＳ２９ではｉ≧Ｎ（全候補数）か否かを判別する。ｉ≧Ｎでない場合はステップＳ２５に戻り、次のｈiにつき上記同様の最大値探索処理を行う。以下、同様にして進み、やがてｉ≧Ｎになると全ネストブロックの探索終了である。この時、上記配列［Ｉk］にはｈiを最大とするような第１基底ベクトル〈ｕ1〉のインデクス値ｉが保持されている。
【００８４】
ステップＳ３０では第１基底ベクトル〈ｕ1〉を正規化して正規化基底ベクトル〈ｖ1〉となし、これを配列［Ｖk］（ｋ＝１）に格納する。またスカラー係数α1（〈ｄ〉の〈ｖ1〉への射影）を求め、これを配列［Ａk］（ｋ＝１）に格納する。
【００８５】
ステップＳ３１では残差ベクトル〈ｄ〉を第１基底で近似後の残差ベクトル〈ｄ1〉＝〈ｄ〉−α1〈ｖ1〉により更新する。ステップＳ３２では新たな残差ベクトルの二乗ノルムｅ＝‖ｄ1‖2を求め、更にステップＳ３３ではｅ≦Ｚか否かを判別する。ｅ≦Ｚの場合はこの段階でＡＯＴ処理を終了し、またｅ≦Ｚでない場合は次いで第２基底の探索処理を行う。
【００８６】
図５は第２基底の探索処理を示している。この処理の説明前に該処理を効率よく行うために行った計算上の工夫を説明する。即ち、通常なら第２基底は残差ベクトル〈ｄ1〉との差の二乗ノルムｅiを最小とする直交ベクトル〈ｕi'〉として求められるが、この関係式を更に展開すると（１２）式が得られる。
【００８７】
【数１２】
0003932244.tif 000013
【００８８】
ここで、直交ベクトル〈ｕi'〉は第２基底の候補ベクトル＜ｕi＞を第１正規化基底ベクトル＜ｖ1＞に直交化したものである。
【００８９】
【数１３】
0003932244.tif 000014
【００９０】
同様にして、上記（１２）式右辺第１項の‖d1‖2＞０は基底候補によらず一定であるから、同右辺第２項を最大にするような直交ベクトル〈ｕi'〉が第２基底となり得る。この右辺第２項をｈiとおく。
【００９１】
【数１４】
0003932244.tif 000015
【００９２】
ｈiは、このまま求めても良いが、上記図４の演算結果を効率よく利用するために（１４）式の分母を変形する。即ち、まずｈi分子の直交ベクトル〈ｕi'〉を基底候補ベクトル〈ｕi〉で表すと、ｈi分子は（１５）式で表せる。
【００９３】
【数１５】
0003932244.tif 000016
【００９４】
更に残差ベクトル〈ｄ1〉を最初の残差ベクトル〈ｄ〉で表すと、ｈi分子は（１６）式で表せる。
【００９５】
【数１６】
0003932244.tif 000017
【００９６】
従って、ｈi分子の演算には第１基底探索で得られた演算結果〈ｄ・ｕ1〉，‖ｕ1‖を利用できる。また、同様にしてｈi分母を変形すると（１７）式で表せる。
【００９７】
【数１７】
0003932244.tif 000018
【００９８】
従って、ｈi分母の演算には第１基底探索で得られた演算結果‖ｕi‖2，‖ｕ1‖を利用できる。以上を（１４）式のｈiに代入すると、ｈiは（１８−１）式となり、最終的に（１８−２）式で表せる。
【００９９】
【数１８】
0003932244.tif 000019
【０１００】
ここで、Ｐi＝〈ｄ・ｕi〉，Ｌｉ＝‖ｕｉ‖2は配列［Ｐi］，［Ｌｉ］の演算結果を夫々利用でき、かつＰk＝Ｐ1＝〈ｄ・ｕ1〉，√（Ｌk）＝√（Ｌ1）＝‖ｕ1‖も前回の演算結果を利用できる。従って、今回新たに演算するのは〈ｕk・ｕi〉＝〈ｕ1・ｕi〉の部分である。
【０１０１】
以上を前提として、第２基底の探索は以下の演算処理を行う。即ち、ステップＳ４１ではｋ＝１によりＰ1＝〈ｄ・ｕ1〉，L1＝‖ｕ1‖2を保持する。これらは上記ステップＳ２２，Ｓ２３で求めた結果を利用できる。なお、添え字の「１」は第１基底〈ｕ1〉を指すインデクスカウンタｉの内容であり、これは上記ステップＳ２７の処理により配列［Ｉk］に保持されている。ステップＳ４２では（１９）式の演算を行い、結果をレジスタη，κに格納する。
【０１０２】
【数１９】
0003932244.tif 000020
【０１０３】
ステップＳ４３では後述の内積演算〈ｕ1・ｕi〉の前処理として〈ｕ1〉の第１６成分を残りの各成分の値から差し引いた１５次元ベクトル〈ｗ1〉を求める。ステップＳ４４ではｉ＝０〜（Ｎ−１）につき内積〈ｗk・ｕi〉ηを求め、これらを配列［Ｑi］に格納する。ステップＳ４５ではｉ＝０〜（Ｎ−１）につき（Ｐi−κＱi）を求め、これらを配列［Ｐi］に格納する。ここで、右辺のＰiは上記ステップＳ２２の演算結果であり、更にこのステップＳ４５の演算結果をステップＳ２２の配列［Ｐi］に上書き保存することで、配列［Ｐi］の内容は過去の演算結果を反映して逐次更新される。ステップＳ４６ではｉ＝０〜（Ｎ−１）につき（Ｌi−Ｑi2）を求め、これらを配列［Ｌi］に格納（上書）する。ここで、右辺のＬiは上記ステップＳ２３の演算結果であり、更にこのステップＳ４６の演算結果をステップＳ２３の配列［Ｌi］に上書き保存することで、配列［Ｌi］の内容も過去の演算結果を反映して逐次更新される。以上によるｈiの繰り返し演算は最終的に（２０）式で表せる。
【０１０４】
【数２０】
0003932244.tif 000021
【０１０５】
ステップＳ４７ではｈiの最大値を保持するレジスタＥ＝０，基底候補ベクトル〈ｕi〉のインデクスカウンタｉ＝０に夫々初期化し、かつ基底数カウンタｋに＋１する。この時点でｋ＝２となる。
【０１０６】
ステップＳ４８ではｈi＝Ｐi2／Ｌiを求める。ステップＳ４９ではｈi＞Ｅか否かを判別する。ｈi＞Ｅの場合はステップＳ５０でＥをｈiで更新し、その時のｉを配列［Ｉk］（ｋ＝２）に保持する。またｈi＞Ｅでない場合は上記ステップＳ５０の処理をスキップする。
【０１０７】
ステップＳ５１ではｉに＋１し、更にステップＳ５２ではｉ≧Ｎか否かを判別する。ｉ≧Ｎでない場合はステップＳ４８に戻り、次のｈiにつき上記同様の最大値探索処理を行う。以下、同様にして進み、やがて、ｉ≧Ｎになると全ネストブロックの探索終了である。この時、上記配列［Ｉk］（ｋ＝２）にはｈiを最大とするような第２基底ベクトル〈ｕ2〉のインデクス値ｉが保持されている。
【０１０８】
ステップＳ５３では第２基底ベクトル〈ｕ2〉を〈ｖ1〉に正規直交化して正規化基底ベクトル〈ｖ2〉となし、これを配列［Ｖk］（ｋ＝２）に格納する。またスカラー係数α2（〈ｄ1〉の〈ｖ2〉への射影）を求め、これを配列［Ａk］（ｋ＝２）に格納する。このように基底ベクトル〈ｕ2〉の正規直交化とスカラー係数α2の演算は上記探索結果について１回行えばよく、これによってＡＯＴ処理の大幅な軽量化と高速化が図られる。以下も同様である。
【０１０９】
ステップＳ５４では残差ベクトル〈ｄ1〉を第２基底で近似後の残差ベクトル〈ｄ2〉＝〈ｄ1〉−α2〈ｖ2〉により更新する。ステップＳ５５では新たな残差ベクトルの二乗ノルムｅ＝‖ｄ2‖2を求め、更にステップＳ５６ではｅ≦Ｚか否かを判別する。ｅ≦Ｚの場合はこの段階でＡＯＴ処理を終了し、またｅ≦Ｚでない場合は第３基底の探索処理を行う。
【０１１０】
図６は第３基底の探索処理を示している。この処理の説明前に該処理を効率よく行うために行った計算上の工夫を説明する。即ち、通常なら第３基底は残差ベクトル〈ｄ2〉との差の二乗ノルムｅiを最小とする直交ベクトル〈ｕi'〉として求められるが、この関係式を更に展開すると（２１）式が得られる。
【０１１１】
【数２１】
0003932244.tif 000022
【０１１２】
ここで、直交ベクトル〈ｕi'〉は第３基底の候補ベクトル〈ｕi〉を第１，第２の正規化基底ベクトル〈ｖ1〉，〈ｖ2〉に直交化したものである。
【０１１３】
【数２２】
0003932244.tif 000023
【０１１４】
同様にして上記（２１）式右辺第１項の‖d2‖2＞０は基底候補によらず一定であるから、同右辺第２項を最大にするような直交ベクトル〈ｕi'〉が第３基底となり得る。この右辺第２項をｈiとおく。
【０１１５】
【数２３】
0003932244.tif 000024
【０１１６】
更にｈi分子の直交ベクトル〈ｕi'〉を基底候補ベクトル〈ｕi〉で表すと、ｈi分子は（２４）式で表せる。
【０１１７】
【数２４】
0003932244.tif 000025
【０１１８】
更に（２４）式の残差ベクトル〈ｄ2〉を最初の残差ベクトル〈ｄ〉で表すと、ｈi分子は（２５）式で表せる。
【０１１９】
【数２５】
0003932244.tif 000026
【０１２０】
同様にしてｈi分母を変形すると（２６）式で表せる。
【０１２１】
【数２６】
0003932244.tif 000027
【０１２２】
以上を（２３）式のｈiに代入すると（２７）式が得られる。
【０１２３】
【数２７】
0003932244.tif 000028
【０１２４】
ところで、（２７）式分子／分母の各第２項までは既に計算されており、これらには（２８）式の関係がある。
【０１２５】
【数２８】
0003932244.tif 000029
【０１２６】
従って、ｈiの演算は上記（１８−２）式に習って最終的に（２９）式で表せる。
【０１２７】
【数２９】
0003932244.tif 000030
【０１２８】
（２９）式は内積〈ｕk・ｕi〉が〈ｖk・ｕi〉になっていることを除き、上記（１８−２）式と同じ形をしている。従って、これ以降の各基底は図５と同様のルーティンを再帰的に使用することで効率よく求まる。
【０１２９】
以上を前提として、第３基底以降の探索は以下の演算処理を行う。即ち、ステップＳ６１ではｋ＝２によりＰ2＝〈ｄ1・ｕ2〉，L2＝‖ｕ2‖2を保持する。ステップＳ６２では（３０）式の演算を行い、結果をレジスタη，κに格納する。
【０１３０】
【数３０】
0003932244.tif 000031
【０１３１】
ステップＳ６３では後述の内積演算〈ｖ2・ｕi〉の前処理として〈ｖ2〉の第１６成分を残りの各成分の値から差し引いた１５次元ベクトル〈ｗ2〉を求める。但し、〈ｖ2〉の各成分は整数値ではないので、このままでは内積演算を実数型で行う必要が生じる。これを避けるために、予め〈ｖ2〉(即ち、〈ｗ2〉）の各成分に定数ａを掛けて整数にしておく。
【０１３２】
ステップＳ６４ではｉ＝０〜（Ｎ−１）につき内積（〈ｗ2・ｕi〉η／ａ）を求め、これらを配列［Ｑi］に格納（上書）する。この時、各演算結果を定数ａで割ることにより、位を戻す。ステップＳ６５ではｉ＝０〜（Ｎ−１）につき（Ｐi−κＱi）を求め、これらを配列［Ｐi］に格納（上書）する。ステップＳ６６ではｉ＝０〜（Ｎ−１）につき（Ｌi−Ｑi2）を求め、これらを配列［Ｌi］に格納（上書）する。以上により上記（２９）式の演算は（３１）式で表せる。
【０１３３】
【数３１】
0003932244.tif 000032
【０１３４】
ステップＳ６７ではｈiの最大値を保持するレジスタＥ＝０，基底候補ベクトル〈ｕi〉のインデクスカウンタｉ＝０に夫々初期化し、かつ基底数カウンタｋに＋１する。この時点でｋ＝３となる。
【０１３５】
ステップＳ６８ではｈi＝Ｐi2／Ｌiを求める。ステップＳ６９ではｈi＞Ｅか否かを判別する。ｈi＞Ｅの場合はステップＳ７０でＥをｈiで更新し、その時のｉを配列［Ｉk］（ｋ＝３）に保持する。またｈi＞Ｅでない場合は上記ステップＳ７０の処理をスキップする。
【０１３６】
ステップＳ７１ではｉに＋１し、更にステップＳ７２ではｉ≧Ｎか否かを判別する。ｉ≧Ｎでない場合はステップＳ６８に戻り、次のｈiにつき上記同様の最大値探索処理を行う。以下、同様にして進み、やがて、ｉ≧Ｎになると全ネストブロックの探索終了である。この時、上記配列［Ｉk］（ｋ＝３）にはｈiを最大とするような第３基底ベクトル〈ｕ3〉のインデクス値ｉが保持されている。
【０１３７】
ステップＳ７３では第３基底ベクトル〈ｕ3〉を〈ｖ1〉，〈ｖ2〉に直交化かつ正規化して正規化基底ベクトル〈ｖ3〉となし、これを配列［Ｖk］に格納する。またスカラー係数α3（〈ｄ2〉の〈ｖ3〉への射影）を求め、これを配列［Ａk］に格納する。
【０１３８】
ステップＳ７４では残差ベクトル〈ｄ2〉を第３基底で近似後の残差ベクトル〈ｄ3〉＝〈ｄ2〉−α3〈ｖ3〉により更新する。ステップＳ７５では新たな残差ベクトルの二乗ノルムｅ＝‖ｄ3‖2を求め、更にステップＳ７６ではｅ≦Ｚか否かを判別する。ｅ≦Ｚの場合はこの段階でＡＯＴ処理を終了し、またｅ≦Ｚでない場合はステップＳ６１に戻り、第４基底以降の前処理及び探索処理を行う。なお、図示しないが、好ましくは、例えば上記ステップＳ７６の次にｋ≧４か否かの判別処理を設け、ｋ≧４の場合はこのＡＯＴ処理を抜けるようにする。
【０１３９】
以上により、ＡＯＴ処理の大幅な軽量化、かつ高速化が可能となり、演算時間は実測比で従来の１／３〜１／１０に短縮された。
【０１４０】
図２を参照し、ＡＯＴ３２からはαk，〈ｖk〉(ｋ＝１〜ｍ）の組が得られ、これらの一次結合により残差ベクトル〈ｄj〉を許容誤差Ｚ以内に近似できる。更に、係数変換部３３はαk，〈ｖk〉(ｋ＝１〜ｍ）の組をβk，〈ｕk〉(ｋ＝１〜ｍ）の組に変換すべく、以下（従来と同様）の方法により展開係数βkを求める。即ち、今、基底候補ベクトル〈ｕk〉，展開係数βk，正規化基底ベクトル〈ｖk〉，スカラー係数αkの各行列を（３２）式とおく時に、
【０１４１】
【数３２】
0003932244.tif 000033
【０１４２】
これらを（３３）式で関係つける。
【０１４３】
【数３３】
0003932244.tif 000034
【０１４４】
これを行列Ｂについて解くためには、まず行列Ｕを正方行列に変換すべく、両辺に行列Ｕの転置行列ＵTを左側から掛ける。
【０１４５】
【数３４】
0003932244.tif 000035
【０１４６】
この行列（ＵTＵ）は、（３５）式の様に展開され、
【０１４７】
【数３５】
0003932244.tif 000036
【０１４８】
ここで〈ｕi・ｕj〉は内積を表し、かつ〈ｕi・ｕj〉＝〈ｕj・ｕi〉であるから、対角要素に対して対称な正方行列が得られ、かつ〈ｕi〉と〈ｕj〉とが異なるから、逆行列が存在する。そこで、更に両辺の左側から行列（ＵTＵ）の逆行列（ＵTＵ）-1を掛けることで（３６）式が得られ、βkが求まる。
【０１４９】
【数３６】
0003932244.tif 000037
【０１５０】
このように正規直交基底系αk，〈ｖk〉(ｋ＝１〜ｍ）の組を非直交基底系βk，〈ｕk〉(ｋ＝１〜ｍ）の組に変換することにより、復号側では各基底候補ベクトル〈ｕk〉を一々直交化する必要は無く、夫々にβkを掛けて加算することにより残差ベクトル〈ｄj〉を近似できる。従って、復号処理を簡単かつ高速に行える。次に展開係数βkの圧縮符号処理を説明する。
【０１５１】
図９は実施の形態による展開係数符号処理のイメージ図である。図９（ａ）において、生成されたβ1〜β4からノルム（大きさ）を抽出する。図９（ｂ）において、ノルムを例えば昇順（β3，β2，β4，β1）に並べ換え、前方（最初は０）から順に差分（△β3，△β2，△β4，△β1）を求める。図９（ｃ）において、係数残差（△β3，△β2，△β4，△β1）をその下位２ビットと上位ビットとに分離し、上位ビットをハフマン符号化する。
【０１５２】
この例では△β3と（△β2＝△β4＝△β1）との２組の値が発生しており、よってハフマン符号では発生頻度の高い（△β2，△β4，△β1）にはビット数の少ない符号が割り振られ、また発生頻度の低い△β3にはビット数の多い符号が割り振られる。従って、展開係数βkの圧縮符号化が可能となる。しかも、係数残差△βkの上位ビットをハフマン符号化する構成により、下位ビットの端数分が切り離されることになり、よって上位ビットでは図示の如く△β2＝△β4＝△β1となるような可能性が高い。
【０１５３】
また、残差△βkの下位２ビットは正負の符号ビットと共に対応する基底ベクトル〈ｕk〉のインデクス情報（１３ビット＝０〜８１９１）と共に２バイト固定長符号エリアにパッキングされ、固定長符号として出力される。これらの符号の出力順は△β3，△β2，△β4，△β1（即ち、ｕ3，ｕ2，ｕ4，ｕ1）の順である。
【０１５４】
図９（ｄ）において、復号側では各符号をｕ3，ｕ2，ｕ4，ｕ1の順で入力し、夫々から係数△β3，△β2，△β4，△β1を分離する。更に最初の△β3からβ3を復号し、該β3に△β2を加えてβ2を復号し、該β2に△β4を加えてβ4を復号し、そして、該β4に△β1を加えてβ1を復号する。βk〈ｕk〉はこれらの和（一次結合）をとって機能するものであるから、これらの順序は問題ではない。
【０１５５】
なお、上記ノルムを昇順に並べ換え、前方（最初は０）から順に差分を求めたが、逆にノルムを降順に並べ換え、後方（最初は０）から順に差分を求めても良い。
【０１５６】
以下、符号部３４による符号処理を説明する。ＤＰＣＭの予測残差△ＤＣJ,I については量子化係数Ｑ（Ｚ）で量子化すると共に、△ＤＣJ,I ＝０の場合のみランレングスを考慮し、予測残差△ＤＣJ,I 及びランレングスを夫々独立にハフマン符号化する。基底数ｋは、ｋ＝０の場合のみランレングスを考慮し、基底数ｋ 及びランレングスを夫々独立にハフマン符号化する。係数残差△βkの上位ビットは定数Ｑ（例えば８）で量子化した商をハフマン符号化する。また基底ベクトル〈ｕk〉のコード情報ｉ（＝１３ビット）に展開係数βkの符号ビット及び係数残差△βkの下位２ビットを詰めて計１６ビットの固定長符号となし、これらは残差△βkの昇順（又は降順）に詰めて送られる。全体としては画素ブロック単位で出現順に詰めて符号列を構成する。必要なら画素ブロックの切り替わりを示すための符号ＥＯＢを書き込む。
【０１５７】
図１０は実施の形態による画像復号装置のブロック図で、上記図２の画像符号装置に対応したものである。図において、４１はハフマン等による復号部、４２は注目画素ＤＣJを含む周囲のＤＣ値ＤＣJ'から交流成分を含むターゲットブロック〈Ｒj〉を推定する交流成分予測部、４３は復号基底系βk〈ｕk〉（ｋ＝１〜ｍ）に基づきく近似残差ベクトル〈ｄj〉を再生する残差ベクトル再生部、４４は復号ブロック〈Ｒj〉に基づきターゲットブロック〈Ｒj〉を再生するＲj再生部、４５は再生画像を記憶する再生画像メモリ、４６は復号ＤＣ値をＩＤＰＣＭ復号するＩＤＰＣＭ部、４７は復号ＤＣ画像を記憶するＤＣ画像メモリ、４８は図２と同様のＤＣネスト生成部、４９はＤＣネストを記憶するＤＣネストメモリ、５０はＤＣネストからダウンサンプルされた選択ブロック〈Ｕk〉を保持する選択ブロックバッファ、５１は〈Ｕk〉にβkを乗算する乗算器、５２，５３はβk〈Ｕk〉（ｋ＝１〜ｍ）の累積加算部、５４は累積加算結果のブロック平均値Ａjを求める平均器、５５は累積加算結果からブロック平均値Ａjを分離する減算器、５６は再生近似残差ベクトル〈ｄj〉を保持する近似ベクトルバッファ、５７はターゲットブロック〈Ｒj〉の再生ＤＣ値ＤＣJに再生近似残差ベクトル〈ｄj〉を加算する加算器である。
【０１５８】
図１１は実施の形態による画像復号処理のフローチャートである。ステップＳ１０１では画像符号データを読み込む。ステップＳ１０２では図２と同様のＩＤＰＣＭ法によりＹ，Ｕ，Ｖの各ＤＣ値を解凍（復号）し、ＤＣ画像を再生する。ステップＳ１０３ではＹ成分のＤＣ画像からＤＣネストを生成する。この時、上記図７で示した如く、各ＤＣ画素値ＤＣJの下位４ビットがマスク（＝０）され、各ＤＣネスト画素値Ｎjとなる。なお、ＤＣ画像の切り出し位置等の情報は別途に受け取る。ステップＳ１０４では原画像メモリ４５及びＤＣ画像メモリ４７に対するインデクスカウンタｊ，Ｊを共に０に初期化する。
【０１５９】
ステップＳ１０５では１ブロック画像分の符号データを入力する。ステップＳ１０６では基底数ｋ＝０か否かを判別する。ｋ＝０の場合はステップＳ１１４で後述する交流成分予測法によりターゲットブロック〈Ｒｊ〉を再生する。またｋ≠０の場合は更にステップＳ１０７で１≦ｋ≦４か否かを判別する。
【０１６０】
１≦ｋ≦４の場合はステップＳ１１２で残差ベクトル〈ｄj〉を逆量子化する。本実施の形態では予めＤＣネストの下位４ビットがマスク（＝０）されているため、各選択ブロック〈Ｕk〉に直接βkを掛けてこれらを累積加算し、累積加算結果からそのブロック平均値Ａjを１回だけ分離することで残差ベクトル〈ｄj〉が一挙に得られる。よって復号処理が高速化される。ステップＳ１１３では得られた残差ベクトル〈ｄj〉に対応するＤＣ値ＤＣJを加算する。
【０１６１】
また１≦ｋ≦４でない場合はステップＳ１０８でターゲットブロック〈Ｒj〉の復号データよりターゲットブロック〈Ｒj〉を直接再生する。こうして、上記何れかの方法により４×４画素のターゲットブロック〈Ｒｊ〉が再生された。ステップＳ１０９では再生されたターゲットブロック〈Ｒｊ〉を再生画像メモリ４５に格納する。
【０１６２】
ステップＳ１１０ではカウンタｊ，Ｊに夫々＋１し、更にステップＳ１１１ではｉ≧Ｍ（全画素ブロック数）か否かを判別する。ｉ≧Ｍでない場合はステップＳ１０５に戻り、次のブロック画像符号データにつき上記同様の復号・再生処理を行う。以下同様にして進み、やがて、ステップＳ１１１の判別でｊ≧Ｍになると、１画像分の復号処理を終了する。
【０１６３】
図１２は実施の形態における交流成分予測のイメージ図で、公知の予測法を採用できる．図１２（Ａ）は段階的交流成分予測法を示しており、以下に内容を概説する。その第１段階では注目ブロックＳ上の各サブブロックＳ1 〜Ｓ4 を該Ｓを含む周囲４ブロック（Ｕ，Ｒ，Ｂ，Ｌ）の各ＤＣ値から次式により推定する。
【０１６４】
Ｓ1 ＝Ｓ＋（Ｕ＋Ｌ−Ｂ−Ｒ）／８
Ｓ2 ＝Ｓ＋（Ｕ＋Ｒ−Ｂ−Ｌ）／８
Ｓ3 ＝Ｓ＋（Ｂ＋Ｌ−Ｕ−Ｒ）／８
Ｓ4 ＝Ｓ＋（Ｂ＋Ｒ−Ｕ−Ｌ）／８
同様にして、この第１段階目ではＵ1 〜Ｕ4 ，Ｌ1 〜Ｌ4 ，Ｒ1 〜Ｒ4 ，Ｂ1 〜Ｂ4 等が推定される。更に、その第２段階では上記方法を再帰的に使用することで、Ｓ1 上の４画素Ｐ1 〜Ｐ4 を次式により推定する。
【０１６５】
Ｐ1 ＝Ｓ1 ＋（Ｕ3 ＋Ｌ2 −Ｓ3 −Ｓ2 ）／８
Ｐ2 ＝Ｓ1 ＋（Ｕ3 ＋Ｓ2 −Ｓ3 −Ｌ2 ）／８
Ｐ3 ＝Ｓ1 ＋（Ｓ3 ＋Ｌ2 −Ｕ3 −Ｓ2 ）／８
Ｐ4 ＝Ｓ1 ＋（Ｓ3 ＋Ｓ2 −Ｕ3 −Ｌ2 ）／８
Ｓ2 〜Ｓ4 上の各４画素Ｐ1 〜Ｐ4 についても同様である。このような２段階処理によりターゲットブロック〈Ｒｊ〉が再生される。
【０１６６】
図１３（Ｂ）は本件出願人による既提案の非段階的交流成分予測法を示しており、注目ブロックＳを含む周囲４ブロック（Ｕ，Ｒ，Ｂ，Ｌ）の各ＤＣ値から各サブブロックＳ1 〜Ｓ4 における各４画素Ｐ1 〜Ｐ4 を一挙に推定する。以下内容を概説する。まずＳ1 上の４画素Ｐ1 〜Ｐ4 を求める場合は、Ｓ2 ≒Ｓ3 ≒Ｓ，Ｕ3 ≒Ｕ，Ｌ2 ≒Ｌの各近似を行う。この近似を上記Ｓ1 上のＰ1 の式に適用すると、
Ｐ1 ＝Ｓ1 ＋（Ｕ3 ＋Ｌ2 −Ｓ3 −Ｓ2 ）／８
＝Ｓ1 ＋（Ｕ＋Ｌ−Ｓ−Ｓ）／８
が得られる。更にこの式に上記Ｓ1 の式、Ｓ1 ＝Ｓ＋（Ｕ＋Ｌ−Ｂ−Ｒ）／８を代入すると、Ｓ1 上のＰ1 は最終的に、
Ｐ1 ＝Ｓ＋（２Ｕ＋２Ｌ−２Ｓ−Ｂ−Ｒ）／８
で表せる。また上記Ｓ1 上のＰ2 については、
Ｐ2 ＝Ｓ1 ＋（Ｕ3 ＋Ｓ2 −Ｓ3 −Ｌ2 ）／８
＝Ｓ1 ＋（Ｕ＋Ｓ−Ｓ−Ｌ）／８
が得られる。更にこの式に上記Ｓ1 の式、Ｓ1 ＝Ｓ＋（Ｕ＋Ｌ−Ｂ−Ｒ）／８を代入すると、Ｓ1 上のＰ2 は最終的に、
Ｐ2 ＝Ｓ＋（２Ｕ−Ｂ−Ｒ）／８
で表せる。また上記Ｓ1 上のＰ3 については、
Ｐ3 ＝Ｓ1 ＋（Ｓ3 ＋Ｌ2 −Ｕ3 −Ｓ2 ）／８
＝Ｓ1 ＋（Ｓ＋Ｌ−Ｕ−Ｓ）／８
が得られる。更にこの式に上記Ｓ1 の式、Ｓ1 ＝Ｓ＋（Ｕ＋Ｌ−Ｂ−Ｒ）／８を代入すると、Ｓ1 上のＰ3 は最終的に、
Ｐ3 ＝Ｓ＋（２Ｌ−Ｂ−Ｒ）／８
で表せる。また上記Ｓ1 上のＰ4 については、
Ｐ4 ＝Ｓ1 ＋（Ｓ3 ＋Ｓ2 −Ｕ3 −Ｌ2 ）／８
＝Ｓ1 ＋（Ｓ＋Ｓ−Ｕ−Ｌ）／８
が得られる。更にこの式に上記Ｓ1 の式、Ｓ1 ＝Ｓ＋（Ｕ＋Ｌ−Ｂ−Ｒ）／８を代入すると、Ｓ1 上のＰ4 は最終的に、
Ｐ4 ＝Ｓ＋（２Ｓ−Ｂ−Ｒ）／８
で表せる。従って、Ｓ1 上の４画素Ｐ1 〜Ｐ4 は、
Ｐ1 ＝Ｓ＋（２Ｕ＋２Ｌ−２Ｓ−Ｂ−Ｒ）／８
Ｐ2 ＝Ｓ＋（２Ｕ−Ｂ−Ｒ）／８
Ｐ3 ＝Ｓ＋（２Ｌ−Ｂ−Ｒ）／８
Ｐ4 ＝Ｓ＋（２Ｓ−Ｂ−Ｒ）／８
により非段階的に一挙に求まる。Ｓ2 〜Ｓ4上の各４画素Ｐ1 〜Ｐ4 についても同様である。
【０１６７】
なお、上記実施の形態を具体的数値例を伴って説明したが本発明がこれらに限定されないことは明らかである。
【０１６８】
また、上記本発明に好適なる実施の形態を述べたが、本発明思想を逸脱しない範囲内で各部の構成、制御、処理及びこれらの組合せの様々な変更が行えることは言うまでも無い。
【０１６９】
【発明の効果】
以上述べた如く本発明によれば、ＤＣネストの改良により高画質が得られ、またＡＯＴ演算の工夫により高速符号化が得られた。従って、ＨＶＱ方式の高画質化、高速符号化に寄与するところが極めて大きい。
【図面の簡単な説明】
【図１】本発明の原理を説明する図である。
【図２】実施の形態による画像符号装置のブロック図である。
【図３】実施の形態による画像符号（メイン）処理のフローチャートである。
【図４】実施の形態による適応的直交変換処理のフローチャート（１）である。
【図５】実施の形態による適応的直交変換処理のフローチャート（２）である。
【図６】実施の形態による適応的直交変換処理のフローチャート（３）である。
【図７】実施の形態によるＤＣネストの説明図（１）である。
【図８】実施の形態によるＤＣネストの説明図（２）である。
【図９】実施の形態による展開係数符号処理のイメージ図である。
【図１０】実施の形態による画像復号装置のブロック図である。
【図１１】実施の形態による画像復号処理のフローチャートである。
【図１２】実施の形態における交流成分予測のイメージ図である。
【図１３】従来の画像符号装置のブロック図である。
【図１４】従来の適応的直交変換処理のフローチャートである。
【図１５】従来の適応的直交変換処理のイメージ図である。
【図１６】従来の平均値分離処理のイメージ図である。
【符号の説明】
１１  原画像メモリ
１２  ＤＣ値生成部
１３  差分ＰＣＭ符号部（ＤＰＣＭ）
１４  逆ＤＰＣＭ符号部（ＩＤＰＣＭ）
１５  ＤＣ画像メモリ
１６  ＤＣネスト生成部
１７  ＤＣネストメモリ
１８  減算器
１９  残差ベクトルバッファ
２０  抽出部ブロックバッファ
２１  平均器
２２  減算器
２３  候補ベクトルバッファ
２４  適応的直交変換処理部（ＡＯＴ）
２５  係数変換部
２６  符号部
３１  ＤＣネスト生成部
３２  適応的直交変換処理部（ＡＯＴ）
３３  係数変換部
３４  符号部
【図１】
0003932244.tif 000038
【図２】
0003932244.tif 000039
【図３】
0003932244.tif 000040
【図４】
0003932244.tif 000041
【図５】
0003932244.tif 000042
【図６】
0003932244.tif 000043
【図７】
0003932244.tif 000044
【図８】
0003932244.tif 000045
【図９】
0003932244.tif 000046
【図１０】
0003932244.tif 000047
【図１１】
0003932244.tif 000048
【図１２】
0003932244.tif 000049
【図１３】
0003932244.tif 000050
【図１４】
0003932244.tif 000051
【図１５】
0003932244.tif 000052
【図１６】
0003932244.tif 000053