(57)【特許請求の範囲】
【請求項１】
画像中の複数の領域に対してそれぞれ代表データを設定する代表データ設定手段と、
前記代表データとの座標及び色に係る距離に基づいて、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け手段と、
前記関連付け手段によって関連付けされた画素の集合で構成された領域の評価値を算出する算出手段と、
前記評価値の目標値を設定する目標値設定手段と、
前記評価値が前記目標値に近づくように前記座標と前記色との間の重みを制御する重み制御手段とを備え、
前記関連付け手段は、前記重み制御手段によって制御された重みに従って前記座標及び色に係る距離を算出し、前記算出された距離に基づいて、前記画像中のそれぞれの画素を前記何れかの代表データと関連付けることを特徴とする画像処理装置。
【請求項２】
前記代表データ設定手段は、前記関連付けられた画素の集合に基づいて前記それぞれの代表データを更新することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記重み制御手段は、前記座標と前記色との間の重みを前記関連付けされた画素の集合で構成された領域の単位で制御することを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記重み制御手段は、前記座標と前記色との間の重みをブロック単位で制御することを特徴とする請求項１又は２に記載の画像処理装置。
【請求項５】
前記重み制御手段は、前記座標と前記色との間の重みを画像単位で制御することを特徴とする請求項１又は２に記載の画像処理装置。
【請求項６】
前記算出手段は、前記関連付けされた画素の集合で構成された領域の形状の複雑度を前記評価値として算出することを特徴とする請求項１〜５の何れか１項に記載の画像処理装置。
【請求項７】
前記算出手段は、前記関連付けされた画素の集合で構成された領域における色特徴の統計量を前記評価値として算出することを特徴とする請求項１〜５の何れか１項に記載の画像処理装置。
【請求項８】
所定の条件を満たした場合に前記関連付けされた画素の集合で構成された領域の結果を出力する出力手段をさらに備えることを特徴とする請求項１〜７の何れか１項に記載の画像処理装置。
【請求項９】
画像中の複数の領域に対してそれぞれ代表データを設定する代表データ設定工程と、
前記代表データとの座標及び色に係る距離に基づいて、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け工程と、
前記関連付け工程において関連付けされた画素の集合で構成された領域の評価値を算出する算出工程と、
前記評価値の目標値を設定する目標値設定工程と、
前記評価値が前記目標値に近づくように前記座標と前記色との間の重みを制御する重み制御工程とを備え、
前記関連付け工程においては、前記重み制御工程において制御された重みに従って前記座標及び色に係る距離を算出し、前記算出された距離に基づいて、前記画像中のそれぞれの画素を前記何れかの代表データと関連付けることを特徴とする画像処理方法。
【請求項１０】
画像中の複数の領域に対してそれぞれ代表データを設定する代表データ設定工程と、
前記代表データとの座標及び色に係る距離に基づいて、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け工程と、
前記関連付け工程において関連付けされた画素の集合で構成された領域の評価値を算出する算出工程と、
前記評価値の目標値を設定する目標値設定工程と、
前記評価値が前記目標値に近づくように前記座標と前記色との間の重みを制御する重み制御工程とをコンピュータに実行させ、
前記関連付け工程においては、前記重み制御工程において制御された重みに従って前記座標及び色に係る距離を算出し、前記算出された距離に基づいて、前記画像中のそれぞれの画素を前記何れかの代表データと関連付けることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特に、画像を座標など属性が類似した複数の領域に分割するために用いて好適な画像処理装置、画像処理方法及びプログラムに関する。
【背景技術】
【０００２】
近年、画像を色やテクスチャ、座標など属性が類似した複数の領域に分割する技術が注目されている。このように分割された領域はスーパーピクセルと呼ばれ、分割された領域の単位で符号化処理や、画像処理、画像認識処理等を実行できるため、様々な画像処理装置におけて応用することができる。
【０００３】
従来、画像の領域分割に関して様々な手法が提案されている。特に、画素をクラスタリングすることによって画像を複数の領域に分割する手法が多く提案されている。これらの手法では、色やテクスチャ、座標を要素にもつデータをクラスタリングし、クラスタリングでは、各クラス（領域）の代表データを求め、入力データを最近傍代表データに割り当てる。ここで、最近傍代表データとは、入力データに対する複数の代表候補データの中で、入力データとの距離が最短の代表候補データのことである。
【０００４】
非特許文献１には、ＳＬＩＣ（Simple Linear Iterative Clustering）と呼ばれるクラスタリング手法を用いて複数の領域に分割する方法が提案されている。ＳＬＩＣは、Ｋ−ｍｅａｎｓクラスタリングの最近傍代表データの探索範囲を画像中の局所領域に限定した手法である。ＳＬＩＣでは、クラスタリングの距離関数として座標空間の距離と色空間の距離との重み付き総和を用いている。非特許文献１には、これら二つの距離の重みを適応的に設定する方法としてＡＳＬＩＣ（Adaptive-SLIC）が提案されている。ＡＳＬＩＣでは、各領域の代表データからの色空間の距離と座標空間の距離との最大値を用いて色距離と座標距離とを正規化することにより二つの重みを適応的に設定している。
【０００５】
また、非特許文献２に記載の手法では、入力データと代表候補データとの距離計算において、注目する入力データの近傍に異なるクラスの入力データが存在する程距離が大きくなる項を導入している。これにより、分割される形状が円形に近くなるようにクラスタリングしている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Radhakrishna Achanta, et al., "SLIC Superpixels Compared to State-of-the-Art Superpixel Methods," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, No. 11, pp. 2274-2282, Nov. 2012.
【非特許文献２】J. Wang, and X. Wang, "VCells: Simple and Efficient Superpixels Using Edge-Weighted Centroidal Voronoi Tessellations," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, No. 6, pp. 1241-1247, Jun. 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
クラスタリングは画像の領域分割においてよく用いられる技術である。ただし、クラスタリングによる領域分割では、フラグメンテーションが発生することがある。フラグメンテーションとは、同一クラス内の画素が座標空間上で連続していない状態のことである。領域分割結果を応用する場合には、フラグメンテーションが発生しないことが好ましい。
【０００８】
フラグメンテーションの発生度合いは、色距離の重み及び座標距離の重みの設定によって変化する。色距離の重みを大きくした場合は、色のエッジで領域が分割される傾向が強くなるが、フラグメンテーションが発生し易い傾向となる。一方、座標距離の重みを大きくした場合は逆の傾向となり、フラグメンテーションは発生し難い傾向となるが、色のエッジで領域分割され難くなる傾向となる。このように領域分割精度とフラグメンテーションとではトレードオフの関係にあり、領域分割の応用先が必要とする領域分割精度とフラグメンテーションの発生度合いとを満たす重みを決定することが難しいという課題がある。
【０００９】
非特許文献１に開示されているＡＳＬＩＣでは、前述したように、各領域の代表点データからの色距離の最大値と座標距離の最大値とを用いて色距離と座標距離とを正規化し、二つの距離の重みを適応的に決定している。しかし、この方法は座標距離と色距離とを正規化しているのであって、フラグメンテーションの軽減という目標に基づいて重みを決定しているわけではない。したがって、ＡＳＬＩＣでは、領域分割の応用先が必要とする領域分割精度とフラグメンテーションの発生度合いとを満たす結果に必ずしもなっていないという課題がある。
【００１０】
また、非特許文献２に記載の方式では、フラグメンテーションの発生を抑制することができるが、各入力データについて代表候補データとの距離計算時に、近傍の入力データのクラス情報を参照する必要がある。このため、処理コストが大きいという課題がある。
【００１１】
本発明は前述の問題点に鑑み、所望の領域分割精度で画像の領域分割を行う際に、処理コストを抑えてフラグメンテーションの発生を抑制できるようにすることを目的としている。
【課題を解決するための手段】
【００１２】
本発明に係る画像処理装置は、画像中の複数の領域に対してそれぞれ代表データを設定する代表データ設定手段と、前記代表データとの座標及び色に係る距離に基づいて、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け手段と、前記関連付け手段によって関連付けされた画素の集合で構成された領域の評価値を算出する算出手段と、前記評価値の目標値を設定する目標値設定手段と、前記評価値が前記目標値に近づくように前記座標と前記色との間の重みを制御する重み制御手段とを備え、前記関連付け手段は、前記重み制御手段によって制御された重みに従って前記座標及び色に係る距離を算出し、前記算出された距離に基づいて、前記画像中のそれぞれの画素を前記何れかの代表データと関連付けることを特徴とする。
【発明の効果】
【００１３】
本発明によれば、所望の領域分割精度で画像の領域分割を行う際に、処理コストを抑えてフラグメンテーションの発生を抑制することができる。
【図面の簡単な説明】
【００１４】
【図１】実施形態におけるクラスタリング処理の処理手順の一例を示すフローチャートである。
【図２】画像中のブロック及びその代表データを説明するための図である。
【図３】フラグメンテーションが発生している領域分割結果の一例を示す図である。
【図４】実施形態におけるデータ処理装置のハードウェア構成例を示すブロック図である。
【発明を実施するための形態】
【００１５】
以下、本発明の好適な実施形態について、図面を参照しながら詳細に説明する。本実施形態では、本発明による画像領域分割方法を用いて画像を領域分割する例について説明する。
【００１６】
＜データ処理装置の構成例＞
図４は、本実施形態におけるクラスタリング方法を実現可能なデータ処理装置４００のハードウェア構成例を示すブロック図である。
図４において、データ保存部４０１は、画像データを保持する記憶媒体である。データ保存部４０１は、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＣＤ−ＲやＤＶＤ、メモリーカード、ＣＦカード、スマートメディア、ＳＤカード、メモリスティック、ｘＤピクチャーカード、ＵＳＢメモリ等で構成される。また、データ保存部４０１には、画像データの他にも、プログラムやその他のデータを保存することも可能である。あるいは、後述するＲＡＭ４０６の一部をデータ保存部４０１として用いてもよい。さらに、後述する通信部４０２により接続した先の機器の記憶装置を、通信部４０２を介して利用するというように仮想的に構成するのであってもよい。
【００１７】
表示部４０３は、領域分割処理を行う前後の画像を表示したり、ＧＵＩ等の画像を表示したりする装置であり、一般的にはＣＲＴや液晶ディスプレイなどが用いられる。あるいは、ケーブル等で接続された外部のディスプレイ装置であっても構わない。
【００１８】
ＣＰＵ４０４は、本実施形態に係る主要な処理を実行すると共にデータ処理装置４００全体の動作を制御する。ＲＯＭ４０５及びＲＡＭ４０６は、その処理に必要なプログラム、データ、作業領域などをＣＰＵ４０４に提供する。後述する処理に必要なプログラムがデータ保存部４０１に格納されている場合や、ＲＯＭ４０５に格納されている場合には、ＲＡＭ４０６に一旦書き込まれてから後述する処理が実行される。また、通信部４０２を経由してデータ処理装置４００がプログラムを受信する場合には、データ保存部４０１に一旦記録した後にＲＡＭ４０６に書き込まれるか、通信部４０２からＲＡＭ４０６に直接書き込まれてから処理が実行される。
【００１９】
ＣＰＵ４０４は、ＲＡＭ４０６またはデータ保存部４０１に書き込まれた画像データを読み出して本実施形態に係る画像処理（クラスタリング処理）を実行する。代表データ等の処理途中のデータはＣＰＵ４０４によりＲＡＭ４０６に書き込まれ、必要な場合に読み出される。そして、クラスタリングの処理結果がＲＡＭ４０６に書き込まれる。また、ＣＰＵ４０４は、表示部４０３に画像を表示する制御を行ったり、通信部４０２を介して外部装置に画像データを送信する制御を行ったりする。
【００２０】
通信部４０２は、機器間の通信を行うためのＩ／Ｆである。Ｉ／Ｆとしては、例えば、公知のローカルエリアネットワーク、ＵＳＢ、ＩＥＥＥ１２８４、ＩＥＥＥ１３９４、電話回線などの有線による通信方式であってもよい。また、赤外線（ＩｒＤＡ）、ＩＥＥＥ８０２．１１ａ、ＩＥＥＥ８０２．１１ｂ、ＩＥＥＥ８０２．１１ｇ、ＩＥＥＥ８０２．１１ｎ、Ｂｌｕｅｔｏｏｔｈ（登録商標）、ＵＷＢ（Ｕｌｔｒａ  ｗｉｄｅ  Ｂａｎｄ）等の無線通信方式であってもよい。
【００２１】
なお、図４に示す例では、データ保存部４０１、表示部４０３が全て１つの装置内に含まれるような例を示しているが、これらの部分が公知の通信方式による通信路で接続されており、全体としてこのような構成となっているのであっても構わない。また、図４に示す例においては、ＣＰＵが１つだけの構成であるが、ＣＰＵを複数設けるような構成にしてもよい。システム構成については、上記以外にも様々な構成要素が存在してもよいが、本発明の主眼ではないのでその説明は省略する。
【００２２】
以下、図４に示したデータ処理装置４００が行う処理の概要について説明する。本実施形態では、画素データを二次元の座標と三次元の色特徴と計五次元の入力データとして使用し、この入力データを代表データにクラスタリングすることによって領域分割を行う。このとき、代表データと入力データとの間の距離は、座標空間上の距離（以下、座標距離）と色空間上の距離（以下、色距離）との重み付き総和で定義する。
【００２３】
座標距離及び色距離の重みは領域分割の結果を左右するパラメータであるため、領域分割の応用先で必要となる領域分割精度及び領域形状を得るためには適切な重みを設定する必要がある。そこで本実施形態では、領域分割結果を評価する評価関数とその目標値とを定義し、領域分割結果の評価値が目標値に近づくように重みを制御する。また、本実施形態では、領域のフラグメンテーションを軽減するために、評価関数として領域形状の複雑度を用い、各領域の複雑度が目標値に近づくように領域単位で重みを制御する。
【００２４】
＜領域分割のためのクラスタリング＞
図１は、本実施形態におけるクラスタリング処理の処理手順の一例を示すフローチャートである。なお、図１に示す各ステップはＣＰＵ４０４の動作を示すものとする。
まず、クラスタリング対象のデータについて説明する。以下の式（１）は第ｉ番目の入力データを示す。入力データは画像中の画素と対応する５次元のベクトルであり、第ｉ番目の入力データとは、画像をラスタスキャンして第ｉ番目に読み出された画素に関する情報である。
Ｘi＝（ｘi,1，ｘi,2，ｘi,3，ｘi,4，ｘi,5）    ・・・（１）
【００２５】
式（１）中のｘi,1、ｘi,2は二次元の座標空間上の位置を表し、それぞれ画像の縦方向、横方向の座標値を意味する。また、ｘi,3、ｘi,4、ｘi,5は画素の色成分を表わす三次元の色特徴である。
【００２６】
まず、ステップＳ１０１においては、初期化した代表データを生成する。具体的には、代表データ設定処理として、例えば図２に示した画像２０１を座標空間上のブロックに分割し、各々のブロック２０３の中に１個の代表データ２０５を設定する。そして、ブロック２０３内の入力データをランダムに選択し、選択した入力データの座標と色特徴とを要素とするベクトルをその代表データのベクトルとする。以下の式（２）は第ｊ番目の代表データＣjを示す。ここで、ｊとは、図２に示すように配置した代表データにラスター順に割り当てたインデックスである。
Ｃj＝（ｃj,1，ｃj,2，ｃj,3，ｃj,4，ｃj,5）      ・・・（２）
【００２７】
式（２）中のｃj,1、ｃj,2は二次元の座標空間上の位置を表し、それぞれ画像の縦方向、横方向の座標値を意味する。また、ｃj,3、ｃj,4、ｃj,5は画素の色成分を表わす三次元の色特徴である。
【００２８】
次にステップＳ１０２においては、領域分割結果の評価値の目標値を設定する。領域分割結果の評価関数及び目標値の定義については後述する。
【００２９】
ステップＳ１０３においては、所定の最大繰り返し回数を設定し、繰り返し回数ｔを制御してステップＳ１０４〜Ｓ１１３までの繰り返し計算のループを開始する。ｔの初期値は１とする。
ステップＳ１０４においては、入力データのループを開始する。画像の中の入力データＸiの順番ｉを制御し、ステップＳ１０５からステップＳ１０９までの処理を繰り返して全ての入力データをクラスタリングする。
【００３０】
まず、ステップＳ１０５において、探索範囲を設定する。具体的には、入力データの座標位置によって代表候補データの探索範囲を設定する。ここで、入力データの代表候補データとは、該当する入力データを割り当てる（帰属させる）代表データの候補である。
【００３１】
ここで、探索範囲２０２の幅および高さがそれぞれ５個の代表データの例について説明する。まず、処理対象の入力データ（以下、注目入力データ）２０６が含まれるブロックを中心に、代表候補データの探索範囲を設定する。この場合、探索範囲は５×５個の座標近傍の代表データである。探索範囲２０２は、縦方向が５〜９までであり、横方向が６〜１０までである。図２に示す例の場合、１ラインあたりの代表データ数が１５個であるため、探索範囲２０２に含まれるインデックスは、６６〜７０、８１〜８５、９６〜１００、１１１〜１１５、１２６〜１３０である。したがって、注目入力データ２０６を含め、ブロック２０４の範囲に入っている全ての入力データの探索範囲２０２は同じである。なお、入力データの位置と探索範囲の代表候補データとの関係は最初に固定され、繰り返し処理によって代表データの位置が変わっても、代表データのインデックスは変わらないものとする。
【００３２】
ステップＳ１０６〜Ｓ１０８は、入力データの最近傍代表データを探索するステップである。ここで、最近傍代表データとは、入力データとの距離が最短な代表候補データ、即ち、距離空間上一番近い代表データである。各ステップにおける処理内容を説明する前に、本実施形態における入力データと代表候補データとの距離の計算方法について説明する。以下の式（３）は第ｉ番目の入力データと第ｊ番目の代表候補データとの間の距離Ｄ（Ｘi，Ｃj）を表す距離関数である。
Ｄ（Ｘi，Ｃj）＝Ｗ（Ｘi，ｔ）×Ｄs（Ｘi，Ｃj）＋Ｄc（Ｘi，Ｃj）・・・（３）
【００３３】
式（３）中のＤsは座標距離を表し、Ｄcは色距離を表す。また、Ｗ（Ｘi，ｔ）は第ｉ番目の入力データＸiの、第ｔ番目の繰り返しにおける座標距離Ｄsの重みである。重みＷ（Ｘi，ｔ）は、以下の式（４）に示すように、入力データＸiが前回の繰り返しで帰属していた領域Ｓj,t-1に対応する重みＷj,tとなる。ただし、第１番目の繰り返しでは、全てのＸiに対して初期値Ｗ1を座標距離の重みとする。本実施形態では初期値Ｗ1の値を１とする。
【００３４】
【数１】
0006468897.tif 000002
【００３５】
座標距離の重みを大きくした場合、色距離よりも座標距離を重視して領域分割するため、代表データと入力データとで色が多少異なる場合であっても、代表データからの座標位置が近い入力データは同じ領域に分割される傾向となる。一方、座標距離の重みを小さくした場合は、座標距離よりも色距離を重視して領域分割するため、代表データからの座標位置が多少離れていたとしても、代表データと色が似ている入力データは同じ領域に分割される傾向となる。したがって、座標距離の重みを大きくするほどフラグメンテーションは軽減されるが、物体の境界で領域分割され難くなる傾向となる。一方、座標距離の重みを小さくするほど物体の境界で領域分割され易くなるが、フラグメンテーションが増加する傾向となる。
【００３６】
式（３）に示すように、入力データと代表候補データとの間の距離Ｄは、座標距離Ｄsと色距離Ｄcとの重み付き総和により算出される。以下、このように複数の部分距離から算出される距離のことを総合距離と呼ぶ。以下の式（５）及び式（６）は、それぞれ座標距離Ｄs、色距離Ｄcを算出する計算式である。本実施形態では、ユークリッド距離を使用するが、これに限る訳ではない。
【００３７】
【数２】
0006468897.tif 000003
【００３８】
ステップＳ１０６においては、代表候補データのループを開始する。代表候補データＣjの順番ｊを制御し、全ての代表候補データを探索する。そして、ステップＳ１０７において、式（３）に従って第ｉ番目の入力データと第ｊ番目の代表候補データとの間の総合距離を算出する。ステップＳ１０８においては、全ての代表候補データとの総合距離の算出が完了したかどうかを判定する。この判定の結果、全ての代表候補データとの総合距離を算出した場合は、ステップＳ１０９に進み、代表候補データのループを終了する。一方、まだ総合距離を算出していない代表候補データがある場合は、ステップＳ１０７に戻り、次の代表候補データとの総合距離を計算する。
【００３９】
続いてステップＳ１０９においては、ステップＳ１０６〜Ｓ１０８のループで算出された総合距離の中から距離が最短であった代表候補データ（最近傍代表データ）に入力データを帰属（関連付け）させる。そして、ステップＳ１１０において、全ての入力データを処理したかどうかを判定する。この判定の結果、全ての入力データを処理した場合は、ステップＳ１１１に進み、入力データのループを終了する。一方、まだ処理していない入力データがある場合はステップＳ１０４に戻り、次の入力データの処理を開始する。
【００４０】
ステップＳ１１１においては、各代表データに対して、帰属させた入力データのベクトルの平均ベクトルを計算する。そして、その平均ベクトルを該当代表データの新しいベクトルＣjとし、代表データを更新する。次に、ステップＳ１１２おいて、更新後の各領域の評価値を算出する。評価値の算出方法については後述する。
【００４１】
続いてステップＳ１１３において、ステップＳ１０８において入力データと代表候補データとの間の総合距離を算出する際に使用する重みＷ（Ｘi，ｔ）を制御する。この処理では、ステップＳ１１２で算出した評価値が、ステップＳ１０２で設定した目標値に近づくように重みを制御する。この重みの制御については後述する。
【００４２】
次に、ステップＳ１１４において、最大繰り返し回数を超えるかどうか、又はクラスタリングの結果が収束したかどうかを判定する。この判定の結果、何れかの条件が成立する場合は、繰り返し計算を終了する。一方、いずれの条件も成立しない場合はステップＳ１０４に戻り、次の繰り返し計算を開始する。以上の処理が完了すると、ＣＰＵ４０４はクラスタリング結果（領域分割結果）を表示部４０３などに出力する。
【００４３】
＜領域の評価値計算＞
次に、ステップＳ１１２における評価値の算出について説明する。本実施形態では、各領域の評価値として領域形状の複雑度を用いる。各領域の評価値はステップＳ１１３の座標距離の重み制御に用いられる。また、各々の領域は、代表データに帰属する入力データの集合によって構成される。以下の式（７）から式（１１）に評価値の計算式を示す。
【００４４】
【数３】
0006468897.tif 000004
【００４５】
領域Ｓj,tの評価値Ｅ（Ｓj,t）は、式（７）に示すように、領域Ｓj,tの面積Ｅs（Ｓj,t）と、領域Ｓj,tの輪郭長Ｅc（Ｓj,t）とを用いて計算される。面積Ｅs（Ｓj,t）は、式（８）に示すように領域Ｓj,tの要素数で定義される。輪郭長Ｅc（Ｓj,t）は、式（９）に示すように、領域Ｓj,tの要素である入力データＸiのうち、領域境界と判定された入力データの総数である。
【００４６】
Ｃｏｎｔｏｕｒ（Ｘi）は入力データＸiが領域境界であるか否かを判定する関数であり、式（１０）に示すように、入力データＸiの周囲８近傍の入力データが帰属する領域番号を参照して計算される。周囲８近傍の入力データが、全て注目入力データＸiと同じ領域に帰属していた場合、注目入力データを非領域境界と判定し、Ｃｏｎｔｏｕｒ（Ｘi）は０となる。周囲８近傍の入力データの中に、１つでも注目入力データＸiと異なる領域に帰属している入力データがある場合は、注目入力データを領域境界と判定し、Ｃｏｎｔｏｕｒ（Ｘi）は１となる。Ｌ（ｘ，ｙ）は座標位置（ｘ，ｙ）の入力データが属する領域番号を示し、δ（ｘ）はｘ＝０の時に１、それ以外のｘについては０となる関数である。
【００４７】
評価値Ｅ（Ｓj,t）は領域の複雑度を示している。例えば図３に示すように、領域３０１から領域３０３、領域３０４から領域３０７、領域３０８から領域３１５、および領域３１６から領域３１７ではフラグメンテーションが発生している。これらの領域のように、凹凸が大きい場合や、領域Ｓj,tが座標空間上で連続していない場合は複雑度が大きくなる。領域Ｓj,tに含まれる全ての入力データが互いに座標空間上で不連続である場合は、領域の輪郭長は面積と等しくなり、複雑度は１となる。一方、領域３１８のように凹凸が少なく、全ての入力データが座標空間上で隣接しているような場合は複雑度が小さくなる。以上のようにフラグメンテーションが生じている領域は複雑度が大きくなる傾向があり、フラグメンテーションが発生していない領域は複雑度が小さくなる傾向がある。
【００４８】
＜重みの目標値設定＞
ステップＳ１０２では、ステップＳ１１２で計算する評価値の目標値を設定する。本実施形態では、評価値Ｅ（Ｓj,t）の目標値Ｔを以下の式（１２）により計算する。目標値Ｔは式（１２）に示すように、領域形状が横Ｌx、縦Ｌyの矩形形状となった場合の評価値に対して、２０％の複雑さを考慮した値である。横Ｌx及び縦Ｌyの長さは、それぞれ式（１３）、式（１４）に示すように、幅Ｉx、高さＩyの画像を横方向にＮx個、縦方向にＮy個の均一な矩形領域で分割した際の辺の長さを示す。
【００４９】
【数４】
0006468897.tif 000005
【００５０】
＜重み制御＞
ステップＳ１１３では、ステップＳ１０２で設定した目標値Ｔと、ステップＳ１１２で計算した評価値Ｅ（Ｓj,t）とを用いて、第ｔ＋１番目の繰り返しにおける座標距離の重みＷj,t+1を計算する。以下の式（１５）は重みの制御式を示している。ｋは制御の強さを示す制御係数であり、本実施形態ではｋの値を０．１と設定する。第１番目の繰り返しでは重みの初期値Ｗ1に対して制御を行い、第２番目以降の繰り返しでは現在の重みＷj,tに対して制御を行う。
【００５１】
【数５】
0006468897.tif 000006
【００５２】
式（１５）の制御により、領域の形状が目標よりも複雑である領域は、座標距離の重みが増加するため、次の領域分割では領域形状が単純になり、評価値が小さくなることが期待できる。領域の形状が目標よりも単純である領域は、座標距離の重みが減少するため、次の繰り返しでは領域形状が複雑になり、評価値が大きくなることが期待できる。
【００５３】
以上説明したように、本実施形態の方式によれば、各領域の形状の複雑度が目標値に近づくように座標距離の重みを制御するようにしたので、フラグメンテーションを軽減することが可能である。
【００５４】
（その他の実施形態）
前述した実施形態では、座標距離の重みを領域単位で制御する例を示したが、本発明はこれに限定するものではなく、画像のブロック単位で重みを制御することも可能である。以下の式（１６）は、注目入力データＸiの重みＷ（Ｘi，ｔ）を示している。
【００５５】
【数６】
0006468897.tif 000007
【００５６】
式（１６）中のＢjは図２に示すブロックであり、入力データの集合である。例えば、注目入力データ２０６を含むブロックはブロック２０４である。図２に示すように、各ブロックには対応する代表データが存在する。そこで、第ｊ番目のブロックＢjに対応する重みＷj,tは、式（１５）に示すように、第ｊ番目の領域Ｓj,tを用いて制御する。前述の実施形態のように領域単位で重みを制御する場合は、入力データＸiが前回の繰り返しで帰属した領域番号を参照する必要があった。これに対してブロック単位で重みを制御する場合は、領域番号の参照が不要であるため、処理コストがより小さいという利点がある。
【００５７】
また、以下の式（１７）を用いて画像単位で重みを設定することも可能である。Ｗtは第ｔ番目の繰り返しにおける重みである。Ｗtは以下の式（１８）に示すように各領域の評価値平均Ｅ（ｔ）を用いて求めることができる。評価値平均Ｅ（ｔ）は、以下の式（１９）により計算される。画像単位で重みを制御する場合は制御する重みが１つであるため、ブロック単位で重みを制御するよりもさらに処理コストが小さいという利点がある。
【００５８】
【数７】
0006468897.tif 000008
【００５９】
また、前述した実施形態では評価関数として、式（７）から式（１１）に示した領域形状の複雑度を用いたが、本発明はこれに限定するものではない。評価関数には領域分割結果を評価する任意の関数を適用することが可能である。例えば、領域の色特徴の統計量である分散値を評価値に使用し、各領域の色特徴の分散値が同程度になるように領域分割することも可能である。
【００６０】
また、前述した実施形態では一つの評価関数、目標値によって一つの重みを制御したが、本発明はこれに限定するものではない。複数の評価関数、目標値によって複数の重みを制御することも可能である。
【００６１】
また、前述した実施形態では各領域の評価値の目標値の算出方法として、式（１２）から式（１４）を用いたが、本発明はこれに限定するものではない。目標値は、評価関数が取りうる値域の中から任意の値を設定することも可能である。
【００６２】
また、前述した実施形態の処理による領域分割結果は、重みの初期値Ｗ1に依存しているため、初期値の設定によっては良い領域分割結果が得られない可能性がある。そこで、重みの初期値を変えながら、図１のステップＳ１０１からＳ１１４の処理を複数回実施し、最も良い領域分割結果を最終的な出力として選択することも可能である。
【００６３】
また、前述した実施形態では、重みを制御する際の制御係数ｋに定数値を設定したが、本発明はこれに限定するものではない。制御係数ｋを以下の式（２０）に示すような繰り返し数ｔによる単調減少関数ｋ（ｔ）として定義してもよい。なお、ｅは自然対数の底を示す。式（２０）は繰り返し回数ｔによる単調減少関数であるため、ステップＳ１０３の繰り返しの中で重みが振動することなく収束するようになる。
【００６４】
【数８】
0006468897.tif 000009
【００６５】
また、重みの初期値による影響を軽減するため、重みの制御式に外乱項Ｒ（ｔ）を加え、以下の式（２１）及び式（２２）を用いて重みを制御することも可能である。なお、ｒａｎｄ（−１，１）は値域［−１，１］の乱数であり、外乱項Ｒ（ｔ）は繰り返し回数ｔによって値域幅が単調減少する項である。式（２１）及び式（２２）を用いた場合には、ステップＳ１０３の繰り返しの初めの間は、評価値及び目標値に影響を受けない強い外乱によって重みが変化するため、初期値の影響を軽減することが可能である。さらに、制御係数ｋに式（２０）のような単調減少関数を用いる場合は、外乱項の収束速度を制御係数ｋの収束速度よりも大きく設定することにより、重みを安定して収束させることが可能である。
【００６６】
【数９】
0006468897.tif 000010
【００６７】
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサーがプログラムを読出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【符号の説明】
【００６８】
４０１  データ保存部
４０４  ＣＰＵ
【図１】
0006468897.tif 000011
【図２】
0006468897.tif 000012
【図３】
0006468897.tif 000013
【図４】
0006468897.tif 000014