JPH09106458A

JPH09106458A - 画像処理方法

Info

Publication number: JPH09106458A
Application number: JP7263962A
Authority: JP
Inventors: Hideaki Kobayashi; 小林　　秀章
Original assignee: Dai Nippon Printing Co Ltd
Current assignee: Dai Nippon Printing Co Ltd
Priority date: 1995-10-12
Filing date: 1995-10-12
Publication date: 1997-04-22
Also published as: KR970022570A; KR100386870B1

Abstract

(57)【要約】【課題】初期値を与えることなく、個々の画像に応じ
て適切な数のクラスタに分けることができる画像処理方
法を提供する。【解決手段】カラー画像を構成する各画素データを色
空間に写像した際に、各色に対する画素の出現頻度とし
て得られる色ヒストグラムを作成し、作成した色ヒスト
グラムに存在する頻度のピークを抽出し、ピークを高い
順に並べ、その順に抽出したピークから、定距離ｄ₀以
内の近傍に存在する降下可能点を探索し、探索した降下
可能点から、定距離ｄ₀以内の近傍に存在する次の降下
可能点を探索する如く、降下可能点探索を繰り返し、得
られる各降下可能点により特定される範囲を、前記頻度
のピークが属するクラスタとして色ヒストグラムをクラ
スタ分けする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、画像処理方法、特
に画像の切り抜きや、画像認識等に応用されるカラー画
像の領域分割に適用して好適な、画像処理方法に関す
る。

【０００２】

【従来の技術】従来、例えば、印刷製版での画像処理に
際して、画像中の各物体に対応する特定領域の抽出（い
わゆる切り抜き）や、領域選択型の色調修正等のために
カラー画像の領域分割が行われている。

【０００３】このようなカラー画像の領域分割法の代表
的なものの１つとして、色空間上でのクラスタ分けがあ
る。これは、図１４に概念的に示すように、画像平面内
の画素を、例えばＲＧＢの色空間（特徴空間）に写像
し、その空間上でクラスタ分けすることにより、クラス
タ毎に各画素を分類すると共に、各画素に１、２、３等
のクラスタ番号を付けるラベル付けを行い、その後これ
らの色空間データを画像平面に逆写像することにより、
領域分割画像を得る方法である。

【０００４】こうしたカラー画像データのクラスタ分け
（領域分割）に関する技術の１つに、Ｋ平均アルゴリズ
ムあるいは非階層的クラスタリングと称されるものがあ
る（長尾真著「画像認識論」コロナ社、田村秀行著「コ
ンピュータ画像処理入門」総研出版）。この技術は、初
めに分けるべきクラスタ数Ｋを決めておいて、データが
分布する色空間上に仮のクラスタ中心としてＫ個の代表
点を適当にばらまいておき、次いで、データ分布の各点
がどの代表点に近いかでクラスタ分けし、分けられた各
クラスタの平均点を改めて代表点とし、この代表点で再
びクラスタ分けするという手順を、反復による変化が起
こらなくなる（収束する）まで繰り返することにより、
クラスタ分けする方法である。

【０００５】ところが、上述したＫ平均アルゴリズム法
は、初期値の与え方が適切でないと精度の良い結果が得
られない上に、クラスタ数Ｋが固定されているため、適
切なクラスタ数が当初から分かっていなければならず、
それ故、切り抜き等の画像処理には必ずしも適していな
い。

【０００６】そこで、この方法を改良した方法として、
クラスタの分割と併合を反復することによってクラスタ
の個数をデータに合せて可変とする自己収束型アルゴリ
ズムを採用したＩＳＯＤＡＴＡ（Ｉterative Ｓelf Ｏ
rganizing Ｄata ＡnalysisＴechniques Ａ）法がある
（前記「画像認識論」１２４頁に記載）。

【０００７】しかしながら、前記Ｋ平均アルゴリズムあ
るいは自己収束型アルゴリズムのいずれの方法において
も、前述した如く、クラスタ分けの精度が、初期値の与
え方に依存しているため、初めにばらまく代表点の取り
方によってクラスタ分けの結果が変化するので、精度の
良いクラスタ分けをするためには適切な初期値を与える
必要があるが、これが難しいという問題がある。

【０００８】そこで、本出願人は、これら問題点を解消
するべく、初期値の与え方によってデータ処理の結果が
変化せず、色空間における画素データの精度の良いクラ
スタ分けを可能にする画像処理方法として、色空間を平
面で切り分ける方法を、特開平４−６１５５８に提案し
ている。

【０００９】

【発明が解決しようとする課題】しかしながら、色ヒス
トグラムにおける個々のクラスタは、例えばＲＧＢ座標
系の色空間であれば、図１５に示すように、原点と座標
（１，１，１）とを通り、且つ原点の黒から白に至るベ
クトルである、いわゆるグレースケールの周囲に配され
たバナナ形状に曲がった分布をなす傾向がある。従っ
て、上記公報で提案した色空間を平面で切り分ける方法
には、画像上で同一領域の画素が、色空間上で常に特定
の場所に局在している場合にはうまくクラスタ分けでき
るが、実際の画像ではそうならないことも多いため、色
空間を平面で切り分けること自体が望ましくない場合が
あり、その上、計算によって求めた平面が必ずしも望ま
しいものではない場合もあり得ることが明らかなにっ
た。

【００１０】本発明は、前記従来の問題点を解決するべ
くなされたもので、個々のカラー画像に応じて適切な数
のクラスタに正確にクラスタ分けすることができる画像
処理方法を提供することを課題とする。

【００１１】

【課題を解決するための手段】本発明は、カラー画像を
構成する各画素データを色空間に写像した際に、各色に
ついての画素の出現頻度として得られる色ヒストグラム
を作成し、作成した色ヒストグラムに存在する頻度のピ
ークを抽出し、抽出したピークから、定距離ｄ ₀以内の
近傍に存在する降下可能点を探索し、探索した降下可能
点から、定距離ｄ₀以内の近傍に存在する次の頻度の降
下可能点を探索する如く、降下可能点の探索を繰り返
し、得られた各降下可能点により特定されるテリトリ
を、前記頻度のピークが属するクラスタとして、色ヒス
トグラムをクラスタ分けするこにより、前記課題を解決
したものである。

【００１２】即ち、色ヒストグラムの極大点（普通は複
数ある）を抽出することにより、出現頻度が際立って高
い色を抽出することができる。従って、これら各極大点
を各クラスタの中心として、各クラスタ中心から頻度の
坂を下り、クラスタ中心を山頂とする山の裾野の範囲を
求め、これを各クラスタの範囲とすることにより、予め
クラスタ数を初期値として与えることなく、自ずと適切
な数のクラスタに分けることができる。

【００１３】

【発明の実施の形態】以下、図面を参照して、本発明の
実施の形態について説明する。なお、以下の説明では、
後出の式やその説明文に用いられるεは、便宜上、左辺
が右辺に属することを表わすエレメント記号の代りに用
いている。

【００１４】一般に、クラスタ分け方法として満たすべ
き要件としては、次の１〜６を挙げることができる。１．クラスタ数を予め与えなくとも、適切な数にクラス
タ分けできること。２．ヒストグラムの次元によらず適用できること。３．多様な分布形状のヒストグラムに適用できること。
言い換えれば、各クラスタをなす分布の形状に正規分布
のような仮定を設ける必要がないこと。４．色の出現頻度のムラによるヒストグラムの細かなガ
タ付きに左右されず、分布の形状を大きく捕らえてクラ
スタ分けできること。５．結果として得られるクラスタ数の多寡を調整するた
めに予め設定しておくパラメータの数が多くないこと。６．計算量及びメモリ容量が実用的な範囲内であるこ
と。

【００１５】本発明に係る一実施形態では、上記１〜６
の要件を実現するために、カラー画像を構成する各画素
データを色空間に写像した際に、各色についての画素の
出現頻度として得られる色ヒストグラムを作成し、作成
した色ヒストグラムに存在する頻度のピークを抽出し、
抽出したピークから、定距離ｄ₀以内の近傍に存在する
降下可能点を探索し、探索した降下可能点から、定距離
ｄ₀以内の近傍に存在する次の降下可能点を探索する如
く、降下可能点の探索を繰り返し、得られた各降下可能
点により特定される範囲を、前記頻度のピークが属する
クラスタとして、色ヒストグラムをクラスタ分けする。

【００１６】又、本実施形態では、点ｘから降下可能点
ｙを探索する際、該点ｘから定距離ｄ₀以内の近傍に存
在する点ｙについて、点ｘにおける頻度が、該点ｙから
定距離ｄ₀以内の近傍に存在する全ての点ｚの中で最大
であるときに、この点ｙを点ｘからの降下可能点である
と判定すると共に、上記定距離ｄ₀を色ヒストグラムを
離散格子で表現する際の隣接格子間最小長さを超える値
で設定し、且つ、上記頻度のピークを、任意の色につい
て設定される定距離ｄ₀以内の近傍に存在する色の極大
頻度として抽出するようにした。

【００１７】始めに、本実施形態で用いられる用語等の
基本的な概念と、色ヒストグラムをクラスタ分けする意
味等について説明する。

【００１８】画像としては風景や人物等の写真原稿をカ
ラースキャナで読み取ったデジタル・カラー画像を対象
とする。デジタル・カラー画像とは、２次元に離散格子
状に配列された各画素（pixel ）に対して、３次元又は
４次元の離散的な階調を持った色の値を対応させた関数
である。この色は、（Ｒ，Ｇ，Ｂ）、（Ｃ，Ｍ，Ｙ，
Ｋ）、（Ｌ，ａ，ｂ）、（Ｙ，Ｉ，Ｑ）等で表現され
る。特に、画像が風景や人物等の写真から生成したもの
であるときは、慣用的に自然画像と呼ばれる。

【００１９】今、カラースキャナで読み取った自然画像
の上で領域分割することを考える。ここで領域とは、画
像を構成する画素の集まりであって、視覚的に類似した
色からなり、例えば、「顔の地肌部分」、「髪」、「衣
服」、「服のボタン」といった言葉で表わすことのでき
る、画像の構成単位である。

【００２０】画像を領域分割した結果は、ラベル画像で
表現する。ラベル画像とは、元になる画像の各画素に対
して、１，２，３，・・・といったラベルの数値を対応
させた関数であり、同じラベルの値を持つ画素は同じ領
域に属し、異なるラベルの値を持つ画素が異なる領域に
属することを表現したものである。このラベル画像は、
前記図１４の右上の図に相当する。

【００２１】今、異なる領域に１つの色が共通して現わ
れることがないと仮定する。この仮定は、画像によって
は成り立たないこともある。例えば、白いシャツを着た
人物が、白い壁を背にして立っている場合である。同じ
白という色が壁とシャツという異なった領域に共有され
ることになる。

【００２２】しかし、このような場合を除けば、領域分
割は、色ヒストグラムをクラスタ分けすることによって
なされ得る。色ヒストグラムとは、画像から生成され、
各色に対して、画像上でその色を持つ画素の個数を対応
させた関数である。従って、色ヒストグラムは、３次元
又は４次元の離散格子から、正又は零の整数値への関数
である。

【００２３】以下に詳述するクラスタ分け手法は、色ヒ
ストグラムの定義域の次元によらず適用できる手法であ
る。従って、本手法を適用できる色ヒストグラムには、
１次元を含む一般の次元のものも含まれるが、説明の都
合上、主として３次元の場合を例に採り挙げる。

【００２４】色ヒストグラムをクラスタ分けする目的
は、色ヒストグラムの定義域をグループ分けし、各グル
ープの色の範囲が、画像を領域分割したときの各領域を
構成する色の範囲に対応するようにすることにある。

【００２５】このクラスタ数は、画像によって個々に決
まる値であり、予め分かっていないのが普通である。従
って、クラスタ分け手法は、対象とする画像データに応
じて、クラスタ数が適切に決まるものであることが重要
である。

【００２６】以下、図面に基づいてより具体的な形態の
例を詳細に説明する。

【００２７】本実施形態においては、図１に示したメイ
ンループのフローチャートに従って、色ヒストグラムの
作成（ステップ１０１）、定距離ｄ₀の設定（ステップ
１０２）、色ヒストグラムのｄ₀近傍に関するピーク抽
出（ステップ１０３）、色ヒストグラムのピークをソー
ト（高→低）（ステップ１０４）、各ピークのｄ₀近傍
に関するテリトリ抽出（ステップ１０５）、取りこぼし
の拾い集め（ステップ１０６）の各基本操作を実行する
ことにより、カラー画像のクラスタ分けが行われる。な
お、これら各基本操作については、後に詳述する。

【００２８】本実施形態では、このように色ヒストグラ
ムをクラスタ分けした場合の最終的な結果は、ラベル・
ヒストグラムの形で記述する。ここで、ラベル・ヒスト
グラムとは、色ヒストグラムの各要素に対して、その要
素はどのクラスタに属するかを示すラベルを対応付けた
表である。言い換えれば、色ヒストグラムが、各色を、
それぞれの出現頻度へ対応付けたものであるのに対し、
ラベル・ヒストグラムは、各色を、それぞれ該当するク
ラスタ番号へ対応付けたものである。

【００２９】このようなクラスタの記述には、次の
（１）〜（３）の意味がある。（１）出現頻度が０でない全ての色にラベル付けをす
る。（２）同一のラベルを付けられた色は、画像上で視覚的
に意味付けできる同一領域に属する。換言すれば、この
ような同一領域では、その領域を構成する色に同じラベ
ルが付けられる。（３）異なるラベルが付けられた色は、画像上で視覚的
に区別されるべき別々の領域に属する。換言すれば、こ
のような別々の領域では、それぞれの領域を構成する色
に異なるラベルが付けられる。

【００３０】なお、ここで、画像上で視覚的に意味付け
できる領域とは、前述した視覚的に類似した色からなる
領域に相当し、例えば、「顔の地肌部分」、「髪」、
「衣服」、「服のボタン」といった言葉で称することが
できる画像領域の構成単位である。

【００３１】以下、図１に示したフローチャートの各ス
テップについて、図２〜図４のフローチャート等を参照
しながら詳述する。

【００３２】ステップ１０１の「色ヒストグラムの作
成」は、次のようにして実行される。

【００３３】先ず、クラスタ分けしようとする画像のあ
る領域を入力する。この領域は画像全体でも、矩形領域
でも、又は適当な形状の領域の集まりであってもよい。
次いで、入力した画像領域内に出現している色のヒスト
グラムを作成する。これは、出現可能な各色に対して、
実際にその色が何画素出現したかを記録した表の形で作
成する。

【００３４】なお、上述した色ヒストグラムを作成する
場合、データ量及び後の計算の負荷の都合上、階調数を
減らしておいた方がよい。例えば、色空間をＲＧＢ各版
が２５６階調の３次元空間として、頻度を整数値で４バ
イトとすると、そのままヒストグラムを作成すれば、２
５６×２５６×２５６×４＝６４ＭＢyte のメモリを要
する。計算機によってはこの程度のメモリを取れるもの
もあるが、後の計算が大変なので、避けるべきである。
これに対し、４階調をひとまとめにして、各版を６４階
調に減じておけば６４×６４×６４×４＝１ＭＢyte の
メモリで収まる。切り抜きには、この程度の階調数で何
等差し支えない。又、８階調をひとまとめにして各版を
３２階調に減じておけば、３２×３２×３２×４＝１２
８ＫＢyte のメモリで収まる。場合によってはこの程度
でも良いこともあり、後の計算が非常に楽になる。この
階調数（２５６、６４、３２）をＲＮで表わす。

【００３５】ここで、上記色ヒストグラムの作成を、対
象が図５のカラー画像である場合を例に具体的に説明す
る。このカラー画像には、テーブルクロス１０の上に載
っている白い皿１２と、その上の緑色のレタス１４と、
更にその上の赤い海老とが描写されている。

【００３６】このカラー画像の各画素のデータを、ＲＧ
Ｂの３次元色空間に写像して、この特徴空間における投
影像（ヒストグラム）を作成する。これを、便宜上ＲＧ
の２次元に関して各２５６階調で表示される色の分布を
概念的にに示したのが図６であり、このＲＧ平面に垂直
な方向が出現頻度（画素数）に当る。従って、この２次
元の色の分布から色ヒストグラムを作成すると、紙面に
垂直な方向に頻度の高さを有する、海老、レタス、テー
ブルクロス、皿の４つの山のテリトリーに大別される。
図示は省略するが、ＧＢ、ＲＢの各２次元座標系につい
ても同様に色の分布が得られる。

【００３７】上記のように作成された色ヒストグラム
は、色と各色の出現頻度との関係を表わした表として作
成される。次の表１は、このような方法で作成された色
ヒストグラムの一部を例示したものである。但し、ここ
では、便宜上、シアン（Ｃyan）、マゼンタ（Ｍagent
a）、イエロー（Ｙellow ）の３次元の色空間につい
て、各色を４階調を１単位とする６４階調（２５６／
４）で表記してある。

【００３８】

【表１】

【００３９】このように表で作成された色ヒストグラム
の一例を、マゼンタ−シアンの２次元座標系で概念的に
示した例が図７であり、この図に示した数字は該当する
シアンの階調座標（横軸）、マゼンタの階調座標（縦
軸）で規定される各色の出現頻度を表わしている。

【００４０】次いで、前記図１のステップ１０２である
定距離ｄ₀の設定を行う。この「定距離ｄ₀の設定」
は、後述するステップ１０３のピーク抽出、ステップ１
０５のテリトリ抽出を行う際に使用する近傍を定義する
ための準備として行われる。

【００４１】定距離ｄ₀の意味を説明するために、３次
元の離散格子における、「連結性」、「距離」、「近
傍」という概念を定義しておく。これは、よく用いられ
る２次元の場合の定義を極自然に拡張して定義できる。
又、ここでは触れないが、４次元以上の場合にもほぼ同
様に定義できる。

【００４２】まず、近接した２点間の「連結性」という
概念については、２次元の離散格子では、図８（Ａ）に
示すように、中心格子の周囲、上下左右の○印を付した
格子に連結する４連結と、それに４つの斜め方向を加え
た同図（Ｂ）に示す８連結とがある。図示は省略する
が、同様の考えに従って、３次元の場合は６連結、１８
連結、２４連結が考えられる。この連結性については、
例えば、森俊二他共著「画像認識の基礎Ｉ」上巻に、２
値画像の４連結、８連結に関して説明されている。

【００４３】４連結と８連結の定義を始めに説明する
と、２次元の離散格子上の２点をｘ＝（ｘ₁，ｘ₂）、
ｙ＝（ｙ₁，ｙ₂）とするとき、ｘとｙとが４連結であ
るとは、（ｘ₁−ｙ₁）²＋（ｘ₂−ｙ₂）²＝１ …（１）であることを言い、ｘとｙとが８連結であるのは、１≦（ｘ₁−ｙ₁）²＋（ｘ₂−ｙ₂）²≦２ …（２）であることを言う。

【００４４】これに倣って、６連結、１２連結、２６連
結を定義すると、３次元の離散格子上の２点を、ｘ＝
（ｘ₁，ｘ₂，ｘ₃）、ｙ＝（ｙ₁，ｙ₂，ｙ₃）とす
るとき、ｘとｙとが６連結であるとは、（ｘ₁−ｙ₁）²＋（ｘ₂−ｙ₂）²＋（ｘ₃−ｙ₃）²＝１ …（３）であることを言い、ｘとｙとが１８連結であるとは、１≦（ｘ₁−ｙ₁）²＋（ｘ₂−ｙ₂）²＋（ｘ₃−ｙ₃）²≦２…（４）であることを言い、ｘとｙとが２６連結であるとは、１≦（ｘ₁−ｙ₁）²＋（ｘ₂−ｙ₂）²＋（ｘ₃−ｙ₃）²≦３…（５）であることを言う。

【００４５】続いて、任意の２点間の「距離」という概
念について説明する。この距離には、上述した連結の定
義に応じて、２次元の離散格子では４連結距離と８連結
距離があるが、２次元の場合は６連結距離、１８連結距
離、２６連結距離が考えられる。ここで言う任意の２点
ｘとｙとの間の距離は、次元に拘らず、ｘからｙに至る
連結な道の最小ステップ数、即ち上記連結性を維持しな
がら到達できる最小ステップ数で定義される。

【００４６】２次元離散格子について、空間内の任意の
２点をｘ＝（ｘ₁，ｘ₂）、ｙ＝（ｙ₁，ｙ₂）とする
と、この２点間の距離ｄ（ｘ，ｙ）は、連結の定義に応
じて、４連結距離、８連結距離はそれぞれ次の（６）
式、（７）式となる。

【００４７】ｄ₄（ｘ，ｙ）＝｜ｘ₁−ｙ₁｜＋｜ｘ₂−ｙ₂｜ …（６）ｄ₈（ｘ，ｙ）＝ｍａｘ（｜ｘ₁−ｙ₁｜，｜ｘ₂−ｙ₂｜） …（７）

【００４８】即ち、図９に２次元離散格子の各格子中心
を×印で示したように、点ｘからｙ迄の４連結距離は、
実線で示すように、上下左右方向のみの隣接格子間最小
長さ（＝１）ずつしか許容されないが、８連結距離は、
破線で示すように、４５°斜め方向の長さ（＝√２）ま
で許容する場合のステップ数であるため、この例では、
ｄ₄（ｘ，ｙ）＝５，ｄ₈（ｙ，ｙ）＝３である。

【００４９】３次元離散格子についても、空間内の任意
の２点を、ｘ＝（ｘ₁，ｘ₂，ｘ₃）、ｙ＝（ｙ₁，ｙ
₂，ｙ₃）とすると、この２点間の距離ｄ（ｘ，ｙ）
は、連結の定義に応じて、６連結、１８連結、２８連結
の各距離は、それぞれ（８）、（９）、（１０）の各式
となると考えられる。なお、（９）式のｃｅｉｌは、括
弧内の値以上の最小の整数を意味する。

【００５０】ｄ₆（ｘ，ｙ）＝｜ｘ₁−ｙ₁｜＋｜ｘ₂−ｙ₂｜＋｜ｘ₃−ｙ₃｜ …（８）ｄ₁₈（ｘ，ｙ）＝ｍａｘ（Ｌ，ｃｅｉｌ（（Ｌ＋Ｍ＋Ｓ）／２） …（９）ここで、Ｌ＝ｍａｘ（｜ｘ₁−ｙ₁｜，｜ｘ₂−ｙ₂｜，｜ｘ₃−ｙ₃｜）Ｍ＝middle（｜ｘ₁−ｙ₁｜，｜ｘ₂−ｙ₂｜，｜ｘ₃−ｙ₃｜）Ｓ＝ｍｉｎ（｜ｘ₁−ｙ₁｜，｜ｘ₂−ｙ₂｜，｜ｘ₃−ｙ₃｜）ｄ₂₆（ｘ，ｙ）＝ｍａｘ（｜ｘ₁−ｙ₁｜，｜ｘ₂−ｙ₂｜，｜ｘ₃−ｙ₃｜） …（１０）

【００５１】次に、後述するステップ１０３、１０５で
用いられる「近傍」という概念について説明する。点ｘ
の近傍とは、その点ｘから定距離内にある点ｙの集合で
ある。定距離ｄ₀を定めるときは、点ｘの近傍Ｖ（ｘ，
ｄ₀）は、２次元離散格子について、４連結、８連結の
各距離を採用する場合は、それぞれ（１１）、（１２）
式で定義される。

【００５２】Ｖ₄（ｘ，ｄ₀）＝｛ｙ；ｄ₄（ｘ，ｙ）≦ｄ₀｝ …（１１）Ｖ₈（ｘ，ｄ₀）＝｛ｙ；ｄ₈（ｘ，ｙ）≦ｄ₀｝ …（１２）

【００５３】又、上記近傍は、３次元離散格子につい
て、６連結、１８連結、２６連結の各距離を採用する場
合は、それぞれ（１３）、（１４）、（１５）の各式で
定義される。

【００５４】Ｖ₆（ｘ，ｄ₀）＝｛ｙ；ｄ₆（ｘ，ｙ）≦ｄ₀｝ …（１３）Ｖ₁₈（ｘ，ｄ₀）＝｛ｙ；ｄ₁₈（ｘ，ｙ）≦ｄ₀｝ …（１４）Ｖ₂₆（ｘ，ｄ₀）＝｛ｙ；ｄ₂₆（ｘ，ｙ）≦ｄ₀｝ …（１５）

【００５５】以上で近傍が定義されたが、以下の説明で
は３次元離散格子における２６連結として考え、後述す
る近傍に関する処理のために定距離ｄ₀を予め定めてお
く。例えば、ｄ₀＝２，３，４のような値を用いる。２
６連結の下では、ある点から距離ｄ₀以内の点の個数は
（２ｄ₀＋１）³個ある。これは、ｄ₀＝１，２，３，
４，５に応じて、２７、１２５、３４３、７２９、１３
３１と急速に増えるので、計算時間を考慮してなるべく
小さな値に設定しておく。

【００５６】次に、前記図１のステップ１０３で実行さ
れる色ヒストグラムのｄ₀近傍に関するピークの抽出に
ついて説明する。この「色ヒストグラムのｄ₀近傍に関
するピーク抽出」は、カラー画像を色空間に写像するこ
とによって作成された前記色ヒストグラムで、最終的
に、出現頻度が周辺に比べて一段と高くなっている色を
ピークとして抽出する操作に当る。これは、色ヒストグ
ラムを、あたかも頻度の山と見做し、山の頂上を捜して
いることに相当する。

【００５７】この操作は、次の（１６）式に示すよう
に、ｘ₀から定距離ｄ₀以内の近傍内のｘで、ヒストグ
ラムｈ（ｘ）がｈ（ｘ₀）よりも高くなるものがないこ
とを、ｘ＝ｘ₀で頻度ｈ（ｘ）が局所的にピークである
と定義し、このような局所的なピークを全て抽出するこ
とに当る。前述したように、この式で、εは左辺が右辺
の要素であることを意味する。以下の式でも同様であ
る。

【００５８】

【数１】

【００５９】上記操作に際し、上の定義だけでは、高さ
０の平原が広がっていて近くに山が無いところがピーク
と見做されてしまう場合もあり得るので、必要に応じ
て、定数ｈ₀を設定し、次の（１７）式により、このｈ
₀より低いピークを除外するようにしてもよい。

【００６０】

【数２】

【００６１】上記定数ｈ₀として１，２，・・・のよう
な適当な値を用いてもよいが、次の（１８）式で与えら
れるｈ（ｘ）の除零平均を用いるのも有効である。

【００６２】

【数３】

【００６３】図２は、下限値としてｈ₀を設定する場合
の、前記ステップ１０３の詳細フローチャートである。

【００６４】即ち、ステップ２０１で、抽出するピーク
高さに、定数の下限値ｈ₀を設定し、ステップ２０２〜
２１０のループで、頻度分布の定義域内を全て探索し、
各点ｘについて、以下の操作を繰り返す。即ち、頻度ｈ
（ｘ）が、上記定数ｈ₀以上であり（ステップ２０
３）、且つ点ｘのｄ₀近傍の各点ｙについて、頻度ｈ
（ｙ）以上である点ｘの捜索を繰り返し（ステップ２０
４〜２０６）、最終的に得られた点ｘをピークとして抽
出し（ステップ２０１）、その点ｘをピークのリストに
追加する。一方、ステッフ２０３でｈ（ｘ）＜ｈ₀の場
合と、ステップ２０５でｈ（ｘ）＜ｈ（ｙ）の場合は、
点ｘはピークではないとして除外する（ステップ２０
８）。

【００６５】ところで、上述したピークの定義では、
（１６）、（１７）式でｈ（ｘ）とｈ（ｘ₀）の比較に
等号が入っているため、近接した同じ高さのピークが全
て抽出されてしまう点に注意する必要がある。等号が入
っている場合には、例えば、ヒストグラムの山頂が平ら
に広がっているときは、その辺り一帯がピークになる
が、等号を除くと全てがピークでなくなってしまうので
不都合である。この時点で不必要に多くのピークが抽出
された場合には、そのピークは後に行う降下の過程で統
合することができる。

【００６６】前記図１のステップ１０４である色ヒスト
グラムのピークのソートでは、抽出したピークを、頻度
の高い順に並べ変える。

【００６７】次に、前記図１のステップ１０５で実行す
る各ピークのｄ₀近傍に関するテリトリー抽出について
説明する。この「各ピークのｄ₀近傍に関するテリトリ
ー抽出」は、以下のように実行される。

【００６８】色ヒストグラムを各色についての出現頻度
の山と見做して抽出した個々のピークに属する山の範囲
を定め、求めた各山の範囲を各クラスタとして決定す
る。この方法は、登山にたとえると、登山者が、次のよ
うな規則に従って山を登ることにあたると説明できる。
歩幅はｄ₀以内であり、今いる地点から周辺を見渡して
一歩でいける範囲内で最も高いところへ一歩進むという
動作を繰り返して登っていき、頂上に到達してそれ以上
進めなくなったところで止まる。今、ある地点Ｑから出
発して山頂Ｐに至ったとき、Ｑは山頂Ｐの山に属すると
考え、該山頂Ｐに至ることのできる出発点Ｑの全体は山
頂Ｐのテリトリーであると考える。

【００６９】従って、計算は大変になるが、このように
山の下方の各点から順次上の方に登って行き、頂上（ピ
ーク）に到達したら、それまでに通った各点をそのピー
クのテリトリーに属するとしてクラスタ分割することも
できる。

【００７０】同じことを山頂から下を見下ろす形で考え
ると、次のように言い換えることができる。まず、山頂
Ｐ自体はＰのテリトリーに属する。このＰへ一歩でいけ
る点Ｑ１の全体は、Ｐのテリトリーに属する。このＱ１
へ一歩でいける点Ｑ２の全体はＰのテリトリーに属す
る。これを繰り返して得られるＱ３、Ｑ４・・・の全体
はＰのテリトリーに属する。

【００７１】これを定式化すると次のようになる。ヒス
トグラムｈ（ｘ）がｘ＝ｘ₀において、定距離ｄ₀によ
る近傍の範囲以内で最大点であるとき、ｘ₀のテリトリ
ーＤ（ｘ₀）を、次の（１）、（２）で定義できる。（１）ｘ₀εＤ（ｘ₀）；ｘ₀は無条件にＤ（ｘ₀）に
属する。（２）今、あるｘ₁がｘ₁εＤ（ｘ₀）であるとき、次
の（１９）式の関係を満たすｘ₂もｘ₂εＤ（ｘ₀）で
ある。

【００７２】

【数４】

【００７３】なお、上記（１９）式における等号は、ｘ
₂の周辺でｈ（ｘ₁）が単独で最大でなくともよいこと
を意味し、（１）山を降下する際、水平に進むことも有
り得る、（２）便宜上、１次元の頻度の山として図１０
に示すように、複数の山に共有される平坦部分が発生し
得る、ことを許容すると言える。

【００７４】上記（１）は、山の中腹に水平な箇所があ
っても、そこで停止することなく降下を続行させること
ができる。又、（１）は、平らな山頂でピークがひしめ
き合っているときに、これらを統合する働きがある。
（２）は、その平坦部分をテリトリーとして包含する複
数の山のうち、最も高いものに帰属させることにし、高
い山から順にテリトリーを調べていくので、最先に調べ
た山にその平坦部分が属することにすればクラスタ分け
ができる。

【００７５】上記（１９）式で定義されるクラスタ分け
は、図３及び図４のフローチャートに従って実現でき
る。

【００７６】以下、図３、図４のフローに従って詳述す
るにあたり、重複する部分もあるが、使用する記号につ
いて説明しておく。

【００７７】取り扱う色空間をＣ、色空間Ｃの要素をｘ
とすると、この色空間Ｃは次の（２０）式で表わすこと
ができる。ここで、Ｚは整数全体の集合で、ＲＮは前述
した階調数で、２５６、それを減じた６４、３２等の整
数である。

【００７８】Ｃ＝｛ｘεＺ³；ｘ＝（ｘ₀，ｘ₁，ｘ₂），０≦ｘ₀，ｘ₁，ｘ₂≦ＲＮ−１｝ …（２０）

【００７９】ヒストグラムｈは、（２１）式に示すよう
に、色空間Ｃから整数Ｚへの写像であり、そのｈ（ｘ）
は色ｘの出現した頻度（画素数）を表わす。

【００８０】ｈ；Ｃ→Ｚ …（２１）

【００８１】使用する画像処理装置では、記憶媒体に対
して、色空間Ｃの要素の個数分だけ整数値の記憶領域を
割り当て、各ヒストグラムｈ（ｘ）の値を格納する。

【００８２】ラベル・ヒストグラムｌは、次の（２２）
式に示すように、色空間Ｃから整数Ｚへの写像であり、
ｌ（ｘ）は色ｘの属するクラスタの番号を表わす。

【００８３】ｌ；Ｃ→Ｚ …（２２）

【００８４】同様に、色空間Ｃの要素の個数分だけ整数
値の記憶領域を割り当て、各クラスタ番号ｌ（ｘ）の値
を格納する。

【００８５】又、前記図１のステップ１０３、１０４で
それぞれ実行したピーク抽出とピークソートの結果、色
空間Ｃに属するＮＰ個のピークの列ｐ₀，ｐ₁，ｐ₂，
・・・，ｐ_NP-1（εＣ）が得られる。つまり、ｈ
（ｐ₀）≧ｈ（ｐ₁）≧ｈ（ｐ₂）・・・≧ｈ
（ｐ_NP-1）である。

【００８６】続いて、各ピークのｄ₀近傍に関するテリ
トリー抽出を、図３に従って説明する。この図３は、既
に得られ、且つソートされている各ピークからテリトリ
ーを抽出するフローの概要である。

【００８７】ここでは、最も頻度の高いピークに対応す
るラベル・ヒストグラムに値０が振られ、そこから降下
可能点を探索することによって得られるテリトリーにも
値０が振られるラベル付けが行われる。次に高いピーク
とその周辺のテリトリーについては値１が振られ、以下
同様の方法で全てのピークとテリトリーについて順次ラ
ベル付けが行われる。

【００８８】これを具体的に説明すると、まずステップ
３０１からステップ３０３までのループで、ラベル・ヒ
ストグラムを初期化する。その結果、頻度分布の全ての
要素について、ラベル・ヒストグラムの値が未処理（即
ち未だどのテリトリーにも属さないこと）を意味する
（−１）となる。

【００８９】次のステップ３０４とステップ３０７の間
は、各ピークに関するループであり、ｉは順次０，１，
２，・・・，ＮＰ−１の値をとる。即ち、ステップ３０
５では、第ｉ番目のピークを着目対象としてｘに格納
し、ステップ３０６では、ｘから頻度の坂を下ることに
より、ｘに属するテリトリーを求め、該ｘ及びそのテリ
トリーに対応するラベル・ヒストグラムｌに値ｉを格納
する。このステップ３０６の詳細が図４のフローチャー
トである。

【００９０】上記ステップ３０６の手続（Ｃ言語でいう
「関数」）は、再帰呼出し（recursive call）を用いて
いる。この手続は、与えられた点ｘから頻度の低い方へ
一歩下ることのできる点ｙを全て見付け出す。得られた
点ｙを改めて点ｘと見做して（このとき元のｘはスタッ
クに一時待避させる）、この手続自体を呼び出すことに
よって、一歩ずつ下っていくことができる。最終的に、
この手続から復帰するときには、当初のｘを頂上（ピー
ク）とする山の裾野に至るまでの全ての道を網羅し、ラ
ベルｉが振られる。

【００９１】ところで、「点ｘから点ｙへ一歩で下るこ
とができる」、即ち点ｘからの降下可能点ｙとは、点ｙ
が次の条件を満たすことにあたる。第１に、点ｙは点ｘ
のｄ ₀近傍内になくてはならない。第２に、点ｙから点
ｘを見たときに、点ｘが点ｙのｄ₀近傍内で最高点にな
っている必要がある。つまり、点ｙのｄ₀近傍内の全て
の点ｚについて、ｈ（ｘ）≧ｈ（ｚ）となっていること
である。従って、点ｘのｄ₀近傍内の全ての点ｙのｄ₀
近傍内の全ての点ｚについて調べることになる。

【００９２】これを具体的に説明すると、まず、ステッ
プ４０１で点ｘ自体がテリトリーｉに属すると見做すと
共に、ステップ４０２でｘに対応するラベル・ヒストグ
ラムｌ（ｘ）に値ｉを入れる。

【００９３】次のステップ４０３とステップ４１６の間
は、ｘのｄ₀近傍内の各候補点ｙに関するループであ
る。

【００９４】ステップ４０４では、点ｙの頻度ｈ（ｙ）
が０かどうかを調べ、０であれば、点ｙは最早山を下り
切っているので候補から外し、ステップ４１１へいく。
上記ｈ（ｙ）が０でなければ、ステップ４０５へ進む。

【００９５】このステップ４０５は、必ずしも必要でな
いが、連峰型の山を統合する。もし、点ｙに既に初期値
（−１）ではないラベルｊが振られていて、且つｊ≠ｉ
であるとき、山ｉが山ｊに出会ったことを示す。この条
件の下で、点ｙの頻度ｈ（ｙ）が一定値以上であれば、
山ｉと山ｊは同一の山であると見做し、全てのラベルｊ
をｉに付け変える。なお、この統合処理については後に
詳述する。

【００９６】ステップ４０６では、点ｙのラベルが（−
１）であるかどうかを調べ、（−１）でなければ点ｙは
既に別の山に属しているので候補から外し、ステップ４
１１ヘいく。逆に（−１）であれば、ステップ４０７へ
進む。

【００９７】次のステップ４０７とステップ４０９との
間は、ｙのｄ₀近傍内の各点ｚに関するループである。

【００９８】ステップ４０８では、点ｘの頻度ｈ（ｘ）
と、点ｚの頻度ｈ（ｚ）とを比較する。ｈ（ｘ）の方が
小さければｙから一歩登って直接ｘに至ることはないの
で、点ｙを候補から外し、ステップ４１１へいく。ｈ
（ｘ）の方が小さくなければ、ステップ４０９へ進んで
次の点ｚについて繰り返す。

【００９９】但し、ここで点ｙが除外されたとしても、
それはｙから一歩で直接的にｘに至らないことを示して
いるのであって、ｙがテリトリーｉに属さないことを示
すものではない。同じ点ｙが別の道からテリトリーｉに
属することは有り得る。

【０１００】ステップ４０７とステップ４０９との間の
点ｚに関するループを全うして、次のステップ４１０に
至ると、点ｙは確かにｘから一歩で下がることのできる
点であったことが分かる。そして、ステップ４１２に進
む。逆にそうでないときは、即ちステップ４０８でＹｅ
ｓのときは、ステップ１１に弾き出され、点ｙは除外さ
れる。

【０１０１】上記ステップ４１２では、今のｘをスタッ
クへプッシュ・ダウンする。このスタックとは、ＬＩＦ
Ｏ（Ｌast Ｉn ，Ｆirst Ｏut）型の格納領域であり、
ここにプッシュ・ダウンすることは、１つの点から進め
る点が２以上ある分岐点がある場合、その点のデータを
記憶することを意味する。

【０１０２】次いで、ステップ４１３でｙを改めてｘと
し、ステップ４１４でこの新たなｘについて、この手続
自体を呼び出し（再帰呼出し）、ｘのｄ₀近傍に関する
テリトリを抽出し、ラベルｉを付ける。

【０１０３】次いで、ステップ４１５では、上記ステッ
プ４１２でスタックに格納したｘをポップアップにより
取り出して、ｘを元に戻す。その後、上述したステップ
４０３〜４１６のループを繰り返すことにより、当初の
ｘを頂上とする山の裾野に至る迄の全ての点に対するラ
ベル付けが実行される。

【０１０４】ここで、以上詳述した処理における定距離
ｄ₀についての意味を考える。

【０１０５】前述したピーク抽出とピーク毎のテリトリ
ー抽出では、予め設定された定数ｄ ₀を用いたが、ヒス
トグラムが十分滑らかであることが仮定できるならば、
ｄ₀＝１（隣接格子間最小長さ）で十分である。このピ
ーク抽出は、連結する周辺に対して極大の点を抽出する
ことを意味し、テリトリー抽出は、ピークから連続的に
坂を下ることを意味する。

【０１０６】ところで、実際のヒストグラムは、図１１
（Ａ）示したようにガタ付いていることが多く、又、頻
度が０の色もよく生じるために、ヒストグラムが、図１
１（Ｂ）に示したように櫛歯状に抜けることもある。こ
のようなとき、ｄ₀として１よりも大きな値を設定する
ことにより、ピーク抽出においては、山の中腹に生じた
無用の小さなピークを排除し、テリトリー抽出において
は、小さな谷を跨ぎ越して坂を下ることができる。

【０１０７】なお、ガタ付いたヒストグラムに対する別
な対策としては、まず、ガウシアンのような平滑化フィ
ルタを施しておいて、ｄ₀＝１でピーク抽出とテリトリ
ー抽出を行う方法を採用してもよい。但し、この場合
は、（１）タップ数の小さなフィルタでは櫛の歯状のガ
タ付きが取り除き切れない、（２）タップ数の大きなフ
ィルタでは元のヒストグラムの情報の損失が大きい、
（３）フィルタをかけること自体、計算の負荷が大き
い、という問題がある。従って、この方法よりも、上述
したｄ₀を大きくとる方法の方が優れていると言える
が、この方法を採用してもよい。

【０１０８】次に、前記図４のステップ４０５である連
峰型の山の問題と統合について説明する。この「連峰型
の山の問題と統合」は、前述した如く、必ずしも必要で
はないが、次のような意味がある。

【０１０９】テリトリー抽出で山を下る際、無用のピー
クを統合していったが、それでも未だクラスタ数が多す
ぎることがある。この問題は、連峰型の山によって生じ
る。連峰型の山とは、本来１つの山と見做されるべき山
が離れた箇所に複数のピークを持つために、今のアルゴ
リズムではピークの個数に対応した個数の山に分離され
てしまうような山があることである。言い換えれば、２
つのピークの間が高い尾根でつながっていて、全体とし
て１つの長細い山を形成している場合である。

【０１１０】連峰型の山は、例えば次のようにして統合
する。まず、定数ＭＴＨ（ＭergeＴＨreshold ）を区間
［０，１］の適当な値、例えば２／３に決めておく。テ
リトリー抽出で、山を下っていく際に別の山に出会った
とき、その地点が元の山の山頂の高さのＭＴＨ倍以上、
上述した列では２／３以上であれば元の山と出会った山
とを統合する。

【０１１１】最後に、前記図１のステップ１０６である
取りこぼしの拾い集めについて説明する。この「取りこ
ぼしの拾い集め」は必ずしも必要ではないが、次のよう
な意味がある。

【０１１２】このクラスタ分けアルゴリズムで、頻度が
０でないにも拘らず、どのクラスタにも属さない色が生
じることがある。それは、ピーク抽出で、低いピークを
切り捨てたからである。切り捨てられたピークが大きな
山から孤立していて、テリトリー抽出の過程で拾い上げ
られなかった場合、無所属の色として取り残される。こ
のような色は必要に応じて適当な最寄りの山に帰属させ
る。

【０１１３】以上、詳述した本実施形態によれば、あた
かも色ヒストグラムを山と見做して、その中から山頂に
あたるピークを抽出し、その後山頂から尾根伝いに下山
する行為を、尾根全体について繰り返す（分岐点がある
場合はその点迄戻って繰り返す）ことにより、その山の
裾野を特定し、その範囲をクラスタとすることが可能と
なる。その結果、図１２に参考のために、実際の地図を
模式的に示し、尾根を破線、テリトリー境界を実線で示
したように、Ａ山、Ｂ山、Ｃ山、Ｄ山、Ｅ山等が山頂で
あるテリトリーからなるクラスタを、それぞれ求めるこ
とができる。

【０１１４】本実施形態によるクラスタ分けを、前記表
１のように作成された色ヒストグラムについて実行し、
ラベル付けした結果であるラベル・ヒストグラムの一部
を、表わしたものが次の表２である。又、この表２のよ
うに作成されたラベル・ヒストグラムを、前記図７に対
応させてニーレンで表示したものが図１３であり、１又
は２等の同一のカテゴリー番号が振られた色は同一のク
ラスタに属することが表わされている。

【０１１５】

【表２】

【０１１６】以上詳述した本実施形態によれば、前述し
たクラスタ分け手法が満たすべき、前記１〜６の各要件
は、対応する次の１〜６に示すように実現することがで
きる。１．色ヒストグラムの極大となる点を抽出することによ
って出現頻度が際立って高い色がピークとして抽出さ
れ、これらが各クラスタの中心となり、その数が自ずと
クラスタの数に反映されるため、クラスタ数を予め与え
ておかなくとも、クラスタ分けの結果として適切に決定
される。２．色ヒストグラムの定義域である色空間は、距離と近
傍の概念が定義できればよいため、本実施形態よるクラ
スタ分けはヒストグラムの次元によらず適用できる。３．各クラスタ中心から頻度の坂を下ることによって各
クラスタの範囲を求めるので、各クラスタ形状は分布の
形状に応じて柔軟に決まることになるため、分布の形状
を決めるために正規分布のような仮定を必要としない。４．近傍を定めるための定距離ｄ₀を１より大きな値に
設定しておくことにより、頻度のピークの抽出において
は、ヒストグラムの細かなガタ付きから生じた不要な小
さなピークを抽出することが抑制され、又、各ピークか
ら頻度の坂を降下する際には、ヒストグラムの細かなガ
タ付きから生じた小さな谷を跨ぎ越すことができるた
め、色の出現頻度のムラによるヒストグラムの細かなガ
タ付きに左右されず、分布の形状を大きく捕らえてクラ
スタ分けすることができる。５．結果として得られるクラスタ数の高を調整するため
に予め設定しておくパラメータは、本質的には定距離ｄ
₀のみである。６．実験結果により、計算量及びメモリ容量は実用的な
範囲内であった。

【０１１７】以上、本発明について具体的に説明した
が、本発明は、前記実施形態に示したものに限られるも
のでなく、その要旨を逸脱しない範囲で種々変更可能で
ある。

【０１１８】

【発明の効果】以上説明したとおり、本発明によれば、
初期値を与えることなく、個々の画像に応じて適切な数
のクラスタに分けることができる。

【図面の簡単な説明】

【図１】クラスタ分けの操作手順の概要を示すフローチ
ャート

【図２】色ヒストグラムのピーク抽出の手順を示すフロ
ーチャート

【図３】各ピークについてのテリトリー抽出手順の概要
を示すフローチャート

【図４】テリトリー抽出とラベル付けの手順の詳細を示
すフローチャート

【図５】クラスタ分け対象のカラー画像を概念的に示す
説明図

【図６】上記カラー画像から得られるＲＧ色空間へ投影
像に当るヒストグラムを示す説明図

【図７】色ヒストグラムを、色空間に出現頻度値で表示
した一例を示す説明図

【図８】２次元の離散格子の連結性を説明するための概
念図

【図９】２次元の離散格子の連結距離を説明するための
概念図

【図１０】テリトリ抽出時における平坦部の取り扱いを
説明するための概念図

【図１１】ヒストグラムのガタ付きを概念的に示す説明
図

【図１２】本実施形態によるクラスタ分けの結果を概念
的に示す説明図

【図１３】前記図７に相当するラベル・ヒストグラムを
示す説明図

【図１４】カラー画像の色空間への写像とクラスタ分け
等の関係を示す説明図

【図１５】色空間におけるクラスタの分布を概念的に示
す説明図

【符号の説明】

１０…テーブルクロス１２…皿１４…レタス１６…海老

Claims

【特許請求の範囲】

【請求項１】カラー画像を構成する各画素データを色空
間に写像した際に、各色についての画素の出現頻度とし
て得られる色ヒストグラムを作成し、作成した色ヒストグラムに存在する頻度のピークを抽出
し、抽出したピークから、定距離ｄ₀以内の近傍に存在する
降下可能点を探索し、探索した降下可能点から、定距離ｄ₀以内の近傍に存在
する次の降下可能点を探索する如く、降下可能点の探索
を繰り返し、得られた各降下可能点により特定されるテリトリを、前
記頻度のピークが属するクラスタとして、色ヒストグラ
ムをクラスタ分けすることを特徴とする画像処理方法。
【請求項２】請求項１において、点ｘから降下可能点ｙを探索する際、該点ｘから定距離
ｄ₀以内の近傍に存在する点ｙについて、点ｘにおける
頻度が、該点ｙから定距離ｄ₀以内の近傍に存在する全
ての点ｚの中で最大であるときに、この点ｙを点ｘから
の降下可能点であると判定することを特徴とする画像処
理方法。
【請求項３】請求項１において、定距離ｄ₀を、色ヒストグラムを離散格子で表現する際
の隣接格子間最小長さを超える値で設定することを特徴
とする画像処理方法。
【請求項４】請求項１において、作成した色ヒストグラムのクラスタ分けを、該色ヒスト
グラムを平滑化処理した後に、行うことを特徴とする画
像処理方法。
【請求項５】請求項１において、頻度のピークを、任意の色について設定される定距離ｄ
₀以内の近傍に存在する色の極大頻度として抽出するこ
とを特徴とする画像処理方法。