(57)【要約】【課題】属性が類似した複数の領域に画像を分割する際に、処理量を抑えてフラグメンテーションの発生を抑制し、動画に適用できるクラスタリング結果を得ることができるようにする。【解決手段】画像中の画素と対応する５次元のベクトルを入力データとしてクラスタリング処理を行い、クラスタリング結果を解析してフラグメンテーションが発生しているか否かを判定する。そして、フラグメンテーションが発生している場合に、そのクラスに係る代表データの位置を、分割されている何れかの領域の重心位置に補正し、ループ処理によりクラスタリング結果を得る。【選択図】図１
2016194862.tif 000002
【特許請求の範囲】
【請求項１】
画像中の複数の領域に対してそれぞれ代表データを設定する代表データ設定手段と、
前記代表データとの座標、及び、色及びテクスチャのうちの少なくとも何れかに係る距離に基づいて、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け手段と、
前記関連付け手段によって関連付けされた画素の集合で構成された領域が、２つ以上の領域で構成されているか否か判定する判定手段と、
前記判定手段により２つ以上の領域で構成されていると判定された場合に、前記領域に係る代表データの位置を前記２つ以上の領域の何れかに属する位置に補正する補正手段とを有し、
前記関連付け手段は、前記補正手段によって補正された代表データとの前記距離に基づいて、前記画像中のそれぞれの画素を前記何れかの代表データと関連付けることを特徴とする画像処理装置。
【請求項２】
前記代表データ設定手段は、前記代表データのそれぞれを該代表データと前記関連付け手段によって関連付けられた画素の集合に基づいて更新し、
前記補正手段は、前記更新された代表データの位置を補正することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記補正手段は、前記領域に係る代表データを補正する位置を、前記関連付けされた画素の集合で構成された領域において、前記領域に係る代表データからの座標空間上の距離に基づいて決定することを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記補正手段は、前記２つ以上の領域の何れかの領域の重心位置に前記領域に係る代表データの位置を補正することを特徴とする請求項１又は２に記載の画像処理装置。
【請求項５】
前記補正手段は、さらに前記領域に係る代表データと前記領域に係る代表データの近傍に位置する代表データとの間の色空間上の距離に基づいて、当該領域に係る代表データを補正することを特徴とする請求項１又は２に記載の画像処理装置。
【請求項６】
前記補正手段は、さらに前記補正する代表データの色特徴を、補正する位置に係る色特徴に補正することを特徴とする請求項１〜５の何れか１項に記載の画像処理装置。
【請求項７】
前記判定手段は、単位領域サイズあたりの周囲長に基づいて、２つ以上の領域で構成されているか否か判定することを特徴とする請求項１〜６の何れか１項に記載の画像処理装置。
【請求項８】
画像中の複数の領域に対してそれぞれ代表データを設定する代表データ設定工程と、
前記代表データとの座標、及び、色及びテクスチャのうちの少なくとも何れかに係る距離に基づいて、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け工程と、
前記関連付け工程において関連付けされた画素の集合で構成された領域が、２つ以上の領域で構成されているか否か判定する判定工程と、
前記判定工程において２つ以上の領域で構成されていると判定された場合に、前記領域に係る代表データの位置を前記２つ以上の領域の何れかに属する位置に補正する補正工程とを有し、
前記関連付け工程においては、前記補正工程において補正された代表データとの前記距離に基づいて、前記画像中のそれぞれの画素を前記何れかの代表データと関連付けることを特徴とする画像処理方法。
【請求項９】
画像中の複数の領域に対してそれぞれ代表データを設定する代表データ設定工程と、
前記代表データとの座標、及び、色及びテクスチャのうちの少なくとも何れかに係る距離に基づいて、前記画像中のそれぞれの画素を前記複数の領域の中の何れかの代表データと関連付ける関連付け工程と、
前記関連付け工程において関連付けされた画素の集合で構成された領域が、２つ以上の領域で構成されているか否か判定する判定工程と、
前記判定工程において２つ以上の領域で構成されていると判定された場合に、前記領域に係る代表データの位置を前記２つ以上の領域の何れかに属する位置に補正する補正工程とをコンピュータに実行させ、
前記関連付け工程においては、前記補正工程において補正された代表データとの前記距離に基づいて、前記画像中のそれぞれの画素を前記何れかの代表データと関連付けることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特に、画像を座標など属性が類似した複数の領域に分割するために用いて好適な画像処理装置、画像処理方法及びプログラムに関する。
【背景技術】
【０００２】
近年、画像を色やテクスチャ、座標など属性が類似した複数の領域に分割する技術が注目されている。このように分割された領域はスーパーピクセルと呼ばれ、分割された領域の単位で符号化処理や、画像処理、画像認識処理等を実行できるため、様々な画像処理装置におけて応用することができる。
【０００３】
従来、画像の領域分割に関して様々な手法が提案されている。特に、画素をクラスタリングすることによって画像を複数の領域に分割する手法が多く提案されている。これらの手法では、色やテクスチャ、座標を要素にもつデータをクラスタリングし、クラスタリングでは、各クラス（領域）の代表データを求め、入力データを最近傍代表データに割り当てる。ここで、最近傍代表データとは、入力データに対する複数の代表候補データの中で、入力データとの距離が最短の代表候補データのことである。
【０００４】
非特許文献１には、ＳＬＩＣ（Simple Linear Iterative Clustering）と呼ばれるクラスタリング手法を用いて複数の領域に分割する方法が提案されている。ＳＬＩＣは、Ｋ−ｍｅａｎｓクラスタリングの最近傍代表データの探索範囲を画像中の局所領域に限定した手法である。また、特許文献１には、領域の形状が線形状の小領域である場合に、その領域を隣接するクラスに統合する手法が提案されている。
【０００５】
また、非特許文献２に記載の手法では、入力データと代表候補データとの距離計算において、注目する入力データの近傍に異なるクラスの入力データが存在する程距離が大きくなる項を導入している。これにより、分割される形状が円形に近くなるようにクラスタリングしている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第５３３５５８１号公報
【非特許文献】
【０００７】
【非特許文献１】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）＝Ｗ×Ｄs（Ｘi，Ｃj）＋Ｄc（Ｘi，Ｃj）・・・（３）
【００３３】
式（３）中のＤsは座標空間上の距離を表し、Ｄcは色空間上の距離を表す。Ｗは座標空間上の距離に対する重みである。式（３）に示すように、入力データと代表候補データとの間の距離Ｄは、座標空間上の距離Ｄsと色空間上の距離Ｄcの線形結合により算出される。以下、このように複数の部分距離から算出される距離のことを総合距離と呼ぶ。以下の式（４）及び式（５）は、それぞれ座標空間上の距離Ｄs、色空間上の距離Ｄcを算出する計算式である。本実施形態では、距離としてユークリッド距離を使用するが、これに限る訳ではない。
【００３４】
【数１】
2016194862.tif 000003
【００３５】
ステップＳ１０５においては、代表候補データのループを開始する。代表候補データＣjの順番ｊを制御し、全ての代表候補データを探索する。そして、ステップＳ１０６において、式（３）に従って第ｉ番目の入力データと第ｊ番目の代表候補データとの間の総合距離を算出する。ステップＳ１０７においては、全ての代表候補データとの総合距離の算出が完了したかどうかを判定する。この判定の結果、全ての代表候補データとの総合距離を算出した場合は、ステップＳ１０８に進み、代表候補データのループを終了する。一方、まだ総合距離を算出していない代表候補データがある場合は、ステップＳ１０６に戻り、次の代表候補データとの総合距離を計算する。
【００３６】
続いてステップＳ１０８においては、ステップＳ１０５〜Ｓ１０７のループで算出された総合距離の中から距離が最短であった代表候補データ（最近傍代表データ）のクラスに入力データを帰属（関連付け）させる。そして、ステップＳ１０９において、全ての入力データを処理したかどうかを判定する。この判定の結果、全ての入力データを処理した場合は、ステップＳ１１０に進み、入力データのループを終了する。一方、まだ処理していない入力データがある場合はステップＳ１０４に戻り、次の入力データの処理を開始する。
【００３７】
ステップＳ１１０においては、各代表データに対して、帰属させた入力データのベクトルの平均ベクトルを計算する。そして、その平均ベクトルを該当代表データの新しい代表ベクトルＣjとし、代表データを更新する。
【００３８】
ステップＳ１１１においては、フラグメンテーションが発生したクラスの代表データを補正する。なお、この処理の詳細については後述する。そして、ステップＳ１１７において、最大繰り返し回数を超えるかどうか、又はクラスタリングの結果が収束したかどうかを判定する。この判定の結果、何れかの条件が成立する場合は、繰り返し計算を終了する。一方、いずれの条件も成立しない場合はステップＳ１０３に戻り、次の繰り返し計算を開始する。
【００３９】
以上の処理が完了すると、ＣＰＵ４０４はクラスタリング結果（領域分割結果）を表示部４０３などに出力する。ここで、クラスタリング結果とは、各入力データが属するクラスインデックスを示すものである。本実施形態では、入力データと同様に２次元の画像形式で出力するものとする。
【００４０】
＜代表データ補正＞
ここで、ステップＳ１１１の詳細な処理手順について、図１（ｂ）を参照しながら説明する。図１（ｂ）のステップＳ１１２〜Ｓ１１６では、フラグメンテーションが発生したクラスの代表データを補正する。
【００４１】
ここで、フラグメンテーションとは、同一クラスに属する入力データが座標空間上で連続していない状態のことである。図３は、フラグメンテーションが発生したクラスタリング結果の例を説明するための図である。図３において、各々の領域は、代表データに帰属する入力データの集合によって構成され、図３における各領域は、その領域内のクラスインデックスが同一であることを示す。領域３０１〜３０３、領域３０４〜３０７、領域３０８〜３１５、領域３１６〜３１７はそれぞれ同じクラスに属するが、座標空間上で分離している。
【００４２】
ステップＳ１１２においては、各クラスの分布を解析する。本実施形態では、各クラスの領域情報を抽出する。図５は、本実施形態における領域情報を説明するための図である。本実施形態では、領域数、各領域のサイズ、重心座標の３点を領域情報として抽出する。領域情報を抽出する手順を以下に示す。
【００４３】
まず、各クラスの領域数をカウントするためのカウンタをすべて０に初期化する。次に、非特許文献１に記載されているフラグメンテーション解消処理と同様の手法により、クラスタリング結果から座標区間上で連続した同一クラスに属する領域を順次抽出する。そして、抽出された領域のサイズと重心座標とを算出し、そのクラスに対する領域情報として登録する。また、そのクラスの領域数をカウントするカウンタをインクリメントする。
以上の処理を画像中のすべての領域を抽出するまで繰り返す。
【００４４】
次に、ステップＳ１１３において、代表データのループを開始する。代表データＣjの順番ｊを順次更新し、全ての代表データに対して以下のステップＳ１１４〜Ｓ１１５の処理を実行する。
【００４５】
ステップＳ１１４においては、ステップＳ１１２において解析した領域情報で第ｊ番目のクラスの情報を参照し、そのクラスの領域数が２以上であるか否かを判定する。この判定の結果、領域数が２以上である場合はフラグメンテーションが発生しているため、ステップＳ１１５に進む。一方、領域数が２未満である場合は、フラグメンテーションは発生していないため、ステップＳ１１６に進む。
【００４６】
ステップＳ１１５においては、フラグメンテーションを解消するためにそのクラスの代表データを補正する。図６は、本実施形態における代表データの補正方法を説明するための図である。図６において、点６０１は補正前の代表データの座標位置であり、領域６０３、６０５は点６０１の代表データのクラスに属する領域である。また、重心６０２、６０４はそれぞれ領域６０３、６０５の重心位置である。
【００４７】
本実施形態では、図５に示した領域情報を参照しながら、代表データの座標位置を同じクラスに属する複数の領域の中でサイズが最大である領域の重心位置に補正する。図６に示した例では、点６０１に示す代表データのクラスに属する領域は領域６０３、６０５の二つであり、領域６０３の領域サイズの方が領域６０５の領域サイズよりも大きいため、重心６０２の位置に代表データを移動する。
【００４８】
以上のように代表データの位置を補正することにより、次のクラスタリングの繰返しループでは、領域６０５内の入力データと、移動後の代表データとの座標空間上の距離が大きくなる。そのため、領域６０５の近傍に色情報が類似した代表データが存在する場合に、その代表データが最近傍代表データとなりやすくなる。一方、領域６０３内の入力データと移動後の代表データとの座標空間上の距離は小さくなるため、同じ代表データが最近傍代表データとなりやすい。したがって、領域６０５は近傍のクラスに吸収され、領域６０３のみが独立したクラスとなりやすくなり、フラグメンテーションが解消されることが期待される。
【００４９】
ステップＳ１１６においては、全ての代表データについてステップＳ１１４〜Ｓ１１５の処理を実行したかどうかを判定する。この判定の結果、全ての代表データについて処理を実行した場合は処理を終了する。一方、まだ処理していない代表データが存在する場合はステップＳ１１４に戻り、次の代表データに対して処理を開始する。
【００５０】
以上説明したように本実施形態によれば、フラグメンテーションが発生したクラスの代表データの座標位置を補正することにより、ループ計算によってフラグメンテーションを解消することができる。また、スーパーピクセルに対応するクラスインデックスは変化しないため、補正処理を施した後でも動画に適用した場合にフレーム間でのスーパーピクセルの対応を取りやすくすることができる。
【００５１】
（その他の実施形態）
前述した実施形態において、図１（ａ）のステップＳ１１１では、代表データの座標位置を、同じクラスに属する複数の領域の中でサイズが最大である領域の重心位置に補正した。一方、同じクラスに属する複数の入力データの中からランダムに選択した入力データの位置に補正してもよい。また、同じクラスに属する入力データの中で代表データからの座標空間上の距離が最大である入力データの位置に代表データを移動させてもよい。あるいは、代表データの周辺のクラスタリング結果をラスタスキャンし、最初に検出された同じクラスに属する入力データの位置に代表データを移動させてもよい。
【００５２】
さらに、注目する代表データの周辺の代表データも考慮して座標位置を補正してもよい。例えば、前述の実施形態に示した手法により同一クラスに対して複数の領域が抽出された場合に、周辺に色特徴の類似した代表データが存在しない領域の重心位置に代表データを移動させてもよい。
【００５３】
図７は、代表データの補正方法の他の例を説明するための図である。なお、図６と同じ部分に関しては同じ符号を割り当てている。点７０１〜７０４、点７０５〜７０８はそれぞれ重心６０２、６０４の近傍に位置する４個の代表データである。ここで、これらの近傍の代表データは、重心６０２、６０４の座標位置と図２に示した代表データの初期配置の座標位置とを基に決定する。なお、図７に示す例では、近傍の代表データの点７０１〜７０８と代表データの点６０１との位置は異なっているが、代表データの点７０１〜７０４、点７０５〜７０８のいずれか１つは代表データの点６０１と一致することもある。補正処理の詳細について以下に説明する。
【００５４】
まず、代表データの点６０１と重心６０２の近傍に位置する代表データの点７０１〜７０４との色空間上の距離の総和と、代表データの点６０１と重心６０４の近傍に位置する代表データの点７０５〜７０８との色空間上の距離の総和とをそれぞれ算出する。そして、色空間上の距離の総和が大きかった方の重心位置に代表データの点６０１を移動する。これにより、選択されなかった方の重心位置の領域（図７の例では領域６０５）の周辺には、他方の領域（図７の例では領域６０３）の周辺よりも色特量の類似した代表データが存在することとなる。そのため、その領域は周辺の代表データに割り当てられてフラグメンテーションが解消されやすい。なお、領域の数が３個以上の場合にも適用可能である。領域の数が３個以上の場合には、代表データと近傍の代表データとの色空間上の距離の総和が最大となった領域の重心位置に代表データを移動すればよい。
【００５５】
また、前回の繰り返しループ時の代表データの座標位置も考慮して代表データの座標位置を補正してもよい。例えば、前述した実施形態に示した手法により同一クラスに対して複数の領域が抽出された場合、前回の繰返しループ時に算出された代表データの座標位置から最も離れた位置にある領域の重心位置に代表データを移動する。補正処理の詳細について以下に説明する。
【００５６】
まず、抽出された複数の領域の重心位置と、前回の繰返しループ時の代表データの座標位置との距離を計算する。そして、距離が最大となる重心位置に代表データを移動する。前回の繰返しループ時から離れた位置に代表データを移動することにより、次回の繰返しループ時には異なるクラスタリング結果が得られる可能性が高くなる。そのため、再度同様のフラグメンテーションが発生する可能性が低減される。
【００５７】
前述した実施形態の図１のステップＳ１１１においては、クラスの分布として非特許文献１に記載の手法を用いて算出される領域情報を抽出し、領域数を基にフラグメンテーションの発生を検出したが、これに限る訳ではない。例えば、クラスの分布としてスーパーピクセルのサイズに対する周囲長を算出し、周囲長の大きさを基にフラグメンテーションの発生を検出してもよい。フラグメンテーションが発生している場合は、スーパーピクセルが複数の領域に分離しているため、単位領域サイズあたりの周囲長は長くなる場合が多い。そのため、予め設定した閾値よりも単位領域サイズあたりの周囲長が長い場合にフラグメンテーションが発生したと判定してもよい。
【００５８】
前述した実施形態では、代表データの座標位置のみを補正したが、これに限る訳ではない。さらに、代表データの色特徴を補正後の座標位置における入力データの色特徴に補正してもよい。あるいは、重心位置を代表データの座標位置として設定した領域内の入力データの色特徴の平均に補正してもよい。
【００５９】
前述した実施形態では、ステップＳ１１０で代表データを更新した後に、ステップＳ１１５で代表データを補正したが、これに限る訳ではない。代表データの更新と代表データの補正とを合わせてステップＳ１１５で実行してもよい。この場合、ステップＳ１１４の判定の結果、領域数が２以上でない場合には、代表データの更新も行わないようにする。
【００６０】
前述した実施形態においては、入力データの座標空間上の位置をｘi1，ｘi2の二次元で表したが、これに限る訳ではなく、任意の次元の座標であってもよい。また、入力データの色特徴をｘi3、ｘi4、ｘi5の三次元で表したが、色特徴に限る訳ではなく、テクスチャ特徴やテクスチャ特徴と色特徴とを複合した特徴量であってもよい。また、特徴量の次元は三次元に限定される訳でなく、任意の次元であってもよい。
【００６１】
また、前述の実施形態では、探索範囲２０２が幅及び高さがそれぞれ５個の代表データの例について説明したが、探索範囲の幅は５個の代表データに限定される訳でなく、任意の探索範囲であってもよい。
【００６２】
（その他の実施形態）
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサーがプログラムを読出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【符号の説明】
【００６３】
４０１  データ保存部
４０４  ＣＰＵ
【図１】
2016194862.tif 000004
【図２】
2016194862.tif 000005
【図３】
2016194862.tif 000006
【図４】
2016194862.tif 000007
【図５】
2016194862.tif 000008
【図６】
2016194862.tif 000009
【図７】
2016194862.tif 000010