(57)【要約】      （修正有）【課題】3D実行時画像内のトレーニングされた3Dモデル画像のポーズを推定するための3Dアライメントシステムの内部で、実行時3D画像の3Dアライメントポーズを評価するために使用される3次元（3D）プローブの配置を選択するためのシステム、コンピュータ化された方法及びコンピュータ可読媒体を提供する。【解決手段】3D画像から第1の複数の特徴点と関連付けられる複数の特徴を生成する。ここで、各特徴は、複数の特徴点から関連付けられる点の3D特性を示すデータを含んでいる。少なくとも一部は、第1の複数の特徴点と関連付けられる複数の特徴に基づいて、第1の複数の特徴点の中から第2の複数の特徴点が選択される。少なくとも一部は、第2の複数の特徴点に基づいて複数の3Dプローブの配置を決定する。【選択図】図２
2018055679.tif 000002
【特許請求の範囲】
【請求項１】
3D実行時画像内のトレーニングされた3Dモデル画像のポーズを推定するための3Dアライメントシステムの内部で、実行時3D画像の3Dアライメントポーズを評価するために使用される3次元（3D）プローブの配置を選択するためのシステムであって、
メモリと通信するプロセッサを有しており、このプロセッサはメモリに保存されたコンピュータプログラムを実行するように構成されており、このコンピュータプログラムは、
3D画像から第1の複数の特徴点と関連付けられる複数の特徴を生成し、各々の前記特徴は複数の特徴点から関連付けられる点の3D特性を示すデータを含んでおり、
少なくとも一部は第1の複数の特徴点と関連付けられる複数の特徴に基づいて第1の複数の特徴点の中から第2の複数の特徴点を選択し、及び
少なくとも一部は第2の複数の特徴点に基づいて複数の3Dプローブの配置を決定するように構成されている、
システム。
【請求項２】
少なくとも1並進自由度でのアライメントのために、複数の特徴の各々が第1の複数の点の中から関連付けられる点の少なくとも1つの有用性の測定値を包含する、請求項1に記載のシステム。
【請求項３】
少なくとも1回転自由度でのアライメントのために、複数の特徴の各々が第1の複数の点の中から関連付けられる点の少なくとも1つの有用性の測定値を包含する、請求項1に記載のシステム。
【請求項４】
複数の3Dプローブの配置は、第1の複数の特徴点の各々への配置によって提供されるより大きい3並進自由度での集合アライメント能力を提供する、請求項1に記載のシステム。
【請求項５】
複数の3Dプローブの配置は、第1の複数の特徴点の各々への配置によって提供されるより大きい3並進自由度での集合アライメントを提供し、このより大きい集合アライメント能力は、第1の複数の点の最も小さく表された回転自由度での集合アライメント能力の増加を含む、請求項1に記載のシステム。
【請求項６】
複数の3Dプローブの配置は、第1の複数の特徴点の各々への配置によって提供されるより大きい3回転自由度での集合アライメント能力を提供する、請求項1に記載のシステム。
【請求項７】
複数の3Dプローブの配置は、第1の複数の点の最も小さく表された回転自由度での集合アライメント能力の増加を提供する、請求項1に記載のシステム。
【請求項８】
第1の複数の点のサブセットに適合する回転の中心及び回転軸は、回転の中心及び回転軸がパターンの回転対称特徴と関連するように決定される、請求項1に記載のシステム。
【請求項９】
第1の複数の点のサブセットから回転の中心及び回転軸を見出すことは、RANSAC技術を用いることを含む、請求項8に記載のシステム。 
【請求項１０】
複数の特徴は、複数の面法線 ベクトルを含んでいる、請求項1に記載のシステム。
【請求項１１】
複数の特徴は、複数のエッジ近接ベクトルを含んでいる、請求項1に記載のシステム。
【請求項１２】
複数の特徴は、複数のエッジ方向ベクトルを含んでいる、請求項1に記載のシステム。
【請求項１３】
複数の特徴は複数の表面湾曲ベクトルを含んでいる、請求項1に記載のシステム。
【請求項１４】
少なくとも一部は第1の複数の特徴点と関連付けられる複数の特徴に基づいて、第1の複数の特徴点の中から第2の複数の特徴点を選択することは、
確率分布を第1の複数の点に適合させること、
目標分布の決定であって、前記目標分布は1個以上の特徴点へのプローブの所望の配置を示すことである、前記決定、並びに、
少なくとも一部は 提案されたプローブサイトでの適合された分布と目標分布と相対的確率を利用することによってプローブの配置を決定すること、
を含む、請求項1に記載のシステム。
【請求項１５】
特徴点分布を決定することは、混合モデルを包含する確率分布に複数の特徴点を適合させることを含んでおり、この確率分布は複数の特徴点で測定された少なくとも1つの配向の分布を示している、請求項14に記載のシステム。
【請求項１６】
更に、プロセッサは、複数の特徴点を少なくとも1つのクラスタにクラスタリングすることによって特徴点分布の混合モデルの多数の成分を決定するように構成されている、請求項14に記載のシステム。
【請求項１７】
更に、プロセッサは、
第1の複数の特徴点から1つ以上の地平点を特定し、
1つ以上の地平点を考慮から除外して第2の複数の特徴点が 1つ以上の地平点を包含しないように構成されている、請求項1に記載のシステム。
【請求項１８】
第2の複数の特徴点を選択することは、モンテカルロ 技術を用いることを含む、請求項1に記載のシステム。
【請求項１９】
3D実行時画像内のトレーニングされた3Dモデル画像のポーズを推定するための3Dアライメントシステムの内部で、実行時3D画像の3Dアライメントポーズを評価するために使用される3次元（3D）プローブの配置を選択するための方法であって、
当該方法は3D画像から第1の複数の特徴点と関連付けられる複数の特徴を生成することを有し、ここで各 特徴は複数の特徴点から関連付けられる点の3D特性を示すデータを含んでおり、
当該方法は少なくとも一部は第1の複数の特徴点と関連付けられる複数の特徴に基づいて第1の複数の特徴点の中から第2の複数の特徴点を選択することを有し、さらに
当該方法は少なくとも一部は第2の複数の特徴点に基づいて複数の3Dプローブの配置を決定することを含む、
方法。
【請求項２０】
少なくとも1並進自由度でのアライメントのために、複数の特徴の各々が第1の複数の点の中から関連付けられる点の少なくとも1つの有用性の測定値を包含する、請求項19に記載の方法。
【請求項２１】
少なくとも1回転自由度でのアライメントのために、複数の特徴の各々が第1の複数の点の中から関連付けられる点の少なくとも1つの有用性の測定値を包含する、請求項19に記載の方法、
【請求項２２】
複数の3Dプローブの配置は、第1の複数の特徴点の各々への配置によって提供されるより大きい3並進自由度での集合アライメント能力を提供する、請求項19に記載の方法。
【請求項２３】
複数の3Dプローブの配置は、第1の複数の特徴点の各々への配置によって提供されるより大きい3並進自由度での集合アライメントを提供し、このより大きい集合アライメント能力は、第1の複数の点の最も小さく表された回転自由度での集合アライメント能力の増加を含む、請求項19に記載の方法。
【請求項２４】
複数の3Dプローブの配置は、第1の複数の特徴点の各々への配置によって提供されるより大きい3回転自由度での集合アライメント能力を提供する、請求項19に記載の方法。
【請求項２５】
複数の3Dプローブの配置は、第1の複数の点の最も小さく表された回転自由度での集合アライメント能力の増加を提供する、請求項19に記載の方法。
【請求項２６】
第1の複数の点のサブセットに適合する回転の中心及び回転軸は、回転の中心及び回転軸がパターンの回転対称特徴と関連するように決定される、請求項19に記載の方法。
【請求項２７】
第1の複数の点のサブセットから回転の中心及び回転軸を見出すことは、RANSAC技術を用いることを含む、請求項26に記載の方法。
【請求項２８】
複数の特徴は、複数の面法線 ベクトルを含んでいる、請求項19に記載の方法。
【請求項２９】
複数の特徴は、複数のエッジ近接ベクトルを含んでいる、請求項19に記載のシステム。
【請求項３０】
複数の特徴は、複数のエッジ方向ベクトルを含んでいる、請求項19に記載の方法。
【請求項３１】
複数の特徴は、複数の表面湾曲ベクトルを含んでいる、請求項19に記載のシステム。
【請求項３２】
少なくとも一部は第1の複数の特徴点と関連付けられる複数の特徴に基づいて、第1の複数の特徴点の中から第2の複数の特徴点を選択することは、
確率分布を第1の複数の点に適合させること、
目標分布の決定であって、前記目標分布は1個以上の特徴点へのプローブの所望の配置を示すことである、前記決定、及び
少なくとも一部は 提案されたプローブサイトでの適合された分布と目標分布と相対的確率を利用することによってプローブの配置を決定すること、
を含む、請求項19に記載の方法。
【請求項３３】
特徴点分布を決定することは、混合モデルを包含する確率分布に複数の特徴点を適合させることを含んでおり、確率分布は複数の特徴点で測定された少なくとも1つの配向の分布を示している、請求項32に記載の方法。
【請求項３４】
更に、複数の特徴点を少なくとも1つのクラスタにクラスタリングすることによって特徴点分布の混合モデルの多数の成分を決定することを含む、請求項32に記載の方法。
【請求項３５】
更に、第1の複数の特徴点から1つ以上の地平点を特定すること、及び1つ以上の地平点を考慮から除外して第2の複数の特徴点が 1つ以上の地平点を包含しないようにすることを含む、請求項19に記載の方法。
【請求項３６】
第2の複数の特徴点を選択することは、モンテカルロ 技術を用いることを含む、請求項19に記載の方法。
【請求項３７】
非一時的コンピュータ可読媒体であって、3D実行時画像内のトレーニングされた3Dモデル画像のポーズを推定するための3Dアライメントシステムの内部で、実行時3D画像の3Dアライメントポーズを評価するために使用される3次元（3D）プローブの配置を選択するためのシステムと連係する実行可能な命令を有しており、システムに、
3D画像から第1の複数の特徴点と関連付けられる複数の特徴を生成させ、ここで各 特徴は複数の特徴点から関連付けられる点の3D特性を示すデータを含んでおり、
少なくとも一部は第1の複数の特徴点と関連付けられる複数の特徴に基づいて、第1の複数の特徴点の中から第2の複数の特徴点を選択させ、及び
少なくとも一部は第2の複数の特徴点に基づいて複数の3Dプローブの配置を決定させるように動作可能である、非一時的コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示の画像、システム及び方法は、画像処理用途のためのパターンの画像上へのプローブの配置に関する。
【背景技術】
【０００２】
デジタル画像は多くのデバイスによって形成され、多くの実用目的のために使用されている。これらのデバイスは、荷電結合デバイス（CCD）画像 センサ又は 相補型金属酸化膜半導体（CMOS）画像 センサ、線走査センサ、飛点走査装置、電子顕微鏡、コンピュータ断層撮影装置（CT）を含むX線装置、磁気共鳴撮像装置、及び当業者に知られている他のデバイスなどの、可視光又は赤外光で作動する画像センサを有するカメラを含む。実用用途は産業オートメーション、医学診断、様々な軍事、民事及び科学的目的のための衛星撮像、写真処理、偵察及び交通監視、文書処理、並びに他の多くの用途に見出される。
【０００３】
これらの用途に対応するために、様々なデバイスによって形成された画像がマシンビジョンシステムによって解析されて適切な情報が抽出される。実用上かなり重要な解析の1形式は、撮像デバイスの視野内のオブジェクトに対応する画像におけるパターンの位置、配向及びサイズを判定することである。パターン検出方法は、当該方法が半導体製造、電子部品組立、製薬、食品加工、消費財製造及び他の多くでロボット及び他のオートメーション装置の誘導に使用される産業オートメーションにおいて特に重要である。
【０００４】
場合によっては、パターン検出方法は1つ以上のプローブを用いてパターンをモデル化できる。プローブは、パターン検出方法が画像の勾配ベクトルを調べる画像内の位置を指すことができる。それゆえ、各プローブ は位置 ベクトル及び 配向 ベクトルと関連付けることができる。プローブは画像内のパターンの位置と配向を効果的に示すことができるので、マシンビジョンシステムはプローブを使用してパターンの位置と配向をアライメントすることができる。
【発明の概要】
【０００５】
幾つかの実施形態 は、3D実行時画像内のトレーニングされた3Dモデル画像のポーズを推定するための3Dアライメントシステムの内部で、実行時3D画像の3Dアライメントポーズを評価するために使用される3次元（3D）プローブの配置を選択するためのシステムを含む。システムはメモリと通信するプロセッサを有しており、プロセッサはメモリに保存されたコンピュータプログラムを実行するように構成されている。コンピュータプログラムは、3D画像から第1の複数の特徴点と関連付けられる複数の特徴を生成し、ここで各 特徴は複数の特徴点から関連付けられる点の3D特性を示すデータを含んでおり、少なくとも一部は第1の複数の特徴点と関連付けられる複数の特徴に基づいて第1の複数の特徴点の中から第2の複数の特徴点を選択し、及び少なくとも一部は第2の複数の特徴点に基づいて複数の3Dプローブの配置を決定するように構成されている。
【０００６】
幾つかの実施形態では、少なくとも1並進自由度でのアライメントのために、複数の特徴の各々が第1の複数の点の中から関連付けられる点の少なくとも1つの有用性の測定値を包含する。幾つかの実施形態では、少なくとも1回転自由度でのアライメントのために、複数の特徴の各々が第1の複数の点の中から関連付けられる点の少なくとも1つの有用性の測定値を包含する。幾つかの実施形態では、複数の3Dプローブの配置は、第1の複数の特徴点の各々への配置によって提供されるより大きい3並進自由度での集合アライメント能力を提供する。幾つかの実施形態では、複数の3Dプローブの配置は、第1の複数の特徴点の各々への配置によって提供されるより大きい3並進自由度での集合アライメントを提供し、このより大きい集合アライメント能力は、第1の複数の点の最も小さく表された回転自由度での集合アライメント能力の増加を含む。幾つかの実施形態では、複数の3Dプローブの配置は、第1の複数の特徴点の各々への配置によって提供されるより大きい3回転自由度での集合アライメント能力を提供する。幾つかの実施形態では、複数の3Dプローブの配置は、第1の複数の点の最も小さく表された回転自由度での集合アライメント能力の増加を提供する。
【０００７】
幾つかの実施形態では、第1の複数の点のサブセットに適合する回転の中心及び回転軸は、回転の中心及び回転軸がパターンの回転対称特徴と関連するように決定される。幾つかの実施形態では、第1の複数の点のサブセットから回転の中心及び回転軸を見出すことはRANSAC技術を用いることを含む。幾つかの実施形態では、複数の特徴は、複数の面法線 ベクトルを含んでいる。幾つかの実施形態では、複数の特徴は、複数のエッジ近接ベクトルを含んでいる。幾つかの実施形態では、複数の特徴は、複数のエッジ方向ベクトルを含んでいる。幾つかの実施形態では、複数の特徴は、複数の表面湾曲ベクトルを含んでいる。
【０００８】
幾つかの実施形態では、少なくとも一部は第1の複数の特徴点と関連付けられる複数の特徴に基づいて、第1の複数の特徴点の中から第2の複数の特徴点を選択することは、確率分布を第1の複数の点に適合させること、目標分布を決定すること、ここで 目標分布は1個以上の特徴点へのプローブの所望の配置を示しており、及び少なくとも一部は 提案されたプローブサイトでの適合された分布と目標分布と相対的確率を利用することによってプローブの配置を決定することを含む。幾つかの実施形態では、特徴点分布を決定することは、混合モデルを包含する確率分布に複数の特徴点を適合させることを含んでおり、確率分布は複数の特徴点で測定された少なくとも1つの配向の分布を示している。幾つかの実施形態では、プロセッサは更に複数の特徴点を少なくとも1つのクラスタにクラスタリングすることによって特徴点分布の混合モデルの多数の成分を決定するように構成されている。幾つかの実施形態では、プロセッサは更に、第1の複数の特徴点から1つ以上の地平点を特定し、及び1つ以上の地平点を考慮から除外して第2の複数の特徴点が 1つ以上の地平点を包含しないように構成されている。幾つかの実施形態では、第2の複数の特徴点を選択することは、モンテカルロ 技術を用いることを含む。
【０００９】
幾つかの実施形態を含む3D実行時画像内のトレーニングされた3Dモデル画像のポーズを推定するための3Dアライメントシステムの内部で、実行時3D画像の3Dアライメントポーズを評価するために使用される3次元（3D）プローブの配置を選択するための方法を含んでいる。この方法は、3D画像から第1の複数の特徴点と関連付けられる複数の特徴を生成すること、ここで各 特徴は複数の特徴点から関連付けられる点の3D特性を示すデータを含んでおり、少なくとも一部は第1の複数の特徴点と関連付けられる複数の特徴に基づいて、第1の複数の特徴点の中から第2の複数の特徴点を選択すること、及び少なくとも一部は第2の複数の特徴点に基づいて複数の3Dプローブの配置を決定することを含んでいる。
【００１０】
幾つかの実施形態では、少なくとも1並進自由度でのアライメントのために、複数の特徴の各々が第1の複数の点の中から関連付けられる点の少なくとも1つの有用性の測定値を包含する。 幾つかの実施形態では、少なくとも1回転自由度でのアライメントのために、複数の特徴の各々が第1の複数の点の中から関連付けられる点の少なくとも1つの有用性の測定値を包含する。 幾つかの実施形態では、複数の3Dプローブの配置は、第1の複数の特徴点の各々への配置によって提供されるより大きい3並進自由度での集合アライメント能力を提供する。 幾つかの実施形態では、複数の3Dプローブの配置は、第1の複数の特徴点の各々への配置によって提供されるより大きい3並進自由度での集合アライメントを提供し、このより大きい集合アライメント能力は、第1の複数の点の最も小さく表された回転自由度での集合アライメント能力の増加を含む。
【００１１】
幾つかの実施形態では、複数の3Dプローブの配置は、第1の複数の特徴点の各々への配置によって提供されるより大きい3回転自由度での集合アライメント能力を提供する。 幾つかの実施形態では、複数の3Dプローブの配置は、第1の複数の点の最も小さく表された回転自由度での集合アライメント能力の増加を提供する。幾つかの実施形態では、第1の複数の点のサブセットに適合する回転の中心及び回転軸は、回転の中心及び回転軸がパターンの回転対称特徴と関連するように決定される。幾つかの実施形態では、第1の複数の点のサブセットから回転の中心及び回転軸を見出すことはRANSAC技術を用いることを含む。幾つかの実施形態では、複数の特徴は、複数の面法線 ベクトルを含んでいる。幾つかの実施形態では、複数の特徴は、複数のエッジ近接ベクトルを含んでいる。幾つかの実施形態では、複数の特徴は、複数のエッジ方向ベクトルを含んでいる。幾つかの実施形態では、複数の特徴は、複数の表面湾曲ベクトルを含んでいる。
【００１２】
幾つかの実施形態では、少なくとも一部は第1の複数の特徴点と関連付けられる複数の特徴に基づいて、第1の複数の特徴点の中から第2の複数の特徴点を選択することは、確率分布を第1の複数の点に適合させること、目標分布を決定すること、ここで 目標分布は1個以上の特徴点へのプローブの所望の配置を示しており、及び少なくとも一部は 提案されたプローブサイトでの適合された分布と目標分布と相対的確率を利用することによってプローブの配置を決定することを含む。幾つかの実施形態では、特徴点分布を決定することは、混合モデルを包含する確率分布に複数の特徴点を適合させることを含んでおり、この確率分布は複数の特徴点で測定された少なくとも1つの配向の分布を示している。幾つかの実施形態では、方法は 更に 複数の特徴点を少なくとも1つのクラスタにクラスタリングすることによって特徴点分布の混合モデルの多数の成分を決定するように構成されている。幾つかの実施形態では、方法は更に、第1の複数の特徴点から1つ以上の地平点を特定すること、及び1つ以上の地平点を考慮から除外して第2の複数の特徴点が 1つ以上の地平点を包含しないようにすることを含む。幾つかの実施形態では、第2の複数の特徴点を選択することは、モンテカルロ 技術を用いることを含む。
【００１３】
幾つかの実施形態は、非一時的コンピュータ可読媒体が、3D実行時画像内のトレーニングされた3Dモデル画像のポーズを推定するための3Dアライメントシステムの内部で、実行時3D画像の3Dアライメントポーズを評価するために使用される3次元（3D）プローブの配置を選択するためのシステムと連係する実行可能な命令を有する。 実行可能な命令 はシステムに、3D画像から第1の複数の特徴点と関連付けられる複数の特徴を生成させ、ここで各 特徴は複数の特徴点から関連付けられる点の3D特性を示すデータを含んでおり、少なくとも一部は第1の複数の特徴点と関連付けられる複数の特徴に基づいて、第1の複数の特徴点の中から第2の複数の特徴点を選択させ、及び少なくとも一部は第2の複数の特徴点に基づいて複数の3Dプローブの配置を決定させるように動作可能である。
【００１４】
以上、開示の主題の特徴をややおおまかに述べたのは、以下に続く詳細な説明においてそれらがより良く理解されるように、また当該技術分野に対する本発明の寄与がより適切に評価されるようにするためである。以下に説明する 開示の主題の追加の特徴があり、それらが本明細書に添付される特許請求の範囲の主題を形成することは言うまでもない。本明細書で 用いられる言い回し及び用語は説明を目的としたものと理解すべきであり、限定するものとして捉えられてはならない。
【００１５】
開示された 主題の種々のオブジェクト、特徴及び利点は以下の詳細な説明を参照して、以下の図面と関連付けて考察するならばより完全に認識できる。図面において同じ参照番号は同じ要素を表わしている。
【図面の簡単な説明】
【００１６】
【図１】細長い矩形形状を有する2D パターンと、このパターン上に均等に配置されたプローブを図示している。
【００１７】
【図２】幾つかの実施形態による、2D画像の特徴点上にプローブを配置するための高レベルプロセスを図示している。
【００１８】
【図３】幾つかの実施形態による、垂直配向のヒストグラムを均等な 分布 に整合させることによってプローブを配置した結果を図示している。
【００１９】
【図４】幾つかの実施形態による、プローブ配置モジュールを含むコンピューティングデバイスを図示している。
【００２０】
【図５】幾つかの実施形態による、画像の特徴点に対する垂直配向のヒストグラムを決定するためのプロセスを図示している。
【００２１】
【図６Ａ】幾つかの実施形態による、垂直配向のヒストグラムを生成するためのプロセスを図示している。
【図６Ｂ】幾つかの実施形態による、垂直配向のヒストグラムを生成するためのプロセスを図示している。
【図６Ｃ】幾つかの実施形態による、垂直配向のヒストグラムを生成するためのプロセスを図示している。
【図６Ｄ】幾つかの実施形態による、垂直配向のヒストグラムを生成するためのプロセスを図示している。
【図６Ｅ】幾つかの実施形態による、垂直配向のヒストグラムを生成するためのプロセスを図示している。
【図６Ｆ】幾つかの実施形態による、垂直配向のヒストグラムを生成するためのプロセスを図示している。
【図６Ｇ】幾つかの実施形態による、垂直配向のヒストグラムを生成するためのプロセスを図示している。
【図６Ｈ】幾つかの実施形態による、垂直配向のヒストグラムを生成するためのプロセスを図示している。
【００２２】
【図７】幾つかの実施形態による、プローブ配置を決定するためのプロセスを図示している。
【００２３】
【図８】幾つかの実施形態による、2D画像の特徴点と関連付けられる弧の長さのスケーリングを図示している。
【００２４】
【図９】幾つかの実施形態による、スケーリングされた特徴点上のプローブの均等な配置を図示している。
【００２５】
【図１０】幾つかの実施形態による、特徴点と関連付けられるスケーリングされた弧の長さの逆 スケーリングを図示している。
【００２６】
【図１１Ａ】幾つかの実施形態による、目標分布からプローブをサンプリングすることによってプローブのバランスを取ることを図示している。
【図１１Ｂ】幾つかの実施形態による、目標分布からプローブをサンプリングすることによってプローブのバランスを取ることを図示している。
【００２７】
【図１２Ａ】幾つかの実施形態による、基準ベクトルと単位法線ベクトルとの関係を図示している。
【００２８】
【図１２Ｂ】幾つかの実施形態による、位置 ベクトルｖｉと単位回転 ベクトルuθｉとの関係を図示している。
【００２９】
【図１３】幾つかの実施形態による、プローブのサンプリングプロセスを要約している。
【００３０】
【図１４Ａ】幾つかの実施形態による、図13に示すプロセスを使用した矩形上へのプローブの配置を図示している。
【００３１】
【図１４Ｂ】幾つかの実施形態による、図13に示すプロセスを使用したレバーアームを有する円形 オブジェクト上へのプローブの配置を図示している。
【００３２】
【図１５Ａ】幾つかの実施形態による、図13に示すプロセスを使用した矩形上へのプローブの配置を図示している 。
【００３３】
【図１５Ｂ】幾つかの実施形態による、図13に示すプロセスを使用したレバーアームを有する円形オブジェクト上へのプローブの配置を図示している。
【００３４】
【図１６Ａ】幾つかの実施形態による、図13に示すプロセスを使用した穴を有するパターン上へのプローブの配置を図示している。
【図１６Ｂ】幾つかの実施形態による、図13に示すプロセスを使用した穴を有するパターン上へのプローブの配置を図示している。
【００３５】
【図１７Ａ】幾つかの実施形態による、回転変数 θの表示がどのようにプローブ配置を変化させるかを図示している。
【図１７Ｂ】幾つかの実施形態による、回転変数 θの表示がどのようにプローブ配置を変化させるかを図示している。
【図１７Ｃ】幾つかの実施形態による、回転変数 θの表示がどのようにプローブ配置を変化させるかを図示している。
【００３６】
【図１８Ａ】幾つかの実施形態による、図13に示すプロセスを使用した細長いアームを有するパターン上へのプローブの配置を図示している。
【図１８Ｂ】幾つかの実施形態による、図13に示すプロセスを使用した細長いアームを有するパターン上へのプローブの配置を図示している。
【００３７】
【図１９】幾つかの実施形態による、長い不規則な パイプ 形状と3D パターン上に均等に配置された3Dプローブを有する3Dパターンを図示している。
【００３８】
【図２０】幾つかの実施形態による、3D画像内の特徴点上に3Dプローブを配置するための高レベルプロセスを図示している。
【００３９】
【図２１Ａ】幾つかの実施形態による、特徴生成プロセスを図示している。
【図２１Ｂ】幾つかの実施形態による、特徴生成プロセスを図示している。
【００４０】
【図２２】幾つかの実施形態による、ピクセルグリッドに正則化された深度マップを図示している。
【００４１】
【図２３Ａ】幾つかの実施形態による、単位正方形から最も近い（任意に離間した）4つの周囲の点への双線形マッピングとこのマッピングの逆を図示しており、ここでピクセルグリッド中心点は単位正方形内に配置されている。
【図２３Ｂ】幾つかの実施形態による、主軸の角度を図示している。
【００４２】
【図２４】幾つかの実施形態による、長軸と短軸に沿って規則的に離間したサンプリングを図示している。
【００４３】
【図２５】幾つかの実施形態による、特徴 生成プロセスの結果を図示している。
【００４４】
【図２６】幾つかの実施形態による、ポイントクラウド 内ですべての面法線 ベクトルの回転のモーメントを最小化する点を図示している 。
【００４５】
【図２７】幾つかの実施形態による、回転の軸を見出すためにRANSAC アルゴリズムが使用されるオブジェクトの例を図示している。
【００４６】
【図２８Ａ】幾つかの実施形態による、地平点除去のないプローブ配置を図示する。
【図２８Ｂ】地平点除去のあるプローブ配置を図示している。
【００４７】
【図２９】幾つかの実施形態による、θpiの計算するのに関係のある ベクトルを示しており、これはｕｉ０、ｕｉ１及びｕｉ２を回転単位 ベクトル^ｕｉθｐに投影した合計の大きさと見なされる。
【００４８】
【図３０Ａ】幾つかの実施形態による、バイアスが適用されないプローブの例を示す。
【図３０Ｂ】空間的バイアスが適用されるプローブの例を示す。
【図３０Ｃ】回転バイアスが適用されるプローブの例を示している。
【００４９】
【図３１Ａ】点とそれらの分解能の例を図示している。
【図３１Ｂ】Clim= 2でのプローブ 選択の結果の例を示す。
【図３１Ｃ】Clim= 4でのプローブ 選択の結果の例を示す。
【図３１Ｄ】Clim= 8でのプローブ 選択の結果の例を示している。
【発明を実施するための形態】
【００５０】
以下の説明において、開示の主題の完全な理解を提供するために、開示の主題のシステム及び方法、並びにそのような システム及び方法が作用できる環境に関して多数の具体的な詳細を記載する。しかしながら、開示の主題 はそのような 具体的な詳細がなくとも実施できること、及び当該技術分野で周知の幾つかの特徴は 開示の主題を複雑にするのを避けるために記載されていないことは、当業者にとって明白であろう。加えて、以下に提供される例は 例示的なものであり、開示の主題の範囲内にある他のシステム及び方法 が存在することが想定されていることが理解されよう。
【００５１】
詳細な説明は、概して次のような編成とする。詳細な記述は、概して 2次元画像に関係する例示的な 実施形態を記すことによって始める。幾つかの例示的な 2次元 技術は、例えば2015年1月23日に出願された「画像処理のためのプローブ配置」と題する米国特許出願第14/603969号において説明されており、その全教示内容は参照により本明細書に組み込まれる。次いで 詳細な説明は、概して3次元 画像に関係する例示的な 実施形態を記述する。第1の部分は 概して2次元画像を包含する例示的な 実施形態に関係し、第2の部分は 概して3次元 画像を包含する例示的な 実施形態に関係するが、当業者は一方の部分における 開示は他方の部分における開示に適用可能であり、その逆でもあることを認識するであろう。加えて、当業者は幾つかの例示的な 実施形態 は 両 部分の教示に依拠することを認識するであろう。例えば 幾つかの例示的な 実施形態では、システム及び方法は 2次元画像と3次元 画像の両方を使用する。加えて、当業者は3D ケースにも適用可能な第1の部分 からの教示 は不必要な繰返しを避けるために第2のセクション では必ずしも詳記されず、その逆でもあることを認識するであろう。言い換えれば、詳細な説明は編成の目的と理解を容易にするために概して2次元のケースと3次元のケースに分割されるが、この編成は開示の限定を意図したものではない。 
【００５２】
以下に1つ以上の実施形態に従い、用語の例示的な 説明を掲げる。これらの説明 は、限定を意図したものではない。
【００５３】
オブジェクト−画像形成装置によって測定できるか、データ処理装置によってシミュレートできる特性を有する任意の物理的オブジェクト又はシミュレートされた オブジェクト又はその部分。
【００５４】
画像−2D 画像は、その値が明るさ（放射エネルギー又はそうでない場合は反射エネルギー）、色、温度、基準面（例えばレンジ画像）からの高さなどのオブジェクトの物理的特性に対応し、任意の画像形成装置によって測定されるか、その値がオブジェクトのシミュレートされた 特性に対応し、任意のデータ処理装置によって生成され2次元関数である。3D画像は、例えばレンジ画像又はポイントクラウドとして表示され得る。 ポイントクラウドは、各点ｉが（xi、yi、zi）として表わされ得る空間における3D点の集合である。
【００５５】
境界−端部が開いているか閉じている、直線又は曲線の、平滑又は鋭利な仮想の輪郭であって、それに沿って特定の粒状度で画像の明るさの不連続 が生じるもの。当該不連続の方向は、各点において境界に対して垂直である。
【００５６】
勾配−画像内の与えられた 点 におけるベクトルで、当該点における特定の粒状度での明るさの最大の変化方向及び大きさを与えるもの。
【００５７】
パターン− 輪郭の平面の境界が付けられたサブセット内にある輪郭の特定の幾何学的配置であり、当該 輪郭は位置が特定され及び/又は 検査されるオブジェクトの理想的な画像の境界を表わす。 3D パターンは、例えばレンジ画像内の輪郭の配置又はポイントクラウドとして表示され得る。
【００５８】
モデル−パターン発見方法による使用のために見出されるパターンのデータ符号化特性のセット。
【００５９】
トレーニング−モデル例示オブジェクトの画像から又はオブジェクト若しくはパターンの幾何学的記述から創成するプロセス。
【００６０】
マシンビジョンシステム は、画像内における所定のパターンの1つ以上のインスタンスの有無を決定し、且つ見出された 各インスタンスの位置を決定するように構成できる。2D画像内で パターンの位置を特定するプロセスは、x-y 位置（並進とも呼ぶ）、配向及びサイズを含むがこれに限定されない多次元空間内で生じる。3D画像については、位置の特定は例えば x-y-z 位置（並進とも呼ぶ）、傾きと回転（ロール、ピッチ及びヨーとも呼ぶ）を含むことができる。
【００６１】
画像内における所定のパターンの1つ以上のインスタンスの有無を決定するために、マシンビジョンシステムは、モデルを使用して見出されたパターンを表示することができる。 マシンビジョンシステムは、1つ以上のトレーニング画像から、又は位置が特定 され及び/又は 検査されるパターンの例を包含する幾何学的記述から合成される1つ以上の画像からパターン用のモデルを生成することができる。モデルが利用可能になると、マシンビジョンシステムはモデルをポーズの適切なセットの各々におけるテスト画像と比較して、各ポーズでの整合 スコアを計算することができ、整合スコアにおける極大値 に対応する候補 ポーズを決定できる。マシンビジョンシステムは、整合スコアが適当な閾値を超える、画像内のパターンのインスタンスとなるべき候補 ポーズを考慮することができる。
【００６２】
モデルはプローブと呼ばれるデータ要素のセットを含むことができる。各プローブ は、画像内の与えられたポーズで特定の測定及びテストが行われる相対的位置を表わし、そのようなテストは各々関連する ポーズでパターン が存在することの証明に寄与する。プローブ は、基礎をなすパターンの構造（例えば境界）に対して実質的に垂直になるようにすることができる。
【００６３】
トレーニング段階で、既存のマシンビジョンシステムが2Dパターンの境界上にプローブを均等に配置する。例えばマシンビジョンシステムは、隣接するプローブ間の距離がすべての隣接するプローブ対についてほぼ同一になるように、パターンの境界上にプローブを配置する。本明細書において「均等配置法」と称するこの方法は、バランスが取れた配向プロファイル（例えば多数の配向を指し示す境界を有する2Dパターンと、様々な配向を指し示す境界の割合が同様である）を有するパターンをモデル化する際に効果的であり得る。例えば均等配置法は正方形のパターンのモデル化に有用であるが、その理由は異なる配向を指し示す（例えば上、下、左、右）プローブの数が2D画像内のパターンの各エッジ上でほぼ同じであり、それは2Dパターンの位置及び配向の正確な情報につながることができるからである。
【００６４】
あいにく均等配置法は、バランスが取れていない配向プロファイルを有するパターン（例えば様々な辺の長さを有するパターン）のモデル化にはしばしば効果的ではない。例えば均等配置法は通常細長い矩形形状のパターンをアライメントするにはそれほど効果的ではない。図1は、細長い矩形形状を有する2Dパターンと、このパターン上に均等に配置されたプローブを示す。境界102が細長い矩形形状を有しているので、均等配置法ではほとんどのプローブ104が境界の長いエッジ106上に配置され、少数のプローブ104のみが境界の短いエッジ108上に配置されるであろう。境界の短いエッジ108に沿うプローブの数が少ないので、プローブに基づいて短いエッジ108が存在するか決定するのは困難である。更に、短いエッジ108が存在することを決定できる場合でも、短いエッジ108の位置を符号化するプローブ104の数が少ないので、短いエッジ108の位置を正確に指し示すことは困難である。このことは例えば境界102が他の2Dパターンに対して水平にアライメントするのに問題になり得る。
【００６５】
均等配置法と関連する問題に対処するために、隣接するプローブ間の距離を変化させる努力がなされてきた。しかしながらこの努力は手作業でのプローブ位置の調整に制限され、このことは手間がかかり且つ高価となり得る。
【００６６】
本明細書に記載される技術は、パターン（2Dパターンと3Dパターンの両方）上にプローブを配置するための自動化されたプローブ配置モジュールを提供する。このプローブ配置モジュールは、プローブが画像に示されるパターンを正確に表わすことができるように、画像の特徴点上にプローブを配置するように構成される。このプローブ配置モジュールは、プローブがパターンの動きと関連するすべての自由度でバランスの取れた情報を抽出できるように、プローブを配置するように構成することができ、それによってプローブから生成されるモデルの精度が向上する。例えばパターンに関連付けられるオブジェクトが2次元で移動する（例えば並進移動）ことが知られている場合、プローブ配置モジュールは、プローブが2次元（2Dパターン及び画像を前提）のバランスの取れた情報を抽出できるように、プローブを配置することができる。プローブ配置モジュールはまた、プローブがパターンの形状にかかわらずバランスの取れた情報を抽出できるようにパターンの形状を考慮することができる。このことは、図1に示すように短いエッジに比べてより多くのプローブが長いエッジに配置される場合に、水平方向の情報に比べてより多くの垂直方向の情報を抽出するようなバランスの取れない情報を抽出する技術とは対照的である。
【００６７】
図2は、幾つかの実施形態による、2D画像内の特徴点上にプローブを配置するための高レベルプロセスを示す。特徴点は、プローブに対する候補位置を示すことができる。例えばプローブ配置モジュールは、画像内の特徴点のサブセットを選択し、選択された特徴点のサブセット上にプローブを配置するように構成され得る。
【００６８】
ステップ202で、プローブ配置モジュールは、画像内の特徴点の位置に関する情報を受信するように構成され得る。例えばプローブ配置モジュールは、特徴点検出モジュールから2D画像内の2Dパターンの境界を受信することができる。 
【００６９】
ステップ204で、プローブ配置モジュールは特徴点の分布を決定できる。例えばプローブ配置モジュールは、特徴（例えば特徴点で測定される垂直配向）を使用して各特徴点を表示し、特徴点に関連付けられる特徴の分布を決定することができる。
【００７０】
ステップ206で、プローブ配置モジュールはプローブの目標分布を決定することができる。場合によっては、プローブの目標分布は、特徴点に関連付けられる特徴及び/又はステップ204で決定された特徴点の分布に基づいて決定できる。例えばプローブ配置モジュールは、プローブの目標分布がステップ204で決定された特徴点の分布とは逆であると決定することができる。ステップ208で、プローブ配置モジュールはプローブの実際の分布がプローブの目標分布に整合するようにプローブの位置を決定できる。
【００７１】
図2に示された概略的なフレームワークは、例えば少なくとも2つの機構を（例えば単独で及び/又は互いに組み合せて）使用して実施され得る。第1の機構では、開示のプローブ配置モジュールは、プローブ位置で測定された垂直配向の分布がバランスを取るように（例えばプローブ位置での垂直配向のヒストグラムがほぼ均等）、プローブを配置するように構成され得る。第1の機構は、2自由度（例えば並進移動）を有するパターンのモデル化に特に有用であり得る。
【００７２】
例えばステップ204で、プローブ配置モジュールは2D画像内の複数の特徴点で測定された垂直配向のヒストグラムを決定できる。ステップ206で、プローブ配置モジュールは、プローブ位置で測定された垂直配向の目標分布が均等な分布であることを決定できる。ステップ208で、プローブ配置モジュールは配置されたプローブによって測定された垂直配向のヒストグラムが均等な分布に近くなるように、1個以上の特徴点上にプローブを配置することができる。
【００７３】
図3は、幾つかの実施形態による、垂直配向のヒストグラムを均等な分布と整合させることによってプローブを配置した結果を示す。この例では、特徴点は全体として2Dパターンの境界102を形成することができる。境界102が細長い矩形形状を有する場合、プローブ配置モジュールは長いエッジ106上のプローブの数が短いエッジ108上のプローブの数と比べてほぼ同じになるように、長いエッジ106上のプローブ104の数を減らし、短いエッジ108上のプローブの数を増やすことができる。このようにして配置されたプローブ104の配向分布のバランスを取ることができる。本明細書を通して第1の機構を実施するプローブ配置モジュールを、特に図5〜図10を参照して説明する。
【００７４】
第2の機構では、プローブ配置モジュールはプローブの分布が目標分布と実質的に同様になるように、プローブの位置を決定できる。ステップ204で、プローブ配置モジュールはパターンの自由度に対応する変数を使用して特徴点を表示することができる。例えば2Dパターンに関連付けられるオブジェクトが2次元で移動することが知られている場合、プローブ配置モジュールは特徴点における2次元の勾配ベクトルを使用して特徴点を表示することができる。次いでプローブ配置モジュールは、特徴点に関連付けられる垂直配向の分布をモデル化することによって特徴点の分布を決定できる。
【００７５】
ステップ206で、プローブ配置モジュールは、特徴点に関連付けられる特徴に基づき所望の目標分布を決定できる。例えばプローブ配置モジュールは、複数の特徴点で測定された垂直配向に基づき所望の目標分布を決定できる。より具体的には、プローブ配置モジュールは、所望の目標分布が特徴点で測定された垂直配向の分布の逆であると決定できる。同様に、プローブ配置モジュールは特徴点で測定された回転ベクトル及びスケール情報を考慮して目標分布を決定できる。続いてステップ208で、プローブ配置モジュールは目標分布からサンプリングすることによって、1個以上の特徴点上にプローブを配置することができる。本明細書を通して第2の機構を、特に図11〜図18を参照して説明する。
【００７６】
図4は、幾つかの実施形態による、プローブ配置モジュールを含むコンピューティングデバイスを示す。コンピューティングデバイス400は、プロセッサ402、メモリ404、特徴点検出（IPD）モジュール406、プローブ配置モジュール408及びインタンク410を含むことができる。
【００７７】
幾つかの実施形態では、プロセッサ402は、命令、並びに命令及び/又はデータを保存するための1つ以上のメモリデバイス404を実行することができる。メモリデバイス404は、ダイナミックランダムアクセスメモリ（DRAM）、スタティックランダムアクセスメモリ（SRAM）、フラッシュメモリ、磁気ディスクドライブ、光学ドライブ、プログラム可能なリードオンリーメモリ（PROM）、リードオンリーメモリ（ROM）、又は他の任意のメモリ若しくはメモリの組合せなどの非一時的コンピュータ可読媒体であることができる。メモリデバイス404は、一時的にデータを保存するのに使用することができる。メモリデバイス404は長期間のデータ保存にも使用できる。プロセッサ402及びメモリデバイス404は、特定の目的の論理回路により補足でき及び/又は特定の目的の論理回路に組み込むことができる。
【００７８】
幾つかの実施形態では、IPDモジュール406は入力画像から特徴点を検出するように構成され得る。例えばIPDモジュール406は、インタフェース410を介して、IPDモジュール406と通信するカメラモジュール又は他のコンピューティングデバイスなどの別のデバイスから画像を受信することができる。続いてIPDモジュール406は、画像処理操作を行って特徴点を検出することができる。
【００７９】
幾つかの実施形態では、特徴点は2Dパターンのエッジ、2Dパターンの境界（例えばエッジの連鎖）、テクスチャ境界、勾配の大きさが大きいピクセル、隣接するピクセルとの明度差が大きいピクセル、隣接するピクセルとの色差が大きいピクセル、スケール不変特徴変換（SIFT）の特徴点、隣接するピクセルから明確に判別できる任意のピクセル、又はその任意の組合せを含むことができる。それゆえIPDモジュール406は、エッジ検出操作を実行して2Dパターンの境界を形成するエッジのセットを決定し、差別化操作を実行して勾配の大きさが大きいピクセルを検出し、SIFTオペレータを実行してSIFT特徴点を検出し、又はそれらの任意の組合せを実行するように構成され得る。
【００８０】
幾つかの実施形態では、基礎構造の勾配配向を決定することによって垂直配向を決定することができる。例えば基礎パターンの勾配ベクトルは特徴点において決定でき、勾配ベクトルに関連付けられる配向を決定することができる。別の場合では、垂直配向は単純な計算で決定することができる。例えば構造の境界上の2点を取ることができ、この2点を結ぶ線を決定することができる。この線に垂直な配向を垂直配向と決定することができる。別の場合では、構造の垂直配向は他のコンピュータモジュール、例えばコンピュータ支援設計（CAD）モデル化モジュールから受信された情報に基づいて決定することができる。
【００８１】
幾つかの実施形態では、プローブ配置モジュール408 は、画像内の特徴点に基づいてプローブの位置を決定するように構成され得る。プローブ配置モジュール408 は、目標分布計算（TDC）モジュール412、特徴分布計算（FDC）モジュール414及びプローブ分布整合（PDM）モジュール416を含むことができる。TDCモジュール412は、1個以上の特徴点に配置されるプローブの目標分布を決定することができる。FDCモジュール414は、画像内の特徴点の分布を決定することができる。PDMモジュール416は、プローブの分布とプローブの目標分布とが実質的に整合するように、プローブの位置を決定することができる。以下に述べるように、TDCモジュール412が垂直配向のヒストグラムのみを扱う場合、目標分布は均等な分布であり得る。他の実施形態では、プローブ配置モジュール408 は実質的に同様の操作を行うためのモジュールの異なるセットを含んでよい。
【００８２】
幾つかの実施形態では、インタフェース410はハードウェア内で実施されて、光学、チョッパ及び無線など様々な媒体で、並びに一部は非一時的であってよい多数の異なるプロトコル信号を送受信することができる。
【００８３】
幾つかの実施形態では、1つ以上のモジュール406、408、412、414、416は、メモリ404を使用してソフトウェア内で実施され得る。ソフトウェアは、コンピュータの指示又はコンピュータコードを実行可能であるプロセッサ402上で実行することができる。プロセッサ402は、特定用途向け集積回路（ASIC）、プログラマブル論理アレイ（PLA）、デジタルシグナルプロセッサ（DSP）、フィールドプログラマブルゲートアレイ（FPGA）、又は任意の他の集積回路を使用してハードウェア内で実施される。コンピュータプログラムを実行するのに適したプロセッサ402は、例として汎用と特殊用途のマイクロプロセッサ、デジタルシグナルプロセッサ、及び任意の種類のデジタルコンピュータの1つ以上のプロセッサを含む。一般に、プロセッサ402はリードオンリーメモリ若しくはランダムアクセスメモリ又はその両方から命令及びデータを受信する。
【００８４】
幾つかの実施形態では、開示の方法ステップは、コンピュータプログラムを実行する1つ以上のプロセッサ402によって行われて、入力データ上の操作及び/又は出力データの生成により本発明の機能を発揮することができる。1つ以上のモジュール（例えばモジュール406、408、412、414、416）は、ASIC（特定用途向け集積回路）、PLA（プログラマブル論理アレイ）、DSP（デジタルシグナルプロセッサ）、FPGA（フィールドプログラマブルゲートアレイ）、又は他の集積回路を使用して、ハードウェア内で実施され得る。幾つかの実施形態では、2つ以上のモジュール406、408、412、414、416を、ASIC、PLA、DSP、又はFPGAなどの同じ集積回路上で実施でき、それによりチップ上にシステムを形成する。サブルーチンは1つ以上の機能を実施するコンピュータプログラム及び/又はプロセッサ/特定の電子回路の部分に関連することができる。
【００８５】
モジュール406、408、412、414、416は、デジタル電子回路内又はコンピュータのハードウェア、ファームウェア、ソフトウェア若しくはそれらの組合せの中で実施され得る。実施はコンピュータプログラム製品、例えば機械読取り可能な記憶デバイスに明白に埋め込まれたコンピュータプログラムであってよく、これをデータ処理装置、例えばプログラマブルプロセッサ、コンピュータ及び/又は複数のコンピュータによって実行し、又は操作を制御する。コンピュータプログラムはソースコード、コンパイルコード、解釈されたコード及び/又は機械コードを含むコンピュータ又はプログラミング言語の任意の形式で書き込むことができ、またコンピュータプログラムは、スタンドアローンプログラム又はサブルーチンとして、コンピュータ環境での使用に適した要素又は他のユニットを含む任意の形式で展開することができる。コンピュータプログラムは展開して、1つのコンピュータ又は1つ以上の現場の複数のコンピュータ上で実行することができる。
【００８６】
コンピューティングデバイス400は、指示及び/又はデータを装置若しくはネットワークから受信するために、及び/又は指示及び/又はデータを装置若しくはネットワークに送信するために、外部装置、例えばファクトリーオートメーション若しくは物流機器に、或いは通信ネットワーク、例えばファクトリーオートメーション若しくは物流ネットワークに操作可能に接続することができる。コンピュータプログラムの指示及びデータを具体化するのに適したコンピュータ可読記憶デバイスは、すべての形式の揮発性及び非揮発性メモリを含み、これには例としてDRAM、SRAM、EPROM、EEPROM及びフラッシュメモリデバイスなどの半導体メモリデバイス、内蔵ハードディスク又はリムーバブルディスクなどの磁気ディスク、磁気光学ディスク、並びにCD、DVD、HD−DVD及びブルーレイディスクなどの光学ディスクが含まれる。
【００８７】
幾つかの実施形態では、コンピューティングデバイス400はユーザ装置を含むことができる。ユーザ装置は、1つ以上の無線アクセスネットワーク及び有線通信ネットワークと通信することができる。ユーザ装置は携帯電話であってもよい。ユーザ装置はワードプロセッシング、ウェブブラウジング、ゲーミング、電子書籍機能、オペレーティングシステム及びフルキーボードなどのサービスを提供するスマートフォンであってもよい。ユーザ装置は、ネットワークアクセス及びスマートフォンによって提供されるサービスのほとんどを提供するタブレットコンピュータであってもよい。ユーザ装置は、シンビアンOS、iPhone（登録商標）OS、RIMのブラックベリー、ウィンドウズ（登録商標）モバイル、リナックス（登録商標）、HPウェブOS及びアンドロイドなどのオペレーティングシステムを使用して動作する。スクリーンはデータをモバイルデバイスに入力するのに使用されるタッチスクリーンであってよく、その場合はスクリーンはフルキーボードの代わりに使用することができる。ユーザ装置は、全地球測位座標、プロフィール情報又は他の位置情報を保有することもできる。
【００８８】
幾つかの実施形態では、コンピューティングデバイス400はサーバを含むことができる。サーバは、オペレーティングシステム（OS）ソフトウェアを使用して動作することができる。幾つかの実施形態では、OSソフトウェアは、リナックスソフトウェアカーネルをベースとして、タスクの監視及びプロトコルスタックの提供などの特定のアプリケーションをサーバ内で実行する。OSソフトウェアは、制御及びデータパスのためにサーバのリソースを別々に配分することを許容する。例えば特定のパケットアクセラレータカード及びパケットサービスカードがルーチング又はセキュリティコントロール機能の実施に割り当てられる一方、他のパケットアクセラレータカード/パケットサービスカードがユーザのセッショントラフィックの処理に割り当てられる。ネットワークの要求が変化すると、ハードウェアのリソースを動的に展開して、幾つかの実施形態における要求に対処することができる。
【００８９】
第1のプローブ配置機構−プローブの垂直配向のバランスを取る
【００９０】
幾つかの実施形態では、プローブ配置モジュール408 は、プローブ位置で測定された垂直配向のバランスを取るようにプローブを配置するように構成できる。より具体的には、プローブ配置モジュール408 は、プローブの位置で測定された垂直配向のヒストグラムがほぼ均等になるように、2D画像内の1個以上の特徴点にプローブを配置するように構成され得る。このオペレーションモードにより、プローブ配置モジュール408 はオブジェクトのモデルの精度を2自由度で向上させることが可能になる。
【００９１】
幾つかの実施形態では、垂直配向のヒストグラムは、複数の配向ビンを含むことができる。各配向ビンは、配向の所定の範囲に対応することができる。例えば垂直配向のヒストグラムは、180のビンを含むことができ、各配向ビンは2度の角度範囲をカバーすることができる。それゆえ垂直配向のヒストグラムは、特徴点で測定される垂直配向のプロファイルを示すことができる。幾つかの実施形態では、垂直配向のヒストグラムは、連続的な分布として表わすことができる。
【００９２】
幾つかの実施形態では、プローブ配置モジュール408 は、特徴点に関連付けられる垂直配向のヒストグラムを決定するように構成され得る。このためにプローブ配置モジュール408 は、各特徴点に関連付けられる垂直配向を決定することができる。例えばプローブ配置モジュール408 は、IPDモジュール406から各特徴点における垂直配向を表わす情報を受信することができる。別の例として、プローブ配置モジュール408 は、各特徴点に関連付けられる垂直配向を計算することができる。次いで、プローブ配置モジュール408 により、複数の特徴点において測定された垂直配向のヒストグラムを決定することができる。
【００９３】
図5は、幾つかの実施形態による、特徴点の垂直配向のヒストグラムを決定するプロセスを示す。
【００９４】
ステップ502では、IPDモジュール406は、画像内の特徴点を決定することができる。幾つかの実施形態では、特徴点は画像に表される2Dパターンの境界を含むことができる。場合によっては、IPDモジュール406は、エッジ検出技術を用いて2Dパターンの境界を識別することができる。例えばIPDモジュール406は、エッジ検出操作を実施して、エッジに対応すると思われるエッジの点のセットを識別することができる。各点は、位置ベクトル及び基礎をなす構造に対し垂直な垂直ベクトルと関連付けることができる。次いで、IPDモジュール406はエッジ点を連鎖して、2Dパターンの一貫した境界を形成することができる。エッジ検出技術は、例えばキャニーエッジ検出技術又はハフ変換技術を含むことができる。エッジ検出技術は、例えばソーベルオペレータ、キルシュオペレータ、プルウィットオペレータ、ガボアフィルタ、ハールウェーブレットフィルタ、画像内のピクセル値の変化（例えば画像の高周波数成分）を検出できる任意の他のフィルタ及び/又はそれらの任意の組合せを含む1つ以上のエッジ検出オペレータを使用することができる。
【００９５】
他の実施形態では、特徴点はSIFT特徴点を含むことができる。そのような場合、IPDモジュール406はSIFT操作を実施してSIFT特徴点を識別することができる。
【００９６】
幾つかの実施形態では、特徴点をパターンの境界上に均等に配置することができる。例えば任意の2つの隣接する特徴点間の距離をほぼ同一にすることができる。この場合、各特徴点を境界の同じ弧の長さと関連付けられるものと見なすことができる。
【００９７】
少なくとも1個の特徴点が利用可能になると、FDCモジュール414がIPDモジュール406から少なくとも1個の特徴点の位置を受信することができる。それからFDCモジュール414はステップ504〜508を繰り返して、少なくとも1個の特徴点で測定された垂直配向のヒストグラムを生成することができる。
【００９８】
ステップ504で、FDCモジュール414は、少なくとも1個の特徴点の内の1つを選択して、選択された特徴点の垂直配向を決定することができる。幾つかの実施形態では、FDCモジュール414は、IPDモジュール406から垂直配向の情報を受信することができる。他の実施形態では、FDCモジュール414はそれ自体で選択された特徴点での垂直配向を決定することができる。例えばFDCモジュール414は特徴点を伴う勾配オペレータを畳み込んで垂直配向を決定する。勾配オペレータは、ガボアフィルタ、ハールウェーブレットフィルタ、可動フィルタ、x方向勾配フィルタ[−1,0,1]、y方向勾配フィルタ[−1,0,1]T及び/又はそれらの任意の組合せを含むことができる。別の例としては、FDCモジュール414は、例えば特徴点の基礎をなす構造の勾配ベクトルを決定するか、構造の境界上の2つの近い点を結ぶ線の配向を決定することにより、各特徴点に関連付けられる垂直配向を計算する。
【００９９】
ステップ506で、FDCモジュール414は、選択された特徴点での垂直配向の寄与を垂直配向のヒストグラムに追加することができる。このためにFDCモジュール414は、ヒストグラムにおいて、ステップ504で判定された垂直配向に対応する配向ビンを決定することができる。例えば垂直配向がx軸に対して3度である場合、FDCモジュール414は、垂直配向がx軸に対して2度ないし4度の配向をカバーする配向ビン#1と関連付けられると決定することができる。次いで、FDCモジュール414は、垂直配向に関連付けられる配向ビンに票を加えることができる。例えばFDCモジュール414は配向ビンの値を1だけ増やすことができる。別の例としては、FDCモジュール414は配向ビンの値を加重値分だけ増やすことができる。加重値は、特徴点に関連付けられる勾配ベクトルに依存するものであってよい。例えば加重値は勾配ベクトルの大きさに依存してよい。
【０１００】
ステップ508で、FDCモジュール414は、FDCモジュール414が垂直配向のヒストグラムに考慮しなかった特徴点が存在するかどうかを決定することができる。存在する場合、FDCモジュール414はステップ504に戻り、すべての特徴点がFDCモジュール414により考慮されるまでステップ504〜508を繰り返すことができる。FDCモジュール414がすべての特徴点を考慮した場合、FDCモジュール414は垂直配向のヒストグラムを出力することができる。
【０１０１】
図6A〜図6Hは、幾つかの実施形態による、垂直配向のヒストグラムを生成するプロセスを示す。この例では、各矢印602の中心が特徴点と対応するものと見なすことができ、すべての特徴点のセットが境界102を含むものと見なすことができる。図6Aに示すように、FDCモジュール414は、第1の特徴点602Aが0とπ/6の範囲をカバーする配向ビンに関連付けられると決定することができる。それゆえFDCモジュール414は、配向ビンと関連付けられる値を1だけ増やすことができる。図6B〜図6Hに示すように、FDCモジュール414は、境界102上の各特徴点602についてこの操作を実施し、対応する垂直配向のヒストグラム604を生成することができる。
【０１０２】
幾つかの実施形態では、TDCモジュール412は、プローブの目標分布を生成するように構成され得る。プローブの目標分布は、1個以上の特徴点上のプローブの所望の配置を示すことができる。幾つかの実施形態では、目標分布は複数の配向ビンを含むことができ、ここで、各配向ビンは値と関連付けられる。場合によっては、目標分布は均等な分布であることができる。本質的には、均等な目標分布は、特定の配向を示す特徴点上のプローブの数が、別の配向を示す特徴点上のプローブの数と同じになるものであることを示す。この方法により、プローブ配置モジュール408 は、異なる配向を示すプローブの数のバランスを取ることができる。
【０１０３】
場合によっては、目標分布は部分的に均等な分布であることができる。例えば目標分布の配向ビンの幾つかはゼロの値を有することができ、残りの配向ビンは同じ値を有することができる。このような場合、目標分布の配向ビンはゼロの値を有することができ、このとき垂直配向のヒストグラム604における対応する配向ビンはゼロの値を有する。
【０１０４】
FDCモジュール414が垂直配向のヒストグラムを決定し、TDCモジュール412が目標分布を決定すると、PDMモジュール416は、1個以上の特徴点上のプローブの分布が目標分布と整合するように、プローブの位置を決定することができる。
【０１０５】
図7は、幾つかの実施形態による、プローブの配置を決定するプロセスを示す。ステップ702で、PDMモジュール416が垂直配向のヒストグラムを使用して、特徴点のどの部分が特定の配向を示す構造上にあるかを決定することができる。例えばヒストグラムが180の配向ビンを有する場合、PDMモジュール416はヒストグラムを使用して、2度の分解能で特定の配向を示す特徴点の比率を決定することができる。次いで、PDMモジュール416は、特徴点に対応するヒストグラムビンの値に基づき、特徴点の弧の長さをスケーリングすることができる。より具体的には、PDMモジュール416は、個別の特徴点に関連付けられるヒストグラムビンの値と反比例するように個別の特徴点の弧の長さを調整することができる。
【０１０６】
例えば図3に示す例を参照すると、短いエッジ104に沿う特徴点の数を長いエッジ106に沿う特徴点の数に比べて少なくすることができる。それゆえ、短いエッジ104に対応するヒストグラムのビンの値を長いエッジ106に対応するビンの値よりも小さくすることができる。これに基づき、PDMモジュール416は、短いエッジ104に沿う特徴点（例えば境界セクション）の弧の長さを長くし、長いエッジ106に沿う特徴点の弧の長さを小さくする（又は変わらないままにする）ことができる。
【０１０７】
図8は、幾つかの実施形態による、境界の特徴点の弧の長さのスケーリングを示す。ヒストグラムが、垂直エッジ上の特徴点の数が水平エッジの特徴点上の数より少ないことを示すため、PDMモジュール416は、垂直エッジの特徴点の弧の長さを長くすることができる。長くなった特徴点の弧の長さは、矢印802で示すように垂直エッジに沿う境界の長さの増大と見なすことができる。
【０１０８】
ステップ704で、PDMモジュール416は、スケーリングされた境界上に均等にプローブを配置することができる。図9は、幾つかの実施形態による、スケーリングされた境界上のプローブの均等な配置を示す。境界の垂直エッジがスケーリングされているため、スケーリングされた垂直エッジ上にプローブ104を均一に配置すると、垂直エッジと水平エッジ上のプローブ104の数がほぼ同じになり得る。
【０１０９】
幾つかの実施形態では、PDMモジュール416は、スケーリングされた境界上に連続して均等にプローブを配置することができる。例えばPDMモジュール416は、最初の特徴点（任意に選択されてよい）から開始し、第1のプローブを最初の特徴点に配置する。次いで、PDMモジュール416が、第1のプローブから所定の距離だけ離れた特徴点に第2のプローブを配置することができる。
【０１１０】
ステップ706で、PDMモジュール416は、ステップ702のスケーリング操作の逆をすることができ、それによって均等に配置されたプローブ間の距離も調節する。図10は、幾つかの実施形態による、スケーリングされた境界の逆スケーリングを示す。境界の逆スケーリングに伴い、2つの隣接するプローブ104間の距離も同様に相応にスケーリングされる。それゆえ、垂直エッジに沿うプローブの密度が水平エッジに沿うプローブの密度に比べて高くなる。このようにして、分布1002によって示されるように、PDMモジュール416は、プローブ位置で測定された垂直配向のヒストグラムのバランスを取ることができる。バランスが取られた垂直配向のヒストグラム1002は全体としてプローブ104から得られる方向の情報もバランスが取られることを示す。
【０１１１】
幾つかの実施形態では、PDMモジュール416は、特徴点の弧（例えば境界セクション）の長さを実際に視覚的に伸ばすことなく弧の長さのスケーリング及び逆スケーリングを行うように構成され得る。例えばPDMモジュール416は、特徴点の弧の長さを効果的にスケーリングするために、特徴点の周りの基礎となる座標系の分解能を増加又は減少させるように構成され得る。
【０１１２】
幾つかの実施形態では、PDMモジュール416は、連続的にプローブを配置することによりステップ704と706を合わせることができる。例えばPDMモジュール416は、2つのプローブを分離するべき均等な距離を決定することができる。次にPDMモジュール416は、最初の特徴点（任意に選択されてよい）で開始し、第1のプローブを最初の特徴点に配置する。次いでPDMモジュール416は、垂直配向のヒストグラムに基づき、最初の特徴点に関連付けられる弧の長さを決定することができる。そしてPDMモジュール416は、弧の長さの関数として均一な距離をスケーリングして、第1のプローブと、この第1のプローブに隣接して配置される第2のプローブとの間のスケーリングされた距離を決定することができる。次いで、PDMモジュール416は、第1のプローブからスケーリングされた距離だけ離れた特徴点に第2のプローブを配置することができる。このプロセスは、PDMモジュール416が複数の特徴点のすべてを考慮するまで繰り返すことができる。このようにしてPDMモジュール416は、パターンの境界を視覚的にスケーリングすることなく、ステップ704及び706を実行できる。
【０１１３】
幾つかの実施形態では、FDCモジュール414は、ステップ702で特徴点の弧の長さをスケーリングする前に垂直配向のヒストグラムにローパスフィルタ操作を実行できる。特徴点の弧の長さをスケーリングする前にローパスフィルタ操作を実行することには、幾つかの利点があり得る。第1に、ローパスフィルタ操作により、プローブ配置モジュールが垂直配向のヒストグラムからノイズを取り除けるようにすることができる。
【０１１４】
第2に、ローパスフィルタによってゼロ除算の問題に対処することができる。弧の長さのスケーリングを実行するPDMモジュール416は、しばしば垂直配向のヒストグラムにおける配向ビンの値を分母として使用するでろう。しかしながら0の値の配向ビンがある場合があり、これがゼロ除算の問題を生じることがある。ローパスフィルタ操作により、効果的にゼロの値の配向ビンを除去することによってこの問題に対処することができる。
【０１１５】
第3に、このローパスフィルタ操作により、プローブ配置モジュールは隣接する配向ビンが良好に示されている場合に、甚だしく不十分に表示される特定の配向ビンを無視することが可能になる。例えば垂直配向のヒストグラムは、パターンが89度の垂直配向を有する構造上に100個の特徴点を有し、91度の垂直配向の構造上に100個の特徴点を有し、しかし90度の垂直配向を有する構造上に1個の特徴点のみを有することを示すことができる。ローパスフィルタがなければ、PDMモジュール416は、89度又は91度の垂直配向を有する特徴点周りのプローブの数を制限しながら、90度の垂直配向を有する特徴点周りのプローブの数を増やすであろう。このような垂直配向のヒストグラムのバランスを取るための抜本策は、同様の配向が同様の情報を取得できるため、プローブからバランスの取れた情報を取得するのに非効果的になることがある。言い換えれば、89度又は91度の垂直配向を示すプローブは、90度の垂直配向を示すプローブと実質的に同様の情報を取得できる。それゆえ、90度の垂直配向を示すプローブの数を増やすことは、特にプローブの全体数が制限されている場合に、全角度範囲に渡ってバランスの取れた情報を取得するのに非効果的になることがある。
【０１１６】
ローパスフィルタによりこの問題に対処することができるが、それは垂直配向のヒストグラムのローパスフィルタにより、90度の配向ビンの値を89度及び91度の配向ビンの値と平滑化（例えば平均化）することができるからである。それゆえローパスフィルタ操作により、90度の配向ビンの値を実質的に増加させることができる。このようにしてPDMモジュール416により、90度の垂直配向の周りの情報が89度及び91度を示すプローブにより良好に得られたことが確認できる。それゆえ、PDMモジュール416は90度を示すプローブの数を激増させることはない。
【０１１７】
幾つかの実施形態では、FDCモジュール414は、カーネルでヒストグラムを畳み込むことにより、ローパスフィルタ操作を実行できる。幾つかの実施形態では、FDCモジュール414は、巡回畳み込みを実行するように構成され得る。例えば巡回畳み込みの下では、FDCモジュール414は、ヒストグラムの配向ドメイン（例えば0−2π）の限界周りのカーネルを包み込むことができる。ローパスフィルタ操作用のカーネルは、レイズド・コサイン・カーネル、コサイン二乗カーネル、又はヒストグラムを平滑化することができる任意の他の巡回関数を含むことができる。FDCモジュール414はカーネルの幅を制御して、ヒストグラム上で実行される平滑化の量を制御することができる。例えばカーネルの幅によって2π/Nをカバーすることができ、ここで、Nは任意の整数であってよい。
【０１１８】
幾つかの実施形態では、図10に示すように短いエッジに沿うプローブの密度を増加させる代わりに、PDMモジュール416が特徴点上のプローブを初期化し、初期化されたプローブに関連付けられる加重値を決定するように構成され得る。例えばプローブが短いエッジと関連付けられる場合（例えばプローブが小さい値の配向ビンに対応するエッジ上に配置される）、PDMモジュール416はプローブに関連付けられる加重値を増加させることができる。プローブが長いエッジと関連付けられる場合（例えばプローブが大きい値の配向ビンに対応するエッジ上に配置される）、PDMモジュール416はプローブに関連付けられる加重値を減少させることができる。次いで、加重値を用いて様々な用途、例えば境界のアライメントに対するプローブの寄与を変化させることができる。この技術を用いるとPDFモジュール416は、（1）短いエッジに沿うプローブの密度を増加させること、及び（2）アライメントの間に増加したプローブ数を整合させることに必要な計算処理能力を少なくすることができる。しかし、PDMモジュール416は図7のプロセスを使用する場合と比較してプローブの分解能を減少させることがある。
【０１１９】
第2のプローブ配置機構−分布からのプローブのサンプリング
【０１２０】
幾つかの実施形態では、プローブ配置モジュール408 は、プローブの目標分布からプローブをサンプリングすることによって、1個以上の特徴点上にプローブを配置するように構成され得る。プローブの目標分布は、パターンに関連付けられる自由度に対応する確率変数を含むことができる。例えばパターンに関連付けられるオブジェクトが2次元で移動することができる場合（例えば並進移動）、目標分布は2つの確率変数:、即ちx座標とy座標（又は他の同等の表現）を有することができる。別の例としては、パターンに関連付けられるオブジェクトが並進移動及び回転移動をすることができる場合、目標分布は3つの確率変数、即ち:x座標、y座標及び回転ベクトル（例えば配向）を有することができる。別の例としては、パターンに関連付けられるオブジェクトが並進移動、回転移動及びスケーリング移動（例えば撮像デバイスから離れる又は撮像デバイスに向かう移動）をすることができる場合、目標分布は4つの確率変数、即ち:x座標、y座標、回転及びスケールを有することができる。
【０１２１】
幾つかの実施形態では、プローブ配置モジュール408 は、ノンパラメトリックな分布として目標分布を示すことができる。例えばプローブ配置モジュール408 は、各確率変数のドメインを複数のビンに量子化し、対応するビンに分類される特徴点の数を単純にカウントすることができる。他の実施形態では、プローブ配置モジュール408 はパラメトリックな分布として目標分布を示すことができる。
【０１２２】
幾つかの実施形態では、プローブ配置モジュール408 はTDCモジュール412を使用して目標分布を決定することができる。TDCモジュール412は、特徴点に関連付けられる特徴に基づいてプローブの目標分布を決定するように構成され得る。例えばTDCモジュール412は、例えば特徴点の座標、特徴点に関連付けられる垂直配向、特徴点の回転又は特徴点のスケールの内の1つ以上に基づいて目標分布を決定することができる。
【０１２３】
幾つかの実施形態では、TDCモジュール412は、目標分布からサンプリングされる垂直配向の分布が実質的にバランスが取られるように、目標分布を決定するように構成される。例えば特徴点のパターンが、図1に示すように水平な矩形であるとしよう。そのようなパターンは、図11Aに示すような勾配ベクトル分布を有するモデルに関連付けられることができる。図11Aに示すように、大きいy方向の成分を有するエッジが、大きいx方向の成分を有するエッジに比べてかなり多い。それゆえ図1のパターンの目標分布は、目標分布から抽出されたプローブが、図11Bに示すようにバランスの取れた勾配分布を有するであろう。
【０１２４】
幾つかの実施形態では、TDCモジュール412は、目標分布が特徴点の分布と同様のサポートを有するように、目標分布を決定するように構成される。これが重要であるのは、これらの実施形態では、プローブ配置モジュール408 が、既存の特徴点のセットから再サンプリング（例えば重要度のサンプリング）することによってプローブをサンプリングするように構成されるためである。このために以下に論じるように、TDCモジュール412は、特徴点の分布と目標分布の両方のための混合モデルを使用するように構成される。
【０１２５】
幾つかの実施形態では、TDCモジュール412は、目標分布をPDMモジュール414に提供し、PDMモジュール414は、目標分布からサンプルを抽出してプローブの位置を決定するように構成される。
【０１２６】
幾つかの実施形態では、PDMモジュール414は、重要度のサンプリング技術を用いて、目標分布からサンプルを抽出することができる。他の実施形態では、PDMモジュール414は、パターンの境界を決定してパターンの境界に沿ってプローブのサンプルを生成するように構成され得る。この技術は、目標分布から少数のサンプルのみを抽出する場合に有用であり得る。この技術には、サンプリングによって生成されたプローブのセットが再サンプリングプロセスにおけるランダムな変動によって影響を受けないようにすることができ、プローブがパターンの境界の幾何学的範囲全体に渡って分配されることを保証できるという利点がある。
【０１２７】
目標分布 計算
【０１２８】
パターンが2自由度を有する場合（例えば並進移動）、TDCモジュール412は、次の関係を満たす重み付け関数f（x,y）を決定することができる。
2018055679.tif 000003
式中、iはi番目の特徴点を示す。この最適化ルーチンの目的は、（1）特徴点で測定された勾配ベクトルのx成分の重み付けされた合計と、（2）特徴点で測定された勾配ベクトルのy成分の重み付けされた合計とに等しい関数f（x,y）を特定することである。場合によっては、TDCモジュール412は勾配ベクトルの大きさのみのバランスを取ることができる。それゆえ、xiはi番目の特徴点において測定された勾配ベクトルのx成分の絶対値を指すことができ、yiはi番目の特徴点において測定された勾配ベクトルのy成分の絶対値を指すことができる。
【０１２９】
TDCモジュール412が重み付け関数f（x,y）を決定すると、TDCモジュール412は、重み付け関数f（x,y）をPDMモジュール416に提供することができる。幾つかの実施形態では、重み付け関数はPDMモジュール416が1個以上の特徴点上にプローブを配置するのに使用することができる確率分布の形態を取ることがある。この場合はPDMモジュール416が重み付け関数f（x,y）を、そこからプローブをサンプリングするための確率分布として使用するので、それは非負に制約されなければならず、少なくとも幾つかの成分（x,y）については正になり得る。そのような実施形態に対して、「目標分布」という用語は本明細書においてf（x,y）と表示される確率分布を称するのに使用される。
【０１３０】
幾つかの実施形態では、重み付け関数が幾つかの他の手段によって選択されたプローブの既存のセットを重み付けするのに使用されて、以下の通り最小化するように相対的重要度に影響を与える。
2018055679.tif 000004
【０１３１】
パターンが3自由度を有する場合（例えば並進移動及び回転移動）、TDCモジュール412は回転移動に対応する回転変数θを目標分布に組み込むことができる。TDCモジュール412は原点に対する回転変数θを規定することができる。
【０１３２】
幾つかの実施形態では、原点は複数の特徴点の質量中心であることができる。幾つかの実施形態では、原点は回転中心であることができる。回転中心は、その周りで回転モーメントが最小になる点であることができる。回転中心は、固有の全体的最小値に対応し、基底ベクトル（例えば座標系）の選択とは独立している。それゆえ、回転中心は複数の特徴点に固有の幾何学量である。回転中心は次の通り計算することができる。
2018055679.tif 000005
式中、pは基準点（任意に選択されてよい）に対する基準ベクトル、uは特定の特徴点における単位法線ベクトル、Xは外積行列である。図11は、幾つかの実施形態による、基準ベクトルpと単位法線ベクトルuとの関係を示す。
2018055679.tif 000006
式中、下付文字x及びyは、対応するベクトルのx成分及びy成分を示す。 
【０１３３】
原点が決まると、TDCモジュール412は、原点からi番目の特徴点の中心までのベクトルである、i番目の特徴点の位置ベクトルviを使用して回転変数θを決定することができ、また、i番目の特徴点の中心における回転単位ベクトルuθiを決定することができる。図12は、幾つかの実施形態による、位置ベクトルviと回転単位ベクトルuθi との関係を示す。
【０１３４】
幾つかの実施形態では、回転変数θiは位置ベクトルviのノルムとは独立したものであることができる。位置ベクトルviのノルムとは独立している回転変数θiにより、位置ベクトルviのノルムに基づいてプローブ位置を区別することのない目標分布を提供することができる。例えばTDCモジュール412は、i番目の特徴点について回転変数θiを次の通り決定することができる。
2018055679.tif 000007
この回転変数θiの表示は、大きい角度ステップサイズωで形状を粗くアライメントするのに有用であることがある。
【０１３５】
幾つかの実施形態では、回転変数θiは位置ベクトルviのノルムを考慮に入れることができる。
2018055679.tif 000008
原点から更に離れた特徴点の寄与を強調することができる。例えばTDCモジュール412はi番目の特徴点の回転変数θiを次の通り決定することができる。
2018055679.tif 000009
位置ベクトルviのノルムに依存する回転変数θiは、原点から更に離れた位置にプローブを配置するのに有利になる目標分布を提供することができる。このようにして、目標分布により原点から更に離れた特徴点でより多くのプローブをサンプリングすることができる。
【０１３６】
幾つかの実施形態では、TDCモジュール412はパターンの形状に基づいて回転変数θiの表示を決定することができる。例えばTDCモジュール412は、パターンがレバーアームを含むことを決定することができる。この場合、TDCモジュール412はどの表示を回転変数θに使用するか判定する際にレバーアームを考慮に入れることができる。別の例としては、TDCモジュール412は、パターンが同心円又は別のナットの内側にあるナットを含んでいると判定することができる。この場合、TDCモジュール412は、どの表示を回転変数θに使用するか判定する際に、同心円又は別のナットの内側にあるナットを考慮に入れることができる。
【０１３７】
TDCモジュール412が回転変数に対する表示を決定すると、TDCモジュール412は決定された表示を使用して各特徴点を表示することができる。次いで、TDCモジュール412は、次の関係を満たす重み付け関数f（x,y,θ）を見出すことによって特徴点の表示に基づいて目標分布を決定するように構成され得る。
2018055679.tif 000010
式中、iはi番目の特徴点を示す。
【０１３８】
TDCモジュール412が目標分布f（x,y,θ）を決定すると、TDCモジュール412はその目標分布f（x,y,θ）をPDMモジュール416に提供することができる。次いで、PDMモジュール416は目標分布f（x,y,θ）を、パターン上のプローブをサンプリングするための確率分布として使用することができる。
【０１３９】
上記の最適化プロセスを容易にするために、プローブ配置モジュール408 は目標分布f（x,y,θ）の関数形態を仮定することができる。
【０１４０】
幾つかの実施形態では、プローブ配置モジュール408 は線形形態を有する目標分布f（x,y,θ）を仮定することができる。線形関数は負になり得るが、f（xi,yi,θi）≧0, ∀iの制約により、目標分布はすべての特徴点で正であることが強制される。目標分布f（x,y,θ）が線形形態を有する場合、目標分布を見出すための最適化ルーチンは単純であることがある。しかしながら線形関数のスペースは限られるため、すべての制約を満足する線形関数を見出すことは困難になることがある。
【０１４１】
幾つかの実施形態では、プローブ配置モジュール408 は、目標分布f（x,y,θ）が非線形形態を有すると仮定することができる。目標分布f（x,y,θ）が非線形形態を有する場合、目標分布を見出すための最適化ルーチンは複雑になることがある。しかしながら非線形関数のスペースは広いので、すべての制約を満たす非線形関数を見出すことの方が容易であろう。
【０１４２】
幾つかの実施形態では、TDCモジュール412は、目標分布f（x,y,θ）を特徴点分布pp（x,y,θ|パラメータ）の逆数として設定することができる。この場合、TDCモジュール412はFDCモジュール414から特徴点分布pp（x,y,θ）を受信し、逆数f（x,y,θ）＝１／pp（x,y,θ）を計算することによって間接的に目標分布f（x,y,θ）を決定することができる。目標分布f（x,y,θ）が特徴点分布pp（x,y,θ）の逆数として決定されたら、目標分布f（x,y,θ）により、残りの特徴点に比べて比較的似ていない特徴点を有する位置でより多くのプローブがサンプリングされるようになる。
【０１４３】
FDCモジュール414は、特徴点分布pp（x,y,θ）を混合モデルとしてモデル化することができる。幾つかの実施形態では、混合モデルは次のガウス混合モデル（GMM）を含むことができる。
2018055679.tif 000011
GMMは4つのパラメータ、即ちガウス分布の数N、k番目のガウス分布の加重値αｋ、
2018055679.tif 000012
他の実施形態では、混合モデルは三角分布の混合を含むことができる。三角分布の混合はより速く計算することができ、特徴点の柔軟なグルーピングを提供するという同様に望ましい特性を与えることができる。
【０１４４】
幾つかの実施形態では、FDCモジュール414は、特徴点のクラスタリング及び特徴点に最も適合するクラスタの数の判定により、GMMのためのガウス分布の数Nを推定することができる。例えばFDCモジュール414は特徴点上でk平均クラスタリング操作を実行して、ガウス分布の数Nを推定することができる。
【０１４５】
残りの
2018055679.tif 000013
は、特徴点に与えられるパラメータの尤度を最大化することによって決定することができる。幾つかの実施形態では、FDCモジュール414は期待値最大化技術を用いて、特徴点に与えられたパラメータの尤度を最大化することができる。期待値最大化を実行するために、FDCモジュール414はクラスタリングステップの結果を使用して、
2018055679.tif 000014
を初期化することができる。
【０１４６】
上述したように、TDCモジュール412は、特徴点分布pp（x,y,θ）を単純に逆にすることによって目標分布f（x,y,θ）を決定することができる。しかしながら、この目標分布f（x,y,θ）は、極めて稀な垂直配向のエッジ上にほとんどのプローブを配置させることがある。例えばパターンが2Dの並進移動のみ行うことが可能であり、パターンが角の丸い矩形の境界を有する場合、この目標分布f（x,y）はPDMモジュール416にほとんどをコーナー位置の周りでサンプリングさせることがある。
【０１４７】
そのような問題に対処するために、幾つかの実施形態では、TDCモジュール412は特徴点分布pp（x,y,θ）を変形し、変形された特徴点分布
2018055679.tif 000015
を逆にして目標分布f（x,y,θ）を決定することができる。前述の「第1のプローブ配置機構」において、この変形は平滑化カーネルをpp（x,y,θ）に適用する形態を取る。
【０１４８】
場合によっては、TDCモジュール412は逆にする以外の方法によって特徴点分布を変形することによって目標分布を決定することができる。そのような1つの実施形態は、特定の条件を満たす新しい加重値αｋを見出すことによって
2018055679.tif 000016
TDCモジュール412は特徴点の柔軟なグルーピング（例えばガウス分布への柔軟なグルーピング）を効果的に実行した。現在TDCモジュール412はそれらのグルーピングを有しており、
2018055679.tif 000017
各グループ（例えば各ガウス分布）を個別に再重み付けするように構成され得る。
【０１４９】
2018055679.tif 000018
【０１５０】
TDCモジュール412は、この連立線形方程式を
2018055679.tif 000019
について解くことができるが、TDCモジュール412は追加的な制約を受ける。上記の連立線形方程式は変形された加重値
2018055679.tif 000020
が負になることを妨げないか、又は大きい加重値
2018055679.tif 000021
が特徴点の小さいグループ（例えば特徴点分布pp（x,y,θ）におけるその元の加重値αｋが小さかった）から推定されたガウスに割り当てられることを妨げない。TDCモジュール412は、それらの制約をプログラムによって適用することができる。
【０１５１】
また、TDCモジュール412は、変形された加重値
2018055679.tif 000022
を規定の値より大きくなるように要求することによって、隣接するプローブ間の最小プローブ距離を課すように構成される。
2018055679.tif 000023
式中、αｋは特徴点分布pp（x,y,θ）におけるk番目のガウス分布の加重値、Nedgesは特徴点分布pp（x,y,θ）における加重値αｋを推定するために使用される特徴点の数、Nprobesはプローブの目標数（例えば64）、dmaxは特徴点の単位又は任意の所定の単位におけるプローブ間の最大の許容可能な距離である。上述の方程式は次の通り再整理することができる。
2018055679.tif 000024
この新しい関係は、混合要素kについてプローブの数に対するエッジの数の比がdmax単位と1単位によって限定されていることを示す。それゆえクラスタkにおける隣接するプローブは、dmax単位からそれ以上離れることなく、また1単位より近づくことなく配置することができる。
【０１５２】
連立線形方程式が、制約に反する少なくとも1つの加重値αｋを有する結果を生み出す場合、TDCモジュール412は境界ケースのすべての可能な組合せについて繰り返し、最適な残りの加重値を計算し、制約された最小値を選択することができる。
【０１５３】
例えばTDCモジュール412は、線形方程式についてすべての可能な境界条件のセット
2018055679.tif 000025
を決定することができる。境界条件の各セットは、変形された加重値
2018055679.tif 000026
のサブセットに対する境界条件を含むことがある。次いで、境界条件の各セットについて、TDCモジュール412は、加重値
2018055679.tif 000027
のサブセットの値を対応する境界条件の値に固定し、境界条件のない残りの自由な加重値
2018055679.tif 000028
について連立線形方程式を解くことができる。このようにして、TDCモジュール412はすべての可能な境界条件のセットの下での解の中から最小スコアの解を選択することによって、制約が与えられた連立線形方程式の大域解を決定することができる。
【０１５４】
場合によっては、GMMにおけるガウス分布の数が、特徴点がある範囲の数より大きい場合、GMMにおけるパラメータの幾つかは線形従属であることがある。例えばガウス分布の数が、特徴点がある範囲の数より大きい場合、ガウス分布の平均ベクトルは線形従属になることがある。
【０１５５】
この問題に対処するために、TDCモジュール412は、例えばティホノフ正則化を用いてGMMに対するパラメータを正則化するように構成され得る。このためにTDCモジュール412は、次の関係を最小化するために最適化の問題を再公式化することができる。
2018055679.tif 000029
新しいラグランジュの公式は、平均ベクトルの（x,y,θ）成分のバランスが取られており、変形された加重値の合計が1であるという制約条件の下で、
2018055679.tif 000030
の変化を数値化することを求める。
【０１５６】
TDCモジュール412は、上述したラグランジュの関係を満たす加重値を直接見出すことができよう。しかしながら、前述のようにこの関係は加重値
2018055679.tif 000031
が負になることを妨げず、又は大きい加重値
2018055679.tif 000032
が特徴点の小さいグループ（例えば特徴点分布pp（x,y, θ）における元の加重値αｋが小さかった）から推定されたガウスに割り当てられることを妨げない。TDCモジュール412は上述したように、これらの制約をプログラムによって適用することができる。これは数学的に有効であるが、その理由は
2018055679.tif 000033
における上記のラグランジュの関係が二次式であり、加重値
2018055679.tif 000034
の1つが負である場合、最適値は1つ（以上）の境界条件にあることになるからである。
【０１５７】
要約すると、
2018055679.tif 000035
パラメータを特定するために、TDCモジュール412は以下の手順を使用することができる。
2018055679.tif 000036
この系が特異である場合、TDCモジュール412は正則化を用いてこの系を解くことができる。例えばTDCモジュール412が
2018055679.tif 000037
このようにして、TDCモジュール412は解ベクトルのＬ２ノルムの合計を最小化することができ、ひいては大きい正及び負のαｋ（合計して単一性になる）を有する解を妨げることができる。
2018055679.tif 000038
4.ステップ2又はステップ3の解を次の制約と照合する。
2018055679.tif 000039
5.解が加重値
2018055679.tif 000040
の有効範囲外にある場合、すべての可能な境界条件（例えば制約）のセットについて、ステップ2又は3の修正版を使用して制約されていない
2018055679.tif 000041
に対する解ベクトルを見出す。TDCモジュール412は検索を通して、次式の最小値を追跡することができる。
2018055679.tif 000042
前者の関係がゼロより大きい場合、TDCモジュール412は前者の関係を用いて
2018055679.tif 000043
に対する解ベクトルを選択することができる。前者の関係がゼロより大きくない場合、TDCモジュール412は、後者の関係を用いて
2018055679.tif 000044
に対する解ベクトルを選択することができる。
【０１５８】
目標分布からのプローブのサンプリング
【０１５９】
TDCモジュール412が変形された特徴点分布
2018055679.tif 000045
を決定すると、TDCモジュール412は変形された特徴点分布
2018055679.tif 000046
（又は変形された特徴点分布の逆数）をPDMモジュール416に提供することができる。次いで、PDMモジュール416は変形された特徴点分布
2018055679.tif 000047
の逆数からサンプリングして、画像内の1個以上の特徴点のプローブの位置を決定することができる。
【０１６０】
直観的に言うと、TDCモジュール412は変形された特徴点分布
2018055679.tif 000048
に関するx、y、及びθの期待値ができるだけ同様になるように、変形された特徴点分布
2018055679.tif 000049
を選択するように構成される。
2018055679.tif 000050
【０１６１】
重要度のサンプリングにより、PDMモジュール416は、別の異なる分布から抽出されたサンプルを、同様のサポートを有するサンプルの条件で重み付けすることによって、目標分布からサンプルを抽出することができる。言い換えれば、
2018055679.tif 000051
となり、式中、Sprobesはプローブのセット、SIPは特徴点のセットである。それゆえPDMモジュール416は、この関係を用いて次式により特徴点分布
2018055679.tif 000052
から抽出されたサンプルの重み付けをすることができる。
2018055679.tif 000053
【０１６２】
こうしてPDMモジュール416がパターンの境界に沿うすべての特徴点にプローブを配置することによってプローブを抽出する場合、PDMモジュール416は上記の比
2018055679.tif 000054
によってプローブの重み付けをすることができる。幾つかの実施形態では、PDMモジュール416は、（1）隣接するプローブをパターンの境界に沿って上記の比の逆数の距離だけ離間させること、及び（2）プローブの所望の数及び最初のエッジの数を補償することによって同様の効果を達成することができる。
【０１６３】
それゆえ、幾つかの実施形態では、変形された特徴点分布
2018055679.tif 000055
の逆数からサンプリングすることは、隣接するプローブを以下の量だけ離間させるように要求することと同等であることができる。
2018055679.tif 000056
式中、Nedgesは、特徴点分布
2018055679.tif 000057
のパラメータを決定するために使用される特徴点の数を示し、Nprobesは、プローブの目標数を示す。このようにして、不十分に表示される特徴点に沿うプローブの密度を増加させることができる。
【０１６４】
そのように隣接するプローブを離間させるように要求するために、PDMモジュール416は連続して1個以上の特徴点上にプローブを配置することができる。例えばPDMモジュール416は最初の特徴点（任意に選択されてよい）で開始し、第1のプローブを最初の特徴点に配置する。次いで、PDMモジュール416は上述の関係を使用して、第1のプローブと第1のプローブに隣接して配置される第2のプローブとの間の距離を決定することができる。次いで、PDMモジュール416は第2のプローブを第1のプローブから決定された距離だけ離れた特徴点に配置することができる。このプロセスは、PDMモジュール416が、特徴点分布
2018055679.tif 000058
を決定するのに使用される複数の特徴点のすべてを考慮するまで繰り返すことができる。
【０１６５】
隣接するプローブを特定の量だけ離間させることの要求は、隣接する特徴点の弧の長さを変更する（例えば伸ばす）と解釈することができる。上述したように、特徴点は、特徴点の中心に配置された、初期化されたプローブの表示と見なすことができる。それゆえ、隣接するプローブを特定の量だけ離間させることの要求は、隣接する特徴点の中心間の弧の長さを変更することと解釈することができる。それゆえプローブを配置するための第1の機構（図5〜図10に関して示す）と、プローブを配置するための第2の機構（図11〜図12に関して示す）とは同様の結果をもたらす。
【０１６６】
本明細書の議論の多くが、x軸成分、y軸成分及び回転ベクトルを含めた混合モデルによって確率空間が広げられた場合に焦点を当てているが、開示の技術を拡大して混合モデルによって広げられた確率空間の次元数を増加させることができる。例えばプローブ配置モジュール408 は、次の4次元空間の情報のバランスを取るように構成され得る。
2018055679.tif 000059
式中、φはスケールを表わす。最適化ステップはこれよりわずかに複雑になることがあるが、プローブ配置モジュール408 は3次元空間のシナリオと同じ技術を利用することができる。例えばプローブ配置モジュール408 は、（上述したように）ラグランジュ乗数を用いて連立線形方程式に減少させることによって、次の通り最小化するように構成され得る。
2018055679.tif 000060
プローブ配置モジュール408 は、加重値
2018055679.tif 000061
が負にならないようにするか、プローブを幾つかのエッジの位置に極度に集中させないようにすることを確実にするように構成され得る。このためにプローブ配置モジュール408 は、3次元空間のシナリオと同様に、境界制約をプログラムによって適用するように構成され得る。
【０１６７】
プローブ配置モジュール408 は、3次元空間のシナリオと同様に平均ベクトルセットが線形的に独立していない場合、及び混合モデルの要素数（N）が次元数（ここでは4）を超える場合、ティホノフ正則化を適用することができる。
2018055679.tif 000062
【０１６８】
図13は、幾つかの実施形態による、パターンの1個以上の特徴点上のプローブのサンプリングのプロセスを要約している。図13において、プローブ配置モジュール408 はパラメトリック分布として目標分布を示す。しかしながら、当業者は図13のプロセスを変更して、プローブ配置モジュール408 が非パラメトリック分布として目標分布を示す場合に適応させることができる。
【０１６９】
ステップ1302で、IPDモジュール406は画像内の特徴点を決定することができる。場合によっては、IPDモジュール406はエッジ検出技術を使用して特徴点を識別することができる。エッジ検出技術は、例えばキャニーエッジ検出技術又はハフ変換技術を含むことができる。エッジ検出技術は、例えばソーベルオペレータ、キルシュオペレータ、プルウィットオペレータ、ガボアフィルタ、ハールウェーブレットフィルタ、画像内のピクセル値の変化（例えば画像の高周波数成分）を検出できる任意の他のフィルタ及び/又はそれらの任意の組合せを含む1つ以上のエッジ検出オペレータを使用することができる。
【０１７０】
幾つかの実施形態では、IPDモジュール406は特徴点の位置情報をFDCモジュール414に提供することができる。FDCモジュール414は、特徴点に関連付けられる自由度を示す変数を使用して各特徴点を示すことができる。例えば特徴点が2次元で移動することが知られている場合、特徴点は、特徴点の（x,y）勾配要素に対応する2次元ベクトルとして示すことができる。別の例では、特徴点が3次元で移動することが知られている場合、特徴点は、特徴点の（x,y）勾配要素及び特徴点の回転配向（又はその関数）に対応する3次元ベクトルとして示すことができる。
【０１７１】
ステップ1304で、FDCモジュール414は、特徴点をクラスタリングするように構成され得る。例えばFDCモジュール414は、その表示におけるユークリッド距離内で互いに近接する特徴点をクラスタリングすることによって特徴点をクラスタリングすることができる。幾つかの実施形態では、FDCモジュール414は、k平均クラスタリング技術、平均シフトクラスタリング技術、「階層を用いたバランスの取れた反復的な削減とクラスタリング」（BIRCH）クラスタリング技術、又は同様の性質で特徴点をグルーピングすることができる任意の他の適切なクラスタリング技術を使用することができる。
【０１７２】
ステップ1306で、FDCモジュール414はステップ1304からのクラスタに基づき、特徴点分布を決定することができる。例えばFDCモジュール414は、ガウス混合モデルを使用して特徴点分布を示すように構成され得る。この場合、FDCモジュール414はクラスタリングステップからのクラスタの数を用いて、ガウス混合モデルのためのガウス分布の数を決定するように構成され得る。また、FDCモジュール414は、期待値最大化操作を実行して、ガウス混合モデルのパラメータのセットの最尤推定値を決定するように構成され得る。このようにして、FDCモジュール414は特徴点分布
2018055679.tif 000063
を決定することができる。FDCモジュール414は、特徴点分布
2018055679.tif 000064
をTDCモジュール412に提供することができる。
【０１７３】
ステップ1308で、TDCモジュール412は特徴点分布
2018055679.tif 000065
から、変形された特徴点分布
2018055679.tif 000066
を決定することができる。このためにTDCモジュール412は、上述のように条件付き最適化を実行して、変形された特徴点分布に対する変形された加重値
2018055679.tif 000067
を再計算することができる。場合によっては、TDCモジュール412は、変形された特徴点分布
2018055679.tif 000068
を逆にすることによって目標プローブ分布を計算することができる。次いで、TDCモジュール412は変形された特徴点分布（又は、変形された特徴点分布の逆数）をPDMモジュール416に提供することができる。
【０１７４】
ステップ1310で、PDMモジュール416は、目標分布（例えば変形された特徴点分布の逆数）をサンプリングして、1個以上の特徴点上のプローブの位置を決定するように構成される。場合によっては、PDMモジュール416は次の関係を用いて2つの隣接するプローブ間のスペースを決定することができる。
2018055679.tif 000069
PDMモジュール416は、上記の関係を用いてすべての隣接する特徴点の中心間（又は、隣接する特徴点のサブセットの中心間）の距離を決定するか、変更することができる。
【０１７５】
図14Aは、幾つかの実施形態による、図13に示すプロセスを使用した矩形上へのプローブの配置を示す。矩形は、2自由度を有すると仮定される（例えば矩形は並進移動のみをすると仮定される）。この場合、PDMモジュール416は矩形の短いエッジに沿うプローブの密度を、矩形の長いエッジに比べて増加させた。この結果は、図5〜図10に関して論じたように、垂直配向のヒストグラムのバランスを取る結果と同様である。
【０１７６】
図14Bは、幾つかの実施形態による、図13に示すプロセスを使用したレバーアームを有する円形のオブジェクト上へのプローブの配置を示す。パターンは2自由度を有すると仮定される（例えばパターンは並進移動のみをすると仮定される）。この場合、PDMモジュール416は、円上のy方向のプローブをわずかに多く増やすことで、レバーアーム上の付加的なx方向のプローブを補償する。
【０１７７】
図15Aは、幾つかの実施形態による、図13に示すプロセスを使用した矩形上へのプローブの配置を示す。矩形は3自由度を有すると仮定され（例えば矩形は並進移動と回転移動をすると仮定される）、回転ベクトルは、次式によって与えられる。
2018055679.tif 000070
この場合、PDMモジュール416は、図14Aに示すように、矩形の長いエッジに比べ、矩形の短いエッジに沿うプローブの密度を増加させた。しかしながら、PDMモジュール416は長いエッジに沿うプローブの距離も変更し、矩形の原点（例えば矩形の質量中心）からより離れたプローブの数を増加させた。その理由は、回転変数θが、矩形の原点とプローブの間の距離に依存していたためである。
【０１７８】
図15Bは、幾つかの実施形態による、図13に示すプロセスを使用したレバーアームを有する円形オブジェクト上へのプローブの配置を示す。パターンは3自由度を有すると仮定される（例えばパターンは並進移動と回転移動をすると仮定される）。この場合PDMモジュール416はレバーに沿うプローブの密度を増加させたが、その理由は回転変数θが矩形の原点とプローブの間の距離に依存していたためである。しかしながら、PDMモジュール416は円形境界の周りに配置されたプローブの数を減少させた。特に、PDMモジュール416は水平軸に近い境界に沿うプローブの数を減少させた。この場合、レバーアームのエッジは回転自由度のアライメント情報のすべてを含み、それゆえより多くのプローブが与えられる。これらのプローブはx方向のアライメントに対しても有用であることができるが、y方向の情報は完全に欠如している。それゆえPDMモジュール416は円の頂部と底部に円の左側と右側より多くのプローブを追加してy方向の情報をモデルに示す。
【０１７９】
図16A-16Bは、幾つかの実施形態による、図13に示すプロセスを使用した穴を有するパターン上へのプローブの配置を示す。境界が別の境界の完全に内側にある場合（例えば同心円又は別のナットの内側のナット）、プローブ配置モジュール408 が境界の1つにプローブを配置するためのより高い優先度を与えるべきか、そして与える場合はどの境界により高い優先度を与えるべきかを制御することができる。幾つかの実施形態では、プローブ配置モジュール408 は回転変数θでそのような優先度を符号化することができる。
【０１８０】
図17A〜図17Cは、幾つかの実施形態による、回転変数θの表示がどのようにプローブの位置を変化させるかを示す。図17Aは、回転変数θが
2018055679.tif 000071
とは独立している場合のプローブの配置に対応する。図17Bは、回転変数θが次式のように、位置ベクトル||vi||のノルムに依存している場合のプローブの配置に対応する。
2018055679.tif 000072
この式は線形形態の半径を組み込んで、角運動量と見なすことができる量をモデル化する。図17Cは、回転変数θが次式のように、位置ベクトル||vi||のノルムに依存している場合のプローブの配置に対応する。
2018055679.tif 000073
この式の2乗を用いて慣性の角運動量と同質の量を形成する。用途に応じて、これらの関数の1つがより好ましくなり得る。半径の項の順で増加させることにより、角度成分が最も高いプローブをパターンの最も外側の領域に押しやる傾向になる。このことは、画像内にパターンを探す際にプローブを全体に適用するスペースを選ぶときに密接に関連する。これは角度アライメント精度にも密接に関連する。
【０１８１】
図18A〜図18Bは、幾つかの実施形態による、図13に示すプロセスを使用した細長いアームを有するパターン上へのプローブの配置を示す。図18Aでは、プローブ配置モジュール408 は、パターンが3自由度を有すると仮定する（例えばパターンは並進移動と回転移動をすると仮定される）。図18Bでは、プローブ配置モジュール408 は、パターンが4自由度を有すると仮定する（例えばパターンは並進移動、回転移動及び撮像デバイスに向かう/撮像デバイスから離れる動きをすると仮定される）。
【０１８２】
これらの図は興味深いケースを示しているが、その理由は特徴点分布の4つのガウス分布が次の従属平均ベクトルを有するためである。
2018055679.tif 000074
この場合、正則化されていない最適化は、加重値が大きい値
2018055679.tif 000075
になることがあるが合計すると1となり得る解を提供することができる。このような特異点に対処するために、TDCモジュール412は最適化の問題を調整することができる。
【０１８３】
プローブ位置モジュール408は種々の応用に用いることができる。例えば、電子デバイスといったパターンのアラインメントや検査において位置モジュール408が有用であり得る。また、プローブ位置モジュール408はロボットガイダンスにおいても有用であり得る。例えば、ロボットが長く非常に細いバッテリーを拾い上げるようになっている場合に、その非常に細いバッテリーを表現するモデルの正確性を向上させるようにプローブ位置モジュール408によってプローブを配置させるようにすることもできる。
【０１８４】
マシンビジョンシステム は、3D画像内における所定のパターンの1つ以上のインスタンスの有無を決定し、見出されたインスタンスの各位置を決定するようにも構成され得る。この情報 は後続の検査（又は 他の）操作に使用されて、欠陥を探し及び/又は 部品拒否など他の操作を実行することができる。
【０１８５】
3D画像は、レーザ変位 センサ（プロファイラ）、立体カメラ、ソナー、レーザ又はLIDAR 距離測定カメラ、及び多様な 他の受動的又は能動的 距離検知 技術など多様な技術に基づく3Dカメラを用いて取得される。そのようなカメラはレンジ画像を生み出し、そこにおいて画像ピクセルの配列（典型的には直交するｘ軸とｙ軸に沿う位置として特徴付けられる）が生み出されるが、これは各ピクセルに対する第3の次元（高さ）（典型的にはｘ−ｙ面に対して垂直な軸に沿って特徴付けられる）も含んでいる。代替的に、そのようなカメラは撮像されたオブジェクトのポイントクラウド表示を生成できる。ポイントクラウドは、各点ｉを例えば（Ｘｉ、Ｙｉ、Ｚｉ）として表わすことができる空間における3D点の集合である。ポイントクラウドは、オブジェクトの背面及び側面、頂面及び底面を含む完全な3Dオブジェクトを表示できる。3D点（Ｘｉ、Ｙｉ、Ｚｉ）は、オブジェクトがカメラに見える空間内の位置を表わす。この表示において空の空間は点が存在しないことによって表わすことができる。
【０１８６】
幾つかの実施形態では、比較により、3Dレンジ画像表示Ｚ（ｘ、ｙ）は、深度又は高さＺが画像内の位置ｘ、ｙにおける輝度／明度Ｉに相当するものに取って代わられた2D画像表示Ｉ（ｘ、ｙ）に類似している。幾つかの実施形態では、レンジ画像は専ら直接カメラに対面するオブジェクトの正面を表示することができるが、その理由は単一の深度のみが任意の点位置ｘ、ｙと関連しているからである。レンジ画像は典型的にオブジェクトの背面又は側面、頂面又は底面を表示しないが、幾つかの実施形態では、レンジ画像はオブジェクトの背面又は側面、頂面又は底面も表示できる。レンジ画像は典型的に、カメラにそのような位置における情報が欠けている場合も、すべての位置（ｘ、ｙ）におけるデータを有するが、任意の点位置（ｘ、ｙ）におけるデータの欠如も表示することが可能である。レンジ画像は当業者にとって明白なやり方で3D点クラウドに変換することが可能である。
【０１８７】
3D画像内における所定の3D パターンの1つ以上のインスタンスの有無を決定するために、マシンビジョンシステムは、モデルを使用して見出された3Dパターンを表示することができる。 マシンビジョンシステムは、1つ以上の3D トレーニング画像から、又は位置が特定 され及び/又は 検査される3Dパターンの例を包含する幾何学的記述から合成される1つ以上の3D 画像から3Dパターン用のモデルを生成することができる。モデルが利用可能になると、マシンビジョンシステムはモデルをポーズの適切なセットの各々における3Dテスト画像と比較して、各ポーズでの整合 スコアを計算することができ、整合スコアにおける極大値 に対応する候補 ポーズを決定できる。マシンビジョンシステムは、整合スコアが適当な閾値を超える、3D画像内の3Dパターンのインスタンスとなるべき候補 ポーズを考慮することができる。
【０１８８】
3Dパターンの位置を特定するプロセスは、x-y-z位置（並進とも呼ぶ）、位置、配向 サイズ及び/又は回転自由度（例えばピッチ、ロール及びヨー）を含むがこれに限定されない多次元空間内で生じる。
【０１８９】
モデルは3Dプローブと呼ばれるデータ要素のセットを含むことができる。各 3Dプローブ は、3D画像内の与えられたポーズで特定の測定及びテストが行われる相対的位置を表わし、そのようなテストは各々関連する ポーズでパターン が存在することの証明に寄与する。3Dプローブ は、基礎をなす3Dパターンの構造（例えば表面）に対して実質的に垂直になるように配置することができる。
【０１９０】
トレーニング段階で、マシンビジョンシステムは3Dパターンの表面上にプローブを均等に配置することができる。例えば幾つかの実施形態では、マシンビジョンシステムは、隣接する3Dプローブ間の距離がすべての隣接する3Dプローブ対についてほぼ同一になるように3Dパターンの表面上に3Dプローブを配置するように構成され得る。本明細書において「均等配置法」と称するこの方法は、バランスが取れた配向プロファイル（例えば直交表面を有する3Dパターンと様々な配向を指し示す表面の割合が同様である）を有する3Dパターンをモデル化する際に効果的であり得る。例えば均等配置法は立方体の3Dパターンのモデル化に有用であり得るが、その理由は異なる配向（例えば上、下、左及び右）を指し示す3Dプローブの数が3D画像内の3Dパターンの各エッジ上でほぼ同じであり、それは3Dパターンの位置及び配向の正確な情報につながることができるからである。
【０１９１】
あいにく均等配置法は、バランスが取れていない配向プロファイルを有する3Dパターン（例えば面法線が考慮されるすべての自由度でアライメント情報を提供しない）のモデル化にはしばしば効果的ではない。例えば均等配置法は、概して細長い不規則なパイプ形状を有する3Dパターンをアライメントするにはそれほど効果的ではない。図19は、細長い不規則なパイプ形状を有する3Dパターンと、この3Dパターン上に均等に配置された3Dプローブを示す。境界1902が細長い不規則なパイプ形状を有しているので、均等配置法ではほとんどのプローブ1904が長い管1906の表面上に配置されるであろう。少数の3Dプローブ1904のみが、短い管1910上に配置されるであろう。また長い管の端部近くに配置されるプローブは少ないであろう。長い管1908の端部に近い3Dプローブの数が小さいので、3Dプローブに基づいて長い管のその中心軸に沿った位置を決定するのは困難である。更に、交差する短い管1910の表面上のプローブの数が比較的小さいので、この軸を中心とする回転の角度を決定することは困難である。加えて、3Dプローブ がオブジェクトの表面全体に均等に配置された場合、オブジェクトをすべての自由度でアライメントする能力 は等しくならない。例えば図19でパイプ全体に3Dプローブ 1904が均等に分布していると、長手方向及び円筒の中心軸周りの回転方向における 情報は比較的わずかしか与えられない。このことは、1つの特定の自由度をアライメントするのに利用可能な情報の量が比較的少ない場合には、アライメント アルゴリズムを誤りやすくすることがある。
【０１９２】
本明細書に記載される技術は、3Dプローブを3Dパターン上に3次元で配置するための自動化されたプローブ配置モジュールを提供することができる。幾つかの実施形態では、プローブ配置はx、y及びzにおいて分解する能力のバランスを取るように配分されることができる。幾つかの実施形態では、3並進自由度が3回転自由度と併せて一緒にバランスが取られる。加えて、幾つかの実施形態では、最小の回転成分を最大化することでx、y及びzのバランスが取られる。このプローブ配置モジュールは、3Dプローブが3D画像に示される3Dパターンを正確に表わすことができるように、3D画像の特徴点上に3Dプローブを配置するように構成される。このプローブ配置モジュールは、3Dプローブが3Dパターンの動きと関連するすべての自由度でバランスの取れた情報を抽出できるように、3Dプローブを配置するように構成でき、それによって3Dプローブから生成されるモデルの精度が向上する。例えば3Dパターンに関連付けられるオブジェクトが3次元で移動することが知られている場合、プローブ配置モジュールは、3Dプローブが3次元のバランスの取れた情報を抽出できるように、3Dプローブを配置することができる。プローブ配置モジュールはまた、3Dプローブが3Dパターンの形状にかかわらずバランスの取れた情報を抽出できるように、3Dパターンの形状を考慮することができる。このことは、図19に示すように3Dプローブが3Dパターンの表面全体に均等に配置される場合に、長い軸に沿った情報に比べてこの長い軸に対して直角の方向の自由度でより多くの情報を抽出するような、バランスの取れない情報を抽出する技術とは対照的である。種々の例示的な 図及び例 は、それらに続く説明と組み合わせて（例えば図19 に示された3D パターンに基づいて）用いられる。当業者は、例示的な 目的のためになされること、及び 任意の3D パターン が本明細書に記載された技術を用いて処理できることを認識するであろう 。
【０１９３】
図20は、幾つかの実施形態による、2D画像内の特徴点上に3Dプローブを配置するための高レベルプロセスを示す。特徴点は、3Dプローブに対する候補位置を示すことができる。例えばプローブ配置モジュール408 は、画像内の特徴点のサブセットを選択し、選択された特徴点のサブセット上に3Dプローブを配置するように構成され得る。
【０１９４】
ステップ2001で、プローブ配置モジュール408 は、3D画像から第1の複数の特徴点と関連付けられる複数の特徴を生成するように構成され得る。例えばプローブ配置モジュール408 は、特徴点検出モジュール406から、第1の複数の特徴点によって表される3D画像内の3Dパターンの表面を受信することができる。次にプローブ配置モジュール408 は、3D画像から、第1の複数の特徴点と関連付けられる複数の特徴を生成できる。
【０１９５】
ステップ2002で、プローブ配置モジュール408 は、少なくとも一部は複数の特徴点に基づいて第1の複数の特徴点の中から第2の複数の特徴点を選択できる。幾つかの実施形態では、選択プロセスの目標は、第2の複数の特徴点が3Dアライメントシステムに関して所望の集合特性を呈することである。幾つかの実施形態では、プローブ配置モジュール408 は、統計的モデルフィッティングと、本明細書において以下に詳述するモンテカルロ・サンプリング 技術を用いて第2の複数の点を選択できる。しかしながら、例えば第1の複数の点をそれらの特徴に関連するビンに仕分けし、次にそれらのビンから均等に点を選択することなど、他の選択技術が利用されてもよい。
【０１９６】
ステップ 2003で、プローブ配置モジュール408 は、少なくとも一部は第2の複数の特徴点に基づいて複数の3Dプローブの配置を決定できる。例えばプローブ配置モジュール408 は、第2の複数の特徴点の各々にプローブを配置することができる。 代替的に、別の実施形態では、プローブ配置 モデルは、例えば第2の複数の特徴点からの隣接する 特徴点の間に補間することによってプローブを配置してよい。
【０１９７】
幾つかの実施形態では、ステップ 2002の点選択プロセス により、所望の集合特性を達成する第2の複数の特徴点を選択することが可能になり、ステップ 2001で生成された特徴が 使用されてよい。 幾つかの実施形態では、各特徴点について、その特徴 は所望の集合特性への寄与を記述するものとなる。例えばアルゴリズムが3並進自由度の各々で3D パターンをアライメントする能力のバランスを取ろうと試みる場合、各点に対する特徴 ベクトルは3つの成分を有してよく、それらの各成分は3並進自由度の各々で3Dパターンを分解するアライメント アルゴリズムの能力への点の寄与を示すものであろう。他の例では、所望の集合特性は、単一の特定の回転自由度で分解する能力を最大化すると同時に、並進自由度の各々でアライメントする能力を保持することであってよい。 この場合は、特徴は特に 回転自由度での分解能への各 点の寄与を記述する情報も含む。 
【０１９８】
幾つかの実施形態では、図20の特徴 生成ステップ 2001は、図21aに示されたステップを含む方法に従って実行できる。幾つかの実施形態では、ステップ 2001 で計算される選択された 特徴は所望の集合特性の選択に依存して変化する。加えて、これらの特徴は多くの種々異なる仕方で数値化され、多くの種々異なる 方法を用いて計算されてよい。 
【０１９９】
例えば 幾つかの実施形態では、特徴生成プロセスは特徴点の位置及び/又は 面法線の方向を使用して、その集合 特性への寄与を数値化することがある。 特定の実施形態では、集合 特性は特定された 3並進自由度でアライメント能力を確実にすることであってよい。 これを達成するために、幾つかの実施形態では、ステップ 2004 は各点について面法線を計算することを含み、ステップ 2005は これらの特徴 ベクトルを取ってユークリッド座標系の回転を計算し（場合により主要 成分 解析を用いる）、及びステップ 2006は複数の面法線を、新しい座標系を定義する単位ベクトルに投影して複数の特徴 ベクトルに対する値を生み出すであろう。
【０２００】
他の実施形態では、集合 特性 は3つの回転座標系の各々の間のアライメント能力が最小化されたことを確実にするように選択されてよい。これを達成するために、特徴 ベクトルは 3つの成分を含んでよく、それらの各々はで3D パターンの回転座標系によって定義された1つの回転単位 ベクトルへの投影に等しくなるように設定されるであろう。 従って この例では、ステップ 2005は3D パターンの回転の中心及び回転の軸を計算することを含むであろう。
【０２０１】
別の実施形態では、面法線方向に対して直角の方向における点の寄与を数値化するのに有用であることがある。このことは、数値化されるべき平面に対して平行な方向でアライメントする場合に、平面のエッジに近いプローブサイトを（ その中心のプローブサイトとは反対に）比較的有用にすることができる。これと対照的に、幾つかの実施形態では、単純に面法線 ベクトルを使用することは、平面の表面に対して平行な自由度でのアライメントに対する情報を与えない。別の例では、図19 に示されたパイプの端部にプローブを配置することは、長軸に沿う方向でのアライメントを可能にしようが、中心に配置されたプローブはこの方向での情報を与えないであろう。 従って この場合は、特徴 生成プロセス は点のパイプの端部への近接及び最も近い エッジ又は端部への方向を数値化したがるであろう。 このために、幾つかの実施形態では、特徴 生成ステップ 2001 は、図21b に示されたステップに従って実行できる。
【０２０２】
ステップ 2101で、プローブ配置モジュール408 は各特徴点でそれぞれの点を中心とするN×N×N 領域内にあるすべての隣接点の位置を特定する。例えば点ｐcenterは、点ｐcenterを中心とする N×N×N 領域内に4つの点 p1、p2、p3及びp4を持つことができよう。
【０２０３】
ステップ 2102で、プローブ配置モジュール408は これらの隣接点をそれらの点の面法線に対して直角な表面に投影する。例えば点ｐcenterを中心とする N×N×N 領域内の4つの点 p1、p2、p3及びp4は、それらの点の面法線に対して直角な表面に投影されることができる。
【０２０４】
ステップ 2103で、プローブ配置モジュール408 は表面をピクセルグリッドに正則化し、その結果として 各ピクセルの値 はピクセル中心における平面からの深度に等しくなる。これをするために、プローブ配置モジュール408 は、図23A に示されているように、単位正方形から最も近い周囲の4つの投影された（任意に離間した）点への2D 双線形マッピングを見出し、次にこのマッピングの逆を使用してピクセルグリッド中心点を単位正方形内に配置する。この時点で、この逆 マッピングされた 中心点を使用する 双線形補間を用いて、ピクセルグリッド 位置に対する深度値を見出すことができる。図23Aに示されているように、点 ｐcenterｔ、p1ｔ、p2ｔ、p3ｔ及びp4ｔ は、点ｐcenter、p1、p2、p3及びp4のマッピングされた中心点で双線形補間によって得られる。特に、pi =（xi、yi）である場合、マッピングは8つの定数a1、a2、a3、a4、b1、b2、b3、b に関して次の通りパラメータ化できる。
2018055679.tif 000076
マッピングパラメータについて可解な 2つの連立方程式がある。点のセットに対する単位正方形からマッピングが得られたら、逆 マッピングを計算して単位正方形内にマッピングされたピクセルグリッド 中心の位置を見出す。逆マッピングは非線形であり、まず、次の通り定義：
2018055679.tif 000077
【０２０５】
ｐcenterｔの位置を得てステップ 2103に進むと、ここで位置を使用して4つの位置 p1、p2、p3及びp4の各々で深度の値の間に双線形補間を行い、ピクセルグリッド 中心に対する深度値を得る。
【０２０６】
ステップ 2103で、周囲の点が 利用できない場合（例えば点が表面のエッジにあるため）、N に等しい深度値を 使用できる。 
【０２０７】
従って ステップ 2103 は、ピクセルグリッドに正則化された深度マップを生み出すことができる。本明細書に記載された 技術を用いて、例えば円筒 2203の視地平に近い領域2202に対して図22 に示された深度マップ 2201を生成できる。
【０２０８】
ステップ 2104で、プローブ配置モジュール408は、深度マップから方向情報を抽出する。プローブ配置モジュール408はこのステップを、主軸2301（例えば図23B に示す）の角度を見出すことにより 次式で与えられる二次モーメントを用いて実行できる。
2018055679.tif 000078
【０２０９】
主軸（例えば図23Bに示された主軸2301）を得たらステップ 2105で、プローブ配置モジュール408は、図24に示されているように各軸に沿って規則的に離間したサンプリングを 実行する。図24は、線 2401を有する長軸に沿って補間された 深度と、線 2402を有する短軸に沿って補間された 深度を示している。次にサンプリングは特別式で採点されて軸に沿って分解能を数値化するための数値を与える（ここで分解能はこの方向におけるアライメント 情報の量を意味することができる。 例えば平坦な 表面の中心にある点は接平面内に包含される任意の方向で 有用なアライメント 情報を有していないが、降伏曲面のエッジにある点はエッジに対して垂直な方向で多くの情報を有する）。例えば上述した例（ステップ 2103）を続けると、長軸は左から右に向けられる。この軸に沿った サンプリング 値は、左側に向かって接平面 からの大きい相違を示し、これがエッジ 位置を示している。この例で分解能を 採点するために、プローブ配置モジュール408は、中心点の左では絶対 深度値の平均の最大値を選択し、中心点の右では 深度値の平均の最大値を選択するように構成され得る。そこで一方の軸に沿って補間された 絶対 深度を考慮するならば、
2018055679.tif 000079
【０２１０】
ステップ 2106で、プローブ配置モジュール408は（主軸の方向における）2D単位ベクトルを 3D領域内にバックマッピングする。プローブ配置モジュール408は、このステップを これらのベクトルを以前のステップ 2016で計算された分解能 によって最初にスケーリングする（例えば2D単位ベクトルに それぞれの分解能を乗じる） ことによって実行するように構成され得る。この例の最終 結果が図25 に示されており、そこでは 各点 2501 に面法線 ベクトルを表わす1本の線 2502と、接平面内の2本の直交 線 2503があり、これらの線の長さは分解能の一次成分と二次成分を示している。
【０２１１】
上記の手順を 各点について続けると、ここでは3つのベクトルu0、u1及びu2があり、その大きさ は空間内のオブジェクトを分解できることへの寄与を示している。この例におけるプロセスの全体目標は、並進自由度及び/又は 回転自由度の各々で等しい 決定 とロバスト性をもって3Dオブジェクトを分解するための登録プロセスを可能にする、これらの点のサブセットを選び出すことである。これをするために、プローブ配置モジュール408は、2つの確率分布を作成するように構成され得る。第1の確率分布は点のセットに適合され、データセットにおける それらの相対的 頻度を示している。第2の「目標」 分布は、モデル所望の特性を有する点のセットの相対的 頻度をモデル化するように作成される。その特性は、例えば点のセットが組み合わされたら3並進自由度での等しい 分解能を与えるようなものであり得よう。他の実施形態では、特性は回転自由度で分解する能力が 改善されると同時に、並進自由度での分解能間の差を最小化するようなものであってよい。
【０２１２】
分布からのプローブのサンプリング
【０２１３】
幾つかの実施形態では、プローブ配置モジュール408 は、プローブの目標分布からプローブをサンプリングすることによって、1個以上の特徴点上にプローブを配置するように構成され得る。プローブの目標分布は、パターンに関連付けられる自由度に対応する確率変数を含むことができる。例えばパターンに関連付けられるオブジェクトが3次元で移動することができる場合（例えば並進移動）、目標分布は3つの確率変数、即ち:x座標、y座標及びz座標（又は他の同等の表現）を有することができる。別の例としては、パターンに関連付けられる3Dオブジェクトが並進移動及び回転移動をすることができる場合、目標分布は6つの確率変数、即ち:x座標、y座標、z座標及び回転に対する3つの変数（例えば ピッチθ p、ロールθr及びヨーθy）を有しよう。
【０２１４】
幾つかの実施形態では、プローブ配置モジュール408 はTDCモジュール412を使用して目標分布を決定することができる。TDCモジュール412は、特徴点に関連付けられる特徴に基づいてプローブの目標分布を決定するように構成され得る。例えばTDCモジュール412は、例えば特徴点の座標、特徴点に関連付けられる垂直配向及び/又は、特徴点の回転の内の1つ以上に基づいて目標分布を決定することができる。
【０２１５】
幾つかの実施形態では、TDCモジュール412は、目標分布からサンプリングされる垂直配向の分布が実質的にバランスが取られるように、目標分布を決定するように構成される。例えば対象とするオブジェクトが細いパイプであるとしよう。そのようなオブジェクトの表面に均等に分布する点のセットは、その長手方向（例えば中心軸に沿う方向）とは反対に、その断面の平面内にはるかに多くの分解情報を含んでいる。それゆえ、このオブジェクトに対する目標分布 は、目標分布から抽出されるプローブのセットが組み合わされると長手方向よりも断面方向でより多くの等しい 分解情報を有するべきものである。そのようなセットにおける 大分部のプローブ 位置はパイプの両端に向かって位置決めされる。
【０２１６】
幾つかの実施形態では、TDCモジュール412は、目標分布が特徴点の分布と同様のサポートを有するように、目標分布を決定するように構成される。これが重要であり得るのは、例えばこれらの実施形態ではプローブ配置モジュール408 が、既存の特徴点のセットから再サンプリング（例えば重要度のサンプリング）することによってプローブをサンプリングするように構成され得るからである。このために以下に論じるように、TDCモジュール412は、特徴点の分布と目標分布の両方のための混合モデルを使用するように構成される。
【０２１７】
幾つかの実施形態では、TDCモジュール412は、目標分布をPDMモジュール414に提供し、PDMモジュール414は、目標分布からサンプルを抽出してプローブの位置を決定するように構成される。
【０２１８】
幾つかの実施形態では、FDCモジュール414は、x、y、z 確率変数を新しい座標 空間に変換するように構成される。このために、幾つかの実施形態では、FDC 414 は平均センタリングではなくPCAを使用して主要な 3D 空間軸を見出す。これによりこの例では残りのプロセスに対する3D 空間座標系が決定される。この例では、座標系は（x,y,z）と表示されるが、これはデカルト座標における新しい座標系に対する単位 ベクトルが
2018055679.tif 000080
であるように、（x,y,z）と表示される最初のデカルト座標を回転させたものである。この例では、FDC 414は平均センタリングを使用するように構成されてはならない。なぜなら、分解能の最大分散の方向で軸を選び出す必要はないであろうからである。むしろ、幾つかの実施形態では、最大分解能及び最小分解能の方向で軸をアライメントすることが望ましいことがある（例えば後でバランスの取れたプローブのセットを選択するため）。 言い換えれば、この例ではFDC 414 は、第1 軸がオブジェクトに対する最大 分解能の方向（主方向）に向けられる座標系の回転を見出すように構成され得る。定義により、他の2 軸の内の1つは最小分解能の方向にあり、従ってプローブ配置モジュール408は後で、この方向 での全体分解能を増加させる（例えば主方向における分解を犠牲にして）傾向のあるプローブ サイトを選択できるようになる。幾つかの他の実施形態では、このプロセスは 平均センタリングを使用しても実行できる。
【０２１９】
幾つかの実施形態では、プローブ配置モジュール408 が確率分布を規定する軸を決定したら、プローブ配置モジュール408は 点を分布に適合させる前にこの空間に投影する。例えば単一の点について、その特徴 ベクトルは次の通りであろう。
2018055679.tif 000081
上述した2Dの例との一貫性を保つために、xi は x 方向でオブジェクトを分解する能力への点の寄与の測定値と見なすことができ、yiはy 方向の測定値、及びziはz 方向の測定値である。
【０２２０】
目標分布 計算
【０２２１】
幾つかの実施形態では、オブジェクトが3自由度（例えば 3次元における並進移動）を用いてアライメントされる場合、TDCモジュール412は、次の関係を満たす重み付け関数f（x,y,z）を決定することが望ましいことがある。
2018055679.tif 000082
式中、iはi番目の特徴点を示す。この最適化ルーチンの目的は、（1）特徴点で測定された特徴ベクトルのx成分の重み付けされた合計と、（2）特徴点で測定された特徴ベクトルのy成分の重み付けされた合計と、（3特徴点で測定された特徴 ベクトルのz成分の重み付けされた合計とに等しい関数f（x,y,z）を特定することである。
【０２２２】
幾つかの実施形態では、TDCモジュール412が重み付け関数f（x,y,z）を決定すると、TDCモジュール412は、重み付け関数f（x,y,z）をPDMモジュール416に提供することができる。幾つかの実施形態では、重み付け関数は、PDMモジュール416が1個以上の特徴点上にプローブを配置するのに使用することができる確率分布の形態を取ることがある。この場合はPDMモジュール416が重み付け関数f（x,y,z）を、そこからプローブをサンプリングするための確率分布として使用するので、それは非負に制約されなければならず、少なくとも幾つかのサポートされた領域については正になり得る。「目標分布」は本明細書においてf（x,y,z）と表示される確率分布であることができる。
【０２２３】
幾つかの実施形態では、重み付け関数が幾つかの他の手段によって選択されたプローブの既存のセットを重み付けするのに使用されて、以下の通り最小化するように相対的重要度に影響を与える。
2018055679.tif 000083
【０２２４】
幾つかの実施形態では、パターンが6自由度を有する場合（例えば3次元における並進移動と回転移動）、TDCモジュール412は回転移動に対応する回転変数θp、θr及びθyを目標分布に組み込むことができる。TDCモジュール412は原点及び軸のセットに対する回転変数θp、θr及びθyを規定することができる。
【０２２５】
幾つかの実施形態では、バランシング 技術を3回転自由度に適用するために、回転の中心及び回転の軸が 見出される。例えばプローブ配置モジュール408は、法線ベクトルの回転 モーメントの合計を最小化する点を見出し、次に同じ 基準を用いて個々の軸を見出すことによって、回転の中心を見出すように構成され得る。
【０２２６】
例えば図26に示されているように、幾つかの実施形態では、回転の中心 cを見出すために、プローブ配置モジュール408 は、ポイントクラウド内のすべての面法線 ベクトルniの回転のモーメントを最小化する点を見出す。単一の法線ベクトルniに対する点 cを中心とした回転のモーメントは、次式によって 与えられる。
［ｎｉ×（ｐｉ−ｃ）］
次に、回転の中心を見出すために、技術は次の通り最小化できる。
前式 は 次の通り書き直すことができる。
2018055679.tif 000084
ここで、回転の中心 cにより、a =bt+cによって与えられる回転軸周りの法線ベクトルのモーメントは、次式によって与えられる。
ｂ．［ｎｉ×（ｐｉ−ｃ）］
それゆえ回転の軸は、次式によって与えられる対称行列のゼロ空間を見出すことによって見出すことができる。
2018055679.tif 000085
【０２２７】
しかしながら、大部分が 回転対称であるオブジェクトがある場合があり得る（例えば図19の画像）。そのような場合、プローブ 選択プロセスはプローブを、この対称性を壊す点 に割り当てることができる。それゆえ 幾つかの実施形態では、第1の例で回転の主軸が管の中心を通って配置され、交差要素の無関係な特徴に向かってバイアスがかけられないことが望ましい。幾つかの実施形態では、当業者に知られているように RANSAC アルゴリズムを用いて（しかし上述したのと同じ基準 に基いて）回転の軸を見出すことができる。 他の実施形態では、ベイズのパラメータ推定問題として課される回転の中心と軸の推定に例えばモンテカルロ 技術が用いられてよい。
【０２２８】
図27 は、RANSAC アルゴリズムを使用して回転の軸 2703を見出すオブジェクトの例を図示している。 図27 は、プローブ 2701及び点 2702を示している。RANSAC アルゴリズムを反復する度に4個の点のサブセットをランダムに選択する。 これらの点を使用して提案された 回転の中心 と回転軸のセットを計算する。回転の中心が点の境界ボックスの外部にあることが見出されて1x拡大される場合は、この提案は拒否される。内部にある点 は、次の通り正規化された ドット積を 閾値化することによって検出できる。
2018055679.tif 000086
式中、aiは提案された 主回転軸（図26に示されている）上にある。内部にある点のセットが得られたら、新しい 回転の中心及び回転軸のセット が 生成及び使用されてモデルの適合を 測定できる。モデルの適合 は、すべての候補と内部にある点に対する上記の正規化されたドット積を合計することによって計算できる。
【０２２９】
アライメント モデルが単一の視野で記録された画像から訓練される用途において、曲面は撮像 デバイスにはっきり見える地平点を有することがある。例えば円筒の表面のごく一部のみがカメラに可視であることがある。プローブをこれらの水平 エッジに近づけて配置することは、あまり望ましくない。例えば円筒をその中心 軸周りで回転させると、1つの底縁に沿うすべてのプローブは視野から消える。アライメントアルゴリズムは回転自由度と並進自由度の両方で検索する可能性があるので、幾つかの実施形態では、できるだけ多くのプローブサイトが 全検索範囲にわたって可視であることが望ましい。
【０２３０】
幾つかの実施形態では、プローブサイトを選択する際に地平点を考慮から除くことができる。幾つかの実施形態では、点が実際に地平点である場合は、2つの条件の内の1つ又は両方を使用して 決定することができる。例えば図26を参照して、点 piが地平点である第1の条件 は、回転単位 ベクトルの1つを有するその面法線のドット積 が、所定の閾値、例えば コサイン（85.0）より小さくなければならないというものである。言い換えれば、この例ではその面法線が図19の[pi - ai]についてほぼ平行である点のみ考慮されよう。この例で続けると、第2の条件は、点が回転の方向、例えば ｕｒｏｔにおける表面のエッジに近くなければならないというものである。このことを確認するために、可能な各地平点（例えば第1の条件を満たす点）について、ステップ 2001-2003を適用して点 piにおける接平面に対する表面深度値の正則化されたグリッドを得ることができる。双線形マッピングを使用して方向ｕｒｏｔに沿う規則的に離間したサンプリングを実行できる。これはステップ 2005で行われたサンプリングと同様であり、相違しているのは方向である。閾値を1-d 信号に適用することにより、piが可視 表面のエッジに近いかどうかに関して決定できる。 閾値は欠けている ピクセル値に対して使用される値に依存するが、N（ステップ 2003で提案）を使用する場合は、この例では0.9 Nが合理的であろう。別の実施形態では、他の値を 使用できよう。例えば閾値 は 0.7 N 〜N、より好ましくは0.85 N〜0.95 Nであることができよう。更に別の実施形態では、他の閾値を使用することができる。
【０２３１】
図28A及び28Bは、幾つかの実施形態による、地平点除去のないプローブ配置及び地平点除去のあるプローブ配置を図示している。具体的に言うと、図28Aは地平点除去のないプローブ配置を図示し、図28Bは幾つかの実施形態に従う地平点除去のあるプローブ配置を図示している。図28A及び28B はプローブ 2801及び点 2802を示している。図28Bは、例えば図28Aの地平点 2803を含んでいない ことに留意されたい。
【０２３２】
幾つかの実施形態では、回転の中心 c と回転軸が 決定されると（それらのそれぞれの単位 ベクトル
2018055679.tif 000087
によってパラメータ化される）、TDCモジュール412 は、原点からi番目の特徴点の中心までのベクトルである、i番目の特徴点の位置ベクトルｐiと、以前計算された 分解能 ベクトルｕｉ０、ｕｉ１及びｕｉ２を使用して、回転変数θp、θr及びθyを次の通り決定することができる。
2018055679.tif 000088
【０２３３】
図29は、θｐｉの計算に関係のある ベクトルを示しており、これはｕｉ０、ｕｉ１及びｕｉ２を回転 単位 ベクトル
2018055679.tif 000089
に投影した合計の大きさと見なされる。
【０２３４】
幾つかの実施形態では、回転変数θｐｉは、点と回転軸との距離、即ちベクトルｄｉθｐのノルムを考慮に入れることができる。
2018055679.tif 000090
であるため、TDCモジュール412は、角度精度を上げるために、原点から更に離れた特徴点の寄与を強調することができる。例えばTDCモジュール412はi番目の特徴点の回転変数θｐｉを次の通り決定することができる。
2018055679.tif 000091
位置ベクトルviのノルムに依存する回転変数θｐｉは、回転の軸から更に離れた位置にプローブを配置するのに有利になるような目標分布を提供することができる。このようにして、目標分布により回転の中心から更に離れた特徴点でより多くのプローブをサンプリングすることができる。
【０２３５】
幾つかの実施形態では、TDCモジュール412が回転変数に対する表示を決定すると、TDCモジュール412は決定された表示を使用して各特徴点を表示することができる。次いで、TDCモジュール412は、次の関係を満たす重み付け関数ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）を見出すことによって特徴点の表示に基づいて目標分布を決定するように構成され得る。
2018055679.tif 000092
式中、iはi番目の特徴点を示す。これは並進自由度と回転 自由度の両方で部品を分解する能力のバランスを一緒に取る効果を有することができる。
【０２３６】
幾つかの実施形態では、TDCモジュール412 は、特徴点の完全なセット、即ち
2018055679.tif 000093
それら以外の場合はロールを使用する最小の分解情報を有することが見出された回転自由度での分解能を最大化することで並進自由度での分解能力のバランスを一緒に取る重み付け関数ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）を見出すことによって、特徴点の表示に基づいて目標分布を決定するように構成され得る。このことは、例えば 1つの回転変数が小さいために、他の2つの回転関数の寄与を最小化することによって3つの回転変数の間の不一致を低減する前述した最適化を引き起こすという 条件下で有利であり得る。これはほとんどのプローブを回転の中心近くに配置する望ましくない効果を有することがある。 
【０２３７】
幾つかの実施形態では、TDCモジュール412 は、次の最適化を実行することによって回転自由度での分解能を最大化することで並進自由度での分解能のバランスを取る重み付け関数ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）を決定するように構成され得る。
2018055679.tif 000094
さらに、パラメータwS とwR は、並進成分間の差の最小化と、最小の回転成分の最大化との間の最適化における相対的 バイアスを規定する。
【０２３８】
幾つかの実施形態では、TDCモジュール412 が目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）を決定したら、TDCモジュール412 は目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）をPDMモジュール416に提供できる。次いで、PDMモジュール416は目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）を確率分布として使用してパターン上のプローブをサンプリングする。
【０２３９】
幾つかの実施形態では、上記の最適化プロセスを 容易にするために、プローブ配置モジュール408は目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）に対する関数形態を仮定できる。
【０２４０】
幾つかの実施形態では、プローブ配置モジュール408 は線形形態を有する目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）を仮定することができる。線形関数は負になり得るが、
2018055679.tif 000095
によって、目標分布はすべての特徴点で正であることが強制され得る。目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）が線形形態を有する場合、目標分布を見出すための最適化ルーチンは線形形態を使用するように構成され得る。しかしながら線形関数のスペースは限られるため、すべての制約を満足する線形関数を見出すことは困難になることがある。
【０２４１】
幾つかの実施形態では、プローブ配置モジュール408は、目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）が非線形形態を有すると仮定することができる。目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）が非線形形態を有する場合、目標分布を見出すための最適化ルーチンは非線形形態を使用するために別様に構成されてよい。しかしながら非線形関数のスペースは広いので、すべての制約を満たす非線形関数を見出すことの方が容易であろう。
【０２４２】
幾つかの実施形態では、TDCモジュール412は、目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）を特徴点分布pp（x,y,θ|パラメータ）の逆数として設定することができる。この場合、TDCモジュール412はFDCモジュール414から特徴点分布pp（x,y,z,θp,θr,θy）を受信し、逆数を計算することによって間接的に目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）を決定することができる：ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）＝１／pp（x,y,z,θp,θr,θy）。例えば目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）が特徴点分布pp（x,y,z,θp,θr,θy）の逆数として定義されたら、目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）により、残りの特徴点に比べて比較的似ていない特徴点を有する位置でより多くのプローブがサンプリングされるようになる。
【０２４３】
幾つかの実施形態では、FDCモジュール414は、特徴点分布pp（x,y,z,θp,θr,θy）を混合モデルとしてモデル化することができる。幾つかの実施形態では、混合モデルは次のガウス混合モデル（GMM）を含むことができる。
2018055679.tif 000096
GMMは4つのパラメータ、即ちガウス分布の数N、k番目のガウス分布の加重値αｋ、k番目のガウス分布の平均ベクトル
2018055679.tif 000097
、及びk番目のガウス分布の共分散行列
2018055679.tif 000098
を有する。他の実施形態では、混合モデルは三角分布の混合を含むことができる。幾つかの実施形態では、三角分布の混合はより速く計算することができ、特徴点の柔軟なグルーピングを提供するという同様に望ましい特性を与えることができる。
【０２４４】
幾つかの実施形態では、FDCモジュール414は、特徴点のクラスタリング及び特徴点に最も適合するクラスタの数の判定により、GMMのためのガウス分布の数を推定することができる。例えばFDCモジュール414は特徴点上でk平均クラスタリング操作を実行して、ガウス分布の数Nを推定することができる。
【０２４５】
残りのパラメータのセット
2018055679.tif 000099
は、特徴点に与えられるパラメータの尤度を最大化することによって決定することができる。幾つかの実施形態では、FDCモジュール414は期待値最大化技術を用いて、特徴点に与えられたパラメータの尤度を最大化することができる。期待値最大化を実行するために、FDCモジュール414はクラスタリングステップの結果を使用して、パラメータのセット
2018055679.tif 000100
を初期化することができる。
【０２４６】
上述したように、TDCモジュール412は、特徴点分布pp（x,y,z,θp,θr,θy）を単純に逆にすることによって目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）を決定することができる。しかしながら、この目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）は、極めて稀なｘ，ｙ，ｚ，θｐ，θｒ，θｙの値を有するエッジ上にほとんどのプローブを配置させることがある。例えばオブジェクトが3Dの並進移動のみ行うことが可能であり、オブジェクトが角の丸い矩形の境界を有する場合、この目標分布f（x,y,z）はPDMモジュール416にほとんどをコーナー位置の周りでサンプリングさせることがある。そのような シナリオでは、コーナー位置のみにプローブが配置されたアライメント モデルは 遮蔽及びノイズに対して脆弱であろう。
【０２４７】
そのような問題に対処するために、幾つかの実施形態では、TDCモジュール412は特徴点分布pp（x,y,z,θp,θr,θy）を変形し、変形された特徴点分布を逆にして目標分布ｆ（ｘ，ｙ，ｚ，θｐ，θｒ，θｙ）を決定することができる。この変形は平滑化カーネルをpp（x,y,z,θp,θr,θy）に適用する形態を取る。
【０２４８】
幾つかの実施形態では、TDCモジュール412は逆にする以外の方法によって特徴点分布を変形することによって目標分布を決定することができる。そのような1つの実施形態は、特定の条件を満たす新しい加重値
2018055679.tif 000101
を見出すことによって特徴点分布
2018055679.tif 000102
を変形することができる。パラメータのセット
2018055679.tif 000103
を推定する際に、TDCモジュール412は特徴点の柔軟なグルーピング（例えばガウス分布への柔軟なグルーピング）を実行できる。TDCモジュール412がこれらのグルーピングを実行したら、TDCモジュール412は新しい加重値
2018055679.tif 000104
を見出して各グループ（例えば各ガウス分布）を個別に再重み付けするように構成され得る。
【０２４９】
例えばTDCモジュール412は
2018055679.tif 000105
【０２５０】
幾つかの実施形態では、最適化の並進成分と回転成分との相対的重み付けを単一のパラメータRBIAS及び加重値に対する以下の式を用いて設定できる：
2018055679.tif 000106
【０２５１】
RBIASを変化させることがプローブ配置に及ぼす効果が、図30A〜図30Cに示す例で図示されている。図30A はバイアスが適用されない例を示しており、図30Bは並進バイアスが適用される例を示しており、図30Cは回転バイアスが点 3002上のプローブの配置 3001 に適用される例を示している。図30Aと比較すると、図30B は端部3003及び区域 3004の近傍により多くのプローブを含んでおり、このことは管の中心 軸に対して平行な方向でのモデルの分解能を増加させる。図30Aと比較すると、図30Cは小さい 交差 管 3010の頂部により多くのプローブを含んでいる。これらのプローブ 位置は、本管の中心 軸周りの回転自由度で分解するモデルの能力を増加させる。
【０２５２】
幾つかの実施形態では、TDCモジュール412は、追加的な制約を用いて
2018055679.tif 000107
に関する最小化を解くことができよう。例えば、上述した技術は変形された加重値
2018055679.tif 000108
が負になることを妨げないか、又は大きい加重値
2018055679.tif 000109
が特徴点の小さいグループ（例えば特徴点分布pp（x,y,z,θp,θr,θy）におけるその元の加重値αｋが小さかった）から推定されたガウスに割り当てられることを妨げない。TDCモジュール412は、これら及び/又は他の制約をプログラムによって適用することができる。
【０２５３】
また、幾つかの実施形態では、TDCモジュール412は、プローブの最終セットにおいて過度に又は不十分に表示されることがある個々のクラスターの量を制限するように構成される。これは次の制約のセットを追加することによって達成できる。
2018055679.tif 000110
式中、Climは制限係数を与える定数である。
【０２５４】
制限係数を変化させる効果の例が 図31A 〜図31Dに図示されている。図31Aは分解能を有する 点 3103の例を示している。詳細図の区域3104は、点が視地平に近づくに連れて、管中心 軸周りの回転分解能が増加していることを図示している。これらの「地平点」は、プローブ位置を選択する際に考慮から除外される。詳細図の第2の区域3105は、特徴点が管の端部に近づくに連れて、管中心軸に平行な分解能が増加することを示している。図31Bは、Clim= 1.2によるプローブ 選択の結果の例を示している。このプローブセットは、ランダムに選択されたプローブのセットよりもごく僅かバランスが取れているに過ぎない。 図31Cは、Clim= 4によるプローブ 選択の結果の例を示している。ここではプローブサイト は 管の端部と側部に向かってより多く重み付けされているのが見て取れる。 図31Dは、Clim= 10によるプローブ 選択の結果の例をプローブ 3101及び点 3102で示している。ここでは 大分部のプローブサイトが管の端部にある。図31Aから図31Dに見ることができるように、制限係数が増加すると、プローブサイトは管の端部に向かってより多く集中する。制限係数が増加するとよりバランスの取れたプローブのセットが生み出されるが、モデルのロバスト性は遮蔽領域に対してますます弱くなる（例えば実行時に管の一方の端部が見えなくなる）。 
【０２５５】
幾つかの実施形態では、連立方程式（例えばラグランジュの微分によって形成され ゼロに等しい）が制約に違反する少なくとも1つの加重値αｋを有する結果を生む場合、TDCモジュール412 は、境界 ケースの可能なあらゆる組合せで反復し、最適な残りの加重値を計算し、及び制約された 最小値を選択するように構成され得る。
【０２５６】
例えばTDCモジュール412は、線形方程式についてすべての可能な境界条件のセット
2018055679.tif 000111
を決定することができる。境界条件の各セットは、変形された加重値
2018055679.tif 000112
のサブセットに対する境界条件を含むことがある。次いで、境界条件の各セットについて、TDCモジュール412は、加重値
2018055679.tif 000113
のサブセットの値を対応する境界条件の値に固定し、境界条件のない残りの自由な加重値
2018055679.tif 000114
について連立線形方程式を解くことができる。このようにして、TDCモジュール412はすべての可能な境界条件のセットの下での解の中から最小スコアの解を選択することによって、制約が与えられた連立線形方程式の大域解を決定することができる。
【０２５７】
場合によっては、GMMにおけるガウス分布の数が、特徴点がある範囲の数より大きい場合、GMMにおけるパラメータの幾つかは線形従属であることがある。例えばガウス分布の数が、特徴点がある範囲の数より大きい場合、ガウス分布の平均ベクトルは線形従属になることがある。
【０２５８】
この問題に対処するために、TDCモジュール412は、例えばティホノフ正則化を用いてGMMに対するパラメータを正則化するように構成され得る。そのような方策が失敗した場合、TDCモジュール412は、次の関数を最小化するために最適化の問題を再公式化することができる。
2018055679.tif 000115
この新しいラグランジュの公式は、解が並進自由度で完全にバランスが取られており、変形された加重値の合計が1であるという制約条件の下で、最小の適合した分解能を有する回転自由度での分解能を最大化することを求める。
【０２５９】
幾つかの実施形態では、TDCモジュール412は、上述したラグランジュの関係を満たす加重値を直接見出すことができよう。しかしながら、前述のようにこの関係は加重値
2018055679.tif 000116
が負になることを妨げず、又は大きい加重値
2018055679.tif 000117
が特徴点の小さいグループ（例えば特徴点分布pp（x,y,z,θp,θr,θy）における元の加重値αｋが小さかった）から推定されたガウスに割り当てられることを妨げないことがある。TDCモジュール412は上述したように、これらの制約をプログラムによって適用することができる。これは数学的に有効であるが、その理由は
2018055679.tif 000118
における上記のラグランジュの関係が二次式であり、加重値
2018055679.tif 000119
の1つが負である場合、最適値は1つ（以上）の境界条件にあることになるからである。
【０２６０】
要約すると、特徴点分布pp（x,y,z,θp,θr,θy）のパラメータに基づいて目標分布
2018055679.tif 000120
のパラメータを特定するために、TDCモジュール412は以下の手順を使用することができる。
１．ラグランジュを微分することによって形成されるゼロに等しい線型方程式系を解く。
2018055679.tif 000121
２．この系が特異である場合、TDCモジュール412は正則化を用いてこの系を解くことができる。例えばTDCモジュール412は行列方程式
2018055679.tif 000122
を解くことができる。このようにして、TDCモジュール412は解ベクトルのＬ２ノルムの合計を最小化することができ、ひいては大きい正及び負のαｋ（合計して単一性になる）を有する解を妨げることができる。
３． ステップ2に失敗した場合は、代替ラグランジュを微分することによって形成されるゼロに等しい線型方程式系を解く。
2018055679.tif 000123
４．ステップ2又はステップ3の解を次の制約と照合する。
2018055679.tif 000124
５．解が加重値
2018055679.tif 000125
の有効範囲外にある場合、すべての可能な境界条件（例えば制約）のセットについて、ステップ2又は3の修正版を使用して制約されていない
2018055679.tif 000126
に対する解ベクトルを見出す。TDCモジュール412は検索を通して、次式の最小値を追跡することができる。
2018055679.tif 000127
前者の関係がゼロより大きい場合、TDCモジュール412は前者の関係を用いて
2018055679.tif 000128
に対する解ベクトルを選択することができる。前者の関係がゼロより大きくない場合、TDCモジュール412は、後者の関係を用いて
2018055679.tif 000129
に対する解ベクトルを選択することができる。
【０２６１】
目標分布からのプローブのサンプリング 
【０２６２】
TDCモジュール412が変形された特徴点分布
2018055679.tif 000130
を決定すると、TDCモジュール412は変形された特徴点分布
2018055679.tif 000131
（又は変形された特徴点分布の逆数）をPDMモジュール416に提供することができる。次いで、PDMモジュール416は変形された特徴点分布
2018055679.tif 000132
の逆数からサンプリングして、画像内の1個以上の特徴点のプローブの位置を決定することができる。
【０２６３】
TDCモジュール412は変形された特徴点分布
2018055679.tif 000133
に関するx、y及びzの期待値ができるだけ同様になるように、変形された特徴点分布
2018055679.tif 000134
を選択するように構成される。
2018055679.tif 000135
【０２６４】
重要度のサンプリングにより、PDMモジュール416は、別の異なる分布から抽出されたサンプルを、同様のサポートを有するサンプルの条件で重み付けすることによって、目標分布からサンプルを抽出することができる。換言すると下記式のとおりであり、
2018055679.tif 000136
式中、Ｓprobesはプローブのセット、ＳIPは特徴点のセットである。それゆえPDMモジュール416は、この関係を用いて次式により特徴点分布
2018055679.tif 000137
から抽出されたサンプルの重み付けをすることができる。
2018055679.tif 000138
【０２６５】
開示の主題は、その用途において、以下の説明で述べた又は図面に示した構成の詳細及び成分の配置に限定されないことを理解されたい。開示の主題は、他の実施形態も可能であり、また、様々な方法で実施及び実行することができる。また、本明細書で使用されている言い回し及び用語は説明を目的とするものであり、限定するものとして見なされるべきではない。
【０２６６】
同様に、当業者は、本開示が基づく概念は、開示の主題の幾つかの目的を実行するための他の構造、方法及び装置を設計するための基礎として容易に利用できよう。それゆえ特許請求の範囲が、開示の主題の趣旨及び範囲から逸脱しない限り、そのような同等の構造を含むものと見なされることが重要である。例えば開示された実施形態の幾つかは、1つ以上の変形形態に関する。この関係は、数理的方程式を用いて説明され得る。しかし、当業者は、1つ以上の変形形態の間の同じ関係を、開示の数理的方程式を変形することにより、異なる数理的方程式を用いて表現することもできる。特許請求の範囲が、1つ以上の変形形態の間のそれらの均等の関係も含むものと見なされることが重要である。
【０２６７】
開示の主題は、上述の例示的な実施形態において記載及び図示されたが、本開示は例としてのみ行われたものであり、開示の主題の実施の詳細の多くの変更は、開示の主題の精神と範囲を逸脱することなく行うことができる。
【図１】
2018055679.tif 000139
【図２】
2018055679.tif 000140
【図３】
2018055679.tif 000141
【図４】
2018055679.tif 000142
【図５】
2018055679.tif 000143
【図６Ａ】
2018055679.tif 000144
【図６Ｂ】
2018055679.tif 000145
【図６Ｃ】
2018055679.tif 000146
【図６Ｄ】
2018055679.tif 000147
【図６Ｅ】
2018055679.tif 000148
【図６Ｆ】
2018055679.tif 000149
【図６Ｇ】
2018055679.tif 000150
【図６Ｈ】
2018055679.tif 000151
【図７】
2018055679.tif 000152
【図８】
2018055679.tif 000153
【図９】
2018055679.tif 000154
【図１０】
2018055679.tif 000155
【図１１Ａ】
2018055679.tif 000156
【図１１Ｂ】
2018055679.tif 000157
【図１２Ａ】
2018055679.tif 000158
【図１２Ｂ】
2018055679.tif 000159
【図１３】
2018055679.tif 000160
【図１４Ａ】
2018055679.tif 000161
【図１４Ｂ】
2018055679.tif 000162
【図１５Ａ】
2018055679.tif 000163
【図１５Ｂ】
2018055679.tif 000164
【図１６Ａ】
2018055679.tif 000165
【図１６Ｂ】
2018055679.tif 000166
【図１７Ａ】
2018055679.tif 000167
【図１７Ｂ】
2018055679.tif 000168
【図１７Ｃ】
2018055679.tif 000169
【図１８Ａ】
2018055679.tif 000170
【図１８Ｂ】
2018055679.tif 000171
【図１９】
2018055679.tif 000172
【図２０】
2018055679.tif 000173
【図２１Ａ】
2018055679.tif 000174
【図２１Ｂ】
2018055679.tif 000175
【図２２】
2018055679.tif 000176
【図２３Ａ】
2018055679.tif 000177
【図２３Ｂ】
2018055679.tif 000178
【図２４】
2018055679.tif 000179
【図２５】
2018055679.tif 000180
【図２６】
2018055679.tif 000181
【図２７】
2018055679.tif 000182
【図２８Ａ】
2018055679.tif 000183
【図２８Ｂ】
2018055679.tif 000184
【図２９】
2018055679.tif 000185
【図３０Ａ】
2018055679.tif 000186
【図３０Ｂ】
2018055679.tif 000187
【図３０Ｃ】
2018055679.tif 000188
【図３１Ａ】
2018055679.tif 000189
【図３１Ｂ】
2018055679.tif 000190
【図３１Ｃ】
2018055679.tif 000191
【図３１Ｄ】
2018055679.tif 000192
【外国語明細書】
2018055679000001.pdf