同一または互いに対応する3次元対象体をそれぞれが表現した、第1点群および第2点群の各点の3次元位置情報を取得する取得手段と、前記取得手段において取得した前記第1点群の分布の方向的な集中度を評価し、当該集中度が最も低い方向に沿うように、基準軸を設定する軸設定手段と、前記取得手段において取得した前記第2点群における各点を注目点として、各前記注目点の3次元位置に対応し、かつ、前記基準軸に沿う特定範囲において、前記第1点群の各点と前記注目点との距離を算出し、当該距離の最も近い前記第1点群の点である最近傍点を探索する最近傍点探索手段とを備えることを特徴とする、最近傍点探索装置。前記軸設定手段が、前記第1点群の分布の分散の値が最も大きい方向に沿うように、前記基準軸を設定することを特徴とする、請求項1に記載の最近傍点探索装置。前記軸設定手段が、前記第1点群の分布の情報エントロピーの値が最も大きい方向に沿うように、前記基準軸を設定することを特徴とする、請求項1に記載の最近傍点探索装置。前記軸設定手段が、前記基準軸を設定する際、前記第1点群の分布中心から所定距離以上離れた点である外れ点を除外して、前記第1点群の分布の方向的な集中度を評価することを特徴とする、請求項1~3のいずれかに記載の最近傍点探索装置。前記基準軸の方向に前記第1点群の各点をソートするソート手段をさらに備え、前記最近傍点探索手段が、前記特定範囲において、前記ソート手段によってソートした順に前記第1点群の各点と前記注目点との距離を算出し、前記最近傍点を探索することを特徴とする、請求項1~4のいずれかに記載の最近傍点探索装置。前記最近傍点探索手段が、前記第1点群の重心と前記第2点群の重心とが一致するように、前記第1点群および前記第2点群のうち少なくとも一方を位置変換させた場合に、前記注目点の3次元位置を基準とした、前記第1点群または前記第2点群の外形サイズを、前記基準軸に沿う前記特定範囲として用いることを特徴とする、請求項1~5のいずれかに記載の最近傍点探索装置。前記最近傍点探索手段が、各前記注目点と各前記最近傍点とが近づくように、前記第1点群および前記第2点群のうち少なくとも一方を位置変換させた場合に、前記注目点の3次元位置を基準とした、各前記注目点と各前記最近傍点との間の、前記位置変換後の距離を、前記基準軸に沿う前記特定範囲として用いることを特徴とする、請求項1~5のいずれかに記載の最近傍点探索装置。前記最近傍点探索手段が、前記最近傍点の探索処理ごとに前記特定範囲を変更可能であることを特徴とする、請求項1~7のいずれかに記載の最近傍点探索装置。前記第1点群および前記第2点群の各点の3次元位置情報が、CADデータで与えられることを特徴とする、請求項1~8のいずれかに記載の最近傍点探索装置。請求項1~9のいずれかに記載の最近傍点探索装置と、前記最近傍点探索手段における前記最近傍点の探索処理の結果に基づいて、各前記注目点と各前記最近傍点とが近づくように、前記第1点群および前記第2点群のうち少なくとも一方を位置変換させる、位置変換手段と、前記位置変換手段における位置変換結果に基づいて、前記第1点群と前記第2点群との相対的な空間位置関係を把握し、前記対象体の3次元位置および姿勢を認識する認識手段とを備えることを特徴とする、3次元位置姿勢認識装置。コンピュータにインストールされて実行されることにより、前記コンピュータを請求項1~9のいずれかに記載の最近傍点探索装置として機能させることを特徴とする、最近傍点探索プログラム。a同一または互いに対応する3次元対象体をそれぞれが表現した、第1点群および第2点群の各点の3次元位置情報を取得する工程と、b取得した前記第1点群の分布の方向的な集中度を評価し、当該集中度が最も低い方向に沿うように、基準軸を設定する工程と、c取得した前記第2点群における各点を注目点として、各前記注目点の3次元位置に対応し、かつ、前記基準軸に沿う特定範囲において、前記第1点群の各点と前記注目点との距離を算出し、当該距離の最も近い前記第1点群の点である最近傍点を探索する工程とを備えることを特徴とする、最近傍点探索方法。前記工程bが、前記第1点群の分布の分散の値が最も大きい方向に沿うように、前記基準軸を設定する工程であることを特徴とする、請求項12に記載の最近傍点探索方法。前記工程bが、前記第1点群の分布の情報エントロピーの値が最も大きい方向に沿うように、前記基準軸を設定する工程であることを特徴とする、請求項12に記載の最近傍点探索方法。前記工程bが、前記基準軸を設定する際、前記第1点群の分布中心から所定距離以上離れた点である外れ点を除外して、前記第1点群の分布の方向的な集中度を評価する工程であることを特徴とする、請求項12~14のいずれかに記載の最近傍点探索方法。d前記工程bの後、前記工程cの前に、前記基準軸の方向に前記第1点群の各点をソートする工程をさらに備え、前記工程cが、前記特定範囲において、前記工程dでソートした順に前記第1点群の各点と前記注目点との距離を算出し、前記最近傍点を探索する工程であることを特徴とする、請求項12~15のいずれかに記載の最近傍点探索方法。前記工程cが、前記特定範囲として、前記第1点群の重心と前記第2点群の重心とが一致するように、前記第1点群および前記第2点群のうち少なくとも一方を位置変換させた場合の、前記注目点の3次元位置を基準とした、前記基準軸に沿う特定距離範囲を用いる工程であることを特徴とする、請求項12~16のいずれかに記載の最近傍点探索方法。前記工程cが、前記特定範囲として、各前記注目点と各前記最近傍点とが近づくように、前記第1点群および前記第2点群のうち少なくとも一方を位置変換させた場合の、前記注目点の3次元位置を基準とした、前記基準軸に沿う特定距離範囲を用いる工程であることを特徴とする、請求項12~16のいずれかに記載の最近傍点探索方法。前記工程cにおいて、前記最近傍点の探索処理ごとに前記特定範囲を変更可能であることを特徴とする、請求項12~18のいずれかに記載の最近傍点探索方法。前記工程aにおいて取得される前記第1点群および前記第2点群の各点の3次元位置情報が、CADデータで与えられることを特徴とする、請求項12~19のいずれかに記載の最近傍点探索方法。請求項12~20のいずれかに記載の最近傍点探索方法の各工程と、e前記工程cにおける前記最近傍点の探索処理の結果に基づいて、各前記注目点と各前記最近傍点とが近づくように、前記第1点群および前記第2点群のうち少なくとも一方を位置変換させる工程と、f前記工程eにおける位置変換結果に基づいて、前記第1点群と前記第2点群との相対的な空間位置関係を把握し、前記対象体の3次元位置および姿勢を認識する工程とを備えることを特徴とする、3次元位置姿勢認識方法。しかし、特許文献1によっても、なお最近傍点探索処理の対象となる点群の数は多く、処理時間の短縮化、すなわち、処理の高速化は十分ではなかった。本発明は、上記のような問題を解決するためになされたものであり、最近傍点探索処理を高速化を実現することができる、最近傍点探索装置およびその方法、プログラム、3次元位置姿勢認識装置およびその方法を提供することを目的とする。請求項1の発明である最近傍点探索装置は、同一または互いに対応する3次元対象体をそれぞれが表現した、第1点群および第2点群の各点の3次元位置情報を取得する取得手段と、前記取得手段において取得した前記第1点群の分布の方向的な集中度を評価し、当該集中度が最も低い方向に沿うように、基準軸を設定する軸設定手段と、前記取得手段において取得した前記第2点群における各点を注目点として、各前記注目点の3次元位置に対応し、かつ、前記基準軸に沿う特定範囲において、前記第1点群の各点と前記注目点との距離を算出し、当該距離の最も近い前記第1点群の点である最近傍点を探索する最近傍点探索手段とを備えることを特徴とする。請求項2の発明は、請求項1に記載の最近傍点探索装置であって、前記軸設定手段が、前記第1点群の分布の分散の値が最も大きい方向に沿うように、前記基準軸を設定することを特徴とする。請求項3の発明は、請求項1に記載の最近傍点探索装置であって、前記軸設定手段が、前記第1点群の分布の情報エントロピーの値が最も大きい方向に沿うように、前記基準軸を設定することを特徴とする。請求項4の発明は、請求項1~3のいずれかに記載の最近傍点探索装置であって、前記軸設定手段が、前記基準軸を設定する際、前記第1点群の分布中心から所定距離以上離れた点である外れ点を除外して、前記第1点群の分布の方向的な集中度を評価することを特徴とする。請求項5の発明は、請求項1~4のいずれかに記載の最近傍点探索装置であって、前記基準軸の方向に前記第1点群の各点をソートするソート手段をさらに備え、前記最近傍点探索手段が、前記特定範囲において、前記ソート手段によってソートした順に前記第1点群の各点と前記注目点との距離を算出し、前記最近傍点を探索することを特徴とする。請求項6の発明は、請求項1~5のいずれかに記載の最近傍点探索装置であって、前記最近傍点探索手段が、前記第1点群の重心と前記第2点群の重心とが一致するように、前記第1点群および前記第2点群のうち少なくとも一方を位置変換させた場合に、前記注目点の3次元位置を基準とした、前記第1点群または前記第2点群の外形サイズを、前記基準軸に沿う前記特定範囲として用いることを特徴とする。請求項7の発明は、請求項1~5のいずれかに記載の最近傍点探索装置であって、前記最近傍点探索手段が、各前記注目点と各前記最近傍点とが近づくように、前記第1点群および前記第2点群のうち少なくとも一方を位置変換させた場合に、前記注目点の3次元位置を基準とした、各前記注目点と各前記最近傍点との間の、前記位置変換後の距離を、前記基準軸に沿う前記特定範囲として用いることを特徴とする。請求項8の発明は、請求項1~7のいずれかに記載の最近傍点探索装置であって、前記最近傍点探索手段が、前記最近傍点の探索処理ごとに前記特定範囲を変更可能であることを特徴とする。請求項9の発明は、請求項1~8のいずれかに記載の最近傍点探索装置であって、前記第1点群および前記第2点群の各点の3次元位置情報が、CADデータで与えられることを特徴とする。また、請求項10の発明は、3次元位置姿勢認識装置であって、請求項1~9のいずれかに記載の最近傍点探索装置と、前記最近傍点探索手段における前記最近傍点の探索処理の結果に基づいて、各前記注目点と各前記最近傍点とが近づくように、前記第1点群および前記第2点群のうち少なくとも一方を位置変換させる、位置変換手段と、前記位置変換手段における位置変換結果に基づいて、前記第1点群と前記第2点群との相対的な空間位置関係を把握し、前記対象体の3次元位置および姿勢を認識する認識手段とを備えることを特徴とする。また、請求項11の発明は、最近傍点探索プログラムであって、コンピュータにインストールされて実行されることにより、前記コンピュータを請求項1~9のいずれかに記載の最近傍点探索装置として機能させることを備えることを特徴とする。また、請求項12の発明は、最近傍点探索方法であって、a同一または互いに対応する3次元対象体をそれぞれが表現した、第1点群および第2点群の各点の3次元位置情報を取得する工程と、b取得した前記第1点群の分布の方向的な集中度を評価し、当該集中度が最も低い方向に沿うように、基準軸を設定する工程と、c取得した前記第2点群における各点を注目点として、各前記注目点の3次元位置に対応し、かつ、前記基準軸に沿う特定範囲において、前記第1点群の各点と前記注目点との距離を算出し、当該距離の最も近い前記第1点群の点である最近傍点を探索する工程とを備えることを特徴とする。請求項13の発明は、請求項12に記載の最近傍点探索方法であって、前記工程bが、前記第1点群の分布の分散の値が最も大きい方向に沿うように、前記基準軸を設定する工程であることを特徴とする。請求項14の発明は、請求項12に記載の最近傍点探索方法であって、前記工程bが、前記第1点群の分布の情報エントロピーの値が最も大きい方向に沿うように、前記基準軸を設定する工程であることを特徴とする。請求項15の発明は、請求項12~14のいずれかに記載の最近傍点探索方法であって、前記工程bが、前記基準軸を設定する際、前記第1点群の分布中心から所定距離以上離れた点である外れ点を除外して、前記第1点群の分布の方向的な集中度を評価する工程であることを特徴とする。請求項16の発明は、請求項12~15のいずれかに記載の最近傍点探索方法であって、d前記工程bの後、前記工程cの前に、前記基準軸の方向に前記第1点群の各点をソートする工程をさらに備え、前記工程cが、前記特定範囲において、前記工程dでソートした順に前記第1点群の各点と前記注目点との距離を算出し、前記最近傍点を探索する工程であることを特徴とする。請求項17の発明は、請求項12~16のいずれかに記載の最近傍点探索方法であって、前記工程cが、前記特定範囲として、前記第1点群の重心と前記第2点群の重心とが一致するように、前記第1点群および前記第2点群のうち少なくとも一方を位置変換させた場合の、前記注目点の3次元位置を基準とした、前記基準軸に沿う特定距離範囲を用いる工程であることを特徴とする。請求項18の発明は、請求項12~16のいずれかに記載の最近傍点探索方法であって、前記工程cが、前記特定範囲として、各前記注目点と各前記最近傍点とが近づくように、前記第1点群および前記第2点群のうち少なくとも一方を位置変換させた場合の、前記注目点の3次元位置を基準とした、前記基準軸に沿う特定距離範囲を用いる工程であることを特徴とする。請求項19の発明は、請求項12~18のいずれかに記載の最近傍点探索方法であって、前記工程cにおいて、前記最近傍点の探索処理ごとに前記特定範囲を変更可能であることを特徴とする。請求項20の発明は、請求項12~19のいずれかに記載の最近傍点探索方法であって、前記工程aにおいて取得される前記第1点群および前記第2点群の各点の3次元位置情報が、CADデータで与えられることを特徴とする。また、請求項21の発明は、3次元位置姿勢認識方法であって、請求項12~20のいずれかに記載の最近傍点探索方法の各工程と、e前記工程cにおける前記最近傍点の探索処理の結果に基づいて、各前記注目点と各前記最近傍点とが近づくように、前記第1点群および前記第2点群のうち少なくとも一方を位置変換させる工程と、f前記工程eにおける位置変換結果に基づいて、前記第1点群と前記第2点群との相対的な空間位置関係を把握し、前記対象体の3次元位置および姿勢を認識する工程とを備えることを特徴とする。請求項1~21の発明によれば、第1点群の分布の方向的な集中度を評価し、当該集中度が最も低い方向に沿うように、基準軸を設定すること、また、各注目点の3次元位置に対応し、かつ、基準軸に沿う特定範囲において、最近傍点を探索することにより、点群の分布の方向的な集中度を考慮した最近傍点の探索領域の限定をすることができるので、探索が必要な領域に存在する点の数を効果的に減らすことができる。よって、最近傍点探索処理の際に、探索の対象となる点が減り、最近傍点探索処理の高速化を実現することができる。特に請求項4の発明によれば、軸設定手段が、基準軸を設定する際、外れ点を除外して第1点群の分布の方向的な集中度を評価することにより、外れ点が存在するために、分布の方向的な集中度を適切に評価できない場合であっても、分布の方向的な集中度を適切に評価できる。まず、本発明の前提技術として、対象体の3次元位置および姿勢を認識するためのICPマッチングを行う場合に、特に、最近傍点探索処理をモデル点群の特定領域においてのみ行う方法について、以下説明する。ICPマッチングのために用いる計測点群の生成等の動作を行う3次元位置姿勢認識装置として、例えば図1に示すようなロボットに備えられたコンピュータを想定する。図1に示すロボットは、対象体3物品などを異なる方向から撮影する複数の撮影手段であるカメラ4およびカメラ5と、カメラ4およびカメラ5を例えば先端ハンド部7付近に取り付けたアーム6と、アーム6を支える胴体部8とを備える。コンピュータ10は、ロボットと有線図1のDL2または無線で通信可能であって、カメラ4およびカメラ5の撮影結果に基づいて、対象体3の3次元位置および姿勢を認識する機能を有する。コンピュータ10には、演算処理手段や制御手段としてのMPUのほか、記憶デバイスやディスプレイやマウス等のマンマシンインターフェイスを備えられる。そして、このコンピュータにおいて3次元位置姿勢認識装置としての機能を実現させるプログラムが、あらかじめインストールされている。図2においては、3次元位置姿勢認識装置の機能を概念的に示す。図2に示すように3次元位置姿勢認識装置は、対象体3を撮像するカメラ5およびカメラ5と、カメラ4およびカメラ5の撮影結果に基づいて、対象体3の計測点群の各点の3次元位置情報を生成する生成手段11と、対象体3の3次元モデル上に規定されたモデル点群の各点の3次元位置情報を記憶する記憶手段12と、計測点群およびモデル点群の各点の3次元位置情報を取得する取得手段13と、取得手段13からの出力をもとにICPアルゴリズムを実行するマッチング手段14と、マッチング手段14における結果に基づいて、対象体3の3次元位置および姿勢を認識する認識手段15とを備える。生成手段11において、対象体3の計測点群は、カメラ4およびカメラ5で撮影された対象体3のステレオ画像から抽出された、対象体3の形状を規定する特徴的な点の集合であって、各点がその3次元位置座標によって表現されている。記憶手段12は、対象体3の3次元モデル上に規定されたモデル点群の各点の3次元位置情報を記憶する。3次元モデルとしては、対象体3が工業製品の場合にはそのCADデータなどを利用可能である。取得手段13は、生成手段11から対象体3の計測点群の各点の3次元位置情報を取り込んで取得するとともに、モデル点群の各点の3次元位置情報を記憶手段12から読出して取得する。さらに図3において、マッチング手段14の機能を詳細に示す。図3に示すように、マッチング手段14は、ソート軸基準軸を設定する軸設定手段20と、点群における各点に対してソートするソート手段21と、最近傍点を探索する最近傍点探索手段22と、点群の位置変換を行う位置変換手段23とを備える。軸設定手段20は、後述するように、最近傍点を探索される点群が定義された座標系において、ソート軸基準軸を設定する。ここでソート軸とは、点群の各点に順序づけるための基準となる軸であり、ソート軸の単純増加または単純減少の方向に沿って、点群の各点は順序づけられるソートされる。ソート手段21は、軸設定手段20において設定されたソート軸に沿って、実際に点群の各点を順序づける機能を有する。最近傍点探索手段22は、一方の点群における特定の点上記の注目点に相当から、他方の点群における各点上記の対応点に相当までの距離を順次計算し、当該距離が最も近い点である最近傍点を探索する機能を有する。位置変換手段23は、一方の点群における各点注目点と、その各点について探索された各最近傍点とを近づけるように、少なくとも一方の点群を位置変換させる機能を有する。当該機能によって、双方の点群がマッチングする。3次元位置姿勢認識装置は、ICPマッチングを行うための最近傍点探索装置としての機能も包含している。すなわち、計測点群およびモデル点群の各点の3次元位置情報を取得する取得手段13と、ソート軸基準軸を設定する軸設定手段20と、点群における各点に対してソートするソート手段21と、最近傍点を探索する最近傍点探索手段22とを備える、最近傍点探索装置が包含されているということができる。次に、図4に示すフローチャートを用いて、3次元位置および姿勢認識処理の流れを説明する。まず、3次元位置および姿勢を認識したい対象体3たとえば物品を異なる方向からカメラ等カメラ4およびカメラ5で撮影し、その画像を取得するステップS1。対象体3が複数ある場合には、その画像中から目標とする対象体3の部分を切り出して用いることも可能である。次に、生成手段11において、それらの画像に対しステレオ処理、すなわち2つのカメラ4およびカメラ5からの視差に基づく三角測量の原理によって、各カメラから対象体3上の各点の3次元的な相対位置の特定を行うことにより、計測点群に相当する各点の3次元位置情報を生成するステップS2。次に、取得手段13において、計測した計測点群と、記憶手段12にあらかじめ記憶されている、対象体3に対応するモデル点群とを、それぞれ取得するステップS3。次に、マッチング手段14において、計測点群とモデル点群とをICPマッチングさせるステップS4。詳細な内容については、図5を参照して後述する。次に認識手段15において、ICPマッチング処理における点群の位置変換の変換値から、計測点群とモデル点群との相対的な空間位置関係を把握し、対象体3の3次元位置および姿勢を認識するステップS5。次に、マッチング手段14における動作図4のステップS4について、図5を参照しつつ説明する。以下では、計測点群における特定の点を注目点とし、モデル点群における対応点最近傍点を探索する場合の、ICPマッチング処理について説明する。まず、軸設定手段20において、最近傍点を探索されるモデル点群が定義された座標系において、ソート軸を設定する。ソート軸の設定は、モデル点群が定義された座標系のX軸方向、Y軸方向、Z軸方向のうち、モデル点群の各点が存在する範囲、すなわち、点群の分布幅が最も広い座標軸座標値の最大値から最小値を減じた値が最大となる座標軸に沿うようになされるステップS40。例えば、モデル点群が、X軸方向に長く広がる分布を示している場合には、X軸がソート軸となる。次に、ソート手段21において、モデル点群の各点に対し、ソート軸に沿った順序づけソートを行うステップS41。次に最近傍点探索手段22において、計測点群における注目点に対応する、モデル点群における最近傍点を探索するステップS42。最近傍点探索処理は、モデル点群における各点について、ソート手段21においてソートした順に行われる。このとき、モデル点群の探索領域は、以下のように限定することができる。すなわち、ソート軸上において、注目点の3次元位置を基準とする特定距離範囲を指定し、当該範囲に区切られる領域のみを探索領域とすることができる。特定距離範囲は、探索処理ごとに変更することも可能である。特定距離範囲は、例えば、最近傍点探索処理の前に、計測点群の重心とモデル点群の重心とを一致させる処理粗位置合わせ処理を行う場合には、計測点群またはモデル点群の外形サイズ全周サイズに基づいて、例えばその一定割合分の長さに設定することができる。また、既に最近傍点探索処理がなされ、点群の位置変換処理が行われている場合図6参照には、前回、ある注目点A0の最近傍点として探索されたモデル点群の点B1を記憶しておき、位置変換処理を行うことによって3次元位置が移動した注目点A1からモデル点群の前回の最近傍点B1までの距離L1を、特定距離範囲として用いることができる。図6は、X軸がソート軸として設定されている場合であり、注目点A1を中心として、X軸の正方向および負方向に距離L1の、特定距離範囲が設けられている。図6においては、モデル点群の点B1、点B2、点B3、点B4については探索されるが、点B5および点B6については、特定距離範囲による探索領域から外れているため探索対象とされない。このように設定すれば、前回探索された最近傍点は確実に探索領域に含まれ、位置変換処理によって移動した3次元位置における最近傍点が異なっていればより近傍の点が存在すれば、最近傍点を効率的に更新することができる。図6においては、注目点A1から点B3までの距離L3が、注目点A1から点B1までの距離L1より短いため、最近傍点は点B3に更新される。次に位置変換手段23において、計測点における各注目点と、それらに対応するモデル点群における各最近傍点とが近づくように、計測点群およびモデル点群のうち少なくとも一方を位置変換するステップS43。以上のように、ソート軸上の特定範囲に区切られる領域に最近傍点探索処理の探索領域を限定することにより、各注目点の最近傍点探索の処理時間を短くし、ICPマッチング処理、さらには対象体の3次元位置および姿勢認識処理の高速化を実現することができる。しかし上記のような場合でも、ソート軸基準軸をどのように設定するかによって、十分に処理の高速化が実現できない場合がある。例えば図7に示すような、他の点群の分布とは一定距離離れた3次元位置に外れ点X0があるような分布の点群がある場合、上記の例のように、点群の分布幅が最も広い軸に沿うようにソート軸を設定すると、ソート軸はX軸に沿うものとなる。なお、外れ点外れ値、アウトライヤーは、計測によるノイズである場合だけでなく、適切な測定点である場合もある。ソート軸をX軸に沿うように設定し、注目点を中心としてソート軸上の特定範囲L1を区切り、その探索領域での最近傍点探索処理を行った場合、例えば図8に示すような領域を探索することとなり、探索領域内に多くの点が含まれてしまう図8においては、7点。一方で、例えばソート軸をY軸に沿うように設定し、注目点を中心としてソート軸上の特定範囲L1を区切り、その探索領域での最近傍点探索処理を行った場合、例えば図9に示すような領域を探索することとなり、探索領域内に含まれる点の数は、図8に示す場合より少なくなる図9においては、4点。探索領域に含まれる点の数が少ないほど最近傍点探索処理にかかる時間は短くなるから、ソート軸上の同じ特定範囲L1に区切られる探索領域内の最近傍点探索を行う場合でも、ソート軸の設定によって、高速化の度合いが異なることが分かる。また、例えば図10に示すような、X軸およびY軸に沿わない方向図10においては、図面上の右斜め方向に広がりを持つ分布の点群がある場合、上記の例のように、点群の分布幅が最も広い軸に沿うようにソート軸を設定すると、例えば、ソート軸はX軸に沿うものとなる。ソート軸をX軸に沿うように設定し、注目点を中心としてソート軸上の特定範囲L1を区切り、その探索領域での最近傍点探索処理を行った場合、例えば図11に示すような領域を探索することとなり、探索領域内に多くの点が含まれてしまう図11においては、6点。一方で、ソート軸を、例えば図12に示すX’軸に沿うように設定し、注目点を中心としてソート軸上の特定範囲L1を区切り、その探索領域での最近傍点探索処理を行った場合、図12に示すような領域を探索することとなり、探索領域内に含まれる点の数は、図11に示す場合より少なくなる図12においては、3点。よってこの場合にも、ソート軸上の同じ特定範囲L1に区切られる探索領域内の最近傍点探索を行う場合でも、ソート軸の設定によって、高速化の度合いが異なることが分かる。以下に示す実施形態では、上記のような問題を踏まえ、ソート軸の選定を適切に行うことによって、高速化を実現する最近傍点探索装置を示す。<実施形態><構成>ICPマッチングのために用いる計測点群の生成等の動作を行う3次元位置姿勢認識装置として、例えば図1に示すようなロボットに備えられたコンピュータを想定する。各構成についての説明については、上述した内容と同様であるので、詳細な説明を省略する。図13においては、3次元位置姿勢認識装置の機能を概念的に示す。図13に示すように3次元位置姿勢認識装置は、対象体3を撮像するカメラ5およびカメラ5と、カメラ4およびカメラ5の撮影結果に基づいて、対象体3の計測点群第2点群の各点の3次元位置情報を生成する生成手段11と、対象体3の3次元モデル上に規定されたモデル点群第1点群の各点の3次元位置情報を記憶する記憶手段12と、計測点群第2点群およびモデル点群第1点群の各点の3次元位置情報を取得する取得手段13と、取得手段13からの出力をもとにICPアルゴリズムを実行するマッチング手段40と、マッチング手段40における結果に基づいて、対象体3の3次元位置および姿勢を認識する認識手段15とを備える。マッチング手段40以外の機能部の説明については、上述した内容と同様であるので、詳細な説明を省略する。さらに図14において、マッチング手段40の機能を詳細に示す。図14に示すように、マッチング手段40は、ソート軸基準軸を設定する軸設定手段41と、点群における各点に対してソートするソート手段21と、最近傍点を探索する最近傍点探索手段22と、少なくとも一方の点群の位置変換を行う位置変換手段23とを備える。軸設定手段41以外の機能部の説明については、上述した内容と同様であるので、詳細な説明を省略する。軸設定手段41は、点群の分布を解析し、分布の方向的な集中度一様性の低い方向に沿うように、ソート軸基準軸を設定する。詳細は、後述する。<動作>次に、マッチング手段40における動作図4のステップS4に対応について、図15を参照しつつ説明する。以下では、計測点群における特定の点を注目点とし、モデル点群における対応点最近傍点を探索する場合の、ICPマッチング処理について説明する。まず、軸設定手段41において、最近傍点を探索されるモデル点群が定義された座標系において、ソート軸を設定する。ソート軸の設定に際して、まず、外れ点図7等に示すX0の探索を行うステップS50。ここで外れ点とは、ノイズおよび測定点のいずれであるかは問わないが、点群の分布中心重心からの距離が所定距離以上である点である。所定距離としては、例えば、3次元位置および姿勢を認識する対象体の外形サイズ等を用いることができる。外れ点X0がある場合には、当該点を軸設定の際の考慮する点群から除外する。なお、外れ点X0がないことがあらかじめ分かっているような場合、例えば、モデル点群を参照することによりそれが分かる場合には、当該動作は省略されてもよい。次に、外れ点X0を除外した点群において、モデル点群の分布する3次元座標系全方向の、分布の方向的な集中度を評価するステップS51。ここで点群の分布の方向的な集中度とは、その方向に点群の分布位置がばらつく程度を示す指標であり、分布の方向的な集中度が高いとは、点群の分布位置がばらつかないことであり、分布の方向的な集中度が低いとは、点群の分布位置がばらついていることである。分布の方向的な集中度の評価には、例えば、その方向成分の分散や情報エントロピーを用いることができる。そして、分布の方向的な集中度の最も低い方向、すなわち、分散の最も大きい方向、情報エントロピーの最も大きい方向に沿うように、ソート軸基準軸を設定するステップS52。以下、分散を用いた場合を例として説明する。モデル点群の分布の分散u2は、例えば以下に示す式1で表される。ここで、xiはn個それぞれの点における軸方向成分を示し、xの相加平均とxiとの差の2乗の総和が分散値として計算される。分散を求める際には、分散を求める軸上に各点の成分を射影し、それぞれの点の軸上の成分によるヒストグラムを生成する図16参照。ヒストグラムを生成する際のビン幅については、固定幅を設定してもよいし、点群存在幅を基準として所定数分割した幅を設定してもよい。式1に示す分散の値が最大となる方向成分を求め、その方向に沿うようにソート軸を設定する。ここで、分散の値が最大となる方向成分を求めることは主成分分析PrincipalComponentAnalysis:PCAに対応し、ソート軸として設定する方向は、主成分分析における第1主成分の方向に対応する。主成分分析の第1主成分の方向は、分散が最大となるため、第1主成分と直交する第2主成分の方向には、分散が最小となる。よって、第1主成分方向の軸上で特定範囲に区切った領域領域Aに含まれる点群と、他の方向、例えば第2主成分方向の軸上で特定範囲に区切った領域領域Bに含まれる点群とを比較した場合、領域Aでは、特定範囲および第2主成分方向の分布広がりにより形成される、点群の分布広がりとなるのに対し、領域Bでは、特定範囲および第1主成分方向の分布広がりにより形成される、点群の分布広がりとなる。よって、領域Aにおける点群の分布広がりの方が狭くなり、領域Aに含まれる点の数も少なくなる。すなわち、当該領域において最近傍点探索処理を行うことによって、探索が必要となる点数は減り、処理の高速化が可能となる。なお、第1主成分の方向は、点群の分布に対して3次元的に一意に決定することが可能であるが、本発明におけるソート軸としては、第1主成分を平行に移動した軸第1主成分と直交する方向に平行移動した軸であってもよい。次に、ソート手段21において、モデル点群の各点に対し、ソート軸に沿った順序づけソートを行うステップS41。なお、外れ点として除外されている点を、ソートの対象に含めてもよい。次に最近傍点探索手段22において、計測点群における注目点に対応する、モデル点群における最近傍点を探索するステップS42。最近傍点探索処理は、モデル点群における各点について、ソート手段21においてソートした順に行われる。ただし、ソートした順でない順序で、各点についての最近傍点探索処理が行われてもよく、その場合、ソート手段21が備えられなくてもよい。このとき、モデル点群の探索領域は、ソート軸上において、注目点の3次元位置を基準とする特定距離範囲を指定し、当該範囲に区切られる領域のみを探索領域とすることができる。特定距離範囲の設定方法については、上述したとおりである。次に位置変換手段23において、計測点における各注目点と、それらに対応するモデル点群における各最近傍点とが近づくように、計測点群およびモデル点群のうち少なくとも一方を位置変換するステップS43。以上のように、適切に設定したソート軸上の特定範囲に区切られる領域に、最近傍点探索処理の探索領域を限定することにより、各注目点の最近傍点探索の処理時間を短くし、ICPマッチング処理、さらには対象体の3次元位置および姿勢認識処理の高速化を実現することができる。特に、ソート軸を点群の分布の方向的な集中度が低い方向に沿って設定したため、より効率的に、最近傍点探索処理の探索領域を限定することができる。例えば図17に示すような、他の点群の分布とは一定距離離れた3次元位置に外れ点X0があるような分布の点群がある場合、まず、外れ点を探索することによって、軸設定の際に考慮する点群から外れ点X0を除外することができる。次に、外れ点X0を除く点群の分布を解析し、分布の方向的な集中度の低い方向に沿うようにソート軸を設定すると、ソート軸SはY軸に沿うものとなる。ソート軸S上において、注目点を中心とする特定範囲L1を区切り、その探索領域での最近傍点探索処理を行った場合、例えば図17に示すような領域を探索することとなり、探索領域内に含まれる点は少なくなる図17においては、4点。また、例えば図18に示すような、X軸およびY軸に沿わない方向図18においては、図面上の右斜め方向に広がりを持つ分布の点群がある場合、まず、外れ点X0を探索する。図18の場合には外れ点X0に該当する点は存在しないので、分布する全ての点を、軸設定の際に考慮する点群とする。次に、点群の分布を解析し、分布の方向的な集中度の低い方向に沿うようにソート軸を設定すると、ソート軸Sは図18に示すように、図面上の右斜め方向に沿うものとなる。ソート軸S上において、注目点を中心とする特定範囲L1を区切り、その探索領域での最近傍点探索処理を行った場合、例えば図18に示すような領域を探索することとなり、探索領域内に含まれる点は少なくなる図18においては、3点。よってどちらの場合であっても、最近傍点探索処理を行う探索領域を適切に限定し、より効率よく最近傍点探索処理を行うことができる。<変形例>上記の実施形態においては、計測点群における各注目点の、モデル点群における最近傍点を探索する最近傍点探索処理について記載したが、計測点群同士、あるいはモデル点群同士での最近傍点探索処理に適用してもよいし、モデル点群における各注目点の、計測点群における最近傍点を探索する最近傍点探索処理に適用してもよい。また、実施形態に示す最近傍点探索処理は、ICPマッチングを行うための前処理として行われているが、他の用途のために行われる場合であってもよい。また、実施形態の図7~12、図16~18においては、説明を簡略化させるために2次元座標系を用いているが、もちろん、3次元座標系に拡張して適用することができる。<効果>本発明にかかる実施形態によれば、モデル点群第1点群の分布の方向的な集中度分散や情報エントロピーを評価し、当該集中度が最も低い方向に沿うように、ソート軸基準軸を設定する軸設定手段41と、計測点群第2点群における各点を注目点として、各注目点の3次元位置に対応し、かつ、基準軸に沿う特定範囲L1において、モデル点群第1点群の各点と注目点との距離を算出し、モデル点群第1点群の最近傍点を探索する最近傍点探索手段22とを備えることで、点群の分布の方向的な集中度を考慮した最近傍点の探索領域の限定をすることができるので、探索が必要な領域に存在する点の数を効果的に減らすことができる。よって、最近傍点探索処理の際に、探索の対象となる点が減り、最近傍点探索処理の高速化を実現することができる。また、点群の分布が外れ点X0を含んでいる場合図17参照や、点群の分布が規定された軸X軸、Y軸、Z軸に沿わない広がりを持っている場合図18参照等、点群の分布幅に基づくソート軸の設定では探索処理の高速化が実現できない場合であっても、適切にソート軸基準軸を設定し、効率のよい最近傍点探索処理を行うことができる。また、本発明にかかる実施形態によれば、軸設定手段41が、ソート軸基準軸を設定する際、モデル点群第1点群の分布中心から離れた外れ点X0を除外して、モデル点群第1点群の分布の方向的な集中度を評価することで、外れ点X0が存在するために、分布の方向的な集中度を適切に評価できない場合であっても、外れ点X0を探索し、その外れ点X0を分布の方向的な集中度の判断には含めないことにより、分布の方向的な集中度を適切に評価できる。また、本発明にかかる実施形態によれば、モデル点群第1点群の重心と計測点群第2点群の重心とが一致させた後、最近傍点探索手段22が、注目点の3次元位置を基準として、モデル点群第1点群または計測点群第2点群の外形サイズの例えば一定割合分の長さを、ソート軸基準軸に沿う特定距離範囲として設定することで、点群同士の重心を一致させた状態での、注目点の周辺領域を効果的に探索することができ、最近傍点探索の効率を高めることができる。また、本発明にかかる実施形態によれば、各注目点と各最近傍点とが近づけた後、最近傍点探索手段22が、注目点の3次元位置を基準とした、各注目点と各最近傍点との間の、位置変換後の距離を、ソート軸基準軸に沿う特定距離範囲として設定することで、位置変換させる前に最近傍点とされた対応点と、注目点との間の、位置変換後の距離を基準に特定距離範囲を設定でき、前回探索された最近傍点を確実に探索領域に含みつつ、位置変換後の最近傍点を効率的に探索することができる。また、本発明にかかる実施形態によれば、最近傍点探索手段22が、最近傍点の探索処理ごとに特定範囲を変更可能であることで、それぞれの最近傍点探索処理において、適切な探索領域を設定することができ、処理の高速化が可能となる。また、本発明にかかる実施形態によれば、最近傍点探索処理の結果に基づいて、各注目点と各最近傍点とが近づくように、点群を位置変換させる位置変換手段23と、位置変換結果に基づいて、モデル点群第1点群と計測点群第2点群との相対的な空間位置関係を把握し、対象体3の3次元位置および姿勢を認識する認識手段15とを備えることで、最近傍点探索処理を高速化し、さらに、3次元位置および姿勢認識の高速化も実現できる。なお本発明は、その発明の範囲内において、本実施形態における任意の構成要素の変形もしくは省略が可能である。