"対象物上の各点の三次元座標を設計数値的にそれぞれ表現した第1モデル点群データと、当該対象物上の各点の3次元座標を実測に基づいてそれぞれ表現した第1測定点群データとを取得する取得部と、前記第1モデル点群データを予め設定された基準座標軸の座標値順にソートすることにより第2モデル点群データを取得するとともに、前記第1測定点群データを当該基準座標軸の座標値順にソートすることにより第2測定点群データを取得するソート部と、前記第2モデル点群データと前記第2測定点群データとのうち一方の基準点群データと他方の参照点群データとについて、前記基準点群データが表現する第1点群において予め設定された基準点に対する距離が最短となる最近傍点を、前記参照点群データが表現する第2点群において探索する探索処理を行なう探索部と、前記第1点群の各点を前記基準点としてそれぞれ設定する基準点設定部と、を備え、前記探索部が、前記基準点に対する前記基準座標軸方向の距離が予め設定された基準距離よりも短い注目点を前記第2点群において選択する選択処理を行なう選択部と、前記基準点と前記注目点との点間距離が前記基準距離よりも短い場合には、当該点間距離を前記基準距離として設定することにより前記基準距離を更新する更新処理を行なう更新部と、前記第2点群において前記注目点として新たに選択可能な未選択点が無くなるまで、前記更新処理によって更新された前記基準距離が前記選択処理に反映されつつ前記選択処理と前記更新処理とがそれぞれ逐次実行されるように、前記選択部と前記更新部とを制御する探索制御部と、前記選択処理と前記更新処理との逐次実行処理が終了されたときの前記基準距離の設定に用いられた前記注目点を前記最近傍点として決定する決定部と、を備えたことを特徴とする画像処理装置。請求項1に記載された画像処理装置であって、前記基準点設定部が、前記基準座標軸方向についての前記第1点群の並び順に前記基準点を逐次設定し、前記探索部が、逐次設定された前記基準点に関する前記探索処理のそれぞれにおいて、当該基準点と、当該基準点の直前に設定された基準点に対して探索された最近傍点との距離を前記基準距離の初期値として設定しつつ、前記探索処理を逐次行うことを特徴とする画像処理装置。請求項1または請求項2に記載された画像処理装置であって、座標空間の各座標軸のうち前記参照点群データの派生元の点群データにおける座標値の分布幅が最も広い座標軸を前記基準座標軸として設定する座標軸設定部、をさらに備えることを特徴とする画像処理装置。請求項1から請求項3の何れか1つの請求項に記載された画像処理装置であって、前記対象物の三次元形状を測定可能な測定部、をさらに備え、前記取得部が、前記測定部が前記対象物を測定して取得した測定情報に基づいて、前記第1測定点群データを取得することを特徴とする画像処理装置。画像処理装置に搭載されたコンピュータにおいて実行されることにより当該画像処理装置を請求項1から請求項4の何れか1つの請求項に記載の画像処理装置として機能させることを特徴とするプログラム。対象物上の各点の三次元座標を設計数値的にそれぞれ表現した第1モデル点群データと、当該対象物上の各点の3次元座標を実測に基づいてそれぞれ表現した第1測定点群データとを取得する取得工程と、前記第1モデル点群データを予め設定された基準座標軸の座標値順にソートすることにより第2モデル点群データを取得するとともに、前記第1測定点群データを当該基準座標軸の座標値順にソートすることにより第2測定点群データを取得するソート工程と、前記第2モデル点群データと前記第2測定点群データとのうち一方の基準点群データと他方の参照点群データとについて、前記基準点群データが表現する第1点群において予め設定された基準点に対する距離が最短となる最近傍点を、前記参照点群データが表現する第2点群において探索する探索処理を行なう探索工程と、前記第1点群の各点を前記基準点としてそれぞれ設定する基準点設定工程と、を有し、前記探索工程が、前記基準点に対する前記基準座標軸方向の距離が予め設定された基準距離よりも短い注目点を前記第2点群において選択する選択処理を行なう選択工程と、前記基準点と前記注目点との点間距離が前記基準距離よりも短い場合には、当該点間距離を前記基準距離として設定することにより前記基準距離を更新する更新処理を行なう更新工程と、前記第2点群において前記注目点として新たに選択可能な未選択点が無くなるまで、前記更新処理によって更新された前記基準距離が前記選択処理に反映されつつ前記選択処理と前記更新処理とがそれぞれ逐次実行されるように、前記選択部と前記更新部とを制御する探索制御工程と、前記選択処理と前記更新処理との逐次実行処理が終了されたときの前記基準距離の設定に用いられた前記注目点を前記最近傍点として決定する決定工程と、を有することを特徴とする画像処理方法。しかしながら、木構造を用いた最近傍探索によっても、処理時間の短縮が十分ではないといった問題がある。本発明は、こうした問題を解決するためになされたもので、最近傍探索を高速化できる技術を提供することを目的とする。上記の課題を解決するために、第1の態様に係る画像処理装置は、対象物上の各点の三次元座標を設計数値的にそれぞれ表現した第1モデル点群データと、当該対象物上の各点の3次元座標を実測に基づいてそれぞれ表現した第1測定点群データとを取得する取得部と、前記第1モデル点群データを予め設定された基準座標軸の座標値順にソートすることにより第2モデル点群データを取得するとともに、前記第1測定点群データを当該基準座標軸の座標値順にソートすることにより第2測定点群データを取得するソート部と、前記第2モデル点群データと前記第2測定点群データとのうち一方の基準点群データと他方の参照点群データとについて、前記基準点群データが表現する第1点群において予め設定された基準点に対する距離が最短となる最近傍点を、前記参照点群データが表現する第2点群において探索する探索処理を行なう探索部と、前記第1点群の各点を前記基準点としてそれぞれ設定する基準点設定部とを備え、前記探索部が、前記基準点に対する前記基準座標軸方向の距離が予め設定された基準距離よりも短い注目点を前記第2点群において選択する選択処理を行なう選択部と、前記基準点と前記注目点との点間距離が前記基準距離よりも短い場合には、当該点間距離を前記基準距離として設定することにより前記基準距離を更新する更新処理を行なう更新部と、前記第2点群において前記注目点として新たに選択可能な未選択点が無くなるまで、前記更新処理によって更新された前記基準距離が前記選択処理に反映されつつ前記選択処理と前記更新処理とがそれぞれ逐次実行されるように、前記選択部と前記更新部とを制御する探索制御部と、前記選択処理と前記更新処理との逐次実行処理が終了されたときの前記基準距離の設定に用いられた前記注目点を前記最近傍点として決定する決定部とを備えたことを特徴とする。第2の態様に係る画像処理装置は、第1の態様に係る画像処理装置であって、前記基準点設定部が、前記基準座標軸方向についての前記第1点群の並び順に前記基準点を逐次設定し、前記探索部が、逐次設定された前記基準点に関する前記探索処理のそれぞれにおいて、当該基準点と、当該基準点の直前に設定された基準点に対して探索された最近傍点との距離を前記基準距離の初期値として設定しつつ、前記探索処理を逐次行うことを特徴とする。第3の態様に係る画像処理装置は、第1または第2の態様に係る画像処理装置であって、座標空間の各座標軸のうち前記参照点群データの派生元の点群データにおける座標値の分布幅が最も広い座標軸を前記基準座標軸として設定する座標軸設定部をさらに備えることを特徴とする。第4の態様に係る画像処理装置は、第1から第3の何れか1つの態様に係る画像処理装置であって、前記対象物の三次元形状を測定可能な測定部をさらに備え、前記取得部が、前記測定部が前記対象物を測定して取得した測定情報に基づいて、前記第1測定点群データを取得することを特徴とする。第5の態様にかかるプログラムは、画像処理装置に搭載されたコンピュータにおいて実行されることにより当該画像処理装置を第1から第4の何れか1つの態様に係る画像処理装置として機能させることを特徴とする。第6の態様に係る画像処理方法は、対象物上の各点の三次元座標を設計数値的にそれぞれ表現した第1モデル点群データと、当該対象物上の各点の3次元座標を実測に基づいてそれぞれ表現した第1測定点群データとを取得する取得工程と、前記第1モデル点群データを予め設定された基準座標軸の座標値順にソートすることにより第2モデル点群データを取得するとともに、前記第1測定点群データを当該基準座標軸の座標値順にソートすることにより第2測定点群データを取得するソート工程と、前記第2モデル点群データと前記第2測定点群データとのうち一方の基準点群データと他方の参照点群データとについて、前記基準点群データが表現する第1点群において予め設定された基準点に対する距離が最短となる最近傍点を、前記参照点群データが表現する第2点群において探索する探索処理を行なう探索工程と、前記第1点群の各点を前記基準点としてそれぞれ設定する基準点設定工程とを有し、前記探索工程が、前記基準点に対する前記基準座標軸方向の距離が予め設定された基準距離よりも短い注目点を前記第2点群において選択する選択処理を行なう選択工程と、前記基準点と前記注目点との点間距離が前記基準距離よりも短い場合には、当該点間距離を前記基準距離として設定することにより前記基準距離を更新する更新処理を行なう更新工程と、前記第2点群において前記注目点として新たに選択可能な未選択点が無くなるまで、前記更新処理によって更新された前記基準距離が前記選択処理に反映されつつ前記選択処理と前記更新処理とがそれぞれ逐次実行されるように、前記選択部と前記更新部とを制御する探索制御工程と、前記選択処理と前記更新処理との逐次実行処理が終了されたときの前記基準距離の設定に用いられた前記注目点を前記最近傍点として決定する決定工程とを有することを特徴とする。第1から第6の何れの形態に係る発明によっても、第1モデル点群データと第1測定点群データとが基準座標軸の座標値順にそれぞれソートされた各点群データに係る第1点群と第2点群とにおいて、第1点群の基準点に対する基準座標軸方向の距離が基準距離よりも短い注目点が第2点群から選択される。また、基準点と注目点との点間距離が基準距離よりも短い場合には、当該点間距離によって基準距離が設定され更新される。そして、更新された基準距離が、選択点の選択処理に反映されつつ、該選択処理と、基準距離の更新処理とが逐次実行され、これらの処理が終了されたときの基準距離の設定に用いられた注目点が最近傍点として決定される。従って、探索が進むにつれて、基準軸方向の探索範囲が狭められつつ最近傍点の探索が行なわれるので、最近傍探索が高速化され得る。以下、本発明の一実施形態を図面に基づいて説明する。図面では同様な構成および機能を有する部分に同じ符号が付され、下記説明では重複説明が省略される。また、各図面は模式的に示されたものであり、例えば、各図面における画像上の表示物のサイズおよび位置関係等は正確に図示されたものではない。また、画像データと、該画像データに基づいて表示される画像とをまとめて画像と適宜総称する。また、ユークリッド距離は、単に距離とも称される。なお、図4~図7には、直交するXYZの3軸が付されている。<実施形態について><1画像処理システム100Aの構成について>図1は、実施形態に係る画像処理装置200Aを用いた画像処理システム100Aの外観構成を例示する図である。図1に示されるように、画像処理システム100Aは、画像処理装置200Aとロボット300Aとを主に備えて構成されている。画像処理装置200Aは、画像処理部200とステレオカメラ400とを主に備えて構成され、ステレオカメラ400は、左カメラ61と右カメラ62とを主に備えて構成されている。左カメラ61と右カメラ62とは所定の基線長を隔てて設けられており、それぞれのカメラの焦点距離などのカメラパラメータは既知である。ステレオカメラ400は、着脱機構などにより柱状物などに着脱自在に構成されており、図1の例では、ロボット装置300Aの腕部64の両端部のうち、手部65側の端部に取付けられている。ステレオカメラ400の制御は、画像処理部200が通信回線DL1を介して供給する制御信号によって行なわれる。画像処理装置200Aは、ステレオカメラ400が対象物を撮像した左画像1図2および右画像2図2を画像処理部200で処理することによって、原測定点群データ4図2を取得する。原測定点群データ4は、ステレオカメラ400を基準とするカメラ座標系における対象物上の各点の三次元座標が、実測に基づいて表現された点群データである。ここで、後述するロボット装置300Aは、ロボット装置300Aの本体部63を基準とした所定のロボット座標系において、ロボット装置300Aの各部の動作を制御可能に構成されている。従って、画像処理システム100Aにおいては、腕部64に取付けられたステレオカメラ400の、ロボット座標系における位置姿勢も取得可能である。従って、ステレオカメラ400によって測定された原測定点群データ4は、カメラ座標系からロボット座標系に座標変換され得る。ロボット装置300Aの近傍に設置された作業台66には、既知の三次元形状を有する複数の対象物71が載置されている。ロボット装置300Aに対する作業台66の位置姿勢は既知である。画像処理部200の記憶部52図2には、対象物71が作業台66上の所定の基準位置に、所定の基準姿勢で載置されたときの該対象物71についての原モデル点群データ3図2が、予め記憶されている。原モデル点群データ3としては、例えば、対象物71の各点の三次元座標がロボット座標系において表現されたCADデータ等が、採用される。なお、原モデル点群データ3が、例えば、ステレオカメラ400に比べて、測定精度が十分に高い三次元測定機を用いて測定された対象物71の三次元形状データに基づいて生成された点群データなどであったとしても良い。すなわち、原モデル点群データ3は、対象物71上の各点の三次元座標が、設計数値的に表現された点群データである。ロボット装置300Aは、本体部63、所定の回転軸周りに回転可能に構成された回転部68、回転部68に取付けられ、関節部を有して屈伸可能な腕部64、および腕部64の先端に取り付けられた手部65を主に備えて構成される。ロボット装置300Aの制御は、画像処理部200が通信回線DL2を介して供給する制御信号によって行なわれる。なお、通信回線DL1、DL2は、有線の回線であっても、無線通信による回線であっても良い。本体部63は、画像処理部200からの制御に基づいて、回転部68による所定の回転軸周りの回転動作と、関節部での腕部64の屈伸動作とを制御するとともに、手部65による対象物の把持解放動作を制御する。なお、ロボット装置300Aは、作業台66上の所定の基準位置に所定の基準姿勢で載置された対象物71、および該対象物71に対する位置姿勢が既知の対象物71を把持して、不図示の他の作業台等へ載置するパレタイジング動作などを実行可能に構成されている。従って、作業台66に載置された対象物71の実際の位置姿勢が不明であったとしても、基準の位置姿勢に対する該対象物71の実際の位置姿勢を求めることができれば、ロボット装置300Aは、該対象物71のパレタイジング動作を行い得る。そこで、画像処理システム100Aは、画像処理装置200Aが、作業台66における位置姿勢が不明な対象物71についての原測定点群データ4を取得し、原測定点群データ4を用いて基準の位置姿勢に対する該対象物71の実際の位置姿勢を求める。図12は、実施形態に係る画像処理装置200Aが、基準の位置姿勢に対する該対象物71の位置姿勢を求める動作フローS100の一例を示す図である。動作フローS100に示される動作において、原測定点群データ4図2は、先ず、記憶部52から原モデル点群データ3を取得する図12のステップS110。次に、画像処理装置200Aは、ステレオカメラ400によって対象物71を測定し、原測定点群データ4を取得する図12のステップS120。原測定点群データ4は、具体的には、三次元化部31図2が、入出力部51を介して取得した左画像1、右画像2を処理することによって取得される。三次元化部31は、左画像1と右画像2との間で対応点探索処理を行なって両画像間で互いに対応した対応点を取得し、取得した対応点に対応した対象物71の点の三次元座標を三角測量の原理を用いて求めることなどによって原測定点群データ4を取得する。取得された原測定点群データ4は、カメラ座標系で表現されており、取得部32図2に供給される。取得部32は、原測定点群データ4の原モデル点群データ3への相対的な粗位置合わせを行い、第1モデル点群データ5図2と第1測定点群データ6図2とを取得する図12のステップS130。具体的には、取得部32は、先ず、ロボット座標系におけるステレオカメラ400の位置姿勢に基づいて、原測定点群データ4をカメラ座標系からロボット座標系に座標変換する。次に、取得部32は、互いにロボット座標系で表現された原モデル点群データ3と原測定点群データ4とのそれぞれの重心を算出し、算出された2つの重心が一致するように、原測定点群データ4を原モデル点群データ3に相対的に移動させることにより該粗位置合わせを行なう。該粗位置合わせが施された原モデル点群データ3が第1モデル点群データ5であり、該粗位置合わせが施された原測定点群データ4が第1測定点群データ6である。なお、三次元化部31は、予め、生成された第1モデル点群データ5と第1測定点群データ6とを例えば、入出力部51を介して取得することなどによっても第1モデル点群データ5と第1測定点群データ6とを取得することもできる。第1モデル点群データ5と第1測定点群データ6とが取得されると、画像処理部200のCPU43A図2は、ICP法を用いた原測定点群データ4の原モデル点群データ3への配置合わせ位置姿勢合わせを行なう図12のステップS140。ICP法を用いた配置合わせの詳細については後述する。該配置合わせが完了すると、CPU43Aは、原測定点群データ4を原モデル点群データ3に配置合わせする座標変換情報を取得する図12のステップS150。具体的には、CPU43Aは、原測定点群データ4の原モデル点群データ3への相対的な粗位置合わせの変換と、ICP法を用いた配置合わせの変換とを総合することにより該座標変換情報を取得する。該座標変換情報が取得されると、CPU43Aは、該座標変換情報を表現したアフィン変換の回転行列と平行移動行列とに基づいて、作業台66における所定の基準位置および基準姿勢に対する対象物71の実際の位置姿勢情報20図2を取得する図12のステップS160。取得された位置姿勢情報20は、記憶部52に記憶される。ロボット装置300Aは、位置姿勢情報20に基づいて対象物71のパレタイジング動作を行なう。なお、画像処理システム100Aのうち画像処理装置200Aのみを用いることによって、例えば、対象物71の実際の形状と、設計された形状との差異を検出する形状検査が行なわれ得る。原測定点群データ4の原モデル点群データ3への相対的な配置合わせを行なうことができれば、配置合わせ後における原モデル点群データ3と原測定点群データ4との差に基づいて、対象物71の形状検査が可能となる。従って、形状検査用の原モデル点群データ3として、作業台66上の基準位置に基準姿勢で載置された対象物71のロボット座標系で表現された設計数値的な点群データが使用される必要は無い。形状検査用の原モデル点群データ3としては、任意の三次元座標系の任意の位置に、任意の姿勢で配置された、対象物71についての設計数値的な点群データが使用可能である。また、パレタイジング動作用および形状検査用の何れにおいても、ステレオカメラ400などの三次元測定機によって、先ず、対象物71のポリゴンデータ等が取得され、該ポリゴンデータが原測定点群データ4に変換されて使用されたとしても本発明の有用性を損なうものではない。また、パレタイジング動作用および形状検査用の何れにおいても、対象物71の三次元形状が、例えば、ベジェ曲線などによって表現された形状データが記憶部52に予め記憶されていたとしても良い。この場合には、画像処理部200において、該形状データから原モデル点群データ3が生成されて使用される。<2画像処理装置200Aの構成について>図2は、実施形態に係る画像処理装置200Aの主な機能構成を例示するブロック図である。既述したように画像処理装置200Aは、画像処理部200とステレオカメラ400とを主に備えて構成される。また、画像処理部200は、例えば、入出力部51、記憶部52、およびCPU43Aを主に備えて構成される。◎入出力部51について:入出力部51は、例えばUSBインタフェース、またはBluetooth登録商標インタフェースなどの入出力インタフェース、マルチメディアドライブ、およびネットワークアダプタなどのLANやインターネットに接続するためのインタフェースなどを備えて構成され、CPU43Aとの間でデータの授受を行うものである。具体的には、入出力部51は、例えば、CPU43Aがステレオカメラ400を制御するための各種の制御信号を、通信回線DL1を介してステレオカメラ400へと供給する。また、入出力部51は、ステレオカメラ400が撮影した左画像1および右画像2を画像処理部200に供給する。また、入出力部51は、例えば、予め生成された原モデル点群データ3および原測定点群データ4が記憶された光ディスクなどの記憶媒体を受け付けることなどによって、原モデル点群データ3および原測定点群データ4を画像処理部200に供給することもできる。◎記憶部52について:記憶部52は、例えば、それぞれ不図示のROMReadOnlyMemory、RAMRandomAccessMemory、およびフラッシュメモリなどの読み書き自在な不揮発性メモリによって構成される。不揮発性メモリに代えて、ハードディスク装置などが採用されても良い。該ROMは、読出し専用メモリであり、CPU43Aを動作させるプログラムPG1などを格納している。該RAMは、読み書き自在の揮発性メモリであり、画像処理装置200Aが取得、または処理した各種画像などを一時的に記憶する画像格納部として機能する。また、該RAMは、CPU43Aの処理情報を一時的に記憶するワークメモリなどとしても機能する。なお、後述するCPU43Aにおける各要素の間での情報の授受は、該RAMを介して行なわれる。該不揮発性メモリは、画像処理部200の各種制御パラメータや各種動作モードなどの情報を恒久的に記録する。原モデル点群データ3も予め該不揮発性メモリに記憶されている。◎CPU43Aについて:CPUCentralProcessingUnit43Aは、画像処理装置200Aの各機能部を統轄制御する制御処理装置であり、記憶部52に格納されたプログラムPG1などに従った制御および処理を実行する。CPU43Aは、三次元化部31、取得部32、座標軸設定部33、ソート部34、基準点設定部35、選択部36、初期化部37、更新部38、探索制御部39、決定部40、および配置合わせ部41などの各要素としても動作する。CPU43Aは、これらの各要素などとして動作することによって、左画像1および右画像2をそれぞれ処理して対象物71についての位置姿勢情報20図2を取得する。また、CPU43A、入出力部51、記憶部52等のそれぞれは、電気的に接続されている。したがって、CPU43Aは、例えば、入出力部51を介したステレオカメラ400、ロボット装置300Aの制御およびステレオカメラ400からの画像情報の取得等を所定のタイミングで実行できる。なお、図2に示される構成例では、三次元化部31~配置合わせ部41などの各要素は、CPU43Aで所定のプログラムPG1を実行することによって実現されているが、これらの各要素はそれぞれ、例えば、専用のハードウェア装置などによって実現されてもよい。○三次元化部31:三次元化部31は、左画像1と右画像2との間で対応点探索処理を行なって両画像間で互いに対応した対応点を取得し、取得した対応点に対応した対象物71の点の三次元座標を三角測量の原理を用いて求めることなどによって原測定点群データ4を取得する。原測定点群データ4の取得においては、予め記憶部52に記憶されているステレオカメラ400についての各種のカメラパラメータおよび基線長情報などが用いられる。取得された原測定点群データ4は、所定のカメラ座標系で表現されており、取得部32図2に供給される。○取得部32:取得部32は、原測定点群データ4を、記憶部52から読出した原モデル点群データ3に相対的に粗位置合わせを行うことにより、第1モデル点群データ5図2と第1測定点群データ6図2とを取得する。第1モデル点群データ5は、対象物71上の各点の三次元座標を設計数値的にそれぞれ表現した点群データであり、第1測定点群データ6は、対象物71上の各点の3次元座標を実測に基づいてそれぞれ表現した第1測定点群データである。取得部32は、第1モデル点群データ5を基準点群データ10図2の派生元の点群データとしてソート部34に供給するとともに、第1測定点群データ6を参照点群データ11図2の派生元の点群データとして座標軸設定部33およびソート部34に供給する。なお、基準点群データ10が表現する第1点群において最近傍探索の基準となる基準点が設定され、参照点群データ11が表現する第2点群において最近傍点の候補点である注目点が設定される。なお、第1測定点群データ6が基準点群データ10の派生元の点群データとしてソート部34に供給されるとともに、第1モデル点群データ5が参照点群データ11の派生元の点群データとして座標軸設定部33およびソート部34に供給されたとしても本発明の有用性を損なうものではない。すなわち、画像処理部200においては、第1モデル点群データ5と第1測定点群データ6とのうち一方の点群データが基準点群データ10の派生元の点群データとしてソート部34に供給される。また、他方の点群データが参照点群データ11の派生元の点群データとして座標軸設定部33およびソート部34に供給される。なお、第1モデル点群データ5と第1測定点群データ6との何れの点群データが基準点群データ10の派生元の点群データであるかを規定した情報は、例えば、予め記憶部52に記憶されており、取得部32その他の各部によって取得されて用いられる。○座標軸設定部33:座標軸設定部33は、座標空間の各座標軸のうち参照点群データ11の派生元の点群データにおける座標値の分布幅が最も広い座標軸を基準座標軸として設定し、該基準座標軸についての基準座標軸情報9図2をソート部34に供給する。なお、図2に例示された構成においては、座標軸設定部33は、第1測定点群データ6に基づいて基準座標軸を設定している。○ソート部34:ソート部34は、第1モデル点群データ5を基準座標軸の座標値順にソートすることにより第2モデル点群データ7を取得するとともに、第1測定点群データ6を基準座標軸の座標値順にソートすることにより第2測定点群データ8を取得する。なお、該ソート処理は、例えば、メモリ空間における各データの記憶アドレスがソート順に従って変更されることにより、あるいは記憶アドレスは変更されずにソート順を示す新たな情報が各データに付加されることなどにより実現される。ソート部34は、予め記憶部52に記憶された設定情報に基づいて、第2モデル点群データ7と第2測定点群データ8との何れか一方の点群データを基準点群データ10として基準点設定部35および配置合わせ部41に供給する。また、ソート部34は、他方の点群データを参照点群データ11として選択部36および配置合わせ部41に供給する。図2に例示された構成においては、第2モデル点群データ7が基準点群データ10として採用され、第2測定点群データ8が参照点群データ11として採用されている。○基準点設定部35:基準点設定部35は、基準点群データ10が表現する第1点群の各点を基準点としてそれぞれ設定する。画像処理部200においては、該基準点に対する距離が最短となる最近傍点が、参照点群データ11が表現する第2点群において探索される。なお、基準点設定部35が、例えば、基準座標軸方向についての該第1点群の並び順に基準点を逐次設定したとしても本発明の有用性を損なうものではない。基準点設定部35は、設定した基準点を規定した基準点情報12を選択部36、初期化部37および配置合わせ部41へと供給する。○探索部42:探索部42は、基準点群データ10が表現する第1点群において設定された基準点に対する距離が最短となる最近傍点を、参照点群データ11が表現する第2点群において探索する探索処理を行なう。探索部42は、また、選択部36、初期化部37、更新部38、探索制御部39、および決定部40としても動作する。○選択部36:選択部36は、それぞれ選択された基準点について、該基準点に対する基準座標軸方向の距離が予め設定された基準距離よりも短い注目点を第2点群において選択する選択処理を行なう。選択部36は、選択した注目点を規定する注目点情報13を更新部38に供給する。また、選択部36は、選択した注目点が、最近傍探索の開始当初における最初の注目点である場合には、該最初の注目点を規定した注目点情報13を初期化部37に対しても供給する。図5は、実施形態に係る画像処理装置200A画像処理部200が行なう最近傍探索において注目点の選択が可能な領域R1を例示する図である。黒塗りの四角形で示された点は、基準点設定部35によって設定された1つの基準点A3である。黒塗りの円でそれぞれ示された各点は、参照点群データ11によって表現された第2点群である。なお、図5においてはX軸が基準座標軸である。枠S1は、XY空間における該第2点群の分布空間の外縁を示している。また、領域R2は、枠S1に内包された領域である。斜線が付された領域R1は、注目点の選択が可能な領域であり、基準点A3を空間的な基準点として基準距離に基づいて設定されている。いわゆる総当たり探索線形探索においては、領域R2が注目点の選択可能な範囲、すなわち基準点A3に対する最近傍点の探索範囲となる。対して、画像処理装置200Aにおいては、領域R2よりも狭い探索範囲R1が注目点の選択が可能な範囲となる。従って、画像処理装置200Aによれば、線形探索に比べて最近傍点の探索処理に要する処理時間を短縮できる。さらに、後述するように、画像処理装置200Aにおいては、最近傍点の探索最近傍探索が進むにつれて領域R1の基準座標軸方向に沿った幅が狭くなりつつ最近傍探索が行なわれる。従って、線形探索が行なわれる場合に比べて最近傍点の探索処理に要する処理時間がさらに短縮され得る。○初期化部37:初期化部37は、それぞれ供給された基準点情報12と、最初の注目点を規定した注目点情報13とに基づいて、基準点と最初の注目点との距離を、基準距離16の初期値として設定する。設定された基準距離16は、選択部36および更新部38に供給される。○更新部38:更新部38は、基準点と注目点との点間距離が基準距離16よりも短い場合には、当該点間距離を基準距離16として設定することにより基準距離16を更新する更新処理を行なう。更新部38は、更新された基準距離16を選択部36に供給するとともに、基準距離16と、該基準距離16の設定に用いられた注目点を規定した注目点情報13とを対応づけて決定部40に供給する。また、更新部38は、基準距離16の初期値についても、該基準距離16と、該基準距離16の設定に用いられた最初の注目点を規定した注目点情報13とを対応づけて決定部40へと供給する。○探索制御部39:探索制御部39は、第2点群において注目点として新たに選択可能な未選択点が無くなるまで、更新処理によって更新された基準距離16が注目点の選択処理に反映されつつ、選択処理と更新処理とがそれぞれ逐次実行されるように、選択部36と更新部38とを制御する。○決定部40:決定部40は、第2点群において注目点として新たに選択可能な未選択点が無くなったことにより、注目点の選択処理と基準距離の更新処理との逐次実行処理が終了されたことを探索制御部39からの信号に基づいて検知する。そして、決定部40は、該選択処理と該更新処理との逐次実行処理が終了されたときの基準距離16の設定に用いられた注目点を最近傍点として決定する。決定部40は、最近傍点を規定した最近傍点情報17を選択部36および配置合わせ部41に供給する。なお、基準点設定部35が基準座標軸方向についての第1点群の並び順に基準点を逐次設定する動作を行なう場合には、探索制御部39は、逐次設定される基準点に対して最近傍探索を逐次行なう。また、この場合、最近傍点情報17を供給された選択部36は、探索された最近傍点を、次に設定される基準点に対する探索処理における最初の注目点として設定する。該最初の注目点に関する注目点情報13は、初期化部37へと供給され、初期化部37において、基準距離16の初期値の設定に用いられる。○配置合わせ部41:配置合わせ部41は、基準点設定部35によってそれぞれ設定された基準点のそれぞれについて、最近傍点が探索されると、各基準点と各最近傍点との対応する組み合わせ間での距離の和が最小値となる座標変換を、例えば、最小二乗法などによって求める。該座標変換は、参照点群データ11を基準点群データ10に相対的に配置合わせする座標変換情報である。配置合わせ部41は、該座標変換を用いて参照点群データ11を座標変換することによって参照点群データ11の基準点群データ10への配置合わせを行なう。該配置合わせが完了すると、配置合わせ部41は、各基準点と各最近傍点との対応する組み合わせ間での距離の和が所定の閾値以下である否かを判定する。該判定の結果、該距離の和が閾値より大きければ、配置合わせ部41は、基準点群データ10および参照点群データ11に基づいて、第1モデル点群データ5および第1測定点群データ6を更新し、取得部32に供給する。そして、該第1モデル点群データ5および該第1測定点群データ6についての上述した配置合わせ処理が再び行なわれる。すなわちICP法による配置合わせが行なわれる。該判定の結果、該距離の和が閾値以下であれば、配置合わせ部41は、原測定点群データ4を原モデル点群データ3に配置合わせする座標変換情報を取得する。該座標変換情報は、原測定点群データ4の原モデル点群データ3への相対的な粗位置合わせの変換と、ICP法を用いた各配置合わせの変換とを総合することによって求められる。該座標変換情報が取得されると、配置合わせ部41は、該座標変換情報を表現したアフィン変換の回転行列と平行移動行列とに基づいて、作業台66における所定の基準位置および基準姿勢に対する対象物71の実際の位置姿勢情報20図2を取得する。取得された位置姿勢情報20は、記憶部52に供給され、記憶部52に記憶される。<3画像処理装置200Aが行なう配置合わせ動作について>図13、図14は、図12のステップS140におけるICP法を用いた配置合わせの処理に係る画像処理装置200Aより詳細には、画像処理部200の動作フローの一例を示す図である。次に、画像処理装置200Aの画像処理部200が行なうICP法を用いた配置合わせの動作について、図13、図14を参照しつつ詳しく説明する。図12のステップS140の処理が開始されると、処理は、図13のステップS210に移され、座標軸設定部33が、既述した処理手法によってソート処理用の基準座標軸を設定するステップS210。図6および図7は、基準座標軸の設定例について説明するための図である。なお、ここでは、第1モデル点群データ5が基準点群データ10の派生元の点群データであり、第1測定点群データ6が参照点群データ11の派生元の点群データであるとして説明が行なわれる。測定点群BG2図6と測定点群BG3図7とは、それぞれ、第1測定点群データ6が表現した測定点群の一例である。測定点群BG2においては、X、Y、Zの各軸方向の座標値の分布幅のうちX軸方向に沿った分布幅が最大となっている。すなわち、各座標軸方向に沿った測定点群の分布密度のうちX軸方向に沿った分布密度が最小となっている。従って、測定点群BG2については、X軸が基準座標軸として選択された場合に、注目点の選択が可能な領域R1図5に内包された点の数が最小となる。また、測定点群BG3においては、Y軸方向に沿った座標値の分布幅が最大となっている。すなわち、各座標軸方向に沿った測定点群の分布密度のうちY軸方向に沿った分布密度が最小となっている。従って、測定点群BG3については、Y軸が基準座標軸として選択された場合に、領域R1に内包された点の数が最小となる。上述したように、座標値の最大値から最小値を減じた値が最大となる座標軸がソート対象の基準座標軸として選択されれば、点間距離の計算対象となる注目点の点数が最も少なくなり得る。従って、最近傍探索の処理時間の更なる短縮が可能となる。なお、何れの座標軸が基準座標軸として選択されたとしても、本発明の有用性を損なうものではない。図13のステップS210において基準座標軸が設定されると、ソート部34は、第1モデル点群データ5を基準座標軸の座標値順にソートすることにより第2モデル点群データ7を取得するとともに、第1測定点群データ6を基準座標軸の座標値順にソートすることにより第2測定点群データ8を取得する図13のステップS220。なお、第1モデル点群データ5と第1測定点群データ6との点数は、例えば、ほぼ同じ点数でも、異なった点数であってもよい。次に、基準点設定部35は、第2モデル点群データ7基準点群データ10が表現する第1点群において基準点を設定する図13ステップS230。基準点が設定されると、探索部42によって基準点に対する最近傍点を探索する最近傍探索処理が行なわれる図13のステップS240。図15、図16は、図13のステップS240における最近傍探索処理に係る画像処理装置200Aより詳細には、画像処理部200の動作フローの一例を示す図である。最近傍探索処理が開始されると、選択部36は、第2測定点群データ8参照点群データ11が表現する第2点群において昇順探索前方探索用の最初の注目点を選択する図15のステップS310。最初の注目点が選択されると、初期化部37は、基準点と該注目点との点間距離を、基準距離16の初期値として設定する図15のステップS320。次に、更新部38は、該点間距離が基準距離16未満であるか否かを判定する図15のステップS330。ステップS330での判定の結果、該点間距離が基準距離16未満であれば、更新部38は、該点間距離を基準距離16として設定することにより基準距離16を更新し図15のステップS340、処理はステップS350に移される。また、ステップS330での判定の結果、該点間距離が基準距離16以上であれば、処理は、ステップS350に移される。なお、ステップS330での判定においては、基準点と注目点との各座標値の差についての二乗和に基づいて比較することにより、該二乗和の平方根を求める場合に比べて処理時間を短縮されている。また、座標の二乗和を求める前に、基準点と注目点とのYZ座標の差の絶対値と、基準距離16とを比較し、YZ座標の差の絶対値が、基準距離16よりも大きければ、座標の二乗和を計算することなく、処理はステップS350に移される。従って処理時間はさらに短縮され得る。また、後述するステップS380図16においても、ステップS330と同様に処理が行なわれる。図15のステップS350において、選択部36は、第2点群において基準座標軸の座標値の昇順で注目点の1つ隣の点と、基準点との基準軸方向の距離が基準距離16未満であるか否かを判定する。ステップS350での判定の結果、基準点との基準軸方向の距離が基準距離16未満であれば、選択部36は、該隣の点を新たな注目点として選択し図15のステップS360、探索制御部39は、処理をステップS320に戻す。ステップS350での判定の結果、基準点との基準軸方向の距離が基準距離16以上であれば、探索制御部39は、昇順方向の注目点の選択最近傍点の探索において、注目点として選択可能な未選択点が無くなったと判定し、処理を図16のステップS370に移す。図4は、画像処理装置200A画像処理部200が行なう、上述した最近傍探索前方探索を説明するための図である。図4に示された基準点A1は、最近傍点の探索と処理が行なわれている基準点であり、基準点A0は、基準点A1の直前に、最近傍点が探索された基準点である。基準点A0と基準点A1とは、基準座標軸であるX軸の座標値順に、ソートされたときに隣り合う点である。第2点群における点B1~B6は、基準軸方向の座標値が、基準点A1についての該座標値に近い注目点の例であり、それぞれ、基準点A1に対する注目点として順次設定される。特に点B1は、基準点A0に対して探索された最近傍点でもある。また、点B1~B6のそれぞれのX座標は、昇順に増加している。基準点A1と点B1、B2、B3、およびB4のそれぞれとの距離ユークリッド距離は、それぞれ距離点間距離L1、L2、L3、およびL4である。座標X1は、基準点A1のX座標である。座標X2は、座標X1からX方向昇順方向、前方に、距離L3離れた座標であり、座標X3は、座標X1からX方向に、距離L1離れた座標である。基準点A1に対する最初の注目点としては、点B1が選択される。該選択は、第1点群と第2点群とは、それぞれソート済みであるので、基準点A0の最近傍点と、基準点A1の最近傍点との位置は近いと推定されることに基づいている。そして、基準距離16としては、距離L1が採用される。距離L1の基準距離16としての採用により、点B1の次の注目点としては、座標X1~座標X3の範囲のX座標を有する点B2~B4がX座標の昇順に選択可能となる。そして、点B2が該次の注目点として、先ず選択される。ここで、距離L2の値は、距離L1の値よりも大きい。従って、距離L2は、基準距離16として設定されることなく、点B3が点B2の次の注目点として選択される。また、距離L3の値は、距離L1の値よりも小さいため、距離L3が基準距離16として設定されて、基準距離16が更新される。基準距離16の該更新により、座標X1~座標X2の範囲のX座標を有する点が、次の注目点として選択され得る。このように、探索が進むにつれて、注目点の選択範囲、すなわち最近傍点の探索範囲は狭められていく。なお、点B4および点B4よりもX座標が大きい点B5以降の各点は、基準点A1に対するユークリッド距離を実際に計算されるまでもなく注目点としての選択対象から除外される。そして、昇順方向の近傍点探索は終了される。後方探索降順探索についても、昇順探索と同様にして行なわれる。なお、注目点の逐次の選択処理として、例えば、基準点に対して、昇順方向と降順方向の両方向において、基準点に対する各測定点の基準座標軸方向の距離絶対値に基づいて、該距離の昇順で注目点が選択される手法が採用され得る。該手法が採用されたとしても探索が進むにつれて、注目点の選択範囲、すなわち最近傍点の探索範囲は狭められていく。従って、該手法が、上述した前方探索および後方探索による注目点の選択手法に代えて選択されたとしても、本発明の有用性を損なうものではない。また、基準点A1に対する最初の注目点として、前回の探索に係る最近傍点、すなわち、基準点A0に対する最近傍点が採用されない場合には、選択部36は、例えば、基準点A1に対する基準座標軸方向の距離が最短となる測定点などを最初の注目点として選択する。前回の探索に係る最近傍点が最初の注目点として採用されない場合には、各基準点についての対応点探索処理の並列化が可能となるので、該並列化処理によって探索処理の更なる高速化がなされ得る。従って、最初の注目点として、前回の探索に係る最近傍点が採用されないとしても、本発明の有用性を損なうものではない。ステップS370において、選択部36は、第2測定点群データ8参照点群データ11が表現する第2点群において降順探索後方探索用の最初の注目点を選択する。該最初の注目点が選択されると、更新部38は、基準点と該注目点との点間距離が基準距離16未満であるか否かを判定する図16のステップS380。ステップS380での判定の結果、該点間距離が基準距離16未満であれば、更新部38は、該点間距離を基準距離16として設定することにより基準距離16を更新し図16のステップS390、処理はステップS400に移される。また、ステップS380での判定の結果、該点間距離が基準距離16以上であれば、処理は、ステップS400に移される。図16のステップS400において、選択部36は、第2点群において基準座標軸の座標値の昇順で注目点の1つ隣の点と、基準点との基準軸方向の距離が基準距離16未満であるか否かを判定する。ステップS400での判定の結果、基準点との基準軸方向の距離が基準距離16未満であれば、選択部36は、該隣の点を新たな注目点として選択し図16のステップS410、探索制御部39は、処理をステップS380に戻す。ステップS400での判定の結果、基準点との基準軸方向の距離が基準距離16以上であれば、探索制御部39は、降順方向の注目点の選択最近傍点の探索において、注目点として選択可能な未選択点が無くなったと判定し、処理を図16のステップS420に移す。ステップS420において、決定部40は、基準距離16の設定に用いられた注目点を最近傍点として決定し、処理は、図13のステップS250へと移される。図13のステップS250において、基準点設定部35は、全ての基準点について最近傍探索処理が終了したか否か、すなわち、第1点群における全ての点が基準点として設定されたか否かを判定する。ステップS250での判定の結果、全ての基準点について最近傍探索処理が終了していなければ、処理は、図13のステップS230へと戻される。また、該判定の結果、全ての基準点について最近傍探索処理が終了していれば、処理は、図14のステップS260へと移される。ステップS260において、配置合わせ部41は、設定された各基準点と、各基準点にそれぞれ探索された各最近傍点とについて、各基準点と各最近傍点との対応する組み合わせ間での距離の和が最小値となる座標変換を、例えば、最小二乗法などによって求める。該座標変換は、参照点群データ11を基準点群データ10に相対的に配置合わせする座標変換情報であるステップS260。該座標変換情報が求められると、配置合わせ部41は、該座標変換情報を用いて参照点群データ11を座標変換することによって参照点群データ11の基準点群データ10への配置合わせを行なう図14のステップS270。該配置合わせが完了すると、配置合わせ部41は、各基準点と各最近傍点との対応する組み合わせ間での距離の和が所定の閾値以下である否かを判定する図14のステップS280。ステップS280での判定の結果、該距離の和が閾値より大きければ、配置合わせ部41は、基準点群データ10および参照点群データ11に基づいて、第1モデル点群データ5および第1測定点群データ6を更新する図14のステップS290。そして、処理は、図13のステップS210へと戻される。そして、該第1モデル点群データ5および該第1測定点群データ6についての上述した配置合わせ処理が再び行なわれる。なお、ステップS220図13におけるソート処理の手法として、ステップS220の処理が初めて行なわれる場合には、例えば、一般的に使用される最も高速なソート法の一つであるクイックソート法などが使用される。一方、ステップS220の処理が1回以上行なわれている状態で、ステップS220が行なわれる場合には、ステップS270図14での配置合わせ処理によって、先のステップS220でのソート結果にずれが生ずる。しかし、該ずれが、極端に大きなずれとなることは、通常、起こりえず、該配置合わせ処理によっても、先のステップS220でのソート結果は、ある程度維持されていると推定される。ステップS220の処理が1回以上行なわれている状態で、ステップS220が行なわれる場合には、ステップS220でのソート法としては、例えば、公知のマージソート法などが採用される。従って、2回目移行のソート処理では、クイックソート法が用いられる場合に比べて、ソート処理の高速化が可能となる。ステップS280での判定の結果、該距離の和が閾値以下であれば、ICP法を用いた配置合わせ処理は終了される。そして、処理は、図12のステップS150へと移され、既述したステップS150~S160の処理が行なわれて対象物71についての位置姿勢情報20が取得される。次に、画像処理装置200Aによる最近傍探索の処理と、従来手法による最近傍探索の処理との比較結果について説明する。図8は、ランダムに発生させた点群データを対象として、各種法により行なわれた最近傍探索の処理時間を例示するグラフを示す図である。図8のグラフの横軸は、点群データの個数であり、100点から10,000点の点群データが使用されている。図8のグラフの縦軸は、最近傍点の探索に要した処理時間が表示されている。該処理時間は、図13のステップS230~ステップS250の反復動作部分の処理に関する処理時間であり、後述する図9においても同様である。図8の凡例に示されたLinearは、一般的な線形探索手法を示し、また、Flannは、一般的なNNS最近傍探索手法の一種であるKdTree法を実現するオープンソースによる探索処理を示す。また、Sweepは、画像処理装置200A画像処理部200が行なう対応点探索処理であり、該処理は、図15、図16に示された動作フローに従って実現されている。なお、後述する図9の凡例についても、図8の凡例と共通の凡例が用いられている。図8に示されるように、ランダムに発生させた点群データを対象とした場合には、線形探索手法では、点数の二乗に比例して探索時間が増加しているが、Sweep法では、点数の二乗に比例して探索時間が増加する様なことはなく、他の手法に比べて、処理時間を最も短く抑えることができている。また、点数が10,000点の場合では、Sweep法では、KdTree法の約3倍の高速化が達成できている。図9は、4種類の部品A~Dを対象として、各種法により行なわれた最近傍探索の処理時間を例示するグラフを示す図である。なお、図9のグラフにおいては、処理時間は棒グラフで示されている。また、図9のグラフにおいては、各部品についての測定点群数とモデル点群数とがそれぞれ折れ線で表示されている。また、部品A、Bは、平面部が多い単純形状の部品であり、部品B、Cは、平面部の他に曲面部を有する部品である。なお、部品Bには、くぼみ部分が設けられている。図9に示されるように、ランダムに発生させた点群データを処理対象としない場合でも、本願手法Sweep法は、他の手法に比べて、処理時間をより抑制できている。なお、Sweep法の処理時間は、対象物の形状の差異にはあまり依存せず、主として、処理対象データの点数に依存している。図10、図11は、実施形態に係る最近傍探索Sweep法における点間距離の計算回数を例示するグラフを示す図である。より詳細には、図10、図11には、図8に示された、ランダムに生成された10,000点の点群に対するSweep法における最近傍探索の処理内容が解析されて、基準点と注目点との点間距離の計算回数がヒストグラムとして示されている。図10の横軸は、昇順探索前方探索における図15のステップS330において、実際に該点間距離が計算された回数である。また、図11の横軸は、降順探索後方探索における図16のステップS380において、実際に該点間距離が計算された回数である。該点間距離の計算には、膨大な時間を要するため、該点間距離の計算回数が少なければ少ないほど、処理時間は短縮される。図10の破線E1に内包された部分に示されるように、Sweep法の前法探索においては、基準点と注目点との点間距離の計算回数のほとんどは、10回以内に収まっている。また、図11の破線E2に内包された部分に示されるように、Sweep法の後方探索においては、該点間距離の計算回数のほとんどは、3回以内に収まっている。一方、同一データに対して線形探索法が適用された場合には、該点間距離の計算回数は、10,000回となる。従って、該点間距離の計算回数の比較によっても、Sweep法が線形探索法に比べて、著しく高速化されていることが裏付けられている。上述したように、画像処理装置200A画像処理部200によれば、第1モデル点群データ5と第1測定点群データ6とが基準座標軸の座標値順にそれぞれソートされた各点群データに係る第1点群と第2点群とにおいて、第1点群の基準点に対する基準座標軸方向の距離が基準距離16よりも短い注目点が第2点群から選択される。また、基準点と注目点との点間距離が基準距離16よりも短い場合には、当該点間距離によって基準距離16が設定され更新される。そして、更新された基準距離16が、選択点の選択処理に反映されつつ、該選択処理と、基準距離の更新処理とが逐次実行され、これらの処理が終了されたときの基準距離16の設定に用いられた注目点が最近傍点として決定される。従って、最近傍点の探索が進むにつれて、基準軸方向の探索範囲が狭められつつ最近傍点の探索が行なわれるので、最近傍探索が高速化され得る。<変形例について>以上、本発明の実施の形態について説明してきたが、本発明は上記実施の形態に限定されるものではなく様々な変形が可能である。例えば、画像処理装置200Aのステレオカメラ400に代えて、検出光を投影して三角測量の原理で三次元測定する測定機、あるいはレーザートラッカーなどが採用されたとしても本発明の有用性を損なうものではない。また、画像処理システム100Aにおいて、ステレオカメラ400は、腕部64に取付けられているが、ロボット座標系に対するステレオカメラ400の位置姿勢が取得可能な他の場所に取付けられたとしても本発明の有用性を損なうものではない。"