"予め用意されたテンプレートとの照合によって3次元の対象物を検出する3Dパターンマッチング方法であって、コンピュータが実行する工程として、前記対象物の表面形状を計測した3次元の点群データを記憶する3次元点群データベースから前記点群データを読み込む工程と、前記対象物の3次元形状を、前記点群データと同等の密度の点群で表したテンプレートを記憶するテンプレートデータベースから前記テンプレートを読み込む工程と、前記点群データと、前記テンプレートとを照合して、両者が一致するか否かを判定するテンプレートマッチング工程とを備え、前記テンプレートマッチング工程は、3次元空間を所定サイズの格子に分割し、各格子内に存在する前記点群データおよびテンプレートのデータ点数を特徴量とし、該特徴量の比較によって前記判定を行う工程である3Dパターンマッチング方法。請求項1記載の3Dパターンマッチング方法であって、前記テンプレートマッチング工程に先立って、3次元空間内に周期的に配列する配列点を求め、前記点群データに含まれる点を近接する前記配列点のデータに置換するリサンプリング工程を備える3Dパターンマッチング方法。請求項1記載の3Dパターンマッチング方法であって、前記テンプレートマッチング工程に先立って、前記点群データの分布状態に近似する近似面を求め、該点群データをそれぞれ前記近似面上の点のデータに置換するリサンプリング工程を備える3Dパターンマッチング方法。請求項1記載の3Dパターンマッチング方法であって、前記テンプレートマッチング工程に先立って、前記点群データの分布状態に近似する近似面を求めるとともに、3次元空間内に周期的に配列する配列点を求めて前記点群データに含まれる点を近接する前記配列点のデータに置換し、前記配列点のデータをそれぞれ前記近似面上の点のデータに置換するリサンプリング工程を備える3Dパターンマッチング方法。請求項1または2記載の3Dパターンマッチング方法であって、前記テンプレートマッチング工程の結果に基づき、前記対象物の点群データに対して前記テンプレートを相対的に配置する工程と、前記点群データとテンプレートを構成する点ごとの位置誤差に基づいて、両者のずれを所定の評価式に基づいて定数的に評価する工程と、前記点群データに対する前記テンプレートの相対的な位置および姿勢を変えながら前記評価を行い、前記ずれが最小になると評価される位置および姿勢を求める工程とを備える3Dパターンマッチング方法。テンプレートとの比較によって点群データから対象物を検出する方法は有用ではあるが、従来技術では、検出できる対象物が限定されていたり、精度が不十分だったりするという課題があった。ICPは高い精度で対象物を検出可能ではあるが、計算量が多大となり、解析を開始する初期条件としての点群データとテンプレートとの相対的配置によっては膨大な計算時間を要し、十分な精度も確保できないという課題があった。これらの課題は、レーザ計測によらず、3次元の点群データとテンプレートとの照合によって対象物を検出する際に共通の課題であった。本発明は、かかる検出において対象物の制約なく、検出の処理速度を速め、精度向上を図ることを目的とする。本発明は、コンピュータによって、3次元の対象物を検出する3Dパターンマッチング方法として構成することができる。即ち、予め用意されたテンプレートとの照合によって3次元の対象物を検出する3Dパターンマッチング方法であって、コンピュータが実行する工程として、前記対象物の表面形状を計測した3次元の点群データを記憶する3次元点群データベースから前記点群データを読み込む工程と、前記対象物の3次元形状を、前記点群データと同等の密度の点群で表したテンプレートを記憶するテンプレートデータベースから前記テンプレートを読み込む工程と、前記点群データと、前記テンプレートとを照合して、両者が一致するか否かを判定するテンプレートマッチング工程とを備え、前記テンプレートマッチング工程は、3次元空間を所定サイズの格子に分割し、各格子内に存在する前記点群データおよびテンプレートのデータ点数を特徴量とし、該特徴量の比較によって前記判定を行う工程である3Dパターンマッチング方法である。本発明によれば、上述の通り、格子内に存在するデータ点数を特徴量として、対象物の点群データとテンプレートとの照合を行う。このように特徴量によって点群データおよびテンプレートのそれぞれをモデル化することによって、3次元空間内での両者の照合が比較的容易となり、対象物形状の制約なく検出が可能となる。また、照合が容易になる結果、テンプレートの位置、姿勢を多様に変化させて照合することが可能となるため、検出精度を向上させることができる。上記態様においては、3次元空間を立方体で分割する他、格子は種々の形状をとることができる。またその寸法も任意に設定可能であるが、点群データおよびテンプレートのデータ点数が、十分、有意な値となるよう、これらのデータ点数の空間密度に応じて設定することが好ましい。特徴量としては、上述の他、曲率、反射率を併せて用いても良い。曲率は、データの配置を曲面近似することによって求めることができる。反射率は、レーザ計測する際に各点ごとに、射出光と反射光との強度の比として計測しておくことができ、これを特徴量とすることによって、例えば、反射鏡などの地物を容易に検出することが可能となる。複数の特徴量を併用する場合には、これらの特徴量の重み付き加算値を用いるようにしてもよい。本発明においては、さらに、前記テンプレートマッチング工程に先立って、3次元空間内に周期的に配列する配列点を求め、前記点群データに含まれる点を近接する前記配列点のデータに置換するリサンプリング工程を備えるうようにしてもよい。計測によって得られる点群データには少なからずノイズが含まれているのが通常である。上述の態様により、車両計測による点群の偏り近いほど密で、遠いほど粗を改善することができる。周期的に配列する配列点とは、例えば、3次元空間に直交座標系、円筒座標系、極座標系によって定められる格子点を利用することができる。また、周期的とは、必ずしも等間隔であることを意味せず、例えば、配列点の間隔を正弦関数などの周期関数によって変化させてもよい。また、テンプレートマッチング工程に先立って、前記点群データの分布状態に近似する近似面を求め、該点群データをそれぞれ前記近似面上の点のデータに置換するリサンプリング工程を備えるようにしてもよい。検出されるべき対象物が現実に存在する物である以上、その表面は何らかの平面または曲面で構成されているはずである。上述の態様では、点群データの分布状態から近似面を求め、近似面上の点で元のデータを置換することによって、点群データに含まれるノイズの影響を抑制することができ、検出精度をより向上させることができる。近似面上の点は、種々の方法で求めることができる。例えば、空間内に予め設定された格子点を前記近似面に射影することで、置換されるべき点群を求めても良い。また、原点群データを、それぞれ近似面に射影して置換されるべき点群を求めても良い。さらに、前記テンプレートマッチング工程に先立って、前記点群データの分布状態に近似する近似面を求めるとともに、3次元空間内に周期的に配列する配列点を求めて前記点群データに含まれる点を近接する前記配列点のデータに置換し、前記配列点のデータをそれぞれ前記近似面上の点のデータに置換するリサンプリング工程を備えるようにしてもよい。上述した2つの態様のリサンプリングデータを併用する態様である。こうすることにより、相互の利点を活かし、ノイズを効果的に除去することができる。また、本発明では、さらに、前記テンプレートマッチング工程の結果に基づき、前記対象物の点群データに対して前記テンプレートを相対的に配置する工程と、前記点群データとテンプレートを構成する点ごとの位置誤差に基づいて、両者のずれを所定の評価式に基づいて定数的に評価する工程と、前記点群データに対する前記テンプレートの相対的な位置および姿勢を変えながら前記評価を行い、前記ずれが最小になると評価される位置および姿勢を求める工程とを備えるものとしてもよい。これは、いわゆるICPによる検出工程を追加した態様である。こうすることによって、点群データとテンプレートとを構成する点ごとの位置誤差を評価するため、上述の特徴量を用いる方法よりも、両者をより精度良く一致させることができ、さらに検出精度を向上させることができる。一般にICPでは、計算開始の初期条件における点群データとテンプレートの相対的位置関係以下、初期位置というによって計算量が増大するとともに、検出精度が確保できないという課題があるが、本発明では、上記態様による照合は、特徴量を用いて点群データとテンプレートとを概ね一致させてあるから、初期位置の影響なく、十分な精度を確保することができる。本発明は、その他、上述の各工程を実現する機能部を設けることによって、対象物を検出する3次元対象物検出装置として構成することもできる。また、上述の各工程を、コンピュータに実行させるためのコンピュータプログラムとして構成してもよい。さらに、かかるコンピュータプログラムを記録したコンピュータが読み取り可能な記録媒体として構成してもよい。記録媒体としては、フレキシブルディスクやCD-ROM、光磁気ディスク、ICカード、ROMカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置RAMやROMなどのメモリおよび外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。A.装置構成:図1は、3次元対象物検出装置の構成を示す説明図である。3次元対象物検出装置10は、コンピュータに、図中の各機能を実現するコンピュータプログラムをインストールすることによって構成されている。本実施例では、スタンドアロンで稼働する装置として構成しているが、ネットワークで接続された複数のコンピュータからなる分散システムとして構成してもよい。3次元対象物検出装置10には、3次元点群データベース16、テンプレートデータベース17が備えられている。3次元点群データベース16は、レーザ計測装置で現実の空間をスキャンすることによって得られる3次元の点群データを格納するデータベースである。図の下側に、点群データの例を示した。車両にレーザ計測装置を搭載して、図示するようにスキャンしながら走行すると、車両から、道路、および周囲の壁や電柱などの表面までの距離を計測することができる。図中では、スキャンの軌跡が線状に描かれているが、計測は離散的に行われるため、計測した表面の位置は点状に得られている。スキャン時にレーザの射出した方向および車両の位置は既知であるから、これらの点の3次元座標を得ることができる。3時点点群データベース16に格納されている点群データとは、こうして得られた各点の3次元座標から構成されている。点群データは、対象物を検出可能な密度解像度と呼ぶこともできるとすることが好ましく、例えば、レーザスキャンの走査方向に5cm、スキャン走査線の間隔方向に50cm程度とすることができる。テンプレートデータベース17は、検出すべき対象物の3次元形状を表した3次元ポリゴンデータに従って、その表面を、点群データと同等の空間密度で点群化したデータ以下、テンプレートというを格納している。つまり、テンプレートとは、3次元モデルの原点とする相対座標で、対象物の表面上の各点の座標値を表したデータである。テンプレートは、検出すべき対象物に応じて複数種類用意されている。リサンプリング処理部13は、3次元点群データベース16内の点群データに対し、リサンプリング処理を施し、結果をリサンプリングデータ記憶部11に格納する。リサンプリング処理とは、点群データに含まれるノイズの影響を低減させるための処理である。リサンプリング処理の具体的な内容は後述する。テンプレートマッチング部14は、テンプレートデータベース17に格納されているテンプレートと、リサンプリングデータ記憶部11内の点群データとを照合する。テンプレートデータベース17内にある複数のテンプレートのうち、点群データに一致するものを検出することによって、対象物を検出するのである。テンプレートマッチング部14による検出結果は、マッチング結果記憶部12に記憶される。ICPマッチング部15は、テンプレートと、点群データとのICPマッチング処理を行う。ICPマッチングとは、点群データおよびテンプレートを構成する点ごとに、位置および姿勢のずれを評価し、両者の一致/不一致を判断する処理である。処理の具体的内容は後述する。本実施例では、ICPマッチングに先立って行われたテンプレートマッチングの結果に基づいて得られた相対的な位置および姿勢で、テンプレートを点群データに配置して、ICPマッチングを行う。マッチングの結果は、マッチング結果記憶部12に格納される。B.リサンプリング処理:図2は、リサンプリング処理の方法を示す説明図である。リサンプリング処理とは、点群データのノイズの影響を抑制するための処理である。図2aには近接する格子点への置換による処理を例示した。点群データは、3次元のデータであるが、図の煩雑化を回避するため、ここでは2次元のデータとして示した。図示する直線は、点群データの周囲を所定の間隔で区切った格子を表している。この処理では、例えば、点Pa1を点Pb1で置換するように、点群データを構成する各点図中の黒丸を、近接する格子点で置換する。図2bに示すように、点群データを近似する近似面を求め、点群データをそれぞれ近似面に射影した点のデータに置換する処理も例示することができる。図2bの処理では、点群データの点Pa1、Pa2、Pa3等に対し、これらを近似する直線Lを求める。そして、点Pc1、Pc2、Pc3等のように、点群データの各点を、直線Lに射影した点に置換する。点Pc1、Pc2、Pc3等のように、原点群データの点Pa1、Pa2、Pa3等を直線Lに射影してもよいが、射影の方法としては、図中の点PAを点PCに射影しているように、直線L上に、原点群データに代えて格子点を射影してもよい。図2bでは、2次元での処理を例示したが、実際の点群データは3次元空間に配置されているから、近似する近似面を求めることになる。本実施例では、近似面は平面としたが、曲面としてもよい。近似した平面の基となる点群において平面との距離が大きい点群の比率が多い場合は、地物の面が平面ではない可能性が高いので、近似面として曲面を求め、この曲面に対してリサンプリングすることとしてもよい。曲面の近似面は非線形最適化によって曲面を当てはめていくことにより求めることができる。また上述の場合においては、格子を区切る間隔を小さくして再びリサンプリング処理を行なうこととしてもよい。点群データに基づいて得られる近似面は、対象物の表面を近似する面であると考えられるから、図2bの方法によれば、点群データからノイズの影響を除去しつつ、対象物の形状により近づけたデータを得ることができる。図2a、図2bで示したリサンプリング処理は、いずれか一方を適用してもよいし、図2aの処理、図2bの処理の順に、双方を適用してもよい。図3は、リサンプリング処理のフローチャートである。リサンプリング処理部13図1参照の処理に相当する。ここでは、3次元空間に所定の間隔で格子を設定し、原点群データの各点の位置を近接する格子点へ置換し、置換された格子点を原点群データから求められる近似面に射影する処理を例示する。この置換は、先に図2a、図2bを順次適用した処理である。処理を開始すると、コンピュータのCPUは、注目点xを設定するステップS10。ここで、注目点xとは、上述した通り、原点群データを格子点に置換した点の一つである。そして、3次元の点群データから、前述の注目点xの近傍に存在するN点p1、p2、...pNを抽出するステップS11。そして、これらのN点p1、p2、...pNを主成分分析して、平面に近似する直交基底ベクトルvx、vyを求めるステップS12。主成分分析は、周知の解析方法であるため、詳細な説明は省略する。この直交基底ベクトルvx、vyで定義される平面が、近似面αとなる。CPUは、点xを近似面αに射影するステップS13。図中に射影の様子を例示した。直交基底ベクトルvx、vyで定義される平面αに対し、点xからおろした垂線の足を射影点x’とするのである。直交基底ベクトルvx、vyの原点からxまでの座標は既知であるから、射影点x’のvx成分a、vy成分bも求めることができる。CPUは、全ての射影点x’を無条件にリサンプリング点として採用する訳ではない。本実施例では、注目点xから射影点x’までの距離Dが所定の閾値Th以下の場合に、射影点x’をリサンプリング点として追加するのである。近似面αから遠方にある格子点まで全てをリサンプリング点として追加すると、データ点数が増大しすぎるとともに、リサンプリング点の密度が均一とならず、マッチング処理に悪影響を与えるからである。すなわち、距離Dが大きな点は近似面に近似できているとは言い難く、この点をそのままリサンプリング点として追加すると元の形状と大きく乖離した点群データが得られてしまう。そこで、距離Dが大きな点は近似面に射影せず、原データをそのままリサンプリング点に追加することで、壁や路面などの平面等で近似可能な点群はリサンプリングされ、車両や電柱など平面での近似が困難な点群はそのまま残すことが可能である。すなわち、元の形状を保ったリサンプリング方法が可能となる。図3の処理方法によれば、格子点を射影することでリサンプリング点を得ることができる。格子点は空間上に均一に並んだ点であるため、この方法によれば、リサンプリング点を概ね均等な密度で得ることができる利点がある。図3の処理に代えて、原点群データを構成する各点を射影するようにしてもよい。この場合には、ステップS13における条件を省略し、原点群データから射影点までの距離に関係なくリサンプリングデータとして追加することができる。図4は、リサンプリングの処理結果例を示す説明図である。図中のOBJ1~OBJ3は、電柱に相当する部分である。図4aは、原点群データを図示したものである。レーザスキャン時の走査線に沿って点群データが配列されており、走査方向には点群データの密度が高く、走査線に交差する方向ではやや疎になっていることが分かる。図4bは、近接する格子点に割り当てる方法図2aに示した方法でリサンプリングした結果例である。この方法では、全点群データの密度が均一になっていることが分かる。図4cは、実施例におけるリサンプリング処理の結果である。つまり、図2aの方法でリサンプリングした結果に対し、図2bの方法によるリサンプリング処理を施したものである。道路面において点群データの密度がほぼ均一になるとともに、領域OBJ3に示すように電柱の形状も保持されていることが分かる。このように本実施例のリサンプリング処理によれば、対象物の形状を保持したまま、リサンプリングデータとして、密度がほぼ均一な点群データを得ることができる。C.正規化テンプレートマッチング:図5は、正規化テンプレートマッチング処理の方法を示す説明図である。図5aは、マッチングの対象となる対象物の点群データを示した。説明の便宜上、ティーポットを例示しているが、現実には道路際などに存在する電柱その他の地物が対象物となる。点群データは、図3で示した上述のリサンプリング処理を施したものである以下リサンプリングデータという。正規化テンプレートマッチング処理では、3次元空間内に格子を設定し、各格子内に存在する点群データのデータ点数メッシュ密度ということもあるを特徴量として用いる。図5a中に示すように、ある3次元の格子内に点群データが6個存在すれば、特徴量=6となる。メッシュ密度を特定するための格子のサイズは、任意に設定可能であるが、対象物が複数の格子にまたがって存在する範囲で、リサンプリング処理で用いた格子よりも大きくすることが好ましい。図5bは、テンプレート例を示している。テンプレート用に設定されたx、y、zの3次元空間内で定義される3次元ポリゴンモデルの表面を対象物と同等の密度で点群データ化したものである。本実施例では、テンプレートに対し、さらに対象物と同じ格子によって、格子ごとのメッシュ密度を求め、この結果を正規化テンプレートマッチングに用いる。図5cは、対象物のリサンプリングデータと、テンプレートとのマッチング処理の考え方を示した。図の煩雑化を回避するため、ここでは、双方を2次元のデータとして例示してある。図中のx、y平面における領域Iの4つの格子に、対象物の点群データが存在するものとする。それぞれの格子に記載されている3,1,2,8という数は、対象物のメッシュ密度を表している。説明の便宜上、数字を示していない格子は、全てメッシュ密度が0であるものとする。対象物と同じ物体に対応するテンプレートTOも、同じく3,1,2,8というメッシュ密度を有している。このテンプレートTOを、まず、図示するように、原点付近に配置し、対象物のリサンプリングデータとテンプレートとの積を格子ごとに求めると、この状態では、全ての格子で、対象物とテンプレートの一方が0となっているから、全ての格子で積は0となる。テンプレートの位置を順に移動させながら、同様の処理を実行すると、x3,y2の位置領域T1に配置した時には、テンプレートの右上の格子メッシュ密度=1と、対象物の左下の格子メッシュ密度=2とが重なるから、積は2となる。このように、対象物とテンプレートとの位置関係に応じて、積の総和は変化し、テンプレートを領域Iに配置して、対象物に重なった時に最大となる。従って、積の総和が最大となる位置を求めることにより、対象物とテンプレートとが最も一致した状態を特定することができる。正規化テンプレートマッチング処理では、上述の手順によって、対象物とテンプレートとが最も一致した状態を求め、その状態での一致度を評価することによって、対象物がテンプレートに対応する物品か否かを判定するのである。また、車両にレーザ計測装置を搭載して車両の前方を扇状にレーザでスキャンしながら走行することによって得られた距離データに基づく点群においては、レーザ計測装置から遠い空間に比べて近い空間のほうが密度が高くなり、また、車両の速度が速いときに比べて遅いときのほうが密度が高くなる傾向がある。このような現実の地物とは無関係な点群密度の偏りは、メッシュ密度に影響し、さらに一致度の評価に影響する可能性がある。そこで、先述したように、原点群データの各点の位置を近接する格子点へ置換し、置換された格子点を原点群データから求められる近似面に射影するリサンプリング処理を行なうと、点群の密度の偏りがある程度均一化されるので、正規化テンプレートマッチングへの上述したような計測の事情によって生じる影響が少なくなる。すなわち、密度によって表す特徴量の相関を解析する正規化テンプレートマッチング処理の前処理として図3に示す方法でリサンプリング処理することは特に有効である。図6は、正規化テンプレートマッチング処理のフローチャートである。図1に示したテンプレートマッチング部14が実行する処理に相当する。処理を開始すると、CPUは、対象物のリサンプリングデータに対し、メッシュ密度を求めステップS20、その結果であるIx、y、zを処理用のメモリに格納するステップS21。Ix、y、zは、3次元の各軸方向にx、y、z番目の格子におけるメッシュ密度を表している。CPUは、また、テンプレートについてもメッシュ密度を求めステップS30、n番目のテンプレートを選択してステップS31、その結果TnX,Y,Zを処理用のメモリに格納するステップS32。TnX、Y、Zは、テンプレートを規定する3次元の各軸方向にX、Y、Z番目の格子におけるメッシュ密度を表している。そして、CPUは3次元的に正規化テンプレートマッチングを行いステップS40、正規化相関テーブルRNCCx,y,zを求めるステップS41。これらの処理では、テンプレートTnX,Y,Zを、図5cに示すように、リサンプリングデータのx,y,zの位置に配置して、正規化相関値RNCCを次式によって求めるのである。正規化相関テーブルRNCCx,y,zは、それぞれ、テンプレートの配置位置x,y,zに応じた正規化相関値RNCCを格納した3次元テーブルである。正規化相関テーブルを求めると、CPUは、その中の極大値を検出するステップS42。本実施例では、所定サイズのマスクを利用して極大値を求めるものとした。図中に正規化相関テーブルを二次元であるとして、3×3の二次元マスクを用いた場合の処理例を示した。処理R1に示すように、正規化相関テーブルのうち処理対象となるレコードに、マスクの中央の値を対応させ、判定領域を設定する。例えば、左下のレコード2丸囲みで示したを処理する際には、マスクを対応させた領域M1が判定領域となる。処理対象のレコードが、この判定領域内の他のレコードよりも大きい値となっている時は、極大値の候補レコードとして残し、そうでない場合には値0とする。同様に、丸囲み4のレコードには判定領域M2が特定され、この中で4は最大値であるから、極大値候補として残される。この極大値を取る位置X,Y,Zを検出候補位置として保存する。以上の処理を全レコードについて行うと、処理結果R2に示すように、2,4の2つのレコードのみが極大値候補として残る。そして、両者のうち大きい値である4が最終的にステップS42における極大値となる。この例では、2次元で3×3のマスクを用いる例を示したが、実際には、正規化相関テーブルは3次元テーブルであるから、3次元のマスクとし、20×20×20ほどのサイズとしている。CPUは、検出された極大値を所定のしきい値と比較するステップS43。極大値がしきい値よりも大きい場合には、リサンプリングデータとテンプレートとの一致度が十分に高いと判断し、対象物が検出されたものとしてステップS44、この処理を終了する。極大値がしきい値よりも小さい場合には、対象物とは異なるテンプレートを用いており、対象物が検出できなかったものと判断しステップS44、テンプレートを換えてステップS31、以上の処理を繰り返す。テンプレートを換える前に、テンプレートの角度を変えて同様の処理を繰り返すものとしてもよい。テンプレートの姿勢が対象物に対して相対的にずれているために、不一致と判断されている可能性もあるからである。対象物を検出した結果は、次のICPマッチング処理に引き継がれる。D.ICPマッチング:図7は、ICPマッチング処理の方法を示す説明図である。図7aの左側に示す状態でテンプレートが用意されているのに対し、対象物のリサンプリングデータが右側に示すように傾いた状態にあるものとする。ICPマッチング処理では、このテンプレートを順次、回転および平行移動することによって、リサンプリングデータに一致する状態を求め、対象物とテンプレートとの一致/不一致を判断し、対象物を検出する。図7bには、対象物に対するテンプレートの初期位置と検出精度との関係を示した。横軸に、初期位置の角度差をとり、縦軸にはICPマッチング処理を施した後のテンプレートと対象物との平均距離、即ちズレを示している。この例では、初期位置の角度差が35度以上になると、平均距離が極端に増大し、検出誤差が低下することが分かる。本実施例では、ICPマッチング処理に先立って、正規化テンプレートマッチングを施しており、対象物とテンプレートが概ね一致させてあるため、ICPマッチング処理の検出精度を十分に確保することができる。図8は、ICPマッチング処理のフローチャートである。ICPマッチング部15の処理に相当する。処理を開始すると、CPUは、初期値設定を行うステップS50。正規化テンプレートマッチングで得られた結果に基づき例えば、図6で得られた検出候補位置を用いることが可能である、リサンプリングデータに対してテンプレートを配置するのである。また、テンプレートを移動させるための回転行列Rおよび平行移動ベクトルMを、それぞれ用意する。CPUは、テンプレートとリサンプリングデータの各点の対応づけを行いステップS51、誤差量の計算及び最小化を行うステップS52。正規化テンプレートマッチングによってテンプレートとリサンプリングデータは比較的近接して配置されているから、テンプレートの近傍で、リサンプリングデータの対応する点を求めればよい。誤差量の計算および最小化は、次式に示すMSE値が最小となる回転行列R、平行移動ベクトルMを求める処理である。T...テンプレートの点群I...リサンプリングデータの点群N...点群の総数Σ...点群全体についての総和MSEが最小となる回転行列R3×3行列、平行移動ベクトルM3×1ベクトルは、回転行列の行列式デターミナントが1となる拘束条件を考慮して解を得る方法が知られている。かかる解法の一つとして、クォータニオン四元数とも言われるを用いた制約付最小二乗法が知られている。この解法については、公知の技術であるため、詳細な説明は省略する。CPUは、こうして得られた回転行列R、平行移動ベクトルMを用いて、テンプレートの点群の回転および平行移動を行うステップS53。リサンプリングデータを回転および平行移動してもよい。そして、終了条件を判定しステップS54、終了したと判断される場合は処理を終了する。終了していない場合は、ステップS51以降の処理を繰り返し実行する。終了条件は、条件1:所定反復回数施してもMSE値の変化が所定範囲内におさまっている場合、または条件2:所定の最大反復回数に至った場合とした。条件1に該当する場合は、MSE値の収束によってテンプレートと対象物が一致する状態が見いだされたことを意味し、条件2に該当する場合は、反復によってもMSE値が収束せず、テンプレートと対象物が不一致であると判断される場合であることを意味している。E.効果および変形例:以上で説明した本実施例によれば、対象物およびテンプレートを表す点群データを、メッシュ密度によって格子ごとの特徴量で表すことによって、効率的に正規化テンプレートマッチングを施すことが可能となり、形状の制約なく対象物を精度良く検出することが可能である。また、リサンプリング処理を施すことによって、点群データに含まれるノイズの影響を抑制することができ、さらに精度を向上することができる。さらに、正規化テンプレートマッチングを施した後にICPマッチングを行うため、ICPマッチングによる検出を安定的に高精度で実現することができる。なお、ICPマッチングが終了したときにテンプレートとリサンプリングデータとの対応する点同士の距離が予め設定した閾値以上のものがあれば、正規化テンプレートマッチングで誤マッチングが発生していると判断することもできる。本実施例においては、上述した種々の処理を全て備えている必要はなく、適宜、一部を省略しても差し支えない。本発明は上述の実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。例えば、実施例においてハードウェア的に構成されている部分は、ソフトウェア的に構成することもでき、その逆も可能である。"