(57)【特許請求の範囲】
【請求項１】
ユーザー登録の方法であって：
諸ユーザーの諸ピクチャーのシーケンスにアクセスする段階と；
ユーザー間の区別をするユーザーの物理的特徴に対応する画像を、諸ピクチャーの前記シーケンスから検出する段階と；
前記検出された画像を使って距離メトリックを決定する段階であって、前記距離メトリックは、類似したサンプル対の距離と画像の非類似のサンプル対の距離の間のマージンを最大化するものであり、該距離メトリックを決定する段階は：
点間のある距離をもつ前記画像中の複数対の点を同定する段階であって、一対の点(xi,xj)の間の距離dA(xi,xj)は距離メトリックAに基づいて
【数１】
0005792320.tif 000018
として定義される、段階と；
前記距離メトリックAの正則化関数を選択する段階と；
前記複数対の点の間の距離dAに対する一組の制約条件に従って前記正則化関数を最小化して、前記正則化関数の第一の値を得る段階であって、前記一組の制約条件が、前記距離メトリックが半定値であること；前記同定された類似対の距離が第一の非負の値以下であること；および前記同定された非類似対の距離が第二の非負の値以上であることを含む、段階と；
前記距離メトリックAを、前記正則化関数の、前記第一の値以下である値を達成するものを見出すことによって決定する段階とを含む、段階と；
前記距離メトリックを使って計算された前記距離に基づいて前記画像をクラスタリングする段階と；
クラスタリング結果に基づいてユーザーを登録する段階とを含む、
方法。
【請求項２】
検出された画像が顔画像である、請求項１記載の方法。
【請求項３】
検出された画像の類似対が同じ人物の二つの検出された画像からなる、請求項１記載の方法。
【請求項４】
検出された画像の非類似対が二人の異なる人物の二つの検出された画像からなる、請求項１記載の方法。
【請求項５】
ユーザー登録を更新する方法であって：
諸ユーザーの諸ピクチャーのシーケンスにアクセスする段階と；
前記諸ピクチャーのシーケンスから画像を検出する段階であって、前記画像はユーザー間の区別をするユーザーの物理的特徴に対応する、段階と；
検出された画像の間で制約条件を識別する段階と；
既存の距離メトリックを使って計算された距離に基づいて前記画像をクラスタリングする段階であって、前記距離メトリックは、類似したサンプル対の距離と画像の非類似のサンプル対の距離の間のマージンを最大化するものであり、該距離メトリックの決定は：
点間のある距離をもつ前記画像中の複数対の点を同定する段階であって、一対の点(xi,xj)の間の距離dA(xi,xj)は距離メトリックAに基づいて
【数２】
0005792320.tif 000019
として定義される、段階と；
前記距離メトリックAの正則化関数を選択する段階と；
前記複数対の点の間の距離dAに対する一組の制約条件に従って前記正則化関数を最小化して、前記正則化関数の第一の値を得る段階であって、前記一組の制約条件が、前記距離メトリックが半定値であること；前記同定された類似対の距離が第一の非負の値以下であること；および前記同定された非類似対の距離が第二の非負の値以上であることを含む、段階と；
前記距離メトリックAを、前記正則化関数の、前記第一の値以下である値を達成するものを見出すことによって決定する段階とを含む、段階と；
前記クラスタリングの結果を前記識別された制約条件を用いて検証する段階と；
前記クラスタリングの結果および検証結果に基づいてユーザー登録を更新する段階とを含む、
方法。
【請求項６】
検出された画像が顔画像である、請求項５記載の方法。
【請求項７】
制約条件を識別する前記段階が、検出された画像の類似対および検出された画像の非類似対を識別することを含む、請求項５記載の方法。
【請求項８】
検出された画像の類似対が同じ人物の二つの検出された画像からなる、請求項７記載の方法。
【請求項９】
検出された画像の非類似対が二人の異なる人物の二つの検出された画像からなる、請求項７記載の方法。
【請求項１０】
前記検証する段階において前記制約条件が満たされる場合、前記更新する段階はさらに、新たにクラスタリングされた画像を追加することによってユーザー登録を更新することを含む、請求項５記載の方法。
【請求項１１】
前記検証する段階において前記制約条件が満たされない場合、前記更新する段階はさらに：
前記識別された制約条件を加えることによって距離メトリックを学習する段階と；
前記学習された距離メトリックを使って計算された距離に基づいて前記画像および既存の画像をクラスタリングし直す段階と；
前記クラスタリングし直した結果および前記学習された距離メトリックを使ってユーザー登録を更新する段階とを含む、
請求項５記載の方法。
【請求項１２】
前記距離メトリックの正則化関数がフロベニウス・ノルムである、請求項１記載の方法。
【請求項１３】
前記正則化関数の前記第一の値が極小値である、請求項１記載の方法。
【請求項１４】
点の類似対および点の非類似対を同定する段階をさらに含む、請求項１記載の方法。
【請求項１５】
一組の余裕変数を選択する段階をさらに含み、前記一組の余裕変数は、前記最小化において最小化される組み合わせ関数を通じて前記正則化関数と組み合わされる、請求項１記載の方法。
【請求項１６】
点の類似対および点の非類似対を同定する段階をさらに含む、請求項１５記載の方法。
【請求項１７】
前記余裕変数が非負である、請求項１６記載の方法。
【請求項１８】
前記最小化が半正定値計画法により実行される、請求項１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特に顔登録（face  registration）の技術に関わる、顔認識およびメトリック学習（metric  learning）の分野に関する。
【背景技術】
【０００２】
器具など家庭における諸システムを制御する伝統的な方式は、手動でシステムを所望のモードに設定することによる。ユーザーがインターフェースをもつシステムが自動的に制御されるとなれば魅力的だろう。テレビのようなシステムについては、ユーザーは、自分が最もよく見たテレビ・チャンネルまたはテレビ番組種別についてのユーザー選好を学習する機構をもつことを好むであろう。そうすれば、ユーザーがテレビの前に現れたとき、対応する設定が自動的にロードされる。
【０００３】
ユーザー認識は過去数十年においてコンピュータ技術のホットな領域であり続けてきた。顔認識、ジェスチャー認識などである。顔認識を例に取ると、伝統的な登録プロセスは通例込み入っている。ユーザーは自分のIDを入力する必要があり、一方、多数の顔画像が、ある種の照明環境および顔を見る固定した角度などのあらかじめ定義された条件のもとで撮影される。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Paul  Viola  and  Michael  Jones,  "Robust  Real-Time  Face  Detection",  International  Journal  of  Computer  Vision,  Vol.  57,  pp.  137-154,  2004
【非特許文献２】J.  L¨ofberg,  "Yalmip:  A  toolbox  for  modeling  and  optimization  in  MATLAB",  Proceedings  of  the  CACSD  Conference,  Taipei,  Taiwan,  2004
【非特許文献３】Shai  Shalev-Shwartz,  Yoram  Singer,  and  Nathan  Srebro,  "Pegasos:  Primal  estimated  sub-gradient  solver  for  svm",  ICML,  pp.  807-814,  2007
【発明の概要】
【発明が解決しようとする課題】
【０００５】
あらゆるユーザー画像は高次元空間におけるベクトルである。それらをユークリッド・メトリックに従って直接的にクラスタリングすることは、望ましくない結果につながることがある。一人の人物の諸ユーザー画像の分布は球状ではなく、層状だからである。異なる条件のもとでの同じ人物の二つの画像の間の距離は、同じ条件のもとでの異なる人物の間の距離よりも大きくなる可能性が高い。この問題を解決するためには、適正なメトリックを学習することが決定的に重要になる。
【０００６】
ビデオ源において、画像のいくつかの有用なペアごとの（pair-wise）制約条件があり、それがメトリックを学習するようシステムをトレーニングする助けとなりうる。たとえば、二つの近いフレームから捕捉された二つのユーザー画像は同じ人物に属し、一つのフレームから捕捉された二つのユーザー画像は異なる人物に属する。それら二種類のペアごとの制約条件は、類似対制約条件および非類似対制約条件である。ペアごとの制約条件のもとでメトリックを学習することの問題は、半教師ありメトリック学習と呼ばれる。伝統的な半教師ありメトリック学習の主たる発想は、非類似サンプル対の距離を厳しく制約しつつ、類似サンプル対の距離を最小化することである。類似サンプル対および非類似サンプル対の扱いが対称的でないので、この方法は制約条件の数に対して堅牢ではない。たとえば、非類似対の数が類似対の数よりはるかに大きいと、非類似サンプル対の制約条件がゆるくなりすぎて十分な相違ができず、この方法は良好なメトリックを見出すことができない。別の距離メトリック学習方法では、最大化されるべき真のオブジェクトは、マージンの幅ではなく、二つのクラスの距離の境界値（interface  value）である。これは、より小さな距離値をもつクラスの最大距離と、より大きな距離値をもつ他方のクラスの最小距離の中間値（middle  value）である。マージンの幅のほうは、前記二つのクラスの前記最大距離と前記最小距離の間の差である。このように、システムは堅牢ではない。
【課題を解決するための手段】
【０００７】
本発明は、システムとの対話のユーザー選好を解析することができ、ユーザーがシステムと対話し、ユーザーの画像が検出されてユーザー画像データベースにマッチするときにユーザーの前記選好を自動的に取り出すことができるユーザー・インターフェースを記述する。本ユーザー・インターフェースは、システムのユーザーの物理的な特徴に対応する画像のデータベースを有する。ユーザーの物理的な特徴は、システムのユーザー間の区別をする。ユーザーがシステムとインターフェースをもつときにユーザー画像を捕捉するためにビデオ装置が用いられる。選好解析器が、システムとのユーザー対話に基づいてシステムのユーザー選好を収集し、該選好を分離して、システムの各ユーザーに対応する個別ユーザー選好の集合を生成する。分離されたユーザー選好は選好データベースに格納され、相関器を通じて、画像のデータベース中の画像に基づいて、システムのユーザーと相関付けされる。相関器は、システムのある特定のユーザーがシステムとインターフェースをもつときにビデオ装置によって捕捉された、システムの前記特定のユーザーに関係した個別ユーザー選好を適用する。
【０００８】
本発明はさらに、ユーザーを画像データベース中に登録するユーザー登録方法を含む。本発明のある実施形態では、諸ユーザーの諸ピクチャーのシーケンスがアクセスされ、それから、ユーザー間の区別をするユーザーの物理的特徴に対応する画像が検出される。前記検出された画像を使って距離メトリックが決定され、前記距離メトリックを使って計算された距離に基づいて前記画像がクラスタリングされる。クラスタリング結果はユーザーを登録するために使われる。
【０００９】
本発明のもう一つの実施形態は、ユーザー登録を更新する方法であって、諸ユーザーの諸ピクチャーのシーケンスにアクセスする段階と；前記諸ピクチャーのシーケンスから画像を検出する段階であって、前記画像はユーザー間の区別をするユーザーの物理的特徴に対応する、段階と；検出された画像の間で制約条件を同定する段階と；既存の距離メトリックを使って計算された距離に基づいて前記画像をクラスタリングする段階と；前記クラスタリング結果を前記同定された制約条件を用いて検証する段階と；前記クラスタリング結果および検証結果に基づいてユーザー登録を更新する段階とを含む、方法を提供する。
【００１０】
本発明のもう一つの実施形態は、距離メトリックAを決定する方法であって：点間のある距離をもつ複数対の点(xi,xj)を同定する段階であって、前記距離dAは距離メトリックAに基づいて
【数１】
0005792320.tif 000002
として定義される、段階と；前記距離メトリックAの正則化関数（regularizer）を選択する段階と；前記複数対の点の間の距離dAに対する制約条件の集合に従って前記正則化関数を最小化して、前記正則化関数の第一の値を得る段階と；前記距離メトリックAを、前記正則化関数の、前記第一の値以下である値を達成するものを見出すことによって決定する段階とを含む、方法を提供する。
【図面の簡単な説明】
【００１１】
本発明の上記の特徴は、付属の図面を参照してその例示的な実施形態に詳細に記述することによってより明白となるであろう。
【図１】本発明に基づくユーザー・インターフェースを示すブロック図である。
【図２】本発明に基づく顔登録プロセスを示すフローチャートである。
【図３】入力ビデオ・セグメントに基づいて顔画像データベースを構築するプロセスを示すフローチャートである。
【図４】入力ビデオ・セグメントに基づいて顔画像データベースを更新するプロセスを示すフローチャートである。
【図５】本発明に基づく、RFIDラベルを使ってビデオ・セグメントをマージすることを示す図である。
【図６】RFIDラベルが利用可能なときの顔登録プロセスを示すフローチャートである。
【図７】本発明のある好ましい実施形態に基づく顔登録プロセスを示すフローチャートである。
【図８】発明されたMMMLメトリック学習方法のパフォーマンスを示す結果である。
【発明を実施するための形態】
【００１２】
本発明は、物理的特徴認識および登録機構に基づいてユーザー１０の選好に従ってサービスをユーザー１０に対してカスタマイズするシステムである。それは、ユーザー間の区別をすることができる顔、ジェスチャーなどといったものである。カスタマイズは好ましくは、後述するように透明に達成される。図１は、ユーザー１０がインターフェースをもつシステムの例としてテレビを使い、物理的な特徴の例として顔を使うシステムを示している。カメラのようなビデオ装置３０が作業環境中に、たとえば居間のテレビ・セット２０の上に設置され、カメラ３０に対する位置または角度などといったユーザーに対する制約なしに、ユーザーが当該システムとインターフェースをもつときにユーザーの画像を捕捉するようにされる。ユーザーの画像データベース４０を構築するよう、各ユーザーについての顔画像がビデオから抽出され、各ユーザーに登録される。選好解析器９０は、ユーザーが当該システムと対話しているときに、ユーザーのお気に入りのチャンネル、好まれる映画ジャンルといった当該システムに対するユーザー選好を収集し、それらの選好を分離して、当該システムの各ユーザーに対応する個々のユーザー選好の集合を生成する。収集されたユーザー選好は選好データベース５０に記憶される。相関器６０はユーザー選好データベース５０と画像データベース４０を、個々の各ユーザーについての画像をそのユーザーの対応する選好集合にマッピングすることによって、リンクする。あるユーザーの新たに捕捉された画像がはいってくると、その画像は、画像データベース４０に登録され、次いで対応するユーザーの選好データを取得するよう相関器６０がトリガーされ、そのデータが次いで自動セットアップのためにシステムに送られる。この登録プロセスおよびデータベース構築プロセスを容易にするためにメトリック学習モジュール７０が用いられる。捕捉されたユーザー画像が画像データベースにとって新規である、つまり新規ユーザーであれば、更新器８０は画像データを更新し、そのユーザーの選好を構築し、選好データベース５０に記憶するよう、選好解析器９０を開始する。相関器６０は、選好プロファイルをユーザーとリンクするために用いられる。
【００１３】
図２は、顔を例示的な特徴として使う特徴登録２００の方法のある実施形態を示している。当業者は、このプロセスは顔に制約されるものではなく、他の任意の特徴にも適用可能であることを認識するであろう。本発明の利点は、特徴登録プロセスがユーザーにとって透明であるということである。ユーザーが自分のIDを入力する必要があり、照明および顔を見る角度などのある種の条件のもとでいくつかの顔画像を撮影される伝統的な顔登録プロセスとは異なり、ある好ましい実施形態は、ビデオ源から直接的に顔画像を抽出し、抽出された顔画像に基づいて登録に取り組む。そのようなプロセスを容易にするため、ビデオ源は好ましくは最初に処理される。ある好ましい実施形態では、ビデオはセグメントに分割される。各セグメントは、たとえば同じ諸ユーザーをもち類似した条件下にある、類似した相続くフレームからなる。ビデオをセグメント分割することによって、あるセグメントに現れるユーザーが高度に関係していることが保証され、このことはのちに示すように、画像の類似対および非類似対を識別するプロセスを簡単にする。登録プロセスはユーザーにとって透明なので、セグメント分割は自動的に行われるべきである。よって、セグメント分割プロセスにおいてシーン検出のような方法を用いることができる。同じ人物または異なる人物に属する二枚の画像のような、ユーザーの間の関係が保証できるのは、この実施形態では一つのセグメント内においてのみであるので、登録プロセスはセグメントごとになされる。システムが始動するときは、画像データベースは空である。よって、データベースを構築するプロセスが実行される。のちには、任意のはいってくるビデオ・シーケンスについて、データベース更新が必要とされるだけである。
【００１４】
入力ビデオ・シーケンスがビデオ・アクセス・ステップ２１０において、たとえばビデオ装置３０から得られ、ビデオ・セグメント分割ステップ２２０において、たとえばシーンの切れ目に基づいてセグメントに分割される。それにより、各ビデオ・セグメントは、少なくとも一人の人物の顔を含む相続くフレームからなることになる。ステップ２３０で取得されたセグメントのそれぞれについて、画像データベースが空かどうかの条件２３５が検証される。条件２３５が満たされる場合、すなわち現在のセグメントが処理されている時点で画像データベースが空である場合、ステップ２５０により、現在のセグメントに基づいて、画像データベースが構築される。そうでない場合には、データベースは次のステップ２４０で更新される。ステップ２３５、２４０および２５０は、条件２５５が満たされるまで、すなわちそれ以上ビデオ・セグメントがなくなるまで、繰り返される。登録プロセスはステップ２６０で停止する。
【００１５】
画像データベース２５０を構築する諸ステップは、図３においてより詳細に示されている。ある入力ビデオ・セグメントについて、顔抽出が実行される。抽出された顔画像から、ペアごとの制約条件が同定される。ある好ましい実施形態では、類似対制約条件および非類似対制約条件が使われる。類似対制約条件は、同じ人物の二つの顔画像として同定される；非類似対制約条件は、二人の異なる人物の二つの顔画像として同定される。ステップ２２０はビデオを一貫する相続く諸フレームにセグメント分割したので、一つのセグメントは人物の同じグループを含んでいる可能性が非常に高い。よって、類似および非類似制約条件は、比較的簡単に同定されることができる。たとえば、一つのフレームに属する二つの顔画像は、異なる人物に属するはずなので、非類似対として同定される。二つの相続くフレームにおいて類似した位置にある顔画像は類似対として同定される。一般に、同じ人物の顔画像はあるフレームから次のフレームにかけてあまり有意には動かないであろうからである。顔画像とともに同定された制約条件は、メトリックを得るためのメトリック学習機構に入力される。そのようなメトリックを使って、顔画像が諸クラスにクラスタリングできる。各クラスが各ユーザーに対応するのである。ここでメトリック学習が使われる理由は、あるシナリオにおいてクラスタリングのために使われる一つのメトリックは異なるシナリオでは満足いくものでないことがあるからである。たとえば、一人の人物の顔画像の分布は球状ではなく、層状である。ユークリッド距離が使われる場合、異なる条件下での同じ人物の二つの画像間の距離は、まず、同じ条件下での異なる人物間の距離より大きくなる。この問題を克服するため、適正なメトリックを学習することが決定的に重要である。さまざまなメトリック学習方法がこのステップにおいて使用できる。本発明のある好ましい実施形態では、最大マージン・メトリック学習（MMML:  Maximum  Margin  Metric  Learning）方法が用いられる。MMMLについての詳細についてはのちに論じる。ひとたび学習メトリックが得られると、クラスタリングを実行してクラスターを生成することができる。各クラスターは、データベースにおいて、各ユーザーの識別情報をもってマークされる。
【００１６】
図３では、まずビデオ・セグメント・アクセス・ステップ３１０が実行されてビデオ・シーケンス３１５が得られる。顔検出ステップ３２０が用いられて、ビデオ・セグメント３１５から顔画像３２５が検出される。例示的な顔検出方法は非特許文献１に見出すことができる。検出された顔画像３２５から、ステップ３３０において、顔画像の類似対および顔画像の非類似対が制約条件３３５として識別される。顔画像３３５の類似対および非類似対に対する識別された制約条件は次いで、距離メトリックを得るためのメトリック学習ステップ３４０に入力される。距離メトリック３４５を得たら、クラスタリング・ステップ３５０が用いられて、顔画像３２５に対してクラスタリングが実行され、顔画像がそれぞれ一人の人物を表すいくつかのクラスターにグループ分けされ、入力ビデオ中の個々の各ユーザーが識別される。顔画像、クラスタリング結果、距離メトリックおよび他の必要な情報はステップ３６０においてデータベースに記憶される。
【００１７】
図４は、新しい入力ビデオ・セグメントに基づいて既存のデータベースを更新するプロセス４００を示している。ビデオ・シーケンス４１５が得られたのち、ビデオ・シーケンス４１５中の顔画像を生成するために顔検出ステップ４２０が開始される。好ましくは、既存のデータベースがすでにその距離メトリックを以前の諸ビデオ・セグメントから学習している。そのようなシナリオでは、まずそのメトリックが、検出された顔画像に対してクラスタリングを実行するために利用される。すなわち、検出された顔画像４２５が、既存のデータベースからの距離メトリック４４４に基づくクラスタリング・ステップ４５０に入力される。そのメトリックは当該システムが遭遇したことのある以前の諸ビデオ・セグメントから学習されたものなので、既存のメトリック学習が考慮に入れていない新たな側面／制約条件を導入することがありうる現在のセグメントについては、有効でないことがありうる。したがって、生成されたクラスター４５２は条件チェッカー４５５に入力される。検証されるべき条件は、ステップ４３０で識別された制約条件４３５が現在のセグメントについて画像の類似対および非類似対としてである。４５５において条件が満たされれば、データベースにおいて新たなクラスターは更新されて、プロセスはステップ４６０で完了する。満たされなければ、現在のビデオ・セグメントの特性を取り込まず、既存のメトリックは更新される必要がある。よって、識別された制約条件４３５、データベースからの既存の制約条件、既存のデータベースからの顔画像４４２および新たな顔画像４２５に基づいてメトリックを再学習するために、メトリック学習ステップ４７０が開始される。ステップ４７０から学習された新たな距離メトリック４７５は次いでクラスタリング４８０を実行するために使われ、その結果がデータベースにおいて、新たな距離メトリックとともに更新される。ある好ましい実施形態では、MMMLメトリック学習方法が用いられる。その詳細はのちに開示する。
【００１８】
家庭環境中などの異なる実施形態では、ユーザーはRFIDデバイスまたは他の無線接続器（connectors）を携行することができ、それにより取り込まれたビデオには、検出されたRFIDラベルが関連付けられる。すなわち、あるRFIDまたは複数のRFIDが検出され、ある時間期間内の諸フレームに関連付けられる。RFIDラベルは、ステップ２２０において生成された諸セグメントを組み合わせることにおいて有用でありうる。各セグメントは、相続くフレームの一貫した集合である。しかしながら、異なるセグメント間では、そのような関係は保証されないまたは識別しがたいとはいえ、存在することがありうる。結果として、抽出された制約条件は孤立したものとなり、メトリック学習の劣ったパフォーマンスのもとになりうる。それらのセグメントを組み合わせ、それらの制約条件を結び付けることによって、メトリック学習の精度が改善できる。RFIDラベルは、セグメントを組み合わせるそのような機構を提供する。たとえば、図５のＡに示されるように、ビデオ・シーケンスはシーンに基づいて三つのセグメントにセグメント分割される。ここで、セグメント１および３はユーザーＡおよびＢがいるフレームであり、一方、セグメント２はユーザーＣのみを含む。セグメント１および３においてユーザーＡおよびＢについてRFIDラベルが存在している場合、セグメント１および３を併合して新たなセグメント１とすることが可能である。RFID検出から、どちらのセグメントもユーザーＡおよびユーザーＢを含んでおり両者が高度に関係していることがわかっているからである。同様に、図５のＢに示されるように、捕捉の際の照明条件変化のため二つのセグメントにセグメント分割されているビデオ・シーケンスが、RFIDラベル情報を使うことによって、一つのセグメントとして識別されることになる。RFIDラベル情報はセグメントの数を減らし、よって図２におけるループの数を減らし、より高速な顔認識プロセスにつながる。本システムでは、RFIDラベルは単にセグメントを組み合わせるためのブリッジのはたらきをしている。ユーザーがRFIDカードをビデオ撮影期間全体にわたって携行することは要求されない。
【００１９】
RFIDラベル情報は、ステップ３３０および４３０において識別される類似対および非類似対制約条件を洗練するためにも使うことができる。先述した自動的方法を使う識別プロセスの好ましい実施形態では、類似対とマークされている顔画像について、その対の一方の顔画像が他方の顔画像と異なるRFIDラベルをもつ場合、その対は非類似対とマーク付けし直される。同様に、非類似対の二つの顔画像が同じRFIDラベルをもつ場合には、この対は、類似対とマーク付けし直される。すべてのユーザーがRFIDデバイスを携行してはいない場合には、RFIDラベルが対応するユーザーと関連付けされる必要がある。顔画像の数の変化についての情報が、そのような目標を達成するために使用できる。たとえば、あるフレームにおいて二つの顔があり一つのRFIDカードしか検出されない場合、それは一人のユーザーだけがこのRFIDカードを携行していることを示している。さらに、次のフレームにおいて一つの顔だけが検出される場合、RFIDカード検出の結果に基づいて、現在の一つの顔がRFIDカードに関連付けられているかどうかが判定される。RFIDカードがいまだに検出できる場合には、現在の顔はそのRFIDカードと関連付けされる。そうでない場合には、前のフレームにおける他方の顔がRFIDカードと関連付けされる。ある好ましい実施形態によれば、これはフィードバック・リンクと称される。この種のリンクはシステムが類似対および非類似対制約条件の知識の収集を向上させるのを支援することができる。
【００２０】
顔登録プロセスの修正されたフローチャート６００が図６に示されている。RFID検出および関連付けステップ６３０が実行されて、RFIDラベルおよびそのビデオ・フレームとの対応についての情報が得られる。RFIDラベル情報６３５を用いて、ビデオ・セグメントの併合ステップ６４０が実行されて、関係しているビデオ・セグメントをより大きなビデオ・セグメントに組み合わせる。登録システムは次いで、組み合わされたビデオ・セグメントに基づいて、セグメントごとに処理していく。RFIDラベル６３５はデータベース構築ステップ６７０および更新ステップ６６０においても使用される。ここで、RFIDラベル３７０および４９０が、類似および非類似制約条件識別プロセス３３０および４３０を容易にするために使われる。
【００２１】
本発明のもう一つの実施形態では、ビデオ・シーケンスに対する顔登録プロセスは図７に従って実施される。ここで、諸ビデオ・セグメントに対するループは、顔検出７６０および制約条件識別７７０のみを含む。顔画像および制約条件が全部のビデオ・セグメントから収集されたのち、データベース構築ステップ７９０およびデータベース更新ステップ７８０が、データベースが空かどうかの条件に基づいて、開始される。この実施形態は、距離メトリックの学習およびクラスタリングのための反復工程数をなくし、よってより効率的な解決策を提供する。更新ステップ７８０は、顔検出ステップ４２０および制約条件識別ステップ４３０がスキップされる点のほかは、図４に示されたものと同じである。同様に、データベース構築ステップ７９０は、顔検出ステップ３２０および制約条件識別ステップ３３０がスキップされる点のほかは、図３に示されたものと同じである。RFIDラベルが利用可能なとき、プロセス７００はRFID情報を利用してセグメント併合７４０を実行して、ループの前に、関係したセグメントをより大きな、より少数のセグメントに組み合わせる。制約条件識別ステップ７７０もRFIDラベル情報が入手可能なときにはこれを利用する。
【００２２】
最大マージン・メトリック学習
あらゆる画像は高次元空間におけるベクトルである。それらをユークリッド・メトリックに従って直接的にクラスタリングすることは、望ましくない結果につながることがある。一人の人物の顔画像の分布は球状ではなく、層状だからである。人物は同じだが条件が異なる二つの画像の間の距離は、同じ条件のもとだが異なる人物の間の距離よりも大きくなる可能性が高い。この問題を解決するためには、適正なメトリックを学習することが決定的に重要になる。
【００２３】
本稿で記述される半教師ありメトリック学習の枠組みは、最大マージン・メトリック学習（MMML:  Maximum  Margin  Metric  Learning）と呼ばれる。主たる発想は、類似サンプル対の距離と非類似サンプル対の距離との間のマージンを最大化することである。それは、半正定値計画法により解くことができる。上記の規則に従って学習されたメトリックは、ユークリッド・メトリックよりも、顔画像のような画像をクラスタリングするためにより好適である。類似対の距離が非類似対の距離より小さくなることが保証されるからである。
【００２４】
【数２】
0005792320.tif 000003
を入力データ・セットとする。ペアごとの制約条件は次のように記される。
【００２５】
S＝{(xi,xj)|xiおよびxjは類似対（similar  pair）サンプル}
D＝{(xi,xj)|xiおよびxjは非類似対（dissimilar  pair）サンプル}
ここで、nは入力データ・セット・サンプルの数である。各xi∈Xはd次元の列ベクトルである。Sは類似サンプル対の集合であり、Dは非類似サンプル対の集合である。ペアごとの制約条件は、規則または適用の背景に従って、事前の知識に基づいて同定されることができる。
【００２６】
距離メトリックはA∈Rd×dで表される。この距離メトリックを使っての二つのサンプルxiとxjの間の距離は、
【数３】
0005792320.tif 000004
と定義される。空間Rd内のあらゆる対の点の距離が非負であることを保証するため、距離メトリックAは半正定値でなければならない。すなわち、A≧0である。実のところ、Aはマハラノビス距離メトリックを表し、Iを恒等行列としてA＝Iであれば、距離はユークリッド距離に帰着する。
【００２７】
クラスタリングを容易にするため、非類似対の間の距離を最大化し、類似対の間の距離を最小化するメトリックが学習される。この目標を達成するため、類似対の距離と非類似対の距離の間のマージンが拡大される。換言すれば、実軸中の距離の、いかなるサンプル対の距離も属さない最大の空白区間を与え、類似サンプル対の距離はその一方の側にあり、非類似サンプル対の距離は他方の側にあるようなメトリックが求められる。
【００２８】
距離メトリック学習のための枠組みは次のように定式化される。
【００２９】
【数４】
0005792320.tif 000005
この最適化問題の制約条件は、類似対の距離がb0−dより小さく、非類似対の距離がb0＋dより大きいことを保証する。よって、2dが最大化すべき空白マージンである。Ω(A)はA上で定義される正則化関数（regularizer）であり、これはA上の関数であり、Ω(λA)がスカラーλと正の相関をもち、Ω(A)≠Ω(λA)  （λ≠1）となることを保証するという属性をもつ。制約条件Ω(A0)＝1は必要である。これなしでは、単にA0にλ＞0を乗算することによって、任意のdを得ることができる。ある実施形態では、Aのフロベニウス・ノルムが正則化関数Ω(A)として使われる。これは次のように定義される。
【００３０】
【数５】
0005792320.tif 000006
b＝b0/d、A＝A0/dと表すと、Ω(A)＝Ω(A0/d)でありこれは1/dと正の相関をもつので、max  dの最適化結果はminΩ(A)と等価である。よって、この枠組みは、次と等価になる。
【００３１】
【数６】
0005792320.tif 000007
現実世界の応用では、たいていのデータは分離不能である。すなわち、上記のすべての制約条件を満たすマージンを見出すことはできない。よって、この場合、上記の問題には解がない。これでは、上記で提案した方法が適用不可能となってしまう。この種の問題に取り組むため、余裕〔スラック〕変数が上記の枠組みに導入される。
【００３２】
【数７】
0005792320.tif 000008
ここで、λは、過剰な適合〔フィッティング〕を制約するための正のパラメータであり、αはペナルティーの重みを制御する正のパラメータである。
【００３３】
上記の枠組みを単純化するため、次のようなyijが導入される。
【００３４】
【数８】
0005792320.tif 000009
すると、上記の枠組みは次のように書ける。
【００３５】
【数９】
0005792320.tif 000010
これが、大マージン・メトリック学習（Large  Margin  Metric  Learning）の枠組みの主要な形である。これは凸最適化問題である。距離メトリックAの半定値制約条件は問題を半定値最適化問題に制限する。この種の問題を解くことのできる例示的なツールは非特許文献２に見出すことができる。
オンライン学習アルゴリズム
非特許文献３における統計的勾配降下（stochastic  gradient  descent）法の発想を使って本方法の効率を改善するためにさらにオンライン・アルゴリズムが導出される。勾配を解く計算を単純化するために、上記の枠組みは損失関数のスタイルで次のように書き直される。
【００３６】
【数１０】
0005792320.tif 000011
ここで、
【数１１】
0005792320.tif 000012
はαヒンジ損失関数であり、αは正のパラメータである。α＝1のときは、損失関数はヒンジ損失関数になる。α＞1に設定すれば、損失関数はなめらかになる。特にα＝2であれば、二乗ヒンジ損失関数と呼ばれ、これはヒンジ損失と二乗損失の間のトレードオフと見ることができる。αが大きくなると、上記関数は大きな誤差に対してより敏感になる。適正な損失関数は、パラメータαを調整することによって簡単に選ぶことができる。さらに、α＜1のときは、αが小さくなる場合にマージン付近でより敏感になる。
【００３７】
上記の枠組みにおける目的関数をf(A,b)を記すと、f(A,b)のAおよびbに関する勾配は次式によって与えられる。
【００３８】
【数１２】
0005792320.tif 000013
オンライン学習アルゴリズムはループ内で一つの制約条件を考えるだけなので、勾配の総和関数には一つの項しかない。このアルゴリズムは、「アルゴリズム１」において呈示される。
【００３９】
アルゴリズム１  最大マージン・メトリック学習のためのオンライン学習アルゴリズム
入力：時刻t＝1,…,Tにおけるペアごとの制約条件(xit,xjt)およびyijt
出力：AT
A0＝I、b0＝1と初期化；
【表１】
0005792320.tif 000014
このアルゴリズムでは、αtは降下の適切なきざみ長さである。それは、現在の逐次反復回数の関数であってもよいし、他の規則に従って計算されてもよい。Aを半正定値の円錐に投影する一般的な方法は、Aのすべての負の固有値を0に設定することである。特徴の数dが大きいときは、あらゆる固有値を計算することは多大な時間がかかる。本アルゴリズムにはこの問題がない。そのことは、下記で見ることができる。
【００４０】
補題１：A∈Rd×dが半定値行列であれば、∀x∈Rd  B＝A−xxTの負の固有値の最大数は1である。
【００４１】
補題１から、降下後のAの負の固有値の最大数が1であることが推論できる。よって、最小の固有値とその固有ベクトルをみつければよい。eを負の固有値λeの固有ベクトルとする。Aを半正定値の円錐に投影することは、A＝A−λeeeTと設定することによって達成できる。
【００４２】
例
下記は、本MMMLメトリック学習方法を使って顔画像データ・セットについての距離メトリックを取得する例である。この例では、ORLデータ・セットが入力顔画像として選ばれ、顔画像ベクトルの次元は、主成分解析（PCA）法を使って30まで減らされる。ペアごとの制約条件は、データ・セット中ですでに与えられているラベル情報に従って生成される。データ・セット中で与えられているラベル情報は、顔画像のクラスについての基礎となる事実であり、クラス・ラベルと呼ばれる。次いで、識別された制約条件は、顔画像データとともに、発明されたMMML方法に従って距離メトリックを学習するために使われる。ペアごとの制約条件のもとで学習された距離メトリックの性能を評価するために、得られた距離メトリックは、K平均法によってサンプルをクラスタリングするために使われ、クラスタリングされた結果がクラスター・ラベルと呼ばれる。こうして、顔画像について、二つのラベルがあることになる：基礎となる事実であるクラスであるクラス・ラベルと、学習された距離メトリックを使ったクラスタリングを通じて得られたクラスターであるクラスター・ラベルである。クラスタリングの結果は、メトリックの性能を示すために使われる。クラスタリング結果を定量的に評価するために、次のような二つの性能指標が採用される。
【００４３】
１．クラスタリング精度
クラスタリング精度は、クラスターとクラスの間の一対一関係を発見し、各クラスターが対応するクラスからのデータ点を含んでいる度合いを測る。クラスタリング精度は次のように定義される。
【００４４】
【数１３】
0005792320.tif 000015
ここで、nは顔画像の総数であり；riは顔画像xiのクラスター・ラベルを表し；liはxiの真のクラス・ラベルを表し；δ(a,b)はa＝bであれば1に等しく、そうでなければ0に等しいデルタ関数であり；map(ri)は各クラスター・ラベルriをデータ・セットからのその対応するクラス・ラベルにマッピングするマッピング関数である。
【００４５】
２．規格化された相互情報
第二の指標は、規格化された相互情報（NMI:  Normalized  Mutual  Information）であり、これはクラスターの品質を決定するために使われる。クラスタリング結果を与えられると、NMIは次式によって推定される。
【００４６】
【数１４】
0005792320.tif 000016
ここで、niはクラスターRiに含まれるデータ・サンプル（すなわち顔画像）の数を表し、i＝1,…,cであり；cはクラスターの総数である。カレット＾付きのnjはクラスLjに属するデータ・サンプル（すなわち顔画像）の数であり、j＝1,…,cであり、nijはクラスターRiとクラスLjの共通部分にはいるデータの数を表す。NMIが大きいほど、得られたクラスタリング結果はよい。
【００４７】
実験結果は図８に示されている。横軸は生成され使用された制約条件の数と利用可能な制約条件の最大数との比を表す。実線は、AccおよびNMIで表したMMMLの結果を示し、点線はユークリッド・メトリックを使った結果を表す。他の二つの線は二つの従来技術の結果である。この図は、MMML法がORL顔データ・セットにおいて他よりもずっとよい性能を発揮することを示している。MMML法は、顔登録のよりよい結果を得る助けとなることができる。
【００４８】
本発明の好ましい実施形態について本稿で詳細に述べてきたが、本発明がこれらの実施形態に限定されるものではなく、付属の請求項によって定義される本発明の精神および範囲から外れることなく他の修正および変更が当業者によって実施されてもよいことは理解しておくものとする。
いくつかの付記を記載しておく。
〔付記１〕
ユーザー・インターフェースであって：
システムのユーザーの物理的特徴に対応する画像のデータベースであって、ユーザーの前記物理的特徴は、前記システムのユーザー間の区別をする、段階と；
ユーザーが前記システムとインターフェースをもつときにユーザー画像を捕捉するビデオ装置と；
前記システムとのユーザー対話に基づいて前記システムのユーザー選好を収集し、前記選好を分離して、前記システムの各ユーザーに対応する個別ユーザー選好の集合を生成する選好解析器と；
前記システムの使用に関係する個別ユーザー選好を記憶する選好データベースと；
画像のデータベース中の画像に基づいて前記システムの諸ユーザーを相関付けし、前記システムの特定のユーザーに関係した、そのユーザーが前記システムとインターフェースをもつときに前記ビデオ装置によって捕捉された個別ユーザー選好を適用する相関器とを有する、
ユーザー・インターフェース。
〔付記２〕
画像の前記データベースが顔画像のデータベースである、付記１記載のユーザー・インターフェース。
〔付記３〕
前記システムはテレビ・セットであり、前記ユーザー選好はユーザーのお気に入りのチャンネル、映画およびテレビ番組の好まれるジャンルを含む、付記１記載のユーザー・インターフェース。
〔付記４〕
ユーザー登録の方法であって：
諸ユーザーの諸ピクチャーのシーケンスにアクセスする段階と；
ユーザー間の区別をするユーザーの物理的特徴に対応する画像を、諸ピクチャーの前記シーケンスから検出する段階と；
前記検出された画像を使って距離メトリックを決定する段階と；
前記距離メトリックを使って計算された距離に基づいて前記画像をクラスタリングする段階と；
クラスタリング結果に基づいてユーザーを登録する段階とを含む、
方法。
〔付記５〕
検出された画像が顔画像である、付記４記載の方法。
〔付記６〕
距離メトリックを決定する前記段階がさらに、検出された画像の間で制約条件を識別する段階と；識別された制約条件に基づいて距離メトリックを学習する段階とを含む、付記４記載の方法。
〔付記７〕
前記識別された制約条件が、検出された画像の類似対および検出された画像の非類似対を含む、付記６記載の方法。
〔付記８〕
検出された画像の類似対が同じ人物の二つの検出された画像からなる、付記７記載の方法。
〔付記９〕
検出された画像の非類似対が二人の異なる人物の二つの検出された画像からなる、付記７記載の方法。
〔付記１０〕
ユーザー登録を更新する方法であって：
諸ユーザーの諸ピクチャーのシーケンスにアクセスする段階と；
前記諸ピクチャーのシーケンスから画像を検出する段階であって、前記画像はユーザー間の区別をするユーザーの物理的特徴に対応する、段階と；
検出された画像の間で制約条件を識別する段階と；
既存の距離メトリックを使って計算された距離に基づいて前記画像をクラスタリングする段階と；
前記クラスタリングの結果を前記識別された制約条件を用いて検証する段階と；
前記クラスタリングの結果および検証結果に基づいてユーザー登録を更新する段階とを含む、
方法。
〔付記１１〕
検出された画像が顔画像である、付記１０記載の方法。
〔付記１２〕
制約条件を識別する前記段階が、検出された画像の類似対および検出された画像の非類似対を識別することを含む、付記１０記載の方法。
〔付記１３〕
検出された画像の類似対が同じ人物の二つの検出された画像からなる、付記１２記載の方法。
〔付記１４〕
検出された画像の非類似対が二人の異なる人物の二つの検出された画像からなる、付記１２記載の方法。
〔付記１５〕
前記検証する段階において前記制約条件が満たされる場合、前記更新する段階はさらに、新たにクラスタリングされた画像を追加することによってユーザー登録を更新することを含む、付記１０記載の方法。
〔付記１６〕
前記検証する段階において前記制約条件が満たされない場合、前記更新する段階はさらに：
前記識別された制約条件を加えることによって距離メトリックを学習する段階と；
前記学習された距離メトリックを使って計算された距離に基づいて前記画像および既存の画像をクラスタリングし直す段階と；
前記クラスタリングし直した結果および前記学習された距離メトリックを使ってユーザー登録を更新する段階とを含む、
付記１０記載の方法。
〔付記１７〕
距離メトリックAを決定する方法であって：
点間のある距離をもつ複数対の点(xi,xj)を同定する段階であって、一対の点(xi,xj)の間の距離dA(xi,xj)は距離メトリックAに基づいて
【数１５】
0005792320.tif 000017
として定義される、段階と；
前記距離メトリックAの正則化関数を選択する段階と；
前記複数対の点の間の距離dAに対する一組の制約条件に従って前記正則化関数を最小化して、前記正則化関数の第一の値を得る段階と；
前記距離メトリックAを、前記正則化関数の、前記第一の値以下である値を達成するものを見出すことによって決定する段階とを含む、
方法。
〔付記１８〕
前記距離メトリックの正則化関数がフロベニウス・ノルムである、付記１７記載の方法。
〔付記１９〕
前記点が顔画像である、付記１７記載の方法。
〔付記２０〕
前記正則化関数の前記第一の値が極小値である、付記１７記載の方法。
〔付記２１〕
点の類似対および点の非類似対を同定する段階をさらに含む、付記１７記載の方法。
〔付記２２〕
前記一組の制約条件が、前記距離メトリックが半定値であること；前記識別された類似対の距離が第一の非負の値以下であること；および前記識別された非類似対の距離が第二の非負の値以上であることを含む、付記２１記載の方法。
〔付記２３〕
一組の余裕変数を選択する段階をさらに含み、前記一組の余裕変数は、前記最小化において最小化される組み合わせ関数を通じて前記正則化関数と組み合わされる、付記１７記載の方法。
〔付記２４〕
点の類似対および点の非類似対を同定する段階をさらに含む、付記２３記載の方法。
〔付記２５〕
前記一組の制約条件が：前記距離メトリックが半定値であること；前記余裕変数が非負であること；前記識別された類似対の距離が第一の非負の値以下であること；および前記識別された非類似対の距離が第二の非負の値以上であることを含む、付記２４記載の方法。
【図１】
0005792320.tif 000020
【図２】
0005792320.tif 000021
【図３】
0005792320.tif 000022
【図４】
0005792320.tif 000023
【図５】
0005792320.tif 000024
【図６】
0005792320.tif 000025
【図７】
0005792320.tif 000026
【図８】
0005792320.tif 000027