JPH01286677A - 画像データ圧縮方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［概要］ 画像データを圧縮して伝送し、伝送されたデータを受信
して再生する画像データ圧縮方式に関し、画像データを
効率よくしかも高画質で伝送することを目的とし、 多値中間調画像を所定の複数画素からなるブロックに分
割し、分割した各ブロック毎の画素データから入力ベク
トルを作成してベクトル量子化し１、出力ベクトルのイ
ンデックスを符号化する場合に、該インデックスを上位
ビットと下位ビットに分割し、前記上位ビットをその周
囲のブロックのインデックスより予測順位符号化するよ
うに構成する。

［産業上の利用分野］ 本発明は画像データを圧縮して伝送し、伝送されたデー
タを受信して再生する画像データ圧縮方式に関する。

画像データを表わすために必要な情報量は、数値データ
に比べて桁違いに増大する。この情報量の増大は画像デ
ータの中でも特に多値中間調画像やカラー画像で著しい
。このような画像データを蓄積し、或いは高速、高品質
で伝送するためには、画像毎の階調情報を高能率に符号
化（つまり圧縮）する必要がある。

［従来の技術］ 画像データの圧縮符号化方式としては、従来よりブロッ
ク符号化方式とベクトル量子化方式がよく用いられてい
る。これらの方式は、更に改良方式が研究されており、
以下に示すようなベクトル吊子化符号化方式（例えばテ
レビジョン学会誌。

Ｖｏ１３８．Ｎｏ、５．１９８４年　ｒ画ｍ信Ｍのベク
トル吊子化」）が提案されている。ここで、ベクトル量
子化方式とは、画像信号を複数画素毎にまとめたものを
、多次元のベクトルと見て、多次元空間において入力ベ
クトルを最短距離にある出力ベクトル（有限個の代表点
の１つ）に写像することで、多次元の量子化を行う方法
である。

多値中間調画像のベクトル量子化法としては、平均値分
離正規化ベクトル陽子化符号化方式（Ｍｅａｎ　　５ｅ
ｐａｒａｔｅｄ　　ＶｅｃｔｏｒＱｕａｎｔ　ｉ　ｚｅ
ｒ）がよく知られている。

この方式は、画像をＮｘＮ　（−ｋ）画素からなるブロ
ックに分割し、ブロック毎の画素５ｉ（ｉ＝１．２．・
・・ｋ）の入力ベクトルＳ−［Ｓｔ　。

Ｓ２　＋・・・８３　］から平均値μを差し引いて分離
し、偏差σで正規化した平均値分離正規化入力ベクトル
Ｘ　”　［Ｘ　１　＋　×２　＋・・・Ｘド１を構成す
る。Ｘはに次元信号空間上の１点を指すベクトルとなる
。

そこで、ＲをＮ個の部分空間に分割し、部分空間Ｒ１を
代表点のベクトルＹｉ　　＝　［’１７１＊　Ｖ；ｚ　
、　　　　　’・・・Ｖｉｋ　］で表わすようにする。

そして、Ｙｌ　　の集合をＹ−（Ｙｔ　、Ｙ２・・・Ｙ
Ｎ）とし、ｙｌ　　のインデックスの集合を１−（１，
２，・・・Ｎ）とすると、ベクトル量子化ＶＱは次式で
表わされる。

Ｓ　＝　［Ｓｔ　ｅ　　Ｓ　２　、・・・ｓ、］　　　
　　（１）μ＝（１／ｋ）２．ｓ、　　　　　　（２）
ｘ　＃−（ｓ　Ｈ−μ）、／σ　　　　　　（４）Ｘ−
［Ｘｔ　　、Ｘ、、−、Ｘ）、］　　　　　（５）上記
Ｘのベクトル量子化ＶＱ（Ｘ）−Ｙｉｄ　（Ｘ、Ｙ’＋
　　）　＜ｄ　（Ｘ、Ｙ、＞　　　＜　７）但しｉ　ａ
−Ｐｊ ベクトル吊子化による符号化Ｃ１復号化りは、次の写像
の操作を表わす。

Ｃ：Ｘ−＊ｉ、　　　　Ｄ：ｉ−＋Ｙ１従って、ＶＱ−
Ｄ　−Ｃ 前記ｄ（Ｘ、Ｙｉ）は歪み測度で、入出力間の距離を表
わし、 ２乗歪測度　ｄ（Ｘ、Ｙｉ）＝ ！（Ｘ；　　−ｙ；Ｈｌ　　　（８） 絶対値歪ミｌｌｌ１度ｄ（Ｘ、Ｙｉ）−等で定義される
。平均値分離正規化ベクトル量子化では、符号化情報は
ブロック毎の平均値μ、幅偏差及び出力ベクトルのイン
デックスｉとなる。

第６図は平均値分離ベクトル量子化器の従来構成例を示
す図である・。図中（ａ）は符号器を、（ｂ）は復号器
をそれぞれ示す。先ず、（ａ）に示す符号器について説
明する。ここでは、画像信号を４×４画素のブロックと
し、平均値と偏差で正規化して入力ベクトルを作り、絶
対値歪温度を用いてベクトル量子化する。４×４画素の
画像信号を８！　　−［Ｓ　１　＋　８２　＋・・・Ｓ
、６］とすると、正規化した入力ベクトルＸ−［Ｘｔ　
、Ｘ２　、・・・ｘ＋ｂＥは分離・正規化回路１により
次のようにして作成される。

Ｘ　１　　＝　（８ｉｕｐ　　）　／　（ｊｐ　　　　
　　（１０）μｌ′″（１／１６）Ｆ、、Ｓｉ　　　　
　（１１）上記変換により、入力ベクトルＸは平均値Ｏ
１要素の絶対値和が１に正規化される。そして、正規化
された入力ベクトルＸはレジスタ２に一時的に保持され
る。

一方、出力ベクトルコードテーブル３から順次出力ベク
トルＹｉ　　を読出して、レジスタ４に−時的に保持す
る。そして、図に示す符号化器は入力ベクトルＸと出力
ベクトルＹ１　　との差分（歪）ｄ（Ｘ、Ｙｉ）を減算
器５で計算し、最少歪となる出力ベクトルのインデック
スｉを正規化定数μｌ。

σ１　と共に符号化する。つまり減算器５で減算した結
果を絶対値回路６に入力して絶対値化する。

そして、これら絶対値回路６の出力を累算回路７に入力
する。

累算回路７は（９）式で示す絶対値型測度ｄを累口する
。該累算回路７の出力は、最少歪検出回路８に入り、今
まで求めている出力ベクトルの歪より小さいかどうか比
較され、小さければ、コードテーブル・インデックスカ
ウンタ１０よりインデックスがインデックススラッチ９
に入ってラッチされる。次にコードデープルインデック
スカウンタ１０を１つカウントアツプし、次に歪を検査
するインデックスＩを出力する。このインデックス■は
出力ベクトルコードテーブル３に入って対応する次の出
力ベクトルＹｒ　　を出力する。コードテーブルインデ
ックスカウンタ１０が逐次カウントアツプして、全イン
デックスを走査すると、インデックスラッチ９には最小
歪のインデックスが求まることになる。この結果、イン
デックスｉ。

正規化定数μノ及び偏差σノが出力される。

次に（ｂ）に示す復号器の動作について説明する。（ａ
）に示す符号器から伝送されてきた圧縮データの内、イ
ンデックスｉはインデックスラッチ１１にラッチされる
。ラッチされたインブックスミデータは、出力ベクトル
コードテーブル１２に入り、該出力ベクトルコードテー
ブル１２はインデックスｉをアドレスとして、対応する
番地に格納されている出力ベクトルＹｉ　　を読み出す
。読み出された出力ベクトルＹｉ　　は、再生回路１４
に入る。該再生回路１４には、入力データの内の正規化
定数μノ及び偏差σノも入力されており、出力ベクトル
Ｙｉ　　にμノ及びσノとを演算させて復元画像信号と
している。

第６図に示すベクトル量子化器は、入力ベクトルに対し
て出力ベクトルを１つずつ比較して最少歪となる出力ベ
クト、ルを選択するもので、全探索型と呼ばれている。

この全探索型ベクトル量子化器では、入力ベクトルと最
少歪となる出力ベクトルを検出プる部分の演Ｒｆｆｉが
大きくなるため、処理に時間がかかる。そこで、高速の
ベクトル量子化を行う方法として出力ベクトルのセット
に一定の構造を持たせる木探索ベクトル量子化がある。

本探索恒子化の内、多く用いられている２進木探索ベク
トル量子化について説明する。

２進木探索ベクトル量子化では、正規化した入力ベクト
ルのトレーニング系列を段階的に分割し、第７図に示す
ような本構造をもつ出力ベクトルのセットを作成する。

同図で、木の根はに次元空間Ｒに対応し、各節点はＲを
順次２分割した空間に対応する。各節点に仮の出力ベク
トルが置かれ、入力ベクトルはこれらの出力ベクトルと
比較され、ｌ　ｏｇ２　ｋ回の歪演算で最終の出力ベク
トルを選ぶことができる。

第８図は２進本探索ベクトル量子化の符号器の構成例を
示すブロック図である。図に示す例は、各節点の処理を
パイプライン化して高速化するもので、第ｎ＋１段につ
いて示している。図中、ｂ（ｎ）は２進ｎ桁のインデッ
クスであり、第ｎ段までの２進水の経路を承り。入力ベ
クトルＸは、先ず入力ベクトルレジスタ２１に入り一時
的に保持される。一方、前段からの２進ｎ桁のインデッ
クスｂ　（ｎ）は、出力ベクトルコードテーブル２２に
入る。そして、図に示すｎ＋１段目で入力ベクトルＸと
、仮の出力ベクトル譬ｂｃｎ）ｏと１Ｆｂ（ｎ）＋との
歪計算を続く歪計算回路２３．２４で行い、これら計算
結果を比較器２５で行って、ｎ＋１桁目におけるＯ／１
を決定し、インデックスレジスタ２６に入力する。そし
て、該インデックスレジスタ２６からインデックスｂ（
ｎ）Ｏ／１を出力する。

第９図は従来技術のベクトル量子化の可変長符号化回路
の構成例を示す図である。この図は従来技術の平均値分
離正規化ベクトル量子化・可変長符号化によるデータ圧
縮器の構成例を示している。

図において、１は画像信号の入力端子、３０は第６図に
示したものと同様の正規化回路であり、プロック毎の画
像信号から平均値μ１．及び標準偏差σメ　を分離して
出力すると共に、平均値０．標準偏差１に正規化した入
力ベクトルＸを出力する。

３１は２連木探索ベクトル量子化符号器であり、第８図
の２進水探索ベクトル量子化器をｌ　ｏｇ２　ｋ段分、
パイプラインに接続したものである。２連木探索ベクト
ル量子化符号か器３１からはｌ　００２　ｋピットのイ
ンデックスが出力される。正規化回路３０から出力され
る平均値μｌ及び標準偏差σメ　（正規化係数）は、Ｄ
ＰＣＭ符号化によりデータ圧縮する。そこで、μｌ及び
σｌは、それぞれ予測陽子化器３３．３４に入力され、
予測値との差分が量子化され出力される。

例えば、平均値μｌについて考えると、予測値へ μｌ　（Ｘ）は、第１０図に示すような予測器を用いる
ものとすると、隣接ブロックＡ、Ｂ、Ｃの平均値μ、（
Ａ＞、μｔ　　（Ｂ）、μｌ　（Ｃ）を参照することに
より、次式のように求めることができる。

へ μｔ　（Ｘ）　　−μｌ　（Ａ＞　　＋μ）　（Ｂ）−
μｅ　　（Ｃ）　　　　　　　（１３）これから予測誤
差ε力　（Ｘ）は、 ε力　（Ｘ）　　−μｌ　（Ｘ）　　−μｌ　（Ｘ）　
　（１４）のように表される。

ここで、画像信号が２５６階調であり、Ｏ〜２５５で表
されるものとすると、予測誤差εμは、−２５５から２
５５までの値をとり得る。そこで、５１２レベルの予測
誤差を６３レベル程度に量子化器、量子化した値εＡを
出力する。標準偏差σノについても同様で、予測量子化
器３３で予測吊子化し、εσを出力する。

次に、インデックスｉは吊子化後の標準偏差を用い、適
応量子化器３２で実際のインデックス長を適応的に切り
つめたｉ　を出力する。これは、偏差が小さい場合、入
力ブロックの階調変化が穏やかと考えられるため、２進
木の上位の出力ベクトルでも十分表現できるからである
。そして、最斧　　４ｆ　　　　　片 襖にこれらεＡ、εσ及び１　は可変長符号化器３５で
可変長符号化され、圧縮符号として出力される。

［発明が解決しようとする課題］ 上述した従来技術においては、正規化係数μｌ。

σＬは予測符号化するため、隣接ブロックとの相関によ
る冗長性を低くできる。しかしながら、インデックスｉ
については、隣接ブロックとの相関が残り、このため符
号化効率を十分に上げることができないという不具合が
あった。

本発明はこのような課題に鑑みてなされたものであって
、インデックスを含めて画像データを効率よくしかも高
画質で伝送することができる画像データ圧縮方式を提供
することを目的としている。

［課題を解決するための手段］ 第１図は本発明方式の原理を示ずフローチャートである
。本発明は、多値中間調画像を所定の複数画素からなる
プロ、ツクに分割しくステップ［１］）、分割した各ブ
ロック毎の画素データから入力ベクトルを作成してベク
トル量子化しくステップ［２］）出力ベクトルのインデ
ックスを符号化する場合に、該インデックスを上位ピッ
トと下位ビットに分割しくステップ［３］）、 前記上位ピットをその周囲のブロックのインデックスよ
り予測順位符号化する（ステップ［４］）ようにしたこ
とを特徴としている。

［作用１ 出力ベクトルのインデックスを符号化する場合に、該イ
ンデックスを上位ピットと下位ピットに分割し、前記上
位ピットをその周囲のブロックのインデックスより予測
順位符号化するようにした。

これにより、インデックスｉについても相関がとれるの
で、隣接要素との冗長性を低くでき、従って符号化効率
を上げることができる。

［実施例Ｊ 以下、図面を参照して本発明の実施例を詳細に説明する
。

本発明は、ベクトルｍ子化した出力ベクトルのインデッ
クスの内、上位ピットを隣接ブロックのインデックスよ
り予測順位符号化し、インデックスの隣接ブロック間の
相関を低減させるようにしたものである。

出力ベクトルのインデックス（以下、単にインデックス
と呼ぶ）の隣接ブロック閤の相関を低減させるには、正
規化係数の符号化と同時に、予測符号化を用いる方法が
考えられる。しかしながら、インデックスは多次元空間
を２進水分割した部分空間に付したＷｊ＠であるので、
距離が定義されていない。従って、２つのインデックス
の差分の大小は歪ｍ度の大小とは対応しないため、ＤＰ
ＣＭ符号化を適用しても冗長性の除去は期待できない。

本発明方式では、予測符号化を適用することで、周囲の
ブロックのインデックスからみた注目ブロックの出現の
しやすさの順番を符号化するように、冗長性を除去しよ
う、とするものである。しかるに、インデックスは通常
８〜１２ピツトに選ばれるため、予測順位符号化をその
まま用いると、２ブロツク参照でも予測状態数が非常に
大きくなり（例３メ嘗　　　　ｊｙ＋１ えば２〜２　）、そのままでは予測器を構成するのは不
可能である。しかしながら、インデックスは２進水構成
であり、上位ビット程予測が当たりやすいことから、本
発明ではインデックスの上位ピットのみ予測符号化する
ようにしたものである。

第２図は本発明に用いる符号器の一実施例を示す構成ブ
ロック図、第３図は本発明に用いる復号器の一実施例を
示ず構成ブロック図である。先ず、第３図に示す符号器
について説明する。同図に示す符号器が、第９図に示す
符号器と異なる点は、予測順位発生器４０及び可変長符
号器４１．４２が付加されていることである。正規化回
路３０より平均値分離正規化入力ベクトルＸを入力した
２進本探索ベクトル量子化器３１は、インデックスｉを
上位ピットｉ′と下位ピットｉ＝′とに分けて出力する
。上位ビ、ットｉ′は予測順位発生器４０に入力されて
、予測順位が出力される。

この予測順位発生器４０は、例えば第４図に示すように
その直前ブロックと真上ブロックのインデックスを参照
するようにすると、その構成は第５図に示すようなもの
となる。即ち、インデックス上位ピットを１ブロックラ
イン分蓄積できるシフトレジスタ４０ｂを持ち、注目イ
ンデックス４０ａを入力するたび毎に１ブロック分シフ
ト動作を行う。そして、シフトレジスタ４０ｂよりＡ。

Ｂ、Ｘのブロックに対応するインデックスを予測器４０
ｃに入力する。この予測器４０ｃはＲＯＭで構成されて
おり、インデックスの上位ピットを６ビツトとすると、
該予測器４０ｃの容量は２Ｊ％ｂ （−２）ｋＷｘ６ピツトとなる。予測５４０Ｃは、Ａ、
Ｂの位置にあるインデックスからみて、注目ブロックの
インデックスの出現しやすさの順序を出力する。

可変長符号器４１は、この予測順位を可変長符号化する
。また、可変長符号器４２は、インデックスの下位ピッ
ト１″を従来技術と同様にして偏差σｌの大きさにより
適応的に切りつめてから符号化する。σ！　、μｌにつ
いての符号化は、第９図と同じであるので、その説明は
省略する。そして、これら可変長符号器３５．４１．４
２の出力は、マルチプレクサ４３により順次切換えられ
て出力端子２から出力される。

次に第３図に示す復号器について説明する。符号器より
送られてくる順に、従来技術と同様にしτμ、及びσｌ
　を可変長復号化する。つまり、符号分配器５０から分
配された圧縮信号の内、εＧ及びε々は可変長復号器５
３．５４に入り、復号される。復号された信号εσ及び
εｌは、それぞれ続く予測逆変換回路５６．５７に入っ
て逆変換され、σｌ　、μｌに変換される。

その慢、インデックスの上位ビットｉ′を可変長復号器
５１で復号する。その後、信号された予測順位を予測順
位逆変換回路５５に入力し、前述した第４図のＡ、Ｂブ
ロックのインデックスを参照し、注目ブロックＸのイン
デックスの上位ビットｉ′を復元する。次に、求まって
いるＩＩ差σノにより符号分配器５０を可変長復号器５
２に切換え、インデックスの下位ビットｉ＝−を復号す
る。

そして、求まったインデックスの上位、下位ビットを合
わせて出力ベクトルコードテーブル５８をアドレスし、
対応する番地に格納されている出力ベクトルＹ１　　を
読出す。以陪は、従来技術と同様忙　　　　ゲ であり、μノ、σｌ　及びＹｌ　　を画像再生回路５９
に入力し、出力ベクトルの正規化を解き、平均値のオフ
セットを加えて端子４に画像信号として出力す、る。

［発明の効果］ 以上詳細に説明したように、本発明によれば出力ベクト
ルの隣接ブロック間の相関が低減されるので、符号化効
率を上げることができる画像データ圧縮方式を提供する
ことができる。

【図面の簡単な説明】

第１図は本発明方式の原理を示すフローチャート、 第２図は本発明に用いる符号器の一実施例を示す構成ブ
ロック図、 第３図は本発明に用いる復号器の一実施例を示す構成ブ
ロック図、 第４図は予測順位符号化の隣接インデックスの配置を示
す図、 第５図は予測順位符号化の予測器のブロック図、第６図
は平均値分離正規化ベクトル量子化器の従来構成例を示
す図、 第７図は２進水の部分空間分割を示す図、第８図は２連
木探索ベクトル量子化器号器の構成例を示すブロック図
、 第９図は従来技術のベクトル量子化の可変長符号化回路
の構成例を示す図、 第１０図は予測器の構成例を示す図である。 第２図、第３図において、 １．３は入力端子、 ２．４は出力端子、 ３０は正規化回路、 ３１は２進水探索ベクトル間子化器、 ３３．３４は予測邑子化器、 ３５は可変長符号器、 ４０は予測順位発生器、 ４１．４２は可変長符号器、 ４３はマルチプレクサ、 ５０は符号分配器、 ５１〜５４は可変長復号器、 ５５は予測順位逆変換器、 ５６．５７は予測逆変換回路、 ５８は出力ベクトルコードテーブル、 ５９は画像再生回路である。 特許出願人　　富　士　通　株　式　会　社代　　理　
　人　　　　　弁理士　　　井　　島　　藤　　治外１
名 、本発明方式の原理を示すフローチャート第１図

Claims (1)

1. 【特許請求の範囲】 多値中間調画像を所定の複数画素からなるブロックに分
   割し（ステップ［１］）、 分割した各ブロック毎の画素データから入力ベクトルを
   作成してベクトル量子化し（ステップ［２］）出力ベク
   トルのインデックスを符号化する場合に、該インデック
   スを上位ビットと下位ビットに分割し（ステップ［３］
   ）、 前記上位ビットをその周囲のブロックのインデックスよ
   り予測順位符号化する（ステップ［４］）ようにしたこ
   とを特徴とする画像データ圧縮方式。