(57)【要約】【課題】クラスタリング処理において、着目画素とクラスタ群との色距離比較の回数を抑え、クラスタリング処理の精度を落とすことなく高速に処理を行う。【解決手段】入力画像中の着目画素のコンポーネント和とクラスタの代表値のコンポーネント和との差の絶対値が第一の閾値以下であるクラスタを、比較クラスタとして選択する。そして、当該選択した比較クラスタそれぞれの代表値と前記着目画素との間の色距離を算出する。算出した色距離のうちの最小値が第二の閾値以下の場合、当該最小値の色距離に対応するクラスタに前記着目画素を分類する。一方、算出した色距離のいずれもが前記第二の閾値より大きい場合は、当該着目画素を分類するクラスタを新たに生成する。【選択図】図１
2010211639.tif 000002
【特許請求の範囲】
【請求項１】
入力画像データに対し処理を行う画像処理装置であって、
前記入力画像データの中の着目画素のコンポーネント和とクラスタの代表値のコンポーネント和との差の絶対値が第一の閾値以下であるクラスタを、前記着目画素と比較する比較クラスタとして選択する比較クラスタ選択手段と、
前記比較クラスタ選択手段により選択した前記比較クラスタそれぞれの代表値と前記着目画素との間の色距離を算出する色距離算出手段と、
前記色距離算出手段において算出した前記色距離の最小値が第二の閾値以下の場合、当該最小値の色距離に対応するクラスタに前記着目画素を分類するクラスタ分類手段と、
前記色距離算出手段において算出した前記色距離のいずれもが前記第二の閾値より大きい場合、当該着目画素を分類するクラスタを新たに生成する新規クラスタ生成手段と
を有することを特徴とする画像処理装置。
【請求項２】
生成済みのクラスタ群を前記コンポーネント和に基づいてソートするクラスタ群ソート手段を更に備え、
前記比較クラスタ選択手段は、前記クラスタ群ソート手段によりソートした前記クラスタ群を処理対象とすることを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記色距離算出手段で算出する前記色距離がマンハッタン距離であり、
前記第一の閾値と前記第二の閾値とが同じ値であることを特徴とする請求項１または２に記載の画像処理装置。
【請求項４】
前記色距離算出手段で算出する前記色距離がユークリッド距離であり、
前記第一の閾値と前記第二の閾値とが異なる値であることを特徴とする請求項１または２に記載の画像処理装置。
【請求項５】
前記入力画像データを、クラスタ毎にベクトル化するベクトルデータ変換手段をさらに有することを特徴とする請求項１乃至４のいずれか一項に記載の画像処理装置。
【請求項６】
入力画像データに対し処理を行う画像処理装置の制御方法であって、
前記画像処理装置の比較クラスタ選択手段が、前記入力画像データの中の着目画素のコンポーネント和とクラスタの代表値のコンポーネント和との差の絶対値が第一の閾値以下であるクラスタを、前記着目画素と比較する比較クラスタとして選択する比較クラスタ選択工程と、
前記画像処理装置の色距離算出手段が、前記比較クラスタ選択工程により選択した前記比較クラスタそれぞれの代表値と前記着目画素との間の色距離を算出する色距離算出工程と、
前記画像処理装置のクラスタ分類手段が、前記色距離算出工程において算出した前記色距離の最小値が第二の閾値以下の場合、当該最小値の色距離に対応するクラスタに前記着目画素を分類するクラスタ分類工程と、
前記画像処理装置の新規クラスタ生成手段が、前記色距離算出工程において算出した前記色距離のいずれもが前記第二の閾値より大きい場合、当該着目画素を分類するクラスタを新たに生成する新規クラスタ生成工程と
を有することを特徴とする制御方法。
【請求項７】
コンピュータを、
入力画像データの中の着目画素のコンポーネント和とクラスタの代表値のコンポーネント和との差の絶対値が第一の閾値以下であるクラスタを、前記着目画素と比較する比較クラスタとして選択する比較クラスタ選択手段と、
前記比較クラスタ選択手段により選択した前記比較クラスタそれぞれの代表値と前記着目画素との間の色距離を算出する色距離算出手段と、
前記色距離算出手段において算出した前記色距離の最小値が第二の閾値以下の場合、当該最小値の色距離に対応するクラスタに前記着目画素を分類するクラスタ分類手段と、
前記色距離算出手段において算出した前記色距離のいずれもが前記第二の閾値より大きい場合、当該着目画素を分類するクラスタを新たに生成する新規クラスタ生成手段と
して機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像処理装置、画像処理方法、及びプログラムに関する。特に画像処理におけるクラスタリングを用いたスキャンノイズの減色処理に関する。更には、着目画素と各クラスタの色距離を比較する際に、比較処理を行うクラスタ数を抑えることでクラスタリング処理を高速に行う方法とその装置に関する。
【背景技術】
【０００２】
近年、情報の電子化が進み、紙文書をそのまま保存するのではなく、スキャナ等で読み取ったのち電子データとして保存したり、その電子データを他装置に送信したりするシステムが普及してきている。こういった状況において、電子データの保存や送信コストを削減するため、電子化された文書には高い圧縮性が要求されている。一方でユーザの利便性に重点を置くと、部分的に電子データ内のオブジェクトを編集できる再利用性と、拡大や縮小をしても画質が劣化しない高画質性といった点も要求されている。
【０００３】
ところが文書データに文字領域や写真領域が混在する場合、文字領域に適した圧縮を行うと画質は良いが圧縮率が低くなり、写真領域に適した圧縮を行うと圧縮率は高いが文字領域の画質が劣化してしまう問題がある。そこで文書画像の電子データを文字領域や写真領域に分離し、再利用性と高画質性が重視される文字領域はベクトルデータに変換し、それ以外の簡易にベクトル化で再現できない写真領域等はＪＰＥＧで圧縮する。そして、各領域の処理結果を合成して出力することにより、文書画像の高圧縮性、再利用性、高画質性を実現する手法が提案されている（特許文献１を参照）。
【０００４】
また文字領域だけでなく、数色の均等色で構成され、輪郭がはっきりしている特徴を持つ図形領域（イラストやクリップアート、線画と一般的に呼ばれる）をベクトル処理の対象とする手法も提案されている（特許文献２を参照）。ここで提案されている方式は、画像を入力し、色の類似度を使って入力画像の色数を減色する。次に各色領域の輪郭線を抽出した後に関数近似を行い、色情報を加えてベクトルデータを出力するものである。
【０００５】
特許文献２の方式でベクトル化を行うには、入力画像に含まれるスキャンノイズを低減し、原画像の輪郭を抽出するための前処理として減色処理が必要である。スキャンノイズの減色処理としては、あらかじめ決められた代表色とのマッチングを行う方式と、特許文献２でも使用されているクラスタリングを用いる方式が有用である。代表色とのマッチングは入力画像を選択した数色に分類できるものの、あらかじめ数色の代表色を決定しておく必要があり、また決定した代表色に原画像と著しく異なる色が使われる可能性がある。そのため原画像で使われている色数とその色味が処理前に不明であり、原画像で使われている色味を精度良く残しつつ減色するにはクラスタリングを用いる方式の方が優れている。
【０００６】
クラスタリングを実現する技術はいくつか存在するが、例えば公知のＮＮ法(Ｎｅａｒｅｓｔ  Ｎｅｉｇｈｂｏｒ)を適用することができる。これは入力Ｐ１からＰｎをクラスタリングする際、まずＰ１を代表パターンとするクラスタＣ１を作成する。次にＰｉ(ｉ≧２)に着目し、Ｃｊ(ｊはクラスタ数)との距離を比較する。ＰｉとＣｊとの距離があらかじめ定められた閾値未満の場合、距離が最も小さいクラスタにＰｉを所属させる。閾値未満の距離にあるクラスタが見つからなかった場合、新たなクラスタを作成する。これをすべての入力に対して実行するのがＮＮ法のアルゴリズムである。ＮＮ法の詳細に関しては、非特許文献１等に述べられている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００４−２６５３８４号公報
【特許文献２】特開２００６−３４４０６９号公報
【非特許文献】
【０００８】
【非特許文献１】安居院、長尾著“Ｃ言語による画像処理入門”初版,ＩＳＢＮ４−７８５６−３１２４−４,昭晃堂,２０００年
【発明の概要】
【発明が解決しようとする課題】
【０００９】
減色処理を適用する場合、入力を画素値（ＲＧＢ値、または輝度値など）とし、距離をマンハッタン距離（シティブロック距離とも呼ばれる）やユークリッド距離といった色距離にすればよい。当然のことながら、色距離を小さくとると生成されるクラスタ数が多くなり、画素値と各クラスタの比較演算に多くの処理時間を要するようになる問題がある。図３はクラスタリング処理の模式図とフローチャートである。白黒画像等、画素値が１次元の値（例えば０（黒）から２５５（白）の範囲の値）で与えられていれば、生成済みのクラスタを画素値に基づいてソートしておくことで比較が必要なクラスタ数を抑えることができる。しかし例えばＲＧＢの色空間上でクラスタリングを行う場合、色距離は３次元で表現されるため、着目している画素がどのクラスタと色距離が近いかを比較の途中で一意に特定することができず、このような手法をとることができない。結果として最も色距離が近いクラスタを探索するにはすべての生成されたクラスタとの色距離を求める必要がある。クラスタ数が多くなるにつれて処理時間が長くなる原因はここにある。
【課題を解決するための手段】
【００１０】
上記課題を解決するために、本発明に係る画像処理装置は以下の構成を特徴とする。入力画像データに対し処理を行う画像処理装置であって、前記入力画像データの中の着目画素のコンポーネント和とクラスタの代表値のコンポーネント和との差の絶対値が第一の閾値以下であるクラスタを、前記着目画素と比較する比較クラスタとして選択する比較クラスタ選択手段と、前記比較クラスタ選択手段により選択した前記比較クラスタそれぞれの代表値と前記着目画素との間の色距離を算出する色距離算出手段と、前記色距離算出手段において算出した前記色距離の最小値が第二の閾値以下の場合、当該最小値の色距離に対応するクラスタに前記着目画素を分類するクラスタ分類手段と、前記色距離算出手段において算出した前記色距離のいずれもが前記第二の閾値より大きい場合、当該着目画素を分類するクラスタを新たに生成する新規クラスタ生成手段とを有することを特徴とする。
【発明の効果】
【００１１】
本発明によれば着目画素とクラスタ群の色距離を求める処理を少数に限定することができる。新しいクラスタを作成するかどうかの閾値が第一の閾値として与えられるとすると、着目画素のコンポーネント和とクラスタ群のコンポーネント和との差分の絶対値が第一の閾値以下の時のみ、着目画素とクラスタの色距離が第一の閾値以下の可能性がある。結果としてクラスタリングを用いた減色処理を高速に行うことができる。
【００１２】
さらに、本発明によれば、着目画素と各クラスタの色距離をマンハッタン距離で求めることにより、処理結果を変えることなく、クラスタリング処理を高速化することができる。
【図面の簡単な説明】
【００１３】
【図１】実施形態における画像処理装置のメイン処理ブロック構成図である。
【図２】実施形態における画像処理装置のブロック構成図である。
【図３】３次元空間上で着目画素とクラスタ群との色距離を求めるイメージ図とその処理のフローチャートを示す図である。
【図４】実施形態における画像処理装置のメイン処理を示すフローチャートである。
【図５】ソート済みのクラスタとクラスタ選択処理で用いる値の例を示す図である。
【発明を実施するための形態】
【００１４】
＜実施形態１＞
以下、添付の図面を参照して本発明の実施の形態を説明する。ただし、この実施の形態に記載されている構成要素はあくまで例示であり、本発明の技術的範囲は、特許請求の範囲によって確定されるのであって、以下の個別の実施形態によって限定されるわけではない。
【００１５】
本実施形態の画像処理装置の構成例について、図２のブロック図を参照して説明する。同図において、７は装置全体を制御するＣｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＣＰＵ）である。６は変更を必要としないプログラムやパラメータを格納するＲｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）である。５は外部装置等から供給されるプログラムやデータを一時記憶するＲａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）である。１は、文書等を光電走査して電子的な画像データを得るためのスキャナであり、３はこのスキャナ１と画像処理装置を接続する画像入出力インターフェースである。２は、スキャナ１で読み取られた入力画像データ等を保持する画像メモリである。１２は固定して設置されたハードディスクやメモリカード、あるいは着脱可能なフレキシブルディスク（ＦＤ）やＣｏｍｐａｃｔ  Ｄｉｓｋ（ＣＤ）等の光ディスク、磁気や光カード、ＩＣカード、メモリカード等を含む外部記憶装置である。また、１３はこれら外部記憶装置１２と画像処理装置との入出力（Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）インターフェースである。１５はユーザの操作を受け、データを入力するマウス等のポインティングデバイス１０やキーボード９等の入力デバイスとのインターフェースである。１４は画像処理装置の保持するデータや供給されたデータを表示するためのディスプレイモニタ８とのインターフェースである。４はインターネット等のネットワーク回線に接続するためのネットワークインターフェースである。１１は１〜１５の各ユニットを通信可能に接続するシステムバスである。
【００１６】
＜クラスタリング処理＞
以下、ＣＰＵ７上で実行されるプログラムにより本願発明を実現する処理手順を、図１のブロック図と図４のフローチャートを用いて説明する。ステップＳ１０００で処理を開始すると、処理対象となる画像領域を含む画像データを入力する。画像入力に関しては、スキャナ１にて読み取られた画像データを画像入出力Ｉ／Ｏ３を介して画像メモリ２に入力する。また、通信Ｉ／Ｆ４を介して、装置外部より前記処理対象となる画像領域を含む画像を入力してもよく、あるいは、外部記憶装置１２に予め記憶される画像データをＩ／Ｏ１３を介して読み込むものであってもよい。得られた入力画像は、画像メモリ２上に保持される。次に読み取った入力画像データに対しステップＳ２０００でクラスタリング処理を行い、各画素の値がクラスタ番号からなるインデックス画像を生成する。これは図１におけるクラスタ群生成手段１１を実現している。入力がカラー画像で、ＲＧＢ空間でクラスタリングを行うと、各クラスタはＲＧＢの画素値を値として持つ。ステップＳ２１００ではソートの基準用として各クラスタのコンポーネント和（Ｒ＋Ｇ＋Ｂ）を求めクラスタの順序を昇順、または降順でソートしておく。なお、本実施形態において、画素値をＲＧＢで表す場合、コンポーネント和としてＲＧＢの各値の和を用いるものとするが、コンポーネント和の算出式の詳細に関しては後述する。これは図１におけるコンポーネント和に基づくクラスタ群ソート手段１３を実現している。なお、クラスタのコンポーネント和は、クラスタが有する代表値である色地の各色成分の和となる。クラスタの代表値は、例えば、新規にクラスタを生成する際に最初に属する画素値を用いることができる。また、新たな画素がクラスタに加わるたびにそのクラスタに属する画素の各コンポーネントの平均値を求め、それを代表値としても良い。もちろんこれらの方法に限定するものではなく、その方法は問わない。ステップＳ２２００ではステップＳ１０００で読み取った入力画像から未処理の画素を着目画素として１つ選択し、着目画素のコンポーネント和を求める。これは図１における着目画素選択手段１４を実現している。ステップＳ２３００では色距離を算出する比較クラスタの選択を行う。
【００１７】
図５はクラスタリング処理の途中状態で保持するデータを表した例であり、５つのクラスタが生成された後、各クラスタのコンポーネント和に基づいて昇順でソートされている状態を示している。これにおいて、ＲＧＢ＝（１７０，２２０，１２０）の値を持つ着目画素に対して、生成済みのクラスタの中から比較クラスタを選択しようとしている。ここで新たにクラスタを生成するかどうかの判断に用いる第一の閾値を例えば４６とする。ここで、クラスタと着目画素の色距離Ｘをマンハッタン距離で求めると、各クラスタが保持するコンポーネント和Ａと着目画素のコンポーネント和Ｂには以下の関係式が常に成り立つ。
【００１８】
クラスタのコンポーネント（ＲＧＢ）和Ａ＝Ｒ１＋Ｇ１＋Ｂ１
着目画素のコンポーネント（ＲＧＢ）和Ｂ＝Ｒ２＋Ｇ２＋Ｂ２
クラスタと着目画素の色距離（マンハッタン距離：Ｘ）＝｜Ｒ１−Ｒ２｜＋｜Ｇ１−Ｇ２｜＋｜Ｂ１−Ｂ２｜
とすると、
｜Ａ−Ｂ｜＝｜（Ｒ１＋Ｇ１＋Ｂ１）−（Ｒ２＋Ｇ２＋Ｂ２）｜
＝｜（Ｒ１−Ｒ２）＋（Ｇ１−Ｇ２）＋（Ｂ１−Ｂ２）｜
≦｜Ｒ１−Ｒ２｜＋｜Ｇ１−Ｇ２｜＋｜Ｂ１−Ｂ２｜（＝Ｘ）
通常、クラスタリング処理では最も色距離が近いクラスタに着目画素を分類するが、上記の通り、コンポーネント和の差分値（図４における｜Ａ−Ｂ｜）と色距離では常に以下の関係式が成り立つ。
【００１９】
｜Ａ−Ｂ｜≦色距離(マンハッタン距離)
よって、第一の閾値４６以下の色距離にあるクラスタを探索するには、クラスタと着目画素のコンポーネント和の差分｜Ａ−Ｂ｜が４６以下のクラスタに限定してクラスタリング処理を行えば十分である。クラスタと着目画素のコンポーネント和の差分は、クラスタがソートされていると、コンポーネント和の差分が最も小さいクラスタよりソート順が前または後ろにいくにつれて、大きくなっていくことになる。
【００２０】
例えば、コンポーネント和の差分が最も小さいクラスタがソート順の途中にある場合、ソート順の最初は当該差分が大きいものから始まって単調減少し、ある点を境に単調増加に転じる傾向がある。そこでコンポーネント和の差分が最も小さいクラスタをまず探索し、その後、ソート順の前後に位置するクラスタを順に参照して、コンポーネント和の差が第一の閾値以下のものだけ選択する。これにより、色距離が第一の閾値以下のクラスタを含むクラスタ群を効率よく限定することができる。もちろんクラスタのリストを頭から順に走査し、条件を満たす区間だけを取り出すことでも同様の処理が可能である。
【００２１】
ステップＳ２４００ではステップＳ２３００で１つ以上のクラスタが比較対象のクラスタ（比較クラスタ）として選択されたかを判定する。もし選択されたクラスタが１つもない場合は着目画素を元に新規クラスタをステップＳ２５００で生成する。例えば、着目画素の画素値を代表値にした新規クラスタを生成する。選択されたクラスタが１つ以上あった場合、ステップＳ２６００で着目画素と各選択されたクラスタとの色距離（すなわち、色空間における距離）をそれぞれ求める。本実施形態で求める色距離は、上述したマンハッタン距離である。
【００２２】
ステップＳ２７００では選択されたクラスタの中で、最も着目画素との色距離が小さいクラスタ（すなわち、色距離が最小値となるクラスタ）を取り出し、求めた色距離と第二の閾値の値（例えば４６）とを比較する。求めた色距離が第二の閾値以下の場合、ステップＳ２８００で着目画素を当該クラスタ（すなわち色距離が最小値となったクラスタ）に分類する。画素のクラスタへの分類は、例えば画素に対応付けて各クラスタが有する識別子を配列した属性マップ（前述のインデックス画素）を作成することで実現でき、各画素とクラスタの関連付けを保持できる。もし色距離が第二の閾値よりも大きい場合、ステップＳ２５００に進み、着目画素を元に新規クラスタを作成する。新規クラスタの作成は、例えば新規クラスタの識別子とその代表値を定義し、それを保存することなどが処理として行われる。ステップＳ２５００またはＳ２８００の処理が終了すると、当該入力画像内の画素全てをクラスタリング処理したか否かを判定する。クラスタリング処理が終了していないと判定した場合は、ステップＳ２１００に戻って、未処理の画素を次の着目画素として選択してクラスタリング処理を繰り返す。全ての画素のクラスタリングが終了したと判定した場合は、ステップＳ３０００に進む。すなわち、クラスタ群生成処理であるＳ２０００は、入力画像における全ての画素に対して行われる事となる。
【００２３】
なお、本実施形態１では、色距離算出においてマンハッタン距離を用いるので、ステップＳ２３００で用いる閾値（第一の閾値）と、ステップＳ２７００で用いる閾値（第二の閾値）は、同じ値を用いるものとする。したがって、上述した例では、ステップＳ２３００、Ｓ２７００のどちらにおいても、同じ閾値（例えば、４６）を用いた。
【００２４】
ステップＳ２３００とステップＳ２４００の処理は図１における比較クラスタ選択手段１５を実現し、ステップＳ２５００の処理は図１における新規クラスタ生成手段１６を実現している。またステップＳ２６００とステップＳ２７００の処理は図１における色距離算出手段１７を実現し、ステップＳ２８００の処理は図１におけるクラスタ分類手段１８を実現している。以上、ステップＳ２０００の説明ではＲＧＢ空間でのクラスタリングを例として挙げたが、これに限らずＨＳＶやＹＭＣＫなど他の色空間を用いても同様の効果を得ることが可能である。
【００２５】
ステップＳ３０００ではステップＳ２０００のクラスタリング処理によって得られた減色画像から各クラスタに属する画素塊の輪郭を抽出し、輪郭を関数近似することでクラスタ毎にベクトル化処理を行う。ベクトル化処理は例えば特許文献２の手法を適用することができる。この処理はベクトルデータ変換手段１２で行われる。
【００２６】
以上により、着目画素とクラスタ群の色距離を求める処理を少数に限定することができる。そして、その結果としてクラスタリングを用いた減色処理を高速に行うことが可能となる。以上本発明にかかる実施形態を説明したが、実施形態の処理の多くは、画像処理装置上で実行されるコンピュータプログラムによるものであるので、当然、本発明はかかるコンピュータプログラムをもその範疇とする。通常、コンピュータプログラムはＲＡＭ５やＲＯＭ６、またはＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されていて、それをコンピュータにセットしシステムにコピーもしくはインストールすることで実行可能になる。従って、かかるコンピュータ可読記憶媒体も当然に本発明の範疇に入る。
【００２７】
＜実施形態２＞
実施形態１では図４のステップＳ２６００で色距離を求める際に、各コンポーネントの差分を単純に足した和を色距離として用いた。ＲＧＢの各コンポーネントを同じ条件で扱う場合は問題ないが、例えば、異なる条件の一つとして、明るさを考慮してクラスタリングを行う場合も考えられる。例えばＹＣｂＣｒ色空間のＹは輝度を表しているが、ＲＧＢからの変換式は以下で与えられる。
【００２８】
Ｙ＝０．２９９Ｒ＋０．５８７Ｇ＋０．１１４Ｂ
これはＲＧＢの各コンポーネントにあらかじめ定められた閾値を係数として掛けていると考えることもできる。色距離を求める際に、このような係数を各コンポーネントにかけてから求めてもよい。この場合、ステップＳ２１００、ステップＳ２３００で用いるコンポーネント和を求める際にも、色距離に対して適用したものと同じ所定の閾値を各コンポーネントに係数として掛けた値の和をコンポーネント和として扱うことで、実施形態１に述べた処理と同じように行うことができる。この例の場合ではＲＧＢの各コンポーネントを均等に扱うのではなく、明るさの観点から見た寄与率をかけて扱っているため、明るさ重視のクラスタリングを行う系でも本発明を適用することができる。また入力画像データをあらかじめ所定の閾値（係数）に基づいて正規化しておくことでも、実施形態１に述べた処理と同様に行うこともできる。
【００２９】
以上により、着目画素とクラスタ群の色距離を求める処理を少数に限定することができる。そして、その結果としてクラスタリングを用いた減色処理を高速に行うことが可能となる。
【００３０】
＜実施形態３＞
実施形態３では、図４のステップＳ２６００で色距離を求める際にユークリッド距離などマンハッタン距離以外の指標を用いる。この場合、各コンポーネントの線形和の差分値（図５における｜Ａ−Ｂ｜）と色距離（ユークリッド距離）の間には以下の関係式は成立するとは限らない。
【００３１】
|Ａ−Ｂ|≦色距離（ユークリッド距離）
しかしながら、マンハッタン距離とユークリッド距離にはある程度の相関関係があるため、ステップＳ２３００で実施形態１と同様の比較クラスタ選択処理を行うことにより、比較クラスタを絞り込むようにしてもよい。すなわち、各コンポーネント和の差分の絶対値を用いて絞り込み処理を行った後に、ステップＳ２６００で比較クラスタに対する色距離をユークリッド距離で算出する。
【００３２】
なお、実施形態１では、色距離としてマンハッタン距離を用いたので、ステップＳ２３００で比較クラスタの選択処理に用いる閾値と、ステップＳ２７００で用いる閾値は、同じ値を用いた。一方、本実施形態３では色距離算出にユークリッド距離を用いるので、ステップＳ２３００で比較クラスタの選択処理に用いる閾値（第一の閾値）と、ステップＳ２７００で用いる閾値（第二の閾値）は異なる値にするのが望ましい。
【００３３】
以上により、着目画素とクラスタ群の色距離を求める処理を少数に限定することができる。そして、その結果としてクラスタリングを用いた減色処理を高速に行うことが可能となる。
【００３４】
＜その他の実施形態＞
なお、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムをコンピュータ（またはＣＰＵやＭＰＵ）が読出し実行することによっても、達成される。この場合、プログラムは図示したフローの手順を実現するためのものを含むこととなる。
【図１】
2010211639.tif 000003
【図２】
2010211639.tif 000004
【図４】
2010211639.tif 000005
【図３】
2010211639.tif 000006
【図５】
2010211639.tif 000007