"画像を解釈する方法であって、因子分解可能な上限を有する目的関数を最適化する複数変数の構成を発見することを含み、因子分解可能とは、前記上限が、構成候補として知られるエレメントの効率的な動的順序づけに依存する反復アルゴリズムを優先待ち行列における上限スコアの降順で適用することによって非相互作用パーツの合計または非負の相互作用パーツの積の形式へと操作される、または操作され得ることを意味する方法。前記反復アルゴリズムは、a.優先待ち行列優先Qを確立することであって、候補の優先順位は上限候補と共に上がることと、b.カレント候補値を確立し、かつこれを0,0...,0に設定することと、c.最良候補値を確立し、かつこれを0,0...,0に設定することと、d.優先Qに後続候補カレントの全エレメントを挿入することと、e.真のスコア最良候補>上限先頭優先Qであるかどうかについて問合せを行うことと、ステップeが正しければ、最良候補を返すことと、ステップeが正しくなければ、i優先Qの先頭における候補をカレントへ割り付けかつこれを優先Qから外し、ii優先Qに後続候補カレントの全エレメントを挿入し、かつこの後、iii真のスコア最良候補>真のスコアカレントであるかどうかを決定することと、次に、ステップeのiiiが真であれば、ステップeの開始へ戻ることと、ステップeのiiiが真でなければ、カレントにおける値を包含するように最良候補を更新し、ステップeの開始へ戻ることを含む、請求項1に記載の方法。前記反復アルゴリズムは、実行中に、その時点で入手可能な最良の完全解を得るために中断されてもよい任意時間アルゴリズムである、請求項1に記載の方法。前記目的関数は第一項と第二項とを含み、前記第一項はオブジェクトまたはシーンの個々のパーツの特性を記述し、かつ前記第二項はこれらのパーツ間の関係及び/または制約を記述する、請求項1に記載の方法。個々のパーツの局在化を向上させるためには、その典型的な空間的配置に関する情報をモデリングすることが有益である。このような幾何学的情報のモデリングは、局在化パフォーマンスを大幅に向上させる。しかしながら、これもまた、パーツ間の依存性を招来する。例えば、顔の場合、モデリングされ得る情報は顔面の対称性または典型的なパーツ間距離である。しかしながらこのモデルでは、目のパーツとして所定のロケーションを仮定すると、鼻が発見されると思われるロケーション集合に影響が出る。その結果、もはやパーツを独立的に画像へ嵌め込むことはできない。代わりに、全パーツの接合ロケーションとしてのNK個の可能性について最適構成が探索される必要がある。これはKの指数関数であることから、この探索は、パーツ数の増加に伴ってすぐに処理しにくいものとなる。具体的には、7個のパーツ間の空間的関係のモデリングが事実上の限界とされている場合が多い。従って、パーツ間に依存性があるモデルを最適化する新しい方法を発見することが望ましい。本出願は、構成候補の効率的な動的順序づけに依存する反復アルゴリズムを優先待ち行列における上限スコアの降順で適用することにより、因子分解可能な上限を有する目的関数を最適化する複数変数の構成を発見して画像を解釈する方法及びシステムである。一例として、オブジェクトの星座モデルを考察されたい。これは、オブジェクトの個々のパーツ、並びにこれらのパーツ間の空間的関係のアピアランスモデルを明示する。これらは、その値が画像内のオブジェクトの類似を表す単一関数へと結合される。オブジェクトが存在する構成を画像内に発見するために、我々はこの関数を全ての構成候補に渡って最大化する。上述の反復アルゴリズムの目的は、このような最適構成を効率的に発見することにある。図1は、本出願のコンセプトが実装されている環境100を示す。環境100は、ネットワーク102及び通信チャネル104を介して複数のコンポーネント間の通信を提供する。環境100内のコンポーネントには、カテゴリ分類システム106と、局在化システム108と、オブジェクト認識システム110と、全関数評価システム112と、パーツ間関係システム114と、パーツアピアランスシステム116と、因子分解可能上限システム118とが含まれる。これらのシステムは各々、別々のプロセッサ及びコンピュータメモリを有しかつ適切なソフトウェアを実行する別々のコンピュータ操作可能サーバ上に存在してもよい。またこれらは、クラウドコンピューティング環境へ1つのエレメントとして付着されてもよく、またはサーバ120等の同じサーバ上に位置決めされてもよい。各サーバは、通信リンク104を介して、ウェブ対応コンピュータ122、画像生成能力を有する電話124または他のウェブ対応携帯デバイス126等の、但しこれらに限定されない、画像を送受信することができる様々なデバイスの任意のものへ接続されてもよい。またサーバ120は、電子的に格納された画像128を含むコンピュータデータベースとして編成されてもよい、コンピュータメモリで構成される情報レポジトリとして考慮される場合もある。或いは、本出願の全体システムは、スタンドアロンコンピューティングデバイス上に位置決めされてもよい。デバイス122-126は、後述する画像解釈オペレーションを達成するような方法で、システム106-118との間で画像を送受信してもよい。但し、これらのオペレーションの様々なステップはシステム106-118によって達成される。次に、図2を参照すると、星座モデルを顔200、オートバイ210及び自動車220へ適用したプロセスの結果が示されている。星座モデルは、コンピュータビジョンの分野では周知であり、コンピュータビジョンにおけるカテゴリレベルのオブジェクト認識のための確率モデルである。パーツベースの他のモデルと同様に、星座モデルは、オブジェクトのクラスを相互的な幾何学的制約下にあるK個のパーツの集合によって表現しようとする。星座モデルは、異なるパーツ間の幾何学的関係を考慮することから、ある特定のオブジェクトカテゴリについて、これらのパーツの相対的ロケーション、相対的スケール及びアピアランスを明示的にモデリングする。星座モデルは2つのコンポーネント、即ちアピアランスモデルと、空間的関係モデルとを含む。本出願の実施形態の9例は、3つの異なるアピアランスモデル及び3つの異なる空間的な先験的確率にスパンする。星座モデルが強調されているが、より一般的には、因子分解可能な上限を有する限り、星座モデルのうちの1つ以外の目的関数が使用される可能性もある。次の論考においてさらに詳述するが、因子分解可能とは、上限が何らかの算術演算または他の演算によって非相互作用パーツの合計または非負の相互作用パーツの積の形式へと操作される、または操作され得ることを意味する。従って、コンピュータビジョンの文献ではオブジェクトまたはシーンカテゴリのパーツベースモデルが一般的であり、かつ関連のbag-of-featuresモデルが画像のタグ付け及びカテゴリ分類にうまく使用されてきているが、オブジェクト表現の重大部分は、オブジェクト特徴間の空間的関係にあるという長い間の認識がある。空間的関係のモデリングは、オブジェクトの認識、カテゴリ分類及び局在化のパフォーマンスを向上させる。空間的関係を用いるモデルは、オブジェクト及びそのパーツに関する自動画像解釈を呼び出すために使用されることも可能である。この後者の課題、即ちオブジェクトパーツの効率的な局在化は、それ自体で関心対象である。これは、図2から分かるように、目201、202、鼻204、206及び口203、205等のオブジェクトパーツの中には、あまりに重要であるために内在的な関心対象オブジェクトであるとされ得るものがあることに起因する。一例として、多くの異なる形状、サイズ及びデザインを有するオートバイ具体的なオートバイは、オートバイ210であるを考察されたい。画像内でのオートバイの認識は困難である。しかしながら、オートバイのパーツは、車輪211、212及びヘッドライト213等のより一貫したアピアランスを有する傾向がある。従って、オートバイの認識に取り組む一方法は、車輪211、212、ヘッドライト213及び予測される相対的な空間的関係性にあるパーツを探すことである。同様の例は、車輪221、222、ドア223及びヘッドライト224を有する自動車220であろう。この認識は、星座モデルが実行しようとするものである。この場合、車輪及びヘッドライトといえども変化に富んでいることから、その検出も完全ではない。典型的には、あらゆるロケーションが車輪の中心であるという幾分かの類似性を有するが、大部分のロケーションでこの類似の値は小さい、という複数の仮説が検討されなければならなくなる。各パーツの複数の仮説は、最も可能性の高い構成に対する組合せ探索に問題を生じさせる。従って、本出願は、星座モデルの目的関数を最適化するという上述の問題点に適用される、複数の離散変数の関数を最適化するための一般的アルゴリズムを提供する。目的関数の因子分解可能な上限を用いることにより、本出願のアルゴリズムは、優先待ち行列を動的に成長させてNK個の候補を効率的に暗に順序づけする。ソリューション候補は、優先待ち行列から1つずつ検索され、その候補の真の目的関数が計算され、次いで待ち行列からまだ抽出されていない全ての候補の上限と比較される。これは、後に説明するように、因子分解可能性を活用することによって効率的に実行されることが可能である。未探索候補の全ての上限を超える真のスコアを有する候補が識別されると、これは、これまでで最良の候補が最適ソリューションであることを保証する。我々は、実際には、近似または制限モデルによらない場合でも、本方法が代替の最適化スキームより数倍も効率的であることを実証している。コンピュータビジョン及びパターン認識における他の多くの問題点は、離散変数に渡る関数の最大化としての枠内に入れることができる。K個の変数が存在し、その各々がN個の値のうちの1つをとるとすれば、このような最大化は、NK個の可能な組合せに渡る探索になる。本アルゴリズムは、このような多くの問題点に対する確実な最適ソリューションを効率的に発見するために適用されてもよい。一般的な要件は、目的関数上で因子分解可能な上限が発見されることである。次に、以下の論考では、複数のパーツ及びこれらのパーツ間の空間的関係によってモデリングされる最適化アルゴリズム及びオブジェクトロケーションへのその適用について述べる。この場合、最適化アルゴリズムはパーツのアピアランス及びパーツ間距離より一般的には、距離に加えて、または距離の代わりに角度、共直線関係、他等のものを含んでもよいこれらのパーツの空間的構造を受信することに言及しておく。以下の説明は、専ら星座モデルについて行うが、記述されるべき最適化アルゴリズムは一般的であり、僅かな修正によって追加の問題点に適用され得ることは認識されるべきである。核心的な最適化アルゴリズムは、K個の離散変数、l1,...,l2,...,lkに渡って最適化を考慮する。但し、liは離散変数をとる。各liは、異なる値集合をとることができる。単純化を期して、各々が0からN-1までのN個の値をとるものと想定する。これは、目的関数fが実行可能領域より外部-∞であるようにして定義されるという理解によって最適化と呼ばれる。可能なソリューションの数は、NKである。関数gl1...lkは、目的関数f上の上限であり、即ち、∀l1...1kgl1...lk≧fl1...lkである。可能なNK個のソリューションが全て、優先待ち行列においてその上限スコアの降順で配列されることを想像されたい。最も高い上限を有するソリューション候補優先待ち行列の先頭または先頭エレメントが選択され、その真のスコアfが評価される。この真のスコアが待ち行列における次のエレメントの上限gを超えていれば、これは、あらゆる未探索ソリューション候補の上限及び真のスコアも超える。従って、最適ソリューションが発見される。そうでなければ、システムは最良候補発見の追跡を継続し、プロセスが反復される。ループ終了時点で探索された最良のソリューションが、我々の最適ソリューションであるものとして保証される。優先待ち行列には、NK個の候補が配列されたままであり、よってシステムは依然として高い計算複雑度を負っていることに留意されたい。この負担は、上限が因子分解可能であれば軽減されることが可能である。関数gl1...lKは、gを非相互作用パーツの和または積として表すことができれば、fの因子分解可能な上限である。すると、になる。因数分解可能という言い回しは、本出願の概念が主として倍数因子を成分として有する確率関数に対処するものであるために使用されている。本明細書において記述している概念は、i個に渡る和が正項の積に置換されても同じく効力を発する。これは、上限によってソートされる優先待ち行列を動的に編成しかつこれを必要に応じて成長させるための我々のアルゴリズムに繋がる。単純化を期して、かつ一般性を失うことなく、hiaは、aが0からN-1まで増大するにつれて低減するものと仮定する。この仮定が成り立たなければ、我々は各iにおける候補をhiでソートし、逆写像のためのソート-指数アレイを保持する。我々は次に、このソーティングにより提供された候補の新しい順序づけを使用する。この新しい順序づけでは、上述の仮定の成立が保証される。明らかに、0,0,...,0が最も高い上限を有する候補であり、後続候補1,0,...,0,0,1,...,0,...,0,0,...,1のうちの1つがこれに続く。後続候補の集合は、カレント候補を取り上げ、各位置指数を一度に1だけ増分することによって取得されることが可能である。従って、我々は各位置における指数を次に最良である可能性のある値で置換する。例えば、K=4、及び考慮対象の候補を2,3,0,1であるとすると、第1のパーツは3番目によい選択肢であり、第2のパーツは4番目によい選択肢であり、第3のパーツは最良の選択肢であり、かつ第4のパーツは2番目によい選択肢である。この配列下では、この候補の後続候補は3,3,0,1、2,4,0,1、2,3,1,1及び2,3,0,2である。優先待ち行列へ追加されるのがこれらの後続候補のみであれば、それが既に待ち行列内に存在していて未だ考慮されていないものであるか、これらの4つの直近後続候補のうちの1つであるかのいずれかで、次に高い上限を有する候補が既に待ち行列内に存在することが確信される。これにより、待ち行列を動的に成長させることができるようになり、かつ全ての候補を前もってソートする必要がない。候補は、常時、その後続候補より高い上限を有することが保証される。この観測は、次の擬似コードをもたらす。priorityQ={};current=0,0,...,0;best=current;priorityQ.addsuccessorscurrent;whilenotfbest>gheadpriorityQ{current=headpriorityQ;remove_headpriorityQ;priorityQ.addsuccessorscurrent;ifnotfbest>fcurrentbest=current;}returnbest;このように、優先待ち行列は、探索が進むにつれて動的に成長される。アルゴリズムがソリューションを返すと、これは最適なソリューションを提供する。最も高度な探索アルゴリズムの場合のように、このアルゴリズムの最悪の複雑度はNKであり、実際に、待ち行列を保持しかつ上限を計算するオーバーヘッドに起因して単純な全数検索よりも悪い。しかしながら、実際には、空間の大部分が明確に探索されることはなく、このアプリケーションにおけるアルゴリズムは極めて効率的になる。この経験的効率は、上限に依存する。不良ソリューションに対して上限が厳密であるほど、実際に探索される空間は少なくなる。注目すべき詳細は、もう1点ある。ソリューション候補2,3,0,1この場合、K=4について考察されたい。これは、全てより高い上限を有することが保証される3つの先行候補、1,3,0,1、2,2,0,1及び2,3,0,0を有する。全ての先行候補が調査されれば、2,3,0,1は待ち行列に三度追加される可能性がある。僅かなブックキーピングの追加は、この不必要なオーバーロードを回避する。後続候補リストは、一度に1位置を、i=1から開始して最初の非ゼロ位置まで増分することによって計算される。従って、後続候補0,0,2,1={1,0,2,1,0,1,2,1,0,0,3,1}になる。これは、各候補が一意の先行候補を有することを保証し、かつアルゴリズムの実行時間効率を向上させる。理想的には、ある候補は、その最も低い上限の先行候補を除外する場合にのみ待ち行列に入れられるべきであるが、これを実施する計算オーバーヘッドは任意の潜在的節減分を超過する場合がある。この反復アルゴリズムのアプリケーション例として、何らかのオブジェクトカテゴリの星座モデルについて再度考察されたい。例えば、このカテゴリは人間の顔であって、目、鼻及び口等のパーツを使用することができる。概して、特徴的なアピアランスを有するK個のパーツが存在する。これらのパーツの幾何学的構成は、ベクトルL=[l1,...,lk]によって表される。但し、li=xi,yiはパーツiのロケーションである。画像Iを所与とすると、Iにおけるパーツの構成を記述するためにロケーションベクトルLが決定されてもよい。これを行うために、システムは、画像内のパーツ構成Lの確率、pL|Iを最大化する。これは、と表すことができる。第一項pLは、先行空間と呼ばれる。第二項アピアランス項と呼ばれるは、下記のようにモデリングされることが多い。ここで、I[li]は、画像Iにおけるliを中心とした画像パッチのアピアランスを表す。これは、そのロケーションから抽出された生のピクセル値である可能性もあれば、スケール不変特徴変換SIFT記述子によって与えられるもの等のアピアランスの他の何らかの表現である可能性もある。Aiは、i番目のパーツのアピアランスを符号化するモデルパラメータの集合である。例えば、I[li]が画像パッチのSIFT記述子であれば、Aiはトレーニング記述子の平均及び共分散である可能性がある。この因子分解は、画像内にロケーションを与えられている各パーツのアピアランスが他の全てのパーツのロケーション及びアピアランスとは独立しているものと仮定している。この仮定は、必ずしも厳密には成り立たない。例えば、顔の特徴のアピアランスは人の性別によって影響され、よって、1つのパーツの女性的アピアランスは、別のパーツが男性的に見える確率に影響を与える。この仮定は、パーツ同士が重なる場合にも破られる但し、何れにしても、多くの先行空間はこのような構成を考慮から外す。しかしながら、概して、この近似は実際には広く使用され、かつD.Crandall、P.Felzenszwalb及びD.Huttenlocher共著統計モデルを用いるパーツベース認識のための先行空間CVPR、2005年、及びT.K.Leung、M.C.Burl及びP.Perona共著ランダムラベルグラフマッチングを用いるクラッタシーン内の顔の発見ICCV、1995年、に示されているように有益な結果を与えることができる。上記文献は共に、本参照によりその全体が開示に含まれる。従って、完全なモデルは下記のようになる。この場合もやはり、局在化のタスクは、この式を最大化するパーツ構成L=|l1...lk|を発見することである。上述の星座モデルの最適化は、目的関数が対数形式で、である本出願のアルゴリズム要件と容易に結びつく。本来の因子分解は、である。0≧logpl1...1kであることに留意されたい。従って、上限はアピアランスモデルによって与えられ、かつ完全なスコアまたは真のスコアは、これに先行空間の対数を加算することによって得られる。この定式化の下では、本アルゴリズムは良き直観的説明を有する。探索は、パーツモデルに対する局所応答に従って順序づけされる。画像内の各パーツに対する最良の応答は、より強い仮定は先行空間の結合時に拒絶されていることからより弱い適合を考慮してまず検査される仮説を構成する。星座モデルは確率的であるが、本アルゴリズムは、確率ではなくエネルギー関数を基礎とする類似モデルに等しく適用可能である。図3を参照すると、先に述べた、かつ先に開示した擬似コードのオペレーションを反映する最適化アルゴリズムのフロー図300が提示されている。諸ステップは、複数のパーツによってモデリングされたオブジェクトを位置決めしかつこれらのオブジェクト間の空間的関係を識別するためのアルゴリズムの適用方法を明示している。図3のフロー図300は、ステップ305において、候補の優先順位が上限候補に伴って上がる優先待ち行列優先Qを確立する。上限関数は、[0021]におけるgと同じであり、式1のように計算される。ステップ310において、プロセスは、0,0,...,0に設定されるカレント候補値も確立し、かつステップ320において、0,0,...,0に設定される最良候補値も確立する。次にステップ330において、プロセスは優先Qに後続候補カレントの全エレメントを挿入する。任意の候補の後続は、[0024]及び[0027]において説明したように計算される。この時点で、ステップ340において、真のスコア最良候補>上限先頭優先Qであるかどうかを決定するための検査によって反復ループが始まる。我々の表記法では、真のスコアはfと同じである。ステップ340における検査が成功すればYES、であれば、ステップ350においてプロセスは最良候補を返す。しかしながら、ステップ340における検査が失敗すればNO、であれば、ステップ360においてプロセスは優先Qの先頭における候補をカレントに割り付け、これを優先Qから外す。次に、ステップ370において、プロセスの反復ループは優先Q内に後続候補カレントの全エレメントを挿入し、この後、ステップ380において真のスコア最良候補>真のスコアカレントであるかどうかを決定する別の検査へ移動する。ステップ380における検査が成功すればYES、であれば、プロセスはステップ340に戻って継続される。ステップ380における検査が失敗であればNO、であれば、ステップ390においてプロセスはカレントの値を包含して最良候補を更新し、次いでプロセスはステップ340に戻ってさらなる処理を行う。図4は、4つの星座モデル顔モデルが2つ、オートバイモデルが1つ及び車モデルが1つの最適構成即ち、パーツロケーションを発見するための提案アルゴリズムの適用を実証する一連の検査結果を提示している。モデルパラメータは、カテゴリラベル及びパーツロケーションを用いて手動で注釈された画像即ち、画像テンプレートの監督された学習を介してトレーニングされることが可能である。このようなモデルを自動的に学習する代替方法は、例えばFergus他著非監督スケール不変学習によるオブジェクトクラスの認識CVPR、2003年6月、Weber他著オブジェクトカテゴリの自動的発見へ向けてCVPR、101-109ページ、2000年、及びWeber他著認識用モデルの非監督学習ECCV、18-32ページ、2000年、において論じられているように容易に利用可能である。上述の文献は各々、その全体が開示に含まれる。星座モデルのセットアップに注目すると、先に述べたように、星座モデルは2つの要素、即ちパーツアピアランスモデル及び空間的関係モデルから成る。異なる種類のアピアランスモデル及び先行空間がトレーニングされ、これらは混合されかつ合わされて幾つかの星座モデルが作られる。本アルゴリズムは、これらのモデルによって評価される。これを行うに当たっては、アルゴリズム擬似コードの探索図3のフローチャートも参照されたいのために、使用されるモデルの種類によって変更を行う必要はないことが留意される。実際、その優位点は探索が最適ソリューションを与えることにあり、パフォーマンスが不良であれば、変更を要するのはモデルの方である。本明細書に記述している検査では、3つのアピアランスモデルが使用される。そのうちの1つでは、各画像ロケーションがスケール不変特徴変換SIFT記述子Lowe著スケール不変キーポイントからの弁別的画像特徴、IJCV、602:91-110、2004年、において論じられているもの等。上記文献は、本参照によりその全体が開示に含まれるによって、ロケーション周囲の41x41ピクセル近傍内に表現される。各パーツの尤度pI[li]│li,Aiは、モデルのトレーニングに使用される画像から推定されるパラメータμi、Σiを用いてガウス分布としてモデリングされる。別のアピアランスモデルでは、画像ロケーションのアピアランスが生のピクセル値によって41x41ピクセル近傍内に与えられる。パーツAiは、マーキングされたパーツロケーション付近の近傍パッチであり、かつアピアランススコアpI[li]│li,Aiは、正規化された相互相関NCCAi,I[li]として計算される。この定式化では、pI[li]│li,Aiは適切な確率分布ではなく、表記法hI[li]│li,Aiがより適切である。しかしながら、確率分布だけでなく任意関数に適用可能であることから、最適化アルゴリズムは変わらない。第3のアピアランスモデルでは、ある画像ロケーションにおけるアピアランスが90個の異なるハールフィルタの応答として41x41ピクセル近傍内に符号化される。アピアランススコアhI[li]│li,Aiは、ランダムな画像ロケーションから真のパーツロケーションのアピアランスを見分けるようにトレーニングされたアダブースト分類器の応答として計算される。ハール-アダブーストモデルの場合、画像全体に渡る均一な格子点がパーツロケーション候補ほぼ全ての画像においてN>1000個のロケーションとして使用されるが、ハリス-ラプラス関心点Mikolajczyk他著アフィン領域検出器の比較IJCV、651/2:43-72、において論じられているようなもの。上記文献は、本参照によりその全体が開示に含まれるは、最初の2個N>100におけるロケーション候補として処理される。上述の実験では、41x41ピクセルの近傍が使用されたが、これはモデル要件ではなく、任意サイズの近傍非正方形及び非長方形の近傍を含むを代わりに使用できることに留意されたい。異なる先行空間について、追加実験を行った。1つの先行空間pLは、パーツ間の対間距離を用いてモデリングされた。K個のパーツでは、このような距離がKK-1/2個存在する。ロケーションli及びlj間の距離をdi,jで表し、かつ全距離[d1,2,...,dK-1,K]のベクトルをDで表して、このモデルでは、pLをpDLに比例するものと定義する。実験において、pDLは、対角共分散行列を有するガウス分布であった。この分布のパラメータは、トレーニング例から学習された。別の先行空間は上述のものに類似するものであったが、全距離がl1及びl2間の距離でスケーリングされる点が異なる。その目的は、スケール不変を達成することにある。第3のタイプの先行空間は顔画面のみに対処し、対称先行候補と呼ばれる。これは、顔の軸を中心にして互いの鏡となっていなければ、左右のパーツロケーションにペナルティを与える。本明細書において、これは、我々の対称先行候補を任意に複雑にすることが可能であって、何れにしても因子分解可能である必要はないことの例証として包含されている。実験の一部として、図4に示すような3種のデータセット、即ち、顔のデータセット410、420、オートバイのデータセット430及び車のデータセット440が使用された。顔画像のバイオIDデータセット410,420は、Jesorsky他著ハウスドルフ距離を用いるロバストな顔検出AudioandVideoBasedPersonAuthentication、2001年、において論じられているように、23個のサブジェクトの1521個の顔画像から成る。上記文献は、本参照によりその全体が開示に含まれる。各画像は、パーツ名及びロケーションで完全に注釈を付けられる。顔の表情及び照度には、著しい変形が存在する。オリジナル画像にもスケール変化があり、よって全ての画像は、顔がほぼ同じサイズを有するようにスケールし直されている。さらに、Caltech101データセットからのオートバイ及び車側面のビューが検査されている。Caltech101データセットは、Fei-Fei他著少数訓練例からの生成的ビジュアルモデルの学習:101オブジェクトカテゴリ上でテスト済みのインクリメンタルなBayesアプローチCVPR2004WorkshoponGenerative-ModelBasedVision、2004年、において論じられている。上記文献は、本参照によりその全体が開示に含まれる。この場合もやはり、各カテゴリ内の画像は、特定のオブジェクトが全画像を通じてほぼ同じサイズになるようにスケールし直された。バイオIDの顔モデルのトレーニングには、約100個の画像が使用され、Caltechのオートバイ及び車については各々30個のトレーニング画像が使用された。妥当なモデルが使用されていることを確立するために、2つの標的課題、即ちオブジェクト検出及びオブジェクト局在化に定性的なパフォーマンス測度が設けられる。これらのタスクは、段落[0001]において定義されている。第1のタスクに関しては、受信者動作特性ROC曲線を用いてパフォーマンスが測定される。カテゴリ毎に、我々のアルゴリズムを用いて星座モデルの最良一致スコアが発見される。これは、対応するカテゴリ内の各検査画像について、さらには、背景画像Caltech101背景集合からの50画像についても行われる。背景画像は、負の手本として使用される。ここから、受容しきい値を変えることによってROCプロットが計算される。受信者動作特性ROC曲線または単にROC曲線は、2値分類器システムのその弁別しきい値の変更に伴う感度対1-特異度をグラフにプロットするための信号検出理論における概念である。ROCは、真陽性の割合TPR=真陽性率対偽陽性の割合FPR=偽陽性率をプロットすることによっても等しく表現されることが可能である。これは、基準の変更に伴う2つの動作特性TPR及びFPRの比較であることから、相対動作特性曲線としても知られる。ROC分析は、コストコンテキストまたはクラス分布から独立してまたはこれらを明示する前に最適モデルである可能性のあるものを選択しかつ最適以下のものを放棄するためのツールを提供する。第2のタスクは、パーツの局在化である。この場合、モデルパーツの最良ロケーションは、我々のアルゴリズムによって発見される最適なモデル構成に対応するものとして識別される。これらのロケーションは、全てのカテゴリ内検査画像について記録され、評価のために、手動で注釈を付けられたグラウンドトルースロケーションと比較される。一例として、推測されたロケーションと手動で注釈を付けられたグラウンドトルースロケーションとの間の平均ユークリッド距離を計算して、パーツの局在化の精度を定量化することができる。図4には、幾つかの実験結果が提示されている。ヒストグラム450には、幾つかのモデルの局在化誤差がプロットされている。また、検出パフォーマンスを明示したROC曲線460も提示されている。図5は、各々6個、10個及び14個のパーツでモデルを構築するバイオIDの顔データセット500による実験結果を詳述している。6パーツモデル510では、目の瞳511、512、2つの鼻孔513、514及び左右の口角515、516が使用されている。10パーツモデル520では、眉毛の4つの端点521、522、523、524が追加されている。14パーツのモデルでは、システムは4つの目の端を使用してもよい。図6は、2つの車輪の中心631、632、フロントライト及びテールライト634及び座席の前側635及び後側636の6パーツを使用するオートバイのデータセット630を用いた結果を提示している。また、2つの車輪の中心641、642、タイヤガードの内角643、644、フロントライト及びテールライト645、646、フロントガラス輪郭の最低ポイント647及びルーフの2つの末端648、649の9パーツを使用する車のデータセット640を用いた結果が提示されている。これらの例は、各カテゴリ内の個々のオブジェクトのアピアランス及びジオメトリの変化に関わらず、パーツが如何に高精度で局在化されるかを実証している。図7は、各々6パーツ、10パーツ及び14パーツによる3つの顔モデル700、730、720の顔検出パフォーマンスを明示している。全てのモデルがバイオIDデータセットからの画像上でトレーニングされて検査され、かつ対間距離ガウス先行候補を使用している。ROC曲線は、誤警報率X軸対ヒット率Y軸をプロットしている。図8は、6パーツ810、10パーツ820及び14パーツ830を基礎とする最適ソリューションを提示している。主たる結果は、最適性を保証しながらの提案している探索アルゴリズムの効率である。本アルゴリズム840が探索する平均構成数は、starモデル850、2-fanモデル860及び全数検索870が探索する構成数と比較される。2-fanがより限定的なモデルを要するとしても、アルゴリズム840の効率は経験的に2-fanをも凌ぐことに留意されたい。結果は、使用されたモデル及び検査データセット毎に編成されている。学習されたモデル毎に、大域的最適化を発見するためにアルゴリズムが行った平均反復回数が示されている。各反復は、1つのパーツ構成の評価に対応する。比較のために、starモデル850及び2-fanモデル860が実行する評価回数が提示されている。starモデル850及び2-fanモデル860は限定空間を探索し、よってその表現力は完全な先行空間による星座モデルよりも弱いことに留意されたい。2-fanモデルによる最適構成は、完全な星座モデルでは必ずしも最適とはならない。これに対して、提案している最適化アルゴリズムは、完全な星座モデルの大域的最適化を確実に発見する。また、可能性のある全ての構成数も記されているが、3または4以上のパーツに関してこの数字が実際には実行不可能であることは知られている。図から分かるように、本アルゴリズム/擬似コード図3のフローチャートも参照されたいが行う評価は、より限定的なモデルである2-fanモデルが行う回数よりさらに少ない。これは、計算効率も向上させながら、確率分布pL|Iをより精確にモデリングすることを可能にする。図9は、反復回数が画像内のパーツロケーション候補の数にどのように依存するかを明示している。また、X軸910上のパーツロケーション候補例えば、キーポイントの数、Y軸920上のパーツロケーション候補の数の関数としての我々のアルゴリズムによる反復探索される構成の数の散布図900、3-fanの反復数に関する対数O及び6パーツによるフル探索もプロットされている930。最悪のケースで我々のアルゴリズムにより探索された構成の数は、フル探索及び3-fanより何倍も望ましいものである。散布図を調べると、本アルゴリズムに関して幾つかの洞察が得られる。画像が、そのモデルのカテゴリのオブジェクトを含んでいれば、アルゴリズムは極めて少ない反復の後に終了することが多い。これらは、パーツアピアランスモデルが正しい候補に高得点をつける状況を反映している。画像が背景カテゴリに属していれば、パーツモデルは偽のロケーションでマッチングし、明確な勝者はほとんどいない。従って、勝利する構成を宣言するまでには、さらに多くの構成を探索する必要がある。当然ながら、実際には、上限が受容しきい値を下回ると、探索を停止することによって背景画像は迅速に拒絶される。最終的には、カテゴリ内の画像に関して探索が百万回以上もの反復を実行する幾つかのケースも存在する。通常、これらの状況では最適ソリューションがごく早期に発見されるが、アルゴリズムは、これが実際に最適であるかを確認できるまで多くの代替ソリューションを調査しなければならない。その最適構成が正しいものであれば、これは、先行空間モデルが正しい構成に過度に不利益を与えていることを含意する。最適構成が間違ったものであれば、これは、アピアランスモデルに問題があることを指す場合が多い。このパターンは、星座モデルに関して、我々のアルゴリズムがモデルの目的関数の分析及びデバッグに有益である可能性があることを示唆している。我々のアルゴリズムの計算効率により有効化される当然の功績として、星座モデル内のパーツ数は増大される。文献では、適用される最大の星座モデルは7パーツから成る。我々は、10パーツ及び14パーツバイオIDデータセット上を有する星座モデルを適用している。大部分の先行研究における代替先行空間は、ガウス分布によってモデリングされている。これは、探索プロセスの幾つかの最適化を許容するものであった。例えば、探索時間を評価数Nk1からNkへ短縮するために、ガウス分布の簡易な関数形式が使用された。また、分布の特性は、優先待ち行列の探索を高速化するためにも使用された。本出願のアルゴリズムは、先行空間に凸状、まして連続性等の制約を与えない。本方法の多用性を例証するために、本明細書ではこれが、顔パーツの空間的関係が対称性を用いてモデリングされるモデルに適用される。モデルには、顔の右側からの各パーツに対して、左側の対応するパーツも包含される。対称性の先行候補は、次のように計算される。まず、各反復において部分的ソリューションではなく全てのパーツロケーションが発生することから、最良の顔軸-両目及び両唇端の中点を結ぶ線、が計算される。次に、各パーツペア例えば、左鼻孔、右鼻孔を結ぶ各線分について、顔軸がこれを二等分していなければ、ペナルティが累算される。本アルゴリズムは、この新しい星座モデルを効率的に最適化することができる。本アルゴリズムは、先行分布が容易な分析形式を有していなくても、モデルを首尾良く最適化することができる。本方法は、パーツ間の空間的関係を有するカテゴリモデルの最適化を効率的に実行する。本方法は、星座モデルの周知のファミリに適用され、これらのモデルの計算効率を数倍も向上させることが示された。またこれは、より多くのパーツによるモデルの使用によってカテゴリ分類パフォーマンスの向上を可能にすることから、この高速化が実際に有益であることも実証している。本アルゴリズムは、許容的ヒューリスティックを有するA探索の概念に幾分関連する探索を実行する。しかしながら、典型的なA探索では、探索ノードは部分解子孫葉ノードの全集合を表す。従って、各ノードで計算されるべきヒューリスティック関数は全ての派生解に対する上限でなければならず、有界関数の全体階層が利用可能であることを要する。本アルゴリズムでは、各反復において、解葉ノードが考慮される。従って、目的関数は任意に複雑である可能性があり、必要なものは1つの因子分解可能な上限が全てである。星座局在化実験において、本出願のこの反復アルゴリズムは、多様で複雑な先行空間にも変わらず機能する。これは、探索の考慮事項は文献において考察されるモデルを限定する傾向があるのに対して、本アルゴリズムの著しい優位点である。本アルゴリズムは、任意時間アルゴリズムである。これは、その実行中のいつでも、部分解ではなく、その時点で入手可能な最良の完全解を得るために中断されることが可能である。提案しているアルゴリズムは、k-fanモデルにおける探索効率を向上させるためにも使用されることが可能である。本アルゴリズムは、k個のアンカパーツ構成の評価をスケジュールするために使用される。これらのk個のアンカパーツによる所定の構成に関して、真のスコアは、k個のアンカパーツ並びに他のパーツの最適配列を含む合計モデルスコアになる。本明細書に記述している概念は、最適化の速度を数倍も向上させる利点を提供する。これは、局在化をさらに大幅に効率的にし、よって本方法は潜在的に幾つかの現実的なタスクに適用され得る。さらに、速度の向上に起因して、より多くのオブジェクトパーツをモデリングすることができる。その結果、局在化及びカテゴリ分類のパフォーマンスは向上する。画像のカテゴリ分類に関しては、個々のカテゴリモデルを基礎とする多クラス分類のための幾つかの周知技術のうちの1つを使用することができる。我々は、幾つかのカテゴリモデルに関して、我々のアルゴリズムを用いて最適一致を発見する。最も高い一致スコアを有するカテゴリは、その画像のカテゴリとして割り付けられる。当然ながら、取り上げるカテゴリは1つだけでなくてもよい。画像の検出検査に合格する全てのカテゴリは、有効なカテゴリラベルとして受容される可能性もある。他に、割り付けられる1つまたは複数のカテゴリを解く前に様々なカテゴリスコアが正規化される多くの方法を使用することができる。これまでに開示した、及び他の特徴及び機能またはこれらの代替物のうちの様々なものが、望ましくは他の多くの異なるシステムまたはアプリケーションへと結合されてもよいことは認識されるであろう。また、同じく以下の請求の範囲に包含されることが意図される様々な、現時点では不測である、または予期されていない代替物、修正、変形またはこれらにおける改良が、当業者によって続いて実行される場合もある。"