JPH07160879A

JPH07160879A - 画像処理方法

Info

Publication number: JPH07160879A
Application number: JP34007793A
Authority: JP
Inventors: Naohito Atozawa; 尚人後澤
Original assignee: Toppan Printing Co Ltd
Current assignee: Toppan Inc
Priority date: 1993-12-07
Filing date: 1993-12-07
Publication date: 1995-06-23

Abstract

(57)【要約】（修正有）【目的】画像を、「ライト、中間、シャドウ」のよう
に視覚的に合致した領域分割を行う。【構成】ＣＰＵは、画像データ２１中の一の画素２１
０に着目し、画素２１０に隣接する画素を検出する。Ｃ
ＰＵは、頂点及び辺のデータ画素２１０に隣接する画素
の中から色空間上における対比強度尺度値が最小（類似
度が最大）となる画素２１１を画素２１０に順次統合す
る。色空間上の座標及び実画像上の領域の連結性を考慮
することにより、視覚特性に合致した領域分割が可能と
なる。また、領域統合の判断を隣接するクラスタについ
てのみ行えばよいため、処理時間及びメモリ容量を軽減
できる。また、領域統合されたクラスタに不連続の部分
が生じることもない。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、画像処理方法に関し、
詳しくは画像データをある特徴を有する領域毎に分割を
行う画像処理方法に関する。

【０００２】

【従来の技術】印刷・写真・絵画等の分野においては、
画像の明度・色相・彩度・座標（位置）等を総合的にと
らえ、「ライト、中間、シャドウ」のように画像の部分
を分類することが多い。例えば、人物を表す写真の校正
段階において「人物のライトをさらに明るく」等のよう
に、画像のある部分を特定するために「ライト、中間、
シャドウ」という概念が用いられることが多い。「ライ
ト、中間、シャドウ」の判断は専ら作業者の判断に委ね
られており、作業者はこの判断をする際に画像の明度・
色相・彩度・座標等を総合的に考慮することが知られて
いる。

【０００３】近年、印刷等の分野においては、原稿画像
をコンピュータにより処理することが多くなったため、
「ライト、中間、シャドウ」についても同様にコンピュ
ータにより自動的に抽出処理できることが好ましい。画
像中のある領域を抽出する一般的な方法として、濃度差
を有する画像を所定の閾値を用いて領域分割を行う方
法、濃度または色度等のヒストグラムにより決定された
閾値を用いて領域分割を行う方法、画像のエッジを領域
の境界線とみなして領域分割を行う方法等を用いること
が考えられる。

【０００４】しかしながら、上記従来の画像処理方法
は、いずれも画像の明度・色相・彩度・座標等をそれぞ
れ別個に判断することにより領域分割を行うものであっ
て、これらを総合的にとらえて領域分割を行うものでは
ない。したがって、従来の画像処理方法によって分割さ
れた領域は、「ライト、中間、シャドウ」という概念に
よる領域とは異なったものとなってしまう。すなわち、
上述した画像処理方法によっては、「ライト、中間、シ
ャドウ」のように、人間の認識に合致した領域分割を行
うことはできない。

【０００５】また、「ライト、中間、シャドウ」の分割
・分類に階層性があることに着目すれば、階層的クラス
タ分析法を画像に適用して、「ライト、中間、シャド
ウ」の各領域を分割・分類することも考えられる。とこ
ろが、この場合には以下の問題が生じる。階層的クラス
タリングを行うためには、全ての画素対についての色空
間上の距離を計算し、この中から最小距離のクラスタ対
を見つけださなければならない。このため、画素数が増
えると、計算対象とするクラスタ対の数は膨大な数とな
り、処理時間および必要とするメモリ容量は膨大なもの
となってしまう。例えば、５１２×５１２画素の画像デ
ータにあっては、全画素数ｎ＝５１２×５１２＝２６２
１４４における画素対の組み合わせの数は_nＣ₂＝３.４
３６×１０⁶となる。この数のデータを同時にメモリに
保持しようとすると、およそ２００〜４００ＧＢｙｔｅ
ｓもの大容量メモリを必要とする。また、画素数ｎにつ
いての画素対の数は_nＣ₂＝ｎ（ｎ＋１）／２で表される
ことから、演算対象となる画素対の数は画素数ｎの二乗
に比例して増加することが確認できる。したがって、か
かる方法は、膨大な計算時間およびメモリ容量を必要と
するため、高精細画像を対象としたクラスタリングには
適用できず、「ライト、中間、シャドウ」の各領域の分
割を行うことは不可能である。

【０００６】したがって、従来の画像処理方法のいずれ
を用いたとしても、画像を「ライト、中間、シャドウ」
の各領域に分割することはできなかった。

【０００７】

【発明の目的】そこで、本発明は、画像を人間の認識に
合わせて「ライト、中間、シャドウ」の各領域に分割可
能な画像処理方法を提供することを目的としている。

【０００８】

【課題を解決するための手段】請求項１に記載の発明
は、画像データ中の対比される２つの領域の類似度を、
色空間上における当該２つの領域の座標に基づき算出
し、上記画像データ中の一の領域に隣接した複数の他の
領域のうち、当該一の領域との類似度が最大となる他の
領域を当該一の領域に順次統合することを特徴とする画
像処理方法である。

【０００９】請求項２に記載の発明は、画像データ中の
対比される２つの領域の類似度を、色空間上における当
該２つの領域の座標に基づき算出し、上記画像データ中
の一の領域に隣接した複数の他の領域のうち、当該一の
領域との類似度が最大となる他の領域を当該一の領域に
順次統合し、領域統合の順序および領域統合された領域
間の類似度を表す履歴データを生成し、上記履歴データ
に従い領域統合された画像データのうち、所定範囲の類
似度の領域対を、領域統合の順序と逆の順序で順次分割
することを特徴とする画像処理方法である。

【００１０】請求項３記載の発明は、請求項１または請
求項２記載の類似度を画像データ中の対比される２つの
領域を統合したことによる色空間上における各領域の分
散または重心の変化に基づき算出することを特徴とする
画像処理方法である。

【００１１】請求項４に記載の発明は、画像データを構
成する各領域を頂点とみなし、隣接し合う２つの頂点の
類似度を色空間上における２つの頂点の座標に基づき算
出し、算出された類似度を上記２つの頂点を連結する辺
とみなし、一の頂点に連結された複数の辺のなかから、
類似度が最大となる辺を検索するとともに、検索された
辺に連結された他の頂点を上記一の頂点に統合する処理
を繰り返すことを特徴とする画像処理方法である。

【００１２】

【作用】請求項１記載の発明において、画像データ中の
対比される２つの領域（クラスタ）の類似度を、色空間
上における当該２つの領域の座標に基づき算出する。す
なわち、２つの領域の色度等が近似している場合には、
類似度は大きくなる。そして、画像データ中の一の領域
に隣接した複数の他の領域のなかから、当該一の領域と
の類似度が最大となる他の領域を当該一の領域に順次統
合する。これにより、色度の近似した領域同士が統合さ
れ、領域間のコントラストを十分に高くすることができ
る。

【００１３】本発明によれば、色空間上座標および実画
像上の座標等を考慮することにより、明度・色度等を総
合的にとらえた領域統合が可能となる。以上のことよ
り、画像を「ライト、中間、シャドウ」のように画像を
大局的にとらえた領域抽出を行うことができる。さら
に、本発明によれば、隣接する領域対についてのみ類似
度を算出すればよいため、類似度のデータ等を保持する
ためのメモリ容量を低減できるとともに、画像に関して
階層的クラスタリングを短時間に行うことができるとい
う利点もある。

【００１４】請求項２記載の発明において、画像データ
中の対比される２つの領域の類似度を、色空間上におけ
る当該２つの領域の座標に基づき算出する。そして、上
記画像データ中の一の領域に隣接した複数の他の領域の
うち、当該一の領域との類似度が最大となる他の領域を
当該一の領域に順次統合する。このとき、領域統合の順
序および領域統合された領域間の類似度を表す履歴デー
タを生成しておく。そして、領域統合された画像データ
のうち、上記履歴データに従い、所定範囲の類似度の領
域対を、領域統合の順序と逆の順序で順次分割する。す
なわち、領域統合された画像データは、ある程度特徴の
近似した領域毎に再度分割される。したがって、本発明
によれば、画像データ中から所望の領域を抽出すること
ができるものである。

【００１５】請求項３記載の発明においては、請求項１
または請求項２記載の類似度を画像データ中の対比され
る２つの領域を統合した場合における色空間上の各領域
の分散または重心の変化に基づき算出する。例えば、色
度が相違するために色空間上において２領域が離れてい
る場合には、これらの２領域を統合することにより分散
は大きくなる。一方、色度が近似するために色空間上に
おいて２領域が接近している場合には、これらの２領域
を統合したとしても分散はさほど変化しない。また、色
空間上においてかけ離れた２領域を統合した場合には、
統合前後の重心位置が大きく変動する。一方、距離が近
い２領域を統合した場合には、統合前後の重心位置の変
動は少ない。よって、分散または重心の変化に基づき類
似度を算出することが可能となる。

【００１６】請求項４に記載の発明において、先ず、画
像データを構成する各領域を頂点とみなす。次に、隣接
し合う２つの頂点の類似度を色空間上における２つの頂
点の座標に基づき算出し、算出された類似度を上記２つ
の頂点を連結する辺とみなす。すなわち、各領域、類似
度を頂点および辺を用いたグラフ構造によって表す。そ
して、一の頂点に連結された複数の辺のなかから、類似
度が最大となる辺を検索するとともに、検索された辺に
連結された他の頂点を上記一の頂点に統合する処理を繰
り返す。このようにグラフ構造を用いることにより、領
域統合を階層的に行うことが可能となるものである。

【００１７】

【実施例】以下、本発明の一実施例に係る画像処理方法
を説明する。

【００１８】本実施例に係る画像処理方法を実行可能な
画像処理装置のブロック図を図１に示す。この画像処理
装置は、バス１０、ＣＰＵ１１、入力Ｉ／Ｆ１２、プロ
グラムメモリ１３、ワークメモリ１４、画像メモリ１
５、出力Ｉ／Ｆ１６、外部記憶装置１７、ＧＤＣ（グラ
フィック・ディスプレイ・コントローラ）１８、ディス
プレイ１９等により構成されている。ＣＰＵ１１は、プ
ログラムメモリ１３に書き込まれたプログラムに従い画
像の領域分割等の処理を実行するものである。入力Ｉ／
Ｆ１２は、処理対象となる画像データを入力するための
インタフェースである。画像データは自然画像を表し、
例えば５１２×５１２画素のＲＧＢ（またはＣＭＹＫ、
ＣＩＥＬＡＢ）のカラーのデータより構成される。プ
ログラムメモリ１３は上述したＣＰＵ１１の処理手順を
表すプログラムデータを格納するためのものである。

【００１９】ワークメモリ１４はＣＰＵ１１が領域分割
の処理に伴い算出するデータ（後述するツリーデータ、
リストデータ等）を一時保持しておくためのものであ
る。画像メモリ１５は入力Ｉ／Ｆ１２から入力された画
像データを蓄えるためのものである。出力Ｉ／Ｆ１６
は、領域分割された画像データ等を外部機器（プリンタ
等）に出力するためのディジタルインタフェースであ
る。外部記憶装置１７は、ハードディスクユニット、光
磁気ディスクユニット等により構成され、画像データ、
領域分割された画像データ、ツリーデータ、リストデー
タ、プログラムデータ等を保存する大容量記憶装置であ
る。ＧＤＣ１８は画像データおよび領域分割後の画像デ
ータ等に基づき、表示データを生成するものである。デ
ィスプレイ１９はこの表示データに基づく画像を表示す
るためのものである。

【００２０】本実施例に係る画像処理方法の詳細を説明
する前に、階層的クラスタリングの概要を先ず説明す
る。階層的クラスタリングは、色相、明度、彩度等の特
徴が近似している（類似度の大きい）領域（クラスタ）
同士を順次統合していくことにより画像の領域分割を行
うものである。この画像処理装置によれば、与えられた
画像を人物と背景との領域に分割することが可能となる
ものである。

【００２１】例えば、物と背景をあらわす画像データが
画像処理装置に与えられたとする。画像処理装置は、ｎ
画素の画像データ中の各画素の色空間上の座標点を初期
クラスタとする。色空間上におけるｎ個のクラスタは、
背景を表す画素と人物を表す画素とに対応して２つのか
たまった分布をなす。画像処理装置は、ｎ個の初期クラ
スタの中の一のクラスタに着目し、色空間上においてこ
のクラスタに色度の近いクラスタを探し出す。すなわ
ち、画像処理装置は一のクラスタと他の全てのクラスタ
との色度等を色空間上の座標により計算し、色度の近似
した他のクラスタを探し出す。

【００２２】このようにして検出されたクラスタ対は、
実画像におけるる色相、明度、彩度等が互いに近似した
ものとなる。画像処理装置がこのクラスタ対を統合する
ことにより、クラスタの数はｎ−１個となる。この処理
を繰り返し実行し、クラスタ同士を順次統合すると、最
終的にはクラスタの数は１個となる。ここで、画像処理
装置が領域統合の過程においてクラスタの数が２個とな
った時点において領域統合を中止し、各画素を２つのク
ラスタに分類したとする。このようにして得られた２つ
のクラスタのうち、同一のクラスタを構成する画素同士
は互いに色度が近似しているが、異なるクラスタ間の画
素同士は色度が大きく異なっている。すなわち、画像デ
ータは特徴の異なる２つのグループに分割されたことに
なる。以上の処理により、画像を背景と人物との２つの
領域に分割することが可能となるものである。

【００２３】図２は画像データおよび領域統合処理の概
念図である。図２中の符号２１は、入力Ｉ／Ｆ１２から
入力された画像データのうちの一部（９画素分）を示し
ている。図３はＬ^*ａ^*ｂ^*色空間上における画像データ
を表す図である。本画像処理装置にあっては、例えば画
素（クラスタ）２１０といずれの画素を統合させるかを
以下のように判断している。

【００２４】先ず、画像処理装置は、画素２１０に隣接
する画素（４近傍または８近傍）を探し出す。画素２１
０に隣接する画素のみが、画素２１０と統合可能なもの
である。そして、画像処理装置は、画素２１０に隣接す
る画素のうち対比強度尺度値が最小となる（類似度が最
大となる）画素を探し出す。対比強度尺度値は、後述す
るようにＬ^*ａ^*ｂ^*色空間（図３）上において領域統合
をした場合に、クラスタの分散値の変化を表したもので
ある。Ｌ^*ａ^*ｂ^*色空間は均等色空間であり、この空間
上における距離は視覚上の色度の差に略比例したものと
なっている。すなわち、Ｌ^*ａ^*ｂ^*色空間における対比
強度尺度値が小さいということは、クラスタ対の色度等
が近似している（類似度が大きい）ことを意味し、対比
強度尺度値が大きいということは領域対の色度等が相違
（類似度が小さい）ということを意味している。

【００２５】例えば、Ｌ^*ａ^*ｂ^*色空間において画素２
１０と画素２１１との対比強度尺度値が最小であったと
すると、画像処理装置は画素２１０と画素２１１との領
域統合を行う。このような処理を繰り返すことにより、
隣接する画素（クラスタ）対のうち、色度等の近似した
もの同士が順次統合され、最終的には９個の画素は１つ
のクラスタ（領域）にまとめられるものである。

【００２６】上述した階層的クラスタリング処理を効率
よく行うために、本実施例はいわゆるグラフ構造による
データ処理を行っている。すなわち、画像データを構成
する画素（クラスタ）を頂点とみなし、Ｌ^*ａ^*ｂ^*色空
間における画素（クラスタ）間の対比強度尺度値を辺と
みなし、各領域および各領域間の類似度等をグラフとし
て扱うものである。これらの頂点および辺の全体をグラ
フとしてとらえると、階層的クラスタリングの処理はい
わゆる木（ｔｒｅｅ）を構成することになる。以下に、
本画像処理装置における各種データ構造を図５〜図８を
参照しながら説明する。

【００２７】図５は、頂点のデータ５０および辺のデー
タ５１を表している。頂点のデータ５０はクラスタの情
報を表すものであり、以下のデータにより構成されてい
る。同図において、ラベル５０１はグラフ中の一意の記
号であればよいが、本実施例では頂点であるクラスタの
実画像上の座標（ｘ，ｙ）を表している。例えば、３２
ビットのデータのうちの上位１６ビットをｙ座標値、下
位１６ビットをｘ座標値とすると、ラベル５０１はｙ×
６５５３６＋ｘのように表される。また、画像の幅をｗ
とし、ｘ＋ｙ×ｗのようにラベル５０１を表すことも可
能である。Ｌ^*平均値５０２、ａ^*平均値５０３、ｂ^*平
均値５０４は、クラスタ内の各画素についてのＬ^*ａ^*ｂ
^*色空間における各座標の平均値を表したものである。
サンプル数５０５は、クラスタを構成する全画素数を表
している。リストへのポインタ５０６は、ワークメモリ
１４上におけるリストデータ６０のアドレスを表すもの
である。リストデータ６０は、辺のデータのポインタよ
りなるものであり、これについては後述する（図６）。
二分木へのポインタ５０７は、統合前の頂点を表す二分
木のノードを表すものである。すなわち、二分木のデー
タはクラスタの統合履歴をツリー構造のデータとして表
したものである。

【００２８】辺のデータ５１は以下のように構成されて
いる。対比強度尺度値５１１は辺の両端にある頂点（ク
ラスタ）間のＬ^*ａ^*ｂ^*色空間上における分散変化を表
している。すなわち、対比強度尺度値５１１は、対比さ
れる２つのクラスタを統合したと仮定して、統合前後に
おけるＬ^*ａ^*ｂ^*色空間上のクラスタの分散値の変化を
表したものである。したがって、対比強度尺度値が小さ
いということは、２つのクラスタを統合した場合におけ
る分散値の変化が少ないということであり、すなわち、
２つのクラスタの色度が近似している（類似度が大き
い）ということを意味している。逆に、対比強度尺度値
が大きいということは、２つのクラスタを統合した場合
における分散値の変化が大きいということであり、すな
わち、２つのクラスタの色度が相違している（類似度が
小さい）ということを意味している。なお、図３の下式
に従い対比強度尺度値を算出する際に、Ｌ^*ａ^*ｂ^*の各
成分に重み付けをしてもよい。

【００２９】辺のデータ５１中の頂点のデータへのポイ
ンタ５１２、５１３は、辺の両端の頂点のデータのアド
レスを示している。したがって、辺のデータ５１を参照
することにより、クラスタの連結関係および各クラスタ
間の類似度を容易に判断することが可能となるものであ
る。

【００３０】図６は、リストデータ６０、頂点のデータ
５０、辺のデータ５１の関係を表している。この図の頂
点のデータ５０、辺のデータ５１は上述したとうりのも
のである。リストデータ６０は、辺のデータ５１のアド
レスを示すポインタ６０１より構成されているものであ
る。よって、リストデータ６０を参照することにより、
辺および頂点の連結関係を把握することが可能となるも
のである。また、辺のデータ５１中のポインタ５１２、
５１３を参照することにより辺の両端にある２つの頂点
のデータ５０を探し出すことができ、頂点のデータ５０
中のリストへのポインタ５０６を参照することによりリ
ストデータ６０を探し出すことができるものである。

【００３１】図７は、頂点のデータ５０、ツリー構造の
ノードデータ７０を表している。ノードデータ７０に
は、２つの頂点（クラスタ）を統合する際の情報が含ま
れており、二分木のデータの一部を構成するものであ
る。ラベル７０１は統合後の頂点のラベルで、本実施例
では、統合前の２つの頂点のラベルのいずれかとする。
Ｌ^*平均値７０２、ａ^*平均値７０３、ｂ^*平均値７０４
は、２つのクラスタを統合した後の各色成分の平均値で
ある。すなわち、各クラスタの総画素数に従い各色成分
の値を加重平均したものが、Ｌ^*平均値７０２、ａ^*平均
値７０３、ｂ^*平均値７０４である。対比強度尺度値７
０５は、上述したように２つのクラスタを統合した場合
におけるＬ^*ａ^*ｂ^*色空間上の分散値の変化を示してい
る。

【００３２】サブツリーへのポインタ７０６、７０７
は、統合されたノードデータ７０を指し示すものであ
る。このように階層的構造をなすノードデータ７０をた
どっていくことにより、領域統合の過程を把握すること
ができるものである。

【００３３】図８は、Ｂ−木（ｔｒｅｅ）を表す図であ
る。このＢ−木８０は、対比強度尺度値をキー（検索項
目）としてリスト８１〜８６、・・・の中から対比強度
尺度の最小となる辺のデータを検索するために用いられ
るものである。すなわち、このＢ−木８０を参照するこ
とにより、ある頂点（クラスタ）と、この頂点に隣接し
た他の頂点とを結ぶ辺のなかから色度がもっとも類似し
たものを極めて少ないメモリアクセスで検索することが
可能となるものである。この図において、リスト８１〜
８６、・・・には辺のデータ５１のアドレスを指し示す
ポインタが書き込まれており、同一リストのポインタで
示される辺のデータ５１は同一の対比強度尺度値をもつ
ものである。これらのポインタは辺のデータ５１中の対
比強度尺度値５１１の昇順に対応して並んでいる。した
がって、最上位のリスト８１に登録されたポインタを調
べ、このポインタの示す辺のデータ５１を探し出すこと
により、対比強度尺度値が最小となる辺のデータ５１を
探索できるものである。なお、対比強度尺度値が同一と
なる辺が複数存在する場合には、同一のリストに複数の
ポインタが登録される。

【００３４】Ｂ−木８０の根のノードは４つのキー８１
１〜８１４からなり、さらにそれぞれのキーの前後に５
つのポインタ８２１〜８２５があり、各ポインタは一つ
のノードを指し、各キーは一つのリストをポイントす
る。これらは、全体として階層構造をなしている。根の
５つのポインタ８２１〜８２５はそれぞれ、キー８１１
より小さいキー、キー８１１より大きくキー８１２より
小さいキー、キー８１２より大きくキー８１２より小さ
いキー、キー８１２より大きくキー８１３より小さいキ
ー、・・・、キー８１４より大きいキーのようにデータ
が分割して割り当てられ、これらの各ポインタに接続さ
れた各ノードには、さらにデータが分割して割り当てら
れている。従って、各層ごとに最上位のノード８０１、
８０２、８０３をたどっていくことにより、最小の対比
強度尺度値を示す辺のデータへのポインタのリスト８１
を探索することができるものである。なお、Ｂ−木８０
は、リスト８１、・・・の追加、削除が容易であるとい
う利点を備えている。また、同一リスト内に複数の対比
強度尺度値が登録されている場合、このうちの一つが削
除されたとしても、リストが空になるまでそのキーは削
除されることはない。すなわち、Ｂ−木８０は常に平衡
状態を保つため、高速の検索が可能となる。

【００３５】続いて、本実施例に係る画像処理装置にお
ける階層的クラスタリング処理、すなわち各クラスタを
１つのクラスタに統合するまでの作用を説明する。図４
は本実施例に係る画像処理装置の領域統合の処理を表す
フローチャートである。先ず、ＣＰＵ１１は入力Ｉ／Ｆ
１２を介して画像データを入力し、これを画像メモリ１
５に記憶させる。ここで、図２に示される画像データ２
１が入力されたとする。実際の画像データはこれよりは
るかに画素数が多いが、ここでは３×３の画素の画像デ
ータ２１を例に説明を進める。

【００３６】ステップＳ４１において、ＣＰＵ１１は画
像データ２１に基づき、頂点のデータ５０、辺のデータ
５１、ノードデータ７０を算出することにより、いわゆ
る格子グラフを生成する（ステップＳ４１）。このステ
ップＳ４１の処理を詳細に表したものが、ステップＳ４
１１、Ｓ４１２のサブルーチンである。

【００３７】ステップＳ４１１において、ＣＰＵ１１は
画像データ２１の各画素についての頂点のデータを算出
する。頂点のデータ５０は上述したように、ラベル５０
１、Ｌ^*ａ^*ｂ^*色空間における各色成分の平均値５０２
〜５０４、サンプル数５０５、リストへのポインタ５０
６、二分木へのポインタ５０７により構成されるもので
ある。なお、この時点では領域統合は行われてないた
め、ラベル５０１は各画素の画像データ上の座標値とな
り、サンプル数５０５は”１”となる。また、各色成分
の平均値５０２〜５０４は画素毎のＬ^*ａ^*ｂ^*色空間上
の座標値となる。

【００３８】さらに、ＣＰＵ１１は各画素について、二
分木のノードデータ７０を登録する。このとき、領域統
合は行われていないためいわゆるサブツリーは存在せ
ず、よってサブツリーへのポインタ７０６、７０７は空
欄（ゼロ）となる。また、クラスタの分散の変化を表す
対比強度尺度値７０５も空欄（ゼロ）となる。

【００３９】ステップＳ４１２において、ＣＰＵ１１は
辺のデータ５１を以下の手順で算出する。先ず、ＣＰＵ
１１は、画像データ２１中の画素２１０に着目し、この
画素２１０と、画素２１０に隣接する（例えば４近傍）
画素２１１〜２１４との間のＬ^*ａ^*ｂ^*色空間上におけ
る対比強度尺度値を求める。すなわち、ＣＰＵ１１はス
テップＳ４１１で算出された頂点データ５０中のＬ^*ａ^*
ｂ^*の各色成分５０２〜５０４に基づき、画素２１０と
画素２１１〜２１４との各画素間における各色成分５０
２〜５０４の分散の変化を調べる。これらの分散の変化
が対比強尺度値５１１として辺のデータ５１に登録され
るものである。また、辺のデータ５１のポインタ５１
２、５１３には辺の両端にある頂点のデータ５０のアド
レスが書き込まれる。このようにして、画素２１０を中
心とした４つの辺のデータ５１が生成されるものであ
る。

【００４０】ＣＰＵ１１は、このようにして生成された
辺のデータ５１を図８のＢ−木８０にキーと辺のデータ
へのポインタを登録する。すなわち、ＣＰＵ１１は、対
比強度尺度値の小さい順に辺のデータ５１のポインタを
登録し、リスト８１、・・・・が完成する。以上のステ
ップＳ４１１、Ｓ４１２の処理により、頂点および辺の
データよりなる初期格子グラフが完成する（ステップＳ
４１）。

【００４１】続いて、ＣＰＵ１１はステップＳ４２の判
断を実行する。このとき、領域統合は行われていないた
め、画素数がそのまま総クラスタ数となる。したがっ
て、ステップＳ４２の判断結果はＮＯとなり、次のステ
ップＳ４３が実行される。ステップＳ４３において、Ｃ
ＰＵ１１はＢ−木８０を参照し、リスト８１、・・・の
中から対比強度尺度値が最小となる辺のデータ５１を検
索する。検索が終了すると、ＣＰＵ１１はリスト８１を
先出し、または、後出し、もしくは何らかの規定に従っ
てリスト全体から削除する。

【００４２】対比強度尺度値の最小となる辺のデータ５
１が検索されろと、ＣＰＵ１１はこの辺のデータ５１の
両端にある頂点を統合する。例えば、画素２１０と画素
２１１との対比強度尺度値が最小であったとすると、画
素２１０と画素２１１との統合が行われる。これに伴
い、ＣＰＵ１１は頂点のデータ５０、辺のデータ５１、
二分木のデータ７０等を更新する（ステップＳ４４）。

【００４３】頂点のデータ５０の更新処理を以下に説明
する。ＣＰＵ１１は、ステップＳ４３において統合され
た画素２１０、２１１のそれぞれに対応する２つの頂点
のデータ５０を読み出し、いずれか一方の頂点のデータ
５０を他方の頂点のデータ５０に統合する。例えば、画
素２１０に係る頂点のデータ５０を画素２１１に係る頂
点のデータに統合したとする。２つの画素２１０、２１
１が一つのクラスタに統合された結果、統合後のクラス
タのＬ^*ａ^*ｂ^*色空間上における各色成分の平均値５０
２〜５０４は変動する。したがって、ＣＰＵ１１は統合
されたクラスタにおける各色成分の平均値５０２〜５０
４を、画素２１０に係る頂点のデータ５０に登録する。

【００４４】頂点のデータ５０中の二分木へのポインタ
５０７は、以下のように更新される。先ず、ＣＰＵ１１
は新たなノードデータ７０を生成し、画素２１０に係る
頂点のデータ５０中のポインタ５０７を新たなノードデ
ータ７０のポインタ７０６に、画素２１１に係る頂点の
データ中のポインタ５０７を新たなノードデータ７０の
ポインタ７０７にそれぞれ登録する。また、ＣＰＵ１１
は、画素２１０に係るラベル５０１を新たなノードデー
タ７０のラベル７０１に、画素２１０、２１１に係る色
成分５０２〜５０４の平均値を新たなノードデータ７０
の色成分７０２〜７０４に、画素２１０、２１１を結ぶ
辺のデータ５１中の対比強度尺度値５１１を新たなノー
ドデータ７０の対比強度尺度値７０５にそれぞれ登録す
る。

【００４５】辺のデータ５１の更新処理を以下に説明す
る。先ず、画素２１０、２１１の双方のリスト６０から
頂点２１０、２１１に係る辺のデータを削除する。２つ
の頂点を統合した場合、各頂点が保有していた情報が重
複してしまうことがある。そこで、リストデータ６０、
Ｂ−木８０中の重複したデータを削除する。画素２１
０、２１１を統合する第１回目の領域統合の段階におい
ては、画素２１０、２１１が重複して連結する辺が存在
しないため、かかる処理は必要がない。新たに統合され
た領域に対する非類似度の更新を、これに隣接するすべ
ての領域について行う。

【００４６】以上により、画素２１０、２１１が一つの
頂点（クラスタ）２１６に統合される。この後、ＣＰＵ
１１はステップＳ４２に戻り、Ｓ４２〜Ｓ４４の処理を
繰り返し実行する。このようにして、画像データ２１の
領域統合の段階で、例えば図３に示されるようにそれぞ
れ複数の画素を有するクラスタＰ、Ｑ、Ｒが生成された
とする。以下、これらのクラスタＰ、Ｑ、Ｒについての
処理を説明する。

【００４７】ステップＳ４３において、ＣＰＵ１１はＢ
−木８０を参照し、リスト８１、・・・の中から対比強
度尺度値が最小となる辺のデータ５１を検索する。検索
が終了すると、ＣＰＵ１１は、リストからその検索され
た他の登録を削除し、リストが空であれば、そのキーを
Ｂ−木から削除する。対比強度尺度値の最小となる辺の
データ５１が検索されろと、ＣＰＵ１１はこの辺のデー
タ５１の両端にある頂点を統合する。例えば、クラスタ
ＰとクラスタＱとの対比強度尺度値が最小であったとす
ると、クラスタＰとクラスタＱとの統合が行われる。こ
れに伴い、ＣＰＵ１１は頂点のデータ５０、辺のデータ
５１、二分木のデータ７０等を更新する（ステップＳ４
４）。

【００４８】頂点のデータ５０の更新処理を以下に説明
する。ＣＰＵ１１は、ステップＳ４３において統合され
たクラスタＰ、Ｑのそれぞれに対応する２つの頂点のデ
ータ５０を読み出し、いずれか一方の頂点のデータ５０
を他方の頂点のデータ５０に統合する。例えば、クラス
タＰに係る頂点のデータ５０をクラスタＱに係る頂点の
データに統合したとする。２つのクラスタＰ、Ｑが一つ
のクラスタに統合された結果、統合後のクラスタのＬ^*
ａ^*ｂ^*色空間上における各色成分の平均値５０２〜５０
４は変動する。したがって、ＣＰＵ１１は統合されたク
ラスタにおける各色成分の平均値５０２〜５０４を、ク
ラスタＱに係る頂点のデータ５０に登録する。

【００４９】頂点のデータ５０中の二分木へのポインタ
５０７は、以下のように更新される。先ず、ＣＰＵ１１
は新たなノードデータ７０を生成し、クラスタＰに係る
頂点のデータ５０中のポインタ５０７を新たなノードデ
ータ７０のポインタ７０６に、クラスタＱに係る頂点の
データ中のポインタ５０７を新たなノードデータ７０の
ポインタ７０７にそれぞれ登録する。また、ＣＰＵ１１
は、クラスタＰに係るラベル５０１を新たなノードデー
タ７０のラベル７０１に、クラスタＰ、Ｑに係る色成分
５０２〜５０４の平均値を新たなノードデータ７０の色
成分７０２〜７０４に、クラスタＰ、Ｑを結ぶ辺のデー
タ５１中の対比強度尺度値５１１を新たなノードデータ
７０の対比強度尺度値７０５にそれぞれ登録する。

【００５０】辺のデータ５１の更新処理を図３を参照し
ながら以下に説明する。先ず、ＣＰＵ１１は、頂点Ｐ、
Ｑを結ぶ辺ＰＱを示すポインタ６０１をリストデータ６
０から削除する。また、頂点Ｐ、Ｑがともに連結する頂
点Ｒが存在する場合、ＣＰＵ１１は頂点Ｐ、Ｑに関する
リストデータ６０から、辺ＱＲＲまたは辺ＲＰのポイン
タ６０１を削除し、Ｂ−木８０から辺ＱＲまたは辺ＲＰ
に関するデータを削除する。さらに、ＣＰＵ１１は頂点
Ｐに連結する辺のポインタ６０１を頂点Ｑのそれにマー
ジする。以上の処理により重複したデータの削除等が行
われ、辺のデータ５１に関する更新処理が終了する。

【００５１】さらに、原点Ｐ、Ｑと連結していた他の頂
点Ｔとの辺のデータ５１中の対比強度尺度値５１１は、
統合後のＰおよびＴのＬ^*ａ^*ｂ^*の平均値と構成画素数
に基づき更新処理される（図３中段の式）。この処理
は、上述した頂点データ５０の更新処理におけるものと
同様である。統合後の新たな対比強度尺度値５１１の更
新に際し、更新されるべき辺のデータは一時Ｂ−木から
削除され、対比強度尺度値５１１が更新されると、ＣＰ
Ｕ１１は新たな対比強度尺度値５１１をキーとしてデー
タ５１へのポインタをＢ−木８０に再登録する。

【００５２】以上により、ステップＳ４４の処理が終了
する。この後、ＣＰＵ１１はステップＳ４２に戻り、画
像データ２１の総クラスタ数が”１”になるまでステッ
プＳ４２〜Ｓ４４の処理を繰り返し実行する。総クラス
タ数が”１”になった時点で、領域統合処理は終了す
る。この結果、画像データ２１は１つの頂点（クラス
タ）２５０に統合されるものである。

【００５３】なお、上述した領域統合処理は、一のクラ
スタに他のクラスタを順次統合させるものであるが、領
域統合を画像データの局所において並列に行うことも可
能である。このような並列処理はとくに初期の統合過程
において有効である。

【００５４】図４のフローチャートで表された処理によ
る領域統合が終了すると、ＣＰＵ１１は統合履歴を表す
二分木のノードデータ７０をワークメモリ１４から外部
記憶装置１７に書き込む。なお、二分木を構成するノー
ドデータ７０の数は画像データの総画素数の約２倍とな
ることから、二分木のデータ数は膨大な数に達する。し
たがって、ワークメモリ１４上に配置された二分木のデ
ータの全ての二分木探索を行っていたのでは、メモリア
クセスが膨大となる。そこで、本実施例においては、二
分木を構成するノードデータ７０毎に、これを二分木探
索の順に外部記憶装置１７に書き込み、読み出し時には
これと逆の順序でノードデータ７０毎に外部記憶装置１
７からワークメモリ１４に転送する。これにより、ワー
クメモリへの二分木再配置のためのメモリアクセスを大
幅に低減することが可能となるものである。以下に、外
部記憶装置１７に対するルートノードからの書き込みお
よび読み込み時の処理を図７に基づき説明する。

【００５５】書き込み時においては、ルートノードまた
は所定のノードを始点として以下の処理を再帰的に実行
する。先ず、始点となるノードデータ７０中のラベル７
０１、Ｌ^*ａ^*ｂ^*の各平均値７０２〜７０４、対比強度
尺度値７０５を外部記憶装置１７に書き込む。次に、Ｃ
ＰＵ１１はこのノードデータ７０サブツリーへのポイン
タ７０６を参照し、サブツリーへのポインタ７０６が空
欄でなければ、サブツリー７０６が示す次のノードデー
タ７０を外部記憶装置１７に書き込む。ポインタ７０６
が空欄である場合には、このポインタ７０６が書き込ま
れたノードデータ７０が「葉」である旨を外部記憶装置
１７に書き込み一つ上の親ノードに戻り、ポインタ７０
７についても同様の処理を行う。以上の処理を繰り返す
ことにより、ノードデータ７０が二分木探索の順に外部
記憶装置１７に書き込まれるものである。

【００５６】なお、上記書き込み処理において、二分木
の「葉」となるノードデータ７０の判別をサブツリーへ
のポインタ７０６、７０７が空欄か否かにより行ってい
るが、対比強度尺度値７０５が空欄か否かにより行って
もよい。また、ノードデータ７０に対応する頂点データ
５０中のサンプル数５０５が”１”になったことをもっ
て当該ノードデータ７０が「葉」であることを判断して
もよい。

【００５７】続いて、ノードデータ７０の読み込み処理
を説明する。先ず、ＣＰＵ１１はワークメモリ１４上に
ノードデータ７０の領域を確保し、ここに外部記憶装置
１７から読み出された始点となるノードデータ７０中の
各データを転送する。次にワークメモリ１４から読み出
されるノードデータはこのノードデータ７０のポインタ
７０６がポイントするものとして新たなノードデータ７
０を確保し、そこにワークメモリ１４からのデータを読
み込む。このとき、読み込まれたデータが「葉」でなけ
れば、ノードデータ７０のポインタ７０６について同様
の処理を繰り返す。「葉」である場合には、このノード
データ７０のポインタ７０６、７０７を空欄として一つ
上のノードに戻り、そのノードのポインタ７０７にポイ
ントされるものとして新たなノードデータ７０の確保
と、ワークメモリ１４からのデータの読み込みを行い、
このノードデータ７０のワークメモリ７０６について処
理を継続する。

【００５８】続いて、この二分木をもとにした領域抽出
の処理について説明する。上述した領域統合処理によ
り、図２の（Ａ）に示されるように画像データは最終的
に１つのクラスタ（頂点）２５０に統合された。この領
域統合の過程を逆にたどることにより、図２の（Ｂ）に
示されるように、画像データ２１を分割した画像データ
２２を得ることが可能である。すなわち、背景、人物等
を表す画像データを、背景の画像領域、人物の画像領域
等に分割し、所望の画像領域を抽出することができるも
のである。

【００５９】二分木（履歴データ）をルートノードから
「葉」に向かってたどっていくことにより、１のクラス
タを順次２つのクラスタに分割することができるわけで
あるが、二分木をどの深さまでたどるかを以下の手順で
予め決定しておく。先ず、分割を終了させる条件として
対比強度尺度値の下限（類似度の範囲）を、オペレータ
が画像処理装置に与えておく。すなわち、二分木に従い
一つのクラスタを分割していく過程において、各クラス
タの色度がある程度近似したならば分割処理を中止させ
る。これにより、画像を特徴の全く相違する領域毎に分
割することができるものである。

【００６０】対比強度尺度値の下限値が画像処理装置に
与えられると、ＣＰＵ１１はルートのノードデータ７０
中の対比強度尺度値７０５が指示された下限値より小さ
いか否かを判断する。このとき、対比強度尺度値７０５
が下限値より小さい（類似度が所定値以上）場合には処
理を終了する。一方、対比強度尺度値７０５が下限値よ
りも大きい（類似度が所定値以下）場合には、ＣＰＵ１
１はノードデータ７０中のポインタ７０６、７０７を参
照する。そして、ポインタ７０６、７０７が空欄である
場合（サブツリーが存在しない場合）には、ＣＰＵ１１
は処理を終了する。ポインタ７０６、７０７が空欄でな
い場合には、ポインタ７０６、７０７で示されたサブツ
リーのノードデータ７０を参照する。このサブツリーの
対比強度尺度値７０５が下限値よりも小さい場合には処
理を終了する。これらの処理を繰り返すことにより、二
分木が限定される（二分木の枝が途中で切断される）も
のである。このようにして限定された二分木の「葉」に
よって示される各クラスタは、ある程度特徴が相違した
ものとなっている。

【００６１】図２の（Ｂ）に示されるように、ノード２
５０をルートとする二分木は画像データ２１の各画素に
向かって延びているが、この二分木を途中で切断するこ
とにより、４つのクラスタを「葉」とする二分木が得ら
れるものである。

【００６２】このようにして限定された二分木の各葉
を、それ以下のサブツリーのルートノードとして、分割
された領域を示す領域指定データを生成する。なお、こ
の領域指定データは画像データ２１に対応した座標値を
持つ二次元データである。先ず、ＣＰＵ１１はルートノ
ードのポインタ７０６、７０７を参照する。ポインタ７
０６、７０７が空欄である場合には、ＣＰＵ１１はラベ
ル７０１から実画像におけるｘ、ｙ座標を算出し、この
ｘ、ｙ座標に対応した領域指定データの座標にラベル７
０１を書き込む。ポインタ７０６、７０７が空欄でない
場合には、ポインタ７０６、７０７で示されたサブツリ
ーのノードデータ７０を参照し、上記と同様の処理を繰
り返していく。このような処理により、分割された各領
域にラベル７０１が付されるものである。また、各領域
に付されたラベル７０１を基に、画像データ２１から所
望の領域を抽出することが可能となるものである。例え
ば、人物と背景とを表す画像データから、人物を表す領
域のみを抽出することができるものである。

【００６３】本実施例の画像処理装置により領域分割さ
れた画像の一例を図９および図１０に示す。図９は原画
像を表している。図１０はこの画像を領域分割したデー
タを表している。図９の原画像の階層的クラスタリング
を行うことにより、図１０の（Ａ）、（Ｂ）、（Ｃ）の
ように、順にクラスタが統合されていくものである。図
１１は、図９の原画像を領域統合する過程を表したツリ
ーである。このツリーの横軸は領域統合の非類似度を対
数で表したものである。また、図１１に付された矢印
（Ａ）、（Ｂ）、（Ｃ）の各段階の画像が、図１０の
（Ａ）、（Ｂ）、（Ｃ）にそれぞれ対応している。図１
３、図１４、図１５は、それぞれ図１０の（Ａ）、
（Ｂ）、（Ｃ）に対応しており、領域統合の各段階にお
ける頂点および辺を示すグラフである。図１３は同図の
矢印（Ａ）の段階のグラフであり、図１４は同図の矢印
（Ｂ）の段階のグラフである。さらに、図１５は同図の
矢印（Ｃ）の段階のグラフを表している。図１２は、原
画像１２１（図９に示されたものと同一）を領域統合す
る各段階の画像１２１〜１２６を示している。この図の
画像１２３、１２４、１２５は、図１０の（Ａ）、
（Ｂ）、（Ｃ）に対応している。

【００６４】以上述べたように、本実施例によれば、隣
接するクラスタ対のうち、色空間上の対比強度尺度値の
最小となる（類似度の最大となる）もの同士を統合する
ことにより階層的クラスタリングを行っている。したが
って、領域統合の判断を隣接するクラスタについてのみ
行えばよいため、処理時間を大幅に短縮できるとともに
処理に要するメモリ容量を軽減できる。

【００６５】また、Ｌ^*ａ^*ｂ^*色空間上の分散変化の最
小となるクラスタ同士を統合するため、大局的な対比関
係を捉えるという視覚特性に合致した領域分割が可能と
なるものである。例えば、写真、映像、印刷等の分野に
おいては、階調を「ライト、中間、シャドウ」のように
主観的に分類することがある。本実施例によれば、視覚
特性に合致したＬ^*ａ^*ｂ^*色空間を用いて領域分割を行
っているため「ライト、中間、シャドウ」のような主観
的な画像の分割が可能となるものである。

【００６６】なお、Ｌ^*ａ^*ｂ^*色空間の他、Ｕ^*Ｖ^*Ｗ色
空間、Ｌ^*ｕ^*ｖ色空間等の色空間を使用することも可能
である。色空間上の各成分に重み付けを持たして、対比
強度尺度値を算出することにより、明度、色相、彩度の
いずれを重視した領域分割を行うかを適宜選択してもよ
い。また、本実施例においては、４近傍の画素について
領域統合を行っているが、８近傍の画素について領域統
合を行ってもよい。

【００６７】

【発明の効果】以上説明したように、本発明にあって
は、色空間上の座標および実画像上の座標等を考慮して
階層的クラスタリングを行っている。したがって、画像
の明度・色相・彩度等を総合的にとらえることができ、
視覚特性に合わせて画像を「ライト、中間、シャドウ」
の各領域に分割することができる。

【００６８】また、隣接するクラスタ対のうち、色空間
上の対比強度尺度値の最小（類似度が最大）となるもの
同士を統合することにより、領域統合の判断対象となる
クラスタ対を限定することができ、クラスタ分割の処理
時間および画像処理装置の負担を軽減することが可能と
なる。また、実画像上において隣接する画素対を統合す
るため、統合された領域に不連続な部分が生じることも
ない。

【図面の簡単な説明】

【図１】本発明の一実施例に係る画像処理装置のブロッ
ク図である。

【図２】本発明の一実施例に係る画像データ、グラフ構
造のデータ等を表す図である。

【図３】本発明の一実施例に係る対比強度尺度値の計算
式およびＬ^*ａ^*ｂ^*色空間色空間を表す図である。

【図４】本発明の一実施例に係る画像処理装置の領域統
合処理を表すフローチャートである。

【図５】本発明の一実施例に係る頂点のデータ、辺のデ
ータを表す図である

【図６】本発明の一実施例に係る頂点のデータ、辺のデ
ータ、リストデータを表す図である。

【図７】本発明の一実施例に係る頂点のデータ、ノード
データを表す図である。

【図８】本発明の一実施例に係るＢ−木等を表す図であ
る。

【図９】本発明の一実施例に係る画像データを表す図で
ある。

【図１０】本発明の一実施例に係る領域分割された画像
データを示す図である。

【図１１】本発明の一実施例に係る領域統合を表すツリ
ーである。

【図１２】本発明の一実施例に係る領域分割された画像
データを示す図である。

【図１３】本発明の一実施例に係る領域統合過程におけ
る頂点および辺を表すグラフである。

【図１４】本発明の一実施例に係る領域統合過程におけ
る頂点および辺を表すグラフである。

【図１５】本発明の一実施例に係る領域統合過程におけ
る頂点および辺を表すグラフである。

【符号の説明】

１１ＣＰＵ７０ノードデータ（履歴データ）５１１、７０５対比強度尺度値（類似度）

Claims

【特許請求の範囲】

【請求項１】画像データ中の対比される２つの領域の
類似度を、色空間上における当該２つの領域の座標に基
づき算出し、上記画像データ中の一の領域に隣接した複数の他の領域
のうち、当該一の領域との類似度が最大となる他の領域
を当該一の領域に順次統合することを特徴とする画像処
理方法。
【請求項２】画像データ中の対比される２つの領域の
類似度を、色空間上における当該２つの領域の座標に基
づき算出し、上記画像データ中の一の領域に隣接した複数の他の領域
のうち、当該一の領域との類似度が最大となる他の領域
を当該一の領域に順次統合し、領域統合の順序および領域統合された領域間の類似度を
表す履歴データを生成し、上記履歴データに従い領域統合された画像データのう
ち、所定範囲の類似度の領域対を、領域統合の順序と逆
の順序で順次分割することを特徴とする画像処理方法。
【請求項３】請求項１または請求項２記載の類似度を
画像データ中の対比される２つの領域を統合したことに
よる色空間上における各領域の分散または重心の変化に
基づき算出することを特徴とする画像処理方法。
【請求項４】画像データを構成する各領域を頂点とみ
なし、隣接し合う２つの頂点の類似度を色空間上における２つ
の頂点の座標に基づき算出し、算出された類似度を上記２つの頂点を連結する辺とみな
し、一の頂点に連結された複数の辺のなかから、類似度が最
大となる辺を検索するとともに、検索された辺に連結さ
れた他の頂点を上記一の頂点に統合する処理を繰り返す
ことを特徴とする画像処理方法。