(57)【特許請求の範囲】
【請求項１】
シーンを再構成するシステムであって、
光パルスを前記シーンの方へ送信するように構成された光源と、
反射パルスを受信して、前記光パルスに対応する検知信号を、前記反射パルスの時間プロファイルに従って取得するように構成されたセンサの組と、
前記シーンと前記センサの組との間の光路における固定符号化開口と、
前記光源および前記センサの組に接続され、前記検知信号から、シーンモデルを用いて三次元（３Ｄ）奥行きマップとして前記シーンを再構成する方法を実行するように構成されたプロセッサと、
を備えたシーンを再構成するシステム。
【請求項２】
前記固定符号化開口は、前記光源と前記シーンとの間にある、
請求項１に記載のシステム。
【請求項３】
前記固定符号化開口は、前記シーンと前記センサの組との間にあり、前記センサの組は、光ベースの飛行時間（ＴＯＦ）奥行きセンサである、
請求項１に記載のシステム。
【請求項４】
奥行きマップのシーケンス内に３Ｄ奥行きマップごとに１つの光パルスが存在する、
請求項１に記載のシステム。
【請求項５】
前記光パルスは、広幅ビーム光パルスである、
請求項１に記載のシステム。
【請求項６】
前記光パルスは、時間においてガウス形状をとる、
請求項１に記載のシステム。
【請求項７】
前記光パルスは、パルスの符号化シーケンスを含む、
請求項１に記載のシステム。
【請求項８】
前記センサの組の配置は、ランダムであり、前記光源と同一平面上にある、
請求項１に記載のシステム。
【請求項９】
前記センサの組の配置は、等間隔アレイを形成する、
請求項１に記載のシステム。
【請求項１０】
前記センサの組の出力は、前記プロセッサにおいて、スパースな再構成方法を用いて処理される、
請求項１に記載のシステム。
【請求項１１】
前記センサの組の出力は、前記プロセッサにおいて、モデルベースのスパースな再構成方法を用いて処理される、
請求項１に記載のシステム。
【請求項１２】
前記光源は、非定常であり、非定常光源は、前記シーンを走査する、
請求項１に記載のシステム。
【請求項１３】
前記固定符号化開口のパターンは、ランダムである、
請求項１に記載のシステム。
【請求項１４】
前記パターンは、バイナリ値を有する、
請求項１１に記載のシステム。
【請求項１５】
前記パターンは、連続値を有する、
請求項１１に記載のシステム。
【請求項１６】
前記シーンモデルは、前記３Ｄ奥行きマップに対し制約を課す、
請求項１に記載のシステム。
【請求項１７】
前記３Ｄ奥行きマップに対する前記制約は、総変動（ＴＶ）制約である、
請求項１６に記載のシステム。
【請求項１８】
前記ＴＶ制約に対する投影は、ネットワークフロー問題を解くことによって求められる、
請求項１７に記載のシステム。
【請求項１９】
前記シーンモデルは、任意の方向に沿って最大で単一の反射器が存在するという制約を課す、
請求項１に記載のシステム。
【請求項２０】
シーンを再構成する方法であって、
光源によって、光パルスを前記シーンの方へ送信するステップと、
センサの組において反射パルスを受信して、前記光パルスに対応する検知信号を、前記反射パルスの時間プロファイルに従って取得するステップであって、前記シーンと前記センサの組との間の光路内に固定符号化開口が存在する、ステップと、
前記検知信号を処理して、シーンモデルを用いて前記シーンを三次元（３Ｄ）奥行きマップとして再構成するステップと、
を備えたシーンを再構成する方法。
【請求項２１】
前記光パルスが前記光源から前記シーンに進み、前記センサの組に戻る距離は、パルス遅延、すなわち光ベースの飛行時間（ＴＯＦ）であり、前記ＴＯＦは、センサ面からの距離、すなわち奥行きと同等の時間を有するように構成される
請求項１に記載のシステム。
【請求項２２】
シーンを再構成する方法であって、
光源によって、時系列のフレームごとに光パルスを前記シーンの方へ送信するステップであって、プロセッサは前記光源によって送信される前記パルスのタイミングを制御する、ステップと、
前記光源と平面になるように配置された飛行時間（ＴＯＦ）センサの組において反射パルスを受信して、前記光パルスに対応する検知信号を、前記反射パルスの時間プロファイルに従って取得するステップであって、前記シーンと前記ＴＯＦセンサの組との間の光路内に固定符号化開口が存在する、ステップと、
前記検知信号を処理して、シーンモデルを用いて前記シーンを三次元（３Ｄ）奥行きマップとして再構成するステップと、
を備えたシーンを再構成する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、光パルスを用いてシーンを再構成することに関し、より詳細には、シーンを三次元（３Ｄ）奥行きマップとして再構成することに関する。
【背景技術】
【０００２】
圧縮センシング
圧縮センシング（ＣＳ）は、取得した信号の次元によって示されるよりも少ない線形測定値を用いる。取得レートを低減するために、ＣＳ再構成法は、信号の構造を利用する。構造を捕捉するために、最も一般的に用いられる信号モデルはスパース性である。
【０００３】
本明細書において用いられるとき、スパースは信号処理分野においてよく知られた用語であり、不定関係詞ではない。「スパース」近似は、高次元の測定データおよび取得行列を所与とした連立一次方程式を満たす、スパースベクトル、すなわち、ほとんどの係数がゼロに等しいかまたは概ねゼロに等しいベクトルを推定する。
【０００４】
ＣＳに基づく取得システムは以下のようにモデル化することができる。
【数１】
0006456269.tif 000002
ここで、Ａ（．）は線形関数であり、ｓは、或る適切な信号空間内にあり、ｒは測定空間内にある。測定空間は信号空間よりもはるかに低い次元を有する。モデルに依拠する、低コヒーレンス、制限された等長特性等の、Ａ（．）の複数の可能な特性によって、適切な方法を用いて再構成が可能であることが保証される。
【０００５】
ＣＳは多くの撮像システムにおける適用に成功し、通常、取得される信号ｓは、
【数２】
0006456269.tif 000003
における２Ｄ画像である。
【０００６】
圧縮センシング手法を用いることにより、ピクセル数ＮｘＮｙの僅か１０％の測定値で画像を取得することができることが示された。これらの進歩は、電荷結合素子および金属酸化膜半導体センサ技術が測定を極度に安価にし、医用撮像、微光撮像、ハイパースペクトル撮像および奥行き検知等の他の様式に大きな影響を与えた従来の可視光撮像には関連していない。しかしながら、これらの進歩は、「飛行時間型」（ＴＯＦ）の光センサまたはレーダセンサ等の複雑でコストの高いセンサに依存する撮像システムにとって重大である。
【０００７】
モデルベースの圧縮センシング
モデルベースのＣＳフレームワークは、多数の信号モデルを開発し、ＣＳ取得への適性を特徴付けることへの一般的な手法を提供する。このフレームワークの下のモデルは、信号サポートに制約を課すことによって生成される。基本動作は、モデルに対するサポート制約を満たす信号の組への一般信号の投影である。そのような投影を計算することができる限り、圧縮サンプリングマッチング追跡（ＣｏＳａＭＰ）および反復ハード閾値処理（ＩＨＴ）等の一般的な貪欲ＣＳ再構成方法を変更して、モデルにおける信号を再構成することができる。さらに、異なる近似特性を有する一対の近似投影が、厳密な投影ではなく正確な再構成を保証するのに十分であることが示された。非特許文献１を参照されたい。
【０００８】
１つの信号モデルである、近似耐性モデルベースの圧縮センシングは、２Ｄの地震学的（ｓｅｉｓｍｉｃ）撮像を用いて測定される信号によって動機付けられる。そのモデルによる信号
【数３】
0006456269.tif 000004
は、Ｎ個の行およびＴ個の列を有する行列である。信号の各行はＳ個の非ゼロエントリしか有さず、これらは上または下の行のＳ個の非ゼロエントリに空間的に近接している。これは、信号の後続の行のサポート間のアースムーバ距離（ＥＭＤ）を制約することによって強制される。近似耐性モデル下の投影は、一連のネットワークフロー問題を解決することによって行われる。
【０００９】
光検知
光検知は、光信号を用いてシーンを照明し、反射光を解析することによってシーンへの距離を測定する。１つの光検知技法、例えば光レーダ（Ｌｉｄａｒ）を、地球科学、遠隔検知、航空機レーザマッピング（ＡＬＳＭ）、レーザ高度測定、等高線マッピングおよび車両ナビゲーション等の用途で用いることができる。
【００１０】
従来の高解像度、高フレームレートの光ベースのシステムは、通常、精密ＴＯＦセンサの高価なアレイを用い、定常レーザによって送信される単一のパルスでシーンを照明する。代替的に、フレームレートが低減することと引き換えに、レーザはシーンを走査する。同じくシーンを走査することができる、より小さなセンサアレイが反射を取得する。結果として得られるシステムにより、コストが大幅に下がるが、機械部品の使用が必要となり、これは故障を起こしやすく、モバイル用途では厄介である。
【００１１】
圧縮センシングは、低減された検知コストに起因する計算能力における大きな利得を利用して、複雑な信号モデルおよび再構成方法を可能にし、これによって、センサ複雑度を低減することを可能にする。例えば、いくつかの圧縮奥行きセンシングシステムは、空間光変調器と組み合わされた単一のセンサと、シーンを照明する複数のパルスとを用いる。
【００１２】
空間光変調器を用いて、全てのパルスとともに変化する可変符号化開口が実施される。一方、これによって、これらのシステムが静的シーンに制限される。非特許文献２、非特許文献３および非特許文献４、並びに特許文献１を参照されたい。さらに、空間光変調器（ＳＬＭ）は比較的高価であり、所望の分解能に依拠して、例えば１０００＄以上である。Ｈｏｌｏｅｙｅ（商標）またはＴｅｘａｓ  Ｉｎｓｔｒｕｍｅｎｔｓ  ＤＬＰ（商標）製品を参照されたい。
【００１３】
Ｓ＝１の場合、上記の近似耐性モデルの制約付きバージョンは、光パルスを用いた２Ｄ撮像（１つの空間次元および１つの奥行き次元）のための良好なモデルである。なぜなら、このモデルは、奥行きマップの１Ｄの総変動を最小にするためである。一方、モデルを３Ｄ体積、すなわち信号
【数４】
0006456269.tif 000005
（２つの空間次元および１つの空間次元）に拡張することは、不都合ながら自明でない。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】米国特許出願公開第２０１３／００８８７２６号
【非特許文献】
【００１５】
【非特許文献１】Ｈｅｇｄｅ他「Ａｐｐｒｏｘｉｍａｔｉｏｎ−ｔｏｌｅｒａｎｔ  ｍｏｄｅｌ−ｂａｓｅｄ  ｃｏｍｐｒｅｓｓｉｖｅ  ｓｅｎｓｉｎｇ」Ｐｒｏｃ．  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｄｉｓｃｒｅｔｅ  Ａｌｇｏｒｉｔｈｍｓ  （ＳＯＤＡ）．  ＳＩＡＭ，  ｐｐ．  １５４４−１５６１，  Ｊａｎｕａｒｙ  ２０１４
【非特許文献２】Ｈｏｗｌａｎｄ他「Ｃｏｍｐｒｅｓｓｉｖｅ  Ｓｅｎｓｉｎｇ  Ｌｉｄａｒ  ｆｏｒ  ３Ｄ  ｉｍａｇｉｎｇ」ＣＬＥＯ：  Ｓｃｉｅｎｃｅ  ａｎｄ  Ｉｎｎｏｖａｔｉｏｎｓ．  Ｏｐｔｉｃａｌ  Ｓｏｃｉｅｔｙ  ｏｆ  Ａｍｅｒｉｃａ，  ２０１１，  ＣＭＧ３
【非特許文献３】Ｋｉｒｍａｎｉ他「Ｅｘｐｌｏｉｔｉｎｇ  ｓｐａｒｓｉｔｙ  ｉｎ  ｔｉｍｅ−ｏｆ−ｆｌｉｇｈｔ  ｒａｎｇｅ  ａｃｑｕｉｓｉｔｉｏｎ  ｕｓｉｎｇ  ａ  ｓｉｎｇｌｅ  ｔｉｍｅ−ｒｅｓｏｌｖｅｄ  ｓｅｎｓｏｒ」Ｏｐｔ．  Ｅｘｐｒｅｓｓ，  ｖｏｌ．  １９，  ｎｏ．  ２２，  ｐｐ．  ２１４８５−２１５０７，  Ｏｃｔ  ２０１１
【非特許文献４】Ｋｉｒｍａｎｉ他「ＣｏＤＡＣ：  ａ  ｃｏｍｐｒｅｓｓｉｖｅ  ｄｅｐｔｈ  ａｃｑｕｉｓｉｔｉｏｎ  ｃａｍｅｒａ  ｆｒａｍｅｗｏｒｋ」ＩＥＥＥ  Ｉｎｔ．  Ｃｏｎｆ．  Ａｃｏｕｓｔｉｃｓ，  Ｓｐｅｅｃｈ  ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ  （ＩＣＡＳＳＰ）．  ＩＥＥＥ，  ２０１２，  ｐｐ．  ５４２５−５４２８
【発明の概要】
【００１６】
光検知コンポーネントの持続的改善および信号取得理論における近年の進展により、奥行き検知システムのコストを低減し、機能を高める機会がもたらされている。本発明の実施形態は、従来のシステムと比較して、固定符号化開口（マスク）を用いて必要なセンサ数を大幅に低減する新規の奥行き検知システムおよび方法を提供する。利点として、マスクは任意の透明材料の上に安価にプリントすることができる。
【００１７】
実施形態は、多岐にわたる奥行き検知システムを特徴とするモデルベースの圧縮センシングに基づくモデル化および再構成のフレームワークも提供する。実験データは、検知品質に対する無視できる程度の影響で、センサ数を８５％よりも大きく低減することが可能であることを示している。
【００１８】
本発明の主な寄与は、
・光ベースの飛行時間（ＴＯＦ）奥行きセンサのためのリアルタイム圧縮ハードウェアアーキテクチャと、
・数の奥行き検知システムアーキテクチャを特徴付ける非常に一般的なシステムモデルと、
・構成を改善するために奥行きシーンの低変動（ＴＶ）を利用するモデルベースの圧縮センシング（ＣＳ）再構成方法と、
を含む。
【００１９】
従来技術と対照的に、実施形態は少数のセンサおよび固定符号化開口を用いる。開口は、空間光変調器（ＳＬＭ）と比較して非常に安価なコンポーネントである。コードは変化しないので、本発明の１つの実施形態は、フレーム、すなわち奥行きマップのシーケンスにおける奥行きマップあたり単一のパルス送信のみを必要とする。これはコードを搬送する場合もしない場合もある。このため、はるかに高価な単一パルスシステムと同等のフレームレートを、大幅に低いコストで達成することができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施形態による、光検知を用いるシーン再構成システムおよびシーン再構成方法の概略図である。
【図２】本発明の別の実施形態による、光検知を用いるシーン再構成システムの概略図である。
【図３】本発明の実施形態による、スパースシーン再構成方法の流れ図である。
【図４】本発明によるモデルベースのＣｏＳａＭＰ再構成方法の擬似コードのブロック図である。
【図５】本発明によるモデルベースのＩＨＴ  ＣｏＳａＭＰ再構成方法の擬似コードのブロック図である。
【発明を実施するための形態】
【００２１】
本発明の実施形態は、光検知および固定符号化開口を用いてシーンを再構成するための方法およびシステムを提供する。
【００２２】
光検知
システムアーキテクチャ
図１に示すように、固定光源１１０、例えばレーザが、シーン１００から取得されるフレームごとに光パルスを送信する。レンズはパルスを広幅ビームパルス１１１にする。広幅ビームパルスを用いることによって、シーンは走査される必要がない。パルスは、例えば、時間においてガウス形状１１３をとり得る。代替的に、パルスの符号化シーケンス１１４を用いることができる。
【００２３】
反射器である各シーン点１０２からの反射パルス１１２は、レンズ１２０を通過する。レンズ１２０は、反射パルスを、光源と平面になるように配置された１組のセンサ１４０に分散する。このようにして、総距離は単に２ｄとなる。分散されたパルスは、光源とシーンとの間の光路内のマスクの形態の固定符号化開口１３０を通る。マスクは、透明材料、例えば酢酸シート上に安価にプリントすることができる。マスクは、分散されたパルスを空間的に変調する。
【００２４】
１つの実施形態では、センサの配置はランダムにすることができる。別の実施形態では、センサは等間隔アレイとして配置することができる。特に、光学飛行時間（ＴＯＦ）センサのコストが大きいときのこれらの実施形態の１つの利点は、検知品質を維持しながら、必要とされるセンサ数が、従来のシステムと比較して約８５％低減されることである。
【００２５】
１組のセンサの出力３０１は、プロセッサ１５０において、スパース再構成方法３００によって処理され、シーンモデルを用いて奥行きマップ１０１の形態で再構成されたシーンが得られる。プロセッサは、光源１１０によって送信されるパルスのタイミングも制御することができる（１５１）。
【００２６】
図２は、システムの代替的な構造を示す。この場合、マスク１３０は光源とシーン１００との間の光学経路内にある。この実施形態では、シーンは非定常光源１１０によって走査され（１１５）、組は１つのセンサ１４０しか有しない。光源がシーンを走査するとき、光源は、走査経路１１５の各位置において１つのパルスを、符号化開口を通してシーンに送信する。通常、固定符号化開口は、光源とセンサの組との間の光路内にある。
【００２７】
さらに、または代替的に、センサは、シーンを走査する間、非定常とすることができる。代替的な実施形態は、２つのアーキテクチャーを組み合わせて、前に固定符号化開口を有する走査レーザと、有しないレーザとの双方を用いる。これらのレーザは、反射の戻り経路における、同じコードまたは異なるコードを用いる別の固定符号化開口の後ろの複数のセンサと組み合わされる。
【００２８】
再構成方法
図３は、本発明の実施形態による再構成方法を示す。１つの実施形態（ＣｏＳａＭＰ）について、ステップ１〜１０のための擬似コードが図４に示されている。代替的な実施形態（ＩＨＴ）について，ステップ１〜９のための擬似コードが図５に示されている。ステップは、推定される信号が奥行きマップ１０１に収束するまで反復する。擬似コードにおいて用いられる変数を本明細書において説明する。
【００２９】
最初に、信号推定値がゼロに設定される（３１０）（ステップ１）。入力データは、１組のセンサ１４０によって取得された信号の行列の形態をとる。入力データが信号推定値とどの程度一致しないかを記述する残余が、信号推定および入力データ（信号）から求められる（３２０）（ステップ４〜６）。
【００３０】
次に、信号推定値が、現在の信号推定値、信号モデルおよび残余を用いて更新される（３３０）。再構成手順に依拠して、モデルはこのステップにおいて用いられる場合も用いられない場合もある。
【００３１】
次に、ステップ３４０において、シーンモデル２１０を強制することによって信号推定値が更新される。プロセスは、３２０から収束３５０まで繰り返される。１つの実施形態では、シーンモデルは、任意の方向に沿って最大で単一の反射器が存在するという制約を課す。
【００３２】
本方法の実施形態は、Ｋ項トランケーションステップに頼る。このステップは、様々な実施形態において様々な形態をとることができる。例えば、トランケーションステップは、当該技術分野において知られているような単純なＫスパース近似とすることもできるし、米国特許出願第１３／４０５，５０４号に記載されているように、全ての空間方向に沿った単一の反射器に関連する大きさ係数における最大のものの選択とすることもできる。さらに、または代替的に、以下で説明するようにグラフカットの定式を用いることができる。
【００３３】
飛行時間
反射パルスの検知は、距離２ｄに起因して、パルスが送信される時間から遅延するので、奥行きマップの再構成は飛行時間（ＴＯＦ）の原理に基づく。遅延は、シーン内の各点１０２への距離または各点１０２の奥行きに対応する。
【００３４】
従来のシステムは、各方向からの反射パルスを注意深く分離および検知してＴＯＦを求め、奥行きマップ１０１内の正しい場所に遅延を割り当てなければならない。
【００３５】
対照的に、本発明では圧縮センシング（ＣＳ）の原理を用い、全ての方向における反射パルスを意図的に混合してサンプリング負荷を低減する。したがって、本発明では、混合を分離して、シーン内の各点に正しい奥行き値を割り当てる計算方法に頼る。
【００３６】
例えば、バイナリパターンに従って光をブロックするマスクを用いて固定符号化開口を実装することができる。１つの実施形態では、パターンはランダムである。パターンが範囲［０，１］において連続値を有しない符号化開口も可能である。レンズおよび符号化開口の組み合わせによって、各方向から受信した反射パルスを混合し、１組のセンサに混合パルスを投影する。各センサは、開口コードによって決まる異なる混合を受信する。このため、各センサによって取得される信号は、センサによって受信される反射パルスの混合である。これらの混合を用いてシーンを再構成する。
【００３７】
代替的な実施形態では、符号化開口を有するレーザがシーンを走査するにつれ、単一のセンサは異なる混合を受信する。レーザの走査経路の全ての点において、シーンは異なる形で照明され、したがって、センサによって取得される各反射はシーンの異なる混合である。
【００３８】
信号モデル
システムをモデル化するために、検知面から距離ｄにある単一反射シーン点から開始し、符号化開口がないと仮定する。都合上、光源１１０がセンサと同一平面にあると仮定するが、この仮定は自明的に緩和することができる。このため、パルスが光源から反射シーン点に進み、センサに戻る距離は２ｄであり、パルス遅延、すなわちＴＯＦ、τ＝２ｄ／ｃに対応する。ここで、ｃは媒体内の光速である。この対応関係を用いると、時間はセンサ面からの距離、すなわち奥行きと同等である。本明細書では、距離および奥行きを交換可能に用いる。
【００３９】
２つの空間方向、すなわち、センサ面に対する横方向と、時間または遅延と呼ばれ、センサ面に対し直交する１つの奥行き方向とを含む３Ｄシーンを考える。このため、取得されるシーンは、関数ｓｘ，ｙ，ｔによって表すことができ、ここで、ｓは点（ｘ，ｙ，ｔ）におけるシーンの反射率を表す。点からの反射がない場合、対応する反射率は０である。
【００４０】
透明性のないランバート面を仮定する。これは、任意の（ｘ，ｙ）対について、非ゼロ反射率を有する奥行きｔが１つしか存在しないことを示す。換言すれば、（ｘ，ｙ，ｔ）からの反射がある場合、そのロケーションと検知面との間、すなわち反射器の前に反射器が存在しない。さらに、同じ（ｘ，ｙ）対についてその点の後ろのいかなる反射器にも光が到達せず、したがって、それらの反射率もゼロである。この制約は、コヒーレントな検知システムの文脈において、ｓに対する奥行き制約である。有効なシーン信号ｓはこの奥行き制約を満たすべきである。
【００４１】
座標（ｘ，ｙ）におけるシーンの奥行き、および同じ座標についての反射率（アルベド）マップａｘ，ｙとを表す奥行きマップｄｘ，ｙを所与として、シーンは以下によって表すことができる。
【数５】
0006456269.tif 000006
ここで、δｔはディラックインパルス関数である。奥行き制約を満たす任意のシーンについて、奥行きマップおよびアルベドマップを抽出することは自明である。換言すれば、３Ｄシーンは２Ｄ奥行きマップおよび２Ｄアルベドマップに対応する。同様に、２Ｄ（１つの空間および１つの奥行き寸法）シーンは１Ｄ奥行きマップおよび１Ｄアルベドマップに対応する。
【００４２】
取得モデル
ｐｔを用いて、シーン１００によって反射される伝達されたパルス１１１またはパルスシーケンスを表す。ピンホール開口が存在すると仮定すると、ロケーション（ｘ，ｙ）の受信信号は以下となる。
【数６】
0006456269.tif 000007
ここで、
【数７】
0006456269.tif 000008
は時間方向に沿った線形畳み込みを表す。空間コードｍｘ，ｙを有する符号化開口１３０は、反射パルスの混合をもたらす。これは、マスクを用いた
【数８】
0006456269.tif 000009
の空間的畳み込みであることを示すことができる。このため、センサ面における受信光束は、
【数９】
0006456269.tif 000010
である。
【００４３】
この信号は、ｍ＝１，．．．，Ｍによってインデックス付けされたＭ個のセンサによって検知される。各センサはロケーション（ｘｍ，ｙｍ）に位置決めされる。各センサは、センサ面において光束をサンプリングし、時間において
【数１０】
0006456269.tif 000011
をサンプリングする。
【００４４】
シーンを
【数１１】
0006456269.tif 000012
に離散化する。ここで、Ｎｘ、Ｎｙは取得される空間ピクセル数であるか、またはシステムの所望の分解能であり、Ｎｔは時間サンプル数である。離散化は、シーン内の各反射器が概ね平坦でありかつピクセルのエリアにわたってセンサ面に対し平行であると推定することができるようにされ、それによって離散表現において奥行き制約が保持される。この離散化は、離散化２Ｄ奥行きマップ
【数１２】
0006456269.tif 000013
も示し、これも離散値ｄｘ，ｙ∈｛１，．．．，Ｎｔ｝をとる。
【００４５】
さらに、サンプリング時間は、伝送パルスのナイキストレートよりも高いレートである。同様に、パルス、符号化開口マスクおよび受信信号を離散化し、パルスおよびマスクパターンを用いた畳み込みを離散時間において表現することができるようにする。
【００４６】
センサｍにおける離散化された受信信号
【数１３】
0006456269.tif 000014
の線形結合は、一連のより単純な線形変換として分解することができる。
【数１４】
0006456269.tif 000015
ここで、Ｐ、ＭおよびＳはそれぞれ、パルス、符号化開口のマスクおよびセンサによる光場のサンプリングに起因した線形変換を示す。それらの成分Ａは、受信信号ｒへのシーンｓの順方向線形変換マッピングである。
【００４７】
特定のモデルが図１の実施形態、すなわちレーザが定常であるときの実施形態を説明したが、レーザが符号化開口を用いてシーンを走査する図２の実施形態等の他の実施形態を説明する非常に類似した線形モデルを容易に導出することができる。再構成方法は、そのような線形モデルが存在することのみを必要とする。そのような線形モデルは、シーンｓを取得し、そのシーンの線形変換ｒ＝Ａ（ｓ）として受信信号ｒを表すことができる。
【００４８】
モデル実施
式（５）における線形モデルを用いる効率的な計算は最近の反復再構成方法において最重要である。このために、高速フーリエ変換（ＦＦＴ）に基づく畳み込み方法を用いて離散時間で演算子ＰおよびＭを効率的に実施することができる。
【００４９】
さらに、Ｓは単に適切な信号を選択するので、計算的に自明である。ほとんどの再構成方法に必要な随伴行列Ａ＊は、各演算子の随伴行列を逆の順序で、すなわちＡ＊（ｒ）＝Ｐ＊（Ｍ＊（Ｓ＊（ｒ）））を用いて作成することによって実施することができる。この実施はまた、式（５）において空間演算子と時間演算子との可分性を利用し、線形結合をＳ（Ｍ（Ｐ（ｓ）））＝Ｐ（Ｓ（Ｍ（ｓ）））として再編成して複雑度を単純化することができる。このため、パルス畳み込みＰは、Ｎｘ×Ｎｙ×Ｎｔ次元のオブジェクトではなくＭ×Ｎｔ次元のオブジェクトに適用され、この間ＳおよびＭの複雑度は変化しない。
【００５０】
効率的な実施態様は、メモリ要件を大幅に低減するために、奥行きマップｄおよびアルベドａ表現を用いることができる。そのような表現から順方向演算子を効率的に求めることができるが、随伴行列は、ｓ全体を記憶するための追加の一時メモリを必要とする。
【００５１】
奥行き再構成
奥行きシーン、変動およびネットワークフロー
サブサンプリングされた信号を再構成し、ノイズを低減するために、ＣＳは取得信号の構造を利用する。特に、奥行きマップは低変動（ＴＶ）ノルムを有する傾向にある。低ＴＶノルムを有する信号は概ね平坦であり、不連続性が非常に僅かであり、小さな勾配を有するエリアが非常に僅かである。
【００５２】
離散マップ
【数１５】
0006456269.tif 000016
の（ｌ１）ＴＶノルムは以下のように定義される。
【数１６】
0006456269.tif 000017
ここで、∇ｘｄは方向ｘに沿った離散勾配であり、‖・‖１は行列の要素単位のｌ１ノルムであり、すなわち以下である。
【数１７】
0006456269.tif 000018
ここで、ｙ方向も同様に定義される。
【００５３】
ＴＶノルム奥行き制約を満たすシーンを所与とすると、奥行きマップのＴＶノルムに対する追加の制約は、ｓにおける非ゼロのサポートに対する制約と等しい。特に、ｓの２つの空間的に隣接した非ゼロ要素、すなわちｎｘおよびｎｙ座標に関して空間的に隣接した非ゼロ要素も、非常に僅かな不連続性を除いて、同様の奥行き、すなわちｎｔ座標を有するべきである。しかしながら、この１対１の対応は、ｓが奥行き制約を満たすことを必要とする。一般的な密なｓはこの奥行き制約を満たさない。このためＣｏＳａＭＰおよびＩＨＴ等のモデルベースのＣＳ方法について、奥行き制約およびＴＶ制約の双方への投影が必要とされる。
【００５４】
１次元奥行きマップ問題について、すなわち、２次元シーン
【数１８】
0006456269.tif 000019
および
【数１９】
0006456269.tif 000020
について、非特許文献１によって記載されている投影が解決策を提供している。この解決策では、行列として表される２Ｄ信号が検討される。行列の各行は、Ｓ個の非ゼロのみを有し、サポート間のＥＭＤに対する所定の制約に従って、行間のこれらの非ゼロのサポートはほとんど変化しない。
【００５５】
Ｓ＝１の場合、ｓに適用されるＥＭＤ制約が、そのサポート、すなわち奥行きマップに対するＴＶ制約となることを示すことができる。制約への投影は、ネットワークフロー問題を解く一連の動的プログラムを用いて求めることができる。不都合なことに、その手法は、２Ｄ奥行きマップ、すなわち３Ｄシーンを一般化しない。これらのために、異なる定式化を用いる。
【００５６】
３Ｄシーンのために用いることができる１つの定式化が、米国特許出願第１３／４０５，５０４に記載されている。ここでは、空間位置ｘ，ｙごとに、奥行き方向に沿った奥行き係数が最大のものが選択される。これらの中から、Ｋ個の最大係数およびそれらのロケーションが選択される。本発明の１つの実施形態は、この定式化を用いることができる。一方、この定式化は、２Ｄ奥行きマップにおいて（すなわち、３Ｄシーンにおける非ゼロのサポートにおいて）低ＴＶノルム制約を強制しない。
【００５７】
この制約を強制することができる異なる定式化を次に説明する。これは、他の定式化を用いる実施形態と比較して、センサ数およびレーザ走査時間の更なる低減を可能にするので、本発明の好ましい実施形態である。
【００５８】
２Ｄ変動およびグラフカット
投影を３Ｄオブジェクトに、すなわち２Ｄ奥行きマップ一般化するために、グラフカット定式化を用いる。無向の重み付きグラフＧ＝（Ｖ，Ｅ）について、一般的なグラフカット問題を検討する。すなわち、１組の観測値Ｘを所与として、タスクは、全ての頂点ｌの共同ラベル付けにより、ラベルと観測値との間のエネルギー関数Ｅ（ｌ，Ｘ）が最小化されるように各頂点ｖ∈Ｖにラベルｌｖ∈Ｌを割り当てることである。
【００５９】
本発明の奥行き検知方法では、各頂点を、シーンの空間ロケーションｖ＝（ｎｘ，ｎｙ）を表すようにマッピングし、各ラベルは離散奥行き値
【数２０】
0006456269.tif 000021
を表す。このため、組ＶのおよびＬの濃度はそれぞれＮｘＮｙおよびＮｔである。
【００６０】
また、観測値Ｘの組をシーンｓにマッピングする。エネルギー関数を、１変数項および２変数項の和として表す。
【数２１】
0006456269.tif 000022
ここで、
【数２２】
0006456269.tif 000023
は    
【数２３】
0006456269.tif 000024
の近傍であり、すなわち、Ｎｖはグラフ内でｖ＝（ｎｘ，ｎｙ）に直接隣接する全ての頂点を含む。
【００６１】
１変数項はフィデリティー項であり、ラベル、すなわち奥行き値を用いてシーンｓから適切なデータ点を選択し、ｌ２データペナルティを課す。２変数項は、近傍組Ｎｖ内のｖのラベルと頂点のラベルとの間の平滑性制約を課す。このため、式（８）からの２変数項は奥行き値の勾配のｌ１ノルム、すなわち、ｄのＴＶノルムである。ルーディン−オッシャー−ファテミ総変動と類似して、パラメータλはデータ忠実性と平滑性とのトレードオフを表す。
【００６２】
既知である、式（８）を最小化するソルバーは、α拡張およびα−βスワップ、並びにブール手法を含む。１つの実施形態では、α拡張技法を用いる。
【００６３】
本発明のモデルベースの方法のトランケーションステップ（図４の６、８および図５の８）は、式（８）を最初に最適化して候補奥行きマップｄを得ることによってｓのＫ項トランケーションを組み込み、これは候補サポート組
【数２４】
0006456269.tif 000025
に対応する。この候補サポート組から、ｓの最大のＫ個の成分が選択され、モデルベースのＣｏＳａＭＰまたはＩＨＴの適切なステップによって用いられる。
【００６４】
対照的に、従来のトランケーションは、グラフカット解決策によって制約されないデータｓのＫ個の最大成分を単に選択する。従来のスパース性と比較して、本発明のモデルベースの閾値処理は、奥行き制約およびＴＶ制約を満たすシーンｓを生成する。
【００６５】
シーン再構成
上記で記載したような投影を所与とすると、これを再構成アルゴリズムに組み込んで、実際の奥行きマップを復元することができる。図４および図５に２つの代替的な実施形態が実証される。
【００６６】
図４において、モデルベースのＣｏＳａＭＰ（圧縮サンプリングマッチング追跡）に基づいて再構成を実行するための反復アルゴリズムが説明される。反復カウントｌおよび信号推定値
【数２５】
0006456269.tif 000026
が維持され、各反復を通じて更新される。ステップ１はこれらをゼロに初期化する。ステップ３は反復カウントを増大させる。ステップ４は、信号推定値
【数２６】
0006456269.tif 000027
とデータｒとの不一致を捕捉する残余ｕｌを計算する。ステップ５において、シーンのためのプロキシｇｌが計算される。これは、現在のシーン推定値
【数２７】
0006456269.tif 000028
におけるコスト関数の勾配でもある。ステップ６は、上記で記載したようなモデルベースのトランケーション関数を用いて、ｓｕｐｐ（ｔｒｕｎｃ（ｇｌ，Ｋ））で表されるモデルに従ってＫ個の係数にトランケートされた、プロキシのサポートを求める。代替的な実施形態は、２ＫまたはＫ／２等の異なるトランケーション長を用い得ることに留意されたい。このサポートは、
【数２８】
0006456269.tif 000029
、すなわち現在の信号推定値のサポートと一体化され、サポート候補Ｔｌが形成される。ステップ７において、サポート候補にわたって制限されたシステムを反転することによってステップ７に新たな一時信号推定値ｂｌが形成される。一時信号推定値は、ステップ８において、信号推定値
【数２９】
0006456269.tif 000030
を更新するようにトランケートされる。ステップ３〜８は、アルゴリズムが収束するまで、または有限数の反復にわたって反復される。収束は、例えばステップ４において計算される残余の大きさによって、または反復間の信号推定値
【数３０】
0006456269.tif 000031
の変化量によって測定することができる。ステップ１０において、収束後の最終信号推定値
【数３１】
0006456269.tif 000032
が返される。
【００６７】
図５において、再構成を実行するための代替的な反復アルゴリズムがモデルベースのＩＨＴ（反復ハード閾値処理）に基づいて説明される。反復カウントｌおよび信号推定値
【数３２】
0006456269.tif 000033
が維持され、各反復を通じて更新される。ステップ１はこれらを０に初期化する。ステップ３は、反復カウントを増大させる。ステップ４は、残余ｕｌを計算し、これは、信号推定値
【数３３】
0006456269.tif 000034
とデータｒとの不一致を捕捉する。ステップ５において、シーンのプロキシｇｌが計算される。これは、現在のシーン推定値
【数３４】
0006456269.tif 000035
におけるコスト関数の勾配でもある。ステップ６において、ステップサイズτを有する勾配を辿ることによって代替的な一時シーン推定値
【数３５】
0006456269.tif 000036
が形成される。ステップ７において、一時信号推定値は、信号推定値
【数３６】
0006456269.tif 000037
を更新するようにトランケートされる。ステップ３〜８は、アルゴリズムが収束するまで、または有限数の反復にわたって反復される。収束は、例えばステップ４において計算される残余の大きさによって、または反復間の信号推定値
【数３７】
0006456269.tif 000038
の変化量によって測定することができる。ステップ９において、収束後の最終信号推定値
【数３８】
0006456269.tif 000039
が返される。
【図１】
0006456269.tif 000040
【図２】
0006456269.tif 000041
【図３】
0006456269.tif 000042
【図４】
0006456269.tif 000043
【図５】
0006456269.tif 000044