JP4008428B2

JP4008428B2 - 画像圧縮方法

Info

Publication number: JP4008428B2
Application number: JP2004130161A
Authority: JP
Inventors: 憲一郎酒井; 嗣男野田
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 2004-04-26
Filing date: 2004-04-26
Publication date: 2007-11-14
Anticipated expiration: 2024-04-26
Also published as: US20050238240A1; JP2005311987A; US7444024B2

Description

本発明は、画像データを圧縮する技術に関する。例えば、コンピュータ上のドキュメントをプリンタから印刷出力する場合に、該ドキュメントのビットマップデータをプリンタに圧縮して転送することで、転送時間の短縮やプリンタの簡素化を可能とする技術に関する。

従来のビットマップ画像の圧縮方法としては、ＭＨ(Modified Huffman)やＭＲ(Modified READ)、ＭＭＲ(Modified Modified READ)、JBIG(Joint Bi-Level Image Experts Group)等があり、ＦＡＸ通信や画像ファイリングに広く使用されている。

これらの圧縮方法はビット処理を多用するなど高速な符号化処理に向かないことから、高速処理を狙ったビットマップデータの圧縮方法及び圧縮装置が提案されている（特許文献１）。

この画像圧縮方法では、図２０（Ａ）のように、入力画像１４２を水平方向に走査して黒画素を含む領域１４６を分離し、この分離した領域を図２０（Ｂ）のように垂直方向に走査して黒画素を含む領域１５２−１〜１５２−３を分離する。

図２０（Ａ）の黒画素を含まない領域１４４−１は垂直方向へのスキップ１４８として符号化し、図２０（Ｂ）の黒画素を含まない領域１５０−１，１５０−２は水平方向へのスキップ１５１−１，１５１−２として符号化する。

分離された黒画素を含む領域１５２−１〜１５２−３は、同一画素値を持つ列が連続する同一列パターン１５４を列の画素値と繰り返し回数により符号化し、それ以外は圧縮できない非圧縮領域として画素値をそのまま符号出力する。

更に図２０（Ｂ）のように分離された黒画素を含む領域１５２−１〜１５２−３の圧縮率を向上させるために、列の画素値が階段状に変化する階段状パターン１５６を圧縮する方法(特許文献２)や、一定の列と幅のパターンが連続して繰り返し出現する反復パターン１５８を圧縮する方法(特許文献３)、更に離散的に出現する同一パターンを圧縮する方法(特許文献４)を提案している。これらの画像圧縮方法を適用した後に残った領域は、圧縮できない非圧縮領域１５７−１〜１５７−４として画素値に非圧縮を示す種別符号語を付けてそのまま符号出力する。

特許第３２７８２９８号公報特開２００３−１９８８５５号公報特開２００３−１８９１０８号公報特開２００３−１９８８５６号公報

しかしながら、このような従来の画像符号化方法では、圧縮できなかった非圧縮領域を
符号出力する際に、他の符号と区別するため非圧縮であることを示す符号語を付加する必要があるため、元データサイズよりもデータ量が増加することがあった。例えば非圧縮領域の画像データがＮバイト、符号語を１バイトとすると元のデータがＮバイトであるのに対し、非圧縮領域の符号データはＮ＋１バイトに増加する。

また，上記のような非圧縮領域は、一般的に列数（幅）が短いものほど出現頻度が高く、列数１の領域の出現頻度を最大として列数の増加に従って出現頻度が減少する傾向がある。即ち、１列程度の非圧縮領域が圧縮可能な領域から孤立して存在することが、比較的高い頻度で発生している。この孤立して存在する列（孤立列）は、例えば最も出現頻度の高い列数１の場合、上述のとおり符号語を付けることで符号サイズが２倍に増加するので、符号化効率を低下させる要因となっていた。

そこで本発明は、高頻度に出現する孤立列の符号化効率を向上させる技術の提供を目的としている。

これらの課題を解決するために本発明は、以下の手段を採用した。即ち、本発明の画像圧縮方法は、
画像を主走査方向と副走査方向の画素の配列で示すビットマップデータを主走査方向に走査する主走査ステップと、
前記主走査結果により、所定行数の論理行単位に、黒画素を含む領域と黒画素を含まない領域とに分離する第１領域分離ステップと、
前記第１領域分離ステップで分離された黒画素を含む領域について副走査方向に走査する副走査ステップと、
前記副走査結果により、所定の符号化パターンに一致する符号化領域と該符号化パターンに一致しない非符号化領域とに分離する第２領域分離ステップと、
前記第２領域分離ステップで分離された非符号化領域の中から、所定の孤立パターンに一致する孤立列を分離する第３領域分離ステップと、
前記第１乃至第３領域分離ステップで分離された各領域を要素として符号化する際、前記孤立列を表す符号および該孤立列に隣接する領域の列数を表す符号を組み合わせて符号化する符号化ステップと、
をコンピュータが実行する。

また、本発明の画像圧縮装置は、
画像を主走査方向と副走査方向の画像の配列で示すビットマップデータを主走査方向に走査することにより、所定行数単位に、黒画素を含む領域と黒画素を含まない領域とに分離する第１領域分離部と、
前記第１領域分離部で分離された黒画素を含む領域について副走査方向に走査することにより、所定の符号化パターンに一致する符号化領域と該符号化パターンに一致しない非符号化領域とに分離する第２領域分離部と、
前記第２領域分離部で分離された非符号化領域の中から、所定の孤立パターンに一致する孤立列を分離する第３領域分離部と、
前記第１乃至第３領域分離部で分離された各領域を要素として符号化する際、前記孤立列を表す符号および該孤立列に隣接する領域の列数を表す符号を組み合わせて符号化する符号化部とを備えた。

このように本発明は、画像を主走査(水平)方向に走査して黒画素を含む領域と黒画素を含まない領域に分離し、黒画素を含む領域を更に副走査(垂直)方向に走査して符号化領域と非符号化領域に分離して分離された各領域を要素として符号化する際に、非圧縮領域として残る領域について、列数が短いほど出現頻度が高く、列数１程度の領域（孤立パター
ン）が高頻度に出現するという特徴に着目し、非圧縮領域から孤立列を分離し、隣接する領域と組み合わせて符号を割り当てることで、短い孤立列を符号化してもデータ量が増えることが無く、圧縮率を高められる。
なお、前記画像圧縮方法及び画像圧縮装置において、前記孤立パターンは、列数１で、且つ全ての行が黒画素或は特定の行が黒画素であっても良く、前記孤立列に隣接する領域は、黒画素を含まない領域であっても良い。

また、前記孤立列が繰り返し出現する場合に、該孤立列を表す符号および該孤立列に隣接する領域の列数を表す符号に加えて、該孤立列の繰り返しの回数を表す符号を組み合わせて符号化しても良い。

このように、該孤立列の繰り返しの回数を表す符号を組み合わせて符号化することにより、繰り返し回数に割当てる符号長を考慮しても少なくとも３回以上「水平スキップ＋孤立列」が繰り返す場合には、繰り返し回数を組み合わせない場合と比べて符号サイズが小さくなる。

また、前記孤立列を分離する際、黒画素を列内に１個だけ含む孤立列を選択的に分離し、前記符号化の際、前記孤立列を表す符号として列内における該黒画素の存在位置を用いて符号化しても良い。

孤立列を表す符号としては、画素値そのものを用いることもできるが、出現頻度の高い孤立列に対象を限定した符号を用いることにより符号サイズをより小さくすることができる。例えば、論理行の行数を８とした場合、画素値そのものを孤立列の符号とすると８ビットが必要になるが、黒画素を１個含む孤立列に特定すれば、図１４に示したように黒画素の位置は８通りであるため、３ビットの数値で符号化することができる。

更に、前記孤立列を分離する際、連続するＮ個（Ｎは１以上の整数）の黒画素のみを含む孤立列を選択的に分離し、前記符号化の際、前記孤立列を表す符号として列内における該黒画素の存在位置および黒画素数を用いて符号化しても良い。
これにより例えば、論理行の行数を８とした場合、図１５に示したように黒画素の位置は最大８通り、また含まれる黒画素数は１個から８個まであるため、両者にそれぞれ３ビットを割り当てて合計６ビットで符号化することができる。

このとき、対象とする黒画素数の最大数を減らすことにより更に符号のビット数を少なくできる。例えば対象を最大４個の連続する黒画素を含む孤立列に制限すると、黒画素数の符号に割り当てるビットは２ビットで済み、黒画素を表す符号の３ビットと加えて合計５ビットで符号化することができる。

また、前記孤立列を分離する際、所定の孤立パターンに一致する画素値を有する孤立列を選択的に分離し、前記符号の際、孤立列を表す符号として該孤立パターンに予め割当てておいた番号を用いて符号化しても良い。

これにより、孤立列の画素パターンの中で出現頻度の高いパターンを選択して各パターンに一意に識別するためのパターン番号を付与し，該パターン番号を符号に用いる。例えば出現頻度の高い３２個のパターンを選択した場合、パターン番号として５ビットの数値で符号化することができる。
また、本発明は、前記画像圧縮方法をコンピュータに実行させる画像圧縮プログラムや、該画像圧縮プログラムをコンピュータで読み取り可能に記録した記録媒体であっても良い。

また、本発明の画像復号方法は、
前記画像圧縮方法で圧縮された圧縮画像データの展開命令を受ける命令受信ステップと、
該圧縮画像データに含まれる符号を、対応する符号化パターンに一致する符号化領域に復号する第１復号化ステップと、
該圧縮画像データに含まれる符号のうち、孤立列を含むことを示す符号に基づいて前記孤立列と該孤立列に隣接する領域に復号する第２復号ステップと、
該圧縮画像データのうち、非符号化領域を識別する第３復号ステップと、
前記第１乃至第３復号ステップで得た各領域を要素として論理行単位に画素の配列を求め、各論理行から求めた画素の配列を合成してビットマップデータを得る合成ステップと、
をコンピュータが実行する。

また、本発明の画像復号装置は、
前記画像圧縮方法で圧縮された圧縮画像データの展開命令を受ける命令受信部と、
該圧縮画像データに含まれる符号を、対応する符号化パターンに一致する符号化領域に復号する第１復号化部と、
該圧縮画像データに含まれる符号のうち、孤立列を含むことを示す符号に基づいて前記孤立列と該孤立列に隣接する領域に復号する第２復号部と、
該圧縮画像データのうち、非符号化領域を識別する第３復号部と、
前記第１乃至第３復号部で得た各領域を要素として論理行単位に画素の配列を求め、各論理行から求めた画素の配列を合成してビットマップデータを得る合成部と、
を備えた。

また、本発明の印刷装置（プリンタ）は、
前記画像圧縮方法で圧縮された圧縮画像データを受信するデータ受信部と、
該圧縮画像データに含まれる符号を、対応する符号化パターンに一致する符号化領域に復号する第１復号化部と、
該圧縮画像データに含まれる符号のうち、孤立列を含むことを示す符号に基づいて前記孤立列と該孤立列に隣接する領域に復号する第２復号部と、
該圧縮画像データのうち、非符号化領域を識別する第３復号部と、
前記第１乃至第３復号部で得た各領域を要素として論理行単位に画素の配列を求め、各論理行から求めた画素の配列を合成してビットマップデータを得る合成部と、
該ビットマップデータに基づいて画像を印刷出力する印刷部と、
を備えた。

また、本発明は、前記画像復号方法をコンピュータに実行させる画像復号プログラムや該画像復号プログラムをコンピュータで読み取り可能に記録した記録媒体であっても良い。
そして、コンピュータに、前記記録媒体のプログラムを読み込ませて実行させることにより、その機能を提供させることができる。

ここで、前記コンピュータで読み取り可能な記録媒体とは、データやプログラム等の情報を電気的、磁気的、光学的、機械的、または化学的作用によって蓄積し、コンピュータから読み取ることができる記録媒体をいう。このような記録媒体の内コンピュータから取り外し可能なものとしては、例えばフレキシブルディスク、光磁気ディスク、CD-ROM、CD-R/W、DVD、DAT、８mmテープ、メモリカード等がある。
また、コンピュータに固定された記録媒体としてハードディスクやＲＯＭ（リードオンリーメモリ）等がある。

本発明は、高頻度に出現する孤立列の符号化効率を向上させる技術を提供できる。

以下、図面を参照して本発明を実施するための最良の形態について説明する。以下の実施の形態の構成は例示であり、本発明は実施の形態の構成に限定されない。

<装置構成>
図１は、本発明の画像圧縮装置としてのコンピュータ１及びプリンタ（印刷装置）２を示した概略図、図２は前記画像圧縮装置１の機能構成を示すブロック図、図３は本発明の画像復号装置を備えるプリンタ２の機能構成を示すブロック図である。
本実施形態においてコンピュータ１は、図１に示すように、ドキュメントを印刷する際、該ドキュメントのビットマップデータを生成し、このビットマップデータを符号化（圧縮）して圧縮画像データとし、該圧縮画像データをプリンタ２に転送する。そして、該圧縮画像データを受信したプリンタ２は、該データを復号化してビットマップデータを得、該ビットマップデータに基づいて印刷を行う。

このように印刷するデータを圧縮して転送することにより、本発明の画像圧縮装置（コンピュータ）１は、該転送時間を短縮している。一方、本発明の印刷装置（プリンタ）２は、プリンタフォントで置き換えたデータではなく、ビットマップデータが直接得られるので、フォントを記憶するＲＯＭ等を備える必要がなく、装置の簡素化が図れる。

本発明の画像圧縮装置は、図２に示すように、ＣＰＵ及びメインメモリ等からなる演算処理部１２や、記憶部（ハードディスク等）１３、入出力部（Ｉ／Ｏ）１４等からなる一般的なコンピュータ（パーソナルコンピュータ）である。

入出力部（Ｉ／Ｏ）１４は、キーボードやマウス、ＣＤ−ＲＯＭドライブ等の入力部、並びにディスプレイやプリンタ２、モデム等の出力部が適宜接続されるインターフェイスである。

記憶部１３は、オペレーティングシステムや、ドキュメントを作成するプログラム、画像を圧縮するための画像圧縮プログラム等のソフトウェアを記憶している。特に本実施形態のコンピュータ１は、該画像圧縮プログラムをプリンタドライバの一部として有している。

演算処理部１２は、記憶部１３に記憶されているプログラムを適宜読み出して実行する。特に本実施形態において演算処理部１２は、画像圧縮プログラムを実行することにより、第１領域分離部や、第２領域分離部、第３領域分離部、符号化部としても機能している。

該第１領域分離部は、画像を主走査方向（本例では水平方向）と副走査方向（本例では垂直方向）の画像の配列で示すビットマップデータを主走査方向に走査することにより、所定行数単位に、黒画素を含む領域と黒画素を含まない領域とに分離する。

また、第２領域分離部は、前記第１領域分離部で分離された黒画素を含む領域について副走査方向に走査することにより、所定の符号化パターンに一致する符号化領域と該符号化パターンに一致しない非符号化領域とに分離する。
第３領域分離部は、前記第２領域分離部で分離された非符号化領域の中から、所定の孤立パターンに一致する孤立列を分離する。

符号化部は、前記第１乃至第３領域分離部で分離された各領域を要素として符号化する際、前記孤立列を表す符号および該孤立列に隣接する領域の列数を表す符号を組み合わせて符号化する。

一方、プリンタ２は、図３に示すように、コンピュータ１から圧縮画像データを受信するデータ受信部２１や、該圧縮画像データを復号化してビットマップデータを得る画像復号装置３、該ビットマップデータに基づいて画像を印刷出力する印刷部２２を備えている。

該画像復号装置３は、ＣＰＵ等からなる演算処理部３２や、記憶部（ＲＡＭ等）３３、入出力部（Ｉ／Ｏ）３４等からなるコンピュータ（マイクロコンピュータ）である。

入出力部（Ｉ／Ｏ）３４は、データ受信部２１からの圧縮画像データを演算処理部３２へ入力すると共に、演算処理部３２からのビットマップデータを印刷部２２へ出力するインターフェイスである。

記憶部３３は、画像を復号するための画像復号プログラム等のソフトウェアを記憶している。また、記憶部３は、復号後のビットマップデータをスプールするためのバッファ（記憶領域）を有している。

演算処理部３２は、記憶部３３に記憶されているソフトウェアを適宜読み出して実行する。特に本実施形態において演算処理部３２は、画像復号プログラムを実行することにより、第１復号化部や、
第２復号部、第３復号部、合成部としても機能している。

該第１復号化部は、圧縮画像データに含まれる符号を、対応する符号化パターンに一致する符号化領域に復号する。
該第２復号部は、圧縮画像データに含まれる符号のうち、孤立列を含むことを示す符号に基づいて前記孤立列と該孤立列に隣接する領域に復号する。

該第３復号部は、圧縮画像データのうち、非符号化領域を識別する。
合成部は、前記第１乃至第３復号部で得た各領域を要素として論理行単位に画素の配列を求め、各論理行から求めた画素の配列を合成してビットマップデータを得る。

本実施形態では、画像圧縮装置１及び画像復号装置３として、ソフトウェアに従って汎用のコンピュータが上記各部の機能を実現する例を示したが、これに限らず、画像圧縮装置１及び画像復号装置３が、各部の機能を実行する専用の電子回路（ハードウェア）から構成された専用の電子機器であっても良い。

〈画像圧縮方法〉
上記構成の画像圧縮装置が画像圧縮プログラムに従って実行する画像圧縮方法について図４〜図６を用いて説明する。なお、本実施形態では、図４に示すように、画像を主走査方向（水平方向）と副走査方向（垂直方向）との画素の配列として表し、主走査方向に連なる画素を行、副走査方向に連なる画素を列と称する。ビットマップデータは、この画像を構成する各画素の値（例えば、二値画像なら、白画素が０、黒画素が１）を当該画素の位置に応じて羅列したものである。本実施形態では、このビットマップデータを１以上の整数Ｌとなる論理行単位に分離して符号化を行う（図５）。この論理行の行数は、任意に設定できるが、コンピュータの処理単位にあわせて８の倍数とするのが望ましい。特に、プリンタでテキスト等を出力する場合には、論理行Ｌ＝８とするのが望ましい。また、この論理行は、画像の解像度によって異ならせても良く、例えば、ビットマップデータが６
００ｄｐｉであればＬ＝８、２４００ｄｐｉであればＬ＝１６のように可変としても良い。

ユーザが、テキストや写真等のドキュメントの印刷を指示すると、コンピュータ１は、該ドキュメントのビットマップデータを作成し、プリンタドライバに含まれる画像圧縮プログラムに従い図６に示すように該ビットマップデータの圧縮を開始し、以下のステップＳ１０１〜Ｓ１１５を実行する。

Ｓ１０１：前処理として画像をブロック単位に分離し、近傍のブロックとＸＯＲした差分画像に置き換える処理を行う。この差分画像に置き換える処理については、後に詳述する。
Ｓ１０２：第一領域分離部は、画像を主走査方向に１行ずつ走査し、黒画素を含む行か、黒画素を含まない行（白ライン）かを識別する（主走査ステップ）。

Ｓ１０３：
ステップＳ１０２で識別した行を上端から順に選択する。
Ｓ１０４：
ステップＳ１０３で選択した行が白ラインか否かを判定し、白ラインであればステップＳ１０５に移行し、そうでなければステップＳ１０６に移行する。

Ｓ１０５：
この白ライン、即ち黒画素を含まない領域を垂直スキップとして分離し、白ラインの行数を用いて符号化する。例えば垂直スキップを示す符号と行数を示す符号を組み合わせた符号とする。

Ｓ１０６：
ステップＳ１０３で選択した行を含めた８行（論理行）を抽出する。即ち黒画素を含む領域を論理行単位で分離する。本例では、上記ステップＳ１０３〜Ｓ１０６が第１領域分離ステップに相当する。

Ｓ１０７：
ステップＳ１０６で抽出した論理行を副走査方向に走査し、黒画素を含む列と黒画素を含まない列を識別し、これらの列を所定の符号化パターンと比較し、この符号化パターンと一致する符号化可能な領域（符号化領域）と該符号化パターンに一致しない非符号化領域（符号化しない領域）とに分離する。例えば、特許第３２７８２９８号公報、特開２００３−１９８８５５号公報、特開２００３−１８９１０８号公報、特開２００３−１９８８５６号公報に記載されているように、予め出現頻度の高い画素値の配列パターンに符号を割り当て、この符号を割り当てたパターン（符号化パターン）と一致した領域を分離する（第２領域分離ステップ）。

Ｓ１０８：
ステップＳ１０７で分離した領域を先頭から順に選択する。

Ｓ１０９：
ステップＳ１０８で選択した領域が、黒画素を含まない全白領域（水平スキップ）の場合には、ステップＳ１１１に移行し、黒画素を含む領域の場合にはステップＳ１１０に移行する。

Ｓ１１０：
従来の符号化方法により符号化を行う。例えば前記公報に記載されているように、黒画
素を含む領域が所定の符号化パターンと一致した場合には、当該符号化パターンに割り当てた符号やその繰返し回数等に符号化する。また、黒画素を含む領域が符号化パターンと一致しない場合には、その画素値を出力する。

Ｓ１１１：
ステップＳ１０８で選択した全白領域の後に孤立列があるか否かを判定する。即ち全白領域の次の領域が非符号化領域で、且つその先頭が所定の孤立パターンと一致するか否かを判定する。この結果、孤立列が存在しない場合には、ステップＳ１１２に移行し、孤立列が存在する場合には、ステップＳ１１３に移行する。

Ｓ１１２：
全白領域をその列数を用いて論理行内の水平スキップとして符号化する。
Ｓ１１３：
全白領域の次の非符号化領域の中から、所定の孤立パターンに一致する孤立列を分離する（第３領域分離ステップ）。

Ｓ１１４：
ステップＳ１１３で分離した孤立列を当該孤立パターンに割り当てた符号に符号化する（符号化ステップ）。

Ｓ１１５：
ステップＳ１０６で抽出した論理行の符号化が終了したか否かを判定し、終了していない場合にはステップＳ１０８に戻り、終了した場合にはステップＳ１１６に移行する。
Ｓ１１６
未処理の行があるか否かを判定し、未処理の行がある場合にはステップＳ１０３に戻り、未処理の行が無い場合には、圧縮処理を終了し、符号化した圧縮画像データを出力する。

〈符号化の詳細説明〉
上記ステップＳ１１０，Ｓ１１２における従来の符号化は、予め符号を割り当てた出現頻度の高い列数２以上の領域についての処理である。即ち、符号を割り当てることで、画素値を羅列するよりもデータ量が少なくなる領域にのみ適用できる。このため従来の符号化により圧縮できなかった部分が図５のように非圧縮領域６１〜６５として残る。

図５のように非圧縮領域６１〜６５として残る列数の出現頻度は、本願発明者による考察によれば図７のようになる。図７は横軸に非圧縮領域の列数を示し、縦軸に出現頻度を表わしている。この図７の特性から明らかなように、非符号化領域の列数の出現頻度は、列数が短いほど出現頻度が高く、列数１の領域の出現頻度が最大となり、列数が長くなるにつれて出現頻度が低下するという特徴がある。

そこで本実施形態では、図７における非圧縮領域の特徴に着目し、非符号化領域の１列を孤立列として分離し、隣接する領域（本例では直前の領域）と組み合わせて符号化することで、圧縮率の向上を図っている。即ち、本実施形態では、孤立パターンを非符号化領域の先頭１列と定めておき、非符号化領域が存在すれば画素パターンにかかわらず、その先頭１列を孤立列としている。なお、孤立パターンは、１列に限らず、複数列としても、所定列数以下で可変としても良い。
この孤立列が存在する場合の符号の割り当て方について、図８〜図１１を用い従来例と本実施形態とを対比させながら詳細に説明する。

図８は従来の符号化方法による符号の割り当て例であり、水平スキップを示す符号CODE
-Aと、孤立列を示す符号CODEC-Bを示している。CODE-Aには水平スキップであることを示す符号識別子と、水平スキップ長とにそれぞれ８ビット（１バイト）を割り当てている。また、CODE-Bには孤立列であることを示す符号識別子と孤立列の画素値にそれぞれ８ビット（１バイト）を割り当てている。これによりCODE-AおよびCODE-Bの符号サイズは共に２バイトとなる。

図９は図８の符号語を論理行の一部に適用した場合の符号例であり，５個の孤立列が符号化される様子を示している。従来の符号化方法による符号データサイズは（２バイト＋２バイト）×５個＝２０バイトとなる。

次に，本発明による符号割り当ての第一の実施例について説明する。
図１０は本発明による符号割り当て例であり、水平スキップと孤立列を組合せた符号を示している。この例では、符号語識別子CODEC-C、水平スキップ長および孤立列の画素値にそれぞれ８ビット（１バイト）を割り当てており、１個の符号サイズは合計で３バイトとなる。

図１１は図９と同じ画像に対して図１０の符号語を適用した場合の符号化の様子を示している。本実施例による符号サイズは３バイト×５個＝１５バイトとなり、従来の符号化方法による符号サイズに比べて２５％小さくなる。

図１２は本発明による符号割り当ての第二の実施例であり、水平スキップと孤立列とその繰り返し回数を組合せた符号を示している。この例では、符号語識別子CODEC-D、繰り返し回数、水平スキップ長および孤立列の画素値にそれぞれ８ビット（１バイト）を割り当てており、１個の符号サイズが２バイト＋２バイト×繰り返し回数となる。
図１３は図８と同じ画像に対して図１１の符号語を適用した場合の符号化の様子を示している。本実施例による符号サイズは２バイト＋２バイト×５回＝１２バイトとなり、従来の符号化方法による符号サイズに比べて４０％小さくなる。

以上説明した本発明による第一および第二の符号割り当ての実施例では各符号に８ビット単位で割り当てているが，これらは８ビットに限定するものではない。例えば符号識別子については他の符号語との兼ね合いでビット長を決めることができ、符号語の種類が少なければより少ないビット長を割り当てることができる。

また，水平スキップ長についても長さに応じてビット長を変えるように構成してもよく、例えば水平スキップ長が１６未満の場合には４ビットで表し、１６以上の場合には８ビットを追加して割り当てることもできる。

さらに孤立列を示す符号についても上記実施例のように画素値そのものを用いる代わりに、黒画素の位置や個数、あるいは所定の画素値を示す番号を符号として用いても良い。
例えば、前記孤立パターンを列内に１個だけ黒画素を含む１列と定めておき、この画素パターンの孤立列を選択的に分離し、前記符号化の際、図１４に示すように前記孤立列を表す符号として列内における該黒画素の存在位置を用いて符号化しても良い。

これにより、論理行の行数を８とした場合、画素値そのものを孤立列の符号とすると８ビットが必要になるが、黒画素を１個含む孤立列に特定すれば、黒画素の位置は８通りであるため、３ビットの数値で符号化することができる。

更に、前記孤立パターンを連続するＮ個（Ｎは１以上の整数）の黒画素のみを含む１列と定めておき、この画素パターンの孤立列を選択的に分離し、前記符号化の際、図１５に示すように前記孤立列を表す符号として列内における該黒画素の存在位置および黒画素数
を用いて符号化しても良い。

これにより、論理行の行数を８とした場合、黒画素の位置は最大８通り、また含まれる黒画素数は１個から８個まであるため、両者にそれぞれ３ビットを割り当てて合計６ビットで符号化することができる。

また、出現頻度が最大となる列数１に含まれる黒画素の画素パターンの出現頻度は、図１６のようになる。このように、ある特定のパターンの出現頻度には偏りが存在するという特徴がある。なお図１６にあっては、画素パターンにおけるビット１となる黒画素の数を出現頻度の対応点の横に数字で表わしている。

そこで、前記孤立列を分離する際、出現頻度の高い所定の孤立パターンに一致する画素値を有する孤立列を選択的に分離し、前記符号の際、孤立列を表す符号として該孤立パターンに予め割当てておいた番号を用いて符号化しても良い。

更に、入力画像は多様で特徴も異なることから、入力画像から得た１列の非圧縮領域の出現頻度を例えば図１７のように求め、この中から出現頻度が高いパターンを孤立パターンとして選択して決定することで、画像ごとに符号化率を高めるに好適な孤立パターンを選択しても良い。

図１７は、図１６の列数１の非圧縮領域の画素値に対する出現頻度について、出現頻度の高い順に参照パターンを登録した参照パターンファイル３０の例であり、パターン番号と出現頻度の高い順に並べられたパターンで構成されている。この参照パターンファイル３０に登録するパターンの数は、パターン番号に割り当てることのできる符号語のビット数に応じて決まることになる。

〈前処理〉
図１８は、本発明の圧縮時における前処理として用いた排他的論理和処理の説明図である。図１８において、処理ブロック７２は、この例では縦横画素Ｍ×Ｎ＝８×８とした場合を例にとっており、現在、処理対象となっている処理ブロック７２に対し、既に処理済のブロックの中から選択された参照ブロック７１との間で排他的論理和（ＸＯＲ）７４をとることにより、差分画像７３を生成している。このような処理ブロック７２と参照ブロック７１の同じ画素位置の画素についての排他的論理和をとった場合には、両ブロックの同一位置の画素値が異なる部分、即ち白画素対黒画素または黒画素対白画素の部分だけが差分画像７３の中に黒画素として残る。このため、グラデーションのようにパターン形状が連続的に変化するディザ画像にあっては、隣接ブロック間の画素値の相関が高く、相関が高いほど差分画像の黒画素は少なくなり、同一画素配置のブロックの場合には差分画像内は全て白画素となり圧縮率を高めることができる。

〈圧縮画像データの復号〉
上記のように符号化された圧縮画像データを受信したプリンタ２は、画像復号装置３で図１９に示すように以下のステップを実行する。
Ｓ２０１：
プリンタ２は、コンピュータ１から前記圧縮画像データを受信すると、該データの展開及び印刷命令の受信とみなし、ステップＳ２０２に移行して復号処理を開始する。

Ｓ２０２：
該圧縮画像データに含まれる符号を、前述の符号化とは逆に対応する符号化パターンと一致する符号化領域に復号する。
Ｓ２０３：
該圧縮画像データに含まれる符号のうち、孤立列を含むことを示す符号に基づいて前記孤立列と該孤立列に隣接する領域に復号する。

Ｓ２０４：
該圧縮画像データのうち、非符号化領域を識別する。
Ｓ２０５：
前記ステップＳ２０１〜Ｓ２０４で得た各領域を要素として論理行単位に画素の配列を求め、各論理行から求めた画素の配列を合成してビットマップデータを得る。
プリンタ２は、画像復号装置３で復号した該ビットマップデータを印刷部２２に送り、該ビットマップデータに基づいて印刷部２２で印刷を行う。

以上説明したように、本実施形態のビットマップデータの圧縮方法によれば、従来別々に符号化を行なっていた水平スキップと孤立列をまとめて符号化することで圧縮率を高めることがでる。このため，印刷画像の圧縮データサイズが削減されてプリンタへの転送時間が短くなり、印刷を指示してから終了までの印刷時間を短縮でき、プリンタの使い勝手の向上に寄与する。

なお、本発明において、各画素の値を便宜上白画素（第一の画素値）又は黒画素（第二の画素値）と称したが、これは白と黒に限定されるものではなく、二種類の画素値であれば良い。

また、この二種類の画素値とは、二値に限定するものではなく、例えば０とそれ以外（１〜２５４）のように、多値であっても良い。
更に、本発明は、複数色（例えば赤色、緑色、青色）のビットマップデータでカラー画像を構成する場合の各色のビットマップデータに適用しても良い。

〈その他の実施形態〉
本発明は、上述の図示例にのみ限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変更を加え得ることは勿論である。
例えば、以下に付記した構成であっても上述の実施形態と同様の効果が得られる。また、下記の構成は可能な限り組み合わせることができる。

（付記１）
画像を主走査方向と副走査方向の画素の配列で示すビットマップデータを主走査方向に走査する主走査ステップと、
前記主走査結果により、所定行数の論理行単位に、黒画素を含む領域と黒画素を含まない領域とに分離する第１領域分離ステップと、
前記第１領域分離ステップで分離された黒画素を含む領域について副走査方向に走査する副走査ステップと、
前記副走査結果により、所定の符号化パターンに一致する符号化領域と該符号化パターンに一致しない非符号化領域とに分離する第２領域分離ステップと、
前記第２領域分離ステップで分離された非符号化領域の中から、所定の孤立パターンに一致する孤立列を分離する第３領域分離ステップと、
前記第１乃至第３領域分離ステップで分離された各領域を要素として符号化する際、前記孤立列を表す符号および該孤立列に隣接する領域の列数を表す符号を組み合わせて符号
化する符号化ステップと、
をコンピュータが実行する画像圧縮方法。（１）

（付記２）
前記孤立パターンは、列数１で、且つ全ての行が黒画素或は特定の行が黒画素である付記１に記載の画像圧縮方法。

（付記３）
前記孤立列に隣接する領域が、黒画素を含まない領域である付記１に記載の画像圧縮方法。

（付記４）
前記符号化ステップにて、前記孤立列が繰り返し出現する場合に、該孤立列を表す符号および該孤立列に隣接する領域の列数を表す符号に加えて、該孤立列の繰り返しの回数を表す符号を組み合わせて符号化する付記１に記載の画像圧縮方法。

（付記５）
前記第３の領域分離ステップにて、黒画素を列内に１個だけ含む孤立列を選択的に分離し、
前記符号化ステップにて、前記孤立列を表す符号として列内における該黒画素の存在位置を用いて符号化する付記１に記載の画像圧縮方法。

（付記６）
前記第３の領域分離ステップにて、連続するＮ個（Ｎは１以上の整数）の黒画素のみを含む孤立列を選択的に分離し、
前記符号化ステップにて、前記孤立列を表す符号として列内における該黒画素の存在位置および黒画素数を用いて符号化する付記１に記載の画像圧縮方法。

（付記７）
前記第３の領域分離ステップにて、所定の孤立パターンに一致する画素値を有する孤立列を選択的に分離し、
前記符号化ステップにて、孤立列を表す符号として該孤立パターンに予め割当てておいた番号を用いて符号化する付記１に記載の画像圧縮方法。

（付記８）
画像を主走査方向と副走査方向の画像の配列で示すビットマップデータを主走査方向に走査することにより、所定行数単位に、黒画素を含む領域と黒画素を含まない領域とに分離する第１領域分離部と、
前記第１領域分離部で分離された黒画素を含む領域について副走査方向に走査することにより、所定の符号化パターンに一致する符号化領域と該符号化パターンに一致しない非符号化領域とに分離する第２領域分離部と、
前記第２領域分離部で分離された非符号化領域の中から、所定の孤立パターンに一致する孤立列を分離する第３領域分離部と、
前記第１乃至第３領域分離部で分離された各領域を要素として符号化する際、前記孤立列を表す符号および該孤立列に隣接する領域の列数を表す符号を組み合わせて符号化する符号化部と、
を備えたことを特徴とする画像圧縮装置。（２）

（付記９）
前記孤立パターンは、列数１で、且つ全ての行が黒画素或は特定の行が黒画素である付
記８に記載の画像圧縮装置。

（付記１０）
前記孤立列に隣接する領域が、黒画素を含まない領域である付記８に記載の画像圧縮装置。

（付記１１）
前記符号化部が、前記孤立列が繰り返し出現する場合に、該孤立列を表す符号および該孤立列に隣接する領域の列数を表す符号に加えて、該孤立列の繰り返しの回数を表す符号を組み合わせて符号化する付記８に記載の画像圧縮装置。

（付記１２）
前記第３の領域分離部が、黒画素を列内に１個だけ含む孤立列を選択的に分離し、
前記符号化部が、前記孤立列を表す符号として列内における該黒画素の存在位置を用いて符号化する付記８に記載の画像圧縮装置。

（付記１３）
前記第３の領域分離部が、連続するＮ個（Ｎは１以上の整数）の黒画素のみを含む孤立列を選択的に分離し、
前記符号化部が、前記孤立列を表す符号として列内における該黒画素の存在位置および黒画素数を用いて符号化する付記８に記載の画像圧縮装置。

（付記１４）
前記第３の領域分離部が、所定の孤立パターンに一致する画素値を有する孤立列を選択的に分離し、
前記符号化部が、孤立列を表す符号として該孤立パターンに予め割当てておいた番号を用いて符号化する付記８に記載の画像圧縮装置。

（付記１５）
画像を主走査方向と副走査方向の画素の配列で示すビットマップデータを主走査方向に走査する主走査ステップと、
前記主走査結果により、所定行数の論理行単位に、黒画素を含む領域と黒画素を含まない領域とに分離する第１領域分離ステップと、
前記第１領域分離ステップで分離された黒画素を含む領域について副走査方向に走査する副走査ステップと、
前記副走査結果により、所定の符号化パターンに一致する符号化領域と該符号化パターンに一致しない非符号化領域とに分離する第２領域分離ステップと、
前記第２領域分離ステップで分離された非符号化領域の中から、所定の孤立パターンに一致する孤立列を分離する第３領域分離ステップと、
前記第１乃至第３領域分離ステップで分離された各領域を要素として符号化する際、前記孤立列を表す符号および該孤立列に隣接する領域の列数を表す符号を組み合わせて符号化する符号化ステップと、
をコンピュータに実行させる画像圧縮プログラム。（３）

（付記１６）
前記孤立パターンは、列数１で、且つ全ての行が黒画素或は特定の行が黒画素である付記１５に記載の画像圧縮プログラム。

（付記１７）
前記孤立列に隣接する領域が、黒画素を含まない領域である付記１５に記載の画像圧縮
プログラム。

（付記１８）
前記符号化ステップにて、前記孤立列が繰り返し出現する場合に、該孤立列を表す符号および該孤立列に隣接する領域の列数を表す符号に加えて、該孤立列の繰り返しの回数を表す符号を組み合わせて符号化する付記１５に記載の画像圧縮プログラム。

（付記１９）
前記第３の領域分離ステップにて、黒画素を列内に１個だけ含む孤立列を選択的に分離し、
前記符号化ステップにて、前記孤立列を表す符号として列内における該黒画素の存在位置を用いて符号化する付記１５に記載の画像圧縮プログラム。

（付記２０）
前記第３の領域分離ステップにて、連続するＮ個（Ｎは１以上の整数）の黒画素のみを含む孤立列を選択的に分離し、
前記符号化ステップにて、前記孤立列を表す符号として列内における該黒画素の存在位置および黒画素数を用いて符号化する付記１５に記載の画像圧縮プログラム。

（付記２１）
前記第３の領域分離ステップにて、所定の孤立パターンに一致する画素値を有する孤立列を選択的に分離し、
前記符号化ステップにて、孤立列を表す符号として該孤立パターンに予め割当てておいた番号を用いて符号化する付記１５に記載の画像圧縮プログラム。

（付記２２）
付記１から７の何れかに記載の画像圧縮方法で圧縮された圧縮画像データの展開命令を受ける命令受信ステップと、
該圧縮画像データに含まれる符号を、対応する符号化パターンに一致する符号化領域に復号する第１復号化ステップと、
該圧縮画像データに含まれる符号のうち、孤立列を含むことを示す符号に基づいて前記孤立列と該孤立列に隣接する領域に復号する第２復号ステップと、
該圧縮画像データのうち、非符号化領域を識別する第３復号ステップと、
前記第１乃至第３復号ステップで得た各領域を要素として論理行単位に画素の配列を求め、各論理行から求めた画素の配列を合成してビットマップデータを得る合成ステップと、
をコンピュータが実行する画像復号方法。（４）

（付記２３）
付記１から７の何れかに記載の画像圧縮方法で圧縮された圧縮画像データの展開命令を受ける命令受信部と、
該圧縮画像データに含まれる符号を、対応する符号化パターンに一致する符号化領域に復号する第１復号化部と、
該圧縮画像データに含まれる符号のうち、孤立列を含むことを示す符号に基づいて前記孤立列と該孤立列に隣接する領域に復号する第２復号部と、
該圧縮画像データのうち、非符号化領域を識別する第３復号部と、
前記第１乃至第３復号部で得た各領域を要素として論理行単位に画素の配列を求め、各論理行から求めた画素の配列を合成してビットマップデータを得る合成部と、
を備えた画像復号装置。（５）

（付記２４）
付記１から７の何れかに記載の画像圧縮方法で圧縮された圧縮画像データを受信するデータ受信部と、
該圧縮画像データに含まれる符号を、対応する符号化パターンに一致する符号化領域に復号する第１復号化部と、
該圧縮画像データに含まれる符号のうち、孤立列を含むことを示す符号に基づいて前記孤立列と該孤立列に隣接する領域に復号する第２復号部と、
該圧縮画像データのうち、非符号化領域を識別する第３復号部と、
前記第１乃至第３復号部で得た各領域を要素として論理行単位に画素の配列を求め、各論理行から求めた画素の配列を合成してビットマップデータを得る合成部と、
該ビットマップデータに基づいて画像を印刷出力する印刷部と、
を備えた印刷装置。

（付記２５）
付記１から７の何れかに記載の画像圧縮方法で圧縮された圧縮画像データの展開命令を受ける命令受信ステップと、
該圧縮画像データに含まれる符号を、対応する符号化パターンに一致する符号化領域に復号する第１復号化ステップと、
該圧縮画像データに含まれる符号のうち、孤立列を含むことを示す符号に基づいて前記孤立列と該孤立列に隣接する領域に復号する第２復号ステップと、
該圧縮画像データのうち、非符号化領域を識別する第３復号ステップと、
前記第１乃至第３復号ステップで得た各領域を要素として論理行単位に画素の配列を求め、各論理行から求めた画素の配列を合成してビットマップデータを得る合成ステップと、
をコンピュータに実行させる画像復号プログラム。

本発明は、印刷させる画像の圧縮に限らず、表示装置に表示させる画像データや、記憶装置に記憶させる画像データの圧縮に利用可能である。例えば、画像を携帯電話に送信して表示させる際に、ビットマップデータを圧縮して送信することで、通信時間や通信コストを削減できる。

本発明の概略図画像圧縮装置のブロック図印刷装置のブロック図ビットマップデータの模式図論理行の模式図圧縮処理の説明図非圧縮領域の列数と出現頻度の一般的傾向を示す図従来の符号語例を示す図従来の符号化方法による符号データの説明図本発明の符号語例１を示す図本発明の符号化方法による符号データの説明図本発明の符号語例２を示す図本発明の符号化方法による符号データの説明図１個の黒画素を含む孤立列内の黒画素位置の説明図Ｎ個の黒画素を含む孤立列内の黒画素位置及び黒画素数の説明図列数１の非圧縮領域の画素値と出現頻度との関係を示した分布図出現頻度の高い順に参照パターンを登録した参照パターンファイルの説明図前処理（ＸＯＲ処理）の説明図画像復号方法の説明図従来の符号化の説明図

符号の説明

１コンピュータ（画像圧縮装置）
２プリンタ（印刷装置）
３画像復号装置
１２演算処理部
１３記憶部（ハードディスク等）
１４入出力部（Ｉ／Ｏ）
２１データ受信部
２２印刷部
３２演算処理部
３３記憶部（ＲＡＭ等）
３４入出力部（Ｉ／Ｏ）

Claims

画像を第一又は第二の画素値をとる画素の主走査方向と副走査方向の配列で示すビットマップデータを主走査方向に走査する主走査ステップと、
前記主走査結果により、所定行数の論理行単位に、前記第二の画素値をとる画素である黒画素を含む領域と黒画素を含まない領域とに分離する第１領域分離ステップと、
前記第１領域分離ステップで分離された黒画素を含む領域について副走査方向に走査する副走査ステップと、
前記副走査結果により、所定の符号化パターンに一致する符号化領域と該符号化パターンに一致しない非符号化領域とに分離する第２領域分離ステップと、
前記第２領域分離ステップで分離された非符号化領域の中から、所定の孤立パターンに一致する孤立列を分離する第３領域分離ステップと、
前記第１乃至第３領域分離ステップで分離された各領域を要素として符号化する際、前記孤立列の画素値のパターンを表す符号および該孤立列の主走査方向に隣接する領域の列数を表す符号を組み合わせて符号化する符号化ステップと、
をコンピュータが実行する画像圧縮方法。
画像を第一又は第二の画素値をとる画素の主走査方向と副走査方向の配列で示すビットマップデータを主走査方向に走査することにより、所定行数の論理行単位に、前記第二の画素値をとる画素である黒画素を含む領域と黒画素を含まない領域とに分離する第１領域分離部と、
前記第１領域分離部で分離された黒画素を含む領域について副走査方向に走査することにより、所定の符号化パターンに一致する符号化領域と該符号化パターンに一致しない非符号化領域とに分離する第２領域分離部と、
前記第２領域分離部で分離された非符号化領域の中から、所定の孤立パターンに一致する孤立列を分離する第３領域分離部と、
前記第１乃至第３領域分離部で分離された各領域を要素として符号化する際、前記孤立列の画素値のパターンを表す符号および該孤立列の主走査方向に隣接する領域の列数を表す符号を組み合わせて符号化する符号化部と、
を備えたことを特徴とする画像圧縮装置。
画像を第一又は第二の画素値をとる画素の主走査方向と副走査方向の配列で示すビットマップデータを主走査方向に走査する主走査ステップと、
前記主走査結果により、所定行数の論理行単位に、前記第二の画素値をとる画素である黒画素を含む領域と黒画素を含まない領域とに分離する第１領域分離ステップと、
前記第１領域分離ステップで分離された黒画素を含む領域について副走査方向に走査する副走査ステップと、
前記副走査結果により、所定の符号化パターンに一致する符号化領域と該符号化パターンに一致しない非符号化領域とに分離する第２領域分離ステップと、
前記第２領域分離ステップで分離された非符号化領域の中から、所定の孤立パターンに一致する孤立列を分離する第３領域分離ステップと、
前記第１乃至第３領域分離ステップで分離された各領域を要素として符号化する際、前記孤立列の画素値のパターンを表す符号および該孤立列の主走査方向に隣接する領域の列数を表す符号を組み合わせて符号化する符号化ステップと、
をコンピュータに実行させる画像圧縮プログラム。
請求項１に記載の画像圧縮方法で圧縮された圧縮画像データの展開命令を受ける命令受信ステップと、
該圧縮画像データに含まれる符号を、対応する符号化パターンに一致する符号化領域に復号する第１復号ステップと、
該圧縮画像データに含まれる符号のうち、孤立列を含むことを示す符号に基づいて前記
孤立列と該孤立列に隣接する領域に復号する第２復号ステップと、
該圧縮画像データのうち、非符号化領域を識別する第３復号ステップと、
前記第１乃至第３復号ステップで得た各領域を要素として論理行単位に画素の配列を求め、各論理行から求めた画素の配列を合成してビットマップデータを得る合成ステップと、をコンピュータが実行する画像復号方法。
請求項１に記載の画像圧縮方法で圧縮された圧縮画像データの展開命令を受ける命令受信部と、
該圧縮画像データに含まれる符号を、対応する符号化パターンに一致する符号化領域に復号する第１復号化部と、
該圧縮画像データに含まれる符号のうち、孤立列を含むことを示す符号に基づいて前記孤立列と該孤立列に隣接する領域に復号する第２復号部と、
該圧縮画像データのうち、非符号化領域を識別する第３復号部と、
前記第１乃至第３復号部で得た各領域を要素として論理行単位に画素の配列を求め、各論理行から求めた画素の配列を合成してビットマップデータを得る合成部と、
を備えた画像復号装置。