(57)【要約】【課題】計測対象から取得した２つの画像間のマッチング演算を行う際に、高精度のマッチング結果を短時間で得ることができる画像処理装置、画像処理方法、および、プログラムを提供する。【解決手段】ＤＰマッチングを用いたステレオ計測において、フレーム間で対応する画素の輝度値に変化がない領域については、前のフレームにおける経路探索結果を継承する。また、１つのフレーム処理において、隣接する走査線間で対応する画素の輝度値に変化がない領域については、１つ前の走査線における経路探索結果を継承する。【選択図】図１
2006331108.tif 000002
【特許請求の範囲】
【請求項１】
一定期間ごとに、物体の２次元画像として第１画像を取得する第１撮像手段と、
当該第１撮像手段と水平方向に所定の距離だけ離れた場所に位置し、前記一定期間ごとに、前記物体の２次元画像として第２画像を取得する第２撮像手段と、
前記第１および第２画像のエピポーラ線上に沿った画素の順で、その画素間の画素値の差分に応じたコストの累積値を最小にする前記画素間の対応付けを探索する探索手段と、
前記第１または第２画像のいずれかの画像を基準画像として、当該基準画像のＮ番目画像（Ｎ：２以上の整数）とＮ−１番目画像間とで、対応する画素間の画素値の変化が基準値よりも小さい第１領域を検出する検出手段と、
前記探索手段によるＮ−１番目画像の前記第１領域の探索結果を引き継ぐことで、前記探索手段によるＮ番目の探索対象領域を制限する制限手段と、
を備えた画像処理装置。
【請求項２】
Ｎ番目の基準画像において、隣接するエピポーラ線上の画素間の画素値の変化が基準値よりも小さい第２領域を検出する第２検出手段と、
前記第２領域では、隣接するエピポーラ線の間で探索結果を引き継ぐことで、前記探索手段によるＮ番目画像の探索対象領域を制限する第２制限手段と、
をさらに備えた請求項１記載の画像処理装置。
【請求項３】
エピポーラ線上における前記基準画像のエッジを画素単位で検出するエッジ検出部と、
当該エッジ検出位置において対応付けられた画素の位置に応じて、前記探索手段による、それ以降の探索対象領域を制限する第３制限手段と、
をさらに備えた請求項１または２記載の画像処理装置。
請求項１または２記載の画像処理装置。
【請求項４】
一定期間ごとに物体の２次元画像を処理する画像処理方法であって、
水平方向に所定の距離だけ離れた場所から、前記物体の２次元画像として、Ｎ−１番目（Ｎ：２以上の整数）の第１画像および第２画像を取得する第１工程と、
前記Ｎ−１番目の第１および第２画像のエピポーラ線上に沿った画素の順で、その画素間の画素値の差分に応じたコストの累積値を最小にする前記画素間の対応付けを探索する第２工程と、
Ｎ番目の前記第１画像および第２画像を取得する第３工程と、
前記第１または第２画像のいずれかの画像を基準画像として、当該基準画像のＮ番目画像とＮ−１番目画像間とで、対応する画素間の画素値の変化が基準値よりも小さい第１領域を検出する第４工程と、
Ｎ番目の第１画像および第２画像に基づいて画素間の対応付けを探索するときに、Ｎ−１番目画像の前記第１領域の探索結果を引き継ぐことで、Ｎ番目の探索対象領域を制限する第５工程と、
を備えた画像処理方法。
【請求項５】
前記第２工程は、
Ｎ番目の基準画像において、隣接するエピポーラ線上の画素間の画素値の変化が基準値よりも小さい第２領域を検出する第６工程と、
前記第２領域では、隣接するエピポーラ線の間で探索結果を引き継ぐことで、前記探索手段によるＮ番目画像の探索対象領域を制限する第７工程と、
をさらに備えた請求項４記載の画像処理方法。
【請求項６】
一定期間ごとに物体の２次元画像を処理する画像処理のプログラムであって、
水平方向に所定の距離だけ離れた場所から、前記物体の２次元画像として取得された、Ｎ−１番目（Ｎ：２以上の整数）の第１画像および第２画像を取り込む第１手順と、
前記Ｎ−１番目の第１および第２画像のエピポーラ線上に沿った画素の順で、その画素間の画素値の差分に応じたコストの累積値を最小にする前記画素間の対応付けを探索する第２手順と、
Ｎ番目の前記第１画像および第２画像を取り込む第３手順と、
前記第１または第２画像のいずれかの画像を基準画像として、当該基準画像のＮ番目画像とＮ−１番目画像間とで、対応する画素間の画素値の変化が基準値よりも小さい第１領域を検出する第４手順と、
Ｎ番目の第１画像および第２画像に基づいて画素間の対応付けを探索するときに、Ｎ−１番目画像の前記第１領域の探索結果を引き継ぐことで、Ｎ番目の探索対象領域を制限する第５手順と、
をコンピュータに実行させるプログラム。
【請求項７】
前記第２手順は、
Ｎ番目の基準画像において、隣接するエピポーラ線上の画素間の画素値の変化が基準値よりも小さい第２領域を検出する第６手順と、
前記第２領域では、隣接するエピポーラ線の間で探索結果を引き継ぐことで、前記探索手段によるＮ番目画像の探索対象領域を制限する第７手順と、
をさらに備えた請求項６記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計測対象である物体の２次元情報を取得し、その２次元情報に基づいて、その物体の３次元情報を推定する画像処理技術に関する。
【背景技術】
【０００２】
従来から非接触で対象物体の３次元情報を取得する手法として、ステレオ計測が知られている。このステレオ計測による３次元情報取得手法は、異なる視点から対象物体の画像を取得し、各視点の位置関係と各画像の見え方の違いから対象物体の３次元情報を得るというものである。
【０００３】
例えば、図１に示すように、平行かつ等位に置かれた複数（この場合、２つ）のカメラからの複数の画像（左画像、右画像）を取得し、その中の１つの画像、例えば左画像を基準画像とする。そして、計測対象の物体２上の点Ａ，Ｂに対応する、基準画像（左画像）の座標上での位置Ａ１，Ｂ１と、右画像の座標上での位置Ａ２，Ｂ２との差（視差）と、視点位置と視線方向から三角測量の原理に基づいて、点Ａ，Ｂまでの距離を算出する。
【０００４】
通常、ステレオ視による３次元情報の取得を行う場合、１つの基準となる画像上の点が、その他の画像上のどの点に対応しているかを対応点探索（マッチング演算）によって認識する。そして、一方の画像上にある点に対して、その対応点は、他方の画像内のある直線上に存在する。一般に、この直線をエピポーラ線（Epipolar Line）と呼ぶ。
したがって、図１に示すように、２つの同一のカメラが平行かつ等位に置かれた場合には、エピポーラ線が水平となり、水平方向の一次元探索でマッチングをとることができる。
このような水平方向の一次元探索でのマッチングを高精度に行う手法として、例えば下記非特許文献１に記載された技術が開示されている。
【０００５】
【非特許文献１】宇都木修一、鈴木寿、“高速ステレオ計測のためのＤＰマッチングの近似手法”、電子情報通信学会技術報告、Vol.104, No.290, pp.165-170, Sep.2004.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、上記非特許文献１に記載された技術は、エピポーラ線上において、左画像および右画像の対応する画素間の輝度値の差分に応じたコストの累積値を最小にするように一次元探索を行う、動的計画法（ＤＰ：Dynamic Programming）を用いたマッチング（以下、ＤＰマッチングという）を行っているため、マッチング精度に優れるものの、エピポーラ線上のほぼすべての画素に対してＤＰマッチング（経路探索演算）を行っているので、計算量が非常に多い。それゆえ、処理対象が動画となる場合には、実時間処理が困難である。
【０００７】
本発明は、上述した観点によってなされたものであって、その目的は、計測対象から取得した２つの画像間のマッチング演算を行う際に、高精度のマッチング結果を短時間で得ることができる画像処理装置、画像処理方法、および、プログラムを提供することにある。
【課題を解決するための手段】
【０００８】
上記課題を克服するために、本発明の第１の観点は、一定期間ごとに、物体の２次元画像として第１画像を取得する第１撮像手段と、当該第１撮像手段と水平方向に所定の距離だけ離れた場所に位置し、前記一定期間ごとに、前記物体の２次元画像として第２画像を取得する第２撮像手段と、前記第１および第２画像のエピポーラ線上に沿った画素の順で、その画素間の画素値の差分に応じたコストの累積値を最小にする前記画素間の対応付けを探索する探索手段と、前記第１または第２画像のいずれかの画像を基準画像として、当該基準画像のＮ番目画像（Ｎ：２以上の整数）とＮ−１番目画像間とで、対応する画素間の画素値の変化が基準値よりも小さい第１領域を検出する検出手段と、前記探索手段によるＮ−１番目画像の前記第１領域の探索結果を引き継ぐことで、前記探索手段によるＮ番目の探索対象領域を制限する制限手段と、を備えた画像処理装置である。
【０００９】
上記課題を克服するために、本発明の第２の観点は、一定期間ごとに物体の２次元画像を処理する画像処理方法であって、水平方向に所定の距離だけ離れた場所から、前記物体の２次元画像として、Ｎ−１番目（Ｎ：２以上の整数）の第１画像および第２画像を取得する第１工程と、前記Ｎ−１番目の第１および第２画像のエピポーラ線上に沿った画素の順で、その画素間の画素値の差分に応じたコストの累積値を最小にする前記画素間の対応付けを探索する第２工程と、Ｎ番目の前記第１画像および第２画像を取得する第３工程と、前記第１または第２画像のいずれかの画像を基準画像として、当該基準画像のＮ番目画像とＮ−１番目画像間とで、対応する画素間の画素値の変化が基準値よりも小さい第１領域を検出する第４工程と、Ｎ番目の第１画像および第２画像に基づいて画素間の対応付けを探索するときに、Ｎ−１番目画像の前記第１領域の探索結果を引き継ぐことで、Ｎ番目の探索対象領域を制限する第５工程と、を備えた画像処理方法である。
【００１０】
上記課題を克服するために、本発明の第３の観点は、一定期間ごとに物体の２次元画像を処理する画像処理のプログラムであって、水平方向に所定の距離だけ離れた場所から、前記物体の２次元画像として取得された、Ｎ−１番目（Ｎ：２以上の整数）の第１画像および第２画像を取り込む第１手順と、前記Ｎ−１番目の第１および第２画像のエピポーラ線上に沿った画素の順で、その画素間の画素値の差分に応じたコストの累積値を最小にする前記画素間の対応付けを探索する第２手順と、Ｎ番目の前記第１画像および第２画像を取り込む第３手順と、前記第１または第２画像のいずれかの画像を基準画像として、当該基準画像のＮ番目画像とＮ−１番目画像間とで、対応する画素間の画素値の変化が基準値よりも小さい第１領域を検出する第４手順と、Ｎ番目の第１画像および第２画像に基づいて画素間の対応付けを探索するときに、Ｎ−１番目画像の前記第１領域の探索結果を引き継ぐことで、Ｎ番目の探索対象領域を制限する第５手順と、をコンピュータに実行させるプログラムである。
【発明の効果】
【００１１】
本発明によれば、計測対象から取得した２つの画像間のマッチング演算を行う際に、高精度のマッチング結果を短時間で得ることが可能となる。
【発明を実施するための最良の形態】
【００１２】
先ず、本発明と以下に述べる実施の形態との対応関係を記す。
本発明の第１撮像手段、第２撮像手段は、実施形態における左カメラ１０、右カメラ２０に対応する。
本発明の探索手段は、制御部３１の「累積距離算出処理」および「最適経路取得処理」により実現される。
本発明の検出手段は、制御部３１の「フレーム間の差分検出処理」により実現される。
本発明の第２検出手段は、制御部３１の「走査線間の差分検出処理」により実現される。
本発明の制限手段は、制御部３１の「フレーム間の差分検出処理」により実現される。
本発明の第２制限手段は、制御部３１の「走査線間の差分検出処理」により実現される。
本発明の第３制限手段は、制御部３１の「刈込み処理」により実現される。
本発明のエピポーラ線は、実施形態の説明における「走査線」に対応する。
【００１３】
以下、本発明の一実施形態を添付図面に関連付けて説明する。
本発明の一実施形態である３次元形状計測装置１は、計測対象の物体の２次元画像をステレオ視カメラによって取得し、エピポーラ線上において、得られた２つの２次元画像に対してマッチング演算（対応点探索）を行う。そして、その演算結果に基づいて計測対象の物体までの距離を推定する。
実施形態に係る３次元形状計測装置１は、マッチング演算に要する処理時間を極めて短時間で行うことを特徴としている。これによって、特に、計測対象の物体が動いている場合、すなわち、動画に基づいてフレーム単位で（実時間で）マッチング演算を行う場合に効果を奏する。
【００１４】
図１は、実施形態に係る３次元形状計測装置１の外観構成の一例を示す図である。
３次元形状計測装置１では、ステレオ視カメラとしての左カメラ１０および右カメラ２０は、全く同一のカメラであって、かつ、撮像を行う上での設定（たとえば、焦点距離、輝度調整など）は同一となっている。そして、左カメラ１０および右カメラ２０は、同一高さに、かつ、計測対象の物体２に向けて平行配置されている。したがって、本実施形態では、エピポーラ線が水平軸に常に平行であり、かつ、そのエピポーラ線である同一の水平ライン上で、左画像および右画像の一次元マッチング問題を想定することができる。
【００１５】
図２は、実施形態に係る３次元形状計測装置１のシステム構成を示すブロック図である。
図２に示すように、３次元形状計測装置１の画像処理装置３０は、制御部３１、画像インタフェース３２、メモリ３３、表示部３４を含んで構成され、各部はバス３５によって接続されている。
【００１６】
制御部３１は、マイクロコントローラを主体として含み、たとえばデータ転送制御、タイミング制御など画像処理装置３０の全体の制御を統括する。
制御部３１は、左カメラ１０および右カメラ２０に対して、同期した撮像指示信号をフレーム期間（たとえば、３０フレーム／秒であれば１／３０秒）ごとに送出する。これにより、左カメラ１０および右カメラ２０は、同時に物体２の撮像を開始する。
制御部３１は、左カメラ１０および右カメラ２０により撮像された画像データをそのフレーム期間内に、画像インタフェース３２を介して取得する。そして、１フレーム期間内に水平線を順に走査し、取得した画像データに基づいて画像処理を行う。
制御部３１で行われる様々な画像処理については、後に詳述する。
【００１７】
メモリ３３のＲＡＭ領域には、毎フレームごとのマッチング演算結果が格納される。後述するように、３次元形状計測装置１では、あるフレーム時点のマッチング演算を行う際に、１つ前のフレームにおけるマッチング演算結果を使用するため、少なくとも１フレーム期間、メモリ３３にマッチング演算結果を保持しておく。
また、後述するように、３次元形状計測装置１では、あるフレーム期間内の１走査線（エピポーラ線）に対するマッチング演算を行う際に、１つ前の走査線におけるマッチング演算結果を使用するため、少なくとも１走査期間、メモリ３３にマッチング演算結果を保持しておく。
【００１８】
次に、制御部３１で行われる画像処理について、以下の順序で説明する。
なお、以下の複数の処理は、（＊１）ＤＰマッチングを用いた３次元計測に必須の処理、（＊２）ＤＰマッチングの高速化のための処理、に大別できる。
【００１９】
［画像データの取り込み]（＊１）
［水平線の抽出処理]（＊１）
［特徴点の抽出処理]（＊２）
［輝度距離算出処理]（＊１）
［累積距離算出処理]（＊１）
［刈込み処理]（＊２）
［最適経路取得処理]（＊１）
［物体までの距離算出処理]（＊１）
［フレーム間の差分検出処理]（＊２）
［走査線間の差分検出処理]（＊２）
【００２０】
［画像データの取り込み]
画像処理装置３０では、左カメラ１０および右カメラ２０により生成された画像データをフレーム期間ごとに取り込む。
図３は、一例として略立方体の物体２に対して、左カメラ１０および右カメラ２０がそれぞれ撮像・生成した画像の一例であって、（ａ）は左画像、（ｂ）は右画像を示す。取り込まれた画像は、たとえば左画像を基準画像として、フレーム期間内に以降の処理が行われる。
【００２１】
なお、以降の処理の説明のために、取り込んだ画像について、以下のように定義する。すなわち、左画像（基準画像）の水平位置をｉ、画像の幅をＩとし、右画像の水平位置をｊ、画像の幅をＪとする。また、双方の画像において垂直位置をｈ、画像の高さをＨとする。さらに、ｔ番目フレームの左画像上の座標（ｉ，ｈ）における画素の輝度値をｅＬ（ｉ，ｈ，ｔ）、ｔ番目フレームの右画像上の座標（ｊ，ｈ）における画素の輝度値をｅＲ（ｊ，ｈ，ｔ）とする。
【００２２】
［水平線の抽出処理]
水平線の抽出処理では、エピポーラ線としての走査線（高さｈ）に対して、左画像および右画像から、走査線を中心とする幅２η＋１本の水平線（走査線自体も含む）を抜き出す処理を行う。
ＤＰマッチング演算では、走査線を下方から上方へ順にシフトさせ、異なる高さの走査線ごとに幅２η＋１本の水平線を抽出して、以下の処理を行う。各走査線に対して抽出された幅２η＋１本の水平線は、後述する輝度距離の算出に用いられる。
【００２３】
［特徴点の抽出処理]
特徴点の抽出処理では、左画像と右画像の相関を精度良くかつ高速に行うために、計測対象である物体２の特徴位置（特徴点）を、走査線ごとに抽出する。隣接する画素の輝度値の差が大きい位置で、物体の輪郭など物体２の外形上の特徴を示すことから、本処理では、基準画像である左画像の走査線上のすべての画素において、隣接する左（または右）の画素との輝度値の差分を算出し、この差分が一定の閾値以上であることを条件として、特徴点の抽出を行う。すなわち、画像上のエッジを画素単位で検出して、これを特徴点とする。
その際、走査線の両端点については、特徴点の対象としない。また、特徴点を多く算出し過ぎると、精度が維持できなくなるため、輝度値の差分が大きいものから数えて、所定のＮ個の点までを特徴点とする。また、高速化の妨げとなるため、隣接する特徴点が所定の閾値以上の間隔となるように、特徴点を抽出する。
特徴点の抽出結果は、刈込み処理、走査線間差分検出処理、フレーム間差分検出処理において探索範囲を絞り込むために利用される。
【００２４】
図４は、ある走査線上において、画像の水平軸と輝度値の差分との関係を図解した図である。図４において、Ｎは、たとえばユーザにより予め設定された特徴点の数、ｉｉｎｔは、特徴点同士の最小間隔を規定する閾値、を示す。
【００２５】
実際の処理では、この特徴点の数Ｎと閾値ｉｉｎｔに基づいて、制御部３１では、以下のように特徴点を抽出する。
すなわち、走査線上のすべての画素について、それぞれ隣接する画素との輝度値の差分を計算し、計算した輝度値の差分を大きい順に、その画素の位置と関連付けてメモリ３３に保存する。
次に、差分の順位が２番目以降の画素について、その上位にあるすべての画素（ｎ位の画素は１位の画素からｎ−１位までのすべての画素）との位置の差を計算する。位置の差がｉｉｎｔより小さいものが１つでもあった場合は、その画素を除外する。除外されずに残った上位Ｎ個の点を特徴点とする。
ここで、以降の処理の説明のため、画像の左端からｎ番目の特徴点のｉの値をｉｎと定義する。
【００２６】
図５は、上述した特徴点抽出処理の一例を図解する図である。
たとえば、走査線上のすべての画素について、輝度値の差分を計算し、計算した輝度値の差分を大きい順に並べた結果が図５に例示した結果であり、かつ、予め、Ｎ＝５およびｉｉｎｔ＝２０が与えられていた場合を想定する。
かかる場合には、順位３のｉ：２５６の画素については、これよりも上位の順位２のｉ：２４５の画素と比較して、位置の差分が閾値ｉｉｎｔ（＝２０）よりも小さいため、削除される。同様に、順位４のｉ：１２の画素については、これよりも上位の順位１のｉ：１０の画素と比較して、位置の差分が閾値ｉｉｎｔ（＝２０）よりも小さいため、削除される。
このようにして、図５に示す例では、位置：５６７，１７８，４１３の画素の順位が繰り上がって、５個の特徴点が抽出される。
【００２７】
［輝度距離算出処理]    
輝度距離算出処理は、次処理の累積距離算出処理において逐次実行される。
輝度距離とは、左画像（基準画像）上のある垂直ライン上に存在する複数の画素と、右画像上のある垂直ライン上に存在する複数の画素とに対して、水平ラインごとに対応する画素同士の輝度の距離を、以下の式（１）に示すようにユークリッド距離として定義したものである。この輝度距離が、ＤＰ演算において最適解に対するコストに相当する。
この輝度距離は、［水平線の抽出処理］で抽出された２η＋１本の水平線による範囲（水平位置：ｈ−η〜ｈ＋ηの範囲）において算出する。
【００２８】
【数１】
2006331108.tif 000003
【００２９】
なお、式（１）において、ｉ≧ｊのときｄ（ｉ，ｊ）＝∞（コンピュータで計算させる場合には、一般的に輝度距離がとり得る値と比較して十分に大きな値）とする。また、ｄ（ｉ，０）＝０，ｄ（Ｉ−１，ｊ）＝０とする。
【００３０】
図６は、輝度距離の算出例を図解する図である。
図６では、８つの水平線に対して、左画像の画素と、対応する右画像の画素に対して上記（１）式が演算され、特定のｉ，ｊに対し、輝度距離ｄ（ｉ，ｊ）として「６」が算出されている。
【００３１】
［累積距離算出処理]
本実施形態に係る３次元形状計測装置１では、走査線上において、左画像（基準画像）に対する右画像のマッチング演算を高精度に行うため、コストとしての輝度距離が最小となるようなＤＰマッチング演算を用いる。
本実施形態では、走査線がエピポーラ線となっているので、走査線上における左画像と右画像の画素間を対応付けを、走査線上に沿って輝度距離を累積した累積距離が最小となるような経路を探索することにより決定する。この経路探索は、（ｉ，ｊ）が（０，０）から（Ｉ−１，Ｊ−１）までの範囲で、かつ、ｊが増加する方向に探索する。
【００３２】
具体的に、累積距離は、（ｉ，ｊ）を（０，０）から（Ｉ−１，Ｊ−１）まで、ｉ＞ｊの範囲に対し、下記式（２）に示すように算出する。
なお、下記式（２）において、ｉ≧ｊまたはｉ＜０またはｊ＜０のとき、Ｄ（ｉ，ｊ）＝∞（コンピュータで計算させる場合には、一般的に累積距離がとり得る値と比較して十分に大きな値）とする。また、Ｄ（０，０）＝０とする。
【００３３】
【数２】
2006331108.tif 000004
【００３４】
式（２）において、λは、（ｉ−１，ｊ−１）から（ｉ，ｊ）へ経路を探索する際のチューニングパラメータである。すなわち、（ｉ−１，ｊ−１）から（ｉ，ｊ）への経路は、斜め方向である点で隣接画素間の経路と異なるため、アプリケーションに応じてλを変更することで、画素間の対応付けを調整できるようにしている。
【００３５】
図７は、累積距離の算出例を図解する図である。
図７に示すように、探索処理において、（ｉ，ｊ）に達するには３つの経路、すなわち、（ｉ−１，ｊ）→（ｉ，ｊ），（ｉ−１，ｊ−１）→（ｉ，ｊ），（ｉ，ｊ−１）→（ｉ，ｊ）の経路があり得る。そして、水平位置（ｉ，ｊ）の累積距離Ｄ（ｉ，ｊ）を求める際には、式（２）に従って上記３つの経路の中でどの経路を選択したかをメモリ３３に逐次記憶しておく。たとえば、経路を記憶しておく配列をｋとして、（ｉ，ｊ−１）から（ｉ，ｊ）への経路を採用した場合は、ｋ（ｉ，ｊ）＝（ｉ，ｊ−１）を配列ｋに書き込む。
【００３６】
図７に示した例では、（ｉ，ｊ−１）における累積距離Ｄ（ｉ，ｊ−１）：１３に対して、（ｉ，ｊ−１）〜（ｉ，ｊ）間の輝度距離ｄ（ｉ，ｊ）：３２を加えた累積距離Ｄ（ｉ，ｊ）：４５が３つの経路の中で最小になるため、（ｉ，ｊ−１）→（ｉ，ｊ）の経路が採用される。そして、配列ｋに対して、「ｋ（ｉ，ｊ）＝（ｉ，ｊ−１）」が書き込まれる。
【００３７】
［刈込み処理]
刈込み処理は、すでに算出しておいた特徴点を用いて、上述した経路探索を高精度かつ高速に行うための処理である。刈込み処理は、経路探索中に特徴点ｉｎに到達したときに、実行され、（ｉ，ｊ）領域において経路探索を行う必要がない領域を特定する。
【００３８】
具体的には、経路の探索（ｉ，ｊを変化させながら累積距離Ｄ（ｉ，ｊ）の逐次計算）中に、ｉ＝ｉｎ（ｉｎ：ｎ番目の特徴点）達した場合には、ｉ＝ｉｎである全ての画素について、累積距離Ｄ（ｉｎ，ｊ）を計算し、その累積距離Ｄ（ｉｎ，ｊ）をｉｎ＋ｊで除算する。そして、その除算結果が最も小さくなるｊをｊｎとする。すなわち、下記の式（３）が成立するｊをｊｎとする。
なお、累積距離Ｄ（ｉｎ，ｊ）をｉｎ＋ｊで除算するのは、（０，０）から（ｉｎ，ｊ）までの距離に応じてｊｎの決定が影響を受けないように、正規化するためである。
【００３９】
【数３】
2006331108.tif 000005
ただし、ｊ−１＝０。
【００４０】
そして、ｊｎを算出した後の経路探索（ｉ＞ｉｎの範囲の探索）では、ｊ＜ｊｎとなる範囲の探索を行わない。すなわち、特徴点における対応位置（ｉｎ，ｊｎ）のマッチング精度は十分に高いと判断でき、累積距離がＤ（ｉｎ，ｊ）よりも大きくなる範囲、すなわちｊｎより小さいｊの範囲は探索する必要がないので行わない。
図８は、刈込み処理を図解した図であるが、上記（３）式の結果が最小となる位置（ｉｎ，ｊｎ）が決定された後、ｉ＞ｉｎの範囲の経路探索では、図の「刈込み領域」（ｊ＜ｊｎとなる範囲）を処理対象としない。
【００４１】
［最適経路取得処理]
以上のようにして、刈込み処理を行って探索範囲を絞り込みながら、経路探索を行う。
図９は、探索結果の一例を図解した図であるが、図に示すように、特徴点において特定された「刈込み領域」を探索対象から除去しながら、ｉ＞ｊの範囲で経路（図９において太い矢印で示す。）を探索する。すなわち、（ｉ，ｊ）を（０，０）から（Ｉ−１，Ｊ−１）までの累積距離Ｄ（ｉ，ｊ）を逐次求めていくことにより、累積距離Ｄ（Ｉ−１，Ｊ−１）を最小にする経路を算出する。
この最小にする経路は、たとえば下記の式（４）が示す形で、経路を決定するごとにメモリ３３内の配列ｋに順次書き込まれるため、式（４）において矢印で示すように、この配列ｋを逆に辿ることで、走査線上における、左画像および右画像の画素間のマッチング結果が得られる。
【００４２】
【数４】
2006331108.tif 000006
【００４３】
［物体までの距離算出処理]
以上のＤＰマッチング演算により、左画像と右画像の水平位置の対応付けがなされたため、三角測量の原理により、計測対象である物体２までの距離を算出することができる。
たとえば、左画像上の点ｉ０が右画像上の点ｊ０に対応しているとすると、左カメラ１０〜右カメラ２０間の距離ｂ、両カメラの焦点から撮像面までの距離ρを用いて、下記の式（５）に従って物体２までの距離ｄｉｓを算出する。そして、式（５）の演算をすべての（ｉ，ｊ）について行うことで、走査線上における物体２までの距離を推定することができる。
以上の処理をすべての走査線に対して行うことで、１フレームにおける物体２の３次元形状を推定することができる。
【００４４】
【数５】
2006331108.tif 000007
【００４５】
［フレーム間の差分検出処理]
上述した［画像データの取り込み]〜［物体までの距離算出処理]の処理は、１フレームにおいて得られた画像データに基づいて行われる処理であり、以上の処理がフレームごとに順次行われる。
そこで、物体２が動く場合、すなわち左画像および右画像が動画像である場合を想定する。かかる場合、ある画像領域においてフレームごとに変化がない（または小さい）ことがあるため、フレーム間の画像の差分を検出することで、前のフレームの計算結果（経路探索結果）を流用できる可能性がある。
したがって、本実施形態に係る３次元形状計測装置１では、フレーム間の差分（輝度差分）を検出することにより、フレームごとの計算量を削減し、実時間処理に適したＤＰマッチング処理を行う。
【００４６】
つまり、各フレームにおいてＤＰマッチング演算を行う前に、前回のフレームと現在のフレームにおける同一位置の画素の輝度値の差分を求め、この差分が小さいと判断した画像領域については、現在のフレームにおけるＤＰマッチング演算を行わず、当該画像領域については前回のフレームにおける演算結果を流用する。
なお、画素の輝度値の差分演算は、一方の画像、たとえば左画像（基準画像）のみについて行えばよい。
【００４７】
輝度値に変化があったか否かについての判断は、以下のように行う。
先ず、あらかじめ画素の輝度値の差分の閾値ｅｔｈと、閾値ｅｔｈを越えた画素の数に対する閾値Ｓｔｈを設定しておき、特徴点間の区間ごとに、ｔ番目フレームと（ｔ−１）番目フレーム（前回のフレーム）の画素の輝度値の差分が閾値ｅｔｈを越えた画素の数をカウントする。
すなわち、ｔ番目フレームにおいて左画像上の座標（ｉ，ｈ）の輝度差分値が閾値ｅｔｈを越えたか否かを示す値をδＦ（ｉ，ｈ，ｔ）（１：閾値ｅｔｈを越えた、０：閾値ｅｔｈを越えない）、特徴点位置（垂直軸位置）ｉｎから次の特徴点位置ｉｎ＋１までの区間内に、輝度差分値が閾値ｅｔｈを越えた画素の数をＳＦとすると、δＦ（ｉ，ｈ，ｔ）およびＳＦは、それぞれ、下記の式（６）および（７）に示すように算出される。
【００４８】
【数６】
2006331108.tif 000008
【００４９】
【数７】
2006331108.tif 000009
【００５０】
次に、カウント対象区間内において式（７）によって算出されたＳＦと、所定の閾値Ｓｔｈ（個）とを比較し、ＳＦが閾値Ｓｔｈよりも多い場合、その区間では画素の輝度値の変化を検出したと判断する。逆に、ＳＦが閾値Ｓｔｈよりも少ない場合、その区間では画素の輝度値の変化を検出しなかったと判断する。
【００５１】
上述した処理を具体例に基づいてさらに説明する。
図１０は、フレーム間の差分検出処理の一例を図解する図であって、（ａ）は（ｔ−１）番目フレームにおける、ある区間の複数の画素の輝度値、（ｂ）はｔ番目フレームにおける、同一区間の複数の画素の輝度値、（ｃ）は（ｔ−１）番目フレーム〜ｔ番目フレーム間の輝度差分、をそれぞれ示す。
図１０に例示した区間は、ｔ番目フレームにおいて抽出された３つの特徴点によって、図に示すように４つの区間ａ１〜ａ４に分割され、分割された区間ごとに、上述した画素の輝度値の変化を検出する。
【００５２】
図１０に示す例において、仮に閾値ｅｔｈを「１．５」、閾値Ｓｔｈを「３」に設定すると、区間ａ１およびａ２は、輝度差分がいずれも閾値ｅｔｈより小さいので、ＳＦ＝０となる。したがって、区間ａ１およびａ２では、画素の変化がないと判断され、この区間では、（ｔ−１）番目フレームの経路探索結果を流用（継承）する。区間ａ３では、いずれの閾値も越えるため、画素の輝度値の変化があると判断され、この区間では、ｔ番目フレームにおいて再度経路探索処理（再計算）を行う。区間ａ４では、閾値ｅｔｈを越える画素の数が１つのみであり、閾値Ｓｔｈを越えないため、（ｔ−１）番目フレームの経路探索結果を流用（継承）する。
このように、閾値ｅｔｈを越える画素の数を、処理対象区間における画素の輝度値の変化の判断に加えることで、フレーム間の誤差を排除しつつ、再計算領域を制限する（狭める）ことができる。
【００５３】
なお、画素の輝度値変化が検出された区間が複数連続する場合には、その複数の区間を１つの区間にまとめる。同様に、画素の変化が検出されなかった区間が複数連続する場合にも、その複数の区間を１つの区間にまとめる。
たとえば、図１０に示した例では、画素の輝度値変化が検出されなかった区間ａ１およびａ２は、１つの区間にまとめられる。
【００５４】
図１１は、（ｉ，ｊ）領域において、新しいフレームにおいて経路を再計算する再計算領域と、前のフレームの経路を継承する継承領域とを図解した図である。
あるフレームにおいて特徴点を抽出した後に、図１１に示すように、画素の輝度値変化が検出された区間は、「再計算領域」としてまとめられ、また、画素の輝度値変化が検出されなかった区間は、「承継領域」としてまとめられる。そして、そのフレームでは、図１１に示す点Ａから点Ｂまでの経路のみが探索される。
【００５５】
図１２は、再計算領域における計算結果と、継承領域における計算結果（前のフレームから流用された結果）との間の処理を図解した図である。
たとえば（ｔ−１）番目フレームでの計算結果（マッチング結果）は、少なくとも１フレーム期間の間メモリ３３に保持される。そして、ｔ番目フレームの処理において継承領域が確定されると、その継承領域の計算結果がメモリ３３から取り出される。なお、（ｔ−１）番目フレームでの計算結果は、図１２に示すように、配列ｋの形で（前述の式（４）参照）メモリ３３に格納されている。
そして、ｔ番目フレームでの計算結果（マッチング結果）を算出して、ｔ番目フレームにおける配列ｋの値が決定すると、図１１に矢印で示すように、配列ｋを逆に辿ることで、ｔ番目フレームにおいて、（０，０）から（Ｉ−１，Ｊ−１）までの（ｉ，ｊ）のマッチング結果が得られる。
以上説明した処理が走査線ごとに行われ、走査線上の対応する画素間でのマッチング演算対象領域が狭められる。
【００５６】
このようにして、本実施形態に係る３次元形状計測装置１では、フレーム間の差分（輝度差分）を検出することにより、フレームごとの計算量を削減し、実時間処理に適したＤＰマッチング処理を行う。
【００５７】
［走査線間の差分検出処理]
フレーム間の輝度差分に応じて計算量を削減する処理と同様に、走査線間の輝度差分に応じて、［画像データの取り込み]〜［物体までの距離算出処理]に要する計算量を削減することができる。
すなわち、あるフレームにおいて、隣接する走査線の画素の輝度値変化がない（または小さい）ことがあるため、走査線間の画素の輝度差分を検出することで、すでに計算が済んだ走査線の計算結果（経路探索結果）を次の計算対象の走査線に対して流用できる可能性がある。つまり、上述した［フレーム間の差分検出処理]における再計算領域について、さらに計算領域を制限できる（狭めることができる）余地がある。
かかる観点から、本実施形態に係る３次元形状計測装置１では、走査線間の差分（輝度差分）を検出することにより、１フレームにおける計算量を削減し、実時間処理に適したＤＰマッチング処理を行う。なお、隣接する走査線間の輝度値の差分演算は、一方の画像、たとえば左画像（基準画像）のみについて行えばよい。
【００５８】
以下、走査線間の差分検出処理の具体的処理について、図１３を参照して説明する。
図１３において、再計算領域ＲＡ１は、上述した［フレーム間の差分検出処理］によって限定された再計算領域（区間ａｑ＋１の領域）であり、左下端点が（ｉｑ，ｊｑ）、右上端点が（ｉｑ＋１，ｊｑ＋１）である。
先ず、すでに計算が終了している、高さ（ｈ−１）の走査線（１ライン下の走査線）における経路が、再計算領域ＲＡ１の左下端点（ｉｑ，ｊｑ）および右上端点（ｉｑ＋１，ｊｑ＋１）を通過しているか否かを確認する。そして、通過していない場合は、高さｈの走査線に対しては、再計算領域ＲＡ１の全領域を対象として、経路探索を行う。
【００５９】
一方、高さ（ｈ−１）の走査線における経路が、高さｈの走査線における再計算領域ＲＡ１の両端点を通過している場合には、以下の処理を行う。
先ず、あらかじめ画素の輝度値の差分の閾値ｅｔｈと、閾値ｅｔｈを越えた画素の数に対する閾値Ｓｔｈを設定しておく。区間ａｑ＋１内に存在する特徴点のうち、区間ａｑ＋１の左端から数えてζ個目の特徴点のｉの値をｉζとしたときに、ｉζとｉζ＋１を両端とする区間（特徴点間の区間）に対して、高さｈの走査線と高さ（ｈ−１）の走査線間で、対応する画素の輝度値の差分が閾値ｅｔｈを越えた画素の数をカウントする。
すなわち、高さｈの走査線における左画像上の座標（ｉ，ｈ）の輝度差分値が閾値ｅｔｈを越えたか否かを示す値をδＬ（ｉ，ｈ，ｔ）（１：閾値ｅｔｈを越えた、０：閾値ｅｔｈを越えない）、特徴点位置ｉζから次の特徴点位置ｉζ＋１までの区間内に、輝度差分値が閾値ｅｔｈを越えた画素の数をＳＬとすると、δＬ（ｉ，ｈ，ｔ）およびＳＬは、それぞれ、下記の式（８）および（９）に示すようにして算出される。
【００６０】
【数８】
2006331108.tif 000010
【００６１】
【数９】
2006331108.tif 000011
【００６２】
次に、カウント対象区間内において式（９）によって算出されたＳＬと、所定の閾値Ｓｔｈ個とを比較し、ＳＬが閾値Ｓｔｈよりも多い場合、その区間では画素の輝度値変化が検出されたと判断する。逆に、ＳＬが閾値Ｓｔｈよりも少ない場合、その区間では画素の輝度値変化が検出されなかったと判断する。
このように、閾値ｅｔｈを越える画素の数を、処理対象区間における画素の輝度値変化の判断に加えることで、走査線間の誤差を排除しつつ、再計算領域をさらに制限する（狭める）ことができる。
【００６３】
なお、画素の輝度値変化が検出された区間が複数連続する場合には、その複数の区間を１つの区間にまとめる。同様に、画素の輝度値変化が検出されなかった区間が複数連続する場合にも、その複数の区間を１つの区間にまとめる。
たとえば、図１３では、画素の輝度値変化が検出された区間によって、再計算領域ＲＡ１をさらに限定した、左下端点（ｉｐ，ｊｐ）および右上端点（ｉｐ＋１，ｊｐ＋１）を有する再計算領域ＲＡ２が生成される。
このように、本実施形態に係る３次元形状計測装置１では、図１３において、（ｉｐ，ｊｐ）から（ｉｐ＋１，ｊｐ＋１）までの累積距離Ｄ（ｉ，ｊ）に基づいて経路探索を行うだけでよい。そして、フレーム間の差分検出処理と同様に（図１２と示したのと同様に）、走査線間の承継領域に対しては、すでに行われた（一つ下の）走査線におけるマッチング結果を流用することで、大幅に計算量が削減される。
【００６４】
以上、制御部３１で行われる画像処理について説明した。次に、３次元形状計測装置１の動作について、図１４〜１７に示すフローチャートを参照して説明する。
【００６５】
図１４〜図１７に示すフローチャートは、１フレーム期間に処理されるべき、３次元形状計測装置１の処理内容を示す。
先ず、図１４において、３次元形状計測装置１は、１フレーム期間ごとに左カメラ１０および右カメラ２０から画像データを取り込む（ステップＳＴ１）。
本実施形態では、取り込んだ画像から、走査線を中心とする幅２η＋１本の水平線を抜き出す。したがって、走査線ｈは、ηを初期値として、η〜Ｈ−η（Ｈ：画像の高さ）の範囲で順に上方にシフトされ、走査線ごとに左右画像のマッチング処理を行う（ステップＳＴ２、ＳＴ３）。
ある走査線ｈを定めると、その走査線を中心とする幅２η＋１本の水平線が両画像から抽出され（ステップＳＴ４）、基準画像である左画像において、走査線ｈ上の特徴点の抽出（輝度によるエッジ検出）が行われる（ステップＳＴ５）。
【００６６】
次に、ＤＰマッチング演算を特徴点間の区間ごとに行う。なお、Ｎは予め設定された特徴点の数であり、ｐは、特徴点の区間ごとにＤＰマッチング演算が終了するとインクリメントされる変数である（ステップＳＴ６、ＳＴ７）。但し、本実施形態に係る３次元形状計測装置１では、ＤＰマッチング演算による経路探索を行う前に、処理対象フレームにおける計算対象の画像領域を制限する。
すなわち、最初に処理されるフレームであるか否か判別し（ステップＳＴ８）、最初に処理されるフレームでなければ、前回のフレームと今回のフレームとで、対応する画素同士の輝度値を比較して、フレーム間で画素の輝度変化があるか否かが判別され（ステップＳＴ９、ＳＴ１０）、輝度変化がないと判定されれば前回のフレームにおける計算結果の継承処理が行われる（ステップＳＴ１１）。これにより、再計算領域と継承領域が特定され、再計算領域のみ経路探索が行われる。
【００６７】
一方、フレーム間で輝度変化があると判定された場合には、その輝度変化があった再計算領域を特定し、その再計算領域において、走査線間の輝度変化に応じて、特定された再計算領域をさらに制限できないか（狭められないか）について判断する処理を行う。
この場合には、先ず、処理される走査線が最も下に位置する(高さη)走査線であるか否かを判別する（ステップ１３）。最も下に位置する走査線ではない場合には、特定された再計算領域の端点を、１つ前の走査線（高さ（ｈ−１）の走査線）において算出された経路が通過するか否かを判別し（ステップＳＴ１４）、通過しない場合には、ステップＳＴ９において特定された再計算領域のすべてについて経路探索を行う。
１つ前の走査線において算出された経路が再計算領域の端点を通過する場合には、対応する画素間の輝度差分に基づいて、走査線間の差分検出を行う（ステップＳＴ１５）。そして、走査線間の差分が基準値よりも小さいと判断される（ステップＳＴ１６）と、１つ前の走査線において算出された経路が、次の走査線における経路として継承される（ステップＳＴ１７）。輝度変化が大きいと判断される（ステップＳＴ１６）と、ステップＳＴ１５において特定された再計算領域のすべてについて経路探索を行う。
また、最も下に位置する走査線であった場合にはステップＳＴ１５において特定された再計算領域のすべてについて経路探索を行う。
【００６８】
一方、最初に処理されるフレームであった場合には、そのフレーム内において、走査線間の輝度変化に応じて、特定された再計算領域をさらに制限できないか（狭められないか）について判断する処理を行う。
この場合には、先ず、処理される走査線が最も下に位置する(高さη)走査線であるか否かを判別する（ステップＳＴ１２）。最も下に位置する走査線ではない場合には、対応する画素間の輝度差分に基づいて、走査線間の差分検出を行う（ステップＳＴ１５）。そして、走査線間の差分が基準値よりも小さいと判断される（ステップＳＴ１６）と、１つ前の走査線において算出された経路が、次の走査線における経路として継承される（ステップＳＴ１７）。輝度変化が大きいと判断される（ステップＳＴ１６）と、ステップＳＴ１５において特定された再計算領域のすべてについて経路探索を行う。また、最も下に位置する走査線であった場合には走査線全体について経路探索を行う。
【００６９】
以上のフレーム間差分検出および走査線間差分検出によって、最終的に再計算領域が特定されると、図１６以降に示すステップＳＴ１８〜ＳＴ３１において、ＤＰマッチング演算（経路探索）が行われる。
ＤＰマッチング演算は、基準画像（左画像）の水平位置ｉが、たとえばｉｐ〜ｉｐ＋１の範囲で（ステップＳＴ１８、１９）、かつ、右画像の水平位置ｊがｊｎからｊ＜ｉを満たす範囲で行われる（ステップＳＴ２０、２１）。
ＤＰマッチング演算では、走査線上の左画像および右画像の画素間のコストとして輝度距離を算出し（ステップＳＴ２２）、累積距離が最小となる経路を順に探索する（ステップＳＴ２３）。
そして、図１７において、基準画像（左画像）の水平位置ｉが、ステップＳＴ５で抽出した特徴点ｉｎと一致すると（ステップＳＴ２６）、その特徴点ｉｎが区間の開始位置ｉｐでないことを条件として、刈込み処理を行う（ステップＳＴ２８）。これにより、さらに経路探索領域を制限する。
１つの刈込み処理が終了すると、次の刈込み処理のために、ステップＳＴ３０でｎがインクリメントされ、ステップＳＴ２６において次の特徴点ｉｎと水平位置ｉとの一致判断がなされる。
【００７０】
以上のようにして、走査線上の１つの区間におけるＤＰマッチング演算を行った後は、メモリ３３に格納された配列ｋを逆に辿ることで、最適経路を取得し（ステップＳＴ３２）、ｐをインクリメントして（ステップＳＴ３３）、同一走査線上の次の区間における処理をステップＳＴ８に戻って行う。
走査線上のすべての区間の最適経路が算出されると、その走査線における左右画像の水平位置が対応付けられたことになるので、三角測量の原理によって、計測対象までの距離を算出し（ステップＳＴ３５）、１つ上の走査線の処理に移行する（ステップＳＴ３６）。
【００７１】
以上説明したように、本実施形態に係る３次元形状計測装置１によれば、計測対象である物体２の２次元画像として、左画像と右画像を取得し、走査線ごとにＤＰマッチング演算によって左画像および右画像の水平位置を特定する際に、フレーム間差分検出処理、走査線間差分検出処理、および刈込み処理を行うため、各フレームにおいて計算対象（経路探索対象）とする画像領域を極小化できる。
したがって、計測対象である物体２が大きく動く場合等、動画処理を伴う場合でも、実時間処理が十分に可能となる。
さらに、マッチング精度が高いＤＰマッチング演算を基本としているため、マッチング処理における高精度化と高速化を高い次元で両立することが可能となる。
なお、上述したフレーム間差分検出処理、走査線間差分検出処理、および刈込み処理は、すべて実行されることが実時間処理の観点から好ましいが、各処理は相互に依存性を持たないので、それぞれ独立に実行することもできる。
【００７２】
次に、本実施形態に係る３次元形状計測装置１の定量的な効果の一例について述べる。
図１８は、実施形態に係る３次元形状計測装置１の効果を測定するためのサンプル画像であって、（ａ）は計測対象の左画像、（ｂ）は計測対象の右画像、をそれぞれ示す。実際には、図１８に示す画像は動画像であり、矢印で示すチェック柄の立方体が画像の右の方向に向かって１０［ｍｍ／ｆｌａｍｅ］の速度で移動している。なお、画像のサイズは６４０［ｐｉｘｅｌ］×４８０［ｐｉｘｅｌ］である。
【００７３】
図１９は、図１８に示したサンプル動画像に対する特徴点の数と計算時間との関係を示す図である。図１９における計算時間は、１フレームのステレオ計測処理にかかる計算時間の平均値である。
図２０は、図１８に示したサンプル動画像において、計測精度の違いを表した図である。図２０では、特徴点を変化させたときの相対誤差の平均値の変化を表している。
図１９および図２０において、ケースIは、フレーム間の差分検出処理および走査線間の差分検出処理を行わない場合の結果を、ケースIIは、フレーム間の差分検出処理および走査線間の差分検出処理を行った場合の結果を、それぞれ示す。
【００７４】
図１９において、たとえば、特徴点の数が２０個のときの計算時間は、ケースIでは約１４［ｓ］であるが、ケースIIでは、約２［ｓ］まで短縮され、ケースIと比較すると、約１／７の計算時間となっている。また、特徴点の数が０個のときは、ＤＰマッチングに対する高速化を一切おこなわないが、このとき計算時間は約７０［ｓ］である。すなわち、ケースIIでは、特徴点の数が２０個の場合には、特徴点の数が０個のときと比較して、計算時間は約１／３５にもなる。
【００７５】
図２０において、特徴点の数が０個の場合がＤＰマッチングにおける最適解であり、このときの相対誤差は３．９［％］であった。特徴点の数が１９個のときには、ケースIとケースIIとの相対誤差の差が最大となり、ケースIでは約４．３［％］であったのに対し、ケースIIでは５．９［％］であった。すなわち、ケースI〜ケースII間で計測精度に大きな変化は見られないことがわかる。
【００７６】
以上説明したように、フレーム間の差分検出処理および走査線間の差分検出処理を行った場合には、行わない場合と比較して、計測精度をほぼ維持したまま、計算時間を１／７〜１／８程度に短縮するという顕著な効果を得ることができる。
【００７７】
なお、本発明の実施形態は、上述した実施形態に拘泥せず、当業者であれば、本発明の要旨を変更しない範囲内で様々な改変が可能である。
たとえば、上述の実施形態では、画素の画素値の指標として「輝度」を用いたが、これに限られず、たとえば「色差」を用いてもよい。
また、上述した実施形態の説明で述べた、制御部３１で実行される複数の処理は、コンピュータに実行させるプログラムによって、ソフトウエアとして実現することもできる。
【産業上の利用可能性】
【００７８】
本発明は、物体の３次元形状を認識するための用途、たとえば以下の用途に利用できる。
（１）セキュリティ分野
本発明は、顔画像認識（歩行者、侵入者の顔の認識等）へ応用できる。
（２）ＩＴＳ分野
本発明は、走行中の自動車から他の走行車両に対する車間距離の計測など、自動車などの移動物体の形状計測に利用できる。
（３）ロボットビジョン
本発明は、自律移動ロボットの静止障害物および移動障害物に対するセンサとして利用できる。
【図面の簡単な説明】
【００７９】
【図１】実施形態に係る３次元形状計測装置の外観構成の一例を示す図である。
【図２】実施形態に係る３次元形状計測装置のシステム構成を示すブロック図である。
【図３】計測対象の物体に対して、左カメラおよび右カメラがそれぞれ撮像・生成した左画像および右画像を例示する図である。
【図４】ある走査線上において、画像の水平軸と輝度値の差分との関係を図解した図である。
【図５】特徴点抽出処理の一例を図解する図である。
【図６】輝度距離の算出例を図解する図である。
【図７】累積距離の算出例を図解する図である。
【図８】刈込み処理を図解した図である。
【図９】探索結果の一例を図解した図である。
【図１０】フレーム間の差分検出処理の一例を図解する図である。
【図１１】新しいフレームにおいて経路を再計算する再計算領域と、前のフレームの経路を継承する継承領域とを図解した図である。
【図１２】再計算領域における計算結果と、継承領域における計算結果との間の処理を図解した図である。
【図１３】走査線間の差分検出処理の具体的処理を説明するための図である。
【図１４】実施形態に係る３次元形状計測装置の動作を示すフローチャートである。
【図１５】実施形態に係る３次元形状計測装置の動作を示すフローチャートである。
【図１６】実施形態に係る３次元形状計測装置の動作を示すフローチャートである。
【図１７】実施形態に係る３次元形状計測装置の動作を示すフローチャートである。
【図１８】実施形態に係る３次元形状計測装置の効果を測定するためのサンプル動画像を表示する図である。
【図１９】サンプル動画像に対する特徴点の数と計算時間との関係を示す図である。
【図２０】サンプル動画像に対する計測精度を表した図である。
【符号の説明】
【００８０】
１…３次元形状計測装置
１０…左カメラ
２０…右カメラ
３０…画像処理装置
３１…制御部
３２…画像インタフェース
３３…メモリ
３４…表示部
３５…バス
２…物体
【図１】
2006331108.tif 000012
【図２】
2006331108.tif 000013
【図３】
2006331108.tif 000014
【図４】
2006331108.tif 000015
【図５】
2006331108.tif 000016
【図６】
2006331108.tif 000017
【図７】
2006331108.tif 000018
【図８】
2006331108.tif 000019
【図９】
2006331108.tif 000020
【図１０】
2006331108.tif 000021
【図１１】
2006331108.tif 000022
【図１２】
2006331108.tif 000023
【図１３】
2006331108.tif 000024
【図１４】
2006331108.tif 000025
【図１５】
2006331108.tif 000026
【図１６】
2006331108.tif 000027
【図１７】
2006331108.tif 000028
【図１９】
2006331108.tif 000029
【図２０】
2006331108.tif 000030
【図１８】
2006331108.tif 000031