"離散参照信号と被疑信号との間の変換を計算する方法であって、前記離散参照信号を表す特徴位置のセットを用意し、初期変換パラメータのシードセットを用意するステップであって、前記特徴位置及び変換パラメータが、電子メモリにおけるデジタル電子信号として表される、当該ステップと、前記シードセットを使用して、前記離散参照信号の前記特徴位置と前記被疑信号における対応する特徴位置とをアライメントするために線形変換が使用されるときに誤差を最小限にする線形変換候補を見つけ出す最小二乗最小化を計算するステップであって、前記線形変換候補に対応する相関の尺度を計算するサブステップを含む当該ステップと、シードのそれぞれについて前記線形変換候補を評価して、線形変換候補の絞り込まれた推定値を表す前記候補のサブセットを識別するステップと、を含む方法。前記特徴位置が、前記離散参照信号におけるピークに対応する、請求項1に記載の方法。前記特徴位置が、前記離散参照信号の正弦曲線信号成分に対応する、請求項1に記載の方法。前記参照信号が、デジタル透かし信号を含み、前記被疑信号が、前記デジタル透かし信号が埋め込まれるホスト信号を含む、請求項1に記載の方法。前記シードセットが、均等に分布した変換パラメータのまばらなセットを含む、請求項1に記載の方法。有限集合における残りの変換パラメータを一定に維持しながら、変換パラメータの有限集合のサブセットを均等に変化させることによって、前記まばらなセットが選択される、請求項5に記載の方法。前記絞り込まれた推定値を得るために、前記候補の間の類似性に基づいて線形変換候補の少なくとも第1のクラスタを選択する、請求項1に記載の方法。線形変換候補の前記第1のクラスタにおける候補線形変換が組み合わされて、絞り込まれた線形変換候補を用意する、請求項7に記載の方法。前記候補が、前記候補の相関強度に応じて前記候補を重み付けすることによって組み合わされ、相関強度が、位相相関の尺度を含む、請求項8に記載の方法。命令が格納されたコンピュータ可読媒体であって、前記命令が、1つ又は複数のプロセッサによって実行されたとき、離散参照信号と被疑信号との間の変換を計算する方法を実施し、前記方法が、前記離散参照信号を表す特徴位置のセットを用意し、初期変換パラメータのシードセットを用意するステップであって、前記特徴位置及び変換パラメータが、電子メモリにおけるデジタル電子信号として表される、当該ステップと、前記シードセットを使用して、前記離散参照信号の前記特徴位置と前記被疑信号における対応する特徴位置とをアライメントするために線形変換が使用されるときに誤差を最小限にする線形変換候補を見つけ出す最小二乗最小化を計算するステップであって、前記線形変換候補に対応する相関の尺度を計算するサブステップを含む当該ステップと、シードのそれぞれについて前記線形変換候補を評価して、線形変換候補の絞り込まれた推定値を表す前記候補のサブセットを識別するステップと、を含む、コンピュータ可読媒体。被疑信号表現を格納するためのメモリと、線形変換候補のシードセットを受け取り、線形変換候補が適用されるとき、参照信号と前記被疑信号表現との間の相関の尺度として各候補について相関メトリックを決定するための相関モジュールと、前記線形変換候補を適用することによって決定される位置における前記参照信号の特徴に対応する特徴の前記被疑信号表現内の特徴位置を決定するための座標更新モジュールと、参照信号特徴位置と前記座標更新モジュールによって決定された前記特徴位置との間の最小二乗適合を提供する前記候補のそれぞれについての絞り込まれた線形変換を決定するための最小二乗計算器と、を備える回路。前記回路は、前記線形変換候補に従って、参照信号特徴位置を前記被疑信号表現の座標空間内へ変換するための線形変換モジュール、を含む、請求項11に記載の回路。前記相関モジュールが、前記変換モジュールからの変換された参照信号特徴位置を使用して、前記被疑信号における領域を決定して、前記相関メトリックを計算し、前記相関メトリックが、位相相関メトリックを含む、請求項12に記載の回路。前記座標更新モジュールが、前記変換モジュールからの変換された参照信号特徴位置を使用して、前記被疑信号における領域を決定して、前記特徴位置を決定する、請求項12に記載の回路。変換された信号の位相の推定値を計算する方法であって、離散参照信号を表す特徴位置のセットを用意するステップと、被疑信号を受け取るステップと、前記参照信号に変換を適用して、変換された位置のセットを用意するステップと、点広がり関数を使用して、前記変換された位置のあたりの近傍の離散サンプル位置において前記被疑信号から位相をサンプリングし、前記変換された位置に対応する位置における前記被疑信号の位相の推定値を用意するステップと、を含む方法。前記被疑信号が画像信号を含む、請求項15に記載の方法。前記被疑信号が、画像センサからサンプリングされた画像信号を含む、請求項16に記載の方法。前記参照信号が信号成分のセットを含み、前記特徴位置が前記信号成分の位置である、請求項15に記載の方法。前記信号成分が周波数成分であり、前記特徴位置が前記周波数成分の周波数位置である、請求項18に記載の方法。前記被疑信号が、前記参照信号のバージョンを含み、前記点広がり関数が、前記被疑信号内の前記参照信号の前記バージョンの位相を決定するために使用される、請求項15に記載の方法。前記位相が、前記被疑信号内の前記参照信号の前記バージョンと前記参照信号との間の変換を決定するために使用される、請求項20に記載の方法。前記参照信号が、前記被疑信号に埋め込まれたデジタル透かし信号に対応し、前記位相が、前記被疑信号内の前記デジタル透かし信号を検出するために使用される、請求項20に記載の方法。命令が格納されたコンピュータ可読媒体であって、前記命令が、1つ又は複数のプロセッサによって実行されたとき、変換された信号の位相の推定値を計算する方法を実施し、前記方法が、離散参照信号を表す特徴位置のセットを用意するステップと、被疑信号を受け取るステップと、前記参照信号に変換を適用して、変換された位置のセットを用意するステップと、点広がり関数を使用して、前記変換された位置のあたりの近傍の離散サンプル位置において前記被疑信号から位相をサンプリングし、前記変換された位置に対応する位置における前記被疑信号の位相の推定値を用意するステップと、を含む方法。被疑信号の位相を格納するためのメモリと、参照信号の座標を、変換された座標位置に変換するための変換モジュールと変換された座標位置のあたりの位置において前記メモリから前記被疑信号の選択された位相を読み取り、点広がり関数を前記選択された位相に適用して推定位相を提供するための点広がり関数モジュールと、を備える回路。前記被疑信号が画像信号を含む、請求項24に記載の回路。前記被疑信号が、画像センサからサンプリングされた画像信号を含む、請求項25に記載の回路。前記参照信号が信号成分のセットを含み、前記座標が前記信号成分の位置である、請求項24に記載の回路。前記信号成分が周波数成分であり、前記座標が前記周波数成分の周波数位置を含む、請求項27に記載の回路。前記被疑信号が、前記参照信号のバージョンを含み、前記点広がり関数が、前記被疑信号内の前記参照信号の前記バージョンの位相を決定するために使用される、請求項24に記載の回路。前記位相が、前記被疑信号内の前記参照信号の前記バージョンと前記参照信号との間の変換を決定するために使用される、請求項29に記載の回路。前記参照信号が、前記被疑信号に埋め込まれたデジタル透かし信号に対応し、前記位相が、前記被疑信号内の前記デジタル透かし信号を検出するために使用される、請求項29に記載の回路。前記点広がり関数モジュールは、点広がり関数テーブルと、前記点広がり関数を前記選択された位相に適用するための積演算子及び和演算子と、を備える、請求項24に記載の回路。参照信号と被疑信号との間の平行移動オフセットの推定値を計算する方法であって、被疑信号の位相推定値のセットを用意するステップと、平行移動オフセットのアレイにおける各要素について、前記平行移動オフセットにおける前記参照信号の期待される位相のセットを用意し、前記平行移動オフセットにおける期待される位相及び対応する位相推定値のセットのそれぞれについて位相偏移メトリックを計算し、前記移動オフセットにおける前記位相偏移メトリックの合計を計算するステップと、平行移動オフセットの前記アレイに対する前記位相偏移メトリックにおけるピークを決定するステップであって、前記ピークの位置が、前記平行移動オフセットの前記推定値を用意する当該ステップと、を含む方法。前記被疑信号は画像信号を含む、請求項33に記載の方法。前記被疑信号が、画像センサからサンプリングされた画像信号を含む、請求項34に記載の方法。前記参照信号が信号成分のセットを含み、期待される位相の前記セットが前記信号成分の位相に対応する、請求項33に記載の方法。前記信号成分が周波数成分であり、前記期待される位相が前記周波数成分の周波数位置に対応する、請求項36に記載の方法。前記被疑信号が、前記参照信号のバージョンを含み、前記位相偏移メトリックが、前記被疑信号内の前記参照信号の前記バージョンの平行移動オフセットを決定するために使用される、請求項33に記載の方法。前記平行移動オフセットが、前記被疑信号内の前記参照信号の前記バージョンと前記参照信号との間の変換を決定するために使用される、請求項38に記載の方法。前記参照信号が、前記被疑信号に埋め込まれたデジタル透かし信号に対応し、前記平行移動オフセットが、前記被疑信号内の前記デジタル透かし信号を検出するために使用される、請求項38に記載の方法。命令が格納されたコンピュータ可読媒体であって、前記命令が、1つ又は複数のプロセッサによって実行されたとき、参照信号と被疑信号との間の平行移動オフセットの推定値を計算する方法を実施し、前記方法が、被疑信号の位相推定値のセットを用意するステップと、平行移動オフセットのアレイにおける各要素について、前記平行移動オフセットにおける前記参照信号の期待される位相のセットを用意し、前記平行移動オフセットにおける期待される位相及び対応する位相推定値のセットのそれぞれについて位相偏移メトリックを計算し、前記移動オフセットにおける前記位相偏移メトリックの合計を計算するステップと、平行移動オフセットの前記アレイに対する前記位相偏移メトリックにおけるピークを決定するステップであって、前記ピークの位置が、前記平行移動オフセットの前記推定値を用意する当該ステップと、を含む、コンピュータ可読媒体。被疑信号の位相推定値及び参照信号の既知の位相のセットを格納するためのメモリと、平行移動オフセットのアレイに対する前記参照信号から、前記参照信号の既知の位相と対応する位相推定値との前記セットのそれぞれについて位相偏移メトリックを計算し、前記平行移動オフセットにおける前記位相偏移メトリックの合計を計算するための偏移位相モジュールと、平行移動オフセットの前記アレイに対する前記位相偏移メトリックにおけるピークを決定するためのピーク決定モジュールであって、前記ピークの位置が、前記参照信号と前記被疑信号との間の前記平行移動オフセットの推定値を提供する、当該ピーク決定モジュールと、を備える位相偏移回路。前記平行移動オフセットのあたりのサブサンプル平行移動オフセットにおける位相偏移メトリックを使用して絞り込まれた平行移動オフセットを計算することによって、前記平行移動オフセットを絞り込み、前記サブサンプル平行移動オフセットにおける前記位相偏移メトリックにおいて絞り込まれたピーク位置を見つけ出すための絞り込みモジュール、を備える、請求項42に記載の回路。平行移動オフセットの前記アレイが、平行移動オフセットの2Dアレイを備える、請求項42に記載の回路。平行移動オフセットの前記アレイが2D空間に対応し、1D平行移動オフセットの2つのアレイに細分化され、各1Dアレイが、1D探索を使用してピーク位置を決定するために評価される、請求項42に記載の回路。00034図1は、参照信号と被疑信号との間の変換を決定するためのプロセスの実装を示すブロック図である。このプロセスを変換回復プロセスと呼ぶことにする。その理由は、このプロセスが、デバイス内に取り込まれた被疑信号から参照信号の変換を回復するためである。特に、この方法は、被疑信号を参照信号とアライメントするために必要な変換を海部フィードバックするために実装されている。このプロセスは、入力として、既知の参照信号及び取り込まれた被疑信号の離散表現100を入力として取り込み、変換の推定値を決定し、変換の推定値は、参照信号に適用されたときに被疑信号を近似することになる。変換回復プロセスは、段階102~106に細分化され、第1の段階は、変換の推定値例えば、線形変換パラメータの4次元ベクトル又は2掛ける2の線形変換行列によって記述された線形変換を提供し、後続の段階は、まず、段階102の推定された変換によって変換されるような参照信号の位相を推定し、次いで、段階106で位相及び平行移動を見つけ出すよって平行移動の2つの追加のパラメータを提供することによって、推定を絞り込む。本発明の特定の実装形態では、段階102において、それぞれが2掛ける2の線形変換行列に対応する候補線形変換を提供する。次の2つの段階では、2次元2D平行移動垂直及び水平方向のを提供し、この平行移動は、2掛ける2の線形変換行列と組み合わされたとき、アフィン変換候補を提供する。この文脈では、位相シフト及び平行移動は、異なるよう領域で表される関連する量である。すなわち、信号成分の位相角の変化としての位相シフトは、フーリエ変換領域などのフーリエ領域で表され、平行移動は、空間領域例えば、画像の空間領域又は時間領域オーディオのような経時変化する信号の時間領域で表される。段階102~106はそれぞれ、他の段階から独立した新規の要素を含み、これらの新規な要素について、より詳細に説明する。これらの段階は、信号間のアフィン変換を計算し、後で更に説明するように組み合わせて使用されるとき追加的な利点を実現するように、システムに実装される。これらの方法及び関連するハードウェア実装は、様々な信号検出、物体認識、及びマッチング用途に適用される。デジタル透かし検出の文脈で方法の例を説明するが、これらの方法は、この文脈に限定されない。00035これらの方法はまた、様々な信号タイプに適用される。それらは、センサから取り込まれた2次元コンテンツ信号例えば、カメラにより取り込まれた画像又はビデオフレームに対して動作するように設計される。これらの方法はまた、1次元及び2以上の次元の信号に適用される。ある実装形態は、特に、画像コンテンツにおける参照信号の幾何変換を決定するように構成される。参照信号は、ホスト画像に埋め込まれた2次元画像透かし信号の形態をとる。参照信号は、異なる用途に対する様々な信号タイプを包含するように一般化されうる。このように、ソフトウェア及びハードウェア実装は、物体認識、パターン認識、マッチング、コンテンツフィンガープリント、マシンビジョン、及び信号間の変換が計算される他の用途など、様々な信号処理用途に適用される。本発明の方法は、具体的には、センサ、特にデジタルスキャナ、カメラ、携帯電話ハンドセットなどで使用されるタイプのCCD及びCMOSアレイのような画像センサに取り込まれた信号を処理するように構成される。00036方法を具体的に説明するための例として、透かし信号検出ハードウェアの概説から始める。次いで、個々の段階の実装を説明する。図2は、参照信号と被疑信号との間のアフィン変換を計算するハードウェアデバイスを示す図である。この特定の設計は、埋め込まれた2次元透かし信号のアフィン変換を回復するように構成される。この設計は、取り込まれデジタル化された電子画像のいくつかの部分をメモリRAM120にバッファする被疑画像信号。フィルタ及びフーリエ変換処理モジュール122が、被疑画像をフィルタリングし、2次元フーリエ変換を計算する。線形変換推定モジュール124は、被疑信号の離散周波数表現を取得し、参照信号とフィルタリングされた被疑信号との間の線形変換の推定を計算する。アフィン変換回復モジュール126は、線形変換推定、並びに参照及び被疑信号表現を使用して、参照及び被疑信号との間の位相/平行移動を計算し、それにより、参照信号を被疑信号に変換するアフィン変換が得られる。00037図2の下部は、モジュール122~126内のサブモジュールを分解したものを示す。これらのサブモジュールの実装は、後で更に説明する。00038図1の変換推定は、いくつかの代替方法で実装されてもよい。1つの手法は、参照信号と被疑信号との間のマッチドフィルタ相関matchedfiltercorrelationを行うことである。被疑信号に対する参照信号の回転及びスケールを決定する1つのそのような方法は、フーリエ-メリン相関である。被疑信号と参照信号の両方をフーリエ-メリン座標空間対数極座標空間に変換することによって、2つの信号の間の回転及びスケール変換が平行移動シフトに変換されて、マッチドフィルタ相関の適用により、信号間の回転及びスケールの推定に対応する相関ピークの位置を見つけ出すことが可能になる。別の手法は、最小二乗法、特に直接最小二乗法を実行することである。以下に、最小二乗法の実装について説明する。これらは、逐次パイプライン型ハードウェア論理段階で処理を実装できるハードウェアにおける実装、並びに、専用ハードウェア処理ユニット、いくつかの例を挙げるならば、グラフィック処理装置GPU、デジタル信号プロセッサDSP、又はマルチコア中央処理装置CPUなどで並行に処理を実行できるソフトウェアにおける実装に特に有用である。00039最小二乗00040最小二乗技法00041最小二乗技法は、線形変換の初期推測を前提として最小二乗誤差すなわち、最尤推定値を生じる線形変換を推定する。演算は乗算及び加算からなり、ハードウェアに都合がよい。00042図3は、最小二乗法を示す流れ図である。一実装形態では、入力として、参照位置のセットに対する座標周波数又は空間領域のいずれかにおいて、及び変換された位置のセットに対する座標の対応するセットを取り込むやはり周波数又は空間領域のいずれかにおいて。例示のために、参照位置が周波数領域における特徴、特に周波数領域におけるピークに対応する実装形態のための技法について説明する。00043この最小二乗法は反復して実行され、反復ごとに3つのステップを含む。これら3つのステップは、図3において処理ブロック130、132、及び134で示される。00044変換された周波数座標の計算130この段階では、変換された周波数座標は、信号の初期変換及び元のすなわち変換されていない周波数座標を使用して計算される。00045座標更新132このステップでは、周波数振幅平面において変換された周波数の小さな近傍のあたりのピーク値を探索することによって、変換された周波数ごとにより適切な位置を求める。このステップの最後において、より適切なピーク位置がこの周波数について見つけられた場合は、各変換された周波数の座標が更新される。このプロセスで計算された最適周波数座標によって、単一線形変換では、もはや同時に求めることができない位置がもたらされる。00046変換更新134このステップでは、更新された線形変換が、最小二乗公式を使用して更新された座標から計算される。この更新された変換が、次の反復のための初期推測として使用される。最小二乗技法は、元の座標と変換された座標の間の二乗誤差を最小限にする変換を提供する。特に、最小二乗技法は、位置誤差の合計を最小二乗誤差の観点で最小限にする変換を提供する。誤差からの新しい変換の計算は、以下のように実装される。00047相関強度と呼ばれる相関の尺度が反復ごとに計算される。相関強度メトリックは、反復の早期の終了を決定するために使用してもよいし、正規化を行うために使用してもよい。00048理論的には、最小二乗技法は、線形変換パラメータの任意の初期推測から開始して参照信号と被疑信号との間の実際の線形変換を見つけ出すことができる。しかし、実用的見地からは座標更新が過度に複雑になるのを防止するために、線形変換パラメータの初期推測は、実際の線形変換からいくらか近くなければならない。したがって、この技法は初期推測に敏感である。00049変換の初期推測は、回転とスケールの対のように単純でありうる。00050この最小二乗法は、あらゆる任意の線形変換すなわち、回転、スケール、せん断変形、及び差分スケールdifferentialscaleを含むを決定することができる。00051直接最小二乗DLS00052DLSは、被疑信号と参照信号との間の線形変換を決定するための最小二乗技法の効率的な適用である。本発明の特定の実装形態は、画像に適用され、特に、被疑画像が、透かし入り画像であり、参照信号が、透かし入り画像に埋め込まれていると想定される透かし信号である。この場合、課題は、既知である元の参照信号と、被疑信号に埋め込まれていると想定されるその対応物との間の線形変換を決定することである。00053最小二乗技法が、線形変換の初期推測のまばらなセットsparsesetに適用される。00054DLSは、フーリエ-メリン型相関よりも必要とする評価が少ないと共に、フーリエ-メリンよりも正確な変換を提供することができる。前述のように、フーリエ-メリン領域における参照信号と被疑信号との間の相関が、回転及びスケールの推定値を与える。これとは対照的に、最小二乗では、あらゆる任意の線形変換例えば、線形変換パラメータの4次元ベクトルを提供することができる。00055DLSを用いて、2×2線形変換行列で包含される4次元空間を、まばらな2次元部分空間にわたる初期推測により極めて効率的に評価することができる。00056各DLS評価は、最小二乗技法を使用し、また2D部分空間上の他のDLS評価から独立している。したがって、DLS評価は、ハードウェア内又はマルチコアプロセッサアーキテクチャ上で効率的に実行することができる。各評価は、推定された線形変換及び対応する相関強度値をもたらす。候補線形変換は、最大相関強度値に対応する候補線形変換として識別される。これらの候補線形変換のうち1つ又は複数が、アフィン変換を回復するために更に処理される。00057DLSは、初期推測が2D部分空間に任意に広がることを可能にする。例えば、初期推測が回転/スケールの対を含む場合、回転軸及びスケール軸に沿った間隔は任意でありうる。これと比較して、フーリエ-メリン手法は、スケール軸での間隔が対数的であることを要する。任意の間隔の使用は、2つの利点、すなわち、向上された頑強性及び効率的な計算を備える。一般的な事例では、初期予測のセットは、初期推測が回転及びスケール値のまばらなサブセットにわたって均等に分布するように理想的に選択される。例えば、スケール軸での均等な間隔スケールの均等な増大が、効果的に計算されることができ、またノイズアーチファクトを低減する。適切な線形変換及び推定された変換の精度に収束するDLSの能力は、初期推測の数、及び最小二乗の反復の数によって影響される。これらのパラメータの最適値は、ハードウェアコスト、計算速度、及び所望の頑強性の間のトレードオフとして決定される。より洗練された戦略は、適応された数の反復と併せて初期推測の非常にまばらなセットを使用することから構成される。連続した反復からもたらされる変換が収束を示す場合、より多くの反復が行われる。この戦略は、頑強性を犠牲にせずに計算効率性を実現する。00058いくつかの用途では、被疑信号は、限定されたセットの変換を受けることがある。例えば、回転は、-30度と30度の間の範囲に制限されうる。このような状況では、DLS評価は、更に制限された範囲のまばらな初期推測に対して行われる。00059ノイズ及び歪みにより、DLSによって推定された線形変換にノイズが入る可能性がある。本発明の特定の事例では、変換は、弱い透かし信号を有する画像の単一画像ブロックから推定されたときにノイズが入る。推定された変換におけるノイズを低減するために、DLS出力の特性を利用する。DLSは、初期推測ごとに、推定された線形変換及び相関強度値をもたらすことを想起されたい。適切に設計されたセットの初期推測では、複数の初期推測が同様の線形変換につながる。言い換えれば、出力線形変換がクラスタ化される。線形変換推定におけるノイズを低減するために、線形変換のクラスタが識別され、それらの要素が適切に平均化される。適切な平均化は、相関強度のある種の関数例えば、非線形関数によって各線形変換を重み付けすることによって行うことができる。00060図4は、デジタル論理回路実装における処理の流れのブロック図である。フーリエ変換モジュール140は、メモリからの入力信号例えば、画像センサによって取り込まれた画像データのブロックにアクセスし、フーリエ変換及びフーリエ振幅Fouriermagnitudeデータを計算する。フーリエ振幅フィルタ142は、2Dフーリエ振幅データをフィルタリングする。1つのそのようなフィルタは、サンプル値をその8個の隣接のそれぞれと比較し、これらの比較に基づいてサンプル値を集約値に置き換える非線形フィルタである。一実装形態では、フィルタは、サンプル値のその8つの隣接の平均に対する比を使用するフーリエ振幅領域において。そして、フィルタの出力は、この比の関数この場合、非線形関数である。このフィルタは、例えば、参照信号が被疑信号に埋め込まれたデジタル透かしにおいて参照信号の特徴を抽出する際に特に役立つ。次いで、フィルタの出力が、直接最小二乗法に対する入力を形成する。00061座標の更新図3のブロック13200062座標更新プロセスは、対象となる変換された位置周波数を囲む小さな近傍のあたりのピーク又は角部若しくは特徴などの所望の特性の局所探索を含む。00063近傍は、典型的には、3×3若しくは2×2のサンプルの領域として定義され、又は問題領域及び用途に応じてかなり大きくなりうる。00064ピーク又は所望の特徴が変換された位置と異なる位置にある場合、変換された位置の座標は、この位置に更新される。00065最小二乗法は、被疑信号と参照信号との間の線形変換の推定値を提供する。完全なアフィン変換を回復するために、2つの信号間の位相シフト又は平行移動を計算する必要がある。1つの手法は、参照信号と被疑信号との両方の位相表現の間の位相相関を計算し、線形変換を考慮に入れる。本発明者らは、アフィン変換を回復するのに特に有利である処理モジュールを開発した。図1で先に説明したように、これらの処理モジュールは、位相推定及び位相偏移である。00066位相推定00067本発明の位相推定手法は、位相を計算し抽出するために追加の高速フーリエ変換FFTが続く画像の逆変換を行うのではなく、変換された信号のFFTから位相を計算するため、有利である。位相推定は、参照信号が被疑信号内で受けた線形変換を使用する。この線形変換を計算する1つの方法として直接最小二乗を示したが、マッチドフィルタ例えば、線形変換を近似するためのフーリエメリン相関を使用するなどして線形変換を計算する他の方法がある。00068この利点を強調して、図5及び図6は、位相情報を計算する異なる方法を示すブロック図であり、一方は位相推定が無く、他方は位相推定を有する。双方の方法は、直接最小二乗法を使用して、信号間の線形変換を推定する。第1のFFTは、直接最小二乗技法が基づいて作用する振幅情報を得るために行われる。図5では、位相を計算するための第2のFFTが続く逆線形変換を行うが、図6の手法は、本発明の位相推定技法を使用する。位相推定が、逆線形変換と第2のFFTの両方の追加的処理を回避する。00069図7は、位相推定が扱う問題を示す図である。線形変換は参照信号座標に適用されると、離散座標にマッピングされないことが見込まれる。この位相推定方法は、非離散すなわち実数値の座標位置での位相を計算する効率的手法を提供する。00070どのように位相推定が問題を扱うかを理解するために、位相推定方法の導出から始める。図8は、位相推定方法を導出するプロセス、及び導出をサポートする関連する計算を示す図である。図7、及び図8のブロック180に示されるように、導出の第1のステップは、フーリエ面において実位置vに配置された複素周波数からなる関数を仮定する。00071図8のブロック182及び対応する数式は、位相推定に使用される点広がり関数PSFの導出を示す。PSFは、整数複素数周波数の観点からフーリエ面において実位置に配置された複素周波数を分解することによって導出される。このPSFは、複素数値である。00072ブロック184に示されるように、導出の最後のステップでは、フーリエ面におけるPSFの畳み込みを行う。図8のブロック182の内積は、フーリエ基底関数に対するものであり、これによりPSFがもたらされる。次いで、PSFがブロック184で使用されて、フーリエ面において値の畳み込みがされる。00073図9は、線形変換及び参照信号を所与として位相を計算する位相推定方法を示す流れ図である本発明の位相推定プロセスでは2つの主要な段階がある。第1の段階では、実装形態が、線形変換に従って、既知の参照信号座標特に、既知の周波数座標での正弦曲線のセットを変換する。第2の段階では、実装形態が、変換された座標、及び被疑信号の周波数領域においてこれらの座標を囲む位相情報を使用して、変換された周波数座標の位相推定値を得る。このプロセスへの入力は、離散被疑信号であり、離散被疑信号は、仮定された変換例えば、事前に計算された線形変換、及び参照信号の周波数仕様これは、参照信号の正弦曲線の既知の周波数位置のセットであると共に、2次元FFTから複素周波数平面の形態でメモリに格納されている。実複素周波数realcomplexfrequencyごとに、位相推定が、以下のステップを適用する。00074a.提供された線形変換を使用して、周波数の変換された実位置例えば、非整数を計算するブロック190。00075b.整数座標フーリエ基底の観点から実位置における複素周波数を表現する。これにより複素PSFがもたらされるブロック192。00076c.被疑画像ブロックのFTTから、所望の実周波数を囲む整数周波数の位相を得るブロック194。PSFは、Δ=0でピークに達し、したがって、非整数のピークが期待されるように小さな近傍に現れる。特に、関数sinπΔ/NsinπΔ/Nは、極限に0でピークを有する。00077d.整数周波数の複素値とPSFの対応する複素値との積の合計を計算するブロック196。これは、実複素周波数における推定された位相を与える。00078PSF値を効率性のために事前計算してテーブルに格納することができる。更に、効率を高めるために位相を少数の位相角に量子化することもできる。位相推定の第1の段階の実装形態により、参照信号の各周波数位置を離散周波数サンプル間の適切な分数fractional位置に移動させる変換を行う。変換された参照信号の位相の特性は、信号周波数とは独立である。分数周波数位置ごとに、PSFテーブルが、最も近い離散周波数位置に対する事前計算された位相情報を含む。00079計算を単純化するために、実装形態は、各整数周波数間で分数周波数位置の限られた分解能を使用する。実装形態は、この分数周波数位置の数の減少を利用して、更にPSFテーブルのサイズを減少させる。PSFテーブルは、各許容された分数周波数位置のみについて事前計算された位相情報を含む。00080そして、このPSF位相情報は、すべての将来の推定のために再使用されるプロセスの第2段階において。1つの特定の実装形態では、位相情報が事前計算され、小さな離散テーブルに値が格納される。テーブルは、水平周波数方向及び垂直周波数方向について同じであり、したがって、実装形態は、2回アクセスし、値を組み合わせて2D周波数位置について期待される位相を作成する。00081本発明の位相推定動作は、効率的でありハードウェアに都合がよい。逆変換及び追加のFFTを取り除くのに加えて、この手法は、図5の方法で示すような被疑信号データ例えば、入力被疑画像へのアクセスを必要としない。代わりに、この手法は、図6に示すように既に計算された被疑信号の周波数データを使用する。したがって、位相推定がハードウェアでのパイプラインアーキテクチャに適している。00082一般に、位相推定技法は、最初に空間領域データを用いることなく、複素周波数領域における回転又は他の変換を行うために使用することができる。00083図10は、位相推定のデジタル論理回路実装を示すブロック図である。図10に示される位相推定実装は、モジュール200においてデータで被疑信号ブロックに関する位相情報のストリームを受け取る。制御モジュール202の制御下で、それは位相情報被疑信号ブロックの2次元FFTからの位相半平面をRAMメモリ204に格納する。また、線形変換候補がモジュール200のデータを通して受け取られ、モジュール206、208、及び212に直接格納される或いはRAM204に格納されてもよい。00084線形変換候補行列モジュール206は、行列における線形変換候補を形成し、それらを行列反転モジュール208及びデータ出力モジュール210に供給する。行列反転モジュール208は、線形変換行列を反転する。この実装形態では、線形変換は画像の空間変換のためである。被疑画像周波数領域において参照信号座標をマッピングするために、線形変換の逆転置を行う。次いで、変換座標モジュール212が、メモリ読取り専用メモリROM214から参照信号成分の位置を指定する参照信号座標を取り、その位置を被疑信号ブロックの座標空間の座標に変換する。制御モジュール216は、参照信号成分の位置のそれぞれを配列して、周波数領域における座標を提供する。各参照信号座標について、制御モジュール218は、2掛ける2の行列の点広がり関数PSF点を配列する。制御モジュール218は、そのようにして、参照信号成分の変換された座標に基づいて動作する座標上限/下限関数モジュール220を制御し、それがPSFテーブル222におけるその座標に対するPSFを選択する。次いで、座標上限/下限関数モジュール220が、位相情報RAM204内の隣接周波数位置を選択し、次いで、それが隣接位置での位相情報を積及び和論理演算子224に出力する。積及び和論理演算子224は、点広がり関数をテーブル222から位相情報に適用して、推定された位相を計算する。次いで、データ出力モジュール210が、対応する線形変換座標と共に、参照信号の参照座標ごとに推定された位相を出力する。この位相推定実装形態は、線形変換座標のすべてを繰り返して、LT候補ごとに各参照信号成分について推定された位相のセットを提供する。00085位相偏移00086図1を再度参照すると、位相推定に続くプロセスが、変換された参照信号の位相のこの推定値を使用して、参照信号と被疑信号との間の平行移動を決定している。この段階で平行移動を計算する代替的手法がある。本発明の手法は、変換された参照信号と被疑信号との位相表現の間の位相相関を行うことであるこれは逆FFT演算を必要とする。次に、位相偏移と呼ばれる代替的手法について説明する。000872D位相偏移00088位相偏移は、一般に2つの画像又は信号の間の平行移動を推定する代替的手法である。位相変換手法と比較して、位相偏移は、逆FTT動作を必要としない。00089図11は、位相偏移方法の概要を示す流れ図である。まず、位相偏移方法は、ステップ230で、参照信号と被疑信号との間の第1のレベルの細目例えば、整数オフセットで候補平行移動値のセット平行移動オフセットと呼ばれるを得る。図11のステップ232では、位相偏移方法は、候補平行移動の第1のセットのあたりでより高いレベルの細目例えば、分数オフセットを使用して参照信号と被疑信号との間のより良い適合を提供する平行移動値を決定することによって、それらの候補を絞り込む。00090指定された平行移動オフセットに対する位相偏移は、対象となるすべての参照信号成分での測定された位相と期待される位相との間の偏移の合計である。参照信号が、それぞれ特定の位相を有する正弦曲線のセットを備える場合では、期待される参照信号位相は、既知の平行移動オフセットでの正弦曲線の位相である。これらの期待される位相は、いくつかの平行移動オフセットのそれぞれについて提供され、それらは、位相角又は平行移動値例えば、特定の画像解像度でのピクセルオフセットの観点から指定することができる。言い換えれば、可能な平行移動オフセットごとに、参照信号についての期待される位相のセットがある。更に、他方の入力が、被疑信号から前もって計算された測定された位相である。期待される位相と測定された位相との間の偏移は、平行移動オフセットごとに計算される。各周波数における偏移は、測定された位相と期待される位相との間のユークリッド距離のような距離測度を使用して計算してもよい。すべての可能な平行移動オフセットについて計算された位相偏移が、2D位相偏移面を構成する。2D位相偏移面における最小値の位置が、平行移動オフセットの位置を示す。000912D位相偏移方法は、加算のみ乗算なしを用いて、2DFFTの計算コストのごく一部のコストで実装することができる。また、オフセットごと及び周波数ごとの位相偏移演算を独立して計算することができ、並列実装がもたらされる。これは、位相相関のような他の代替方法に対する利点である。00092位相差及び位相偏移は、複素数値として計算することも、角度の観点から直接計算することも可能である。角度を用いた操作により、計算の効率性が改善される。00093ユークリッド距離以外の距離測度を使用することもできる。例えば、L1ノルム又は非線形尺度が、関連する信号及びノイズの特性に応じて改善を実現することができる。00094特に、偏移の合計は、測定された位相角度と期待される位相角度との間の絶対差の合計として計算することができ、各差は、-πとπの間に含まれる2πを法とする。この計算は、ハードウェアで実装するのに効率的である。00095サブサンプル平行移動推定00096位相偏移が、任意の実数値の平行移動オフセットについて計算されうる。これは、位相相関手法を用いる整数値の平行移動推定ではなく、サブサンプル平行移動推定を行う。00097サブサンプル平行移動で位相偏移メトリックを計算する能力を、平行移動絞込み技法を実装するために使用することができ、この技法では、まず、整数平行移動が、適切な平行移動オフセットを決定するために評価され、適切な平行移動オフセットの周辺で、サブサンプルすなわち、画像コンテンツに対する部分的サブピクセル平行移動オフセットを評価することによって更なる絞込みが行われる。000981次元1D位相偏移00099基本的位相偏移の定式は、周波数におけるパターンを活用するために修正してもよい。1次元水平又は垂直の座標値の線形結合がゼロである周波数のセットにより、直交次元での1D位相偏移の定式がもたらされる。概念的には、これにより、2D空間の2D正弦曲線のセットの乗算である直交次元での仮想1D信号がもたらされる。仮想1D信号の周波数は、直交次元の周波数の合計によって与えられる。次いで、平行移動を、2D位相偏移のコストのごく一部のコストで、1D位相偏移の定式を用いて、各次元で独立して推定することができる。加えて、最小位相偏移メトリックの探索は、1Dに沿っておりすなわち、1次元データセット上であり、計算コスト全体を更に減少させる。000100いくつかの場合、線形結合が、元の信号のサポート長例えば、128ポイントの外側の仮想1D信号がもたらされる。これらの仮想1D信号は、ナイキストより高い周波数を有する。この場合、1D位相偏移方法は、エイリアシングを回避するために、より大きい人工的なサポート長によって例えば、より高いサンプリングレートを保証するために256ポイントを使用して指定してもよい。エイリアシングを回避することにより、ノイズ中の平行移動推定の信頼性が向上する。0001011D位相偏移は、直交次元のすべての結果として生じる仮想周波数が偶数値であるとき、平行移動の曖昧性を生じる。例えば、2D空間内の長さ128×128の象限対称周波数の対例えば、[-45,9]と[45,9]、並びに[-44,6]と[44,6]などが乗算されると、結果として生じる1D位相偏移は、長さ64の周期性を有する。同じ値の2つの周波数を組み合わせることで生じる周波数倍増により、偶数値の1D信号周波数例えば、18及び12がもたらされ、それにより曖昧性が導入される。エイリアシングの当然の帰結として、2つの周波数A及びBを混合することにより、新しい周波数AB及びA-Bを作り出される。周期性によって生じる曖昧性は、特定の平行移動の更なる評価のために2D位相偏移を使用して解消されうる。或いは、曖昧性は、仮想周波数の相当数約半分が奇数値であることを保証することによって解消することができる。0001021D位相偏移と2D位相偏移の組み合わせを用いて、1D位相偏移の少ない計算負荷及び2D位相偏移の頑強性を活用することができる。000103図12及び図13は、ハードウェア実装をより詳細に示すブロック図である。図12は、線形変換の推定例えば、図1のブロック102、及び図2のブロック122~124のためのデジタル論理回路のブロック図である。図13は、位相推定及び位相偏移のためのデジタル論理回路のブロック図である。000104図12に示されるように、実装形態への入力は、被疑画像からの画像データのパケットである。実装形態は、参照信号であるデジタル透かしの初期座標空間に対する被疑画像である入力画像に埋め込まれたデジタル透かし信号のアフィン変換を計算する。この特定の例では、参照信号は、透かし信号に対応する周波数ピークのセットすなわち、互いに対し既知の疑似ランダム位相を有する正弦曲線のセットである。プロセスのこの時点で、被疑画像は、サンプリング走査、印刷などによって引き起こされる様々な形態の歪み並びに幾何歪みにさらされていることがある例えば、画像編集、及び/又はスキャナ又はカメラからの変換された状態の画像の取り込みの結果として。この歪みの結果として、既知の参照信号と被疑画像に埋め込まれたその対応物との間の変換を最も近似するアフィン変換が知られていない。目的は、埋め込み時の参照信号と被疑信号内の埋め込まれた参照信号との間の変換を最も近似するアフィン変換を計算することである。000105回路実装を説明する前に、参照信号及び被疑信号の属性の背景を説明することが有益である。その理由は、それらの信号が、ハードウェアの設計検討に影響するからである。デジタル透かしは、信号の隣接ブロックの範囲内で繰り返されている例えば、タイル様式で。デジタルハードウェア回路は、入力パケットのストリームに基づいて動作する。入力パケットは、透かしが当初埋め込まれたブロックの元のサイズにおおむね対応する被疑画像のブロックの重複ブロックを含む。各ブロックは、128掛ける128のピクセルのアレイである。メモリ及びFFTフィルタなどのサイズは、これらの信号の属性に基づいて適合され、また、用途及び用途に応じた信号仕様によって異なることが可能である。000106前置フィルタ300は、先に説明した方法を用いて画像ブロック内のピクセル値をフィルタリングする。すなわち、各サンプルは、その8つの隣接サンプルと比較され、これらの比較の関数である値に置き換えられて、埋め込まれた参照信号を被疑画像データから隔離しようとする非線形フィルタリングの形態を実現する。000107ウィンドウ動作302は、2DFFTのためにフィルタリングされた画像データを準備する。結果として得られたフィルタリングされた画像データブロックは、FTT2D304に受け取られてRAMに格納される。この場合、RAM306は、図12に示される他のハードウェアコンポーネントと共にACIC内に実装される。FTT2Dは、空間入力データのブロックを処理して、複素周波数データを生成する。複素周波数データの実部及び虚部は、単一のパイプ出力ストリーム内へ出力でインタリーブされる。000108CORDIC308は、インタリーブされた実Re及び虚Imストリームをインタリーブされた振幅及び位相ストリームに変換する。当分野で知られているように、CORDICは、三角関数の効率的なデジタル信号処理実装のための方法である。フーリエ振幅フィルタ310は、データのフーリエ振幅部分のみをフィルタリングする。フィルタは、サンプル値のその8個の隣接の平均に対する比を使用するフーリエ振幅領域において。そして、フィルタの出力は、この比の関数この場合、非線形関数である。位相は、変更されずに通過する。000109直接最小二乗DLSモジュール312は、フィルタリングされたフーリエ振幅及び位相データのインタリーブされたストリームを受け取る。これらのデータストリームのそれぞれは、RAMブロック314及び316として示されるRAMに格納される。000110DLSは、最大相関強度に関して各潜在的線形変換候補を計算し絞り込む。DLSモジュール312の出力は、格納された位相ブロックに先行される線形変換LT候補のストリームである。位相推定に使用される位相データは、位相を候補線形変換ごとに推定できるように、サンプリングされる準備ができている形態で格納される。000111ブロック318では、相関の尺度に基づいて、上位10個の候補を見つけ出すために線形変換候補の入力ストリームをソートする。この相関の尺度は、この実装形態では、線形変換候補が参照信号及び被疑信号をアライメントするために使用された後、参照信号と被疑信号との間のドット積として計算される相関強度である。RAM320は、上位の線形変換候補及び対応する相関メトリックを格納するために使用されるメモリである。000112図13は、図12が上位線形変換候補で終了したところから開始する。位相推定モジュール322は、位相データのシステムを受け取ってRAM324に格納する。位相推定モジュールは、線形変換候補のそれぞれを使用して、参照信号内の周波数位置のそれぞれに対応する被疑画像内の信号成分に関する位相のセットを推定する。線形変換候補ごとに、位相推定モジュールは、線形変換候補と、参照信号内の主は数位置に対応する位相のセットとの両方を提供する。これらの位相は、被疑信号に埋め込まれた参照信号成分の位相の尺度を表す。特に、参照信号がデジタル透かしとして被疑信号内に埋め込まれるこの実装形態では、位相のセットは、ランダム位相を有する正弦曲線に対応する埋め込まれた参照信号成分の位相の推定値を表す。000113他の実装形態では、位相推定モジュールは、DLSモジュール内に含まれてもよい。その理由は、参照信号座標を変換する行列計算の大部分はそこで既に計算され、位相データもまた容易に利用可能であるからである。この結果、DLSモジュールは、線形変換とこれらの変換のそれぞれの推定された位相との両方を出力することになる。000114位相推定方法をデジタル透かし検出器の実装形態として示したが、位相推定方法は、信号プロセッサが被疑信号内の既知の参照信号を見つけ出そうとする他の用途に適用可能である。例として、信号プロセッサが画像内の既知の参照信号を見つけ出そうとする物体認識及びパターンマッチングがある。位相推定方法は、信号プロセッサが、被疑画像の成分であると疑われる参照信号の位相の推定を計算することを可能にする。次いで、これらの位相推定は、参照信号が被疑信号内に存在するかどうかを検出するために追加のマッチング又は認識動作で使用されうる。これらの方法では、同じ一般的手法が行われる。すなわち、位相推定は、被疑信号の位相と共に、期待される信号パターンと被疑信号内の対応する成分との間の変換の推定値を使用して、被疑画像内の信号パターンの位相の推定値を計算する。000115図13に戻ると、位相偏移モジュール326が、各線形変換候補と、被疑信号内の参照信号の推定された位相の対応するセットとを受け取る。位相偏移モジュール326は、線形変換候補ごとに位相偏移面を計算する。この面は、位相偏移のアレイであり、アレイ内の各要素は、平行移動オフセットに対応し、要素の値は、対応する期待される位相差と測定された位相差との間の位相偏移メトリックの合計である。2D位相偏移について、これは、平行移動オフセットのすべてのペア例えば、128掛ける128の値の面に対応する位相偏移値の2Dアレイである。先に述べたように、特定の平行移動オフセットに対する位相偏移は、特定の参照信号成分において期待される位相差と測定された位相差との間の偏移を計算する異なるメトリックの合計として計算される。本発明の実装形態では、0、90、180、及び270度の配向に対応する各線形変換候補についての4つの配向がある。配向のための位相偏移面を計算するのが終わると、位相レジスタが90度再配向される。0001162D偏移モジュールの目的は、位相偏移における最小値に対応する1つ又は複数の平行移動オフセット候補を提供することである。言い換えれば、目的は、期待される位相差と測定された位相差との2つの間の最小偏移によって決定されるように、期待される位相差と測定された位相差が最も合致する平行移動オフセットを見つけ出すことである。実装形態は、大きな定数から位相偏移を引いて、最小値を探索する問題を便宜上ピークを探索する問題に変換するこの場合、ピークは、位相偏移面における最小位相偏移メトリックを表す。目的は、期待される信号と測定された信号すなわち、既知の参照信号と被疑画像におけるその対応物の最良の合致を見出すことであるので、ハードウェアは、その2つの間の偏移のピークを見つけ出そうとする。初期2D位相偏移面が、計算効率のために整数平行移動オフセットに対して計算される。しかし、実際の平行移動は、分数すなわち、サブピクセルオフセットに存在することがある。結果として、反転された位相偏移面におけるピークが、2掛ける1のピクセル領域に広がることがある水平又は垂直方向に。この影響を解消するために、ピークは、最高2×1Highest2x1モジュール328において2×1領域にわたって探索される。000117ノイズ及び歪みの影響を解消するために、絞り込みモジュール332を使用して上位N個のピーク候補が更に評価される。000118絞り込みモジュールは、反転された2D位相偏移面で識別されるピーク例えば、位相偏移面における振幅が最も最小のものの上位N個のピーク例えば、2掛ける1から開始する。Nの値は、計算効率と頑強性の間のトレードオフとして決定され、通常2と10の間である。次いで、これらN個のピークのそれぞれについて、絞り込みモジュールは、ピークに対応する平行移動オフセットのあたりの近傍の絞り込まれた位相偏移面を計算する。これらの絞り込まれた位相偏移面は、サブピクセル平行移動オフセットに対して計算される。特に、期待される位相差は、ピークの整数平行移動オフセット位置のあたりのM掛けるMアレイにおけるサブピクセル平行移動のそれぞれについて計算される。Mの値及び平行移動の分数すなわち、サブピクセルの増分は、所望の計算処理量及び頑強性に基づいて決定される。Mの典型的な値は16であり、典型的な分数の増分は、4分の1ピクセルである。位相偏移の合計が、サブピクセル位相偏移面を提供するために計算される。より高いピークを有するサブピクセルオフセットがある場合、このサブピクセルオフセットは上位ピークのリストに含められる。0001192D位相偏移モジュールの出力は、線形変換候補であり、位相偏移面絞込み段階で計算される任意の表面を含むにおける最小値に対応するピーク座標のリストが後続する。000120平行移動補正モジュール330は、線形変換候補のそれぞれについて計算された平行移動オフセットを補正する。補正の性質は、実装形態に特有であり、実装形態の詳細に依存し、例えば、入力として使用される参照信号位相がフーリエ表現ブロックの中央に対して表現されるかそれともブロックの角部に対して表現されるか、フーリエ処理及び表現がブロックの中央に対してかそれとも角部に対してか、及び、変換された被疑信号又は参照信号の座標系に対して表現されるかに依存する平行移動の差に依存する。000121図14は、偏移メトリックに基づく位相偏移方程式を示す図である。この図は、位相偏移メトリックの例を示す。このメトリックは、位相偏移面内の位相偏移値をどのように計算するかを示す。図14に示されるように、位相偏移は、参照信号の特定の周波数成分iについて測定された位相差と期待される位相差との間の偏移を表す。測定された位相差は、被疑信号内の参照信号の推定された位相例えば、位相推定プロセスで決定されたについての周波数成分iの位相角と、参照信号成分の既知の位相角との間の差である。前述のように、位相推定プロセスは、変換された状態で被疑信号について位相角推定値を提供する。実装形態では、既知の参照信号のために使用される位相角は、その元の未変換の状態にある。000122期待される位相差は、水平及び垂直位相オフセットから直接計算される。上記のように、これらのオフセットは、整数オフセットとして始まり、次いで、絞込みのためにサブ整数sub-integer例えば、サブピクセルとなる。000123式中、参照信号中にM個の周波数成分があることに留意されたい。偏移メトリックは、周波数成分のそれぞれについての個々の偏移の合計である。ユークリッド距離測度が示されているが、前述のように他の偏移メトリックが使用されてもよい。000124図14の描写から、図示の2Dの場合、参照信号を使用することによって、1D位相偏移の2つの別個のインスタンスに減少させることができることが分かり、この参照信号は、垂直軸に対して対称であって、したがって水平成分が互いに打ち消す対の周波数成分を有し、また同様に、水平軸に対して対称であって、したがって垂直成分が互いに打ち消す対の周波数成分を有する。前述のように、これにより、垂直及び水平平行移動オフセットが、各ID位相偏移アレイにおけるピークの独立した探索で別個に決定されることが可能になる。000125図15は、DLS方法の実装形態を示す図である。これは、例えば図12のブロック312内の処理の実装形態である。前述のように、DLSモジュールは、ブロック350でシード線形変換候補のセットから開始する。例えば、この実装形態は、2掛ける2の線形変換行列で表現される線形変換パラメータのサブセットを含む、回転-スケール候補のまばらなセットから開始する前述の一例のように。2掛ける2の行列で表現される他の線形変換パラメータは、差分スケール例えば、水平及び垂直スケール並びにせん断変形例えば、水平及び垂直せん断変形を含む。DLS方法が回転及びスケール候補から開始すると、他のパラメータは、任意の追加の変換を提供しないように当初想定され、方法の引き続く反復により、他の線形変換をパラメータが参照信号と被疑信号との間のより良い適合を実現するように変化することが可能なように線形変換を更新する。他の実装形態では、まばらな線形変換候補の異なるサブセット又は定式が、シード候補として選択されてもよい。000126シード候補の開始セット内の各線形変換候補について、DLSモジュール内の変換モジュールが参照信号内の周波数成分の周波数位置を変換する352。次いで、サンプルモジュールは、各変換された位置の場所周辺の近傍位置で被疑信号の周波数平面をサンプリングする354。近傍は、変換された周波数位置を囲む領域であり、実際的には、被疑信号のFFTにおけるいくつかの離散周波数位置を包含する。次に、DLSモジュール内の相関モジュールが、信号相関メトリックを計算し356、この信号相関メトリックは、参照信号の各変換された成分の周囲の被疑信号内のこれらの領域について参照信号と被疑信号との間の相関の尺度を提供するものである。このプロセスの終わりに、DLSモジュールは、線形変換候補に対する信号相関メトリックを有する。このメトリックが、先行の反復に対する先に格納されたメトリックに対して改善されたかどうかが決定される358。DLSモジュールは、相関メトリックに改善がある358、及び反復限度に達していない360限り、続行される。000127領域及びそれらの領域について計算された信号相関メトリックを計算する様々な方法がある。DLSモジュールが4つの最近傍位置からサンプリングをする一実装形態では、信号相関メトリックが、被疑信号内の変換された場所ごとのそれらの隣接物での周波数振幅の共一次内挿の合計として計算される。代替形態は、共3次内挿を使用して、及び各変換された周波数成分の場所のあたりの3掛ける3のサンプル領域を使用して相関を計算することを含む。相関は、領域における参照信号及び被疑信号の位相成分の相関も含むことができる。この場合、位相推定方法を用いて被疑信号内の位相が推定される。000128DLSモジュールが、信号相関を改良しまた反復限度より下である線形変換候補を見つけ出す場合、DLSモジュールは、最小二乗計算器への入力のセットの確立に進み、最小二乗計算器は、新しい候補線形変換を計算する。入力のこのセットは、周波数振幅の最大値が存在する、各変換された周波数成分位置に対応する周波数成分位置のセットを含む。参照信号の成分ごとのこれらの新しい位置を見つけ出すプロセスは、ブロック362に反映されている。特に、座標更新モジュールは、変換された座標位置のあたりの近傍の特徴座標例えば、ピークを計算する。次に、最小二乗計算器364は、参照信号成分をそれらの元の場所からブロック362で見出された新しい位置へ最も良くマッピングする線形変換を見つけ出すために、最小二乗法を使用することにより、新しい線形変換候補を計算する。000129ブロック362に示されるプロセスは、前述の座標更新の実装形態である。参照信号の周波数成分の座標を更新する1つの手法は、2掛ける2、3掛ける3、5掛ける5など、変換された周波数位置のあたりのサンプル領域のような隣接領域における最大の振幅を有する隣接周波数位置の座標を選択することである。このプロセスは、新しい座標を見出すために内挿を必要としない。いくつかの実装形態では、本発明らは、3掛ける3の近傍は、2~3までの差分スケールアップ、時には5までのスケールアップを含むことを見出した。より大きな近傍を用いることと、参照信号の隣接周波数成分のノイズによる潜在的な混乱との間にトレードオフがある。本発明の実装形態は、参照信号を使用し、Mは、35~75の範囲であり、被疑画像は、およそ100ドットパーインチDPIの解像度でサンプリングされ、ブロックサイズ及びFFTサイズは、128掛ける128サンプルである。近傍サイズ及び形状は、参照信号の固有の特性に合わせて調整してもよい。近傍サイズは、周波数の増大と共に増大することができる。近傍サイズ及び形状は、参照信号内の隣接周波数成分によるノイズの競合を避けるように調整してもよい。近傍サイズ及び形状は、線形変換候補例えば、LT候補によって変換されたに応じて適合させることもできる。また、変換された位置の座標の更新は、隣接ピークの中心例えば、正規化された質量中心、質量中心、二次フィットquadraticfit、又は隣接値の他の内挿を見つけ出すことなどによって、隣接値の組み合わせとして計算してもよい。000130ブロック364の最小二乗計算器は、図に示される式を実装して、式の左側の2掛ける2の線形方程式を解く。これは、乗算及び加算論理回路を使用してハードウェアで実装され、もちろん、ソフトウェアファームウェア命令を含むで実装されてもよい。図示のように、入力は、参照信号成分の座標、及び先行ブロック362から決定されるように被疑信号内の参照信号についての対応する更新された座標である。000131ブロック364で線形変換候補の更新を計算した後、DLSモジュールはこの線形変換を新しい候補として追加し、ブロック352に戻る。000132判断ブロック358~360で決定されるようにDLSモジュールが完了すると、結果として得られた線形変換候補及びそれに関連する信号相関メトリックが、更なる処理のために格納される366。DLSモジュールは、ブロック368に示されるように、更なるシード線形変換候補について反復をする。初期候補が図示のように処理されて絞り込まれると、DLSモジュールは、各初期シード候補について絞り込まれた線形変換候補を有する。DLSモジュールは、このセットの絞り込まれた線形変換候補を探索して最も強い相関を求める。次いで、相関に基づく上位候補のサブセットが、前述のように更なる処理で使用されうる。また、前述のように、線形変換候補は、クラスタ化され組み合わされて新しい線形変換候補を形成することができる。結語000133具体的な実装形態を参照して本技術の原理を説明し例示したが、本技術は、多くの他の異なる形態で実装可能であることが理解されよう。明細書を過度に長くせずに包括的な開示を行うために、出願人は、上記に参照した特許及び特許出願を参照により組み込む。000134上述の方法、プロセス、及びシステムは、ハードウェア、ソフトウェア、又はハードウェア及びソフトウェアの組み合わせで実装することができる。例えば、DLS、位相推定、及び位相偏移のための信号処理動作は、メモリに格納された命令として実装され、プログラマブルコンピュータソフトウェア及びファームウェア命令の両方を含むで実行され、専用デジタル回路内のデジタル論理回路、又は1つ若しくは複数のプロセッサ及びデジタル論理回路モジュールで実行される命令の組み合わせとして実装されてもよい。前述の方法及びプロセスは、システムのメモリ電子、光、又は磁気ストレージデバイスなどのコンピュータ可読媒体から実行されるプログラムに実装可能である。方法、命令、及び回路は、電子信号又は他の電磁形状の信号に基づいて動作する。これらの信号は更に、画像センサに取り込まれた画像信号のような物理信号、音声センサに取り込まれた音声、及び他のタイプのためのセンサに取り込まれた他の物理信号タイプを表す。これらの電磁信号表現は、信号間の線形変換、位相シフト、及び平行移動を決定するように、上述のような異なる状態に変換される。000135上記の方法、命令、及びハードウェアは、参照及び被疑信号成分に基づいて動作する。信号を基底関数に投影することによって形成される信号成分の合計として信号を表すことができるので、上記の方法は、一般に様々な信号タイプに適用される。例えば、フーリエ変換は、基底関数のセットへの信号の投影の合計として信号を表す。000136上述の実施形態における要素及び特徴の特定の組み合わせは例示に過ぎず、これらの教示と本明細書及び参照により組み込まれた特許/出願における他の教示との交換及び置換も考えられる。"