(57)【特許請求の範囲】
【請求項１】
ｍ×ｎハーフトーンマトリックス、および画像内の第１のｍ×ｎピクセルブロックに基づいて、コンピュータにより、前記第１のｍ×ｎピクセルブロックの、第１のｍ×ｎのハーフトーン処理されたバージョンを決定する工程と、
前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎのハーフトーン処理されたバージョンの複数の行に対してｎ箇所の交互配置工程（ｎ−ｗａｙ  ｉｎｔｅｒｌｅａｖｅ）を行い、第１のｍｎ×１のハーフトーンセグメントを生成する工程と、
前記第１のｍｎ×１のハーフトーンセグメントを、ＦＩＦＯ（Ｆｉｒｓｔ  ｉｎ  Ｆｉｒｓｔ  ｏｕｔ）バッファの一つ以上のハーフトーンセグメントと比較する工程と、
前記第１のｍｎ×１のハーフトーンセグメントが、ＦＩＦＯバッファのいずれのハーフトーンセグメントにもマッチングしない場合、（ｉ）リテラルコードワードと、前記第１のｍｎ×１のハーフトーンセグメントの表現を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの前記表現を前記ＦＩＦＯバッファに書き込む工程と、
前記第１のｍｎ×１のハーフトーンセグメントがＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングする場合、（ｉ）リピートコードワードおよびリピート値を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現をＦＩＦＯバッファに書き込む工程と、を含む、方法。
【請求項２】
前記第１のｍｎ×１のハーフトーンセグメントは、ｋ−１の他のハーフトーンセグメントと共に、ルックアヘッドバッファに保存されており、
ｊ−１≧ｋの他のｍｎ×１のハーフトーンセグメントは、ＦＩＦＯバッファ内の前記特定のハーフトーンセグメントにマッチングし、
前記ｊのマッチングするハーフトーンセグメントは、少なくとも前記ルックアヘッドバッファに隣接しており、
前記リピート値はｊの指標であり、
前記第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの前記表現をＦＩＦＯバッファに書き込む工程は、ＦＩＦＯバッファに、ｊの前記第１のｍｎ×１のハーフトーンセグメントを書き込む工程を含む、請求項１に記載の方法。
【請求項３】
前記ｋ―１の他のｍｎ×１のハーフトーンセグメントは、前記画像の他のｍ×ｎピクセルブロックから得られる、請求項２に記載の方法。
【請求項４】
前記ｊのマッチングするハーフトーンセグメントを前記ルックアヘッドバッファから削除する工程をさらに含む、請求項２に記載の方法。
【請求項５】
前記リピートコードワードはショートリピートコードワードまたは拡張リピートコードワードである、請求項２に記載の方法。
【請求項６】
ｊをｋと比較する工程と、
ｊ＜ｋである場合、前記リピートコードワードとして、ショートリピートコードワードを用いる工程と、
ｊ≧ｋである場合、前記リピートコードワードとして、拡張リピートコードワードを使用する工程と、をさらに含む、請求項５に記載の方法。
【請求項７】
前記拡張リピートコードワードは、前記リピートコードワードであり、
前記方法は、
前記第１のｍｎ×１のハーフトーンセグメントのｊの前記表現を前記ＦＩＦＯバッファに書き込む工程の後に、前記ルックアヘッドバッファ内の少なくとも１つのエントリを第２のｍｎ×１のハーフトーンセグメントと置換する工程であって、前記第２のｍｎ×１のハーフトーンセグメントは、前記画像の第２のｍ×ｎピクセルブロックから得られる工程をさらに含む、請求項６に記載の方法。
【請求項８】
前記第１のｍｎ×１のハーフトーンセグメントを、前記ＦＩＦＯバッファの前記１以上のハーフトーンセグメントと比較する前記工程は、前記第１のｍｎ×１のハーフトーンセグメントにマッチする、ＦＩＦＯバッファ内の最も長く連続するハーフトーンセグメントと、前記第１のｍｎ×１のハーフトーンセグメントに隣接して続いている任意の他のハーフトーンセグメントを決定する工程を含む、請求項１から請求項７のいずれか１つに記載の方法。
【請求項９】
前記第１のｍｎ×１のハーフトーンセグメントは、前記ＦＩＦＯバッファ内の前記特定のハーフトーンセグメントにマッチングしており、
前記ＦＩＦＯバッファ内の前記特定のハーフトーンセグメントの位置の指標である、リピート位置を出力する工程をさらに含む、請求項１から８のいずれか１つに記載の方法。
【請求項１０】
前記ｍ×ｎハーフトーンマトリックスの各セルは、ｉ―１の閾値を含み、
前記ｉ―１の閾値は、ｉの画素値の範囲を定義し、
前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎのハーフトーン処理されたバージョンの各セルは、ｌｏｇ２（ｉ）のビット値を含む、請求項１から９のいずれか１つに記載の方法。
【請求項１１】
前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎのハーフトーン処理されたバージョンを決定する工程は、前記第１のｍ×ｎピクセルブロックの各特定のセルについて、
前記第１のｍ×ｎピクセルブロックの前記特定のセルの特定のピクセル値を決定する工程と、
前記ｍ×ｎハーフトーンマトリックスの特定のセル内における、ｉの画素値範囲のうちの１つが、前記特定の画素値を含んでいると決定する工程であって、前記第１のｍ×ｎピクセルブロックの前記特定のセルは、前記ｍ×ｎハーフトーンマトリックスの前記特定のセルに対応している、工程と、
前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎのハーフトーン処理されたバージョンの特定のセルに対し、前記決定された前記ｉの画素値範囲のうちの１つを表すｌｏｇ２（ｉ）ビットの値を書き込む工程と、
を含む、請求項１０に記載の方法。
【請求項１２】
前記第１のｍ×ｎのピクセルブロックの前記第１のｍ×ｎのハーフトーン処理されたバージョンを決定する工程は、
前記ｍ×ｎハーフトーンマトリックスの縦に連続するタイルの初期位置がｑピクセルのオフセットを呈するように、前記画像上に前記ｍ×ｎハーフトーンマトリックスを割り当てる工程を含み、
前記方法は、
前記画像の最も右の列に、ｒ１×ｎのパディング画素列を追加する工程をさらに含む、請求項１から１１のいずれか１つに記載の方法。
【請求項１３】
ｐは、前記ｒ１×ｎのパディング画素列を追加する工程の前における、前記画像の画素値での幅であり、ｒはｍ―（ｐ―ｑ）ｍｏｄ  ｍ  である、請求項１２に記載の方法。
【請求項１４】
コンピュータプログラムであって、
ｍ×ｎハーフトーンマトリックス、および、第１のｍ×ｎのピクセルブロックに基づいて、コンピュータにより、前記第１のｍ×ｎピクセルブロックの第１のｍ×ｎのハーフトーン処理されたバージョンを決定する工程と、
前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎのハーフトーン処理されたバージョンの複数の行に対して、ｎ箇所の交互配置工程を施して、第１のｍｎ×１のハーフトーンセグメントを作成する工程と、
前記第１のｍｎ×１のハーフトーンセグメントを、ファーストインファーストアウトバッファ（ＦＩＦＯバッファ）内の１以上のハーフトーンセグメントと比較する工程と、
前記第１のｍｎ×１のハーフトーンセグメントが、前記ＦＩＦＯバッファ内の任意のハーフトーンセグメントにマッチングしない場合、（ｉ）リテラルコードワードおよび第１のｍｎ×１のハーフトーンセグメントの表現を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの表現を前記ＦＩＦＯバッファに書き込む工程と、
前記第１のｍｎ×１のハーフトーンセグメントが、前記ＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングする場合、（ｉ）リピートコードワードおよびリピート値を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現を前記ＦＩＦＯバッファに書き込む工程と、を含む動作をコンピュータに実行させるコンピュータプログラム。
【請求項１５】
前記第１のｍｎ×１のハーフトーンセグメントが、ｋ−１の他のｍｎ×１のハーフトーンセグメントと共にルックアヘッドバッファに格納されており、
ｊ−１≧ｋの他のハーフトーンセグメントも、前記ＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングし、
前記ｊのマッチングするハーフトーンセグメントは、前記ルックアヘッドバッファ内において隣接し、
前記リピート値はｊを示し、
前記第１のｍｎ×１のハーフトーンセグメントの前記少なくとも１つの表現を前記ＦＩＦＯバッファに書き込む工程は、前記第１のｍｎ×１のハーフトーンセグメントのｊの表現を前記ＦＩＦＯバッファに書き込む工程を含む、請求項１４に記載のコンピュータプログラム。
【請求項１６】
前記リピートコードワードがショートリピートコードワードまたは拡張リピートコードワードである、請求項１５に記載のコンピュータプログラム。
【請求項１７】
前記動作は、
ｊをｋと比較する工程と、
ｊ＜ｋである場合に、前記リピートコードワードとして前記ショートリピートコードワードを用い、
ｊ≧ｋである場合、前記リピートコードワードとして前記拡張リピートコードワードを用いる工程と、をさらに含む、請求項１６に記載のコンピュータプログラム。
【請求項１８】
前記拡張リピートコードワードは、前記リピートコードワードであり、
前記動作は、
前記第１のｍｎ×１のハーフトーンセグメントのｊの表現をＦＩＦＯバッファに書き込む工程の後に、前記ルックアヘッドバッファ内の少なくとも１つのエントリを、第２のｍｎ×１のハーフトーンセグメントに置換する工程であって、前記第２のｍｎ×１のハーフトーンセグメントは、画像の第２のｍ×ｎピクセルブロックから得られる、工程をさらに含む、請求項１６に記載のコンピュータプログラム。
【請求項１９】
プロセッサと、
データ記憶装置と、
前記データ記憶装置に記憶され、プロセッサによる実行において、コンピュータに、請求項１から請求項１３のいずれか１つに記載の方法の動作を実行させる、プログラム命令と、を備えるコンピュータ。
【請求項２０】
コンピュータによる実行において、コンピュータに請求項１から請求項１３のいずれか１つに記載の方法の動作を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はハーフトーンのデジタル画像の圧縮方法に関する。
【背景技術】
【０００２】
ハーフトーン処理は、サイズ、形状または間隔において異なる複数のドットを用いることにより、連続した色調のイメージをシミュレーションする技術である。これらの、基本的な２値（バイナリ）のハーフトーン処理の単一のトーンレベルの複数のドットにより、中間調のドットパターンを形成する。中間調のドットパターンを適切に設計することによって、単一のトーンレベルのオン／オフ動作のマーキングを介して、複数の色調（トーン）および滑らかなシェーディング（濃淡）がハーフトーンの画像に表示される。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】ＵＳ２００７／０１１６３６７
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、ハーフトーン処理されたデジタル画像の圧縮方法を提供する。
【課題を解決するための手段】
【０００５】
例示の実施形態において、ｍ×ｎのハーフトーンマトリックスおよび画像の第１のｍ×ｎピクセルブロックに基づいて、第１のｍ×ｎピクセルブロックの第１のｍ×ｎハーフトーンバージョンが、決定されてもよい。ｎ箇所のインターリーブが、第１のｍｎ×１ハーフトーンセグメントを作成するために、第１のｍ×ｎのピクセルブロックの第１のｍ×ｎハーフトーンバージョンの行に実行されてもよい。第１のｍｎ×１のハーフトーンセグメントは、ファーストインファーストアウト（ＦＩＦＯ）バッファの１つ以上のハーフトーンセグメントと比較されてもよい。第１のｍｎ×１のハーフトーンセグメントがＦＩＦＯバッファのいずれのハーフトーンセグメントにもマッチングしない場合、リテラルコードワードおよび第１のｍｎ×１のハーフトーンセグメントの表現が出力されてもよく、第１のｍｎ×１のハーフトーンセグメントの表現が、ＦＩＦＯバッファに書き込まれてもよい。第１のｍｎ×１のハーフトーンセグメントがＦＩＦＯバッファの特定のハーフトーンセグメントにマッチングする場合、リピートコードワードおよびリピート値が出力されてもよく、そして、第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現が、ＦＩＦＯバッファに書き込まれてもよい。
【０００６】
追加の実施形態は、コンピュータによる実行に応じて、コンピュータに上記の、または他の例示の実施形態における動作を実行させるプログラム命令を格納した非一時的コンピュータ読み取り可能な記録媒体を含んでいてもよい。
【０００７】
さらなる実施形態は、少なくとも１つのプロセッサと、データ格納部と、コンピュータによる実行に応じて、コンピュータに上記の、または他の例示の実施形態における動作を実行させる、データ収納部に格納されたプログラム命令を含むコンピュータを含んでいてもよい。
【０００８】
さらに他の実施形態は、コンピュータによる実行に応じて、コンピュータに上記の例示の実施形態の少なくとも１つに従って動作を実行させるプログラムを含んでいてもよい。
【０００９】
必要に応じて添付の図面を参照して示される以下の詳細な説明を読むことによって、これら、および同様の他の態様、利点および変形例が、当業者にとって明らかになる。更に、この概要およびこの文書の他の部分で提供される説明は実施例により請求項に記載の構成を説明することが意図され、限定を目的とするものではないことを理解されたい。
【発明の効果】
【００１０】
本発明によれば、ハーフトーン処理されたデジタル画像の圧縮方法が提供される。
【図面の簡単な説明】
【００１１】
【図１】図１は、例示の実施形態における印刷装置を表す。
【図２】図２は、例示の実施形態における、印刷装置のコンピュータの構成要素を示すブロック図である。
【図３】図３は、例示の実施形態における、印刷装置に関する様々なデータ経路を例示するブロック図である。
【図４】図４は、例示の実施形態における、画像中の画素への、ハーフトーンマトリックスの適用を表す図である。
【図５Ａ】図５Ａは、例示の実施形態における、画像上に適用されるハーフトーンマトリックスを表す図である。
【図５Ｂ】図５Ｂは、例示の実施形態における、画像上に列を追加して適用されるハーフトーンマトリックスを表す図である。
【図６】図６は、例示の実施形態における、画像及び前記画像の拡大された部分を表す図である。
【図７】図７は、例示の実施形態における、列を追加する画像のハーフトーン処理を表す図である。
【図８】図８は、例示の実施形態における、ハーフトーン処理された画像の一部の１６進数による表現を表す図である。
【図９】図９は、例示の実施形態における、ハーフトーン処理された画像に対する交互配置（インターリービング（ｉｎｔｅｒｌｅａｖｉｎｇ））を表す図である。
【図１０】図１０は、例示の実施形態における、ヒストリーバッファ、ルックアヘッドバッファ、および新しいセグメントバッファを表す図である。
【図１１】図１１は、例示の実施形態における、圧縮後のハーフトーン処理されたセグメントのフォーマットを表す図である。
【図１２】図１２は、例示の実施形態におけるフローチャートである。
【図１３】図１３は、例示の実施形態において、前記ルックアップバッファ内のセグメントに対しマッチングが見出されなかった場合における、前記ヒストリバッファ、前記ルックアヘッドバッファ、および新しいセグメントバッファの動作を表す図である。
【図１４】図１４は、例示の実施形態において、前記ルックアップバッファ内の２つのセグメントに対しマッチングが見出された場合における、前記ヒストリバッファ、前記ルックアヘッドバッファ、および新しいセグメントバッファの動作を表す図である。
【図１５】図１５は、例示の実施形態において、前記ルックアップバッファ内の複数のセグメントに対しマッチングが見出された場合における、前記ヒストリバッファ、前記ルックアヘッドバッファ、および新しいセグメントバッファの動作を表す図である。
【図１６】図１６は、例示の実施形態において、前記ルックアップバッファ内の１つのセグメントに対しマッチングが見出された場合における、前記ヒストリバッファ、前記ルックアヘッドバッファ、および新しいセグメントバッファの動作を表す図である。
【図１７】図１７は、例示の実施形態において、列の追加が実行により、前記ルックアップバッファ内の３つのセグメントに対しマッチングが見出された場合における、前記ヒストリバッファ、前記ルックアヘッドバッファ、および新しいセグメントバッファの動作を表す図である。
【図１８】図１８は、例示の実施形態において、前記ルックアップバッファおよび前記新しいセグメントバッファ内の全てのセグメントに対しマッチングが見出され、拡張されたリピートコードワードの使用が促進される場合における、前記ヒストリバッファ、前記ルックアヘッドバッファ、および新しいセグメントバッファの動作を表す図である。
【図１９】図１９Ａ、１９Ｂ、１９Ｃ、および１９Ｄは、列の追加の使用により、より効果的にハーフトーン画像圧縮が可能となるというシナリオを表す図である。
【図２０】図２０は、例示の実施形態におけるフローチャートである。
【発明を実施するための形態】
【００１２】
以下、例示の実施形態における方法および装置が、本願明細書において説明される。他の例示の実施形態または特徴が、本願明細書において提示される主題の範囲および精神を逸脱しない範囲で、さらに利用されてもよい。以下の詳細な説明においては、添付の図面が参照され、その図面は詳細な説明の一部を構成する。
【００１３】
本願明細書において記載されている例示の実施形態は、限定を意図したものではない。一般的に本願明細書において記載され、図示されているように、本発明の態様が多種多様な異なる構成において配置される、置換される、結合される、分離される、そして設計されることができることが理解され、その全ては本願明細書において明確に考察される。
１．イントロダクション
印刷技術は、白黒の画像だけを形成する単純なドットマトリクスベースの出力装置から高解像度のカラー画像を形成することができる今日の高度なレーザーベースの印刷装置まで、最近の３０年ほどで進化してきている。さらに、最新の印刷装置は、複写機、スキャナ、およびファックスとして機能することもできる。そのために、これらの装置は、印刷またはファックスするためにキューイングされる、または、走査された多数の電子文書を格納することが可能となっていることがある。このように、多くの印刷装置は、例えば、一つ以上のプロセッサ、データ格納部、および入出力インタフェースを含むことができるコンピュータの特別な形態である。
【００１４】
印刷装置が、住宅において、ビジネスにおいて、または、他の種類の場所において用いられるかどうかにかかわらず、印刷装置は様々な他のコンピュータに通信可能な状態で接続されることができる共用されたリソースであってもよい。従って、ある環境においては、多数のコンピュータが、印刷するための電子文書を印刷装置に発信することができるようになるにつれて、印刷装置の記憶容量に対する要件が非常になってくる。一般に、印刷装置は、先着順の方法で、一度に１つの電子文書を印刷、複製、ファックス、および／またはスキャンする。従って、印刷装置は、潜在的に、処理されるために待っているかなりの数の電子文書を格納することができる。データ格納部（例えば、ランダムアクセスメモリ（ＲＡＭ）、ソリッドステートメモリ、ハードディスクメモリ、および／またはフラッシュメモリ等のメモリ）のコストが高価でありえるので、印刷装置のデータ格納部において必要とされる容量を減らすことを目的として、格納された電子文書を圧縮することは有益でもよい。加えて、いくつかの電子文書が印刷装置およびコンピュータに、および／またはそれから送信されることができるので、これらの電子文書を圧縮することは転送をより速くすることができ、また、使用するネットワーク容量を少なくすることができる。
【００１５】
さらに、印刷ジョブが大きくなることがある（例えば、印刷ジョブは数百ページも含んでいる１または複数の電子文書を含むことがある）ので、各ジョブが印刷される前に、キューに入れられた印刷ジョブを圧縮することは短期記憶領域を節約することができる。加えて、ユーザは、後ほど印刷するために長期間記憶装置の印刷ジョブを保存したいと考えることがある。したがって、印刷ジョブを圧縮することによって、より多くの印刷ジョブを保存するることができる。さらにまた、長期記憶からサイズの大きい印刷ジョブを格納あるいは引き出しは遅くなることがあるが、印刷ジョブを圧縮し、サイズを小さくすることによって、迅速に処理することが可能となる。
２．例示の実施形態の印刷装置
図１は、例示の実施形態における印刷装置１００を示す。印刷装置１００は、部分的に格納された、および／または全体が格納された電子文書を様々な形の物理的な出力メディアに印刷するように構成されていてもよい。これらの出力メディアは、紙、ＯＨＰの透光性のスライド、その他の様々なサイズおよびタイプを含むが、これに限定されるものではない。印刷装置１００は、「プリンタ」と呼ばれてもよい。
【００１６】
印刷装置１００は、パーソナルコンピュータ、サーバ装置、プリントサーバ等のコンピュータに対するローカル周辺機器として機能することができる。これらの場合には、印刷装置１００は、例えばシリアルポートケーブル、パラレルポートケーブル、ユニバーサルシリアルバス（ＵＳＢ）ケーブル、Ｆｉｒｅｗｉｒｅ（ＩＥＥＥ  １３９４）ケーブル、またはＨｉｇｈ―Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ（ＨＤＭＩ）ケーブル等のケーブルにより、コンピュータに取り付けられてもよい。このように、コンピュータは、印刷装置１００のための電子文書の出所（ソース（ｓｏｕｒｃｅ））としての機能を果たすことができる。
【００１７】
一方、印刷装置１００は、例えばイーサネットまたは８０２．１１の（Ｗｉｆｉ）インタフェースのような、有線または無線のネットワークインタフェースを含んでいてもよい。このように配置されることにより、印刷装置１００は、ネットワークの上の印刷装置１００と通信することができる任意の数のコンピュータ用の印刷装置として機能することができる。いくつかの実施形態においては、印刷装置１００は、同時に、ローカル周辺機器およびネットワーク上のプリンタとしての機能を果たすことができる。
【００１８】
印刷装置１００を使用するために、コンピュータは、１つ以上のプリンタドライバをインストールしてもよい。これらのプリンタドライバは、印刷される電子文書を、コンピュータに格納される様々なローカルな表現から、印刷装置１００によってサポートされる１つ以上の表現に、変換するソフトウェア構成要素を含んでいてもよい。
【００１９】
これらにかかわらず、印刷装置１００は、コンピュータであると考慮されてもよく、印刷に関連する、および印刷に関連しない作業を実行してもよい。
【００２０】
上記の如く、印刷装置１００は、複写機能、ファックス機能、およびスキャナ機能を含んでいてもよい。いくつかの実施形態においては、複写機および／またはファックス機能を促進することを目的として、印刷装置１００は、スキャナ機能を使用してもよい。例えば、印刷装置１００は、物理的な文書を電子的なフォーマットにするようにスキャンすることができて、そしてそれから、結果として得られる電子文書を印刷してコピーとしての機能を提供し、および／または電話インターフェースを介して結果として得られる電子文書を送信してファックスとしての機能を提供することができる。
【００２１】
その様々な機能をサポートするために、印刷装置１００は、ドキュメントフィーダ／排出トレイ１０２、用紙収容部１０４、ユーザインタフェース１０６、スキャナー素子１０８、および筐体１１０を含んでいてもよい。印刷装置は多種多様な形態をとり得ることができる。従って、印刷装置１００は、図１において表されるより多くであるかあるいはより少しの構成要素を含んでいてもよく、および／または、図１において表されるのとは異なる方法で構成要素が配置されていてもよい。
【００２２】
ドキュメントフィーダ／排出トレイ１０２は、スキャンされることになっているか、複製されることになっているかまたは、ファックスされることになっている物理的な文書（例えば、１枚以上の紙の束）を保持することができる。好ましくは、ドキュメントフィーダ／排出トレイ１０２により、ユーザの手動作業を必要とすることなく、印刷装置１００によって処理される複数の物理的な文書を自動的に供給することができてもよい。ドキュメントフィーダ／排出トレイ１０２は、また、印刷装置１００によって処理された物理的な文書を保持するための１つ以上の独立の排出トレイを含んでいてもよい。これらは、例えば、印刷装置１００のファックスおよび／またはコピー機能によって形成された物理的な文書と同様に、印刷装置１００によってスキャンされたか、コピーされたか、またはファックスされた物理的な文書を含んでいてもよい。
【００２３】
用紙カセット１０４は、様々な形態の物理的なメディア用のトレイおよび／または供給部を含んでいてもよい。例えば、用紙カセット１０４は、８  １／２×１１インチの用紙、Ａ４紙、レターヘッド紙、封筒、その他について、別々のトレイを含んでいてもよい。物理的なメディアを出力する（例えば、印刷、複製、および／またはファックスを受け取る）印刷装置１００のいかなる機能のためにも、用紙カセット１０４は、物理的なメディアを供給することができる。
【００２４】
ユーザインタフェース１０６は、例えばユーザからの入力の受け取りや、出力をユーザへの供給のような、人間または人間以外のユーザと、印刷装置１００との相互作用を促進することができる。このように、ユーザ・インタフェース１０６は、例えばキーパッド、キーボード、タッチセンシティブまたはプレゼンスセンシティブのパネル、ジョイスティック、マイクロホン、スチールカメラおよび／またはビデオ・カメラのような、入力素子を含んでいてもよい。ユーザインタフェース１０６は、また、例えば、ディスプレイスクリーン（例えば、プレゼンスセンシティブなパネルと組み合わされてもよい）、陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）、発光ダイオード（ＬＥＤ）ベースのディスプレイ、デジタルライトプロセッシング（ＤＬＰ（登録商標））を使用するディスプレイ技術、電球、および／または１つ以上の他の類似の、現在知られているあるいは今後開発される装置等の、１つ以上の出力素子を含んでいてもよい。ユーザインタフェース１０６は、また、スピーカ、スピーカ・ジャッキ、オーディオ出力ポート、オーディオ出力デバイス、イヤホン、および／または他の類似の、現在公知であるかまたは将来開発される装置を介して、聞き取り可能な出力を生成することが可能に構成されていてもよい。
【００２５】
スキャナ素子１０８は、ガラスパネルであってもよく、ガラスパネルの下側においては、移動可能な光源が、ガラスパネル上に配置される物理的なメディアをスキャンするために作動してもよい。
あるいは、ガラスパネルの下側に配置されたデジタルカメラが、物理的なメディアの画像を撮影することによって、ガラスパネルの上に配置される物理的なメディアを「走査」してもよい。走査された物理的なメディアの画像は、印刷装置１００と関連したデータ格納部に格納されてもよい。
【００２６】
筐体１１０は、例えばドキュメントフィーダ／排出トレイ１０２、用紙カセット１０４、ユーザインタフェース１０６、およびスキャナ素子１０８のような、印刷装置１００の種々の構成要素を包含する、および／または相互接続する物理的なハウジングを含んでいてもよい。加えて、筐体１１０は、図１に示されない他の構成要素を格納していてもよい。例えば、筐体１１０は、１つ以上のトナーカートリッジ、液体インクジェット、ベルト、ローラー、および／または電源を含んでいてもよい。更に、筐体１１０は、例えば有線および／または無線のネットワークインタフェース、電話通信インタフェース（例えば、ＲＪ４５ジャッキ）、ＵＳＢインターフェース、ＢＬＵＥＴＯＯＴＨ（登録商標）インタフェース、カード読取りポートなどのコミュニケーションインターフェースを含んでいてもよい。
【００２７】
印刷装置１００は、汎用の、および／または特別に設計されたコンピュータの構成要素に基づいていてもよいので、筐体１１０は、これらの構成要素のいくつかあるいは全てを含んでいてもよい。その点に関して、図２は、印刷装置１００に含まれることができるコンピュータ装置の構成要素２００（例えば、コンピュータの機能素子）の例示の実施形態を示す。
【００２８】
コンピュータ装置の構成要素２００は、プロセッサ２０２、データ格納部２０４、および入出力機能素子２０６を含んでいてもよく、その全てはシステムバス２０８または類似の機構によって連結されていてもよい。プロセッサ２０２は、例えば１つ以上の汎用プロセッサおよび／または１つ以上の専用プロセッサ（例えば、特定用途向け集積回路（ＡＳＩＣ）またはデジタル信号プロセッサ（ＤＳＰ）、その他））のような、１つ以上の中央演算処理装置（ＣＰＵ）を含んでいてもよい。
【００２９】
次に、データ格納部２０４は、揮発性および／または不揮発性のデータ格納部を含んでいてもよく、全体的にあるいは部分的にプロセッサ２０２と統合されていてもよい。データ格納部２０４は、プロセッサ２０２によって実行可能なプログラム命令を含んでいてもよく、本願明細書において記載されているさまざまな方法、プロセス、または機能を実行するこれらの命令によって操作されるデータを格納していてもよい。あるいは、これらの方法、プロセス、または機能は、ハードウェア、ファームウェア、および／またはハードウェア、ファームウェアおよびソフトウェアの任意の組合せによっても定義されることができる。従って、データ格納部２０４は、１つ以上のプロセッサによる実行に応じて、本願明細書または添付の図面に開示されている任意の方法、プロセス、または機能を印刷装置１００に実行させる、プログラム命令を格納している有形の、非一時的なコンピュータ読み取り可能な記録媒体を含んでいてもよい。
【００３０】
入出力機能２０６は、ユーザインタフェース１０６に関して記載されている任意の機能および／または構成要素を含んでいてもよい。このように、入出力機能２０６は、プロセッサ２０２の動作を構成し、および／または制御する役割を果たしていてよい。入出力機能２０６は、プロセッサ２０２によって実行される動作に基づいて、出力を提供してもよい。
【００３１】
印刷装置のこれらの実施形態は、説明の便宜上設けられていることを理解されたい。更に、これらに加えておよび／または代えて、上記の実施形態に、本願明細書における実施形態の要旨を逸脱しない範囲で、他の可能な、プリンタおよびコンピュータ技術の他の組合せおよび／または補足的な組合せが、存在してもよい。
【００３２】
図３は、印刷装置１００によって処理される電子文書の表現が通信されることができる可能なデータ経路のいくつかを示す。図３においては、印刷装置１００は、スキャナー機能３０２および印刷機能３０４を含んでいると仮定されている。これらの機能の各々は、ハードウェア、ファームウェア、ソフトウェア、またはハードウェア、ファームウェアおよび／またはソフトウェアの任意の組合せで実行することができる。加えて、スキャン機能３０２および印刷機能３０４の各々は、コンピュータ３００に通信することができ、そしておそらく他のコンピュータにも通信することができる。いくつかの場合において、印刷装置１００でサポートされるデータ経路は、「パイプライン」と称されることもある。
【００３３】
スキャン−プリントデータ経路３１０は、スキャン機能３０２および印刷機能３０４によってサポートされていてもよい。スキャン−プリントデータ経路３１０は、例えば、ユーザが印刷装置１００に物理的な文書を複製するように指示する場合に使われることができる。この指示に応答して、スキャン機能３０２は、物理的な文書を電子文書にスキャンすることができ、電子文書を印刷機能３０４に、スキャン−プリントデータ経路３１０を介して送信することができる。スキャン−プリントデータ経路３１０を使用することにより、少なくとも一時的に、電子文書の一部もしくは全部を印刷装置１００のデータ格納部に格納してもよい。それから、印刷機能３０４は、物理的なメディア（例えば、１つ以上の用紙）に、電子文書を印刷することができる。
【００３４】
スキャン−ホストデータ経路３０６は、スキャン機能３０２およびコンピュータ３００によってサポートされてもよい。スキャン−ホストデータ経路３０６は、例えば、ユーザが印刷装置１００に物理的な文書をスキャンするように指示する際に使われることができる。ユーザは、印刷装置１００に、結果として生じる電子文書の表現をコンピュータ１００に送信するように指示することもできるし、または、自動的に電子文書をコンピュータ３００に送信するように、印刷装置１００が予め設定されていてもよい。このように、この指示に応答して、スキャン機能３０２は、物理的な文書を電子文書にスキャンすることができ、コンピュータ３００にスキャン−ホストデータ経路３０６を介して、結果として生じる電子文書を送信することができる。スキャン−プリントデータ経路３１０の使用により、少なくとも一時的に、電子文書の一部もしくは全部を印刷装置１００のデータ格納部に格納して、結果として生じる電子文書の表現をコンピュータ３００に送信してもよい。
【００３５】
ホスト−プリントデータ経路３０８は、コンピュータ３００および印刷機能３０４によってサポートされていてもよい。ホスト−プリントデータ経路３０８は、ユーザが、コンピュータ３００に電子文書を印刷装置１００に印刷するように指示する際に使われてもよい。この指示に応答して、コンピュータ３００は、電子文書の表現を印刷機能３０４に送信してもよい。印刷装置１００は、印刷機能３０４を介して、物理的な媒体に電子文書を印刷することができる。電子文書を印刷する前におよび／または印刷する間、電子文書の一部もしくは全部が、印刷装置１００のデータ格納部に格納されてもよい。
【００３６】
明らかに、印刷装置１００でサポートされる他のデータ経路と恐らく同様に、上述したデータ経路のうちの少なくとも１つに対し、電子文書が、ネットワークまたはケーブル上の記憶および／または送信が必要となってもよい。電子文書の蓄積および／または送信の効率は、これらの電子文書を圧縮することによって改善されることができる。例えば、電子文書が、平均して、初期のサイズの１／４のサイズに圧縮されることができる場合、データ格納部内の一定の容量において、約４倍の電子文書を格納することができる。更に、圧縮されていない電子文書の送信する場合に比べ、ネットワークまたはケーブルの上において、これらの圧縮された電子文書を、約４倍の速さで送信することが可能となりうる。
【００３７】
以下、印刷装置１００によって処理される電子文書の圧縮を提供する各種実施形態を説明する。
３．例示の実施形態の画像のカラーモデル
電子文書は、多くのカラーモデルを使用して表現されることができる。従って、有効な圧縮技術が、これらのモデルの一部もしくは全部に作用することが可能であるべきである。更に、ハーフトーン圧縮が、個々のカラーモデルに特有であってもよいし、あるいはカラーモデルの各チャネルに別に作用することができてもよい。
【００３８】
例えば、赤―緑―青（ＲＧＢ）のカラーモデルが、例えばテレビ、モニタ、およびコンピュータスクリーンのような電子出力装置上の画像の表示に用いられてもよい。ＲＧＢは、可視光域の色を表現する様々な方法において、赤色光、緑色光、および青色光が互いに足し合わされる加法混色のカラーモデルである。例えば、シアンは緑および青を混合することによって表現することができ、黄色は赤および緑を混合することによって表現することができ、マゼンタは赤および青を混合することによって表現することができ、白は、赤・緑・青を混合することによって表現されることができる。
【００３９】
ＲＧＢ画像における画素は、３つのチャネルのタプル（Ｒ，Ｇ，Ｂ）として表されることができる。各チャネルはゼロから所定の最大値（例えば、２５５）まで変化することができる。もし、チャネルの全てがゼロである場合、黒が表現されてもよい。チャネルの全てが最大値である場合、再現可能な最も明るい白が表現されてもよい。
【００４０】
異なる出力装置においては、同じＲＧＢ画像を異なる方式により表示することができるという点で、ＲＧＢの出力は典型的にはデバイスに依存する。ある場合には、これらの違いは、人間によって知覚されることがある。いくつかの実施形態においては、スキャン−ホストデータ経路３０６を使用して印刷装置１００にスキャンされる物理的な文書が、ＲＧＢカラーモデルを使用して符号化されることができる。
【００４１】
シアン・マゼンタの黄色（ＣＭＹ）カラーモデルが、印刷装置によって色画像を印刷するために用いられることができる。ＣＭＹは、可視光域の色を表現する様々な方法において、白色表面上に、シアン、イエローおよびマゼンタが付与される減法混色のカラーモデルである。例えば、赤はマゼンタおよびイエローを混合することによって表現することができ、青はシアンおよびマゼンタを混合させることによって表現することができ、そして、緑はシアンおよびイエローを混合することによって表現することができる。このように、ＣＭＹカラーモデルは、ＲＧＢカラーモデルを補うもの（補色の関係にある）と考えてもよい。
【００４２】
ＣＭＹ画像における画素は３つのチャネルのタプル（Ｃ，Ｍ，Ｙ）として表されることができる。そして、各チャネルはゼロから所定の最大値まで変化することができる。ャネルの全てがゼロである場合、白が表現されてもよい。チャネルの全てが最大値である場合、黒が表現されてもよい。
【００４３】
ＲＧＢカラーモデルと同様に、同じＣＭＹの画像が、異なる印刷装置上では、異なるように見える可能性があるという点で、ＣＭＹ出力は、典型的には、デバイスに依存する。ある場合には、これらの違いは、人間によって知覚される可能性がある。いくつかの実施形態においては、ホスト−プリントデータ経路３０８および／またはスキャン−プリントデータ経路３１０を使用している印刷装置１００によって印刷される電子文書が、ＣＭＹカラーモデルを使用して符号化されることができる。
【００４４】
いくつかの実施形態では、４つのチャネルを用いるＣＭＹＫカラーモデルが用いられることもできる。この４つのチャネルを用いたＣＭＹＫカラーモデルは、キー（ｋｅｙ）チャネル（黒チャネル）も使われるという点以外、ＣＭＹカラーモデルとほぼ同様または同じであってもよい。黒を形成するためにシアン、マゼンタおよび黄色を混合することに加えて、別のキーの（黒の）インク源が、黒を形成するために用いられることができる。このように、ＣＭＹＫ画像の画素は４つのチャネルのタプル（Ｃ，Ｍ，Ｙ，Ｋ）として表することができ、各チャネルはゼロから所定の最大値まで変化することができる。
【００４５】
ＣＭＹＫカラーモデルを使用して、ＣＭＹモデルと同じ色がサポートされることができるが、Ｋの色剤がＣ、ＭおよびＹの色剤の混合物と置き換えることができるので、典型的には、色剤（インク）の使用量をより少なくすることができる。しかしながら、ＣＭＹＫカラーモデルの、他のカラーモデルへの変換や、他のカラーモデルからの変換は、必ずしも都合よくは可能とならないことがある。なぜなら、Ｋの色剤の追加により、例えば、同じ色がＣ、Ｍ、ＹおよびＫの異なる組合せにより表現できることから、冗長性が付加される可能性があるからである。
【００４６】
他のカラーモデルはグレー（中間調）、または、グレースケールとも呼ばれ、モノクロの画像の表現に使われることができる。ＲＧＢおよびＣＭＹ／ＣＭＹＫカラーモデルとは異なり、グレースケールカラーモデルの各画素は、画素の強度を符号化する単一のチャネルを使用して表される。グレーチャネルによって使用される値は、黒に対応するゼロから、白（例えば、２５５）に対応する所定の最大値まで、変化することができる。いくつかの実施形態では、印刷装置１００でサポートされる１つ以上のデータ経路において、グレースケールのカラーモデルを使用して、画像を符号化することが可能となってもよい。
【００４７】
他のカラーモデルとしては、例えばＹＣｂＣｒがある。ある実施態様においては、このカラーモデルが、画像の代替の表現として用いられることができる。具体的には、Ｙチャネルは画素の輝度を表し、ＣｂおよびＣｒチャネルが、それぞれ、青−黄クロミナンス（ｂｌｕｅ−ｙｅｌｌｏｗ  ｃｈｒｏｍｉｎａｎｃｅ）および赤−緑クロミナンス（ｒｅｄ−ｂｌｕｅ  ｃｈｒｏｍｉｎａｎｃｅ）を表すことができる。ＹＣｂＣｒカラーモデルは、ＲＧＢカラーモデルおよびＣＭＹカラーモデルとの関係性が明確であり、比較的容易に、これらのカラーモデルからの変換およびこれらのカラーモデルへの変換が可能である。
【００４８】
ＹＣｂＣｒカラーモデルに対する更なる利点としては、ＹＣｂＣｒカラーモデルを用いて符号化される画像の圧縮は、ＲＧＢまたはＣＭＹ／ＣＭＹＫカラーモデルを用いて符号化される画像の圧縮より効率的であるという傾向がある点がある。特に、人間の眼は、画像における高周波（例えば、急速に変化する）成分のクロミナンスに関する情報の検知が得意ではない。従って、ＣｂおよびＣｒチャネルの高周波成分を無視することによっても、ＹＣｂＣｒカラーモデルを用いて符号化された画像は、この情報（クロミナンスの情報）を十分に利用したものとすることができる。このように、以下に詳述するように、特定のカラーモデルに符号化される画像は、圧縮のパフォーマンスを向上させる目的で、圧縮の前にＹＣｂＣｒカラーモデルに変換されてもよい。
４．例示の実施形態の画像ハーフトーン処理
多くのデジタル画像は、画像の色またはグレイスケールの部分がより明るいトーンからより暗いトーンまで滑らかに移行する、あるいは逆の関係になる連続する色調を含んでいてもよい。しかしながら、多くのプリンタは、連続する色調をサポートしていない。その代わりに、プリンタは、最も明るいトーンから最も暗いトーンまでの離散的な数のトーンをサポートしていてもよい。例えば、単純な白黒のプリンタは、画像の任意の注目ピクセルに対し、黒または白のいずれかの出力だけをサポートしていてもよい。
【００４９】
ハーフトーン処理は、連続階調の画像を複数のパターンの画素の濃淡に解体し、滑らかに移行するグレーまたはカラーの錯覚的な表現を生成する方法を含む。本願明細書においては、「画像」という用語が完全な画像（ｆｕｌｌ  ｉｍａｇｅ）または画像ブロックのような部分的な画像を指すことがある。下記の実施形態のいくつかにおいては、簡単のために、動作は、完全な画像よりもむしろ画像ブロックについて例示される。
【００５０】
ハーフトーンマトリックスはｍ×ｎブロックのセルであってもよく、そして、各セルが１つ以上の閾値を含んでいてもよい。ハーフトーンマトリックスを画像に適用するときには、ハーフトーンマトリックスは、画像の各画素が適用されたハーフトーンマトリックスのうちの１つにあるセルと、それぞれ対応付けられるように、画像に適用される。ハーフトーンマトリックスは、特定のプリンタの特性に基づいて定義されることができ、従って、出力装置固有であってもよい。ハーフトーンマトリックスは、ハーフトーンスクリーン、閾値テーブル、またはディザテーブルと称されてもよい。
【００５１】
画像の各画素は、画素に対するハーフトーン値を決定する目的で、その対応するセルの閾値と比較されてもよい。例えば、ある特定のカラーチャネルにおいて、画素は、０―２５５の、例えばその画素の強度または輝度を表す値を呈していてもよい。対応付けられているセルは、３つの閾値、６４、１２８および２４０を含んでいてもよく、これにより４つの範囲：０―６４、６５―１２８、１２９―２４０および２４１―２５５が定義されてもよい。画素の値はこれらの範囲のうちの１つに該当し、画素が該当する範囲により、画素のハーフトーン値が定義されてもよい。従って、画素のハーフトーン値は、２ビットの値によって定義されることができる。例えば、００は０―６４の範囲を示し、０１は範囲６５―１２８の範囲を示し、１０は１２９―２４０の範囲を示し、そして、１１は２４１―２５５の範囲を示していてもよい。
【００５２】
より形式的には、ハーフトーンマトリックス内の各セルに対して定められる閾値がある場合、これらの閾値はｉの範囲を定めることができ、そして、画素値が該当する範囲は、ｌｏｇ２（ｉ）のビット値によって表されることができる。画像の各画素にハーフトーンマトリックスを適用することにより、各画素がｌｏｇ２（ｉ）ビット値によって表される画像のハーフトーンバージョンが得られてもよい。それから、このハーフトーン処理された画像は、ｉの色調をサポートするプリンタに送られてもよい。
【００５３】
このプロセスは、図４に図示される。画像の画素マトリックス４００は、多くの個々の画素を含み、各々が８ビット値（すなわち、０―２５５）を呈する例示の画素４０２および４０４を含む。ハーフトーンマトリックス４０６は、各々が１５の閾値（すなわち、０−２５５の全体の範囲内において、０から１５までで表される１６の範囲）を示す表現を含む、例示のセル４０８および４１０を含むパターンを含んでいる。
【００５４】
ハーフトーンマトリックス４０６は、例示のセル４０８が例示の画素４０２と関連付けられ、例示のセル４１０が例示の画素４０４と関連付けられるように、画像の画素マトリックス４００の上に覆わせることができる。例示の画素４０２の値は、例示のセル４０８の閾値によって定義される範囲にマッピングされ、例示の画素４０２の値は、例示のセル４１０の閾値によって定義される範囲にマッピングされてもよい。
【００５５】
例示のセルのそれぞれは、異なる閾値を定義していてもよい。例えば、例示のセル４０８は閾値４１２を定義し、例示のセル４１０は閾値４１４を定義してもよい。このように、画素をこれらの各閾値にマッピングすることにより、例示の画素４０２の値が、閾値４１２のうち、第４の閾値と第５の閾値との間に該当し、例示の画素４０４の値が、閾値４１４のうちの第１５の閾値を上回っていると決定される。このように、例示の画素４０２のハーフトーン値は４として表現され、その一方で、例示の画素４０４のハーフトーン値が１５として表現されることができる。
【００５６】
さらに一般的にいえば、ハーフトーンマトリックスのセルが閾値を定義すると仮定する。画素値が最も高い閾値以上である場合、ハーフトーン値は最も高い。画素値が最も低い閾値より小さい場合、ハーフトーン値は０である。画素値がｃ番目の閾値以上であるが、（ｃ＋１）番目の閾値より小さい場合、ハーフトーン値はｃである。
【００５７】
例示の画像ブロックに適用される例示のハーフトーンマトリックスが、図５Ａにおいて表される。
ハーフトーンマトリックスの各セルは、Ａ１…Ａ８またはＢ１…Ｂ８のうちの１つとしてラベルが付される。これらのラベルの各々は、閾値の、潜在的に異なるセットを示す。このように、Ａ１とラベルが付されているセルは、Ａ２やその他のラベルが付されているセルとは異なる閾値のセットを備えていてもよい。
【００５８】
ハーフトーンマトリックスのオーバーレイパターンは、垂直方向に隣接するタイルの初期位置が、２セルで相殺される（オフセットされる）ように、左側にシフトされる。例えば、ハーフトーンマトリックス５０２のＡ１セルは、ハーフトーンマトリックス５００のＡ１セルより２つのセル分だけ左にシフトしている。同様に、ハーフトーンマトリックス５０４のＡ１セルは、ハーフトーンマトリックス５０２のＡ１セルより２つのセル分だけ左にシフトしている。このオフセットにより、審美的に魅力的な角度を有するプリンタによって、ハーフトーンパターンが形成される。
【００５９】
ハーフトーンマトリックスをタイリングするときの１つの考えられる不利な点としては、画像の幅が、ハーフトーンマトリックスの非整数倍である場合に画像の各列に適用することが必要となる場合である。例えば、図５Ａにおいては、画像ブロックは１２×８画素であり、ハーフトーンマトリックスは８×２セルである。このように、１  １／２のハーフトーンマトリックスが、画像ブロックの幅にわたることが必要とされる。以下で更に詳細に説明される理由により、画像の列をパディングする（詰め物をする、埋め込む）ことにより、ハーフトーン処理された画像の圧縮効率の向上につながる。特に、整数のハーフトーンマトリックスの整数が各列に適用されることができるように、画像ブロックは画素の追加の列を用いてパディングされることができる。これらのパディングのコラム（列（埋め込み画素列））は、画像ブロックの最も右にあるコラムの画素のコピーを含んでいてもよい。
【００６０】
パディングのコラムの数は、様々な方法で決定されることができる。パディングの柱の数（ｒ）を決定する１つの可能な方法は、方程式：ｒ＝ｍ  ｒ−（ｐ―ｑ）ｍｏｄ  ｍに従い、ここで、ｍは、セル内のハーフトーンマトリックスの幅であり、ｐは複数の画素の画像ブロックの幅であり、そして、ｑはオフセットである。図５Ａの例においては、ｍ＝８、ｐ＝１２、およびｑ＝２である。
従って、ｒ＝６である。
【００６１】
図５Ｂは、図５Ａの画像ブロックを、６の列をパディングし、ハーフトーンマトリックスをタイリングして示している。図５Ｂに示されるタイリングされたハーフトーンマトリックスに加えて、さらなるハーフトーンマトリックスが、パディングされた画像ブロックに対し、１対の行の右端から行の次の下側の一対の左端までハーフトーンマトリックスで覆うことによって、タイリングされることができる。このように、ハーフトーンマトリックスは、右上角のＡ１…Ａ６およびＢ１…Ｂ６のセルに適用されてもよく、そして、次の２つの行の左側にあるＡ７…Ａ８およびＢ７…Ｂ８セルに包み込ませてもよい。従って、一対の行のそれぞれが左から右へ隣接すると読み込まれる場合に、ハーフトーンマトリックスは順次繰り返される。
【００６２】
実際の画像に基づいて他の実施例を提供するために、図６は、実施例の画像６００および画像６００の１画像ブロック６０２を示す。簡単のため、画像６００は、単一のカラーチャネルを含む。画像ブロック６０２は、画像６００の一部、すなわち、「Ｒ」描写の一の領域の拡大図を表す。
【００６３】
例として、画像ブロック６０２が１２８×１２８の画素の大きさであると仮定する。さらに、図５Ａの８×２のハーフトーンマトリックスが画像ブロック６０２を覆うのに用いられ、そして、オフセットが２、ｍ＝８、ｐ＝１２８、およびｑ＝２であると仮定する。従って、パディングの列の数（ｒ）は、２である。
【００６４】
図７は、再び画像ブロック６０２を、今度は２ピクセルのパディングの列７００が配置して示す。パディングの列７００は、画像ブロック６０２の右側に追加され、１３０×１２８ピクセルのブロックを形成していてもよい。パディングの列７００の画素は画像ブロック６０２の２本の最も右の列から得られることができ、そして、ハーフトーン処理がこれらの画素に適用されてもよい。このように、ハーフトーン処理の後、パディングの列７００の画素は、それらが抽出された画素に類似しなくなる可能性がある。
【００６５】
加えて、図７は、画像ブロック６０２を少し拡大し、ハーフトーン処理が施された画像ブロック７０２を含む。同様に、列７０４は、列７００を少し拡大し、ハーフトーン処理されている。適当な距離から見られると、画像ブロック７０２は、画像ブロック６０２に濃淡としては近い。この効果は、画像ブロック６０２に適切なハーフトーンマトリックスを適用することによって得られる。
【００６６】
図８のハーフトーン処理が施された画素８００は、ハーフトーン処理が適用された後における画像ブロック６０２の右上角の画素を表す。このように、ハーフトーン処理が施された画素８００は、画像ブロック７０２の一部を表していてもよい。ハーフトーン処理された画素８００においては、１６進数の表記法で、個々のハーフトーン処理された画素が、０からＦの値を呈していてもよい。０は最も明るいハーフトーン処理された画素（例えば、白い）を表し、Ｆが最も暗いハーフトーン処理された画素（例えば、黒）を表していてもよい。０とＦとの間におけるハーフトーンの画素値は、ハーフトーン画素値が１の淡い灰色から始まり、その大きさが増加するにつれて、次第により暗くなるグレーの濃淡を表していていもよい。
【００６７】
画像ブロック６０２の右上角は同一調の色であるので、ハーフトーン処理された画素８００の値は、画像ブロック７０２の右上角に現れる斜めのパターンを反映する。これにより、ハーフトーン処理がどのように特定の色合いを表すのに用いることができるかについて、説明される。
【００６８】
画像ブロックのハーフトーン処理された画素において、これらの画素は複数のセグメントに配列されてもよい。この配置を実行する１つの可能な方法が、図９に示される。図９においては、画像ブロックに適用されるハーフトーンマトリックスは、幅８セルおよび高さ２セルであると仮定される。それにもかかわらず、ハーフトーンマトリックスの他のサイズが、使われてもよい。例えば、他の実施例においては、幅がｍセルで高さがｎセルのｍ×ｎ画素のハーフトーンマトリクスを使用することができる。これらのセグメントは、パディング列内の画素を含んでいてもよい。
【００６９】
具体的に、図９は、セグメント９００Ａ、９０２Ａ、９０４Ａおよび９０６Ａに配列されたハーフトーン処理された画素８００の上部の２列を示す。各セグメントは、ハーフトーンマトリックスのサイズ、すなわち、幅８ピクセル、高さ２ピクセルのサイズである。しかしながら、概して、ｍ×ｎセルのハーフトーンマトリックスが用いられる場合、ｍ×ｎ画素のセグメントがそれに応じて用いられてもよい。
【００７０】
図９は、各セグメントの２ウェイのインターリービング（２−ｗａｙ  ｉｎｔｅｒｌｅａｖｉｎｇ）も示す。例えば、セグメント９００Ａにおいて、上部の複数の画素は、そのセグメントの下部の画素を用いて、１つずつインターリービングされる（交互に配置される）。この結果は、インターリービングが施されたセグメント９００Ｂであってもよく、そしてそれは幅１６ピクセルおよび高さ１ピクセルである。同じように、セグメント９０２Ａはインターリービングされたセグメント９０２Ｂを形成するためにインターリービングが施され、セグメント９０４Ａは、インターリービングされたセグメント９０４Ｂを形成するためにインターリービングが施され、そして、セグメント９０６Ａは、インターリービングが施されたセグメント９０６Ｂを形成するためにインターリービングが施されてもよい。一般に、セグメントの高さがｎピクセルである場合、ｎ箇所のインターリービングが施されることができる。かくして、明確化のため、これらのインターリービングが施されたセグメントは、ｍｎ×１のハーフトーンセグメントと称されてもよい。
【００７１】
インターリービングが施されたセグメント９００Ｂ、９０２Ｂ、９０４Ｂ、および９０６Ｂが形成されると、これらのセグメントは、図９に示される順番、すなわち、インターリービングされた最も左のセグメントは、インターリービングされた最も左から２番目のセグメントに続くというように配置されてもよい。これらのインターリービングが施されたセグメントは、その特定の順番で、更なる処理のためにこれらのセグメントを格納するように調整される１つ以上のバッファに、提供されてもよい。このように、以下の説明においては、「セグメント」は、インターリービングが施されたセグメントであると仮定する。更に、これらのセグメントのシーケンスは、バッファの「入力ストリーム」と称されてもよい。
【００７２】
図１０は、１２のセグメントの履歴バッファ（ヒストリバッファ（ｈｉｓｔｏｒｙ  ｂｕｆｆｅｒ））１００２（ＨＢ＿１０〜ＨＢ＿１１のエントリ）と、４つのセグメントの先取りバッファ（ルックアヘッドバッファ（Ｌｏｏｋａｈｅａｄ  ｂｕｆｆｅｒ））１００４（ＬＢ＿０〜ＬＢ＿３のエントリ）および「新しい」バッファ（ニューバッファ（ｎｅｗ  ｂｕｆｆｅｒ））１００６を含む、バッファーにおける配列１０００を示す。そのセグメントにおいては、一端のヒストリバッファ１００２（例えば、ＨＢ＿１１）が、他端のヒストリバッファ１００２（例えば、ＨＢ＿０）に広がるように順番に挿入されるという点で、ヒストリバッファ１００２は、ＦＩＦＯバッファであってもよい。データフローの一般的な方向は、図１０に示されるように、一番下から上部の方向である。すなわち、セグメントは、ニューバッファ１００６にまず配置され、ルックアヘッドバッファ１００４に、そして、ヒストリバッファ１００２に配置されてもよい。
【００７３】
便宜のため、ヒストリバッファ１００２は「ＦＩＦＯバッファ」と称され、ｋのエントリから構成されていてもよく、そして、ルックアヘッドバッファ１００４は、ｋのエントリから構成されていてもよい。ニューバッファ１００６は、図１０に示されるように、単一またはより多くのエントリから構成されていてもよい。従って、バッファアレンジメント１０００の個々のバッファは、それぞれ、任意の数のエントリを含むことができ、そして、図１０に示される具体的な配置は、例示の目的のために示されいてるということを理解されたい。例えば、いくつかの実施態様においては、ニューバッファ１００６のエントリは、ルックアヘッドバッファ１００４の一部であると処理されてもよい。
【００７４】
一般に、ハーフトーンセグメントは、ヒストリバッファ１００２においてマッチングするセグメントを見出すことによって、圧縮されることができる。具体的に、それぞれのシーケンスのうちで最長のマッチングを決定するために、ルックアヘッドバッファ１００４のセグメントの現在のシーケンスが、ヒストリバッファ１００２のセグメントのシーケンスと比較されてもよい。ルックアヘッドバッファ１００４に含まれるセグメントは、ＨＢ＿９、ＨＢ＿１０またはＨＢ＿１１から始めるマッチングを考がえるときに、ヒストリバッファ１００２の一部であるとみなされてもよい。
【００７５】
図１１は、圧縮後のハーフトーンセグメントを表すために用いることができるいくつかの異なるフォーマットを表す。図１１は、図１０のバッファ配列１０００、すなわち、６４ビットのセグメント、ヒストリバッファの１２のエントリ、ルックアヘッドバッファの４つのエントリ、およびニューバッファの１つのエントリに基づく。それにもかかわらず、他のバッファ配列が、図１１のフォーマットを調整することによって、サポートされてもよい。図示の目的で、フォーマット１１００、１１０２および１１０４のサイズは、一定の比率で示されていない。
【００７６】
フォーマット１１００は、セグメントの文字通りの符号化を表していてもよく、特定のセグメントがバッファ配列１０００の情報に基づいて圧縮することができないときに使われることができる。従って、フォーマット１１００は、文字通りのコードワード（リテラルコードワード（ｌｉｔｅｒａｌ  ｃｏｄｅ  ｗｏｒｄ））から開始され、そして、それは１に設定される単一のビットであってもよい。リテラルコードワードは、次のフィールドが圧縮されていないセグメントを含んでいることを示すことができる。具体的に、この次のフィールドは、６４ビットであってもよく、圧縮されることができないセグメントのコピーであってもよい。
【００７７】
フォーマット１１０２は、リピートフォーマットまたはショートリピートフォーマットと称されてもよい。フォーマット１１０２はリピートコードワードから開始され、そして、そのコードワードは０に設定される単一のビットであってもよい。このフィールドには、４ビットのリピート位置フィールドと、２ビットのリピート長フィールドが続いてもよい。リピート位置フィールドは、ヒストリバッファにおけるリピートするセグメントが開始する位置を示していてもよい。リピート長フィールドは、その位置から始まっている繰り返されたセグメントの数を示すことができる。リピート長フィールドのビットを効率的に利用するために、このフィールドは、繰り返されたセグメントの数から１を差し引いた数を含むことができる。リピート長フィールドが「００」を含む場合、リピート長が「１」であることを表す。リピート長フィールドが「０１」を含む場合、リピート長が２であることを表す、等である。
【００７８】
フォーマット１１０４は、拡張リピートフォーマットまたはロングリピートフォーマットと呼ばれてもよい。フォーマット１１０４は、拡張リピートコードワードから開始されてもよく、それは３ビットで１にセットされてもよい。このフィールドの後に、ＨＢ＿１１のセグメントがルックアヘッドバッファ１００４、ニューバッファ１００６、および／または入力ストリームにおいて繰り返される回数、を示す５ビットのリピート長フィールドが続いてもよい。リピート長フィールドのビットを効率的に利用をするために、このフィールドは、繰り返されたセグメントの数から５を差し引いた数を含むことができる。したがって、リピート長フィールドが「０００００」の値を含む場合、繰り返し長さが５であることを表す。リピート長フィールドが「００００１」の値を含む場合、繰り返し長さが６であることを表していてもよい、等である。
【００７９】
図１２は、ある特定のシナリオにおいて、図１１のフォーマットのいずれを使用するべきかについて決定するために実行される全プロセスのフローチャートである。上記の如く、ステップ１２００において、セグメントのそれぞれのシーケンスの間において最長のマッチングを決定するために、ルックアヘッドバッファ１００４のセグメントの現在のシーケンスが、ヒストリバッファ１００２のセグメントのシーケンスと比較されてもよい。ニューバッファ１００６は、入力ストリームから読み込まれる次のセグメントを含んでいてもよい。
【００８０】
ステップ１２０２において、マッチングが見つからなかったことを示す、マッチング長がゼロであるかどうかが決定される。マッチング長がゼロである場合、以降、ステップ１２０４で、以下の処理がとられてもよい：（１）ＬＢ＿０のセグメントを、フォーマット１１００にコード化して出力する、（２）ヒストリバッファからエントリＨＢ＿０の以前のセグメントを落とし、１つのセグメントをヒストリバッファにシフトする、（３）エントリＬＢ＿０のセグメントをエントリＨＢ１１に移す、そして、（４）ＬＢ＿３に新しいセグメントをシフトする。
【００８１】
マッチング長がゼロでない場合、とられる措置はマッチングの長さに依存していてもよい。ステップ１２０６で、以下の条件が真かどうかが決定される：マッチングは、ＨＢ＿１１から始まっており、長さは５でる（全てのルックアヘッドバッファのセグメントは同じであり、ＨＢ＿１１のセグメントに等しく、そして、ニューバッファ１００６のセグメントもＨＢ＿１１の値にマッチする）。
【００８２】
条件が真である場合、それから、ステップ１２０８で、以下の措置がとられることができる：（１）拡張カウント値を５にセットする、（２）拡張カウント値が３６未満で、ニューバッファ１００６のセグメントがＨＢ＿１１のセグメントにマッチする限り、ニューバッファ１００６のセグメントを捨て、拡張カウント値をインクリメントする、（３）フォーマット１１０４を用いて、リピート長フィールドにエンコードされた拡張長さの最終値と共に拡張リピートコードを出力する、（４）ヒストリバッファ１００２を更新することなく、ルックアヘッドバッファ１００４の全４値を破棄する、そして、（５）入力ストリームからの次のセグメントを有するルックアヘッドバッファ１００４をリロードする。
【００８３】
条件が真でない場合、ステップ１２１０において、以下の措置がとられてもよい：（１）マッチするヒストリバッファの位置と、コード化されたマッチする長さと共に、フォーマット１１０２を出力する、（２）マッチしている長さの分、実行ウインドウをシフトする、そして、（３）入力データストリームからの次のセグメントを有するルックアヘッドバッファ１００６をリロードする。同じゼロ以外の最適なのマッチング長を有する複数のマッチングが存在する場合、最も低いヒストリバッファ１００２のインデックスで始まるマッチングが用いられてもよい。
【００８４】
なお、伸張モジュール（ｄｅｃｏｍｐｒｅｓｓｏｒ  ｍｏｄｕｌｅ）が圧縮モジュール（ｃｏｍｐｒｅｓｓｏｒ  ｍｏｄｕｌｅ）と同じヒストリバッファの初期値から始め、同じルールを使用している実行ウインドウを維持してもよい。加えて、もし圧縮される画像が、セグメントサイズの整数倍でない場合、入力ストリームが使い果たされているときは、最後のセグメントには０ビットが記入されてもよい。
【００８５】
ハーフトーンの画像または画像ブロックが圧縮されることができる様々な方法のいくつかをさらに説明するために、図１０のバッファ、図１１のフォーマットおよび図１２の方法がこの種の圧縮を容易にするためにどのように操作されることができるかという実施例を、図１３―１８により提供する。
【００８６】
図１３は、入力ストリームからのセグメントがどのようにニューバッファ１００６およびルックアヘッドバッファ１００４に加えられることができるかについて示す。初期化において、ヒストリバッファ１００２は、エントリＨＢ＿０からエントリＨＢ＿１０に対して全て「Ｆ」値（すなわち、二進数の１１１１）およびエントリＨＢ＿１１に対して全て「０」値（すなわち、二進数の００００）をロードされてもよい。ルックアヘッドバッファ１００４には、入力ストリームから最初の４つのセグメントをロードすることができる。
【００８７】
図１３に示されるシナリオにおいては、マッチングが見出されない。従って、フォーマット１１００の出力が、出力セグメントは圧縮されていないことを示すリテラルコードワードおよび出力セグメントのコピー（例えば、ＬＢ＿０「０００００Ｆ９Ｆ０００００Ｆ９」で表される６４ビット）のコピーを含んで生成される。このように、このセグメントの出力は、合計６５ビットとなる。
【００８８】
加えて、ヒストリバッファ１００２のセグメントが１つのエントリだけ上側にシフトされ、それはエントリＨＢ＿０のセグメントを破棄することを含む。出力セグメントは、エントリＨＢ＿１１に書かれてもよい。
【００８９】
図１４は、ルックアヘッドバッファ１００４およびヒストリバッファ１００２のセグメント間に２つのマッチングが見出される例示のシナリオを示す。図１４の例示のシナリオは、ほぼ、
図１３の例示のシナリオが捨てられたところから続く。このように、ルックアヘッドバッファ１００４のセグメントは１つのエントリによって上にシフトされ、ニューバッファ１００６のセグメントはＬＢ＿３にシフトされ、そして、入力ストリームからの次のセグメントはニューバッファ１００６に置かれる。
【００９０】
それらのバッファ内のセグメントのそれぞれのシーケンスの間において最長のマッチングを決定するために、ルックアヘッドバッファ１００４のセグメントのシーケンスは、ヒストリバッファ１００２のセグメントのシーケンスと再び比較されてもよい。今回、ＬＢ＿０およびＬＢ＿１のセグメントは、２つのセグメントのマッチングについて、セグメントＨＢ＿１１およびＬＢ＿０にマッチングする（上記の如く、マッチングを捜すときには、ルックアヘッドバッファ１００４の内容はヒストリバッファ１００２の一部であるとみなされることができる）。
【００９１】
２つのセグメントのマッチがあると決定することに応答して、フォーマット１１０２の出力が生成されてもよい。この出力は、０（バイナリの）のリピートコードワードと、マッチングがＨＢ＿１１、すなわち、１１番目のバッファエントリ、から始まることを示す、１０１１（バイナリの）のリピート位置、およびＨＢ＿１１のセグメントが２回繰り返されることを示している０１（バイナリ）のリピート長さを、含むことができる（上記の如く、効率化のために、リピート長コードは１が差し引かれた繰り返し長さを示していてもよい。）。このように、２つの６４ビットのセグメントの代わりに、１つの７ビットの値が使われることができる。
【００９２】
加えて、ヒストリバッファ１００２のセグメントは２つのエントリだけ上にシフトされることができ、そして、それによりエントリＨＢ＿０およびＨＢ＿１のセグメントを破棄することを含んでいてもよい。更に、ルックアヘッドバッファのセグメントは２つのエントリだけ上にシフトされることができ、そして、それはエントリＨＢ＿１０およびＨＢ＿１１へシフトされるエントリＬＢ＿０およびＬＢ＿１のセグメントを含むことができる。加えて、ニューバッファ１００６のセグメントはエントリＬＢ＿２にシフトされることができ、そして、それぞれ、入力ストリームからの次の２つのセグメントが、エントリＬＢ＿３およびニューバッファ１００６に格納されることができる。
【００９３】
図１５は、図１４の実施例のシナリオが破棄されたところからほぼ続く他のシナリオを表す。もう一度、ルックアヘッドバッファ１００４のセグメントのシーケンスが、ヒストリバッファ１００２のセグメントのシーケンスと比較され、それらのバッファのセグメントのそれぞれのシーケンスの間における最長のマッチングを決定する。このシナリオにおいては、図１３のシナリオの様に、マッチングは、見つからない（ゼロ長マッチング（ｚｅｒｏ―ｌｅｎｇｔｈ  ｍａｔｃｈ）。
【００９４】
従って、フォーマット１１００の出力が生成される。この出力は、出力セグメントが圧縮されていない（１バイナリ）ことを示すリテラルコードワードおよび出力セグメントのコピー（例えば、ＬＢ＿０のセグメント、「ＦＡＥ００ＦＦＦＦＡＥ００ＦＦＦ」によって表される６４ビット）を含んでいてもよい。このように、合計６５ビットが、このセグメントのために出力される。加えて、ヒストリバッファ１００２のセグメントは１つのエントリだけ上側にシフトされ、そして、それにより、エントリＨＢ＿０のセグメントを捨てることになる。出力セグメントは、エントリＨＢ＿１１に書かれることもできる。
【００９５】
図１６は、ルックアヘッドバッファ１００４およびヒストリバッファ１００２のセグメントの間に１のセグメントのマッチングが見出される実施例のシナリオを示す。図１６の実施例のシナリオは、図１５の実施例シナリオが捨てられたところからほぼ続く。
【００９６】
ルックアヘッドバッファ１００４のセグメントのシーケンスは、ヒストリバッファ１００２のセグメントのシーケンスと再び比較され、それらのバッファのセグメントのそれぞれのシーケンスの間における最長のマッチングを決定してもよい。今回、最長のマッチングは、エントリＬＢ＿０のセグメントとエントリＨＢ＿１１のセグメントとの間にある。
【００９７】
１つのセグメントのマッチングがあると決定することに応じて、フォーマット１１０２の出力が生成されてもよい。この出力は、リピートコードワード（０バイナリ）、ＨＢ＿１１、すなわち、１１番目のバッファエントリにおいてマッチングが始まることを示すリピート位置の１０１１（バイナリ）、およびマッチングが１つのセグメントの長さであることを示す（再び、リピート長は１を差し引いた実際の繰り返し長を意味していてもよい。）００（バイナリ）のリピート長さを含んでいてもよい。このように、６４ビットのセグメントの代わりに、１つの７ビット値が使われることができる。
【００９８】
加えて、ヒストリバッファ１００２のセグメントは１つのエントリ分、上側にシフトされてもよく、そして、それによりエントリＨＢ＿０のセグメントが破棄されてもよい。更に、ルックアヘッドバッファのセグメントが１つのエントリ分、上にシフトされてもよく、そして、それにより、エントリＬＢ＿０のセグメントをエントリＨＢ＿１１へシフトされてもよい。ニューバッファ１００６のセグメントはルックアヘッドバッファ１００４のエントリＬＢ＿３にシフトされることができ、そして、それぞれ、入力ストリームからの次のセグメントが、ニューバッファ１００６に格納されてもよい。
【００９９】
図１７は、ルックアヘッドバッファ１００４およびヒストリバッファ１００２のセグメントの間に、３つのセグメントのマッチングが見出される実施例のシナリオを示す。ルックアヘッドバッファ１００４のセグメントのシーケンスが、ヒストリバッファ１００２のセグメントのシーケンスと再び比較され、それらのバッファのセグメントのそれぞれのシーケンスの間における最長のマッチングを決定してもよい。今回、最長のマッチングは、エントリＬＢ＿０、ＬＢ＿１およびＬＢ＿２の部分と、エントリＨＢ＿４、ＨＢ＿５およびＨＢ＿６のセグメントとの間にある。図１７において楕円で囲まれる値は、パディングの列の値を表す。
【０１００】
３つのセグメントのマッチングがあると決定することに応答して、フォーマット１１０２の出力が生成されることができる。この出力は、リピートコードワード（０バイナリ）と、ＨＢ＿４、すなわち、ヒストリバッファ１００２の４番目のエントリにおいてマッチングが始まることを示す、リピート位置の０１００（バイナリ）、およびマッチングが３セグメント続くことを示すリピート長さの０バイナリを含んでいてもよい。このように、３つの６４ビットのセグメントの代わりに、１つの７ビットの値が使われることができる。
【０１０１】
加えて、ヒストリバッファ１００２のセグメントが、３つのエントリ分、上側にシフトされることができ、そして、それにより、エントリＨＢ＿０、ＨＢ＿１およびＨＢ＿２のセグメントが破棄されてもよい。更に、ルックアヘッドバッファのセグメントは３つのエントリ分、上側にシフトされることもでき、そして、それにより、エントリＨＢ＿９、ＨＢ＿１０およびＨＢ＿１１へ、エントリＬＢ＿０、ＬＢ＿１およびＬＢ＿２のセグメントがシフトされることができる。ニューバッファ１００６のセグメントはエントリＬＢ＿１にシフトされることができ、そして、それぞれ、入力ストリームからの次の３つのセグメントが、ＬＢ＿２、ＬＢ＿３およびニューバッファ１００６に格納されることができる。
【０１０２】
図１８は、５つのセグメントのマッチングがルックアヘッドバッファ１００４およびヒストリバッファ１００２のセグメントの間に見出される実施例のシナリオを示す。このシナリオは、エントリＨＢ＿１１のセグメントがルックアヘッドバッファ１００４およびニューバッファ１００６のエントリの全てにマッチングするとう、「拡張リピート」の実施例である。このように、最長のマッチングは、エントリＨＢ１１、ＬＢ＿０、ＬＢ＿１、ＬＢ＿２およびＬＢ＿３のセグメントとエントリＬＢ＿０、ＬＢ＿１、ＬＢ＿２、ＬＢ＿３およびニューバッファ１００６のセグメントの間にある。
【０１０３】
５つのセグメントの拡張リピートマッチングがあると決定することに応じて、フォーマット１１０４を使用する出力が生成されることができる。この出力は、拡張リピートコードワードの１１１（バイナリ）、マッチングが５つのセグメントにおいて続くことを示すリピート長０００００（バイナリ）を含んでいてもよい（拡張リピートコードワードについて、リピート長コードが、５を差し引いた繰り返し長さを意味していてもよい）。このように、５つの６４ビットのセグメントの代わりに、１つの８ビットの値が使われることができる。リピートがさらなるセグメントにわたって続くシナリオにおいては、入力ストリームが読み込まれ続け、そして、繰り返し長さがそれに応じてインクリメントされてもよい。
【０１０４】
図１９Ａ、１９Ｂ、１９Ｃおよび１９Ｄは、上記の列のパディングのメカニズムの可能な利点の更なる例を提供する。図１９Ａは、例示の８×２のハーフトーンマトリックスに覆われた実施例の画像ブロック１９００を表す。特に、ハーフトーン処理の後、位置１９０２から始まり３つのハーフトーンマトリックスに合わせられる複数の画素と、位置１９０４から始まり３つのハーフトーンマトリックスに合わせられる複数の画素は同一である。
【０１０５】
図１９Ｂは、交互の配置（インターリービング）の後の図１９Ａのハーフトーンマトリックスを含むバッファ配列１９０６を表す。図１９Ｂで分かるように、位置１９０２から始まる３つのハーフトーンマトリックスに合わせられる画素群と位置１９０４から始まる３つのハーフトーンマトリックスに合わせられる画素群が同一である場合であっても、それらはバッファ配列１９０６において互いにオフセットされている。従って、マッチングが、ルックアヘッドバッファおよびヒストリバッファのエントリの間にはない。
【０１０６】
図１９Ｃは、８×２のハーフトーンマトリックスで覆われた実施例の画像ブロック１９０８を表す。実施例の画像ブロック１９０８は、実施例の画像ブロック１９００と、２本のパディング列１９１０が右側に適用されている点以外、類似している。パディング列１９１０を入れることによってなされる変化以外、位置１９０４から始まる３つのハーフトーンマトリックスに合わせられる画素群と、位置１９０２から始まる３つのハーフトーンマトリックスに合わせられる画素群とは同一である。
【０１０７】
図１９Ｄは、交互配置（インターリービング）の後の、図１９Ｃのハーフトーンマトリックスを含むバッファ配列１９１２を表す。パディング列の最初の２画素１９１４（一番上のパディングピクセル）は楕円で囲われており、パディング列の２番目の２画素１９１６（一番上から２番目のパディングピクセル）についても同様に囲われている。図１９Ｄで分かるように、パディング列の挿入により、ヒストリバッファとルックアヘッドバッファとの間に３つのマッチングがある。具体的には、エントリＨＢ＿５、ＨＢ＿６およびＨＢ＿７は、エントリＬＢ＿０、ＬＢ＿１およびＬＢ＿２にマッチングする。このようにして、パディング列は、ハーフトーンの画像のより効果的な圧縮という結果を得ることができる。
５．例示の実施形態の動作
図２０は、例示の実施形態のフローチャートである。このフローチャートで例示されるステップは、印刷装置１００のような１つ以上の印刷装置、および／またはコンピュータ３００のようなコンピュータによって実行されることができる。個々のステップの態様は、単一のデバイスによって実行されることができ、あるいは複数のコンピュータに配布されることができる。図２０の例示の実施形態は、本明細書および／または添付の図面の全体にわたって開示される任意の１または複数の特徴を含んでいてもよい。
【０１０８】
ステップ２０００において、ｍ×ｎのハーフトーンマトリックスおよび画像の第１のｍ×ｎ画素ブロック（ピクセルブロック）に基づいて、第１のｍ×ｎ画素ブロックの第１のｍ×ｎハーフトーン処理された画素ブロックが決定されてもよい。この決定は、ハーフトーンマトリックスの垂直方向に隣接するタイルの開始位置がｑ画素分オフセットするように、画像の上にｍ×ｎハーフトーンマトリックスをタイリングする工程を含んでいてもよい。加えて、ｒ１×ｎのパディング画素列が、画像の最も右の列に追加されてもよい。いくつかの実施形態においては、ｐは、ｒ１×ｎのパディング画素列を追加する前における、画像の画素で現される幅であってもよく、ｒは、ｍ−（ｐ―ｑ）ｍｏｄ  ｍであってもよい。
【０１０９】
ステップ２００２においては、ｎ回のインターリーブが、第１のｍ×ｎの画素ブロックについての第１のｍ×ｎのハーフトーン処理された画素ブロックの複数の行に対して実行され、第１のｍｎ×１のハーフトーンセグメントが生成されてもよい。
【０１１０】
ステップ２００４においては、第１のｍｎ×１のハーフトーンセグメントが、ファースト−イン−ファースト−アウトバッファ（ＦＩＦＯバッファ）内の１つ以上のセグメントと比較――されてもよい。この比較は、第１のｍｎ×１のハーフトーンセグメントおよび隣接して第のｍｎ×１のハーフトーンセグメントに続く他の任意のハーフトーンセグメントにもマッチングするＦＩＦＯバッファ内のハーフトーンセグメントの最も長く連続する範囲を決定する工程を含んでいてもよい。
【０１１１】
ステップ２００６においては、第１のｍｎ×１のハーフトーンセグメントがＦＩＦＯバッファ内の任意のハーフトーンセグメントにマッチングするかどうかが、決定されてもよい。第１のｍｎ×１のハーフトーンセグメントがＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングする場合、ステップ２００８においては、リピートコードワードおよびリピート値が出力されてもよく、そして、第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現が、ＦＩＦＯバッファに書き込まれてもよい。いくつかの実施形態においては、この特定ハーフトーンセグメントが、ＦＩＦＯバッファ内における位置を示すリピート位置が出力に含まれていてもよい。
【０１１２】
第１のｍｎ×１のハーフトーンセグメントが、ＦＩＦＯバッファ内のいずれのハーフトーンセグメントにもマッチングを見出せない場合には、ステップ２０１０において、リテラルコードワードおよび最初のｍｎ×１のハーフトーンセグメントの表現が出力されてもよく、そして、第１のｍｎ×１のハーフトーンセグメントの表現が、ＦＩＦＯバッファに書き込まれてもよい。
【０１１３】
いくつかの実施形態においては、第１のｍｎ×１のハーフトーンセグメントが、他のｍｎ×１のハーフトーンセグメントと共に、１つ以上のルックアヘッドバッファに格納されてもよい。加えて、ＦＩＦＯバッファ内の他のｍｎ×１のハーフトーンセグメントに、特定のハーフトーン部分にマッチするものがあってもよい。ハーフトーンセグメントにｊのマッチングがある場合には、ルックアヘッドバッファにおいて隣接していてもよく、および／または、リピート値がｊを表していてもよい。第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現をＦＩＦＯバッファに書き込むことは、ＦＩＦＯバッファに第１のｍｎ×１のハーフトーンセグメントのｊの表現を書き込む工程を含んでいてもよい。更に、他のｍｎ×１のハーフトーンセグメントが、画像の他のｍ×ｎ画素ブロックから得られることができる。いくつかの実施態様においては、ｊのマッチングするハーフトーンセグメントが、ルックアヘッドバッファから削除されてもよい。
【０１１４】
加えて、リピートコードワードは、ショートリピートコードワードまたは拡張リピートコードワードであってもよい。いずれにせよ、ｊは、ｋと比較されることができる。ｊ＜ｋである場合、リピートコードワードとしてショートリピートコードワードが用いられ、ｊ≧ｋである場合、リピートコードワードとして拡張リピートコードワードが使われることができる。拡張リピートコードワードがリピートコードワードである場合、ＦＩＦＯバッファに第１のｍｎ×１のハーフトーンセグメントのｊの表現を書き込んだ後、ルックアヘッドバッファの少なくとも１つのエントリが、第２のｍｎ×１のハーフトーンセグメントと置き換えられてもよい。第２のｍｎ×１のハーフトーンセグメントは、画像の第２のｍ×ｎ画素ブロックから抽出可能である。
【０１１５】
さらに、ｍ×ｎハーフトーンマトリックスの各セルは、閾値を含んでいてもよい。閾値はｉの画素値の範囲を定めることができ、そして、第１のｍ×ｎ画素ブロックの第１のｍ×ｎハーフトーンバージョンの各セルはｌｏｇ２（ｉ）のビット値を含んでいてもよい。ｍ×ｎの画素ブロックの第１のｍ×ｎのハーフトーンバージョンを決定する工程は、第１のｍ×ｎの画素ブロック内の特定のセルのそれぞれに対して、（ｉ）第１のｍ×ｎ画素ブロックの特定のセルの特定の画素値を決定する工程と、（ｉｉ）ｍ×ｎのハーフトーンマトリックスの特定のセルのｉの画素値の範囲のうちの１つが、特定の画素値を含むか決定する工程であって、第１のｍ×ｎの画素ブロック内の特定のセルは、ｍ×ｎのハーフトーンマトリックスの特定のセルに対応している、工程と、（ｉｉｉ）第１のｍ×ｎ画素ブロックの第１のハーフトーンバージョンの特定のセルに対し、ｉの画素値の範囲のうちの１つを決定することを表すｌｏｇ２（ｉ）のビット値を書き込む工程と、を含んでいてもよい。
６．結論
本発明は、種々の局面を表現することを意図した本願に記載された特定の実施形態の用語に限定されない。当業者に明らかであるように、多くの修正変更が、その趣旨および範囲を逸脱しない範囲でなされることができる。本発明の範囲内の機能的に等価な方法および装置は、本願明細書において列挙されるそれらに加えて、前述の説明から明らかである。この種の修正変更は、添付の請求の範囲内であることを意図する。
【０１１６】
任意のまたは全ての、図示され又は説明された梯子図、シナリオおよびフローチャートに関して、各ブロックおよび／または通信は、例示の実施形態における、情報の処理および／または情報の送受信を表すことができる。別の実施形態は、この種の例示の実施形態の範囲内に含まれることができる。さらに、本願明細書において述べられる任意の梯子図、シナリオおよびフローチャートにおいて、より多くであるか、あるいはより少しのブロックまたは機能が用いられてもよく、そして、部分的に、または、全体で、これらの梯子図、シナリオおよびフローチャートは互いに組み合わされることができる。
【０１１７】
情報の処理を示すステップやブロックは、本願で説明された具体的な方法または技術の論理的特性を実行するように構成されることができる回路に対応することができる。あるいは、または、さらに、情報の処理を表すステップまたはブロックは、モジュール、セグメント、または一部のプログラムコード（関連したデータを含む）に対応することができる。方法または技術の特定の論理的機能または処理を実行するためのプロセッサによって実行可能な１つ以上の指示を、プログラムコードは含むことができる。プログラムコードおよび／または関連したデータは、ディスク駆動装置、ハードディスクまたは他の記憶媒体を含む、記憶装置のような、任意のタイプのコンピュータ読み取り可能な記録媒体に格納されることもできる。
【０１１８】
コンピュータ読み取り可能な記録媒体は、例えばレジスタメモリ、プロセッサキャッシュおよび／またはランダムアクセスメモリ（ＲＡＭ）のような短い期間にデータを格納するコンピュータ読み取り可能な記録媒体のような、非一時的なコンピュータ読み取り可能な記録媒体を含むこともできる。コンピュータ読み取り可能な記録媒体は、例えば、読出し専用メモリ（ＲＯＭ）、光学であるか磁気のディスクおよび／またはＣＤ―ＲＯＭのような、例えば第２であるか持続性の長期記憶媒体のような、より長い期間、プログラムコードおよび／またはデータを格納する非一時的なコンピュータ読み取り可能な記録媒体を含むこともできる。コンピュータ読み取り可能な記録媒体は、他の任意の揮発性、あるいは不揮発性の記憶装置でもあってもよい。コンピュータ読み取り可能な記録媒体は、例えば、コンピュータ読み取り可能な記録媒体および／または有形の記憶装置と考えられることができる。
【０１１９】
様々な態様および実施例が本願明細書において開示されると共に、他の態様および実施例が当業者にとって明らかである。本願明細書において開示されるさまざまな態様および実施形態は、真の範囲および趣旨が以下の請求項によって示される、説明のためのものであって、制限することを目的としない。
【０１２０】
方法は、ｍ×ｎハーフトーンマトリックス、および画像内の第１のｍ×ｎピクセルブロックに基づいて、コンピュータにより、前記第１のｍ×ｎピクセルブロックの、第１のｍ×ｎのハーフトーン処理されたピクセルブロックを決定する工程と、前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎのハーフトーン処理されたピクセルブロックの複数の行に対してｎ箇所の交互配置工程（ｎ−ｗａｙ  ｉｎｔｅｒｌｅａｖｅ）を行い、第１のｍｎ×１のハーフトーンセグメントを生成する工程と、前記第１のｍｎ×１のハーフトーンセグメントを、ＦＩＦＯ（Ｆｉｒｓｔ  ｉｎ  Ｆｉｒｓｔ  ｏｕｔ）バッファの一つ以上のハーフトーンセグメントと比較する工程と、前記第１のｍｎ×１のハーフトーンセグメントが、ＦＩＦＯバッファのいずれのハーフトーンセグメントにもマッチングしない場合、（ｉ）リテラルコードワードと、前記第１のｍｎ×１のハーフトーンセグメントの表現を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの前記表現を前記ＦＩＦＯバッファに書き込む工程と、前記第１のｍｎ×１のハーフトーンセグメントがＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングする場合、（ｉ）リピートコードワードおよびリピート値を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現をＦＩＦＯバッファに書き込む工程と、を含む。
【０１２１】
上記の方法において、前記第１のｍｎ×１のハーフトーンセグメントは、ｋ−１の他のハーフトーンセグメントと共に、ルックアヘッドバッファーに保存されており、ｊ−１≧ｋの他のｍｎ×１のハーフトーンセグメントは、ＦＩＦＯバッファ内の前記特定のハーフトーンセグメントにマッチングし、前記ｊのマッチングするハーフトーンセグメントは、少なくとも前記ルックアヘッドバッファに隣接しており、前記リピート値はｊの指標であり、前記第１のハーフトーンセグメントの少なくとも１つの前記表現をＦＩＦＯバッファに書き込む工程は、ＦＩＦＯバッファに、ｊの前記第１のｍｎ×１のハーフトーンセグメントを書き込む工程を含む。
【０１２２】
上記の方法において、前記ｋ―１の他のｍｎ×１のハーフトーンセグメントは、前記画像の他のｍ×ｎピクセルブロックから得られる。
【０１２３】
上記の方法は、更に以下を含む：
ルックアヘッドバッファからハーフトーンに部分に合うものを見つけているｊを削除すること。
上記の方法において、前記リピートコードワードはショートリピートコードワードまたは拡張リピートコードワードである。
【０１２４】
上記の方法は、ｊをｋと比較する工程と、ｊ＜ｋである場合、前記リピートコードワードとして、ショートリピートコードワードを用いる工程と、ｊ≧ｋである場合、前記リピートコードワードとして、拡張リピートコードワードを使用する工程と、をさらに含む。
【０１２５】
上記の方法において、前記拡張リピートコードワードは、前記リピートコードワードであり、前記方法は、前記第１のｍｎ×１のハーフトーンセグメントのｊの前記表現を前記ＦＩＦＯバッファに書き込む工程の後に、前記ルックアヘッドバッファ内の少なくとも１つのエントリを第２のｍｎ×１のハーフトーンセグメントと置換する工程であって、前記第２のｍｎ×１のハーフトーンセグメントは、前記画像の第２のｍ×ｎピクセルブロックから得られる工程をさらに含む。
【０１２６】
上記の方法において、前記第１のｍｎ×１のハーフトーンセグメントを、前記ＦＩＦＯバッファの前記１以上のハーフトーンセグメントと比較する前記工程は、前記第１のｍｎ×１のハーフトーンセグメントにマッチする、ＦＩＦＯバッファ内の最も長く連続するハーフトーンセグメントと、前記第１のｍｎ×１のハーフトーンセグメントに隣接して続いている任意の他のハーフトーンセグメントを決定する工程を含む。
【０１２７】
上記の方法において、前記第１のｍｎ×１のハーフトーンセグメントは、前記ＦＩＦＯバッファ内の前記特定のハーフトーンセグメントにマッチングしており、前記ＦＩＦＯバッファ内の前記特定のハーフトーンセグメントの位置の指標である、リピート位置を出力する工程をさらに含む。
【０１２８】
上記の方法において、前記ｍ×ｎのハーフトーンマトリックスの各セルは、ｉ―１の閾値を含み、前記ｉ―１の閾値は、ｉの画素値の範囲を定義し、前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎハーフトーンのピクセルブロックの各セルは、ｌｏｇ２（ｉ）のビット値を含む。
【０１２９】
上記の方法において、前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎハーフトーンのピクセルブロックを決定する工程は、前記第１のｍ×ｎピクセルブロックの各特定のセルについて、前記第１のｍ×ｎピクセルブロックの前記特定のセルの特定のピクセル値を決定する工程と、前記ｍ×ｎハーフトーンマトリックスの特定のセル内における、ｉの画素値範囲のうちの１つが、前記特定の画素値を含んでいると決定する工程であって、前記第１のｍ×ｎピクセルブロックの前記特定のセルは、前記ｍ×ｎハーフトーンマトリックスの前記特定のセルに対応している、工程と、前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎハーフトーンのピクセルブロックの特定のセルに対し、前記決定された前記ｉの画素値範囲のうちの１つを表すｌｏｇ２（ｉ）ビットの値を書き込む工程と、を含む。
【０１３０】
上記の方法において、前記第１のｍ×ｎのピクセルブロックの前記第１のハーフトーンのピクセルブロックを決定する工程は、前記ｍ×ｎのハーフトーンマトリックスの縦に連続するタイルの初期位置がｑピクセルのオフセットを呈するように、前記画像上に前記ｍ×ｎのハーフトーンマトリックスを割り当てる工程を含み、上記の方法は、前記画像の最も右の列に、ｒ１×ｎのパディング画素列を追加する工程をさらに含む。
【０１３１】
上記の方法において、ｐは、前記ｒ１×ｎのパディング画素列を追加する工程の前における、前記画像の画素値での幅であり、ｒはｍ―（ｐ―ｑ）ｍｏｄ  ｍ  である。
【０１３２】
非一時的なコンピュータ読み取り可能な記録媒体を含む製造物は、コンピュータによる実行において、コンピュータに、ｍ×ｎのハーフトーンマトリックス、および、第１のｍ×ｎのピクセルブロックに基づいて、コンピュータにより、前記第１のｍ×ｎピクセルブロックの第１のｍ×ｎのハーフトーン処理されたバージョンを決定する工程と、前記第１のｍ×ｎピクセルブロックの前記第１のｍ×ｎハーフトーンバージョンの複数の行に対して、ｎ箇所の交互配置工程を施して、第１のｍｎ×１のハーフトーンセグメントを作成する工程と、前記第１のｍｎ×１のハーフトーンセグメントを、ファーストインファーストアウトバッファ（ＦＩＦＯバッファ）内の１以上のハーフトーンセグメントと比較する工程と、前記第１のｍｎ×１のハーフトーンセグメントが、前記ＦＩＦＯバッファ内の任意のハーフトーンセグメントにマッチングしない場合、（ｉ）リテラルコードワードおよび第１のｍｎ×１のハーフトーンセグメントの表現を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの表現を前記ＦＩＦＯバッファに書き込む工程と、前記第１のｍｎ×１のハーフトーンセグメントが、前記ＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングする場合、（ｉ）リピートコードワードおよびリピート値を出力し、（ｉｉ）前記第１のｍｎ×１のハーフトーンセグメントの少なくとも１つの表現を前記ＦＩＦＯバッファに書き込む工程と、を含む動作を実行させるプログラム命令を格納する。
【０１３３】
上記の製造物において、前記第１のｍｎ×１のハーフトーンセグメントが、ｋ−１の他のｍｎ×１のハーフトーンセグメントと共にルックアヘッドバッファに格納されており、ｊ−１≧ｋの他のハーフトーンセグメントも、前記ＦＩＦＯバッファ内の特定のハーフトーンセグメントにマッチングし、前記ｊのマッチングするハーフトーンセグメントは、前記ルックアヘッドバッファ内において隣接し、前記リピート値はｊを示し、前記第１のｍｎ×１のハーフトーンセグメントの前記少なくとも１つの表現を前記ＦＩＦＯバッファに書き込む工程は、前記第１のｍｎ×１のハーフトーンセグメントのｊの表現を前記ＦＩＦＯバッファに書き込む工程を含む。
【０１３４】
上記の製造物において、前記リピートコードワードがショートリピートコードワードまたは拡張リピートコードワードである。
【０１３５】
上記の製造物において、前記動作は、ｊをｋと比較する工程と、ｊ＜ｋである場合に、前記リピートコードワードとして前記ショートリピートコードワードを用い、ｊ≧ｋである場合、前記リピートコードワードとして前記拡張リピートコードワードを用いる工程と、をさらに含む。
【０１３６】
上記の製造物において、前記拡張リピートコードワードは、前記リピートコードワードであり、前記動作は、前記第１のｍｎ×１のハーフトーンセグメントのｊの表現をＦＩＦＯバッファに書き込む工程の後に、前記ルックアヘッドバッファ内の少なくとも１つのエントリを、第２のｍｎ×１のハーフトーンセグメントに置換する工程であって、前記第２のｍｎ×１のハーフトーンセグメントは、画像の第２のｍ×ｎピクセルブロックから得られる、工程をさらに含む。
【０１３７】
コンピュータは、プロセッサと、データ記憶装置と、前記データ記憶装置に記憶され、プロセッサによる実行において、コンピュータに、請求項１から請求項１３のいずれか１つに記載の方法の動作を実行させる、プログラム命令と、を備える。
【０１３８】
プログラムは、コンピュータによる実行において、コンピュータに請求項１から請求項１３のいずれか１つに記載の方法の動作を実行させる。
【産業上の利用可能性】
【０１３９】
本発明は、半分トーンのデジタル画像の圧縮に適用できてもよい。
【符号の説明】
【０１４０】
１００  印刷装置
１０２  ドキュメントフィーダ／排出トレイ
１０４  給紙カセット
１０６  ユーザインターフェイス
１０８  スキャナー素子
１１０  筐体
２００  コンピュータ
２０２  プロセッサ
２０４  データ格納部
２０６  入力／出力機能
２０８  システムバス
３００  コンピュータ
３０２  スキャン機能
３０４  印刷機能
３０６  スキャン−ホストデータ経路
３０８  ホスト−プリントデータ経路
３１０  スキャン−プリントデータ経路
【図１】
0006268467.tif 000002
【図２】
0006268467.tif 000003
【図３】
0006268467.tif 000004
【図４】
0006268467.tif 000005
【図５Ａ】
0006268467.tif 000006
【図５Ｂ】
0006268467.tif 000007
【図６】
0006268467.tif 000008
【図７】
0006268467.tif 000009
【図８】
0006268467.tif 000010
【図９】
0006268467.tif 000011
【図１０】
0006268467.tif 000012
【図１１】
0006268467.tif 000013
【図１２】
0006268467.tif 000014
【図１３】
0006268467.tif 000015
【図１４】
0006268467.tif 000016
【図１５】
0006268467.tif 000017
【図１６】
0006268467.tif 000018
【図１７】
0006268467.tif 000019
【図１８】
0006268467.tif 000020
【図１９Ａ】
0006268467.tif 000021
【図１９Ｂ】
0006268467.tif 000022
【図１９Ｃ】
0006268467.tif 000023
【図１９Ｄ】
0006268467.tif 000024
【図２０】
0006268467.tif 000025