TOP > 中国の大学の特許 > 北京大学の特許一覧 > マルチサイトFMスクリーンドットを同時に生成する方法及び装置 > 明細書

明細書 :マルチサイトFMスクリーンドットを同時に生成する方法及び装置

発行国 日本国特許庁(JP)
公表番号 特表2010-504007 (P2010-504007A)
公報種別 特許公報(B2)
公表日 平成22年2月4日(2010.2.4)
特許番号 特許第5113174号 (P5113174)
登録日 平成24年10月19日(2012.10.19)
発行日 平成25年1月9日(2013.1.9)
発明の名称または考案の名称 マルチサイトFMスクリーンドットを同時に生成する方法及び装置
国際特許分類 H04N   1/405       (2006.01)
G06T   5/00        (2006.01)
G09G   5/00        (2006.01)
G09G   3/20        (2006.01)
B41J   2/52        (2006.01)
FI H04N 1/40 B
G06T 5/00 200A
G09G 5/00 520J
G09G 5/00 555G
G09G 3/20 641H
B41J 3/00 A
請求項の数または発明の数 11
全頁数 22
出願番号 特願2009-527680 (P2009-527680)
出願日 平成19年9月17日(2007.9.17)
国際出願番号 PCT/CN2007/002729
国際公開番号 WO2008/040162
国際公開日 平成20年4月10日(2008.4.10)
優先権出願番号 200610113131.6
優先日 平成18年9月15日(2006.9.15)
優先権主張国 中華人民共和国(CN)
審査請求日 平成22年8月18日(2010.8.18)
特許権者または実用新案権者 【識別番号】507231932
【氏名又は名称】北大方正集▲団▼有限公司
【氏名又は名称】PEKING UNIVERSITY FOUNDER GROUP CO., LTD
【識別番号】507232478
【氏名又は名称】北京大学
【氏名又は名称】PEKING UNIVERSITY
【識別番号】507232456
【氏名又は名称】北京北大方正▲電▼子有限公司
【氏名又は名称】BEIJING FOUNDER ELECTRONICS CO., LTD.
発明者または考案者 【氏名】チェン,ファン
【氏名】リュー,チーホン
【氏名】ウェン,シャオフイ
【氏名】チュー,ウェイ
個別代理人の代理人 【識別番号】110000051、【氏名又は名称】特許業務法人共生国際特許事務所
審査官 【審査官】秦野 孝一郎
参考文献・文献 特開2001-358942(JP,A)
特開2006-229928(JP,A)
特開2001-236249(JP,A)
特開平11-146202(JP,A)
特表2008-523739(JP,A)
調査した分野 H04N 1/405
G06T 5/00
G09G 3/20
B41J 3/00
特許請求の範囲 【請求項1】
マルチサイトFMスクリーンドットを同時に生成する方法であって、
画素点の最終誤差蓄積値及び中間誤差蓄積値を記憶するように構成された誤差行メモリを初期化するステップと、
誤差割当/蓄積レジスタファイルを初期化するステップと、
行・列をなす画素の各行ごとに、及び各行内のN個の近隣の画素からなるグループごとに、前記画素のオリジナルグレーレベル(ソース画素値)を取得し、前記誤差行メモリ及び前記誤差割当/蓄積レジスタファイルに記憶された値に従って前記N個の画素のスクリーンドットを生成するステップであって、N≧2であるステップと、
1つの前記グループ内のN個の近隣の画素が処理される毎に、前記誤差行メモリ及び前記誤差割当/蓄積レジスタファイル内の値を更新するステップと、を含み、
前記現在のN個の画素のオリジナルグレー値(レベル)、並びに、前記誤差行メモリ及び前記誤差割当/蓄積レジスタファイル内に記憶された値に従って前記N個の画素のスクリーンドットを生成する方法がさらに、
前記誤差行メモリから、前記現在のN個の近隣の画素に対応するN個の最終誤差蓄積値を読み取り、前記誤差割当/蓄積レジスタファイルによってN個の合計誤差割当値を取得するステップであって、前記N個の合計誤差割当値は、前記現在のN個の画素と同じ行内にあって、前記現在のN個の画素に先立って処理された全ての画素から得られる誤差割当値を合計することによって作り出されるステップと、
前記N個のオリジナルグレー値、前記N個の最終誤差蓄積値、及び前記N個の合計誤差割当値に従って、前記現在のN個の近隣の画素の最終グレー値を順次算出し、前記最終グレー値を用いて、前記Nサイトスクリーンドットを生成すると共に、周辺画素に対する前記現在のN個の画素からの誤差割当値を算出するステップと、を含む方法であって、
前記現在のN個の画素のいずれか1つが処理された後に、前記周辺画素のうち前記N個の画素の内の引き続いて処理すべき画素点に対して生成された誤差割当値が、前記引き続いて処理すべき画素点の最終グレー値を算出するために使用される、ことを特徴とする方法。
【請求項2】
前記誤差割当/蓄積レジスタファイルは、誤差割当レジスタファイル及び誤差蓄積レジスタファイルを含んでおり、前記誤差割当レジスタファイルは、フォローアップ誤差処理で使用するために、現在処理されている画素の前に処理された現在の行内の画素からの誤差割当値を記憶するように構成されており、前記誤差蓄積レジスタファイルは、前記誤差行メモリから読み取られた画素点の中間誤差蓄積値をキャッシングするように構成されて
いる、ことを特徴とする請求項1に記載の方法。
【請求項3】
前記誤差行メモリから、前記N個の近隣の画素に対応するN個の最終誤差蓄積値を読み取ると共に、前記N個の近隣の画素に対して後続する行内の対応するN個の近隣の画素の中間誤差蓄積値を読み取る、ことを特徴とする請求項1に記載の方法。
【請求項4】
前記誤差行メモリ内のデータを更新する方法は、
前記現在の行内のN個の近隣の画素Pi,j~Pi,j+N-1を処理した後に、前記誤差割当/蓄積レジスタファイルに記憶された中間誤差蓄積値及び現在の行内の先行して処理された画素からの誤差割当値に従って、現在の行iの次の行(i+1)内のN個の近隣の画素Pi+1,j-N~Pi+1、j-1の最終誤差蓄積値、及び現在の行の2つ先の行(i+2)内の対応するN個の近隣の画素Pi+2、j~Pi+2、j-1の中間誤差蓄積値を得るステップを含んでいる、ことを特徴とする請求項に記載の方法。
【請求項5】
前記誤差割当/蓄積レジスタファイル内のデータを更新する方法は、
前記誤差割当レジスタファイル内の各N個の近隣の画素の誤差割当値を全て列としてとるステップと、N個の近隣の画素の次の列の誤差割当値となるようにN個の近隣の画素の前の列の誤差割当値を更新するステップと、現在のN個の近隣の画素の誤差割当値となるようにN個の近隣の画素の最終列の誤差割当値を更新するステップと、現在のN個の近隣の画素に対応する次の行(i+1)のN個の近隣の画素Pi+1、j~Pi+1、j+N-1の中間誤差蓄積値となるように誤差蓄積レジスタファイル内のオリジナルのN個の近隣の画素Pi+1,j-N~Pi+1,j-1の中間誤差蓄積値を更新するステップとを含む、ことを特徴とする請求項2に記載の方法。
【請求項6】
ソース画素のオリジナルグレー値はスキャンによって得られ、スキャンはS字形である、即ち偶数行では左から右に、奇数行では右から左へ、又はその逆のスキャンである、ことを特徴とする請求項に記載の方法。
【請求項7】
誤差行メモリのバス幅がN×W×(H-1)であり、Nは現在同時に処理されている画素の数のことであり、Wは誤差行メモリ内の1つの位置でのデータ幅であり、Hは現在処理されている画素が置かれる行を含む、1つの画素の誤差を拡散することができる行の数である、ことを特徴とする請求項1に記載の方法。
【請求項8】
マルチサイトFMスクリーンドットを同時に生成する装置(1)であって、
誤差行メモリ(2)、及びこれに接続された誤差行メモリ制御回路(4)と、
誤差割当/蓄積レジスタファイル(3)、及びこれに接続された誤差割当/蓄積レジスタファイル制御回路(5)と、
グレー生成回路(7)、並びに、それぞれ、前記グレー生成回路の出力端部に接続された閾値比較回路(8)及び誤差生成回路(9)からなり、1つの画素の最終スクリーンドット、及びこの画素から周辺画素への誤差割当値を生成するように構成されている、複数のスクリーンドット生成回路(10)とを備えた装置であって、
前記スクリーンドット生成回路(10)それぞれの誤差生成回路(9)の出力端部が、前記スクリーンドット生成回路(10)に後続するスクリーンドット生成回路(10)内のグレー生成回路(7)の入力端部に接続されていると共に、前記誤差行メモリ制御回路(4)及び前記誤差割当/蓄積レジスタファイル制御回路(5)の入力端部に接続されており、
前記誤差行メモリ制御回路(4)及び前記誤差割当/蓄積レジスタファイル制御回路(5)の出力端部が、前記各スクリーンドット生成回路(10)内の前記グレー生成回路(7)の入力端部に接続されており、
前記誤差行メモリ制御回路(4)は、読取アドレスレジスタ、書込アドレスレジスタ、読取/書込制御回路、及び書込データ生成回路を備えており、前記読取アドレスレジスタ及び前記書込アドレスレジスタは、現在処理されている画素のうちの第1の画素の列数(アドレス)に合わせて生成され、前記書込データ生成回路は加算器からなり、前記加算器の入力は、前記誤差蓄積値、現在の画素全てを処理した後に生成された前記誤差割当値、及び前記誤差割当レジスタファイルに記憶された関連する誤差割当値からもたらされる、ことを特徴とする装置。
【請求項9】
前記誤差割当/蓄積レジスタファイル(3)は、トリガからなるレジスタアレイによって達成され、誤差割当レジスタファイル及び誤差蓄積レジスタファイルを備えており、前記誤差割当レジスタファイルは、フォローアップ誤差処理に有用であり、現在処理されている画素に先行して処理された現在の行内の画素からの誤差割当値を記憶するように構成されており、前記誤差蓄積レジスタファイルは前記誤差行メモリから読み取った画素点の中間誤差蓄積値をキャッシングするように構成されている、ことを特徴とする請求項に記載の装置。
【請求項10】
前記誤差行メモリ制御回路(4)は、前記誤差行メモリの読取/書込アドレス、読取/書込制御信号、及び読取/書込データを生成するために前記誤差行メモリ(2)に接続されており、前記誤差行メモリ制御回路(4)の入力は、現在処理されている画素のうちの第1の画素の座標(アドレス)、前記誤差割当/蓄積レジスタファイル制御回路(5)の出力、及び前記スクリーンドット生成回路(10)の各グループの前記誤差生成回路(9)の出力を含んでいる、ことを特徴とする請求項に記載の装置。
【請求項11】
前記誤差割当/蓄積レジスタファイル制御回路(5)は、前記誤差割当/蓄積レジスタファイル(3)のデータを更新及び初期化するために、前記誤差割当/蓄積レジスタファイル用の制御信号を生成する複数のマルチプレクサを備えている、ことを特徴とする請求項に記載の装置。
発明の詳細な説明 【技術分野】
【0001】
本発明は、デジタル画像ハーフトーニング(half-toning)の分野のスクリーンドット生成方法及び装置に関し、より詳細には、マルチサイト周波数変調(FM)スクリーンドットを同時に生成する方法及び装置に関する。
【背景技術】
【0002】
誤差拡散は、最も一般的に使用されるFMスクリーニング方法である。この方法によると、ソース画像の各画素点のグレーレベルを、スクリーンドットを生成させる閾値と比較し、画素点のグレーレベルと閾値の誤差がその画素点の周辺の画素点に拡散される。例えば、256グレーレベルの画像で閾値が127であり、特定の画素点のグレーレベルが150である場合、閾値との比較の結果、その画素点は白色スクリーンドット(白色スクリーンドットのグレーレベルは255である)として記録されなければならない。実際にはこの画素点は本当の白色ではないから、本当の白色に対して105の誤差値を有し、105の誤差は何らかの方法でこの画素点の周りの画素点に拡散される。一般的な誤差拡散方法としては、Floyd-Steinbergアルゴリズム、及びJarvisアルゴリズムがある。
【0003】
Floyd-Steinbergアルゴリズムは、1つの画素の誤差を、この画素を囲む4つの画素点に割り当てることを言う。即ち、誤差の7/16が現在の画素点の右側にある第1の画素点に加えられ、誤差の5/16が現在の画素点に対して次の行で同一位置にある第2の画素点に加えられ、誤差の3/16が第2の画素点の左側にある第3の画素点に加えられ、誤差の1/16が第2の画素点の右側にある画素点に加えられる。この過程は、繰り返し行なわれ、グレーレベル及びハーフトーニングの同じ修正が画像内の各画素点に対して行なわれる。
【0004】
Jarvisアルゴリズムでは、図1(A)に示すように、現在の画素Xの誤差を12個の近隣の(neighboring)画素に割り当てる。12個の画素位置のうちのいくつかの位置の画素に対する誤差割り当て比が同一であり、従って4種の異なる誤差割り当て比のみが必要であり、現在の画素Xの誤差を画素位置D~Dに対して各々、D=1/48、D=3/48、D=5/48、及びD=7/48の比で割り当てる。Jarvis誤差拡散方法に基づく画像ハーフトーニング処理は、誤差拡散の範囲を拡大することによってより優れた効果を達成することができるが、この方法による誤差拡散は、より多くの行及びより多くの画素点が関係するので記憶容量の増加及び処理速度の低下につながり、従ってリアルタイム要求を満たすことができず、応用分野は限られる。
【0005】
加えて、上記アルゴリズムを使用した誤差拡散の最中に、ソース画像が常に単方向スキャンのみにより処理される場合、各スキャン行の誤差は次の行に単純に加算され、出力パターンにおける画像の駆動傾向(driving_tendency)によって示される誤差蓄積につながる。従って、スキャン方法としては、S字形スキャンを通常採用する。即ち、奇数行に対しては図1(A)に示すような誤差割り当て比を用いて左から右へスキャンし、偶数行に対しては図1(B)に示すような誤差割り当て比を用いて右から左へのスキャン(又は、その逆)する。スキャンは、最終行までこのように繰り返される。
【0006】
特許文献1は、高速でFMスクリーンドットを生成する方法を開示しており、この方法はメモリの操作回数を減少できるが、画像を1時に1個ごとしか処理できないので、多数の画素を同時に処理できず、従って多数のスクリーンドットを同時に生成できない。
【0007】
特許文献2は、誤差拡散の並列処理方法を開示している。この方法は複数の画素点を同時に処理できるが、メモリ上で多数の読取/書込操作を行なう必要がある一方、S字形画像スキャンをソース画像上で実行できないので、スクリーンドットの生成速度に影響し、その結果、誤差蓄積により生じる駆動効果の排除がうまく行かなくなる。
【先行技術文献】
【0008】

【特許文献1】中国特許出願CN200510063255.3号(2005年9月14日公開)
【特許文献2】米国特許5271070号「Multi-dimensional error diffusion technique」
【発明の概要】
【発明が解決しようとする課題】
【0009】
本発明は、上記従来技術の欠点に鑑みて、複数の画素を同時に処理するにも拘わらず、メモリの読取及び書込回数を格段に削減し、FMスクリーンドットの生成速度を向上できる、マルチサイトFMスクリーンドットを同時に生成する方法及び装置を提供することを目的としている。
【課題を解決するための手段】
【0010】
本発明による、マルチサイトFMスクリーンドットを同時に生成する方法は、
画素点の最終誤差蓄積値及び中間誤差蓄積値を記憶するように構成された誤差行メモリを初期化するステップと、
誤差割当/蓄積レジスタファイルを初期化するステップと、
行・列をなす画素の各行ごとに、及び各行内のN個の近隣の画素からなるグループごとに、前記画素のオリジナルグレーレベル(ソース画素値)を取得し、前記誤差行メモリ及び前記誤差割当/蓄積レジスタファイルに記憶された値に従って前記N個の画素のスクリーンドットを生成するステップであって、N≧2であるステップと、
1つの前記グループ内のN個の近隣の画素が処理される毎に、前記誤差行メモリ及び前記誤差割当/蓄積レジスタファイル内の値を更新するステップと、を含み、
前記現在のN個の画素のオリジナルグレー値(レベル)、並びに、前記誤差行メモリ及び前記誤差割当/蓄積レジスタファイル内に記憶された値に従って前記N個の画素のスクリーンドットを生成する方法が、さらに、
前記誤差行メモリから、前記現在のN個の近隣の画素に対応するN個の最終誤差蓄積値を読み取り、前記誤差割当/蓄積レジスタファイルによってN個の合計誤差割当値を取得するステップであって、前記N個の合計誤差割当値は、前記現在のN個の画素と同じ行内にあって、前記現在のN個の画素に先立って処理された全ての画素から得られる誤差割当値を合計することによって作り出されるステップと、
前記N個のオリジナルグレー値、前記N個の最終誤差蓄積値、及び前記N個の合計誤差割当値に従って、前記現在のN個の近隣の画素の最終グレー値を順次算出し、前記最終グレー値を用いて、前記Nサイトスクリーンドットを生成すると共に、周辺画素に対する前記現在のN個の画素からの誤差割当値を算出するステップと、を含む方法であって、
前記現在のN個の画素のいずれか1つが処理された後に、前記周辺画素のうち前記N個の画素の内の引き続いて処理すべき画素点に対して生成された誤差割当値が、前記引き続いて処理すべき画素点の最終グレー値を算出するために使用される

【0011】
本発明による、マルチサイトFMスクリーンドットを同時に生成する装置は、
誤差行メモリ、及びこれに接続された誤差行メモリ制御回路と、誤差割当/蓄積レジスタファイル、及びこれに接続された誤差割当/蓄積レジスタファイル制御回路と、グレー生成回路、並びに、それぞれ、前記グレー生成回路の出力端部に接続された閾値比較回路及び誤差生成回路からなり、1つの画素の最終スクリーンドット、及びこの画素から周辺画素への誤差割当値を生成するように構成されている、複数のスクリーンドット生成回路とを備えた装置であって、
前記スクリーンドット生成回路それぞれの誤差生成回路の出力端部が、前記スクリーンドット生成回路に後続するスクリーンドット生成回路内のグレー生成回路の入力端部に接続されていると共に、前記誤差行メモリ制御回路及び前記誤差割当/蓄積レジスタファイル制御回路の入力端部に接続されており、
前記誤差行メモリ制御回路及び前記誤差割当/蓄積レジスタファイル制御回路の出力端部が、前記各スクリーンドット生成回路内の前記グレー生成回路の入力端部に接続されており、
前記誤差行メモリ制御回路は、読取アドレスレジスタ、書込アドレスレジスタ、読取/書込制御回路、及び書込データ生成回路を備えており、前記読取アドレスレジスタ及び前記書込アドレスレジスタは、現在処理されている画素のうちの第1の画素の列数(アドレス)に合わせて生成され、前記書込データ生成回路は加算器からなり、前記加算器の入力は、前記誤差蓄積値、現在の画素全てを処理した後に生成された前記誤差割当値、及び前記誤差割当レジスタファイルに記憶された関連する誤差割当値からもたらされる
【発明の効果】
【0012】
本発明による方法及び装置は、画像の同じ行に属する複数の近隣の画素点を同時に処理してマルチサイトスクリーンドットを生成し、1回の読取操作及び1回の書込操作のみにより誤差行メモリ内の複数の誤差蓄積値の更新を達成できるので、それによりメモリの読取及び書込回数を格段に削減し、FMスクリーンドットの生成速度を向上できる。
【図面の簡単な説明】
【0013】
【図1】(A)は、S字形スキャン中のJarvisアルゴリズムに基づいた偶数行内の画素Xの誤差拡散原理の略図であり、 (B)は、S字形スキャン中のJarvisアルゴリズムに基づいた奇数行内の画素Xの誤差拡散原理の略図であり、 (C)及び(D)は、Jarvisアルゴリズムに基づいた誤差拡散割当の略図である。
【図2】は、本発明の一実施形態による、同じ行内の多数の近隣の画素を処理する高速FMスクリーンドット生成装置のブロック図である。
【図3】は、図2に示すような装置内のスクリーンドット生成回路のブロック図である。
【図4】は、本発明の一実施形態による同じ行内の多数の近隣の画素を処理する高速FMスクリーンドット方法のフローチャートである。
【図5】は、本発明の一実施形態によるJarvisアルゴリズムに基づく同じ行内の2つの隣接する画素を処理する高速FMスクリーンドット生成装置のブロック図である。
【図6】(A)は、図2に示すような装置のグレー生成回路Iの原理図であり、 (B)は、図2に示すような装置のグレー生成回路IIの原理図である。
【図7】(A)は、本発明の一実施形態によるJarvisアルゴリズムに基づく同じ行内の2つの隣接する画素を処理する高速FMスクリーンドット生成装置内の8画素の画像幅を有する誤差行メモリの略図であり、 (B)は、処理した画像の特定の3つの隣接する行の画素点の一部の略図である。
【図8】は、図2に示すような装置内の誤差行メモリを読み取り、これに書き込むプロセスの略図である。
【図9】は、図2に示すような装置内の誤差行メモリ制御回路のブロック図である。
【図10】は、図2に示すような装置の誤差割当/蓄積レジスタファイルの構造の略図である。
【図11】は、図2に示すような装置内の誤差割当/蓄積レジスタファイル制御回路内のマルチプレクサの操作原理の略図である。
【図12】は、図2に示すような装置の誤差割当/蓄積レジスタファイル内のデータを更新するプロセスの略図である。
【発明を実施するための形態】
【0014】
本発明を、説明の図面及びその実施形態と合わせて以下にさらに詳細に説明する。

【0015】
本発明による誤差拡散装置を採用した基本的原理及び装置を、最初に簡単に説明する。

【0016】
誤差拡散中、各点はその周りの点への誤差拡散を有する。それに応じて、現在処理される点は、周りの点の誤差拡散によって影響を受ける。従って、現在の画素点に影響を与える全ての点は、現在の画素点を処理するために処理されなければならない。(以下、「画素点」「点」「画素」「サイト」は同義に用いる。)

【0017】
Floyd-Steinbergアルゴリズムを例としてとると、1つの画素点の誤差がその周りの4点に拡散されるので、規則を簡単に得ることができる、即ち、あらゆる画素点がその周りの4点の誤差拡散によって影響を受けるだけである。即ち、1つの画像がn行及びm列に配置された画素点からなり、iは行番号、jは列番号(これらi、jは、以下同じ意味で使う)とすると、行(i-1)の画素点Pi-1,j+1を処理した時点で初めて、行(i-1)の画素点からの誤差拡散のうち画素点Pi,jに集束する誤差拡散を全て算出することができる。
従って、画素点Pi,jに対する行(i-1)の点からの誤差拡散の蓄積値は、行(i-1)の残りの点が全て処理されるまでのあいだ記憶しておくメモリが必要があり、この誤差蓄積値は、行(i)の各点を処理する際に抽出されて、Pi,jのスクリーンドット値及び周りの画素への画素点Pi,jからの誤差拡散を算出する際に使われる。画像が多数の行をなす画素点からなり、このようなメモリは、一般に画素点の誤差蓄積値を行ごとに記憶するので、誤差行メモリと呼ばれる。本発明の一実施形態によると、SRAM(静的ランダムアクセスメモリ)が誤差行メモリとして採用される。

【0018】
この場合、特定の画素点の、スクリーンドット値及び誤差拡散を算出する場合、最初に、この現在の画素のソースグレーレベルを取得し、誤差行メモリから読み取ったこの時点での直前の行の画素点からの誤差蓄積値を加え、さらに、この現在の画素点が乗っている行の、この現在の画素点に先行する画素点からの誤差拡散を加えて、この現在の画素点の最終グレーレベルを得る。この画素のスクリーンドットは、得られた最終グレーレベルと閾値を比較することによって生成でき、この画素がその周りの点に割り当てる誤差値を得ることもできる。本発明では、先行誤差拡散でもある、誤差拡散アルゴリズムにより近隣の画素に割り当てられた各画素の誤差値は、誤差割当値と呼ばれる。

【0019】
このように1つの画素点からその周りの点への誤差割当値を得た後、これらの誤差割当値は、画素の誤差拡散によって影響を受ける画素点を処理するためにある期間一時的に記憶させる必要がある。本発明によると、レジスタグループがこの誤差割当値を一時的に記憶するために使用され、誤差割当レジスタファイルと呼ばれる。

【0020】
同じ理由によって、Jarvisアルゴリズムは、現在の画素を処理している間に、現在処理している画素に続く最大2画素点及び後続する2行の10個の画素点に誤差拡散を生成するので、この行から次の2行への誤差拡散を記憶させる必要がある。図1(A)は、その周りの画素への画素点Xからの誤差拡散を示しており、D、D、D及びDは誤差拡散係数を示している。この場合、その周りの画素への画素点Xの誤差割当値は、ED、ED、ED及びEDによって示すことができ、ここで、Eは拡散させる必要がある誤差である。一方、図1(C)に示すように、任意の画素点*は、先行する2行の最大10個の画素点及び現在の行の先行する2個の画素点によって影響される。このような影響は、一度に算出することはできず、各行のデータのバッチ処理で生成され、従って、各バッチで生成される誤差拡散値は最終グレー値を生成するために記憶させる必要があることを理解すべきである。

【0021】
即ち、任意の画素点Pi,jに対して、最初に、行(i-2)の点Pi-2,j+2が処理された後、画素点Pi,jに集束する行(i-2)の全ての画素点の誤差拡散が算出でき、画素点Pi,jに対する行(i-2)からの誤差蓄積値を生成できる。これを中間誤差蓄積値Li,j’と呼び、誤差行メモリに記憶する。その後、行(i-1)での画素点Pi-1,j+2が処理された後、画素点Pi,jに対する行(i-1)からの誤差蓄積値が生成され、誤差行メモリ内に前に記憶された中間誤差蓄積値Li,j’を読み取り、この画素点に対して行(i-1)によって生成された誤差蓄積値を加えて、画素点Pi,jでの直前の2行(行(i-1)及び行(i-2))からの合計誤差蓄積値、即ち最終誤差蓄積値Li,jを得る。

【0022】
図1(D)に示すように、Pi,j点*を処理した後に、画素点Pi+1,j-2(図1(D)の@)に対する行(i-1)及び(i)からの最終誤差蓄積値Li+1,j-2、及び画素点Pi+2,j-2(図1(D)の@’)に対する行(i)の中間誤差蓄積値Li+2,j-2’が、同時に生成される。便宜上、両者はデータパケットとして取り扱い、誤差行メモリ内に同時に記憶させることができる。この場合、画素点Pi+1,j-2(@)の最終グレー値を算出する場合、画素点Pi+1,j-2の最終誤差蓄積値Li+1,j-2を誤差行メモリから読み取る必要があり、同じデータパケット内の画素点Pi+2,j-2(@’)の中間誤差蓄積値Li+2,j-2’もメモリから同時に読み取られる。しかし、中間誤差蓄積値Li+2,j-2’は、Pi+2,j-2(@’)に対する行(i+1)からの誤差割当値を処理し、最終誤差蓄積値を算出するためにのみ使用され、従って、レジスタに一時的に記憶させる必要がある。

【0023】
このように、最終誤差蓄積値と共に同時に読み取られた中間誤差蓄積値を、後で新しく生成される最終誤差蓄積値の算出に参加させるために、一時的に記憶するためには、本発明によると誤差蓄積レジスタファイルと呼ばれる、読み取った中間誤差蓄積値を記憶する新しいレジスタファイルを設ける必要がある。

【0024】
本発明は、同じ行のN個(N≧2)の近隣の画素点を処理し、それによって誤差拡散方法に基づいてマルチサイトFMスクリーンドットを同時に生成することができる方法及び装置を提供する。
図2は、本発明により多数の近隣の画素を同時に処理する高速FMスクリーンドット装置(1)のブロック図である。高速FMスクリーンドット装置(1)は、誤差行メモリ(2)と、誤差割当/蓄積レジスタファイル(3)と、誤差行メモリ制御回路(4)と、誤差割当/蓄積レジスタファイル制御回路(5)と、スクリーンドット生成装置(6)とを備えている。前記部品の機能を、以下に簡単に説明する。

【0025】
上に記載したように、特定の画素Pi,jを処理している間、これに対する周りの画素の影響を蓄積する必要がある。画素Pi,jに対する周りの画素の影響は、以下の通り2つの部分に分けることができる。
一は、画素Pi,jの属する行(i)に先行する行によって生じる誤差影響、即ち最終誤差蓄積値又は中間誤差蓄積値であり、誤差行メモリ(2)はコンテンツのこのような部分を記憶するのに使用される。
また他は、画素Pi,jの属する行(i)の、画素Pi,jの前に位置する画素点によって生じる誤差影響、即ち行(i)の画素Pi,jに対する現在の画素の前に位置する画素点からの誤差割当値の合計であり、各先行画素点の誤差割当値が誤差割当/蓄積レジスタファイル(3)内に記憶される。誤差割当/蓄積レジスタファイル(3)はまた、使用される誤差行メモリ(2)から読み取られた中間誤差蓄積値などの、画素処理中の中間処理値をキャッシングするのに使用される。

【0026】
誤差行メモリ(2)に接続された誤差行メモリ制御回路(4)は、誤差行メモリ(2)の入力及び出力を制御する。誤差割当/蓄積レジスタファイル(3)に接続された、誤差割当/蓄積レジスタファイル制御回路(5)は、誤差割当/蓄積レジスタファイル(3)の入力及び出力を制御する。

【0027】
図2に示すように、スクリーンドット生成装置(6)は、多数のスクリーンドット生成回路(10)からなる。
図3は、グレー生成回路(7)と、閾値比較回路(8)と、誤差生成回路(9)とを備えた、本発明によるスクリーンドット生成回路(10)を示している。グレー生成回路(7)の入力は、画素Pi,jのソース画素値、この画素に対応する誤差行メモリ内の最終誤差蓄積値、及びこの画素に対する同じ行内の画素の前の画素によって生成される誤差割当値であり、スクリーンドット生成回路の出力は最終スクリーンドット、及びこの画素を処理した後に生成される誤差割当値である。本発明の装置によると、処理可能な画素の数は、含んでいるスクリーン生成回路(10)のグループの数と同じである。

【0028】
図4は、本発明により、同じ行内のN個の近隣の画素を同時に処理する方法のフローチャートであり、以下のステップS1~S7を含む、。
S1、誤差行メモリを初期化するステップ
S2、誤差割当/蓄積レジスタファイルを初期化するステップ
S3、行列をなす画素の各行ごとに、且つ各行内のN個の近隣の(neighboring)画素からなるグループごとに、前記画素のオリジナルグレーレベル(ソース画素値)を取得し、誤差行メモリと誤差割当/蓄積レジスタファイルに記憶された値に応じてNサイトスクリーンドットを生成するステップ
S4、1つのグループ内のN個の近隣の画素が処理される毎に、誤差行メモリ及び誤差割当/蓄積レジスタファイルを更新するステップ
S5、1つの行の処理が終了したかどうかを判断し、そうでない場合、S3に進み、そうである場合S6に進むステップ
S6、誤差行メモリを再び更新するステップ
S7、画像処理が終了したかどうかを判断し、そうでない場合、S2に進み、そうである場合、処理が終了するステップ

【0029】
本発明の方法によると、同じ行内の多数の近隣の画素を同時に処理して、マルチサイトスクリーンドットを生成することができる。また、ステップS3内のスキャンはS字形であってもよい、即ち、ある行内のソース画素は左から右に処理され、次の行内のソース画素は右から左に処理される。

【0030】
Jarvisアルゴリズムに基づいて、2サイトスクリーンドットを同時に生成する場合を例として取り上げ(即ち、N=2)、本発明による装置及び方法を以下に詳細に説明する。

【0031】
図5は、Jarvisアルゴリズムに基づいており、本発明により同じ行内の2つの隣接する画素を同時に処理することができる、高速FMスクリーンドット生成装置を示している。図5に示すように、装置(11)は、誤差行メモリ(12)、誤差割当/蓄積レジスタファイル(13)、誤差行メモリ制御回路(14)、誤差割当/蓄積レジスタファイル制御回路(15)、グレー生成回路I(16)、閾値比較回路I(17)、誤差生成回路I(18)、グレー生成回路II(19)、閾値比較回路II(20)、及び誤差生成回路II(21)の10個の部品を備えている。装置内のグレー生成回路I(16)、閾値比較回路I(17)、及び誤差生成回路I(18)は、スクリーンドット生成回路(10)の第1のグループを構成し、グレー生成回路II(19)、閾値比較回路II(20)、及び誤差生成回路II(21)は、スクリーンドット生成回路(10)の第2のグループを構成する。
[グレー生成回路]

【0032】
図5に示すように、グレー生成回路I(16)は、ソース画素1の最終グレー値を生成するために使用され、グレー生成回路I(16)の入力はソース画素1、誤差行メモリ制御回路(14)及び誤差割当/蓄積レジスタファイル制御回路(15)に接続され、その出力は閾値比較回路I(17)及び誤差生成回路I(18)に供給される。

【0033】
グレー生成回路II(19)は、ソース画素2の最終グレー値を生成するために使用され、グレー生成回路IIの入力は、ソース画素2、誤差行メモリ制御回路(14)及び誤差割当/蓄積レジスタファイル制御回路(15)に接続され、その出力は閾値比較回路II(20)及び誤差生成回路II(21)に供給される。

【0034】
図6(A)は、本実施形態によるグレー生成回路I(16)の動作原理を示している。この図に示すように、画素1の最終グレー値は加算器によって生成される。即ち、
画素1の最終グレー値= 画素1のソース画素値 + 画素1に対応する誤差行メモリ(12)から読み取られた最終誤差蓄積値 + 誤差割当/蓄積レジスタファイル(13)内でキャッシングされた、画素1が属する同じ行内の前に位置する画素からの誤差割当値。

【0035】
図6(B)は、本実施形態によるグレー生成回路II(19)の動作原理を示している。この図に示すように、画素2の最終グレー値は加算器によって生成される。即ち、
画素2の最終グレー値= 画素2のソース画素値 + 誤差行メモリ(12)から読み取られた画素2に対応する最終誤差蓄積値 + 誤差割当/蓄積レジスタファイル(13)内でキャッシングされた、画素2が属する同じ行内の前に位置する画素からの誤差割当値 + 画素1を処理することによって生成される現在の画素2に対する誤差割当値。

【0036】
このようにして得られた画素の最終グレー値は、スクリーンドットを生成するために閾値比較回路に運ばれ、同時に、その周囲の点に対するこの画素からの誤差割当値を得るために誤差生成回路に運ばれる。

【0037】
上記装置が2つの隣接する画素を同時に処理し、2サイトスクリーンドットを生成できる理由は一つには、スクリーンドット生成回路(10)の2つのグループの間の密接な関係にある。図5及び図6(B)に示すように、画素1の誤差生成回路I(18)によって出力された誤差割当値のうち画素2に割当てられた値は、画素2のグレー生成回路II(19)に直接入力され、誤差割当/蓄積レジスタファイル(13)内に登録される必要はない。
[誤差行メモリ及びその制御回路]

【0038】
誤差行メモリ(12)は、最終誤差蓄積値及び中間誤差蓄積値を記憶するために使用され、誤差行メモリ制御回路(14)に接続され、これによって制御される。

【0039】
Jarvisアルゴリズムによれば、画素の誤差は次の2つの行内の関連画素に拡散される。従って、本実施形態の誤差行メモリは、2行であるように構成されている。現在処理されている2つの隣接する画素が、Pi,5及びPi,6であるとすると、本発明の解決法によると、2つの隣接する画素を同時に処理する間に、Pi,5及びPi,6に対応する最終誤差蓄積値、及び次の行において2つの隣接する位置の画素に対応する(画素Pi+1,5及びPi+1,6に対応する)中間誤差蓄積値は、誤差行メモリから同時に読み取る必要がある。従って、誤差行メモリ内のデータは、4つの位置、即ち画像の1つの行の2つの隣接する位置、及び次の行の2つの隣接する位置に対応するデータが1つのユニットとしてアクセスできるように配置され、これらのユニットは、ユニット順に配置されている。

【0040】
図7(A)は、8画素の画素幅を有する誤差行メモリの略図であり、(i,j)は誤差行メモリに記憶されたデータに対応する画素の位置を示している。

【0041】
図7(B)は、処理された画像の特定の3つの隣接する行内の画素点の一部の略図であり、Pi,jは行i及び列jにある画素点のことを言う。

【0042】
図7(A)に示すように、誤差行メモリの第1のユニットは、ソース画像の行i内の第1の画素Pi,1及び第2の画素Pi,2の最終誤差蓄積値、及びソース画像の行i+1内の第1の画素Pi+1,1及び第2の画素Pi+1,2の中間誤差蓄積値に対応し、誤差行メモリの第2のユニットはソース画像の行iの第3の画素Pi,3及び第4の画素Pi,4の最終誤差蓄積値、及びソース画像の行i+1の第3の画素Pi+1,3及び第4の画素Pi+1,4の中間誤差蓄積値に対応しており、誤差行メモリの最終ユニットは、ソース画像の行i内の第7の画素Pi,7及び第8の画素Pi,8の最終誤差蓄積値、及びソース画像の行i+1内の第7の画素Pi+1,7及び第8の画素Pi+1、8の中間誤差蓄積値に対応している。

【0043】
誤差行メモリのバス幅は、誤差行メモリの1ユニット内の4つの位置でのデータを一度に読み取る/書き込むことが可能である必要がある。誤差行メモリ内の1つの画素に対応する位置でのデータ幅が8ビットであるとすると、誤差行メモリのバス幅は4×8=32ビットであるべきである。

【0044】
誤差行メモリの読取及び書込過程をこれ以下に説明する。

【0045】
Jarvisアルゴリズムによれば、行i内の1つの画素点の中間誤差蓄積値は行i-2内の5つの近隣の画素によって決まり、最終誤差蓄積値は行i-1内の5つの近隣の画素及び行i-2内の5つの近隣の画素の合計によって決まる。同様に、行i内の2つの近隣の画素点の中間誤差蓄積値は、行i-2内の6つの近隣の画素によって決まり、最終誤差蓄積値は行i-1内の6つの近隣の画素及び行i-2内の6つの近隣の画素の合計によって決まる。

【0046】
従って、図1(D)と合わせて上の説明を参照すると、Pi,jを処理した後に、点Pi+1、j-2の最終誤差蓄積値及びPi+2、j-2の中間誤差蓄積値を同時に決定でき、データパケットとして誤差行メモリの1つのユニット内に同時に記憶される。同様に、2つの隣接する画素点Pi,j及びPi,j+1を処理した後に、点Pi+1、j-2の最終誤差蓄積値及びPi+2、j-1の中間誤差蓄積値を同時に決定でき、データパケットとして誤差行メモリの1つのユニット内に同時に記憶される。ちょうどこの原理に基づいて、本発明は誤差行メモリのデータ更新を行なう。

【0047】
図8は、本発明による誤差行メモリの読取及び書込過程の例示的な略図である。図7(B)及び図8に示すような実施形態を例として、これ以下に説明する。図7(B)に示す8列の画素行列の場合を例として、行i内の画素を処理し始める直前に誤差行メモリ内に記憶されているものは、行i内の画素の最終誤差蓄積値及び行i+1内の画素の中間誤差蓄積値である。

【0048】
画素Pi,1及びPi,2が処理され始めると、画素Pi,1及びPi,2の最終誤差蓄積値Li,1及びLi,2、並びに画素Pi+1,1及びPi+1,2の中間誤差蓄積値Li+1,1’及びLi+1,2’は、誤差行メモリの第1のユニットから一度で読み取られる。Li,1及びLi,2は、それぞれ画素Pi,1及びPi,2の最終グレー値を生成するために使用され、最終スクリーンドットを生成した後には使用されない。Li+1,1’及びLi+1,2’は誤差割当/蓄積レジスタファイル内でキャッシングされ、対応する最終誤差蓄積値Li+1,1及びLi+1,2を生成するために後で使用される。

【0049】
画素Pi,3及びPi,4は、画素Pi,1及びPi,2が処理された後に処理される。この時、画素Pi,3及びPi,4の最終誤差蓄積値、並びに画素Pi+1,3及びPi+1,4の中間誤差蓄積値が誤差行メモリの第2のユニットから読み取られる。同様に、最終誤差蓄積値は、画素Pi,3及びPi,4の最終スクリーンドットを生成するのに使用され、中間誤差蓄積値は誤差割当/蓄積レジスタファイル内でキャッシングされる。

【0050】
画素Pi,3及びPi,4が処理されると、画素Pi,3及びPi,4の誤差割当値が提供され、その結果、図7(B)の破線ブロックa内の4つの画素の最終誤差蓄積値及び中間誤差蓄積値を決定でき、更新データとして誤差行メモリの第1のユニットに記憶され、また、誤差行メモリ内のこの番地内のコンテンツは、行iのこれ以降の誤差処理中に変更されない。

【0051】
その後、画素Pi,5及びPi,6が処理される。同様に画素Pi,5及びPi,6が処理された場合、破線ブロックb内の4つの画素の最終誤差蓄積値及び中間誤差蓄積値を決定でき、その後、更新データとして誤差行メモリの第2のユニットに記憶される。

【0052】
行i内の最後の2つの画素Pi,7及びPi,8が処理された場合、破線ブロックc内の4つの画素の最終誤差蓄積値及び中間誤差蓄積値だけでなく、破線ブロックd内の4つの画素の最終誤差蓄積値及び中間誤差蓄積値を決定できることが分かる。

【0053】
従って、データ更新を2回行なうために、誤差行メモリに対して2つの読取及び書込動作を行なう必要がある。誤差行メモリ内の更新データ算出方法を、例によりこれ以下に説明する。

【0054】
現在処理されている画素がPi,5及びPi,6であるとすると、画素Pi,5及びPi,6を処理した後の誤差割当値はそれぞれ、Ei,5、Ei,5、Ei,5、Ei,5、並びに、Ei,6、Ei,6、Ei,6、及びEi,6によって示される。(ここで、Ei,5及びEi,6はそれぞれ、画素Pi,5及びPi,6から拡散させる必要がある誤差Eである。) 従って、破線ブロックb内の4つの画素の最終誤差蓄積値及び中間誤差蓄積値Li+1,3、Li+1,4、Li+2,3’、及びLi+2,4’は以下のように示される。

i+1,3 = Li+1,3’+Ei,1+Ei,2+Ei,3+Ei,4+Ei,5
i+1,4 = Li+1,4’+Ei,2+Ei,3+Ei,4+Ei,5+Ei,6
i+2,3’ = Ei,1+Ei,2+Ei,3+Ei,4+Ei,5
i+2,4’ = Ei,2+Ei,3+Ei,4+Ei,5+Ei,6

式中、Li+1,3’及びLi+1,4’はそれぞれ、行(i-1)の画素からの、画素Pi+1,3及びPi+1,4に対する中間誤差値である。

【0055】
一般的に言えば、現在の行の処理した画素に対応する誤差行メモリ内の最終誤差蓄積値は、画素の最終ドットが生成された後には使用されず、中間誤差蓄積値は、誤差割当/蓄積レジスタファイル内に記憶される。従って、誤差行メモリ内の書き込まれたユニットにおいて、第1の2つの位置の内容は現在処理されている行の次の行の2つの隣接する画素に対応する最終誤差蓄積値であり、次の2つの位置の内容は現在処理されている行の2つ後の行の2つの隣接する画素に対応する中間誤差蓄積値である。従って、誤差行メモリは、初期値を0に設定した上で、2つの行を繰り返し使用できる。

【0056】
一方、現在処理されている画素(Pi,5及びPi,6を例とすると)の誤差割当値に加えて、Li+1,3、Li+1,4、Li+2,3’及びLi+2,4’に影響を与える他の関連値(即ち、画素Pi,1、Pi,2、Pi,3及びPi,4からの誤差割当値及び中間誤差蓄積値Li+1,3’及びLi+1,4’)は、誤差割当/蓄積レジスタファイル内に記憶されている。従って、Li+1,3、Li+1,4、Li+2,3’及びLi+2,4’の算出及び書込は誤差行メモリを再び読み取ることなく完了できる。
本発明の誤差行メモリのバス幅が誤差行メモリ内の4つの位置の少なくともデータ幅である場合、1つのユニット内の4つの値Li,5、Li,6、Li+1,5’及びLi+1,6’(それぞれ、図7(B)のPi,5、Pi,6、Pi+1,5及びPi+1,6に対応する)の読取は、メモリ上の1回の読取動作のみで完了し、また別のユニット内の4つの値Li+1,3、Li+1,4、Li+2,3’及びLi+2,4’(図7(B)内の破線ブロックb内の画素に対応する)の書込は、メモリ上の1回の書込動作のみで完了する。従って、本発明による装置を使用した2つの隣接する画素Pi,5及びPi,6の処理中に、Li,5、Li,6、Li+1,5’及びLi+1,6’を読み取るには、メモリ上で1回の読取動作だけが必要であり、Li+1,3、Li+1,4、Li+2,3’及びLi+2,4’を書き込むには、メモリ上で1回の書込動作だけが必要であり、それによってスクリーンドット生成速度が格段に向上する。

【0057】
図9は、読取アドレスレジスタ、書込アドレスレジスタ、読取/書込制御回路、及び書込データ生成回路を備えた、本発明による装置の誤差行制御回路(14)のブロック図である。読取アドレスレジスタ及び書込アドレスレジスタ内に記憶されたコンテンツ(即ち、アドレス)は、現在処理されている2つの画素内の第1の画素(Pi,5であるとする)の座標(アドレス)に合わせて生成され、書込データ生成回路は加算器からなり、現在の2つの隣接する画素Pi,5及びPi,6を処理することによって生成される誤差割当値、同じ行の画素Pi,5及びPi,6の前の位置にある画素によって生成される(誤差割当/蓄積レジスタファイルに記憶された)誤差割当値、(誤差割当/蓄積レジスタファイルに記憶された)関連する中間誤差蓄積値に従って、誤差行メモリ内に一回で書き込むべきデータを提供し、読取/書込制御回路は、誤差行メモリの読取/書込制御信号を生成する。

【0058】
読取アドレスレジスタ及び書込アドレスレジスタ内に記憶された読取アドレス又は書込アドレスの決定は、例により以下に説明する。例示的な実施例としては、読取アドレスを2×j-1、書込アドレスを2×(j-2)-1と設定する。ここで、jは現在処理されている画素のうちの第1の画素の列数であり、j=1,2,...nである。上記アドレスはバイトアドレスである。例として現在処理されている画素のうち第1の画素Pi,5の列数は、j=5であるから、読取アドレスは2×5-1=9であり、現在の読取アドレスから始まる1ユニット内の4つの連続位置から一度にデータLi,5、Li,6、Li+1,5’及びLi+1,6’を読み取る。一方、書込アドレスは2×(5-2)-1=5であり、書込データ生成回路が、現在の行の次の行、及び現在の行の2つ後の行の2つの隣接する位置にある画素にそれぞれ対応する書込データLi+1,3、Li+1,4、Li+2,3’、及びLi+2,4’(その算出方法は上述したとおりである)を生成し、現在の書込アドレスから始まる1つのユニット内の4つの連続位置内に上記書込データを一度に書き込む。
[誤差割当/蓄積レジスタファイル及びその制御回路]

【0059】
誤差割当/蓄積レジスタファイル(13)は、誤差割当値及び中間誤差割当値をキャッシングする、ハードウェアトリガからなり、誤差割当/蓄積レジスタファイル制御回路(15)に接続され、これによって制御される。

【0060】
図10は、同じ行内の現在処理されている画素の前の4つの隣接する画素の誤差割当値全て、及び現在処理されている行の次の行内の2つの画素のために読み取られた中間誤差蓄積値を含む、本実施形態による誤差割当/蓄積レジスタファイルの略図である。

【0061】
前の説明から、誤差行メモリを更新するために本発明による方法での最終誤差蓄積値及び中間誤差蓄積値を算出する間に、現在の行内の最大6つの近隣の画素の誤差割当値が必要であり、それによって誤差割当レジスタファイルは、現在処理されている2つの隣接する画素によって生成される誤差割当値と共に、誤差行メモリ内で、次の行内、及び現在処理されている行の次の2行内の対応する画素の最終誤差蓄積値及び中間誤差蓄積値を更新するため、即ち、誤差行メモリ内の現在処理されている画素に対応するユニットの前のユニット内の4つの位置で値を更新するために使用される、同じ行内の現在処理されている画素の前の4つの近隣の画素の誤差割当値を全て記憶する必要がある。Farvisアルゴリズムから、現在の行の次の行の最終誤差値は誤差行メモリ内のオリジナル値、及び現在の行の処理が開始する前に現在の行が0となった後の第2の行の誤差値に関連し、それによって誤差蓄積レジスタファイルは、現在の行の次の行の2つの中間誤差蓄積値を記憶する必要があるだけであることが容易に分かる。

【0062】
本実施形態では、図10に示すように、誤差割当/蓄積レジスタファイル(13)は、4つの近隣の画素の誤差割当値全て、及び現在処理されている行の次の行の2つの中間誤差蓄積値をキャッシングすることができ、Pi,5及びPi,6が2つの現在処理されている隣接する画素であるとすると、Ei,m(m=1...4,n=1...4)は、同じ行内のPi,5及びPi,6の前に位置する4つの近隣の画素Pi,1~Pi,4からの誤差割当値全てを示し、Li+1,3’及びLi+1,4’は、画素Pi,3及びPi,4の処理中に読み取られた中間誤差蓄積値を示している。

【0063】
図11は、本発明による装置内の誤差割当/蓄積レジスタファイル制御回路のマルチプレクサの作動原理の略図である。誤差割当/蓄積レジスタファイル制御回路は、n個のマルチプレクサを介して各処理期間において一回誤差割当/蓄積レジスタファイルを更新し、各行を処理する前に初期化及びリセットを行い、nは誤差割当/蓄積レジスタファイル内のレジスタの数である、即ち、誤差割当/蓄積レジスタファイル内の各レジスタは同じ構造を備えた1つのマルチプレクサを備えており、この実施形態では、図10に示したように、n=18である。マルチプレクサの入力は、現在処理されている画素の誤差割当値全て、現在の画素の処理中に読み取られた中間誤差蓄積値、及び誤差割当/蓄積レジスタファイルのオリジナル値を含んでおり、マルチプレクサの出力は、誤差割当/蓄積レジスタファイル内のレジスタの更新値である。

【0064】
誤差割当/蓄積レジスタファイルのデータ更新を、本発明による方法と合わせて、以下に説明する。

【0065】
図12は、本発明による誤差割当/蓄積レジスタファイル内のデータを更新する過程の略図であり、Ei,j(n=1...4)は行i内の画素jの誤差割当値を示している。現在処理されている画素Pi,5及びPi,6を例としてとると、2つの現在の隣接する画素の誤差割当値Ei,5及びEi,6及び(図12に示す列2内の)Ei,3及びEi,4に対応する、現在の行に隣接する行から読み取られた中間誤差蓄積値Li+1,5’及びLi+1,6’をレンダリングした後に、マルチプレクサはそれぞれ、Li+1,3’及びLi+1,4’に対応する(図12の現在の列内の)Ei,5及びEi,6を出力し、次に、マルチプレクサはそれぞれ、(図12に示す列1内の)Ei,1及びEi,2に対応する出力Li+1,5’及びLi+1,6’を出力し、さらに、マルチプレクサはそれぞれ(図12の列2内の)Ei,3及びEi,4を出力する。誤差割当/蓄積レジスタファイル内の列は、比喩的に言えば、逐次前進するように更新される。
[スクリーンドット生成方法]

【0066】
本実施形態では、2つの現在処理されている画素がPi,5及びPi,6であるとすると、マルチサイトFMスクリーンドット生成方法は以下のステップを含んでいる。

【0067】
ステップ1) 行i内の2つの隣接するソース画素、即ちPi,5及びPi,6を取得する。

【0068】
ステップ2) 誤差行メモリから一度に1ユニット内の4つの位置の誤差値、即ち、Pi,5及びPi,6に対応する最終誤差蓄積値Li,5及びLi,6、並びに、画素Pi+1,5及びPi+1,6に対応する中間誤差蓄積値Li+1,5’及びLi+1,6’を読み取る。

【0069】
ステップ3)
誤差割当/蓄積レジスタファイルのコンテンツから現在処理されている画素のうちの第1の画素Pi,5では、同じ行内の画素の全ての先行処理によって生成される画素Pi,5に割り当てる誤差によってレンダリングされる誤差割当値の合計であるSを算出し(S=Ei,3+E1,4)、
その後、画素Pi,5の最終グレー値を算出し(ここで、画素Pi,5の最終グレー値= Pi,5のソース画素値1+Li,5+S)、この最終グレー値を、画素Pi,5の最終スクリーンドット1を生成するための閾値と比較して画素Pi,5の最終スクリーンドット1を生成し、
次に、その周囲画素点に対する画素Pi,5の誤差割当値を算出し、そのうちの画素Pi,5の誤差割当値Ei,5を第2の画素点Pi,6にトランスポートする。

【0070】
一方、現在処理されている画素のうちの第2の画素Pi,6では、同じ行内の画素の全ての先行処理によって生成される画素Pi,6に割り当てる誤差によってレンダリングされる誤差割当値の合計であるSを算出し(S=Ei,4+E1,5)、
その後、画素Pi,6の最終グレー値を算出し(ここで、画素Pi,6の最終グレー値= Pi,6のソース画素値2+Li,6+S)、この最終グレー値を、画素Pi,6の最終スクリーンドット2を生成するための閾値と比較して画素Pi,6の最終スクリーンドット2を生成し、
次に、その周囲画素点に対する画素Pi,6の誤差割当値を算出する。

【0071】
ステップ4)
誤差行メモリ及び誤差割当/蓄積レジスタファイルのデータ更新を行なう、即ち、誤差割当/蓄積レジスタファイル内に記憶された画素Pi,1~Pi,6の誤差割当値及び中間誤差蓄積値Li+1,3’及びLi+1,4’に従って、最終誤差蓄積値Li+1,3及びLi+1,4及び中間誤差蓄積値Li+2,3’及びLi+2,4’を算出し、誤差行メモリのデータ更新を実現するために誤差行メモリ内に算出結果を書き込む。

【0072】
ステップ2で読み取った中間誤差蓄積値Li+1,5’及びLi+1,6’、並びにステップ3で得られた画素Pi,5及びPi,6の誤差割当値を誤差割当/蓄積レジスタファイル内に記憶させ、逐次前進するように誤差割当/蓄積レジスタファイルを更新する。

【0073】
本実施形態による特定の実施装置では、閾値比較回路I(17)は、スクリーンドット1を生成するために、グレー生成回路(16)によって生成されたグレー値を閾値と比較するのに使用される。
閾値比較回路II(20)は、スクリーンドット2を生成するために、グレー生成回路II(19)によって生成されたグレー値を閾値と比較するのに使用される。
誤差生成回路I(18)は、グレー生成回路I(16)によって生成されたグレー値から、計算又はテーブル検索を介して現在の画素1の誤差割当値を生成し、結果を誤差行メモリ制御回路(14)、誤差割当/蓄積レジスタファイル制御回路(15)、及びグレー生成回路II(19)に出力するために使用される。
誤差生成回路II(21)は、グレー生成回路II(19)によって生成されたグレー値から、計算又はテーブル検索を介して現在の画素2の誤差割当値を生成し、結果を誤差行メモリ制御回路(14)及び誤差割当/蓄積レジスタファイル制御回路(15)に出力するために使用される。
誤差行メモリ制御回路(14)及び誤差割当/蓄積レジスタファイル制御回路(15)はそれぞれ、誤差行メモリ(12)及び誤差割当/蓄積レジスタファイル(13)のデータ更新を行なうために使用される。

【0074】
Nサイトドットを同時に生成する必要がある場合、装置構成は上述の2サイトスクリーンドットの場合と類似しており、図2に示したように、違いは、実現に当って、スクリーンドット生成装置(6)が、N個のグループのスクリーンドット生成回路(10)からなるということにある。
その際、同じ行内のN個の近隣のソース画素が一度に取得され、現在のN個のソース画素値、並びに、誤差行メモリ(2)及び誤差割当/蓄積レジスタファイル(3)内に記憶されたデータによってNサイトスクリーンドットが生成される。

【0075】
一度のデータ読取及び記憶の需要に応じるためには、誤差行メモリのバス幅、及び誤差割当/蓄積レジスタファイルの容量をさらに大きくする必要があることを当業者は理解すべきである。同時に処理されるべき現在の画素の数がNであり、誤差行メモリ内の1つの位置でのデータ幅がWであり、1つの画素の誤差を拡散することができる行の数がH(現在の行を含む)であるとすると、誤差行メモリの最小バス幅は、N×W×(H-1)となる。誤差割当/蓄積レジスタファイルの容量は、1つの画素の処理に伴う誤差が拡散されるべき近隣の画素の最大数に依存し、採用した誤差拡散アルゴリズムにより決まる。

【0076】
特に、現在のN個の画素のグレー値、誤差行メモリの値、及び誤差割当/蓄積レジスタファイルの値により、Nサイトスクリーンドットを生成する方法は以下のステップを含んでいる。

【0077】
ステップ1)
N個のグループのスクリーンドット生成回路が、行i内のN個の近隣のソース画素のグレー値を同時に取得し、行i内の現在のN個の近隣の画素に応じた最終誤差蓄積値、及び行(i+1)~行(i+H-2)の、直接対応する位置でのN個の近隣の画素の中間誤差蓄積値を誤差行メモリから一度に読み取る。

【0078】
ステップ2)
現在処理されているN個の近隣のソース画素のうち第1の画素Pi,j(jは列番数のことを言う)に関して、Sをレンダリングする。ここで、Sは、誤差割当レジスタファイル内に記憶されたデータを用いて、同じ行内で全ての先行する画素を処理することによって生成される誤差を全てこの画素に割り当てることによってレンダリングされる誤差値の合計である。

【0079】
第1のグループのスクリーンドット生成回路は、現在処理されている画素のうちの第1の画素Pi,jに対応する最終誤差蓄積値Li,jに、このSを加え、次に、ステップ1で取得された第1のソース画素のグレー値を加えて、第1の画素Pi,jの最終画素グレー値を得、これを閾値と比較して第1の画素の最終スクリーンドットを生成すると共に、その周辺画素点に対する画素Pi,jの誤差割当値を算出する。

【0080】
同時に、現在処理されている画素のうちの第2の画素Pi,j+1に関して、Sをレンダリングする。ここで、Sは、誤差割当/蓄積レジスタファイルに記憶されたデータを用いて、同じ行内の画素Pi,jの前の画素全てによって生成される誤差全てをこの画素に割り当てることによってレンダリングされる誤差割当値の合計をレンダリングし、その後、上記第1の画素Pi,jを処理することによって生成される誤差を画素Pi,j+1に割り当てることによってレンダリングされる誤差割当値の合計である。

【0081】
第2のグループのスクリーンドット生成回路は、現在処理されている画素のうちの第2の画素Pi,j+1に対応する最終誤差蓄積値Li,j+1に、このSを加え、次に、ステップ1で取得された第2のソース画素のグレー値を加えて、第2の画素Pi,j+1の最終画素グレー値を得、これを閾値と比較して第2の画素の最終スクリーンドットを生成すると共に、その周辺画素点に対する画素Pi,j+1の誤差割当値を算出する。

【0082】
同様に、現在処理されている画素のうちの第M番目の画素Pi,j+M-1(2<M≦N)に関して、S’をレンダリングする。ここで、S’は、誤差割当レジスタファイルに記憶されたデータを用いて、同じ行内の画素Pi,jの前の画素全てによって生成された誤差全てをこの第M番目の画素に割り当てることによってレンダリングされる誤差割当値の合計である。
その後、S”をレンダリングする。ここで、S”は、第1~第(M-1)番目の画素によって生成された誤差全てを第M番目の画素に割り当てることによってレンダリングされる誤差割当値全ての合計である。
次に、このS’とS”を加えて、同じ行内のM番目の画素の前の画素全てによって生成される誤差全てを第M番目の画素に割り当てることによってレンダリングされる誤差割当値の合計であるSをレンダリングする。

【0083】
現在のN個の近隣の画素を処理した後に、この方法は以下のステップを含んでいる。

【0084】
ステップ1)
現在処理されている画素それぞれの最終画素グレー値及び閾値に従って、現在のN個の近隣の画素によって生成される誤差を全ての近隣の画素に割り当てることによって値Ei,Kをレンダリングする(Ei,Kは、現在処理されている画素のうちのK番目の画素によって生成される誤差割当値のグループのことを言い、1≦K≦Nであり、Jarvisアルゴリズムでは、n=1~4である)。

【0085】
ステップ2)
誤差割当/蓄積レジスタファイル内のコンテンツ、及び現在のN個の近隣の画素を処理することによって生成される誤差割当値に従って、行(i+1)内のN個の近隣の位置Pi+1,j-N~Pi+1,j-1での最終誤差蓄積値、及び行(i+2)~行(i+H-2)内の、N個の近隣の位置の画素(Pi+2,j-N~Pi+2,j-1)~N個の近隣の位置の画素(Pi+H-2,j-N~Pi+H-2,j-1)の中間誤差蓄積値をレンダリングする。これらは、一度に誤差行メモリ内の対応する位置に書き込まれる。

【0086】
ステップ3)
誤差割当レジスタファイル内の1つの列内に各N個の近隣の画素の誤差割当値全てを配置し、N個の画素の先行列の誤差割当値をN個の近隣の画素の後続列の誤差割当値となるように逐次更新し、最後にN個の近隣の画素の最終列の誤差割当値を現在のN個の画素の誤差割当値となるように更新する。

【0087】
ステップ4)
現在のN個の近隣の画素に応じて次の行の位置でN個の近隣の画素Pi+1,j~Pi+1,j+N-1のものとなるようにオリジナルのN個の近隣の画素Pi+1,j-N~Pi+1,j-1の中間誤差蓄積値を更新する。

【0088】
本発明の好ましい実施形態のみを上記に記載したものであり、本発明をこれに限定するものと解釈すべきではない。上記装置の様々な部分、及びその間の接続関係は例示的なものであり、当業者は本発明の精神から逸脱することなく様々な変更及び置換ができることを理解すべきである。加えて、上記方法は単に本発明の好ましい解決法であり、特定の状況によって方法のステップに対して当業者は適切な選択及び最適化できる。

【0089】
例えば、誤差行メモリ内のデータを更新する上記方法では、いずれの画像の行においても、最初及び最後の画素の処理中に誤差行メモリを更新する方法が紹介されている、即ち、誤差行メモリは(現在更新されたデータが生成されるときに)各行内の最初の2つの画素を処理中に更新されず、各行内の最後の2つの画素の処理中に2度更新される。しかし当業者ならば、多くの他のデータ更新方法が存在することを理解できるであろう。

【0090】
例えば、誤差行メモリの最前部の1つのユニットが残され、各行内の最初の2つの画素を処理する間にリフレッシュされ、効果的な最終誤差蓄積値及び中間誤差蓄積値が誤差行メモリの第2のユニットから記憶される。また、例えば、誤差行メモリは、各行内の最後の2つの画素を処理した後に一度リフレッシュすることができ、その後、各行の後に2つのブランクドットを処理し、誤差行メモリの最終ユニットをリフレッシュすることができる。

【0091】
加えて、本発明により一度に2サイトスクリーンドットを同時に生成する装置の実施形態が、誤差が12個の近隣の位置に拡散されるJarvisアルゴリズムに関連して記載されているが、本発明はまた、他の誤差拡散アルゴリズム、及び3つ以上のスクリーンドットを同時に生成する装置に適用することができる。従って、本発明の精神及び原理内でのあらゆる変更、等価置換、改良などは、本発明の保護の範囲内に含まれるべきものである。
【符号の説明】
【0092】
1、11 高速FMスクリーンドット装置、マルチサイトFMスクリーンドットを同時に生成する装置
2、12 誤差行メモリ
3、13 誤差割当/蓄積レジスタファイル
4、14 誤差行メモリ制御回路
5、15 誤差割当/蓄積レジスタファイル制御回路
6 スクリーンドット生成装置
7 グレー生成回路
8 閾値比較回路
9 誤差生成回路
10 スクリーンドット生成回路
16、19 グレー生成回路I、II
17、20 閾値比較回路I、II
18、21 誤差生成回路I、II
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11