JPH07112279B2 - ２次元情報の符号化システム - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、２次元情報の符号化システム、更に詳細に
は、サイド・マッチングおよびオーバラップ・マッチン
グによる画像用ベクトル量子化器に関する。

〔従来の技術〕

画像を伝送するためのデータ処理には、画像データの伝
送に必要なビット率（bit rate:画素当たりのビット
数）を低く抑えるためのいろいろな技術が今まで使われ
てきた。こうした技術の多くは、概して画像圧縮として
特徴付けられるものであり、必要なビット率を下げるた
めに、画像データのうち知覚的に無意味な部分を取り除
いたり、符号化技術によってデータの冗長度を低減した
りするものである。利用可能なチャネルの帯域幅が増す
と共に、画質に対する要求が高まってきたので、いろい
ろな技術が拡大してきた。

前記の目的にかなう技術には、ベクトル量子化を用いた
画像圧縮として知られる技術がある。この技術では、別
個の画素から成る各グループをブロックまたはベクトル
として表し、それらが別々に符号化される。この技術
は、１画素当たりのビット率が適度に低くなる効果があ
ることが実証されている。

伝送の質を変えずにビット率を更に小さくするには、メ
モリを用いたベクトル量子化として特徴付けられるタイ
プのベクトル量子化を利用する必要があった。つまり、
既に符号化されている幾つかのブロックのメモリを後続
の入力ブロックに使用することにより、符号化処理にメ
モリが組み入れられる。有限状態ベクトル量子化として
知られているこの特殊な技術においては、以前に符号化
されている幾つかのベクトルに付いての重要な情報を端
的に表す状態を多数使用し、一群のいわゆるコードブッ
ク（符号簿）から１つを選択して各入力ベクトルを符号
化する。この技術の例は、1987年７月出版の「光工学
（Optical Engineering）」、第26巻のp.570−p.680に
記載のR.AravindおよびAllen Gershoによる「有限メモ
リを用いたベクトル量子化に基ずく画像圧縮（Image Co
mpression Based on Vector Quantization With Finite
Memory）」と題する記事に見られる。

このようなシステムの符号器や復号器は、帰還構成を備
えていて、出力によって決定された内部状態が帰還さ
れ、符号化および復号化のために入力と共に使用される
ようになっている。このような有限状態方式の目的は、
希望の低ビット率を達成しつつ得られる伝送の質を維持
することである。符号化すべき入力ベクトルを含む小領
域を内部状態によって正確に表すことができれば、有限
状態ベクトル量子化は、コードブックの比較的短時間で
変化する集合を用いることにより前記の目的を実現する
ことができる。

画像の符号化分野において、上述の技術およびその他
は、画像の符号化に関する２つの特殊な要素に取り組ん
できた。その１つは、画像は２次元的特性を有するた
め、音声の符号化分野におけるような１次元の標本ブロ
ックとは異なり、画素ブロック（通常は、長方形の画素
ブロックである）が、そのブロックの外側でより多くの
画素と隣接することである。もう１つは、普通の画像と
ほとんどの場合、隣接する画素間の相関関係が非常に緊
密であることである。前者の特性を空間的隣接性（spat
ial contiguity）と言う。

しかし、従来から空間的隣接性を利用する試みが為され
てきたが、伝送の質を向上させると共にビット率を低下
させる可能性を最大限に利用することができなかった。
例えば、AravindおよびGarshoによる前述のシステムに
おいては、空間的に隣接する画素に関する情報を、例え
ば輝度の不連続性の存在およびその種類のような間接的
な情報に変換することにより、空間的隣接性の効果を失
なっている。

AravindおよびGershoによる前述の記事の技術では、各
ブロック内の画像のエッジを探すが、内部にそのような
エッジを持つ最高の一致性を有する画像ブロックとして
選択された状態コードブック・ブロックは探さないので
画像のエッジが継続する可能性のある後続の隣接画像ブ
ロックへの照合において前記のようなコードブック・ブ
ロック内の他の画素が最も重要に扱われる。従って、Ar
avindおよびGershoの技術によれば、空間的隣接性によ
る関連性の一部は、後続の画像ブロックの符号化にもた
らされていない。

本発明の目的は、伝送された画像の質、および伝送に必
要なビット率の低減の一方、または両方に付いて、前記
のような符号化技術の性能を改善することである。更
に、例えば、医学的写真、地球物理学的写真、航空また
は衛生写真を目的としたり、電子ショッピングやテレビ
会議のために、画像の経済的な保存技術に対する市場が
新たに活気づくにつれて、このような技術を更に、そし
て極限にまで押し進めることにより、符号化技術がある
程度複雑になるという犠牲を払ってでも、復号化技術を
単純にすることをシステムの第一の目的とする必要性が
増している。

〔発明の概要〕

本発明によれば、前記のようなシステムにメモリを取り
入れる最も効果的な方法は、隣接するブロックの空間的
に接近している画素どうしの間で輝度の連続性を直接制
御するように二次元空間的隣接性を利用することであ
る。空間的隣接性の意味を失わないように、前のブロッ
クを表すベクトルおよび１つの前の行におけるブロック
を表すベクトルの相対的に最も近い画素に輝度を最高に
一致させるために選択された状態ゴードブックを使用す
るために、本発明では、不連続を分類するような間接的
な情報は全く考慮に入れていない。

空間的隣接性をより直接的に応用することは、本発明の
主題であり、これを、２次元情報ブロックの「サイド・
マッチ」または「オーバラップ・マッチ」ベクトル量子
化と呼ぶことにする。

更に、仕込用の画像の統計あるいは入力画像自体に基づ
く可変長符号化を行うことにより、この改良システムの
有効性は、益々増大する。ここで提案する可変長無雑音
符号化は単純なので、ビット率がわずか高くなるだけ
で、符号化した全内容を通信システムの受信側に伝送す
ることができる。実際、本発明のこの特徴によれば、可
変長無雑音符号のファミリーが記述され、いわゆるチャ
ネル記号のエントロピーを確実に達成する。また、本発
明のこの著しい特徴は、他の有限状態ベクトル量子化設
計に新たな改善を施すことができる。

〔実施例〕

有限状態ベクトル量子化タイプ（Aravindらによる前述
の記事に開示されているものを含む）の符号化アルゴリ
ズムを実施するために使用できるシステムと同様に編成
されている基本的な実施例を、第１図に示す。ただし、
詳しく吟味すれば、第１図の実施例が特に本発明の著し
い特徴に適合していることが解る。更に具体的には、第
１図は、遠隔地間で画像を伝送する通信システムの送信
部に使用される本発明の実施例を示す。この送信部は、
走査撮影された画像信号を受け入れるように構成されて
いる。この画像信号は、テレビの画像送信用に従来の方
法で走査されたものであるが、高解像度のものでもよ
い。また、これには、第１図のブロック形成段11によっ
て示されるような画像の画素をブロック化する手段も含
まれる。各ブロックは、4x4個の画素から成るブロック
である。例えば、最初のブロックは、走査された画像画
素から成る最初の４行の各行における最初の４個の画素
を含む。得られた各画素ブロックは、次に量子化器12に
渡され、そこで後述のようにして選択される特定のコー
ドブックの中から所望の項目（符号語）を選択するため
に最近似値の検索が行われる。この検索は、ブロック11
および量子化器12を備えた符号化部41と連絡をとり合う
論理回路42の管理下で行われる。この論理は、更に後で
詳述するように、適当な符号語のインデックスを、その
画素ブロックのエッジに最適マッチングした状態ではあ
るが適当に低いビット率で伝送することを可能とするよ
うなものである。ブロックの形成および量子化器による
最近似値検索は、Aravindの記事の1.1.節に説明されて
いるようにして行われる。端的には、次のとうりであ
る。画素ブロックは、例えば、最小の画像単位である4x
4画素のブロックである。これらのブロックは隙間なく
配列され、その結果、各ブロックは、画像がその表示画
面、即ちその画像の２次元表示面にわたって１行ずつ展
開される方向に関して、幅４画素、奥行き４画素とな
る。換言すれば、隣接する画素から成るブロックを生成
するのに、４行が使用される。次に、画素ブロックは、
量子化器に送られる。スイッチ位置の集合14の中から選
択された１個のスイッチ位置によって現在動的に選択さ
れた状態コードブックから、例えば、スイッチ20から、
コードブックの限られた項目（符号語）C₁、C₂、および
C_nが、そのブロックの各画素に対する実際の入力画素ブ
ロックｘと、最小隔たりベースとして比較される。平均
自乗誤差を最小とするC_iの値が選択され、更に、そのコ
ードブック値のインデックス、つまりｉの値が、量子化
器12から符号語のインデックスとして送られる。これと
同時に、この符号語のインデックスは、画像情報の履歴
の一部として使用され、その画像情報は、次の状態のコ
ードブック（これは、次の画素ブロックの選択に使用さ
れる）を動的に選択するために使用される。

画像の履歴を使用して次の状態のコードブックを選択す
る論理は、第１図の論理回路42で見いだされる。前の符
号語のインデックスは、逆量子化器13に渡される。逆量
子化器13は、基本的には探索テーブルであり、前の状態
の符号語のインデックスをブロックを表す符号語に復元
変換する。この出力は、遅延およびその他の論理処理に
当てがわれ、回路スイッチ20の以降の位置決め動作に影
響を与える。逆量子化（復号）された値が隣接する画素
ブロックにのみ影響するようにするために、逆量子化器
の出力信号は、列状態出力部および行状態出力部にそれ
ぞれ適当な時間に到達するよう、１ブロック遅延回路23
および１ブロック行遅延回路25を通される。探索テーブ
ル22および27は、それぞれ列状態空間21および行状態空
間28を伴っており、随意、状態コードブック19の個数を
減らすことができる。列状態空間21および行状態空間28
は、全ての状態コードブックにおける全ての標本ブロッ
クの、それぞれ最終画素列および最終画素行に対する標
本値（代表値）の集合である。

前述のブロック21、22、27および28は、状態コードブッ
クの数を減らすための機構であり、このために、（符号
化器内部の）必要なメモリ空間は少なくて済む。状態コ
ードブックの個数やメモリ空間に全く制限がなければ、
これらのブロックは、削除することができる。検討中の
画素列および画素行の標本値から、フィルター24および
26を通過するのは、それぞれ最終列および最終行のみで
あり、これらは、現在符号中のブロックに隣接するか、
または重複する列および行の画素である。前記画素列お
よび画素行は、画素における標本値の不連続性を避けよ
うとする場合には、現在の画素の符号化に最も関係する
画素である。従って、論理回路42のこの部分が、先に引
用したAravindおよびGershoのものとは構成および動作
を異にするところである。状態コードブック19の１つを
選択する技術の差異は、特定の列状態が列状態出力に現
れ、特定の行状態が行状態出力に現れるところにある。
そして、これらの値は、スイッチ20の制御部分に与えら
れ、符号化すべき現在の画素ブロックの符号化に際し、
量子化器12が最近似値を検索するのに使用される状態コ
ードブックを制御する。例えば、列の状態の同様なイン
デックスに対して使用されると分かっている行の状態の
順序集合を行状態インデックスによって配列し、これに
続けて、列状態の続いて連続するインデックスに対する
行状態を同様の順序に配列すると言うように、使用する
ことが分かっている全ての列状態が順番に配列されるま
で、繰り返すことにより、状態コードブックを順番に配
列することができる。そして、ブロック22から出力され
る列状態インデックスにより、スイッチ20は相応の列状
態位置をカウントし、続いてブロック27から出力される
行状態インデックスにより、スイッチ20は先にカウント
された列状態にふさわしい行配列における相応の行状態
をカウントする。探索テーブル22および27が必要なの
は、状態コードブックの縮小集合19に対して、スーパー
・コードブック（後述する）の全ての行状態インデック
スが必ずしもスーパー・コードブックの列状態インデッ
クスとともに使用されるとは限らないからである。選ば
れた状態コードブックは、スーパー・コードブックにお
ける統計的に類似するブロックからのコードブックの設
計過程に従って同様な統計の２次元特性、即ち、隣接す
る最も類似性のあるエッジ（一つ前のブロックであれば
列のエッジ、一行前のブロックであれば隣接する行のエ
ッジ）を生むようなコードブックである。状態空間21お
よび28からブロック22および27への入力に含まれ得るの
は、前に決定された有限個の可能な値のみであり、フィ
ルタ24および26からの入力に含まれ得るもの、（値から
なる）より大きい集合からの前に決定された有限個の可
能値のみであるから、望むならば、ブロック22および27
における最近似値検索の動作を、探索テーブルによって
行うことが可能である。

論理回路42で用いられる処理は、全て探索テーブルによ
る処理であり、量子化器12で計算を中心として行われる
最近似値検索に比べて一般的に非常に迅速に行われる。

第２図に、第１図における符号語インデックスの出力を
更に伝送媒体によって実際に伝送し、受信部で受信する
ために、その出力を調整する処理を示す。つまり、媒体
の特性か、または画像自体の統計的特性が与えられてい
る伝送には、符号語のインデックスは、必ずしも最適な
バイナリー形態である必要はない。

換言すれば、符号語のインデックスは、更に（バイナリ
ー）符号器31でのバイナリー符号化に当てがわれる。こ
のとき、ビット率が付随的に更に下がるが、その程度
は、接頭語長決定器33および伝送用のバイナリー・コー
ドブック32で定められる接頭語長次第である。

本発明者は、第１および３図のシステムに、可変長無雑
音符号が有利であることを発見した。第２図による１対
１の写像は、チャネル記号をバイナリー・シーケンスに
変換するもので、バイナリー符号器と呼ばれ、その逆が
バイナリー復号器と呼ばれる。FSVQ（finite state vec
tor quantizer＝有限状態ベクトル量子化器）のような
情報限の符号器から到来するチャネル記号は、有限アル
ファベット（即ち、有限量の記号体系）を有する。情報
源の種類、即ちこの場合は画像が与えられれば、そのチ
ャネル記号により、ある確率分布が推定される。既知の
確率分布を有する有限アルファベットに属する記号に対
する無雑音符号に関して充分に確立された理論があるの
で、チャネル記号に対して最適な無雑音符号を容易に適
用することができる。しかし、アルファベットの量がか
なり多い場合、ハフマン符号（Huffman code）などの無
雑音符号を盲目的に適用すると問題をはらむことにな
る。例えば、バイナリー符号化器や復号器が、相当複雑
になったり、非常に大きいバッファを必要とする場合が
ある。これらの問題は、主にバイナリー符号語の長さに
大きなばらつきがあることが原因となっている。無雑音
符号における符号語の長さは、無雑音符号のレベル（水
準）と呼ばれることがある。一方、チャネル記号の分布
が未知である場合、１つの確率分布に対して設計された
最適無雑音符号は、別の分布に対しては極めて不十分に
なる可能性がある。バイナリー符号化器はチャネル記号
の統計を有するので、それに対応する最適無雑音符号が
何時でも使用できるとの主張も有り得る。この場合は、
最適無雑音符号の記述内容もバイナリー復号器に伝送
し、正しく符号化できるようにする必要がある。そのよ
うな記述内容が、都合悪く無視できない量の情報を含む
こともある。つまり、その最適無雑音符号の記述内容を
伝送すると、全体的なビット率がかなり高くなる場合で
ある。これらの問題を全て解決するには、無雑音符号の
レベル数を制限する必要がある。そうすれば、問題は、
「僅かなレベルしかない無雑音符号で良い結果が得られ
るか？」と言うことである。後述するように、この用途
で経験するチャネル記号の分布が特別な形であるため
に、サイド・マッチ・ベクトル量子化およびオーバラッ
プ・マッチ・ベクトル量子化に付いて言えば肯定的であ
る。

バイナリー符号は、通信チャンネルまたはメモリ・チャ
ンネル37によって受信部に伝送された後、送信部のバイ
ナリー・コードブックと同様の探索バイナリー・コード
ブック35に従いバイナリー復号器34によって符号語のイ
ンデックスに逆変換される。第２図の可変長符号化論理
は、後述の数学的処理に従って実施することができる。
また、それに代わり、当分野で使用されているその他の
可変長無雑音符号化技術に従って実施することも可能で
ある。上述した別方式は、本発明の目的にかなう好まし
い一代替案であるが、唯一の方法ではない。

第３図に、バイナリー復号器34の出力部に結合して、出
力画像を与える受信部を示す。その画像は、通信チャン
ネル37を通して伝送されるビット数に関係する。この受
信部は、送信部の逆量子化器13と全く同様の探索テーブ
ル動作を行う逆量子化器43、および送信部の論理回路42
と本質的に同様の論理回路44を備えている。画像形成回
路45は、第１図のブロック形成回路11において画素ブロ
ックを形成する処理と基本的に逆の処理を行うが、オー
バラップ・マッチングおよび復号化（後述する）には更
にいくつかの操作が加わる。

＜有限状態ベクトル量子化器の動作＞ 第１図の送信部の動作は、次のように更に明確に数学的
に特徴付けることができる。有限状態ベクトル量子化器
は、基本的に、デジタル回路の分野で定義されているよ
うな有限状態機構のものである。各標本の採取時ｉにお
けるベクトルの次元をｋとすれば、符号化器は、ｋ次元
の情報源ベクトルx_i を、有限アルファベットに属するチ
ャネル記号y_iに対応させて伝送する。これを受信する復
合器は、前記のチャネル記号y_iをｋ次元の再生ベクトル
_ｉに逆に対応付ける。デジタル的な伝送、またはメモ
リ、またはその両方を行うために、チャネル記号は通常
バイナリー・シーケンスで表される。

有限状態ベクトル量子化器の符号化器および復号器を詳
細に説明するために、これらを幾つかの構成ブロック、
つまり構成要素に展開する。即ち、これら構成要素は、
（１）状態の有限集合である状態空間Ｓ、（２）状態コ
ードブックの集合｛C_s:s∈Ｓ｝、（３）量子化演算子
ｑ、（４）コードブック（符号テーブル）探索関数であ
る逆量子化演算子ｐ、そして最後に（５）次状態関数
ｆ、である。これら構成要素の概要を説明すると、次の
ようになる。状態空間は、状態と呼ばれるＭ個の記号の
集まりでありs₁,s₂…,s_Mが状態を示すとすれば、Ｓ＝
｛s₁,s₂…,s_M｝となる。各状態コードブックは、符号語
と呼ばれるｋ次元ベクトルがＮ個集まった集合である。
状態コードブックの集合は、状態ごとにインデックスが
付けられている。従って、状態コードブックの総数は、
状態空間の大きさ、即ちＭに等しい。全ての状態コード
ブックの和集合を、スーパー・コードブックといい、Ｃ
で表す。つまり、Ｃ＝Ｕ_ｓ∈ＳC_sである。インデックス
の集合Ｙ＝｛1,2…,N｝は、チャネル信号空間といい、
全ての状態コードブックに共有される。この名称の根拠
は、状態コードブックの符号語のインデックスがそのチ
ャネルを介して伝送またはメモリされることになるチャ
ネル信号であるからである。量子化演算子は、ｋ次元ユ
ークリッド空間R^kと状態空間Ｓとのデカルト積（積集
合）からチャネル記号空間への写像である。つまり、×
でデカルト積を表すとすれば、q:R^k×Ｓ→Ｙである。こ
の量子化演算子は、R^kからＹへの写像q_sの集まり｛q_s:s
∈Ｓ｝として理解できる。ただし、ここでは説明の便宜
をはかるため、量子化演算子には前者の定義を使用す
る。量子化演算子によりデータの圧縮が行われるという
概念からすれば、量子化演算子は明らかに多対１の写像
でなければならないので、その逆は有り得ないと言うこ
とになる。しかしながら、量子化演算子の逆を模する逆
量子化演算子（de−quantizer）と呼ばれる写像ｐを定
義する。具体的には、逆量子化演算子はＹ×ＳからＣへ
の写像である。量子化演算子が写像q_sの集まり｛q_s:s∈
Ｓ｝であると考えれば、逆量子化演算子は、１対１の写
像p_s:Y→C_sの集合｛p_s:s∈Ｓ｝と見ることもできる。こ
の場合、各p_sは、テーブル探索関数であり、各チャネル
記号を状態コードブックC_sに属しインデックスがそのチ
ャネル記号と同じである符号語に写像する。有限状態ベ
クトル量子化演算子の符号化器および復号器は、有限状
態機関として機能するので、それらの内部状態は、標本
採取時点ごとに、更新される必要がある。内部状態の更
新は、次状態関数ｆによって行われる。Ｊを次の状態の
生成に係わる過去の再生ベクトルの数とすれば、次状態
関数ｆは、スーパー・コードブックＣのｊ重デカルト積
から状態空間への写像であり、 となる。換言すれば、次状態関数は、選択された符号語
の有限の過去の履歴から次の状態を生成する。

上述の構成ブロックを用いて有限状態ベクトル量子化器
の符号化器および復号器の特徴を説明する。有限状態ベ
クトル量子化器の符号化器は、状態空間、状態コードブ
ックの集合、量子化演算子、逆量子化演算子、および次
状態関数から成る五要素構成、即ち（S,｛C_s:s∈Ｓ｝,
q,p,f）によって特徴付けられる。ここで標本採取時ｉ
に、符号化器が状態空間Ｓの状態s_iを持っているとす
る。すると、量子化演算子は、ｋ次元情報源ベクトルx_i
を、ある基準に照らしてx_i に最も近い、状態コードブッ
クC_sjの符号語のインデックスy_iであるようなチャネル
信号y_iに写像させる。この結果得られる符号語は、ｘ _ｉ
で表される再生ベクトルである。最も一般的な基準を掲
げれば、次式で示される平均自乗誤差を最小にすること
である。

ただし、［x_i ］_ｊおよび［ _ｉ ］_ｊは、それぞれベクト
ルx_i および _ｉ のｊ番目の要素である。ここで論じてい
る量子化器は、基本的には、コードブックとして状態コ
ードブックを備えたメモリ無しベクトル量子化器であ
る。従って、有限状態ベクトル量子化器に使用可能な量
子化器には、種々の構成がある。例えば、ここで論じて
いる完全検索ベクトル量子化器（VQ）の他に、樹状検索
VQ、多段VQ、および積VQ等がある。なお、本明細書では
完全探索VQのみ検討する。各々が唯一のインデックスを
有する元から成る集合の元を、そのインデックスに写像
させる関係をηで表す。例えば、Ａ＝｛a₁,a₂,…,a₁,
…,a_L｝ならば、η（a₁,A）＝１とする。これにより、
標本採取時ｉの量子化動作は、次式のように要約され
る。

ただし、min^-1は、「それに続く量を最小とする変数」
を意味する関数を示す。角括弧の中の頃は、情報源ベク
トルからの最小歪みの符号語を表し、再生ベクトルと呼
ばれる。

量子化器によってチャネル記号が生成された後、符号化
器は次の情報源ベクトルの符号化に備え、状態を更新す
る必要がある。この更新は、次状態関数が有限個の過去
の再生ベクトルを次の状態s_i+1に写像することによって
行われる。再生ベクトルは、量子化の過程で暗黙のうち
に決定されるが、それだけでは再生ベクトルを利用する
ことができないことは留意を要する。この再生ベクトル
を次状態関数に利用できるようにするのが逆量子化器13
である。逆量子化器は、テーブル探索関数であるが、こ
の場合、探索テーブルは状態コードブックである。標本
採取時をｉ、状態をs_iとすると、逆量子化器は、チャネ
ル記号y_iを、C_siに属しy_iをインデックスとする符号語
に写像する。換言すれば、時刻ｉにおける再生ベクトル
が_ｉで表されるならば、 _ｉ ∈C_siおよびy_i＝η（
_ｉ ,C_si）として、 _ｉ ＝ｐ（y_i,s_i）となる。逆量子化
器によって再生ベクトルが使用可能となったので、次状
態関数は、s_i+1＝ｆ（ _i, _i-1,…）という関係で表さ
れている。初期状態をs₀とすれば、量子化演算子および
次状態関数は、前述のように繰り返し作用して、連続す
る情報源ベクトルｘ ₀,ｘ ₁,ｘ ₂,…から次々とチャネル記
号y₀,y₁,y₂,…を生成する。このチャネル信号・シーケ
ンスは、伝送あるいはメモリをとおして、復号器によっ
て受信され、 ₀, ₁, _２…で表される再生ベクトル・
シーケンスに逆変換される。

有限状態ベクトル量子化器の復号器は、状態空間、状態
コードブック集合、逆量子化演算子、および次状態関数
から成る四要素構成、即ち、（S,｛C_s:s∈Ｓ｝,p,f）に
よって特徴付けられる。構成要素は、すべて既に詳述し
た有限状態ベクトル量子化器の符号化器の構成要素と同
じである。有限状態ベクトル量子化器の復号器は、チャ
ネル記号を受信するので、逆量子化器は、内部状態に応
じた状態コードブックから、そのインデックスが受信し
たチャネル記号と同一であるような符号語を選択する。
選択された符号語（即ち、再生ベクトル）に基づいて、
復号器の内部状態が次状態関数によって更新される。符
号化器の内部状態が復号器にも知らされている場合に
は、復号器の次状態関数は、符号化器の状態を辿ること
ができる。従って、復号器によって生成された再生ベク
トルは、符号化器において決定された前記ベクトルに対
応する再生ベクトルと同じである。

要約すれば、初期状態をｓとした場合、有限状態ベクト
ル量子化器による符号化は、次の演算を順次繰り返して
行われる。

y_i＝ｑ（ｘ _i,s_i） _ｉ ＝ｐ（y_i,s_i） s_i+1＝ｆ（ _i, _i-1,…， _i-j+1） 初期状態をｓとした場合、有限状態ベクトル量子化器の
復号器の動作は、次の演算を順次繰り返して行われる。 _ｉ ＝ｐ（y_i,s_i） s_i+1＝ｆ（ _i, _i-1,…， _i-j+1） ＜サイド・マッチ・ベクトル量子化＞ 本発明によるサイド・マッチ・ベクトル量子化器は、完
全検索VQの部類に属する。「サイド・マッチ」なる名称
が示唆するように、サイド・マッチ・ベクトル量子化器
は、再生ベクトルの境界における輝度（明暗レベル）の
変化を可能な限り穏やかにするようにしたものである。
サイド・マッチ・ベクトル量子化器では、情報源画像の
画素行および画素列は一重マルコフ過程であるという前
提を背景としている。この前提が正しければ、現在のブ
ロック（符号化すべきブロック）に隣接する画素は、現
在のブロックに関して過去の履歴全体に含まれる全ての
情報を持っていることになる。換言すれば、画素の行お
よび列が一重マルコフ過程である場合、現在のブロック
は、現在のブロックに隣接する画素が与えられれば、そ
れ以外の過去の全ての履歴とは独立していると仮定でき
る。従って、過去の履歴に対する量子化の影響は無視
し、符号化すべき画素ブロックに隣接する画素のみによ
って状態を生成する必要がある。このことは、前述の空
間的隣接性（第７図の斜線部分を参照）と密接な関係が
ある。また前記の仮定により、状態コードブックとして
は、状態の生成に関与する再生画素に最も類似した画素
を境界に有する符号語の集合を選択することが最良であ
ることが推察される。換言すれば、状態コードブック
は、最良の「サイド・マッチ」を有する符号語の集合で
ある必要がある。「サイド・マッチ」が他のタイプの有
限状態ベクトル量子化器より優れている点は、再生ベク
トルがスーパー・コードブック中の最良の符号語でない
場合でも、それによる誤差が再生画像の中で目立ち難い
ことが多いことである。

サイド・マッチ・ベクトル量子化器の全体的構成が、第
２図に与えられている。この図の構成要素を一通り簡単
に説明する。本節において混乱を避けるために、行およ
び列を有する行列型のベクトルにはブロック、行ベクト
ルまたは列ベクトルにはベクトルという用語を用いるこ
とにする。

前節で展開した用語を使用してサイド・マッチ・ベクト
ル量子化器の特徴を述べるため、初めに状態空間を定義
する。全ての情報源（画素）ブロックがm x nの大き
さ、即ちｍ行およびｎ列の画素を有する行列であるとす
る。各状態は、ｍ次元の列状態ベクトルおよびｎ次元の
行状態ベクトルの対で表される。つまり、列状態ベクト
ルをｕ、行状態ベクトルをｖとした場合、状態は（ｕ，
ｖ）の形式である。列状態ベクトルが、列状態空間と称
するアルファベットｕを有し、行状態ベクトルが行状態
空間と称するアルファベットｖを有するものとする。こ
のようにすると、状態空間は、列状態空間および行状態
空間のデカルト積、即ちｓ＝ｕ×ｖとなる。これらの列
および行の状態ベクトルの意義は、これらのベクトルに
よって符号化すべき情報源ブロックに隣接する再生画素
が表されることである。

前述のように、サイド・マッチ・ベクトル量子化器は、
状態空間に各状態に対する状態コードブックを備えてい
なければならない。スーパー・コードブックをＣとし
て、状態コードブックを説明する。状態ｓ＝（ｕ，ｖ）
が与えられると、それに対応する状態コードブックは、
各辺に沿って、即ち第１列および第１行に沿ってｕおよ
びｖに最も良く一致する元からなる、スーパー・コード
ブックの部分集合であると定義される。正確を期するた
めに、サイド・マッチ歪ｅを次のように定義する。先
ず、［ｘ］₁ ^cおよび［ｘ］₁ ^rが、ブロックｘの１番目の
列ベクトルおよび１番目の行ベクトルをそれぞれ示すも
のとする。つまり、［ｘ］₁ ^c＝（x₁₁,x₂₁,…,x_m1）^Ｔお
よび［ｘ］₁ ^r＝（x₁₁,x₁₂,…,x_1n）とする。ここでx_j1
はｘの第ｊ行、第１列にある要素を示し、肩文字Ｔは転
置行列（transpose）であることを示す。状態ｓ＝
（ｕ，ｖ）およびmxnのブロックｘが与えられると、サ
イド・マッチ歪は、歪測度ｄおよび加重定数ａおよびｂ
に対して、ｅ（s,ｘ）＝ad（ｕ，［ｘ］₁ ^c）＋bd（ｖ，
［ｘ］₁ ^r）と定義される。例えば、歪測度を平均自乗誤
差とし、更にａ＝ｂ＝1/2とすることができる。この場
合、状態ｓ＝（ｕ，ｖ）に対する状態コードブロックC_s
は、C_s＝（ｃ ₁ ^s,ｃ ₂ ^s,…，ｃ _N ^s）と定義される。ただ
し、ここでC_sの元の条件（Ａ）、（Ｂ）および（Ｃ）を
満足するものとする。即ち、 （Ａ）１＝1,2,…,Nならばｃ ₁ ^s∈Ｃ （Ｂ）１≦1₁≦1₂≦Ｎならば、 常にｅ（s,ｃ ₁ ^s）≦ｅ（s,ｃ ₁ ^s） （Ｃ）１＝1,2,…,N、かつ全てのｃがｃ∈Ｃ−C_sなら
ば、ｅ（s,ｃ ₁ ^s）≦ｅ（s,ｃ） であるとする。

要するに、状態ｓが与えられた場合、状態コードブック
C_sは、最小のサイド・マッチ歪を有するＮ個の符号語を
サイド・マッチ歪に関して昇順に配列して含む、スーパ
ー・コードブックの部分集合である。この定義に関し、
状態コードブックは単なる集合ではなく順序集合（シー
ケンス）であることに注意を要する。この順序による情
報は、以下において無雑音符号化を考察する際に、大変
重要である。

場合によっては、サイド・マッチ・ベクトル量子化器の
量子化演算子および逆量子化演算子は、有限状態ベクト
ル量子化演算子および逆量子化演算子の一般的な定義と
変わらない。前節の定義のように、歪測度ｄを有する完
全検索型の量子化器の動作は、 であり、また、その逆量子化器の動作は、ｃ ∈C_sかつη（ｃ,C_s）＝ｙ のとき、 ｐ（y,s）＝ｃ となる。

サイド・マッチ・ベクトル量子化器の次状態関数を実際
の符号化過程の観点から説明する。サイド・マッチ・ベ
クトル量子化器において、状態の生成に関与するのは、
２つの過去の再生ブロックだけである。符号化が、画像
上で、先ず左から右へ（西から東へ）進み、次に上から
下へ（北から南へ）進むと仮定すると、前記の２つの再
生ブロックは、第７図に示すように、次のブロックの北
および西の辺と隣接している。第７図の斜線の部分は、
同図における最終のブロックを符号化するための状態の
生成に関わる画素に担当する。x_iまでの全ての画素ブロ
ックが符号化されて…,x_i-2,x_i-1,x_iとなり、次状態関
数がｘ _i+1の符号化に備えるものとする。このとき、次
状態関数ｆの動作は、次のように表される。

s_i+1＝ｆ（ _i, _i-J+1） ここでＪは画像におけるブロック列の個数、（即ち、画
像の幅に丁度納まるブロック数）である。具体的には、
次状態関数により、西側の再生ブロック_ｉが列状態に
ベクトルｕ _i+1に、北側の再生ブロック_i-J+1が行状態
ベクトルｖ _i+1に、写像される。列状態空間Ｕおよび行
状態空間Ｖが与えられると、最小歪の原則によって列状
態ベクトルおよび行状態ベクトルが生成される。即ち、 写像ｆの変域および直域が、共に有限で、かつそれらの
濃度が相対的に小さいので、写像ｆは探索テーブルによ
って実現される。

次に、サイド・マッチ・ベクトル量子化器の設計手順の
他、符号化および復号の手順も説明する。実際に画像を
符号化する状況では、状態が正しく定義できないため
に、サイド・マッチ・ベクトル量子化器を適用できない
画素ブロックも幾つかある。それらは、画像の最上段、
左辺にあるブロックである。そのようなブロックに独断
的に状態を割り当てると、それらのブロックのみなら
ず、後続のブロックに対しても符号化の歪が増大するの
で、他のブロックとは区別して扱う必要がある。その結
果、符号のビット率が、若干（一般に１％にも満たない
程度）増加する。この増加分を無視すれば、サイド・マ
ッチ・ベクトル量子化器のビット率は、画素当たりlog₂
N/（mn）ビットである。例えば、ｍ＝ｎ＝４（第７図）
かつＮ＝256の場合、ビット率は、画素当たり1/2ビット
となる。

＜SMVQの符号化手順＞ （１）スーパー・コードブックを有するメモリ無しベク
トル量子化器（例えば、完全検索ベクトル量子化器）に
よって、画像の第１行、第１列の画素ブロックを、符号
化する。その他のブロックに対しては、ステップ２およ
び３のみを繰り返す。

（２）西側および北側の再生ブロックから、状態を生成
する。

（３）対応する状態コードブックを有する量子化器を用
いてブロックを符号化する。

＜SMGQの復号手順＞ （１）スーパー・コードブックをテーブルで検索するこ
とによって、画像の第１行、第１列にある画素ブロック
を復号する。その他のブロックに対しては、ステップ２
および３のみを繰り返す。

（２）西側および北側の再生ブロックから、状態を生成
する。

（３）対応する状態コードブックを有する逆量子化器を
用いて、ブロックを復号する。

サイド・マッチ・ベクトル量子化器においては、状態コ
ードブックの設計に情報源の統計を必要としないので、
設計手順は単純である。

＜コードブックの設計手順＞ ２次元の情報を符号化するために本発明を使用するに
は、必ず「サイド・マッチ」および「オーバラップ・マ
ッチ」の原理に従って状態コードブックを設計する必要
がある。設計の成否は、存在し得る莫大な数の量子化ベ
クトルの中から適切な選択を行うかどうかに依存する。

符号化すべきブロック毎に、16画素がある。典型的なシ
ステムでは、各画素に対して256階調の明度である。従
って、各ブロックについて（256）¹⁶、即ち、400億以上
のベクトルが有り得る。

２次元データの分野、即ち視覚的な画像から始めること
は、当システムを意図的に使用することから考えれば、
ある意味では当然と看做すことができるが、そのために
は、（256）¹⁶通り可能な符号ベクトルから最も代表的
なベクトルを決定する必要がある。

前記のAravindおよびGershoによる記事の設計手順で
は、いくつかの異なる状態のコードブックで初め、その
後それに伴って前記のコードブックが共にスーパー・コ
ードブックを持つようになるのであるが、これとは異な
り、本発明の手順では、第４図に示すように、仕込用の
画像に見いだされる画素ブロックに対する1024個の最良
の代表であるスーパー・コードブックから開始する。ベ
クトルに応用されるような最大尤度法など、周知の最適
化技法は、全て使用することができる。

次に、「サイド・マッチ」および「オーバラップ・マッ
チ」の原理を用いて、前記スーパー・コードブックか
ら、異なる状態のコードブックの以下のように構築す
る。

スーパー・コードブックに属する1024個の代表ブロック
の左側の列および最も下の行から成る10⁶以上の可能な
対の中から、（符号化すべき２次元情報ブロックを入力
するために前述の「マッチング」に使用するものを得る
ために）、スーパー・コードブックのブロックを最も良
く代表する行および列の対を次のように選択する。

前記の10⁶対の各候補対に対し、最も良く一致する256の
ブロック、即ち、その最上行が候補対の行部分に合わせ
られ、各ブロックの左側の列が候補対の列部分に合わせ
られたブロックによって、暫定的な状態コードブックを
形成する。そして、各候補対に対し最も良く一致するブ
ロックを決定する。やはり、この場合も、最小サイド・
マッチ歪などの周知の最適化方法を使用することができ
る。

10⁶以上存在し得る状態コードブックから、128の行の部
分および128の列の部分の対の組みに合わされた、各々
の256の要素に対し最良総合得点（最小総合歪）を持つ
として選択することにより、縮小集合（＝（128）^２≒1
6,000）が形成される。

状態コードブックは、第１図の状態コードブックの集合
19を含むメモリ、即ちメモリ装置に表される。

＜オーバラップ・マッチ・ベクトル量子化器＞ オーバラップ・マッチ・ベクトル量子化器（OMVQ）は、
有限状態ベクトル量子化器の部類に属し、サイド・マッ
チ・ベクトル量子化器に良く似ている。しかし、サイド
・マッチ・ベクトル量子化器を含む、その他の画像用VQ
とは異なり、OMVQの情報源（画素）ブロックは、一部重
複して構成される。換言すれば、重複する幅および高さ
を、それぞれn₀列およびm₀行とすれば、画像の境界に沿
ったブロックは例外として、情報源ブロックの最初のn₀
列は、情報源ブロックの最後のn₀列の左（西）への複製
であり、その情報源ブロックの最初のm₀行は、その情報
源ブロックの最後のm₀行の真上（北）への複製である。
この状態を、ｍ＝ｎ＝４かつm₀＝n₀＝１の場合に付い
て、第８図に示す。

OMVQの構成は、サイド・マッチ・ベクトル量子化器のそ
れと非常に類似しているので、前節で導入した表記を借
用してオーバラップ・マッチ・ベクトル量子化器の構成
要素を説明する。オーバラップ・マッチ・ベクトル量子
化器のブロック線図を第１および３図に示す。OMVQに対
し、大きさmxnの情報源ブロックを考えることにする。
状態空間の各状態を、１対のブロック、即ち列状態ブロ
ックと呼ぶmxn₀のブロック行状態ブロックと呼ぶm₀xnの
ブロックによって表される。つまり、mxn₀の列状態ブロ
ックをｕ、m₀xnの行状態ブロックをｖとしたとき、状態
は（ｕ，ｖ）の形式となる。列および行の状態ブロック
が、それぞれ列状態空間および行状態空間と呼ばれる、
アルファベットｕおよびｖを有するものとする。SMVQの
場合のように、OMVQの状態空間Ｓは、デカルト積ｕ×ｖ
である。これらの列および行の状態ブロックの意義は、
それらが符号化すべき情報源ブロックと重複する再生画
素を表すことである。

OMVQの状態コードブックは、次のように定義される。所
与のスーパー・コードブックＣおよび状態ｓ＝（ｕ，
ｖ）に対し、対応する状態コードブックは、重複領域に
おいてｕおよびｖに最も一致する元からなる、ｃの部分
集合であると定義される。OMVQの状態コードブックを説
明するために、照合による歪ｅを定義し、これをオーバ
ラップ・マッチ歪と命名する。先に導入した表記の拡張
として、 および が、列1₁から1_jまでを集めて形成したmxj個のブロッ
ク、行1₁から1_jまでを集めて形成したjxn個のブロック
を、それぞれ表すものとする。所与の状態ｓ＝（ｕ，
ｖ）およびmxnブロックｘに対し、オーバラップ・マッ
チ歪は、次のように定義される。

ただし、ｄは歪測度、ａおよびｂは定数である。

ここで、OMVQの状態コードブックの定義は、サイド・マ
ッチ歪をオーバラップ・マッチ歪で置き換えればSMVQの
場合の定義と同じである。つまり、スーパー・コードブ
ックＣおよび状態ｓ＝（ｕ，ｖ）が与えられた場合、そ
の状態に対する状態コードブックC_sは、 C_s＝（ｃ ^s ₁,ｃ ^s ₂,…，ｃ ^s _N） と表されるとき、C_sの元が前節の（Ａ），（Ｂ）および
（Ｃ）を満足するものとして定義される。この場合も、
各状態コードブックの元は、順番に配列されていること
に注目したい。

OMVQの状態コードブックが確立したので、OMVQの量子化
器および逆量子化器も、一般のFSVQのものと変わらな
い。

OMVQの次状態関数を説明するために、部分的に重複した
ｘ _ｉまでの情報源ブロックが、…， _i-2, _i-1, _ｉに
符号化済みであるとする。すると、状態s_i+1は、次状態
関数ｆによって、 s_i+1＝ｆ（ _i, _i-J+1） として生成される。ただし、Ｊは、画像において部分的
に重複するブロックの列の数（即ち、画像の幅に丁度納
まり、部分手に重複するブロックの数）である。が画
像の画素列の数を表すとすれば、Ｊを次式により算出す
ることができる。

Ｊ＝（−ｎ）／（ｎ−n₀）＋１ 具体的には、次状態関数は、西側の再生ブロック
_ｉを、列状態ブロックｕ _i+1に写像し、北側の再生ブロ
ック _i-J+1を、行状態ブロックｖ _i+1に写像する。所与
の列状態空間ｕおよび行状態空間ｖに対し、列状態ブロ
ックおよび行状態ブロックが、最小歪の原則によって生
成される。つまり、 写像ｆの変域および値域が、共に有限で、かつ濃度が相
対的に小さいので、写像ｆは探索テーブルによって実現
される。状態の生成に関与する画素を、第８図に斜線を
施した領域として示す。

OMVQの定義は、SMVQの定義に類似している。特に、m₀＝
n₀＝１の場合、単純な前処理装置（preprocessor）によ
りOMVQをSMVQと看做すことができる。具体的には、前処
理装置を用いて画素の行および列を複製することによ
り、OMVQであれば重複領域にあるべき「拡張画像」を構
成すれば、画像に適用されるOMVQの処理は、前記の拡張
画像に適用されるSMVQの処理と同一である。しかしなが
ら、再構成された画像も拡張されていることに注意を要
する。

元の画像の大きさの再生画像を復元するために、オーバ
ラップ解除関数と呼ぶ構成要素を更に導入し、これによ
って、複製された画素の各対を最終的な再生画素へと写
像する。量子化の誤差のために、再生中に複製される画
素は、その対の片方と同じにならない。換言すれば、複
製された各画素は、２通りに別個に再生される。これら
の異なった再生画素（同一の元の画素から再生された画
素）の対は、元の画素に関する情報を、単一に再生され
た画素より多く含んでいることが容易に想像できる。従
って、このような異なった再生画素の対の一方を重複解
除関数によって捨てるべきではない。詳しく説明するた
めに、重複解除関数ｈを、符号化器において複製された
再生画素の各双子対に作用し最終的な再生画素を生成す
る写像である、とする。x₁およびx₂で再生画素の双子対
を表すと、最終的な再生画素は、＝ｈ（x₁,x₂）と表
される。重複解除関数は、例えば、ｈ（x₁,x₂）＝（x₁
＋x₂）/2である。

次に、OMVQの設計手順の他、符号化および復号の手順も
説明する。状態コードブックおよび次状態関数が与えら
れれば、OMVQの符号化手順は、情報源ブロックどうしが
互いに一部重複していることを除けば、SMVQの符号化手
順と同じである。一方、OMVQの復号手順は、SMVQの復号
手順に比べて、更に１段、即ち重複解除操作を経る。従
って、OMVQの復号手順は、単にSMVQの復号手順に続いて
重複解除操作を行うだけである。

OMVQの設計手順も、SMVQの場合に似ていて、第４図によ
って表すことができる。

＜OMVQの設計手順＞ （１）スーパー・コードブック 何らかのコードブック設計アルゴリズムを用いてスーパ
ー・コードブックを設計する。

（２）状態空間 コードブック設計アルゴリズムにより、スーパー・コー
ドブックの符号語全体の最後のn₀列および最後のm₀行を
それぞれ仕込用の集合として使用して、列状態空間およ
び行状態空間を生成する。

（３）状態コードブック スーパー・コードブックの中から、「設計手順」の下で
前述した状態コードブックの条件を満足する部分集合を
選ぶことにより、状態コードブックを設計する。m₀＝n₀
＝１の場合、スーパー・コードブック、状態コードブッ
ク、および状態空間は、SMVQとOMVQとの間で相互に交換
して使用することができる。

ここで、伝送するために符号語のインデックスを無雑音
符号化する問題に戻る。

画像どうしに高い相関関係があり、各状態コードブック
において照合による歪によって順序付けが為されている
ことから、チャネル記号の分布は単調な減少傾向を示す
と、推測することができる。ａおよびｂを定数とした場
合、チャネル記号の分布は事実｛ｂμ^-a:μ＝1,2,…,
N｝に近似することが、実験から判っている。以下にお
いて、分布が急速に減少するように、小さいレベルしか
持たない一種の無雑音符号を提案し、それらが最適に近
いことを示す。

ここで提案する無雑音符号は、基本的には周知のハフマ
ン符号（Huffman code）であり、これは減衰の速い分布
に対する階段近似のために設計されたものである。しか
し、記号の個数が２の累乗でない場合は、提案する無雑
音符号と近似のためのハフマン符号とは若干異なること
がある。急速に減少する確率分布Ｐ、即ち（P₁,P₂,…,P
_N）に対し、次の条件を満足する階段近似を定義す
る。即ち、ｊ＝0,1,2,…,Log₂N（Log₂Nは整数）なるｊ
に対し、 （Ａ）2^j-1＜μ、ν≦2^jである限り、_μ＝ 前記の定義の（Ｂ）の部分によって、もまた確率分布
である。Ｎが大きい場合、に対してハフマン符号を設
計することは、一般に容易なことではない。しかし、こ
の分布は特殊な形式なので、ハフマン符号の設計は、
次のように大幅に単純化することができる。初めに、確
率の集合 に対しハフマン接頭符号（Huffman prefix code）を設
計する。次に、各ｊに対し総計区間内の記号を見分ける
ために、接尾語（suffix）と呼ばれる単純な固定長のバ
イナリー符号を、前記のハフマン接頭符号に連結する。
各ｊに対する総計区間における記号の個数は、 である。ただし、 はｊより小さくない最小の整数である。従って、前記の
接尾語の長さは、_max｛ｊ−1,0｝である。ここで言う
「接頭符号」は、二重の意味を持つ。その一つは、接頭
符号における何れのバイナリー符号語も、その接頭符号
内の他の何れのバイナリー符号語においても接頭語でな
い、と言うことである。もう一つは、接頭符号はその接
尾語に対する接頭語である、と言うことである。前者の
意味では、結果として得られる無雑音符号も、また接頭
符号である。更に、Ｎが２の累乗である場合、この無雑
音符号が、分布に対して最適であることを示すのは困
難なことではない。

＜コードブックの設計＞ 第４図に、流れ線図を示す。この流れ線図の処理によっ
て、スーパー・コードブックおよびそれから抽出すべき
全ての状態コードブックを設計する。先ず、本質的な特
性の面で伝送すべき画像に対して統計的類似性を有する
仕込用の画像を選択する必要がある。このような画像を
仕込用画像（training image）という。最初の段階にお
いて、これらの仕込用画像を、小さなブロックに分割す
る（ステップ61）。そして、これらの仕込用ブロック
を、ロイド（Lloyd）クラスター化アルゴリズムによっ
てクラスター化する。

前記のクラスター化処理が済むと、ベクトルを量子化し
た符号、即ち1024個の符号のスーパー・コードブックを
構築できるようになる。次の段階で、前記のスーパー・
コードブックから状態コードブックを構成するために前
記本質特性を抽出し、スーパー・コードブックから状態
コードブックに対する種々の構成要素を選択できるよう
にする。この処理の最初の段階は、ステップ63で示さ
れ、ここでは、スーパー・コードブックにおけるブロッ
クを表す各符号語に対して最後の画素列を選択する。最
後の画素列からなるこれらの集合は、ロイドのクラスタ
ー化アルゴリズムによってクラスター化される（ステッ
プ64）。これと平行して行われる処理において、最後の
画素行が選択される（平行するステップ65および66）。
行ベクトルに対するクラスター化ステップ66において
も、スーパー・コードブックから照合歪が最小のコード
ブックがＮ個選択される。この結果、これら２つの平行
処理から、状態コードブックを得る。各状態コードブッ
クの大きさはＮ（例えば、Ｎ＝256）である。具体的に
は、クラスター化された符号語における情報は、次のよ
うに構成される。即ち、ｕが列状態空間にあり、ｖが行
空間にあるような１対の値ｕおよびｖの各々に対して、
スーパー・コードブックから照合歪が最小の符号語をそ
れぞれＮ個選択する。ステップ67で必要となる最小照合
歪の符号語の選択において、例えば16,000の状態コード
ブックを作成するために、計算を中心とする照合歪の算
出および検索を行う必要がある。この計算は、第１図の
送信部10の実時間動作に先だって、集中的に行う方が有
利である。

第５図は、第１図の符号化器41の動作を幾分異なる方法
で理解しやすく説明する流れ。線図である。この段階の
中には、第１図のブロックと明らかに類似するものがあ
る例えば、ステップ71によって伝送すべき入力画像が4x
4画素の小さなブロックに分割される。ステップ72で
は、既に述べた最小平均自乗誤差最近似値検索法に従っ
て、現在の状態コードブックの符号語の最近似値にある
ものを見つける。この結果、状態コードブックから得ら
れた符号語のインデックスは、ステップ73でその符号語
に逆変換され、数学的に前述したように境界不連続最小
法または重複不連続最小法に必要な過去の画像統計を与
える。この符号語のインデックスは、伝送のためのバイ
ナリー符号化ステップ74にも与えられ、ステップ75にお
いて、そのインデックスに可変流無雑音符号語を割り当
てることを可能にする。ステップ73（逆量子化器13と同
じ）のテーブル探索の結果得られる符号語は、第６図の
ステップに示したように第１図の論理回路42に与えられ
る。第５図および６図は一続きのプロセスである。第６
図に示すように、隣接する列のサイド・マッチ操作のた
めに、ステップ81で１ブロック分の遅延を導入すること
により、現在符号中の画素ブロックｘの左側にある符号
化済みのブロックがｘの符号化中に現れるようにする。
画素ブロックｘのすぐ左側の符号化済みのブロックは、
すぐ前の画素列にあり、これがステップ83で言う列状態
空間における最近似値ベクトルである。その列状態ｕに
対し、類似のステップ84、85、および86から得られる同
様のベクトルｖを使用する。ただし、ステップ84では、
遥かに大きな遅延を与えることにより、前に符号化され
た行または行の集合にあるブロックが、行状態ベクトル
ｖ（これは、その行状態にある最近似値値を表す）を結
果的に生成する連続性の検査に使用されるようにする必
要がある。つぎに、テーブルを探索することによりベク
トルｕおよびｖに対して適当な状態コードブックを見つ
け、この結果ステップ87において状態コードブックを選
択したことになる。この点において、サイド・マッチお
よびオーバラップ・マッチの間には次のような相違があ
る。即ち、本発明によるサイド・マッチ・ベクトル量子
化においては、画像の画素ブロックは、重複していない
ので、行１、２、３おび４がブロックの最初の集合を表
し、行５、６、７および８がブロックの２番目の集合を
表すといった具合であり、同様の原則が列にも適用され
る。オーバラップ・マッチ・ベクトル量子化において
は、行１、２、３および４がブロックの最初の集合を表
し、次に行４、５、６および７が２番目のブロックを表
すので、行４の画素は、適当な遅延時間の後に続けて、
行から行へと符号化する際に輝度変化の程度が最小とな
るように、別のブロックへと符号化される。重複（オー
バラップ）により変化は最小化されるが、そのブロック
に、例えば行３から他の値が現れることにより、ある変
化が強いられる。これらの方式の両方ともAravindおよ
びGershoの方式と対象的なのは、エッジは現在のブロッ
クを通ってブロック自体のエッジに抜け出る可能性があ
るものであるが、後者がそのようなエッジにまたがる画
素の間の連続性の度合いを強調していることである。そ
れに対して、本発明では、AravindおよびGershoのよう
に画素の値を直接的な情報に変換することにより生じる
ほどの希薄化を伴うことなく、空間的隣接性を利用して
いる。

ここでサイド・マッチ・ベクトル量子化およびオーバラ
ップ・マッチ・ベクトル量子化と命名した、各画素の値
における空間的隣接性の情報を直接利用する方法は、前
記と異なった実施例にも明らかに応用可能である。例え
ば、隣接する２行および隣接する２列における各画素の
値も考え得る。

【図面の簡単な説明】

第１図は、本発明による通信システムの送信部を示すブ
ロック線図、 第２図は、本発明によるシステムの送信部および受信部
間の関係を示すブロック図、 第３図は、本発明による受信部を更に詳細に示すブロッ
ク図、 第４図は、本発明によるコードブック設計過程を示す流
れ線図、 第５図は、本発明に従って画像情報を実際に符号化する
過程の動作を示す流れ線図、 第６図は、次の状態コードブックを見つける手法を示す
流れ線図、 第７図は、仕込（コードブック設計）および符号化に
「サイド・マッチ」構成を使用する場合の典型的な画素
の構成を示す図、 第８図は、仕込（コードブック設計）および符号化に
「オーバラップ・マッチ」構成を使用する場合の典型的
な画素の構成を示す図である。

Claims (9)

【特許請求の範囲】
1. 【請求項１】行ｉ＝1,…,i_maxおよび列ｊ＝1,…,j_maxを
   有する画素Ｐ_i,jの配列からなり行Ｉ＝1,…,I_maxおよび
   列Ｊ＝1,…,J_maxを有するブロックＢ_I,Jの配列中の１つ
   のブロックを表す信号を符号化して符号化信号を形成
   し、その符号化信号に基づいて前記ブロックが再構成さ
   れるようにするための符号化方法において、 それぞれインデックスによって識別される複数の符号語
   を格納した複数のコードブックのうちから、Ｂ_Ｉ−1,J
   の第i_max行およびＢの_I,J−１の第j_max列のみに基づい
   て１つのコードブックを選択するステップと、 選択したコードブック内の符号語のうちから、所定の誤
   差基準に基づいて、Ｂ_I,Jを最も良く近似するように選
   択される符号語のインデックスを決定するステップと、 決定したインデックスに基づいて符号化信号を形成する
   ステップと、 その符号化信号を通信路を通じて伝送するステップとか
   らなることを特徴とする２次元情報の符号化方法。
2. 【請求項２】画素の配列からなるブロックの配列中の特
   定のブロックを表す第１信号を符号化して符号化信号を
   形成する符号化方法において、 それぞれ対応するインデックスを有する複数の符号語を
   格納した複数のコードブックのうちから、前記特定のブ
   ロックの上隣のブロック内の最下行の画素および前記特
   定のブロックの左隣のブロック内の最右列の画素のみに
   基づいて１つのコードブックを選択するステップと、 選択したコードブック内の符号語のうちから、所定の誤
   差基準に基づいて、前記特定のブロックを最も良く近似
   する符号語を選択するステップと、 選択した符号語に対応するインデックスに基づいて符号
   化信号を形成するステップと、 その符号化信号を通信路を通じて伝送するステップとか
   らなることを特徴とする２次元情報の符号化方法。
3. 【請求項３】前記コードブックを選択するステップは、 前記特定のブロックの上隣のブロックを符号化するのに
   使用したコードブック内の符号語に対応する第１インデ
   ックスに基づいて第１符号語を形成するステップと、 前記特定のブロックの左隣のブロックを符号化するのに
   使用したコードブック内の符号語に対応する第２インデ
   ックスに基づいて第２符号語を形成するステップと、 前記第１符号語を１行分遅延させ、前記特定のブロック
   の上隣のブロック内の最下行の画素のみを通過させるよ
   うに前記第１符号語をフィルタリングすることによっ
   て、行状態出力信号を生成するステップと、 前記第２符号語を１列分遅延させ、前記特定のブロック
   の左隣のブロック内の最右列の画素のみを通過させるよ
   うに前記第２符号語をフィルタリングすることによっ
   て、列状態出力信号を生成するステップと、 前記行状態出力信号および前記列状態出力信号に基づい
   てコードブックを選択するステップとからなることを特
   徴とする請求項２の方法。
4. 【請求項４】前記コードブックを選択するステップは、 それぞれ画素の配列からなるトレーニングブロックのセ
   ットから導出される符号語のセットに基づいてスーパー
   コードブックを生成するステップと、 前記スーパーコードブックから複数のコードブックを生
   成するステップとからなり、 この複数のコードブックを生成するステップは、 前記トレーニングブロック内の最下行の画素を表す各符
   号語の部分と、前記トレーニングブロック内の最右列を
   表す各符号語の部分との対を形成するステップと、 各対ごとに、前記符号語のセットのうちから、誤差基準
   に従ってその対に最も良く一致する符号語のサブセット
   を選択し、その対に対応するコードブックとするステッ
   プと、 前記対応するコードブックのうちから、歪み基準を満た
   す符号語を含むコードブックのサブセットを選択するス
   テップとからなることを特徴とする請求項２の方法。
5. 【請求項５】画素の配列からなるブロックの配列中の特
   定のブロックを表す符号語に対応するインデックスを表
   す第２信号を復号して復号信号を形成する復号方法にお
   いて、 通信チャネルから前記第２信号を受信するステップと、 それぞれ対応するインデックスを有する複合の符号語を
   格納した複数のコードブックのうちから、前記特定のブ
   ロックの上隣のブロック内の最下行の画素および前記特
   定のブロックの左隣のブロック内の最右列の画素のみに
   基づいて１つのコードブックを選択するステップと、 選択したコードブック内の符号語のみから、前記第２信
   号によって表されるインデックスに対応する符号語を決
   定するステップと、 決定した符号語に基づいて符号信号を形成するステップ
   とからなることを特徴とする２次元情報の復号方法。
6. 【請求項６】前記コードブックを選択するステップは、 前記特定のブロックの上隣のブロックを符号化するのに
   使用したコードブック内の符号語に対応する第１インデ
   ックスに基づいて第１符号語を形成するステップと、 前記特定のブロックの左隣のブロックを符号化するのに
   使用したコードブック内の符号語に対応する第２インデ
   ックスに基づいて第２符号語を形成するステップと、 前記第１符号語を１行分遅延させ、前記特定のブロック
   の上隣のブロック内の最下行の画素のみを通過させるよ
   うに前記第１符号語のフィルタリングすることによっ
   て、行状態出力信号を生成するステップと、 前記第２符号語を１列分遅延させ、前記特定のブロック
   の左隣のブロック内の最右列の画素のみを通過させるよ
   うに前記第２符号語をフィルタリングすることによっ
   て、列状態出力信号を生成するステップと、 前記行状態出力信号および前記列状態出力信号に基づい
   てコードブックを選択するステップとからなることを特
   徴とする請求項５の方法。
7. 【請求項７】前記決定するステップは、 それぞれ画素の配列からなるトレーニングブロックのセ
   ットから導出される符号語のセットに基づいてスーパー
   コードブックを生成するステップと、 前記スーパーコードブックから複数のコードブックを生
   成するステップとからなり、 この複数のコードブックを生成するステップは、 前記トレーニングブロック内の最下行の画素を表す各符
   号語の部分と、前記トレーニングブロック内の最右列を
   表す各符号語の部分との対を形成するステップと、 各対ごとに、前記符号語のセットのうちから、誤差基準
   に従ってその対に最も良く一致する符号語のサブセット
   を選択し、その対に対応するコードブックとするステッ
   プと、 前記対応するコードブックのうちから、歪み基準を満た
   す符号語を含むコードブックのサブセットを選択するス
   テップとからなることを特徴とする請求項５の方法。
8. 【請求項８】画素の配列からなるブロックの配列中の特
   定のブロックを表す第１信号を符号化して符号化信号を
   形成する符号化システムにおいて、 それぞれ対応するインデックスを有する複数の符号語を
   格納した複数のコードブックのうちから、前記特定のブ
   ロックの上隣のブロック内の最下行の画素および前記特
   定のブロックの左隣のブロック内の最右列の画素のみに
   基づいて１つのコードブックを選択する手段と、 選択したコードブック内の符号語のうちから、特定の誤
   差基準に基づいて、前記特定のブロックを最も良く近似
   する符号語を選択する手段と、 選択した符号語に対応するインデックスに基づいて符号
   化信号を形成する手段と、 その符号化信号を通信路を通じて伝送する手段とからな
   ることを特徴とする２次元情報の符号化システム。
9. 【請求項９】画素の配列からなるブロックの配列中の特
   定のブロックを表す符号語に対応するインデックスを表
   す第２信号を復号して復号信号を形成する復号システム
   において、 通信チャネルから前記第２信号を受信する手段と、 それぞれ対応するインデックスを有する複数の符号語を
   格納した複数のコードブックのうちから、前記特定のブ
   ロックの上隣のブロック内の最下行の画素および前記特
   定のブロックの左隣のブロック内の最右列の画素のみに
   基づいて１つのコードブックを選択する手段と、 選択したコードブック内の符号語のみから、前記第２信
   号によって表されるインデックスに対応する符号語を決
   定する手段と、 決定した符号語に基づいて復号信号を形成するステップ
   とからなることを特徴とする２次元情報の復号システ
   ム。