JP2800251B2 - データ圧縮法 - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、中間調画像のデータ圧縮法に関する。

（従来の技術） ファクシミリ等で画像を送る時、通常は送信側で圧
縮、受信側で伸長という処理を行ない、実際に送るビッ
ト数を画像のビット数よりも少なくなるようにして、通
信時間の短縮を実現している。

この圧縮・伸長は一定のルール（MH法、MR法など）に
基づいて行なわれておりこのルールは一般的な原稿（文
字や図形等が描かれたもの）を送る時に効率がよくなる
ように設計されている。

即ち、このような原稿は白又は黒（特に白）のドット
が連続する確率が非常に多く、発生頻度の高い連続ドッ
トについてはより少ないビット数のデータに変換する事
で圧縮を行なっている。しかし、かかる圧縮方法では、
発生確率の低い数ドット以下の場合、圧縮変換後のデー
タのビット数が逆に増加するという現象がある。全体と
しては圧縮効率をよくしているので通常はこの欠点は問
題とはならない。

ところで、最近、ファクシミリを使って写真等の中間
調を含んだ画像を送る要望が増えており、ファクシミリ
でも写真モードを持つものがある。ビット単位では、白
又は黒の表現しかできないため、中間調画像に対しては
中間調処理を行ない、１つの画素を複数個のビット（通
常はＮ×Ｎ個）として扱い、その画素の中での白黒比に
よって中間調を表現している。

ファクシミリで中間調画像を送ろうとした場合、この
ような画像データは、一般の文字原稿に比較して白又は
黒が連続する確率が低く、従来通りの圧縮を行なうと、
効率が悪く、逆にビット数が増加する可能性もある。

本出願人は、別の出願（特願平１−44139号）におい
て、中間調画像を効率よく圧縮できるデータ圧縮法を開
示している。このデータ圧縮法では、データ圧縮の前処
理として、画像を複数の段階の濃度に対応する２次元的
に広がりを有する複数のドットにより表現し、この表現
した画像に対応する１次元の濃度パターンを定めてお
く。また、１次元の濃度パターンを隣接して並ぶように
画像データの再構成位置を定めておく。こうして、２次
元的ドットを所定の１次元の濃度パターンに変換する。
こうして再構成した画像データをデータ圧縮する。１次
元の濃度パターンを隣接して並べるので、白または黒ド
ットがデータ圧縮方向に連続しやすくなり、効率よく圧
縮できる。

（発明が解決しようとする課題） 上記のデータ圧縮法により白または黒のドットがデー
タ圧縮方向に連続的に発生しやすくなり、中間調画像デ
ータの圧縮効率を改善することができる。

しかし、１次元濃度パターンへの変換によっても中間
調画像中に白または黒のドットが孤立して存在すると白
黒交互のパターンが発生しやすく、データ圧縮の効率が
その付近で改善されない。たとえば、MH法では、白の１
ドットは６倍のデータに、黒の１ドットは３倍のデータ
に変換されてしまい、データ数が増えてしまう。

本発明の目的は、中間調画像データをさらに効率よく
圧縮できるデータ圧縮法を提供することである。

（課題を解決するための手段） 本発明に係るデータ圧縮法は、画像を複数の段階の濃
度に対応して画像のデータ圧縮方向及びその直交方向に
複数ドットの広がりを有するｍドットからなる２次元濃
度パターンにより表現し、この表現したｍドットの画像
をデータ圧縮方向に対して直交する方向にｍドットの広
がりを有する１次元の濃度パターンに変換し、この１次
元濃度パターンをデータ圧縮方向に隣接して並べ、こう
して並べかえた画像データについてデータ圧縮方向に連
続した所定数のドットのブロックを参照し、白又は黒の
孤立点があった場合に孤立点がなくなるようにデータを
入れ換え、データ圧縮を行うことを特徴とする。前記２
次元濃度パターンは、たとえば、Ｎ×Ｎドット、Ｎ×Ｍ
ドット又は非矩形のドットパターンとして構成される。

（作用） ２次元的ドットを１次元の濃度パターンに変換した
後、所定位置に隣接して並べる。こうして再構成した画
像データについて、さらにデータ圧縮方向に白ドット又
は黒ドットの孤立点があるか否かを判断する。孤立点が
ある場合は、孤立点をなくすようにデータを入れ換え
る。このデータ入換えにより、白又は黒ドットがデータ
圧縮方向にさらに連続しやすくなる。従って、通常のデ
ータ圧縮法を用いても、効率よくデータを圧縮できる。

（実施例） 以下、添付の図面を参照して本発明の実施例を説明す
る。

１画素を２×２の４ドットで構成し中間調画像を表現
する濃度パターン法の場合について説明する。この場
合、５段階で表現した画素の濃度（０〜４）に対応して
４ドットのうち所定個のドットを黒で表現するので、た
とえば第１図に示すように、濃度が増すにつれ黒くなる
５種類の濃度パターン（黒ドットをハッチング部分で表
わす）で画素を表現できる。

従って、読み取った中間調画像は、この濃度パターン
の集合で表現され、その一部を抽出すると、たとえば第
２図のようになる。

第２図の中間調画像データをそのまま従来のデータ圧
縮法（たとえばMH法）で圧縮する場合は以下の如き不都
合が生じる。たとえば第２図の横方向の最上ラインおよ
び第３ラインについてはほとんど１ドットごとに白黒の
反転が起っている。この場合、白の１ビットは６倍のデ
ータに、黒の１ドットは３倍のデータに変換されてしま
うため、結果的にデータの数は4.5倍となり、データ圧
縮の目的に対して逆効果となってしまう。

中間調画像データの圧縮を有効に行うため、本実施例
では、第３図に示すように、２次元の２×２ドットの濃
度パターンを４×１ドットの１次元の濃度パターンに変
換する。このとき、第４図に示すように、２×２ドット
の濃度パターンのドット位置と４×１ドットの濃度パタ
ーンのドット位置とを、４×１ドットの濃度パターンに
おいて下から順に連続的に黒ドットになるように対応さ
せる。そして、この４×１ドットの１次元パターンをデ
ータ圧縮方向に隣接して並べる。この隣接配置により、
黒ドット、白ドットになりやすい位置が隣接するように
なる。

この１次元パターンを用いての画像の再構成におい
て、４×１ドットのパターンは２×２ドットのパターン
の２個分でデータ圧縮方向に直交する１辺の長さ（４ド
ット）が同じになる。そこで、再構成画像をたとえば元
の画像の同じ大きさにするため、第５図に示すように、
４ライン分の画像データを２×２ドットのパターン（す
なわち１画素）の単位で左側から上下の順で取り出し
て、４×１ドットのパターンに変換して右方向に並べ
る。この１次元パターンの隣接した配列により、黒ドッ
トまたは白ドットになりやすい位置が隣接して並ぶこと
になる。

第６図に、第２図の中間調画像のデータについての画
像再構成結果を示す。第２図の元の中間調画像に比べ、
黒ドットや白ドットがデータ圧縮方向に連続しているこ
とが明瞭に示されている。第７図は、その場合の第２図
のドット位置との対応を示す。ここに数字（ij）は、第
（ｉ＋１）列の（ｊ＋１）番目のデータを示す。

このように再構成した画像データについて、データ圧
縮方向に白または黒の孤立点があった場合、白の１ドッ
トは６倍のデータに、黒の１ドットは３倍のデータに変
換され、変換効率が悪い。そこで次に、孤立点の前後数
ブロックのデータを参照して白または黒のデータが連続
するようにデータを入れ換える。

このため、あらかじめ、どういうパターンのデータの
場合にどのようにデータを入れかえるかを決めておき、
その規則に従ってデータを入れ換える。

第８図（ａ），（ｂ），（ｃ）は、本実施例における
データ入れ換えの対象となるパターンの例を示す。本実
施例では８ブロックのデータを参照する。第８図（ａ）
の場合、左側のパターン（“11010111"）が発生する
と、右側のパターン（“11001111"）に入れ換える。第
８図（ｂ）の場合、パターン“00101"がどの位置にあっ
ても、パターン“00101"があれば“00011"に変換する。
たとえば、第６図の第２ラインにそのようなパターンが
存在する。第８図（ｃ）の場合、先頭に“1010"のパタ
ーンがあれば、“1100"のパターンに入れ換える。第６
図の第２ラインの先頭にそのようなパターンが存在す
る。これらのデータ入れ換えの例では、特にデータ変換
効率が悪い白の孤立点と黒の孤立点のパターンの発生を
なくすようにした。これにより、データ圧縮効率が上が
る。

なお、隣接した位置のデータを入れかえているだけな
ので、マクロ的に見れば、濃度は変わらないので、中間
調画像の画質への影響は小さい。

さらに、データ圧縮効率が悪い白ドットが数個連続す
る場合についても、画質への影響が大きくなければ、デ
ータ入換えを行うとデータ圧縮をさらに効率よく行え
る。

第９図の再構成画像は、第２図の中間調画像につい
て、第８図（ａ）〜（ｃ）のパターンに従って孤立点を
なくしたものであり、第２図の元の画像データに比べて
横方向（データ圧縮方向）に白または黒が比較的連続し
て発生している。従って、この再構成画像データについ
て従来の一般的なデータ圧縮法（MH法など）を用いる
と、データ圧縮が有効に行える。

また、元の画像に復元するときは、４×１ドットのデ
ータを２×２ドットのデータに戻す逆の変換を行えばよ
い。

なお、一次元パターンを第５図のように２列の画素を
交互に並べる代わりに、１列の画素をそのまま並べても
よい。再構成画像は元の画像と異なる大きさになるが、
受信側で元の画像に戻すことができる。

以上のように、２次元の画像データを１次元に変換し
てから必要な場合にデータ入換えを行った後、データを
圧縮する事で従来のデータ圧縮方法を使用しても比較的
効率よく圧縮でき、高速の伝送や少ないメモリ領域への
格納に効果があらわれる。次に、以上に説明したデータ
圧縮法を実現するファクシミリ装置の構成を第10図に示
す。このファクシミリ装置の送信側においては、読取部
１で、画像を読取り、画素当たりの濃度をデジタル値に
変換し、中間調処理部２で、このデジタル濃度値を２×
２ドットの中間調画像データに変換し、２次元/1次元変
換部３で、上に説明したように２×２ドットの中間調画
像を４×１ドットの画像に変換し、圧縮処理部４で、一
般のデータ圧縮法（たとえばMH法）で変換データを圧縮
し、送信する。また、送信データを記憶部５に記憶して
おき、送信する。

受信側においては、通信データを必要ならば記憶部５
に格納しておき、伸長処理部６で圧縮データを変換デー
タに戻し、１次元/2次元変換部７で変換データを中間調
データに変換し、出力部８で用紙に画像を印字する。

第10図に示すファクシミリ装置の構成において従来の
ファクシミリ装置と異なる点は、２次元/1次元変換部３
と１次元/2次元変換部７を備えることである。その他の
部分、たとえばデータ圧縮、伸長用の圧縮処理部４、伸
長処理部６などは、従来と同じである。

次に、２次元/1次元変換部３においてCPU（図示せ
ず）により制御される変換回路について、第11図に示す
書込回路と第12図に示す読出回路を用いて説明する。

第２図に示した中間調画像を第９図に示す再構成画像
に変換するには、画像データをメモリに書き込み、次
に、メモリのデータを読みだして第６図のように再構成
を行う。最後に所定のパターンに該当する場合は、デー
タ入換えを行う。実際には、両図の回路は併せて１つの
回路として構成することができる。

第11図に示す書込回路においては、２次元/1次元変換
部３を制御するCPUのアドレスバス、データバスおよび
ライト信号（▲▼）が４個のメモリ21,22,23,24の
アドレス端子、データ端子、▲▼端子に接続され
る。各メモリ21,22,23,24は、それぞれ、中間調画像の
第１列，第２列，第３列，第４列のデータ（第７図参
照）を記憶する。このため、アドレスバスの信号をデコ
ーダ25でデコードしてチップセレクト信号を生成し、各
メモリの▲▼端子に入力して１つのメモリだけを選
択する。こうして、４列の信号が、１列ごとにメモリ2
1,22,23,24の順に書き込まれる。

メモリ21,22,23,24のデータは、第12図に示す読出回
路で読出され、再構成される。このとき各列のデータ
は、読み出された後で並べかえる必要がある。第７図に
示すように、第１ラインの出力データ（出力データの場
合は「ライン」を用いて、入力データの場合の「列」と
の混同を避ける）は、第１列と第３列の半分の入力デー
タを並べかえたものである。そこで、出力ラインを指定
するデコーダ25のデコード信号が第１ラインに対する第
１ライン出力信号である場合、負論理ORゲート31,33を
介してチップセレクト信号をメモリ21,23の▲▼端
子に同時に出力する。これにより、メモリ21,23のデー
タがCPUからのリード信号に対応して同時に読み出され
ることになる。また、読出されたデータは、ラインの第
１列の奇数番目ビット（01,03,…）と第３列の奇数番目
ビット（21,23,…）を組合わせて第７図に示すように交
互に並べねばならない。そこで、メモリ21とメモリ23の
それぞれの奇数番目のビット（データ端子1,3,5,7）
が、第７図に示す出力データの順に並べられて３−ステ
ートゲート35の入力端子に接続される。このゲート35の
出力端子はCPUへのROM39のアドレス端子に接続される。
ゲート35もデコーダ25の第１ライン出力信号をゲートコ
ントロール信号として選択される。こうして、メモリ2
1,23のデータをアドレスに対応して順次読出して第１ラ
インの出力データに再構成する。

第２ラインの出力も同様に行われる。この場合、メモ
リ22の第２列データの偶数番目ビット（10,12,…）とメ
モリ24の第４列データの偶数番目ビット（30,32,…）と
を組合わせて出力する。このため、メモリ22,24を第２
ライン出力の際に同時に選択するため、デコーダの第２
ライン出力信号をORゲート32,34を介してメモリ22,24の
▲▼端子に出力する。一方、メモリ22とメモリ24の
偶数番目のビット（データ端子0,2,4,6）を組合わせて
ゲート36を介してROM39のアドレス端子に接続する。ゲ
ート36は、デコーダ25の第２ライン出力信号で選択され
る。

第３ラインの出力も同様に行われる。この場合、メモ
リ22の第２列データの奇数番目ビット（11,13,…）とメ
モリ24の第４列データの奇数番目ビット（31,33,…）と
を組合わせて出力する。このため、メモリ22,24を第３
ライン出力の際に同時に選択するため、デコーダの第３
ライン出力信号をORゲート32,34を介してメモリ22,24の
▲▼端子に出力する。一方、メモリ22とメモリ24の
偶数番目ビット（データ端子0,2,4,6）を組合わせてゲ
ート37を介してROM39のアドレス端子に接続する。ゲー
ト37は、デコーダ25の第３ライン出力信号で選択され
る。

第４ラインの出力も同様に行われる。この場合、メモ
リ21の第１列データの偶数番目ビット（00,02,…）とメ
モリ23の第３列データの偶数番目ビット（20,22,…）と
を組合わせて出力する。このため、メモリ21,23を第４
ライン出力の際に同時に選択するため、デコーダの第４
ライン出力信号をORゲート31,33を介してメモリ21,23の
▲▼端子に出力する。一方、メモリ21とメモリ23の
偶数番目ビット（データ端子0,2,4,6）を組合わせてゲ
ート38を介してROM39のアドレス端子に接続する。ゲー
ト38は、デコーダ25の第４ライン出力信号で選択され
る。

ゲート35〜38から出力されたデータは、ROM39のアド
レス端子に入力される。これに対応して、所定のデータ
入換パターンに該当する場合にはデータ入換パターンが
データバスに出力される。その他の場合は、そのまま出
力される。ROM39には、たとえば第８図に示したような
入換パターンを記憶しておけばよい。本実施例では、１
ラインのデータを８ブロックの単位で読出してデータを
入れ換える。

復調時の１次元/2次元変換部７におけるデータ読出と
データ書込も、以上に説明した書込回路と読出回路を逆
に用いることで可能になる。（但し、ROM39は使用しな
い。） 次に、変形実施例について説明する。本発明に係るデ
ータ圧縮法を用いてデータを再構成して送信した場合、
受信側で元の画像に変換できない通常のファクシミリ装
置を使用していることがありうる。かかる場合でもある
程度画像を再現できることが望ましい。

第３図，第４図のようにドット位置を変換した場合、
黒ドットは、横方向だけでなく、縦方向にも並びやすく
なる。そこで、１次元データへの変換の方式を、第３図
のように縦方向に黒ドットを集中する型ではなく、たと
えば第13図に示すような黒ドットを分散する型を用いる
方がよい。第13図の場合、５段階の濃度０〜４に対応し
て２×２のドットを４×１ドットの１次元データに変換
するとき、第14図のように黒ドットを縦方向に分散する
ように構成する。

第２図の中間調画像について、第13図の方式でデータ
を再構成すると、第15図のように変換される。さらに、
第８図に示した入換え方式を用いると、第16図に示すよ
うに、白黒交互のパターンが少ない画像に再構成でき
る。従って、この再構成画像を圧縮して送信した場合、
そのまま受信側で伸長して１次元/2次元変換部７を用い
ずに再現しても、第９図の黒ドットを集中する型の再構
成画像と比べると、横の白または黒のラインが目立ちに
くくなっている。従って、マクロ的に見ればある程度の
元の画像（第２図）の認識が効果的にできる。

具体的な画像再構成の回路は、第11図と第12図におい
て、デコーダ25の出力からのチップセレクト信号とゲー
トコントロール信号との選び方を変更するだけでよい。

以上では、２×２の濃度パターンを４×１の濃度パタ
ーンに変換する場合について説明したが、一般に、Ｎ×
Ｎドット（Ｎは２以上の整数）の濃度パターンをN²×１
ドットの濃度パターンに変換する場合も同様にデータ再
構成を行えばよい。

本実施例ではファクシミリの場合について説明した
が、その他にも例えばファイリングシステムのように画
像データをメモリに格納する時の圧縮に応用することが
できる。

また１画素の構成がＮ×Ｎ以外（例えば、Ｎ×Ｍや非
矩形のもの）でも同様の処理によって効果を得ることが
できると共に、濃度パターン法に限らず、ディザ法への
応用も可能である。

（発明の効果） １次元の濃度パターンを隣接して中間調画像を再構成
し、さらに、白または黒の孤立点があった場合に、孤立
点がなくなるようにデータを入れ換えるので、白ドット
又は黒ドットがデータ圧縮方向にさらに連続しやすくな
る。従って、通常のデータ圧縮法（MH法など）を用いて
画像データを圧縮してもさらに効率よく圧縮できるよう
になる。

【図面の簡単な説明】

第１図は、２×２ドットの濃度パターンの一例を示す図
である。 第２図は、中間調処理後の画像の一例の図である。 第３図は、画像再構成のための１次元濃度パターンの一
例の図である。 第４図は、２×２濃度パターンと４×１濃度パターンの
対応を示す図である。 第５図は、画像再構成におけるデータ変換位置の対応を
示す図である。 第６図は、第２図の画像の再構成画像の図である。 第７図は、第２図の中間調画像と第６図の中間調画像と
のドットの対応を示す図である。 第８図（ａ），（ｂ），（ｃ）は、それぞれ、データ入
換パターンの図である。 第９図は、データ入換後の再構成画像の図である。 第10図は、ファクシミリ装置のブロック図である。 第11図は、２次元/1次元変換部の書込回路の図である。 第12図は、２次元/1次元変換部の読出回路の図である。 第13図は、画像再構成のための１次元パターンの変形例
の図である。 第14図は、２×２濃度パターンと４×１濃度パターンの
対応を示す図である。 第15図は、再構成画像の変形例の図である。 第16図は、データ入換え後の変形例の図である。 ３……２次元/1次元変換部、 ７……１次元/2次元変換部。

フロントページの続き (72)発明者 中島 昭夫 大阪府大阪市中央区安土町２丁目３番13 号 大阪国際ビル ミノルタカメラ株式 会社内 (58)調査した分野(Int.Cl.⁶，ＤＢ名) H04N 1/41 - 1/419

Claims (2)

(57)【特許請求の範囲】
1. 【請求項１】画像を複数の段階の濃度に対応して画像の
   データ圧縮方向及びその直交方向に複数ドットの広がり
   を有するｍドットからなる２次元濃度パターンにより表
   現し、この表現したｍドットの画像をデータ圧縮方向に
   対して直交する方向にｍドットの広がりを有する１次元
   の濃度パターンに変換し、この１次元濃度パターンをデ
   ータ圧縮方向に隣接して並べ、こうして並べかえた画像
   データについてデータ圧縮方向に連続した所定数のドッ
   トのブロックを参照し、白又は黒の孤立点があった場合
   に孤立点がなくなるようにデータを入れ換え、データ圧
   縮を行うことを特徴とするデータ圧縮法。
2. 【請求項２】前記２次元濃度パターンは、Ｎ×Ｎドッ
   ト、Ｎ×Ｍドット又は非矩形のドットパターンとして構
   成される請求項１記載のデータ圧縮法。