JP2000236448A

JP2000236448A - データ圧縮装置

Info

Publication number: JP2000236448A
Application number: JP11035227A
Authority: JP
Inventors: Masayuki Tanaka; 公幸田中
Original assignee: Oki Data Corp
Current assignee: Oki Electric Industry Co Ltd
Priority date: 1999-02-15
Filing date: 1999-02-15
Publication date: 2000-08-29

Abstract

(57)【要約】【解決手段】画素スキャン部３は、入力装置１から多
値画像データに含まれる各画素値を出力装置２の処理順
に取り出す。パターン変換部は、各画素値に対応する２
値表現された階調パターンを出力する。この階調パター
ンは配列方向に見たとき、例えば黒ラン、白ランが発生
しやすくなるようなパターンにしておく。【効果】多値画像データを階調パターンを用いて２値
化すると、高い圧縮率で圧縮できる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、多値画像データを
受け入れて、これを圧縮し、出力するためのデータ圧縮
装置に関する。

【０００２】

【従来の技術】上位装置で作成された画像データを出力
装置に転送したり、あるいは記憶装置に記憶するような
場合、データ量を縮小するためにデータ圧縮が行われ
る。白または黒の画素のみから構成される２値画像デー
タの圧縮には、ランレングス符号化法、ハフマン符号化
法、ＭＭＲ符号化法等の手法が知られている。

【０００３】ランレングス符号化法では、圧縮対象とな
る画像データの１ラスタライン毎に、連続する白画素ま
たは黒画素の固まり（ラン）を検出する。そして、この
ランの長さ毎に任意の符号を割り当てて、これらの符号
の系列でラスタライン内の全ての画素の並びを記述す
る。頻繁に出現するラン長に対しては短いビットの符号
を割り当て、出現頻度の少ないラン長に対しては長いビ
ットの符号を割り当てる。こうして、１ラスタラインの
データ量を圧縮することができる。こうした技術が、例
えばファクシミリ装置等で広く利用されている。

【０００４】一方、多値画像データの圧縮には、ＪＰＥ
Ｇ方式やZiv−Lempel方式等が知られている。前者は動
画像や静止画像の圧縮に適するが、圧縮後のデータから
圧縮前のデータを完全に再現できない非可逆的な圧縮方
法である。また、後者は、文書等の文字コードデータを
圧縮するのに適する方法である。

【０００５】

【発明が解決しようとする課題】ところで、上記のよう
な従来の技術には、次のような解決すべき課題があっ
た。例えば、上位装置からプリンタに印刷データを伝送
する場合には、印刷データを一時的に圧縮し、プリンタ
で受信後に再び復元するといった方法が採用される。こ
の場合には、可逆的なデータ圧縮が要求される。また、
プリンタに転送する印刷データには、一般に多数の文字
画像が含まれる。写真等の連続階調画像を処理するため
の多値画像データ圧縮方法では、こうした文字画像に対
し画質劣化が目立つという問題がある。また、複雑な演
算処理が必要になり、適用可能な画像のビット長にも制
限がある。

【０００６】そこで、１枚の多値画像を複数枚の２値ビ
ットプレーン画像に分解する。即ち、多値画像の各画素
値の最上位ビットのみを集めたビットプレーン画像、２
番目のビットのみを集めたビットプレーン画像といった
要領で、画素値のビット数分のビットプレーン画像を用
意する。そして、各ビットプレーン画像毎に２値画像デ
ータ圧縮方法を用いて圧縮する。

【０００７】ところが、下位ビットプレーン画像の各ビ
ットはばらつきが大きくなるから、十分な圧縮率が得ら
れないという問題があった。また、ビットプレーン画像
への分解には多くのメモリが必要で、最大階調数即ち画
素値を表すためのビット数も制限を受ける。従って、多
値画像データの圧縮をする場合に、より圧縮率が高く、
最大階調数にも制限を受けない圧縮方法の確立が望まれ
ている。

【０００８】

【課題を解決するための手段】本発明は以上の点を解決
するため次の構成を採用する。〈構成１〉多値画像データに含まれる各画素値を取り出
す画素スキャン部と、この画素スキャン部の出力する画
素値を受け入れて、その画素値に対応する２値表現され
た階調パターンを出力するパターン変換部と、上記パタ
ーン変換部の出力する階調パターンを出力順に配列し
て、配列方向に見た規則性を利用してデータ圧縮をする
データ圧縮部とを備え、上記パターン変換部は、上記配
列方向に見た規則性が大きくなるようにドット配列を選
定した、各画素値に対応する階調パターンを出力するこ
とを特徴とするデータ圧縮装置。

【０００９】〈構成２〉構成１に記載のデータ圧縮装置
において、上記パターン変換部は、上記階調パターンを
出力順に配列したとき、上記配列方向に同種類の画素が
並ぶ確率が高くなるようにドット配列を選定した、各画
素値に対応する階調パターンを出力することを特徴とす
るデータ圧縮装置。

【００１０】〈構成３〉構成１に記載のデータ圧縮装置
において、上記パターン変換部は、上記階調パターンを
出力順に配列したとき、上記配列方向に一定の組み合わ
せのドットが並ぶ確率が高くなるようにドット配列を選
定した、各画素値に対応する階調パターンを選択するこ
とを特徴とするデータ圧縮装置。

【００１１】

【発明の実施の形態】以下、本発明の実施の形態を具体
例を用いて説明する。図１は、本発明のデータ圧縮装置
を示すブロック図である。この装置は、入力装置１から
多値画像データを受け入れて圧縮処理し、出力装置２に
出力するよう構成されている。入力装置１は例えば多値
画像データを生成するアプリケーションや上位装置、出
力装置は、例えば記憶装置やプリンタ等である。この装
置には、画素スキャン部３、パターン変換部４、２値デ
ータ圧縮部５、パターン変換テーブル６が設けられてい
る。パターン変換テーブル６には、図の上部に示すよう
な階調パターン７が記憶されている。

【００１２】この例では、例えば多値画像データの各画
素値は、０から７までの８種類で表現される。この画素
値に対応する２値表現された階調パターンを、パターン
変換テーブル６に記憶する。即ち、パターン変換テーブ
ル６には８種類の階調パターン７が記憶されている。図
の階調パターン７は、３×３マトリクスによって構成さ
れており、各ます目に書き込まれた数値は、画素値が
“１”増加する度に白画素から黒画素に切り替わる画素
の順番を示している。

【００１３】即ち、例えば画素値が“１”の場合には、
図の階調パターン７の右上隅の“１”という数字を記入
した部分のみが黒ドットとなり、他の部分は白ドットと
なる。また、画素値が“２”の場合には、（１）の行で
右上隅と上中央の数値が１，２と書き込まれた部分が黒
ドットとなり、他の部分は白ドットとなる。入力装置１
から順に入力し、画像データ中に順番に配列される上記
のような階調パターン７の配列方向を図の矢印Ａとし
た。

【００１４】この場合に、上記のような階調パターン７
を採用すると、画素値が“３”以上のものは、図の
（１）に示す行の各ドットが全て黒ドットとなる。ま
た、画素値が“７”に満たないものは（３）に示した行
のドットは全て白ドットとなる。従って、このような階
調パターン７が矢印Ａの方向に多数配列されたデータ
は、黒ランや白ランが発生する確率が高い。即ち黒ドッ
トや白ドットが配列方向に連続して並ぶ確率が高い。従
って、これを従来のランレングス法等によってデータ圧
縮すると、高い圧縮率でデータを圧縮することができ
る。

【００１５】図２に、データ圧縮方法と階調パターンの
変形説明図を示す。図２（ａ）は、横一列に並んだ２値
化画像データ８の一例を示す。図に示すように、例えば
長さが“４”の白ラン、長さが“３”の黒ラン、長さが
“５”の黒ラン、長さが“１”の白ランといったデータ
が含まれる場合、図の（ｂ）に示すように、各ラン長に
対し一定の符号５を当てはめる。

【００１６】この（ｂ）に示す例では、ラン長が“１”
の場合の符号語が“００００”、ラン長が１６の場合の
符号語が“１１１１”である。従って、ラン長が長くな
るほど圧縮率が高くなる。このため、上記のような階調
パターン７が、図１に示す矢印Ａの方向に長く配列され
ると、高い圧縮率での圧縮が可能になる。なお、上記の
ような画素が並ぶ確率が高くなるように階調パターンを
選択する方法は、例えば図２（ｃ）〜（ｆ）に示すよう
な変形が可能である。

【００１７】（ｃ）は、図１に示した例と同一である。
（ｄ）は、（ｃ）の丁度左右が反対になった例を示す。
（ｅ）は、（ｃ）の上下を反対にした例で、（ｆ）は
（ｅ）の左右を反対にした例である。いずれの場合にお
いても、図１に示す矢印Ａの方向に階調パターン７が配
列された場合に高い圧縮率を得ることができる。

【００１８】図３には、配列方向の規則性説明図を示
す。この図を用いて、上記のような階調パターンが配列
された場合の圧縮率向上効果を説明する。図に示す元画
像データ１１は、多値画像データの各画素値を数字で示
した構造のものである。これまでの例の通り、１画素の
画素値を０〜７までの範囲に選定している。この各画素
の画素値を上記のように２値階調パターンに変換する
と、図の右側あるいは下側に示すように、各階調パター
ンが配列される。右側はポートレイト形式の用紙に印刷
される画像のイメージデータを示す。

【００１９】各階調パターンは、この例では、Ｘの方向
に順番に配列される。３×３ドットで構成された階調パ
ターンは、それぞれ対応する黒ドットと白ドットの組み
合わせで図に示すように配列されている。この例を見て
分かるように、例えば画素値が５，６，５というように
並ぶ場合、黒ドットがＸ方向に連続する部分と白ドット
がＸ方向に連続する部分が多く存在する。これによっ
て、Ｘ方向に見たデータ圧縮を行うと高い圧縮率でデー
タを圧縮できる。

【００２０】なお、従来、階調パターンは、なるべく黒
ドットの位置を分散させるように設定していた。従っ
て、階調パターンを用いる２値化後のデータは、圧縮率
が極めて低い傾向があった。本発明では、この図に示す
ように階調パターンの配列方向に同種類の画素が並ぶ確
率が高くなるようにドット配列を選定した、圧縮率を高
めている。

【００２１】図の下側に示す用紙１３は、ランドスケー
プ形式の用紙である。このような場合にも、例えば階調
パターンをＹ方向に配列して出力する場合には、このＹ
方向に同一の値の画素が並ぶ確率が高くなるようにドッ
ト配列を選定する。これによって、同様の効果が得られ
る。

【００２２】なお、上記の例では、同一の値の画素が並
ぶ確率が高くなるようにした例を示したが、例えば配列
方向に一定の組み合わせのドットが並ぶ確率が高くなる
ようにしてもよい。即ち、白ドットと黒ドットの組み合
わせから成る一定のパターンが配列方向に見て何回も繰
り返される場合、そのようなパターンの繰り返し状態を
符号化し圧縮するという方法も考えられる。例えば“０
１１”というパターンが繰り返された数に応じて、一定
の符号を決定する。こうしてデータ圧縮することも可能
である。

【００２３】以下、図１に示す装置の各部分の具体的な
動作を説明する。図４は、画素スキャン部３の動作説明
図を示す。画素スキャン部３は、入力装置１から入力す
る信号を出力装置の要求に応じた配列にして取り出し、
これをパターン変換部４に出力する機能を持つ。例え
ば、出力装置が電子写真方式プリンタの場合、図４
（ａ）に示すように、用紙の幅方向に１ラインずつスキ
ャンするようなデータ配列が要求される。即ち、用紙の
幅方向に主走査し、高さ方向に副走査するように、１ラ
イン分ずつデータを取り出して出力する。

【００２４】一方、インクジェットプリンタやドットイ
ンパクトプリンタのような、いわゆるシリアルプリンタ
の場合には、副走査方向に並んだノズル群を持つヘッド
を主走査方向に移動させて印刷を行う。そこで、データ
を供給するための順番は異なってくる。即ち、図４
（ｂ）に示すように、ヘッドの高さに相当する画素デー
タ群を取り出し、この動作を幅方向に順番に繰り返すと
いったスキャンを実行する。ヘッドの高さ分の帯状の画
素データ群を取り出した後は、ヘッドを高さ方向に、丁
度ヘッドの高さ分だけ位置をずらし、同様のスキャンを
実行する。

【００２５】画素スキャン部３は、例えばこのような動
作をして、多値画像データに含まれる各画素値を取り出
してパターン変換部４に転送する。パターン変換部４
は、各画素値に対応する図１に示したような階調パター
ンを出力する。２値データ圧縮部５は、パターン変換部
４から出力された画像データを２値データの集合と見な
し、その２値データの配列方向にデータを圧縮する。

【００２６】図５には、図２に示したパターン変換部４
の動作フローチャートを示す。まず、ステップＳ１にお
いて、画素スキャン部３から読み出すべき画素の座標値
を初期化する。そして、次のステップＳ２において、１
行分の画素の取り込み処理を行う。次のステップＳ３に
おいて、１行ずつ１ページ分の画素読み込みが終了する
までステップＳ２の処理を繰り返す。

【００２７】図６（ａ）には、このステップＳ２のサブ
ルーチンフローチャートを示す。まず、図６のステップ
Ｓ１１において、Ｘ，Ｙの座標値で指定した画素をスキ
ャンし、ステップＳ１２において、その画素値をスキャ
ンメモリへ格納する。スキャンメモリは、図の（ｂ）に
示すように、読み込んだ順番に画素値を配列して記憶し
たメモリである。図には、印刷イメージを考慮して横
Ｘ、縦Ｙの形状のメモリを図示したが、メモリは、実際
には入力された全てのデータをシリアルに連続的に記憶
できればよい。

【００２８】図６ステップＳ１３において、Ｘをインク
リメントし、ステップＳ１４において、１行分のスキャ
ンを終了するまで繰り返し制御を行う。そして、１行分
の処理が終了すると、ステップＳ１５において、Ｘを
“０”に初期化し、Ｙをインクリメントする。こうし
て、図５のステップＳ３に進む。以上の処理によって、
１ページ分の画素値が図６（ｂ）に示すようにスキャン
メモリに記憶されると、図５ステップＳ４において、最
大階調数、画像データ幅及び画像データ高の設定を行
う。そして、ステップＳ５において、Ｘ，Ｙの値を初期
化する。

【００２９】次のステップＳ６では、１行分ずつ画素の
階調パターンへの変換処理を実行する。ステップＳ７
は、この画素の階調パターン変換処理を１ページ分行う
まで、ステップＳ６を繰り返す制御を行う部分である。

【００３０】図７（ａ）には、このような１行画素のパ
ターン化処理サブルーチンフローチャートを示す。図７
において、ステップＳ１６では、スキャンメモリ中の
Ｘ，Ｙに格納した画素値を読み出す。そして、ステップ
Ｓ１７において、読み出した多値画像データをこれまで
説明したような階調パターンに変換し、パターンメモリ
へ格納する。

【００３１】図７（ｂ）は、パターンメモリの構成を説
明し、図に示すように、上記の例では、横３Ｘ、縦３Ｙ
の記憶領域を持つ。なお、この場合にも、メモリは通
常、入力された順にシリアルにデータを取り出すことが
できるようなものであればよく、このように縦横にパタ
ーン化をされている必要はない。各階調パターンの内容
は、これまで説明した通りである。

【００３２】図７ステップＳ１８において、１行分が終
了したかどうかを判断し、全ての画素値について、階調
パターンへの変換を実行する。そして、１行分の処理が
終了すると、ステップＳ２０に進み、Ｘを“０”に初期
化し、Ｙをインクリメントする。このような処理を図５
のステップＳ７の制御によって１ページ分繰り返す。１
ページ分の処理が終了すると、パターン変換部の動作を
終了する。

【００３３】ステップＳ８では、ＸとＹを“０”に初期
化し、ステップＳ１０で、圧縮処理を開始する。この場
合には、図７に示したパターンメモリの上から１行ずつ
圧縮処理を進める。そして、ステップＳ１０で、１ペー
ジ分の繰り返し処理を制御する。図７（ｃ）は、この圧
縮処理のサブルーチンである。

【００３４】図７ステップＳ２１において、パターンメ
モリのＹ行目を呼び出し、ランレングス法によって圧縮
し出力する。ステップＳ２２では、Ｙをインクリメント
する。こうして、Ｙが“０”から最終行に至るまでの圧
縮処理を実行する。

【００３５】以上のような制御を行うことによって、目
的とする２値化された画像データの圧縮が終了する。従
って、例えば図４に示す電子写真方式の場合には、幅方
向の１ライン毎に、インパクト系のプリンタの場合には
ヘッドの長さ分ずつデータの圧縮が行われ、これが図１
に示す出力装置２に向けて出力されることになる。出力
装置２の側では、受け取ったデータを対応するアルゴリ
ズムによって復号化し、更に上記パターン変換部と同様
の階調パターン７を用いて逆変換をすることにより、元
の多値画像データを復元できる。

【００３６】

【発明の効果】以上のように、本発明によれば、多値画
像データに含まれる各画素値を装置の出力順に取り出
し、その画素値に対応する２値表現された階調パターン
を出力し、配列方向に見た規則性が大きくなるように画
素値に対応する階調パターンを選択し、圧縮するように
したので、多値画像データを効率よく、高い圧縮率で圧
縮することが可能になる。また、これによって、パター
ン変換テーブル６の内容を設定するだけで、多値画像デ
ータの最大階調数に影響を受けることなく、高い効率で
データを圧縮し、出力することが可能になる。

【図面の簡単な説明】

【図１】本発明のデータ圧縮装置ブロック図である。

【図２】データ圧縮方法と階調パターンの変形例説明図
である。

【図３】配列方向の規則性説明図である。

【図４】画素スキャン部の動作説明図である。

【図５】パターン変換部以下の動作フローチャートであ
る。

【図６】サブルーチンフローチャート（その１）であ
る。

【図７】サブルーチンフローチャート（その２）であ
る。

【符号の説明】

１入力装置２出力装置３画素スキャン部４パターン変換部５２値データ圧縮部６パターン変換テーブル７階調パターン

Claims

【特許請求の範囲】

【請求項１】多値画像データに含まれる各画素値を取
り出す画素スキャン部と、この画素スキャン部の出力する画素値を受け入れて、そ
の画素値に対応する２値表現された階調パターンを出力
するパターン変換部と、前記パターン変換部の出力する階調パターンを出力順に
配列して、配列方向に見た規則性を利用してデータ圧縮
をするデータ圧縮部とを備え、前記パターン変換部は、前記配列方向に見た規則性が大
きくなるようにドット配列を選定した、各画素値に対応
する階調パターンを出力することを特徴とするデータ圧
縮装置。
【請求項２】請求項１に記載のデータ圧縮装置におい
て、前記パターン変換部は、前記階調パターンを出力順に配
列したとき、前記配列方向に同種類の画素が並ぶ確率が
高くなるようにドット配列を選定した、各画素値に対応
する階調パターンを出力することを特徴とするデータ圧
縮装置。
【請求項３】請求項１に記載のデータ圧縮装置におい
て、前記パターン変換部は、前記階調パターンを出力順に配
列したとき、前記配列方向に一定の組み合わせのドット
が並ぶ確率が高くなるようにドット配列を選定した、各
画素値に対応する階調パターンを選択することを特徴と
するデータ圧縮装置。