(57)【特許請求の範囲】
【請求項１】
情報処理装置が、複数のサンプルを使用して分類器の学習を行う方法であって、
前記情報処理装置の追加ユニットが、ラベルなしサンプルを既存のサンプルに追加する追加ステップと、
前記情報処理装置の抽出ユニットが、複数の既存のサポートベクトルを使用して、前記追加されたラベルなしサンプルから新たなサポートベクトルの候補サンプルを抽出する抽出ステップと、
前記情報処理装置の選択ユニットが、前記複数の既存のサポートベクトルを使用して、前記候補サンプルから前記新たなサポートベクトルを選択する選択ステップと、
を備え、
前記抽出ユニットが、前記抽出ステップでは更に、
サンプルのうちいずれかのサンプルからすべての前記サポートベクトルの中心までの最長距離を推定し、
サンプルのうちいずれかのサンプルから前記中心までの最短距離を推定し、
前記新たに追加されたラベルなしサンプルが正のサンプルであるか否かを判断するために、前記最長距離と前記最短距離との間で閾値を設定し、
前記新たに追加されたラベルなしサンプルが候補サンプルであるか否かを前記閾値に従って判定する、
ことを特徴とする方法。
【請求項２】
前記情報処理装置の置き換えユニットが前記既存のサポートベクトルのうちいくつかを前記新たなサポートベクトルと置き換える置き換えステップを更に含むことを特徴とする請求項１記載の方法。
【請求項３】
前記置き換えステップは、
前記サポートベクトルの各々から中心までの距離を計算することと、
最も近い距離を有するサポートベクトルを前記新たなサポートベクトルと置き換えてサポートベクトルの数のカウントを一定に維持することと、
を更に含むことを特徴とする請求項２記載の方法。
【請求項４】
前記情報処理装置の更新ユニットが前記サポートベクトルのすべての重みを更新する更新ステップを更に含むことを特徴とする請求項１記載の方法。
【請求項５】
前記閾値は、どの正のサンプルに関しても、そのサンプルが前記閾値内に入る確率を一定にするように設定されることを特徴とする請求項１記載の方法。
【請求項６】
前記最長距離を推定する際にサポートベクトルデータ記述（ＳＶＤＤ）アルゴリズムが使用されることを特徴とする請求項１記載の方法。
【請求項７】
前記最長距離及び前記最短距離を推定する際にカーネル関数Ｋ（・）が使用され、前記カーネル関数は、どの正規化ベクトルｚに対してもＫ（ｚ，ｚ）が一定であるように選択されることを特徴とする請求項１記載の方法。
【請求項８】
前記カーネル関数Ｋ（・）はヒストグラムインタセクションカーネル（ＨＩＫ）を含むことを特徴とする請求項７記載の方法。
【請求項９】
前記選択ステップは、
前記複数の既存のサポートベクトルに従ってバウンディング超球面を描出することと、
前記候補サンプルが前記新たなサポートベクトルであるか否かを判定することと、
を更に備え、
候補サンプルが前記バウンディング超球面の外側にある場合、その候補サンプルは新たなサポートベクトルとして選択され、候補サンプルが前記バウンディング超球面の内側にある場合、その候補サンプルは新たなサポートベクトルとして選択されないことを特徴とする請求項１記載の方法。
【請求項１０】
複数のサンプルを使用して分類器の学習を行う装置であって、
ラベルなしサンプルを既存のサンプルに追加する追加ユニットと、
複数の既存のサポートベクトルを使用して、前記追加されたラベルなしサンプルから新たなサポートベクトルの候補サンプルを抽出する抽出ユニットと、
前記複数の既存のサポートベクトルを使用して、前記候補サンプルから前記新たなサポートベクトルを選択する選択ユニットと、
を備え、
前記抽出ユニットは、
サンプルのうちいずれかのサンプルからすべての前記サポートベクトルの中心までの最長距離を推定し、
サンプルのうちいずれかのサンプルから前記中心までの最短距離を推定し、
前記新たに追加されたラベルなしサンプルが正のサンプルであるか否かを判断するために、前記最長距離と前記最短距離との間で閾値を設定し、
前記新たに追加されたラベルなしサンプルが候補サンプルであるか否かを前記閾値に従って判定する、
ことを特徴とする装置。
【請求項１１】
情報処理装置が行うユーザ登録対象物検出方法であって、
前記情報処理装置の受信ユニットが、検出されるべき対象物を受信するステップと、
前記情報処理装置の呼び出しユニットが、前記ユーザ登録対象物に従って生成される複数の既存のサポートベクトルを備えた分類器を呼び出すステップと、
前記情報処理装置の認識ユニットが、前記分類器に基づいて前記検出されるべき対象物を認識するステップと、
前記情報処理装置の更新ユニットが、請求項１記載の方法を使用して前記分類器を更新するステップと、
を備えることを特徴とするユーザ登録対象物検出方法。
【請求項１２】
前記検出されるべき対象物は画像又はビデオであることを特徴とする請求項１１記載の方法。
【請求項１３】
ユーザ登録対象物検出システムであって、
検出されるべき対象物を受信する対象物受信ユニットと、
前記ユーザ登録対象物に従って生成される複数の既存のサポートベクトルを備えた分類器に基づいて前記検出されるべき対象物を認識する対象物認識ユニットと、
前記分類器を更新するために、請求項１０記載の分類器の学習のための装置と、
を備えることを特徴とするシステム。
【請求項１４】
コンピュータを請求項１０記載の装置の各ユニットとして機能させるプログラムを記憶するコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、機械学習及びパターン認識に関し、特に、分類器の学習方法及び装置に関する。
【背景技術】
【０００２】
対象物検出及び対象物追跡の分野では、この数十年間、１クラス分類法が広く採用されてきた。Ｍｏｙａ、Ｍ及びＨｕｓｈ、Ｄの「Ｎｅｔｗｏｒｋ ｃｏｎｓｔｒａｉｎｔｓ ａｎｄ ｍｕｌｔｉ‐ｏｂｊｅｃｔｉｖｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｆｏｒ ｏｎｅ‐ｃｌａｓｓ ｃｌａｓｓｉｆｉｃａｔｉｏｎ」（Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ、９（３）：４６３‐４７４．ｄｏｉ：１０．１０１６／０８９３‐６０８０（９５）００１２０‐４、１９９６年）に記載されるように、１クラス分類法では、１つのクラスの対象物のみを含むトレーニング集合から学習することにより、そのクラスの対象物を可能な他のすべての対象物から弁別することが試みられる。
【０００３】
サポートベクトルデータ記述（ＳＶＤＤ）法は、１クラス分類の分野では強力なカーネル法である。Ｄ． Ｔａｘ及びＲ． Ｄｕｉｎの「Ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｄｏｍａｉｎ ｄｅｓｃｒｉｐｔｉｏｎ」（Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔ． Ｌｅｔｔ．、第２０巻、１１９１〜１１９９ページ、１９９９年１１月）に記載されるように、ＳＶＤＤ法は、目標トレーニングサンプルのすべて又は大部分を囲むような最小体積の球（最小球とも呼ばれる）を発見することを目指す。図１はＳＶＤＤ法を示す概略図である。最小球上の点はサポートベクトルと呼ばれ、サポートベクトルはトレーニングサンプルを囲むための最小球を表す。
【０００４】
ＳＶＤＤ法は学習容量が大きく且つ一般化性能を有するため、近年、種々の用途でＳＶＤＤは成果をあげている。ＳＶＤＤ法の性能及び精度は、トレーニングサンプルの代表的データ集合をどの程度利用可能であるかによって決まる。しかし、ビデオ監視及び画像検索などのいくつかのオンラインアプリケーションの場合、初期状態では十分な数のトレーニングサンプルがないので、ＳＶＤＤ法により十分な結果を残せないこともある。
【０００５】
この問題に対応するため、オンライン学習技術が導入された。オンライン学習技術において、まず、１つ又は少数のサンプルにより分類器の学習が実行され、その後、分類器はシステム実行の手順に伴って更新される。オンライン学習技術は、優れた適応能力を有し且つ限られた容量しか必要としないために大きな成功を収めた。オンラインＳＶＤＤ法及び増分ＳＶＤＤ法は、現在、リアルタイム対象物検出に広く使用されている技術であるが、共にサポートベクトル法に基づくオンライン学習方法である。
【０００６】
Ｄ．Ｍ．Ｊ． Ｔａｘ及びＰ． Ｌａｓｋｏｖの「Ｏｎｌｉｎｅ ＳＶＭ ｌｅａｒｎｉｎｇ：ｆｒｏｍ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｔｏ ｄａｔａ ｄｅｓｃｒｉｐｔｉｏｎ ａｎｄ ｂａｃｋ」（Ｃ． Ｍｏｌｉｎａ他編、Ｐｒｏｃ． ＮＮＳＰに掲載、２００３年、４９９〜５０８ページ）には、オンラインＳＶＤＤ法が説明されている。図２（ａ）は、オンラインＳＶＤＤ法を示す簡略化されたフローチャートである。まず、ＳＶＤＤに基づく元の分類器及び新たに追加されたラベル付きサンプル（すなわち正のサンプル）が取得される。いわゆる正のサンプルは、目標カテゴリに属すると判定されたサンプルである。次に、各サンプルの関係性が分類器によって計算される。更に、元の分類器の以前のトレーニングサンプル集合から最も関係性の低いサンプルが選択される。次に、新たなサンプルが追加され、新たに追加された正のサンプルに基づいて最も関係性の低いサンプルが除去される。最後に、残ったサンプル及び新たに追加されたサンプルを使用して、分類器は再学習される。
【０００７】
図２（ｂ）は、オンラインＳＶＤＤ法を示す概略図である。図２（ｂ）に示されるように、分類器の更新処理において、元のサンプル集合に含まれるサンプルは、新たに追加されたサンプルと置き換えられ、更新処理の中で分類器の超球面は徐々に拡大される。
【０００８】
Ｘｉａｏｐｅｎｇ Ｈｕａ及びＳｈｉｆｅｉ Ｄｉｎｇの「Ｉｎｃｒｅｍｅｎｔａｌ Ｌｅａｒｎｉｎｇ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｄａｔａ Ｄｅｓｃｒｉｐｔｉｏｎ」（ＪＯＵＲＮＡＬ ＯＦ ＳＯＦＴＷＡＲＥ、第６巻、第７号、２０１１年７月）では、増分ＳＶＤＤ法が説明されている。増分ＳＶＤＤ法において、ＳＶＤＤ増分学習は、トレーニングサンプル集合に新たなサンプルが追加された後に起こりうるサポートベクトル集合（ＳＶ）の変化を解析することにより実行される。図３（ａ）は、増分ＳＶＤＤ法を示す簡略化されたフローチャートである。まず、ＳＶＤＤに基づく元の分類器及び新たに追加されたラベル付きサンプルが取得される。次に、以前のトレーニング集合がサポートベクトル集合と、非サポートベクトル集合とに分割される。その後、元の分類器の超球面の外側に新たに追加されたサンプルが存在するか否かが検証される。存在する場合、それらのサンプルはトレーニングサンプル集合に追加される。次に、非サポートベクトル集合の中から、新たなサポートベクトルになる可能性が最も高いサンプルが発見される。最後に、元の分類器の超球面の外側にあるサンプルと、非サポートベクトル集合の中で新たなサポートベクトルになる可能性が最も高いサンプルと、サポートベクトル集合とを使用して、分類器が再学習される。
【０００９】
図３（ｂ）は、増分ＳＶＤＤ法を示す概略図である。図３（ｂ）に示されるように、分類器の更新処理において、分類器は、元の分類器の超球面の外側にあるサンプルと、非サポートベクトル集合の中で新たなサポートベクトルになる可能性が最も高いサンプルと、元のサポートベクトル集合とに基づいて更新され、更新処理の中で分類器の超球面は徐々に拡大される。
【００１０】
図２（ｂ）及び図３（ｂ）からわかるように、トレーニングサンプルの多様性が小さい場合、学習後の超球面は小さい。すなわち、分類器が小さなトレーニングサンプルの集合によりトレーニングされた場合、学習後の分類器の閾値は小さい。トレーニングサンプルの多様性が拡張されると、学習後の超球面も拡大される。すなわち、新たなサンプルが追加されると、学習後の分類器の閾値は大きくなる。
【００１１】
すなわち、トレーニングサンプルの数が増加するにつれて超球面は拡大されるので、学習後の分類器の性能は不安定になる。更に、新たに追加されたいくつかのサンプルが誤ってラベル付けされた場合（これは分類器による判定では常に自動的に起こる）、学習後の分類器の性能はいっそう悪化する。従って、オンラインＳＶＤＤ法及び増分ＳＶＤＤ法では、長い実行時間にわたり分類器の性能を安定したレベルに保持するために、サンプルを予め正確に（正又は誤と）ラベル付けしておく必要がある。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従って、従来の技術における問題に対処するための新規の技術が必要とされている。
【課題を解決するための手段】
【００１３】
本発明において、上記の問題を十分に解決する分類器の学習のための新規の方法及び装置が提供される。
【００１４】
本発明の１つの態様によれば、複数のサンプルを使用する分類器の学習の方法が提供される。方法は、ラベルなしサンプルを既存のサンプルに追加する追加ステップと、複数の既存のサポートベクトルを使用して、追加されたラベルなしサンプルから候補サンプルを抽出する抽出ステップと、複数の既存のサポートベクトルを使用して、候補サンプルから新たなサポートベクトルを選択する選択ステップとを備えることを特徴とする。
【００１５】
本発明の利点は、本発明によって、分類器の性能が不安定であるという問題を解決でき且つ高速計算を実現できることである。
【００１６】
本発明の別の利点は、本発明によって、ラベルなしサンプルを絶えず追加することにより学習後の分類器の性能を向上できることである。本発明は、学習の精度を保証するだけではなく、空間的及び時間的な複雑さを低減する。
【００１７】
本発明の更に別の利点は、本発明によって、拒絶率（誤警報率）を安定した低いレベルに調整でき且つ分類器の過剰トレーニングが回避されることである。
【００１８】
更に、本発明によれば、分類器を急速に学習させ且つ更新することができるので、デジタル製品において追跡を実現するための解法ともなりうる。
【００１９】
本発明の更なる特徴及びその利点は、添付の図面を参照して以下の本発明に係る例示的な実施形態の詳細な説明から明らかになるだろう。
【図面の簡単な説明】
【００２０】
本明細書の一部を構成する添付の図面は、本発明の実施形態を例示し且つ以下の説明と共に本発明の原理を説明するのに有用である。
添付の図面を参照して以下の詳細な説明を読むことにより、本発明は更によく理解されるだろう。
【図１】図１は、従来の技術におけるＳＶＤＤ法を示す概略図である。
【図２】図２は、従来の技術におけるオンラインＳＶＤＤ法を示す概略図であり、（ａ）は、その概略的なフローチャートであり、（ｂ）は、その概略的な原理図である。
【図３】図３は、従来の技術における増分ＳＶＤＤ法を示す概略図であり、（ａ）は、その概略的なフローチャートであり、（ｂ）は、その概略的な原理図である。
【図４】図４は、本発明の実施形態に係る分類器の学習の方法を示す原理図である。
【図５】図５は、本発明の実施形態に係る分類器の学習の方法を示す全体フローチャートである。
【図６】図６は、本発明の実施形態に係る候補サンプルを抽出する処理を示す詳細なフローチャートである。
【図７】図７は、本発明の実施形態に係る任意のサンプルからサポートベクトルの中心までの距離の計算におけるｆｍｉｎ、ｆｍａｘ−２ΣＪ＝１ＮΣｉ＝１Ｍαｉｘｉｊ、ｆｍａｘの関係図である。
【図８】図８は、本発明の実施形態に係る閾値の設定を示す原理図である。
【図９】図９は、本発明の実施形態に係る新たなサポートベクトルを選択する処理を示す詳細なフローチャートである。
【図１０】図１０は、本発明の実施形態に係るサポートベクトルを更新する処理を示す詳細なフローチャートである。
【図１１】図１１は、本発明の実施形態に係る分類器の学習のための装置を示す機能ブロック図である。
【図１２】図１２は、本発明の実施形態に係る処理装置を示す機能ブロック図である。
【図１３】図１３は、本発明の実施形態に係るユーザ登録対象物検出方法を示すフローチャートである。
【図１４】図１４は、本発明の実施形態に係るユーザ登録対象物検出システムを示す機能ブロック図である。
【図１５】図１５は、本発明の実施形態に係るコンピュータシステムのハードウェア構成を示すブロック図である。
【図１６】図１６は、本発明の実施形態に係る方法、オンラインＳＶＤＤ法及び増分ＳＶＤＤ法に関して３つのビデオに対する検出率及びＦＰＰＩの比較グラフである。
【図１７】図１７は、本発明の実施形態に係る方法及び従来の技術の他の３つの方法に関して追跡アプリケーションにおける平均誤り率を示すグラフである。
【図１８】図１８は、本発明の実施形態に係る方法及び従来の技術の他の３つの方法に関して追跡アプリケーションにおける例示的な結果を示す図である。
【発明を実施するための形態】
【００２１】
添付の図面を参照して、本発明の種々の例示的な実施形態を詳細に説明する。尚、実施形態において説明される構成要素の相対的配置及びステップの相対的配列、数式及び数値は、特に指示のない限り本発明の範囲を限定しない。
【００２２】
以下の少なくとも１つの例示的な実施形態の説明は本質的に単なる例であり、本発明、その適用又は用途を限定することをまったく意図しない。
【００２３】
当業者には周知である技術、方法及び装置は詳細に説明されない場合があるが、本明細書の一部を適宜構成することが意図される。
【００２４】
本明細書で示され且つ説明されるすべての例において、特定の値は、いずれも単なる例であり、本発明を限定すると解釈されるべきではない。従って、例示的な実施形態の他の例では値が異なることもありうるだろう。
【００２５】
尚、添付の図面中、同一の図中符号及び文字は類似する項目を示すので、１つの図においてある項目が定義されている場合、他の図でその項目を更に解説する必要はないと考えられる。
【００２６】
本発明は、分類器の学習の方法を提供することを目的とする。従来の方法とは異なり、本発明は、ラベルなしサンプル、すなわち正のサンプルとして判定されていないサンプルを指向する。
【００２７】
図４は、本発明の実施形態に係る分類器の学習の方法を示す原理図である。図４に示されるように、内側の円（最も小さい円）は、初期分類器が分類を実行するための元の超球面を示す。元の超球面は元のサンプルに従って生成され、その境界は、元のサポートベクトルにより定義される。この元の超球面により、サポートベクトルと非サポートベクトルとを識別できる。図４の外側の円（最大の円）は、すべてのサンプルが占める可能な限り大きな空間を表す最大超球面である。本実施形態において、元の超球面と最大超球面との間で決定超球面を判定することが望ましく、どの正のサンプルに関しても、この決定超球面の中に入る確率は安定している。正のサンプルがこの決定超球面に入る確率を調整することにより、超球面の大きさは変更可能である。この決定超球面によって、追加されたラベルなしサンプルが正のサンプルであるか否かを判定できる。
【００２８】
図４に示されるように、新たに追加されたラベルなしサンプルが最大超球面と決定超球面との間に位置する場合、それらのサンプルは正のサンプルとは判定されず、以前の分類器が維持される。新たに追加されたラベルなしサンプルが元の超球面の内側に位置する場合、それらのサンプルは正のサンプルとして判定されるが、以前のサポートベクトル集合を変更させることはなく、この場合にも以前の分類器が維持される。新たに追加されたラベルなしサンプルが元の超球面と決定超球面との間にある場合、それらのサンプルは正のサンプルとして判定され、以前のサポートベクトル集合を変更させる。
【００２９】
言い換えると、分類器の学習の方法において、分類器は、元の超球面と決定超球面との間に入るサンプルによってのみ更新される。本実施形態に係る方法では、分類器の性能が不安定であるという問題を解決でき且つ迅速な計算を実現できる。ラベルなしサンプルを絶えず追加することにより、学習後の分類器の性能を向上できる。本発明によれば、学習精度が保証されるだけではなく、空間的及び時間的な複雑さも軽減される。
【００３０】
図５は、本発明の実施形態に係る分類器の学習の方法を示す全体フローチャートである。図５に示されるように、新たな分類器を取得するために、新たに追加されたラベルなしサンプルによって元の分類器を再度学習させることが望ましい。まず、ステップ５において、いくつかのラベルなしサンプルが既存のサンプルに追加される。
【００３１】
ステップ１０において、複数の既存のサポートベクトルを使用して、追加されたラベルなしサンプルから新たなサポートベクトルの候補サンプルが抽出される。
【００３２】
図６は、本発明の実施形態に係る候補サンプルを抽出する処理を示す詳細なフローチャートである。まず、ステップ１１０において、サンプルのうちいずれかのサンプルからすべてのサポートベクトルの中心までの最長距離が推定される。すなわち、元の分類器のサポートベクトル（特徴空間内のサポートベクトル）に従って、可能最大限の超球面が生成される。
【００３３】
可能最大限の超球面は、上述のサポートベクトルデータ記述（ＳＶＤＤ）アルゴリズムを使用して生成される。すなわち、超球面の中心に対する最大半径Ｒｍａｘが判定される。トレーニングサンプルの大半又はすべては、この最大超球面の中に囲い込まれる。最大超球面は、次の式（１）を使用して構成される。
【００３４】
【数１】
0005570629.tif 000002
【００３５】
式中、ｘｉはサポートベクトルを表し、Ｃはペナルティ係数であり、ξｉはスラック誤差である。
【００３６】
式（１）にラグランジュ乗数を適用すると、次のように双対問題を取得できる。
【００３７】
【数２】
0005570629.tif 000003
【００３８】
式中、Ｋ（・）は非負関数値を有するカーネル関数である。本明細書において、カーネル関数Ｋ（・）は、特徴空間内の任意の正規化特徴ベクトルｚに対して一定であるとして選択される。すなわち、Ｋ（ｚ，ｚ）は一定である。
【００３９】
一実施形態において、ヒストグラムインタセクションカーネル（ＨＩＫ）関数を選択できる（例えば、http://c2inet.sce.ntu.edu.sg/ Jianxin/projects/libHIK/libHIK_v2.pdfを参照）。
【００４０】
【数３】
0005570629.tif 000004
【００４１】
式中、Ｔ，Ｑは特徴のヒストグラムであり、Ｎはヒストグラムの次元である。
【００４２】
尚、本実施形態では式（３）のＨＩＫ関数を例にとって説明するが、へリンガーのカーネル関数及びジェンセン‐シャノンカーネル関数も選択できることは当業者により理解されるべきである。
【００４３】
式（２）の双対最適化問題の解によって、サポートベクトルの集合ｘｉ∈ＳＶｓ及び対応する重みαｉを取得できる。
【００４４】
上記のＳＶＤＤ法により取得されたサポートベクトルｘｉ及び重みαｉから、可能最大限の超球面の半径Ｒｍａｘが計算される。所定のラベルなしサンプルに関して、この半径から正規化特徴ベクトルｚが生成され、超球面の中心までの距離を次のように計算できる。
【００４５】
【数４】
0005570629.tif 000005
【００４６】
ｆ（ｚ）＝Ｒｚ２≦Ｒ２であれば、特徴ベクトルｚは超球面の内側に入っており、この特徴ベクトルは目標対象物カテゴリに分類される。そこで、超球面の半径の二乗、すなわちＲ２が分類器の閾値として定義される。
【００４７】
式（４）によれば、ラベルなしサンプルに基づいて生成された特徴ベクトルｚに関して、超球面の中心までの距離が計算される。この距離は超球面の半径以下である。すなわち、次の式が成立する。
【００４８】
【数５】
0005570629.tif 000006
【００４９】
ここで、サポートベクトルの中心の位置を発見することが試みられるのではなく、いずれかのラベルなしサンプルの特徴ベクトルから中心までの距離関数を判定することが望まれる。
【００５０】
可能最大限の超球面の半径Ｒｍａｘを解くために、式（４）に従って、次の式を取得できる。
【００５１】
【数６】
0005570629.tif 000007
【００５２】
先に述べた通り、任意の正規化特徴ベクトルｚに関して、Ｋ（ｚ，ｚ）は一定である。サポートベクトルｘｉ∈ＳＶｓ及び対応する重みαｉが式（２）に従って計算される場合、
【００５３】
【数７】
0005570629.tif 000008
【００５４】
は一定の値を有する。従って、ｆｍａｘを解く鍵は、
【００５５】
【数８】
0005570629.tif 000009
【００５６】
の最小値を取得することである。前述のように、カーネル関数Ｋ（・）は非負であるので、
【００５７】
【数９】
0005570629.tif 000010
【００５８】
となる。
【００５９】
従って、式（５）を次のように簡略化できる。
【００６０】
【数１０】
0005570629.tif 000011
【００６１】
このように、上記の式（６）から最大超球面の半径Ｒｍａｘが判定される。Ｋ（・）はＨＩＫカーネルであり且つベクトルｚは正規化されているので、どの特徴ベクトルｚに対してもＫ（ｚ，ｚ）は一定になる。すべてのサポートベクトルが一定であれば、
【００６２】
【数１１】
0005570629.tif 000012
【００６３】
は一定である。従って、すべてのサポートベクトルが判定された場合、どの特徴ベクトルｚに対してもｆｍａｘは一定である。
【００６４】
次に、図６のステップ１２０を参照すると、いずれかのサンプルから中心までの最短距離が推定される。すなわち、可能最小限の超球面が生成される（最短距離ｆｍｉｎが判定される）。
【００６５】
上記の式（４）によれば、最短距離ｆｍｉｎを次のように表すことができる。
【００６６】
【数１２】
0005570629.tif 000013
【００６７】
前述のように、すべてのサポートベクトルの判定が完了した条件の下では、任意の正規化特徴ベクトルｚに対して、ｆｍｉｎは一定である。従って、ｆｍｉｎを解くことを
【００６８】
【数１３】
0005570629.tif 000014
【００６９】
の最大値を解くことに変換できる。カーネル関数の定義から、
【００７０】
【数１４】
0005570629.tif 000015
【００７１】
は特定の値でなければならないが、＋∞であってはならないことがわかる。
【００７２】
本例では、説明の便宜上、ＨＩＫ関数が選択されている。計算を高速化するために、次のようにルックアップテーブルｌｕｔが定義される。
【００７３】
【数１５】
0005570629.tif 000016
【００７４】
式中、ｘｉｊ∈Ｘｉ、Ｘｉ∈ＳＶｓであり、Ｍはサポートベクトルの数であり、Ｎはサポートベクトルの次元である。
【００７５】
上記の式（８）から、
【００７６】
【数１６】
0005570629.tif 000017
【００７７】
であることがわかるが、以下に詳細に説明するように、ｍａｘ（ｌｕｔ）は必ずしも
【００７８】
【数１７】
0005570629.tif 000018
【００７９】
と等しくない。ｍａｘ（ｌｕｔ）が
【００８０】
【数１８】
0005570629.tif 000019
【００８１】
の形態をとることができる場合、これは、最小超球面の内側にただ１つの特徴ベクトルが存在していることを意味する。そのような場合、この特徴ベクトルを超球面の中心と判定でき、
【００８２】
【数１９】
0005570629.tif 000020
【００８３】
と判定される。
【００８４】
図７は、本発明の実施形態に従っていずれかのサンプルからサポートベクトルの中心までの距離を計算する際のｆｍｉｎ、
【００８５】
【数２０】
0005570629.tif 000021
【００８６】
、ｆｍａｘの関係図を示す。図７を参照すると、最小超球面の内側の特徴ベクトルがただ１つではなく複数ある場合、
【００８７】
【数２１】
0005570629.tif 000022
【００８８】
である。この場合、ｆｍｉｎを推定しなければならない。すなわち、ｍａｘ（ｌｕｔ）を推定しなければならない。
【００８９】
ＨＩＫカーネル関数の例では、ｊ番目の次元に関して、これは次のように定義される。
【００９０】
【数２２】
0005570629.tif 000023
【００９１】
Ｈｊの平均値は
【００９２】
【数２３】
0005570629.tif 000024
【００９３】
と定義され、式（８）に従って、
【００９４】
【数２４】
0005570629.tif 000025
【００９５】
となる。従って、Ｎ次元の特徴ベクトルｚｊに関して、ｌｕｔの最大値を推定することは、Ｎ個の次元のｌｕｔの平均値の最大値を推定すること、すなわち
【００９６】
【数２５】
0005570629.tif 000026
【００９７】
を推定することと同等である。以下の説明中、
【００９８】
【数２６】
0005570629.tif 000027
【００９９】
の範囲は、統計学の分野における標本推定理論を使用して推定される。
【０１００】
中心極限定理によれば、
【０１０１】
【数２７】
0005570629.tif 000028
【０１０２】
は標本空間内の正規分布を満たす。従って、確率Φｚは、特に次のような累積分布である。
【０１０３】
【数２８】
0005570629.tif 000029
【０１０４】
中心極限定理によれば、次の通りになる。
【０１０５】
【数２９】
0005570629.tif 000030
【０１０６】
【数３０】
0005570629.tif 000031
【０１０７】
によれば、標準正規累積分布関数のルックアップテーブルからλｚを取得でき、
【０１０８】
【数３１】
0005570629.tif 000032
【０１０９】
の範囲は
【０１１０】
【数３２】
0005570629.tif 000033
【０１１１】
と判定される。その結果として、
【０１１２】
【数３３】
0005570629.tif 000034
【０１１３】
が判定される。
【０１１４】
最後に、式（１１）の結果を式（７）に代入することにより、ｆｍｉｎの推定値を取得できる。
【０１１５】
次に、図６に戻って説明する。ステップ１３０において、ステップ１２０で計算されたｆｍｉｎ及びステップ１１０で計算されたｆｍａｘを使用して決定超球面が生成される。
【０１１６】
図８は、本発明の実施形態に係る閾値の設定を示す原理図である。図８を参照すると、ステップ４１０において、最大超球面の面積が計算される。
【０１１７】
【数３４】
0005570629.tif 000035
【０１１８】
ｆ（ｚ）は、［ｆｍｉｎ、ｆｍａｘ］の間でほぼ同一の型の分布を有する。以下の説明中、パラメータＰ、すなわち決定超球面の面積と最大超球面の面積との比を表す値を想定する。ステップ１２０で計算されたＲｍｉｎ及びステップ１１０で計算されたＲｍａｘを使用して、決定超球面の半径ＲＴが生成される。パラメータＰは次のように定義される。
【０１１９】
【数３５】
0005570629.tif 000036
【０１２０】
式（１３）によれば、決定超球面の半径ＲＴは次のように判定される。
【０１２１】
【数３６】
0005570629.tif 000037
【０１２２】
式（１４）によれば、特徴ベクトルｚに対して適切な閾値、すなわちｆＴ（ｚ）が推定される。最後に、すべてのサポートベクトルＸｉ∈ＳＶｓに対してｆＴが推定される。
【０１２３】
【数３７】
0005570629.tif 000038
【０１２４】
ｆＴはトレーニング後の分類器の閾値である。利用可能なトレーニングサンプルの数及びどのようなトレーニングサンプルを利用可能であるかにかかわらず、分類器の誤検出率（false positive rate）は、パラメータＰによりあるレベル以下に安定して調整される。すなわち、どの正特徴ベクトルに関しても、生成された決定超球面の中に含まれる確率は一定である。すなわち、分類器の性能をパラメータＰにより調整可能である。
【０１２５】
次に、図６のステップ１４０により示されるように、図６のステップ１３０で設定された閾値に従って、新たに追加されたラベルなしサンプルが候補サンプルであるか否かが判定される。新たに追加されたラベルなしサンプルに関して、そのサンプルに基づいて特徴ベクトルｚが抽出される。式（４）を使用して、特徴ベクトルｚから既存の分類器のサポートベクトルの中心までの距離が計算される。次に、この距離は、図６のステップ１３０で設定された閾値と比較される。
【０１２６】
サンプルの特徴ベクトルｚから中心までの距離が閾値より小さい場合、そのサンプルは候補サンプルとして判定される。サンプルの特徴ベクトルｚから中心までの距離が閾値を超える場合、そのサンプルは候補サンプルとして判定されない。
【０１２７】
図５に戻ると、図５のステップ２０において、複数の既存のサポートベクトルを使用して、候補サンプルから新たなサポートベクトルが選択される。図９は、本発明の実施形態に係る新たなサポートベクトルを選択する処理を示す詳細なフローチャートである。
【０１２８】
まず、ステップ２１０において、複数の既存のサポートベクトルに従ってバウンディング超球面が描出される。既知の分類器に関して、最適な解ａ＊＝［ａ１、ａ２、…ａｌ］により、どのトレーニングサポートベクトルｘｉもＫＫＴ（カラッシュ‐クーン‐タッカー）の条件を次のように満たす。
【０１２９】
【数３８】
0005570629.tif 000039
【０１３０】
式中、ｄｉ２は、ｘｉからサポートベクトルの中心までの距離である。従って、サポートベクトルのバウンディング超球面は、半径Ｒ２の超球面である。ＫＫＴ条件は当業者には周知であるので、ここでは詳細に説明しない。
【０１３１】
次に、ステップ２２０において、ステップ２１０で取得されたバウンディング超球面に従って、候補サンプルが新たなサポートベクトルであるか否かが判定される。上記のＫＫＴ条件によれば、候補サンプル、すなわち目標トレーニングデータは次の３つのカテゴリに分類可能である。
【０１３２】
１）ａｉ＝０が球の内側にあるデータポイント。
【０１３３】
２）０＜ａｉ＜Ｃが球境界上にあるデータポイント。
【０１３４】
３）ａｉ＝Ｃが球の外側にあり且つ零でないξｉを有するデータポイント。
【０１３５】
図４に示されるように、最小超球面の内側にあるサンプルは、以前のサポートベクトル集合を変更させず、以前の分類器が維持される。閾値に対して最大超球面と決定超球面との間に位置するサンプルは、以前のサポートベクトル集合を変更させる。従って、候補サンプルがバウンディング超球面の外側にある場合、その候補サンプルは新たなサポートベクトルとして選択される。
【０１３６】
図５に戻ると、本発明に係る分類器の学習の方法は、任意のステップ３０を含む。言い換えれば、ステップ３０は省略されてもよい。図５のステップ３０において、既存のサポートベクトルの一部が新たなサポートベクトルと置き換えられる。図１０は、本発明の実施形態に係るサポートベクトルを更新する処理を示す詳細なフローチャートである。
【０１３７】
図１０のステップ３１０において、式（４）に従って、各サポートベクトルから超球面の中心までの距離が計算される。その結果はＶ＝［ｄ１，ｄ２，…ｄｎ］である。式中、ｄは距離であり、ｎはサポートベクトルの数である。
【０１３８】
ステップ３２０において、Ｖ＝［ｄ１，ｄ２，…ｄｎ］における距離ｄが昇順に再配列され、Ｖ’＝［ｄ’１，ｄ’２，…ｄ’ｎ］が取得される。式中、ｄ’１は最も近い距離であり、ｄ’ｎは最も遠い距離である。次に、最も近い距離を有するサポートベクトルが新たなサポートベクトルと置き換えられ且つサポートベクトルのカウントが一定に維持される。例えば、３つの新たなサポートベクトルがある場合、最も近い距離を有する３つの元のサポートベクトルが置き換えられる。図１０の動作により、新たなサポートベクトルの集合が取得される。
【０１３９】
図５に戻ると、本発明の実施形態に係る分類器の学習の方法は、別の任意のステップ４０を含む。言い換えれば、ステップ４０は省略されてもよい。図５のステップ４０において、すべてのサポートベクトルの重みが更新される。Ｊｏｈｎ Ｃ． Ｐｌａｔｔの「Ｓｅｑｕｅｎｔｉａｌ Ｍｉｎｉｍａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ：Ａ Ｆａｓｔ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｔｒａｉｎｉｎｇ Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅｓ」（ｈｔｔｐ：／／ｒｅｓｅａｒｃｈ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ／ｐｕｂｓ／６９６４４／ｔｒ‐９８‐１４．ｐｄｆ）には、サポートベクトルマシンをトレーニングする高速アルゴリズム、すなわち逐次最小最適化（ＳＭＯ）法が開示されている。Ｃｈｉｈ‐Ｃｈｕｎｇ Ｃｈａｎｇ及びＣｈｉｈ‐Ｊｅｎ Ｌｉｎの、ＬＩＢＳＶＭ：ａ ｌｉｂｒａｒｙ ｆｏｒ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ，２００１、ｈｔｔｐ：／／ｃｓｉｅ．ｎｔｕ．ｅｄｕ．ｔｗ／〜ｃｊｌｉｎ／ｌｉｂｓｖｍで利用可能なソフトウェア）には、サポートベクトルマシンのライブラリが開示されている。ＳＭＯ法は、大規模な二次計画（ＱＰ）最適化問題を一連の可能な限り小さなＱＰ問題に分解する。それらの小さなＱＰ問題は解析的に解決されるので、多大な時間を要する数値ＱＰ最適化を内部ループとして使用する必要はない。ＬＩＢＳＶＭはＳＶＭのライブラリであり、現在、最も広く使用されているＳＶＭソフトウェアの１つである。上記の参考文献に記載される方法は、共に参考として本明細書にすべての内容が取り入れられている。分類器のすべてのサポートベクトルの重みは、ＳＭＯ方法を使用してＬＩＢＳＶＭライブラリによって更新される。すなわち、分類器は再学習される。
【０１４０】
図１１は、本発明の実施形態に係る分類器の学習のための装置１０００を示す機能ブロック図である。本発明の原理を実行するために、装置１０００の機能ブロックは、ハードウェア、ソフトウェア又はハードウェアとソフトウェアとの組み合わせにより実現される。先に説明したように本発明の原理を実現するために、図１１に示される機能ブロックが組み合わされるか又はサブブロックに分割されてもよいことは当業者により理解される。従って、以下の説明は、本明細書中で説明される機能ブロックについて可能なすべての組み合わせ又は分割又は更なる定義をサポートするだろう。
【０１４１】
図１１に示されるように、一実施形態によれば、分類器の学習のための装置１０００は、追加ユニット１０５０と、抽出ユニット１１００と、選択ユニット１２００とを備える。追加ユニット１０５０は、ラベルなしサンプルを既存のサンプルに追加する。抽出ユニット１１００は、複数の既存のサポートベクトルを使用して、追加されたラベルなしサンプルから新たなサポートベクトルの候補サンプルを抽出する。選択ユニット１２００は、複数の既存のサポートベクトルを使用して、候補サンプルから新たなサポートベクトルを選択する。
【０１４２】
別の実施形態によれば、本発明の実施形態に係る分類器の学習のための装置１０００は、サポートベクトル置き換えユニット１３００を更に備えても良い。サポートベクトル置き換えユニット１３００は、既存のサポートベクトルのうちのいくつかを新たなサポートベクトルと置き換える。
【０１４３】
別の実施形態によれば、本発明の実施形態に係る分類器の学習のための装置１０００は、重み更新ユニット１４００を更に備えても良い。重み更新ユニット１４００は、すべてのサポートベクトルの重みを更新する。
【０１４４】
別の実施形態によれば、抽出ユニット１１００は、第１の推定ユニット１１１０と、第２の推定ユニット１１２０と、設定ユニット１１３０と、第１の判定ユニット１１４０とを更に備えても良い。第１の推定ユニット１１１０は、いずれかのサンプルからすべてのサポートベクトルの中心までの最長距離を推定する。第２の推定ユニット１１２０は、いずれかのサンプルから中心までの最短距離を推定する。設定ユニット１１３０は、新たに追加されたラベルなしサンプルが正のサンプルであるか否かを判断するために最長距離と最短距離との間で閾値を設定する。第１の判定ユニット１１４０は、新たに追加されたラベルなしサンプルが候補サンプルであるか否かを閾値に従って判定する。
【０１４５】
閾値は、どの正のサンプルに関しても、そのサンプルが閾値以内に入る確率を一定にするように設定されるのが好ましい。
【０１４６】
別の実施形態によれば、選択ユニット１２００は、描出ユニット１２１０と、第２の判定ユニット１２２０とを更に備えても良い。描出ユニット１２１０は、複数の既存のサポートベクトルに従ってバウンディング超球面を描出する。第２の判定ユニット１２２０は、候補サンプルが新たなサポートベクトルであるか否かを判定する。候補サンプルがバウンディング超球面の外側にある場合、その候補サンプルは新たなサポートベクトルとして選択されるが、候補サンプルがバウンディング超球面の内側にある場合、その候補サンプルは新たなサポートベクトルとして選択されない。
【０１４７】
別の実施形態によれば、サポートベクトル置き換えユニット１３００は、計算ユニット１３１０と、置き換えユニット１３２０とを更に備えても良い。計算ユニット１３１０は、各サポートベクトルから中心までの距離を計算する。置き換えユニット１３２０は、最も近い距離のサポートベクトルを新たなサポートベクトルと置き換え且つサポートベクトルのカウントを一定に維持する。
【０１４８】
第１の推定ユニットでは、サポートベクトルデータ記述（ＳＶＤＤ）アルゴリズムが使用されるのが好ましい。
【０１４９】
第１の推定ユニット及び第２の推定ユニットでは、カーネル関数Ｋ（・）が使用されるのが好ましい。このカーネル関数は、どの正規化ベクトルｚに対してもＫ（ｚ，ｚ）が一定であるように選択される。
【０１５０】
カーネル関数Ｋ（・）はヒストグラムインタセクションカーネル（ＨＩＫ）を含むのが好ましい。
【０１５１】
図１２は、本発明の実施形態に係る処理装置２０００を示す機能ブロック図である。本発明の原理を実行するために、処理装置２０００の機能ブロックは、ハードウェア、ソフトウェア又はハードウェアとソフトウェアとの組み合わせにより実現される。先に説明したような本発明の原理を実現するために、図１２に示される機能ブロックが組み合わされるか又はサブブロックに分割されてもよいことは当業者には理解される。従って、以下の説明は、本明細書中で説明される機能ブロックについて可能なあらゆる組み合わせ又は分割又は更なる定義をサポートするだろう。
【０１５２】
図１２に示されるように、一実施形態によれば、処理装置２０００は、分類器２１００と、受信ユニット２２００と、抽出ユニット１１００と、選択ユニット１２００とを備える。分類器２１００は複数の既存のサポートベクトルを使用する。受信ユニット２２００は、新たに追加されたラベルなしサンプルを受信する。抽出ユニット１１００は、複数の既存のサポートベクトルを使用して、追加されたラベルなしサンプルから新たなサポートベクトルの候補サンプルを抽出する。選択ユニット１２００は、複数の既存のサポートベクトルを使用して、候補サンプルから新たなサポートベクトルを選択する。
【０１５３】
別の実施形態によれば、処理装置２０００はサポートベクトル置き換えユニット１３００を更に備える。サポートベクトル置き換えユニット１３００は、分類器のいくつかのサポートベクトルを新たなサポートベクトルと置き換える。
【０１５４】
別の実施形態によれば、処理装置２０００は重み更新ユニット１４００を更に備える。重み更新ユニット１４００は、分類器のすべてのサポートベクトルの重みを更新する。
【０１５５】
別の実施形態によれば、抽出ユニット１１００は、第１の推定ユニット１１１０と、第２の推定ユニット１１２０と、設定ユニット１１３０と、第１の判定ユニット１１４０とを更に備える。第１の推定ユニット１１１０は、いずれかのサンプルからすべてのサポートベクトルの中心までの最長距離を推定する。第２の推定ユニット１１２０は、いずれかのサンプルから中心までの最短距離を推定する。設定ユニット１１３０は、新たに追加されたラベルなしサンプルが正のサンプルであるか否かを判断するために最長距離と最短距離との間で閾値を設定する。第１の判定ユニット１１４０は、新たに追加されたラベルなしサンプルが候補サンプルであるか否かを閾値に従って判定する。
【０１５６】
閾値は、どの正のサンプルに関しても、そのサンプルが閾値以内に入る確率が一定になるように設定されるのが好ましい。
【０１５７】
別の実施形態によれば、選択ユニット１２００は、描出ユニット１２１０と第２の判定ユニット１２２０とを更に備える。描出ユニット１２１０は、複数の既存のサポートベクトルに従ってバウンディング超球面を描出する。第２の判定ユニット１２２０は、候補サンプルが新たなサポートベクトルであるか否かを判定する。候補サンプルがバウンディング超球面の外側にある場合、その候補サンプルは新たなサポートベクトルとして選択されるが、候補サンプルがバウンディング超球面の内側にある場合、その候補サンプルは新たなサポートベクトルとして選択されない。
【０１５８】
別の実施形態によれば、サポートベクトル置き換えユニット１３００は、計算ユニット１３１０と、置き換えユニット１３２０とを更に備える。計算ユニット１３１０は、各サポートベクトルから中心までの距離を計算する。置き換えユニット１３２０は、最も近い距離のサポートベクトルを新たなサポートベクトルと置き換え且つサポートベクトルのカウントを一定に維持する。
【０１５９】
第１の推定ユニットでは、サポートベクトルデータ記述（ＳＶＤＤ）アルゴリズムが使用されるのが好ましい。
【０１６０】
第１の推定ユニット及び第２の推定ユニットでは、カーネル関数Ｋ（・）が使用されるのが好ましい。このカーネル関数は、どの正規化ベクトルｚに対してもＫ（ｚ，ｚ）が一定であるように選択される。
【０１６１】
カーネル関数Ｋ（・）はヒストグラムインタセクションカーネル（ＨＩＫ）を含むのが好ましい。
【０１６２】
図１３は、本発明の実施形態に係るユーザ登録対象物検出方法を示すフローチャートである。図１３に示されるように、ステップ３１００において、検出されるべき対象物が受信される。例えば、検出されるべき対象物は画像又はビデオである。ステップ３２００において、分類器が呼び出される。分類器は、ユーザ登録対象物に従って生成された複数の既存のサポートベクトルを含む。ステップ３３００において、検出されるべき対象物が分類器に基づいて認識される。検出されるべき対象物を分類器に基づいて認識する処理は当業者には周知であるので、ここでは詳細に説明しない。ステップ３４００において、本発明の原理に従った分類器の学習の方法を使用して分類器が更新される。従って、新たな対象物が次に入力された場合、検出を実行するために更新済みの分類器を使用できる。
【０１６３】
図１４は、本発明の実施形態に係るユーザ登録対象物検出システムを示す機能ブロック図である。図１４において、ユーザ登録対象物検出システム４０００は、対象物受信ユニット４１００と、対象物認識ユニット４２００と、本発明の原理に従った分類器の学習のための装置１０００とを備える。対象物受信ユニット４１００は、検出されるべき対象物を受信する。例えば、検出されるべき対象物は画像又はビデオである。対象物認識ユニット４２００は、検出されるべき対象物を分類器に基づいて認識する。分類器は、ユーザ登録対象物に従って生成された複数の既存のサポートベクトルを含む。検出されるべき対象物を分類器に基づいて認識する処理は当業者には周知であるので、ここでは詳細に説明しない。本発明の原理に従った分類器の学習のための装置１０００は、分類器を更新する。従って、新たな対象物が次に入力された場合、検出を実行するために更新済みの分類器を使用できる。
【０１６４】
図１５は、本発明の実施形態に係るコンピュータシステム５０００のハードウェア構成を示すブロック図である。
【０１６５】
図１５に示されるように、コンピュータシステムはコンピュータ５１１０を備える。コンピュータ５１１０は、処理ユニット５１２０と、システムメモリ５１３０と、着脱不可能な不揮発性メモリインタフェース５１４０と、着脱可能な不揮発性メモリインタフェース５１５０と、ユーザ入力インタフェース５１６０と、ネットワークインタフェース５１７０と、ビデオインタフェース５１９０と、出力周辺装置インタフェース５１９５とを備え、これらの構成要素はシステムバス５１２１を介して接続されている。
【０１６６】
システムメモリ５１３０は、ＲＯＭ（読み取り専用メモリ）５１３１及びＲＡＭ（ランダムアクセスメモリ）５１３２を備える。ＲＯＭ５１３１にはＢＩＯＳ（基本入出力システム）５１３３が常駐する。ＲＡＭ５１３２には、オペレーティングシステム５１３４、アプリケーションプログラム５１３５、他のプログラムモジュール５１３６及びいくつかのプログラムデータ５１３７が常駐する。
【０１６７】
ハードディスクなどの着脱不可能な不揮発性メモリ５１４１は、着脱不可能な不揮発性メモリインタフェース５１４０に接続される。着脱不可能な不揮発性メモリ５１４１は、例えばオペレーティングシステム５１４４、アプリケーションプログラム５１４５、他のプログラムモジュール５１４６及びいくつかのプログラムデータ５１４７を記憶する。
【０１６８】
フロッピー（登録商標）ドライブ５１５１及びＣＤ‐ＲＯＭドライブ５１５５などの着脱可能な不揮発性メモリは、着脱可能な不揮発性メモリインタフェース５１５０に接続される。例えば、フロッピー（登録商標）ドライブ５１５１にはフロッピーディスク５１５２を挿入可能であり、ＣＤ‐ＲＯＭドライブ５１５５にはＣＤ（コンパクトディスク）５１５６を挿入可能である。
【０１６９】
マイク５１６１及びキーボード５１６２などの入力デバイスは、ユーザ入力インタフェース５１６０に接続される。
【０１７０】
コンピュータ５１１０は、ネットワークインタフェース５１７０を介してリモートコンピュータ５１８０に接続可能である。例えば、ネットワークインタフェース５１７０は、ローカルエリアネットワーク５１７１を介してリモートコンピュータ５１８０に接続される。あるいは、ネットワークインタフェース５１７０はモデム（変復調器）５１７２に接続可能であり、モデム５１７２は、ワイドエリアネットワーク５１７３を介してリモートコンピュータ５１８０に接続される。
【０１７１】
リモートコンピュータ５１８０は、リモートアプリケーションプログラム５１８５を記憶するハードディスクなどのメモリ５１８１を備える。
【０１７２】
ビデオインタフェース５１９０はモニタ５１９１に接続される。
【０１７３】
出力周辺装置インタフェース５１９５は、プリンタ５１９６及びスピーカ５１９７に接続される。
【０１７４】
図１５に示されるコンピュータシステムは単なる例であり、本発明、その適用又は使用を限定することはまったく意図されていない。
【０１７５】
図１５に示されるコンピュータシステムは、スタンドアローンのコンピュータとして又は１つの装置の中の処理システムとして、あらゆる実施形態に実現され、１つ以上の不要な構成要素が除去されること又は１つ以上の追加構成要素が追加されることも可能である。
【０１７６】
本発明の原理に従った分類器の学習の方法と従来の他の方法とを試験により比較した例を示す。尚、本明細書において示される例は、本発明の技術的効果の利点を示すための単なる例であり、限定的な意味を持たない。
【０１７７】
ユーザ登録対象物検出（ＵＲＯＤ）システムにおいて、本発明に係る分類器の学習の方法が使用される。指定対象物のワンショットサンプルがユーザにより提供される。ユーザ登録対象物を検出するために、所定のサンプルからＳＶＤＤに基づく分類器が取得される。画像にウィンドウが（可能であれば複数のスケールで）設定され、各ローカルウィンドウを目標を含むウィンドウ又は背景を含むウィンドウとして分類するために、ウィンドウは画像に沿ってスライドされる。次に、検出された対象物を使用して分類器が更新される。画像領域記述のための特徴は、色及び局所三つ組パターン（ＬＴＰ）である。その後、更新後の検出器により次のフレームが検出される。
【０１７８】
表１は、試験の際のハードウェア構成及びソフトウェア構成を示す。
【０１７９】
【表１】
0005570629.tif 000040
【０１８０】
評価例１
異なる種類の動物を含む８つのビデオを無作為に選択する。それらのビデオは、すべてハンドヘルドカメラにより撮影された。ビデオ中の多くのフレームは、非合焦又は動きによってぶれており、視点の変化及び目標の歪みは非常に大きい。加えて、照明条件も頻繁に変化していた。評価に際して、評価基準としてＰＡＳＣＡＬ基準を選択した。Ｍ． Ｅｖｅｒｉｎｇｈａｍ、Ａ． Ｚｉｓｓｅｒｍａｎ、Ｃ．Ｋ．Ｉ． Ｗｉｌｌｉａｍｓ及びＬ． Ｇｏｏｌの「Ｔｈｅ ＰＡＳＣＡＬ Ｖｉｓｕａｌ Ｏｂｊｅｃｔ Ｃｌａｓｓｅｓ Ｃｈａｌｌｅｎｇｅ ２００６（ＶＯＣ２００６） Ｒｅｓｕｌｔｓ」（ｈｔｔｐ：／／ｗｗｗ．ｐａｓｃａｌ‐ｎｅｔｗｏｒｋ．ｏｒｇ／ｃｈａｌｌｅｎｇｅｓ／ＶＯＣ／ｖｏｃ２００６／ｒｅｓｕｌｔｓ．ｐｄｆ）に、ＰＡＳＣＡＬ基準が説明されている。上記の参考文献は、参考として本明細書に内容全体が取り入れられている。（ラベル付け領域∩検出領域）／（ラベル付け領域Ｕ検出領域）＞Ｔである場合、検出領域は正しい検出領域であるとみなされる。すなわち、その検出領域は正のサンプルである。この例では、Ｔは０．５に設定される。本発明の実施形態に係る方法をオンラインＳＶＤＤ法及び増分ＳＶＤＤ法と比較した。その比較結果を表２に示す。
【０１８１】
【表２】
0005570629.tif 000041
【０１８２】
表２に示されるように、本発明に係る分類器の学習の方法を対象物検出に使用した場合、オンラインＳＶＤＤ法及び増分ＳＶＤＤ法と比較して拒絶率を大幅に減少でき、我々の方法の検出率は、オンラインＳＶＤＤ法より高く、増分ＳＶＤＤ学習に匹敵する。更に、本発明に係る分類器の学習の方法の学習速度もオンラインＳＶＤＤ法の学習速度より速い。
評価例２
それぞれ１つの対象物を含む３つのビデオシーケンスを評価試験のために選択する。各対象物のビデオに対して、ただ１つのサンプルを提供し、透視変換を使用して、合わせて５０のサンプルをシミュレートした。それらのサンプルをトレーニングに使用した。本発明に係る方法、オンラインＳＶＤＤ法及び増分ＳＶＤＤ法を使用して検出試験を実施した。各フレームの対象物を検出した後、すべての検出フレームに対して検出率及びＦＰＰＩ（画像ごとの誤検出率）を計算した。
【０１８３】
図１６は、本発明に係る方法、オンラインＳＶＤＤ法及び増分ＳＶＤＤ法に関して３つのビデオに対する検出率及びＦＰＰＩを比較して示すグラフである。図１６において、図中符号１、２及び３は、本発明に係る方法、オンラインＳＶＤＤ法及び増分ＳＶＤＤ法をそれぞれ示す。
【０１８４】
図１６に示されるように、新たなサンプルが絶えず追加される場合、本発明に係る分類器の学習の方法によって検出率を高いレベルに保つことができると同時に、ＦＰＰＩを安定して低いレベルに抑えることもできる。オンラインＳＶＤＤ法及び増分ＳＶＤＤ法では、ＦＰＰＩを低レベルに保持できない。
評価例３
次に、本発明に係る方法の対象物追跡の分野への適用を検討する。
【０１８５】
Ｓ． Ｓｔａｌｄｅｒ、Ｈ． Ｇｒａｂｎｅｒ及びＬ． Ｖａｎ Ｇｏｏｌの「Ｂｅｙｏｎｄ ｓｅｍｉ‐ｓｕｐｅｒｖｉｓｅｄ ｔｒａｃｋｉｎｇ」（ＩＣＣＶ Ｗｏｒｋｓｈｏｐ、２００９年）には、ｂｅｙｏｎｄ  ｓｅｍｉ−ｂｏｏｓｔ法が説明されている。Ａ． Ｓａｆｆａｒｉ他の「Ｏｎ‐ｌｉｎｅ ｒａｎｄｏｍ ｆｏｒｅｓｔｓ」（Ｐｒｏｃ． Ｏｎ‐ｌｉｎｅ Ｌｅａｒｎｉｎｇ ｆｏｒ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ Ｗｏｒｋｓｈｏｐに掲載、２００９年）には、ｏｎｌｉｎｅ  Ｒａｎｄｏｍ  Ｆｏｒｅｓｔ法が説明されている。Ｂ． Ｂａｂｅｎｋｏ、Ｍ．Ｈ． Ｙａｎｇ及びＳ． Ｂｅｌｏｎｇｉｅの「Ｖｉｓｕａｌ Ｔｒａｃｋｉｎｇ ｗｉｔｈ Ｏｎｌｉｎｅ Ｍｕｌｔｉｐｌｅ Ｉｎｓｔａｎｃｅ Ｌｅａｒｎｉｎｇ」（ＣＶＰＲに掲載、２００９年）には、ｏｎｌｉｎｅ  Ｍｕｌｔｉ−Ｉｎｓｔａｎｃｅ  Ｌｅａｒｎｉｎｇ法が説明されている。以上３つの方法は、対象物追跡に従来使用されてきた。評価例３では、本発明に係る方法をこれら３つの方法と比較する。
【０１８６】
異なる種類の動物を含む１０のビデオを選択する。それらのビデオは、すべてハンドヘルドカメラにより撮影された。ビデオ中の多くのフレームは非合焦又は動きによってぶれており、且つ視点の変化及び歪みも非常に多く、急速に起こっているので、ビデオの追跡は困難である。
【０１８７】
本発明に係る方法及び上記の３つの追跡方法に関して、第１のフレーム中の対象物の大きさ及び位置を指摘し、対象物の周囲の画像領域を本発明に対する教示サンプルとして切り切り出した。
【０１８８】
図１７は、本発明に係る方法及び他の従来の３つの方法を追跡に適用した場合の平均誤り率を示すグラフである。平均誤り率は、総フレーム数に占める累積誤フレーム数の割合（％）である。図１８は、本発明に係る方法及び他の従来の３つの方法を追跡に適用した場合の例示的な結果を示す。図１８の矩形は、そのフレームで取り出された追跡中の対象物である。図１７及び図１８において、図中符号１、２、３及び４は、本発明に係る方法、ｂｅｙｏｎｄ  ｓｅｍｉ−ｂｏｏｓｔ法、ｏｎｌｉｎｅ  Ｒａｎｄｏｍ  Ｆｏｒｅｓｔ法及びｏｎｌｉｎｅ  Ｍｕｌｔｉ−Ｉｎｓｔａｎｃｅ  Ｌｅａｒｎｉｎｇ法の結果をそれぞれ示す。
【０１８９】
図１７及び図１８に示されるように、本発明に係る方法は、他のオンライン追跡方法より優れた性能を示す。これにより、追跡におけるドリフトの問題を解決できる。
【０１９０】
表３は、本発明に係る方法と上記の３つの方法との計算時間の比較を示す。
【０１９１】
【表３】
0005570629.tif 000042
【０１９２】
表３に示されるように、本発明に係る方法の検出速度、学習速度及び更新速度は、オンラインに利用するのに十分に早い。
【０１９３】
本発明の方法及びシステムを多くの態様で実施できる。例えば、本発明の方法及びシステムをソフトウェア、ハードウェア、ファームウェア又はそれらの何らかの組み合わせによって実施可能である。先に説明した方法のステップの実行順序は単なる例であり、特に指示のない限り、本発明の方法のステップは、先に特定して説明した順序に限定されない。更に、いくつかの実施形態において、本発明は、本発明に係る方法を実現するための機械可読命令を含めて記録媒体に記録されたプログラムとして実施されてもよい。従って、本発明は、本発明に係る方法を実現するためのプログラムを記憶する記録媒体をも含む。
【０１９４】
本発明のいくつかの特定の実施形態を例によって詳細に説明したが、上記の例は単に例示を目的としており、本発明の範囲を限定することは意図されないことを当業者は理解すべきである。本発明の範囲及び精神から逸脱することなく上記の実施形態を変形してもよいことを当業者は理解すべきである。本発明の範囲は、添付の特許請求の範囲により定義される。
【図１】
0005570629.tif 000043
【図２】
0005570629.tif 000044
【図３】
0005570629.tif 000045
【図４】
0005570629.tif 000046
【図５】
0005570629.tif 000047
【図６】
0005570629.tif 000048
【図７】
0005570629.tif 000049
【図９】
0005570629.tif 000050
【図１０】
0005570629.tif 000051
【図１１】
0005570629.tif 000052
【図１２】
0005570629.tif 000053
【図１３】
0005570629.tif 000054
【図１４】
0005570629.tif 000055
【図８】
0005570629.tif 000056
【図１５】
0005570629.tif 000057
【図１６】
0005570629.tif 000058
【図１７】
0005570629.tif 000059
【図１８】
0005570629.tif 000060