(57)【特許請求の範囲】
【請求項１】
複数の画像から三次元形状を構築するための装置であって、
前記複数の画像それぞれから、対応する特徴点の組合せを抽出する、特徴点抽出部と、
抽出された前記特徴点の組合せごとに、前記特徴点間の幾何学的関係を計算し、計算結果に基づいて、誤った特徴点の組合せを特定し、特定した前記誤った特徴点の組合せを排除する、フィルタリング部と、
前記複数の画像のうちの少なくとも２つの画像上に、抽出された前記特徴点とは異なる独立した互いに対応する２以上の線分又は２以上の点が指定された場合に、互いに対応する２以上の線分間の幾何学的関係、又は互いに対応する２以上の点間の幾何学的関係を特定し、特定した前記幾何学的関係を表現する数値行列を算出する、行列算出部と、
前記数値行列を用いて、抽出された前記特徴点の組合せのうち、特徴点間の幾何学的関係が矛盾する前記特徴点の組合せを特定し、特定した前記特徴点の組合せ以外の前記特徴点の組合せを用いて、前記三次元形状を構築する、形状構築部と、
を備え、
前記行列算出部は、更に、前記特徴点の組合せの数が不足して前記数値行列が算出できない場合においても、前記特徴点とは異なる独立した互いに対応する２以上の線分又は２以上の点を指定することで、前記フィルタリング部の処理により残った誤差の少ない特徴点の組み合わせから数値行列を算出する、
ことを特徴とする画像処理装置。
【請求項２】
前記形状構築部が、抽出された前記特徴点の組合せを構成している特徴点のうち、指定された、互いに対応する２以上の線分又は２以上の点に重なる特徴点を特定し、特定した特徴点を含む前記特徴点の組合せを排除して、前記三次元形状を構築する、
請求項１に記載の画像処理装置。
【請求項３】
前記形状構築部によって構築された前記三次元形状を画面上に表示する、表示部を更に備えている、
請求項１または２に記載の画像処理装置。
【請求項４】
前記形状構築部が、前記特徴点抽出部によって抽出された前記特徴点の組合せを用いて、仮の三次元形状を構築し、
前記表示部が、更に、前記仮の三次元形状を画面上に表示する、
請求項３に記載の画像処理装置。
【請求項５】
複数の画像から三次元形状を構築するための方法であって、
（ａ）前記複数の画像それぞれから、対応する特徴点の組合せを抽出する、ステップと、
（ｂ）抽出された前記特徴点の組合せごとに、前記特徴点間の幾何学的関係を計算し、計算結果に基づいて、誤った特徴点の組合せを特定し、特定した前記誤った特徴点の組合せを排除する、ステップと、
（ｃ）前記複数の画像のうちの少なくとも２つの画像上に、抽出された前記特徴点とは異なる独立した互いに対応する２以上の線分又は２以上の点が指定された場合に、互いに対応する２以上の線分間の幾何学的関係、又は互いに対応する２以上の点間の幾何学的関係を特定し、特定した前記幾何学的関係を表現する数値行列を算出する、ステップと、
（ｄ）前記数値行列を用いて、抽出された前記特徴点の組合せのうち、特徴点間の幾何学的関係が矛盾する前記特徴点の組合せを特定し、特定した前記特徴点の組合せ以外の前記特徴点の組合せを用いて、前記三次元形状を構築する、ステップと、
を有し、
さらに、（ｃ）のステップにおいて、前記特徴点の組合せの数が不足して前記数値行列が算出できない場合においても、前記特徴点とは異なる独立した互いに対応する２以上の線分又は２以上の点を指定することで、前記（ｂ）のステップにより残った誤差の少ない特徴点の組み合わせから数値行列を算出する、ステップと、
ことを特徴とする画像処理方法。
【請求項６】
前記（ｄ）のステップにおいて、
前記ステップ（ａ）で抽出された前記特徴点の組合せを構成している特徴点のうち、指定された、互いに対応する２以上の線分又は２以上の点に重なる特徴点を特定し、特定した特徴点を含む前記特徴点の組合せを排除して、前記三次元形状を構築する、
請求項５に記載の画像処理方法。
【請求項７】
（ｅ）前記（ｄ）のステップによって構築された前記三次元形状を画面上に表示する、ステップを更に有する、
請求項５または６に記載の画像処理方法。
【請求項８】
（ｆ）前記（ａ）のステップによって抽出された前記特徴点の組合せを用いて、仮の三次元形状を構築する、ステップと、
（ｇ）前記（ｆ）のステップで構築された前記仮の三次元形状を画面上に表示する、ステップと、
を更に有する請求項７に記載の画像処理方法。
【請求項９】
コンピュータによって、複数の画像から三次元形状を構築するためのプログラムであって、
前記コンピュータに、
（ａ）前記複数の画像それぞれから、対応する特徴点の組合せを抽出する、ステップと、
（ｂ）抽出された前記特徴点の組合せごとに、前記特徴点間の幾何学的関係を計算し、計算結果に基づいて、誤った特徴点の組合せを特定し、特定した前記誤った特徴点の組合せを排除する、ステップと、
（ｃ）前記複数の画像のうちの少なくとも２つの画像上に、抽出された前記特徴点とは異なる独立した互いに対応する２以上の線分又は２以上の点が指定された場合に、互いに対応する２以上の線分間の幾何学的関係、又は互いに対応する２以上の点間の幾何学的関係を特定し、特定した前記幾何学的関係を表現する数値行列を算出する、ステップと、
（ｄ）前記数値行列を用いて、抽出された前記特徴点の組合せのうち、特徴点間の幾何学的関係が矛盾する前記特徴点の組合せを特定し、特定した前記特徴点の組合せ以外の前記特徴点の組合せを用いて、前記三次元形状を構築する、ステップと、
を有し、
さらに、（ｃ）のステップにおいて、前記特徴点の組合せの数が不足して前記数値行列が算出できない場合においても、前記特徴点とは異なる独立した互いに対応する２以上の線分又は２以上の点を指定することで、前記（ｂ）のステップにより残った誤差の少ない特徴点の組み合わせから数値行列を算出する、ステップと、
を実行させる命令を含むプログラム。
【請求項１０】
前記（ｄ）のステップにおいて、
前記ステップ（ａ）で抽出された前記特徴点の組合せを構成している特徴点のうち、指定された、互いに対応する２以上の線分又は２以上の点に重なる特徴点を特定し、特定した特徴点を含む前記特徴点の組合せを排除して、前記三次元形状を構築する、
請求項９に記載のプログラム。
【請求項１１】
前記プログラムが、前記コンピュータに、
（ｅ）前記（ｄ）のステップによって構築された前記三次元形状を画面上に表示する、ステップを実行させる命令を更に含む、
請求項９または１０に記載のプログラム。
【請求項１２】
前記プログラムが、前記コンピュータに、
（ｆ）前記（ａ）のステップによって抽出された前記特徴点の組合せを用いて、仮の三次元形状を構築する、ステップと、
（ｇ）前記（ｆ）のステップで構築された前記仮の三次元形状を画面上に表示する、ステップと、
を実行させる命令を更に含む、
請求項１１に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の画像からの三次元形状の構築を可能にするための、画像処理装置、及び画像処理方法に関し、更には、これらを実現させるためのプログラムに関する。
【背景技術】
【０００２】
近年、画像に写っている対象の三次元形状を構築する技術が注目されている。このような技術の代表例としては、ＳｆＭ（Structure from Motion）が知られている。ＳｆＭでは、特定の対象をカメラの視点を変えながら複数回撮影し、得られた複数枚の画像から、特定の対象の三次元形状が復元される。【０００３】
具体的には、まず、ＳｆＭでは、画像毎に、その特徴量（例えば、SIFT特徴量、SURF特徴量）が計算され、画像の拡大縮小、回転、及び照度変化に強いロバストネスな特徴点が抽出される。次に、画像間で、抽出した特徴点のマッチングが実行され、一致する特徴点のペアが抽出される。次に、例えば、ロバスト推定（Robust Estimation）によって、特徴点ペアの幾何学的な関係が計算され、誤った特徴点ペアが除外される。【０００４】
その後、幾つかの特徴点ペア毎に、これらの幾何学的な関係に基づいて、Fundamental行列が算出され、算出された各Fundamental行列間での差が最も少なくなるように、特徴点ペア毎の幾何学的な関係が調整される。そして、調整後の幾何学的な関係に基づいて、三次元形状（点群）が再構築される。なお、この時の誤差の調整方法としては、Bundle Adjustmentと呼ばれる処理手法が挙げられる。【０００５】
ところで、上述のＳｆＭでは、マッチングに間違いが発生する場合があり、この場合、異なる特徴点間でペアが抽出されてしまい、復元される三次元形状の精度が低下してしまう。また、抽出された特徴点のペアが少なかったり、マッチングがうまく行かなかったりして、特徴点ペアが少ない領域が発生する場合がある。この場合も、復元される三次元形状の精度が低下してしまう。【０００６】
これに対して、特許文献１は、対応する特徴点の位置を補正するシステムを開示している。具体的には、特許文献１に開示されたシステムは、まず、２枚の画像をそれぞれのエピポーラ線が走査線に平行となるよう配置し、走査線毎に、各画像から対応する特徴点を抽出する。【０００７】
次に、このシステムは、ユーザーによる各画像上への対応する箇所を指定する線分の入力を受け付ける。そして、システムは、走査線上の対応する各特徴点が、この走査線と入力された線分との交点に一致しているかどうかを判定し、一致していない場合は、各特徴点の位置を交点の位置に補正する。その後、システムは、位置が補正された特徴点を用いて、三次元形状の再構築を実行する。【０００８】
このように、特許文献１に開示されたシステムによれば、間違った特徴点ペアが抽出されてしまうという問題、及び特徴点ペアが少ない領域が発生するという問題が解消されるので、復元される三次元形状の精度が低下するという問題が解消される。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特許第５３１１４６５号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、特許文献１に開示されたシステムでは、特徴点の位置の補正は、２枚の画像のエピポーラ線に沿った走査線上でしか行われないので、同一の走査線上にない間違った特徴点ペアについて補正されることはない。このため、特許文献１に開示されたシステムでは、間違った特徴点ペアの修正が不十分であり、復元される三次元形状の精度の低下を抑制することが困難となる。【００１１】
本発明の目的の一例は、上記問題を解消し、複数の画像から対応する特徴点の組合せを抽出するに際して、間違った特徴点の組合せの抽出を抑制しうる、画像処理装置、画像処理方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【００１２】
上記目的を達成するため、本発明の一側面における画像処理装置は、複数の画像から三次元形状を構築するための装置であって、
前記複数の画像それぞれから、対応する特徴点の組合せを抽出する、特徴点抽出部と、
前記複数の画像のうちの少なくとも２つの画像上に、互いに対応する２以上の線分又は２以上の点が指定された場合に、互いに対応する２以上の線分間の幾何学的関係、又は互いに対応する２以上の点間の幾何学的関係を特定し、特定した前記幾何学的関係を表現する数値行列を算出する、行列算出部と、
前記数値行列を用いて、抽出された前記特徴点の組合せのうち、特徴点間の幾何学的関係が矛盾する前記特徴点の組合せを特定し、特定した前記特徴点の組合せ以外の前記特徴点の組合せを用いて、前記三次元形状を構築する、形状構築部と、
を備えている、ことを特徴とする。【００１３】
また、上記目的を達成するため、本発明の一側面における画像処理方法は、複数の画像から三次元形状を構築するための方法であって、
（ａ）前記複数の画像それぞれから、対応する特徴点の組合せを抽出する、ステップと、
（ｂ）前記複数の画像のうちの少なくとも２つの画像上に、互いに対応する２以上の線分又は２以上の点が指定された場合に、互いに対応する２以上の線分間の幾何学的関係、又は互いに対応する２以上の点間の幾何学的関係を特定し、特定した前記幾何学的関係を表現する数値行列を算出する、ステップと、
（ｃ）前記数値行列を用いて、抽出された前記特徴点の組合せのうち、特徴点間の幾何学的関係が矛盾する前記特徴点の組合せを特定し、特定した前記特徴点の組合せ以外の前記特徴点の組合せを用いて、前記三次元形状を構築する、ステップと、
を有する、ことを特徴とする。【００１４】
更に、上記目的を達成するため、本発明の一側面におけるプログラムは、コンピュータによって、複数の画像から三次元形状を構築するためのプログラムであって、
前記コンピュータに、
（ａ）前記複数の画像それぞれから、対応する特徴点の組合せを抽出する、ステップと、
（ｂ）前記複数の画像のうちの少なくとも２つの画像上に、互いに対応する２以上の線分又は２以上の点が指定された場合に、互いに対応する２以上の線分間の幾何学的関係、又は互いに対応する２以上の点間の幾何学的関係を特定し、特定した前記幾何学的関係を表現する数値行列を算出する、ステップと、
（ｃ）前記数値行列を用いて、抽出された前記特徴点の組合せのうち、特徴点間の幾何学的関係が矛盾する前記特徴点の組合せを特定し、特定した前記特徴点の組合せ以外の前記特徴点の組合せを用いて、前記三次元形状を構築する、ステップと、
を実行させることを特徴とする。
【発明の効果】
【００１５】
以上のように、本発明によれば、複数の画像から対応する特徴点の組合せを抽出するに際して、間違った特徴点の組合せの抽出を抑制することができる。
【図面の簡単な説明】
【００１６】
【図１】図１は、本発明の実施の形態における画像処理装置の概略構成を示すブロック図である。
【図２】図２は、本発明の実施の形態における画像処理装置の具体的構成を示すブロック図である。
【図３】図３は、本実施の形態で処理対象となる複数の画像の一例を示す図である。
【図４】図４は、本発明の実施の形態における行列算出部による処理を説明する図である。
【図５】図５は、本発明の実施の形態における形状構築部による処理を説明する図である。
【図６】図６は、本発明の実施の形態における画像処理装置動作を示すフロー図である。
【図７】図７は、本発明の実施の形態における画像処理装置を実現するコンピュータの一例を示すブロック図である。
【発明を実施するための形態】
【００１７】
（実施の形態）
以下、本発明の実施の形態における、画像処理装置、画像処理方法、及びプログラムについて、図１〜図７を参照しながら説明する。
【００１８】
［装置構成］
最初に、図１を用いて、本実施の形態における画像処理装置の概略構成について説明する。図１は、本発明の実施の形態における画像処理装置の概略構成を示すブロック図である。
【００１９】
図１に示すように、本実施の形態における画像処理装置１０は、複数の画像から三次元形状を構築する装置である。画像処理装置１０には、処理対象となる複数枚の画像の画像データが入力される。
【００２０】
また、図１に示すように、画像処理装置１０は、特徴点抽出部１１と、行列算出部１２と、形状構築部１３とを備えている。このうち、特徴点抽出部１１は、複数の画像それぞれから、対応する特徴点の組合せを抽出する。
【００２１】
行列算出部１２は、複数の画像のうちの少なくとも２つの画像上に、互いに対応する２以上の線分又は２以上の点が指定された場合に、互いに対応する２以上の線分間の幾何学的関係、又は互いに対応する２以上の点間の幾何学的関係を特定する。そして、行列算出部１２は、特定した幾何学的関係を表現する数値行列を算出する。
【００２２】
形状構築部１３は、行列算出部１２によって算出された数値行列を用いて、抽出された特徴点の組合せのうち、特徴点間の幾何学的関係が矛盾する特徴点の組合せを特定する。そして、形状構築部１３は、特定した特徴点の組合せ以外の特徴点の組合せを用いて、三次元形状を構築する。
【００２３】
このように、本実施の形態では、指定された２以上の線分又は点から特定された幾何学的関係から、間違った特徴点の組合せが特定されるので、同一の走査線上にない間違った特徴点の組合せも排除できる。本実施の形態によれば、複数の画像から対応する特徴点の組合せを抽出するに際して、間違った特徴点の組合せの抽出を抑制でき、復元される三次元形状の精度を向上させることができる。
【００２４】
続いて、図２〜図５を用いて、本実施の形態における画像処理装置１０の構成についてより具体的に説明する。図２は、本発明の実施の形態における画像処理装置の具体的構成を示すブロック図である。
【００２５】
図２に示すように、画像処理装置１０は、本実施の形態では、特徴点抽出部１１、行列算出部１２、及び形状構築部１３に加えて、画像取得部１４と、フィルタリング部１５と、入力受付部１６と、表示部１７とを更に備えている。
【００２６】
画像取得部１４は、外部の装置、例えば、撮像装置、端末装置、画像データを保持している記憶装置等から、三次元形状の構築対象が写った複数の画像それぞれの画像データを取得する。図３は、本実施の形態で処理対象となる複数の画像の一例を示す図である。図３の例では、ペア画像が例示されているが、本実施の形態において対象となる画像の枚数は特に限定されるものではない。
【００２７】
特徴点抽出部１１は、本実施の形態では、画像毎に、例えば、SIFT特徴量、又はSURF特徴量を計算して特徴点を特定し、更に、画像間で対応する特徴点同士を、対応する特徴点の組合せとして抽出する。なお、図３の例では、画像が２枚であるため、特徴点の組合せは、特徴点ペアである。また、図３において、丸で囲まれた部分が特徴点の一つである。
【００２８】
フィルタリング部１５は、特徴点の組合せ毎に、特徴点間の幾何学的な関係を計算し、計算結果に基づいて、誤った特徴点の組合せを特定し、特定した特徴点の組合せを排除する。フィルタリング部１５によるフィルタリング処理は、従来と同様に、ロバスト推定を用いて行われる。本実施の形態では、後述する形状構築部１３によるフィルタリングに加えて、フィルタリング部１５によるフィルタリングも行われるので、より確実に間違った特徴点の組合せが排除される。
【００２９】
入力受付部１６は、処理対象となる各画像上において互いに対応する線分又は点が指定されると、指定された線分又は点の入力を受け付ける。また、入力受付部１６は、各画像上で互いに対応する線分の入力を受け付けた場合は各線分の情報（始点及び終点の座標）を、互いに対応する点の入力を受け付けた場合は各点の情報（座標）を、行列算出部１２に通知する。なお、線分又は点の指定は、画像処理装置１０のユーザーによって行われても良いし、別の計算機によって行われても良い。
【００３０】
行列算出部１２は、入力受付部１６から各画像上の線分又は点の情報が通知されると、通知された情報に基づいて、線分間又は点間の幾何学的関係を特定し、特定した幾何学的関係を表現する数値行列を算出し、この数値行列を絶対的数値行列として定義する。行列算出部１２は、入力受付部１６から通知された各画像上の線分又は点の情報から数値行列が算出出来ない、または画像によっては線分又は点の情報が存在しない場合には、特徴点抽出部１１で抽出されフィルタリング部１５で残った誤差の少ない特徴点の組み合わせから数値行列を算出することも出来る。ただし、この場合算出される数値行列は従来と同様の数値行列であり、絶対的数値行列ではない。
【００３１】
ここで、図４を用いて、行列算出部１２における処理についてより具体的に説明する。図４は、本発明の実施の形態における行列算出部による処理を説明する図である。図４において、Ｅはエピポーラ面を示し、Ｏｉは一方の画像のカメラの中心位置を示し、Ｏ’ｉは他方の画像のカメラの中心位置を示している。また、図４において、左右に示された並行四辺形はそれぞれ画像のフレームを示している。
【００３２】
また、図４の例では、一方の画像において線分Ｌが指定され、他方の画像において線分Ｌ’が指定されており、両線分は対応している。この場合において、線分Ｌにおいて、その始点と交わるエピポーラ線ｌｎと、終点で交わるエピポーラ線ｌｎ＋ｍとを絶対的エピポーラ線として定義し、線分Ｌ‘においても、その始点と交わるエピポーラ線ｌ’ｎと、終点で交わるエピポーラ線ｌ’ｎ＋ｍとを絶対的エピポーラ線として定義する。
【００３３】
更に、線分Ｌと絶対的エピポーラ線ｌｎとの交点ｘｉと、線分Ｌと絶対的エピポーラ線ｌ’ｎとの交点ｘ’ｉとは、絶対的な特徴点の組合せとして定義する。また、線分Ｌと絶対的エピポーラ線ｌｎ＋ｍとの交点ｘｊと、線分Ｌ’と絶対的エピポーラ線ｌ’ｎ＋ｍとの交点ｘ’ｊも、絶対的な特徴点の組合せとして定義する。
【００３４】
なお、図４に示すように、エピポーラ線ｌｎとエピポーラ線ｌｎ＋ｍとの間に、任意のエピポーラ線ｌｎ＋１及びｌｎ＋２が設定されていても良い。この場合、同様に、エピポーラ線ｌ’ｎとエピポーラ線ｌ’ｎ＋ｍとの間にも、任意のエピポーラ線ｌ’ｎ＋１及びｌ’ｎ＋２が設定される。また、この場合、線分Ｌと新たに設定されたエピポーラ線ｌｎ＋１及びｌｎ＋２それぞれとの交点は、線分Ｌ’と新たに設定されたエピポーラ線ｌ’ｎ＋１及びｌ’ｎ＋２それぞれとの交点との間で、絶対的な特徴点の組合せとなる。なお、エピポーラ線間の間隔は任意の値に設定される。
【００３５】
従って、図４の例においては、行列算出部１２は、線分間の幾何学的関係として、絶対的な特徴点の組合せを求め、求めた特徴点の組合せを用いて、下記の数１の関係式から、絶対的数値行列として、Fundamental行列（参照文献）を算出する。なお、下記の数１において、「ｘ」は、三次元空間における点Ｘを一方の画像上に射影することによって得られた二次元上の点である。「ｘ’」は、三次元空間における点Ｘを他方の画像上に射影することによって得られた二次元上の点である。Ｔは転置行列である。また、ＦはFundamental行列である。また、本実施の形態において数値行列は、Fundamental行列に限定されるものではなく、幾何学的関係を表現できる行列であれば良い。
【００３６】
（数１）
ｘ’ＴＦｘ＝０
【００３７】
参照文献：Richard Hartley and Andrew Zisserman, “Multiple View Geometry in Computer Vision Second Edition”,Cambridge University Press, March 2004.
【００３８】
形状構築部１３は、本実施の形態では、まず、行列算出部１２によって算出された数値行列（Fundamental行列）を用いて、特徴点抽出部１１で抽出された特徴点の組合せ（フィルタリング部１５で除外されたものを除く）から、幾何学的関係が矛盾する特徴点の組合せを排除する。その後、形状構築部１３は、幾何学的関係が矛盾する特徴点の組合せが排除された特徴点の組合せを用いて、三次元形状を構築するが、その際、入力受付部１６によって受け付けられた、対応する点、又は対応する線分上の点も、特徴点の組合せとして用いることができる。
【００３９】
また、形状構築部１３は、特徴点抽出部１１で抽出された特徴点の組合せ（フィルタリング部１５で除外されたものを除く）の中から、指定された線分又は点に重なる特徴点を特定し、特定した特徴点を含む特徴点の組合せも排除することができる。これは、一方の線分又は点に重なる特徴点に対応する特徴点が、他方の線分又は点の上にないときは、この特徴点の組合せは間違っている可能性が高いからである。その後、形状構築部１３は、残った特徴点の組合せを用いて、三次元形状を構築する。
【００４０】
ここで、図５を用いて、形状構築部１３における処理についてより具体的に説明する。図５は、本発明の実施の形態における形状構築部による処理を説明する図である。図５において、図４示された符号が付されたものは、図４で同じ記号が付与されたものを示している。そして、図５においては、特徴点ｐｉと特徴点ｐ’ｉとの組合せが間違っているかどうかの判断対象であるとする。
【００４１】
図５の例において、形状構築部１３は、エピポーラ線についての下記の数２に示す関係を用いて、特徴点ｐｉが存在しているエピポーラ線ｌ１に対応するエピポーラ線ｌ’１を算出する。
【００４２】
（数２）
ｌ’＝Ｆｘ
【００４３】
そして、形状構築部１３は、算出したエピポーラ線ｌ’１と特徴点ｐ’ｉとの距離ｄが、閾値以上となっているかどうかを判定し、距離ｄが閾値以上となっている場合は、特徴点ｐｉと特徴点ｐ’ｉとの組合せは間違っていると判定する。この場合、形状構築部１３は、特徴点ｐｉと特徴点ｐ’ｉとの組合せを排除して、三次元形状を構築する。
【００４４】
また、本実施の形態においては、形状構築部１３は、フィルタリング部１５によるフィルタリングが済んだ特徴点の組合せを用いて、一旦、仮の三次元形状を構築しても良い。この場合は、ユーザーは、仮の三次元形状に基づいて、三次元形状の復元が不十分な箇所を特定できるので、適切な線分又は点を指定することが可能となる。その後、形状構築部１３は、三次元形状を再構築する。
【００４５】
また、表示部１７は、形状構築部１３によって構築された三次元形状を、表示装置２０の画面上に表示させる。具体的には、表示部１７は、構築された三次元形状を二次元画面上に表示するための画像データを作成し、作成した画像データを表示装置２０に出力する。更に、表示部１７は、形状構築部１３が仮の三次元形状を構築した場合も、この仮の三次元形状を表示装置２０の画面上に表示させる。
【００４６】
［装置動作］
次に、本発明の実施の形態における画像処理装置１０の動作について図６を用いて説明する。図６は、本発明の実施の形態における画像処理装置動作を示すフロー図である。以下の説明においては、適宜図１〜図５を参酌する。また、本実施の形態では、画像処理装置１０を動作させることによって、画像処理方法が実施される。よって、本実施の形態における画像処理方法の説明は、以下の画像処理装置１０の動作説明に代える。
【００４７】
図６に示すように、最初に、画像取得部１４は、外部の装置から、三次元形状の構築対象が写った複数の画像それぞれの画像データを取得する（ステップＡ１）
【００４８】
次に、特徴点抽出部１１は、ステップＡ１で取得された画像データの画像毎に、特徴量を計算して特徴点を特定し、画像間で対応する特徴点同士を、対応する特徴点の組合せとして抽出する（ステップＡ２）。
【００４９】
次に、フィルタリング部１５は、ステップＡ２で抽出された特徴点の組合せ毎に、特徴点間の幾何学的な関係を計算し、計算結果に基づいて、誤った特徴点の組合せを特定し、特定した特徴点の組合せを排除する（ステップＡ３）。
【００５０】
次に、形状構築部１３は、ステップＡ３によるフィルタリング処理が行われた後の特徴点の組合せを用いて、仮の三次元形状を構築する（ステップＡ４）。また、ステップＡ４が実行されると、表示部１７は、ステップＡ４で構築された仮の三次元形状を表示装置２０の画面上に表示させる。
【００５１】
ステップＡ４が実行され、仮の三次元形状が表示装置２０の画面上に表示されると、ユーザーは、入力装置（図２において図示せず）を介して、各画像上において互いに対応する線分又は点を指定する。これにより、入力受付部１６は、指定された線分又は点の入力を受け付ける（ステップＡ５）。また、入力受付部１６は、指定された各線分の情報又は各点の情報を、行列算出部１２に通知する。
【００５２】
次に、行列算出部１２は、ステップＡ５が実行されると、各線分の情報又は各点の情報に基づいて、線分間又は点間の幾何学的関係を特定し、特定した幾何学的関係を表現する数値行列を算出する（ステップＡ６）。
【００５３】
次に、形状構築部１３は、ステップＡ６で算出された数値行列を用いて、ステップＡ３の処理の適用後の特徴点の組合せから、幾何学的関係が矛盾する特徴点の組合せを排除する（ステップＡ７）。
【００５４】
次に、形状構築部１３は、残った特徴点の組合せを用いて、再度、三次元形状を構築する（ステップＡ８）。その後、表示部１７は、ステップＡ８で構築された三次元形状を表示装置２０の画面上に表示させる（ステップＡ９）。
【００５５】
［実施の形態の効果］
以上のように本実施の形態によれば、同一の走査線上にない間違った特徴点の組合せも排除して、三次元形状を構築することができる。このため、本実施の形態によれば、複数の画像から対応する特徴点の組合せを抽出するに際して、間違った特徴点の組合せの抽出を抑制できる。また、その結果、復元される三次元形状の精度が向上することになる。
【００５６】
［プログラム］
本実施の形態におけるプログラムは、コンピュータに、図６に示すステップＡ１〜Ａ９を実行させるプログラムであれば良い。このプログラムをコンピュータにインストールし、実行することによって、本実施の形態における画像処理装置１０と画像処理方法とを実現することができる。この場合、コンピュータのプロセッサは、特徴点抽出部１１、行列算出部１２、形状構築部１３、画像取得部１４、フィルタリング部１５、入力受付部１６、及び表示部１７として機能し、処理を行なう。
【００５７】
また、本実施の形態におけるプログラムは、複数のコンピュータによって構築されたコンピュータシステムによって実行されても良い。この場合は、例えば、各コンピュータが、それぞれ、特徴点抽出部１１、行列算出部１２、形状構築部１３、画像取得部１４、フィルタリング部１５、入力受付部１６、及び表示部１７のいずれかとして機能しても良い。
【００５８】
ここで、本実施の形態におけるプログラムを実行することによって、画像処理装置１０を実現するコンピュータについて図７を用いて説明する。図７は、本発明の実施の形態における画像処理装置を実現するコンピュータの一例を示すブロック図である。
【００５９】
図７に示すように、コンピュータ１１０は、ＣＰＵ１１１と、メインメモリ１１２と、記憶装置１１３と、入力インターフェイス１１４と、表示コントローラ１１５と、データリーダ／ライタ１１６と、通信インターフェイス１１７とを備える。これらの各部は、バス１２１を介して、互いにデータ通信可能に接続される。なお、コンピュータ１１０は、ＣＰＵ１１１に加えて、又はＣＰＵ１１１に代えて、ＧＰＵ（Graphics Processing Unit）、又はＦＰＧＡ（Field-Programmable Gate Array）を備えていても良い。
【００６０】
ＣＰＵ１１１は、記憶装置１１３に格納された、本実施の形態におけるプログラム（コード）をメインメモリ１１２に展開し、これらを所定順序で実行することにより、各種の演算を実施する。メインメモリ１１２は、典型的には、ＤＲＡＭ（Dynamic Random Access Memory）等の揮発性の記憶装置である。また、本実施の形態におけるプログラムは、コンピュータ読み取り可能な記録媒体１２０に格納された状態で提供される。なお、本実施の形態におけるプログラムは、通信インターフェイス１１７を介して接続されたインターネット上で流通するものであっても良い。
【００６１】
また、記憶装置１１３の具体例としては、ハードディスクドライブの他、フラッシュメモリ等の半導体記憶装置が挙げられる。入力インターフェイス１１４は、ＣＰＵ１１１と、キーボード及びマウスといった入力機器１１８との間のデータ伝送を仲介する。表示コントローラ１１５は、ディスプレイ装置１１９と接続され、ディスプレイ装置１１９での表示を制御する。
【００６２】
データリーダ／ライタ１１６は、ＣＰＵ１１１と記録媒体１２０との間のデータ伝送を仲介し、記録媒体１２０からのプログラムの読み出し、及びコンピュータ１１０における処理結果の記録媒体１２０への書き込みを実行する。通信インターフェイス１１７は、ＣＰＵ１１１と、他のコンピュータとの間のデータ伝送を仲介する。
【００６３】
また、記録媒体１２０の具体例としては、ＣＦ（Compact Flash（登録商標））及びＳＤ（Secure Digital）等の汎用的な半導体記憶デバイス、フレキシブルディスク（Flexible Disk）等の磁気記録媒体、又はＣＤ−ＲＯＭ（Compact Disk Read Only Memory）などの光学記録媒体が挙げられる。
【００６４】
なお、本実施の形態における画像処理装置１０は、プログラムがインストールされたコンピュータではなく、各部に対応したハードウェアを用いることによっても実現可能である。更に、画像処理装置１０は、一部がプログラムで実現され、残りの部分がハードウェアで実現されていてもよい。
【００６５】
上述した実施の形態の一部又は全部は、以下に記載する（付記１）〜（付記１２）によって表現することができるが、以下の記載に限定されるものではない。
【００６６】
（付記１）
複数の画像から三次元形状を構築するための装置であって、
前記複数の画像それぞれから、対応する特徴点の組合せを抽出する、特徴点抽出部と、
前記複数の画像のうちの少なくとも２つの画像上に、互いに対応する２以上の線分又は２以上の点が指定された場合に、互いに対応する２以上の線分間の幾何学的関係、又は互いに対応する２以上の点間の幾何学的関係を特定し、特定した前記幾何学的関係を表現する数値行列を算出する、行列算出部と、
前記数値行列を用いて、抽出された前記特徴点の組合せのうち、特徴点間の幾何学的関係が矛盾する前記特徴点の組合せを特定し、特定した前記特徴点の組合せ以外の前記特徴点の組合せを用いて、前記三次元形状を構築する、形状構築部と、
を備えている、ことを特徴とする画像処理装置。
【００６７】
（付記２）
前記形状構築部が、抽出された前記特徴点の組合せを構成している特徴点のうち、指定された、互いに対応する２以上の線分又は２以上の点に重なる特徴点を特定し、特定した特徴点を含む前記特徴点の組合せを排除して、前記三次元形状を構築する、
付記１に記載の画像処理装置。
【００６８】
（付記３）
前記形状構築部によって構築された前記三次元形状を画面上に表示する、表示部を更に備えている、
付記１または２に記載の画像処理装置。
【００６９】
（付記４）
前記形状構築部が、前記特徴点抽出部によって抽出された前記特徴点の組合せを用いて、仮の三次元形状を構築し、
前記表示部が、更に、前記仮の三次元形状を画面上に表示する、
付記３に記載の画像処理装置。
【００７０】
（付記５）
複数の画像から三次元形状を構築するための方法であって、
（ａ）前記複数の画像それぞれから、対応する特徴点の組合せを抽出する、ステップと、
（ｂ）前記複数の画像のうちの少なくとも２つの画像上に、互いに対応する２以上の線分又は２以上の点が指定された場合に、互いに対応する２以上の線分間の幾何学的関係、又は互いに対応する２以上の点間の幾何学的関係を特定し、特定した前記幾何学的関係を表現する数値行列を算出する、ステップと、
（ｃ）前記数値行列を用いて、抽出された前記特徴点の組合せのうち、特徴点間の幾何学的関係が矛盾する前記特徴点の組合せを特定し、特定した前記特徴点の組合せ以外の前記特徴点の組合せを用いて、前記三次元形状を構築する、ステップと、
を有する、ことを特徴とする画像処理方法。
【００７１】
（付記６）
前記（ｃ）のステップにおいて、
前記ステップ（ａ）で抽出された前記特徴点の組合せを構成している特徴点のうち、指定された、互いに対応する２以上の線分又は２以上の点に重なる特徴点を特定し、特定した特徴点を含む前記特徴点の組合せを排除して、前記三次元形状を構築する、
付記５に記載の画像処理方法。
【００７２】
（付記７）
（ｄ）前記（ｃ）のステップによって構築された前記三次元形状を画面上に表示する、ステップを更に有する、
付記５または６に記載の画像処理方法。
【００７３】
（付記８）
（ｅ）前記（ａ）のステップによって抽出された前記特徴点の組合せを用いて、仮の三次元形状を構築する、ステップと、
（ｆ）前記（ｅ）のステップで構築された前記仮の三次元形状を画面上に表示する、ステップと、
を更に有する付記７に記載の画像処理方法。
【００７４】
（付記９）
コンピュータによって、複数の画像から三次元形状を構築するためのプログラムであって、
前記コンピュータに、
（ａ）前記複数の画像それぞれから、対応する特徴点の組合せを抽出する、ステップと、
（ｂ）前記複数の画像のうちの少なくとも２つの画像上に、互いに対応する２以上の線分又は２以上の点が指定された場合に、互いに対応する２以上の線分間の幾何学的関係、又は互いに対応する２以上の点間の幾何学的関係を特定し、特定した前記幾何学的関係を表現する数値行列を算出する、ステップと、
（ｃ）前記数値行列を用いて、抽出された前記特徴点の組合せのうち、特徴点間の幾何学的関係が矛盾する前記特徴点の組合せを特定し、特定した前記特徴点の組合せ以外の前記特徴点の組合せを用いて、前記三次元形状を構築する、ステップと、
を実行させる命令を含むプログラム。
【００７５】
（付記１０）
前記（ｃ）のステップにおいて、
前記ステップ（ａ）で抽出された前記特徴点の組合せを構成している特徴点のうち、指定された、互いに対応する２以上の線分又は２以上の点に重なる特徴点を特定し、特定した特徴点を含む前記特徴点の組合せを排除して、前記三次元形状を構築する、
付記９に記載のプログラム。
【００７６】
（付記１１）
前記プログラムが、前記コンピュータに、
（ｄ）前記（ｃ）のステップによって構築された前記三次元形状を画面上に表示する、ステップを実行させる命令を更に含む、
付記９または１０に記載のプログラム。
【００７７】
（付記１２）
前記プログラムが、前記コンピュータに、
（ｅ）前記（ａ）のステップによって抽出された前記特徴点の組合せを用いて、仮の三次元形状を構築する、ステップと、
（ｆ）前記（ｅ）のステップで構築された前記仮の三次元形状を画面上に表示する、ステップと、
を実行させる命令を更に含む、
付記１１に記載のプログラム。
【００７８】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記実施の形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００７９】
この出願は、２０１７年９月２９日に出願された日本出願特願２０１７−１９０３７７を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００８０】
以上のように、本発明によれば、複数の画像から対応する特徴点の組合せを抽出するに際して、間違った特徴点の組合せの抽出を抑制することができる。本発明は、ＳｆＭといった複数の画像から三次元形状を構築する技術に有用である。
【符号の説明】
【００８１】
１０  画像処理装置
１１  特徴点抽出部
１２  行列算出部
１３  形状構築部
１４  画像取得部
１５  フィルタリング部
１６  入力受付部
１７  表示部
１１０  コンピュータ
１１１  ＣＰＵ
１１２  メインメモリ
１１３  記憶装置
１１４  入力インターフェイス
１１５  表示コントローラ
１１６  データリーダ／ライタ
１１７  通信インターフェイス
１１８  入力機器
１１９  ディスプレイ装置
１２０  記録媒体
１２１  バス
【図１】
0006989153.tif 000002
【図２】
0006989153.tif 000003
【図３】
0006989153.tif 000004
【図４】
0006989153.tif 000005
【図５】
0006989153.tif 000006
【図６】
0006989153.tif 000007
【図７】
0006989153.tif 000008