(57)【要約】【課題】デジタル画像を処理するための方法および装置を提供すること。【解決手段】一実施形態による方法は、複数のデジタル画像に属する複数の要素を表す要素データにアクセスするステップと、前記複数の要素中の前記要素間の類似性分析を実施して、前記要素に関係する相関データ結果を取得するステップと、前記複数の要素のクラスタリングを実施するステップとを含み、前記クラスタリングを実施するステップは、前記複数の要素中の要素に関係する少なくとも１つのハード制約条件を前記相関データ結果に組み込んで、制約条件付き相関データ結果を取得するステップと、前記制約条件付き相関データ結果から固有ベクトル結果を取得するためのスペクトル分析を実施するステップと、前記少なくとも１つのハード制約条件を強制する基準を用いた制約条件付きクラスタリングを使用し、前記固有ベクトル結果の離散化を実施してクラスタを取得するステップとを含む。【選択図】図１
2007272890.tif 000002
【特許請求の範囲】
【請求項１】
デジタル画像処理方法であって、
複数のデジタル画像に属する複数の要素を表す要素データにアクセスするステップと、
前記複数の要素中の前記要素間の類似性分析を実施して、前記要素に関係する相関データ結果を取得するステップと、
前記複数の要素のクラスタリングを実施するステップとを含み、クラスタリングを実施する前記ステップは、
前記複数の要素中の要素に関係する少なくとも１つのハード制約条件を前記相関データ結果に組み込んで、制約条件付き相関データ結果を取得するステップと、
前記制約条件付き相関データ結果から固有ベクトル結果を取得するためのスペクトル分析を実施するステップと、
前記少なくとも１つのハード制約条件を強制する基準を用いた制約条件付きクラスタリングを使用し、前記固有ベクトル結果の離散化を実施してクラスタを取得するステップとを含む、
デジタル画像処理方法。
【請求項２】
離散化を実施する前記サブ・ステップは、制約条件付きＫ平均クラスタリングを使用する、請求項１に記載のデジタル画像処理方法。
【請求項３】
前記要素は、前記複数のデジタル画像内で発見される人々である、請求項１に記載のデジタル画像処理方法。
【請求項４】
前記少なくとも１つのハード制約条件は、前記複数のデジタル画像中の同じ画像内で発見される２人の人が異なる同一性を有するハード・ネガティブ制約条件を含む、請求項３に記載のデジタル画像処理方法。
【請求項５】
前記少なくとも１つのハード制約条件は、前記複数のデジタル画像中の異なる画像内で発見される２人の人が同じ人物となる所定の知識に基づくハード・ポジティブ制約条件を含む、請求項３に記載のデジタル画像処理方法。
【請求項６】
前記要素間の類似性分析を実施する前記ステップは、
前記人々の顔間の顔類似性分析を実施して、前記人々の顔間の顔類似性測定値を取得するステップと、
前記人々の服装間の服装類似性分析を実施して、前記人々の服装間の服装類似性測定値を取得するステップと、
前記顔類似性測定値と前記服装類似性測定値との利用可能性に基づいて、同じ人物を表す前記複数のデジタル画像中の複数対の人々に関する類似性測定値を推定する複数の公式を提供するステップとを含む、
請求項３に記載のデジタル画像処理方法。
【請求項７】
前記要素間の類似性分析を実施する前記ステップは、
前記複数のデジタル画像中の画像が撮影された時間に基づいて、前記相関データ結果に対する２人の人の間の類似性測定値を取得する少なくとも１つの公式を、前記複数の公式から選択し、
前記複数のデジタル画像中の画像が撮影された場所に基づいて、前記相関データ結果に対する２人の人の間の類似性測定値を取得する少なくとも１つの公式を、前記複数の公式から選択し、
単一の画像内で２人以上の人物が同じ服装をしているかどうかに基づいて、前記相関データ結果に対する２人の人の間の類似性測定値を取得する少なくとも１つの公式を、前記複数の公式から選択し、
前記顔類似性測定値に由来する顔類似性測定値だけが利用可能であり、前記服装類似性測定値に由来する服装類似性測定値は利用可能でない場合に、前記相関データ結果に対する２人の人の間の類似性測定値を取得する少なくとも１つの公式を、前記複数の公式から選択し、
前記服装類似性測定値に由来する服装類似性測定値だけが利用可能であり、前記顔類似性測定値に由来する顔類似性測定値は利用可能でない場合に、前記相関データ結果に対する２人の人の間の類似性測定値を取得する少なくとも１つの公式を、前記複数の公式から選択し、
前記顔類似性測定値に由来する顔類似性測定値と、前記服装類似性測定値に由来する服装類似性測定値とが利用可能である場合に、前記相関データ結果に対する２人の人の間の類似性測定値を取得する少なくとも１つの公式を、前記複数の公式から選択する、
請求項６に記載のデジタル画像処理方法。
【請求項８】
服装をセグメント化し、隣接する服装間の差を最大化することにより、前記複数のデジタル画像内の服装領域を判定するステップと、
類似性分析を実施する前記ステップの前に、前記服装領域からクラッタを除去するステップと
をさらに含む、請求項６に記載のデジタル画像処理方法。
【請求項９】
前記複数のデジタル画像内の服装は、衣服、靴、腕時計、および眼鏡の内の少なくとも１つを含む、請求項８に記載のデジタル画像処理方法。
【請求項１０】
クラッタを除去する前記ステップの後でかつ類似性分析を実施する前記ステップの前に、服装の特徴抽出を実施するステップをさらに含み、服装の特徴抽出を実施する前記ステップは、
前記服装領域から代表的な画像パッチを抽出するステップと、
前記要素間の類似性分析を実施する前記ステップで使用される前記服装領域の数値表現を取得するために、前記服装領域内に現れる前記代表的な画像パッチの周波数から特徴ベクトルを生成するステップとを含む、
請求項８に記載のデジタル画像処理方法。
【請求項１１】
前記クラスタの数は、前記複数の要素のクラスタリングを実施する前記ステップの前に予め決定される、請求項１に記載のデジタル画像処理方法。
【請求項１２】
前記固有ベクトル結果は、数値要素セットであり、
前記複数の要素中の要素と前記数値要素の間に１対１の対応関係が存在し、
複数の要素中の各要素は、前記クラスタ中、離散化を実施する前記サブ・ステップで前記数値要素の対応する数値要素がクラスタリングされたクラスタに割り当てられる、
請求項１に記載のデジタル画像処理方法。
【請求項１３】
類似性分析を実施する前記ステップは、
前記要素間の類似性スコアを取得するステップと、
前記類似性スコアを使用して親和性行列Ａを取得するステップとを含み、
組み込みを行う前記サブ・ステップは、
前記親和性行列Ａに前記少なくとも１つのハード制約条件を組み込むステップと、
前記親和性行列Ａを使用して、前記制約条件付き相関データ結果を相関データ行列Ｌの形で取得するステップとを含み、
スペクトル分析を実施する前記サブ・ステップは、
前記相関データ行列Ｌにおける所定の数の最大固有ベクトルを選択するステップと、
選択された固有ベクトルを列にスタックして行列Ｘを取得するステップと、
前記行列Ｘの各行を単位長さに正規化して前記固有ベクトル結果を行列Ｙの形で取得するステップとを含み、
離散化を実施する前記サブ・ステップは、
前記少なくとも１つのハード制約条件を強制する基準を使用した制約条件付きＫ平均クラスタリングを使用し、前記行列Ｙの各行をクラスタリングして、前記クラスタを取得するステップと、
前記複数の要素中の要素を、前記要素に関連する前記行列Ｙの各行が割り当てられているクラスタに割り当てるステップとを含む、
請求項１に記載のデジタル画像処理方法。
【請求項１４】
前記要素は、前記複数のデジタル画像内で発見される人々であり、
前記少なくとも１つのハード制約条件は、前記複数のデジタル画像中の同じ画像内で発見される２人の人が異なる同一性を有するネガティブ制約条件を含み、
前記要素間の類似性分析を実施する前記ステップは、
前記人々の顔間の類似性分析を実施して、前記人々の顔間の顔類似性スコアを取得するステップと、
前記人々の服装間の類似性分析を実施して、前記人々の服装間の服装類似性スコアを取得するステップと、
複数対の人々に関する前記顔類似性スコアと前記服装類似性スコアとを組み合わせて、前記類似性スコアを取得するステップと、
前記複数対の人々に関する前記類似性スコアを使用して前記親和性行列Ａを取得するステップとを含む、
請求項１３に記載のデジタル画像処理方法。
【請求項１５】
デジタル画像処理方法であって、
複数のデジタル画像に属する複数の要素を表す要素データにアクセスするステップと、
前記複数の要素中の前記要素間の類似性分析を実施して、前記要素に関係する相関データ結果を取得するステップと、
前記複数の要素のクラスタリングを実施するステップとを含み、前記クラスタリングを実施するステップは、
前記要素間の非類似性に関係する少なくとも１つのハード・ネガティブ制約条件を前記相関データ結果に組み込んで、制約条件付き相関データ結果を取得するステップと、
前記制約条件付き相関データ結果から固有ベクトル結果を取得するためのスペクトル分析を実施するステップと、
前記固有ベクトル結果をクラスタリングし、前記固有ベクトル結果の離散化を実施してクラスタを取得するステップとを含む、
デジタル画像処理方法。
【請求項１６】
離散化を実施する前記サブ・ステップは、前記固有ベクトル結果をクラスタリングして前記クラスタを取得するために、Ｋ平均クラスタリングを使用する、請求項１５に記載のデジタル画像処理方法。
【請求項１７】
前記要素は、前記複数のデジタル画像内で発見される人々であり、
前記少なくとも１つのハード制約条件は、前記複数のデジタル画像中の同じ画像内で発見される２人の人が異なる同一性を有するネガティブ制約条件を含む、
請求項１６に記載のデジタル画像処理方法。
【請求項１８】
前記要素間の類似性分析を実施する前記ステップは、
前記人々の顔間の顔類似性分析を実施して、前記人々の顔間の顔類似性測定値を取得するステップと、
前記人々の服装間の服装類似性分析を実施して、前記人々の服装間の服装類似性測定値を取得するステップと、
前記顔類似性測定値と前記服装類似性測定値との利用可能性に基づいて、同じ人物を表す前記複数のデジタル画像中の複数対の人々に関する類似性測定値を推定する複数の公式を提供するステップと
を含む、請求項１７に記載のデジタル画像処理方法。
【請求項１９】
服装をセグメント化し、隣接する服装間の差を最大化することにより、前記複数のデジタル画像内の服装領域を判定するステップと、
類似性分析を実施する前記ステップの前に、前記服装領域からクラッタを除去するステップと、
類似性分析を実施する前記ステップの前に、服装の特徴抽出を実施するステップとをさらに含み、服装の特徴抽出を実施する前記ステップは、
前記服装領域から代表的な画像パッチを抽出するステップと、
前記要素間の類似性分析を実施する前記ステップで使用される前記服装領域の数値表現を取得するために、前記服装領域内に現れる前記代表的な画像パッチの周波数から特徴ベクトルを生成するステップとを含む、
請求項１７に記載のデジタル画像処理方法。
【請求項２０】
類似性分析を実施する前記ステップは、
前記要素間の類似性スコアを取得するステップと、
前記類似性スコアを使用して親和性行列Ａを取得するステップとを含み、
組み込みを行う前記サブ・ステップは、
前記親和性行列Ａに前記少なくとも１つのハード・ネガティブ制約条件を組み込むステップと、
前記少なくとも１つのハード・ネガティブ制約条件を使用して相反性行列Ｒを生成するステップと、
前記親和性行列Ａと前記相反性行列Ｒとを使用して、前記制約条件付き相関データ結果を相関データ行列Ｌの形で取得するステップとを含み、
スペクトル分析を実施する前記サブ・ステップは、
前記相関データ行列Ｌにおける所定の数の最大固有ベクトルを選択するステップと、
選択された固有ベクトルを列にスタックして行列Ｘを取得するステップと、
前記行列Ｘの各行を単位長さに正規化して前記固有ベクトル結果を行列Ｙの形で取得するステップとを含み、
離散化を実施する前記サブ・ステップは、
Ｋ平均クラスタリングを使用し、前記行列Ｙの各行をクラスタリングして、前記クラスタを取得するステップと、
前記複数の要素中の要素を、前記要素に関連する前記行列Ｙの各行が割り当てられているクラスタに割り当てるステップとを含む、
請求項１５に記載のデジタル画像処理方法。
【請求項２１】
デジタル画像処理装置であって、
複数のデジタル画像に属する複数の要素を表す要素データを提供する画像データ・ユニットと、
前記複数の要素中の前記要素間の類似性分析を実施して、前記要素に関係する相関データ結果を取得する類似性分析ユニットと、
前記複数の要素のクラスタリングを実施するクラスタリング・ユニットとを備え、前記クラスタリングを実施するクラスタリング・ユニットは、
前記複数の要素中の要素に関係する少なくとも１つのハード制約条件を前記相関データ結果に組み込んで、制約条件付き相関データ結果を取得し、
前記制約条件付き相関データ結果から固有ベクトル結果を取得するためのスペクトル分析を実施し、
前記少なくとも１つのハード制約条件を強制する基準を用いた制約条件付きクラスタリングを使用し、前記固有ベクトル結果の離散化を実施してクラスタを取得することによって、クラスタリングを実施する、
デジタル画像処理装置。
【請求項２２】
前記クラスタリング・ユニットは、制約条件付きＫ平均クラスタリングを使用して離散化を実施する、請求項２１に記載の装置。
【請求項２３】
前記要素は、前記複数のデジタル画像内で発見される人々である、請求項２１に記載の装置。
【請求項２４】
前記少なくとも１つのハード制約条件は、前記複数のデジタル画像中の同じ画像内で発見される２人の人が異なる同一性を有するハード・ネガティブ制約条件を含む、請求項２３に記載の装置。
【請求項２５】
前記少なくとも１つのハード制約条件は、前記複数のデジタル画像中の異なる画像内で発見される２人の人が同じ人物となる所定の知識に基づくハード・ポジティブ制約条件を含む、請求項２３に記載の装置。
【請求項２６】
前記類似性分析ユニットは、
前記人々の顔間の顔類似性分析を実施して、前記人々の顔間の顔類似性測定値を取得する顔ユニットと、
前記人々の服装間の服装類似性分析を実施して、前記人々の服装間の服装類似性測定値を取得する服装ユニットと、
前記顔類似性測定値と前記服装類似性測定値との利用可能性に基づいて、同じ人物を表す前記複数のデジタル画像中の複数対の人々に関する類似性測定値を推定する複数の公式を提供する組合せユニットとを備える、
請求項２３に記載の装置。
【請求項２７】
前記組合せユニットは、
前記複数のデジタル画像中の画像が撮影された時間に基づいて、前記相関データ結果に対する２人の人の間の類似性測定値を取得する少なくとも１つの公式を、前記複数の公式から選択し、
前記複数のデジタル画像中の画像が撮影された場所に基づいて、前記相関データ結果に対する２人の人の間の類似性測定値を取得する少なくとも１つの公式を、前記複数の公式から選択し、
単一の画像内で２人以上の人物が同じ服装をしているかどうかに基づいて、前記相関データ結果に対する２人の人の間の類似性測定値を取得する少なくとも１つの公式を、前記複数の公式から選択し、
前記顔類似性測定値に由来する顔類似性測定値だけが利用可能であり、前記服装類似性測定値に由来する服装類似性測定値は利用可能でない場合に、前記相関データ結果に対する２人の人の間の類似性測定値を取得する少なくとも１つの公式を、前記複数の公式から選択し、
前記服装類似性測定値に由来する服装類似性測定値だけが利用可能であり、前記顔類似性測定値に由来する顔類似性測定値は利用可能でない場合に、前記相関データ結果に対する２人の人の間の類似性測定値を取得する少なくとも１つの公式を、前記複数の公式から選択し、
前記顔類似性測定値に由来する顔類似性測定値と、前記服装類似性測定値に由来する服装類似性測定値とが利用可能である場合に、前記相関データ結果に対する２人の人の間の類似性測定値を取得する少なくとも１つの公式を、前記複数の公式から選択する、
請求項２６に記載の装置。
【請求項２８】
隣接する服装間の差を最大化することにより、前記複数のデジタル画像内の服装領域を判定し、前記類似性分析ユニットが前記類似性分析を実施する前に、前記服装領域からクラッタを除去する服装セグメント化ユニット
をさらに備える、請求項２６に記載の装置。
【請求項２９】
前記複数のデジタル画像内の服装は、衣服、靴、腕時計、および眼鏡の内の少なくとも１つを含む、請求項２８に記載の装置。
【請求項３０】
前記服装領域上の服装の特徴抽出を実施する服装表現ユニットをさらに備え、前記服装表現ユニットは、
前記服装領域から代表的な画像パッチを抽出し、
前記服装領域の数値表現を取得するために、前記服装領域内に現れる前記代表的な画像パッチの周波数から特徴ベクトルを生成し、
前記服装領域の前記数値表現を前記服装ユニットに送ることによって、前記服装領域上の服装の特徴抽出を実施する、
請求項２８に記載の装置。
【請求項３１】
前記クラスタの数は、前記クラスタリング・ユニットが前記複数の要素のクラスタリングを実施する前に予め決定される、請求項２１に記載の装置。
【請求項３２】
前記固有ベクトル結果は、数値要素セットであり、
前記複数の要素中の要素と前記数値要素との間に１対１の対応関係が存在し、
前記クラスタリング・ユニットは、前記複数の要素中の各要素を、前記クラスタ中、前記数値要素の対応する数値要素がクラスタリングされたクラスタに割り当てる、
請求項２１に記載の装置。
【請求項３３】
前記類似性分析ユニットは、
前記要素間の類似性スコアを取得し、
前記類似性スコアを使用して親和性行列Ａを取得することによって、前記要素間のスペクトル分析を実施し、
前記クラスタリング・ユニットは、
前記親和性行列Ａに前記少なくとも１つのハード制約条件を組み込み、
前記親和性行列Ａを使用して、前記制約条件付き相関データ結果を相関データ行列Ｌの形で取得し、
前記相関データ行列Ｌにおける所定の数の最大固有ベクトルを選択し、
選択された固有ベクトルを列にスタックして行列Ｘを取得し、
前記行列Ｘの各行を単位長さに正規化して前記固有ベクトル結果を行列Ｙの形で取得し、
前記少なくとも１つのハード制約条件を強制する基準を使用した制約条件付きＫ平均クラスタリングを使用し、前記行列Ｙの各行をクラスタリングして、前記クラスタを取得し、
前記複数の要素中の要素を、前記要素に関連する前記行列Ｙの各行が割り当てられているクラスタに割り当てることによって、前記複数の要素のクラスタリングを実施する、
請求項２１に記載の装置。
【請求項３４】
前記要素は、前記複数のデジタル画像内で発見される人々であり、
前記少なくとも１つのハード制約条件は、前記複数のデジタル画像中の同じ画像内で発見される２人の人が異なる同一性を有するハード・ネガティブ制約条件を含み、
前記類似性分析ユニットは、
前記人々の顔間の類似性分析を実施して、前記人々の顔間の顔類似性スコアを取得し、
前記人々の服装間の類似性分析を実施して、前記人々の服装間の服装類似性スコアを取得し、
複数対の人々に関する前記顔類似性スコアと前記服装類似性スコアとを組み合わせて、前記類似性スコアを取得し、
前記複数対の人々に関する前記類似性スコアを使用して前記親和性行列Ａを取得することによって、前記要素間の前記類似性分析を実施する、
請求項３３に記載の装置。
【請求項３５】
デジタル画像処理装置であって、
複数のデジタル画像に属する複数の要素を表す要素データを提供する画像データ・ユニットと、
前記複数の要素中の前記要素間の類似性分析を実施して、前記要素に関係する相関データ結果を取得する類似性分析ユニットと、
前記複数の要素のクラスタリングを実施するクラスタリング・ユニットとを備え、前記クラスタリング・ユニットは、
前記要素間の非類似性に関係する少なくとも１つのハード・ネガティブ制約条件を前記相関データ結果に組み込んで、制約条件付き相関データ結果を取得し、
前記制約条件付き相関データ結果から固有ベクトル結果を取得するためのスペクトル分析を実施し、
前記固有ベクトル結果をクラスタリングし、前記固有ベクトル結果の離散化を実施してクラスタを取得することによって、クラスタリングを実施する、
デジタル画像処理装置。
【請求項３６】
前記クラスタリング・ユニットは、前記固有ベクトル結果をクラスタリングして前記クラスタを取得するために、Ｋ平均クラスタリングを使用する、請求項３５に記載の装置。
【請求項３７】
前記要素は、前記複数のデジタル画像内で発見される人々であり、
前記少なくとも１つのハード・ネガティブ制約条件は、前記複数のデジタル画像中の同じ画像内で発見される２人の人が異なる同一性を有するネガティブ制約条件を含む、
請求項３６に記載の装置。
【請求項３８】
前記類似性分析ユニットは、
前記人々の顔間の顔類似性分析を実施して、前記人々の顔間の顔類似性測定値を取得する顔ユニットと、
前記人々の服装間の服装類似性分析を実施して、前記人々の服装間の服装類似性測定値を取得する服装ユニットと、
前記顔類似性測定値と前記服装類似性測定値との利用可能性に基づいて、同じ人物を表す前記複数のデジタル画像中の複数対の人々に関する類似性測定値を推定する複数の公式を提供する組合せユニットとを備える、
請求項３７に記載の装置。
【請求項３９】
隣接する服装間の差を最大化することにより、前記複数のデジタル画像内の服装領域を判定し、前記服装領域からクラッタを除去する服装セグメント化ユニットと、
前記服装領域上の服装の特徴抽出を実施する服装表現ユニットとをさらに備え、前記服装表現ユニットは、
前記服装領域から代表的な画像パッチを抽出し、
前記服装領域の数値表現を取得するために、前記服装領域内に現れる前記代表的な画像パッチの周波数から特徴ベクトルを生成し、
前記服装領域の前記数値表現を前記類似性分析ユニットに送ることによって、前記服装領域上の服装の特徴抽出を実施する、
請求項３７に記載の装置。
【請求項４０】
前記類似性分析ユニットは、
前記要素間の類似性スコアを取得し、
前記類似性スコアを使用して親和性行列Ａを取得することによって、前記要素間の類似性分析を実施し、
前記クラスタリング・ユニットは、
前記親和性行列Ａに前記少なくとも１つのハード・ネガティブ制約条件を組み込み、
前記少なくとも１つのハード・ネガティブ制約条件を使用して相反性行列Ｒを生成し、
前記親和性行列Ａと前記相反性行列Ｒとを使用して、前記制約条件付き相関データ結果を相関データ行列Ｌの形で取得し、
前記相関データ行列Ｌにおける所定の数の最大固有ベクトルを選択し、
選択された固有ベクトルを列にスタックして行列Ｘを取得し、
前記行列Ｘの各行を単位長さに正規化して前記固有ベクトル結果を行列Ｙの形で取得し、
Ｋ平均クラスタリングを使用し、前記行列Ｙの各行をクラスタリングして、前記クラスタを取得し、
前記複数の要素中の要素を、前記要素に関連する前記行列Ｙの各行が割り当てられているクラスタに割り当てることによって、前記複数の要素のクラスタリングを実施する、
請求項３５に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この本出願の基礎となるＵＳ出願は、当該ＵＳ出願と同時に出願された「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｃｏｎｔｅｘｔ−Ａｉｄｅｄ  Ｈｕｍａｎ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ」および「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ａｄａｐｔｉｖｅ  Ｃｏｎｔｅｘｔ−Ａｉｄｅｄ  Ｈｕｍａｎ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ」と題する同時係属本出願の関連出願であり、各本出願は参照によりその内容全体が本明細書に組み込まれる。
【０００２】
本発明は、グループ化技法に関し、より詳細には、人々などのオブジェクトのデジタル画像をクラスタリングするための方法および装置に関する。
【背景技術】
【０００３】
画像内のオブジェクトの識別および分類は、多くの分野で役立つ重要な応用分野である。例えば、画像内の人々の識別および分類は、写真アルバム内の画像の自動編成および検索、セキュリティの応用例などに重要かつ有用なものである。写真内およびデジタル画像データ内の人々を識別するために、顔認識が使用されている。しかしながら、信頼性のある顔認識および分類は、照明の変動や姿勢の変化などを含めた画像状態および人間画像の変動の故に、実現が困難である。
【０００４】
画像内の人々の同一性に基づく画像分類技法は、Ｌ．Ｚｈａｎｇ、Ｌ．Ｃｈｅｎ、Ｍ．Ｌｉ、およびＨ．Ｚｈａｎｇの「Ａｕｔｏｍａｔｅｄ  Ａｎｎｏｔａｔｉｏｎ  ｏｆ  Ｈｕｍａｎ  Ｆａｃｅｓ  ｉｎ  Ｆａｍｉｌｙ  Ａｌｂｕｍｓ」Ｐｒｏｃ．ＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ、ＭＭ’０３、Ｂｅｒｋｅｌｅｙ、ＣＡ、ＵＳＡ、Ｎｏｖ．２−８（２００３年）（非特許文献１）で研究がなされている。この刊行物では、画像内の人々を特徴付けする上で、顔の特徴および文脈的特徴が使用されている。しかしながら、この刊行物では、人々の同一性に基づく画像のグループ化は、自動的に行うことができず、画像探索しか利用可能でない。
【０００５】
オブジェクトを複数のクラスにグループ化するために、Ｋ平均クラスタリング・アルゴリズムおよびスペクトル・クラスタリング・アルゴリズムが使用されている。スペクトル・クラスタリング・アルゴリズムは、Ｊ．ＳｈｉおよびＪ．Ｍａｌｉｋの「Ｎｏｒｍａｌｉｚｅｄ  ｃｕｔｓ  ａｎｄ  ｉｍａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ」Ｐｒｏｃ．ＣＶＰＲ（１９９７年６月）７３１〜７３７頁（非特許文献２）、Ｙ．Ｗｅｉｓｓの「Ｓｅｇｍｅｎｔａｔｉｏｎ  ｕｓｉｎｇ  ｅｉｇｅｎｖｅｃｔｏｒｓ：ａ  Ｕｎｉｆｙｉｎｇ  Ｖｉｅｗ」Ｐｒｏｃ．ＩＣＣＶ（１９９９年）（非特許文献３）、ならびに、Ａ．Ｙ．Ｎｇ、Ｍ．Ｉ．Ｊｏｒｄａｎ、およびＹ．Ｗｅｉｓｓの「Ｏｎ  ｓｐｅｃｔｒａｌ  ｃｌｕｓｔｅｒｉｎｇ：Ａｎａｌｙｓｉｓ  ａｎｄ  ａｎ  ａｌｇｏｒｉｔｈｍ」ＮＩＰＳ  １４（２００２年）（非特許文献４）に記載されている。しかしながら、Ｋ平均クラスタリングは、照明の変動や姿勢の変化などの変動に起因して画像状態が変化する人間のクラスタリング（ｈｕｍａｎ  ｃｌｕｓｔｅｒｉｎｇ）の場合と同様に、オブジェクトのクラスタが凸領域に対応しないときは失敗しやすい。スペクトル・クラスタリング方法にはこのような制限がないものの、スペクトル・クラスタリング・アルゴリズムでは、ハード制約条件（ｈａｒｄ  ｃｏｎｓｔｒａｉｎｔ）などの状況情報を強制（ｅｎｆｏｒｃｅ）することが非常に困難である。２つのオブジェクトが同じクラスタに属するか否かに関する情報を提供するハード制約条件は、オブジェクトのクラスタリングを行う上で重要かつ有用な手掛り（ｃｕｅ）を提供する。
【非特許文献１】Ａｕｔｏｍａｔｅｄ  Ａｎｎｏｔａｔｉｏｎ  ｏｆ  Ｈｕｍａｎ  Ｆａｃｅｓ  ｉｎ  Ｆａｍｉｌｙ  Ａｌｂｕｍｓ」Ｐｒｏｃ．ＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ、ＭＭ’０３、Ｂｅｒｋｅｌｅｙ、ＣＡ、ＵＳＡ、Ｎｏｖ．２−８（２００３年）
【非特許文献２】Ｊ．ＳｈｉおよびＪ．Ｍａｌｉｋの「Ｎｏｒｍａｌｉｚｅｄ  ｃｕｔｓ  ａｎｄ  ｉｍａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ」Ｐｒｏｃ．ＣＶＰＲ（１９９７年６月）７３１〜７３７頁
【非特許文献３】Ｙ．Ｗｅｉｓｓの「Ｓｅｇｍｅｎｔａｔｉｏｎ  ｕｓｉｎｇ  ｅｉｇｅｎｖｅｃｔｏｒｓ：ａ  Ｕｎｉｆｙｉｎｇ  Ｖｉｅｗ」Ｐｒｏｃ．ＩＣＣＶ（１９９９年）
【非特許文献４】Ａ．Ｙ．Ｎｇ、Ｍ．Ｉ．Ｊｏｒｄａｎ、およびＹ．Ｗｅｉｓｓの「Ｏｎ  ｓｐｅｃｔｒａｌ  ｃｌｕｓｔｅｒｉｎｇ：Ａｎａｌｙｓｉｓ  ａｎｄ  ａｎ  ａｌｇｏｒｉｔｈｍ」ＮＩＰＳ  １４（２００２年）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本願に開示の諸実施形態は、ハード制約条件が強制できる制約条件付きスペクトル・クラスタリング方法および装置を使用することによって、人間の認識および分類に関連する問題に対処する。この方法および装置は、新しい服装認識アルゴリズム（ｃｌｏｔｈｅｓ  ｒｅｃｏｇｎｉｔｉｏｎ  ａｌｇｏｒｉｔｈｍ）を使用し、顔と服装の認識データの原理的統合を実施する。制約条件付きスペクトル・クラスタリング方法および装置は、文脈的手掛り（ｃｏｎｔｅｘｔ  ｃｕｅ）およびユーザ・フィードバックに由来する論理ベース制約条件などのハード制約条件を強制することができる。
【課題を解決するための手段】
【０００７】
本発明は、デジタル画像を処理するための方法および装置を対象とする。本発明の第１の態様によれば、デジタル画像処理方法は、複数のデジタル画像に属する複数の要素を表す要素データにアクセスするステップと、前記複数の要素中の前記要素間の類似性分析を実施して、前記要素に関係する相関データ結果（ｉｎｔｅｒ−ｒｅｌａｔｉｏｎａｌ  ｄａｔａ  ｒｅｓｕｌｔ）を取得するステップと、前記複数の要素のクラスタリングを実施するステップとを含み、前記クラスタリングを実施するステップは、前記複数の要素中の要素に関係する少なくとも１つのハード制約条件を前記相関データ結果に組み込んで、制約条件付き相関データ結果を取得するステップと、前記制約条件付き相関データ結果から固有ベクトル結果を取得するためのスペクトル分析を実施するステップと、前記少なくとも１つのハード制約条件を強制する基準を用いた制約条件付きクラスタリングを使用し、前記固有ベクトル結果の離散化を実施してクラスタを取得するステップとを含む。
【０００８】
本発明の第２の態様によれば、デジタル画像処理方法は、複数のデジタル画像に属する複数の要素を表す要素データにアクセスするステップと、前記複数の要素中の前記要素間の類似性分析を実施して、前記要素に関係する相関データ結果を取得するステップと、前記複数の要素のクラスタリングを実施するステップとを含み、前記クラスタリングを実施するステップは、前記要素間の非類似性に関係する少なくとも１つのハード・ネガティブ制約条件（ｈａｒｄ  ｎｅｇａｔｉｖｅ  ｃｏｎｓｔｒａｉｎｔ）を前記相関データ結果に組み込んで、制約条件付き相関データ結果を取得するステップと、前記制約条件付き相関データ結果から固有ベクトル結果を取得するためのスペクトル分析を実施するステップと、前記固有ベクトル結果をクラスタリングすることによる前記固有ベクトル結果の離散化を実施して、クラスタを取得するステップとを含む。
【０００９】
本発明の第３の態様によれば、デジタル画像処理装置は、複数のデジタル画像に属する複数の要素を表す要素データを提供する画像データ・ユニットと、前記複数の要素中の前記要素間の類似性分析を実施して、前記要素に関係する相関データ結果を取得する類似性分析ユニットと、前記複数の要素のクラスタリングを実施するクラスタリング・ユニットとを備え、前記クラスタリングを実施するクラスタリング・ユニットは、前記複数の要素中の要素に関係する少なくとも１つのハード制約条件を前記相関データ結果に組み込んで、制約条件付き相関データ結果を取得し、前記制約条件付き相関データ結果から固有ベクトル結果を取得するためのスペクトル分析を実施し、前記少なくとも１つのハード制約条件を強制する基準を用いた制約条件付きクラスタリングを使用し、前記固有ベクトル結果の離散化を実施してクラスタを取得することによって、クラスタリングを実施する。
【００１０】
本発明の第４の態様によれば、デジタル画像処理装置は、複数のデジタル画像に属する複数の要素を表す要素データを提供する画像データ・ユニットと、前記複数の要素中の前記要素間の類似性分析を実施して、前記要素に関係する相関データ結果を取得する類似性分析ユニットと、前記複数の要素のクラスタリングを実施するクラスタリング・ユニットとを備え、前記クラスタリングを実施するクラスタリング・ユニットは、前記要素間の非類似性に関係する少なくとも１つのハード・ネガティブ制約条件を前記相関データ結果に組み込んで、制約条件付き相関データ結果を取得し、前記制約条件付き相関データ結果から固有ベクトル結果を取得するためのスペクトル分析を実施し、前記固有ベクトル結果をクラスタリングすることによる前記固有ベクトル結果の離散化を実施してクラスタを取得することによって、クラスタリングを実施する。
【００１１】
本発明の別の諸態様および利点は、以下の詳細な説明を添付の図面と併せて読めば明らかとなるであろう。
【発明を実施するための最良の形態】
【００１２】
以下の説明では、添付の図面を参照しながら本発明の諸態様をより具体的に記載する。図１は、本発明の一実施形態によるデジタル画像データの制約条件付きスペクトル・クラスタリングを実施する画像処理ユニットを含むシステムを概略的に示すブロック図である。図１に示されるシステム１０８は、次の構成要素、すなわち、画像入力デバイス２８と、画像処理ユニット３８と、表示装置６８と、ユーザ入力ユニット５８と、画像出力ユニット６６と、印刷ユニット４８とを含む。図１のシステム１０８の動作は、以下の論述を読めば明らかとなるであろう。
【００１３】
画像入力デバイス２８は、画像処理ユニット３８に画像データを提供する。画像データは、デジタル画像であることもある。画像入力デバイス２８から入力できるデジタル画像の例は、人々の日常活動の写真や、セキュリティまたは身分証明のために撮影される人々の写真などである。画像入力デバイス２８は、デジタル画像データを提供する任意の数のデバイスの１つまたは複数とすることができる。画像入力デバイス２８は、画像データベースやデジタル・システムなどから取り出されるデジタル画像データを提供することもできる。画像入力デバイス２８は、フィルム上に記録された白黒またはカラー画像を走査するスキャナ、デジタル・カメラ、例えばＣＤ−Ｒ、フロッピー・ディスク、ＵＳＢドライブなどの記録媒体、画像を記憶するデータベース・システム、ネットワーク接続、画像を処理するコンピュータ・アプリケーションのようなデジタル・データを出力する画像処理システムなどであってよい。
【００１４】
画像処理ユニット３８は、画像入力デバイス２８から画像データを受け取り、後段で詳細に論じる様式でデジタル画像データの制約条件付きスペクトル・クラスタリングを実施する。ユーザは、表示装置６８を介して、デジタル画像データの制約条件付きスペクトル・クラスタリングにおける中間結果を含めた画像処理ユニット３８の出力を閲覧することができ、ユーザ入力ユニット５８を介して、画像処理ユニット３８に対するコマンドを入力することができる。図１に示される実施形態では、ユーザ入力ユニット５８は、キーボード６０と、マウス６１とを含んでいるが、他の従来の入力デバイスを使用することもできる。
【００１５】
本発明の諸実施形態によるデジタル画像データの制約条件付きスペクトル・クラスタリングを実施することに加え、画像処理ユニット３８は、ユーザ入力ユニット５８から受け取ったコマンドに従って、知られている色／密度補正機能だけでなく画像の切り取り（ｃｒｏｐｐｉｎｇ）や圧縮など、追加的な画像処理機能を実施することもできる。印刷ユニット４８は、画像処理ユニット３８の出力を受け取り、処理済みの画像データのハード・コピーを生成する。印刷ユニット４８は、画像処理ユニット３８から出力された画像データに従って感光材料を露光させて、その感光材料に画像を記録することができる。印刷ユニット４８は、カラー・レーザ・プリンタなど他の形をとることもできる。画像処理ユニット３８の出力のハード・コピーを生成することに加えてまたはその代わりに、処理済みの画像データは、例えば携帯型記録媒体やネットワーク（図示せず）を介してファイルとしてユーザに返却することもできる。表示装置６８は、画像処理ユニット３８の出力を受け取り、画像データと共に当該画像データのクラスタリング結果を表示する。画像処理ユニット３８の出力は、画像出力ユニット６６にも送ることができる。画像出力ユニット６６は、画像処理ユニット３８から受け取られた画像のクラスタリング結果を記憶するデータベースとすることができる。
【００１６】
図２は、本発明の一実施形態によるデジタル画像データの制約条件付きスペクトル・クラスタリングを実施する画像処理ユニット３８の諸態様をより詳細に示すブロック図である。図２に示されるように、この実施形態による画像処理ユニット３８は、画像データ・ユニット１２５と、服装認識モジュール１３５と、顔認識モジュール１４５と、組合せモジュール１５５と、クラスタリング・モジュール１６５と、任意選択の顔検出モジュール１４４と、任意選択の頭部検出モジュール１４２とを含む。図２の様々な構成要素は離散的な要素として示されているが、かかる表現は説明を分かりやすくするためのものであり、様々な構成要素のある種の動作は、同じ物理デバイスによって、例えば１つまたは複数のマイクロプロセッサによって実施されてもよいことが理解されるべきである。
【００１７】
一般に、図２に示される画像処理ユニット３８の各要素からなる構成は、画像入力デバイス２８から画像セットを入力し、画像セット中の画像内の服装および顔の認識を実施し、画像セットに関する服装と顔の認識結果を組み合わせ、制約条件付きスペクトル・クラスタリングを使用して、画像内に示される人々の同一性に従って画像をクラスタリングする。クラスタリング・モジュール１６５は、画像内に示される人々の同一性に基づいて、画像の分類および識別結果を出力する。かかる分類および識別結果は、印刷ユニット４８、表示装置６８、および／または画像出力ユニット６６に出力される可能性がある。画像データ・ユニット１２５は、服装認識モジュール１３５、顔認識モジュール１４５、任意選択の顔検出モジュール１４４、および任意選択の頭部検出モジュール１４２に画像を送る前に、それらの画像に対する前処理操作および作成処理を実施することもできる。画像に対して実施される前処理操作および作成処理としては、画像のサイズ、色、外観などを変更する、サイズ変更、切り取り、圧縮、色補正などを挙げることができる。
【００１８】
顔検出は、画像セット内の顔の位置およびサイズを判定する。顔認識は、検出された顔の同一性を既知の位置およびサイズを用いて判定する。したがって、顔認識は典型的には、顔検出の後に実施される。顔検出は、任意選択の顔検出モジュール１４４が存在する場合には、当該モジュールによって実施される。顔検出は、顔認識モジュール１４５が顔検出用のサブ・モジュールを含む場合には、顔認識モジュール１４５によって実施されてもよい。したがって、この場合、顔認識の実施には、顔検出の実施が含まれる。服装認識モジュール１３５は、顔認識モジュール１４５または任意選択の顔検出モジュール１４４と通信して、顔検出結果を取得することができる。別法として、服装認識モジュール１３５は、任意選択の頭部検出モジュール１４２から頭部検出結果を取得することもできる。
【００１９】
服装認識モジュール１３５、顔認識モジュール１４５、組合せモジュール１５５、クラスタリング・モジュール１６５、顔検出モジュール１４４、および頭部検出モジュール１４２は、例示的な一実装形態ではソフトウェア・システム／アプリケーションである。次に、図２に示される画像処理ユニット３８内に含まれる構成要素の処理を、図３〜８を参照しながら説明する。
【００２０】
写真の自動編成は、写真アルバムの編成やセキュリティの応用例など、多くの潜在的な用途が存在する重要な応用分野である。現在の応用分野では、顔情報、服装情報、写真記録データ、および他の文脈的手掛りを使用することにより１人または複数の人物の同一性に従って写真が編成できる人間のクラスタリング技法が、実装されている。写真内の人物は、クラスタリング・アルゴリズムを使用し、その人物の同一性に基づいて複数のグループ（クラスタ）に配置される。したがって、同じ個人の画像は全て１つのクラスタ内に所在し、別の個人に由来する画像は他のクラスタ内に所在する。
【００２１】
人々の同一性に基づいて画像をクラスタリングするクラスタリング方法および装置は、顔認識ならびに画像内の他の手掛りを使用することができる。顔以外の情報（本願では「文脈」情報とも呼ばれる）が、人々を認識する上で豊富な手掛りを提供する可能性もある。これらのタイプの文脈情報は典型的には、画像内に所在する。第１のタイプの文脈情報は、ある人物が身に付けている服装などの外観ベース（ａｐｐｅａｒａｎｃｅ−ｂａｓｅｄ）の情報であり、第２のタイプの文脈情報は、例えば１枚の写真内の異なる顔は異なる人物に属するという事実や、一部の人々（例えば夫婦）は一緒に写真に写る可能性が高いという事実によって表現できる論理ベース（ｌｏｇｉｃ−ｂａｓｅｄ）の情報であり、第３のタイプの文脈情報は、写真の撮影された時間など写真のメタデータ（ｍｅｔａ−ｄａｔａ  ｏｆ  ｐｉｃｔｕｒｅｓ）である。これらの３つのタイプの文脈情報はしばしば、人間の観察者が写真内の人々を意識的にまたは無意識的に区別するのに使用される。文脈情報を有効に利用することができるクラスタリング方法は、人間の認識精度を向上させることができる。
【００２２】
本願に提示される方法および装置は、顔だけでなく可能な限り多くの文脈情報も使用することにより、人物の同一性に従って写真を自動的に編成する。本願に記載の方法を使用すると、文脈情報を使用した顔認識エンジンの結果が改善される。
【００２３】
本願では、「人物の画像（ｐｅｒｓｏｎ  ｉｍａｇｅ）」、「人々の画像（ｐｅｏｐｌｅ  ｉｍａｇｅｓ）」、または「複数の人物の画像（ｐｅｒｓｏｎ  ｉｍａｇｅｓ）」という表現は、画像内の人々の画像を指すために相互に置換え可能に使用される。したがって、３人の人を示す画像は、３人の人物の画像を含み、１人の人物を示す画像は、１人の人物の画像を含む。
【００２４】
図３は、図２に示される本発明の一実施形態によるデジタル画像データの制約条件付きスペクトル・クラスタリングを行う画像処理ユニット３８によって実施される処理を示す流れ図である。画像データ・ユニット１２５は、画像入力デバイス２８から受け取った画像セットを入力する（Ｓ２０３）。これらの画像は、様々な姿勢で、様々な時間帯および様々な日にちに、様々な環境で撮影された人々の写真である可能性がある。
【００２５】
顔認識モジュール１４５は、画像セットを受け取り、当該画像セット（ｉｍａｇｅ  ｓｅｔ）に含まれる画像内の顔の顔認識を実施する（Ｓ２０６）。顔認識は、顔の同一性に関連する顔情報を取得するために使用される。顔認識モジュール１４５は、顔の同一性に関係するスコア・セットを導出することができる。かかるスコアは、同じ画像または異なる画像中の２つの顔の相関を指示（ｉｎｄｉｃａｔｅ）することができる。異なる画像中の２つの顔が同じ人物に属する場合には、それらの２つの顔は、高い相関を示すことになる。一方、異なる画像中の２つの顔が異なる人に属する場合には、それらの２つの顔は、低い相関を示すことになる。顔認識モジュール１４５は、参照により本明細書に組み込まれる刊行物であるＴ．Ｌｅｕｎｇの「Ｔｅｘｔｏｎ  Ｃｏｒｒｅｌａｔｉｏｎ  ｆｏｒ  Ｒｅｃｏｇｎｉｔｉｏｎ」Ｐｒｏｃ．Ｅｕｒｏｐｅａｎ  Ｃｏｎｆｅｒｅｎｃｅ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ、ＥＣＣＶ（２００４年）２０３〜２１４頁に記載の方法を使用して顔認識を実施し、顔認識スコアを取得することができる。「Ｔｅｘｔｏｎ  Ｃｏｒｒｅｌａｔｉｏｎ  ｆｏｒ  Ｒｅｃｏｇｎｉｔｉｏｎ」では、顔は、テクストン（ｔｅｘｔｏｎ）と呼ばれる局所的な特性特徴（ｌｏｃａｌ  ｃｈａｒａｃｔｅｒｉｓｔｉｃ  ｆｅａｔｕｒｅ）を使用して、状況の変化による顔の外観の変動がテクストン間の相関で符号化されるように表現される。テクストンの相関をモデル化するには、２つの方法を使用することができる。１つの方法は、条件付きテクストン分散モデル（ｃｏｎｄｉｔｉｏｎａｌ  ｔｅｘｔｏｎ  ｄｉｓｔｒｉｂｕｔｉｏｎ  ｍｏｄｅｌ）であり、位置的独立性を仮定するものである。第２の方法は、フィッシャー線形識別分析を使用して各位置間の２次変動（ｓｅｃｏｎｄ  ｏｒｄｅｒ  ｖａｒｉａｔｉｏｎ）を取得するものである。テクストン・モデルは、長時間に及ぶ様々な照明および姿勢の画像内の顔認識に使用することができる。顔認識モジュール１４５は、顔対における顔間の類似性を測定する顔認識スコアを導出する（Ｓ２０６）。次いで、顔認識モジュール１４５は、顔認識スコアを組合せモジュール１５５に出力する（Ｓ２０７）。顔認識モジュール１４５によって他の顔認識技法が使用されてもよい。
【００２６】
服装認識モジュール１３５も、画像データ・ユニット１２５から画像セットを受け取り、服装認識を実施し、画像セットに含まれる画像内の人々の服装に関して、服装認識の類似性スコアを取得する（Ｓ２０９）。本発明で言及される服装は、実際の服装だけでなく、画像内の人々に関連する他の外部オブジェクトも含む。本願では、「服装」という用語は、様々な人々を区別する際に次の全てのオブジェクトが役立つ可能性があることから、実際の服装だけでなく、帽子、靴、腕時計、眼鏡なども指す。服装認識モジュール１３５は、服装認識スコアを組合せモジュール１５５に出力する（Ｓ２１０）。
【００２７】
服装認識スコアは、様々な人々の服装間の類似の程度を測定する。例えば、同じ服装をした人物が２つの画像に登場するときは、２つの異なる画像中の当該人物の服装に関連するスコアは、それらの服装が類似することを指示する。服装認識モジュール１３５は、参照によりその内容全体が本明細書に組み込まれる「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｃｏｎｔｅｘｔ−Ａｉｄｅｄ  Ｈｕｍａｎ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ」と題する相互参照の関連米国出願に記載の方法を使用し、服装認識を実施して服装認識スコアを取得することができる。
【００２８】
組合せモジュール１５５は、顔認識スコアを顔認識モジュール１４５から受け取り、服装認識スコアを服装認識モジュール１３５から受け取る。次いで、組合せモジュール１５５は、顔認識スコアと服装認識スコアとを統合して、画像内に存在する人々の間の複合的な類似性測定値（ｃｏｍｂｉｎｅｄ  ｓｉｍｉｌａｒｉｔｙ  ｍｅａｓｕｒｅｓ）を取得する（Ｓ２１３）。顔のスコアと服装のスコアの両方を統合する複合的な類似性測定値は、様々な画像中の２人の人が同じ人物か否かを判定するより頑健な方法を実現する。線形ロジスティック回帰、フィッシャー線形識別分析、またはエキスパートの混合（ｍｉｘｔｕｒｅ  ｏｆ  ｅｘｐｅｒｔｓ）を使用して顔と服装の認識結果を組み合わせ、複合的な類似性測定値を取得することができる。顔と服装の認識結果を組み合わせて複合的な類似性測定値を取得する線形ロジスティック回帰法は、参照によりその内容全体が本明細書に組み込まれる「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ａｄａｐｔｉｖｅ  Ｃｏｎｔｅｘｔ−Ａｉｄｅｄ  Ｈｕｍａｎ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ」と題する相互参照の関連米国出願に記載される技法を使用することができる。
【００２９】
クラスタリング・モジュール１６５は、組合せモジュール１５５から複合的な類似性測定値を受け取る。クラスタリング・モジュール１６５はこの複合的な類似性測定値に基づいて、画像内に存在する人々の同一性に従って画像を複数のクラスタにグループ化する（Ｓ２１７）。クラスタリング・モジュール１６５は、制約条件付きスペクトル・クラスタリングを使用して画像のクラスタリングを実施する。クラスタリング・モジュール１６５は、クラスタリング結果を出力する（Ｓ２１９）。かかる画像のクラスタリング結果は、印刷ユニット４８、表示装置６８、および／または画像出力ユニット６６に出力される可能性がある。
【００３０】
図４は、本発明の一実施形態による服装認識を実施してデジタル画像データ内の服装に関する服装認識スコアを取得する技法を示す流れ図である。図４に記載の技法を使用して、服装認識モジュール１３５は、図３のステップＳ２０９の画像内の服装に関する類似性スコアを取得することができる。
【００３１】
服装認識は、画像内の服装の断片を識別し、服装の断片が互いにどの程度類似しているかを判定し、したがって、２人の人物の画像中の２着の服装の断片が実際に同じ個人に属する可能性がどの程度あるかを指示するものである。服装認識には３つの主要なステップが含まれ、すなわち、服装の検出およびセグメント化、特徴抽出による服装表現、ならびに抽出された特徴に基づく類似性計算が含まれる。
【００３２】
服装認識モジュール１３５は、画像データ・ユニット１２５から画像セットを受け取る（Ｓ２４４）。次いで、服装認識モジュール１３５は、画像内に存在する服装の検出およびセグメント化を実施する（Ｓ２４８）。服装の検出およびセグメント化は、初期の服装領域を検出する服装位置の初期推定と、洗練された（ｒｅｆｉｎｅｄ）服装領域を取得する画像内の初期の服装領域のセグメント化と、洗練された服装領域からのクラッタ除去とを含む。服装位置の初期推定値は、顔認識モジュール１４５からの顔検出結果、またはそれが存在する場合は任意選択の顔検出モジュール１４４からの顔検出結果を使用することによって、顔検出から取得される。顔認識モジュール１４５および任意選択の顔検出モジュール１４４は、参照により本明細書に組み込まれる次の各刊行物、すなわち、Ｓ．Ｉｏｆｆｅの「Ｒｅｄ  Ｅｙｅ  Ｄｅｔｅｃｔｉｏｎ  ｗｉｔｈ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ」Ｐｒｏｃ．ＩＣＩＰ（２００３年）、Ｈ．ＳｃｈｎｅｉｄｅｒｍａｎおよびＴ．Ｋａｎａｄｅの「Ａ  Ｓｔａｔｉｓｔｉｃａｌ  Ｍｅｔｈｏｄ  ｆｏｒ  ３Ｄ  Ｏｂｊｅｃｔ  Ｄｅｔｅｃｔｉｏｎ  Ａｐｐｌｉｅｄ  ｔｏ  Ｆａｃｅｓ  ａｎｄ  Ｃａｒｓ」Ｐｒｏｃ．ＣＶＰＲ（２０００年）、ならびにＰ．ＶｉｏｌａおよびＭ．Ｊｏｎｅｓの「Ｒａｐｉｄ  Ｏｂｊｅｃｔ  Ｄｅｔｅｃｔｉｏｎ  Ｕｓｉｎｇ  ａ  Ｂｏｏｓｔｅｄ  Ｃａｓｃａｄｅ  ｏｆ  Ｓｉｍｐｌｅ  Ｆｅａｔｕｒｅｓ」Ｐｒｏｃ．ＣＶＰＲ（２００１年）に記載の方法の１つまたは複数を使用して顔検出を実施することができる。服装位置の初期推定値は、任意選択の頭部検出モジュール１４２からの頭部検出結果から取得することもできる。頭部検出は、上記の各刊行物に記載の方法と同様の方法を使用して実施することができる。頭部検出を実施する他の方法が使用されてもよい。
【００３３】
クラッタは、実際には服装領域の一部ではないが服装領域と混合されまたはそれと混ざり合う画像領域である。クラッタとしては、服装を身に付けている人々の皮膚などの皮膚領域と、人物の前にある物体や人々の服装を遮る部分などの遮蔽物とが挙げられる。
【００３４】
次に、服装認識モジュール１３５は特徴を抽出し、服装領域の数値表現を取得するために、抽出された特徴を使用して服装領域を表現する（Ｓ２５２）。服装認識モジュール１３５によって生成される服装領域の数値表現は、さらなる分析のための服装領域の操作を可能にする。服装領域の代表的な領域またはコード・ワードが抽出され、服装領域に現れるコード・ワードの周波数から特徴ベクトルが生成される。特徴ベクトルは、服装領域の数値表現を提供する。
【００３５】
最後に、服装認識モジュール１３５は、類似性計算を実施して服装領域間の類似性スコアを判定する（Ｓ２５６）。２着の服装の断片の類似性スコアは、２着の服装の断片に関して重み付けされたコード・ワードの周波数ベクトルを正規化したスカラ積として計算される。次いで、服装認識モジュール１３５は、複数対の服装の断片に関する類似性スコアを組合せモジュール１５５に出力する（Ｓ２１０）。ステップＳ２４８、Ｓ２５２、およびＳ２５６がどのように実施されるかに関するさらなる詳細は、参照によりその内容全体が本明細書に組み込まれる「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｃｏｎｔｅｘｔ−Ａｉｄｅｄ  Ｈｕｍａｎ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ」と題する相互参照の関連米国出願で確認することができる。
【００３６】
図５Ａは、顔と服装の認識結果を組み合わせて本発明の一実施形態による人物の画像に関する複合的な類似性測定値を取得する技法を示す図である。図５Ａに記載の技法を使用して、組合せモジュール１５５は、図３のステップＳ２１３を実施する間に、人物の画像に関する複合的な類似性測定値を取得することができる。線形ロジスティック回帰、フィッシャー線形識別分析、またはエキスパートの混合を使用して顔と服装の認識結果を組み合わせ、複合的な類似性測定値を取得することができる。
【００３７】
服装情報は、顔情報を補完するものであり、プロフィールの顔の場合によくあるように、顔の位置および角度が変化する場合、顔の画像品質が悪い場合、または画像内の顔の表情が変動する場合は、非常に有益な情報となる。顔と服装の手掛りを統合したときは、顔の手掛りだけを使用したときよりも強力な画像内の人々の同一性認識の結果が達成される。組合せモジュール１５５は、服装の文脈を顔の文脈と統合して、類似性測定値を確率測定値の形で取得する。
【００３８】
手掛りの組合せの問題は、数学的には以下のように記述することができる。任意の対の画像に関しては、ｘ１を顔認識に由来する顔認識スコアとし、ｘ２を服装認識に由来する服装認識スコアとし、画像内に現れる２人の人の間の類似性を測定するものとする。ランダム変数Ｙは、当該対の人物が同じ人物であるか否かを示すものとする。したがって、Ｙ＝１は、２人の人物が同じ人物であることを意味し、Ｙ＝０は、そうでないことを意味する。手掛りの組合せの問題は、確率
Ｐ（Ｙ｜ｘ１，ｘ２）＝ｆ（ｘ１，ｘ２）      （１）
から、当該対の人物の画像が同じ人物を表すものであるか否かが適切な形で指示されるような関数ｆ（ｘ１，ｘ２）を発見することによって解決することができる。
【００３９】
線形ロジスティック回帰法では、関数ｆは、
【００４０】
【数１】
2007272890.tif 000003
【００４１】
となり、
上式で、
【００４２】
【数２】
2007272890.tif 000004
【００４３】
であり、ｗ＝［ｗ１，ｗ２，ｗ０］は、訓練画像セット（ａ  ｔｒａｉｎｉｎｇ  ｓｅｔ  ｏｆ  ｉｍａｇｅｓ）を学習することによってパラメータが決定される（Ｓ２８３）３次元ベクトルである。訓練画像セットは、同じ人物または異なる人物に由来する複数対の人物の画像を含む。複数対の訓練画像に関する顔認識スコアおよび服装認識スコアが、抽出される。パラメータｗは、公式（２）の確率から、訓練対（ｔｒａｉｎｉｎｇ  ｐａｉｒ）に由来する２人の人が同じ人物である場合と、訓練対に由来する２人の人が同じ人物でない場合とが正しく記述される可能性を最大化することができるパラメータとして決定される。訓練画像からｗ＝［ｗ１，ｗ２，ｗ０］がどのように決定されるかについての詳細は、参照によりその内容全体が本明細書に組み込まれる「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ａｄａｐｔｉｖｅ  Ｃｏｎｔｅｘｔ−Ａｉｄｅｄ  Ｈｕｍａｎ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ」と題する相互参照の関連米国出願で確認することができる。
【００４４】
パラメータｗは、学習プロセスの後に決定され、新しい画像に由来する顔認識スコアと服装認識スコアとを使用して新しい画像内の人々の間の複合的な類似性測定値を取得する、画像処理ユニット３８の実際の動作に関する線形ロジスティック回帰で使用される（Ｓ２７９）。画像内の１対の人々に関しては、当該対の人物の画像に由来する顔認識スコアと服装認識スコアとを公式（２）に導入することによって、複合的な類似性測定値Ｐ（Ｙ＝１）が得られる（Ｓ２８５）。Ｐ（Ｙ＝１）は、１対の人物が実際に同じ人物となる確率である。したがって、顔認識スコアと服装認識スコアのいずれかが使用可能でない、または１対の人物の画像について欠落している場合も、確率Ｐ（Ｙ＝１）を計算する公式を採用することができる（Ｓ２８７、Ｓ２８９）。線形ロジスティック回帰法および公式選択／採用方法に関する詳細な説明は、参照によりその内容全体が本明細書に組み込まれる「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ａｄａｐｔｉｖｅ  Ｃｏｎｔｅｘｔ−Ａｉｄｅｄ  Ｈｕｍａｎ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ」と題する相互参照の関連米国出願で確認することができる。
【００４５】
フィッシャー線形識別分析は、組合せモジュール１５５が顔と服装の認識結果を組み合わせ、複合的な類似性測定値を取得するために使用することもできる（Ｓ２７５）。フィッシャーの識別分析は、正の例（同じ人物に由来する画像対）と負の例（異なる人物に由来する画像対）とを最もよく区別できる係数を発見する基準を提供する。フィッシャー線形識別分析を使用して学習された線形係数を使用して、顔認識と服装認識に由来するスコアを線形的に組み合わせることができる。
【００４６】
エキスパートの混合は、組合せモジュール１５５がそれを使用して顔と服装の認識結果を組み合わせ、複合的な類似性測定値を取得することができる第３の方法である（Ｓ２７７）。線形ロジスティック回帰法およびフィッシャー線形識別分析法は、本質的に線形的であり、組合せの係数は、空間全体で同じになる。エキスパートの混合は、空間全体を分割することによって類似性測定値を組み合わせる手法を提供する。エキスパートの混合法は、それぞれロジスティック回帰単位となるいくつかのエキスパートを組み合わせるものである。組合せモジュール１５５は、参照により本明細書に組み込まれるＭ．Ｉ．ＪｏｒｄａｎおよびＲ．Ａ．Ｊａｃｏｂｓの「Ｈｉｅｒａｒｃｈｉｃａｌ  Ｍｉｘｔｕｒｅｓ  ｏｆ  Ｅｘｐｅｒｔｓ  ａｎｄ  ｔｈｅ  ＥＭ  Ａｌｇｏｒｉｔｈｍ」Ｎｅｕｒａｌ  Ｃｏｍｐｕｔａｔｉｏｎ，６（１９９４年）１８１〜２１４頁に記載のエキスパートの混合法を使用することもできる。
【００４７】
図５Ｂは、本発明の一実施形態による顔および服装の類似性スコアの利用可能性に基づいて人物の画像の類似性測定値を判定する技法を示す流れ図である。図５Ｂの技法は、組合せモジュール１５５が画像内の人々の間の類似性スコアを判定するために使用することができる。
【００４８】
組合せモジュール１５５は、服装認識モジュール１３５および顔認識モジュール１４５から顔および服装の認識スコアを受け取るものと仮定する（Ｓ５０１）。画像セット内に存在する人物の画像に関する顔および服装の認識スコアが、抽出される。組合せモジュール１５５は、写真の撮影された時間、または他の暗黙的な時間、あるいは画像セット中の画像の位置情報を検証することによって、画像セット中の画像が同じイベント（同じ日）に由来するものであるか否かを判定する（Ｓ５０２）。服装は、服装が変更されない同じイベントにおいて（または同じ日に）人々を認識する重要な手掛りを提供する。画像セット中の画像が同じイベントと同じ日に由来しない場合には、組合せモジュール１５５は、顔認識スコアだけを使用して、本明細書では総類似性スコア（ｏｖｅｒａｌｌ  ｓｉｍｉｌａｒｉｔｙ  ｓｃｏｒｅ）とも呼ばれる人々の間の複合的な類似性測定値を計算する（Ｓ５０３）。次いで、組合せモジュール１５５は、総類似性スコアをクラスタリング・モジュール１６５に送る。
【００４９】
画像セット中の画像が同じ日／イベントに由来するものである場合には、組合せモジュール１５５は、服装認識スコアと顔認識スコアがどちらも利用可能かつ使用可能であれば、これらのスコアを組み合わせることによって人々の間の総類似性スコアを計算する（Ｓ５１１）。顔がプロフィールの顔である場合または顔を遮るものが存在する場合によくあるように、いくつかの対の人物の画像に関する顔認識スコアが利用可能でない場合には、組合せモジュール１５５は、服装認識スコアだけを使用して人々の間の総類似性スコアを計算する（Ｓ５１３）。画像内の服装を遮るものが存在する場合によくあるように、いくつかの対の人物の画像に関する服装認識スコアが利用可能でない場合には、組合せモジュール１５５は、顔認識スコアだけを使用して人々の間の総類似性スコアを計算する（Ｓ５１５）。組合せモジュール１５５は、総類似性スコアをクラスタリング・モジュール１６５に送る。
【００５０】
画像内の２人の人が同じ（または同様の）服装をしているときは、特別な場合が発生する。人々が同じ（または同様の）服装をしている場合は、服装情報を組み込むことが困難となる。１枚の写真内の２人の人は通常、同じ個人ではない。したがって、１枚の写真内の２人の人物ｓｉおよびｓｊが同じ（または同様の）服装をしている場合は（Ｓ５１７）、服装情報を破棄する必要がある。したがって、同じ画像に由来するｓｉおよびｓｊが高い服装類似性スコアを有するときは、組合せモジュール１５５は、服装類似性スコアを欠落として扱い、顔類似性スコアだけを使用してｓｉとｓｊの間の総類似性スコアを計算する（Ｓ５１９）。
【００５１】
さらに、ｓｉと第３の人物ｓｋ（ｓｋ≠ｓｊ）の間の服装類似性スコアが高い場合（Ｓ５２１）、すなわちｓｋの服装がｓｉの服装に（したがってｓｊの服装にも）非常に似ている場合には、総類似性スコアを計算する際に、ｓｉとｓｋに関する服装類似性スコアも欠落として扱われる（Ｓ５２３）。同じように、ｓｊと第３の人物ｓｋ（ｓｋ≠ｓｉ）の間の服装類似性スコアが高い場合、すなわちｓｋの服装がｓｊの服装に（したがってｓｉの服装にも）非常に似ている場合には、総類似性スコアを計算する際に、ｓｊとｓｋに関する服装類似性スコアも欠落として扱われる。
【００５２】
一方、画像セット中の任意の画像内に存在するｓｉと別の人物ｓｋ（ｓｋ≠ｓｊ）の画像間の１対の服装類似性が高くない場合には、総類似性スコアを計算する際に、ｓｉとｓｋの間の服装認識スコアと共に、それが利用可能であれば顔認識スコアも使用することができる（Ｓ５２５）。同様に、画像セット中の任意の画像内に存在するｓｊと別の人物ｓｋ（ｓｋ≠ｓｉ）の画像間の１対の服装類似性が高くない場合には、総類似性スコアを計算する際に、ｓｊとｓｋの間の服装認識スコアと共に、それが利用可能であれば顔認識スコアも使用することができる。
【００５３】
クラスタリング・モジュール１６５は、全ての総類似性スコアを受け取り、それらのスコアを使用して、画像内の人々の同一性に基づいて画像をクラスタリングする（Ｓ５０７）。
【００５４】
図６は、本発明の一実施形態による人物の画像のスペクトル・クラスタリングを実施する技法を示す流れ図である。図６の技法は、クラスタリング・モジュール１６５が画像内の人々の同一性に基づいて画像をクラスタリングするために使用することができる。組合せモジュール１５５によって取得される１対の確率類似性測定値（総類似性スコア）は、画像中の人々を各自の同一性に基づいてクラスタリングする基礎を提供し、したがって、各画像に示される人々の同一性に従って画像をクラスタリングする基礎を提供する。
【００５５】
Ｊ．ＳｈｉおよびＪ．Ｍａｌｉｋの「Ｎｏｒｍａｌｉｚｅｄ  ｃｕｔｓ  ａｎｄ  ｉｍａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ」Ｐｒｏｃ．ＣＶＰＲ（１９９７年６月）７３１〜７３７頁、Ｙ．Ｗｅｉｓｓの「Ｓｅｇｍｅｎｔａｔｉｏｎ  ｕｓｉｎｇ  ｅｉｇｅｎｖｅｃｔｏｒｓ：ａ  Ｕｎｉｆｙｉｎｇ  Ｖｉｅｗ」Ｐｒｏｃ．ＩＣＣＶ（１９９９年）、Ａ．Ｙ．Ｎｇ、Ｍ．Ｉ．Ｊｏｒｄａｎ、およびＹ．Ｗｅｉｓｓの「Ｏｎ  ｓｐｅｃｔｒａｌ  ｃｌｕｓｔｅｒｉｎｇ：Ａｎａｌｙｓｉｓ  ａｎｄ  ａｎ  ａｌｇｏｒｉｔｈｍ」ＮＩＰＳ  １４（２００２年）、ならびにＳｔｅｌｌａ  Ｘ．Ｙｕの博士論文「Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｍｏｄｅｌｓ  ｏｆ  Ｐｅｒｃｅｐｔｕａｌ  Ｏｒｇａｎｉｚａｔｉｏｎ」Ｃａｒｎｅｇｉｅ  Ｍｅｌｌｏｎ  Ｕｎｉｖｅｒｓｉｔｙ（２００３年：ＣＭＵ−ＲＩ−ＴＲ−０３−１４）に記載されるように、従来のＫ平均法から現行のスペクトル・クラスタリング法にいたるまで、多くのクラスタリング・アルゴリズムが開発されている。Ｋ平均法を凌ぐスペクトル・クラスタリング法の主要な利点の１つは、クラスタが凸領域に対応しないとき、Ｋ平均法は失敗しやすい可能性があることである。各クラスタの密度がしばしばガウス型と仮定されるＥＭを使用してモデルを混合する場合にも同じことがいえる。人間のクラスタリングを行う際は、画像状態の様々な側面が変化する可能性もあることから、クラスタは、必ずしも凸領域を形成しない。したがって本願では、人間のクラスタリングにはスペクトル・クラスタリング・アルゴリズムの方が好都合である。
【００５６】
スペクトル・クラスタリング法は、ポイント間の１対の類似性から導出される行列の固有値および固有ベクトルによって各ポイントをクラスタリングする。スペクトル・クラスタリング法ではグローバル構造が想定されておらず、したがって、非凸クラスタを扱うことができる。スペクトル・クラスタリングは、例えば各ポイントがグラフ内のノードとなり、２つのポイント間の類似性が各ポイント間のエッジの重みを与える、グラフ・パーティショニングと同様のものである。人間のクラスタリングを行う際は、各ポイントは、人物の画像であり、類似性測定値は、顔および／または服装の認識スコアから同じ同一性が導出される確率である。
【００５７】
コンピュータ・ビジョンで使用される１つの効果的なスペクトル・クラスタリング法は、参照により本明細書に組み込まれるＪ．ＳｈｉおよびＪ．Ｍａｌｉｋの「Ｎｏｒｍａｌｉｚｅｄ  Ｃｕｔｓ  ａｎｄ  Ｉｍａｇｅ  Ｓｅｇｍｅｎｔａｔｉｏｎ」Ｐｒｏｃ．ＣＶＰＲ（１９９７年６月）７３１〜７３７頁に記載の正規化カット（ｎｏｒｍａｌｉｚｅｄ  ｃｕｔｓ）方法である。上記の刊行物の正規化カット方法は、参照により本明細書に組み込まれるＳｔｅｌｌａ  Ｘ．Ｙｕの博士論文「Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｍｏｄｅｌｓ  ｏｆ  Ｐｅｒｃｅｐｔｕａｌ  Ｏｒｇａｎｉｚａｔｉｏｎ」Ｃａｒｎｅｇｉｅ  Ｍｅｌｌｏｎ  Ｕｎｉｖｅｒｓｉｔｙ（２００３年：ＣＭＵ−ＲＩ−ＴＲ−０３−１４）において一般化されている。
【００５８】
正規化カットの基準は、各クラスタ内のリンク（類似性）を最大化し、クラスタ間のリンクを最小化する。ポイント・セットＳ＝｛ｓ１，．．．，ｓＮ｝は、Ｋ個のクラスタにクラスタリングされるものとする。Ｗを、項Ｗｉｊがポイントｓｉとｓｊの間の類似性となるＮ×Ｎの重み行列とする。Ｄは、ｉ番目の対角要素がＷのｉ番目の行の合計となる対角行列を表すものとする。クラスタリング結果は、Ｎ×Ｋの区画行列Ｘで表すことができ、ここでポイントｓｉがｋ番目のクラスタに属するとき、かつそのときに限り、Ｘｉｋ＝１となる。Ｘｌは、Ｘのｌ番目の列ベクトルを表すものとし、１≦ｌ≦Ｋとする。Ｘｌは、ｌ番目のクラスタのメンバシップ・インジケータ・ベクトルである。これらの表記法を使用して、正規化カットの基準は、
【００５９】
【数３】
2007272890.tif 000005
【００６０】
を最大化することができる最良の区画行列Ｘ＊を発見する。
【００６１】
Ｘに対するバイナリ区画行列の制約条件を緩和し、レイリー・リッツ法を使用すれば、連続領域の最適解がＤ−１／２ＷＤ−１／２におけるＫ個の最大固有ベクトルから導出されることを示すことができる。ｖｉを、Ｄ−１／２ＷＤ−１／２におけるｉ番目の最大固有ベクトルとし、ＶＫ＝［ｖ１，ｖ２，．．．，ｖＫ］とする。したがって、ε（Ｘ）の連続最適解（ｃｏｎｔｉｎｕｏｕｓ  ｏｐｔｉｍｕｍ）は、
【００６２】
【数４】
2007272890.tif 000006
【００６３】
によって、すなわち、ＶＫの行が正規化されたバージョン（
【００６４】
【数５】
2007272890.tif 000007
【００６５】
の各行は単位長さとなる）によって達成することができる。最適解は実際には一意でなく、上記の最適解は、正規直交変換：
【００６６】
【数６】
2007272890.tif 000008
【００６７】
までの行列セットであり、上式で、ＩｋはＫ×Ｋの同一性行列である。
【００６８】
したがって、画像処理ユニット３８の動作に関して、ポイント・セットＳ＝｛ｓ１，．．．，ｓＮ｝は、クラスタリング・モジュール１６５に入力されるものとし、ここで１≦ｉ≦Ｎとする各ポイントｓｉは、画像セット中の画像に由来する人物の画像（顔または服装あるいはその両方を含む可能性がある）となる（Ｓ３０１）。したがって、画像Ｉ１が３人の人を示す場合には、画像Ｉ１は、組Ｓのｓ１，ｓ２，ｓ３に寄与する。画像Ｉ２が２人の人を示す場合には、画像Ｉ２は、組Ｓのｓ４，ｓ５に寄与し、以下もまた同様である。ポイントｓ１，ｓ２，．．．，ｓＮは、画像内で発見される人々のＫ個の同一性の内の１つにそれぞれ対応するＫ個のクラスタにクラスタリングされることになる。
【００６９】
顔認識結果および／または服装認識結果から、２つのポイント間の類似性を組合せモジュール１５５によって計算することができる。次に、参照により本明細書に組み込まれるＡ．Ｙ．Ｎｇ、Ｍ．Ｉ．Ｊｏｒｄａｎ、およびＹ．Ｗｅｉｓｓの「Ｏｎ  ｓｐｅｃｔｒａｌ  ｃｌｕｓｔｅｒｉｎｇ：Ａｎａｌｙｓｉｓ  ａｎｄ  ａｎ  Ａｌｇｏｒｉｔｈｍ」ＮＩＰＳ  １４（２００２年）に記載のスペクトル・クラスタリング法を説明する。ポイント（人物の画像）間の類似性測定値を使用して、ｉ≠ｊのときは各項Ａｉｊがｓｉとｓｊの間の類似性スコアとなり、対角項についてＡｉｊ＝０となる、Ｎ×Ｎの親和性行列（ａｆｆｉｎｉｔｙ  ｍａｔｒｉｘ）Ａが形成される（Ｓ３０３）。次いで、クラスタリング・モジュール１６５は、Ｄを、それ自体のｉ番目の対角要素がＡのｉ番目の行の合計となる対角行列として定義する（Ｓ３０５）。次いで、クラスタリング・モジュール１６５は、行列Ｌ＝Ｄ−１／２ＡＤ−１／２を構築し（Ｓ３０７）、ＬにおけるＫ個の最大固有ベクトルを発見し、それらの固有ベクトルを列にスタックすることによって行列Ｘを形成する（Ｓ３０９）。
【００７０】
画像セット内の異なる人の数Ｋは、クラスタリング・モジュール１６５がＫ個の最大固有ベクトルを選択する前にクラスタリング・モジュール１６５に入力される（Ｓ３０８）。画像セット内の異なる人の数は、発見されるクラスタの数である。画像内の異なる人またはクラスタの数は、複数の手法で判定することができる。画像セット内の異なる人の数は、ユーザがユーザ入力ユニット５８を使用して、クラスタリング・モジュール１６５に手動で入力することができる。画像セット内の異なる人の数は、Ｌ行列の固有値を使用して発見することもできる。Ｌの最大固有値は１であり、全ての固有値は非負である。固有値は、１＝λ１≧λ２≧．．．≧λＮ≧０となるように降順にソートされる。λｉからλｉ＋１への値の変化が大きい場合は、ｉをクラスタの数Ｋに適するように選択することができる。Ｋ平均クラスタリングでは、各ポイントからそれらの中心までの距離の合計に従ってクラスタの数を選択することにより、画像セット内の異なる人（クラスタ）の数を発見することもできる。クラスタの数Ｋに関していくつかの値を検査することができる。Ｋは、距離の計算の際に考慮する様々な次元の正規化が実施された後に、各ポイントからそれらの中心までの距離の合計が最小となるクラスタの数として選出される。
【００７１】
次いで、クラスタリング・モジュール１６５は、Ｘの各行を単位長さに再び正規化することによって行列Ｙを形成する（Ｓ３１１）。Ｙの各行をポイントとして扱うことにより、クラスタリング・モジュール１６５は、Ｋ平均アルゴリズムまたは他のアルゴリズムを使用してＹの各行をクラスタリングする（Ｓ３１３）。最後に、クラスタリング・モジュール１６５は、Ｙのｉ番目の行をクラスタｊに割り当てる場合は、各ポイントｓｉをクラスタｊに割り当てる（Ｓ３１５）。
【００７２】
行列の固有値セットは、行列のスペクトルと呼ばれる。図６に示されるアルゴリズムは、データの親和性行列における固有値と固有ベクトルとを利用するものであり、したがって、スペクトル・クラスタリング・アルゴリズムに該当する。このアルゴリズムは本質的に、新しい空間においてデータがより良い形でクラスタリングされるように、データを新しい空間に変換する。
【００７３】
図７は、本発明の一実施形態によるハード制約条件を伴う相反性行列（ｒｅｐｕｌｓｉｏｎ  ｍａｔｒｉｘ）を使用して人物の画像のスペクトル・クラスタリングを実施する技法を示す流れ図である。図７の技法は、クラスタリング・モジュール１６５が画像内の人々の同一性に基づいて画像をクラスタリングするために使用することができる。
【００７４】
参照により本明細書に組み込まれる刊行物であるＳｔｅｌｌａ  Ｘ．Ｙｕの博士論文「Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｍｏｄｅｌｓ  ｏｆ  Ｐｅｒｃｅｐｔｕａｌ  Ｏｒｇａｎｉｚａｔｉｏｎ」Ｃａｒｎｅｇｉｅ  Ｍｅｌｌｏｎ  Ｕｎｉｖｅｒｓｉｔｙ（２００３年：ＣＭＵ−ＲＩ−ＴＲ−０３−１４）には、ポイント間の非類似性をモデル化するための相反性行列が紹介されている。クラスタリングの目標は、クラスタ内の類似性とクラスタ間の非類似性とを最大化する一方で、それぞれの補数を最小化することとされている。ポイント・セットＳ＝｛ｓ１，．．．，ｓＮ｝は、Ｋ個のクラスタにクラスタリングする必要があるものとし、ここで各ポイントｓｋは、人物の画像である。Ａを、類似性を定量化する行列（親和性行列）とし、Ｒを、非類似性を表す行列（相反性行列）とし、ＤＡおよびＤＲをそれぞれ、ＡおよびＲの行の合計に対応する対角行列とする。
【００７５】
【数７】
2007272890.tif 000009
【００７６】
かつ
【００７７】
【数８】
2007272890.tif 000010
【００７８】
と定義する。次いで、目標は、
【００７９】
【数９】
2007272890.tif 000011
【００８０】
を最大化することができる区画行列Ｘを発見することとなる。連続最適解は、相反性行列が存在しない場合と同様の形式で、
【００８１】
【数１０】
2007272890.tif 000012
【００８２】
のＫ個の最大固有ベクトルを使用して発見することができる。
【００８３】
連続解は固有システムを解くことによって発見できるので、親和性行列と相反性行列とを使用する上記の方法は高速であり、連続領域のグローバル最適解を達成することができる。しかしながら、クラスタリングに関しては、連続解を離散化する必要がある。Ｓｔｅｌｌａ  Ｘ．Ｙｕの博士論文「Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｍｏｄｅｌｓ  ｏｆ  Ｐｅｒｃｅｐｔｕａｌ  Ｏｒｇａｎｉｚａｔｉｏｎ」Ｃａｒｎｅｇｉｅ  Ｍｅｌｌｏｎ  Ｕｎｉｖｅｒｓｉｔｙ（２００３年：ＣＭＵ−ＲＩ−ＴＲ−０３−１４）では、離散化は、
【００８４】
【数１２】
2007272890.tif 000013
【００８５】
を最小化することができるバイナリ区画行列
【００８６】
【数１１】
2007272890.tif 000014
【００８７】
を発見するまで繰り返され、上式で、｜｜Ｍ｜｜は行列Ｍのフロベニウス・ノルム
【００８８】
【数１３】
2007272890.tif 000015
【００８９】
であり、Ｏは任意の正規直交行列であり、
【００９０】
【数１４】
2007272890.tif 000016
【００９１】
は、連続最適解である。
【００９２】
クラスタリング・モジュール１６５の目標は、可能な限り多くの文脈情報を利用して、各人物の同一性に従って写真をクラスタリングすることである。２つのポイント（２人の人物の画像）間の類似性計算は、クラスタリング・プロセスで重要なものである。画像内の顔と服装に加えて、その手掛りを組み込み人間の認識力を高めるのに利用できる追加的な手掛りが存在する可能性もある。論理ベース制約条件は、人々を同一性に基づいてクラスタリングする際に役立つ可能性がある追加的な手掛りである。かかる手掛りは、ハード制約条件とすることもできる。論理ベースの文脈および制約条件は、１枚の写真内の異なる顔は異なる個人に属するという制約条件や、夫婦は一緒に写真に写る可能性が高いという制約条件など、一般的な論理から得ることが可能な知識である。一部の論理ベース制約条件は、ハード制約条件である。例えば、１枚の写真内の異なる顔は異なる個人に属するという制約条件は、ネガティブ型のハード制約条件である。他の論理ベース制約条件は、夫婦は一緒に写真に写る可能性が高いという制約条件などのソフト制約条件である。別の有用なポジティブ型のソフト制約条件は、ある人物が一群の画像内に存在するという事前知識である。
【００９３】
したがって、ある顔が人物Ａに属するはずであるという制約条件は、ハード制約条件である。一方、ある顔が人物Ａに属する確率が８０％であるという事実は、ソフト制約条件である。クラスタリング・モジュール１６５は、ハード制約条件として表現できる論理ベースの文脈をクラスタリング方法に組み込み、より多くの文脈的手掛りを使用することによって、人間のクラスタリング結果を改善することができる。論理制約条件を利用するために、図６に示されるクラスタリング手法は、相反性行列を使用することによって変更される。
【００９４】
人間のクラスタリングを行う際は、かかるハード制約条件を強制できることが望ましい。しかしながら、プライアーズ（ｐｒｉｏｒｓ）（ハード制約条件など）を組み込んだ場合は、スペクトル・クラスタリング・アルゴリズムに支障が生じる。Ｓｔｅｌｌａ  Ｘ．Ｙｕの博士論文「Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｍｏｄｅｌｓ  ｏｆ  Ｐｅｒｃｅｐｔｕａｌ  Ｏｒｇａｎｉｚａｔｉｏｎ」Ｃａｒｎｅｇｉｅ  Ｍｅｌｌｏｎ  Ｕｎｉｖｅｒｓｉｔｙ（２００３年：ＣＭＵ−ＲＩ−ＴＲ−０３−１４）、ならびにＳ．Ｘ．ＹｕおよびＪ．Ｓｈｉの「Ｇｒｏｕｐｉｎｇ  ｗｉｔｈ  Ｂｉａｓ」ＮＩＰＳ（２００１年）では、ポジティブ制約条件を課す方法が提案されているが、離散化ステップで制約条件の違反が起きる可能性がある故に、ポジティブ制約条件が尊重される保証はない。
【００９５】
本願の図７における人間のクラスタリングは、ネガティブ型ならびにポジティブ型のハード制約条件を強制しようと試みるものである。
【００９６】
公式（４）、（５）、および（６）で記述されるクラスタリング方法で導入した表記法を使用して、Ｓ＝｛ｓ１，．．．，ｓＮ｝を、画像セット中の全ての画像に由来する人物の画像に関連するポイント・セットとする（Ｓ３２５）。ポイントｓ１，ｓ２，．．．，ｓＮは、画像内で発見される人々の合計Ｋ個の同一性の内の１つにそれぞれ対応するＫ個のクラスタにクラスタリングされることになる。２つのポイントｓｉとｓｊの間の１対の類似性は、顔および／または服装の認識スコアならびに他の文脈的手掛りから取得される。複数対の人々の画像に関する類似性の値は、組合せモジュール１５５によって、複数対の人々が同じ人物となる確率として計算された。クラスタリング・モジュール１６５は、複数対の人物の画像に関連する類似性測定値を使用して、ｉ≠ｊのときは各項Ａｉｊがｓｉとｓｊの間の確率類似性スコアとなり、ｉ＝ｊのときはＡｉｊ＝０となる、すなわち行列Ａの対角項についてＡｉｊ＝０となる、Ｎ×Ｎの親和性行列Ａを形成する（Ｓ３２７）。
【００９７】
ｓｉおよびｓｊは、同じ写真内で発見される２人の人物の画像とする。この場合、２人の人物は典型的には、異なる人物であり（異なる同一性を有し）、したがって、クラスタリング・モジュール１６５は、ｓｉおよびｓｊを異なるクラスタ内に配置することになる。この制約条件を埋め込むために、ｓｉとｓｊの間の類似性に対応する親和性行列Ａ内の項Ａｉｊは、ゼロにセットされ、Ａｉｊ＝０となる（Ｓ３２９）。
【００９８】
ハード・ネガティブ制約条件を強化するために、２つのポイントｓｉとｓｊの非類似性の程度を記述する相反性行列Ｒが生成される（Ｓ３３１）。ｓｉおよびｓｊが同じ写真内で発見される２人の人物の画像であり、したがって異なる人を表す場合は、項Ｒｉｊは、１にセットされる。より一般的にいえば、項Ｒｉｊは、ｓｉおよびｓｊが同じクラスタ内に所在する可能性がない場合に１にセットされることになる（Ｓ３３３）。ポイントｓｉとｓｊの間の既知の制約条件が存在しない場合は、対応する項Ｒｉｊは、ゼロにセットされる。
【００９９】
ＤＲを、それ自体のｉ番目の対角要素がＲのｉ番目の行の合計となる対角行列とし（Ｓ３３５）、ＤＡを、それ自体のｉ番目の対角要素がＡのｉ番目の行の合計となる対角行列とする（Ｓ３３７）。行列
【０１００】
【数１５】
2007272890.tif 000017
【０１０１】
および
【０１０２】
【数１６】
2007272890.tif 000018
【０１０３】
は、公式（４）および（５）の場合と同様に、
【０１０４】
【数１７】
2007272890.tif 000019
【０１０５】
および
【０１０６】
【数１８】
2007272890.tif 000020
【０１０７】
によって定義される（Ｓ３３９）。次いで、Ｌ行列が、
【０１０８】
【数１９】
2007272890.tif 000021
【０１０９】
として定義される（Ｓ３４１）。次いで、クラスタリング・モジュール１６５は、Ｌ’におけるＫ個の最大固有ベクトルを発見し、それらの固有ベクトルを列にスタックすることによって行列Ｘを形成する（Ｓ３４３）。
【０１１０】
画像セット内の異なる人の数Ｋは、クラスタリング・モジュール１６５がＫ個の最大固有ベクトルを選択する前にクラスタリング・モジュール１６５に入力される（Ｓ３６０）。画像セット内の異なる人の数は、発見されるクラスタの数である。画像内の異なる人またはクラスタの数は、複数の手法で判定することができる。画像セット内の異なる人の数は、ユーザがユーザ入力ユニット５８を使用して、クラスタリング・モジュール１６５に手動で入力することができる。画像セット内の異なる人の数は、図６の場合と同様に構築される行列Ｌ０＝Ｄ−１／２ＡＤ−１／２の固有値を使用して、図６で説明したような形で発見することもできる。画像セット内の異なる人（クラスタ）の数は、図６で説明したようなＫ平均クラスタリングにおいて、各ポイントからそれらの中心までの距離の合計に従ってクラスタの数を選択することによって発見することもできる。
【０１１１】
次いで、クラスタリング・モジュール１６５は、Ｘの各行を単位長さに再び正規化することによって行列Ｙを形成する（Ｓ３４５）。Ｙの各行をポイントとして扱うことにより、クラスタリング・モジュール１６５は、Ｋ平均アルゴリズムまたは他のアルゴリズムを使用してＹの各行をクラスタリングする（Ｓ３４７）。最後に、クラスタリング・モジュール１６５は、Ｙのｉ番目の行をクラスタｊに割り当てる場合は、各ポイントｓｉをクラスタｊに割り当てる（Ｓ３５０）。
【０１１２】
図８は、本発明の一実施形態によるハード制約条件を強制する、人物の画像の制約条件付きＫ平均クラスタリング（ｃｏｎｓｔｒａｉｎｅｄ  Ｋ−ｍｅａｎｓ  ｃｌｕｓｔｅｒｉｎｇ）を用いたスペクトル・クラスタリングを実施する技法を示す流れ図である。図８の技法は、クラスタリング・モジュール１６５が画像内の人々の同一性に基づいて画像をクラスタリングするハード制約条件を強制するために使用することができる。
【０１１３】
スペクトル・クラスタリング法は、クラスタが凸領域に対応しないとき、Ｋ平均法が失敗しやすい可能性がある故にＫ平均法よりも有利であるが、スペクトル・クラスタリング法では、ハード制約条件を強制することが困難である。親和性行列Ａおよび相反性行列Ｒにハード制約条件を導入した場合も、離散化ステップの間にハード制約条件が満足される保証がない故に、これらの制約条件を強制するには十分でない可能性がある。制約条件付きＫ平均クラスタリングは、ハード制約条件が満足されることを保証するために実施される。
【０１１４】
Ｋ平均クラスタリングにハード制約条件を統合する制約条件付きＫ平均アルゴリズムは、参照により本明細書に組み込まれるＫ．Ｗａｇｓｔａｆｆ、Ｃ．Ｃａｒｄｉｅ、Ｓ．Ｒｏｇｅｒｓ、およびＳ．Ｓｃｈｒｏｅｄｌの「Ｃｏｎｓｔｒａｉｎｅｄ  Ｋ−Ｍｅａｎｓ  Ｃｌｕｓｔｅｒｉｎｇ  ｗｉｔｈ  Ｂａｃｋｇｒｏｕｎｄ  Ｋｎｏｗｌｅｄｇｅ」Ｐｒｏｃ．１８ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ  ＩＣＭＬ（２００１年）５７７〜５８４頁に提示されている。参照により本明細書に組み込まれるＡ．Ｙ．Ｎｇ、Ｍ．Ｉ．Ｊｏｒｄａｎ、およびＹ．Ｗｅｉｓｓの刊行物「Ｏｎ  Ｓｐｅｃｔｒａｌ  Ｃｌｕｓｔｅｒｉｎｇ：Ａｎａｌｙｓｉｓ  ａｎｄ  ａｎ  Ａｌｇｏｒｉｔｈｍ」ＮＩＰＳ  １４（２００２年）では、離散化ステップにおいてＫ平均法が使用されている。しかしながら、この刊行物では、相反性行列が使用されず、相反性行列を用いたＫ平均法の使用も正当化されず、制約条件付きＫ平均法の代わりに通常のＫ平均法が使用されており、したがって制約条件が何ら課されていない。
【０１１５】
本願では、離散化ステップにおいて、画像内の人間のクラスタリングを行うハード制約条件を強制する制約条件付きＫ平均アルゴリズムが実施される。制約条件付きＫ平均アルゴリズムは、参照により本明細書に組み込まれる刊行物であるＫ．Ｗａｇｓｔａｆｆ、Ｃ．Ｃａｒｄｉｅ、Ｓ．Ｒｏｇｅｒｓ、およびＳ．Ｓｃｈｒｏｅｄｌの「Ｃｏｎｓｔｒａｉｎｅｄ  Ｋ−Ｍｅａｎｓ  Ｃｌｕｓｔｅｒｉｎｇ  ｗｉｔｈ  Ｂａｃｋｇｒｏｕｎｄ  Ｋｎｏｗｌｅｄｇｅ」Ｐｒｏｃ．１８ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ  ＩＣＭＬ（２００１年）５７７〜５８４頁に記載の方法を使用することができる。
【０１１６】
Ｓ＝｛ｓ１，．．．，ｓＮ｝は、画像セット中の全ての画像に由来する人物の画像に関連するポイント・セットとする（Ｓ４２５）。ポイントｓ１，ｓ２，．．．，ｓＮは、画像内で発見される人々の合計Ｋ個の同一性の内の１つにそれぞれ対応するＫ個のクラスタにクラスタリングされることになる。先述のように、２つのポイントｓｉとｓｊの間の１対の類似性は、顔および／または服装の認識スコアならびに他の文脈的手掛りから取得される。複数対の人々の画像に関する類似性の値は、組合せモジュール１５５によって、複数対の人々が同じ人物となる確率として計算された。クラスタリング・モジュール１６５は、複数対の人物の画像に関連する類似性測定値を使用して、ｉ≠ｊのときは各項Ａｉｊがｓｉとｓｊの間の確率類似性スコアとなり、ｉ＝ｊのときはＡｉｊ＝０となる、すなわち行列Ａの対角項についてＡｉｊ＝０となる、Ｎ×Ｎの親和性行列Ａを形成する（Ｓ４２７）。
【０１１７】
次に、クラスタリング・モジュール１６５は、ｓｉとｓｊが異なるクラスタに属する（異なる人となる）ことが分かったときにＡｉｊ＝０とすることにより、親和性行列Ａにハード・ネガティブ制約条件を埋め込む（Ｓ４２９）。クラスタリング・モジュール１６５はまた、ｓｉとｓｊの間にハード・ポジティブ制約条件が存在するときにＡｉｊ＝１とすることにより、親和性行列Ａにハード・ポジティブ制約条件も埋め込む（Ｓ４２９、Ｓ４７１）。ポジティブ制約条件の一例は、ある人物が連続する写真に現れるという制約条件である。例えば、２つの画像内の２人の人物の画像ｓｉとｓｊが同じ個人に属する場合は、上記のアルゴリズムは、親和性行列Ａにおいて項Ａｉｊ＝１とセットし、ステップＳ４３１で生成された相反性行列Ｒにおいて項Ｒｉｊ＝０とセットすることにより、かかるポジティブ制約条件を強制することができる。かかるハード・ポジティブ制約条件は、ある人物の現れる画像がアプリケーションで正確に示された旨の指示がユーザから受け取られるユーザ・フィードバックから利用可能になる可能性がある。
【０１１８】
クラスタリング・モジュール１６５は、２つのポイントｓｉとｓｊの非類似性の程度を記述する相反性行列Ｒも生成する（Ｓ４３１）。ｓｉとｓｊが同じクラスタ内に所在する可能性がない（異なる人を表す）場合は、ハード・ネガティブ制約条件を埋め込むために、項Ｒｉｊは、１にセットされる（Ｓ４３３）。クラスタリング・モジュール１６５は、ポジティブ制約条件が利用可能であれば、相反性行列Ｒにハード・ポジティブ制約条件を埋め込むこともできる（Ｓ４７１）。
【０１１９】
次いで、クラスタリング・モジュール１６５は、それ自体のｉ番目の対角要素がＲのｉ番目の行の合計となる対角行列ＤＲを生成し（Ｓ４３５）、それ自体のｉ番目の対角要素がＡのｉ番目の行の合計となる対角行列ＤＡを生成する（Ｓ４３７）。行列
【０１２０】
【数２０】
2007272890.tif 000022
【０１２１】
および
【０１２２】
【数２１】
2007272890.tif 000023
【０１２３】
は、公式（４）および（５）の場合と同様に、
【０１２４】
【数２２】
2007272890.tif 000024
【０１２５】
および
【０１２６】
【数２３】
2007272890.tif 000025
【０１２７】
によって定義される（Ｓ４３９）。次いで、Ｌ行列が、
【０１２８】
【数２４】
2007272890.tif 000026
【０１２９】
として定義される（Ｓ４４１）。
【０１３０】
次いで、クラスタリング・モジュール１６５は、Ｌ’のＫ個の最大固有ベクトルを発見し、それらの固有ベクトルを列にスタックすることによって行列Ｘを形成する（Ｓ４４３）。画像セット内の異なる人の数Ｋは、クラスタリング・モジュール１６５がＫ個の最大固有ベクトルを選択する前にクラスタリング・モジュール１６５に入力される（Ｓ４７３）。画像セット内の異なる人の数は、発見されるクラスタの数である。画像内の異なる人またはクラスタの数は、複数の手法で判定することができる。画像セット内の異なる人の数は、ユーザがユーザ入力ユニット５８を使用して、クラスタリング・モジュール１６５に手動で入力することができる。画像セット内の異なる人の数は、図６の場合と同様に構築される行列Ｌ０＝Ｄ−１／２ＡＤ−１／２の固有値を使用して、図６で説明したような形で発見することもできる。画像セット内の異なる人（クラスタ）の数は、図６で説明したようなＫ平均クラスタリングにおいて、各ポイントからそれらの中心までの距離の合計に従ってクラスタの数を選択することによって発見することもできる。
【０１３１】
次いで、クラスタリング・モジュール１６５は、Ｘの各行を単位長さに再び正規化することによって行列Ｙを形成する（Ｓ４４５）。Ｙの各行をポイントとして扱うことにより、クラスタリング・モジュール１６５は、制約条件付きＫ平均クラスタリングを使用してＹの各行をクラスタリングする（Ｓ４４７）。ユーザ入力５８からの追加のポジティブ制約条件および／またはネガティブ制約条件が、クラスタリング・モジュール１６５によって受け取られることもある（Ｓ４８１）。制約条件付きＫ平均クラスタリングは、ハード制約条件を強制する。制約条件付きＫ平均アルゴリズムが繰り返される度に、ポイントがクラスタに割り当てられるときは、（１）クラスタの中心までの距離、および（２）ハード制約条件が満足されたかどうか、という２つの基準が使用される。ポイントは、ハード制約条件が違反されないときに限りクラスタに割り当てることができる。したがって、各ポイントは、ハード制約条件に違反しない最も近くにあるクラスタに割り当てられる。したがって、制約条件付きＫ平均法は、ハード制約条件が満足されることを保証する。クラスタリング・モジュール１６５はステップＳ４４７で、制約条件付きＫ平均法の代わりに、制約条件を使用し尊重する他の制約条件付きクラスタリング方法を使用することもできる。
【０１３２】
クラスタリング・モジュール１６５は、Ｙのｉ番目の行をクラスタｊに割り当てる場合は、各ポイントｓｉをクラスタｊに割り当てる（Ｓ４５０）。次いで、クラスタリング・モジュール１６５は、画像内の人々の同一性に基づいて、画像セット内の画像に関するＫ個のクラスタを出力する（Ｓ４８３）。ユーザは、クラスタリング結果を閲覧し、ある人物が画像内に現れるか否かに関することなど、追加の新しいポジティブ制約条件および／またはネガティブ制約条件を入力することができる（Ｓ４８１）。追加の新しいポジティブ制約条件および／またはネガティブ制約条件の入力は、ステップＳ４２９およびＳ４３３で、親和性行列Ａおよび相反性行列Ｒに埋め込まれる。次いで、クラスタリング・モジュール１６５は、制約条件付きＫ平均クラスタリングを再び実行し、それによって新たに受け取られた制約条件を強制することができる。図８のステップ・シーケンスは、クラスタリング結果を洗練するためにユーザが望む所望の回数だけ実施することができる。
【０１３３】
次に、（相反性行列および制約条件の使用の有無を問わず）Ｋ平均法の使用が正当化され、したがって制約条件付きＫ平均法の使用が正当化される理由を提示する。
【０１３４】
【数２５】
2007272890.tif 000027
【０１３５】
は、図８のステップＳ４４５または図７のステップ３４５または図６のステップＳ３１１で取得される行列Ｙである。
【０１３６】
【数２６】
2007272890.tif 000028
【０１３７】
の各行は、人物の画像ｓｒに対応しており、したがって、
【０１３８】
【数２７】
2007272890.tif 000029
【０１３９】
の各行は、ポイントとして解釈され、それらのポイントに対してＫ平均クラスタリングまたは制約条件付きＫ平均クラスタリングが実施される。離散化ステップでは、Ｋ平均クラスタリングは、元のポイント・セットＳ＝｛ｓ１，．．．，ｓＮ｝に対してではなく、
【０１４０】
【数２８】
2007272890.tif 000030
【０１４１】
の各行に対して実施するのが有利である。というのも、Ｋ平均クラスタリングは、
【０１４２】
【数３０】
2007272890.tif 000031
【０１４３】
を取得するために実施されるスペクトル・クラスタリングの各ステップが場合により（元のポイント・セットＳ＝｛ｓ１，．．．，ｓＮ｝が非凸クラスタを形成している場合に）非凸クラスタを凸クラスタに変換したときに、
【０１４４】
【数２９】
2007272890.tif 000032
【０１４５】
の各行に対して作用することができるからである。
【０１４６】
Ｋ平均クラスタリングまたは制約条件付きＫ平均クラスタリング方法は、
【０１４７】
【数３２】
2007272890.tif 000033
【０１４８】
を最小化する最良の区画行列
【０１４９】
【数３１】
2007272890.tif 000034
【０１５０】
と同等の良好な結果を達成することができ、上式で、Ｏは正規直交行列である。Ｋ平均クラスタリングが
【０１５１】
【数３４】
2007272890.tif 000035
【０１５２】
を最小化する最良の区画行列
【０１５３】
【数３３】
2007272890.tif 000036
【０１５４】
と同等の良好な結果が達成できることを証明するために、命題１および２が使用される。命題１は、任意の正規直交行列Ｏについて、
【０１５５】
【数３５】
2007272890.tif 000037
【０１５６】
および
【０１５７】
【数３６】
2007272890.tif 000038
【０１５８】
の行ベクトルが、次の条件の下に、例えば
【０１５９】
【数３７】
2007272890.tif 000039
【０１６０】
に関しては、ｃｌが初期のｌ番目の中心となり、次いで
【０１６１】
【数３８】
2007272890.tif 000040
【０１６２】
に関しては、ｃｌＯが初期のｌ番目の中心となる場合に、同じＫ平均クラスタリング結果を有することを表明する。
【０１６３】
命題２は、
【０１６４】
【数３９】
2007272890.tif 000041
【０１６５】
と仮定し、Ｏ＊が
【０１６６】
【数４０】
2007272890.tif 000042
【０１６７】
を最小化する離散的な区画行列および回転行列となることを表明する。Ｋ×Ｋの同一性行列ＩＫの各行がクラスタの中心として解釈される場合は、
【０１６８】
【数４１】
2007272890.tif 000043
【０１６９】
の行ベクトルに対してＫ平均クラスタリングを１回繰り返すことにより、区画行列
【０１７０】
【数４２】
2007272890.tif 000044
【０１７１】
で表されるクラスタリング結果と同じクラスタリング結果が達成される。さらに、
【０１７２】
【数４３】
2007272890.tif 000045
【０１７３】
が小さい場合は、クラスタの中心は、ＩＫの各行から遠く離れることはなく、したがって、
【０１７４】
【数４４】
2007272890.tif 000046
【０１７５】
の各行に対するＫ平均クラスタリングは、
【０１７６】
【数４５】
2007272890.tif 000047
【０１７７】
と同じクラスタリング結果に収束することになる。命題１および２から、
【０１７８】
【数４６】
2007272890.tif 000048
【０１７９】
が小さく、（Ｏ＊）−１の各行が初期のクラスタの中心として解釈される場合は、
【０１８０】
【数４７】
2007272890.tif 000049
【０１８１】
に対するＫ平均クラスタリングは、
【０１８２】
【数４８】
2007272890.tif 000050
【０１８３】
と同じ結果を達成する。
【０１８４】
【数４９】
2007272890.tif 000051
【０１８５】
が小さいということは、各ポイントが実際に良好なクラスタに由来することを意味し、そうでない場合には、クラスタリング・アルゴリズムは十分な働きをすることができない。（Ｏ＊）−１の良好な近似値は、
【０１８６】
【数５０】
2007272890.tif 000052
【０１８７】
の各行の直交ベクトルを発見することによって見出すことができる。したがって、制約条件付きＫ平均法によってハード制約条件が強制できることから、Ｋ平均法は、ハード制約条件を組み込むのにより適した離散化方法といえる。
【０１８８】
本願では、制約条件付きスペクトル・クラスタリングを使用するための方法および装置が説明されている。この方法および装置は、顔情報と、服装情報と、他の利用可能な文脈情報（１枚の写真内の人々が異なる個人となる事実など）とを使用して認識および分類を実施するものである。本願に提示される方法および装置は、複数の結果を達成する。本願に提示される方法および装置は、１枚の写真に由来する複数の人物が異なるクラスタ内に存在する事実などの文脈情報を利用して、スペクトル・クラスタリング・アルゴリズムを発展させるものである。この方法および装置は、従来のクラスタリング・アルゴリズムよりも優れた結果をもたらす。本願に提示される方法および装置は、顔および服装の情報が欠落している場合にも、適切な周辺確率を計算することによってこれに対処することができる。本願の方法および装置は、相反性行列および制約条件付きＫ平均法を使用することによって、顔情報および服装情報だけでなくより多くの文脈的手掛りも組み込むことができる。例えば、この方法および装置は、１枚の写真に由来する複数の人物が異なるクラスタ内に所在するという制約条件などのハード・ネガティブ制約条件を強制することができる。本願の方法および装置は、同じ画像内で発見される異なる人が同じ（または同様の）服装をしている場合にも対処することができる。
【０１８９】
本願に詳細に記載される諸実施形態は、人間の認識および分類に関するものであるが、本発明の諸原理は、デジタル画像内に現れる他のタイプのオブジェクトに適用することもできる。
【０１９０】
以上、本発明の詳細な諸実施形態および諸実装形態を説明してきたが、本発明の趣旨および範囲を逸脱しない様々な修正形態が可能であることは明らかなはずである。
【図面の簡単な説明】
【０１９１】
【図１】本発明の一実施形態によるデジタル画像データの制約条件付きスペクトル・クラスタリングを実施する画像処理ユニットを含むシステムを概略的に示すブロック図である。
【図２】本発明の一実施形態によるデジタル画像データの制約条件付きスペクトル・クラスタリングを実施する画像処理ユニットの諸態様をより詳細に示すブロック図である。
【図３】図２に示される本発明の一実施形態によるデジタル画像データの制約条件付きスペクトル・クラスタリングを行う画像処理ユニットによって実施される処理を示す流れ図である。
【図４】本発明の一実施形態による服装認識を実施してデジタル画像データ内の服装に関する服装認識スコアを取得する技法を示す流れ図である。
【図５Ａ】顔と服装の認識結果を組み合わせて本発明の一実施形態による人物の画像の複合的な類似性測定値を取得する技法を示す図である。
【図５Ｂ】本発明の一実施形態による顔および服装の類似性スコアの利用可能性に基づいて人物の画像の類似性測定値を判定する技法を示す流れ図である。
【図６】本発明の一実施形態による人物の画像のスペクトル・クラスタリングを実施する技法を示す流れ図である。
【図７】本発明の一実施形態によるハード制約条件を伴う相反性行列を使用して人物の画像のスペクトル・クラスタリングを実施する技法を示す流れ図である。
【図８】本発明の一実施形態によるハード制約条件を強制する、人物の画像の制約条件付きＫ平均クラスタリングを用いたスペクトル・クラスタリングを実施する技法を示す流れ図である。
【符号の説明】
【０１９２】
２８  画像入力デバイス
３８  画像処理ユニット
４８  印刷ユニット
５８  ユーザ入力ユニット
６０  キーボード
６１  マウス
６６  画像出力ユニット
６８  表示装置
１２５  画像データ・ユニット
１３５  服装認識モジュール
１４２  頭部検出モジュール
１４４  顔検出モジュール
１４５  顔認識モジュール
１５５  組合せモジュール
１６５  クラスタリング・モジュール
【図１】
2007272890.tif 000053
【図２】
2007272890.tif 000054
【図３】
2007272890.tif 000055
【図４】
2007272890.tif 000056
【図５Ａ】
2007272890.tif 000057
【図５Ｂ】
2007272890.tif 000058
【図６】
2007272890.tif 000059
【図７】
2007272890.tif 000060
【図８】
2007272890.tif 000061