TOP > 中国の大学の特許 > 北京大学の特許一覧 > 高速でFM格子点の発生を可能にする方法および装置 > 明細書

明細書 :高速でFM格子点の発生を可能にする方法および装置

発行国 日本国特許庁(JP)
公表番号 特表2008-535419 (P2008-535419A)
公報種別 特許公報(B2)
公表日 平成20年8月28日(2008.8.28)
特許番号 特許第4481343号 (P4481343)
登録日 平成22年3月26日(2010.3.26)
発行日 平成22年6月16日(2010.6.16)
発明の名称または考案の名称 高速でFM格子点の発生を可能にする方法および装置
国際特許分類 H04N   1/405       (2006.01)
G06T   5/00        (2006.01)
FI H04N 1/40 B
G06T 5/00 200A
請求項の数または発明の数 9
全頁数 15
出願番号 特願2008-504606 (P2008-504606)
出願日 平成18年3月31日(2006.3.31)
国際出願番号 PCT/CN2006/000567
国際公開番号 WO2006/105721
国際公開日 平成18年10月12日(2006.10.12)
優先権出願番号 200510063255.3
優先日 平成17年4月7日(2005.4.7)
優先権主張国 中華人民共和国(CN)
審査請求日 平成19年12月10日(2007.12.10)
特許権者または実用新案権者 【識別番号】507231932
【氏名又は名称】北大方正集▲団▼有限公司
【氏名又は名称】PEKING UNIVERSITY FOUNDER GROUP CO., LTD
【識別番号】507232456
【氏名又は名称】北京北大方正▲電▼子有限公司
【氏名又は名称】BEIJING FOUNDER ELECTRONICS CO., LTD.
【識別番号】507232478
【氏名又は名称】北京大学
【氏名又は名称】PEKING UNIVERSITY
発明者または考案者 【氏名】リュウ ヂィホン
【氏名】チェン フェン
【氏名】ヤン ビン
個別代理人の代理人 【識別番号】100077481、【弁理士】、【氏名又は名称】谷 義一
【識別番号】100088915、【弁理士】、【氏名又は名称】阿部 和夫
審査官 【審査官】加内 慎也
参考文献・文献 特開平06-098159(JP,A)
特開平09-135348(JP,A)
特開2002-185788(JP,A)
特開2002-094790(JP,A)
調査した分野 H04N 1/405
特許請求の範囲 【請求項1】
周波数変調ハーフトーンドットを高速で発生させることを可能にする方法であって、
(a)累積誤差値を格納する誤差行メモリの列に誤差行を編成し、誤差行メモリを初期化するステップと、
(b)誤差分散値および累積誤差値を格納する誤差バッファレジスタファイルをセットするステップと、
(c)カレントソースピクセルを取得するステップと、
(d)カレントソースピクセルの値、誤差行に格納されている累積誤差値および誤差バッファレジスタファイルに格納されている前記誤差分散値に基づいてハーフトーンドットを発生させるステップと、
(e)誤差行および誤差バッファレジスタファイルを前記カレントソースピクセルからの誤差分散値に基づいて更新するステップと、
(f)カレント行が完全に処理されるまで前記ステップ(c)、(d)および(e)を繰り返すステップと、
(g)画像が完全に処理されるまで前記ステップ(b)、(c)、(d)、(e)および(f)を繰り返すステップと
含み、
前記ステップ(a)は、
(1)繰り返し使用される誤差行であって、1つのピクセルからの誤差をそこに分散させることができる行の数より少なくない誤差行の数を、nが正の整数である2としてセットするステップであって、前記誤差行メモリのバスの幅は2個の要素を誤差行メモリから同期的に読み書きすることを可能にするステップと、
(2)同じ列では同じ数になっている誤差位置であって、2個の列の誤差位置の各々を隣接して配列するステップと、
(3)前記誤差行を0として初期化するステップと
をさらに含むことを特徴とする方法。
【請求項2】
前記ステップ(b)は、
(1)誤差バッファレジスタファイルを、誤差分散バッファレジスタファイルと誤差累積バッファレジスタファイルとを含むようにセットするステップと、
(2)前記誤差バッファレジスタファイルを初期化するステップであって、前記誤差バッファレジスタファイルは各々の行の処理の開始時に0として初期化されるステップと
をさらに含み、
前記誤差分散バッファレジスタファイルは、誤差行内のある位置の相対ピクセルのすべてからの誤差分散値のすべてをストアするのに十分になっており、カレント相対ピクセルはカレント操作行内のピクセルのすべてとしてセットされ、その誤差値は誤差行内のその位置に分散させることができ、
前記誤差累積バッファレジスタファイルは、カレント操作行の後に続くオリジナル誤差行の相対累積誤差値のすべてをストアするのに十分になっており、前記相対累積誤差値は、誤差行内のある位置のオリジナル累積誤差値を読み出してからその位置の新しい累積誤差値を書き込むまでの行程における誤差行内の読み取られたオリジナル累積誤差値のすべてとしてセットされることを特徴とする請求項1に記載の方法。
【請求項3】
前記ステップ(d)は、
(1)カレントソースピクセルの位置と、次の行および同じ列における位置とに対応する累積誤差値を誤差行メモリから同期的に読み出すステップと、
(2)同じ行内の先行ピクセルのすべてによって生成された誤差の分散に由来するカレントソースピクセルの誤差値の総和Sを、誤差バッファレジスタファイルに照らして計算するステップと、
(3)カレントピクセルに対応する位置のオリジナル累積誤差値、総和Sおよびカレントソースピクセルの値を加算することによってピクセルの最終値を求め、該最終値をしきい値と比較することによって最終ハーフトーンドットを発生させるステップと
をさらに含むことを特徴とする請求項1に記載の方法。
【請求項4】
前記ステップ(e)は、
(1)隣接するピクセルのすべてについて、カレントピクセルによって生成された誤差の分散によって引き起こされた値Dをピクセルの最終値としきい値とに照らして求めるステップと、
(2)誤差分散バッファレジスタファイル内の各ピクセルの誤差分散値を、その次のピクセルの誤差分散値として更新し、最終ピクセルの誤差分散値を値Dとして更新するステップと、
(3)誤差累積バッファレジスタファイル内の各ピクセルの累積誤差値をその次のピクセルの累積誤差値として更新し、最終ピクセルの累積誤差値をカレントピクセルに対応していて、次の行内の位置のオリジナル累積誤差値として更新するステップと、
(4)誤差行内の1つの列内の書き込まれたデータ値のすべてを誤差バッファレジスタファイルに照らして求め、書き込まれたデータ値を誤差行メモリに同期的に書き込むステップと
をさらに含み、
誤差行内の列におけるある位置の書き込まれたデータ値は、その位置のオリジナル累積誤差値と、その位置に分散され、誤差バッファレジスタファイルにストアされたすべての誤差分散値との総和に等しいことを特徴とする請求項1に記載の方法。
【請求項5】
請求項1に記載の方法を実現するために周波数変調ハーフトーンドットを高速で発生させることができる装置(1)であって、しきい値比較回路(4)と、誤差生成回路(5)と、誤差行メモリ(2)と、誤差バッファレジスタファイル(3)と、誤差バッファレジスタファイル制御回路(6)と、グレー生成回路(7)と、誤差行制御回路(8)とを備えた装置(1)であって、
前記誤差行メモリ(2)は、処理期間中に誤差分散の結果をストアするために使用され、前記誤差バッファレジスタファイル(3)は、中間誤差値をバッファリングするために使用され、前記グレー生成回路(7)は、ソースピクセル、前記誤差行メモリ(2)、および誤差バッファレジスタファイル(3)に結合され、誤差分散の後ソースピクセルの最終グレーレベルを生成するために使用され、
前記しきい値比較回路(4)は、グレー生成回路(7)に接続されていて、最終グレーレベルをしきい値と比較して最終ハーフトーンドットを発生させ、前記誤差生成回路(5)は、グレー生成回路(7)に接続されていて、しきい値および最終グレーレベルに照らしてカレント誤差分散値を算出し、前記誤差バッファレジスタファイル制御回路(6)は、誤差バッファレジスタファイルの更新と出力を制御するために使用され、誤差バッファレジスタファイル制御回路(6)の入力は、誤差生成回路(5)、誤差行制御回路(8)、および誤差バッファレジスタファイル(3)のフィードバックから得られ、前記誤差行制御回路(8)は、誤差行メモリ(2)に結合されていて、誤差行メモリに対して読み書きアドレス、読み書き制御信号および読み書きデータを生成するために使用され、前記誤差行制御回路(8)の入力はカレント操作ピクセル、誤差バッファレジスタファイル制御回路(6)、および誤差生成回路(5)を含む座標から得られ
繰り返し使用される誤差行であって、1つのピクセルからの誤差をそこに分散させることができる行の数より少なくない誤差行メモリの誤差行の数を、nが正の整数である2とし、前記誤差行メモリのバスの幅は2個の要素を誤差行メモリから同期的に読み書きすることを可能にし、
同じ列では同じ数になっている、2個の列の誤差位置を隣接して配列し、
前記誤差行を0として初期化することを特徴とする装置。
【請求項6】
誤差バッファレジスタファイル(3)はトリガを含み、誤差分散バッファレジスタファイルおよび誤差累積バッファレジスタファイルを含んでおり、
前記誤差分散バッファレジスタファイルは、誤差行内のある位置の相対ピクセルのすべてからの誤差分散値のすべてをストアするのに十分になっており、カレント相対ピクセルはカレント操作行内のピクセルのすべてとしてセットされ、その誤差値は誤差行内のその位置に分散させることが可能であり、前記誤差累積バッファレジスタファイルはカレント操作行の後に続くオリジナル誤差行の相対累積誤差値のすべてをストアするのに十分になっており、前記相対累積誤差値は誤差行内のある位置のオリジナル累積誤差値を読み出してから、その位置の新しい累積誤差値に書き込むまでの行程における誤差行内の読み出されたオリジナル累積誤差値のすべてとしてセットされることを特徴とする請求項に記載の装置。
【請求項7】
グレー生成回路(7)は加算器を含み、
前記加算器の入力は、ソースピクセル、誤差行から読み出されたカレント誤差値、および誤差バッファレジスタファイル内のバッファリングされたカレント誤差値から得られることを特徴とする請求項に記載の装置。
【請求項8】
誤差バッファレジスタファイル制御回路(6)は、n個のマルチプレクサを含み、
nは誤差バッファレジスタファイル内のレジスタの数であり、前記マルチプレクサの入力は、カレント誤差分散値、カレント累積誤差値、および誤差バッファレジスタファイル内のオリジナル値を含み、前記マルチプレクサの出力は誤差バッファレジスタファイル内のレジスタの更新値であることを特徴とする請求項に記載の装置。
【請求項9】
誤差行制御回路(8)は、読み取りアドレスレジスタ、書き込みアドレスレジスタ、読み書き制御回路、および書き込みデータ生成回路を含み、
前記読み取りアドレスレジスタおよび書き込みアドレスレジスタは、カレントピクセルの列番号別に生成され、
前記書き込みデータ生成回路は加算器を含み、前記加算器の入力は、オリジナル累積誤差値、カレント誤差分散値およびバッファリングされた相対誤差値から得られることを特徴とする請求項に記載の装置。
発明の詳細な説明 【技術分野】
【0001】
本発明はデジタル画像ハーフトーンの分野においてハーフトーンドットを発生させるための方法および装置に関し、さらに具体的には、周波数変調(FM)ハーフトーンドットを高速で発生させることができる方法および装置に関する。
【背景技術】
【0002】
デジタル画像ハーフトーンの技術としては、振幅変調スクリーニングと周波数変調スクリーニングとがある。誤差拡散法(Error Diffusion method)は、共通周波数変調スクリーニング法で広く使用されている。誤差拡散法では、ハーフトーンドットはオリジナル画像の各ドットのグレーレベルをしきい値と比較することによって作り出されているが、各ドットのグレーレベルとしきい値との差は隣接ドットに分散されている。例えば、256のグレーレベルを持つ画像では、しきい値は127にセットされている。比較後、グレーレベルが150であるドットはホワイトドット(white dot)になっている。しかし、このドットは、ドットのグレーレベルとホワイトドットとの間に差があるため、純粋にホワイトになっていないはずである。この誤差値23は、なんらかの手段によってそのドットの前後の隣接ドットに分散されている。
【0003】
Floyd-Steinberg法(algorithm)は、誤差拡散法のための最も周知の共通アルゴリズムである。このアルゴリズムを使用すると、カレントドットのグレーレベルがしきい値と比較された後、ドットのグレーレベルは1または0にセットされる(すなわち、ドットはブラックドットまたはホワイトドットにセットされる)。次に、グレーレベルとしきい値との差を計算することによって誤差が求められる。最後に、誤差は隣接ドットのグレーレベルを調整するために隣接ドットに分散される。特に、Floyd-Steinberg法によると、誤差値の7/16がカレントドットに隣接し、その右側にあるドットに加算され、誤差値の5/16は、カレントドットに対応している次の行内のドットに加算され、誤差値の3/16は、次の行(row)内のカレントドットに対応するドットに隣接し、その左側にあるドットに加算され、誤差値の1/16は次の行内のカレントドットに対応するドットに隣接し、その右側にあるドットに加算される。このようにして、カレントドットの誤差は隣接ドットに分散される。このプロセスは画像内のすべてのドットごとに実行され、ハーフトーンを生成し、グレーレベルを改善する。
【0004】
Stucki法(algorithm)などの、いくつかの改良アルゴリズムがFloyd-Steinberg法に基づいて出現している。Stucki法を使用すると、カレントドットによって発生した誤差はカレントドットの12個の隣接ドットに分散される。アウトプット画像の効果が向上しているのは、分散期間により多くのドットが関係しているためである。さらに、誤差を分散する期間に、各行のドットが左から右に向かって処理される場合、各行からの誤差は次の行の誤差に加算されるので、誤差が累積される。このようにすると、アウトプット画像は視覚に傾向を持つことになる。良好な効果を得るために、スキャンが行なわれるときS形状スキャン(S-shaped scan)が使用される。具体的に説明すると、画像全体について、奇数の行は左から右に向かってスキャンされ、偶数の行は右から左に向かってスキャンされる。
【0005】
一般的に、誤差拡散法によると、良好な効果が得られる。しかし、この方法に欠点があることは明らかである。この方法によると、メモリにおける計算と操作の回数が多くなるためドットの発生速度が低速になっている。例えば、Stucki法をS形状スキャンと併用するとき、一般に誤差行メモリ(error row memory)と呼ばれているメモリは、誤差拡散の後、カレント行と次の2行の結果を格納するために使用されるのが一般的である。誤差行の各位置は対応する位置の累積誤差値(accumulated error value)を示している。従って、カレントピクセルおよび誤差行内の12個の隣接位置に対応するオリジナル累積誤差値は、すべてのピクセルを処理するために読み出される必要がある。カレントピクセルの計算誤差値が得られた後、その値は12個の隣接位置に分散される。各分散値は、対応する位置のオリジナル累積誤差値に加算され、その結果はそれぞれ誤差行内の12個の位置に書き込まれる。以上から明らかであるように、従来の方法では、メモリにおいて要求される操作が多くなっている。メモリの読み書き速度はコンピュータシステムのボトルネックになっている。従って、誤差拡散法に基づくスクリーニング法を適用する範囲が制限されているのは、アウトプット効果を向上できる一方でその処理速度によるためである。誤差拡散法に基づく方法でドットを発生させる速度を向上するために特殊なハードウェアが使用されるのが一般的であるが、メモリにおける操作が複数あるため、速度に影響を与え、リアルタイム機能を持つ高速プリンタや複写マシンの要求条件を満たすことが困難であるので、誤差拡散法に基づくスクリーニング法は、最新の高速プリンタや複写マシンに適用することが困難になっている。
【発明の開示】
【発明が解決しようとする課題】
【0006】
従来技術の欠点を解消するために、本発明は、周波数変調ハーフトーンドットを高速で発生させることができる方法と装置を提供する。各々のピクセルを処理するとき、装置は、周波数変調ハーフトーンドットを発生させる速度を向上させるように、一回の読み取り操作と一回の書き込み操作だけで誤差行メモリにアクセスする。
【課題を解決するための手段】
【0007】
上記目的を達成するために、本発明は周波数変調ハーフトーンドットを高速で発生させることを可能にする方法であって、
(a)列に編成し、誤差行メモリを初期化するステップと、
(b)誤差バッファレジスタファイルをセットするステップと、
(c)カレントソースピクセルを取得するステップと、
(d)カレントソースピクセル、誤差行および誤差バッファレジスタファイルに基づいてハーフトーンドットを発生させるステップと、
(e)誤差行および誤差バッファレジスタファイルを更新するステップと、
(f)カレント行が完全に処理されるまで前記ステップ(c)、(d)および(e)を繰り返すステップと、
(g)画像が完全に処理されるまで前記ステップ(b)、(c)、(d)、(e)および(f)を繰り返すステップと
を含むことを特徴とする方法を提供している。
【0008】
さらに、本発明の効果を向上させるために、前記ステップ(a)は、さらに、
1)繰り返し使用される誤差行であって、1つのピクセルからの誤差をそこに分散させることができる行の数より少なくない誤差行の数を、nが正の整数である2としてセットするステップであって、当該誤差行メモリのバスの幅は2個の要素を誤差行メモリから同期的に読み書きすることを可能にするステップと、
2)同じ列では同じ数になっている誤差位置であって、2個の列の誤差位置の各々を隣接して配列するステップと、
3)誤差行を0として初期化するステップと、
を含むことを特徴としている。
【0009】
本発明の効果を向上させるために、前記ステップ(b)は、さらに、
1)誤差バッファレジスタファイルを、誤差分散バッファレジスタファイルと誤差累積バッファレジスタファイルを含むようにセットし、当該誤差分散バッファレジスタは、誤差行内のある位置の相対ピクセルのすべてからの誤差分散値のすべてをストアするのに十分になっており、カレント相対ピクセルはカレント操作行内のピクセルのすべてとしてセットされ、その誤差値は誤差行内のその位置に分散させることができ、当該誤差累積バッファレジスタファイルは、カレント操作行(current operating row)の後に続くオリジナル誤差行の相対累積誤差値のすべてをストアするのに十分になっており、相対累積誤差値は、誤差行内のある位置のオリジナル累積誤差値を読み出してからその位置の新しい累積誤差値を書き込むまでの行程における誤差行内の読み取られたオリジナル累積誤差値のすべてとしてセットされ、
2)誤差バッファレジスタファイルを初期化し、当該誤差バッファレジスタファイルファイルは、各々の行の処理の開始時に0として初期化される、
ことを含むことを特徴としている。
【0010】
本発明の効果を向上させるために、前記ステップ(d)は、さらに、
1)カレントソースピクセルの位置と、次の行および同じ列における位置とに対応する累積誤差値を誤差行メモリから同期的に読み出し、
2)同じ行内の先行ピクセルのすべてによって生成された誤差の分散に由来するカレントソースピクセルの誤差値の総和Sを、誤差バッファレジスタファイルに照らして計算し、
3)カレントピクセルに対応する位置のオリジナル累積誤差値、総和Sおよびカレントソースピクセルの値を加算することによってピクセルの最終値を求め、当該最終値をしきい値と比較することによって最終ハーフトーンビットを発生させる、
ことを含むことを特徴としている。
【0011】
本発明の効果を向上させるために、前記ステップ(e)は、さらに、
1)隣接するピクセルのすべてについて、カレントピクセルによって発生した誤差の分散によって引き起こされた値Dをピクセルの最終値としきい値とに照らして求め、
2)誤差分散バッファレジスタファイル内の各ピクセルの誤差分散値を、その次のピクセルの誤差分散値として更新し、最終ピクセルの誤差分散値を値Dとして更新し、
3)誤差累積バッファレジスタファイル内の各ピクセルの累積誤差値をその次のピクセルの累積誤差値として更新し、最終ピクセルの累積誤差値をカレントピクセルに対応していて、次の行内の位置のオリジナル累積誤差値として更新し、
4)誤差行内の1つの列内の書き込まれたデータ値のすべてを誤差バッファレジスタファイルに照らして求め、書き込まれたデータ値を誤差行メモリに同期的に書き込み、そこでは、誤差行内の列におけるある位置の書き込まれたデータ値は、その位置のオリジナル累積誤差値と、その位置に分散され、誤差バッファレジスタファイルにストアされたすべての誤差分散値との総和に等しくなっている、
ことを含むことを特徴としている。
【0012】
上記方法を実施するために、本発明はハードウェア回路を使用した装置も提供する。この装置1は、誤差行メモリ(error row memory)2、誤差バッファレジスタファイル(error buffer register file)3、しきい値比較回路(threshold comparison circuit)4、誤差生成回路(error generation circuit)5、誤差バッファレジスタファイル制御回路(error buffer register file control circuit)6、グレー生成回路(gray generation circuit)7、および誤差行制御回路(error row control circuit)8を備える。さらに、誤差行メモリ2は処理期間中に誤差分散の結果をストアするために使用され、誤差バッファレジスタファイル3は中間誤差値をバッファリングするために使用され、グレー生成回路7は、ソースピクセル、誤差行メモリ2、および誤差バッファレジスタファイル3に結合され、誤差分散の後ソースピクセルの最終グレーレベルを生成するために使用される。しきい値比較回路4はグレー生成回路7に接続され、最終グレーレベルをしきい値と比較して最終ハーフトーンドットを発生させる。誤差生成回路5はグレー生成回路7に接続され、しきい値と最終グレーレベルに照らしてカレント誤差分散値を算出する。誤差バッファレジスタファイル制御回路6は誤差バッファレジスタファイルの更新と出力を制御するために使用され、誤差バッファレジスタファイル制御回路6の入力は誤差生成回路5、誤差行制御回路8および誤差バッファレジスタファイル3のフィードバックから得られ、誤差行制御回路8は誤差行メモリ2に結合され、誤差行メモリに対する読み書きアドレス、読み書き制御信号および読み書きデータを生成するために使用され、誤差行制御回路8の入力はカレント操作ピクセル、誤差バッファレジスタファイル制御回路6および誤差生成回路5を含む座標から得られる。また、当該装置が動作状態にあるとき、最終ピクセルのグレーレベルは、カレント操作ピクセル、誤差行メモリ2および誤差バッファレジスタファイル3に照らしてグレー生成回路7によって得られる。次に、ハーフトーンドットはしきい値比較回路4によって発生し、そのピクセルに対応する誤差分散値は最終ピクセルのグレーレベルに対して誤差生成回路5によって得られる。その後、誤差バッファレジスタファイル3および誤差行メモリ2は、それぞれ誤差バッファレジスタファイル制御回路6および誤差行制御回路8によって更新される。
【0013】
さらに、装置において本発明の効果を向上させるために、誤差バッファレジスタはトリガを含み、誤差分散バッファレジスタファイルおよび誤差累積バッファレジスタファイルを含んでおり、誤差分散バッファレジスタファイルは誤差行内のある位置の相対ピクセルのすべてからの誤差分散値のすべてをストアするのに十分になっており、カレント相対ピクセルはカレント操作行内のピクセルのすべてとしてセットされ、その誤差値は誤差行内のその位置に分散させることができ、誤差累積バッファレジスタファイルは、カレント操作行の後に続くオリジナル誤差行の相対累積誤差値のすべてをストアするのに十分になっており、相対累積誤差値は、誤差行内のある位置のオリジナル累積誤差値を読み出してからその位置の新しい累積誤差値を書き込むまでの行程における誤差行内の読み出されたオリジナル累積誤差値のすべてとしてセットされる。
【0014】
さらに、当該装置において本発明の効果を向上させるために、グレー生成回路は加算器を含み、当該加算器の入力はソースピクセル、誤差行から読み出されたカレント誤差値および誤差バッファレジスタファイル内のバッファリングされたカレント誤差値から得られる。グレー生成回路は、カレントソースピクセルの値、ピクセルに対応していて誤差行から読み出された誤差値、およびカレントピクセルをもつ行内の先行ピクセルによって当該カレントピクセルに対して生成された、誤差バッファレジスタファイル内のバッファリングされたカレント誤差値を加算することによってカレントピクセルの最終グレーレベルを得ている。
【0015】
さらに、当該装置において本発明の効果を向上させるために、誤差バッファレジスタファイル制御回路はn個のマルチプレクサを含み、ここでnは誤差バッファレジスタファイル内のレジスタの数であり、当該マルチプレクサは、処理するピクセルの各周期において各行の開始時に誤差バッファレジスタファイルの更新と初期化(ゼロにクリアする)を実行するために誤差バッファレジスタファイルの入力および制御信号を生成するために使用され、マルチプレクサの入力はカレント誤差分散値、カレント累積誤差値および誤差バッファレジスタファイル内のオリジナル値を含み、マルチプレクサの出力は誤差バッファレジスタファイル内のレジスタの更新値である。
【0016】
さらに、当該装置において本発明の効果を向上させるために、誤差行制御回路は、読み取りアドレスレジスタ、書き込みアドレスレジスタ、読み書き制御回路、および書き込みデータ生成回路を含み、当該読み取りアドレスレジスタおよび書き込みアドレスレジスタは、カレントピクセルの列番号別に生成され、当該書き込みデータ生成回路は加算器を含み、当該加算器の入力はオリジナル累積誤差値、カレント誤差分散値、およびバッファリングされた相対誤差値から得られる。
【発明の効果】
【0017】
本発明には次のような効果がある。すなわち、デジタル画像ハーフトーンの分野において、周波数変調ハーフトーンドットが誤差拡散法に基づく方法によって発生するとき、本発明の方法と装置は、各々のピクセルを処理する行程で一回の読み取り操作と一回の書き込み操作だけでメモリを操作する。さらに、本発明の方法と装置は特殊なハードウェア回路を使用して実現することができる。従って、周波数変調ハーフトーンドットを発生させる速度は向上する。
【発明を実施するための最良の形態】
【0018】
以下、添付図面と実施形態を参照して本発明を詳しく説明する。
【0019】
図1は、Floyd-Steinberg法に基づく誤差拡散(Error Diffusion)の原理を示す図である。カレントピクセル*の誤差は図1に示す4個の隣接ピクセルに分散される。
【0020】
図2は、Stucki法に基づく誤差拡散の原理を示す図である。カレントピクセル*の誤差は図2に示す12個の隣接ピクセルに分散される。一般的に、これらの12個の位置のいくつかは、誤差分散比率(error distribution ratio)が同じになっている。図2に示すアルゴリズムは、5つの異なる誤差分散比率だけを必要としており、そこではカレントピクセル*の誤差はD=1/44、D=2/44、D=5/44、D=4/44、およびD=8/44の比率で分散させることができる。一般的に、このアルゴリズムとS形状スキャニングプロセス(S-shaped scanning process)が採用されるときは、カレントピクセルからの後続2行の累積誤差分散値を格納するために誤差行(error row)が必要になる。従って、3個の誤差行が必要になり、これらの行の幅はソース画像の幅に等しくなっている。以上から理解されるように、ピクセルが処理されるとき、誤差行メモリ(error row memory)内の12個の位置上の累積誤差値を更新するために複数の読み書き操作が必要になる。
【0021】
図3は、Stucki法に基づく7ピクセル幅の画像と共に誤差行メモリを示す図であり、そこでは(i,j)は、ピクセルが誤差行において行iと列jの位置にあることを示している。公知のように、Stucki法に基づく誤差行は繰り返し使用することができる。従って、必要になる誤差行は3つだけであり、そこではi番目の行内のピクセルと(i+3)番目の行内のピクセルは同じ誤差行を使用している。
【0022】
図4に示すように、本発明は、画像に対してFMハーフトーンドットを高速で発生させることができる方法を提供しており、この方法は、
(1)列に編成し、誤差行メモリを初期化するステップと、
(2)誤差バッファレジスタファイルをセットするステップと、
(3)カレントソースピクセルを取得するステップと、
(4)カレントソースピクセル、誤差行および誤差バッファレジスタファイルに基づいてハーフトーンドットを発生させるステップと、
(5)誤差行および誤差バッファレジスタファイルを更新するステップと、
(6)ある行が完全に処理されたかどうかを判断し、処理されていなければ、プロセスはステップ(3)に戻され、処理されていれば、ステップ(7)を実行するステップと、
(7)画像が完全に処理されたかどうかを判断し、処理されていなければ、プロセスはステップ(2)に戻され、処理されていれば、プロセスを終了させるステップと、
を含んでいる。
【0023】
図5は、ステップ(1)におけるStucki法に基づく誤差行メモリを示す図であり、そこでは画像は7ピクセル幅になっており、(i,j)はピクセルが誤差行の行iと列jの位置にあることを示している。従来のコンピュータシステムでは、メモリのデータバスの幅は一般に16、32、64などの、2のn乗(nは一定の整数である)になっている。従って、本発明で使用される誤差行の数は2のn乗と定義されている。具体的には、Stucki法に基づく方法では、4個の誤差行が必要であり、これらの誤差行は繰り返し使用されている。すなわち、i番目の行内のピクセルと(i+4)番目の行内のピクセルは同じ誤差行を使用している。さらに、図5に示すように、本発明の方法と従来技術の方法との違いは、本発明の方法では誤差行は列に編成され(すなわち、同じ列では数が同じになっている誤差行の4つの列の要素は隣接して配列されている)、誤差行の同じ列内のすべての累積誤差値は32ビットのバス幅の誤差行メモリと共に同期的に読み書きされるようになっている。
【0024】
図6は、ステップ(2)におけるStucki法に基づく誤差バッファレジスタファイルを示す図であり、このファイルにはカレント操作ピクセルおよびカレント操作行内のいくつかの先行相関ピクセル(correlative pixels)の誤差分散値のすべてと、カレント操作行の後に続く複数のオリジナル誤差行の値とが含まれている。例えば、図2に示すStucki法では、誤差行内のある位置の誤差は多くても、カレント行内の5つのピクセルに由来しているので、誤差バッファレジスタファイルは、その行内の5個の隣接ピクセルの誤差分散値のすべてをストアしているはずである。さらに、カレント操作ピクセルの誤差は次の2行内の2つの先行ピクセルだけに分散させることができるので、当然に理解されるように、カレント行の後の次の行内の最終誤差値だけが誤差行メモリ内のオリジナル値に相対し、次の行の後の行内の誤差値はカレント行が処理される前は0に等しくなっている。カレント行の次の行のある位置の最終累積誤差値を書き込むことは、後続の2ピクセルに対応する誤差行が読み出されたあと実行される。この行程において、読み取られた誤差行は3つのオリジナル累積誤差値になっている。従って、誤差バッファレジスタファイルにストアする必要があるのは、次の行内の誤差行の3つのオリジナル値だけである。本実施形態では、図6に示すように、誤差バッファレジスタファイルは、5個の隣接ピクセルの誤差分散値のすべてと、次の行内の誤差行の3つのオリジナル値とをバッファリングすることができ、そこではPはカレント操作ピクセルとしてセットされ、P(i,j=1...5)は、それぞれ、誤差値Pおよび同じ行内の4つの先行隣接ピクセルの誤差値を示しており、P(i=3,4,5)は、それぞれ、読み取られた位置Pが誤差行メモリ内に置かれている行の後に続く行のオリジナル累積誤差値を示している。
【0025】
本発明の方法において、カレントソースピクセル、誤差行および誤差バッファレジスタファイルに照らしてハーフトーンドットを発生させるステップ(4)は以下のステップを含んでいる。
【0026】
1)カレントソースピクセルの位置と、次の行および同じ列内の位置とに対応する累積誤差値は、誤差行メモリから同期的に読み出される。誤差行は列に編成され、誤差行の数は誤差行メモリのバス幅に一致しているので、読み取りアドレスレジスタと書き込みアドレスレジスタはカレント操作ピクセルの列番号に照らして得られている。例えば、図2に示すStucki法によれば、カレント操作ピクセルの列番号がjであると想定すると、読み取りアドレスレジスタは4*jになっている。繰り返し使用される誤差行は4つであるので、誤差行が読み出された後、誤差行内のカレント操作ピクセルに対応するオリジナル累積誤差値Lは、カレント操作ピクセルの行番号の最後の2桁に従って得られる。誤差行における次の行内のピクセルに対応する値はLとしてセットされる。
【0027】
2)同じ行内の先行ピクセルのすべてによって発生した誤差の分散から得られるカレントソースピクセルの誤差値の総和Sは、誤差バッファレジスタファイルに従って計算される。図2に示すように、Stucki法によればS=P+Pである。
【0028】
3)ピクセルの最終値は、カレントピクセルに対応する位置のオリジナル累積誤差値LをSとカレントソースピクセルの値に加算することによって得られる。最終ハーフトーンビットはこの値をしきい値と比較することにより得られる。
【0029】
本発明の方法において、ステップ(5)は、さらに、以下のステップを含んでいる。
【0030】
1)カレントピクセルによって発生した誤差を分散させると引き起こされる、すべての隣接ピクセルの値Dは、ピクセルの最終値としきい値に照らして得られる。図2に示すStucki法によれば、分散比率はD=1/44、D=2/44、D=5/44、D=4/44およびD=8/44である。
【0031】
2)誤差分散バッファレジスタファイル内の各ピクセルの誤差分散値は、その次のピクセルの誤差分散値として更新され、最終ピクセルの値はDとして更新される。図2に示すStucki法によれば、PにはPi+1が割り当てられ、PにはD(i=1...4,j=1...5)が割り当てられる。
【0032】
3)誤差累積バッファレジスタファイル内の各ピクセルの累積誤差値は、その次のピクセルの累積誤差値として更新され、最終ピクセルの値は、カレントピクセルに対応していて、次の行内の位置上のオリジナル累積誤差値として更新される。例えば、図2に示すStucki法によれば、PにはPi+1(i=3,4)が割り当てられ、PにはLが割り当てられる。
【0033】
4)誤差行内のある列における書き込みデータ値のすべては誤差バッファレジスタファイルに照らして取得され、誤差行メモリに同期的に書き込まれ、そこでは誤差行内のある列におけるある位置の書き込みデータ値は、その位置上のオリジナル累積誤差値およびその位置に分散され、誤差バッファレジスタファイルにストアされた誤差分散値のすべての総和に等しくなっている。例えば、図2に示すStucki法によれば、カレント操作ピクセルがPであると想定すると、Pの前で、1ピクセルによってPから分離されたピクセルをもつ列の最終書き込みデータPLとPLは、次のように得ることができる。すなわち、PL=P+P+P+P+P+PおよびPL=P+P+P+P+P
本発明は、FMハーフトーンドットを高速で発生させることができる装置1も提供しており、装置は、図7に示すように、次の7つのコンポーネント、すなわち、誤差行メモリ2、誤差バッファレジスタファイル3、しきい値比較回路4、誤差生成回路5、誤差バッファレジスタファイル制御回路6、グレー生成回路7、および誤差行制御回路8を備えている。
【0034】
当該装置において、最終ピクセルのグレーレベルは、カレント操作ピクセル、誤差行メモリ2および誤差バッファレジスタファイル3に照らしてグレー生成回路7によって得られる。次に、ハーフトーンドットは、しきい値比較回路4によって発生され、そのピクセルに対応する誤差分散値は、最終ピクセルのグレーレベルに対して誤差生成回路5によって得られる。そのあと、誤差バッファレジスタファイル3および誤差行メモリ2は、誤差バッファレジスタファイル制御回路6および誤差行制御回路8によってそれぞれ更新される。
【0035】
当該装置において、累積誤差値をストアするために列に編成された誤差行メモリ2は、制御回路8に結合され、制御回路8の制御下に置かれている。
【0036】
誤差バッファレジスタファイル3は、中間誤差分散値をバッファリングするように構成されたハードウェアトリガを含んでいる。誤差バッファレジスタファイル3は、制御回路6に結合され、制御回路6の制御下に置かれている。
【0037】
グレー生成回路7は、ソースピクセルの最終グレーレベルを生成するために使用される。その入力端はソースピクセルと誤差バッファレジスタファイル制御回路6に結合され、その出力端はしきい値比較回路4と誤差生成回路5に結合されている。図8は、FMハーフトーンドットを高速で発生させることができる装置内のグレー生成回路を示すブロック図である。各ピクセルの最終グレーレベルは加算器によって生成され、ソースピクセル、そのピクセルに対応していて、誤差行から読み出されたカレント誤差値、および誤差バッファレジスタファイル内にあって、同じ列内のカレントピクセルに先行するピクセルによって生成されたカレントバッファリング誤差値の総和に等しくなっている。例えば、図2に示すStucki法によれば、この回路の論理式は、ピクセルの最終グレーレベル=ソースピクセル値+L+(P+P)になっている。
【0038】
しきい値比較回路4は、しきい値をグレー生成回路7によって生成されたグレーレベルと比較してハーフトーンを発生させるために使用される。しきい値比較回路4の入力端はグレー生成回路7に結合され、この回路4の出力は最終ハーフトーンドットである。
【0039】
誤差生成回路5はカレントピクセルの誤差分散値を、計算またはサーチによってグレー生成回路7によって生成されたグレーレベルに照らして生成するために使用される。誤差生成回路5の入力端はグレー生成回路7に結合され、この回路5の出力端は誤差バッファレジスタファイル制御回路6と誤差行制御回路8に結合されている。
【0040】
誤差バッファレジスタファイル制御回路6は、誤差バッファレジスタファイルの更新を制御するために使用される。この制御回路6の入力端は、誤差生成回路5、誤差行制御回路8および誤差バッファレジスタファイル3に結合され、この回路6の出力端は、誤差行制御回路8、誤差バッファレジスタファイル3およびグレー生成回路7に結合されている。図10は、FMハーフトーンドットを高速で発生させることができる装置内の誤差バッファレジスタファイル制御回路に含まれるマルチプレクサを示すブロック図である。n個のマルチプレクサを使用して、誤差バッファレジスタファイル制御回路は、1つのピクセルを処理した後、誤差バッファレジスタファイルを更新し、各行の開始時に初期化(ゼロにクリアする)する。ここでnは誤差バッファレジスタファイル内のレジスタの数である。すなわち、誤差バッファレジスタファイル内の各レジスタは1つのマルチプレクサに対応付けられている。1つのマルチプレクサの入力は、カレント操作ピクセルの誤差分散値(すなわち、カレント誤差分散値)、カレント操作ピクセルのあとの次の行内にあって、誤差行から読み出された累積誤差値、および誤差バッファレジスタファイル内のオリジナル値のすべてを含んでいる。また、1つのマルチプレクサのアウトプットは誤差バッファレジスタファイル内のレジスタにおける更新値である。例えば、図2に示すStucki法によれば、カレント誤差分散値Dとカレント累積誤差値Lが取得された後、1つのマルチプレクサの出力は、Pi+1がPに対応し、DがP(i=1...4,j=1...5)に対応し、Pi+1がPに対応し、LがPに対応するものとして示すことができる。
【0041】
誤差行制御回路8は、誤差行メモリ2の読み書きを制御するために使用される。誤差行制御回路8の入力は誤差生成回路5と誤差バッファレジスタファイル制御回路6から得られ、出力端はグレー生成回路7に結合されている。さらに、誤差行制御回路8は誤差行メモリ2に結合されている。図9は、FMハーフトーンドットを高速で発生させることができる装置内の誤差行制御回路を示すブロック図であり、この制御回路は読み取りアドレスレジスタ、書き込みアドレスレジスタ、読み書き制御回路、および書き込みデータ生成回路を含み、読み取りアドレスレジスタおよび書き込みアドレスレジスタはカレント操作ピクセルの座標に従って計算され、書き込みデータ生成回路は加算器を含んでいる。誤差行の書き込みデータの列は、オリジナル累積誤差値、カレント誤差分散値およびバッファリングされた相対誤差値に照らして書き込みデータ生成回路によって得られる。読み書き制御回路は、誤差行メモリの読み書き制御信号を生成するために使用される。例えば、図2に示すStucki法によれば、カレント操作ピクセルの列番号がjであると想定すると、読み取りアドレスレジスタは4*jであり、書き込みアドレスは4*(j-2)である。書き込みデータPLとPLの列は誤差行の書き込みデータ生成回路によって生成され、そこではPLはPL=P+P+P+P+P+Pとして示すことができ、PLはPL=P+P+P+P+Pとして示すことができる。
【0042】
図11は、ピクセルが本発明における方法に従って処理されるときの誤差行メモリの読み書きプロセスを示す図である。例えば、図2に示すStucki法によれば、シンボル*がカレント操作ピクセルを示すと想定すると、従来技術が使用される場合、PL、PL、L、Lおよび図11に示す誤差行内のXでマークしたすべての位置上のオリジナルコンテンツを、カレント操作ピクセル*の処理時に読み出す必要がある。カレント操作ピクセルを処理した後、カレントピクセルに隣接する12個の位置上の累積値を更新する必要もある。これに反して、本発明で提供している方法と装置を使用すると、カレントピクセル*を処理するとき、LとLが最初に誤差行メモリから読み出される。Lは最終グレーを生成するために使用され、Lは以後のPLの生成に備えてバッファリングされる。カレント操作ピクセルの誤差分散値Dが生成された後、当然に理解されるように、誤差行メモリ内のPLとPLの値を判断して、書き込むことができる。後続の行内のピクセルを処理する行程では、誤差行内のピクセルのコンテンツは変更されることがない。さらに、PLとPLの最終累積値を変更する相対誤差値のすべては誤差バッファレジスタファイルにバッファリングされるので、PLとPLの書き込みは、メモリを再び読み取ることなく完了することができる。誤差行は本発明によれば列に編成されている。従って、LとLを読み取るために必要なメモリの読み取り操作は一回で済み、PLとPLを書き込むのに必要なメモリの書き込み操作は一回で済むことになる。このことから明らかであるように、本発明における方法を使用すると、1つのピクセルを処理するときLとLを読み出すとき必要なメモリの読み取り操作は一回で済み、PLとPLを書き込むとき必要な書き込み操作は一回で済むことになる。従って、ハーフトーンドットを発生させる速度は大幅に向上されることになる。
【0043】
本発明の一実施形態について上述してきたが、本発明はその実施形態に限定されない。例えば、各誤差値が12個の隣接位置に分散するStucki法と関連付けて実施形態を上述してきたが、本発明は、誤差拡散の原理に基づく方法にも適応性があり、誤差をより多くのドットに分散されたハーフトーンドットを発生させることができる。従って、本発明の要旨と原理から逸脱しない限り、いかなる変更、置換および改良も本発明の範囲に属するものである。
【図面の簡単な説明】
【0044】
【図1】Floyd-Steinberg法に基づく誤差拡散の原理を示す図である。
【図2】Stucki法に基づく誤差拡散の原理を示す図である。
【図3】一般的にStucki法に基づく7ピクセル幅の画像と共に誤差行メモリを示す図である。
【図4】本発明の方法に従って画像を処理するフローチャートを示す図である。
【図5】本発明の方法に従ってStucki法に基づく7ピクセル幅の画像と共に誤差行メモリを示す図である。
【図6】本発明の方法に従ってStucki法に基づく誤差バッファレジスタファイルを示す図である。
【図7】本発明に従ってFMハーフトーンドットを高速で発生させる装置を示すブロック図である。
【図8】本発明に従ってFMハーフトーンドットを高速で発生させる装置におけるグレー生成回路を示すブロック図である。
【図9】本発明に従ってFMハーフトーンドットを高速で発生させる装置における誤差行の制御回路を示すブロック図である。
【図10】本発明に従ってFMハーフトーンドットを高速で発生させる装置における誤差バッファレジスタファイルの制御回路内のマルチプレクサを示すブロック図である。
【図11】本発明の方法に従ってピクセルが処理されるときの誤差行メモリの読み書きプロセスを示す図である。
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10