画像処理方法およびシステム
【課題】２Ｄ被写体の検出と分離、カメラ姿勢推定、３Ｄ形状位置合わせおよび３Ｄ画像認識を含む画像処理における被写体の姿勢を推定する方法を提供する。
【解決手段】画像データを分析するための装置はプロセッサを含む。該プロセッサは、被写体の姿勢の複数の予測を得るために前記画像データを分析するよう構成され、前記予測は前記被写体の予測姿勢のインジケーションを含んでおり、前記予測姿勢は共通の座標系の位置、方向、スケールに関して表現され、２つの被写体姿勢間の距離を計算することで前記予測姿勢を比較することにより前記予測をグループ化するように構成され、前記距離は距離関数を用いて計算される。
【解決手段】画像データを分析するための装置はプロセッサを含む。該プロセッサは、被写体の姿勢の複数の予測を得るために前記画像データを分析するよう構成され、前記予測は前記被写体の予測姿勢のインジケーションを含んでおり、前記予測姿勢は共通の座標系の位置、方向、スケールに関して表現され、２つの被写体姿勢間の距離を計算することで前記予測姿勢を比較することにより前記予測をグループ化するように構成され、前記距離は距離関数を用いて計算される。
【発明の詳細な説明】
【関連出願】
【０００１】
本出願は、２０１１年７月１１日に提出された英国特許出願第１１１１８７１．８号に基づいており、その優先権の利益を主張するものであって、その全内容は参照により本明細書に組込まれる。
【技術分野】
【０００２】
本明細書で説明されているように本発明の実施形態は、一般に画像処理の分野に関する。
【背景技術】
【０００３】
画像処理においては、画像内の被写体の姿勢を推定することが必要となる場合がしばしばある。これは、２Ｄ被写体の検出と分離（2D object detection motion segmentation）、カメラ姿勢推定、３Ｄ形状位置合わせおよび３Ｄ画像認識を含むさまざまな画像タスクで発生する。姿勢推定により、被写体の位置、回転あるいはスケールの推定が必要となりうる。
【図面の簡単な説明】
【０００４】
以下の非制限の実施形態を参照して本発明の実施形態を説明する。
【図１】図１（ａ）はキャプチャー３Ｄ画像から生成された点群であり、図１（ｂ）は図１（ａ）の点群から認識された被写体を示す。
【図２】図２は３Ｄ画像のキャプチャーに用いられた装置の概略図である。
【図３】図３は本発明の実施形態に従う方法を実現するように構成されたハードウェアシステムの概略図である。
【図４】図４は本発明の実施形態に従う方法において用いることができる、特徴をキャプチャーする方法を示すフローチャートである。
【図５】図５は特徴を示す写真である。
【図６】図６（ａ）は被写体のキャプチャー３Ｄ画像から生成された点群であり、図６（ｂ）は抽出された特徴とともに図６（ａ）の画像を示す。
【図７】図７は本発明の実施形態に従う方法の概略図である。
【図８】図８はカーネル密度推定法を用いてモデル化された予測姿勢密度のプロットである。
【図９】図９は２つの姿勢の間の変動を示す概略図である。
【図１０】図１０（ａ）乃至（ｃ）は本発明の方法に従う、入力姿勢、密度推定およびフィルタリングの段階を示す３枚の図である。
【図１１】図１１（ａ）は、画像化される被写体および本発明の実施形態に従う方法を用いて処理された画像であり、図１１（ｂ）は図１１（ａ）の被写体の点群であり、図１１（ｃ）は図１１（ｂ）の点群に検出された特徴を重ね合わせた図であり、図１１（ｄ）は、検出された特徴をデータベースのものと比較した後に生成された予測姿勢の図である。図１１（ｅ）は、図１１（ａ）における被写体についてシステムによって返された登録ＣＡＤモデルである。
【図１２】図１２（ａ）〜１２（ｊ）は、本発明の実施形態に従う方法を用いて認識され登録される工業用部品の例である。
【図１３】図１３は図１２の被写体の混同行列である。
【図１４】図１４（ａ）は本発明の実施形態に従って認識された工業用部品の点群である。
【図１５】図１５は、写真中の顔の位置を認識するために本発明の実施形態に従う方法をどのように用いることができるか示す写真である。
【発明を実施するための形態】
【０００５】
一実施形態によれば、各被写体姿勢が共通の座標系の位置、方向、スケールに関して表現される場合の２つの被写体姿勢を比較する方法が提供される。該方法は、前記２つの被写体姿勢間の距離を計算することを含む。前記距離は距離関数
【数１】
【０００６】
を用いて計算される。Ｘは１つの被写体の被写体姿勢であり、Ｙは別の被写体の被写体姿勢であり、
【数２】
【０００７】
である。
【０００８】
ｓ（Ｘ）およびｓ（Ｙ）は被写体姿勢ＸおよびＹのスケールをそれぞれ表わすスカラー関数、Ｒ（Ｘ）およびＲ（Ｙ）は被写体姿勢ＸおよびＹの回転をそれぞれ表現する行列、ｔ（Ｘ）およびｔ（Ｙ）は被写体姿勢ＸおよびＹの平行移動をそれぞれ表現するベクトル、σｓ、σｒ、σｔはそれぞれｄｓ、ｄｒ、ｄｔの重み係数である。
【０００９】
上記距離基準（ｓＲｔ距離と称する）は、例えば車両情報システムにおける車両、歩行者、街灯柱などの被写体を認識し位置合わせするといった様々な処理に用いられる。例えば製造ライン等で工業用部品を認識する場合に用いることができ、画像内のクラッターシーンからの手、顔、心臓、肺、ポリープなどの認識に用いられ、カメラ姿勢推定、被写体追跡技術、医用画像技術における組織位置合わせ／ポリープ検出、車両ナビゲーション技術、ヒューマンコンピュータ技術（ＨＣＩ）、オートフォーカス技術などに用いられる。
【００１０】
上記の距離基準は、当該距離を用いるカーネルの開発に適している。カーネルは、Ｋ（ｄ２（Ｘ，Ｙ））で表される。
【００１１】
一実施形態において、カーネルは
【数３】
【００１２】
の式で表されるガウスカーネルである。ここで、σはカーネルのバンド幅である。ｓＲｔ距離を用いるガウスカーネルは、姿勢空間における確率密度関数を表わす。これは、ユークリッド空間においてポピュラーな正規分布に似ていて、分析的に非常にトレーサブルであり（つまり扱いやすい）、その「ベル」形状は、確率変数を実際にモデル化する際に有利である。
【００１３】
上記の重み付けは応用に応じて選択することができる。一実施形態では０．０４≦σｓ≦０．１２、０．０６≦σｒ≦０．２０、０．０６≦σｔ≦０．２０である。
【００１４】
平均を計算する方法が上記の距離基準に基づいてもよい。したがって、更なる実施形態によれば、複数の被写体姿勢の平均を比較する方法が提供される。該方法は、
【数４】
【００１５】
を用いて平均被写体姿勢を計算することを含む。ここで、Ｘ＝｛（Ｘ１，ｗ１），（Ｘ２，ｗ２），．．．（ＸＮ，ｗＮ）｝は姿勢集合、Ｘｉはｉ番目の姿勢、ｗｉはｉ番目の姿勢の重み、ｓ（Ｘｉ）は被写体姿勢Ｘｉのスケールを表わすスカラー関数、Ｒ（Ｘｉ）は被写体姿勢Ｘｉの回転を表現する行列、ｔ（Ｘｉ）被写体姿勢Ｘｉの平行移動を表現するベクトルである。
【数５】
【００１６】
はＳＯ（ｎ，Ｒ）への行列Ｘの特殊直交射影である。ここで、ＳＯ（ｎ，Ｒ）は全ｎ×ｎ特殊直交行列の集合であり、関数ｓｏｐ（Ｘ）はＹ−Ｘのフロベニウスノルムが最小化されるように特殊直交行列Ｙを返す。
【００１７】
別の実施形態において、画像データを分析する方法が提供される。前記方法は、被写体姿勢の複数の予測を得るために前記画像データを分析することを含む。前記予測は、被写体の予測姿勢のインジケーションを含む。予測姿勢は共通の座標系の位置、方向、スケールに関して表現される。
【００１８】
また、２つの被写体姿勢間の距離の計算により予測姿勢を比較することで予測をグループ化することを含む。該距離は距離関数
【数６】
【００１９】
を用いて計算される。
【００２０】
ここで、ＸとＹは同一被写体の被写体姿勢であって、
【数７】
【００２１】
であり、ｓ（Ｘ）およびｓ（Ｙ）は被写体姿勢ＸおよびＹのスケールをそれぞれ表わすスカラー関数、Ｒ（Ｘ）およびＲ（Ｙ）は被写体姿勢ＸおよびＹの回転をそれぞれ表現する行列、ｔ（Ｘ）およびｔ（Ｙ）は被写体姿勢ＸおよびＹの平行移動をそれぞれ表現するベクトル、σｓ、σｒ、σｔはそれぞれｄｓ、ｄｒ、ｄｔの重み係数である。
【００２２】
上記の方法によって分析された画像は少なくとも１つの被写体を含み、前記予測は前記被写体とその姿勢のインジケーションを含む。前記被写体のインジケーションは、少なくともデータの一部をデータベースにおける被写体のデータと比較することにより得ることができる。一実施形態において、前記データベースの各被写体は複数の特徴を含む。該データベースの被写体と画像データを比較することは、前記画像データを分析して前記データベースの被写体の特徴との一致を求めることを含む。
【００２３】
別の構成において、姿勢を推定する被写体は、画像をキャプチャーするのに用いられるカメラである。
【００２４】
実施形態において、各姿勢の複数の予測が生成されると、代表姿勢を決定できるようにするために、姿勢の密度を推定する密度推定法が用いられる。一実施形態において、被写体姿勢をグループ化することは、全姿勢が分布ｆ（Ｘ）からサンプリングされることを仮定するカーネル密度推定法を用いることを含み、前記カーネル密度推定法における前記カーネルは前記距離関数を含む。
【００２５】
前記グループ化によって形成されたグループの代表姿勢は、ｆ（Ｘ）の極大値の決定により計算することができる。この極大値は、平均値シフト、クイックシフトあるいはメドイドシフトのような様々な技術を用いて得ることができる。
【００２６】
実施形態の平均値シフト技術において、反復の各段階の平均は
【数８】
【００２７】
を用いて計算される。
【００２８】
ここで、Ｘｉはｉ番目の姿勢であり、ｗｉは平均被写体姿勢を計算するためのｉ番目の姿勢の重みである。また、χ＝｛（Ｘ１，ｗ１），（Ｘ２，ｗ２），．．．（ＸＮ，ｗＮ）｝は、Ｘｉをｉ番目の姿勢とするときの姿勢集合であり、ｗｉはｉ番目の姿勢の重みである。
【数９】
【００２９】
は、ＳＯ（ｎ，Ｒ）への行列Ｘの特殊直交射影である。ここで、ＳＯ（ｎ，Ｒ）は全ｎ×ｎ特殊直交行列の集合であり、関数ｓｏｐ（Ｘ）は、Ｙ−Ｘのフロベニウスノルムが最小化されるような特殊直交行列Ｙを返す。
【００３０】
重みｗｉは、ｗｉ＝λｉ＊Ｋ（ｄ２（Ｙ，Ｘｉ））から求めることができる。ここで、Ｋはカーネル関数であり、ｄは、平均値シフト技術を用いて推定された現在の極大値Ｙを持つ姿勢と、姿勢Ｘｉとの間の距離である。別の実施形態において、距離ｄは上述のｓＲｔ距離である。しかしながら、該平均を用いた他の重みを用いてもよい。平均値シフト法においてｗｉ＝λｉ＊Ｋ（ｄ２（Ｙ，Ｘｉ））の場合、Ｙが固定ならば、Ｙは
【数１０】
【００３１】
の極大である。しかしながら、他の方法はこの制約を要しない。
【００３２】
ある実施形態において、演算時間を削減するために、先ずハフ投票法またはメドイドシフト法を用いて姿勢推定が予測される。ある実施形態では、各予測は初期の重みを持つ。
【００３３】
上記方法は２Ｄおよび３Ｄの画像データに適用することができる。さらに、該方法をより高い次元に拡張することもできる。
【００３４】
さらに別の実施形態において、各被写体姿勢が共通の座標系の位置、方向、スケールに関して表現される場合の２つの被写体姿勢を比較するための装置が提供される。該装置はプロセッサを含む。
【００３５】
前記プロセッサは２つの被写体姿勢間の距離を計算するように構成され、該距離は距離関数
【数１１】
【００３６】
を用いて計算される。
【００３７】
ここで、Ｘは１つの被写体の被写体姿勢である。また、Ｙは別の被写体の被写体姿勢であり、
【数１２】
【００３８】
であり、ｓ（Ｘ）およびｓ（Ｙ）は被写体姿勢ＸおよびＹのスケールをそれぞれ表わすスカラー関数、Ｒ（Ｘ）およびＲ（Ｙ）は被写体姿勢ＸおよびＹの回転をそれぞれ表現する行列、ｔ（Ｘ）およびｔ（Ｙ）は被写体姿勢ＸおよびＹの平行移動をそれぞれ表現するベクトル、σｓ、σｒ、σｔはそれぞれｄｓ、ｄｒ、ｄｔの重み係数である。
【００３９】
本発明の実施形態は、ハードウェアまたは汎用計算機のソフトウェアによって実現することができる。また、本発明の実施形態は、ハードウェアとソフトウェアの組み合わせとして実現することができる。本発明の実施形態は、単一の処理装置あるいは処理装置の分散ネットワークによって実装することもできる。
【００４０】
本発明の実施形態はソフトウェアによって実現することができ、本発明の実施形態は任意の適合する記録媒体によって汎用計算機に導入される計算機コードを含む。記録媒体は、フロッピー（登録商標）ディスク、ＣＤ ＲＯＭ、磁気デバイス、プログラマブルメモリデバイスのような任意の計算機可読記録媒体を含むことができる。
【００４１】
第１実施形態に従うシステムおよび方法を説明する。
【００４２】
図１（ａ）は、４つの被写体１、３、５および７を含むシーンの点群である。点群は図２を参照して説明した装置を用いて得られる。点群は、３Ｄイメージング技術によって得られた表面への法線から構築された表面上の予測点を含む。
【００４３】
図１（ｂ）は、図１（ａ）のシーンを含む、被写体１、３、５および７の認識を可能にするために本発明に従う方法によって変更された後の図１（ａ）のデータを示す。
【００４４】
図２は本発明の一実施形態を被写体１１の画像をキャプチャーし、当該被写体の姿勢を認識するのに使用したシステムの概略図である。被写体１１は３つの異なる光源１３，１５，１７によって照明される。この実施形態では、これら３つの光源がそれぞれ異なる３色の光を発することができる。ここでは、赤、緑、青の色を、これら３色を識別できるビデオカメラを得ることができるので、選択することとする。しかしながら、ビデオカメラで識別できる色を発光できるものであれば、どのような色を発光する光源であってもよい。また、可視光外の放射光源も使用することができる。色の正確な濃淡または発光の周波数はビデオカメラに依る。一実施形態では、光源は複数のプロジェクタであり、場面（シーン）がそれぞれのプロジェクタからのそれぞれの発光色で照明されるよう複数のフィルターを設ける。また、さらに別の実施形態では、被写体を照明するのにＬＥＤが用いられる。
【００４５】
一実施形態において、光源光は、カメラ内のセンサによりキャプチャーされた周波数に、それぞれのセンサが０から２５５の範囲の色をキャプチャーされるように調整される。この範囲より外の色が決定されると、サチュレーションが起こることがあり、その場合、生成される３−Ｄ画像に誤差が生じる。
【００４６】
この実施形態において、３つの光源１３，１５，１７は被写体１の周りに横方向に配置され、フロア位置から被写体１の高さまでの間の数段階に縦方向に置かれる。ある実施形態においては、光源１３，１５，１７は三角形に配置される。一配置例では、三角形配置された光源は隣り合う光源の間隔が１から３メートルであり、他の配置例では、隣り合う光源の間隔が１．５メートルから２．５メートルである。光源は被写体１に向けられている。
【００４７】
三光源１３，１５，１７の角度は、被写体１１を中心にその回転面においておよそ３０度の間隔で設けられる。角度間隔が大きいほど方向に依存する色はよりはっきりと変化する。光源が離れすぎていると、被写体１のへこんだ形の部分の識別が難しくなる。これは、そのような部分でつくられる影は被写体のさらに大きな部分に拡大され、データの解析をさらに難しくするからである。好ましくは、被写体１の各部分が三つのすべての光源１３，１５，１７で照明される。
【００４８】
第２の光源１５の縦方向下に位置するカメラ１９は、３つの光源３，５，７で照明されながら移動する被写体を記録するために用いられる。光源が三角に配置される実施形態においては、カメラ１９はその三角形の面の内部に設置されてもよい。
【００４９】
カメラ１９は異なった色の複数の画像を分離することができる。これは、カメラ内のフィルター機構によりなされる。こうして、カメラ１９は三つのすべての光源からの照明を利用して被写体１１の画像をキャプチャーすることができ、それぞれの光源からの反射光を順次識別することができる。したがって、赤、緑、青の光源からのそれぞれの反射光を用いて画像を生成することができる。
【００５０】
一実施形態において、第一ビデオカメラは生画像データを出力する。例えばＭＰＥＧのようなデータ圧縮機構は使用されない。画像データの圧縮により、再構成された３Ｄ画像に影響が現れる可能性がある。
【００５１】
カメラ１９でキャプチャーされたデータは解析部２０に供給される。解析部２０は、三光源１３，１５，１７に接続されている。
【００５２】
図３はシステム解析部２０の可能な基本構造を示す。解析部２３は、プログラム２５を実行するプロセッサ２３を有する。解析部１３は、さらにストレージ２７を有する。ストレージ２７は、カメラ１９（図２）から受け取ったデータを解析し、光源１３，１５，１７の照明を制御するためのプログラム２５で用いられるデータを記憶する。解析部２０はさらに入力モジュール１１と出力モジュール３３を有する。入力モジュール３１はカメラ入力部３５に接続されている。カメラ入力部３５はカメラ１９からのデータを受け取る。カメラ入力部３５はカメラから単に直接データを受け取ってもよいし、または、外部記憶媒体またはネットワークからデータを受け取ってもよい。
【００５３】
出力モジュール３３にはディスプレイ３７が接続されている。ディスプレイ３７はカメラ入力部３５から受け取ったカメラデータからキャプチャーされた３Ｄ画像を表示する。ディスプレイ２７の代わりに、出力モジュール３３がファイルまたはインターネット等を介して出力を行ってもよい。
【００５４】
使用時において、解析部２０はカメラ入力部３３を介してカメラデータを受け取る。プロセッサ２３で実行されるプログラム２５は、３Ｄ画像データを生成するためにストレージ２７に記憶されたデータを使ってカメラデータを解析し、被写体およびその姿勢を認識する。該データは出力モジュール３３を介してディスプレイ３７に出力される。
【００５５】
上記は、フォトメトリックステレオ技術を用いて３Ｄ被写体データをキャプチャーする技術を示している。しかしながら、(少なくとも1つの光源および2つのカメラを用いる)２眼ステレオのような他の方法が可能であり、タイムオブフライトセンサやアクティブ光源デプスセンサを用いてもよい。
【００５６】
次に、キャプチャーされたシーンの画像内の被写体およびそれらの姿勢を検出するための方法を説明する。
【００５７】
被写体認識を行なえるようにするには、システムは、認識対象となりうる被写体に関する情報を記憶するための学習をしておく必要がある。これを図４を参照して説明する。
【００５８】
まずステップＳ４０１では、１つの被写体または複数の被写体が図２および３を参照して説明されたものと同様の装置を用いて画像化される。
【００５９】
この実施形態では、各被写体に座標系が割り当てられる。一実施形態において、該座標系の原点は被写体の中心に位置し、該座標系の各軸の方向は被写体の向きに一致し、この座標系における単位長は被写体のスケールと等しい。該座標系は、グローバル座標系の点をローカル座標系に変形する単一の４ｘ４アフィン変換行列によって定められる。
【００６０】
特徴が被写体から抽出される。特徴は特定が容易な球状の領域である。特徴の例を図５に示す。
【００６１】
特徴を特定する方法は既知であり、ここでは詳細に述べない。本実施形態では、各特徴にローカル座標系を設定する。座標系の原点は特徴の中心に位置し、軸の方向は特徴の基準方向に一致し、該座標系における単位長は特徴の半径と等しい。該座標系もまたグローバル座標系の点をローカル座標系に変形する４ｘ４変換行列によって定められる。特徴の座標系において、原点に近い固定位置での３１点がサンプリングされ、３１次元の記述子ベクトルが生成される。（領域中心、領域半径、方向、記述子）のタプルが特徴を形成し、これはステップＳ４０５において記憶される。
【００６２】
したがって、データベース内の各特徴について、特徴のローカル座標系の変換行列、およびそれに関連した被写体のローカル座標系の両方が既知である。特徴の変換行列がＦ１であって、被写体の変換行列がＭ１である場合、Ｍ１にＦ１の逆数を乗ずる（つまりT=M1(F1)^(-1)を計算する）ことにより、特徴のローカル座標系の点を、関連する被写体のローカル座標系に変形する変換行列Ｔが求まる。
【００６３】
被写体がスケーリング、平行移動および回転によって変形される場合、行列Ｔは不変である。上記処理は、シーンに存在すると考えられる被写体について繰り返される。例えば図６（ｂ）の被写体６１に関して、図６（ｂ）は被写体６１に割り当てられた特徴６３を示す。
【００６４】
図７を参照して説明するように、動作中に、図２および３を参照して説明したように画像がキャプチャーされる。ステップＳ４１１において、この画像から特徴が抽出される。図４を参照して上述したように特徴について述べる。データベースにおける特徴の記述子と、画像から抽出された特徴の記述子との間に一致が見られる場合、予測が生成される。
【００６５】
実施形態において、ユークリッド距離が閾値未満である場合、２つの記述子間には一致がある。画像から抽出された特徴とデータベースにおける特徴との間に一致がある場合、ステップＳ４１５において予測が生成される。この予測は、どのような被写体が現時点で認識されており、それはどこにあるかの仮説である。
【００６６】
実施形態において、シーン上の特徴が一致する場合、該特徴のローカル座標系の変換行列のみが識別される。２つの特徴が一致する場合、テストシーンからの特徴のローカル座標系の点を予測被写体のローカル座標系に変形する変換行列は、Ｔと同じであると考えられる。したがって、グローバル座標系からの一致特徴の変換行列がＦ２である場合、予測被写体のローカル座標系を表わす変換行列は、ＴにＦ２を乗ずること（つまりM2’=T F2）により与えられる。Ｍ２’は予測被写体姿勢のスケール、中心点および方位を与える。
【００６７】
要するに、２つの記述子の一致によって、２つの対応する領域が同じ形状を持つものと見なされる。データベースからの特徴における被写体の識別、位置、スケールおよび方位は既知であることから、データベースからの特徴がシーンからの特徴と同じ場所に移動し、スケーリングし、回転するように該被写体を（スケーリング、平行移動、回転によって）変形することができる。これは、変形の後にこの被写体がシーンに存在することを予測するのに用いられる。
【００６８】
上記方法は多くの予測をもたらす。この予測は、ステップＳ４１７においてグループ化される。
【００６９】
各予測は、被写体のＩＤおよびその姿勢に関する情報を含む。該姿勢（Ｘ）について、各姿勢は変換行列
【数１３】
【００７０】
として表わすことができる。
【００７１】
ここで、ｓ（Ｘ）は被写体のサイズに関係のある実数、Ｒ（Ｘ）はこれに沿って被写体が向く方向を示す正方行列、ｔ（Ｘ）は被写体中心の位置を示すベクトルである。
【００７２】
姿勢をグループ化するために、カーネル密度推定法（ＫＤＥ）が用いられる。この方法では、被写体について多数の姿勢Ｘ１，Ｘ２，．．．，Ｘｎが考慮される。
【００７３】
各姿勢Ｘｉは、高次元（非ユークリッド）空間の点と見なされ、重みλｉを持つ。
【００７４】
場合によっては、全姿勢が同等に処理され、全姿勢についてλｉ＝１である。別の実施形態において、姿勢には重みが加えられる。
【００７５】
一つの方法として、重み付けは、データベースにおける被写体の特徴および被写体のインスタンスの数を考慮に入れることにより行なわれる。
【００７６】
例えば、データベースにＮ個の被写体がある場合、各被写体は複数のインスタンスを持ち得るのであって、各インスタンスは、異なる姿勢でスキャンされた同じ被写体を表わす点群である。そのようなシナリオでは、各被写体にはＮｋ個のインスタンスが存在し得る。この場合、被写体Ｋの各インスタンスｋはＮｋ，ｌ個の特徴を持つ。このシナリオでは、各姿勢の初期重み（シーン上の特徴と特徴とを一致させる結果である）は、
【数１４】
【００７７】
に設定される。
【００７８】
ＫＤＥ法では、全姿勢が未知の確率密度関数ｆ（Ｘ）からサンプリングされることを仮定している。姿勢をグループ化する問題は、ｆ（Ｘ１’），ｆ（Ｘ２’），．．．，ｆ（Ｘｍ’）が局所的に最大化される全ての点Ｘ１’，Ｘ２’，．．．，Ｘｍ’を求めることとして再定式化される。各対（Ｘｊ’，ｆ（Ｘｊ’））は代表姿勢（Ｘｊ’）およびその重み（ｆ（Ｘｊ’））を定める。
【００７９】
この実施形態では、この問題を次の２つのステップによって解決する。
【００８０】
（１）（Ｘ１，λ１）、（Ｘ２，λ２）、（Ｘｎ，λｎ）からｆ（Ｘ）を推定すること。
【００８１】
（２）ｆ（Ｘ）からの極大値Ｘ１’，Ｘ２’，．．．，Ｘｍ’を求めること。
【００８２】
ＫＤＥは、
【数１５】
【００８３】
の式で表されるカーネル密度推定量
【数１６】
【００８４】
が未知の密度関数ｆ（Ｘ）を近似できることを仮定する方法である。
【００８５】
ここで、Ｋ（）は距離関数ｄ（）を用いるカーネル密度関数であり、
【数１７】
【００８６】
はＫ（）のボリューム密度関数である。上記は全姿勢についてλｉ＝１を仮定している。
【００８７】
この式において、各点Ｘｉは、カーネル関数に基づいてＸｉを中心とする密度関数をアサートし、それは、図８のトレース２０１に示されるような小さな「ブロブ（ｂｌｏｂ）」として現われ、
【数１８】
【００８８】
は簡単には全ての密度関数の平均であり、それはトレース２０３として示された全ブロブの平均として現われる。ＫＤＥにおいて、
【数１９】
【００８９】
がｆ（Ｘ）を推定するのに用いられる。
【数２０】
【００９０】
は、入力点から直接定義されるので、ｆ（Ｘ）の推定は問題にならない。そのような系の極大値は、平均値シフト、メドイド（medoid）シフト、クイックシフトのような方法を用いて求めることができる。
【００９１】
カーネル密度関数Ｋ（）を定義する必要がある（つまり、点からの小さなブロブを定義することである）。これは任意のユークリッド空間において行うことができる。しかし、これを非ユークリッド空間において行うのは困難である。全姿勢の空間は非ユークリッドである。本発明の実施形態に従って、距離基準に基づくガウスＳＲＴカーネル
【数２１】
【００９２】
が用いられる。ここで、ＸとＹは図９に概略的に示されるような被写体姿勢、ｓ（Ｘ）およびｓ（Ｙ）は被写体姿勢ＸおよびＹのスケールをそれぞれ表わすスカラー関数、Ｒ（Ｘ）およびＲ（Ｙ）は被写体姿勢ＸおよびＹの回転をそれぞれ表現する行列、ｔ（Ｘ）およびｔ（Ｙ）は被写体姿勢ＸおよびＹの平行移動をそれぞれ表現するベクトル、σｓ、σｒ、σｔは重み係数である。ノルム
【数２２】
【００９３】
は、行列のフロベニウスノルムを表わし、ノルム
【数２３】
【００９４】
はベクトルのユークリッドノルムを表わす。
【００９５】
実施形態において、σｓ、σｒ、σｔは、システムの独立なテストセットにおける位置合わせスコアの最大化により求まる。この手続きでは、既知の被写体姿勢を用いて２００の点群のテストセットが作成される。システムは（σｓ，σｒ，σｔ）の異なる組み合わせを用いてこれらの点群について実行される。その後、各組み合わせについてシステムが正しく位置合わせをする回数のカウントがなされる。次の場合、位置合わせは正解である。
【００９６】
出力スケールはグランドトルーススケールの５％未満である。
【００９７】
出力位置とグランドトルース位置の間の距離は、グランドトルーススケールの１０％以内である。
【００９８】
出力方位とグランドトルース方位の間の角度は１５度未満である。
【００９９】
正しい位置合わせの数を最大化する（σｓ，σｒ，σｔ）の組み合わせが選択される。
【０１００】
実施形態において、一般的な範囲は次のとおりである。
【０１０１】
・σｓ＝０．０４．．０．１２
・σｒ＝０．０６．．０．２０
・σｔ＝０．０６．．０．２０
比をσｓ：σｒ：σｔ＝７：１２：１２、例えば（σｓ，σｒ，σｔ）＝（０．０７，０．１２，０．１２）とすれば上手く行くことが分かった。
【０１０２】
ここで、極大値を求めるための平均値シフト技術について説明する。平均値シフト法は初期姿勢から開始する。この姿勢をＹとする。カーネル（ここではガウスカーネル）Ｋ（）が定義されていることを考慮し、上述の距離基準を用いることにより、この方法は、Ｙが動かなくなるまで繰り返しＹを「移動させる」。
【０１０３】
ガウスカーネルが上述の距離基準を用いている場合、Ｙ、ｇＹ（Ｘ）に中心がある（つまり
【数２４】
【０１０４】
に定義された全てのブロブと同じ形の小ブロブ）。すべての姿勢Ｘｉについて、新しい重みｗｉ＝λｉ＊ｇＹ（Ｘ）を設定する。したがって、Ｙの近くの姿勢は大きな重みを持ち、Ｙから遠くはなれた姿勢は小さな重みを持っている。
【０１０５】
そして、新たな平均Ｙ’を（Ｘ１，ｗ１），（Ｘ２，ｗ２），（Ｘｎ，ｗｎ）から計算することができ、ＹがＹ’にセットされる。実施形態において、上記距離基準に基づいた平均を用いて平均が計算される。この平均は、ｓＲｔ平均と呼ばれ、
【数２５】
【０１０６】
である。
【０１０７】
ここで、χ＝｛（Ｘ１，ｗ１），（Ｘ２，ｗ２），．．．（ＸＮ，ｗＮ）｝は姿勢の集合、Ｘｉはｉ番目の姿勢、ｗｉはｉ番目の姿勢に関連した重みであり、該重みは姿勢の精度のインジケーションである。ここで、
【数２６】
【０１０８】
は行列ＸのＳＯ（ｎ，Ｒ）への特殊直交射影である。ここで、ＳＯ（ｎ，Ｒ）は全ｎ×ｎ特殊直交行列の集合である（つまり、ＹＴＹが恒等行列となり、Ｙの行列式が１となる任意のｎ×ｎの実行列Ｙ）。関数ｓｏｐ（Ｘ）は、Ｙ−Ｘのフロベニウスノルムが最小化されるような特殊直交行列Ｙを返す。関数ｓｏｐ（Ｘ）は既知である。これは、既知の方法によって効率的に実装することができる。
【０１０９】
Ｙが動かなくなる（つまり、Ｙ’はＹと同じである）場合、Ｙは、
【数２７】
【０１１０】
の極大値に一致することが数学的に証明される。平均値シフトは、できるだけ多くの極大値を求めるために開始点を異ならせて多数回実行される。新たなＳＲＴ平均を計算するステップにおいて、異なる重みにより全姿勢から単一の平均を計算する。しかし実際のところｗｉが小さすぎる場合、新たなｓＲｔ平均の計算に（Ｘｉ，ｗｉ）が織り込まれるかどうかにかかわらず、該成分は結果として生ずる平均にほとんど影響がない。したがって計算を省くために、ｗｉが閾値より大きい姿勢ＸｉのみからｓＲｔ平均を計算する。一実施形態においては、この閾値として１Ｅ−１１を用いる。
【０１１１】
上記は全ての被写体について繰り返される。
【０１１２】
次に、ステップＳ４１９においてフィルター処理が行なわれる。ここで、最大の重みを持った代表姿勢が選択される。この姿勢に重なった被写体を表わす全姿勢が削除される。次に、２番目に大きい重みを持った姿勢が処理され、この姿勢に重なった全姿勢もまた削除される。該ステップは、処理中の姿勢の重みが閾値より小さくなるか、姿勢がなくなるまで繰り返される。
【０１１３】
これにより、シーン内の全ての被写体の識別およびその姿勢が得られる。
【０１１４】
図１０（ａ）乃至（ｃ）は、図７を参照して説明した処理を概略的に示している。図１０（ａ）は一致特徴のそれぞれについて予測が生成されるステップＳ４１５に対応する。
【０１１５】
図１０（ｂ）は、姿勢についてカーネル密度推定法を用いた密度推定が行なわれることを示す。これは、Ｓ４１７のグループ化ステップの一部を成す。図１０（ｃ）に示すように、各クラスターにおける姿勢はグループ化され、各クラスターの代表姿勢が形成される。
【０１１６】
上記実施形態では、投票ベースの３Ｄ形状認識および位置合わせが提供される。投票は、各被写体について予測された３Ｄ姿勢である。上記実施形態は、平行移動、回転、スケールを同時に用いて、３Ｄ応用に平均値シフトを適用する。
【０１１７】
上記は直接相似変形の空間における３Ｄ姿勢投票に平均値シフトを用いる。この空間の姿勢間に距離基準が導入される（ＳＲＴ距離）。これはユークリッド距離とは異なり左不変であって、リーマン距離とは対照的にユニークで閉じた形の平均を持つ。したがって、計算上効率的である。
【０１１８】
上記実施形態では、可能な姿勢の組または投票のコレクションによって、姿勢の経験分布が確立される。投票は、テスト被写体からのローカル特徴を、既知の姿勢を持ったライブラリの特徴に一致させることにより計算される。
【０１１９】
そして第２のステップは、該分布における１つ以上の「最良な」姿勢を求めることである。上記実施形態では、これは確率の極大値を繰り返し求める平均値シフト処理によって実現される。
【０１２０】
上記実施形態のシステムは、既知の方位を持った関心被写体が固定されない場合に対処することができる。上記実施形態では、被写体が認識され、直接相似群、即ち平行移動、回転、スケールによってパラメータ化された等方相似変換群において位置合わせされる。スケールは、入力データのスケールが未知であるか高いクラス内スケール変動がある場合に必要である。回転は完全な位置合わせに必要であり、より正確な認識をもたらす。結果として得られる７Ｄ姿勢空間は大きすぎるので、既知の技術を用いる現行の計算機能力では効率的に分析することができない。
【０１２１】
上記実施形態は平均値シフト技術を用いている。上記技術において、スケールおよび回転はユークリッド距離およびリーマン距離のような既知の距離尺度を用いる課題を導入し得る。ユークリッド距離はスケール不変ではなく、回転は非線形多様体（manifold）を生成し、それへの投影はスケールのバイアスを引き起こす。リーマン距離の平均は閉じた形の解を持たず、計算が遅い。
【０１２２】
上記の距離基準はスケール、回転、平行移動の不変性を付随的に提供する。実施形態において、この距離の重み付け平均には以下の特性がある。
【０１２３】
１．ユニークであること。
【０１２４】
２．閉じた形であること−これは計算を効率化する。
【０１２５】
３．スケール互換であること。回転および平行移動がすべて等しい場合、平均はスケールの平均として作用する筈である。数学的に、あるＲ’およびｔ’について
【数２８】
【０１２６】
であるならば、Ｒ（μ（χ））＝Ｒ’であり、ｔ（μ（χ））＝ｔ’であり、ｓ（μ（χ））がｓ（Ｘｉ）の平均である場合、μはスケール互換である。
【０１２７】
４．回転互換であること。
【数２９】
【０１２８】
ならば、ｓ（μ（χ））＝ｓ’であり、ｔ（μ（χ））＝ｔ’であり、Ｒ（μ（χ））はＲ（Ｘｉ）’ｓの平均である。
【０１２９】
５．平行移動互換であること。
【数３０】
【０１３０】
であるならば、ｓ（μ（χ））＝ｓ’であり、Ｒ（μ（χ））＝Ｒ’であり、ｔ（μ（χ））はｔ（Ｘｉ）’ｓの平均である。
【０１３１】
６．左不変であること。左不変距離は事後変換に不変のものである。すなわち、
【数３１】
【０１３２】
である。この特性は、（ａ）左共変平均すなわち
μ（ＺＸ）＝Ｚμ（Ｘ）
を導く。つまり、全姿勢ＸｉがＺによって変換される場合、平均もＺによって変換される。また、（ｂ）平均値シフトで計算された重みｗｉは任意の事後変換Ｚに対して不変であり、左共変平均シフトをもたらすことを保証する。
【０１３３】
対称距離は
【数３２】
【０１３４】
となるように定められ、直観的に望ましいものに見えるが、これが無くても平均値シフトにおける距離の使用が妨げられることはなく、リストされた特性を与えられるならば、それは必要ではない。右共変も望ましい特性と考えられるかもしれないが、３Ｄ認識のコンテキストにおいて、この存在は何ら意味のある振る舞いに関係しない。
【０１３５】
ｓＲｔ距離はその成分
【数３３】
【０１３６】
に分割することができる。
【０１３７】
ここで、ｄｓ（）、ｄｒ（）、ｄｔ（）はそれぞれスケール、回転、平行移動の距離である。
【０１３８】
あるバンド幅係数σｓ；σｒ；σｔ＞０を所与として、ｓＲｔ距離は次のように定義される。
【数３４】
【０１３９】
σｓ；σｒ；σｔを制御することによりスケール、回転、平行移動のうちの１つの種類の変換に対して他のものより敏感なｓＲｔ距離を生成することが可能であり、したがって、非常に柔軟性がある。
【０１４０】
ｄｓＲｔ（）が定義されると、ｄｓＲｔ（）により導入される平均μｓＲｔは次のように定義される。
【数３５】
【０１４１】
これは、平均をもたらし、
【数３６】
【０１４２】
である。
【０１４３】
ここで、
【数３７】
【０１４４】
は、ＳＯ（ｎ，Ｒ）への行列Ｘの特殊直交射影である。ここで、ＳＯ（ｎ，Ｒ）は全ｎ×ｎ特殊直交行列の集合である（つまり、ＹＴＹが恒等行列となり、Ｙの行列式が１となる任意のｎ×ｎの実行列Ｙ）。関数ｓｏｐ（Ｘ）は、Ｙ−Ｘのフロベニウスノルムが最小化されるような特殊直交行列Ｙを返す。関数ｓｏｐ（Ｘ）は既知である。これは、既知の方法（例えばM. Moakher. Means and averaging in the group of rotations. SIAM J. Matrix Anal. Appl., 24:1-16, 2002）によって効率的に実装することができる。
【０１４５】
上記において回転平均行列を計算する場合、全ての回転行列Ｒ（Ｘｉ）の重み付け算術平均が計算される。これは、関数ｓｏｐ（）を介してそれに近い真の回転行列と置き換えられる。任意の特殊直交行列は実行列であり、逆もまた同様である。重み付け平均行列は必ずしも回転行列ではないので、Ｓｏｐ（）はこの実施形態において用いられる。
【０１４６】
上記の実例説明のために、物理的な被写体およびこれに一致するＣＡＤモデルを用意し、１２の形状クラスから成る実験データを用いて実験を行った。
【０１４７】
図１１（ａ）に示されるような各被写体のジオメトリを、図１１（ｂ）に示すように点群の形で様々な角度から２０回ほどキャプチャーした。クラスラベルと共に、すべての形状インスタンスは関連するグランドトルース姿勢を持つ。これは、先ずおおよその関連ＣＡＤモデルを点群に手動で位置合わせし、該位置合わせを改善するためにＩｔｅｒａｔｉｖｅ Ｃｌｏｓｅｓｔ Ｐｏｉｎｔアルゴリズムを用いることにより計算される。
【０１４８】
入力姿勢投票Ｘの計算は、テスト点群および（クラスおよび姿勢が既知の）学習点群の集合を所与として２段階の処理である。第一段階において、記述子と、被写体に関連するスケール、平行移動、回転とから構成されるローカル形状特徴が図１１（ｃ）に示すような全ての点群について計算される。先ず最も近い点への各ボクセル中心の距離についてのガウスオペレーターを用いて点群を１２８３のボクセルボリュームに変換する。次に、ガウスオペレーターの差分を利用する３次元位置とスケールによって特徴点をローカライズし、各特徴点の基準方向を計算してローカル特徴姿勢を生成する。最終的には、特徴点の周囲３１箇所の規則的に分布した位置において（正確なスケールで）ボリュームを単純にサンプリングすることにより、基礎となる３１次元の記述子を計算する。
【０１４９】
第二段階では、記述子間のユークリッド距離に関して各テスト特徴を２０の最も近い学習特徴に一致させる。これら一致の各々により、図１１（ｄ）に示されるテスト被写体の姿勢の投票Ｘｉ＝ＡＢ−１Ｃが生成される。Ａ、Ｂ、Ｃは、それぞれ、テスト特徴、学習特徴、学習被写体のグランドトルース姿勢である。さらに、各投票は（ＮＣＮＩ）−１として計算される重み即ちλｉを持つ。ＮＣはクラス内の学習インスタンスの数、ＮＩは特徴の特定インスタンスにおいて求まった特徴の数である。
【０１５０】
平均値シフトは、所与の被写体クラスの出力姿勢分布において局所最頻値とその重みを求める。そのような最頻値は多数存在しうることから、平均値シフトは各クラスにつき１００のランダムな入力姿勢から開始する。各最頻値は、重複を除外しつつ、全クラスにわたる候補姿勢のリストに加えられる。Ｓ＋（３）では、回転の四元数表現すなわちｑ（Ｘ）を用いることが可能である。この式を用いることにより、ｄｓＲｔ（）の回転成分を次のように定義することができる。
【数３８】
【０１５１】
ここで、｜．．．｜はｑ（Ｘ）および−ｑ（Ｘ）が同じ回転を表わすことを示すために必要である。この式は、他のものに比較して計算量が少ないという利点を持ち、当該空間における非成分的（noncomponent-wise）な距離を与える。
【０１５２】
この例では、平均値シフト推論アプローチと比較するためにハフ投票法を実装した。これは、回転を効果的に周辺化して、平行移動およびスケールに関する４Ｄヒストグラムの各ビン（bin）に該当する、姿勢投票の重みの和を計算するものである。ビン幅は４次元の各々における平均形状幅（あるいはスケール）の０．１６倍になるように設定される。各クラスで最も高いビンの和は姿勢の最頻値を定義する。
【０１５３】
学習データの評価に交差検定を用いた。各クラスにおける２０個の形状インスタンスのうちの１９個から学習セットを作成した。各クラスの残りのインスタンスはテスト形状となる。各テスト形状に５つのランダムな変換（０．５−２の範囲の平行移動、回転、スケール）を施し、この処理をテスト形状である各学習形状で繰り返し、１クラス当たり１００のテストインスタンスを生成する。
【０１５４】
図１２に示すような、１２個のクラスを評価に用いた。これらは、ベアリング、ブロック、ブラケット、車両、歯車、フランジ、ノブ、パイプ、２つのピストンである。これは全部で１０００個のテストをもたらす。残りの２つのクラスは、最適なカーネルバンド幅（σ）を学習するために推論法に用いられる。
【０１５５】
推論法は２つの基準（認識率と位置合わせ率）について評価された。
【０１５６】
認識率−上述したように、重みと共に姿勢およびクラスにわたる最頻値のリストが生成される。出力クラスは最も高い重みの最頻値のクラスである。混同行列は全テストにわたる出力クラス対グランドトルースクラスを記録する。認識率は、この行列のトレースすなわち正解分類の数から与えられる。
【０１５７】
位置合わせ率−あるテストの出力姿勢は、そのクラスがグランドトルースクラスと一致する重み付け（weightiest）最頻値の出力姿勢から与えられる。次のスケール、回転、平行移動の判定基準
【数３９】
【０１５８】
をすべて満たす場合、姿勢Ｘは正しいと考えられる。Ｙはグランドトルース姿勢である。対称性がある被写体の場合には、Ｙが複数存在し、最も接近しているものへの距離が用いられる。
【０１５９】
平均値シフトアルゴリズムに用いられるσｓ、σｒ、σｔを決めるために、（最終評価に用いられない）２つの学習クラスの交差検定から位置合わせ率を最大化する。位置合わせ率は局所探索を用いて最大化される。初期バンド幅が選ばれ、この値と値１：２および１＝この値の１：２倍について位置合わせ率が計算される。最も高いスコアを持つ値が選ばれ、収束するまで当該処理は繰り返される。学習するべきパラメータを３つとし、３Ｄグリッドについて局所探索が計算される。
【０１６０】
表１は、ｓＲｔを用いる平均値シフト法の定量的な結果をまとめたものである。
【表１】
【０１６１】
表１によれば、ｓＲｔ平均値シフトは、認識と位置合わせの両方について良い結果を示すことがわかる。３行目はスケールおよび平行移動のみを考慮する場合の位置合わせ率である。また５行目は位置合わせ結果の出力スケールの平均（各々はグランドトルーススケールに対する出力スケールの比）を示している。
【０１６２】
平均値シフト法のクラスごとの位置合わせ率を表２に示す。
【表２】
【０１６３】
ｓＲｔ推論法の混同行列を図１３に示す。
【０１６４】
図１４は、複数の被写体を含んだ現実のシーンにｓＲｔ平均値シフトを容易に適用できることを示している
別の実施形態において、該システムは、地表面および衝突検出の位置のような物理的な制約を用いて出力姿勢のリストをフィルターしてもよい。これにより誤判定結果の数を低減することができる。
【０１６５】
上記は、直接相似変換の空間すなわちＳ＋（ｎ）における姿勢についての平均値シフトにおけるｓＲｔ距離の利用を示している。距離は左不変であるものとし、スケール、回転、平行移動互換の望ましい特性を伴うユニークでクローズドな形の平均を持つことを示した。
【０１６６】
この距離は、視覚ベースのジオメトリキャプチャーシステムおよび基本特徴とともに回転の対称性を持つ／持たない現実世界の被写体を合成する困難でリアリスティックな３Ｄデータセットの位置合わせおよび認識のタスクに用いることができる。
【０１６７】
別の実施形態において、ｓＲｔ平均値シフトは、初期化に関してメドイドシフト、ハフ投票（回転は省略）のいずれかにより、計算時間を削減することができる。さらに、位置合わせと認識スコアの間の相関の欠如は、入力投票の重みが改善されうることを示唆する。
【０１６８】
別の実施形態において、ＳＲＴ距離は画像中の被写体検出に適用され、これらの方法は画像中の特定のクラス（例えば全ての人物の顔のクラス）の被写体を検出する問題を対象とする。これらの方法では、被写体の位置は図１５に示されるような正方ウインドウによって特定される。これは画像中の被写体を包含するバウンディングボックスを表わす。正方ウインドウは、被写体の画像内回転を表現するために、回転され得る。
【０１６９】
この方法において、スケール、位置、方位が異なる多数のウインドウが画像全域にわたってスキャンされ、その各々はポジティブとネガティブのどちらかに分類される。ポジティブとは、ウインドウが関心被写体を含むことを意味し、ネガティブとは、そうでないことを意味する。そして、互いにオーバーラップするポジティブウインドウがグループ化される。各グループについて、「平均（average）」ウインドウが計算される。
【０１７０】
本発明の実施形態に従う方法では、ｓＲｔ平均はウインドウ集合からの「平均」ウインドウを計算するために用いられる。平均ウインドウのリストは、検出被写体およびそれらの位置のリストとして返される。
【０１７１】
別の実施形態において、代表ウインドウが各グループのメドイドウインドウとして選ばれる。メドイドウインドウは、それ自体がグループ内のウインドウであって、他のウインドウとの平均距離が最小であるウインドウである。この実施形態において、ウインドウ間の距離がｓＲｔ距離を用いて計算される。
【０１７２】
別の実施形態において、部品から関節オブジェクトを追跡する方法が提供される。画像シーケンス上で関節オブジェクトを追跡するために、この方法ではトラッキングが容易な被写体の剛体部分を検出しまたは追跡する別の方法を利用する。各部品について、被写体の幾つかの候補姿勢を生成する。結果を合成して最良解を求める際に投票ベース姿勢推定フレームワークを用いることができる。最大の重みを持った姿勢が現在の姿勢として返される。
【０１７３】
本発明の実施形態に従う方法は、動き分離に適用することもできる。映像シーケンスでは、複数の動きが同時に起こる場合がある。例えば、異なる被写体あるいは被写体部分が異なる方向に向かって移動する。映像シーケンスからこれらの動きをセグメント化することが目的である。動き分離は、複数被写体のトラッキングのための初期ステップに役立つ。動き分離法は、連続する２つのフレームにおける点、一対の点、あるいは点集合の間の対応を明らかにする。これらの対応は２Ｄ変換として表わされる。
【０１７４】
２Ｄ変換はグループにクラスター化され、その各々は動き（motion）を形成する。２Ｄ変換が単純な平行移動、スケーリング、回転を含むと仮定される場合、２Ｄ用途の投票ベース姿勢推定フレームワークを２Ｄ変換のセグメント化に用いることができる。この実施形態では、本発明の実施形態に従う方法を用いて２Ｄ画像あるいは３Ｄ画像を処理する。
【０１７５】
本発明の実施形態に従う方法はカメラ姿勢推定に用いられてもよい。カメラ姿勢推定では、シーン中の較正カメラの姿勢を該カメラによってキャプチャーされた画像シーケンスから直接的に推定することに興味が示される。カメラ姿勢推定はステレオ３Ｄ再構成法の重要なステップである。
【０１７６】
一般に、カメラ姿勢推定法は、画像シーケンスから２Ｄコーナー点を検出し追跡する。連続する２つのフレーム間で追跡される隣接コーナー点の各小集合を用いてカメラ姿勢候補を生成することができる。カメラ姿勢候補の重みは、他のコーナー点が候補姿勢にどれだけ一致するかをカウントすることにより推定することができる。図４〜１０を参照して説明された姿勢推定フレームワークは、最尤姿勢を見つけるのに用いることができる。
【０１７７】
別の実施形態において、カメラ姿勢はｓＲｔ平均を用いて重み付けされた平均姿勢から推定され、あるいはｓＲｔ距離を用いて重み付けされたメドイド姿勢を検出することにより推定される。
【０１７８】
いくつかの実施形態を説明したが、これらの実施形態は例示のみを目的としており、発明の範囲を制限することは意図していない。実際には、本明細書で説明した新規の方法およびシステムは他の様々な形で具体化することができ、また発明の要旨から逸脱しない範囲で、本明細書で説明した方法およびシステムの構造における様々な省略、置換、および変更を行ってもよい。添付の特許請求の範囲およびその均等物は、発明の範囲および要旨に含まれうる構造あるいは改良に及ぶことが意図される。
【関連出願】
【０００１】
本出願は、２０１１年７月１１日に提出された英国特許出願第１１１１８７１．８号に基づいており、その優先権の利益を主張するものであって、その全内容は参照により本明細書に組込まれる。
【技術分野】
【０００２】
本明細書で説明されているように本発明の実施形態は、一般に画像処理の分野に関する。
【背景技術】
【０００３】
画像処理においては、画像内の被写体の姿勢を推定することが必要となる場合がしばしばある。これは、２Ｄ被写体の検出と分離（2D object detection motion segmentation）、カメラ姿勢推定、３Ｄ形状位置合わせおよび３Ｄ画像認識を含むさまざまな画像タスクで発生する。姿勢推定により、被写体の位置、回転あるいはスケールの推定が必要となりうる。
【図面の簡単な説明】
【０００４】
以下の非制限の実施形態を参照して本発明の実施形態を説明する。
【図１】図１（ａ）はキャプチャー３Ｄ画像から生成された点群であり、図１（ｂ）は図１（ａ）の点群から認識された被写体を示す。
【図２】図２は３Ｄ画像のキャプチャーに用いられた装置の概略図である。
【図３】図３は本発明の実施形態に従う方法を実現するように構成されたハードウェアシステムの概略図である。
【図４】図４は本発明の実施形態に従う方法において用いることができる、特徴をキャプチャーする方法を示すフローチャートである。
【図５】図５は特徴を示す写真である。
【図６】図６（ａ）は被写体のキャプチャー３Ｄ画像から生成された点群であり、図６（ｂ）は抽出された特徴とともに図６（ａ）の画像を示す。
【図７】図７は本発明の実施形態に従う方法の概略図である。
【図８】図８はカーネル密度推定法を用いてモデル化された予測姿勢密度のプロットである。
【図９】図９は２つの姿勢の間の変動を示す概略図である。
【図１０】図１０（ａ）乃至（ｃ）は本発明の方法に従う、入力姿勢、密度推定およびフィルタリングの段階を示す３枚の図である。
【図１１】図１１（ａ）は、画像化される被写体および本発明の実施形態に従う方法を用いて処理された画像であり、図１１（ｂ）は図１１（ａ）の被写体の点群であり、図１１（ｃ）は図１１（ｂ）の点群に検出された特徴を重ね合わせた図であり、図１１（ｄ）は、検出された特徴をデータベースのものと比較した後に生成された予測姿勢の図である。図１１（ｅ）は、図１１（ａ）における被写体についてシステムによって返された登録ＣＡＤモデルである。
【図１２】図１２（ａ）〜１２（ｊ）は、本発明の実施形態に従う方法を用いて認識され登録される工業用部品の例である。
【図１３】図１３は図１２の被写体の混同行列である。
【図１４】図１４（ａ）は本発明の実施形態に従って認識された工業用部品の点群である。
【図１５】図１５は、写真中の顔の位置を認識するために本発明の実施形態に従う方法をどのように用いることができるか示す写真である。
【発明を実施するための形態】
【０００５】
一実施形態によれば、各被写体姿勢が共通の座標系の位置、方向、スケールに関して表現される場合の２つの被写体姿勢を比較する方法が提供される。該方法は、前記２つの被写体姿勢間の距離を計算することを含む。前記距離は距離関数
【数１】
【０００６】
を用いて計算される。Ｘは１つの被写体の被写体姿勢であり、Ｙは別の被写体の被写体姿勢であり、
【数２】
【０００７】
である。
【０００８】
ｓ（Ｘ）およびｓ（Ｙ）は被写体姿勢ＸおよびＹのスケールをそれぞれ表わすスカラー関数、Ｒ（Ｘ）およびＲ（Ｙ）は被写体姿勢ＸおよびＹの回転をそれぞれ表現する行列、ｔ（Ｘ）およびｔ（Ｙ）は被写体姿勢ＸおよびＹの平行移動をそれぞれ表現するベクトル、σｓ、σｒ、σｔはそれぞれｄｓ、ｄｒ、ｄｔの重み係数である。
【０００９】
上記距離基準（ｓＲｔ距離と称する）は、例えば車両情報システムにおける車両、歩行者、街灯柱などの被写体を認識し位置合わせするといった様々な処理に用いられる。例えば製造ライン等で工業用部品を認識する場合に用いることができ、画像内のクラッターシーンからの手、顔、心臓、肺、ポリープなどの認識に用いられ、カメラ姿勢推定、被写体追跡技術、医用画像技術における組織位置合わせ／ポリープ検出、車両ナビゲーション技術、ヒューマンコンピュータ技術（ＨＣＩ）、オートフォーカス技術などに用いられる。
【００１０】
上記の距離基準は、当該距離を用いるカーネルの開発に適している。カーネルは、Ｋ（ｄ２（Ｘ，Ｙ））で表される。
【００１１】
一実施形態において、カーネルは
【数３】
【００１２】
の式で表されるガウスカーネルである。ここで、σはカーネルのバンド幅である。ｓＲｔ距離を用いるガウスカーネルは、姿勢空間における確率密度関数を表わす。これは、ユークリッド空間においてポピュラーな正規分布に似ていて、分析的に非常にトレーサブルであり（つまり扱いやすい）、その「ベル」形状は、確率変数を実際にモデル化する際に有利である。
【００１３】
上記の重み付けは応用に応じて選択することができる。一実施形態では０．０４≦σｓ≦０．１２、０．０６≦σｒ≦０．２０、０．０６≦σｔ≦０．２０である。
【００１４】
平均を計算する方法が上記の距離基準に基づいてもよい。したがって、更なる実施形態によれば、複数の被写体姿勢の平均を比較する方法が提供される。該方法は、
【数４】
【００１５】
を用いて平均被写体姿勢を計算することを含む。ここで、Ｘ＝｛（Ｘ１，ｗ１），（Ｘ２，ｗ２），．．．（ＸＮ，ｗＮ）｝は姿勢集合、Ｘｉはｉ番目の姿勢、ｗｉはｉ番目の姿勢の重み、ｓ（Ｘｉ）は被写体姿勢Ｘｉのスケールを表わすスカラー関数、Ｒ（Ｘｉ）は被写体姿勢Ｘｉの回転を表現する行列、ｔ（Ｘｉ）被写体姿勢Ｘｉの平行移動を表現するベクトルである。
【数５】
【００１６】
はＳＯ（ｎ，Ｒ）への行列Ｘの特殊直交射影である。ここで、ＳＯ（ｎ，Ｒ）は全ｎ×ｎ特殊直交行列の集合であり、関数ｓｏｐ（Ｘ）はＹ−Ｘのフロベニウスノルムが最小化されるように特殊直交行列Ｙを返す。
【００１７】
別の実施形態において、画像データを分析する方法が提供される。前記方法は、被写体姿勢の複数の予測を得るために前記画像データを分析することを含む。前記予測は、被写体の予測姿勢のインジケーションを含む。予測姿勢は共通の座標系の位置、方向、スケールに関して表現される。
【００１８】
また、２つの被写体姿勢間の距離の計算により予測姿勢を比較することで予測をグループ化することを含む。該距離は距離関数
【数６】
【００１９】
を用いて計算される。
【００２０】
ここで、ＸとＹは同一被写体の被写体姿勢であって、
【数７】
【００２１】
であり、ｓ（Ｘ）およびｓ（Ｙ）は被写体姿勢ＸおよびＹのスケールをそれぞれ表わすスカラー関数、Ｒ（Ｘ）およびＲ（Ｙ）は被写体姿勢ＸおよびＹの回転をそれぞれ表現する行列、ｔ（Ｘ）およびｔ（Ｙ）は被写体姿勢ＸおよびＹの平行移動をそれぞれ表現するベクトル、σｓ、σｒ、σｔはそれぞれｄｓ、ｄｒ、ｄｔの重み係数である。
【００２２】
上記の方法によって分析された画像は少なくとも１つの被写体を含み、前記予測は前記被写体とその姿勢のインジケーションを含む。前記被写体のインジケーションは、少なくともデータの一部をデータベースにおける被写体のデータと比較することにより得ることができる。一実施形態において、前記データベースの各被写体は複数の特徴を含む。該データベースの被写体と画像データを比較することは、前記画像データを分析して前記データベースの被写体の特徴との一致を求めることを含む。
【００２３】
別の構成において、姿勢を推定する被写体は、画像をキャプチャーするのに用いられるカメラである。
【００２４】
実施形態において、各姿勢の複数の予測が生成されると、代表姿勢を決定できるようにするために、姿勢の密度を推定する密度推定法が用いられる。一実施形態において、被写体姿勢をグループ化することは、全姿勢が分布ｆ（Ｘ）からサンプリングされることを仮定するカーネル密度推定法を用いることを含み、前記カーネル密度推定法における前記カーネルは前記距離関数を含む。
【００２５】
前記グループ化によって形成されたグループの代表姿勢は、ｆ（Ｘ）の極大値の決定により計算することができる。この極大値は、平均値シフト、クイックシフトあるいはメドイドシフトのような様々な技術を用いて得ることができる。
【００２６】
実施形態の平均値シフト技術において、反復の各段階の平均は
【数８】
【００２７】
を用いて計算される。
【００２８】
ここで、Ｘｉはｉ番目の姿勢であり、ｗｉは平均被写体姿勢を計算するためのｉ番目の姿勢の重みである。また、χ＝｛（Ｘ１，ｗ１），（Ｘ２，ｗ２），．．．（ＸＮ，ｗＮ）｝は、Ｘｉをｉ番目の姿勢とするときの姿勢集合であり、ｗｉはｉ番目の姿勢の重みである。
【数９】
【００２９】
は、ＳＯ（ｎ，Ｒ）への行列Ｘの特殊直交射影である。ここで、ＳＯ（ｎ，Ｒ）は全ｎ×ｎ特殊直交行列の集合であり、関数ｓｏｐ（Ｘ）は、Ｙ−Ｘのフロベニウスノルムが最小化されるような特殊直交行列Ｙを返す。
【００３０】
重みｗｉは、ｗｉ＝λｉ＊Ｋ（ｄ２（Ｙ，Ｘｉ））から求めることができる。ここで、Ｋはカーネル関数であり、ｄは、平均値シフト技術を用いて推定された現在の極大値Ｙを持つ姿勢と、姿勢Ｘｉとの間の距離である。別の実施形態において、距離ｄは上述のｓＲｔ距離である。しかしながら、該平均を用いた他の重みを用いてもよい。平均値シフト法においてｗｉ＝λｉ＊Ｋ（ｄ２（Ｙ，Ｘｉ））の場合、Ｙが固定ならば、Ｙは
【数１０】
【００３１】
の極大である。しかしながら、他の方法はこの制約を要しない。
【００３２】
ある実施形態において、演算時間を削減するために、先ずハフ投票法またはメドイドシフト法を用いて姿勢推定が予測される。ある実施形態では、各予測は初期の重みを持つ。
【００３３】
上記方法は２Ｄおよび３Ｄの画像データに適用することができる。さらに、該方法をより高い次元に拡張することもできる。
【００３４】
さらに別の実施形態において、各被写体姿勢が共通の座標系の位置、方向、スケールに関して表現される場合の２つの被写体姿勢を比較するための装置が提供される。該装置はプロセッサを含む。
【００３５】
前記プロセッサは２つの被写体姿勢間の距離を計算するように構成され、該距離は距離関数
【数１１】
【００３６】
を用いて計算される。
【００３７】
ここで、Ｘは１つの被写体の被写体姿勢である。また、Ｙは別の被写体の被写体姿勢であり、
【数１２】
【００３８】
であり、ｓ（Ｘ）およびｓ（Ｙ）は被写体姿勢ＸおよびＹのスケールをそれぞれ表わすスカラー関数、Ｒ（Ｘ）およびＲ（Ｙ）は被写体姿勢ＸおよびＹの回転をそれぞれ表現する行列、ｔ（Ｘ）およびｔ（Ｙ）は被写体姿勢ＸおよびＹの平行移動をそれぞれ表現するベクトル、σｓ、σｒ、σｔはそれぞれｄｓ、ｄｒ、ｄｔの重み係数である。
【００３９】
本発明の実施形態は、ハードウェアまたは汎用計算機のソフトウェアによって実現することができる。また、本発明の実施形態は、ハードウェアとソフトウェアの組み合わせとして実現することができる。本発明の実施形態は、単一の処理装置あるいは処理装置の分散ネットワークによって実装することもできる。
【００４０】
本発明の実施形態はソフトウェアによって実現することができ、本発明の実施形態は任意の適合する記録媒体によって汎用計算機に導入される計算機コードを含む。記録媒体は、フロッピー（登録商標）ディスク、ＣＤ ＲＯＭ、磁気デバイス、プログラマブルメモリデバイスのような任意の計算機可読記録媒体を含むことができる。
【００４１】
第１実施形態に従うシステムおよび方法を説明する。
【００４２】
図１（ａ）は、４つの被写体１、３、５および７を含むシーンの点群である。点群は図２を参照して説明した装置を用いて得られる。点群は、３Ｄイメージング技術によって得られた表面への法線から構築された表面上の予測点を含む。
【００４３】
図１（ｂ）は、図１（ａ）のシーンを含む、被写体１、３、５および７の認識を可能にするために本発明に従う方法によって変更された後の図１（ａ）のデータを示す。
【００４４】
図２は本発明の一実施形態を被写体１１の画像をキャプチャーし、当該被写体の姿勢を認識するのに使用したシステムの概略図である。被写体１１は３つの異なる光源１３，１５，１７によって照明される。この実施形態では、これら３つの光源がそれぞれ異なる３色の光を発することができる。ここでは、赤、緑、青の色を、これら３色を識別できるビデオカメラを得ることができるので、選択することとする。しかしながら、ビデオカメラで識別できる色を発光できるものであれば、どのような色を発光する光源であってもよい。また、可視光外の放射光源も使用することができる。色の正確な濃淡または発光の周波数はビデオカメラに依る。一実施形態では、光源は複数のプロジェクタであり、場面（シーン）がそれぞれのプロジェクタからのそれぞれの発光色で照明されるよう複数のフィルターを設ける。また、さらに別の実施形態では、被写体を照明するのにＬＥＤが用いられる。
【００４５】
一実施形態において、光源光は、カメラ内のセンサによりキャプチャーされた周波数に、それぞれのセンサが０から２５５の範囲の色をキャプチャーされるように調整される。この範囲より外の色が決定されると、サチュレーションが起こることがあり、その場合、生成される３−Ｄ画像に誤差が生じる。
【００４６】
この実施形態において、３つの光源１３，１５，１７は被写体１の周りに横方向に配置され、フロア位置から被写体１の高さまでの間の数段階に縦方向に置かれる。ある実施形態においては、光源１３，１５，１７は三角形に配置される。一配置例では、三角形配置された光源は隣り合う光源の間隔が１から３メートルであり、他の配置例では、隣り合う光源の間隔が１．５メートルから２．５メートルである。光源は被写体１に向けられている。
【００４７】
三光源１３，１５，１７の角度は、被写体１１を中心にその回転面においておよそ３０度の間隔で設けられる。角度間隔が大きいほど方向に依存する色はよりはっきりと変化する。光源が離れすぎていると、被写体１のへこんだ形の部分の識別が難しくなる。これは、そのような部分でつくられる影は被写体のさらに大きな部分に拡大され、データの解析をさらに難しくするからである。好ましくは、被写体１の各部分が三つのすべての光源１３，１５，１７で照明される。
【００４８】
第２の光源１５の縦方向下に位置するカメラ１９は、３つの光源３，５，７で照明されながら移動する被写体を記録するために用いられる。光源が三角に配置される実施形態においては、カメラ１９はその三角形の面の内部に設置されてもよい。
【００４９】
カメラ１９は異なった色の複数の画像を分離することができる。これは、カメラ内のフィルター機構によりなされる。こうして、カメラ１９は三つのすべての光源からの照明を利用して被写体１１の画像をキャプチャーすることができ、それぞれの光源からの反射光を順次識別することができる。したがって、赤、緑、青の光源からのそれぞれの反射光を用いて画像を生成することができる。
【００５０】
一実施形態において、第一ビデオカメラは生画像データを出力する。例えばＭＰＥＧのようなデータ圧縮機構は使用されない。画像データの圧縮により、再構成された３Ｄ画像に影響が現れる可能性がある。
【００５１】
カメラ１９でキャプチャーされたデータは解析部２０に供給される。解析部２０は、三光源１３，１５，１７に接続されている。
【００５２】
図３はシステム解析部２０の可能な基本構造を示す。解析部２３は、プログラム２５を実行するプロセッサ２３を有する。解析部１３は、さらにストレージ２７を有する。ストレージ２７は、カメラ１９（図２）から受け取ったデータを解析し、光源１３，１５，１７の照明を制御するためのプログラム２５で用いられるデータを記憶する。解析部２０はさらに入力モジュール１１と出力モジュール３３を有する。入力モジュール３１はカメラ入力部３５に接続されている。カメラ入力部３５はカメラ１９からのデータを受け取る。カメラ入力部３５はカメラから単に直接データを受け取ってもよいし、または、外部記憶媒体またはネットワークからデータを受け取ってもよい。
【００５３】
出力モジュール３３にはディスプレイ３７が接続されている。ディスプレイ３７はカメラ入力部３５から受け取ったカメラデータからキャプチャーされた３Ｄ画像を表示する。ディスプレイ２７の代わりに、出力モジュール３３がファイルまたはインターネット等を介して出力を行ってもよい。
【００５４】
使用時において、解析部２０はカメラ入力部３３を介してカメラデータを受け取る。プロセッサ２３で実行されるプログラム２５は、３Ｄ画像データを生成するためにストレージ２７に記憶されたデータを使ってカメラデータを解析し、被写体およびその姿勢を認識する。該データは出力モジュール３３を介してディスプレイ３７に出力される。
【００５５】
上記は、フォトメトリックステレオ技術を用いて３Ｄ被写体データをキャプチャーする技術を示している。しかしながら、(少なくとも1つの光源および2つのカメラを用いる)２眼ステレオのような他の方法が可能であり、タイムオブフライトセンサやアクティブ光源デプスセンサを用いてもよい。
【００５６】
次に、キャプチャーされたシーンの画像内の被写体およびそれらの姿勢を検出するための方法を説明する。
【００５７】
被写体認識を行なえるようにするには、システムは、認識対象となりうる被写体に関する情報を記憶するための学習をしておく必要がある。これを図４を参照して説明する。
【００５８】
まずステップＳ４０１では、１つの被写体または複数の被写体が図２および３を参照して説明されたものと同様の装置を用いて画像化される。
【００５９】
この実施形態では、各被写体に座標系が割り当てられる。一実施形態において、該座標系の原点は被写体の中心に位置し、該座標系の各軸の方向は被写体の向きに一致し、この座標系における単位長は被写体のスケールと等しい。該座標系は、グローバル座標系の点をローカル座標系に変形する単一の４ｘ４アフィン変換行列によって定められる。
【００６０】
特徴が被写体から抽出される。特徴は特定が容易な球状の領域である。特徴の例を図５に示す。
【００６１】
特徴を特定する方法は既知であり、ここでは詳細に述べない。本実施形態では、各特徴にローカル座標系を設定する。座標系の原点は特徴の中心に位置し、軸の方向は特徴の基準方向に一致し、該座標系における単位長は特徴の半径と等しい。該座標系もまたグローバル座標系の点をローカル座標系に変形する４ｘ４変換行列によって定められる。特徴の座標系において、原点に近い固定位置での３１点がサンプリングされ、３１次元の記述子ベクトルが生成される。（領域中心、領域半径、方向、記述子）のタプルが特徴を形成し、これはステップＳ４０５において記憶される。
【００６２】
したがって、データベース内の各特徴について、特徴のローカル座標系の変換行列、およびそれに関連した被写体のローカル座標系の両方が既知である。特徴の変換行列がＦ１であって、被写体の変換行列がＭ１である場合、Ｍ１にＦ１の逆数を乗ずる（つまりT=M1(F1)^(-1)を計算する）ことにより、特徴のローカル座標系の点を、関連する被写体のローカル座標系に変形する変換行列Ｔが求まる。
【００６３】
被写体がスケーリング、平行移動および回転によって変形される場合、行列Ｔは不変である。上記処理は、シーンに存在すると考えられる被写体について繰り返される。例えば図６（ｂ）の被写体６１に関して、図６（ｂ）は被写体６１に割り当てられた特徴６３を示す。
【００６４】
図７を参照して説明するように、動作中に、図２および３を参照して説明したように画像がキャプチャーされる。ステップＳ４１１において、この画像から特徴が抽出される。図４を参照して上述したように特徴について述べる。データベースにおける特徴の記述子と、画像から抽出された特徴の記述子との間に一致が見られる場合、予測が生成される。
【００６５】
実施形態において、ユークリッド距離が閾値未満である場合、２つの記述子間には一致がある。画像から抽出された特徴とデータベースにおける特徴との間に一致がある場合、ステップＳ４１５において予測が生成される。この予測は、どのような被写体が現時点で認識されており、それはどこにあるかの仮説である。
【００６６】
実施形態において、シーン上の特徴が一致する場合、該特徴のローカル座標系の変換行列のみが識別される。２つの特徴が一致する場合、テストシーンからの特徴のローカル座標系の点を予測被写体のローカル座標系に変形する変換行列は、Ｔと同じであると考えられる。したがって、グローバル座標系からの一致特徴の変換行列がＦ２である場合、予測被写体のローカル座標系を表わす変換行列は、ＴにＦ２を乗ずること（つまりM2’=T F2）により与えられる。Ｍ２’は予測被写体姿勢のスケール、中心点および方位を与える。
【００６７】
要するに、２つの記述子の一致によって、２つの対応する領域が同じ形状を持つものと見なされる。データベースからの特徴における被写体の識別、位置、スケールおよび方位は既知であることから、データベースからの特徴がシーンからの特徴と同じ場所に移動し、スケーリングし、回転するように該被写体を（スケーリング、平行移動、回転によって）変形することができる。これは、変形の後にこの被写体がシーンに存在することを予測するのに用いられる。
【００６８】
上記方法は多くの予測をもたらす。この予測は、ステップＳ４１７においてグループ化される。
【００６９】
各予測は、被写体のＩＤおよびその姿勢に関する情報を含む。該姿勢（Ｘ）について、各姿勢は変換行列
【数１３】
【００７０】
として表わすことができる。
【００７１】
ここで、ｓ（Ｘ）は被写体のサイズに関係のある実数、Ｒ（Ｘ）はこれに沿って被写体が向く方向を示す正方行列、ｔ（Ｘ）は被写体中心の位置を示すベクトルである。
【００７２】
姿勢をグループ化するために、カーネル密度推定法（ＫＤＥ）が用いられる。この方法では、被写体について多数の姿勢Ｘ１，Ｘ２，．．．，Ｘｎが考慮される。
【００７３】
各姿勢Ｘｉは、高次元（非ユークリッド）空間の点と見なされ、重みλｉを持つ。
【００７４】
場合によっては、全姿勢が同等に処理され、全姿勢についてλｉ＝１である。別の実施形態において、姿勢には重みが加えられる。
【００７５】
一つの方法として、重み付けは、データベースにおける被写体の特徴および被写体のインスタンスの数を考慮に入れることにより行なわれる。
【００７６】
例えば、データベースにＮ個の被写体がある場合、各被写体は複数のインスタンスを持ち得るのであって、各インスタンスは、異なる姿勢でスキャンされた同じ被写体を表わす点群である。そのようなシナリオでは、各被写体にはＮｋ個のインスタンスが存在し得る。この場合、被写体Ｋの各インスタンスｋはＮｋ，ｌ個の特徴を持つ。このシナリオでは、各姿勢の初期重み（シーン上の特徴と特徴とを一致させる結果である）は、
【数１４】
【００７７】
に設定される。
【００７８】
ＫＤＥ法では、全姿勢が未知の確率密度関数ｆ（Ｘ）からサンプリングされることを仮定している。姿勢をグループ化する問題は、ｆ（Ｘ１’），ｆ（Ｘ２’），．．．，ｆ（Ｘｍ’）が局所的に最大化される全ての点Ｘ１’，Ｘ２’，．．．，Ｘｍ’を求めることとして再定式化される。各対（Ｘｊ’，ｆ（Ｘｊ’））は代表姿勢（Ｘｊ’）およびその重み（ｆ（Ｘｊ’））を定める。
【００７９】
この実施形態では、この問題を次の２つのステップによって解決する。
【００８０】
（１）（Ｘ１，λ１）、（Ｘ２，λ２）、（Ｘｎ，λｎ）からｆ（Ｘ）を推定すること。
【００８１】
（２）ｆ（Ｘ）からの極大値Ｘ１’，Ｘ２’，．．．，Ｘｍ’を求めること。
【００８２】
ＫＤＥは、
【数１５】
【００８３】
の式で表されるカーネル密度推定量
【数１６】
【００８４】
が未知の密度関数ｆ（Ｘ）を近似できることを仮定する方法である。
【００８５】
ここで、Ｋ（）は距離関数ｄ（）を用いるカーネル密度関数であり、
【数１７】
【００８６】
はＫ（）のボリューム密度関数である。上記は全姿勢についてλｉ＝１を仮定している。
【００８７】
この式において、各点Ｘｉは、カーネル関数に基づいてＸｉを中心とする密度関数をアサートし、それは、図８のトレース２０１に示されるような小さな「ブロブ（ｂｌｏｂ）」として現われ、
【数１８】
【００８８】
は簡単には全ての密度関数の平均であり、それはトレース２０３として示された全ブロブの平均として現われる。ＫＤＥにおいて、
【数１９】
【００８９】
がｆ（Ｘ）を推定するのに用いられる。
【数２０】
【００９０】
は、入力点から直接定義されるので、ｆ（Ｘ）の推定は問題にならない。そのような系の極大値は、平均値シフト、メドイド（medoid）シフト、クイックシフトのような方法を用いて求めることができる。
【００９１】
カーネル密度関数Ｋ（）を定義する必要がある（つまり、点からの小さなブロブを定義することである）。これは任意のユークリッド空間において行うことができる。しかし、これを非ユークリッド空間において行うのは困難である。全姿勢の空間は非ユークリッドである。本発明の実施形態に従って、距離基準に基づくガウスＳＲＴカーネル
【数２１】
【００９２】
が用いられる。ここで、ＸとＹは図９に概略的に示されるような被写体姿勢、ｓ（Ｘ）およびｓ（Ｙ）は被写体姿勢ＸおよびＹのスケールをそれぞれ表わすスカラー関数、Ｒ（Ｘ）およびＲ（Ｙ）は被写体姿勢ＸおよびＹの回転をそれぞれ表現する行列、ｔ（Ｘ）およびｔ（Ｙ）は被写体姿勢ＸおよびＹの平行移動をそれぞれ表現するベクトル、σｓ、σｒ、σｔは重み係数である。ノルム
【数２２】
【００９３】
は、行列のフロベニウスノルムを表わし、ノルム
【数２３】
【００９４】
はベクトルのユークリッドノルムを表わす。
【００９５】
実施形態において、σｓ、σｒ、σｔは、システムの独立なテストセットにおける位置合わせスコアの最大化により求まる。この手続きでは、既知の被写体姿勢を用いて２００の点群のテストセットが作成される。システムは（σｓ，σｒ，σｔ）の異なる組み合わせを用いてこれらの点群について実行される。その後、各組み合わせについてシステムが正しく位置合わせをする回数のカウントがなされる。次の場合、位置合わせは正解である。
【００９６】
出力スケールはグランドトルーススケールの５％未満である。
【００９７】
出力位置とグランドトルース位置の間の距離は、グランドトルーススケールの１０％以内である。
【００９８】
出力方位とグランドトルース方位の間の角度は１５度未満である。
【００９９】
正しい位置合わせの数を最大化する（σｓ，σｒ，σｔ）の組み合わせが選択される。
【０１００】
実施形態において、一般的な範囲は次のとおりである。
【０１０１】
・σｓ＝０．０４．．０．１２
・σｒ＝０．０６．．０．２０
・σｔ＝０．０６．．０．２０
比をσｓ：σｒ：σｔ＝７：１２：１２、例えば（σｓ，σｒ，σｔ）＝（０．０７，０．１２，０．１２）とすれば上手く行くことが分かった。
【０１０２】
ここで、極大値を求めるための平均値シフト技術について説明する。平均値シフト法は初期姿勢から開始する。この姿勢をＹとする。カーネル（ここではガウスカーネル）Ｋ（）が定義されていることを考慮し、上述の距離基準を用いることにより、この方法は、Ｙが動かなくなるまで繰り返しＹを「移動させる」。
【０１０３】
ガウスカーネルが上述の距離基準を用いている場合、Ｙ、ｇＹ（Ｘ）に中心がある（つまり
【数２４】
【０１０４】
に定義された全てのブロブと同じ形の小ブロブ）。すべての姿勢Ｘｉについて、新しい重みｗｉ＝λｉ＊ｇＹ（Ｘ）を設定する。したがって、Ｙの近くの姿勢は大きな重みを持ち、Ｙから遠くはなれた姿勢は小さな重みを持っている。
【０１０５】
そして、新たな平均Ｙ’を（Ｘ１，ｗ１），（Ｘ２，ｗ２），（Ｘｎ，ｗｎ）から計算することができ、ＹがＹ’にセットされる。実施形態において、上記距離基準に基づいた平均を用いて平均が計算される。この平均は、ｓＲｔ平均と呼ばれ、
【数２５】
【０１０６】
である。
【０１０７】
ここで、χ＝｛（Ｘ１，ｗ１），（Ｘ２，ｗ２），．．．（ＸＮ，ｗＮ）｝は姿勢の集合、Ｘｉはｉ番目の姿勢、ｗｉはｉ番目の姿勢に関連した重みであり、該重みは姿勢の精度のインジケーションである。ここで、
【数２６】
【０１０８】
は行列ＸのＳＯ（ｎ，Ｒ）への特殊直交射影である。ここで、ＳＯ（ｎ，Ｒ）は全ｎ×ｎ特殊直交行列の集合である（つまり、ＹＴＹが恒等行列となり、Ｙの行列式が１となる任意のｎ×ｎの実行列Ｙ）。関数ｓｏｐ（Ｘ）は、Ｙ−Ｘのフロベニウスノルムが最小化されるような特殊直交行列Ｙを返す。関数ｓｏｐ（Ｘ）は既知である。これは、既知の方法によって効率的に実装することができる。
【０１０９】
Ｙが動かなくなる（つまり、Ｙ’はＹと同じである）場合、Ｙは、
【数２７】
【０１１０】
の極大値に一致することが数学的に証明される。平均値シフトは、できるだけ多くの極大値を求めるために開始点を異ならせて多数回実行される。新たなＳＲＴ平均を計算するステップにおいて、異なる重みにより全姿勢から単一の平均を計算する。しかし実際のところｗｉが小さすぎる場合、新たなｓＲｔ平均の計算に（Ｘｉ，ｗｉ）が織り込まれるかどうかにかかわらず、該成分は結果として生ずる平均にほとんど影響がない。したがって計算を省くために、ｗｉが閾値より大きい姿勢ＸｉのみからｓＲｔ平均を計算する。一実施形態においては、この閾値として１Ｅ−１１を用いる。
【０１１１】
上記は全ての被写体について繰り返される。
【０１１２】
次に、ステップＳ４１９においてフィルター処理が行なわれる。ここで、最大の重みを持った代表姿勢が選択される。この姿勢に重なった被写体を表わす全姿勢が削除される。次に、２番目に大きい重みを持った姿勢が処理され、この姿勢に重なった全姿勢もまた削除される。該ステップは、処理中の姿勢の重みが閾値より小さくなるか、姿勢がなくなるまで繰り返される。
【０１１３】
これにより、シーン内の全ての被写体の識別およびその姿勢が得られる。
【０１１４】
図１０（ａ）乃至（ｃ）は、図７を参照して説明した処理を概略的に示している。図１０（ａ）は一致特徴のそれぞれについて予測が生成されるステップＳ４１５に対応する。
【０１１５】
図１０（ｂ）は、姿勢についてカーネル密度推定法を用いた密度推定が行なわれることを示す。これは、Ｓ４１７のグループ化ステップの一部を成す。図１０（ｃ）に示すように、各クラスターにおける姿勢はグループ化され、各クラスターの代表姿勢が形成される。
【０１１６】
上記実施形態では、投票ベースの３Ｄ形状認識および位置合わせが提供される。投票は、各被写体について予測された３Ｄ姿勢である。上記実施形態は、平行移動、回転、スケールを同時に用いて、３Ｄ応用に平均値シフトを適用する。
【０１１７】
上記は直接相似変形の空間における３Ｄ姿勢投票に平均値シフトを用いる。この空間の姿勢間に距離基準が導入される（ＳＲＴ距離）。これはユークリッド距離とは異なり左不変であって、リーマン距離とは対照的にユニークで閉じた形の平均を持つ。したがって、計算上効率的である。
【０１１８】
上記実施形態では、可能な姿勢の組または投票のコレクションによって、姿勢の経験分布が確立される。投票は、テスト被写体からのローカル特徴を、既知の姿勢を持ったライブラリの特徴に一致させることにより計算される。
【０１１９】
そして第２のステップは、該分布における１つ以上の「最良な」姿勢を求めることである。上記実施形態では、これは確率の極大値を繰り返し求める平均値シフト処理によって実現される。
【０１２０】
上記実施形態のシステムは、既知の方位を持った関心被写体が固定されない場合に対処することができる。上記実施形態では、被写体が認識され、直接相似群、即ち平行移動、回転、スケールによってパラメータ化された等方相似変換群において位置合わせされる。スケールは、入力データのスケールが未知であるか高いクラス内スケール変動がある場合に必要である。回転は完全な位置合わせに必要であり、より正確な認識をもたらす。結果として得られる７Ｄ姿勢空間は大きすぎるので、既知の技術を用いる現行の計算機能力では効率的に分析することができない。
【０１２１】
上記実施形態は平均値シフト技術を用いている。上記技術において、スケールおよび回転はユークリッド距離およびリーマン距離のような既知の距離尺度を用いる課題を導入し得る。ユークリッド距離はスケール不変ではなく、回転は非線形多様体（manifold）を生成し、それへの投影はスケールのバイアスを引き起こす。リーマン距離の平均は閉じた形の解を持たず、計算が遅い。
【０１２２】
上記の距離基準はスケール、回転、平行移動の不変性を付随的に提供する。実施形態において、この距離の重み付け平均には以下の特性がある。
【０１２３】
１．ユニークであること。
【０１２４】
２．閉じた形であること−これは計算を効率化する。
【０１２５】
３．スケール互換であること。回転および平行移動がすべて等しい場合、平均はスケールの平均として作用する筈である。数学的に、あるＲ’およびｔ’について
【数２８】
【０１２６】
であるならば、Ｒ（μ（χ））＝Ｒ’であり、ｔ（μ（χ））＝ｔ’であり、ｓ（μ（χ））がｓ（Ｘｉ）の平均である場合、μはスケール互換である。
【０１２７】
４．回転互換であること。
【数２９】
【０１２８】
ならば、ｓ（μ（χ））＝ｓ’であり、ｔ（μ（χ））＝ｔ’であり、Ｒ（μ（χ））はＲ（Ｘｉ）’ｓの平均である。
【０１２９】
５．平行移動互換であること。
【数３０】
【０１３０】
であるならば、ｓ（μ（χ））＝ｓ’であり、Ｒ（μ（χ））＝Ｒ’であり、ｔ（μ（χ））はｔ（Ｘｉ）’ｓの平均である。
【０１３１】
６．左不変であること。左不変距離は事後変換に不変のものである。すなわち、
【数３１】
【０１３２】
である。この特性は、（ａ）左共変平均すなわち
μ（ＺＸ）＝Ｚμ（Ｘ）
を導く。つまり、全姿勢ＸｉがＺによって変換される場合、平均もＺによって変換される。また、（ｂ）平均値シフトで計算された重みｗｉは任意の事後変換Ｚに対して不変であり、左共変平均シフトをもたらすことを保証する。
【０１３３】
対称距離は
【数３２】
【０１３４】
となるように定められ、直観的に望ましいものに見えるが、これが無くても平均値シフトにおける距離の使用が妨げられることはなく、リストされた特性を与えられるならば、それは必要ではない。右共変も望ましい特性と考えられるかもしれないが、３Ｄ認識のコンテキストにおいて、この存在は何ら意味のある振る舞いに関係しない。
【０１３５】
ｓＲｔ距離はその成分
【数３３】
【０１３６】
に分割することができる。
【０１３７】
ここで、ｄｓ（）、ｄｒ（）、ｄｔ（）はそれぞれスケール、回転、平行移動の距離である。
【０１３８】
あるバンド幅係数σｓ；σｒ；σｔ＞０を所与として、ｓＲｔ距離は次のように定義される。
【数３４】
【０１３９】
σｓ；σｒ；σｔを制御することによりスケール、回転、平行移動のうちの１つの種類の変換に対して他のものより敏感なｓＲｔ距離を生成することが可能であり、したがって、非常に柔軟性がある。
【０１４０】
ｄｓＲｔ（）が定義されると、ｄｓＲｔ（）により導入される平均μｓＲｔは次のように定義される。
【数３５】
【０１４１】
これは、平均をもたらし、
【数３６】
【０１４２】
である。
【０１４３】
ここで、
【数３７】
【０１４４】
は、ＳＯ（ｎ，Ｒ）への行列Ｘの特殊直交射影である。ここで、ＳＯ（ｎ，Ｒ）は全ｎ×ｎ特殊直交行列の集合である（つまり、ＹＴＹが恒等行列となり、Ｙの行列式が１となる任意のｎ×ｎの実行列Ｙ）。関数ｓｏｐ（Ｘ）は、Ｙ−Ｘのフロベニウスノルムが最小化されるような特殊直交行列Ｙを返す。関数ｓｏｐ（Ｘ）は既知である。これは、既知の方法（例えばM. Moakher. Means and averaging in the group of rotations. SIAM J. Matrix Anal. Appl., 24:1-16, 2002）によって効率的に実装することができる。
【０１４５】
上記において回転平均行列を計算する場合、全ての回転行列Ｒ（Ｘｉ）の重み付け算術平均が計算される。これは、関数ｓｏｐ（）を介してそれに近い真の回転行列と置き換えられる。任意の特殊直交行列は実行列であり、逆もまた同様である。重み付け平均行列は必ずしも回転行列ではないので、Ｓｏｐ（）はこの実施形態において用いられる。
【０１４６】
上記の実例説明のために、物理的な被写体およびこれに一致するＣＡＤモデルを用意し、１２の形状クラスから成る実験データを用いて実験を行った。
【０１４７】
図１１（ａ）に示されるような各被写体のジオメトリを、図１１（ｂ）に示すように点群の形で様々な角度から２０回ほどキャプチャーした。クラスラベルと共に、すべての形状インスタンスは関連するグランドトルース姿勢を持つ。これは、先ずおおよその関連ＣＡＤモデルを点群に手動で位置合わせし、該位置合わせを改善するためにＩｔｅｒａｔｉｖｅ Ｃｌｏｓｅｓｔ Ｐｏｉｎｔアルゴリズムを用いることにより計算される。
【０１４８】
入力姿勢投票Ｘの計算は、テスト点群および（クラスおよび姿勢が既知の）学習点群の集合を所与として２段階の処理である。第一段階において、記述子と、被写体に関連するスケール、平行移動、回転とから構成されるローカル形状特徴が図１１（ｃ）に示すような全ての点群について計算される。先ず最も近い点への各ボクセル中心の距離についてのガウスオペレーターを用いて点群を１２８３のボクセルボリュームに変換する。次に、ガウスオペレーターの差分を利用する３次元位置とスケールによって特徴点をローカライズし、各特徴点の基準方向を計算してローカル特徴姿勢を生成する。最終的には、特徴点の周囲３１箇所の規則的に分布した位置において（正確なスケールで）ボリュームを単純にサンプリングすることにより、基礎となる３１次元の記述子を計算する。
【０１４９】
第二段階では、記述子間のユークリッド距離に関して各テスト特徴を２０の最も近い学習特徴に一致させる。これら一致の各々により、図１１（ｄ）に示されるテスト被写体の姿勢の投票Ｘｉ＝ＡＢ−１Ｃが生成される。Ａ、Ｂ、Ｃは、それぞれ、テスト特徴、学習特徴、学習被写体のグランドトルース姿勢である。さらに、各投票は（ＮＣＮＩ）−１として計算される重み即ちλｉを持つ。ＮＣはクラス内の学習インスタンスの数、ＮＩは特徴の特定インスタンスにおいて求まった特徴の数である。
【０１５０】
平均値シフトは、所与の被写体クラスの出力姿勢分布において局所最頻値とその重みを求める。そのような最頻値は多数存在しうることから、平均値シフトは各クラスにつき１００のランダムな入力姿勢から開始する。各最頻値は、重複を除外しつつ、全クラスにわたる候補姿勢のリストに加えられる。Ｓ＋（３）では、回転の四元数表現すなわちｑ（Ｘ）を用いることが可能である。この式を用いることにより、ｄｓＲｔ（）の回転成分を次のように定義することができる。
【数３８】
【０１５１】
ここで、｜．．．｜はｑ（Ｘ）および−ｑ（Ｘ）が同じ回転を表わすことを示すために必要である。この式は、他のものに比較して計算量が少ないという利点を持ち、当該空間における非成分的（noncomponent-wise）な距離を与える。
【０１５２】
この例では、平均値シフト推論アプローチと比較するためにハフ投票法を実装した。これは、回転を効果的に周辺化して、平行移動およびスケールに関する４Ｄヒストグラムの各ビン（bin）に該当する、姿勢投票の重みの和を計算するものである。ビン幅は４次元の各々における平均形状幅（あるいはスケール）の０．１６倍になるように設定される。各クラスで最も高いビンの和は姿勢の最頻値を定義する。
【０１５３】
学習データの評価に交差検定を用いた。各クラスにおける２０個の形状インスタンスのうちの１９個から学習セットを作成した。各クラスの残りのインスタンスはテスト形状となる。各テスト形状に５つのランダムな変換（０．５−２の範囲の平行移動、回転、スケール）を施し、この処理をテスト形状である各学習形状で繰り返し、１クラス当たり１００のテストインスタンスを生成する。
【０１５４】
図１２に示すような、１２個のクラスを評価に用いた。これらは、ベアリング、ブロック、ブラケット、車両、歯車、フランジ、ノブ、パイプ、２つのピストンである。これは全部で１０００個のテストをもたらす。残りの２つのクラスは、最適なカーネルバンド幅（σ）を学習するために推論法に用いられる。
【０１５５】
推論法は２つの基準（認識率と位置合わせ率）について評価された。
【０１５６】
認識率−上述したように、重みと共に姿勢およびクラスにわたる最頻値のリストが生成される。出力クラスは最も高い重みの最頻値のクラスである。混同行列は全テストにわたる出力クラス対グランドトルースクラスを記録する。認識率は、この行列のトレースすなわち正解分類の数から与えられる。
【０１５７】
位置合わせ率−あるテストの出力姿勢は、そのクラスがグランドトルースクラスと一致する重み付け（weightiest）最頻値の出力姿勢から与えられる。次のスケール、回転、平行移動の判定基準
【数３９】
【０１５８】
をすべて満たす場合、姿勢Ｘは正しいと考えられる。Ｙはグランドトルース姿勢である。対称性がある被写体の場合には、Ｙが複数存在し、最も接近しているものへの距離が用いられる。
【０１５９】
平均値シフトアルゴリズムに用いられるσｓ、σｒ、σｔを決めるために、（最終評価に用いられない）２つの学習クラスの交差検定から位置合わせ率を最大化する。位置合わせ率は局所探索を用いて最大化される。初期バンド幅が選ばれ、この値と値１：２および１＝この値の１：２倍について位置合わせ率が計算される。最も高いスコアを持つ値が選ばれ、収束するまで当該処理は繰り返される。学習するべきパラメータを３つとし、３Ｄグリッドについて局所探索が計算される。
【０１６０】
表１は、ｓＲｔを用いる平均値シフト法の定量的な結果をまとめたものである。
【表１】
【０１６１】
表１によれば、ｓＲｔ平均値シフトは、認識と位置合わせの両方について良い結果を示すことがわかる。３行目はスケールおよび平行移動のみを考慮する場合の位置合わせ率である。また５行目は位置合わせ結果の出力スケールの平均（各々はグランドトルーススケールに対する出力スケールの比）を示している。
【０１６２】
平均値シフト法のクラスごとの位置合わせ率を表２に示す。
【表２】
【０１６３】
ｓＲｔ推論法の混同行列を図１３に示す。
【０１６４】
図１４は、複数の被写体を含んだ現実のシーンにｓＲｔ平均値シフトを容易に適用できることを示している
別の実施形態において、該システムは、地表面および衝突検出の位置のような物理的な制約を用いて出力姿勢のリストをフィルターしてもよい。これにより誤判定結果の数を低減することができる。
【０１６５】
上記は、直接相似変換の空間すなわちＳ＋（ｎ）における姿勢についての平均値シフトにおけるｓＲｔ距離の利用を示している。距離は左不変であるものとし、スケール、回転、平行移動互換の望ましい特性を伴うユニークでクローズドな形の平均を持つことを示した。
【０１６６】
この距離は、視覚ベースのジオメトリキャプチャーシステムおよび基本特徴とともに回転の対称性を持つ／持たない現実世界の被写体を合成する困難でリアリスティックな３Ｄデータセットの位置合わせおよび認識のタスクに用いることができる。
【０１６７】
別の実施形態において、ｓＲｔ平均値シフトは、初期化に関してメドイドシフト、ハフ投票（回転は省略）のいずれかにより、計算時間を削減することができる。さらに、位置合わせと認識スコアの間の相関の欠如は、入力投票の重みが改善されうることを示唆する。
【０１６８】
別の実施形態において、ＳＲＴ距離は画像中の被写体検出に適用され、これらの方法は画像中の特定のクラス（例えば全ての人物の顔のクラス）の被写体を検出する問題を対象とする。これらの方法では、被写体の位置は図１５に示されるような正方ウインドウによって特定される。これは画像中の被写体を包含するバウンディングボックスを表わす。正方ウインドウは、被写体の画像内回転を表現するために、回転され得る。
【０１６９】
この方法において、スケール、位置、方位が異なる多数のウインドウが画像全域にわたってスキャンされ、その各々はポジティブとネガティブのどちらかに分類される。ポジティブとは、ウインドウが関心被写体を含むことを意味し、ネガティブとは、そうでないことを意味する。そして、互いにオーバーラップするポジティブウインドウがグループ化される。各グループについて、「平均（average）」ウインドウが計算される。
【０１７０】
本発明の実施形態に従う方法では、ｓＲｔ平均はウインドウ集合からの「平均」ウインドウを計算するために用いられる。平均ウインドウのリストは、検出被写体およびそれらの位置のリストとして返される。
【０１７１】
別の実施形態において、代表ウインドウが各グループのメドイドウインドウとして選ばれる。メドイドウインドウは、それ自体がグループ内のウインドウであって、他のウインドウとの平均距離が最小であるウインドウである。この実施形態において、ウインドウ間の距離がｓＲｔ距離を用いて計算される。
【０１７２】
別の実施形態において、部品から関節オブジェクトを追跡する方法が提供される。画像シーケンス上で関節オブジェクトを追跡するために、この方法ではトラッキングが容易な被写体の剛体部分を検出しまたは追跡する別の方法を利用する。各部品について、被写体の幾つかの候補姿勢を生成する。結果を合成して最良解を求める際に投票ベース姿勢推定フレームワークを用いることができる。最大の重みを持った姿勢が現在の姿勢として返される。
【０１７３】
本発明の実施形態に従う方法は、動き分離に適用することもできる。映像シーケンスでは、複数の動きが同時に起こる場合がある。例えば、異なる被写体あるいは被写体部分が異なる方向に向かって移動する。映像シーケンスからこれらの動きをセグメント化することが目的である。動き分離は、複数被写体のトラッキングのための初期ステップに役立つ。動き分離法は、連続する２つのフレームにおける点、一対の点、あるいは点集合の間の対応を明らかにする。これらの対応は２Ｄ変換として表わされる。
【０１７４】
２Ｄ変換はグループにクラスター化され、その各々は動き（motion）を形成する。２Ｄ変換が単純な平行移動、スケーリング、回転を含むと仮定される場合、２Ｄ用途の投票ベース姿勢推定フレームワークを２Ｄ変換のセグメント化に用いることができる。この実施形態では、本発明の実施形態に従う方法を用いて２Ｄ画像あるいは３Ｄ画像を処理する。
【０１７５】
本発明の実施形態に従う方法はカメラ姿勢推定に用いられてもよい。カメラ姿勢推定では、シーン中の較正カメラの姿勢を該カメラによってキャプチャーされた画像シーケンスから直接的に推定することに興味が示される。カメラ姿勢推定はステレオ３Ｄ再構成法の重要なステップである。
【０１７６】
一般に、カメラ姿勢推定法は、画像シーケンスから２Ｄコーナー点を検出し追跡する。連続する２つのフレーム間で追跡される隣接コーナー点の各小集合を用いてカメラ姿勢候補を生成することができる。カメラ姿勢候補の重みは、他のコーナー点が候補姿勢にどれだけ一致するかをカウントすることにより推定することができる。図４〜１０を参照して説明された姿勢推定フレームワークは、最尤姿勢を見つけるのに用いることができる。
【０１７７】
別の実施形態において、カメラ姿勢はｓＲｔ平均を用いて重み付けされた平均姿勢から推定され、あるいはｓＲｔ距離を用いて重み付けされたメドイド姿勢を検出することにより推定される。
【０１７８】
いくつかの実施形態を説明したが、これらの実施形態は例示のみを目的としており、発明の範囲を制限することは意図していない。実際には、本明細書で説明した新規の方法およびシステムは他の様々な形で具体化することができ、また発明の要旨から逸脱しない範囲で、本明細書で説明した方法およびシステムの構造における様々な省略、置換、および変更を行ってもよい。添付の特許請求の範囲およびその均等物は、発明の範囲および要旨に含まれうる構造あるいは改良に及ぶことが意図される。
【特許請求の範囲】
【請求項１】
画像データを分析するための装置であって、該装置はプロセッサを含み、
前記プロセッサは、
被写体の姿勢の複数の予測を得るために前記画像データを分析するよう構成され、前記予測は前記被写体の予測姿勢のインジケーションを含んでおり、前記予測姿勢は共通の座標系の位置、方向、スケールに関して表現され、
２つの被写体姿勢間の距離を計算することで前記予測姿勢を比較することにより前記予測をグループ化するように構成され、前記距離は距離関数を用いて計算される、装置。
【請求項２】
前記距離関数は
【数４０】
を含み、ここで、ＸおよびＹは同一被写体の被写体姿勢であり、
【数４１】
であり、ｓ（Ｘ）およびｓ（Ｙ）は被写体姿勢ＸおよびＹのスケールをそれぞれ表わすスカラー関数、Ｒ（Ｘ）およびＲ（Ｙ）は被写体姿勢ＸおよびＹの回転をそれぞれ表現する行列、ｔ（Ｘ）およびｔ（Ｙ）は被写体姿勢ＸおよびＹの平行移動をそれぞれ表現するベクトル、σｓ、σｒ、σｔはそれぞれｄｓ、ｄｒ、ｄｔの重み係数である、請求項１に記載の装置。
【請求項３】
前記画像は少なくとも１つの被写体を含み、前記予測は前記被写体とその姿勢のインジケーションを含む、請求項１に記載の装置。
【請求項４】
前記被写体の前記インジケーションを、少なくとも前記画像データの一部をデータベースの被写体のデータと比較することにより求める、請求項３に記載の装置。
【請求項５】
前記データベースの各被写体は複数の特徴を含み、該データベースの被写体と前記画像データを比較することは、前記画像データを分析して前記データベースの被写体の特徴との一致を求めることを含む、請求項４に記載の装置。
【請求項６】
前記被写体は、前記画像をキャプチャーするのに用いられるカメラである、請求項１に記載の装置。
【請求項７】
全姿勢が分布ｆ（Ｘ）からサンプリングされることを仮定するカーネル密度推定法を用いて前記被写体姿勢がグループ化され、前記カーネル密度推定における前記カーネルは前記距離関数を含む、請求項４に記載の装置。
【請求項８】
前記グループの代表姿勢を、ｆ（Ｘ）の極大値を決定することにより計算する請求項７に記載の装置。
【請求項９】
前記極大値を平均値シフト技術、クイックシフト技術またはメドイドシフト技術を用いて求める請求項８に記載の装置。
【請求項１０】
前記極大値を平均値シフト技術を用いて求め、反復の各段階の平均を
【数４２】
を用いて計算し、ここで、Ｘｉはｉ番目の姿勢であり、ｗｉは前記平均被写体姿勢を計算するためのｉ番目の姿勢の重みであり、χ＝｛（Ｘ１，ｗ１），（Ｘ２，ｗ２），．．．（ＸＮ，ｗＮ）｝は、Ｘｉを前記ｉ番目の姿勢とするときの姿勢集合であり、ｗｉは前記ｉ番目の姿勢の重みであって、
【数４３】
はＳＯ（ｎ，Ｒ）への行列Ｘの特殊直交射影であって、ここで、ＳＯ（ｎ，Ｒ）は全ｎ×ｎ特殊直交行列の集合であり、関数ｓｏｐ（Ｘ）はＹ−Ｘのフロベニウスノルムが最小化されるように特殊直交行列Ｙを返す、請求項８に記載の装置。
【請求項１１】
重みｗｉをｗｉ＝λｉ＊Ｋ（ｄ２（Ｙ，Ｘｉ））から求め、Ｋはカーネル関数であり、ｄは、平均値シフト技術を用いて推定された現在の極大値Ｙを持つ姿勢と、姿勢Ｘｉとの間の距離である、請求項１０に記載の装置。
【請求項１２】
前記姿勢評価が先ずハフ投票法を用いてグループ化される請求項９に記載の装置。
【請求項１３】
各予測が初期の重みを持つ請求項１に記載の装置。
【請求項１４】
前記画像データは３Ｄ画像データである請求項１に記載の装置。
【請求項１５】
各被写体姿勢が共通の座標系の位置、方向、スケールに関して表現される場合の２つの被写体姿勢を比較するための装置であって、該装置はプロセッサを含み、前記プロセッサは前記２つの被写体姿勢間の距離を計算するように構成され、前記距離は、距離関数
【数４４】
を用いて計算され、ここで、Ｘは１つの被写体の被写体姿勢であり、Ｙは別の被写体の被写体姿勢であって、
【数４５】
であり、ｓ（Ｘ）およびｓ（Ｙ）は被写体姿勢ＸおよびＹのスケールをそれぞれ表わすスカラー関数、Ｒ（Ｘ）およびＲ（Ｙ）は被写体姿勢ＸおよびＹの回転をそれぞれ表現する行列、ｔ（Ｘ）およびｔ（Ｙ）は被写体姿勢ＸおよびＹの平行移動をそれぞれ表現するベクトル、σｓ、σｒ、σｔはそれぞれｄｓ、ｄｒ、ｄｔの重み係数である、装置。
【請求項１６】
前記距離は、前記距離を用いるカーネルを用いて計算され、前記カーネルは、Ｋ（ｄ２（Ｘ，Ｙ））の式で表される、請求項１５に記載の装置。
【請求項１７】
前記カーネルは
【数４６】
の式で表されるガウスカーネルであって、σはカーネルのバンド幅である、請求項１６に記載の装置。
【請求項１８】
０．０４≦σｓ≦０．１２、０．０６≦σｒ≦０．２０、０．０６≦σｔ≦０．２０である、請求項１５に記載の装置。
【請求項１９】
複数の被写体姿勢の平均を決定するための装置であって、該装置はプロセッサを含み、
前記プロセッサは
【数４７】
を用いて前記複数の被写体姿勢の平均を計算するように構成され、ここで、Ｘ＝｛（Ｘ１，ｗ１），（Ｘ２，ｗ２），．．．（ＸＮ，ｗＮ）｝は姿勢集合、Ｘｉはｉ番目の姿勢、ｗｉはｉ番目の姿勢の重み、ｓ（Ｘｉ）は被写体姿勢Ｘｉのスケールを表わすスカラ関数、Ｒ（Ｘｉ）は被写体姿勢Ｘｉの回転を表現する行列、ｔ（Ｘｉ）被写体姿勢Ｘｉの平行移動を表現するベクトルであり、
【数４８】
はＳＯ（ｎ，Ｒ）への行列Ｘの特殊直交射影であり、ＳＯ（ｎ，Ｒ）は全ｎ×ｎ特殊直交行列の集合であり、関数ｓｏｐ（Ｘ）はＹ−Ｘのフロベニウスノルムが最小化されるように特殊直交行列Ｙを返す、装置。
【請求項２０】
画像データを分析する方法であって、該方法は
被写体の姿勢の複数の予測を得るために前記画像データを分析することを含み、前記予測は前記被写体の予測姿勢のインジケーションを含んでおり、前記予測姿勢は共通の座標系の位置、方向、スケールに関して表現され、
２つの被写体姿勢間の距離を計算することで前記予測姿勢を比較することにより前記予測をグループ化することを含み、前記距離は距離関数を用いて計算される、方法。
【請求項２１】
請求項２０の方法をコンピュータに実行させるように構成されたコンピュータ可読命令を記録する記憶媒体。
【請求項１】
画像データを分析するための装置であって、該装置はプロセッサを含み、
前記プロセッサは、
被写体の姿勢の複数の予測を得るために前記画像データを分析するよう構成され、前記予測は前記被写体の予測姿勢のインジケーションを含んでおり、前記予測姿勢は共通の座標系の位置、方向、スケールに関して表現され、
２つの被写体姿勢間の距離を計算することで前記予測姿勢を比較することにより前記予測をグループ化するように構成され、前記距離は距離関数を用いて計算される、装置。
【請求項２】
前記距離関数は
【数４０】
を含み、ここで、ＸおよびＹは同一被写体の被写体姿勢であり、
【数４１】
であり、ｓ（Ｘ）およびｓ（Ｙ）は被写体姿勢ＸおよびＹのスケールをそれぞれ表わすスカラー関数、Ｒ（Ｘ）およびＲ（Ｙ）は被写体姿勢ＸおよびＹの回転をそれぞれ表現する行列、ｔ（Ｘ）およびｔ（Ｙ）は被写体姿勢ＸおよびＹの平行移動をそれぞれ表現するベクトル、σｓ、σｒ、σｔはそれぞれｄｓ、ｄｒ、ｄｔの重み係数である、請求項１に記載の装置。
【請求項３】
前記画像は少なくとも１つの被写体を含み、前記予測は前記被写体とその姿勢のインジケーションを含む、請求項１に記載の装置。
【請求項４】
前記被写体の前記インジケーションを、少なくとも前記画像データの一部をデータベースの被写体のデータと比較することにより求める、請求項３に記載の装置。
【請求項５】
前記データベースの各被写体は複数の特徴を含み、該データベースの被写体と前記画像データを比較することは、前記画像データを分析して前記データベースの被写体の特徴との一致を求めることを含む、請求項４に記載の装置。
【請求項６】
前記被写体は、前記画像をキャプチャーするのに用いられるカメラである、請求項１に記載の装置。
【請求項７】
全姿勢が分布ｆ（Ｘ）からサンプリングされることを仮定するカーネル密度推定法を用いて前記被写体姿勢がグループ化され、前記カーネル密度推定における前記カーネルは前記距離関数を含む、請求項４に記載の装置。
【請求項８】
前記グループの代表姿勢を、ｆ（Ｘ）の極大値を決定することにより計算する請求項７に記載の装置。
【請求項９】
前記極大値を平均値シフト技術、クイックシフト技術またはメドイドシフト技術を用いて求める請求項８に記載の装置。
【請求項１０】
前記極大値を平均値シフト技術を用いて求め、反復の各段階の平均を
【数４２】
を用いて計算し、ここで、Ｘｉはｉ番目の姿勢であり、ｗｉは前記平均被写体姿勢を計算するためのｉ番目の姿勢の重みであり、χ＝｛（Ｘ１，ｗ１），（Ｘ２，ｗ２），．．．（ＸＮ，ｗＮ）｝は、Ｘｉを前記ｉ番目の姿勢とするときの姿勢集合であり、ｗｉは前記ｉ番目の姿勢の重みであって、
【数４３】
はＳＯ（ｎ，Ｒ）への行列Ｘの特殊直交射影であって、ここで、ＳＯ（ｎ，Ｒ）は全ｎ×ｎ特殊直交行列の集合であり、関数ｓｏｐ（Ｘ）はＹ−Ｘのフロベニウスノルムが最小化されるように特殊直交行列Ｙを返す、請求項８に記載の装置。
【請求項１１】
重みｗｉをｗｉ＝λｉ＊Ｋ（ｄ２（Ｙ，Ｘｉ））から求め、Ｋはカーネル関数であり、ｄは、平均値シフト技術を用いて推定された現在の極大値Ｙを持つ姿勢と、姿勢Ｘｉとの間の距離である、請求項１０に記載の装置。
【請求項１２】
前記姿勢評価が先ずハフ投票法を用いてグループ化される請求項９に記載の装置。
【請求項１３】
各予測が初期の重みを持つ請求項１に記載の装置。
【請求項１４】
前記画像データは３Ｄ画像データである請求項１に記載の装置。
【請求項１５】
各被写体姿勢が共通の座標系の位置、方向、スケールに関して表現される場合の２つの被写体姿勢を比較するための装置であって、該装置はプロセッサを含み、前記プロセッサは前記２つの被写体姿勢間の距離を計算するように構成され、前記距離は、距離関数
【数４４】
を用いて計算され、ここで、Ｘは１つの被写体の被写体姿勢であり、Ｙは別の被写体の被写体姿勢であって、
【数４５】
であり、ｓ（Ｘ）およびｓ（Ｙ）は被写体姿勢ＸおよびＹのスケールをそれぞれ表わすスカラー関数、Ｒ（Ｘ）およびＲ（Ｙ）は被写体姿勢ＸおよびＹの回転をそれぞれ表現する行列、ｔ（Ｘ）およびｔ（Ｙ）は被写体姿勢ＸおよびＹの平行移動をそれぞれ表現するベクトル、σｓ、σｒ、σｔはそれぞれｄｓ、ｄｒ、ｄｔの重み係数である、装置。
【請求項１６】
前記距離は、前記距離を用いるカーネルを用いて計算され、前記カーネルは、Ｋ（ｄ２（Ｘ，Ｙ））の式で表される、請求項１５に記載の装置。
【請求項１７】
前記カーネルは
【数４６】
の式で表されるガウスカーネルであって、σはカーネルのバンド幅である、請求項１６に記載の装置。
【請求項１８】
０．０４≦σｓ≦０．１２、０．０６≦σｒ≦０．２０、０．０６≦σｔ≦０．２０である、請求項１５に記載の装置。
【請求項１９】
複数の被写体姿勢の平均を決定するための装置であって、該装置はプロセッサを含み、
前記プロセッサは
【数４７】
を用いて前記複数の被写体姿勢の平均を計算するように構成され、ここで、Ｘ＝｛（Ｘ１，ｗ１），（Ｘ２，ｗ２），．．．（ＸＮ，ｗＮ）｝は姿勢集合、Ｘｉはｉ番目の姿勢、ｗｉはｉ番目の姿勢の重み、ｓ（Ｘｉ）は被写体姿勢Ｘｉのスケールを表わすスカラ関数、Ｒ（Ｘｉ）は被写体姿勢Ｘｉの回転を表現する行列、ｔ（Ｘｉ）被写体姿勢Ｘｉの平行移動を表現するベクトルであり、
【数４８】
はＳＯ（ｎ，Ｒ）への行列Ｘの特殊直交射影であり、ＳＯ（ｎ，Ｒ）は全ｎ×ｎ特殊直交行列の集合であり、関数ｓｏｐ（Ｘ）はＹ−Ｘのフロベニウスノルムが最小化されるように特殊直交行列Ｙを返す、装置。
【請求項２０】
画像データを分析する方法であって、該方法は
被写体の姿勢の複数の予測を得るために前記画像データを分析することを含み、前記予測は前記被写体の予測姿勢のインジケーションを含んでおり、前記予測姿勢は共通の座標系の位置、方向、スケールに関して表現され、
２つの被写体姿勢間の距離を計算することで前記予測姿勢を比較することにより前記予測をグループ化することを含み、前記距離は距離関数を用いて計算される、方法。
【請求項２１】
請求項２０の方法をコンピュータに実行させるように構成されたコンピュータ可読命令を記録する記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２０１３−３３４６８（Ｐ２０１３−３３４６８Ａ）
【公開日】平成２５年２月１４日（２０１３．２．１４）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−１５５４４５（Ｐ２０１２−１５５４４５）
【出願日】平成２４年７月１１日（２０１２．７．１１）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２５年２月１４日（２０１３．２．１４）
【国際特許分類】
【出願番号】特願２０１２−１５５４４５（Ｐ２０１２−１５５４４５）
【出願日】平成２４年７月１１日（２０１２．７．１１）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]