JPH1115971A

JPH1115971A - 画像領域分割方法および画像領域分割装置

Info

Publication number: JPH1115971A
Application number: JP9162563A
Authority: JP
Inventors: Ryosuke Toho; 良介東方
Original assignee: Fuji Xerox Co Ltd
Current assignee: Fujifilm Business Innovation Corp
Priority date: 1997-06-19
Filing date: 1997-06-19
Publication date: 1999-01-22
Anticipated expiration: 2017-06-19
Also published as: JP3611006B2

Abstract

(57)【要約】【課題】不自然な領域分割となることなく、高速に画
像を領域分割できるようにする。【解決手段】分割対象の入力画像を、格子線によっ
て、複数のブロック画像ｆ１１，ｆ１２‥‥に分割す
る。最初に、ブロック画像ｆ１１に含まれる画素のみ
を、対象部分画像として抽出して領域分割し、領域Ａａ
〜Ａｄを算出する。次に、ブロック画像ｆ１２に含まれ
る画素、およびブロック画像ｆ１２に隣接する算出済み
の領域Ａｂ，Ａｃに含まれる画素を、対象部分画像とし
て抽出して領域分割し、修正された領域Ａｂ，Ａｃと新
たな領域Ａｅ〜Ａｈを算出する。以下、同様である。そ
れぞれの領域分割では、対象部分画像の画素を所定の間
引き率で間引いた間引き部分画像を領域分割することが
できる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、量子化された多
階調の画像データで表現された画像を領域分割する画像
領域分割方法および画像領域分割装置に関する。

【０００２】

【従来の技術】イメージスキャナにより読み取られた画
像やコンピュータにより生成された画像などの画像を領
域分割することは、画像処理のさまざまな分野で前処理
として利用されている。

【０００３】例えば、画像編集処理では、編集する領域
を自動的に切り出すために、領域分割が用いられる。ま
た、画像認識処理では、認識対象物を見つけ出すため
に、領域分割が用いられる。さらに、画像の部分的なテ
クスチャや色の分布状態などが類似する領域ごとに異な
る画像処理を行う場合などにも、領域分割を利用するこ
とができる。

【０００４】このような場合の領域分割は、その性能の
良否が画像処理全体の性能を大きく左右することになる
ので、性能のよい領域分割方法によることが要求され
る。

【０００５】領域分割の方法としては、古くから知られ
ているＫ平均アルゴリズム（Ｋ平均クラスタ化アルゴリ
ズム）がある（例えば、中谷ほか「複数の領域分割結果
に基づく対象物境界線検出」電子情報通信学会論文誌Ｄ
２，Ｖｏｌ．Ｊ７６−Ｄ２，Ｎｏ４，ｐｐ．９１４−９
１６，’９３／４）。

【０００６】また、画像の色ベクトルのＲＧＢ（赤、
緑、青）などの３成分に画像平面におけるＸＹ座標を加
えた５次元特徴空間上でＫ平均アルゴリズムを行う方法
も提案されている（泉ほか「色情報と位置情報とを併用
したセグメンテーション手法の一検討」１９９１年電子
情報通信学会春季全国大会予稿集Ｄ−６８０）。

【０００７】さらに、特開平８−３０７８７号には、分
割対象の画像を、複数のブロック領域と、それぞれのブ
ロック領域の間に位置する境界領域とに分けて、それぞ
れのブロック領域の領域分割に当たって、そのブロック
領域と接する境界領域を一緒に領域分割することによっ
て、小容量のメモリにより、短時間で高速に、ブロック
領域間の不整合がなく、画像を領域分割する方法が提案
されている。

【０００８】

【発明が解決しようとする課題】Ｋ平均アルゴリズムに
よる領域分割は、画像中の各画素を適切な領域に配分す
る処理を所定状態に収束するまで繰り返し、少しずつよ
りよい領域を求めていく方法である。そのため、用いる
特徴空間に応じた領域を高い精度で求めることができ
る。しかしながら、分割領域を少しずつよりよい領域に
収束させていくため、処理に膨大な時間が必要となる。

【０００９】特開平８−３０７８７号によって提案され
た方法は、その処理時間を激減させることができるが、
それでもかなりの時間を必要とする。また、この方法で
は、境界領域を小さく設定すると、境界領域が適切に作
用しないで、不自然な領域分割が行われてしまう可能性
があり、逆に境界領域を大きく設定すると、境界領域の
効果が薄れて、処理時間が長くなってしまう欠点があ
る。

【００１０】そこで、この発明の第１の目的は、より高
速に画像を領域分割できるようにすることにある。

【００１１】この発明の第２の目的は、不自然な領域分
割となることなく、高速に画像を領域分割できるように
することにある。

【００１２】

【課題を解決するための手段】請求項１の発明では、画
像領域分割方法として、量子化された多階調の入力画像
データで表現された分割対象の入力画像を所定の間引き
率で間引いた間引き画像を領域分割して、前記入力画像
の領域の数および中心を算出する領域算出ステップと、
この領域算出ステップで算出された領域に前記入力画像
に含まれるすべての画素を配分する領域確定ステップ
と、を設ける。

【００１３】この場合、前記領域算出ステップは、前記
入力画像を第１の間引き率で間引いた第１の間引き画像
を領域分割して、前記入力画像の領域のおおよその数お
よび中心を推定する領域推定ステップと、この領域推定
ステップで推定された領域の数および中心を用いて、前
記入力画像を前記第１の間引き率より小さい第２の間引
き率で間引いた第２の間引き画像を領域分割して、前記
入力画像の領域の数および中心を算出する領域生成ステ
ップと、を有するものとすることが好ましい。

【００１４】請求項３の発明では、画像領域分割方法と
して、量子化された多階調の入力画像データで表現され
た分割対象の入力画像を複数のブロック画像に分割した
ときの、注目ブロック画像およびこれに隣接する算出済
みの領域に含まれる画素からなる対象部分画像を領域分
割する部分画像領域分割ステップを、前記複数のブロッ
ク画像中の異なるブロック画像を順次、前記注目ブロッ
ク画像として繰り返し行って、前記入力画像を領域分割
する。

【００１５】この場合、前記部分画像領域分割ステップ
は、前記対象部分画像を所定の間引き率で間引いた間引
き部分画像を領域分割して、前記対象部分画像の領域の
数および中心を算出する領域算出ステップと、この領域
算出ステップで算出された領域に前記対象部分画像に含
まれるすべての画素を配分する領域確定ステップと、を
備えるものとすることが好ましい。

【００１６】さらに、この場合、前記領域算出ステップ
は、前記対象部分画像を第１の間引き率で間引いた第１
の間引き部分画像を領域分割して、前記対象部分画像の
領域のおおよその数および中心を推定する領域推定ステ
ップと、この領域推定ステップで推定された領域の数お
よび中心を用いて、前記対象部分画像を前記第１の間引
き率より小さい第２の間引き率で間引いた第２の間引き
部分画像を領域分割して、前記対象部分画像の領域の数
および中心を算出する領域生成ステップと、を有するも
のとすることが望ましい。

【００１７】請求項１５の発明では、Ｋ平均アルゴリズ
ムによって画像を領域分割する方法において、対象画素
からの特徴空間上における距離が、あらかじめ定められ
た閾値より小さい領域中心を有する領域のみを探索の候
補とし、その探索候補の中から、対象画素を再配置すべ
き領域を探索する。

【００１８】この場合、探索候補が存在しない場合に
は、領域が収束する前に対象画素一つからなる領域を生
成することが望ましい。

【００１９】請求項１７の発明では、Ｋ平均アルゴリズ
ムによって画像を領域分割する方法において、特徴空間
上における、対象画素に最も近い距離を有する領域中心
と対象画素との距離が、あらかじめ定められた閾値以上
である場合には、領域が収束する前に対象画素一つから
なる領域を生成する。

【００２０】

【作用】上記の方法による請求項１の発明の画像領域分
割方法においては、入力画像が所定の間引き率で間引か
れた、入力画像の一部の画素しか含まない間引き画像に
よって、入力画像の領域の数および中心が算出され、そ
の算出された領域に入力画像に含まれるすべての画素が
配分される。したがって、領域の収束までに要する時間
が大幅に短縮され、入力画像が高速に領域分割される。

【００２１】この場合、間引き率のより大きい第１の間
引き画像により入力画像の領域のおおよその数および中
心を推定し、その推定結果を用いて、所定の間引き率の
第２の間引き画像により入力画像の領域の数および中心
を算出する場合には、当初から所定の間引き率の間引き
画像により入力画像の領域の数および中心を算出する場
合に比べて、領域の数および中心の算出に要する時間を
より短縮することができる。

【００２２】上記の方法による請求項３の発明の画像領
域分割方法においては、最初、例えば入力画像の左上に
位置する第１のブロック画像が注目ブロック画像とさ
れ、その第１のブロック画像に含まれる画素のみが、対
象部分画像として領域分割される。次に、例えば第１の
ブロック画像の右隣りに位置する第２のブロック画像が
注目ブロック画像とされ、その第２のブロック画像に含
まれる画素、および第１のブロック画像の算出済みの領
域のうちの第２のブロック画像に隣接する領域に含まれ
る画素が、対象部分画像として領域分割される。以降
も、同様である。

【００２３】したがって、各回の領域分割は、少ない画
素を少ない領域に分割するものとして高速で行うことが
でき、全体として、入力画像を高速に領域分割すること
ができる。また、ブロック画像に隣接する領域を重複し
て処理するので、ブロック画像間の不整合を生じること
がなく、不自然な領域分割となることがない。

【００２４】この場合、部分画像領域分割ステップを、
対象部分画像の間引きによる領域算出ステップと、領域
確定ステップとによって構成する場合には、領域分割を
より高速で行うことができる。さらに、その領域算出ス
テップを、より大きい間引き率による領域推定ステップ
と、所定の間引き率による領域生成ステップとによって
構成する場合には、領域分割をさらにより高速で行うこ
とができる。

【００２５】上記の方法による請求項１５の発明の画像
領域分割方法においては、対象画素を再配置すべき領域
の探索を効率化でき、領域分割を高速化することができ
る。この場合、探索候補が存在しないときには、領域が
収束する前に対象画素一つからなる領域を生成する場合
には、領域の収束までに要する時間を短縮することがで
きる。

【００２６】上記の方法による請求項１７の発明の画像
領域分割方法においても、同様に領域の収束までに要す
る時間を短縮することができる。

【００２７】

【発明の実施の形態】

〔第１の実施形態〕図１は、この発明の画像領域分割装
置の第１の実施形態を示し、画像の間引きを利用して入
力画像を領域分割する場合である。この実施形態の画像
領域分割装置は、画像入力部１０、領域推定部２０、領
域生成部３０および領域確定部４０によって構成され
る。

【００２８】画像入力部１０は、分割対象の入力画像Ｉ
ｉを示す量子化された多階調の入力画像データＤｉを得
るもので、用紙上やフィルム上の画像を読み取るイメー
ジスキャナ、被写体像を撮影するデジタルカメラ、ハー
ドディスクなどの記憶装置から、これに記憶されている
画像データを読み出す装置、ネットワークなどを介して
送信された画像データを受信して取り込む装置、または
コンピュータにより描画して画像データを生成する装置
などである。

【００２９】画像入力部１０では、必要に応じて、入力
画像データの表色系が以後の処理において用いられる表
色系に変換される。以下の例では、入力画像データは、
ＲＧＢ画像データとして得られてＬ^*ａ^*ｂ^*画像データ
に変換され、Ｌ^*，ａ^*，ｂ^*成分を有する色ベクトルの
２次元マップで表現されるものとする。また、画像入力
部１０は、必要に応じて、入力画像データの一部または
全部を記憶するメモリなどの記憶装置を備えるものとす
る。

【００３０】領域推定部２０は、上記の入力画像データ
で表現された入力画像を、あらかじめ定められた間引き
率Ｒａで間引いた間引き画像を領域分割して、入力画像
の領域のおおよその数および中心を推定し、領域生成部
３０は、この領域推定部２０で推定された領域の数およ
び中心を用いて、入力画像を上記の間引き率Ｒａより小
さい間引き率Ｒｂで間引いた間引き画像を領域分割し
て、入力画像の領域の数および中心を算出する。以下の
例では、単純間引きを用いる場合を示す。

【００３１】図９（Ａ）に示すように、入力画像Ｉｉは
Ｘ方向（横方向）およびＹ方向（縦方向）に画素Ｐｉが
連続するもので、画像入力部１０からは、その画素Ｐｉ
をＸ方向およびＹ方向に間引き率Ｒａで間引いた、図９
（Ｂ）で塗り潰して示す画素Ｐａのような一部の画素か
らなる間引き画像Ｉａと、画素ＰｉをＸ方向およびＹ方
向に間引き率Ｒｂで間引いた、図９（Ｃ）で塗り潰して
示す画素Ｐｂのような一部の画素からなる間引き画像Ｉ
ｂとを得る。間引き率Ｒ（ＲａまたはＲｂ）は、Ｒ²個
に１個の画素を取り出すことを意味する。

【００３２】そして、領域推定部２０では、後述するよ
うに間引き画像Ｉａを領域分割して、入力画像Ｉｉの領
域のおおよその数および中心を推定し、領域生成部３０
では、その推定結果を用いて、後述するように間引き画
像Ｉｂを領域分割して、入力画像Ｉｉの領域の数および
中心を算出する。

【００３３】領域確定部４０は、後述するように、入力
画像Ｉｉに含まれるすべての画素を、領域生成部３０で
算出された領域のうちの最も適切な領域に配分する。

【００３４】図２は、図１の画像領域分割装置に対応す
る、この発明の画像領域分割方法の第１の実施形態を示
し、まず領域推定部２０でのステップＳ２０で、間引き
率Ｒａによる間引き画像を領域分割して、入力画像の領
域のおおよその数および中心を推定し、次に領域生成部
３０でのステップＳ３０で、その推定結果を用いて、間
引き率Ｒｂによる間引き画像を領域分割して、入力画像
の領域の数および中心を算出し、次に領域確定部４０で
のステップＳ４０で、その算出された領域に入力画像に
含まれるすべての画素を配分する。

【００３５】ステップＳ２０での領域推定、ステップＳ
３０での領域生成、およびステップＳ４０での領域確定
は、以下に示すように、Ｋ平均アルゴリズムに改良を加
えたクラスタリング手法によって行う。これは、図６〜
図８に示して後述する、この発明の画像領域分割方法の
第３の実施形態における対象部分画像を、入力画像その
ものに置き換えた場合と同じであるので、図６〜図８を
流用して示す。

【００３６】ステップＳ２０では、図６に示すように
（ただし、ステップＳ２０２の対象部分画像は入力画像
に置き換える）、まずステップＳ２０１で、クラスタ数
Ｋを適切に選んで、入力画像に対して初期領域中心を設
定し、次にステップＳ２０２で、入力画像の画素を間引
き率Ｒ＝Ｒａで間引いて一つ選択する。

【００３７】この画素の選択は、例えば、入力画像の画
素の特徴ベクトルＰ_n＝（Ｌ_n，ａ_n，ｂ_n，Ｘ_n，Ｙ_n）
（ただし、１≦ｎ≦入力画像の画素総数）から、次の式
（１）の条件を満たす画素を一つずつ順に選択すること
によって行う。

【００３８】Ｘ_nｍｏｄＲ＝Ｒ／２かつＹ_nｍｏｄＲ＝Ｒ／２ ‥‥（１）ここで、Ｌ_n，ａ_n，ｂ_nは、画素の色ベクトルの３成
分、上記の場合にはＬ^*，ａ^*，ｂ^*成分であり、Ｘ_n，Ｙ
_nは、画素の画像平面におけるＸ，Ｙ座標である。ま
た、ｍｏｄは余りを求める演算子で、式（１）における
除算の結果は小数点以下を切り捨てて整数値とする。

【００３９】次にステップＳ２０３で、その選択した画
素の特徴ベクトルＰ_nと各領域中心Ｖ_m＝（Ｌ_m，ａ_m，ｂ
_m，Ｘ_m，Ｙ_m）との距離ｄを計算して、選択した画素に
最も近い距離ｄ_minを有する領域中心を探索する。距離
ｄは、例えば、次の式（２）によって算出する。

【００４０】ｄ＝｛ｋ_L（Ｌ_n−Ｌ_m）＋ｋ_a（ａ_n−ａ_m）＋ｋ_b（ｂ_n−ｂ_m）＋ｋ_X（Ｘ_n−Ｘ_m）＋ｋ_Y（Ｙ_n−Ｙ_m）｝^1/2 ‥‥（２）ここで、Ｌ_m，ａ_m，ｂ_mは、領域中心Ｖｍの色ベクトル
のＬ^*，ａ^*，ｂ^*成分であり、Ｘ_m，Ｙ_mは、領域中心Ｖ
ｍの画像平面におけるＸ，Ｙ座標である。また、ｋ_L，
ｋ_a，ｋ_b，ｋ_X，ｋ_Yは、それぞれ、Ｌ^*成分、ａ^*成分、
ｂ^*成分、Ｘ座標、Ｙ座標に対応する特徴軸をスケーリ
ングするための係数である。この例では、座標より色ベ
クトル情報を重視するため、ｋ_L，ｋ_a，ｋ_b＝１に対し
て、０＜ｋ_X，ｋ_Y＜１に設定する。

【００４１】ただし、この例では、領域中心の探索を効
率化するため、選択した画素からの距離ｄが、あらかじ
め定められた閾値ｄ_thより小さい領域中心のみを探索の
候補とし、その探索候補の中から、選択した画素に最も
近い距離ｄ_minを有する領域中心を探索する。

【００４２】次にステップＳ２０４で、その最も近い距
離ｄ_minが、あらかじめ定められた閾値Ｔ_diff（Ｔ_diff
＜ｄ_th）より小さいか否かを判断して、選択した画素
を、その最も近い距離ｄ_minを有する領域中心の領域に
再配置できるか否かを判定する。

【００４３】すなわち、距離ｄ_minが閾値Ｔ_diffより小
さいときには、選択した画素を距離ｄ_minを有する領域
中心の領域に再配置できるとして、ステップＳ２０５に
進み、距離ｄ_minが閾値Ｔ_diff以上であるときには、選
択した画素を距離ｄ_minを有する領域中心の領域に再配
置できないとして、ステップＳ２０６に進む。

【００４４】また、ステップＳ２０３で、選択した画素
からの距離ｄが閾値ｄ_thより小さい探索候補の領域中心
が存在しなかったときにも、選択した画素を再配置すべ
き適当な領域中心が存在しないとして、ステップＳ２０
４からステップＳ２０６に進む。

【００４５】ステップＳ２０５では、その選択した画素
を、閾値Ｔ_diffより小さい範囲で最も近い距離ｄ_minを
有する領域中心の領域に配分する。

【００４６】ステップＳ２０６では、その選択した一つ
の画素からなる領域を新たに生成する。具体的には、選
択した一つの画素の色ベクトルのＬ^*，ａ^*，ｂ^*成分
と、その画素の画像平面におけるＸＹ座標とからなる特
徴ベクトルを生成して、これを領域中心とし、その領域
中心の領域に、選択した一つの画素を配分する。その結
果、領域中心ないし領域の総数は、一つ増加することに
なる。

【００４７】ステップＳ２０５で画素を再配置し、また
はステップＳ２０６で一つの画素からなる領域を新たに
生成したら、次にステップＳ２０７で、ステップＳ２０
２で選択すべき画素をすべて選択したか否かを判断し、
すべて選択していなければ、ステップＳ２０２に戻っ
て、次の選択すべき画素を選択して、その選択した画素
につき、ステップＳ２０３以降の処理を繰り返す。

【００４８】ステップＳ２０７で、ステップＳ２０２で
選択すべき画素をすべて選択したと判断したときには、
次にステップＳ２０８に進んで、ステップＳ２０５でそ
れぞれの領域中心の領域に再配置した画素の特徴ベクト
ルの平均を、それぞれの領域ごとに新たな領域中心とし
て算出する。

【００４９】次にステップＳ２０９で、その算出した新
たな領域中心を前の領域中心と置き換える。その際、新
たな領域中心と前の領域中心との特徴空間における距離
を、それぞれの領域ごとに算出し、その距離があらかじ
め定められた閾値以上であれば、領域がいまだ収束して
いないことを示すフラグを立てる。

【００５０】次にステップＳ２１０で、そのフラグが立
っていないか否かを見て、領域が収束したか否かを判断
し、フラグが立っていて、領域が収束していないときに
は、ステップＳ２１１に進んで、それぞれの領域中心の
領域から、これに再配置された画素を削除した上で、ス
テップＳ２０２に戻って、画素の選択から上記の処理を
繰り返す。

【００５１】ステップＳ２１０で、フラグが立っていな
いことにより、領域が収束したと判断したときには、領
域推定の処理を終了する。

【００５２】ステップＳ３０では、図７に示すように
（ただし、ステップＳ３０２の対象部分画像は入力画像
に置き換える）、まずステップＳ３０１で、初期領域中
心として、上記の領域推定ステップＳ２０で算出した領
域中心を設定する。ただし、それぞれの領域中心の領域
に再配置されている画素は削除しておく。

【００５３】次にステップＳ３０２で、入力画像の画素
を間引き率Ｒ＝Ｒｂ（Ｒｂ＜Ｒａ）で間引いて一つ選択
する。この画素の選択は、例えば、図６の領域推定ステ
ップＳ２０のステップＳ２０２での画素の選択と同様
に、上記の式（１）の条件を満たす画素を一つずつ順に
選択することによって行う。

【００５４】次のステップＳ３０３以降については、図
６の領域推定ステップＳ２０のステップＳ２０３以降と
同じである。

【００５５】ステップＳ４０では、図８に示すように
（ただし、ステップＳ４０２の対象部分画像は入力画像
に置き換える）、まずステップＳ４０１で、初期領域中
心として、上記の領域生成ステップＳ３０で算出した領
域中心を設定する。ただし、それぞれの領域中心の領域
に再配置されている画素は削除しておく。

【００５６】次にステップＳ４０２で、入力画像に含ま
れるすべての画素を一つずつ選択する。これは、間引き
率Ｒを１とすればよい。しかし、入力画像に含まれるす
べての画素を順に選択するにもかかわらず、上記の式
（１）の条件判断を行うのは、無駄である。したがっ
て、領域確定ステップＳ４０では、再配置のみを行うフ
ラグを作成しておいて、このフラグが立っていれば、入
力画像の画素を無条件に順に選択するように構成するこ
とができる。

【００５７】次にステップＳ４０３で、処理の効率化の
ために、領域推定ステップＳ２０のステップＳ２０３お
よび領域生成ステップＳ３０のステップＳ３０３とは違
って無条件で、選択した画素に最も近い距離を有する領
域中心を探索し、次にステップＳ４０５で、処理の効率
化のために、領域推定ステップＳ２０のステップＳ２０
４および領域生成ステップＳ３０のステップＳ３０４の
ような判断をすることなく、かつ領域推定ステップＳ２
０のステップＳ２０６および領域生成ステップＳ３０の
ステップＳ３０６のように選択した一つの画素からなる
領域を新たに生成することなく、選択した画素を、これ
に最も近い距離を有する領域中心の領域に配分する。

【００５８】この処理の効率と生成される領域の精度と
は、トレードオフの関係にあり、要求する分割内容に応
じて、領域生成ステップＳ３０における間引き率Ｒｂを
調整する。

【００５９】次にステップＳ４０７で、ステップＳ４０
２で入力画像のすべての画素を選択したか否かを判断
し、すべての画素を選択していなければ、ステップＳ４
０２に戻って、次の選択すべき画素を選択して、その選
択した画素につき、ステップＳ４０３以降の処理を繰り
返す。

【００６０】次のステップＳ４０８以降については、領
域推定ステップＳ２０のステップＳ２０８以降および領
域生成ステップＳ３０のステップＳ３０８以降と同じで
ある。

【００６１】上記の例は、領域推定ステップＳ２０およ
び領域生成ステップＳ３０で単純間引きを用いる場合で
あるが、入力画像の色分布の特徴をできるだけ保持し、
かつ入力画像より画素総数が少なくなる間引き方法であ
れば、いかなる間引き方法でもよく、例えば、入力画像
のＲ²（Ｒａ²またはＲｂ²）個の画素の平均値や中央値
を間引き画像として用いることができる。

【００６２】上述した第１の実施形態によれば、所定の
間引き率Ｒｂの間引き画像により入力画像の領域の数お
よび中心を算出し、その算出した領域に入力画像に含ま
れるすべての画素を配分するので、領域の収束までに要
する時間を大幅に短縮でき、入力画像を高速に領域分割
することができるとともに、領域の数および中心の算出
に当たっては、より大きい間引き率Ｒａの間引き画像に
より入力画像の領域のおおよその数および中心を推定
し、その推定結果を用いて、所定の間引き率Ｒｂの間引
き画像により入力画像の領域の数および中心を算出する
ので、当初から所定の間引き率Ｒｂの間引き画像により
入力画像の領域の数および中心を算出する場合に比べ
て、領域の数および中心の算出に要する時間をより短縮
することができる。

【００６３】〔第２の実施形態〕図３は、この発明の画
像領域分割装置の第２の実施形態を示し、画像のブロッ
ク化を利用して入力画像を領域分割する場合である。こ
の実施形態の画像領域分割装置は、画像入力部１０、対
象部分画像抽出部５０および部分画像領域分割部６０に
よって構成される。画像入力部１０は、図１のそれと同
じである。

【００６４】対象部分画像抽出部５０は、画像入力部１
０で入力画像データとして得られる入力画像を複数のブ
ロック画像に分割したときの、注目ブロック画像および
これに隣接する算出済みの領域に含まれる画素からなる
対象部分画像を、複数のブロック画像中の異なるブロッ
ク画像を順次、注目ブロック画像として、順次抽出す
る。ただし、対象部分画像は、画素の色ベクトルの３成
分と画素の画像平面におけるＸＹ座標とを保持するもの
とする。対象部分画像抽出部５０は、その抽出した対象
部分画像を一時的に記憶しておく記憶部を内部に備え
る。

【００６５】部分画像領域分割部６０は、この対象部分
画像抽出部５０で順次抽出された対象部分画像を順次、
領域分割する。また、部分画像領域分割部６０は、領域
分割によって算出した領域データを内部の記憶部に記憶
するとともに、すべてのブロック画像に対する処理が終
了したか否かを判定して、その判定出力を対象部分画像
抽出部５０に送出する。

【００６６】図４は、図３の画像領域分割装置に対応す
る、この発明の画像領域分割方法の第２の実施形態を示
し、まずステップＳ５０で、複数のブロック画像のうち
のあるものを注目ブロック画像として対象部分画像を抽
出し、次にステップＳ６０で、その対象部分画像を領域
分割し、次にステップＳ７０で、最後のブロック画像を
含む最終部分画像を領域分割したか否かを判断し、最終
部分画像を領域分割していなければ、ステップＳ５０に
戻って、次のブロック画像を注目ブロック画像として次
の対象部分画像を抽出し、ステップＳ６０で、その対象
部分画像を領域分割する。そして、ステップＳ７０で最
終部分画像を領域分割したと判断したときには、入力画
像の領域分割を終了する。

【００６７】入力画像は、例えば、図１０（Ｂ）に示す
ように、Ｘ方向に６分割、Ｙ方向に４分割し、総計２４
個のブロック画像ｆ１１，ｆ１２‥‥ｆ４５，ｆ４６に
分割する。そして、例えば、図１０（Ｃ）に示すよう
に、ｆ１１，ｆ１２……ｆ１６，ｆ２１，ｆ２２……ｆ
２６，ｆ３１，ｆ３２‥‥ｆ３６，ｆ４１，ｆ４２‥‥
ｆ４６の順序で注目ブロック画像とする。ただし、注目
ブロック画像とする順序は、これに限らず、任意にする
ことができる。また、２つ以上のブロック画像を同時に
注目ブロック画像として、並列に処理することも可能で
ある。

【００６８】注目ブロック画像は、例えば、以下のよう
にして抽出する。まず、図１０（Ｂ）に示すような入力
画像Ｉｉの幅（画素数）Ｗおよび高さ（画素数）Ｈを、
それぞれ、あらかじめ定められた一つのブロック画像の
Ｘ方向およびＹ方向のおおよその大きさ（画素数）Ｎｏ
で除して、小数点以下を切り捨てることにより、入力画
像ＩｉをＸ，Ｙ方向に分割したときのＸ，Ｙ方向の分割
数Ｎｘ，Ｎｙを算出する。

【００６９】次に、次の式（３）によって、注目ブロッ
ク画像として抽出する図１０（Ａ）に示すようなブロッ
ク画像ｆ_ij（１≦ｉ≦Ｎｘ，１≦ｊ≦Ｎｙ）の左上の画
素の座標（ｘ_i，ｙ_j）を算出し、式（４）によって、そ
のブロック画像ｆ_ijの幅（画素数）ｗ_ijおよび高さ（画
素数）ｈ_ijを算出する。

【００７０】（ｘ_i，ｙ_j）＝（Ｗ（ｉ−１）／Ｎｘ，Ｈ（ｊ−１）／Ｎｙ） ‥（３）（ｗ_ij，ｈ_ij）＝（ｘ_i+1−ｘ_i，ｙ_i+1−ｙ_i） ‥（４）ただし、この場合の画素のＸＹ座標は、図１０（Ｂ）に
示すように、入力画像Ｉｉの左上の画素の座標を（０，
０）として、横方向は右に行くほど、縦方向は下に行く
ほど、増加するものとする。また、式（３）における除
算の結果は、小数点以下を切り捨てて整数値とするもの
とする。

【００７１】図１２（Ｂ）に示すように、式（４）のｘ
_i+1は、注目ブロック画像ｆ_ijの右横のブロック画像ｆ
_(i+1)jの左上の画素のＸ座標であり、ｙ_i+1は、注目ブ
ロック画像ｆ_ijの真下のブロック画像ｆ_i(j+1)の左上の
画素のＹ座標である。

【００７２】対象部分画像抽出部５０では、このように
注目ブロック画像を抽出するとともに、後述するように
部分画像領域分割部６０で前に行われた部分画像の領域
分割の結果の領域データを用いて、その注目ブロック画
像に隣接する算出済みの領域を抽出して、その注目ブロ
ック画像およびこれに隣接する算出済みの領域に含まれ
る画素を対象部分画像とする。ただし、１番目のブロッ
ク画像、例えば図１０（Ｂ）のブロック画像ｆ１１を注
目ブロック画像として抽出するときには、いまだ部分画
像領域分割部６０では部分画像の領域分割が行われてな
く、算出済みの領域が存在しないので、１番目のブロッ
ク画像に含まれる画素のみを対象部分画像として抽出す
る。

【００７３】したがって、例えば、図１０（Ｂ）に示し
たブロック画像ｆ１１‥‥ｆ４６を図１０（Ｃ）に示し
た順序で注目ブロック画像とする場合には、最初に、対
象部分画像抽出部５０では、ブロック画像ｆ１１のみが
対象部分画像として抽出され、部分画像領域分割部６０
では、そのブロック画像ｆ１１が領域分割されて、例え
ば、図１１（Ａ）に示すように、４個の領域Ａａ，Ａ
ｂ，Ａｃ，Ａｄが算出される。

【００７４】次に、対象部分画像抽出部５０では、図１
１（Ｂ）に斜線を付して示すように、ブロック画像ｆ１
２が注目ブロック画像として抽出され、領域Ａｂおよび
Ａｃが注目ブロック画像ｆ１２に隣接する算出済みの領
域として抽出されて、ブロック画像ｆ１２と領域Ａｂ，
Ａｃとからなる部分画像Ｇ１２が対象部分画像として抽
出され、部分画像領域分割部６０では、その対象部分画
像Ｇ１２が領域分割されて、例えば、図１１（Ｃ）に示
すように、修正された２個の領域Ａｂ，Ａｃと新たな４
個の領域Ａｅ，Ａｆ，Ａｇ，Ａｈが算出される。

【００７５】図１２（Ａ）は、このようにして、ブロッ
ク画像ｆ２２の左に隣接するブロック画像ｆ２１を注目
ブロック画像とする対象部分画像までの領域分割がなさ
れた状態を示し、この場合、そのブロック画像ｆ２１を
注目ブロック画像とするときの、これに隣接する算出済
みの領域は、図１１（Ｃ）から明らかなように、領域Ａ
ａ，Ａｃ，Ａｄである。

【００７６】以下では、あるブロック画像ｆ_ijおよびこ
れに隣接する算出済みの領域からなる対象部分画像の領
域分割によって算出された領域の集合を、領域集合Ｃ_ij
とする。この領域集合Ｃ_ijは、ブロック画像ｆ_ijに対応
づけて部分画像領域分割部６０に記憶し、以後の対象部
分画像抽出部５０での注目ブロック画像に隣接する算出
済みの領域の抽出に供する。

【００７７】注目ブロック画像に隣接する算出済みの領
域の抽出は、以下のようにして行う。例えば、各ブロッ
ク画像を図１０（Ｃ）に示したような順序で注目ブロッ
ク画像とする場合、図１２（Ｂ）に示すように、注目ブ
ロック画像ｆ_ijに隣接する算出済みの領域は、注目ブロ
ック画像ｆ_ijの左に隣接するブロック画像ｆ_(i-1)jに対
応する領域集合Ｃ_(i-1)j中の、Ｘ座標がｘ_i−１に等し
い画素を含む領域と、注目ブロック画像ｆ_ijの真上およ
び右上に隣接するブロック画像ｆ_i(j-1)およびｆ
_(i+1)(j-1)に対応する領域集合Ｃ_i(j-1)およびＣ
_(i+1)(j-1)中の、Ｘ座標がｘ_i以上、ｘ_i+1未満で、かつ
Ｙ座標がｙ_i−１に等しい画素を含む領域である。

【００７８】すなわち、ＸＹ座標が（ｘ_i−１，ｙ_i）も
しくはその下の斜線を付した部分内となる画素、または
（ｘ_i，ｙ_i−１）もしくはその右の斜線を付した部分内
となる画素を含む領域が、注目ブロック画像ｆ_ijに隣接
する算出済みの領域であり、画素のＸＹ座標から、その
領域を探索し、その探索された領域に含まれる画素を抽
出することによって、注目ブロック画像ｆ_ijに隣接する
算出済みの領域を抽出することができる。

【００７９】ただし、注目ブロック画像が図１０（Ｂ）
のブロック画像ｆ１１〜ｆ１６のように入力画像の上端
に位置している場合、またはブロック画像ｆ１１，ｆ２
１，ｆ３１，ｆ４１のように入力画像の左端に位置して
いる場合には、それぞれ注目ブロック画像の上方または
左に隣接する領域は存在しないので、上方または左に隣
接する領域からの画素の抽出はなされない。

【００８０】図１０（Ｂ）のブロック画像ｆ２２を注目
ブロック画像とするときには、それまでに図１２（Ａ）
に示したような領域分割がなされているとすると、ブロ
ック画像ｆ２２に隣接する算出済みの領域として、領域
Ａｃ，Ａｇ，Ａｈ，Ａｑに含まれる画素が抽出されるこ
とになる。

【００８１】部分画像領域分割部６０でのステップＳ６
０では、以下に示すように、Ｋ平均アルゴリズムに改良
を加えたクラスタリング手法によって、対象部分画像を
領域分割する。これは、図１３に示して後述する、この
発明の画像領域分割方法の第４の実施形態における入力
画像を、上記の対象部分画像に置き換えた場合と同じで
あるので、図１３を流用して示す。

【００８２】まずステップＳ１０１で、対象部分画像に
対して初期領域中心を設定する。注目ブロック画像に対
しては、任意に初期領域中心を与えることができ、例え
ば、そのブロック画像の重心に位置する画素の特徴ベク
トルを初期領域中心とすることもできるが、この例で
は、注目ブロック画像を４分割した矩形領域の重心に位
置する画素の特徴ベクトルによる４つの初期領域中心を
設定する。注目ブロック画像に隣接する算出済みの領域
については、それぞれの算出済みの領域中心を初期領域
中心とする。

【００８３】次にステップＳ１０２で、対象部分画像に
含まれる画素を一つ選択し、次にステップＳ１０３で、
その選択した画素の特徴ベクトルＰ_n＝（Ｌ_n，ａ_n，
ｂ_n，Ｘ_n，Ｙ_n）（ただし、１≦ｎ≦対象部分画像の画
素総数）と各領域中心Ｖ_m＝（Ｌ_m，ａ_m，ｂ_m，Ｘ_m，
Ｙ_m）との距離ｄを計算して、選択した画素に最も近い
距離ｄ_minを有する領域中心を探索する。距離ｄは、例
えば、第１の実施形態で示した式（２）によって算出す
る。特徴ベクトルＰ_nおよび領域中心Ｖ_mの各成分も、第
１の実施形態と同じである。

【００８４】ただし、この例でも、領域中心の探索を効
率化するため、選択した画素からの距離ｄが、あらかじ
め定められた閾値ｄ_thより小さい領域中心のみを探索の
候補とし、その探索候補の中から、選択した画素に最も
近い距離ｄ_minを有する領域中心を探索する。

【００８５】次のステップＳ１０４以降については、図
６に示した領域推定ステップＳ２０のステップＳ２０４
以降、または図７に示した領域生成ステップＳ３０のス
テップＳ３０４以降と同じである。ただし、ステップＳ
１０７では、ステップＳ１０２で対象部分画像のすべて
の画素を選択したか否かを判断する。

【００８６】図４において上述したように、ステップＳ
６０で、このように対象部分画像を領域分割したら、ス
テップＳ７０で、最後のブロック画像を含む、例えば、
図１０（Ｂ）に示したブロック画像ｆ１１‥‥ｆ４６を
図１０（Ｃ）に示した順序で注目ブロック画像とする場
合にはブロック画像ｆ４６を含む、最終部分画像を領域
分割したか否かを判断し、最終部分画像を領域分割して
いなければ、ステップＳ５０に戻って、次のブロック画
像を注目ブロック画像として次の対象部分画像を抽出
し、ステップＳ６０で、図１３に示して上述したよう
に、その対象部分画像を領域分割する。そして、ステッ
プＳ７０で最終部分画像を領域分割したと判断したとき
には、入力画像の領域分割を終了する。

【００８７】上述した第２の実施形態によれば、画像の
ブロック化によって、各回の領域分割は、少ない画素を
少ない領域に分割するものとして高速で行うことがで
き、全体として、入力画像を高速に領域分割することが
できる。また、ブロック画像に隣接する領域を重複して
処理するので、ブロック画像間の不整合を生じることが
なく、不自然な領域分割となることがない。

【００８８】〔第３の実施形態〕図５および図６〜図８
は、この発明の画像領域分割装置および画像領域分割方
法の第３の実施形態を示し、画像のブロック化に画像の
間引きを組み合わせた場合である。

【００８９】図５の画像領域分割装置は、画像入力部１
０、画像記憶部１５、対象部分画像抽出部５０、領域集
合記憶部７０、部分画像記憶部８０、領域推定部２０、
領域生成部３０、領域確定部４０、終了判定部９０およ
び統計情報算出部１００によって構成される。

【００９０】画像入力部１０は、図１および図３のそれ
と同じである。この例でも、入力画像データは、ＲＧＢ
画像データとして得られてＬ^*ａ^*ｂ^*画像データに変換
され、Ｌ^*，ａ^*，ｂ^*成分を有する色ベクトルの２次元
マップで表現されるものとする。

【００９１】画像記憶部１５は、図１および図３では画
像入力部１０に含まれるとして省略した、入力画像デー
タの一部または全部を記憶するメモリなどの記憶装置
で、この例では、対象部分画像抽出部５０で対象部分画
像を抽出できる、入力画像データの一部を記憶する。そ
のため、画像入力部１０は、対象部分画像抽出部５０で
の処理と同期して、その処理に必要な部分の画像データ
を生成して、画像記憶部１５に書き込む。ただし、画像
記憶部１５として十分な容量のものを使用できる場合に
は、入力画像データ全体を一度に読み込んで、画像記憶
部１５に書き込むように構成することもできる。

【００９２】領域集合記憶部７０は、後述するように領
域確定部４０で算出された領域データを記憶する。この
領域データは、例えば、一般的なマスク情報によって表
現することもできるが、この例では、領域を構成する画
素の画像平面におけるＸＹ座標のリストを領域データと
し、その領域データの集合を第２の実施形態でも示した
領域集合とする。

【００９３】対象部分画像抽出部５０は、領域集合記憶
部７０に記憶されている領域データをもとに、画像記憶
部１５に記憶されている画像データから、領域推定部２
０、領域生成部３０および領域確定部４０で処理される
べき、上述した注目ブロック画像およびこれに隣接する
算出済みの領域からなる対象部分画像を抽出する。この
場合の対象部分画像も、画素の色ベクトルの３成分と画
素の画像平面におけるＸＹ座標とを保持するものとす
る。

【００９４】対象部分画像抽出部５０での対象部分画像
の抽出方法としては、第２の実施形態において上述した
方法を用いることができる。対象部分画像抽出部５０
で、注目ブロック画像に隣接する算出済みの領域に含ま
れる画素が、注目ブロック画像に含まれる画素に追加し
て抽出されたら、その抽出された算出済みの領域につい
ての領域データは、領域集合記憶部７０から削除され
る。

【００９５】部分画像記憶部８０は、対象部分画像抽出
部５０で抽出された対象部分画像を一時的に記憶して、
領域推定部２０、領域生成部３０および領域確定部４０
での処理に供する。処理が完了すれば、その対象部分画
像は破棄することができる。

【００９６】領域推定部２０は、部分画像記憶部８０に
記憶されている対象部分画像を、あらかじめ定められた
間引き率Ｒａで間引いた間引き部分画像を領域分割し
て、対象部分画像の領域のおおよその数および中心を推
定する。

【００９７】領域生成部３０は、この領域推定部２０で
推定された領域の数および中心を用いて、部分画像記憶
部８０に記憶されている対象部分画像を、上記の間引き
率Ｒａより小さい間引き率Ｒｂで間引いた間引き部分画
像を領域分割して、対象部分画像の領域の数および中心
を算出する。

【００９８】領域確定部４０は、部分画像記憶部８０に
記憶されている対象部分画像に含まれるすべての画素
を、領域生成部３０で算出された領域のうちの最も適切
な領域に配分して、対象部分画像が構成する領域集合を
算出する。この領域確定部４０で算出された領域集合
は、上述したように領域集合記憶部７０に記憶される。

【００９９】領域推定部２０、領域生成部３０および領
域確定部４０は、第１の実施形態における入力画像の代
わりに、第２の実施形態における対象部分画像につき、
それぞれの処理を行う以外は、図６〜図８に領域推定ス
テップＳ２０、領域生成ステップＳ３０および領域確定
ステップＳ４０として示して後述するように、第１の実
施形態のそれと同じにすることができる。

【０１００】対象部分画像抽出部５０での対象部分画像
の抽出と、その抽出した対象部分画像の部分画像記憶部
８０への書き込み、その部分画像記憶部８０に書き込ま
れた対象部分画像に対する領域推定部２０、領域生成部
３０および領域確定部４０での処理、および領域確定部
４０で算出された領域集合の領域集合記憶部７０への書
き込みは、対象部分画像における注目ブロック画像を順
次変更して、順次繰り返す。

【０１０１】終了判定部９０では、すべてのブロック画
像に対する処理が終了したか否かを判定して、未処理の
ブロック画像が存在すれば、対象部分画像抽出部５０以
降の処理を繰り返す。

【０１０２】統計情報算出部１００は、終了判定部９０
ですべてのブロック画像に対する処理が終了したと判定
したとき、領域集合記憶部７０に記憶されている領域集
合から、領域を構成する画素数や色ベクトルの分散など
の統計情報を算出し、必要に応じて領域の統合や削除な
どを行う。この処理は、領域分割により得られた領域を
どのように使用するかに依存するとともに、この発明の
要旨ではないので、ここでは具体例を省略する。

【０１０３】領域推定部２０では、図６に領域推定ステ
ップＳ２０として示すように、まずステップＳ２０１
で、対象部分画像に対して初期領域中心を設定する。図
１３を流用して上述した第２の実施形態と同様に、注目
ブロック画像に対しては、この例では、注目ブロック画
像を４分割した矩形領域の重心に位置する画素の特徴ベ
クトルによる４つの初期領域中心を設定し、注目ブロッ
ク画像に隣接する算出済みの領域については、それぞれ
の算出済みの領域中心を初期領域中心とする。

【０１０４】次にステップＳ２０２で、対象部分画像の
画素を間引き率Ｒ＝Ｒａで間引いて一つ選択する。この
画素の選択は、例えば、対象部分画像の画素の特徴ベク
トルＰ_n＝（Ｌ_n，ａ_n，ｂ_n，Ｘ_n，Ｙ_n）（ただし、１≦
ｎ≦対象部分画像の画素総数）から、第１の実施形態で
示した式（１）の条件を満たす画素を一つずつ順に選択
することによって行う。

【０１０５】次のステップＳ２０３以降については、第
１の実施形態で示したのと同じである。

【０１０６】領域生成部３０では、図７に領域生成ステ
ップＳ３０として示すように、まずステップＳ３０１
で、初期領域中心として、上記の領域推定ステップＳ２
０で算出した領域中心を設定する。ただし、それぞれの
領域中心の領域に再配置されている画素は削除してお
く。

【０１０７】次にステップＳ３０２で、対象部分画像の
画素を間引き率Ｒ＝Ｒｂ（Ｒｂ＜Ｒａ）で間引いて一つ
選択する。この画素の選択は、例えば、図６の領域推定
ステップＳ２０のステップＳ２０２での画素の選択と同
様に、第１の実施形態で示した式（１）の条件を満たす
画素を一つずつ順に選択することによって行う。

【０１０８】次のステップＳ３０３以降については、図
６の領域推定ステップＳ２０のステップＳ２０３以降と
同じである。

【０１０９】領域確定部４０では、図８に領域確定ステ
ップＳ４０として示すように、まずステップＳ４０１
で、初期領域中心として、上記の領域生成ステップＳ３
０で算出した領域中心を設定する。ただし、それぞれの
領域中心の領域に再配置されている画素は削除してお
く。

【０１１０】次にステップＳ４０２で、対象部分画像に
含まれるすべての画素を一つずつ選択する。これは、間
引き率Ｒを１とすればよい。しかし、対象部分画像に含
まれるすべての画素を順に選択するにもかかわらず、上
記の式（１）の条件判断を行うのは、無駄である。した
がって、領域確定ステップＳ４０では、再配置のみを行
うフラグを作成しておいて、このフラグが立っていれ
ば、対象部分画像の画素を無条件に順に選択するように
構成することができる。

【０１１１】次のステップＳ４０３以降については、第
１の実施形態で示したのと同じである。ただし、ステッ
プＳ４０７では、対象部分画像のすべての画素を選択し
たか否かを判断する。

【０１１２】上記の例は、領域推定ステップＳ２０およ
び領域生成ステップＳ３０で単純間引きを用いる場合で
あるが、対象部分画像の色分布の特徴をできるだけ保持
し、かつ対象部分画像より画素総数が少なくなる間引き
方法であれば、いかなる間引き方法でもよく、例えば、
対象部分画像のＲ²（Ｒａ²またはＲｂ²）個の画素の平
均値や中央値を間引き部分画像として用いることができ
る。

【０１１３】上述した第３の実施形態によれば、第２の
実施形態よりも、より高速で領域分割を行うことができ
るとともに、第２の実施形態と同様に、ブロック画像間
の不整合を生じることがなく、不自然な領域分割となる
ことがない。

【０１１４】〔第４の実施形態〕図１３は、この発明の
画像領域分割方法の第４の実施形態を示し、画像のブロ
ック化や間引きを用いることなく、Ｋ平均アルゴリズム
に改良を加えたクラスタリング手法によって、入力画像
を領域分割する場合である。

【０１１５】この実施形態では、まずステップＳ１０１
で、クラスタ数Ｋを適切に選んで、入力画像に対して初
期領域中心を設定し、次にステップＳ１０２で、入力画
像に含まれる画素を一つ選択する。

【０１１６】次にステップＳ１０３で、その選択した画
素の特徴ベクトルＰ_n＝（Ｌ_n，ａ_n，ｂ_n，Ｘ_n，Ｙ_n）
（ただし、１≦ｎ≦入力画像の画素総数）と各領域中心
Ｖ_m＝（Ｌ_m，ａ_m，ｂ_m，Ｘ_m，Ｙ_m）との距離ｄを計算し
て、選択した画素に最も近い距離ｄ_minを有する領域中
心を探索する。距離ｄは、例えば、第１の実施形態で示
した式（２）によって算出する。特徴ベクトルＰ_nおよ
び領域中心Ｖ_mの各成分も、第１の実施形態と同じであ
る。

【０１１７】ただし、この場合、選択した画素からの距
離ｄが、あらかじめ定められた閾値ｄ_thより小さい領域
中心のみを探索の候補とし、その探索候補の中から、選
択した画素に最も近い距離ｄ_minを有する領域中心を探
索する。

【０１１８】次にステップＳ１０４で、その最も近い距
離ｄ_minが、あらかじめ定められた閾値Ｔ_diff（Ｔ_diff
＜ｄ_th）より小さいか否かを判断して、選択した画素
を、その最も近い距離ｄ_minを有する領域中心の領域に
再配置できるか否かを判定する。

【０１１９】すなわち、距離ｄ_minが閾値Ｔ_diffより小
さいときには、選択した画素を距離ｄ_minを有する領域
中心の領域に再配置できるとして、ステップＳ１０５に
進み、距離ｄ_minが閾値Ｔ_diff以上であるときには、選
択した画素を距離ｄ_minを有する領域中心の領域に再配
置できないとして、ステップＳ１０６に進む。

【０１２０】また、ステップＳ１０３で、選択した画素
からの距離ｄが閾値ｄ_thより小さい探索候補の領域中心
が存在しなかったときにも、選択した画素を再配置すべ
き適当な領域中心が存在しないとして、ステップＳ１０
４からステップＳ１０６に進む。

【０１２１】ステップＳ１０５では、その選択した画素
を、閾値Ｔ_diffより小さい範囲で最も近い距離ｄ_minを
有する領域中心の領域に配分する。

【０１２２】ステップＳ１０６では、その選択した一つ
の画素からなる領域を新たに生成する。具体的には、選
択した一つの画素の色ベクトルのＬ^*，ａ^*，ｂ^*成分
と、その画素の画像平面におけるＸＹ座標とからなる特
徴ベクトルを生成して、これを領域中心とし、その領域
中心の領域に、選択した一つの画素を配分する。その結
果、領域中心ないし領域の総数は、一つ増加することに
なる。

【０１２３】ステップＳ１０５またはＳ１０６の後のス
テップＳ１０７以降については、図６に示した領域推定
ステップＳ２０のステップＳ２０７以降、または図７に
示した領域生成ステップＳ３０のステップＳ３０７以降
と同じである。ただし、ステップＳ１０７では、ステッ
プＳ１０２で入力画像のすべての画素を選択したか否か
を判断する。

【０１２４】上述した第４の実施形態によれば、対象画
素からの距離ｄが所定の閾値ｄ_thより小さい領域中心の
みを探索の候補とし、その探索候補の中から、対象画素
に最も近い距離ｄ_minを有する領域中心を探索するの
で、対象画素を再配置すべき領域の探索を効率化でき、
領域分割を高速化することができる。

【０１２５】また、その探索候補の領域中心が存在しな
いとき、または対象画素に最も近い距離ｄ_minを有する
領域中心と対象画素との距離ｄ_minが所定の閾値Ｔ_diff
以上であるときには、領域が収束する前に対象画素一つ
からなる領域を生成するので、領域の収束までに要する
時間を短縮することができる。

【０１２６】

【発明の効果】上述したように、請求項１，８または
２，９の発明によれば、画像の間引きを利用することに
よって、分割対象の入力画像を高速に領域分割すること
ができ、特に請求項２，９の発明によれば、より高速に
領域分割することができる。

【０１２７】請求項３，１０の発明によれば、入力画像
をブロック画像に分割することによって、各回の領域分
割は、少ない画素を少ない領域に分割するものとして高
速で行うことができ、全体として、入力画像を高速に領
域分割することができるとともに、ブロック画像間の不
整合を生じることがなく、不自然な領域分割となること
がない。

【０１２８】請求項４，１１または５，１２の発明によ
れば、画像のブロック化に画像の間引きを組み合わせる
ことによって、不自然な領域分割となることなく、入力
画像をより高速に領域分割することができ、特に請求項
５，１２の発明によれば、さらに高速に領域分割するこ
とができる。

【０１２９】請求項１５，１６または１７の発明によれ
ば、画像のブロック化および間引きのいずれも用いない
場合においても、領域分割を高速化することができる。

【図面の簡単な説明】

【図１】この発明の装置の第１の実施形態を示す図であ
る。

【図２】この発明の方法の第１の実施形態を示す図であ
る。

【図３】この発明の装置の第２の実施形態を示す図であ
る。

【図４】この発明の方法の第２の実施形態を示す図であ
る。

【図５】この発明の装置の第３の実施形態を示す図であ
る。

【図６】この発明の方法の第３の実施形態の領域推定ス
テップの例を示す図である。

【図７】この発明の方法の第３の実施形態の領域生成ス
テップの例を示す図である。

【図８】この発明の方法の第３の実施形態の領域確定ス
テップの例を示す図である。

【図９】入力画像とその間引きの説明に供する図であ
る。

【図１０】入力画像のブロック化の説明に供する図であ
る。

【図１１】ブロック化の場合の領域分割の説明に供する
図である。

【図１２】ブロック化の場合の対象部分画像の抽出の説
明に供する図である。

【図１３】この発明の方法の第４の実施形態を示す図で
ある。

【符号の説明】

１０画像入力部１５画像記憶部２０領域推定部３０領域生成部４０領域確定部５０対象部分画像抽出部６０部分画像領域分割部７０領域集合記憶部８０部分画像記憶部９０終了判定部１００統計情報算出部Ｓ２０領域推定ステップＳ３０領域生成ステップＳ４０領域確定ステップＳ６０領域分割ステップ

Claims

【特許請求の範囲】

【請求項１】量子化された多階調の入力画像データで表
現された分割対象の入力画像を所定の間引き率で間引い
た間引き画像を領域分割して、前記入力画像の領域の数
および中心を算出する領域算出ステップと、この領域算
出ステップで算出された領域に前記入力画像に含まれる
すべての画素を配分する領域確定ステップと、を備える
ことを特徴とする画像領域分割方法。
【請求項２】請求項１の画像領域分割方法において、前
記領域算出ステップは、前記入力画像を第１の間引き率で間引いた第１の間引き
画像を領域分割して、前記入力画像の領域のおおよその
数および中心を推定する領域推定ステップと、この領域
推定ステップで推定された領域の数および中心を用い
て、前記入力画像を前記第１の間引き率より小さい第２
の間引き率で間引いた第２の間引き画像を領域分割し
て、前記入力画像の領域の数および中心を算出する領域
生成ステップと、を有することを特徴とする画像領域分
割方法。
【請求項３】量子化された多階調の入力画像データで表
現された分割対象の入力画像を複数のブロック画像に分
割したときの、注目ブロック画像およびこれに隣接する
算出済みの領域に含まれる画素からなる対象部分画像を
領域分割する部分画像領域分割ステップを、前記複数の
ブロック画像中の異なるブロック画像を順次、前記注目
ブロック画像として繰り返し行って、前記入力画像を領
域分割することを特徴とする画像領域分割方法。
【請求項４】請求項３の画像領域分割方法において、前
記部分画像領域分割ステップは、前記対象部分画像を所定の間引き率で間引いた間引き部
分画像を領域分割して、前記対象部分画像の領域の数お
よび中心を算出する領域算出ステップと、この領域算出
ステップで算出された領域に前記対象部分画像に含まれ
るすべての画素を配分する領域確定ステップと、を備え
ることを特徴とする画像領域分割方法。
【請求項５】請求項４の画像領域分割方法において、前
記領域算出ステップは、前記対象部分画像を第１の間引き率で間引いた第１の間
引き部分画像を領域分割して、前記対象部分画像の領域
のおおよその数および中心を推定する領域推定ステップ
と、この領域推定ステップで推定された領域の数および
中心を用いて、前記対象部分画像を前記第１の間引き率
より小さい第２の間引き率で間引いた第２の間引き部分
画像を領域分割して、前記対象部分画像の領域の数およ
び中心を算出する領域生成ステップと、を有することを
特徴とする画像領域分割方法。
【請求項６】請求項１，２，３，４または５の画像領域
分割方法において、前記領域算出ステップ、または前記領域推定ステップ、
もしくは前記領域生成ステップ、または前記部分画像領
域分割ステップは、画素の色ベクトルの３成分および画
像平面における座標による５次元特徴空間上で、Ｋ平均
アルゴリズムによって、前記間引き画像、または前記対
象部分画像、もしくは前記間引き部分画像を領域分割す
ることを特徴とする画像領域分割方法。
【請求項７】請求項１，２，４または５の画像領域分割
方法において、前記領域確定ステップは、画素の色ベクトルの３成分お
よび画像平面における座標による５次元特徴空間での重
み付き距離が最も小さい領域に画素を配分することを特
徴とする画像領域分割方法。
【請求項８】分割対象の入力画像を表現する量子化され
た多階調の入力画像データを得る画像入力部と、前記入力画像を所定の間引き率で間引いた間引き画像を
領域分割して、前記入力画像の領域の数および中心を算
出する領域算出部と、この領域算出部で算出された領域に前記入力画像に含ま
れるすべての画素を配分する領域確定部と、を備えることを特徴とする画像領域分割装置。
【請求項９】請求項８の画像領域分割装置において、前
記領域算出部は、前記入力画像を第１の間引き率で間引いた第１の間引き
画像を領域分割して、前記入力画像の領域のおおよその
数および中心を推定する領域推定部と、この領域推定部で推定された領域の数および中心を用い
て、前記入力画像を前記第１の間引き率より小さい第２
の間引き率で間引いた第２の間引き画像を領域分割し
て、前記入力画像の領域の数および中心を算出する領域
生成部と、を有することを特徴とする画像領域分割装置。
【請求項１０】分割対象の入力画像を表現する量子化さ
れた多階調の入力画像データを得る画像入力部と、前記入力画像を複数のブロック画像に分割したときの、
注目ブロック画像およびこれに隣接する算出済みの領域
に含まれる画素からなる対象部分画像を、前記複数のブ
ロック画像中の異なるブロック画像を順次、前記注目ブ
ロック画像として、順次抽出する対象部分画像抽出部
と、この対象部分画像抽出部で順次抽出された対象部分画像
を順次、領域分割する部分画像領域分割部と、を備えることを特徴とする画像領域分割装置。
【請求項１１】請求項１０の画像領域分割装置におい
て、前記部分画像領域分割部は、前記対象部分画像抽出部で抽出された対象部分画像を所
定の間引き率で間引いた間引き部分画像を領域分割し
て、前記対象部分画像抽出部で抽出された対象部分画像
の領域の数および中心を算出する領域算出部と、この領域算出部で算出された領域に前記対象部分画像抽
出部で抽出された対象部分画像に含まれるすべての画素
を配分する領域確定部と、を備えることを特徴とする画像領域分割装置。
【請求項１２】請求項１１の画像領域分割装置におい
て、前記領域算出部は、前記対象部分画像抽出部で抽出された対象部分画像を第
１の間引き率で間引いた第１の間引き部分画像を領域分
割して、前記対象部分画像抽出部で抽出された対象部分
画像の領域のおおよその数および中心を推定する領域推
定部と、この領域推定部で推定された領域の数および中心を用い
て、前記対象部分画像抽出部で抽出された対象部分画像
を前記第１の間引き率より小さい第２の間引き率で間引
いた第２の間引き部分画像を領域分割して、前記対象部
分画像抽出部で抽出された対象部分画像の領域の数およ
び中心を算出する領域生成部と、を有することを特徴とする画像領域分割装置。
【請求項１３】請求項８，９，１０，１１または１２の
画像領域分割装置において、前記領域算出部、または前記領域推定部、もしくは前記
領域生成部、または前記部分画像領域分割部は、画素の
色ベクトルの３成分および画像平面における座標による
５次元特徴空間上で、Ｋ平均アルゴリズムによって、前
記間引き画像、または前記対象部分画像、もしくは前記
間引き部分画像を領域分割することを特徴とする画像領
域分割装置。
【請求項１４】請求項８，９，１１または１２の画像領
域分割装置において、前記領域確定部は、画素の色ベクトルの３成分および画
像平面における座標による５次元特徴空間での重み付き
距離が最も小さい領域に画素を配分することを特徴とす
る画像領域分割装置。
【請求項１５】Ｋ平均アルゴリズムによって画像を領域
分割する方法において、対象画素からの特徴空間上における距離が、あらかじめ
定められた閾値より小さい領域中心を有する領域のみを
探索の候補とし、その探索候補の中から、対象画素を再
配置すべき領域を探索することを特徴とする画像領域分
割方法。
【請求項１６】請求項１５の画像領域分割方法におい
て、前記探索候補が存在しない場合には、領域が収束する前
に対象画素一つからなる領域を生成することを特徴とす
る画像領域分割方法。
【請求項１７】Ｋ平均アルゴリズムによって画像を領域
分割する方法において、特徴空間上における、対象画素に最も近い距離を有する
領域中心と対象画素との距離が、あらかじめ定められた
閾値以上である場合には、領域が収束する前に対象画素
一つからなる領域を生成することを特徴とする画像領域
分割方法。
【請求項１８】請求項１，２，３，４，５，６，７，１
５，１６または１７の画像領域分割方法を実行するため
のプログラムが記載されたプログラム記録媒体。