(57)【要約】  一群の２次元画像から３次元シーンを再構成するための方法、システム、及びコンピューター可読媒体が提供される。コンピューター化された再構成システムが、一群の２次元画像に対しコンピュータービジョンアルゴリズムを実行し、２次元画像内に示された環境の視覚特性をモデリングするのに用いられる候補平面を特定する。コンピュータービジョンアルゴリズムは、２次元画像の特徴間の関係及び類似度を表すエネルギー関数を最小化して、２次元画像のピクセルを３次元シーンの平面に割り当てることができる。３次元シーンはナビゲート可能であり、複数の２次元画像間の視点遷移を示す。
2012530323.tif 000002
【特許請求の範囲】
【請求項１】
電子データベース内に格納された一群の画像からナビゲート可能な３次元シーンをレンダリングするのに用いられる平面を選択する、コンピューターにより実施される方法であって、
前記電子データベースから前記一群の画像を受信するステップ（１８２０）と、
前記一群の画像からシーン情報を抽出するステップ（１８３０）であって、該シーン情報は、カメラキャリブレーション、３次元点群、３次元線分、並びに点及び線のマルチビュー一致のためのデータを含む、抽出するステップと、
エッジ検出及び２次元線分抽出を用いて、前記一群の画像における各画像内の消失方向を検出するステップ（１８４０）と、
前記消失方向及び前記シーン情報に基づいて前記ナビゲート可能な３次元シーン内の各平面を特定するステップ（１８５０）と、
マルコフ確率場分布を生成するステップ（１８６０）であって、該マルコフ確率場分布に適用された最小化関数に基づいて各平面にピクセルを割り当て、該ピクセルを前記ナビゲート可能な３次元シーン内の平面に割り当てる大域コストを最適にする、生成するステップと
を含む、コンピューターにより実施される方法。
【請求項２】
平均シフトクラスタリングを用いて、前記一群の画像によって捕捉された様々なビューの前記消失方向を検出する、請求項１に記載のコンピューターにより実施される方法。
【請求項３】
前記一群の画像から抽出された平行線を用いて前記消失方向を検出する、請求項１に記載のコンピューターにより実施される方法。
【請求項４】
前記一群の画像から抽出された消失方向の各可能な対の外積に基づいて平面の向きのセットを求めるステップを更に含む、請求項１に記載のコンピューターにより実施される方法。
【請求項５】
平面−ピクセル割当ての前記大域コストの一部分は、マルコフ確率場分布グラフに適用された前記最小化関数に含まれる平滑項によって表され、該平滑項は、遮蔽平面の法線ベクトルに直交する前記消失方向に整合する２次元線における不連続性に対応するピクセルにおける平面間の遷移を選好するように計算される、請求項１に記載のコンピューターにより実施される方法。
【請求項６】
マルコフ確率場分布グラフにおける平滑項を、平面への１つの画像内のピクセルの割当てに対し、近傍画像内の対応するピクセルが同じ平面を選択しなかった場合にペナルティを課すように計算するステップを更に含む、請求項５に記載のコンピューターにより実施される方法。
【請求項７】
前記マルコフ確率場分布グラフにおける平滑項を、前記画像内の２次元線又は２次元線分に対応する遷移を選好するように計算するステップを更に含む、請求項５に記載のコンピューターにより実施される方法。
【請求項８】
前記一群の画像における各画像内のピクセルは、反復的に投票して、前記大域コストを最小にする前記平面ラベル割当てを求める、請求項５に記載のコンピューターにより実施される方法。
【請求項９】
前記最小化関数は、前記平滑項によって制約される前記マルコフ確率場分布グラフにおけるカットコストを選択する、請求項５に記載のコンピューターにより実施される方法。
【請求項１０】
電子データベース内に格納された一群の２次元画像からナビゲート可能な３次元シーンをレンダリングするときに、２次元画像から３次元平面にピクセルを割り当てる方法を実行するためのコンピューター実行可能命令を格納する１つ又は複数のコンピューター可読媒体であって、前記方法は、
前記一群の２次元画像を受信するステップ（１９２０）と、
前記２次元画像から抽出されたシーン情報から３次元平面のセットを生成するステップ（１９３０）であって、前記シーン情報は、消失方向、線、及び３次元点を含む、生成するステップと、
前記シーン情報及び前記生成された３次元平面を用いてマルコフ確率場を生成するステップ（１９４０）と、
前記マルコフ確率場によって表されるエネルギー関数を最小にするように、前記生成された平面にピクセルを割り当てるステップ（１９５０）であって、前記マルコフ確率場は前記２次元画像の深度マップを提供し、該深度マップを用いてナビゲート可能な３次元シーンがレンダリングされる、割り当てるステップと
を含む、コンピューター可読媒体。
【請求項１１】
遮蔽エッジ及び折れエッジを特定することによって前記深度マップ及び境界を補正するステップと、
前記深度マップ及び前記２次元画像の対応する深度マップへの該２次元画像の投影を用いて３次元シーンをレンダリングするステップであって、複数の２次元画像間のクロスフェージングによって、前記一群の前記２次元画像のそれぞれについて平滑なビュー補間が可能になる、レンダリングするステップと
を更に含む、請求項１０に記載のコンピューター可読媒体。
【請求項１２】
前記マルコフ確率場によって表されるエネルギー関数を最小にするように、前記生成された平面にピクセルを割り当てるステップは、
マルチビュー光学的整合性、スパースな３次元点及び３次元線の地理的近接度、並びに前記３次元点及び前記３次元線の光線視認性から導出された自由空間違反を考慮するステップと、
ピクセルを割り当てる条件を設定するデータ項及び平面間の遷移条件を設定する平滑項に基づいて前記マルコフ確率場を最適化するステップと
を更に含む、請求項１０に記載のコンピューター可読媒体。
【請求項１３】
前記データ項は、平面への１つの画像内のピクセルの割当てに対し、近傍画像内の対応するピクセルが、各２次元画像上を反復的に通過する間に同じ平面を選択しなかった場合にペナルティを課す、請求項１２に記載のコンピューター可読媒体。
【請求項１４】
前記平滑項は、以下の平滑項、すなわち、
遮蔽平面の法線ベクトルに直交する消失方向に整合する２次元線における不連続性に対応する遷移を選好する平滑項、
前記画像内の２次元線に対応する遷移を選好する平滑項、又は
平面への１つの画像内のピクセルの割当てに対し、近傍画像内の対応するピクセルが、前記一群の２次元画像における全ての画像上を同時に通過する間に同じ平面を選択しなかった場合にペナルティを課す平滑項、
のうちの少なくとも１つを含む、請求項１２に記載のコンピューター可読媒体。
【請求項１５】
一群の２次元画像からナビゲート可能な３次元シーンを生成するように構成されたメモリ及びプロセッサを有するコンピューターシステムであって、
前記２次元画像から抽出された前記シーン情報から３次元平面のセットを生成するように構成された平面生成器（１１１）と、
前記２次元画像のそれぞれについて深度マップを推定するように、かつ前記生成された平面に前記２次元画像からのピクセルを割り当てる大域境界制約及び局所境界制約を規定するように構成された最適化エンジン（１１２）と、
前記生成された平面、補間されたビュー、及び前記一群の画像の各々からのクロスフェードビューから、前記３次元シーンの前記深度マップに基づいて複数の平面多角形を生成する再構成エンジン（１１３）と、
を備える、コンピューターシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元シーンの区分的平面再構成に関する。
【背景技術】
【０００２】
[0001]従来から、コンピューターのレンダリングエンジンは、整列されていない一群の２次元画像からカメラキャリブレーション（較正）及びシーンのスパース構造を回復する、自動特徴マッチング又は自動特徴抽出を提供するように構成することができる。従来のレンダリングエンジンは、カメラキャリブレーション、スパースシーン構造、及び２次元画像を用いて、３次元空間における各ピクセルのロケーションをトライアンギュレート（triangulate：三角測量）することができる。ピクセルはトライアンギュレートされたロケーションにレンダリングされ、３次元シーンを形成する。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
[0002]しかしながら、生成される３次元シーンの品質及び細部は多くの場合に種々の難点を被る。例えば、従来のレンダリングエンジンは、２次元画像において捕捉されたテクスチャのない表面又は非ランバート平面を穴としてレンダリングする場合がある。これらの穴は、近傍ピクセルの深度を補間することによってカバーされる。しかし、従来のレンダリングエンジンの補間は、３次元シーンにおいて、直線を有する平坦な表面をでこぼこの表面として誤って再現する場合がある。従来のレンダリングエンジンはまた、非ランバート表面の信頼性のないマッチング、遮蔽等に起因して、３次元シーン内に誤ってジャギーをもたらす場合もある。
【０００４】
[0003]従来のレンダリングエンジンの品質及び細部は、建築のシーン、都会のシーン、又は多数の平面を有する人工物を有するシーンの３次元シーンを生成するときに大幅に劣化する。さらに、スパースな一群の２次元画像からの３次元シーンの再構成は、写実的な形でナビゲート可能でない。なぜなら、従来のレンダリングエンジンによって実行される従来のコンピュータービジョンアルゴリズムの前提は、人工表面を含むシーンの場合に上手く機能するように設計されていないためである。
【課題を解決するための手段】
【０００５】
[0004]当該技術分野におけるこれらの問題及び他の問題を克服する本発明の実施の形態は、１つには、一群の２次元画像からナビゲート可能で写実的なシーンを生成するための、コンピューター化された再構成システム、コンピューター可読媒体、及びコンピューターにより実施される方法に関する。コンピューター化された再構成システムは、一群の２次元画像から捕捉されたシーンの密な区分的平面再構成を回復する。
【０００６】
[0005]コンピューター化された再構成システムは、３次元平面候補の離散したセットを特定する。コンピューター化された再構成システムは、シーンのスパースな点群（point cloud）及び一群の２次元画像において捕捉された複数のビューから再構成されたスパースな３次元線分に基づいて３次元平面候補の離散したセットを生成する。そして、グラフカットに基づくエネルギー最小化技法を用いたマルチラベルマルコフ確率場（ＭＲＦ）最適化問題を解くことによって、各画像について区分的平面深度マップが回復される。コンピューター化された再構成システムは、元の２次元画像を回復された平面深度マップに投影して、３次元シーンのレンダリングを生成する。
【０００７】
[0006]本概要は、詳細な説明において以下で更に説明される概念の抜粋を簡略化された形で紹介するために提供される。本概要は、特許請求される主題の主要な特徴又は本質的な特徴を特定するように意図されるものでもなければ、特許請求される主題の範囲を画定するのに役立つものとして分離して用いるように意図されるものでもない。
【図面の簡単な説明】
【０００８】
【図１】[0007]本発明の実施形態による一例示の計算システムを示すネットワーク図である。
【図２Ａ】[0008]本発明の実施形態による例示的な２次元画像を示すイメージ図であり、それぞれ、本発明の実施形態によるカメラによって捕捉された２次元画像を示す図である。
【図２Ｂ】本発明の実施形態による例示的な２次元画像を示すイメージ図であり、それぞれ、本発明の実施形態によるカメラによって捕捉された２次元画像を示す図である。
【図３Ａ】[0009]本発明の実施形態による例示的な３次元平面を示す平面図であり、本発明の実施形態による、動き特徴抽出及びカメラキャリブレーション決定からの構造を示す図である。本発明の実施形態による、コンピューター化された再構成サーバーによって生成された様々な３次元視点のうちの１つの候補平面を示す図である。
【図３Ｂ】本発明の実施形態による、コンピューター化された再構成サーバーによって生成された３次元線を示す図であ
【図３Ｃ】本発明の実施形態による、コンピューター化された再構成サーバーによって生成された様々な３次元視点のうちの１つの候補平面を示す図である。
【図３Ｄ】本発明の実施形態による、コンピューター化された再構成サーバーによって生成された様々な３次元視点のうちの１つの候補平面を示す図である。
【図３Ｅ】本発明の実施形態による、コンピューター化された再構成サーバーによって生成された様々な３次元視点のうちの１つの候補平面を示す図である。
【図４Ａ】[0010]本発明の実施形態による計算システムによって生成された一例示のシーンを示す３次元シーン図であり、本発明の実施形態による、コンピューター化された再構成サーバーによって生成された深度マップを示す図である。
【図４Ｂ】本発明の実施形態による、コンピューター化された再構成サーバーによって生成されたプロキシメッシュを示す図である。
【図４Ｃ】本発明の実施形態による、コンピューター化された再構成サーバーによって生成された、テクスチャーを付けられたプロキシメッシュを示す図である。
【図５Ａ】[0011]本発明の実施形態による、２次元画像内の消失方向（vanishing direction）の検出を示す消失方向図であり、本発明の実施形態による、コンピューター化された再構成システムによって消失方向を抽出するように処理される一例示の２次元画像を示す図である。
【図５Ｂ】本発明の実施形態による、２次元画像から抽出された消失方向の各クラスターの向きを示す図であ
【図５Ｃ】本発明の実施形態による、コンピューター化されたサーバーによってレンダリングされた３次元シーンの一例示の再構成を示す図である。
【図６Ａ】[0012]本発明の実施形態による面法線の確率分布（probable distribution）を示す法線の向きの図であり、本発明の実施形態による、３次元点の共分散の基準を示す図である。
【図６Ｂ】本発明の実施形態による、３次元点を通る平面の法線の分布を示す図である。
【図７Ａ】[0013]本発明の実施形態による平面又は３次元線の向きの確率分布を示す分布ヒストグラムであり、本発明の実施形態による、３次元点からの投票に基づく法線の分布を表すヒストグラムである。
【図７Ｂ】本発明の実施形態による、３次元線からの投票に基づく法線の分布を表すヒストグラムである。
【図８】[0014]本発明の実施形態による、２次元画像から抽出されたシーン情報を示す視認性の図である。
【図９】[0015]本発明の実施形態による、マルコフ確率場表現及びグラフカット最小化を用いた平面を表すラベルに対するピクセルの割当てを示すグラフ図である。
【図１０Ａ】[0016]本発明の実施形態による、３次元シーンを生成するのに用いられる２次元画像間の関係を示す光学的整合性（photo-consistency）の図であり、本発明の実施形態による、一例示の基準画像を示す図である。
【図１０Ｂ】本発明の実施形態による、コンピューター化された再構成システムによって用いられる一例示の近傍ワープ画像を示す図である。
【図１０Ｃ】本発明の実施形態による、コンピューター化された再構成サーバーによって求められる基準画像とワープ画像との間の光学的整合性の基準を示す図である。
【図１１】[0017]本発明の実施形態による、３次元シーン内の平面における平面対と平面の遮蔽境界との交差部に対応する折れエッジ（crease edge）を示す境界図であり、図１１Ａは、本発明の実施形態による折れエッジを示す図であり、図１１Ｂは、本発明の実施形態による遮蔽境界を示す図である。
【図１２Ａ】[0018]本発明の実施形態による、３次元の劇場のシーンにおける視点間のナビゲーションを示す遷移図である。
【図１２Ｂ】本発明の実施形態による、３次元の劇場のシーンにおける視点間のナビゲーションを示す遷移図である。
【図１３Ａ】[0019]本発明の実施形態による、３次元の小屋のシーンにおける視点間のナビゲーションを示す遷移図である。
【図１３Ｂ】本発明の実施形態による、３次元の小屋のシーンにおける視点間のナビゲーションを示す遷移図である。
【図１４Ａ】[0020]本発明の実施形態による、３次元アーチシーン内の視点間ナビゲーションを示す遷移図である。
【図１４Ｂ】本発明の実施形態による、３次元アーチシーン内の視点間ナビゲーションを示す遷移図である。
【図１５Ａ】[0021]本発明の実施形態による、３次元の城のシーンにおける視点間のナビゲーションを示す遷移図である。
【図１５Ｂ】本発明の実施形態による、３次元の城のシーンにおける視点間のナビゲーションを示す遷移図である。
【図１６Ａ】[0022]本発明の実施形態による、３次元の部屋のシーンにおける視点間のナビゲーションを示す遷移図である。
【図１６Ｂ】本発明の実施形態による、３次元の部屋のシーンにおける視点間のナビゲーションを示す遷移図である。
【図１７Ａ】[0023]本発明の実施形態による、３次元のロビーのシーンにおける視点間のナビゲーションを示す遷移図である。
【図１７Ｂ】本発明の実施形態による、３次元のロビーのシーンにおける視点間のナビゲーションを示す遷移図である。
【図１７Ｃ】本発明の実施形態による、３次元のロビーのシーンにおける視点間のナビゲーションを示す遷移図である。
【図１７Ｄ】本発明の実施形態による、３次元のロビーのシーンにおける視点間のナビゲーションを示す遷移図である。
【図１７Ｅ】本発明の実施形態による、３次元のロビーのシーンにおける視点間のナビゲーションを示す遷移図である。
【図１８】[0024]本発明の実施形態による、電子データベース内に格納された一群の画像からナビゲート可能な３次元シーンをレンダリングするのに用いられる平面を選択する方法を示す論理図である。
【図１９】[0025]電子データベース内に格納された一群の２次元画像からナビゲート可能な３次元シーンをレンダリングするときに、ピクセルを２次元画像から３次元平面に割り当てる方法を示す論理図である。
【発明を実施するための形態】
【０００９】
[0026]本発明は、特許を受けるための主題を、法定の要件を満たすように具体的に説明する。しかしながら、この説明自体が本発明の範囲を限定するように意図されるものではない。そうではなく、本発明者らは、特許請求される主題は、他の特許又は未来の技術と併せて、本文書において説明されているステップと異なるステップ又は類似したステップの組み合わせを含むように、他の形で実施することもできることを熟慮している。さらに、用語「ステップ」及び「ブロック」は、本明細書において、用いられる方法の様々な要素を意味するのに用いることができるが、これらの用語は、個々のステップの順序が明示的に説明されない限り、及びその場合を除いて、本明細書において開示される種々のステップ間のいかなる特定の順序も意味するものとして解釈されるべきではない。また、参照により本明細書にその全体が援用される添付の図面を参照して、実施形態を以下で詳細に説明する。
【００１０】
[0027]本発明の実施形態は、一群の２次元画像からナビゲート可能な３次元シーンを生成するコンピューター化された再構成システムを提供する。２次元画像は、コンピューター化された再構成システムによって、マッチする特徴、カメラキャリブレーション、及び地理的情報又は空間情報を抽出するように処理される。そして、コンピューター化された再構成システムは、２次元画像から消失方向を自動的に検出する。コンピューター化された再構成システムによって、マッチする特徴、カメラキャリブレーション、空間情報、及び消失方向を用いて、３次元シーンの平面候補のセットを生成する。コンピューター化された再構成システムによって、平面候補のセットの確からしい向きが求められ、マルコフ確率場が生成される。そして、コンピューター化された再構成システムによって、マルコフ確率場に対応する最小化関数を用いて、２次元画像からのピクセルを候補平面のセットに割り当てることによって２次元画像から３次元シーンを生成する。
【００１１】
[0028]当業者であれば理解するように、コンピューター化された再構成システムは、ハードウェア、ソフトウェア、又はハードウェア及びソフトウェアの組み合わせを含むことができる。ハードウェアは、プロセッサ及びメモリを含むことができ、該プロセッサ及びメモリは、該メモリ内に格納された命令を実行するように構成される。１つの実施形態では、メモリには、コンピューターにより実施される方法のコンピューター使用可能命令を有するコンピュータープログラム製品を格納するコンピューター可読媒体が含まれる。コンピューター可読媒体には、揮発性媒体及び不揮発性媒体の双方、取り外し可能媒体及び取り外し不可能媒体、並びにデータベース、スイッチ、及び種々の他のネットワークデバイスによって読み取り可能な媒体が含まれる。ネットワークスイッチ、ルーター、及び関連構成要素は、それらと通信する手段と同様に本質的に従来のものであり、限定ではないが例として、コンピューター可読媒体には、コンピューターストレージ媒体及び通信媒体が含まれる。コンピューターストレージ媒体又は機械可読媒体は、情報を格納するための任意の方法又は技術で実装された媒体を含む。格納される情報の例には、コンピューター使用可能命令、データ構造、プログラムモジュール、及び他のデータ表現が含まれる。コンピューターストレージ媒体には、限定ではないが、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、電気的に消去可能なプログラム可能読み出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュメモリ又は他のメモリ技術、コンパクトディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）、デジタル多用途ディスク（ＤＶＤ）、ホログラフィック媒体又は他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、及び他の磁気ストレージデバイスが含まれる。これらのメモリ技術は、データを瞬間的に、一時的に、又は永続的に格納することができる。
【００１２】
[0029]図１は、本発明の一実施形態による一例示の動作環境１００を示すネットワーク図である。図１に示す動作環境１００は単なる例示であり、範囲又は機能に関して一切制限を示唆するように意図されるものではない。本発明の実施形態は多数の他の構成を用いて動作可能である。図１を参照すると、動作環境１００は、ネットワーク１１３を通じて互いに通信する、コンピューター化された再構成サーバー１１０、２次元画像１２０、３次元シーン１３０、ラップトップ１４０、マルチメディア捕捉デバイス１５０及び１６０、ファイルサーバー１７０、パーソナルコンピューター１８０、人工衛星１９０、及並びに移動デバイス１９５を含む。
【００１３】
[0030]コンピューター化された再構成サーバー１１０は、ナビゲート可能な３次元シーン１３０を生成するように構成される。コンピューター化された再構成サーバー１１０は、平面生成器１１１、最適化エンジン１１２、再構成エンジン１１３、及びマルチメディアインデックス１１４を備える。コンピューター化された再構成システムは、計算デバイス（例えば、ラップトップ１４０、マルチメディア捕捉デバイス１５０及び１６０、ファイルサーバー１７０、パーソナルコンピューター１８０、人工衛星１９０、並びに移動デバイス１９５）から、３次元シーン１３０を生成することの要求を受信することができる。要求は、コンピューター化された再構成サーバー１１０に送信される一群の２次元画像１２０を含むことができる。コンピューター化された再構成サーバーはマルチメディアインデックス１１４内に一群の２次元画像１２０を格納する。
【００１４】
[0031]平面生成器１１１は、カメラからの候補平面及び２次元画像１２０に含まれるシーン情報を特定するように構成される。そして、平面生成器１１１は、各候補平面について確からしい向きを求め、類似した確からしい向きを共有する候補平面をクラスタリングする。いくつかの実施形態では、平面生成器１１１は、３次元シーン１３０の境界を表す基面及び背面を作成する。
【００１５】
[0032]平面生成器１１１は、２次元画像１２０から大域シーン情報を抽出する。大域シーン情報は、２次元画像１２０内で捕捉されたシーンの複数のビューからの、３次元点及び３次元座標、消失方向、３次元線分、並びに３次元点、３次元線、及び消失方向の一致の基準を含むことができる。１つの実施形態では、平面生成器１１１は、改良型のランダムサンプルコンセンサス（ＲＡＮＳＡＣ）アルゴリズムを実行し、大域シーン情報を用いて候補平面を検出する。
【００１６】
[0033]平面生成器１１１は２次元画像１２０からの３次元点及び３次元座標、並びにシーンを捕捉したカメラによって提供される任意の関連メタデータを抽出することができる。カメラによって提供されるメタデータには、ロケーション情報、距離情報、及び任意の他のカメラキャリブレーション情報を含めることができる。このため、平面生成器１１１は、メタデータ及び２次元画像１２０を用いて、２次元画像内の各ピクセルについて空間３次元点を生成することができる。いくつかの実施形態では、平面生成器１１１は、ピクセルを類似度に基づいてスーパーピクセルにグループ化する。
【００１７】
[0034]２次元画像１２０によって捕捉されるシーンにおける消失方向は平面生成器１１１によって検出される。１つの実施形態では、平面生成器１１１によってエッジ検出アルゴリズムが実行され、２次元画像内の消失方向が検出される。エッジ検出アルゴリズムは２次元画像１２０内に含まれる２次元線分を提供する。２次元線分は連結され、一群の２次元画像における各画像のエッジマップが形成される。そして、平面生成器１１１によって、３次元における平行な線に対応する、各エッジマップ内の線又は線分が検出される。画像内の消失点は３次元シーンにおける消失方向に対応する。平面生成器１１１は、消失方向に対応するベクトルの単位球に対し平均シフトクラスタリングを実行する。多数の消失方向を有するクラスターが平面生成器１１１によって保持され、スパースなクラスターは破棄される。平面生成器１１１は、クラスター内に含まれるシーンの様々なビューからの各２次元線分を用いて、各クラスターについて代表的な消失方向を特定する。いくつかの実施形態では、平面生成器１１１は互いにほぼ直交する対について消失方向のセットを検査し、該セット内に直交する３つ組が既に存在しない限り、直交する３つ組を完成させる第３の消失方向を追加する。
【００１８】
[0035]平面生成器１１１によって３次元線分が構成される。平面生成器１１１は、エピポーラ拘束及び大域シーン情報を用いてマッチする線分を特定する。平面生成器１１１は、２次元画像によって捕捉されたシーンにおいて類似した消失方向を有しかつ近接したマッチする関心点を有する、２次元線分の対を検索する。２次元線の複数のマッチする対が互いにリンクされ、平面生成器１１１は、２次元画像によって捕捉されたシーンの複数のビューからの３次元線のコンセンサスを検証する。いくつかの実施形態では、検証に用いられるビューの数は少なくとも４つである。３次元線は、２次元セグメントの対をトライアンギュレートし、リンクされた２次元セグメント内で全体最小再投影誤差を有する対を見つけることによって計算される。そして、平面生成器１１１が間隔解析を介して３次元線分の端点を求める。いくつかの実施形態では、平面生成器１１１は、特定された消失方向によって制約されない２次元セグメントを探す。これらの追加の２次元セグメント（誤対応、異常値（outlier））は、それらの方向及び共分散に基づいてクラスタリングされる。
【００１９】
[0036]平面生成器１１１は、生成された３次元線及び特定された消失方向に基づいて、平面の向き及び各３次元点の確からしいロケーションを求める。平面生成器１１１により、消失方向の全ての対の外積の値を求めることによって、可能性の高い平面の向きのセット
【００２０】
【数１】
2012530323.tif 000003
【００２１】
が生成される。或る実施形態では、互いに５度以内の平面の向き
【００２２】
【数２】
2012530323.tif 000004
【００２３】
は複製として扱われる。平面生成器１１１は顕著性に基づいて可能性の高い平面の向きのセット
【００２４】
【数３】
2012530323.tif 000005
【００２５】
をソートする。各平面の向き
【００２６】
【数４】
2012530323.tif 000006
【００２７】
の顕著性は、消失方向の対応する対に関連付けられたクラスターのサイズをカウントすることによって測定される。
【００２８】
[0037]平面生成器１１１によって各３次元点の確からしいロケーションが求められる。１つの実施形態では、平面生成器１１１によって、各３次元点について３次元マハラノビス距離が計算され、３次元点が３次元線及び消失方向によって表される１つ又は複数の平面仮説に属するか否かが判断される。マハラノビス距離は３次元点の共分散（不確実性）及び平面仮説の対応する適合誤差を測定する。或る実施形態では、平面生成器１１１は、２次元画像１２０によって捕捉されたシーンの平均ビュー方向に沿った向きのベクトル
【００２９】
【数５】
2012530323.tif 000007
【００３０】
を計算することによって各３次元点Ｘｋについて概算不確実性を特定する。ベクトル
【００３１】
【数６】
2012530323.tif 000008
【００３２】
の大きさは２次元画像１２０内のピクセルの投影された不確実性に対応する。平面生成器１１１によって、ベクトル
【００３３】
【数７】
2012530323.tif 000009
【００３４】
の大きさを用いて平面仮説の不確実性の値を求めることができる。
【００３５】
[0038]平面生成器１１０によって、平面の向きのセット
【００３６】
【数８】
2012530323.tif 000010
【００３７】
にわたる離散尤度分布に基づいて、各３次元点Ｘｋについて面法線が求められる。３次元点Ｘｋを通る、向きを有する各平面は、平面生成器１１１によって、３次元点Ｘｋの周囲の近傍３次元点の数及び向きを有する平面の１つの次元に沿ったロバスト変動に基づいてスコアを与えられる。平面生成器１１１は、向きを有する平面の尤度分布の１つの次元に沿って独自のピークを有する、密な近傍を有する各３次元点に面法線を割り当てる。３次元点に割り当てられた面法線は、３次元平面に対する対応する３次元点の割当てを制限する。いくつかの実施形態では、平面生成器１１１は、３次元線の線方向を用いて、該３次元線が平面及び３次元線の割当ての間にいずれれの平面に投票することができるかを判定する。同様に、平面生成器１１１によって、３次元点の面法線を用いて、該３次元点が平面への３次元点の割当ての間にいずれの平面に投票することができるかを判定することができる。
【００３８】
[0039]平面生成器１１１によって、各３次元点及び３次元線を用いて、２次元画像１２０によって捕捉されたシーンの平面を求める。平面生成器１１１は２つのヒストグラム
【００３９】
【数９】
2012530323.tif 000011
【００４０】
を構築して、３次元点及び３次元線から受け取った各向き
【００４１】
【数１０】
2012530323.tif 000012
【００４２】
に対する投票を測定する。平面生成器１１１は、対応する２次元画像１２０を捕捉したカメラに関連付けられたロケーションが平面の正面に位置するときに各３次元点及び３次元線からの投票をカウントする。平面生成器１１１は平面の向き
【００４３】
【数１１】
2012530323.tif 000013
【００４４】
とのマッチングに失敗した推定法線を有する各３次元点及び３次元線の投票をカウントしない。いくつかの実施形態では、平面生成器１１１は平面の向き
【００４５】
【数１２】
2012530323.tif 000014
【００４６】
とのマッチングに失敗した推定法線を有する各３次元点及び３次元線をフィルタリングする。
【００４７】
[0040]１つの実施形態では、平面生成器１１０によって３次元点及び３次元線がサンプリングされ、ヒストグラム
【００４８】
【数１３】
2012530323.tif 000015
【００４９】
を作成するのに用いられる代表的な一群の３次元点及び３次元線が取得される。３次元点のサンプルのセット（Ｓ１）が以下の
【００５０】
【数１４】
2012530323.tif 000016
【００５１】
によって構築される。３次元線のサンプルのセット（Ｓ２）が以下の
【００５２】
【数１５】
2012530323.tif 000017
【００５３】
によって構築される。ここで、Ｙｋは３次元線を表す。
【００５４】
[0041]各３次元点サンプルｘｋはサイズ
【００５５】
【数１６】
2012530323.tif 000018
【００５６】
の適応ガウスカーネルによって表される。カーネルのサイズは、平面生成器１１１によって、各３次元点に関連付けられた不確実性を考慮に入れるように適合される。平面生成器１１１は、ヒストグラム
【００５７】
【数１７】
2012530323.tif 000019
【００５８】
の平滑性を制御するための重み（Ｗ）を割り当てる。そして、平面生成器１１１は
【００５９】
【数１８】
2012530323.tif 000020
【００６０】
に直交する１次元の部分空間を作成し、該１次元の部分空間において各３次元点サンプルｘｋを投影し、３次元点サンプルが向き
【００６１】
【数１９】
2012530323.tif 000021
【００６２】
を共有しているか否かを判断する。マッチするごとに、現在の向き
【００６３】
【数２０】
2012530323.tif 000022
【００６４】
についてのヒストグラム
【００６５】
【数２１】
2012530323.tif 000023
【００６６】
におけるカウントが増大する。
【００６７】
[0042]各３次元線サンプルｙｋはサイズ
【００６８】
【数２２】
2012530323.tif 000024
【００６９】
の適応ガウスカーネルによって表される。カーネルのサイズは、各３次元線に関連付けられた不確実性を考慮に入れるように適合される。Ｗは、ヒストグラム
【００７０】
【数２３】
2012530323.tif 000025
【００７１】
の平滑性を制御するために割り当てられた重みである。そして、平面生成器１１１は
【００７２】
【数２４】
2012530323.tif 000026
【００７３】
に直交する１次元の部分空間を作成し、該１次元の部分空間において各３次元線サンプルｙｋを投影し、３次元線サンプルが向き
【００７４】
【数２５】
2012530323.tif 000027
【００７５】
を共有しているか否かを判断する。マッチするごとに、現在の向き
【００７６】
【数２６】
2012530323.tif 000028
【００７７】
のヒストグラム
【００７８】
【数２７】
2012530323.tif 000029
【００７９】
におけるカウントが増大する。
【００８０】
[0043]平面生成器１１１は、双方のヒストグラム
【００８１】
【数２８】
2012530323.tif 000030
【００８２】
において局所ピークを検出する。或る実施形態では、複数の平行な３次元線が多くの場合に偶然同一平面状にあり、かつ平行でない線は、実際の平面がシーン内に存在しない限り同一平面となる可能性がより低いので、３次元線が、全て
【００８３】
【数２９】
2012530323.tif 000031
【００８４】
に直交する複数（≧２）の独自の方向を有するとき、平面生成器は
【００８５】
【数３０】
2012530323.tif 000032
【００８６】
におけるピークをカウントする。また、平面生成器１１１は非最大抑圧（non-maximal suppression）を実行して近接しすぎた候補平面を生成することを回避する。そして、ピークの向き、３次元点、及び３次元線の任意の組み合わせに基づいて候補平面が生成される。
【００８７】
[0044]他の実施形態では、平面生成器１１１は２次元画像１２０、基面、及び背面によって捕捉されたシーンの誤対応部分の追加平面を提供する。誤対応部分はスパースな大域シーン情報を有する２次元画像１２０の領域である。平面生成器１１１は、２点ＲＡＮＳＡＣアルゴリズム又は３点ＲＡＮＳＡＣアルゴリズムを用いて、３次元点及び消失方向のランダムサンプリングを実行することができる。そして、平面生成器１１１によって、関連付けられた３次元点の不確実性が計算され、３次元点を通る追加平面の向きが求められ、候補平面のセットが特定される。
【００８８】
[0045]平面生成器１１１はまた、カメラによって捕捉された２次元画像の各ビューについて基面及び背面を計算する。基面は、カメラのサイドベクトルに直交するアップベクトルを選択することによって推定される。基面は、アップベクトルに直交し、かつ平面上に位置する３次元点の９５％を有する平面として特定される。そして、平面生成器１１１は３次元シーンにおける基部をより良好に表すように基面を精緻化する。
【００８９】
[0046]背面は、カメラの光軸に直交するベクトルを選択することによって推定される。背面は、光軸に直交し、かつ平面の正面に位置する３次元点の９５％を有する平面として特定される。そして、平面生成器１１１は、３次元シーン内の背景をより良好に表すように背面を最適化することができる。
【００９０】
[0047]最適化エンジン１１２は、平面生成器１１１によって提供された候補平面を用いて各２次元画像について深度マップを生成するように構成される。最適化エンジン１１２は、３次元画像内の候補平面及び２次元画像内のピクセルを用いてマルコフ確率場（ＭＲＦ）を生成する。最適化エンジン１１２はピクセル及び平面を表すノードを有するグラフを生成する。グラフは、グラフのノードを連結するエッジも含んでいた。各エッジは、該エッジが連結する２つのピクセルに異なる平面ラベルを割り当てることに対するペナルティを表すコストに関連付けられる。最適化エンジン１１２は、画像内のピクセルへの平面ラベル割当ての一貫性を測定する目的関数の値を求める。いくつかの実施形態では、最適化エンジン１１２はエネルギー関数Ｅを用いてピクセルの最適なラベリングを求める。
【００９１】
[0048]エネルギー関数Ｅは、近傍システムを用いて基礎を成すピクセルデータに関して規定されたＭＲＦにおける事後確率分布の対数尤度を表す（例えば、４連結近傍は全ての垂直近傍ピクセル及び水平近傍ピクセルを考慮する）。最適化エンジン１１２は
【００９２】
【数３１】
2012530323.tif 000033
【００９３】
の値を求めることができる。各平面Ｐはラベルｌに対応する。各ピクセルは画像内の点ｐに対応し、該ピクセルにラベルｌｐを割り当てることができる。ラベルのセットは有限であり、閉集合ｌｐ∈Ｌから選択される。エネルギー関数Ｅはデータ項及び平滑項（smoothness term）を含む。データ項Ｄｐは、最適化エンジン１１２が、ラベルｌｐを割り当てられたピクセルｐのコスト（ペナルティ）を測定することを可能にする。平滑項Ｖｐ，ｑは、最適化エンジン１１２が、近傍ピクセルｐ及びｑがそれぞれラベルｌｐ及びｌｑを割り当てられるときはいつでもコストを割り当てることによって区分的に平滑なラベリングを促進する（すなわち解を正規化する）ことを可能にする。或る実施形態では、Ｖｐ，ｑはメトリックであり、最適化エンジン１１２は拡張移動アルゴリズムを実行して、大域最適化から証明可能な距離内にあるラベル割当てを計算することができる。
【００９４】
[0049]いくつかの実施形態では、最適化エンジン１１２は平面のサブセットＭ⊆Ｐについてラベルｌｐを選択することができる。平面のサブセットはＭ＝｛ｍｉ｝，ｉ＝１．．．Ｎによって表され、各選択された平面ｍｉはカメラに面し、カメラの視錐台（view frustum）内にある。最適化エンジン１１２は平面ｍのロケーションに対応するロケーションに関連付けられたピクセルの密度に基づいて平面ｍｉをソートすることができる。加えて、最適化エンジンは、一群の２次元画像における水平線のロケーションに基づいて平面Ｍのサブセット内に基面及び背面を含むことができる。
【００９５】
[0050]１つの実施形態では、最適化エンジン１１２は、マルチビュー光学的整合性、３次元点及び３次元線の地理的近接度、並びに３次元点及び３次元平面の光線視認性を組み合わせることによってＤｐを測定する。Ｄｐはラベルｌｐ（すなわち平面ｍｐ）をピクセルｐに割り当てるコストを測定する。
【００９６】
【数３２】
2012530323.tif 000034
【００９７】
であり、ここで
【００９８】
【数３３】
2012530323.tif 000035
【００９９】
はマルチビュー光学的整合性であり、
【０１００】
【数３４】
2012530323.tif 000036
【０１０１】
はスパースな３次元点及び３次元線の地理的近接度であり、
【０１０２】
【数３５】
2012530323.tif 000037
【０１０３】
は、３次元点及び３次元線の、自由空間違反に基づく光線視認性を測定する。一実施形態では、最適化エンジン１１２は各ピクセルにおいて
【０１０４】
【数３６】
2012530323.tif 000038
【０１０５】
を密に測定することができ、スパース制約を用いて、１つ又は複数の２次元画像１２０内の特定のピクセルにおいて
【０１０６】
【数３７】
2012530323.tif 000039
【０１０７】
及び
【０１０８】
【数３８】
2012530323.tif 000040
【０１０９】
を測定する。
【０１１０】
[0051]最適化エンジン１１２は、基準画像の近傍画像から複数のビューを選択することによってマルチビュー光学的整合性
【０１１１】
【数３９】
2012530323.tif 000041
【０１１２】
を測定し、近傍画像及び基準画像のビュー間の類似性を測定する。１つの実施形態では、最適化エンジン１１２は、基準画像Ｉｒについて、ｋ（≦１０）個の近傍画像
【０１１３】
【数４０】
2012530323.tif 000042
【０１１４】
を選択する。そして、最適化エンジン１１２は、平面ｍｐによって、各近傍画像
【０１１５】
【数４１】
2012530323.tif 000043
【０１１６】
をワープして基準画像Ｉｒにするためのホモグラフィを生成する。最適化エンジン１１２によって、ワープ画像
【０１１７】
【数４２】
2012530323.tif 000044
【０１１８】
及び基準画像Ｉｒを用いて、ワープ画像
【０１１９】
【数４３】
2012530323.tif 000045
【０１２０】
及び基準画像Ｉｒのρ×ρ経路における各ピクセルρにおいて正規化相互相関（ＮＣＣ）を測定する。いくつかの実施形態では、ρ＝９であり、ＮＣＣは基準画像ｗｒ（ρ）のピクセルとワープ画像ｗｊ（ｐ）のピクセルとの類似度を測定する。最適化エンジン１１２は、視差範囲ｄを有する候補平面のロケーションにおける不確実性を考慮することができる。視差範囲δｐは平面ｍｐを中心とすることができ、最適化エンジン１１２は視差範囲内の最適なマッチを検索することができる。いくつかの実施形態では、最適化エンジンは、最適なマッチを探しているときに２次元画像
【０１２１】
【数４４】
2012530323.tif 000046
【０１２２】
を修正する。各平面に関連付けられたＮＣＣの測定値はＭｊ（ｐ）＝ｍａｘ（ＮＣＣ（ｗｒ（ｐ），ｗｊ（ｑ）））であり、ここでｑ＝（ｐ−ｄ，ｐ＋ｄ）である。各近傍画像についての類似度測定値は、
【０１２３】
【数４５】
2012530323.tif 000047
【０１２４】
の値を求めるのに用いられる類似度の全体測定値において平均化される。
【０１２５】
【数４６】
2012530323.tif 000048
【０１２６】
であり、ここでσ＝０．８であり、Ｋ＝３００である。一実施形態では、最適化エンジン１１２は類似度スコアの値を求めるときに、画像内の遮蔽を誤対応として扱うことができる。
【０１２７】
[0052]最適化エンジン１１２は、スパースな３次元点及び３次元線の地理的近接度
【０１２８】
【数４７】
2012530323.tif 000049
【０１２９】
を測定する。最適化エンジン１１２は、平面ｍｐの正対応（inlier）として特定された各３次元点を選択する。そして、最適化エンジン１１２によって平面ｍｐ上の最も近接した３次元点が選択される。平面ｍｐの正対応であり、かつ平面ｍｐ上にある３次元点は、ピクセルｑ及び  においてそれぞれ基準３次元ビューに投影される。最適化エンジン１１２は、ｑの周囲の３×３の窓内の全てのピクセルｐについて
【０１３０】
【数４８】
2012530323.tif 000050
【０１３１】
の値を求めて、３次元点の地理的近接度を求める。最適化エンジン１１２は、３次元線の端点を用いて、かつ各端点の再投影誤りの値を求めて、スパースな３次元線の地理的近接度
【０１３２】
【数４９】
2012530323.tif 000051
【０１３３】
を測定する。
【０１３４】
[0053]最適化エンジン１１２は、３次元点及び３次元平面の光線視認性並びに
【０１３５】
【数５０】
2012530323.tif 000052
【０１３６】
に基づいて自由空間違反を測定する。最適化エンジン１１２は、自由空間制約に違反するピクセル−平面割当てに大きなペナルティを割り当てる。１つ又は複数の２次元画像によって捕捉されたビューにマッチする３次元点Ｘ又は３次元線分Ｌは、３次元シーンにおける対応するビューにおいて視認可能であるべきである。最適化エンジン１１２は視認可能であるべき３次元点又は３次元線分Ｌを特定し、該３次元点又は３次元線分Ｌに対応する光線を特定する。最適化エンジン１１２は３次元点又は３次元線分Ｌに交差する任意の平面をロケーション特定し、自由空間違反ペナルティを付与する。１つの実施形態では、最適化エンジン１１２によって、光線平面交差が発生するロケーションを表す各平面ｍｐ上の３次元点のセットＦが特定される。そして、３次元点Ｘｊに関連付けられたｑの周囲の３×３の窓内の全てのピクセルｐについて、最適化エンジン１１２によって、３次元シーンのビュー内に投影する各Ｘｊ∈Ｆについて
【０１３７】
【数５１】
2012530323.tif 000053
【０１３８】
が割り当てられる。
【０１３９】
[0054]３次元シーン内の境界においてピクセル及びラベルを効率的に割り当てるための平滑項Ｖp,qが最適化エンジン１１２によって割り当てられる。最適化エンジン１１２は適切な不連続性を用いた区分的に一定のラベル付けを促進する。平滑項は、平面構成及び消失方向から導出された地理的制約を課し、この地理的制約によって、最適化エンジン１１２は正確なラベル境界を回復することが可能になる。いくつかの実施形態では、最適化エンジン１１２は、３次元シーンの一部分である２次元画像における遮蔽エッジ及び折れエッジを特定するように構成される。３次元シーンに関連付けられた深度マップは、遮蔽エッジ及び折れエッジの双方を含むことができ、それらは平面不連続性を表すことができる。遮蔽エッジでは、該遮蔽エッジを横切って動くピクセルにおいて、平面ラベル及びシーン深度の双方が異なる。遮蔽エッジは２次元画像のいかなる場所でも発生し得る。しかし、平面シーンの場合、遮蔽エッジは通常、２次元画像内の視認可能な２次元線分と合致する。折れエッジでは、該折れエッジを横切るピクセルについて、平面ラベルのみが異なる。平面ラベルの対間の折れエッジは、２つの対応する平面の３次元交差線の投影と合致し、したがって常に直線の線分である。
【０１４０】
[0055]別の実施形態では、最適化エンジン１１２は一群の２次元画像内の各２次元画像の平面ジオメトリを同時に推定することができる。３次元シーンの推定された平面ジオメトリは不整合を有する場合がある。最適化エンジン１１２は、各２次元画像内のピクセルを通る、該ピクセルに対応する候補平面への光線をレンダリングして３次元点をロケーション特定することによってこの不整合を検出する。最適化エンジン１１２は近傍画像内のピクセル上に３次元点を再投影して、該３次元点に対応する近傍画像内のピクセルに割り当てられた平面が元の２次元画像内の候補平面にマッチするか否かを判断することができる。最適化エンジン１１２は、不整合のピクセル−平面割当てにペナルティを課す平滑項を加えることによって不整合に対処することができる。ピクセルにおける各可能な平面選択について、平面を近傍画像内の対応するピクセルに連結する平滑項が求められる。対応する近傍ピクセルにおけるピクセル−平面割当てが異なる場合、最適化エンジン１１２によって用いられる最適化関数によって計算された大域コストに、平滑項としてペナルティが加えられる。
【０１４１】
[0056]１つの実施形態では、最適化エンジン１１２は、２次元画像内の線分を特定することによって遮蔽エッジ及び折れエッジを検出する。２次元線分を通過するラベル境界を用いて遮蔽エッジ及び折れエッジをロケーション特定する。いくつかの実施形態では、最適化エンジンによって消失方向を用いて、直線遮蔽エッジの選択をシグナリングする。
【０１４２】
[0057]最適化エンジン１１２は、３次元シーン内の平滑項の区分的定義の値を求める。近傍ピクセル（ｐ，ｑ）に関連付けられた近傍平面ｌｐ及びｌｑを用いて平滑項の値を求める。
【０１４３】
[0058]
ｌｐ＝ｌｑのとき
【０１４４】
【数５２】
2012530323.tif 000054
【０１４５】
[0059]
ｌｐ≠ｌｑのとき
【０１４６】
【数５３】
2012530323.tif 000055
【０１４７】
[0060]いくつかの実施形態では、λ１＝１０００、λ２＝１２００、及びλ３＝２０００である。
【０１４８】
[0061]最適化エンジン１１２は、平面Ｍのサブセットにおける全ての平面対（ｍｉ，ｍｊ）について折れ線のセット｛Ｌｉｊ｝を求め、２次元画像の境界内にある平面ｌｉ及びｌｊを選択する。各平面ｌｉ及びｌｊについて、最適化エンジン１１２は２次元画像内の近傍ピクセル（ｐ，ｑ）の対をロケーション特定する。ここで、ｐ及びｑはｌｉ及びｌｊの異なる側にある。最適化エンジン１１２は、（ｐ，ｑ，ｌｉ，ｌｊ）の４つ組の組み合わせを用いてセットＳ１を生成する。
【０１４９】
[0062]最適化エンジン１１２は遮蔽線のセット｛Ｌｉｋ｝を求める。各平面ｍｉについて法線に直交する消失方向を用いて遮蔽線をロケーション特定する。特定された消失方向をサポートする２次元線分を用いて２次元画像内の近傍ピクセルの対（ｐ，ｑ）をロケーション特定する。ここで、ｐ及びｑはｌｉ及びｌｋの異なる側にある。最適化エンジン１１２は（ｐ，ｑ，ｌｉ，ｌｌ）の４つ組の組み合わせを用いてセットＳ２を生成する。セットＳ２は最適化エンジン１１２によってポピュレートされる。最適化エンジン１１２は、ｐ及びｑの中点から光線を逆投影し、カメラからの距離に基づいてソートしたときに｛ｍｉ｝を超える平面｛ｍｋ｝のリストを取得する。
【０１５０】
[0063]残りの２次元線分は最適化エンジン１１２によって特定される。そして、２次元線をサポートする近傍ピクセル（ｐ，ｑ）のセットＳ３が生成される。平滑項によって、最適化エンジン１１２は、３次元シーン内に含まれる不連続性を有する平面を効率的に表現することができる。
【０１５１】
[0064]再構成エンジン１１３は、３次元平面上の最適化及び最適化エンジンによって提供される関連ピクセルに基づいて３次元シーン内のナビゲーションを提供するように構成される。１つの実施形態では、グラフカット最適化は深度マップ及びプロキシメッシュを提供し、これらを用いてナビゲート可能な３次元シーンが生成される。再構成エンジン１１３は、一群の２次元画像内の各ラベル画像を２次元トライアンギュレーションに変換することができる。いくつかの実施形態では、再構成エンジンはラベル境界に対しポリライン簡単化を用いて２次元画像のトライアンギュレーションを生成する。そして、２次元画像のトライアンギュレーションは、再構成エンジン１１３によって、ラベルに対応する平面から形成された３次元三角形のセットに直接マッピングされる。
【０１５２】
[0065]そして、再構成エンジン１１３によって、３次元三角形のセットに投影的テクスチャマッピングが適用され、複数の２次元画像間のビュー補間が可能になる。ビュー補間中、再構成エンジン１１３は各２次元画像を、その対応するプロキシメッシュに投影的にテクスチャマッピングする。
【０１５３】
[0066]再構成エンジン１１３によって実行されるテクスチャマッピングは、３次元シーンを表す混合したクロスフェード平面を生成することができる。再構成エンジンによって、各ピクセルについて混合色（Ｃ１，Ｃ２）が求められる。再構成エンジンは以下の値を求める。
【０１５４】
[0067]
【０１５５】
【数５４】
2012530323.tif 000056
【０１５６】
及び
[0068]
【０１５７】
【数５５】
2012530323.tif 000057
【０１５８】
[0069]再構成エンジン１１３は、遷移全体を通じて完全に不透過でレンダリングされることになる１つのソース画像によってのみカバーされる３次元シーンの補間されたビューにおいて、その遷移にピクセルを与えるように構成される。再構成エンジン１１３はビュー補間中、複数の画像からの寄与でピクセルを線形にクロスフェードする。再構成エンジン１１３によって実行されたクロスフェージングは、閲覧者が、他の２次元画像によって満たされている２次元画像の遮蔽されていない領域に焦点を当てることを防ぐ。
【０１５９】
[0070]ユーザーは、一群の２次元画像を、３次元シーンを再構成するコンピューター化された再構成サーバーに提供することができる。代替的に、ユーザーはローカルコンピューター上で３次元再構成プログラムを実行して、該ローカルコンピューター上に配置された２次元画像から３次元シーンを再構成することができる。３次元シーンはナビゲート可能であり、ユーザーに、２次元画像によって捕捉されたシーンの没入型の体験を提供する。
【０１６０】
[0071]図２は、本発明の実施形態による例示的な２次元画像を示すイメージ図である。この２次元画像は家の様々なビューを捕捉している。１つの実施形態では、図２Ａ及び図２Ｂの２次元画像はカメラによって捕捉されている。そして、２次元画像はコンピューター化された再構成サーバーによって処理され、３次元シーンが生成される。
【０１６１】
[0072]いくつかの実施形態では、３次元シーンは、各２次元画像に対し動きからの構造復元（structure from motion）を実行して画像特徴及びカメラキャリブレーションを抽出することによって再構成される。そして、コンピューター化された再構成サーバーによって、画像特徴及びカメラキャリブレーションを用いて、３次元シーンの候補平面を特定する。平面候補はコンピューター化された再構成サーバーによって組織化され、３次元シーン内の全体大域整合性に基づいてレンダリングされる。
【０１６２】
[0073]図３は、本発明の実施形態による例示的な３次元平面を示す平面図である。図３Ａは、コンピューター化された再構成サーバーによって、シーンの様々なビューを捕捉する２次元画像に対して実行される、動き特徴抽出及びカメラキャリブレーション決定からの構造を示している。画像特徴（例えば、線、点、色、ピクセル等）及びカメラキャリブレーション（例えば、向き、ロケーション等）を用いて３次元線及び３次元平面が生成される。図３Ｂは、コンピューター化された再構成サーバーによって生成された３次元線を示している。図３Ｃ〜図３Ｅは、コンピューター化された再構成サーバーによって生成された様々な３次元視点の候補平面を示している。
【０１６３】
[0074]コンピューター化された再構成サーバーは、画像特徴及びカメラキャリブレーションに基づいて３次元シーンの深度マップ及びプロキシメッシュを生成する。そして、３次元シーンは、推定された３次元平面、深度マップ、及びプロキシメッシュを用いてレンダリングされる。いくつかの実施形態では、コンピューター化された再構成システムは３次元シーンをカラーリングし、３次元シーンに関連付けられた視点間の遷移を提供する。
【０１６４】
[0075]図４は、本発明の実施形態による計算システムによって生成された一例示のシーンを示す３次元シーンの図である。コンピューター化された再構成システムは、３次元シーンのビューに関して、図４Ａに示す深度マップを生成する。そして、コンピューター化された再構成システムによって、プロキシメッシュを用いて３次元シーンにテクスチャを提供する。プロキシメッシュが図４Ｂに示されている。コンピューター化された再構成サーバーはプロキシメッシュに対するテクスチャマッピングも実行する。テクスチャマッピングされたプロキシメッシュが図４Ｃに示されている。
【０１６５】
[0076]１つの実施形態では、コンピューター化された再構成システムは２次元画像における消失方向を検出する。コンピューター化された再構成サーバーは消失方向に基づいて３次元線を構成する。そして、消失方向並びに３次元線及び３次元点を用いて候補平面を生成する。候補平面は、３次元シーンのプロキシメッシュを規定する。
【０１６６】
[0077]図５は、本発明の実施形態による、２次元画像内の消失方向の検出を示す消失方向図である。コンピューター化された再構成システムによって２次元画像が受信される。図５Ａは、コンピューター化された再構成システムによって処理され消失方向が抽出される一例示の２次元画像を示している。図５Ｂは、２次元画像から抽出された消失方向の各クラスターの向きを示している。コンピューター化された再構成サーバーは、消失方向に対応する３次元線及び対応する画像特徴を特定する。図５Ｃは、コンピューター化されたサーバーによって消失方向及び生成された３次元線を用いてレンダリングされた３次元シーンの一例示の再構成を示している。
【０１６７】
[0078]コンピューター化された再構成サーバーは、３次元シーンの深度マップに関連付けられた不確実性に基づいて３次元シーンを調整する。コンピューター化された再構成サーバーによって実行される平面検出は、該コンピューター化された再構成サーバーによって生成された平面上に位置するか又は該平面に近接した３次元点のビュー方向に沿ってベクトルを計算することによってこの不確実性を考慮する。そして、コンピューター化された再構成サーバーは、３次元点の面に対する法線を推定し、３次元点を通る平面の向きを推定する。
【０１６８】
[0079]図６は、本発明の実施形態による面法線の確率分布を示す法線方向図である。コンピューター化された再構成システムは、３次元点Ｘｋの周囲の各３次元点について共分散（
【０１６９】
【数５６】
2012530323.tif 000058
【０１７０】
）を求める。図６Ａは、３次元点Ｘｋの周囲の３次元点の共分散
【０１７１】
【数５７】
2012530323.tif 000059
【０１７２】
の基準を示している。また、コンピューター化された再構成サーバーは、Ｘｋに近接した３次元点間の面法線
【０１７３】
【数５８】
2012530323.tif 000060
【０１７４】
の分布の値を求める。コンピューター化された再構成システムによって、法線を用いて、３次元点Ｘｋを通る平面の向きを求める。図６Ｂは、３次元点Ｘｋを通る平面の法線の分布を示している。
【０１７５】
[0080]いくつかの実施形態では、法線の分布は、強力な独自のピークを有せず、複数の視点からの投票及び関連する画像特徴を用いて平面の向きが推定される。コンピューター化された再構成サーバーは、３次元点及び３次元線からの平面の向きに関する投票を収集することができる。そして、投票の分布を用いて平面の向きが求められる。
【０１７６】
[0081]図７は、本発明の実施形態による、平面又は３次元線の向きの確率分布を示す分布ヒストグラムである。３次元点及び３次元線からの投票の分布は、コンピューター化された再構成サーバーによってヒストグラムにおいて値を求められる。図７Ａは、３次元点からの投票に基づく法線の分布を表すヒストグラム
【０１７７】
【数５９】
2012530323.tif 000061
【０１７８】
を示している。図７Ｂは、３次元線からの投票に基づく法線の分布を表すヒストグラム
【０１７９】
【数６０】
2012530323.tif 000062
【０１８０】
を示している。コンピューター化された再構成サーバーによって特定された平面に対し、優勢の法線が向きとして割り当てられる。
【０１８１】
[0082]コンピューター化された再構成サーバーは、平面にピクセルを割り当てるときの光線視認性を考慮するグラフカット最適化を実行する。２次元画像から抽出され、３次元線及び３次元点に対応する光線視認性情報は、グラフカット最適化を実行するのに利用される目的関数におけるデータ項として用いられる。３次元線又は３次元点に対応する平面から対応する視点までの可視光線（visibility ray）に交差する任意の平面はペナルティを割り当てられる。
【０１８２】
[0083]図８は、本発明の実施形態による２次元画像から抽出されたシーン情報を示す視認性の図である。平面ｍｉは３次元線Ｌ及び３次元Ｘに関連付けられる。３次元線Ｌ及び３次元Ｘは複数の視点において視認可能である。平面ｍｋは平面ｍｉから対応する視点への可視光線と交差する。コンピューター化された再構成システムによって実行される最適化機能は、平面ｍｋが視点と平面ｍｉとの間で可視光線と交差するので、平面ｍｋに高い視認性コストを割り当てることになる。
【０１８３】
[0084]３次元ピクセル及び３次元平面は、コンピューター化された再構成サーバーによってグラフ内に組織化される。コンピューター化された再構成システムによって、グラフカット最適化が実行され、平面に対するピクセルの最適な割当てが選択される。グラフカット最適化は、平面及びピクセルを連結する各エッジに関連付けられたデータ項及び平滑項の値を求める。
【０１８４】
[0085]図９は、本発明の実施形態による、マルコフ確率場表現及びグラフカット最小化を用いた平面を表すラベルに対するピクセルの割当てを示すグラフである。
【０１８５】
[0086]グラフは、２次元画像内のピクセルに対応するノードと、３次元シーン内の平面に対応するラベルとを含む。グラフは、３次元シーンのマルコフ確率場を表すことができる。各ピクセルｌ（ｉ，ｊ）は平面Ｐ（ｉ，ｊ）に割り当てられる。ピクセルｌ（ｉ，ｊ）と平面Ｐ（ｉ，ｊ）とを連結しているエッジは、コンピューター化された再構成システムによって値を求められたデータ項及び平滑項に基づくコストを割り当てられる。カットコストは除去又はカットされるエッジの合計である。ピクセルｌ（ｉ，ｊ）と平面Ｐ（ｉ，ｊ）とを連結しているエッジは、３次元シーンの平面に各ピクセルを割り当てる全体コストを測定する目的関数を最小にするように除去される。
【０１８６】
[0087]いくつかの実施形態では、コンピューター化された再構成システムは、一群の２次元画像における近傍画像をワープすることによって光学的整合性を測定する。そして、コンピューター化された再構成サーバーはワープ画像と近傍画像との間の類似度を測定する。コンピューター化された再構成システムによって、複数の近傍の類似度スコアが平均化され、光学的整合性測定値の値が求められ、この測定値はグラフカット最適化におけるデータ項として用いられる。
【０１８７】
[0088]図１０は、本発明の実施形態に従って３次元シーンを生成するのに用いられる２次元画像間の関係を示す光学的整合性の図である。コンピューター化された再構成サーバーは、一群の２次元画像から選択された基準画像を特定する。図１０Ａは一例示の基準画像を示している。そして、近傍２次元画像が選択され、ワープされ、光学的整合性が計算される。図１０Ｂは、コンピューター化された再構成システムによって用いられる一例示の近傍ワープ画像を示している。図１０Ｃは、コンピューター化された再構成サーバーによって求められた、基準画像とワープ画像との間の光学的整合性の測定値を示している。
【０１８８】
[0089]グラフカット最適化の平滑項を用いて、ピクセル及び平面が、平滑な境界遷移を確実にするように割り当てられることを確実にする。コンピューター化された再構成サーバーは、２次元に含まれる折れ線及び遮蔽線を特定する。そして、コンピューター化された再構成サーバーは、折れ線、遮蔽線、及び２次元シーン内の他の線に関連付けられたピクセル及び平面のロケーションに基づいて平滑項の値を求める。
【０１８９】
[0090]図１１は、本発明の実施形態による、３次元シーン内の平面の平面境界及び遮蔽境界の対の交差に対応する折れエッジを示す境界図である。
【０１９０】
[0091]コンピューター化された再構成サーバーは、２次元画像内の折れ線を特定する。折れ線は図１１Ａに示されている。折れ線を用いて、該折れ線を生成する平面間の境界の平滑項が計算される。コンピューター化された再構成サーバーは、２次元画像内の遮蔽線を特定する。遮蔽線は図１１Ｂに示されている。遮蔽線を用いて、該遮蔽線を生成する平面に関連付けられた境界の平滑項を計算する。
【０１９１】
[0092]コンピューター化された再構成サーバーによって提供されるピクセル及び平面割当てに基づいてプロキシメッシュが生成される。そして、コンピューター化された再構成サーバーは、プロキシメッシュ内の平面にテクスチャをマッピングし、テクスチャを付けられマッピングされたメッシュをユーザーに表示する。コンピューター化された再構成システムはまた、３次元シーンのビューを補間して、３次元シーン内のナビゲーションを提供する。
【０１９２】
[0093]図１２〜図１７は、本発明の実施形態による、種々の３次元シーンにおける視点間の可能なナビゲーションを示す遷移図である。
【０１９３】
[0094]いくつかの実施形態では、コンピューター化された再構成サーバーは、ナビゲート可能な３次元シーンをレンダリングする方法を実行する。一群の２次元画像が受信され、処理されて、画像特徴及びカメラキャリブレーションが抽出される。コンピューター化された再構成サーバーは、カメラによってシーン内で捕捉された３次元線を特定し、消失方向、画像特徴、及びカメラキャリブレーションを用いて３次元シーンの複数の平面を生成する。
【０１９４】
[0095]図１８は、本発明の実施形態による、電子データベース内に格納された一群の画像からナビゲート可能な３次元シーンをレンダリングするのに用いられる平面を選択する方法を示す論理図である。この方法は、ステップ１８１０において開始する。ステップ１８２０において、コンピューター化された再構成サーバーによって、電子データベースから一群の画像が受信される。ステップ１８３０において、コンピューター化された再構成サーバーは一群の画像からシーン情報を抽出する。シーン情報は、カメラキャリブレーション、３次元点群、３次元線分、並びに点及び線のマルチビュー一致のためのデータを含むことができる。
【０１９５】
[0096]そして、ステップ１８４０において、コンピューター化された再構成サーバーは、エッジ検出を用いて一群の画像における各画像内の消失方向を検出する。消失方向は、収集画像内に含まれる平行線の方向を表すベクトルである。消失方向は、一群の２次元画像から推定された平行な３次元線の方向から導出される。代替的に、消失方向は、一群の２次元画像における２次元画像から抽出された２次元線交差から推定することができる。１つの実施形態において、コンピューター化された再構成サーバーによって、平均シフトクラスタリングを用いて、一群の２次元画像によって捕捉された様々なビューの消失方向を選択する。
【０１９６】
[0097]ステップ１８５０において、コンピューター化された再構成サーバーは消失方向及びシーン情報に基づいて、ナビゲート可能な３次元シーン内の各平面を特定する。一実施形態では、コンピューター化された再構成サーバーは一群の画像から抽出された消失方向の各可能な対の外積に基づいて平面の向きのセットを求める。加えて、コンピューター化された再構成サーバーによって、３次元シーンの優勢な平面を特定することができる。
【０１９７】
[0098]ステップ１８６０において、コンピューター化された再構成サーバーはマルコフ確率場分布を生成し、該マルコフ確率場分布に適用された最小化関数に基づいて各平面にピクセルを割り当てる。最小化関数は、ナビゲート可能な３次元シーンにおいて平面にピクセルを割り当てる大域コストを最適化する。ピクセルは３次元点群内に含まれ、中でも、一群の画像内に含まれる複数のビューにわたる光学的整合性に基づいて優勢な平面のそれぞれに割り当てられる。いくつかの実施形態では、画像内のピクセルは、カメラの向きに対応する平面に投票する。代替的に、一群の画像における各画像内のピクセルは、大域コストを最小にする平面−ピクセル割り当てを求めるために反復的に投票する。或る実施形態では、最小化関数は、平滑項によって制約されたマルコフ確率場分布グラフのカットコストを選択する。マルコフ確率場分布グラフの選択されたカットコストは、コンピューター化された再構成サーバーによって、大域コストに到達するように集計することができる。
【０１９８】
[0099]１つの実施形態では、平面−ピクセル割り当ての大域コストの一部分は、マルコフ確率場分布グラフに適用された最小化関数に含まれる平滑項によって表される。コンピューター化された再構成サーバーは、平面及びピクセルを有するマルコフ確率場分布グラフ内の平滑項を、遮蔽平面の法線ベクトルに直交する消失方向に整合する２次元線における不連続性に対応する遷移を選好するように計算ことができる。コンピューター化された再構成サーバーは、平面への１つの画像内のピクセルの割当てに対し、近傍画像内の対応するピクセルが同じ平面を選択しなかった場合にペナルティを課すように平滑項を計算することができる。コンピューター化された再構成サーバーは、画像内の２次元線に対応する遷移を選好するように平滑項を計算することができる。
【０１９９】
[00100]コンピューター化された再構成サーバーは、割り当てられた平面上でピクセルをレンダリングする。この方法はステップ１８７０において終了する。
【０２００】
[00101]コンピューター化された再構成サーバーは、ピクセル及び平面の可能な割当てを表すグラフに対し実行される最適化に基づいてピクセルを割り当てる。コンピューター化された再構成サーバーは、ピクセルと平面との間の各割当てのコストを最小にすることを試みる。割当てのコストは、データ項及び平滑項を含む目的関数によって表される。
【０２０１】
[00102]図１９は、電子データベース内に格納された一群の２次元画像からナビゲート可能な３次元シーンを再構成するときに、２次元画像から３次元平面にピクセルを割り当てる方法を示す論理図である。この方法は、ステップ１９１０において開始する。ステップ１９２０において、コンピューター化された再構成サーバーは一群の２次元画像を受信する。ステップ１９３０において、コンピューター化された再構成システムは、２次元画像から抽出されたシーン情報から３次元平面のセットを生成する。シーン情報は、消失方向、線、及び３次元点を含む。
【０２０２】
[00103]そして、ステップ１９４０において、コンピューター化された再構成サーバーによって、シーン情報及び生成された３次元平面を用いてマルコフ確率場が生成される。ステップ１９５０において、コンピューター化された再構成システムは、マルコフ確率場によって表されたエネルギー関数を最小にするように、生成された平面にピクセルを割り当てる。マルコフ確率場は２次元画像の深度マップを提供する。
【０２０３】
[00104]マルコフ確率場は、ピクセルを割り当てるための条件を設定するデータ項、及び平面間の遷移のための条件を設定する平滑項に基づいて最適化される。いくつかの実施形態では、ピクセル割当て中に、コンピューター化された再構成システムは、マルチビュー光学的整合性のためのデータ項、スパースな３次元点及び３次元線の地理的近接度、並びに３次元点及び３次元線の光線視認性から導出された自由空間違反を検査する。データ項は、画像内で観測された３次元点又は３次元線を遮蔽する平面へのピクセルの割当てにペナルティを課すか、又は画像内で観測された３次元点若しくは３次元線に整合する平面にピクセルを割り当てることを促進する。別の実施形態では、データ項は、平面への１つの画像内のピクセルの割当てに対し、近傍画像内の対応するピクセルが一群の２次元画像における各２次元画像上を反復的に通過する間に同じ平面を選択しなかった場合にペナルティを課す。
【０２０４】
[00105]平滑項は、平面が交差する線に沿った平面間の遷移を選好する。平滑項はまた、遮蔽平面の法線ベクトルに直交する消失方向に整合する２次元線における不連続性に対応する遷移も選好する。平滑項は、画像内の２次元線に対応する遷移を選好する。平滑項は、平面への１つの画像内のピクセルの割当てに対し、近傍画像内の対応するピクセルが、一群の２次元画像における２次元画像上を同時に通過する間に同じ平面を選択しなかった場合にペナルティを課す。
【０２０５】
[00106]コンピューター化された再構成システムによって、ピクセル−平面割当てに基づいて深度マップが生成され、ナビゲート可能な３次元シーンをレンダリングするのに用いられる。いくつかの実施形態では、コンピューター化された再構成システムは、遮蔽線及び折れ線を特定することによって深度マップ及び境界を補正する。コンピューター化された再構成サーバーによって、深度マップ及び２次元画像の投影を用いて３次元シーンがレンダリングされる。２次元画像投影はクロスフェージングされ、３次元シーンの一部分である一群の２次元画像のそれぞれの平滑なビュー補間が可能になる。この方法はステップ１９６０において終了する。
【０２０６】
[00107]要約すると、大量の整列されていない２次元画像の画像に基づくレンダリングに用いられる区分的に平面の密な深度マップを計算する自動方法を実行するコンピューター化された再構成サーバー及びクライアントが提供される。コンピューター化された再構成サーバーは大域シーン情報を用いて３次元シーンを生成するので、コンピューター化された再構成サーバーによってレンダリングされる３次元シーンは信頼性があり、写実的である。コンピューター化された再構成サーバーは、３次元点及び３次元線のロバストな平面適合に基づいて優勢なシーン平面のセットを回復する一方、強力な消失方向を利用して平面の向きを推測する。コンピューター化された再構成サーバーによって、マルコフ確率場（ＭＲＦ）グラフ及び対応する最適化が実行され、２次元画像に含まれる多角形形状及び直線形状の不連続性から導出された地理的制約を組み込んだ区分的平面深度マップが生成される。また、コンピューター化された再構成サーバーによって、３次元点及び３次元線の光線視認性を用いて自由空間制約が強化され、非ランバートでかつテクスチャのない表面を有するシーンにおける穴が最小にされる。
【０２０７】
[00108]本発明の実施形態の上述の説明は例示的なものであり、構成及び実施態様の変更はこの説明の範囲内にある。例えば、本発明の実施形態は、図１〜図１９を参照して大まかに説明されたが、これらの説明は例示的なものである。構造的特徴及び方法論的動作に特有の言語で主題を説明したが、添付の特許請求の範囲において規定される主題は必ずしも上述した特定の特徴又は動作に限定されないことが理解される。そうではなく、上述した特定の特徴及び動作は、特許請求の範囲を実施する形態例として開示されている。したがって、本発明の実施形態の範囲は、以下の特許請求の範囲によってのみ限定されることが意図される。
【図１】
2012530323.tif 000063
【図２Ａ】
2012530323.tif 000064
【図２Ｂ】
2012530323.tif 000065
【図３Ａ】
2012530323.tif 000066
【図３Ｂ】
2012530323.tif 000067
【図３Ｃ】
2012530323.tif 000068
【図３Ｄ】
2012530323.tif 000069
【図３Ｅ】
2012530323.tif 000070
【図４Ａ】
2012530323.tif 000071
【図４Ｂ】
2012530323.tif 000072
【図４Ｃ】
2012530323.tif 000073
【図５Ａ】
2012530323.tif 000074
【図５Ｂ】
2012530323.tif 000075
【図５Ｃ】
2012530323.tif 000076
【図６Ａ】
2012530323.tif 000077
【図６Ｂ】
2012530323.tif 000078
【図７Ａ】
2012530323.tif 000079
【図７Ｂ】
2012530323.tif 000080
【図８】
2012530323.tif 000081
【図９】
2012530323.tif 000082
【図１０Ａ】
2012530323.tif 000083
【図１０Ｂ】
2012530323.tif 000084
【図１０Ｃ】
2012530323.tif 000085
【図１１Ａ】
2012530323.tif 000086
【図１１Ｂ】
2012530323.tif 000087
【図１２Ａ】
2012530323.tif 000088
【図１２Ｂ】
2012530323.tif 000089
【図１３Ａ】
2012530323.tif 000090
【図１３Ｂ】
2012530323.tif 000091
【図１４Ａ】
2012530323.tif 000092
【図１４Ｂ】
2012530323.tif 000093
【図１５Ａ】
2012530323.tif 000094
【図１５Ｂ】
2012530323.tif 000095
【図１６Ａ】
2012530323.tif 000096
【図１６Ｂ】
2012530323.tif 000097
【図１７Ａ】
2012530323.tif 000098
【図１７Ｂ】
2012530323.tif 000099
【図１７Ｃ】
2012530323.tif 000100
【図１７Ｄ】
2012530323.tif 000101
【図１７Ｅ】
2012530323.tif 000102
【図１８】
2012530323.tif 000103
【図１９】
2012530323.tif 000104
【国際調査報告】
2012530323.tif 000105
2012530323.tif 000106