(57)【要約】【課題】クラスタリングの前段処理の中で、新規クラスタの追加だけでなく、既存クラスタの統合を随時行うことにより、処理途中でクラスタ数が増えすぎるのを抑え、処理を高速化する。【解決手段】領域の各画素を色差に応じてクラスタ１、２に分割する（ｂ）。クラスタ１、２にそれぞれ属する各画素の連続性評価値を計算する（ｃ）、（ｄ）。注目画素ｅの連続性評価値は、近傍４画素（ａ，ｂ，ｃ，ｄ）のうち、注目画素ｅと同じクラスタに属する画素数（０〜４の値）として求める。連続性評価値が小さい（領域的な連続性が低い）クラスタ２を、連続性評価値が大きい（領域的な連続性が高い）クラスタ１にクラスタ統合する。【選択図】図１２
2010183416.tif 000002
【特許請求の範囲】
【請求項１】
カラー画像内の各画素を色情報に基づき複数のクラスタに分割するクラスタ分割手段を有し、前記クラスタ分割手段の出力に応じて画像処理を行う画像処理装置であって、前記クラスタ分割手段は、新規クラスタの追加、および、既存クラスタの統合を随時行いながら前記各画素を複数のクラスタに分割することを特徴とする画像処理装置。
【請求項２】
同一クラスタに属する画素の領域的な連続性を評価する連続性評価値を算出する連続性評価値算出手段を有し、前記既存クラスタの統合は、前記連続性評価値に基づき、領域的な連続性が低いクラスタを優先して他のクラスタへ統合することを特徴とする請求項１記載の画像処理装置。
【請求項３】
前記既存クラスタの統合は、新規クラスタの追加によりクラスタの数が予め設定された上限値を超える場合に、随時実施することを特徴とする請求項１または２記載の画像処理装置。
【請求項４】
注目画素が属するクラスタを既存クラスタの中から判定する、あるいは、注目画素が属するクラスタが既存クラスタの中に存在しないと判定する所属クラスタ判定手段を有し、前記新規クラスタの追加は、前記所属クラスタ判定手段において注目画素が属するクラスタが既存クラスタの中に存在しないと判定された場合に、随時実施することを特徴とする請求項１から３のいずれか１項に記載の画像処理装置。
【請求項５】
カラー画像内の暗部領域を判定する暗部領域判定手段を有し、前記クラスタ分割手段は、前記暗部領域の各画素を色情報に基づき複数のクラスタに分割することを特徴とする請求項１から４のいずれか１項に記載の画像処理装置
【請求項６】
前記画像処理は、前記クラスタ分割手段の出力に応じて、前記暗部領域の明るさを補正する補正量を決定し、決定した補正量に基づいて、前記カラー画像を階調補正する手段であることを特徴とする請求項５記載の画像処理装置。
【請求項７】
カラー画像内の各画素を色情報に基づき複数のクラスタに分割するクラスタ分割工程を有し、前記クラスタ分割工程の出力に応じて画像処理を行う画像処理方法であって、前記クラスタ分割工程は、新規クラスタの追加、および、既存クラスタの統合を随時行いながら前記各画素を複数のクラスタに分割することを特徴とする画像処理方法。
【請求項８】
請求項７記載の画像処理方法をコンピュータに実現させるためのプログラム。
【請求項９】
請求項７記載の画像処理方法をコンピュータに実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、カラー画像の各画素を複数のクラスタに分割し、クラスタ分割結果に応じて画像処理を行う画像処理装置、画像処理方法、プログラムおよび記録媒体に関し、カラーＭＦＰ、カラープリンタ、デジタルカメラの付属ソフト等に好適な技術である。
【背景技術】
【０００２】
画像を複数のクラスタに分割する従来のクラスタリング技術として、１画素に対して１クラスタを割り当てた初期状態からスタートし、それらを１ステップ毎に統合していく階層的クラスタリングや、あるいは、予めクラスタ数と各クラスタのクラスタ代表値を設定し、各画素をクラスタ代表値との距離を評価していずれかのクラスタに割り当てた後、クラスタ間で所属画素を移動させてクラスタ内距離を最小にしていくＫ平均法がある。
【０００３】
従来のクラスタリング技術はいずれも、各画素を複数クラスタに一旦領域分割する前段処理と、統合（あるいは分割）を行う後段処理で実現される。特許文献１に記載の方法もまた、カラー画像を色情報に基づいて領域分割した後、分割領域を統合する方法である。
【０００４】
階層的クラスタリングは圧倒的に多くの処理時間を要する問題があり、Ｋ平均法はクラスタ数とクラスタ代表値の初期値の設定次第で結果が意外に大きく変わってしまう問題がある。特許文献１は前段の領域分割について方法が特定されていない。それに対して、特許文献２は、画素毎に所属するクラスタを判定して領域分割する前段処理の中で、クラスタ数０からスタートし、最初の画素が入力されたらその画素の値をクラスタ代表値（クラスタ代表点）とする新規クラスタを追加し（この時点でクラスタ数は１）、その後は次の画素が入力される度にクラスタ代表値との距離に基づき必要に応じて新規クラスタを追加する。この方法によれば、クラスタ数が固定でなく、画像に対応したクラスタのみ追加されるため、不要なクラスタとの距離を計算する処理時間を省略できるし、クラスタ数とクラスタ代表値の初期値によって結果が大きく変わることがない。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、特許文献２はクラスタ数が固定でないことから、画像によってはクラスタ数が不要に増加してクラスタリングの前段処理部分で計算時間が嵩んでしまうケースがある。前段処理後のクラスタ分割結果を観察したところ、特にノイズが大きい画像でクラスタ数が増加する問題が起こる。注目画素とその時点で存在する各クラスタのクラスタ代表値との距離を算出し、予め設定した距離閾値以内のクラスタが既存クラスタの中になければ新規クラスタを追加することになるが、ノイズの起伏部分（山または谷）で新規クラスタが発生しやすいためである。ノイズの影響からクラスタ数が増加したとしても、後段処理部分で上手く他のクラスタと統合できれば最終的に得られるクラスタ分割結果としては問題ない（特許文献２のように、所属数が少ないクラスタを他のクラスタに統合する簡易的な後段処理でも良好な結果が得られる）が、処理途中でクラスタ数が増えれば増えるだけ処理順が遅い画素に要する処理時間が増えてしまう。
【０００６】
本発明は上記した課題に鑑みてなされたもので、
本発明の目的は、カラー画像内の各画素を色情報に基づき複数のクラスタに分割するクラスタ分割において、クラスタリングの前段処理の中で、新規クラスタの追加だけでなく、既存クラスタの統合を随時行うことにより、処理途中でクラスタ数が増えすぎるのを抑え、処理を高速化すると共に、ノイズの起伏部分で追加される新規クラスタは、領域的な連続性が低いという特徴があるので、クラスタの領域的な連続性を評価し、連続性が低いクラスタから順に随時統合することにより、処理を高速化した上で最終的なクラスタ分割の精度を維持する画像処理装置、画像処理方法、プログラムおよび記録媒体を提供することにある。
【課題を解決するための手段】
【０００７】
本発明は、カラー画像内の各画素を色情報に基づき複数のクラスタに分割するクラスタ分割手段を有し、前記クラスタ分割手段の出力に応じて画像処理を行う画像処理装置であって、前記クラスタ分割手段は、新規クラスタの追加、および、既存クラスタの統合を随時行いながら前記各画素を複数のクラスタに分割することを最も主要な特徴とする。
【発明の効果】
【０００８】
本発明によれば、画像内の各画素をクラスタ分割する途中段階で、新規クラスタの追加と既存クラスタの統合を随時行うので、処理途中でのクラスタ数の増加が抑制され、処理が高速化される。
【図面の簡単な説明】
【０００９】
【図１】従来のクラスタリングと本発明のクラスタリングの相違を説明する図である。
【図２】本発明の実施例の構成を示す。
【図３】ヒストグラムの例と、画像を領域判定した結果の一例を示す。
【図４】閾値決定部の構成を示す。
【図５】ヒストグラムの分析範囲１、分析範囲２と決定される閾値を示す。
【図６】作成される補正テーブルの形状を示す。
【図７】暗部補正量生成部の構成を示す。
【図８】領域面積率計算部の構成を示す。
【図９】クラスタリング部の構成を示す。
【図１０】予備クラスタリング部の処理フローチャートを示す。
【図１１】図１０のステップ１５６６、１５６７、１５６８の処理フローチャートを示す。
【図１２】クラスタの連続性評価値を説明する図である。
【図１３】クラスタ統合部の処理フローチャートを示す。
【図１４】暗部補正量決定部の構成を示す。
【図１５】補正量算出部の構成を示す。
【図１６】最暗クラスタの補正量制限を説明する図である。
【図１７】仮補正テーブル生成部により作成される補正テーブルを示す。
【図１８】補正量決定部の構成を示す。
【図１９】本発明により作成される補正テーブルを示す。
【発明を実施するための形態】
【００１０】
以下、発明の実施の形態について図面により詳細に説明する。
【実施例１】
【００１１】
図１は、従来のクラスタリングと本発明のクラスタリングの相違を説明する図である。説明を簡単にするために、クラスタリング対象領域に、１つのオブジェクトが存在するものとし、背景をクラスタ０、オブジェクトをクラスタ１としてクラスタ分割したいケースについて図示した。
【００１２】
オブジェクト領域内部にノイズがあり、ノイズに反応して本来発生して欲しくないクラスタ２が発生している（これも説明を簡単にするために、ノイズに反応して発生するクラスタが１つとしているが、実際はもっと多くのクラスタが発生する）。
【００１３】
従来のクラスタリング（ａ）では、前段処理途中でクラスタ０とクラスタ１とクラスタ２が発生し、その後の前段処理では常に各画素と３つのクラスタ代表値との距離を計算することになる。
本発明のクラスタリング（ｂ）では、前段処理途中でクラスタ２をクラスタ１に統合するので、統合後の前段処理では各画素と２つのクラスタ代表値との距離の計算を行えば良い。
【００１４】
図２は、本発明の実施例の構成を示す。輝度変換部１０は、ビットマップ形式の入力画像データの各画素のＲＧＢ値を、次式で輝度Ｙに変換する。
Ｙ＝０．３０×Ｒ＋０．５９×Ｇ＋０．１１×Ｂ
ヒストグラム作成部１１は、輝度Ｙのヒストグラムを作成する。ＲＧＢが０〜２５５の各８ｂｉｔの値を持つ場合で説明すると、Ｙも０〜２５５の値を持つことになる。
【００１５】
閾値決定部１２は、作成したヒストグラムに基づき、画像内における被写体領域、暗部領域、ハイライト領域を判定するための閾値ｔｈ１，ｔｈ２を求める。図３（ａ）は、ヒストグラムの例を示す。閾値ｔｈ１はハイライト領域と被写体領域の境界に該当する閾値、閾値ｔｈ２は被写体領域内における暗部領域とその他の領域の境界に該当する閾値である。図３（ｂ）は、画像を領域判定した結果の一例を示す。上空部分がハイライト領域、被写体である建築物の影領域であって、何が写っているか視認困難な部分が暗部領域、それ以外の被写体部分が暗部領域以外の被写体領域として領域判定されている。閾値決定部１２では、このような領域判定を行うための閾値ｔｈ１，ｔｈ２を決定する。
【００１６】
図４（ａ）は、閾値決定部１２の構成を示す。ヒストグラム形状から適応的に背景と対象物を分離する二値化閾値を求める判別分析法を２回使用して閾値を決定する。
【００１７】
図４（ｂ）は、判別分析法を説明する図である。簡単に説明すると、ヒストグラムの入力の最小値ｓｔ〜閾値Ｔまでを一つのクラス、閾値Ｔ〜入力の最大値ｅｎまでを一つのクラスとして、判別分析法の評価値である（クラス間分散／クラス内分散）が最大になる閾値Ｔを求めることで、背景と対象物がよく分離され（即ちクラス間分散が大きい）、かつ、背景内および対象物内がよくまとまっている（即ちクラス内分散が小さい）二値化閾値を求める方法である。
【００１８】
判別分析法を用いることにより、分析範囲内における（局所的ではなく大局的な）谷位置を探すことができる。なお、判別分析法は、谷位置に該当する閾値を探すための手段として適切であるため、本実施例では判別分析法を使用した例を提示するが、判別分析法に近い精度で画像に対して適応的に谷位置を探すことができる方法であれば他の方法でも構わない。
【００１９】
判別分析法１２０では、ヒストグラムの入力値の最小値から最大値までを分析範囲として（図５の分析範囲１）判別分析法を適用し、閾値ｔｈ１を求める。判別分析法１２１では、ヒストグラムの入力値のうち最小値から閾値ｔｈ１までの暗い側を分析範囲として（図５の分析範囲２）判別分析法を適用し、閾値ｔｈ２を求める。
【００２０】
画像サンプリング部３０は、使用する画像データの画素数が大きすぎると処理に時間がかかり、また性能面でも解像度が高すぎるとノイズの影響から階調補正のための補正量が正確に求められないことがあるので、画像が所定サイズよりも大きい場合には、画像を平均値でサンプリングする。例えば、長辺が６４０画素よりも大きい場合に、サンプリングを実施し、長辺の画素数が６４０の３倍の画像が入力された場合には、３×３画素毎に平均値を求めてサンプリング画像の画素値とする。
【００２１】
階調補正テーブル作成部１９は、補正量決定部１８が決定した最終的な補正量Δに応じて階調補正テーブルを生成する。入力画像データや抽出した色情報等に基づき、暗部補正量生成部１５は、暗部領域の視認性向上に着目した補正量を生成し、ハイライト補正量生成部１６は、ハイライト領域の階調つぶれ抑制に着目した補正量を生成し、補正量決定部１８は、最終的な補正量Δを決定する。
【００２２】
図６は、最終的に作成する補正テーブルの形状を示したものである。補正テーブルは輝度Ｙの変換テーブルとする。制御点は、始点０と終点２５５以外では、入力Ｙ＝ｔｈ１，ｔｈ２，Ｙａの３点であり、各区間内では直線形状とする。制御点ｔｈ１とｔｈ２は前述の閾値決定部１２から出力される閾値であり、制御点Ｙａは後述の暗部補正量生成部１５から出力される暗部領域内の制御点である。補正量Δは、制御点Ｙａにおける入力Ｙに対する出力Ｙの増加分を表したものである。暗部領域における０≦入力Ｙ＜Ｙａの傾きα１は、ＹａとΔにより決まる。制約条件として、暗部領域以外の被写体領域に該当するｔｈ２≦入力Ｙ＜ｔｈ１で、傾きα３を１にして階調性を保存し、Ｙａ≦入力Ｙ＜ｔｈ２は区間境界で傾きが急激に変化することを防止するため傾きα２を傾きα１とα３の中間とする。これにより、３つの制御点と補正量Δが決まれば、補正テーブル全体が決まる。また、３つの制御点が決まっていれば、もう一つの情報は補正量Δでなくα４であっても、あるいは補正テーブルが通るどこか一点の入力と出力のデータセットであっても、上記制約条件から補正テーブル全体を決定することが可能である。
【００２３】
階調補正部２０は、生成した補正テーブルを基に、入力画像データの各画素に対して階調補正を施す。ＲＧＢから輝度変換により輝度Ｙを算出し、算出した輝度Ｙを入力として補正テーブルを参照して出力Ｙを求め、ＲＧＢの各信号に対して（出力Ｙ／入力Ｙ）を乗算したものを階調補正後のＲＧＢとする。
【００２４】
図７は、暗部補正量生成部１５の構成を示す。クラスタリング部１５３は、領域判定結果から暗部領域の画素であるか否かの情報を取得し、色変換部１５２でＬａｂに変換したサンプリング画像データを入力として、クラスタリングを行う。
【００２５】
暗部領域判定部１５０は、サンプリング画像の各画素が暗部領域に属するか否かを、閾値ｔｈ２に基づき判定する。サンプリング画像のＲＧＢ値から輝度Ｙを求め、輝度Ｙを閾値ｔｈ２と比較する。
・Ｙ＜ｔｈ２、かつ、Ｍａｘ（Ｒ，Ｇ，Ｂ）−Ｍｉｎ（Ｒ，Ｇ，Ｂ）＜５０ならば、暗部領域の画素であると判定する。
【００２６】
暗部領域の画素の判定条件にＭａｘ（Ｒ，Ｇ，Ｂ）−Ｍｉｎ（Ｒ，Ｇ，Ｂ）＜５０を加えているのは、彩度が比較的高く、視認可能な領域を暗部から除外して判定するためである。
【００２７】
領域面積率計算部１５１では、被写体領域内に占める暗部領域の比率を暗部面積率Ｐｄとして求める。図８は、領域面積率計算部１５１の構成を示す。被写体画素数計数部１５１０は、ヒストグラムと閾値ｔｈ１から、被写体領域の画素数Ｎａを計数する。被写体領域の画素数はヒストグラムにおける０≦Ｙ＜ｔｈ１の画素数を全て足し合わせることで求められる。同様に、暗部画素数計数部１５１１は、ヒストグラムと閾値ｔｈ２から、暗部領域の画素数Ｎｃを計数する。暗部領域の画素数はヒストグラムにおける０≦Ｙ＜ｔｈ２の画素数を全て足し合わせることにより求められる。
暗部面積率計算部１５１２では、被写体領域における暗部領域の面積率Ｐｄを次式で求める。
Ｐｄ＝Ｎｃ／Ｎａ
【００２８】
図７に戻り、色変換部１５２は、クラスタリングで色差計算を行うため、ＲＧＢで表されている画素値をＬ＊ａ＊ｂ＊に変換しておく。
【００２９】
図９は、クラスタリング部１５３の構成を示す。予備クラスタリング部１５６は、色差に応じて１つ以上のクラスタに分割し（前段処理）、その後、クラスタ統合部１５７では、画素数の少ないクラスタを他のクラスタに統合する（後段処理）。
【００３０】
なお、本実施例では、クラスタ代表値はクラスタの平均Ｌ＊ａ＊ｂ＊であり、各クラスタのクラスタ代表値との距離は平均Ｌ＊ａ＊ｂ＊間の色差に該当する。
【００３１】
図１０は、予備クラスタリング部１５６の処理フローチャートである。注目画素のＬａｂを順次入力し（ステップ１５６１）、クラスタリングを行う。画像先端からスタートして初めて暗部領域の画素が入力された時点では、クラスタ数Ｎが初期化されてＮ＝０にセットされた状態であるため（ステップ１５６０）、色差による条件分岐（ステップ１５６５）で“Ｎｏ”の方に進み、新規クラスタの追加（ステップ１５６７）において、注目画素を唯一の所属画素とする新規クラスタを追加する（Ｎ＝１になる）。
【００３２】
その後は、順次入力される注目画素のＬ＊ａ＊ｂ＊値に対して、暗部領域の画素であれば（ステップ１５７０でＹｅｓ）、各クラスタの平均Ｌ＊ａ＊ｂ＊との色差を求め（ステップ１５６３）、その中で色差最小のクラスタ番号ｊと色差ｄＥ＿ｍｉｎの組を抽出する（ステップ１５６４）。色差による条件分岐（ステップ１５６５）で、色差ｄＥ＿ｍｉｎが予め設定された閾値ｄＥ＿ｔｈ以下であれば“Ｙｅｓ”の方に進み、クラスタｊに注目画素を追加する（ステップ１５６６）。色差による条件分岐（１５６５）で色差ｄＥ＿ｍｉｎが予め設定された閾値ｄＥ＿ｔｈより大きければ“Ｎｏ”の方に進み、その時点でのクラスタ数Ｎが予め設定されたクラスタ数上限値Ｎ＿ｍａｘ未満であれば新規クラスタを追加し（ステップ１５６７）、クラスタ数Ｎが上限値Ｎ＿ｍａｘに達していれば、既存クラスタの統合と新規クラスタの追加を行う（ステップ１５６８）。
【００３３】
新規クラスタを追加するか否かの境界色差を表しているのがｄＥ＿ｔｈであり、暗部の何が写っているかはっきり視認できない領域を対象としていることを考慮してｄＥ＿ｔｈ＝３くらいの小さい値に設定しておくのが適当である。画像後端まで到達して入力するＬａｂデータが無くなった時点で、クラスタリング終了となる。
【００３４】
既存クラスタであるクラスタｊに注目画素を追加する処理（ステップ１５６６）について説明する。図１１（ａ）は、ステップ１５６６の処理フローチャートである。クラスタｊの所属画素数ｎ（ｊ）を１つカウントアップし（ステップ１５６９）、平均Ｌ＊ａ＊ｂ＊を再計算する（ステップ１５７０）。
（再計算後の平均Ｌ＊）＝（（再計算前の平均Ｌ＊）×（ｎ（ｊ）−１）＋（注目画素のＬ＊））／ｎ（ｊ）
（再計算後の平均ａ＊）＝（（再計算前の平均ａ＊）×（ｎ（ｊ）−１）＋（注目画素のａ＊））／ｎ（ｊ）
（再計算後の平均ｂ＊）＝（（再計算前の平均ｂ＊）×（ｎ（ｊ）−１）＋（注目画素のｂ＊））／ｎ（ｊ）
【００３５】
次に、クラスタｊの連続性評価値ｌｅｎ（ｊ）を再計算する（ステップ１５７１）。連続性評価値の定義について説明する。クラスタの連続性評価値は、そのクラスタに属する各画素の連続性評価値の平均で定義する。各画素の連続性評価値は次のように定義する。図１２（ａ）の注目画素ｅの連続性評価値は、近傍４画素（ａ，ｂ，ｃ，ｄ）の所属クラスタを参照して求める。
「注目画素ｅの連続性評価値＝近傍４画素（ａ，ｂ，ｃ，ｄ）のうち注目画素ｅと同じクラスタに属する画素数」
つまり、各画素の持つ連続性評価値は０〜４の値になる。クラスタの連続性評価値も、その平均値であるので０〜４の値になり、領域的に塊で存在するクラスタは評価値が３前後の大きい値になり、点在するクラスタは０〜１前後の小さい値になる。
クラスタｊの連続性評価値ｌｅｎ（ｊ）の再計算は、以下の式で行える。
（再計算後のｌｅｎ［ｊ］）＝（（再計算前のｌｅｎ［ｊ］）×（ｎ（ｊ）−１）＋（注目画素の連続性評価値））／ｎ（ｊ）
【００３６】
図１２（ｂ）〜（ｄ）は、クラスタ分割結果の一例に対する連続性評価値を示す。図１２（ｂ）のクラスタ分割結果の例では、クラスタ１に分割される領域内に、ノイズ部分と思われるクラスタ２が点在している。その時、クラスタ１の連続性評価値は２．８１で比較的大きく、領域的な連続性が高い（ｃ）。クラスタ２の連続性評価値は０．２５で比較的小さく、領域的な連続性が低い（ｄ）。この連続性評価値に基づきクラスタ統合を行うので、クラスタ２はクラスタ統合の対象になりやすい。
【００３７】
新規クラスタの追加（ステップ１５６７）について説明する。図１１（ｂ）は、ステップ１５６７の処理フローチャートである。クラスタ数をカウントアップし（ステップ１５７２）、クラスタＮの所属画素数を初期化してｎ（Ｎ）＝１に設定し（ステップ１５７３）、平均Ｌ＊ａ＊ｂに注目画素のＬ＊ａ＊ｂを設定する（ステップ１５７４）。連続性評価値も初期化してｌｅｎ（Ｎ）＝０に設定する（ステップ１５７５）。
【００３８】
既存クラスタの統合＆新規クラスタの追加（ステップ１５６８）について説明する。図１１（ｃ）は、ステップ１５６８の処理フローチャートである。その時点での各クラスタの連続性評価値を比較し、連続性評価値が最も小さいクラスタを選択する（以降、該当クラスタをクラスタＸと表記する）（ステップ１６００）。クラスタＸが統合対象のクラスタになる。クラスタＸと他のクラスタの平均Ｌ＊ａ＊ｂ＊間の色差を計算し（ステップ１６０１）、色差最小のクラスタを抽出する（以降、該当クラスタをクラスタＹと表記する）（ステップ１６０２）。クラスタＹが統合先のクラスタになる。
【００３９】
クラスタＸをクラスタＹへ統合すべく、クラスタＹの所属画素数ｎ（Ｙ）にクラスタＸの所属画素数ｎ（Ｘ）を加算し（ステップ１６０３）、クラスタＹの平均Ｌ＊ａ＊ｂ＊を再計算する（ステップ１６０４）。
（クラスタＹの再計算後の平均Ｌ＊）＝（（クラスタＹの再計算前の平均Ｌ＊）×（ｎ（Ｙ）−ｎ（Ｘ））＋（クラスタＸの平均Ｌ＊）×ｎ（Ｘ））／ｎ（Ｙ）
（クラスタＹの再計算後の平均ａ＊）＝（（クラスタＹの再計算前の平均ａ＊）×（ｎ（Ｙ）−ｎ（Ｘ））＋（クラスタＸの平均ａ＊）×ｎ（Ｘ））／ｎ（Ｙ）
（クラスタＹの再計算後の平均ｂ＊）＝（（クラスタＹの再計算前の平均ｂ＊）×（ｎ（Ｙ）−ｎ（Ｘ））＋（クラスタＸの平均ｂ＊）×ｎ（Ｘ））／ｎ（Ｙ）
【００４０】
次に、クラスタＸを消去して新規クラスタを追加すべく、クラスタＸを新規クラスタで置換する。クラスタＸの所属画素数を初期化してｎ（Ｘ）＝１に設定し（ステップ１６０５）、平均Ｌ＊ａ＊ｂ＊に注目画素のＬ＊ａ＊ｂ＊を設定する（ステップ１６０６）。連続性評価値も初期化してｌｅｎ（Ｘ）＝０に設定する（ステップ１６０７）。
【００４１】
図１０のクラスタ統合部１５７の処理を説明すると、予備クラスタリング部１５６で分割されたクラスタのうち、ある程度画素数が少ないクラスタは被写体を有意な塊単位で抽出する上において不要または重要性が低いクラスタである。
【００４２】
図１３は、クラスタ統合部１５７の処理フローチャートである。各クラスタを順次見ていき、クラスタの画素数が所定閾値ｎ＿ｔｈより小さいか否かを判定し（ステップ１６１２）、小さい場合は注目クラスタｉの平均Ｌ＊ａ＊ｂ＊と他のクラスタの平均Ｌ＊ａ＊ｂ＊との色差を求め（ステップ１６１３）、他のクラスタ全てに対して求めた色差のうち最小のものに該当するクラスタ番号ｊを抽出し（ステップ１６１４）、クラスタｉをクラスタｊに統合する（ステップ１６１５）。クラスタｊの画素数にクラスタｉの画素数を加算し、クラスタｉの画素数を０に変更する。
【００４３】
統合するクラスタの画素数境界である閾値ｎ＿ｔｈは、暗部領域の画素数に対して例えば１５％（１０％〜２０％程度に設定するのが適当）の画素数に相当する値を画像毎に求めて、それを閾値とする。
【００４４】
図７に戻り、判断部１５４は、クラスタ数に応じて階調補正を行うか否かを判断する。クラスタ数が１であれば階調補正を行わないと判断し、クラスタ数が１以外であれば階調補正を行うと判断する。これにより、夜空を背景に花火を撮影した画像のように暗部に該当する夜空に何もオブジェクトが潜んでおらず、明るく補正する必要がない画像が入力された場合に、階調補正を行わないと判断して処理することができる。
【００４５】
図１４は、暗部補正量決定部１５５の構成を示す。判断部１５４が階調補正を行わないと判断した場合は、選択部１５９は、Δ１＝Δ１ａ（＝０）を補正量として選択出力することにより、実質的に階調補正を無効にする。判断部１５４が階調補正を行うと判断した場合は、補正量算出部１５８が算出した補正量Δ１ｂを選択して、Δ１＝Δ１ｂを補正量として出力する。
【００４６】
図１５は、補正量算出部１５８の構成を示す。第一のクラスタ抽出部１５８０は、クラスタリング結果から各クラスタの画素数を比較して画素数が最も多いクラスタとその次に多いクラスタを抽出する。２つのクラスタのうち明度が高い方をクラスタＡ、明度が低い方をクラスタＢと表記する。色差計算部１５８２では、クラスタＡとクラスタＢの補正前の平均Ｌａｂ同士の色差ｄＥ１を計算しておく。補正量生成部１５９２は補正量Δ１ｂを設定して、仮補正テーブル生成部１５９１は補正量に応じた仮補正テーブルを作成する。階調補正部１５８５は仮補正テーブルを用いた階調補正を、クラスタＡの平均Ｌａｂを色変換部１５８４でＲＧＢに変換したＲＧＢ＿ａと、クラスタＢの平均Ｌａｂを同じくＲＧＢに変換したＲＧＢ＿ｂに対して行い、階調補正後の値を色変換部１５８６で再度Ｌａｂ信号に変換する。色差計算部１５８７では、クラスタＡとクラスタＢの補正後の平均Ｌａｂ同士の色差ｄＥ２を計算する。色差比計算部１５８８は補正前の色差ｄＥ１と補正後の色差ｄＥ２の比率を計算して求める。
【００４７】
第二のクラスタ抽出部１５８１では、クラスタリング結果から最も暗いクラスタを抽出する。最も暗いクラスタをクラスタＣと表記する。ちなみに、画像によってはクラスタＢとクラスタＣが同じクラスタを指すこともあるが、それでも構わない。階調補正部１５８５は仮補正テーブルを用いた階調補正を、クラスタＣの平均Ｌａｂを色変換部１５８４でＲＧＢに変換したＲＧＢ＿ｃに対して行い、階調補正後の値を色変換部１５８６で再度Ｌａｂ信号に変換する。
【００４８】
暗部補正量判定部１５８９では、以下の終了条件１または終了条件２を満たせば、その時点での補正量Δ１ｂを出力して終了する。どちらの終了条件も満たさなければ、補正量生成部１５９２は変更した補正量を発生させ、終了条件を満足するまで処理を繰り返す。
［終了条件１］クラスタＡとクラスタＢの補正前後の色差比が、色差比目標値設定部１５８３に設定された目標値Ｘｄ以上である。
［終了条件２］クラスタＣの階調補正後の平均Ｌが、最暗クラスタの明度上限設定部１５９０に設定された上限値Ｌｃ＿ｔｈ以上である。
【００４９】
画素数が最も大きいクラスタと次に大きいクラスタの色差が補正前のＸ倍になるように補正するということは、他の面積の狭いクラスタ同士の色差比に着目して補正するよりも視認性が向上したことが観察者に認識されやすく、非常に効果的である。また、最も暗いクラスタが明るく補正されすぎないように補正量を制限することは、暗部ノイズが目立つ副作用を防止するのに有効である。
【００５０】
図１６は、最暗クラスタの補正量制限を説明する図である。（ａ）は暗部を示し、（ｂ）は暗部を拡大した図である。図１６のＹｃとＹｃ＿ｔｈは最暗クラスタの補正量制限をわかりやすく表現したものであり、ＹｃがクラスタＣの補正後の輝度を表しており、Ｙｃ＿ｔｈは上限値を輝度で表している。
【００５１】
補正量生成部１５９２は、Δ１ｂ＝０を初期値として、補正量生成の要求がある度に、Δ１ｂに＋１したものを次の補正量として発生させる。仮補正テーブル生成部１５９１では、ＲＧＢ＿ａを輝度変換して求めた輝度Ｙａを制御点として、図１６のような補正テーブルを作成する。制御点ＹａはクラスタＡ（面積が大きい２つのクラスタのうち明るい方）の輝度に該当する。制御点Ｙａにおける出力がＹａ＋Δ１ｂになるように補正テーブルを作成し、暗部領域以外は暗部補正量生成部１５で使用されず、どのように設定してもよいので、図１６のように、Ｙａ≦入力Ｙ＜２５５は直線で結んでおけば良い。
【００５２】
色差比目標値設定部１５８３では、暗部面積率Ｐｄに応じて色差比の目標値Ｘｄ＝３．５×Ｐｄを算出する。算出式は数十枚のサンプル画像を用意してどのくらいに設定すれば、ほぼ全ての画像（少なくとも用意したサンプルの８割）で適正な明るさに補正されるかを主観評価結果から導出したものである。被写体における暗部領域の占める割合が大きいほど暗部の視認性向上を重視した方が高評価を得る傾向があり、暗部領域の占める割合が小さいほど暗部以外の被写体画質を重視した方が高評価が得られ、暗部の視認性向上に対する要求レベルが下がる傾向があった。
【００５３】
最暗クラスタの明度上限設定部１５９０では、Ｌｃ＿ｔｈが１５くらいの値（１０〜１８の間）に設定されるようにしておくのが適当である。これは予め決めておいた固定値でよい。
【００５４】
図２に戻り、ハイライト補正量生成部１６では、補正テーブルのハイライト領域における傾きα４’を補正量として求め、出力する。これはハイライトが階調補正によって白飛びするのを抑制するために行う処理である。サンプリング画像の各画素を閾値ｔｈ１と比較し、閾値ｔｈ１以上であればハイライト領域の画素であると判定する。更に、ハイライト領域のＲＧＢ値全てが２５５である画素（白画素）を除外した領域を対象として、対象領域における飽和度が予め設定された飽和度上限値Ｘｈ以下になることを終了条件とし、終了条件を満たすα４’を求める。
【００５５】
図１７のように、ｔｈ１を制御点とし、ハイライト領域で傾きがα４’になる仮補正テーブルを作成し、傾きα４’＝０からはじめてα４’を徐々に大きくしていく。ハイライト領域以外はハイライト補正量生成部１６で使用されないので、仮補正テーブルでは図１７のように、０≦入力Ｙ＜ｔｈ１を直線で結んでおけば良い。
【００５６】
飽和度は、対象領域における飽和画素の割合である。飽和画素は、階調補正前後のＲＧＢ値を参照し、ＲＧＢ３信号のうち補正後の値が（２５５−ｘ１）以上に飽和した信号数が、補正前に２５５に飽和している信号数よりも多ければ、階調補正によって飽和した画素（＝飽和画素）であると判断する。ｘ１は（２５５−ｘ１）が目視でほぼ飽和していると認定されるくらいの値、ｘ１＝２０くらいに設定しておくのが適当である。
【００５７】
図２に示す補正量決定部１８の構成を、図１８に示す。補正量Δ２算出部１８０では、最終的に求める図６の階調補正テーブルと同様に、図１９に示した関係を使って、ハイライトの傾きがα４’である場合の補正量Δ２を求める。暗部補正量生成部１５で生成された補正量Δ１と、ハイライト補正量生成部１６で生成された傾きα４’から求めた補正量Δ２とを、最小値選択部１８１で比較し、最小のものを選択して出力する（Δ＝ｍｉｎ（Δ１，Δ２））。
【００５８】
以上説明したように、本実施例によれば、クラスタリングの前段処理の中で、予め設定したクラスタ数の上限値を超えないように、新規クラスタの追加だけでなく、既存クラスタの統合を随時行うため、処理を高速化することができる。また、連続性評価値に基づき統合対象となるクラスタを選択するため、いずれにしても最終的には不要なクラスタを前段処理の途中の段階で統合することで処理を高速化し、かつ、最終的なクラスタリング後段処理後のクラスタ分割の精度を維持することができる。
【００５９】
本実施例では、前述の通り、画像の暗部領域をクラスタリング対象領域としているため、新規クラスタを追加するか否かの判定条件に当たる色差閾値をｄＥ＿ｔｈ＝３程度の小さい値に設定する必要があった。これは通常画像に対して適用する閾値よりもかなり小さい。また、暗部領域では暗電流の影響もあり比較的大きいノイズが発生しやすい。そのため、暗部領域をクラスタリング対象領域とする場合、本発明が問題としているノイズの起伏に反応してクラスタ数が増加する問題が特に発生しやすく、本発明の効果が非常に大きいと言える（但し、暗部領域のみをクラスタリング対象領域とする場合以外にも、効果の大きさが違うだけで、本発明の効果はある）。
【００６０】
なお、本発明のクラスタ分割結果の適用先の画像処理は、階調補正のみに限定されるものではない。別の適用例を２つ挙げる。
【００６１】
適用例１：
特許文献２と同様に、クラスタ分割結果に基づき減色処理を行い、文字色を一色に統一する際に、本発明のクラスタリング高速化技術を適用する。文字文書原稿をスキャナで読み取ると、例えば黒一色であった文字に色成分が混入して黒一色でなくなる。クラスタ分割し、画素値を所属クラスタの代表値で置換することにより、本来黒一色であった文字を黒一色に再生することができるようになる。
【００６２】
適用例２：
画像の色数や画像の代表色に応じて、画像を分類する際に、本発明のクラスタリング高速化技術を適用する。色数（クラスタ数）や代表色（所属画素数が最大のクラスタ代表値）を画像特徴として含み、画像特徴が近い画像同士を近くに配置分類した画像一覧を表示してユーザーに提示することで、ユーザーが素早く類似画像を見つけられるようになる。
【００６３】
本発明によれば、カラー画像内の各画素を色情報に基づき複数のクラスタに分割するクラスタ分割において、画像内の全画素を一旦クラスタ分割してからクラスタの統合（あるいは分割）行うのではなく、各画素をクラスタ分割する途中段階において、新規クラスタの追加、および、既存クラスタの統合を随時行うため、処理途中でクラスタ数が増えすぎるのを抑え、処理を高速化することができる。
【００６４】
本発明によれば、同一クラスタに属する画素の領域的な連続性を評価する連続性評価値を算出し、既存クラスタの統合は、連続性評価値に基づき、領域的な連続性が低いクラスタを優先して他のクラスタへ統合するため、処理を高速化した上で最終的なクラスタ分割の精度を維持することができる。
【００６５】
本発明によれば、既存クラスタの統合は、新規クラスタの追加によりクラスタの数が予め設定された上限値を超える場合に随時実施するため、処理途中でクラスタ数が予め設定した上限値を超えないように制御することができ、処理を高速化できる。
【００６６】
本発明によれば、新規クラスタの追加は、注目画素が属するクラスタが既存クラスタの中に存在しないと判定された場合に随時実施し、クラスタ数が固定でなく画像に対応したクラスタのみ追加されるため、不要なクラスタとの距離を計算する処理時間が省略され、クラスタ数とクラスタ代表値の初期値に左右されないクラスタ分割結果を得ることができる。
【００６７】
本発明によれば、画像の暗部領域を判定してクラスタ分割を行う対象領域とする場合に対して本発明のクラスタリング高速化技術を適用するため、新規クラスタを追加するか否かの判定条件に当たる色差閾値設定と暗電流の影響からノイズの起伏に反応してクラスタ数が増加する問題が特に発生しやすいケースに対して特に、本発明の処理の高速化（かつクラスタ分割の精度維持）効果を発揮することができる。
【００６８】
本発明は特に高速化に効果があるため、その点を強調して説明したが、実装上はメモリを節約できる効果もある。従来方式（特許文献２のクラスタリング）では、クラスタ数がいくつまで増えるかわからないので、各クラスタのデータ（所属画素数、代表値）を保存するためのメモリを予めかなり余裕を持って確保しておくか、あるいは、動的に確保する必要があった。一方、本発明によれば、クラスタ数が増えすぎないように（予め設定した上限値を超えないように）制御できるため、各クラスタのデータを保存するためのメモリを節約できる。
【００６９】
本発明は、前述した実施例の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（ＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行することによっても達成される。この場合、記憶媒体から読出されたプログラムコード自体が前述した各実施例の機能を実現することになる。プログラムコードを供給するための記憶媒体としては、例えば、ハードディスク、光ディスク、光磁気ディスク、不揮発性のメモリカード、ＲＯＭなどを用いることができる。また、コンピュータが読出したプログラムコードを実行することにより、前述した実施例の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部または全部を行い、その処理によって前述した各実施例の機能が実現される場合も含まれる。さらに、記憶媒体から読出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した各実施例の機能が実現される場合も含まれる。また、本発明の実施例の機能等を実現するためのプログラムは、ネットワークを介した通信によってサーバから提供されるものでも良い。
【符号の説明】
【００７０】
１０  輝度変換部
１１  ヒストグラム作成部
１２  閾値決定部
１５  暗部補正量生成部
１６  ハイライト補正量生成部
１８  補正量決定部
１９  階調補正テーブル作成部
２０  階調補正部
３０  画像サンプリング部
【先行技術文献】
【特許文献】
【００７１】
【特許文献１】特許第４１６４９０７号公報
【特許文献２】特開２００６−２２９２８０号公報
【図１】
2010183416.tif 000003
【図２】
2010183416.tif 000004
【図３】
2010183416.tif 000005
【図４】
2010183416.tif 000006
【図５】
2010183416.tif 000007
【図６】
2010183416.tif 000008
【図７】
2010183416.tif 000009
【図８】
2010183416.tif 000010
【図９】
2010183416.tif 000011
【図１０】
2010183416.tif 000012
【図１１】
2010183416.tif 000013
【図１２】
2010183416.tif 000014
【図１３】
2010183416.tif 000015
【図１４】
2010183416.tif 000016
【図１５】
2010183416.tif 000017
【図１６】
2010183416.tif 000018
【図１７】
2010183416.tif 000019
【図１８】
2010183416.tif 000020
【図１９】
2010183416.tif 000021