JPS6337777A - 画像デ−タ圧縮方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔目　次〕 概要 産業上の利用分野 従来の技術　　　　　（第７．８．９図）発明が解決し
ようとする問題点 問題点を解決するための手段 作用 実施例 本発明の原理説明　　　（第１．２図）代表階調の初期
値作成　（第３．４図）代表階調の送出１選択及び収束
判定 （第５図） 代表階調の更新頁　　　　　（第６図）変形例 発明の効果 〔１既　　要〕 本発明は、多値中間調画像のデータ圧縮において、画像
を所定の複数画素からなるブロックに分割するとともに
、ブロック内の階調変化の大きさに応じてそのブロック
を表示する代表階調の数と代表階調の初期値を求め、こ
の初期値がら、例えばに平均アルゴリズムにより代表階
調の更新を行い、最終的な代表階調と、その代表階調の
ブロック内の配置を決定し、これら代表階調とブロック
内配置とを符号化するようにしたものである。

〔産業上の利用分野〕

本発明は画像データ圧縮方式に係り、特に多値中間調画
像のデータ圧縮方式の改良に関する。

〔従来の技術〕

画像データを表すために必要な情報量は、数値データに
比べて桁違いに増大する。この情報量の増大は、画像デ
ータの中でも特に多値中間調画像やカラー画像で著しい
。

このような画像データを蓄積し、或いは高速。

高品質で伝送するためには、画像ごとの階調情報を高能
率に符号化する必要がある。

画像データの高能率な圧縮方式として、例えば差分適応
ブロック符号化（画像電子学会研究会予稿８５−０７−
０４掲載）、及び、本願の出願人の考案のブロックごと
に複数個の代表階調で表現する方式次にこれら２者の方
式を説明する。

（１）　　前者の方式は、画像を所定の複数画素のブロ
ックに分割した後、ブロック内の階調レベルの最大値と
最小値を２″階調に量子化し、これをビットプレーン符
号化するものであり、画像情報を中央値、差分値、ビッ
トプレーン情報の３成分に分けることを特徴とする。

濃淡画が２５６階調（θ〜２５６）で、ｎ＝２のときに
ついて考えると、ブロック内の階調の最大値（Ｌ　ｍａ
ｘ）と最小値（Ｌ　ｌｌ１ｉｎ）に対して、その差分を
、第７図のように一様量子化するとき、中央値ＬＡ。

差分値ＬＤ、代表階ｊＰＩＰｉ、Ｑ、を次式のように定
めておく。

中央値：　ＬＡ　−（Ｌｍａｘ　＋　Ｌｍｉｎ　）　／
　２差分値：　Ｌ、　−（Ｌｍａｘ　−Ｌｍｉｎ　）　
／　２２２階調示： Ｐ、−り、＋　　−ＬＤ　　（ｉ　　１　）Ｌ。

濃淡画像を表現するに当たっては、濃度変化の大きなブ
ロック程、少ない階調レベル数で、画質を落とさずに近
似し得る。そこで、第８図に示すように、ＬＩ、を閾値
Ｔ　Ｉ、　Ｔ　ｚと比較し、その大小により、そのブロ
ックをそれぞれ１．２．４階調で近似表現する。最大４
階調（階調成分）を用いるので、この階調のブロック内
配置を指定するには、画素ごとに最大２ｂｉｔの情報（
分解能成分）が必要である。分解能成分の２ビットφ１
．φ２は、それぞれビットプレーン符号化する。

（２）後者の方式は、画像を所定の複数画素のブロック
に分割した後、各ブロックの画情報の近似度に応じて、
階調数を１．２，３，４．　　・・・と逐次増加させる
ものであり、代表階調とその代表階調の配置を、例えば
に平均アルゴリズムにより決定することを特徴とする。

この方式の符号化情報を抽出回路のブロック図を第９図
に示す。

この方式は画像信号を入力してハ、ファメモリに蓄積し
、１ブロツクごとに読みだして、次のようにして符号化
情報を作成する。まず、代表階調としてブロックの平均
値を求め、ブロックを平均値で表して、十分な近似がで
きるか否かを調べる。

近似度は、ブロック内の各画素を代表階調で表したとき
の、実際の値との２乗平均誤差を用いる。

もし、近似度が不十分ならば、代表階調のうち誤差の大
きい代表階調を２分して２つの代表階調とすることにし
、その代表階調の２つの初期値を作成する。次に、この
代表階調を用いて、ブロックの画素を最も近い代表階調
に分類するとともに、分類された各画素のグループごと
に平均値（セントロイド）を求め、新しい代表階調とす
る。このようにブロックの近似度に応じて代表する階調
数を増すとともに、代表階調（階調成分）と代表階調の
ブロック内配置（分解能成分）とを決定するものであっ
た。

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

従来技術において、前者の差分適応ブロック符号化にお
いては、ブロックを複数画素で近似したとき、ブロック
の平均濃度は保存されないため、画像を自然に再現する
ためには、各ブロックを代表する階調数を後者の方式よ
り増さなければならないという欠点があり、圧縮比を高
められなかった。一方、後者の階調数を増加させなから
に平均アルゴリズムで代表階調を決定する方式において
は、代表階調数と代表階調の最適な選択が可能であるが
、繰り返し計算が必要であり、符号化に時間が掛かると
いう欠点があった。

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

本発明は、多値中間調画像を所定数の複数画素からなる
ブロックに分割し、このブロック内の階調変化を予め定
められた複数個の闇値と比較し、階調変化に応じたクラ
スタ数と、各クラスタを表示する代表階調の初期値を決
定する。

次いで上記代表階調の中から、各画素ごとに最も距離が
近いものを選んで割り付けることにより各画素を上記決
定された数のクラスタに分類し、この分類結果を記録す
る。

次いで上記各クラスタごとにセントロイド（重心）を求
め、これを新たな代表階調とする。

この代表階調の更新操作において、新たに得られた分類
結果と先の分類結果が一致すれば、代表階調更新操作は
収束したと判定する。

代表階調更新操作が収束した場合、または同操作を一定
回数繰り返した後、求めた代表階調と分類結果をそのブ
ロックの階調成分及び分解能成分として出力する。

〔作　用〕

本発明ではクラスタ数を画像データの階調変化の度合に
応じて選択するとともに、クラスタごとに画素データの
平均値が保存されるので、最適に近い代表階調を決定す
ることができる。しかも、代表階調の更新操作に用いる
演算は至って簡単であるので、高速で実行できる。

〔実　施　例〕

第１図は、本発明に係る画像データ圧縮方式における符
号化情報抽出回路の原理説明図である。

同図において、１は画像データの入力端子、２はバッフ
ァメモリ、３は代表階調の初期値作成手段、４は代表階
調を順次送出する代表階調送出手段、５は代表階調選択
手段、６は分解能成分メモリ、７は収束判定手段、８は
代表階調更新手段、９は階調成分の出力端子、ＩＯは分
解能成分の出力端子である。

本発明のバッファメモリ２は、画素単位の画像信号を端
子ｌから入力して、ｌブロック９４７分の画像データを
蓄積し、１ブロツクずつ画素データを出力する。このバ
ッファメモ”ノ２に格納さ机た画素データは、１ブロツ
クごとに読みだされて必要な処理が施される。

以下、画像データを２５６階調（０〜２５６）、ブロッ
クサイズを４×４画素、１ブロツクを最大４階調で近似
するものとして説明する。

各ブロックの符号化情報は、次のように作成される。ま
ず初期値作成手段３は、１ブロツク分の画素データをバ
ッファメモリ２より読み込んで、ブロック内の最大値（
Ｌｍａｘ）と最少値（Ｌ　ｍ１ｎ）を求め、更にこれら
の値から差分値Ｌｏ＝Ｌｍａｘ−Ｌ＋ｎｉｎを求める。

次に、上記差分値り、を閾値Ｔ　ｌ＋　Ｔ　ｚ、　Ｔ　
ｓと比較し、ＬＤの大小によってそのブロックを表示す
る階調数を１〜４に決める〔第２図参照〕とともに、代
表階調の初期値Ｌ　Ａ、　Ｐ　ｋ、　Ｑｋ、　Ｒｉ＝を
次式から求める。

中央値： Ｌｘ　−１−＋＋＋；ｎ　”　　　　Ｌｏ　　　（ｋ　
＝　１　）２階調表示： Ｐ　ｋ＝　Ｌ　、、ｌｉｎ士□ＬＤ　　（ｋ＝１．２）
３階調表示： ｋ Ｑｋ＝　Ｌ＋＋＋ｉ＋ｓ　”　　　　Ｌｎ　　　（ｋ　
＝１．２．３　）４階調表示： Ｒｋ　−Ｌａｔｈ　＋　−Ｌｔ＋　　　（ｋ　＝１．２
，３１４　）そして、これらの代表階調の初期値を代表
階調送出手段４にセットする。

次に、代表階調選択手段５は、これらの代表階調を用い
て、ブロックの画素を最も近い代表値に分類し、その結
果（階調の配置）を分解能成分メモリ６に書き込む。

次に代表階調選択手段５は、再びバッファメモリ２から
画素データを読みだし、各画素データを上記代表階調の
中の最も距離が近いものが表示するクラスタに分類する
。そして、この分類結果を分解能成分メモリ６に格納す
る。

代表階調更新手段８は分解能成分メモリ６より分類結果
を読みだし、分類された各クラスタごとに平均値（セン
トロイド）を求め、これを新しい代表階調として代表階
調送出手段４にセットする。

代表階調送出手段４１代表階調選択手段５２分解能成分
メモリ６、代表階調更新手段８を用いた新たな代表階調
を求める操作は、必要に応じて繰り返される。

収束判定手段７はこの操作を繰り返し行わせ、新に作成
した分解能成分と以前の分解能成分の一致を検査し、一
致すれば、代表階調を求める操作が収束したと判定する
。そして１代表階調送出手段４に、求めた代表階調を端
子９に出力させるとともに、分解能成分メモリ６から代
表階調のブロック内配置情報を端子１０に出力させる。

階調成分及び分解能成分の符号化については、従来技術
と同様であるので説明は省略する。

以下上記符号化情報抽出回路を実現するための具体的な
実施例を説明する。

第３図、第５図、第６図は第１図に示す本発明の符号化
情報抽出回路各部の詳細図である。

第３図は初期値作成手段３の詳細図であって、図中、端
子３−１にはバッファメモリ２よりブロックごとに画素
データが入力される。

Ｌ＋＋＋ａｘ検出器３−２及びＬ　ｗｉｎ検出器３−３
は、ブロックごとに読みだされた画素データを入力し、
それぞれブロック内の最大値（Ｌ、、、）と最少値（Ｌ
、、、）を出力する。

この最大値、最小値検出回路は、例えば第４図（ａｌに
示す如く、ＲＯＭ３−２−１及びレジスタ３−２−２を
用いて構成し得る。同図に示す構成で最大値を求める場
合は、レジスタ３−２−２を最初クリアしておく。端子
３−１からはブロックの画素データＸｉｊが入力され、
ＲＯＭ３−２−１のアドレスの一部（例えば上位ｎビッ
ト）として加えられる。また、ＲＯＭ３−２−１にはレ
ジスタ３−２−２の値が、これまたＲ　ＯＭ３−２−１
のアドレスの一部（例えば下位ｎビット）として加えら
れる。このＲＯＭ３−２−１は、同図（ｂ）に見られる
ように、アドレスとして入力された２つの値のうち、大
きい方を出力する表を書き込んでおく。こうすることに
より、画素データが入力されるたびに、ＲＯＭ３−２〜
１の出力をレジスタ３−２−２にセットすれば、最終的
にブロックの最大値がレジスタ３〜２−２に得られる。

これに対して最小値を求める場合は、レジスタ３−２−
２に最初総てのビットを１にプリセットしておくととも
に、ＲＯＭ３−２−１には、アドレスに入力した２つの
値のうち小さい方を出力する表を書き込んでおけばよい
。前述の如く、画像データの階調数が２５６の場合には
、ＲＯＭ３−２４の容量は６４に−ｏｒｄ　Ｘ　８ｂｉ
　ｔとなる。

さて、第３図の説明に戻る。減算器３−４はＬ　ｍａｘ
検出器３−２及びり、ｉ、検出器３−３から、上述のよ
うにして求められたし□、とり０８．を入力し、その差
分値（１，＋＞　）を出力する。また、階調数算出ＲＯ
Ｍ３−５は、同様にＬ　ＭＩＩＸとり０．７を、そのア
ドレスに入力し、そのブロックを表示する階調数ｍを出
力する０階調数の最大値は４であるので、階調数１〜４
を０〜３に対応させ、ｍを２　ｂｉｔで表す。

ＲＯＭ３−５には、入力した差分値と閾値Ｔ、。

”ｒｚ　、　Ｔ、との比較結果から（第２図参照）、階
調数即ち前述のクラスタ数ｍを決定する表を予め書き込
んでおく。

次に、求めた差分（Ｊ　Ｌ　ｏ及び階調数ｍは、増分Ｒ
ＯＭ３−６のアドレスの一部に加えられる。また、増分
ＲＯＭ３−６のアドレスには階調磁カウンタ３−７の出
力２　ｂｉｔが加えられる。

階調光カウンタ３−７は最初クリアされており、制御用
の順序信号（図示せず）が加えられるたびに１つずつカ
ウントアツプしたイ直１　　（／＝０．１゜２．３）を
出力する、増分ＲＯＭ３−６はこれらの値を入力し、増
分ＬＤ　　（ｊ！＋１）／　（ｍ＋２）を出力する。加
算器３−８はＬ　ｓｉｎと増分とを入力し、制？Ｂ用の
順序信号（図示せず）が加えられるたびに、増分を増し
て代表階調の初期値を１つずつ端子３−９に出力する。

第５図は、代表階調送出手段４９代表階調選択手段５．
及び収束判定手段７の詳細図である。

第５図において、まず、代表階調送出手段４の動作は、
次のようになる。同図において、端子４−１．４−２か
らは、それぞれ初期値作成手段３と代表階調更新手段８
より、代表階調ＬＡ　　（ｋ＝１）。

またはＰｋ　（ｋ＝１．２）、またはＱｋ　（ｋ＝１゜
２．３）、またはＲｋ　（ｋ＝１．２，３．４）が入力
される。マルチプレクサ４−３は、入力された側に切り
換えられ、これらの代表階調を出力する。

デマルチプレクサ４−４は、これら代表階調を入力し、
ｋの値１，２，３．４に応じて、出力をそれぞれレジス
タ４−５．４−６．４−７．４−８の側に切り換えて各
レジスタにセットする。マルチプレクサ４−９は、各レ
ジスタを順次選択して代表階調を出力する。

次に、代表階調選択手段５の動作について説明する。減
算器５−２には、端子５−１からバッファメモリ２より
ブロックごとの画素データＸｉｊが入力される。そして
、各画素のデータについて、マルチプレクサ４−９を介
して、代表階調が一つずつ階調数分選択され、減算器５
−２に加えられる。減算器５−２は、これらの値から差
分の絶対値ｄ　’１ｊ−ｌ　Ｘ＝Ｊ−（ＲＥＧ）’ｌを
出力する。（ＲＥＧ）ｋ（ｋ−１，２，３，４）は、そ
れぞれレジスタ４−５゜４−６．　４−７．４−８の内
容とする。

検出器５−３は、ｄ　ｋｉｊを入力し、この値が最少と
なるｋ（代表階調のインデックス）を出力する。

検出器５−３は、第４図に示す最少値検出回路とほぼ同
様の構成で、最初レジスタ３−２−２に総てのビットに
“１”をプリセットしておき、３−１に入力した値の方
が大きければ、このときのｋの値をラッチ出力する信号
を付加すればよい。

次に、端子５−１に人力されたプロ・ツクの各画素ごと
に求められた、代表階調のインデックス（番号）ｋ４、
　をシフトレジスタ６−１に１つずつシフトしながら格
納する。ここでは、分解能成分としての代表階調のイン
デックスを記憶しておくメモリ６として、シフトレジス
タ６−１を用いている。

このシフトレジスタ６−１の構成は１６ｗｏｒｄ　Ｘ　
２　ｂｉ　ｔである。

収束判定手段７は不一致検出回路７−１．フリップフロ
ップ７−２から構成される。収束判定の動作は次のよう
にして行われる。不一致検出回路７−１は検出器５−３
からの新たに分類された代表階調のインデックスと、シ
フトレジスタから前回分類した代表階調のインデックス
を入力し、これらの一致を検査する。そして新たに求め
た代表階調インデックスが、前回の代表階調インデック
スと不一致の画素があれば、この旨の信号をフリップフ
ロップ７−２にセットする。これにより、代表階調を求
めるに平均アルゴリズムが収束したか否かが判る。

もし、ブロック中に不一致の画素があれば、フリ、プフ
ロソプ７−２からの信号により、再度、代表階調を更新
する操作を行う。

第６図は、代表階調更新手段８の詳細図である。

第６図において、加算器８−２には、バッファメモリか
らブロックごとの画素データＸｉＪが入力されるととも
に、レジスタ８−３の内容がもう一方の入力に加えられ
ている。そして、この加算器８−２は、−数構出回路８
−６からの加算指令に従って累算を行う。

一致検出回路８−６には、分解能成分メモリ６より読み
だされた代表階調のインデックスにと、順序制御信号に
基づいて、現在求められている代表階調の番号がカウン
タ８−５から入力される。そして、これら２つの値が一
致したとき、−数構出回路８−６は前述の加算指令を出
力する。

またこれと同時にカウンタ８−７では、−数構出回路８
−６からの加算指令の回数を計数している。

そして、これら２つの値が一致したとき、−数構出回路
８−６は前述の加算指令を出力する。

またこれと同時にカウンタ８−７では、−数構出回路８
−６からの加算指令の回数を計数している。

そして、各代表階調について、累算値がレジスタ８−３
に、ブロック内の個数がカウンタ８−７に求められるこ
とになり、これら２つの値が除算器８−４に入力される
。これによって、新たな代表階調が、前回の代表階調に
属する画素の平均値（セントロイド）として求められる
。

新たな代表階調はレジスタ８−８にセットされ、代表階
調送出手段４へ送られる。

本実施例では収束判定を、ブロック内の代表階調の配置
が前回と新たに求めたものが一致するか否かで行なった
が、これに変えて、前回求めた代表階調によるブロック
画情報の近似の誤差と、新たに求めた代表階調による近
似の誤差の差分を求め、この差分の減少の割合により判
定するようにしてもよい。

また、第１図では、収束判定手段７を用いて、代表階調
が収束するまで更新する操作を行なっているが、これも
種々変形して実施できる。

即ち、代表階調の正確な選択より処理速度の方を重視す
る場合には、収束判定手段７を省略し、代表階調更新操
作は初期値から１度だけ行うようにしてもよい。

また、上記一実施例では、ブロックサイズを４×４画素
とし、ブロックを構成する階調数を最大４個とした例を
説明したが、ブロックサイズや表示階調数は、画像の種
類や符号化条件を考慮して、任意に選んでよい。

更に、上記一実施例では、モノクロ多値中間調をデータ
圧縮する場合について述べたが、本方式はカラー多値画
像にも適用できることは明らかである。

本発明をＲＧＢのカラー多値画像に適用する場合には、
モノクロ階調の代わりに、Ｒ，Ｇ、Ｂの３要素を持つ３
次元ベクトルを考えればよく、代表階調（代表色）の近
さの尺度は、ベクトル間の距離で計ればよい。従って、
本方式をカラー多値画像に適用したときは、１ブロツク
が複数個の代表色で近似される。

〔発明の効果〕

本発明によれば、画像を細分した各ブロックでの階調の
平均値が保存され、最適に近い代表階調が選択されるの
で、各ブロックを表示する階調数を少な（とることがで
き、大きい圧縮比が得られる。また、各ブロックの階調
変化に応じて、表示階調の数（クラスタ数）と、代表階
調（クラスタ中心）の初期値を定めてに平均アルゴリズ
ムを用いるので、計算時間を短縮でき、高速処理が可能
となる。

【図面の簡単な説明】

第１図は本発明の符号化情報抽出回路説明図、第２図は
ブロックの表示階調数と初期値を説明するための図、 第３図は初期値作成回路詳細説明図、 第４図（ａ）及び（ｂ）は、最大値・最小値検出器説明
図、 第５図は代表階調送出手段１代表階調選択手段。 収束判定手段説明図、 第６図は代表階調更新手段説明図、 第７図は従来の画信号の量子化説明図、第８図は従来の
ブロックの表示階調数と符号化情報説明図、 第９図は従来の画像データ圧縮方式説明図である。 図において、２はバッファメモリ、３は初期値作成手段
、４は代表階調送出手段、５は代表階調選択手段、６は
分解能成分メモリ、７は収束判定手段、８は代表階調更
新手段、ｘｔＪは画素データ、Ｌａ　、Ｐｈ　、Ｑｋ、
Ｒ工は代表階調の初期値、φは分解能成分を示す。 本発明の符号化情報抽出回路説明図 第１図 階調の初期値　　　　　　Ｌａ　　　　　Ｐ−Ｑ−Ｒｋ
プロ７りの表示階調数と初期値 第　　２　　図 初期値作成回路詳細説明図 ！＠　　３　　図 ＲＯＭ構成例説明図 最大値・最小値検出Ｓ！！明図 第　　４　　図 代表階調退出手段１代表階調選択手段、及び収束判定手
段説明図第５図 第　　６　　図 従来の画信号の量子化説明図 ＠　　７　　図 従来のブロックの表示階調数と符号化情報説明図箱　　
８　　図

Claims (1)

1. 【特許請求の範囲】 画像を所定数の画素からなるブロックに分割するととも
   に、ブロック内の階調変化の大きさに応じたクラスタの
   数を予め設定しておき、 各ブロックごとに、 ブロック内の画素データから、該画素データの最小値及
   び最大値並びに両者の差分を求め、該差分の大きさから
   対応したクラスタ数を選択するとともに、該各クラスタ
   を表示する代表階調の初期値を算出して、各画素データ
   を最も距離が近い代表階調が表示するクラスタに分類し
   、 同一クラスタに分類された画素データのセントロイドを
   算出して新たな代表階調を作成し、前記各画素データを
   該新たに作成された代表階調のうちから最も距離が近い
   代表階調が表示するクラスタに分類し直す操作を少なく
   とも１回実行し、最終的に決定された少なくとも１個の
   代表階調と各画素データが属するクラスタ番号とでブロ
   ックの画情報を表すようにしたことを特徴とする画像デ
   ータ圧縮方式。