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

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

国内特許コード P150011631
掲載日 2015年3月30日
出願番号 特願2008-504606
公表番号 特表2008-535419
登録番号 特許第4481343号
出願日 平成18年3月31日(2006.3.31)
公表日 平成20年8月28日(2008.8.28)
登録日 平成22年3月26日(2010.3.26)
国際出願番号 CN2006000567
国際公開番号 WO2006105721
国際出願日 平成18年3月31日(2006.3.31)
国際公開日 平成18年10月12日(2006.10.12)
優先権データ
  • 200510063255.3 (2005.4.7) CN
発明者
  • リュウ ヂィホン
  • チェン フェン
  • ヤン ビン
出願人
  • 北大方正集▲団▼有限公司
  • 北京北大方正▲電▼子有限公司
  • 北京大学
発明の名称 高速でFM格子点の発生を可能にする方法および装置
発明の概要 本発明はデジタル画像ハーフトーンの分野に属し、周波数変調格子点(frequency-modulation lattice points)を高速で発生させることを可能にする方法および装置を開示している。従来技術では、ピクセルの処理時に誤差行に読み書き操作が多数回行なわれるため、格子点の生成が遅くなっている。本発明による方法では、カレントピクセルによって発生した誤差はレジスタスタックにバッファリングされ、最終誤差累積値が誤差行に書き込まれるのは、すべての相関ピクセルが処理された後だけであるので、処理されるピクセルごとに、誤差行に行なう読み書き操作は一回だけで済んでいる。本発明は当該方法を実現する装置も提供している。装置は7つの部分、すなわち、誤差行ストレージ、誤差バッファレジスタスタック、グレー生成回路、しきい値比較回路、誤差生成回路、誤差バッファレジスタスタック制御回路および誤差行制御回路から構成されている。本発明の方法と装置を採用すると、操作ステップ数は低減され、FM格子点の生成速度は大幅に向上する。
従来技術、競合技術の概要



デジタル画像ハーフトーンの技術としては、振幅変調スクリーニングと周波数変調スクリーニングとがある。誤差拡散法(Error Diffusion method)は、共通周波数変調スクリーニング法で広く使用されている。誤差拡散法では、ハーフトーンドットはオリジナル画像の各ドットのグレーレベルをしきい値と比較することによって作り出されているが、各ドットのグレーレベルとしきい値との差は隣接ドットに分散されている。例えば、256のグレーレベルを持つ画像では、しきい値は127にセットされている。比較後、グレーレベルが150であるドットはホワイトドット(white dot)になっている。しかし、このドットは、ドットのグレーレベルとホワイトドットとの間に差があるため、純粋にホワイトになっていないはずである。この誤差値23は、なんらかの手段によってそのドットの前後の隣接ドットに分散されている。





Floyd-Steinberg法(algorithm)は、誤差拡散法のための最も周知の共通アルゴリズムである。このアルゴリズムを使用すると、カレントドットのグレーレベルがしきい値と比較された後、ドットのグレーレベルは1または0にセットされる(すなわち、ドットはブラックドットまたはホワイトドットにセットされる)。次に、グレーレベルとしきい値との差を計算することによって誤差が求められる。最後に、誤差は隣接ドットのグレーレベルを調整するために隣接ドットに分散される。特に、Floyd-Steinberg法によると、誤差値の7/16がカレントドットに隣接し、その右側にあるドットに加算され、誤差値の5/16は、カレントドットに対応している次の行内のドットに加算され、誤差値の3/16は、次の行(row)内のカレントドットに対応するドットに隣接し、その左側にあるドットに加算され、誤差値の1/16は次の行内のカレントドットに対応するドットに隣接し、その右側にあるドットに加算される。このようにして、カレントドットの誤差は隣接ドットに分散される。このプロセスは画像内のすべてのドットごとに実行され、ハーフトーンを生成し、グレーレベルを改善する。





Stucki法(algorithm)などの、いくつかの改良アルゴリズムがFloyd-Steinberg法に基づいて出現している。Stucki法を使用すると、カレントドットによって発生した誤差はカレントドットの12個の隣接ドットに分散される。アウトプット画像の効果が向上しているのは、分散期間により多くのドットが関係しているためである。さらに、誤差を分散する期間に、各行のドットが左から右に向かって処理される場合、各行からの誤差は次の行の誤差に加算されるので、誤差が累積される。このようにすると、アウトプット画像は視覚に傾向を持つことになる。良好な効果を得るために、スキャンが行なわれるときS形状スキャン(S-shaped scan)が使用される。具体的に説明すると、画像全体について、奇数の行は左から右に向かってスキャンされ、偶数の行は右から左に向かってスキャンされる。





一般的に、誤差拡散法によると、良好な効果が得られる。しかし、この方法に欠点があることは明らかである。この方法によると、メモリにおける計算と操作の回数が多くなるためドットの発生速度が低速になっている。例えば、Stucki法をS形状スキャンと併用するとき、一般に誤差行メモリ(error row memory)と呼ばれているメモリは、誤差拡散の後、カレント行と次の2行の結果を格納するために使用されるのが一般的である。誤差行の各位置は対応する位置の累積誤差値(accumulated error value)を示している。従って、カレントピクセルおよび誤差行内の12個の隣接位置に対応するオリジナル累積誤差値は、すべてのピクセルを処理するために読み出される必要がある。カレントピクセルの計算誤差値が得られた後、その値は12個の隣接位置に分散される。各分散値は、対応する位置のオリジナル累積誤差値に加算され、その結果はそれぞれ誤差行内の12個の位置に書き込まれる。以上から明らかであるように、従来の方法では、メモリにおいて要求される操作が多くなっている。メモリの読み書き速度はコンピュータシステムのボトルネックになっている。従って、誤差拡散法に基づくスクリーニング法を適用する範囲が制限されているのは、アウトプット効果を向上できる一方でその処理速度によるためである。誤差拡散法に基づく方法でドットを発生させる速度を向上するために特殊なハードウェアが使用されるのが一般的であるが、メモリにおける操作が複数あるため、速度に影響を与え、リアルタイム機能を持つ高速プリンタや複写マシンの要求条件を満たすことが困難であるので、誤差拡散法に基づくスクリーニング法は、最新の高速プリンタや複写マシンに適用することが困難になっている。

産業上の利用分野



本発明はデジタル画像ハーフトーンの分野においてハーフトーンドットを発生させるための方法および装置に関し、さらに具体的には、周波数変調(FM)ハーフトーンドットを高速で発生させることができる方法および装置に関する。

特許請求の範囲 【請求項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)は、読み取りアドレスレジスタ、書き込みアドレスレジスタ、読み書き制御回路、および書き込みデータ生成回路を含み、
前記読み取りアドレスレジスタおよび書き込みアドレスレジスタは、カレントピクセルの列番号別に生成され、
前記書き込みデータ生成回路は加算器を含み、前記加算器の入力は、オリジナル累積誤差値、カレント誤差分散値およびバッファリングされた相対誤差値から得られることを特徴とする請求項に記載の装置。
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2008504606thum.jpg
出願権利状態 登録
分野
  • 電気
  • 物理学
※ 特許の内容に興味を持たれた方は、下記問合せ先にご相談下さい。


PAGE TOP

close
close
close
close
close
close