(57)【要約】      （修正有）【課題】サンプルの本来の構造が、同じクラスタ又は異なるクラスタにならなければならないサンプル対を指定する制約条件から求められる弱監視付きカーネル平均値シフト手順を提供する。【解決手段】平均値シフト手順を使用してサンプルをクラスタリングするための方法であって、第１の次元においてサンプルからカーネル行列を求めるステップと、制約条件集合から制約条件行列及びスケーリング行列を求めるステップと、制約条件行列を使用してカーネル行列を第２の次元を有する特徴空間に投影するステップとから構成され、第２の次元を有する特徴空間に投影されたカーネル行列に従ってサンプルをクラスタリングする。【選択図】図１
2011014133.tif 000002
【特許請求の範囲】
【請求項１】
平均値シフト手順を使用してサンプルをクラスタリングするための方法であって、該方法のステップを実行するためのコンピュータシステムを備え、
第１の次元において前記サンプルからカーネル行列を求めるステップと、
制約条件集合から制約条件行列及びスケーリング行列を求めるステップと、
前記制約条件行列を使用して、前記カーネル行列を、第２の次元を有する特徴空間に投影するステップであって、前記第２の次元は、前記第１の次元よりも高い、投影するステップと、
前記カーネル行列に従って前記サンプルをクラスタリングするステップと
を含む方法。
【請求項２】
各クラスタの中心を求めるステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記制約条件集合は、同じクラスタにクラスタリングされるサンプル対を指定する、請求項１に記載の方法。
【請求項４】
前記制約条件集合は、異なるクラスタにクラスタリングされるサンプル対を指定する、請求項１に記載の方法。
【請求項５】
前記クラスタリングするステップは、ソフト類似制約条件を使用する、請求項１に記載の方法。
【請求項６】
前記投影するステップは、前記サンプルのマッピング関数φで明示的に定義される、請求項１に記載の方法。
【請求項７】
前記カーネル関数は、内積の対称行列であり、前記投影するステップは暗黙的である、請求項１に記載の方法。
【請求項８】
前記投影するステップは、前記特徴空間における前記制約条件ベクトルと直交している、請求項１に記載の方法。
【請求項９】
前記投影するステップは、前記特徴空間における前記制約条件ベクトルに沿って前記サンプルをスケーリングする、請求項１に記載の方法。
【請求項１０】
前記投影するステップは、前記制約条件集合を満たしつつ前記サンプル間の距離を保存する、請求項１に記載の方法。
【請求項１１】
前記サンプルは、任意のマニホールド上にある、請求項１に記載の方法。
【請求項１２】
前記カーネル行列は、該カーネル行列の低ランク分解によって近似される、請求項１に記載の方法。
【請求項１３】
前記投影するステップは、前記制約条件行列に従って前記カーネル行列を直接操作する、請求項１に記載の方法。
【請求項１４】
前記クラスタリングするステップは、任意の距離メトリックを使用する、請求項１に記載の方法。
【請求項１５】
前記クラスタリングするステップは、ソフト非類似制約条件を使用する、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、平均値シフトクラスタリングに関し、より詳細には、サンプルの弱監視付きカーネル平均値シフトクラスタリング（weakly supervised kernel mean shift clustering）に関する。
【背景技術】
【０００２】
平均値シフトは、サンプル集合から導出された密度関数の停留点を特定するための反復手順である。平均値シフト手順は、数十年間知られてきたが、近年、物体追跡、画像平滑化、及び前景セグメンテーション等のコンピュータビジョンアプリケーションにのみ適用されている。
【０００３】
平均値シフトクラスタリングは、カーネル密度推定によって近似された未知の分布を有するサンプルの監視無し密度ベースノンパラメトリッククラスタリング（unsupervised density based nonparametric clustering）技法である。クラスタ中心は、平均値シフト手順によって特定され、密度関数が同一の局所的最大に関連付けられた複数のサンプルが、それらサンプルをクラスタリングする。ラベル情報が利用可能である場合、クラスタリングの正確度を大幅に改善することができる。
【０００４】
弱監視付きクラスタリング手順は、対にして「リンクしなければならない（must-link：マストリンク）」制約条件を使用して、２つのサンプルが同じクラスタに属することを指定することができる。この形態の制約条件は、グラフ分割のコンテキストでは自然である。グラフ分割では、グラフのエッジが、グラフ切断及びランダムウォークセグメンテーション等において対関係を符号化する。
【０００５】
同様に、「リンクすることができない（cannot-link：キャンノットリンク）」制約条件は、２つのサンプルが異なるクラスタに属することを指定する。ハード制約条件は、その制約条件がクラスタリング中に満たされなければならないことを示すのに対して、ソフト制約条件は、クラスタリング中に必ずしも満たされるとは限らないが、ガイドとして使用される。
【０００６】
ｋ平均クラスタリング方法、スペクトルクラスタリング方法、及びグラフクラスタリング方法の弱監視付きの変形とは異なり、従来の平均値シフト方法は、ラベル情報を利用してクラスタリングをガイドすることはしない。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
平均値シフトクラスタリングは、クラスタの個数を事前に知る必要はなく、クラスタの形状を制約しない。その代わり、クラスタは、サンプルの基礎と成る確率分布に基づく。この確率分布は、距離メトリックを使用して前もって定義される。多くのアプリケーションでは、距離メトリックは、クラスタリングにおける曖昧さを解消することができない。
【課題を解決するための手段】
【０００８】
本発明の実施形態は、サンプルの本来の構造が、同じクラスタ又は異なるクラスタにならなければならないサンプル対を指定する制約条件から求められる弱監視付きカーネル平均値シフト手順を提供する。
【０００９】
サンプルは、クラスタリング中に制約条件を有効に強制できるカーネル関数によって、より高い次元に暗黙的に（implicitly）投影される。
【図面の簡単な説明】
【００１０】
【図１】本発明者の発明の実施形態による平均値シフトクラスタリングのシステム及び方法の概略図である。
【図２】本発明の実施形態による入力サンプルのグラフである。
【図３】本発明の実施形態による特徴空間に投影された入力サンプルのグラフである。
【図４】本発明の実施形態による類似制約条件（similarity constraint）ベクトルの零空間に投影された特徴空間のグラフである。
【図５】本発明の実施形態による入力サンプルのグラフである。
【図６】本発明の実施形態による特徴空間に投影された入力サンプルのグラフである。
【図７】本発明の実施形態による、ソフト類似制約条件サンプルが近傍ロケーションに投影される空間に投影された特徴空間のグラフである。
【図８】本発明の実施形態による入力サンプルのグラフである。
【図９】本発明の実施形態による特徴空間に投影された入力サンプルのグラフである。
【図１０】本発明の実施形態による、非類似制約条件サンプルが遠隔ロケーションに投影される空間に投影された特徴空間のグラフである。
【発明を実施するための形態】
【００１１】
概観
図１は、本発明の実施形態によるサンプルの平均値シフトクラスタリングのシステム及び方法１００を示す。サンプルは、例えば、画像から特徴を抽出することによって、従来の手段により取得された任意のデータとすることができる。
【００１２】
カーネル行列Ｋ  １１１は、第１の次元においてサンプル１０１から求められる。制約条件行列Ｃ及びスケーリング行列Ｓ  １２１は、制約条件集合１０２から求められる。カーネル行列は、特徴空間の第２の次元Ｋ’  １３１に投影される（１３０）。この第２の次元は、第１の次元よりも高い。次に、サンプルは、行列Ｋ’を使用してクラスタ１４１にクラスタリングされる（１４０）。クラスタ中心１４２も求めることができる。上記ステップは、当該技術分野で知られているようなメモリ及び入出力インターフェースを含むコンピュータシステムにおいて実行することができる。
【００１３】
制約条件付きクラスタリングの例
図２は、サンプル（＋）及び制約条件サンプル対（×）、（ｃ１，ｃ２）を示す。図３は、２次マッピング関数
φ（ｘ）＝［ｘ ｘ２］Ｔ
を使用したより高次元の特徴空間への投影を示す。ここで、Ｔは転置演算子である。矢印３０１は制約条件ベクトル（φ（ｃ２）−φ（ｃ１））Ｔであり、破線３０２は零空間を示す。行列Ｋの零空間は、Ｋｘ＝０であるすべてのベクトルｘの集合である。
【００１４】
図４は、制約条件ベクトルの零空間への特徴空間の投影を示す。制約条件付きサンプルは、容易に識別できる２つのクラスタに存在する。
【００１５】
動機
本発明は、類似のサンプル対が同じクラスタに存在するように制約条件集合を強制するアイデアによって動機付けられている。加えて、クラスタは、ローカルスケールで変更され、強制された構造は、入力サンプルに伝えられる。そうすることによって、少数の制約条件のみを使用してサンプルの対象となる構造に向けてクラスタリングをガイドすることが可能である。
【００１６】
本発明の制約条件付き平均値シフトクラスタリングは、密度推定がより高次元の特徴空間で実行されるとき、制約条件付き対が同じモードに関連付けられるように、サンプル空間の次元よりも高い次元にサンプルを投影することに基づいている。加えて、サンプル間の当初の距離は、制約条件を満たしつつ投影している間、保存される。
【００１７】
単一の制約条件を有し、クラスタが線形分離可能である図２〜図４に示す例で始めることにする。サンプル対（ｃ１，ｃ２）が制約条件付きとなる。サンプルが、制約条件ベクトル３０１と直交する（ｃ２−ｃ１）Ｔの零空間３０２に投影される場合、サンプルｃ１及びｃ２は、同じ点に投影され、それらサンプルが同じモードに関連付けられることが保証される。加えて、零空間投影は、投影方向と直交した方向に沿った分散を保存するので、最適な線形投影である。
【００１８】
しかしながら、この手法は、制約条件の個数が増加すると共に十分にスケーリングしない。ｄ次元入力空間上にｍ個の線形独立制約条件ベクトルが与えられると、制約条件行列の零空間は、ｄ−ｍ次元となる。これは、ｄ−１個よりも多くの制約条件が指定された場合に、すべてのサンプルが１つのクラスタに存在することを暗に意味する。
【００１９】
本発明の解決法では、サンプルが、マッピング関数φを使用して、より高次元の特徴空間に投影される。さらに、同じ技法は、サンプルを、（φ（ｃ２）−φ（ｃ１））Ｔの零空間に投影するのに使用することができる。
【００２０】
図２は、３つのクラスタに存在するように見えるサンプルの（第１の）１次元空間を示す。２つのサンプルｃ２及びｃ１が一緒にクラスタリングされるように強制する対の制約条件に関するラベル情報を組み込むことにする。
【００２１】
図３に示すように、サンプルは、２次マッピング関数φ（ｘ）＝［ｘ ｘ２］Ｔを介して（第２の）２次元特徴空間に明示的（explicitly）に投影される。この投影は、任意の例である。図４に示すように、入力空間を制約条件ベクトルの零空間に投影することによって、制約条件付きサンプルの点は、単一の点に落ち込み（collapse）、クラスタリングは、それらサンプルを一緒にグルーピングする。
【００２２】
図５〜図７に、ソフト類似制約条件によるクラスタリングを示す。図解を容易にするために、単一の制約条件のみが示されている。しかしながら、この方法は、複数の制約条件についても同一である。
【００２３】
図５では、サンプルは、当初の空間に存在する。図６では、サンプルは、２次マッピングにより特徴空間に投影される。ソフト類似制約条件によるクラスタリングでは、サンプルは、制約条件対が互いに近づくように、制約条件ベクトル方向３０３に沿ってスケーリングされる。
【００２４】
図７は、スケーリングを示す。このスケーリングによって、制約条件サンプルは、特徴空間において互いに接近し、同じクラスタにクラスタリングされる可能性がより高くなる。
【００２５】
図８〜図１０は、非類似制約条件によるクラスタリングを示す。図解を簡単にするために、単一の制約条件のみが示されている。しかしながら、この方法は、複数の制約条件についても同一である。
【００２６】
図８では、サンプルは、当初の空間に存在する。図９では、サンプルは、２次マッピングにより特徴空間に投影される。非類似制約条件によるクラスタリングでは、サンプル点は、制約条件対が互いに遠隔になるように、制約条件ベクトル方向３０５に沿ってスケーリングされる。このスケーリングは図１０に示される。図８の当初の空間には２つのクラスタが存在するように見えるが、図１０には、３つのクラスタを明確に視認することができる。図１０では、２つの制約条件点が、異なるクラスタに入れられている。
【００２７】
しかしながら、より高次元の空間での明示的な投影及び操作は、実際的ではない。したがって、より高次元の特徴空間上で暗黙的に動作するカーネルベース平均値シフト手順を提供し、従来のユークリッド平均値シフトを内積空間に拡張することにする。次いで、カーネル誘導空間（kernel induced space）上での制約条件付き平均値シフトは、定義された制約条件に関するカーネル行列の変更に還元される。
【００２８】
平均値シフトクラスタリング
本発明の平均値シフト手順は、２００３年７月８日にComaniciu他に発行された米国特許第６，５９０，９９９号明細書「Real-time tracking of non-rigid objects using mean shift」を拡張したものである。ｄ次元空間におけるｎ個のサンプルｘｉ及び関連付けられたスケール（帯域幅）ｈｉ＝ｈ（ｘｉ）、ｉ＝１，…，ｎが与えられると、プロファイルｋ（ｘ）のサンプル密度推定器は、
【００２９】
【数１】
2011014133.tif 000003
【００３０】
となる。
【００３１】
本発明では、多変量プロファイル（multivariate profile）
【００３２】
【数２】
2011014133.tif 000004
【００３３】
を使用することにする。
【００３４】
式（１）の勾配を取ることによって、密度関数の停留点は、
【００３５】
【数３】
2011014133.tif 000005
【００３６】
を満たす。ここで、ｇ（ｘ）＝−ｋ’（ｘ）である。解は、不動点平均値シフト手順
【００３７】
【数４】
2011014133.tif 000006
【００３８】
を介して反復して求めることができる。
【００３９】
分布のローカルモードへの収束は、平均値シフト反復がサンプルから開始するときに保証される。
【００４０】
カーネル平均値シフト
カーネル平均値シフト手順は、本発明者の制約条件付き平均値シフト手順の基礎を成す。従来の平均値シフト手順が、ユークリッド空間から内積空間に拡張される。これによって、任意のマニホールド上にあるサンプルのクラスタリング等、より大きな部類の問題にこの手順を適用することが可能になる。
【００４１】
入力サンプル集合は、ｘｉ∈Ｘ、ｉ＝１，…，ｎであり、必ずしもユークリッドではない。Ｋ：Ｘ×Ｘを、すべてのｘ、ｘ’について、
Ｋ（ｘ，ｘ’）＝φ（ｘ）Ｔφ（ｘ’）      （５）
を満たす正定カーネル関数とする。ここで、マッピング関数φは、サンプルをｄφ次元特徴空間
Ｈ，φ（ｘ）＝［φ１（ｘ）φ２（ｘ），…，φｄφ（ｘ）］Ｔ
に投影する。
【００４２】
カーネルによって、サンプルの非線形構造を観察でき且つ制約条件を有効に適用できるより高次元の特徴空間にサンプルを暗黙的に投影することが可能になる。
【００４３】
特徴空間Ｈ上の平均値シフト手順を、マッピング関数φの明示的な表現によって定義することにする。ｙ∈Ｈにおけるサンプル密度評価器は、
【００４４】
【数５】
2011014133.tif 000007
【００４５】
である。
【００４６】
φに関して式（６）の勾配を取ると、密度関数の停留点は、
【００４７】
【数６】
2011014133.tif 000008
【００４８】
を満たす。
【００４９】
式（４）に関して、解は、
【００５０】
【数７】
2011014133.tif 000009
【００５１】
として反復して見つけることができる。
【００５２】
次に、手順の暗黙的な形態を導出することにする。特徴点のｄφ×ｎ行列は、
Φ＝［φ（ｘ１）φ（ｘ２）…φ（ｘｎ）］      （９）
であり、ｎ×ｎカーネル行列は、内積の対称行列であるＫ＝ΦＴΦ、すなわちグラム行列（Gram matrix）である。式（８）の平均値シフト手順の各反復において、推定値
【００５３】
【数８】
2011014133.tif 000010
【００５４】
は、Φの列空間にある。Φの列が及ぶ部分空間上のどの点も、
ｙ＝Φαｙ            （１０）
として記述することができる。ここで、αｙは、ｎ次元重みベクトルである。ｙとｙ’との間の距離は、
【００５５】
【数９】
2011014133.tif 000011
【００５６】
である。
【００５７】
距離は、サンプルの内積によって表すことができ、この方法は、重みベクトルαｙを反復して更新する。ｅｉを、
【００５８】
【数１０】
2011014133.tif 000012
【００５９】
のｉ番目の標準基底を示すものとする。カーネル平均値シフト手順は、このとき、
【００６０】
【数１１】
2011014133.tif 000013
【００６１】
となる。
【００６２】
クラスタリングアルゴリズムは、カーネル空間上のサンプルから始める。したがって、初期重みベクトルは、αｙｉ＝ｅｉである。同じモードに収束するサンプルがクラスタリングされる。
【００６３】
カーネル行列Ｋのランクは、ｎよりも小さく、Φの列は、過完備基底を形成する。したがって、モードは、特徴空間上の距離が０であるときに２つのモードが同じであるとみなされる等価関係内で識別することができる。加えて、マッピング関数φは必ずしも反転可能であるとは限らないので、モードを入力空間Ｘ上で表すことができない可能性がある。
【００６４】
制約条件付き平均シフトクラスタリング手順
ｍ個の制約条件付きサンプルの集合は｛（ｃｊ，１，ｃｊ，２）｝である。最初に、サンプルが、マッピング関数φを介して特徴空間に投影され、制約条件は、特徴空間を制約条件ベクトルの零空間に投影することによって満たされる。Ａを、ｍ×ｄφ次元制約条件行列
【００６５】
【数１２】
2011014133.tif 000014
【００６６】
とする。
【００６７】
サンプル及び制約条件集合が与えられると、制約条件付き平均値シフト手順は、サンプルを、制約条件行列の零空間に投影する。
【００６８】
【数１３】
2011014133.tif 000015
【００６９】
ここで、Ｐは、投影行列
Ｐ＝Ｉｄφ−ＡＴ（ＡＡＴ）＋Ａ          （１５）
であり、特徴空間上で平均値シフトを暗黙的に実行する。制約条件付きサンプルは、同じ特徴点に投影されるので、サンプルは、同じモードに収束する。平均値シフト手順を特徴空間上で書き換える代わりに、投影に関してカーネル行列Ｋを変更し、導出されたカーネル平均値シフト手順を変更されたカーネル行列に対して適用することで十分である。等価性は、距離計算とは別に、手順が同一であり、距離が内積に関する特徴点のみを含んでいることから得られる。投影されたカーネル行列は、
Ｋ（ｘ，ｘ’）−Ｋ（φ（ｘ），Ａ）ＴＳ＋Ｋ（φ（ｘ’），Ａ）      （１６）
によって与えられる。ここで、
Ｓｉ，ｊ＝Ｋ（ｃｉ，１，ｃｊ，１）−Ｋ（ｃｉ，１，ｃｊ，２）
−Ｋ（ｃｉ，２，ｃｊ，１）＋Ｋ（ｃｉ，２，ｃｊ，２）      （１７）
は、スケーリング行列である。
【００７０】
サンプルの代わりに、カーネル行列Ｋ  １１０及び制約条件１２１のみを本発明の弱監視付きカーネル平均値シフト手順に供給することで十分である。
【００７１】
メモリ所要量を削減するために、カーネル行列Ｋは、インクリメンタル特異値分解（ＳＶＤ）を使用してカーネル行列の低ランク分解（low rank decomposition）により近似することができる。
【００７２】
「リンクすることができない」制約条件は、同じ枠組みで適用することができる。サンプルは、制約条件対が互いに遠隔になるように、制約条件ベクトル方向に沿ってスケーリングされる。まず、サンプルは、式（１４）に従って制約条件ベクトルの零空間に投影される。次に、制約条件方向のスカラー倍したものがサンプルに加えられる。
【００７３】
【数１４】
2011014133.tif 000016
【００７４】
を、正規化された制約条件ベクトルとする。各制約条件方向に沿ったスケーリングは、
【００７５】
【数１５】
2011014133.tif 000017
【００７６】
によって定義される。ここで、λ１，…，λｍは、どれだけのスケーリングが各方向に沿って行われるのかを制御する。スケーリングされた投影は、
【００７７】
【数１６】
2011014133.tif 000018
【００７８】
である。
【００７９】
式（１９）においてλｉを１よりも大きく設定すると、サンプルは、制約条件サンプルが互いに遠隔になるようにスケーリングされる。λｉをより大きな値に設定し、カーネル平均値シフト手順を使用することによって、制約条件サンプルは、図８〜図１０に示すように、異なるクラスタにグループピングされる。
【００８０】
ソフト制約条件も、同じ枠組みで適用することができる。サンプルは、制約条件対が互いにより接近するように、制約条件ベクトル方向に沿ってスケーリングされる。これは、式（１９）においてλｉを１未満に設定することによって達成される。制約条件サンプルは、必ずしも同じ点ではないが、近傍の点に投影される。したがって、制約条件付きサンプルは、図５〜図７に示すように、必ずしも同じクラスタにグループピングされないが、ガイドとして使用される。λｉを０に等しく設定することは、上述したハード制約条件アルゴリズムと等価である。
【００８１】
この方法は、平均値シフトクラスタリングをあらゆる内積空間及びメトリック公理（metric axiom）を満たすあらゆる任意の距離関数に拡張する。
【００８２】
本発明を、好ましい実施形態の例として説明してきたが、本発明の精神及び範囲内で他のさまざまな適合及び変更を行えることが理解されるべきである。したがって、本発明の真の精神及び範囲内に入るすべての変形及び変更を包含することが、添付の特許請求の範囲の目的である。
【図１】
2011014133.tif 000019
【図２】
2011014133.tif 000020
【図３】
2011014133.tif 000021
【図４】
2011014133.tif 000022
【図５】
2011014133.tif 000023
【図６】
2011014133.tif 000024
【図７】
2011014133.tif 000025
【図８】
2011014133.tif 000026
【図９】
2011014133.tif 000027
【図１０】
2011014133.tif 000028
【外国語明細書】
2011014133.tif 000029
2011014133.tif 000030
2011014133.tif 000031
2011014133.tif 000032
2011014133.tif 000033
2011014133.tif 000034
2011014133.tif 000035
2011014133.tif 000036
2011014133.tif 000037
2011014133.tif 000038
2011014133.tif 000039
2011014133.tif 000040
2011014133.tif 000041
2011014133.tif 000042
2011014133.tif 000043
2011014133.tif 000044
2011014133.tif 000045
2011014133.tif 000046
2011014133.tif 000047
2011014133.tif 000048
2011014133.tif 000049
2011014133.tif 000050
2011014133.tif 000051
2011014133.tif 000052
2011014133.tif 000053
2011014133.tif 000054
2011014133.tif 000055
2011014133.tif 000056