(57)【特許請求の範囲】
【請求項１】
対象物体を異なる位置及び方向から撮影した画像を入力する入力手段と、
前記入力手段により入力された複数の画像各々から前記対象物体を示す線分を検出する検出手段と、
前記検出手段により検出された線分各々を識別するのに用いる特徴ベクトルを求める特徴導出手段と、
前記特徴導出手段により求められた特徴ベクトルに基づいて前記複数の画像間における線分各々の対応付けを決定する決定手段と
を具備し、
前記特徴導出手段は、
前記検出手段により検出された線分に対して複数の分割点を設定し、該分割点を通過する参照ラインを設定し、該参照ラインを用いて該分割点毎に前記検出された線分の特徴ベクトルを求め、該分割点毎に求めた特徴ベクトルを線分毎に平均して前記線分各々に対応した代表特徴ベクトルを求め、
前記決定手段は、
前記特徴導出手段により求められた前記代表特徴ベクトルに基づいて前記複数の画像間における線分各々の対応付けを決定する
ことを特徴とする画像処理装置。
【請求項２】
前記特徴導出手段は、
前記検出された線分に直交する方向に前記参照ラインを設定する
ことを特徴とする請求項１記載の画像処理装置。
【請求項３】
前記特徴ベクトルは、前記参照ライン上において輝度が変化した画素の輝度情報の変化パターンを示すベクトルである
ことを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記特徴ベクトルは、前記参照ライン上で前記線分との交点となる画素を交点画素とし、該交点画素から規定範囲内にある前記参照ライン上の画素のうち、隣接画素に対して輝度が変化した画素の輝度情報を並べた情報を要素とするベクトルである
ことを特徴とする請求項１乃至３の何れか１項記載の画像処理装置。
【請求項５】
前記決定手段により決定された前記線分の対応関係に基づいて前記対象物体を構成する３次元幾何モデルを算出する算出手段
を更に具備することを特徴とする請求項１又は２記載の画像処理装置。
【請求項６】
画像処理装置の画像処理方法であって、
入力手段が、対象物体を異なる位置及び方向から撮影した画像を入力する工程と、
検出手段が、前記入力手段により入力された複数の画像各々から前記対象物体を示す線分を検出する工程と、
特徴導出手段が、前記検出手段により検出された線分各々を識別するのに用いる特徴ベクトルを求める工程と、
決定手段が、前記特徴導出手段により求められた特徴ベクトルに基づいて前記複数の画像間における線分各々の対応付けを決定する工程と
を含み、
前記特徴導出手段は、
前記検出手段により検出された線分に対して複数の分割点を設定し、該分割点を通過する参照ラインを設定し、該参照ラインを用いて該分割点毎に前記検出された線分の特徴ベクトルを求め、該分割点毎に求めた特徴ベクトルを線分毎に平均して前記線分各々に対応した代表特徴ベクトルを求め、
前記決定手段は、
前記特徴導出手段により求められた前記代表特徴ベクトルに基づいて前記複数の画像間における線分各々の対応付けを決定する
ことを特徴とする画像処理装置の画像処理方法。
【請求項７】
コンピュータを、
対象物体を異なる位置及び方向から撮影した画像を入力する入力手段、
前記入力手段により入力された複数の画像各々から前記対象物体を示す線分を検出する検出手段、
前記検出手段により検出された線分を通過し且つ該線分に平行でない方向に沿って参照ラインを設定し、当該参照ライン上において輝度が変化した画素の輝度情報をその順序に従って並べた情報を要素として含む特徴ベクトルを求める特徴導出手段、
前記特徴導出手段により求められた特徴ベクトルに基づいて前記複数の画像間における線分各々の対応付けを決定する決定手段
として機能させるためのプログラムであって、
前記特徴導出手段は、
前記検出手段により検出された線分に対して複数の分割点を設定し、該分割点を通過する参照ラインを設定し、該参照ラインを用いて該分割点毎に前記検出された線分の特徴ベクトルを求め、該分割点毎に求めた特徴ベクトルを線分毎に平均して前記線分各々に対応した代表特徴ベクトルを求め、
前記決定手段は、
前記特徴導出手段により求められた前記代表特徴ベクトルに基づいて前記複数の画像間における線分各々の対応付けを決定する
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置、その画像処理方法及びプログラムに関する。
【背景技術】
【０００２】
近年、複合現実感やロボットの自動走行への応用を目的として、現実物体の３次元幾何モデルに基づいて当該現実物体に対するカメラの位置及び姿勢を計測する技術の研究が行なわれている。その中でも特に、３次元幾何モデルを線分の集合として表し、当該線分の投影像を画像上のエッジに当てはめるべくカメラの位置及び姿勢を計測する技術が幅広く研究されている（例えば、非特許文献１）。
【０００３】
３次元幾何モデルに基づいたカメラの位置及び姿勢の計測には、対象となる現実物体の３次元幾何モデルを予め用意しておく必要がある。現実物体の３次元幾何モデルを作成する方法としては、例えば、現実物体を撮影した複数の画像における画像特徴の対応関係に基づいて３次元幾何モデルを作成する手法が知られている。非特許文献２及び３においては、２枚又は３枚以上の画像から線分を検出し、当該画像間における線分の対応関係に基づいて３次元幾何モデルを作成する技術が開示されている。この場合、何らかの方法を用いて、画像間における線分の対応関係を求めなければならない。線分の数が少なければ、例えば、画面上に表示された複数の画像における線分をユーザが手動で対応付けてもよいが、線分の数が増えれば、手動による対応付けは困難となる。この対応付けを自動且つ効率的に行なうには、観察位置によらない線分固有の情報が、画像上で検出された線分に特徴として割り当てられる必要がある。
【０００４】
そこで、特許文献１には、画像上で検出された線分周辺の画素の情報をデータ列とし、当該データ列を比較することにより対応付けを行なう技術が開示されている。この技術では、比較する線分同士が３次元空間における同一の線分の投影像であることが前提となっている。そのため、線分の端点を精度よく検出しなければならないが、画像のノイズ、照明変化、開口等を考慮すると、当該前提条件を常に満たすことは難しい。
【０００５】
これに対して、非特許文献４では、画像間のエピポーラ幾何が既知であると仮定して、エピポーラ幾何を用いて、線分上の一方の点を線分上の他方の点と対応付けて比較を行なう技術が開示されている。この技術では、特許文献１のような前提条件は不要となるが、線分以外の情報（例えば、識別性の高い特徴点等）から画像間のエピポーラ幾何を予め推定しておく必要がある。
【０００６】
また、非特許文献５では、検出された線分の両側の色分布に基づいて線分を対応付ける技術が開示されている。この技術では、検出された線分の両側において、当該線分から数画素離れた画素群の色のヒストグラムを生成し、このヒストグラムを他の線分との比較に用いている。この場合、比較する線分が３次元空間において同一である必要はなく、また、画像間のエピポーラ幾何といった事前知識も必要ない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００４−３３４８１９号公報
【非特許文献】
【０００８】
【非特許文献１】T.Drummond and R.Cipolla,“Real-time visual tracking of complex structures," IEEE Transactions on Pattern Recognition and Machine Intelligence,vol.24,no.7,pp.932-946,2002.
【非特許文献２】Z.Zhang,“Estimating Motion and structure from correspondences of line segments between two perspcetive images," IEEE Transactions on Pattern Recognition and Machine Intelligence,vol.17,no.12,pp.1129-1139,1995.
【非特許文献３】C.J.Taylor and D.J.Kriegman,“Structure and motion from line segments in multiple images," IEEE Transactions on Pattern Recognition and Machine Intelligence,vol.17,no.11,pp.1021-1032,1995.
【非特許文献４】C.Schmid and A.Zisserman,“Automatic line matching across views," Proc.IEEE Computer Society Conference on Computer Vision and Pattern Recognition 1997,pp.666-671,1997.
【非特許文献５】H.Bay,V.Ferrari,and L.Van Gool,“Wide-baseline stereo matching with line segments," Proc.IEEE Computer Society Conference on Computer Vision and Pattern Recognition 2005,vol.1,pp.329-336,2005.
【非特許文献６】J.Weng,T.S.Huang,and N.Ahuja,“Motion and structure from line correspondences:closed-form solution,uniquness,and optimization," IEEE Transactions on Pattern Recognition and Machine Intelligence,vol.14,no.3,pp.318-336,1992.
【非特許文献７】H.Bay,A.Ess,A.Neubeck and L.Van Gool,“3D from line segments in two poorly-textured,uncalibrated images," Proc.3rd International Symposium on 3D Data Processing,Visualization and Transmission,pp.496-503,2006.
【非特許文献８】M.A.Fischler and R.C.Bolles,“Random sample consensus:a paradigm for model fitting with applications to image analysis and automated cartography," Communications of ACM,vol.24,no.6,pp.381-395,1981.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非特許文献５に開示される手法では、検出された線分の両側の色分布に基づいて線分の対応付けを行なっているため、類似した線分が存在すれば、対応付けを誤ってしまう可能性がある。
【００１０】
また、非特許文献５に開示される手法では、検出した線分から数画素離れた線分上の色のヒストグラムを用いるため、線分が隣接又は密集している場合、観察位置によってヒストグラムが大きく変化してしまう。この場合にも、対応付けを誤ってしまう可能性がある。
【００１１】
本発明は、上記課題に鑑みてなされたものであり、画像上に類似した線分が存在する場合や画像上に線分が密集している場合であっても、画像間の線分を正確に対応付けられるようにした技術を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記課題を解決するため、本発明の一態様による画像処理装置は、対象物体を異なる位置及び方向から撮影した画像を入力する入力手段と、
前記入力手段により入力された複数の画像各々から前記対象物体を示す線分を検出する検出手段と、
前記検出手段により検出された線分各々を識別するのに用いる特徴ベクトルを求める特徴導出手段と、
前記特徴導出手段により求められた特徴ベクトルに基づいて前記複数の画像間における線分各々の対応付けを決定する決定手段と
を具備し、
前記特徴導出手段は、
前記検出手段により検出された線分に対して複数の分割点を設定し、該分割点を通過する参照ラインを設定し、該参照ラインを用いて該分割点毎に前記検出された線分の特徴ベクトルを求め、該分割点毎に求めた特徴ベクトルを線分毎に平均して前記線分各々に対応した代表特徴ベクトルを求め、
前記決定手段は、
前記特徴導出手段により求められた前記代表特徴ベクトルに基づいて前記複数の画像間における線分各々の対応付けを決定する
ことを特徴とする。
【発明の効果】
【００１３】
本発明によれば、画像上に類似した線分が存在する場合や画像上に線分が密集している場合であっても、画像間における線分の誤対応を低減できる。
【図面の簡単な説明】
【００１４】
【図１】本発明の一実施の形態に係わる画像処理装置の機能的な構成の一例を示す図。
【図２】現実物体２０の撮影の仕方の一例を示す図。
【図３】図１に示す画像処理装置１０の全体的な動作の一例を示すフローチャート。
【図４】図３のＳ１０２に示す線分検出処理の流れの一例を示すフローチャート。
【図５】本実施形態に係わる特徴ベクトルを説明するための図。
【図６】本実施形態に係わる特徴ベクトルの求め方の概要を説明するための図。
【図７】図３のＳ１０４に示す線分の対応付け処理の流れの一例を示すフローチャート。
【図８】図７のＳ３０３に示す対応線分探索処理の流れの一例を示すフローチャート。
【図９】実施形態２に係わる画像間における線分の対応付け処理の流れの一例を示すフローチャート。
【発明を実施するための形態】
【００１５】
以下、本発明の一実施の形態について添付図面を参照して詳細に説明する。
【００１６】
（実施形態１）
図１は、本発明の一実施の形態に係わる画像処理装置の機能的な構成の一例を示す図である。
【００１７】
画像処理装置１０は、現実物体を撮影した複数の画像を用いて、当該現実物体を線分の集合によって表現する３次元幾何モデルを作成する。ここで、画像処理装置１０は、コンピュータを内蔵して構成される。コンピュータには、例えば、ＣＰＵ等の主制御手段、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）等の記憶手段が具備される。また、コンピュータには、ネットワークカードや赤外線等の通信手段、ディスプレイ又はタッチパネル等の入出力手段、等が具備されていてもよい。なお、これら各構成手段は、バス等により接続され、主制御手段が記憶手段に記憶されたプログラムを実行することで制御される。
【００１８】
ここで、画像処理装置１０は、機能的な構成として、画像入力部１１と、線分検出部１２と、特徴導出部１３と、対応付け決定部１４と、モデル算出部１５とを具備して構成される。
【００１９】
ここで、画像入力部１１は、現実物体２０の画像を装置内に入力する。本実施形態においては、図２に示すように、現実物体２０を異なる位置及び方向から撮影した複数の画像（この場合、３枚）を入力する。なお、現実物体２０の画像が予め記憶されている場合、画像入力部１１は、当該記憶された画像を読み出すことにより上記入力を行なう。現実物体２０の画像は、例えば、ビデオカメラ（撮像装置）によって撮影された画像であってもよい。この場合、例えば、撮像装置の出力がアナログ信号（ＮＴＳＣ信号など）であれば、画像入力部１１は、アナログビデオキャプチャボードによって実現される。また、例えば、撮像装置の出力がデジタル出力（ＩＥＥＥ１３９４など）であれば、画像入力部１１は、ＩＥＥＥ１３９４インタフェースボードによって実現される。
【００２０】
線分検出部１２は、画像入力部１１により入力された画像から線分を検出する。なお、本実施形態においては、撮像装置の焦点距離や歪みパラメータなどの固有パラメータは、予め校正されているものとし、また、線分の検出結果は、焦点距離が１となるように変換されているものとする。
【００２１】
特徴導出部１３は、線分検出部１２により検出された線分各々の特徴ベクトルを求める。なお、特徴ベクトルは、線分各々を識別するための情報であり、画像の輝度等に基づいて求められる。
【００２２】
対応付け決定部１４は、画像入力部１１により入力された複数の画像（この場合、３枚）から検出された線分各々を対応付ける。この対応付けは、特徴導出部１３により求められた特徴ベクトルを用いて行なわれる。モデル算出部１５は、対応付け決定部１４により決められた複数の画像間における線分の対応関係に基づいて、現実物体２０を構成する３次元の線分を算出する。これにより、画像処理装置１０は、３次元幾何モデルを作成する。
【００２３】
次に、図３を用いて、図１に示す画像処理装置１０の全体的な動作の一例について説明する。ここでは、３次元幾何モデルを作成する際の処理の流れについて説明する。
【００２４】
画像処理装置１０は、画像入力部１１において、複数視点（この場合、３視点）から撮影された現実物体２０の画像を装置内に入力するとともに（Ｓ１０１）、線分検出部１２において、当該複数の画像各々から線分を検出する（Ｓ１０２）。
【００２５】
線分の検出が済むと、画像処理装置１０は、特徴導出部１３において、当該検出された線分各々の特徴ベクトルを求める。なお、特徴ベクトルは、画像の輝度等に基づいて求める（Ｓ１０３）。そして、対応付け決定部１４において、各線分の特徴ベクトルに基づいて、画像間における線分各々を対応付ける（Ｓ１０４）。この対応付けでは、例えば、第１の画像における線分と第２の画像における線分とを対応付けた後、第２の画像における線分と第３の画像における線分とを対応付ける。これにより、複数の画像間における線分各々を対応付ける。
【００２６】
線分の対応付けが済むと、画像処理装置１０は、モデル算出部１５において、当該線分の対応関係に基づいて、現実物体２０を構成する３次元の線分（３次元幾何モデル）を算出する（Ｓ１０５）。この算出は、公知の技術を用いればよいため、ここでは詳細な説明については省略する。例えば、非特許文献３に開示された手法を用いればよい。なお、非特許文献３に開示された技術を用いる場合、対応付け決定部１４においては、少なくとも６本の線分を３枚の画像間で対応付ける必要がある。勿論、これ以外の手法を用いてもよい。例えば、非特許文献６に開示された技術を用いる場合には、対応付け決定部１４においては、少なくとも１３本の線分を３枚の画像間で対応付ける必要がある。
【００２７】
ここで、図４を用いて、図３のＳ１０２に示す線分検出処理の流れの一例について説明する。
【００２８】
この処理が開始すると、線分検出部１２は、画像からエッジ検出を行なう（Ｓ２０１）。エッジとは、画像上で濃度が急激に変化する点である。エッジ検出には、公知のエッジ検出オペレータ（例えば、Ｓｏｂｅｌオペレータ、Ｐｒｅｗｉｔｔオペレータ等）を用いればよい。具体的には、画像の水平方向及び垂直方向に対してエッジ検出オペレータを適用する。これを各画素に対して行なう。そして、その出力値に基づいてエッジ強度や方向を算出する。エッジ検出オペレータの水平方向の出力値がｆｘ、垂直方向の出力値がｆｙである場合、各画素におけるエッジ強度Ｉは、「数１」を用いて算出される。
0005538868.tif 000002
【００２９】
次に、線分検出部１２は、エッジの細線化を行なう（Ｓ２０２）。すなわち、Ｓ２０１で検出されたエッジは、所定幅を有しているため、当該エッジを細線化する。これは、エッジのぼけやエッジ検出オペレータのウィンドウサイズの影響を受けているためである。細線化処理では、エッジ方向における隣接画素のエッジ強度を画素毎に比較し、隣接画素よりもエッジ強度が大きい画素をエッジとして残す。これにより、エッジ幅を１画素にする細線化を行なう。その後、線分検出部１２は、エッジとして残った画素に「１」、それ以外の画素に「０」を割り当て、２値化画像を生成する。なお、Ｃａｎｎｙのエッジ検出器を用いて、エッジ検出及び細線化を行なうようにしてもよい。
【００３０】
次に、線分検出部１２は、当該生成した２値化画像について、隣接エッジのラベリングを行なう（Ｓ２０３）。ラベリングでは、例えば、ある画素の周囲８画素の中にエッジが存在すれば、同一ラベルを割り当てる。
【００３１】
ラベリングが済むと、線分検出部１２は、同一ラベルに分類された隣接エッジの中から複数の枝が分岐する点を探索する。そして、分岐点において枝を切断し、各枝に異なるラベルを割り当てる。なお、分岐点がないものについては、分岐点の処理は行なわない（Ｓ２０４）。
【００３２】
次に、線分検出部１２は、ラベルを割り当てられた各枝について、折れ線近似を行なう（Ｓ２０５）。折れ線近似では、まず、枝の両端を線分で結び、枝上の点の内、線分との距離が最大且つ閾値以上の点に対して分割点を新たに設ける。そして、この分割点と枝の両端とを線分で結び、当該線分との距離が最大の点に対して分割点を設ける。この処理を、枝が折れ線によって十分近似されるまで再帰的に繰り返す。繰り返し処理が済むと、折れ線を構成する各線分における両端の座標を線分の検出結果として出力する。
【００３３】
なお、図４の説明においては、ラベリング処理と折れ線近似処理とを用いて線分検出を行なう場合について説明したが、線分の検出方法はこれに限られず、画像上から線分を検出できるのであれば、如何なる手法を用いてもよい。例えば、ハフ変換によって線分を検出してもよい。
【００３４】
次に、図５及び図６を用いて、図３のＳ１０３に示す線分の特徴記述処理（特徴ベクトルの算出処理）について説明する。
【００３５】
まず、図５を用いて、本実施形態に係わる特徴ベクトルについて説明する。なお、特徴ベクトルは、上述した通り、画像間における線分の対応付けを行なう際に用いられる。
【００３６】
図５（ａ）及び（ｃ）は、同一の物体を距離を変えて撮影した画像である。具体的には、図５（ａ）は、図５（ｃ）よりも近距離から撮影した画像（物体の撮影像）である。ここで、図５（ａ）及び（ｃ）に丸印で示した点に着目し、この点を通過するライン（参照ライン）上の輝度パターンについて考察する。丸印で示した点は、３次元空間における同一の点を表している。
【００３７】
図５（ｂ）及び（ｄ）は、図５（ａ）及び（ｃ）における参照ライン上の輝度パターンを示している。図５（ｂ）及び（ｄ）を参照すると、距離を変えて撮影された画像においては、参照ライン上での輝度パターンが異なっていることが分かる。そのため、参照ライン上における画素の輝度値を単純に比較するだけでは、画像間における線分を対応付けできない。
【００３８】
ここで、図５（ｂ）及び（ｄ）における輝度パターンを参照すると、輝度パターンの大きさは変わっていても、輝度値が急激に変化する点（エッジ）が表れる順序（以下、輝度値の変化パターン）は同じであることが分かる。
【００３９】
そこで、本実施形態においては、線分固有の情報として、参照ライン上のエッジ（輝度値が急激に変化する点）における輝度をその変化の順序に従って並べた情報を用いる。すなわち、本実施形態においては、輝度パターンそのものではなく、輝度値とその変化パターンとを線分固有の情報（特徴ベクトル）として用いる。これにより、線分の対応付けを行なう。
【００４０】
次に、図６を用いて、特徴ベクトルの求め方の概要について説明する。ここでは、図６（ａ）に示す対象物体における線分について特徴ベクトルを算出する場合について説明する。
【００４１】
この処理では、まず、図６（ｂ）に示すように、図３のＳ１０２の処理により検出された線分を分割し、分割点を設定する。図６（ｂ）では、特徴ベクトルの算出対象となる線分（図中「注目する線分」）の分割点のみを示している。なお、分割点は、例えば、画像上での距離が等間隔（例えば、２０画素）になるように設定する。
【００４２】
次に、図６（ｃ）に示すように、分割点を通過し、且つ検出された線分に平行でない線分（この場合、直交する線分）を参照ラインとして各分割点に設定する。図６（ｄ）は、図６（ｃ）に示す「注目する参照ライン」上における輝度値の変化を表している。
【００４３】
ここで、特徴ベクトルの次元数を２Ｎ＋１とする。この内の１次元には、分割点の輝度値を割り当てる。また、残りの２Ｎ次元には、参照ライン上における分割点の両側の情報をＮ次元ずつ割り当てる。すなわち、図６（ｅ）に示すように、参照ラインに沿ってエッジとなる点の輝度値をサンプリングし、それを特徴ベクトルの要素として設定する。参照ライン上でのエッジの検出は、例えば、注目画素の参照ライン上での両側の画素の差分をとり、差分の絶対値の極値をとる画素を抽出することにより行なえばよい。
【００４４】
図６（ｅ）では、（参照ラインに沿って）エッジとして検出された画素の両側にある２画素の輝度値の平均値を特徴ベクトルの各要素の値としている。図６（ｅ）では、特徴ベクトルの次元数は７（Ｎ＝３）である。特徴ベクトルの要素を設定する場合、参照ライン上での順序が保持されるようにし、Ｎ＋１番目（図６（ｅ）では４番目）に分割点の輝度値が設定されるようにする。なお、参照ライン上に２Ｎ＋１個以上のエッジ点が存在しなければ、特徴ベクトル内における該当箇所には、「データなし」のフラグを立てる。
【００４５】
このように参照ライン上におけるエッジ点の情報のみを特徴ベクトルとして用いるのは、線分の見えが変わったとしても、その周辺における輝度変化のパターンを保持できるためである。また、複数のエッジ点での輝度値を特徴ベクトルとすることで、線分の識別性も向上する。
【００４６】
次に、図７を用いて、図３のＳ１０４に示す線分の対応付け処理について説明する。ここでは、２枚の画像間（第１の画像、第２の画像）における線分を対応付ける場合を例に挙げて説明する。なお、第１の画像及び第２の画像においては、Ｎ１個、Ｎ２個の線分がそれぞれ検出されているものとする。
【００４７】
この処理が開始すると、対応付け決定部１４は、第２の画像から検出された線分における各分割点の特徴ベクトルから特徴ベクトルリストを作成する（Ｓ３０１）。特徴ベクトルリストの個々の要素は、第２の画像における線分のＩＤと、分割点における特徴ベクトルとの組み合わせで構成される。ここで、特徴ベクトルリストの長さをＮｌｉｓｔとする。Ｎｌｉｓｔは、第２の画像から検出された線分の分割点の個数に相当する。
【００４８】
次に、対応付け決定部１４は、対応付け対象となる第１の画像における線分のＩＤに相当する変数ｉに１をセットし（Ｓ３０２）、対応線分探索処理を実施する。すなわち、線分ｉに対応する線分を第２の画像における線分から探索する（Ｓ３０３）。当該線分ｉについての探索が済むと、対応付け決定部１４は、ｉを１増分する（Ｓ３０４）。
【００４９】
その後、対応付け決定部１４は、第１の画像における線分全てに対する処理が終了したか否かを判定する。この判定は、ｉがＮ１より大きいか否かに基づいて行なわれる。ここで、全ての線分について処理が終了していれば（Ｓ３０５でＹＥＳ）、この処理を終了し、そうでないければ（Ｓ３０５でＮＯ）、再度、Ｓ３０３の処理に戻る。
【００５０】
ここで、図８を用いて、図７のＳ３０３に示す対応線分探索処理の流れの一例について説明する。
【００５１】
この処理が開始すると、対応付け決定部１４は、線分ｉにおける分割点ＩＤに相当する変数ｊに１をセットする（Ｓ４０１）。また、対応線分を決定するのに用いられる投票用のヒストグラムの階級を全て０にセットする。ヒストグラムの階級は、第２の画像における各線分に対応し、Ｎ２個の階級がある。
【００５２】
次に、対応付け決定部１４は、図７のＳ３０１で作成した特徴ベクトルリストから、線分ｉにおける分割点ｊの特徴ベクトルに最も類似した特徴ベクトルを探索する（Ｓ４０２）。最も類似した特徴ベクトルの探索は、特徴ベクトルの２Ｎ＋１個の要素の平均二乗誤差に基づいて行なわれる。なお、対応する特徴ベクトルは、平均二乗誤差が最小となる特徴ベクトルとする。ここで、比較する２個の特徴ベクトルのある要素において、いずれかにデータなしのフラグが設定されていれば、平均二乗誤差の算出にその要素は用いない。
【００５３】
その後、対応付け決定部１４は、線分ｉにおける分割点ｊの特徴ベクトルに対応する線分のＩＤを決定し、ヒストグラムにおいて当該ＩＤの線分に相当する階級に投票を行なう（Ｓ４０３）。このとき、平均二乗誤差には予め閾値を設定しておき、当該閾値を越えれば、対応する線分はない旨判定し、投票を行なわない。
【００５４】
次に、対応付け決定部１４は、ｊを１増分した後（Ｓ４０４）、線分ｉの全ての分割点に対して処理が終了したか否かを判定する。この判定は、ｊがＮｌｉｓｔより大きいか否かに基づいて行なわれる。判定の結果、全ての分割点に対する処理が終了していなければ（Ｓ４０５でＮＯ）、再度、Ｓ４０２の処理に戻る。
【００５５】
全ての分割点に対して処理が終了していれば（Ｓ４０５でＹＥＳ）、対応付け決定部１４は、ヒストグラムへの投票結果に基づいて、第１の画像における線分ｉに対応する第２の画像における線分を決定する（Ｓ４０６）。ここでは、対応する線分として、投票結果が最大となるＩＤの線分を選ぶ。
【００５６】
以上説明したように実施形態１によれば、画像上で検出された線分に対して分割点を設定し、各分割点の特徴ベクトルを他の画像上で検出された線分の分割点の特徴ベクトルと比較し、それにより、対応する線分の探索を行なう。すなわち、参照ライン上における複数のエッジ点の輝度値の集合を特徴ベクトルとして線分各々を識別する。これにより、画像上に類似した線分が存在する場合や画像上に線分が密集している場合であっても、画像間における線分の誤対応を低減できる。その結果、従来、対応付けが困難であり、３次元幾何モデルの作成ができなかった現実物体に対しても、３次元幾何モデルを作成できる。
【００５７】
（実施形態２）
次に、実施形態２について説明する。実施形態２においては、線分の探索時間よりも、処理時間を優先する場合について説明する。具体的には、実施形態２においては、分割点毎に保持していた特徴ベクトルを一つの特徴ベクトルに統合し、統合された特徴ベクトルにより比較を行なう（すなわち、線分毎に１つの特徴ベクトルを持つ）。なお、実施形態２に係わる画像処理装置１０に構成や全体的な動作は、実施形態１を説明した図１及び図３と同様であるため、その説明については省略し、ここでは、相違点を重点的に説明する。相違点としては、図３のＳ１０４における線分対応付け処理にある。
【００５８】
ここで、図９を用いて、実施形態２に係わる画像間における線分の対応付け処理について説明する。ここでは、２枚の画像間（第１の画像、第２の画像）における線分を対応付ける場合を例に挙げて説明する。なお、第１の画像及び第２の画像においては、Ｎ１個、Ｎ２個の線分がそれぞれ検出されているものとする。
【００５９】
この処理が開始すると、対応付け決定部１４は、第１の画像及び第２の画像から検出された各線分に対応して一つの代表特徴ベクトルを生成する（Ｓ５０１）。代表特徴ベクトルの次元数は、特徴ベクトル同様に２Ｎ＋１次元である。代表特徴ベクトルの生成は、線分上の全ての分割点の特徴ベクトルの平均ベクトルを算出することにより行なう。平均ベクトルは、特徴ベクトルの次元毎に要素の値を加算し、分割点の個数で割ることにより算出する。なお、特徴ベクトルのある要素に「データなし」のフラグが立っている場合は、そのデータは平均値の算出から除外する。全ての分割点において「データなし」のフラグが立っている要素に関しては、代表特徴ベクトルにおいても「データなし」のフラグを立てる。
【００６０】
次に、対応付け決定部１４は、対応付け対象となる第１の画像における線分のＩＤに相当する変数ｉに１をセットし（Ｓ５０２）、対応線分探索処理を実施する。すなわち、線分ｉの代表特徴ベクトルに最も類似した第２の画像における線分の代表特徴ベクトルを探索する（Ｓ５０３）。最も類似した代表特徴ベクトルの探索は、代表特徴ベクトルの２Ｎ＋１個の要素の平均二乗誤差に基づいて行なう。そして、平均二乗誤差が最小となる第２の画像における線分を、線分ｉに対応する線分とする。ここで、比較する２個の代表特徴ベクトルのある要素において、いずれかにデータなしのフラグが設定されていれば、平均二乗誤差の算出にその要素は用いない。平均二乗誤差には予め閾値を設定しておき、当該閾値を越えれば、対応する線分はない旨判定する。
【００６１】
線分ｉについての探索が済むと、対応付け決定部１４は、ｉを１増分する（Ｓ５０４）。その後、対応付け決定部１４は、第１の画像における線分全てに対する処理が終了したか否かを判定する。この判定は、ｉがＮ１より大きいか否かに基づいて行なわれる。ここで、全ての線分について処理が終了していれば（Ｓ５０５でＹＥＳ）、この処理を終了し、そうでないければ（Ｓ５０５でＮＯ）、再度、Ｓ５０３の処理に戻る。
【００６２】
以上説明したように実施形態２によれば、各線分上の分割点毎に求めた特徴ベクトルを一つの特徴ベクトル（代表特徴ベクトル）に統合し、当該統合した特徴ベクトル同士を比較することにより画像間における線分を対応付ける。これにより、画像間における線分の対応付けが高速に行なえる。
【００６３】
以上が本発明の代表的な実施形態の一例であるが、本発明は、上記及び図面に示す実施形態に限定することなく、その要旨を変更しない範囲内で適宜変形して実施できるものである。
【００６４】
例えば、本発明は、例えば、システム、装置、方法、プログラム若しくは記憶媒体等としての実施態様を採ることもできる。具体的には、複数の機器から構成されるシステムに適用してもよいし、また、一つの機器からなる装置に適用してもよい。
【００６５】
ここで、本発明に係わる変形例について以下にいくつか列挙する。
（変形例１）
上述した実施形態においては、検出された線分に分割点を設定し、当該分割点毎に特徴ベクトルを求めていたが、特徴の記述方法（特徴ベクトルの算出方法）は、これに限られない。例えば、検出された線分上の全ての点について特徴ベクトルを求めてもよい。線分検出では、エッジ検出結果を折れ線近似するため、該当する線分に近似される全てのエッジについて特徴ベクトルを求めてもよい。
【００６６】
（変形例２）
上述した実施形態においては、参照ライン上のエッジ点の輝度値を特徴ベクトルの要素としていたが、輝度値に限られず、輝度に関する情報（輝度情報）であればいかなる情報であってもよい。例えば、参照ライン上におけるエッジ点のＲＧＢ値の内のいずれかを保持してもよい。また、例えば、ＹＵＶといった他の色空間に変換した後の値を保持してもよい。また更に、参照ライン上の一つのエッジ点に対して一つの値ではなく、例えば、ＲＧＢ３値全てを保持しておき、特徴ベクトルの比較に際してＲＧＢ値それぞれを比較して平均二乗誤差を算出してもよい。この場合であっても、色の表現方法は、ＲＧＢに限られず、ＹＵＶなどの色空間により表現してもよい。
【００６７】
（変形例３）
上述した実施形態においては、参照ライン上の分割点における両側の情報を用いて対応する線分を探索する場合について説明したが、これに限られない。例えば、背景が大きく変わるような場合であれば、片側の情報が意味を持たないときがある。そのため、参照ライン上の分割点における片側の情報のみを用いて対応線分の探索を行なってもよい。また更に、片側ずつ独立して対応線分の探索を実施し、最後に２つの結果を統合してもよい。
【００６８】
（変形例４）
上述した実施形態においては、参照ライン上におけるエッジ点の両側の２画素の輝度値の平均値を特徴ベクトルの要素として保持していたが、特徴ベクトルの要素として保持する情報はこれに限られない。特徴ベクトルの要素は、輝度値の変化パターンを表す情報であればよい。例えば、参照ライン上でのエッジ検出オペレータのウィンドウサイズが大きい場合には、ウィンドウサイズに応じた画素数の輝度値の平均値を特徴ベクトルの要素として保持してもよい。また、参照ライン上のエッジ間にある画素の輝度値の情報を用いてもよい。これは、エッジ間では大きな輝度値の変化がなく、ほぼ同一の輝度値を持つと仮定できるためである。参照ライン上のエッジ間にある画素の輝度値の情報としては、例えば、輝度値の平均値やメディアン値を用いればよい。また更に、参照ライン上のエッジ点における輝度勾配を特徴ベクトルの要素として用いてもよい。
【００６９】
（変形例５）
線分の対応関係に誤対応が含まれていると仮定して、例えば、ロバスト推定手法により３次元線分を算出してもよい。非特許文献３に開示されている手法では、３枚の画像間で少なくとも６本の線分の対応を必要とする。そこで、非特許文献８に開示されているＲＡＮＳＡＣ（Random Sample Consensus）と呼ばれる方法を利用する。この場合、誤対応が含まれている場合であっても、３次元線分を正確に検出できる。より詳細には、対応付けられた線分の集合から、ランダムに６本を抽出し、非特許文献３の手法により３次元の線分及びカメラの位置及び姿勢を算出する。そして、算出されたカメラの位置及び姿勢に同意する集合中の線分の対応の数を計数する。この処理を一定数繰り返し、最も同意する数が多い場合の解を選択する。
【００７０】
（変形例６）
上述した実施形態においては、特徴ベクトル、代表特徴ベクトルの類似度を算出するために、平均二乗誤差を用いていたが、類似度の算出方法はこれに限られず、ベクトル間の類似度を比較できるのであれば、いかなる方法であってもよい。例えば、大きい入力には小さい出力を、小さい入力には大きい出力を返す関数を用いて、各次元の類似度を算出し、この出力の和又は平均値によりベクトルの類似度を算出してもよい。
【００７１】
（変形例７）
上述した実施形態においては、現実物体の３次元の線分を３枚の画像における線分の対応に基づいて算出していたが、これに限られない。例えば、画像の枚数は３枚に限られず、２枚以上であれば何枚であってもよい。仮に、画像の枚数が２枚であれば、２枚の画像間の線分を対応付けた後、例えば、非特許文献２又は非特許文献７の方法により３次元の線分を算出すればよい。また、画像が３枚以上であれば、画像間の線分を対応付けた後、非特許文献３の方法により３次元の線分を算出すればよい。
【００７２】
（変形例８）
上述した実施形態２においては、第１の画像及び第２の画像において検出された線分について代表特徴ベクトルを算出していたが、必ずしも、比較対象となる２枚の画像の両方の線分について代表特徴ベクトルを算出しなくてもよい。例えば、一方の画像上の線分のみ代表特徴ベクトルを算出する。そして、比較に際しては、線分上における分割点の特徴ベクトルと他方の画像の代表特徴ベクトルとを比較し、実施形態１のような投票を行なって対応線分を求めてもよい。
【００７３】
（変形例９）
上述した実施形態においては、検出した線分上の分割点を通過する線分上の画素情報に基づいて線分の特徴を表現（記述）していたが、線分の特徴の記述方法はこれに限られない。例えば、上述した実施形態においては、１画素幅の線分上の画素情報に基づいて記述を行なっていたが、複数画素の幅を持つウィンドウ内の画素情報に基づいて記述を行なってもよい。また、例えば、検出した線分を通過し、且つ当該検出した線分に直交する幅Ｎ画素のウィンドウを設定し、当該Ｎ画素の情報を用いてエッジを検出し、当該検出したエッジ点における画素情報に基づいて記述してもよい。
【００７４】
（変形例１０）
上述した実施形態においては、対象物体の３次元幾何モデルの作成を行なう場合について説明したが、他の用途を目的として上述した対応付け処理を行なってもよい。例えば、対応付けた線分の情報を用いて、複数の画像を撮影したときの撮像装置の相対的な位置及び姿勢を算出してもよい。
【００７５】
（その他の実施形態）
本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
0005538868.tif 000003
【図２】
0005538868.tif 000004
【図３】
0005538868.tif 000005
【図４】
0005538868.tif 000006
【図５】
0005538868.tif 000007
【図６】
0005538868.tif 000008
【図７】
0005538868.tif 000009
【図８】
0005538868.tif 000010
【図９】
0005538868.tif 000011