JPH0262167A - ベクトル量子化の最適出力ベクトル探索方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔鷹要〕 画像信号あるいは音声信号の高能率符号化などに用いら
れるベクトル量子化の最適出力ベクトル探索方法に関し
。

最適出力ベクトル探索のための計算マを削減して探索処
理の高速化を図ることを目的とし要素の正負対称性のな
い複数の出力ベクトル１−禎を格納するコードブックが
用意され、入力ヘクトルと出力ベクトル候補の内積の絶
対値に基づきＩｊｋ　’Ａな出力ベクトル候補が該コー
ドブック中から探索され、この内積値の正負に応じて最
適な出力ベクトル候補あるいはそれと要素が正負対称な
出力ベクトル候補の何れか一方がＨＡ出力ベクトルとし
て出力されるように構成される。

〔産業上の利用分野〕

本発明は３画像信号あるいは音声信号の高能率符号化な
どに用いられるベクトル９子化、特に出力ベクトルの構
成要素の平均値が零、標準偏差が一定値に正規化された
ＧＡＩＮ／５ＩＩＡＰＦベクトル９子化に通した。ベク
トル量子化の最適出力ベクトル探索方法に関する。

〔従来の技術〕

画像信号あるいは音声信号の高能率符号化に用いられる
ベクトル量子化として、　ＧＡＩＮ／５ＩＩＡＰＥベク
トル量子化がある。このＧＡＩＮ／Ｓｌｌ＾ＰＥベクト
ル量子化は、入力信号（入力ベクトル）からその要素の
平均値を引いて標準偏差で正規化するものであり。

用意されているコードブック中の出力ベクトルは要素の
平均値が全て零で、標準偏差σが例えばσ＝１に正規化
されている。

このベクトル量子化におけるｂｋ通出力ベクトルの探索
方法は、入力ベクトルとコードブック中の全ての出力ベ
クトルとを比較し、距離（誤差）が最も少ない出力ベク
トルを検出して最適出力ベクトルとするものである。

〔発明が解決しようとする課題〕

−ａ的なベクトル量子化では、最適出力ベクトルの探索
に際してコードブック中の全ての出力ベクトルを探索し
て誤差計算をする必要がある。このためコードブック中
の出力ベクトル数が多いと計算量も多大となり、探索に
要する時間が長くかかってしまうという問題点がある。

したがって本発明は、最適出力ベクトル探索のための計
算量を削減して探索処理の高速化を図ることを目的とす
る。

〔課題を解決するための手段〕

第１図は本発明に係る原理説明回である。本発明に係る
ベクトル量子化の最適出力ベクトル探索方法においては
、要素の正負対称性のない複数の出力ベクトル候補ｙ、
十が格納されるコードブックＹ＋が用意される（ステッ
プＳｌ）。このコードブック中の各出力ベクトル候補ｙ
、十と入力ベクトルＸとの内積をそれぞれ求め（ステッ
プＳ２）、この内積の絶対値に基づきこの内積値の絶対
値が最大なものを最適な出力ベクトル候補ｙｏ＋とじて
該コードブック中から探索する（ステップ３３）。

次いで内積値の正負に応じて最適な出力ベクトル候補７
ｏ　＋、あるいはこの出力ベクトル候補ｙｏ＋と構成要
素の正負が反転している対称な出力ベクトル候補ｙｏ−
の何れか一方を最適出力ベクトルとして出力する（ステ
ップ３４）。

〔作用〕

コードブック中の出力ベクトル候補ｙＩ十と入力ベクト
ルＸの内積演算を行い、そのうちの例えば絶対値が最大
となるものを最適出力ベクトル候補ｙｏ÷として選び出
す。この内積の符号が例えば正であるときにはそのｉＪ
出力ベクトル候補ｙｏ十をそのまま最適出力ベクトルと
して出力し。

一方、内積の符号が負のときには最適出力ベクトル候補
ｙｏの各要素の符号の正負を反転させたベクトルｙｏ−
を最適出力ベクトルとして出力する。

これによりコードブック中に保持する出力ベクトル候補
の数を半減することができ、よって探索のための演算回
数が半減するので、最適出力ベクトル探索処理の高速化
を図れる。

〔実施例〕

以下１図面を参照しつつ本発明の詳細な説明する。この
実施例は動き補償フレーム間予測符号化回路に本発明の
方法を適用したものである。

第２図において、ｌは減算器であって、１ブロツクの入
力画像へと予測値Ｐとの差分を求めて予測誤差Ｘを出力
する。２はＧＡＩＮ／ＳＨ＾ＰＦ、ベクトル精子化鼎で
あって、１ブロツクの予測誤差Ｘが入力ベクトルＸとし
て入力されてＧＡＩＮ／５ＨＡＰＥベクトル量子化を行
い、量子化値Ｘ′および予測誤差情報として平均値ｍ′
、ゲインｆ１．ベクトルインデックスｉを出力する。こ
こで入力ベクトルＸはに個の要素（画素）からなり。

ｘ＝　（ｘｌ　、Ｘ２−−−−−−ｘｋ　）で表される
。

３は加算器であって、量子化値Ｘ′と予測値Ｐとを加算
して局部復号信号Ａ′を発生する。４は入力信号を約１
フレーム遅延させることによって前画面を記憶するフレ
ームメモリ、５はフレームメモリ４の前画面と入力され
た現画面の入力画像Ａとを比較して入力画像への勅き？
（動きベクトルＶ）を検出する動き補償器、６は動き補
償′／：ｔ５からの動きベクトルＶに応じてフレームメ
モリ４の前画面を偏位させて動きＴｔ＋　ｍ予測値Ｐを
発生する可変遅延型である。

この動き補償フレーム間符号化回路におけるＧＡＩＮ／
５ＩＩＡＰＥベクトル量子化器２の詳細な構成が第３図
に示される。第３図において、２０はコードブックであ
って、予め用窓された複数（ｎｌ＆１）の出力ベクトル
候補ＶＩ　（ｉ＝ｌ〜ｎ）の集合Ｙからなる。各出力ベ
クトル候補ｙ、はに個の要素からなり ’！＝　　（ｙ　＋　Ｉ　、ｙ　＋　□、−−−ｙＩｋ
）と表され、これらの集合Ｙは。

Ｙ＝　（７１、ｙ２−−−−ｙｎ　ｌ と表される。

この出力ベクトル候補ｙ、は平均値が零で、正規化され
ているベクトルであるので、平均値ｍは。

ｋ　　　ｊ＝１ となり、標準偏差σは。

となる。これらの出力ベクトルは一般に（ｋ−１）次元
の超球面一ヒにある。

コードブック２０中の出力ベクトル族Ｍ　７　＋は相互
に要素が正負対称となるものは含まない。すなわち、あ
る出力ベクトル群をＹ十とし、これと各要素が正負対称
となっている出方ベクトル群をＹ−とすれば、コードブ
ック２ｏ中に含まれる出力ベクトル候補はこれらＹ＋ま
たはＹ−の何れか一方である。Ｙ命中の出力ベクトル候
補を。

７＋　”＝　（ｙｌ　１　”ｒ　　ｙｉ　２”＋　”−
”’−ｙ１に＋１とすると、この出力ベクトル候補ｙ、
十の各要素の符号を反転したものがＹ−中の出方ベクト
ル候補となり。

Ｙ＋−＝（）’ｌｌ”、ＹＩ２”−−−−３’ｉｋ”）
＝　（ｙｌ＋−、ｙｔ　２−＋　　”−””ｙｉ　ｋ−
）と表される。したがってコードブック２ｏ中の出力ベ
クトル候補の数は、Ｙ十とＹ−を両方とも用窓じた場合
（Ｙ＝Ｙ＋　ＵＹ−）と比較するとＹ十またはＹ−の何
れか一方のみであり、その数は半分になる。

２１はゲイン計算及び出力ベクトル探索回路であって、
入力ベクトルＸとコードブック２５中の出力ベクトル族
？！３１’＋　とのゲイン（内積：ｇ＋）計算を行って
最適な出力ベクトルの探索を行いそのゲインｇｉとベク
トルインデックスｉとを出力する。

２２は入力ベクトルＸの要素の平均値ｍ′を求める平均
値演算回路、２３はＧＡ　ＩＮ／５）ＩＡＰＥベクトル
量ｒ化器２からのゲインｇ＋とコードブック２５からの
出力ベクトル候補の要素ｙｊとを乗算する乗算器、２４
は乗算器２３からの出力ｇＩ　’！Ｊと平均値演算回路
２２からの平均値ｍ′とを加算して元信号の再生を行う
加算器である。

ゲイン計算及び出力ベクトル探索回路２１の詳細な構成
が第４図に示される。第４図において。

２１１は入力ベクトルＸの要Ｎｘｊと出力ベクトル候補
ｙ、の要−！ＩＥｙｊとを乗算する乗算器、２１２は各
要素の乗算値の総和演算を行う加算器、２１３はレジス
タ、２１４は絶対値をとる絶対値演算回路、２１５は最
大値を検出する最大値検出回路、２１６はレジスタであ
り、最大値検出回路２１５からはゲインｇｌが最大とな
る出力ベクトル候補ｙＩのベクトルインデックスｉが出
力され。

レジスタ２１６からはその時のゲインｇｉが出力される
。

実施例装置の動作が以下に説明される。

ＧＡＩＮ／Ｓｌｌ＾ＰＥベクトル量子化塁２において人
量子化上２Ｘに最も距離が近い出力ベクトル族ｉｆ　７
　ｒをコードブック２０中から探索するには２次の式で
定義される入力ベクトルＸと出力ベクトル候補ｙＩの歪
みｄ、を出力ベクトル候補の集合Ｙについて求め、この
うち歪みｄ、が最小となるものを最適出力ベクトルイ哄
補ｙｏとする。すなわら。

と定義し、最適出力ベクトル（候補ｙｏの探索は。

ｓｉｎ　　ｄ　Ｉ　＝ｓｉｎ　　　　ｘｙｌ （ここでｉ　＝　１−ｎ） を満たすｉを探索することによる。ここで、歪みｄ、は
。

ｄｌ＝　　ｘ　　７１　　　＝Σ（ｘｊｊ・１ ｙｉ　１　）２ で表される。この式のうち、第１項は入力ベクトルＸの
みに依存して値が定まり、また第３項はコードブックが
正規化されており出力ベクトルによらず一定の値となる
ので、結局、歪みｄ、を最小にするｊは、第２項の入力
ベクトルＸと出力ベクトル候補ｙ１の内積（ゲイン）。

２ΣＸｊ　’）’ＩＪ ｊ＝１ を最大にするｉであることが分かる。よってこの内積値
を最大にするｉを求めることによって最適出力ベクトル
ｙ。を探索することができる。

ここでコードブック２０の中には、ＹＪまたはＹ−のう
ちのＹ十の方だけが格納されているものとする。集合Ｙ
十の中の出力ベクトル量子化と入力ベクトルＸとの内積
値の絶対値ｈＩ。

ｈＩ＝ｘ−Ｉ！” をそれぞれ求め、このうちから絶対値ｈｉが最大となる
ｉを求める。このとき。

ｇｌ＝ｘ　　−７１＋　≧　Ｏ であれば、ＹＪ十が最適出力ベクトルｙｏとして選択さ
れ。

ｇｌ〈０ であれば、−ｙ、＋　＝ｙ、−が選択される。

この結果、内積演算の回数は、出力ベクトル集合Ｙとし
てＹＪとＹ−の両方をもつ場合と比較して半分に減らす
ことができる。このようにコードブック中のベクトルの
対称性を利用することによって演算回数を半減すること
ができる。

このことは見方を変えれば、正負対称性がないＹしか予
め用意されていないコードブックの中からｈｉを最大に
するｉのベクトルを探し、ｈＩ≧０ならばそのベクトル
を出力し、ｈｉ＜Ｑならば選択されたベクトルの全ての
要素の符号を反転したベクトルを出力することによって
、あたかもコードブック中に２倍の出力ベクトルを持っ
ていることと等価になる。

なお、入力ベクトルの再生は、入力ベクトルＸの平均値
を ｋ　　　ｊ＝１ とすると、再生値、　Ｊ　ｆ　は。

ＹＪ　’　””ｍ’　＋　ｇ　ｉ　　’　Ｙｊにより求
めることができる。

〔発明の効果〕

本発明によれば、内積演算をＮ回行うことにより、Ｎ個
の出力ベクトル候補とその各要素の正負を反転したＮ個
の出力ベクトル候補の合計２Ｎ個の探索を行ったのと等
価になる。また見方を変えれば同数の出力ベクトル候補
に対して本発明方法によれば従来方法よりも演算回数が
半分となり。

最適出力ベクトルの探索演算の高速化を図れる。

【図面の簡単な説明】

第１図は本発明に係るベクトル量子化の最適出力ベクト
ル探索方法の原理説明図。 第２図は本発明の一実施例としてのベクトル量子化の最
適出力ベクトル探索方法を行う動き補償フレーム間予測
符号化回路を示すブロック図。 第３図は第２図実施例回路におけるＧＡＩＮ／５ＩＩＡ
ＰＩＩ’ベクトル量子化器２の詳細な構成例を示すブロ
ック図、および。 第４図は第３図回路におけるゲイン計算及び出力ベクト
ル探索回路２１の詳細な構成例を示すブロック図である
。 図において。 １−−一減算器 ２−Ｇ＾ＩＮ／５ＩＩＡＰＩベクトル！七子化器３．２
４，２１２−加算器 ４−　フレームメモリ ５−動き補償器 ６−可変遅延器 ２０−　コードブック ゲイン計算及び出力ベク 平均値演算回路 ２１１−乗算器 ２１６−−レジスタ 絶対値演算回路 最大値検出回路 ２３゜ ２１３゜ トル探索回路

Claims (1)

1. 【特許請求の範囲】 要素の正負対称性のない複数の出力ベクトル候補が格納
   されるコードブックが用意され、入力ベクトルと該出力
   ベクトル候補の内積の絶対値に基づき最適な出力ベクト
   ル候補が該コードブック中から探索され、 該内積値の正負に応じて該最適な出力ベクトル候補ある
   いはそれと正負対称な出力ベクトル候補の何れか一方が
   最適出力ベクトルとして出力されるように構成されたベ
   クトル量子化の最通出力ベクトル探索方法。