(57)【要約】      （修正有）【課題】環境中に分散したセンサのポーズを求めることである。【解決手段】環境の信号が各センサにより得られる。少なくとも１つの他の信号中の特徴に対応する、各信号中の特徴が識別される。センサと対応する特徴との間の方向が求められる。方向の零空間を使用して行列が構築される。行列の零空間固有ベクトルが求められ、次いで零空間固有ベクトルが、センサの位置を特定する行列に再構成される。【選択図】図３
2005172803.tif 000002
【特許請求の範囲】
【請求項１】
環境中に分散した複数のセンサのポーズを求める方法であって、
各センサを使用して前記環境の信号を得ること、
少なくとも１つの他の信号中の特徴に対応する各信号中の特徴を識別すること、
各センサと前記対応する特徴との間の方向を求めることによって前記センサの向きを求めること、
前記方向の零空間を行列に整理すること、
前記行列の単一の零空間固有ベクトルを求めること、
前記単一の零空間固有ベクトルを、各センサの各位置の各次元毎に１行を有する行列に構成すること
を含む、環境中に分散した複数のセンサのポーズを求める方法。
【請求項２】
前記センサはカメラであり、前記信号は画像であり、前記方向は前記画像中の特徴から求められる、請求項１記載の方法。
【請求項３】
前記センサはアレイ無線受信器であり、前記方向は、前記環境中の点源から放射される前記信号との位相差から求められる、請求項１記載の方法。
【請求項４】
前記センサはアレイ無線受信器であり、前記方向は、前記環境中の点源から放射される前記信号の伝搬時間差から求められる、請求項１記載の方法。
【請求項５】
前記方向の制約は不確実である、請求項１記載の方法。
【請求項６】
前記行列は複数の固有ベクトルを含み、
前記複数の固有ベクトルから、前記方向をすべて正にする線形結合を選択することをさらに含む、請求項１記載の方法。
【請求項７】
前記方向の制約は同時に矛盾すると共に、制約過剰であり、かつ制約不十分である、請求項１記載の方法。
【請求項８】
前記行列を平行移動基底（translation basis）の零空間の直交基底に射影することをさらに含む、請求項１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはセンサに関し、より詳細にはセンサのポーズを求めることに関する。
【背景技術】
【０００２】
多くのコンピュータ用途では、センサが配置された環境中の被検知特徴に相対するセンサのポーズを求める必要がある。センサのポーズにより、センサの位置および向きの両方が与えられる。三次元では、位置は通常、三次元デカルト座標系（ｘ，ｙ，ｚ）によって特定され、向きは三次元極座標系（ｕ，ｖ，ｗ）によって特定される。
【０００３】
たとえば、多くのコンピュータビジョンおよびグラフィックス用途では、カメラのポーズを知る必要がある。こういった用途としていくつか挙げると、三次元再構築、運動からの構造復元（structure-from-motion）によるモデリング、写実的レンダリング、画像ベースの環境拡大、シミュレーション、および画像位置合わせがある。
【０００４】
単純な用途では、一対のカメラによりシーンの立体像の形の信号が得られる。両方の画像に共通する特徴は同一である。特徴を用いて、カメラの外部パラメータ（ポーズ）が求められる。その用途では、シーンは局所化され、信号は高度の重複を有する。この結果、大きな共通特徴群が得られる。２台のカメラが２枚の重複した画像を撮影する場合、スケールおよび向きまでカメラの相対的なポーズを容易に求めることができる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は、環境中に広く分散したセンサのポーズを求めることに関する。たとえば、画像の形の信号が、都市の様々な場所にあるセキュリティカメラにより、または都市を歩き回っている旅行者により、またはユーザが都市周辺を移動する際に携帯電話のカメラにより得られる。別の応用分野では、信号は、何千キロメートルも離れたところにある電波望遠鏡を使用して宇宙の一部から得られる。地球上に分散した数々のマイクロフォンまたは地震計は、大規模センサ網の他の例である。
【０００６】
したがって、本発明により処理する信号は２つの主な特性、すなわち信号が得られる環境が大きいこと、また設定信号が散在すると言えることを有する。或る信号のいくつかの特徴が、別の信号の特徴と一部重なるとはいえ、大半の信号において共通点は非常に少ない。
【０００７】
得られた信号からセンサのポーズを求めるいくつかの技法が既知である。特に興味深いのは、３つの平行移動自由度（位置）と３つの回転自由度（向き）とを切り離す方法である。このような方法では、自由度は通常、同時に推定されるパラメータ数を減らす要因である。対話型方法および自動型方法の両方が既知である。対話型方法は効率的にスケーリングせず、操作者エラーおよび数値不安定性に弱い。したがって自動型方法が好ましい。
【０００８】
射影技法もまた構造およびポーズを復元するのに使用することができるが、任意射影変換までのみである。他の運動からの構造復元方法は特異値分解またはランダム探索を用いる。しかし大半の従来技術による方法では、対応する特徴の大きな集合が必要である。
【０００９】
Antone等は、「Scalable extrinsic calibration of omni-directional image networks」IJCV 49, pp. 143-174, 2002において画像のスパース集合から対応する特徴（対応性）を復元する方法について述べている。対応性は、ランダム探索により、または同一位置の大まかな指示、たとえば画像ヒストグラムのマッチング、エッジ検出、ワイヤレス通信セルへの割り当て、またはＧＰＳから見つけることができる。Antone等はまた、スパース対応性を解析することによって一部重なる画像の集合の全体的な向きを求める方法について述べている。
【課題を解決するための手段】
【００１０】
本発明は、大規模環境、たとえば都市や世界に亘って分散したセンサのポーズを求める方法を提供する。方法は、センサによって得られたスパース信号を入力として採用する。スパースとは、各信号中のごく少数の特徴が少なくとも１つの他の信号中の少数の特徴に重なることを意味する。方法は、各信号のセンサのポーズ、すなわち位置および向きを求める。
【００１１】
本発明は、この問題を埋め込みグラフとしてモデリングする。埋め込みグラフに、二次形式の部分スペクトル分解が適用される。最小二乗誤差（ＭＳＥ）解により、センサのポーズおよび任意の数の次元での特徴が求められる。
【００１２】
スペクトル分解により制約不十分な問題も特定され、制約不十分な問題は次いで十分に制約された厳密な部分問題（rigid sub-problems）に分解することができる。次いで、部分問題を解析してセンサに新しいポーズを求め、欠けている制約を解決する追加信号を得ることができる。
【００１３】
本発明は、方向制約が信号中の対応する特徴から求められる多数のスパースに分散したセンサに対して特に有用である。
【００１４】
カメラ画像の場合、スペクトル分解により、１ミリメートルの何分の一かまで制約される解がもたらされ、最先端のキャリブレーション方法を４桁改良する。方法はまた、少なくとも２桁高速でもある。
【００１５】
従来技術による反復プロセスとは対照的に、本発明による方法は、数値的に安定した、線形時間で閉じた形の解を与える。方法は容易かつ高速に実施することができる。
【発明の効果】
【００１６】
本発明による部分スペクトル分解方法は、方向制約からグラフ埋め込みに線形時間最適解を与える。こういった解は制約に対して完璧な忠実性を有し、制約における欠点を曝す。いくつかの欠点は自動的に検出し補正することができ、制約が実質的な系統誤差を有する場合であっても誤制約付き問題の略完璧な埋め込みをもたらす。
【００１７】
スペクトル方法の１つの特定の有利な属性は、新しいノードおよび新しい制約を拡張零空間（expanded nullspace）Ｈε行列に対する一連の低ランク変更として表現することができるため、新しいデータが来たときに解を略線形時間で更新することができることである。したがって、新しい視点および環境特徴を増分的に追加することができる。
【００１８】
この方法は、不完全な方向制約からネットワークノードのポーズを計算したいいずれの問題にも適用されることがすぐに明らかになるはずである。こういったノードは非イメージングセンサ、たとえば得た信号の位相または伝搬時間差から方向情報を感知するフェーズアレイマイクロフォンやフェーズアレイアンテナであることができる。本発明は、夜空の特徴により全体の向きを計算する自然の集合または基準特徴が与えられる天文学の状況でも有用であることができる。
【００１９】
本発明について好ましい実施の形態の例として説明したが、本発明の精神および範囲内で他の様々な適合形態および変更形態を行い得ることを理解されたい。したがって、添付の特許請求の範囲の目的は、このような変形形態および変更形態をすべて本発明の真の精神および範囲内にあるものとして包含することにある。
【発明を実施するための最良の形態】
【００２０】
システム構造
図１は、センサまたは「ノード」１０１および１０２、たとえばカメラを示す。本発明による方法は、センサによって得られる信号１１１および１１２、たとえば画像を解析することによってセンサのポーズを求める。特徴として、広い環境、たとえば都市部や宇宙の一部の信号が得られる。各信号は、別の信号と共通するごく少数の特徴１２１を有する。したがって信号はスパースであると言える。
【００２１】
本発明による方法は、この問題をグラフ埋め込み問題として処理する。従来技術による解決策は通常、既知の混合重みを用いての隣接ノードへの方向の線形混合によってノードのポーズを制約する。Roweis等著「Nonlinear dimensionality reduction by locally linear embedding」Science 290, pp. 2323-2326, 2000を参照のこと。
【００２２】
同様に本方法は、ノードのポーズをノードと特徴１２１の間の方向１３１の線形混合に制約するが、未知の混合重みを用いる。方向は本質的にノードの向きを反映する。ポーズを求めるには、ノードの位置も求める必要がある。したがって、本方法は新規の構造を有する。すべての従来技術によるスペクトル埋め込み方法とは対照的に、本発明の解は埋め込みの次元に関わりなく単一の固有ベクトルによって識別される。固有ベクトルは行列に容易に再構成して、センサの（ｘ，ｙ，ｚ）位置を復元することができる。
【００２３】
図２Ａは単純な埋め込み問題を示す。方向制約１〜４の群をグラフに整理しなければならない。図２Ｂは、自由度を有することができる、たとえばノード４が部分的にのみ制約される解を示す。２Ｄでは問題は自明である。より高い次元では、制約は同時に矛盾すると共に、制約過剰であり、かつ制約不十分である。
【００２４】
動作方法
図３は本発明による方法３００を示す。センサ３０１は広い環境３０２に配置される。信号３１１が環境のセンサによって得られる（３１０）。信号中の対応する特徴３２１が識別される（３２０）。センサと特徴の間の方向３３１が求められる（３３０）。方向によりノードの向き３０７が明らかになる。
【００２５】
方向から零空間行列Ｈε３４１が構築される（３４０）。零空間行列の固有ベクトル３５１が求められる（３５０）。次いで、固有ベクトルが行列に再構成される（３６０）。行列は復元位置３０８の各次元毎に１行を有する。次いで、向き３０７および位置３０８によりセンサ３０１のポーズ３０９が明らかになる。
【００２６】
方向制約付き埋め込み
正式には、方向制約付き埋め込み問題は以下のように説明される。入力はＮ個のノード３０１の集合およびいくつかのノードｉ，ｊ∈［１，Ｎ］⊂Ｎ、ｉ≠ｊ間のノードからノードへの方向ｄｉｊ∈Ｒｄ３３１の不完全な指定である。真のノード間変位の符号および長さは未知である。解は、規模および平行移動まで一意に求めることができるＲｄ中の一貫した埋め込みの集合である。
【００２７】
本発明のスペクトル解は、細い固有値分解（ＥＶＤ：thin eigenvalue decomposition）に基づく。埋め込み行列
【００２８】
【数１】
2005172803.tif 000003
【００２９】
は、列ｉ中のｉ番目のノードの位置ｘｉ∈Ｒｄを制約する。ノード間変位（ｘｉ−ｘｊ）が制約方向ｄｉｊ３３１と最大に一致する埋め込みを求めることが望ましい。
【００３０】
最大共分散スペクトル解
まず、制約への変位の射影の長さの二乗が、
【００３１】
【数２】
2005172803.tif 000004
【００３２】
によって最大化される。式中、‖Ｘ‖はフロベニウスノルムまたはユークリッドノルムを表す。明らかにＣは二次形式を有する。したがって問題は凸である。Ｃを最大化するには、すべての埋め込み方向ベクトル
【００３３】
【数３】
2005172803.tif 000005
【００３４】
は対称行列
【００３５】
【数４】
2005172803.tif 000006
【００３６】
に縦連結される。式中、矢印は縦連結、横連結、およびブロック対角連結を示す。
【００３７】
ＨＣの固有ベクトルを最大化することにより、符号および規模までＣを最大化する埋め込みｙが求められる。
【００３８】
構築により、
【００３９】
【数５】
2005172803.tif 000007
【００４０】
である。
【００４１】
シュミット−エッカルト−ヤング（Schmidt-Eckart-Young）定理により、二次形式の最大
【００４２】
【数６】
2005172803.tif 000008
【００４３】
は、対応する固有ベクトルｙ＝ｖｍａｘ（ＨＣ）において得られる最大固有値λｍａｘ（ＨＣ）である。Eckart等著「The approximation of one matrix by another of lower rank」Psychometrika, Vol. 1, pp. 211-218, 1936を参照のこと。
【００４４】
したがって、最適埋め込みはＸ＝ｙ（ｄ）＝ｖ（ｄ）ｍａｘである。これはベクトルｙ∈ＲｄＮｘ１を行列Ｘ∈ＲｄｘＮに再構成するｄ次ベクトル転置である。但し、各行ｄは位置の次元に対応する。任意の方向ベクトルのノルム‖ｄｉｊ‖により、ノルムがどの程度強く最終解を制約するかが決まる。‖ｄｉｊ‖＝０の場合、制約は問題から除外される。したがって、問題はスパース制約を許容する。
【００４５】
最小二乗誤差（ＭＳＥ）スペクトル解
最大共分散問題は、方向が不正確な短変位を時に犠牲にして、大きな変位が方向的に正確である解を好む。誤差が解に亘って均等に分散し、制約により許される場合は厳密な解が保証されるため、最小二乗誤差の枠組みが好ましい。ＭＳＥ解を得るため、所望の方向に直交する変位の成分が最小化される。誤差関数は、
【００４６】
【数７】
2005172803.tif 000009
【００４７】
であり、式中、
【００４８】
【数８】
2005172803.tif 000010
【００４９】
は方向ｄｉｊの零空間の直交基底である。零空間は、所与の部分空間に直交するすべての方向として定義される。この場合、すべての方向はベクトルｄｉｊに垂直な平面にある。
【００５０】
図１に示すように、各方向制約ｄｉｊをノードｉまたはｊから出る線として思い描くことができる。値ε（Ｘ）は、線の長さで測られる、ノードからノードがある各線までの距離を二乗したものを合算する。すべての制約は、すべての方向ｄｉｊが同じノルムを有する場合に等しく重み付けされる。制約が誤差のない埋め込みを許す場合、埋め込みは制約のいずれの非ゼロ再スケールに対しても不変である。誤差関数εを最小化するために、零空間行列Ｈε３４１が、式（２）において以下の置換がある以外は行列ＨＣと同様に構築される（３４０）。
【００５１】
【数９】
2005172803.tif 000011
【００５２】
【数１０】
2005172803.tif 000012
【００５３】
に直交する空間中のＨεの固有ベクトル３５１を最小化することにより、符号およびスケールまで誤差関数（３）を最小化する所望の非退化埋め込み（non-degenerate embedding）ｙが求められる。
【００５４】
上に述べたように、
【００５５】
【数１１】
2005172803.tif 000013
【００５６】
である、すなわち方向ｄｉｊに直交するｘｉ−ｘｊの成分を分離し、‖ｄｉｊ‖２により成分をスケーリングするスケーリング直交射影作用素であるため、
【００５７】
【数１２】
2005172803.tif 000014
【００５８】
は固有対｛ε（ｙ（ｄ））＝λｍｉｎ（Ｈε），ｙ＝ｖｍｉｎ（Ｈε）｝によって最小化することができる。
【００５９】
【数１３】
2005172803.tif 000015
【００６０】
制約は、方向制約がすべてのノードをＲｄ中の単一点に写像することによって自明に満たされるため生じる。これは、零空間行列Ｈεが、Ｒｄ中の任意の場所にある点を見つけるために直交基底を与えるｄ個の擾乱な固有ベクトルを含むことを暗に示す。その基底は、
【００６１】
【数１４】
2005172803.tif 000016
【００６２】
であるため、
【００６３】
【数１５】
2005172803.tif 000017
【００６４】
に及ぶ。これによりまた、埋め込み空間において解を平行移動する直交基底も与えられる。したがって、非退化埋め込みは、
【００６５】
【数１６】
2005172803.tif 000018
【００６６】
に直交するＨεの零空間中になければならない。
【００６７】
従来技術による固有値ソルバは、零空間行列Ｈεを平行移動固有ベクトルおよび埋め込み固有ベクトルに分けない場合がある。さらに、従来技術による方法は一般に、零空間固有ベクトルと略零空間固有ベクトルを分ける数値エラーに弱い。
【００６８】
平行移動固有ベクトルを抑制することにより、問題の数値安定性を向上させることができる。これを行うために、零空間行列Ｈεは平行移動基底の零空間の直交基底Ｑ∈ＲＮｄｘ（Ｎ−１）ｄに射影され、すなわちＱＴＱ＝Ｉ、かつ
【００６９】
【数１７】
2005172803.tif 000019
【００７０】
である。次いで、簡約化された問題が固有値分解され、固有ベクトルが、
【００７１】
【数１８】
2005172803.tif 000020
によって逆射影される。
【００７２】
Ｈεの二次形式はスパースであり、零空間基底Ｑは単純な構造を有し、特別な計算効率が実現され、非常に大きなＥＶＤを計算するコストが削減されることが示唆される。
【００７３】
実際、所望の固有ベクトル３５１を得るためにいずれの行列も明示的に計算する必要がない。第１に、式（２）を用いて、ｙおよび方向制約からｙＴ（Ｉ−Ｈε）を直接求めることができる。したがって、行列Ｈε自体を構築することなく固有対｛λｍａｘ（Ｉ−Ｈε），ｖｍａｘ（Ｉ−Ｈε）｝＝｛１−λｍｉｎ（Ｈε），ｖｍｉｎ（ＨεＥ）｝を求める方法が使用可能になる。
【００７４】
さらに、Ｑは中心化行列：
【００７５】
【数１９】
2005172803.tif 000021
【００７６】
である。式（５〜６）中の行列Ｑは、Ｘ＝ｙ（ｄ）のすべての行が合算するとゼロになることを確実にすることによって原点にセンタリングされる解を構成する（３６０）。式（５〜６）は、構成を各々繰り返す毎にベクトルｙを再びセンタリングすることによってなくすことができる。
【００７７】
方向が不確実である場合、方向ベクトルｄｉｊを、直交列がそれぞれ、制約がその方向にある確実性によってスケーリングされる行列Ｄｉｊで置き換えることができる。外積
【００７８】
【数２０】
2005172803.tif 000022
【００７９】
は事実上、可能なすべての方向に亘るガウス分布の共分散である。関連するスケーリングされた直交射影作用素は‖Σｉｊ‖２・Ｉ−Σｉｊである。行列Ｄｉｊの列がスケーリングされない場合、方向制約は単に部分空間制約に弱められる。すなわち、ｘｊ−ｘｉがＤｉｊに亘る部分空間の可能な限り近くにある。
【００８０】
制約付き問題
スペクトル解は制約に対するＭＳＥ最適解である。ビジョン問題では、制約自体が画像データから導出され、したがって制約が疑わしい場合がある。したがって、制約データが不十分である、または矛盾する不適切問題を検出して解決するために、追加処理が必要な場合がある。
【００８１】
制約不十分問題
問題は、考えられる２つの条件下で制約不十分である。第１に、連結性グラフが切断している、すなわちｉからｊまでの無向パスがなく、互いの座標枠において厳格に変換することができる２つの部分埋め込みが可能である。第２に、ノード上のすべての制約が同一線形上にあり、ノードをいずれの方向制約に沿ってもスライドさせることができる。両方のケースは、それら自身を行列Ｈεのスペクトル中の複数のゼロまたは略ゼロの固有値として表す。すなわち、この近似零空間において任意の２つの固有ベクトルを回転させると、望まれていない自由度のようなものに動きが与えられ、解軌道が与えられる。
【００８２】
このようにして、固有値多重度により解の部分空間の次元が突き止められる。しかし、多重度は過剰なＤＯＦに対応しない。軌道は、様々な同位置ＤＯＦに異なるダイナミクスをそれぞれ与えるｄ個の固有ベクトルで冗長的に表現することができる。問題を特定する際に、固有のＤＯＦを特徴付けるためにいくつかの解析がさらに必要である。
【００８３】
解が多くのＤＯＦを有する場合、共に連結しているノードをクラスタ化することが有用である。直観的に、２つのノードは、両方のノードがゼロ固有値に関連する固有ベクトル中に非ゼロエントリを有する場合に共に連結されている。このような固有ベクトルはすべてＤＯＦ行列中にまとめることができる。最適なクラスタ化は低次元直交二値基底（すなわち、規定値は０あるいは１である）によって与えられる。基底はＤＯＦ行列を最もよく近似する。
【００８４】
このような基底を見つけることはＮＰハードとして既知である。したがって、問題はＤＯＦ行列の行ベクトルのスペクトルクラスタ化により、または列の独立成分解析により絶えず緩和される。クラスタ化は、動きが最も非相関化されたグループを探し、解析は完全に統計学的に独立したより強い状況を探す。
【００８５】
解における非厳格性（non-rigidity）を特定することにより、この解析は、たとえば追加の方向制約の形で、いずれのノードに制約を追加する必要があるかを判断する有用な根拠を提供する。
【００８６】
「負の長さ」を許容する問題
ε（−Ｘ）＝−ε（Ｘ）であるため、ノードからノードへの変位の所望の方向への射影（ｘｊ−ｘｉ）Ｔ＞ｄｉｊは正である場合もあれば、負である場合もある。一般に、完全に制約された問題は、射影がすべての正であるか、またはすべて負であるかいずれか一方である解のみを許容する。制約不十分な問題または矛盾する制約を有する問題は、いくつかの射影の符号が変わるＭＳＥ解を有する場合がある。すべての正の解は二次計画法（ＱＰ）を介して見つけることができる。ＱＰ問題は固有値分解Ｈε→Ｖｄｉａｇ（λ）ＶＴを用いる。非ゼロベクトルｍが固有ベクトルと混ざりｙ＝Ｖｍ、すべての長さを正に保ちながら最小二乗誤差
【００８７】
【数２１】
2005172803.tif 000023
【００８８】
を受ける。結果得られるベクトルｍを単位ノルム（unit norm）にスケーリングすることは、超球上で制約付き最適化を実行することと等価である。大きな固有値を有する固有ベクトルが使用される可能性は低いため、Ｖおよびλを切り捨てることによって、最小固有値／ベクトル対のみを考慮するように問題を制限することが有用である。これは小さなＱＰ問題である。
【００８９】
ずれたまたは回転したノードを有する問題
位置合わせ問題では、ｉ番目のノードの制約｛ｄｉｊ｝ｊが回転ＲＴｉにより摂動し、埋め込み前にこれを特定して除去する必要がある。方向制約が得られた信号に一致すると想定すると、このような摂動は埋め込みにおける誤差原因としてのみ検出可能である。
【００９０】
不都合なことに、図４に示すように、回転が誤差を生じさせないいくつかの適切埋め込み問題がある。ここでは、方向制約４０１のセット（実線矢印）は、影付きノード４０３のあらゆる回転４０２に対して十分に制約された埋め込みを有する。
【００９１】
回転が誤差を生じさせる場合であっても、位置合わせ問題は、正規直交性の制約を無視して、誤差関数が回転パラメータにおいて四次であるため略間違いなく凸ではない。しかし、摂動が小さく、誤差を生じさせる場合は、誤差関数が最適解の近傍でおおよそ凸であると予期することが妥当である。この場合、ＭＳＥ埋め込みはこの近傍で少々歪む場合がある。したがって、回転した制約から埋め込みを計算し、埋め込みから回転を計算する交互最小二乗手順が、より低い誤差埋め込みを許容する制約のセットに対して繰り返される。厳密に言えば、これは１回の繰り返しに当たり１つの回転が更新される場合にのみ保証される。小さな摂動については、誤差は、すべての回転が一まとめに更新された場合、単調減少する。
【００９２】
最適回転の解は、プロクラステス位置合わせ問題であり、すなわち正規化方向制約から行列
【００９３】
【数２２】
2005172803.tif 000024
【００９４】
を構築し、正規化埋め込み変位から行列
【００９５】
【数２３】
2005172803.tif 000025
【００９６】
を構築することである。特異値分解Ｕｄｉａｇ（ｓ）ＶＴからの最適に位置合わせされた回転
【００９７】
【数２４】
2005172803.tif 000026
【００９８】
は、ＡｉＢＴｉである。正規化により、不正確な変位長による誤差の可能性が回避される。
【００９９】
センサ網のキャリブレーション例
本発明による方法の有用性を評価するため、大学構内に亘って広く分散した何百ものセンサによって信号が得られた。信号は、画像の形であり、「Scalable extrinsic calibration of omni-directional image networks」（上記参照）においてAntone等によって処理されたものと同じであった。画像から導出されたデータセットは、カメラ対を建造物の一般的に見られる特徴に対して三角測量し、画像中の消点を解析することによって得られた３Ｄ方向制約を含む。これら三角測量だけでは、完全な、すなわち一貫したキャリブレーションは与えられない。さらに、全地球測位システム（ＧＰＳ）を使用してカメラの大まかな位置が約５ｍの精度で推定された。雑音の多いＧＰＳデータ以外では、このデータに地上較正はない。
【０１００】
図５は「グリーンビルディング」ノード構成５００を示す（Antone等における図３４を参照のこと）。このデータセットはおおよそ８０×１１５ｍの面積に広がる３２個のノードを有する。Ｃプログラムで実施される従来技術によるAntone方法は、約４５ｍｍの平均精度で全体的に一貫した位置を復元する。任意のノードの最大位置誤差は８１ｍｍである。この方法は実行におおよそ１時間かかる。
【０１０１】
本発明による方法は、Ｃコードよりも効率が悪いことが知られている１３行のＭａｔｈｌａｂコードで実施され、解を約０．５秒で取得し、誤差をおおよそ４桁、大幅に減らした（表Ａを参照のこと）。
【０１０２】
【表１】
2005172803.tif 000027
【０１０３】
図６は、Antoneの図３８の「エームズコート（Ames Court）」カメラ網６００を示す。エームズコートデータセットは、おおよそ３１５×３８０ｍに広がる１５７個のノードを有する。Antone等は、すべてのノードが適宜制約されたこの問題のノード１００個の部分集合を解く。彼らは全体位置をおおよそ４時間で復元し、平均一致は５７ｍｍであり、最大のポーズ不一致は８８ｍｍである。
【０１０４】
本発明によるスペクトル埋め込み方法は、１５７個すべてのノードの場合に問題を約３秒で解く。ここでもまた、この問題にはより多くのノードがあるにもかかわらず一致誤差が低減する。さらに、いくつかの不一致制約がある。たとえば、本データセットは、制約が残りのデータとは４３度ずれて回転したノードを含む。より顕著なことは、データセットは、Antone等の場合には問題を完全に制約されたものとした制約のいくつかを欠いている。問題は、いくつかのノードが２つ以上の線形的に独立した制約を欠き、したがってノードが方向ベクトルに沿って自由にスライドすることができるという点で制約不十分である。また、多重制約ノードの多くが誤差のない埋め込みを有さない、すなわち制約が矛盾するという点で制約過剰でもある。したがって、最初の１３個の固有ベクトルによりε＝０の埋め込みが与えられ、ここで矛盾して制約されたノードは点クラスタにまとめられ、主に制約不十分である残りのノードは空間に分散する。こういった「退化」解は結局、非自明解の自由度（ＤＯＦ）になり、これは非ゼロ誤差を有する第１の固有ベクトルである。
【０１０５】
固有ベクトルｖ１４は誤差ε＝λ１４≒７．３×１０−５を有する。この固有ベクトルは、実際のシーンの妥当な再構築において分散させる埋め込みおよび環境を通してのすべてのノードのポーズを特定する。この埋め込みは、シーンの実際の幾何学的形状に矛盾する制約も反映する。二次計画法により、正の長さを徹底することができる。
【図面の簡単な説明】
【０１０６】
【図１】本発明による方法により解析されるセンサおよび信号の図である。
【図２Ａ】グラフに整理すべき方向の図である。
【図２Ｂ】図３のベクトルを整理したグラフの図である。
【図３】本発明による方法の流れ図である。
【図４】センサの十分に制約された埋め込みの図である。
【図５】本発明により解析される第１のセンサ網である。
【図６】本発明により解析される第２のセンサ網である。
【図１】
2005172803.tif 000028
【図２Ａ】
2005172803.tif 000029
【図２Ｂ】
2005172803.tif 000030
【図３】
2005172803.tif 000031
【図４】
2005172803.tif 000032
【図５】
2005172803.tif 000033
【図６】
2005172803.tif 000034
【外国語明細書】
2005172803.tif 000035
2005172803.tif 000036
2005172803.tif 000037
2005172803.tif 000038
2005172803.tif 000039
2005172803.tif 000040
2005172803.tif 000041
2005172803.tif 000042
2005172803.tif 000043
2005172803.tif 000044
2005172803.tif 000045
2005172803.tif 000046
2005172803.tif 000047
2005172803.tif 000048
2005172803.tif 000049
2005172803.tif 000050
2005172803.tif 000051
2005172803.tif 000052
2005172803.tif 000053
2005172803.tif 000054
2005172803.tif 000055
2005172803.tif 000056
2005172803.tif 000057
2005172803.tif 000058