JPH11243490A - 誤差拡散値の処理方法 - Google Patents

Abstract

(57)【要約】 【課題】 誤差拡散技術において、残留誤差ストリーム
の改良された圧縮と、メモリのより効率的な操作とを可
能にする。 【解決手段】 本発明の方法およびシステムは、連続画
像を与えるために用いられる誤差拡散処理から誤差を累
積する。原稿からの走査は複数の原稿の画素値を生成
し、これらの画素値は隣接する画素の全影響に対応する
累積誤差値によって調整される。調整画素誤差値は調整
画素値と出力の間で決定される。調整画素誤差値は所定
の重み付け技術によって重みが付けられ、複数の隣接す
る画素位置の間に拡散され、複数の中間画素誤差値を生
成する。中間画素誤差は、原稿の画素値と組み合わされ
る前に、誤差バッファに累積および記憶される。調整画
素値に関連するメモリ位置に繰り返しアクセスする動作
を、中間画素値を中間レジスタに累積することによって
避ける。圧縮器は、累積誤差値としてバッファに記憶す
る前に、拡散誤差値を圧縮する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はデータ処理システム
の技術に関し、特に、２値出力装置で印刷または表示を
行う目的のために、連続階調画像を２値ドットパターン
に描画（レンダリング）するための誤差拡散に関する。
本発明は、特に、誤差拡散技術によって発生した誤差革
新列（error innovation sequence ）をより効率的に処
理するとともに、列からの累積誤差値を圧縮してライン
バッファの記憶サイズを小さくする処理システムに適用
することができる。本発明は、向上したメモリ効率およ
び小さなメモリサイズという重要な利点と、プロセッサ
チップに対する外部メモリの必要性を回避することを、
２値印刷または表示装置に提供する。しかしながら、当
業者には、本発明は、他の適用、例えば、同様のデータ
ストリームを順次累積してラインバッファ型レジスタに
記憶するような場合に用いられるように容易に適合させ
ることができることは明らかである。

【０００２】

【従来の技術】誤差拡散は、２値装置で印刷または表示
を行う目的のために、連続階調画像をドットパターンに
描画するための公知の技術である。多くの場合、誤差拡
散技術は、低〜中解像度の装置（６００ドット／インチ
未満）にとって好適な技術である。特に、誤差拡散法は
従来のクラスタドット・スクリーニング技術（clustere
d dot screening technique ）のように所定のしきい値
配列を含まないからである。このような構造化されたセ
ルがないために、誤差拡散は入力データ位置を迅速にト
ラッキングし、高周波部分の描画をより良好にできる。
代替の方法は、高品質の再生に必要なのと同じくらい十
分に多数のグレイレベルを累積するのに、大サイズのア
レイを必要とする（人間の目は約２００のグレイシェー
ド（shadesof gray）を識別することができるとし
た）。このような大サイズのアレイは出力の際に視覚的
に目立つようになるおそれがあるので、アレイサイズお
よびそれに相当する数のグレイレベルは所望の画質に反
して妥協しなければならない。

【０００３】通常、誤差拡散法は、入力画像全体にわた
る走査装置による１つのパスを含み、このとき、各画素
は順次処理される。従来のプロセスは、入力画素値のし
きい値処理と、入力画素値を２つの値、オンまたはオフ
のうち１つに置換する処理とからなる。各画素がこのよ
うに変換される際、誤差が画像の局所グレイレベルに導
入される。誤差とは、走査で決定した原稿の画素値と
「オン」または「オフ」の密度で印刷または表示された
値とのグレイレベルでの差である。この誤差は、隣接す
る画素の値を調整することによって、隣接する画素に拡
散され、観察者の目に見えたしきい値処理前の局所グレ
イレベルを保持する。画像全体にわたり何重にも通過す
るのを避けるために、誤差は、未処理の後続画素の間に
だけ（例えば、左から右への走査順の場合、現在の画素
の右および下に位置する画素に）伝搬（または「拡
散」）される。誤差を隣接する画素の間にどのように分
配するかを決定するいくつかの方法は公知である。

【０００４】図２は、特によく知られたフィルタ方式を
ともなう誤差拡散技術の原理を示す。図２の拡散方式は
本来フロイドおよびスタインバーグによって導出され、
ここでは、例示の目的のために含まれているにすぎない
ことは記憶されるべきである。しかしながら、この例
は、主題の発明の技術、その実施を示し、主題の発明と
従来の誤差拡散技術との違いを明示するためにも用いる
ことができる。

【０００５】図２において、正方形１０は、入力走査装
置から決定されたラスタ格子上の入力画像画素を示す。
黒画素１２および白画素１４は既に処理され、しきい値
処理が行われ、２値化され、オンまたはオフのいずれか
になっている。陰影の付いた画素１６はまだ処理されて
いない。濃い枠で囲まれた中心画素１８は次に処理され
る画素である。現在の画素から重み付き値、、お
よびへの矢印は、現在のしきい値誤差を隣接する画素
にどのように分配するかを示す。それは文献において
「誤差拡散フィルタ」と呼ばれる場合が多い。なぜなら
ば、特定の重み付け方式を適用することは、実際には、
各画素毎にスキャナが検出するものとプリンタが印刷す
るものとの間で算出される誤差のフィルタリングをする
ことであるからである。矢印の番号は、（変動する可能
性がある）非正規化相対近傍重みを説明する。例えば、
現在の画素１８のすぐ右側にある画素に関連する番号
は、誤差の７／１６を用いてこの画素を調整することを
示し、ここで、１６は重みの総和に等しい正規化係数で
ある。これらの近傍をそれぞれこのように調整すると、
それに関連するグレイ値は変化し（誤差の徴候によっ
て、暗くなったり明るくなったりする）、更新された値
は、隣接する画素のしきい値処理に用いられる。

【０００６】上記に基づいて、従来の誤差拡散技術は以
下の３つの基本的なステップからなる。第１に、しきい
値処理ステップにおいて、現在の原稿の画素値を所定の
しきい値と比較して、印刷または表示画素の出力を決定
し、第２に、誤差計算ステップにおいて、原稿の画素値
からこの２値出力レベルを減じることによって、誤差を
計算し、第３に、誤差は選択した重み付け方式にしたが
ってフィルタリングされ、隣接する画素に分配される。
その後、行の終わりに達するまで、この処理は１画素ず
つ進み、繰り返される。

【０００７】従来の誤差拡散処理は図３に示されてい
る。ここで、ｘ（ｉ，ｊ）は現在の画素値、ｅ（ｉ，
ｊ）は誤差、Δｘ（ｉ，ｊ）は位置（ｉ，ｊ）の画素に
対する補正値（compensation value）を示す。また、小
さい矩形はデータレジスタを示し、太線はバスを示し、
細線は２値を示す。

【０００８】

【発明が解決しようとする課題】図３から分かるよう
に、従来の方法では、補正値列を累積するには、メモリ
に多数回アクセスする必要がある。処理された各画素毎
に、システムは、隣接する画素に対して多数の誤差値を
読み込み、誤差値を修正し、その結果をメモリに戻して
書き込む必要がある。これは、すべての画素の値をこの
ように多数回調整しなければならないので、明らかに非
効率的である。例えば、図２中で陰影の付いた画素の
値は、現在のサイクルで発生した誤差につき１回「読み
出し−修正−書き込み」が行われ、その結果、処理が次
の画素に移行すると、再び、「読み出し−修正−書込
み」が行われる（このときは、左から右への処理と仮定
すると、のフィルタ重みによる）。

【０００９】メモリに繰り返しアクセスすることは、時
間消費の点からコストがかかり、データ処理が非効率的
であり、主題の発明が克服しようとする１つの特有の課
題である。

【００１０】従来の誤差拡散システムにともなう別の特
有の課題は、メモリサイズである。１回のラスタ走査の
ために関連する誤差値を記憶および累積するために必要
なメモリ量は、通常、処理チップに対する外部メモリを
用いなければならない程の大きさである。また、追加的
なコストをともなうだけでなく、外部メモリにアクセス
することの非効率さは、実質的に、誤差拡散技術をリア
ルタイムに適用する場合の読み取り内容のメモリ量を最
小化する必要があることを表す。

【００１１】図３に示される誤差拡散方法では、現在の
画素誤差が、その下にある、およそ走査線１本分離れた
画素の値を直接修正するので、メモリ内に少なくとも１
行分の内容を記憶する必要がある。実際、この内容はか
なり大きい可能性がある。例えば、６００ｄｐｉで印刷
された典型的な８．５インチ幅の４色ページの場合に
は、メモリ内に少なくとも２０，０００個のデータセル
を保持する必要がある。ここで、各セルは１つの画素を
処理するのに必要なすべての情報を含むのに十分な大き
さである。以下に詳細に示す理由から、セル当たり８ビ
ットの精度を用いても十分ではないおそれがある。セル
当たり１２ビットを用いると仮定すると、この例の場
合、全体の記憶要件は約３０Ｋバイトのメモリになる。
このような記憶サイズは、現在の低コストのシリコン技
術を用いる単一チップで実施するにはコスト効率が良く
なく、外部メモリ装置を用いてより良好に利用される。
したがって、実質的には、画質を妥協することなく、圧
縮技術を適用してセルサイズを大幅に小さくし、総メモ
リサイズを小さくすることによって、システム全体のコ
ストを低減する必要がある。

【００１２】最小のセルサイズについて考えると、人間
の視覚システムが約２００を超えるグレイシェードを識
別できないことはよく知られており、このことは画素当
たり８ビットがグレイスケール画像表現には十分である
ことを意味する。現行の実施例では、通常、８ビットの
システムを用い、各連続階調画像分解をコンパクトに符
号化している。このため、カラー画像は、通常、３つ以
上の８ビット分解、例えば、「赤、緑および青」または
「シアン、マジェンタおよび黄」のような３色、「シア
ン、マジェンタ、黄および黒」のような４色、または、
ハイファイ色再生をともなう上記以上の色を用いて、符
号化される。８ビットのシステムは、上記の誤差フィル
タ処理／フィードバック機構を操作することができな
い。いずれの単一画素誤差の値も、補正グレイレベルと
しきい値の最大絶対差と同じ大きさになる可能性があ
り、この場合、後者は他のいくつかの向上技術の一部と
しての処理によって変化するおそれもある。所定の画素
に対する誤差分配の総和は画像内容および過去の誤差伝
播履歴に依存し、大きい値になることもある。また、こ
れらの分配は負または正でありうるが、画素値は正の整
数のみであると考えられる。これらの寄与を隣接する画
素値に加えると、これらの寄与によって、結果全体が８
ビットのレンジをオーバーフローし、大きくなりすぎた
り、負になったりする。したがって、通常、より大きな
レンジ、すなわち、より大きなビットが必要になる。

【００１３】さらに、描画に伴う種々の人工生成物（ar
tifact）を除去する通常の実施例のように、ノイズもま
た導入されなければならないので、誤差値のサイズが増
大してしまう。上記に例示したフロイドおよびスタイン
バーグの方法は、決定型誤差拡散フィルタ（determinis
tic error diffusion filter）を用いる。すなわち、誤
差を隣接する画素に分配する方法は、すべての画素に対
して一定かつ固定された状態である。フロイドおよびス
タインバーグは、実験に基づいて、図２に示されるフィ
ルタが許容可能な描画品質を生成するのに必要な（重み
数に換算して）最小のフィルタサイズを有するという結
論を出した。しかしながら、描画に伴う人工生成物は、
出力時に、特に、いくつかの特定のグレイレベルで目に
見える状態のままであるおそれがある。通常、これらの
人工生成物は「くねくねした人工生成物（worming arti
fact）」として現れ、観察者には、いくつかの散在する
ドットが互いにつながり短い線分を形成しているように
見える。これらの人工生成物をさらに除去する効果的な
方法の１つは、追加的な擬似ランダムノイズを処理に導
入することである。ノイズはしきい値を中心としたドッ
ト位置を「ディザー（dither）」するのに役立ち、それ
によって、線分構造を切り離し、より小さく目に見えな
いものにする。より大きなノイズレベルは上記の人工生
成物を除去するのにより効果的であるが、画像の「粒状
性（graininess）」の見かけのレベルを増大させるおそ
れもある。これが、誤差値当たり１０〜１２ビットを通
常の実施に用いられる場合が多い理由である。

【００１４】誤差拡散技術のランダム性および関連する
高周波部分のため、誤差拡散画像を圧縮することが比較
的困難であることはよく知られている。利用できる大抵
の標準的な圧縮技術は高い圧縮比を生成することができ
ない。一般に、同様のことが誤差列の圧縮にも当てはま
る。しかし、８ビットの連続階調画像を紙上またはディ
スプレイ上に２値出力する際、情報内容が大幅に削減さ
れることは明らかである。

【００１５】本発明は新しく改良された装置および方法
を図り、本装置および方法は上記すべての問題およびそ
の他を克服し、新しい誤差拡散システムを提供し、本シ
ステムは、経済的に製造され、様々な次元でのデータ特
性を有する複数の拡散技術に容易に適合でき、残留誤差
ストリームの改良された圧縮と、好適な誤差拡散技術に
おいてメモリのより効率的な操作とを提供する。

【００１６】

【課題を解決するための手段】本発明によると、連続画
像を描画するために用いられる誤差拡散処理から誤差値
を累積する方法において、誤差値は本システムによって
より効率的に処理され、コンパクトな形式に変換され、
誤差バッファに記憶される方法を提供する。本システム
は、個々の画素位置について所定の技術によって原稿を
走査し、前記原稿の原稿画素値の列を識別し、入力バッ
ファに読み込む。前記原稿の画素値は、隣接する画素が
現在の画素に及ぼす全影響に対応する累積誤差値によっ
て調整され、原稿の画素に対応する位置でプリンタまた
はディスプレイによって表示される出力を決定可能な調
整画素値を決定する。調整画素誤差値は、前記調整画素
値と前記表示装置への出力との間で決定される。前記調
整画素誤差値は所定の重み付け技術によって重み付けさ
れ、複数の隣接する画素位置の間へ拡散され、複数の中
間画素誤差値を生成する。前記中間画素誤差値は、前記
調整ステップで前記原稿の画素値と組み合わされる前
に、誤差バッファに累積および記憶され、それによっ
て、前記調整画素値に関連した前記累積誤差値を記憶す
るメモリ位置に、繰り返しアクセスする動作を、前記中
間画素誤差値を中間レジスタに累積することによって避
ける。

【００１７】本発明の別の側面によると、圧縮器（comp
ressor）が拡散器（diffuser）と誤差バッファの中間に
配置され、累積誤差値として誤差バッファに記憶する前
に、拡散誤差値を圧縮する。好ましくは、圧縮器は量子
化器（quantizer ）を備え、拡散誤差値を表現するのに
必要なビット数を低減する。圧縮誤差値はメモリに記憶
され、解凍され、拡散調整画素誤差値と組み合わされ
て、順次の累積を修正し、ディスプレイまたはプリンタ
での十分なグレイレベルを改良されたやり方でメンテナ
ンスする。

【００１８】本発明の別の側面によると、２値重み付き
画像誤差拡散を行うシステムのための特定の回路構成を
提供し、この構成において、分配処理の各除算で発生し
た残りのビットを次の加算器の桁上げ入力（carry-in）
に送るので、累積ハードウェアをさらに設ける必要がな
い。

【００１９】本発明の別の側面によると、誤差バッファ
は水平誤差バッファおよび垂直誤差バッファを備える。
中間レジスタは順方向誤差バッファおよび逆方向誤差バ
ッファを備え、これらのバッファは、最後に垂直誤差バ
ッファに累積および記憶する前に、垂直誤差状態値を順
次累積する。

【００２０】本発明によって得られる恩恵の１つは、フ
ィルタサイズに関わらず、アクセスサイクルの総数を１
つの画素につきたった１回のメモリ読み込みおよび１回
のメモリ書き込み動作に低減することによって、誤差拡
散システムのメモリ効率を大幅に向上させることであ
る。

【００２１】本発明から得られる別の恩恵は、誤差値を
コンパクトな形式に変換し、誤差拡散メモリの使用率を
大幅に向上させる一方、十分な局所グレイレベルを保持
し、画質が目立って低下することはないことである。

【００２２】主題の新しい誤差拡散システムおよび方法
の他の恩恵および利点は、本明細書を読んで理解したと
き、当業者には明らかになるだろう。

【００２３】

【発明の実施の形態】主題の発明は、従来の誤差拡散技
術を改良するとともにさらに向上させ、上記困難および
制限を改善する。特に、本発明は新しく効率的な方法を
提供し、フィルタサイズに関わらず、アクセスサイクル
の総数を１つの画素につきたった１回のメモリ読み込み
および１回のメモリ書き込み動作に低減することによっ
て、メモリ効率を大幅に向上させる。これは、動作の順
序を「逆にして」、メモリのラインバッファに対する
「読み込み」の前に「書き込み」を行うことによって、
行われる。各誤差が拡散されているときラインバッファ
内のすべての関連する画素値を更新する代わりに、本発
明は、まず、中間のΔｘ（ｉ，ｊ）の画素の更新値を局
所レジスタに累積する。所定の画素に対して起こりうる
すべての誤差の寄与が合計されたときのみ、累積結果が
ラインバッファに書き込まれる。最後に、誤差拡散が進
み、（ｉ，ｊ）の位置にある画素を処理するときにな
り、実際の画素値ｘ（ｉ，ｊ）が入力で利用できるよう
になった場合、更新された合計値をラインバッファから
読み出し、直ちに、その値を用いてｘ（ｉ，ｊ）を補正
する。

【００２４】ラインバッファメモリおよび帯域幅の極め
て効率的な使用は、その内容を適正に構成することで、
達成することができる。提案される方法は、調整された
画素誤差を２つの成分、すなわち、水平誤差状態および
垂直誤差状態に分解する。水平誤差状態ｅＸは、処理の
高速走査方向に送られた誤差である。垂直誤差ｅＹは、
現在の行から未処理の行に向かう低速走査方向に送られ
た誤差である。水平誤差に含まれる情報ははるかに短い
語（term）を有するので、水平誤差の方が垂直状態より
処理コストがかなり低いことは明らかである。水平誤差
は生成された後、いくつかの画素にわたって短時間で消
費される。一方、垂直状態情報は数行にわたって保持さ
れなければならない。

【００２５】各誤差拡散サイクルで、１つの垂直誤差が
ラインバッファから検索され、その垂直誤差を用いて、
現在の画素、例えば、ｉ番目の画素を補正する。この位
置は自由になると、次の行のｉ番目の画素のための新し
い垂直誤差で書き換えられる。当然、誤差拡散フィルタ
のスパン（span）を考慮して、書き込み動作は遅延され
る。このため、効率は、各画素につき１回の「書き込
み」動作の前に行われる１回の「読み込み」動作によっ
て表される。

【００２６】必要な総メモリ量は、垂直誤差状態を記憶
する１つのラインバッファと水平状態を記憶する数個の
局所レジスタ分である。このようなレジスタの数は、誤
差拡散フィルタの水平スパンから１を引いた数に等し
い。

【００２７】図面を参照すると、これらの図面は本発明
の好適な実施の形態を例示するためのものにしかすぎ
ず、本発明を限定するためのものではない。図１は、ス
キャナによって生成され、ビデオ画面またはプリンタ等
の２値表示で正確に再生される原稿の画素値を処理する
一方で、十分な局所グレイレベルを維持する記憶システ
ムのブロック図を示す。本発明は従来の誤差拡散技術に
適用することができ、原稿の画素値と２値出力の差を計
算し、表示の隣接する画素に沿って拡散させ、観察者に
は、局所グレイレベルが保持されているように見える。
主題の発明は、特に、隣接する画素からの特定の画素に
適用される誤差革新列を処理および記憶し、表示のグレ
イレベルの所望の保持を維持する場合に適用することが
できる。

【００２８】図１は、本発明に基づくとともに、上記フ
ロイドおよびスタインバーグによる隣接する画素の重み
付け技術の例に対応して実施される誤差拡散技術の１つ
の可能な実施例を示す。図４のフローチャートを対応さ
せながら参照すると、本発明は、まず、原稿を走査し
（ステップ４０）、現在の走査線の原稿の画素値または
現在の画素値を獲得する、その画素値の行方向の位置は
黒く図示されている、すなわち、ブロック６１である。
図１の実施の形態において、現在の画素値は割り当てら
れていない８ビットから構成され、原稿上の、たとえあ
るとしても、ただ１つの色分解から原稿のグレイスケー
ル画像またはテキスト画素を十分に示す。処理要素６２
は現在の画素値を対応する累積誤差値に組み合わせるこ
とによって現在の画素値を調整し、調整画素値を生成
し、この調整画素値は出力を決定可能であり、この出力
は表示上の対応する画素位置で２値表示によって表示さ
れる。調整処理はこれらの値の合計処理を含む。図１に
おいて、累積誤差値は、垂直誤差状態値を保持する垂直
誤差バッファｅＹ６４および水平誤差状態値を保持する
水平誤差バッファｅＸ６６に記憶される。処理要素６２
はこれらの３つの数量すべてを同時に組み合わせ、出力
を決定する調整画素値を生成することができる。調整画
素値はしきい値６８と比較される（ステップ４４）。
尚、しきい値６８は、７０に示されるように、２値出力
がオン、すなわち、「１」かオフ、すなわち、「０」か
を決定する。さらに、オン状態またはオフ状態は、スキ
ャナによって用いられるグレイスケールまたは範囲に対
応する出力値７２に割り当てられる（ステップ４６）。
図３では、８ビットを用いているので、出力のオンの値
は「２５５」、出力のオフの値は「０」である。但し、
２値誤差拡散の場合、１つの比較器７４で十分である。
マルチレベルの誤差拡散の場合は、より多くの比較器
（およびしきい値）が必要になる。しきい値レジスタ６
８は、出力をさらに向上させるとともにいくつかの人工
生成物を除去するため、固定されてもよいし画素から画
素に変動してもよい。

【００２９】好ましくは、処理要素７６は加算器を備
え、加算器は調整画素値を対応する出力のグレイレベ
ル、２５５または０と組み合わせ（ステップ４８）、そ
れらの調整画素誤差値を決定する。例えば、調整画素値
が２００で、しきい値がそれより小さい場合、対応する
画素出力は「オン」になり、対応する補正値は「２５
５」になり、調整画素誤差値は「−５５」になる。主題
の発明の方式は、適当な選択論理（ロジック）の前に多
数の比較器および加算器を用いて、多数の決定を行うマ
ルチレベルの誤差拡散をサポートするように容易に拡張
することもできることは記憶すべきである。

【００３０】調整画素誤差値は拡散器８０の論理に送ら
れ、この論理は種々の誤差の大きさを計算し（ステップ
５０）、これらの大きさは、どのような所定の重み付け
技術が選択された誤差拡散フィルタに適用されても、そ
れにしたがって、隣接する画素に分配される。本発明の
サンプルの場合、拡散器８０は、図２に示される重み付
け／分配方式にしたがって、４つのフィルタタップ（ta
p ）（１／１６、３／１６、５／１６および７／１６）
の中で誤差値を計算する。正確かつ完全な誤差値を確実
に分配させるように注意しなければならない。もしそう
でなければ、有限数精度および／または丸め誤差から生
じる小さな誤差が印刷ページまたはディスプレイ全体に
わたって累積する。本例で用いられるような整数フィル
タの重みを用いれば、簡単な加算演算を用いることによ
って拡散を容易に行うことができる。

【００３１】実際の拡散器の実施は、当然、性能面での
要求に強く依存する。最大速度の場合、平行論理を用い
て、４つすべての誤差タップを一度に生成することがで
きる。しかしながら、外部装置が（本発明の回路の内部
クロック速度と比較して）低速で動作する場合、誤差値
を一度に１つ生成することができ、それによって、１つ
の重み論理を何回も再構成および共有することによって
コストを削減する。後者の場合、タップを計算する順番
を、ハードウェアの記憶および複雑さを最小限にするよ
うに決めることができる。このため、例えば、まず、
（新しい水平状態誤差値に対応する）７／１６の誤差タ
ップ８２の内容（context ）を生成し、その直後に、水
平誤差バッファｅＸのレジスタ６６に記憶し、不要にな
った古い値と置き換える。

【００３２】図１の実施の形態と図３の実施の形態との
違いは、本発明によって計算された調整画素誤差値は、
誤差計算用の現在の画素値でなく、加算器６２によって
生成された調整画素値に基づくことである。図３の従来
のシステムでは、現在の画素値ｘ（ｉ，ｊ）は既に原稿
の画素値と累積誤差とのコンパイレーション（compilat
ion ）でなければならず、その累積処理は、記憶の前、
または、現在の画素値を記憶するラインバッファで行わ
なければならない。

【００３３】本発明を続けると、計算される第２のタッ
プ８４は３／１６タップであり、このタップは、現在の
画素のちょうど左下に位置する画素（図２）に対する現
在の誤差の寄与を含む。第３のタップは５／１６タップ
８６、第４のタップは１／１６タップ８８である。後の
３つのタップ８４、８６、８８はすべて圧縮器９０に入
力され、圧縮器９０は１組の中間レジスタセットおよび
圧縮器を含み、この圧縮器は誤差を圧縮累積誤差値に圧
縮し、垂直バッファｅＹ６４によりコンパクトに記憶す
る。圧縮器９０は、中間レジスタｅＦＷＤ９２およびｅ
ＢＫＤ９４と、加算器９６、９８と、量子化器１００と
を備える。中間レジスタ９２、９４における拡散調整画
素誤差値の順次累積５２は、図２に示される左から右へ
の走査列に対応する順序で行われる。したがって、垂直
誤差状態値を累積する場合、特定の画素に対して、１／
１６タップ８８が計算され、ｅＦＷＤレジスタ９２に記
憶される。現在の画素が誤差が累積されている画素の真
上にあるようにして走査が続くので、以下により詳細に
説明するように、加算器９８によって、量子化器１００
からの余りｒとともに、次の５／１６タップはｅＦＷＤ
レジスタ９２に含まれる値に加算される。その後、加算
器９８からの値は第２の中間レジスタｅＢＫＤ９４に記
憶され、対象の画素のために誤差寄与を累積し続ける。
最後に、現在の画素が対象の画素の右上に移動すると、
加算器９６によって、３／１６タップ８４からの値をｅ
ＢＫＤレジスタ９４の内容に加算される。加算器９６か
らの値は、大きくなり十分に累積された垂直誤差状態値
からなる。その特定の画素を処理するときまで、その値
をメモリ６４に書き込み、記憶することができる。

【００３４】本発明の特徴は、加算器９６からの最後に
累積された誤差値が、誤差バッファ６４に記憶される前
に、圧縮される（ステップ５４）ことである。したがっ
て、その結果は量子化器（ＱＴＺ１００）によって量子
化され、例えば４ビットに圧縮されるが、品質保持と圧
縮程度との間の望しいのトレードオフによって、他のサ
イズを用いることができ、その後、量子化出力ｑとして
誤差拡散バッファに書き込まれる。上記のように、結果
として生じる量子化誤差（量子化器１００からの余りｒ
の出力）はフィードバックされ、順方向レジスタｅＦＷ
Ｄ９２の値を修正する。実際、この重要なステップは余
りの誤差を次の行の次の画素に送ることによって、正確
なグレイレベル全体を維持する。代替例として、余りｒ
は、加算器９８の代わりに加算器７６または加算器９６
に直接入力されることもでき、次に、量子化誤差を用い
て、次の画素値のためにフィルタの重み付けを行う。こ
れは、人工生成物の除去に役立つ。このため、「圧縮」
処理は誤差拡散処理とともに行われ、正確なグレイレベ
ルを保持し、同時に、生じる誤差ストリームのサイズを
小さくする。この意味で、圧縮は「目に見える損失はな
い（visually lossless ）」。圧縮器９０からの結果は
圧縮誤差バッファ６４に記憶され（ステップ５６）、こ
のため、その結果は垂直誤差状態の圧縮を含む。バッフ
ァ６４のサイズは、加算器６２で特定の垂直誤差状態を
水平誤差バッファ６６内の水平誤差状態および原稿の画
素値に組み合わせる必要が生じる前に、十分な垂直誤差
状態を記憶できるような大きさにされる。しかしなが
ら、圧縮状態の記憶は、ラインバッファ６４のサイズの
条件を大幅に低減する。処理要素６２でこれらの値を加
算する前に、符号付きの４ビットとして示される圧縮値
を展開器１０２によって符号付きの９ビットに展開する
（ステップ５８）。その後、システムは次の画素位置に
移動し（ステップ５９）、繰り返すことができる。

【００３５】各行の始めと終わりでの境界条件について
は、１つの手法（多くの場合、ハードウェアによる実施
において好ましい）は、行サイズおよび誤差バッファ
を、それぞれ、各側で数画素分（誤差拡散フィルタ幅よ
り１小さい値に相当する）大きくし、これらに対して知
られている値（通常、白、または、各行の最初／最後の
画素値の複製のいずれか）を仮定することである。第２
の代替例は、最初の数画素でフィルタタップを調整し、
真の行限界からはみ出さないようにする。例えば、１行
の最初の画素に対しては、上記例の誤差拡散フィルタは
３／１６タップを７／１６タップに組み合わせ、１０／
１６の重み等で１つの真下のタップを生成する等。第１
の方法（ハードウェアによる実施の場合に好ましい）
は、行延長（すなわち、より大きなバッファ記憶、より
大きな拡散サイクル）を犠牲にして、拡散フィルタを固
定した状態を保つという利点がある。

【００３６】特に、図５を参照すると、２値幅分配パタ
ーンを用いる画像−誤差拡散描画を行うときに誤差値を
分配させるシステムが示されている。

【００３７】より大きなサイズの２値重み付き分配パタ
ーンは、上記の本来のフロイドおよびスタインバーグの
重み付けシステムの良い代替例であり、２値の乗算はシ
フトとして示されるので、実施をより簡単になるという
利点を有することが分かった。良い一例は、それぞれ、
８、４、２、１、１（図５に示されるような分配ｗｔ＿
ｘｘ、ｗｔ＿０、ｗｔ＿１、ｗｔ＿２、ｗｔ＿ｙ３の場
合）である。重みはそれぞれ２値のべき乗であり、重み
の合計も２値のべき乗である。これによって、２による
除算が単に１桁のシフトなので、各分配項に加算される
べき誤差の総数の計算が容易になる。図５の装置によっ
て実施される方法は、各除算の余りを分配させ、分配処
理が情報を失わないようにする経済的な方法である。こ
れは、種々の余りビットを既存の加算器の桁上げ入力に
送ることによって、行われる。重要な点は、分配に対す
る余りが４つしかないので余分のハードウェアを設ける
必要はなく、また、他の理由のため分配誤差の５つの指
定値のうち４つは既に加算器を有することである。特
に、剰余を入力の桁上げによって順次累積することがで
きるので、除算の剰余のために累積器は必要ない。

【００３８】特に、図５は、現在の画素に隣接する複数
の画素の間に拡散される調整画素誤差値を記憶する拡散
誤差バッファ１１０を示す。複数の中間レジスタＹ０、
Ｙ１、Ｙ２およびＹ３は、中間画素誤差値を保持しなが
ら配置されている。例えば、拡散誤差バッファのサイズ
は、符号付きの９ビットの誤差値を保持する大きさであ
る。１／４で除算して１／４重みタップをレジスタＹ０
に割り当てる処理は、誤差バッファ１１０を２桁桁送り
し、２つの最下位ビットを落とし、６つの最上位ビット
をＹ０にロードすることだけである。走査技術による
と、１／４重みタップが１／８重みタップと合計された
場合、誤差値Ｙ０は累積器１１２で累積され、レジスタ
Ｙ１に記憶されることができる。同様に、順次走査が続
くにつれて、拡散誤差バッファにロードされる連続する
値は１／４＋１／８＋１／１６＋１／２のように累積さ
れる。ｘｘの値は、水平誤差状態値の重み付けに相当す
る。累積器１１４、１１６、１１８は中央累積処理を行
う。累積器１１８への誤差入力１２０は、垂直誤差状態
値の累積処理からなる。累積器１１８からの出力が、誤
差入力＋ｘｘは、誤差バッファに記憶されるべき値であ
る。

【００３９】本発明の特徴は、それぞれの重み付けタッ
プを割り当てる桁送りからの除算の剰余は失われない
が、各累積器の入力の桁上げによって累積器セットに順
次分配されることである。

【００４０】２値数を２で割るには、最下位ビットの左
のビットを選択しさえすればよい。次に、最下位ビット
は除算の剰余になり、桁上げおよび入力に分配される。
従来のシステムはこの分配誤差を累積し、別個の演算を
用いて、その誤差を目的の１つに加えていた。主題の発
明はより均一な分配を行い、これらの分配誤差を合計す
る累積器のハードウェア使用を回避する。

【００４１】主題の発明が、誤差データが圧縮されてい
るか否かに関わらず、上記メモリアクセスについて効率
的であることは特記すべきである。圧縮をすべて省くに
は、量子化ブロックＱＴＺ１００を除去し、代わりに、
未処理の入力を圧縮器９０のｑ出力に単に送るだけの配
線を用いれば十分であり、常に、余り出力ｒで０に戻
る。簡単であるが重要な圧縮を可能にするためには、入
力スペースの均一な量子化を適用することができ、この
処理において、ＱＴＺブロック１００は上位数桁のビッ
ト（最上位ビット）だけを取り込む。代替例として、
（対数スケールのような）非線形写像によって入力スペ
ースを引き延ばすように量子化器１００を設計し、小さ
いルックアップテーブルを追加するという犠牲をはらっ
て、より良好な圧縮を行うことができる。

【００４２】上記のように、主題の発明についてフロイ
ドおよびスタインバーグの例を用いて説明してきたが、
基本的な技術は極めて一般的であり、カスタマイズし
て、任意の誤差拡散フィルタ、マルチレベル誤差拡散、
ランダム化しきい値処理および他の品質向上の変形例と
ともに機能することができる。

【００４３】主題の発明は、コピー機、プリンタおよび
多機能装置に適用することができる。本発明は、他のシ
ステムよりかなり低い描画コストを可能にすることによ
ってプリンタ／コピー機／ファックス等の電子機器のコ
ストを大幅に削減することができ、さらに、向上させる
可能性を示す。

【００４４】本発明について好適な実施の形態および代
替の実施の形態を参照して説明してきた。本明細書を読
んで理解したとき、変形および変更が行われるであろう
ことは明らかである。このようなすべての変形および変
更が特許請求の範囲またはそれの等価物の範囲内にある
限り、本発明はこれらの変形および変更を含む。

【図面の簡単な説明】

本発明はある部品および部品の配置において物理的な形
態をとり、本発明の好適な実施の形態について本明細書
で詳細に説明するとともに添付図面に例示する。

【図１】本発明の好適な実施の形態のブロック図であ
る。

【図２】従来の誤差拡散の走査／重み付け技術を示す説
明図である。

【図３】従来の誤差拡散システムのブロック図である。

【図４】本発明の好適な実施の形態の方法のフローチャ
ートである。

【図５】２値重み付き誤差拡散システムに用いる拡散器
の１つの特定のハードウェアの実行を示す説明図であ
る。

【符号の説明】 １０ 正方形 １２ 黒画素 １４ 白画素 １６ 画素 １８ 中心画素 ５２ 累積器 ６２ 加算器 ６４ 垂直誤差バッファｅＹ ６６ 水平誤差バッファｅＸ ６８ しきい値レジスタ ７２ 出力値 ７４ 比較器 ７６ 加算器 ８０ 拡散器 ８２、８４、８６、８８ 誤差タップ ９０ 圧縮器 ９２ 中間レジスタｅＦＷＤ ９４ 中間レジスタｅＢＫＤ ９６、９８ 加算器 １００ 量子化器 １０２ 展開器 １１０ 拡散誤差バッファ １１２、１１４、１１６、１１８ 累積器 Ｙ０、Ｙ１、Ｙ２、Ｙ３ 中間レジスタ

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ドナルド ジェイ．カリー アメリカ合衆国 94025 カリフォルニア 州 メンロ パーク レランド アベニュ ー 333

Claims (1)

【特許請求の範囲】
1. 【請求項１】 ２値表示で連続画像を２値表示で描画す
   るために用いられる誤差拡散処理からの誤差値を累積す
   る方法であって、 個々の画素位置について所定の技術によって原稿を走査
   し、前記原稿の原稿の画素値の列を識別するステップ
   と、 走査された原稿の画素位置に対応する描画された画素位
   置で前記２値表示によって表示される２値出力を決定す
   る調整画素値を決定するために、前記原稿の画素値を累
   積誤差値によって調整するステップと、 調整画素誤差値からなる、前記２値出力と前記調整画素
   値の差を計算するステップと、 所定の重み付け技術にしたがって各画素位置に影響を及
   ぼす中間画素誤差値に基づいて、各画素位置毎に拡散調
   整画素誤差値を生成するために、前記調整画素誤差値を
   所定の重み付け技術によって拡散させるステップと、 走査技術の列にしたがって誤差革新列を順次累積するた
   めに、前記中間画素誤差値のうち相対的な１組を千鳥状
   に配列された中間レジスタに配置するステップと、 前記中間画素誤差値の和を備える誤差バッファに累積誤
   差値を記憶するステップとを有し、それによって、前記
   累積誤差値を記憶するために前記調整画素値に関連する
   メモリ位置に繰り返しアクセスする動作を、前記中間画
   素誤差値を前記中間レジスタに順次累積することによっ
   て避けることを特徴とする誤差値累積方法。