(57)【特許請求の範囲】
【請求項１】
信号を再構成する方法であって、前記信号は光場を含みうるものであり、
サンプリング手順を用いて前記信号をサンプリングして、入力信号を取得することであって、前記入力信号はタイプと関連付けられることと、
前記入力信号からコンシステント集合を求めることであって、前記コンシステント集合は、前記サンプリング手順を第１の要素に適用した結果、前記入力信号が得られるような前記第１の要素を含むことと、
前記タイプに従って、ガイド集合を求めることであって、前記ガイド集合は、前記第１の要素と互いに素である第２の要素を含むことと、
再構成集合を生成することであって、前記再構成集合は第３の要素を含み、前記第３の要素は、前記第１の要素に対する前記第３の要素の第１の類似性尺度と、前記第２の要素に対する前記第３の要素の第２の類似性尺度との合計を最小化することと、
前記再構成集合上で関数を最小化する変換信号を求めることと、
前記変換信号に対する再構成信号の第３の類似性尺度が許容範囲よりも小さくなるように前記再構成信号を生成することと、
前記再構成信号をレンダリングすることと、
を備え、
前記入力信号、前記コンシステント集合、前記ガイド集合、前記変換信号、および前記再構成集合は、処理を実行するプロセッサに接続されたメモリに記憶される、
信号を再構成する方法。
【請求項２】
前記入力信号の前記タイプは、画像、画像内のパッチ、１組の画像、ビデオシーケンス、ビデオシーケンス内のパッチ、深度マップ、スペクトルマップ、深度マップのパッチ、マップのパッチ、画像関連特徴ベクトル、およびそれらの組み合わせからなる群から選択されるものを含みうるものであり、
前記ガイド集合を求めることは、フーリエ変換、コサイン変換、ウェーブレット変換、トレーニングデータセットから学習する方法、およびグラフの行列のスペクトル変換、並びにそれらの組み合わせからなる群から選択されるものを用いるものであり、
前記信号を再構成する方法は、
前記タイプに従って前記グラフを構成することと、
前記グラフおよび前記入力信号を用いて前記グラフの前記行列を求めることと、
をさらに備えるものである請求項１に記載の方法。
【請求項３】
前記入力信号はストリーミングであり、
前記再構成信号をリアルタイムで生成することをさらに備えた
請求項１に記載の方法。
【請求項４】
前記タイプ、前記コンシステント集合、および前記ガイド集合のうちの１つまたはそれらの組み合わせは、第１の組の確率分布を用いて求められ、
前記第１の組の確率分布に従った確率変数間の統計的類似性尺度を用いた第２の組の確率分布を用いて前記再構成集合を求めることをさらに備えた
請求項１に記載の方法。
【請求項５】
前記コンシステント集合および前記ガイド集合のうちの一方またはそれらの組み合わせは、１つまたは１群の第１の線形集合を含み、
前記１つまたは１群の前記第１の線形集合に従った第２の線形集合を用いて前記再構成集合を求めることをさらに備えた
請求項１に記載の方法。
【請求項６】
前記ガイド集合は、近似クリロフ部分空間、有理クリロフ部分空間、近似有理クリロフ部分空間、およびそれらの組み合わせからなる群から選択されたクリロフベースの部分空間であり、
前記クリロフベースの部分空間に従ったクリロフベースの方法を用いて前記再構成信号を求めることをさらに備えた
請求項５に記載の方法。
【請求項７】
プロジェクタ、フレーム関数、およびフィルタ関数のうちの１つまたはそれらの組み合わせを含む様々なガイド変換を用いて前記ガイド集合を求めることをさらに備えた
請求項５に記載の方法。
【請求項８】
行列関数または近似行列関数のうちの一方またはそれらの組み合わせを用いて前記フィルタ関数を近似することをさらに備え、
前記行列関数は、行列多項式、近似行列多項式、行列有理関数、近似行列有理関数、およびそれらの組み合わせからなる群を用いて求められる、
請求項７に記載の方法。
【請求項９】
距離、ノルム、セミノルム、相関、コヒーレンス、ダイバージェンス、およびメトリックのうちの１つまたはそれらの組み合わせを用いて、前記第１の類似性尺度、前記第２の類似性尺度、および前記第３の類似性尺度のうちの少なくとも１つを求めることをさらに備えた
請求項１に記載の方法。
【請求項１０】
前記第１の類似性尺度と、前記第２の類似性尺度と、パラメータとを用いて、前記第２の類似性尺度に対する前記第１の類似性尺度の比が前記関数の最小値において前記パラメータに等しくなるように前記関数を求めることをさらに備えた
請求項１に記載の方法。
【請求項１１】
前記サンプリング手順は、雑音、前記サンプリング手順によって用いられるセンサの限られた正確度、および前記入力信号の限られた精度のうちの１つまたはそれらの組み合わせに起因して前記入力信号に不正確さをもたらし、
前記再構成集合の直径に対して相対的な前記入力信号の前記不正確さのレベルを求めることと、
前記不正確さの前記レベルに比例するように前記パラメータを求めることと、
をさらに備えた請求項１０に記載の方法。
【請求項１２】
前記再構成集合は、前記コンシステント集合における第１の端点および前記ガイド集合における第２の端点を有する区間であり、
第１の連立方程式を解くことおよび前記第２の端点を前記コンシステント集合に投影することのうちの一方またはそれらの組み合わせを用いて前記第１の端点を求めることと、
第２の連立方程式を解くことおよび前記第１の端点を前記ガイド集合に投影することのうちの一方またはそれらの組み合わせを用いて前記第２の端点を求めることと、
前記第１の端点および前記第２の端点の凸線形結合として前記再構成集合を求めることと、
反復法を用いて、前記第１の連立方程式および前記第２の連立方程式のうちの一方またはそれらの組み合わせを解くことと、
をさらに備えた請求項１に記載の方法。
【請求項１３】
前記信号は音場を含みうるものであり、
前記入力信号の前記タイプは、１つまたは１組のオーディオシーケンス、オーディオシーケンス内のパッチ、オーディオスペクトルマップ、オーディオスペクトルマップのパッチ、オーディオ特徴ベクトル、およびそれらの組み合わせを含みうるものである、
請求項２に記載の方法。
【請求項１４】
信号を再構成する装置であって、前記信号は光場を含みうるものであり、
サンプリング手順を用いて前記信号をサンプリングして、入力信号を取得する少なくとも１つのセンサであって、前記入力信号はタイプと関連付けられる、少なくとも１つのセンサと、
前記入力信号と、
前記入力信号から求められたコンシステント集合であって、前記コンシステント集合は、前記サンプリング手順を前記コンシステント集合の第１の要素に適用した結果、前記入力信号が得られるような前記第１の要素を含む、コンシステント集合と、
前記タイプに従って求められる、前記第１の要素と互いに素である第２の要素のガイド集合と、
第３の要素を含む再構成集合であって、前記第３の要素は、前記第２の要素に対する前記第３の要素の第１の類似性尺度と、前記第１の要素に対する前記第３の要素の第２の類似性尺度との合計を最小化する、再構成集合と、
前記再構成集合上で関数を最小化する変換信号と、
前記変換信号に対する再構成信号の第３の類似性尺度が許容範囲よりも小さくなるような前記再構成信号と、
を記憶するメモリと、
処理を実行する、前記メモリに接続された少なくとも１つのプロセッサと、
前記再構成信号をレンダリングする少なくとも１つの出力デバイスと、
を備えた信号を再構成する装置。
【請求項１５】
前記タイプは、画像、画像内のパッチ、１組の画像、ビデオシーケンス、ビデオシーケンス内のパッチ、深度マップ、スペクトルマップ、深度マップのパッチ、マップのパッチ、画像関連特徴ベクトル、１つまたは１組のオーディオシーケンス、オーディオシーケンス内のパッチ、オーディオスペクトルマップ、オーディオスペクトルマップのパッチ、オーディオ特徴ベクトル、１組の時系列、時系列内のパッチ、時系列特徴ベクトル、およびそれらの組み合わせからなる群から選択され、
前記少なくとも１つのプロセッサは、フーリエ変換、コサイン変換、ウェーブレット変換、トレーニングデータセットから学習する方法、およびグラフの行列のスペクトル変換、並びにそれらの組み合わせからなる群から選択された手法を用いて前記ガイド集合を求め、
前記グラフは、前記入力信号の前記タイプに従って構成され、
前記グラフの前記行列は、前記グラフおよび前記入力信号を用いて求められる、
請求項１４に記載の装置。
【請求項１６】
前記入力信号はストリーミングであり、
前記再構成信号はリアルタイムで生成される、
請求項１４に記載の装置。
【請求項１７】
信号を再構成する方法であって、前記信号は、時間変化する光場、画像シーケンス、およびビデオシーケンスのうちの１つまたはそれらの組み合わせにおける物体ラベルを表し、
前記信号の初期セクションにおける種々の物体の特徴点のラベルを用いて入力信号を求めることと、
グラフおよび前記信号にわたって前記特徴点を接続する関連付けられたグラフ行列を求めることと、
前記グラフ行列に従ってタイプを求めることと、
前記入力信号から、コンシステント集合であって、前記入力信号を取得するために用いられるサンプリング手順を前記コンシステント集合の第１の要素に適用した結果、前記入力信号が得られるような前記第１の要素を含む、コンシステント集合と、
前記タイプに従って求められた、前記第１の要素と互いに素である第２の要素のガイド集合と、
第３の要素を含む再構成集合であって、前記第３の要素は、前記第２の要素に対する前記第３の要素の第１の類似性尺度と、前記第１の要素に対する前記第３の要素の第２の類似性尺度との合計を最小化する、再構成集合と、
前記再構成集合上で関数を最小化する変換信号と、
前記変換信号に対する再構成信号の第３の類似性尺度が許容範囲よりも小さくなるような前記再構成信号と、
を求めることと、
前記再構成信号を用いて、前記信号においてラベル付けされていない物体にラベルを出力することと、
を備えた信号を再構成する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、信号再構成に関し、より詳細には、サンプリングされた信号を解析すること、近似すること、雑音除去すること、および補間することに関する。
【背景技術】
【０００２】
信号再構成は、多くの信号処理アプリケーションにおいて様々な名称で用いられている。画像処理およびビデオ処理では、信号は、例えば、画像を含むことができ、再構成の目標は、例えば、超解像度で、すなわち、画像の元の解像度よりも高い解像度で画像を出力することとすることができる。同様に、オーディオ処理アプリケーションでは、信号は、オーディオシーケンスを含むことができ、再構成は、例えば、オーディオ周波数レンジを増大させるのに用いることができる。データマイニングアプリケーションでは、信号再構成は、例えば、データ完成の形で現われる。信号再構成、より詳細には、サンプリングされた信号の解析、近似、雑音除去、および補間は特に重要であり、非常に多くの特許および刊行物に記載されている。
【０００３】
特許文献１には、反復信号データシステムのサンプリングされた信号エッジの波形再構成の方法および装置が開示されている。高周波数成分を有する反復入力信号の比較的低解像度のサンプルのシーケンスが、トリガーすることなく取得され、これらの低解像度サンプルから近似の波形が求められる。次に、高速フーリエ変換が入力信号の再構成された時間記録に適用されて、各信号成分の周波数が取得される。サンプリングされた波形は、サンプリングされた成分を共通の時刻または位相を基準として重ね合わせることによって再構成される。
【０００４】
特許文献２には、不均一にサンプリングされた信号の再構成のシステムが開示されている。不均一にサンプリングされた信号は、サンプリングされた信号と、等距離サンプル周期を用いてサンプリングされた信号と不均一にサンプリングされた信号との間の振幅誤差とを含む。再構成された振幅誤差が、時間オフセットおよび不均一にサンプリングされた信号を通じて求められる。この振幅誤差は、不均一にサンプリングされた信号から差し引かれる。
【０００５】
特許文献３には、入力フィールドからの超解像度信号再構成の方法およびシステムが開示されている。この方法は、測定システムの出力フィールドに対応する測定データを提供することと、入力フィールドのスパース性についてのデータおよび測定システムの効果的な応答関数についてのデータを提供することと、既知のデータに基づいて測定データを処理することとを含む。この処理は、最初に、入力フィールドのスパース性を示す集合および効果的な応答関数とともに、測定データの関数としてのスパースベクトルを求める。次に、このスパースベクトルが、入力情報を再構成するのに用いられる。
【０００６】
特許文献４は、シーン光を検知して、サンプリングされた画像データを３つの色で提供する方法を開示している。このサンプリングされた画像データは、続いて、サンプリングされていない色について補間され、その後、減算されて、２つの色差信号が提供される。これらの２つの色差信号は、次に、それぞれメディアンフィルタリングされ、その後、元のサンプリングされた画像データと併せて再構成され、再構成された画像内の色ぶちが削減される。
【０００７】
特許文献５には、リアルタイム超解像度方法が開示されている。その方法では、制約付き全体最小二乗法の超解像度技法が用いられて、より高解像度のスペクトル解析および出力を得るために入力信号のサンプルが拡張される。
【０００８】
特許文献６には、ヒルベルト変換を用いた再構成方法が開示されている。この方法は、スキャンされた物体のコンピュータートモグラフィー（ＣＴ）画像内の再構成の或る時点における画像データ値を求める。これは、取得された投影データを、１次元ランプフィルタを用いてフィルタリングして、ランプフィルタリングされたデータを生成し、このランプフィルタリングされたデータに逆投影演算子を逆距離加重法とともに適用して、ＣＴ画像内の再構成のその時点における画像データ値を生成することで行われる。
【０００９】
特許文献７には、不明瞭なアンダーサンプリングされた時間領域データからのスパース周波数スペクトルの再構成の方法が開示されている。この方法は、高帯域幅アナログ信号をデジタル信号に変換する。この方法は、高帯域幅アナログ信号を、遅延の増大を伴う並列チャネルに分割する。各チャネルは、次に、高帯域幅信号よりも低いサブナイキスト周波数でサンプリングされる。これらのチャネルは、次に、高帯域幅信号のナイキスト周波数でアップサンプリングされ、組み合わされて、高帯域幅アナログ信号を表すデジタル信号が生成される。
【００１０】
特許文献８には、量子化に起因した不正確な測定値から信号を再構成する方法が開示されている。非線形フィルタリングが、量子化された信号に適用されて、量子変化をそれらのそれぞれの時間間隔にわたって分散させ、例えば、より平滑な再構成信号を提供する。量子化限界（ｑｕａｎｔｉｚａｔｉｏｎ  ｂｏｕｎｄｓ）が、微細な信号点ごとに実施されて、原信号と関連付けられた、限られた不確実性内にある再構成信号が確保される。
【００１１】
特許文献９は、ささやき声を含む入力信号から音声を再構成する方法を開示している。この方法は、入力信号を解析して、この入力信号の表現を形成し、この表現は、次に、信号のスペクトルを調整するように変更される。この変更によって、スペクトルにおける少なくとも１つのフォルマントの帯域幅が変化し、この少なくとも１つのフォルマントの所定のスペクトルエネルギー分布および振幅が達成される。
【００１２】
サンプリング理論は、超解像度画像の生成、生物医学撮像の処理、音響信号のサンプリングレート変換、およびグラフベースの信号補間等の信号処理システムおよび信号処理アプリケーションに重要である。
【００１３】
１つの例は、時間領域において取得されたサンプルからの帯域制限された信号の再構成である。これについては、非特許文献１を参照されたい。シャノン・ハートレー定理の幾つかの拡張が、適切な部分空間上への投影のより広い意味でサンプリングを考察し、次いで、特定のアプリケーションに従ってそれらの部分空間を選択することに基づいて開発されている。これについては、非特許文献２を参照されたい。
【００１４】
より近時においては、グラフのノードの部分集合上の信号サンプルからの、グラフラプラシアンの固有値に関して帯域制限されたグラフ上の信号の再構成が人気を得ている。これについては、例えば、非特許文献３および非特許文献４を参照されたい。
【００１５】
再構成の１つの課題は、未知の原信号の再構成信号を原信号のサンプルに基づいて求めることである。ここで、サンプルは、通常、サンプリング部分空間に属する。これについては、非特許文献５を参照されたい。再構成信号の検索は、一般に部分空間において行われる。この部分空間をガイド部分空間（ｇｕｉｄｉｎｇ  ｓｕｂｓｐａｃｅ）と呼ぶことにする。未知の原信号と再構成信号との間の距離として表される誤差を最小化することが多くの場合望まれる。
【００１６】
１つの従来技術の方法では、コンシステント（ｃｏｎｓｉｓｔｅｎｔ：無矛盾）再構成方法が開示されている。コンシステント条件によって、再構成信号は、常に、サンプリング部分空間において同じサンプルを原信号として与えることが確保される。加えて、傾斜プロジェクタ（ｏｂｌｉｑｕｅ  ｐｒｏｊｅｃｔｏｒ：傾斜投影線）を解決法に用いることができるように、ガイド部分空間とサンプリング部分空間の補空間（ｃｏｍｐｌｅｍｅｎｔ）との直和が信号空間に等しいことが必要とされる。これについては、非特許文献６および非特許文献７を参照されたい。ガイド部分空間とサンプリング部分空間の補空間との直和が信号空間に等しいという要件は、アプリケーションによっては過度に制限的であるか、または不利である可能性があり、例えば、この要件は、大きなノルムを有する傾斜プロジェクタをもたらす可能性があり、その結果、再構成方法は、信号雑音の影響を非常に受けやすい不安定なものとなる。
【００１７】
この要件を回避するために、より一般的な制約付き再構成が、再構成信号からサンプルコンシステント再構成平面までの距離を最小化する。この距離が０である場合、この再構成はサンプルコンシステントであり、そうでない場合、この再構成は、一般化された再構成を表す。ほとんどの実際的なアプリケーションでは、全ての可能なコンシステント再構成信号は、ガイド部分空間とは互いに素である。それらの一般化された再構成方法は、再構成信号をガイド部分空間内に置き、この再構成信号をサンプルインコンシステントにする。これについては、非特許文献７を参照されたい。
【００１８】
狭帯域オーディオ信号の帯域幅拡張の異なるアプリケーション分野では、再構成方法は、再構成信号をコンシステントにする。これについては、非特許文献８を参照されたい。Ｂｅｒｇｅｒ他のように再構成信号をガイド部分空間内に置くこととは異なる。
【００１９】
従来技術の信号再構成方法の重要な限界のうちの１つは、実際には、ガイド部分空間がサンプルコンシステント信号を含まない特に重要な場合において、再構成信号をガイド部分空間内に強制的に入れるべきか否か、または再構成信号がサンプルコンシステントであるべきか否かがアプリオリに明らかでない場合があるということである。従来技術は、例えば、サンプリングおよびガイドの双方の手順が等しく信頼可能とすることができる状況をカバーしていない。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】米国特許第４，９２８，２５１号
【特許文献２】米国特許第７，４０３，８７５号
【特許文献３】米国特許出願公開第２０１２０１８８３６８号
【特許文献４】米国特許第４，７７４，５６５号
【特許文献５】米国特許第５，７４８，５０７号
【特許文献６】米国特許第７，４２４，０８８号
【特許文献７】米国特許出願公開第２０１４０２３２５８１号
【特許文献８】米国特許第５，５８７，７１１号
【特許文献９】米国特許出願公開第２０１２０１５０５４４号
【非特許文献】
【００２１】
【非特許文献１】Ｕｎｓｅｒ他「Ａ  ｇｅｎｅｒａｌ  ｓａｍｐｌｉｎｇ  ｔｈｅｏｒｙ  ｆｏｒ  ｎｏｎ−ｉｄｅａｌ  ａｃｑｕｉｓｉｔｉｏｎ  ｄｅｖｉｃｅｓ」（Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ，  ４２（１１）：２９１５−２９２５，  １９９４）
【非特許文献２】Ｅｌｄａｒ他「Ｂｅｙｏｎｄ  ｂａｎｄｌｉｍｉｔｅｄ  ｓａｍｐｌｉｎｇ」（Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｍａｇａｚｉｎｅ，  ＩＥＥＥ，  ２６（３）：４８−６８，  ２００９）
【非特許文献３】Ｎａｒａｎｇ他「Ｓｉｇｎａｌ  ｐｒｏｃｅｓｓｉｎｇ  ｔｅｃｈｎｉｑｕｅｓ  ｆｏｒ  ｉｎｔｅｒｐｏｌａｔｉｏｎ  ｉｎ  ｇｒａｐｈ  ｓｔｒｕｃｔｕｒｅｄ  ｄａｔａ」（ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｃｏｕｓｔｉｃｓ，  Ｓｐｅｅｃｈ  ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ  （ＩＣＡＳＳＰ），  ｐｐ．  ５４４５−５４４９，  ２０１３）
【非特許文献４】Ｎａｒａｎｇ他「Ｌｏｃａｌｉｚｅｄ  ｉｔｅｒａｔｉｖｅ  ｍｅｔｈｏｄｓ  ｆｏｒ  ｉｎｔｅｒｐｏｌａｔｉｏｎ  ｉｎ  ｇｒａｐｈ  ｓｔｒｕｃｔｕｒｅｄ  ｄａｔａ」（Ｇｌｏｂａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｓｉｇｎａｌ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  （ＧｌｏｂａｌＳＩＰ），  ２０１３  ＩＥＥＥ，  ｐａｇｅｓ  ４９１−４９４，  Ｄｅｃ  ２０１３）
【非特許文献５】Ｅｌｄａｒ他「Ｂｅｙｏｎｄ  ｂａｎｄｌｉｍｉｔｅｄ  ｓａｍｐｌｉｎｇ」（Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｍａｇａｚｉｎｅ，  ＩＥＥＥ，  ２６（３）：４８−６８，  ２００９）
【非特許文献６】Ｅｌｄａｒ「Ｓａｍｐｌｉｎｇ  ｗｉｔｈ  ａｒｂｉｔｒａｒｙ  ｓａｍｐｌｉｎｇ  ａｎｄ  ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ  ｓｐａｃｅｓ  ａｎｄ  ｏｂｌｉｑｕｅ  ｄｕａｌ  ｆｒａｍｅ  ｖｅｃｔｏｒｓ」（Ｊｏｕｒｎａｌ  ｏｆ  Ｆｏｕｒｉｅｒ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ，  ９（１）：７７−９６，  ２００３）
【非特許文献７】Ｂｅｒｇｅｒ他「Ｓａｍｐｌｉｎｇ  ａｎｄ  ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ  ｉｎ  ｄｉｆｆｅｒｅｎｔ  ｓｕｂｓｐａｃｅｓ  ｂｙ  ｕｓｉｎｇ  ｏｂｌｉｑｕｅ  ｐｒｏｊｅｃｔｉｏｎｓ」（Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ａｒＸｉｖ：１３１２．１７１７，  Ｄｅｃｅｍｂｅｒ  ２０１３）
【非特許文献８】Ｂａｎｓａｌ他「Ｂａｎｄｗｉｄｔｈ  ｅｘｐａｎｓｉｏｎ  ｏｆ  ｎａｒｒｏｗｂａｎｄ  ｓｐｅｅｃｈ  ｕｓｉｎｇ  ｎｏｎ−ｎｅｇａｔｉｖｅ  ｍａｔｒｉｘ  ｆａｃｔｏｒｉｚａｔｉｏｎ」（Ｎｉｎｔｈ  Ｅｕｒｏｐｅａｎ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｓｐｅｅｃｈ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ，  ２００５）
【発明の概要】
【００２２】
本発明の実施の形態は、サンプリング手順を用いて取得された入力信号から或る特定のタイプの信号を再構成する方法およびシステムを提供する。サンプリング手順をコンシステント集合（ｃｏｎｓｉｓｔｅｎｔ  ｓｅｔ）の第１の要素に適用した結果、入力信号が得られるような当該第１の要素を含むコンシステント集合が、入力信号から求められる。
【００２３】
サンプリングは、通常、情報の喪失を伴う。したがって、一般に未知の原信号を回復するには、仮定が必要とされる。１つのそのような仮定は、信号が閉ガイド集合（ｃｌｏｓｅｄ  ｇｕｉｄｉｎｇ  ｓｅｔ）に属することとすることができる。コンシステント集合の第１の要素と互いに素である第２の要素を含むガイド集合が、信号のタイプに従って求められる。信号のガイド集合は、望ましい再構成信号挙動のモデルまたは他の形態の記述を用いて求めることができ、例えば、トレーニングデータセットから学習することができる。固有（ｎａｔｕｒａｌ）スペクトル特性を有する信号の場合、スペクトル変換、例えば、フーリエ変換、コサイン変換、およびウェーブレット変換を用いて、信号をスペクトル領域に変換することができ、このスペクトル領域では、例えば、所望の信号が帯域制限を受けることを仮定すると、ガイド部分空間を或る特定の周波数レンジに対応するものとして選ぶことができる。
【００２４】
自明のスペクトル特性を有しない信号の場合、それらの信号は、信号のタイプに応じて特別に構成された構造、例えば、グラフまたはリーマン多様体に組み込むことができ、それに応じて、スペクトル特性は、「エネルギー」ノルムおよびその「エネルギー」演算子、例えば、グラフラプラシアン行列またはラプラス・ベルトラミ（Ｌａｐｌａｃｅ−Ｂｅｌｔｒａｍｉ）演算子によって求められる。その場合、ガイド部分空間は、例えば、所望の信号が帯域制限を受け、主としてエネルギー演算子のスペクトルの低い部分からの成分を有すると仮定すると、そのスペクトルにおける或る特定のレンジに対応するエネルギー演算子の不変部分空間として選ぶことができる。この組み込むことは、信号空間における信号類似性尺度に応じて、組み込まれる空間における距離を選ぶことも伴う。この距離は、信号のタイプに応じて、例えば、相関、コヒーレンス、ダイバージェンス、またはメトリックを含むことができる。
【００２５】
本発明の１つの実施の形態では、入力信号のタイプは、画像、画像内のパッチ、１組の画像、ビデオシーケンス、ビデオシーケンス内のパッチ、深度マップ、スペクトルマップ、深度マップのパッチ、マップのパッチ、画像関連特徴ベクトル、およびそれらの組み合わせを含む。画像ベースの再構成の目標は、例えば、画像超解像度、アップスケーリング、修復、深度回復、画像ダイナミックレンジの増大、より高速なリフレッシュレートのためのビデオフレーム追加とすることができる。幾つかの外見上無関係に見えるタスク、例えば、分類、すなわち欠落したラベルを求めること、またはビデオシーケンスにおける物体追跡および今後の移動予測、すなわち物体のインジケータ関数の欠落した値若しくは今後の値を取得することは、画像ベースの信号再構成問題としての枠組みに入れることができる。
【００２６】
別の実施の形態では、信号は音場を更に含み、入力信号のタイプは、１つまたは１組のオーディオシーケンス、オーディオシーケンス内のパッチ、オーディオスペクトルマップ、オーディオスペクトルマップのパッチ、オーディオ特徴ベクトル、およびそれらの組み合わせを含む。オーディオベースの再構成は、例えば、アップサンプリング、オーディオ周波数またはダイナミックレンジの増大、合成オーディオチャネルの追加、深度再構成、および例えばインパルス雑音のリアルタイム除去を含むオーディオ回復に用いることができる。画像ベースの信号再構成問題およびオーディオベースの信号再構成問題を組み合わせたものは、対応する利用可能なビデオフレームを解析することによって、例えば、オーディオビデオシーケンスにおける自動読唇および欠落または破損したオーディオの再構成に有益である可能性がある。
【００２７】
上記タイプの入力信号の場合、ガイド集合は、フーリエ変換、コサイン変換、ウェーブレット変換、トレーニングデータセットから学習する方法、およびグラフの行列のスペクトル変換のうちの１つまたはそれらの組み合わせを含む群を用いて求められ、グラフは、タイプに従って構成され、グラフの行列は、グラフおよび入力信号を用いて求められる。
【００２８】
データマイニングアプリケーションでは、信号再構成は、例えば、欠落したデータを推定するかまたは今後のデータを予測するデータ完成またはデータ補間の形で現れる。例えば、時系列データ再構成は、障害のあるセンサを取り扱うのに用いることができ、データ外挿は、今後のシステム障害を予測するのに役立つことができる。そのような再構成は、例えば、カメラからのオーディオビデオ信号がシステムに向けられることも必要となる可能性がある。
【００２９】
更に別の実施の形態では、タイプ、コンシステント集合、およびガイド集合のうちの１つまたはそれらの組み合わせが、第１の組の確率分布を用いて求められ、再構成集合は、第１の組の確率分布に従った確率変数間の統計的類似性尺度を用いた第２の確率分布を用いて求められる。確率分布を用いることは、例えば、サンプリング手順の結果、測定値がランダムに分布するとき、例えば、測定値がガウス雑音を含むとき、またはガイド集合が再構成信号の所望の特性を記述した確率変数から学習されるとき、有益である。その場合、再構成集合は、確率変数も含む。
【００３０】
本発明の別の実施の形態では、例えば、入力信号がストリーミングであるとき、再構成信号をリアルタイムで生成することが有益である。
【００３１】
本発明者らは、ガイド集合がサンプルコンシステント信号を含まない特に重要な場合に関心がある。このため、再構成信号がガイド集合に属すると同時にサンプルコンシステントであるという条件を満たすことは不可能である。
【００３２】
その場合、従来技術は、再構成のための２つの二者択一の選択肢しか提案していない。すなわち、ガイド集合に存在するべきかまたはサンプルコンシステントであるべきかしか提案していない。本発明は、これらの２つの二者択一の選択肢が、再構成集合の新規な概念からは両極端な選択肢として解釈することができるという認識に基づいている。再構成集合は、第３の要素が、第２の要素集合（すなわち、ガイド集合）に対する当該第３の要素の第１の類似性尺度と、第１の要素集合（すなわち、コンシステント集合）に対する当該第３の要素の第２の類似性尺度との合計を最小化するような第３の要素を含む。このため、再構成集合は、選ばれた類似性尺度の観点から、所与のサンプリングされた信号のガイド集合とコンシステント集合との間の最短の経路集合を記述する。サンプリングまたはガイドの手順のうちのいずれが再構成信号のより良好な表現をもたらすことができるのかが判明していない場合、本発明者らの認識は、再構成集合の任意の要素が再構成に有効な候補となるということである。
【００３３】
複数の再構成信号の完全な再構成集合を出力しなければならないということは、幾つかのアプリケーションでは適切でない場合がある。再構成集合から単一の再構成信号を選択するには、追加の情報、例えば、再構成品質に対する再構成コストの比を表す関数が必要である。
【００３４】
１つの実施の形態では、再構成集合上で上記関数を最小化することによって、変換信号が求められ、その場合、再構成信号は、この変換信号に対する再構成信号の第３の類似性尺度が所定の許容範囲よりも小さくなるように生成される。同様に、再構成信号は、別の許容範囲に従って関数を最小化する再構成集合の近傍に生成することができる。
【００３５】
異なる実施の形態では、再構成信号は、上記関数と、再構成集合に対する類似性尺度との重み付き合計を最小化するように生成される。これは、関数値が、コンシステントおよびガイド集合の双方よりも再構成信号をより良く代表するときに有益である。上記関数と、再構成集合に対する類似性尺度との重み付き合計を最小化することは、再構成信号の制限を再構成集合の近傍に緩和する。
【００３６】
本発明の更に別の実施の形態では、変換信号は、関数を最小化する反復法を用いて求められる。この反復法は、トレーニングデータセットを用いて求められる調整可能な終了基準を有することができる。この反復法は、共役勾配反復法、チェビシェフ反復法、または前処理付き反復法を用いて求めることができる。
【００３７】
本発明の１つの実施の形態では、コンシステント集合およびガイド集合のうちの一方またはそれらの組み合わせは、１つまたは１群の線形集合を含む。再構成集合は、線形集合を用いて求められる。線形集合の１つの例は、近似クリロフ部分空間、有理クリロフ部分空間、および近似有理クリロフ部分空間からなる群から選択されたクリロフベースの部分空間である。
【図面の簡単な説明】
【００３８】
【図１】本発明の実施形態による信号を再構成する方法およびシステムの概略図である。
【図２Ａ】本発明の実施形態による再構成集合を求める方法の概略図である。
【図２Ｂ】本発明の実施形態による再構成集合を求める方法の概略図である。
【図２Ｃ】本発明の実施形態による再構成集合を求める方法の概略図である。
【図３】本発明の実施形態による、コンシステント集合およびガイド集合がラインである３次元ベクトル信号の再構成集合の概略図である。
【図４】本発明の実施形態によるグラフ信号を補間する方法およびシステムの概略図である。
【図５】本発明の実施形態による画像超解像度アップサンプリングの、本発明において説明される方法の適用の概略図である。
【図６】本発明の実施形態によるクリロフベースの部分空間を求める一実施形態のフロー図である。
【図７】本発明の実施形態によるグラフフィルタを求める方法のフロー図である。
【図８】本発明の実施形態による、物体追跡等の半教師あり学習アプリケーションにおいて物体ラベルを求める方法およびシステムの概略図である。
【発明を実施するための形態】
【００３９】
図１に示すように、本発明の実施形態は、入力信号１３０を再構成信号１８０として再構成する方法およびシステムを提供する。入力信号１３０は、センサ１２０を用いた原信号１００に対するサンプリング手順１１０によって取得される。入力信号は、プロセッサのメモリに記憶することもできるし、リアルタイムで処理することもできる。入力信号は、タイプ１５１と関連付けられる。入力信号が画像またはビデオシーケンスであるとき、サンプリング手順は、例えば、カメラのセンサ１２０と連動して動作することができる。他のサンプリング手順１１０およびセンサ１２０を、以下でより詳細に説明する入力信号１３０の特定の信号タイプ１５１向けに設計することができる。
【００４０】
コンシステント集合１４０内の任意の要素１４２にサンプリング手順１１０を適用した結果、入力信号１３０が得られるような、第１の要素１４２を含むコンシステント集合１４０が、入力信号１３０について求められる。コンシステント集合１４０も、メモリに記憶することができる。
【００４１】
メモリに記憶された第２の要素１５２を含むガイド集合１５０が、入力信号１３０のタイプ１５１に従って求められる。ガイド集合１５０は、コンシステント集合１４０と互いに素である。
【００４２】
再構成集合１６０も求められて記憶される。再構成集合１６０は、第３の要素１６１からなり、これらの第３の要素は、第３の要素１６１から第１の要素１４２までの第１の許容範囲Ｔ１内にある第１の類似性尺度ｄ１と、第３の要素１６１から第２の要素１５２までの第２の許容範囲Ｔ２内にある第２の類似性尺度ｄ２との合計を最小化する。
【００４３】
本発明の１つの実施形態では、これらの類似性尺度は、信号のタイプおよび再構成の目標に従って、距離、ノルム、セミノルム、相関、コヒーレンス、ダイバージェンス、およびメトリックのうちの１つまたはそれらの組み合わせを用いて求められる。例えば、ユークリッド２ノルムは、最小二乗最小化を提供し、プロセッサにおいて実施される本方法の計算コストの観点から有益である。別の例では、様々な重み付き最小二乗ノルムを、異なる類似性尺度について選ばれた異なる重みとともに用いることができる。これは、ユーザーが、例えば、第３の要素から第１の要素集合（すなわち、コンシステント集合）への第２の類似性尺度と比較した第３の要素から第２の要素集合（すなわち、ガイド集合）への第１の類似性尺度の相対的な重要度を制御することが可能になるので、有益である。
【００４４】
関数１６４は、再構成集合１６０上で最小化され（１６５）、変換信号１７０が取得される。
【００４５】
再構成信号１８０は、再構成信号と変換信号１７０との間の第３の類似性尺度ｄ３が第３の許容範囲Ｔ３よりも小さくなるように、変換信号１７０から生成される（１８１）。このように、再構成信号は、コンシステント集合１４０内になく、ガイド集合１５０内にもない。再構成信号は、信号に適切な出力デバイス１９０、例えば、入力信号が画像を含むときはディスプレイユニットまたはプリンターに提供することができる。
【００４６】
入力信号１３０から変換信号１７０を与える本方法のステップは、変換関数１７１を用いて入力信号１３０を変換信号１７０に変換することとみなすことができる。
【００４７】
図２Ａは、サンプリング手順１１０によって取得された入力信号１３０のコンシステント集合１４０を生成する一実施形態を示している。コンシステント集合は、サンプリング手順１１０によってサンプリングされると、その結果、入力信号を与える第１の要素２１０、２１１、２１２を含む。コンシステント集合内の要素は、入力信号およびサンプリング手順の零空間内の任意の要素にサンプリング手順の随伴を適用することによって生成することができる。
【００４８】
図２Ｂは、コンシステント集合１４０、再構成集合１６０、およびガイド集合１５０の間の一例示の関係を示している。再構成集合１６０は、少なくとも第１の要素２１２についてコンシステント集合１４０と交差し、少なくとも第２の要素２３０についてガイド集合１５０と交差する。再構成集合は、コンシステント集合にもガイド集合にも属さない第３の要素２２５も含むことができる。これらの第３の要素は、変換信号１７０とは異なる。
【００４９】
図２Ｃは、変換信号１７０と再構成信号１８０との間の関係の一例を示している。再構成信号１８０は、変換信号１７０に対する再構成信号の第３の類似性尺度ｄ３が許容範囲Ｔ３よりも小さくなるように求められる。
【００５０】
本発明の別の実施形態は、入力信号１３０から再構成信号１８０を求める変換関数１７１を求める方法を提供する。既に述べたように、入力信号、コンシステント集合、ガイド集合、および再構成集合は、システムのメモリに記憶される。
【００５１】
本発明の１つの実施形態の図３に示すように、コンシステント集合およびガイド集合のうちの一方またはそれらの組み合わせは、１つまたは１群の線形集合を含む。再構成集合は、線形集合の凸部分集合、例えば、図３に示すような区間を用いて求めることができる。図３は、コンシステント集合およびガイド集合が１群の線形集合１４０および１５０を含むとともに、再構成集合が第１の群内の線形集合を接続する第２の線形集合１６０を含み、このため、所与のサンプリングされた信号１３０について、選ばれた類似性尺度の観点から、ガイド集合１５０とコンシステント集合１４０との間の最短の経路集合１６０を記述する、本発明の一例示の実施形態を示している。
【００５２】
具体的には、図３における再構成集合は、コンシステント集合１４０内の第１の端点２１２と、ガイド集合１５０内の第２の端点２３０とを有する区間１６０である。再構成集合１６０は、第１の端点と第２の端点との凸線形結合として求められる。変換信号１８０は、第１の端点２１２に対する変換信号の第１の類似性尺度ｄ１および第２の端点２３０に対する変換信号の第２の類似性尺度ｄ２の観点から関数１６４を最小化する変換関数１７１によって求められる。最小化１６５は、第２の類似性尺度ｄ２に対する第１の類似性尺度ｄ１の比がパラメータα  ３７１の許容範囲Ｔ４内にあるときに取得される。
【００５３】
入力信号１３０が不正確であるかまたは雑音を有する場合、パラメータα  ３７１は、再構成集合１６０の直径に対する入力信号の不正確度の比に比例するものとして定義することができ、ここで、再構成集合１６０の直径は、再構成集合１６０の両極端にある端点間の類似性尺度、例えば、図３では、コンシステント集合１４０内の第１の端点２１２とガイド集合１５０内の第２の端点２３０との間の類似性尺度を用いて求められる。再構成集合の直径に対する入力信号の不正確度の比を用いることは、この比によって、ユーザーがサンプリング手順の正確度およびガイド集合の信頼度に従ってパラメータαを選ぶことが可能になるので有益である。これらの正確度および信頼度は、多くの実際的なアプリケーションについて既知である。
【００５４】
例えば、サンプリング手順１１０は、入力信号１３０の不正確度を必要とし、この不正確度は、雑音、サンプリング手順１１０を提供するセンサ１２０の限られた正確度、および入力信号１３０を表すデータの限られた精度のうちの１つまたはそれらの組み合わせに起因して現われる場合がある。センサ１２０の正確度は、センサ仕様から知ることができる。入力信号１３０を表すデータの精度は、通常、前もって知られており、メモリに接続されたプロセッサ上で実施されるとき、データを記憶するのに利用可能な複数のビットについてのデータ量子化によって決まる。
【００５５】
１つの実施形態では、信号のタイプ１５１、コンシステント集合１４０、およびガイド集合１５０のうちの１つまたはそれらの組み合わせは、第１の組の確率分布、例えば、ガウス分布またはガウス分布の混合体を用いて求められる。その場合、再構成集合は、カルバック・ライブラー（Ｋｕｌｌｂａｃｋ−Ｌｅｉｂｌｅｒ）（ＫＬ）ダイバージェンス等の第１の組の確率分布に従った確率変数間の統計的類似性尺度を用いる第２の確率分布を用いて求められる。この場合、入力信号１３０は、統計的分布からのサンプルを表すことができる。
【００５６】
１つの例は、ガウス混合モデル（ＧＭＭ）をビデオシーケンスのピクセルに割り当てる。再構成タスクは、オクルージョンを有するストリーミング入力画像のシーケンスからビデオ背景を求めるタスクとすることができる。その場合、ガイド集合１５０は、ビデオ内の背景ピクセルの分布を記述するＧＭＭとして表される。コンシステント集合１４０は、背景の一部であると知られている全てのピクセルを含む。その場合、再構成信号１８０は、いずれの前景オクルージョンも除去されたビデオシーケンスに表される背景シーンである。
【００５７】
複数の実施形態によれば、信号のガイド集合１５０は、望ましい再構成信号挙動のモデルまたは他の形態の記述を用いて求めることができる。１つの実施形態では、ガイド集合１５０は、トレーニングデータセットからアプリオリに学習される。これは、望ましい再構成信号挙動を含むトレーニングデータセットが利用可能であるとき、またはトレーニング用の対応するデータを収集することができるときに有利である。望ましい再構成信号挙動のモデルは、明示的に定式化することができない。
【００５８】
固有スペクトル特性を有する信号の場合、スペクトル変換、例えば、フーリエ変換、コサイン変換、およびウェーブレット変換を用いて、信号をスペクトル領域に変換することができ、このスペクトル領域では、例えば、所望の信号が帯域制限を受けるというモデルを仮定すると、ガイド集合１５０を或る特定の周波数レンジに対応するものとして選ぶことができる。このスペクトルモデルは、信号処理の多くのアプリケーションにおいて有利であり、信号は、それらのスペクトル特性によって必然的に解析することができるとともに良好に特徴付けることができる。
【００５９】
自明のスペクトル特性を有しない信号の場合、それらの信号は、信号のタイプ１５１に応じて特別に構成された構造、例えば、グラフまたはリーマン多様体に組み込むことができ、それに応じて、スペクトル特性は、「エネルギー」ノルムおよびその「エネルギー」演算子、例えば、グラフラプラシアン行列またはラプラス・ベルトラミ演算子によって求められる。その場合、ガイド部分空間１５０は、例えば、所望の信号が帯域制限を受け、主としてエネルギー演算子のスペクトルの低い部分からの成分を有すると仮定すると、そのスペクトルにおける或る特定のレンジに対応するエネルギー演算子の不変部分空間として選ぶことができる。エネルギー演算子は、所与の信号１３０または１群の信号について構成することができる。エネルギー演算子は、トレーニングデータセットからアプリオリに学習することもできる。
【００６０】
１つの実施形態では、ガイド部分空間は、グラフ信号と呼ばれるグラフに組み込まれた信号から構成されたグラフ行列を含むエネルギー演算子について求められる。帯域制限を受けるグラフ信号を再構成または補間する問題は、既知のサンプルによって指定された平面と、グラフ行列の低周波数固有ベクトルによってスパンされた部分空間との交差部分にある信号を求めることに類似している。この問題は、対称半正定値行列または対称半正定値演算子を有する線形システムとして再定式化することができる。これについては、以下の「問題定式化」セクションを参照されたい。
【００６１】
図４は、グラフ信号を再構成または補間する方法およびシステムの実施形態を示している。入力信号１３０（ビデオシーケンス４０１）が、センサ１２０（カメラ４０３）によってシーン４０２から取得される。記述子（特徴ベクトル）が抽出され（４１０）、基準信号が入力信号から抽出される（４１１）。
【００６２】
グラフ４２６が、入力信号１３０に対応するデータを用いて構成される（４２０）。この入力信号は、半教師あり学習の場合にように特徴ベクトルを用いて表すこともできるし、３Ｄビュー再構成の場合のようにサンプリングされたピクセルおよび基準信号を用いて表すこともできる。グラフ内のノードは、入力信号１３０のサンプルまたはピクセルに対応する。これらのノードは、重み付きエッジを用いて他のノードの部分集合に接続されている。重みは、エッジによって接続されたノードと関連付けられたデータ間の類似性を表す。
【００６３】
値が、データ点またはピクセル値のクラスメンバーシップ関数に従って各ノードに関連付けられる。目標は、本発明の実施形態を用いて、入力信号の欠落したサンプルを再構成することである。図４は、ガイド集合フィルタ４５１を計算して、本発明の方法において用いられるガイド集合を求める一例を示している。このフィルタの詳細は、図７を参照して説明される。
【００６４】
グラフ行列４３１が、グラフの隣接行列およびラプラシアン行列のうちの一方またはそれらの組み合わせとしてグラフから求められる（４３０）。１つの例示のアプリケーションでは、補間されるグラフ信号のタイプは帯域制限型である。この場合、グラフ行列および入力信号１３０のタイプ１５１に基づいてガイド部分空間４４１が求められる（４４０）。
【００６５】
異なる実施形態は、プロジェクタ（ｐｒｏｊｅｃｔｏｒ：投影線）、フレーム関数、およびフィルタ関数等の様々なガイド変換を用いてガイド集合１５０を求める。プロジェクタの使用は、例えば、ガイド部分空間の次元が過度に大きく、ガイド部分空間の対応するフレームをメモリに記憶することができない場合のフレームレス再構成にとって有益である。フレーム関数の使用は、フレームを容易に構成することができて、フレームが小さなメモリを用いるとき、またはコンピューターメモリ内で信号を表すベクトルに対してフレーム関数の操作を実行する算術演算が、ＢＬＡＳ−２およびＢＬＡＳ−３等の、コンピュータープロセッサについて最適化された基本線形代数サブプログラム（ＢＬＡＳ）を用いて実施されるときに有利である。例えば、計算統合デバイスアーキテクチャ（ＣＵＤＡ）を用いたグラフィックス処理ユニット（ＧＰＵ）またはフィールドプログラマブルゲートアレイ（ＦＰＧＡ）等における複数のコンピュータープロセッサを伴う実施は、スケーラブル線形代数パッケージ（ＳｃａＬＡＰＡＣＫ）およびＣＵＤＡ基本線形代数サブルーチン（ｃｕＢＬＡＳ）等の対応するソフトウェアライブラリーを用いることによって最適化することができる。
【００６６】
フィルタ関数を用いてガイド集合を求めることは、フレームを構成することが実際的でないときまたはプロジェクタであってもそれを構成することが実際的でないときに有益である。フィルタ関数は、例えば、行列多項式、近似行列多項式、行列有理関数、および近似行列有理関数を含む群を用いた近似として求めることができる。行列多項式は、チェビシェフ多項式の根およびチェビシェフ多項式の再帰公式のうちの一方またはそれらの組み合わせを用いたチェビシェフ（Ｃｈｅｂｙｓｈｅｖ）反復法を用いて求めることができる。加えて、行列多項式は、共役勾配反復法を用いて求めることもできる。
【００６７】
行列多項式および行列有理関数は、行列の関数の例であり、この行列は、例えば、フーリエ変換、コサイン変換、およびウェーブレット変換等の固有スペクトル変換、並びにグラフラプラシアン行列およびラプラス・ベルトラミ演算子等の強制構造によって取得された変換のうちの一方またはそれらの組み合わせによって定義されたエネルギー演算子を表す。この行列の多項式の使用は、信号に対するそれらの操作を、この行列と信号を表すベクトルとの乗算を用いてコンピュータープロセッサ上で実施することができるので有利である。この行列の有理関数のフィルタ関数としての使用は、フィルタ関数の所望のスペクトル特性を増幅するように有理関数を構成することができるので有利であるが、信号に対する有理関数の操作は、通常、行列を用いて線形システムを解くことを必要とする。なお、このシステムの右辺は、信号を表すベクトルである。
【００６８】
１つの実施形態では、ガイド部分空間は、クリロフ部分空間６０５、近似クリロフ部分空間６１０、有理クリロフ部分空間６２０、近似有理クリロフ部分空間６３０、およびそれらの組み合わせ６４０からなる群から選択されたクリロフベースの部分空間４４１として求められる（４４０：図６参照）クリロフベースの部分空間である。クリロフ部分空間の使用は、行列の多項式を用いてこれを構成することができるので有利である。計算を簡単にするために、ガイドフィルタ４５１は、ガイド部分空間４４１を用いて求めることができる（４５０）。
【００６９】
異なる実施形態では、ガイド集合は、グラフ行列Ｌの関数、例えばｈ（Ｌ）によって求めることができる。加えて、図７を参照すると、本発明の幾つかの実施形態によれば、求められる（７３０）フィルタ４５１は、グラフ行列Ｌの関数７０５およびこのグラフ行列の近似関数７１０のうちの一方またはそれらの組み合わせ７４０とすることができる。例えば、グラフ行列の正確な関数がｈ（Ｌ）によって与えられる場合、近似行列関数は、
【数１】
0006573538.tif 000002
とすることができ、ここで、行列
【数２】
0006573538.tif 000003
は、行列Ｌを近似したものであり、例えば、Ｌの正確度を低くした表現である一方、関数ｈ（）は同じままである。
【００７０】
フィルタは、例えば、或る区間上の信号のグラフフーリエスペクトル成分を最適に抑制する一方、その区間の外部のグラフフーリエスペクトル成分を強調する行列多項式を用いて求めることができる（７３０）。１つの実施形態では、多項式は、帯域を超える信号のグラフフーリエスペクトル成分を最適かつ均一に抑制する一方、その帯域を下回るグラフフーリエスペクトル成分を強調する所定の阻止帯域を有するチェビシェフ多項式である。
【００７１】
同様の実施形態では、多項式は、１つまたは複数の非インターレース区間上の信号のグラフフーリエスペクトル成分を抑制する一方、この１つまたは複数の非インターレース区間の外部のグラフスペクトル成分を強調する多項式の組み合わせである。例えば、多項式は、対応する区間上のチェビシェフ多項式の積とすることができる。別の例では、１つまたは複数の非インターレース区間上の信号のグラフフーリエスペクトル成分を最適かつ均一に抑制する一方、この１つまたは複数の非インターレース区間の外部のグラフスペクトル成分を強調する多項式を求めることができる。
【００７２】
１つの実施形態は、チェビシェフ多項式の根を用いる２項チェビシェフ反復法に基づいてガイドフィルタ関数を求める。別の実施形態は、例えば、３項チェビシェフ反復法を与えるチェビシェフ多項式の再帰式を利用する。
【００７３】
異なる実施形態では、ガイド多項式は、信号に対して適応的であり、ここで、適応的とは、多項式の係数または根が信号に応じて求められることを意味する。１つの実施形態では、適応的多項式の一例は、共役勾配（ＣＧ）手順の反復を用いるパラメータフリー適応的フィルタリング手法である。ガイドＣＧ適応的フィルタは、行列有理関数が、その行列が特異である場合にその行列のその逆行列または擬似逆行列に基づいている一実施形態のクリロフ部分空間多項式近似の一例とみなすことができる。
【００７４】
代替的にまたは加えて、変換信号は、関数を最小化する反復法に直接基づいて求めることができ、この反復法の反復数は閾値によって決まる。関数が２次である場合、最小化は、関数の勾配が最小値の点において零になることを反映して連立１次方程式を解くことと等価である。関数最小化に反復法を用いることは、関数を最小化する反復法の反復数を制限することによって、ユーザーはフィルタの品質および計算コストの双方を制御することが可能になるので、有利である。例えば、ローパスフィルタリングにおいては、スペクトルにおける低帯域を対象にすることができる。反復数が過度に大きい場合、このフィルタ法は、計算的に複雑であり、フィルタリングを特に選択された対象に限定し、フィルタの品質を低下させる。
【００７５】
関数を最小化する反復法の例には、クリロフ部分空間法および有理クリロフ部分空間法が含まれる。１つの実施形態では、クリロフ部分空間法は、例えば、ランチョス（Ｌａｎｃｚｏｓ）法または共役勾配法であり、多項式の根および係数は信号に対して適応しており、次の利点を有する。ＣＧ法の収束に必要とされる反復数は、凸集合上への投影（ＰＯＣＳ）に基づく手法と比較して少ない。このため、実行時間は大幅に減少し、サンプル信号がストリーミングである場合に、提案した信号再構成方法が信号をリアルタイムで再構成することが可能になる。所与の限られた反復数を用いて取得された解の品質は、ＰＯＣＳに基づく方法よりも良好とすることができる。
【００７６】
問題定式化
本方法の１つの実施形態では、サンプリング部分空間と呼ばれる閉部分空間Ｓ⊆Ｈ上への直交投影Ｓｆとして定義される、スカラー積および対応するノルム‖・‖を備えるヒルベルト空間Ｈにおける未知の原信号ｆ∈Ｈ  １００の再構成ｚ∈Ｈ  １８０をｆのサンプル１３０から求める問題を検討する。プロジェクタＳの操作は、サンプリング手順１１０を表す。ノルム‖・‖は、信号間の類似性尺度を求める。
【００７７】
原信号ｆ  １００は、通常、未知であり、サンプリングされた原信号Ｓｆ  １３０のみが、再構成方法への入力として利用可能である。サンプリング手順１１０は、情報の喪失を伴っているので、回復される原信号ｆ  １００に対して幾つかのアプリオリな仮定が必要となる。
【００７８】
１つのそのような仮定は、信号ｆ  １００が、対象の再構成部分空間と考えることができる閉部分空間Ｔ⊆Ｈに属するということである。Ｔは、ガイド再構成部分空間１５０と呼ぶことが好ましい。なぜならば、本発明者らの技法では、信号ｆは、必ずしもＴに限定されないからである。
【００７９】
別の可能な仮定は、信号ｆが、信号ｆの平滑化によって求められるＨのコンパクト部分集合１５０に属するということである。いずれにしても、所望の再構成は、再構成誤差‖ｚ−ｆ‖を最小化する。
【００８０】
同じサンプルＳｆを有する全ての信号の集合は、コンシステント平面と呼ばれる閉平面Ｓｆ＋Ｓ⊥である。ここで、Ｓ⊥は、サンプリング部分空間Ｓに対する直交補空間である。しかし、Ｓｆ＋Ｓ⊥およびＴは、一般に交差せず、その場合、再構成信号ｙ  １８０を双方の集合１４０および１５０に制約することはできない。
【００８１】
ＴおよびＳを、それぞれ閉部分空間ＴおよびＳ上へのオルソプロジェクタとする。Ｔ⊥＝Ｉ−ＴおよびＳ⊥＝Ｉ−Ｓは、それらの直交補空間Ｔ⊥およびＳ⊥上へのオルソプロジェクタを示すものとする。ここで、Ｉは恒等演算子である。Ｒ（Ａ）は演算子Ａのレンジを示し、Ｎ（Ａ）はＲ（Ａ）の零空間を示すものとし、その場合、プロジェクタＳを有する任意の部分空間Ｓについて、Ｓ＝Ｒ（Ｓ）であり、Ｓ⊥＝Ｒ（Ｓ⊥）＝Ｎ（Ｓ）となる。
【００８２】
本発明者らは、要素ｆ∈Ｈを、Ｓ上のその投影によってサンプリングし、すなわち、観測されるサンプルがＳｆによって与えられ、Ｓｆからｆを再構成したい。信号ｆは、以下の２つの直交成分に分割することができる。
【数３】
0006573538.tif 000004
ここで、Ｓｆは、ｆ  １００の観測されるサンプル１３０であり、ｘは、求められる欠落した情報を含む。
【００８３】
コンシステント再構成信号ｙは、以下の制約付き最小化問題の解として求めることができる。
【数４】
0006573538.tif 000005
この式は、ｘ＝ｙ−Ｓｆを代入すると、以下の問題と等価である。
【数５】
0006573538.tif 000006
【００８４】
問題（３）は、以下の演算子形式で等価に記述することができる。
【数６】
0006573538.tif 000007
ここで、
【数７】
0006573538.tif 000008
は、その不変部分空間Ｓ⊥への演算子制限を示す（すなわち、Ｓ⊥Ｔ⊥の領域はＳ⊥に制限される）。ｘが問題（４）の解である場合、信号ｙ＝ｘ＋Ｓｆは、式（２）における本発明者らの制約付き最小化問題の演算子形式である以下の式を満たす。
【数８】
0006573538.tif 000009
【００８５】
図３では、信号ｙは、コンシステント集合内の第１の端点２１２に対応する。上記説明は、第１の端点を連立方程式（４）によってどのように求めることができるのかを指定する。図３における第２の端点２３０を計算するには、ｙに直交プロジェクタＴを乗算して信号ｙｇを得ることで十分である。ｙｇを求める別の手法は、以下の方程式を解くことである。
【数９】
0006573538.tif 000010
【００８６】
例えば、共役勾配反復法を用い、次いで、以下の式を計算する。
【数１０】
0006573538.tif 000011
【００８７】
図３に示すように、第１の端点２１２は、コンシステント平面Ｓｆ＋Ｓ⊥の要素からガイド部分空間Ｔまでの距離の最小点（ｍｉｎｉｍｉｚｅｒ：ミニマイザー）である一方、第２の端点２３０は、コンシステント平面Ｓｆ＋Ｓ⊥までの距離を最小化するガイド部分空間Ｔからの要素である。
【００８８】
コンシステント平面Ｓｆ＋Ｓ⊥とガイド部分空間Ｔとの間の最短経路集合である再構成集合Ｒ  １６０を定義するヒントを本発明者らに与える等式として、以下の等式がある。
【数１１】
0006573538.tif 000012
【００８９】
その結果、再構成集合Ｒ  １６０は、パラメータαによって、以下の式となるような、ｙとｙｇとの間の凸線形区間をスパンする全ての信号ｙαの集合として求めることができる。
【数１２】
0006573538.tif 000013
【００９０】
変換関数を最小化する特定のパラメータα＊の選択は、変換信号１８０を決定する。例えば、ｎが真のサンプルＳｆからのずれを表すものとして、ＳｆをＳｆ＋ｎによって置き換えた場合において、雑音を有するサンプルまたはそれ以外の不正確なサンプルから再構成を求めるときは、以下の式を選択することができる。
【数１３】
0006573538.tif 000014
【００９１】
式（６）において、分子‖ｎ‖は、サンプリングセンサの仕様から知ることができる。分母‖ｙ−ｙｇ‖は、再構成集合Ｒ  １６０の直径である。
【００９２】
その上、パラメータαは、以下の式となるように許容範囲Ｔ５内で選択することもできる。
【数１４】
0006573538.tif 000015
【００９３】
最後に、再構成信号ｚ  １７０が、ｙαから距離ｄ３内となるように求められる。
【００９４】
問題の別の定式化は、以下の式の重み付き制約付き最小化を用いる。
【数１５】
0006573538.tif 000016
この式は、ｘ＝ｙ−Ｓｆを代入すると、以下の問題と等価である。
【数１６】
0006573538.tif 000017
【００９５】
（８）における問題の演算子形式は、以下の式として等価的に記述することができる。
【数１７】
0006573538.tif 000018
【００９６】
この場合も同様に、ｘが上記問題の解である場合、信号ｙ＝ｘ＋Ｓｆは、式（７）における本発明者らの重み付き制約付き最小化問題の演算子形式である以下の式を満たす。
【数１８】
0006573538.tif 000019
【００９７】
１つの実施形態は、再構成信号ｙ  １８０が再構成集合１６０において変換信号１７０に接近しているという制約を緩和し、その代わり、以下の式の重み付き制約なし最小化を用いる。
【数１９】
0006573538.tif 000020
ここで、正の実定数ｃ１、ｃ２、およびｃ３は重みを表し、式ｄｉｓｔ（ｙ，Ｒ）は、再構成信号ｙ  １８０と再構成集合Ｒ  １６０との間の類似性尺度を示し、関数Ｅ（ｙ）は、例えば、信号ｙのエネルギーまたは再構成の品質に対するコストの比を表す。
【００９８】
信号再構成の例
本信号再構成方法およびシステムは、種々のタイプの信号に適用することができる。このセクションでは、幾つかのアプリケーション、例えば、グラフ信号補間、画像アップサンプリング、および物体追跡の信号再構成を更に詳しく説明する。本発明は、これらの例示的なアプリケーションに限定されるものではないことに留意すべきである。
【００９９】
例えば、入力信号は、画像、画像内のパッチ、１組の画像、ビデオシーケンス、ビデオシーケンス内のパッチ、深度マップ若しくはスペクトルマップ、深度マップ若しくはスペクトルマップのパッチ、または画像関連特徴ベクトルとすることができる。
【０１００】
音響領域では、入力信号は、音声等の１つまたは１組のオーディオシーケンス、オーディオシーケンス内のパッチ、オーディオスペクトルマップ、オーディオスペクトルマップのパッチ、およびオーディオ特徴ベクトルとすることができる。その上、本方法は、画像シーケンスおよびオーディオシーケンスの組み合わせからなる信号に適用することができる。
【０１０１】
入力信号は、１つまたは１組の時系列、時系列内のパッチ、または時系列特徴ベクトル、およびそれらの組み合わせとすることもできる。
【０１０２】
画像超解像度アップサンプリング
画像超解像度アップサンプリング問題は、本発明の方法を用いる単純な例を表す。図５は、本発明を用いて画像をアップサンプリングする一例を示している。元の画像１００が、サンプリング手順１１０を用いてサンプリングされて、入力信号１３０が取得される。この入力信号およびサンプリング手順は、コンシステント集合１４０を求める。このコンシステント集合は、サンプリング手順を用いてサンプリングされると、その結果、入力信号を与える画像を含む。
【０１０３】
１つの実施形態では、入力信号のタイプ１５１は、帯域制限型であると仮定される。帯域制限型の条件によって、ローパス離散コサイン変換（ＤＣＴ）、離散フーリエ変換（ＤＦＴ）、離散ウェーブレット変換（ＤＷＴ）のうちの１つまたはそれらの組み合わせによって特徴付けられるガイド部分空間を指定することが可能になる。或る周波数帯域に制限されたＤＣＴ領域、ＤＦＴ領域、またはＤＷＴ領域における係数を有する画像の集合体が、ガイド集合１５０を構成する。次に、再構成集合１６０を、コンシステント集合とガイド集合との間の最小距離を有する区間として求めることができる。次に、変換関数１７１が最小化されて、変換信号１７０が求められる。
【０１０４】
オーディオ再構成
画像アップサンプリングと同様に、音響信号再構成またはオーディオ再構成では、信号は、１つまたは１組のオーディオシーケンス、オーディオシーケンス内のパッチ、オーディオスペクトルマップ、オーディオスペクトルマップのパッチ、オーディオ特徴ベクトルを含む。この信号は、ビデオシーケンスおよび対応するオーディオトラックの組み合わせも含むことができる。この場合、再構成問題は、狭帯域オーディオ信号の帯域幅を拡張することを目標とする。ガイド部分空間は、関連した信号のデータベースから学習することによって取得することができる。再構成方法は、次に、サンプリング部分空間とガイド部分空間との間の区間に存在する再構成信号を見つける。この手法は、実際的なアプリケーションでは、信頼できる対象の再構成部分空間のフレームを明示的に見つけることが困難な場合もあるし、信頼できる対象の再構成部分空間を選ぶことさえも困難な場合があるという認識によって動機付けられている。このため、ガイド部分空間は、ガイドとしてのみ用いられ、サンプリングおよび周期性等の信号のタイプの特性を特徴付ける関数がより重視される。
【０１０５】
物体追跡
本発明の１つの実施形態は、クラスラベルを用いて物体とのみ関連付けられた特徴記述子の部分集合を特定することによって、ビデオ内の種々の移動物体に対応する特徴点記述子を追跡する。
【０１０６】
図８は、カメラ４０３を用いて取得されたシーン４０２のビデオ４０１を示している。このビデオは処理されて、特徴点特徴記述子８０５が抽出される。対象物体に属する記述子がシーンの残りの記述子と異なるラベル値を割り当てられるように、信号の初期セクション、例えば、ビデオ内の第１の画像における記述子のみが、例えば手動でラベル付けされる（８１０）。このタスクは、対象物体の記述子のみが最初のフレームと同じラベル値を割り当てられるとともに残りの全ての記述子が異なるラベルを割り当てられるように、次のビデオ画像における記述子にラベルを割り当てることである。
【０１０７】
１つの実施形態では、図４について説明した実施形態と同様に、最初のビデオ画像および次のビデオ画像の記述子は、グラフにおいてノードとして取り扱われ、ラベルは、各ノードの値とみなされる。図４に示すグラフ信号補間のガイドフィルタ構成４９０の実施形態を用いると、変換信号１７０が、ガイドフィルタおよび入力信号に従って求められる（１７１）。次に、再構成信号１８０が、事後処理およびラベル精緻化関数を用いて変換信号から求められる。最初のフレームにおける物体のラベルの値と一致する値を有する新たなビデオ画像のそれぞれにおける記述子のラベルは、その物体に属するとみなされる。物体ラベルを有するそれらの記述子のロケーションは、新たなビデオ画像における物体のロケーションを決定する。
【図１】
0006573538.tif 000021
【図２Ａ】
0006573538.tif 000022
【図２Ｂ】
0006573538.tif 000023
【図２Ｃ】
0006573538.tif 000024
【図３】
0006573538.tif 000025
【図４】
0006573538.tif 000026
【図５】
0006573538.tif 000027
【図６】
0006573538.tif 000028
【図７】
0006573538.tif 000029
【図８】
0006573538.tif 000030