(57)【特許請求の範囲】
【請求項１】
元画像の計測位置から参照画像のエピポーララインを設定し、元画像、参照画像、計測位置及び参照画像のエピポーララインから対応点を検出し、
元画像を参照画像に、参照画像を元画像に入れ換え設定し、
上記対応点を、計測位置（以降「計測位置（回帰）」と呼ぶ）として、入れ換え設定後の元画像に設定し、
計測位置（回帰）とカメラデータから入れ換え設定後の参照画像のエピポーララインを計算し、入れ換え設定後の元画像及び参照画像、並びに、計測位置（回帰）及び入れ換え設定後の参照画像のエピポーララインから対応点（以降「回帰対応点」と呼ぶ）を検出し、
計測位置と回帰対応点との距離（以降「回帰距離」と呼ぶ）を計算し、回帰距離を基に、上記対応点が適切か不適切か判断すること
を特徴とする回帰的対応点探索方法。
【請求項２】
元画像の計測位置とカメラデータから参照画像のエピポーララインを設定し、
元画像の計測位置から元画像の縮小画像における計測位置を計算すると共に参照画像のエピポーララインから参照画像の縮小画像におけるエピポーララインを設定し、元画像の縮小画像において縮小パッチを設定し、この縮小パッチを用いて、参照画像の縮小画像におけるエピポーラライン上の探索範囲に関して対応点（以降「対応点（縮小）」と呼ぶ）を検出し、この対応点（縮小）から参照画像上の対応点位置（以降「対応箇所」と呼ぶ）を計算し、元画像においてパッチを設定し、このパッチを用いて、参照画像のエピポーラライン上の対応箇所近傍のみに関して対応点を検出し、
元画像を参照画像に、参照画像を元画像に入れ換え設定し、
上記対応点を、計測位置（以降「計測位置（回帰）」と呼ぶ）として、入れ換え設定後の元画像に設定し、
計測位置（回帰）とカメラデータから入れ換え設定後の参照画像の縮小画像におけるエピポーララインを設定し、入れ換え設定後の元画像の縮小画像において縮小パッチを設定し、この縮小パッチを用いて、入れ換え設定後の参照画像の縮小画像におけるエピポーラライン上の探索範囲に関して対応点（以降「対応点（回帰・縮小）」と呼ぶ）を検出し、この対応点（回帰・縮小）から入れ換え設定後の参照画像上の対応点位置（以降「対応箇所（回帰）」と呼ぶ）を計算し、入れ換え設定後の元画像においてパッチを設定し、このパッチを用いて、入れ換え設定後の参照画像のエピポーラライン上の対応箇所（回帰）近傍のみに関して対応点（以降「回帰対応点」と呼ぶ）を検出し、
上記元画像の計測位置と上記回帰対応点との距離（以降「回帰距離」と呼ぶ）を計算し、回帰距離を基に、上記対応点が適切か不適切か判断すること
を特徴とする回帰的対応点探索方法。
【請求項３】
元画像の計測位置から元画像の縮小画像における計測位置を計算すると共に、参照画像のエピポーララインから参照画像の縮小画像におけるエピポーララインを設定し、
元画像の縮小画像において縮小パッチを設定し、この縮小パッチを用いて、参照画像の縮小画像におけるエピポーラライン上の探索範囲に関して対応点（以降「対応点（縮小）」と呼ぶ）を検出し、
元画像を参照画像に、参照画像を元画像に入れ換え設定し、
上記対応点（縮小）を、計測位置（以降「計測位置（回帰）」と呼ぶ）として、入れ換え設定後の元画像の縮小画像に設定し、
計測位置（回帰）とカメラデータから入れ換え設定後の参照画像の縮小画像におけるエピポーララインを設定し、
入れ換え設定後の元画像の縮小画像において縮小パッチを設定し、この縮小パッチを用いて、入れ換え設定後の参照画像の縮小画像におけるエピポーラライン上の探索範囲に関して対応点（以降「回帰対応点」と呼ぶ）を検出し、
上記元画像の縮小画像における計測位置と回帰対応点との距離（「以降「回帰距離（縮小）」と呼ぶ）を計算し、回帰距離（縮小）を基に、上記対応点（縮小）が適切か不適切か判断し、
上記対応点（縮小）が不適切であれば処理を中断し、
上記対応点（縮小）が適切であれば元画像と参照画像の設定を元に戻し、上記対応点（縮小）の位置から参照画像上の対応点位置（以降「対応箇所」と呼ぶ）を計算し、元画像においてパッチを設定し、このパッチを用いて参照画像のエピポーラライン上の対応箇所近傍のみに関して対応点を検出すること
を特徴とする回帰的対応点探索方法。
【請求項４】
左右画像を元画像及び参照画像として入力し、
左右画像から元画像及び参照画像の縮小画像を作り、
計測位置を元画像で指定し、
請求項２に記載する回帰的対応点探索方法により対応点を求め、
対応点探索結果が不適切であれば処理を中断し、適切であれば上記対応点、計測位置、カメラデータから三次元位置を計算することを特徴とする三次元位置計測方法。
【請求項５】
左右画像を元画像及び参照画像として入力し、
左右画像から元画像及び参照画像の縮小画像を作り、
計測位置を元画像で指定し、
請求項３に記載する回帰的対応点探索方法により対応点を求め、
対応点探索結果が不適切であれば処理を中断し、適切であれば上記対応点、計測位置、カメラデータから三次元位置を計算することを特徴とする三次元位置計測方法。
【請求項６】
左右画像を元画像及び参照画像として入力し、
左右画像から元画像及び参照画像の縮小画像を作り、
計測位置を元画像で指定し、
請求項２に記載する回帰的対応点探索方法により対応点を求め、
対応点探索結果が不適切であれば処理を中断し、適切であれば上記対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算し、
再計算で得た対応点、計測位置、カメラデータから三次元位置を計算することを特徴とする三次元位置計測方法。
【請求項７】
左右画像を元画像及び参照画像として入力し、
左右画像から元画像及び参照画像の縮小画像を作り、
計測位置を元画像で指定し、
請求項３に記載する回帰的対応点探索方法により対応点を求め、
対応点探索結果が不適切であれば処理を中断し、適切であれば上記対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算し、
再計算で得た対応点、計測位置、カメラデータから三次元位置を計算することを特徴とする三次元位置計測方法。
【請求項８】
元画像の計測位置とカメラデータから参照画像のエピポーララインを設定する第１のエピポーラライン設定手段と、
元画像、参照画像、元画像の縮小画像、参照画像の縮小画像、縮小比率、計測位置及びエピポーララインから、参照画像の縮小画像における対応点（以降「対応点（縮小）」と呼ぶ）を検出し、この対応点（縮小）から参照画像上の対応点位置（以降「対応箇所」と呼ぶ）を計算し、参照画像のエピポーラライン上の対応箇所近傍のみに関して対応点を検出する第１の段階解像度対応点探索手段と、元画像を参照画像に、参照画像を元画像に入れ換え設定する元画像・参照画像設定入れ換え手段と、
第１の段階解像度対応点探索手段で検出された上記対応点を計測位置（以降「計測位置（回帰）」と呼ぶ）として入れ換え設定後の元画像に設定する計測位置（回帰）設定手段と、
計測位置（回帰）とカメラデータから入れ換え設定された参照画像の縮小画像におけるエピポーラライン（以降「エピポーラライン（回帰）」と呼ぶ）を設定する第２のエピポーラライン設定手段と、
入れ換え設定された元画像、入れ換え設定された参照画像、入れ換え設定された元画像の縮小画像、入れ換え設定された参照画像の縮小画像、計測位置（回帰）及びエピポーラライン（回帰）から入れ換え設定された参照画像の縮小画像における対応点（以降「対応点（回帰・縮小）」と呼ぶ）を検出し、この対応点（回帰・縮小）から入れ換え設定された参照画像上の対応点位置（以降「対応箇所（回帰）」と呼ぶ）を計算し、入れ換え設定された参照画像のエピポーラライン（回帰）上の対応箇所（回帰）近傍のみに関して回帰対応点を検出する第２の段階解像度対応点探索手段と、
上記元画像の計測位置と上記回帰対応点との距離（以降「回帰距離」と呼ぶ）を計算する回帰距離計算手段と、
回帰距離を基に、第１の段階解像度対応点探索手段で検出された上位対応点が適切か不適切か判断する探索結果判断手段
を具備することを特徴とする回帰的対応点探索装置。
【請求項９】
元画像の計測位置とカメラデータから参照画像のエピポーララインを設定する第１のエピポーラライン設定手段と、
元画像の計測位置から元画像の縮小画像における計測位置を計算する計測点変換部、参照画像のエピポーララインから参照画像の縮小画像におけるエピポーララインを計算するエピポーラライン変換部、元画像の縮小画像において縮小パッチを設定する縮小パッチ設定部、この縮小パッチを用いて参照画像の縮小画像におけるエピポーラライン上の探索範囲に関して対応点（以降「対応点（縮小）と呼ぶ）を検出し、この対応点（縮小）から参照画像上の対応点位置（以降「対応箇所」と呼）を計算する縮小画像対応点検出部、元画像においてパッチを設定するパッチ設定部、及び、このパッチを用いて、参照画像のエピポーラライン上の対応箇所近傍のみに関して対応点を検出する通常画像対応点検出部を有する第１の段階解像度対応点探索手段と、
元画像を参照画像に、参照画像を元画像に入れ換え設定する元画像・参照画像設定入れ換え手段と、
第１の段階解像度対応点探索手段の通常画像対応点検出部で検出された上記対応点を、計測位置（以降「計測位置（回帰）と呼ぶ）として、入れ換え設定された元画像に設定する計測位置（回帰）設定手段と、
計測位置（回帰）とカメラデータから入れ換え設定された参照画像の縮小画像におけるエピポーラライン（以降「エピポーラライン（回帰）」と呼ぶ）を設定する第２のエピポーラライン設定手段と、
計測位置（回帰）から入れ換え設定された元画像の縮小画像における計測位置（以降「計測位置（回帰・縮小）」と呼ぶ）を計算する計測点変換部、エピポーラライン（回帰）から入れ換え設定された参照画像の縮小画像におけるエピポーララインを計算するエピポーラライン変換部、入れ換え設定された元画像の縮小画像において縮小パッチを設定する縮小パッチ設定部、この縮小パッチを用いて、入れ換え設定された参照画像の縮小画像におけるエピポーラライン上の探索範囲に関して対応点（以降「対応点（回帰）」と呼ぶ）を検出し、この対応点（回帰）から入れ換え設定された参照画像上の対応点位置（以降「対応箇所（回帰）」と呼）を計算する縮小画像対応点検出部、入れ換え設定された元画像においてパッチを設定するパッチ設定部、及び、このパッチを用いて、入れ換え設定された参照画像のエピポーラライン上の対応箇所（回帰）近傍のみに関して対応点（以降「回帰対応点」と呼ぶ）を検出する通常画像対応点検出部を有する第２の段階解像度対応点探索手段と、
上記元画像の計測位置と上記回帰対応点との距離（以降「回帰距離」と呼ぶ）を計算する回帰距離計算手段と、
回帰距離を基に、第１の段階解像度対応点探索手段で検出された上位対応点が適切か不適切か判断する探索結果判断手段
を具備することを特徴とする回帰的対応点探索装置。
【請求項１０】
元画像の計測位置から元画像の縮小画像における計測位置を計算し、参照画像のエピポーララインから参照画像の縮小画像におけるエピポーララインを設定し、元画像の縮小画像において縮小パッチを設定し、この縮小パッチを用いて参照画像の縮小画像におけるエピポーラライン上の探索範囲に関して対応点（以降「対応点（縮小）」と呼ぶ）を検出する第１の縮小画像対応点探索手段と、
元画像を参照画像に、参照画像を元画像に入れ換え設定する元画像・参照画像設定入れ換え手段と、
上記対応点（縮小）を、計測位置（以降「計測位置（回帰）」と呼ぶ）として、入れ換え設定後の元画像に設定する計測位置（回帰）設定手段と、
計測位置（回帰）とカメラデータから入れ換え設定後の参照画像の縮小画像におけるエピポーララインを設定し、入れ換え設定後の元画像の縮小画像において縮小パッチを設定し、この縮小パッチを用いて、入れ換え設定後の参照画像の縮小画像におけるエピポーラライン上の探索範囲に関して対応点（以降「回帰対応点」と呼ぶ）を検出する第２の縮小画像対応点探索手段と、
上記元画像の縮小画像における計測位置と上記回帰対応点との距離（「以降「回帰距離（縮小）」と呼ぶ）を計算する回帰距離計算手段と、
回帰距離を基に、第１の縮小画像対応点探索手段で検出された上記対応点（縮小）が適切か不適切か判断する探索結果判断手段と、
上記対応点（縮小）が適切であれば元画像と参照画像の設定を元に戻し、上記対応点（縮小）から参照画像上の対応点位置（以降「対応箇所」と呼ぶ）を計算する対応箇所設定手段と、
設定が戻された元画像においてパッチを設定するパッチ設定手段と、
このパッチを用いて、設定が戻された参照画像のエピポーラライン上の対応箇所近傍のみに関して対応点を検出する通常画像対応点探索手段
を具備することを特徴とする回帰的対応点探索装置。
【請求項１１】
元画像の計測位置とカメラデータから参照画像のエピポーララインを設定するエピポーラライン設定部、元画像の計測位置から元画像の縮小画像における計測位置を計算する計測点変換部、参照画像のエピポーララインから参照画像の縮小画像におけるエピポーララインを設定するエピポーラライン変換部、元画像の縮小画像において縮小パッチを設定する縮小パッチ設定部、及び、この縮小パッチを用いて、参照画像の縮小画像におけるエピポーラライン上の探索範囲に関して対応点（以降「対応点（縮小）」と呼ぶ）を検出する縮小画像対応点検出部を有する第１の縮小画像対応点探索手段と、
元画像を参照画像に、参照画像を元画像に入れ換え設定する元画像・参照画像設定入れ換え手段と、
第１の縮小画像対応点探索手段の縮小画像対応点検出部で検出された上記対応点（縮小）を、計測位置（以降「計測位置（回帰）」と呼ぶ）として、入れ換え設定された元画像の縮小画像に設定する計測位置（回帰）設定手段と、
計測位置（回帰）とカメラデータから入れ換え設定された参照画像のエピポーララインを設定するエピポーラライン設定部、入れ換え設定された参照画像のエピポーララインから入れ換え設定された参照画像の縮小画像におけるエピポーララインを設定するエピポーラライン変換部、入れ換え設定された元画像の縮小画像において縮小パッチを設定する縮小パッチ設定部、及び、この縮小パッチを用いて、入れ換え設定された参照画像の縮小画像におけるエピポーラライン上の探索範囲に関して対応点（以降「回帰対応点」と呼ぶ）を検出する縮小画像対応点検出部を有する第２の縮小画像対応点探索手段と、
上記元画像の縮小画像における計測位置と回帰対応点との距離（「以降「回帰距離（縮小）」と呼ぶ）を計算する回帰距離計算手段と、
回帰距離（縮小）を基に、上記対応点（縮小）が適切か不適切か判断する探索結果判断手段と、
上記対応点（縮小）が適切であれば元画像と参照画像の設定を元に戻し、上記対応点（縮小）から参照画像上の対応点位置（以降「対応箇所」と呼ぶ）を計算する対応箇所設定手段と、
設定が戻された元画像においてパッチを設定するパッチ設定手段と、
このパッチを用いて、設定が戻された参照画像のエピポーラライン上の対応箇所近傍のみに関して対応点を検出する通常画像対応点探索手段
を具備することを特徴とする回帰的対応点探索装置。
【請求項１２】
左右画像を元画像及び参照画像として入力する画像入力手段と、
左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、
計測位置を元画像で指定する計測位置指定手段と、
請求項８または９に記載する回帰的対応点探索装置と、
上記回帰的対応点探索装置による探索結果が適切であれば、同回帰的対応点探索装置で求まった対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段
を具備することを特徴とする三次元位置計測装置。
【請求項１３】
左右画像を元画像及び参照画像として入力する画像入力手段と、
左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、
計測位置を元画像で指定する計測位置指定手段と、
請求項１０または１１に記載する回帰的対応点探索装置と、
上記回帰的対応点探索装置による探索結果が適切であれば、同回帰的対応点探索装置で求まった対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段
を具備することを特徴とする三次元位置計測装置。
【請求項１４】
左右画像を元画像及び参照画像として入力する画像入力手段と、
左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、
計測位置を元画像で指定する計測位置指定手段と、
請求項８または９に記載する回帰的対応点探索装置と、
上記回帰的対応点探索装置による探索結果が適切であれば、同回帰的対応点探索装置で求まった対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算する対応点実数化手段と、
再計算した対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段を
具備することを特徴とする三次元位置計測装置。
【請求項１５】
左右画像を元画像及び参照画像として入力する画像入力手段と、
左右画像から元画像及び参照画像の縮小画像を作る画像処理手段と、
計測位置を元画像で指定する計測位置指定手段と、
請求項１０または１１に記載する回帰的対応点探索装置と、
上記回帰的対応点探索装置による探索結果が適切であれば、同回帰的対応点探索装置で求まった対応点を中心とする複数点の相関値データを用いる補間処理により対応点を再計算する対応点実数化手段と、
再計算した対応点、計測位置、カメラデータから三次元位置を計算する三次元位置計算手段
を具備することを特徴とする三次元位置計測装置。
【請求項１６】
請求項２に記載する回帰的対応点探索方法の手順を、当該回帰的対応点探索方法をコンピュータで実現するコンピュータプログラムとして、記録している記録媒体。
【請求項１７】
請求項３に記載する回帰的対応点探索方法の手順を、当該回帰的対応点探索方法をコンピュータで実現するコンピュータプログラムとして記録している記録媒体。
【請求項１８】
請求項４に記載する三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している記録媒体。
【請求項１９】
請求項５に記載する三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している記録媒体。
【請求項２０】
請求項６に記載する三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している記録媒体。
【請求項２１】
請求項７に記載する三次元位置計測方法の手順を、当該三次元位置計測方法をコンピュータで実現するコンピュータプログラムとして記録している記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は回帰的対応点探索方法、これを利用した三次元位置計測方法、これらの装置、並びに、記録媒体に関し、いわゆるステレオ画像を用いた三次元位置計測に適用して有用なものである。
【０００２】
【従来の技術】
ステレオ画像を用いた三次元位置計測方法にとして、一方の入力画像の一部を計測位置にて切り出してその濃淡パターンを画像モデル（以降これを「パッチ」と呼ぶ）として記憶し、もう一方の入力画像（以降これを「参照画像」と呼ぶ）においてパッチと同じパターンを持つ画像の小領域の位置（以降これを「対応点」と呼ぶ）を、濃淡パターンの相関から検出する方法（以降これを「領域相関法」と呼ぶ）が用いられている。以降、パッチの元になる画像を「元画像」と呼ぶ。
【０００３】
また、対応点探索においては、探索範囲をエピポーラライン上に拘束する手法が用いられることがある。エピポーララインとは対応点が存在可能な直線であり、ステレオ画像を取り込む２台のカメラの位置関係から導かれる。
【０００４】
領域相関法について更に詳言すると、
▲１▼先ず、検査前の予備段階として、対象物のサンプルの画像（元画像）の一部を切り出して、その部分の濃度に関するパターンを、パッチとして記憶する。
▲２▼次に、検査時に、もう一方のサンプルの画像（参照画像）から、１画素ずれた各点毎に順次パッチと同じ形状で且つ同じ大きさの濃度に関するパターンを切り出し、各点毎にパッチと切り出したパターンとの相関値を計算し、相関の最も強いパターンが切り出された点の位置を、パッチとの対応点の位置とする。ここで、相関値の大小と相関の強弱は相関値を求める計算式により異なり、相関値が最小の場合に相間が最強となる計算式と、相関値が最大の場合に相関が最強となる計算式とがある。
【０００５】
下式（１）は２つのパターン間の相関値を求める計算式の一例であり、式中のＰi はパッチのｉ番目の画素の濃度であり、Ｑi は切り出したパターンのｉ番目の画素の濃度であり、この式（１）の場合は、切り出した各パターンのうち、相関値Ｃが最小となるパターンが切り出された点の位置を、対応点の位置として決定することになる。
【数１】
0003906615.tif 000002
【０００６】
また、下式（２）は相関値の計算式の他の例であり、この場合は、切り出したパターンのうち、相関値Ｃが最大となるパターンが切り出された点の位置を、対応点の位置として決定することになる。
【数２】
0003906615.tif 000003
【０００７】
上述した相関マッチング処理は、常識的で広く使用されているが、厳密に言うと次の点で問題がある。
【０００８】
即ち、１画素ずつずれた各点毎にパターンを切り出しているから、式（１）の計算から得られる対応点の位置は１画素毎の離散的なものであり、つまり、１画素を単位とする整数で表されるので、場合によっては真の対応点から最大で±０．５画素分ずれた位置になる危険性がある。そして、この０．５画素のずれが実際の対象物上でどのような寸法になるかは、撮影に用いるビデオカメラの分解能等に依存するので、従来の相関マッチング処理では対処することができないものである。
【０００９】
しかしながら、実用的には０．５画素のずれは影響が大きく、精密な位置決めには使用することができない。例えば、ビデオカメラの分解能が水平方向に５１２画素で視角が６０°、ビデオカメラと対象物間の距離が２ｍである場合、±０．５画素のずれは約５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) 〜(8) により基本型回帰的対応点探索を行う。この例では、通常画像を対象としている。
(1) 図１（ａ）に示す元画像１の計測位置３とカメラデータから、図１（ａ）に示す参照画像２のエピポーラライン７を設定する（ステップＳ１）。
(2) 図１（ａ）に示す元画像１及び参照画像２、並びに、エピポーラライン７及び計測位置３を入力して、相関計算による領域相関法等、適宜な対応点探索手法により、対応点４を検出する（ステップＳ２）。
(3) 次に、回帰処理を行うべきか否か判断する（ステップＳ３）。回帰処理を行う場合(ON)には、元画像と参照画像の設定を入れ換える。始めは回帰処理を行うので、図１（ａ）の元画像１と参照画像２を、図１（ｂ）のように元画像２と参照画像１に入れ換えて再設定する（ステップＳ４）。
(4) 上記手順(2) で検出した対応点４を計測位置（回帰）５として図１（ｂ）の元画像２に設定する（ステップＳ５）。
(5) 次は、ステップＳ１に戻り、計測位置（回帰）５とカメラデータから、図１（ｂ）の参照画像１にエピポーラライン８を設定する。
(6) 図１（ａ）の元画像２及び参照画像１、エピポーラライン８及び計測位置（回帰）５を入力して、相関計算による領域相関法等、適宜な対応点探索手法により、回帰対応点６を検出する（ステップＳ２）。
(7) 次に、回帰処理を行うべきか否か判断する（ステップＳ３）。回帰処理を行わない場合(OFF) には、ステップＳ６に進む。今回は回帰処理を行わないので、ステップＳ６にて、計測位置３と回帰対応点６との距離、即ち回帰距離を計算する。
(8) 回帰距離を基に、対応点４が適切か不適切か、対応点探索結果の是非を判断する（ステップＳ７）。
【００４８】
対応点探索結果の是非の判断としては、例えば、回帰距離が所定範囲内であれば上記手順(2) で検出した対応点４が適切であると判断し、所定範囲外であれば不適切であると判断することができる。対応点が不適切であると判断した場合は、処理を中断すれば良い。所定範囲は、例えば適宜な手法により予め定めておくことができる。
【００４９】
なお、処理中断の場合、不適切な対応点の次に相関が強い点を改めて対応点と定め、回帰処理を行うことができる。
【００５０】
［直列型回帰的対応点探索方法］
次に、図３〜図５に基づき、本発明の実施形態例として、処理時間を短縮するために、後述する「段階的解像度画像による対応点探索」を用いる回帰的対応点探索方法を説明する。図３は段階的解像度画像による対応点探索方法を説明する模式図を示し、図４は段階的解像度画像による対応点探索方法の処理手順のフローチャートを示し、図５は本実施形態例に係る回帰的対応点探索方法全体のフローチャートを示す。
【００５１】
一般に、対応点探索及び回帰処理には、時間がかかる濃淡パターンの相関演算を多量に行う必要があるため、パッチのサイズが大きくなるほど処理時間が長くなる。
【００５２】
図３に示すように、通常解像度の画像（通常画像）２１と、設定した間隔毎の画像データにより構成した解像度の低い画像（縮小画像）２２とを段階的解像度画像として用意し、最初は縮小画像２２のエピポーラライン２６上に関して対応点２７を探索し、次に、この対応点２７の位置に対応する通常画像２１上の位置（以降これを「対応箇所」と呼ぶ）２８の近傍のみについて、対応点探索を行うことにより、計算時間を短縮することができる。例えば、縮小比率１／２で行った場合、最初の対応点探索において探索範囲が１／２となりパッチサイズが１／４となるので相関計算の対象となる点数は１／８に減少し、処理時間が短縮し、処理が高速化する。
【００５３】
詳しくは、図４に示すように、下記▲１▼〜▲７▼の処理手順により段階的解像度画像による対応点探索を行う。なお、２１ａは元画像、２１ｂは参照画像とし、予め設定されている。２２ａは元画像２１ａの縮小画像、２２ｂは参照画像２１ａの縮小画像とする。
▲１▼元画像２１ａの計測位置２３から、その縮小画像２２ａにおける計測位置２５を計算し、設定する（ステップＳ１１）。
▲２▼参照画像２１ｂにおけるエピポーラライン２４から、その縮小画像２２ｂにおけるエピポーラライン２６を計算し、設定する（ステップＳ１２）。
▲３▼計測位置２５を設定した縮小画像２２ａにおいて縮小比率に対応するサイズのパッチ（以降これを「縮小パッチ」と呼ぶ）を設定する（ステップＳ１３）。
▲４▼もう一方の縮小画像２２ｂのエピポーラライン２６上の探索範囲に関して対応点２７を相関計算によって検出する（ステップＳ１４）。
▲５▼縮小画像２２ｂ上の対応点２７の位置から参照画像２１ｂ上の対応点位置、つまり、対応箇所２８を計算する（ステップＳ１５）。
▲６▼計測位置２３を設定した元画像２１ａにおいてパッチを設定する（ステップＳ１６）。
▲７▼参照画像２１ｂのエピポーラライン２４上の対応箇所２８の近傍のみに関して対応点を相関計算によって検出する（ステップＳ１７）。
【００５４】
そこで、上記段階的解像度画像による対応点探索処理を直列に並べ、
(1) １段目の「段階的解像度画像による対応点探索処理」で、対応点を検出し、
(2) 次に、元画像を参照画像に、参照画像を元画像に入れ換え設定し、
(3) 上記対応点を、計測位置（回帰）として、入れ換え設定後の元画像に設定し、
(4) ２段目の「段階的解像度画像による対応点探索処理」で、回帰対応点を検出し、
(5) 入れ換え設定前の元画像における計測位置と上記回帰対応点との回帰距離を計算し、回帰距離を基に、１段目の「段階的解像度画像による対応点探索処理」で検出した上記対応点が適切か不適切か判断することにより、
処理時間を短縮することができる。以降、この回帰的対応点探索方法を「直列型回帰的対応点探索方法」と呼ぶ。
【００５５】
図５に示す例では、以下の手順(1) 〜(8) により「直列型回帰的対応点探索方法」を行う。
(1) 元画像の計測位置とカメラデータから参照画像のエピポーララインを設定する（ステップＳ２１）。
(2) 通常画像（元画像と参照画像）、元画像と参照画像の各縮小画像、縮小比率、参照画像のエピポーラライン、元画像の計測位置を入力して、対応点を検出する（ステップＳ２２）。具体的には、図４に準じて下記▲１▼〜▲７▼の手順により、上記「段階的解像度画像による対応点探索方法」で対応点を検出する。
▲１▼元画像の計測位置から元画像の縮小画像における計測位置を計算し、設定する。
▲２▼参照画像におけるエピポーララインから参照画像の縮小画像におけるエピポーラライン（以降「エピポーラライン（縮小）と呼ぶ）を計算し、設定する。
▲３▼元画像の縮小画像において縮小パッチを設定する。
▲４▼参照画像の縮小画像のエピポーラライン（縮小）上の探索範囲に関して対応点（以降「対応点（縮小）」と呼ぶ）を相関計算によって検出する。
▲５▼この対応点（縮小）位置から参照画像上の対応箇所を計算する。
▲６▼元画像においてパッチを設定する。
▲７▼参照画像のエピポーラライン上の対応箇所近傍のみに関して対応点を相関計算によって検出する。
(3) 次に、回帰処理を行うすべきか否か判断する（ステップＳ２３）。回帰処理を行う場合(ON)は、元画像と参照画像の設定を入れ換える（ステップＳ２４）。最初は回帰処理を行うので、元画像を参照画像に、参照画像を元画像に入れ換えて再設定する。
(4) 上記手順(2) で検出した対応点を計測位置（回帰）として入れ換え設定後の元画像に設定する（ステップＳ２５）。
(5) ステップＳ２１に戻り、計測位置（回帰）とカメラデータから、入れ換え設定後の参照画像のエピポーラライン（以降「エピポーラライン（回帰）と呼ぶ）を設定する。
(6) 入れ換え設定後の元画像と参照画像、それらの縮小画像、縮小比率、エピポーラライン（回帰）、計測位置（回帰）を入力して、回帰対応点を検出する（ステップＳ２２）。具体的には、図４に準じて下記▲１▼〜▲７▼の手順により、上記「段階的解像度画像による対応点探索方法」で回帰対応点を検出する。
▲１▼計測位置（回帰）から元画像の縮小画像における計測位置（以降「計測位置（回帰・縮小）」と呼ぶ）を計算する。
▲２▼エピポーラライン（回帰）から参照画像の縮小画像におけるエピポーラライン（以降「エピポーラライン（回帰・縮小）」と呼ぶ）を計算する。
▲３▼計測位置（回帰・縮小）を設定した元画像の縮小画像において縮小パッチ（以降「縮小パッチ（回帰）」と呼ぶ）を設定する。
▲４▼参照画像の縮小画像のエピポーラライン（回帰・縮小）上の探索範囲に関して対応点（以降「対応点（回帰・縮小）」と呼ぶ）を相関計算により検出する。
▲５▼参照画像の縮小画像上の対応点位置（回帰・縮小）から参照画像上の対応箇所（以降「対応箇所（回帰）」と呼ぶ）を計算する。
▲６▼計測位置（回帰）を指定した元画像においてパッチ（以降「パッチ（回帰）」と呼ぶ）を設定する。
▲７▼パッチ（回帰）を用い、参照画像のエピポーラライン（回帰）上の対応箇所（回帰）近傍のみに関して対応点（以降「回帰対応点」と呼ぶ）を相関計算によって検出する。
(7) 次に、回帰処理を行うすべきか否か判断する（ステップＳ２３）。回帰処理を行わない場合(OFF) には、ステップＳ２６に進む。今回は回帰処理を行わないので、ステップＳ２６にて、入れ換え設定前の元画像の計測位置と上記の回帰処理で検出した回帰対応点から回帰距離を計算する。
(8) 回帰距離を基に、対応点探索結果の是非を判断する（ステップＳ２７）。回帰距離が所定範囲内であれば、上記手順(2) で検出した対応点が適切であると判断する。所定範囲外であれば不適切であると判断し、処理を中断する。この場合、必要に応じて、不適切な対応点の次に相関が強い点を改めて対応点と定め、回帰処理を行うことができる。
【００５６】
［縮小画像型回帰的対応点探索方法］
次に、図６に基づき、本発明の実施形態例としては、処理時間を短縮するために、段階的解像度画像による対応点探索方法のうち、縮小画像における対応点探索について回帰処理を適用して、回帰的対応点探索方法を行う。
【００５７】
つまり、
(1) 元画像の縮小画像、参照画像の縮小画像、参照画像の縮小画像におけるエピポーラライン（以降「エピポーラライン（縮小）と呼ぶ）及び元画像の縮小画像における計測位置（以降「計測位置（縮小）と呼ぶ）から、参照画像の縮小画像における対応点（以降「対応点（縮小）と呼ぶ）を検出し、次に、元画像を参照画像に、参照画像を元画像に入れ換え再設定し、上記対応点（縮小）を計測位置（以降「計測位置（回帰）」と呼ぶ）として、入れ換え設定後の元画像の縮小画像に設定し、計測位置（回帰）とカメラデータから入れ換え設定後の参照画像の縮小画像にエピポーラライン（以降「エピポーラライン（回帰）」と呼ぶ）を設定し、入れ換え設定後の元画像及び参照画像の各縮小画像、エピポーラライン（回帰・縮小）及び計測位置（回帰）から対応点（以降「回帰対応点」と呼ぶ）を検出し、
(2) 縮小画像において計測位置（縮小）と回帰対応点との距離（以降「回帰距離（縮小）」と呼ぶ）を計算し、回帰距離（縮小）を基に縮小画像における対応点探索結果が適切か不適切か判断し、
(3) 対応点探索結果が不適切であれば処理を中断し、
(4) 対応点探索結果が適切であれば元画像と参照画像の設定を元に戻し、上記対応点（縮小）の位置から参照画像上の対応点位置（以降「対応箇所」と呼ぶ）を計算し、参照画像のエピポーラライン上の対応箇所近傍のみに関して対応点を検出することにより、
処理時間を短縮することができる。以降、この回帰的対応点探索方法を「画像縮小型回帰的対応点探索方法」と呼ぶ。
【００５８】
詳しくは、図６に示すように、以下の手順(1) 〜(15)により縮小画像型回帰的対応点探索を行う。図６は縮小画像型回帰的対応点探索方法の全体的なフローチャートを示す。
(1) 元画像の計測位置から元画像の縮小画像における計測位置（縮小）を計算し、設定する（ステップＳ３１）。
(2) 元画像の計測位置とカメラデータから、参照画像でのエピポーララインを計算し、設定する（ステップＳ３２）。
(3) 参照画像でのエピポーララインから、参照画像の縮小画像におけるエピポーラライン（縮小）を計算し、設定する（ステップＳ３３）。
(4) 元画像の縮小画像において縮小パッチを設定する。（ステップＳ３４）
(5) 参照画像の縮小画像のエピポーラライン（縮小）上の探索範囲に関して対応点（縮小）を相関計算によって検出する（ステップＳ３５）。
(6) 次に、回帰処理を行うすべきか否か判断する（ステップＳ３６）。今回は回帰処理を行うので(ON)、元画像を参照画像に、参照画像を元画像に入れ換え再設定する。即ち、元画像と参照画像の設定を入れ換える（ステップＳ３７）。
(7) 上記手順(5) で検出した対応点（縮小）を計測位置（回帰）として入れ換え設定後の元画像に設定する（ステップＳ３８）。
(8) 上記手順(2) から手順(5) を繰り返して回帰対応点を検出する（ステップＳ３２〜Ｓ３５）。即ち、
▲１▼入れ換え設定後の元画像の縮小画像における計測位置（回帰）とカメラデータから、入れ換え設定後の参照画像でのエピポーララインを計算し、設定する（ステップＳ３２）。
▲２▼入れ換え設定後の参照画像でのエピポーララインから、入れ換え設定後の参照画像の縮小画像におけるエピポーラライン（縮小）を計算し、設定する（ステップＳ３３）。
▲３▼入れ換え設定後の元画像の縮小画像において縮小パッチを設定する。（ステップＳ３４）
▲４▼入れ換え設定後の参照画像の縮小画像のエピポーラライン（縮小）上の探索範囲に関して回帰対応点を相関計算によって検出する（ステップＳ３５）。
(9) 次に、回帰処理を行うすべきか否か判断する（ステップＳ３６）。回帰処理を行わない場合(OFF) はステップＳ３９に進む。今回は回帰処理を行わなわず、ステップＳ３９にて、縮小画像において、上記手順(1) で設定した計測位置（縮小）と上記手順(8) で検出した回帰対応点から回帰距離（縮小）を計算する。
(10)回帰距離（縮小）を基に、対応点探索結果の是非を判断する（ステップＳ４０）。つまり、上記手順(5) で検出した対応点（縮小）が適切か不適切か判断する。例えば、回帰距離（縮小）が所定範囲外(NO)であれば不適切として処理を中断し、所定範囲内(YES) であれば、適切と判断する。
(11)上記手順(10)での判断において対応点（縮小）が適切であれば、元画像と参照画像の設定を元に戻す（ステップＳ４１）。
(12)上記手順(5) で検出した対応点（縮小）から設定が戻った参照画像上の対応箇所を計算する（ステップＳ４２）。
(14)設定が戻った元画像においてパッチを設定する（ステップＳ４３）。
(15)このパッチを用いて、設定が戻った参照画像のエピポーラライン上の対応箇所近傍のみに関して対応点を相関計算によって検出する（ステップＳ４４）。
【００５９】
［三次元位置計測方法］
ステレオ画像に計測位置を設定し、それの対応点を上記「直列型回帰的対応点探索方法」あるいは「縮小画像型回帰的対応点探索方法」を用いて求めることにより、計測位置、対応点及びカメラデータから三次元位置が求まる。この場合、対応点間違いがなく信頼性が高いので、三次元位置計測データの信頼性も高い。また、上記「直列型回帰的対応点探索方法」あるいは「縮小画像型回帰的対応点探索方法」を用いて対応点を求める場合は、処理時間が短縮するので、三次元位置計測の処理時間も短縮する。以下、具体的に説明する。
【００６０】
［三次元位置計測方法１］
本実施形態例に係る三次元位置計測方法１は上記「直列型回帰的対応点探索方法」を用いたものであり、その処理手順のフローチャートを図７に示す。図７に示すように、次の手順(1) 〜(6) によりステレオ画像から三次元位置計測を行う。
(1) 左右画像を元画像及び参照画像として入力する（ステップＳ５１）。
(2) 左右画像から左右縮小画像、つまり、元画像及び参照画像の縮小画像を作る（ステップＳ５２）。
(3) 計測位置を元画像で指定する（ステップＳ５３）。
(4) 上記「直列型回帰的対応点探索方法」により対応点探索を行い、対応点を得る（ステップＳ５４）。
(5) 対応点の探索結果を確認する（ステップＳ５５）。対応点が不適切(NO)と判断された場合は、処理を中断する。
(6) 対応点が適切(YES) であると判断された場合は、計測位置、対応点、カメラデータから三次元位置を計算する（ステップＳ５６）。
【００６１】
［三次元位置計測方法２］
本実施形態例に係る三次元位置計測方法２は上記「縮小画像型回帰的対応点探索方法」を用いたものであり、その処理手順のフローチャートを図８に示す。図８に示すように、次の手順(1) 〜(6) によりステレオ画像から三次元位置計測を行う。
(1) 左右画像を元画像及び参照画像として入力する（ステップＳ６１）。
(2) 左右画像から左右縮小画像、つまり、元画像及び参照画像の縮小画像を作る（ステップＳ６２）。
(3) 計測位置を元画像で指定する（ステップＳ６３）。
(4) 上記「縮小画像型回帰的対応点探索方法」により対応点探索を行い、対応点を得る（ステップＳ６４）。
(5) 対応点の探索結果を確認する（ステップＳ６５）。対応点が不適切(NO)と判断された場合は、処理を中断する。
(6) 対応点が適切(YES) であると判断された場合は、計測位置、対応点、カメラデータから三次元位置を計算する（ステップＳ６６）。
【００６２】
［三次元位置計測方法３］
画像データは離散的なデータであるため、上記「三次元位置計測方法１」においては、上記「直列型回帰的対応点探索方法」により得られる対応点は離散的な画素の位置データとして与えられ、実際の対応点位置と比べて最大で１／２画素の誤差を生じる。高精度位置決めが要求される作業においてはこの誤差を小さく抑える必要がある。
【００６３】
そこで、本実施形態例に係る三次元位置計測方法３では、検出した対応点の近傍点の相関値データを用いて補間演算するという対応点実数化方式により、離散的な画素間に存在する真の対応点位置を再計算して求める。
【００６４】
対応点実数化方式としては、適宜な補間演算を行うものを使用すれば良いが、ここでは「直線型対応点実数化方式」と「二次曲線型対応点実数化方式」を例に挙げ、下記に説明する。
▲１▼直線型対応点実数化方式では、上式（３）または（４）を用いた上述の補間演算を行うことにより、対応点位置を再計算する。
▲２▼二次曲線型対応点実数化方式では、二次曲線は唯一のピーク（凸または凹）を持つ曲線であることに着目して、図９に模式的に示すように、対応点探索で得られる点を中心に幾つかの近傍点（３点以上）の相関値データを二次曲線で近似し、得られた二次曲線のピークの位置を対応点とするという補間演算により、対応点位置を再計算する。
【００６５】
三次元位置計測方法３の処理手順のフローチャートを図１０に示す。図１０に示すように、次の手順(1) 〜(7) によりステレオ画像から三次元位置計測を行う。
(1) 左右画像を元画像及び参照画像として入力する（ステップＳ７１）。
(2) 左右画像から左右縮小画像、つまり、元画像及び参照画像の縮小画像を作る（ステップＳ７２）。
(3) 計測位置を元画像で指定する（ステップＳ７３）。
(4) 上記「直列型回帰的対応点探索方法」により対応点探索を行い、対応点を得る（ステップＳ７４）。
(5) 対応点の探索結果を確認する（ステップＳ７５）。対応点が不適切(NO)と判断された場合は、処理を中断する。
(6) 対応点が適切(YES) であると判断された場合は、上記「直線型対応点実数化方式」あるいは「二次曲線型対応点実数化方式」等の対応点実数化方式により、対応点の再計算を行う（ステップＳ７６）。
(7) 計測位置、再計算した対応点、カメラデータから三次元位置を計算する（ステップＳ７７）。
【００６６】
［三次元位置計測方法４］
本実施形態例に係る三次元位置計測方法４では、上記「三次元位置計測方法２」において上記「縮小画像型回帰的対応点探索方法」により得られる対応点を、誤差を小さく抑えるため、対応点実数化方式により再計算する。
【００６７】
三次元位置計測方法４の処理手順のフローチャートを図１１に示す。図１１に示すように、次の手順(1) 〜(7) によりステレオ画像から三次元位置計測を行う。
(1) 左右画像を元画像及び参照画像として入力する（ステップＳ８１）。
(2) 左右画像から左右縮小画像、つまり、元画像及び参照画像の縮小画像を作る（ステップＳ８２）。
(3) 計測位置を元画像で指定する（ステップＳ８３）。
(4) 上記「縮小画像型回帰的対応点探索方法」により対応点探索を行い、対応点を得る（ステップＳ８４）。
(5) 対応点の探索結果を確認する（ステップＳ８５）。対応点が不適切(NO)と判断された場合は、処理を中断する。
(6) 対応点が適切(YES) であると判断された場合は、上記「直線型対応点実数化方式」または「二次曲線型対応点実数化方式」等の対応点実数化方式により、対応点の再計算を行う（ステップＳ８６）。
(7) 計測位置、再計算した対応点、カメラデータから三次元位置を計算する（ステップＳ８７）。
【００６８】
［直列型回帰的対応点探索方法による対応点探索装置］
図１２、図１３を参照して、本発明の実施形態例に係る対応点探索装置として、上記「直列型回帰的対応点探索方法」を実現する対応点探索装置を説明する。図１２は本実施形態例に係る対応点探索装置を示すブロック図であり、図１３は図１２中の段階的解像度画像対応点探索部３２、３６それぞれの構成例を示すブロック図である。
【００６９】
図１２に示すように、当該対応点探索装置は、第１のエピポーラライン設定部３１、第１の段階解像度画像対応点探索部３２、元画像・参照画像設定入れ換え部３３、計測位置（回帰）設定部３４、第２のエピポーラライン設定部３５、第２の段階解像度画像対応点探索部３６、回帰距離計算部３７及び探索結果判断部３８を有している。計測データとしては、元画像の計測位置、カメラデータ、縮小比率（縮小データ）、探索結果判断用の基準（例えば、回帰距離に対する範囲）等が与えられる。
【００７０】
これらのうち、第１のエピポーラライン設定部３１は、元画像の計測位置とカメラデータに基づいて、参照画像のエピポーララインを設定するものである。
【００７１】
第１の段階解像度画像対応点探索部３２は上記「段階的解像度画像による対応点探索方法」を実現する装置であり、通常画像（元画像と参照画像）、元画像と参照画像の各縮小画像、縮小比率（縮小データ）、元画像の計測位置及びエピポーラライン設定部３１により設定された参照画像のエピポーララインを入力して対応点を検出する。詳しくは、第１の段階解像度画像対応点探索部３２は図１３に示すように、計測点変換部４１、エピポーラライン変換部４２、縮小パッチ設定部４３、縮小画像対応点検出部４４、通常画像対応点検出部４５及びパッチ設定部４６を有している。
【００７２】
第１の段階解像度画像対応点探索部３２に関して、計測点変換部４１は、縮小データ及び元画像の計測位置のデータに基づいて、元画像の計測位置から元画像の縮小画像における計測位置（縮小）を計算するものである。エピポーラライン変換部４２は、縮小データ及びエピポーラライン設定部３１により設定された参照画像のエピポーララインのデータに基づいて、参照画像のエピポーララインから、その縮小画像におけるエピポーラライン（縮小）を計算するものである。縮小パッチ設定部４３は、縮小画像のデータ、縮小データ及び計測点変換部４１で計算される計測位置（縮小）のデータに基づいて、元画像の縮小画像において縮小パッチを設定するものである。縮小画像対応点検出部４４は、縮小画像のデータ、縮小データ、縮小パッチ設定部４３で設定される縮小パッチのデータ及びエピポーラライン変換部４２で計算されるエピポーラライン（縮小）のデータに基づいて、参照画像の縮小画像におけるエピポーラライン（縮小）上の探索範囲に関して対応点を相関計算によって検出するものである。パッチ設定器４６は、元画像のデータ及び元画像の計測位置のデータに基づいて、元画像においてパッチを設定するものである。通常画像対応点検出部４５は、縮小画像対応点検出部４４の検出データ（対応点位置）、元画像及び参照画像のデータ、パッチ設定器４６で設定されるパッチのデータ及び参照画像のエピポーララインのデータに基づいて、縮小画像上の対応点位置から参照画像上の対応箇所を計算し、エピポーラライン上の対応箇所近傍のみに関して対応点を相関計算によって検出することで対応点を決定するものである。
【００７３】
従って、第１の段階解像度画像対応点探索部３２においては、元画像における計測位置から元画像の縮小画像における計測位置（縮小）を計算し、参照画像におけるエピポーララインから参照画像の縮小画像におけるエピポーラライン（縮小）を計算し、元画像の縮小画像において縮小パッチを設定し、参照画像の縮小画像におけるエピポーラライン（縮小）上の探索範囲に関して対応点を相関計算によって検出し、縮小画像上の対応点位置から参照画像上の対応箇所を計算し、元画像においてパッチを設定し、参照画像のエピポーラライン上の対応箇所近傍のみに関して対応点を相関計算によって検出することで、対応点を決定する。このように、広範囲の対応点探索を縮小画面にて行い、縮小画面における処理で検出された対応箇所近傍のみについて通常画面で対応点探索を行うため、高速な対応点検出を行うことができるメリットがある。
【００７４】
元画像・参照画像設定入れ換え部３３は、元画像と参照画像の設定を入れ換えるものである。即ち、第１の段階解像度画像探索部３２が対応点を検出した後、元画像を参照画像に、参照画像を元画像に再設定する。
【００７５】
計測位置（回帰）設定部３４は、第１の段階解像度画像対応点探索部３２で検出した対応点を計測位置（回帰）として、入れ換え設定された元画像に設定するものである。
【００７６】
第２のエピポーラライン設定部３５は、計測位置（回帰）とカメラデータから、入れ換え設定された参照画像におけるエピポーラライン（回帰）を設定するものである。
【００７７】
第２の段階解像度画像対応点探索部３６は上記「段階解像度画像による対応点探索方法」を実現する装置であり、元画像と参照画像が入れ換わった通常画像及びその縮小画像、縮小率（縮小データ）、エピポーラライン（回帰）及び計測位置（回帰）を入力して、回帰対応点を検出する。具体的には、第２の段階解像度画像対応点探索部３６は、先に説明した段階的解像度画像対応点探索部３２と同様、図１３に示すように、計測点変換部４１、エピポーラライン変換部４２、縮小パッチ設定部４３、縮小画像対応点検出部４４、通常画像対応点検出部４５及びパッチ設定部４６を有している。
【００７８】
第２の段階的解像度画像対応点探索部３６に関しては、計測点変換部４１は、縮小データ及び計測位置（回帰）のデータに基づいて、元画像における計測位置（回帰）から縮小画像における計測位置（回帰・縮小）を計算する。エピポーラライン変換部４２は、縮小データ及び第２のエピポーラライン設定部３５により設定されるエピポーラライン（回帰）のデータに基づいて、参照画像におけるエピポーラライン（回帰）から縮小画像におけるエピポーラライン（回帰・縮小）を計算する。縮小パッチ設定部４３は、縮小画像のデータ、縮小データ及び計測点変換部４１で計算される計測位置（回帰・縮小）のデータに基づいて、計測位置（回帰・縮小）を設定した方の縮小画像（元画像の縮小画像）において縮小パッチ（回帰）を設定する。縮小画像対応点検出部４４は、縮小画像のデータ、縮小データ、縮小パッチ設定部４３で設定される縮小パッチ（回帰）のデータ及びエピポーラライン変換部４２で計算されるエピポーラライン（回帰・縮小）のデータに基づいて、元画像の縮小画像におけるエピポーラライン（回帰・縮小）上の探索範囲に関して対応点を相関計算によって検出する。パッチ設定器４６は、通常画像のデータ及び計測位置のデータに基づいて、元画像においてパッチ（回帰）を設定する。通常画像対応点検出部４５は、縮小画像対応点検出部４４で検出される対応点位置のデータ、通常画像のデータ、パッチ設定器４６で設定されるパッチ（回帰）のデータ及びエピポーラライン（回帰）のデータに基づいて、参照画像の縮小画像上の対応点位置から参照画像上の対応箇所（回帰）を計算し、エピポーラライン（回帰）上の対応箇所（回帰）近傍のみに関して対応点を相関計算によって検出することで回帰対応点を決定する。
【００７９】
従って、第２の段階的解像度画像対応点探索部３６においては、元画像おける計測位置（回帰）から元画像の縮小画像における計測位置（回帰・縮小）を計算し、参照画像におけるエピポーラライン（回帰）から参照画像の縮小画像におけるエピポーラライン（回帰・縮小）を計算し、計測位置（回帰・縮小）を設定した方の縮小画像において縮小パッチ（回帰）を設定し、もう一方の縮小画像のエピポーラライン上（回帰・縮小）の探索範囲に関して対応点（回帰・縮小）を相関計算によって検出し、この縮小画像上の対応点（回帰・縮小）位置から参照画像上の対応箇所（回帰）を計算し、計測位置（回帰）を指定した方の通常画像（こと画像）においてパッチ（回帰）を設定し、もう一方の通常画像（参照画像）のエピポーラライン上の対応箇所（回帰）近傍のみに関して対応点を相関計算によって検出することで、回帰対応点を決定する。このように、広範囲の回帰対応点探索を縮小画面にて行い、縮小画面における処理で検出された対応箇所（回帰）近傍のみについて通常画面で回帰対応点探索を行うため、高速な回帰対応点検出を行うことができるメリットがある。
【００８０】
回帰距離計算部３７は、元画像の計測位置と入れ換え設定後の参照画像（入れ換え設定前の元画像）の回帰対応点から回帰距離を計算するものである。
【００８１】
探索結果判断部３８は、回帰距離を基に対応点探索結果の是非を判断するものであり、例えば、回帰距離が所定範囲内であれば、第１の段階解像度画像対応点探索部３２で検出した対応点が適切(YES) であると判断する。所定範囲外であれば不適切(NO)であると判断する。
【００８２】
かくして、本実施形態例に係る「直列型回帰的対応点探索方法による対応点探索装置」においては、計測位置とカメラデータからエピポーララインを設定し、段階解像度画像対応点探索方法を実現する第１の段階的解像度画像対応点探索部３２により対応点を検出し、元画像を参照画像に、参照画像を元画像にそれぞれ入れ換えて再設定し、第１の段階解像度画像対応点探索部３２で検出した対応点を計測位置（回帰）として設定し、計測位置（回帰）とカメラデータからエピポーラライン（回帰）を設定し、段階解像度画像対応点探索方法を実現する第２の段階解像度画像対応点探索部３６により回帰対応点を検出し、計測位置と回帰対応点から回帰距離を計算し、回帰距離を元に対応点探索の是非を判断する。
【００８３】
このように、当該対応点探索装置では、広範囲の対応点探索を縮小画面にて行い、縮小画面における処理で検出された対応箇所近傍のみについて通常画面で対応点探索を行う処理を、元画面と参照画面に対して回帰的に行い、対応点探索結果の是非を判断するため、信頼性のある対応点を高速に得ることができる。
【００８４】
ここで、通常画像のデータ及び縮小画像のデータは、図１６や図１８に示す三次元位置計測装置の画像メモリ７１から供給される。また、縮小データ（縮小比率）、カメラデータ、探索結果判断用の基準（例えば、回帰距離に対する所定範囲内）等のデータはパラメータメモリ７２から、元画像の計測位置のデータは計測位置指定部７３からそれぞれ供給される。
【００８５】
［縮小画像型回帰的対応点探索方法による対応点探索装置］
図１４、図１５を参照して、本発明の実施形態例に係る対応点探索装置として、上記「縮小画像型回帰的対応点探索方法」を実現する対応点探索装置を説明する。図１４は本実施形態例に係る対応点探索装置を示すブロック図であり、図１５は図１４中の縮小画像対応点探索部５１、５４それぞれの構成例を示すブロック図である。
【００８６】
図１４に示すように、当該対応点探索装置は、第１の縮小画像対応点探索部５１、元画像・参照画像設定入れ換え部５２、計測位置（回帰）設定部５３、第２の縮小画像対応点探索部５４、回帰距離計算部５５、探索結果判断部５６、対応箇所設定部５７、パッチ設定部５８及び通常画像対応点検出部５９を有している。この対応点探索装置には、通常画像、その縮小画像、元画像における計測位置、計測データ、縮小比率（縮小データ）が与えられる。計測データとしては、カメラデータ、探索結果判断用の基準（例えば、回帰距離に対する範囲）等が与えられる。
【００８７】
第１の縮小画像対応点探索部５１は計測位置、計測データ、縮小画像を元に、縮小画像における対応点を検出するものであり、図１５に示す例では、計測点変換部６１、エピポーラライン設定部６２、エピポーラライン変換部６３、縮小パッチ設定部６４、縮小画像対応点検出部６５を有している。これらのうち、計測点変換部６１は、通常画像（元画像）における計測位置と計測データ（カメラデータ、縮小比率）から、縮小画像における計測位置（縮小）を計算し、設定するものである。エピポーラライン設定部６２は、元画像における計測位置と計測データ（カメラデータ）から、通常画像（参照画像）におけるエピポーララインを計算し、設定するものである。エピポーラライン変換部６３は、エピポーラライン設定部６２で設定された参照画像におけるエピポーララインと計測データ（カメラデータ、縮小比率）から、参照画像の縮小画像におけるエピポーラライン（縮小）を計算し、設定するものである。縮小パッチ設定部６４は、縮小画像と計測データ（縮小比率）を元に、元画像の縮小画像（計測位置（縮小）を設定した方の縮小画像）において縮小パッチを設定するものである。縮小画像対応点検出部６５は、参照画像の縮小画像（もう一方の縮小画像）のエピポーラライン（縮小）上の探索範囲に関して対応点（縮小）を相関計算によって検出するものである。
【００８８】
従って、第１の縮小画像対応点探索部５１は縮小画像における対応点（縮小）を検出する。
【００８９】
元画像・参照画像設定入れ換え部５２は、元画像と参照画像の設定を入れ換えるものである。即ち、元画像を参照画像に、参照画像を元画像に入れ換え設定する。
【００９０】
計測位置（回帰）設定部５３は、第１の縮小画像対応点探索部５１により検出された対応点（縮小）を計測位置（回帰）として、入れ換え設定した後の元画像の縮小画像に設定するものである。
【００９１】
第２の縮小画像対応点探索部５４は、計測位置（回帰）、計測データ、縮小画像（回帰）を元に、入れ換え設定した後の参照画像の縮小画像における回帰対応点を検出するものであり、具体的には、図１５に示すもののうち、計測点変換部６１を除き、エピポーラライン設定部６２、エピポーラライン変換部６３、縮小パッチ設定部６４及び縮小画像対応点検出部６５を有している。これらのうち、エピポーラライン設定部６２は、計測位置（回帰）と計測データ（カメラデータ）から、参照画像におけるエピポーラライン（回帰）を計算し、設定する。エピポーラライン変換部６３は、計測データ（縮小比率）とエピポーラライン設定部６２により設定されたエピポーラライン（回帰）から、参照画像の縮小画像におけるエピポーラライン（回帰・縮小）を計算し、設定する。縮小パッチ設定部６４は、元画像の縮小画像において縮小パッチ（回帰）を設定する。縮小画像対応点検出部６５は、参照画像の縮小画像のエピポーラライン（回帰・縮小）上の探索範囲に関して回帰対応点（以降「回帰対応点」と呼ぶ）を相関計算によって検出する。
【００９２】
従って、第２の縮小画像対応点探索部５４は縮小画像における回帰対応点を検出する。
【００９３】
回帰距離計算部５５は、縮小画像において、計測位置（縮小）と回帰対応点から回帰距離（以降「回帰距離（縮小）」と呼ぶ）を計算する。
【００９４】
探索結果判断部５６は、回帰距離（縮小）を基に対応点探索結果の是非を判断する。例えば、回帰距離（縮小）が所定範囲外(NO)であれば処理を中断し、所定範囲内(YES) であれば対応点（縮小）が適切であると判断する。
【００９５】
対応箇所設定部５７は、回帰距離（縮小）が所定範囲内(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) 〜(5) により三次元位置計測を行う。
(1) 左右画像を入力する（ステップＳ９１）。
(2) 計測位置を一方の通常画像（元画像）で指定する（ステップＳ９２）。
(3) 上記「基本型回帰的対応点探索方法」により対応点探索を行い、もう一方の通常画像（参照画像）上に対応点を得る（ステップＳ９３）。
(4) 対応点探索結果を確認する（ステップＳ９４）。対応点が不適切(NO)と判断された場合は、処理を中断する。
(5) 対応点が適切(YES) と判断された場合は、計測位置、対応点、カメラデータから三次元位置を計算する（ステップＳ９５）。
【０１４２】
また、図２５に示した「三次元位置計測方法」における誤差を小さく抑えるため、上記「基本型回帰的対応点探索方法」で得られる対応点を対応点実数化方式により再計算するようにしても良い。その処理手順は図２６のフローチャートに示し、次の手順(1) 〜(7) によりステレオ画像から三次元位置計測を行う。
(1) 左右画像を入力する（ステップＳ１０１）。
(2) 計測位置を一方の通常画像（元画像）で指定する（ステップＳ１０２）。
(3) 上記「基本型回帰的対応点探索方法」により対応点探索を行い、もう一方の通常画像（参照画像）上に対応点を得る（ステップＳ１０３）。
(4) 対応点探索結果を確認する（ステップＳ１０４）。対応点が不適切(NO)と判断された場合は、処理を中断する。
(5) 対応点が適切(YES) と判断された場合は、上記「直線型対応点実数化方式」または「二次曲線型対応点実数化方式」等の対応点実数化方式により、対応点の再計算を行う（ステップＳ１０５）。
(6) 対応点が適切であると判断された場合は、計測位置、再計算で得た対応点、カメラデータから三次元位置を計算する（ステップＳ１０６）。
【０１４３】
他の対応点探索装置として、図２７を参照して、上記「基本型回帰的対応点探索方法」を実現する装置を説明する。図２７に示すように、当該対応点探索装置は、第１のエピポーラライン設定部８１、第１の通常画像対応点探索部８２、元画像・参照画像設定入れ換え部８３、計測位置（回帰）設定部８４、第２のエピポーラライン設定部８５、第２の通常画像対応点探索部８６、回帰距離計算部８７及び探索結果判断部８８を有している。
【０１４４】
これらのうち、第１のエピポーラライン設定部８１は、計測位置と計測データに基づいて、エピポーララインを設定する。計測データには、カメラデータ、回帰距離に対する所定範囲等が含まれる。第１の通常画像対応点探索部８２は、通常画像（元画像と参照画像）、計測位置、計測データ及び第１のエピポーラライン設定部８１により設定されたエピポーララインを入力して対応点を検出する。元画像・参照画像設定入れ換え部８３は、元画像と参照画像の設定を入れ換える。即ち、元画像を参照画像に、参照画像を元画像に再設定する。計測位置（回帰）設定部８４は、第１の通常画像対応点探索部８２で検出した対応点を計測位置（回帰）として再設定後の元画像に設定する。第２のエピポーラライン設定部８５は、計測位置（回帰）とカメラデータ等の計測データから、入れ換え設定された参照画像におけるエピポーラライン（回帰）を設定する。第２の通常画像対応点探索部８６は、元画像と参照画像が入れ換わった通常画像、エピポーラライン（回帰）及び計測位置（回帰）を入力して、回帰対応点を検出する。回帰距離計算部８７は、計測位置と回帰対応点から回帰距離を計算する。探索結果判断部８８は、回帰距離を基に対応点探索結果の是非を判断するものであり、例えば、回帰距離が所定範囲内であれば第１の通常画像対応点探索部８２で検出した対応点が適切(YES) であると判断する。所定範囲外であれば不適切(NO)であると判断する。
【０１４５】
かくして、図２７に示す「基本型回帰的対応点探索方法による対応点探索装置」においては、計測位置とカメラデータからエピポーララインを設定し、第１の通常画像対応点探索部８２により対応点を検出し、元画像を参照画像に、参照画像を元画像にそれぞれ再設定し、第１の通常画像対応点探索部８２で検出した対応点を計測位置（回帰）として設定し、計測位置（回帰）とカメラデータからエピポーラライン（回帰）を設定し、第２の通常画像対応点探索部８６により回帰対応点を検出し、計測位置と回帰対応点から回帰距離を計算し、回帰距離を元に対応点探索の是非を判断する。
【０１４６】
ここで、通常画像のデータは、図２８や図２９に示す三次元位置計測装置の画像メモリ７１から供給される。また、カメラデータ、回帰距離に対する所定範囲内等の計測データはパラメータメモリ７２から、計測位置のデータは計測位置指定部７３からそれぞれ供給される。
【０１４７】
次に、図２８を参照して、他の三次元位置計測装置として、図２６に示した上記「他の三次元位置計測方法」を実現する装置を説明する。
【０１４８】
図２８に示すように、当該三次元位置計測装置は、画像メモリ７１、パラメータメモリ７２、計測位置指定部７３、画像入力部７４、基本型回帰的対応点探索部９１及び三次元位置計算部７７を有している。これらのうち、画像メモリ７１は、画像入力部７４を介して供給される通常の画像データを記憶する。パラメータメモリ７２は、縮小データ及びカメラデータ、回帰距離の所定範囲等、当該三次元位置計測に必要な計測データを、パラメータとして記憶している。計測位置指定部７３は所望の計測位置を指定することができるようになっている。基本型回帰的対応点探索部９１は図２７に示した構成の対応点探索装置であり、通常画像のデータ、計測点のデータ及びエピポーララインのデータに基づき、回帰的処理により、対応点のデータを計算で求める。三次元位置計算部７７は、対応点のデータ、計測位置のデータ及びカメラデータに基づき、対象物の三次元位置を計算により求める。
【０１４９】
かくして、当該三次元位置計測装置は、左右画像を入力し、計測位置を通常画像の一方で指定し、基本型回帰的対応点探索方法により対応点を検出し、この対応点探索において対応点が不適切(NO)であればここで処理を中断し、適切な場合 (YES)は計測位置、対応点、カメラデータから三次元位置を計算する。
【０１５０】
次に、図２９を参照して、図２８に示した三次元位置計測装置に対し、対応点実数化部９２を追加した三次元位置計測装置を説明する。従って、図２９中で、図２８と同一部分には同一符号を付し、重複する説明を省略する。
【０１５１】
対応点実数化部９２は、図１８や図１９中の対応点実数化部７９と同様、例えば上記「直線型対応点実数化方式」あるいは「二次曲線型対応点実数化方式」等、対応点の補間演算の計算を実行する。
【０１５２】
かくして、当該三次元位置計測装置は、左右画像を入力し、計測位置を通常画像の一方で指定し、基本型回帰的対応点探索方法により対応点を検出し、この対応点探索において対応点が不適切(NO)であればここで処理を中断し、適切な場合 (YES)は対応点実数化方式により対応点を再計算し、計測位置、再計算で得た対応点、カメラデータから三次元位置を計算する。
以上の各方法の手順も記録媒体にコンピュータプログラムとして記録して、該当する装置をコンピュータで実現することができる。
【０１５３】
【発明の効果】
本発明によれば、下記の効果がある。
(1) 対応点探索において元画像と参照画像間で回帰的な処理を行い、対応点探索結果の是非を判断するため、対応点間違いを排除することができる。
(2) 対応点探索において元画像と参照画像間で回帰的な処理を行い、対応点探索結果の是非を判断するため、検出した対応点の信頼性が大きい。
(3) 検出した対応点の信頼性が大きいため、位置計測装置としての信頼性が向上する。
(4) 対応点間違いによる不適切な位置計測を排除できるため、複数点の位置計測により、位置計測対象部品の全体としての位置計測精度が向上する。
(5) 位置計測対象部品の位置計測精度が向上するため、高精度位置決めを要する作業に対応できる。
【０１５４】
(6) 対応点の広範囲な探索を縮小画像で行い、その対応箇所近傍についてのみ通常画像により探索を行い、回帰対応点の広範囲な探索も縮小画像で行い、その対応箇所近傍についてのみ通常画像により探索を行う行うことにより、高速な処理でかつ従来の精度を確保することができる。
(7) 広範囲の探索を縮小画像で行い、対応箇所近傍についても縮小画像で行って回帰対応点を検出することにより、高速な処理でかつ従来の精度を確保することができる。
(8) 対応点探索に対応点実数化処理を組み合わせることにより、高精度な三次元位置計測が実現する。
(9) 高速な三次元位置計測が実現できるため、作業時間に余裕がある場合、複数回の三次元位置計測を行うことができ、これにより、計測データの精度を向上させることができる。
(10)高速な三次元位置計測が実現できるため、作業時間に余裕がある場合、複数回の三次元位置計測を行うことができ、これにより、計測データの信頼性をより向上させることができる。
(11)対応点処理に要する処理時間が短いため、高速な処理を要する作業にも対応できる。
【図面の簡単な説明】
【図１】本発明の実施形態例に係る基本型回帰的対応点探索方法を説明する模式図。
【図２】基本型回帰的対応点探索方法の処理手順を示すフローチャート。
【図３】段階解像度画像による対応点探索方法を説明する模式図。
【図４】段階解像度画像による対応点探索方法の処理手順を示しフローチャート。
【図５】本発明の実施形態例に係る直列型回帰的対応点探索方法の処理手順を示すフローチャート。
【図６】本発明の実施形態例に係る縮小画像型回帰的対応点探索方法の処理手順を示すフローチャート。
【図７】本発明の実施形態例に係る三次元位置計測方法１の処理手順を示すフローチャート。
【図８】本発明の実施形態例に係る三次元位置計測方法２の処理手順を示すフローチャート。
【図９】二次曲線型対応点実数化方式による対応点再計算の例を模式的に示す図。
【図１０】本発明の実施形態例に係る三次元位置計測方法３の処理手順を示すフローチャート。
【図１１】本発明の実施形態例に係る三次元位置計測方法４の処理手順を示すフローチャート。
【図１２】本発明の実施形態例に係る直列型回帰的対応点探索方法による対応点探索装置の構成を示す図。
【図１３】図１２中の段階解像度対応点探索部の構成例を示す図。
【図１４】本発明の実施形態例に係る縮小画像型回帰的対応点探索方法による対応点探索装置の構成を示す図。
【図１５】図１３中の縮小画像対応点探索部の構成例を示す図。
【図１６】本発明の実施形態例に係る三次元位置計測装置１の構成を示す図。
【図１７】本発明の実施形態例に係る三次元位置計測装置２の構成を示す図。
【図１８】本発明の実施形態例に係る三次元位置計測装置３の構成を示す図。
【図１９】本発明の実施形態例に係る三次元位置計測装置４の構成を示す図。
【図２０】従来技術に係る「相関マッチングの対応点位置計測方法」の原理となる相関値変化の対称性を示す説明図。
【図２１】「相関マッチングの対応点位置計測方法」における補間式の第１の導出方法を示す説明図。
【図２２】「相関マッチングの対応点位置計測方法」における補間式の第２の導出方法を示す説明図。
【図２３】「相関マッチングの対応点位置計測方法」における補間式の第３の導出方法を示す説明図。
【図２４】「相関マッチングの対応点位置計測方法」における補間式の第４の導出方法を示す説明図。
【図２５】本発明の実施形態例に係る他の三次元位置計測方法の処理手順を示すフローチャート。
【図２６】本発明の実施形態例に係る更に他の三次元位置計測方法の処理手順を示すフローチャート。
【図２７】本発明の実施形態例に係る基本型回帰的対応点探索方法による対応点探索装置の構成を示す図。
【図２８】本発明の実施形態例に係る他の三次元位置計測装置の構成を示す図。
【図２９】本発明の実施形態例に係る更に他の三次元位置計測装置の構成を示す図。
【符号の説明】
１  元画像（入れ換え設定後の参照画像）
２  参照画像（入れ換え設定後の元画像）
３  計測位置
４  対応点
５  計測位置（回帰）
６  回帰対応点
７  エピポーラライン
８  エピポーラライン（回帰）
２１  通常画像（元画像、参照画像）
２２  縮小画像（元画像の縮小画像、参照画像の縮小画像）
２３  計測位置
２４  エピポーラライン
２５  計測位置（縮小）
２６  エピポーラライン（縮小）
２７  対応点（縮小）
２８  対応箇所
【図１】
0003906615.tif 000004
【図２】
0003906615.tif 000005
【図３】
0003906615.tif 000006
【図４】
0003906615.tif 000007
【図５】
0003906615.tif 000008
【図６】
0003906615.tif 000009
【図７】
0003906615.tif 000010
【図８】
0003906615.tif 000011
【図９】
0003906615.tif 000012
【図１０】
0003906615.tif 000013
【図１１】
0003906615.tif 000014
【図１２】
0003906615.tif 000015
【図１３】
0003906615.tif 000016
【図１４】
0003906615.tif 000017
【図１５】
0003906615.tif 000018
【図１６】
0003906615.tif 000019
【図１７】
0003906615.tif 000020
【図１８】
0003906615.tif 000021
【図１９】
0003906615.tif 000022
【図２０】
0003906615.tif 000023
【図２１】
0003906615.tif 000024
【図２２】
0003906615.tif 000025
【図２３】
0003906615.tif 000026
【図２４】
0003906615.tif 000027
【図２５】
0003906615.tif 000028
【図２６】
0003906615.tif 000029
【図２７】
0003906615.tif 000030
【図２８】
0003906615.tif 000031
【図２９】
0003906615.tif 000032