(57)【要約】【課題】  画像処理装置において、広い範囲にある対象物に対して、屋外や強い照明下においても安定して形状復元する。【解決手段】  画像処理装置において、画像入力手段１ａが時系列的に入力した画像上の特徴的な点の位置関係の変化を第１の計算手段１ｂが抽出する。位置関係の変化から特徴的な点の三次元位置と画像を捉えた際の視点の位置と方向を第２の計算手段１ｃが計算する。入力した画像と特徴的な点の三次元位置とから画像に捉えられている物体の三次元形状データを第３の計算手段が計算する。【選択図】  図１
2006004122.tif 000002
【特許請求の範囲】
【請求項１】
画像入力手段と、この画像入力手段から入力した画像についてその特徴的な部分の位置関係の変化を抽出する第１の計算手段と、入力画像の位置関係の変化から特徴的な部分の三次元位置を計算する第２の計算手段と、この第２の計算手段が計算した特徴的な部分の三次元位置を用いて画像内に表示される物体の三次元形状データを計算する第３の計算手段とを備えたことを特徴とする画像処理装置。
【請求項２】
三次元形状を記憶する記憶手段と、前記第３の計算手段が計算した物体の三次元形状データと予め前記記憶手段に記憶された三次元形状データとを比較して、記憶された三次元形状データに類似する形状を有する物体の位置と姿勢を求める第４の計算手段を備えたことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記画像入力手段は、アナログ入力信号またはデジタル入力信号をデジタル画像データに変換する変換手段を有することを特徴とする請求項１に記載の画像処理装置。
【請求項４】
前記画像入力手段は受光素子を有し、この受光素子が取り込んだ信号を画像データに変換する手段を備えたことを特徴とする請求項１に記載の画像処理装置。
【請求項５】
前記第３の計算手段は、物体を表す点の座標値と、線分を構成する始点および終点の番号と、面を構成する線の番号とを用いて三次元形状データを計算することを特徴とする請求項１に記載の画像処理装置。
【請求項６】
入力された画像に対して予め基準座標系を設定し、この基準座標系における物体または視点の位置を３個のパラメータで、物体の姿勢または視点を３個のパラメータでそれぞれ表示し、前記第１ないし第３の計算手段はこれらのパラメータを用いて物体の三次元形状データを計算することを特徴とする請求項１に記載の画像処理装置。
【請求項７】
前記画像入力手段はアドレス信号とデータ信号と制御信号とを入力し、前記第１ないし第３の計算手段の少なくともいずれかは、前記画像入力手段から入力された画像のデータあるいはレジスタの内容を読み出すときは、前記アドレス信号に該当するアドレスを与えた状態で制御信号を出力することを特徴とする請求項１に記載の画像処理装置。
【請求項８】
前記第１の計算手段は、画像入力手段が入力した画像から画像の特徴的な部分を抽出する特徴部分抽出手段と、特徴的な部分の位置の変化を追跡する特徴部分追跡手段とを備えることを特徴とする請求項１に記載の画像処理装置。
【請求項９】
前記第３の計算手段は、前記第２の計算手段が計算した点から複数の線分を演算し、この複数の線分が構成する面を計算することを特徴とする請求項１に記載の画像処理装置。
【請求項１０】
前記第３の計算手段は、入力画像に表示される物体について求められた輪郭を構成する複数の線分を、その端点で接続して輪郭線を形成することを特徴とする請求項１に記載の画像処理装置。
【請求項１１】
前記第３の計算手段は、前記第２の計算手段が計算した特徴的部分における隣接する点同士を結んで線分を形成するとともにこの線分が構成する面を計算し、線分と入力画像に表示される物体の輪郭線とが交差する場合には線分と輪郭線が交差しないように線分と計算した面を修正することを特徴とする請求項１に記載の画像処理装置。
【請求項１２】
前記記憶手段に既に計算した形状データを記憶し、前記第２の計算手段が新たに座標計算した特徴部分と前記記憶手段に記憶されている形状データの部分の対応関係を用いて新たに座標計算した特徴部分を既に計算した形状データに統合する統合手段を設けたことを特徴とする請求項２に記載の画像処理手段。
【請求項１３】
前記第４の計算手段は、記憶された三次元形状データに類似する形状を有する物体の位置と姿勢を求めるときに記憶された三次元形状データの一部を用いて類似する形状を有する物体の位置と姿勢とを求めるよう限定する手段を有することを特徴とする請求項２に記載の画像処理装置。
【請求項１４】
前記記憶手段に記憶された三次元形状データと物体の形状とをともに点群で表示し、前記第４の計算手段は、記憶された三次元形状データと物体の形状における点群の一致度を比較する比較手段を有することを特徴とする請求項２に記載の画像処理装置。
【請求項１５】
前記比較手段は、点群の一致度が所定の値より小さい場合には、前記記憶手段に記憶された三次元形状データに類似する形状が見つからないと判定することを特徴とする請求項１４に記載の画像処理装置。
【請求項１６】
前記第４の計算手段は、前記記憶手段に記憶された三次元形状に類似する物体を求めたときには、前記記憶手段に記憶された三次元形状を求めた物体形状で置換することを特徴とする請求項２に記載の画像処理装置。
【請求項１７】
前記第４の計算手段は、前記記憶手段に記憶された三次元形状に類似する物体を求めたときには、類似する物体の識別情報と位置情報とを前記記憶手段に記憶させることを特徴とする請求項２に記載の画像処理装置。
【請求項１８】
前記画像入力手段が入力した複数の画像の初めの画像から特徴部分を抽出する特徴部分抽出回路と、複数の画像の２番目の画像においては初めの画像から抽出された特徴部分に対応する部分を求めて特徴部分とし、複数の画像の３番目以後の画像においては直前の画像の特徴部分に対応する部分を求めて特徴部分とする特徴部分追跡回路とを、前記第３の計算手段に設けたことを特徴とする請求項１に記載の画像処理装置。
【請求項１９】
前記第２の計算手段は、前記複数の画像のそれぞれにおける特徴部分の位置を求めて特徴部分の三次元位置を計算する座標計算回路を備えることを特徴とする請求項１８に記載の画像処理装置。
【請求項２０】
前記座標計算回路が求めた特徴部分の三次元位置と前記記憶手段に記憶された三次元形状データを用いて、前記座標計算回路が求めた特徴部分の三次元位置を三次元形状データに適合するように変換するデータ統合回路を設けたことを特徴とする請求項１９に記載の画像処理装置。
【請求項２１】
前記画像入力手段および前記特徴部分抽出回路、特徴部分追跡回路、座標計算回路、データ統合回路がパイプライン的に並列に動作するようにそれぞれを配置したことを特徴とする請求項２０に記載の画像処理装置。
【請求項２２】
画像入力手段と、この画像入力手段から入力した画像についてその特徴的な部分の位置関係の変化を抽出する第１の計算手段と、入力画像の位置関係の変化から特徴的な部分の三次元位置を計算する第２の計算手段と、この第２の計算手段が計算した特徴的な部分の三次元位置を用いて画像内に表示される物体の三次元形状データを計算する第３の計算手段とを有する画像処理装置と、この画像処理装置との間でデータを伝達する制御装置と、アームと手先とを有するマニピュレータとを備え、前記画像取込手段をこのマニピュレータのアームあるいは手先に設けたことを特徴とするロボット装置。
【請求項２３】
画像入力手段と、この画像入力手段から入力した画像についてその特徴的な部分の位置関係の変化を抽出する第１の計算手段と、入力画像の位置関係の変化から特徴的な部分の三次元位置を計算する第２の計算手段と、この第２の計算手段が計算した特徴的な部分の三次元位置を用いて画像内に表示される物体の三次元形状データを計算する第３の計算手段とを有する画像処理装置と、この画像処理装置の出力を表示する表示装置とを備える車両の誘導装置であって、前記表示装置は前記画像処理装置が求めた物体の形状データに基づいて画像処理装置が搭載された車両の周囲の障害物の位置を表示することを特徴とする車両誘導装置。
【請求項２４】
前記表示装置は、車両の周囲の障害物を上面図として表示することを特徴とする請求項２３に記載の車両誘導装置。
【請求項２５】
前記表示装置は、前記画像処理装置が搭載された車両の前方を走行する車両の位置を表示することを特徴とする請求項２３に記載の車両誘導装置。
【請求項２６】
前記表示装置は、前記画像処理装置が搭載された車両の駐車スペースにある物体の位置を表示することを特徴とする請求項２３に記載の車両誘導装置。
【請求項２７】
前記表示装置は、前記画像処理装置が搭載された車両の周囲の建物の位置関係に基づいて、地図上に車両の位置を補正して表示することを特徴とする請求項２３に記載の車両誘導装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像から物体あるいは周囲の障害物の三次元的な形状を復元する画像処理装置及びそれを搭載したロボット装置ならびに車両誘導装置に関する。
【背景技術】
【０００２】
従来の撮像画像を画像処理する装置の例が、特許文献１及び特許文献２に記載されている。特許文献１に記載の撮像画像処理装置は、対象物体を撮像して２次元輝度画像データを得、この２次元輝度画像データから３次元形状を復元している。その際、２次元輝度画像データについてエッジを検出し、エッジから対象物体の表面の滑らかさを示すパラメータを算出している。そしてパラメータを用いて３次元形状を正確に復元する陰影情報としての反射地図パラメータを決定し、このパラメータを用いて対象物体の３次元形状を復元している。
【０００３】
一方特許文献２には、画像処理装置において、撮像手段が撮像した所定視点位置からの被写体画像を第１の記憶手段に記憶し、撮像された画像に最も近い視点位置からの対象物画像を標準３次元形状モデルに基づいて生成し、第２の記憶手段に記憶することが記載されている。そして、これら第１、第２の記憶手段に記憶された画像の差から差異を抽出し、この差に基づいて標準３次元形状モデルを修正することが記載されている。
【０００４】
【特許文献１】特開平５-１８１９８０号公報
【０００５】
【特許文献２】特開平８-２３３５５６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上記特許文献１、２に記載の従来の画像処理装置においては、物体がカメラから遠方にあると視野角が非常に小さくなるため、物体の形状を精度よく復元することができない。また、屋外や明るい照明の下にある物体では、明るい反射光によりハレーションを起こしやすく、輝度値の識別が困難である。さらに、遠方にある物体や暗い場所の輝度は一般に低いから、低レベルな輝度の違いを区別するのは難しく、遠方や暗い場所の物体形状を復元しにくい。
【０００７】
本発明は上記従来技術の不具合に鑑みなされたものであり、その目的は、遠方から至近距離まで広い範囲にある対象物に対して、屋外や強い照明下においても安定して形状復元を可能にすることである。本発明はまた、形状復元に要する時間を低減することも目的とする。
【課題を解決するための手段】
【０００８】
上記目的は、画像入力手段と、前記画像入力手段より入力した画像上の特徴的な部分の位置関係の変化を抽出する第１の計算手段と、前記位置関係の変化から特徴的な部分の三次元位置を計算する第２の計算手段と、前記特徴的な部分の三次元位置を用いて画像に捉えられている物体の三次元形状データを計算する第３の計算手段を備えた画像処理装置により達成される。
【０００９】
また、上記目的は、画像入力手段が時系列的に入力した複数の画像をセットとして、その先頭の画像に関して特徴部分を抽出する特徴部分抽出回路と、前記画像のセットの２番目の画像については、１番目の画像の特徴部分の位置を中心とした近傍を探索して対応する部分の位置を求め、前記画像のセットの３番目以後の画像については、その一つ前の画像について求めた部分の位置を中心とした近傍を探索して対応する部分の位置を求める特徴部分追跡回路と、前記画像のセットにおける特徴部分の位置が求まった段階で、特徴部分の三次元位置を計算する座標計算回路と、前記座標計算回路が特徴部分の三次元位置を求めた段階でこれらの特徴部分と記憶手段に記憶されている形状データの部分の対応関係を求め、前記新たに座標計算した特徴部分の三次元座標を変換するデータ統合回路とを備え、これら画像入力手段、特徴部分抽出回路、特徴部分追跡回路、座標計算回路、データ統合回路がパイプライン的に並列に動作するものである画像処理装置により達成される。
【発明の効果】
【００１０】
本発明による画像処理装置によれば、対象を様々な方向から眺めた画像を得るだけで対象物の３次元形状を復元することができるので、空撮画像のような遠方の対象物に対しても、至近距離にある対象物に対しても３次元形状を復元することが可能である。また、特別な参照光を用いないので、屋外や強い照明下においても安定して形状復元が可能である。また、全ての処理を自動で行うことが可能であるので手間がかからない。また、ＬＳＩのようなチップとして構成することも可能であるので、安価でコンパクトな装置とすることができる。
【発明を実施するための最良の形態】
【００１１】
以下、本発明の実施の形態を図面によって説明する。図１は、本発明による画像処理装置の一実施例である。１は本発明による画像処理装置、２は対象物体の画像を取り込むカメラ、３は画像処理装置が復元した対象物体の形状を利用する処理装置である。処理装置３は、具体的には例えば画像処理装置１が組込まれた機械装置の制御装置などであり、画像処理装置が復元した物体の形状データを元に機械装置の動きを制御するものである。また、１ａは画像処理装置１内に設けられた画像入力手段、１ｂは時系列的に入力される画像上の特徴点の位置関係の変化を抽出する第１の計算手段、１ｃは特徴点の位置関係の変化から各点の三次元位置と各入力画像を捉えた際の視点の位置と方向（カメラ位置姿勢）を計算する第２の計算手段、１ｄは入力画像と特徴点の三次元位置とから画像に捉えられている物体の三次元形状データを計算する第３の計算手段、１ｅは復元した物体の三次元形状データに関する情報を制御装置３とやり取りする入出力手段、１ｆは第３の計算手段が計算した物体の三次元形状データと入出力手段から入力された三次元形状データを比較することにより、同一の形状の物体の位置・姿勢を求める第４の計算手段である。
【００１２】
図２は、図１の各構成要素を更に詳しく示す図である。図２においては、特徴点・エッジ抽出手段１２と特徴点追跡手段１３が第１の計算手段１ｂを構成し、物体認識手段２３と空間探索手段２４が第４の計算手段を構成する。また、座標計算手段１６が第２の計算手段１ｃに、線／面抽出・登録手段１９が第３の計算手段１ｄに対応する。また、１１、１４、１５、１７はデータを一時的に記憶しておく記憶手段であり、それぞれ画像入力手段が入力した画像データ、特徴点追跡手段が生成した観測マトリックス、特徴点・エッジ抽出手段が生成した特徴点・エッジマップ、座標計算手段が計算した特徴点の３次元座標データを記憶する。
【００１３】
２０はＣＡＤデータの記憶手段であり、線／面抽出・登録手段が形状データを生成するたびにＣＡＤデータ記憶手段に記憶されている形状データ（以後ＣＡＤデータと呼ぶ）と統合され、蓄積される。また、１８はカメラ位置姿勢の記憶手段であり、座標計算手段が計算したカメラ位置姿勢データを記憶しておく。記憶しておくデータは最新のデータのみであっても、入力画像系列の全てに関するデータを記憶するものであっても良い。
【００１４】
２２はＣＡＤデータの中から探索すべき物体の形状モデルを記憶しておく記憶手段であり、物体認識手段２３は２２に記憶された形状データと一致する部分を２０に記憶されているＣＡＤデータの中から探索する。また、空間探索手段２４は２０に記憶されているＣＡＤデータの中から物体認識手段２３が探索すべき範囲を限定する。
【００１５】
各部の詳細について説明する。図３は、画像入力手段１０の具体的構成例を示すものである。一般に画像データを得るためには、ＣＣＤ撮像素子等を用いたカメラなどが用いられる。このカメラは、例えば図３の２として示すように、画像を撮像素子上に結像するためのレンズ２ａ、ＣＣＤ素子２ｂ、ＣＣＤ出力を読み出す読出回路２ｃ、ＣＣＤ出力を映像信号に変換する信号生成回路２ｄなどから構成される。
【００１６】
一般にＣＣＤ素子は、格子状に配置された受光素子の行の方向に順次読み出すようになっており、信号生成回路２ｄは順次読み出された画素の明るさを信号の振幅によってアナログ的に表す信号（輝度信号）と画像の各行や１画面の区切りを表す同期信号を合成したいわゆるビデオ信号２ｅを生成する。
【００１７】
図３に示す画像入力手段の例では、このビデオ信号から同期信号を分離する同期回路１０ａと、ビデオ信号から輝度信号を分離して画素の明るさをデジタル値に変換するＡ／Ｄ変換器１０ｂと、明るさのデジタル値を同期信号に同期して記憶素子１１に書き込む書込回路１０ｃを備えている。
【００１８】
図４は、画像入力手段１０の別な具体的構成例を示すものである。上記のようなビデオ信号を出力するカメラの他に、画像をデジタル信号として出力するタイプのカメラも存在する。この様なカメラでは、例えば図４に示すように画素の輝度値を表す複数ビットのデジタル信号２ｇと同期信号２ｆから構成されるデジタル映像信号を出力する。この様なカメラでは、データ転送効率が良くなるため高速に画像データを得ることができる。また、カメラ内部で輝度値がデジタル化されるため、信号の歪やノイズによる画像の劣化が起こらないと言うメリットがある。
【００１９】
図４に示す画像入力手段の例では、このデジタル映像信号から画素データの書込みアドレスを計算して画素データを記憶素子１１に書込む書込回路１０ｃを備えている。画像入力手段１０の構成としては、図３に示す構成、あるいは図４に示す構成、あるいはその両方を備えた構成であっても良い。画像入力手段をこのような構成とすることにより、画像処理装置を直接カメラ等に接続することができる。このため、画像処理装置を機械装置等に組込む際に特別な付加回路等を設けなくても済む。
【００２０】
図５は、画像入力手段１０の更に別な具体的構成例を示すものである。図５は、画像処理装置１上にＣＣＤ素子のような受光素子１０ｆを構成し、そこに画像を結像させるためのレンズ１０ｄを設けたものである。受光素子１０ｆが検出した輝度情報は直接あるいはデジタル値に変換されて記憶素子１１に転送される。この様な構成とすることにより、画像データをカメラから画像処理装置に転送する必要がなくなるため、非常に高速に画像データを得ることができる。
【００２１】
特徴点・エッジ抽出手段１２の詳細について図６を用いて説明する。ここで、特徴点とは多角形の頂点、線と線の交点、曲線の折れ点や線の分岐点など空間において位置を一意に特定できる点のことを意味する。３次元の物体を線画の様に描いた画像から上記のような特徴点を抽出すると、これらの点は物体の頂点や物体表面に描かれた図形の頂点である場合が多い。従って、これらの点の３次元位置を求めて、線で結ぶことにより元の物体の形状や物体表面に描かれた図形の形状を再現することが可能となる。
【００２２】
一方、エッジとは３次元物体の形状における稜線や、物体表面に描かれた図形の境界線、あるいは物体の２次元画像における輪郭線などを意味する。即ち、３次元の物体を線画の様に描いた場合に得られる線に対応するものである。上記の特徴点を線で結ぶ際に、この様なエッジに沿って結ぶことにより、物体形状を正しく再現することが可能となる。なお、エッジは画像において空間的に明るさが大きく変化する場所に現れることが多い。
【００２３】
図６において、１２ａは画像の輝度値のＵ方向（横方向）の空間微分を計算する手段であり、１２ｂは輝度値のＶ方向（縦方向）の空間微分を計算する手段である。具体的には、座標（ｕ，ｖ）における画像の輝度をＩ（ｕ，ｖ）とする時に、Ｕ方向微分Ｉｕ（ｕ，ｖ）とＶ方向微分Ｉｖ（ｕ，ｖ）は、例えば以下の式により計算する。（以後の説明において特に断りのない限り（ｕ，ｖ）は画像上の横方向と縦方向の座標を表すものとする。）
【００２４】
【数１】
2006004122.tif 000003
【００２５】
これは、画像における空間的な明るさの変化を計算するものであり、具体的計算方法は上記に限定されるものではない。
【００２６】
１２ｃは、特徴点としての指標Ｅｆを計算する手段であり、例えば以下の式により計算する。
【００２７】
【数２】
2006004122.tif 000004
【００２８】
ここで、Ｇｕｕ、Ｇｖｖ、Ｇｕｖは以下に示す様に近傍領域ＷにおいてＵ方向微分の二乗、Ｖ方向微分の二乗、Ｕ方向微分とＶ方向微分の積を積算したものである。
【００２９】
【数３】
2006004122.tif 000005
【００３０】
指標Ｅｆは近傍領域Ｗにおいて明るさの変化の方向が変化する程度を表すものであり、具体的計算方法としては上記に限定されるものではない。
【００３１】
特徴点・エッジ抽出手段１２は、上記の指標Ｅｆを用いて、例えばＥｆがある設定値以上である画素を特徴点として抽出し、その画像上での座標（ｕ，ｖ）のリスト１５ａを出力する。１２ｄは、エッジとしての指標Ｅｅを計算する手段であり、例えば以下の式により計算する。
【００３２】
【数４】
2006004122.tif 000006
【００３３】
指標Ｅｅは画素（ｕ，ｖ）における明るさの空間変化の程度を表すものであり、具体的計算方法としては上記に限定されるものではない。
【００３４】
特徴点・エッジ抽出手段１２は、上記の指標Ｅｅを用いて、例えばＥｅがある設定値以上である画素に対してはそれがエッジであることを示す値を、そうでない画素に対してはそれがエッジでないことを示す値を設定した画像データ（エッジパターン）１５ｂを生成する。そして、上記特徴点の座標リスト１５ａとエッジパターン１５ｂとにより特徴点・エッジマップ１５を構成する。
【００３５】
特徴点追跡手段１３の詳細について、図７を用いて説明する。特徴点追跡手段１３は、既に特徴点の位置が既知である第１の画像Ｉ１をもとに、特徴点の位置が未知である第２の画像Ｉ２における対応する特徴点の位置を求める。この時、対応する特徴点の位置は、既知の特徴点の位置を中心とした近傍領域を第２の画像Ｉ２について探索することにより求める。
【００３６】
具体的探索手順を図７に示す。既知の特徴点の座標が（ｕ０，ｖ０）であるとして、（ｕ０，ｖ０）を中心とした近傍領域、例えばｕ，ｖ座標がそれぞれ±ｗの範囲のＩ１の画像ＩＷ１を得る（ｓ１）。この時、座標（ｕ０，ｖ０）は、必ずしも画像Ｉ１の画素を構成する格子点の座標と一致するものではないとし、ｓ１ではＩ１の格子点の画素値から座標（ｕ０，ｖ０）を中心とした格子点の画素値を補間計算するものとする（サブピクセル処理）。
【００３７】
ＩＷ１のＵ方向微分画像とＶ方向微分画像を求め、これをＩｕ、Ｉｖとする（ｓ２）。この処理は、例えば図６に示したＵ方向微分計算手段１２ａ、Ｖ方向微分計算手段１２ｂを用いて行う。画像Ｉ２の対応する特徴点の推定位置（ｕ，ｖ）をまず（ｕ０，ｖ０）と置いて（ｓ３）、繰り返し回数ｔを０と置く（ｓ４）。Ｉ２に対して座標（ｕ，ｖ）を中心とした近傍領域、例えばｕ，ｖ座標がそれぞれ±ｗの範囲の画像を得てＩＷ２とする（ｓ５）。この手順では、手順ｓ１と同様にサブピクセル処理を行う。
【００３８】
ＩＷ１、ＩＷ２、Ｉｕ、Ｉｖとから行列Ｇとベクトルｂを計算する（ｓ６）。具体的には以下の式によりＧとｂを計算する。
【００３９】
【数５】
2006004122.tif 000007
【００４０】
ここで、Ｇｕｕ、Ｇｖｖ，Ｇｕｖの定義は（数３）と同様であるが、積算する範囲は（ｕ０，ｖ０）を中心とする近傍領域、例えばｕ，ｖ座標がそれぞれ±ｗの範囲である。また、ｂの積算演算はＩＷ１，Ｉｕ，Ｉｖについては（ｕ０，ｖ０）を中心とする近傍領域、ＩＷ２については（ｕ，ｖ）を中心とする近傍領域について積算することを表している。
【００４１】
行列Ｇが逆行列を持つなら（ｓ７）なら手順ｓ８に示す式により（ｕ，ｖ）の修正量（ｄｕ，ｄｖ）を計算する。Ｇが逆行列を持たないなら修正量は０とする（ｓ９）。そして、（ｕ，ｖ）を（ｄｕ，ｄｖ）により修正し（ｓ１０）、その修正量が所定の値ｄｍより小さいなら（ｓ１１）、処理を終了する。また、修正量がｄｍより大きい場合には、繰り返し回数ｔを１増やし（ｓ１２）、繰り返し回数が所定の回数ｔｍより小さければ処理を継続し、所定の回数ｔｍとなったら処理を終了する（ｓ１３）。
【００４２】
上記のように、特徴点追跡手段１３においては、既知の特徴点の位置を初期値推定値として、その近傍領域から計算される修正量で推定値を修正することを繰り返すことにより対応する特徴点の位置を特定する。この繰り返し処理において、修正量が所定の値以下になった場合、あるいは繰り返し回数が所定の回数となった場合に処理を終了する。
【００４３】
修正量に関するしきい値ｄｍを小さくすると高精度に対応点の位置を特定することができる。しかし、場合によっては繰り返し回数が多くなり、対応点を求める計算に時間がかかることになる。これに対して、繰り返し回数に関するしきい値ｔｍを設けることにより、常に所定の時間以内で計算が終了し、かつ収束の速い特徴点については高精度に対応点の位置を求めることができる。また、繰り返し計算が収束しない場合の無限ループを防ぐこともできる。
【００４４】
画像入力手段１０により入力される時系列的な画像に対しては、例えば、１番目の画像に対して特徴点・エッジ抽出手段１２により特徴点の位置を求め、Ｉ１を１番目の画像、Ｉ２を２番目の画像として、上記の手順によりＩ２の対応する特徴点の位置を求める。次にＩ１を２番目の画像、Ｉ２を３番目の画像として、Ｉ１の特徴点の位置は上記で求めた特徴点とすることで、３番目の画像に対して対応する特徴点の位置を求める。以下、同様の手順を繰り返すことにより、時系列的な画像全体に渡って特徴点の位置を追跡することができる。
【００４５】
以上の手順により、特徴点追跡手段は以下に示す観測行列を生成する。
【００４６】
【数６】
2006004122.tif 000008
【００４７】
ここで、ｕｉｊ，ｖｉｊはｉ番目の画像におけるｊ番目の特徴点の画像上での位置座標である。
【００４８】
座標計算手段１６の詳細について図８を用いて説明する。（数６）に示した観測行列はｍ個の異なる視点から対象物を観測して得た画像上でのｎ個の特徴点の位置座標を列挙したものと考えることができる。このようにｍ個の異なる視点におけるｎ個の点の見え方から点の３次元座標と視点の位置姿勢を求める計算方法としては、いくつかの方法が存在する。これらの方法は、点を画像面に投影するモデル、例えば正射影モデルであるか、パースペクティブモデルであるかなどの相異により異なる計算方法を用いる。ここでは、例えば正射影モデルを用いた場合の例について説明する。
【００４９】
まず、観測行列の各行についてその行の平均値を差し引く（ｓ２０）。具体的には、以下の式により計算を行う。
【００５０】
【数７】
2006004122.tif 000009
【００５１】
次に、上記で得られた行列を特異値分解して以下の形として、Ｕ行列とＶ行列を得る（ｓ２１）。なお、記号Ｔは行列の転置を表す。
【００５２】
【数８】
2006004122.tif 000010
【００５３】
ここで、対角行列Ｓの対角要素は特異値の値の大きい順に並べられているものとする。
【００５４】
次に、Ｕ行列の左３行列から得た２ｍ行３列の行列Ｕ３から回転行列Ｒを計算する（ｓ２２）。具体的には、対角行列Ｓの左上３×３行列から得た部分行列をＳ３とする時、例えば以下の式によりＲを計算する。
【００５５】
【数９】
2006004122.tif 000011
【００５６】
同様に、Ｖ行列の左３行列から得たｎ行３列の行列Ｖ３から形状行列Ｐを計算する（ｓ２３）。具体的には、前記部分行列Ｓ３を用いて例えば以下の式により計算する。
【００５７】
【数１０】
2006004122.tif 000012
【００５８】
次に回転行列Ｒを正規直交化する変換行列Ａを求める（ｓ２４）。これは、Ｒの各行から作ったベクトルをｒｉとする時、以下の連立方程式を満たす解として求めることができる。
【００５９】
【数１１】
2006004122.tif 000013
上記変換行列Ａを右から掛けたものを回転行列、Ａの逆行列をＰの左から掛けたものを形状行列とすることにより（ｓ２５）、Ｒのｉ行とｉ＋ｍ行が第ｉ番目の画像における視点の方向を規定する二つのベクトル座標となり、Ｐのｊ列がｊ番目の特徴点の３次元座標となる。また、視点の平行移動成分は、観測行列Ｍの各行の平均値として与えられる。
【００６０】
線／面抽出・登録手段１９の詳細について図９を用いて説明する。まず、特徴点群からデローニ三角形を生成する（ｓ３０）。ここで、デローニ三角形とは２次元空間上の点群を結んで空間を三角形に分割する時、三角形の最小角ができるだけ大きくなるような分割方法で三角形を構成するものである。数学的には、点群から構成されるボロノイ図の双対として与えられる。ここでは、座標計算に使用した任意の画像における特徴点の２次元位置に対してデローニ三角形を生成するものである。
【００６１】
上記デローニ三角形を生成するのに用いた画像のエッジパターンを用いて、エッジで結ばれた特徴点のペアを求める（ｓ３１）。これは、例えばある特徴点から出発して直線状に伸びているエッジを辿って行き、他の特徴点に到達したなら、結ばれていると判定することにより求める。
【００６２】
上記で求めたペアの間のエッジがデローニ三角形の辺と交差する部分に対して、デローニ三角形の辺がエッジと交差しないように修正する（ｓ３２）。例えば、図１０（ａ）において、特徴点群４０に対してデローニ三角形が点線４１の様な形で生成されたとする。これに対して、特徴点同士を結ぶエッジの線が図１０（ｂ）の実線４２のように得られたとする。この時、デローニ三角形の辺４１ａと４１ｂとが、エッジの線４２ａと交差するので、４１ａと４１ｂを例えば図１０（ｃ）に示す線４１ｃとエッジ４２ａと重なる線に修正する。
【００６３】
以上の手順によって得られた三角形の面に関して、互いに隣接していて面の方向がほとんど同じもの同士を統合する（ｓ３３）。例えば、図１０（ｃ）において、三角形４３ａ、４３ｂ、４３ｃ、４３ｄ、４３ｅの面の向きがほとんど同じであるので統合する。他の面についても同様の処理を行うことにより、図１０（ｄ）に示すような結果となる。但し、上記の処理において、面が接する辺がエッジの線と重なる場合には、統合しない。
【００６４】
上記で得た面の色を求める（ｓ３４）。これは、画像上において面に対応する領域の画素の色の平均値として求める。物体表面上に描かれた図形などの境界は多くの場合エッジとして抽出され、境界の頂点などは特徴点として抽出される。従って、上記の処理により物体表面に描かれた図形なども形状データとして生成される。
【００６５】
以上の手順により、生成した点と線と面により構成された形状データをＣＡＤデータに統合する（ｓ３５）。この統合処理の詳細手順を図１０に示す。新たに生成された形状データの点（特徴点）に対応するＣＡＤデータ内の点を抽出する（ｓ４０）。これは、例えば特徴点・エッジ抽出手段１２が特徴点を抽出した際に、特徴点の座標リスト１５ａに対して、個々の特徴点を識別する識別番号を付加しておく。そして、ＣＡＤデータに登録する際に点のデータと合わせて識別番号も記憶しておく。次に、再び特徴点の抽出を行った際に、前回作成した特徴点の座標リスト１５ａを参照し、座標がほとんど同じ特徴点については、前回と同一の識別番号を付加するようにする。これにより、新たに生成した形状データにおける点の識別番号と同一の識別番号を持つ点をＣＡＤデータから探索することにより対応する点の抽出を行うことができる。
【００６６】
新たに生成された形状データの点とＣＡＤデータより抽出した対応点の座標が一致するように変換する座標変換を求める（ｓ４１）。これは、点の座標に関する連立方程式を解くことにより求められる。新たに生成された啓上データの全ての点の座標を上記の座標変換により変換した後にＣＡＤデータに登録する（ｓ４２）。この時、新たな点の中でＣＡＤデータ内の点と対応のあるものは登録しない。点データの統合により生じる線や面のデータの修正処理を行う（ｓ４３）。これは、例えば新たに生成された形状データの中の線の端点や面の頂点の点がＣＡＤデータ内の点と対応のあるものであれば、その点への接続に置き換えるなどの処理を行うものである。
【００６７】
形状データの統合処理の例を図１２に示す。まず、カメラ位置２０１における画像に対して特徴点・エッジ抽出手段１２により特徴点４０ａ、４０ｂ、４０ｃ、４０ｄの抽出が行われたとする。これらは、カメラ位置２０２、２０３においても視野の中に入っており、特徴点追跡手段１３によって追跡され、それぞれ対応する画像上での位置が求められる。これらの位置データから特徴点４０ａ、４０ｂ、４０ｃ、４０ｄの３次元座標が計算され形状データとしてＣＡＤデータに登録されたとする。次に、カメラ位置２０４における画像に対して特徴点４０ｃ、４０ｄ、４０ｅ、４０ｆが抽出され、続くカメラ位置２０５、２０６における画像に対して追跡処理が行われ、これらの特徴点の３次元座標が計算されたとする。この時、両者の間で共通する特徴点４０ｃ、４０ｄの座標は必ずしも同一の３次元座標とはならない。これは、画面上での特徴点の位置関係から３次元座標を復元する計算処理において、カメラと特徴点の相対的な位置関係のみが求まるためである。そこで、カメラ位置２０１、２０２、２０３から計算した特徴点４０ｃ、４０ｄの座標とカメラ位置２０４、２０５、２０６から計算した４０ｃ、４０ｄの座標が重なるような座標変換を求め、これにより特徴点４０ｅ、４０ｆの座標を変換して統合することにより、正しい形状データを得ることができる。
【００６８】
次に、データ入出力手段２１の詳細について図１３を用いて説明する。データ入出力手段には、例えばアドレスを指定するアドレス信号線２１ａ、データをセットまたは読み出すためのデータ線２１ｂ、画像処理装置１へのアクセスを指定するチップセレクト制御線２１ｃ、データの入力または読み出しを指定するリードライト制御線２１ｄ、データの書込みまたは読み出しのタイミングを指定するストローブ制御線２１ｅ、画像処理装置１に接続された制御装置に割り込み処理を要求する割込み制御線２１ｆなどが備えられている。
【００６９】
これらの信号線を用いて、例えば図１４に示すような形の形状データの入出力を行う。図１４において、４４は形状を構成する点の座標データであり、４５は線のデータであり、４６は面のデータであり、４７は物体のデータである。線のデータ４５は二つ一組の数値データであり、それぞれ始点と終点の点の番号を表す。面のデータ４６は任意個の組からなる数値データであり、それぞれ線の番号を表す。物体のデータ４７は任意個の組からなる数値データであり、それぞれ面の番号を表す。例えば図１４に示す例は、図１５に示すような一つの面Ｐ１、四つの線Ｌ１、Ｌ２、Ｌ３、Ｌ４、四つの点（ｘ１，ｙ１，ｚ１）、（ｘ２，ｙ２，ｚ２）、（ｘ３，ｙ３，ｚ３）、（ｘ４，ｙ４，ｚ４）からなる物体の形状データを表すものである。
【００７０】
次に、物体認識手段２３と空間探索手段２４の詳細について図１６を用いて説明する。
【００７１】
物体認識手段２３は、入出力手段２１より入力され、記憶手段２２に一時的に記憶された形状データと一致する形状部分をＣＡＤデータ２０の中から探索し、その位置姿勢を求めるものである。この時行われる探索は、ＣＡＤデータ２０の全体に渡るものであっても良いが、例えば現在のカメラ位置姿勢を指定して現在のカメラから見える範囲の中から探索するものであっても良い。後者のように探索範囲を限定することにより、より短い時間で探索処理を行うことができる。例えば図１７（ａ）において、例えば画像処理装置１が組込まれた作業機械に装着されたカメラが５２に示す位置姿勢にあり、前記作業機械がこのカメラから見える範囲の物体５１ａ，５１ｂ、５１ｃに対して作業を行っている場合、この中のある特定の物体を探す目的においては、ＣＡＤデータの全空間５１を探索する必要はなく、カメラ位置姿勢５２から見える範囲の空間５２ａの中だけを探索すれば良い。これによって、現在の作業には関係のない５１ｄや５１ｅの様な物体を探索する必要がなくなり、探索時間を短縮することができる。
【００７２】
図１６における手順ｓ５０はこのような探索範囲の限定を行うための処理であり、カメラ視点などによって指定される空間に含まれる形状データを抽出するものである。
【００７３】
この抽出処理は、例えば図１７（ｂ）に示すような空間探索木を用いることによって高速に行うことができる。図１７（ｂ）に示す空間探索木の際下段のノード５５は、図１７（ａ）の空間５１を分割した部分空間に対応し、それぞれ対応する数字で示した点線で囲まれた部分空間に対応する。２段目のノード５４は、前記部分空間の隣接するもの同士を統合した空間に対応するものであり、最上位のノード５３は、全空間５１に対応する。
【００７４】
この空間探索木を用いて、例えば図１７（ａ）における探索範囲５２ａに含まれる物体は以下の手順で抽出される。まず、空間探索木の最上位ノードから出発して、探索範囲５２ａと重なる部分空間に対応したノードのみを残して、順次下位のノードに探索を進めていく。例えば図１７の例では、２段目のノードにおいてノード４に対応する空間（図１７（ａ）で１１、１２、１５、１６で示す空間）は、５２ａと重ならないので、ノード４より下につながっているノードに関する探索は行わない。ノード１、２、３についてはその下につながる第１段のノードについて同様に重なる部分があるものだけを残す。これにより、１、２、５、６、３、７、９、１０、１３のノードが残されることになる。そして最後に、この残されたノードに対応する部分空間に含まれる物体をもって、空間５２ａに含まれる物体とすることができる。正確には、物体は上記で求めた物体の中に空間５２ａに含まれない物体も存在し得るが、この数は空間の分割数を適切に設定することにより十分小さくすることができる。
【００７５】
次に、記憶手段２２に記憶されている形状データ（モデル）とｓ５０で抽出された形状データの形状表面に点群を設定する（ｓ５１）。これは、例えば図１８に示すように、形状データの表面に一様に分布するような点群５６を設定するものである。
【００７６】
次に、形状データの点群にモデルの点群を様々な位置姿勢で重ね合せてみて、最も良く重なる位置姿勢を求める（ｓ５２）。この重ね合せの探索手順としては種々提案されている手法、例えばA. Johnson and M. Hebert, "Using spin images for efficient object recognition in cluttered 3D scenes," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 21, No. 5, May, 1999, pp. 433 - 449などを用いる。
【００７７】
次に、上記の結果得られた位置姿勢における形状データとモデルの点群の一致度が所定の値より大きければ（ｓ５３）、上記の位置姿勢データを出力し（ｓ５４）、そうでなければ物体が見つからなかった旨を出力する（ｓ５５）。次に、画像処理装置１の全体的な動作の流れについて図１９を用いて説明する。
【００７８】
図１９において横方向の流れは、左から右へ時間の経過を表し、縦方向の流れは主にデータの流れを表す。また、図中の四角は主にそれらが並べられた各行の左端に示される処理が行われるタイミングを表す。
【００７９】
まず、カメラが捉えた画像は画像入力手段１０により６０で示すタイミングで逐次画像処理装置に取り込まれる。これらの画像データを例えば６０ａに示すようなセットとした時に、その先頭の画像が取り込まれたタイミングで特徴点・エッジ抽出処理６１が実行される。その結果得られた特徴点の画像上での座標データは、観測行列６３の先頭行となる。画像のセット６０ａの２番目以後の画像については、特徴点の追跡処理６２が実行され、その結果得られる各画像における特徴点の座標データは、観測行列６３の２番目以後の行となる。
【００８０】
以上の手順で画像のセット６０ａの全ての画像に関する特徴点追跡の処理が終了した段階で、生成された観測行列から特徴点の３次元座標とカメラの位置姿勢を計算する座標計算処理６４が実行される。そして、特徴点の３次元座標が求まった段階で線／面の抽出と登録処理６５が実行され、新たな形状データがＣＡＤデータ６６に登録される。一方、入出力手段２１を介して物体の探索指令が入力されると（６８）、その時点から物体の認識処理の実行が開始され（６７）、認識処理が終了した段階で結果である物体の位置姿勢データが出力される（６９）。
【００８１】
一般に特徴点の抽出処理や、特徴点の追跡処理に比べて座標計算処理や線／面抽出登録処理は非常に長い時間を必要とする。このため、画像取込から形状データ登録までの全ての処理が終了してから次の画像の取込を開始すると、最初の画像を取り込んでから次の画像を取り込むまでの間の時間が長くなる。すると、前の画像と後の画像の間での特徴点の対応関係を見つけることが非常に難しくなる。
【００８２】
これに対して、画像をセットとしてまとめて、そのセットの長さを座標計算処理や線／面抽出登録処理の長さより長く取って、図１９の様なパイプライン処理とすることにより、入力される画像の時間間隔を短く取ることができ、簡単な追跡処理によって特徴点の対応関係を求めることができる。また、特徴点の３次元座標計算に際しては、多くの画像データに関する情報を使うことができるので計算結果の精度を高めることができる。
【００８３】
次に、上述した画像処理装置を搭載した各機器について、詳細に説明する。図２０に、画像処理装置をマニピュレータ型ロボットに適用したときの、ブロック図を示す。ロボット７０は、複数の関節を備えその先端に物体を把持する把持機構を備えている。把持機構の近くにカメラ７１を設け、これにより取り込んだ画像を本発明による画像処理装置１に入力する。そして、画像処理装置１により求めた物体の形状データをロボットの制御手段７２で利用する。
【００８４】
例えば、今ロボットが把持している物体７５を物体７３に設けられた穴７４に挿入する作業を行うとする。まず、ロボットの把持機構を物体７３の周りで動かし、カメラ７１から物体７３を様々な方向から見た画像を得る。これらの画像を画像処理装置１で処理することにより、物体７３の３次元形状データが生成される。ここで、制御手段７２が物体７３の形状モデルを画像処理装置１に入力し、この物体の位置姿勢を求めるように指示する。すると、画像処理装置１は、内蔵する物体認識手段により物体７３を探索し、その位置姿勢を求めて制御手段７２に出力する。制御手段７２は、この位置姿勢データをもとに把持機構の位置姿勢を制御することにより、物体７５を穴７４に正しく挿入することができる。
【００８５】
図２１に、画像処理装置を移動機構に搭載したときの模式図を示す。。ロボット８０は、移動機構８３とカメラ８１を備え、カメラ８１で取り込んだ画像を本発明による画像処理装置１に入力する。そして、画像処理装置１により求めた物体の形状データをロボットの制御手段８２で利用する。例えば、今ロボットが移動機構８３を用いて家の中を移動しているとする。カメラ８１から取り込まれたロボットの周囲の画像を画像処理装置１で処理することにより、ロボットの周囲の障害物の３次元形状データとカメラ８１の位置姿勢が計算される。ここで、制御手段８２は障害物の形状データとカメラの位置姿勢データを画像処理装置１から取り出し、周囲の障害物に対する現在のロボット自身の位置関係を計算する。これを用いることにより、ロボット８０は周囲の障害物にぶつかることなく家の中を自由に移動することが可能となる。
【００８６】
図２２に、画像処理装置を搭載した車両の模式図を示す。車両９０は、カメラ９１、９２と、車両誘導装置９３と、表示装置９４と、本発明による画像処理装置１を備え、カメラ９１または９２で取り込んだ画像を本発明による画像処理装置１に入力する。そして、画像処理装置１により求めた物体の形状データを車両誘導装置９３で利用する。
【００８７】
例えば、今車両９０が道路を走行中であるとすると、カメラ９１は車両９０の前方を走行する別な車両の画像を捉え、画像処理装置１に入力する。すると、画像処理装置１は先行する車両の形状とカメラ９１の位置姿勢を計算する。車両誘導装置９３は、画像処理装置１から上記の形状データとカメラの位置姿勢データを読み出し、前記カメラの位置姿勢データを用いて前記先行車両の形状の自車に対する相対的な位置関係を計算する。そして、図２３に示すように、自車９４ａと先行車両９４ｂの位置関係を表示装置９４に表示する。
【００８８】
例えば車両９０がバックで車庫に入ろうとしているとすると、カメラ９２は車両９０の後方の障害物の画像を捉え、画像処理装置１に入力する。すると、画像処理装置１は後方の障害物の形状データとカメラ９２に位置姿勢を計算する。車両誘導装置９３は、画像処理装置１から上記の形状データとカメラの位置姿勢データを読み出し、前記カメラの位置姿勢データを用いて前記後方障害物の形状の自車に対する相対的な位置関係を計算する。そして、図２３に示すように、自車９４ａと後方障害物９４ｃの位置関係を表示装置９４に表示する。図２３の様な表示は、車両９０の運転者に対して、道路走行中あるいは車庫入れ中の運転の助けとなるものである。
【００８９】
上記各実施例では、画像処理装置１の中の各種演算処理は、一般的なデジタル回路で実行している。しかしながら、デジタル回路として例えばＬＳＩのような半導体チップを用いれば、コンパクトな画像処理装置になる。また、上記各種演算処理は、コンピュータで使用するコンピュータ・プログラムであってもよい。その場合、画像処理装置１は、コンピュータである。また、特徴点は画像における線分や模様などでも良い。
【図面の簡単な説明】
【００９０】
【図１】本発明に係る画像処理装置の一実施例のブロック図である。
【図２】図１に示した画像処理装置の詳細ブロック図である。
【図３】図２に示した画像入力手段の模式図である。
【図４】図２に示した画像入力手段の他の実施例の模式図である。
【図５】図２に示した画像入力手段のさらに他の実施例の模式図である。
【図６】図２に示した特徴点およびエッジ抽出手段の模式図である。
【図７】図２に示した特徴点追跡手段の動作を説明するフローチャートである。
【図８】図２に示した座標計算手段の動作を説明するフローチャートである。
【図９】図２に示した線または面を抽出および登録する手段の動作を説明するフローチャートである
【図１０】線または面の抽出方法を説明する図である。
【図１１】形状データをＣＡＤデータに登録する方法を説明するフローチャートである。
【図１２】形状データをＣＡＤデータに登録する方法を説明する図である。
【図１３】第１ないし第４の計算手段が備える入出力手段の一実施例のブロック図である。
【図１４】図１３に示した入出力手段から入出力される形状データを説明する図である。
【図１５】形状データの内容を説明する図である。
【図１６】物体探索および物体認識手段の動作を説明するフローチャートである。
【図１７】物体および空間探索を説明する図である。
【図１８】形状表面の点群を説明する図である。
【図１９】画像処理装置の動作を説明するタイムチャートである。
【図２０】本発明に係るマニピュレータ型のロボットの一実施例のブロック図である。
【図２１】本発明に係る移動機構の一実施例の模式図である。
【図２２】本発明に係る車両誘導装置の一実施例の模式図である。
【図２３】図２２に示した車両誘導装置に用いる表示装置の表示画面例を示す図である。
【符号の説明】
【００９１】
１…画像処理装置、２…カメラ、３…制御装置、１０…画像入力手段、１１…画像記憶手段、１２…特徴点・エッジ抽出手段、１３…特徴点追跡手段、１４…観測行列記憶手段、１５…特徴点・エッジマップ記憶手段、１６…座標計算手段、１７…３次元座標データ記憶手段、１８…カメラ位置姿勢記憶手段、１９…線／面抽出・登録手段、２０…ＣＡＤデータ記憶手段、２１…入出力手段、２２…物体モデル記憶手段、２３…物体認識手段、２４…空間探索手段。
【図１】
2006004122.tif 000014
【図２】
2006004122.tif 000015
【図３】
2006004122.tif 000016
【図４】
2006004122.tif 000017
【図５】
2006004122.tif 000018
【図６】
2006004122.tif 000019
【図７】
2006004122.tif 000020
【図８】
2006004122.tif 000021
【図９】
2006004122.tif 000022
【図１０】
2006004122.tif 000023
【図１１】
2006004122.tif 000024
【図１２】
2006004122.tif 000025
【図１３】
2006004122.tif 000026
【図１４】
2006004122.tif 000027
【図１５】
2006004122.tif 000028
【図１６】
2006004122.tif 000029
【図１７】
2006004122.tif 000030
【図１８】
2006004122.tif 000031
【図１９】
2006004122.tif 000032
【図２０】
2006004122.tif 000033
【図２１】
2006004122.tif 000034
【図２２】
2006004122.tif 000035
【図２３】
2006004122.tif 000036