(57)【要約】【課題】演算過程で処理を中断して新たな入力値を与えることができないプロセッサーを利用して誤差拡散処理を高速化すること。【解決手段】前記画像データの各ラインを、分割後の領域内の画素数が複数個となるように分割し、前記領域のそれぞれにおいて、前記画像データのＮライン（Ｎは自然数）目の画素からの誤差の拡散が未完了であるＮ＋１ライン目の画素にて誤差拡散処理が行われることを防止するための遅延時間を確保するための画素数ｍを特定し、前記画像データのＮライン目において前記領域内でｍ番目に処理される画素の誤差拡散処理が終了した後に、同じ領域内の前記画像データのＮ＋１ライン目の誤差拡散処理を開始する制御を前記領域のそれぞれで行って前記画像データの各ラインについての誤差拡散処理を行う。【選択図】図１
2012134913.tif 000002
【特許請求の範囲】
【請求項１】
画像データを取得する画像データ取得手段と、
前記画像データの各ラインを、分割後の領域内の画素数が複数個となるように分割する画像データ分割手段と、
前記領域のそれぞれにおいて、前記画像データのＮライン（Ｎは自然数）目の画素からの誤差の拡散が未完了であるＮ＋１ライン目の画素にて誤差拡散処理が行われることを防止するための遅延時間を確保するための画素数ｍを特定する遅延画素数特定手段と、
前記画像データのＮライン目において前記領域内でｍ番目に処理される画素の誤差拡散処理が終了した後に、同じ領域内の前記画像データのＮ＋１ライン目の誤差拡散処理を開始する制御を前記領域のそれぞれで行って前記画像データの各ラインについての誤差拡散処理を行う誤差拡散処理手段と、
を備える画像処理装置。
【請求項２】
前記誤差拡散処理手段は、複数のプロセッサーを備えるとともに、前記Ｎライン目の誤差拡散処理と前記Ｎ＋１ライン目の誤差拡散処理とは異なるプロセッサーで実行され、各プロセッサーは前記領域内の前記複数個の画素については中断することなく誤差拡散処理を実行する、
請求項１に記載の画像処理装置。
【請求項３】
前記画像データ分割手段は、前記領域の数が、前記画像データを分割して前記Ｎ＋１ライン目の誤差拡散処理を前記Ｎライン目よりも画素数ｍだけ遅延させて開始する制御を前記領域のそれぞれで行うことによって、前記画像データを分割しない状態において前記遅延時間を確保するための画素数ｍ'だけ前記Ｎ＋１ライン目の誤差拡散処理を前記Ｎライン目よりも遅延させて開始する場合と比較して誤差拡散処理の所要時間が短縮されるような数になるように前記ラインを分割する、
請求項１または請求項２のいずれかに記載の画像処理装置。
【請求項４】
前記遅延画素数特定手段は、前記領域内で前記Ｎライン目の誤差拡散処理が最低速で行われ、かつ、同じ領域内で前記Ｎ＋１ライン目の誤差拡散処理が最高速で行われた場合であっても、同じ領域内で前記画像データのＮライン目の画素からの誤差の拡散が未完了であるＮ＋１ライン目の画素にて誤差拡散処理が開始されないように前記ｍを設定する、
請求項１〜請求項３のいずれかに記載の画像処理装置。
【請求項５】
前記遅延画素数特定手段は、各ラインにおける前記分割後の領域内の画素数Ｗと、前記Ｎライン目の座標（ｉ，Ｎ）の画素（ｉは自然数）を着目画素とした場合の前記Ｎ＋１ライン目における誤差の拡散範囲が座標（ｉ−ｂ，Ｎ＋１）から座標（ｉ＋ａ，Ｎ＋１）まで（ａ，ｂは自然数）の範囲である場合におけるｂの最大値Ｌと、画素毎の誤差拡散処理の最短所要時間Ｔminと、画素毎の誤差拡散処理の最長所要時間Ｔmaxと、に基づいて、
（Ｗ−ｍ）×Ｔmax＝（Ｗ−Ｌ−１）×Ｔmin
の関係から前記ｍを設定する、
請求項１〜請求項４のいずれかに記載の画像処理装置。
【請求項６】
前記遅延画素数特定手段は、各ラインにおける前記分割後の領域内の画素数が少なくなるほど前記ｍを小さくする、
請求項１〜請求項５のいずれかに記載の画像処理装置。
【請求項７】
画像データを取得する画像データ取得工程と、
誤差拡散処理の進行方向に平行な方向の画素数が複数個であり、かつ、前記進行方向に平行な方向に複数個の領域となるように前記画像データを分割する画像データ分割工程と、
前記領域のそれぞれにおいて、前記画像データのＮライン（Ｎは自然数）目の画素からの誤差の拡散が未完了であるＮ＋１ライン目の画素にて誤差拡散処理が行われることを防止するための遅延時間を確保するための画素数ｍを特定する遅延画素数特定工程と、
前記画像データのＮライン目において前記領域内でｍ番目に処理される画素の誤差拡散処理が終了した後に、同じ領域内の前記画像データのＮ＋１ライン目の誤差拡散処理を開始する制御を前記領域のそれぞれで行って前記画像データの各ラインについての誤差拡散処理を行う誤差拡散処理工程と、
を含む画像処理方法。
【請求項８】
画像データを取得する画像データ取得手段と、
前記画像データの隣接する２以上のラインにて構成される処理単位を、分割後の領域内の前記ラインに平行な横方向の画素数が複数個となるように縦方向の分割線によって分割する画像データ分割手段と、
前記処理単位が並ぶ順に処理対象に設定して各処理単位内の前記領域のそれぞれにおいて画素が並ぶ順に誤差拡散処理を行う場合に、前記領域のそれぞれにおいて、Ｎ番目（Ｎは自然数）に処理対象となる前記処理単位内に存在する画素からの誤差の拡散が未完了である画素であって、Ｎ＋１番目に処理対象となる前記処理単位内に存在する画素にて誤差拡散処理が行われることを防止するための遅延時間を確保するための画素数ｍを特定する遅延画素数特定手段と、
Ｎ番目に処理対象となる前記処理単位において前記領域内でｍ番目に処理される画素の誤差拡散処理が終了した後に、Ｎ＋１番目に処理対象となる前記処理単位において同じ領域内の誤差拡散処理を開始する誤差拡散処理手段と、
を備える画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、誤差拡散処理を行う画像処理装置に関する。
【背景技術】
【０００２】
誤差拡散処理は、多階調の画像データをより少ない階調で表現するために利用され、例えば、画素の階調値を２値化する場合、２値化を行った場合に生じる階調値の誤差を着目画素の周辺の画素に拡散させる処理を画像データの各画素について実行するなどして実現される。当該誤差拡散処理が画像データのライン毎に行われる場合、あるラインの一方端の画素から他方端の画素までのそれぞれを逐次着目画素として誤差を拡散させる処理を行うこととし、当該処理が１ライン目から最終ライン目まで実行されることになる。
【０００３】
この場合、Ｎライン目の着目画素の誤差は、Ｎ＋１ライン目に存在する画素にも拡散される。従って、Ｎ＋１ライン目のある画素に対するＮライン目の誤差の拡散が完了し、それ以後、当該画素に誤差が拡散される可能性がなくなるまで当該画素を着目画素としたＮ＋１ライン目の誤差拡散処理を行うことはできないという制約がある。従来、この制約下において誤差拡散処理を高速に実行するための技術が開発されており、例えば、特許文献１に開示された技術においては、隣接するラインの誤差拡散処理を第１のＣＰＵおよび第２のＣＰＵで実行する並列化を行い、Ｎ＋１ライン目の誤差拡散処理がＮライン目の誤差拡散処理を追い越さないように着目画素の位置関係を画素毎に逐次チェックしながら誤差拡散処理を並列進行させる技術が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−１２５１２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１の技術においては、Ｎ＋１ライン目の誤差拡散処理がＮライン目の誤差拡散処理を追い越さないように着目画素の位置関係を画素毎に逐次チェックしている。従って、各ラインに存在する全画素について着目画素が変わるたびに当該チェックを行う必要がある。このため、当該チェックのために要する時間は無視できないほど大きく、画素数が増加するほど従来の技術による高速化の効果が減殺されてしまう。また、非常に多くの並列処理を行うプロセッサーにおいては、処理を開始する際に与えられた入力値に基づいて予め決められた処理を行って出力値を得るように演算を行う構成が採用されており、当該演算過程で処理を中断して新たな入力値を与えることができない構成となっている。従って、このようなプロセッサーを複数個用いて、着目画素が変わるたびにライン間の進捗をチェックしながらライン毎の誤差拡散処理を行う構成について完全に並列化しようとしても、一方のプロセッサーの処理の進捗を示す入力値に基づいて他方のプロセッサーの処理の進捗度合いを制御することは不可能であり、現実的には完全に並列化することは不可能である。
本発明は上記課題にかんがみてなされたもので、演算過程で処理を中断して新たな入力値を与えることができないプロセッサーを利用して誤差拡散処理を高速化することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するため、本発明においては、画像データの各ラインを、分割後の領域内の画素数が複数個となるように分割する。そして、分割後の領域のそれぞれにおいて、画像データのＮライン（Ｎは自然数）目の画素からの誤差の拡散が未完了であるＮ＋１ライン目の画素にて誤差拡散処理が行われることを防止するための遅延時間を確保するための画素数ｍを特定する。さらに、画像データのＮライン目において分割後の領域内でｍ番目に処理される画素の誤差拡散処理が終了した後に、同じ領域内の画像データのＮ＋１ライン目の誤差拡散処理を開始する。すなわち、分割後の領域のそれぞれにおいて、Ｎライン目の画素からの誤差の拡散が終了していない画素についてはＮ＋１ライン目の誤差拡散が開始されないように、Ｎ＋１ライン目においてはＮライン目に対して一定の画素数ｍだけ遅延したタイミングで誤差拡散処理を開始する構成とした。
【０００７】
この構成によれば、分割後の領域のそれぞれにおいて、誤差拡散処理の開始タイミングさえチェックしておけば、誤差拡散処理の開始後に処理を中断することなく分割後の領域内の誤差拡散処理を進行させることができる。従って、１ラインの全画素について着目画素が変わるたびにＮ＋１ライン目における誤差拡散処理がＮライン目における誤差拡散処理を追い越すか否かをチェックする構成と比較して誤差拡散処理を高速に実行することができる。また、分割後の領域内でライン毎の誤差拡散処理を開始した後、当該領域内の画素の誤差拡散処理の過程で他のラインの進捗をチェックすることなく各ラインにおける誤差拡散処理を完了することができる。従って、演算過程で処理を中断して新たな入力値を与えることができないプロセッサーを利用して分割後の領域内の画素についての誤差拡散処理を高速化することが可能である。
【０００８】
ここで、画像データ分割手段は、画像データの各ラインを、分割後の領域内の画素数が複数個となるように分割することができればよい。すなわち、画像データにおいて誤差拡散処理の進行方向と平行な方向に延び、当該進行方向と垂直な方向に並ぶ各ラインを、当該進行方向と垂直な方向に延びる分割線で分割することによって複数の領域を形成すればよい。ここで、ラインの分割後の領域数は２以上であれば良いが、ラインを構成する画素の画素数と分割後の領域数とが同一である場合にはライン上の全画素について進捗をチェックする構成となってしまう。そこで、分割後の領域内の画素数が複数個となるように分割後の領域数を設定する。なお、分割後の領域数は、誤差拡散処理の高速化に寄与する数であれば良く、画像データに応じて決定されても良いし、予め決められた固定値であっても良い。また、分割後の領域数に応じて１ライン分の誤差拡散処理を完了するまでの所要時間が変化し、極小値が得られる場合には、所要時間が当該極小値となる分割後の領域数に設定することが好ましい。
【０００９】
また、遅延画素数特定手段は、全ラインに共通の画素数ｍだけ分割後の各領域における誤差拡散処理の開始タイミングがずれることによって、分割後の領域のそれぞれにおいて、Ｎライン目の画素からの誤差の拡散が未完了であるＮ＋１ライン目の画素にて誤差拡散処理が行われることを防止するための遅延時間を確保することができるようにｍを特定することができればよい。従って、画素数ｍはある画像データにおいて各ラインに共通の値であれば良く、画像データに応じて決定されても良いし、予め決められた固定値であっても良い。なお、分割後の領域のラインに平行な方向の画素数が各領域で共通であれば、画素数ｍを各領域に共通の値とすることができるが、分割後の領域のラインに平行な方向の画素数が各領域で異なる場合には、画素数ｍを各領域で異なる値とする。後者の場合、領域のラインに平行な方向の画素数に対応した複数のｍの値が特定されるが、各ラインにおいてｍの値は共通である。また、遅延時間はＮライン目の開始タイミングとＮ＋１ライン目の開始タイミングとの差に相当する時間であれば良く、Ｎライン目の誤差拡散処理をｍ画素分先行させることによって当該遅延時間を確保できればよい。
【００１０】
誤差拡散処理手段は、分割後の各領域において、Ｎ＋１ライン目の誤差拡散処理の開始タイミングをＮライン目よりもｍ画素分遅延させることができればよい。すなわち、各ラインについて共通の遅延を設けて誤差拡散処理を開始し、誤差拡散処理を開始した後には他のラインの進捗に依存して処理を中断することなく誤差拡散処理を進行させることができればよい。誤差拡散処理としては種々の態様の処理を採用可能であり、誤差が拡散される着目画素周辺の画素の数や配置は種々の構成を採用可能である。また、画像データに応じて当該着目画素周辺の画素の数や配置が変動しても良い。
【００１１】
さらに、並列化を利用した高速化を行うための好ましい構成例として、誤差拡散処理手段が複数のプロセッサーを備える構成において、Ｎライン目の誤差拡散処理とＮ＋１ライン目の誤差拡散処理とは異なるプロセッサーで実行される構成とし、さらに、各プロセッサーが分割後の領域における同一ライン上の複数個の画素については中断することなく誤差拡散処理を実行するように構成してもよい。この構成によれば、各領域内で隣接するラインの誤差拡散処理が異なるプロセッサーによって実行され、各領域内で各ラインの誤差拡散処理は隣接する他のラインにおける誤差拡散処理の進捗に依存することなく進行することになる。そして、分割後の領域の境界においては、Ｎライン目の誤差拡散処理がＮ＋１ライン目の誤差拡散処理よりもｍ画素分先行しているか否かをチェックする必要があるものの、各領域の処理を開始した後においては、他のラインの進捗に依存することなく誤差拡散処理を進行させることができる。従って、極めて高速に各領域内の誤差拡散処理を実行することができる。
【００１２】
なお、この構成においてはＮライン目の誤差拡散処理がＮ＋１ライン目の誤差拡散処理よりもｍ画素分先行しているか否かをチェックする必要があるが、当該チェックは（分割後の領域数−１）回で済むため、当該チェックを行う構成であっても１ライン全体の誤差拡散処理は高速に実行される。また、ここではプロセッサーが複数であれば良く、プロセッサーが３個以上であれば、Ｎ，Ｎ＋１，Ｎ＋２ライン目のそれぞれについての誤差拡散処理が異なるプロセッサーによって実行されるように構成してもよい。
【００１３】
さらに、分割後の領域数は、各種の指標に基づいて調整可能である。例えば、ラインを分割しない場合よりも高速で誤差拡散処理を実行できるように調整しても良い。具体的には、領域の数が、画像データを分割してＮ＋１ライン目の誤差拡散処理をＮライン目よりも画素数ｍだけ遅延させて開始する制御を領域のそれぞれで行うことによって、画像データを分割しない状態において遅延時間を確保するための画素数ｍ'だけＮ＋１ライン目の誤差拡散処理をＮライン目よりも遅延させて開始する場合と比較して誤差拡散処理の所要時間が短縮されるような数になるようにラインを分割する構成を採用可能である。
【００１４】
すなわち、Ｎライン目の画素からの誤差の拡散が未完了であるＮ＋１ライン目の画素にて誤差拡散処理が行われることを防止するための遅延時間を確保するための画素数は、ラインを分割した場合と分割しない場合とのそれぞれについて画素数ｍ、画素数ｍ'と定義することができる。これらの画素数は、Ｎライン目、Ｎ＋１ライン目の双方にてどのように誤差拡散処理が進捗してもＮ＋１ライン目の誤差拡散処理がＮライン目に追いつかないように特定される。従って、誤差拡散処理の対象となる画素数が多くなるほど、追いつかないようにするための遅延時間は長くなり、ラインを分割した場合の画素数ｍはラインを分割しない場合の画素数ｍ'よりも少なくなる。
【００１５】
そして、ラインを分割する構成においては、分割後の各領域の誤差拡散処理を開始するか否かをＮライン目の誤差拡散処理がＮ＋１ライン目よりも画素数ｍだけ先行しているか否かを判定することによって判定するため、Ｎ＋１ライン目の誤差拡散処理の開始タイミングの判定を行った時点で、Ｎライン目の誤差拡散処理が少しでも先行していれば、Ｎライン目でｍ画素分の誤差拡散処理が行われる時間を待つことなくＮ＋１ライン目の誤差拡散処理を開始することができる。例えば、分割後の領域の境界においてＮ＋１ライン目の誤差拡散処理の開始タイミングの判定を行った時点でＮライン目が３画素分先行していれば、Ｎライン目であとｍ−３画素分の誤差拡散処理が行われた後にＮ＋１ライン目の誤差拡散処理を開始することができる。従って、この場合には、ラインを分割しない場合よりもＮ＋１ライン目の誤差拡散処理を早期に開始することが可能であり、誤差拡散処理を高速化することができる。
【００１６】
一方、分割後の各領域の境界の全てにおいて、Ｎ＋１ライン目の誤差拡散処理の開始タイミングの判定を行った時点で、Ｎライン目の誤差拡散処理が先行していない場合、境界の全てにおいて画素数ｍ分の誤差拡散処理が行われることを待つ必要がある。従って、この場合、Ｎ＋１ライン目の誤差拡散処理の開始タイミングの判定に要する時間だけ、ラインを分割しない場合よりも余分に時間がかかり、ラインを分割しない場合の方が高速になる。そこで、ラインを分割した方が誤差拡散処理の所要時間が短縮されるように分割後の領域数を設定することにより、より効果的に高速化を行うことが可能になる。なお、ラインを分割した方が誤差拡散処理の所要時間が短縮されるように分割後の領域数を設定するためには、画像データの画素数に応じて分割しない場合と分割後の領域数が２以上の場合とにおける誤差拡散処理の所要時間の統計を比較するなどの構成を採用可能である。
【００１７】
さらに、画素数ｍを特定するため、各ラインにおける誤差拡散処理の速度を利用する構成としても良い。例えば、分割後の領域内のＮライン目の誤差拡散処理が最低速で行われ、かつ、同じ領域内でＮ＋１ライン目の誤差拡散処理が最高速で行われた場合であっても、同じ領域内でＮライン目の画素からの誤差の拡散が未完了であるＮ＋１ライン目の画素にて誤差拡散処理が開始されないようにｍを特定する構成としても良い。すなわち、Ｎライン目の誤差拡散処理が最低速で行われ、Ｎ＋１ライン目の誤差拡散処理が最高速で行われた場合に、Ｎ＋１ライン目の誤差拡散処理の進捗とＮライン目の誤差拡散処理の進捗との差が最も早期に減少していくため、この場合であっても分割後の領域内で誤差拡散処理が追いつかないように画素数ｍを特定すれば、分割後の領域内でＮ＋１ライン目の誤差拡散処理がＮライン目の誤差拡散処理に対して追いつくことを確実に防止することが可能である。
【００１８】
さらに、分割後の領域内でＮ＋１ライン目の誤差拡散処理がＮライン目の誤差拡散処理に追いつかないようにするための条件は、「分割後の領域内のＮライン目の誤差拡散処理が終了していない画素を着目画素としたときの誤差の拡散範囲に存在するＮ＋１ライン目の画素において誤差拡散処理が開始されないようにする」という条件である。そこで、誤差の拡散範囲を参照して画素数ｍを特定する構成とすることが好ましい。例えば、各ラインにおける分割後の領域内の画素数Ｗと、Ｎライン目の座標（ｉ，Ｎ）の画素（ｉは自然数）を着目画素とした場合のＮ＋１ライン目における誤差の拡散範囲が座標（ｉ−ｂ，Ｎ＋１）から座標（ｉ＋ａ，Ｎ＋１）まで（ａ，ｂは自然数）の範囲である場合におけるｂの最大値Ｌと、画素毎の誤差拡散処理の最短所要時間Ｔminと、画素毎の誤差拡散処理の最長所要時間Ｔmaxと、に基づいて、（Ｗ−ｍ）×Ｔmax＝（Ｗ−Ｌ−１）×Ｔminの関係からｍを特定する構成としても良い。この構成によれば、分割後の領域内で、Ｎライン目の誤差拡散処理が終了していない画素を着目画素としたときの誤差の拡散範囲に存在するＮ＋１ライン目の画素において誤差拡散処理が開始されないように画素数ｍを特定することができる。なお、誤差の拡散範囲が変動する場合にはｂが変動し、その変動範囲内でのｂの最大値がＬとなり、誤差の拡散範囲が変動しない場合にはｂと最大値Ｌとが等しくなる。
【００１９】
さらに、画素数ｍは、各ラインにおける分割後の領域内の画素数が少なくなるほど小さくなるように構成されていることが好ましい。すなわち、各ラインにおける前記分割後の領域内の画素数が少なくなるほど、当該領域において、Ｎライン目の画素からの誤差の拡散が未完了であるＮ＋１ライン目の画素にて誤差拡散処理が行われることを防止するための遅延時間も短くなる。そこで、各ラインにおける前記分割後の領域内の画素数が少なくなるほど当該遅延時間を確保するための画素数ｍを小さくすればよい。なお、各ラインにおける前記分割後の領域内の画素数に対応する画素数ｍの変化は線形的であっても良いし、非線形的であっても良いし、段階的であっても良く、種々の構成を採用可能である。
【００２０】
さらに、誤差拡散処理の順序としては種々の順序を採用可能であり、ライン毎にラインが延びる方向に処理を進行させる態様と異なる態様で処理を進行させる構成としても良い。例えば、２以上のラインにて構成されるブロックを処理単位とし、処理単位内で画素が並ぶ順に誤差拡散処理を行うこととし、処理単位が並ぶ順に各処理単位を逐次処理対象に設定して画像データの全体についての誤差拡散処理を行う構成を想定可能である。すなわち、当該処理単位を分割することによって誤差拡散処理を高速化する。この場合、分割後の領域内において画像データのラインに平行な横方向の画素数が複数個となるように縦方向の分割線によって処理単位が分割される。
【００２１】
さらに、分割後の領域のそれぞれにおいて、Ｎ番目（Ｎは自然数）に処理対象となる処理単位内に存在する画素からの誤差の拡散が未完了である画素であって、Ｎ＋１番目に処理対象となる処理単位内に存在する画素にて誤差拡散処理が行われることを防止するための遅延時間を確保するための画素数ｍを特定する。そして、Ｎ番目に処理対象となる処理単位において分割後の領域内でｍ番目に処理される画素の誤差拡散処理が終了した後に、Ｎ＋１番目に処理対象となる処理単位において同じ領域内の誤差拡散処理を開始する。
【００２２】
この構成によれば、分割後の領域のそれぞれにおいて、誤差拡散処理の開始タイミングさえチェックしておけば、誤差拡散処理の開始後に処理を中断することなく分割後の領域内の誤差拡散処理を進行させることができる。従って、各処理単位に存在する全画素について着目画素が変わるたびにＮ＋１番目に処理対象となる処理単位における誤差拡散処理がＮ番目に処理対象となる処理単位における誤差拡散処理を追い越すか否かをチェックすることなく、各処理単位における誤差拡散処理を完了することができる。このため、着目画素が変わるたびにＮ＋１番目に処理対象となる処理単位における誤差拡散処理がＮ番目に処理対象となる処理単位における誤差拡散処理を追い越すか否かをチェックする構成と比較して誤差拡散処理を高速に実行することができる。また、各処理単位の分割後の領域内で誤差拡散処理を開始した後、他の処理単位の進捗をチェックすることなく各処理単位の分割後の領域における誤差拡散処理を完了することができる。従って、演算過程で処理を中断して新たな入力値を与えることができないプロセッサーを利用して分割後の領域内の画素についての誤差拡散処理を高速化することが可能である。なお、ここでは、異なる処理単位内の画素は異なるプロセッサーで誤差拡散処理がなされるように構成することが好ましい。
【００２３】
さらに、本発明のように、分割後の領域のそれぞれにおいて、各ラインに共通の画素数ｍだけライン間の誤差拡散処理の開始タイミングをずらしておく手法は、プログラムや方法としても適用可能である。また、以上のような装置、プログラム、方法は、単独の装置として実現される場合もあれば、複合的な機能を有する装置において共有の部品を利用して実現される場合もあり、各種の態様を含むものである。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施形態にかかる画像処理装置のブロック図である。
【図２】（２Ａ），（２Ｂ），（２Ｃ），（２Ｄ）は画像データの例を示す図である。
【図３】分割後の領域数と誤差拡散処理の所要時間を示す図である。
【図４】誤差拡散処理のフローチャートである。
【図５】誤差拡散処理のフローチャートである。
【発明を実施するための形態】
【００２５】
ここでは、下記の順序に従って本発明の実施の形態について説明する。
（１−１）画像処理装置の構成：
（１−２）誤差拡散処理：
（２）他の実施形態：
【００２６】
（１−１）画像処理装置の構成：
図１は、コンピューター１０を本発明にかかる画像処理装置として機能させる実施形態を示すブロック図である。コンピューター１０は、ＣＰＵ２０，ＲＡＭ３０，ＲＯＭ４０，ＨＤＤ５０，出力Ｉ／Ｆ６０を備えている。本実施形態において、ＣＰＵ２０は、複数のプロセッサー２０ａ，２０ｂ，，，２０ｎを備えており、ＣＰＵ２０は、コンピューター１０にて実行される処理の主たる制御を行いながら、画像処理等の所定単位の演算をプロセッサー２０ａ，２０ｂ，，，２０ｎに並列的に実行させることができる。なお、本実施形態におけるプロセッサー２０ａ，２０ｂ，，，２０ｎは、処理を開始する際に与えられた入力値に基づいて予め決められたプログラムに従って中断することなく演算処理を行って出力値を得るように構成されており、当該演算処理の過程で演算処理の過程で算出された値以外の新たな入力値を与えることができない構成となっている。
【００２７】
ＣＰＵ２０は、プロセッサー２０ａ，２０ｂ，，，２０ｎを適宜利用しながら、ＲＯＭ４０やＨＤＤ５０に記録されたプログラムを実行することができる。本実施形態においては、このプログラムの一つとして複数のプログラムモジュールから構成された印刷制御プログラムを実行可能であり、当該印刷制御プログラムは誤差拡散処理を実行する誤差拡散処理プログラム２１を備えている。
【００２８】
さらに、コンピューター１０は出力Ｉ／Ｆ６０を介してプリンター７０と接続されており、利用者はＣＰＵ２０に印刷制御プログラムを実行させることによって利用者所望の印刷対象をプリンター７０に印刷させることができる。本実施形態においては、ＨＤＤ５０に画像データ５０ａが記録されており、当該画像データ５０ａを印刷対象としてプリンター７０に画像を印刷させることができる。
【００２９】
印刷制御プログラムは、画像データに対して所定の画像処理を行って印刷データを生成し、当該印刷データをプリンター７０に対して出力する機能をＣＰＵ２０に実行させるプログラムである。本実施形態において、ＣＰＵ２０は、図示しないアプリケーションプログラムにより、ＨＤＤ５０に記録された印刷対象の画像データ５０ａをＲＡＭ３０に画像データ３０ａとして記録し、当該画像データ３０ａを処理対象として利用者が指示した画像処理等を実行する。また、ＣＰＵ２０は、印刷制御プログラムにより、利用者からの印刷指示を受け付け、画像データ３０ａを対象とした印刷処理を実行する。すなわち、ＣＰＵ２０は、画像データ３０ａをＲＡＭ３０から取得して各種の画像処理を行った後に印刷データをプリンター７０に対して転送して印刷を行う。
【００３０】
具体的には、ＣＰＵ２０は、必要に応じてＣＰＵ２０のキャッシュを利用しつつ、画像データ３０ａに基づいて、利用者に指示された解像度で印刷を行うために画素数を調整する補間処理や印刷結果の画質を向上するための画像処理（シャープネス強調処理やコントラスト調整処理等）等の画像調整処理を実行する。さらに、ＣＰＵ２０は、印刷制御プログラムにより、当該画像調整処理が行われた画像データに対して、表色系をＲＧＢ表色系やＹＣＣ表色系からインクの色を色成分としたインク表色系（例えば、ＣＭＹＫ表色系）に変換する色変換処理を実行する。
【００３１】
さらにＣＰＵ２０は、印刷プログラムに含まれる誤差拡散処理プログラム２１により、色変換処理後の画像データの階調数をプリンター７０の階調表現力に応じた階調数に変換する誤差拡散処理を実行する。本実施形態においては、２５６階調の画像データを２階調の画像データに変換する。なお、変換後の画像データにおける階調数はプリンター７０の階調表現力に依存しており、本実施形態においてプリンター７０は画素毎にインクを吐出しない状態とインクを吐出した状態とを形成可能であるため、誤差拡散処理後の階調数が２階調となっている。
【００３２】
さらに、ＣＰＵ２０は、印刷制御プログラムにより、誤差拡散処理後の画像データに基づいて、画素毎のインクの吐出量を特定可能な印刷データを生成し、当該印刷データをプリンター７０に対して出力する。プリンター７０においては、当該印刷データを取得すると、当該印刷データが示す吐出量でインクを吐出して各画素にインクを記録するようにキャリッジ，紙送りローラ、各ノズルのピエゾ素子を駆動して印刷媒体上に画像を印刷する。
【００３３】
（１−２）誤差拡散処理：
本実施形態においては、以上の印刷制御処理において、高速に誤差拡散処理を実行できるように誤差拡散処理プログラム２１が構成されており、以下、当該誤差拡散処理プログラム２１による処理を詳細に説明する。
【００３４】
図２Ａは、誤差拡散対象となる画像データを説明するための模式図である。本実施形態において、誤差拡散対象となる画像データは、インク表色系で表現された画像データであり、色毎に各画素の階調数が２５６階調で表現された矩形の画像データである。図２Ａにおいては、横方向をｉ軸方向、縦方向をｊ軸方向とした２次元区間の座標で画素の位置が定義された矩形の画像データを実線の矩形で示している。本実施形態においては、このような矩形の画像データにおいて、ｊ軸方向の座標値が同一の画素を同一ラインとみなし、ｊ軸方向に平行な分割線で誤差拡散対象となる画像データを複数の領域に分割する。図２Ａに示す例においては、破線の分割線で誤差拡散対象となる画像データを分割し、３個の領域としている。
【００３５】
図２Ｂは、分割された領域内の画素を模式的に示す図であり、分割後の領域においてある色に対応する画像データの各画素を正方形で示している。具体的には、図２Ｂにおいては、図２Ａのように分割された３個の領域のうち、最も左側に位置する領域を模式的に示している。同図２Ｂにおいて、誤差拡散対象となる画像データは、ｉ軸方向にＷ個の画素、ｊ軸方向にＨ個の画素が並んだ直交格子を形成しており、座標（ｉ，ｊ）によって指定される各画素について階調値が対応付けられたデータとなっている。
【００３６】
誤差拡散処理は、着目画素について比較対象となる階調値（画像データが示す階調値と拡散された誤差との和）と閾値とを比較し、階調値が閾値よりも小さい場合には誤差拡散処理後の階調値を０，階調値が閾値よりも大きい場合には誤差拡散処理後の階調値を１とする処理である。さらに、当該誤差拡散処理後の階調値と比較対象となる階調値との差分（誤差）を着目画素の周辺画素に拡散させることにより、階調数を減じることに伴って生じる誤差が蓄積することを抑制する。
【００３７】
ここで、誤差を拡散させる範囲は適宜調整可能であり、例えば、図２Ｂにおいて黒色で示す座標（６，１）の画素が着目画素であり、その周辺においてハッチングで示した画素が周辺画素であるような例を想定可能である。本実施形態においては、誤差拡散処理の対象となる画像データの画素毎の階調値によって誤差の拡散範囲を変化させる方式を採用している。すなわち、画像データに応じて誤差が拡散される範囲が可変である。
【００３８】
さらに、本実施形態においては、１ラインを処理単位とし、各ライン上で横方向に並ぶ各画素を画素が並んでいる順に逐次着目画素に設定して誤差拡散処理を進行させる。すなわち、ｊ座標値をライン番号とみなした場合に同じライン番号で指定される各画素においてｉ座標値が小さい値の画素から順に着目画素に設定し、一つの画素における誤差拡散処理が終了するたびにｉ座標値を"１"大きくして新たな着目画素に設定して誤差拡散処理を行うという手順をｉ座標値がＷになるまで繰り返す。
【００３９】
本実施形態においては、以上のようなライン毎の誤差拡散処理をライン毎に異なるプロセッサーで実行させる並列化を行い、かつ、各プロセッサーが分割後の領域内の複数個の画素については中断することなく誤差拡散処理を実行するように構成することで誤差拡散処理を高速に実行できるように構成している。すなわち、１ライン内に含まれる画素の誤差拡散処理を１つのプロセッサーによって実行し、かつ、Ｎライン目（Ｎは自然数）の誤差拡散処理とＮ＋１ライン目の誤差拡散処理とは異なるプロセッサーで実行される構成とする。さらに、分割後の領域内の画素について誤差拡散処理を開始する前においては、Ｎ＋１ライン目の誤差拡散処理がＮライン目の誤差拡散処理に追い越し（誤差の拡散が未完了の画素に対して誤差拡散処理を実行すること）が発生しないようにチェックするが、各領域内の画素について誤差拡散処理を開始した後にはライン間の進捗をチェックすることなく当該領域内の画素について誤差拡散処理が行われるように構成されている。
【００４０】
すなわち、本実施形態のような誤差拡散処理は、Ｎライン目の画素を着目画素とした場合に算出された誤差を同一ライン上の画素のみならずＮ＋１ライン目の画素にも拡散させるため、Ｎライン目での誤差拡散処理はＮ＋１ライン目での誤差拡散処理よりも所定の画素数だけ先行して実行されなくてはならない。例えば、図２Ｂに示す分割後の領域において、１番目のライン上で黒色で示す座標（６，１）の画素が着目画素であり、その周辺においてハッチングで示した画素が周辺画素である場合、２番目のライン上で座標（３，２）〜座標（８，２）までの画素に誤差が拡散される。従って、座標（６，１）の画素が着目画素となっている誤差拡散処理が終了する以前において座標（２，２）よりもｉ座標値が大きい座標の画素に対する誤差の拡散は未完了であり、比較対象となる階調値は確定していない。従って、座標（６，１）の画素が着目画素となっている誤差拡散処理が終了する以前において、２番目のライン上で座標（２，２）よりもｉ座標値が大きい座標の画素に誤差拡散処理を実行することはできない。
【００４１】
そこで、本実施形態においては、分割後の各領域内で誤差拡散処理の追い越しが発生しないタイミングで各ラインの誤差拡散処理が開始するように構成した。すなわち、分割後の各領域内で画像データのＮライン目の画素からの誤差の拡散が未完了であるＮ＋１ライン目の画素にて誤差拡散処理が行われることを防止するための遅延時間を確保するための画素数ｍを特定する。そして、画像データのＮライン目において分割後の領域内でｍ番目に処理される画素の誤差拡散処理が終了した後に、同じ領域内の画像データのＮ＋１ライン目の誤差拡散処理を開始する制御を分割後の領域のそれぞれにて実行する構成とした。
【００４２】
なお、本実施形態において画素数ｍは誤差拡散処理を開始する前に予め決定される。すなわち、本実施形態におけるプロセッサー２０ａ，２０ｂ，，，２０ｎは、処理を開始する際に与えられた入力値に基づいて予め決められたプログラムに従って演算処理を行って出力値を得るように構成されており、当該演算処理の過程で演算処理の過程で算出された値以外の新たな入力値を与えることができない構成である。従って、ライン毎に異なるプロセッサーで分割後の領域毎に誤差拡散処理を実行する場合、分割領域内の画素に関する演算処理の過程であるラインの誤差拡散処理の進捗状況が他のラインの誤差拡散処理の進捗状況に依存するように誤差拡散処理の進捗状況を調整することはできない。
【００４３】
そこで、本実施形態においては、分割後の領域のそれぞれにおいて、予め決められた画素数ｍだけＮライン目がＮ＋１ライン目に対して先行した状態でＮ＋１ライン目の誤差拡散処理を開始するように構成することで、Ｎ＋１ライン目においてＮライン目の進捗状況と無関係に誤差拡散処理を進めた場合であっても、分割後の領域のそれぞれにおいてＮ＋１ライン目の誤差拡散処理がＮライン目の誤差拡散処理に追いつくことがないように画素数ｍを特定する構成とした。この結果、着目画素が変わるたびにＮ＋１ライン目における誤差拡散処理がＮライン目における誤差拡散処理を追い越すか否かをチェックする構成と比較して誤差拡散処理を高速に実行することができる。
【００４４】
なお、本実施形態において、画素数ｍは、分割後の領域内でＮライン目の誤差拡散処理が最低速で行われ、かつ、同じ領域内でＮ＋１ライン目の誤差拡散処理が最高速で行われた場合であっても、同じ領域内でＮライン目の画素からの誤差の拡散が未完了であるＮ＋１ライン目の画素にて誤差拡散処理が開始されないように特定される。ここで、画素毎の誤差拡散処理の速度は誤差の拡散範囲等に依存するため、画素毎に最低速で誤差拡散処理が行われる場合と画素毎に最高速で誤差拡散処理が行われる場合とが想定可能である。そして、分割後の領域内のＮライン目に存在する複数個の画素において誤差拡散処理が最低速で行われ、同じ領域内のＮ＋１ライン目に存在する複数個の画素において誤差拡散処理が最高速で行われた場合に、分割された領域内でＮ＋１ライン目の誤差拡散処理の進捗とＮライン目の誤差拡散処理の進捗との差が最も早期に減少していく。そこで、この場合であっても誤差拡散処理が追いつかないように画素数ｍを特定すれば、分割後の領域内でＮ＋１ライン目の誤差拡散処理がＮライン目の誤差拡散処理に対して追いつくことを確実に防止することが可能である。
【００４５】
このような想定においては、分割後の領域内でラインに平行な方向の画素数が多くなるほどＮ＋１ライン目の誤差拡散処理がＮライン目の誤差拡散処理に追いつく可能性が高くなるため、分割後の領域内でラインに平行な方向の画素数が多くなるほどｍが大きくなり、誤差拡散処理を開始するまでの遅延時間が長期化する可能性が高くなる。従って、画像データを分割しない場合と比較すると、分割した方が誤差拡散処理を高速化でき、分割後の領域数を２から徐々に増加させるとしばらくは誤差拡散処理を高速化する効果が徐々に高くなっていく。
【００４６】
一方、画素数ｍを小さくするために分割後の領域数を過度に増加させると、分割後の領域においてＮライン目の誤差拡散処理がＮ＋１ライン目の誤差拡散処理に対して先行しているか否かを判定する頻度が過度に増加することに起因して誤差拡散処理を高速化する効果が徐々に低下する。従って、画像データを分割してＮ＋１ライン目の誤差拡散処理をＮライン目よりも画素数ｍだけ遅延させて開始することによって、画像データを分割しない状態において遅延時間を確保するための画素数ｍ'だけＮ＋１ライン目の誤差拡散処理をＮライン目よりも遅延させて開始する場合と比較して誤差拡散処理の所要時間が短縮されるような数になるようにラインを分割することが好ましい。
【００４７】
図３Ａは、分割後の領域数と誤差拡散処理の所要時間の関係を例示するグラフであり、領域数１は画像データを分割しない場合、領域数Ｐは画像データの１ライン分の全画素数と同数に分割した場合（すなわち画素毎に分割した場合）の領域数を示している。図３Ａに示す例においては、領域数１から領域数が増加するにつれて所要時間が低下し、領域数Ｄmで所要時間が極小となり、さらに領域数が増加するにつれて所要時間が増加していく。なお領域数Ｄ1においては、誤差拡散処理の所要時間が画像データを分割しない場合と同等である。そこで、このような例においては、領域数を２以上とし、Ｄ1より少なくすれば、画像データを分割しない場合よりも誤差拡散処理の所要時間を短縮することが可能である。さらに、領域数をＤmとすれば、誤差拡散処理の所要時間を極小化することが可能である。
【００４８】
なお、図３Ａは、分割後の領域数と誤差拡散処理の所要時間との関係の例であり、他の関係となる場合もあり得る。例えば、図３Ｂに示すグラフにおいては、領域数１から領域数を増加させても増加の程度が小さい間は領域の境界でＮライン目の誤差拡散処理が先行しているか否かをチェックする際の所要時間によって誤差拡散処理の所要時間が増加し、さらに領域数を増加させると所要時間が低下し、領域数Ｄmで所要時間が極小となり、さらに領域数が増加するにつれて所要時間が増加していく。なお領域数Ｄ2，Ｄ3においては、誤差拡散処理の所要時間が画像データを分割しない場合と同等である。そこで、このような例においては、領域数をＤ2以上とし、Ｄ3より少なくすれば、画像データを分割しない場合よりも誤差拡散処理の所要時間を短縮することが可能である。さらに、領域数をＤmとすれば、誤差拡散処理の所要時間を極小化することが可能である。
【００４９】
いずれにしても、誤差拡散処理のアルゴリズムが確定した段階で、サンプルの画像データを複数個用意し、分割後の領域数を変更した複数の状態を設定し、誤差拡散処理の所要時間を測定して分割後の領域数と誤差拡散処理の所要時間との関係の統計を取るなどして、分割後の領域数と誤差拡散処理の所要時間との関係を特定することができる。そして、当該関係から、画像データを分割しない場合よりも誤差拡散処理の所要時間を短縮することができるように画素数ｍを特定する。
【００５０】
以上のような誤差拡散処理を実行するため、本実施形態にかかる誤差拡散処理プログラム２１は画像データ取得部２１ａと画像データ分割部２１ｂと遅延画素数特定部２１ｃと誤差拡散処理部２１ｄとを備えている。画像データ取得部２１ａは、誤差拡散処理の対象となる画像データを取得する機能をＣＰＵ２０に実行させるモジュールである。また、画像データ分割部２１ｂは、画像データの各ラインを、分割後の領域内の画素数が複数個となるように分割する機能をＣＰＵ２０に実行させるモジュールである。遅延画素数特定部２１ｃは、分割後の領域のそれぞれにおいて、画像データのＮライン目の画素からの誤差の拡散が未完了であるＮ＋１ライン目の画素にて誤差拡散処理が行われることを防止するための遅延時間を確保するための画素数ｍを特定する機能をＣＰＵ２０に実行させるモジュールである。さらに、誤差拡散処理部２１ｄは、画像データのＮライン目において分割後の領域内でｍ番目に処理される画素の誤差拡散処理が終了した後に、同じ領域内の画像データのＮ＋１ライン目の誤差拡散処理を開始する制御を分割後の領域のそれぞれで行って画像データの各ラインについての誤差拡散処理を行う機能をＣＰＵ２０およびプロセッサー２０ａ，２０ｂ，，，２０ｎに実行させるモジュールである。
【００５１】
誤差拡散処理において、ＣＰＵ２０は、画像データ取得部２１ａの処理により、ＲＡＭ３０内やＣＰＵ２０のキャッシュ内に記録された誤差拡散処理対象の画像データを取得し、画像データ分割部２１ｂや遅延画素数特定部２１ｃ、誤差拡散処理部２１ｄ、プロセッサー２０ａ，２０ｂ，，，２０ｎに対して受け渡す。本実施形態においては、このように、画像データ取得部２１ａの処理により、ＣＰＵ２０内の演算主体に画像データが適宜受け渡される状態で、ＣＰＵ２０やプロセッサー２０ａ，２０ｂ，，，２０ｎが、図４に示すフローチャートに従って誤差拡散処理を実行する。
【００５２】
本実施形態においては、ライン毎の誤差拡散処理を開始する前に、誤差拡散処理の対象となる画像データを分割し、分割後の領域内で同一ラインを構成する画素数に基づいて画素数ｍを決定する構成としている。すなわち、ＣＰＵ２０は、図４に示す誤差拡散処理において、まず、ＣＰＵ２０は、画像データ分割部２１ｂの処理により、誤差拡散対象の画像データを縦方向に平行な分割線で分割する（ステップＳ１００）。なお、本実施形態においては、誤差拡散処理の所要時間を極小化する領域数が予め特定されており、当該領域数となるように画像データを分割する。例えば、図２Ａにて破線で示す分割線によって画像データを分割する。
【００５３】
次に、ＣＰＵ２０は、遅延画素数特定部２１ｃの処理により、分割後の領域内の横方向画素数Ｗと、隣接ラインから逆方向に誤差が拡散される場合の拡散範囲の最大値Ｌと、画素毎の誤差拡散処理の最短所要時間Ｔminと、画素毎の誤差拡散処理の最長所要時間Ｔmaxとを取得する（ステップＳ１１０）。ここで、横方向画素数Ｗは、分割後の領域内でラインと平行な方向の画素数であり、画像データの１ラインの全画素数が領域数で割り切れない場合、各領域においてラインと平行な方向の画素数ができるだけ均等になるように分割がなされ、当該ラインと平行な方向の画素数のうち、最大値がＷに設定される。
【００５４】
隣接ラインから逆方向に誤差が拡散される場合の拡散範囲の最大値Ｌは、誤差拡散処理のアルゴリズムによって予め決定される値である。すなわち、本実施形態において、誤差拡散処理で誤差が拡散される拡散範囲は可変の大きさであり、予め拡散範囲を特定することができる。そこで、本実施形態における誤差拡散処理において、採用され得る拡散範囲の中から、隣接ラインから逆方向に誤差が拡散される場合の拡散範囲を抽出し、その最大値を特定すれば、上述の最大値Ｌとなる。
【００５５】
例えば、図２Ｂにおいて、座標（６，１）が着目画素である場合の誤差の拡散範囲がハッチングを付した周辺画素によって示されているが、当該周辺画素の配置は一例である。すなわち、本実施形態においては、着目画素の階調値に応じて誤差の拡散範囲が動的に変動する。このように誤差の拡散範囲は動的に変動するが、周辺画素の配置パターンは予め決められた配置パターンから選択される。従って、周辺画素の配置パターンの中から拡散範囲が最も広い配置パターンを予め特定可能である。具体的には、図２Ｂに示す１ライン目の座標（６，１）の画素から２ライン目の画素に誤差が拡散される得る範囲を座標（６−ｂ，１）〜座標（６＋ａ，Ｎ＋１）（ａ，ｂは自然数）と表記した場合のｂの最大値を最大値Ｌとして特定すればよい。
【００５６】
画素毎の誤差拡散処理の最短所要時間Ｔminと、画素毎の誤差拡散処理の最長所要時間Ｔmaxとは、実測するなどして予め特定しておくことが可能である。すなわち、誤差拡散処理の画素毎の処理速度は、誤差の拡散範囲やプロセッサー２０ａ，２０ｂ，，，２０ｎの構成等に依存して変動する。そこで、誤差拡散処理が最も高速に実行される条件と最も低速に実行される条件とを設定し、それぞれの条件で誤差拡散処理の所要時間を測定すれば、画素毎の誤差拡散処理の最短所要時間Ｔminと、画素毎の誤差拡散処理の最長所要時間Ｔmaxとを特定することができる。以上のように、ステップＳ１１０においては、処理対象の画像データの分割後の大きさに依存する横方向画素数Ｗと、予め決められた最大値Ｌと、最短所要時間Ｔminと、最長所要時間Ｔmaxとを取得する。
【００５７】
次に、ＣＰＵ２０は、遅延画素数特定部２１ｃの処理により、横方向画素数Ｗと、最大値Ｌと、最短所要時間Ｔminと、最長所要時間Ｔmaxとに基づいて画素数ｍを取得する（ステップＳ１１５）。すなわち、ＣＰＵ２０は、（Ｗ−ｍ）×Ｔmax＝（Ｗ−Ｌ−１）×Ｔminの関係を満たすように画素数ｍを特定する。図２Ｃにおいては、横方向に合計Ｗ個の画素を備える分割後の領域のＮライン目とＮ＋１ライン目の画像データを示している。この例において、Ｎライン目のｍ画素目の処理が終了した後に、Ｎ＋１ライン目の誤差拡散処理が開始されるため、当該開始後においてＮライン目で誤差拡散処理をすべき画素数は（Ｗ−ｍ）個である。そこで、（Ｗ−ｍ）に画素毎の誤差拡散処理の最長所要時間Ｔmaxを乗じると、Ｎライン目のｍ画素目の誤差拡散処理が終了した後、Ｎライン目の最終画素における誤差拡散処理が終了するまでに最も時間を要する場合の所要時間を得ることができる。
【００５８】
一方、Ｎ＋１ライン目においては、Ｎライン目の最終画素（Ｗ画素目）の誤差拡散処理が終了するまでの間に、Ｎライン目の最終画素から逆方向に誤差が拡散される場合の拡散範囲の最大範囲の隣の画素までであれば誤差拡散処理を実行することができ、この場合の画素数は（Ｗ−Ｌ−１）個になる。そこで、（Ｗ−Ｌ−１）に画素毎の誤差拡散処理の最短所要時間Ｔminを乗じると、Ｎ＋１ライン目の誤差拡散処理が開始された後、Ｎライン目の最終画素からの誤差の拡散範囲の最大範囲の隣の画素における誤差拡散処理が終了するまでに最も短時間で処理を行った場合の所要時間を得ることができる。そこで、これらの所要時間が等しくなるように所要時間を上述の等式で結合し、当該等式を解くことで画素数ｍを特定しておけば、分割後の領域においてＮライン目の誤差拡散処理が最低速で行われ、Ｎ＋１ライン目の誤差拡散処理が最高速で行われた場合であっても、Ｎライン目の誤差拡散処理による誤差の拡散が未完了であるＮ＋１ライン目の画素においてＮ＋１ライン目の誤差拡散処理が開始されないようにｍを特定することができる。
【００５９】
次に、ＣＰＵ２０は、誤差拡散処理部２１ｄの処理により、各プロセッサー２０ａ，２０ｂ，，，２０ｎにライン毎の誤差拡散処理を実行させる。このため、ＣＰＵ２０は、まず、ｊ軸方向に沿ったラインの位置に対応したライン番号を示す変数Ｎを１に設定する（ステップＳ１２０）。次にＣＰＵ２０は、プロセッサー２０ａ，２０ｂ，，，２０ｎの中で、演算処理を実行していないプロセッサーを選択し、Ｎライン目の誤差拡散処理を実行させる（ステップＳ１２５）。当該ステップＳ１２５における処理は１ライン目と２ライン目以降とで異なっており、１ライン目においてＣＰＵ２０は、他のラインの進捗を考慮することなく左の画素から右の画素に向けて中断することなく誤差拡散処理を実行する処理を演算処理を実行していないプロセッサーに実行させる。一方、２ライン目以降においてＣＰＵ２０は、演算処理を実行していないプロセッサーに図５に示す処理を実行させる。当該処理の詳細は後述する。なお、ここで、ＣＰＵ２０は、演算処理を実行していないプロセッサーにステップＳ１２５を実行させると、当該プロセッサーの演算終了を待つことなくステップＳ１３０以降の処理を続けて実行する。また、ステップＳ１２５において、演算処理を実行していないプロセッサーが存在していない場合、任意の１個のプロセッサーにおいて演算処理が終了し、演算処理を実行していないプロセッサーが存在するようになるまで待機する。また、ステップＳ１２５に示す処理において、最終ラインを除く各ラインにおいては、分割後の領域内でｍ番目に処理される画素の誤差拡散処理が終了した場合に当該領域内のＮライン目においてｍ画素目の誤差拡散処理が終了したことを示すフラグをオンにする。
【００６０】
ステップＳ１２５において、演算処理を実行していないプロセッサーに図５に示す処理を実行させると、ＣＰＵ２０は、誤差拡散処理部２１ｄの処理により、Ｎが最終ラインに相当する番号であるか否かを判定する（ステップＳ１３０）。例えば、図２Ｂに示す例においてはＮ＝Ｈであるか否かを判定する。ステップＳ１３０にて、Ｎが最終ラインに相当する番号であると判定された場合、ＣＰＵ２０による処理は終了する。この場合、各プロセッサーはステップＳ１２５の処理を最終画素まで実行して処理を終了する。一方、ステップＳ１３０にて、Ｎが最終ラインに相当する番号であると判定されない場合、ＣＰＵ２０は、ライン番号を示す変数Ｎをインクリメントし（ステップＳ１４０）、ステップＳ１２５以降の処理を繰り返す。
【００６１】
次に、ステップＳ１２５におけるＮライン目の誤差拡散処理（Ｎ≧２）について、詳細に説明する。図５は、Ｎライン目の誤差拡散処理（Ｎ≧２）を示しており、この処理において、プロセッサーは、誤差拡散処理部２１ｄの処理により、分割後の領域を示す変数ＭをＭ＝１に設定する（ステップＳ２００）。なお、変数Ｍは左から順に分割後の領域を指定するための変数であり、例えば、図２Ａに示す例において、最も左に位置する領域に対応する変数Ｍは１、中央に位置する領域に対応する変数Ｍは２、最も右に位置する領域に対応する変数Ｍは３である。
【００６２】
次に、プロセッサーは、誤差拡散処理部２１ｄの処理により、領域ＭのＮ−１ライン目のｍ画素目の誤差拡散処理が終了するまで待機する（ステップＳ２０５）。すなわち、プロセッサーは、領域ＭのＮ−１ライン目においてｍ画素目の誤差拡散処理が終了したことを示すフラグを監視し、当該フラグがオンになるまで待機する。
【００６３】
ステップＳ２０５において、領域ＭのＮライン目のｍ画素目の誤差拡散処理が終了したと判定された場合、プロセッサーは、誤差拡散処理部２１ｄの処理により、領域ＭのＮライン目の誤差拡散処理を開始する。すなわち、プロセッサーは領域ＭのＮライン目において最も左側に存在する画素から誤差拡散処理を開始する。
【００６４】
次に、プロセッサーは、誤差拡散処理部２１ｄの処理により、Ｍが最後に処理される領域を示す番号であるか否かを判定する（ステップＳ２１５）。例えば、図２Ａに示す例においてはＮ＝３であるか否かを判定する。ステップＳ２１５にて、Ｍが最後に処理される領域を示す番号であると判定された場合、プロセッサーは領域Ｍ内の最終画素まで誤差拡散処理を実行して処理を終了する。一方、ステップＳ２１５にて、Ｍが最後に処理される領域を示す番号であると判定されない場合、プロセッサーは、領域を指定するための変数Ｍをインクリメントし（ステップＳ２２０）、ステップＳ２０５以降の処理を繰り返す。この結果、分割後の領域のそれぞれにおいて、隣接ライン間で画素数ｍに相当する遅延量の遅延が与えられつつプロセッサー２０ａ，２０ｂ，，，２０ｎによってライン毎の誤差拡散処理が並列的に実行されることになる。
【００６５】
（２）他の実施形態：
以上の実施形態は本発明を実施するための一例であり、分割後の領域のそれぞれにおいて、各ラインに共通の画素数ｍだけライン間の誤差拡散処理の開始タイミングをずらしておくことができる限りにおいて、他にも種々の実施形態を採用可能である。例えば、誤差拡散処理後の画像データにおける階調数は２階調に限定されず、３以上の階調数としても良い。すなわち、誤差拡散処理後の画像データにおける階調数が、プリンターの階調表現力に対応していれば良く、例えば、プリンターにてインク滴の大きさを３段階に調整可能である場合、プリンターにおいて表現可能な１画素の階調数は４であるため、誤差拡散処理後の画像データの階調数を４とすればよい。
【００６６】
さらに、誤差拡散処理を実行する画像処理装置は、コンピューターによって実現される構成に限定されず、プリンターに内蔵されたＣＰＵ等によって実現されても良い。また、並列化を行うためのプロセッサーの構成も上述の実施形態に限定されず、ＣＰＵと複数のプロセッサーが別体に構成されていてもよいし、複数のプロセッサーが複数の装置に分散配置されていても良い。
【００６７】
さらに、上述の実施形態のような複数のプロセッサーがＣＰＵの制御下に置かれている構成以外にも種々の構成を採用可能であり、同一構成の複数のプロセッサーの一つが処理全体の制御を行い、他のプロセッサーが誤差拡散処理を行う構成としても良い。さらに、ＣＰＵとプロセッサーの役割分担は適宜変更可能であり、プロセッサーが画像データの分割を実行する構成や画素数ｍを決定する構成など、種々の構成を採用可能である。すなわち、分割後の領域のそれぞれにおいて、プロセッサーによってあるラインにおいて１画素目の誤差拡散処理を開始した後に他のラインの進捗に依存することなく最終画素まで誤差拡散処理を実行する構成である限りにおいて、種々の構成を採用可能である。
【００６８】
さらに、誤差拡散処理は画素が並ぶ順に処理を進行させれば良く、ライン毎に誤差拡散処理を実行する構成と異なる構成を採用することも可能である。例えば、隣接する２以上のラインを処理単位とし、処理単位が並ぶ順に処理対象に設定して各処理単位において画素が並ぶ順に誤差拡散処理を行う構成に本発明を適用することも可能である。この場合、各処理単位を、分割後の領域内のラインに平行な横方向の画素数が複数個となるように縦方向の分割線によって分割することによって本発明を適用することができる。
【００６９】
図２Ｄは、図２Ａと同様に画像データを分割した場合の分割後の領域と処理単位とを示す図である。当該図２Ｄにおいては、実線の矩形で画素を示し、処理単位を破線で示している。すなわち、図２Ｄに示す例においては、１ライン目と２ライン目とが一つの処理単位Ｂ1、３ライン目と４ライン目とが一つの処理単位Ｂ2、５ライン目と６ライン目とが一つの処理単位Ｂ3を構成する。以下、２個のラインが一つの処理単位とされる。また、分割後の領域の境界を一点鎖線で示しており、分割後の領域であって最も左側に位置する領域はｉ座標値１〜Ｗまでの画素、中央に位置する領域はｉ座標値Ｗ＋１〜２Ｗまでの画素、最も右側に位置する領域はｉ座標値２Ｗ＋１〜３Ｗまでの画素によって構成されている。
【００７０】
この構成においては、処理単位Ｂ1、Ｂ2、Ｂ3が並ぶ順に各処理単位が誤差拡散処理の処理対象に設定されるため、各処理単位Ｂ1、Ｂ2、Ｂ3は上から順に処理対象となる。このような各処理単位において、画素が並ぶ順に誤差拡散処理を行って全画素を逐次着目画素に設定するためには、例えば、処理単位内において縦方向に未処理の画素が存在する間は上から下に向かって縦方向に着目画素を変化させ、縦方向に未処理の画素が存在しなくなった場合に隣接する画素のうち、処理単位内で縦方向の最も上の位置に存在する画素を着目画素とすればよい。
【００７１】
図２Ｄに示す例の処理単位Ｂ1の最も左側に位置する領域であれば、座標（１，１）、座標（１，２）、座標（２，１）、座標（２，２）、、、座標（Ｗ，１）、座標（Ｗ，２）という順で着目画素となる。処理単位Ｂ1の中央に位置する領域であれば、座標（Ｗ＋１，１）、座標（Ｗ＋１，２）、座標（Ｗ＋２，１）、座標（Ｗ＋２，２）、、、座標（２Ｗ，１）、座標（２Ｗ，２）という順で着目画素となる。処理単位Ｂ1の最も右側に位置する領域であれば、座標（２Ｗ＋１，１）、座標（２Ｗ＋１，２）、座標（２Ｗ＋２，１）、座標（２Ｗ＋２，２）、、、座標（３Ｗ，１）、座標（３Ｗ，２）という順で着目画素となる。
【００７２】
以上の構成においては、分割後の領域のそれぞれにおいて、Ｎ番目（Ｎは自然数）に処理対象となる処理単位ＢNに存在する画素からの誤差の拡散が未完了である画素であって、Ｎ＋１番目に処理対象となる処理単位ＢN+1内に存在する画素にて誤差拡散処理が行われることを防止するための遅延時間を確保するために画素数ｍを特定する。すなわち、分割後の領域内においてラインに平行な方向の画素数Ｗと、Ｎ番目に処理対象となる処理単位からＮ＋１番目に処理対象となる処理単位に対して誤差が拡散される場合であって、誤差拡散処理の横方向の進行方向に対して逆方向に誤差が拡散される場合の拡散範囲の最大値Ｌと、画素毎の誤差拡散処理の最短所要時間Ｔminと、画素毎の誤差拡散処理の最長所要時間Ｔmaxとに基づいて、（Ｗ−ｍ）×Ｔmax＝（Ｗ−Ｌ−１）×Ｔminの関係を満たすように画素数ｍを特定する。なお、図２Ｄにおいて、座標（６，２）の画素からの誤差の拡散範囲の最大範囲が図２Ｄにハッチングを付して示す範囲である場合、誤差拡散処理の横方向の進行方向はｉ軸方向であるため、誤差拡散処理の横方向の進行方向に対して逆方向に誤差が拡散される場合の拡散範囲の最大値Ｌは３である。
【００７３】
画素数ｍが特定されれば、分割後の領域のそれぞれにおいて、Ｎ番目に処理対象となる処理単位においてｍ画素目の誤差拡散処理が終了した後に、Ｎ＋１番目に処理対象となる処理単位の誤差拡散処理を開始すればよい。例えば、図２Ｄに示す例において、画素数ｍが１２である場合、処理単位Ｂ1における１２番目の画素である座標（６，２）の誤差拡散処理が終了した後に、処理単位Ｂ2の誤差拡散処理を開始する。なお、以上のような誤差拡散処理において、各処理単位内の画素は異なるプロセッサーで誤差拡散処理が行われるように構成することが好ましい。以上の構成によれば、高速に誤差拡散処理を実行することができる。
【００７４】
さらに、上述の実施形態において、ライン毎に誤差拡散処理を行う場合には同一ラインを同一のプロセッサーで処理していたが、分割後の領域毎に異なるプロセッサーで処理する構成としても良い。
【００７５】
さらに、画像データの分割後の領域数は、分割後の領域内のラインに平行な方向の画素数Ｗが縦方向の画素数Ｈよりも少なくなるように設定しても良い。すなわち、画素数Ｗよりも画素数Ｈの方が少ないのであれば、画像データを９０°回転させて横方向のラインに平行な方向に誤差拡散処理を進行させることで画素数ｍを小さくすることができる。そこで、少なくとも、画像データを回転する必要がなくなるまで画像データを分割するために、分割後の領域内のラインに平行な方向の画素数Ｗが縦方向の画素数Ｈよりも少なくなるように設定してもよい。
【００７６】
さらに、上述の実施形態においては、画像データを分割し、分割後の領域内のラインに平行な方向の画素数Ｗに基づいて画素数ｍを算出していたが、画素数ｍと、隣接ラインから逆方向に誤差が拡散される場合の拡散範囲の最大値Ｌと、画素毎の誤差拡散処理の最短所要時間Ｔminと、画素毎の誤差拡散処理の最長所要時間Ｔmaxとに基づいて画素数Ｗを決定して画像データを分割しても良い。
【符号の説明】
【００７７】
１０…コンピューター、２０…ＣＰＵ、２０ａ，２０ｂ，，，２０ｎ…プロセッサー、２１…誤差拡散処理プログラム、２１ａ…画像データ取得部、２１ｂ…画像データ分割部、２１ｃ…遅延画素数特定部、２１ｄ…誤差拡散処理部、３０…ＲＡＭ、３０ａ…画像データ、４０…ＲＯＭ、５０…ＨＤＤ、５０ａ…画像データ、６０…出力Ｉ／Ｆ、７０…プリンター
【図１】
2012134913.tif 000003
【図２】
2012134913.tif 000004
【図３】
2012134913.tif 000005
【図４】
2012134913.tif 000006
【図５】
2012134913.tif 000007