(57)【要約】      （修正有）【課題】バイナリー埋め込み、１ビット圧縮センシングに関係し、ビットレートを所与とした埋め込みの不確実性を削減する。【解決手段】１つ又は複数の信号が、複素測定値行列を用いてこれらの信号を測定し、信号の複素数値測定値を生成することによって埋め込まれる。次に、信号の角度が保存されるように、複素数値測定値の位相のみが保持される。その後、量子化するとともにデータベースに記憶するこれらの位相を、信号の位相角度のみに基づいて探索して、類似した信号を突き止める。【選択図】図１
2014194757.tif 000002
【特許請求の範囲】
【請求項１】
信号を埋め込む方法であって、
複素測定値行列を用いて前記信号を測定することによって、前記信号の複素数値測定値を生成するステップと、
前記信号の角度が保存されるように、前記複素数値測定値の位相のみを保持するステップと、
を含み、前記ステップは、プロセッサにおいて実行される、信号を埋め込む方法。
【請求項２】
請求項１に記載の方法であって、
前記複素数値測定値の前記位相を量子化するステップ、
を更に含む、請求項１に記載の方法。
【請求項３】
請求項１に記載の方法であって、
複数の信号の前記複素数値測定値の前記位相間の平均位相差を測定することによって、前記複数の信号の前記角度を推定するステップ、
を更に含む、請求項１に記載の方法。
【請求項４】
請求項２に記載の方法であって、
前記複素数値測定値の量子化された位相間の平均位相差を測定することによって、２つの信号の前記角度を推定するステップ、
を更に含む、請求項２に記載の方法。
【請求項５】
請求項１に記載の方法であって、
前記複素測定値行列をランダムに生成するステップ、
を更に含む、請求項１に記載の方法。
【請求項６】
請求項５に記載の方法であって、前記複素測定値行列は、複素正規分布から別々に取り出された要素から構成される、請求項５に記載の方法。
【請求項７】
請求項３に記載の方法であって、
前記位相をメモリに記憶するステップと、
前記生成するステップ、前記保持するステップ、及び前記記憶するステップをクエリ信号に適用するステップと、
前記クエリ信号の前記角度と比較して、前記複数の信号のうちの、最小の角度の１つ又は複数を選択するステップと、
を更に含む、請求項３に記載の方法。
【請求項８】
請求項７に記載の方法であって、
前記メモリは、サーバーの一部であり、該方法は、
前記サーバーからクライアントに前記位相を送信するステップと、
前記１つ又は複数の選択された信号に関係した関連データを前記クライアントに返すステップと、
を更に含む、請求項７に記載の方法。
【請求項９】
請求項８に記載の方法であって、前記関連データは、前記信号のメタデータである、請求項８に記載の方法。
【請求項１０】
請求項８に記載の方法であって、前記関連データは、前記信号に類似した他の信号である、請求項８に記載の方法。
【請求項１１】
請求項８に記載の方法であって、データベースが、埋め込み信号の集合を記憶する、請求項８に記載の方法。
【請求項１２】
請求項８に記載の方法であって、最近傍探索を用いて探索が実行される、請求項８に記載の方法。
【請求項１３】
請求項１０に記載の方法であって、
前記類似した信号のクラスを用いて、前記クエリ信号のクラスを決定するステップ、
を更に含む、請求項１０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、信号処理に関し、より詳細には、複素線形測定値の位相によって捕捉される信号間の角度のランダム化埋め込み（ｒａｎｄｏｍｉｚｅｄ  ｅｍｂｅｄｄｉｎｇｓ）に関する。
【背景技術】
【０００２】
ランダム化埋め込みは、信号処理においてますます重要な役割を有するようになっている。これらの埋め込みは、信号の幾何学的形態の或る側面を保存しつつ、信号を計算に好都合な空間にマッピングする。したがって、埋め込み信号に対する計算効率の良い操作は、元の空間における操作に直接マッピングすることができる。
【０００３】
例えば、よく知られたジョンソンリンデンシュトラウス（Ｊ−Ｌ：Ｊｏｈｎｓｏｎ−Ｌｉｎｄｅｎｓｔｒａｕｓｓ）埋め込みは、ｌ２距離を保存しつつ次元数を削減する。これらの埋め込みは、信号の集合Ｓ⊂ＲＮ内の任意の２つの信号ｘ及びｙのイメージが以下の式を満たすように、ＳをＫ次元ベクトル空間にマッピングする関数ｆ：Ｓ→ＲＫである。
【０００４】
【数１】
2014194757.tif 000003
【０００５】
これらの埋め込みは、次元当たりＢビットに均等に量子化されるとき、以下の式を保証する。
【０００６】
【数２】
2014194757.tif 000004
【０００７】
式中、Ｓは、無視してよい飽和を確保するように設定される量子化子の飽和レベルである。これについては、米国特許出願第１３／５２５，２２２号を参照されたい。
【０００８】
量子化された埋め込みは、パターンマッチングのための効率的な伝送を必要とする拡張現実感等の多くの用途において用いられる。これについては、例えば、本出願人の米国特許出願第１３／４５６、２１８号の「Ｍｅｔｈｏｄ  ｆｏｒ  Ｓｙｎｔｈｅｓｉｚｉｎｇ  ａ  Ｖｉｒｔｕａｌ  Ｉｍａｇｅ  ｆｒｏｍ  ａ  Ｒｅｄｕｃｅｄ  Ｒｅｓｏｌｕｔｉｏｎ  Ｄｅｐｔｈ  Ｉｍａｇｅ」を参照されたい。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、多くの用途において、ｌ２距離は適切なメトリックではない。
【課題を解決するための手段】
【００１０】
信号のランダム化された複素数値射影の位相が、信号間の角度、すなわち相関についての情報を保存する。この情報は、有限のビットレートを用いてそのような相関を表す量子化された角度保存埋め込みを設計するのに利用することができる。
【発明の効果】
【００１１】
これらの埋め込みは、バイナリー埋め込み、１ビット圧縮センシングに関係し、ビットレートを所与とした埋め込みの不確実性を削減する。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施形態による信号の位相を埋め込むシステム及び方法のブロック図である。
【図２】本発明の実施形態による、角度の埋め込みから信号の角度を推定するシステム及び方法のブロック図である。
【図３】測定当たり異なるレートにおいて異なる角度を有する数対の信号の埋め込み距離及び信号距離の関数として埋め込み性能を比較するグラフである。
【図４】測定当たり異なるレートにおいて異なる角度を有する数対の信号の埋め込み距離及び信号距離の関数として埋め込み性能を比較するグラフである。
【図５】測定当たり異なるレートにおいて異なる角度を有する数対の信号の埋め込み距離及び信号距離の関数として埋め込み性能を比較するグラフである。
【発明を実施するための形態】
【００１３】
本発明の実施形態は、信号の角度、すなわち相関を保存する、信号の位相を埋め込む方法を提供する。以下のように定義される、２つの信号ｘ及びｘ’の間の正規化された角度が用いられる。
【００１４】
【数３】
2014194757.tif 000005
【００１５】
多くの場合、特に、信号が正規化されるとき、信号間の角度は、比較のための情報を距離よりも多く与える。したがって、角度保存埋め込みは、より効率的な符号化をもたらすことができる。
【００１６】
角度埋め込みは、１ビット圧縮センシングに関して従来技術で用いられてきた。バイナリーε安定埋め込みが、ランダム射影と、以下の式にある各係数の正負符号（ｓｉｇｎ）のみを符号化するその後の１−ビットスカラー量子化子とを用いて信号を符号化する。
【００１７】
【数４】
2014194757.tif 000006
【００１８】
この点で、ｑ及びｑ’にそれぞれ埋め込まれた２つの信号ｘ及びｘ’の間の正規化された角度は、以下のように、それらの埋め込み間の正規化されたハミング距離に保存されている。
【００１９】
【数５】
2014194757.tif 000007
【００２０】
式中、
【数６】
2014194757.tif 000008
は、信号埋め込み間の正規化されたハミング距離を示す。
【００２１】
実施形態は、以下の式のように、最初に信号を複素数値空間に射影し、射影係数の位相のみを保存及び量子化することによって得られる位相埋め込みを検討している。
【００２２】
【数７】
2014194757.tif 000009
【００２３】
式中、ＡＣ∈Ｋ×Ｎは、複素数値行列である。好ましい実施形態では、これは、従来の複素正規分布から取り出されたｉ．ｉ．ｄ．要素からなる。式（４）において、量子化子Ｑ（・）は任意選択的である。
【００２４】
説明する埋め込みを図１に示す。この埋め込みは、プロセッサ１００において実行することができる。信号空間１０２に属する入力信号ｘ１０１が、最初に、行列Ａｃを用いてランダムに射影され（１１０）、射影された信号Ａｃｘ１１１が得られる。射影の位相１２１が、射影された信号から得られる（１２０）。任意選択として、この位相を量子化することができる（１３０）。この位相又は量子化された位相は、埋め込み信号１３１を構成し、この埋め込み信号は、埋め込み空間１３２に位置する。
【００２５】
この変換は、一対の信号ｘ及びｘ’を所与として、それらの射影係数の位相差の予想値がそれらの角度に比例することを最初に確立することによって、信号間の角度を保存する。
【００２６】
【数８】
2014194757.tif 000010
と定義すると、上記予想値は、Ｅ｛｜Δφｉ｜｝＝πｄＳ（ｘ，ｘ’）に等しい。式中、∠（・）は、主位相の角度を示す。ヘフディング（Ｈｏｅｆｆｄｉｎｇ）の不等式を用いると、量子化子Ｑ（・）がなくても、
【数９】
2014194757.tif 000011
よりも大きな確率を用いて、以下の式を示すことができる。
【００２７】
【数１０】
2014194757.tif 000012
【００２８】
したがって、Ｊ−Ｌ埋め込みと同様に、Ｌ個の点の集合を埋め込むのに、Ｋ＝Ｏ（ｌｏｇＬ）個の次元で十分である。
【００２９】
既知の方法を用いると、この議論は、スパース信号等の無限の信号集合に拡張することができる。埋め込みが、次元当たりＢビットに量子化される場合、この保証は以下の式となる。
【００３０】
【数１１】
2014194757.tif 000013
【００３１】
これらの埋め込みは、角度、すなわち相関を保存するので、２つの信号の角度は、先ず、式（４）に従って信号を埋め込み、次に、埋め込み領域において角度を計算することによって簡単に近似計算することができる。角度は、それらの埋め込みのみを用いて推定することができる。角度の推定値は以下となる。
【００３２】
【数１２】
2014194757.tif 000014
【００３３】
この推定値を用いると、信号を比較して、これらの信号が当該信号の相関に関してどの程度類似しているのかを求めることが可能である。
【００３４】
図２は、角度推定のステップを示している。２つの埋め込み信号ｘ２３１及びｘ’２３２が、プロセッサ２００において処理される。スケーリングされた絶対位相差が、式（７）に従って計算され（２１０）、角度推定値２４１が生成される。
【００３５】
多くの用途では、信号は、多くの場合、クライアントからサーバーにおけるデータベース（メモリ）へのクエリとして用いられる。このクエリは、そのデータベースから類似した信号、又はこれらの類似した信号に関係したメタデータを検索することを目的としている。類似性メトリックは、ｌ２距離とすることができる。これについては、例えば、米国特許出願第１３／５２５，２２２号及び第１３／７３３，５１７号を参照されたい。しかしながら、非常に多くの場合、角度、すなわち正規化された相関が、適切なメトリックである。この場合、実際の信号の代わりに埋め込みを用いると、探索の計算時間を削減することができる。なぜならば、埋め込みの次元数は、信号の次元数よりもはるかに少なくすることができるからである。
【００３６】
多くの場合、信号を、他の信号又はデータベースに記憶されたデータと比較する前に、その信号を送信することが必要な場合がある。例えば、拡張現実感の用途及びイメージベースの探索の用途では、信号、又は信号から抽出された特徴のベクトルが、探索を実行する中央サーバーに送信される。式（４）を用いて計算された、信号又は特徴の量子化された埋め込みの送信は、全部でＫＢ個のビットを用いる。これは、信号全体又はその特徴を送信するよりも大幅に少ない。したがって、埋め込みを送信することによって、必要な通信帯域幅を大幅に削減することができる。
【００３７】
これらの埋め込みは、１ビット埋め込みを一般化したものである。なぜならば、複素信号の位相は、実数値信号の正負符号を一般化しているからである。したがって、１ビット埋め込みと同様に、位相埋め込みは、信号から振幅情報（ｍａｇｎｉｔｕｄｅ  ｉｎｆｏｒｍａｔｉｏｎ）を取り除くが、角度計算を可能にするのに十分な情報を保存する。
【００３８】
図３、図４、及び図５は、測定ごとに異なるレートを用いて埋め込まれた、異なる角度を有する数対の信号に関するシミュレーション結果をプロットして、埋め込みの性能を比較している。量子化された角度埋め込みは、量子化レートに応じた或る不確実性を有する、信号間の真の角度を捕捉している。図３は、１ビット／測定対２ビット／測定を示し、図４は、１ビット／測定対４ビット／測定を示し、図５は、４ビット／測定対３２ビット／測定を示している。予想されるように、測定当たりの量子化が微細であるほど、埋め込み精度は改善される。しかしながら、測定当たり４ビットを超えると、利点は小さい。さらに、測定当たりのレートが増加すると、総レートも増加し、これは、システム設計の考慮に入れられるべきである。
【００３９】
信号の複素射影の位相のみ、すなわち、位相のみの圧縮センシングを用いて、スパース再構成のための凸計画問題を定式化することができることが理解されるべきである。
【図１】
2014194757.tif 000015
【図２】
2014194757.tif 000016
【図３】
2014194757.tif 000017
【図４】
2014194757.tif 000018
【図５】
2014194757.tif 000019
【外国語明細書】
2014194757.tif 000020
2014194757.tif 000021
2014194757.tif 000022
2014194757.tif 000023
2014194757.tif 000024
2014194757.tif 000025
2014194757.tif 000026
2014194757.tif 000027
2014194757.tif 000028
2014194757.tif 000029
2014194757.tif 000030
2014194757.tif 000031
2014194757.tif 000032
2014194757.tif 000033
2014194757.tif 000034
2014194757.tif 000035