JPH0720244B2 - 画像信号ベクトル量子化器 - Google Patents

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、画像信号系列を複数個毎にベクトル化し、多
次元信号空間で量子化・符号化する画像信号ベクトル量
子化器に関するものである。

従来の技術 はじめに、木探索型ベクトル量子化の基本原理について
第７図と共に簡単に説明する。ベクトル量子化すべき入
力信号系列を、ｋ個毎にまとめてｋ次元の信号ベクトル
ｘ＝｛x₁，x₂，…，x_k｝とする。第７図にはｋ＝２の場
合の量子化例を示した。木探索構造の階層をｎで表すも
のとし、まずｘに対し第１階層（ｎ＝１）の量子化とし
て２次元信号空間R²（ｘ∈R²）を２分割する各部分空間
ｒ（１）ａ（ａ＝0,1）（ｒ（１）0Ur（１）１＝R²）の
代表ベクトルとして各々１個の量子化用ベクトルya＝
｛ya₁，ya₂｝（ａ＝0,1）のセットＹ（１）が与えられ
る。木探索型ベクトル量子化器・符号化部は、入力信号
ベクトルｘを量子化用ベクトルya（ａ＝0,1）に量子化
した場合に生ずる量子化歪ｄ（x,ya）がより小さいya
（即ち、ｘに対してより近距離にあるya）を選択する
（第７図でａ＝０））。次に、選択された第１階層にお
ける量子化用ベクトルy₀が代表する２つの第２階層（ｎ
＝２）の各部分空間ｒ(2)_b（ｂ＝0,1）の量子化用ベク
トルy_0b（ｂ＝0,1）のセットＹ（２）が与えられ、入力
信号ベクトルｘに対してより量子化歪の小さい量子化用
ベクトルy_0bを選択する（第７図ではｂ＝１）。以下同
様の操作を第Ｎ階層（ｎ＝４）の部分空間まで繰り返し
量子化ベクトルy₀₁₁₀を得る（第７図参照）。一般に、
各階層ｎにおける部分空間ｒ（ｎ）の量子化用ベクトル
は二者択一されるものであるため、部分空間上の量子化
用ベクトルは１ビット（０または１）で表され、第Ｎ階
層まで探索して得られた量子化ベクトルはｋ次元信号空
間R_kにおいてＮビットのアドレスで表すことができる。
従って、木探索型ベクトル量子化器・符号化部は量子化
ベクトルの代わりに、Ｎビットのアドレスを送出し、こ
れが伝送または記録される（第７図では４ビット。abcd
＝0110）。木探索ベクトル量子化器・復号部は木探索ベ
クトル量子化器・符号化部の木構造コードテーブルＹの
最終第Ｎ階層の出力ベクトルセット及びＮビットアドレ
スのみを記憶するコードテーブルメモリを持ち、入力さ
れたＮビットのアドレスにより出力ベクトルｙを再生す
る。

第８図，第９図，第10図に、従来の木探索型画像信号ベ
クトル量子化器の具体例を示し説明する。第８図（ａ）
のベクトル量子化器・符号化部に入力された１画面分の
画像信号系列Ｖ（480サンプル／ライン,480ライン）は
画素メモリ80に記憶された後、順次ブロック生成部81に
よって3600個の８（サンプル）×８（ライン）部分ブロ
ックBj、即ち64（＝８×８）次元画素ベクトルx_j＝｛x
_1j，x_2j，…，x_64j｝（ｊはブロック番号。ｊ＝１〜360
0）となり、ベクトル量子化部800に入力される。第８図
（ｂ）に示すベクトル量子化部においては、B_jからなる
画素ベクトルx_j＝｛x_1j，x_2j，…，x_64j｝が入力ベクト
ルレジスタ801にラッチされ、まず階層カウンタ810の出
力ｎ＝１及びアドレスポンイタ809の出力Ｐ（１）＝0,1
に従って、第10図に示すような木構造コードテーブルメ
モリ802内ベクトルセットＹの第１階層の量子化用ベク
トルy_P（１）＝｛yP(1)₁，yP(1)₂，…，yP(1)₆₄｝（Ｐ
（１）＝0,1）が出力ベクトルレジスタ803にラッチさ
れ、両レジスタ出力間の量子化歪ｄ（x_j,yP（１））が
並列減算器804,並列絶対値演算器805及び絶対値差歪演
算器806により順次計算される。なお、ここでは入力画
素ベクトルx_jと出力ベクトルyP（１）との量子化歪は、
二乗差歪測度と呼ばれる を用いている。差歪比較器807はｄ（x_j,yP（１））（Ｐ
（１）＝0,1）でより小さい値をとる出力ベクトルyP
（１）を選択し、対応するアドレスＰ（１）をminP
（１）ｊ（第10図ではminP(1)_j＝０）としてアドレスポ
インタ809に与える。同様にして、階層カウンタ810の出
力ｎ＝２及びアドレスポインタ809の出力Ｐ（２）＝min
P(1)_j・O,minP(1)_j・１（階層カウンタｎ＝１の場合に
選ばれたアドレスminP(1)_jを上位として、その下位に０
または１を加えて得られるアドレス。第10図ではＰ
（２）＝00,01）に従って、木構造コードテーブルメモ
リ802内ベクトルセットＹの第２階層の量子化用ベクト
ルyP（２）＝｛yP(2)₁，yP(2)₂，…，yP(2)₆₄｝（Ｐ
（２）＝00,01）と画素ベクトルx_jとの差歪計算が行わ
れminP(2)_j（第10図ではminP(2)_j＝00）が得られる。以
下、木構造コードテーブルメモリ802内ベクトルセット
Ｙの最終第８階層までの差歪計算の結果得られたminP
(8)_j（第10図ではminP(8)_j＝00000010）は８ビットとな
り、アドレスレジスタ808によりラッチ出力される。こ
れが64次元信号空間に対し８階層の木探索型ベクトル量
子化を行った場合の量子化ベクトルのアドレスを示すこ
とになる。このような木探索型の量子化方法を採ること
により１入力画素ベクトルx_j（１部分ブロックB_j）当り
の差歪計算回数を２×８＝16回と少なくすることができ
る。１画面総計16×3600（全部分ブロック数）回の差歪
計算の結果、ベクトル量子化部800より出力された3600
個の８ビットアドレスminP(8)_j（ｊ＝１〜3600）がイン
デックスとして出力され、これが伝送または記録され
る。

第９図のベクトル量子化器・復号部に入力された部分ブ
ロックB_jに対応するインデックス即ち８ビットのアドレ
スminP(8)_jは、インデックスレジスタ90にラッチされた
後、木探索型ベクトル量子化器・符号化部の最終第８階
層と同じ内容の８ビットアドレスＰ（８）＝00000000〜
11111111及びベクトルセットyP（８）＝｛yP(8)₁，yP
(8)₂，…yP(8)₆₄｝を持つコードテーブルメモリ91によ
りアドレスminP(8)_jに対応する出力ベクトルyP（８）＝
｛yP(8)₁，yP(8)₂，…，yP(8)₆₄｝（Ｐ（８）＝minP(8)
_j）に再生される。出力ベクトルyP（８）は出力ベクト
ルレジスタ92によりラッチ出力され、画像の部分ブロッ
クB_jとして画素メモリ93に順次書き込まれ１画面分の画
像信号系列Ｖ′を生成する。

また以上のような構成に加えて、第11,12図のように、
ベクトル量子化器・符号化部において、ブロック生成部
1101とベクトル量子化部1103との間にアダマール変換あ
るいは離散コサイン変換等の直交変換部1102を挿入し、
ベクトル量子化器・復号部において、出力ベクトルレジ
スタ1202と画素メモリ1204との間に逆直交変換部1203を
挿入することによって、画像信号系列そのものではな
く、画像の各周波数成分に対してベクトル量子化を施す
ような構成においても同様の手順で量子化・符号化及び
復号が行われる。

発明が解決しようとする課題 従来の木探索型画像信号ベクトル量子化器では、上記例
のように１画面分の全サンプルデータ（480サンプル／
ライン,480ライン）を８（サンプル）×８（ライン）ブ
ロック化した場合、得られた64（＝８×８）次元の画素
ベクトルに対して、最終第８階層の2⁸＝256種の出力ベ
クトルから木探索により２×８＝16回の差歪計算を行っ
て量子化ベクトル即ち８ビット符号のアドレスを選び出
し、１画面全体では16×3600（全ブロック数）回の計算
時間を要する。しかし、特に動画等の高速の処理速度を
必要とするようなデータに対しては更に高速の処理が要
求される。また、これらの画像信号の量子化データを伝
送・記録するにあたっては、８×８ブロックの画素ベク
トルを常時８ビット符号のアドレスで量子化するのでは
なく、適応的に量子化ビット数を減らして伝送・記録容
量を小さくすることが望ましい。

課題を解決するための手段 本発明によると、木探索型画像信号ベクトル量子化器・
符号化部は、符号化すべき画面を所定サイズの複数個の
量子化ブロックに分割し、更に各量子化ブロックを一様
に分布する所定の画素で構成される所定数の部分ブロッ
クに分割する。ベクトル量子化部が量子化ブロックの第
１の部分ブロックを量子化する際は、第１の部分ブロッ
クの画素ベクトルと全Ｎ（Ｎは正の整数）階層の木構造
出力ベクトル（総数２×（2^N−１）個）を記憶する木構
造コードテーブルメモリの第１階層から第Ｎ階層までの
量子化用ベクトル対の差歪値の小さい量子化用ベクトル
を順次選択、最終第Ｎ階層において得られた出力ベクト
ルのアドレスをＮビット符号で出力する。同時に第Ｎ′
（Ｎ＞Ｎ′は正の整数）階層における量子化用ベクトル
対において差歪値の小さい量子化用ベクトルのアドレル
Ｎ′ビットをアドレスメモリに記憶しておく。次に、量
子化ブロックの第2,3…の部分ブロックからなる画素ベ
クトルに対しては、前記アドレスメモリに記憶された第
Ｎ′階層における量子化用ベクトルのＮ′ビットアドレ
スを初期値とて第（Ｎ′＋１）階層から第Ｎ階層までの
量子化用ベクトル対の差歪値の小さい量子化用ベクトル
を選択し、最終第Ｎ階層における出力ベクトルのアドレ
スを初期値Ｎ′ビット符号のアドレスを除いた（Ｎ−
Ｎ′）ビット符号のインデックスとして出力する。ま
た、木探索型画像信号ベクトル量子化器・復号部は、前
記木構造コードテーブルメモリの第Ｎ階層のみの内容
（2⁸個のベクトルセット及びアドレス）を記憶したコー
ドテーブルメモリを備え、前述の木探索型画像信号ベク
トル量子化器・符号化部が量子化ブロックの部分ブロッ
クからなる画素ベクトルを量子化して得たアドレスを前
記Ｎ階層木構造コードテーブルメモリの第１階層から第
Ｎ′階層に相当するＮ′ビット符号（以下、上位アドレ
スと呼ぶ）と第（Ｎ′＋１）階層から第Ｎ階層に相当す
る（Ｎ−Ｎ′）ビット符号（以下、下位アドレスと呼
ぶ）とに分離して保持できる構造で、量子化ブロックの
第１の部分ブロックを量子化して得られたＮビット符号
のアドレスをコードテーブルメモリに与えて量子化ベク
トルを再生し、量子化ブロックの第2,3…の部分ブロッ
クを量子化して得られた（Ｎ−Ｎ′）ビット符号のアド
レスはこれを下位アドレスとし、第１の部分ブロックの
量子化によって得られた上位アドレスＮ′ビット符号と
合わせてＮビット符号のアドレスとしてコードテーブル
メモリに与えて量子化ベクトルを再生する。以上のよう
にして再生された量子化ブロックの第1,2,3…の部分ブ
ロックに対応する量子化ベクトルは、画素メモリ上で合
成される１画面を構成する。

作用 上記の方法により、画像信号の木探索型ベクトル量子化
を行う際、量子化ブロックを相関性の非常に強い部分ブ
ロックに分割することによって、第１の部分ブロックの
画素ベクトルの量子化については木構造コードテーブル
メモリの第１階層から第Ｎ階層の全階層の量子化用ベク
トル対との総計2N回の差歪計算によりＮビット符号化を
行い、第2,第３…の部分ブロックの画素ベクトルの量子
化では木構造コードテーブルメモリの第１階層から差歪
計算を行うのではなく、第１部分ブロック量子化の際に
得られた第Ｎ′階層における量子化用ベクトル即ちＮ′
ビット符号のアドレスを初期値として、第（Ｎ′＋１）
階層から第Ｎ階層までの総計２（Ｎ−Ｎ′）回の差歪計
算により最終第Ｎ階層における量子化ベクトルを求めそ
のアドレスＮビットから初期値Ｎ′ビット符号を除いた
（Ｎ−Ｎ′）ビットの符号化を行い、全体を通しての画
素ベクトルの量子化を効率良く行い、高速及び低容量の
符号化を可能とするものである。

実施例 （１） 本発明による木探索型画像信号のベクトル量子
化器の一実施例を第１図，第２図，第３図，第４図に示
し説明する。第１図（ａ）は、木探索型ベクトル量子化
器・符号化部の構成図である。画素メモリ10に入力され
た１フレーム画像信号V0（480サンプル／ライン,480ラ
イン）は、ブロック生成部11により、仮想的に24（サン
プル）×８（ライン）量子化ブロックbj（ｊはブロック
番号。ｊ＝１〜1200）に分割、更に各量子化ブロックbj
をブロック内サンプル点を一様に分散させる様に３組の
８（サンプル）×８（ライン）部分ブロックB_1j，B_2j，
B_3j（ｊ＝１〜1200）に分割する（第３図参照）。即ち
３組の64次元画素ベクトルx_1j，x_2j，x_3j（ｊ＝１〜120
0）が生成される。画像信号は本来隣接画素間の相関が
非常に強いものであるため、ｊを同じくする部分ブロッ
クB_1j，B_2j，B_3j、即ち64次元画素ベクトルx_1j，x_2j，x
_3jの間の相関性も強い。第１図（ｂ）に示すベクトル量
子化部は、第８図（ｂ）の従来例とほぼ同様の手順で、
ｊで指定される第１の部分ブロックB_1jからなる画素ベ
クトルx_1jに対して、切替器A112によって接続された階
層カウンタA110の出力ｎ＝１〜８に従って、木構造コー
ドテーブルメモリ102の第１階層から第８階層までの量
子化用ベクトル対との差歪計算ｄ（x_1j,yP（ｎ））（ｎ
＝１〜８）を１部分ブロック当り２×８＝16回行い、x
_1jに対して差歪値が最小となるような第８階層の出力ベ
クトルyP（８）即ち８ビトのアドレスminP(8)_j（第４図
ではminP(8)_j＝00000011）を求め、これをインデックス
ijとしてアドレスレジスタ108でラッチ後、出力する
（８ビット）。また、第１部分ブロックの量子化過程に
おいて、木構造コードテーブルメモリ102の第４階層に
おける量子化用ベクトルのアドレスminP(4)_j（第４図で
はminP(4)_j＝0000）を上位アドレスij（upper）として
アドレスメモリ114に記憶させておく（Ｎ′＝４）。次
に、ｊで指定される部分ブロックB2_jからなる画素ベク
トルx2_jに対しては、切替器112により階層カウンタB111
を接続、その出力ｎ＝５〜８に従い、まず木構造コード
テーブルメモリ102の第５階層において前記アドレスメ
モリ114に記憶された上位アドレスminP(4)_j（ij（uppe
r））を初期値としてアドレスポインタＰ（５）＝minP
(4)_j・0,minP(4)_j・１（第４図ではＰ（５）＝00000,00
001）の示す量子化用ベクトル対との差歪計算ｄ（x_2j,y
P（５））を行い、差歪の小さい量子化用ベクトルyP
（５）即ちアドレスminP(5)_jを求める。以下、第６階層
から第８階層まで同様の手順によりx_2jに対する差歪値
最小の第８階層の量子化用ベクトルyP(8)_jを求める。但
し、この時インデックスi_2jとしてアドレスレジスタ108
にラッチ出力するアドレスは８ビットのminP(8)_j（第４
図ではminP(8)_j＝00000100）ではなく、上位アドレス４
ビット（第４図ではminP(8)_j（upper）＝minP(4)_j＝000
0）を除いた下位アドレス（第４図ではminP(8)_j（lowe
r）＝0100）のみとする（４ビット）。同様に、ｊで指
定される部分ブロックB_3jからなる画素ベクトルx_3jに対
しても、階層カウンタB111の出力ｎ＝５〜８に従い上位
アドレスminP(4)_j（i_1j（upper））＝0000を初期値とし
て差歪計算を行い木構造コードテーブルメモリ102の第
８階層における差歪最小アドレス（第４図ではminP(8)_j
＝00000101）を求め、その下位アドレス（第４図ではmi
nP(8)_j（lower）＝0101）をインデックスi_3jとしてアド
レスレジスタ108でラッチ後、出力する（４ビット）。
このようにして64次元画素ベクトルx_1j，x_2j，x_3j（ｊ
＝１〜1200）に対応する各インデックスi_1j（８ビッ
ト），i_2j（４ビット），i_3j（４ビット）が出力され
る。

第２図のベクトル量子化器・復号部に入力されたインデ
ックスi_1j，i_2j，i_3j（ｊ＝１〜1200）は、８ビットのi
_1jは上位アドレスi_1j（upper）（４ビット）と下位アド
レスi_1j（lower）（４ビット）に分離され、各々上位ア
ドレスレジスタ24,下位アドレスレジスタ25にラッチさ
れる。４ビットのi_2j，i_3jは共に下位アドレスレジスタ
25にラッチされ、上位アドレス24にラッチされたi_1jの
上位アドレスi_1j（upper）と合わせ、各々８ビットのア
ドレスi_2j′，i_3j′を構成する。８ビットアドレス
i_1j，i_2j′，i_3j′は、各々木探索型ベクトル量子化器
・符号化部の木構造コードテーブルメモリの第８階層に
おける2⁸個の出力ベクトルセット及びアドレスを記憶し
たコードテーブルメモリに与えられ、64次元の出力ベク
トルy_1j，y_2j，y_3j（ｊ＝１〜1200）を再生、順次画素
メモリ23に記憶され、１フレーム分の画像信号V₀′を再
生する。

（２） 第２の実施例とて、第５図，第６図には、第１
の実施例の木探索型ベクトル量子化器・符号化部におい
てブロック生成部51とベクトル量子化部500の間に直交
変換部52を挿入、木探索型ベクトル量子化器・復号部に
おいて出力ベクトルレジスタ62と画素メモリ63の間に逆
直交変換部66を挿入して、画像信号系列の周波数成分に
対してベクトル量子化を施す構成を示したが、この例に
おいても前記実施例１と同様の手順によってベクトル量
子化を行うことができる。

発明の効果 本発明によれば、画像信号の木探索型ベクトル量子化の
際、量子化ブロックを相関性の非常に強い部分ブロック
に分割し、第１の部分ブロックの画素ベクトルに対し木
構造コードテーブルメモリを探索し量子化する過程にお
いて、その途中階層における量子化用ベクトル即ちアド
レスを記憶しておき、第2,第３…の部分ブロックの画素
ベクトルに対しては、この量子化用ベクトル即ちアドレ
スを初期値として用いて前出の途中階層の次階層から木
構造コードテーブルメモリを探索・量子化することによ
り、全体を通しての画素ベクトルと量子化用ベクトルと
の差歪計算回数を少なくし、また、第2,第３…の部分ブ
ロックの画素ベクトルの量子化ベクトルのアドレスは、
その一部を第１の部分ブロックの画素ベクトルに対する
量子化ベクトルのアドレスを併用することにより少ない
ビット数で表現し、高速かつ低容量のベクトル量子の実
現を可能とするものである。

【図面の簡単な説明】

第１図、第２図は本発明における一実施例のベクトル量
子化器の構成図、第３図は同実施例の動作説明図、第４
図は木構造コードテーブルの説明図、第５図、第６図は
本発明の他の実施例のベクトル量子化器の構成図、第７
図は木探索型ベクトル量子化の基本原理説明図、第８
図、第９図は従来のベクトル量子化器の構成図、第10図
は木構造コードテーブルの説明図、第11図、第12図はベ
クトル量子化器の構成図である。 10……画素メモリ,11……ブロック生成部,100……ベク
トル量子化部,101……入力ベクトルレジスタ,102……木
構造コードテーブルメモリ,103……出力ベクトルレジス
タ,104……並列減算器,105……並列絶対値演算器,106…
…絶対値差歪演算器,107……比較器,108……アドレスレ
ジスタ,109……アドレスポインタ,110……階層カウンタ
A,111……階層カウンタB,112……切替器A,113……切替
器B,114……アドレスメモリ,20……インデックスレジス
タ,21……コードテーブルメモリ,22……出力ベクトルレ
ジスタ,23……画素メモリ,24……上位アドレスレジス
タ,25……下位アドレスレジスタ。

Claims (4)

【特許請求の範囲】
1. 【請求項１】符号化すべき画面を記憶する画素メモリ
   と、前記画素メモリに記憶された画面を所定サイズの複
   数個の量子化ブロックに分割し更に前記各量子化ブロッ
   クを一様に分布する所定の画素で構成される所定数の部
   分ブロックに分割するブロック生成部と、出力ベクトル
   を含む２×（2^N−１）（Ｎは正の整数）個の量子化用ベ
   クトル及びアドレスを記憶するＮ階層の木構造コードテ
   ーブルメモリと、前記量子化ブロックの第１の部分ブロ
   ックの画素ベクトルに対しては前記木構造コードテーブ
   ルメモリの第１階層から木探索型ベクトル量子化を行い
   第Ｎ階層の出力ベクトルのアドレスをＮビット符号で出
   力すると同時に第Ｎ′（Ｎ＞Ｎ′は正の整数）階層にお
   ける木探索型ベクトル量子化で得られたＮ′ビットのア
   ドレスをアドレスメモリに記憶し、量子化ブロックの第
   １の部分ブロック以外の部分ブロックの画素ベクトルに
   対しては前記アドレスメモリに記憶されたＮ′ビットア
   ドレスを初期値として前記木構造コードテーブルメモリ
   の第（Ｎ′＋１）階層から木探索型ベクトル量子化を行
   い第Ｎ階層の量子化によって得た出力ベクトルのＮビッ
   トアドレスから前記アドレスメモリに記憶されたＮ′ビ
   ットアドレスを除いた（Ｎ−Ｎ′）ビット符号を出力す
   るベクトル量子化部と、量子化ブロックの第１の部分ブ
   ロックの画素ベクトルを量子化する際には１からＮをカ
   ウントし量子化ブロックの第１の部分ブロック以外の部
   分ブロックの画素ベクトルを量子化する際にはＮ′から
   Ｎをカウントする階層カウンタと、量子化ブロックの第
   １の部分ブロック以外の部分ブロックの画素ベクトルを
   量子化する際にのみベクトル量子化部に前記アドレスメ
   モリを接続する切替器とを具備してなる木探索型画像信
   号ベクトル量子化器・符号化部。
2. 【請求項２】特許請求の範囲第１項記載の木探索型画像
   信号ベクトル量子化器・符号化部が量子化ブロックの部
   分ブロックの画素ベクトルを量子化して得たアドレスに
   対し前記木構造コードテーブルメモリの第１階層から第
   Ｎ′階層に対応するＮ′ビット符号を保持する上位アド
   レスレジスタと、第Ｎ′階層から第Ｎ階層に対応する
   （Ｎ−Ｎ′）ビット符号を保持する下位アドレスレジス
   タと、前記木構造コードテーブルメモリの第Ｎ階層の出
   力ベクトル及びＮビットアドレスを記憶するコードテー
   ブルメモリと、前記コードテーブルメモリによって再生
   された前記量子化ブロックの各部分ブロックの出力ベク
   トルを合成して画像信号系列とする画素メモリとを具備
   してなる木探索型画像信号ベクトル量子化器・復号部。
3. 【請求項３】特許請求の範囲第１項において、ブロック
   生成部とベクトル量子化部との間に直交変換部を挿入し
   てなる木探索型画像信号ベクトル量子化器・符号化部。
4. 【請求項４】特許請求の範囲第２項において、画素メモ
   リの直前に逆直交変換部を挿入してなる木探索型画像信
   号ベクトル量子化器・復号部。