(57)【要約】パターン分類のための画像を表す方法は、分類のためにフィッシャー線形識別関数（ＦＬＤ）またはカーネルフィッシャー線形識別関数（ＫＦＬＤ）を使用して従来のＩｓｏｍａｐを拡張する。拡張Ｉｓｏｍａｐ法はパターン分類のための画像に対応するデータ点の測地線距離を予測し、ペアの測地線距離を特徴ベクトルとして使用する。この方法は特徴ベクトルのクラスタ中心間の距離を最大化する最適の投影方向を見つけるために特徴ベクトルにＦＬＤを適用する。この方法はＦＬＤの代わりにＫＦＬＤを特徴ベクトルに適用することも可能である。
2005535017.tif 000002
【特許請求の範囲】
【請求項１】
パターン分類のための画像セットを表す方法であって、
入力空間の前記画像セットに対応するデータ点を受け取るステップと、
前記データ点が近傍点であるかを示す近傍グラフを生成するステップと、
前記近傍グラフに基づいて前記データ点間の測地線距離を予測するステップと、
他のデータ点までの前記測地線距離に対応する関連特徴ベクトルによって個々の前記データ点を表すステップと、
パターン分類のための前記特徴ベクトルの投影に最適な方向を取得するために、前記データ点と関連づけられた前記特徴ベクトルにフィッシャー線形識別関数を適用するステップとからなる方法。
【請求項２】
前記近傍グラフを生成するステップは、
前記データ点間の距離を決定するステップと、
決定された前記距離に基づいて前記データ点は近傍点であるかを決定するステップと、
前記データ点が近傍点であると決定した場合は、決定された前記距離を前記近傍グラフのために選択するステップと、
前記データ点が近傍点でないと決定した場合は、無限大の数値を前記近傍グラフのために選択するステップとからなることを特徴とする請求項１の方法。
【請求項３】
前記データ点が近傍点であるかを決定するステップは、決定された前記距離に基づいて個々のデータ点の近いものから順番に所定の数のデータ点を前記近傍点として選択することを特徴とする請求項２の方法。
【請求項４】
前記データ点が近傍点であるかを決定するステップは、決定された前記距離に基づいて個々のデータ点から所定の半径内のデータ点を前記近傍点として選択することを特徴とする請求項２の方法。
【請求項５】
前記データ点間の測地線距離を予測するステップは、前記近傍グラフ上の近傍データ点間をフロイド−ワーシャルアルゴリズムを用いた連続的な近距離接続で決まる距離によって、前記データ点間の測地線距離を近似することからなることを特徴とする請求項１の方法。
【請求項６】
前記特徴ベクトルにフィッシャー線形識別関数を適用するステップは、特徴ベクトルの個々のクラスタ内での変動を略最小化しながら、特徴ベクトルクラスタ間の変動を略最大化するために、前記入力空間より次元の低い低次元空間へ前記特徴ベクトルを投影するステップからなることを特徴とする請求項１の方法。
【請求項７】
前記特徴ベクトルクラスタ間の前記変動は級間散布図行列によって表され、前記特徴ベクトルの個々のクラスタ内の前記変動は級内散布図行列によって表されることを特徴とする請求項６の方法。
【請求項８】
前記級間散布図行列の前記級内散布図行列に対する比率を略最大化するように、前記特徴ベクトルは前記低次元空間へ投影されることを特徴とする請求項７の方法。
【請求項９】
前記画像は顔画像または数字画像であることを特徴とする請求項１の方法。
【請求項１０】
パターン分類のための画像セットを表す方法であって、
入力空間の前記画像セットに対応するデータ点を受け取るステップと、
前記データ点が近傍点であるかを示す近傍グラフを生成するステップと、
前記近傍グラフに基づいて前記データ点間の測地線距離を予測するステップと、
他のデータ点までの前記測地線距離に対応する関連特徴ベクトルによって個々の前記データ点を表すステップと、
パターン分類のための前記特徴ベクトルの投影に最適な方向を取得するために、前記データ点と関連づけられた前記特徴ベクトルにカーネルフィッシャー線形識別関数を適用するステップとからなる方法。
【請求項１１】
前記近傍グラフを生成するステップは、
前記データ点間の距離を決定するステップと、
決定された前記距離に基づいて前記データ点は近傍点であるかを決定するステップと、
前記データ点が近傍点であると決定した場合は、決定された前記距離を近傍グラフのために選択するステップと、
前記データ点が近傍点でないと決定した場合は、無限大の数値を近傍グラフのために選択するステップとからなることを特徴とする請求項１０の方法。
【請求項１２】
前記データ点が近傍点であるかを決定するステップは、決定された前記距離に基づいて個々のデータ点の近いものから順番に所定の数のデータ点を前記近傍点として選択することを特徴とする請求項１１の方法。
【請求項１３】
前記データ点が近傍点であるかを決定するステップは、決定された前記距離に基づいて個々のデータ点から所定の半径内のデータ点を前記近傍点として選択することを特徴とする請求項１１の方法。
【請求項１４】
前記データ点間の測地線距離を予測するステップは、前記近傍グラフ上の近傍データ点間をフロイド−ワーシャルアルゴリズムを用いた連続的な近距離接続で決まる距離によって、前記データ点間の測地線距離を近似することからなることを特徴とする請求項１０の方法。
【請求項１５】
前記特徴ベクトルにカーネルフィッシャー線形識別関数を適用するステップは、
投影関数を用いて高次元の特徴空間へ前記特徴ベクトルを投影するステップと、
高次元の前記特徴空間へ投影した前記特徴ベクトルに対してカーネルフィッシャー顔を生成するステップと、
前記特徴ベクトルの個々のクラスタ内の変動を略最小化しながら、前記特徴ベクトル間の変動を略最大化するために、前記入力空間および前記カーネルフィッシャー顔に基づく前記高次元の特徴空間より低い次元の低次元空間へ前記特徴ベクトル投影するステップとからなることを特徴とする請求項１０の方法。
【請求項１６】
前記特徴ベクトルクラスタ間の前記変動は級間散布図行列によって表され、前記特徴ベクトルの個々のクラスタ内の前記変動は級内散布図行列によって表されることを特徴とする請求項１５の方法。
【請求項１７】
前記級間散布図行列の前記級内散布図行列に対する比率を略最大化するように、前記特徴ベクトルは前記低次元空間へ投影されることを特徴とする請求項１６の方法。
【請求項１８】
前記級内散布図行列に単位行列の１部分が加えられたことを特徴とする請求項１７の方法。
【請求項１９】
2005535017.tif 000012
【請求項２０】
前記画像は顔画像または数字画像であることを特徴とする請求項１０の方法。
【請求項２１】
パターン分類のための画像セットを表すシステムであって、
入力空間の前記画像セットに対応するデータ点を受け取り、前記データ点が近傍点であるかを示す近傍グラフを生成する近傍グラフ生成モジュールと、
前記近傍グラフに基づいて前記データ点間の測地線距離を予測する測地線距離予測モジュールと、
他のデータ点までの前記測地線距離に対応する関連特徴ベクトルによって個々の前記データ点を表し、パターン分類のための前記特徴ベクトルの投影に最適な方向を取得するために、前記データ点と関連づけられた前記特徴ベクトルにフィッシャー線形識別関数を適用するフィッシャー線形識別関数モジュールとからなるシステム。
【請求項２２】
前記近傍グラフ生成モジュールは、
前記データ点間の距離を決定するステップと、
決定された前記距離に基づいて前記データ点は近傍点であるかを決定するステップと、
前記データ点が近傍点であると決定した場合は、決定された前記距離を前記近傍グラフのために選択するステップと、
前記データ点が近傍点でないと決定した場合は、無限大の数値を前記近傍グラフのために選択するステップとによって前記近傍グラフを生成することを特徴とする請求項２１のシステム。
【請求項２３】
前記データ点が近傍点であるかを決定するステップは、決定された前記距離に基づいて個々のデータ点の近いものから順番に所定の数のデータ点を前記近傍点として選択することを特徴とする請求項２２のシステム。
【請求項２４】
前記データ点が近傍点であるかを決定するステップは、決定された前記距離に基づいて個々のデータ点から所定の半径内のデータ点を前記近傍点として選択することを特徴とする請求項２２のシステム。
【請求項２５】
前記測地線距離予測モジュールは、前記近傍グラフ上の近傍データ点間をフロイド−ワーシャルアルゴリズムを用いた連続的な近距離接続で決まる距離によって、前記データ点間の測地線距離を近似することを特徴とする請求項２１のシステム。
【請求項２６】
前記フィッシャー線形識別関数モジュールは、前記特徴ベクトルの個々のクラスタ内の変動を略最小化しながら、前記特徴ベクトル間の変動を略最大化するために、前記入力空間より次元の低い低次元空間への前記特徴ベクトルの投影によって、前記特徴ベクトルにフィッシャー線形識別関数を適用することを特徴とする請求項２１のシステム。
【請求項２７】
前記特徴ベクトルクラスタ間の前記変動は級間散布図行列によって表され、前記特徴ベクトルの個々のクラスタ内の前記変動は級内散布図行列によって表されることを特徴とする請求項２６のシステム。
【請求項２８】
前記級間散布図行列の前記級内散布図行列に対する比率を略最大化するように、前記特徴ベクトルは前記低次元空間へ投影されることを特徴とする請求項２７のシステム。
【請求項２９】
前記画像は顔画像または数字画像であることを特徴とする請求項２１のシステム。
【請求項３０】
パターン分類のための画像セットを表すシステムであって、
入力空間の前記画像セットに対応するデータ点を受け取り、前記データ点が近傍点であるかを示す近傍グラフを生成する近傍グラフ生成モジュールと、
前記近傍グラフに基づいて前記データ点間の測地線距離を予測する測地線距離予測モジュールと、
他のデータ点までの前記測地線距離に対応する関連特徴ベクトルによって個々の前記データ点を表し、パターン分類のための前記特徴ベクトルの投影に最適な方向を取得するために、前記データ点と関連づけられた前記特徴ベクトルにカーネルフィッシャー線形識別関数を適用するカーネルフィッシャー線形識別関数モジュールとからなるシステム。
【請求項３１】
前記近傍グラフ生成モジュールは、
前記データ点間の距離を決定するステップと、
決定された前記距離に基づいて前記データ点は近傍点であるかを決定するステップと、
前記データ点が近傍点であると決定した場合は、決定された前記距離を前記近傍グラフのために選択するステップと、
前記データ点が近傍点でないと決定した場合は、無限大の数値を前記近傍グラフのために選択するステップとによって前記近傍グラフを生成することを特徴とする請求項３０のシステム。
【請求項３２】
前記データ点が近傍点であるかを決定するステップは、決定された前記距離に基づいて個々のデータ点の近いものから順番に所定の数のデータ点を前記の近傍点として選択することを特徴とする請求項３１のシステム。
【請求項３３】
前記データ点が近傍点であるかを決定するステップは、決定された前記距離に基づいて個々のデータ点から所定の半径内のデータ点を前記の近傍点として選択することを特徴とする請求項３１のシステム。
【請求項３４】
前記測地線距離予測モジュールは、前記近傍グラフ上の近傍データ点間をフロイド−ワーシャルアルゴリズムを用いた連続的な近距離接続で決まる距離によって、前記データ点間の測地線距離を近似することを特徴とする請求項３０のシステム。
【請求項３５】
前記カーネルフィッシャー線形識別関数モジュールは、
投影関数を用いて高次元の特徴空間へ前記特徴ベクトルを投影するステップと、
高次元の前記特徴空間へ投影した前記特徴ベクトルに対してカーネルフィッシャー顔を生成するステップと、
前記特徴ベクトルの個々のクラスタ内の変動を略最小化しながら、前記特徴ベクトル間の変動を略最大化するために、前記入力空間および前記カーネルフィッシャー顔に基づく前記高次元の特徴空間より低い次元の低次元空間へ前記特徴ベクトル投影するステップとによって、前記特徴ベクトルにカーネルフィッシャー線形識別関数を適用することを特徴とする請求項３０のシステム。
【請求項３６】
前記特徴ベクトルクラスタ間の前記変動は級間散布図行列によって表され、前記特徴ベクトルの個々のクラスタ内の前記変動は級内散布図行列によって表されることを特徴とする請求項３５のシステム。
【請求項３７】
前記級間散布図行列の前記級内散布図行列に対する比率を略最大化するように、前記特徴ベクトルは前記低次元空間へ投影されることを特徴とする請求項３６のシステム。
【請求項３８】
前記画像は顔画像または数字画像であることを特徴とする請求項３０のシステム。
【請求項３９】
2005535017.tif 000013
【請求項４０】
コンピュータが読み込み可能な媒体上に保存され、パターン分類のための画像セットを表すコンピュータプログラム製品であって、
入力空間の前記画像セットに対応するデータ点を受け取るステップと、
前記データ点が近傍点であるかを示す近傍グラフを生成するステップと、
前記近傍グラフに基づいて前記データ点間の測地線距離を予測するステップと、
他のデータ点までの前記測地線距離に対応する関連特徴ベクトルによって個々の前記データ点を表すステップと、
パターン分類のための前記特徴ベクトルの投影に最適な方向を取得するために、前記データ点と関連づけられた前記特徴ベクトルにフィッシャー線形識別関数を適用するステップとからなる方法を実行するコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にパターン分類、より具体的には線形識別関数またはカーネルフィッシャー線形識別関数を用いた拡張Ｉｓｏｍａｐによるパターン分類のための画像表示に関する。
【背景技術】
【０００２】
本発明の背景
パターン分類（パターン認識としても知られている）は多方面で適用可能なため近年ますます着目されている。顔の画像分類を含む顔認識技術は、監視、警備、宣伝その他に適用することができる。
【０００３】
パターン分類には、データ点が分類対象の画像またはパターンに対応している入力空間内で、データ点を分類することが含まれる。データ点は一般に入力空間内の複素多様体上にあり、パターン分類はデータ点がどの程度参照画像に対応する参照データ点に近接するかを決定することにより実施される。例えば、顔の認識において、顔の画像は一般に２次元Ｎ×Ｎの強度値の配列であり、個々の顔の画像はＮ2次元の入力空間におけるＮ2次元のベクトルとして入力空間において表すことができる。顔画像の１セットはＮ2次元の入力空間におけるデータ点（ベクトル）の１セットに対応し、データ点は一般にＮ2次元の入力空間における複素多様体を構成する。顔認識には、顔画像に対応するデータ点が参照顔画像に対応するデータ点にどの程度近づいているかを決定することが含まれる。
【０００４】
データ点が相互にどの程度近接しているか、およびデータ点がパターン分類のための入力空間における参照データ点にどの程度近接しているか決定するために、多様体の特性が考慮される。即ち、入力空間におけるデータ点間の測地線距離（多様体の表面に沿う距離メトリクス）がデータ点同士の近接の程度を決定するために用いられるべきである。なぜなら、測地線距離は基礎となる多様体の固有の表面形状を反映しているからである。
【０００５】
図１Ａは異なる級のデータ点が区別され影を施されたパッチで表されている複素多様体１００の例を示し、図１Ｂは図１Ａの複素多様体１００に示されたこれらの異なる級から抽出されたデータ点を示すダイアグラムである。図１Ａの複素多様体１００上の１対の点に対して、それらのユークリッド距離はそれらの固有の類似性を正確には反映しておらず、従ってパターン分類での使用には適さない。図１Ｂを参照して１例をあげると、２個のデータ点（例えば、ｘ1およびｘ2）間のユークリッド距離は３次元の入力空間では見かけ上小さくなることがある。しかしながら、固有の２次元多様体１００上ではこの２個のデータ点（ｘ1およびｘ2）間の測地線距離は大きい。従って、測地線距離が基礎の多様体１００の固有の表面形状を反映しているので、多様体上でデータ点（ｘ1およびｘ2）がどの程度近接しているかの決定には測地線距離が使用されるべきである。
【０００６】
近年Ｉｓｏｍａｐ法（「アイソメトリック特徴写像」としても知られている）と局所的線形埋め込み法（Ｌｏｃａｌｌｙ  Ｌｉｎｅａｒ  Ｅｍｂｅｄｄｉｎｇ：ＬＬＥ）が、単一のグローバルな座標系内で局所的な幾何学的距離を用いて複素多様体の固有の表面形状を知るために提案されている。従来のＩｓｏｍａｐ法はまず多様体上の個々のデータ点をその点に対して距離が近いものからｋ個の全ての点と結んだ近傍グラフ、または入力空間内の半径εに固定された範囲内の全ての点と結んだ近傍グラフを構築する。近傍の点に対しては入力空間のユークリッド距離は測地線距離に対して通常良い近似を与える。データ点の個々のペアに対して、近傍グラフにおいてそれらの点を結んだ最短距離が計算され、真の測地線距離の予測値として使用される。図１Ｂに示すように入力空間の多様体上のデータ点の個数が充分な場合は、これらの予測値は真の測地線距離に対して良い近似となる。次に、予測された多様体の固有の表面形状を最も良く保存する低次元の部分空間を構築するために従来の多次元スケーリング法が適用される。
【０００７】
局所的線形埋め込み（ＬＬＥ）法は、入力空間の近傍点から個々のデータ点を最適に近似する高次入力空間の線形係数のセットによって、複素埋め込み多様体の局所的形状特性を把握する。次にＬＬＥは再構築の経費を最小化しながら、入力空間の高次元データ点から計算された同一セットの係数を使用して、個々の点がその近傍点によって線形的に近似可能な低次元の点の１セットを見つける。
【０００８】
従来のＩｓｏｍａｐ法とＬＬＥ法は、他と比較して最低の再構築誤差でデータ点を最適に表す埋め込み多様体を検出する際には、許容できる結果を示したが、それらの画像の分類を促進する最適な方法で画像を表すことには失敗している。さらに、従来のＩｓｏｍａｐ法とＬＬＥ法では埋め込み多様体がうまく抽出されていると仮定されているが、一般的に個々の人物について利用できるサンプルは数個に限られているので、顔認識のようなある種の分類問題はこのような場合にあてはまらない。
【０００９】
従って、パターン分類が促進され、パターンに対応したデータ点からなる基礎の多様体の固有の表面形状が保存されるように、パターンを最適化して表す方法が必要である。
【発明の開示】
【００１０】
発明の要約
本発明はカーネルフィッシャー線形識別関数（ＫＦＬＤ）またはフィッシャー線形識別関数（ＦＬＤ）を用いて従来のＩｓｏｍａｐ法を拡張することによりパターン分類のための画像を表す方法を提供する。本発明の方法では、従来のＩｓｏｍａｐ法と同様に、パターン分類のための画像に対応するデータ点の測地線距離を予測し、ペアの測地線距離を特徴ベクトルとして用いる。本発明の一実施例によると、特徴ベクトルのクラスタ中心間の距離を最大化する最適投影方向を捜すためにＦＬＤを特徴ベクトルに適用する。
【００１１】
本発明の他の実施例では、特徴ベクトルのクラスタ中心間の距離を最大化する最適投影方向を捜すためにＦＬＤに代えてＫＦＬＤを特徴ベクトルに適用する。
【００１２】
本発明はまた、分類のためにフィッシャー線形識別関数またはカーネルフィッシャー線形識別関数を用いて従来のＩｓｏｍａｐ法を拡張することにより、パターン分類のための画像を表すシステムを提供する。本発明の一実施例によると本発明のシステムは、画像に対応するデータ点に対して近傍グラフを生成する近傍グラフ生成モジュール、データ点の測地線距離を予測する測地線距離予測モジュール、ペアの測地線距離に基づいて特徴ベクトルを生成するとともに特徴ベクトルのクラスタ中心間の距離を最大化するための最適投影方向を捜すために特徴ベクトルにＦＬＤを適用するＦＬＤ投影モジュールから構成される。
【００１３】
本発明の他の実施例によると、システムはＦＬＤモジュールに代えてＫＦＬＤモジュールを含み、ペアの測地線距離に基づいて特徴ベクトルを生成するとともに、特徴ベクトルのクラスタ中心間の距離を最大化する最適投影方向を捜すために特徴ベクトルにＦＬＤを適用する。
【００１４】
本発明はさまざまな形で実施が可能であり、コンピュータプログラム製品、方法、およびシステム、特定あるいは汎用の計算器または装置、オンラインサービスまたはシステム、ユーザーインターフェース装置およびその他が含まれる。
【発明を実施するための最良の形態】
【００１５】
実施形態の詳細説明
図２は本発明の第１の実施例による拡張Ｉｓｏｍａｐを用いたパターン分類のための画像を表す方法を示すフローチャートである。図２の拡張Ｉｓｏｐｍａｐ法はパターン分類のための画像を表すために従来のＩｓｏｍａｐ法と合わせてフィッシャー線形識別関数を用いる。
【００１６】
図２を参照すると、ステップ２０２で分類に供するサンプル画像のセットが入力空間で得られる。サンプル画像はベクトルで表されている。ｍ個のサンプル画像｛ｘ1，．．．，ｘm｝からなるセットがあり、個々のサンプル画像はｃ級｛Ｚ1，．．．．，Ｚc｝の１つに属すと仮定して、ステップ２０４でサンプル画像の近傍グラフが生成される。個々のサンプルｘiの近傍点は、入力空間Ｘの距離メトリクスｄX（ｘi，ｘj）に基づいて、サンプル画像に対応するデータ点のある低次元の多様体Ｍ上で決定される。そのような距離メトリクスは顔認識でよく利用されるユークリッド距離になり得る。そのような距離メトリクスは手書き数字の認識で有用性が示されているタンジェント距離にもなり得る。データ点が近傍点である場合は入力空間の２個のデータ点間の距離は測地線距離に対して良い近似を与える。このように、２個のデータ点が近傍点であるかないかを判断するために入力空間距離メトリクスが利用できる。
【００１７】
一実施例においては、近傍点を決定するために距離が近いものから順番にｋ個の近傍点を選ぶアルゴリズムを使用するｋ−Ｉｓｏｍａｐ法によって個々のサンプルｘiの近傍点が決定される。他の実施例では、所定の半径ε内の全てのデータ点を近傍点として含めるε−Ｉｓｏｍａｐ法によって個々のサンプルｘiの近傍点が決定される。
【００１８】
サンプル画像に対応するデータ点間の近傍関係は重み付けグラフＧで表され、
ｄG（ｘi，ｘj）＝ｄx（ｘi，ｘj）、ｘiとｘjが近傍点の場合
ｄG（ｘi，ｘj）＝∞、その他の場合・・・・・・・・・（１）
が成り立つ。
【００１９】
次に、ステップ２０６で多様体Ｍ上のデータ点で構成するペアの全てに対してペア間の測地線距離ｄM（ｘi，ｘj）が予測される。離れたデータ点のペアに対しては、近傍データ点間の近距離接続を連続することによって測地線距離が近似できる。換言すれば、測地線距離ｄM（ｘi，ｘj）は重み付きグラフＧ上でデータ点ｘiおよびｘj間の最短距離によって近似され、フロイド−ワーシャルアルゴリズムを用いて次式で計算される。
ｄM（ｘi，ｘj）＝ｍｉｎ｛ｄG（ｘi，ｘj）， ｄG（ｘi，ｘk）
＋ｄG（ｘk，ｘj）｝，ｋ≠ｉ，ｊ・・・・・・・・・（２）
いずれの２個のデータ点に対してもその間の最短距離はＤij＝ｄM（ｘi，ｘj）の行列Ｄで表現される。
【００２０】
次に、ステップ２０８でサンプル画像に対応する個々のデータ点が他の全ての点に対する測地線距離の特徴ベクトルによって表され、ステップ２０８で分類のための最適投影方向を捜すために特徴ベクトルにフィッシャー線形識別関数が適用される。フィッシャー線形識別関数はサンプル画像の分類が促進されるようにできるだけ級中心が分離される低次元空間の部分空間を決定する。データ点ｘiに対応する特徴ベクトルはｍ−１次元のベクトルｆi＝[Ｄij]で、ｊ＝１，．．．，ｍ  ｊ≠ｉである。
【００２１】
2005535017.tif 000003
【００２２】
従来のＩｓｏｍａｐ法および本発明の拡張Ｉｓｏｍａｐ法に要求される記憶領域および計算の複雑性の原因に対しては、データ点間の最短距離の計算が支配的である。フロイド−ワーシャルアルゴリズムは直接的な実行をするために、Ｏ（ｍ3）の実行を必要とし、Ｏ（ｍ2）の予測された測地線距離要素を保存する。一方、従来のＩｓｏｍａｐ法で用いられている多次元スケーリング（ＭＤＳ）は、データ点間に認められた類似性または相違点（距離）を説明する有意な基礎となる次元を見つけるための反復処理の結果、時間が掛かることがある。近傍グラフｄG（ｘi，ｘj）はデータ点数が増すに従い、固有の測地線距離ｄM（ｘi，ｘj）のより良い予測を可能にする。実際には、充分な個数のサンプルが無いことがあるので、測地線距離ｄG（ｘi，ｘj）は固有の測地線距離の良好な近似とはならない可能性がある。このようにして、従来のＩｓｏｍａｐ法はデータ点から固有の次元数を見つけられなくて、パターン分類の目的には適さないことがある。
【００２３】
対照的に、拡張Ｉｓｏｍａｐ法は散布図中心間の距離（即ち低品位の近似は平均によって除外される）を利用するので、パターン分類に対しては良好な性能を発揮する。従来のＩｓｏｍａｐ法は埋め込み多様体の次元を見つけるためにＭＤＳを用いるが、本発明の拡張Ｉｓｏｍａｐ法では、部分空間の次元数は級の数（即ちｃ−１）によって決定される。これにより従来のＩｓｏｍａｐ法で要求される計算よりもはるかに簡単なパターン分類のための計算が可能になる。
【００２４】
パターン分類でよく遭遇する級内散布図行列Ｓwの特異点問題に対処するために、本発明の一実施例によると単位行列の倍数が級内散布図行列に追加され、Ｓw＋εＩ（εは小さな数値）が生成される。これによって固有値問題も数値的により安定化される。
【００２５】
図３は本発明の第２の実施例による拡張Ｉｓｏｍａｐを用いたパターン分類のための画像を表す方法を示すフローチャートである。線形的に分離不可能なデータセットに対してステップ２０８のＦＬＤの適用に代えてステップ３０８でカーネルフィッシャー線形識別関数（ＫＦＬＤ）を適用する。これはＫＦＬＤが概念的には、データ点を分離するための最適識別関数を計算するに先立ち、画像のより良い特徴を抽出するためにデータを入力空間から高次元の空間へ投影するからである。特徴ベクトルがステップ３０８でＦＬＤに代えてＫＦＬＤを使用して投影される点を除いて、図３の方法は図２に示された方法と同一である。
【００２６】
ＫＦＬＤ解析において、拡張Ｉｓｏｍａｐから得られる個々の特徴ベクトルｆ（ｆi＝［Ｄij］  ｊ＝１，．．．．，ｍ  ｊ≠ｉ）は、非線形写像関数（投影関数）を用いて入力空間Ｒnから高次元の特徴空間ＲFのΦ（ｆ）に投影される。
Φ：Ｒn→ＲF，Ｆ＞ｎ・・・・・・・・・・・・・・（７）
個々の特徴ベクトルｆiはＫＦＬＤに含まれる式を記述する際の便宜のために今後特徴ベクトルｆとして示す。高次元の特徴空間の次元Ｆは任意に大きく取ることが可能である。
【００２７】
具体的な投影関数の選択はデータと適用の性質に依存し、経験的に決定されることが多い。本発明に対しては多くの形の投影関数Φ（ｘ）を使用することが可能である。しかしながら、効率的且つ系統的な計算の実施に適する投影関数の数は限られている。固有の投影関数Φ（ｘ）を選択する１つの方法は、投影関数の点乗積を実際に計算するよりも、カーネル関数を用いて点乗積が効率的に計算可能な投影関数を選ぶことである。その理由は、高次元の特徴空間から低次元の顔画像空間へ特徴ベクトルを投影するための計算において、投影関数の演算が頻繁に使用され、計算として集約的であるからである。このようにして上記の方法は次の関係を満たすカーネル関数ｋ（ｘ，ｙ）を捜す。
ｋ（ｘ，ｙ）＝Φ（ｘ）・Φ（ｙ）・・・・・・・・・（８）
【００２８】
2005535017.tif 000004
【００２９】
投影関数（Φ（ｘ），Φ（ｙ））の厳密な形は選択したカーネル関数ｋ（ｘ，ｙ）によって完全に決まることに注目する。実際には、顔画像を高次元の特徴空間から低次元の顔画像空間へ投影するための計算に、投影されたサンプルの点乗積、Φ（ｘ）・Φ（ｙ）が使用されるだけならば、厳密な閉じた形式の投影関数を知る必要はない。この理由は、そのような投影を実行する代わりに計算上効率的な方法でカーネル関数ｋ（ｘ，ｙ）が使用できるからである。このように、カーネル関数を使用することの利点の一つは、ｎ次元の顔画像を、より富んだ特徴表示を提供するｆ次元の特徴空間（ｆはｎより格段に大きい）に、厳密な閉じた形式での投影関数を知ることなく投影できることである。
【００３０】
2005535017.tif 000005
【００３１】
2005535017.tif 000006
【００３２】
2005535017.tif 000007
【００３３】
2005535017.tif 000008
【００３４】
2005535017.tif 000009
【００３５】
2005535017.tif 000010
【００３６】
2005535017.tif 000011
【００３７】
図４は本発明の第１の実施例による拡張Ｉｓｏｍａｐを用いたパターン分類のための画像を表すシステム４００を示す。システム４００は近傍グラフ生成モジュール４０２、測地線距離予測モジュール４０４およびＦＬＤ投影モジュール４０６からなる。近傍グラフ生成モジュール４０２は分類のためのサンプル画像を受け取り、図２のステップ２０４に従ってサンプル画像に対応するデータ点の近傍グラフを生成する。測地線距離予測モジュール４０４は図２のステップ２０６に従って近傍グラフ上のデータ点間の測地線距離を予測する。ＦＬＤ投影モジュール４０６は、図２のステップ２０８に従って、近傍グラフ上の他のデータ点までの測地線距離に対応する特徴ベクトルによって個々のデータ点を表し、ＦＬＤをこの特徴ベクトルに適用する。その結果ＦＬＤ投影モジュール４０６は分類のために最適に投影されたサンプル画像を表す特徴ベクトルを出力する。
【００３８】
図５は本発明の第２の実施例による拡張Ｉｓｏｍａｐを用いたパターン分類のための画像を表すシステム５００を示す。システム５００は近傍グラフ生成モジュール５０２、測地線距離予測モジュール５０４およびＦＬＤ投影モジュール５０６からなる。近傍グラフ生成モジュール５０２は分類のためのサンプル画像を受け取り、図３のステップ３０４に従ってサンプル画像に対応するデータ点の近傍グラフを生成する。測地線距離予測モジュール５０４は図３のステップ３０６に従って近傍グラフ上のデータ点間の測地線距離を予測する。ＦＬＤ投影モジュール５０６は、図３のステップ３０８に従って、近傍グラフ上の他のデータ点までの測地線距離に対応する特徴ベクトルによって個々のデータ点を表し、ＫＦＬＤをこの特徴ベクトルに適用する。その結果ＦＬＤ投影モジュール５０６は分類のために最適に投影されたサンプル画像を表す特徴ベクトルを出力する。
【００３９】
２つのパターン分類問題、顔認識と手書き数字認識が、本発明の拡張Ｉｓｏｍａｐ法の性能を従来のＩｓｏｍａｐ法との比較においてテストするために考えられた。これらの２つの問題は興味深い特徴を有し、それぞれ異なった方針で解決される。正面位置の顔認識に対する外見準拠法では、個々の顔画像が同一性を提供し、通常全体として（全体論として）特に特徴を抽出することなくパターンとして扱われる。これとは別に、主要コンポーネント解析（Ｐｒｉｎｃｉｐａｌ  Ｃｏｍｐｏｎｅｎｔ  Ａｎａｌｙｓｉｓ：ＰＣＡ）やフィッシャー線形識別関数（Ｆｉｓｈｅｒ  Ｌｉｎｅａｒ  Ｄｉｓｃｒｉｍｉｎａｎｔ：ＦＬＤ）のような部分空間法は有意なまたは識別に寄与する特徴を内的に抽出するために適用され、認識のために低次元の部分空間へパターンを投影する。これとは逆に、分類のためにデシジョンサーフェースが誘導される前に、手書き数字画像には高度な特徴抽出手法が通常適用される。
【００４０】
公開の利用可能なデータベースから検索した第１の試験用顔画像セット、第２の試験用顔画像セットおよび第３の試験用手書き数字画像セットを用いて、本発明の拡張Ｉｓｏｍａｐは従来のＩｓｏｍａｐ、ＬＬＥ、固有顔（ＰＣＡ）およびフィッシャー顔（ＦＬＤ）法との比較によってテストされた。第１と第２の試験用顔画像セットはいくつかの特有の性質を持っている。第１の試験用顔画像セットは顔の輪郭を含みスケールとともに姿勢も変化するが、第２の試験用顔画像セットは眉、目、鼻、口および顎のような内部的な顔の構成を含むように切り取りと調整が施され、顔の輪郭は含んでいない。第１の試験用顔画像セットは充分に調整された照明条件下で取得されたが、第２の試験用顔画像セットは照明条件を変えた条件下で取得された。手書き数字認識問題については、本発明の拡張Ｉｓｏｍａｐの試験が、手書き数字画像からなる第３の試験用画像セットを用いて行われた。
【００４１】
図６は本発明の第１の実施例による拡張Ｉｓｏｍａｐ（従来のＩｓｏｍａｐにＦＬＤを使用）を用いたパターン分類のための画像を表す方法を、第１の試験用顔画像セットに適用して試験した結果を示すグラフである。第１の試験用顔画像セットには４０の対象物の４００画像が含まれている。計算の複雑さを低減するために、個々の顔画像は実験用として２３×２８にピクセル数が減じられた。個々の顔画像は強度値のラスタースキャンベクトルによって表され、その後強度値はゼロ平均単位分散ベクトルに正規化された。
【００４２】
テストは１個抜き法（ｍ倍のクロスバリデーション）を用いて実施された。１人の人物の画像を分類するために（ｍ−１）個の画像の訓練セットからその画像が取り除かれ、投影行列が計算された。訓練セットに含まれるｍ個全ての画像が低次元空間へ投影され、最も近傍の分類子に基づいて認識する方法が取られた。固有顔（ＰＣＡ）およびＬＬＥ法における主要コンポーネントの数などのパラメータは、個々の方法によって誤差率を最低にするように経験的に決められた。フィッシャー法（ＦＬＤ）および本発明の拡張Ｉｓｏｍａｐ法に対しては、全てのサンプルが、大きいほうから数えてｃ−１番目までの固有ベクトル（ｃは級の数）によって張られた部分空間へ投影された。
【００４３】
図６を参照すると、全ての顔認識方法の中で、半径を用いた拡張Ｉｓｏｍａｐ法（“Ｅｘｔ  Ｉｓｏｍａｐ（ｅ）”で表示）が最低の誤差率を達成できることが示され、著しいマージンでフィッシャー顔法（“ＦＬＤ”で表示）を凌駕し、他の方法（例えばＰＣＡおよびＬＬＤ）よりも性能が優れていることが分かる。拡張Ｉｓｏｍａｐの２つの実施形態（近傍のデータ点を決定するために、大きいほうからｋ番目までの近傍点を用いる方法（拡張ｋ−Ｉｓｏｍａｐ、“Ｅｘｔ  Ｉｓｏｍａｐ（ｎｅｉｇｈｂｏｒ）”で表示）と、ε半径を用いるもう１つの方法（拡張ε−Ｉｓｏｍａｐ、“Ｅｘｔ  Ｉｓｏｍａｐ（ｅ）”）で表示）は、これらの方法に対応する従来のＩｓｏｍａｐ法（“Ｉｓｏｍａｐ（ｎｅｉｇｈｂｏｒ）”と表示されているｋ−Ｉｓｏｍａｐおよび“Ｉｓｏｍａｐ（ｅ）”と表示されているε−Ｉｓｏｍａｐ）よりも、著しいマージンを有してパターン分類にける誤差率が低く優れた性能を示している。
【００４４】
図７は試験用顔画像の第２のセットに基づいて本発明の第１の実施例（従来のＩｓｏｍａｐと合わせてＦＬＤを使用）による拡張Ｉｓｏｍａｐを用いたパターン分類のための画像を表す方法の試験結果を示す。試験用顔画像の第２のセットは、顔の表情と照明の変化を含む１１の対象物の１６５の画像からなる。計算効率を上げるために個々の画像は２９×４１にピクセル数が低減された。同様に、個々の顔画像は正規化された強度値の中心化ベクトルによって表された。
【００４５】
テストは１個抜き法を用いて実施され、主要コンポーネントの数は固有顔（ＰＣＡ）およびＬＬＥ法に対して誤差率を最低にするように変更された。フィッシャー法（ＦＬＤ）および本発明の拡張Ｉｓｏｍａｐ法に対しては、大きいほうからｃ−１番目までの固有ベクトル（ｃは級の数）によって張られた部分空間へ、サンプルが投影された。
【００４６】
図７を参照すると、拡張Ｉｓｏｍａｐ法の２つの実施形態の両者（近傍データ点を決めるために大きいほうからｋ番目までの近傍点を用いる方法（“Ｅｘｔ  Ｉｓｏｍａｐ（ｎｅｉｇｈｂｏｒ）”で表示された拡張ｋ−Ｉｓｏｍａｐ）と、ε半径を用いるもう１つの方法（“Ｅｘｔ  Ｉｓｏｍａｐ（ｅ）”）で表示された拡張ε−Ｉｓｏｍａｐ）は、これらの方法に対応する従来のＩｓｏｍａｐ法（Ｉｓｏｍａｐ（ｎｅｉｇｈｂｏｒ）およびＩｓｏｍａｐ（ｅ））よりも、パターン分類にける誤差率が低く優れた性能を示している。さらに、拡張されたε−Ｉｓｏｍａｐ法（Ｅｘｔ  Ｉｓｏｍａｐ（ｅ））は、従来のＩｓｏｍａｐが試験用顔画像の第２のセットでは良い性能を示していないにもかかわらず、ほとんどフィッシャー顔法（ＦＬＤ、顔認識の方法としては最も優れた方法の１つ）と同程度の性能を示している。
【００４７】
図８Ａは従来のＩｓｏｍａｐ法によって投影された試験用顔画像の第２のセットのサンプル画像を示し、図８Ｂは本発明の第１の実施例による拡張Ｉｓｏｍａｐ法によって投影された試験用顔画像の第２のセットのサンプル画像を示す。図８Ａでは、試験用顔画像の第２のセットのサンプル画像が、従来のＩｓｏｍａｐ法で抽出された最初の２つの固有ベクトルに投影され、図８Ｂでは、試験用顔画像の第２のセットのサンプル画像が、本発明のＩｓｏｍａｐ法で抽出された最初の２つの固有ベクトルに、図２に示されるように投影された。異なる級の投影されたサンプルは、図８Ａに示すように、従来のＩｓｏｍａｐでは不鮮明であるが、本発明の拡張Ｉｓｏｍａｐ法によって投影されたサンプルは図８Ｂに示すように良好に分離されている。
【００４８】
図９は試験用の手書き数字画像の第３のセットに適用して、本発明の第１の実施例による拡張Ｉｓｏｍａｐ法を用いたパターン分類のための画像を表す方法のテスト結果を示すグラフである。試験用手書き数字画像の第３のセットは、訓練セット６０，０００例と試験セット１０，０００例を含んでいる。画像はアスペクト比を保ちながら正規化され、個々の画像はピクセルの質量中心を計算して、この質量中心を中心に配置するために画像変換した上で、２８×２８のグレースケールのウィンドウ中心に配置された。
【００４９】
計算上および記憶量の制約のために１，５００個の手書き数字画像からなる訓練セットが試験用手書き数字画像の第３セットから無作為的に選択され、重複を避けた２５０の画像からなる試験セットが試験用手書き数字画像の第３セットから無作為的に選択された。同じ試験が５回実施され、個々の実施において最低の誤差率が実現できるように試験パラメータを変更した。個々の画像は特徴抽出アルゴリズムを適用せずに強度値のラスタースキャンベクトルによって表された。
【００５０】
図９には、従来のｋ−Ｉｓｏｍａｐ法（“Ｋ−Ｉｓｏｍａｐ（ｎｅｉｇｈｂｏｒ）”と表示）、拡張ｋ−Ｉｓｏｍａｐ法（“Ｅｘｔ−Ｋ−Ｉｓｏｍａｐ（ｎｅｉｇｈｂｏｒ）”と表示）、従来のε−Ｉｓｏｍａｐ法（“Ｉｓｏｍａｐ（ｅ）”と表示）、および拡張ε−Ｉｓｏｍａｐ（“Ｅｘｔ  Ｉｓｏｍａｐ（ｅ）”と表示）のテスト結果の平均が示されている。図９に示すように、拡張Ｉｓｏｍａｐ法は対応する従来のＩｓｏｍａｐ法と比較して、試験用手書き数字画像の第３のセットを用いた実験でパターン認識に関する誤差率が低く、一貫して性能が勝っている。
【００５１】
方法およびシステムとして本発明の説明がなされたが、本発明の方法はコンピュータが読取可能ないかなる媒体に記録されたコンピュータプログラム製品としても実施が可能であることに注目すべきである。明細書で使用された言葉は読み易さと説明の目的に重点が置かれて選ばれており、本発明の主題を詳述および制限するために選ばれていないことに注意すべきである。従って、本発明の開示は請求項で明らかにされている本発明の範囲を制限するためではなくて、その説明を意図するものである。
【００５２】
関連出願の相互参照
本出願は３５Ｕ．Ｓ．Ｃ．§１１９（ｅ）に従い、２００２年７月２９日に出願され「パターン分類のための拡張Ｉｓｏｍａｐ」と題された同時係属中の米国仮特許出願Ｎｏ．６０／３９９、５０７に基づいて優先権を主張し、その主題の全てがここで参照されている。本願は２００２年７月２２日に出願され「カーネルフィッシャー顔を用いた顔認識」と題された同時係属中の米国特許出願Ｎｏ．１０／２０１、４２９にも関連している。
【図面の簡単な説明】
【００５３】
【図１Ａ】図１Ａは異なる級のデータ点が区別された影付きパッチで表されている複素多様体の１例を示す図である。
【図１Ｂ】図１Ｂは図１Ａの多様体に示された異なる級から抽出されたデータ点を示す図である。
【図２】図２は本発明の第１の実施例による拡張Ｉｓｏｍａｐを用いたパターン分類のための画像を表す方法を示すフローチャートである。
【図３】図３は本発明の第２の実施例による拡張Ｉｓｏｍａｐを用いたパターン分類のための画像を表す方法を示すフローチャートである。
【図４】図４は本発明の第１の実施例による拡張Ｉｓｏｍａｐを用いたパターン分類のための画像を表すシステムを示す図である。
【図５】図５は本発明の第２の実施例による拡張Ｉｓｏｍａｐを用いたパターン分類のための画像を表すシステムを示す図である。
【図６】図６は本発明の第１の実施例による拡張Ｉｓｏｍａｐを用いたパターン分類のための画像を表す方法を、試験用顔画像の第１のセットに基づいて試験を実施した時の結果を示すグラフである。
【図７】図７は本発明の第１の実施例による拡張Ｉｓｏｍａｐを用いたパターン分類のための画像を表す方法を、試験用顔画像の第２のセットに基づいて試験を実施した時の結果を示すグラフである。
【図８Ａ】図８Ａは従来のＩｓｏｍａｐ法によって投影されたサンプル画像を示すグラフである。
【図８Ｂ】図８Ｂは本発明の第１の実施例による拡張Ｉｓｏｍａｐ法によって投影されたサンプル画像を示すグラフである。
【図９】図９は本発明の第１の実施例による拡張Ｉｓｏｍａｐを用いたパターン分類のための画像を表す方法を、試験用顔画像の第３のセットに基づいて試験を実施した時の結果を示すグラフである。
【図１Ａ】
2005535017.tif 000014
【図１Ｂ】
2005535017.tif 000015
【図２】
2005535017.tif 000016
【図３】
2005535017.tif 000017
【図４】
2005535017.tif 000018
【図５】
2005535017.tif 000019
【図６】
2005535017.tif 000020
【図７】
2005535017.tif 000021
【図８Ａ】
2005535017.tif 000022
【図８Ｂ】
2005535017.tif 000023
【図９】
2005535017.tif 000024
【国際調査報告】
2005535017.tif 000025
2005535017.tif 000026