(57)【特許請求の範囲】
【請求項１】
現在の画素の濃淡を表現する輝度値を、それぞれのディザ行列しきい値と比較することにより、画素オン／オフ信号を供給する第１比較器と、
前記現在の画素の濃淡を表現する前記輝度値を量子化することにより、１からqの範囲で量子化された画素値pを生成する多重しきい値処理装置と、
１からqの範囲で複数の量子化値を格納しており、前記量子化された画素値pにより制御された、アクティブ量子化値としてのp個の量子化値を出力するとともに、フレーム信号に応じて、有している前記量子化値をシフトさせる量子化テーブルと、
量子化されたディザ行列のしきい値を前記アクティブ量子化値と比較して、アクティブ量子化しきい値信号を生成する第２比較器と、
前記画素オン／オフ信号及び前記アクティブ量子化しきい値信号に応じて、q個のフレームからなる表示周期に前記現在の画素を、平均濃度値p/qで表示装置に表示するための画素出力信号を生成する画素出力生成器と、
を有することを特徴とする表示装置駆動用回路。
【請求項２】
請求項１に記載の表示装置駆動用回路において、さらに複数のしきい値を格納するディザ行列を有することを特徴とする表示装置駆動用回路。
【請求項３】
請求項２に記載の表示装置駆動用回路において、前記現在の画素の座標に応じて、前記複数のしきい値を格納するディザ行列をアドレス指定して、それぞれのディザ行列しきい値を出力するカウンタを少なくとも１個さらに有することを特徴とする表示装置駆動用回路。
【請求項４】
請求項２に記載の表示装置駆動用回路において、前記それぞれのディザ行列しきい値を量子化して、１からqの範囲で量子化されたディザ行列しきい値を生成する多重しきい値処理装置をさらに有することを特徴とする表示装置駆動用回路。
【請求項５】
請求項２に記載の表示装置駆動用回路において、ディザ行列を生成するディザ行列生成器をさらに有しており、このディザ行列生成器は、
ディザ行列しきい値を含有し、かつ繰り返しディザ行列の位置にしきい値を割り当てることにより、画像の部分領域のそれぞれの部分領域画素と関連しているディザ行列位置からなるディザ行列を生成するディザ行列生成手段と、
複数の部分領域画素それぞれに関して、部分領域が割り当てられるしきい値に対応する一様な濃度階調値を示している場合に、ドットを受取る画素が、複数の部分領域画素の周辺でクラスタ（群れ）になっている相対的な詰り具合を決定する第１決定手段と、
前記第１決定手段により決定された詰り具合が最大である部分領域画素をそれぞれ識別する識別手段と、
前記識別手段により識別された複数の部分領域画素それぞれに関して、部分領域が割り当てられるしきい値に対応する一様な濃度階調値を示している場合に、ドットを受け取るいくつかの部分領域画素を除き、割り当てられるしきい値に依存している階数域に存在する階数を割り当てられた部分領域画素が、複数の部分領域画素の周辺でクラスタ（群れ）になっている相対的詰り具合を決定する第２決定手段と、
前記第２決定手段により決定された詰り具合が最大である部分領域画素を少なくとも一つ選択する選択手段と、
前記選択手段により選択された部分領域画素と関連しているディザ行列位置にしきい値を割り当てるしきい値割り当て手段と、
を有することを特徴とする表示装置駆動用回路。
【請求項６】
請求項１に記載の表示装置駆動用回路において、前記量子化テーブルがシフトレジスタからなることを特徴とする表示装置駆動用回路。
【請求項７】
請求項６に記載の表示装置駆動用回路において、前記量子化テーブルが循環シフトレジスタからなることを特徴とする表示装置駆動用回路。
【請求項８】
請求項６に記載の表示装置駆動用回路において、前記量子化テーブルが循環線形シフトレジスタからなることを特徴とする表示装置駆動用回路。
【請求項９】
現在の画素の濃淡を表現する輝度値を、それぞれのディザ行列しきい値と比較することにより、画素オン／オフ信号を供給する第１比較器と、
前記現在の画素の濃淡を表現する前記輝度値を量子化することにより、１からqの範囲で量子化された画素値pを生成する多重しきい値処理装置と、
１からqの範囲で複数の量子化値を格納しており、前記量子化された画素値pにより制御された、アクティブ量子化値としてp個の量子化値を出力するとともに、フレーム信号に応じて、有している前記量子化値をシフトさせる量子化テーブルと、
量子化されたディザ行列のしきい値を前記アクティブ量子化値と比較して、アクティブ量子化しきい値信号を生成する第２比較器と、
前記画素オン／オフ信号及び前記アクティブ量子化しきい値信号に応じて、画素出力信号を生成する画素出力生成器と、
前記画素出力生成器から出力される前記画素出力信号に応じて、q個のフレームからなる表示周期に前記現在の画素を、平均濃度値p/qで表示するための表示装置と、
を有することを特徴とする表示装置。
【請求項１０】
請求項９に記載の表示装置において、さらに複数のしきい値を格納するディザ行列を有することを特徴とする表示装置。
【請求項１１】
請求項１０に記載の表示装置において、前記現在の画素の座標に応じて、前記複数のしきい値を格納するディザ行列をアドレス指定して、それぞれのディザ行列しきい値を出力するカウンタを少なくとも１個さらに有することを特徴とする表示装置。
【請求項１２】
請求項１０に記載の表示装置において、前記それぞれのディザ行列しきい値を量子化して、１からqの範囲で量子化されたディザ行列しきい値を生成する多重しきい値処理装置をさらに有することを特徴とする表示装置。
【請求項１３】
請求項１０に記載の表示装置において、ディザ行列を生成するディザ行列生成器をさらに有しており、このディザ行列生成器は、
ディザ行列しきい値を含有し且つ繰り返しディザ行列の位置にしきい値を割り当てることにより画像の部分領域のそれぞれの部分領域画素と関連しているディザ行列位置からなるディザ行列を生成するディザ行列生成手段と、
複数の部分領域画素それぞれに関して、部分領域が割り当てられるしきい値に対応する一様な濃度階調値を示している場合に、ドットを受取る画素が、複数の部分領域画素の周辺でクラスタ（群れ）になっている相対的な詰り具合を決定する第１決定手段と、
前記第１決定手段により決定された詰り具合が最大である部分領域画素をそれぞれ識別する識別手段と、
前記識別手段により識別された複数の部分領域画素それぞれに関して、部分領域が割り当てられるしきい値に対応する一様な濃度階調値を示している場合に、
ドットを受け取るいくつかの部分領域画素を除き、割り当てられるしきい値に依存している階数域に存在する階数を割り当てられた部分領域画素が、複数の部分領域画素の周辺でクラスタ（群れ）になっている相対的詰り具合を決定する第２決定手段と、
前記第２決定手段により決定された詰り具合が最大である部分領域画素を少なくとも一つ選択する選択手段と、
前記選択手段により選択された部分領域画素に関連するディザ行列位置にしきい値を割り当てる手段と、
を有することを特徴とする表示装置。
【請求項１４】
請求項９に記載の表示装置において、前記表示装置は、液晶ディスプレイ（ＬＣＤ）であることを特徴とする表示装置。
【請求項１５】
現在の画素の濃淡を表現する輝度値を、それぞれのディザ行列しきい値と比較することにより、画素オン／オフ信号を供給する工程と、
前記現在の画素の濃淡を表現する前記輝度値を量子化して１からqの範囲で量子化された画素値ｐを生成する工程と、
量子化テーブルに１からqの範囲で複数の量子化値を格納する工程と、
前記量子化された画素値pにより制御された、アクティブ量子化値としてのp個の量子化値を前記量子化テーブルから出力する工程と、
フレーム信号に応じて、前記量子化テーブルの前記量子化値をシフトさせる工程と、
量子化されたディザ行列のしきい値を前記アクティブ量子化値と比較して、アクティブ量子化しきい値信号を生成する工程と、
前記画素オン／オフ信号及び前記アクティブ量子化しきい値信号に応じて、画素出力信号を生成する工程と、
前記画素出力信号に応じて、q個のフレームからなる表示周期に前記現在の画素を、平均濃度値p/qで表示装置に表示させる工程と、
を有することを特徴とする表示方法。
【請求項１６】
請求項１５に記載の表示方法において、さらにディザ行列に複数のしきい値を格納してなることを特徴とする表示方法。
【請求項１７】
請求項１６に記載の表示方法において、前記現在の画素の座標に応じて、前記ディザ行列をアドレス指定し、前記それぞれのディザ行列しきい値を出力する工程をさらに有することを特徴とする表示方法。
【請求項１８】
請求項１６に記載の表示方法において、前記それぞれのディザ行列しきい値を量子化して、１からqの範囲で量子化されたディザ行列しきい値を生成する工程をさらに有することを特徴とする表示方法。
【請求項１９】
請求項１６に記載の表示方法において、前記ディザ行列を生成するディザ行列生成の工程は、
ディザ行列しきい値を含有し、かつ繰り返しディザ行列の位置にしきい値を割り当てることにより、画像の部分領域のそれぞれの部分領域画素と関連しているディザ行列位置からなるディザ行列を生成するディザ行列生成工程と、
複数の部分領域画素それぞれに関して、部分領域が割り当てられるしきい値に対応する一様な濃度階調値を示している場合に、ドットを受取る画素が、複数の部分領域画素の周辺でクラスタ（群れ）になっている相対的な詰り具合を決定する第１決定工程と、
前記第１決定工程により決定された詰り具合が最大である部分領域画素それぞれを識別する識別工程と、
前記識別工程により識別された複数の部分領域画素それぞれに関して、部分領域が割り当てられるしきい値に対応する一様な濃度階調値を示している場合に、ドットを受取るいくつかの部分領域画素を除き、割り当てられるしきい値に依存している階数域に存在する階数を割り当てられた部分領域画素が、複数の部分領域画素の周辺でクラスタ（群れ）になっている相対的詰り具合を決定する第２決定工程と、
前記第２決定工程により決定された詰り具合が最大である部分領域画素を少なくとも一つ選択する選択工程と、
前記選択工程により選択された部分領域画素と関連しているディザ行列位置にしきい値を割り当てるしきい値割り当て工程と、
からなることを特徴とする表示方法。
【請求項２０】
請求項１６に記載の表示方法において、前記量子化テーブルがシフトレジスタからなることを特徴とする表示方法。
【請求項２１】
請求項２０に記載の表示方法において、前記量子化値を前記量子化テーブルで循環シフトさせてなることを特徴とする表示方法。
【請求項２２】
請求項２０に記載の表示方法において、前記量子化値を前記量子化テーブルに線形格納してなることを特徴とする表示方法。
【請求項２３】
請求項１５に記載の表示方法において、前記現在の画素を液晶ディスプレイ（LCD）に表示してなることを特徴とする表示方法。
【請求項２４】
機械で実行可能な命令プログラムを含んだ機械可読記録媒体であって、その命令プログラムは、
前記現在の画素の濃淡を表現する前記輝度値を量子化して１からqの範囲で量子化された画素値ｐを生成する手段と、
現在の画素の濃淡を表現する輝度値を、それぞれのディザ行列しきい値と比較することにより、画素オン／オフ信号を生成する手段と、
量子化テーブルに１からqの範囲で複数の量子化値を格納する手段と、
前記量子化された画素値pに従って前記量子化テーブルからp個の量子化値をアクティブ量子化値として出力する手段と、
フレーム信号に応じて、前記量子化テーブルの前記量子化値をシフトさせる手段と、
量子化されたディザ行列のしきい値を前記アクティブ量子化値と比較して、アクティブ量子化しきい値信号を生成する手段と、
前記画素オン／オフ信号及び前記アクティブ量子化しきい値信号に応じて、画素出力信号を生成する手段と、
前記画素出力信号に応じて、q個のフレームからなる表示周期に前記現在の画素を、平均濃度値p/qで表示装置に表示させる手段と、
を有することを特徴とする機械可読記録媒体。
【請求項２５】
請求項２４に記載の機械可読記録媒体において、さらにディザ行列に複数のしきい値を格納してなることを特徴とする機械可読記録媒体。
【請求項２６】
請求項２５に記載の機械可読記録媒体において、前記現在の画素の座標に応じて、前記ディザ行列をアドレス指定し、前記それぞれのディザ行列しきい値を出力してなる手段をさらに有することを特徴とする機械可読記録媒体。
【請求項２７】
請求項２５に記載の機械可読記録媒体において、前記それぞれのディザ行列しきい値を量子化して、１からqの範囲で量子化されたディザ行列しきい値を生成する手段をさらに有することを特徴とする機械可読記録媒体。
【請求項２８】
請求項２５に記載の機械可読記録媒体において、前記ディザ行列を生成する手段は、
ディザ行列しきい値を含有し、かつ繰り返しディザ行列の位置にしきい値を割り当てることにより、画像の部分領域のそれぞれの部分領域画素と関連しているディザ行列位置からなるディザ行列生成するディザ行列生成手段と、
複数の部分領域画素それぞれに関して、部分領域が割り当てられるしきい値に対応する一様な濃度階調値を示している場合に、ドットを受取る画素が、複数の部分領域画素の周辺でクラスタ（群れ）になっている相対的な詰り具合を決定する第１決定手段と、
前記第１決定手段により決定された詰り具合が最大である部分領域画素れぞれを識別する識別手段と、
前記識別手段により識別された複数の部分領域画素それぞれに関して、部分領域が割り当てられるしきい値に対応する一様な濃度階調値を示している場合に、ドットを受取るいくつかの部分領域画素を除き、割り当てられるしきい値に依存している階数域に存在する階数を割り当てられた部分領域画素が、複数の部分領域画素の周辺でクラスタ（群れ）になっている相対的詰り具合を決定する第２決定手段と、
前記第２決定手段により決定された詰り具合が最大である部分領域画素を少なくとも一つ選択する選択手段と、
前記選択手段により選択された部分領域画素と関連しているディザ行列位置にしきい値を割り当てるしきい値割り当て手段と、
を有してなることを特徴とする機械可読記録媒体。
【請求項２９】
請求項２４に記載の機械可読記録媒体において、前記量子化テーブルがシフトレジスタからなることを特徴とする機械可読記録媒体。
【請求項３０】
請求項２９に記載の機械可読記録媒体において、前記量子化テーブルに前記量子化値を循環シフトさせてなる手段をさらに有することを特徴とする機械可読記録媒体。
【請求項３１】
請求項２９に記載の機械可読記録媒体において、前記量子化テーブルに前記量子化値を線形格納させる手段をさらに有することを特徴とする機械可読記録媒体。
【請求項３２】
請求項２４に記載の機械可読記録媒体において、液晶ディスプレイ（LCD）に前記現在の画素を格納させる手段をさらに有することを特徴とする機械可読記録媒体。
【請求項３３】
M個のレベルの濃淡描画能力を有する表示装置に対して、画素につきN個のビットで表現される使用可能な濃淡数を有する原画像を表示する表示システムであって、それにおいてMは２N未満であり、
前記原画像を提供する入力装置と、
表示サイクルにつきq個のフレームのフレームレートを有する表示装置と、
前記原画像の現在の画素の濃淡を表現する輝度値を、それぞれのディザ行列しきい値と比較することにより、画素オン／オフ信号を提供する第１比較器と、
前記現在の画素の濃淡を表現する前記輝度値を量子化して１からqの範囲で量子化された画素値ｐを生成する多重しきい値処理装置と、
１からqの範囲で複数の量子化値を格納しており、前記量子化された画素値pにより制御された、アクティブ量子化値としてのp個の量子化値を出力するとともに、フレーム信号に応じて、有している前記量子化値をシフトさせる量子化テーブルと、
量子化されたディザ行列のしきい値を前記アクティブ量子化値と比較して、アクティブ量子化しきい値信号を生成する第２比較器と、
前記画素オン／オフ信号及び前記アクティブ量子化しきい値信号に応じて、画素出力信号を生成する画素出力生成器と、
前記画素出力生成器から出力される前記画素出力信号に応じて、q個のフレームからなる表示周期に前記現在の画素を、平均濃度値p/qで表示するための表示装置と、
を有することを特徴とする表示システム。
【請求項３４】
請求項３３に記載の表示システムにおいて、前記入力装置がスキャナ、パーソナルコンピュータ、ディジタルカメラまたは記録媒体であることを特徴とする表示システム。
【請求項３５】
請求項３３に記載の表示システムにおいて、前記表示装置がパーソナルコンピュータ、プロジェクタまたは液晶ディスプレイ（LCD）であることを特徴とする表示システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般的には、表示装置駆動用回路及び表示装置に関し、より具体的には画素ごとに２つの状態（オンとオフ）だけを、もしくは限定数の離散的状態を選択可能な表示装置駆動用回路及び表示装置に関する。さらに詳しく言えば、本発明は液晶ディスプレイといった表示装置の濃淡の描画能力を拡張する方法並びに装置に関する。
【０００２】
【従来の技術】
様々な画像表示用の装置があり、その表示能力は大幅に異なる。例えば、CRTディスプレイでは光が３原色、即ち、赤・緑・青（RGB）の発光体によって作られ、CRTの電子ビームで個別に励起される。強度が様々に変化する電子ビームを隣接する赤、緑、青の発光体（画素を形成する）のそれぞれに印加することによって、広域なカラー並びに輝度レベルを生成することができる。カラー画像は画素の配列として表されることが多く、各画素の値は２４ビットの語で表される。言い換えれば、カラー成分あたり８ビット構成の１バイトで表現される。画素ごとにカラー成分はそれぞれ０から２５５の範囲の輝度値で表現することができる。CRTに表示するためのカラー画像（例えば、コンピュータ生成の）はこの域もしくは範囲内の多数の色を含んでいることがある。
【０００３】
CRTに比べ、液晶ディスプレイ（LCD）は精度がはるかに低く、しかも２値（オン／オフ）に限定され、画素につき１ビット或いは多くても画素につき４ビットまでである。LCDで生成できるカラー数或いは濃淡数は８ビットの画素精度で表せる場合よりはるかに少ない。LCDは概して２枚の基板の隙間を埋めている液晶物質から形成されたフラットパネルからなる。画像は、外部信号により液晶物質の配向を制御して変調し、光がパネルを通るようにするか或いは遮断するかによって、表示される。個々の画素はマトリックス又はアレイ状に配列され、複数の走査電極及びデータ電極で駆動される。一般に、各画素は制御されて完全にオンになるか又は完全にオフになるか（２値）である。デバイスによっては、完全なオンと完全なオフの間のセル増分電圧を印加することによって、中間の濃度を描写することができる。しかしながら、そうした中間電圧レベルの生成及び維持には実用面で限定がある。個々の画素電極に対してレジストレーションされたカラーフィルタのモザイクを用いて、或いはダイクロイックミラーのような光学素子で赤・緑・青の成分に分離される白色光を用いて、カラー画像をLCDディスプレイで生成することができる。その際、赤・緑・青の成分はLCDパネルで変調される。
【０００４】
LCDデバイスで画像を比較的高精度（例えば、画素あたり８ビット）で忠実に描写しようとすれば、視覚的に認識可能な濃度階調輝度レベル数を増やさなければならない。一つの手法はフレームレートサイクリング又はフレームレート変調で、その際画素は複数のフレームリフレッシュでオンとオフ交互に駆動されてパターンサイクル中平均輝度の視覚的効果を生じる。例えば、画素が３フレームリフレッシュサイクル中オンになり、２フレームリフレッシュではオフとなれば、そのリフレッシュサイクルの濃度階調輝度は３/５のように見える。この手法には知覚フリッカー（画像が急速にオン・オフしているように見える）或いはスイム（画像を通り抜ける人工的パターンが画像にあるように見える）といった欠点がある。
【０００５】
これらの視覚的欠点を減らそうとする様々な試みがなされてきた。例えば、Scheffer et al.に付与された米国特許番号５,６４２,１３３は、表示コラム駆動信号の振幅又はパルスの高さを変調することによりLCDで多数の濃度を実現している。しかしながら、そうしたシステムにはマルチレベルドライバが必要である。Singhal et al.に付与された米国特許５,３１３,２２４は、画素を変調する位相を時間と表示の水平軸及び垂直軸に広げることによりフリッカーを減らすようにしている。Akodesの米国特許４,９２１,３３４は、マルチレベルドライバと連続フレーム間の時分割多重化との組み合わせを用いる一例である。Garrettの米国特許５,６０８,６４９は、オンとオフの状態間のサイクルに認識不能なパターンを用いてフリッカーを減らすようにしている。Liuの米国特許５,３８９,９４８は、オリジナル画像において対応する画素の濃度値、フレーム番号、ディザ行列における要素の値とに従って各画素の照度を変える。これらの先行技術による方法はフリッカー又は可視のアーティファクトを減らすのには役に立つかもしれないが、一様なドットパターン又は多数の濃淡を提供する能力には限界がある。
【０００６】
【発明が解決しようとする課題】
従って、精度に限界のある表示装置で濃淡を描画できるように従来のシステムの欠点を克服するのが本発明の目的である。
【０００７】
特に、本発明の目的は、液晶表示（LCD）装置で画像を表示できるように改善されたシステムを提供することである。
【０００８】
本発明のもう一つの目的は、LCDデバイスをフレームレート変調してフリッカーや可視アーティファクトを減らす改善されたシステムを提供することである。
【０００９】
本発明の更なる目的は、２値の表示装置で描写できる濃淡の数を増やすことである。
【００１０】
本発明のまた更なる目的は、フレームレート変調画像の各フレームで一様なドットパターンを実現することである。
【００１１】
【課題を解決するための手段】
本発明は、分散型ディザ行列を用いて非常に一様なドットパターンを生成する。この行列は周波数変調又は分散型ドットスクリーニング手法を用いて生成される。典型的な１６ x １６の分散型ディザ行列を図３に示す。
【００１２】
p/qの濃淡を生成するために、表示周期あたりのフレーム数又はフレームリフレッシュ数に従って１からqのレベルの線形量子化テーブルを先ず作成する。時間t(１)で、量子化テーブルの最初のp個のエントリが選択され起動される。後続の各時間t(２)、t(３)、t(４)、・・・、t(q)で、量子化テーブルの内容が循環シフトされ、シフト後の量子化テーブルの最初のp個のエントリが選択される。例えば、３/５の濃淡を生成するには、図５に示すような量子化テーブルが作成される。各フレームで、テーブルの最初の３エントリがアクティブである。時間の経過と共に、これら最初の３エントリにおける量子化レベルは図５に示すように変化する。５個のフレームのアクティブレベルは、(１,２,３)、(４,５,１)、(２,３,４)、(５,１,２)、そして(３,４,５)のシーケンスになる。この方法を用いると、どのフレーム周期にも３つのレベルがアクティブになるが、選択して起動される特定のレベルはフレームからフレームで異なる。
【００１３】
アクティブ量子化レベルは、図３に示すような分散型ディザ行列で写像され、対応するパターンシーケンスが生成される。そのパターンシーケンスはLCDパネルに表示され、いろいろ異なる濃淡が描画される。ディザ行列（例えば、図３）は行列の各エントリの階数に基づいてqのレベル（例えば、５）に量子化される。この結果が図４に示す量子化された行列である。画素は、その対応する量子化レベルがアクティブか否かにより、オンかオフのいずれかになる。３/５の濃淡の例において、行列は各要素の階数に従って、５つの異なるレベルに量子化される。図５に示すようなシーケンスで５つのフレームでアクティブレベルが生成される。シフトされたバージョンのアクティブレベルは量子化された行列で写像され、その結果、対応するパターンシーケンスが生じる。ドットの分布を最大限一様にする図３の行列が選択されているので、生成されるパターンはどのフレームにおいても一様性を有することになる。
【００１４】
添付の図面と共に以下の説明並びに請求の範囲を読むことにより、本発明を一層深く理解すると共に本発明の他の目的並びに達成したことをはっきり認識できるようになるであろう。
【００１５】
【発明の実施の形態】
図１A、１B及び１Cに、本発明の環境の大まかなブロック図を示す。原画像Sは、例えば、グラフィックス生成機能を有するパソコン、ディジタルカメラ、スキャナなど、画像生成装置又は入力デバイス１０から出力される。その原画像は静止画像でも、又はビデオソースからの動画でも構わない。原画像は、画像処理装置１２によって処理され、LCD表示装置１４に送られ表示される。LCD表示装置１４は、例えば、コンピュータ用のパネルディスプレイでも、或いはプロジェクタでもいい。
【００１６】
画像処理装置１２は、個別部品を有するハードウェアでも、ソフトウェア、ファームウェア、又は特定用途向け集積回路（ASIC）でも、或いはこれらの組み合わせでもいい。また、画像処理装置の機能ブロックは本明細書ではあくまでも説明の便宜上分かれている。これらのブロックの機能上及び物理的な境界はデバイスにより異なるであろう。例えば、図１Bに示すのは、LCD表示装置１４と物理的に一体化された画像処理装置である。その画像処理装置は部分によってLCD表示装置よりも入力装置と機能的にもっと関係しているかもしれないし、或いはその逆かもしれない。図１Cは、パーソナルコンピュータ（PC）１８の一部として形成された画像処理装置を有する実施例で、PC １８は画像処理装置１２、LCD表示装置１４、プリンタ２６の他、スキャナ１６やディジタルカメラ２８といった入力デバイスの動作を制御すると共にそれらの間の通信を制御し、さらにI/Oデバイス２４のような周辺機器を制御すると共にそうした機器との通信を制御する。その際、各々は直接或いは間接にPC バス３０に接続される。この実施例において、原画像はI/Oデバイス２４に先に格納され（しかも恐らく処理されて強調されている）てI/Oインタフェース２０でPCにロードされるようにしてもいいし、或いはディジタルカメラ２８のようなディジタル画像入力デバイスで取り込むようにすることもできる。さらに、画像処理装置１２を、ソフトウェアの形で、外部記憶装置、すなわち、I/Oデバイス２４からPCのメモリにロードするようにしてもいい。或いは、画像処理装置を、ハードウェア、ASIC、ファームウェアなどの形で、又はこれらの組み合わせで、PCのカードスロットに挿入できるオプションカード２２に実現することもできる。
【００１７】
本発明はこれらの基本的な構成要素を有するそうしたデバイスならどれにでも応用することができるが、例証の目的で、図２A及び２Bに示すLCD表示装置１４のような或る特定の画像処理装置の環境において本発明を説明する。図２Aに示した典型的なシステムにおいて、中央演算処理装置（CPU）３６は、画像処理やその他のシステム動作を制御するように、バス４０を介してグラフィックスコントローラ３８に結合されている。ここで、CPU ３６はPC １８の一部であってもいい。また、バス４０はPCパス３０の一部であっても、或いはPCバス３０とは別の独立したものであってもいい。グラフィックスコントローラ３８は、画像データを検索できるようにバス４４を介してビデオメモリ４２に結合されると共に、画像データを供給できるようにバス４６を介してLCD表示装置１４に結合されている。グラフィックスコントローラ３８は、データ信号（Px,y）、走査線クロック信号、フレーム信号及び画素クロック信号をバス４６で送りLCDデバイス１４を動作させる。ディザ行列生成器７８もバス４０に接続された状態で示されている。ディザ行列生成器について以下に説明する。ディザ行列生成器７８は、説明の目的で、別個の機能ブロックとして示したが、画像処理装置１４の一部となっていても（図１A、１B、１C）構わないし、個別部品を有するハードウェア、又はソフトウェア、ファームウェア、特定用途向け集積回路（ASIC）、或いはこれらの組み合わせで実現するようにしてもいい。
【００１８】
原画像Sは、画像生成機能を備えたパーソナルコンピュータ、スキャナ、ディジタルカメラなど様々な入力デバイスから送られてくる。画像は、文書、写真、或いはテキストとグラフィックス画像の混合を、例えば、ビットマップ形式又はビットマップの組み合わせでディジタル表現したもので、ビデオメモリ４２に格納されている。ビデオメモリ４２は、適したメモリならどれでも構わないし、或いはメモリ、例えば、ランダムアクセスメモリ（RAM）の割り当て領域であっても構わない。この格納された電子画像は、ピクセル（ピクセルは画素の略語）又はペル（ペルはプリントエレメントの略語）と呼ばれる多数の離散的な標本からなる。各画素はその位置（例えば、xy座標）と輝度とで定義される。普通、画像をコンピュータに格納するのに用いられる精度は画素につき８ビットで、２５６の濃度値が可能である。ここでは説明のため、入力原画像Sの解像度とLCDディスプレイの解像度は同じであると仮定する。しかしながら、ほとんどの場合、原画像は様々なフィルタリング技法を用いてダウンサンプリング又はアップサンプリングされてLCDの解像度にマッチするようになる。
【００１９】
画素クロック信号は現在の画素のx座標を記録し、走査線クロック信号は現在の画素のy座標を記録し、現在の画素の値（輝度）が画素データ信号Px,yで伝えられる。フレーム信号又は垂直方向ブランキング信号を用いて１表示時間周期内に表示フレームごとのカウントを記録する。LCDの表示画面は１表示時間周期内に何回もリフレッシュされて同じ画像データを描写する。グラフィックスコントローラはビデオメモリを動作させて新たな画像データを検索し新たな表示時間周期ごとに表示する。この伝統的な動作は、よく知られているように、フレームバッファ及び先入れ先出し（FIFO）バッファを用いて実行される。
【００２０】
画素クロック信号及び走査線クロック信号はディザ行列４８のアドレス指定にも用いられる。ディザ行列はディザ行列しきい値がN x Nの配列になったものである。画素の一つ一つが考えられる２５６の値の一つを有するオリジナル画像とは対照的に、典型的なLCDディスプレイはどんな画素でも完全にオンにするか或いは完全にオフ（濃度階調表示で）にするしかできないので、ディザ行列４８を用いる。LCDディスプレイによっては幾分より精細な値の量子化能力を有する場合があるが、そうした能力を有するディスプレイでも量子化はオリジナル画像より粗い場合がほとんどである。より精細な濃度階調の量子化になっているかのように見えるようにするために、ハーフトーン処理を用いる。それにおいては交互にオン画素・オフ画素にすることにより一様な濃度値領域で濃度値を達成するが、オン画素及びオフ画素それぞれの割合は達成しようとする濃度階調作用に依存する。言うまでもなく、対象となる画像はほとんどが画素値が一様でない領域を有するから、一つの画素とその次の画素では輝度値が違う画素をハーフトーン処理する方法があるはずである。そうした画像に対してハーフトーン処理を行なう比較的に高速な方法は「ディザリング」として知られている。
【００２１】
ディザリングには画素値をディザ行列のそれぞれのしきい値と比較することが必要である。例えば、ディザ行列のサイズが１６ x １６で、画像空間が６４０画素x ４８０行であると仮定しよう。ディザリング処理は、概念的にいえば、各画素がそれぞれのディザしきい値と関連し合うように、オリジナル画像の各部分領域の上にディザ行列を置くことである。所定の画素の画像値をそのように割り当てられたその画素のしきい値と比較すると、その画素がオンになるかオフになるかが決まる。或る所定の画素における画像値がその画素のディザしきい値を超えていれば、その画素はオンになる。そうでなければ、その画素はオフになる。画素ごとのディザ処理の出力はその画素がオンになるかオフになるかを示す２値である。ディザ行列の要素は、D(x,y) = D(i,j) for i = x mod N and j = y mod Nとなるように、モジュロカウンタ、すなわち、画素カウンタ５０及び走査線カウンタ５２でx-y画像座標空間に写像される。本発明はディザ行列生成器７８を用いてディザ行列４８の値を生成する新規の技法を活用する。それについては以下にもう少し詳しく説明するが、目下係属中の関連出願である１９９７年７月９日出願の出願番号０８/８９０,６１１で開示している。ついては０８/８９０,６１１出願を参照することにより本発明の一部をなすものとする。そうした新規の技法から生成された典型的な１６ x １６ディザ行列を図３に示す。そうしたディザ行列は表示画像で非常に一様な画素パターンになる。
【００２２】
現在の画素Px,y値（即ち、０ 〜 ２５５）は比較器５４で対応するディザ行列Di,jと比較され、２つの値Pdith = １又はPdith = ０の一つが生成される。例えば、現在の画素Px,yが濃度値１５０を有し、そのx-y座標に写像するディザ行列位置Di,jのしきい値が１２２であるとすれば、比較器５４は値Pdith = １を出力する。説明上、比較器５４の２つ別々の出力を示しているが、Pdith = １がハイ（アクティブ）、Pdith = ０をロー（インアクティブ）として単一出力Pdithを実現することができる。比較器５４の出力は画素出力生成器５６（図２B）に出力される。それについて以下に説明する。
【００２３】
表示画像の視覚作用を向上させるために、本発明ではフレームレート変調を用いてLCDディスプレイで表現される濃淡を拡大する。LCDがリフレッシュされるフレームレート又は頻度はデバイスからデバイスで異なる。フレーム変調システムにおいて、ディスプレイ上に画像を形成する画素は描写される濃度又は色の濃淡と相関していろいろなフレームでオン又はオフになる。本書の説明では、表示周期あたりのフレーム数をqで表す。一例として、表示は周期（q = ５）ごとに５回リフレッシュされ、表示領域は有効な濃淡３/５（例えば、１２１/１２５が表示可能な５つの濃度値に量子化されている）を有すると仮定しよう。対象領域にある全ての画素を単純に最初の３フレームでオン、次の２フレームでオフにするとしたら、フリッカーがはっきり目に見える。オン画素とオフ画素の比率を維持しながら時間をかけてオン画素とオフ画素のパターンを変化させるようにすると錯乱作用を減らすことができる。
【００２４】
図２Aを見ると、本発明におけるディザ行列のしきい値Di,jは、表示周期あたりのフレームレート又はフレーム数に従って値を量子化する多重しきい値処理装置５８にも入力される。例えば、フレーム周期あたり５つのフレームがある（q = ５）とすれば、しきい値は値１、２、３、４又は５に量子化される。図４に示すのは、図３に例証したディザ行列を５つのレベルに量子化した量子化表現である。多重しきい値処理装置５８の出力は量子化されたディザ行列値DijQである。この値はアクティブレベル比較器６０（図２B）に入力され、そこで量子化ディザ行列値DijQを量子化テーブル６２のアクティブエントリに対して比較する。
【００２５】
量子化テーブル６２は、図２Bに示すように、線形多重出力循環シフトのレジスタとして構成される。量子化テーブル６２のエントリ数は表示周期のフレーム数（q）によって決まる。例えば、周期につき５フレームあるとすれば、テーブル６２は１、２、３、４、５の値を有する５つのエントリで構成される。フレームリフレッシュごとの出力数は描写される量子化画素値（p）によって決まる。p/qの濃淡を生成するために、線形量子化テーブル６２は周期あたりのフレーム数の値qに従って１からqまでのレベルを有するq個のエントリで構成される。時間t(１)で、量子化テーブルにおける最初のp個のエントリが出力#線の量子化画素値pに従って選択され起動される。これらのエントリは出力線６４でアクティブレベル比較器６０に出力される。後続の各時間t(２)、t(３)・・・t(q)で、シフト線上でフレーム信号が起動された後、量子化テーブルの内容が、例えば、２位置だけ循環シフトされ、シフト後の量子化テーブルの最初のp個のエントリが選択され線６４で出力される。例えば、３/５の濃淡を生成するには、図５に示したような量子化テーブルが生成される。各時間周期で、テーブルの最初の３エントリがアクティブレベルとして出力される。時間が経過するにつれて、これら最初の３つのエントリの量子化レベルが変わる。図５に示すように、５つのフレームのアクティブレベルはシーケンス（１,２,３）、（４,５,１）、（２,３,４）、（５,１,２）、そして（３,４,５）になる。この構成にすると、３つのレベルがどのフレーム周期においてもアクティブになるが、起動のために選択された特定レベルはフレームからフレームで異なる。
【００２６】
描写される濃淡p/qは現在の画素値Px,yとフレームレートによって決まる。図２Aに示すように、現在の画素値Px,yは多重しきい値処理装置５８に入力され、そこで現在の画素値を量子化する。周期あたり５フレームの前述の例では、多重しきい値処理装置５８は現在の画素値を量子化して量子化画素値pの１、２、３、４又は５に量子化する。それに対応する濃淡はそれぞれ１/５、２/５、３/５、４/５、５/５である。
【００２７】
図２Bに示すように、線形量子化テーブル６２の出力線６４のアクティブレベルはアクティブレベル比較器６０に入力される。既に説明したように、量子化ディザ行列値DijQもアクティブレベル比較器６０に入力される。アクティブレベル比較器６０は各アクティブレベルを現在の量子化ディザ行列値DijQと比較し、現在の画素Px,yに対応するディザ行列値がアクティブレベルか又はインアクティブレベルかを決定する。例えば、現在の画素Px,yが或る濃度値を有し且つそのx-y座標に写像するディザ行列位置Di,jの値が１２０であるとすれば、その量子化ディザ行列値DijQは３になる（図３と図４を比較せよ）。さらに、図５に示した例を用いると、表示周期が第１フレームt(１)にある場合、アクティブレベル比較器６０は現在の量子化ディザ行列値３を現在のアクティブレベル値１、２、３と比較して、一致を見つける。比較器６０は次にアクティブレベル信号Latv = １を出力して、現在の画素に対応する量子化ディザ行列しきい値が現在のフレームのアクティブレベルの一つと一致することを示す。再び図５に示した例を用いると、表示周期が第２フレームt(２)にあると、アクティブレベル比較器６０は現在の量子化ディザ行列値３を現在のアクティブレベル値４、５、１と比較し、一致するものがない。比較器６０は次にアクティブレベル信号Latv = ０を出力して、現在の画素に対応する量子化ディザ行列しきい値が現在のフレームのアクティブレベルのどれとも一致しないことを示す。説明のために、比較器６０の２つ別々の出力を示しているが、Latv = １がハイ（アクティブ）、Latv = ０をロー（インアクティブ）として単一出力Latvを実現することもできる。比較器６０の出力は画素出力生成器５６に入力される。
【００２８】
画素出力生成器５６は比較器５４からディザ画素値Pdithを受け取り、比較器６０からレベルアクティブ値Latvを受取る。画素出力生成器は２つのゲート論理演算子として描いてある。論理ANDゲート５６Aは、ディザ画素値Pdithとレベルのアクティブ値Latvが共に１（又はハイすなわちアクティブ）ならば、信号Pout = １を生成する。言い換えれば、現在の画素値がそれに対応するディザ行列しきい値を超え且つ量子化ディザ行列値が現在のフレームの量子化テーブルのアクティブ値の一つであれば、Pout = １が生成される。論理ORゲート５６Bは、ディザ画素値Pdith又はレベルアクティブ値Latvのいずれかが０（又はローすなわちインアクティブ）ならば、信号Pout = ０を生成する。言い換えれば、現在の画素値がそれに対応するディザ行列しきい値を超えていないか或いは量子化ディザ行列値が現在のフレームの量子化テーブルのアクティブ値の一つではない場合には、Pout = ０が生成される。画素出力生成器５６は、説明の目的上、２つのゲート及び２つの出力として表示してあるが、入力Pdith及びLatvと単一出力Poutを有し入力が共にアクティブ（又は１すなわちハイ）の時だけアクティブ（又は１すなわちハイ）になる単一ANDゲートとして実現することができる。Pout信号は、現在の画素のデータ値（オン／オフすなわち１/０）を表し、LCDパネル６４に入力される。
【００２９】
LCDパネル６４は伝統的な方法で動作し、例えば、水平方向及び垂直方向のシフトレジスタ６６及び６８、画素ドライバ７０及びラインドライバ７２、画素データラッチ７４、LCDディスプレイ７６を備えているかもしれない。画素クロック信号に基づき、水平方向シフトレジスタ６６は選択可能画素ラッチ７４をイネーブルにし入ってくる画素データを格納する。ラッチ７４は取り込んだ一行の画素データを画素ドライバで渡し、ディスプレイ７６に一行を形成する。走査線クロック信号に基づき、垂直方向シフトレジスタ６８はディスプレイ７６のどの行が画素データの一行を受取るかを決定する。連続する各走査線クロック信号によって、垂直シフトレジスタ６８はその前の行をディスエーブルにし、連続ラインドライバ７２を用いてディスプレイ７６の連続する各行をイネーブルにして次の行の画素データを受取る。画像情報のフレームごとにこのプロセスが繰り返される。
【００３０】
本発明の上述の態様から、LCDディスプレイにどんな数の濃淡でも描写できるような構成にすることができ、特定ディスプレイのフレームレートにだけ限定される柔軟性のあるデバイスが生まれる。レベルをシフトした後の量子化テーブルによってフレームからフレームへの遷移が保証され、目に見えるようなフリッカー又はスイムが生じない。ディザ行列を本発明のように用いると、フレームからフレームで一様なドットパターンになる。
【００３１】
以下に、ディザ行列生成演算について説明するが、これについては１９９７年７月９日出願の米国出願番号０８/８９０,６１１により詳細に記載されている。その出願を参照することにより本願明細書の一部をなすものとする。
【００３２】
図６から図１１にディザ行列生成器７８の動作を例証する。説明上、単独の機能ブロックとして表示してあるが、ディザ行列生成器７８は、処理装置１４（図１A、１B、１C）又はPC １８の一部をなすようにしてもいいし、或いは個別部品からなるハードウェアに、或いはソフトウェア、ファームウェア、特定用途向け集積回路（ASIC）、又はこれらの組み合わせで実施することもできる。画素あたり８ビットのディジタル画像の場合を考えてみよう。画素は、完璧に白すなわち完全に「オン」の２５５（=２8-１）と、完璧に黒すなわち完全に「オフ」の０との間で、どんな濃度値でも有することができる。イメージング装置が、イメージング因子（プリンタの場合はインク）の付着量が増えるとその結果画像輝度が低下するプリンタのようなデバイスの場合、画像データは画像表示処理期間中に補数値に普通変換される。これ以降の説明は、そうした補色値に換算して、言い換えれば、値が大きくなるほどに画像は暗くなる、さらに「オン」画素と「オフ」画素ではなく「インクドット」によって説明するが、この原理はLCDディスプレイ又は陰極線管の場合のようなポジティブカラー又は濃淡の表示にも同じく当てはまる。
【００３３】
より具体的に説明するために、行列は８ビットの入力値と１ビットの出力値を有するディザ演算用であると仮定することにするので、画素ごとに２５６の入力画素値が考えられる。いろいろ異なるしきい値の数は、従って、一つ少ない、すなわち、２５５のはずである。行列のサイズが１２８ x １２８であるとすれば、各しきい値は６４又は６５いずれかのディザ行列位置（１９１値 x ６４位置／値 + ６５値 x ６４位置／値 ＝１２８ x １２８位置）にある。
【００３４】
さて、ディザ行列値を割り当てる一般的な手法は、初期ライトグレー値をともかく任意に選び、その初期濃度値を一様に表示する部分領域に用いられるべき（まばらな）初期のドットパターンを選択することから始まる。様々な手法を用いてその初期ドットパターンを得ることができる。例えば、一様に初期濃度値からなる画像に「誤差拡散」を用いることにより生成された出力のディザ行列サイズの部分領域から得ることができる。誤差拡散はよく知られたハーフトーン処理法で、画素の一つでハーフトーン処理を行なうことから生じる量子化誤差を隣接している画素に「拡散」する方法である。誤差拡散はディザリングと比べて総体的な誤差を最小限に抑える傾向があるけれども、計算集約型だから、ディザリングの方が好ましい場合が多い。
【００３５】
図６のブロック８２は誤差拡散のプロセスを表す。図６に表すシーケンスの目的は、サイズが生成されるディザ行列のサイズと同じで、しかも要素が、対応する部分領域が開始値に等しい一様な濃度値を表示しているとその部分領域の画素がインクドットを受取るかどうかを示す、２値の行列を生成することである。言い換えれば、「１」を含有する２値行列の位置は、全ての入力画素値が開始値に等しいと、インクドットを受取るべき部分領域の画素に対応し、「０」を含有する２値行列の位置はその他の部分領域の画素に対応する。初期濃度階調値が、例えば、０（白）から２２５（黒）のスケールで１０（ライトグレー）であるとしよう。それは、理論的にはインクが部分領域画素６４２ヶ所、すなわち、１２８ x １２８の部分領域画素の１０/２５５に付着されるはずだから、誤差拡散出力には理論上それほどたくさんの論理の「１」があるはずである。
【００３６】
実際には、「１」の数は６４２にも満たないことがあるので、ブロック８４に示すように点を付加しなければならないことがある。ドットを付け加えるために選ばれた行列位置は「ヴォロノイ頂点」を含有する画素に対応する候補の中から選択される。図８に関して以下に説明するように、ヴォロノイ頂点は、ドットを含有する少なくとも３つの画素の中心から最も近い等距離にある点だから、その最大の空所、すなわち白い空間がそうした点を含有することになる。これらの点のどれが最大の空所の中に位置するかは、候補位置のコンボリューション核の中心点を決定し、未だドットを含有していない画素に対応する核係数の和をとることにより得られる得点を候補の各位置に割り当てることにより、決定される。他の核を用いることもできるけれども、１.５画素幅の標準偏差値を有する１１ x １１のガウス核がこの目的に適している。本方法の後続フェーズに関して空所の大きさやクラスタ（群れ）の詰まり具合の様々な他の測定基準について説明する。
【００３７】
ドット数の調整が不要な場合でも、誤差拡散処理はドットの配置で異質性が残ることがあるので、最も詰まっているクラスタ（群れ）から「１」を取り去り最大の空所が生じるようになるまで、最も詰まっているクラスタ（群れ）から最大の空所に「１」を移動することにより等質化処理８６を行なう。
【００３８】
インクドットを受け取り初期の濃度階調レベルを生成すべき部分領域の画素を既に識別しているので、そのように配置されるインクドットとなるディザ行列しきい値を割り当てるタスクについて説明する。複数のフェーズでしきい値を割り当てる。「１」を含有している初期の２値行列に対応するディザマトリクス位置にあるしきい値は全て１０未満であるはずで、そのしきい値はそれ以外全ての位置では１０以上のはずである。しきい値割り当てタスクの第１フェーズは１０未満のしきい値全ての位置を確定することである。
【００３９】
図７にこのフェーズを示す。このフェーズでは、２値行列の最も込み合っている位置から「１」を反復して取り除く、すなわち、概念的に言えば前のインクドット除去後に最も込み合っている残りのインクドット位置からインクドット一つを取り除く。充分に「１」が取り除かれ、濃度値９にするのに必要なインクドット数まで残り数が減ると、そのプロセスで「１」が取り除かれた２値行列位置に対応する全てのディザ行列位置がしきい値９を受取る。言い換えれば、濃度値が１０の時これらの位置でインクドットの付着が許可され、濃度値が９の時は許可されない。このようにして「１」を取り除き続けることにより、８から０までのしきい値を受取るべき位置を同じように識別することができる。
【００４０】
図７に、実効しきい値を参照しない演算のこのフェーズを示す。実効しきい値は量子化レベル数及びディザ行列のサイズに依存する（例では、２8=２５６及び１２８x１２８）。図７では、代わって、もっと一般的な表現で、各位置に階数を割り当てることとして説明しており、階数は、部分領域画素数が許す限り増分的に部分領域が暗くなるとすれば、対応する部分領域画素がインクドットを受取るシーケンスにおけるそれらの画素の順番を示す。言い換えれば、入力量子化レベル数（この例では２8）がディザ行列位置数（この例では１２８x１２８）より一つ多ければ、階数としきい値は同じであり、従ってしきい値数に等しい。そうでなければ、しきい値は次のような関係を用いることにより階数から容易に得ることができる。
【００４１】
0003982099.tif 000002
【００４２】
上の式において、Tはしきい値、trunc(χ)はχより大きくない最大整数、Rは階数、NTはしきい値数（この例では２8-１=２５５）で、NLはディザ行列位置数である。階数値を明白に割り当てて格納すると、同じ割り当て演算をいろいろ程度の異なる量子化に用いることができるようになるから、最初に階数値を計算することによって割り当てる方が好ましいと考える。言い換えれば、一旦階数Rを決定したら、Tに上記の式を用いる以外他に何も処理を行なわなくてもいろいろ異なるNT/NLの値に対していろいろ異なるディザ行列を生成することができる。とはいえ、上記の式が示すように、ディザ行列位置に階数を割り当てることは本発明の目的からすればしきい値を割り当てることと同じことだから、この２つの概念は互いに同じ意味で用いている。
【００４３】
この例で「１」が一つ捨てられた第１の２値行列位置に対応するディザ行列位置の階数は、部分領域が増分的に暗くなっていくとしたらインクドットを受取る最初の６４２ヶ所のうち最後の位置だから、６４１である。図７のブロック８８は従って階数値の初期化を表す。図７に表す手続きは繰り返され、最初に選ばれた位置の階数は全てブロック９０に表す工程で決定される通りに割り当てられるまで次第に階数値が低下していく。
【００４４】
最も込み合っている部分領域画素に対応する位置を識別する別々の方法を２つ用いる。２値行列における「１」の数が、すなわち、概念上ディザ行列がカバーする部分領域に残っているインクドット数が、しきい値「０」を受取るべき位置数に達すると、ブロック９２に示す工程で決定される通り、候補のコンボリューション核の中心点を決定し、ドットが残存する画素に対応する核係数の和をとることにより込み合い具合を査定する。前と同じく、標準偏差値１.５を有する２次元のガウス関数に値が比例する１１ x １１の核を用いる。ブロック９４は査定された込み合い具合に基づき位置の中から選択することを表している。
【００４５】
しかしながら、残存するドット数が０しきい値レベルになる前に、最も込み合っている画素はヴェルノイ分割により識別されるが、それをブロック９６に示す。図８を参照するとヴェルノイ分割を理解することができる。
【００４６】
図８は、例証の目的で、サイズが１０ x １０のディザ行列で定義された部分領域９８を描いている。言い換えれば、先に言及した例の１２８ x １２８のディザ行列よりはるかに小さい。２値行列は、部分領域９８が図７のルーチンが向かっているライトグレー値の一つを表示しようとしているとどの画素がインクドットを受取るかを指定するが、ここでは画素１００、１０２、１０４、１０６、１０８、１１０だけがインクドットを受取ると指定していると仮定しよう。ヴェルノイ分割は、このようにして選択された画素のそれぞれに対して、選択されたが未だインクドットを受取っていない他の画素の中心からその画素の中心までとを比べ同じかもしくはより近い距離にある全ての点からなる分割を、関連させる。（多角形）分割の頂点を決定し、面積決定計算用にこれらの頂点の順番を決める手続きはよく知られており、例えば、ニュージャージー州Englewood Cliffs所在のPrentice-Hall社１９９４年発行のK. Mulmuley著Computational Geometry, An Introduction Through Randomized Algorithmsに記載されている。
【００４７】
分割を実行する際、ディザ行列は画像に「タイル」を張ることであることを忘れないようにしなければならない。一様な濃淡画像において、隣接している部分領域の画素１１２及び１１４は対応する画素１００及び１０２がインクドットを受取るといつでもインクドットを受取るので、結果として生じる分割は図８に破線で示す通りである。特に、画素１００の分割は面積１１６も含む。なぜならば、面積１１６が含有する点は画素１０８及び１１０に対するよりも対応する画素１１２に対して接近しているからである。これの一つの見方は、部分領域を可撓性を有するシートと考え、その上辺を底辺にくっ付けることによりそのシートからチューブを形成し、２つの端部を接続して輪環面を形成し、その結果として生じた輪環面上の点と点の間の測地的距離を用いてヴェルノイ分割を決定することである。
【００４８】
分割を用いて、インクドットを受取る画素のどれがインクドットが最も込み合っている面積にあるかを決定する。最低面積のヴェルノイ分割と関連している画素を最もぎっしり詰まっているクラスタ（群れ）と関係していると考える。
【００４９】
そうした画素クラスタ（群れ）の一つだけが最もぎっしり詰まっている場合、対応するディザ行列位置は現在の階数が割り当てられる個所である。一つ以上の画素の分割が最低面積を有する場合、単にその最低分割面積画素の中から無作為に選択してインクドットが取り除かれる次の画素を選択することができる。しかしながら、画素選択用に更なる判定基準を適用すると、視覚的妨害となるアーティファクトを抑制する傾向があることを発見している。
【００５０】
図７の工程１１８で用いるクラスタ（群れ）の詰まり具合の測度は、候補ディザ行列位置に対応する候補画素がいかに込み合っているかを他のインクドット含有画素によって示すのに対し、ブロック１２０で用いるクラスタ（群れ）の詰まり具合の測度は候補位置がいかに込み合っているかを、その階数（先に決定した通り）が割り当てられる階数に近い位置によって示す。何をもって「近い」とするかは設計上の選択の問題である。例えば、設計によっては関連しているしきい値が同じかもしくは割り当てられているしきい値と１だけ異なる場合には階数を近いと考えるかもしれない。また、他の設計では、或る階数が、割り当てられる階数としきい値につき部分領域画素数（本書の例では６４又は６５）未満しか違わない場合、その階数を近いと考えるかもしれない。これを「距離判定基準」と呼んでいる。
【００５１】
ヴェルノイ分割によるクラスタ（群れ）の込み合い具合測度を用いてこの判定基準を適用し本発明の教えを実現することができるが、我々は別の測度を好む。ブロック１２０に示す工程で、近い階数を有する画素が或る所定の画素の周囲でクラスタ（群れ）になっている詰まり具合の測度は単にその所定の画素から近い階数を有する画素までの最低距離である。すなわち、工程１１８で同点になった候補位置の中から、そのように近い階数を有する位置が最も詰ったクラスタ（群れ）の中にあると考えられるのは、最も近くにある近い階数を有する位置までの距離が最低である候補である。すなわち、P = {pi; i = ０, ・・・, M-１}がM個のそのように近い階数を有する位置の集合で、X = {xi; j = ０, ・・・, N-１}が工程１１８を生き延びたN個の候補位置の集合であるとすれば、次の階数を有する位置の指数Jを下記の式から得ることができる。
【００５２】
【数１】
0003982099.tif 000003
【００５３】
この式において、D(x,y)は位置x及びyに対応する部分領域画素間の先に説明した輪環面上の測地的最低距離である。
【００５４】
この判定基準もまた同点になった場合には、ブロック１２１に示すように、その同点になっている位置にもう一つ別の判定基準を適用する。この判定基準では、部分領域行列全体がブロックに分割される。例えば、２値行列の大きさが１２８ x １２８とすれば、図９Aの部分領域を、破線で示すように、３２ x ３２のブロック１６個に分割する。図８に関して先に説明したと同様の理由で、１ブロックに属する位置は平面部分領域が変形して輪環面になると近接している画素に対応するから、部分領域の一辺に近接する画素に対応する位置は対向辺に近接する画素に対応する位置と同じブロックに属する。例えば、図９Aの部分ブロック１２２a〜１２２bは図９Bの単一ブロックをなし、図９Aの部分ブロック１２３a〜１２３dは図９Cの単一ブロックをなす。
【００５５】
生き延びた候補の中の所定の一候補に対応する画素が入っているブロックが生き延びた他の候補のどれかに対応する画素を含有するブロックより多く残留ドットを含んでいれば、言い換えれば、残存候補を含有するブロックに対応する他のいかなる部分行列に比べ２値行列の対応部分行列の方が含有している残留する「１」の数が多ければ、その所定の生き延びた候補は選択されて次の階数が付けられる。それ以外は、生き延びた候補の中から無作為に選ばれる。
【００５６】
このように選択された次の位置、現在の階数（すなわち、関連しきい値と同値）は、ブロック１２４が示すように、ディザ配列において対応する位置に入力され、次のループで割り当てられる階数が、ブロック１２６が示すように、減分される。その後、割り当てられる階数値が０になるまで図７のループが繰り返される。
【００５７】
最初に選ばれた濃度階調値より低いしきい値を受取ることになる位置に下降順に階数を割り当てる図７のルーチンとは対照的に、図１０A、１０B、１０C（集合的に、「図１０」と称する）のルーチンはそれより高いしきい値を受取ることになる位置に上昇順に階数を割り当てる。ブロック１２８が示すように、図１０のルーチンは図７のルーチンと同じ初期の２値行列から始まるが、図１０のルーチンは、初期の２値行列の「１」に対応する位置ではなく、「０」に対応する位置に階数を割り当てる。
【００５８】
ブロック１３０に示すように、このルーチンは初期の２値行列にある「１」の数に等しい階数から始まる。言い換えれば、未だ割り当てられていない最下位の階数から始まる。ブロック１３２及び１３４に示すように、このルーチンは、増分された階数値がディザ行列の位置の総数に比べてもはや小さくなくなる、すなわち、M x N行列でMNになると、停止する。
【００５９】
その時点まで、次の階数の位置がその階数の値に依存する方法で選択される。図１０Bは、階数域が４個の区間に分けられていることを示している。この例で最下位区間の上限VBOUND1は１６００、つまり階数全域のおよそ１０%である。さて、この範囲の階数が割り当てられると、２値行列の位置の圧倒的多数が「０」を含有する。すなわち、ほとんど全ての位置が未だしきい値を割り当てられていない。例えば、図８に描いた分領域９８においては、画素１００、１０２、１０４、１０６、１０８、１１０を除く全ての画素が候補である。従って、図１０Bのブロック１３６及び１３８に示すように、ルーチンはヴェルノイ分割を行なうことにより候補位置数を減らす。具体的に、位置は、頂点１４２のような結果として生じた分割頂点を含有する、画素１４０など部分領域画素に対応する場合のみ、候補と考えられる。
【００６０】
この方法は、候補のコンボリューション核の中心点を決めドットを未だ含まない画素に対応する核係数の和をとることから生じる得点を各候補位置に割り当てることにより、これらの位置のどれが最大の空所、つまり白い空間における（ヴェルノイ頂点を含む）部分領域画素に対応するかを確定する。ブロック１４３はこの工程を表し、周辺でドットを受取る画素が最も詰っていないクラスタ（群れ）になっている画素を識別することと考えることもできる。この目的で使われる核のタイプの一つは、図１１に例として描いた、９ x ９の１.５画素幅標準偏差ガウス核である。
【００６１】
結果が同点になったら、ブロック１４４に示す距離の判定基準を適用する。演算は、２つの例外があるが、図７の工程１２０と同じである。第１に、判定基準を適用する際に用いられる集合において既に割り当てられた階数は割り当てられている階数より低く、高くはない。第２に、概念上ドットは最も詰まったクラスタ（群れ）から取り除かれるのではなく、最大の空所に追加されるから、選択された画素は周辺でそのように近い階数を有する画素が最もまばらなクラスタ（群れ）になっている画素で、最も詰まったクラスタ（群れ）の画素ではないから、最低距離ではなく、最大距離を探す。すなわち、P = {pi; i = ０, ・・・, M-１}はM個のそのような近い階数を有する位置の集合で、X = {xj; j = ０, ・・・, N-１}は前に工程を生き残るN個の候補位置の集合であるとすれば、次の階数が付けられる位置の指数Jは下記の式により得られる。
【００６２】
【数２】
0003982099.tif 000004
【００６３】
この式において、D(x,y)は位置x及びyに対応する部分領域画素間の先に説明した輪環面の測地的最低距離である。
【００６４】
未だに結果が同点の場合は、ブロック１４６に示すように、図７のブロック１２１に用いられるブロック分割判定基準を補足する判定基準を用いて同点を解消するようにする。生き延びた候補の所定の一つに対応する画素があるブロックは他の生き延びた候補のどれかに対応する画素を含むブロックに比べ含有するドット数が少ない場合、言い換えれば、生き延びた候補を含むブロックに対応する他のどの部分行列よりも２値行列の対応する部分行列の方が含有する「１」の数が少なければ、その所定の生き延びた候補は選択されて次の階数が付けられる。さらに同点があれば、無作為な選択によって同点を解消する。
【００６５】
初期に同点だった候補に階数が付けられる順序は、工程１４４と１４６の判定基準を適用して決められる、もしくは図７の工程１２０及び１２１の判定基準を用いて決められるが、幾つかの状況においてはこの順序が重要である。第１に、同点の候補の数が現在のしきい値を未だ割り当てられていない位置の数を超えていれば、例えば、２５５個のいろいろなしきい値からなる１２８ x １２８の配列として、そうした候補数が６４又は６５より大きければ、順位がこれらの同点の位置のうち別々の位置が受取るしきい値に影響するので、軽率に選択を行なうと目障りな明るい又は中間色のアーティファクトが発生しやすくなる。第２に、選択された候補が選択の判定基準のコンボリューション核を用いて別の候補の得点の計算が行われる領域内にあると、その得点は変り、その他の位置が同じしきい値を受取るような選択にならないようにする。第３に、もう一つの候補のヴェルノイ分割がその選択された候補と一つ以上の頂点を共有し、そのためにその選択によってそのヴェルノイ分割のサイズが変化している場合、その候補の得点が同様に変わり、結果が類似する。本発明を実践する際、これらの状態をテストし、可能な場合にだけ追加の選択判定基準を適用することができるが、結果として生じるディザ行列の画質が量子化レベル数と比較的に無関係で、そのためどんな所定のしきい値を割り当てられる位置の数とも比較的に無関係であるように、追加の判定基準を一様に用いる方が好ましいと考える。
【００６６】
選択されたディザ行列に階数（もしくはしきい値）を入力し、図１０のルーチンは上昇順で、言い換えれば、画像の暗さが増す方向に、階数が割り当てられるから、ブロック１４８に示すように、対応する２値行列位置に「１」を１個加える。ブロック１５０は図１０のループを繰り返す前に階数を増分することを表す。
【００６７】
或る時点で、２値行列における「１」の数、すなわち、現在割り当てられている階数に対応する濃度値を達成させるインクドット数が大きくなり、既に割り当てられた位置に基づいてヴェルノイ分割を計算することの魅力が減少する。これが先にVBOUND1と称したレベルである。割り当てられる階数がそのレベルを超えているがレベルVREGIONより低い場合、工程１３８のように、候補の白い空間の数はヴェルノイ分割で減少しない。レベルVREGIONは、「０」の数がレベルVBOUND1が対応する「１」の数まで減少したレベルである。代わって、工程１４３に関して先に説明したやり方で核を適用することにより、全ての白い空間に得点が割り当てられる。ブロック１５３及び１５４は図１０のルーチンのこの態様を表す。必要なら、図１０Cの工程１４４、１４６及び１４８で前と同じように、候補位置の数がさらに減らされる。
【００６８】
割り当てられる階数が階数全域の９０%に等しいレベルVREGIONに一旦達すると、「０」の数はレベルVBOUND1が対応する「１」の数にまで減るので、分割が２値行列の「１」の位置ではなく「０」の位置に基づいている場合、ヴェルノイ分割の適用が再び魅力的になる。ブロック１５５、１５６及び１５８に示すように、これは、従って、割り当てられる階数がより高レベルであるVBOUND2より低い限り、図１０のルーチンが行なうことであり、レベルVBOUND2は、残留する「０」の数、すなわち、未だ階数を割り当てられていない位置の数がしきい値あたりのディザ行列位置数に等しい（例においては６４又は６５）レベルである。この数は充分に小さいので、候補位置の数を減らす特別の努力をする必要がない。割り当てられる階数がVBOUND2を超えると、ルーチンはブロック１５４の演算を用いて得点を割り当てる。いずれの場合も、必要があれば、図１０Cの演算を再び用いて同点を解消する。
【００６９】
図７及び１０のプロセスを用いて、位置が選ばれるのに伴なってしきい値を明白に割り当てることができるし、もしくは単に階数を割り当て、それにより暗にしきい値を示す階数のディザ行列を出力として生成することができる。後者の場合、しきい値は、先に概要を説明した関係に従って、その後明白に割り当てられる。結果として生じる行列はディザ行列４８に格納され、上述のごとく本発明で活用される。
【００７０】
上記の説明において、様々な機能ユニットを液晶表示装置１４を形成する一部として表したが、画像処理装置１２の一部として形成しても、もしくはパーソナルコンピュータ１８といった他のシステム構成要素の一部として形成してもいい。図１２に示すように、LCD表示装置１４、画像処理装置１２、及び／又はPC １８は、例えば、中央処理装置（CPU）３６の他、ランダムアクセスメモリ（RAM）１６０、読み出し専用メモリ（ROM）１６２、一時レジスタセット１６４などのメモリ、さらに入出力コントローラ１６６を含んでいても構わない。その際、これらは全て内部バス１６８に接続される。例証の目的で、上記の装置をそれぞれ個別に表示しているが、これらの機能ユニットはビデオメモリ４２、ディザ行列４８、ディザ行列生成器７８、多重しきい値処理装置５８、比較器６０など先に説明した様々な機能ユニットの一部又は全部をなすようにしてもいい。さらに、例えば、中央制御型ネットワークの一部としてスキャナ、プリンタ、LCDディスプレイなどシステムの性質によっては、機能ユニットは走査、印刷、LCD表示の各装置を制御するようにプログラムされた汎用のコンピュータの一部であっても構わない。さらに、これらの機能ユニットは個別部品、特定用途向け集積回路、適正ソフトウェアを実行するプロセッサその他類似のもの或いはそれらの組み合わせで実行するようにしてもいい。
【００７１】
LCD装置１４及び／又は画像処理装置１２及び／又は本書で説明した様々な機能ユニットを動作させるオペレーティングシステムソフトウェア及び／又は特定用途向けソフトウェアはメモリ１６０、１６２、１６４の何らかの組み合わせに格納しても、もしくはそれぞれI/Oバス１８０に接続された、ハードディスクドライブ１７０、ディスケットドライブ１７２、及びコンパクトディスクドライブ１７４など一つ以上のI/Oユニットに外部的に格納されるようにしてもいい。様々な機能ユニットを動作させる及び／又は本発明の方法を実行するソフトウェアはハードディスク１７０A、ディスケット１７２A又はコンパクトディスク１７４Aなど媒体に格納されても、もしくは遠隔装置１７８に格納され、通信インタフェース１７６を介して入力されるようにしてもいい。
【００７２】
図１３は本発明の方法の大まかな流れを示す。例として、工程S１０で、グラフィックスコントローラ３８は次の画像を受け取り、工程S１２でそれがビデオメモリ４２に読み込まれるようにする。画像データの検索及び一時格納はデバイスからデバイスで異なり、デバイスの相対スピード、記憶容量、バンド幅によって違ってくる。そうした動作はよく知られた技術である。工程S１４で、濃淡又はカラーを表す第１画素Pxyの値が受取られる。工程S１６でこの画素値が対応するディザ行列のしきい値Di,jと比較される。画素値がしきい値より小さければ、LCDディスプレイに送られる出力画素値Poutは０（すなわち、オフ）になる。現在の画素値がしきい値と同じかそれ以上であれば、量子化ディザ行列のしきい値ＤijQが工程S１８で量子化テーブルのアクティブレベルと比較される。量子化ディザ行列のしきい値DijQが量子化テーブルのアクティブレベルの一つならば、LCDディスプレイに送られる出力画素値Poutは１（すなわち、オン）になる。工程S２０で現在の画素が画像の最後の画素でない場合は、次の画素が工程S２２で受取られ、現在のリフレッシュフレームサイクルの完全な画像が表示されるまで工程S１６から始まるループが繰り返され、プロセスは工程S２４に進む。これが表示サイクルの最後のフレームリフレッシュならば、次の画像が工程S１０で検索される。そうでなければ、新たなレベルが今やアクティブでプロセスが工程S１４にループバックして現在の画像の最初の画素を受取れるように、量子化テーブルのレベルがシフトされる。
【００７３】
発明を幾つかの具体的な実施例に結び付けて説明してきたが、上記の説明に鑑みればさらに数多くの代替え案、変更、変形がすぐ分かることが当業者には明白であろう。したがって、本書で説明した発明は添付の請求の範囲の精神並びに範疇に入るそうした代替え案、変更、業務用途、変形を全て含むものとする。
【図面の簡単な説明】
【図１】A、B、Cは、本発明の幾つかの大まかな環境構成を表すブロック図。
【図２】A、Bは、合わせて本発明の主要な機能構成要素の概略ブロック図をなす。
【図３】本発明の典型的なディザ行列のしきい値を表す。
【図４】５個のレベルに量子化された図３のディザ行列を表す。
【図５】内容が繰り返して５フレームシフトされた本発明の例としての量子化テーブル。
【図６】本発明のディザ行列生成法の初期化段階のフローチャート。
【図７】本発明のディザ行列の位置に最下位階数値を割り当てる方法のフローチャート。
【図８】ヴェルノイ分割の例証に用いた図。
【図９】A〜Cは、ブロック分割を示す。
【図１０】A〜Cは、本発明のディザ行列の位置により高い階数値を割り当てる方法のフローチャート。
【図１１】空所の大きさを査定するのに用いるガウス核の図。
【図１２】本発明の主要な機能構成要素の別の部分の概略ブロック図。
【図１３】本発明の方法の大まかな工程を示すフローチャート。
【図１】
0003982099.tif 000005
【図２】
0003982099.tif 000006
【図３】
0003982099.tif 000007
【図４】
0003982099.tif 000008
【図５】
0003982099.tif 000009
【図６】
0003982099.tif 000010
【図７】
0003982099.tif 000011
【図８】
0003982099.tif 000012
【図９】
0003982099.tif 000013
【図１０】
0003982099.tif 000014
【図１１】
0003982099.tif 000015
【図１２】
0003982099.tif 000016
【図１３】
0003982099.tif 000017