(57)【要約】【課題】  ランダム信号変換および／またはその適用例を提供する技法を開示すること。【解決手段】  より具体的には、無作為に選択された基底関数を信号に適用することによって、信号（例えば、オーディオ信号、画像信号、またはビデオ信号）を変換する。ランダム信号変換の適用例として、圧縮、雑音除去、ハッシング、識別、認証、およびデータ埋め込み（例えば、電子透かし）などがあるが、これらに限定されるものではない。【選択図】  図１
2005346041.tif 000002
【特許請求の範囲】
【請求項１】
複数の生成された基底関数を無作為に選択するステップと、
前記無作為に選択した基底関数を信号に適用するステップと
を備えたことを特徴とする方法。
【請求項２】
前記基底関数は、１次元関数、２次元関数、および３次元関数からなる群の１つまたは複数の項目から選択される１組の関数から生成されることを特徴とする請求項１に記載の方法。
【請求項３】
前記基底関数の各々は、母ｒａｎｄｌｅｔに施すスケーリング、回転、平行移動、離散化、および正規化からなる群から選択される操作によって生成されることを特徴とする請求項１に記載の方法。
【請求項４】
前記基底関数は、スケーリング操作および回転操作のうち限られた操作だけを許容することによって制限されることを特徴とする請求項３に記載の方法。
【請求項５】
前記各基底関数を他のすべての基底関数とは独立に定義する代わりに、平行移動を施さない基底関数からなるライブラリが、前記母ｒａｎｄｌｅｔにスケーリングおよび回転を無作為に施すことによって生成されることを特徴とする請求項３に記載の方法。
【請求項６】
スケーリングを施すとき、ウェーブレット族が選択されることを特徴とする請求項３に記載の方法。
【請求項７】
前記母ｒａｎｄｌｅｔは、ガウスｒａｎｄｌｅｔ、ハーフｒａｎｄｌｅｔ、メキシカンハットｒａｎｄｌｅｔ、ウェーブレットｒａｎｄｌｅｔ、およびそれらの組合せからなる群から選択されることを特徴とする請求項３に記載の方法。
【請求項８】
前記適用するステップは、
前記各選択した基底関数を前記信号上に射影するステップと、
前記信号から各射影を減算するステップと、
前記各選択した基底関数を前の基底関数の残余上に射影するステップと、
前記各基底関数の変換係数を計算するステップと、
前記変換係数を量子化するステップと、
前記量子化変換係数を保存するステップと、
次の残余を計算するステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項９】
前記方法は、前記信号を圧縮するために使用され、および前記適用するステップは、
前記各選択した基底関数を前記信号上に射影するステップと、
前記信号から各射影を減算するステップと、
前記各基底関数の変換係数を計算するステップと、
前記変換係数を量子化するステップと、
選択された前記量子化変換係数を取り除くステップと、
前記量子化変換係数を保存するステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項１０】
前記方法は、比較的小さな基底関数をデエンファシスし、および残った基底関数を重ね合わせることによって、前記信号の雑音を除去するために使用されることを特徴とする請求項１に記載の方法。
【請求項１１】
前記方法は、前記信号をハッシングするために使用され、および前記適用するステップは、
前記信号をスケーリングするステップと、
前記各選択した基底関数を前記スケーリングした信号上に射影するステップと、
前記各基底関数の変換係数を計算するステップと、
前記変換係数を量子化するステップと、
前記量子化変換係数に誤り訂正を適用するステップと、
前記量子化変換係数を保存するステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項１２】
前記ハッシュされた信号の値は、識別または認証のために利用されることを特徴とする請求項１１に記載の方法。
【請求項１３】
前記方法は、前記信号に電子透かしを入れるために使用され、および前記適用するステップは、
前記信号をスケーリングするステップと、
前記各選択した基底関数を前記スケーリングした信号上に射影するステップと、
各基底関数の変換係数を計算するステップと、
前記変換係数に電子透かしを適用するステップと、
前記電子透かしを前記信号に挿入するステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項１４】
前記適用するステップは、変換された信号を提供し、および前記変換された信号は、
前記各基底関数に対応する変換係数を乗算するステップと、
前記乗算ステップの結果を合算するステップと
を含む操作によって再構成されることを特徴とする請求項１に記載の方法。
【請求項１５】
信号を受信し、および無作為に選択された複数の基底関数を前記信号に適用するｒａｎｄｌｅｔ変換（ＲＴ）モジュールと、
前記ＲＴモジュールに結合されて、前記ＲＴモジュールによって利用される乱数を生成し、前記無作為に選択された基底関数を選択する疑似乱数生成器と
を備えたことを特徴とするシステム。
【請求項１６】
前記疑似乱数生成器は、前記乱数を生成する乱数種として秘密鍵を利用することを特徴とする請求項１５に記載のシステム。
【請求項１７】
前記乱数種は、ビットストリームであることを特徴とする請求項１６に記載のシステム。
【請求項１８】
前記基底関数の各々は、母ｒａｎｄｌｅｔにスケーリング、回転、平行移動、離散化、および正規化を施すことによって生成されることを特徴とする請求項１５に記載のシステム。
【請求項１９】
命令を保存する１つまたは複数のコンピュータ読取り可能な媒体であって、前記命令は、実行されたときに、
複数の生成された基底関数を無作為に選択するステップと、
前記無作為に選択した基底関数を信号に適用するステップと
を備えた操作を実行するようマシンに指令することを特徴とする１つまたは複数のコンピュータ読取り可能な媒体。
【請求項２０】
前記基底関数は、１次元関数、２次元関数、および３次元関数からなる群の１つまたは複数の項目から選択される１組の関数から生成されることを特徴とする請求項１９に記載の１つまたは複数のコンピュータ読取り可能な媒体。
【請求項２１】
前記基底関数の各々は、母ｒａｎｄｌｅｔにスケーリング、回転、平行移動、離散化、および正規化を施すことによって生成されることを特徴とする請求項１９に記載の１つまたは複数のコンピュータ読取り可能な媒体。
【請求項２２】
前記基底関数は、スケーリング操作および回転操作のうち限られた操作だけを許容することによって制限されることを特徴とする請求項２１に記載の１つまたは複数のコンピュータ読取り可能な媒体。
【請求項２３】
前記各基底関数を他のすべての基底関数とは独立に定義する代わりに、平行移動を施さない基底関数からなるライブラリが、前記母ｒａｎｄｌｅｔにスケーリングおよび回転を無作為に施すことによって生成されることを特徴とする請求項２１に記載の１つまたは複数のコンピュータ読取り可能な媒体。
【請求項２４】
スケーリングを施すとき、ウェーブレット族が選択されることを特徴とする請求項２１に記載の１つまたは複数のコンピュータ読取り可能な媒体。
【請求項２５】
前記母ｒａｎｄｌｅｔは、ガウスｒａｎｄｌｅｔ、ハーフｒａｎｄｌｅｔ、メキシカンハットｒａｎｄｌｅｔ、ウェーブレットｒａｎｄｌｅｔ、およびそれらの組合せからなる群から選択されることを特徴とする請求項２１に記載の１つまたは複数のコンピュータ読取り可能な媒体。
【請求項２６】
前記適用するステップは、
前記各選択した基底関数を前記信号上に射影するステップと、
前記信号から各射影を減算するステップと、
前記各選択した基底関数を前の基底関数の残余上に射影するステップと、
前記各基底関数の変換係数を計算するステップと、
前記変換係数を量子化するステップと、
前記量子化変換係数を保存するステップと、
次の残余を計算するステップと
を含むことを特徴とする請求項１９に記載の１つまたは複数のコンピュータ読取り可能な媒体。
【請求項２７】
前記操作は、前記信号を圧縮するために使用され、および前記適用するステップは、
前記各選択した基底関数を前記信号上に射影するステップと、
前記信号から各射影を減算するステップと、
前記各基底関数の変換係数を計算するステップと、
前記変換係数を量子化するステップと、
選択された前記量子化変換係数を取り除くステップと、
前記量子化変換係数を保存するステップと
を含むことを特徴とする請求項１９に記載の１つまたは複数のコンピュータ読取り可能な媒体。
【請求項２８】
前記操作は、比較的小さな基底関数をデエンファシスし、および残った基底関数を重ね合わせることによって、前記信号の雑音を除去するために使用されることを特徴とする請求項１９に記載の１つまたは複数のコンピュータ読取り可能な媒体。
【請求項２９】
前記操作は、前記信号をハッシングするのに使用され、および前記適用するステップは、
前記信号をスケーリングするステップと、
前記各選択した基底関数を前記スケーリングした信号上に射影するステップと、
前記各基底関数の変換係数を計算するステップと、
前記変換係数を量子化するステップと、
前記量子化変換係数に誤り訂正を適用するステップと、
前記量子化変換係数を保存するステップと
を含むことを特徴とする請求項１９に記載の１つまたは複数のコンピュータ読取り可能な媒体。
【請求項３０】
前記ハッシュされた信号の値は、識別または認証のために利用されることを特徴とする請求項２９に記載の１つまたは複数のコンピュータ読取り可能な媒体。
【請求項３１】
前記操作は、前記信号に電子透かしを入れるために使用され、および前記適用するステップは、
前記信号をスケーリングするステップと、
前記各選択した基底関数を前記スケーリングした信号上に射影するステップと、
前記各基底関数の変換係数を計算するステップと、
前記変換係数に電子透かしを適用するステップと、
前記電子透かしを前記信号に挿入するステップと
を含むことを特徴とする請求項１９に記載の１つまたは複数のコンピュータ読取り可能な媒体。
【請求項３２】
前記適用するステップは、変換された信号を提供し、および前記変換された信号は、
各基底関数に対応する変換係数を乗算するステップと、
前記乗算ステップの結果を合算するステップと
を含む操作によって再構成されることを特徴とする請求項１９に記載の１つまたは複数のコンピュータ読取り可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、信号変換に関し、より詳細には、ランダム信号変換（ｒａｎｄｏｍｉｚｅｄ  ｓｉｇｎａｌ  ｔｒａｎｓｆｏｒｍ）および／またはその適用例に関する。
【背景技術】
【０００２】
デジタル通信が一層の普及をみせるなかで、伝送デジタルデータの保護および／または認証の必要性がますます高まっている。デジタルデータを運ぶデジタル信号は、（必ずではないにしても）多くの場合、伝送される前に、（例えば、変換によって）一定のフォーマットに変形される。例えば、デジタルデータを含むファイルは、インターネットを介して送信する前に、圧縮することができる。
【０００３】
より高性能なコンピュータ、高速インターネット接続、および優れた圧縮技術を、大多数のユーザが利用できるようになったことで、デジタル媒体コンテンツに対する要望が、これまで以上に大きなものとなっている。消費者は、文字通り何百万もの音楽および映像の中からお気に入りのものにいつでも瞬時にアクセスできるという、デジタル配信がもたらした利便性を歓迎している。消費者は、テレビ放送に匹敵する滑らかさで、音楽をハードドライブまたはパーソナルコンピュータのハードドライブにダウンロードまたはストリーム受信することができる。
【０００４】
しかし、デジタルコンテンツに対する要望の高まりとともに、デジタルコンテンツの不正利用の可能性も高まっている。セキュリティ対策が施された配信システムが適切に機能していないと、コンテンツ所有者の許可がなくても、デジタル媒体ファイルをコピーしたり、より小さなファイルに圧縮したりすることが簡単にできてしまう。これらのファイルは、インターネットを介して伝送され、他人が自由に使用したり、配信したりできるものになる。このような行為は、何千ものメディア企業、レコード会社、映画会社、およびレコーディングアーティストが保有する著作権を侵害する。さらに、そのような不正利用は、これらの関係者から多額の収益を奪ってもいる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
現在行われている対策の１つは、不正利用を抑制するためにデジタルコンテンツを暗号化することである。しかし、この対策だと、オーバヘッドが余計にかかるようになり、信号変換を利用するシステムの速度低下を招くことになり得る。
【０００６】
したがって、性能の低下を抑えながら、強化されたセキュリティ機能を提供する信号変換方法が求められている。
【課題を解決するための手段】
【０００７】
ランダム信号変換および／またはその適用例を提供するための技法を開示する。より具体的には、無作為に選択された基底関数を信号に適用することによって、信号（例えば、オーディオ信号またはビデオ信号）を変換する。ランダム信号変換の適用例として、圧縮、雑音除去、ハッシング、識別、認証、およびデータ埋め込み（例えば、電子透かし）などがあるが、これらに限定されるものではない。
【０００８】
添付の図面を参照しながら詳細な説明を行う。図面中、参照番号の左端の数字は、その参照番号が最初に出現した図面を表す。異なる図面で同じ参照番号が使用されている場合、その対象が類似または同一の項目であることを示している。
【発明を実施するための最良の形態】
【０００９】
以下の開示は、概して、信号変換を改善する技法について説明したものである。より具体的には、妥当な性能を維持しながら、セキュリティ機能を提供するため、本明細書でｒａｎｄｌｅｔ変換（ＲＴ：ｒａｎｄｌｅｔ  ｔｒａｎｓｆｏｒｍ）と呼ばれる信号変換の一族を（オーディオ信号および／またはビデオ信号などの）信号に適用する。この一族のメンバである各変換は、秘密鍵（Ｋ）に基づいた乱数または疑似乱数によって選択される１組の基底関数（本明細書では「ｒａｎｄｌｅｔ」とも呼ばれる）を使用する。説明する様々な実施形態において、ＲＴを適用することによって、データ埋め込み（例えば、電子透かし）、識別、認証、ハッシング、雑音除去、および／または圧縮を改善することができる。
【００１０】
ｒａｎｄｌｅｔ変換の概要
図１に、例示的なｒａｎｄｌｅｔ変換（ＲＴ）システム１００を示す。ＲＴモジュール１０２は、オーディオ信号および／またはビデオ信号などの入力データ（ステップ１０４）を受信する。信号は、コンピュータ読取り可能な媒体、（例えば、イントラネット、インターネット、無線ネットワークなどの）コンピュータネットワークに接続された入力源、（図１１のコンピューティング環境を参照しながら説明するような）その他の入力源から供給することができる。
【００１１】
ＲＴモジュール１０２は、無作為に選択された基底関数（ステップ１０６）を使用して、入力信号を変換する。選択の無作為性は、疑似乱数生成器（ステップ１０８）が生成する乱数（または複数の乱数）によってもたらされる。本発明の一実施形態では、疑似乱数生成器（ステップ１０８）は、秘密鍵（Ｋ）（ステップ１１０）を乱数種とする。秘密鍵（Ｋ）は、ビットストリームとして提供することができる。本発明の一実施形態では、生成器１０８は、暗号的に堅牢な疑似乱数生成器である。ＲＴモジュール１０２の出力（例えば、ベクトル）は、例えば、図６から図１０を参照しながらさらに説明する数々のアプリケーション（１１２）で使用することができる。
【００１２】
図２に、例示的なＲＴ方法２００を示す。（図３および図４を参照しながらさらに説明するように）ＲＴ基底関数を生成した後（ステップ２０２）、生成した基底関数からいくつかを、図１を参照しながら説明したように、無作為に選択する（ステップ２０４）。本発明の一実施形態では、（例えば、疑似乱数生成器の乱数種として使用される）秘密鍵（Ｋ）が、どの基底関数を個々の事例のために選択すべきかを指定する。次に、無作為に選択された基底関数を適用することによって、入力信号（ステップ１０４）を変換する（ステップ２０６）。本発明の一実施形態では、入力信号は、例えば、図５を参照しながらさらに説明するように、ブロックに分割することができる。
【００１３】
さらに、ＲＴは、離散変換として適用することもできる。無作為性を与えることで、ＲＴに２つの異なる利点がもたらされる。第１に、攻撃者はどの基底関数が変換に使用されているかを知ることができず、攻撃を仕掛けるのが比較的非常に困難になるため、セキュリティ目的で有用である。第２に、基底は比較的大きな基底関数集合から無作為に選択されるので、最悪時の性能で変換が行われることは、比較的低い確率でしか起こらない。したがって、ＲＴの尺度は、最悪時の性能ではなく、平均時の性能となる。
【００１４】
（ＲＴ基底の生成）
基底関数（本明細書では「ｒａｎｄｌｅｔ」とも呼ばれる）は、「母ｒａｎｄｌｅｔ（ｍｏｔｈｅｒ  ｒａｎｄｌｅｔ）」と呼ばれる２次元関数の集合に基づいている。後ほど、様々な母ｒａｎｄｌｅｔについて説明する。（例えば、オーディオ信号、画像信号、ビデオ信号にそれぞれ対応して）１次元、２次元、または３次元の基底関数が利用できるものと想定されている。
【００１５】
図３に、ＲＴ基底関数を生成するための例示的な方法３００を示す。一般に、ｒａｎｄｌｅｔは、母ｒａｎｄｌｅｔにスケーリング（ステップ３０２）、回転（ステップ３０４）、平行移動（ステップ３０６）、離散化（ステップ３０８）、および正規化（ステップ３１０）を施すことによって生成される。ステップ３０２、３０４、３０６の順序、および／またはステップ３０８、３１０の順序は異なってもよいものと想定されている。さらに、対称的なガウス分布など、ある種の分布の場合は、回転を施さなくてもよい（すなわち、円の回転は実行されない）。
【００１６】
本発明の一実施形態では、母ｒａｎｄｌｅｔ  ｍ（ｘ，ｙ）が与えられた場合、水平方向の平行移動ａ、垂直方向の平行移動ｂ、水平方向のスケーリングα、垂直方向のスケーリングβ、および回転θを施した結果のｒａｎｄｌｅｔは、次式で表される。
【００１７】
【数１】
2005346041.tif 000003
ｒ［ｉ，ｊ］＝Ｋ・ｍ（ｘ［ｉ，ｊ］，ｙ［ｉ，ｊ］）
【００１８】
したがって、ＲＴの具体例で使用される特定のｒａｎｄｌｅｔを選択するのに、秘密鍵（Ｋ）が、（図１の１０８のような）疑似乱数生成器の乱数種として使用される。また、乱数が必要な場合はいつでも、この擬似乱数生成器から取られる。
【００１９】
（基底関数ライブラリ）
図４に、ＲＴ基底関数ライブラリを生成するための例示的な方法４００を示す。一般に、すべてのｒａｎｄｌｅｔを独立かつ無作為に選択することによって、ＲＴ基底を定義することができる。しかし、本発明の一実施形態では、ｒａｎｄｌｅｔの選択を多少制限したとしても等しい性能を達成することができるので、実用上の理由から、すべてのｒａｎｄｌｅｔを選択する必要はない。さらに、ｒａｎｄｌｅｔの選択を制限することによって、計算上の性能を著しく向上させることができる。
【００２０】
本発明の一実施形態では、ｒａｎｄｌｅｔ毎に独立にスケーリングおよび回転を選択する代わりに、スケーリング操作および回転操作のうち限られた操作だけを許容することによって、基底関数を制限する。各ｒａｎｄｌｅｔを他のすべてのｒａｎｄｌｅｔとは独立に定義する代わりに、平行移動を施さないｒａｎｄｌｅｔからなるライブラリを無作為に生成する。これらのｒａｎｄｌｅｔは、「継母ｒａｎｄｌｅｔ（ｓｔｅｐ−ｍｏｔｈｅｒ  ｒａｎｄｌｅｔ）」として知られ、母ｒａｎｄｌｅｔに無作為なスケーリング（ステップ４０２）、および無作為な回転（ステップ４０４）を施すことによって生成される。すべての継母ｒａｎｄｌｅｔからなるこの集合は、「ライブラリ」と呼ばれることがある（ステップ４０６）。
【００２１】
各母ｒａｎｄｌｅｔは、水平方向と垂直方向に無作為にスケーリングされる。スケーリングの分布は、個々の母ｒａｎｄｌｅｔとアプリケーションに依存する。いくつかの例を後のセクションで提示する。スケーリングされた各母ｒａｎｄｌｅｔについて、施される回転の数は外周に比例することができる。
【００２２】
継母ｒａｎｄｌｅｔには、平行移動（ステップ４０８）、離散化（ステップ４１０）、および正規化（ステップ４１２）が施される。継母ｒａｎｄｌｅｔは、実数値によるスケーリングおよび回転が施された母ｒａｎｄｌｅｔを離散化したものなので、正規化定数は、ｒａｎｄｌｅｔとそれ自身との内積を１に等しく定めることによって決定される。よって、次式が得られる。
【００２３】
【数２】
2005346041.tif 000004
【００２４】
Ｋがαおよびβに依存することに留意されたい。
【００２５】
以下に示すいくつかの重要な値は、ＲＴ基底を生成するためのパラメータである。
【００２６】
ｎ：基底関数の総数。
【００２７】
＜Ｔ，Ｕ＞：変換されるブロックの幅および高さ。
【００２８】
Ｆ（・）：各ｒａｎｄｌｅｔの型を決定するアルゴリズム。
【００２９】
ｒａｎｄｌｅｔの完全な集合は、ライブラリから継母ｒａｎｄｌｅｔを無作為に選択し、それに平行移動を施す（ステップ４０８）ことによって生成される。これは、３つの要素からなる組＜ｉ，ａ，ｂ＞をｎ個含んだリストを生成することによって行われ、１つの組は、変換で使用される１つのｒａｎｄｌｅｔを表す。３つの要素からなる組において、ｉは、ライブラリへのインデックスであり、そのため、ｒａｎｄｌｅｔのスケーリングおよび回転を暗黙に決定する。ｉは、関数Ｆ（・）によって無作為に選択される。使用される具体的な関数Ｆは、アプリケーションに依存する。ａおよびｂは、ｒａｎｄｌｅｔの中心点の水平方向および垂直方向の平行移動の大きさであり、それぞれ［０，Ｔ］、［０，Ｕ］の範囲から一様かつ無作為に選択される実数値である。本発明の一実施では、リストは、生成された後、ｒａｎｄｌｅｔのサイズに基づいて、例えば、最大のｒａｎｄｌｅｔが先頭になり、最小のｒａｎｄｌｅｔが末尾に来るようにソートされる。
【００３０】
（母ｒａｎｄｌｅｔ）
上記で図４を参照しながら説明したように、母ｒａｎｄｌｅｔは、その他のすべてのｒａｎｄｌｅｔを生成する基本ｒａｎｄｌｅｔである。母ｒａｎｄｌｅｔは、（０，０）を中心とする、局所的に有効なサポート（ｌｏｃａｌｉｚｅｄ  ｅｆｆｅｃｔｉｖｅ  ｓｕｐｐｏｒｔ）を有する２次元実数値関数である。一般に、母ｒａｎｄｌｅｔには、低周波ｒａｎｄｌｅｔ（ｌｏｗ−ｆｒｅｑｕｅｎｃｙ  ｒａｎｄｌｅｔ）と高周波ｒａｎｄｌｅｔ（ｈｉｇｈ−ｆｒｅｑｕｅｎｃｙ  ｒａｎｄｌｅｔ）の２つのタイプがある。水平方向については、両タイプのｒａｎｄｌｅｔとも、ガウス形状を有する。垂直方向については、低周波ｒａｎｄｌｅｔは、ガウス形状をもつが、高周波ｒａｎｄｌｅｔは、振動形状（ｏｓｃｉｌｌａｔｏｒｙ  ｓｈａｐｅ）をもつ。高周波ｒａｎｄｌｅｔのみが、ガウスｒａｎｄｌｅｔとしても知られている。このｒａｎｄｌｅｔは、画像コンテンツまたは音声コンテンツの低周波成分を見つけるのに有用である。このｒａｎｄｌｅｔは、水平と垂直の両方向について、ガウス形状をもつが、各方向の幅は、異なることができる。
【００３１】
ガウスｒａｎｄｌｅｔ：
【００３２】
【数３】
2005346041.tif 000005
【００３３】
高周波ｒａｎｄｌｅｔは、水平方向については、ガウス形状をもち、垂直方向については、様々な振動形状を有する。高周波ｒａｎｄｌｅｔには回転が施されるので、ガウス形状の方向を滑らかな方向と呼び、振動関数の方向を粗い方向と呼ぶことにする。垂直方向での変動は、これらのｒａｎｄｌｅｔに、水平方向でのエッジ検出属性を与える。高周波ｒａｎｄｌｅｔは、θ度回転させたとき、θ度のところでエッジを検出する傾向がある。その他のタイプのｒａｎｄｌｅｔとして、例えば、以下のものがある。
【００３４】
ハーフｒａｎｄｌｅｔ（Ｈａｌｆ  Ｒａｎｄｌｅｔ）：
【００３５】
【数４】
2005346041.tif 000006
メキシカンハットｒａｎｄｌｅｔ（Ｍｅｘｉｃａｎ  Ｈａｔ  Ｒａｎｄｌｅｔ）：
【００３６】
【数５】
2005346041.tif 000007
ウェーブレットｒａｎｄｌｅｔ（Ｗａｖｅｌｅｔ  Ｒａｎｄｌｅｔ）：
【００３７】
【数６】
2005346041.tif 000008
【００３８】
ウェーブレットｒａｎｄｌｅｔのｗ（ｙ）の部分は、１次元ウェーブレット関数である。本発明の一実施では、ウェーブレットｒａｎｄｌｅｔにスケーリングを施すとき、固定サイズのウェーブレットを選択する代わりに、ウェーブレット族を選択することができ、スケーリングの代わりに、ウェーブレット族のより長いまたはより短いメンバを選択することができる。
【００３９】
一般に、高周波ｒａｎｄｌｅｔは、粗い方向でよりも滑らかな方向でｒａｎｄｌｅｔがより長くなるように、スケーリングが施される。こうすることで、ｒａｎｄｌｅｔのエッジ検出能力が高まる。
【００４０】
本発明の一実施形態では、ガウスｒａｎｄｌｅｔ、ハーフｒａｎｄｌｅｔ、メキシカンハットｒａｎｄｌｅｔ、および／またはウェーブレットｒａｎｄｌｅｔを組み合わせることによって、母ｒａｎｄｌｅｔを取得することができる。
【００４１】
（ＲＴ変換）
図５に、ＲＴ変換を適用するための例示的な方法５００を示す。変換は、各ｒａｎｄｌｅｔを順々に信号上に射影することによって行われる（ステップ５０２）。ｒａｎｄｌｅｔは、（例えば、図１から図２を参照しながら説明したように）疑似乱数によって選択することができる。各射影が行われた後、信号から各射影が減算される（ステップ５０４）。減算後の残りの信号は、「残余（ｒｅｓｉｄｕｅ）」と呼ばれる。ＲＴ変換方法５００は、選択された各ｒａｎｄｌｅｔを前のｒａｎｄｌｅｔの残余上に射影することによって続行される（ステップ５０６）。このようにして変換が原信号に収束し、係数の効力は、指数関数的に減少する傾向にある。
【００４２】
変換係数ｋは、ｒａｎｄｌｅｔ  ｋとｒａｎｄｌｅｔ  ｋ−１の残余との内積を見つけることによって、ｒａｎｄｌｅｔ毎に計算される（ステップ５０８）。ｒａｎｄｌｅｔ  ｋをｒｋで表し、ｒａｎｄｌｅｔ  ｍの残余をＲｍで表し、係数ｎをｃｎで表す場合、次式が成り立つ。
【００４３】
【数７】
2005346041.tif 000009
【００４４】
各係数が生成されたので、それを量子化し（ステップ５１０）、係数として変換内に保存される量子化値とする（ステップ５１２）。本発明の一実施形態によれば、信号から減算されるのも（ステップ５０４）、この量子化値である。本発明の一実施形態では、レベル数がｒａｎｄｌｅｔの型およびスケーリングに基づいた、一様な量子化器が使用される。例えば、乱数に基づいて係数を丸めるなど、ランダム丸め（ｒａｎｄｏｍｉｚｅｄ  ｒｏｕｎｄｉｎｇ）を使用することもできる。ランダム丸めの効果は、反復収束のアルゴリズムにおいて現れ得る。
【００４５】
量子化が完了した後、次の残余が計算される（ステップ５１４）。Ｑ（・）を量子化器とする場合、次式が成り立つ。
【００４６】
Ｒｋ［ｉ，ｊ］＝Ｒｋ−１［ｉ，ｊ］−Ｑ（ｃｋ）・ｒｋ［ｉ，ｊ］
本発明の一実施形態では、ｒａｎｄｌｅｔは、信号ブロック全体には射影されない。ｒａｎｄｌｅｔの効果的なフットプリントは、前処理フェーズ（図示せず）において、ｒａｎｄｌｅｔが無視できない値をもつ領域だけを考慮することによって計算される。その後、その領域に対してのみ、ｒａｎｄｌｅｔを射影する。
【００４７】
本発明の代替の実施形態では、基底関数を通常通りに置き、次に、その位置に摂動を与えて最大効力の傍に近づける。こうすることで、より少ない係数で変換を収束させることができるが、水平方向および垂直方向の摂動を与える付加的情報を各係数とともに保存しなければならない。
【００４８】
各ｒａｎｄｌｅｔの中心は、信号ブロックの全域にわたって一様に分散するので、ｒａｎｄｌｅｔの端がブロックの外部にはみ出すことがある。これが、ブロック境界でのエッジ効果の原因となる。これらのエッジ効果は、各エッジにおいて各ブロックを自身のミラー信号で埋め込みを行うことによって、打ち消すことができる。一般に、非常に大きな画像であっても、（例えば、１画像につき）５から１０ピクセルの埋め込みで十分である。
【００４９】
（ＲＴ変換の拡張）
一般に、ＲＴの具体例は、特定のサイズの信号ブロック（例えば、画像）に作用させるために生成される。ＲＴを行うのに、３つの方法がある。第１の方法では、［０，１］の範囲に中心をもつｒａｎｄｌｅｔを選択することができ、どのような信号ブロックが選択されたとしても、その実際のサイズに変換を拡張することができる。この方法の利点の１つは、変換の係数の多くが、スケーリングに対して不変となることである。しかし、この変換が大きなデータブロックのためのスケーリングを適切に行うことを保証するには、非常に多くのｒａｎｄｌｅｔを選択することが必要になる場合がある。これらのｒａｎｄｌｅｔは、小さな信号では冗長であるが、変換が大きな比率のスケーリングを行えるようにするには不可欠である。
【００５０】
次の方法は、最大信号ブロックサイズに対して変換を定義するものである。この方法は、先の方法と類似しているが、最大信号ブロックサイズは分かっているので、基底関数の数に制限を設けられる点が異なっている。しかし、より小さな信号で基底関数が冗長となる問題はまだ残っている。
【００５１】
第３の方法は、比較的小さなブロック、例えば、５０×５０または１００×１００の画像に対して変換を生成するものである。このサイズより大きなブロックはいずれも、このサイズのブロックに分解され、変換は、すべてのブロックで独立に実行される。この方法は、先の２つの方法でのように基底関数が冗長となることを避けることができるので、変換にとって有益なものとなり得る。しかし、第１の方法は、使用する基底関数の数を少なくすることができるハッシングや電子透かしといったＲＴの適用例で役に立つ。これらについては、「ハッシング」および「電子透かし」という表題の下で後ほどさらに説明する。
【００５２】
さらに、大多数の信号ブロックは、ブロックサイズの整数倍にはならないので、ブロックサイズの倍数となるように、ブロックにゼロに埋め込みを行うことができる。この埋め込みは、以下で説明する逆変化または再構成の一環において、取り除くことができる。
【００５３】
本発明の一実施形態では、基底関数は、完全かつ独立にランダムである必要はない。例えば、第１の基底関数は、完全に無作為に選択することができる。後続の各基底関数については、それまでに選択されたすべての基底関数との直交性および／または正規性を保証する制約を含む、１組の線形制約（ｌｉｎｅａｒ  ｃｏｎｓｔｒａｉｎｔ）を生成することができる。そのような制約は、基底関数の形状がｒａｎｄｌｅｔであることを保証することもできる。その後、制約を満たす関数から、次の基底関数を無作為に選択することができる。しかし、追加の基底関数が選択されたので、関数がすべての制約を満たすことはより困難になる可能性がある。このような場合、所望の基底関数のサイズに応じて変化し得る何らかの閾値によって定義されるような、近似的な制約を満たす（例えば、ほとんど直交な）関数の中から、次の基底関数を無作為に選択することができる。本発明の一実施形態では、このプロセスは、最適化アルゴリズムによって実施することができる。
【００５４】
（圧縮）
図６に、ＲＴベースの圧縮のための例示的な方法６００を示す。量子化の後（例えば、図５のステップ５１０）、変換係数の多くがゼロになることがある。これらの係数は取り除くことができるので（ステップ６０２）、係数のこのような分布は、圧縮に非常に適したものとなる。
【００５５】
さらに、最小ｒａｎｄｌｅｔに対応する係数を取り除くことによって（ステップ６０２）、任意のレベルの非可逆圧縮を実行することができる。図４を参照しながら説明したｒａｎｄｌｅｔのソートされたリストについて言えば、リストの先頭付近のｒａｎｄｌｅｔだけを使用し、リストの末尾のほうのｒａｎｄｌｅｔを無視することによって、非可逆圧縮を達成することができる。（１）より厳格な方法で係数を圧縮することができ、かつ／または（２）係数の値に閾値を適用して、例えば、大きさ（例えば、絶対値）が一定の閾値より小さい係数を取り除くことができるなど、その他の非可逆圧縮技法を利用することもできる。
【００５６】
さらに、非可逆圧縮の圧縮率を動的に変化させることもできるので、信号ブロックで費やされる帯域幅の量を、利用可能な帯域幅に応じたものとすることができる。また、最初は基本表現が現れ、後から細部が満たされていくように、画像を反復して送信することもできる。さらに、（図４を参照しながら説明したように）基底関数のリストをサイズに従ってソートする場合、これは自動的に行われる。
【００５７】
（雑音除去）
図７に、ＲＴベースの雑音除去のための例示的な方法７００を示す。最初に、小さな基底関数をデエンファシスする（ｄｅ−ｅｍｐｈａｓｉｚｅ）（ステップ７０２）。次に、残った基底関数を重ね合わせることによって、雑音の多くが相殺される（ステップ７０４）。
【００５８】
（ハッシング）
ＲＴは、画像のハッシングなど、マルチメディア信号のハッシングのための理想的なツールである。このセクションでは、画像のハッシングについて具体的に細かく説明するが、ＲＴベースのハッシングは、図８を参照しながら説明するように、信号全般に適用できるものと想定されている。
【００５９】
画像ハッシングの場合、生成されたハッシュ値は、画像内の乱れ（ｐｅｒｔｕｒｂａｔｉｏｎ）に対して堅牢であると考えられ、基底関数の無作為性は、ハッシュが予測困難であることを保証する。ハッシングでは完全な変換で求められる要件よりも少ない要件しか求められないので、ハッシングのためには図５のＲＴの修正版を使用することができる。具体的には、ハッシュ値を生成するために変換を使用する場合、原信号を生成するために、ハッシュ値を元の値に戻すことができなくてもかまわない。したがって、ハッシングを行う場合は、完全な画像変換を実行する場合に比べて、はるかに少ない係数が使用される。
【００６０】
さらに、ハッシングを行う場合、例えば、係数をすべての画像にわたってとるようなとき、各係数をその他のすべての係数と同じ分布からとると有益なことがある。したがって、ハッシングのためにＲＴを使用する場合、残余は使用されない。そのため、ハッシングアルゴリズムは単純化され、前のｒａｎｄｌｅｔによってハッシュ係数の効力が弱められるようなことがないことが保証される。また、残余を用いる場合、後のほうの係数は、前のほうの係数に依存するので、信号内の小さな乱れが、後のほうの係数における大きな変化の原因となることがあり得る。これは、近似的なハッシュにとって望ましくない特性である。
【００６１】
本発明の一実施形態では、適切な格子を使用して、ハッシュされたベクトルを量子化することができる。例えば、公開鍵格子をもつことができ、その格子に関して、秘密鍵は、量子化を容易に可能にするが、公開鍵からの量子化は、より多くの誤りを持ち込む可能性がある。したがって、適切なユニモジュラ行列変換の下での格子に関して、公開鍵基底は、秘密鍵基底の像となる。さらに、量子化は、小さな変化を無視することを許容しもする。
【００６２】
さらに、ハッシュ用の変換を選択する場合、（図４を参照しながら説明したように）ｒａｎｄｌｅｔをサイズによってソートする必要はない。図８に示すように、ＲＴに基づくハッシングは、最初に信号を所定のサイズ、例えば、２５６×２５６にスケーリングし（ステップ８０２）、次に選択された各ｒａｎｄｌｅｔを直接、残余を使用せずに、スケーリングした信号上に射影する（ステップ８０４）ことによって行われる。（図５を参照しながら説明したように）変換係数を計算する（ステップ８０６）。次に、生成された係数を（重みづけして）量子化する（ステップ８０８）。
【００６３】
最後に、量子化された変換係数に誤り訂正を適用し（ステップ８１０）、係数を保存する（ステップ８１２）。本発明の一実施形態では、誤り訂正符号の復号器は、ハッシュ値を小さくし、それを乱れに対してより耐性のあるものにする。
【００６４】
（識別／認証のためのハッシング）
（図８を参照しながら説明したような）ＲＴベースのハッシングを実行し、様々なハッシュ値を比較することによって、画像（または一般に信号）を比較することができる。しかし、画像の識別または認証のためには、誤り訂正復号化は必要ではない（ステップ８１０）。その結果、各信号または画像は、量子化変換係数のベクトルに関係づけられる。距離計量に基づいて係数のベクトルを比較することによって、信号を素早く比較することができる。
【００６５】
本発明の一実施形態では、Ｌ２ノルムが利用される。Ｌｎノルムは、ｎが大きいほうが（係数の間の大きな差は拡大され、より小さな差は重要な役割を果たさなくなるので）、よりよい結果を得られると想定されている。
【００６６】
係数は、直接比較することも、または比率として比較することもできる。例えば、ある画像の統計量の比率を別の画像の同じ統計量の比率と比較すれば、等化攻撃（ｅｑｕａｌｉｚａｔｉｏｎ  ａｔｔａｃｋ）を撃退する助けとすることができる。これは、変換係数の正規化に似ている。代替として、係数のサブセットの関数である統計量を形成することができる。やはり、これも、直接比較することも、または比率として比較することもできる。
【００６７】
（ＲＴ電子透かし）
図９に、ＲＴベースの電子透かしのための例示的な方法９００を示す。方法９００はより一般的に、データ組み込みのために利用できるものと想定されている。電子透かし（またはより一般的にデータ組み込み）では、ＲＴは、ソートされていない比較的少数のｒａｎｄｌｅｔのために定義され、ＲＴベースのハッシングでのように、残余は利用されない（上記の図８の説明を参照されたい）。最初に、信号サイズをスケーリングする（ステップ９０２）。画像信号の場合、変換は、基準サイズ［０，１］×［０，１］の画像上で定義され、提供された画像のサイズにスケーリングされる。変換は、図５および図８を参照しながら説明したように、ｒａｎｄｌｅｔを信号上に直接射影し（ステップ９０４）、変換係数を計算する（ステップ９０６）ことによって実行される。
【００６８】
次に、電子透かしが変換係数に適用され（ステップ９０８）、その変換係数は、例えば、変換を逆転させる最小ノルム行列解法（ｍｉｎｉｍｕｍ−ｎｏｒｍ  ｍａｔｒｉｘ  ｓｏｌｕｔｉｏｎ）によって、信号に挿入し戻される（ステップ９１０）。行列がよい挙動をみせることを保証するため、ｒａｎｄｌｅｔがあまり重なり合わないように、ｒａｎｄｌｅｔを選択することができる。しかし、このようにすると、電子透かしを識別し、破ることがより簡単になる可能性がある。
【００６９】
（逆変換または再構成）
図１０に、ＲＴを使用して変換された信号を再構成するための例示的な方法１０００を示す。（図５を参照しながら説明したように）変換を行うときに残余を使用するので、各ｒａｎｄｌｅｔの射影は、それより前のｒａｎｄｌｅｔに対して直交している。これは、各ｒａｎｄｌｅｔの射影を単純に合算することによって、直交画像を再構成できることを意味している。すなわち、各ｒａｎｄｌｅｔに対応する変換係数を掛け（ステップ１００２）、それらの和をとる（ステップ１００４）ことによって入力信号が得られる（ステップ１００６）。
【００７０】
例えば、Ｉ［ｉ，ｊ］が画像である場合、次式が成り立つ。
【００７１】
【数８】
2005346041.tif 000010
【００７２】
本発明の一実施では、ほとんど直交な基底関数に再構成方法１０００を適用することができる。したがって、残余を使用する場合、基底関数が直交する場合、または基底関数がほとんど直交する場合に、再構成方法１０００を適用することができる。
【００７３】
（ハードウェア実装）
図１１に、本明細書で説明する技法を実施するために使用できる汎用的なコンピューティング環境１１００を示す。例えば、コンピューティング環境１１００は、図１から図１０を参照しながら説明した処理の実行に関連する命令を実行するのに利用することができる。コンピューティング環境１１００は、コンピューティング環境の１つの例に過ぎず、コンピュータおよびネットワークアーキテクチャの用途または機能の範囲について、どのような限定も示唆しようとするものではない。コンピューティング環境１１００は、例示的なコンピューティング環境１１００に示す構成要素の任意の１つまたは組合せに関して、どのような依存性または必然性ももたないと解釈されたい。
【００７４】
コンピューティング環境１１００は、コンピュータ１１０２の形態をとる汎用コンピューティング装置を含む。コンピュータ１１０２の構成要素には、１つまたは複数のプロセッサまたは処理装置１１０４（任意選択で暗号プロセッサまたはコプロセッサを含む）、システムメモリ１１０６、および処理装置１１０４を含む様々なシステム構成要素をシステムメモリ１１０６に結合するシステムバス１１０８が含まれ得るが、これらに限定されるものではない。
【００７５】
システムバス１１０８は、様々なバスアーキテクチャのいずれかを使用する、メモリバスまたはメモリコントローラ、周辺バス、アクセラレータグラフィックスポート、およびプロセッサまたはローカルバスを含む複数のタイプのバス構造のいずれか１つまたは複数に相当する。例えば、バスアーキテクチャには、ＩＳＡ（業界標準アーキテクチャ）バス、ＭＣＡ（マイクロチャネルアーキテクチャ）バス、ＥＩＳＡ（拡張ＩＳＡ）バス、ＶＥＳＡ（ビデオ電子規格協会）ローカルバス、およびメザニンバス（Ｍｅｚｚａｎｉｎｅ  ｂｕｓ）としても知られるＰＣＩ（周辺コンポーネント相互接続）バスが含まれ得る。
【００７６】
コンピュータ１１０２は一般に、様々なコンピュータ読取り可能な媒体を含む。コンピュータ読取り可能な媒体は、コンピュータ１１０２によってアクセス可能な任意の利用可能な媒体とすることができ、揮発性および不揮発性媒体、着脱可能および固定の媒体が含まれる。
【００７７】
システムメモリ１１０６には、ＲＡＭ（ランダムアクセスメモリ）１１１０などの揮発性メモリ、および／またはＲＯＭ（読み取り専用メモリ）１１１２などの不揮発性メモリの形態をとるコンピュータ記憶媒体が含まれる。ＢＩＯＳ（基本入出力システム）１１１４は、起動時などにコンピュータ１１０２内の要素間での情報伝送を支援する基本ルーチンを含み、ＲＯＭ１１１２に保存される。ＲＡＭ１１１０は一般に、プロセッシングユニット１１０４が直ちにアクセス可能な、かつ／または現在それに基づいて動作している、データおよび／またはプログラムモジュールを格納する。
【００７８】
コンピュータ１１０２はまた、その他の着脱可能／固定の、揮発性／不揮発性コンピュータ記憶媒体を含む。例えば、図１１には、固定の不揮発性磁気媒体（図示せず）に対して読み書きを行うハードディスクドライブ１１１６、着脱可能な不揮発性磁気ディスク１１２０（例えば、「フロッピディスク（登録商標）」）に対して読み書きを行う磁気ディスクドライブ１１１８、およびＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、またはその他の光媒体といった着脱可能な不揮発性光ディスク１１２４に対して読み書きを行う光ディスクドライブ１１２２が示されている。ハードディスクドライブ１１１６、磁気ディスクドライブ１１１８、および光ディスクドライブ１１２２は各々、１つまたは複数のデータ媒体インターフェース１１２５によってシステムバス１１０８に接続される。代替として、ハードディスクドライブ１１１６、磁気ディスクドライブ１１１８、および光ディスクドライブ１１２２を、１つまたは複数のインターフェース（図示せず）によってシステムバス１１０８に接続することもできる。
【００７９】
ディスクドライブおよび関連するコンピュータ読取り可能な媒体は、コンピュータ読取り可能な命令、データ構造、プログラムモジュール、およびその他のデータの不揮発性記憶をコンピュータ１１０２に提供する。図例には、ハードディスクドライブ１１１６、着脱可能な磁気ディスク１１２０、および着脱可能な光ディスク１１２４が示されているが、コンピュータによってアクセス可能なデータを保存できるその他の種類のコンピュータ読取り可能な媒体、例えば、磁気カセット、またはその他の磁気記憶装置、フラッシュメモリカード、ＣＤ−ＲＯＭ、ＤＶＤ（デジタル多用途ディスク）、またはその他の光記憶、ＲＡＭ（ランダムアクセスメモリ）、ＲＯＭ（読み取り専用メモリ）、ＥＥＰＲＯＭ（電気的消去可能なプログラム可能読み取り専用メモリ）などを利用して、例示的なコンピューティング装置および環境を実施することもできることを理解されたい。
【００８０】
例えば、オペレーティングシステム１１２６、１つまたは複数のアプリケーションプログラム１１２８、その他のプログラムモジュール１１３０、およびプログラムデータ１１３２を含む任意の数のプログラムモジュールを、ハードディスク１１１６、磁気ディスク１１２０、光ディスク１１２４、ＲＯＭ１１１２、および／またはＲＡＭ１１１０に保存することができる。そのようなオペレーティングシステム１１２６、１つまたは複数のアプリケーションプログラム１１２８、その他のプログラムモジュール１１３０、およびプログラムデータ１１３２（またはそれらの何らかの組合せ）の各々は、分散ファイルシステムを支援する常駐コンポーネントの全部または一部を実施することができる。
【００８１】
ユーザは、キーボード１１３４およびポインティング装置１１３６（例えば、「マウス」）などの入力装置を介して、コマンドおよび情報をコンピュータ１１０２に入力することができる。その他の入力装置１１３８（具体的には図示せず）には、マイクロフォン、ジョイスティック、ゲームパッド、衛星放送用パラボラアンテナ、シリアルポート、および／またはスキャナなどが含まれ得る。上記およびその他の入力装置は、システムバス１１０８に結合された入出力インターフェース１１４０を介して、プロセッシングユニット１１０４に接続されるが、パラレルポート、ゲームポート、またはＵＳＢ（汎用シリアルバス）など、その他のインターフェースおよびバス構造によって接続することもできる。
【００８２】
モニタ１１４２またはその他のタイプのディスプレイ装置も、ビデオアダプタ１１４４などのインターフェースを介して、システムバス１１０８に接続される。その他の出力周辺装置には、モニタ１１４２の他に、入出力インターフェース１１４０を介してコンピュータ１１０２に接続できる、スピーカ（図示せず）およびプリンタ１１４６などの構成要素が含まれ得る。
【００８３】
コンピュータ１１０２は、リモートコンピューティング装置１１４８など、１つまたは複数のリモートコンピュータへの論理接続を使用して、ネットワーク環境で動作することができる。例えば、リモートコンピューティング装置１１４８は、パーソナルコンピュータ、ポータブルコンピュータ、サーバ、ルータ、ネットワークコンピュータ、ピア装置またはその他の共通ネットワークノード、およびゲームコンソールなどとすることができる。リモートコンピューティング装置１１４８は、コンピュータ１１０２に関して本明細書で説明した多くの要素またはすべての要素を含むことができる、ポータブルコンピュータとして示されている。
【００８４】
コンピュータ１１０２とリモートコンピューティング装置１１４８の間の論理接続は、ＬＡＮ（ローカルエリアネットワーク）１１５０および汎用的なＷＡＮ（ワイドエリアネットワーク）１１５２として示されている。このようなネットワーク環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、およびインターネットで一般的である。
【００８５】
ＬＡＮネットワーク環境で実施される場合、コンピュータ１１０２は、ネットワークインターフェースまたはアダプタ１１５４を介して、ローカルネットワーク１１５０に接続される。ＷＡＮネットワーク環境で実施される場合、コンピュータ１１０２は一般に、ワイドネットワーク１１５２を介して通信を確立するためのモデム１１５６またはその他の手段を含む。モデム１１５６は、コンピュータ１１０２に内蔵することも、外付けとすることもでき、入出力インターフェース１１４０またはその他の適切な機構を介して、システムバス１１０８に接続することができる。図示のネットワーク接続は例示的なものであり、コンピュータ１１０２とリモートコンピューティング装置１１４８の間で通信リンクを確立するその他の手段も利用できることは理解されよう。
【００８６】
コンピューティング環境１１００によって説明したようなネットワーク環境では、コンピュータ１１０２に関して示したプログラムモジュールまたはその部分は、リモートメモリ記憶装置に保存することができる。例えば、リモートアプリケーションプログラム１１５８は、リモートコンピュータ１１４８のメモリ装置に存在する。説明のため、本明細書では、アプリケーションプログラム、およびオペレーティングシステムなどのその他の実行可能プログラムコンポーネントを別個のブロックとして示してあるが、そのようなプログラムおよびコンポーネントは、様々なときにコンピュータ１１０２の異なる記憶構成要素に存在し、コンピュータのデータプロセッサによって実行されることを理解されたい。
【００８７】
本明細書では、様々なモジュールおよび技法を、１つまたは複数のコンピュータまたはその他の装置によって実行される、プログラムモジュールなどの、コンピュータ実行可能命令という一般的コンテキストにおいて説明することができる。一般に、プログラムモジュールには、特定のタスクを実行したり、または特定の抽象データ型を実施したりする、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。通常、プログラムモジュールの機能は、様々な実施における要求に応じて、組み合わせたり、または分割したりすることができる。
【００８８】
これらのモジュールおよび技法の実施物は、何らかの形態のコンピュータ読取り可能な媒体に保存することができ、または何らかの形態のコンピュータ読取り可能な媒体を介して送信することができる。コンピュータ読取り可能な媒体は、コンピュータによってアクセス可能な任意の利用可能媒体とすることができる。例えば、コンピュータ読取り可能な媒体には、「コンピュータ記憶媒体」および「通信媒体」が含まれ得るが、これらに限定されるものではない。
【００８９】
「コンピュータ記憶媒体」には、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータといった情報を記憶するための任意の方法または技術によって実施される、揮発性／不揮発性、着脱可能／着脱不能媒体が含まれる。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、もしくはその他のメモリ技術、ＣＤ−ＲＯＭ、ＤＶＤ（デジタル多用途ディスク）、もしくはその他の光記憶、磁気カセット、磁気テープ、磁気ディスク記憶、もしくはその他の磁気記憶装置、または所望の情報を記憶するのに利用でき、コンピュータによってアクセスできる、その他の任意の媒体が含まれるが、これらに限定されるものではない。
【００９０】
一般に「通信媒体」には、搬送波またはその他の移送機構などの変調データ信号中のコンピュータ可読命令、プログラムモジュール、データ構造、またはその他のデータが含まれる。通信媒体には、任意の情報送達媒体も含まれる。「変調データ信号」という用語は、信号中に情報を符号化するための方式によって設定または変更された１つまたは複数の信号特性をもつ信号を意味する。例えば、通信媒体には、有線ネットワークまたは直接線接続などの有線媒体、ならびに音響、無線周波（ＲＦ）、赤外線（ＩＲ）、ワイヤレスフェデリティ（例えば、ＩＥＥＥ８０２．１１ｂ無線ネットワーキング）（Ｗｉ−Ｆｉ）、セルラ電話、Ｂｌｕｅｔｏｏｔｈ対応およびその他の無線媒体などの無線媒体が含まれるが、これらに限定されるものではない。上記の任意の媒体の組合せも、コンピュータ読取り可能な媒体の範囲に含まれる。
【００９１】
（結び）
本発明を特定の構造的機能および／または方法の工程に適した言葉で説明してきたが、添付の特許請求の範囲において確定される本発明が、説明された特定の機能または工程に必ずしも限定されるものではないことを理解されたい。例えば、本明細書で説明した技法は、オーディオ信号、画像、および／またはビデオ信号（すなわち、それぞれ１次元、２次元、３次元信号）に適用することができる。したがって、特定の機能および工程は、特許請求される発明を実施する例示的な形態として開示されたものである。
【図面の簡単な説明】
【００９２】
【図１】例示的なｒａｎｄｌｅｔ変換（ＲＴ）システムを示した図である。
【図２】例示的なＲＴ方法を示した図である。
【図３】ＲＴ基底関数を生成するための例示的な方法を示した図である。
【図４】ＲＴ基底関数ライブラリを生成するための例示的な方法を示した図である。
【図５】ＲＴ変換を適用するための例示的な方法を示した図である。
【図６】ＲＴに基づく圧縮のための例示的な方法を示した図である。
【図７】ＲＴに基づく雑音除去のための例示的な方法を示した図である。
【図８】ＲＴに基づくハッシングのための例示的な方法を示した図である。
【図９】ＲＴに基づく電子透かしのための例示的な方法を示した図である。
【図１０】ＲＴを使用して変換された信号の再構成のための例示的な方法を示した図である。
【図１１】本明細書で説明する技法を実施するのに使用できる汎用的なコンピューティング環境１１００を示した図である。
【符号の説明】
【００９３】
１１００  コンピューティング環境
１１０２  コンピュータ
１１１８  磁気ディスクドライブ
１１２２  光ディスクドライブ
【図１】
2005346041.tif 000011
【図２】
2005346041.tif 000012
【図３】
2005346041.tif 000013
【図４】
2005346041.tif 000014
【図５】
2005346041.tif 000015
【図６】
2005346041.tif 000016
【図７】
2005346041.tif 000017
【図８】
2005346041.tif 000018
【図９】
2005346041.tif 000019
【図１０】
2005346041.tif 000020
【図１１】
2005346041.tif 000021