(57)【特許請求の範囲】
【請求項１】
ストリートビューの画像をラベル付けする方法であって、前記画像はピクセルの列のセットを含み、該方法は、
少なくとも１つのコンピュータ読み取り可能なメモリに記憶されたコンピュータ実行可能な命令を実行する少なくとも１つのプロセッサを使用するステップであって、２次元の各特徴を含む画像ピクセルを有する画像を受信するステップと、前記画像に対応する、３次元の各画像特徴を含む画像データ点を受信するステップと、を実行するステップと、
ピクセルごとに、前記画像ピクセルから外観特徴を抽出するステップであって、前記外観特徴は、ラベル付きデータセットから学習されたディープニューラルネットワークを用いて決定される、ステップと、
ピクセルごとに、前記画像データ点から奥行き特徴を抽出するステップと、
列単位のラベル付け手順を適用して、前記画像のピクセルの列の前記セットからのピクセルの各列ごとに、前記外観特徴及び前記奥行き特徴の両方を用いてピクセルの各列からピクセルごとに意味ラベル及び奥行きラベルを共同で求めるステップであって、前記列単位のラベル付け手順は、前記ストリートビューのモデルに従い、ピクセルの列の前記セットのピクセルの各列は、最上層または第４の層から、第１の層または最下層までの、最大で４つの順序付けられた層を含み、前記最大で４つの順序付けられた層は、各画像列ごとに前記意味ラベル及び前記奥行きラベルを共同で推定する推測手順を用いて、取得される、ステップと、
前記最大で４つの順序付けられた層に施された前記列単位のラベル付け手順を処理するステップと
を含み、各前記ステップは前記プロセッサが実行する、方法。
【請求項２】
前記ストリートビューのモデルの前記第１の層は運転可能エリアを表し、第２の層は、ストリートにおける動的オブジェクトを表し、第３の層は静的オブジェクトを表し、前記第４の層は空を表し、これらの層における奥行きは上から下に向かって順序付けされる、請求項１に記載の方法。
【請求項３】
前記第１の層内の前記運転可能エリアは、地面、草、歩道を含む、請求項２に記載の方法。
【請求項４】
前記第２の層内の前記動的オブジェクトは、車両、歩行者、自転車運転者、オートバイ運転者及び動物を含む、請求項２に記載の方法。
【請求項５】
前記第３の層内の前記静的オブジェクトは、建物、橋及び木を含む、請求項２に記載の方法。
【請求項６】
前記外観特徴は、前記ラベル付けされたデータセットから学習された前記ディープニューラルネットワークを用いて求められ、前記ディープニューラルネットワークは、意味クラスのための画像特徴を前記画像から抽出するのに用いられる、
請求項１に記載の方法。
【請求項７】
前記奥行き特徴は、ステレオ画像から得られた視差マッチングコストから求められる、請求項１に記載の方法。
【請求項８】
ピクセルの列の最上層におけるピクセルのための前記奥行きラベルは、ピクセルの前記列の残りの低次層内のピクセルの前記奥行きラベルより大きい、
請求項１に記載の方法。
【請求項９】
ピクセルの列の最下層におけるピクセルのための前記奥行きラベルは、基面定数によって決定される、
請求項１に記載の方法。
【請求項１０】
前記画像は、カメラ装置または画像取得装置によって取得され、前記ラベル付けされた画像は、ディスプレイ上の出力であり、前記ディスプレイおよび前記プロセッサは車両に搭載されている、
請求項１に記載の方法。
【請求項１１】
ストリートビューの画像をラベル付けする方法であって、前記画像はピクセルの列のセットを含み、該方法は、
少なくとも１つのコンピュータ読み取り可能なメモリに記憶されたコンピュータ実行可能な命令を実行する少なくとも１つのプロセッサを使用するステップであって、２次元の各特徴を含む画像ピクセルを有する画像を受信するステップと、前記画像に対応する、３次元の各画像特徴を含む画像データ点を受信するステップと、を実行するステップと、
ピクセルごとに、前記画像ピクセルから外観特徴を抽出するステップであって、前記外観特徴は、前記画像から意味的クラスのための画像特徴を抽出するのに用いられるラベル付きデータセットから、ディープ・マルチスケール・畳み込みネットワークを用いて決定される、ステップと、
ピクセルごとに、前記画像データ点から奥行き特徴を抽出するステップと、
列単位のラベル付け手順を適用して、前記画像のピクセルの列の前記セットからのピクセルの各列ごとに、前記外観特徴及び前記奥行き特徴の両方を用いてピクセルの各列からピクセルごとに意味ラベル及び奥行きラベルを共同で求めるステップであって、前記列単位のラベル付け手順は、前記ストリートビューのモデルに従い、ピクセルの列の前記セットのピクセルの各列は、最上層または第４の層から、第１の層または最下層までの、最大で４つの順序付けられた層を含み、前記最大で４つの順序付けられた層は、各画像列ごとに前記意味ラベル及び前記奥行きラベルを共同で推定する推測手順を用いて、取得される、ステップと、
前記最大で４つの順序付けられた層に施された前記列単位のラベル付け手順を処理するステップと
を含み、各前記ステップは前記プロセッサが実行する、方法。
【請求項１２】
前記推測手順は動的アルゴリズムに基づき、
前記動的アルゴリズムは、
前記最大で４つの順序付けられた層の最上部ピクセルのｙ座標を示す変数ｈｉ１、ｈｉ２、ｈｉ３及びｈｉ４を含み、
変数ｌｉ１、ｌｉ２、ｌｉ３及びｌｉ４は、前記最大で４つの順序付けられた層のための意味的ラベルであり、
変数ｄｉ１、ｄｉ２、ｄｉ３及びｄｉ４は、前記最大で４つの順序付けられた層の奥行きであり、
未知の変数のみが決定され、例えば、前記未知の変数がｈ１、ｈ２、ｈ３、ｌ２、ｄ３を含むとき、前記未知の変数は、下式によって求められる、
【数１】
0006485646.tif 000028
請求項１に記載の方法。
【請求項１３】
前記推測手順は動的アルゴリズムに基づき、
前記動的アルゴリズムは、
前記最大で４つの順序付けられた層の最上部ピクセルのｙ座標を示す変数ｈｉ１、ｈｉ２、ｈｉ３及びｈｉ４を含み、
変数ｌｉ１、ｌｉ２、ｌｉ３及びｌｉ４は、前記最大で４つの順序付けられた層のための意味的ラベルであり、
変数ｄｉ１、ｄｉ２、ｄｉ３及びｄｉ４は、前記最大で４つの順序付けられた層の奥行きであり、
未知の変数のみが決定され、例えば、前記未知の変数がｈ１、ｈ２、ｈ３、ｌ２、ｄ３を含むとき、前記未知の変数は、下式によって求められる、
【数２】
0006485646.tif 000029
請求項１１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、画像処理に関し、より詳細には、画像内の意味特徴及び奥行き特徴に基づいてストリートシーン（street scene：街頭風景）の画像をラベル付けすることに関する。
【背景技術】
【０００２】
オンラインストリートビューアプリケーションは、多くの場合、オンラインマッピングアプリケーションと組み合わされる。例えば、ユーザーは、マップ又は衛星画像から特定の地理的対象点を選択し、次に、パノラマストリートビューに切り替える。ストリートビューは、ユーザーが、例えば車両の運転者によって見えるとおりに対象点までナビゲートすることを可能にする。ストリートビューは、多くの他のコンピュータービジョン、拡張現実、スマートカー及び安全性の用途に用いることもできる。
【０００３】
通常のストリートシーンは、コンポーネント、例えば、基面の道路と、歩行者、自転車運転者、他の車両等のオブジェクトと、建物と、空とを含む。そのようなシーンの画像を理解しラベル付けすることは、コンポーネント及びそれらの相対的空間ロケーションを理解することを必要とする。ほとんどの従来の方法はこれを２つの問題、すなわち三次元（３Ｄ）シーン再構成及びコンポーネントセグメンテーションとして解く。
【０００４】
近年、これらの２つの問題は統合され、単一の最適化問題として解決されているが、依然として幾つかの課題が存在している。従来技術によるセグメンテーションは、ピクセルを様々なクラスに分類することに焦点を当てる。そのような手法は、一般的に長時間かかり、ストリートシーンについて守られる階層制約（layered constraint）を遵守しない場合がある。
【０００５】
ストリートシーンのラベル付けは、意味的セグメンテーション及びシーンの理解に関連する。初期の従来技術による方法は、通常、手作業で設計された（hand-designed）特徴に基づいていた。近年、特徴学習のためにディープニューラルネットワークを用いることによって、より良好な性能がもたらされることが示されている。意味的セグメンテーション及び奥行き推定の双方をステレオカメラから解くことは、統一されたエネルギー最小化フレームワークを用いて行うことができる。
【０００６】
道路シーンの１つの一般的なモデルは、基面と、障害を表す地面上の１組の垂直スティックとを用いてワールドを単純化する「ｓｔｉｘｅｌワールド」である。ｓｔｉｘｅｌは、地面に立っている直立したオブジェクトの一部を、その３Ｄフットプリント、高さ、幅、及びカメラまでの距離（奥行き）によってコンパクトでかつ効率的に表す。ｓｔｉｘｅｌ表現は、場合によっては非常に非平滑的な２つの曲線の計算によって特徴付けることができる。ここで、第１の曲線は衝突なしで即座に到達可能であり得る自由空間を取り囲む基面上を通り、第２の曲線は、自由空間の垂直オブジェクトの境界を符号化する。ｓｔｉｘｅｌワールドを求めるために、半グローバルステレオマッチング手順（ＳＧＭ）からの奥行きマップ、又はステレオマッチングコストを用いることができる。
【０００７】
ｓｔｉｘｍａｎｔｉｃｓシーン表現は、ｓｔｉｘｅｌと比較して柔軟性が高い。列ごとに１つのｓｔｉｘｅｌのみを有する代わりに、ｓｔｉｘｍａｎｔｉｃｓは、画像内の全ての列に沿った複数のセグメントを可能にし、また、近隣のセグメントを組み合わせて、より良好な幾何学的意味を有するスーパーピクセル型エンティティを形成する。
【発明の概要】
【０００８】
本発明の実施形態は、ストリートシーンのための４階層モデルと、地面、例えば道路、歩行者及び車両等の移動オブジェクト、建物並びに空等のコンポーネントの意味クラスをラベル付けする方法とを提供する。
【０００９】
方法への入力はステレオ画像対である。ニューラルネットワークを用いて、ステレオ画像から意味クラスのための特徴を抽出する。画像列ごとに意味クラス及び階層型奥行きを共同で推定する推測手順を用いて階層モデルを得る。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施形態による、ステレオ画像対におけるコンポーネントをラベル付けする方法の概略図である。
【図２】本発明の実施形態による、図１の方法の流れ図である。
【図３】本発明の実施形態による、４つの層を有するストリートシーンの画像である。
【図４】本発明の実施形態による、ラベル付けされた層の概略図である。
【発明を実施するための形態】
【００１１】
図１及び図２に示すように、本発明の実施形態は、ストリートシーンのための４階層モデルと、ステレオ画像対１０１内のコンポーネントをラベル付けする方法２００とを提供する。当該コンポーネントには、例えば道路等の地面と、歩行者及び車両等のオブジェクトと、建物と、空とが、含まれる。当該画像は、カメラ２０１によって取得することができる。ラベル付けされた画像１０２はディスプレイ２０２上に出力することができる。本方法のステップは、当該技術分野において既知のバスによって、メモリ、および、入出力インターフェースに接続されたプロセッサ２０３において実行することができる。１つの実施形態では、ディスプレイ及びプロセッサは車両内に配置することができる。このようにして、車両の運転者に、向上したシーン画像を知らせることができる。
【００１２】
ディープニューラルネットワーク、例えば、畳み込みニューラルネットワーク（ＣＮＮ）２１０を用いて、ステレオ画像１０１から、意味クラスのための画像特徴２１１を抽出する。ステレオコスト関数２２０を用いて奥行き特徴２２１を抽出する。画像特徴及び奥行き特徴は、層順序制約２３１を受けた列単位の画像ラベル付け手順２３０によって処理されて、ラベル付けされた画像１０２が生成される。
【００１３】
階層型ストリートシーン
図３に示すように、本発明の目的は、外観情報及び三次元情報を用いて、ストリートビュー画像内のピクセルごとに意味ラベル及び奥行きを共同で（jointly）推定することである。本発明では、階層型画像解釈を用いる。画像は、異なる意味コンポーネント及び奥行きコンポーネントの１つ〜４つの層に水平に分割される。層１は地面、例えば道路である。層２は、歩行者（ｐｅｄｓ）と、車両やオートバイ等の他の動的オブジェクトとを含み得る。層３は建物を含み、層４は空である。
【００１４】
各層は下から上に向かって順序付けされる。各画像列において、同じ層に属するピクセルは、同じ意味ラベル、及び、ほぼ同じ奥行きを有する。唯一の例外は、地面層におけるピクセルの奥行きは、地面によって決定されるそれらのピクセルの垂直画像座標に応じて変動する可能性があることである。本発明では、奥行き順序制約、すなわち、各画像列において、低次層の奥行きは常に高次層の奥行きよりも小さくなくてはならないという制約を課す。
【００１５】
例えば、第１の層は、地面、例えば運転可能エリアのみを有することができる。第２の層は、オブジェクト、例えば歩行者又は車両を含むことができる。第３の層は、建物のみを有することができる。第４の層は、空のみを有することができる。本発明では、各画像列が厳密に４つの層を有することを強制しない。１つの列は、１つ〜４つの層を有することができ、換言すれば、列は４つの層全てを含まなくてもよい。これは、層を分離する境界が平滑でかつ連続している必要がないことを暗に意味する。４層モデルは、ストリートシーンの豊富で系統的な解釈をもたらす。本発明では、以下で説明するように、シーン内で幾何学及び意味論を実施するための柔軟な方法を提供する。
【００１６】
注記
【数１】
0006485646.tif 000002
及び
【数２】
0006485646.tif 000003
を用いて、それぞれ水平のｘ座標及び垂直のｙ座標を含む組を指す。ここで、
【数３】
0006485646.tif 000004
は画像幅であり、
【数４】
0006485646.tif 000005
は画像高さである。５つの異なる意味クラス、すなわち、それぞれシンボル
【数５】
0006485646.tif 000006
によって表される地面、車両、歩行者、建物及び空を用いる。意味クラスラベルの組は、
【数６】
0006485646.tif 000007
によって表される。視差（奥行き）の組のために
【数７】
0006485646.tif 000008
を用いる。本明細書において、視差及び奥行きは、相互に置き換え可能なもの（interchangeably）として用いられる。カメラ較正パラメーターを用いることによって、１対１の変換を得ることができることを理解されたい。意味ラベル空間及び視差値の濃度はそれぞれ
【数８】
0006485646.tif 000009
及び
【数９】
0006485646.tif 000010
によって表される。
【００１７】
ストリートシーンモデル
図４に示すように、階層型ストリートビュー問題を、制約付きエネルギー最小化問題として定式化する。制約は、各列における意味オブジェクトクラスラベル及び奥行き値の順序を符号化する。制約は、各画像列に関連付けられた変数の解空間を制限する。本発明では、動的計画法に基づく推測アルゴリズムを用いて制約付きエネルギー最小化問題を効率的に解く。
【００１８】
本発明では、変数ｈｉ１、ｈｉ２、ｈｉ３及びｈｉ４を用いて、画像列４００内の４つの層の最上部ピクセルのｙ座標を表す。ｌｉ１、ｌｉ２、ｌｉ３及びｌｉ４を、４つの層のための意味オブジェクトクラスラベルとし、ｄｉ１、ｄｉ２、ｄｉ３及びｄｉ４を、画像列ｉ内の４つの層の奥行きとする。順序付け制約及び地面の知識によって、これらのパラメーターのうちの幾つかを知ることが可能になる。未知数の実際の数は、ｘｉ＝［ｈｉ１，ｈｉ２，ｈｉ３，ｌｉ２，ｄｉ３］によって与えられる５つのみである。このため、全体画像のためのラベル割り当ては、ｘＩ＝［ｘ１，ｘ２，．．．，ｘＷ］によって与えられる。画像列のための可能な割り当ての数は、
【数１０】
0006485646.tif 000011
であるため、Ｏ（Ｈ３ＬＤ）のオーダーである。
【００１９】
ラベル尤度ランク付け
ラベル割り当ての尤度をランク付けするために、画像外観特徴２１１及びステレオ視差マッチング特徴２２１からの証拠を用いる。列内の全てのピクセルからの証拠を総計して、証拠を計算する。
【数１１】
0006485646.tif 000012
及び
【数１２】
0006485646.tif 000013
を、それぞれ、ｘｉを画像列ｉに割り当てるときに被る意味ラベルコスト及び奥行きラベルコストを表すデータ項とする。２つの項は合算され、ｘｉを画像列ｉに割り当てるコストを表すデータ項
【数１３】
0006485646.tif 000014
が得られる。各ピクセルが独立した変数として奥行き値及び意味ラベルを有することができる標準２Ｄマルコフ確率場（ＭＲＦ）空間に対し作用する代わりに、本発明では、問題を以下によって与えられる制約付きエネルギー最小化問題に変換する。
【００２０】
【数１４】
0006485646.tif 000015
【００２１】
ここで、第１の制約は層構造を与え、第２の制約は奥行き順序を強制し、第３の制約は意味変動を制限する。変数ｄｉ２はｈｉ１の関数、すなわち地面層の最上部ピクセルロケーションである。なぜなら、本発明では、動的オブジェクトが画像のｈｉ１番目の行において水平地表面に対し垂直であると仮定するためである。エネルギー関数
【数１５】
0006485646.tif 000016
は、同じ列内のピクセルの関係をモデル化するが、同じ行内のピクセルの関係はモデル化しない。同じ行内のピクセルの関係は、特徴関数内に暗黙的に符号化される。ピクセルロケーションにおける特徴計算のための受容野（reception fields）として、ピクセルを中心とする画像パッチを用いる。近傍ピクセルは類似した受容野を有し、このため、類似した特徴表現及びクラスラベル割り当てを有する。
【００２２】
データ項Ｕｉ（ｘｉ）は、ラベルｘｉを列ｉに割り当てるコストである。データ項は以下によって与えられるピクセル単位のデータ項の総和である。
【００２３】
【数１６】
0006485646.tif 000017
【００２４】
ここで、ピクセルごとの外観データ項ＥＡ（ｘ，ｙ，ｌ）は、ラベルｌをピクセル（ｘ，ｙ）に割り当てるコストであり、ピクセルごとの奥行きデータ項ＥＤ（ｘ，ｙ，ｄ）は奥行きｄをピクセル（ｘ，ｙ）に割り当てるコストである。ピクセルごとの外観データ項ＥＡ（ｘ，ｙ，ｌ）を得るためにディープ畳み込みニューラルネットワークを用い、ピクセルごとの奥行きデータ項ＥＤ（ｘ，ｙ，ｄ）を得るために従来の視差コストを用いる。
【００２５】
奥行き特徴
本発明では、ピクセルごとの奥行きデータ項のための平滑化された絶対輝度差を用いる。これは、ステレオ再構成アルゴリズムにおいて一般的に用いられる。まず、Ｄ内の視差値ごとにピクセルごとの絶対輝度差を計算し、これによりコストボリューム表現をレンダリングする。次に、コストボリュームを平滑化するためにボックスフィルターを適用する。ピクセルごとの奥行きデータ項は以下によって与えられる。
【００２６】
【数１７】
0006485646.tif 000018
【００２７】
ここで、ＩＬ及びＩＲは左画像及び右画像の輝度値を指し、Ｐ（ｘ，ｙ）は（ｘ，ｙ）を中心とする画像パッチであり、Ｎ＝｜Ｐ（ｘ，ｙ）｜は正規化定数としての役割を果たすパッチの濃度を表す。パッチサイズは、例えば１１×１１ピクセルに固定される。
【００２８】
外観特徴
ディープマルチスケール畳み込みニューラルネットワーク（ＣＮＮ）を用いてピクセルごとの外観データ項を求める。例えば、ネットワークは３つの畳み込み層を有する。
（１）サイズ８×８の１６個のフィルター、それに続く正規化線形関数（ＲｅＬＵ：Rectified Linear Unit）非線形性、及び２×２の最大値プーリング、
（２）サイズ７×７×１６の６４個のフィルター、それに続くＲｅＬＵ、及び２×２の非重複最大値プーリング、及び、
（３）サイズ７×７×６４の２５６個のフィルター、それに続くＲｅＬＵ。
【００２９】
１つの実施形態では、０．５を減算することによって０と１との間にスケーリングされたグレースケール画像をＣＮＮのための入力として用いる。スケール間で共有されるフィルターが、入力画像のガウスピラミッドの３つのスケールに別個に適用される。
【００３０】
より低いスケールからの特徴は、元の画像サイズにアップサンプリングされることに留意されたい。３つのスケールからの特徴は、ピクセルごとに３×２５６＝７６８個の特徴を得るように連結される。ネットワークをトレーニングするために、特徴層を、５つのニューロン（クラス）を有する全結合層に結合し、それに続いて、ｓｏｆｔｍａｘ又は正規化指数層に結合する。全結合層においてドロップアウトを用いることもできる。ネットワークは、運動量を用いた確率的勾配降下法により交差エントロピー誤差を最小化することによってトレーニングされる。クラスのｓｏｆｔｍａｘスコアの負対数を、ピクセルごとの外観データ項として用いる。
【００３１】
推測手順
式（２）のエネルギー最小化問題をＷ個の部分問題に分解する。ここで、ｉ番目の部分問題は以下によって与えられる。
【００３２】
【数１８】
0006485646.tif 000019
【００３３】
部分問題のそれぞれを最適に解き、これらの解を組み合わせて画像の意味及び奥行きの完全なラベル付けを構築する。表記を簡単にするために以下の記載では下付き文字ｉを省く。
【００３４】
部分問題のそれぞれを１Ｄチェーンラベル付け問題にマッピングすることができる。チェーンは４つのノードを有することができる。ここで、第１のノードは変数（ｈ１，ｄ１，ｌ１）を含み、第２のノードは変数（ｈ２，ｄ２，ｌ２）を含み、第３のノードは変数（ｈ３，ｄ３，ｌ３）を含み、第４のノードは変数（ｈ４，ｄ４，ｌ４）を含む。従来の動的計画アルゴリズムは、ラベルコスト評価において再帰を利用し、複雑度Ｏ（（ＨＤＬ・Ｈ）２）で１Ｄチェーンラベル付け問題を解くことができる。ここで、積ＨＤＬは各ノードにおけるラベル空間のサイズを表し、第２のＨは各ノードにおけるラベルコスト評価のために必要とされる複雑度である。不都合なことに、この複雑度はリアルタイム用途には高すぎる。
【００３５】
（９）における部分問題を解く複雑度をＯ（Ｈ２Ｄ）に低減してリアルタイム動作を達成するための動的計画アルゴリズムの一変形を記載する。まず、問題定式化セクションに記載したように、変数のうちの幾つかが、本発明によるストリートビューセットアップから既知であることを記す。本発明では、ｈ１、ｈ２、ｈ３、ｌ２、ｄ３の値を検索するのみでよい。ｈ１、ｈ２及びｌ２の任意の組み合わせについて、ｄ３及びｈ３の最良の組み合わせを求める。以下において、任意のｈ１、ｈ２及びｌ２のためのｄ３及びｈ３の最良の組み合わせを事前に計算することを、再帰を用いてＯ（Ｈ２Ｄ）の時間で達成することができることを示す。
【００３６】
まず、（９）における問題を、このとき以下のように書き換えることができることに着目する。
【００３７】
【数１９】
0006485646.tif 000020
【００３８】
ここで、Ｑｉは、以下によって与えられる中間コストテーブルである。
【００３９】
【数２０】
0006485646.tif 000021
【００４０】
第２の層オブジェクトｄ２の奥行きは、ｈ１の関数であることに留意されたい。なぜなら、ｄ２はｈ１及び地面方程式（基面方程式）から一意に求めることができるためである。結果として、Ｑｉはｈ１及びｈ２の双方によって決まる。
【００４１】
【数２１】
0006485646.tif 000022
及び
【数２２】
0006485646.tif 000023
をｙ方向に沿って積分することによって、ｈ２及びｈ３の全ての組み合わせについて、下式によって得られる総和は、固定のｄ３についてＯ（Ｈ２）の時間で計算することができる。
【００４２】
【数２３】
0006485646.tif 000024
【００４３】
なお、Ｑｉは、下式によって与えられる再帰更新規則により計算することができることも更に記す。
【００４４】
【数２４】
0006485646.tif 000025
【００４５】
ここで、
【数２５】
0006485646.tif 000026
は、
【数２６】
0006485646.tif 000027
を満たす整数であり、第２の層と第３の層との間の奥行き順序付け制約が満たされることを確実にするのに用いられる。
【００４６】
直観的に、本発明では、建物層の減少していく奥行きに沿って移動最小構造（running min structure）を計算している。再帰的更新規則によって、Ｏ（Ｈ２Ｄ）の時間で任意のｈ１及びｈ２についてＱｉを計算することが可能になる。結果として、分割のための最良構成を得る複雑度を、Ｏ（Ｈ２Ｌ＋Ｈ２Ｄ）＝Ｏ（Ｈ２Ｄ）に低減することができる。ここで、Ｈ２Ｌはｈ１、ｈ２及びｌ２の組み合わせを探索するのに必要な時間である。各画像列に対し１Ｄラベル付けアルゴリズムを実行する。ラベル付けアルゴリズムの全体複雑度はＯ（ＷＨ２Ｄ）である。
【図１】
0006485646.tif 000030
【図２】
0006485646.tif 000031
【図３】
0006485646.tif 000032
【図４】
0006485646.tif 000033