(57)【特許請求の範囲】
【請求項１】
メモリに格納されるコンピュータプログラムを実行するように構成されるプロセッサであって、前記プロセッサは、
特徴点検出モジュールを使用して画像から複数の特徴点を定めることと、
特徴点検出モジュールと繋げられるメモリ内に格納されたプローブ配置モジュールを使用して、前記画像中の特徴点の分布を示すデータを含む、前記複数の特徴点の特徴点分布を定めることと、
前記プローブ配置モジュールを使用して複数のプローブの目標分布を定めることであって、前記複数のプローブの各プローブは、パターンの一部をモデル化するのに利用されると共に、前記目標分布は１つまたは複数の特徴点上の前記プローブの所望の配置を示すことと、
前記プローブ配置モジュールを使用して、少なくとも部分的に前記特徴点分布に基づき１つまたは複数の前記特徴点上の前記複数のプローブの配置を定めて、前記複数のプローブと、関連する配置とを含む、前記パターンのためのモデルを生成するために、前記複数のプローブの分布を前記目標分布に整合させることと、
を行うように構成されるプロセッサを備える、機械視覚システム。
【請求項２】
前記プロセッサはさらに、
前記複数の特徴点における配向を定めることと、
特定の配向を有する特徴点の数を示す配向のヒストグラムを定めることと、
を行うように構成される、請求項１に記載の機械視覚システム。
【請求項３】
前記プロセッサはさらに、
平滑化関数を使用して前記配向の前記ヒストグラムを平滑化するように構成される、請求項２に記載の機械視覚システム。
【請求項４】
前記平滑化関数には、配向ドメインにおける円形カーネルが含まれる、請求項３に記載の機械視覚システム。
【請求項５】
前記円形カーネルには、コサイン関数が含まれる、請求項４に記載の機械視覚システム。
【請求項６】
前記プロセッサはさらに、
寸法のすべてにおいて等しくバランスが取られる前記複数のプローブを見出すように構成される、請求項１に記載の機械視覚システム。
【請求項７】
前記特徴点は、前記複数のプローブによってモデル化されたパターンの境界と関連付けられ、前記特徴点は、前記境界に沿う弧と関連付けられ、前記プロセッサはさらに、
第１のプローブを第１の特徴点に配置することと、
前記第１の特徴点とほぼ同様の配向を有する特徴点の数に基づき、前記第１の特徴点の弧の長さを調整することと、
前記第１の特徴点の前記弧の前記調整された長さに基づき、第２の特徴点に第２のプローブを配置することと、
を行うように構成される、請求項１に記載の機械視覚システム。
【請求項８】
前記プロセッサはさらに、前記複数の特徴点の前記配向の前記分布を、混合モデルを含む確率分布の混合に合わせるように構成される、請求項２に記載の機械視覚システム。
【請求項９】
前記プロセッサはさらに、前記複数の特徴点を少なくとも１つのクラスタにクラスタリングすることにより、前記特徴点分布の前記混合モデルの構成要素の数を定めるように構成される、請求項８に記載の機械視覚システム。
【請求項１０】
前記プロセッサはさらに、前記特徴点分布の混合モデルの加重値を調整して、少なくとも１つのモーメントが考慮される寸法のそれぞれにわたってほぼ等しい特性を有する前記目標分布を定めるように構成される、請求項８に記載の機械視覚システム。
【請求項１１】
前記プロセッサはさらに、前記目標分布を特徴点の配向の分布比に使用して、前記特徴点をサンプリングし直し、前記複数のプローブを生成するように構成される、請求項１に記載の機械視覚システム。
【請求項１２】
前記特徴点分布および前記目標分布は、寸法の所定のセット上の分布を含み、前記寸法の所定のセットは、ユークリッドの寸法または円柱状の寸法の１つを含む、請求項１に記載の機械視覚システム。
【請求項１３】
機械視覚システムの特徴点検出モジュールを使用して画像からの複数の特徴点を定めることと、
前記機械視覚システムの前記特徴点検出モジュールと繋げられるプローブ配置モジュールを使用して、前記画像中の特徴点の分布を示すデータを含む、前記複数の特徴点の特徴点分布を定めることと、
前記プローブ配置モジュールを使用して複数のプローブの目標分布を定めることであって、前記複数のプローブの各プローブは、パターンの一部をモデル化するのに利用されると共に、前記目標分布は１つまたは複数の前記特徴点上のプローブの所望の配置を示すことと、
前記プローブ配置モジュールを使用して、少なくとも部分的に前記特徴点分布に基づき１つまたは複数の前記特徴点上の前記複数のプローブの配置を定めて、前記複数のプローブと、関連する配置とを含む、前記パターンのためのモデルを生成するために、前記複数のプローブの分布を前記目標分布に整合させることと、
を含む、方法。
【請求項１４】
前記特徴点分布を定めることは、
前記複数の特徴点における配向を定めることと、
特定の配向を有する特徴点の数を示す前記配向のヒストグラムを定めることと、
を含む、請求項１３に記載の方法。
【請求項１５】
平滑化関数を使用して、前記配向の前記ヒストグラムを平滑化することをさらに含む、請求項１４に記載の方法。
【請求項１６】
考慮される寸法のすべてにおいて等しくバランスが取られる前記複数のプローブを識別することをさらに含む、請求項１３に記載の方法。
【請求項１７】
前記特徴点は、前記複数のプローブによってモデル化されたパターンの境界に関連付けられ、前記特徴点は、前記境界に沿う弧と関連付けられ、少なくとも部分的に特徴点分布基づき前記複数のプローブの配置を定めることは、
第１のプローブを第１の特徴点に配置することと、
前記第１の特徴点と実質的に同様な配向を有する前記特徴点の数に基づいて前記第１の特徴点の弧の長さを調整することと、
前記第１の特徴点の前記弧の前記調整された長さに基づいて第２のプローブを第２の特徴点に配置することと、
を含む、請求項１３に記載の方法。
【請求項１８】
特徴点分布を定めることは、前記複数の特徴点を、混合モデルを含む確率分布に合わせることを含み、前記確率分布は少なくとも、前記複数の特徴点において測定された配向の分布を示す、請求項１３に記載の方法。
【請求項１９】
前記複数の特徴点を少なくとも１つのクラスタにクラスタリングすることにより、前記特徴点分布の前記混合モデルの構成要素の数を定めることをさらに含む、請求項１８に記載の方法。
【請求項２０】
特徴点検出モジュール、プローブ配置モジュールに関連付けられ、機械視覚システムに、
画像から複数の特徴点を定めることと、
前記画像中の特徴点の分布を示すデータを含む、前記複数の特徴点の特徴点分布を定めることと、
複数のプローブの目標分布の定めることであって、前記複数のプローブの各プローブは、パターンの一部をモデル化するのに利用されると共に、前記目標分布は１つまたは複数の前記特徴点上の前記プローブの所望の位置を示す、前記定めることと、
少なくとも部分的に前記特徴点分布に基づき１つまたは複数の前記特徴点上の前記複数のプローブの位置を定めて、前記複数のプローブと、関連する配置とを含む、前記パターンのためのモデルを生成するために、前記複数のプローブの分布を前記目標分布に整合させることと、
を行わせるように操作可能である、実行可能な命令を有する固定されたコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
開示の装置、システム、および方法は、画像処理用途のためのパターンの画像上へのプローブの配置に関する。
【背景技術】
【０００２】
デジタル画像が、多くのデバイスによって形成され、多くの実用目的のために使用される。デバイスには、荷電結合デバイス（ＣＣＤ）画像センサまたは相補型金属酸化膜半導体（ＣＭＯＳ）画像センサ、線走査センサ、飛点走査装置、電子顕微鏡、コンピュータ断層撮影（ＣＴ）装置を含むＸ線装置、磁気共鳴映像装置、ならびに当業者に知られている他のデバイスなどの、可視光または赤外光で作動する画像センサを有するカメラが含まれる。実用用途が、産業オートメーション、医学診断、様々な軍事、民事、および科学的目的のための衛生撮像、写真処理、偵察および行先監視、文献処理、ならびに他の多くの用途に見出される。
【０００３】
これらの用途に対応するために、様々なデバイスによって形成された画像が、機械視覚システムによって解析されて適切な情報が抽出される。実用上かなり重要な解析の形態の１つが、撮像デバイスの視野内の対象に対応する画像のパターンの位置、配向、およびサイズの判定である。パターン検出法が、その方法が半導体製造、電子回路組立て、製薬、食品加工、消費財製造、および他の多くでロボットおよび他のオートメーション装置の誘導に使用される産業オートメーションにおいて特に重要である。
【０００４】
場合によっては、パターン検出法により、１つまたは複数のプローブを使用してパターンをモデル化することができる。プローブは、パターン検出法によって画像の傾斜ベクトルが調べられる、画像における位置に関連付けることができる。したがって、各プローブは位置ベクトルおよび配向ベクトルに関連付けることができる。プローブが画像におけるパターンの位置および配向を効果的に示すことができるので、機械視覚システムはプローブを使用してパターンの位置および配向を調整することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
開示の主題にしたがって、装置、システム、および方法が、画像処理用途のためにパターン上にプローブを配置するために提供される。
【課題を解決するための手段】
【０００６】
いくつかの実施形態には、機械視覚システムが含まれる。機械視覚システムは、メモリに格納されるコンピュータプログラムを実行するように構成されるプロセッサを含むことができる。プロセッサは、コンピュータプログラムを実行して、特徴点検出モジュールを使用して画像から複数の特徴点を定め、特徴点検出モジュールと繋げられるメモリ内に格納された特徴分布算出（ＦＤＣ）モジュールにより、複数の特徴点の特徴点分布を定め、目標分布算出（ＴＤＣ）モジュールを使用して複数のプローブの目標分布を定め、ここで、目標分布は１つまたは複数の特徴点上のプローブの所望の位置を示すものであり、ＴＤＣモジュールおよびＦＤＣモジュールと繋げられるプローブ分布整合（ＰＤＭ）モジュールを使用して、少なくとも部分的に特徴点分布に基づき１つまたは複数の特徴点上の複数のプローブの位置を定めて、複数のプローブの分布を目標分布に整合させることができる。
【０００７】
いくつかの実施形態では、プロセッサはコンピュータプログラムを実行して複数の特徴点における配向を定め、特定の配向を有する特徴点の数を示す配向のヒストグラムを定めることができる。
【０００８】
いくつかの実施形態では、プロセッサは、コンピュータプログラムを実行して、平滑化関数を使用して配向のヒストグラムを平滑化することができる。
【０００９】
いくつかの実施形態では、プロセッサは、コンピュータプログラムを実行して、考慮される寸法（dimension:次元、大きさ、範囲、特徴）のすべてにおいて等しくバランスが取られる複数のプローブを定めることができる。
【００１０】
いくつかの実施形態では、プロセッサはさらに、第１のプローブを第１の特徴点に配置し、第１の特徴点と実質的に同様な配向を有する特徴点の数に基づいて第１の特徴点の弧の長さを調整し、第１の特徴点の調整された弧の長さに基づいて第２のプローブを第２の特徴点に配置するように構成される。
【００１１】
いくつかの実施形態では、プロセッサはさらに、複数の特徴点の配向の分布を、混合モデルを含む確率分布に合わせるように構成される。
【００１２】
いくつかの実施形態では、プロセッサは、コンピュータプログラムを実行して、複数の特徴点を少なくとも１つのクラスタにクラスタリングすることにより、特徴点分布の混合モデルの構成要素の数を定めることができる。
【００１３】
いくつかの実施形態では、プロセッサは、コンピュータプログラムを実行して特徴点分布の混合モデルの加重値を調整することで、少なくとも１つのモーメントが考慮される寸法（dimension:次元、大きさ、範囲、特徴）のそれぞれにわたってほぼ等しい特性を有する目標分布を定めることができる。
【００１４】
いくつかの実施形態では、プロセッサはさらに、目標分布を使用して特徴点の配向分布比を定めることで、特徴点をサンプリングし直し、複数のプローブに提供するように構成される。
【００１５】
いくつかの実施形態では、特徴点分布および目標分布は、寸法の所定のセット上の分布を含み、この寸法の所定のセットは、ユークリッドの寸法または円柱状の寸法（cylindrical dimension）の１つを含む。
【００１６】
いくつかの実施形態には、特徴点判定モジュール、特徴分布算出（ＦＤＣ）、目標分布算出（ＴＤＣ）モジュール、およびプローブ分布整合（ＰＤＭ）モジュールに関連付けられる実行可能な命令を有する固定されたコンピュータ可読媒体が含まれる。これらのモジュールは、機械視覚システムに、画像から複数の特徴点を判定させ、複数の特徴点の特徴点分布を判定させ、複数のプローブの目標分布を判定させ、ここで、目標分布は１つまたは複数の特徴点上のプローブの所望の配置を示すものであり、少なくとも部分的に特徴点分布に基づき１つまたは複数の特徴点上の複数の特徴点の配置を定めて、複数のプローブの分布を目標分布に整合させるように操作可能である。
【００１７】
いくつかの実施形態では、固定されたコンピュータ可読媒体がさらに、機械視覚システムに複数の特徴点における配向を判定させ、特定の配向を有する特徴点の数を示す配向のヒストグラムを判定させるように構成される、実行可能な命令を有する。
【００１８】
いくつかの実施形態では、固定されたコンピュータ可読媒体がさらに、機械視覚システムに、平滑化関数を使用して配向のヒストグラムを平滑化させるように構成される、実行可能な命令を有する。
【００１９】
いくつかの実施形態では、固定されたコンピュータ可読媒体がさらに、機械視覚システムに、考慮される寸法のすべてにおいて等しくバランスが取られる複数のプローブを定めるように構成される、実行可能な命令を有する。
【００２０】
いくつかの実施形態では、固定されたコンピュータ可読媒体がさらに、機械視覚システムに、第１の特徴点に第１のプローブを配置させ、第１の特徴点と実質的に同様な配向を有する特徴点の数に基づいて第１の特徴点の弧の長さを調整させ、第１の特徴点の調整された弧の長さに基づいて第２のプローブを第２の特徴点に配置させるように構成される、実行可能な命令を有する。
【００２１】
いくつかの実施形態では、固定されたコンピュータ可読媒体がさらに、機械視覚システムに、複数の特徴点を、確率分布の混合に合わせるように構成される、実行可能な命令を有し、確率分布の混合は少なくとも、複数の特徴点において測定された配向の分布を示す。
【００２２】
いくつかの実施形態では、固定されたコンピュータ可読媒体がさらに、機械視覚システムに、複数の特徴点を少なくとも１つのクラスタにクラスタリングすることにより、混合における確率分布の数を判定させるように構成される、実行可能な命令を有する。
【００２３】
いくつかの実施形態では、固定されたコンピュータ可読媒体がさらに、機械視覚システムに、確率分布の混合の加重値を調整させるように構成される、実行可能な命令を有する。
【００２４】
いくつかの実施形態では、固定されたコンピュータ可読媒体がさらに、機械視覚システムに、特徴点分布と目標分布の比を計算させて、隣接するプローブ間の距離を判定させるように構成される実行可能な命令を有する。
【００２５】
いくつかの実施形態には、開示のシステムまたは開示の固定されたコンピュータ可読媒体を操作する方法が含まれる。この方法には、特徴点検出モジュールを使用して画像から複数の特徴点を定めることと、特徴点検出モジュールと繋げられるメモリ内に格納されたＦＤＣモジュールを使用して複数の特徴点の特徴点分布を定めることと、ＴＤＣモジュールを使用して複数のプローブの目標分布を定めることと、ここで、目標分布は１つまたは複数の特徴点上のプローブの所望の配置を示すものであり、ＴＤＣモジュールおよびＦＤＣモジュールと繋げられるＰＤＭモジュールにより、少なくとも部分的に特徴点分布に基づき１つまたは複数の特徴点上の複数のプローブの配置を定めて、複数のプローブの分布を目標分布に整合させることが含まれる。
【００２６】
いくつかの実施形態では、方法には、複数の特徴点における配向を定めることと、特定の配向を有する特徴点の数を示す配向のヒストグラムを定めることとが含まれる。
【００２７】
いくつかの実施形態では、方法には、平滑化関数を使用して配向のヒストグラムを平滑化することが含まれる。
【００２８】
いくつかの実施形態では、方法には、考慮される寸法のすべてにおいて等しくバランスが取られる複数のプローブを識別することが含まれる。
【００２９】
いくつかの実施形態では、方法には、第１のプローブを第１の特徴点に配置することと、第１の特徴点と実質的に同様な配向を有する特徴点の数に基づいて第１の特徴点の弧の長さを調整することと、第１の特徴点の調整された弧の長さに基づいて第２のプローブを第２の特徴点に配置することとが含まれる。
【００３０】
いくつかの実施形態では、方法には、複数の特徴点を、混合モデルを含む確率分布に合わせることが含まれ、確率分布は少なくとも、複数の特徴点において測定された配向の分布を示す。
【００３１】
いくつかの実施形態では、方法には、複数の特徴点を少なくとも１つのクラスタにクラスタリングすることにより、特徴点分布の混合モデルの構成要素の数を定めることが含まれる。
【００３２】
いくつかの実施形態では、平滑化関数には、配向ドメインにおける円形カーネルが含まれる。
【００３３】
いくつかの実施形態では、円形カーネルにはコサイン関数が含まれる。
【００３４】
いくつかの実施形態では、特徴点が、複数のプローブによってモデル化されたパターンの境界と関連付けられ、特徴点は境界に沿う弧と関連付けられる。
【００３５】
いくつかの実施形態では、特徴点が、複数のプローブによってモデル化されたパターンの境界と関連付けられ、特徴点は境界に沿う弧と関連付けられる。
【発明の効果】
【００３６】
本明細書に記載される開示の装置、システム、および方法により、パターンのすべての自由度においてバランスの取れた情報を抽出することで、パターンのモデルを向上させることができる。たとえば、パターンに対応する対象が、２次元で移動する（たとえば、平行移動）場合、このため、開示の装置およびシステムにより、プローブが２次元のパターンからバランスの取れた情報を抽出できるように、プローブを配置することができる。開示の装置およびシステムは、開示の方法を使用してそのようにプローブを配置するように構成することができる。
【００３７】
以下のその詳細な説明がより良く理解され得るために、また、技術への本件の寄与がより良く認識され得るために、開示の主題の特徴をこうして幾分大まかに概説した。もちろん、これ以降に記載され、本明細書に添付される特許請求の範囲の主題を形成する、開示の主題のさらなる特徴がある。本明細書に利用される言い回しおよび用語は、説明を目的とするものであり、限定的に捉えられるべきではないことを理解されたい。
【００３８】
開示の主題の様々な目的、特徴、および利点が、以下の図面と関連づけて考察されると、以下の開示の主題の詳細な説明を参照することで、より完全に認識され得る。図面において、同様の参照符号は同様の要素を識別する。
【図面の簡単な説明】
【００３９】
【図１】図１は、細長い矩形形状を有するパターン、およびこのパターン上に均等に配置されたプローブを示す。
【図２】図２は、いくつかの実施形態に係る、画像の特徴点上へのプローブの配置のための高レベルプロセスを示す。
【図３】図３は、いくつかの実施形態に係る、垂直配向のヒストグラムを均等な分布に整合させることによるプローブの配置の結果を示す。
【図４】図４は、いくつかの実施形態に係る、プローブ配置モジュールを含むコンピュータデバイスを示す。
【図５】図５は、いくつかの実施形態に係る、画像の特徴点に向けた垂直配向のヒストグラムを定めるプロセスを示す。
【図６Ａ】図６Ａ〜６Ｈは、いくつかの実施形態に係る、垂直配向のヒストグラムを生成するプロセスを示す。
【図６Ｂ】図６Ａ〜６Ｈは、いくつかの実施形態に係る、垂直配向のヒストグラムを生成するプロセスを示す。
【図６Ｃ】図６Ａ〜６Ｈは、いくつかの実施形態に係る、垂直配向のヒストグラムを生成するプロセスを示す。
【図６Ｄ】図６Ａ〜６Ｈは、いくつかの実施形態に係る、垂直配向のヒストグラムを生成するプロセスを示す。
【図６Ｅ】図６Ａ〜６Ｈは、いくつかの実施形態に係る、垂直配向のヒストグラムを生成するプロセスを示す。
【図６Ｆ】図６Ａ〜６Ｈは、いくつかの実施形態に係る、垂直配向のヒストグラムを生成するプロセスを示す。
【図６Ｇ】図６Ａ〜６Ｈは、いくつかの実施形態に係る、垂直配向のヒストグラムを生成するプロセスを示す。
【図６Ｈ】図６Ａ〜６Ｈは、いくつかの実施形態に係る、垂直配向のヒストグラムを生成するプロセスを示す。
【図７】図７は、いくつかの実施形態に係る、プローブの配置を定めるプロセスを示す。
【図８】図８は、いくつかの実施形態にかかる、画像の特徴点に関連付けられる弧の長さのスケーリングを示す。
【図９】図９は、いくつかの実施形態に係る、スケーリングされた特徴点上のプローブの均等な配置を示す。
【図１０】図１０は、いくつかの実施形態に係る、特徴点に関連付けられるスケーリングされた弧の長さの逆スケーリングを示す。
【図１１Ａ】図１１Ａ〜１１Ｂは、いくつかの実施形態に係る、目標分布からのプローブのサンプリングによってプローブのバランスを取ることを示す。
【図１１Ｂ】図１１Ａ〜１１Ｂは、いくつかの実施形態に係る、目標分布からのプローブのサンプリングによってプローブのバランスを取ることを示す。
【図１２Ａ】図１２Ａは、いくつかの実施形態に係る、基準ベクトルと単位法線ベクトルとの関係を示す。
【図１２Ｂ】図１２Ｂは、いくつかの実施形態に係る、位置ベクトルｖｉと単位回転ベクトルｕθiとの関係を示す。
【図１３】図１３には、いくつかの実施形態に係る、プローブのサンプリングプロセスが要約されている。
【図１４Ａ】図１４Ａは、いくつかの実施形態に係る、図１３に示すプロセスを使用した矩形上へのプローブの配置を示す。
【図１４Ｂ】図１４Ｂは、いくつかの実施形態に係る、図１３に示すプロセスを使用したレバーアームを有する円形の対象上へのプローブの配置を示す。
【図１５Ａ】図１５Ａは、いくつかの実施形態に係る、図１３に示すプロセスを使用した矩形上へのプローブの配置を示す。
【図１５Ｂ】図１５Ｂは、いくつかの実施形態に係る、図１３に示すプロセスを使用したレバーアームを有する円形の対象上へのプローブの配置を示す。
【図１６Ａ】図１６Ａ〜Ｂは、いくつかの実施形態に係る、図１３に示すプロセスを使用した穴を有するパターン上へのプローブの配置を示す。
【図１６Ｂ】図１６Ａ〜Ｂは、いくつかの実施形態に係る、図１３に示すプロセスを使用した穴を有するパターン上へのプローブの配置を示す。
【図１７Ａ】図１７Ａ〜１７Ｃは、いくつかの実施形態に係る、回転変数θの表示がどのようにプローブの配置を変化させるのかを示す。
【図１７Ｂ】図１７Ａ〜１７Ｃは、いくつかの実施形態に係る、回転変数θの表示がどのようにプローブの配置を変化させるのかを示す。
【図１７Ｃ】図１７Ａ〜１７Ｃは、いくつかの実施形態に係る、回転変数θの表示がどのようにプローブの配置を変化させるのかを示す。
【図１８Ａ】図１８Ａ〜１８Ｂは、いくつかの実施形態に係る、図１３に示すプロセスを使用した細長いアームを有するパターン上へのプローブの配置を示す。
【図１８Ｂ】図１８Ａ〜１８Ｂは、いくつかの実施形態に係る、図１３に示すプロセスを使用した細長いアームを有するパターン上へのプローブの配置を示す。
【発明を実施するための形態】
【００４０】
以下の説明では、開示の主題を十分に理解することを可能にするために、開示の主題のシステムおよび方法、ならびにそれらのシステムおよび方法が機能できる環境などに関して、多数の具体的な詳細が説明される。しかし、開示の主題はそのような具体的な詳細に関わらず実施され得、また、開示の主題が複雑になることを避けるために、当該技術分野で周知の特定の特徴は詳細に記載されないことが、当業者には明らかになる。さらに、以下に提供される例は例示的なものであり、また、開示の主題の範囲内にある他のシステムおよび方法が存在することが予想されることが理解されよう。
【００４１】
以下に、１つまたは複数の実施形態に係る、明細書を通して使用される用語の例示的な説明を示す。これらの説明は限定を意図するものではない。
【００４２】
対象−画像形成デバイスによって測定できるか、データ処理装置によってシミュレートすることができる特性を有する任意の物理的または擬似的な対象、またはその部分。
【００４３】
画像−その値が、たとえば明るさ（反射された、または別様の放射エネルギー）、色、温度、基準面からの高さなどの対象の物理的特性に対応し、任意の画像形成デバイスによって測定されるか、その値が、対象のシミュレートされる特性に対応し、任意のデータ処理デバイスによって生成される、二次元的相関関係。
【００４４】
境界−それに沿って特定の粒状度で画像の明るさの不連続が生じる、端部が開いているか閉じている、直線または曲線、平滑または鋭い仮想の輪郭。前述の不連続の方向は、各点において境界に垂直である。
【００４５】
傾斜−画像の所与の点における、前述の点での特定の粒状度の明るさの最も大きい変化の向きおよび大きさを与えるベクトル。
【００４６】
パターン−輪郭の平面の境界が付けられたサブセットに位置する、輪郭の特定の幾何学配置であり、前述の輪郭は、位置が特定され、かつ／または検査される対象の理想的な画像の境界を示す。
【００４７】
モデル−パターン発見方法によって使用のために見出される、パターンのデータ符号化特性のセット。
【００４８】
トレーニング−例示的対象の画像から、または対象もしくはパターンの幾何学的記載からモデルを構築するプロセス。
【００４９】
機械視覚システムは、画像の所定のパターンの１つまたは複数の例の有無を定め、かつ発見された例のそれぞれの位置を定めるように構成することができる。パターンの位置を特定するプロセスは、それに限定されないが、ｘ−ｙ位置（平行移動とも呼ばれる）、配向、およびサイズを含む多次元スペース内で生じる。
【００５０】
画像の所定のパターンの１つまたは複数のインスタンスの有無を定めるために、機械視覚システムは、モデルを使用して見出されるパターンを示すことができる。機械視覚システムは、１つもしくは複数のトレーニング画像、または、位置が特定され、かつ／もしくは検査されるパターンのインスタンスを含む幾何学的記載からの１つもしくは複数の合成画像から、パターン用のモデルを生成することができる。モデルが使用可能になると、機械視覚システムは、モデルを、ポーズの適切なセットのそれぞれにおけるテスト画像と比較し、各ポーズの整合スコアを算出し、また、整合スコアの極大値に対応する、候補となるポーズを定める。機械視覚システムは、画像のパターンのインスタンスになる、適切な閾値を超える整合スコアを有する候補となるポーズを考慮することができる。
【００５１】
モデルには、プローブと呼ばれるデータ要素のセットを含むことができる。各プローブは、所与のポーズの画像における特定の測定およびテストが行われる相対位置を示し、それらのテストのそれぞれにより、関連するポーズにおいてパターンが存在することの証明に寄与する。プローブは、基礎を成すパターンの構造（たとえば境界）に対してほぼ垂直になる方式で配置することができる。
【００５２】
トレーニング段階では、既存の機械視覚システムがパターンの境界上にプローブを均等に配置する。たとえば、機械視覚システムは、隣接するプローブ間の距離が、すべての隣接するプローブの対についてほぼ同一になるように、パターンの境界上にプローブを配置する。本明細書において「均等配置方法」と称されるこの方法では、バランスが取れた配向プロファイル（たとえば、多数の配向を示す境界を有するパターンと、様々な配向を示す境界の割合とが類似している）を有するパターンのモデル化に効果的となり得る。たとえば、均等配置方法は正方形のパターンのモデル化に有用であり、この理由は、異なる配向を示す（たとえば、上、下、左、および右）プローブの数が、画像のパターンの各縁上においてほぼ同じであり、このことにより、パターンの位置および配向の正確な情報につなげることができるためである。
【００５３】
不幸なことに、均等配置方法は、バランスが取れていない配向プロファイルを有するパターン（たとえば、様々な辺の長さを有するパターン）のモデル化にはしばしば非効率的である。たとえば、均等配置方法は通常、細長い矩形形状のパターンを調整するには、それほど効率的ではない。図１が、細長い矩形形状を有するパターン、およびこのパターン上に均等に配置されたプローブを示す。境界１０２が細長い矩形形状を有しているため、均等配置方法では、ほとんどのプローブ１０４が境界の長縁１０６上に配置され、少数のプローブ１０４のみが境界の短縁１０８上に配置される。境界の短縁１０８に沿うプローブの数が少ないため、プローブに基づいて短縁１０８があるかどうかを定めるのは困難である。さらに、短縁１０８があることを判定できるとしても、短縁１０８の位置を符号化するプローブ１０４の数が少ないため、短縁１０８の位置を正確に示すことは困難である。このことは、たとえば、境界１０２が他のパターンに対して水平に並べるのに問題になり得る。
【００５４】
均等配置方法に関連付けられる問題に対処するために、隣接するプローブ間の距離を変化させる作業を要してきた。しかし、この作業は手作業でのプローブ位置の調整に制限され、このことは、手間がかかり、かつ高価になり得る。
【００５５】
本明細書に記載される技術により、パターン上にプローブを配置するための自動化されたプローブ配置モジュールが提供される。このプローブ配置モジュールは、プローブが画像に表れるパターンを正確に示すことができるように、画像の特徴点上にプローブを配置するように構成される。このプローブ配置モジュールは、プローブが、パターンの動きに関連付けられるすべての自由度においてバランスが取れた情報を抽出できるように、プローブを配置するように構成することができる。このことにより、プローブから生成されるモデルの正確さが向上する。たとえば、パターンに関連付けられる対象が二次元で移動する（たとえば、並行移動）ことが知られている場合、プローブ配置モジュールは、プローブが二次元のバランスの取れた情報を抽出できるように、プローブを配置することができる。プローブ配置モジュールはまた、プローブがパターンの形状に関わらずバランスの取れた情報を抽出することができるように、パターンの形状を考慮することができる。このことは、図１に示すように、短縁に比べてより多くのプローブが長縁に配置される場合に、水平な情報に比べてより多くの垂直な情報を抽出するような、バランスが取れていない情報を抽出する技術とは対照的である。
【００５６】
図２は、いくつかの実施形態に係る、画像の特徴点上へのプローブの配置のための高レベルプロセスを示す。特徴点は、プローブの候補となる位置を示すことができる。たとえば、プローブ配置モジュールは、画像における特徴点のサブセットを選択し、選択された特徴点のサブセット上にプローブを配置するように構成することができる。
【００５７】
ステップ２０２では、プローブ配置モジュールは、画像における特徴点の位置の情報を受信するように構成することができる。たとえば、プローブ配置モジュールは、特徴点検出モジュールから、画像におけるパターンの境界を受信することができる。
【００５８】
ステップ２０４では、プローブ配置モジュールは、特徴点の分布を定めることができる。たとえば、プローブ配置モジュールは、特徴（たとえば、特徴点において測定される垂直配向）を使用して各特徴点を示し、特徴点に関連付けられる特徴の分布を定めることができる。
【００５９】
ステップ２０６では、プローブ配置モジュールは、プローブの目標分布を定めることができる。場合によっては、プローブの目標分布が、特徴点に関連付けられる特徴および／またはステップ２０４で判定された特徴点の分布に基づいて判定され得る。たとえば、プローブ配置モジュールは、プローブの目標分布がステップ２０４で判定された特徴点の分布とは逆であることを定めることができる。ステップ２０８では、プローブ配置モジュールは、プローブの実際の分布がプローブの目標分布に整合するように、プローブの位置を定めることができる。
【００６０】
図２に記載の概略的なフレームワークは、たとえば、少なくとも２つの機構を（たとえば単独でおよび／または互いに組み合わせて）使用して、実施することができる。第１の機構では、開示のプローブ配置モジュールは、プローブの位置で測定される垂直配向の分布のバランスを取るように（たとえば、プローブの位置での垂直配向のヒストグラムがほぼ均一）、プローブを配置するように構成することができる。第１の機構は、２つの自由度（たとえば、平行移動）を有するパターンのモデル化に特に有用とすることができる。
【００６１】
たとえば、ステップ２０４では、プローブ配置モジュールは、画像の複数の特徴点において測定された垂直配向のヒストグラムを定めることができる。ステップ２０６では、プローブ配置モジュールは、プローブの位置において測定される垂直配向の目標分布が均等な分布であることを定めることができる。ステップ２０８では、プローブ配置モジュールは、配置されたプローブによって測定される垂直配向のヒストグラムが均等な分布に近くなるように、１つまたは複数の特徴点にプローブを配置することができる。
【００６２】
図３は、いくつかの実施形態に係る、垂直配向のヒストグラムを均等な分布と整合させることによるプローブの配置の結果を示す。この例では、特徴点は全体としてパターンの境界１０２を形成することができる。境界１０２が細長い矩形形状を有する場合、プローブ配置モジュールは、長縁１０６上のプローブの数が短縁１０８上のプローブの数に対してほぼ同じになるように、長縁１０６上のプローブ１０４の数を減らし、短縁１０８上のプローブの数を増やすことができる。この方法で、配置されたプローブ１０４の配向分布のバランスを取ることができる。第１の機構を実施するプローブ配置モジュールを、明細書を通し、特に図５〜１０で説明する。
【００６３】
第２の機構では、プローブ配置モジュールは、プローブの分布が目標分布と実質的に同様になるように、プローブの位置を定めることができる。ステップ２０４では、プローブ配置モジュールは、パターンの自由度に対応する変数を使用して特徴点を示すことができる。たとえば、パターンに関連付けられる対象が二次元で移動することが知られている場合、プローブ配置モジュールは、特徴点における二次元の傾斜ベクトルを使用して特徴点を示すことができる。そして、プローブ配置モジュールは、特徴点に関連付けられる垂直配向の分布をモデル化することにより、特徴点の分布を定めることができる。
【００６４】
ステップ２０６では、プローブ配置モジュールは、特徴点に関連付けられる特徴に基づき、所望の目標分布を定めることができる。たとえば、プローブ配置モジュールは、複数の特徴点において測定される垂直配向に基づき、所望の目標分布を定めることができる。より詳細には、プローブ配置モジュールは、所望の目標分布が、特徴点において測定された垂直配向の分布の逆であると定める。同様に、プローブ配置モジュールは、特徴点において測定された回転ベクトルおよびスケール情報を考慮して、目標分布を定めることができる。次いで、ステップ２０８では、プローブ配置モジュールは、目標分布からのサンプリングにより、１つまたは複数の特徴点上にプローブを配置することができる。第２の機構を、明細書を通して、特に図１１〜１８で説明する。
【００６５】
図４は、いくつかの実施形態に係る、プローブ配置モジュールを含むコンピュータデバイスを示す。コンピュータデバイス４００は、プロセッサ４０２、メモリ４０４、特徴点検出（ＩＰＤ）モジュール４０６、プローブ配置モジュール４０８、およびインターフェイス４１０を含むことができる。
【００６６】
いくつかの実施形態では、プロセッサ４０２は、命令、ならびに命令および／またはデータを格納するための１つまたは複数のメモリデバイス４０４を実行することができる。メモリデバイス４０４は、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、フラッシュメモリ、磁気ディスクドライブ、光学ドライブ、プログラム可能なリード・オンリー・メモリ（ＰＲＯＭ）、リード・オンリー・メモリ（ＲＯＭ）、もしくは他の任意のメモリまたはメモリの組合せなどの、固定されたコンピュータ可読媒体とすることができる。メモリデバイス４０４は、一時的にデータを格納するのに使用することができる。メモリデバイス４０４は、長期間のデータの格納にも使用することができる。プロセッサ４０２およびメモリデバイス４０４は、特定の目的の論理回路により補足および／または特定の目的の論理回路に組み込むことができる。
【００６７】
いくつかの実施形態では、ＩＰＤモジュール４０６は、入力画像から特徴点を検出するように構成することができる。たとえば、ＩＰＤモジュール４０６は、インターフェイス４１０を介して、ＩＰＤモジュール４０６と繋がったカメラモジュールまたは別コンピュータデバイスなどの別のデバイスから画像を受信することができる。次いで、ＩＰＤモジュール４０６は、画像処理操作を行って特徴点を検出することができる。
【００６８】
いくつかの実施形態では、特徴点には、パターンの縁、パターンの境界（たとえば、縁の連結部（ｃｈａｉｎ））、文字の境界、傾斜の大きさが大であるピクセル、隣接するピクセルとの明度差が大であるピクセル、隣接するピクセルとの色差が大であるピクセル、Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ  Ｆｅａｔｕｒｅ  Ｔｒａｎｓｆｏｒｍ（ＳＩＦＴ）の特徴点、隣接するピクセルから明確に判別できる任意のピクセル、またはその任意の組合せが含まれ得る。したがって、ＩＰＤモジュール４０６は、縁検出操作を行ってパターンの境界を形成する縁のセットを定めるように、差別化操作を行って傾斜の大きさが大であるピクセルを検出するように、ＳＩＦＴオペレータを行ってＳＩＦＴ特徴点を検出するように、またはその任意の組合せを行うように構成することができる。
【００６９】
いくつかの実施形態では、ＩＰＤモジュール４０６は、特徴点の基礎を成す、構造に対し垂直な配向（以下、垂直配向と称する）を定めるように構成することができる。いくつかの実施形態では、基礎構造の傾斜配向を定めることによって垂直配向を定めることができる。たとえば、基礎パターンの傾斜ベクトルは特徴点において定めることができ、傾斜ベクトルに関連付けられる配向を定めることができる。別の場合では、垂直配向は、単純な計算で定めることができる。たとえば、構造の境界上の２点を取ることができ、この２点を結ぶ線を定めることができる。この線に垂直な配向を垂直配向と定めることができる。別の場合では、構造の垂直配向は、たとえば計算機援用設計（ＣＡＤ）モデル化モジュールである他のコンピュータモジュールから受信された情報に基づいて定めることができる。
【００７０】
いくつかの実施形態では、プローブ配置モジュール４０８は、画像の特徴点に基づいて、プローブの位置を定めるように構成することができる。プローブ配置モジュール４０８は、目標分布算出（ＴＤＣ）モジュール４１２、特徴分布算出（ＦＤＣ）モジュール４１４、およびプローブ分布整合（ＰＤＭ）モジュール４１６を含むことができる。ＴＤＣモジュール４１２は、１つまたは複数の特徴点に配置されるプローブの目標分布を定めることができる。ＦＤＣモジュール４１４は、画像の特徴点分布を定めることができる。ＰＤＭモジュール４１６は、プローブの分布とプローブの目標分布とが実質的に整合するように、プローブの位置を定めることができる。以下に述べるように、ＴＤＣモジュール４１２が垂直配向のヒストグラムのみを扱う場合、目標分布は均等な分布になり得る。他の実施形態では、プローブ配置モジュール４０８は、実質的に同様の操作を行うための、モジュールの異なるセットを含み得る。
【００７１】
いくつかの実施形態では、インターフェイス４１０は、ハードウェア内で実施されて、光学、チョッパ、ならびに無線、およびその中の固定されているものがあってもよい、いくつかの異なるプロトコルなどの様々な媒体と信号を送受信することができる。
【００７２】
いくつかの実施形態では、１つまたは複数のモジュール４０６、４０８、４１２、４１４、４１６は、メモリ４０４を使用して、ソフトウェア内で実施することができる。ソフトウェアは、コンピュータの指令、またはコンピュータコードを実行可能であるプロセッサ４０２上で実行することができる。プロセッサ４０２は、特定用途向け集積回路（ＡＳＩＣ）、プログラマブル論理アレイ（ＰＬＡ）、デジタル・シグナル・プロセッサ（ＤＳＰ）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、または任意の他の集積回路を使用して、ハードウェア内で実施される。コンピュータプログラムを実行するのに適切なプロセッサ４０２には、例として、一般と特殊の両方の目的のマイクロプロセッサ、デジタル・シグナル・プロセッサ、および任意の種類のデジタルコンピュータの任意の１つまたは複数のプロセッサが含まれる。一般に、プロセッサ４０２はリード・オンリー・メモリもしくはランダム・アクセス・メモリ、またはその両方から命令およびデータを受信する。
【００７３】
いくつかの実施形態では、開示の方法のステップは、コンピュータプログラムを実行する１つまたは複数のプロセッサ４０２によって行われることで、入力データ上の操作および／または出力データの生成により本発明の機能を発揮することができる。１つまたは複数のモジュール（たとえば、モジュール４０６、４０８、４１２、４１４、４１６）は、ＡＳＩＣ（特定用途向け集積回路）、ＰＬＡ（プログラマブル論理アレイ）、ＤＳＰ（デジタル・シグナル・プロセッサ）、ＦＰＧＡ（フィールド・プログラマブル・ゲート・アレイ）、または他の集積回路を使用して、ハードウェア内で実施することができる。いくつかの実施形態では、２つ以上のモジュール４０６、４０８、４１２、４１４、４１６を、ＡＳＩＣ、ＰＬＡ、ＤＳＰ、またはＦＰＧＡなどの同じ集積回路上で実施することができ、それによってチップ上にシステムを形成する。サブルーチンは、１つまたは複数の機能を実施する、コンピュータプログラム、および／またはプロセッサ／特定の電子回路の部分に関連することができる。
【００７４】
モジュール４０６、４０８、４１２、４１４、４１６は、デジタル電子回路内、またはコンピュータのハードウェア、ファームウェア、ソフトウェア、もしくはそれらの組合せの中で実施することができる。実施は、たとえばプログラマブルプロセッサ、コンピュータ、および／または複数のコンピュータなどのデータ処理装置によって実行させる、または操作を制御させる、たとえば機械読取り可能な記憶デバイスに明白に埋め込まれたコンピュータプログラムなどの、コンピュータプログラム製品としてすることができる。コンピュータプログラムは、ソースコード、コンパイルコード、解釈されたコード、および／または機械コードを含むコンピュータまたはプログラミング言語の任意の形式で書き込むことができる。また、コンピュータプログラムは、スタンドアローンなプログラムまたはサブルーチンとして、コンピュータ環境での使用に適切な要素、または他の単位を含む任意の形式で展開することができる。コンピュータプログラムは、展開して、１つのコンピュータ、または１つまたは複数の現場の複数のコンピュータ上で実行することができる。
【００７５】
コンピュータデバイス４００は、指示および／もしくはデータを装置もしくはネットワークから受信するために、および／または指示および／もしくはデータを装置もしくはネットワークに送信するために、たとえばファクトリーオートメーションもしくは物流機材などの外部装置、または、たとえばファクトリーオートメーションもしくは物流機材のネットワークなどの通信ネットワークと操作可能に接続することができる。コンピュータプログラムの指示およびデータを具体化するのに適切なコンピュータ可読記憶デバイスには、ＤＲＡＭ、ＳＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュ・メモリ・デバイスなどの半導体メモリデバイス、内蔵ハードディスクまたはリムーバブルディスクなどの磁気ディスク、磁気光学ディスク、ならびにＣＤ、ＤＶＤ、ＨＤ−ＤＶＤ、およびＢｌｕ−ｒａｙ（登録商標）ディスクなどの光学ディスクを例として含む、すべての形式の揮発性および非揮発性メモリが含まれる。
【００７６】
いくつかの実施形態では、コンピュータデバイス４００はユーザ装置を含むことができる。ユーザ装置は、１つまたは複数の無線アクセスネットワーク、および有線通信ネットワークと通信することができる。ユーザ装置は、移動電話であってもよい。ユーザ装置は
また、ワードプロセッシング、ウェブブラウジング、ゲーミング、電子書籍機能、オペレーティングシステム、およびフルキーボードなどのサービスを提供するスマートフォンでもよい。ユーザ装置は、ネットワークへのアクセス、およびスマートフォンによって提供されるサービスのほとんどを提供するタブレットコンピュータでもよい。ユーザ装置は、Ｓｙｍｂｉａｎ  ＯＳ、ｉＰｈｏｎｅＯＳ、ＲＩＭのＢｌａｃｋｂｅｒｒｙ、Ｗｉｎｄｏｗｓ（登録商標）  Ｍｏｂｉｌｅ、Ｌｉｎｕｘ（登録商標）、ＨＰ  ＷｅｂＯＳ、およびＡｎｄｒｏｉｄなどのオペレーティングシステムを使用して機能する。スクリーンはデータをモバイルデバイスに入力するのに使用されるタッチスクリーンであってもよく、その場合、スクリーンはフルキーボードの代わりに使用することができる。ユーザ装置は、全地球測位座標、プロフィール情報、または他の位置情報を保有することもできる。
【００７７】
いくつかの実施形態では、コンピュータデバイス４００はサーバを含むことができる。サーバは、オペレーティングシステム（ＯＳ）ソフトウェアを使用して機能することができる。いくつかの実施形態では、ＯＳソフトウェアは、Ｌｉｎｕｘ（登録商標）ソフトウェアカーネルを基礎とし、タスクの監視およびプロトコルスタックの提供などの特定のアプリケーションをサーバ内で実行する。ＯＳソフトウェアは、制御およびデータパスのために、サーバのリソースを別々に配置することを許容する。たとえば、特定のパケット・アクセラレータ・カードおよびパケット・サービス・カードがルーチングまたはセキュリティコントロール機能の実施に割り当てられ、一方では他のパケット・アクセラレータ・カード／パケット・サービス・カードがユーザのセッショントラフィックの処理に割り当てられる。ネットワークの要求が変化すると、ハードウェアのリソースを動的に展開して、いくつかの実施形態における要求に対処することができる。
【００７８】
第１のプローブ配置機構−プローブの垂直配向のバランスを取ること
いくつかの実施形態では、プローブ配置モジュール４０８は、プローブを配置して、プローブ位置で測定された垂直配向のバランスを取るように構成することができる。より詳細には、プローブ配置モジュール４０８は、プローブの位置で測定された垂直配向のヒストグラムがほぼ均等になるように、画像の１つまたは複数の特徴点にプローブを配置するように構成することができる。このオペレーションモードにより、プローブ配置モジュール４０８が対象のモデルの精度を２つの自由度で向上できるようにすることができる。
【００７９】
いくつかの実施形態では、垂直配向のヒストグラムには、複数の配向ビンを含むことができる。各配向ビンは、配向の所定の範囲に対応することができる。たとえば、垂直配向のヒストグラムは、１８０のビンを含むことができ、各配向ビンは２度の角度範囲をカバーすることができる。したがって、垂直配向のヒストグラムは、特徴点で測定される垂直配向のプロファイルを示すことができる。いくつかの実施形態では、垂直配向のヒストグラムは、連続的な分布として示すことができる。
【００８０】
いくつかの実施形態では、プローブ配置モジュール４０８は、特徴点に関連付けられる垂直配向のヒストグラムを定めるように構成することができる。この目的で、プローブ配置モジュール４０８は、各特徴点に関連付けられる垂直配向を定めることができる。たとえば、プローブ配置モジュール４０８は、ＩＰＤモジュール４０６から、各特徴点における垂直配向を示す情報を受信することができる。別の例として、プローブ配置モジュール４０８は、各特徴点に関連付けられる垂直配向を計算することができる。次いで、プローブ配置モジュール４０８により、複数の特徴点において測定された垂直配向のヒストグラムを定めることができる。
【００８１】
図５は、いくつかの実施形態に係る、画像の特徴点の垂直配向のヒストグラムを定めるプロセスを示す。
【００８２】
ステップ５０２では、ＩＰＤモジュール４０６により、画像の特徴点を定めることができる。いくつかの実施形態では、特徴点には画像に表されるパターンの境界を含むことができる。場合によっては、ＩＰＤモジュール４０６により、縁検出技術を使用して、パターンの境界を識別することができる。たとえば、ＩＰＤモジュール４０６は、縁検出操作を実施して、縁に対応すると思われる縁の点のセットを識別することができる。各点は、位置ベクトル、および基礎を成す構造に対し垂直な垂直ベクトルと関連付けることができる。次いで、ＩＰＤモジュール４０６は、縁の点を繋いで、パターンの一貫した境界を形成することができる。縁検出技術には、たとえば、キャニー縁検出技術またはハフ変換技術を含むことができる。縁検出技術は、たとえば、Ｓｏｂｅｌオペレータ、キルシュオペレータ、プルウィットオペレータ、ガボアフィルタ、ハールウェーブレットフィルタ、画像のピクセル値の変化（たとえば、画像の高周波数成分）を検出できる任意の他のフィルタ、および／またはそれらの任意の組合せを含む、１つまたは複数の縁検出オペレータを使用することができる。
【００８３】
他の実施形態では、特徴点には、ＳＩＦＴ特徴点を含むことができる。そのような場合、ＩＰＤモジュール４０６によりＳＩＦＴ操作を実施してＳＩＦＴ特徴点を識別することができる。
【００８４】
いくつかの実施形態では、特徴点をパターンの境界上に均等に配置することができる。たとえば、任意の２つの隣接する特徴点間の距離をほぼ同一にすることができる。この場合、各特徴点を、境界の同じ弧の長さと関連付けられるものと見なすことができる。
【００８５】
少なくとも１つの特徴点が利用可能になると、ＦＤＣモジュール４１４が、ＩＰＤモジュール４０６から、少なくとも１つの特徴点の位置を受信することができる。そして、ＦＤＣモジュール４１４はステップ５０４〜５０８を繰り返して、少なくとも１つの特徴点において測定された垂直配向のヒストグラムを生成することができる。
【００８６】
ステップ５０４では、ＦＤＣモジュール４１４は、少なくとも１つの特徴点の内の１つを選択し、選択された特徴点の垂直配向を定めることができる。いくつかの実施形態では、ＦＤＣモジュール４１４は、ＩＰＤモジュール４０６から垂直配向の情報を受信することができる。他の実施形態では、ＦＤＣモジュール４１４はそれ自体で、選択された特徴点の垂直配向を定めることができる。たとえば、ＦＤＣモジュール４１４は特徴点を伴う傾斜オペレータを畳み込んで、垂直配向を定める。傾斜オペレータには、ガボアフィルタ、ハールウェーブレットフィルタ、可動フィルタ、ｘ方向傾斜フィルタ［−１，０，１］、ｙ方向傾斜フィルタ［−１，０，１］Ｔ、および／またはそれらの任意の組合せを含むことができる。別の実施形態としては、ＦＤＣモジュール４１４は、たとえば特徴点の基礎を成す構造の傾斜ベクトルを定めるか、構造の境界上の２つの近い点を結ぶ線の配向を定めることで、各特徴点に関連付けられる垂直配向を算出する。
【００８７】
ステップ５０６では、ＦＤＣモジュール４１４は、選択された特徴点の垂直配向の寄与を垂直配向のヒストグラムに追加することができる。この目的で、ＦＤＣモジュール４１４は、ヒストグラムにおいて、ステップ５０４で判定された垂直配向に対応する配向ビンを定めることができる。たとえば、垂直配向がｘ軸に対し３度である場合、ＦＤＣモジュール４１４は、垂直配向が、ｘ軸に対し２度から４度までの間の配向をカバーする配向ビン＃１と関連付けられると定めることができる。次いで、ＦＤＣモジュール４１４は、垂直配向に関連付けられる配向ビンに票を加えることができる。たとえば、ＦＤＣモジュール４１４は、配向ビンの値を１だけ増やすことができる。別の例としては、ＦＤＣモジュール４１４は、配向ビンの値を加重値分だけ増やすことができる。加重値は、特徴点に関連付けられる傾斜ベクトルに依存するものとすることができる。たとえば、加重値は、傾斜ベクトルの大きさに依存するものとすることができる。
【００８８】
ステップ５０８では、ＦＤＣモジュール４１４は、ＦＤＣモジュール４１４が垂直配向のヒストグラムに考慮してこなかった特徴点が存在するかどうかを定めることができる。存在する場合、ＦＤＣモジュール４１４はステップ５０４に戻り、すべての特徴点がＦＤＣモジュール４１４により考慮されるまで、ステップ５０４〜５０８を繰り返すことができる。ＦＤＣモジュール４１４がすべての特徴点を考慮してきた場合、ＦＤＣモジュール４１４は垂直配向のヒストグラムを出力することができる。
【００８９】
図６Ａ〜６Ｈは、いくつかの実施形態に係る、垂直配向のヒストグラムを生成するプロセスを示す。この例では、各矢印６０２の中心が特徴点と対応するものと見なすことができ、すべての特徴点のセットが境界１０２を含むものと見なすことができる。図６Ａに示すように、ＦＤＣモジュール４１４は、第１の特徴点６０２Ａが０とπ／６の領域をカバーする配向ビンに関連付けられると定めることができる。したがって、ＦＤＣモジュール４１４は、配向ビンと関連付けられる値を１だけ増やすことができる。図６Ｂ〜６Ｈに示すように、ＦＤＣモジュール４１４は、境界１０２上の各特徴点６０２についてこの操作を実施し、対応する垂直配向のヒストグラム６０４を生成することができる。
【００９０】
いくつかの実施形態では、ＴＤＣモジュール４１２は、プローブの目標分布を生成するように構成することができる。プローブの目標分布は、１つまたは複数の特徴点上のプローブの所望の配置を示すことができる。いくつかの実施形態では、目標分布には、複数の配向ビンを含むことができ、ここで、各配向ビンは値と関連付けられる。場合によっては、目標分布は均等な分布とすることができる。本質的には、均等な目標分布は、特定の配向を示す特徴点上のプローブの数が、別の配向を示す特徴点上のプローブの数と同じになるものであることを示す。この方法により、プローブ配置モジュール４０８は、異なる配向を示すプローブの数のバランスを取ることができる。
【００９１】
場合によっては、目標分布は、部分的に均等な分布とすることができる。たとえば、目標分布の配向ビンのいくつかはゼロの値を有することができ、残りの配向ビンが同じ値を有することができる。このような場合、垂直配向のヒストグラム６０４における対応する配向ビンがゼロの値を有する場合、目標分布の配向ビンがゼロの値を有することができる。
【００９２】
ＦＤＣモジュール４１４が垂直配向のヒストグラムを定め、ＴＤＣモジュール４１２が目標分布を定めると、ＰＤＭモジュール４１６は、１つまたは複数の特徴点上のプローブの分布が目標分布と整合するように、プローブの位置を定めることができる。
【００９３】
図７は、いくつかの実施形態に係る、プローブ位置を定めるプロセスを示す。ステップ７０２では、ＰＤＭモジュール４１６が垂直配向のヒストグラムを使用して、特徴点のどの部分が特定の配向を示す構造上にあるかを定めることができる。たとえば、ヒストグラムが１８０の配向ビンを有する場合、ＰＤＭモジュール４１６はヒストグラムを使用して、２度の分解能で特定の配向を示す特徴点の比率を定めることができる。次いで、ＰＤＭモジュール４１６は、特徴点に対応するヒストグラムビンの値に基づき、特徴点の弧の長さをスケーリングすることができる。より詳細には、ＰＤＭモジュール４１６は、個別の特徴点に関連付けられるヒストグラムビンの値と反比例する方式で、個別の特徴点の弧の長さを調整することができる。
【００９４】
たとえば、図３に示す例を参照すると、短縁１０４に沿う特徴点の数を長縁１０６に沿う特徴点の数に比べて少なくすることができる。したがって、短縁１０４に対応するヒストグラムのビンの値を長縁１０６に対応するビンの値よりも小さくすることができる。これに基づき、ＰＤＭモジュール４１６は、短縁１０４に沿う特徴点（たとえば、境界セクション）の弧の長さを長くし、長縁１０６に沿う特徴点の弧の長さを小さくする（または変わらないままにする）ことができる。
【００９５】
図８は、いくつかの実施形態にかかる、境界の特徴点の弧の長さのスケーリングを示す。ヒストグラムが、垂直縁上の特徴点の数が水平縁の特徴点上の数より少ないことを示すため、ＰＤＭモジュール４１６は、垂直縁の特徴点の弧の長さを長くすることができる。長くなった特徴点の弧の長さは、矢印８０２で示すように、垂直縁に沿う境界の長さの増大とみなすことができる。
【００９６】
ステップ７０４では、ＰＤＭモジュール４１６は、スケーリングされた境界上に均等にプローブを配置することができる。図９は、いくつかの実施形態に係る、スケーリングされた境界上のプローブの均等な配置を示す。境界の垂直縁がスケーリングされているため、スケーリングされた垂直縁上にプローブ１０４を均一に配置すると、垂直縁と水平縁とで、プローブ１０４の数がほぼ同じになり得る。
【００９７】
いくつかの実施形態では、ＰＤＭモジュール４１６は、スケーリングされた境界上に連続して、均等にプローブを配置することができる。たとえば、ＰＤＭモジュール４１６は、最初の特徴点（任意に選択することができる）から開始し、第１のプローブを最初の特徴点に配置する。次いで、ＰＤＭモジュール４１６が、第１のプローブから所定の距離だけ離れた特徴点に第２のプローブを配置することができる。このプロセスは、ＰＤＭモジュール４１６が複数の特徴点のすべてを考慮するまで繰り返すことができる。
【００９８】
ステップ７０６では、ＰＤＭモジュール４１６は、ステップ７０２のスケーリング操作の逆をすることができ、それによっても、均等に配置されたプローブ間の距離を調節する。図１０は、いくつかの実施形態に係る、スケーリングされた境界の逆スケーリングを示す。境界の逆スケーリングに伴い、隣接するプローブ１０４間の距離も同様にスケーリングされる。したがって、垂直縁に沿うプローブの密度が水平縁に沿うプローブの密度に比べて高くなる。この方法で、分布１００２によって示されるように、ＰＤＭモジュール４１６により、プローブ位置で測定された垂直配向のヒストグラムのバランスを取ることができる。バランスが取られた垂直配向のヒストグラム１００２は全体として、プローブ１０４から得られる方向の情報もバランスが取られることを示す。
【００９９】
いくつかの実施形態では、ＰＤＭモジュール４１６は、実際に絵で見えるように特徴点の弧（たとえば、境界セクション）の長さを伸ばすことなく、弧の長さのスケーリングおよび逆スケーリングを行うように構成することができる。たとえば、ＰＤＭモジュール４１６は、特徴点の弧の長さを効率的にスケーリングするために、特徴点の周りの基礎となる座標系の分解能を増大または減少させるように構成することができる。
【０１００】
いくつかの実施形態では、ＰＤＭモジュール４１６は、連続的にプローブを配置することで、ステップ７０４と７０６を合わせることができる。たとえば、ＰＤＭモジュール４１６は、２つのプローブを分けるものとする均等な距離を定めることができる。そして、ＰＤＭモジュール４１６は、最初の特徴点（任意に選択することができる）で開始し、第１のプローブを最初の特徴点に配置する。次いで、ＰＤＭモジュール４１６は、垂直配向のヒストグラムに基づき、最初の特徴点に関連付けられる弧の長さを定めることができる。そして、ＰＤＭモジュール４１６は、弧の長さの関数として均一な距離をスケーリングして、第１のプローブと、この第１のプローブに隣接して配置される第２のプローブとの間のスケーリングされた距離を定めることができる。次いで、ＰＤＭモジュール４１６は、第１のプローブからスケーリングされた距離だけ離れた特徴点に第２のプローブを配置することができる。このプロセスは、ＰＤＭモジュール４１６が複数の特徴点のすべてを考慮するまで繰り返すことができる。この方法で、ＰＤＭモジュール４１６は、絵で見えるようにパターンの境界をスケーリングすること無く、ステップ７０４および７０６を実施することができる。
【０１０１】
いくつかの実施形態では、ＦＤＣモジュール４１４は、ステップ７０２で特徴点の弧の長さをスケーリングする前に、垂直配向のヒストグラムにローパスフィルタ操作を実施することができる。特徴点の弧の長さをスケーリングする前にローパスフィルタ操作を実施することには、いくつかの利点がある場合がある。第１に、ローパスフィルタ操作により、プローブ配置モジュールが垂直配向のヒストグラムからノイズを取り除くことができるようにすることができる。
【０１０２】
第２に、ローパスフィルタにより、ゼロ除算の問題に対処することができる。弧の長さのスケーリングを実施するＰＤＭモジュール４１６はしばしば、垂直配向のヒストグラムにおける配向ビンの値を分母として使用する。しかし、０の値の配向ビンがある場合があり、このことが、ゼロ除算の問題を生じる場合がある。ローパスフィルタ操作により、効果的にゼロの値の配向ビンを除去することでこの問題に対処することができる。
【０１０３】
第３に、このローパスフィルタ操作により、プローブ配置モジュールに、隣接する配向ビンが良好に示されている場合に、粗野に、実際より低く示されている特定の配向ビンを考慮しないようにさせることができる。たとえば、垂直配向のヒストグラムが、パターンが、８９度の垂直配向を有する構造上に１００個の特徴点を有し、９１度の垂直配向の構造上に１００個の特徴点を有し、しかし、９０度の垂直配向を有する構造上に１個の特徴点のみを有することを示すことができる。ローパスフィルタが無ければ、ＰＤＭモジュール４１６は、８９度または９１度の垂直配向を有する特徴点周りのプローブの数を制限しつつ、９０度の垂直配向を有する特徴点周りのプローブの数を増やすと思われる。このような、垂直配向のヒストグラムのバランスを取ることの抜本的対策は、プローブからバランスの取れた情報を取得するのに非効率的になる場合があり、この理由は、同様の配向が同様の情報を取得できるためである。言い換えると、８９度または９１度の垂直配向を示すプローブは、９０度の垂直配向を示すプローブと実質的に同様の情報を取得できる。したがって、９０度の垂直配向を示すプローブの数を増やすことは、特にプローブの全体数が制限されている場合に、全角度領域に渡ってバランスの取れた情報を取得するのに非効率的になる場合がある。
【０１０４】
ローパスフィルタにより、この問題に対処することができ、この理由は、垂直配向のヒストグラムのローパスフィルタにより、９０度の配向ビンの値を８９度および９１度の配向ビンの値と平滑化（たとえば、平均化）することができるためである。したがって、ローパスフィルタ操作により、９０度の配向ビンの値を実質的に増大させる。この方法で、ＰＤＭモジュール４１６により、９０度の垂直配向の周りの情報が８９度および９１度を示すプローブにより良好に得られたことが確認できる。したがって、ＰＤＭモジュール４１６は、９０度を示すプローブの数を激増させることは無い。
【０１０５】
いくつかの実施形態では、ＦＤＣモジュール４１４は、カーネルでヒストグラムを畳み込むことにより、ローパスフィルタ操作を実施することができる。いくつかの実施形態では、ＦＤＣモジュール４１４は、巡回畳み込みを実施するように構成することができる。たとえば、巡回畳み込みの下では、ＦＤＣモジュール４１４は、ヒストグラムの配向ドメイン（たとえば、０−２π）の限界周りのカーネルを包み込むことができる。ローパスフィルタ操作用のカーネルには、レイズドコサインカーネル（ｒａｉｓｅｄ  ｃｏｓｉｎｅ  ｋｅｒｎｅｌ）、コサイン二乗カーネル、またはヒストグラムを平滑化することができる任意の他の巡回関数を含むことができる。ＦＤＣモジュール４１４は、カーネルの幅を制御して、ヒストグラム上で実行される平滑化の量を制御することができる。たとえば、カーネルの幅によって２π／Ｎをカバーすることができ、ここで、Ｎは任意の整数とすることができる。
【０１０６】
いくつかの実施形態では、図１０に示すように短縁に沿うプローブの密度を増大させる代わりに、ＰＤＭモジュール４１６が、特徴点上のプローブを初期化し、初期化されたプローブに関連付けられる加重値を定めるように構成することができる。たとえば、プローブが短縁と関連付けられる場合（たとえば、プローブが小さい値の配向ビンに対応する縁上に配置される）、ＰＤＭモジュール４１６は、プローブに関連付けられる加重値を増大させることができる。プローブが長縁と関連付けられる場合（たとえば、プローブが大きい値の配向ビンに対応する縁上に配置される）、ＰＤＭモジュール４１６は、プローブに関連付けられる加重値を減少させることができる。次いで、加重値を使用して、様々な用途、たとえば境界の位置決めに対するプローブの寄与を変化させることができる。この技術を使用することで、ＰＤＦモジュール４１６は、（１）短縁に沿うプローブの密度を増大させること、および（２）位置決めの間に、増大したプローブ数を整合させることに必要な計算処理能力を少なくすることができる。しかし、ＰＤＭモジュール４１６は、図７のプロセスを使用する場合と比較して、プローブの分解能を減少させる場合がある。
【０１０７】
第２のプローブ配置機構−分布からのプローブのサンプリング
いくつかの実施形態では、プローブ配置モジュール４０８は、プローブの目標分布からプローブをサンプリングすることで、１つまたは複数の特徴点にプローブを配置するように構成することができる。プローブの目標分布は、パターンに関連付けられる自由度に対応する確率変数を含むことができる。たとえば、パターンに関連付けられる対象が２次元で移動することができる場合（たとえば、平行移動）、目標分布は、２つの確率変数：ｘ座標とｙ座標（または他の同等の表現）を有することができる。別の例としては、パターンに関連付けられる対象が平行移動および回転移動をすることができる場合、目標分布は３つの確率変数：ｘ座標、ｙ座標、および回転ベクトル（たとえば、配向）を有することができる。別の例としては、パターンに関連付けられる対象が平行移動、回転移動、およびスケーリング移動（たとえば、撮像デバイスから離れる、または撮像デバイスに向かう移動）をすることができる場合、目標分布は４つの確率変数：ｘ座標、ｙ座標、回転、およびスケールを有することができる。
【０１０８】
いくつかの実施形態では、プローブ配置モジュール４０８は、ノンパラメトリックな分布として目標分布を示すことができる。たとえば、プローブ配置モジュール４０８は、各確率変数のドメインを複数のビンに量子化し、対応するビンに分類される特徴点の数を単純にカウントすることができる。他の実施形態では、プローブ配置モジュール４０８は、パラメトリックな分布として目標分布を示すことができる。
【０１０９】
いくつかの実施形態では、プローブ配置モジュール４０８は、ＴＤＣモジュール４１２を使用して目標分布を定めることができる。ＴＤＣモジュール４１２は、特徴点に関連付けられる特徴に基づき、プローブの目標分布を定めるように構成することができる。たとえば、ＴＤＣモジュール４１２は、１つまたは複数の、たとえば特徴点の座標、特徴点に関連付けられる垂直配向、特徴点の回転、または特徴点のスケールに基づき、目標分布を定めることができる。
【０１１０】
いくつかの実施形態では、ＴＤＣモジュール４１２は、目標分布からサンプリングされる垂直配向の分布が、実質的にバランスが取られるように、目標分布を定めるように構成される。たとえば、図１に示すように、特徴点のパターンが水平な矩形であると仮定する。そのようなパターンは、図１１Ａに示すような傾斜ベクトル分布を有するモデルに関連付けられる場合がある。図１１Ａに示すように、大であるｙ方向の成分を有する縁が、大であるｘ方向の成分を有する縁に比べてかなり多い。したがって、図１のパターンの目標分布は、目標分布から抽出されたプローブが、図１１Ｂに示すように、バランスの取れた傾斜分布を有するようになるはずである。
【０１１１】
いくつかの実施形態では、ＴＤＣモジュール４１２は、目標分布が特徴点の分布と同様のサポートを有するように、目標分布を定めるように構成される。このことは、これらの実施形態において、プローブ配置モジュール４０８が、既存の特徴点のセットから再サンプリング（たとえば、重要度のサンプリング）することによってプローブをサンプリングするように構成されることから、重要である。この目的で、以下に論じるように、ＴＤＣモジュール４１２は、特徴点の分布と目標分布の両方のための混合モデルを使用するように構成される。
【０１１２】
いくつかの実施形態では、ＴＤＣモジュール４１２は、目標分布をＰＤＭモジュール４１４に提供し、ＰＤＭモジュール４１４は、目標分布からサンプルを抽出してプローブの位置を定めるように構成される。
【０１１３】
いくつかの実施形態では、ＰＤＭモジュール４１４は、重要度のサンプリング技術を使用して、目標分布からサンプルを抽出することができる。他の実施形態では、ＰＤＭモジュール４１４は、パターンの境界を定め、パターンの境界に沿ってプローブのサンプルを生成するように構成することができる。この技術は、目標分布から少数のサンプルのみを抽出する場合に有用とすることができる。この技術には、サンプリングによって生成されたプローブのセットが、再サンプリングプロセスにおけるランダムな変動によって影響を受けないようにでき、プローブがパターンの境界の幾何学的範囲全体に渡って分配されることを保証できるという利点がある。
【０１１４】
目標分布算出
パターンが２つの自由度を有する場合（たとえば、平行移動）、ＴＤＣモジュール４１２は、以下の関係を満たす重み付け関数ｆ（ｘ，ｙ）を定めることができる。
0006702732.tif 000002
0006702732.tif 000003
0006702732.tif 000004
式中、ｉはｉ番目の特徴点を示す。この最適化ルーチンの目的は、（１）特徴点で測定された傾斜ベクトルのｘ成分の重み付けされた合計と、（２）特徴点で測定された傾斜ベクトルのｙ成分の重み付けされた合計とを同等として扱う関数ｆ（ｘ，ｙ）を識別することである。場合によっては、ＴＤＣモジュール４１２は、傾斜ベクトルの大きさのみのバランスを取ることができる。したがって、ｘｉは、ｉ番目の特徴点において測定された傾斜ベクトルのｘ成分の絶対値に関するものとすることができ、ｙｉは、ｉ番目の特徴点において測定された傾斜ベクトルのｙ成分の絶対値に関するものとすることができる。
【０１１５】
ＴＤＣモジュール４１２が重み付け関数ｆ（ｘ，ｙ）を定めると、ＴＤＣモジュール４１２は、重み付け関数ｆ（ｘ，ｙ）をＰＤＭモジュール４１６に提供することができる。いくつかの実施形態では、重み付け関数は、ＰＤＭモジュール４１６が１つまたは複数の特徴点にプローブを配置するのに使用することができる確率分布の形式を取る場合がある。この場合のＰＤＭモジュール４１６が重み付け関数ｆ（ｘ，ｙ）を、そこからプローブをサンプリングするための確率分布として使用するため、非負に規制されなければならず、少なくともいくつかの成分（ｘ，ｙ）については正になり得る。そのような実施形態のために、「目標分布」という用語が、本明細書においてｆ（ｘ，ｙ）を示す確率分布を称するのに使用される。
【０１１６】
いくつかの実施形態では、重み付け関数がいくつかの他の手段によって選択されたプローブの既存のセットを重み付けするのに使用され、最小化するような方法で相対的重要度に影響を与える。
0006702732.tif 000005
0006702732.tif 000006
0006702732.tif 000007
【０１１７】
パターンが３つの自由度を有する場合（たとえば、平行移動および回転移動）、ＴＤＣモジュール４１２は目標分布に、回転移動に対応する回転変数θを組み込むことができる。ＴＤＣモジュール４１２は、原点に対する回転変数θを規定することができる。
【０１１８】
いくつかの実施形態では、原点は複数の特徴点の質量中心とすることができる。いくつかの実施形態では、原点は回転中心とすることができる。回転中心は、その周りで回転モーメントが最小になる点とすることができる。回転中心は、固有の全体的最小値に対応し、基底ベクトル（たとえば、座標系）の選択とは独立している。したがって、回転中心は、複数の特徴点に固有の幾何学量である。回転中心は、以下のように算出することができる。
0006702732.tif 000008
式中、ｐは、基準点（任意に選択することができる）に対する基準ベクトル、ｕは特定の特徴点における単位法線ベクトル、Ｘはクロス積行列（ｃｒｏｓｓ  ｐｒｏｄｕｃｔ  ｍａｔｒｉｘ）である。図１１は、いくつかの実施形態に係る、基準ベクトルｐと単位法線ベクトルｕとの関係を示す。正規直交の規定では、
0006702732.tif 000009
となる。算出目的のために、正規直交の規定での座標系の回転中心は、以下のように算出することができる。
0006702732.tif 000010
式中、下付文字ｘおよびｙは、対応するベクトルのｘ成分およびｙ成分を示す。
【０１１９】
原点が定められると、ＴＤＣモジュール４１２は、原点からｉ番目の特徴点の中心までのベクトルである、ｉ番目の特徴点の位置ベクトルｖｉを使用して回転変数θを定めることができ、また、ｉ番目の特徴点における回転単位ベクトル
0006702732.tif 000011
を定めることができる。図１２は、いくつかの実施形態に係る、位置ベクトルｖｉと回転単位ベクトル
0006702732.tif 000012
との関係を示す。
【０１２０】
いくつかの実施形態では、回転変数θｉは、位置ベクトルｖｉのノルムとは独立しているものとすることができる。位置ベクトルｖｉのノルムとは独立している回転変数θｉにより、位置ベクトルｖｉのノルムに基づいてプローブ位置を区別することのない目標分布を提供することができる。たとえば、ＴＤＣモジュール４１２は、以下のようにｉ番目の特徴点の回転変数θｉを定めることができる。
0006702732.tif 000013
この回転変数θｉの表示は、大きい角度ステップサイズωで形状を粗めに調整するのに有用である場合がある。
【０１２１】
いくつかの実施形態では、回転変数θｉは、位置ベクトルｖｉのノルムを考慮に入れることができる。
0006702732.tif 000014
であるため、ＴＤＣモジュール４１２は、角度精度を上げるために、原点からさらに離れた特徴点の寄与を強調することができる。たとえば、ＴＤＣモジュール４１２は、以下のようにｉ番目の特徴点の回転変数θｉを定めることができる。
0006702732.tif 000015
または
0006702732.tif 000016
位置ベクトルｖｉのノルムに依存する回転変数θｉにより、原点からさらに離れた位置にプローブを配置するのに有利になる目標分布を提供することができる。この方法で、目標分布により、原点からさらに離れた特徴点でより多くのプローブをサンプリングすることができる。
【０１２２】
いくつかの実施形態では、ＴＤＣモジュール４１２は、パターンの形状に基づき、回転変数θｉの表示を定めることができる。たとえば、ＴＤＣモジュール４１２は、パターンがレバーアームを含むことを定めることができる。この場合、ＴＤＣモジュール４１２は、どの表示を回転変数θに使用するかの判定において、レバーアームを考慮に入れることができる。別の例としては、ＴＤＣモジュール４１２は、同心円、またはナットが別のナットの内側にあるものを含むパターンを定めることができる。この場合、ＴＤＣモジュール４１２は、どの表示を回転変数θに使用するかの判定において、同心円、またはナットが別のナットの内側にあるものを考慮に入れることができる。
【０１２３】
ＴＤＣモジュール４１２が回転変数の表示を定めると、ＴＤＣモジュール４１２は定められた表示を使用して各特徴点を表示することができる。次いで、ＴＤＣモジュール４１２は、以下の関係を満たす重み付け関数ｆ（ｘ，ｙ，θ）を見出すことにより、特徴点の表示に基づいて目標分布を定めるように構成することができる。
0006702732.tif 000017
式中、以下の制限を伴う。
0006702732.tif 000018
0006702732.tif 000019
式中、ｉはｉ番目の特徴点を示す。
【０１２４】
ＴＤＣモジュール４１２により目標分布ｆ（ｘ，ｙ，θ）が定められると、ＴＤＣモジュール４１２はＰＤＭモジュール４１６に目標分布ｆ（ｘ，ｙ，θ）を提供することができる。次いで、ＰＤＭモジュール４１６は目標分布ｆ（ｘ，ｙ，θ）を確率分布として使用してパターン上のプローブをサンプリングすることができる。
【０１２５】
上述した最適化プロセスを容易にするためにプローブ配置モジュール４０８は、目標分布ｆ（ｘ，ｙ，θ）の関数形態を仮定することができる。
【０１２６】
いくつかの実施形態では、プローブ配置モジュール４０８は、線形形態を有する目標分布ｆ（ｘ，ｙ，θ）を仮定することができる。線形関数は負になり得るが、ｆ（ｘｉ，ｙｉ，θｉ）≧０，∀ｉの制限により、すべての特徴点における目標分布を正に制限することができる。目標分布ｆ（ｘ，ｙ，θ）が線形形態を有する場合、目標分布を見出すための最適化ルーチンは単純になる場合がある。しかし、線形関数の区域は限られるため、すべての制限を満足する線形関数を見出すことは困難になる場合がある。
【０１２７】
いくつかの実施形態では、プローブ配置モジュール４０８は、目標分布ｆ（ｘ，ｙ，θ）が非線形形態を有することを仮定することができる。目標分布ｆ（ｘ，ｙ，θ）が非線形形態を有する場合、目標分布を見出すための最適化ルーチンは複雑になる場合がある。しかし、非線形関数の区域は広いため、すべての制限を満たす非線形関数を見出すことは容易である場合がある。
【０１２８】
いくつかの実施形態では、ＴＤＣモジュール４１２は、目標分布ｆ（ｘ，ｙ，θ）を、特徴点分布ｐｐ（ｘ，ｙ，θ｜パラメータ）の逆数（ｉｎｖｅｒｓｅ）として設定することができる。この場合、ＴＤＣモジュール４１２は、ＦＤＣモジュール４１４から特徴点分布ｐｐ（ｘ，ｙ，θ）を受信し、逆数：
0006702732.tif 000020
を算出することで間接的に目標分布ｆ（ｘ，ｙ，θ）を定めることができる。目標分布ｆ（ｘ，ｙ，θ）が特徴点分布ｐｐ（ｘ，ｙ，θ）の逆数として定められる場合、目標分布ｆ（ｘ，ｙ，θ）により、残りの特徴点に比べて比較的異なる特徴点の位置でより多くのプローブがサンプリングされる。
【０１２９】
ＦＤＣモジュール４１４は、特徴点分布ｐｐ（ｘ，ｙ，θ）を混合モデルとしてモデル化することができる。いくつかの実施形態では、混合モデルは、ガウスの混合モデル（ＧＭＭ）：
0006702732.tif 000021
を含むことができる。ＧＭＭは、４つのパラメータ：ガウス分布の数Ｎ、ｋ番目のガウス分布の加重値αｋ、ｋ番目のガウス分布の平均ベクトル
0006702732.tif 000022
、およびｋ番目のガウス分布の分散行列
0006702732.tif 000023
を有する。他の実施形態では、混合モデルは三角分布の混合を有することができる。三角分布の混合は、速く算出することができ、また、特徴点の柔軟なグルーピングを提供する、同様の望ましい特性を与えることができる。
【０１３０】
いくつかの実施形態では、ＦＤＣモジュール４１４は、特徴点のクラスタリング、および特徴点に最も合うクラスタの数の判定により、ＧＭＭのためのガウス分布の数Ｎを見積もることができる。たとえば、ＦＤＣモジュール４１４は、特徴点のｋ平均クラスタリング操作を実施して、ガウス分布の数Ｎを見積もることができる。
【０１３１】
残りのパラメータのセット
0006702732.tif 000024
は、特徴点に与えられるパラメータの確度を最大化することで定めることができる。いくつかの実施形態では、ＦＤＣモジュール４１４は、期待値最大化技術を使用して、特徴点に与えられたパラメータの確度を最大化することができる。期待値最大化を実施するために、ＦＤＣモジュール４１４は、クラスタリングステップの結果を使用して、パラメータのセット
0006702732.tif 000025
を初期化することができる。
【０１３２】
上記で論じたように、ＴＤＣモジュール４１２は、特徴点分布ｐｐ（ｘ，ｙ，θ）をただ逆にすることにより、目標分布ｆ（ｘ，ｙ，θ）を定めることができる。しかし、この目標分布ｆ（ｘ，ｙ，θ）は、最も共通していない垂直配向の縁上にほとんどのプローブを配置する場合がある。たとえば、パターンが２Ｄの平行移動のみ行うことが可能であり、パターンが角の丸い矩形の境界を有する場合、この目標分布ｆ（ｘ，ｙ）は、ＰＤＭモジュール４１６に、角の位置の周りからほとんどをサンプリングさせる場合がある。
【０１３３】
そのような問題に対処するために、いくつかの実施形態では、ＴＤＣモジュール４１２は、特徴点分布ｐｐ（ｘ，ｙ，θ）を変形し、変形した特徴点分布
0006702732.tif 000026
を逆にして、目標分布ｆ（ｘ，ｙ，θ）を定めることができる。前述の「第１のプローブ配置機構」において、この変形は、平滑化カーネルをｐｐ（ｘ，ｙ，θ）に適用する形態を取る。
【０１３４】
場合によっては、ＴＤＣモジュール４１２は、逆にする以外の方法によって特徴点分布を変形することで、目標分布を定めることができる。そのような実施形態では、特定の条件を満たす新しい加重値αｋを見出すことによって、特徴点分布
0006702732.tif 000027
を変形することができる。パラメータのセット
0006702732.tif 000028
を見積もる際に、ＴＤＣモジュール４１２は特徴点の柔軟なグルーピング（たとえば、ガウス分布への柔軟なグルーピング）を効率的に実施する。ここで、ＴＤＣモジュール４１２は、それらのグルーピングを有し、ＴＤＣモジュール４１２は、新しい加重値
0006702732.tif 000029
を見出して各グループ（たとえば、各ガウス分布）を個別に再重み付けするように構成することができる。
【０１３５】
たとえば、ＴＤＣモジュール４１２は
0006702732.tif 000030
を表示することができる。この表示では、ＴＤＣモジュール４１２は、以下の関係を最小化する加重値
0006702732.tif 000031
を見出すように構成することができる。
0006702732.tif 000032
式中、以下の制限を伴う。
0006702732.tif 000033
ラグランジュ乗数を使用して、ＴＤＣモジュール４１２は、
0006702732.tif 000034
についての連立線形方程式
0006702732.tif 000035
0006702732.tif 000036
のように、この問題を減少させることができる。
【０１３６】
ＴＤＣモジュール４１２は、この連立線形方程式を
0006702732.tif 000037
について解くことができるが、ＴＤＣモジュール４１２はさらなる制限を受ける。上記の連立線形方程式は、変形した加重値
0006702732.tif 000038
が負になることを防止しない、または、大きな加重値
0006702732.tif 000039
が、特徴点の小さいグループ（たとえば、特徴点分布ｐｐ（ｘ，ｙ，θ）におけるその元の加重値αｋが小であった）から見積もられたガウスに割り当てられることを防止しない。ＴＤＣモジュール４１２は、それらの制限をプログラムに基づいて適用することができる。
【０１３７】
また、ＴＤＣモジュール４１２は、変形した加重値
0006702732.tif 000040
を規定の値より大となるように要求することで、隣接するプローブ間の最小プローブ距離を課すように構成される。
0006702732.tif 000041
式中、αｋは、特徴点分布ｐｐ（ｘ，ｙ，θ）におけるｋ番目のガウス分布の加重値、Ｎｅｄｇｅｓは、特徴点分布ｐｐ（ｘ，ｙ，θ）における加重値αｋを見積もるのに使用される特徴点の数、Ｎｐｒｏｂｅｓは、プローブの目標数（たとえば、６４）、ｄｍａｘは、特徴点の単位または任意の所定の単位におけるプローブ間の最大の許容可能な距離である。上述の方程式は以下のように整理し直すことができる。
0006702732.tif 000042
この新しい関係は、混合要素ｋについての、縁の数のプローブの数に対する比がｄｍａｘの単位および１の単位によって境界が定められていることを示す。したがって、クラスタｋの隣接するプローブは、ｄｍａｘの単位から少しも離れることなく、また、１の単位よりも近づくことなく、配置することができる。
【０１３８】
連立線形方程式が、制限に反する少なくとも１つの加重値αｋを有する結果を与える場合、ＴＤＣモジュール４１２は、境界のケースのすべての可能性のある組合せに渡って繰り返し、最適な残りの加重値を算出し、制限された最小値を選択することができる。
【０１３９】
たとえば、ＴＤＣモジュール４１２は、線形方程式についてすべての可能性のある境界状態のセット（たとえば、
0006702732.tif 000043
）を定めることができる。境界状態の各セットは、変形された加重値
0006702732.tif 000044
のサブセットの境界状態を含む場合がある。次いで、境界状態の各セットについて、ＴＤＣモジュール４１２は、加重値
0006702732.tif 000045
のサブセットの値を対応する境界状態の値に固定し、境界状態の無い残りの自由加重値（ｆｒｅｅ  ｗｅｉｇｈｔ）
0006702732.tif 000046
について連立線形方程式を解くことができる。この方法で、ＴＤＣモジュール４１２は、すべての可能性のある境界状態のセットの下の解の中から最小スコアの解を選択することによって制限に与えられた連立線形方程式の大域解を定めることができる。
【０１４０】
場合によっては、ＧＭＭのガウス分布の数が、特徴点がある寸法（dimension:次元、大きさ、範囲、特徴）の数より大きい場合、ＧＭＭのパラメータのいくつかは、一次従属である場合がある。たとえば、ガウス分布の数が、特徴点がある寸法の数より大きい場合、ガウス分布の平均ベクトルは一次従属になる場合がある。
【０１４１】
この問題に対処するために、ＴＤＣモジュール４１２は、ＧＭＭのパラメータについて、たとえばチホノフ正則化（Ｔｉｋｈｏｎｏｖ  ｒｅｇｕｌａｒｉｚａｔｉｏｎ）を使用して、正則化するように構成することができる。この目的で、ＴＤＣモジュール４１２は、以下の関係を最小化するために最適化の問題を再公式化することができる。
0006702732.tif 000047
新しいラグランジュの公式は、平均ベクトルの（ｘ，ｙ，θ）の成分のバランスが取られ、変形した加重値の合計が１である制限に従い、特徴点分布ｐｐ（ｘ，ｙ，θ）と目標分布
0006702732.tif 000048
の間の変形した加重値
0006702732.tif 000049
の変化を数値化することを求める。
【０１４２】
ＴＤＣモジュール４１２は、上述したラグランジュの関係を満たす加重値を直接見出すことができる。しかし、前述のように、この関係は、加重値
0006702732.tif 000050
が負になることを妨げない、または、大きな加重値
0006702732.tif 000051
が、特徴点の小さいグループ（たとえば、特徴点分布ｐｐ（ｘ，ｙ，θ）におけるその元の加重値αｋが小であった）から見積もられたガウスに割り当てられることを妨げない。ＴＤＣモジュール４１２は、上記で説明したように、それらの制限をプログラムに基づいて適用することができる。このことは数学的に有効であり、この理由は、
0006702732.tif 000052
における上述のラグランジュの関係が二次式であるためであり、そのため、加重値
0006702732.tif 000053
の１つが負である場合、最適値が１つ（または複数）の境界状態にあるものとなる。
【０１４３】
まとめると、特徴点分布ｐｐ（ｘ，ｙ，θ）のパラメータに基づいて目標分布
0006702732.tif 000054
のパラメータを識別するために、ＴＤＣモジュール４１２は以下の手順を使用することができる。
１．
0006702732.tif 000055
および
0006702732.tif 000056
を規定する。
２．基礎を成すデータの寸法（dimension:次元、大きさ、範囲、特徴）であるＮＤｉｍがＮ＜＝ＮＤｉｍである場合、以下の方程式を使用して
0006702732.tif 000057
について解く。
0006702732.tif 000058
この系が特異である場合、ＴＤＣモジュール４１２は正則化を使用してこの系を解くことができる。たとえば、ＴＤＣモジュール４１２が行列方程式
0006702732.tif 000059
を解こうと試みるが、
0006702732.tif 000060
が特異である場合、ＴＤＣモジュール４１２は代わりに
0006702732.tif 000061
を解くことができる。この方法で、ＴＤＣモジュール４１２は、解ベクトルのＬ２−ノルムの合計を最小化することができ、このことは、ひいては、大きい正および負のαｋ（合算して単一にする）を有する解を妨げることができる。
３．Ｎ＞ＮＤｉｍである場合、以下の方程式を使用して
0006702732.tif 000062
について解く。
0006702732.tif 000063
４．ステップ２またはステップ３の解を次の制限と照らし合わせる。
0006702732.tif 000064
５．解が加重値
0006702732.tif 000065
の有効な範囲の外にある場合、すべての可能性のある境界状態のセット（たとえば、制限）について、ステップ２または３の修正版を使用して制限されていない
0006702732.tif 000066
の解ベクトルを見出す。検索を通して、ＴＤＣモジュール４１２は
0006702732.tif 000067
および
0006702732.tif 000068
の最小値を追跡することができる。前者の関係がゼロより大である場合、ＴＤＣモジュール４１２は、前者の関係を使用して
0006702732.tif 000069
についての解ベクトルを選択することができる。前者の関係がゼロより大でない場合、ＴＤＣモジュール４１２は、後者の関係を使用して
0006702732.tif 000070
についての解ベクトルを選択することができる。
【０１４４】
目標分布からのプローブのサンプリング
ＴＤＣモジュール４１２が変形した特徴点分布
0006702732.tif 000071
を定めると、ＴＤＣモジュール４１２は、変形した特徴点分布
0006702732.tif 000072
（または変形した特徴点分布の逆数）をＰＤＭモジュール４１６に提供することができる。次いで、ＰＤＭモジュール４１６は、変形した特徴点分布
0006702732.tif 000073
の逆数からサンプリングして、画像の１つまたは複数の特徴点のプローブの位置を定めることができる。
【０１４５】
直観的に言うと、ＴＤＣモジュール４１２は、変形した特徴点分布
0006702732.tif 000074
に関するｘ、ｙ、およびθの期待値ができるだけ同様になるように、変形した特徴点分布
0006702732.tif 000075
を選択するように構成される。
0006702732.tif 000076
【０１４６】
重要度のサンプリングにより、別の異なる分布から抽出されたサンプルを同様のサポートを有するサンプルの状態で重み付けすることによってＰＤＭモジュール４１６が目標分布からサンプルを抽出することができる。言い換えると、
0006702732.tif 000077
となる。式中、Ｓｐｒｏｂｅｓはプローブのセット、ＳＩＰは特徴点のセットである。したがって、ＰＤＭモジュール４１６は、この関係を使用して、
0006702732.tif 000078
により、特徴点分布
0006702732.tif 000079
から抽出されたサンプルの重み付けをすることができる。
【０１４７】
したがって、ＰＤＭモジュール４１６がパターンの境界に沿うすべての特徴点にプローブを配置することによってプローブを抽出する場合、ＰＤＭモジュール４１６は、上述の比
0006702732.tif 000080
によってプローブの重み付けをすることができる。いくつかの実施形態では、ＰＤＭモジュール４１６は、（１）隣接するプローブをパターンの境界に沿って上述の比の逆数の距離だけ離間させること、ならびに（２）プローブの所望の数および最初の縁の数を補償することにより、同様の効果を達成することができる。
【０１４８】
したがって、いくつかの実施形態では、変形した特徴点分布
0006702732.tif 000081
の逆数からサンプリングすることを、以下の量だけ隣接するプローブを離間させるように要求することと等しくすることができる。
0006702732.tif 000082
式中、Ｎｅｄｇｅｓは、特徴点分布
0006702732.tif 000083
のパラメータを定めるのに使用される特徴点の数を示し、Ｎｐｒｏｂｅｓは、プローブの目標数を示す。この方法で、標本として不十分である特徴点に沿うプローブの密度を増大させることができる。
【０１４９】
そのように隣接するプローブを離間させるように要求するために、ＰＤＭモジュール４１６は、引き続き、１つまたは複数の特徴点上にプローブを配置することができる。たとえば、ＰＤＭモジュール４１６が最初の特徴点（任意に選択することができる）から開始し、第１のプローブを最初の特徴点に配置する。次いで、ＰＤＭモジュール４１６が、上述の関係を使用して、第１のプローブと、第１のプローブに隣接して配置される第２のプローブとの間の距離を定めることができる。次いで、ＰＤＭモジュール４１６は第２のプローブを、第１のプローブから定められた距離だけ離れた特徴点に配置することができる。このプロセスは、ＰＤＭモジュール４１６が、特徴点分布
0006702732.tif 000084
を定めるのに使用される複数の特徴点のすべてを考慮するまで繰り返すことができる。
【０１５０】
隣接するプローブを特定の量だけ離間させることの要求は、隣接する特徴点の弧の長さを変更する（たとえば、伸ばす）と解釈することができる。上述したように、特徴点は、特徴点の中心に配置された、初期化されたプローブの表示と見なすことができる。したがって、隣接するプローブを特定の量だけ離間させることの要求は、隣接する特徴点の中心間の弧の長さを変更することと解釈することができる。したがって、プローブを配置するための第１の機構（図５〜１０に関して示す）と、プローブを配置するための第２の機構（図１１〜１２に関して示す）とは、同様の結果をもたらす。
【０１５１】
本明細書の議論の多くが、ｘ軸成分、ｙ軸成分、および回転ベクトルを含めた混合モデルによって、可能性のあるスペースが広げられた場合に焦点を当てているが、開示の技術は、混合モデルによって広げられた、確率空間の次元数を増大させることまで広げることができる。たとえば、プローブ配置モジュール４０８は、４次元のスペース
0006702732.tif 000085
（式中、Φはスケールを示す）の情報のバランスを取るように構成することができる。最適化ステップがわずかに複雑になる場合があるが、プローブ配置モジュール４０８は、３次元のスペースの筋書きと同じ技術を利用することができる。たとえば、プローブ配置モジュール４０８は、ラグランジュ乗数を使用して（前述のように）連立線形方程式に減少させることで、以下を最小化するように構成することができる。
0006702732.tif 000086
式中、以下の制限を伴う。
0006702732.tif 000087
プローブ配置モジュール４０８は、加重値
0006702732.tif 000088
が負にならないようにするか、プローブをいくつかの縁の位置に極度に集中させないようにすることを確実にするように構成することができる。この目的で、３次元のスペースの筋書きと同様に、プローブ配置モジュール４０８は、境界制限をプログラムに基づいて適用するように構成することができる。
【０１５２】
３次元のスペースの筋書きと同様に、プローブ配置モジュール４０８は、平均ベクトルセットが線形的に独立していない場合、および混合モデルの要素数（Ｎ）が次元数（ここでは４）を超える場合、チホノフ正則化を適用することができる。
0006702732.tif 000089
【０１５３】
図１３には、いくつかの実施形態に係る、パターンの１つまたは複数の特徴点上のプローブのサンプリングのプロセスが要約されている。図１３において、プローブ配置モジュール４０８は、パラメトリック分布として目標分布を示す。しかし、当業者は、図１３のプロセスを変更して、プローブ配置モジュール４０８が非パラメトリック分布として目標分布を示す場合に適応させることができる。
【０１５４】
ステップ１３０２では、ＩＰＤモジュール４０６は、画像の特徴点を定めることができる。場合によっては、ＩＰＤモジュール４０６は、縁検出技術を使用して特徴点を識別することができる。縁検出技術には、たとえば、キャニー縁検出技術またはハフ変換技術を含めることができる。縁検出技術は、たとえば、Ｓｏｂｅｌオペレータ、キルシュオペレータ、プルウィットオペレータ、ガボアフィルタ、ハールウェーブレットフィルタ、画像のピクセル値の変化（たとえば、画像の高周波数成分）を検出できる任意の他のフィルタ、および／またはそれらの任意の組合せを含む、１つまたは複数の縁検出オペレータを使用することができる。
【０１５５】
いくつかの実施形態では、ＩＰＤモジュール４０６は、特徴点の位置情報をＦＤＣモジュール４１４に提供することができる。ＦＤＣモジュール４１４は、特徴点に関連付けられる自由度を示す変数を使用して各特徴点を示すことができる。たとえば、特徴点が２次元で移動することが知られている場合、特徴点は、特徴点の（ｘ，ｙ）傾斜要素に対応する２次元ベクトルとして示すことができる。別の実施形態では、特徴点が３次元で移動することが知られている場合、特徴点は、特徴点の（ｘ，ｙ）傾斜要素および特徴点の回転配向（またはその関数）に対応する３次元ベクトルとして示すことができる。
【０１５６】
ステップ１３０４では、ＦＤＣモジュール４１４は、特徴点をクラスタリングするように構成することができる。たとえば、ＦＤＣモジュール４１４は、その表示におけるユークリッド距離内で互いに近接する特徴点をクラスタリングすることにより、特徴点をクラスタリングすることができる。いくつかの実施形態では、ＦＤＣモジュール４１４は、ｋ平均クラスタリング技術、平均シフトクラスタリング技術、「ｂａｌａｎｃｅｄ  ｉｔｅｒａｔｉｖｅ  ｒｅｄｕｃｉｎｇ  ａｎｄ  ｃｌｕｓｔｅｒｉｎｇ  ｕｓｉｎｇ  ｈｉｅｒａｒｃｈｉｅｓ」（ＢＩＲＣＨ）クラスタリング技術，または、同様の性質で特徴点をグルーピングすることができる任意の他の適切なクラスタリング技術を使用することができる。
【０１５７】
ステップ１３０６では、ＦＤＣモジュール４１４は、ステップ１３０４からのクラスタに基づき、特徴点分布を定めることができる。たとえば、ＦＤＣモジュール４１４は、ガウス混合モデルを使用して特徴点分布を示すように構成することができる。この場合、ＦＤＣモジュール４１４は、クラスタリングステップからのクラスタの数を使用して、ガウス混合モデルのためのガウス分布の数を定めるように構成することができる。また、ＦＤＣモジュール４１４は、期待値最大化操作を実施して、ガウス混合モデルのパラメータのセットの最尤推定値を定めるように構成することができる。この方法で、ＦＤＣモジュール４１４は、特徴点分布
0006702732.tif 000090
を定めることができる。ＦＤＣモジュール４１４は、特徴点分布
0006702732.tif 000091
をＴＤＣモジュール４１２に提供することができる。
【０１５８】
ステップ１３０８では、ＴＤＣモジュール４１２は、変形した特徴点分布
0006702732.tif 000092
を特徴点分布
0006702732.tif 000093
から定めることができる。この目的で、ＴＤＣモジュール４１２は、上述のように、条件付き最適化を実施して、変形した特徴点分布の変形した加重値
0006702732.tif 000094
を再算出することができる。場合によっては、ＴＤＣモジュール４１２は、変形した特徴点分布
0006702732.tif 000095
を逆にすることで、目標プローブ分布を算出することができる。次いで、ＴＤＣモジュール４１２は、変形した特徴点分布（または、変形した特徴点分布の逆数）をＰＤＭモジュール４１６に提供することができる。
【０１５９】
ステップ１３１０では、ＰＤＭモジュール４１６は、目標分布（たとえば、変形した特徴点分布の逆数）をサンプリングして、１つまたは複数の特徴点上のプローブの位置を定めるように構成される。場合によっては、ＰＤＭモジュール４１６は、以下の関係を使用して２つの隣接するプローブ間のスペースを定めることができる。
0006702732.tif 000096
ＰＤＭモジュール４１６は、上記関係を使用して、すべての隣接する特徴点の中心間（または、隣接する特徴点のサブセットの中心間）の距離を定めるか、変更することができる。
【０１６０】
図１４Ａは、いくつかの実施形態に係る、図１３に示すプロセスを使用した矩形上へのプローブの配置を示す。矩形は、２つの自由度を有すると仮定される（たとえば、矩形は、平行移動のみすると仮定される）。この場合、ＰＤＭモジュール４１６は、矩形の短縁に沿うプローブの密度を、矩形の長縁に比べて増加させた。この結果は、図５〜１０に関して論じたように、垂直配向のヒストグラムのバランスを取る結果と同様である。
【０１６１】
図１４Ｂは、いくつかの実施形態に係る、図１３に示すプロセスを使用したレバーアームを有する円形の対象上へのプローブの配置を示す。パターンは、２つの自由度を有すると仮定される（たとえば、パターンは平行移動のみを行うと仮定される）。この場合、ＰＤＭモジュール４１６は、円上のｙ方向のプローブをわずかに多く増やすことで、レバーアーム上の付加的なｘ方向のプローブを補償する。
【０１６２】
図１５Ａは、いくつかの実施形態に係る、図１３に示すプロセスを使用した矩形上へのプローブの配置を示す。矩形は、３つの自由度を有すると仮定され（たとえば、矩形は平行移動および回転移動をすると仮定される）、回転ベクトルは、以下の式で与えられる。
0006702732.tif 000097
この場合、ＰＤＭモジュール４１６は、図１４Ａに示すように、矩形の長縁に比べ、矩形の短縁に沿うプローブの密度を増大させた。しかし、ＰＤＭモジュール４１６は、長縁に沿うプローブの距離も変更し、矩形の原点（たとえば、矩形の質量中心）からより離れたプローブの数を増加させた。この理由は、回転変数θが、矩形の原点とプローブの間の距離に依存していたためである。
【０１６３】
図１５Ｂは、いくつかの実施形態に係る、図１３に示すプロセスを使用した、レバーアームを有する円形対象上へのプローブの配置を示す。パターンは、３つの自由度を有すると仮定される（たとえば、パターンは平行移動および回転移動をすると仮定される）。この場合ＰＤＭモジュール４１６は、レバーに沿うプローブの密度を増大させ、この理由は、回転変数θが、矩形の原点とプローブの間の距離に依存していたためである。しかし、ＰＤＭモジュール４１６は、円形境界の周りに配置されたプローブの数を減少させた。特に、ＰＤＭモジュール４１６は、水平軸に近い境界に沿うプローブの数を減少させた。この場合、レバーアームの縁は回転自由度の位置決め情報のすべてを含み、したがって、より多くのプローブが与えられる。これらのプローブは、ｘ方向の位置決めに有用とすることもできるが、ｙ方向の情報は完全に欠如している。したがって、ＰＤＭモジュール４１６は、円の頂部および底部に、左側および右側より多くのプローブを追加して、ｙ方向の情報をモデルに示す。
【０１６４】
図１６Ａ〜Ｂは、いくつかの実施形態に係る、図１３に示すプロセスを使用した穴を有するパターン上へのプローブの配置を示す。境界が別の境界の完全に内側にある場合（たとえば、同心円、または別のナットの内側のナット）、プローブ配置モジュール４０８が、境界の内の１つに、プローブを配置することのより高い優先度を与えるべきかどうかを、そしてその場合、どの境界により高い優先度を与えるべきかを制御することができる。いくつかの実施形態では、プローブ配置モジュール４０８は、回転変数θで、そのような優先度を符号化することができる。
【０１６５】
図１７Ａ〜１７Ｃは、いくつかの実施形態に係る、回転変数θの表示がどのようにプローブの位置を変化させるのかを示す。図１７Ａは、回転変数θが位置ベクトル
0006702732.tif 000098
のノルムとは独立している場合のプローブの配置に対応する。図１７Ｂは、回転変数θが以下のように、位置ベクトル
0006702732.tif 000099
のノルムに依存している場合のプローブの配置に対応する。
0006702732.tif 000100
この式は、線形形態の半径を組み込んで、角運動量とみなすことができる量をモデル化する。図１７Ｃは、回転変数θが以下のように、位置ベクトル
0006702732.tif 000101
のノルムに依存している場合のプローブの配置に対応する。
0006702732.tif 000102
この式は、２乗を使用して、慣性の角運動量と同質の量を形成する。用途に応じて、これらの関数の１つがより好ましくなり得る。半径の項（ｒａｄｉｕｓ  ｔｅｒｍ）の順に増大させることで、角度成分が最も高いプローブをパターンの最も外側の領域に押しやる傾向になる。このことは、画像のパターンを探す場合に、それを越えてプローブを適用するスペースをとる際に、密接に関連する。そのことは、角度位置決め精度にも密接に関連する。
【０１６６】
図１８Ａ〜１８Ｂは、いくつかの実施形態に係る、図１３に示すプロセスを使用した細長いアームを有するパターン上へのプローブの配置を示す。図１８Ａでは、プローブ配置モジュール４０８は、パターンが３つの自由度を有すると仮定する（たとえば、パターンは、平行移動および回転移動をすると仮定される）。図１８Ｂでは、プローブ配置モジュール４０８は、パターンが４つの自由度を有すると仮定する（たとえば、パターンは、平行移動、回転移動、および撮像デバイスに向かう／撮像デバイスから離れる動きをすると仮定される）。
【０１６７】
これらの図は、興味深いケースを示しており、この理由は、特徴点分布の４つのガウス分布が従属平均ベクトル
0006702732.tif 000103
を有するためである。この場合、正則化していない最適化が、加重値が大きい値（たとえば、
0006702732.tif 000104
）になる場合があるが、合計すると１にできる解を提供することができる。このような特異点に対処するために、ＴＤＣモジュール４１２は、最適化の問題を調整することができる。
【０１６８】
プローブ配置モジュール４０８は、様々な用途に使用できる。たとえば、プローブ配置モジュール４０８は、電子デバイスのように、パターンを位置決めし、調査するのに有用とすることができる。また、プローブ配置モジュール４０８は、ロボットの誘導に有用とすることができる。たとえば、ロボットが、細長いバッテリーを拾うように構成される場合、プローブ配置モジュール４０８は、プローブを配置して、細長いバッテリーを示すモデルの正確さを上げるように構成することができる。
【０１６９】
開示の主題は、その用途において、以下の説明で述べた、または図面に示した構成の詳細、および構成要素の配置に限定されないことを理解されたい。開示の主題は、他の実施形態も可能であり、また、様々な方法で実施および実行することができる。また、本明細書で使用されている言い回しおよび用語は、説明を目的とするものであり、限定的に捉えられるべきではないことを理解されたい。
【０１７０】
そのように、当業者には、本開示の元である概念により、開示の主題のいくつかの目的を実行するための他の構造、方法、および装置を設計するための基礎として容易に利用できることを理解されたい。したがって、特許請求の範囲が、開示の主題の趣旨および範囲から逸脱しない限り、そのような同等の構造を含むと解されることが重要である。たとえば、開示の実施形態のいくつかは、１つまたは複数の変形形態に関する。この関係は、数理的方程式を使用して説明され得る。しかし、当業者は、１つまたは複数の変形形態の間の同じ関係を、開示の数理的方程式を変形することにより、異なる数理的方程式を使用して表現することもできる。特許請求の範囲が、１つまたは複数の変形形態の間のそれらの均等の関係も含むと解されることが重要である。
【０１７１】
開示の主題は、上述の例示的な実施形態で記載され、説明されたが、本開示は例としてのみ行われたものであり、開示の主題の実施の詳細の多くの変更を、開示の主題の要旨および範囲を逸脱することなく行うことができることを理解されたい。
【符号の説明】
【０１７２】
１０２  ・・・境界
１０４  ・・・プローブ
１０６  ・・・長縁
１０８  ・・・短縁
４００  ・・・コンピュータデバイス
４０２  ・・・プロセッサ
４０４  ・・・メモリ
４０６  ・・・ＩＰＤモジュール
４０８  ・・・プローブ配置モジュール
４１０  ・・・インターフェイス
４１２  ・・・ＴＤＣモジュール
４１４  ・・・ＦＤＣモジュール
４１６  ・・・ＰＤＭモジュール
６０２  ・・・矢印
６０４  ・・・ヒストグラム
８０２  ・・・矢印
【図１】
0006702732.tif 000105
【図２】
0006702732.tif 000106
【図３】
0006702732.tif 000107
【図４】
0006702732.tif 000108
【図５】
0006702732.tif 000109
【図６Ａ】
0006702732.tif 000110
【図６Ｂ】
0006702732.tif 000111
【図６Ｃ】
0006702732.tif 000112
【図６Ｄ】
0006702732.tif 000113
【図６Ｅ】
0006702732.tif 000114
【図６Ｆ】
0006702732.tif 000115
【図６Ｇ】
0006702732.tif 000116
【図６Ｈ】
0006702732.tif 000117
【図７】
0006702732.tif 000118
【図８】
0006702732.tif 000119
【図９】
0006702732.tif 000120
【図１０】
0006702732.tif 000121
【図１１Ａ】
0006702732.tif 000122
【図１１Ｂ】
0006702732.tif 000123
【図１２Ａ】
0006702732.tif 000124
【図１２Ｂ】
0006702732.tif 000125
【図１３】
0006702732.tif 000126
【図１４Ａ】
0006702732.tif 000127
【図１４Ｂ】
0006702732.tif 000128
【図１５Ａ】
0006702732.tif 000129
【図１５Ｂ】
0006702732.tif 000130
【図１６Ａ】
0006702732.tif 000131
【図１６Ｂ】
0006702732.tif 000132
【図１７Ａ】
0006702732.tif 000133
【図１７Ｂ】
0006702732.tif 000134
【図１７Ｃ】
0006702732.tif 000135
【図１８Ａ】
0006702732.tif 000136
【図１８Ｂ】
0006702732.tif 000137