(57)【要約】      （修正有）【課題】単一の２Ｄ画像から抽出された２Ｄラインから３Ｄワールド座標系内の３Ｄラインを再構成する方法を提供する。【解決手段】シーンの単一の画像内の２次元（２Ｄ）ラインから３Ｄワールド座標系内の３次元（３Ｄ）ラインを再構成する方法が、消失点を用いて２Ｄラインを検出し、クラスター化する。頂点およびエッジの制約グラフが生成され、頂点は、２Ｄラインを表し、エッジは、２Ｄラインに対する制約を表す。次に、制約を満たす３Ｄラインを特定し、特定された制約を用いて、３Ｄラインを再構成する。【選択図】図１
2014229305.tif 000002
【特許請求の範囲】
【請求項１】
シーンの単一の画像内の２次元（２Ｄ）ラインから３Ｄワールド座標系内の３次元（３Ｄ）ラインを再構成する方法であって、
消失点を用いて前記２Ｄラインを検出およびクラスター化するステップと、
頂点およびエッジの制約グラフを生成するステップであって、前記頂点は、前記２Ｄラインを表し、前記エッジは、前記２Ｄラインに対する制約を表す、ステップと、
前記３Ｄライン上で満たされる前記２Ｄラインに対する前記制約を特定するステップと、
前記特定された制約を用いて、前記３Ｄワールド座標系における前記３Ｄラインを再構成するステップと、
を含む、シーンの単一の画像内の２次元ラインから３Ｄワールド座標系内の３Ｄラインを再構成する方法。
【請求項２】
前記制約は、直交性制約、共線性制約、および結合点制約である、請求項１に記載の方法。
【請求項３】
前記特定するステップは、線形計画法を用いる、請求項１に記載の方法。
【請求項４】
前記３Ｄラインを用いて前記シーンを再構成するステップ
をさらに含む、請求項１に記載の方法。
【請求項５】
前記線形計画法におけるペナルティ項は、Ｌ結合点、Ｘ結合点、Ｔ結合点、Ｗ結合点、およびＹ結合点を用いる、請求項３に記載の方法。
【請求項６】
前記線形計画法の解に対し最小全域木アルゴリズムを用いて前記満たされる制約を特定する、請求項３に記載の方法。
【請求項７】
前記再構成は、複数の画像に適用される、請求項１に記載の方法。
【請求項８】
前記３Ｄラインは、立体コンテンツを生成するのに用いられる、請求項１に記載の方法。
【請求項９】
前記３Ｄラインは、物体検出および物体認識の３Ｄコンテキストを提供するのに用いられる、請求項１に記載の方法。
【請求項１０】
カメラを家庭用品上に搭載して屋内シーンを再構成する、請求項４に記載の方法。
【請求項１１】
前記屋内シーン再構成を用いて、暖房、換気、および空調ユニットにおける空気の流れの最適制御を行う、請求項１０に記載の方法。
【請求項１２】
カメラを自動車に搭載し、大きなシーンの再構成を用いて障害を検出する、請求項７に記載の方法。
【請求項１３】
カメラを自動車に搭載し、大きなシーンの再構成を３Ｄ街モデルとマッチングして自動車のロケーションを計算する、請求項７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはコンピュータービジョンに関し、より詳細には、単一の２Ｄ画像内の２Ｄラインから３Ｄワールド座標系内の３Ｄラインを再構成し、シーン再構成に３Ｄラインを用いることができるようにすることに関する。
【背景技術】
【０００２】
コンピュータービジョンにおける基本的な問題は、単一ビュー再構成（ＳＶＲ）である。ＳＶＲは、単一の２Ｄ画像から３Ｄ実世界シーンを復元する問題に対処する。
【０００３】
人工構造物、例えば、建物および部屋を含む屋内シーン、または屋外シーンの２Ｄ画像において、顕著な特徴は、３つの直交する方向における３Ｄラインである。画像内でラインが交差するときを求めるのは、比較的容易である。しかしながら、これは、必ずしも、３Ｄ実世界において対応するラインが交差することを意味するものではない。
【０００４】
自明な反例として、画像内の共通の消失点を共有するラインがある。これらのラインは、消失点において交差するように見えるが、いずれも実世界において交差せず、実世界では、これらのラインは、互いに平行である。このため、画像内の見掛けの交差が、実世界の交差に対応するときを特定するのは困難である。ラインの３Ｄ構造を推測するには、いくつかの難題がある。
【０００５】
最大の難題は、誤交差を生じる画像内の遮蔽エッジに関するものである。実画像におけるライン検出方法は、多くの場合に重要なラインを見逃し、スプリアスラインを生成する。検出されるラインは、多くの場合に途切れているかまたは短く、交差の証拠がなくなっている。加えて、実世界シーンは、クラッターに起因して特に難易度が高い。
【０００６】
ＳＶＲは、コンピュータービジョンにおける明確には解決されていない問題である。再構成は、幾何学的または意味的に行うことができる。最も一般的な幾何学的再構成方法は、ラインを凸ライン、凹ライン、または遮蔽ラインとしてラベリングすることに基づく。ラインラベルリング問題は、一般に、ＮＰ困難である。いくつかの難易度が高い線画が研究され、ＳＶＲ問題を解決する新規の制約充足方法が開発された。これらの方法は、主に合成線画またはコンピューター生成線画に対し動作し、一般に、実世界画像には不十分である。実画像に対し良好な結果を与えるほとんどの他の幾何学的単一ビュー再構成方法は、ある種のユーザーインタラクションに頼る。
【０００７】
より全体的な手法が利用可能になるにつれて、ＳＶＲ問題への関心が新たになっている。例えば、画像内のピクセルは、空、建物および地面として分類することができる。その分類により、面の向きの推定と併せて、いくつかの用途に十分な３Ｄモデルを生成することができる。いくつかの用途とは、ウォークスルーの合成、映画用の立体コンテンツの生成、ならびに物体検出および認識用の３Ｄコンテキスト等である。こうした粗いモデリングに用いられる方法は、いくつかの幾何学的特徴および画像特徴を用いる。
【０００８】
いくつかの画像特徴、ならびに共平面性および共線性に対する弱い推定と併せて、１つの方法は、単一画像から奥行きを推定する。別の方法は、直方体を用いて部屋の幾何学的形状を概算し、様々な仮説をサンプリングし、いくつかの画像特徴および幾何学的特徴に基づいて、最も良好な仮説を選択する。屋内シーン内のクラッターは、直方体としてモデリングされ、３Ｄで再構成される。
【０００９】
ＳＶＲは、不良設定問題であるので、いくつかの解法が導かれる。いくつかの解法とは、方位マップの計算、人間の活動からの幾何学的形状推測、境界情報、テンプレート３Ｄ形状、さらには物理学主導の安定性制約および機械的制約の明白な使用等である。
【００１０】
より大きな解空間からレイアウトを正確に推測する最適化戦略を用いることによって、性能を大幅に改善することができる。航空写真から建物をモデリングするのにマンハッタン推定に基づく制約が用いられてきた。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明の実施の形態は、単一の２Ｄ画像から抽出された２Ｄラインから３Ｄワールド座標系内の３Ｄラインを再構成する方法を提供する。これらの３Ｄラインをシーン再構成に用いることができる。本方法は、消失点、直交構造、およびライン間の全ての妥当な連結性制約を検討する最適化手順を用いた、２Ｄ画像から抽出されたラインの３Ｄ再構成に基づく。
【００１２】
画像内の結合点において実質的に交差するラインが特定される。しかしながら、比較的少ない数の結合点のみが、３Ｄシーン内の実際の交差に対応する。本方法は、線形計画法（ＬＰ）を用いて、ラインを明確に再構成するのに十分な最小数の最も違反されていない連結性制約を特定する。
【００１３】
厳密に拘束する推定を用いた良好に機能する合成（グラフィック）線画に主に焦点を当てた既知のＬＰによる解決法と対照的に、本方法は、実世界の画像からシーンを再構成することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施の形態による、単一の２Ｄ画像内の２Ｄラインから３Ｄワールド座標系内の３Ｄラインを再構成する方法のブロック図である。
【図２Ａ】切頂四面体の合成線画である。
【図２Ｂ】切頂四面体の合成線画である。
【図２Ｃ】切頂四面体の合成線画である。
【図３】本発明の実施の形態による、ラインを含む屋外シーンの２Ｄ画像である。
【図４】本発明の実施の形態による、ライン、交差および制約の概略図である。
【図５】本発明の実施の形態による制約グラフである。
【図６】本発明の実施の形態による、画像平面内の交差するラインの概略図である。
【図７】本発明の実施の形態による、結合点の概略図である。
【発明を実施するための形態】
【００１５】
本発明の実施の形態は、単一画像内の２Ｄラインから３Ｄワールド座標系内の３Ｄラインを再構成する方法を提供する。再構成されたラインは、次に、２Ｄ画像から３次元（３Ｄ）シーンを再構成するのに用いることができる。
【００１６】
図１は、ライン抽出方法を示している。カメラを較正し、２Ｄ画像１０１の向きを推定した後、ラインが検出され、消失点が推定され、ラインがクラスター化される（１１０）。ラインクラスター１１５から、共線性制約および直交性制約を用いて制約グラフ１２５を生成する（１２０）。グラフから、制約グラフ内の頂点について、結合点１３５に基づくペナルティ項を求める（１３０）。
【００１７】
線形計画法（ＬＰ）１４０および最小全域木１５０を用いて、３Ｄワールド座標系内の３Ｄラインを再構成する（１６０）。次に、３Ｄラインを用いてシーンを再構成する（１７０）ことができる。
【００１８】
ここで、これらのステップをより詳細に説明する。ステップは、当該技術分野において既知のメモリおよび入／出力インターフェースに接続されたプロセッサにおいて実行することができる。
【００１９】
カメラアラインメント
本発明の方法は、全ての３Ｄラインが３つの直交軸のうちの１つに沿ってアラインされる３Ｄワールド（マンハッタン）座標系を用いる。これを達成するために、ワールドに対するカメラの向きを求め、必要な回転を行う。
【００２０】
３つの消失点ｖｐｘ、ｖｐｙ、およびｖｐｚを求める。これらの消失点のうちの２つを用いて、２Ｄカメラ座標系と３Ｄワールド座標系との間の回転Ｒを求めることができる。この回転を用いて、再構成するラインが、実世界の座標系とアラインされるように、カメラの光線を向ける。
【００２１】
カメラ行列Ｋを用いて較正されるカメラの場合、画像平面内の全てのピクセルｐ（ｘ，ｙ）が、単位ベクトルｄｐ＝ＲＫ−１（ｘ  ｙ  １）Ｔによって与えられるワールド座標系内の３Ｄ投影射線に対応する。ｄｘｐ、ｄｙｐ、およびｄｚｐは、方向ベクトルｄｐのｘ成分、ｙ成分、およびｚ成分を表す。
【００２２】
ライン抽出
線画のためのＳＶＲにおいて、結合点およびラインラベルを用いて、３Ｄ物体の構造を理解することができる。結合点は、２つ以上のラインが交差する点である。２Ｄ画像座標系内のラインの角度および向きに基づいて、結合点をＬ、Ｔ、Ｙ、またはＷとしてそれらに分類することができる。
【００２３】
図２Ａ、図２Ｂ、および図２Ｃは、切頂四面体の線画である。頂点Ａ、Ｂ、およびＣは、Ｗ結合点に対応し、頂点Ｄ、Ｅ、およびＦは、Ｙ結合点に対応する。合成線画において、結合点を検出するのは簡単である。結合点が検出された後、入射ラインが、凸（＋）、凹（−）、および遮蔽ライン（←→）を表すように、ラベリングされる。遮蔽ラベルの方向は、遮蔽面を示す。
【００２４】
カメラ較正を用いた、画像内の全てのピクセルへの投影射線が知られている。３Ｄ空間における線図からの全ての制約は、一次不等式である。例えば、４つ組（Ａ，Ｂ，Ｅ，Ｄ）は、単一面上に位置する。ラインラベリングは、ＤがＡよりもカメラの近くにあることを矯正する。そのような制約は、一次不等式の形で書くことができる。線形計画法が許容解を有する場合、線画は、物理的に実現可能である。これらの連立一次方程式の階数を研究することによって、線画が複数の３Ｄ解釈を有するとき、またはそうでないときを理解することができる。
【００２５】
投影射線に沿って３Ｄ点を抽出するように、連立一次不等式を生成する。本発明の解法は、従来の解法と異なる。なぜなら、実世界画像は、完全に異なる１組の難題を課し、これらは、幾何学的構造および組み合わされた構造のみを用いてモデリングすることが困難であるためである。
【００２６】
図３は、建物およびラインを有する３Ｄシーンの画像を示している。いずれの３Ｄ点がこの実世界画像内の平面に位置し、いずれの点が位置しないかを知ることは、容易でない。欠落したラインおよびスプリアスラインに起因して、非常に高い信頼度で結合点を検出することができない。
【００２７】
本発明では、検出した結合点からの平面性制約も、困難な不等式も有しない。さらに、実際のシーンは、多くの誤った交点を有し、これらによって、常に非許容解が導かれる。これらの実世界の難題に対処するために、本発明では、見掛けの結合点から絶対制約を一切導出しない。代わりに、結合点に関する証拠を用いて、ＬＰにおける一貫した３Ｄ構造を得るためのペナルティ項を通知する。
【００２８】
制約グラフ
図３におけるような実世界画像は、ライン検出にいくつかの難題を課す。結果として、ライン検出器は、一般に、欠落したライン、スプリアスライン、および途切れたラインをもたらす。本発明では、ライン間の最短距離がしきい値未満であるとき、２つのライン間の連結性制約を考察する。本発明は、２つのタイプの連結性を考察する。２つの直交ラインは、交点において交差することができる。２つの共線ラインは、入射点において合わさるように延長することができる。
【００２９】
交差および入射は、２Ｄ画像内の２Ｄラインから３Ｄワールド座標系内の３Ｄラインを再構成するための結合制約を与える。また、入射関係は、ワールド座標系内で２つの異なる物体から到来する２つの共線ラインを連結する。そのような関係を用いて、連結グラフを構成することができる。
【００３０】
しかしながら、実際の画像では、偶然の共線性が生じる可能性がある。しかし、これも、許容可能である。本発明のＬＰ定式化は、結合点に基づくペナルティ項を用いることによって、真でない場合がある制約に対処するように設計される。ＬＰにおいて用いる制約は、点および線にのみ依拠する方向制約である。この制約は、点が交差であるかまたは入射であるかに無関係である。
【００３１】
図４に示すように、制約を表すのに統一された表現を用いる。ｎは、画像内のライン数を表し、ｌｉは、インデックスｉを有するラインを表すものとする。ｍは、交差および入射の総数を表すものとする。制約グラフＧ＝（Ｖ，Ｅ）を用いて、交差および入射の関係を表すことができる。ここで、頂点Ｖ＝｛１，２，・・・，ｎ｝は、ラインを表し、エッジ（ｉ，ｊ）∈Ｅは、ラインｌｉとラインｌｊとの間の交差または入射を表す。４つのラインｌ１、ｌ２、ｌ３、およびｌ４を示す。これらのラインは、３つの交差Ｉ１２、Ｉ１３、およびＩ１４をもたらす。ラインｌ１およびｌ４は、共線であり、これらのラインは、入射点Ｉ１４をもたらす。グラフの頂点およびエッジは、それぞれＶ＝（１，２，３，４）およびＥ＝｛（１，２），（１，３），（１，４），（２，３）｝によって与えられる。
【００３２】
図５に示すように、画像内の全てのラインは、頂点（ｘ１，ｘ２，ｘ３，ｘ４）であり、全ての交差および入射は、制約グラフにおけるエッジ（ｅ１２，ｅ１３，ｅ１４，ｅ２３）である。
【００３３】
線形計画法
図６に示すように、ピクセルに対応する３Ｄ点は、その投影射線上にあり、点は、λｄｐによって表すことができる。ここで、λは、カメラ中心からの３Ｄ点の距離に等しい未知のスケールパラメータである。一般に、２Ｄ画像ラインから３Ｄラインを再構成するには、３Ｄ空間内で双方の端点を再構成する２つのパラメーターを必要とする。しかしながら、マンハッタンワールド推定の下では、一方の点を再構成すれば、他方の点を復元するのに十分である。本発明の定式化では、単一のパラメーターλｉを用いて、ラインの端点のうちの一方のスケールを表す。
【００３４】
図６では、点Ｉｉｊにおいて交差する２つのラインｌｉおよびｌｊを示している。制約グラフＧ＝（Ｖ，Ｅ）に関して、全ての頂点ｉ∈Ｖについて、１つの未知のλｉを有し、全てのエッジ（ｉ，ｊ）∈Ｅについて、１つの未知のλｉｊを有する。全ての交差または入射Ｉｉｊが、画像ラインｌｉおよびｌｊに対応する双方の３Ｄライン上に独立して位置する。このため、ベクトルλｉｄｉ−λｉｊｄｉｊは、ラインｌｉに対応する３Ｄラインの方向に沿ってアラインされる。同様に、ベクトルλｊｄｊ−λｉｊｄｉｊは、ラインｌｊに対応する３Ｄラインの方向に沿ってアラインされる。
【００３５】
この特性は、ラインを再構成する際の制約として用いられる。本発明の目標は、以下の最適化問題において、そのような制約の最大数を満たすような未知のパラメーターを求めることである。
【００３６】
【数１】
2014229305.tif 000003
【００３７】
ここで、ａ、Ａｉ∈｛ｘ，ｙ，ｚ｝およびＡｉは、ｌｉの向きに対応する。単一の２Ｄ画像から、再構成は、未知のグローバルスケールまでのみ可能である。制約λｉ，λｉｊ≧１は、ラインがカメラから、またカメラの正面において、少なくとも単位距離にあることを確保する。全てのエッジ（ｉ，ｊ）について、２つのスラック変数ｓｉｊ１およびｓｉｊ２を有する。
【００３８】
元のＬ０ノルム最大化問題を解く代わりに、ＬＰを用いて、以下の最小化を解く。
【００３９】
【数２】
2014229305.tif 000004
【００４０】
目的関数（３）における重みパラメーターｗｉｊは、以下に示すように結合点特徴から得られる。ＬＰは、全てのスラック変数ｓｉｊｋについての解を与える。全てのエッジ（ｉ，ｊ）について、スラック変数ｓｉｊ１およびｓｉｊ２は、シーンの最低コストの大域一貫３Ｄ解釈を得るのに必要なラインｉとラインｊ間の最小奥行き分離を与える。（ｓｉｊ１＋ｓｉｊ２）をエッジコストとして用いて、エッジ集合ＥＳによって表される最小全域木を求める。スケール係数λｉおよびλｉｊは、ツリー構造グラフに対応する連立一次方程式から直接求めることができる。
【００４１】
結合点コスト
マンハッタンワールド推定の下で、投票を用いてＬＰにおけるペナルティ項として結合点特徴を求める。式（３）における重みパラメーターｗｉｊは、エッジ（ｉ，ｊ）に対応する制約が違反されたときに課すペナルティに対応する。これらの重みは、結合点特徴の関数としてモデリングされる。関数が特定の結合点について高い値を有する場合、この関数が異なる結合点について高いスコアを有し得る可能性は、極めて低い。
【００４２】
図７は、本発明の結合点の基礎をなす着想および結合点を求める方法を示している。画像内の全てのピクセルについて、消失点ｖｐｘ、ｖｐｙ、およびｖｐｚに関して、６つの可能な向きの領域が存在する。これらの向きは、集合
【数３】
2014229305.tif 000005
によって表される。
【００４３】
全ての部分集合Ａ⊆Ｓは、結合点を表し、全ての可能な部分集合Ａおよびピクセルｐについて、関数Ｆ（Ａ，ｐ）を求めることができる。関数の値は、ピクセルｐにおいて結合点Ａの存在を示すスコアを与える。例えば、図７のピクセルｐにおけるＹ結合点は、集合
【数４】
2014229305.tif 000006
に対応する。ピクセルｑにおいて、Ｔ結合点が存在する。
【００４４】
以下は、マンハッタンシーンにおける結合点の場合にあてはまる。Ｌ結合点およびＸ結合点は、平面上で生じる。Ｔ結合点は、平面および遮蔽境界の双方で生じる。Ｙ結合点およびＷ結合点は、凸エッジおよび凹エッジ上で共通である。
【００４５】
Ｊ（ｐ）がピクセルｐにおける結合点のタイプを表すものとする。ｐは、制約グラフ内のエッジ（ｉ，ｐ）にマッピングされる交点を表す。ＬＰにおいて、ｗｉｊの重みを、以下のように設定する。
【００４６】
【数５】
2014229305.tif 000007
【００４７】
ここで、ＣｈおよびＣｍは、結合点ごとの視覚的証拠の品質に従ってスケーリングされる定数であり、それによって、ラインを延長することによって得られる結合点は、より弱いペナルティを有する。
【００４８】
Ｔは、場合によって、欠落したラインに起因してＬとして検出される可能性があるので、Ｌ結合点を何ら優先しない。
【００４９】
応用形態
１つの応用形態において、再構成は、シーンの複数の画像に適用され、大きなシーンが再構成される。別の応用形態は、立体コンテンツを生成するのに３Ｄラインを用いる。カメラを家庭用品に搭載して屋内シーンを再構成し、暖房、換気および空調ユニットにおける空気の流れを最適に制御することができる。カメラを車両に搭載して、障害物または車両のロケーションを検出することもできる。
【図１】
2014229305.tif 000008
【図２Ａ】
2014229305.tif 000009
【図２Ｂ】
2014229305.tif 000010
【図２Ｃ】
2014229305.tif 000011
【図３】
2014229305.tif 000012
【図４】
2014229305.tif 000013
【図５】
2014229305.tif 000014
【図６】
2014229305.tif 000015
【図７】
2014229305.tif 000016
【外国語明細書】
2014229305.tif 000017
2014229305.tif 000018
2014229305.tif 000019
2014229305.tif 000020
2014229305.tif 000021
2014229305.tif 000022
2014229305.tif 000023
2014229305.tif 000024
2014229305.tif 000025
2014229305.tif 000026
2014229305.tif 000027
2014229305.tif 000028
2014229305.tif 000029
2014229305.tif 000030
2014229305.tif 000031
2014229305.tif 000032
2014229305.tif 000033
2014229305.tif 000034
2014229305.tif 000035
2014229305.tif 000036
2014229305.tif 000037
2014229305.tif 000038
2014229305.tif 000039
2014229305.tif 000040