(57)【要約】【課題】分割対象の入力画像をより高速に領域分割できるようにする。【解決手段】分割対象の入力画像Ｉｉを第1の間引き率Ｒａで間引いた第1の間引き画像Ｉａを領域分割して、入力画像Ｉｉの領域のおおよその数および中心を推定し、次に、その推定結果を用いて、入力画像Ｉｉを第１の間引き率Ｒａより小さい第２の間引き率Ｒｂで間引いた第２の間引き画像Ｉｂを領域分割して、入力画像Ｉｉの領域の数および中心を算出し、次に、その算出された領域のうちの最も適切な領域に、入力画像Ｉｉに含まれるすべての画素を配分する。【選択図】図９
2005011375.tif 000002
【特許請求の範囲】
【請求項１】
量子化された多階調の入力画像データで表現された分割対象の入力画像を所定の間引き率で間引いた間引き画像を領域分割して、前記入力画像の領域の数および中心を算出する領域算出ステップと、この領域算出ステップで算出された領域に前記入力画像に含まれるすべての画素を配分する領域確定ステップとを備える画像領域分割方法であって、
前記領域算出ステップは、前記入力画像を第１の間引き率で間引いた第１の間引き画像を領域分割して、前記入力画像の領域のおおよその数および中心を推定する領域推定ステップと、この領域推定ステップで推定された領域の数および中心を用いて、前記入力画像を前記第１の間引き率より小さい第２の間引き率で間引いた第２の間引き画像を領域分割して、前記入力画像の領域の数および中心を算出する領域生成ステップとを有することを特徴とする画像領域分割方法。
【請求項２】
請求項１の画像領域分割方法において、
前記領域推定ステップまたは前記領域生成ステップは、画素の色ベクトルの３成分および画像平面における座標による５次元特徴空間上で、Ｋ平均アルゴリズムによって、前記第１の間引き画像または前記第２の間引き画像を領域分割することを特徴とする画像領域分割方法。
【請求項３】
請求項１の画像領域分割方法において、
前記領域確定ステップは、画素の色ベクトルの３成分および画像平面における座標による５次元特徴空間での重み付き距離が最も小さい領域に画素を配分することを特徴とする画像領域分割方法。
【請求項４】
分割対象の入力画像を表現する量子化された多階調の入力画像データを得る画像入力部と、前記入力画像を所定の間引き率で間引いた間引き画像を領域分割して、前記入力画像の領域の数および中心を算出する領域算出部と、この領域算出部で算出された領域に前記入力画像に含まれるすべての画素を配分する領域確定部とを備える画像領域分割装置であって、
前記領域算出部は、前記入力画像を第１の間引き率で間引いた第１の間引き画像を領域分割して、前記入力画像の領域のおおよその数および中心を推定する領域推定部と、この領域推定部で推定された領域の数および中心を用いて、前記入力画像を前記第１の間引き率より小さい第２の間引き率で間引いた第２の間引き画像を領域分割して、前記入力画像の領域の数および中心を算出する領域生成部とを有することを特徴とする画像領域分割装置。
【請求項５】
請求項４の画像領域分割装置において、
前記領域推定部または前記領域生成部は、画素の色ベクトルの３成分および画像平面における座標による５次元特徴空間上で、Ｋ平均アルゴリズムによって、前記第１の間引き画像または前記第２の間引き画像を領域分割することを特徴とする画像領域分割装置。
【請求項６】
請求項４の画像領域分割装置において、
前記領域確定部は、画素の色ベクトルの３成分および画像平面における座標による５次元特徴空間での重み付き距離が最も小さい領域に画素を配分することを特徴とする画像領域分割装置。
【請求項７】
請求項１，２または３の画像領域分割方法を実行するためのプログラムが記載されたプログラム記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、量子化された多階調の画像データで表現された画像を領域分割する画像領域分割方法および画像領域分割装置に関する。
【背景技術】
【０００２】
イメージスキャナにより読み取られた画像やコンピュータにより生成された画像などの画像を領域分割することは、画像処理のさまざまな分野で前処理として利用されている。
【０００３】
例えば、画像編集処理では、編集する領域を自動的に切り出すために、領域分割が用いられる。また、画像認識処理では、認識対象物を見つけ出すために、領域分割が用いられる。さらに、画像の部分的なテクスチャや色の分布状態などが類似する領域ごとに異なる画像処理を行う場合などにも、領域分割を利用することができる。
【０００４】
このような場合の領域分割は、その性能の良否が画像処理全体の性能を大きく左右することになるので、性能のよい領域分割方法によることが要求される。
【０００５】
領域分割の方法としては、古くから知られているＫ平均アルゴリズム（Ｋ平均クラスタ化アルゴリズム）がある（例えば、非特許文献１：中谷ほか「複数の領域分割結果に基づく対象物境界線検出」電子情報通信学会論文誌Ｄ２，Ｖｏｌ．Ｊ７６−Ｄ２，Ｎｏ４，ｐｐ．９１４−９１６，’９３／４）。
【０００６】
また、画像の色ベクトルのＲＧＢ（赤、緑、青）などの３成分に画像平面におけるＸＹ座標を加えた５次元特徴空間上でＫ平均アルゴリズムを行う方法も提案されている（非特許文献２：泉ほか「色情報と位置情報とを併用したセグメンテーション手法の一検討」１９９１年電子情報通信学会春季全国大会予稿集Ｄ−６８０）。
【０００７】
さらに、特許文献１（特開平８−３０７８７号公報）には、分割対象の画像を、複数のブロック領域と、それぞれのブロック領域の間に位置する境界領域とに分けて、それぞれのブロック領域の領域分割に当たって、そのブロック領域と接する境界領域を一緒に領域分割することによって、小容量のメモリにより、短時間で高速に、ブロック領域間の不整合がなく、画像を領域分割する方法が提案されている。
【０００８】
上に挙げた先行技術文献は、以下のとおりである。
【非特許文献１】中谷ほか「複数の領域分割結果に基づく対象物境界線検出」電子情報通信学会論文誌Ｄ２，Ｖｏｌ．Ｊ７６−Ｄ２，Ｎｏ４，ｐｐ．９１４−９１６，’９３／４
【非特許文献２】泉ほか「色情報と位置情報とを併用したセグメンテーション手法の一検討」１９９１年電子情報通信学会春季全国大会予稿集Ｄ−６８０
【特許文献１】特開平８−３０７８７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
Ｋ平均アルゴリズムによる領域分割は、画像中の各画素を適切な領域に配分する処理を所定状態に収束するまで繰り返し、少しずつよりよい領域を求めていく方法である。そのため、用いる特徴空間に応じた領域を高い精度で求めることができる。しかしながら、分割領域を少しずつよりよい領域に収束させていくため、処理に膨大な時間が必要となる。
【００１０】
特許文献１（特開平８−３０７８７号公報）によって提案された方法は、その処理時間を激減させることができるが、それでもかなりの時間を必要とする。
【００１１】
そこで、この発明の目的は、より高速に画像を領域分割できるようにすることにある。
【課題を解決するための手段】
【００１２】
この発明の画像領域分割方法は、
量子化された多階調の入力画像データで表現された分割対象の入力画像を所定の間引き率で間引いた間引き画像を領域分割して、前記入力画像の領域の数および中心を算出する領域算出ステップと、この領域算出ステップで算出された領域に前記入力画像に含まれるすべての画素を配分する領域確定ステップとを備える画像領域分割方法であって、
前記領域算出ステップは、前記入力画像を第１の間引き率で間引いた第１の間引き画像を領域分割して、前記入力画像の領域のおおよその数および中心を推定する領域推定ステップと、この領域推定ステップで推定された領域の数および中心を用いて、前記入力画像を前記第１の間引き率より小さい第２の間引き率で間引いた第２の間引き画像を領域分割して、前記入力画像の領域の数および中心を算出する領域生成ステップとを有することを特徴とする。
【００１３】
上記の、この発明の画像領域分割方法においては、入力画像が所定の間引き率で間引かれた、入力画像の一部の画素しか含まない間引き画像によって、入力画像の領域の数および中心が算出され、その算出された領域に入力画像に含まれるすべての画素が配分される。したがって、領域の収束までに要する時間が大幅に短縮され、入力画像が高速に領域分割される。
【００１４】
しかも、間引き率のより大きい第１の間引き画像により入力画像の領域のおおよその数および中心を推定し、その推定結果を用いて、所定の間引き率の第２の間引き画像により入力画像の領域の数および中心を算出するので、当初から所定の間引き率の間引き画像により入力画像の領域の数および中心を算出する場合に比べて、領域の数および中心の算出に要する時間をより短縮することができる。
【発明の効果】
【００１５】
以上のように、この発明によれば、より高速に画像を領域分割することができる。
【発明を実施するための最良の形態】
【００１６】
〔第１の実施形態〕
図１は、この発明の画像領域分割装置の第１の実施形態を示し、画像の間引きを利用して入力画像を領域分割する場合である。この実施形態の画像領域分割装置は、画像入力部１０、領域推定部２０、領域生成部３０および領域確定部４０によって構成される。
【００１７】
画像入力部１０は、分割対象の入力画像Ｉｉを示す量子化された多階調の入力画像データＤｉを得るもので、用紙上やフィルム上の画像を読み取るイメージスキャナ、被写体像を撮影するデジタルカメラ、ハードディスクなどの記憶装置から、これに記憶されている画像データを読み出す装置、ネットワークなどを介して送信された画像データを受信して取り込む装置、またはコンピュータにより描画して画像データを生成する装置などである。
【００１８】
画像入力部１０では、必要に応じて、入力画像データの表色系が以後の処理において用いられる表色系に変換される。以下の例では、入力画像データは、ＲＧＢ画像データとして得られてＬ*ａ*ｂ*画像データに変換され、Ｌ*，ａ*，ｂ*成分を有する色ベクトルの２次元マップで表現されるものとする。また、画像入力部１０は、必要に応じて、入力画像データの一部または全部を記憶するメモリなどの記憶装置を備えるものとする。
【００１９】
領域推定部２０は、上記の入力画像データで表現された入力画像を、あらかじめ定められた間引き率Ｒａで間引いた間引き画像を領域分割して、入力画像の領域のおおよその数および中心を推定し、領域生成部３０は、この領域推定部２０で推定された領域の数および中心を用いて、入力画像を上記の間引き率Ｒａより小さい間引き率Ｒｂで間引いた間引き画像を領域分割して、入力画像の領域の数および中心を算出する。以下の例では、単純間引きを用いる場合を示す。
【００２０】
図９（Ａ）に示すように、入力画像ＩｉはＸ方向（横方向）およびＹ方向（縦方向）に画素Ｐｉが連続するもので、画像入力部１０からは、その画素ＰｉをＸ方向およびＹ方向に間引き率Ｒａで間引いた、図９（Ｂ）で塗り潰して示す画素Ｐａのような一部の画素からなる間引き画像Ｉａと、画素ＰｉをＸ方向およびＹ方向に間引き率Ｒｂで間引いた、図９（Ｃ）で塗り潰して示す画素Ｐｂのような一部の画素からなる間引き画像Ｉｂとを得る。間引き率Ｒ（ＲａまたはＲｂ）は、Ｒ2個に１個の画素を取り出すことを意味する。
【００２１】
そして、領域推定部２０では、後述するように間引き画像Ｉａを領域分割して、入力画像Ｉｉの領域のおおよその数および中心を推定し、領域生成部３０では、その推定結果を用いて、後述するように間引き画像Ｉｂを領域分割して、入力画像Ｉｉの領域の数および中心を算出する。
【００２２】
領域確定部４０は、後述するように、入力画像Ｉｉに含まれるすべての画素を、領域生成部３０で算出された領域のうちの最も適切な領域に配分する。
【００２３】
図２は、図１の画像領域分割装置に対応する、この発明の画像領域分割方法の第１の実施形態を示し、まず領域推定部２０でのステップＳ２０で、間引き率Ｒａによる間引き画像を領域分割して、入力画像の領域のおおよその数および中心を推定し、次に領域生成部３０でのステップＳ３０で、その推定結果を用いて、間引き率Ｒｂによる間引き画像を領域分割して、入力画像の領域の数および中心を算出し、次に領域確定部４０でのステップＳ４０で、その算出された領域に入力画像に含まれるすべての画素を配分する。
【００２４】
ステップＳ２０での領域推定、ステップＳ３０での領域生成、およびステップＳ４０での領域確定は、以下に示すように、Ｋ平均アルゴリズムに改良を加えたクラスタリング手法によって行う。これは、図６〜図８に示して後述する、この発明の画像領域分割方法の第３の実施形態における対象部分画像を、入力画像そのものに置き換えた場合と同じであるので、図６〜図８を流用して示す。
【００２５】
ステップＳ２０では、図６に示すように（ただし、ステップＳ２０２の対象部分画像は入力画像に置き換える）、まずステップＳ２０１で、クラスタ数Ｋを適切に選んで、入力画像に対して初期領域中心を設定し、次にステップＳ２０２で、入力画像の画素を間引き率Ｒ＝Ｒａで間引いて一つ選択する。
【００２６】
この画素の選択は、例えば、入力画像の画素の特徴ベクトルＰ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を有する領域中心の領域に配分する。
【００３５】
ステップＳ２０６では、その選択した一つの画素からなる領域を新たに生成する。具体的には、選択した一つの画素の色ベクトルのＬ*，ａ*，ｂ*成分と、その画素の画像平面におけるＸＹ座標とからなる特徴ベクトルを生成して、これを領域中心とし、その領域中心の領域に、選択した一つの画素を配分する。その結果、領域中心ないし領域の総数は、一つ増加することになる。
【００３６】
ステップＳ２０５で画素を再配置し、またはステップＳ２０６で一つの画素からなる領域を新たに生成したら、次にステップＳ２０７で、ステップＳ２０２で選択すべき画素をすべて選択したか否かを判断し、すべて選択していなければ、ステップＳ２０２に戻って、次の選択すべき画素を選択して、その選択した画素につき、ステップＳ２０３以降の処理を繰り返す。
【００３７】
ステップＳ２０７で、ステップＳ２０２で選択すべき画素をすべて選択したと判断したときには、次にステップＳ２０８に進んで、ステップＳ２０５でそれぞれの領域中心の領域に再配置した画素の特徴ベクトルの平均を、それぞれの領域ごとに新たな領域中心として算出する。
【００３８】
次にステップＳ２０９で、その算出した新たな領域中心を前の領域中心と置き換える。その際、新たな領域中心と前の領域中心との特徴空間における距離を、それぞれの領域ごとに算出し、その距離があらかじめ定められた閾値以上であれば、領域がいまだ収束していないことを示すフラグを立てる。
【００３９】
次にステップＳ２１０で、そのフラグが立っていないか否かを見て、領域が収束したか否かを判断し、フラグが立っていて、領域が収束していないときには、ステップＳ２１１に進んで、それぞれの領域中心の領域から、これに再配置された画素を削除した上で、ステップＳ２０２に戻って、画素の選択から上記の処理を繰り返す。
【００４０】
ステップＳ２１０で、フラグが立っていないことにより、領域が収束したと判断したときには、領域推定の処理を終了する。
【００４１】
ステップＳ３０では、図７に示すように（ただし、ステップＳ３０２の対象部分画像は入力画像に置き換える）、まずステップＳ３０１で、初期領域中心として、上記の領域推定ステップＳ２０で算出した領域中心を設定する。ただし、それぞれの領域中心の領域に再配置されている画素は削除しておく。
【００４２】
次にステップＳ３０２で、入力画像の画素を間引き率Ｒ＝Ｒｂ（Ｒｂ＜Ｒａ）で間引いて一つ選択する。この画素の選択は、例えば、図６の領域推定ステップＳ２０のステップＳ２０２での画素の選択と同様に、上記の式（１）の条件を満たす画素を一つずつ順に選択することによって行う。
【００４３】
次のステップＳ３０３以降については、図６の領域推定ステップＳ２０のステップＳ２０３以降と同じである。
【００４４】
ステップＳ４０では、図８に示すように（ただし、ステップＳ４０２の対象部分画像は入力画像に置き換える）、まずステップＳ４０１で、初期領域中心として、上記の領域生成ステップＳ３０で算出した領域中心を設定する。ただし、それぞれの領域中心の領域に再配置されている画素は削除しておく。
【００４５】
次にステップＳ４０２で、入力画像に含まれるすべての画素を一つずつ選択する。これは、間引き率Ｒを１とすればよい。しかし、入力画像に含まれるすべての画素を順に選択するにもかかわらず、上記の式（１）の条件判断を行うのは、無駄である。したがって、領域確定ステップＳ４０では、再配置のみを行うフラグを作成しておいて、このフラグが立っていれば、入力画像の画素を無条件に順に選択するように構成することができる。
【００４６】
次にステップＳ４０３で、処理の効率化のために、領域推定ステップＳ２０のステップＳ２０３および領域生成ステップＳ３０のステップＳ３０３とは違って無条件で、選択した画素に最も近い距離を有する領域中心を探索し、次にステップＳ４０５で、処理の効率化のために、領域推定ステップＳ２０のステップＳ２０４および領域生成ステップＳ３０のステップＳ３０４のような判断をすることなく、かつ領域推定ステップＳ２０のステップＳ２０６および領域生成ステップＳ３０のステップＳ３０６のように選択した一つの画素からなる領域を新たに生成することなく、選択した画素を、これに最も近い距離を有する領域中心の領域に配分する。
【００４７】
この処理の効率と生成される領域の精度とは、トレードオフの関係にあり、要求する分割内容に応じて、領域生成ステップＳ３０における間引き率Ｒｂを調整する。
【００４８】
次にステップＳ４０７で、ステップＳ４０２で入力画像のすべての画素を選択したか否かを判断し、すべての画素を選択していなければ、ステップＳ４０２に戻って、次の選択すべき画素を選択して、その選択した画素につき、ステップＳ４０３以降の処理を繰り返す。
【００４９】
次のステップＳ４０８以降については、領域推定ステップＳ２０のステップＳ２０８以降および領域生成ステップＳ３０のステップＳ３０８以降と同じである。
【００５０】
上記の例は、領域推定ステップＳ２０および領域生成ステップＳ３０で単純間引きを用いる場合であるが、入力画像の色分布の特徴をできるだけ保持し、かつ入力画像より画素総数が少なくなる間引き方法であれば、いかなる間引き方法でもよく、例えば、入力画像のＲ2（Ｒａ2またはＲｂ2）個の画素の平均値や中央値を間引き画像として用いることができる。
【００５１】
上述した第１の実施形態によれば、所定の間引き率Ｒｂの間引き画像により入力画像の領域の数および中心を算出し、その算出した領域に入力画像に含まれるすべての画素を配分するので、領域の収束までに要する時間を大幅に短縮でき、入力画像を高速に領域分割することができるとともに、領域の数および中心の算出に当たっては、より大きい間引き率Ｒａの間引き画像により入力画像の領域のおおよその数および中心を推定し、その推定結果を用いて、所定の間引き率Ｒｂの間引き画像により入力画像の領域の数および中心を算出するので、当初から所定の間引き率Ｒｂの間引き画像により入力画像の領域の数および中心を算出する場合に比べて、領域の数および中心の算出に要する時間をより短縮することができる。
【００５２】
〔第２の実施形態〕
図３は、この発明の画像領域分割装置の第２の実施形態を示し、画像のブロック化を利用して入力画像を領域分割する場合である。この実施形態の画像領域分割装置は、画像入力部１０、対象部分画像抽出部５０および部分画像領域分割部６０によって構成される。画像入力部１０は、図１のそれと同じである。
【００５３】
対象部分画像抽出部５０は、画像入力部１０で入力画像データとして得られる入力画像を複数のブロック画像に分割したときの、注目ブロック画像およびこれに隣接する算出済みの領域に含まれる画素からなる対象部分画像を、複数のブロック画像中の異なるブロック画像を順次、注目ブロック画像として、順次抽出する。ただし、対象部分画像は、画素の色ベクトルの３成分と画素の画像平面におけるＸＹ座標とを保持するものとする。対象部分画像抽出部５０は、その抽出した対象部分画像を一時的に記憶しておく記憶部を内部に備える。
【００５４】
部分画像領域分割部６０は、この対象部分画像抽出部５０で順次抽出された対象部分画像を順次、領域分割する。また、部分画像領域分割部６０は、領域分割によって算出した領域データを内部の記憶部に記憶するとともに、すべてのブロック画像に対する処理が終了したか否かを判定して、その判定出力を対象部分画像抽出部５０に送出する。
【００５５】
図４は、図３の画像領域分割装置に対応する、この発明の画像領域分割方法の第２の実施形態を示し、まずステップＳ５０で、複数のブロック画像のうちのあるものを注目ブロック画像として対象部分画像を抽出し、次にステップＳ６０で、その対象部分画像を領域分割し、次にステップＳ７０で、最後のブロック画像を含む最終部分画像を領域分割したか否かを判断し、最終部分画像を領域分割していなければ、ステップＳ５０に戻って、次のブロック画像を注目ブロック画像として次の対象部分画像を抽出し、ステップＳ６０で、その対象部分画像を領域分割する。そして、ステップＳ７０で最終部分画像を領域分割したと判断したときには、入力画像の領域分割を終了する。
【００５６】
入力画像は、例えば、図１０（Ｂ）に示すように、Ｘ方向に６分割、Ｙ方向に４分割し、総計２４個のブロック画像ｆ１１，ｆ１２‥‥ｆ４５，ｆ４６に分割する。そして、例えば、図１０（Ｃ）に示すように、ｆ１１，ｆ１２……ｆ１６，ｆ２１，ｆ２２……ｆ２６，ｆ３１，ｆ３２‥‥ｆ３６，ｆ４１，ｆ４２‥‥ｆ４６の順序で注目ブロック画像とする。ただし、注目ブロック画像とする順序は、これに限らず、任意にすることができる。また、２つ以上のブロック画像を同時に注目ブロック画像として、並列に処理することも可能である。
【００５７】
注目ブロック画像は、例えば、以下のようにして抽出する。まず、図１０（Ｂ）に示すような入力画像Ｉｉの幅（画素数）Ｗおよび高さ（画素数）Ｈを、それぞれ、あらかじめ定められた一つのブロック画像のＸ方向およびＹ方向のおおよその大きさ（画素数）Ｎｏで除して、小数点以下を切り捨てることにより、入力画像ＩｉをＸ，Ｙ方向に分割したときのＸ，Ｙ方向の分割数Ｎｘ，Ｎｙを算出する。
【００５８】
次に、次の式（３）によって、注目ブロック画像として抽出する図１０（Ａ）に示すようなブロック画像ｆ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）（ただし、１≦ｎ≦対象部分画像の画素総数）から、第１の実施形態で示した式（１）の条件を満たす画素を一つずつ順に選択することによって行う。
【００９４】
次のステップＳ２０３以降については、第１の実施形態で示したのと同じである。
【００９５】
領域生成部３０では、図７に領域生成ステップＳ３０として示すように、まずステップＳ３０１で、初期領域中心として、上記の領域推定ステップＳ２０で算出した領域中心を設定する。ただし、それぞれの領域中心の領域に再配置されている画素は削除しておく。
【００９６】
次にステップＳ３０２で、対象部分画像の画素を間引き率Ｒ＝Ｒｂ（Ｒｂ＜Ｒａ）で間引いて一つ選択する。この画素の選択は、例えば、図６の領域推定ステップＳ２０のステップＳ２０２での画素の選択と同様に、第１の実施形態で示した式（１）の条件を満たす画素を一つずつ順に選択することによって行う。
【００９７】
次のステップＳ３０３以降については、図６の領域推定ステップＳ２０のステップＳ２０３以降と同じである。
【００９８】
領域確定部４０では、図８に領域確定ステップＳ４０として示すように、まずステップＳ４０１で、初期領域中心として、上記の領域生成ステップＳ３０で算出した領域中心を設定する。ただし、それぞれの領域中心の領域に再配置されている画素は削除しておく。
【００９９】
次にステップＳ４０２で、対象部分画像に含まれるすべての画素を一つずつ選択する。これは、間引き率Ｒを１とすればよい。しかし、対象部分画像に含まれるすべての画素を順に選択するにもかかわらず、上記の式（１）の条件判断を行うのは、無駄である。したがって、領域確定ステップＳ４０では、再配置のみを行うフラグを作成しておいて、このフラグが立っていれば、対象部分画像の画素を無条件に順に選択するように構成することができる。
【０１００】
次のステップＳ４０３以降については、第１の実施形態で示したのと同じである。ただし、ステップＳ４０７では、対象部分画像のすべての画素を選択したか否かを判断する。
【０１０１】
上記の例は、領域推定ステップＳ２０および領域生成ステップＳ３０で単純間引きを用いる場合であるが、対象部分画像の色分布の特徴をできるだけ保持し、かつ対象部分画像より画素総数が少なくなる間引き方法であれば、いかなる間引き方法でもよく、例えば、対象部分画像のＲ2（Ｒａ2またはＲｂ2）個の画素の平均値や中央値を間引き部分画像として用いることができる。
【０１０２】
上述した第３の実施形態によれば、第２の実施形態よりも、より高速で領域分割を行うことができるとともに、第２の実施形態と同様に、ブロック画像間の不整合を生じることがなく、不自然な領域分割となることがない。
【０１０３】
〔第４の実施形態〕
図１３は、この発明の画像領域分割方法の第４の実施形態を示し、画像のブロック化や間引きを用いることなく、Ｋ平均アルゴリズムに改良を加えたクラスタリング手法によって、入力画像を領域分割する場合である。
【０１０４】
この実施形態では、まずステップＳ１０１で、クラスタ数Ｋを適切に選んで、入力画像に対して初期領域中心を設定し、次にステップＳ１０２で、入力画像に含まれる画素を一つ選択する。
【０１０５】
次にステップＳ１０３で、その選択した画素の特徴ベクトルＰ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以上であるときには、領域が収束する前に対象画素一つからなる領域を生成するので、領域の収束までに要する時間を短縮することができる。
【図面の簡単な説明】
【０１１５】
【図１】この発明の装置の第１の実施形態を示す図である。
【図２】この発明の方法の第１の実施形態を示す図である。
【図３】この発明の装置の第２の実施形態を示す図である。
【図４】この発明の方法の第２の実施形態を示す図である。
【図５】この発明の装置の第３の実施形態を示す図である。
【図６】この発明の方法の第３の実施形態の領域推定ステップの例を示す図である。
【図７】この発明の方法の第３の実施形態の領域生成ステップの例を示す図である。
【図８】この発明の方法の第３の実施形態の領域確定ステップの例を示す図である。
【図９】入力画像とその間引きの説明に供する図である。
【図１０】入力画像のブロック化の説明に供する図である。
【図１１】ブロック化の場合の領域分割の説明に供する図である。
【図１２】ブロック化の場合の対象部分画像の抽出の説明に供する図である。
【図１３】この発明の方法の第４の実施形態を示す図である。
【符号の説明】
【０１１６】
主要部については図中に全て記述したので、ここでは省略する。
【図１】
2005011375.tif 000003
【図２】
2005011375.tif 000004
【図３】
2005011375.tif 000005
【図４】
2005011375.tif 000006
【図５】
2005011375.tif 000007
【図６】
2005011375.tif 000008
【図７】
2005011375.tif 000009
【図８】
2005011375.tif 000010
【図９】
2005011375.tif 000011
【図１０】
2005011375.tif 000012
【図１１】
2005011375.tif 000013
【図１２】
2005011375.tif 000014
【図１３】
2005011375.tif 000015