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

Abstract

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

Description

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

〔従来の技術〕

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

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

伝送の質を変えずにビット率を更に小さくするには、メ
モリを用いたベクトル量子化として特徴付けられるタイ
プのベクトル量子化を利用する必要があった。つまり、
既に符号化されている幾つかのブロックのメモリを後続
の入力ブロックに使用することにより、符号化処理にメ
モリが組み入れられる。有限状態ベクトル量子化として
知られているこの特殊な技術においては、以前に符号化
されている幾つかのベクトルに付いての重要な情報を端
的に表す状態を多数使用し、−群のいわゆるコードブッ
ク（符号器）から１つを選択して各入力ベクトルを符号
化する。この技術の例は、１９８７年７月出りの「光工
学（Ｏｐｔｉｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ）　Ｊ、
第２６巻のｐ、　５７０−ｐ、　６８０に記載のＲ，Ａ
ｒａｖｉｎｄおよびＡ１１ｅｎ　Ｇｅｒｓｈｏによる「
有限メモリを用いたベクトル量子化に基ずく画像圧縮（
Ｉｍａｇｅ　Ｃｏｍｐｒｅｓｓｉｏｎ　Ｂａ５ｅｄ　　
ｏｎ　Ｖｅｃｔｏｒ　Ｑｕａｎｔｉｚａｔｉｏｎ　Ｗｉ
ｔｈ　ＦｉｎｉｔｅＭｅｍｏｒｙ）　Ｊと題する記事に
見られる。

このようなシステムの符号器や複合器は、帰還構成を備
えていて、出力によって決定された内部状態が帰還され
、符号化および複合化のために入力と共に使用されるよ
うになっている。このような有限状態方式の目的は、希
望の低ビツト率を達成しつつ得られる伝送の質を維持す
ることである。

符号化すべき入力ベクトルを含む小領域を内部状態によ
って正確に表すことができれば、有限状態ベクトル量子
化は、コードブックの比較的短時間で変化する集合を用
いることにより前記の目的を実現することができる。

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

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

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

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

〔発明の概要〕

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

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

更に、仕込用の画像の統計あるいは入力画像自体に基づ
く可変長符号化を行うことにより、この改良システムの
有効性は、益々増大する。ここで提案する可変長無雑音
符号化は単純なので、ビット率がわずか高くなるだけで
、符号化した全内容を通信システムの受信側に伝送する
ことができる。

実際、本発明のこの特徴によれば、可変長無雑音符号の
ファミリーが記述され、いわゆるチャネル記号のエント
ロピーを確実に達成する。また、本発明のこの著しい特
徴は、他の有限状態ベクトル量子化設計に新たな改善を
施すことができる。

〔実施例〕

有限状態ベクトル量子化タイプ（Ａｒａｖｉｎｄらによ
る前述の記事に開示されているものを含む）の符号化ア
ルゴリズムを実施するなめに使用できるシステムと同様
に編成されている基本的な実施例を、第１図に示す、た
だし、詳しく吟味すれば、第１図の実施例が特に本発明
の著しい特徴に適合していることが解る。更に具体的に
は、第１図は、遠隔地間で画像を伝送する通信システム
の送信部に使用される本発明の実施例を示す、この送信
部は、走査撮影された画像信号を受は入れるように構成
されている。この画像信号は、テレビの画像送信用に従
来の方法で走査されたものであるが、高解像度のもので
もよい。また、これには、第１図のブロック形成段１１
によって示されるような画像の画素をブロック化する手
段も含まれる。各ブロックは、４ｘ４個の画素から成る
ブロックである。

例えば、最初のブロックは、走査された画像画素から成
る最初の４行の各行における最初の４個の画素を含む、
得られた各画素ブロックは、次に量子化器１２に渡さ九
　そこで後述のようにして選択される特定のコードブッ
クの中から所望の項目（符号語）を選択するために最近
似値の検索が行われる。この検索は、ブロック１１およ
び量子化器１２を備えた符号化部４１と連絡をとり合う
論理回路４２の管理下で行われる。この論理は、更に後
で詳述するように、適当な符号語のインデックスを、そ
の画素ブロックのエツジに最適マツチングした状態では
あるが適当に低いビット率で伝送することを可能とする
ようなものである。ブロックの形成および量子化器によ
る最近似値検索は、Ａｒａｖｉｎｄの記事にの１．１２
節に説明されているようにして行われる。端的には、次
のとうりである。画素ブロックは、例えば、最小の画像
単位である４ｘ４画素のブロックである。これらのブロ
ックは隙間なく配列さ九　その結果、各ブロックは、画
像がその表示画面、即ちその画像の２次元表示面にわた
って１行ずつ展開される方面に関して、幅４画素、奥行
き４画素となる。換言すれば、隣接する画素から成るブ
ロックを生成するのに、４行が使用される０次に、画素
ブロックは、量子化器に送られる。スイッチ位置の集合
１４の中から選択された１個のスイッチ位置によって現
在勤的に選択された状態コードブックから、例えば、ス
イッチ２０から、コードブックの限られた項目（符号語
）Ｃｔ、Ｃ２、およびＣ，、が、そのブロックの各画素
に対する実際の入力画素ブロックＸと、最小隔たりベー
スとして比較される。平均自乗誤差を最小とするＣ１の
値が選択され、更に、そのコードブック値のインデック
ス、つまりｉの値が、量子化器１２から符号語のインデ
ックスとして送られる。

これと同時に、この符号語のインデックスは、゛画像情
報の履歴の一部として使用され、その画像情報は、次の
状態のコードブック（これは、次の画素ブロックの選択
に使用される）を動的に選択するために使用される。

画像の履歴を使用して次の状態のコードブックを選択す
る論理は、第１ばの論理回路４２で見いだされる。前の
符号語のインデックスは、逆量子化器１３に渡される。

逆量子化器１３は、基本的には探索テーブルであり、前
の状態の符号語のインデックスをブロックを表す符号語
に復元変換する。この出力は、遅延およびその他の論理
処理に当てがわれ、回路スイッチ２０の以降の位置決め
動作に影響を与える。逆量子化（復号）された値が隣接
する画素ブロックにのみ影響するようにするために、逆
量子化器の出力信号は、列状態出力部および行状態出力
部にそれぞれ適当な時間に到達するよう、１ブロック遅
延回路２３および１ブロック行遅延回路２５を通される
。探索テーブル２２および２７は、それぞれ列状態空間
２１および行状態空間２８を伴っており、随意、状態コ
ードブック１９の個数を減らすことができる。列状態空
間２１および行状態空間２８は、全ての状態コードブッ
クにおける全ての標本ブロックの、それぞれ最終画素列
および最終画素行に対する標本値（代表値）の集合であ
る。

前述のブロック２１．２２．２７および２８は、状態コ
ードブックの数を減らすための機構であり、このために
、（符号化器内部の）必要なメモリ空間は少なくて済む
、状態コードブックの個数やメモリ空間に全く制限がな
ければ、これらのブロックは１．削除することができる
。検討中の画素列および画素行の標本値から、フィルタ
ー２４および２６を通過するのは、それぞれ最終列およ
び最終行のみであり、これらは、現在符号化中のブロッ
クに隣接するか、または重複する列および行の画素であ
る。前記画素列および画素行は、画像における標本値の
不連続性を避けようとする場合には、現在の画素の符号
化に最も関係する画素である。

従って、論理回路４２のこの部分が、先に引用したＡｒ
ａｖｉｎｄおよびＧｅｒｓｈｏのものとは構成および動
作を異にするところである。状態コードブック１９の１
つを選択する技術の差異は、特定の列状態が列状態出力
に現れ、特定の行状態が行状態出力に現れるところにあ
る。そして、これらの値は、スイッチ２０の制御部分に
与えられ、符号化すべき現在の画素ブロックの符号化に
際し、量子化器１２が最近似値を検索するのに使用され
る状態コードブックを制御する０例えば、列の状態の同
様なインデックスに対して使用されると分かっている行
の状態の順序集合を行状態インデックスによって配列し
、これに続けて、列状態の続いて連続するインデックス
に対する行状態を同様の順序に配列すると言うように、
使用することが分かっている全ての列状態が順番に配列
されるまで、繰り返すことにより、状態コードブックを
順番に配列することができる。そして、ブロック２２か
ら出力される列状態インデックスにより、スイッチ２０
は相応の列状態位置をカウントし、続いてブロック２７
から出力される行状態インデックスにより、スイッチ２
０は先にカウントされた列状態にふされしい行配列にお
ける相応の行状態をカウントする。探索テーブル２２お
よび２７が必要なのは、状態コードブックの縮小集合１
９に対して、スーパー・コードブック（後述する）の全
ての行状態インデックスが必ずしもスーパー・コードブ
ックの列状態インデックスとともに使用されるとは限ら
ないからである０選ばれた状態コードブックは、スーパ
ー・コードブックにおける統計的に類似するブロックか
らのコードブックの設計過程に従って同様な統計の２次
元特性、即ち、隣接する最も類似性のあるエツジ−つ前
のブロックであれば列のエツジ、−行前のブロックであ
れば隣接する行のエツジ）を生むようなコードブックで
ある。状態空間２１および２８がらブロック２２および
２７への入力に含まれ得るのは、前に決定された有限個
の可能な値のみであり、フィルタ２４および２６からの
入力に含まれ得るのも、　（値からなる）より大きい集
合からの前に決定された有限個の可能値のみであるから
、望むならば、ブロック２２および２７における最近似
値検索の動作を、探索テーブルによって行うことが可能
である。

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

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

換言すれば、符号語のインデックスは、更に（バイナリ
−）符号器３１でのバイナリ−符号化に当てかわれる。

このとき、ビット率が付随的に更に下がるが、その程度
は、接頭語長決定器３３および伝送用のバイナリー・コ
ードブック３２で定められる接頭語長次第である。

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

バイナリ−符号は、通信チャンネルまたはメモリ・チャ
ンネル３７によって受信部に伝送された後、送信部のバ
イナリー・コードブックと同様の探索バイナリー・コー
ドブック３５に従いバイナリ−復号器３４によって符号
語のインデックスに逆変換される。第２図の可変長符号
化論理は、後述の数学的処理に従って実施することがで
きる。

また、それに代わり、当分野で使用されているその他の
可変長無雑音符号化技術に従って実施することも可能で
ある。上述した別方式は、本発明の目的にかなう好まし
い一代替案であるが、唯一の方法ではない。

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

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

有限状態ベクトル量子化器の符号化器および復号器を詳
細に説明するために、これらを幾つかの構成ブロック、
つまり構成要素に展開する。即ち、これら構成要素は、
（１）状態の有限気合である状態空間Ｓ、（２）状態コ
ードブックの集合（Ｃ，：　ｓεＳ）、（３）量子化演
算子ｑ、（４）コードブック（符号テーブル）探索関数
である逆量子化演算子ｐ、そして最後に（５）次状態関
数で、である、これら構成要素の概要を説明すると、次
のようになる。状態空間は、状態と呼ばれるＭ個の記号
の集まりであり、ｓ　１．　ｓ　２・・・、Ｓ−が状態
を示すとすれば、Ｓ”（Ｓｔ、Ｓｔ・・・＋　Ｓ　Ｍ　
）となる、各状態コードブックは、符号語と呼ばれるに
次元ベクトルがＮ個集まった気合である。状態コードブ
ックの集合は、状態ごとにインデックスが付けられてい
る。従って、状態コードブックの総数は、状態空間の大
きさ、即ちＭに等しい０、全ての状態コードブックの和
集合を、スーパー・コードブックといい、Ｃで表す、つ
まり、Ｃ＝Ｕ、ε６Ｃ＊である。インデックスの集合Ｙ
＝（１，２・・・、Ｎ）は、チャネル記号空間といい、
全ての状態コードブックに共有される。

この名称の根拠は、状態コードブックの符号語のインデ
ックスがそのチャネルを介して伝送またはメモリされる
ことになるチャネル記号であるからである。量子化演算
子は、ｋ次元ユークリッド空間Ｒｋと状態空間Ｓとのデ
カルト積（積集合）からチャネル記号空間への写像であ
る。つまり、×でデカルト積を表すとすれば、ｑ：Ｒｋ
Ｘｓ→Ｙである。この量子化演算子は、ＲｋからＹへの
写像ｑ。

の集まり（ｑｓ：ｓ”Ｓｔとして理解できる。ただし、
ここでは説明の便宜をはかるため、量子化演算子には前
者の定義を使用する。量子化演算子によりデータの圧縮
が行われるという概念からすれば、量子化演算子は明ら
かに多対１の写像でなければならないので、その逆は有
り得ないと言うことになる。しかしながら、量子化演算
子の逆を模する逆量子化演算子（ｄｅ−ｑｕａｎｔｉｚ
ｅｒ　）と呼ばれる写像ｐを定義する。具体的には、逆
量子化演算子はＹＸＳからＣへの写像である。量子化演
算子が写像ｑ、の集まり（ｑｓ：５Ｃｓｌであると考え
れば、逆量子化演算子は、１対１の写像ｐ　ｓ　：　Ｙ
−４Ｃ８の集合（ｐｓ：５Ｃ３）と見ることもできる。

この場合、各ｐ、は、テーブル探索関数であり、各チャ
ネル記号を状態コードブックＣ，に属しインデックスが
そのチャネル記号と同じである符号語に写像する。有限
状態ベクトル量子化演算子の符号化器および復号器は、
有限状態機関として機能するので、それらの内部状態は
、標本採取時点ごとに、更新される必要がある。内部状
態の更新は、次状態関数ｆによって行われる。Ｊを次の
状態の生成に関わる過去の再生ベクトルの数とすれば、
次状態関数ｆは、スーパー・コードブックＣのｊ重デカ
ルト積から状態空間への写像であり、ｆ、　ｘ　、？。

、Ｃ→Ｓとなる。換言すれば、次状態関数は、選択され
た符号語の有限の過去の履歴から次の状態を生成する。

上述の構成ブロックを用いて有限状態ベクトル量子化器
の符号化器および復号器の特徴を説明する。有限状態ベ
クトル量子化器の符号化器は、状態空間、状態コードブ
ックの集合、量子化演算子、逆量子化演算子、および次
状態関数から成る五要素構成、即ち（Ｓ、（Ｃｓ：　５
ＥＳ）、ｑ、Ｐ、ｆ　）によって特徴付けられる。ここ
で、標本採取時ｉに、符号化器が状態空間Ｓの状態Ｓｉ
を持っているとする。すると、量子化演算子は、ｋ次元
情報源ベクトルＬを、ある基準に照らしてＸユに最も近
い、状態コードブックＣ，の符号語のインデックスｙｌ
であるようなチャネル記号ｙ、に写像させる。

この結果得られる符号語は、Ｘ、で表される再生ベクト
ルである。最も一般的な基準を掲げれば、次式で示され
る平均自乗誤差を最小にすることである。

ただし、［ｘｉ］ｊおよび［Ｕ］、は、それぞれベクト
ル量およびヌ−２の３番目の要素である。ここで論じて
いる量子化器は、基本的には、コードブックとして状態
コードブックを備えたメモリ無しベクトル量子化器であ
る。従って、有限状態ベクトル量子化器に使用可能な量
子化器には、種々の構成がある０例えば、ここで論じて
いる完全検索ベクトル量子化器（ＶＱ）の他に、樹状検
索ＶＱ、多段ＶＱ、およびｆｆＶＱ等がある。なお、本
明細書では完全探索ＶＱのみを検討する。各々が唯一の
インデックスを有する元から成る集合の元を、そのイン
デックスに写像させる関数をηで表す０例えば、Ａ−（
ａｔ＋ａ２．・・・、ａｔ、・・・、ａｔ、ｌならば、
η（ａ　１．　Ａ　）　＝　ｌとする。これにより、標
本採取時ｉの量子化動作は、次式のように要約される。

１！／；＝（１（Ｘ；、５ｔ）ＴＩ（［ｍｉｎ　　ｄ（
ｘ、ｃ）］、Ｃｔ、ＬεｃＣＩｌ ただし、ｍ１ｎ−’は、　［それに続く量を最小とする
変数」を意味する関数を示す、角括弧の中の項は、情報
源ベクトルからの最小歪みの符号語を表し、再生ベクト
ルと呼ばれる。

量子化器によってチャネル記号が生成された後、符号化
器は次の情報源ベクトルの符号化に備え、状態を更新す
る必要がある。この更新は、次状態関数が有限個の過去
の再生ベクトルを次の状態Ｓし１に写像することによっ
て行われる。再生ベクトルは、量子化の過程で暗黙のう
ちに決定されるが、それだけでは再生ベクトルを利用す
ることができないことは留意を要する。この再生ベクト
ルを次状態関数に利用できるようにするのが逆量子化器
１３である。逆量子化器は、テーブル探索関数であるが
、この場合、探索テーブルは状態コードブックである。

標本採取時をｉ、状態をＳ、とすると、逆量子化器は、
チャネル記号ｙ、を、Ｃ６，に属しｙｌをインデックス
とする符号語に写像する。換言すれば、時刻ｉにおける
再生ベクトルが交、で表きれるならば、え、ｅＣ，−、
および’１１＝η（ヌユ、ｃ、、＞とじて、運＝Ｐ　（
ｙ＋、Ｓｔ）となる、逆量子化器によって再生ベクトル
が使用可能となったので、次状態関数は、Ｓｔ＋ｔ＝ｆ
（又１．父、−４，・・・）という関係で表される。初
期状態をｓ□とすれば、量子化演算子および次状態関数
は、前述のように繰り返し作用して、連続する情報源ベ
クトルｘ□、ｘ１．ｘ２、・・・・から次々とチャネル
記号ｙｏ＋　ｙ１＋　３’２．・・・・を生成する。こ
のチャネル記号・シーケンスは、伝送あるいはメモリを
とおして、復号器によって受信され１，２　Ｏｒ　９　
ｉｎ　２２＋・・・・で表される再生ベクトル・シーケ
ンスに逆変換される。

有限状態ベクトル量子化器の復号器は、状態空間、状態
コードブック集合、逆量子化演算子、および次状態関数
から成る四要素構成、即ち、（Ｓ。

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

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

ｙｔ＝Ｑ　（ｘｔ、ｓ＋） 擢＝ｐ（３’　ｔ＋　Ｓ　ｔ　） ｓ　ｓ＋、＝　ｆ　（宋１．’Ｑｔ−１，・”・、９ｔ
−、Ｂ４）初期状態をＳとした場合、有限状態ベクトル
量子化器の復号器の動作は、次の演算を順次繰り返して
行われる。

９１＝　Ｐ　（３／　ｓ、　ｓ　ｔ　）Ｓ＋＋ｔ＝ｆ（
宮１．宋１−１．°”’、入１−Ｊ＋１）くサイド・マ
゛ツチ・ベクトル量子化〉本発明によるサイド・マツチ
・ベクトル量子化器は、完全検索ＶＱの部類に属する。

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

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

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

前述のように、サイド・マツチ・ベクトル量子化器は、
状態空間に各状態に対する状態コードブックを備えてい
なければならない、スーパー・コードブックをＣとして
、状態コードブックを説明する。状態ｓ＝（且、ヱ）が
与えられると、それに対応する状態コードブックは、各
辺に沿って、即ち第１列および第１行に沿ってＵおよび
■に最も良く一致する元からなる、スーパー・コードブ
ックの部分集合であると定義される。正確を期するため
に、サイド・マツチ歪ｅを次のように定義する。

先ず、　［Ｘｌ、ｃおよび［Ｘｌ、’が、ブロックＸの
１番目の列ベクトルおよび１番目の行ベクトルをそれぞ
れ示すものとする。つまり、　［Ｘｌ、Ｃ（Ｘ＋ｔ＋Ｘ
２ｔ＋””＋Ｘｍｔ）　”および［Ｋコ、’＝（ｘＩｔ
、ＸＩ２．・・・・、ｘｔｎ）とする、ここでＸｌはＸ
の第５行、第１列にある要素を示し、肩文字Ｔは転置行
列（ｔｒａｎｓｐｏｓｅ　）であることを示す、状Ｗ５
ｓ　＝（ｕ、　　ｖ）およびｍｘｎのブロック五が与え
られると、サイド・マツチ歪は、歪温度ｄおよび加重定
数ａおよびｂに対して、ｅ　（ｓ、ｘ）＝ａｄ　（ｕ。

［ｘｌ　、ｃ）＋ｂｄ　（ｖ、［ｘコ、ｒ）と定義され
る。

例えば、歪温度を平均自乗誤差とし、更にａ＝ｂ＝１／
２とすることができる。この場合、状態５＝（ｕ、ｖ）
に対する状態コードブックＣ，は、Ｃ１＝（且げ、立２
１．・・・・＋ＣＮ”）と定義される。ただし、ここで
Ｃ，の元が次の条件（Ａ）、（Ｂ）および（Ｃ）を満足
するものとする。即ち、 （Ａ）　１＝１．２．・・・、Ｎならば、且、′６Ｃ（
Ｂ）１≦１．≦１２≦Ｎならば、 常にｅ　（ｓ、ｃｌ”　）≦ｅ　（ｓ、ｃｌ’　）（Ｃ
）　１＝１．２．・・・、Ｎ、かつ全ての立が立ｅｃ−
ｃｓならば、ｅ　（ｓ、ｃ１＠）≦ｅ　（ｓ、ｃ）であ
るとする。

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

場合によっては、サイド・マツチ・ベクトル量子化器の
量子化演算子および逆量子化演算子は、有限状態ベクト
ル量子化演算子および逆量子化演算子の一般的な定義と
変わらない、前節の定義のように、歪温度ｄを有する完
全検索型の量子化器の動作は、 ｑ（王、Ｓ）＝η（［ｍ石川ｄ（Δ、Ｃ）］、ＣＩ）。

ｃ＠ｃ。

であり、また、その逆量子化器の動作は、立εＣ１かつ
η（立、Ｃ５）＝ｙ のとき、 ｐ（ｙ、ｓ）＝旦 となる。

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

Ｓｌ。、＝で（又１＋２Ｌ−Ｊ＋１） ここでＪは画像におけるブロック列の個数（即ち、画像
の幅に丁度納まるブロック数）である、具体的には、次
状態関数により、西側の再生ブロック↑１が列状態ベク
トル旦、や、に、北側の再生ブロック９１−Ｊや１が行
状態ベクトル量、。、に、写像される。

列状窓空間Ｕおよび行状態空間■が与えられると、最小
歪の原則によって列状態ベクトルおよび行状態ベクトル
が生成される。即ち、 ５ｔｙ１＝（且１＋１．ヱ１＋１） ＝ｆ＜２．、ヌｌ−Ｊ＋ｊ） 写像ｆの変域および値域が、共に有限で、かつそれらの
濃度が相対的に小さいので、写像では探索テーブルによ
って実現される。

次に、サイド・マツチ・ベクトル量子化器の設計手順の
他、符号化および復号の手順も説明する。

実際に画像を符号化する状況では、状態が正しく定義で
きないために、サイド・マツチ・ベクトル量子化器を適
用できない画素ブロックも幾つかある。

それらは、画像の最上段、左辺にあるブロックである。

そのようなブロックに独断的に状態を割り当てると、そ
れらのブロックのみならず、後続のブロックに対しても
符号化の歪が増大するので、他のブロックとは区別して
扱う必要がある。その結果、符号のビット率が、若干（
一般に１％にも満たない程度）増加する。この増加分を
無視すれば、サイド・マツチ・ベクトル量子化器のビッ
ト率は、画素当たりｌｏｇ２Ｎ／（ｍｎンビットである
。

例えば、ｍ＝ｎ＝４　（第７図）かつＮ＝２５６の場合
、ビット率は、画素当たり１／２ビツトとなる。

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

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

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

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

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

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

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

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

符号化すべきブロック毎に、１６画素がある。

典型的なシステムでは、各画素に対して２５６階調の明
度がある。従って、各ブロックについて（２５６）１６
、即ち、４００億以上のベクトルが有り得る。

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

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

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

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

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

１０６以上存在し得る状態コードブックから、１２８の
行の部分および１２８の列の部分の対の組みに合わされ
た、各々の２５６の要素に対し最良総合得点く最小総合
歪）を持つとして選択することにより、縮小集合（＝　
（１２８）　２≠１６．０００　’）が形成される。

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

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

ＯＭＶＱの構成は、サイド・マツチ・ベクトル量子化器
のそれと非常に類似しているので、前節で導入した表記
を借用してオーバラップ・マツチ・ベクトル量子化器の
構成要素を説明する。オーバラップ・マツチ・ベクトル
量子化器のブロック線図を第１および３図に示す、ＯＭ
ＶＱに対し、大きさｍｘｎの情報源ブロックを考えるこ
とにする。状態空間の各状態を、１対のブロック、即ち
列状態ブロックと呼ぶｍｘｎ（、のブロックおよび行状
態ブロックと呼ぶｍ（、χｎのブロックによって表され
る。

つまり、ｍｘｎ□の列状態ブロックを且、ｍ□ｘｎの行
状態ブロックを凹としなとき、状態は（旦、工）の形式
となる０列および行の状態ブロックが、それぞれ列状態
空間および行状態空間と呼ばれる、アルファベット且お
よびヱを有するものとする。

ＳＭＶＱの場合のように、ＯＭＶＱの状態空間Ｓは、デ
カルト積ｕＸｖである。これらの列および行の状態ブロ
ックの意義は、それらが符号化すべき情報源ブロックと
重複する再生画素を表すことである。

ＯＭＶＱの状態コードブックは、次のように定義される
。所与のスーパー・コードブックＣおよび状態５＝（ｕ
、ｖ）に対し、対応する状態コードブックは、重複領域
において且およびｙに最も一致する元からなる、Ｃの部
分集合であると定義される。ＯＭＶＱの状態コードブッ
クを説明するために、照合による歪ｅを定義し、これを
オーバラップ・マツチ歪と命名する。先に導入した表記
の拡張として、　［Ｍ］　ｃｌｌ　＋、　＋２　＋　”
’＋　ＩＪおよび［Ｘ］’。

、１１．・・・＋ｌｊが、列１１から１ｊまでを集めて
形成したｍχｊ個のブロック、行ｌ、からｌｊまでを集
めて形成したＪｘｎ個のブロックを、それぞれ表すもの
とする。所与の状態ｓ＝　（ｕ、ヱ）およびｍｘｎブロ
ック五に対し、オーバラップ・マツチ歪は、次のように
定義される。

ｅ　（Ｓ、Ｋ）　＝　ａｄ（ｕ、　［Ｘ］ＣＩ＋　＋　
１１　、”　’　、＋、、）＋　ｂｄ（ｙ、　［ｘ］ｒ
＋、　、　１．　、　・・・、　＋、。）ただし、ｄは
歪温度、ａおよびｂは定数である。

ここで、ＯＭＶＱの状態コードブックの定義は、サイド
・マツチ歪をオーバラップ・マツチ歪で置き換えればＳ
ＭＶＱの場合の定義と同じである。つまり、スーパー・
コードブックＣおよび状Ｑｓ＝（ｕ、ｖ）が与えられた
場合、その状態に対する状態コードブックＣ，は、 Ｃ１＝（立１１．立″２．・・・、立“Ｎ）と表される
とき、Ｃ８の元が前節の（Ａ）、（Ｂ）および（Ｃ）を
満足するものとして定義される。この場合も、各状態コ
ードブックの元は、順番に配列されていることに注目し
たい。

ＯＭＶＱの状態コードブックが確立したので、ＯＭＶＱ
の量子化器および逆量子化器も、−ｉのＦＳＶＱのもの
と変わらない。

ＯＭＶＱの次状態関数を説明するために、部分的に重複
したＸｌまでの情報源ブロックが、・・・・ｉｔ　−２
＋　ｇ　１−１．　ｇ　＋に符号化済みであるとする。

すると、状Ｒ８１＋１は、次状態関数ｆによって、Ｓ　
１＋１＝　ｆ　（又４ｌ−Ｊｅｔ）として生成される。

ただし、Ｊは、画像において部分的に重複するブロック
の列の数（即ち、画像の幅に丁度納まり、部分的に重複
するプロ・ンクの数）である、五が画像の画素列の数を
表すとすれば、Ｊを次式により算出することができる。

Ｊ＝（五−ｎ）／　（ｎ−ｎｏ）　＋１具体的には、次
状態関数は、西側の再生ブロック又１を、列状態ブロッ
ク基１＋１に写像し、北側の再生ブロックｇｔ−Ｊ＋１
を、行状態ブロックエ１や、に写像する。所与の列状態
空間用および行状態空間ヱに対し、列状態ブロックおよ
び行状態ブロックが、最小歪の原則によって生成される
。つまり、Ｓ１＋１：（且１＋トヱ１＋１） ＝ｆ（又１．又１−Ｊや、） ”　（［ｍ１ｎ−’　ｄ（！！、　［ｇ；１５＋ｔ、　
−１−、ｎ　）］。

ＵεＵ 写像ｆの変域および値域が、共に有限で、かつ濃度が相
対的に小さいので、写像では探索テーブルによって実現
される。状態の生成に関与する画素を、第８図に斜線を
施した領域として示す。

ＯＭＶＱの定義は、ＳＭＶＱの定義に類似している。特
に、ｍ□＝ｎ□＝１の場合、単純な前処理装置（ｐｒｅ
ｐｒｏｃｅｓｓｏｒ　）によりＯＭＶＱをＳＭＶＱと看
做すことができる。具体的には、前処理装置を用いて画
素の行および列を複製することにより、ＯＭＶＱであれ
ば重複領域にあるべき「拡張画像」を構成すれば、画像
に適用されるＯＭＶＱの処理は、前記の拡張画像に適用
されるＳＭＶＱの処理と同一である。しかしながら、再
構成された画像も拡張されていることに注意を要する。

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

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

ＯＭＶＱの設計手順も、ＳＭＶＱの場合に似ていて、第
４図によって表すことができる。

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

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

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

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

画像どうしに高い相関関係があり、各状態コードブック
において照合による歪によって順序付けが為されている
ことから、チャネル記号の分布は単調な減少傾向を示す
と、推測することができる。

ａおよびｂを定数とした場合、チャネル記号の分布は事
実（ｂμｍ″：μ＝　１．２．・・・、Ｎｌに近似する
ことが、実験から判っている。以下において、分布が急
速に減少するように、小さいレベルしか持たない一種の
無雑音符号を提案し、それらが最適に近いことを示す。

ここで提案する無雑音符号は、基本的には周知のハフマ
ン符号（Ｈｕｆｆｍａｎ　ｃｏｄｅ）であり、これは減
衰の速い分布に対する階段近似のために設計されたもの
である。しかし、記号の個数が２の累乗でない場合は、
提案する無雑音符号と近似のためのハフマン符号とは若
干異なることがある。急速に減少する確率分布Ｐ、即ち
（Ｐｌ、Ｐ２．・・・、ＰＮ）に対し、次の条件を満足
する階段近似Ｐを定義する。即ち、ｊ＝ｏ、１，２．・
・・、Ｌｏｇ２Ｎ　（Ｌｏｇ２Ｎは整数）なるｊに対し
、 （Ａ）　　２Ｊ−１＜μ、ν≦２ｊである限り、Ｐ□＝
Ｐ（Ｂ）　　Σ　ｐ、＝　　Σ　Ｐ、。

２ト１〈μ≦２’　　　　　　　ｔ’＜μｓ１前記の定
義の（Ｂ）の部分よって、Ｐもまた確率分布である。Ｎ
が大きい場合、Ｐに対してハフマン符号を設計すること
は、一般に容易なことではない。

しかし、この分布Ｐは特殊な形式なので、ハフマン符号
の設計は、次のように大幅に単純化することができる。

初めに、確率の集合 を設計する０次に、各ｊに対し総計区間内の記号を見分
けるために、接尾語（ｓｕｆｆｉχ）と呼ばれる単純な
固定長のバイナリ−符号を、前記のハフマン接頭符号に
連結する。各ｊに対する総計区間における記号の個数は
、’；ｆ口である。ただし、口］は、ｊより小さくない
最小の整数である。従って、前記の接尾語の長さは、ｍ
ａｘ（ｊ−１，Ｏｆである。

ここで言う「接頭符号」は、二重の意味を持つ。

その一つは、接頭符号における何れのバイナリ−符号語
も、その接頭符号内の他の何れのバイナリ−符号語にお
いても接頭語ではない、と言うことである。もう一つは
、接頭符号はその接尾語に対する接頭語である、と言う
ことである。前者の意味では、結果として得られる無雑
音符号も、また接頭符号である。更に、Ｎが２の累乗で
ある場合、この無雑音符号が、分布Ｐに対して最適であ
ることを示すのは困難なことではない。

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

前記のクラスター化処理が済むと、ベクトルを量子化し
た符号、即ち１０２４個の符合のスーパー・コードブッ
クを構築できるようになる０次の段階で、前記のスーパ
ー・コードブックから状態コードブックを構成するため
に前記本質特性を抽出し、スーパー・コードブックから
状態コードブックに対する種々の構成要素を選択できる
ようにする。この処理の最初の段階は、ステップ６３で
示され、ここでは、スーパー・コードブックにおけるブ
ロックを表す各符号語に対して最後の画素列を選択する
。最後の画素列からなるこれらの集合は、ロイドのクラ
スター化アルゴリズムによってクラスター化される（ス
テップ６４）、これと平行して行われる処理において、
最後の画素行が選択される（平行するステップ６５およ
び６６）。

行ベクトルに対するクラスター化ステップ６６において
も、スーパー・コードブックから照合歪が最小のコード
ブックがＮ個選択される。この結果、これら２つの平行
処理から、状態コードブックを得る。各状態コードブッ
クの大きさはＮ（例えば、Ｎ＝２５６　’）である、具
体的には、クラスター化された符号語における情報は、
次のように構成される。即ち、且が列状態空間にあり、
ヱが行交間にあるような１対の値且およびヱの各々に対
して、スーパー・コードブックから照合歪が最小の符号
語をそれぞれＮ個選択する。ステップ６７で必要となる
最小照合歪の符号語の選択において、例えば１６．００
０の状態コードブックを作成するために、計算を中心と
する照合歪の算出および検索を行う必要がある。この計
算は、第１図の送信部１０の実時間動作に先だって、集
中的に行う方が有利である。

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

これらの方式の両方ともＡｒａｖｉｎｄおよびＧｅｒｓ
ｈｏの方式と対象的なのは、エツジは現在のブロックを
通ってブロック自体のエツジに抜は出る可能性があるも
のであるが、後者がそのようなエツジにまたがる画素の
間の連続性の度合いを強調していることである。それに
対して、本発明では、ＡｒａｖｉｎｄおよびＧｅｒｓｈ
ｏのように画素の値を直接的な情報に変換することによ
り生じるほどの希薄化を伴うことなく、空間的隣接性を
利用している。

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

【図面の簡単な説明】

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

Claims (9)

【特許請求の範囲】
1. （１）順次走査された２次元情報をブロックに編成する
   編成手段、 １個の量子化済みの値を選択するために、有り得る量子
   化済みの値に対し適性検索を行う手段を備え、前記ブロ
   ックを量子化する量子化手段、および 複数の切り替え可能な状態コードブックを備え、前記量
   子化済みの値を与える手段 からなり、この量子化済みの値を与える手段が、更に 符号化すべき画素のブロックと、直前のブロックまたは
   １行前のブロックまたは前記両ブロックとに関する空間
   的隣接性の原理に基づいて現在使用するために、前記複
   数の切り替え可能な状態コードブックの１つを選択する
   選択手段を備え、この選択手段が、更に 前記前のブロックのうち最低１つのブロックにおいて隣
   接または重複する画素の強度を、前記符号化すべきブロ
   ックにおいて隣接または重複する画素の強度と比較する
   比較手段、および前記比較手段によって行われる比較の
   形式に適合したコードブックの間で、前記比較手段から
   の結果に応じて切り替えを行う切り替え手段を備え、更
   に 前記複数の切り替え可能な状態コードブックは、それら
   が前記比較手段によって行われる比較と同一の比較を受
   けたベクトルを生成する２次元情報の仕込用標本から取
   り出されるように適用されている ことを特徴とする ２次元情報の符号化システム。
2. （２）順次走査された情報をブロックに編成する前記編
   成手段が、前記情報を隣接するブロックにおいて重複す
   る画素の行および列に編成する手段からなり、更に 前記選択手段が、それにより選択されたコードブックの
   何れの項目（符号語）も前記重複する画素の間の値にお
   ける不連続性を最小にする、という原則に基づく ことを特徴とする 請求項１記載の２次元情報の符号化システム。
3. （３）順次走査された情報をブロックに編成する前記編
   成手段が、前記情報を隣接するエッジを有するブロック
   に編成する手段からなり、更に前記選択手段が、それに
   より選択されたコードブックの何れの項目（符号語）も
   前記隣接するブロックに属する最も近いそれぞれの行の
   画素の間の値における不連続性を最小にする、という原
   則に基づく ことを特徴とする 請求項１記載の２次元情報の符号化システム。
4. （４）前記量子化済みの値を与える前記手段が、２次元
   情報の前記仕込用標本から得た共通のスーパー・コード
   ブックから取り出したコードブックからなり、しかも、
   前記スーパー・コードブックからのこのコードブックの
   取り出しは、特にサイド・マッチングおよびオーバラッ
   プ・マッチングの原理を含む符号語の限定的部分集合へ
   のマッチングの原理によるものである ことを特徴とする 請求項１記載の２次元情報の符号化システム。
5. （５）前記選択手段が、 伝送すべき符合語インデックスを符号語に変換する変換
   手段、 前記の変換結果の符号語を、２次元の視覚的画像におい
   て次に続くブロックの異なる２辺に関する空間的隣接性
   に関連した２つの異なった期間だけ遅らせ、それぞれ別
   個の経路に出力する遅延手段、および 符号化すべき前記ブロックの前記異なる２辺に関する値
   における不連続性を最小にする項目（符号語）を有する
   として選択された前記状態コードブックに、前記の両経
   路の前記出力に応じて、切り替える手段からなる ことを特徴とする 請求項４記載の２次元情報の符号化システム。
6. （６）順次走査された視覚的情報をブロックに編成する
   前記編成手段が、前記情報を隣接するブロックにおいて
   重複する画素の行および列に編成する手段からなり、更
   に 前記切り替え手段が、前記の重複する画素の間の値にお
   ける不連続性を最小にする項目を有する状態コードブッ
   クに切り替える手段からなる ことを特徴とする 請求項５記載の２次元情報の符号化システム。
7. （７）順次走査された視覚的情報をブロックに編成する
   前記編成手段が、前記情報を隣接する辺を有するブロッ
   クに編成する手段からなり、更に 前記切り替え手段が、前記の隣接するブロックに属する
   最も近いそれぞれの行の画素の間の値における不連続性
   を最小にする項目を有する状態コードブックに切り替え
   る手段からなることを特徴とする 請求項５記載の２次元情報の符号化システム。
8. （８）前記符号化を可変長無雑音符号化とするためのバ
   イナリー・コードブックを備え、前記量子化手段に続い
   て、量子化済みの前記値のデータを更に圧縮する圧縮手
   段を備える ことを特徴とする 請求項５記載の２次元情報の符号化システム。
9. （９）前記量子化手段から物理的に分かれていて、量子
   化済みの前記値を逆量子化し、その結果の値を再編成し
   て前記の２次元情報を復元する逆量子化手段を備え、こ
   の逆量子化手段が、更に量子化済みの値を与える前記手
   段に本質的に類似していて、逆量子化する値の切り替え
   可能な状態コードブックを与える手段、および 量子化済みの値を与える前記手段における前記選択され
   たコードブックと同一のコードブックを選択する手段 を備え、更に 前記逆量子化手段および再編成手段が、前記第１の２次
   元情報に対する実質的類似性を有する２次元情報を形成
   するように適合されていることを特徴とする 請求項５記載の２次元情報の符号化システム。