(57)【特許請求の範囲】
【請求項１】
作用素に対して不変である、信号の埋め込みを生成する方法であって、
測定ベクトルの集合からの各ベクトルを用いて前記信号を測定して、対応する係数の集合を生成するステップであって、各測定ベクトルと前記信号とを比較し、前記作用素を用いて各測定ベクトルおよび前記信号を変換する、測定するステップと、
既定の基準に従った１つまたは複数の一致する係数の集合を選択するステップと、
前記一致する係数を組み合わせて、前記信号の前記埋め込みを生成するステップであって、前記埋め込みは、作用素不変である、生成するステップと
を含み、前記ステップは、プロセッサにおいて実行される、方法。
【請求項２】
２つの信号のそれぞれについて前記埋め込みを生成するステップと、
前記２つの信号の前記埋め込みを比較して、比較結果を生成するステップと
をさらに含む、請求項１に記載の方法。
【請求項３】
信号のデータベースに記憶された各信号について前記埋め込みを生成するステップと、
各信号を前記埋め込みに関連付けて、インデックスエントリーを生成するステップと、
前記インデックスエントリーをインデックステーブルに記憶するステップと
をさらに含む、請求項１に記載の方法。
【請求項４】
クエリ信号の埋め込みを生成するステップと、
前記インデックスエントリーを用いて、前記クエリ信号の前記埋め込みを、前記データベースに記憶された前記信号の前記埋め込みと比較するステップと、
前記クエリ信号の前記埋め込みに対応する、一致する埋め込みを有する前記データベース内の前記信号を取り出すステップと
をさらに含む、請求項３に記載の方法。
【請求項５】
前記測定ベクトルの集合をランダムに生成するステップ
をさらに含む、請求項１に記載の方法。
【請求項６】
前記選択するステップは、類似性メトリックを用いる、請求項１に記載の方法。
【請求項７】
前記選択するステップは、非類似性メトリックを用いる、請求項１に記載の方法。
【請求項８】
前記比較するステップは、類似性メトリックを用いる、請求項２に記載の方法。
【請求項９】
前記比較するステップは、非類似性メトリックを用いる、請求項２に記載の方法。
【請求項１０】
前記一致する係数は、最もよく一致する係数である、請求項１に記載の方法。
【請求項１１】
前記非類似性メトリックは、２つの信号間の距離を計算するものである、請求項７または９に記載の方法。
【請求項１２】
前記距離は、ユークリッド距離である、請求項１１に記載の方法。
【請求項１３】
前記非類似性メトリックは、ダイバージェンスである、請求項７または９に記載の方法。
【請求項１４】
前記ダイバージェンスは、ブレグマンダイバージェンスである、請求項１３に記載の方法。
【請求項１５】
前記類似性メトリックは、相関である、請求項６または８に記載の方法。
【請求項１６】
前記類似性メトリックは、相関の大きさである、請求項６または８に記載の方法。
【請求項１７】
前記類似性メトリックは、類似性カーネルを用いて測定される、請求項６または８に記載の方法。
【請求項１８】
前記類似性カーネルは、動径基底カーネルである、請求項１７に記載の方法。
【請求項１９】
前記作用素は、シフト、縮尺変更、または回転、およびそれらの組み合わせを特徴付ける、請求項１に記載の方法。
【請求項２０】
前記作用素は、前記信号の変換を特徴付ける、請求項１に記載の方法。
【請求項２１】
前記変換の特定の特性が、パラメーターによって特徴付けられる、請求項２０に記載の方法。
【請求項２２】
前記測定ベクトルの数は、前記信号の次元数よりも少ない、請求項１に記載の方法。
【請求項２３】
前記測定ベクトルは、信号空間における単位球面上に一様に分布している、請求項１に記載の方法。
【請求項２４】
前記埋め込みを量子化するステップ
をさらに含む、請求項１に記載の方法。
【請求項２５】
前記埋め込みを前記比較するステップは、前記埋め込みのハッシュを用いる、請求項１または４に記載の方法。
【請求項２６】
前記関連付けるステップも、前記埋め込みのハッシュを用いて、インデックスエントリーを生成する、請求項３に記載の方法。
【請求項２７】
前記信号は、画像である、請求項１に記載の方法。
【請求項２８】
前記信号は、センサーによって生成される、請求項１に記載の方法。
【請求項２９】
前記センサーは、機械システムを検知するものである、請求項２８に記載の方法。
【請求項３０】
前記機械システムは、工場機器である、請求項２９に記載の方法。
【請求項３１】
前記センサーは、電気システムを検知するものである、請求項２９に記載の方法。
【請求項３２】
前記電気システムは、電力貯蔵システムである、請求項３１に記載の方法。
【請求項３３】
前記電力貯蔵システムは、電池を含む、請求項３２に記載の方法。
【請求項３４】
前記データベースに記憶された前記信号に関連付けられたメタデータを取り出すステップ
をさらに含む、請求項４に記載の方法。
【請求項３５】
作用素に対して不変である、信号の埋め込みを生成するシステムであって、
前記信号を取得する手段と、
前記取得する手段に接続されたプロセッサであって、
測定ベクトルの集合からの各ベクトルを用いて前記信号を測定して、対応する係数の集合を生成し、なお、前記測定は、各測定ベクトルと前記信号とを比較し、前記作用素を用いて各測定ベクトルおよび前記信号を変換し、
既定の基準に従って１つまたは複数の一致する係数の集合を選択し、
前記一致する係数を組み合わせて、前記信号の前記埋め込みを生成し、ここで、前記埋め込みは、作用素不変である、
ように構成されたプロセッサと
を備える、システム。
【請求項３６】
前記取得する手段は、センサーを含む、請求項３５に記載のシステム。
【請求項３７】
前記プロセッサは、クライアントであり、該クライアントは、クエリ信号の埋め込みを生成するように構成され、
信号および該信号のそれぞれの前記埋め込みを記憶するデータベースを備えるサーバーと、
前記クエリ信号の前記埋め込みを前記データベースに記憶された全ての前記信号の前記埋め込みと比較することと、
前記クエリ信号の前記埋め込みと一致する前記埋め込みに対応する前記データベース内の前記信号を取り出すことと
をさらに備える請求項３５に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、信号処理に関し、より詳細には、変換を受ける信号を比較することに関する。
【背景技術】
【０００２】
多くの用途では、変換を受けた画像を表す信号、音信号、または産業オートメーション信号等の信号を比較することが望ましい。これらの変換は、平行移動、回転、拡大縮小等を含むことができる。さらに、信号は、変換の或る態様を制御するパラメーターを用いてパラメーター化することができる。例えば、変換が回転である場合、パラメーターは、回転の角度とすることができる。同様に、変換が平行移動である場合、パラメーターは、平行移動の量とすることができる。
【０００３】
そのような比較が必要であるいくつかの例がある。例えば、多くの用途では、コーナー、車両、または顔の画像等の処理されている画像の構成要素を識別することが必要である。これらの構成要素を識別するには、実例またはテンプレートである顔または自動車の画像が、識別されるために処理されている画像の要素と比較されるべきである。しかしながら、処理されている画像内の顔または自動車は、必ずしも、実例の画像内の顔または自動車と同じ縮尺、位置、または向きを有しない。
【０００４】
同様に、多くの産業用途では、機器監視センサーから取得された信号を、適切な機器動作の例であるテンプレート信号と比較することが望ましい。これらの信号が類似していないとき、これは、機器の機能不良を示すものであり、オペレーターに警告を発するべきである。しかしながら、そのような信号は、多くの場合、テンプレート信号と比較して、時間が平行移動（遅延）している。
【０００５】
そのような比較を行うにはいくつかの手法がある。最も一般的なものは、第１の信号を第２の信号の全ての変換と比較し、最もよく一致する信号を選択することである。この一致の質は、これらの信号が変換の下でどれだけ類似しているかを示す。この手法の１つの例は、これらの信号の自己相関を求め、この自己相関のピークを選択することである。これは、複数の用途において非常に一般的な手法である。この比較は、多くの場合、「インプレース（その場）」で、すなわち、全ての変換を明示的に求めることなく、行われる可能性がある。
【０００６】
図１は、従来の信号比較技法の概略図である。信号１０１および１０２は、類似し得るが、例えば、時間の平行移動に起因して何らかの方法で変換されている場合がある。一方、２つの信号１０３および１０４は、変換を考慮に入れても類似しない場合がある。類似性を特徴付ける距離メトリックを求めることが望まれている。例えば、１つの実施の形態では、この距離は、ユークリッド距離である。通常、これは、相互相関１１０を用いて実行される。この相互相関は、全ての可能な変換（すなわち、時間の平行移動）の下で２つの信号の相関を求める。これによって、全ての変換の下で信号の対応する信号距離１１５が得られる。この相互相関および対応する距離から、最大相関１１１、および対応する最小距離１１６が求められる。
【０００７】
その手法に関する問題は、単一の信号を、例えば、データベースに記憶された２つ以上の信号と比較して類似性を求める必要があるときの、本来的な計算複雑さである。なぜならば、信号のペアの比較は、検討された変換のうちのいくつかに従って本質的に多くの信号を比較し、最もよく一致するものを選択するからである。この計算は、比較が「インプレース」であっても、かなり大規模になる可能性がある。この問題は、以下で説明する代替の不変の手法において軽減される。
【０００８】
１つの代替の手法は、元の変換に対して不変である方法で、元の信号をさらに変換することである。換言すれば、元の信号が、所望の不変性に従って異なるシフト、回転または縮尺等を有するときであっても、変換された信号は同じである。この変換された信号は、その後、比較され、この比較の出力は、信号の類似性を求めるのに用いられる。
【０００９】
この変換は、通常、上記で説明したような信号の全てのペアの比較よりも、はるかに低い計算集約性を有する。このため、或る信号とデータベース内の多くの信号との比較をはるかに効率的にすることができる。他方、不変性手法に関する問題のうちの１つは、多くの場合、有意義な比較を行うのに十分な情報も保持する適切な不変性を有する変換を見つけることが困難または不可能であるということである。
【００１０】
類似の手法は、信号から所望の変換に対して不変である特徴を抽出するが、信号全体を変換しないものである。その場合、それらの特徴が比較され、一致するものが求められる。これは、縮尺不変特徴変換（ＳＩＦＴ）または勾配の圧縮ヒストグラム（ＣＨｏＧ）および他の類似の方法等の多くの一般的な画像記述子において採用される手法である。その手法の利点は、不変の記述子を抽出することが信号全体を変換することよりも容易であるということである。欠点は、これらの記述子が通常、画像内の物体の検出等の特定の用途および作業を念頭に置いて設計され、特に、この作業向けに調節されているということである。異なる作業ごとに、その作業に対して調節された適切な特性を有する異なる記述子を設計する必要がある。
【発明の概要】
【００１１】
上記問題を克服し、計算効率性を維持するために、本発明の実施の形態は、作用素不変埋め込み（operator invariant embeddings：演算子不変埋め込み）を生成する方法を提供する。これらの埋め込みは、従来の手法の欠点を伴うことなく、従来の手法の利点を組み合わせる方法を提供する。埋め込みは、従来の手法と異なり、汎用的であり、用途ごとまたは信号のタイプごとに特に設計する必要がない特徴抽出メカニズムを提供する。
【００１２】
さらに、埋め込み生成から得られた或る特定の情報を保持することが所望される場合、埋め込みは、作用素不変変換とみなすことができる。この場合、信号を埋め込みから回復することができる。埋め込みの計算は、信号を中間信号の集合およびそれらの全ての変換と比較することによって求めることができる。
【００１３】
後者の場合、各信号は、少数の中間信号の全ての変換と比較される。これらの比較は、他の信号から抽出された特徴と比較される特徴集合としての機能を果たす。このため、信号を、他の全ての信号の全ての変換と比較する計算コストは、削減される。なぜならば、網羅的な比較は、少数のテンプレート信号の変換の場合にしか行われないからである。この比較の結果が特徴であり、この特徴は、他の全ての信号から抽出された特徴と比較され、これは、はるかに高速な比較である。
【図面の簡単な説明】
【００１４】
【図１】従来の信号比較技法の概略図である。
【図２】本発明の１つの実施の形態による埋め込みを生成するプロセスの概略図である。
【図３Ａ】本発明の実施の形態による単一の係数または特徴を抽出するプロセスの概略図である。
【図３Ｂ】本発明の実施の形態による単一の係数または特徴を抽出するプロセスの概略図である。
【図４】本発明の１つの実施の形態による信号クエリ実行の概略図である。
【図５】本発明の代替の実施の形態による信号クエリ実行の概略図である。
【図６】本発明の代替の実施の形態によるリモートに生成されたクライアント／サーバークエリの概略図である。
【図７】本発明の１つの実施の形態による図３Ａおよび図３Ｂに示す概略図に対応する擬似コードである。
【発明を実施するための形態】
【００１５】
作用素不変埋め込み
図２は、作用素に対して不変である信号の埋め込みを生成する方法の１つの実施の形態を示している。測定ベクトルｅｉ  ２１０のそれぞれは、取得された信号ｘ  ２０１を測定するのに用いられ、ｘの埋め込みをｙ  ２４０として生成する。
【００１６】
信号は、前処理ステップにおいて、例えばセンサー２０５、例えばカメラ、マイクロフォン、または他のタイプのセンサーを用いて取得することができる（２０５）。信号は、視覚信号、例えば画像若しくはビデオ、オーディオ信号、例えば音声および音楽、または産業オートメーション信号とすることができる。代替的にまたは付加的に、信号は、当該信号から特徴を抽出するアプリケーション、例えば、画像処理アプリケーションまたは音声処理アプリケーションによって取得することができる。信号は、工場機器、機械システム、電池を含む電力貯蔵システム等の電気システムを検知するセンサーによって取得することもできる。
【００１７】
信号２０１は、測定プロセス２２０を用いて一組の測定ベクトルｅｉ  ２１０のそれぞれによって測定され、一組の対応する係数２３０が生成される。全ての係数がベクトルに組み合わされて、埋め込み２４０  ｙが生成される。
【００１８】
本方法は、当該技術分野において知られているように、バスによってメモリおよび入力／出力インターフェースに接続されたプロセッサ２００において実行することができる。
【００１９】
その後、埋め込みは、以下で説明するように、信号の類似性を比較するのに用いることができる。
【００２０】
信号類似性
２つの信号を比較するために、類似度または非類似度が、多くの場合に用いられる。類似度は、２つの信号が類似しているときは高く、２つの信号が類似していないときは低い。非類似度は、信号が類似しているときは低く、信号が類似していないときは高い。
【００２１】
非類似度の一例は、信号距離であり、これは、信号比較において非常に一般的に用いられる尺度である。対象となる信号の集合をＳとし、２つの信号ｘ、ｘ’∈Ｓが与えられると、
【数１】
0006271092.tif 000002
距離は、以下のように定義される。
【００２２】
【数２】
0006271092.tif 000003
【００２３】
ここで、ｐ≧１である。非常に類似している信号は、これらの信号が類似しているとき、小さな距離を有する。すなわち、ｘ＝ｘ’であり、距離は０である。
【００２４】
一方の信号が、他方の信号の倍数である場合、いくつかの特定のアプリケーションは、それらの信号を同じであるとみなすことができるが、
【数３】
0006271092.tif 000004
距離は、大きくなる可能性がある。その理由のために、多くの場合に、代替の類似度が用いられる。この代替の類似度は、最初に信号を正規化することと、次にそれらの信号の
【数４】
0006271092.tif 000005
距離を求めることと、を含む。この尺度は、以下の式となる。
【００２５】
【数５】
0006271092.tif 000006
【００２６】
別の部類の有用な類似度は、ダイバージェンスである。これらのダイバージェンスは、距離に類似している。例えば、ブレグマン（Bregman）ダイバージェンスが、多くの場合、信号を比較するのに用いられる。ブレグマンダイバージェンスは、三角不等式も対称性も満たさない場合もあるし、満たす場合もある。
【００２７】
最も有用な類似度のうちの１つは、信号相関ｃであり、以下のように定義される。
【００２８】
【数６】
0006271092.tif 000007
【００２９】
距離尺度と同様に、信号にスカラーを乗算することによって、相関尺度によって測定されるそれらの信号の類似性が影響を受ける可能性がある。そのような場合、正規化された信号を用いる相関係数は、以下のとおりである。
【００３０】
【数７】
0006271092.tif 000008
【００３１】
複数の用途において、互いに逆である２つの信号、すなわち、ｘ≒−ｘ’、または或るｃ＞０についてｘ≒−ｃｘ’は、引き続き類似しているとみなされるべきである。そのような用途では、相関または相関係数の大きさ、すなわち、｜ｃ（ｘ，ｘ’）｜または｜ρ（ｘ，ｘ’）｜は、信号のより適切な類似度である。
【００３２】
多くの場合に好ましい代替の類似度は、動径基底カーネルとして知られている関数に基づいている。動径基底カーネルは、カーネルが２つの信号の距離｜｜ｘ−ｘ’｜｜ｐの関数にすぎないという定義特性（defining property）を有する。すなわち、カーネルは、或る適切なｋ（・）およびｐについて以下のように定義される。
【００３３】
【数８】
0006271092.tif 000009
【００３４】
最も一般的な動径基底カーネルのうちの２つが、ラプラシアンカーネルおよびガウシアンカーネルであり、それぞれ以下のように定義される。
【００３５】
【数９】
0006271092.tif 000010
【００３６】
もちろん、他にもいくつかの類似度が存在し、この後に続く展開において用いることができる。
【００３７】
本発明の実施の形態による作用素不変埋め込みを設計するために、信号ｘ、ｘ’に加えて、パラメーターαによってパラメーター化された作用素Ｔα：Ｓ→Ｓを考慮する。埋め込みは、この作用素に対して不変であるように設計される。作用素Ｔαは、シフト、縮尺変更、回転等が画像等の信号をどのように変換するのかを特徴付ける。この作用素は、複数の変換、例えば、回転および縮尺変更の双方、若しくは回転およびシフトの双方、または３つ全てを特徴付けることもできる。
【００３８】
パラメーターαは、変換の特定の特性を特徴付ける。例えば、変換が回転である場合、αは回転の角度とすることができる。変換が平行移動である場合、αは平行移動の量とすることができる。作用素が複数の変換を組み合わせる場合、αは、各変換に必要とされるパラメーターのタプレット（tuplet）とすることができ、例えば、平行移動量および回転量の双方を含む。パラメーターαは、例えば、回転における値の範囲α∈Ｒを取ることができる。ここで、Ｒは、０〜２πまたはπ〜πの角度の範囲とすることができる。
【００３９】
パラメーターαの各値について、Ｔαを反転する変換に応じた反転値
【数１０】
0006271092.tif 000011
が存在する。すなわち、
【数１１】
0006271092.tif 000012
である。例えば、αの分だけ右への回転は、αの分だけ左への回転、すなわち−αの分だけ右への回転を用いて反転される。この回転は、２π−αの分だけ右への回転とも等価である。同様に、縮尺変更パラメーターαは、１／αによる縮尺変更を用いて反転される。
【００４０】
埋め込みは、作用素Ｅ：Ｓ→Ｖでもある。ここで、Ｓは、上記のように信号空間であり、Ｖは、埋め込み空間である。通常、埋め込み空間Ｖは、或るＭについて、
【数１２】
0006271092.tif 000013
または
【数１３】
0006271092.tif 000014
である。この作用素は、全てのα∈Ｒおよび全てのｘ∈ＳについてＥ（ｘ）≒Ｅ（Ｔα（ｘ））である場合、Ｔαに対してほぼ不変であり、この近似式は、Ｅ（・）がＴα（・）に対して正確に不変である場合、正確な等式となる。
【００４１】
非類似度は、一般に、ｄ（ｘ，ｘ’）を用いて表されるか、または用途によって適宜、類似度ｓ（ｘ，ｘ’）を用いて表される。類似性は、ｘがｘ’に類似している場合には高い値を有し、類似していない場合には低い値を有する。非類似性は、ｘがｘ’に類似している場合には低い値を有し、類似していない場合には高い値を有する。
【００４２】
Ｅ（・）を生成するために、複数の測定ベクトルｅｉ，ｉ＝１，・・・，Ｍ  ２１０が用いられる。通常の実施の形態では、ベクトルは、ランダムに生成される。ベクトルの個数Ｍは、用途に依存する。例えば、Ｍは、速度と精度との間のトレードオフに基づくことができる。Ｍが大きいほど、精度は高くなる。一般に、Ｍは、信号の次元数よりもはるかに小さくあるべきであり、また、比較される信号の数に依存することができる。例えば、以下で説明するように、データベースのクエリおよび検索の用途では、Ｍは、データベース内の信号の数とともに対数的に増加する。通常の数は、用途タイプに依存する。例えば、埋め込みを用いて、画像内でテンプレートを探すとき、Ｍは、数百未満、通常は、２００未満であることが予想される。
【００４３】
信号空間Ｓがどのようなものであるのかに応じて、ベクトルは、複数の方法で生成することができる。例えば、ベクトルは、Ｓにおける単位球面上の一様分布を用いて生成することができる。または、例えば、
【数１４】
0006271092.tif 000015
または
【数１５】
0006271092.tif 000016
である場合、各ｅｉは、ランダムな実Ｎ次元ベクトルまたは複素Ｎ次元ベクトルとして生成することができ、各ベクトル成分は、ｉ．ｉ．ｄ．実正規分布またはｉ．ｉ．ｄ．複素正規分布から取り出される。代替的に、分布は、一様分布、ラーデマッヘル（Rademacher）分布、または他の部分ガウス実分布若しくは部分ガウス複素分布とすることができる。
【００４４】
測定プロセス２２０の実施の形態は、図３Ａおよび図３Ｂを参照して、より詳細に説明される。
【００４５】
測定プロセス２２０を用いて信号２０１を測定するために、本発明の１つの実施の形態は、パラメーター集合から十分に微細な有限格子
【数１６】
0006271092.tif 000017
を生成する。すなわち、
【数１７】
0006271092.tif 000018
である。ここで、
【数１８】
0006271092.tif 000019
は、格子点の数である。一般に、格子が、全てのパラメーターα∈Ｒについて十分に微細である場合、十分に小さな許容誤差εについて
【数１９】
0006271092.tif 000020
である。例えば、αが平行移動および回転の双方を捕捉するものである場合、複数の許容誤差値を有する同様の保証が、マルチパラメーター格子用に提供されるべきである。ほとんどの実施態様において、格子は、パラメーターと、当該パラメーターを反転したものとを含むことが必要でなくても、これらを含む。すなわち、
【数２０】
0006271092.tif 000021
である。
【００４６】
図３Ａは、各格子点につき１つである複数の変換を用いて各測定ベクトル２１０を変換するのに格子点がどのように用いられるのかを、例によって示している。特に、各格子点について、変換
【数２１】
0006271092.tif 000022
３２０は、測定ベクトルｅｉを変換するのに用いられる。変換された各測定ベクトルは、類似性メトリックまたは非類似性メトリックを用いて信号２０１と比較される（３１０）。一致するものが選択され、信号と、変換された測定ベクトルの一致するものとの内積が求められる（３４０）。好ましい実施の形態では、一致するものは、選択されたメトリックに従って、最もよく一致したものとなるように選択される（３３０）。しかしながら、一致するものは、例えば、２番目に最もよく一致するものまたは３番目に最もよく一致するものとなる可能性もあるし、同じ測定ベクトルの異なる変換を用いると２つ以上の一致するものとなる可能性もある。図における例では、最もよく一致するものは、
【数２２】
0006271092.tif 000023
を通じた変換である。内積の結果ｙｉは、埋め込み２４０  ｙのｉ番目の係数２３０である。
【００４７】
代替のまたは追加の実施の形態が、図３Ｂに示されている。図３Ｂにおいて、信号２０１は、変換３２０において各パラメーターを用いて変換され、その結果は、類似性メトリックまたは非類似性メトリックを用いて測定ベクトル２１０と比較される（３１０）。係数２３０を生成するために、選択された一致するもの３３０を用いて、変換された信号と測定ベクトルとの内積３４０が計算される。
【００４８】
図３Ａおよび図３Ｂの概略図に従って埋め込みを求める手順の擬似コードが図７に示されている。
【００４９】
好ましい実施の形態では、各測定ベクトルについて、本手順は、最初に、この測定ベクトルと信号との類似性を最大にするこの測定ベクトルの変換を求める（ステップ２）。これを行うために、本手順は、用途によって非類似性関数および類似性関数のうちのいずれが利用可能であるかに応じて、非類似性関数ｄ（・，・）を最小にするかまたは類似性関数ｓ（・，・）を最大にする。次に、本手順は、この変換を用いて信号を測定する（ステップ３）。ステップ２および３は、それぞれ以下の公式に置き換えることができることに留意されたい。
【００５０】
【数２３】
0006271092.tif 000024
【００５１】
全てではないが、ほとんどの変換において、双方の公式は等価であり、交換可能に用いることができる。
【００５２】
図７における公式は、図３Ａに示す実施の形態に対応し、（８）および（９）における代替の公式は、図３Ｂの実施の形態に対応する。図７における擬似コードは、通常、実際のシステムにおいて実施が容易であり、特に、多数の信号を測定するときに実施が容易である。
【００５３】
埋め込み関数の主な出力は、測定値のベクトルｙである。任意選択で、用途がシフトを必要としている場合、この関数は、最適な変換パラメーター
【数２４】
0006271092.tif 000025
も返す。いくつかの実施の形態では、パラメーターを用いて、埋め込みから信号を再構成または近似的に再構成することができる。パラメーターを用いて、類似している信号の相対変換を見つけることもできる。
【００５４】
２つの信号ｘ、ｘ’およびそれらの埋め込みｙ＝Ｅ（ｘ）、ｙ’＝Ｅ（ｘ’）が与えられると、次に、それらの類似性または非類似性は、Ｖにおける近似的に定義された類似性関数ｓ（ｙ，ｙ’）または非類似性関数ｄ（ｙ，ｙ’）を用いて評価することができる。この類似性または非類似性は、パラメーター集合Ｒから取得されたパラメーターを用いて、ｘの全ての変換をｘ’の全ての変換と比較したときの最大の類似性または最小の非類似性を近似的に表す。
【００５５】
実施の形態が、埋め込みを計算するのに用いられる最適な変換パラメーターも保持している場合、２つの信号を埋め込むのに用いられるパラメーターを比較して、これらの信号を整合または一致させる最適な変換を生成することができる。例えば、パラメーターの平均若しくは中央の相対値、または最もよく一致する係数の平均若しくは中央の相対値は、一方の信号が他方の信号に一致するために受けるべき相対変換の推定値とすることができる。
【００５６】
埋め込みベクトルは、適切な量子化関数を用いてｑ＝Ｑ（ｙ）に量子化することもできる。これは、例えば、埋め込みを記憶または送信すべきであり、用いられるビットレートを削減する必要がある場合に、非常に有用である。
【００５７】
埋め込みとの比較に基づいて信号取り出しの速度をさらに改善するために、埋め込みのハッシュｈ＝Ｈ（ｙ）を求めることもでき、このハッシュは、さらに局所鋭敏ハッシュ（ＬＳＨ：locality sensitive hash）とすることができる。
【００５８】
使用法およびプロトコル
これらの埋め込みのいくつかの使用法がある。最も重要なもののうちの１つは、データベース、例えば画像のデータベースからの作用素不変信号取り出しである。この用途では、着信したクエリ信号に類似した信号を得るために、信号のデータベースが、作用素不変方法を用いて検索される。データベースは、当該データベース内の全ての信号の埋め込みを求め、これらの埋め込みをインデックスとしてデータベースに記憶することによる適切な作用素不変埋め込みを用いて準備される。
【００５９】
クエリが実行されると、クエリ信号の埋め込みが最初に求められる。この埋め込みは、データベース内の全ての信号の埋め込みと比較される。用途に応じて、最も密接に一致するもの若しくは複数の最も密接に一致するものが返されるか、または密接に一致するものがデータベースに存在する表示若しくは存在しない表示が返される。これは、クエリ信号を、パラメーター空間内の全てのパラメーターについてのデータベース内の全ての信号の全ての変換と比較するという代替形態と対比したとき、はるかに高速な比較である。データベースを準備する初期計算コストは、特に、多くのクエリを実行する必要があるときは少ない。
【００６０】
データベース内の全ての信号から、局所鋭敏ハッシュがそれらの埋め込みから求められ、信号およびその埋め込みとともに記憶されている場合に、クエリ時間をさらに削減することができる。クエリが実行されると、ハッシュが、同じハッシュ関数を用いて埋め込みから求められる。同じハッシュを有するデータベース内の少数の信号のみが比較のために選択される。
【００６１】
図４および図５は、本発明の実施の形態による、信号のデータベースを準備し、このデータベースにクエリする方法を概略的に示している。
【００６２】
図４は、上記で説明した埋め込みをハッシュすることなくどのように用いて、信号のデータベース４５０を準備し、このデータベースにクエリすることができるのかを示している。データベースは、最初に、次のように準備される（４２０）。各信号ｘ  ４２１について、埋め込みｙが計算される（４２２）。この埋め込みは、信号とともにペア（ｘ，ｙ）４２３を形成する。このペアは、インデックスエントリーである。全てのインデックスエントリーが、データベース４５０に記憶されたインデックスに記憶され、当該技術分野において既知のインデックス付け方法を用いてデータベースをインデックス付けするのに用いられる。
【００６３】
クエリ信号ｘ’  ４１１を用いてデータベースにクエリするために、このクエリ信号の埋め込みｙ’  ４１２を計算することによってクエリが準備される（４１０）。クエリは、クエリ信号の埋め込みｙ’をデータベース４５０内の信号のそれぞれの埋め込みｙと比較する（４１３）ことによって実行される。一致する信号が、クエリ結果として選択される。最もよく一致するものまたはいくつかの一致するものは、クエリ結果４１４を含む。これらのステップも、データベースに接続されたプロセッサにおいて実行することができる。
【００６４】
クエリの出力４１５は、クエリ結果に基づいている。例えば、この出力は、一致する信号自体とすることもできるし、一致する信号に関連付けられたメタデータとすることもできるし、ユーザーに対してアクセスを許可するかまたは不許可とするような、一致する信号に基づく判定とすることもできる。
【００６５】
図５は、埋め込みをハッシュとともにどのように用いて、信号のデータベースを準備し、このデータベースにクエリすることができるのかを示している。図４と同様に、データベースは、最初に、各信号ｘ  ５２１の埋め込みｙを計算する（５２２）ことによって準備される（５２０）。ハッシュｈは、埋め込み５２３から計算される。全ての信号からのハッシュは、インデックスエントリーであり、データベース５５０のインデックス５２４を作成するのに用いられる。このインデックスは、当該技術分野において既知のインデックス付け方法を用いて、信号と、埋め込みのハッシュによるそれらの信号の埋め込みとをインデックス付けする。
【００６６】
クエリは、同様の形式で準備される（５１０）。クエリ信号５１１の埋め込みが計算され（５１２）、埋め込みのハッシュが計算される（５１３）。ハッシュと、全ての実施の形態ではなくいくつかの実施の形態では埋め込み自体とを用いて、データベースがクエリされる。
【００６７】
クエリは、データベースのインデックスから、クエリハッシュと同じハッシュを有する全ての信号のリストを取り出すことによって実行される（５１４）。これらは全て、データベースからの一致する信号である。クエリ埋め込みも取り出しにおいて用いられる場合、一致する信号の数を減らすために、取り出された信号の埋め込みは、クエリ信号の埋め込みとも比較することができる。これらの一致する信号がクエリ結果５１５である。いくつかの実施の形態では、複数のハッシュを用いて、当該技術分野においてよく知られた方法を用いた取り出しの精度を高めることができる。
【００６８】
図４における実施の形態と同様に、この実施の形態では、クエリの出力５１６は、クエリ結果に基づいている。例えば、この出力は、一致する信号自体とすることもできるし、一致する信号に関連付けられたメタデータとすることもできるし、ユーザーに対してアクセスを許可するかまたは不許可とするような、一致する信号に基づく判定とすることもできる。
【００６９】
図６に示す好ましい実施の形態では、クエリがリモートに生成される。すなわち、クエリ準備５１０を実行し、サーバー６０２に記憶されたデータベース５５０にネットワークを用いてクエリするクライアント６０１が存在する。このデータベースは、上記で説明したプロトコルを用いて既に準備されている（５２０）。そのような場合、クライアントは、信号、または信号の圧縮したものを送信することができ、データベースは、場合によっては信号を伸長した後に上記プロトコルに従う。代替的に、クライアントは、他の或る方法で埋め込みを求め、埋め込みを量子化し、または埋め込みを符号化若しくは圧縮することができ、この埋め込みをサーバーに送信して、検索プロトコル５１４を続けることができる。サーバーは、一致する信号５１５を取り出し、クエリ出力５１６をクライアントに送信する。図６は、図５において説明したインデックス付きデータベースを用いたクライアント／サーバーの実施の形態を例示しているが、同様の方法で、図４において説明したデータベース準備に基づくクライアント／サーバーの実施の形態を実施することも可能である。
【図１】
0006271092.tif 000026
【図２】
0006271092.tif 000027
【図３Ａ】
0006271092.tif 000028
【図３Ｂ】
0006271092.tif 000029
【図４】
0006271092.tif 000030
【図５】
0006271092.tif 000031
【図６】
0006271092.tif 000032
【図７】
0006271092.tif 000033