トップ :: G 物理学 :: G01 測定;試験




【発明の名称】 段階的対応点探索方法、対応点候補抽出方法、三次元位置計測方法、これらの装置、並びに、記録媒体
【発明者】 【氏名】藤原 伸行

【氏名】恩田 寿和
【要約】 【課題】対応点探索における対応点間違いを排除する。

【解決手段】２つの画像１、２のうち、一方の画像（元画像）１で計測位置を指定し、この計測位置で小パッチ３を設定し、この小パッチ３を用いて他方の画像（参照画像）２上の探索範囲４を探索して対応点候補５を複数抽出し、次に、大パッチ６を元画像１の計測位置に設定し、この大パッチ６を用い、対応点候補５の位置のみについて相関を求め、最も相関の強いものを対応点７として検出する。
【特許請求の範囲】
【請求項１】 サイズの異なる２段階のパッチを用い、２つの画像のうち、一方の画像で計測位置を指定し、この計測位置で小さい方のパッチ（以降これを「小パッチ」と呼ぶ）を設定し、この小パッチを用いて他方の画像上の探索範囲を探索して対応点候補を複数抽出し、次に、大きい方のパッチ（以降これを「大パッチ」と呼ぶ）を前記一方の画像に設定し、この大パッチを用い、前記対応点候補の位置のみについて相関を求め、相関の最も強いものを対応点として検出することを特徴とする段階的対応点探索方法。
【請求項２】 相関値グラフから対応点候補を複数抽出する方法において、前記相関値グラフから相関の最も強い点を検出し、第一候補として、対応点候補を保存するための配列（以降これを「候補配列」と呼ぶ）の先頭へ保存し、前記相関値グラフから相関の強さが凸の点（以降これを「凸点」と呼ぶ）を順次検出し、前記候補配列に既に保存されている対応点候補（以降これを「保存候補」と呼ぶ）と比較し、前記凸点が保存候補に対して位置的に近傍にあり、かつ、相関が強ければ、この凸点を比較対象となった保存候補として更新し、相関の強さの順に前記候補配列をソートし、前記凸点が保存候補に対して位置的に近傍に無く、かつ、前記候補配列に余裕がある場合は、この凸点を候補配列の末尾に保存し、相関の強さの順に前記候補配列をソートし、前記凸点が保存候補に対して位置的に近傍に無く、かつ、前記候補配列に余裕がない場合は、工法配列の末尾の保存候補と比較し、凸点の方が相関が強いならば、この凸点を前記末尾の保存候補に更新し、相関の強さの順に前記候補配列をソートすることを特徴とする対応点候補抽出方法。
【請求項３】 元画像の縮小画像に小パッチ（以降これを縮小パッチ（小）」と呼ぶ）を設定し、参照画像の縮小画像の探索範囲上に関して前記縮小パッチ（小）を用いた相関計算により相関値グラフを作成し、この相関値グラフから対応点候補を抽出し、前記元画像の縮小画像に大パッチ（以降これを縮小パッチ（大）」と呼ぶ）を設定し、前記参照画像の縮小画像の前記対応点候補の位置のみに関して前記縮小パッチ（大）を用いた相関計算により最も相関の強い点を対応点として決定し、この決定した対応点の位置から通常画像上の対応点（以降これを「対応箇所」と呼ぶ）を計算し、元画像にパッチを設定し、このパッチを用いた相関計算により参照画像の探索範囲上の前記対応箇所近傍のみに関して対応点を検出することを特徴とする段階的対応点探索方法。
【請求項４】 請求項３において、請求項２に記載の対応点抽出方法により対応点候補を抽出することを特徴とする段階的対応点探索方法。
【請求項５】 請求項３又は４に記載の段階的対応点探索方法により、参照画像における対応点を検出し、次に、元画像を参照画像に、参照画像を元画像に入れ換え設定し、前記検出した対応点を計測位置（以降これを「計測位置（回帰）」と呼ぶ）として入れ換え設定後の元画像に設定し、請求項３又は４に記載の段階的対応点探索方法により参照画像における対応点（以降これを「回帰対応点」と呼ぶ）を検出し、入れ換え設定前の元画像における計測位置と前記回帰対応点との距離（以降これを「回帰距離」と呼ぶ）を計算し、前記回帰距離を基に、入れ換え設定前の参照画像において検出した前記対応点が適切か否か判断することを特徴とする段階的対応点探索方法。
【請求項６】 第１の対応点探索処理として、元画像の縮小画像に小パッチ（以降これを縮小パッチ（小）」と呼ぶ）を設定し、参照画像の縮小画像の探索範囲上に関して前記縮小パッチ（小）を用いた相関計算により相関値グラフを作成し、この相関値グラフから対応点候補を抽出し、前記元画像の縮小画像に大パッチ（以降これを縮小パッチ（大）」と呼ぶ）を設定し、前記参照画像の縮小画像の前記対応点候補の位置のみに関して前記縮小パッチ（大）を用いた相関計算により最も相関の強い点を対応点として検出すること、次に、元画像を参照画像に、参照画像を元画像に入れ換え設定すること、前記検出した対応点を計測位置（以降これを「計測位置（回帰）」と呼ぶ）として入れ換え設定後の元画像の縮小画像に設定すること、第２の対応点探索処理として、前記計測位置（回帰）に基づき、入れ換え設定後の参照画像の縮小画像の探索範囲上に関して小パッチ（以降これを縮小パッチ（小）」と呼ぶ）を用いた相関計算により相関値グラフを作成し、この相関値グラフから入れ換え設定後の参照画像の縮小画像上の対応点候補を抽出し、前記元画像の縮小画像に大パッチ（以降これを「縮小パッチ（大）」と呼ぶ）を設定し、入れ換え設定後の参照画像の縮小画像上の前記対応点候補の位置のみに関して縮小パッチ（大）を用いた相関計算により最も相関の強い点を対応点（以降これを「回帰対応点」と呼ぶ）として検出すること、入れ換え設定前の縮小画像における計測位置と前記回帰対応点との距離（以降これを「回帰距離（縮小）」と呼ぶ）を計算し、前記回帰距離（縮小）を基に、入れ換え設定前の参照画像の縮小画像において検出した前記対応点が適切か否か判断し、不適切であれば処理を中断し、適切であれば元画像と参照画像の設定関係を元に戻すこと、及び、入れ換え設定前の参照画像の縮小画像において検出した前記対応点の位置から通常画像上の対応点（以降これを「対応箇所」と呼ぶ）を計算し、元画像においてパッチを設定し、このパッチを用いた相関計算により、参照画像の探索範囲上の前記対応箇所近傍のみに関して対応点を検出することを特徴とする段階的対応点探索方法。
【請求項７】 請求項６において、第１及び第２それぞれの対応点探索処理で、請求項２に記載の対応点抽出方法により対応点候補を抽出することを特徴とする段階的対応点探索方法。
【請求項８】 左右画像を元画像及び参照画像として入力し、前記左右画像から元画像及び参照画像の縮小画像を作り、計測位置を前記元画像で指定し、請求項３又は４に記載の段階的対応点探索方法により前記参照画像上の対応点を求め、この対応点、前記計測位置及びカメラデータから三次元位置を計算することを特徴とする三次元位置計測方法。
【請求項９】 左右画像を元画像及び参照画像として入力し、左右画像から元画像及び参照画像の縮小画像を作り、計測位置を前記元画像で指定し、請求項５に記載の段階的対応点探索方法により前記参照画像上の対応点を求め、この対応点が不適切であれば処理を中断し、適切であれば、この対応点、前記計測位置及びカメラデータから三次元位置を計算することを特徴とする三次元位置計測方法。
【請求項１０】 左右画像を元画像及び参照画像として入力し、左右画像から元画像及び参照画像の縮小画像を作り、計測位置を前記元画像で指定し、請求項６又は７に記載の段階的対応点探索方法により前記参照画像上の対応点を求め、この対応点、前記計測位置及びカメラデータから三次元位置を計算することを特徴とする三次元位置計測方法。
【請求項１１】 左右画像を元画像及び参照画像として入力し、左右画像から元画像及び参照画像の縮小画像を作り、計測位置を前記元画像で指定し、請求項３又は４に記載の段階的対応点探索方法により前記参照画像上の対応点を求め、この対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算し、再計算で得た対応点、前記計測位置及びカメラデータから三次元位置を計算することを特徴とする三次元位置計測方法。
【請求項１２】 左右画像を元画像及び参照画像として入力し、左右画像から元画像及び参照画像の縮小画像を作り、計測位置を前記元画像で指定し、請求項５に記載の段階的対応点探索方法により前記参照画像上の対応点を求め、求めた対応点が不適切であれば処理を中断し、適切であればこの対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算し、再計算で得た対応点、前記計測位置及びカメラデータから三次元位置を計算することを特徴とする三次元位置計測方法。
【請求項１３】 左右画像を元画像及び参照画像として入力し、左右画像から元画像及び参照画像の縮小画像を作り、計測位置を前記元画像で指定し、請求項６又は７に記載の段階的対応点探索方法により前記参照画像上の対応点を求め、この対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算し、再計算で得た対応点、前記計測位置及びカメラデータから三次元位置を計算することを特徴とする三次元位置計測方法。
【請求項１４】 相関値グラフから対応点候補を複数抽出する装置において、対応点候補を保存するための配列（以降これを「候補配列」と呼ぶ）と、相関の最も強い点を検出し、第一候補として、前記候補配列の先頭へ保存する第一候補設定手段と、相関の強さが凸の点（以降これを「凸点」と呼ぶ）を順次検出する凸点検出手段と、前記凸点を前記候補配列に既に保存されている対応点候補（以降これを「保存候補」と呼ぶ）と比較し、凸点が前記保存候補に対して位置的に近傍にあり、かつ、相関が強ければ、この凸点を比較対象となった保存候補として更新し、相関の強さの順に前記候補配列をソートする第１処理手段と、前記凸点を前記保存候補と比較し、凸点が前記保存候補に対して位置的に近傍に無く、かつ、前記候補配列に余裕がある場合は、この凸点を前記候補配列の末尾に保存し、相関の強さの順に候補配列をソートする第２処理手段と、前記凸点を前記保存候補と比較し、凸点が前記保存候補に対して位置的に近傍に無く、かつ、前記候補配列に余裕がない場合は、前記候補配列の末尾の保存候補と比較し、凸点の方が相関が強いならば、この凸点を前記末尾の保存候補へ更新し、相関の強さの順に候補配列をソートする第３処理手段を具備することを特徴とする対応点候補抽出装置。
【請求項１５】 通常画像における計測位置とカメラデータを基に通常画像におけるエピポーララインを計算するエピポーラライン設定手段と、縮小比率及び前記計測位置に基づいて縮小画像における計測位置（以降これを「計測位置（縮小）」と呼ぶ）を計算する計測点変換手段と、縮小比率及び前記エピポーララインに基づいて縮小画像におけるエピポーラライン（以降これを「エピポーラライン（縮小）」と呼ぶ）を計算するエピポーラライン変換手段と、前記計測位置（縮小）に基づいて元画像の縮小画像において小パッチ（以降これを「縮小パッチ（小）」と呼ぶ）を設定する縮小パッチ（小）設定手段と、参照画像の縮小画像の前記エピポーラライン（縮小）上の探索範囲に関して前記縮小パッチ（小）を用いた相関計算を行い相関値グラフを作成する相関値グラフ作成手段と、前記相関値グラフから前記参照画像の縮小画像における対応点候補を抽出する対応点候補抽出手段と、前記計測位置（縮小）に基づいて前記元画像の縮小画像において大パッチ（以降これを「縮小パッチ（大）」と呼ぶ）を設定する縮小パッチ（大）設定手段と、前記参照画像の縮小画像の対応点候補の位置に関して前記縮小パッチ（大）を用いた相関計算を行い相関が最も強い点を縮小画像における対応点として設定する対応点設定手段と、前記縮小画像における対応点の位置から通常画像上の対応点（以降これを「対応箇所」と呼ぶ）を計算する対応箇所設定手段と、前記計測位置に基づいて前記元画像にパッチを設定するパッチ設定手段と、前記参照画像のエピポーラライン上の前記対応箇所近傍のみに関して、前記パッチを用いた相関計算によって対応点を検出する通常画像対応点検出手段を具備することを特徴とする段階的対応点探索装置。
【請求項１６】 請求項１５において、前記対応点候補抽出手段が請求項１４記載の対応点候補抽出装置であることを特徴とする段階的対応点探索装置。
【請求項１７】 元画像及び参照画像を含む通常画像、元画像及び参照画像の各縮小画像、並びに、通常画像の計測位置を基に、２段階のパッチ（以降これらを「縮小パッチ（小）及び縮小パッチ（大）」と呼ぶ）を用い、縮小画像において縮小パッチにより対応点候補を抽出し、この対応点候補から縮小パッチ（大）により対応点を決定し、この対応点位置に対応する通常画像における対応点（以降これを「対応箇所」と呼ぶ）の近傍のみに関して対応点を検出する第１の段階的対応点探索手段と、元画像と参照画像の設定を入れ換える元画像・参照画像設定入れ換え手段と、第１の段階的対応点探索手段で検出した前記対応点を計測位置（以降これを「計測位置（回帰）」と呼ぶ）として入れ換え設定された元画像に設定する計測位置（回帰）設定手段と、前記計測位置（回帰）、元画像と参照画像の設定が入れ換わった通常画像及びその縮小画像に基づき、２段階のパッチ（以降これらを「縮小パッチ（小）及び縮小パッチ（大）」と呼ぶ）を用い、縮小画像において縮小パッチにより対応点候補を抽出し、この対応点候補から縮小パッチ（大）により対応点を決定し、この対応点位置に対応する通常画像における対応点（以降これを「対応箇所」と呼ぶ）近傍のみに関して対応点（以降これを「回帰対応点」と呼ぶ）を検出する第２の段階的対応点探索手段と、前記計測位置と前記回帰対応点との距離（以降これを「回帰距離」ぽ呼ぶ）を計算する回帰距離計算手段と、前記回帰距離を基に第１の段階的対応点探索手段により検出された前記対応点が適切か否か判断する探索結果判断手段を具備することを特徴とする段階的対応点探索装置。
【請求項１８】 請求項１７において、第１の段階的対応点探索手段は請求項１５又は１６に記載の段階的対応点探索装置であり、第２の段階的対応点探索手段は、前記計測位置（回帰）とカメラデータを基に通常画像におけるエピポーララインを計算するエピポーラライン設定手段と、縮小比率及び前記計測位置に基づいて前記計測位置（回帰）から縮小画像における計測位置（以降これを「計測位置（縮小）」と呼ぶ）を計算する計測点変換手段と、縮小比率及び前記エピポーララインに基づいて縮小画像におけるエピポーラライン（以降これを「エピポーラライン（縮小）」と呼ぶ）を計算するエピポーラライン変換手段と、前記計測位置（縮小）に基づいて元画像の縮小画像において縮小パッチ（小）を設定する縮小パッチ（小）設定手段と、参照画像の縮小画像の前記エピポーラライン（縮小）上の探索範囲に関して縮小パッチ（小）を用いた相関計算を行い相関値グラフを作成する相関値グラフ作成手段と、この相関値グラフから前記参照画像の縮小画像における対応点候補を抽出する対応点候補抽出手段と、前記計測位置（縮小）に基づいて元画像の縮小画像において縮小パッチ（大）を設定する縮小パッチ（大）設定手段と、前記参照画像の縮小画像の対応点候補の位置に関して縮小パッチ（大）を用いた相関計算を行い相関が最も強い点を縮小画像における対応点として設定する対応点設定手段と、この縮小画像における対応点の位置から通常画像上の対応箇所を計算する対応箇所設定手段と、前記計測位置に基づいて元画像にパッチを設定するパッチ設定手段と、前記参照画像の前記エピポーラライン上の前記対応箇所近傍のみに関してパッチを用いた相関計算によって前記回帰対応点を検出する通常画像対応点検出手段を有することを特徴とする段階的対応点探索装置。
【請求項１９】 請求項１８において、第２の段階的対応点探索手段の対応点候補抽出手段が請求項１４記載の対応点候補抽出装置であることを特徴とする段階的対応点探索装置。
【請求項２０】 縮小画像において、縮小パッチ（小）を用いて対応点候補を抽出し、縮小パッチ（大）を用いて対応点候補から対応点を決定する第１の縮小画像対応点探索処理手段と、元画像と参照画像の設定を入れ換える元画像・参照画像設定入れ換え手段と、第１の縮小画像対応点探索処理手段で決定した対応点を計測位置（以降これを「計測位置（回帰）」と呼ぶ）として、入れ換え設定された元画像の縮小画像に設定する計測位置（回帰）設定手段と、前記計測位置（回帰）が設定された状態で、縮小画像において、縮小パッチ（小）を用いて対応点候補を抽出し、次に、縮小パッチ（大）を用いて対応点候補から対応点（以降これを「回帰対応点」と呼ぶ）を決定する第２の縮小画像対応点探索処理手段と、前記計測位置（回帰）と前記回帰対応点との距離（以降これを「回帰距離（縮小）」と呼ぶ）を計算する回帰距離計算手段と、この回帰距離（縮小）を基に第１の縮小画像探索処理手段により決定された縮小画像における前記対応点が適切か否か判断する探索結果判断手段と、適切であると判断された対応点の位置から通常画像上の対応箇所を計算する対応箇所設定手段と、通常画像及び計測位置に基づいて、元画像においてパッチを設定するパッチ設定手段と、通常画像、前記対応箇所及び前記パッチに基づいて、参照画像上におけるエピポーラライン上の前記対応箇所近傍のみに関して、前記パッチを用いた相関計算によって対応点を検出する通常画像対応点検出手段を具備することを特徴とする段階的対応点探索装置。
【請求項２１】 請求項２０において、第１の縮小画像対応点探索処理手段は、縮小比率及び通常画像における計測位置に基づいて縮小画像における計測位置（以降これを「計測位置（縮小）」と呼ぶ）を計算する計測点変換手段と、縮小比率及び通常画像のエピポーララインに基づいて縮小画像におけるエピポーラライン（以降これを「エピポーラライン（縮小）」と呼ぶ）を計算するエピポーラライン変換手段と、前記計測位置（縮小）に基づいて元画像の縮小画像において縮小パッチ（小）を設定する縮小パッチ（小）設定手段と、参照画像の縮小画像の前記エピポーラライン（縮小）上の探索範囲に関して前記縮小パッチ（小）を用いた相関計算を行い相関値グラフを作成する相関値グラフ作成手段と、相関値グラフから対応点候補を抽出する対応点候補抽出手段と、前記計測位置（縮小）に基づいて前記元画像の縮小画像において縮小パッチ（大）を設定する縮小パッチ（大）設定手段と、前記参照画像の縮小画像の対応点候補の位置に関して前記縮小パッチ（大）を用いた相関計算を行い相関が最も強い点を縮小画像における対応点として設定する対応点設定手段を有し、第２の縮小画像対応点探索処理手段は、前記計測位置（回帰）、カメラデータ及び縮小比率を基に縮小画像におけるエピポーラライン（以降これを「エピポーラライン（縮小）」と呼ぶ）を計算するエピポーラライン変換手段と、前記計測位置（回帰）に基づいて元画像の縮小画像において縮小パッチ（小）を設定する縮小パッチ（小）設定手段と、参照画像の縮小画像の前記エピポーラライン（縮小）上の探索範囲に関して前記縮小パッチ（小）を用いた相関計算を行い相関値グラフを作成する相関値グラフ作成手段と、この相関値グラフから対応点候補を抽出する対応点候補抽出手段と、前記計測位置（回帰）に基づいて前記元画像の縮小画像において縮小パッチ（大）を設定する縮小パッチ（大）設定手段と、参照画像の縮小画像の対応点候補の位置に関して縮小パッチ（大）を用いた相関計算を行い相関が最も強い点を縮小画像における回帰対応点として設定する対応点設定手段を有することを特徴とする段階的対応点探索装置。
【請求項２２】 請求項２１において、第１及び第２の縮小画像対応点探索処理手段が有する対応点候補抽出手段がそれぞれ、請求項１４に記載の対応点候補抽出装置であることを特徴とする段階的対応点探索装置。
【請求項２３】 左右画像を元画像及び参照画像として入力する画像入力手段と、左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、計測位置を元画像で指定する計測位置指定手段と、請求項１５又は１６に記載の段階的対応点探索装置と、この段階的対応点探索装置により検出された対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段を具備することを特徴とする三次元位置計測装置。
【請求項２４】 左右画像を元画像及び参照画像として入力する画像入力手段と、左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、計測位置を元画像で指定する計測位置指定手段と、請求項１７又は１８又は１９に記載の段階的対応点探索装置と、この段階的対応点探索装置により検出された対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段を具備することを特徴とする三次元位置計測装置。
【請求項２５】 左右画像を元画像及び参照画像として入力する画像入力手段と、左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、計測位置を元画像で指定する計測位置指定手段と、請求項２０又は２１又は２２に記載の段階的対応点探索装置と、この段階的対応点探索装置により検出された対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段を具備することを特徴とする三次元位置計測装置。
【請求項２６】 左右画像を元画像及び参照画像として入力する画像入力手段と、左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、計測位置を元画像で指定する計測位置指定手段と、請求項１５又は１６に記載の段階的対応点探索装置と、この段階的対応点探索装置により検出された対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算する対応点実数化手段と、再計算した対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段を具備することを特徴とする三次元位置計測装置。
【請求項２７】 左右画像を元画像及び参照画像として入力する画像入力手段と、左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、計測位置を元画像で指定する計測位置指定手段と、請求項１７又は１８又は１９に記載の段階的対応点探索装置と、この段階的対応点探索装置により検出された対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算する対応点実数化手段と、再計算した対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段を具備することを特徴とする三次元位置計測装置。
【請求項２８】 左右画像を元画像及び参照画像として入力する画像入力手段と、左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、計測位置を元画像で指定する計測位置指定手段と、請求項２０又は２１又は２２に記載の段階的対応点探索装置と、この段階的対応点探索装置により検出された対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算する対応点実数化手段と、再計算した対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段を具備することを特徴とする三次元位置計測装置。
【請求項２９】 請求項３又は４に記載する段階的対応点探索方法の手順を、当該段階的対応点探索方法をコンピュータで実現するコンピュータプログラムとして、記録している記録媒体。
【請求項３０】 請求項５に記載する段階的対応点探索方法の手順を、当該段階的対応点探索方法をコンピュータで実現するコンピュータプログラムとして記録している記録媒体。
【請求項３１】 請求項６又は７に記載する段階的対応点探索方法の手順を、当該段階的対応点探索方法をコンピュータで実現するコンピュータプログラムとして記録している記録媒体。
【請求項３２】 請求項８に記載する三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している記録媒体。
【請求項３３】 請求項９に記載する三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している記録媒体。
【請求項３４】 請求項１０に記載する三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している記録媒体。
【請求項３５】 請求項１１に記載する三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している記録媒体。
【請求項３６】 請求項１２に記載する三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している記録媒体。
【請求項３７】 請求項１３に記載する三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している記録媒体。
【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、段階的対応点探索方法、対応点候補抽出方法、三次元位置計測方法、これらの装置、並びに、記録媒体に関し、いわゆるステレオ画像を用いた三次元位置計測に適用して有用なものである。
【０００２】
【従来の技術】ステレオ画像を用いた三次元位置計測方法として、一方の入力画像の一部を計測位置にて切り出してその濃淡パターンを画像モデル（以降これを「パッチ」と呼ぶ）として記憶し、もう一方の入力画像（以降これを「参照画像」と呼ぶ）においてパッチと同じパターンを持つ画像の小領域の位置（以降これを「対応点」と呼ぶ）を、濃淡パターンの相関から検出する方法（以降これを「領域相関法」と呼ぶ）が用いられている。以降、パッチの元になる画像を「元画像」と呼ぶ。
【０００３】また、対応点探索においては、探索範囲をエピポーラライン上に拘束する手法が用いられることがある。エピポーララインとは対応点が存在可能な直線であり、ステレオ画像を取り込む２台のカメラの位置関係から導かれる。
【０００４】領域相関法について更に詳言すると、■先ず、検査前の予備段階として、対象物のサンプルの画像（元画像）の一部を切り出して、その部分の濃度に関するパターンを、パッチとして記憶する。
■次に、検査時に、もう一方のサンプルの画像（参照画像）から、１画素ずれた各点毎に順次パッチと同じ形状で且つ同じ大きさの濃度に関するパターンを切り出し、各点毎にパッチと切り出したパターンとの相関値を計算し、相関の最も強いパターンが切り出された点の位置を、パッチとの対応点の位置とする。ここで、相関値の大小と相関の強弱は相関値を求める計算式により異なり、相関値が最小の場合に相間が最強となる計算式と、相関値が最大の場合に相関が最強となる計算式とがある。
【０００５】下式（１）は２つのパターン間の相関値を求める計算式の一例であり、式中のＰi はパッチのｉ番目の画素の濃度であり、Ｑi は切り出したパターンのｉ番目の画素の濃度であり、この式（１）の場合は、切り出した各パターンのうち、相関値Ｃが最小となるパターンが切り出された点の位置を、対応点の位置として決定することになる。
【数１】

【０００６】また、下式（２）は相関値の計算式の他の例であり、この場合は、切り出したパターンのうち、相関値Ｃが最大となるパターンが切り出された点の位置を、対応点の位置として決定することになる。
【数２】

【０００７】上述した相関マッチング処理は、常識的で広く使用されているが、厳密に言うと次の点で問題がある。
【０００８】即ち、１画素ずつずれた各点毎にパターンを切り出しているから、式（１）の計算から得られる対応点の位置は１画素毎の離散的なものであり、つまり、１画素を単位とする整数で表されるので、場合によっては真の対応点から最大で±０．５画素分ずれた位置になる危険性がある。そして、この０．５画素のずれが実際の対象物上でどのような寸法になるかは、撮影に用いるビデオカメラの分解能等に依存するので、従来の相関マッチング処理では対処することができないものである。
【０００９】しかしながら、実用的には０．５画素のずれは影響が大きく、精密な位置決めには使用することができない。例えば、ビデオカメラの分解能が水平方向に５１２画素で視角が６０°、ビデオカメラと対象物間の距離が２ｍである場合、±０．５画素のずれは約５mmとなる。
【００１０】そこで、対応点位置を入力画像の分解能よりも精密に計算できるようにする技術として特開平８−４３０２４号公報（特願平６−１７８０２２号）で開示される「相関マッチングの対応点位置計測方法及び装置」がある。これは、次のような２種類の内容の、補間演算による対応点実数化処理技術である。
【００１１】相関が強いほど相関値が小さくなる計算式を用いる場合は、下記の手順■〜■により対応点位置を計測する。
■参照画像の各点毎に、パッチと同じ形状で且つ同じ大きさのパターンを切り出し、パッチと切り出したパターンとの相関値を、相関が強いほど相関値が小さくなる計算式で計算する。
■各点での相関値の計算結果から、相関が最も強い第１の点の位置Ａ0 と、同第１の点での相関値Ｃ0 と、第１の点を含む一次元上で第１の点の直前に位置する第２の点での相関値Ｃ-1と、同一次元上で第１の点の直後に位置する第３の点での相関値Ｃ+1とを求める。
■第２の点での相関値Ｃ-1と第３の点での相関値Ｃ+1の大小関係を判定する。
■判定結果から、Ｃ-1＞Ｃ+1の場合は下式（３）により、Ｃ-1＜Ｃ+1の場合は下式（４）により、参照画像におけるパッチとの対応点の位置Ａr を補間演算で求める。この補間演算により、対応点の位置Ａr は実数になる、つまり、対応点の位置は、整数位置Ａ0 から実数位置Ａr へと実数化される。
Ａr ＝Ａ0 −（１／２）（Ｃ-1−Ｃ+1）／（Ｃ0 −Ｃ-1） …式（３）
Ａr ＝Ａ0 ＋（１／２）（Ｃ+1−Ｃ-1）／（Ｃ0 −Ｃ+1） …式（４）
【００１２】相関が強いほど相関値が大きくなる計算式を用いる場合は、上述の「相関が強いほど相関値が小さくなる計算式を用いる場合」に対し、下記の点■■が異なるだけで、他の構成は同じである。
■パッチと切り出したパターンとの相関値を、相関が強いほど相関値が大きくなる計算式で計算する。
■上記と同様の判定結果から、Ｃ-1＜Ｃ+1の場合は上式（３）により、Ｃ-1＞Ｃ+1の場合は上式（４）により、参照画像におけるパッチとの対応点の位置Ａr を補間演算で求める。
【００１３】係る従来技術によれば、参照画像中でパッチとの真の対応点の近傍では、図２６に示すように、真の対応点Ａr を含む一次元即ち直線１１上の前後で、相関の強弱は真の対応点Ａr を中心に良い近似で対称に変化する。つまり、直線１１と直交する軸１２上に相関値Ｃをとれば、真の対応点Ａr より前側での相関値の変化直線１３と、後側での相関値の変化直線１４とは、互いに傾きの符号が逆で、その絶対値が同一の傾きである。なお、図２６では相関値が小さいほど相関が強いものとしているが、逆の場合でも同様である。
【００１４】更に詳言すると、まず、上記式（１）など、相関が強いほど相関値Ｃが小さくなる計算式を用いる場合、位置Ａと相関値Ｃとの直交座標系を導入すると、図２７または図２８に示すように、パターンを切り出した点の位置とその点での相関値との対（Ａ0 ，Ｃ0 ），（Ａ-1，Ｃ-1），（Ａ+1，Ｃ+1）をプロットすることができる。但し、Ａ0 は相関が最も強い第１の点の位置、Ｃ0 は第１の点Ａ0 での相関値、Ａ-1は第１の点を含む一次元Ａ上で第１の点の直前に位置する第２の点の位置、Ｃ-1は第２の点Ａ-1での相関値、Ａ+1は同一次元Ａ上で第１の点の直後に位置する第３の点の位置、Ｃ+1は第３の点Ａ+1での相関値をそれぞれ示している。
【００１５】図２７はＣ-1＞Ｃ+1となる場合の例であり、この場合は、点（Ａ0 ，Ｃ0 ）と点（Ａ-1，Ｃ-1）を通る実線の直線１５を引き、この直線１５と符号が反対で絶対値が等しい傾きを持ち且つ点（Ａ+1，Ｃ+1）を通る二点鎖線の直線１６との交点を求めれば、そのＡ座標が対応点の位置Ａr となる。
【００１６】図２８はＣ-1＜Ｃ+1となる場合の例であり、この場合は、点（Ａ0 ，Ｃ0 ）と点（Ａ+1，Ｃ+1）を通る実線の直線１７を引き、この直線１７と符号が反対で絶対値が等しい傾きを持ち且つ点（Ａ-1，Ｃ-1）を通る二点鎖線の直線１８との交点を求めれば、そのＡ座標が対応点の位置Ａr となる。
【００１７】一方、前記式（２）など、相関が強いほど相関値Ｃが大きくなる計算式を用いる場合、位置Ａと相関値Ｃとの直交座標系を導入すると、図２９または図３０に示すように、パターンを切り出した点の位置とその点での相関値との対（Ａ0 ，Ｃ0 ），（Ａ-1，Ｃ-1），（Ａ+1，Ｃ+1）をプロットすることができる。但し、Ａ0 は相関が最も強い第１の点の位置、Ｃ0 は第１の点Ａ0 での相関値、Ａ-1は第１の点を含む一次元Ａ上で第１の点の直前に位置する第２の点の位置、Ｃ-1は第２の点Ａ-1での相関値、Ａ+1は同一次元Ａ上で第１の点の直後に位置する第３の点の位置、Ｃ+1は第３の点Ａ+1での相関値をそれぞれ示している。
【００１８】図２９はＣ-1＜Ｃ+1となる場合の例であり、この場合は、図２７と同じく点（Ａ0 ，Ｃ0 ）と点（Ａ-1，Ｃ-1）を通る実線の直線１５を引き、この直線１５と符号が反対で絶対値が等しい傾きを持ち且つ点（Ａ+1，Ｃ+1）を通る二点鎖線の直線１６との交点を求めれば、そのＡ座標が対応点の位置Ａr となる。
【００１９】図３０はＣ-1＞Ｃ+1となる場合の例であり、この場合は、図２８と同じく点（Ａ0 ，Ｃ0 ）と点（Ａ+1，Ｃ+1）を通る実線の直線１７を引き、この直線１７と符号が反対で絶対値が等しい傾きを持ち且つ点（Ａ-1，Ｃ-1）を通る二点鎖線の直線１８との交点を求めれば、そのＡ座標が対応点の位置Ａr となる。
【００２０】係る特開平８−４３０２４号公報が開示する「相関マッチングの対応点位置計測方法」によれば、上述した対称性を利用して補間することにより真の対応点Ａr に実質的に等しい精密な対応点を求めることができ、しかも、この補間に前述した式（３）及び式（４）を用いると、これらは比較的単純な式なので、補間演算に要する時間が短いという利点がある。
【００２１】
【発明が解決しようとする課題】ところが、上記の「相関マッチングの対応点位置計測方法」も含め、従来技術に係る「領域相関法」においては、参照画面の探索範囲上にパッチと似通った画像パターンを持つ部分が複数点存在する場合、本来の位置とは異なる位置の点が対応点として検出されることがある。この間違った対応点は大きな計測誤差を生じる原因となる。
【００２２】本発明は上記従来技術に鑑み、対応点間違いの発生を排除することができる段階的対応点探索方法、対応点候補抽出方法、三次元位置計測方法、これらの装置、並びに、記憶媒体を提供することを目的とする。
【００２３】
【課題を解決するための手段】上記課題を解決するため、請求項１に係る発明は基本的な段階的対応点探索方法であり、サイズの異なる２段階のパッチを用い、２つの画像のうち、一方の画像で計測位置を指定し、この計測位置で小さい方のパッチ（以降これを「小パッチ」と呼ぶ）を設定し、この小パッチを用いて他方の画像上の探索範囲を探索して対応点候補を複数抽出し、次に、大きい方のパッチ（以降これを「大パッチ」と呼ぶ）を前記一方の画像に設定し、この大パッチを用い、前記対応点候補の位置のみについて相関を求め、相関の最も強いものを対応点として検出することを特徴とする。
【００２４】請求項２に係る発明は対応点候補抽出方法であり、相関値グラフから相関の最も強い点を検出し、第一候補として、対応点候補を保存するための配列（以降これを「候補配列」と呼ぶ）の先頭へ保存し、前記相関値グラフから相関の強さが凸の点（以降これを「凸点」と呼ぶ）を順次検出し、前記候補配列に既に保存されている対応点候補（以降これを「保存候補」と呼ぶ）と比較し、前記凸点が保存候補に対して位置的に近傍にあり、かつ、相関が強ければ、この凸点を比較対象となった保存候補として更新し、相関の強さの順に前記候補配列をソートし、前記凸点が保存候補に対して位置的に近傍に無く、かつ、前記候補配列に余裕がある場合は、この凸点を候補配列の末尾に保存し、相関の強さの順に前記候補配列をソートし、前記凸点が保存候補に対して位置的に近傍に無く、かつ、前記候補配列に余裕がない場合は、候補配列の末尾の保存候補と比較し、凸点の方が相関が強いならば、この凸点を前記末尾の保存候補に更新し、相関の強さの順に前記候補配列をソートすることを特徴とする。
【００２５】請求項３に係る発明は段階的対応点探索方法であり、元画像の縮小画像に小パッチ（以降これを縮小パッチ（小）」と呼ぶ）を設定し、参照画像の縮小画像の探索範囲上に関して前記縮小パッチ（小）を用いた相関計算により相関値グラフを作成し、この相関値グラフから対応点候補を抽出し、前記元画像の縮小画像に大パッチ（以降これを縮小パッチ（大）」と呼ぶ）を設定し、前記参照画像の縮小画像の前記対応点候補の位置のみに関して前記縮小パッチ（大）を用いた相関計算により最も相関の強い点を対応点として決定し、この決定した対応点の位置から通常画像上の対応点（以降これを「対応箇所」と呼ぶ）を計算し、元画像にパッチを設定し、このパッチを用いた相関計算により参照画像の探索範囲上の前記対応箇所近傍のみに関して対応点を検出することを特徴とする。
【００２６】請求項４に係る発明は、請求項３に係る発明において、請求項２に係る発明の対応点抽出方法により対応点候補を抽出することを特徴とする段階的対応点探索方法である。
【００２７】請求項５に係る発明は段階的対応点探索方法であり、請求項３又は４に係る発明の段階的対応点探索方法により、参照画像における対応点を検出し、次に、元画像を参照画像に、参照画像を元画像に入れ換え設定し、前記検出した対応点を計測位置（以降これを「計測位置（回帰）」と呼ぶ）として入れ換え設定後の元画像に設定し、請求項３又は４に係る発明の段階的対応点探索方法により参照画像における対応点（以降これを「回帰対応点」と呼ぶ）を検出し、入れ換え設定前の元画像における計測位置と前記回帰対応点との距離（以降これを「回帰距離」と呼ぶ）を計算し、前記回帰距離を基に、入れ換え設定前の参照画像において検出した前記対応点が適切か否か判断することを特徴とする。
【００２８】請求項６に係る発明は段階的対応点探索方法であり、第１の対応点探索処理として、元画像の縮小画像に小パッチ（以降これを縮小パッチ（小）」と呼ぶ）を設定し、参照画像の縮小画像の探索範囲上に関して前記縮小パッチ（小）を用いた相関計算により相関値グラフを作成し、この相関値グラフから対応点候補を抽出し、前記元画像の縮小画像に大パッチ（以降これを縮小パッチ（大）」と呼ぶ）を設定し、前記参照画像の縮小画像の前記対応点候補の位置のみに関して前記縮小パッチ（大）を用いた相関計算により最も相関の強い点を対応点として検出すること、次に、元画像を参照画像に、参照画像を元画像に入れ換え設定すること、前記検出した対応点を計測位置（以降これを「計測位置（回帰）」と呼ぶ）として入れ換え設定後の元画像の縮小画像に設定すること、第２の対応点探索処理として、前記計測位置（回帰）に基づき、入れ換え設定後の参照画像の縮小画像の探索範囲上に関して小パッチ（以降これを縮小パッチ（小）」と呼ぶ）を用いた相関計算により相関値グラフを作成し、この相関値グラフから入れ換え設定後の参照画像の縮小画像上の対応点候補を抽出し、前記元画像の縮小画像に大パッチ（以降これを「縮小パッチ（大）」と呼ぶ）を設定し、入れ換え設定後の参照画像の縮小画像上の前記対応点候補の位置のみに関して縮小パッチ（大）を用いた相関計算により最も相関の強い点を対応点（以降これを「回帰対応点」と呼ぶ）として検出すること、入れ換え設定前の縮小画像における計測位置と前記回帰対応点との距離（以降これを「回帰距離（縮小）」と呼ぶ）を計算し、前記回帰距離（縮小）を基に、入れ換え設定前の参照画像の縮小画像において検出した前記対応点が適切か否か判断し、不適切であれば処理を中断し、適切であれば元画像と参照画像の設定関係を元に戻すこと、及び、入れ換え設定前の参照画像の縮小画像において検出した前記対応点の位置から通常画像上の対応点（以降これを「対応箇所」と呼ぶ）を計算し、元画像においてパッチを設定し、このパッチを用いた相関計算により、参照画像の探索範囲上の前記対応箇所近傍のみに関して対応点を検出することを特徴とする。
【００２９】請求項７に係る発明は、請求項６に係る発明において、第１及び第２それぞれの対応点探索処理で、請求項２に係る発明の対応点抽出方法により対応点候補を抽出することを特徴とする段階的対応点探索方法である。
【００３０】請求項８に係る発明は三次元位置計測方法であり、左右画像を元画像及び参照画像として入力し、前記左右画像から元画像及び参照画像の縮小画像を作り、計測位置を前記元画像で指定し、請求項３又は４に係る発明の段階的対応点探索方法により前記参照画像上の対応点を求め、この対応点、前記計測位置及びカメラデータから三次元位置を計算することを特徴とする。
【００３１】請求項９に係る発明は三次元位置計測方法であり、左右画像を元画像及び参照画像として入力し、左右画像から元画像及び参照画像の縮小画像を作り、計測位置を前記元画像で指定し、請求項５に係る発明の段階的対応点探索方法により前記参照画像上の対応点を求め、この対応点が不適切であれば処理を中断し、適切であれば、この対応点、前記計測位置及びカメラデータから三次元位置を計算することを特徴とする。
【００３２】請求項１０に係る発明は三次元位置計測方法であり、左右画像を元画像及び参照画像として入力し、左右画像から元画像及び参照画像の縮小画像を作り、計測位置を前記元画像で指定し、請求項６又は７に係る発明の段階的対応点探索方法により前記参照画像上の対応点を求め、この対応点、前記計測位置及びカメラデータから三次元位置を計算することを特徴とする。
【００３３】請求項１１に係る発明は三次元位置計測方法であり、左右画像を元画像及び参照画像として入力し、左右画像から元画像及び参照画像の縮小画像を作り、計測位置を前記元画像で指定し、請求項３又は４に係る発明の段階的対応点探索方法により前記参照画像上の対応点を求め、この対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算し、再計算で得た対応点、前記計測位置及びカメラデータから三次元位置を計算することを特徴とする。
【００３４】請求項１２に係る発明は三次元位置計測方法であり、左右画像を元画像及び参照画像として入力し、左右画像から元画像及び参照画像の縮小画像を作り、計測位置を前記元画像で指定し、請求項５に係る発明の段階的対応点探索方法により前記参照画像上の対応点を求め、求めた対応点が不適切であれば処理を中断し、適切であればこの対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算し、再計算で得た対応点、前記計測位置及びカメラデータから三次元位置を計算することを特徴とする。
【００３５】請求項１３に係る発明は三次元位置計測方法であり、左右画像を元画像及び参照画像として入力し、左右画像から元画像及び参照画像の縮小画像を作り、計測位置を前記元画像で指定し、請求項６又は７に係る発明の段階的対応点探索方法により前記参照画像上の対応点を求め、この対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算し、再計算で得た対応点、前記計測位置及びカメラデータから三次元位置を計算することを特徴とする。
【００３６】請求項１４に係る発明は対応点候補抽出装置であり、相関値グラフから対応点候補を複数抽出する装置において、対応点候補を保存するための配列（以降これを「候補配列」と呼ぶ）と、相関の最も強い点を検出し、第一候補として、前記候補配列の先頭へ保存する第一候補設定手段と、相関の強さが凸の点（以降これを「凸点」と呼ぶ）を順次検出する凸点検出手段と、前記凸点を前記候補配列に既に保存されている対応点候補（以降これを「保存候補」と呼ぶ）と比較し、凸点が前記保存候補に対して位置的に近傍にあり、かつ、相関が強ければ、この凸点を比較対象となった保存候補として更新し、相関の強さの順に前記候補配列をソートする第１処理手段と、前記凸点を前記保存候補と比較し、凸点が前記保存候補に対して位置的に近傍に無く、かつ、前記候補配列に余裕がある場合は、この凸点を前記候補配列の末尾に保存し、相関の強さの順に候補配列をソートする第２処理手段と、前記凸点を前記保存候補と比較し、凸点が前記保存候補に対して位置的に近傍に無く、かつ、前記候補配列に余裕がない場合は、前記候補配列の末尾の保存候補と比較し、凸点の方が相関が強いならば、この凸点を前記末尾の保存候補へ更新し、相関の強さの順に候補配列をソートする第３処理手段を具備することを特徴とする。
【００３７】請求項１５に係る発明は段階的対応点探索装置であり、通常画像における計測位置とカメラデータを基に通常画像におけるエピポーララインを計算するエピポーラライン設定手段と、縮小比率及び前記計測位置に基づいて縮小画像における計測位置（以降これを「計測位置（縮小）」と呼ぶ）を計算する計測点変換手段と、縮小比率及び前記エピポーララインに基づいて縮小画像におけるエピポーラライン（以降これを「エピポーラライン（縮小）」と呼ぶ）を計算するエピポーラライン変換手段と、前記計測位置（縮小）に基づいて元画像の縮小画像において小パッチ（以降これを「縮小パッチ（小）」と呼ぶ）を設定する縮小パッチ（小）設定手段と、参照画像の縮小画像の前記エピポーラライン（縮小）上の探索範囲に関して前記縮小パッチ（小）を用いた相関計算を行い相関値グラフを作成する相関値グラフ作成手段と、前記相関値グラフから前記参照画像の縮小画像における対応点候補を抽出する対応点候補抽出手段と、前記計測位置（縮小）に基づいて前記元画像の縮小画像において大パッチ（以降これを「縮小パッチ（大）」と呼ぶ）を設定する縮小パッチ（大）設定手段と、前記参照画像の縮小画像の対応点候補の位置に関して前記縮小パッチ（大）を用いた相関計算を行い相関が最も強い点を縮小画像における対応点として設定する対応点設定手段と、前記縮小画像における対応点の位置から通常画像上の対応点（以降これを「対応箇所」と呼ぶ）を計算する対応箇所設定手段と、前記計測位置に基づいて前記元画像にパッチを設定するパッチ設定手段と、前記参照画像のエピポーラライン上の前記対応箇所近傍のみに関して、前記パッチを用いた相関計算によって対応点を検出する通常画像対応点検出手段を具備することを特徴とする。
【００３８】請求項１６に係る発明は、請求項１５に係る発明において、前記対応点候補抽出手段が請求項１４に係る発明の対応点候補抽出装置であることを特徴とする段階的対応点探索装置である。
【００３９】請求項１７に係る発明は段階的対応点探索装置であり、元画像及び参照画像を含む通常画像、元画像及び参照画像の各縮小画像、並びに、通常画像の計測位置を基に、２段階のパッチ（以降これらを「縮小パッチ（小）及び縮小パッチ（大）」と呼ぶ）を用い、縮小画像において縮小パッチにより対応点候補を抽出し、この対応点候補から縮小パッチ（大）により対応点を決定し、この対応点位置に対応する通常画像における対応点（以降これを「対応箇所」と呼ぶ）の近傍のみに関して対応点を検出する第１の段階的対応点探索手段と、元画像と参照画像の設定を入れ換える元画像・参照画像設定入れ換え手段と、第１の段階的対応点探索手段で検出した前記対応点を計測位置（以降これを「計測位置（回帰）」と呼ぶ）として入れ換え設定された元画像に設定する計測位置（回帰）設定手段と、前記計測位置（回帰）、元画像と参照画像の設定が入れ換わった通常画像及びその縮小画像に基づき、２段階のパッチ（以降これらを「縮小パッチ（小）及び縮小パッチ（大）」と呼ぶ）を用い、縮小画像において縮小パッチにより対応点候補を抽出し、この対応点候補から縮小パッチ（大）により対応点を決定し、この対応点位置に対応する通常画像における対応点（以降これを「対応箇所」と呼ぶ）近傍のみに関して対応点（以降これを「回帰対応点」と呼ぶ）を検出する第２の段階的対応点探索手段と、前記計測位置と前記回帰対応点との距離（以降これを「回帰距離」ぽ呼ぶ）を計算する回帰距離計算手段と、前記回帰距離を基に第１の段階的対応点探索手段により検出された前記対応点が適切か否か判断する探索結果判断手段を具備することを特徴とする。
【００４０】請求項１８に係る発明は、請求項１７に係る発明において、第１の段階的対応点探索手段は請求項１５又は１６に係る発明の段階的対応点探索装置であり、第２の段階的対応点探索手段は、前記計測位置（回帰）とカメラデータを基に通常画像におけるエピポーララインを計算するエピポーラライン設定手段と、縮小比率及び前記計測位置に基づいて前記計測位置（回帰）から縮小画像における計測位置（以降これを「計測位置（縮小）」と呼ぶ）を計算する計測点変換手段と、縮小比率及び前記エピポーララインに基づいて縮小画像におけるエピポーラライン（以降これを「エピポーラライン（縮小）」と呼ぶ）を計算するエピポーラライン変換手段と、前記計測位置（縮小）に基づいて元画像の縮小画像において縮小パッチ（小）を設定する縮小パッチ（小）設定手段と、参照画像の縮小画像の前記エピポーラライン（縮小）上の探索範囲に関して縮小パッチ（小）を用いた相関計算を行い相関値グラフを作成する相関値グラフ作成手段と、この相関値グラフから前記参照画像の縮小画像における対応点候補を抽出する対応点候補抽出手段と、前記計測位置（縮小）に基づいて元画像の縮小画像において縮小パッチ（大）を設定する縮小パッチ（大）設定手段と、前記参照画像の縮小画像の対応点候補の位置に関して縮小パッチ（大）を用いた相関計算を行い相関が最も強い点を縮小画像における対応点として設定する対応点設定手段と、この縮小画像における対応点の位置から通常画像上の対応箇所を計算する対応箇所設定手段と、前記計測位置に基づいて元画像にパッチを設定するパッチ設定手段と、前記参照画像の前記エピポーラライン上の前記対応箇所近傍のみに関してパッチを用いた相関計算によって前記回帰対応点を検出する通常画像対応点検出手段を有することを特徴とする。
【００４１】請求項１９に係る発明は、請求項１８に係る発明において、第２の段階的対応点探索手段の対応点候補抽出手段が請求項１４に係る発明の対応点候補抽出装置であることを特徴とする段階的対応点探索装置である。
【００４２】請求項２０に係る発明は段階的対応点探索装置であり、縮小画像において、縮小パッチ（小）を用いて対応点候補を抽出し、縮小パッチ（大）を用いて対応点候補から対応点を決定する第１の縮小画像対応点探索処理手段と、元画像と参照画像の設定を入れ換える元画像・参照画像設定入れ換え手段と、第１の縮小画像対応点探索処理手段で決定した対応点を計測位置（以降これを「計測位置（回帰）」と呼ぶ）として、入れ換え設定された元画像の縮小画像に設定する計測位置（回帰）設定手段と、前記計測位置（回帰）が設定された状態で、縮小画像において、縮小パッチ（小）を用いて対応点候補を抽出し、次に、縮小パッチ（大）を用いて対応点候補から対応点（以降これを「回帰対応点」と呼ぶ）を決定する第２の縮小画像対応点探索処理手段と、前記計測位置（回帰）と前記回帰対応点との距離（以降これを「回帰距離（縮小）」と呼ぶ）を計算する回帰距離計算手段と、この回帰距離（縮小）を基に第１の縮小画像探索処理手段により決定された縮小画像における前記対応点が適切か否か判断する探索結果判断手段と、適切であると判断された対応点の位置から通常画像上の対応箇所を計算する対応箇所設定手段と、通常画像及び計測位置に基づいて、元画像においてパッチを設定するパッチ設定手段と、通常画像、前記対応箇所及び前記パッチに基づいて、参照画像上におけるエピポーラライン上の前記対応箇所近傍のみに関して、前記パッチを用いた相関計算によって対応点を検出する通常画像対応点検出手段を具備することを特徴とする。
【００４３】請求項２１に係る発明は、請求項２０に係る発明において、第１の縮小画像対応点探索処理手段は、縮小比率及び通常画像における計測位置に基づいて縮小画像における計測位置（以降これを「計測位置（縮小）」と呼ぶ）を計算する計測点変換手段と、縮小比率及び通常画像のエピポーララインに基づいて縮小画像におけるエピポーラライン（以降これを「エピポーラライン（縮小）」と呼ぶ）を計算するエピポーラライン変換手段と、前記計測位置（縮小）に基づいて元画像の縮小画像において縮小パッチ（小）を設定する縮小パッチ（小）設定手段と、参照画像の縮小画像の前記エピポーラライン（縮小）上の探索範囲に関して前記縮小パッチ（小）を用いた相関計算を行い相関値グラフを作成する相関値グラフ作成手段と、相関値グラフから対応点候補を抽出する対応点候補抽出手段と、前記計測位置（縮小）に基づいて前記元画像の縮小画像において縮小パッチ（大）を設定する縮小パッチ（大）設定手段と、前記参照画像の縮小画像の対応点候補の位置に関して前記縮小パッチ（大）を用いた相関計算を行い相関が最も強い点を縮小画像における対応点として設定する対応点設定手段を有し、第２の縮小画像対応点探索処理手段は、前記計測位置（回帰）、カメラデータ及び縮小比率を基に縮小画像におけるエピポーラライン（以降これを「エピポーラライン（縮小）」と呼ぶ）を計算するエピポーラライン変換手段と、前記計測位置（回帰）に基づいて元画像の縮小画像において縮小パッチ（小）を設定する縮小パッチ（小）設定手段と、参照画像の縮小画像の前記エピポーラライン（縮小）上の探索範囲に関して前記縮小パッチ（小）を用いた相関計算を行い相関値グラフを作成する相関値グラフ作成手段と、この相関値グラフから対応点候補を抽出する対応点候補抽出手段と、前記計測位置（回帰）に基づいて前記元画像の縮小画像において縮小パッチ（大）を設定する縮小パッチ（大）設定手段と、参照画像の縮小画像の対応点候補の位置に関して縮小パッチ（大）を用いた相関計算を行い相関が最も強い点を縮小画像における回帰対応点として設定する対応点設定手段を有することを特徴とする段階的対応点探索装置である。
【００４４】請求項２２に係る発明は、請求項２１に係る発明において、第１及び第２の縮小画像対応点探索処理手段が有する対応点候補抽出手段がそれぞれ、請求項１４に係る発明の対応点候補抽出装置であることを特徴とする段階的対応点探索装置である。
【００４５】請求項２３に係る発明は三次元位置計測装置であり、左右画像を元画像及び参照画像として入力する画像入力手段と、左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、計測位置を元画像で指定する計測位置指定手段と、請求項１５又は１６に係る発明の段階的対応点探索装置と、この段階的対応点探索装置により検出された対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段を具備することを特徴とする。
【００４６】請求項２４に係る発明は三次元位置計測装置であり、左右画像を元画像及び参照画像として入力する画像入力手段と、左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、計測位置を元画像で指定する計測位置指定手段と、請求項１７又は１８又は１９に係る発明の段階的対応点探索装置と、この段階的対応点探索装置により検出された対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段を具備することを特徴とする。
【００４７】請求項２５に係る発明は三次元位置計測装置であり、左右画像を元画像及び参照画像として入力する画像入力手段と、左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、計測位置を元画像で指定する計測位置指定手段と、請求項２０又は２１又は２２に係る発明の段階的対応点探索装置と、この段階的対応点探索装置により検出された対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段を具備することを特徴とする。
【００４８】請求項２６に係る発明は三次元位置計測装置であり、左右画像を元画像及び参照画像として入力する画像入力手段と、左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、計測位置を元画像で指定する計測位置指定手段と、請求項１５又は１６に係る発明の段階的対応点探索装置と、この段階的対応点探索装置により検出された対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算する対応点実数化手段と、再計算した対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段を具備することを特徴とする。
【００４９】請求項２７に係る発明は三次元位置計測装置であり、左右画像を元画像及び参照画像として入力する画像入力手段と、左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、計測位置を元画像で指定する計測位置指定手段と、請求項１７又は１８又は１９に係る発明の段階的対応点探索装置と、この段階的対応点探索装置により検出された対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算する対応点実数化手段と、再計算した対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段を具備することを特徴とする。
【００５０】請求項２８に係る発明は三次元位置計測装置であり、左右画像を元画像及び参照画像として入力する画像入力手段と、左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、計測位置を元画像で指定する計測位置指定手段と、請求項２０又は２１又は２２に係る発明の段階的対応点探索装置と、この段階的対応点探索装置により検出された対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算する対応点実数化手段と、再計算した対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段を具備することを特徴とする。
【００５１】請求項２９に係る発明は記録媒体であり、請求項３又は４に係る発明の段階的対応点探索方法の手順を、当該段階的対応点探索方法をコンピュータで実現するコンピュータプログラムとして、記録している。請求項３０に係る発明は記録媒体であり、請求項５に係る発明の段階的対応点探索方法の手順を、当該段階的対応点探索方法をコンピュータで実現するコンピュータプログラムとして記録している。請求項３１に係る発明は記録媒体であり、請求項６又は７に係る発明の段階的対応点探索方法の手順を、当該段階的対応点探索方法をコンピュータで実現するコンピュータプログラムとして記録している。請求項３２に係る発明は記録媒体であり、請求項８に係る発明の三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している。請求項３３に係る発明は記録媒体であり、請求項９に係る発明の三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している。請求項３４に係る発明は記録媒体であり、請求項１０に係る発明の三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している。請求項３５に係る発明は記録媒体であり、請求項１１に係る発明の三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している。請求項３６に係る発明は記録媒体であり、請求項１２に係る発明の三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している。請求項３７に係る発明は記録媒体であり、請求項１３に係る発明の三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している。
【００５２】
【発明の実施の形態】以下、図面に基づいて、本発明の実施形態例を説明する。
【００５３】［基本段階的対応点探索方法］図１に基づき、本発明の実施形態例として、基本となる段階的対応点探索方法（以降これを「基本段階的対応点探索方法」と呼ぶ）を説明する。図１は基本段階的対応点探索方法を説明する模式図を示す。
【００５４】図１を参照すると、本実施形態例では、対応点探索において、サイズの異なる２段階のパッチを用い、２つの画像１、２のうち、一方の画像１を元画像、もう一方の画像２を参照画像として設定し、元画像１上に適宜な計測位置を指定し、指定された計測位置にて元画像１に、先ず、小さい方のパッチ（以降これを「小パッチ」と呼ぶ）３を設定し、この小パッチ３を用いて参照画像２の探索範囲４上を探索することにより、対応点候補５を複数点（予め設定した数）抽出する。その後、大きい方のパッチ（以降これを「大パッチ」と呼ぶ）６を元画像１に設定し、この大パッチ６を用いて各対応点候補５の位置のみについて参照画像２において相関を求め、大パッチ６を用いた場合の相関の最も強いものを対応点７とする。これにより、対応点間違いの発生を排除することができ、対応点探索の信頼性が高まる。また、計測位置、対応点６及びカメラデータから、計測位置データに信頼性がある三次元位置計測を行うことができる。この場合、元画像及び参照画像は通常解像度の画像（以降これを「通常画像」と呼ぶ）であっても、通常画像を適当な縮小比率により縮小したもの、言い換えれば、通常画像から所定の間隔毎の画像データにより構成した解像度の低い画像（以降これを「縮小画像」と呼ぶ）であっても良い。
【００５５】つまり、対応点探索において、サイズの異なる２段階のパッチ３、６を用い、まず小パッチ３で複数の対応点候補５を抽出し、次に大パッチ６で対応点候補５の位置のみについて相関計算を行い対応点７を決定することで、小パッチ３において似通った画像パターンが存在していても、大パッチ６では比較する領域を広げた分、異なる画像となるため、対応点間違いを排除できる。更に、対応点探索において、サイズの異なる２段階のパッチ３、６を用い、予め小パッチ３で対応点候補５を抽出し、次に大パッチ６で対応点候補５の位置のみについて相関計算を行い対応点７を決定するため、単に大きなサイズのパッチのみ用いて対応点探索を行うよりも、計算量が減り高速な処理を実現できる。更に、対応点探索において、サイズの異なる２段階のパッチ３、６を用い、まず小パッチ３で対応点候補５を抽出し、次に大パッチ６で対応点候補５の位置のみについて相関計算を行い対応点７を決定することにより、１つの計測位置に対して大小２種類の画像パターンで対応点を検出することになるため、検出した対応点の信頼性が高い。
【００５６】［対応点候補抽出方法］図２に基づき、対応点候補を抽出する方法の例を説明する。図２は対応点候補抽出方法の処理手順のフローチャートを示す。図２に示すように、対応点候補を保存するための配列（以降これを「候補配列」と呼ぶ）を用いて、次の手順(1)〜(7) により、相関値グラフから対応点候補を抽出する。候補配列は一種の記憶手段である。相関値グラフは参照画像又はその縮小画像の探索範囲上に関して小パッチを用いた相関計算により得られる。
(1) まず、候補配列をクリアする（ステップＳ１）。
(2) 相関値グラフから相関の最も強い点を検出し、これを第一候補として、候補配列の先頭へ保存する（ステップＳ２）。ここで、相関が強いほど相関値が大きくなる相関計算方法を用いる場合は、相関値が最も大きい点が第一候補となり、また、相関が強いほど相関値が小さくなる相関計算方法を用いる場合は、相関値が最も小さい点が第一候補となる。
(3) 相関値グラフから、相関の強さが凸の点（以降これを「凸点」と呼ぶ）を順次検出する（ステップＳ３）。ここで、相関が強いほど相関値が大きくなる相関計算方法を用いる場合は、相関値が上側に凸の点が凸点となり、また、相関が強いほど相関値が小さくなる相関計算方法を用いる場合は、相関値が下側に凸の点が凸点となる。
(4) 候補配列に既に保存されている或る対応点候補（以降これを「保存候補」と呼ぶ）と比較し、或る凸点が保存候補に対して位置的に予め定めた所定の近傍にあり、かつ、相関が強ければ、この凸点を比較対象となった保存候補として更新し、相関の強さの順に候補配列をソートする（ステップＳ４、ステップＳ５、ステップＳ１０）。この処理の判断を以降「候補抽出第１判断」と呼ぶ。
(5) 保存候補と比較して、凸点が位置的に近傍に無く、候補配列に余裕がある場合は、この凸点を候補配列の末尾に保存し、相関の強さの順に候補配列をソートする（ステップＳ６、ステップＳ７、ステップＳ１０）。この処理の判断を以降「候補抽出第２判断」と呼ぶ。
(6) 保存候補と比較して、凸点が位置的に近傍に無く、候補配列に余裕がない場合は、候補配列中末尾の保存候補と比較し、凸点の方が相関が強いならば、この凸点を末尾の保存候補へ更新し、相関の強さの順に候補配列をソートする（ステップＳ８、ステップＳ９、ステップＳ１０）。この処理の判断を以降「候補抽出第３判断」と呼ぶ。なお、この候補抽出第３判断にて、凸点の方が相関が弱いならば、次の凸点に対する処理に移る。
(7) 上記手順(3) から(6) を繰り返し、相関グラフを一通り検査し終わったら、処理を終了する（ステップＳ１０、ステップＳ３）。
【００５７】［通常画像と縮小画像を用いた対応点探索方法］一般に、対応点探索には、時間がかかる濃淡パターンの相関演算を多量に行う必要があるため、パッチのサイズが大きくなるほど処理時間が長くなる。
【００５８】図３に示すように、通常画像（通常解像度の画像）２１と、通常画像２１から所定間隔毎の画像データにより構成した縮小画像（解像度の低い画像）２２とを段階的解像度画像として用意し、最初は縮小画像２２のエピポーラライン（縮小）２６上に関して対応点（縮小）２７を探索し、次に、この対応点（縮小）２７の位置に対応する通常画像２１上の位置（以降これを「対応箇所」と呼ぶ）２８の近傍のみについて、対応点探索を行うことにより、計算時間を短縮することができる。例えば、縮小比率１／２で行った場合、最初の対応点探索において探索範囲が１／２となりパッチサイズが１／４となるので相関計算の対象となる点数は１／８に減少し、処理時間が短縮し、処理が高速化する。なお、図３中、２１ａは元画像、２１ｂは参照画像を示し、これらは予め設定されており、２２ａは元画像２１ａの縮小画像、２２ｂは参照画像２１ａの縮小画像を示す。
【００５９】詳しくは、図４に示すように、下記■〜■の処理手順により、上記「通常画像と縮小画像を用いた対応点探索方法」を行う。
■元画像２１ａの計測位置２３から、その縮小画像２２ａにおける計測位置（縮小）２５を計算し、設定する（ステップＳ１１）。
■参照画像２１ｂにおけるエピポーラライン（探索範囲）２４から、その縮小画像２２ｂにおけるエピポーラライン（縮小）２６を計算し、設定する（ステップＳ１２）。
■計測位置（縮小）２５を設定した縮小画像２２ａにおいて縮小比率に対応するサイズのパッチ（以降これを「縮小パッチ」と呼ぶ）を設定する（ステップＳ１３）。
■もう一方の縮小画像２２ｂのエピポーラライン（縮小）２６上の探索範囲に関して対応点（縮小）２７を相関計算によって検出する（ステップＳ１４）。
■縮小画像２２ｂ上の対応点（縮小）２７の位置から参照画像２１ｂ上の対応点位置、つまり、対応箇所２８を計算する（ステップＳ１５）。
■計測位置２３を設定した元画像２１ａにおいてパッチを設定する（ステップＳ１６）。
■参照画像２１ｂのエピポーラライン２４上の対応箇所２８の近傍のみに関して対応点を相関計算によって検出する（ステップＳ１７）。
【００６０】［回帰的対応点探索方法］一方、図５に示すように、下記■〜■の処理手順により、対応点探索において、回帰的に対応点を探索することにより、対応点間違いを排除することが可能である。以降、この方法を、「回帰的対応点探索方法」と呼ぶ。
■先ず、図５（ａ）に示すように、２つの画像３１、３２のうち、一方の画像３１を元画像、もう一方の画像３２を参照画像として設定し、元画像３１上に適宜な計測位置３３を指定し、計測位置３３にて元画像３１にパッチを設定し、このパッチを用いて参照画像３２のエピポーラライン３７の探索範囲上で対応点３４を検出する。
■その後、今度は、図５（ｂ）に示すように、２つの画像３１、３２のうち、一方の画像３１を参照画像、もう一方の画像３２を元画像に入れ換えて設定し直し、先に検出した対応点３４を入れ換え設定後の元画像３２上の計測位置（以降これを「計測位置（回帰）」と呼ぶ）３５としてパッチを設定し、入れ換え設定後の参照画像３１のエピポーラライン３８上の探索範囲について回帰的に対応点探索を行い対応点３６を検出する（以降この処理を「回帰処理」と呼び、回帰処理で得られる対応点を「回帰対応点」と呼ぶ）。
(3) そして、計測位置３３と回帰対応点３６との距離（以降これを「回帰距離」と呼ぶ）を調べ、回帰距離が予め設定しておいた所定の範囲内である場合にのみ、対応点３３が正しく得られたものと判断する。これにより、対応点間違いの発生を排除することができ、対応点探索の信頼性が高まる。以降、必要に応じて、回帰処理の説明に用いる用語には「（回帰）」を付して他と区別する。回帰距離が所定範囲外であれば不適切であると判断することができ、この場合、処理を中断すれば良い。なお、所定範囲は、例えば適宜な手法により予め定めておくことができる。２つの画像３１、３２としては、通常画像、あるいは、縮小画像を用いることができる。また、処理中断の場合、不適切な対応点の次に相関が強い点を改めて対応点と定め、回帰処理を行うことができる。
【００６１】［段階的対応点探索方法１］そこで、上記「通常画像と縮小画像を用いた対応点探索方法」において、縮小画像上の対応点の探索にサイズの異なる２段階のパッチを用い、まず小パッチで複数の対応点候補を抽出し、次に大パッチで対応点候補の位置のみについて相関計算を行い縮小画像における対応点を決定し、この縮小画像における対応点位置に対応する通常画像の対応点（以降これを「対応箇所」と呼ぶ）を計算し、元画像に計測位置にパッチを設定し、対応箇所近傍のみに関して相関計算により参照画像上の対応点を探索することにより、対応点間違いを排除できるとともに、計算量が低減し、処理時間の短縮が可能となる。以降、この方法を「段階的対応点探索方法１」と呼ぶ。
【００６２】図６、図７に基づき、本発明の実施形態例として、上記「段階的対応点探索方法１」を説明する。
【００６３】図６、図７に示すように、下記(1) 〜(11)の処理手順により、「段階的対応点探索方法１」を行う。ここで、下記(1) から(8) までの処理は図６に示され、以降これを「縮小画像対応点探索処理」と呼び、図７中のステップＳ３１での処理に該当する。
(1) 通常画像における計測位置から、縮小画像における計測位置を計算する（図６中、ステップＳ２１）。
(2) 通常画像における計測位置とカメラデータから、通常画像におけるエピポーララインを設定する計算し、設定する（図６中、ステップＳ２２）。
(3) 通常画像におけるエピポーララインから、縮小画像におけるエピポーララインを計算し、設定する（図６中、ステップＳ２３）。
(4) 元画像の縮小画像において、縮小比率に対応するサイズの小パッチ（以降これを「縮小パッチ（小）」と呼ぶ）を設定する（図６中、ステップＳ２４）。
(5) 参照画像の縮小画像のエピポーラライン上の探索範囲に関して、縮小パッチ（小）を用いた相関計算を行い、相関値グラフを作成する（図６中、ステップＳ２５）。
(6) 相関値グラフから対応点候補を抽出する（図６中、ステップＳ２６）。例えば、先に図２に基づいて説明した上記「対応点候補抽出方法」により、対応点候補を抽出する。
(7) 元画像の縮小画像において、縮小比率に対応したサイズの大パッチ（以降これを「縮小パッチ（大）」と呼ぶ）を設定する（図６中、ステップＳ２７）。
(8) 参照画像の縮小画像の対応点候補の位置のみに関して、縮小パッチ（大）を用いた相関計算を行い、最も相関の強い点を対応点と決定する（図６中、ステップＳ２８）。
(9) 上記手順(1) 〜(8) による「縮小画像対応点探索処理」（図７中、ステップＳ３１参照）で決定した縮小画像上の対応点の位置から、これに対応する通常画像（参照画像）上の対応点（以降これを「対応箇所」と呼ぶ）を計算する（図７中、ステップＳ３２）。
(10)元画像（通常画像）において、小パッチを設定する（図７中、ステップＳ３３）。
(11)参照画像（通常画像）のエピポーラライン上の対応箇所近傍のみに関して、小パッチを用いた相関計算により対応点を検出する（図７中、ステップＳ３４）。即ち、上記手順(1) 〜(8) による「縮小画像対応点探索処理」で対応点間違いが予め排除されているので、通常画像での対応点探索において任意サイズの小パッチを一種類用い、このパッチを元画像に設定し、参照画像のエピポーラライン上の対応箇所近傍のみに関して相関計算により対応点を検出するようにしている。以上のように、上記「段階的対応点探索方法１」ではサイズの異なる２段階のパッチを用いて対応点探索を行うため、信頼性のある対応点を得ることができる。
【００６４】［段階的対応点探索方法２］次に、図８に基づいて、本発明の実施形態例として、上記「段階的対応点探索方法１」を回帰的に処理することにより、対応点間違いを効果的に排除できる対応点探索方法を説明する。以降、本例の方法を「段階的対応点探索方法２」と呼ぶ。
【００６５】図８に示すように、以下の手順(1) 〜(7) により「段階的対応点探索方法２」を行う。
(1) まず、上記「段階的対応点探索方法１」により、参照画像における対応点を検出する（ステップＳ４１）。
(2) 次に、回帰処理を行う否か判断し（ステップＳ４２）、行う場合はステップＳ４３へ、行わない場合はステップＳ４５へ進む。
(3) 最初は回帰処理を行うので、ステップＳ４３へ進み、元画像を参照画像に、参照画像を元画像に入れ換え設定する。
(4) 上記手順(1) で「段階的対応点探索方法１」により検出した対応点を、計測位置（以降これを「計測位置（回帰）」と呼ぶ）として、入れ換え設定後の元画像に設定する（ステップＳ４４）。
(5) 入れ換え設定後の参照画像における対応点（以降これを「回帰対応点」と呼ぶ）を上記「段階的対応点探索方法１」により検出する（ステップＳ４１）。
(6) 次に、回帰処理を行う否か判断するが（ステップＳ４２）、今回は不要なのでステップＳ４５へ進み、入れ換え設定前の元画像における計測位置と上記回帰対応点との距離（以降これを「回帰距離」と呼ぶ）を計算する。
(7) 回帰距離を基に、上記手順(1) で「段階的対応点探索方法１」により検出した対応点が適切か否か、対応点探索結果の是非を判断する（ステップＳ４６）。例えば、回帰距離が所定の範囲内であれば対応点が適切であると判断し、範囲外であれば不適切であると判断する。以上のように、上記「段階的対応点探索方法２」ではサイズの異なる２段階のパッチを用いて対応点探索を回帰的に行うため、信頼性のある対応点を得ることができる。
【００６６】ここで、上記手順(1) で「段階的対応点探索方法１」により対応点を検出する際の縮小パッチ（小）及び縮小パッチ（大）と、上記手順(5) で上記「段階的対応点探索方法１」により入れ換え設定後の参照画像における回帰対応点を検出する際の縮小パッチ（小）及び縮小パッチ（大）は、通常、対応するもの同士が同じ大きさにされるが、必ずしも同じ必要はなく、縮小パッチ（小）同士、縮小パッチ（大）同士で大きさが違っていても所期の目的を果たすことができる。
【００６７】［段階的対応点探索方法３］次に、図９に基づいて、本発明の実施形態例として、図６を参照して説明した上記「縮小画像対応点探索処理」を回帰的に行うことにより、対応点間違いを効果的に排除できる対応点探索方法を説明する。以降、本例の対応点探索方法を「段階的対応点探索方法３」と呼ぶ。
【００６８】図９に示すように、以下の手順(1) 〜(7) により「段階的対応点探索方法３」を行う。
(1) まず、上記「縮小画像対応点探索処理」により、参照画像の縮小画像における対応点（縮小）を検出する（ステップＳ５１）。
(2) 次に、回帰処理を行う否か判断し（ステップＳ５２）、回帰処理を行う場合はステップＳ５３へ、行わない場合はステップＳ５５へ進む。
(3) 最初は回帰処理を行うので、ステップＳ５３５進み、元画像を参照画像に、参照画像を元画像に入れ換え設定する。
(4) 手順(1) で上記「縮小画像対応点探索処理」により検出した対応点（縮小）を、計測位置（回帰）として、入れ換え設定後の元画像の縮小画像に設定する（ステップＳ５４）。
(5) 入れ換え設定後の参照画像の縮小画像について、計測位置（回帰）を用い、上記「縮小画像対応点探索処理」により、計測位置（回帰）に対応する対応点、つまり回帰対応点を検出する（ステップＳ５１）。
(6) 次に、回帰処理を行う否か判断するが（ステップＳ５２）、今度は行わないのでステップＳ５５へ進み、入れ換え設定前の縮小画像における計測位置（縮小）と上記回帰対応点との回帰距離（以降これを「回帰距離（縮小）」と呼ぶ）を計算する。
(7) 回帰距離（縮小）を基に、手順(1) で上記「縮小画像対応点探索処理」により検出した対応点（縮小）が適切か否か、対応点探索結果の是非を判断する（ステップＳ５６）。不適切(NO)であれば処理を中断し、適切(YES) であればステップＳ５７へ進む。例えば、回帰距離（縮小）が所定の範囲内であれば対応点が適切であると判断し、範囲外であれば不適切であると判断する。このように対応点が適切か否か判断することにより、処理時間を短縮することができる。
(8) 対応点探索が適切であれば、元画像と参照画像の関係を元に戻す（ステップＳ５７）。
(9) 手順(1) で上記「縮小画像対応点探索処理」により検出した対応点（縮小）位置から、通常画像（参照画像）上の対応箇所を計算する（ステップＳ５８）。
(10)元画像において小パッチを設定する（ステップＳ５９）。
(11)参照画像のエピポーラライン上の対応箇所近傍のみに関して、対応点を検出する（ステップＳ６０）。即ち、上記手順(7) により対応点間違いが予め排除されているので、通常画像での対応点探索においては任意サイズの小パッチを一種類のみ用い、このパッチを元画像に設定し、参照画像のエピポーラライン上の対応箇所近傍のみに関して相関計算により対応点を検出するようにしている。以上のように、上記「段階的対応点探索方法３」ではサイズの異なる２段階のパッチを用いた回帰的な対応点探索処理を縮小画面のみに対して行い対応点の是非を判断するため、処理の速い段階において対応点の是非を得ることができる。また、対応点が適切と判断された場合は、続けて、縮小画像における処理で検出された対応点近傍のみについて通常画像で対応点探索を行うため、従来方法と同程度の検出精度を得ることができる。
【００６９】ここで、上記手順(1) で「縮小画像対応点探索処理」により対応点（縮小）を検出する際の縮小パッチ（小）及び縮小パッチ（大）と、上記手順(5) で上記「縮小画像対応点探索処理」により入れ換え設定後の参照画像の縮小画像について回帰対応点を検出する際の縮小パッチ（小）及び縮小パッチ（大）は、通常、対応するもの同士が同じ大きさにされるが、必ずしも同じ必要はなく、縮小パッチ（小）同士、縮小パッチ（大）同士で大きさが違っていても所期の目的は達成される。
【００７０】ステレオ画像に計測位置を設定し、それの対応点を上記「基本段階的対応点探索方法」や、上記「段階的対応点探索方法１」、「段階的対応点探索方法２」あるいは「段階的対応点探索方法３」を用いて求めることにより、計測位置、対応点及びカメラデータから三次元位置が求まる。この場合、対応点間違いがなく信頼性が高いので、三次元位置計測データの信頼性も高い。以下、詳しく説明する。
【００７１】［三次元位置計測方法１］図１０に基づいて、本発明の実施形態例として、上記「段階的対応点探索方法１」を用いて行う三次元位置計測方法を説明する。以降、本例の方法を「三次元位置計測方法１」と呼ぶ。
【００７２】図１０に示すように、以下の手順(1) 〜(5) により「三次元位置計測方法１」を行い、ステレオ画像から三次元位置を計測する。
(1) 左右画像を元画像及び参照画像として入力する（ステップＳ６１）。
(2) 左右画像から左右縮小画像、つまり、元画像及び参照画像の各縮小画像を作る（ステップＳ６２）。
(3) 計測位置を通常画像の一方（元画像）で指定する（ステップＳ６３）。
(4) 上記「段階的対応点探索方法１」により対応点探索を行い、対応点を得る（ステップＳ６４）。
(5) この対応点と、計測位置及びカメラデータから三次元位置を計算する（ステップＳ６５）。このように、「三次元位置計測方法１」では、上記「段階的対応点探索方法１」で得た対応点のデータを用いて三次元位置計算を行うため、信頼性のある位置計測結果を得ることができる。
【００７３】［三次元位置計測方法２］次に、図１１に基づいて、本発明の実施形態例として、上記「段階的対応点探索方法２」を用いて行う三次元位置計測方法を説明する。以降、本例の方法を「三次元位置計測方法２」と呼ぶ。
【００７４】図１１に示すように、以下の手順(1) 〜(6) により「三次元位置計測方法２」を行い、ステレオ画像から三次元位置を計測する。
(1) 左右画像を元画像及び参照画像として入力する（ステップＳ７１）。
(2) 左右画像から左右縮小画像、つまり、元画像及び参照画像の縮小画像を作る（ステップＳ７２）。
(3) 計測位置を通常画像の一方（元画像）で指定する（ステップＳ７３）。
(4) 上記「段階的対応点探索方法２」により対応点探索を行い、対応点を得る（ステップＳ７４）。
(5) 手順(4) の上記「段階的対応点探索方法２」による処理で、回帰距離に基づいて対応点が不適切(NO)である判断された場合は、処理を中断する（ステップＳ７５）。
(6) 対応点が適切(YES) であると判断された場合は、この対応点、計測位置及びカメラデータから三次元位置を計算する（ステップＳ７６）。このように、「三次元位置計測方法２」では、上記「段階的対応点探索方法２」で得た対応点のデータを用いて三次元位置計算を行うため、信頼性のある位置計測結果を得ることができる。
【００７５】［三次元位置計測方法３］次に、図１２に基づいて、本発明の実施形態例として、上記「段階的対応点探索方法３」を用いて行う三次元位置計測方法を説明する。以降、本例の方法を「三次元位置計測方法３」と呼ぶ。
【００７６】図１２に示すように、以下の手順(1) 〜(6) により「三次元位置計測方法３」を行い、ステレオ画像から三次元位置を計測する。
(1) 左右画像を元画像及び参照画像として入力する（ステップＳ８１）。
(2) 左右画像から左右縮小画像、つまり、元画像及び参照画像の縮小画像を作る（ステップＳ８２）。
(3) 計測位置を通常画像の一方（元画像）で指定する（ステップＳ８３）。
(4) 上記「段階的対応点探索方法３」により対応点探索を行い、対応点を得る（ステップＳ８４）。
(5) 手順(4) の上記「段階的対応点探索方法３」による処理で、回帰距離（縮小）に基づいて対応点は不適切(NO)である判断された場合は、処理を中断する（ステップＳ８５）。
(6) 対応点が適切(YES) であると判断された場合は、この対応点、計測位置及びカメラデータから三次元位置を計算する（ステップＳ８６）。このように、「三次元位置計測方法３」では、上記「段階的対応点探索方法３」で得た対応点のデータを用いて三次元位置計算を行うため、信頼性のある位置計測結果を得ることができる。
【００７７】［三次元位置計測方法４］画像データは離散的なデータであるから、上記「三次元位置計測方法１」乃至「三次元位置計測方法３」においては、上記「段階的対応点探索方法１」乃至「段階的対応点探索方法１」により得られる対応点が離散的な画素の位置データとして与えられるため、実際の対応点位置と比べて最大で１／２画素の誤差を生じる。従って、高精度位置決めが要求される作業においてはこの誤差を小さく抑える必要がある。
【００７８】そこで、本実施形態例では、上記「段階的対応点探索方法１」により得られる対応点を、誤差を小さく抑えるため、対応点実数化方式で再計算することにより真の対応点を求め、三次元位置計測を行う。以降、本例の三次元位置計測方法を「三次元位置計測方法４」と呼ぶ。
【００７９】対応点実数化方式としては、適宜な補間演算を行うものを使用すれば良いが、ここでは「直線型対応点実数化方式」と「二次曲線型対応点実数化方式」を例に挙げ、下記に説明する。
■直線型対応点実数化方式では、上式（３）または（４）を用いた上述の補間演算を行うことにより、対応点位置を再計算する。
■二次曲線型対応点実数化方式では、二次曲線は唯一のピーク（凸または凹）を持つ曲線であることに着目して、図１３に模式的に示すように、対応点探索で得られる点を中心に幾つかの近傍点（３点以上）の相関値データを二次曲線で近似し、得られた二次曲線のピークの位置を対応点とするという補間演算により、対応点位置を再計算する。
【００８０】三次元位置計測方法４の処理手順のフローチャートを図１４に示す。図１４に示すように、次の手順(1) 〜(6) によりステレオ画像から三次元位置計測を行う。
(1) 左右画像を元画像及び参照画像として入力する（ステップＳ９１）。
(2) 左右画像から左右縮小画像、つまり、元画像及び参照画像の縮小画像を作る（ステップＳ９２）。
(3) 計測位置を通常画像の一方（元画像）で指定する（ステップＳ９３）。
(4) 上記「段階的対応点探索方法１」により対応点探索を行い、対応点を得る（ステップＳ９４）。
(5) 上記「直線型対応点実数化方式」あるいは「二次曲線型対応点実数化方式」等の対応点実数化方式により、対応点の再計算を行う（ステップＳ９５）。
(6) この再計算した対応点、計測位置及びカメラデータから三次元位置を計算する（ステップＳ９６）。このように、「三次元位置計測方法４」では、上記「段階的対応点探索方法１」で得た対応点のデータに対して対応点実数化処理による対応点再計算を行い、再計算で得たデータを用いて三次元位置計算を行うため、高精度かつ信頼性のある位置計測結果を得ることができる。
【００８１】［三次元位置計測方法５］本実施形態例に係る三次元位置計測方法５では、上記「段階的対応点探索方法２」により得られる対応点を対応点実数化方式により再計算し、三次元位置計測を行う。以降本例の三次元位置計測方法を「三次元位置計測方法５」と呼ぶ。
【００８２】三次元位置計測方法５の処理手順のフローチャートを図１５に示す。図１５に示すように、次の手順(1) 〜(7) によりステレオ画像から三次元位置計測を行う。
(1) 左右画像を元画像及び参照画像として入力する（ステップＳ１０１）。
(2) 左右画像から左右縮小画像、つまり、元画像及び参照画像の縮小画像を作る（ステップＳ１０２）。
(3) 計測位置を通常画像の一方（元画像）で指定する（ステップＳ１０３）。
(4) 上記「段階的対応点探索方法２」により対応点探索を行い、対応点を得る（ステップＳ１０４）。
(5) 手順(4) の上記「段階的対応点探索方法２」による処理で、回帰距離に基づいて対応点が不適切(NO)であると判断された場合は、処理を中断する（ステップＳ１０５）。
(6) 対応点が適切(YES) であると判断された場合は、上記「直線型対応点実数化方式」または「二次曲線型対応点実数化方式」等の対応点実数化方式により、対応点の再計算を行う（ステップＳ１０６）。
(7) この再計算した対応点、計測位置及びカメラデータから三次元位置を計算する（ステップＳ１０７）。このように、「三次元位置計測方法５」では、上記「段階的対応点探索方法２」で得た対応点のデータに対して対応点実数化処理による対応点再計算を行い、再計算で得たデータを用いて三次元位置計算を行うため、高精度かつ信頼性のある位置計測結果を得ることができる。
【００８３】［三次元位置計測方法６］本実施形態例に係る三次元位置計測方法６では、上記「段階的対応点探索方法３」により得られる対応点を対応点実数化方式により再計算し、三次元位置計測を行う。以降本例の三次元位置計測方法を「三次元位置計測方法６」と呼ぶ。する。
【００８４】三次元位置計測方法６の処理手順のフローチャートを図１６に示す。図１６に示すように、次の手順(1) 〜(7) によりステレオ画像から三次元位置計測を行う。
(1) 左右画像を元画像及び参照画像として入力する（ステップＳ１１１）。
(2) 左右画像から左右縮小画像、つまり、元画像及び参照画像の縮小画像を作る（ステップＳ１１２）。
(3) 計測位置を通常画像の一方（元画像）で指定する（ステップＳ１１３）。
(4) 上記「段階的対応点探索方法３」により対応点探索を行い、対応点を得る（ステップＳ１１４）。
(5) 手順(4) の上記「段階的対応点探索方法３」による処理で、回帰距離（縮小）に基づいて対応点が不適切(NO)と判断された場合は、処理を中断する（ステップＳ１１５）。
(6) 対応点が適切(YES) であると判断された場合は、上記「直線型対応点実数化方式」または「二次曲線型対応点実数化方式」等の対応点実数化方式により、対応点の再計算を行う（ステップＳ１１６）。
(7) この再計算した対応点、計測位置及びカメラデータから三次元位置を計算する（ステップＳ１１７）。このように、「三次元位置計測方法６」では、上記「段階的対応点探索方法３」で得た対応点のデータに対して対応点実数化処理による対応点再計算を行い、再計算で得たデータを用いて三次元位置計算を行うため、高精度かつ信頼性のある位置計測結果を得ることができる。
【００８５】［対応点探索装置１］図１７を参照して、本発明の実施形態例に係る段階的対応点探索装置として、図７により説明した上記「段階的対応点探索方法１」を実現する装置を説明する。以降、本例の装置を「段階的対応点探索装置１」と呼ぶ。
【００８６】図１７に示すように、当該「段階的対応点探索装置１」は、縮小画像対応点探索処理部４０と、対応箇所設定部４９、小パッチ設定部５０及び通常画像対応点検出部５１を有している。縮小画像対応点探索処理部４０は図６により説明した上記「縮小画像対応点探索処理」を実現する装置であり、エピポーラライン設定部４１、計測点変換部４２、エピポーラライン変換部４３、縮小パッチ（小）設定部４４、相関値グラフ作成部４５、対応点候補抽出部４６、縮小パッチ（大）設定部４７、対応点設定部４８からなる。計測データとしては、元画像の計測位置、カメラデータ、縮小比率（縮小データ）等が与えられる。
【００８７】縮小画像対応点探索処理部４０において、エピポーラライン設定部４１は、通常画像における計測位置のデータとカメラデータを基に、通常画像におけるエピポーララインを計算し、設定するものである。計測点変換部４２は、縮小比率及び通常画像の計測位置のデータに基づいて、通常画像の計測位置から縮小画像における計測位置（縮小）を計算するものである。エピポーラライン変換部４３は、縮小比率及びエピポーラライン設定部４１により計算された通常画像のエピポーララインのデータに基づいて、通常画像のエピポーララインから、縮小画像におけるエピポーラライン（縮小）を計算するものである。縮小パッチ（小）設定部４４は、縮小画像、縮小比率及び計測点変換部４２で計算される計測位置（縮小）のデータに基づいて、元画像の縮小画像において縮小比率に対応するサイズの縮小パッチ（小）を設定するものである。相関値グラフ作成部４５は、縮小画像、計測位置（縮小）、エピポーラライン（縮小）及び縮小パッチ（小）のデータを基に、参照画像の縮小画像におけるエピポーラライン（縮小）上の探索範囲に関して、縮小パッチ（小）を用いた相関計算を行い、相関値グラフを作成するものである。
【００８８】また、縮小画像対応点探索処理部４０内の対応点候補抽出部４６は、相関値グラフから所定複数個の対応点候補を抽出するものであり、上記「対応点候補抽出方法」により対応点候補を抽出する場合は、図３１に例示する構成の対応点候補抽出装置を用いることができる。
【００８９】図３１に示す対応点候補抽出装置は、候補配列９２と、第一候補設定部９３と、凸点検出部９４と、第１処理部９５と、第２処理部９６と、第３処理部９７を有している。候補配列９２は最初、初期化部９８により、その内容をクリアされる。第一候補設定部９３は、相関値グラフ作成部で作成された相関値グラフ９１から、相関の最も強い点を第一候補として、候補配列９２の先頭へ保存するものである。凸点検出部９４は、相関値グラフ９１から、相関の凸点を順次検出するものである。第１処理部９５は、凸点を候補配列９２中の保存候補と比較して、上記「候補抽出第１判断」により凸点が位置的に保存候補の近傍にあり、かつ、相関が強ければ、この凸点を比較対象となった保存候補として更新し、相関の強さの順に候補配列９２をソートするものである。第２処理部９６は、上記「候補抽出第２判断」により凸点が位置的に保存候補の近傍に無く、候補配列９２に余裕がある場合は、この凸点を候補配列９２の末尾に保存し、相関の強さの順に候補配列をソートするものである。第３処理部９７は、上記「候補抽出第３判断」により凸点が位置的に保存候補の近傍に無く、候補配列９２に余裕がない場合は、候補配列９２中の末尾の保存候補と比較し、凸点の方が相関が強いならば、この凸点を末尾の保存候補へ更新し、相関の強さの順に候補配列９２をソートするものである。第１〜第３の各処理部９５〜９７は相関値グラフ９１を一通り検査し終わるまで夫々の処理を繰り返す。第１〜第３処理部９５〜９５における「位置的に近傍」は、適宜な実験等により予め得て設定される。対応点候補は候補配列９２から得られる。
【００９０】更に、縮小画像対応点探索処理部４０内の縮小パッチ（大）設定部４７は、縮小画像、縮小比率及び計測位置（縮小）のデータに基づいて、元画像の縮小画像において縮小比率に対応するサイズの縮小パッチ（大）を設定するものである。対応点設定部４８は対応点候補及び縮小パッチのデータを基に、参照画像の縮小画像の対応点候補の位置に関して、縮小パッチ（大）を用いた相関計算を行い、相関が最も強い点を縮小画像における対応点として設定するものである。
【００９１】次に、対応箇所設定部４９は、縮小比率及び対応点設定部４８で設定された対応点のデータを基に、縮小画像における対応点の位置から通常画像上の対応箇所を計算するものである。小パッチ設定部５０は、通常画像及び計測位置のデータに基づいて、元画像において小パッチを設定するものである。
【００９２】通常画像対応点検出部５１は、対応点候補抽出部４６及び対応点設定部４８の存在により対応点間違いが予め排除されているので、通常画像、対応箇所及び大きさが適宜設定される小パッチのデータに基づいて、参照画像上におけるエピポーラライン上の対応箇所近傍のみに関して小パッチを用いた相関計算によって対応点を検出するものである。参照画像上におけるエピポーララインは、エピポーラライン設定部４１で計算、設定されるものが使用できる。
【００９３】以上のことから、この「段階的対応点探索装置１」では、縮小画像対応点探索処理部４０にて、縮小画像において縮小パッチ（小）を用いて対応点候補を抽出し、縮小パッチ（大）を用いて対応点候補から対応点を決定するという、サイズの異なる２段階のパッチ（縮小パッチ（小）と縮小パッチ（大））を用いて対応点探索を行い、次に、通常画像対応点検出部５１により、通常画像において対応箇所近傍のみに関して、小パッチを用いた相関計算で対応点を検出するため、対応点間違いを排除し、信頼性のある対応点を得ることができる。つまり、サイズの異なる２段階のパッチを用いて対応点探索を行うため、信頼性のある対応点を得ることができる。また、処理時間が短縮する。
【００９４】ここで、通常画像のデータ及び縮小画像のデータは、図２０や図２３に示す三次元位置計測装置の画像メモリ８４から供給される。また、縮小比率、カメラデータ等のデータはパラメータメモリ８２から、元画像の計測位置のデータは計測位置指定部８３からそれぞれ供給される。
【００９５】［対応点探索装置２］図１８を参照して、本発明の実施形態例に係る段階的対応点探索装置として、図８により説明した上記「段階的対応点探索方法２」を実現する装置を説明する。以降、本例の装置を「段階的対応点探索装置２」と呼ぶ。
【００９６】図１８に示すように、当該「段階的対応点探索装置２」は、第１の段階的対応点探索部６１、元画像・参照画像設定入れ換え部６２、計測位置（回帰）設定部６３、第２の段階的対応点探索部６４、回帰距離計算部６５及び探索結果判断部６５を有している。計測データとしては、元画像の計測位置、カメラデータ、縮小比率（縮小データ）、探索結果判断用の基準（例えば、回帰距離に対する範囲）等が与えられる。
【００９７】そのうち、第１の段階的対応点探索部６１は上記「段階的対応点探索方法１」を実現する装置である。従って、第１の段階的対応点探索部６１としては上記「段階的対応点探索装置１」と同様の構成のものが使用でき、その場合は、図１７を参照すれば、縮小画像対応点探索処理部４０（エピポーラライン設定部４１、計測点変換部４２、エピポーラライン変換部４３、縮小パッチ（小）設定部４４、相関値グラフ作成部４５、対応点候補抽出部４６、縮小パッチ（大）設定部４７及び対応点設定部４８）と、対応箇所設定部４９と、小パッチ設定部５０と、通常画像対応点検出部５１を有する。これらの説明は重複するので省略する。
【００９８】要するに、第１の段階的対応点探索部６１は、通常画像（元画像と参照画像）、元画像と参照画像の各縮小画像、通常画像の計測位置及び計測データを基に、上記「段階的対応点探索装置１」と同様、サイズの異なる２段階のパッチ（縮小パッチ（小）と縮小パッチ（大））を用い、縮小画像において、縮小パッチにより対応点候補を抽出し、更に縮小パッチ（大）により対応点候補から対応点を決定し、次いで、通常画像において対応箇所近傍のみに関してパッチを用いた相関計算により対応点を検出するものである。
【００９９】元画像・参照画像設定入れ換え部６２は、元画像と参照画像の設定を入れ換えるものである。即ち、第１の段階的対応点探索部６１で対応点が検出された後、元画像を参照画像に、参照画像を元画像に再設定する。
【０１００】計測位置（回帰）設定部６３は、第１の段階的対応点探索部６１で検出した通常画像における対応点を計測位置（回帰）として、入れ換え設定された元画像に設定するものである。
【０１０１】第２の段階的対応点探索部６４は回帰処理を行うものであり、計測位置（回帰）設定部６３で設定された計測位置（回帰）を用いて、元画像と参照画像の設定が入れ換わった通常画像及びその縮小画像について上記「段階的対応点探索方法１」を実現し、回帰対応点を検出する。従って、上記「段階的対応点探索装置１」に準じた構成そのが使用でき、その場合は、図１７を参照すれば、縮小画像対応点探索処理部４０（エピポーラライン設定部４１、計測点変換部４２、エピポーラライン変換部４３、縮小パッチ（小）設定部４４、相関値グラフ作成部４５、対応点候補抽出部４６、縮小パッチ（大）設定部４７及び対応点設定部４８）と、対応箇所設定部４９と、小パッチ設定部５０と、通常画像対応点検出部５１を有する。
【０１０２】第２の段階的対応点探索部６４による回帰処理においては、エピポーラライン設定部４１は、通常画像における計測位置（回帰）のデータ及びカメラデータを基に、通常画像におけるエピポーララインを計算し、設定する。計測点変換部４２は、縮小比率及び通常画像における計測位置（回帰）のデータに基づいて、計測位置（回帰）から縮小画像における計測位置（縮小）を計算する。エピポーラライン変換部４３は、縮小比率及びエピポーラライン設定部４１により設定された通常画像のエピポーララインのデータに基づいて、縮小画像におけるエピポーラライン（縮小）を計算する。縮小パッチ（小）設定部４４は、縮小画像、縮小比率及び計測位置（縮小）のデータに基づいて、元画像の縮小画像において縮小比率に対応するサイズの縮小パッチ（小）を設定する。相関値グラフ作成部４５は、縮小画像、計測位置（縮小）、エピポーラライン（縮小）及び縮小パッチ（小）のデータを基に、参照画像の縮小画像におけるエピポーラライン（縮小）上の探索範囲に関して、縮小パッチ（小）を用いた相関計算を行い、相関値グラフを作成する。
【０１０３】第２の段階的対応点探索部６４の対応点候補抽出部４６は相関値グラフから対応点候補を上記「対応点候補抽出方法」等により抽出するものであり、例えば図３１に示した構成のものが用いられる。上記「対応点候補抽出方法」により抽出する場合は、■まず、候補配列をクリアし、■相関の最も強い点を第一候補として、候補配列の先頭へ保存し、■相関値グラフから、相関の凸点を順次検出し、■凸点を保存候補と比較して、上記「候補抽出第１判断」により凸点が位置的に保存候補の近傍にあり、かつ、相関が強ければ、この凸点を比較対象となった保存候補として更新し、相関の強さの順に候補配列をソートし、■上記「候補抽出第２判断」により凸点が位置的に保存候補の近傍に無く、候補配列に余裕がある場合は、この凸点を候補配列の末尾に保存し、相関の強さの順に候補配列をソートし、■上記「候補抽出第３判断」により凸点が位置的に保存候補の近傍に無く、候補配列に余裕がない場合は、候補配列中末尾の保存候補と比較し、凸点の方が相関が強いならば、この凸点を末尾の保存候補へ更新し、相関の強さの順に候補配列をソートするという処理を、相関値グラフを一通り検査し終わるまで繰り返す。
【０１０４】第２の段階的対応点探索部６４の縮小パッチ（大）設定部４７は、縮小画像、縮小比率及び計測位置（縮小）のデータに基づいて、元画像の縮小画像において縮小比率に対応するサイズの縮小パッチ（大）を設定する。対応点設定部４８は対応点候補及び縮小パッチ（大）のデータを基に、参照画像の縮小画像の対応点候補の位置のみに関して、縮小パッチ（大）を用いた相関計算を行い、相関が最も強い点を縮小画像における対応点として設定する。対応箇所設定部４９は、縮小比率及び対応点設定部４８で設定された対応点のデータを基に、縮小画像における対応点の位置から通常画像上の対応箇所を計算する。小パッチ設定部５０は、通常画像及び計測位置（回帰）のデータに基づいて、元画像において小さなパッチを設定する。通常画像対応点検出部５１は、通常画像、対応箇所及び小パッチ設定部５０で設定されたパッチのデータに基づいて、参照画像におけるエピポーラライン上の対応箇所近傍のみに関して、同パッチを用いた相関計算によって回帰対応点を検出する。参照画像におけるエピポーララインは、エピポーラライン設定部４１で計算されたものを使用できる。
【０１０５】つまり、第２の段階的対応点探索部６４は、通常画像（元画像と参照画像）、元画像と参照画像の各縮小画像、通常画像の計測位置（回帰）及び計測データを基に、サイズの異なる２段階のパッチ（縮小パッチ（小）と縮小パッチ（大））を用い、縮小画像において縮小パッチ（小）により対応点候補を抽出し、縮小パッチ（大）により対応点候補から対応点を決定し、次いで、通常画像において対応箇所近傍のみに関してパッを用いた相関計算により回帰対応点を検出する。
【０１０６】回帰距離計算部６５は、元画像の計測位置と入れ換え設定後の参照画像（入れ換え設定前の元画像）の回帰対応点との距離、つまり、回帰距離を計算するものである。
【０１０７】探索結果判断部６６は、回帰距離を基に第１の段階的対応点探索部６１による対応点探索結果の是非を判断するものであり、例えば、回帰距離が所定範囲内であれば、第１の段階的対応点探索部６１で検出した対応点が適切(YES) であると判断する。所定範囲外であれば不適切(NO)であると判断する。
【０１０８】かくして、この「段階的対応点探索装置２」では、サイズの異なる２段階のパッチ（縮小パッチ（小）と縮小パッチ（大））を用いて通常画像の対応点を探索する処理を回帰的に行う。つまり、縮小画像において縮小パッチ（小）を用いて対応点候補を抽出し、縮小パッチ（大）を用いて対応点候補から対応点を決定し、次いで、通常画像において対応箇所近傍のみに関して対応点を検出するという処理を回帰的に行い、対応点探索結果の是非を判断するため、対応点間違いを強く排除し、より信頼性のある対応点を得ることができる。つまり、サイズの異なる２段階のパッチを用いて対応点探索を回帰的に行うため、信頼性のある対応点を得ることができる。
【０１０９】ここで、第１の段階定対応点探索部６１における縮小パッチ（小）及び縮小パッチ（大）と、第２の段階定対応点探索部６４における縮小パッチ（小）及び縮小パッチ（大）は、通常、対応するもの同士が同じ大きさにされるが、必ずしも同じ必要はなく、縮小パッチ（小）同士、縮小パッチ（大）同士で大きさが違っていても所期の目的は果たされる。
【０１１０】通常画像のデータ及び縮小画像のデータは、図２１や図２４に示す三次元位置計測装置の画像メモリ８４から供給される。また、縮小比率、カメラデータ、探索結果判断用の基準（例えば、回帰距離に対する所定範囲内）等のデータはパラメータメモリ８２から、元画像の計測位置のデータは計測位置指定部８３からそれぞれ供給される。
【０１１１】［対応点探索装置３］図１９を参照して、本発明の実施形態例に係る段階的対応点探索装置として、図９により説明した上記「段階的対応点探索方法３」を実現する装置を説明する。以降、本例の装置を「段階的対応点探索装置３」と呼ぶ。
【０１１２】図１９に示すように、当該「段階的対応点探索装置３」は、第１の縮小画像対応点探索処理部４０ａ、第２の縮小画像対応点探索処理部４０ｂ、元画像・参照画像設定入れ換え部７１、計測位置（回帰）設定部７２、回帰距離計算部７３、探索結果判断部７４、対応箇所設定部７５、小パッチ設定部７６及び通常画像対応点検出部７７を有している。計測データとしては、元画像の計測位置、カメラデータ、縮小比率（縮小データ）、探索結果判断用の基準（例えば、回帰距離に対する範囲）等が与えられる。
【０１１３】第１の縮小画像対応点探索処理部４０ａは図６により説明した上記「縮小画像対応点探索処理」を実現する装置であり、縮小画像において、縮小パッチ（小）を用いて対応点候補を抽出し、次に、縮小パッチ（大）を用いて対応点候補から対応点を決定するという、サイズの異なる２段階のパッチ（縮小パッチ（小）と縮小パッチ（大））を用いて縮小画像について対応点探索を行う。
【０１１４】第１の縮小画像対応点探索処理部４０ａは、図１７に示した縮小画像対応点探索処理部４０と同じ構成のものが使用でき、その場合、図１７を参照すれば、エピポーラライン設定部４１と、計測点変換部４２と、エピポーラライン変換部４３と、縮小パッチ（小）設定部４４と、相関値グラフ作成部４５と、対応点候補抽出部４６と、縮小パッチ（大）設定部４７と、対応点設定部４８からなる。
【０１１５】第１の縮小画像対応点探索処理部４０ａの機能を、図１７を参照して説明する。エピポーラライン設定部４１にて、通常画像における計測位置のデータとカメラデータを基に、通常画像におけるエピポーララインを計算し、設定する。計測点変換部４２にて、縮小比率及び通常画像の計測位置のデータに基づいて、通常画像の計測位置から縮小画像における計測位置（縮小）を計算する。エピポーラライン変換部４３にて、縮小比率及びエピポーラライン設定部４１により設定された通常画像のエピポーララインのデータに基づいて、通常画像のエピポーララインから、縮小画像におけるエピポーラライン（縮小）を計算する。縮小パッチ（小）設定部４４にて、縮小画像、縮小比率及び計測点変換部４２で計算される計測位置（縮小）のデータに基づいて、元画像の縮小画像において縮小比率に対応するサイズの縮小パッチ（小）を設定する。相関値グラフ作成部４５にて、縮小画像、計測位置（縮小）、エピポーラライン（縮小）及び縮小パッチ（小）のデータを基に、参照画像の縮小画像におけるエピポーラライン（縮小）上の探索範囲に関して、縮小パッチ（小）を用いた相関計算を行い、相関値グラフを作成する。対応点候補抽出部４６は相関値グラフから対応点候補を上記「対応点候補抽出方法」等により抽出するものであり、例えば図３１に示した構成のものが用いられる。縮小パッチ（大）設定部４７は、縮小画像、縮小比率及び計測位置（縮小）のデータに基づいて、元画像の縮小画像において縮小比率に対応するサイズの縮小パッチ（大）を設定する。対応点設定部４８にて、対応点候補及び縮小パッチ（大）のデータを基に、参照画像の縮小画像の対応点候補の位置のみに関して、縮小パッチ（大）を用いた相関計算を行い、相関が最も強い点を縮小画像における対応点として設定する。
【０１１６】元画像・参照画像設定入れ換え部７１は、元画像と参照画像の設定を入れ換えるものである。即ち、第１の縮小画像対応点探索処理部４０ａで対応点が検出された後、元画像を参照画像に、参照画像を元画像に再設定する。
【０１１７】計測位置（回帰）設定部７２は、第１の縮小画像対応点探索処理部４０ｂで検出した対応点を計測位置（回帰）として、入れ換え設定された元画像に設定するものである。
【０１１８】第２の縮小画像対応点探索処理部４０ｂは図６により説明した上記「縮小画像対応点探索処理」を回帰的に行うための装置であり、元画像と参照画像の設定が元画像・参照画像設定入れ換え部７１により入れ換えられ、かつ、入れ換え設定された元画像に計測位置（回帰）設定部７２により計測位置（回帰）が設定された状態で、縮小画像において、縮小パッチ（小）を用いて対応点候補を抽出し、次に、縮小パッチ（大）を用いて対応点候補から回帰対応点を決定するという、サイズの異なる２段階のパッチ（縮小パッチ（小）と縮小パッチ（大））を用いて縮小画像について回帰対応点探索を行う。
【０１１９】従って、第２の縮小画像対応点探索処理部４０ｂも、図１７に示した縮小画像対応点探索処理部４０と同じ構成のものが使用でき、その場合は、図１７を参照すれば、エピポーラライン設定部４１と、計測点変換部４２と、エピポーラライン変換部４３と、縮小パッチ（小）設定部４４と、相関グラフ作成部４５と、対応点候補抽出部４６と、縮小パッチ（大）設定部４７と、対応点設定部４８からなる。
【０１２０】第２の縮小画像対応点探索処理部４０ｂの機能を、図１７を参照して説明する。回帰処理においては、エピポーラライン設定部４１は、通常画像における計測位置（回帰）のデータとカメラデータを基に、通常画像におけるエピポーララインを計算し、設定する。計測点変換部４２は、縮小比率及び通常画像の計測位置のデータに基づいて、通常画像の計測位置（回帰）から縮小画像における計測位置（回帰・縮小）を計算する。従って、前記計測位置（回帰）設定部７２と第２の縮小画像対応点探索処理部４０ｂにおける計測点変換部４２により、第１の縮小画像対応点探索処理部４０ａで検出された対応点が、入れ換え設定された後の元画像の縮小画像における計測位置（回帰・縮小）として設定される。エピポーラライン変換部４３は、縮小比率及びエピポーラライン設定部４１により設定された通常画像のエピポーララインのデータに基づいて、通常画像のエピポーララインから、縮小画像におけるエピポーラライン（縮小）を計算する。縮小パッチ（小）設定部４４は、縮小画像、縮小比率及び計測点変換部４２で計算される計測位置（回帰・縮小）のデータに基づいて、元画像の縮小画像において縮小比率に対応するサイズの縮小パッチ（小）を設定する。相関値グラフ作成部４５は、縮小画像、計測位置（縮小）、エピポーラライン（縮小）及び縮小パッチ（小）のデータを基に、参照画像の縮小画像におけるエピポーラライン（縮小）上の探索範囲に関して、縮小パッチ（小）を用いた相関計算を行い、相関値グラフを作成する。対応点候補抽出部４６は、相関値グラフから対応点候補を上記「対応点候補抽出方法」等により抽出するものであり、例えば図３１に示した構成のものが用いられる。縮小パッチ（大）設定部４７は、縮小画像、縮小比率及び計測位置（回帰・縮小）のデータに基づいて、元画像の縮小画像において縮小比率に対応するサイズの縮小パッチ（大）を設定する。対応点設定部４８は、対応点候補及び縮小パッチ（大）のデータを基に、参照画像の縮小画像の対応点候補の位置に関して、縮小パッチ（大）を用いた相関計算を行い、相関が最も強い点を縮小画像における回帰対応点として設定する。
【０１２１】回帰距離計算部７３は、元画像の縮小画像における計測位置（回帰・縮小）と入れ換え設定後の参照画像の縮小画像（入れ換え設定前の元画像の縮小画像）における回帰対応点との距離、つまり、回帰距離（縮小）を計算する。
【０１２２】探索結果判断部７４は、回帰距離（縮小）を基に第１の縮小画像探索処理部４０ａによる対応点探索結果の是非を判断するものであり、例えば、回帰距離（縮小）が所定範囲内であれば、第１の縮小画像探索処理部４０ａで検出した対応点が適切(YES) であると判断する。所定範囲外であれば不適切(NO)であると判断する。
【０１２３】対応箇所設定部７５は、縮小比率及び縮小画像対応点探索処理部４０ａで検出された対応点のデータを基に、縮小画像における対応点の位置から通常画像上の対応箇所を計算するものである。小パッチ設定部７６は、通常画像及び計測位置のデータに基づいて、元画像において適当な大きさのパッチを設定するものである。通常画像対応点検出部７７は、通常画像、対応箇所及び小パッチ設定部７６で設定されたパッチのデータに基づいて、参照画像上におけるエピポーラライン上の対応箇所近傍のみに関して、同パッチを用いた相関計算によって対応点を検出するものである。参照画像におけるエピポーララインは、エピポーラライン設定部４１で計算されたものを使用できる。
【０１２４】かくして、この「段階的対応点探索装置３」では、第１の縮小画像対応点探索処理部４０ａにて、縮小画像において、縮小パッチ（小）を用いて対応点候補を抽出し、縮小パッチ（大）を用いて対応点候補から対応点を決定するという、サイズの異なる２段階のパッチ（縮小パッチ（小）と縮小パッチ（大））を用いて対応点探索を行い、更に、元画像と参照画像野設定を入れ換え、かつ、計測位置（回帰・縮小）を元画像の縮小画像に設定し、次いで、第２の縮小画像対応点探索処理部４０ｂにて、縮小画像において、縮小パッチ（小）を用いて対応点候補を抽出し、縮小パッチ（大）を用いて対応点候補から回帰対応点を決定するという、サイズの異なる２段階のパッチ（縮小パッチ（小）と縮小パッチ（大））を用いて回帰処理を行い、回帰距離（縮小）を計算して縮小画像における対応点探索の是非を判断し、これが適切な場合のみ、対応箇所設定部７５、小パッチ設定部７６及び通常画像対応点検出部７７により、通常画像において対応箇所近傍のみに関して対応点を検出するため、対応点間違いを強く排除し、より信頼性のある対応点を得ることができる。また、サイズの異なる２段階のパッチを用いた回帰的な対応点探索処理を縮小画面のみに対して行い対応点の是非を判断するため、処理の速い段階において対応点の是非を得ることができる。更に、対応点が適切と判断された場合は、続けて、縮小画像における処理で検出された対応点近傍のみについて通常画像で対応点探索を行うため、従来方法と同程度の検出精度を得ることができる。また、処理時間が短縮する。
【０１２５】ここで、第１の縮小画像対応点探索部４０ａにおける縮小パッチ（小）及び縮小パッチ（大）と、第２の縮小画像対応点探索部４０ｂにおける縮小パッチ（小）及び縮小パッチ（大）は、通常、対応するもの同士が同じ大きさにされるが、必ずしも同じ必要はなく、縮小パッチ（小）同士、縮小パッチ（大）同士で大きさが違っていても所期の目的は果たされる。
【０１２６】通常画像のデータ及び縮小画像のデータは、図２２や図２５に示す三次元位置計測装置の画像メモリ８４から供給される。また、縮小比率、カメラデータ、探索結果判断用の基準（例えば、回帰距離に対する所定範囲内）等のデータはパラメータメモリ８２から、元画像の計測位置のデータは計測位置指定部８３からそれぞれ供給される。
【０１２７】［三次元位置計測装置１］図２０を参照して、本発明の実施形態例に係る三次元位置計測装置１として、上記「三次元位置計測方法１」を実現する装置を説明する。図２０は本実施形態例に係る「三次元位置計測装置１」を示すブロック図である。
【０１２８】図２０に示すように、当該「三次元位置計測装置１」は、画像メモリ８１、パラメータメモリ８２、計測位置指定部８３、画像入力部８４、画像縮小部８５、段階的対応点探索部８６及び三次元位置計算部８７を有している。
【０１２９】これらのうち、画像メモリ８１は、画像入力部８４を介して供給される通常画像のデータを記憶すると共に、画像縮小部８５を介して供給される縮小画像のデータも記憶しておくものである。
【０１３０】画像縮小部８５は、画像メモリ８１から供給される通常画像のデータと、パラメータメモリ８２から供給される各種計測データのうち縮小比率に基づき、所定の縮小画像のデータを作成し、このデータを画像メモリ８１に記憶させる。なお、計測データには、縮小比率、カメラデータ等が含まれる。
【０１３１】パラメータメモリ８２は、縮小比率のデータ及びカメラデータ等、当該三次元位置計測に必要なデータを、パラメータとして記憶している。
【０１３２】計測位置指定部８３は通常画像（元画像）に所望の計測位置を指定することができるようになっている。
【０１３３】段階的対応点探索部８６は、図１７に示した上記「段階的対応点探索装置１」と同じものであり、上記「段階的対応点探索方法１」を実現する。要すれば、縮小画像において縮小パッチ（小）を用いて対応点候補を抽出し、縮小パッチ（大）を用いて対応点候補から対応点を決定するという、サイズの異なる２段階のパッチ（縮小パッチ（小）と縮小パッチ（大））を用いて対応点探索を行い、次に、通常画像において対応箇所近傍のみに関して、適当な小パッチを用いた相関計算で対応点を検出する。
【０１３４】三次元位置計算部７７は、対応点のデータ、計測位置のデータ及びカメラデータに基づき、対象物の三次元位置を計算により求めるものである。
【０１３５】かくして、本実施形態例の「三次元位置計測装置１」は、左右画像を入力し、左右画像から左右縮小画像を作り、計測位置を通常画像の一方で指定し、縮小画像において縮小パッチ（小）を用いて対応点候補を抽出し、縮小パッチ（大）を用いて対応点候補から対応点を決定するという、サイズの異なる２段階のパッチ（縮小パッチ（小）と縮小パッチ（大））を用いて対応点探索を行い、次に、通常画像において対応箇所近傍のみに関して、適当な小パッチを用いた相関計算で対応点を検出し、この対応点と、計測位置及びカメラデータから三次元位置を計算する。
【０１３６】このように当該「三次元位置計測装置１」においては、対応点探索において上記「三次元位置計測方法１」（図１０参照）を実現し、その対応点データを用いて三次元位置計算を行うため、従来に比べ、信頼性のある三次元位置計測結果を得ることができる。
【０１３７】［三次元位置計測装置２］図２１を参照して、本発明の実施形態例に係る三次元位置計測装置２として、上記［三次元位置計測方法２」を実現する装置を説明する。図２１は本実施形態例に係る「三次元位置計測装置２」を示すブロック図である。
【０１３８】図２１に示すように、当該「三次元位置計測装置２」は、図２０に示した「三次元位置計測装置１」に対し、段階的対応点探索部８６に代えて、上記「段階的対応点探索方法２」を実現する段階的対応点探索部８８を用いたものである。この段階的対応点探索部８８は、図１８に示した上記「段階的対応点探索装置２」と同じものである。
【０１３９】即ち、図２１に示すように、当該「三次元位置計測装置２」は、画像メモリ８１、パラメータメモリ８２、計測位置指定部８３、画像入力部８４、画像縮小部８５、段階的対応点探索部８８及び三次元位置計算部８７を有している。
【０１４０】これらのうち、画像メモリ８１は、画像入力部８４を介して供給される通常の画像データを記憶すると共に、画像縮小部８５を介して供給される縮小画像のデータを記憶しておく。画像縮小部８５は、画像メモリ８１から供給される通常画像のデータと、パラメータメモリ８２から供給される計測データのうち縮小比率に基づき、所定の縮小画像のデータを作成し、このデータを画像メモリ８１に記憶させる。計測データには、縮小比率、カメラデータ、回帰距離の所定範囲等が含まれる。パラメータメモリ８２は、縮小比率のデータ及びカメラデータ、回帰距離の所定範囲等、当該三次元位置計測に必要なデータを、パラメータとして記憶している。計測位置指定部８３は通常画像に所望の計測位置を指定することができるようになっている。
【０１４１】段階的対応点探索部８８は、要すれば、縮小画像において縮小パッチ（小）を用いて対応点候補を抽出し、縮小パッチ（大）を用いて対応点候補から対応点を決定し、次いで、通常画像において対応箇所近傍のみに関して対応点を検出するという処理を回帰的に行い、対応点探索結果の是非を判断する。対応点が不適切(NO)であれば、処理を中断する。
【０１４２】三次元位置計算部８７は、段階的対応点探索部８８において対応点が不適切(NO)であると判断された場合は、三次元位置計測を中断し、対応点が適切(YES) であると判断された場合は、この対応点のデータ、計測位置のデータ及びカメラデータに基づき、対象物の三次元位置を計算により求める。
【０１４３】かくして、本実施形態例の「三次元位置計測装置２」は、左右画像を入力し、左右画像から左右縮小画像を作り、計測位置を通常画像の一方で指定し、上記「段階的対応点探索方法２」により対応点を検出し、この対応点探索において対応点が不適切(NO)であればここで処理を中断し、適切な場合 (YES)は計測位置、対応点、カメラデータから三次元位置を計算する。
【０１４４】このように当該「三次元位置計測装置２」においては、対応点探索において上記「三次元位置計測方法２」（図１１参照）を実現し、その対応点のデータを用いて三次元位置計算を行うため、従来に比べ、信頼性のある三次元位置計測結果を得ることができる。
【０１４５】［三次元位置計測装置３］図２２を参照して、本発明の実施形態例に係る三次元位置計測装置３として、上記［三次元位置計測方法３」を実現する装置を説明する。図２２は本実施形態例に係る「三次元位置計測装置３」を示すブロック図である。
【０１４６】図２２に示すように、当該「三次元位置計測装置２」は、図２０に示した「三次元位置計測装置１」に対し、段階的対応点探索部８６に代えて、上記「段階的対応点探索方法３」を実現する段階的対応点探索部８９を用いたものである。この段階的対応点探索部８９は図１９に示した上記「段階的対応点探索装置３」と同じものである。
【０１４７】即ち、図２２に示すように、当該「三次元位置計測装置３」は、画像メモリ８１、パラメータメモリ８２、計測位置指定部８３、画像入力部８４、画像縮小部８５、段階的対応点探索部８９及び三次元位置計算部８７を有している。
【０１４８】これらのうち、画像メモリ８１は、画像入力部８４を介して供給される通常の画像データを記憶すると共に、画像縮小部８５を介して供給される縮小画像のデータを記憶しておく。画像縮小部８５は、画像メモリ８１から供給される通常画像のデータとパラメータメモリ８２から供給される計測データのうち縮小比率に基づき、所定の縮小画像のデータを作成し、このデータを画像メモリ８１に記憶させる。計測データには、縮小比率、カメラデータ、回帰距離の所定範囲等が含まれる。パラメータメモリ８２は、縮小比率のデータ及びカメラデータ、回帰距離の所定範囲等、当該三次元位置計測に必要なデータを、パラメータとして記憶している。計測位置指定部８３は通常画像に所望の計測位置を指定することができるようになっている。
【０１４９】段階的対応点探索部８９は、要すれば、縮小パッチ（小）を用いて対応点候補を抽出し、縮小パッチ（大）を用いて対応点候補から対応点を決定するという、サイズの異なる２段階のパッチ（縮小パッチ（小）と縮小パッチ（大））を用いて対応点探索を行い、更に、元画像と参照画像野設定を入れ換え、かつ、計測位置（回帰・縮小）を元画像の縮小画像に設定し、次いで、縮小画像において、縮小パッチ（小）を用いて対応点候補を抽出し、縮小パッチ（大）を用いて対応点候補から回帰対応点を決定するという、サイズの異なる２段階のパッチ（縮小パッチ（小）と縮小パッチ（大））を用いて回帰処理を行い、回帰距離（縮小）を計算して縮小画像における対応点探索の是非を判断し、これが適切な場合のみ、通常画像において対応箇所近傍のみに関して対応点を検出する。
【０１５０】三次元位置計算部８７は、段階的対応点探索部８９において縮小画像での対応点が不適切(NO)であると判断された場合は、三次元位置計測を中断し、適切(YES) であると判断された場合に、段階的対応点探索部８９で検出された対応点のデータ、計測位置のデータ及びカメラデータに基づき、対象物の三次元位置を計算により求める。
【０１５１】かくして、本実施形態例の「三次元位置計測装置３」は、左右画像を入力し、左右画像から左右縮小画像を作り、計測位置を通常画像の一方で指定し、上記「段階的対応点探索方法３」により対応点を検出し、この対応点探索において対応点が不適切(NO)であればここで処理を中断し、適切な場合 (YES)に計測位置、対応点、カメラデータから三次元位置を計算する。
【０１５２】このように当該「三次元位置計測装置３」においては、対応点探索において上記「三次元位置計測方法３」（図１２参照）を実現し、その対応点のデータを用いて三次元位置計算を行うため、従来に比べ、信頼性のある三次元位置計測結果を得ることができる。
【０１５３】［三次元位置計測装置４］図２３を参照して、本発明の実施形態例に係る三次元位置計測装置４として、上記［三次元位置計測方法４」を実現する装置を説明する。図２３は本実施形態例に係る「三次元位置計測装置４」を示すブロック図である。
【０１５４】図２３に示すように、当該「三次元位置計測装置４」は、図２０に示した「三次元位置計測装置１」に対し、対応点実数化部９０を追加したものである。従って、図２３中で、図２０と同一部分には同一符号を付し、重複する説明を省略する。
【０１５５】対応点実数化部９０は、例えば上記「直線型対応点実数化方式」あるいは「二次曲線型対応点実数化方式」等、対応点補間演算の計算を実行する。
【０１５６】即ち、上記「直線型対応点実数化方式」の計算を実行する場合は、対応点実数化部７９は、入力画像におけるモデルとの対応点の位置Ａr ＝Ａ0 −（１／２）（Ｃ-1−Ｃ+1）／（Ｃ0 −Ｃ-1）又はＡr ＝Ａ0 ＋（１／２）（Ｃ+1−Ｃ-1）／（Ｃ0 −Ｃ+1）（但し、Ａ0 は相関が最も強い第１の点の位置、Ｃ0 は同第１の点での相関値、Ｃ-1は第１の点を含む一次元上で第１の点の直前に位置する第２の点での相関値、Ｃ+1は同一次元上で第１の点の直後に位置する第３の点での相関値）の演算の演算を実行し、この結果である実数化対応点のデータを三次元位置計算部８７に供給する。
【０１５７】また、上記「二次曲線型対応点実数化方式」の計算を実行する場合は、対応点実数化部９０は、図１３に模式的に示したように、対応点探索で得られた点を中心に幾つかの近傍点（３点以上）の相関値データを二次曲線に近似し、得られた二次曲線のピークの位置を対応点とする演算を実行し、この結果である実数化対応点のデータを三次元位置計算部８７に供給する。
【０１５８】かくして、本実施形態例の「三次元位置計測装置４」は、左右画像を入力し、左右画像から左右縮小画像を作り、計測位置を通常画像の一方で指定し、「段階的対応点探索方法１」により対応点を検出し、更に対応点実数化方式により対応点を再計算し、計測位置、再計算で得た対応点、カメラデータから三次元位置を計算する。
【０１５９】このように当該「三次元位置計測装置４」においては、対応点探索において上記「三次元位置計測方法４」（図１４参照）を実現している。つまり、上記「三次元位置計測装置１」に加えて、三次元位置計算を行う前に上記「直線型対応点実数化方式」や上記「二次曲線型対応点実数化方式」等の対応点実数化処理による対応点再計算を行い、実数化処理した対応点のデータを用いて三次元位置計算を行うため、従来に比べ、高精度かつ信頼性のある位置計測結果を得ることができる。
【０１６０】［三次元位置計測装置５］図２４を参照して、本発明の実施形態例に係る「三次元位置計測装置５」として、上記［三次元位置計測方法５」を実現する装置を説明する。図２４は本実施形態例に係る「三次元位置計測装置５」を示すブロック図である。
【０１６１】図２４に示すように、当該「三次元位置計測装置５」は、図２１に示した「三次元位置計測装置２」に対し、対応点実数化部９０を追加したものである。従って、図２４中で、図２１と同一部分には同一符号を付し、重複する説明を省略する。
【０１６２】対応点実数化部９０は上述したとおり、例えば上記「直線型対応点実数化方式」あるいは「二次曲線型対応点実数化方式」等、対応点補間演算の計算を実行し、この結果である実数化対応点のデータを三次元位置計算部８７に供給する。
【０１６３】かくして、本実施形態例の「三次元位置計測装置５」は、左右画像を入力し、左右画像から左右縮小画像を作り、計測位置を通常画像の一方で指定し、「段階的対応点探索方法３」により対応点を検出し、この対応点探索において対応点が不適切(NO)であればここで処理を中断し、適切な場合 (YES)は対応点実数化方式により対応点を再計算し、計測位置、再計算で得た対応点、カメラデータから三次元位置を計算する。
【０１６４】このように当該「三次元位置計測装置５」においては、対応点探索において上記「三次元位置計測方法５」（図１５参照）を実現している。つまり、上記「三次元位置計測装置２」に加えて、三次元位置計算を行う前に上記「直線型対応点実数化方式」や上記「二次曲線型対応点実数化方式」等の対応点実数化処理により対応点の再計算を行い、実数化処理した対応点のデータを用いて三次元位置計算を行うため、従来に比べ、高精度かつ信頼性のある位置計測結果を得ることができる。
【０１６５】［三次元位置計測装置６］図２５を参照して、本発明の実施形態例に係る「三次元位置計測装置６」として、上記［三次元位置計測方法６」を実現する装置を説明する。図２５は本実施形態例に係る「三次元位置計測装置６」を示すブロック図である。
【０１６６】図２５に示すように、当該「三次元位置計測装置５」は、図２２に示した「三次元位置計測装置３」に対し、対応点実数化部９０を追加したものである。従って、図２５中で、図２２と同一部分には同一符号を付し、重複する説明を省略する。
【０１６７】対応点実数化部９０は上述したとおり、例えば上記「直線型対応点実数化方式」あるいは「二次曲線型対応点実数化方式」等、対応点補間演算の計算を実行し、この結果である実数化対応点のデータを三次元位置計算部８７に供給する。
【０１６８】かくして、本実施形態例の「三次元位置計測装置６」は、左右画像を入力し、左右画像から左右縮小画像を作り、計測位置を通常画像の一方で指定し、「段階的対応点探索方法３」により対応点を検出し、この対応点探索において対応点が不適切(NO)であればここで処理を中断し、適切な場合 (YES)は対応点実数化方式により対応点を再計算し、計測位置、再計算で得た対応点、カメラデータから三次元位置を計算する。
【０１６９】このように当該「三次元位置計測装置６」においては、対応点探索において上記「三次元位置計測方法６」（図１６参照）を実現している。つまり、上記「三次元位置計測装置３」に加えて、三次元位置計算を行う前に上記「直線型対応点実数化方式」や上記「二次曲線型対応点実数化方式」等の対応点実数化処理により対応点の再計算を行い、実数化処理した対応点のデータを用いて三次元位置計算を行うため、従来に比べ、高精度かつ信頼性のある位置計測結果を得ることができる。
【０１７０】上述した各装置、つまり、図１７の「段階的対応点探索装置１」、図１８の「段階的対応点探索装置２」、図１９の「段階的対応点探索装置３」、図２０の「三次元位置計測装置１」、図２１の「三次元位置計測装置２」、図２２の「三次元位置計測装置３」、図２３の「三次元位置計測装置４」、図２４の「三次元位置計測装置５」、図２５の「三次元位置計測装置６」、図３１の「対応点候補抽出装置」は、いずれもコンピュータとその処理を実現するソフトウェア（コンピュータプログラム）により実現可能である。これらのソフトウェアはフロッピーディスクやCD-ROM等の適宜な記録媒体に記録しておく。
【０１７１】［記録媒体１］本発明の実施形態例に係る「記録媒体１」として、図１７に示した「段階的対応点探索装置１」をコンピュータで実現するための記録媒体を説明する。当該記録媒体には、図６と図７を参照して説明した上記「段階的対応点探索方法１」を実現するソフトウェアを記録しておき、これをコンピュータに読み込ませて実行する。具体的には、上記「段階的対応点探索方法１」の手順をコンピュータプログラムとして、コンピュータが読み込み可能なデータ形式で記録媒体に記録する。
【０１７２】［記録媒体２］本発明の実施形態例に係る「記録媒体２」として、図１８に示した「段階的対応点探索装置２」をコンピュータで実現するための記録媒体を説明する。当該記録媒体には、図８を参照して説明した上記「段階的対応点探索方法２」を実現するソフトウェアを記録しておき、これをコンピュータに読み込ませて実行する。具体的には、上記「段階的対応点探索方法２」の手順をコンピュータプログラムとして、コンピュータが読み込み可能なデータ形式で記録媒体に記録する。
【０１７３】［記録媒体３］本発明の実施形態例に係る「記録媒体３」として、図１９に示した「段階的対応点探索装置３」をコンピュータで実現するための記録媒体を説明する。当該記録媒体には、図９を参照して説明した上記「段階的対応点探索方法３」を実現するソフトウェアを記録しておき、これをコンピュータに読み込ませて実行する。具体的には、上記「段階的対応点探索方法３」の手順をコンピュータプログラムとして、コンピュータが読み込み可能なデータ形式で記録媒体に記録する。
【０１７４】［記録媒体４］本発明の実施形態例に係る「記録媒体４」として、図２０に示した「三次元位置計測装置１」をコンピュータで実現するための記録媒体を説明する。当該記録媒体には、図１０を参照して説明した上記「三次元位置計測方法１」を実現するソフトウェアを記録しておき、これをコンピュータに読み込ませて実行する。具体的には、上記「三次元位置計測方法１」の手順をコンピュータプログラムとして、コンピュータが読み込み可能なデータ形式で記録媒体に記録する。
【０１７５】［記録媒体５］本発明の実施形態例に係る「記録媒体５」として、図２１に示した「三次元位置計測装置２」をコンピュータで実現するための記録媒体を説明する。当該記録媒体には、図１１を参照して説明した上記「三次元位置計測方法２」を実現するソフトウェアを記録しておき、これをコンピュータに読み込ませて実行する。具体的には、上記「三次元位置計測方法１」の手順をコンピュータプログラムとして、コンピュータが読み込み可能なデータ形式で記録媒体に記録する。
【０１７６】［記録媒体６］本発明の実施形態例に係る「記録媒体６」として、図２２に示した「三次元位置計測装置３」をコンピュータで実現するための記録媒体を説明する。当該記録媒体には、図１２を参照して説明した上記「三次元位置計測方法３」を実現するソフトウェアを記録しておき、これをコンピュータに読み込ませて実行する。具体的には、上記「三次元位置計測方法３」の手順をコンピュータプログラムとして、コンピュータが読み込み可能なデータ形式で記録媒体に記録する。
【０１７７】［記録媒体７］本発明の実施形態例に係る「記録媒体７」として、図２３に示した「三次元位置計測装置４」をコンピュータで実現するための記録媒体を説明する。当該記録媒体には、図１４を参照して説明した上記「三次元位置計測方法４」を実現するソフトウェアを記録しておき、これをコンピュータに読み込ませて実行する。具体的には、上記「三次元位置計測方法４」の手順をコンピュータプログラムとして、コンピュータが読み込み可能なデータ形式で記録媒体に記録する。
【０１７８】［記録媒体８］本発明の実施形態例に係る「記録媒体８」として、図２４に示した「三次元位置計測装置５」をコンピュータで実現するための記録媒体を説明する。当該記録媒体には、図１５を参照して説明した上記「三次元位置計測方法５」を実現するソフトウェアを記録しておき、これをコンピュータに読み込ませて実行する。具体的には、上記「三次元位置計測方法５」の手順をコンピュータプログラムとして、コンピュータが読み込み可能なデータ形式で記録媒体に記録する。
【０１７９】［記録媒体９］本発明の実施形態例に係る「記録媒体９」として、図２５に示した「三次元位置計測装置６」をコンピュータで実現するための記録媒体を説明する。当該記録媒体には、図１６を参照して説明した上記「三次元位置計測方法６」を実現するソフトウェアを記録しておき、これをコンピュータに読み込ませて実行する。具体的には、上記「三次元位置計測方法６」の手順をコンピュータプログラムとして、コンピュータが読み込み可能なデータ形式で記録媒体に記録する。
【０１８０】［記録媒体１０］本発明の実施形態例に係る「記録媒体１０」として、図３１に示した「対応点抽出装置」をコンピュータで実現するための記録媒体を説明する。当該記録媒体には、図２を参照して説明した上記「対応点抽出方法」を実現するソフトウェアを記録しておき、これをコンピュータに読み込ませて実行する。具体的には、上記「対応点抽出方法」の手順を候補配列を用意することを含めてコンピュータプログラムとして、コンピュータが読み込み可能なデータ形式で記録媒体に記録する。
【０１８１】［他の実施形態例］図示しないが、通常画像のみについて小パッチと大パッチを用いて対応点を検出する処理を回帰的に行う段階的対応点探索も可能である。この方法を「段階的対応点探索方法４」と呼ぶ。具体的には、第１段階として、２つの通常画像のうち、一方を元画像、もう一方参照画像として設定し、元画像上に適宜な計測位置を指定し、この計測位置にて元画像に小パッチを設定し、参照画像のエピポーララインの探索範囲上でこの小パッチを用いて相関計算により相関値グラフを作成し、この相関値グラフから上記「対応点候補抽出方法」等により対応点候補を抽出し、その後、元画像に大パッチを設定し、参照画像の対応点候補の位置のみに関して大パッチを用いた相関計算により最も相関の強い点を対応点として検出する。次に、元画像を参照画像に、参照画像を元画像にと設定関係を入れ換え、先に検出した対応点を元画像に計測位置（回帰）として設定する。そして、この計測位置（回帰）にて元画像に小パッチを設定し、参照画像のエピポーララインの探索範囲上でこの小パッチを用いて相関計算により相関値グラフを作成し、この相関値グラフから上記「対応点候補抽出方法」等により対応点候補を抽出し、その後、元画像に大パッチを設定し、参照画像の対応点候補の位置のみに関して大パッチを用いた相関計算により最も相関の強い点を回帰対応点として検出する。最後に、計測位置と回帰対応点との回帰距離を計算し、この回帰距離を基に先に検出した対応点が適切か否か対応点探索の是非を判断する。このように、「段階的対応点探索方法４」ではサイズの異なる２段階のパッチを用いて対応点探索を回帰的に行うため、通常画像のみ用いても対応点間違いを排除することができ、信頼性のある対応点を得ることができる。
【０１８２】この「段階的対応点探索方法４」の手順をコンピュータプログラムとして、コンピュータが読み込み可能なデータ形式で記録媒体に記録しておき、これをコンピュータに読み込ませて実行することにより、上記「段階的対応点探索方法４」を実現する段階的対応点探索装置が構成される。
【０１８３】上記「段階的対応点探索方法４」を利用して三次元位置計測を行うことも可能であり、この方法を「三次元位置計測方法７」と呼ぶ。具体的には、以下の手順で計測する。
(1) 左右画像を元画像及び参照画像として入力する。
(2) 計測位置を通常画像の一方（元画像）で指定する。
(3) 上記「段階的対応点探索方法４」で対応点探索を行い、対応点を得る。
(4) 手順(3) の上記「段階的対応点探索方法４」による処理で、回帰距離に基づいて対応点が不適切と判断された場合は、処理を中断する。
(5) 対応点が適切であると判断された場合は、対応点、計測位置及びカメラデータから三次元位置を計算する。あるいは、対応点が適切であると判断された場合、上記「直線型対応点実数化方式」または「二次曲線型対応点実数化方式」等の対応点実数化方式により、対応点の再計算を行い、この再計算した対応点、計測位置及びカメラデータから三次元位置を計算する。これにより、「三次元位置計測方法７」では上記「段階的対応点探索方法４」を用い、その対応点のデータを用いて三次元位置計測を行うため、信頼性のある位置計測結果を得ることができる。また、三次元位置計算を行う前に上記「直線型対応点実数化方式」や上記「二次曲線型対応点実数化方式」等の対応点実数化処理により対応点の再計算を行い、実数化処理した対応点のデータを用いて三次元位置計算を行う場合は、従来に比べ、高精度かつ信頼性のある位置計測結果を得ることができる。
【０１８４】この「三次元位置計測方法７」の手順をコンピュータプログラムとして、コンピュータが読み込み可能なデータ形式で記録媒体に記録しておき、これをコンピュータに読み込ませて実行することにより、上記上記「三次元位置計測方法７」を実現する段階的対応点探索装置が構成される。
【０１８５】
【発明の効果】本発明によれば、下記の効果がある。
(1) 対応点探索において、サイズの異なる２段階のパッチを用い、まず小パッチで複数の対応点候補を抽出し、次に大パッチで対応点候補の位置のみについて相関計算を行い対応点を決定することで、小パッチにおいて似通った画像パターンが存在していても、大パッチでは比較する領域を広げた分、異なる画像となるため、対応点間違いを排除できる。従って、検出した対応点の信頼性が高い。
(2) 対応点探索において、サイズの異なる２段階のパッチを用い、予め小パッチで対応点候補を抽出し、次に大パッチで対応点候補の位置のみについて相関計算を行い対応点を決定するため、単に大きなサイズのパッチのみ用いて対応点探索を行うよりも、計算量が減り高速な処理が実現できる。
(3) 対応点探索において、サイズの異なる２段階のパッチを用い、まず小パッチで対応点候補を抽出し、次に大パッチで対応点候補の位置のみについて相関計算を行い対応点を決定することにより、１つの計測位置に対して大小２種類の画像パターンで対応点を検出することになり、検出した対応点の信頼性が高い。
(4) 対応点探索において、サイズの異なる２段階のパッチのによる探索処理と回帰的な処理を組み合わせることで、更に効果的に対応点間違いを排除できる。
(5) 検出した対応点の信頼性が大きいため、位置計測方法又は装置としての信頼性が向上する。
(6) 対応点間違いによる不適切な位置計測結果を排除できるため、複数点の計測により、位置計測対象部品の全体としての位置計測精度が向上する。
(7) 位置計測対象部品の位置計測精度が向上するため、高精度位置決めを要する作業に対応できる。
【出願人】 【識別番号】０００００６１０５
【氏名又は名称】株式会社明電舎
【出願日】 平成１１年１１月１２日（１９９９．１１．１２）
【代理人】 【識別番号】１０００７８４９９
【弁理士】
【氏名又は名称】光石 俊郎 （外２名）
【公開番号】 特開２００１−１４１４２４（Ｐ２００１−１４１４２４Ａ）
【公開日】 平成１３年５月２５日（２００１．５．２５）
【出