JPH08279757A - 階層式ベクトル量子化装置 - Google Patents

Abstract

(57)【要約】 【目的】 ベクトル量子化装置に関し、１つのコードブ
ック中の出力ベクトルから入力ベクトルのブロックサイ
ズの変化に応じた次元を有する最適な出力ベクトルを探
索可能とすることを目的とする。 【構成】 入力ベクトルのブロックサイズがＫのとき
は、インデックスｉ毎に、 ^*ｙ_i ¹ 〜 ^*ｙ_i ⁴ までを結
合した出力ベクトルがベクトル量子化のコードブックと
して使用される。入力ベクトルのブロックサイズがｎの
ときは、インデックスｉ毎に、部分的な出力ベクトル ^*
ｙ_i ¹ 〜 ^*ｙ_i ⁴ のそれぞれが独立してベクトル量子化
のコードブックとして使用される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、入力信号系列を複数サ
ンプルまとめてブロック化しこれを多次元空間で量子化
する、画像伝送装置等に用いられるベクトル量子化装置
に関する。

【０００２】

【従来の技術及び発明が解決しようとする課題】ベクト
ル量子化技術では、符号化されるべき複数次元分のデー
タ（例えばそれぞれｍ×ｍ画素の各画像ブロックを示す
画素データ列）を要素とするベクトルの代表的なもの
が、コードブックとして、符号化側及び復号側の双方に
共通に保持される。そして、符号化側では、入力ベクト
ルに最も近い代表ベクトルがコードブック中から探索さ
れ、探索された代表ベクトルを特定するインデックスが
その入力ベクトルに対する量子化データとされ、その量
子化データが符号化される。一方、復号側では、符号化
データから上記インデックスが復号された後、そのイン
デックスに対応する代表ベクトルがコードブックから探
索され、その代表ベクトルが出力ベクトルとして出力さ
れる。

【０００３】このように、ベクトル量子化技術において
は、入力ベクトルがそのベクトルに対応する多次元空間
で量子化されるため、非常に高いデータ圧縮率を得るこ
とができる。

【０００４】ここで、従来の基本的なベクトル量子化装
置では、ベクトルの次元数が固定されている。このた
め、例えば画像信号がベクトル量子化される場合に、ベ
クトル量子化される画像ブロックの大きさが固定されて
しまう。しかし、画像には、狭い領域であっても多くの
濃淡を有するものが存在する一方、広い領域であっても
ほとんど濃淡のないのっぺりとしたものも存在する。従
って、画像ブロックのサイズが固定化されたベクトル量
子化においては、様々な種類の画像を最適に量子化する
ことができない。即ち、前者の画像の場合には、ベクト
ル量子化されるべき画像ブロックのサイズを小さくすべ
きであり、後者の画像の場合には、画像ブロックのサイ
ズを大きくすべきである。このように、ベクトルの次元
数が固定されたベクトル量子化装置においては、入力ベ
クトルを必ずしも最適に量子化することができないとい
う問題点を有している。

【０００５】このような問題点を解決するために、ベク
トルの次元数を可変できるようにしたベクトル量子化装
置が知られている。このようなものにおいては、適当な
評価関数に従って入力ベクトルの次元が可変的に決定さ
れ、各次元の入力ベクトルに対してベクトル量子化が実
行される。この場合に、各次元の入力ベクトルに対応す
るコードブックをどのように構成するかが重要な問題と
なる。

【０００６】次元数が可変のベクトル量子化装置におけ
るコードブックの構成方式の第１の従来技術として、可
変し得る次元のそれぞれに応じてコードブックを構成す
るようにしたものがある。しかし、この従来技術では、
コードブックを記憶するための記憶装置の容量が増大し
てしまうという問題点を有している。

【０００７】次元数が可変のベクトル量子化装置におけ
るコードブックの構成方式の第２の従来技術として、次
元数が固定された出力ベクトルが登録されているコード
ブックに対して、その次元数に合うように入力ベクトル
をサブサンプリングし、探索された出力ベクトルに対し
てはオーバーサンプリングをして出力するようにしたも
のがある。しかし、この従来技術では、サブサンプリン
グ及びオーバーサンプリンによって量子化の精度が劣化
してしまうという問題点を有している。

【０００８】次元数が可変のベクトル量子化装置におけ
るコードブックの構成方式の第３の従来技術として、特
公平5-56070 号公報に記載のものがある。この従来技術
では、図７に示されるように、コードブックは、Ｎ個の
インデックスｉ（１≦ｉ≦Ｎ）により指示され、それぞ
れの次元数（ブロックサイズ）がＫの、Ｎ組の代表ベク
トルである出力ベクトル ^*ｙ_i を含んでいる。そして、
各出力ベクトル ^*ｙ_i は、そのブロックサイズＫを任意
のサブブロックサイズｂで分割して得られるｎ＝Ｋ／ｂ
組の部分的な出力ベクトル ^*ｙ_i ^j （１≦ｊ≦ｎ）によ
って構成される。

【０００９】一方、入力ベクトル ^*ｘもそれをサブブロ
ックサイズｂで等分割して得られるｎ組の部分的な入力
ベクトル ^*ｘ^j 毎に入力される。そして、例えばベクト
ル量子化時のブロックサイズがサブブロックサイズｂに
等しい場合には、コードブック中の各インデックスｉ毎
に、図８(a) に示されるような距離Ｄ_i が計算される。
この距離Ｄ_i は、第１番目の部分的な入力ベクトル ^*ｘ
¹ とインデックスｉに対応する出力ベクトル ^*ｙ_i を構
成する第１番目の部分的な出力ベクトル ^*ｙ_i ¹ との間
の距離ｄ_i ¹ に等しい。この距離Ｄ_i が、コードブック
中の全てのインデックスｉ（１≦ｉ≦Ｎ）について計算
され、その最小値が第１番目の部分的な入力ベクトル ^*
ｘ¹ に対応する量子化データとして出力される。第２番
目以降の部分的な入力ベクトル ^*ｘ² 、・・・、
^*ｘ^j 、・・・、 ^*ｘⁿ のそれぞれについても、上述の
^*ｘ¹ が置き換えられて同様の計算が実行されることに
より、それぞれに対応する量子化データが出力される。

【００１０】次に、例えばベクトル量子化時のブロック
サイズがサブブロックサイズｂの２倍の値ｂ×２に等し
い場合には、コードブック中の各インデックスｉ毎に、
図８(b) に示されるような距離Ｄ_i が計算される。この
距離Ｄ_i は、第１番目の部分的な入力ベクトル ^*ｘ¹ と
インデックスｉに対応する出力ベクトル ^*ｙ_i を構成す
る第１番目の部分的な出力ベクトル ^*ｙ_i ¹ との間の距
離ｄ_i ¹ と、第２番目の部分的な入力ベクトル ^*ｘ² と
インデックスｉに対応する出力ベクトル ^*ｙ_iを構成す
る第２番目の部分的な出力ベクトル ^*ｙ_i ² との間の距
離ｄ_i ² との和に等しい。この距離Ｄ_i が、コードブッ
ク中の全てのインデックスｉ（１≦ｉ≦Ｎ）について計
算され、その最小値が第１番目の部分的な入力ベクトル
^*ｘ¹ と第２番目の部分的な入力ベクトル ^*ｘ² とを結
合して得られる部分的な入力ベクトルに対応する量子化
データとして出力される。第２組目以降の部分的な入力
ベクトル（ ^*ｘ³ 、 ^*ｘ⁴ ）、・・・、（ ^*ｘ^n-1 、 ^*
ｘⁿ ）のそれぞれの組についても、上述の（ ^*ｘ¹ 、 ^*
ｘ² ）の組が置き換えられて同様の計算が実行されるこ
とにより、それぞれに対応する量子化データが出力され
る。

【００１１】加えて、例えば、ベクトル量子化時のブロ
ックサイズがサブブロックサイズｂのｊ倍の値ｂ×ｊに
等しい場合には、コードブック中の各インデックスｉ毎
に、図９(c) に示されるような距離Ｄ_i が計算される。
この距離Ｄ_i は、第１番目の部分的な入力ベクトル ^*ｘ
¹ とインデックスｉに対応する出力ベクトル ^*ｙ_i を構
成する第１番目の部分的な出力ベクトル ^*ｙ_i ¹ との間
の距離ｄ_i ¹ から、第ｊ番目の部分的な入力ベクトル ^*
ｘ^j とインデックスｉに対応する出力ベクトル ^*ｙ_i を
構成する第ｊ番目の部分的な出力ベクトル ^*ｙ_i ^j との
間の距離ｄ_i ^jまでの和に等しい。この距離Ｄ_i が、コ
ードブック中の全てのインデックスｉ（１≦ｉ≦Ｎ）に
ついて計算され、その最小値が第１番目の部分的な入力
ベクトル ^*ｘ¹ から第ｊ番目の部分的な入力ベクトル ^*
ｘ^j までを結合して得られる部分的な入力ベクトルに対
応する量子化データとして出力される。それ以降のｊ組
毎の部分的な入力ベクトルのそれぞれの組についても、
上述の（ ^*ｘ¹ 、・・・、 ^*ｘ^j ）の組が置き換えられ
て同様の計算が実行されることにより、それぞれに対応
する量子化データが出力される。

【００１２】最後に、例えばベクトル量子化時のブロッ
クサイズがサブブロックサイズｂのｎ倍の値ｂ×ｎ＝Ｋ
に等しい場合、コードブック中の各インデックスｉ毎
に、図９(d) に示されるような距離Ｄ_i が、計算され
る。この距離Ｄ_i は、第１番目の部分的な入力ベクトル
^*ｘ¹ とインデックスｉに対応する出力ベクトル ^*ｙ_i
を構成する第１番目の部分的な出力ベクトル ^*ｙ_i ¹ と
の間の距離ｄ_i ¹ から、第ｎ番目（最後）の部分的な入
力ベクトル ^*ｘⁿ とインデックスｉに対応する出力ベク
トル ^*ｙ_i を構成する第ｎ番目の部分的な出力ベクトル
^*ｙ_i ⁿ との間の距離ｄ_i ⁿ までの和に等しい。この距
離Ｄ_i が、コードブック中の全てのインデックスｉ（１
≦ｉ≦Ｎ）につき計算され、その最小値が入力ベクトル
^*ｘ全体に対応する量子化データとして出力される。

【００１３】以上のように、第３の従来技術では、ベク
トル量子化時の入力ベクトルのブロックサイズが変化し
ても、単一のコードブックに登録された出力ベクトル ^*
ｙ₁〜 ^*ｙ_N で対応することができる。

【００１４】しかし、この第３の従来技術では、入力ベ
クトルのブロックサイズが小さくなっても、コードブッ
クにおいて、各インデックス毎にただ１組の出力ベクト
ルしか探索の対象とならないため、必ずしも最適な出力
ベクトルを探索することができないという問題点を有し
ている。

【００１５】本発明の課題は、１つのコードブック中の
出力ベクトルから入力ベクトルのブロックサイズの変化
に応じた次元を有する最適な出力ベクトルを探索可能と
することにある。

【００１６】

【課題を解決するための手段】本発明は、入力ベクトル
のブロックサイズが可変されその可変されたブロックサ
イズを有する入力ベクトルに対してベクトル量子化を実
行するベクトル量子化装置を前提とする。

【００１７】そして、本発明の第１の態様は、次のよう
な構成を有する。まず、１つのブロックサイズを有し該
１つのブロックサイズと同じブロックサイズを有する入
力ベクトルに対するコードブックを構成することができ
る出力ベクトルを結合するとそのブロックサイズよりも
大きな他のブロックサイズを有しその他のブロックサイ
ズと同じブロックサイズを有する入力ベクトルに対する
コードブックを構成することができる出力ベクトルとな
るような出力ベクトルの組を、コードブックとして記憶
するコードブック記憶手段を有する。

【００１８】次に、入力ベクトルのブロックサイズに対
応するようにコードブック内の出力ベクトルを適宜結合
し、その結合によって得られる各出力ベクトルを用いて
入力ベクトルをベクトル量子化するベクトル量子化手段
を有する。

【００１９】続いて、本発明の第２の態様は、次のよう
な構成を有する。まず、構成要素の一部分がその部分の
ブロックサイズと同じブロックサイズを有する入力ベク
トルに対するコードブックを構成することができる出力
ベクトルとなるような出力ベクトルの組を、コードブッ
クとして記憶するコードブック記憶手段を有する。

【００２０】次に、入力ベクトルのブロックサイズを単
位として、コードブックに記憶される各出力ベクトルの
構成要素の一部分を用いて入力ベクトルをベクトル量子
化するベクトル量子化手段を有する。

【００２１】

【作用】本発明の第１の態様では、入力ベクトルのブロ
ックサイズに対応するようにコードブック内の出力ベク
トルが結合され、その結合によって得られる各出力ベク
トルと入力ベクトルとの各歪が計算され、例えば歪が最
小となった結合された出力ベクトルを特定する識別情報
が出力される。

【００２２】本発明の第２の態様では、入力ベクトルの
ブロックサイズを単位として、コードブックに記憶され
る各出力ベクトルの構成要素の各部分との各歪が構成要
素内をシフトしながら計算され、例えば歪が最小となっ
た出力ベクトルの部分を特定する識別情報が出力され
る。

【００２３】

【実施例】以下、図面を参照しながら本発明の実施例に
つき詳細に説明する。 ＜第１の実施例＞図１は、本発明の第１の実施例の構成
図である。

【００２４】画像の画素信号であるＫ個毎にブロック化
された入力ベクトル ^*ｘ＝｛ｘ₁ 、・・・、ｘ_k ｝は、
階層セレクタ１０１に入力される。階層セレクタ１０１
は、上記Ｋ個の入力ベクトル ^*ｘを後述するようにｎ個
単位に細分化してベクトル量子化するか否かを判定し、
伝送路１０６に、その判定結果に応じた判定ビットを送
出する。

【００２５】例えば、ブロックサイズＫでベクトル量子
化すると判定された場合には判定ビット０が、ブロック
サイズＫの入力ベクトル ^*ｘを後述するようにｎ個単位
に細分化してベクトル量子化すると判定された場合には
判定ビット１が、共に１ビットのデータとして伝送路１
０６に出力される。

【００２６】また、上述の判定は、例えば、入力ベクト
ル ^*ｘの各要素値（サンプル値）の分散が計算され、そ
の分散値が所定の閾値以上であるか否かが判定されるこ
とによって決定される。分散値が大きな値であれば、そ
のブロックに対応する画像領域内にエッジや高周波成分
が含まれることになるため、ブロックサイズがＫのまま
では最適な量子化が行えない可能性が高い。従って、分
散値が所定の閾値以上であれば、ブロックサイズＫの入
力ベクトル ^*ｘをｎ個単位に細分化してベクトル量子化
すべく、判定ビットの値が１にセットされる。逆に、分
散値が小さな値であれば、そのブロックに対応する画像
領域は濃淡が少ないことになるため、ブロックサイズが
Ｋのままでも最適な量子化が行える可能性が高い。従っ
て、分散値が所定の閾値より小さければ、ブロックサイ
ズＫの入力ベクトル ^*ｘをそのままベクトル量子化すべ
く、判定ビットの値が０にセットされる。

【００２７】図２は、図１のコードブックメモリ１０４
に記憶されるコードブックの構成図である。第１の実施
例では、コードブックは、Ｎ個のインデックスｉ（１≦
ｉ≦Ｎ）により指示され、それぞれの次元数（ブロック
サイズ）がＫの、Ｎ組の出力ベクトル ^*ｙ_i ＝
｛ｙ_1,1 、・・・、ｙ_1,K ｝を含んでいる。そして、各
出力ベクトル ^*ｙ_i は、そのブロックサイズＫを任意の
サブブロックサイズｎで分割して得られる例えばＫ／ｎ
＝４組の部分的な出力ベクトル｛ ^*ｙ_i ¹ 、 ^*ｙ_i ² 、
^*ｙ_i ³ 、 ^*ｙ_i ⁴ ｝によって構成される。従って、Ｋ
はｎの倍数である。

【００２８】これは外見上は図７に示される従来技術の
場合の構成と同様であるが、第１の実施例の大きな特徴
は、上述の例えば４組の部分的な出力ベクトル｛ ^*ｙ_i
¹ 、 ^*ｙ_i ² 、 ^*ｙ_i ³ 、 ^*ｙ_i ⁴ ｝のそれぞれが入力
ベクトル ^*ｘによって表現される図３(a) に示される画
像領域において破線で仕切られた４つの領域のそれぞれ
に対応している点である。

【００２９】なお、上述のコードブックは、確率分布等
を反映したトレーニングベクトルを用いて、ＬＢＧアル
ゴリズム等によって予め設計されたものである。前述し
たように、階層セレクタ１０１が、ブロックサイズＫで
ベクトル量子化すると判定した場合、ベクトル量子化器
１０３は、図４に示される４０１〜４０８の機能構成に
よって、入力ベクトル ^*ｘに対して、歪（例えば絶対値
歪）が最小となる出力ベクトル ^*ｙ_i を算出する。

【００３０】そのために、まず図１のソート部１０２
は、画像領域に対して図３(a) に示される関係を有する
入力ベクトル ^*ｘ＝｛ｘ₁ 、・・・、ｘ_m 、ｘ_m+1 、・
・・、ｘ_2m、・・・・、ｘ_k ｝の並びを、画像領域に対
して図３(b) に示される関係を有するように変換する。

【００３１】上述の４組の部分的な入力ベクトル
^*ｘ¹ ′＝｛ｘ₁ ′、・・・、ｘ_n ′｝、 ^*ｘ² ′＝
｛ｘ_n+1 ′、・・・、ｘ_2n′｝、 ^*ｘ³ ′＝
｛ｘ_2n+1′、・・・・、ｘ_3n′｝、及び ^*ｘ⁴ ′＝｛ｘ
_3n+1′、・・・、ｘ_4n′｝は、それぞれ、図４に示され
る#1〜#4の入力レジスタ４０１に入力される。

【００３２】次に、コードブックアドレスカウンタ４０
２は、図１のコードブックメモリ１０４及びインデック
スバッファ１０５に、１〜Ｎまで変化するインデックス
ｉを順次出力する。これに対し、コードブックメモリ１
０４は、指定されたインデックスｉに対応する４組の部
分的な出力ベクトル ^*ｙ_i ¹ 、 ^*ｙ_i ² 、 ^*ｙ_i ³ 、及
び ^*ｙ_i ⁴ を、それぞれ、#1〜#4のコードブック出力レ
ジスタ４０３に出力する。

【００３３】続いて、#1〜#4の並列減算器４０４及び#1
〜#4の並列絶対値演算器４０５は、#1〜#4の入力レジス
タ４０１と#1〜#4のコードブック出力レジスタ４０３の
内容に基づいて、次のような並列演算を実行する。

【００３４】#1の並列減算器４０４と#1の並列絶対値演
算器４０５は、#1の入力レジスタ４０１内の部分的な入
力ベクトル ^*ｘ¹ ′の要素ｘ₁ ′、ｘ₂ ′、・・・、ｘ
_n ′と、#1のコードブック出力レジスタ４０３内の部分
的な出力ベクトル ^*ｙ_i ¹ の要素ｙ_i,1 ¹ 、ｙ_i,2 ¹ 、
・・・、ｙ_i,n ¹ に対して、｜ｘ₁ ′−ｙ_i,1 ¹ ｜、｜
ｘ₂ ′−ｙ_i,2 ¹ ｜、・・・、｜ｘ_n ′−ｙ_i,n ¹ ｜で
示されるｎ組の減算／絶対値演算動作を並列に実行す
る。

【００３５】次に、#2の並列減算器４０４及び#2の並列
絶対値演算器４０５は、#2の入力レジスタ４０１内の部
分的な入力ベクトル ^*ｘ² ′の要素ｘ_n+1 ′、
ｘ_n+2 ′、・・・、ｘ_2n′と、#2のコードブック出力レ
ジスタ４０３内の部分的な出力ベクトル ^*ｙ_i ² の要素
ｙ_i,1 ² 、ｙ_i,2 ² 、・・・、ｙ_i,n ² に対し、｜ｘ
_n+1 ′−ｙ_i,1 ² ｜、｜ｘ_n+2 ′−ｙ_i,2 ² ｜、・・
・、｜ｘ_2n′−ｙ_i,n ² ｜で示されるｎ組の減算／絶対
値演算動作を並列に実行する。

【００３６】また、#3の並列減算器４０４及び#3の並列
絶対値演算器４０５は、#3の入力レジスタ４０１内の部
分的な入力ベクトル ^*ｘ³ ′の要素ｘ_2n+1′、
ｘ_2n+2′、・・・、ｘ_3n′と、#3のコードブック出力レ
ジスタ４０３内の部分的な出力ベクトル ^*ｙ_i ³ の要素
ｙ_i,1 ³ 、ｙ_i,2 ³ 、・・・、ｙ_i,n ³ に対し、｜ｘ
_2n+1′−ｙ_i,1 ³ ｜、｜ｘ_2n+2′−ｙ_i,2 ³ ｜、・・
・、｜ｘ_3n′−ｙ_i,n ³ ｜で示されるｎ組の減算／絶対
値演算動作を並列に実行する。

【００３７】更に、#4の並列減算器４０４及び#4の並列
絶対値演算器４０５は、#4の入力レジスタ４０１内の部
分的な入力ベクトル ^*ｘ⁴ ′の要素ｘ_3n+1′、
ｘ_3n+2′、・・・、ｘ_4n′と、#4のコードブック出力レ
ジスタ４０３内の部分的な出力ベクトル ^*ｙ_i ⁴ の要素
ｙ_i,1 ⁴ 、ｙ_i,2 ⁴ 、・・・、ｙ_i,n ⁴ に対し、｜ｘ
_3n+1′−ｙ_i,1 ⁴ ｜、｜ｘ_3n+2′−ｙ_i,2 ⁴ ｜、・・
・、｜ｘ_4n′−ｙ_i,n ⁴ ｜で示されるｎ組の減算／絶対
値演算動作を並列に実行する。

【００３８】続いて、#1〜#4の絶対値歪検出器４０６
は、それぞれ、#1〜#4の並列絶対値演算器４０５から出
力される絶対値｜ｘ₁ ′−ｙ_i,1 ¹ ｜〜｜ｘ_n ′−ｙ
_i,n ¹ ｜、｜ｘ_n+1 ′−ｙ_i,1 ² ｜〜｜ｘ_2n′−ｙ_i,n
² ｜、｜ｘ_2n+1′−ｙ_i,1 ³ ｜〜｜ｘ_3n′−ｙ
_i,n ³ ｜、及び｜ｘ_3n+1′−ｙ_i,1 ⁴ ｜〜｜ｘ_4n′−ｙ
_i,n ⁴ ｜に対して、次式で示される絶対値歪ｄ_i ^j （１
≦ｊ≦４）を検出する。

【００３９】

【数１】

【００４０】次に、加算器４０７は、#1〜#4の絶対値歪
検出器４０６からそれぞれ出力される絶対値歪ｄ
_i ^j （１≦ｊ≦４）の総和を計算する。この結果得られ
る絶対値歪の総和が、入力ベクトル ^*ｘとインデックス
ｉに対応する出力ベクトル ^*ｙ_i の間の歪ｄ（ ^*ｘ、 ^*
ｙ_i ）として、最小歪出力ベクトル検出器４０８に出力
される。

【００４１】最小歪出力ベクトル検出器４０８は、入力
ベクトル ^*ｘとインデックスｉに対応する出力ベクトル
^*ｙ_i の間の歪ｄ（ ^*ｘ、 ^*ｙ_i ）を、現在までに検出
されている最小値と比較することにより、インデックス
ｉが１〜Ｎまで変化する間の最小歪、

【００４２】

【数２】

【００４３】を算出する。最小歪出力ベクトル検出器４
０８は、現在までに検出されている最小値を新たに入力
した歪ｄ（ ^*ｘ、 ^*ｙ_i ）によって置き換えたタイミン
グで、その旨を図１のインデックスバッファ１０５に通
知する。

【００４４】インデックスバッファ１０５は、上記通知
を受信した時点で図４のコードブックアドレスカウンタ
４０２から出力されているインデックスｉを取り込み、
それを図１の伝送路１０６に出力する。このインデック
スｉが、入力ベクトル ^*ｘに対応する量子化データとな
る。

【００４５】伝送路１０６に接続される特には図示しな
い復号装置は、まず、受信した判定ビットからブロック
サイズを認識し、それに基づいて符号化データを受信
し、その符号化データから上述のインデックスｉを復号
した後、そのインデックスに対応する出力ベクトル ^*ｙ
_i を図１のコードブックメモリ１０４に記憶されている
のと同じ構成のコードブックから探索し、それを入力ベ
クトル ^*ｘの復号結果として、ソートした後に出力す
る。

【００４６】次に、前述したように、階層セレクタ１０
１が、ブロックサイズＫを４分割したサブブロックサイ
ズｎでベクトル量子化すると判定した場合、ベクトル量
子化器１０３は、図５に示される機能構成によって、ソ
ート部１０２から出力される並び替え４分割された４組
の部分的な入力ベクトル ^*ｘ¹ ′＝｛ｘ₁ ′、・・・、
ｘ_n ′｝、 ^*ｘ² ′＝｛ｘ_n+1 ′、・・・、ｘ_2n′｝、
^*ｘ³ ′＝｛ｘ_2n+1′、・・・・、ｘ_3n′｝、及び ^*ｘ
⁴ ′＝｛ｘ_3n+1′、・・・、ｘ_4n′｝のそれぞれの組に
対して、歪が最小となる出力ベクトル ^*ｙ_i ^j を算出す
る。

【００４７】以下の説明においては、部分的な入力ベク
トル ^*ｘ¹ ′＝｛ｘ₁ ′、・・・、ｘ_n ′｝を例にとっ
て説明するが、他の組についても同様である。この場
合、図４に示されるそれぞれ４つからなる入力レジスタ
４０１、コードブック出力レジスタ４０３、並列減算器
４０４、並列絶対値演算器４０５、及び絶対値歪検出器
４０６のうち、それぞれ１つの例えば#1のみが使用され
る。

【００４８】まず、部分的な入力ベクトル ^*ｘ¹ ′＝
｛ｘ₁ ′、・・・、ｘ_n ′｝は、#1の入力レジスタ４０
１に保持される。次に、コードブックアドレスカウンタ
４０２は、図１のコードブックメモリ１０４及びインデ
ックスバッファ１０５に、１〜Ｎまで変化するインデッ
クスｉを順次出力すると共に、各インデックスｉ毎に、
例えば１〜４まで変化するサブインデックスｊを出力す
る。これに対し、コードブックメモリ１０４は、指定さ
れたインデックスｉ及びサブインデックスｊに対応する
１組の部分的な出力ベクトル ^*ｙ_i ^j ＝｛ｙ_i,1 ^j 、ｙ
_i,2 ^j 、・・・、ｙ_i,n ^j ｝を、#1のコードブック出力
レジスタ４０３に出力する。

【００４９】#1の並列減算器４０４と#1の並列絶対値演
算器４０５は、#1の入力レジスタ４０１内の部分的な入
力ベクトル ^*ｘ¹ ′の要素ｘ₁ ′、ｘ₂ ′、・・・、ｘ
_n ′と、#1のコードブック出力レジスタ４０３内の部分
的な出力ベクトル ^*ｙ_i ¹ の要素ｙ_i,1 ^j 、ｙ_i,2 ^j 、
・・・、ｙ_i,n ^j に対して、｜ｘ₁ ′−ｙ_i,1 ^j ｜、｜
ｘ₂ ′−ｙ_i,2 ^j ｜、・・・、｜ｘ_n ′−ｙ_i,n ^j ｜で
示されるｎ組の減算／絶対値演算動作を並列に実行す
る。

【００５０】#1の絶対値歪検出器４０６は、#1の並列絶
対値演算器４０５から出力される絶対値｜ｘ₁ ′−ｙ
_i,1 ^j ｜〜｜ｘ_n ′−ｙ_i,n ^j ｜に対して、次式で示さ
れる絶対値歪ｄ_i ^j を検出する。

【００５１】

【数３】

【００５２】最後に、最小歪出力ベクトル検出器４０８
は、部分的な入力ベクトル ^*ｘ¹ ′と、インデックスｉ
及びサブインデックスｊに対応する部分的な出力ベクト
ル ^*ｙ_i ^j の間の歪ｄ（ ^*ｘ¹ ′、 ^*ｙ_i ^j ）を、現在
までに検出されている最小値と比較することにより、イ
ンデックスｉが１〜Ｎまで変化し、かつ各インデックス
ｉ毎にサブインデックスｊが１〜４まで変化する間の最
小歪、

【００５３】

【数４】

【００５４】を算出する。最小歪出力ベクトル検出器４
０８は、現在までに検出されている最小値を新たに入力
した歪ｄ（ ^*ｘ¹ ′、 ^*ｙ_i ^j ）によって置き換えたタ
イミングで、その旨を図１のインデックスバッファ１０
５に通知する。

【００５５】インデックスバッファ１０５は、上記通知
を受信した時点で図４のコードブックアドレスカウンタ
４０２から出力されているインデックスｉ及びサブイン
デックスｊを取り込み、それらを図１の伝送路１０６に
出力する。これらのインデックスｉ及びサブインデック
スｊが、部分的な入力ベクトル ^*ｘ¹ ′に対応する量子
化データとなる。

【００５６】伝送路１０６に接続される特には図示しな
い復号装置は、まず、受信した判定ビットからブロック
サイズを認識し、それに基づいて符号化データを受信
し、その符号化データから上記インデックスｉ及びサブ
インデックスｊを復号した後、それらのインデックスに
対応する部分的な出力ベクトル ^*ｙ_i ^j を図１のコード
ブックメモリ１０４に記憶されているのと同じ構成のコ
ードブックから探索し、それを部分的な入力ベクトル ^*
ｘ¹ ′の復号結果として、ソートした後に出力する。

【００５７】以上説明したように、第１の実施例では、
ブロックサイズＫを例えばＫ／ｎ分割（上述の例では４
分割）したサブブロックサイズｎでベクトル量子化が実
行される場合、コードブックに記憶されている全ての部
分的な出力ベクトル ^*ｙ_i ^j（１≦ｉ≦Ｎ、１≦ｊ≦Ｋ
／ｎ）が探索の対象となるため、従来技術よりも最適な
出力ベクトルを探索することが可能となる。

【００５８】なお、上述の第１の実施例において、イン
デックスｉ毎に、探索する部分的な出力ベクトルを制限
しどの範囲で探索するかをコードブックに登録するよう
にしてもよく、これにより、サブインデックスの符号化
に必要な情報量を削減することができる。 ＜第２の実施例＞次に、本発明の第２の実施例について
説明する。

【００５９】第２の実施例は、第１の実施例に関する図
１の構成と同様の構成によって実現される。まず、図１
の階層セレクタ１０１が、ブロックサイズＫでベクトル
量子化すると判定した場合、ベクトル量子化器１０３
は、前述した第１の実施例の場合と同様にして、入力ベ
クトル ^*ｘと、インデックスｉ毎の出力ベクトル ^*ｙ_i
全体との歪を計算することにより、それが最小となるイ
ンデックスｉを算出し、伝送路１０６に出力する。

【００６０】一方、前述したように、階層セレクタ１０
１が、ブロックサイズＫを分割したサブブロックサイズ
でベクトル量子化すると判定した場合、次のような動作
を実行する。

【００６１】今、例えば、入力ベクトル ^*ｘ＝｛ｘ₁ 、
・・・、ｘ_k ｝が、図６(a) の破線で仕切られる各画像
領域に対応するサブブロックに分割してベクトル量子化
される場合、図１のソート部１０２は、入力ベクトル ^*
ｘの各要素を並び替えることにより、図６(a) の破線で
仕切られる各画像領域に対応する部分的な入力ベクト
ル、例えば ^*ｘ¹ ′＝｛ｘ₁ ′、ｘ₂ ′、ｘ₃ ′、
ｘ₄ ′｝を出力する。

【００６２】一方、図１のベクトル量子化器１０３は、
コードブックメモリ１０４に対し、１〜Ｎまで順次変化
するインデックスｉに対応する出力ベクトル ^*ｙ_i の読
出しアドレスを指定し、更に、インデックスｉ毎に、出
力ベクトル ^*ｙ_i に対応する画像領域内の任意の点
（ｕ、ｖ）を始点とし、部分的な入力ベクトルのブロッ
クサイズと同じブロックサイズを有する領域に対応する
部分的な出力ベクトルを読み出すためのアドレスを指定
する。

【００６３】そして、ベクトル量子化器１０３は、部分
的な入力ベクトルとその指定された部分的な出力ベクト
ルとの絶対値歪を計算する。更に、ベクトル量子化器１
０３は、１つのインデックスｉ内で上記始点（ｕ、ｖ）
をシフトさせながら絶対値歪が最小となる始点（ｕ、
ｖ）を検出し、更に、インデックスｉを１〜Ｎまで変化
させることにより、絶対値歪が最小となるインデックス
ｉ及び始点（ｕ、ｖ）を検出する。

【００６４】このようにして検出されたインデックスｉ
及び始点（ｕ、ｖ）は、インデックスバッファ１０５を
介して、伝送路１０６に送出される。伝送路１０６に接
続される特には図示しない復号装置は、まず、受信した
判定ビットからブロックサイズを認識し、それに基づい
て符号化データを受信し、その符号化データから上記イ
ンデックスｉ及び始点（ｕ、ｖ）を復号した後、インデ
ックスｉ及び始点（ｕ、ｖ）に対応する部分的な出力ベ
クトルを符号化装置側と同じ構成のコードブックから探
索し、それを部分的な入力ベクトルの復号結果として、
ソートした後に出力する。

【００６５】以上説明したように、第２の実施例では、
出力ベクトル ^*ｙ_i 内でシフトされる全ての部分を量子
化のためのコードブックとして使用できるため、従来技
術より最適化な出力ベクトルを探索することが可能とな
る。

【００６６】なお、上述の第２の実施例で、インデック
スｉ毎にシフトする始点（ｕ、ｖ）の範囲を制限しどの
範囲でシフトするかをコードブックに登録するようにし
てもよく、これにより、始点（ｕ、ｖ）の符号化に必要
な情報量を削減することができる。

【００６７】

【発明の効果】本発明の第１の態様によれば、入力ベク
トルのブロックサイズに対応するように単一のコードブ
ック内で結合された各出力ベクトルを量子化のために使
用することができるため、従来技術より最適化な出力ベ
クトルを探索することが可能となる。

【００６８】本発明の第２の態様によれば、入力ベクト
ルのブロックサイズを単位とするコードブックに記憶さ
れる各出力ベクトルの構成要素の各部分を量子化のため
に使用することができるため、従来技術より最適化な出
力ベクトルを探索することが可能となる。

【図面の簡単な説明】

【図１】本発明の実施例の構成図である。

【図２】第１の実施例におけるコードブックの構成図で
ある。

【図３】第１の実施例における入力ベクトル及び部分的
な入力ベクトルと、画像領域との関係を示した図であ
る。

【図４】第１の実施例のベクトル量子化器１０３におけ
るブロックサイズＫのベクトル量子化動作の説明図であ
る。

【図５】第１の実施例のベクトル量子化器１０３におけ
るサブブロックサイズｎのベクトル量子化動作の説明図
である。

【図６】第２の実施例の説明図である。

【図７】従来技術におけるコードブックの構成図であ
る。

【図８】従来技術におけるベクトル量子化動作の説明図
（その１）である。

【図９】従来技術におけるベクトル量子化動作の説明図
（その２）である。

【符号の説明】

１０１ 階層セレクタ １０２ ソート部 １０３ ベクトル量子化器 １０４ コードブックメモリ １０５ インデックスバッファ

Claims (2)

【特許請求の範囲】
1. 【請求項１】 入力ベクトルのブロックサイズが可変さ
   れその可変されたブロックサイズを有する前記入力ベク
   トルに対してベクトル量子化を実行するベクトル量子化
   装置において、 １つのブロックサイズを有し該１つのブロックサイズと
   同じブロックサイズを有する入力ベクトルに対するコー
   ドブックを構成することができる出力ベクトルを結合す
   ると該ブロックサイズよりも大きな他のブロックサイズ
   を有し該他のブロックサイズと同じブロックサイズを有
   する入力ベクトルに対するコードブックを構成すること
   ができる出力ベクトルとなるような出力ベクトルの組
   を、コードブックとして記憶するコードブック記憶手段
   と、 前記入力ベクトルのブロックサイズに対応するように前
   記コードブック内の出力ベクトルを適宜結合し、該結合
   によって得られる各出力ベクトルを用いて前記入力ベク
   トルをベクトル量子化するベクトル量子化手段と、 を有することを特徴とする階層式ベクトル量子化装置。
2. 【請求項２】 入力ベクトルのブロックサイズが可変さ
   れその可変されたブロックサイズを有する前記入力ベク
   トルに対してベクトル量子化を実行するベクトル量子化
   装置において、 構成要素の一部分がその部分のブロックサイズと同じブ
   ロックサイズを有する入力ベクトルに対するコードブッ
   クを構成することができる出力ベクトルとなるような出
   力ベクトルの組を、コードブックとして記憶するコード
   ブック記憶手段と、 前記入力ベクトルのブロックサイズを単位として、前記
   コードブックに記憶される前記各出力ベクトルの構成要
   素の一部分を用いて前記入力ベクトルをベクトル量子化
   するベクトル量子化手段と、 を有することを特徴とする階層式ベクトル量子化装置。