JPH02237270A - 符号化装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、ベクトル量子化手法によって、例えば画像情
報等の信号を符号化するための符号化装置に関するもの
である。

［従来の技術］ 従来、ベクトル量子化による符号化器は、第１３Ａ図に
示すように、人力ベクトルと、メモリ１に格納されてい
るコードブック内の再生ベクトルとの距離を演算器２で
演算し、これらの演算結果に基づいて比較器３で最短距
離の再生ベクトルを選択して、そのコードを出力すると
いうものである。また、第１３Ｂ図に示すように、予め
入カベクトルに対して最短距離にあるベク］一ルを予め
求め、それらをメモリ４に記憶しておくようにし、人力
ベクトルを与えると再生ベクトルのコードか得られるル
ックアップテーブル（以下、ＬＵＴと略す）方式によっ
て構成されていた。

［発明が解決しようとしている課題コ しかしながら前者の演算器による構成（第１３Ａ図）で
は、人力ベクトルが高次元になればなるほど、演算回路
や比較器の規模が増大するために、コストやスピードの
面で問題がある。

また、ＬＵＴ方式（第１３Ｂ図）はスピードやコストの
面での問題は解決しているが、入力ベクトルの次元が高
くなると以下のような欠点がある。

（ｉ）：多次元のベクトル量子化器のＬＵＴを全探索型
で行う場合には、膨大な演算時間とハードウエアが必要
であり、符号化効率、コストの面で問題がある。

（ｉｉ）：メモリの容量が素子の大きさによって制限さ
れてしまい、ＲＯＭ等での構成が難しい。

（ｉｉｉ）　：　Ｌ　Ｕ　Ｔの前にスカラ量子化器を設
定しただけでは、ベクトルの要素間ての相関が利用でき
ず、効率，画質が低下する。

即ち、演算器方式よりもスピードの面で勝ると言われる
ＬＵＴ方式てあっても、入力信号によっては、演算速度
の低下や、符号化効率や画質の劣化等の問題が残ってい
るのである。

［課題を解決するための手段コ そこで本発明は、これら従来の演算器方式やＬＵＴ方式
の有する演算速度、符号化効率や回路規模等の問題を、
ベクトル量子化を多段で構成することにより解決したも
のである。

この課題を達成するための本発明の符号化方法に係る構
成は、前もってトレーニングデータから作成したコード
ブックを用いて、信号のベクトル量子化を行う符号化方
法において、入力信号ベクトルを表すｎ次元ベクトルを
、各々がｐ次元（ｐ＜ｎ）の複数のベクトル空間に分割
する第１の工程と、これらの分割された個々のベクトル
を、同じ空間をもつコードブックによりベクトル量子化
する第２の工程と、上記工程によりベクトル量子化され
た個々の量子化結果をｑ次元（ｑ≦ｎ）のベクトルに合
成する第３の工程と、このｑ次元のベクトルを、これら
が表すベクトル空間の構成をもつコードブックによりベ
クトル量子化する第４の工程と、ｑ＝ｎとなるまで、上
記第３，第４の工程を繰り返す第５の工程とからなるこ
とを特徴とする。

また本発明の符号化装置に係る構成は、前もって１・レ
ーニングデータから作成したコードブックを用いて、信
号のベクトル量子化を行う符号化装置において、入力信
号ベクトルを表すｎ次元ベクトルを、各々がｐ次元（ｐ
＜ｎ）の複数のベクトル空間に分割する分割手段と、こ
れらの分割された個々のベクトルを、同じ空間をもつコ
ードブックによりベクトル量子化する第１のベクトル量
子化手段と、この第１のベクトル量子化手段によりベク
トル量子化された個々の量子化結果をｑ次元（ｑ≦ｎ）
のベクトルに合成する合成手段と、このｑ次元のベクト
ルを、これらが表すベクトル空間の構成をもつコードブ
ックによりベクトル量子化する第２のベクトル量子化手
段とを有し、少なくとも、ｑ−ｎとなるまで、上記第１
のベクトル量子化手段と、合成手段と、第２のベクトル
量子化手段とを複数段に線形に配列したことを特徴とす
る。

また、本発明のコードブックの作成方法に係る構成は、
ｐ次元の入力信号ベクトルとｑ次元の入力信号ベクトル
の各々を夫々第１，第２のコードブックを用いてベクト
ル量子化し、これらの２つの量子化結果を合成して得た
ベクトルを第３のコードブックにより更に量子化する符
号化方式におりる前記第３のコードブックの作成方法で
あって、第１及び第２のコードブックによる量子化によ
っては、第３のコードブックで使用されることのない再
生ベクトルを抽出する第１の工程と、この抽出された再
生ベクトルを第３のコードブックから削除する第２の工
程とを具備したことを特徴とする。

［実施例］ 以下添付図面を参照して、木発明を画像信号の符号化に
適用した実施例を第１実施例〜第３実施例まで３つ挙げ
て説明する。

〈第１実施例〉 第１図は第１の実施例に係る符号化装置を示す構成図で
ある。図中、１０は本装置の画像信号をベクトルの形で
入力するための入力端予てある。

この画像データとしてのベクトルは、４×４の画像ブロ
ックに対してアダマール変換を施して得たものてある。

また、１１は入力されたベクトルを部分空間に細分割す
る分配器である。１２ａ〜ｄは人力されたシーケンスを
シーケンス毎にスカラ量子化するスカラ量子化器であっ
て、ＳＱと略して図中に示す。１３ａ〜１３ｇはベクト
ル量子化器であって、このうち、１３ａ〜１３ｄは入力
されたベクトルに最短距離にあるベクトルのコードを格
納してあるＬＵＴメモリであり、１３ｅ〜１３ｇは入力
されたベクトルコードの表すベクトル等に最短距離にあ
るベクトルのコードを格納してあるＬＵＴメモリから構
成される。即ち、１３ａ〜１３ｄの４つのベクトル量子
化器が並列に配置され、これら４つの量子化器に対して
直列に、１３ｅ．１３ｆの２つの量子化器（１３ｅ，１
３ｆは互いに並列の関係になる）と、１３ｇの量子化器
が配置ざれている。また、１４はベクトル量子化ざれた
出力結果としてのコードの出力端子である。

実施例の画像の符号化は、４×４のブロックを切り出し
、ブロック単位でこれに前処理（本実施例では、一例と
してアダマール変換）を施し、その結果をベクトル量子
化することによって、画像を符号化する際のベクトル量
子化における写像ベクトルの決定する。ベクトル量子化
の概念は、以下に述べる全実施例において共通するもの
である。ヘク１・ル量子化は木質的に優れた符号化であ
り、スカラー量子化と比較して、量子化歪を大幅に改善
する事が可能である。

第２図に従って、簡単にベクトル量子化の概念を述べる
。入力信号をＫ個毎にブロック化して、このブロックを
第２図の説明の便宜上、Ｋ次元のベクトルＸで表すもの
とする。ベクトル量子化とは、このＸから前もって用意
されたＮ個のベクトルの集合への写像として見る事が出
来る。このＮ個のベクトルを出力ベクトルと呼び、この
集合をコート・ブック（又は、出力ベクトル・セット）
と呼ぶ。第２図はベクトル量子化の基本的な構成を示し
ている。

今、入力信号系のＫ個のサンプルをブロック化して人力
ベクトル ．Ｘ＝　（Ｘ＋　，Ｘ２　．Ｘ３．”’．Ｘｋ）とする
。これらのベクトルの集合はＫ次元ユークリット信号空
間Ｒｋを構成する。この空間Ｒｋハ、前もって所定のア
ルゴリズム（トレーニング）により、ｎ個の部分空間Ｐ
Ｉに分割されているものとする。Ｐ１を構成するベクト
ルは既知であるとする。この部分空間を構成ベクトルと
して、部分空間Ｒ＋の代表ベクトルＲ，を選ぶ。従って
、もし ＸεＲ， てあるならば、その指標（インデックス・ナンバー）ｉ
は入力ベクトルＸを表わすことができる。

即ち、このｉを伝送、または蓄積することにより、圧縮
／符号化が可能となる。そして、復号側では、複号側の
コードブックの同じｉ番地に格納されたＫ次元ベクトル
、 Ｒ　＋　””　（　ｒ＋，ｒ２，ｒ３．”’＋　　ｒ　
Ｊを入カベクトルＸの再生ベクトルとして出力する。こ
の様な Ｘ→Ｒ１ のような写像Ｆ Ｆ　：Ｒｌ　＝ｆ　（Ｘ） をベクトル量子化と呼ぶ。この写像はＸをＲＩに写像す
る事による歪が最小となるように行われる。即ち、コー
ドブックは、ある定められたトレニング・シーケンスに
従って、平均歪を極小にするように生成される。ベクト
ル量子化はブロックを単位として量子化を行う手法であ
り、この次元数、即ちブロックの大きさを犬き〈する事
によって理論的なデータ圧縮限界に近づく事が知られて
いる。また、量子化誤差がランダム化される為、画像信
号を対象とした場合にはＳ／Ｎ比の割に高い再生品位が
得られる。

次に、本実施例に用いられるアダマール変換について説
明する。このアダマール変換は直交変換の一形態である
が、かかる直交変換は、ベクトル量子化の前処理とＬ，
て特に好適だからである。

尚、このアダマール変換は第１〜第３実施例に共通のも
のである 例示として、符号化の対象画像を白黒多値画像とし、各
画素が８ビットの情報量であるとする。

アダマール変換は、例えば第３Ａ図に示すような、４×
４画素のブロックに対して施される。

ｘｌ，１（ｉ・１・・４，　ｊ−１・・４）は画像の画
素を表す。

このＸＩＪを行列Ｘを用いて表すと、 Ｘ　−　［Ｘ１１，Ｘ１２，Ｘ１３，Ｘ１４，Ｘ２１．
Ｘ２２，Ｘ２３，Ｘ２４，Ｘ３１，Ｘ３２，．Ｘ３３．
Ｘ３４．Ｘ４１．Ｌ２．Ｘ４３．Ｘ４４］Ｔ−　（　１
　）となる。但し、上式中のＴは転置行列を示す。この
Ｘに対してアダマール変換を施した結果をｙ目（Ｊ−１
・・４．ｊ−　１・・４）とすると、このｙＩＪで表さ
れる行列Ｙは、 Ｙ　　＝　　［ｙＩ＋１ｙＩ２・ｙ１３・ｙｌ４１ｙ２
１・Ｖ２２　＋ｙ２３１ｙ２４Ｙ３１１ｙ３２・Ｖ３３
１ｙ３４・ｙ４１．ｙ４２・ｙ４３　，Ｙ＜４１”・・
・　（２） である。すると、行列Ｘから行列Ｙへの変換は以下の（
３）式で表される。

ここで、Ｉ｛＋ａは１６欣のアダマール行列であり、次
の式で表される。

［以下余白］ ４×４の画素ブロックにアダマール変換を施して得られ
た係数をシーケンシと呼ぶ。即ち、４×４の画素ブロッ
クについては、１６個のシーケンシが得られる。このう
ち、ｙ＋＋は直流成分であり、残りの１５個の交流成分
を量子化の対象とする。

さて、１５個のシーケンシの量子化に際し、１シーケン
シ当りの情報量を１０ビットとすると、従来のＬＵＴ方
式では、 １０（ビット）　Ｘｉ　５＝１　５０　（ビット）の情
報量をアドレスとするメモリをＬＵＴに用いる必要があ
り、これが回路の大規模化にっなかったことは前述した
通りである。そこで、第１実施例では、入力ベクトル空
間を部分空間に分割する。これは次の理由による。シー
ケンシは周波数のパワーを示しており、前処理としての
直交変換かアダマール変換であれは、４×４のシーケン
シは、一般に、左上が低周波、右下が高周波という傾向
を示す。また、各シーケンシの周波数的に近いところは
分散が等しくなる傾向があるから、ベクトル量子化を行
うにはこのようなところで新たなベクトルを形成して量
子化することが適している。即ち、低周波部分と高周波
部分とに分割して新たなベクトルを構成すると、この新
たなベクトルのタイナミツクレンジは近接しているから
、このベクトルをベクトル量子化しても量子化歪みは少
ないことになる。

第３Ａ図は、この第１実施例の分配器１１に適用されて
いる４×４ベクトルの空間分割を表す図である。シーケ
ンシ２０ａは直流成分であり、前述したように、ベクト
ル量子化の対象から除外する。他の１５個の交流成分シ
ーケンシ２０ｂ〜２０ｐを本符号化装置の端子１０より
入力する。分配器１１は、シーケンシ２０ｂ〜２０ｐを
以下に続くスカラ量子化器に、第３Ａ図に示すように分
配する働きをする。即ち、分配器１１は人力のベクトル
空間を部分空間に分割するもので、具体的には、シーケ
ンシ２０ｂ，２０ｅ，２０ｆをスカラ量子化器１２ａへ
、シーケンシ２０ｃ，２０ｇ，２０ｉ，２０ｊをスカラ
量子化器１２ｂへ、シーケンシ２Ｑｄ　　２０ｈ．２０
ｍ，２０ｎをスカラ量子化器１２ｃへ、シーケンシ２Ｃ
ｌｋ，２０１，２０ｏ，２Ｑｐをスカラ量子化器１２ｄ
へ分配する。各スカラ量子化器は各シーケンシを次のベ
クトル量子化器１３ａ〜＋３６を最小の個数のＲＯＭで
構成てぎるビット数まで量子化する。

尚、これらのスカラ量子化器１２ａ〜１２ｄはシーケン
シの数と等しい個数のＲＯＭで構成されるか、ラッチを
用いて少ないＲＯＭで構成することが可能である。

スカラ量子化器１２ａからはシーケンシ２０ｂ，２０ｅ
，２０ｆによるスカラ量子化後の３次元ベクトルが出力
され、スカラ量子化器１２ｂからはシーケンシ２０ｃ，
２０ｇ，２０ｉ，２０ｊによるスカラ量子化後の４次元
ベクトルが出力され、スカラ量子化器１２ｃからはシー
ケンシ２０ｄ．２０ｈ，２０ｍ，２０ｎによるスカラ量
子化後の４次元ベクトルが出力され、スカラ量子化器１
２ｄからはシーケンシ２０ｋ，２０１，２０ｏ，２０ｐ
によるスカラ量子化後の４次元ベクトルが出力される。

各ベクトル量子化器１３ａ〜１３ｄは、これらのスカラ
量子化器から与えられた３次元ないしは４次元のベクト
ルに対して量子化を行い、再生べクトルのコードを求め
て、ベクトル量子化器１３ｅ，１３ｆに出力する。即ち
、ベクトル量子化器１３ｅは前段のベクトル量子化器１
３ａ　　１３ｂの再生ベクトルのコードを入力し、ベク
トル量子化器１３ｆは前段のベクトル量子化器１３ｃ，
１３ｄの再生ベクトルのコードを入力する。

ベクトル量子化器１３ｅ，１３ｆを構成するＬＵＴの内
容を決定手法について説明する。先ず、入力された再生
ベクトルのコードをベクトルに一度復号し、そして、そ
のベクトル空間全体を第３Ｂ図のように２つに分割して
新しいベクトルを作成する。これに対してベクトル量子
化を施して得られる再生ベクトルのコードを求め、これ
が１３ｅ，１３ｆのＬＵＴの内容となる。

かくして、ベクトル量子化器１３ｅは元のシーケンシ２
０ｂ，２０ｃ，２０ｄ，２０ｅ，２０ｆ，２０ｇ，２０
ｉ，２０ｊについてのベクトル量子化を行う。またベク
トル量子化器１３ｆはシーケンシ２０ｄ，２０ｈ．２０
ｋ，２０１，２０ｉ，２０ｊについてのベクトル量子化
を行う。

ベクトル量子化器１３ｇは前段のベクトル量子化器１３
ｅ，１３ｆの再生ベクトルコードな入力する。即ち、前
段のベクトル量子化器１３ｅ，１３ｆと同様に、入力さ
れた再生ベクトルコードを復号し、ベクトル空間を１５
次元にもどしてベクトル量子化を施した結果の再生ベク
トルコードを得る。

この様な構成をとることによって、人力された１５次元
の入力を多段構成のベクトル量子化器を介して、再生ベ
クトルコードを得る。

次に各ベクトル量子化のコードブックの作成について述
べる。コードブックの作成には一般にＬＢＧ法を用いて
行う。これは母集団となるトレニングデータから再生ベ
クトルを算出する手法としてよく知られている。そこで
本実施例ではこのＬＢＧ法を用いる。前述の４×４のベ
クトル空間を例にとって説明する。

トレーニングデータな作成する方法として、実際に画像
に対してアダマール変換を施して得られるベクトルを集
める方法がある。このようにして、１６次元のベクトル
からなるトレーニングデータを作成する。そこからアダ
マール変換により、各ベクトル量子化器に必要なシーケ
ンシをとり出し、必要な次元のベクトルからなるトレー
ニングテーブルを作成する。そして、これらから必要な
再生ベクトルコードを得るためにＬＢＧ法を適用すると
いうものである。このようにするのも、各ベクトル量子
化器を１・レーニングデータから直接設計することによ
って、前段の量子化による歪みのないコードブックを得
ることができるからである。

前述のコードブックの作成方法によると、歪みのないと
いう点ては全段最適となるコードブックが得られる。し
かしながら、前段の量子化によって後段にある再生ベク
トルが使用されない場合が生じ、効率的ではないという
問題がでてくる。

第４図〜第５図はこの使用されない再生ベクトルの発生
を説明する図である。第４図は２×２のブロックについ
ての不使用再生ベクトル発生の全体を説明する図であり
、第５Ａ図〜第５Ｄは第４図の個々の過程を説明してい
る。ベクトルの大きさを２Ｘ２＝４としたのは、４Ｘ４
＝１６の場合よりも説明か単純化するからであり、両者
には木質的には差がない。従って、第４図〜第５図でな
された２×２の議言向はそのまま４Ｘ４の言義言向に適
用される。さて、第４図の処理は以下のようなものであ
る。４次元の人力ヘク１・ル、 Ｙ４°｛’！＋　＋　ｙ２＋　’Ｉ３＋　”Ｉｓ　）を
入力し、このベクトルＹ４は、第５Ａ図にも示すように
、 國；二じ：：乞｛ に分割される。尚、この分割は第１図の分配器１１によ
る分割に対応する。そして更に、第４図に戻って、分割
された個々のベクトルＹ　Ｉ　＋　Ｙ　２に対しベクト
ル量子化を行い、その結果を合成して得たベクトルＹ。

を再びベクトル量子化する。これが第４図の処理である
。ここで、各ｙ１〜ｙ４は２ビットのデータで、０，１
，２．３の何れかの値であるとする。

さて、Ｙ＋＝｛ｙ＋，ｙ２｝を２ビットの情報にベクト
ル量子化するためのコードブックＣＩの再生ベクトルＸ
１．〜Ｘｌ４を、第５Ａ図にも示す如く以下のように定
める。

Ｃ，Ｅ　｛ｘ＋＋｝　　　Ｈ＝ｉ　〜４）また、Ｙ２　
＝　（ｙ３．’Ｉ４’ｊをベクトル量子化し、同ように
２ビットの情報にベクトル量子化するためのコードブツ
クＣ２の再生ベクトルＸ２，〜Ｘ２４を、第５Ｂ図にも
示す如く、以下のように定める。

Ｃ２　ε　｛Ｘ２１｝　　　　（ｉ＝１　〜４）さらに
、Ｙｌ，Ｙ２をベクトル量子化した結果に得られた再生
ベクトルを、 とし、これらを合成したベクトルを、 Ｙｏ　””　｛ｙ＋’＋　’ｌ２”＋　ｙ３’　＋　ｙ
４　’　）とする。これをベクトル量子化するコードブ
ックｃｏの再生ベクトルをＸ。１〜ＸＯ８を以下のよう
に定める。

Ｃｏ　Ｅ　｛ｘｏ＋｝　　　（ｉ＝１〜ａ）Ｘｏ６＝　
　｛３，　　２，　　１　．　　１　　｝このように、
ベクトル及びコードブックを定義した上で、使用されな
い再生ベクトルの発生について説明する。

例えは、Ｙ．＝　｛２．１｝のような成分を有するヘク
１−ルが人力された場合を考察する。コードブックＣ１
のベクトル量子化によって、Ｙ１はＹ“ｌ＝＝Ｘｌ３＝
　｛３．１｝に量子化される。このＹ１゛がＹ２゜と合
成され、合成ベクトルＹ。とされ、コードブックＣ。に
よりベクトル量子化される。ここて、Ｃ１のベクトル量
子化により｛２１｝は（３．１）に量子化されているの
で、ベクトルＹ。を量子化する際は、このＹ。には、コ
ードブックＣ。の｛３．１｝成分をもつ入力ベクトルの
みが量子化される。換言すれば、ベクトルＹｏには｛２
，ｔ｝成分は出現せず、そのために、Ｃｏ中の｛２．１
｝成分を有する再生ベクトルＸ。５．　　ＸＯＩＩは全
く使用されない。このような使用されないベクトルを『
不使用再生ベクトルＪを呼ぶ。このように使われること
のないベクトルをコードブックに記憶していたのでは効
率が低下する。そこで不使用再生ベクトルＸＯＳを取り
除き、その替りに新しい再生ベクトルを加えることによ
って効率を向上させる。

第６図に、不使用再生ベク１−ルを取り除き、新しい再
生ベクトルと交換する手順をフローヂャートで示す。こ
のフローチャートは、一例として、第４図の如く、２×
２の入力ベクトルを２つのベクトルに分割して夫々をＣ
，，Ｃ２によりベクトル量子化し、結果を２Ｘ２のベク
トルに合成して、再度、コートブツクＣ。によりベクト
ル量子化するという場合の、コードブツクＣ。中の不使
用ベクトルの削除の手順である。まず、ステップＳ２，
Ｓ４で、コードブツクＣ２の中に不使用再生ベクトルか
あるかないかを調べる。このチェックは次のようにして
行なう。即ち、あらゆるパターンの人力ベクトルに対し
て、Ｃ，またはＣ２のベクトル量子化を行ない、この結
果の再生ベクトルをＣ。でヘク｝・ル量子化を行なう。

そして、上記全ての人力パターンに対して一度も再生ベ
クトルとして使用されなかったＣ。中のものを、不使用
再生ベクトルｘＮとして拾い出すのである。

尚、人力ベクトルのパターンとは、第４図の例では゛’
　００００゜′〜”　１　１　１　１　”の任意のパタ
ーンである。

ステップＳ６では、コードブックＣ２のなかから不使用
ベクトルＸＮを取り除く。そして同時に、ステップＳ８
ではトレーニングデータＴの全てについてＣ，，Ｃ２に
よりベクトル量子化を行ない新たなトレーニングデータ
Ｔ゜を得る。ここで、２×２のベクトルＴ１を２つのベ
クトルに分割し、その各々にＣ，，Ｃ２のベクトル量子
化を行なって新たなベクトルＴ゜を得るという操作を、 Ｔ　＋　　’　　一Ｖ　ＱＣＩＣ２　（Ｔ　＋）と表記
する。ここで、 ｛＋：・冗二じ；ぢＨ とする。このとき、トレーニングデータの次元はコード
ブツクＣ。の表すベクトル空間の次元である。次に、ス
テップ５１０で、新しいトレーニングデータＴ゜のベク
トルＴ，゜のうち、コードブツクＣ。内の再生ベクトル
ｘＩとの距離が最も遠いものをベクトルＸ，として求め
る。即ち、Ｘ，にＭＡＸ　（ｄｊｓ　｛Ｘ　Ｉ，Ｔ　Ｊ
’））とする。そして、ステップＳ１２ては、この距離
の遠いベクトルｘＦを新たな再生ベクトルとしてコード
ブツクＣ。に加える。即ち、 ｃｏ４−ｃｏ＋ｘＦ とする。この場合、ＸＦはＬＵＴであるＣ。の、前記ｘ
Ｎが削除された部分に格納される。このようにするのも
、不使用ベクトルは密度が高い部分に発生するものであ
るから、密度が粗な領域に新たな再生ベクトルを追加す
ることにより、テーブルとしてのコードブツクＣ。の密
度均一化と効率化とを両立させるのである。

上述の操作をコードブツクＣ。内に不使用ベクトルがな
くなるまで繰返す。

〈第２実施例〉 第７図は、本発明の他の実施例を示す構成図である。こ
の第２実施例は、ベクトル量子化を多段構成とする点で
は同してある。しかし、第１実施例が不使用再生ベクト
ルを削除し、さらに、トレニングデータから新たな再生
ベクトルを抽出して追加するのに対し、この第２実施例
は、入力画像が線画と中間調画とが混在して含む場合に
、不使用再生ベクトルを削除して、線画のベクトル量子
化に適した再生ベクトルを追加する点て異なる。

説明を簡略化する為に、この第２実施例でも、第１実施
例と同ようにアダマール変換によって得られた４×４の
シーケンシを例にとる。第７図において、１１０は１５
個のシーケンシを人力する入力端子である。第１実施例
と同ように、直流成分は量子化の対象から外す。１１１
は入力されたベクトルを細分割する分配器であり、１１
２ａ〜１１２ｄは入力されたシーケンシをスカラ量子化
するスカラ量子化器である。１１３ａ〜１１３ｇは入力
ざれたベクトル又はベクトルコートの表すベクトルをベ
クトル量子化するための量子化器であり、入力ベクトル
に対して最短距離ベクトルのコートを格納してあるＬＵ
Ｔのメモリてある。１１４は出力端子である。端子１１
５は、端子１１０から人力されているシーケンシの画像
が線画であるのか中間調画であるのかを選択するセレク
ト信号を人力する人力端予てある。

人力端子１１０から１５個のシーケンシを人力し、これ
らのシーケンシは分配器１１１で以下に続くスカラ量子
化器に分配される。分配の方法は第１実施例と同じであ
る。スカラ量子化器１１２ａ〜１１２ｄに続くベクトル
量子化器１１３ａ〜１１３ｆまては第１実施例と同じ働
きをする。入力端子１１５はセレクト信号を人力する。

このセレクト信号は最終段のベクトル量子化器１１３ｇ
の中のコードブックを切換えている。今回は、説明の為
に、人力される画像が写真等の自然画像（中間調画像）
たった場合と、文字や細線画だつた場合とて、１１３ｇ
のコードブックの切換えを行う。尚、このコードブック
の切り換えにおいて、２つのコードブック間で全てを切
り換えるというのではなく、特に文字画像等に生じる小
数ながらエッジ情報の保存を行うのに有効なように、線
画用と自然画用の２つの小型の特殊なコードブックを用
意して、セレクト信号によりどちらを使用するかを切換
えている。

このようにするのは以下の理由による。アダマール変換
のシーケンシを量子化する際に、一般に高周波のシーケ
ンシについては粗く量子化を行う。また、トレーニング
データが自然画像だった場合には、この１−レーニング
シーケンスで得られたコードブックを使えは鋭いエッジ
は再現されないことになる。即ち、第８Ａ図のような４
５°の濃度差の大きな斜線データか入力されたとき、エ
ツジ部は図の太線で囲まれたようなブロック１２１８〜
１２１ｋで示され、そのブロック内の分布形状は第８Ｂ
図に表した（ａ）又は（ｂ）のいずれかである。これら
にアダマール変換を施した後にベクトル量子化を施した
一例が第９Ａ図である。前述の第８Ｂ図のブロック（ａ
）又は（ｂ）は滑らかになってしまい、第９Ｂ図のよう
なブロック形状（ａ”）又は（ｂ゜）になる。従って、
ブロック（ａ）の１画素の黒はまわりに白が多いために
極めてうずくなり、ブロック（ａ゜）のように白の平坦
ブロックに近くなる。また、ブロック（ｂ）ては黒エツ
シに近い２画素がまわりに黒が多いため極めて黒に近づ
き、（ｂ゜）のように残りの右下隅の画素も黒を帯びる
。このため、第９Ａ図では斜めのエッジに４×４のブロ
ックのテクスヂャか目立ち、画質に悪い影響を与えてい
る。自然画像でも低周波のエッジは保存されるからであ
る。

そこでベクトル量子化器１１３ｇのコードブツクＡの構
成を第１０図のようにする。

コードブツクＡはｎ個の再生ベクトルのうち、（ｎ−α
）個の再生ベクトルからなるコートブツクＢと、α個の
再生ベクトルからなる自然画用コードブツクＮと、α個
の再生ベクトルからなる文字画像用のコードブツクＣか
らなっている。ここで、αが第１実施例であったような
不使用ベクトルの数に対応すると考えることができる。

即ち、コートブツクＢは不使用ベクトルを取り除いたコ
ードブックである。コードブツクＮは第１実施例のよう
にトレーニングデータから作成された再生ベクトルで構
成される。コートブツクＣは再生ベクトルとして、例え
ば第８Ｂ図のようなブロック（ａ），（ｂ）を登録して
おく。

第１１図に実際の景子化の例を示す。

同図において、入力へクトルＸＮは自然画像のベクトル
てある。また、人力ベクトルＸ。は文字画像のエツシ部
で、第８Ｂ図のブロック（ａ）のようなブロックをアダ
マール変換して入力されたベクトルである。これらの人
力ベクトルは同時には人力されることはないものの、ど
ちらも入力されると分配器１１１によって分割され、ス
カラ量子化器１１２ａ〜１１２ｄを経て、ベクトル量子
化器１１３ａ〜１１３ｆを経て量子化される。その量子
化結果を第１１図のｘｐとする。ここで第１１図の右側
のベクトル量子化は第７図のベクトル量子化器１１３ｇ
か実行するベクトル量子化を表す。このベクトル量子化
は、コートブツクＮＩＪ）ら距ａｔ＋　泪算によって算
出された再生ベクトルｘｎと、コードブックＣから距離
計算によって算出された再生ベクトルＸ，゛とを算出す
るものである。

ここで第７図の人力端子１１５から人力されたセレクト
信号は第１１図のセレクタに入力され、このセレクタは
、セレクト信号が符号化処理の対象が自然画像であるこ
とを示す場合（即ち、第１１図で入力がベクトルｘＮて
ある場合）には、再生ベクトルｘｎ゜のコートを選択し
、文字画像であるこ“とを示す場合（即ち、第１１図で
入力がベクトルＸ。である場合）には再生ベクトルＸ。

゜のコードを選択する。これによってエッジのシャープ
ネスを保つことがてきる。

かくして、この第２実施例によれば、自然画像のような
中間調画像と線画画像等が混在した画像を入力した場合
に、その原画の画質を劣化させずに再現性のよい符号化
が行なうことができる。また併せて、中間調画像と線画
画像とで、コードブックを共有化できる部分は共通化す
ることにより、全体のコードブックの容量を削減するこ
とができる。

〈第３実施例〉 この第３実施例は、第７図の第２実施例のベクトル量子
化器１１３ｇにおいてコードブックの形態を第１２図に
示す形にしたものである。第１２図において、コードブ
ツクＣは前述のように文字情報等のエッジに対応したコ
ードブック、即ち、第９Ｂ図のようなパターンの再生ベ
クトルを含むものである。これはコンピュータ上で二値
パターンを生成することによって得ることもできる。こ
のようなエッジ用の再生ベクトルをコードブツクＣとし
て、最終段の量子化器のコードブックＢ内の不使用ベク
トルを削除した部分に加える。

この第３実施例のコードブックＣ内の再生ベクトルは、
単なる距離計算たりてなく、”　十”゜′の位相の情報
と各係数の絶対値を考慮した距離計算を行うことによっ
て得る。即ち、第１１図の量子化結果ベクトルｘｐの各
シーケンシの符号が゛一゛゜てあり、その量子化結果の
各シーケンシの絶対値が各スカラ量子化結果の絶対値で
最大であった場合に、元のブロックが第８Ｂ図のブロッ
ク（ａ）の如き形状であると判断し、第１１図の再生ベ
クトルｘｃ゜のコーｌ・を出力する。

このようにした場合には、第１１図のセレクタは不要で
あり、セレクタ信号は存在しない。

〈実施例の効果〉 以上３つの実施例で説明したように、ベクトル量子化を
多段に構成し、各コードブックなＬＢＧ法等で得られる
最適な再生ベクトルと共に、不効率な不使用ベクトルを
削除してトレーニングデータ（第１実施例）又は人工的
なデータ（第２実施例）から得られた再生ベクトルを併
せて構成することにより、ベクトル空間の次元，入力ベ
クトルの出現数を減じることができ、ハードウエアで実
現可能なベクトル量子化を実現てきる効果がある。同時
にＬＵＴを作成するにあたり、次元数を減じることでコ
ンピュータ等で演算させる場合に、演算時間を大幅に減
じることができ、さらに多次元のベクトルでも全探索型
のベクトル量子化器と同等の性能を得ることができる。

〈その他の実施例〉 本発明はその要旨を変更しない範囲て種々変形可能てあ
る。

以上の第１〜第３実施例の説明では、４×４のアダマー
ル変換のシーケンシ又は４次元のベクトルを用いて行っ
たが、本発明はこれに制限されず、ｎ次元（ｎ≧３）ベ
クトル全てに応用できることは明らかである。

また画像の種類のセレクト信号を最終段のベクトル量子
化器にのみ人力したが他のベクトル量子化器、スカラ量
子化器、分配器に入力するように変形してもかまわない
。

また、不使用ベクトルを削除した後に新たな再生ベクト
ルをコードブックに加える方法はこれに限定されず、ト
レーニングデータから任意のベクトルで最も各再生ベク
トルより遠いベクトルを加えることも可能であり、トレ
ーニングデータから抽出したベクトルを加える全ての方
式に対応できる。さらに加える再生ベクトルをコードブ
ックに加える再生ベクトルをコンピュータ上て二値バタ
ーンを生成していったか、これに限定されず三値パター
ンでもよく、特に数か少ない場合はマニュアルでパター
ンを入力してもかまわない。

［発明の効果］ 以」二説明したように、木発明によれば、ベクトル量子
化を多段に構成することにより、ベクトル空間の次元の
減らすことが可能となる。

即ち、ベクトル空間の次元を減らすことが可能となる符
号化方法及び法号化装置が提供でき、更にこれらに適用
ざれる効率的なコードブックが作成できる。

また、多段構成とする結果に現われる不効率な不使用ベ
クトルを削除することによりベクトル量子化の構成を小
規模化することか可能となる。

また、この削除分を、トレーニングデータ又は人工的な
データから得られる男生ベクトルて追加構成することに
より、再生信号の劣化を防止しつつ、多次元のベクトル
ても全探索型の高速ベクトル量子化器と同等の性能を得
ることができる。

【図面の簡単な説明】

第１図は本発明に係る第１実施例の符号化装置の全体図
、 第２図は第１実施例〜第３実施例に利用されるベクトル
量子化の概念を説明する図、 第３Ａ図，第３Ｂ図は第１実施例〜第３実施例に適用さ
れる空間分割の概念を説明する図、第４図．第５Ａ図〜
第５Ｄ図は不使用再生ベクトルが発生する様子を説明す
る図、 第６図はトレーニングデータから不使用ベクトルを置換
する手順を示したフローヂャート、第７図は本発明の第
２実施例に係る符号化装置のブロック図、 第８Ａ図，第８Ｂ図．第９Ａ図，第９Ｂ図は、第２実施
例の手法を用いないとエッジ部分が劣化する様子説明す
る図、 第１０図は第２実施例のベクトル量子化コードブックの
構造図、 第１１図は第２実施例の動作を実際の例を用いて説明し
た図、 第１２図は第３実施例に用いられるコードブックの構成
を示す図、 第１３Ａ図．第１３Ｂ図は従来の技術の構成を説明する
図である。 ａ〜ｄ・・・スカラ量子化器、１３ａ〜１３ｇ，１１３
ａ〜１１３ｇ・・・ベクトル量子化器、１４．１１４・
・・出力端子、１１５・・・セレクト信号入力端子、２
０ａ〜２０ｐ・・・シーケンシ、１２０・・・画素、１
２１ａ〜１２１ｋ・・・ブロックである。 特許出願人　　　キヤノン株式会社 図中、 １・・・メモリ、２・・・距離演算器、３・・・比較器
、４・・・ＬＵＴテーブルメモリ、１０．１１０・・・
人力端子、１１，１１１−・・分配器、１２ａ　〜ｄ，
１１２寸 Σ 区 娃 味 澱 −５１０一 〈 手 続 ネ甫 正 ｊｔと （方式） 平成 １年 ６月２２日 許 庁 長 官 殿 事 件の表示 特許廓平１−５６３２１号 ２．発 明の名称 符号化方法及び符号化装置及び これらに用いられるコードブックの作成方法補正をする
者 事件との関係　　特許 キヤノン株式会社 出 願 人 代 理　　　人　　　　　　〒１０５ 東京都港区虎ノ門２−５ 平成 １年 ５月３０日 （発送）

Claims (6)

【特許請求の範囲】
1. （１）前もつてトレーニングデータから作成したコード
   ブックを用いて、信号のベクトル量子化を行う符号化方
   法において、 入力信号ベクトルを表すｎ次元ベクトルを、各々がｐ次
   元（ｐ＜ｎ）の複数のベクトル空間に分割する第１の工
   程と、 これらの分割された個々のベクトルを、同じ空間をもつ
   コードブックによりベクトル量子化する第２の工程と、 上記工程によりベクトル量子化された個々の量子化結果
   をｑ次元（ｑ≦ｎ）のベクトルに合成る第３の工程と、 このｑ次元のベクトルを、これらが表すベクトル空間の
   構成をもつコードブックによりベクトル量子化する第４
   の工程と、 ｑ＝ｎとなるまで、上記第３、第４の工程を繰り返す第
   ５の工程とからなることを特徴とする符号化方法。
2. （２）前もつてトレーニングデータから作成したコード
   ブックを用いて、信号のベクトル量子化を行う符号化装
   置において、 入力信号ベクトルを表すｎ次元ベクトルを、各々がｐ次
   元（ｐ＜ｎ）の複数のベクトル空間に分割する分割手段
   と、 これらの分割された個々のベクトルを、同じ空間をもつ
   コードブックによりベクトル量子化する第１のベクトル
   量子化手段と、 この第１のベクトル量子化手段によりベクトル量子化さ
   れた個々の量子化結果をｑ次元（ｑ≦ｎ）のベクトルに
   合成する合成手段と、 このｑ次元のベクトルを、これらが表すベクトル空間の
   構成をもつコードブックによりベクトル量子化する第２
   のベクトル量子化手段とを有し、少なくとも、ｑ＝ｎと
   なるまで、上記第１のベクトル量子化手段と、合成手段
   と、第２のベクトル量子化手段とを複数段に線形に配列
   したことを特徴とする符号化装置。
3. （３）ｐ次元の入力信号ベクトルとｑ次元の入力信号ベ
   クトルの各々を夫々第１、第２のコードブックを用いて
   ベクトル量子化し、これらの２つの量子化結果を合成し
   て得たベクトルを第３のコードブックにより更に量子化
   する符号化方式における前記第３のコードブックの作成
   方法であつて、第１及び第２のコードブックによる量子
   化によつては、第３のコードブックで使用されることの
   ない再生ベクトルを抽出する第１の工程と、この抽出さ
   れた再生ベクトルを第３のコードブックから削除する第
   ２の工程とを具備したことを特徴とするコードブックの
   作成方法。
4. （４）トレーニングデータから新たな再生ベクトルを抽
   出する第３の工程と、 この抽出された新たな再生ベクトルを前記第２の工程で
   削除した数だけ第３のコードブックに追加する第４の工
   程とを更に具備した事を特徴とする請求項の第３項に記
   載のコードブックの作成方法。
5. （５）トレーニングデータによらない新たな再生ベクト
   ルを抽出する第３の工程と、 この抽出された新たな再生ベクトルを前記第２の工程で
   削除した数だけ第３のコードブックに追加する第４の工
   程を更に具備した事を特徴とする請求項の第３項に記載
   のコードブックの作成方法。
6. （６）入力信号は画像信号であり、トレーニングデータ
   によらない新たな再生ベクトルは、線画のエンジン部分
   を表わす再生ベクトルである事を特徴とする請求項の第
   ５項に記載のコードブックの作成方法。