JPS594380A - 中間調画像圧縮方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （１）発明の技術分野 本発明は、中間調画像圧縮方式に係シ、特に多値画像を
予測し、予測誤差を可変長符号化する方式に関する。

（２）発明の背景 写真・地図・印影などの２値では十分に表わせない画像
を伝送するためには、中間調ファクシミリが用いられる
。この場合、画像伝送時間圧縮のために画像データを符
号化して圧縮する事が必要である。この画像圧縮におい
ては、簡単な回路構成で大きな圧縮比を得、かつ高速に
処理することが要望される。

（３）従来技術と問題点 従来、中間調ファクシミリでは、３〜１６階調を多値信
号か擬似中間調を用いて表示する。このうち、多値信号
を用いる場合、データ圧縮方式とし７て、順位予測符号
化方式（特開昭第５６−７３９７５号公報「多値画像信
号符号化復号化方式とその装置」、電子通信学会通信方
式研究会資料Ｃ８７９−１７６に水野昇治、飯沼−元に
よって著わされた「中間調ファクシミリ信号の符号化」
参照）が、優れた方式として知られている。この方式で
は、マルコフモデルによる理論上の圧縮比の限界に対し
て、約９５チの大きい圧縮比が得られる。しかしこの方
式では、圧縮効率を上げるために予測誤差を符号化する
時に複雑な手順をとらなければならなかった。すなわち
、この手順は、具体的には予測誤差である予測順位をビ
ットごとに予測適中率の高低によシ、例えば９０％以上
の予測適中率のグループとそれ以下のグループの２つの
グループに分け、各グループに属するビットをつなぐ。

そして、２つの符号表を用いて、各グループのつないだ
ビ、ト列をそれぞれランレングス（ＲＬ）符号化する。

ビット毎にグループ分けの処理を行うので処理時間は長
くなる。また、個々のＲＬ符号は、復元側で順序よく復
元できるようにするため、上記の２つのグループととに
伝送する順序を調整しなければならなかった。このため
、従来の中間調画像圧縮方式によれば、複雑な回路構成
を必要とし、かつ処理時間が長いという問題があった。

（４）発明の目的 本発明の目的は、多値画像信号を複数画素単位に予測す
ることによシ、簡単な回路構成で大きな圧縮比を得、か
つ高速処理が可能な方式を提供することにある。

（５）発明の構成 マルコフ情報源からの情報を可変長符号化する〆き、複
数個づつ通報をまとめて符号化することで、１個づつ通
報を符号化するよシも、エントロピーに近い平均符号長
が得られることが知られている（　ＰＲＯＣＥＥＤＩＮ
ＧＳ　ＯＦ　ＴＨＥ　ＩＦＩ：ＥＥ、　ＶＯＬ、６９゜
Ａ２　ｐｐ２３９−２５１．１９８２年２月ｒＦｕｎｄ
ａｍｅｎｔａｌＬｉｍｉｔｓ　１ｎ　Ｉｎｆｏｒｍａｔ
ｌｏｎ　ＴｈｅｏｒｙＪ　＊　ＡＡＲＯＮＤ、ＷＹＮＥ
Ｒ参照）。従って、複数画素分まとめて予測すれば、予
測誤差を可変長符号化しても理論圧縮限界に圧縮比を近
づけることができる。しかし、符号化画素数を増すと参
照画素数も増すため、予測を読取り専用メモリ（ＲＯＭ
）で行なう場合、大容量のＲＯＭが必要となる。

そこで、本発明では、通常の多値画像中の隣接画素間の
階調差の分布ＫＦｉｆ［）があることに注目し、複数画
素単位にまとめ、この複数画素の組合せを発生頻度の高
低の大小によって２つのグループに分け、発生頻度の高
い組合せだけを用いて予測するようにしたものである。

例えば、通常の濃淡画像では、８値ｎ！ｉ像中の隣接画
素間の階調差の分布については、統計をとると・階調差
０が約６０チ、階調差±１が約２５−発生する　このた
め、２画素ごとまとめた場合、階調差０．＋１の組合せ
によって、画像全体の約８０ｑ６が表現できる。

すなわち、本発明の要旨は、各々の画素が多値の階調の
いずれかで表わされる中間調画像データを圧縮する中間
調画像圧縮方式において、該画素を複数個まとめてブロ
ックとし、発生頻度の大きいブロックの階調の組合せを
基本パターンとして、周囲の階調と比較して発生順位を
予測して予測順位を得、該予測順位を可変長符号化する
ことを特徴とする中間調画像圧縮方式にある。

（６）発明の実施例 以下本発明の実施例を図面によシ説明する。

実施例として、Ｂ値画像を２画素づつまとめて予測する
場合を考える。第１図に参照画素と符号化画素の位置関
係を示す。第１図では、参照画素Ｂ、Ｃをまとめて１ブ
ロツクとし、また、符号化画素Ｘｏ、Ｘ、をまとめて１
ブロツクとしているＯ第２図は、２画素の階調の組合せ
を示す表図である。第２図においては、例えば２画素間
の階調差が＋７の場合、２画素Ｘｏ＊　Ｘｌの階調の組
合せは一方が０、他方が７の一組のみである。２画素間
の階調素が＋６ならば、２画素の階調の組合せは（０，
６）と（１，７）の２組がある。以下、他の階調差につ
いても同様に考えられる。第２図に示された組合せを発
生頻度の高低によって２つのグループに分ける。以下で
は、発生頻度の高いグループに属する組合せを基本パタ
ーンと呼び、発生頻度の低いグループに属する組合せを
非基本・臂ターンと呼ぶ。本発明では、基本パターンだ
けを用いて予測を行なう。基本パターンの組合せの個数
は、ハードウェア構成上から、２のべき乗が好ましい。

従って、基本／ＩＰターンとしては、第２図より次のも
ののいずれかが選ばれる。

■階調差０の８個の組合せ 、■階調差０の８個と、階調差±１から発生頻度の高い
もの８個の計１６個の紹合せ ■階調差０．±１の発生頻度の高いもの２２個と、階調
差±２から発生頻度の高いもの１０個の計３２個の組合
せ 本実施例では、基本・ぐターンとして、上記■の組合せ
を選ぶ。

基本パターンには、発生頻度に順に番号を付ける。以下
では、この番号をノリーン通と呼ぶ。パターン屋は３２
個あシ、５ビ、トで表わされる。

非基本・臂ターンには、その基本ノ４ターンに最も近い
基本パターンのｄ’ターン屋を付しておく。

第３図は、本発明の一実施例による方式に適用される中
間調画像圧縮回路を示すブロック図でおる。以下、第３
図の圧縮回路の動作について述べる。

入力された８個の画像データを一画素分レジスタ２０に
七ッ卜する。同時にレジスタ２０にもと入っていたデー
タをレジメタ２１に移し、レジスタ２１にもと入ってい
たデータはレジスタ２４に移す。更に、８値画像データ
をもう１画素分入力し、上記の動作を繰返す。これによ
ってレジスタ２０．２１．２４には第１図の画素Ｘ１＊
　ＸＯｅ　Ａがそれぞれ入ることになる。読み出し専用
メモリ（ＲＯＭ）２２は、レジスタ２０．２１の出力の
ｘｏ　ｌＸ１のデータをアドレスとしてアクセスされる
。

レジスタ２０．２１の組合せが基本パターンの場合、Ｒ
ＯＭ２２はパターンＡを出力する。ＲＯＭ２２は、本実
施例でけ６４ワード×５ピツトのメモリでありＸＯ＋　
Ｘｌの値に対応するノＪ？ターン扁の表を格納している
。もし、レジスタ２０．２１の組合せが非基本／４ター
ンの、場合は、ＲＯＭ２２け非基本パターンが入力され
た旨、制御回路３４に知らせるとともに、この非基本／
ターン如最も近い基本パターンの７４ターン屋を出力す
る。次に、ＲＯＭ２２から出力されたパターン屋をファ
ースト・イン・ファースト・アウトレジスタ（ＦＩＦＯ
）２５に書き込むとともに、レジスタ２３にセットする
。ＦＩＦＯ２５は、参照ブロックＢＣの基本パターンの
パターン屋を記憶しておくためのものである。ＦＩＦＯ
２５から参照ブロックＢＣを読み出す。以下の動作は、
レジスタ２０．２１に格納された符号化ブロックＸｏ　
、　ｘｌが基本パターンのときと、非基本パターンのと
で異なる。

（イ）符号化ブロックが基本パターンのときＦＩＦＯ２
５の出力６６とレジスタ２３．２４の出力６５．６７を
ＲＯＭ２６のアドレスに入力する。

ＲＯＭ２６は本実施例では、８キロワード×５ビツトの
メモリでアシ、パターン屋とＢＣとＡとの値に対応する
順位予測基本パターンを表として格納している。従って
、ＲＯＭ２６は、ＦＩＦＯ２５からの参照ブロックＢＣ
とレジスタ２４からの参照画素人の状態から、符号化ブ
ロックｘ、）　、　Ｘｌの状態が統計的にみて何番目に
出易い状態であったか予測し、その順位を出力６８に出
力する。ＲＯＭ２７は出力６８を介してその順位を入力
し、その順位に割当てた可変長符号を出カフ０に、符号
長を出力６９に出力する。可変長符号を表わす出カフ０
は、マルチプレクサ３１を介して、シフトレジスタ３３
にセットされる。符号長を表わす出力６９は、マルチプ
レクサ３０を介してカウンタ３２にセットされる。カウ
ンタ３２は、０になるまで１つづつカウントダウンし、
そのつどシフトレジスタ３３をシフトして、可変長符号
を切シ出す。例えば、順位が４の場合、符号長は４であ
シ、カウンタは４ビツトだけカウントするのて４ビツト
の符号が出力されるが、順位が１の場合、符号長は１で
アシ、カウンタは１ビツトのみカウントするので１ビツ
トの圧縮されたデータが出力される。

（ロ）符号化ブロックが非基本パターンのとき本実施例
では、非基本／４ターンのときは、差分ＰＣＭ　（ＤＰ
ＣＭ）で符号化を行なっている。レジスタ２０．２１．
２４の出力をＲＯＭ２８のアドレスに入力する。ＲＯＭ
２Ｊｌｊ、その入力に基づいて、隣接画素間の階調差２
組を出力する。画素Ａ　、　ｘ、３間の階調差３ビツト
が信号７２であシ、画素ｘＯｔＸ１間の階調差３ビ、ト
が信号７１である。階調差は、−７〜＋７までの値をと
るが、負の値は補数をとる。ＲＯＭ２９は階調差を入力
して、非基本パターンである旨のフラグ（以下、非基本
パターンフラグと呼ぶ）を含む可変長符号７４と符号長
７３とを出力する。ここで、可変長符号は、階調差の発
生頻度の太きいもの程短かい符号を割当てる。このＤＰ
　ＣＭの可変長符号は、前述の予測順位の可変長符号と
上記の非基本パターンフラグで区別する。次に、可変長
符号７４をマルチプレクサ３１を介してシフトレジスタ
３３にセットし、符号畏７３は、マルチプレクサ３０を
介して、カウンタ３２にセットする。カウンタ３２けＯ
になるまで１つづつカウントダウンし、そのつどシフト
レジスタ３３をシフトし、可変長符号を切出す。

以上が１つの符号化ブロックを圧縮する手順である。上
記の手順を繰返して８値画像の圧縮を行なう。　　　　
　　　　　　　　　　　　　　　以下余白第４図は本発
明の一実施例による方式に適用される復元回路のブロッ
ク図である。第４図において、シフトレジスタ４０は、
シフトしながら１ビツトづつ送られてくる圧縮データを
受ける。ＲＯＭ４１は、シフトレジスタ４０の内容をみ
ておシ、前述の基本パターンの順位の可変長符号を検知
すると、可変長符号の順位を出力する。また、もし前述
の非基本パターンフラグを検知すると、ＲＯＭ４１は、
復元ブロックが非基本パターンである旨制御回路に信号
９４で知らせる。以下の動作は、基本パターンの場合と
非基本パターンのときで異なる。

＠）復元ブロックが基本パターンのときＲＯＭ４１から
出力された順位をレジスタ４２にセットする。ＦＩＦＯ
４７には参照ラインの参照ブロックの／４ターン屋を格
納しである。ＦＩＦＯ４７から復元ブロックの上段にあ
たる参照ブロックＤＣのパターン屋を読出す。レジスタ
５１には、既に復元された画素人が入っている。上記の
レジスタ４２゜５１およびＦＩＦＯの出力は、ＲＯＭ　
４８のアドレスに入力される。ＲＯＭ４８は、順位に応
じた復元基本／’Ｐターンを格納しておシ、入力された
状態から復元ブロックＸｏ　ＸＩのパターン扁を出力８
９に出力する。このノ４ターンＡをＲＯＭ４９のアドレ
スに入力する。同時にこのパターンＡ１に次のラインを
復元するときの参照ブロックのノ４ターン屋としてＦＩ
ＦＯ４７に書き込む。ＲＯＭ４９は、入力され九ノサタ
ーン屋よシ復元ブロック２画素分の階調を出力する。画
素Ｘ６　　＋　ＸＩの階調は、それぞれレジスタ５１．
５２にセットされる。レジスタ５１の出力９３として復
元した１画素の階調を得る。次にレジスタ５２の内容を
レジスタ５１に移し、次の画素の階調を得る。レジスタ
５１には、次の参照画素人がセットされることになる。

（ロ）復元ブロックが非基本パターンのときシフトレジ
スタ４０の出力４１をＲＯＭ４３のアドレスに入力する
。ＲＯＭ４３は、可変長符号から隣接画素間の階調差８
３．８４を出力する。ＲＯＭ４４は、上記の階調差８３
．８４とレジスタ５１（画素人の階調）の出力９３をア
ドレスに入力する。そし°［、ＲＯＭ４４は、復元ブロ
ックの画素ＸＩ）　　＋　ＸＩの階調８６を出力する。

ＲＯＭ４５は、階調８６を入力し、復元ブロックが非基
本・マターンであるから圧縮回路のときと同様に、この
非基本パターンに最も近い基本ノ々ターンのパターン屋
を出力する。このノ９ターン扁は、次のラインを復元す
るときの参照ブロックのパターン肩として、マルチプレ
クサ４６を介してＦＩＦＯＫｉ＊き適寸れる。

さて、復元した２画素分の階調４４は、マルチプレクサ
５０を介してレジスタ５１．５２にセットされる。これ
によって復元した画素Ｘ、の階調をレジスタ５１の出力
９３として得る。また、レジスタ５２の内容をレジスタ
５１に移して、画素ｘｉの階調を得る。

以上が、復元プロ、り′ｆ：ｌブロック分復元する手順
である。上記の手順を繰返して多値画像の復元を行なう
。ここで、最も容量が大きい予測用のＲＯＭは、圧縮回
路でＲＯＭ２６、復元回路ではＲＯＭ４８である。双方
とも容量は８キロワード×５ビツトである。従って、回
路構成上、これらは容易に実現できる。

上述の実施例では、２画素づつまとめて予測したが、圧
縮、復元の手１−は、３画素以上、まとめて予測する場
合も同様である。また、実施例では、符号化プロ、りに
は、ｌライン上の画素をとったが、符号化ブロックには
、２ライン以上にまたがる画素をとってもよい。さらに
実施例では、参照ブロックと参照画素を組合せて予測し
たが、参照ブロツクだけ、あるいは、参照画素だけの組
合せで予測をしてもよい。また、非基本・母ターンの圧
縮にＤＰＣＭを用いたが、これは他の圧縮方式でもよい
。これまでは、多値画像データを圧縮後、忠実に復元で
きる可逆符号化について述べた。しかし、次のように不
可逆符号化をしてもよい。すなわち、多値画像の非基本
パターンを基本ノ４ターンで近似して、基本ノ臂ターン
と、近似した非基本パターンだけで符号化をするわけで
ある。上記のように、不可逆符号化をすれば、画質は少
々劣化するが、圧縮比をさらに大きくとることができる
。

（７）発明の効果 本発明によれば、複数画素まとめて予測するので高速処
理ができ、かつ大きい圧縮比を得ることができる。また
、予測誤差を可変長符号化するので回路構成が簡単にな
る。

【図面の簡単な説明】

第１図は、本発明の一実施例による中間調画像圧縮方式
に用いられる参照画素、参照ブロックと符号化ブロック
の位置関係を示す図、第２図は第１図に示した符号化ブ
ロックの８値画像信号の２画素の階調の組合せを示す表
図、第３図は本発明の一実施例による方式を実施するた
めの中間調画像圧縮回路を示すブロック図、第４図は本
発明の一実施例による方式を実施するための圧縮データ
復元回路を示すブロック図である。 図中２０．２１，２３．２４はレジスタ、２２゜２６．
２７，２８，２９はＲＯＭ、２５はＦＩＦＯ１３０，３
１はマルチブレフサ、３２．３３はシフトレジスタ、３
４は制御回路、４０はシフトレジスタ、４１，４３，４
４，４５，４８．４９はＲＯＭ、４６．５０はマルチプ
レクサ、４２　、４６゜５１．５２はレジスタ、５３は
制御回路でおる。 特許出願人 富士通株式会社 特許出願代理人 弁理士　青　木　　　朗 弁理士西舘和之 弁理士　内　１）幸　男 弁理士　山　口　昭　之 手続補正書（自発） 昭和５７年ｚ月ψρ日 特許庁長官若杉　η」　夫　殿 １、事件の表示 昭和５７年　特許願　　第１１５００４号２、発明の名
称 中間調画像圧縮方式 ３、補正をする者 事件との関係　　特許出願人 名称　（５２２）富士ＪＩＩ株式会社 ４、代理人 （外６　名） ５、補正の対象 図面（第１図乃至第４図）　　　　　１頒６、補正の内
容 正式図面を追完します。 （ただし内容に変更はめジオせん） Ｚ　添付書類の目録

Claims (1)

【特許請求の範囲】
1. ■、各々の画素が多値の階調のいずれかで表わされる中
   間調画像データを圧縮する中間調画像圧縮方式において
   、該画素を複数個まとめてブロックとし、発生頻度の大
   きいブロックの階調の組合せを基本パターンとして、周
   囲の階調と比較して発生順位を予測して予測順位を得、
   該予測順位を可変長符号化することを特徴とする中間調
   画像圧縮方式。