(57)【要約】【課題】ＳＩＭＤ型並列処理プロセッサを用い、処理済みの過去の結果が次の画素の処理に影響を与えるようなヒステリシスを持った逐次処理についても、通常の並列演算による実行を可能とする。【解決手段】所定の回数だけ並列演算を繰り返すとともに、この各並列演算では、参照可能な所定の方向（図４の右方向又は左方向）の隣接するＰＥ５１における少なくとも１つの演算結果を用いる。この並列演算を所定の回数だけ繰り返した結果、各ＰＥ５１に並んだ１次元列データを所定の方向の最初（所定の方向が図４の右方向なら右端、左方向なら左端）のＰＥ５１から順次所定の回数だけ逐次処理した結果が、その最初のＰＥ５１から順次各ＰＥ５１に得られるようにする。【選択図】　　図４
2004110250.tif 000002
【特許請求の範囲】
【請求項１】
左右に複数並ぶ各ＰＥ（プロセッサ・エレメント）が、その隣接する少なくとも左右どちらか一方のＰＥのレジスタ値を参照できるＳＩＭＤ（Ｓｉｎｇｌｅ　Ｉｎｓｔｒｕｃｔｉｏｎ−ｓｔｒｅａｍ　Ｍｕｌｔｉｐｌｅ　Ｄａｔａ−ｓｔｒｅａｍ）型並列処理プロセッサと、
前記参照可能な左右一方の隣接する前記ＰＥにおける少なくとも１つの演算結果を用いて所定の回数だけ前記ＳＩＭＤ型並列処理プロセッサで並列演算を繰り返すことにより、前記各ＰＥに並んだ１次元列データを、前記演算結果を用いたのが右側なら右側の端、左側なら左側の端の前記ＰＥから順次所定の回数だけ逐次処理した結果が、その端のＰＥから順次前記各ＰＥに得られるように処理する逐次処理手段と、
を備えている逐次データ処理装置。
【請求項２】
前記逐次処理手段は、２値画像データの黒を示す値のランレングスを前記逐次処理として求める、請求項１に記載の逐次データ処理装置。
【請求項３】
前記逐次処理手段は、階調データの誤差拡散処理結果を前記逐次処理として求める、請求項１に記載の逐次データ処理装置。
【請求項４】
前記逐次処理手段は、前記各ＰＥで各画素の前記２値画像データの値が０であるときは、当該ＰＥの所定のレジスタに０の値をセットし、前記２値画像データの値が０でないときは、当該ＰＥの前記レジスタに右隣又は左隣の前記ＰＥの所定のレジスタの値に１を加えた値をセットする演算を前記並列処理で実行する、請求項２に記載の逐次データ処理装置。
【請求項５】
前記逐次処理手段は、各画素の入力階調データをｎビットとしたときに、前記各ＰＥで前記入力階調データから右又は左２画素の２値化後の誤差を重みづけした値を引いた値が所定の閾値以上であるときは、当該ＰＥの所定のレジスタに“２ｎ−１”をセットし、そうでないときは、前記レジスタに０をセットする演算を前記並列処理で実行する、請求項２に記載の逐次データ処理装置。
【請求項６】
原稿の画像を読取るスキャナと、
この読取った画像データに対して前記逐次処理を行なう請求項２〜５の何れかの一に記載の逐次データ処理装置と、
を備えている画像読取装置。
【請求項７】
請求項６に記載の画像読取装置と、
前記逐次データ処理装置で処理後のデータを用い、用紙上に画像の形成を行なうプリンタエンジンと、
を備えている画像形成装置。
【請求項８】
左右に複数並ぶ各ＰＥ（プロセッサ・エレメント）が、その隣接する少なくとも左右どちらか一方のＰＥのレジスタ値を参照できるＳＩＭＤ（Ｓｉｎｇｌｅ　Ｉｎｓｔｒｕｃｔｉｏｎ−ｓｔｒｅａｍ　Ｍｕｌｔｉｐｌｅ　Ｄａｔａ−ｓｔｒｅａｍ）型並列処理プロセッサに対して、前記参照可能な左右一方の隣接する前記ＰＥにおける少なくとも１つの演算結果を用いて所定の回数だけ前記ＳＩＭＤ型並列処理プロセッサで並列演算を繰り返すことにより、前記各ＰＥに並んだ１次元列データを、前記演算結果を用いたのが右側なら右側の端、左側なら左側の端の前記ＰＥから順次所定の回数だけ逐次処理した結果が、その端のＰＥから順次前記各ＰＥに得られるように処理する逐次処理を実行させる、前記ＳＩＭＤ型並列処理プロセッサに読み取り可能なプログラム。
【請求項９】
請求項８に記載のプログラムを記憶している、記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、逐次データ処理装置、画像読取装置、画像形成装置、プログラム及び記憶媒体に関する。
【０００２】
【従来の技術】
デジタル複写機などにおいて、大量の画像処理をリアルタイムに行なう場合には、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ　Ｓｐｅｃｉｆｉｃ　Ｉｎｔｅｇｒａｔｅｄ　Ｃｉｒｃｕｉｔ）が用いられてきたが、近年は、ＳＩＭＤ（Ｓｉｎｇｌｅ　Ｉｎｓｔｒｕｃｔｉｏｎ−ｓｔｒｅａｍ　Ｍｕｌｔｉｐｌｅ　Ｄａｔａ−ｓｔｒｅａｍ）型並列処理プロセッサによる処理によっても実現可能となってきた。画像処理の中でも、２値化処理、フィルタリング処理、階調処理などについては、ＳＩＭＤ型並列処理プロセッサを用いた並列処理が可能である。
【０００３】
しかしながら、誤差拡散処理など、画素ごとに順番に処理を行って、処理済みの過去の結果が次の画素の処理に影響を与えるようなヒステリシスを持った逐次処理については、通常の並列演算による実行ができない不具合があった。
【０００４】
そこで、ＳＩＭＤ型並列処理プロセッサとは別に、逐次処理用のＡＳＩＣを搭載して、並列処理可能な処理をＳＩＭＤ型並列処理プロセッサで実行し、逐次処理は逐次処理専用のＡＳＩＣで実行するように分担する技術が提案されている（特許文献１〜４参照）。
【０００５】
【特許文献１】
特開平９−２８２３０５号公報
【特許文献２】
特開２００１−２７４９９３公報
【特許文献３】
特開平９−２８２３０５号公報
【特許文献４】
特開２００２−１０８６０４公報
【０００６】
【発明が解決しようとする課題】
しかしながら、特許文献１〜４に開示の技術では、逐次処理ごとに専用のＡＳＩＣを組み合わせる必要があり、全体の画像処理中に逐次処理の必要な割合が低い場合に、専用のＡＳＩＣを組み合わせることは装置のコスト増大を招く問題点があった。
【０００７】
本発明の目的は、ＳＩＭＤ型並列処理プロセッサを用い、処理済みの過去の結果が次の画素の処理に影響を与えるようなヒステリシスを持った逐次処理についても、通常の並列演算による実行を可能とすることである。
【０００８】
【課題を解決するための手段】
請求項１に記載の発明は、左右に複数並ぶ各ＰＥ（プロセッサ・エレメント）が、その隣接する少なくとも左右どちらか一方のＰＥのレジスタ値を参照できるＳＩＭＤ型並列処理プロセッサと、前記参照可能な左右一方の隣接する前記ＰＥにおける少なくとも１つの演算結果を用いて所定の回数だけ前記ＳＩＭＤ型並列処理プロセッサで並列演算を繰り返すことにより、前記各ＰＥに並んだ１次元列データを、前記演算結果を用いたのが右側なら右側の端、左側なら左側の端の前記ＰＥから順次所定の回数だけ逐次処理した結果が、その端のＰＥから順次前記各ＰＥに得られるように処理する逐次処理手段と、を備えている逐次データ処理装置である。
【０００９】
したがって、特別のハードウエアを併用しなくても、ＳＩＭＤ型並列処理プロセッサにより並列演算のほか逐次処理も実行することができる。
【００１０】
請求項２に記載の発明は、請求項１に記載の逐次データ処理装置において、前記逐次処理手段は、２値画像データの黒を示す値のランレングスを前記逐次処理として求める。
【００１１】
これは、例えば、前記逐次処理手段は、前記各ＰＥで各画素の前記２値画像データの値が０であるときは、当該ＰＥの所定のレジスタに０の値をセットし、前記２値画像データの値が０でないときは、当該ＰＥの前記レジスタに右隣又は左隣の前記ＰＥの所定のレジスタの値に１を加えた値をセットする演算を前記並列処理で実行する、請求項２に記載の逐次データ処理装置とすることができる（請求項４）。
【００１２】
したがって、特別のハードウエアを併用しなくても、ＳＩＭＤ型並列処理プロセッサにより、ヒステリシスを持った逐次処理を伴なう、２値画像データの黒を示す値のランレングスを求める演算を行なうことができる。
【００１３】
請求項３に記載の発明は、請求項１に記載の逐次データ処理装置において、前記逐次処理手段は、階調データの誤差拡散処理結果を前記逐次処理として求める。
【００１４】
これは、例えば、前記逐次処理手段は、各画素の入力階調データをｎビットとしたときに、前記各ＰＥで前記入力階調データから右又は左２画素の２値化後の誤差を重みづけした値を引いた値が所定の閾値以上であるときは、当該ＰＥの所定のレジスタに“２ｎ−１”をセットし、そうでないときは、前記レジスタに０をセットする演算を前記並列処理で実行する、請求項２に記載の逐次データ処理装置とすることができる（請求項５）。
【００１５】
したがって、特別のハードウエアを併用しなくても、ＳＩＭＤ型並列処理プロセッサにより、ヒステリシスを持った逐次処理を伴なう、階調データの誤差拡散処理の演算を行なうことができる。
【００１６】
請求項６に記載の発明は、原稿の画像を読取るスキャナと、この読取った画像データに対して前記逐次処理を行なう請求項２〜５の何れかの一に記載の逐次データ処理装置と、を備えている画像読取装置である。
【００１７】
したがって、画像データに様々な処理を行なう場合に、並列処理のほかにヒステリシスを持った逐次処理を含んでいるような場合にも、特別のハードウエアを併用しなくても、ＳＩＭＤ型並列処理プロセッサにより実行することができる。
【００１８】
請求項７に記載の発明は、請求項６に記載の画像読取装置と、前記逐次データ処理装置で処理後のデータを用い、用紙上に画像の形成を行なうプリンタエンジンと、を備えている画像形成装置である。
【００１９】
したがって、画像データに様々な処理を行なう場合に、並列処理のほかにヒステリシスを持った逐次処理を含んでいるような場合にも、特別のハードウエアを併用しなくても、ＳＩＭＤ型並列処理プロセッサにより実行することができる。
【００２０】
請求項８に記載の発明は、左右に複数並ぶ各ＰＥ（プロセッサ・エレメント）が、その隣接する少なくとも左右どちらか一方のＰＥのレジスタ値を参照できるＳＩＭＤ（Ｓｉｎｇｌｅ　Ｉｎｓｔｒｕｃｔｉｏｎ−ｓｔｒｅａｍ　Ｍｕｌｔｉｐｌｅ　Ｄａｔａ−ｓｔｒｅａｍ）型並列処理プロセッサに対して、前記参照可能な左右一方の隣接する前記ＰＥにおける少なくとも１つの演算結果を用いて所定の回数だけ前記ＳＩＭＤ型並列処理プロセッサで並列演算を繰り返すことにより、前記各ＰＥに並んだ１次元列データを、前記演算結果を用いたのが右側なら右側の端、左側なら左側の端の前記ＰＥから順次所定の回数だけ逐次処理した結果が、その端のＰＥから順次前記各ＰＥに得られるように処理する逐次処理を実行させる、前記ＳＩＭＤ型並列処理プロセッサに読み取り可能なプログラムである。
【００２１】
したがって、特別のハードウエアを併用しなくても、ＳＩＭＤ型並列処理プロセッサにより並列演算のほか逐次処理も実行することができる。
【００２２】
請求項９に記載の発明は、請求項８に記載のプログラムを記憶している、記憶媒体である。
【００２３】
したがって、記憶しているプログラムにより、特別のハードウエアを併用しなくても、ＳＩＭＤ型並列処理プロセッサにより並列演算のほか逐次処理も実行することができる。
【００２４】
【発明の実施の形態】
本発明の一実施の形態について説明する。
【００２５】
図１は、本発明の一実施の形態であるデジタル複写機１の概略構成を示すブロック図である。このデジタル複写機１は、原稿の画像を読取るスキャナ２と、この読取った画像データに様々な処理を施す画像処理装置３と、この処理後の画像データで用紙上に画像の形成を行なうプリンタエンジン４と、デジタル複写機１の全体を制御するマイクロコンピュータを備えた制御部５とを備えている。プリンタエンジン４の印刷方式は、電子写真方式のほか、インクジェット方式、昇華型熱転写方式、銀塩写真方式、直接感熱記録方式、溶融型熱転写方式など、様々な方式を適用することができる。
【００２６】
画像処理装置３は、スキャナ２で読取った画像データに対して、２値化処理、フィルタリング処理、階調処理、誤差拡散処理など、様々な処理を行なうが、その処理の全部又は一部は、所定の制御プログラムに基づいて、ＳＩＭＤ（ＳｉｎｇｌｅＩｎｓｔｒｕｃｔｉｏｎ−ｓｔｒｅａｍ　Ｍｕｌｔｉｐｌｅ　Ｄａｔａ−ｓｔｒｅａｍ）型並列処理プロセッサが実行する。
【００２７】
図２は、このＳＩＭＤ型並列処理プロセッサを用いた処理系のハードウエア構成を示すブロック図である。図２に示すように、この処理系は、各種演算を行い、各部を集中的に制御するＳＩＭＤ型並列処理プロセッサ４１と、本発明のプログラムを実施するＳＩＭＤ型並列処理プロセッサ４１で読取り可能な各種の制御プログラムや、各種の固定データを記憶していて、本発明の記憶媒体を実施するＲＯＭ４５（フラッシュメモリも含む）と、各種データを書き換え可能に記憶し、ＳＩＭＤ型並列処理プロセッサ４１の作業エリアとなるＲＡＭ４６と、Ｉ／Ｏポート４７とが、バス４８で接続されている。ＲＯＭ４５は、そのフラッシュメモリに記憶されている制御プログラムなどを、Ｉ／Ｏポート４７を介し、図示しない外部装置からダウンロードして書き換えることが可能である。
【００２８】
図３、図４は、ＳＩＭＤ型並列処理プロセッサ４１の構成を示すブロック図である。図３に示すように、ＳＩＭＤ型並列処理プロセッサ４１は、グローバルプロセッサ４２を備えている。グローバルプロセッサ４２は、図示しないプログラムＲＡＭとデータＲＡＭとを内蔵し、ＲＯＭ４５に格納されている制御プログラムを解読して、各種制御信号を生成する。この制御信号は内蔵する各種ブロックの制御以外にもレジスタファイル４３、演算アレイ４４に供給される。また、ＧＰ（グローバルプロセッサ）命令実行時は、ＳＩＭＤ型並列処理プロセッサ４１が内蔵する後述の汎用レジスタ５３、ＡＬＵ（算術論理演算器）５５等を使用して、各種演算処理、プログラム制御処理を行なう。
【００２９】
レジスタファイル４３は、ＰＥ（プロセッサ・エレメント）命令で処理されるデータを保持している。ＰＥ命令は、ＳＩＭＤタイプの命令であり、レジスタファイル４３に保持されている複数のデータに対して同時に同じ処理を行なう。このレジスタファイル４３からのデータの読み出し、書き込みの制御は、グローバルプロセッサ４２からの制御によって行なわれる。読み出されたデータは演算アレイ４４に送られ、演算アレイ４４での演算処理後にレジスタファイル４３に書き込まれる。
【００３０】
演算アレイ４４は、ＰＥ命令の演算処理を行なう。処理の制御はすべてグローバルプロセッサ４２から行なわれる。
【００３１】
ＳＩＭＤ型並列処理プロセッサ４１は１次元ＳＩＭＤ型並列処理プロセッサであり、複数のデータに対し、単一の命令を並列に実行させることができる。図４に示すように、レジスタファイル４３は複数のＰＥ（プロセッサ・エレメント）５１からなる１次元ＰＥアレイ５２を備えている。
【００３２】
グローバルプロセッサ４２には、前述のように本プロセッサ４１のプログラム格納用のプログラムＲＡＭと、演算データ格納用のデータＲＡＭに内蔵されている他、プログラムのアドレスを保持するプログラムカウンタ（ＰＣ）、演算処理のデータ格納のための汎用レジスタ、レジスタ退避、復帰時に退避先データＲＡＭアドレスを保持するスタックポインタ（ＳＰ）、サブルーチンコール時にコール元のアドレスを保持するリンクレジスタ（ＬＳ）、同じくＩＲＱ時とＮＭＩ時の分岐元アドレスを保持するＬＩレジスタ、ＬＮレジスタ、プロセッサの状態を保持するプロセッサステータスレジスタ（Ｐ）が内蔵されている（いずれも図示せず）。
【００３３】
グローバルプロセッサ４２は、これらのレジスタと図示しない命令デコーダ、ＡＬＵ（論理演算器）、メモリ制御回路、割り込み制御回路、外部Ｉ／Ｏ制御回路、ＧＰ演算制御回路を使用して、ＧＰ命令の実行を行なう。また、ＰＥ命令実行時は命令デコーダ、図示しないレジスタファイル制御回路、ＰＥ演算制御回路を使用して、レジスタファイル４３の制御と演算アレイ４４の制御を行なう。
【００３４】
レジスタファイル４３は２５６個のＰＥ（プロセッサ・エレメント）５１からなる１次元ＰＥアレイ５２を備えている。各ＰＥ５１には、８ビットのレジスタ５３が３２本内蔵されている。各レジスタ５３は、ＰＥ５１ごとにＲ０，Ｒ１，Ｒ２，…，Ｒ３１と呼ばれている。それぞれのレジスタ５３は演算アレイ４４に対して１つの読み出しポートと１つの書き込みポートを備えており、８ビットのリード／ライト兼用のバスで演算アレイ４４からアクセスされる。３２本のレジスタ５３の内、２４本（Ｒ０〜Ｒ２３）はプロセッサ４１の外部からアクセス可能であり、外部からクロックとアドレス、リード／ライト制御を入力することで、任意のレジスタ５３に読み書きすることできる。残りの８本（Ｒ２４〜Ｒ３１）のレジスタ５３はＰＥ演算の一時的な演算データ保存用として使用されるが、グローバルプロセッサ４２のデータＲＡＭのデータを書き込むこともできる。グローバルプロセッサ４２からのライト制御と演算アレイ４４の条件レジスタ（Ｔレジスタ）５８の条件により、レジスタファイル４３に内蔵される８本（Ｒ２４〜Ｒ３１）のレジスタ５３にグローバルプロセッサ４２のデータＲＡＭのデータを、条件が成立している複数のＰＥ５１に同時に書き込みが可能である。また、データＲＡＭは６４ビットの出力ポートを持つため、１つのＰＥ５１に対しても８本のレジスタ（Ｒ２４〜Ｒ３１）に同時に６４ビットの書き込みが可能である。
【００３５】
演算アレイ４４は１６ビットＡＬＵ５５と、１６ビットＡレジスタ５６、Ｆレジスタ５７を内蔵している。さらに、条件選択５９を内蔵している。ＰＥ命令による演算はレジスタファイル４３から読み出されたデータもしくはグローバルプロセッサ４２から与えられたデータをＡＬＵ５５の片側の入力として、もう片側にはＡレジスタ５６の内容を入力として結果をＡレジスタ５６に格納する。したがって、ＡレジスタとＲ０〜Ｒ３１レジスタ５３又はグローバルプロセッサ４２から与えられたデ一タとの演算がおこなわれることとなる。レジスタファイル４３の８ビットのデータは演算アレイ４４との接続部に配置されている図示しないシフト＆拡張回路により任意ビットを左シフトしてＡＬＵ５５に入力する。
【００３６】
各レジスタ５３は図示しないアドレスバス及びデータバスで接続されており、処理を規定する命令コード、処理の対象となるデータを格納する。レジスタ５３の内容はＡＬＵ５５に入力され、演算処理結果はＡレジスタ５６に格納される。結果をＰＥ５１の外部に取出すために、Ｆレジスタ５７に一旦退避させる。Ｆレジスタ５７の内容を取出すことにより、対象データに対する処理結果が得られる。命令コードは各ＰＥ５１に同一内容で与え、処理の対象データをＰＥ５１ごとに異なる状態で与え、各ＰＥ５１は隣接するＰＥ５１のレジスタ５３の保持しているデータの内容をマルチプレクサ５４において参照することで、演算結果は並列処理され、各Ａレジスタ５６に出力される。
【００３７】
このようなＳＩＭＤ型並列処理プロセッサ４１がＲＯＭ４５に格納されている制御プログラムに従い、ＲＡＭ４６を作業エリアとして動作することにより、以下のような処理を実行する。
【００３８】
すなわち、この制御制御プログラムは、ＳＩＭＤ型並列処理プロセッサ４１上で、逐次処理を、並列処理を複数回繰り返すことで実現する。
【００３９】
具体的には、ＳＩＭＤ型並列処理プロセッサ４１は、各ＰＥ５１は隣接するＰＥ５１のレジスタ５３の保持しているデータの内容をマルチプレクサ５４において参照することができるので、このＳＩＭＤ型並列処理プロセッサ４１が、各ＰＥ５１が隣接する右側のＰＥ５１、左側のＰＥ５１又は左右両側のＰＥ５１を参照できる構成であれば、以下のような逐次処理により逐次処理手段を実行可能である。
【００４０】
すなわち、所定の回数だけ並列演算を繰り返すとともに、この各並列演算では、参照可能な所定の方向（図４の右方向又は左方向）の隣接するＰＥ５１における少なくとも１つの演算結果を用いる。この並列演算を所定の回数だけ繰り返した結果、各ＰＥ５１に並んだ１次元列データを所定の方向の最初（所定の方向が図４の右方向なら右端、左方向なら左端）のＰＥ５１から順次所定の回数だけ逐次処理した結果が、その最初のＰＥ５１から順次各ＰＥ５１に得られるようにする。
【００４１】
このように、各ＰＥ５１での処理では、所定の方向の参照可能な隣接ＰＥ５１のレジスタ５３にある１回前の並列演算の処理結果を参照するので、各並列演算の度に、所定の方向の最初のＰＥ５１から順次逐次処理結果が確定していく。一度逐次処理結果が確定したものは、その後の並列演算においても、その処理結果は変わらない。
【００４２】
以下では、かかる処理を用いた画像処理装置２における処理の例として、黒ラン長の算出と、誤差拡散処理について説明する。
【００４３】
［黒ラン長の算出について］
ＳＩＭＤ型並列処理プロセッサ４１上で、スキャナ２で読取った画像データを対象に、グレー画像を２値化して（並列演算）黒ラン長を計数する。黒ラン長とは、２値画像データの黒を示す値のランレングスである。
【００４４】
入力グレー画像（たとえば２５６階調濃度値）の画素値をＸｉｊとする。ｉ，ｊは画素の２次元座標値とする。
【００４５】
そして、所定の閾値ｔｈｒとの比較により単純な２値化処理を行なう。すなわち、その２値化結果をＹｉｊとすると、
2004110250.tif 000003
である。
【００４６】
この２値化処理部分は、画素ごとに、すなわち、ＰＥ５１ごとに並列に演算可能であり、通常のＳＩＭＤ型並列処理プロセッサの並列演算命令を用いてプログラムすることができる。
【００４７】
次に、上記２値化結果のＹｉｊに対して、ライン順次に各ラインにおいて１次元方向に１の連続する長さ（以下１を黒、０を白とし、黒を示す１の連続を黒ランと呼ぶ）、すなわち黒ランの長さ（ランレングス）を求める。この部分は並列演算で一度に求めることができず、逐次処理が必要な部分である。
【００４８】
この処理は、以下のように特定の方向（図４における右側又は左側）のＰＥ５１の演算結果を参照しつつ、並列演算を繰り返すことで実行される。
【００４９】
図５に、この処理における各並列演算の後のレジスタ５３の値を示す。
【００５０】
入力２値化データＹｉｊの１ライン分の値が、図５（ａ）のレジスタ５３（Ｒ１）にセットされる。図５（ｂ）のレジスタ５３（Ｒ２）には、黒ラン長（１の値のランレングス）のカウント値が出力される。図５（ｂ）には、並列演算の繰返しごとの値の変化を上から下へ並べて示している。図５（ａ），（ｂ）では、並列する９個のＰＥ５１の横一列のレジスタ５３がそれぞれ示されている。レジスタＲ２の初期値はすべて０とする。この例では、各ＰＥ５１は左側のＰＥ５１の値を参照するものとし、一番左のＰＥ５１から参照される左隣（存在しない）のレジスタ値は０になるものとする。並列演算の繰り返しの所定の回数はＰＥ５１の数と同じ９回とする。図５において、“＊”は逐次処理結果の確定したＰＥ５１を示す。
【００５１】
９回の並列演算の後におけるレジスタＲ２の各値は、図５（ｂ）に上から順に示すとおりである。１回の並列演算ごとに図５の左端のＰＥ５１から順に逐次処理結果が確定する。そして、図５（ｂ）の最下段に示すように、２つの黒ランの長さが、レジスタＲ２で０に囲まれた数字列の最後の値として求まる（この例では、黒ラン長３，２のものが１つずつである）。
【００５２】
図６は、各ＰＥ５１における演算を説明するフローチャートである。すなわち、各ＰＥ５１において、レジスタＲ１の値が０であるときは（ステップＳ１のＹ）、当該ＰＥ５１のレジスタＲ２に０の値をセットする（ステップＳ２）。レジスタＲ１の値が０でないときは（ステップＳ１のＮ）、当該ＰＥ５１のレジスタＲ２に左隣のＰＥ５１のレジスタＲ２の値に１を加えた値をセットする（ステップＳ３）。図５の例では、以上の演算を各ＰＥ５１で実行する並列処理を繰り返している。
【００５３】
［誤差拡散処理について］
誤差拡散処理とは、階調データを２値化し、２値で擬似的に中間調を表現する処理であり、２値化済みの注目画素の複数の近傍画素の２値化後の誤差に重みづけを行い、注目画素の値からこの誤差を減算して注目画素の２値化を行なう。
【００５４】
たとえば図４に示すように、注目画素の左隣およびその左隣の２値化済みの２つの近傍画素の２値化後の誤差に重みづけを行い、注目画素の値からこの誤差を引き注目画素の２値化を行なう。
【００５５】
すなわち、
入力階調データ（ｎビット）をｆ（Ｉ）、誤差拡散処理結果２値出力データ（０又は“２ｎ−１”）をｇ（Ｉ）とすると、
2004110250.tif 000004
ここで、
ｔｈｒｅｓｈ：２値化のしきい値
２値化時の誤差：Ｅ（Ｉ）＝ｇ（Ｉ）−ｆ（Ｉ）
誤差伝播後の入力階調データ：ｆ’（Ｉ）
＝ｆ（Ｉ）−Ｅ（Ｉ−１）＊（５／８）−Ｅ（Ｉ−２）＊（３／８）
である。
【００５６】
図７は、この場合の誤差拡散マトリックス６１、すなわち、注目画素の２値化時に過去の２値化済みの画素での２値化時の誤差を伝播させる際の重み係数である。
【００５７】
図８は、かかる場合の処理をＳＩＭＤ型並列処理プロセッサ４１で行なうときの、前述のレジスタＲ１の値（ａ）、レジスタＲ２の変化（ｂ）を黒ラン長の算出の場合と同様に示している。
【００５８】
入力階調データ（ここでは３ｂｉｔ階調データとする）がレジスタＲ１にセットされ、レジスタＲ２には誤差拡散２値化処理結果が出力される。なお、レジスタＲ２の初期値はすべて０とする。また、一番左のＰＥ５１から参照される左隣（存在しない）のレジスタ値は０になるものとする。誤差拡散は、本例では、図７に示すように、注目画素６２の左隣及びその左隣の２値化済みの２つの近傍画素６３，６４の２値化後の誤差に重みづけを行い、注目画素６２の値からこの誤差を引いた後、注目画素６２の２値化を行なう。かかる処理を左端の画素から順次行なっていく。２値化の閾値ｔｈｒｅｓｈは、この例では４とする。ここでも、ＰＥ５１の数を９、並列演算の繰り返しの所定の回数はＰＥ５１の数と同じ９回とする。“＊”は逐次処理結果の確定したＰＥ５１を示す。
【００５９】
９回の並列演算の後、全ＰＥの入力階調データに対する誤差拡散２値化処理結果が、図８（ｂ）の最下欄のレジスタＲ２に示すように求まる。
【００６０】
図９は、各ＰＥ５１における演算を説明するフローチャートである。すなわち、各ＰＥ５１において、レジスタＲ１にある入力階調データから左２画素の２値化後の誤差を重みづけした値を引いた値が閾値ｔｈｒｅｓｈ以上であるときは（ステップＳ１１のＹ）、レジスタＲ２に“２ｎ−１”をセットし（ステップＳ１２）、そうでないときは（ステップＳ１１のＮ）、レジスタＲ２に０をセットする（ステップＳ１３）。
【００６１】
【発明の効果】
請求項１，８，９に記載の発明は、特別のハードウエアを併用しなくても、ＳＩＭＤ型並列処理プロセッサにより並列演算のほか逐次処理も実行することができる。
【００６２】
請求項２，４に記載の発明は、請求項１に記載の発明において、特別のハードウエアを併用しなくても、ＳＩＭＤ型並列処理プロセッサにより、ヒステリシスを持った逐次処理を伴なう、２値画像データの黒を示す値のランレングスを求める演算を行なうことができる。
【００６３】
請求項３，５に記載の発明は、請求項１に記載の発明において、特別のハードウエアを併用しなくても、ＳＩＭＤ型並列処理プロセッサにより、ヒステリシスを持った逐次処理を伴なう、階調データの誤差拡散処理の演算を行なうことができる。
【００６４】
請求項６，７に記載の発明は、画像データに様々な処理を行なう場合に、並列処理のほかにヒステリシスを持った逐次処理を含んでいるような場合にも、特別のハードウエアを併用しなくても、ＳＩＭＤ型並列処理プロセッサにより実行することができる。
【図面の簡単な説明】
【図１】本発明の一実施の形態であるデジタル複写機の概略構成を示すブロック図である。
【図２】ＳＩＭＤ型並列処理プロセッサを用いた処理系のハードウエア構成を示すブロック図である。
【図３】ＳＩＭＤ型並列処理プロセッサの概略構成を示すブロック図である。
【図４】ＳＩＭＤ型並列処理プロセッサの詳細な構成を示すブロック図である。
【図５】ＳＩＭＤ型並列処理プロセッサを用いた黒ラン長の演算の説明図である。
【図６】黒ラン長の演算における各ＰＥの演算を説明するフローチャートである。
【図７】誤差拡散マトリックスの説明図である。
【図８】ＳＩＭＤ型並列処理プロセッサを用いた誤差拡散処理の演算の説明図である。
【図９】誤差拡散処理の演算における各ＰＥの演算を説明するフローチャートである。
【符号の説明】
１　　　画像形成装置、画像読取装置
２　　　スキャナ
４　　　プリンタエンジン
４１　　ＳＩＭＤ型並列処理プロセッサ
５１　　ＰＥ（プロセッサ・エレメント）
【図１】
2004110250.tif 000005
【図２】
2004110250.tif 000006
【図３】
2004110250.tif 000007
【図４】
2004110250.tif 000008
【図５】
2004110250.tif 000009
【図６】
2004110250.tif 000010
【図７】
2004110250.tif 000011
【図８】
2004110250.tif 000012
【図９】
2004110250.tif 000013