(57)【特許請求の範囲】
【請求項１】
事前3Dシーン・モデルに基づいて、3Dオブジェクトを含みシーンを表現する3Dシーン・モデルを計算する方法であって：
（ａ）前記シーンの画像を取得する段階と；
（ｂ）前記3Dシーン・モデルを前記事前3Dシーン・モデルに初期化する段階と；
（ｃ）前記3Dシーン・モデルを前記取得された画像と整合するよう修正することを：
（ｉ）前記取得された画像のデータを前記3Dシーン・モデルのオブジェクトと比較し、結果として関連付けられたデータおよび関連付けられていないデータを与えるステップであって、前記関連付けられたデータは前記比較において前記3Dモデル内の3Dオブジェクトのいずれかと関連付けられた取得された画像データであり、前記関連付けられていないデータは前記比較において前記3Dシーン・モデルのどの3Dオブジェクトとも関連付けられていない取得された画像データである、ステップを行い；
（ｉｉ）前記関連付けられていないデータを使って前記事前3Dシーン・モデル内にない新しい3Dオブジェクトを計算し、該新しい3Dオブジェクトを前記3Dシーン・モデルに加え；
（ｉｉｉ）前記関連付けられたデータを使って前記事前3Dシーン・モデル内にある、前記シーンの前記取得された画像には存在しない3Dオブジェクトを検出して該存在しない3Dオブジェクトを前記3Dシーン・モデルから除去することによって行う段階とを含む、
方法。
【請求項２】
請求項１記載の方法であって、前記シーンの画像がレンジ画像であり、前記3Dシーン・モデルの各オブジェクトpが符号付き距離関数をもち、前記画像のデータを前記3Dシーン・モデルのオブジェクトと比較することがさらに、各オブジェクトpについて、前記画像中の位置であって、前記位置に適用された前記オブジェクトpの前記符号付き距離関数の値が所定の許容値以下であり、前記位置に適用された他のすべてのオブジェクトqについての前記距離関数の値がpの距離関数の値より小さくないような位置を見出すことを含み、これらの位置のデータ点が前記オブジェクトpの関連付けられたデータであり、前記3Dシーン・モデルのどのオブジェクトpとも関連付けられていない任意の位置のデータ点が関連付けられていないデータである、方法。
【請求項３】
請求項２記載の方法であって、前記関連付けられていないデータを使って新しいオブジェクトを計算することがさらに、誤差項を含む目的関数を最適化することを含み、誤差項の値はオブジェクトの表面上で0であるデータ・モデル化関数から値が計算される方法。
【請求項４】
前記目的関数が誤差項の指数関数を含む、請求項３記載の方法。
【請求項５】
請求項１記載の方法であって、前記シーンの画像はレンジ画像であり、前記3Dシーン・モデルの各オブジェクトpが符号付き距離関数をもち、前記関連付けられたデータを使って存在しないオブジェクトを検出することがさらに：
（ａ）前記3Dシーン・モデル中の各オブジェクトpについて、前記画像の第一の数n個のデータ点であって、該データ点に適用される前記オブジェクトの前記符号付き距離関数が所定の許容値未満であるデータ点を計算する段階と、
（ｂ）前記3Dシーン・モデルをレンダリングした結果において見える前記オブジェクトの第二の数N個の位置を計算する段階と、
（ｃ）前記オブジェクトについてnがNの所定の関数未満であれば、前記オブジェクトpに対し、前記オブジェクトpが前記シーンに存在しないかどうかを判定するための追加的な確認を実行する段階とを含む、
方法。
【請求項６】
請求項５記載の方法であって、前記追加的な確認がさらに、前記オブジェクトpを隠蔽する前記画像から計算されうる他のオブジェクトがないことを判定する段階を含む、方法。
【請求項７】
請求項６記載の方法であって、前記計算された3Dシーン・モデルを前記画像と整合するよう修正する段階がさらに、前記関連付けられたデータおよび前記3Dシーン・モデルを使って前記3Dシーン・モデルにおいて存在するオブジェクトのポーズを調整することを含む、方法。
【請求項８】
請求項７記載の方法であって、前記オブジェクトpを隠蔽する前記画像から計算されうる他のオブジェクトがないことを判定する段階がさらに、すべての新しいオブジェクトが計算されて前記3Dシーン・モデルに追加され、前記3Dシーン・モデルにおける既存のオブジェクトにすべてのポーズ調整がなされたあとにのみ前記オブジェクトpを処理することを含む、方法。
【請求項９】
請求項１記載の方法であって、前記取得された画像のデータを前記3Dシーン・モデルのオブジェクトと比較する段階がさらに：
（ａ）前記3Dシーン・モデルの各オブジェクトpをレンダリングし、結果としてpについてのレンダリングされた画像を与える段階と；
（ｂ）ある位置にある前記取得された画像データの値と前記位置にあるオブジェクトpについての前記レンダリングされた画像の値との間の第一の差がある許容差以下であり、他のすべてのオブジェクトqについて、前記位置にある前記取得された画像データの値と前記位置にあるオブジェクトqについての前記レンダリングされた画像の値との間の第二の差が前記第一の差より小さくないような前記画像中の位置を見出す段階とを含み、それらの位置のデータ点が前記オブジェクトpの関連付けられたデータであり、前記3Dシーン・モデルのどのオブジェクトとも関連付けられていない任意の位置のデータ点が関連付けられていないデータである、方法。
【請求項１０】
請求項１記載の方法であって、前記関連付けられたデータを使って存在しないオブジェクトを検出することが：
（ａ）前記3Dシーン・モデルをレンダリングして合成レンダリングを生じる段階と；
（ｂ）前記合成レンダリングを使ってオブジェクトに関連付けられた合成データを計算する段階と；
（ｃ）前記関連付けられたデータを、オブジェクトに関連付けられた前記合成データと比較して、前記取得された画像中に現れない前記3Dシーン・モデル中のオブジェクトを見出す段階と；
（ｄ）前記取得された画像中に現れない前記3Dシーン・モデル中の前記オブジェクトに対し、該オブジェクトが前記シーンに存在していないかどうかを判定するための追加的な確認を実行する段階とを含む、
方法。
【請求項１１】
請求項１０記載の方法であって、前記追加的な確認がさらに、前記画像中に現れない各オブジェクトpについて、前記画像から計算されうる他のオブジェクトであって前記オブジェクトpを隠蔽する他のオブジェクトがないことを判定することを含む、方法。
【請求項１２】
請求項１１記載の方法であって、前記画像はレンジ・データであり、前記画像中に現れない各オブジェクトpについて、前記画像から計算されうる第二のオブジェクトであって前記オブジェクトpを隠蔽する第二のオブジェクトがないことを判定することがさらに：
（ａ）前記3Dシーン・モデル中のオブジェクトおよび前記画像データを前面から背面の順に処理する段階と；
（ｂ）新しいオブジェクトがあれば見出し、該新しいオブジェクトを前記3Dシーン・モデルに追加する段階と；
（ｃ）前記3Dシーン・モデル中で、動いたオブジェクトがあればそのポーズを調整する段階と；
（ｄ）前記オブジェクトpより前面にある前記3Dシーン・モデルおよび画像データ中のすべてのオブジェクトが処理されたのち、前記画像のデータを前記3Dシーン・モデル中のオブジェクトpと比較し、オブジェクトpに関連付けられた画像を生じる段階と；
（ｅ）前記3Dシーン・モデル中のオブジェクトpをレンダリングしてオブジェクトpについての合成データを生じる段階と；
（ｆ）オブジェクトpに関連付けられた前記画像データをオブジェクトpについての前記合成データと比較して、前記オブジェクトpが前記画像中に現れるかどうかを判定する段階とを含む、
方法。
【請求項１３】
請求項１記載の方法であって、計算された前記3Dシーン・モデルを前記画像と整合するよう修正することを行う段階が、前記関連付けられたデータおよび前記3Dシーン・モデルを使って、前記3Dシーン・モデル中に存在するオブジェクトのポーズを調整することをさらに含む、方法。
【請求項１４】
請求項１記載の方法であって、計算された前記3Dシーン・モデルを前記画像と整合するよう修正することを行う段階が：
（ａ）前記関連付けられていないデータをデータ・クラスターにクラスター化する段階と；
（ｂ）前記データ・クラスターを使って新しいオブジェクトを計算する段階と；
（ｃ）前記新しいオブジェクトを前記3Dシーン・モデルに追加する段階とをさらに含む、
方法。
【請求項１５】
請求項１記載の方法であって、新しいオブジェクトを計算する前記段階がさらに、新しいオブジェクトが一つまたは複数の支持するオブジェクトと接触していることを要求する、方法。
【請求項１６】
請求項１記載の方法であって、新しいオブジェクトを計算する前記段階がさらに、新しいオブジェクトが他のいかなるオブジェクトとも衝突していないことを要求する、方法。
【請求項１７】
請求項１記載の方法であって、前記画像のデータを前記3Dシーン・モデルのオブジェクトと比較することがさらに；
（ａ）前記画像を処理して画像特徴を検出する段階と；
（ｂ）前記3Dシーン・モデル中の各オブジェクトpを処理して、見えるであろうpのモデル特徴を検出する段階と；
（ｃ）前記画像特徴が前記モデル特徴に同じまたは近い位置においてマッチし、前記3Dシーン・モデルの他のいかなるオブジェクトqからのモデル特徴ともよりよいマッチをもたない場合に、前記画像特徴を前記モデル特徴に関連付ける段階と；
（ｄ）オブジェクトpのモデル特徴に関連付けられた前記画像特徴を、オブジェクトpに関連付けられたデータとして取る段階とを含む、
方法。
【請求項１８】
請求項１記載の方法であって、前記関連付けられていないデータを使って新しいオブジェクトを計算する段階がさらに：
（ａ）前記関連付けられていないデータ中の特徴を見出す段階と；
（ｂ）前記関連付けられていないデータ中の前記特徴を、オブジェクト・モデルのライブラリ中の特徴と照合する段階と；
（ｃ）オブジェクト・モデルの前記ライブラリ中の前記特徴を使って、オブジェクト・モデルの前記ライブラリ中のオブジェクトを識別する段階とを含む、
方法。
【請求項１９】
請求項１記載の方法であって、前記関連付けられたデータを使って存在しないオブジェクトを検出する段階がさらに：
（ａ）前記3Dシーン・モデルから合成特徴を計算する段階と；
（ｂ）前記関連付けられたデータを前記合成特徴と比較して前記画像中に現れない前記3Dシーン・モデル中のオブジェクトを見出す段階と；
（ｃ）前記画像中に現れない前記3Dシーン・モデル中の前記オブジェクトに対し、該オブジェクトが前記シーンに存在しないかどうかを判別するよう追加的な確認を実行する段階とを含む、
方法。
【請求項２０】
可能な事前3Dシーン・モデルの集合に基づいて、3Dシーン・モデルの集合を計算する方法であって、各3Dシーン・モデルは3Dオブジェクトを含みシーンを表し、当該方法は：
（ａ）前記シーンの画像を取得する段階と；
（ｂ）前記3Dシーン・モデルの集合を、前記可能な事前3Dシーン・モデルの集合に初期化する段階と；
（ｃ）前記3Dシーン・モデルの集合のうちの一つまたは複数と前記取得された画像との間の差を判別することを：
（ｉ）前記画像のデータを前記3Dシーン・モデルのオブジェクトと比較し、結果として関連付けられたデータおよび関連付けられていないデータを与えるステップであって、前記関連付けられたデータは前記比較において前記3Dモデル内の3Dオブジェクトのいずれかと関連付けられた取得された画像データであり、前記関連付けられていないデータは前記比較において前記3Dシーン・モデルのどの3Dオブジェクトとも関連付けられていない取得された画像データである、ステップを行い；
（ｉｉ）前記関連付けられていないデータを使って可能な新しい3Dオブジェクトを計算し；
（ｉｉｉ）前記関連付けられたデータを使って可能な不在3Dオブジェクトを検出することによって行う段階と；
（ｄ）前記3Dシーン・モデルの前記集合のうちの一つまたは複数を、一つまたは複数の可能な新しい3Dオブジェクトを追加する、一つまたは複数の可能な不在3Dオブジェクトを除去するまたはその両方によって修正する段階とを含む、
方法。
【請求項２１】
請求項２０記載の方法であって、前記3Dシーン・モデルの前記集合のうちの一つまたは複数を修正することが、3Dシーン・モデルの尤度を使って、どの可能な新しいオブジェクトが追加され、その可能な不在オブジェクトが除去されるかを選ぶことをさらに含む、方法。
【請求項２２】
請求項２０記載の方法であって、前記3Dシーン・モデルの前記集合のうちの一つまたは複数が、前記3Dシーン・モデルの尤度に基づいて好ましい結果として選択される、方法。
【請求項２３】
命令が記憶されているコンピュータ可読記憶媒体であって、前記命令は、コンピューティング・デバイスに、事前3Dシーン・モデルに基づいて、3Dオブジェクトを含みシーンを表現する3Dシーン・モデルを計算する方法であって：
（ａ）前記シーンの画像を取得する段階と；
（ｂ）前記3Dシーン・モデルを前記事前3Dシーン・モデルに初期化する段階と；
（ｃ）前記3Dシーン・モデルを前記取得された画像と整合するよう修正することを：
（ｉ）前記取得された画像のデータを前記3Dシーン・モデルのオブジェクトと比較し、結果として関連付けられたデータおよび関連付けられていないデータを与えるステップであって、前記関連付けられたデータは前記比較において前記3Dモデル内の3Dオブジェクトのいずれかと関連付けられた取得された画像データであり、前記関連付けられていないデータは前記比較において前記3Dシーン・モデルのどの3Dオブジェクトとも関連付けられていない取得された画像データである、ステップを行い；
（ｉｉ）前記関連付けられていないデータを使って前記事前3Dシーン・モデル内にない新しい3Dオブジェクトを計算し、該新しい3Dオブジェクトを前記3Dシーン・モデルに加え；
（ｉｉｉ）前記関連付けられたデータを使って前記事前3Dシーン・モデル内の、前記シーンの前記取得された画像には不在である3Dオブジェクトを検出して該不在3Dオブジェクトを前記3Dシーン・モデルから除去することによって行う段階とを含む、
方法を実行させるための命令である、
コンピュータ可読記憶媒体。
【請求項２４】
可能な事前3Dシーン・モデルの分布に基づいて、3Dシーン・モデルの分布を計算する方法であって、各3Dシーン・モデルは3Dオブジェクトを含みシーンを表し、当該方法は：
（ａ）前記シーンの画像を取得する段階と；
（ｂ）前記3Dシーン・モデルの分布を、前記可能な事前3Dシーン・モデルの分布に初期化する段階と；
（ｃ）前記3Dシーン・モデルの分布における一つまたは複数の3Dシーン・モデルと前記取得された画像との間の差を判別することを：
（ｉ）前記取得された画像のデータを前記3Dシーン・モデルのオブジェクトと比較し、結果として関連付けられたデータおよび関連付けられていないデータを与えるステップであって、前記関連付けられたデータは前記比較において前記3Dモデル内のオブジェクトのいずれかと関連付けられた取得された画像データであり、前記関連付けられていないデータは前記比較において前記3Dシーン・モデルのどのオブジェクトとも関連付けられていない取得された画像データである、ステップを行い；
（ｉｉ）前記関連付けられていないデータを使って可能な新しい3Dオブジェクトを計算し；
（ｉｉｉ）前記関連付けられたデータを使って可能な不在3Dオブジェクトを検出することによって行う段階と；
（ｄ）前記3Dシーン・モデルの前記分布における3Dシーン・モデルを、一つまたは複数の可能な新しい3Dオブジェクトを追加する、一つまたは複数の可能な不在3Dオブジェクトを除去するまたはその両方によって修正する段階とを含む、
方法。
【請求項２５】
請求項２４記載の方法であって、前記分布における前記3Dシーン・モデルのうちの一つまたは複数を修正することが、3Dシーン・モデルの尤度を使って、どの可能な新しい3Dオブジェクトが追加され、その可能な不在3Dオブジェクトが除去されるかを選ぶことをさらに含む、方法。
【請求項２６】
請求項２４記載の方法であって、前記分布における前記3Dシーン・モデルのうちの一つまたは複数が、前記3Dシーン・モデルの尤度に基づいて好ましい結果として選択される、方法。
【請求項２７】
前記シーンの画像がレンジ画像である、請求項２４記載の方法。
【請求項２８】
前記3Dシーン・モデルのオブジェクトが前面から背面の順に処理される、請求項２４記載の方法。
【請求項２９】
請求項２４記載の方法であって、前記関連付けられたデータを使って存在しないオブジェクトを検出することが：
（ａ）前記3Dシーン・モデルをレンダリングして合成レンダリングを生じる段階と；
（ｂ）前記合成レンダリングを使ってオブジェクトに関連付けられた合成データを計算する段階と；
（ｃ）前記関連付けられたデータを、オブジェクトに関連付けられた前記合成データと比較して、前記画像中に現れない前記3Dシーン・モデル中のオブジェクトを見出す段階と；
（ｄ）前記画像中に現れない前記3Dシーン・モデル中の前記オブジェクトに対し、該オブジェクトが前記シーンに存在していないかどうかを判定するための追加的な確認を実行する段階とを含む、
方法。
【請求項３０】
請求項２４記載の方法であって、計算された前記3Dシーン・モデルを前記画像と整合するよう修正することを行う段階が：
（ａ）前記関連付けられていないデータをデータ・クラスターにクラスター化する段階と；
（ｂ）前記データ・クラスターを使って新しいオブジェクトを計算する段階と；
（ｃ）前記新しいオブジェクトを前記3Dシーン・モデルに追加する段階とをさらに含む、
方法。
【請求項３１】
請求項２４記載の方法であって、前記取得された画像のデータを前記3Dシーン・モデルのオブジェクトと比較することがさらに；
（ａ）前記取得された画像を処理して取得された画像特徴を検出する段階と；
（ｂ）前記3Dシーン・モデル中の各オブジェクトpを処理して、見えるであろうpのモデル特徴を検出する段階と；
（ｃ）前記取得された画像特徴が前記モデル特徴に同じまたは近い位置においてマッチし、前記3Dシーン・モデルの他のいかなるオブジェクトqからのモデル特徴ともよりよいマッチをもたない場合に、前記取得された画像特徴を前記モデル特徴に関連付ける段階と；
（ｄ）オブジェクトpのモデル特徴に関連付けられた前記取得された画像特徴を、オブジェクトpに関連付けられたデータとして取る段階とを含む、
方法。
【請求項３２】
請求項２４記載の方法であって、前記関連付けられていないデータを使って新しいオブジェクトを計算する段階がさらに：
（ａ）前記関連付けられていないデータ中の特徴を見出す段階と；
（ｂ）前記関連付けられていないデータ中の前記特徴を、オブジェクト・モデルのライブラリ中の特徴と照合する段階と；
（ｃ）オブジェクト・モデルの前記ライブラリ中の前記特徴を使って、オブジェクト・モデルの前記ライブラリ中のオブジェクトを識別する段階とを含む、
方法。
【請求項３３】
請求項２４記載の方法であって、前記関連付けられたデータを使って存在しないオブジェクトを検出する段階がさらに：
（ａ）前記3Dシーン・モデルから合成特徴を計算する段階と；
（ｂ）前記関連付けられたデータを前記合成特徴と比較して前記画像中に現れない前記3Dシーン・モデル中のオブジェクトを見出す段階と；
（ｃ）前記画像中に現れない前記3Dシーン・モデル中の前記オブジェクトに対し、該オブジェクトが前記シーンに存在しないかどうかを判別するよう追加的な確認を実行する段階とを含む、
方法。
【請求項３４】
前記シーンの画像がレンジ画像である、請求項１記載の方法。
【請求項３５】
前記3Dシーン・モデルのオブジェクトが前面から背面の順に処理される、請求項１記載の方法。
【請求項３６】
3Dオブジェクトが除去されるのが、すべての3Dオブジェクトが前記3Dシーン・モデルに追加された後でのみである、請求項１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概括的にはコンピュータ・ビジョンに、より詳細にはシーンの画像から3Dシーン・モデルを構築することに関する。
【背景技術】
【０００２】
シーンの画像を得るためにさまざまな技法を使うことができる。画像は、一つまたは複数のスペクトル帯域における強度情報、レンジ情報または両者の組み合わせであってもよい。そのような画像から、シーンの完全な3Dモデルを計算することが有用である。これを必要とするものとして、経路計画（path  planning）、把握（grasping）および他の操作のために完全な3Dシーン・モデルが要求されるロボット応用がある。そのような応用では、シーンのどの部分が他のオブジェクトとは独立して動かすことのできる別個のオブジェクトに対応するかを知ることも有用である。他の応用にも、別個の部分へのセグメント分割を含む、完全な3Dシーン・モデルを得ることに対する同様の要求がある。
【０００３】
シーンの画像から諸部分へのセグメント分割を含む完全な3Dシーン・モデルを計算することは、「3Dシーン・モデルの構築」またはその代わりに「シーンのパース（parsing）」と称される。これを行うには多くの困難な問題がある。その二つを挙げると：（１）画像のどの部分が別個のオブジェクトに対応するかの識別と（２）部分的にまたは完全に隠蔽されるオブジェクトの同一性（identity）を識別または維持することである。
【０００４】
これまでは、かなりの研究にもかかわらず、3Dシーン・モデルを信頼できる形で構築する完全に満足のいく方法はなかった。いくつかの技術文書がこの分野における膨大な先行研究の概説を与えてくれる。そのような概説の一つは非特許文献１である。もう一つは非特許文献２である。もう一つは非特許文献３である。もう一つは非特許文献４である。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許出願第11/452,815号
【特許文献２】米国特許出願第11/159,660号
【非特許文献】
【０００６】
【非特許文献１】Paul  J.  Besl  and  Ramesh  C.  Jain,  "Three-dimensional  object  recognition",  Computing  Surveys,  17(1),  pp  75-145,  1985
【非特許文献２】Roland  T.  Chin  and  Charles  R.  Dyer,  "Model-based  recognition  in  robot  vision",  ACM  Computing  Surveys,  18(1),  pp  67-108,  1986
【非特許文献３】Farshid  Arman  and  J.  K.  Aggarwal,  "Model-based  object  recognition  in  dense-range  images  --  a  review",  ACM  Computing  Surveys,  25(1),  pp  5-43,  1993
【非特許文献４】Richard  J.  Campbell  and  Patrick  J.  Flynn,  "A  survey  of  free-form  object  representation  and  recognition  techniques",  Computer  Vision  and  Image  Understanding,  81(2),  pp  166-210,  2001
【非特許文献５】OpenGL  Programming  Guide,  Addison-Wesley,  2008
【非特許文献６】E.  Trucco  and  A.  Verri,  Introductory  Techniques  for  3-D  Computer  Vision,  Prentice  Hall,  1998
【非特許文献７】Shimon  Ullman,  High-level  Vision,  The  MIT  Press,  1997
【非特許文献８】Ming  C.  Lin,  Stefan  Gottschalk,  "Collision  detection  between  geometric  models:  A  survey,"  Proc.  of  IMA  Conference  on  Mathematics  of  Surfaces,  1998
【非特許文献９】Gino  van  den  Bergen,  Collision  Detection  in  Interactive  3D  Environments,  Elsevier,  2003
【非特許文献１０】Christer  Ericson,  Real  Time  Collision  Detection,  Elsevier,  2005
【非特許文献１１】M.  Goodrich  and  R.  Tamassia,  Data  Structures  and  Algorithms  in  Java,  Wiley,  2005
【非特許文献１２】J.  Marsden  and  A.  Tromba,  Vector  Calculus,  W.  H.  Freeman,  2003
【非特許文献１３】G.  Golub  and  C.  Van  Loan,  Matrix  Computations,  The  Johns  Hopkins  University  Press,  1996
【非特許文献１４】Gilbert  Strang,  Linear  Algebra  and  its  Applications,  Academic  Press,  Inc.  2005
【非特許文献１５】A.  Papoulis  and  S.  Pillai,  Probability,  Random  Variables,  and  Stochastic  Processes,  McGraw  Hill,  2002
【非特許文献１６】Alex  Leonardis,  Ales  Jaklie,  and  Franc  Solina,  Segmentation  and  Recovery  of  Superquadrics,  Kluwer  Academic  Publishers,  Boston,  MA,  2000
【非特許文献１７】A.  Johnson  and  M.  Hebert,  "Efficient  multiple  model  recognition  in  cluttered  3-D  scenes",  Proc.  Computer  Vision  and  Pattern  Recognition  (CVPR'98),  pp.671-678,  1998
【非特許文献１８】David  G.  Lowe,  "Distinctive  image  features  from  scale-invariant  keypoints",  International  Journal  of  Computer  Vision,  Vol.60,  No.2,  pp.91-110,  2004
【非特許文献１９】Mikolajczyk,  K.  Schmid,  C,  "A  Performance  Evaluation  of  Local  Descriptors",  IEEE  Transactions  on  Pattern  Analysis  and  Machine  Intelligence,  Vol.27;  No.10,  pp.1615-1630,  2005
【非特許文献２０】F.  Rothganger  and  Svetlana  Lazebnik  and  Cordelia  Schmid  and  Jean  Ponce,  "Object  modeling  and  recognition  using  local  affine-invariant  image  descriptors  and  multi-view  spatial  constraints",  International  Journal  of  Computer  Vision,  Vol.66,  No.3,  2006
【非特許文献２１】Dorko  and  Schrnid,  "Selection  of  Scale-Invariant  Parts  for  Object  Class  Recognition",  International  Conference  on  Computer  Vision,  (ICCV2003),  pp.634-640,  2003
【非特許文献２２】Burl  et  al.,  "A  probabilistic  approach  to  object  recognition  using  local  photometry  and  global  geometry"  Proc.  European  Conference  on  Computer  Vision  (ECCV)  1998,  pp.628-641
【非特許文献２３】Fergus  et  al.,  "Object  Class  Recognition  by  Unsupervised  Scale-Invariant  Learning",  Computer  Vision  and  Pattern  Recognition,  pp.264-271,  2003
【非特許文献２４】Helmer  and  Lowe,  "Object  Class  Recognition  with  Many  Local  Features",  IEEE  Computer  Vision  and  Pattern  Recognition  Workshops,  2004  (CVPRW'04),  pp.187ff
【非特許文献２５】A.  Doucet,  J.F.G.  de  Freitas,  and  N.J.  Gordon  (ed.),  Sequential  Monte  Carlo  Methods  In  Practice,  Springer,  2001
【発明の概要】
【発明が解決しようとする課題】
【０００７】
従来の研究はいずれも、特にシーンが散らかっており（cluttered）かなりの隠蔽がある場合に、信頼できる形で3Dシーン・モデルを構築するという問題を解決するものではない。よって、これを行うことのできるシステムおよび方法が必要とされている。
【課題を解決するための手段】
【０００８】
本発明は、事前の3Dシーン・モデルに基づいて、3Dオブジェクトを含みシーンを表現する3Dシーン・モデルを構築する方法を提供する。本方法は、シーンの画像を取得する段階と；計算された3Dシーン・モデルを事前3Dシーン・モデルに初期化する段階と；計算された3Dシーン・モデルを前記画像と整合するよう修正する段階とを含む。計算された3Dシーン・モデルを修正する段階は、前記画像のデータを前記3Dシーン・モデルのオブジェクトと比較し、結果として関連するデータおよび関連しないデータを与えるサブ段階と；前記関連しないデータを使って前記3Dシーン・モデル内にない新しいオブジェクトを計算し、該新しいオブジェクトを前記3Dシーン・モデルに加えるサブ段階と；前記関連するデータを使って前記事前3Dシーン・モデル内にある存在しないオブジェクトを検出して該存在しないオブジェクトを前記3Dシーン・モデルから除去するサブ段階からなる。
【０００９】
本発明はまた、さまざまな方法の段階を実行するよう構成された一つまたは複数のコンピュータまたは他の計算装置を有する、3Dシーン・モデルを構築するシステムをも提供する。システムはまた、シーンの画像を取得するための一つまたは複数のカメラおよび事前3Dシーン・モデルおよび／または構築された3Dシーン・モデルを保持するための一つまたは複数のメモリまたは他のデータ記憶手段を含んでいてもよい。
【００１０】
本発明はまた、本稿に記載されるさまざまな方法の段階を実行するためのプログラム命令が具現されているコンピュータ可読媒体をも提供する。
【００１１】
本発明はまた、可能な事前3Dシーン・モデルの集合に基づいて、3Dオブジェクトを含みシーンを表す代替的な3Dシーン・モデルを計算する方法をも提供する。本方法は、シーンの画像を取得する段階と；代替的な3Dシーン・モデルの集合を、可能な事前の3Dシーン・モデルの集合に初期化する段階と；代替的な3Dシーン・モデルの一つまたは複数と前記画像との間の差を判別する段階と；前記代替的な3Dシーン・モデルの一つまたは複数を、一つまたは複数の可能な新しいオブジェクトを追加する、一つまたは複数の可能な不在オブジェクトを除去するまたはその両方によって修正して一つまたは複数の代替的な3Dシーン・モデルを計算する段階とを含む。代替的な3Dシーン・モデルの一つまたは複数と前記画像との間の差を判別する段階は、前記画像のデータを前記3Dシーン・モデルのオブジェクトと比較し、結果として関連するデータおよび関連しないデータを与えるサブ段階と；前記関連しないデータを使って可能な新しいオブジェクトを計算するサブ段階と；前記関連するデータを使って可能な不在オブジェクトを検出するサブ段階をさらに含む。
【図面の簡単な説明】
【００１２】
【図１】本発明のある実施形態に基づく、シーンの画像から3Dシーン・モデルを構築する際に使われる原理動作およびデータ要素を示す図である。
【図２】本発明のある実施形態に基づく、不在オブジェクトを検出する動作を示す図である。
【図３】本発明のある実施形態に基づく、シーンの画像から3Dシーン・モデルを構築する方法の主要なアルゴリズムおよび支援機能の関係を示す図である。
【図４】本発明のある実施形態に基づく、オブジェクト分類器を示す図である。
【図５】本発明のある実施形態に基づく、グラフ掃引機能を示す図である。
【図６】本発明のある実施形態に基づく、SYアルゴリズムを示す図である。
【発明を実施するための形態】
【００１３】
〈序〉
本発明は、画像から3Dシーン・モデルを構築する方法に関する。本発明の革新の一つは、追加的情報を与えるために事前3Dシーン・モデルを使うことである。事前3Dシーン・モデル（prior  3D  scene  model）は多様な仕方で得られる。シーンを時間を追って観察するときのように、以前の観察の結果であることができる。たとえば移動型ロボットが以前に3Dシーン・モデルを構築した位置に戻ってくる場合のように、最後に見た際に世界のその部分がどのように構成されていたかの記録に由来することもできる。あるいはまた、世界の諸部分が典型的にどのように構成されているかについての知識のデータベースに由来することもできる。事前3Dシーン・モデルから新しい3Dシーンへの変化は、動的なシステムと見なされる。
【００１４】
さらに、本発明は、新しい3Dオブジェクトのモデルを構築し、局所的な画像データから事前3Dオブジェクトのモデルを洗練する機能を使う。これは、これらの機能を効率的に使うよう、3Dシーン・モデルによって案内されてもよい。
【００１５】
本発明の方法は、事前3Dシーン・モデル内のオブジェクトがシーンに存在しない場合を検出する：すなわち、画像データと整合しないオブジェクトを見出し、そのようなオブジェクトを追加的な確認試験にかける。これは、事前3Dシーン・モデルにあったオブジェクトが、存在しない、あるいは新しいもしくは移動されたオブジェクトによって隠蔽されているという理由により、画像に現れないことがありうるという事実を取り入れる。
【００１６】
事前3Dシーン・モデル、画像およびシーン変化ダイナミクスのモデルを与えられて、本発明は、観察された画像および事前3Dシーン・モデルに対する蓋然的な変化と整合する新しい3Dシーン・モデルを計算する。
【００１７】
〈概観〉
本発明を次の順序で記述するのが好都合である：（１）定義および記法、（２）本発明の原理、（３）いくつかの例、（４）いくつかの一般的考察、（５）第一の実施形態、（６）さまざまな代替的な実施形態。当業者は、諸実施形態のうちから選ぶことは、部分的には所望される用途に基づいてであろうことを理解するであろう。
【００１８】
〈定義および記法〉
物理的シーンは物理的オブジェクトから構成される。物理的オブジェクトは3Dシーン・モデルにおいて閉じた三次元表面によって表現される。そのような表面は本稿では「3Dオブジェクト・インスタンス」または曖昧さのないところでは「3Dオブジェクト」または「オブジェクト」と称される。3Dオブジェクト・インスタンスは、そのポーズ（pose）・パラメータ（位置および配向）によって記述される。オブジェクトの型に依存して、3Dオブジェクト・インスタンスはさらに、形、大きさなどを記述する補助パラメータによって記述されてもよい。各オブジェクト・インスタンスは一意的な呼称、すなわちその名前をももつ。3Dシーン・モデルは本稿ではGと記される。
【００１９】
本発明のいくつかの実施形態では、次のようなある種の関係した慣例を採用することが好都合である：一意的なオブジェクト、グラウンド平面（ground  plane）がある。グラウンド平面以外のすべてのオブジェクトは、少なくとも一つのオブジェクトが該オブジェクトを支えている。さらに、どのオブジェクトも衝突していない。支持の要求および衝突の不在は、本発明のいくつかの実施形態によって計算される3Dシーン・モデルに対して制約を課すために使うことができる。
【００２０】
画像には、該画像を取得するために使われたセンサーのポーズ（位置および配向）が暗黙的に関連付けられている。さらに、画像はセンサーの視野に依存し、該視野はビュー錐台（view  frustum）によって便利に記述される。ポーズおよびビュー錐台はまとめて「観察者記述」と称され、Γによって記される。曖昧さがない場合には、これを略して「観察者Γ」というのが便利である。
【００２１】
3Dシーン・モデル、観察者Γおよびセンサー種別が与えられると、指定されたポーズおよびビュー錐台から、その型のセンサーによって記録されるであろう画像を計算することができる。この計算は「レンダリング」と称される。あるいは区別を強調するときは、「合成レンダリング（synthetic  rendering）」と称される。ΓからのGのレンダリングから帰結する画像はIrend(G,Γ)と表される。
【００２２】
レンジ（range）・センサーは奥行き情報、すなわち撮像装置からの距離を与える。レンジ・センサーについては、結果として得られるレンダリング画像は時に「合成レンジ画像」と称される。この場合、レンダリングは、計算効率のよいハードウェアZバッファを使って実行できる。あるいはまた、レンダリングはソフトウェアによって実行されることもできる。ΓからのGの合成レンジ画像はR(G,Γ)と表される。この工程は「レンジ・レンダリング（range  rendering）」と称される。
【００２３】
カラー・センサーについては、3Dグラフィクスにおいてポピュラーな「写真のようにリアルなレンダリング（photo-realistic  rendering）」技法を使用してもよい。この分野は膨大な文献がある。参考書である非特許文献５はそのような技法の現在の記述である。
【００２４】
レンダリングの概念は、3Dシーン・モデルから画像が何らかの仕方で記録されその後処理されたとしたら得られるであろうものを計算することと一般化されてもよい。その一例は、「特徴ベースのレンダリング（feature-based  rendering）」である。各オブジェクトは、計算され、該オブジェクトと一緒に記憶される特徴をもつ。特徴ベースのレンダリングは、それらの特徴が3Dシーン・モデルにおいて観察者に対してどのように見えるかを計算する。どの特徴が見えるかを判別するために隠蔽が使われるが、フィーチャーの見え方は投影または他の何らかの技法によって計算される。
【００２５】
よって、「レンダリング」または「合成レンダリング」を、適切な任意のレベルにおいて3Dシーン・モデルの画像において観察者Γから見えると期待される情報を計算する過程と記述するのに使うことが便利である。「レンダリング」の個別的な例は、レンジ・レンダリング、写真のようにリアルなレンダリングおよび特徴ベースのレンダリングである。
【００２６】
物理的なシーンが3Dシーン・モデルGによって正しく記述されており、観察者Γから3Dシーン・モデルがレンダリングされ、結果として合成レンダリングされた画像を与え、観察された画像が同じ観察者位置から撮影されるとする。すると、レンダリングされた画像は、レンダラーにおけるモデリング誤差と物理的センサーにおけるノイズ誤差を除いて観察された画像と同一になるべきである。
【００２７】
3Dシーン・モデル内の何らかのオブジェクトpを考える。後述するように、本発明は画像データを3Dシーン・モデル内のオブジェクトと関連付ける。Ipobsをpに関連付けられたデータとする。レンダリングされた画像の、pに対応する部分を考え、これをIrend(G,Γ,p)と表す。これは、pが物理的なシーンにおいてそのポーズにあったとした場合にpに「関連付けられている」と期待されるであろう画像データを表す。本発明は、IpobsとIrend(G,Γ,p)との間の食い違いを使って、不在オブジェクトまたは移動したオブジェクトを検出する。
【００２８】
本発明はまた、どのオブジェクトにも関連付けられていないデータの検出もする。この「関連付けられていない」データは、シーン内の新しいオブジェクトを検出する、あるいは以前に存在していたがポーズを変えたオブジェクトを検出するために使われる。
【００２９】
事前3Dシーン・モデルG-、観察者Γおよびセンサー検知された画像Iobsが与えられると、本発明は新しい3Dシーン・モデルG+を計算する。ある種の用途では、G+内のオブジェクトを記述する追加的な情報を返すことが有用である。たとえば、オブジェクトを「検証不能」と指定することが有用であることがありうる。これは、そのオブジェクトがG-内にあり、たとえばΓから見たときにG+において完全に隠蔽されているためにそのオブジェクトに矛盾する画像データがないのでG+内に存在しているということを意味する。ロボット・マニピュレータを使う用途は検証不能のオブジェクトを特別に扱ってもよい。
【００３０】
処理過程において、3Dシーン・モデルに関係はするが補助的である他の情報を維持することができることも有用である。そのような追加的情報で増強された3Dシーン・モデルは「増強された3Dシーン・モデル」と称される。
【００３１】
センサー検知された画像は一組の離散的な位置を有している。これらはl∈Lによって表される。位置lにおける観察された画像の値はIlobsによって表される。
【００３２】
レンダリングされた画像について、離散的な位置および添え字の同じ集合を使うことが便利である。GがΓからレンダリングされる場合、位置lにおけるレンダリングされた画像の値はIlrend(G,Γ)によって表される。
【００３３】
pを3Dシーン・モデルにおけるオブジェクトとする。3Dシーン・モデルG内でpがΓから見える位置の集合（ビュー錐台内であり、かつ隠蔽されていない）はLp＝L(G,Γ,p)によって表される。pに対応するレンダリングされた画像の部分は{Ilrend(G,Γ):  l∈Lp}である。これがIrend(G,Γ,p)である。
【００３４】
〈本発明の原理〉
事前3Dシーン・モデル、画像およびシーンがどのように変化すると期待されているかのモデルが与えられると、本発明は、観察された画像およびシーンに対するありそうな変化と整合する新しい3Dシーン・モデルを計算する。
【００３５】
概略的には、本発明は図１に示されるように動作する。動作は長方形として示されており、データ要素は楕円として示されている。本方法は事前3Dシーン・モデル１０１および画像１０２を入力として受け、１０３で、計算された3Dシーン・モデル１０４を事前3Dシーン・モデルに初期化し、次いで、次のように逐次反復的に、計算された3Dシーン・モデルを修正する。１０５で、画像のデータが計算された3Dシーン・モデルのオブジェクトと比較され、結果として関連付けられたデータ１０６と関連付けられていないデータ１０７を与える。関連付けられていないデータから、１０８で、新しいオブジェクトが計算され、計算された3Dシーン・モデルに加えられる。関連付けられたデータを使って、１０９で、不在オブジェクトが検出され、これらの不在オブジェクトが計算された3Dシーン・モデルから除去される。計算１０５、１０８および１０９のそれぞれにおいて、画像データおよび現在の計算された3Dシーン・モデル１０４の両方が使用され、よって3Dシーンの整合性が維持される。
【００３６】
次の詳細レベルでは、図１におけるステップ１０９の不在オブジェクトの検出が、図２に示されるように実行される。現在の3Dシーン・モデルGの各オブジェクトpについて、ステップ２０１において、合成レンダリングを使って合成の関連付けられたデータIrend(G,Γ,p)が計算される；これは、pが指定されたとおりに存在しており、Gの残りも正しかったとした場合に見えると期待されるデータ２０２である。画像からの関連付けられたデータは、ステップ２０３で、合成レンダリングからの関連付けられたデータと比較される。両者が整合しない場合、２０４において、pはデータによって「検証されていない」と考えられる。すなわち、オブジェクトpは画像中でその以前のポーズにおいて現れていない。これは、（ｉ）pが事前3Dシーン・モデルにおけるそのポーズから実際に不在である、あるいは（ｉｉ）pが物理的なシーンに加えられたまたは物理的なシーンにおいて移動された、だが現在の3Dシーン・モデルGにまだ組み込まれていないオブジェクト（単数または複数）qによって隠蔽されているためでありうる。よって、pはステップ２０５において追加的な確認にかけられる。そのようなオブジェクトqがないと判定される場合、第二のケースは消去でき、２０６において、オブジェクトは事前3Dシーン・モデルにおけるそのポーズに存在しないと確認される。そのようなオブジェクトは、他所に見出される新しいオブジェクトと同定されるか、本当に不在であるとして計算された3Dシーン・モデルから除去される。オブジェクトpがこの追加的確認に不合格になると、それは２０７において検証不能とラベル付けされる。その存在も不在も画像からは決定できないからである。そのオブジェクトは「検証不能」ラベルをもって、3Dシーン・モデル中に残る。
【００３７】
そのような隠蔽するまたは移動されたオブジェクト（単数または複数）qがないことが判定できるさまざまな方法がある。「第一の実施形態」は一つの技法を使う。これはデータに対して複数回のパスを行う；最初にデータによって検証されないオブジェクトを見出すとき、オブジェクトは特別な状態に置かれ、すべての新しいオブジェクトを見出してシーンに追加し、すべてのオブジェクトのポーズを調整してしまうまで処理が続けられる。その後、pは隠蔽されているか、事前3Dシーン・モデルにおけるそのポーズにないかが知られる。「代替的な実施形態」は他の技法を記述する。一つの代替技法は、3Dシーン・モデルおよび新しい画像データを前から後の順に処理して、隠蔽されるオブジェクトを処理する前に新しい隠蔽するオブジェクトを見出そうとすることである。
【００３８】
より一般には、計算された3Dシーン・モデルを修正する逐次反復プロセスは、修正を行う順序および画像データをどのようにしてオブジェクトと解釈するかについての選択を行う。これは、可能な修正にわたって探索し、可能性の高い3Dシーン・モデルを見出す問題と見なすことができる。探索には多くの方法があり、それぞれに対して多くの変形がある。いくつかの探索技法は「代替的な実施形態」において記述される。
【００３９】
〈いくつかの例〉
典型的な実施形態によって計算された結果を示すいくつかの例によって、本発明の有用性が例解される。
【００４０】
オブジェクトp1をもつシーンがあるとする。その後、オブジェクトpfがp1の前に置かれてp1を撮像装置からの直接観察から隠蔽する。次いで、シーンの画像が取得される。持続性は、p1が、たとえば画像のどこにも現れていなくても、もともとあった場所に留まったことを示唆し、この持続性は動的モデルにおいて表される。本発明は、隠蔽されたオブジェクトが存在したままであり「検証不能」と指定される、新しい3Dシーン・モデルを計算する。「検証不能（Unverifiable）」とは、画像データがそのオブジェクトの存在を確証もせず、そのオブジェクトの存在に矛盾もしないことを意味する。事前3Dシーン・モデルを使うことにより、本方法は、隠された状態を、可能性としてはそのオブジェクトが観察できない長い期間にわたって、保持することができる。
【００４１】
直立円柱pcをもつシーンがあるとする。その後、同じ半径および視覚的外観をもつ第二の円柱pdがその上に置かれる。pcとpdが一つに融合されたものを示す画像が取得される。持続性は、pcがもともとあった場所に留まっており、新しいオブジェクトpdがシーンに加えられていることを示唆する。本発明は、相異なるオブジェクトpcおよびpdをもつ3Dシーン・モデルを計算する。事前3Dシーン・モデルを使うことにより、本方法は、たとえ画像データが十分な情報を与えなくても、シーンをセグメント分割することを許容する。このようにして、複雑なシーンが、オブジェクトのセグメント分けを保持したまま、逐次的に構築できる。
【００４２】
斜円柱pcをもつシーンがあるとする。その後、オブジェクトpfがpcの前に置かれて中央部を隠蔽する。画像は、前景のpfおよびその背後の二つの円柱セグメントを示す。持続性は、それら二つの円柱セグメントが円柱pcの両端であることを示唆する。本発明は、pcがもともとあった場所にありpfがその前にある、新しい3Dシーン・モデルを計算する。事前3Dシーン・モデルを使うことにより、本方法は、二つの画像セグメントを共通の3Dオブジェクトに割り当てることができる。
【００４３】
オブジェクトpfをもつシーンがあるとする。その後、pfは新しいポーズに移される。画像は、pfと整合するがポーズが変化しているデータを示す。持続性は、pfが動いたことを示唆し、この持続性は動的モデルにおいて表される。本発明は、オブジェクトpfが新しいポーズに移された新しい3Dシーン・モデルを計算する。事前3Dシーン・モデルおよび動的モデルを使うことにより、本方法は時間がたってもオブジェクトの同一性を維持することができる。
【００４４】
それぞれのケースにおいて、画像と整合する代替的な複数の3Dシーン・モデルがある。第一のケースでは、オブジェクトpcが不在であることがありうる。第四のケースでは、オブジェクトpfが除去され、同様のオブジェクトpFが追加されている可能性がある。それぞれのケースにおいて、事前3Dシーン・モデルおよびシーン変化のダイナミクスのモデルにより、該代替の可能性は低くなる。
【００４５】
〈オブジェクト・モデル〉
3Dシーン・モデルにおけるオブジェクトのインスタンスはさまざまな型でありうる。一つの型はパラメータ化された形状モデル、たとえば球、円柱、直方体または超二次曲面（superquadric）である。第二の型は、オブジェクト・モデルのライブラリ中のオブジェクト・モデルに一致する任意形状のオブジェクト・インスタンスである。この場合、ライブラリ中の各モデルは特定のオブジェクトを記述する。そのようなライブラリ中に見出されるオブジェクト・インスタンスを認識することは、「オブジェクト認識」と称される。非特許文献６の第１０章参照。また、非特許文献７参照。第三の型は、クラス・モデルのライブラリ中のクラス・モデルに一致する任意形状のオブジェクト・インスタンスである。この場合、ライブラリ中の各モデルは関係するオブジェクト、たとえば椅子、トラック、自動車、納屋などのクラスを記述する。そのようなクラス・モデルは時に「クラス・プロトタイプ」と呼ばれる。さまざまな実施形態において、本発明は、後述するように、これらの各型のオブジェクト・インスタンスに適用できる。
【００４６】
〈共通の計算上の問題〉
ある種の計算上の問題はいくつかの実施形態に共通である。
【００４７】
一つは可視性の計算である。この計算において、ビュー錐台の奥の限界がグラウンド平面以外の3Dシーン・モデル内のどのオブジェクトよりも向こうにあるよう、Γのビュー錐台を選ぶことが好都合である。Rfarを、ポーズΓの原点からビュー錐台の奥の限界（far  extent）までの距離とする。pをグラウンド平面以外の3Dシーン・モデル中のオブジェクトとする。他のオブジェクトがないとした場合にpが見えるであろう位置の集合をKpで表す。これは次のように計算されうる。pだけからなる3Dシーン・モデルの合成レンジ・マップが観察者Γから計算される；これはR(p,Γ)によって表される。すると、Kpは
Kp＝｛l∈L:  Rl(p,Γ)＜Rfar｝      (1)
として計算される。Kpの大きさはNpによって表される。これは、3Dシーン・モデル内に他のオブジェクトがなかった場合にΓからpが見えるであろう位置の数である。
【００４８】
もう一つの計算上の問題は、Lp、つまり3Dシーン・モデルGにおいてΓからpが見える位置の集合である。これは次のようになされてもよい。ΓからのGの合成レンジ・マップが計算される；これはR(G,Γ)によって表される。LpはΓからpを隠蔽する他のオブジェクトがない位置の集合である。すなわち、
Lp＝｛l∈Kp:  Rl(p,Γ)≦Rl(G,Γ)｝      (2)
Lpの大きさはnpによって表される。これは、3Dシーン・モデルにおいてpが見える位置の数である。明らかに、Lp⊆Kpであり、np≦Npである。np＝Npであれば、そのオブジェクトは完全に見えると言われる。
【００４９】
これらの可視性計算はシーン・モデルGおよび観察者Γの属性であることを注意しておく；画像を取得するために使われるセンサーの型とは独立である。
【００５０】
個別的な諸実施形態は、個別的な必要性のためにLpの定義を修正してもよい。たとえば、ある実施形態は、オブジェクトを、可視と考えられるべきではないという意味で「暫定的（Ephemeral）」とマークしてもよい。Lpを計算するとき、暫定的なオブジェクトは可視な位置をもたず、他のオブジェクトを隠蔽しない。
【００５１】
もう一つの計算上の問題は、本発明のある種の実施形態において幾何学的制約条件を計算することである。そのような実施形態では、3Dシーン・モデル中のオブジェクトは交わってはならない。すなわち、計算されたポーズおよびオブジェクト・パラメータがこのことと整合しなければならない。さらに、区別されるグラウンド平面を除いてすべてのオブジェクトは支持されなければならない。すなわち、下にある少なくとも一つのオブジェクトと接触していなければならない。衝突検出はよく研究されているトピックであり、膨大な技術文献がある。概観論文として、非特許文献８がある。この主題に関する書籍としては、非特許文献９、１０がある。
【００５２】
本発明のさまざまな実施形態において、標準的な衝突検出技法が、
（１）オブジェクトが衝突していないことを検証する、
（２）一つのオブジェクトを別のオブジェクトとの衝突から外す変位を計算する、
（３）あるオブジェクトを別のオブジェクトと接触させる変位を計算する、
ために使われる。
【実施例１】
【００５３】
〈第一の実施形態〉
〈概観〉
第一の実施形態では、のちに詳述する、本稿でSYアルゴリズムと称される方法によって探索が実行される。これは、3Dシーン・モデルの何回かの掃引を行い、各掃引が特定のクラスの決定を行うマルチパス・アルゴリズムである。SYアルゴリズムはさまざまな実施形態をもち、そのそれぞれがさまざまな種類の画像データおよびさまざまな種類のオブジェクト・モデルに適用できる。
【００５４】
第一の実施形態では、画像はレンジ画像であり、オブジェクト・モデルは基本立体：球、円柱および直方体である。これらは一般クラス・モデルであり、新しいオブジェクト・インスタンスを計算する関数が画像データからポーズおよびクラス・パラメータを決定する。
【００５５】
第一の実施形態では、3Dシーン・モデルは3Dオブジェクト・モデルおよびオブジェクトの支持関係を表すグラフ構造からなる。3Dシーン・モデルは、オブジェクト・モデルが衝突していることを許容しない。すべての3Dオブジェクトは、キャラクタ・ストリングとして表現される一意的な名称をもつ。
【００５６】
増強された3Dシーン・モデルは各オブジェクト・インスタンスについての二つの情報を担持する：
（１）そのオブジェクトの分類状態を示す「ラベル」。
（２）後述するようにそのオブジェクトがある種の計算に参加すべきかどうかを示す「マーキング」。オブジェクトが参加すべきでない場合、そのオブジェクトは暫定的とマークされると言われる。それ以外の場合には、実質的（Substantial）とマークされると言われる。
【００５７】
この第一の実施形態を次の順序で記述するのが好都合である：（１）SYアルゴリズムによって使用されるデータ依存関数の抽象的な説明、（２）オブジェクト分類器機能、（３）グラフ掃引機能、（４）SYアルゴリズム本体、（５）レンジ・データおよび基本立体に固有な考察、（６）幾何学的関数。
【００５８】
図３は、これらのコンポーネントの間の関係を示している。SYアルゴリズム３０１が主アルゴリズムである。これはグラフ掃引関数３０２を呼び出し、これはオブジェクト分類器３０３を呼び出し、これがさまざまなデータ依存関数３０４を呼び出す。SYアルゴリズムおよびグラフ掃引関数からデータ依存関数への直接呼び出しもある。また、SYアルゴリズムは幾何学的関数３０５を呼び出す。
【００５９】
〈動的モデル〉
第一の実施形態では、動的モデルはオブジェクトがシーンに追加され、シーンから除去され、あるいはシーン内に異なるポーズで留まることを許容する。ポーズの変化が大きければ、これが異なるポーズの同じオブジェクトであるのか、全く新しいオブジェクトであるのかを判定するのが難しいことがありうる。動的モデルは、3Dシーン・モデルが時間とともにどのように変化するかについて、次の想定をする：
オブジェクト同一性：オブジェクトB1が事前3Dシーン・モデルに存在しているとする。B1が画像に見出されず、似たような外観の新しいオブジェクトB2が画像中に見出されるとする。その場合、B2はB1と同じオブジェクトであると解釈され、計算された3Dシーン・モデルにおいてそのように同定される。
【００６０】
この想定を、第一の実施形態の動作における二つの異なる場所で実装することが好都合である：
（１）同じ大きさおよび形状の二つのオブジェクトが事前3Dシーン・モデルと計算されたシーン・モデルにおいて重なっている場合、両者は互いに同一視される。
（２）計算された3Dシーン・モデルにおいて不在であると検出されるオブジェクトと同じ大きさおよび形状の新しいオブジェクトが計算された3Dシーン・モデルにおいて検出された場合、新しいオブジェクトと不在オブジェクトは互いに同一視される。
【００６１】
第一のものは第二のものの特殊ケースであるが、これを抜き出すことによりある種の計算上の効率性が得られる。
【００６２】
〈データ依存関数〉
SYアルゴリズムは、下記のデータ依存関数が生成されることのできる任意の画像種別に適用できる。
【００６３】
「十分可視（Sufficiently  Visible）」。3Dシーン・モデル、区別されるオブジェクトおよび観察者Γが与えられたときに、この関数は、当該オブジェクトが存在するか不在であるかを決定するために、当該オブジェクトの十分な部分が観察者から見えるかどうかを決定する。解析は、当該オブジェクトの、暫定的とマークされていない他のオブジェクトによる隠蔽およびビュー錐台によるクリッピングならびに画像種別に依存する他の事情を考慮する。たとえば、オブジェクトが完全に隠蔽される場合、決定はできず、関数は偽（false）を返す。
【００６４】
「データ関連付け（Data  Association）」。これは図１のステップ１０５に関係する。3Dシーン・モデルおよび観察される画像が与えられたとき、この関数は画像データを3Dシーン・モデルのオブジェクトと比較し、画像のデータをオブジェクトに関連付け、関連付けの品質の指標をも計算する。
【００６５】
「オブジェクト存在試験（Object  Presence  Test）」。これは図２のステップ２０３に関係する。オブジェクト、該オブジェクトに関連付けられたデータおよび3Dシーン・モデルが与えられたとき、この関数は、当該オブジェクトが前記データから、3Dシーン・モデル中のそのポーズで存在していると検証できるかどうかを決定する。もしそうでなければ、そのオブジェクトは画像中にその以前のポーズで現れていない。
【００６６】
「検出およびクラスター化（Detect  and  Cluster）」。観察されたデータを与えられて、この関数は3Dシーン・モデルのオブジェクトと関連付けられることのできないデータを位置特定し、関連付けられていないデータのクラスターを生成し、それらのクラスターを返す。
【００６７】
「新オブジェクト計算（Compute  New  Objects）」。これは図１のステップ１０８に関係する。観察されたデータおよび提案される支持関係を与えられると、この関数は前記データに対応するオブジェクト・インスタンスを計算する。この関数はオブジェクトのポーズを計算し、パラメトリック・モデルの場合、大きさまたは形状のようなオブジェクトについてのパラメトリック情報をも計算する。この関数はまた、結果として得られるモデルの品質指標をも計算する。この関数は、十分な品質のオブジェクト・インスタンスを計算できない場合には、失敗を報告する。
【００６８】
「データ・クラスターのための支持（Support  for  Data  Cluster）」。観察されたデータおよび3Dシーン・モデルを与えられると、この関数は、前記データから計算されるモデルについての可能な支持オブジェクトの集合を計算する。
【００６９】
「支持をもつモデル（Model  with  Support）」。観察されたデータおよび3Dシーン・モデルを与えられると、この関数は、3Dシーン・モデルからの支持関係を考慮に入れつつ、新しいオブジェクトを計算する。この関数は、上述した関数「データ・クラスターのための支持」および「新オブジェクト計算」を使う。
【００７０】
「既存オブジェクト調整（Adjust  Existing  Object）」。既存のオブジェクト・インスタンス、当該オブジェクトに関連付けられた観察されたデータおよび当該オブジェクトについての支持関係が与えられると、この関数は、当該オブジェクトについての更新されたポーズおよび可能性としては他のオブジェクト・パラメータを計算する。
【００７１】
「オブジェクト同一視（Identify  Objects）」。二つのオブジェクト・インスタンスと第二のオブジェクト・インスタンスを含む3Dシーン・モデルとを与えられると、この関数は、第二のオブジェクト・インスタンスが第一のオブジェクトを新しいポーズに動かす結果としてもっともらしく解釈できる場合に真を返す。確からしさの指標も返してもよい。
【００７２】
〈オブジェクト分類器〉
図３のオブジェクト分類器３０３は、オブジェクト・インスタンスの状態についてのローカルな決定をする。可能な分類状態は：
１．「新しいオブジェクト」
２．「新しいポーズで存在」
３．「同じポーズで存在」
４．「更新されたポーズで存在」
５．「未検証」
６．「検証不能」
７．「未処理」
オブジェクトがこれらの状態の一つに分類されるとき、オブジェクトは分類をもって「ラベル付け」されていると言われる。
【００７３】
オブジェクト分類器３０３は、のちに説明するように、増強された3Dシーン・モデルに対して作用し、その動作を制御するポーズ調整フラグを取る。オブジェクト分類器は各オブジェクトおよびそのオブジェクトに関連付けられたデータを考慮する。オブジェクトのラベルを確証するか、あるいは図４に示されるステップを介して新しいラベルを割り当てる。
【００７４】
入力４０１はラベルをもつオブジェクトを含む。ステップ４０２で、そのラベルが試験される。そのラベルが「新しいオブジェクト」または「新しいポーズ」である場合、オブジェクトに関連付けられたデータを使って「オブジェクト存在」試験４０３が呼び出される。「オブジェクト存在」試験に合格するオブジェクトは４０４でその以前のラベルを保持し；「オブジェクト存在」試験に不合格となるオブジェクトは４０５で「未検証」とラベル付けされる。すなわち、オブジェクトは画像中にその以前のポーズにおいて現れていないということである。
【００７５】
ラベルが「新しいオブジェクト」でも「新しいポーズ」でもなければ、４０６で「十分可視」試験が呼び出される。「十分可視」試験に不合格となるオブジェクトは４０７で「検証不能」とラベル付けされる。「十分可視」試験に合格するオブジェクトは４０８で「オブジェクト存在」試験にかけられる。「オブジェクト存在」試験に不合格となるオブジェクトは、４０９で「未検証」とラベル付けされ、図２における２０４における結果を与える。そのオブジェクトは画像中にその以前のポーズで現れていない。
【００７６】
オブジェクトが「オブジェクト存在」試験に合格する場合、ステップ４１０で次のようにさらなる試験が実行される：ポーズ調整フラグが真でありかつオブジェクトが完全に可視であれば、「既存オブジェクト調整」関数が、そのオブジェクトに関連付けられたデータおよび3Dシーン・モデルにおけるその支持関係をもって呼び出される。その関数が成功すると、そのオブジェクトのポーズが調整され、そのオブジェクトは４１１で「更新されたポーズ」とラベル付けされる。
【００７７】
ポーズ調整フラグが偽であるか、そのオブジェクトが完全に可視ではない、あるいは「既存オブジェクト調整」関数が失敗する場合には、ステップ４１２でオブジェクト・ラベルが試験される。オブジェクト・ラベルが「更新されたポーズ」であれば、４１３でそのラベルは保持され、そうでない場合には、オブジェクトは４１４で「同じポーズ」とラベル付けされる。
【００７８】
〈グラフ掃引（Graph  Sweep）〉
図３の「グラフ掃引」関数３０２は、増強された3Dシーン・モデルにおいて実質的とマークされたすべてのオブジェクト・インスタンスと、画像から得られたデータと、その動作を制御するフラグに対して作用する。グラフ掃引関数は三つの中心的な活動を実行する：（１）増強された3Dシーン・モデルにおいて「実質的」とマークされたオブジェクト・インスタンスにデータを関連付ける、（２）増強された3Dシーン・モデルにおいて「実質的」とマークされたオブジェクトにラベル付けする、（３）現在の3Dシーン・モデルにおいてオブジェクトと関連付けられていないデータをクラスター化する。
【００７９】
「グラフ掃引」関数の動作は図５に概略的に示されている。
（１）「実質的」とマークされた各オブジェクトについて、ステップ５０１で「データ関連付け」関数を呼び出し、関連付けられたデータを増強された3Dシーン・モデルに記憶する。
（２）「実質的」とマークされた各オブジェクトおよびその関連付けられたデータについて、ステップ５０２で「オブジェクト分類器」を呼び出し、そのオブジェクトにラベル付けし直す。
（３）ステップ５０３で、「未検証」とラベル付けされた増強された3Dシーン・モデル内のすべてのオブジェクトのリストを構築する。このリストは、「未検証オブジェクト・リスト」と称され、５０６に示されている。
（４）ステップ５０４で、「検出およびクラスター化」関数を呼び出し、「データ関連付け」関数によってオブジェクトに関連付けられたなかったデータを見出し、クラスター化する。
（５）ステップ５０５でこれらのクラスターのリストを構築する。このリストは「データ・クラスター・リスト」５０７と称される。
【００８０】
「未検証オブジェクト・リスト」、「データ・クラスター・リスト」および更新された増強された3Dシーン・モデルがまとまって、「グラフ掃引」関数の結果となる。「グラフ掃引」の終わりに、「未検証オブジェクト・リスト」が「実質的」とマークされているオブジェクトを含まず、「データ・クラスター・リスト」が空である場合、増強された3Dシーン・モデルは「確認済み」と言われる。
【００８１】
〈SYアルゴリズム本体〉
SYアルゴリズムはグラフ掃引関数を使って、多段階式に諸クラスの決定をなす。各段階またはフェーズの間に、完全な3Dシーン・モデルが評価され、その結果に基づいて、3Dシーン・モデルが修正される。
【００８２】
本アルゴリズムは動作する際に三つの項目を維持する：
１．「現在の3Dシーン・モデル」と称される増強された3Dシーン・モデル。
２．現在の3Dシーン・モデルに対する最も最近のグラフ掃引からの未検証オブジェクト・リスト。
３．現在の3Dシーン・モデルに対する最も最近のグラフ掃引からのデータ・クラスター・リスト。
【００８３】
最初、SYアルゴリズムは事前3Dシーン・モデルを受け、各オブジェクト・インスタンスに「未処理」とラベル付けし、各オブジェクト・インスタンスを「実質的」とマークすることによって増強された（augmented）3Dシーン・モデルを生成する。この増強された3Dシーン・モデルが現在の3Dシーン・モデルとして取られる。
【００８４】
SYアルゴリズムの主要なステップが図６に示されている。ステップ６０１は現在の3Dシーン・モデルの、曖昧さのない諸部分を有効確認する；これが全画像データおよび全オブジェクトをカバーすれば、制御はステップ６０６に進む。ステップ６０２は「未検証」とラベル付けされたオブジェクトを処理する；ある種の試験を合格するものは「暫定的」とマークされる。全画像データおよび全オブジェクトがカバーされたら、制御はステップ６０６に進む。ステップ６０３はポーズが変化したがレンダリングが古いポーズにおけるレンダリングとだいたい重なっているオブジェクトを扱う；画像データから新しいポーズを計算する。ここでもまた、全画像データおよび全オブジェクトがカバーされたら、制御はステップ６０６に進む。ステップ６０４は、関連付けされていないデータのクラスターを考え、そこから図１のステップ１０８に示されているように、新しいオブジェクトを計算し、それらの新しいオブジェクトを現在の3Dシーン・モデルに追加する。全画像データおよび全オブジェクトがカバーされたら、制御はステップ６０６に進む。ステップ６０５は、「未検証」とマークされたオブジェクトを新しいオブジェクトと一致する場合に同一視することによって、動いたオブジェクトを見出そうとし、ステップ６０６に進む。ステップ６０６は、「未検証」とマークされたオブジェクトを現在の3Dシーン・モデルから除去する。
【００８５】
より詳しくは、これら六つのステップは次のようになる：
ステップ６０１（「存在オブジェクト」）：このステップは、現在の3Dシーン・モデルの、曖昧さのない部分を有効確認する。ポーズ調整が許容されないようにポーズ調整フラグをセットして、現在の3Dシーン・モデルに対してグラフ掃引が実行される。現在の3Dシーン・モデルが「確認済み」となったら、アルゴリズムは直接ステップ６０６に移る。現在の3Dシーン・モデルが「確認済み」でなければ、ポーズ調整が許容されるようポーズ調整フラグをセットして、現在の3Dシーン・モデルに対して第二のグラフ掃引が実行される。このグラフ掃引において現在の3Dシーン・モデルが「確認済み」となったら、アルゴリズムは直接ステップ６０６に移る。
【００８６】
ステップ６０２（「未検証オブジェクト」）：このステップは、未検証とラベル付けされたオブジェクトを処理する。ある種の試験に合格するオブジェクトは「暫定的」とマークされる。（本計算ののちのステップが、これらのオブジェクトの実際の状態を確認するためにさらなる試験にかける。）ステップ６０１のあとに「未検証オブジェクト・リスト」にオブジェクト・インスタンスが現れない場合には、実行はステップ６０３に移る。
【００８７】
ステップ６０１のあとに「未検証オブジェクト・リスト」にオブジェクト・インスタンスが現れる場合には、ステップ６０１後の「未検証オブジェクト・リスト」および「データ・クラスター・リスト」がのちの参照のために記録される。次いで、以下の動作が「未検証オブジェクト・リスト」に現れる各オブジェクト・インスタンスに対して実行される：
１．そのオブジェクト・インスタンスが現在の3Dシーン・モデルにおいて「暫定的」とマークされ、修正された3Dシーン・モデルを生成する。
２．修正された3Dシーン・モデルに対してグラフ掃引が実行される。
３．修正された3Dシーン・モデルに対するグラフ掃引の結果が、ステップ６０１後の現在の3Dシーン・モデルに対するグラフ掃引の結果と比較され、次の条件が満たされるかどうかが調べられる：
（ａ）修正された3Dシーン・モデルから帰結する「データ・クラスター・リスト」に現れるデータ点の数が、現在の3Dシーン・モデルの「データ・クラスター・リスト」に現れるデータ点の数より大きくない。
（ｂ）修正された3Dシーン・モデルから帰結する「未検証オブジェクト・リスト」上のオブジェクト・インスタンスの数が、現在の3Dシーン・モデルの「未検証オブジェクト・リスト」上に現れるオブジェクトの数より大きくない。
４．そのオブジェクト・インスタンスがこれら二つの試験に合格したら、「暫定的」とマークされるべきオブジェクトのリストに加えられる。
【００８８】
ステップ６０１後の「オブジェクト不在リスト」に現れるすべてのオブジェクト・インスタンスが処理されたのち、「暫定的」とマークされるべきオブジェクトのリストに現れるどのオブジェクトも、現在の3Dシーン・モデルにおいて「暫定的」とマークすることによって、特別な状態にされる。結果は、修正された3Dシーン・モデルである。この修正された3Dシーン・モデルが現在の3Dシーン・モデルとなる。
【００８９】
現在の3Dシーン・モデルに対してグラフ掃引が実行される。現在の3Dシーン・モデルが「確認済み」となったら、アルゴリズムは直接ステップ６０６に移る。
【００９０】
現在の3Dシーン・モデルが「確認済み」でない場合には、実行はステップ６０３に進む。
【００９１】
ステップ６０３（「摂動されたオブジェクト」）：ステップ６０３は、オブジェクト・インスタンスのポーズが変わったが、いまだ古いポーズとほぼ重なっている場合を扱う。
【００９２】
現在の3Dシーン・モデルについて「未検証オブジェクト・リスト」に現れる、「実質的」とマークされたオブジェクト・インスタンスがない場合には、実行はステップ６０４に移る。
【００９３】
現在の3Dシーン・モデルについて「未検証オブジェクト・リスト」が「実質的」とマークされたオブジェクト・インスタンスを含む場合には、「未検証オブジェクト・リスト」に現れるオブジェクトのリストが新しいリストＣに記録される。次いで、Ｃに現れる、「実質的」とマークされた各オブジェクト・インスタンスpについて、以下のステップが実行される。
【００９４】
１．現在の3Dシーン・モデルに関連付けられたデータが集合Bpとして記録される。現在の3Dシーン・モデルにおいてpを「暫定的」とマークすることによって修正された3Dシーン・モデルが生成される。
【００９５】
２．修正された3Dシーン・モデルに対して「グラフ掃引」が呼び出され、結果として修正された3Dシーン・モデルについての「データ・クラスター・リスト」を与える。
【００９６】
３．修正された3Dシーン・モデルについての「データ・クラスター・リスト」の要素Aが、A∩Bpができるだけ大きくなるように位置特定される。A⊆Bpであれば、このデータ・クラスターは、もともとpに関連付けられていたもの以外のデータ項目は含まない。この場合、修正された3Dシーン・モデルは破棄され、アルゴリズムは、Cに現れる、「実質的」とマークされた次の「未検証」オブジェクト・インスタンスに進む。
【００９７】
４．AがBpの部分集合でない場合、（ａ）データ・クラスターAおよび（ｂ）現在の3Dシーン・モデルにおけるpについての支持するオブジェクト・インスタンスをもって、「新オブジェクト計算」関数が呼び出される。「新オブジェクト計算」が失敗する場合、修正された3Dシーン・モデルは破棄され、アルゴリズムは、Cに現れる、「実質的」とマークされた次の「未検証」オブジェクト・インスタンスに進む。
【００９８】
５．「新オブジェクト計算」が成功する場合、新しいモデルqを呼び出す。pとqが「オブジェクト同一視」試験を満足しない場合、修正された3Dシーン・モデルは破棄され、アルゴリズムは、Cに現れる、「実質的」とマークされた次の未検証オブジェクト・インスタンスに進む。
【００９９】
６．pとqが「オブジェクト同一視」試験を満足する場合、pは、3Dシーン・モデルにおいて、qについて計算されたポーズで現れるよう修正される。オブジェクト・インスタンスpは、「新しいポーズで存在」とラベル付けされ、「実質的」とマークされる。「グラフ掃引」が、今や新しいポーズでのpを含む修正された3Dシーン・モデルに対して呼び出される。
【０１００】
７．新しいポーズでのpを含む修正された3Dシーン・モデルに対するグラフ掃引の結果が四つの条件に関して試験される：１）pは「未検証オブジェクト・リスト」上に現れない；２）「未検証オブジェクト・リスト」はCに現れていなかった以外のメンバーはもたない；３）新しいポーズでのpは、「実質的」とマークされた、3Dシーン・モデル中の他のどのオブジェクト・インスタンスとも衝突していない；および４）新しいポーズでのpを含む修正された3Dシーン・モデルの「データ・クラスター・リスト」は、現在の3Dシーン・モデルの「データ・クラスター・リスト」よりも少ないデータ点を含む。四つすべての条件が満たされる場合、修正された3Dシーン・モデルが現在の3Dシーン・モデルとなる。アルゴリズムは、Cに現れる、「実質的」とマークされた次の「未検証」オブジェクト・インスタンスに進む。
【０１０１】
８．ステップ７の四つの条件のどれかが満たされない場合には、修正された3Dシーン・モデルは破棄され、アルゴリズムは、Cに現れる、「実質的」とマークされた次の「未検証」オブジェクト・インスタンスに進む。
【０１０２】
「実質的」とマークされた、C上のすべてのオブジェクト・インスタンスが処理され終わったら、現在の3Dシーン・モデルについての「データ・クラスター・リスト」中の各クラスターが新しいオブジェクトと考えられる。「データ・クラスター・リスト」にクラスターがない場合、処理はステップ６０６に移り、それ以外の場合には処理はステップ６０４に移る。
【０１０３】
ステップ６０４（「新しいオブジェクト」）：このステップでは、現在の3Dシーン・モデルについての「データ・クラスター・リスト」上のデータ・セグメントがモデル化され、現在の3Dシーン・モデルに加えられる。
【０１０４】
ステップ６０４は、「データ・クラスター・リスト」中の各データ・クラスターに対して次のように作用する。
１．そのデータ・クラスターに対して「支持をもつモデル」関数が呼び出される。この関数が失敗した場合は、このデータ・クラスターに対する処理は打ち切られる。
２．「支持をもつモデル」がモデルを返す場合、そのモデルから新しいオブジェクト・インスタンスが生成される。新しいオブジェクト・インスタンスをその支持と接触させ、他のすべてのオブジェクトとの衝突から外すために必要とされるポーズ変位を計算するために「隣接についての調整（Adjust  for  Adjacent）」関数が呼び出される。
３．許容可能なポーズ変位を、固定されたマージン内であり、オブジェクト・インスタンスを、「未検証」とラベル付けされたまたは「暫定的」とマークされたオブジェクトを除いたすべてのオブジェクトと衝突がないようにするものと定義する。許容可能なポーズ変位がある場合、新しいオブジェクト・インスタンスのポーズが調整され、オブジェクト・インスタンスが現在の3Dシーン・モデルに加えられる。新しいオブジェクト・インスタンスは「新しいオブジェクト」とラベル付けされ、「実質的」とマークされる。
４．許容可能なポーズ変位がない場合、このデータ・クラスターのモデリングは失敗したとみなされ、新しいオブジェクト・インスタンスは破棄される。
【０１０５】
すべてのデータ・クラスターをモデル化したのち、現在の3Dシーン・モデル中の、「暫定的」とマークされたすべてのオブジェクトが「未検証」とラベル付けされ、「実質的」とマークされる。現在の3Dシーン・モデル中のすべての「未検証」オブジェクトに対して「衝突検査」関数が呼び出され、衝突しているオブジェクトは「暫定的」とマークされる。
【０１０６】
現在の3Dシーン・モデルに対して「グラフ掃引」が呼び出される。この掃引の間に計算されたどのデータ・クラスターも見せかけ（spurious）と考えられ、無視される。「未検証オブジェクト・リスト」にオブジェクト・インスタンスがない場合には、実行はステップ６０６に移り、それ以外の場合には実行はステップ６０５に移る。
【０１０７】
グラフ掃引のこの呼び出し前にオブジェクトが「未検証」である場合を考える。図２の２０４参照。このグラフ掃引呼び出しにおいて「十分可視」試験に不合格となる場合、図２の２０５の追加的な確認動作も合格しなかったことになり、「検証不能」２０７とラベル付けされる。
【０１０８】
ステップ６０５（「動かされたオブジェクト」）：Mを「未検証オブジェクト・リスト」とする。Nを、現在の3Dシーン・モデル中で、「新しいオブジェクト」とラベル付けされているすべてのオブジェクト・インスタンスのリストとする。Nの各要素nについて、以下のステップが実行される。
１．Mの各要素mが、「オブジェクト同一視」試験を使って、nと比較される。
２．どの対(m,n)もこの試験に合格しない場合、計算はNの次の要素に進む。
３．Mの単一のメンバーmがオブジェクトnとの上記試験に合格する場合、mはnのポーズを与えられ、mは「新しいポーズ」をもつとラベル付けされ、「実質的」とマークされる。オブジェクトnは現在の3Dシーン・モデルから除去される。オブジェクト・インスタンスmはMから除去され、計算はNの次の要素に進む。
４．Mの二つ以上のメンバーが上記試験に合格する場合、一致するオブジェクト・インスタンスの一つmが任意に選ばれる。選ばれたmはnのポーズを与えられ、mは「新しいポーズ」をもつとラベル付けされ、「実質的」とマークされる。オブジェクトnは現在の3Dシーン・モデルから除去される。オブジェクト・インスタンスmはMから除去され、計算はNの次の要素に進む。
【０１０９】
「新しいオブジェクト」とラベル付けされたすべてのオブジェクト・インスタンスが処理されたのち、現在の3Dシーン・モデルに対してグラフ掃引が呼び出され、実行はステップ６０６に移る。
【０１１０】
ステップ６０６（「オブジェクト除去」）：現在の3Dシーン・モデルにおいて「未検証」とラベル付けされているすべてのオブジェクト・インスタンスが、図２のステップ２０５に示されているように、追加的な確認試験に合格しており、不在として検出される。それらのオブジェクト・インスタンスは現在の3Dシーン・モデルから除去され、結果として最終的な増強された3Dシーン・モデルを与える。
【０１１１】
SYアルゴリズムは、最終的な増強された3Dシーン・モデルを、その計算結果として返し、終了する。
【０１１２】
〈レンジ・データ〉
第一の実施形態では、画像はレンジ・マップである。よって、どの画像位置も奥行き値を含む。同じことだが、各レンジ値は、点t∈R3と考えることもできる。
【０１１３】
レンジ・データという個別的な場合については、唯一の不確定性は奥行き方向にある。レンジ誤差は、既知の分散σ2をもつガウス分布と見せかけの（spurious）値の何らかの割合βをモデル化する一様分布との組み合わせとしてモデル化される。よって、レンジ誤差rは確率密度値：
Pβ(r)＝(1−β)Z(r/σ)＋βU(r;rmin,rmax)      (3)
をもつ。ここで、rminおよびrmaxはシステムのレンジ限界であり、Zは平均0、分散1のガウス密度関数であり、Uは区間[rmin,rmax]上の一様密度関数である。第一の実施形態では、σは、うまく機能するレンジ・センサー・オブジェクトを呈示し、シーン内のオブジェクトにモデルを当てはめ、結果として得られる当てはめの二乗平均平方根誤差を計算することによって計算される。βの値は、典型的なシーンにおけるオブジェクト上で遭遇されると期待される見せかけのデータの割合を説明するよう経験的に選ばれる。
【０１１４】
第一の実施形態では、3Dシーン・モデル中の各オブジェクト・インスタンスは閉じた表面である。そのような各表面は、レンジ点をオブジェクト表面からの符号付き距離にマッピングする、パラメータμをつ符号付きユークリッド距離関数Eと関連付けられる。点t∈R3について、E(μ,t)＜0はtがオブジェクト・インスタンス内にあることを示し、E(μ,t)＞0はtがオブジェクト・インスタンス外にあることを示し、E(μ,t)＝0はオブジェクト・インスタンスの表面を定義する。
【０１１５】
〈「十分可視」〉
「十分可視」試験は、観察者Γから3Dシーン・モデル中のオブジェクト・インスタンスpについて、次のようにして計算される。npを、観察者ΓからのG内におけるpの観察可能な諸位置Lpの大きさとする。Npを、観察者Γからの、同じポーズのpのみを含む3Dシーン・モデルにおけるpの観察可能な位置の数とする。「十分可視」試験は、np＞0.8Npである場合にかつその場合にのみ成功する。
【０１１６】
〈データ関連付け〉
データ関連付けは、「実質的」とマークされたオブジェクト・インスタンスについて計算される。符号付き距離関数E(μp,t)をもつオブジェクト・インスタンスpについて、pに関連付けられたデータ点は、次の二つの条件を満たす点tである。
１）tはpの表面から距離τ以内にある、すなわち|E(μp,t)|≦τ
２）実質的とマークされた、G内にある他のオブジェクト・インスタンスqであって、|E(μq,t)|＜|E(μp,t)|となるものはない。
【０１１７】
第一の実施形態は、これらの演算を二段階で実行する。第一段階では、各位置l∈Lについて、本方法は、G内の「実質的」とマークされているすべてのオブジェクト・インスタンスqについて|E(μp,Rlobs)|≦|E(μq,Rlobs)|となるようなオブジェクトpを計算する。オブジェクトpはアレイMにおいて位置Mlに記憶される。第二段階では、pに関連付けられた画像位置の集合が：
Ap＝｛l∈L:  |Ml＝pかつE(μp,Rlobs)|≦τ｝        (4)
として計算される。第一の実施形態はτ＝3σを使う。ここで、σは式(3)の標準偏差である。データ関連付けの品質は、データ点の、それが関連付けられているオブジェクトまでの距離である。
【０１１８】
符号付き距離関数Eは、球、円柱および直方体の三つの形について定義される。t＝(x,y,z)Tとする。半径r、中心c＝(cx;cy;cz)Tの球については、符号付き距離関数は
ES(c,r;t)＝sqrt((x−cx)2＋(y−cy)2＋(z−cz)2)−r      (5)
高さh、半径r、中心c＝(cx;cy;cz)Tで配向が回転Rによって記述される円柱については、符号付き距離関数は
EC(c,R,h,r;t)＝max(sqrt(x'2＋y'2)−r,  |z'|−h/2)      (6)
ここで、(x',y',z')T＝RT(t−c)である。
【０１１９】
中心cで配向が回転Rによって記述され、寸法がd＝(dx,dy,dz)Tによって記述される直方体については、符号付き距離関数は
EB(c,R,d;t)＝max(|x'|−dx/2,  |y'|−dy/2,  |z'|−dz/2)      (7)
ここで、(x',y',z')T＝RT(t−c)である。
【０１２０】
〈オブジェクト存在試験〉
図２のステップ２０３を参照するに、オブジェクト存在についてオブジェクト・インスタンスpを試験するためには、pに関連付けられる位置の集合Apが計算される。mp＝|Ap|とする。npを、合成レンダリングされた3Dシーン・モデルにおいて可視であるpの画像位置の数とする。すなわち、np＝|Lp|である。計数値npは、その3Dシーン・モデルに基づく関連付けられたデータの期待を与える。「オブジェクト存在」試験は、mp＞0.8npであれば成功する。「オブジェクト存在試験」が失敗する場合、図２の２０４を参照して論じたように、オブジェクトは「未検証」である。
【０１２１】
〈「検出およびクラスター化」〉
レンジ画像Rにおけるレンジ画像位置l∈Lは、l∈ApとなるG内のオブジェクト・インスタンスpがない場合、3Dシーン・モデルに関連付けられていない。Uを、R内のそのような関連付けられていない位置lすべての集合とする。
【０１２２】
Uを解析して、3D連結された表面を位置特定する。二つの位置lおよびmが連結されていると考えられるのは：
１．lおよびmが隣り合う画像座標であり、かつ
２．|Rl−Rm|＜τ
である場合である。画像位置の集合Uが連結されていると言われるのは、U内のすべての画像位置がU内の他の何らかの画像位置に連結されている場合である。二つの分離した位置の集合U1およびU2が連結されていると言われるのは、lとmが連結しているような位置l∈U1およびm∈U2がある場合である。
【０１２３】
すると、Uは、各Uiは連結であり、i≠jであればどのUiもUjとは連結されていないような極大連結成分U1,U2,…,Ukに分割できる。これは、Uの各要素についてノードが作成され、ノードの対が、U内の対応する位置が連結されていればエッジで接続されている無向グラフの極大連結成分を計算することによって実行できる。無向グラフの極大連結成分を計算するためのアルゴリズムは、非特許文献１１のような計算機科学の多くの初等テキストに見出せる。
【０１２４】
「検出およびクラスター化」は、各Uiに含まれる諸位置におけるデータ値のリストDiを形成する。検出およびクラスター化は、リストD1,D2,…,Dkを返す。
【０１２５】
〈モデル分類〉
第一の実施形態によって用いられるオブジェクト・モデルは、球、円柱および直方体である。第一の実施形態は、データをモデル化してこれらのオブジェクト・モデルに分類するために、堅牢な当てはめ〔フィッティング〕関数の集合を使う。当てはめプロセスは、後述するいくつかのケースからなる。各ケースは、データ・モデル化関数によって計算される誤差項を利用する。データ・モデル化関数は、先述した符号付き距離関数と同じ性質をもつ符号付きの「内側−外側」関数Vの形を取るが、点からオブジェクト・インスタンスの表面までのユークリッド距離を計算することは必要とされない。
【０１２６】
〈球についてのモデル当てはめ。制約なし最適化〉
第一の実施形態によって使用される方法を例解するために、点c＝(cx;cy;cz)Tを中心とし、半径rの球を考える。μがこれらのパラメータを表すとする。点t＝(x;y;z)Tが与えられたとき、符号付き内側−外側関数は：
VS(μ;t)＝VS(c,r;t)＝(x−cx)2＋(y−cy)2＋(z−cz)2−r2      (8)
となる。
【０１２７】
{ti}をデータ・クラスターとする。球は、次の目的関数を最適化することによって当てはめされる。
【０１２８】
O(μ)＝ΣiΦ(VS(μ;ti))        (9)
ここで、和は{ti}の添え字について取られ、Φは
Φ(x)＝exp(−x2/(2γ2))        (10)
として定義される。
【０１２９】
この定義はパラメータγに依存しており、γの計算は後述する。
【０１３０】
目的関数Oは二段階で最適化される。
第一に、Oの勾配が計算される。最適時には勾配は0である。
第二に、式の一部がテイラー級数展開を使って線形化される
これらの段階の両方とも非特許文献１２のような初等的なベクトル解析のテキストにおいて一般的に扱われている。
【０１３１】
μに関するOの勾配を取ると、
∇O(μ)＝Σi∇Φ(VS(μ;ti))                (11)
＝Σi∇exp(−VS(μ;ti)2/(2γ2))
＝Σi∇(VS(μ;ti)2)  exp(−VS(μ;ti)2/(2γ2))／(2γ2)
μ*をμについての推定値、Ji＝∇VS(μ*;ti)、wi＝Φ(VS(μ*;ti))とする。VSのテイラー級数展開およびwiの値を式(11)に代入し、結果を0に等しいと置くと、下記が得られる。
【０１３２】
∇O(μ)＝−Σiwi∇（VS(μ*;ti)＋Ji(μ−μ*)）2／(2γ2)      (12)
＝−2Σiwi（JiT（VS(μ*;ti)＋Ji(μ−μ*)））／(2γ2)
＝0
これは線形系であり、μについての更新された解を与えるよう解くことができる。線形連立方程式を解く方法は、非特許文献１３のような行列代数についての初等教科書に記述されている。μについての更新された解は、Jiおよびwiについての新しい値を計算するために使われ、プロセスは繰り返される。
【０１３３】
γの値も各反復工程において次のようにして推定される。パラメータ値μおよびデータ点tiについて、VS(μ,ti)はある値を与える。データ・クラスター中のすべてのレンジ点についてのこれらの値のメジアンmが計算され、γ＝max(σ,1.48m)である。ここで、σは先述したデータ誤差モデルである。
【０１３４】
これらのアルゴリズムは、μの変化が閾値より小さくなるまで逐次反復される。所定の反復回数以内にそのようにならなかった場合には、当てはめアルゴリズムは失敗したと考えられる。第一の実施形態は、閾値10-5を使い、最大反復回数を50に固定する。
【０１３５】
球の半径についての出発点となる推定値は、データ・クラスターについての堅牢な3Dバウンディング・ボックスの最大の寸法の半分として取られる。球の中心についての出発点となる推定値は、前記堅牢な3Dバウンディング・ボックスの中心に取られる。
【０１３６】
堅牢な3Dバウンディング・ボックスは、三つの次元方向のそれぞれにおける最小値および最大値によって記述される。堅牢なバウンディング・ボックスの各次元方向についての値は、その次元方向についてのデータ値をソートし、最も大きいほうおよび最も小さいほうからのある割合の値を破棄し、残りの最小および最大を取ることによって計算される。第一の実施形態で破棄される割合は1%である。
【０１３７】
〈直方体についてのモデル当てはめ〉
直方体は、いかなるレンジ画像においても高々三つの表面が可視であるという事実を利用することによってモデル化される。推定の第一段階は、見える表面すべてに共通する頂点を原点に位置させ、辺を座標軸方向に配向する回転Rおよび位置cを計算することである。この位置では、変換されたデータの成分の一つは、センサー誤差を除いて0になる。よって、目的関数は：
O(R,c)＝ΣiΦ(min(|rix|,|riy|,|riz|))        (13)
となる。ここで、rix,riy,rizはri＝RT(ti−c)のそれぞれx,y,z成分である。
【０１３８】
当てはめ手順は次のように動作する。第一に、事前推定値R-およびc-がデータに適用され、変換されたデータti-＝(R-)T(ti−c-)が生成される。第二に、Rの小角度近似がR'＝(I＋sk(x))として適用される。ここで、skはベクトルxから歪対称（skew  symmetric）行列を生成する。歪対称行列は非特許文献１４のような初等線形代数についての多くのテキストで論じられている。これを用いると、ri＝(I+sk(x))T(ti-−Δc)となる。最後に、m(i)を絶対値が最小のti-の成分とする。新しい目的関数は
O(x,Δc)＝ΣiΦ(ri,m(i))        (14)
となる。
【０１３９】
これらの近似を用いると、Φの引数はxおよびΔcについて線形であり、それらの値について解くために上述した方法が使用される。xおよびΔcについて解いたのち、新しい回転はR+＝R-(I+sk(x))であり、新しい位置はc+＝c-＋R-Δcである。
【０１４０】
最適なRおよびcが計算されたのち、変換されたデータについての堅牢な3Dバウンディング・ボックスが計算される。バウンディング・ボックスの大きさは、オブジェクト・インスタンスの大きさとして取られる。オブジェクト・インスタンスの中心が3Dバウンディング・ボックスの中心に対するcオフセットの最適値である。
【０１４１】
この実施形態では、直方体についての出発点となる配向は、重力ベクトルのまわりの単一の回転角によって与えられる。回転角は、まずデータ・クラスター中の3Dデータ点を2Dのグラウンド平面上に投影し、次いで投影された点に対してRANSAC手順を実行してグラウンド平面上の直線を投影されたデータに堅牢に当てはめることによって計算される。直線発見のためのRANSAC法は、前述した非特許文献６のようなコンピュータ・ビジョンについての多くのテキストにおいて論じられている。その直線が、直方体の一つの辺の配向として取られる。この初期回転をデータに対して適用したのち、堅牢な3Dバウンディング・ボックスが当てはめされ、該堅牢な3Dバウンディング・ボックスの、回転前にレンジ・センサーに最も近い頂点が、上述した計算が行われる見える表面すべてに共通の頂点として取られる。
【０１４２】
〈円柱についてのモデル当てはめ〉
円柱の位置は中心である。その配向は、円柱の中心軸に沿った単位ベクトルaによって与えられる。円柱は半径rおよび高さhをもつ。
【０１４３】
円柱は、まず曲がった側面を当てはめし、次いで中心軸に沿った高さを計算することによって当てはめされる。円柱の側面についての内側−外側関数は、
【０１４４】
【数１】
0005538407.tif 000002
である。ここで、
【０１４５】
【数２】
0005538407.tif 000003
は二つの3Dベクトルに対するクロス積演算を表す。
【０１４６】
球の場合について述べた当てはめ方法は、三つの修正をもってこの関数に適用される。第一に、次のようにしてaに対する単位ベクトル制約が課される。a-がaについての現在の推定値であり、Δaが計算されるべき変化であるとすると、制約a-・Δa＝0が式(12)で形成される連立方程式に加えられる。第二に、aに沿ってのcの値は(15)によって決定されない。この点は、cを、すべての点を軸a上に投影したものの重心付近にあるよう制約することによって是正される。A＝a-aTとし、tavgをすべてのデータ点tの平均とし、Δcを計算すべきcの変化とする。式Atavg＝A(c＋Δc)が前記連立方程式に加えられる。第三に、各反復工程後、aについての新しい推定値が単位ベクトルに規格化し直される。
【０１４７】
円柱の高さおよびaの方向における円柱の中心の位置はいずれも上記の式(15)とは独立である。これらは、まずすべての値a・(t−c)をソートし、最も大きいほうおよび最も小さいほうからある割合の値を除去することによって区間Iを計算することによって推定される。第一の実施形態では1%が除去される。円柱の高さはIの長さに設定され、aに沿った円柱の中心の位置はIの中心に設定される。
【０１４８】
円柱は、直立円柱および斜円柱の二つのケースにおいて当てはめされる。
【０１４９】
直立円柱についての初期値は、データ・クラスターをグラウンド平面に投影することによって計算される。堅牢な2Dバウンディング・ボックスが当てはめされる。初期半径は、バウンディング・ボックスの最大寸法の半分であり、初期中心はバウンディング・ボックスの中心である。初期中心軸はグラウンド平面に対する法線に沿った方向を向く。
【０１５０】
斜円柱についての初期値は、データをグラウンド平面に投影することによって計算される。直線を前記データに堅牢に当てはめするためにRANSAC手順が適用される。この直線とともに配向された堅牢な2Dバウンディング・ボックスが計算される。二つのケースが試験される：円柱の初期軸を前記直線に沿って取る当てはめと、前記直線に垂直な初期軸を用いるものである。初期半径は、選ばれた軸に垂直な方向でのバウンディング・ボックスの大きさの半分として取られる。モデル表面の距離τ内の最大数のレンジ点をもつ当てはめ結果が、結果として返される。
【０１５１】
〈当てはめの際の支持制約条件〉
すべてのオブジェクト・インスタンスは、支持〔サポート〕として一つまたは複数のオブジェクト・インスタンスをもつことが要求される。すべての可能な支持オブジェクトは水平な平面状の上面をもつことが要求される。これは直立円柱および直方体を含む。複数の支持オブジェクトがある場合、それらの上面は同じ高さでなければならない。
【０１５２】
支持は、モデルの底面が支持平面と接触するのに適切であるよう制約することによって、当てはめプロセスに含められる。球または斜円柱については、これは、球または斜円柱の半径を、当てはめの間、支持平面からの高さに設定することによって達成される。直立円柱については、円柱のその中心軸に沿った中心が、支持平面からの円柱の高さの半分に設定される。同様に、直方体については、重力方向における中心の位置は、支持平面から上に向かう方向での直方体の大きさの半分となるよう調整される。
【０１５３】
〈「新オブジェクト計算」関数〉
レンジ表面は、当てはめを通じて分類される。各データ・クラスターは3D点の集合である。この3D点の集合は、単一のオブジェクトとしてモデル化される。3D点の集合および支持平面の高さを与えられると、モデルの底面が支持平面上になるよう制約して、利用可能なモデル当てはめアルゴリズムのすべてがデータに適用される。各ケースにおいて、当てはめの良好さが、当てはめモデルの距離τ内の3D点のデータ・クラスター内のレンジ点の数nとして計算される。この値を最大にするモデルおよびモデル・パラメータが分類の結果として選ばれる。
【０１５４】
モデルを当てはめするレンジ点の数が「オブジェクト存在」試験に合格しない場合、Nをデータ・クラスター中の点の数として取り、nを分類の間に計算される当てはめの良好さとすると、分類は失敗したと考えられる。
【０１５５】
〈「データ・クラスターのための支持」関数〉
「データ・クラスターのための支持」関数は次のように動作する。データ・クラスターからのデータがグラウンド平面に投影され、バウンディング・ボックスが計算される。このグラウンド平面に投影されたときにこのバウンディング・ボックスと交わる任意のオブジェクトが候補支持オブジェクト・インスタンスである。このオブジェクトの集合を枝刈りして、平面状の上面をもたないオブジェクトを除去し、データ・クラスター中のいずれかの点より高い上面をもつオブジェクトを除去する。残りのオブジェクト・インスタンスが、可能性のある支持オブジェクト・インスタンスとして返される。
【０１５６】
〈「支持をもつモデル」〉
「支持をもつモデル」関数は、潜在的な支持のリストを得るために「データ・クラスターのための支持」関数を呼び出す。
【０１５７】
潜在的な支持のリストのすべての要素の平面状の上面の高さが計算される。これは計算された支持高さのリストを生じる。「新オブジェクト計算」関数が前記データ・クラスターおよび計算された支持高さのリストにおける各計算された支持高さをもって呼び出される。
【０１５８】
「新オブジェクト計算」が、計算された支持高さのリストにおける支持高さすべてについて失敗する場合、「支持をもつモデル」は失敗する。
【０１５９】
「新オブジェクト計算」が一つまたは複数の支持高さについて成功すると、対応するデータ・モデルのすべての当てはめの良好さが比較され、最良の当てはめの良好さをもつデータ・モデルが返される。
【０１６０】
〈「既存オブジェクト調整」〉
第一の実施形態では、「既存オブジェクト調整」関数は、次の四つの変更点のほかは「新オブジェクト計算」関数と同じである：１）オブジェクトの形（球、円柱または直方体）が固定に保持される；２）オブジェクト・インスタンスの大きさが固定に保持され、当てはめはポーズ・パラメータに適用されるのみである；３）当てはめは以前のポーズに初期化される；４）当てはめはオブジェクト・インスタンスに関連付けられたデータに対して行われる。「既存オブジェクト調整」についての支持高さは、このオブジェクト・インスタンスについての現在の3Dシーン・モデルにおいて記録された支持オブジェクトの上面の高さに取られる。「既存オブジェクト調整」は、「新オブジェクト計算」関数と同じ条件のもとで失敗となる。
【０１６１】
〈「オブジェクト同一視」〉
第一の実施形態では、二つのオブジェクトがこの試験に合格するのは、同じ型（球、円柱または直方体）であり、寸法がデータ許容差τの範囲内で一致する場合である。
【０１６２】
〈幾何学関数〉
SYアルゴリズムは、センサー・データの型に依存しないいくつかの幾何学的な関数をも利用する。
【０１６３】
「衝突検査」。区別されるオブジェクトpおよび3Dシーン・モデルを与えられて、この関数はpと何らかの「実質的」オブジェクトとの衝突がないかどうか検査する。
【０１６４】
「隣接についての調整」。この関数は、区別されるオブジェクトp、3Dシーン・モデルおよびシフト許容差（tolerance）を受け、pをその下の少なくとも一つの「実質的」支持オブジェクトと接触させ、あらゆる「実質的」オブジェクトとの衝突から外すようポーズ調整を、そのような変位が指定されたシフト許容差内に見出されることができる場合に、計算する。具体的には、まずpをその下の支持（単数または複数）と接触させるための垂直変位を計算する。次いで、その垂直変位がなされたとして、衝突を回避するための水平変位を計算する。指定された許容差内でそのような変位がなかった場合にはこれは失敗する。pが両側で「実質的」なオブジェクトによって囲まれており、どの方向の動きも衝突コンフリクトを解決できない場合にも失敗する。
【０１６５】
「支持」関数。区別されるオブジェクトpおよび3Dシーン・モデルを与えられて、この関数はpを支持するオブジェクト（単数または複数）を返す。
【実施例２】
【０１６６】
〈代替的な実施形態および実装〉
本発明について、ある種の実施形態および実装を参照して説明してきた。さまざまな代替的な実施形態および実装が以下に記載される。以下の議論は限定するものではなく、例解することが意図されていることは認識されるであろう。
【０１６７】
本発明の数多くの代替的な実施形態がある。所与の状況においてどれが好ましいかは、用途を含むいくつかの要因に依存しうる。さまざまな用途は、さまざまな画像型を使い、シーン内のさまざまな型のオブジェクトを認識することを要求し、計算速度についての多様な要求をもち、計算装置の費用についての多様な制約をもつ。これらおよびその他の考察が、複数の代替の間での選択を左右する。
【０１６８】
〈データ関連付け〉
図１において、ステップ１０５を参照するに、画像データが3Dシーン・モデルのオブジェクトと比較される。pを3Dシーン・モデルG内のオブジェクトとする。Rlobsを観察されるレンジ画像、Γを観察者記述子とする。第一の実施形態は、pについての符号付き距離関数を使ってpに関連付けられるデータを計算した。代替的な諸実施形態は、pに関連付けられたデータを他の仕方で計算する。たとえば、合成レンジ・マップRlrend(G,Γ,p)を使って、
Ap＝｛l∈Lp:  |Rlobs−Rlrend(G,Γ,p)|≦τ  ∧            (16)
∀q  |Rlobs−Rlrend(G,Γ,q)|≧|Rlobs−Rlrend(G,Γ,p)|｝
と計算してもよい。τの値はセンサー依存であり、第一の実施形態と同じ仕方で決定される。
【０１６９】
他の実施形態は、関連付けを実行するために他の方法を使ってもよい。一つの方法は、データ点のモデルへの関連付けの品質指標を計算し、品質指標を超えるデータ点を受け容れることである。一つのそのような品質指標は、オブジェクトの存在を条件とするデータ尤度（likelihood）である。もう一つの品質指標は、存在オブジェクトを与えられてのデータの尤度とオブジェクトが不在であることを与えられたときのデータの尤度との尤度比である。
【０１７０】
他の実施形態は複数の関連付けを許容して、複数の代替的な3Dシーン・モデルを生成および維持し、処理ののちの段階にそれらの曖昧さを解決してもよい。
【０１７１】
〈「オブジェクト存在試験」〉
第一の実施形態では、オブジェクトpについての「オブジェクト存在試験」関数はpに関連付けられた画像位置の数nを合成レンダリングされた3Dシーン・モデルにおいて可視であるpの画像位置の数Nと比較することによって動作した。代替的な実施形態では、整数nは、それぞれ確率α≧erf(τ/(σsqrt(2)))−βで真であるN回の観察の二項ランダム変数としてモデル化される。nに対する分布は、平均μ＝αNでσ＝sqrt(Nα(1−α))をもつ正規分布を使って近似される。この近似方法は一般的に使われており、非特許文献１５のような標準的なテキストにおいて説明されている。このテキストは、erf関数の必要な値を示す表も含んでいる。
【０１７２】
そのような代替的な実施形態では、「オブジェクト存在」試験が成功するのは、
α＝erf(τ/(σsqrt(2)))−βとして、n＞αN−5sqrt(Nα(1−α))    (17)
となる場合である。
【０１７３】
〈「支持をもつモデル」〉
第一の実施形態では、「支持をもつモデル」関数は記載されたように動作した。代替的な実施形態では、より一般的な支持関係が認められてもよい。たとえば、オブジェクトは、接触点がさまざまな高さにあっても支持されもよい。
【０１７４】
他の実施形態は、追加的な物理的制約条件および準拠を利用してもよい。いくつかの実施形態は、重力をモデル化し、オブジェクト支持関係が重力と整合することを保証してもよい。他の実施形態は、支持関係を計算するために表面摩擦のような他の物理的属性を使ってもよい。他の実施形態は、オブジェクトの材料属性についての情報を維持し、オブジェクトが接触力のもとで変形することを許容してもよい。
【０１７５】
〈「既存オブジェクト調整」〉
第一の実施形態では、「既存オブジェクト調整」関数は記載されたように動作した。代替的な実施形態では、より一般的な技法が使われてもよい。たとえば、ポーズ変化だけを計算するのではなく、オブジェクトの大きさが新しいデータに基づいて調整されてもよい。さらに、より一般的な支持関係が認められてもよい：オブジェクトは、接触点がさまざまな高さにあっても支持されていてもよい。また、追加的な物理的制約条件が課されてもよく、準拠が許容されてもよい。
【０１７６】
〈「隣接についての調整」〉
第一の実施形態では、「隣接についての調整」関数は記載されたように動作した。代替的な実施形態では、より一般的な技法が使われてもよい。たとえば、変位だけを計算するのではなく、一般的なポーズ変化が計算されてもよい。さらに、衝突を回避するために、ポーズのほかにオブジェクトの大きさも、制限内で、変えられてもよい。この大きさ調整は、新しいオブジェクトが二つの既存のオブジェクトの間に緊密に置かれている場合に必要とされることがありうる。
【０１７７】
第一の実施形態では、「新オブジェクト計算」関数が呼び出され、その後「隣接についての調整」関数が呼び出される。代替的な実施形態では、オブジェクト・モデリングおよび隣接オブジェクトについての調整は合同して実行されてもよい。すなわち、オブジェクト隣接が、「新オブジェクト計算」関数によって使われる最適化プロセスの間の硬制約条件として取られてもよい。
【０１７８】
さらに他の実施形態では、オブジェクトのポーズを計算する際に、オブジェクトがその指示の上に正しく置かれるよう、幾何学的な制約条件のほかに物理的な制約条件が考慮されてもよい。各オブジェクトの重心が、一様密度を想定することによって、あるいはオブジェクト・ライブラリ中のデータから得られてもよい。次いで、オブジェクトのポーズが、オブジェクトの重心が支持多角形の内部になるよう計算される。
【０１７９】
〈「オブジェクト同一視」〉
第一の実施形態では、オブジェクトp1およびp2が互いに同一視されうるのは、両者が同じ型（球、円柱または直方体）であり、データ許容差値τの範囲内で寸法が一致する場合であった。他の実施形態では、試験が近接性、すなわち、p1の以前の位置からのp2の距離、および／または以前の位置からp2の位置までの経路上の障害物の存在を含んでいてもよい。さらに他の実施形態では、試験はさらに、たとえば球は簡単に転がるといった、オブジェクトの物理的属性、あるいは、たとえば壁は典型的には動かないが人は動くといった可動性についての条件を考慮してもよい。同一視の確からしさが返されてもよく、呼び出し側の関数は、複数の可能な同一視があるときにその確からしさを使ってもよい。
【０１８０】
〈超二次曲面〉
第一の実施形態は、3Dシーン・モデル内のオブジェクトが球、円柱または直方体であることを許容している。代替的な実施形態では、追加的なクラスのオブジェクト形状が含められてもよい。オブジェクト形状の多くのクラスが研究されており、これらの形状についてのインスタンスを認識するための技法が公開されている。
【０１８１】
オブジェクト形状の一つのクラスは超二次曲面である。非特許文献１６は、画像中で超二次曲面がどのようにして同定できるかを記載している。これらの技法は、3Dシーン・モデルにおいて超二次曲面のポーズおよびモデル・パラメータを計算し、「新オブジェクト計算」関数を実装するために用いられる。
【０１８２】
第一の実施形態と同様に、関連付けられたデータおよび関連付けられていないデータを見出すために「データ関連付け」が実行される。関連付けられていないデータに対して「検出およびクラスター化」が呼び出されて、データ・クラスターが形成される。各データ・クラスターが「新オブジェクト計算」への入力として与えられ、「新オブジェクト計算」がこれらの代替的な実施形態では、各クラスターを一つまたは複数の超二次曲面としてモデル化する。
【０１８３】
〈レンジ・モデル・オブジェクト（Range  Model  Objects）〉
さらに他の代替的な実施形態では、オブジェクト・モデルのライブラリがあり、シーン内の各オブジェクト・インスタンスがライブラリ中に存在する限り、シーン内のオブジェクト・インスタンスは任意の形状であってもよい。ライブラリ中のモデルはレンジ画像（range  images）に基づく。
【０１８４】
この代替的実施形態の動作は第一の実施形態と同様である。主要な違いは「新オブジェクト計算関数」である。「新オブジェクト計算」関数は、レンジ画像データをライブラリ中のオブジェクト・モデルと照合し、シーン内でのそれらのポーズを計算する。これは、文献では「レンジ・データにおけるオブジェクト認識」と称されている。
【０１８５】
この分野ではかなりの文献がある。上述した非特許文献４は近年の概説である。特に5.3節「レンジ・データにおける自由形オブジェクト認識（Free-Form  Object  Recognition  in  Range  Data）」を参照。3Dレンジ・モデルでのオブジェクト認識におけるより最近の研究は、非特許文献１７に記載されている。
【０１８６】
これらの技法は、SYアルゴリズムによって使用されるデータ依存関数、特に「新オブジェクト計算」関数を実装するために用いられる。先行研究における共通の問題は、散らかり（clutter）と隠蔽（occlusion）である。SYアルゴリズムのコンテキストでは、これらの問題はかなり軽減される。「新オブジェクト計算」は、シーン内の同定された諸オブジェクトに関連付けられていない孤立した画像データのクラスターをもって呼び出され、それにより散らかりの効果が軽減される。さらに、よくあるように前景においてオブジェクトが加えられるとき、隠蔽の効果が軽減される。というのも、シーン・オブジェクトは完全に可視であるときに認識されることができ、その識別情報が隠蔽されたときにのちの3Dシーン・モデルにおいて保持されうるからである。
【０１８７】
画像データのクラスターがライブラリ中のオブジェクトのどれにも一致すると認識できないことがありうる。代替的な実施形態では、このような状況に次のように対処することが可能である。マッチできなかった画像データの任意のクラスターはまずポリゴンの集合としてモデル化される；これは正面、つまりオブジェクトの、イメージ・センサーに向かう側を記述する。オブジェクトの極小表面が、該オブジェクトを、裏側が正面側と同じ形をもつ薄い殻であるとしてモデル化することにより計算される。オブジェクトの極大体積が、正面を3Dシーン・モデル内の他のオブジェクトに遭遇するまで後方に掃引することによって計算される。極大体積から、極大表面がポリゴンの集合として構築される。オブジェクトは、<極小表面,極大表面>の対として表される。
【０１８８】
〈オブジェクト・モデルのライブラリを用いた強度画像〉
第一の実施形態では、画像はレンジ・データであり、シーン内のオブジェクトは三つの形状クラスの一つに属するものであった。代替的な実施形態では、画像は強度データであり、オブジェクト・モデルのライブラリがある。ライブラリ中のオブジェクト・モデルは幾何学的モデルおよび関連する外観情報からなる。幾何学的モデルおよび関連する外観情報は多くの形を取ることができ、事前のモデル学習段階の間の、オブジェクトのセンサー検知された幾何形状および外観を含む。シーン内の各オブジェクトがライブラリ中に存在する限り、シーン内のオブジェクトは任意の形状であってもよい。ライブラリ中のモデルは強度画像に基づいて認識される。これは時に文献において「外観ベースのオブジェクト認識（appearance-based  object  recognition）」と称される。
【０１８９】
たとえば、強度画像はカラー・カメラから得ることのできるようなカラー画像であってもよい。小型、軽量で安価なものも含め幅広い範囲のカラー・カメラがあるので、これは商業上、重要である。カラー画像から3Dシーン・モデルを構築することには、多くの重要な応用がある。そのいくつかを下記で述べる。
【０１９０】
これらの代替的な実施形態では、SYアルゴリズムによって使用されるデータ依存関数は次のように定義される：
「十分可視」関数は第一の実施形態と同じである。
【０１９１】
「データ関連付け」関数：図１のステップ１０５を参照するに、pを3Dシーン・モデル内のオブジェクトとする。Irend(G,Γ,p)を観察者ΓからのG内のpの合成レンダリングの結果とする。先述したように、所与の視点からの添付されたテクスチャーまたは外観情報を用いて三次元幾何学的オブジェクトをレンダリングすることは、コンピュータ・グラフィクスにおいてよく理解された処理である。
【０１９２】
Iobsがセンサー検知される画像であるとする。IobsおよびIrend(G,Γ,p)の両方は、ポーズの小さな変化への感度を下げるよう設計された低域通過フィルタおよびローカルまたはグローバルなピクセル強度の変化について補正するためのカラー規格化を用いて処理され、結果としてそれぞれFobsおよびFrend(G,Γ,p)を与えてもよい。Lを画像位置の集合とする。pに関連付けられたデータは
Ap＝｛l∈Lp:  ‖Flobs−Flrend(G,Γ,p)‖≦τ  ∧            (18)
∀q  ‖Flobs−Flrend(G,Γ,q)‖≧‖Flobs−Flrend(G,Γ,p)‖｝
と計算してもよい。
【０１９３】
他の実施形態は、オブジェクトのポーズの小さな変化に敏感でない他の距離指標を利用してもよい。例としては、シャッフル距離（shuffle  distance）、面取り距離（chamfer  distance）およびバッタチャリヤ・ヒストグラム距離（Bhattacharyya  histogram  distance）が含まれる。
【０１９４】
「オブジェクト存在試験」関数：図２のステップ２０３を参照するに、これは、Apがすぐ上の式のように計算される点を除いては第一の実施形態と同じである。
【０１９５】
「検出およびクラスター化」関数は、クラスタリングが関連付けられていないデータの2D画像位置のみを使って実行される点を除いては、第一の実施形態と同じである。これは、データのセグメント分割が不十分になることがあり、それによりデータ・クラスターが二つ以上のオブジェクト・インスタンスに対応することがある。この不足セグメント分割についてはのちに論じる。
【０１９６】
図１のステップ１０８で言及される「新オブジェクト計算」関数は、関連付けられていない画像データのクラスターを、オブジェクト・モデルのライブラリ中のモデルと照合する。具体的には、（１）ライブラリから最良一致モデルを選び、（２）観察された画像データに最もよく合致する3Dシーン・モデル内に置かれるオブジェクト・インスタンスについてのポーズを計算する。これを行うための技法については膨大な文献がある。上述した非特許文献４は概説であり、特に5.1節「外観ベースの認識（Appearance-Based  Recognition）」を参照。これらの技法のうち任意のものが、多様な代替的実施形態において「新オブジェクト計算」関数を実装するために使用できる。本発明のコンテキストでは、これらの技法は、各照合において考慮されるべきデータが関連付けられていないデータのクラスターであり、これは典型的には画像全体よりずっと小さく、それにより探索および他の組み合わせステップを軽減するという計算上の利点を得る。
【０１９７】
「データ・クラスターのための支持」関数：画像が強度画像であるとき、可能な支持は、関連付けられていないデータから必ずしも信頼できる形で決定できない。よって、この関数はヌル演算である。
【０１９８】
「支持をもつモデル」関数：この関数は、「新オブジェクト計算」関数を呼び出し、それに関連付けられていないデータのクラスターを渡す。
【０１９９】
「既存オブジェクト調整」関数は、次の相違のほかは「新オブジェクト計算」と同様である：１）オブジェクト・モデルのライブラリ中のオブジェクトの選択が固定され、3Dシーン・モデルにおけるオブジェクト・インスタンスのポーズのみが修正される、２）事前ポーズが、新しいポーズを見出すプロセスを初期化するために使われる、３）当てはめはオブジェクト・インスタンスに関連付けられたデータに対して行われる。
【０２００】
「オブジェクト同一視」試験：二つのオブジェクト・インスタンスがこの試験に合格するのは、両者がオブジェクト・モデルのライブラリ中の同じオブジェクトのインスタンスである場合である。
【０２０１】
〈強度画像における画像特徴〉
外観ベースのオブジェクト認識のために使われる技法のいくつかは、画像特徴を使う。概略的には、これらの技法は、画像中で特徴的な点（時に「関心点」または「キーポイント」とも称される）を見出し、これらの特徴的な点における特徴を抽出し、これらの特徴を、データベース中の特徴のライブラリと照合するために使う。ライブラリ中の各オブジェクトは特徴の集合を有しているので、特徴マッチングは、オブジェクト・マッチングを達成するために使用できる。
【０２０２】
このクラスの技法は多くの技術論文において記述されている。一つは、非特許文献１８である。もう一つは非特許文献１９である。もう一つは非特許文献２０である。さらに、新たな技法が本発明者による特許文献１に記載されており、ここに参照によって組み込まれる。
【０２０３】
マッチング技法が特徴に基づくとき、データ依存関数のいくつかにおいて画像ピクセル値ではなく特徴を使う代替的な実施形態がある。主要な相違点は次のとおりである。
【０２０４】
「十分可視」関数：「十分可視」関数は、観察者Γからの3Dシーン・モデルGにおけるオブジェクト・インスタンスpについて次のように計算される。3Dシーン・モデルGを処理して、当該観察者Γ記述から見えるであろう特徴を検出する。具体的には、pがG内のオブジェクト・インスタンスである場合、{fprend}を観察者ΓからのGにおいて見えるpの特徴（feature）であるとする。nを{fprend}の大きさとする。nがある閾値より大きければ、pは十分なデータをもつと見なされ、そうでなければ十分なデータをもたないと見なされる。
【０２０５】
「データ関連付け」関数：図１の処理１０５を参照。観察された画像が処理されて画像特徴を検出する；それを{fobs}と呼ぶ。3Dシーン・モデルGが処理されて、当該観察者Γ記述から見えるであろう特徴を検出する。具体的には、pがG内のオブジェクト・インスタンスである場合、{fprend}を観察者ΓからのGにおいて見えるpの特徴（feature）であるとする。pに関連付けられているデータは、同じまたは近い画像位置における{fprend}の特徴に一致する{fobs}の特徴である。関連付けられていないデータは、そのような一致ができない{fobs}の特徴である。
【０２０６】
「オブジェクト存在試験」関数は特徴マッチに基づく。たとえば、pが3Dシーン・モデルにおけるオブジェクトであり、{fpmatch}が{fprend}のうち{fobs}の特徴に一致する部分集合であるとする。「オブジェクト存在」試験は|{fpmatch}|の|{fprend}|に対する比を考えてもよい。他の代替的実施形態では、一致の品質も使用されてもよい。
【０２０７】
「検出およびクラスター化」関数は、関連付けられていないすべての特徴を検出し、それらを単一のクラスターに入れる。
【０２０８】
「新オブジェクト計算」関数：図１のステップ１０８を参照するに、この関数は、集合{fobs}からのマッチしていない特徴のクラスターを、オブジェクト・モデルのライブラリ中のモデル内の特徴にマッチさせる。マッチされた特徴から、ライブラリからの最良マッチのモデルを選び、観察された画像データに最もよく合致する3Dシーン・モデル内に置かれたオブジェクト・インスタンスについてのポーズを計算する。
【０２０９】
「既存オブジェクト調整」関数は、オブジェクトに関連付けられた特徴をマッチングし、レンダリングされた特徴の位置が、それらの特徴がマッチングされた観察された特徴と整合するようオブジェクトのポーズを調整することに基づく。
【０２１０】
〈クラス・モデルのライブラリを用いた強度画像〉
第一の実施形態では、画像はレンジ・データであり、シーン内のオブジェクトは三つのクラスのうちの一つに属するものであった。代替的な実施形態では、画像は強度データであり、クラス・モデルのライブラリがある。シーン内の各オブジェクトがライブラリ中のクラスのインスタンスである限り、シーン内のオブジェクト・インスタンスは任意の形状であってもよい。ライブラリ中の各クラス・モデルは関係するオブジェクトのクラス、たとえば椅子、トラック、自動車、納屋などを記述する。用途に依存して、クラスは階層的であってもよい。たとえば、トラックのクラスはダンプカー、レッカー車、ピックアップトラックなどからなっていてもよい。
【０２１１】
ライブラリ中のクラスは強度画像に基づく。典型的には、各クラスはそのクラスの複数のインスタンスからの統計的な学習プロセスによって得られる。クラス・モデルは諸クラス・インスタンスに対して一般化し、それらのインスタンスの間で共通するものを抽象化する。
【０２１２】
この代替的実施形態の動作は上述した「オブジェクト・モデルのライブラリを用いた強度画像」と似ている。主要な相違は、「新オブジェクト計算」関数、図１のステップ１０８である。ライブラリがクラス・モデルからなる場合、「新オブジェクト計算」は三つの活動を実行する。（１）ライブラリから最もよく一致するモデルを選び、（２）観察された画像データに最もよく合致する3Dシーン・モデル内に置かれたオブジェクト・インスタンスについてのポーズを計算し、（３）オブジェクト・インスタンスがどのようにしてクラス・モデルから導出されるかを記述するクラス固有パラメータθを計算する。たとえば、クラス・モデルは拡張可能であってもよく、その場合、クラス・パラメータはサイズを指定する；あるいはクラス・モデルは各次元方向に伸張可能であってもよく、その場合、クラス・パラメータは各方向における伸張を指定する。
【０２１３】
クラス・モデルのライブラリ中のモデルに画像データをマッチングするための多くの技法がある。たとえば、さまざまな技法が以下の論文に記述されている：（１）非特許文献２１、（２）非特許文献２２、（３）非特許文献２３、（４）非特許文献２４。さらに、画像データを3Dクラス・モデル中のモデルに画像データをマッチングするための新たな技法が本発明者による特許文献１に記載されている。これらの技法のうちいずれが、クラス・モデルのライブラリ中のモデルに画像データをマッチングするために使われてもよい。
【０２１４】
クラス・モデルのそのようなライブラリが代替的な実施形態において使用されるとき、該ライブラリは、該ライブラリ中の各クラスについてパラメータ化された形状モデルを有するよう構築される。関連付けられていない画像データとクラス・モデルCとの間のマッチが与えられると、ポーズが計算され、さらに、C(θ)がオブジェクト・インスタンスの3D形状を指定するよう、クラス・パラメータθの集合が計算される。
【０２１５】
「既存オブジェクト調整」関数は、次の相違のほかは「新オブジェクト計算」と同様である：（１）オブジェクト・モデルのライブラリ中のオブジェクトの選択が固定され、3Dシーン・モデルにおけるオブジェクト・インスタンスのポーズおよびクラス・パラメータのみが修正される、（２）事前ポーズおよびクラス・パラメータが、新しいポーズおよびクラス・パラメータを見出すプロセスを初期化するために使われる、（３）当てはめはオブジェクト・インスタンスに関連付けられたデータに対して行われる。
【０２１６】
〈レンジ＋強度画像〉
第一の実施形態では、画像はレンジ・データであり、シーン内のオブジェクトは三つのクラスのうちの一つに属するものであった。他の実施形態では、画像はレンジ・データに強度データを加えたものであってもよく、シーン内のオブジェクトは、オブジェクト・モデルのライブラリ中のオブジェクトまたはクラス・モデルのライブラリ中のオブジェクトであってもよい。
【０２１７】
この代替的な実施形態の動作は、第一の実施形態の動作と同様である。主要な相違は「新オブジェクト計算」関数である：この代替的な実施形態では、「新オブジェクト計算」は、レンジおよび強度情報の両方を使って、関連付けられていないデータをライブラリ中の、オブジェクト・モデルまたはクラス・モデルのモデルにマッチングする。これを行うための技法は本発明者による特許文献１に記載されており、ここに参照によって組み込まれる。
【０２１８】
〈データ・クラスター中の複数オブジェクトの同定〉
図１のステップ１０８、「新オブジェクト計算」を参照するに、第一の実施形態では、関連付けられていないデータの各データ・クラスターは単一のオブジェクトとしてモデル化される。他の実施形態では、データ・クラスターは二つ以上のオブジェクトに対応してもよい。この場合、「新オブジェクト計算」はデータ・クラスター中のいくつかのオブジェクトを同定する必要がある。
【０２１９】
上記の代替的実施形態において記述される「新オブジェクト計算」関数を実装するためのさまざまな技法の多くは、データ・クラスター中の複数のオブジェクトを同定することができる。しかしながら、それらの計算時間は通例、同定するオブジェクトの数の関数として増大し、増大は典型的には線形よりも速い。本発明のコンテキストでは、これらの技法は、各マッチにおいて考慮されるべきデータが関連付けられていないデータのクラスターであり、これは典型的には画像全体よりずっと小さく、それにより探索および他の組み合わせステップを軽減するという計算上の利点を得る。
【０２２０】
〈複数観察者〉
本発明について、上記では、単一の観察者Γをもつ単一センサー・システムのコンテキストで記述してきた。しかしながら、本発明は、それぞれが観察者をもつ複数のセンサー・システムを利用してもよく、一般には観察者の集合{Γi}がある。この場合、「十分可視」関数は、各観察者Γiについて「十分可視」関数を考え；いずれかのΓiからオブジェクトが「十分可視」であれば、試験は成功する。「オブジェクト存在試験」が成功するのは、「十分可視」が成功するすべての観察者について「オブジェクト存在試験」が成功する場合である。「データ関連付け」「検出およびクラスター化」「新オブジェクト計算」「データ・クラスターのための支持」および「支持をもつモデル」関数はすべてのセンサーからのデータを使う。
【０２２１】
〈動いている観察者〉
本発明は、時間とともに動く一つまたは複数のセンサー・システムを利用してもよく、一般には時間変動する観察者記述の集合{Γi}がある。この場合、観察者の位置は、ジョイント・エンコーダ（joint  encoders）、走行距離測定（odometry）またはGPSのような外部センサーによって与えられてもよい。あるいはまた、観察者のポーズは、画像自身から、以前の画像または以前のシーン・モデルと比較することによって計算されてもよい。あるいはまた、観察者の位置は、それらの何らかの組み合わせによって計算されてもよい。
【０２２２】
〈動いているオブジェクト〉
第一の実施形態では、動的モデル〔ダイナミック・モデル〕は、オブジェクトは典型的には動かないというものである。代替的な実施形態では、動的モデルは、たとえば一定速度で、あるいは一定加速度で、可能性としては制約された経路に沿って、可能性としては他のオブジェクトとの関係で、動いていると知られている一つまたは複数のオブジェクトを与えてもよい。そのような代替的な実施形態では、事前3Dシーン・モデルは、計算された3Dシーン・モデルを初期化するために使われる前に、動的モデルに従って更新されうる。
【０２２３】
〈シーンの領域への分割〉
第一の実施形態では、探索はSYアルゴリズムによって実行された。代替的な実施形態では、代替的な探索技法が使用されてもよい。特に、シーンの構造が、探索プロセスにおける計算を最適化するために使用されてもよい。
【０２２４】
一つの最適化は、シーンを分離した領域に分け、各領域に対して別個にまたは並列して処理することである。各領域に対して別個に処理することは、オブジェクト数に関連する組み合わせ上の複雑さを軽減する。さらに、各領域に対して並列に処理することは、複数プロセッサの効率的利用を許容する。この分離がいつ実行されうるかの例としては、視野を張るグラウンド平面があるとする。3Dシーン・モデル内のオブジェクトが、3Dシーン・モデルがレンダリングされるときに諸領域のレンダリングされた像がグラウンド平面によって分離されるよう、諸領域に分割されてもよく、センサー検知された画像が同じ仕方で分割されてもよいとする。すると、領域どうしは相互作用せず、各領域は独立して処理されてもよい。
【０２２５】
〈隠蔽順序付け（Occlusion  Ordering）の使用〉
探索を組織化するもう一つの方法は、隠蔽によって誘起される順序付けを、該順序付けが曖昧でない場合に用いることである。順序付けが曖昧でない場合、処理は前景から背景の順に実行される。
【０２２６】
一例として、画像がレンジ・データである場合を考える。Gが3Dシーン・モデルであり、Iobsが観察された画像であり、Γが観察者記述であるとする。他のオブジェクトによって隠蔽されていないG内のオブジェクトpがあるとする。Lpを、観察者記述Γからpが可視である位置の集合であるとする。すべての位置l∈Lpについて、Ilobsは、第一の実施形態で述べた意味において、オブジェクトpに関連付けられているとする。すると、pは同じポーズで存在していると解釈され、その後の処理における考慮から除外される；さらに、画像位置l∈Lpはその後の処理から除外できる。G内に、以前にさらなる処理から除外されたオブジェクトのみによって隠蔽される他のオブジェクトqがあれば、処理は継続できる。
【０２２７】
第一の実施形態のステップ６０１を実行することによって、以前に観察されなかったオブジェクトがこの修正に含められる。結果として生じるデータ・クラスターは三角形分割された表面としてモデル化され、現在の3Dシーン・モデルに一時的に挿入されることができる。各オブジェクト・インスタンスは前から後にかけて処理されるので、これらの一時的なオブジェクト・インスタンスは遭遇される。遭遇されるたびに、そのデータについてのオブジェクト・インスタンスを生成するために「新オブジェクト計算」関数が呼び出される。
【０２２８】
不在オブジェクトが前から後への順序付けにおいて遭遇される際に各不在オブジェクトを試験してそれが関連付けられていないデータ・クラスターに接続されているかどうかを判定することによって、摂動されたポーズをもつオブジェクトが含められる。もしそうであると判定されたら、第一の実施形態において述べたように「新オブジェクト計算」が呼び出される。
【０２２９】
〈複数の代替にわたる最適化〉
SYアルゴリズムは、その処理の間、固定したセットの諸決定を行い、単一の最終的3Dシーン・モデルに導く。代替的な実施形態は、複数の代替を探査する探索アルゴリズムを使ってもよく、それらの代替のうちから選択することによって最良の3Dシーン・モデルを返す。
【０２３０】
たとえば、SYアルゴリズムは、ステップ６０４において各データ・クラスターについて単一のオブジェクト・モデルを選ぶ。しかしながら、代替的な探索アルゴリズムは、関連付けられていないデータのクラスターについて、複数の可能なオブジェクト・モデルを計算し、次いで複数の3Dシーン・モデルを考えてもよい。各3Dシーン・モデルは可能なオブジェクト・モデルのうちの一つを含む。結果として得られる各3Dシーン・モデルは最後まで処理され、評価されて最も確からしいモデルが決定される。
【０２３１】
SYアルゴリズムは、該アルゴリズムのステップ６０３における各「未検証」オブジェクトについて、特定のデータ・クラスターを選ぶ。代替的な実施形態は、いくつかの相異なるデータ・クラスターからの「未検証」オブジェクトをモデル化することを試みてもよい。結果として得られる各3Dシーン・モデルは最後まで処理され、評価されて最も確からしいモデルが決定される。
【０２３２】
複数の3Dシーン・モデルの評価は、データを説明するためのモデルの品質および事前3Dシーン・モデルから3Dシーン・モデルを生成するために必要な変化の確率を含んでいてもよい。たとえば、下記でより詳細に述べる確率的定式化を利用してもよい。
【０２３３】
代替的な探索アルゴリズムは、複数の3Dシーン・モデルを維持してもよく、モデルの尤度またはモデル品質の他の指標の推定を使って動的にモデルのセットを枝刈りしてもよい。探索は、木探索を使ってその計算を実行してもよい。その場合、分枝限定法（branch  and  bound  methods）が適用されてもよい。
【０２３４】
〈3Dシーン・モデルに対する分布〉
第一の実施形態では、3Dシーン・モデルはそれぞれ特定のポーズおよびパラメータをもつオブジェクトの集合である。代替的な諸実施形態では、3Dシーン・モデルは分布であってもよい。曖昧さを避けるため、この種の3Dシーン・モデルは「3Dシーン分布」と称することが有用である。事前3Dシーン・モデルについての不確定さがある場合、それは事前3Dシーン分布として表現される。計算された3Dシーン・モデルについての不確定さがある場合、それは計算された3Dシーン分布として表現される。
【０２３５】
一つのそのような代替では、各オブジェクトはそのポーズに対する分布によって表現される。オブジェクト・クラスが考慮されるとき、各オブジェクトは、クラス・インスタンスを記述するパラメータに対する分布によって追加的に表現されてもよい。これらの分布はパラメータの不確定性を表す。
【０２３６】
さらにもう一つの代替では、3Dシーン分布は構造に対する分布である。すなわち、分布の各要素はそれ自身が事前3Dシーン・モデルであり、それぞれオブジェクトのポーズおよび可能性としてはオブジェクトのパラメータに対する独自の分布をもつ。これらの要素は構造およびパラメータ両方の不確定性を表す。
【０２３７】
事前が3Dシーン分布だとする。いくつかの代替的な実施形態では、分布はサンプリングされ、上述した諸技法が各サンプルに適用される。結果は計算された3Dシーン分布である。他の代替的な実施形態は後述するように分布を使用する。
【０２３８】
〈確率的な定式化〉
事前3Dシーン・モデル、画像およびシーン変化ダイナミクスのモデルを与えられるとき、本発明は、観察された画像および事前3Dシーン・モデルに対するありそうな変化と整合する新しい3Dシーン・モデルを計算する。
【０２３９】
最適解は確率を用いて次のように公式化できる：G-を事前3Dシーン・モデル、Iobsを画像、Γを観察者記述とする。目標は、画像をもっとよく説明する3Dシーン・モデルG+を計算することである。G+は次式を満たす。
【０２４０】
P(G+|Iobs,G-,Γ)＝maxG  P(G|Iobs,G-,Γ)      (19)
右辺を展開してシーン発展についてのマルコフ想定を通じた独立性を活用すると、右辺は次のように書ける。
【０２４１】
maxG  P(Iobs|G,Γ)P(G|G-)      (20)
第一項はデータ項、つまり3Dシーン・モデルおよび観察者Γが与えられたときの画像Iobsの確率である。第二項のG-が与えられたときのGの確率は、シーン・ダイナミクスのモデルに基づく、シーンに対するありそうな変化を記述する。
【０２４２】
最適なG+を計算することは、二つの部分問題に係わる：（１）Gにおけるオブジェクト追加および除去の離散的な探索および（２）Gにおけるオブジェクトの自由パラメータ、たとえばそのポーズの連続的な最適化。これら二つの問題は、連立して解かなければならない。
【０２４３】
P(Iobs|G,Γ)およびP(G|G-)の構造によっては、この問題はきわめて複雑であることがある。近似解を計算する方法を使うことが必要なこともありうる。
【０２４４】
複数の代替にわたって最適化する実施形態は、P(Iobs|G,Γ)P(G|G-)の値を使って3Dシーン・モデルGを評価してもよい。複数の3Dシーン・モデルは、事前3Dシーン分布からサンプリングすることによって生じてもよいし、あるいは複数の3Dシーン・モデルは正しい決定が曖昧である計算中の諸点において生じてもよい。
【０２４５】
〈逐次的モンテカルロ法〉
複数の代替を使って近似解を計算する技法の注目すべきクラスは、サンプリングに依拠する逐次モンテカルロ法である。そのような方法についてのテキストとしては、非特許文献２５を参照。3Dシーン・モデルは画像および事前3Dシーン・モデルから、一連のインクリメンタルな変化を含む多段問題として計算される。
【０２４６】
ある実施形態では、複数の可能な3Dシーン・モデルは複数の粒子（particle）によって表現される。これは、複数の仮定が同時に維持される探索と見なされてもよい。一般に、各粒子はそのオブジェクトを分布として表現しうる。計算は諸エポックに分割される。t番目のエポックによって表される可能な3Dシーン・モデルの集合があり、St＝{Gt1,...,Gtnt}と表される。S0は{G-}、つまり事前3Dシーン・モデルからなる集合に初期化される。集合StはSt-1、Iobs、P(Iobs|Gt,Γ)およびP(Gt|G-)からエポック当たり２フェーズにおいて漸進的に計算される。
【０２４７】
第一フェーズでは、一時的粒子集合Ttが計算される。各Gt-1kについて、データ関連付けがIobsとGt-1kの間で実行され、結果として関連付けられたデータおよび関連付けられていないデータを与え、それが可能なローカルな変化を計算するために使われる。可能なローカルな変化はサンプリングされて、結果としてGtjを与える。この第一のサンプリングはTtが十分なサイズに達して
Tt＝{Gt1,...,Gtnt}
となるまで続けられる。
【０２４８】
第二フェーズでは、Ttは各3Dシーン・モデルGtkの全体的な尤度に比例する確率で、すなわちP(Iobs|Gtk,Γ)P(Gtk|G-)に比例して、サンプリングされる。このサンプリングの結果が集合Stである。
【０２４９】
この技法には、各エポックの第一フェーズにおいて変化がどのようにサンプリングされるか、また第二フェーズにおいてどのように再サンプリングが実行されるかに依存して多くの変形がある。
【０２５０】
〈手順ステップの実装〉
いくつかの実施形態の手順ステップは上述した。これらのステップは多様なC++、C、ジャバ、フォートランまたは他の任意の汎用プログラミング言語といったプログラミング言語で実装されうる。これらの実装は、特定のコンピュータの機械語にコンパイルされてもよいし、あるいはインタープリットされてもよい。特定のコンピュータのアセンブリ言語または機械語で実装されてもよい。
【０２５１】
本方法は、コンピュータ可読媒体上に記憶されるプログラム命令を実行するコンピュータ上で実装されてもよい。
【０２５２】
手順ステップは、汎用コンピュータまたは特化したプログラム可能なプロセッサで実装されてもよい。そのような特化したハードウェアは、デジタル信号プロセッサ（DSP）、グラフィクス・プロセッサ（GPU）、メディア・プロセッサおよびストリーミング・プロセッサを含む。
【０２５３】
手順ステップはまた、このタスクのために設計された特化したプロセッサにおいて実装されてもよい。特に、集積回路が使われてもよい。使用されうる集積回路技術の例は現場プログラム可能なゲート・アレイ（FPGA:  Field  Programmable  Gate  Array）、ゲート・アレイ、標準セルおよびフル・カスタムを含む。
【０２５４】
本発明の開示において記述される方法のいずれを使った実装も、シリアルではなくパラレルに手順ステップの一部を実行してもよい。
【０２５５】
〈ロボット操作への応用〉
諸実施形態は、3Dオブジェクト・モデルを生成するとして記述されてきた。そのような3Dオブジェクト・モデルは、自律ロボット・マニピュレータのコンテキストにおいて、意図が自由空間で動くことであるときにオブジェクトを回避する軌跡を計算し、掴んだりその他の操作をしたりすることが意図であるときに掴んだりその他の操作をしたりするための接触点を計算するために使用できる。
【０２５６】
〈他の応用〉
本発明は、部分的にはロボット操作のコンテキストで記述されてきた。本発明はこの一つの応用に限定されるものではなく、他の応用にも適用されうる。このリストは限定するものではなく例解するものとして意図されており、本発明が多様な目的のために利用できることは認識されるであろう。
【０２５７】
一つのそのような応用はロボット手術である。この場合、目標は、ツールの安全マージンを決定する、あるいは解剖構造の適切な部分に位置合わせされた術前情報を表示するためのシーン解釈でありうる。オブジェクト・モデルは器官のためのモデルのアトラスに由来し、認識は外観情報および変形可能な位置合わせを通じた当てはめを利用するであろう。
【０２５８】
もう一つの応用は監視である。システムは予期される変化のカタログを与えられ、予期されるものからの逸脱を検出するために使用される。たとえば、そのようなシステムは、家庭、オフィスまたは公共の場所をモニタリングするために使用できる。
【０２５９】
〈結語、派生問題および範囲〉
本稿に開示される発明は3Dシーン・モデルを構築するための方法を提供する。
【０２６０】
本発明はまた、前記のさまざまな方法のステップを実行するよう構成された一つまたは複数のコンピュータまたは他の計算装置を有する、3Dシーン・モデルを構築するためのシステムをも提供する。本システムは、シーンの画像を取得するための一つまたは複数のカメラをも含んでいてもよく、事前3Dシーン・モデルおよび／または構築された3Dシーン・モデルを保持するための一つまたは複数のメモリまたは他の手段をも含んでいてもよい。
【０２６１】
本発明はまた、本稿に記載した前記のさまざまな方法のステップを実行するためのプログラム命令を具現したコンピュータ可読媒体をも提供する。
【０２６２】
以上の発明の詳細な説明では、本発明はその個別的な実施形態を参照して記述されている。当業者は、本発明がそれに限定されるものではなく、上記の実施形態に記述されたもの以外のステップまたは構成を使っても、あるいは上記の実施形態以外のステップまたはシステムとの関連でも容易に実装されることができることを認識するであろう。上記の本発明のさまざまな特徴および側面は個々に使用されてもよいし、あるいは合同して使用されてもよい。さらに、本発明は、本明細書の広義の精神および範囲から外れることなく、本稿に記載されたもの以外にもいくらでもある環境および応用において利用されることができる。よって、本明細書および図面は、制約するものではなく例解するものと見なされるべきである。実施形態に対するこれらおよびその他の変形は、本発明によってカバーされることが意図されており、本発明は付属の請求項によってのみ限定される。
【図１】
0005538407.tif 000004
【図２】
0005538407.tif 000005
【図３】
0005538407.tif 000006
【図４】
0005538407.tif 000007
【図５】
0005538407.tif 000008
【図６】
0005538407.tif 000009