(57)【特許請求の範囲】
【請求項１】
デジタルデータを抽出するために画像内の参照信号の幾何変換を決定する方法であって、
プログラムされたプロセッサ又はデジタル論理回路を用いて、
前記画像を周波数領域に変換して、整数座標において前記画像の離散周波数領域表現を生成するステップと、
点広がり関数に従って、前記画像の前記離散周波数領域表現内の非整数座標における複素周波数成分を推定するステップと、
参照信号の複数の参照信号成分について、
候補幾何変換に従って、参照信号成分の座標を変換するステップ、及び
前記参照信号成分の前記座標を、前記変換された参照信号成分の前記座標のあたりの前記離散周波数領域表現の近傍内の位置へ更新するステップであって、前記位置が、前記近傍内の周波数振幅の最も高い周波数振幅に対応し、前記近傍における非整数位置での振幅値が、非整数位置において推定された前記複素周波数成分を使用して計算される、当該ステップと、
前記参照信号成分を前記更新された座標に変換する新しい幾何変換を決定するステップと、
前記新しい幾何変換を適用して、符号化されたデジタルデータを前記画像から抽出するステップと、
を含む方法。
【請求項２】
前記非整数座標における前記複素周波数成分を推定するステップが、点広がり関数から取得された重みを整数位置での隣接複素周波数成分に適用することを含み、
前記近傍内の前記周波数振幅が、前記近傍における前記複素周波数成分の振幅である、請求項１に記載の方法。
【請求項３】
前記参照信号成分が、前記周波数領域におけるピークを含む、請求項１に記載の方法。
【請求項４】
前記参照信号成分が、正弦曲線を含む、請求項１に記載の方法。
【請求項５】
前記新しい幾何変換を適用して画像ブロックの幾何歪みを近似することに基づいて、前記画像ブロックにおける参照信号についての信号信頼度メトリックを決定するステップと、
前記信号信頼度メトリックによって、前記画像ブロックから抽出されたデジタルメッセージ要素を重み付けするステップと、
を含む、請求項１に記載の方法。
【請求項６】
幾何変換候補について、前記変換、及び前記複数の参照信号成分のより低い周波数サブセットとの相関の測定を行って、更なる絞り込みのための前記幾何変換候補のサブセットを決定するステップと、
複数の絞り込み段階において、前記幾何変換候補の前記サブセットに対して、前記変換、相関の前記測定、座標の前記更新、及び新しい幾何変換の前記決定を行うステップと、
を含む、請求項１に記載の方法。
【請求項７】
１つ又は複数のプロセッサ上で命令を実行して、変換、測定、更新、前記新しい幾何変換を決定すること、及び前記新しい幾何変換を適用することの動作を実行するステップを含む、請求項１に記載の方法。
【請求項８】
専用デジタル論理回路において、変換、測定、更新、前記新しい幾何変換を決定すること、及び前記新しい幾何変換を適用することの動作を行うステップを含む、請求項１に記載の方法。
【請求項９】
命令が格納された非一過性のコンピュータ可読媒体であって、前記命令がプロセッサによって実行されたとき、デジタルデータを抽出するために画像内の参照信号の幾何変換を決定する方法を実施し、前記方法が、
前記画像を周波数領域に変換して、整数座標において前記画像の離散周波数領域表現を生成するステップと、
点広がり関数に従って、前記画像の前記離散周波数領域表現内の非整数座標における位相を推定するステップと、
参照信号の複数の参照信号成分について、
候補幾何変換に従って、参照信号成分の座標を変換するステップ、及び
前記参照信号成分の前記座標を、前記変換された参照信号成分の前記座標のあたりの前記離散周波数領域表現の近傍内の位置へ更新するステップであって、前記位置が、前記近傍内の周波数振幅の最も高い周波数振幅に対応し、前記近傍における非整数位置での振幅値が、非整数位置において推定された前記位相を使用して計算される、当該ステップと、
前記参照信号成分を前記更新された座標に変換する新しい幾何変換を決定するステップと、
前記新しい幾何変換を適用して、符号化されたデジタルデータを前記画像から抽出するステップと、
を含む、非一過性のコンピュータ可読媒体。
【請求項１０】
デジタルデータ抽出のための装置であって、
画像センサと、
前記画像センサにより取り込まれた画像、及びソフトウェア命令を格納するためのメモリと、
前記メモリに結合された１つ又は複数のプロセッサと、
を備え、
前記１つ又は複数のプロセッサが、前記ソフトウェア命令を実行して、
幾何変換候補を参照信号成分に適用して、変換された座標を取得することと、
前記変換された参照信号成分の前記座標のあたりの近傍内の前記参照信号成分の新しい座標を、前記近傍内の最も高い周波数振幅を突き止めることによって決定することであって、前記近傍における非整数位置での振幅が、点広がり関数に従う整数位置での周波数成分の重み付けに基づいて取得される、当該決定することと、
前記参照信号成分を前記新しい座標に適合させる新しい幾何変換を計算することと、
前記新しい幾何変換を用いて決定された位置で前記画像から符号化されたデジタルデータを抽出することと、
を行うように構成されている、装置。
【請求項１１】
デジタルデータを抽出するために画像内の参照信号の幾何変換を決定する方法であって、
プログラムされたプロセッサ又はデジタル論理回路を用いて、
参照信号の複数の参照信号成分について、
候補幾何変換に従って、参照信号成分の座標を変換するステップ、
前記変換された参照信号成分と前記画像との間の相関を測定するステップであって、前記相関が、前記変換された参照信号成分の前記座標のあたりの隣接座標における前記画像の周波数領域変換の複素成分の組み合わせを含み、前記複素成分の組み合わせが、前記隣接座標における位相関係に従って前記複素成分を組み合わせる、当該ステップ、及び
前記参照信号成分の前記座標を、前記変換された参照信号成分の前記座標のあたりの近傍内の位置へ更新するステップと、
前記参照信号成分を前記更新された座標に変換する新しい幾何変換を決定するステップと、
前記新しい幾何変換を適用して、符号化されたデジタルデータを前記画像から抽出するステップと、
を含む方法。
【請求項１２】
前記位相関係が、右上隣接要素と左下隣接要素とで位相がマッチすること、及び左上と右下とで位相がマッチすることを含み、前記右上と前記左上との位相が１８０度異なる、請求項１１に記載の方法。
【請求項１３】
前記位相関係が、点広がり関数に従って隣接座標に重み付けすることを含む、請求項１１に記載の方法。
【請求項１４】
前記参照信号成分が、正弦曲線を含む、請求項１１に記載の方法。
【請求項１５】
前記新しい幾何変換を適用して画像ブロックの幾何歪みを近似することに基づいて、前記画像ブロックにおける参照信号についての信号信頼度メトリックを決定するステップと、
前記信号信頼度メトリックによって、前記画像ブロックから抽出されたデジタルメッセージ要素を重み付けするステップと、
を含む、請求項１１に記載の方法。
【請求項１６】
幾何変換候補について、前記変換、及び前記複数の参照信号成分のより低い周波数サブセットとの相関の前記測定を行って、絞り込むために前記幾何変換候補のサブセットを決定するステップと、
複数の絞り込み段階において、前記幾何変換候補の前記サブセットに対して、前記変換、相関の前記測定、座標の前記更新、及び新しい幾何変換の前記決定を行うステップと、
を含む、請求項１１に記載の方法。
【請求項１７】
１つ又は複数のプロセッサ上で命令を実行して、変換、測定、更新、前記新しい幾何変換を決定すること、及び前記新しい幾何変換を適用することの動作を実行するステップを含む、請求項１１に記載の方法。
【請求項１８】
専用デジタル論理回路において、変換、測定、更新、前記新しい幾何変換を決定すること、及び前記新しい幾何変換を適用することの動作を行うステップを含む、請求項１１に記載の方法。
【請求項１９】
命令が格納された非一過性のコンピュータ可読媒体であって、前記命令がプロセッサによって実行されたとき、デジタルデータを抽出するために画像内の参照信号の幾何変換を決定する方法を実施し、前記方法が、
参照信号の複数の参照信号成分について、
候補幾何変換に従って、参照信号成分の座標を変換するステップ、
前記変換された参照信号成分と前記画像との間の相関を測定するステップであって、前記相関が、前記変換された参照信号成分の前記座標のあたりの隣接座標における前記画像の周波数領域変換の複素成分の組み合わせを含み、前記複素成分の組み合わせが、前記隣接座標における位相関係に従って前記複素成分を組み合わせる、当該ステップ、及び
前記参照信号成分の前記座標を、前記変換された参照信号成分の前記座標のあたりの近傍内の位置へ更新するステップと、
前記参照信号成分を前記更新された座標に変換する新しい幾何変換を決定するステップと、
前記新しい幾何変換を適用して、符号化されたデジタルデータを前記画像から抽出するステップと、
を含む、非一過性のコンピュータ可読媒体。
【請求項２０】
デジタルデータ抽出のための装置であって、
画像センサと、
前記画像センサにより取り込まれた画像、及びソフトウェア命令を格納するためのメモリと、
前記メモリに結合された１つ又は複数のプロセッサと、
を備え、
前記１つ又は複数のプロセッサが、前記ソフトウェア命令を実行して、
幾何変換候補を参照信号成分に適用して、変換された座標を取得することと、
前記変換された参照信号成分についての相関メトリックを計算することであって、前記相関メトリックが、隣接座標における位相関係に従って、前記変換された座標の隣接座標における前記画像の周波数成分を組み合わせる、当該計算することと、
前記変換された参照信号成分の前記座標あたりの近傍内に前記参照信号成分の新しい座標を決定することと、
前記参照信号成分を前記新しい座標に適合させる新しい幾何変換を計算することと、
前記新しい幾何変換を用いて決定された位置で前記画像から符号化されたデジタルデータを抽出することと、
を行うように構成されている、装置。
【請求項２１】
デジタルデータを抽出するために画像内の参照信号の幾何変換を決定する方法であって、
プログラムされたプロセッサ又はデジタル論理回路を用いて、
参照信号の複数の参照信号成分について、
候補幾何変換に従って、参照信号成分の座標を変換するステップ、
前記変換された参照信号成分と前記画像との間の相関を測定するステップ、及び
前記参照信号成分の前記座標を、前記変換された参照信号成分の前記座標のあたりの近傍内の位置へ更新するステップと、
前記参照信号成分を前記更新された座標に変換する新しい幾何変換を決定するステップと、
前記新しい幾何変換を適用して、符号化されたデジタルデータを前記画像から抽出するステップと、
幾何変換候補について、前記変換、及び前記複数の参照信号成分のより低い周波数サブセットとの相関の前記測定を行って、絞り込むために前記幾何変換候補のサブセットを決定するステップと、
複数の絞り込み段階において、前記幾何変換候補の前記サブセットに対して、前記変換、相関の前記測定、座標の前記更新、及び新しい幾何変換の前記決定を行うステップと、
を含む方法。
【請求項２２】
前記相関が、前記複数の絞り込み段階における絞り込みのために幾何変換候補を選択するために評価される、請求項２１に記載の方法。
【請求項２３】
前記参照信号成分が、周波数領域におけるピークを含む、請求項２１に記載の方法。
【請求項２４】
前記参照信号成分が、正弦曲線を含む、請求項２１に記載の方法。
【請求項２５】
前記新しい幾何変換を適用して画像ブロックの幾何歪みを近似することに基づいて、前記画像ブロックにおける参照信号についての信号信頼度メトリックを決定するステップと、
前記信号信頼度メトリックによって、前記画像ブロックから抽出されたデジタルメッセージ要素を重み付けするステップと、
を含む、請求項２１に記載の方法。
【請求項２６】
１つ又は複数のプロセッサ上で命令を実行して、変換、測定、更新、前記新しい幾何変換を決定すること、及び前記新しい幾何変換を適用することの動作を実行するステップを含む、請求項２１に記載の方法。
【請求項２７】
専用デジタル論理回路において、変換、測定、更新、前記新しい幾何変換を決定すること、及び前記新しい幾何変換を適用することの動作を行うステップを含む、請求項２１に記載の方法。
【請求項２８】
命令が格納された非一過性のコンピュータ可読媒体であって、前記命令がプロセッサによって実行されたとき、デジタルデータを抽出するために画像内の参照信号の幾何変換を決定する方法を実施し、前記方法が、
参照信号の複数の参照信号成分について、
候補幾何変換に従って、参照信号成分の座標を変換するステップ、
前記変換された参照信号成分と前記画像との間の相関を測定するステップであって、前記相関が、前記変換された参照信号成分の前記座標のあたりの隣接座標における前記画像の周波数領域変換の複素成分の組み合わせを含み、前記複素成分の組み合わせが、前記隣接座標における参照信号成分の位相関係に従って前記複素成分を組み合わせる、当該ステップ、及び
前記参照信号成分の前記座標を、前記変換された参照信号成分の前記座標のあたりの近傍内の位置へ更新するステップと、
前記参照信号成分を前記更新された座標に変換する新しい幾何変換を決定するステップと、
前記新しい幾何変換を適用して、符号化されたデジタルデータを前記画像から抽出するステップと、
を含む、非一過性のコンピュータ可読媒体。
【請求項２９】
デジタルデータ抽出のための装置であって、
画像センサと、
前記画像センサにより取り込まれた画像、及びソフトウェア命令を格納するためのメモリと、
前記メモリに結合された１つ又は複数のプロセッサと、
を備え、
前記１つ又は複数のプロセッサが、前記ソフトウェア命令を実行して、
幾何変換候補を参照信号成分に適用して、変換された座標を取得することと、
前記変換された参照信号成分についての相関メトリックを計算することであって、前記相関メトリックが、参照信号成分の位相関係に従って、前記変換された座標の隣接座標における前記画像の周波数成分を組み合わせる、当該計算することと、
前記変換された参照信号成分の前記座標あたりの近傍内に前記参照信号成分の新しい座標を決定することと、
前記参照信号成分を前記新しい座標に適合させる新しい幾何変換を計算することと、
前記新しい幾何変換を用いて決定された位置で前記画像から符号化されたデジタルデータを抽出することと、
を行うように構成されている、装置。
【発明の詳細な説明】
【関連出願データ】
【０００１】
米国において本出願は、２０１５年７月１６日に出願された米国特許仮出願第６２／１９３，４７９号及び２０１５年７月３１日に出願された米国特許仮出願第６２／１９９，７１０号の利益を主張する。本出願はまた、２０１０年９月３日に出願された米国特許仮出願第６１／３８０，１８０の利益を主張する２０１１年９月２日に出願された米国特許出願第１３／２２４，６０８号に関連する。
【技術分野】
【０００２】
本発明は、信号処理装置に関し、詳細には、特に信号検出、識別、信号マッチング及び認識の用途で使用される、信号間の変換を決定するための信号処理に関する。
【背景技術】
【０００３】
被疑信号と参照信号との間のアフィン変換を正確及び効率的に計算する必要がある様々な信号処理用途がある。これは特に画像用の信号検出及び認識の用途の場合であり、また他のタイプの信号にも適用される。信号検出及び信号認識の場合では、コンピューティングデバイスの目的は、特定の参照信号が被疑信号内に存在するかどうかを決定することである。この目的は、参照信号が存在するが座標空間の変換によって歪んでいる場合はより困難になる。画像処理において、そのような変換は、画像編集（拡大、縮小、回転、デジタルサンプリング（再サンプリング）、フォーマット変換など）を介した参照信号の操作によって生じる。参照画像又はそれらが表す物体は、それらの元の状態に対する異なる参照点からカメラによって取り込まれたとき、その結果は、変換されたままの状態の参照信号を含む被疑画像である。参照信号のアフィン変換を決定し補償する手段がない限り、正確に参照信号を検出し又は認識し或いは被疑画像内のその対応物と照合することがより難しくなる。
【０００４】
この信号処理の問題は、様々な分野で重大なものである。いくつかの例として、マシンビジョン、医療画像解析、物体及び信号認識、生体信号解析及びマッチング（例えば、顔、声、虹彩／網膜、指紋照合）、監視の用途などがある。これらの用途では、目的は、１つの特定の参照信号に対して入力被疑信号を検出若しくは照合し、又は多くの異なる参照信号に対して照合することでありうる（問い合わせが、信号の参照データベースに対して照合される被疑信号（プローブ又はテンプレート）を含む、データベース検索などにおいて）。様々なタイプの画像及び音声が、信号認識及び検出技術を用いて識別されうる。これらは、信号に固有の信号属性に基づく認識、並びに、バーコード及びデジタル透かしのような機械可読の場合と同様に、補助データ運搬能力を用意する別の信号に個別に埋め込まれる信号に基づく認識を含む。
【０００５】
近年、コンピューティングデバイスは、画像及びオーディオセンサを含む様々な種類のセンサを装備することが多くなってきている。これらのデバイスは、それらの周囲の世界と相互作用する能力を得るために、センサを通してそれらが取り込む信号を認識し識別できる必要がある。
【０００６】
電子技術の進歩により、これらの先端的なセンサ機能は、マシンビジョン機器、監視及び探査機器、及び医療画像ツールのような特殊用途のデバイスを超えて、パーソナルコンピュータ及び携帯電話ハンドセットのような家庭用電子デバイスにまで拡張されている。これらのデバイスに取り込まれた信号は、しばしば変換によって歪められる。これらの変換が、アフィン変換又は少なくとも局所的にアフィン変換によって近似できる場合、被疑信号を参照信号と最も合致するアフィン変換（信号の一部分における局所アフィン変換を含む）を決定することが可能でありうる。
【０００７】
参照信号をその被疑信号における対応物とアライメントするアフィン変換は、ｙ＝Ａｘ＋ｂとして表すことができ、ここで、ｘ及びｙは、参照信号の参照バージョン及び変換バージョンを表すベクトルであり、Ａは線形変換行列であり、ｂは平行移動（ｔｒａｎｓｌａｔｉｏｎ）である。アフィン変換は一般に、線形変換（回転、スケール変更、せん断変形）及び平行移動（すなわちシフト）を含む。２次元信号に対する線形変換行列は、回転、スケール、せん断変形を定義するパラメータの２掛ける２の行列（２×２）である。平行移動成分は、垂直及び水平のシフトを定義するパラメータの２掛ける１（２×１）の行列である。平行移動は、後で詳細に説明するような位相シフトに関係する。このように、２つの信号をアライメントするプロセスは、線形変換と平行移動との両方の近似を含むことができる。線形変換は、フーリエ変換及び逆フーリエ変換をしばしば採用する信号相関演算を決定することによって近似されることがある。平行移動成分は、フーリエ表現において位相シフトを決定する（例えば、信号相関を使用して）ことによって近似される。
【０００８】
デジタル画像取り込みで遭遇する変換のタイプの例は、透視変換である。このタイプの変換は、ユーザがモバイルデバイスのカメラで対象物の画像を取り込むとき、カメラの平面が対象物の表面上の画像に対してしばしば傾けられるため、一般的である。例えば、ボックス又は文書上の画像は、ボックス又は文書の表面に対して傾けられたカメラによって取り込まれるときに、透視歪みを受ける。もちろん、対象物表面は、湾曲すること（例えば、ボトル、缶、瓶など）があるので常に平坦ではなく、また柔軟又は変形可能である場合もあり、その場合は表面の一部が様々な方向に曲がる。そうであっても、対象物表面は、互いに縫合されたほぼ平坦な表面のいくつかのパッチとして近似されてもよい。パッチ上の画像の幾何変形は、アフィン変換又は透視変換であってもよい。
【０００９】
数学的に示すために、画像の元の座標（ｘ，ｙ）の変換された座標（ｕ，ｖ，ｚ）への透視変換は、次の式によって表される：
【数１】
0006741306.tif 000002
【００１０】
歪められた画像の変換された座標（ｕ’，ｖ’）は、以下の式によって表現されることがある：
【数２】
0006741306.tif 000003
【００１１】
透視変換は、８個の未知のパラメータを有する。線形変換パラメータは、上記式におけるＡ、Ｂ、Ｄ、及びＥである。平行移動パラメータは、Ｃ及びＦであり、台形パラメータは、Ｇ及びＨである。後者の台形パラメータＧ及びＨは、透視パラメータとも呼ばれる。
【００１２】
図１６は、透視変換の効果を示す図である。透視変換の歪み効果を緩和するタスクが、歪められた画像をブロックに細分化することによって管理されうる。歪みベクトルが小さく、対象となる画像ブロックも小さい場合、透視変換はアフィン変換パラメータを用いて近似されることがある。図１６の左側の実線（４００ａ）で囲まれた領域は、画像にカバーされる長方形のオブジェクトである。オブジェクト（４００ａ）は長方形であるが、カメラを用いてわずかな傾きで画像取り込みされており、透視変換によって歪められ、右側の歪められた画像４００ｂとなっている。破線は、画像のブロックへの細分化の結果を示す。ブロック４０２では、透視歪みは、差分スケール（ｄｉｆｆｅｒｅｎｔｉａｌ  ｓｃａｌｅ）によって密接に近似される。ブロック４０４では、透視歪みは、せん断によって密接に近似される。透視歪みは、画像ブロックサイズが小さくなるにつれて、アフィン変換によってより密接に近似される。しかしながら、ブロックサイズが小さくなるにつれて、歪んでいない画像に対するアフィン変換を突き止めるのに利用可能な画像情報が少なくなるというトレードオフがある。デジタル画像サンプリング、及び画像取り込みプロセスにおける他のノイズ源が、画像の更なる変更をもたらし、透視変換の影響を回復及び緩和する画像信号処理の設計を複雑にする。
【００１３】
信号変換が汎用処理ユニット又は特殊用途デジタル論理回路のデジタルコンピューティング環境において計算される場合、いくつかの問題が生じる。これらの問題の一部は、個別のデジタル論理で信号を表すことによって生じる誤差を含む。アナログ信号がセンサを通してサンプリングされるときだけでなく、これらの信号が異なる座標空間に変換される（例えば、フーリエ変換及び逆フーリエ変換）ときに再サンプリングされるときにも、量子化誤差がもたらされる。信号及び関連する変換パラメータの離散値を格納するために使用される回路の精度又は精度の限界に、更なる誤差がもたらされる。別の問題は、信号認識及び信号アライメントが通常、変換及び逆変換を伴い、変換及び逆変換は、誤差をもたらすことに加え、離散信号内の各値が変換され、再サンプリングされ、又は隣接サンプル値より近似されるのに伴って、メモリに対する読取り／書き込み動作の必要が増大するため、ハードウェアに実装するために計算コストが高く、追加のメモリを要し、メモリ帯域幅の制約がもたらすことである。
【００１４】
これらの問題に鑑みて、正確な信号の間の変換を決定し、しかもデジタルコンピューティング環境で効率的に実装される方法が必要である。これは、線形変換の推定、及び平行移動又は位相シフトの決定をするための効率的な方法を含む。
【発明の概要】
【００１５】
本明細書は、様々な技法を使用して離散参照信号と画像信号との間の変換を計算する方法を詳細に示す。１つの方法は、離散参照信号を表す特徴位置のセットを用意し、初期変換パラメータのシードセット（ｓｅｅｄ  ｓｅｔ）を用意する。特徴位置及び変換パラメータは、電子メモリにおけるデジタル電子信号として表される。シードセットを使用して、この方法は、離散参照信号の特徴位置と被疑信号における対応する特徴位置とをアライメントするために線形変換が使用されるときに誤差を最小限にする幾何変換候補を見つけ出す。これは、幾何変換候補に対応する相関の尺度を計算することを含む。この方法は、シードのそれぞれについて幾何変換候補を評価して、幾何変換候補の絞り込まれた推定値を表す候補のサブセットを識別する。
【００１６】
本明細書はまた、これらの方法の様々な実装形態を説明する。例えば、一実装形態は、特定用途向け集積回路のデジタル論理コンポーネントに実装された電子デバイスである。このデバイスは、被疑信号表現を格納するためのメモリを備える。このデバイスは、幾何変換候補のシードセットを受け取り、線形変換候補が適用されるとき、参照信号と被疑信号表現との間の相関の尺度として各候補について相関メトリックを決定するための相関モジュールを備える。
【００１７】
このデバイスはまた、線形候補変換を適用することによって決定される位置における参照信号の特徴に対応する特徴の被疑信号表現内の特徴位置を決定するための座標更新モジュールを備える。このモジュールは、被疑信号における参照信号の成分の位置を決定し、参照信号と被疑信号との間の変換を決定するために幾何変換計算器に入力を提供する。
【００１８】
このデバイスは、参照信号特徴位置と座標更新モジュールによって決定された被疑信号における対応する特徴位置との間の最小二乗適合を提供する候補のそれぞれについての更新された線形変換を決定するための幾何変換計算器を備える。このデバイスは、相関メトリックを使用して、最も有望な線形変換候補を識別する。例えば、相関メトリックが、参照信号及び被疑信号をアライメントする変換能力の改善の兆候を示す限り、このデバイスは、変換を更新するプロセスを通しで反復する。
【００１９】
いくつかの実施形態は、変換された信号の位相の推定値を計算する方法を利用する。この位相推定方法は、離散参照信号を表す特徴位置のセットを用意し、被疑信号を受け取り、参照信号に変換を適用して、変換された位置のセットを用意する。この方法は、変換された位置のあたりの近傍の離散サンプル位置において被疑信号から位相をサンプリングする。この方法は、これらのサンプリングされた位相に対して、点広がり関数を適用して、変換された位置に対応する位置における被疑信号の位相の推定値を用意する。
【００２０】
位相推定は、例えば、被疑信号の位相を格納するためのメモリと、参照信号の座標を変換された座標位置に変換するための変換モジュールとを備える、デジタル論理回路において実装される。この回路はまた、変換された座標位置のあたりの位置においてメモリから被疑信号の選択された位相を読み取り、点広がり関数を選択された位相に適用して推定位相を提供するための点広がり関数モジュールを備える。
【００２１】
種々の実施形態が、相関メトリック及び座標更新プロセスにおいて位相推定技術を利用する。例えば、複素周波数成分が、点広がり関数を利用して非整数位置で推定される。これらの成分は、候補幾何変換についての相関のより正確な測定を可能にする。加えて、これらの成分は、座標更新プロセスに関する座標のより正確な位置を可能にする。
【００２２】
種々の実施形態は、幾何変換を適用して、参照信号が符号化された画像からデジタルデータを抽出する。幾何変換は、幾何歪みを補償し、埋め込み位置に埋め込まれたデジタルデータメッセージ要素の回復を可能にする。いくつかの実施形態では、参照信号に基づく信号信頼度メトリックを利用して、埋め込み位置から抽出されたメッセージ推定値を重み付けする。
【００２３】
種々の実施形態において、幾何変換の回復を速め、そのプロセスの計算の複雑さを低減する技法を利用する。１つのそのような技法は、参照信号のサブセットを利用して、更なる絞り込みのために幾何変換候補を識別する。単独又は組み合わせで利用されてもよい別の技法は、幾何変換候補をそれらの相関メトリックによって選別する。
【００２４】
いくつかの実施形態では、参照信号と被疑信号との間の平行移動オフセットの推定値を計算する方法を利用する。この方法は、被疑信号の位相推定値のセットに作用する。平行移動オフセットのアレイにおける各要素について、この方法は、平行移動オフセットにおける参照信号の期待される位相のセットを用意する。この方法は、平行移動オフセットにおける期待される位相及び対応する位相推定値のセットのそれぞれについて位相偏移メトリックを計算し、移動オフセットにおける位相偏移メトリックの合計を計算する。この手法は、位相オフセットのアレイに対応する位相偏移面を提供する。この方法は、平行移動オフセットのアレイに対する位相偏移メトリックにおけるピークを決定し（例えば、位相偏移面において）、ピークの位置が、平行移動オフセットの推定値を用意する。
【００２５】
この位相偏移方法は、例えば、位相偏移回路で実装される。位相偏移回路は、被疑信号の位相推定値及び参照信号の既知の位相のセットを格納するためのメモリを備える。位相偏移回路はまた、平行移動オフセットのアレイに対する参照信号から、参照信号の既知の位相及び対応する位相推定値のセットのそれぞれについて位相偏移メトリックを計算するため、及び平行移動オフセットにおける位相偏移メトリックの合計を計算するための偏移位相モジュールを備える。位相偏移回路は、平行移動オフセットのアレイに対する位相偏移メトリックにおけるピークを決定するためのピーク決定モジュールを備える。ピークの位置は、参照信号と被疑信号との間の平行移動オフセットの推定値を提供する。
【００２６】
上記に要約した方法は、命令（例えば、１つ又は複数のプログラマブルプロセッサで実行されるソフトウェア又はファームウェア）、回路、又は回路とプログラマブルプロセッサで実行される命令との組み合わせとして全体又は部分が実装される。
【００２７】
更なる特徴が、以下の詳細な説明及び添付の図面を参照することで明らかとなろう。
【図面の簡単な説明】
【００２８】
【図１】参照信号と被疑信号との間の変換を決定するためのプロセスの実装を示すブロック図である。
【図２】参照信号と被疑信号との間のアフィン変換を計算するハードウェアデバイスを示す図である。
【図３】参照信号と被疑信号内のその対応物とをアライメントする最良適合変換を計算する最小二乗法を示す流れ図である。
【図４】デジタル論理回路実装における処理の流れのブロック図である。
【図５】線形変換の近似が計算されている被疑信号の位相の推定値を計算する方法を示すブロック図である。
【図６】被疑信号の位相の推定値を計算する別の方法を示すブロック図である。
【図７】離散参照信号の変換された周波数成分がフーリエ領域内の整数座標に位置せず、したがって、隣接周波数位置から位相を推定する位相推定方法を要することを示す図である。
【図８】位相推定方法を導出するプロセス、及び導出をサポートする関連する計算を示す図である。
【図９】線形変換及び参照信号を所与として位相を計算する位相推定方法を示す流れ図である。
【図１０】位相推定のデジタル論理回路実装を示すブロック図である。
【図１１】位相偏移方法の概要を示す流れ図である。
【図１２】線形変換を推定するためのデジタル論理回路のブロック図である。
【図１３】位相推定及び位相偏移のためのデジタル論理回路のブロック図である。
【図１４】偏移メトリックに基づく位相偏移方程式を示す図である。
【図１５】直接最小二乗法の実装を示す図である。
【図１６】画像に対する透視変換の効果を示す図である。
【図１７】スケール及び回転角パラメータの座標空間内で選択された、回転及びスケールパラメータ候補の例を示す図である。
【図１８】Ｎ次元変換パラメータ空間の追加次元で変換候補を拡張する方法を示す図である。
【図１９】各候補のまわりのパラメータ空間における方向で変換候補を拡張する別の例を示す図である。
【図２０】実際の歪められた画像ブロック（破線）に重ねられた画像ブロック（実線）の近似された幾何変換を示す図である。
【図２１】画像から抽出されたメッセージ推定値に重み付けするために使用される信号信頼度メトリックを決定するための処理の実装のブロック図である。
【図２２】デジタル透かし信号の埋め込み位置のタイル状パターンに重ねられた画像ブロックの例を示す図である。
【図２３】信号信頼度メトリックによる重み付けを利用するメッセージ信号抽出の実装を示す図である。
【図２４】画像ブロックをフィルタリングする例を強調した、図２２の埋め込み位置に重ねられた画像ブロックの拡大図である。
【図２５】画像フィルタリング及びメッセージ推定値の抽出に使用するための画像ブロックのサンプリングの例を示す図である。
【図２６】非整数座標に配置された純粋な正弦曲線参照信号成分の整数座標における位相を示す図である。
【発明を実施するための形態】
【００２９】
図１は、参照信号と被疑信号との間の変換を決定するためのプロセスの実装を示すブロック図である。このプロセスを変換回復プロセスと呼ぶことにする。その理由は、このプロセスが、デバイス内に取り込まれた被疑信号から参照信号の変換を回復するためである。特に、この方法は、被疑信号を参照信号とアライメントするために必要な変換を海部フィードバックするために実装されている。このプロセスは、入力として、既知の参照信号及び取り込まれた被疑信号の離散表現１００を入力として取り込み、変換の推定値を決定し、変換の推定値は、参照信号に適用されたときに被疑信号を近似することになる。変換回復プロセスは、段階１０２〜１０６に細分化され、第１の段階は、変換の推定値（例えば、線形変換パラメータの４次元ベクトル（又は２掛ける２の線形変換行列）によって記述された線形変換）を提供し、後続の段階は、まず、段階１０２の推定された変換によって変換されるような参照信号の位相を推定し、次いで、段階１０６で位相及び平行移動を見つけ出す（よって平行移動の２つの追加のパラメータ、例えば、水平及び垂直シフトパラメータ、ｘ及びｙを提供する）ことによって、推定を絞り込む。位相及び平行移動は、関連したパラメータであるので、必ずしも別個ではなく、それらのパラメータは、被疑信号における参照信号の垂直及び水平シフトを提供するために使用されることがある。本発明の特定の実装形態では、段階１０２において、それぞれが２掛ける２の線形変換行列に対応する候補線形変換を提供する。次の２つの段階では、２次元（２Ｄ）平行移動（垂直及び水平方向の）を提供し、この平行移動は、２掛ける２の線形変換行列と組み合わされたとき、アフィン変換候補を提供する。この文脈では、位相シフト及び平行移動は、異なるよう領域で表される関連する量である。すなわち、信号成分の位相角の変化としての位相シフトは、フーリエ変換領域などのフーリエ領域で表され、平行移動は、空間領域（例えば、画像の空間領域）又は時間領域（オーディオのような経時変化する信号の時間領域）で表される。段階１０２〜１０６はそれぞれ、他の段階から独立した新規の要素を含み、これらの新規な要素について、より詳細に説明する。これらの段階は、信号間のアフィン変換を計算し、後で更に説明するように組み合わせて使用されるとき追加的な利点を実現するように、システムに実装される。これらの方法及び関連するハードウェア実装は、様々な信号検出、物体認識、及びマッチング用途に適用される。デジタル透かし検出の文脈で方法の例を説明するが、これらの方法は、この文脈に限定されない。
【００３０】
これらの方法はまた、様々な信号タイプに適用される。それらは、センサから取り込まれた２次元コンテンツ信号（例えば、カメラにより取り込まれた画像又はビデオフレーム）に対して動作するように設計される。これらの方法はまた、１次元及び２以上の次元の信号に適用される。ある実装形態は、特に、画像コンテンツにおける参照信号の幾何変換を決定するように構成される。参照信号は、ホスト画像に埋め込まれた２次元画像透かし信号の形態をとる。参照信号は、異なる用途に対する様々な信号タイプを包含するように一般化されうる。このように、ソフトウェア及びハードウェア実装は、物体認識、パターン認識、マッチング、コンテンツフィンガープリント、マシンビジョン、及び信号間の変換が計算される他の用途など、様々な信号処理用途に適用される。本発明の方法は、具体的には、センサ、特にデジタルスキャナ、カメラ、携帯電話ハンドセットなどで使用されるタイプのＣＣＤ及びＣＭＯＳアレイのような画像センサに取り込まれた信号を処理するように構成される。
【００３１】
方法を具体的に説明するための例として、透かし信号検出ハードウェアの概説から始める。次いで、個々の段階の実装を説明する。図２は、参照信号と被疑信号との間のアフィン変換を計算するハードウェアデバイスを示す図である。この特定の設計は、埋め込まれた２次元透かし信号のアフィン変換を回復するように構成される。この設計は、取り込まれデジタル化された電子画像のいくつかの部分をメモリ（ＲＡＭ）１２０にバッファする（被疑画像信号）。フィルタ及びフーリエ変換処理モジュール１２２が、被疑画像をフィルタリングし、２次元フーリエ変換を計算する。線形変換推定モジュール１２４は、被疑信号の離散周波数表現を取得し、参照信号とフィルタリングされた被疑信号との間の線形変換の推定を計算する。アフィン変換回復モジュール１２６は、線形変換推定、並びに参照及び被疑信号表現を使用して、参照及び被疑信号との間の位相／平行移動を計算し、それにより、参照信号を被疑信号に変換するアフィン変換が得られる。
【００３２】
図２の下部は、モジュール１２２〜１２６内のサブモジュールを分解したものを示す。これらのサブモジュールの実装は、後で更に説明する。
【００３３】
図１の変換推定は、いくつかの代替方法で実装されてもよい。１つの手法は、参照信号と被疑信号との間のマッチドフィルタ相関（ｍａｔｃｈｅｄ  ｆｉｌｔｅｒ  ｃｏｒｒｅｌａｔｉｏｎ）を行うことである。被疑信号に対する参照信号の回転及びスケールを決定する１つのそのような方法は、フーリエ−メリン相関である。被疑信号と参照信号の両方をフーリエ−メリン座標空間（対数極座標空間）に変換することによって、２つの信号の間の回転及びスケール変換が平行移動シフトに変換されて、マッチドフィルタ相関の適用により、信号間の回転及びスケールの推定に対応する相関ピークの位置を見つけ出すことが可能になる。別の手法は、最小二乗法、特に直接最小二乗法を実行することである。以下に、最小二乗法の実装について説明する。これらは、逐次パイプライン型ハードウェア論理段階で処理を実装できるハードウェアにおける実装、並びに、ハードウェア処理ユニット、いくつか（「プロセッサ」）の例を挙げるならば、グラフィック処理装置（ＧＰＵ）、デジタル信号プロセッサ（ＤＳＰ）、又はマルチコア中央処理装置（ＣＰＵ）などで並行に処理を実行できるソフトウェアにおける実装に特に有用である。
【００３４】
最小二乗
最小二乗技法
最小二乗技法は、線形変換の初期推測を前提として最小二乗誤差（すなわち、最尤推定値）を生じる線形変換を推定する。演算は乗算及び加算からなり、ハードウェアに都合がよい。
【００３５】
図３は、最小二乗法を示す流れ図である。一実装形態では、入力として、参照位置のセットに対する座標（周波数又は空間領域のいずれかにおいて）、及び変換された位置のセットに対する座標の対応するセットを取り込む（やはり周波数又は空間領域のいずれかにおいて）。例示のために、参照位置が周波数領域における特徴、特に周波数領域におけるピークに対応する実装形態のための技法について説明する。
【００３６】
この最小二乗法は反復して実行され、反復ごとに３つのステップを含む。これら３つのステップは、図３において処理ブロック１３０、１３２、及び１３４で示される。
【００３７】
変換された周波数座標の計算１３０
この段階では、変換された周波数座標は、信号の初期変換及び元の（すなわち変換されていない）周波数座標を使用して計算される。
【００３８】
座標更新１３２
このステップでは、周波数振幅平面において変換された周波数の小さな近傍のあたりのピーク値を探索することによって、変換された周波数ごとにより適切な位置を求める。このステップの最後において、より適切なピーク位置がこの周波数について見つけられた場合は、各変換された周波数の座標が更新される。このプロセスで計算された最適周波数座標によって、単一線形変換では、もはや同時に求めることができない位置がもたらされる。
【００３９】
変換更新１３４
このステップでは、更新された線形変換が、最小二乗公式を使用して更新された座標から計算される。この更新された変換が、次の反復のための初期推測として使用される。最小二乗技法は、元の座標と変換された座標の間の二乗誤差を最小限にする変換を提供する。特に、最小二乗技法は、位置誤差の合計を最小二乗誤差の観点で最小限にする変換を提供する。誤差からの新しい変換の計算は、以下のように実装される。
【００４０】
相関強度と呼ばれる相関の尺度が反復ごとに計算される。相関強度メトリックは、反復の早期の終了を決定するために使用してもよいし、正規化を行うために使用してもよい。
【００４１】
理論的には、最小二乗技法は、線形変換パラメータの任意の初期推測から開始して参照信号と被疑信号との間の実際の線形変換を見つけ出すことができる。しかし、実用的見地からは（座標更新が過度に複雑になるのを防止するために）、線形変換パラメータの初期推測は、実際の線形変換からいくらか近くなければならない。したがって、この技法は初期推測に敏感である。
【００４２】
変換の初期推測は、回転とスケールの対のように単純でありうる。
【００４３】
この最小二乗法は、あらゆる任意の線形変換（すなわち、回転、スケール、せん断変形、及び差分スケール（ｄｉｆｆｅｒｅｎｔｉａｌ  ｓｃａｌｅ）を含む）を決定することができる。
【００４４】
直接最小二乗（ＤＬＳ）
ＤＬＳは、被疑信号と参照信号との間の線形変換を決定するための最小二乗技法の効率的な適用である。本発明の特定の実装形態は、画像に適用され、特に、被疑画像が、透かし入り画像であり、参照信号が、透かし入り画像に埋め込まれていると想定される透かし信号である。この場合、課題は、既知である元の参照信号と、被疑信号に埋め込まれていると想定されるその対応物との間の線形変換を決定することである。
【００４５】
最小二乗技法が、線形変換の初期推測のまばらなセット（ｓｐａｒｓｅ  ｓｅｔ）に適用される。
【００４６】
ＤＬＳは、フーリエ−メリン型相関よりも必要とする評価が少ないと共に、フーリエ−メリンよりも正確な変換を提供することができる。前述のように、フーリエ−メリン領域における参照信号と被疑信号との間の相関が、回転及びスケールの推定値を与える。これとは対照的に、最小二乗では、あらゆる任意の線形変換（例えば、線形変換パラメータの４次元ベクトル）を提供することができる。
【００４７】
ＤＬＳを用いて、２×２線形変換行列で包含される４次元空間を、まばらな２次元部分空間にわたる初期推測により極めて効率的に評価することができる。
【００４８】
各ＤＬＳ評価は、最小二乗技法を使用し、また２Ｄ部分空間上の他のＤＬＳ評価から独立している。したがって、ＤＬＳ評価は、ハードウェア内又はマルチコアプロセッサアーキテクチャ上で効率的に実行することができる。各評価は、推定された線形変換及び対応する相関強度値をもたらす。候補線形変換は、最大相関強度値に対応する候補線形変換として識別される。これらの候補線形変換のうち１つ又は複数が、アフィン変換を回復するために更に処理される。
【００４９】
ＤＬＳは、初期推測が２Ｄ部分空間に任意に広がることを可能にする。例えば、初期推測が回転／スケールの対を含む場合、回転軸及びスケール軸に沿った間隔は任意でありうる。これと比較して、フーリエ−メリン手法は、スケール軸での間隔が対数的であることを要する。任意の間隔の使用は、２つの利点、すなわち、向上された頑強性及び効率的な計算を備える。一般的な事例では、初期予測のセットは、初期推測が回転及びスケール値のまばらなサブセットにわたって均等に分布するように理想的に選択される。例えば、スケール軸での均等な間隔（スケールの均等な増大）が、効果的に計算されることができ、またノイズアーチファクトを低減する。適切な線形変換及び推定された変換の精度に収束するＤＬＳの能力は、初期推測の数、及び最小二乗の反復の数によって影響される。他の影響要素として、被疑信号における参照信号成分の探索の範囲（例えば、参照信号成分が探索される近傍のサイズ）がある。これらのパラメータの最適値は、ハードウェアコスト、計算速度、及び所望の頑強性の間のトレードオフとして決定される。より洗練された戦略は、適応された数の反復と併せて初期推測の非常にまばらなセットを使用することから構成される。連続した反復からもたらされる変換が収束を示す場合、より多くの反復が行われる。この戦略は、頑強性を犠牲にせずに計算効率性を実現する。
【００５０】
いくつかの用途では、被疑信号は、限定されたセットの変換を受けることがある。例えば、回転は、−３０度と＋３０度の間の範囲に制限されうる。このような状況では、ＤＬＳ評価は、更に制限された範囲のまばらな初期推測に対して行われる。
【００５１】
ノイズ及び歪みにより、ＤＬＳによって推定された線形変換にノイズが入る可能性がある。本発明の特定の事例では、変換は、弱い透かし信号を有する画像の単一画像ブロックから推定されたときにノイズが入る。推定された変換におけるノイズを低減するために、ＤＬＳ出力の特性を利用する。ＤＬＳは、初期推測ごとに、推定された線形変換及び相関強度値をもたらすことを想起されたい。適切に設計されたセットの初期推測では、複数の初期推測が同様の線形変換につながる。言い換えれば、出力線形変換がクラスタ化される。線形変換推定におけるノイズを低減するために、線形変換のクラスタが識別され、それらの要素が適切に平均化される。適切な平均化は、相関強度のある種の関数（例えば、非線形関数）によって各線形変換を重み付けすることによって行うことができる。
【００５２】
図４は、デジタル論理回路実装における処理の流れのブロック図である。フーリエ変換モジュール１４０は、メモリからの入力信号（例えば、画像センサによって取り込まれた画像データのブロック）にアクセスし、フーリエ変換及びフーリエ振幅（Ｆｏｕｒｉｅｒ  ｍａｇｎｉｔｕｄｅ）データを計算する。フーリエ振幅フィルタ１４２は、２Ｄフーリエ振幅データをフィルタリングする。１つのそのようなフィルタは、サンプル値をその８個の隣接のそれぞれと比較し、これらの比較に基づいてサンプル値を集約値に置き換える非線形フィルタである。一実装形態では、フィルタは、サンプル値のその８つの隣接の平均に対する比を使用する（フーリエ振幅領域において）。そして、フィルタの出力は、この比の関数（この場合、非線形関数）である。このフィルタは、（例えば、参照信号が被疑信号に埋め込まれたデジタル透かしにおいて）参照信号の特徴を抽出する際に特に役立つ。次いで、フィルタの出力が、直接最小二乗法に対する入力を形成する。別の実装形態では、フィルタ出力が、８個の隣接要素の平均に対する中央値の比の線形関数であり、これは、低い信号対ノイズ比の条件下の頑強性を改善する傾向がある。
【００５３】
座標の更新（図３のブロック１３２）
座標更新プロセスは、対象となる変換された位置（周波数）を囲む小さな近傍のあたりのピーク（又は角部若しくは特徴などの所望の特性）の局所探索を含む。
【００５４】
近傍は、典型的には、３×３若しくは２×２のサンプルの領域として定義され、又は問題領域及び用途に応じてかなり大きくなりうる。
【００５５】
ピーク又は所望の特徴が変換された位置と異なる位置にある場合、変換された位置の座標は、この位置に更新される。
【００５６】
最小二乗法は、被疑信号と参照信号との間の線形変換の推定値を提供する。完全なアフィン変換を回復するために、２つの信号間の位相シフト（又は平行移動）を計算する必要がある。１つの手法は、参照信号と被疑信号との両方の位相表現の間の位相相関を計算し、線形変換を考慮に入れる。本発明者らは、アフィン変換を回復するのに特に有利である処理モジュールを開発した。図１で先に説明したように、これらの処理モジュールは、位相推定及び位相偏移である。
【００５７】
位相推定
本発明の位相推定手法は、位相を計算し抽出するために追加の高速フーリエ変換（ＦＦＴ）が続く画像の逆変換を行うのではなく、変換された信号のＦＦＴから位相を計算するため、有利である。位相推定は、参照信号が被疑信号内で受けた線形変換を使用する。この線形変換を計算する１つの方法として直接最小二乗を示したが、マッチドフィルタ（例えば、線形変換を近似するためのフーリエメリン相関）を使用するなどして線形変換を計算する他の方法がある。
【００５８】
この利点を強調して、図５及び図６は、位相情報を計算する異なる方法を示すブロック図であり、一方は位相推定が無く、他方は位相推定を有する。双方の方法は、直接最小二乗法を使用して、信号間の線形変換を推定する。第１のＦＦＴは、直接最小二乗技法が基づいて作用する振幅情報を得るために行われる。図５では、位相を計算するための第２のＦＦＴが続く逆線形変換を行うが、図６の手法は、本発明の位相推定技法を使用する。位相推定が、逆線形変換と第２のＦＦＴの両方の追加的処理を回避する。
【００５９】
図７は、位相推定が扱う問題を示す図である。線形変換は参照信号座標に適用されると、離散座標にマッピングされないことが見込まれる。この位相推定方法は、非離散（すなわち実数値の）座標位置での位相を計算する効率的手法を提供する。
【００６０】
どのように位相推定が問題を扱うかを理解するために、位相推定方法の導出から始める。図８は、位相推定方法を導出するプロセス、及び導出をサポートする関連する計算を示す図である。図７、及び図８のブロック１８０に示されるように、導出の第１のステップは、フーリエ面において実位置ｖに配置された複素周波数からなる関数を仮定する。
【００６１】
図８のブロック１８２及び対応する数式は、位相推定に使用される点広がり関数（ＰＳＦ）の導出を示す。ＰＳＦは、整数複素数周波数の観点からフーリエ面において実位置に配置された複素周波数を分解することによって導出される。このＰＳＦは、複素数値である。
【００６２】
ブロック１８４に示されるように、導出の最後のステップでは、フーリエ面におけるＰＳＦの畳み込みを行う。図８のブロック１８２の内積は、フーリエ基底関数に対するものであり、これによりＰＳＦがもたらされる。次いで、ＰＳＦがブロック１８４で使用されて、フーリエ面において値の畳み込みがされる。
【００６３】
図９は、線形変換及び参照信号を所与として位相を計算する位相推定方法を示す流れ図である本発明の位相推定プロセスでは２つの主要な段階がある。第１の段階では、実装形態が、線形変換に従って、既知の参照信号座標（特に、既知の周波数座標での正弦曲線のセット）を変換する。第２の段階では、実装形態が、変換された座標、及び被疑信号の周波数領域においてこれらの座標を囲む位相情報を使用して、変換された周波数座標の位相推定値を得る。このプロセスへの入力は、離散被疑信号であり、離散被疑信号は、仮定された変換（例えば、事前に計算された線形変換）、及び参照信号の周波数仕様（これは、参照信号の正弦曲線の既知の周波数位置のセットである）と共に、２次元ＦＦＴから複素周波数平面の形態でメモリに格納されている。実複素周波数（ｒｅａｌ  ｃｏｍｐｌｅｘ  ｆｒｅｑｕｅｎｃｙ）ごとに、位相推定が、以下のステップを適用する。
ａ．提供された線形変換を使用して、周波数の変換された実位置（例えば、非整数）を計算する（ブロック１９０）。
ｂ．整数座標フーリエ基底の観点から実位置における複素周波数を表現する。これにより複素ＰＳＦがもたらされる（ブロック１９２）。
ｃ．被疑画像ブロックのＦＴＴから、所望の実周波数を囲む整数周波数の位相を得る（ブロック１９４）。ＰＳＦは、Δ＝０でピークに達し、したがって、非整数のピークが（期待されるように）小さな近傍に現れる。特に、関数（ｓｉｎ（πΔ）／Ｎ  ｓｉｎ（πΔ／Ｎ））は、（極限に）０でピークを有する。
ｄ．整数周波数の複素値とＰＳＦの対応する複素値との積の合計を計算する（ブロック１９６）。これは、実複素周波数における推定された位相を与える。
【００６４】
ＰＳＦ値を効率性のために事前計算してテーブルに格納することができる。更に、効率を高めるために位相を（少数の位相角に）量子化することもできる。位相推定の第１の段階の実装形態により、参照信号の各周波数位置を離散周波数サンプル間の適切な「分数（ｆｒａｃｔｉｏｎａｌ）」位置に移動させる変換を行う。変換された参照信号の位相の特性は、信号周波数とは独立である。分数周波数位置ごとに、ＰＳＦテーブルが、最も近い離散周波数位置に対する事前計算された位相情報を含む。
【００６５】
計算を単純化するために、実装形態は、各整数周波数間で分数周波数位置の限られた分解能を使用する。実装形態は、この分数周波数位置の数の減少を利用して、更にＰＳＦテーブルのサイズを減少させる。ＰＳＦテーブルは、各許容された分数周波数位置のみについて事前計算された位相情報を含む。
【００６６】
そして、このＰＳＦ位相情報は、すべての将来の推定のために再使用される（プロセスの第２段階において）。１つの特定の実装形態では、位相情報が事前計算され、小さな離散テーブルに値が格納される。テーブルは、水平周波数方向及び垂直周波数方向について同じであり、したがって、実装形態は、２回アクセスし、値を組み合わせて２Ｄ周波数位置について期待される位相を作成する。
【００６７】
本発明の位相推定動作は、効率的でありハードウェアに都合がよい。逆変換及び追加のＦＦＴを取り除くのに加えて、この手法は、図５の方法で示すような被疑信号データ（例えば、入力被疑画像）へのアクセスを必要としない。代わりに、この手法は、図６に示すように既に計算された被疑信号の周波数データを使用する。したがって、位相推定がハードウェアでのパイプラインアーキテクチャに適している。
【００６８】
一般に、位相推定技法は、最初に空間領域データを用いることなく、複素周波数領域における回転又は他の変換を行うために使用することができる。
【００６９】
図１０は、位相推定のデジタル論理回路実装を示すブロック図である。図１０に示される位相推定実装は、モジュール２００においてデータで被疑信号ブロックに関する位相情報のストリームを受け取る。制御モジュール２０２の制御下で、それは位相情報（被疑信号ブロックの２次元ＦＦＴからの位相半平面）をＲＡＭメモリ２０４に格納する。また、線形変換候補がモジュール２００のデータを通して受け取られ、モジュール２０６、２０８、及び２１２に直接格納される（或いはＲＡＭ２０４に格納されてもよい）。
【００７０】
線形変換候補行列モジュール２０６は、行列における線形変換候補を形成し、それらを行列反転モジュール２０８及びデータ出力モジュール２１０に供給する。行列反転モジュール２０８は、線形変換行列を反転する。この実装形態では、線形変換は画像の空間変換のためである。被疑画像周波数領域において参照信号座標をマッピングするために、線形変換の逆転置を行う。次いで、変換座標モジュール２１２が、メモリ（読取り専用メモリ（ＲＯＭ）２１４）から参照信号成分の位置を指定する参照信号座標を取り、その位置を被疑信号ブロックの座標空間の座標に変換する。制御モジュール２１６は、参照信号成分の位置のそれぞれを配列して、周波数領域における座標を提供する。各参照信号座標について、制御モジュール２１８は、２掛ける２の行列の点広がり関数（ＰＳＦ）点を配列する。制御モジュール２１８は、そのようにして、参照信号成分の変換された座標に基づいて動作する座標上限／下限関数モジュール２２０を制御し、それがＰＳＦテーブル２２２におけるその座標に対するＰＳＦを選択する。次いで、座標上限／下限関数モジュール２２０が、位相情報ＲＡＭ２０４内の隣接周波数位置を選択し、次いで、それが隣接位置での位相情報を積及び和論理演算子２２４に出力する。積及び和論理演算子２２４は、点広がり関数をテーブル２２２から位相情報に適用して、推定された位相を計算する。次いで、データ出力モジュール２１０が、対応する線形変換座標と共に、参照信号の参照座標ごとに推定された位相を出力する。この位相推定実装形態は、線形変換座標のすべてを繰り返して、ＬＴ候補ごとに各参照信号成分について推定された位相のセットを提供する。
【００７１】
位相偏移
図１を再度参照すると、位相推定に続くプロセスが、変換された参照信号の位相のこの推定値を使用して、参照信号と被疑信号との間の平行移動を決定している。この段階で平行移動を計算する代替的手法がある。本発明の手法は、変換された参照信号と被疑信号との位相表現の間の位相相関を行うことである（これは逆ＦＦＴ演算を必要とする）。次に、位相偏移と呼ばれる代替的手法について説明する。
【００７２】
２Ｄ位相偏移
位相偏移は、一般に２つの画像又は信号の間の平行移動を推定する代替的手法である。位相変換手法と比較して、位相偏移は、逆ＦＴＴ動作を必要としない。
【００７３】
図１１は、位相偏移方法の概要を示す流れ図である。まず、位相偏移方法は、ステップ２３０で、参照信号と被疑信号との間の第１のレベルの細目（例えば、整数オフセット）で候補平行移動値のセット（平行移動オフセットと呼ばれる）を得る。図１１のステップ２３２では、位相偏移方法は、候補平行移動の第１のセットのあたりでより高いレベルの細目（例えば、分数オフセット）を使用して参照信号と被疑信号との間のより良い適合を提供する平行移動値を決定することによって、それらの候補を絞り込む。
【００７４】
指定された平行移動オフセットに対する位相偏移は、対象となるすべての参照信号成分での測定された位相と期待される位相との間の偏移の合計である。参照信号が、それぞれ特定の位相を有する正弦曲線のセットを備える場合では、期待される参照信号位相は、既知の平行移動オフセットでの正弦曲線の位相である。これらの期待される位相は、いくつかの平行移動オフセットのそれぞれについて提供され、それらは、位相角又は平行移動値（例えば、特定の画像解像度でのピクセルオフセット）の観点から指定することができる。言い換えれば、可能な平行移動オフセットごとに、参照信号についての期待される位相のセットがある。更に、他方の入力が、被疑信号から前もって計算された測定された位相である。期待される位相と測定された位相との間の偏移は、平行移動オフセットごとに計算される。各周波数における偏移は、測定された位相と期待される位相との間のユークリッド距離のような距離測度を使用して計算してもよい。すべての可能な平行移動オフセットについて計算された位相偏移が、２Ｄ位相偏移面を構成する。２Ｄ位相偏移面における最小値の位置が、平行移動オフセットの位置を示す。
【００７５】
２Ｄ位相偏移方法は、加算のみ（乗算なし）を用いて、２Ｄ  ＦＦＴの計算コストのごく一部のコストで実装することができる。また、オフセットごと及び周波数ごとの位相偏移演算を独立して計算することができ、並列実装がもたらされる。これは、位相相関のような他の代替方法に対する利点である。
【００７６】
位相差及び位相偏移は、複素数値として計算することも、角度の観点から直接計算することも可能である。角度を用いた操作により、計算の効率性が改善される。
【００７７】
ユークリッド距離以外の距離測度を使用することもできる。例えば、Ｌ１ノルム又は非線形尺度が、関連する信号及びノイズの特性に応じて改善を実現することができる。
【００７８】
特に、偏移の合計は、測定された位相角度と期待される位相角度との間の絶対差の合計として計算することができ、各差は、−πと＋πの間に含まれる（２＊πを法とする）。この計算は、ハードウェアで実装するのに効率的である。
【００７９】
サブサンプル平行移動推定
位相偏移が、任意の実数値の平行移動オフセットについて計算されうる。これは、位相相関手法を用いる整数値の平行移動推定ではなく、サブサンプル平行移動推定を行う。
【００８０】
サブサンプル平行移動で位相偏移メトリックを計算する能力を、平行移動絞り込み技法を実装するために使用することができ、この技法では、まず、整数平行移動が、適切な平行移動オフセットを決定するために評価され、適切な平行移動オフセットの周辺で、サブサンプル（すなわち、画像コンテンツに対する部分的サブピクセル）平行移動オフセットを評価することによって更なる絞り込みが行われる。
【００８１】
１次元（１Ｄ）位相偏移
基本的位相偏移の定式は、周波数におけるパターンを活用するために修正してもよい。１次元（水平又は垂直）の座標値の線形結合がゼロである周波数のセットにより、直交次元での１Ｄ位相偏移の定式がもたらされる。概念的には、これにより、２Ｄ空間の２Ｄ正弦曲線のセットの乗算である直交次元での仮想１Ｄ信号がもたらされる。仮想１Ｄ信号の周波数は、直交次元の周波数の合計によって与えられる。次いで、平行移動を、２Ｄ位相偏移のコストのごく一部のコストで、１Ｄ位相偏移の定式を用いて、各次元で独立して推定することができる。加えて、最小位相偏移メトリックの探索は、１Ｄに沿っており（すなわち、１次元データセット上であり）、計算コスト全体を更に減少させる。
【００８２】
いくつかの場合、線形結合が、元の信号のサポート長（例えば、１２８ポイント）の外側の仮想１Ｄ信号がもたらされる。これらの仮想１Ｄ信号は、ナイキストより高い周波数を有する。この場合、１Ｄ位相偏移方法は、エイリアシングを回避するために、より大きい人工的なサポート長によって（例えば、より高いサンプリングレートを保証するために２５６ポイントを使用して）指定してもよい。エイリアシングを回避することにより、ノイズ中の平行移動推定の信頼性が向上する。
【００８３】
１Ｄ位相偏移は、直交次元のすべての結果として生じる仮想周波数が偶数値であるとき、平行移動の曖昧性を生じる。例えば、２Ｄ空間内の長さ１２８×１２８の象限対称周波数の対（例えば、［−４５，９］と［４５，９］、並びに［−４４，６］と［４４，６］など）が乗算されると、結果として生じる１Ｄ位相偏移は、長さ６４の周期性を有する。同じ値の２つの周波数を組み合わせることで生じる周波数倍増により、偶数値の１Ｄ信号周波数（例えば、１８及び１２）がもたらされ、それにより曖昧性が導入される。エイリアシングの当然の帰結として、２つの周波数Ａ及びＢを混合することにより、新しい周波数Ａ＋Ｂ及びＡ−Ｂを作り出される。周期性によって生じる曖昧性は、特定の平行移動の更なる評価のために２Ｄ位相偏移を使用して解消されうる。或いは、曖昧性は、仮想周波数の相当数（約半分）が奇数値であることを保証することによって解消することができる。
【００８４】
１Ｄ位相偏移と２Ｄ位相偏移の組み合わせを用いて、１Ｄ位相偏移の少ない計算負荷及び２Ｄ位相偏移の頑強性を活用することができる。
【００８５】
図１２及び図１３は、ハードウェア実装をより詳細に示すブロック図である。図１２は、線形変換の推定（例えば、図１のブロック１０２、及び図２のブロック１２２〜１２４）のためのデジタル論理回路のブロック図である。図１３は、位相推定及び位相偏移のためのデジタル論理回路のブロック図である。
【００８６】
図１２に示されるように、実装形態への入力は、被疑画像からの画像データのパケットである。実装形態は、参照信号であるデジタル透かしの初期座標空間に対する被疑画像である入力画像に埋め込まれたデジタル透かし信号のアフィン変換を計算する。この特定の例では、参照信号は、透かし信号に対応する周波数ピークのセット（すなわち、互いに対し既知の擬似ランダム位相を有する正弦曲線のセット）である。プロセスのこの時点で、被疑画像は、サンプリング（走査、印刷など）によって引き起こされる様々な形態の歪み並びに幾何歪みにさらされていることがある（例えば、画像編集、及び／又はスキャナ又はカメラからの変換された状態の画像の取り込みの結果として）。この歪みの結果として、既知の参照信号と被疑画像に埋め込まれたその対応物との間の変換を最も近似するアフィン変換が知られていない。目的は、埋め込み時の参照信号と被疑信号内の埋め込まれた参照信号との間の変換を最も近似するアフィン変換を計算することである。
【００８７】
回路実装を説明する前に、参照信号及び被疑信号の属性の背景を説明することが有益である。その理由は、それらの信号が、ハードウェアの設計検討に影響するからである。デジタル透かしは、信号の隣接ブロックの範囲内で繰り返されている（例えば、タイル様式で）。デジタルハードウェア回路は、入力パケットのストリームに基づいて動作する。入力パケットは、透かしが当初埋め込まれたブロックの元のサイズにおおむね対応する被疑画像のブロックの重複ブロックを含む。各ブロックは、１２８掛ける１２８のピクセルのアレイである。メモリ及びＦＦＴフィルタなどのサイズは、これらの信号の属性に基づいて適合され、また、用途及び用途に応じた信号仕様によって異なることが可能である。
【００８８】
前置フィルタ３００は、先に説明した方法を用いて画像ブロック内のピクセル値をフィルタリングする。すなわち、各サンプルは、その８つの隣接サンプルと比較され、これらの比較の関数である値に置き換えられて、埋め込まれた参照信号を被疑画像データから隔離しようとする非線形フィルタリングの形態を実現する。
【００８９】
ウィンドウ動作３０２は、２Ｄ  ＦＦＴのためにフィルタリングされた画像データを準備する。結果として得られたフィルタリングされた画像データブロックは、ＦＴＴ２Ｄ（３０４）に受け取られてＲＡＭに格納される。この場合、ＲＡＭ（３０６）は、図１２に示される他のハードウェアコンポーネントと共にＡＣＩＣ内に実装される。ＦＴＴ２Ｄは、空間入力データのブロックを処理して、複素周波数データを生成する。複素周波数データの実部及び虚部は、単一のパイプ出力ストリーム内へ出力でインタリーブされる。
【００９０】
ＣＯＲＤＩＣ３０８は、インタリーブされた実（Ｒｅ）及び虚（Ｉｍ）ストリームをインタリーブされた振幅及び位相ストリームに変換する。当分野で知られているように、ＣＯＲＤＩＣは、三角関数の効率的なデジタル信号処理実装のための方法である。フーリエ振幅フィルタ３１０は、データのフーリエ振幅部分のみをフィルタリングする。フィルタは、サンプル値のその８個の隣接の平均に対する比を使用する（フーリエ振幅領域において）。そして、フィルタの出力は、この比の関数（この場合、非線形関数）である。位相は、変更されずに通過する。
【００９１】
直接最小二乗（ＤＬＳ）モジュール３１２は、フィルタリングされたフーリエ振幅及び位相データのインタリーブされたストリームを受け取る。これらのデータストリームのそれぞれは、ＲＡＭブロック３１４及び３１６として示されるＲＡＭに格納される。
【００９２】
ＤＬＳは、最大相関強度に関して各潜在的線形変換候補を計算し絞り込む。ＤＬＳモジュール３１２の出力は、格納された位相ブロックに先行される線形変換（ＬＴ）候補のストリームである。位相推定に使用される位相データは、位相を候補線形変換ごとに推定できるように、サンプリングされる準備ができている形態で格納される。
【００９３】
ブロック３１８では、相関の尺度に基づいて、上位１０個の候補を見つけ出すために線形変換候補の入力ストリームをソートする。この相関の尺度は、この実装形態では、線形変換候補が参照信号及び被疑信号をアライメントするために使用された後、参照信号と被疑信号との間のドット積として計算される相関強度である。ＲＡＭ３２０は、上位の線形変換候補及び対応する相関メトリックを格納するために使用されるメモリである。
【００９４】
図１３は、図１２が上位線形変換候補で終了したところから開始する。位相推定モジュール３２２は、位相データのシステムを受け取ってＲＡＭ３２４に格納する。位相推定モジュールは、線形変換候補のそれぞれを使用して、参照信号内の周波数位置のそれぞれに対応する被疑画像内の信号成分に関する位相のセットを推定する。線形変換候補ごとに、位相推定モジュールは、線形変換候補と、参照信号内の主は数位置に対応する位相のセットとの両方を提供する。これらの位相は、被疑信号に埋め込まれた参照信号成分の位相の尺度を表す。特に、参照信号がデジタル透かしとして被疑信号内に埋め込まれるこの実装形態では、位相のセットは、ランダム位相を有する正弦曲線に対応する埋め込まれた参照信号成分の位相の推定値を表す。位相推定モジュールの一実施形態では、位相のみに対して、位相と振幅の両方を利用することがある。位相のみの実施形態は、効率的に機能し、満足な結果をもたらす。
【００９５】
他の実装形態では、位相推定モジュールは、ＤＬＳモジュール内に含まれてもよい。その理由は、参照信号座標を変換する行列計算の大部分はそこで既に計算され、位相データもまた容易に利用可能であるからである。この結果、ＤＬＳモジュールは、線形変換とこれらの変換のそれぞれの推定された位相との両方を出力することになる。
【００９６】
位相推定方法をデジタル透かし検出器の実装形態として示したが、位相推定方法は、信号プロセッサが被疑信号内の既知の参照信号を見つけ出そうとする他の用途に適用可能である。例として、信号プロセッサが画像内の既知の参照信号を見つけ出そうとする物体認識及びパターンマッチングがある。位相推定方法は、信号プロセッサが、被疑画像の成分であると疑われる参照信号の位相の推定を計算することを可能にする。次いで、これらの位相推定は、参照信号が被疑信号内に存在するかどうかを検出するために追加のマッチング又は認識動作で使用されうる。これらの方法では、同じ一般的手法が行われる。すなわち、位相推定は、被疑信号の位相と共に、期待される信号パターンと被疑信号内の対応する成分との間の変換の推定値を使用して、被疑画像内の信号パターンの位相の推定値を計算する。
【００９７】
図１３に戻ると、位相偏移モジュール３２６が、各線形変換候補と、被疑信号内の参照信号の推定された位相の対応するセットとを受け取る。位相偏移モジュール３２６は、線形変換候補ごとに位相偏移面を計算する。この面は、位相偏移のアレイであり、アレイ内の各要素は、平行移動オフセットに対応し、要素の値は、対応する期待される位相差と測定された位相差との間の位相偏移メトリックの合計である。２Ｄ位相偏移について、これは、平行移動オフセットのすべてのペア（例えば、１２８掛ける１２８の値の面）に対応する位相偏移値の２Ｄアレイである。先に述べたように、特定の平行移動オフセットに対する位相偏移は、特定の参照信号成分において期待される位相差と測定された位相差との間の偏移を計算する異なるメトリックの合計として計算される。本発明の実装形態では、０、９０、１８０、及び２７０度の配向に対応する各線形変換候補についての４つの配向がある。配向のための位相偏移面を計算するのが終わると、位相レジスタが９０度再配向される。
【００９８】
２Ｄ偏移モジュールの目的は、位相偏移における最小値に対応する１つ又は複数の平行移動オフセット候補を提供することである。言い換えれば、目的は、期待される位相差と測定された位相差との２つの間の最小偏移によって決定されるように、期待される位相差と測定された位相差が最も合致する平行移動オフセットを見つけ出すことである。実装形態は、大きな定数から位相偏移を引いて、最小値を探索する問題を便宜上ピークを探索する問題に変換する（この場合、ピークは、位相偏移面における最小位相偏移メトリックを表す）。目的は、期待される信号と測定された信号（すなわち、既知の参照信号と被疑画像におけるその対応物）の最良の合致を見出すことであるので、ハードウェアは、その２つの間の偏移のピークを見つけ出そうとする。初期２Ｄ位相偏移面が、計算効率のために整数平行移動オフセットに対して計算される。しかし、実際の平行移動は、分数（すなわち、サブピクセル）オフセットに存在することがある。結果として、反転された位相偏移面におけるピークが、２掛ける１のピクセル領域に広がることがある（水平又は垂直方向に）。この影響を解消するために、ピークは、最高２×１（Ｈｉｇｈｅｓｔ２ｘ１）モジュール３２８において２×１領域にわたって探索される。
【００９９】
ノイズ及び歪みの影響を解消するために、絞り込みモジュール３３２を使用して上位Ｎ個のピーク候補が更に評価される。
【０１００】
絞り込みモジュールは、反転された２Ｄ位相偏移面で識別されるピーク（例えば、位相偏移面における振幅が最も最小のもの）の上位Ｎ個のピーク（例えば、２掛ける１）から開始する。Ｎの値は、計算効率と頑強性の間のトレードオフとして決定され、通常２と１０の間である。次いで、これらＮ個のピークのそれぞれについて、絞り込みモジュールは、ピークに対応する平行移動オフセットのあたりの近傍の絞り込まれた位相偏移面を計算する。これらの絞り込まれた位相偏移面は、サブピクセル平行移動オフセットに対して計算される。特に、期待される位相差は、ピークの整数平行移動オフセット位置のあたりのＭ掛けるＭアレイにおけるサブピクセル平行移動のそれぞれについて計算される。Ｍの値及び平行移動の分数（すなわち、サブピクセル）の増分は、所望の計算処理量及び頑強性に基づいて決定される。Ｍの典型的な値は１６であり、典型的な分数の増分は、４分の１ピクセルである。位相偏移の合計が、サブピクセル位相偏移面を提供するために計算される。より高いピークを有するサブピクセルオフセットがある場合、このサブピクセルオフセットは上位ピークのリストに含められる。
【０１０１】
２Ｄ位相偏移モジュールの出力は、線形変換候補であり、位相偏移面（絞り込み段階で計算される任意の表面を含む）における最小値に対応するピーク座標のリストが後続する。
【０１０２】
平行移動補正モジュール３３０は、線形変換候補のそれぞれについて計算された平行移動オフセットを補正する。補正の性質は、実装形態に特有であり、実装形態の詳細に依存し、例えば、入力として使用される参照信号位相がフーリエ表現ブロックの中央に対して表現されるかそれともブロックの角部に対して表現されるか、フーリエ処理及び表現がブロックの中央に対してかそれとも角部に対してか、及び、変換された被疑信号又は参照信号の座標系に対して表現されるかに依存する平行移動の差に依存する。
【０１０３】
図１４は、偏移メトリックに基づく位相偏移方程式を示す図である。この図は、位相偏移メトリックの例を示す。このメトリックは、位相偏移面内の位相偏移値をどのように計算するかを示す。図１４に示されるように、位相偏移は、参照信号の特定の周波数成分ｉについて測定された位相差と期待される位相差との間の偏移を表す。測定された位相差は、被疑信号内の参照信号の推定された位相（例えば、位相推定プロセスで決定された）についての周波数成分ｉの位相角と、参照信号成分の既知の位相角との間の差である。前述のように、位相推定プロセスは、変換された状態で被疑信号について位相角推定値を提供する。実装形態では、既知の参照信号のために使用される位相角は、その元の未変換の状態にある。
【０１０４】
期待される位相差は、水平及び垂直位相オフセットから直接計算される。上記のように、これらのオフセットは、整数オフセットとして始まり、次いで、絞り込みのためにサブ整数（ｓｕｂ−ｉｎｔｅｇｅｒ）（例えば、サブピクセル）となる。
【０１０５】
式中、参照信号中にＭ個の周波数成分があることに留意されたい。偏移メトリックは、周波数成分のそれぞれについての個々の偏移の合計である。ユークリッド距離測度が示されているが、前述のように他の偏移メトリックが使用されてもよい。
【０１０６】
図１４の描写から、図示の２Ｄの場合、参照信号を使用することによって、１Ｄ位相偏移の２つの別個のインスタンスに減少させることができることが分かり、この参照信号は、垂直軸に対して対称であって、したがって水平成分が互いに打ち消す対の周波数成分を有し、また同様に、水平軸に対して対称であって、したがって垂直成分が互いに打ち消す対の周波数成分を有する。前述のように、これにより、垂直及び水平平行移動オフセットが、各ＩＤ位相偏移アレイにおけるピークの独立した探索で別個に決定されることが可能になる。
【０１０７】
図１５は、ＤＬＳ方法の実装形態を示す図である。これは、例えば図１２のブロック３１２内の処理の実装形態である。前述のように、ＤＬＳモジュールは、ブロック３５０でシード線形変換候補のセットから開始する。例えば、この実装形態は、２掛ける２の線形変換行列で表現される線形変換パラメータのサブセットを含む、回転−スケール候補のまばらなセットから開始する（前述の一例のように）。２掛ける２の行列で表現される他の線形変換パラメータは、差分スケール（例えば、水平及び垂直スケール）並びにせん断変形（例えば、水平及び垂直せん断変形）を含む。ＤＬＳ方法が回転及びスケール候補から開始すると、他のパラメータは、任意の追加の変換を提供しないように当初想定され、方法の引き続く反復により、他の線形変換をパラメータが参照信号と被疑信号との間のより良い適合を実現するように変化することが可能なように線形変換を更新する。他の実装形態では、まばらな線形変換候補の異なるサブセット又は定式が、シード候補として選択されてもよい。
【０１０８】
シード候補の開始セット内の各線形変換候補について、ＤＬＳモジュール内の変換モジュールが参照信号内の周波数成分の周波数位置を変換する（３５２）。次いで、サンプルモジュールは、各変換された位置の場所周辺の近傍位置で被疑信号の周波数平面をサンプリングする（３５４）。近傍は、変換された周波数位置を囲む領域であり、実際的には、被疑信号のＦＦＴにおけるいくつかの離散周波数位置を包含する。次に、ＤＬＳモジュール内の相関モジュールが、信号相関メトリックを計算し（３５６）、この信号相関メトリックは、参照信号の各変換された成分の周囲の被疑信号内のこれらの領域について参照信号と被疑信号との間の相関の尺度を提供するものである。このプロセスの終わりに、ＤＬＳモジュールは、線形変換候補に対する信号相関メトリックを有する。このメトリックが、先行の反復に対する先に格納されたメトリックに対して改善されたかどうかが決定される（３５８）。ＤＬＳモジュールは、相関メトリックに改善がある（３５８）、及び反復限度に達していない（３６０）限り、続行される。
【０１０９】
領域及びそれらの領域について計算された信号相関メトリックを計算する様々な方法がある。ＤＬＳモジュールが４つの最近傍位置からサンプリングをする一実装形態では、信号相関メトリックが、被疑信号内の変換された場所ごとのそれらの隣接物での周波数振幅の共一次内挿の合計として計算される。代替形態は、共３次内挿を使用して、及び各変換された周波数成分の場所のあたりの３掛ける３のサンプル領域を使用して相関を計算することを含む。相関は、領域における被疑信号の位相成分の相関も含むことができる。この場合、位相推定方法を用いて被疑信号内の位相が推定される。
【０１１０】
ＤＬＳモジュールが、信号相関を改良しまた反復限度より下である線形変換候補を見つけ出す場合、ＤＬＳモジュールは、最小二乗計算器への入力のセットの確立に進み、最小二乗計算器は、新しい候補線形変換を計算する。入力のこのセットは、周波数振幅の最大値が存在する、各変換された周波数成分位置に対応する周波数成分位置のセットを含む。参照信号の成分ごとのこれらの新しい位置を見つけ出すプロセスは、ブロック３６２に反映されている。特に、座標更新モジュールは、変換された座標位置のあたりの近傍の特徴座標（例えば、ピーク）を計算する。次に、最小二乗計算器（３６４）は、参照信号成分をそれらの元の場所からブロック３６２で見出された新しい位置へ最も良くマッピングする線形変換を見つけ出すために、最小二乗法を使用することにより、新しい線形変換候補を計算する。
【０１１１】
ブロック３６２に示されるプロセスは、前述の「座標更新」の実装形態である。参照信号の周波数成分の座標を更新する１つの手法は、２掛ける２、３掛ける３、５掛ける５など、変換された周波数位置のあたりのサンプル領域のような隣接領域における最大の振幅を有する隣接周波数位置の座標を選択することである。このプロセスは、新しい座標を見出すために内挿を必要としない。いくつかの実装形態では、本発明らは、３掛ける３の近傍は、２〜３％までの差分スケールアップ、時には５％までのスケールアップを含むことを見出した。より大きな近傍を用いることと、参照信号の隣接周波数成分のノイズによる潜在的な混乱との間にトレードオフがある。本発明の実装形態は、参照信号を使用し、Ｍは、３５〜７５の範囲であり、被疑画像は、およそ１００ドットパーインチ（ＤＰＩ）の解像度でサンプリングされ、ブロックサイズ及びＦＦＴサイズは、１２８掛ける１２８サンプルである。近傍サイズ及び形状は、参照信号の固有の特性に合わせて調整してもよい。近傍サイズは、周波数の増大と共に増大することができる。近傍サイズ及び形状は、参照信号内の隣接周波数成分によるノイズの競合を避けるように調整してもよい。近傍サイズ及び形状は、線形変換候補（例えば、ＬＴ候補によって変換された）に応じて適合させることもできる。また、変換された位置の座標の更新は、隣接ピークの中心（例えば、正規化された質量中心）、質量中心、二次フィット（ｑｕａｄｒａｔｉｃ  ｆｉｔ）、又は隣接値の他の内挿を見つけ出すことなどによって、隣接値の組み合わせとして計算してもよい。位相推定によって被疑信号から取得された位相推定値は、本明細書で更に説明されるように、最大振幅を有する周波数位置を見つけ出すために使用されてもよい。
【０１１２】
ブロック３６４の最小二乗計算器は、図に示される式を実装して、式の左側の２掛ける２の線形方程式を解く。これは、乗算及び加算論理回路を使用してハードウェアで実装され、もちろん、ソフトウェア（ファームウェア命令を含む）で実装されてもよい。図示のように、入力は、参照信号成分の座標、及び先行ブロック（３６２）から決定されるように被疑信号内の参照信号についての対応する更新された座標である。
【０１１３】
ブロック３６４で線形変換候補の更新を計算した後、ＤＬＳモジュールはこの線形変換を新しい候補として追加し、ブロック３５２に戻る。
【０１１４】
判断ブロック３５８〜３６０で決定されるようにＤＬＳモジュールが完了すると、結果として得られた線形変換候補及びそれに関連する信号相関メトリックが、更なる処理のために格納される（３６６）。ＤＬＳモジュールは、ブロック３６８に示されるように、更なるシード線形変換候補について反復をする。初期候補が図示のように処理されて絞り込まれると、ＤＬＳモジュールは、各初期シード候補について絞り込まれた線形変換候補を有する。ＤＬＳモジュールは、このセットの絞り込まれた線形変換候補を探索して最も強い相関を求める。次いで、相関に基づく上位候補のサブセットが、前述のように更なる処理で使用されうる。また、前述のように、線形変換候補は、クラスタ化され組み合わされて新しい線形変換候補を形成することができる。
【０１１５】
透視変換の効果を軽減するために、せん断及び差分スケール方向において追加の候補を含むようにシードが拡張される。例えば、一実施形態では、シードは、回転及びスケールパラメータ候補の対から構成され、各回転及びスケール候補対あたり追加の数Ｎ個の差分スケール及びせん断パラメータを伴う。本発明者らは、４及び８のＮの使用が、本発明の実施形態において効果的な透視法の緩和をもたらすことを見出しているが、Ｎは、用途の必要に応じて異なることがある。
【０１１６】
図１７は、スケール及び回転角パラメータの座標空間内で選択された、回転及びスケールパラメータ候補の例を示す。スケール及び回転角パラメータは、アフィン変換の２×２行列の４次元空間における２次元表面を含む。図１７の例は、均一な間隔のスケール及び回転パラメータを示しているが、間隔は、非均一である、及び／又はアフィン変換を回復する方法の実行中に適応的に決定されることがある。例えば、回転及びスケールパラメータシード候補は、被疑画像上で分類子を実行することに基づいて選択されてもよい。分類子は、画像特性に基づいてシード候補を選択するように訓練される。
【０１１７】
均一な間隔の場合、回転及びスケールパラメータシード候補は、均一なステップによって離間される。回転角候補は、望ましい範囲の可能な回転角度、例えば０〜９０度にわたって、約１〜２度のステップサイズで離間される。スケールパラメータ候補は、スケールの下限、例えば、元の画像サイズの約１／４から、何らかの望ましい上限、例えば、元の画像サイズの２倍以上にわたる。これらの限界は、望ましい動作範囲及び性能要件に基づいて調整されてもよい。
【０１１８】
図１８は、Ｎ次元変換パラメータ空間の追加次元で変換候補を拡張する方法を示す図である。この例では、回転／スケール対の２次元表面が、回転／スケール部分空間内で元のシードごとに差分スケール及びせん断の８個の追加のパラメータを含むことによって拡張される。
【０１１９】
この手法では、以下の例に示されるように、８個の追加のシードは、回転及びスケールの各元のシードに対して差分スケールとせん断との組み合わせを掛けることによって生成される：
［１．００，０．００；  ０．００，１．００］  ：元のシード
［１．０３，０．００；  ０．００，０．９７］  ：差分スケール
［０．９７，０．００；  ０．００，１．０３］  ：差分スケール
［１．００，０．０３；  ０．０３，１．００］  ：せん断
［１．００，−０．０３；  −０．０３，１．００］  ：せん断
［１．０２，０．０２；  ０．０２，０．９８］  ：差分スケール＋せん断
［１．０２，−０．０２；  −０．０２，０．９８］  ：差分スケール＋せん断
［０．９８，０．０２；  ０．０２，１．０２］  ：差分スケール＋せん断
［０．９８，−０．０２；  −０．０２，１．０２］  ：差分スケール＋せん断
【０１２０】
図１９は、各候補のまわりのパラメータ空間における方向で変換候補を拡張する別の例を示す図である。元のシード（例えば、回転及びスケール対）（５００）は、垂直軸に沿った離散点として示されている。これらのシードは「ファット（ｆａｔｔｅｎｅｄ）」シードと呼ばれる。その理由は、これらのシードは、それぞれ４つの方向５０２、５０４、５０６及び５０８（元のシードのまわりの差分スケール及びせん断方向）で元のシードを拡張することによって４つの追加のシードを含むように拡張されているからである。
【０１２１】
ある特定の実施形態では、アフィン変換を決定する方法が３回以上反復され、各回でシードごとに以下の動作を実行する：
シード又は更新されたシードにより指定された線形変換を適用することによって、変換された参照信号の位置を見つけ出す（例えば、図１５、ブロック３５２）；
変換された参照信号点の近傍における更新されたピーク位置を見つけ出す（例えば、図１５、ブロック３６２）；
元の参照信号点をこれらの更新された位置にマッピングする最小二乗線形変換を見つけ出す（例えば、図１５、ブロック３６４）；
この線形変換についての相関を計算する（例えば、図１５、ブロック３５６）；
相関が先行の反復と比較して減少する場合は終了する（例えば、図１５のブロック３５８、３６０、３６６、３６８、及び３７０を通る信号処理経路）。
【０１２２】
これらの動作の実行は、動作の計算の複雑さを低減することによって最適化されてより速くなりうる。この複雑さの低減は、動作を実装するために使用されるハードウェア論理回路、ファームウェア、又はソフトウェアの速度の増大及び複雑さの低減をもたらす。１つの最適化は、座標更新モジュール３６２又は最小二乗計算器３６４を使用して変換パラメータを絞り込もうとすることなく（例えば、ブロック３５２、３５４、及び３５６に従って）すべてのシードについての相関を計算することである。次いで、Ｎ個（例えば、Ｎ＝１００）の最も高い相関値を有するシードが見つけ出され、後続の処理段階に対する入力として選択され、そこで、絞り込みの複数回の反復（例えば、３回以上）がこれらＮ個のシードのそれぞれに対して行われる。絞り込み段階において、ブロック３６２及び３６４の処理を用いて、変換された参照信号位置の座標を更新し、次いで、最小二乗プロセスを適用して、参照信号をこれらの更新された座標に変換する更新された変換パラメータを見つけ出す。反復において、ブロック３５２〜３５６の処理は、更新された変換パラメータに関して取得された相関メトリックで先行の反復に対して相関を改善するかどうかを決定する。この最適化は、絞り込み段階がすべてのシードに対しては実行されないので、処理を減少させる。
【０１２３】
この最適化の別の変形例では、参照信号のサブセットのみが、Ｎ個の最も高い相関を有するシードを識別するために使用される。例えば、参照信号が周波数領域におけるＭ個のピークから構成される場合、最も低い周波数ピークの１／２Ｍ個未満のサブセットが、最も高い相関を有するシードを見つけ出す第１段階で使用される。使用されるサブセット周波数ピークの数の選択は、特定の用途及び制約に応じて異なる。絞り込み段階では、すべてのＭ個のピークが使用される。
【０１２４】
別の変形例では、最小二乗誤差メトリックを使用して、幾何変換候補を評価し、デジタルデータを抽出するための有効な幾何変換を提供しそうにない候補を除去する。この誤差メトリックは、座標更新プロセスによって識別されるような変換された参照信号成分と画像内の対応するピークとの間の位置誤差の合計を含む。この誤差メトリックの形態には、最小二乗誤差の合計、最小二乗残差の合計、又は二乗誤差の合計などが含まれる。どの幾何候補を絞り込み段階から除去するかを決定するために、最小二乗誤差メトリックが、いくつかの幾何変換候補のそれぞれについて計算される。各候補について計算されたメトリックは、閾値と比較される。誤差メトリックが閾値を超える候補が除去される。閾値は、符号化されたデータを有する画像を使用して訓練プロセスで決定される。絞り込み段階後の復号の成功につながる候補の誤差メトリック、及びそうでない候補の誤差メトリックが、ヒストグラムにプロットされ、有効な幾何変換候補を維持し残りを排除する閾値がヒストグラムから選択され、追加の処理を回避する。不必要な処理を回避するこの手法は、回転、スケール、差分スケール、及びせん断パラメータを含む幾何変換パラメータ空間の広い範囲を有する候補を含む、非常に多数の幾何変換候補を評価することを可能にする。この手法のより詳細については、参照により本明細書に組み込まれる２０１６年５月５日に出願された米国特許仮出願第６２／３３２，４７０号「Ｃｏｍｐｅｎｓａｔｉｎｇ  ｆｏｒ  Ｇｅｏｍｅｔｒｉｃ  Ｄｉｓｔｏｒｔｉｏｎ  ｏｆ  Ｉｍａｇｅｓ  ｉｎ  Ｃｏｎｓｔｒａｉｎｅｄ  Ｐｒｏｃｅｓｓｉｎｇ  Ｅｎｖｉｒｏｎｍｅｎｔｓ」を参照されたい。
【０１２５】
別の変形例では、相関計算のために広がり関数が使用される。参照信号は、参照信号ピークから構成され、相関は、参照信号ピークと被疑画像との間の点ごとの相関を実行することによって計算されてもよい。広がり関数を使用して、各参照信号は、透視法の効果を考慮するように周波数領域で「広げられる」。
【０１２６】
別の変形例では、相関メトリック及び座標更新が位相を含むように構成される。この位相の使用は、上記の位相推定方法の展開から得られる位相特性を使用して効率的に実装することができる。位相推定技法は、参照信号成分の変換された座標が非整数座標に位置するときに、被疑画像の隣接周波数成分から位相情報を推定する効率的な手段を用意する。上記で詳述されたように、これらの推定技法は、分数座標（すなわち非整数座標）における完全な複素周波数成分の推定値を用意する。この推定値は、位相及び振幅の両方が含み、各分数座標で実数及び虚数成分として表現されることがある。これらの変形例では、複素周波数成分（位相及び振幅を含む）は、相関及び座標更新モジュールで活用される。
【０１２７】
参照信号の特定の平行移動は、処理フローのこの時点で分かっていない（位相偏移などの後続プロセスで決定される）が、位相推定は、参照信号成分の完全な複素数値の推定値を提供し、これらの推定値は、（平行移動前の）被疑信号における参照信号の幾何変換を決定するプロセスの相関メトリクス及び他の側面を改善するために使用することができる位相特性を提供する。この方法で収集された複素数情報は、隣接整数座標でサンプリングされた被疑画像の位相特性を、参照信号の期待される位相特性と比較する効率的な手段を可能にする。更に、これらの技法は、以下で更に説明されるように、各周波数成分の複素周波数成分（実数及び虚数成分）を活用して、参照信号のより正確な検出及びその幾何変換の導出を用意することが有利である。
【０１２８】
上記実施形態の変形例では、位相を含む複素周波数成分情報が、相関メトリックモジュール（例えば、図１５の３５６）及び座標更新モジュール（例えば、図１５の３６２）内で使用されることが有利である。これらの実施形態では、参照信号は、周波数領域におけるピーク（例えば、正弦曲線）から構成される。信号歪みの様々な形態の結果として、ピークは、被疑画像の周波数領域における座標上にスミア（ｓｍｅａｒ）する傾向がある。一例は、被疑画像の透視変換による幾何歪みである。他の例は、デジタル画像信号処理（離散サンプリング、窓関数、ＦＦＴによるＤＦＴ実装など）における量子及びサンプリング誤差である。この歪みは、スミアしたピークが実際の参照信号ピーク又はノイズ／ホスト画像干渉に対応するかどうかを評価することをより困難にするため、相関及び座標更新プロセスに誤差を導入する。
【０１２９】
上記で詳述されたように、相関及び座標更新処理の予備動作は、参照信号成分（例えば、ピーク又は正弦曲線）の座標を被疑画像の周波数領域変換の座標に変換することである。たいてい、これらの座標は非整数位置に位置する。相関プロセスは、この位置のあたりの被疑画像内の参照信号のエビデンスを測定して、幾何変換の推定値の利点を評価する。利点が不十分（例えば、相関が閾値未満）である場合、座標更新プロセスは、被疑画像内の参照信号成分の新しい座標位置を検出し使用して幾何変換を絞り込もうとする。
【０１３０】
これらのプロセス内で、（位相を含む）複素周波数成分の推定値を使用して、分数位置におけるスミアしたピークが実際の参照信号ピークに対応するかどうかをより確実に評価する。相関及び座標更新の実装形態の例を詳述する前に、位相特性の説明から始める。
【０１３１】
位相推定プロセスの基礎となる原理は、純粋な正弦曲線参照信号成分を非整数位置に移動させる効果を明らかにする。図２６は、非整数座標に配置された純粋な正弦曲線参照信号成分の整数座標における位相を示す図である。この例では、参照信号成分は、周波数座標（８５．４，７５．７）における正弦曲線である。整数座標における各セル内の矢印は、参照信号成分の位相角を示す。この例が示すように、隣接整数座標における位相は、参照信号成分座標の右上（８６，７５）に最も近い整数隣接要素における位相角が最も近い左下の整数座標（８５，７６）における位相角と同じ方向にある関係を有する。左上（８５，７５）に最も近い整数隣接要素における位相角は、右下（８６，７６）に最も近い隣接要素における位相角と同じ方向にある。正弦曲線の非整数座標（８５．４，７５．７）から更に離れて延びて、位相関係が維持される。すなわち、右上の象限の整数座標においてサンプリングされた位相は、左下の象限の整数座標においてサンプリングされた位相と一致する。同様に、左上及び右下の象限の位相も一致する。
【０１３２】
位相推定計算の１つの結果では、ピークが分数座標上にある場合、左上及び右下の整数座標における成分が同一の位相を有する（例えば、複素数が同一位相角を有する）。同様に、右上及び左下が同一の位相を有する。更に、２つの異なる位相の対は逆である。より一般的なＰＳＦ手法を利用する場合、分数座標における複素周波数の推定値は、位相が標準的構成と異なるならば減少される。このことは、図２６に例示されており、ピークはｘ＝８５．５、ｙ＝７５．５を中心とする。
【０１３３】
実際、本発明者らは、これらの関係が、非整数位置の周辺の最も近い隣接要素に一般的に当てはまることを見出した。しかしながら、画像ブロック上のＤＦＴ実装に適用される窓関数のようなある種のデジタル信号処理は、非整数位置から位相の関係を更に変更することができる。有効な結果が、最も近い整数隣接要素に依拠することによって得られ、したがって、更に遠い歪みは問題でない。
【０１３４】
幾何変換を決定するプロセスは、参照信号成分のこれらの位相特性を活用する。推定された変換の利点を評価するとき、これらの位相関係は、参照信号を推定された変換を用いてそれらの位置に変換することによって決定された座標位置において被疑画像内に実際の参照信号成分があるかどうかを評価するために使用される。
【０１３５】
特に、一実施形態では、複素相関演算で位相関係を活用する。被疑画像のブロックのＦＦＴが、整数座標における被疑画像の複素周波数成分を提供する。各参照信号成分、特定の周波数における正弦曲線について、ＤＬＳ処理ロジックは、その成分の元の周波数座標を被疑画像の周波数領域の座標に変換する（変換された座標）。複素相関演算を例示するために、変換された座標の４つの最も近い隣接複素周波数成分にＦｕｌ、Ｆｕｒ、Ｆｌｌ、Ｆｌｒのラベルを付ける。この表記において、Ｆは、ＦＦＴから取得された実部及び虚部を有する複素周波数成分であり、添字表記は、変換された参照成分に対するその位置を指定し、すなわち、「ｕｌ」は左上、「ｕｒ」は右上、「ｌｌ」は左下、「ｌｒ」は右下である。
【０１３６】
正弦曲線参照成分は、これらの複素周波数成分の整数座標によって線引きされる方形（ｓｑｕａｒｅ）内のどこかにある場合、図２６に示される知見に基づき、複素成分Ｆｕｌ及びＦｌｒの位相がマッチする。Ｆｕｒ及びＦｌｌの位相がマッチする。更に、Ｆｕｌ及びＦｕｒのこれらの位相は１８０度異なる。
【０１３７】
複素相関の処理ロジックは、以下の複素線形結合を用いて、隣接複素周波数成分Ｆｕｌ、Ｆｕｒ、Ｆｌｌ、Ｆｌｒを使用して各変換された参照信号成分について相関を決定する：
ａＦｕｌ−ｂＦｕｒ−ｃＦｌｌ＋ｄＦｌｒ。
【０１３８】
係数ａ、ｂ、ｃ、及びｄは、０と１の間のすべての実スケールである。これらの実スケールは、幾何変換の推定値により予測される周波数位置に最も近い周波数ビンに重み付けするために選択される。これらの係数の１つの選択肢は、隣接整数値の共一次内挿として係数を計算することである。別の選択肢は、分数座標のための点広がり関数方法から得られた重みを使用することである。位相関係が、この動作において適用されるスケールファクタの符号によって利用され、元の参照信号成分に対して位相が同じ方向である又は位相が１８０度ずれているという事実に対応することに留意されたい。この関係は、参照信号が画像（被疑画像）に埋め込まれるとき、及び被疑画像が歪みを受けるとき、おおむね維持されるはずである。したがって、被疑画像位相属性は、参照信号成分の被疑位置で異なる場合に、より低い相関結果をもたらすことになる。この位相関係の使用は、参照信号成分の存在のより効果的な評価をもたらす。
【０１３９】
この単一ピークについての相関値は、複素線形結合から得られる複素ベクトルの長さによって与えられる：
｜ａＦｕｌ−ｂＦｕｒ−ｃＦｌｌ＋ｄＦｌｒ｜。
【０１４０】
一実装形態では、スケールファクタは共一次内挿スケーリングから取得される。（ｘ，ｙ）に配置された変換された参照成分に関して、すべての参照信号成分についての全複素相関が、以下の擬似コードで示されるように決定される。
{totCorrelation = 0;
For all reference signal components
// (xFrac, yFraqc) = fraction of thelocation (x,y)
fracX = x - floor(x );
fracY = y - floor(y);
// scale the complex frequency values
ulCmplx = ulCmplx * (1 - fracX) * (1 -fracY);
urCmplx = urCmplx * ( fracX )   *(1 - fracY);
llCmplx = llCmplx * (1 - fracX) * (fracY);
lrCmplx = lrCmplx * ( fracX )   *(fracY);
// Add the complex values using theexpected phase relationship
totCmplx = ulCmplx - urCmplx - llCmplx +lrCmplx
// Compute the magnitude
totMag = sqrt(Re(totCmplx)2 +Im(totComplx)2));
// Add to total correlation
totCorrelation += totMag * scaling;
}
// totCorrelation is the final complexcorrelation, which is a real positive number.
The scaling for the four neighboringintegers is given by bilinear scaling:
Upper Left Scale = (1 - fracX) * (1 -fracY)
Upper Right Scale = (fracX) * (1 - fracY)
Lower Left Scale = (1 - fracX) * (fracY)
Lower Right Scale = (fracX) * (fracY)
【０１４１】
座標更新プロセスにおいて、処理ロジックは、変換された参照信号座標のそれぞれの近傍のピークの探索を実装する。この探索は、最も高い周波数振幅を有する近傍内の位置を見つけ出す処理ロジックによって実装される。この処理ロジックは、位相推定方法を使用して、近傍内の候補位置における複素周波数成分を推定する。これらの候補位置は、周波数領域（画像ブロックの２Ｄ  ＦＦＴによって確立される領域）の整数座標周辺の分数位置の２次元アレイとして定義される。
【０１４２】
特に、分数位置を有する周波数に関して、処理ロジックは、位相推定値を使用して、分数位置のこのアレイ内の各候補位置における複素ピーク周波数を推定する。他の分数が利用されてもよいが、一実装形態では、ｘ及びｙ方向で候補位置間の増分として１／８を使用する。言い換えれば、整数座標の４つの最も近い隣接要素によって線引きされる方形の領域は、候補位置の８掛ける８のアレイである。候補位置のそれぞれにおける位相推定値を取得するために、処理ロジックは、４つの隣接複素周波数成分をサンプリングし、位相推定方法に従って、メモリ（例えば、ＲＯＭ又はＲＡＭユニット）内のルックアップテーブルに予め格納された分数位置に対する重み因子を適用する。各分数座標における複素ピークは、位相推定の推定値に従って選択された４つの周囲の複素周波数成分及び４つの複素重みの複素相関を使用して計算される。
【０１４３】
座標更新の処理ロジックは、元の周波数面（例えば、デジタル画像ブロック及び対応する２Ｄ  ＦＦＴに基づく、１２８掛ける１２８、２５６掛ける２５６、５１２掛ける５１２）よりもＮ倍大きい（ここで、１／Ｎは分数位置増分である）周波数面を得るために候補位置におけるすべてのこれらの推定値の振幅を計算する。表面のより小さい部分が、そのより小さい部分内に参照信号成分が限定されることが期待される場合に使用されてもよい。候補位置における振幅は、複素ベクトルすなわち実数成分と虚数成分の長さであり、その長さは、例えば、各候補位置における実数成分と虚数成分の二乗和の平方根として計算される。
【０１４４】
参照信号座標を更新するかどうかを決定するために、処理ロジックは、各成分の変換された参照信号座標のあたりの近傍でピークを探索する。処理ロジックは、この拡張された周波数領域面における最も高い位置を探索する。近傍は、隣接整数座標（例えば、周波数領域面における２掛ける２又は３掛ける３の整数座標）を含む領域にわたり、これらの整数座標によって囲まれる領域内の分数位置を含む。最も高い振幅を有する位置が、参照信号成分の位置として使用される。次いで、処理は、上述のように、更新された参照信号座標に基づいて幾何変換を絞り込むに進む。
【０１４５】
このＮ倍拡張された周波数面を、所与の幾何変換候補の相関を計算するために使用することもできる。これは、上述された複素相関技法の隣接成分の位相関係を利用する変形例である。検討するため、上記の擬似コード例は、隣接整数座標における共一次内挿及び位相関係を使用して、非整数位置で、より識別できる相関値を計算する。位相関係が、点広がり関数重みを介して相関メトリックで利用されてもよい。この変形例では、Ｎ倍の周波数面上の相関の計算は、各変換された参照信号成分の位置における位相推定によって提供される複素周波数推定値の振幅を使用して相関メトリックを計算する。この方法で、複素周波数推定値を使用して、座標更新で使用されるピーク位置と相関値との両方を推定することができる。
【０１４６】
拡張された周波数面は、検査されている画像又は画像のブロックについて予め計算され、分数位置でインデックス付けされルックアップテーブルに格納される。次いで、このルックアップテーブルは、候補幾何変換のための変換された参照成分の非整数位置における相関メトリックを取得するために使用される。加えて、ルックアップテーブルは、座標更新プロセスのための参照信号成分の新しい座標を取得するために使用される。
【０１４７】
位相推定の更なる背景は、参照により本明細書に組み込まれる米国特許仮出願第６２／０３６，４２７号及び第６２／１０２，５４７号並びに対応する非仮出願の米国特許出願公開第２０１６／０１８８９７２号に示されている。
【０１４８】
被疑画像の画像ブロックにわたる歪みは、しばしば均一ではなく、したがって、均一な歪みの近似に依存する信号抽出及び認識動作の性能を低下させる。不均一な歪みの一例は、上記の場合の透視変換である。所与の画像ブロックの幾何歪みはアフィン変換で近似されることがあるが、この近似における誤差はブロック全体にわたって変化することがある。したがって、近似の使用は、ブロック内の画像サンプルに対する後続の画像処理動作のために一様には信頼できない。
【０１４９】
図２０は、実際の歪められた画像ブロック（破線）に重ねられた画像ブロック（実線）の近似された幾何変換を示す図である。左上隅では、実線は破線により近く一致し、近似された幾何歪みが実際の歪みにより近いことを示す。他方の極端が右下に示される。そこでは、画像ブロックの近似された幾何変換を示す実線が、画像ブロックの実際の変換の破線からより大きく外れている。
【０１５０】
近似におけるこの誤差が問題となる１つの場合は、デジタル透かしメッセージ抽出である。デジタル透かしメッセージ抽出は、メッセージ信号が埋め込まれている画像内の位置（埋め込み位置）からメッセージ信号を抽出するプロセスである。埋め込み位置の近似が不正確であると、抽出プロセスにノイズが導入される。このノイズにより抽出の信頼性が低くなり、信頼性は画像ブロック内の埋め込み位置の近似の誤差によって変化する。この問題に解決するために、参照信号から取得された信号メトリックを使用して、画像における埋め込み位置から抽出されたメッセージ信号に重み付けする。以下では、この手法を使用してデジタル透かしメッセージ抽出を改善する様々な戦略を詳述する。
【０１５１】
いくつかのデジタル透かしアプリケーションでは、メッセージシンボルのシーケンス（例えば、バイナリシンボル又はＭ−ａｒｙシンボル）から構成されるデジタルメッセージペイロードが、画像ブロックにわたって符号化される。メッセージシンボルは、誤り訂正を使用して及び／又は搬送波信号に変調することによってロバスト性を高めるように符号化される。得られた符号化シンボルは、ブロック内の埋め込み位置にマッピングされ、埋め込み位置においてホスト画像を修正することによって埋め込まれる。例えば、ホスト画像ピクセル値（例えば、輝度、クロミナンス、又は他の所望の色方向）は、符号化シンボル値、可視性閾値、及びロバスト性閾値の関数として調整される。例えば、参照により本明細書に組み込まれる米国特許第８，１９９，９６９号及び米国特許出願公開第２０１５／０１５６３６９号を参照されたい。ペイロードは、画像ブロック（例えば、１２８×１２８、２５６×２５６、５１２×５１２ピクセルブロック）におけるペイロードを冗長的に符号化することによって、イメージの範囲にわたって繰り返される。いくつかのブロックパターンが可能であるが、１つの手法は、画像全体にわたってブロックを連続したタイルに配置することである。例えば、参照により本明細書に組み込まれる米国特許第６，１２２，４０３号、第６，６１４，９１４号、及び第９，０８３，５１１号を参照されたい。
【０１５２】
幾何変換された画像における各ブロックからペイロードを抽出するために、まず埋め込み位置の幾何変換を推定する必要がある。幾何変換を推定するこのプロセスは、同期又は同期化と呼ばれることがある。その理由は、このプロセスは、元の画像での埋め込み位置と歪められた被疑画像での埋め込み位置との間の幾何変換を近似することによって、埋め込み位置に対するメッセージ抽出プロセスを同期させるからである。幾何変換は、被疑画像における変換された埋め込み位置に対するデジタル透かしの元の埋め込み位置の近似をもたらす。幾何変換を近似する多くの方法があり、そのいくつかは上記に詳述されている。例えば、透かし信号の（平行移動を含む）アフィン変換は、本明細書、及び／又は参照により本明細書に組み込まれる米国特許第６，１２２，４０３号、第６，６１４，９１４号、第６，５９０，９９６号、第６，４８３，９２７号、第６，９７５，７４５号、第７，０７２，４９０号、若しくは第８，６９４，０４９号に記載の方法を使用して、被疑画像における参照信号のアフィン変換を検出し決定することによって、決定される。参照信号は、符号化されたメッセージ信号とは別個の明示的参照信号であってもよい。或いは、参照信号は、符号化されたメッセージシンボルのパターン化又は配置によって形成された暗黙的参照信号であってもよい。例えば、参照により本明細書に組み込まれる２０１５年５月２８日に出願された同時係属出願第１４／７２４，７２９号を参照されたい。いずれの場合も、参照信号は、メッセージシンボルが埋め込まれた画像ブロックにわたり、したがって、ブロックに対するそのアフィン変換を決定することにより、そのブロック内の未知のメッセージシンボルの埋め込み位置のアフィン変換を提供する。
【０１５３】
同期されると、デジタル透かしメッセージ抽出が進行して、埋め込み位置で符号化されたメッセージシンボルの推定値を抽出する。同期は、メッセージ抽出プロセスが被疑画像内の埋め込み位置を特定することを可能にする幾何変換を提供する。元の埋め込み位置の座標が、幾何変換によって被疑画像座標系にマッピングされてもよく、又は被疑画像が元の埋め込み位置の座標系にマッピングされてもよい。埋め込み位置では、被疑画像をサンプリングしフィルタリングして、符号化されたメッセージシンボルの推定値を得る。例えば、参照により本明細書に組み込まれる米国特許第７，２３１，０６１号及び第６，５９０，９９６号を参照されたい。
【０１５４】
次いで、メッセージシンボルは、符号化されたメッセージシンボルの推定値から復号される。これは、復調及び誤り訂正復号を含んでもよい。この文脈では、復調は、メッセージ搬送波信号からメッセージを復調することを指す。搬送波信号は、正弦曲線又は正弦曲線の集合などの搬送波である。搬送波信号は、ホスト画像の派生物であってもよい。搬送波信号は、スペクトラム拡散変調で使用されるような擬似ランダムシーケンスであってもよい。変調は、周波数シフト若しくは位相シフト変調又は振幅変調などであってもよい。復調は、この変調技法による搬送波からのメッセージの復調である。
【０１５５】
誤り訂正復号は、符号化されたメッセージシンボルを生成するために利用される誤り訂正の対照物である。例として、畳み込み、リードソロモン、ターボ符号、ブロック符号などがある。ソフト誤り訂正が利用されてもよい。例えば、ソフト誤り復号が、畳み込み符号化されたメッセージシンボルのビタビ復号器を使用して実装されてもよい。例えば、参照により本明細書に組み込まれる米国特許第７，２７７，４６８号、第７，０７２，４９０号、及び９，０８３，５１１号を参照されたい。
【０１５６】
メッセージシンボルの推定値の信頼性は、被疑画像がメッセージの埋め込みの後に遭遇した種々の歪みにより変化する。したがって、ソフト復号は、信頼度尺度に応じて推定値に重み付けするために利用されることが好ましい。例えば、参照により本明細書に組み込まれる米国特許第７，４６６，８４０号を参照されたい。
【０１５７】
幾何変換が近似される場合、近似の誤差が、符号化されたメッセージシンボルの推定値に誤差を導入する。メッセージ抽出プロセスにおけるこの誤差を緩和するために、コード化されたメッセージシンボルの推定値が、コード化されたメッセージシンボルの推定値の埋め込み位置における近似の信頼性の尺度を提供する信号信頼度メトリックに基づいて重み付けされる。次いで、この重み付けは、メッセージシンボルの重み付けされた推定値からのメッセージの後続の復号で使用される。後続の復号は、上述したように、復調及び／又は誤り訂正復号を含んでもよい。後者の場合、誤り訂正復号は、上記で参照され以下で更に説明される技術を使用して、ソフト誤り復号の形態を利用することができる。
【０１５８】
図２１は、画像から抽出されたメッセージ推定値に重み付けするために使用される信号信頼度メトリックを決定するための処理の実装のブロック図である。設計の変形例によって説明するように、処理フローはハードウェア又はソフトウェアのいずれかで実装するために設計されている。ブロック６００は、被疑画像ブロック６０２、ブロックの幾何変換（例えば、ブロック方向を含む）６０４、及び参照信号６０６が格納されるメモリ、例えばＲＡＭである。これらのデータタイプのそれぞれは、それぞれの必要に応じてサイズ及びビット深度について適合された別々のＲＡＭユニットに格納されてもよい。或いは、それらのデータタイプは、汎用コンピュータ用のソフトウェア実装で典型的であるような汎用ＲＡＭに格納されてもよい。最後に、いくつかの実装形態は、両方の組み合わせを利用する。ＲＡＭユニットは、「オンチップ」ＲＡＭとしてデジタル論理コンポーネントのパイプライン化されたハードウェア段階に統合されてもよい。汎用ＲＡＭは、デジタルロジック（例えば、パイプライン段階）、又は標準バスアーキテクチャを介してソフトウェア若しくはファームウェアを実行するプロセッサによってアクセスされてもよい。本発明の実装形態のいくつかは、例えば、バスインターフェース、及びＡＭＢＡバス規格に従って設計された関連するコントローラを利用する。
【０１５９】
パイプライン化された実装形態では、処理の各段階に対するデジタルロジックがパイプラインに配置される。データは、このパイプラインを介してその入力からその出力にクロックされる。中間計算のためのデータが、各ステージのレジスタに取り込まれる。パイプライン段階あたりのロジック及び計算の量が、目標クロックレートのタイミングウィンドウを満たすように調整される。サブブロックあたりの信号信頼度メトリックを計算するためのロジックが、パイプラインで実装されてもよく、例えば、図２１のブロックが、パイプライン段階で配置されたデジタルロジックである。
【０１６０】
ブロック６０８は、符号化されたメッセージシンボル推定値の信頼度尺度を決定するための動作を実行するロジックである。このロジックは、プロセッサ（例えば、ＣＰＵ、ＧＰＵ、ＤＳＰなど）上で実行するソフトウェア又はファームウェア命令として実装されてもよい。このロジックは、ＡＳＩＣ、ＦＰＧＡなどのデジタル論理コンポーネント（乗算器、加算器、平方根演算子、平方演算子、除算器など）に実装されてもよい。
【０１６１】
ロジック６０８は、メモリインターフェース６１０を介してメモリ６００におけるデータ信号と通信する。このメモリインターフェースは、例えばＡＭＢＡバス規格に従うバス並びに関連するバスインターフェース及び制御ロジックとして、又はデジタル論理パイプラインにおけるパイプ段階を介してオンチップＲＡＭからのデータのフローを制御する制御ロジックとして実装されてもよい。この技術を実装するためのコンピューティングアーキテクチャ及びハードウェアアーキテクチャの更なる背景については、参照により本明細書に組み込まれる同時係属中の２０１５年７月２日に出願された米国特許仮出願第６２／１８８，４４０号及び２０１５年７月２４日に出願された米国特許仮出願第６２／１９６，８７６号、並びに２０１５年９月１日に出願された対応する非仮出願の米国特許出願第１４／８４２，５７５号、名称「ＨＡＲＤＷＡＲＥ−ＡＤＡＰＴＡＢＬＥ  ＷＡＴＥＲＭＡＲＫ  ＳＹＳＴＥＭＳ」を参照されたい。
【０１６２】
図２２は、処理ロジック６０８の動作の説明を助けるために、デジタル透かし信号の埋め込み位置６３２のタイル状パターンに重ねられた画像ブロック６３０の例を示す図である。透かし信号ブロックのタイル状構造は、太い暗線６３４により示され、埋め込み位置６３２をタイルと呼ばれるブロックに細分化する。各画像ブロックに関して考えられる埋め込み位置６３２は、画像ブロック６３０周辺の境界領域内にある。タイルあたりの埋め込み位置の数は、上述したように適用例によって異なることがあり、ここで示される数は、説明のための例にすぎない。同期プロセスから、画像ブロックの幾何変換が近似され、この例では、透かしタイルに対して回転、スケール、及び平行移動シフトを伴う画像ブロックとして反映される。図２０に示されるように、画像ブロックの実際の幾何変換はアフィンでないことがあり、（例えば、透視変換又はカメラの向き及び／若しくは画像の表面配向による他の変換によって）歪められることがある。
【０１６３】
この実装形態では、ロジックは、デジタル透かし信号の埋め込み位置に沿って進むことによって被疑画像６３０を処理する。線６３６及び６３８は、画像ブロック６３０のスライスが一度に処理されることを示すために追加されている。この場合、スライス内の画像データのトラバースを完了した後、画像データのスライスがメモリ６０２において処理され、次いで、ロジック６０８が次のスライスに進む。例えば、画像メモリは、オンチップＲＡＭ及びオフチップＲＡＭによって実装されてもよく、画像のスライスが、ＡＭＢＡバスを介してオフチップＲＡＭからオンチップＲＡＭに追加される。
【０１６４】
ロジック６０８は、埋め込み位置の列に沿って画像をトラバースする。第１列の強調表示された部分６４０、及び部分６４０の上の矢印は、ロジックが進む方向、すなわち、各列を下に進んでから次の列に行くことを示す。これは、画像ピクセルを埋め込み位置にマッピングするのではなく埋め込み位置を画像内にマッピングする選択と同様に、設計上の選択の問題（列単位対行単位）である。カウンタは、画像ブロックライン、並びにメモリバッファにおける上部及び下部ピクセル行を追跡するために使用される。レジスタは、画像データが抽出された各列における位置を追跡し続ける。
【０１６５】
図２１に再び戻り、ブロック６１２のロジックは次の埋め込み位置に進む。この実装形態における画像ブロックの幾何変換は、メモリユニット６０４に格納され、サブピクセル精度（例えば、位相偏移プロセスに関する上述されたようなピクセル座標間の分数位置）に指定された平行移動を含むアフィン変換パラメータを含む。ブロック６１４のロジックは、タイル中心に対する埋め込み位置の座標を決定し、それに平行移動の小数部分を加える。ブロック６１６のロジックは、幾何変換パラメータによる座標のベクトル乗算を適用することによって、埋め込み位置の座標を画像内の位置にマッピングする。ロジックは、この位置が画像バッファ内に含まれるかどうかを（上端、下端、左端、及び右端をチェックすることによって）決定する。含まれる場合、ブロック６１８の論理が、マッピングされた位置のあたりの画像値をサンプリングする。これは、マッピングされた座標の位置に対する４つの隣接ピクセルに対する内挿演算として実装される。
【０１６６】
一実装形態では、画像のサンプリング動作は、前置フィルタリング動作と関連して動作する。デジタル透かし抽出の場合の前置フィルタリングは、被疑画像を抽出のために準備するための予備フィルタリングを指す。フィルタリングの一態様は、ノイズ及びホスト信号干渉に対して透かし信号を増強することである。例えば、様々な前置フィルタリングを説明している米国特許第６，５９０，９９６号、第７，２３１，０６１号、第７，０７６，０８２号を参照されたい。フィルタリング動作は、ある位置の画像サンプルを隣接位置の画像値に対して比較し、比較の関数としてその位置の新しい値を出力する。例えば、各比較動作において、中間出力は、マッピングされた位置における画像サンプルが隣接値に対して大きいか、等しいか、又は小さいかに応じて、正、ゼロ又は負の整数値である。次に、中間値は、ある正の整数から負の整数の範囲の出力値を提供するように組み合わされる（例えば、合計される）（例えば、水平及び垂直隣接要素を比較するフィルタで２、−１，０，１，２；水平、垂直、及び斜め方向で８個の隣接要素を比較するフィルタで−８〜８）。いくつかの実施形態では、比較動作は、画像サンプルを、隣接値の中央値又は平均のような隣接値の関数と比較する。
【０１６７】
変換された埋め込み位置に前置フィルタを実装するために、ロジックは、アフィン変換のベクトル乗算によって、フィルタサンプル位置のそれぞれを、埋め込み位置に隣接する位置から被疑画像内のマッピングされたサンプル位置へマッピングする。マッピングされた位置に対する画像値は、上述のされたように４つの隣接ピクセルを内挿することによってサンプリングされる。フィルタ演算子は、これらのサンプリングされた値を入力として取り入れ、埋め込み位置のサンプリング値と比較して中間値を生成し、中間値の関数としてフィルタ出力値を出力する。図２３〜２５の追加の図と共に実施形態をより詳細に以下に説明する。ブロック６１８の処理ロジック内のこれらのサンプリング及びフィルタリング動作は、信号信頼度メトリックの画像信号入力を提供する。信号信頼度メトリックが画像と埋め込み位置での参照信号との相関に依存するので、図２１の処理ロジックは、埋め込み位置で参照信号成分を取得するように進行する。
【０１６８】
ブロック６２０のロジックは、参照信号メモリ６０６からの埋め込み位置の参照信号成分を取得し、参照信号成分を画像サブブロックとアライメントさせる必要に応じて調整を伴う。この動作においていくつかの実装変形例がある。設計の一態様は、参照信号の形態である。一実装形態では、参照信号は、それぞれ擬似ランダム位相を有する正弦曲線のコンスタレーションである。この場合、ＤＣ成分が参照信号からその平均を減算することによって除去され、結果がピクセル値の空間領域タイルに変換される。他の実装形態では、参照信号は、メッセージ信号成分の配置から形成された固定メッセージ信号又は暗黙的参照信号に対応する、タイル内のピクセルの配置である。
【０１６９】
設計の別の態様は、参照信号及び／又は画像を調整してそれらをアライメントするプロセスである。例えば、参照信号又は画像ブロックを変換してそれらをアライメントするために、いくつかの調整が必要とされることがある。一実装形態では、参照信号の空間領域タイルが画像ブロックの配向に一致するように回転される。この文脈では、配向は、同期プロセスから得られる互いに対する９０度回転での４つの配向状態のうちの１つを指す。この配向状態は、０〜９０度の範囲の角度である幾何変換の回転角パラメータから離れている。配向状態の数は、参照信号の設計に応じて異なる。フーリエ領域において八分円対称性を有する参照信号では、４つの配向状態が存在する。フーリエ領域において四分円対称性を有する参照信号では、２つの配向状態（０度及び１８０度）が存在する。
【０１７０】
参照信号を変換する別の態様は、同期プロセスによって導出された参照信号の平行移動を考慮に入れた変換である。タイル内の埋め込み位置で参照信号をサンプリングする前に、参照信号の平行移動は画像ブロックの平行移動に対応するように調整される。この配向及び平行移動は、信号信頼度メトリックを導出するのに使用する参照信号の空間領域サンプルを生成するために使用される。生成された参照信号は、次いで、ブロック６２０のロジックによってアクセスされ、現在処理されている埋め込み位置に対応する参照信号値を得る。
【０１７１】
６２０のロジックを実装するとき、例えば、処理速度及びチップ面積の目的及び制約に応じて、代替的設計考慮事項がある。１つの手法は、参照信号の完全な空間領域画像タイルを生成し、タイル内の埋め込み位置における参照信号空間領域値を参照するためにバスを介して又はオンチップバッファ内でアクセスされるメモリユニットに、そのタイルを格納することである。デジタルロジックの実装のために、この完全なタイルは、より大きいオンチップＲＡＭが空間ドメイン参照信号をバッファする必要があるため、コストが高過ぎることがある。代替形態では、必要に応じて空間領域参照信号のより小さい部分を生成し、メッセージ抽出のためにデジタル論理パイプライン内の非常に小さいバッファにそれらの部分を格納する。ブロック６２０のロジックは、参照信号を得ると、現在の埋め込み位置に対応する参照信号の部分についてそのようにする。
【０１７２】
ブロック６２２のロジックは、埋め込み位置における参照信号と画像信号との間の相関の成分を決定する。この動作は、ロジックが各埋め込み位置を訪れて埋め込み位置における画像及び参照信号値をサンプリングするときに実行されてもよい。この動作は、被疑画像及び参照信号のサブブロックを、それらを空間的にアライメントした後にバッファし、次いで、相関の成分として画像及び参照信号サブブロックのベクトル乗算又は比較（例えばベクトルドット積）を実行することによって実装されてもよい。パイプライン化されたデジタル論理設計では、パイプライン段階が埋め込み位置を訪れるとき、埋め込み位置に対して必要とされる場合のみ画像及び参照信号を生成し、この位置についての相関成分を決定し、次いで相関成分を累算することが好ましい。
【０１７３】
ブロック６２４のロジックは、タイルのサブブロックの信号信頼度メトリックを決定する動作を実行する。ロジックは、サブブロックの相関成分を合計することによって信号信頼度メトリックを決定する。このメトリックを計算するために、サブブロック全体の埋め込み位置が訪問されるまで、６１２〜６２０のロジックの実行を埋め込み位置に対して繰り返す。出力は、サブブロックについて合計される。合計は、次いで、サブブロックの総エネルギーに基づいて正規化される。上述したように、回路チップ面積、消費電力、処理速度制約、及びメモリ帯域幅制約に関する設計考慮事項に応じて、動作の順序に変動がある（イメージデータ及び出力のチャンクが、バスを介してＲＡＭメモリからパイプライン化されたプロセッサにロードされ、またパイプライン化されたプロセッサからロードされる）。
【０１７４】
正規化された信頼度メトリックの特定の実装形態は異なりうる。信号相関を測定し、サブブロック内のエネルギーによって正規化する様々な方法がある。本発明の実装形態において、信号相関は、空間領域における対応する画像及び参照信号値を乗算し、得られた積を合計することによって計算される。これは、比較演算又は加重比較演算などの他のタイプの相関を用いて実行されてもよい。それは、透かし信号設計、及び追加のチップ面積に対する許容度、及び他の領域へ／からの画像及び参照信号を変換するためのロジックに応じて、他の領域（例えば、透かし信号の周波数又は他の変換領域）における２つの信号のサンプルに対して実行されてもよい。画像信号に使用される値は、前置フィルタリングされても、フィルタリングされなくてもよいが、前置前フィルタリングは、ノイズ及び／又はホスト信号干渉を抑制する利点を提供する。これは、参照信号に対する信号信頼度を測定する前に、被疑画像の透かし信号コンテンツを強調する利点を有する。信号相関を正規化するために、相関成分の合計をサブブロックの信号エネルギーによって除算する。エネルギーは、一実装形態では、サブブロックの二乗された画像信号成分の合計により乗算された、サブブロックの二乗された参照信号成分の和の平方根として計算される。エネルギー計算に使用される画像信号成分は、信号相関に使用される画像信号成分と同じであり、フィルタリングされてもよくフィルタリングされなくてもよい。
【０１７５】
参照信号が固定又は既知のメッセージシンボル又はメッセージシンボルのパターンから構成される場合、同様の方法が利用されてもよい。ここで、固定は、可変メッセージフィールドのシンボルとは対照的に、これらのメッセージシンボルが変化しないことを意味し、シンボル値は変化して可変メッセージを搬送する（したがって、確実に復号されるまで未知である）。「既知」のシンボルは、固定シンボルなどの予め決定されたシンボルであるか、先行の抽出段階で確認されているシンボルである。例として、参照信号は、タイル内の埋め込み位置にマッピングされ、したがって空間画像タイルに対応する固定メッセージシンボルであってもよい。しかしながら、サブブロックに関する未知のメッセージシンボルについて信頼できる信号信頼度メトリックを与えるためには、未知のメッセージシンボルから独立性を有する参照信号を利用することが好ましい。この独立性のレベルは、可変メッセージ信号に対する参照信号についての直交ベクトルを選択することによって達成されてもよい。例えば、上記で組み込まれた同時係属出願第１４／７２４，７２９号における直交ベクトルの議論を参照されたい。
【０１７６】
信号信頼度メトリックを提供するために、上記の参照信号戦略の様々な組み合わせが使用されてもよい。例えば、サブブロックの信号信頼度は、各画像タイル内の埋め込み位置に散在した既知のメッセージシンボルのアレイから構成される参照信号に基づく信号信頼度と組み合わされた、正弦曲線のアレイから構成される参照信号に基づく信号信頼度の関数であってもよい。
【０１７７】
Ｎ掛けるＮ個の埋め込み位置（例えば、６４、１２８、２５６、５１２）のタイルに対して、信号信頼度メトリックを作成するために使用されるサブブロックサイズは、タイルの一部分である。様々なサイズのサブブロックを使用する実験において、透視変換がある場合のように、アフィン変換がタイルのスパンにわたる幾何変換を正確に表さないとき、より小さいサブブロック（例えば、Ｎ／８掛けるＮ／８のサブブロック）がより良い結果を生じることを、本発明者らは見出した。反対に、幾何変換がアフィン変換によってより綿密にモデル化される場合、より大きいサブブロック（例えば、Ｎ／４掛けるＮ／４のサブブロック）がより良い結果を生じる。
【０１７８】
サブブロックサイズを選択するとき、考慮すべきトレードオフがある。より大きいサブブロックが、信頼できる相関値を与えるためにより良く、より小さいサブブロックは、画像ブロックが透視変換又は他の非アフィン歪みを受けているときにより良い（その歪みは、例えば、カメラが透かし入り対象物の画像を取り込んだときの透かし入り対象物に対するカメラの傾き、対象物表面の変形（柔軟なパッケージ又は材料の操作によって変形された画像）、不規則な形状の物体（例えば、湾曲した表面）などによる）。また、画像が（不注意又は意図的な）操作を受けたとき、これらの操作により、マクロ特性（例えば、より大きいサブブロック）に悪影響を与えうるが、ミクロ特性（例えば、より小さいサブブロック）は損なわれないことがある。
【０１７９】
サブブロックのサイズを適応的に選択することは、既存のＳＮＲ条件に応じて最適な選択を行う方法を可能にする。例えば、一実施形態では、処理ロジックは、複数のサイズのサブブロックについての相関を計算するように構成される。次いで、各領域について、処理ロジックは、サブブロックサイズの最良構成を決定して、相関を実行し、復調決定を通知し、及び／又はローカル変換を調整する。
【０１８０】
サブブロックの幾何変換の近似の誤差に対処するために利用されることがある別の最適化は、サブブロックの幾何変換を絞り込むために指標として信号信頼度メトリックを使用することである。信号信頼度メトリックは、透かし埋め込みのときに画像サブブロックが元のサブブロックとアライメントする程度の尺度を提供する。信号信頼度メトリックが、アラインメントがある利点を有し、更に改善されうる（例えば、望ましい相関レベル未満である）ことを示す場合、ロジックは、絞り込みロジックの実行をトリガすることができる。絞り込みロジックでは、１つ又は複数の幾何変換パラメータがわずかに調整され、信号信頼度を再計算して、信号信頼度メトリックが改善するかどうかを決定する。上述したように、信号信頼度メトリックは、正弦曲線（例えば、周波数領域における点）及びメッセージシンボルパターンを含む、異なる形式の参照信号に基づく信頼度から構成されてもよい。後者の場合、メッセージ抽出方法を使用して、すなわち、既知のメッセージシンボルに対応する埋め込み位置又は埋め込み位置のセットで被疑画像をサンプリングし、復号されたメッセージシンボル推定値を既知のメッセージシンボルと比較することによって、メッセージシンボルパターンを評価することができる。ここでは、埋め込み位置での導出された画像信号特性は、画像値を復号されたシンボルに完全に変換する必要を回避するために、既知のメッセージシンボルの代理として機能することができる。例えば、シンボルが画像値（例えば、空間領域振幅又は位置、周波数領域振幅又は位相など）をシフトすることによって埋め込まれた場合、調整のシフト及び／又は符号の方向（正又は負）は、メッセージシンボルの代理として機能することができる。この代理は、サブブロック内の既知のメッセージシンボルのそれぞれについて期待されるシフトと比較され、その結果が合計されて信号信頼度メトリックを提供する。例えば、正規化された相関の一形式は、期待値と推定値の積の合計を推定値の絶対値の合計によって除算することである。期待値は、信号シフトの符号（正及び負）、及び上述の前置フィルタによって決定される埋め込み位置でのフィルタリングされた出力によって表される推定値によって表されてもよい。
【０１８１】
絞り込みの一形式は、信号信頼度メトリックを改善する調整のために平行移動パラメータ調整のセットを探索することである。信号信頼度メトリックが２つの異なる信号測定に基づく場合、ロジックは、調整のセットにおける両方のメトリックの最大値が同じパラメータ調整に対応する場合に、信号信頼度が改善されたと決定することができる。１つの探索戦略は、例えば、各アフィン変換されたサブブロックの周辺の上、下、左、右の１つ又は２つのサンプル位置において、小さい平行移動シフトを用いて信号信頼度の改善があるかを確認することである。各サブブロックについて幾何変換パラメータの局所的部分空間を探索して、信号信頼度メトリックを改善する更新された変換パラメータを見つけ出すために、他の探索戦略が利用されてもよい。絞り込み変換パラメータ、デジタル透かし抽出のための同期、及びデジタルメッセージ抽出のためのソフト復号の使用に関する更なる例については、参照により本明細書に組み込まれる米国特許第６，９７５，７４５号も参照されたい。
【０１８２】
信号信頼度メトリックは、他のタイプの信号処理動作から生成されてもよい。様々な信号相関測定が、例えば、上記及び組み込まれた文献に詳述されている。ＤＬＳの相関メトリック及び位相偏移を確認するために使用される信号処理は、信号信頼度メトリックの追加の例である。信号メトリックとしての位相偏移のより詳細については、参照により本明細書に組み込まれる関連する米国特許出願公開第２０１５／００７１５６５号を参照されたい。
【０１８３】
絞り込みの１つ又は複数の反復の後、復号に使用される重み付け及びメッセージシンボル推定値は、絞り込まれたサブブロックから導出されるものである。
【０１８４】
信号信頼度メトリックを説明したので、次にメッセージ抽出をより詳細に説明する。図２３は、メッセージ信号抽出の実装を示す図である。この処理ロジックの設計は、図２１の処理ロジックの設計と類似する。実際、処理ロジックは、処理が並列に実行され同様の動作を共有するように統合されてもよい。或いは、処理は段階的に実行され、潜在的に共通の処理動作を再使用してもよい。図２１と同様に、図２３は、画像ブロック７０２、画像ブロック７０４の幾何変換、及び信号信頼度測定値（例えば、信号信頼度測定値が以前に導出された場所）７０６を格納するメモリユニットを含むメモリ７００を示す。メッセージ抽出７０８の処理ロジックは、メモリインターフェース７１０を介してメモリ７００と対話するが、これは図２１に関して先に略示した代替形態と同様に実装されてもよい。
【０１８５】
ブロック７１２、７１４、７１６、及び７１８のロジックの処理は、図２１のブロック６１２、６１４、６１６、及び６１８のロジックの処理に従う。
【０１８６】
上記において、サブブロックの信号メトリックは、画像ブロックの前置フィルタリングされた画像サンプルに基づいて計算できることを説明した。メッセージ抽出プロセスはまた、処理ロジックブロック７２０として示される前置フィルタを利用する。実際、信号信頼度重みを導出するための前置フィルタは、符号化されたメッセージシンボル推定値を抽出するための前置フィルタと同じであってもよい。この前置フィルタリングの実装形態を、ここでより詳細に説明し例示する。
【０１８７】
図２４は、画像ブロックをフィルタリングする例を強調した、図２２の埋め込み位置に重ねられた画像ブロックの拡大図を示す。図２２では、処理ロジックが、第１の列６４０で埋め込み位置のトラバースを始めることを示したが、図２４は、画像ブロックの処理が、列５（８００）に、特に拡大ドット８０２における埋め込み位置に進んだ例を示す。処理ロジックは、上記のような調整と共に、同期プロセスによって決定されたアフィン変換のベクトル乗算を適用することによって、埋め込み位置を画像内にマッピングする。埋め込み位置のマッピングされた座標（クロスハッチ領域８０４）の４つの隣接画素が画像バッファから取得され内挿されて、埋め込み位置８０２における画像値が決定される。隣接位置の平行移動オフセットを調整した後、ロジックは、より小さい黒点（例えば、埋め込み位置８０２の上の隣接位置では８０６）として示されている４つの隣接位置（埋め込み位置の上、下、左、及び右）について、このプロセスを繰り返す。図２５は、例えば、この隣接位置８０６に対する画像ブロックのサンプリングを示す。
【０１８８】
図２３に戻って、処理ブロック７２０のフィルタは、位置８０２におけるサンプリングされた画像値を隣接位置のサンプリングされた画像値と比較することによって適用される。一実装形態では、この動作は、埋め込み位置８０２における画像サンプルと、左及び右画像サンプルの平均並びに上及び下画像サンプルの平均との比較である。各比較は、より小さい、等しい、又はより大きい場合に対して−１、０、又は１の中間出力を生成する。次いで、中間出力が合計され、フィルタ出力が埋め込み位置の合計に設定される。このプロセスは、ロジックが埋め込み位置をトラバースすると繰り返される。結果は、符号化されたシンボルの推定値であり、抽出されているメッセージの各符号化されたシンボルに対応する別々のアレイに格納される。
【０１８９】
処理ロジック７２２では、これらの符号化されたシンボル推定値が重み付けされる。埋め込み位置についてのフィルタ出力の各々は、対応する重みを有し、埋め込み位置が配置されたサブブロックの信号信頼度メトリックである。これらの重みは、図２１の処理ロジックから生成され、バッファされ、次いで、７２２の処理ロジックにおいてアレイの推定値に適用される。サブブロックに対する重みは、重みにより推定値をスケーリングすることによって、対応する符号化されたシンボル推定値に適用される。
【０１９０】
７２４の処理ロジックは、重み付けされた符号化されたシンボル推定値を復調する。復調器動作の特定の処理は、もちろん、符号化されたシンボルに適用された変調の形態に依存する。アレイにおける各重み付けされたシンボル推定値は、復調された符号化シンボル推定値に寄与することができる信号要素である。例えば、符号化されたシンボルが搬送波上に変調される場合、復調器は、搬送波を利用して、アレイ内の重み付けされた信号要素から符号化されたシンボル推定値を復調する。スペクトラム拡散復調の場合、重み付けされた信号要素はチップ推定値であり、チップの搬送波要素による乗算又は排他的論理和によって復調され、結果はアレイ内の重み付けされた推定値のすべてについて累算される。変調されたシンボルの他の形態は、適用される変調のタイプ及び搬送波信号に従って適切な形式で復調されてもよい。復調の結果は、復調器に入力された重み付けされた信号推定値の累算結果である。この累算結果は、それ自体、メッセージ復号の別の段階（例えば、誤り訂正復号又は重み付け相関復号）のための符号化されたメッセージシンボルの重み付けされた推定値である。
【０１９１】
ブロック７２６の処理ロジックは、復調器により生成された符号化メッセージシンボルの重み付けされた推定値に対してソフト誤り訂正を実行する。上述したように、畳み込み符号、ターボ符号、ブロック符号、ＢＣＨ、リードソロモンなどを含む、いくつかの代替的な誤り訂正復号方法が利用されてもよい。ビタビ復号を利用する畳み込み復号は、重み付けされたメッセージシンボル推定値のソフト復号のための１つの特定の手法であるが、様々な他のソフト復号方式が利用されてもよい。
【０１９２】
信号信頼度メトリックを活用する復号の代替的方法は、重み付け相関を利用することである。この方法では、重み付けメッセージシンボル推定値が、候補メッセージシンボル列のセットのそれぞれと相関付けされる。重みは、本明細書の信号信頼度メトリックを使用して得られる。未知のメッセージシンボルのシーケンスが比較的少数の候補メッセージシンボル列から構成されている適用例を検討する。この場合、候補メッセージシンボル列の期待値が、重み付けされたメッセージシンボル推定値の対応する要素（例えば、復調器からの出力）と直接的に相関付けされるので、誤り訂正復号は必要とされない。相関閾値が候補メッセージ列について確立される。重み付け相関演算出力が閾値を超えると、この候補列は確実に復号されたと判断される。
【０１９３】
別の最適化は、抽出フィルタにおける既知の透かし信号成分の情報を利用することである。抽出フィルタは、既知のメッセージシンボルが存在する埋め込み位置に隣接する又は重なる点又は領域における未知のメッセージシンボルの抽出のための既知のシンボルを考慮に入れるように構成されてもよい。
【０１９４】
更に説明するために、ここで説明された抽出フィルタの特定の例を使用する。この抽出フィルタは、埋め込み位置の３×３領域上で動作して、中央位置の未知のメッセージシンボル値の推定値を計算する。１つの最適化は、推定値及び期待値に基づいて中心位置の周りのサンプリングされた値に重み付けを適用するようにフィルタを構成することである。
【０１９５】
フィルタ動作は、検査されている画像ブロック上の複数のパスで実行される。第１のパスでは、抽出ロジックが、既知のメッセージシンボルの信号強度値の尺度を導出する。抽出ロジックは、そのことを、例えば、ブロック内の既知のメッセージシンボルの位置における期待値及び測定値を相関付けることによって行う。例えば、既知のメッセージシンボル値は、正又は負の調整に単純化されてもよい期待値を有する。既知のメッセージシンボルの期待符号は、信号信頼度メトリックを提供するために、領域内の既知のシンボルのすべての埋め込み位置（例えば、対象の埋め込み位置のブロック又はサブブロック内）についてのフィルタ出力と相関付けされる。
【０１９６】
次に、抽出ロジックは、未知のメッセージシンボルの推定値を決定し、ここで、抽出フィルタは、隣接する又は重なる既知のメッセージ信号の信号信頼度メトリックによって重み付けされた入力点を有する。
【０１９７】
このプロセスは、信頼度が改善されたかどうかを決定するために、各パスがブロック又はサブブロックの信頼度メトリックを計算することで反復されてもよい。反復の限界に達する、信号信頼度メトリックが改善されない、又はメッセージが首尾よく復号されるまで、処理が継続する。許容できる信頼度メトリックが達成された場合、抽出ロジックは、メッセージ復号段階に進み、試行復号が試みられ、復号の出力が妥当性について（例えば、ＣＲＣのような誤り検出ビットを介して）検査される。
【０１９８】
この最適化は、平行移動調整とのアライメントを絞り込むための上記方法に統合されてもよい。これら２つの手法は、既知のシンボルを信号信頼度のメトリックとして利用するので、互いに互換性がある。
【０１９９】
加えて、未知のメッセージシンボルが確実に復号されるので、抽出プロセスは、それらをブロック内の埋め込み位置で現在既知のシンボルの期待値に変換する。これらの既知のメッセージシンボルは、後続のパスにおける未知のシンボルの復号に重み付けするための信号信頼度メトリックを導出するために使用することができる。期待値への変換は、未知のシンボルのシーケンスを復号し、復号されたシンボルの期待値を生成することによって達成することができる。復号は、誤り訂正復号又は重み付け相関復号であってもよい。復号されると、復号されたメッセージからメッセージシンボルの期待値が生成される。期待値のこの生成は、未知のシンボルを符号化するために使用される符号化方法（例えば、ブロック内の埋め込み位置に符号化メッセージシンボルを作成するための搬送波に対する誤り訂正符号化及び／又は変調）に従う。
【０２００】
初期の検出器段階によって推定された変換におけるわずかなアフィン変換誤差により、抽出フィルタのサンプル点の初期アライメントは通常、わずかにずれる。したがって、サンプリング中、抽出フィルタ入力サンプルの３×３領域の一部又はすべてが、隣接埋め込み位置のメッセージシンボル内容をより多く含む。これらの隣接位置に既知の期待値がある場合、これらのサンプル位置についての抽出フィルタ入力は、隣接値の寄与を低減又はオフセットするように重み付けされる。
【０２０１】
或いは、３ｘ３画像近傍全体（又は、画像解像度に応じてより大きい若しくはサブサンプリングされた領域）が、既知のメッセージシンボル値及び正又は負の両方の未知のメッセージシンボル値を含む推定された近傍と相関付けされる。最良の相関が保持され、画像ブロックに対して再度反復するために使用され、そこでは、既知の値が２番目以降のパスについて既知のメッセージ値と共に以前に未知の値に代わる。
【０２０２】
本出願人による他の特許文献は、本構成と併せて使用されうる（及び本構成が組み込まれうる）追加の透かし技術を詳述する。例として、以下の特許、出願公開、及び同時係属出願を含む：２０１４年１０月２１日に出願された第１４／５２０，１６０号（米国特許出願公開第２０１５／０１０６４１６号として公開）、及び２０１５年１月１２日に出願された第６２／１０２，５４７号（例えば、位相推定の関連する教示を与える；現在、米国特許出願公開第２０１６／０１８８９７２号として公開）；第７，０７２，４８７号（例えば、透かし検出器によって利用される色ベクトルの適応について教示を与える）；第７，２３１，０６１号（例えば、前置フィルタリング動作を含む適応予測フィルタリングを教示する）；第７，０７６，０８２号（例えば、前置フィルタリングのルックアップベースの実装を説明する）；第２０１２／０１２９５７４号（例えば、適応信号検出を使用する不利な照明における透かし検出を説明する）；第６，９８８，２０２号（例えば、透かし信号対ノイズ比を増大する前置フィルタリングについてより詳細を示す）；第７，９７８，８７５号、第７，５７４，０１４号、第７，０１３，０２１号及び第６，４４２，２８４号（例えば、被疑画像におけるブロック選択、すなわち、復号可能な透かしデータを有する可能性が最も高い画像の領域を識別することを説明する）；第６，５１６，０７９号（例えば、透かし検出器の段階を制御するための検出閾値を決定する）；第８，８９１，８１１号（例えば画像ブロックトラバース及び選択戦略）；第２０１２／０２１４５１５号（例えばオーディオ透かし）；２０１５年５月２９日に出願された第１４／７２５，３９９号（例えば、スパースデータ信号埋め込み構成を詳述する）；２０１５年５月２８日に出願された第１４／７２４，７２９号（例えば、様々な同期及び変調技法を教示する）；並びに第６，９７５，７４５号（例えば、ローカルブロック相関に基づく推定の絞り込み；位相ロック）。
【０２０３】
上記の技術を実装するためのコンピューティング及びハードウェアアーキテクチャのより詳細については、参照により本明細書に組み込まれる２０１５年７月２日に出願された同時係属米国特許仮出願第６２／１８８，４４０号、及び２０１５年９月１日に出願された対応する非仮出願の米国特許出願第１４／８４２，５７５号、名称「ＨＡＲＤＷＡＲＥ−ＡＤＡＰＴＡＢＬＥ  ＷＡＴＥＲＭＡＲＫ  ＳＹＳＴＥＭＳ」を参照されたい。
【０２０４】
上記最小二乗法、位相推定、及び位相偏移法は、マイクロプロセッサ、ＡＳＩＣ（特定用途向け集積回路）及びＦＰＧＡ（フィールドプログラマブルゲートアレイ）を含む種々の異なるハードウェア構造によって実行されうる。再構成可能なハードウェア及びＡＳＩＰなど、そのような構成のハイブリッドも使用されうる。
【０２０５】
マイクロプロセッサによって、出願人は、固定バス相互接続によってリンクされる、整数及び浮動小数点の両方の算術論理ユニット（ＡＬＵ）、制御ロジック、レジスタの集合、及びスクラッチパッドメモリ（例えばキャッシュメモリ）を含む、特定の構造、すなわち多目的クロック駆動集積回路を意味する。制御ロジックは、外部メモリから命令コードをフェッチし、ＡＬＵが命令コードを実行するのに必要な一連の動作を開始する。命令コードは、マイクロプロセッサのネイティブ命令セットとして考えられうる限定された命令語彙から引き出される。
【０２０６】
マイクロプロセッサ上の上記に詳述された方法の特定の実装は、ＭａｔＬａｂ又はＣ＋＋（ソースコードと呼ばれることがある）などの高水準コンピュータ言語におけるアルゴリズム演算のシーケンスをまず定義し、次いで市販のコンパイラ（例えば、インテルＣ＋＋コンパイラなど）を使用して、ソースコードから機械コード（すなわち、ネイティブ命令セットの命令、オブジェクトコードとも呼ばれることがある）を生成することを含む。本明細書では、ソースコードと機械コードの両方がソフトウェア命令とされる。
【０２０７】
現在、多くのマイクロプロセッサは、いくつかのより単純なマイクロプロセッサ（「コア」と呼ばれる）が合同したものである。そのような構成は、複数の動作が並列に実行されることを可能にする。（いくつかの要素、例えば、バス構造及びキャシュメモリなどがコア間で共有されてもよい。）
【０２０８】
マイクロプロセッサ構造の例には、Ｉｎｔｅｌ  Ｘｅｏｎ、Ａｔｏｍ、Ｃｏｒｅ−Ｉシリーズのデバイスが含まれる。それらの構造は、既成のコンポーネントであるため、用途によっては魅力的な選択肢である。実装するためにカスタム設計／製造を待つ必要がない。
【０２０９】
ＧＰＵ（グラフィックスプロセッシングユニット）は、マイクロプロセッサと密接に関連している。ＧＰＵは、ＡＬＵ、制御ロジック、レジスタ、キャッシュ、及び固定バス相互接続を含む点でマイクロプロセッサに類似している。しかしながら、ＧＰＵのネイティブ命令セットは、大きいデータブロックをメモリとの間で移動し、複数のデータセットに対して同一動作を同時に実行するなど、画像／ビデオ処理タスクのために、一般的に最適化される。頂点データのアレイを異なる座標系に回転及び平行移動すること並びに内挿など、他の特殊なタスクも、一般的にサポートされている。ＧＰＵハードウェアの主要ベンダには、Ｎｖｉｄｉａ、ＡＴＩ／ＡＭＤ、Ｉｎｔｅｌが含まれる。本明細書で使用される場合、出願人は、ＧＰＵも包含するマイクロプロセッサへの言及を意図している。
【０２１０】
マイクロプロセッサは、適切なソフトウェアによって、種々の異なるアルゴリズムを実行するために再プログラムすることができるが、ＡＳＩＣではできない。ＡＳＩＣは、専用のタスクをサービスするように設計及び製造されている。
【０２１１】
ＡＳＩＣ構造は、特定の機能を実行するようにカスタム設計された回路のアレイを備える。２つの一般的なクラス、すなわち、ゲートアレイ（セミカスタムと呼ばれることがある）及びフルカスタムがある。前者では、ハードウェアは、拡散層において作られシリコン基板に散在する（典型的には）数百万のデジタル論理ゲート（例えば、ＸＯＲ及び／又はＡＮＤゲート）の規則的アレイを備える。そして、カスタム相互接続を画定するメタライゼーション層が適用され、固定されたトポロジ内のいくつかのゲートを永続的にリンクする。このハードウェア構造の結果として、製造されたゲートの多く（一般には大半）が通常は使用されないままになる。
【０２１２】
しかしながら、フルカスタムのＡＳＩＣでは、ゲートの配置は、（例えば、指定されたアルゴリズムを実行するために）意図された目的に役立つようにカスタム設計される。カスタム設計は、使用可能な基板スペースをより効率的に使用できるようにし、より短い信号パス及びより高速の性能を可能にする。フルカスタムＡＳＩＣは、アナログ部品及び他の回路を含むようにも製造されうる。
【０２１３】
一般的に言えば、詳述されたアルゴリズム（及びそれに準じる他のもの）のＡＳＩＣベースの実装は、マイクロプロセッサを利用する実装よりも、高い性能を提供し、消費電力が小さい。しかしながら、欠点は、特定の１用途に合わせて作られた回路を設計及び製造するために必要とされるかなりの時間及び費用である。
【０２１４】
ＡＳＩＣを使用する上記に詳述された方法の特定の実装は、ＭａｔＬａｂ又はＣ＋＋などのソースコードにおけるアルゴリズム演算のシーケンスをやはり定義することで始まる。しかしながら、多目的マイクロプロセッサのネイティブ命令セットをコンパイルする代わりに、ソースコードは、ＨＤＬＣｏｄｅｒ（ＭａｔｈＷｏｒｋｓから入手可能）などのコンパイラを使用して、ＶＨＤＬ（ＩＥＥＥ標準）などの「ハードウェア記述言語」にコンパイルされる。次いで、ＶＨＤＬ出力は、ＳｙｎｏｐｓｉｓによるＤｅｓｉｇｎ  Ｃｏｍｐｉｌｅｒ、Ｍｅｎｔｏｒ  ＧｒａｐｈｉｃｓによるＨＤＬ  Ｄｅｓｉｇｎｅｒ、又はＣａｄｅｎｃｅ  Ｄｅｓｉｇｎ  ＳｙｓｔｅｍｓによるＥｎｃｏｕｎｔｅｒ  ＲＴＬ  Ｃｏｍｐｉｌｅｒなどのハードウェア合成プログラムに適用される。ハードウェア合成プログラムは、その目的に専用の特殊用途マシンとして、ハードウェア形態でテクノロジを実現する電子論理ゲートの特定のアレイを指定する出力データを提供する。次いで、この出力データは半導体製造業者に提供され、半導体製造業者はこの出力データを使用してカスタマイズされたシリコン部品を製造する。（適した業者には、ＴＳＭＣ、Ｇｌｏｂａｌ  Ｆｏｕｎｄｒｉｅｓ、ＯＮ  Ｓｅｍｉｃｏｎｄｕｃｔｏｒｓが含まれる。）
【０２１５】
上記に詳述された方法を実行するために使用できる第３のハードウェア構造は、ＦＰＧＡである。ＦＰＧＡは、上記に論じられたセミカスタムゲートアレイの親類である。しかしながら、メタライゼーション層を使用してゲートの一般的アレイの間の固定された相互接続を画定する代わりに、相互接続は、オン又はオフのいずれかであるように電気的に構成（及び再構成）されうるスイッチのネットワークによって画定される。構成データは、外部メモリに格納され、外部メモリから読み取られる。そのような構成により、メモリからの異なる構成命令をロードすることによって、論理ゲートのリンク、ひいては回路の機能性を変更することができ、これらの相互接続スイッチがどのように設定されるかを再構成する。
【０２１６】
また、ＦＰＧＡは、一般的に単純なゲートで全体的に構成されていない点で、セミカスタムゲートアレイとは異なる。代わりに、ＦＰＧＡは、複雑な組み合わせの機能を実行するように構成されたいくつかの論理要素を含むことができる。また、メモリ要素（例えば、フリップフロップ、より典型的にはＲＡＭメモリの完全なブロック）も含まれうる。同様に、Ａ／Ｄ及びＤ／Ａ変換器も有する。やはり、ＦＰＧＡを特徴付ける再構成可能な相互接続は、そのような追加要素をより大きい回路内の所望の位置に組み込むことを可能にする。
【０２１７】
ＦＰＧＡ構造の例には、Ａｌｔｅｒａ（現Ｉｎｔｅｌ）のＳｔｒａｔｉｘ  ＦＰＧＡ、ＸｉｌｉｎｘのＳｐａｒｔａｎ  ＦＰＧＡが含まれる。
【０２１８】
他のハードウェア構造と同様に、ＦＰＧＡ上での上記方法の実装は、高水準言語でアルゴリズムをオーサリングすることから始まる。ＡＳＩＣの実装と同様に、次に、高水準言語がＶＨＤＬにコンパイルされる。しかし、次いで、相互接続構成命令が、使用されているＦＰＧＡファミリに特有のソフトウェアツール（例えば、Ｓｔｒａｔｉｘ／Ｓｐａｒｔａｎ）によってＶＨＤＬから生成される。
【０２１９】
上述の構造のハイブリッドも上記方法を実施するために使用することができる。ＡＳＩＣのコンポーネントとして基板上に集積されるマイクロプロセッサを利用する。そのような構成は、システムオンチップ（ＳＯＣ）と呼ばれる。同様に、マイクロプロセッサは、ＦＰＧＡにおける他の要素との再構成可能な相互接続に利用可能な要素のうちの１つとすることができる。そのような構成は、システムオンプログラマブルチップ（Ｓｙｓｔｅｍ  ｏｎ  ａ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｃｈｉｐ：ＳＯＲＣ）と呼ばれることがある。
【０２２０】
出願人による、再構成可能なハードウェアと呼ばれる別のハイブリッド手法は、１つ又は複数のＡＳＩＣ要素を利用する。しかしながら、ＡＳＩＣ動作の特定の態様は、１つ又は複数のメモリに格納されたパラメータによって再構成されうる。例えば、参照信号及び変換シード候補は、書き換え可能メモリに格納されたパラメータによって定義されうる。そのような構成によって、同じＡＳＩＣが、異なる参照信号及び関連する変換パラメータを利用する２つの異なるデバイスに組み込まれてもよい。１つは、第１の参照信号を探す、食料品包装内に隠された透かし符号化された商品識別子を読み取るためのＰＯＳスキャナであってもよい。第２は、異なる周波数位置で異なる位相を持つ周波数成分を有する第２の参照信号を探す、運転免許証に隠された透かし符号化された生年月日情報を読み取るための年齢確認端末であってもよい。これらのチップすべては単一の半導体工場で同一に製造されるが、オンチップメモリに格納された参照信号及び透かしキーパラメータによって、チップの最終使用時に区別される。
【０２２１】
更に別のハイブリッド手法では、アプリケーション特有の命令セットプロセッサ（ＡＳＩＰＳ）を利用する。ＡＳＩＰＳは、マイクロプロセッサであると考えることができる。しかしながら、多目的ネイティブ命令セットを有する代わりに、命令セットは、製造前の設計段階で特定の意図された使用に適合される。したがって、ＡＳＩＰは、ＦＦＴ変換、対数極座標（ｌｏｇ−ｐｏｌａｒ）サンプリング、マッチドフィルタリング、及び相関のうちの一部又は全部に関連付けられた動作に役立つネイティブ命令を含むように設計されてもよい。しかしながら、そのようなネイティブ命令は、より汎用なマイクロプロセッサで利用可能な命令のいくつかを欠くことになる。
【０２２２】
（再構成可能なハードウェア及びＡＳＩＰ構成は、２０１５年９月１日に出願された米国特許出願第１４／８４２，５７５号に更に詳述されており、その開示は参照により本明細書に組み込まれる。）
【０２２３】
実施形態の例
この節は、本明細書に説明された技術の様々な本発明の構成の例を示す。
【０２２４】
Ａ１．画像信号の幾何変換を決定するためのシステムであって、
参照信号と参照信号を含む画像とが格納されたメモリと、
プログラムされたプロセッサと、
を備え、
プログラムされたプロセッサは、命令を実行して、
幾何変換を参照信号の成分に適用することによって成分を変換することであって、幾何変換が、変換候補シードから始まり、変換候補シードが、回転角、スケール、せん断、及び差分スケールパラメータを含む、変換することと、
変換された参照信号成分と画像との間の相関を計算することと、
画像をサンプリングして、変換された成分に隣接する新しい位置を決定することと、
参照信号の成分を新しい位置に変換する最小二乗変換を決定することによって、幾何変換を更新することと、
画像と更新された幾何変換により変換された成分との間の相関に基づいて、更新された変換を評価することと、
画像と更新された幾何変換により変換された成分との間の相関に基づいて、幾何変換を絞り込むようにサンプリング及び更新をするために、命令の実行を繰り返すことと、
を行う、システム。
【０２２５】
Ａ２．画像信号の幾何変換を決定するためのデジタル論理回路であって、
参照信号と参照信号を含む画像とが格納されたメモリと、
幾何変換を参照信号の成分に適用することによって参照信号の成分を変換するための変換ロジックであって、幾何変換が、変換候補シードから始まり、変換候補シードが、回転角、スケール、せん断、及び差分スケールパラメータを含む、変換ロジックと、
変換された参照信号成分と画像との間の相関を計算するための相関ロジックと、
画像をサンプリングして、変換された成分に隣接する新しい位置を決定するためのサンプリングロジックと、
参照信号の成分を新しい位置に変換する最小二乗変換を決定することによって、幾何変換を更新するための更新ロジックと、
画像と更新された幾何変換により変換された成分との間の相関に基づいて、変換、相関、サンプリング、及び更新ロジックの処理の反復を制御するためのロジックと、
を備えるデジタル論理回路。
【０２２６】
Ａ３．画像内に符号化されたデジタルデータからのデジタルメッセージ抽出のための方法であって、
電子メモリから、画像ブロックからの画像サンプルと、画像ブロックの画像サンプル内に符号化されたデジタルデータの埋め込み位置の幾何変換を近似する幾何変換パラメータとを取得するステップと、
プロセッサにおいて命令を実行して、
画像ブロックのサブブロック内の参照信号の信号信頼度の尺度を取得することであって、幾何変換パラメータが、埋め込み位置とサブブロックとの間の幾何変換を用意するために適用される、取得することと、
画像ブロックのサブブロックの埋め込み位置からメッセージ推定値を抽出することと、
メッセージ推定値を、メッセージ推定値が抽出されたサブブロックの信号信頼度によって重み付けすることと、
重み付けされたメッセージ推定値からメッセージを復号することと、
を行う、ステップと、
を含む方法。
【０２２７】
Ａ４．画像内に符号化されたデジタルデータからのデジタルメッセージ抽出のためのデジタル論理回路であって、
画像の埋め込み位置の座標と画像ブロックとの間の変換を決定するための座標変換ロジックであって、埋め込み位置と画像ブロックとの間の変換を近似する幾何変換を適用する座標変換ロジックと、
変換に基づいて画像ブロックをサンプリングするためのサンプリングロジックと、
画像ブロックのサブブロックのサンプルと参照信号との間の相関を決定するための相関ロジックであって、相関が、サブブロックについての信号信頼度メトリックを用意する、相関ロジックと、
サブブロック内の埋め込み位置からメッセージ推定値を抽出するためのメッセージ推定値抽出ロジックと、
サブブロック内の埋め込み位置のメッセージ推定値に対する重みとして、信号信頼度メトリックを適用するための重み付けロジックと、
重み付けされたメッセージ推定値からメッセージシンボルを復号するための復号ロジックと、
を備えるデジタル論理回路。
【０２２８】
結語
具体的な実装形態を参照して本技術の原理を説明し例示したが、本技術は、多くの他の異なる形態で実装可能であることが理解されよう。明細書を過度に長くせずに包括的な開示を行うために、出願人は、上記に参照した特許及び特許出願を参照により組み込む。
【０２２９】
上述の方法、プロセス、及びシステムは、ハードウェア、ソフトウェア、又はハードウェア及びソフトウェアの組み合わせで実装することができる。例えば、ＤＬＳ、位相推定、及び位相偏移のための信号処理動作は、メモリに格納された命令として実装され、プログラマブルコンピュータ（ソフトウェア及びファームウェア命令の両方を含む）で実行され、専用デジタル回路内のデジタル論理回路、又は１つ若しくは複数のプロセッサ及びデジタル論理回路モジュールで実行される命令の組み合わせとして実装されてもよい。前述の方法及びプロセスは、システムのメモリ（電子、光、又は磁気ストレージデバイスなどのコンピュータ可読媒体）から実行されるプログラムに実装可能である。方法、命令、及び回路は、電子信号又は他の電磁形状の信号に基づいて動作する。これらの信号は更に、画像センサに取り込まれた画像信号のような物理信号、音声センサに取り込まれた音声、及び他のタイプのためのセンサに取り込まれた他の物理信号タイプを表す。これらの電磁信号表現は、信号間の線形変換、位相シフト、及び平行移動を決定するように、上述のような異なる状態に変換される。
【０２３０】
上記の方法、命令、及びハードウェアは、参照及び被疑信号成分に基づいて動作する。信号を基底関数に投影することによって形成される信号成分の合計として信号を表すことができるので、上記の方法は、一般に様々な信号タイプに適用される。例えば、フーリエ変換は、基底関数のセットへの信号の投影の合計として信号を表す。
【０２３１】
上述の実施形態における要素及び特徴の特定の組み合わせは例示に過ぎず、これらの教示と本明細書及び参照により組み込まれた特許／出願における他の教示との交換及び置換も考えられる。
［発明の項目］
［項目１］
デジタルデータを抽出するために画像内の参照信号の幾何変換を決定する方法であって、
プログラムされたプロセッサ又はデジタル論理回路を用いて、
前記画像を周波数領域に変換して、整数座標において前記画像の離散周波数領域表現を生成するステップと、
点広がり関数に従って、前記画像の前記離散周波数領域表現内の非整数座標における位相を推定するステップと、
参照信号の複数の参照信号成分について、
候補幾何変換に従って、参照信号成分の座標を変換するステップ、及び
前記参照信号成分の前記座標を、前記変換された参照信号成分の前記座標のあたりの前記離散周波数領域表現の近傍内の位置へ更新するステップであって、前記位置が、前記近傍内の周波数振幅の最も高い周波数振幅に対応し、前記近傍における非整数位置での振幅値が、非整数位置において推定された前記位相を使用して計算される、当該ステップと、
前記参照信号成分を前記更新された座標に変換する新しい幾何変換を決定するステップと、
前記新しい幾何変換を適用して、符号化されたデジタルデータを前記画像から抽出するステップと、
を含む方法。
［項目２］
非整数座標における位相を推定するステップが、点広がり関数から取得された重みを整数位置での隣接複素周波数成分に適用することによって、前記非整数座標における複素周波数成分を推定することを含み、
前記近傍内の前記周波数振幅が、前記近傍における前記複素周波数成分の振幅である、項目１に記載の方法。
［項目３］
前記参照信号成分が、前記周波数領域におけるピークを含む、項目１に記載の方法。
［項目４］
前記参照信号成分が、正弦曲線を含む、項目１に記載の方法。
［項目５］
前記新しい幾何変換を適用して画像ブロックの幾何歪みを近似することに基づいて、前記画像ブロックにおける参照信号についての信号信頼度メトリックを決定するステップと、
前記信号信頼度メトリックによって、前記画像ブロックから抽出されたデジタルメッセージ要素を重み付けするステップと、
を含む、項目１に記載の方法。
［項目６］
幾何変換候補について、前記変換、及び前記複数の参照信号成分のより低い周波数サブセットとの相関の前記測定を行って、更なる絞り込みのための前記幾何変換候補のサブセットを決定するステップと、
複数の絞り込み段階において、前記幾何変換候補の前記サブセットに対して、前記変換、相関の前記測定、座標の前記更新、及び新しい幾何変換の前記決定を行うステップと、
を含む、項目１に記載の方法。
［項目７］
１つ又は複数のプロセッサ上で命令を実行して、変換、測定、更新、前記新しい幾何変換を決定すること、及び前記新しい幾何変換を適用することの動作を実行するステップを含む、項目１に記載の方法。
［項目８］
専用デジタル論理回路において、変換、測定、更新、前記新しい幾何変換を決定すること、及び前記新しい幾何変換を適用することの動作を行うステップを含む、項目１に記載の方法。
［項目９］
命令が格納された非一過性のコンピュータ可読媒体であって、前記命令がプロセッサによって実行されたとき、デジタルデータを抽出するために画像内の参照信号の幾何変換を決定する方法を実施し、前記方法が、
前記画像を周波数領域に変換して、整数座標において前記画像の離散周波数領域表現を生成するステップと、
点広がり関数に従って、前記画像の前記離散周波数領域表現内の非整数座標における位相を推定するステップと、
参照信号の複数の参照信号成分について、
候補幾何変換に従って、参照信号成分の座標を変換するステップ、及び
前記参照信号成分の前記座標を、前記変換された参照信号成分の前記座標のあたりの前記離散周波数領域表現の近傍内の位置へ更新するステップであって、前記位置が、前記近傍内の周波数振幅の最も高い周波数振幅に対応し、前記近傍における非整数位置での振幅値が、非整数位置において推定された前記位相を使用して計算される、当該ステップと、
前記参照信号成分を前記更新された座標に変換する新しい幾何変換を決定するステップと、
前記新しい幾何変換を適用して、符号化されたデジタルデータを前記画像から抽出するステップと、
を含む、非一過性のコンピュータ可読媒体。
［項目１０］
デジタルデータ抽出のための装置であって、
画像センサと、
前記画像センサにより取り込まれた画像、及びソフトウェア命令を格納するためのメモリと、
前記メモリに結合された１つ又は複数のプロセッサと、
を備え、
前記１つ又は複数のプロセッサが、前記ソフトウェア命令を実行して、
幾何変換候補を参照信号成分に適用して、変換された座標を取得することと、
前記変換された参照信号成分の前記座標のあたりの近傍内の前記参照信号成分の新しい座標を、前記近傍内の最も高い周波数振幅を突き止めることによって決定することであって、前記近傍における非整数位置での振幅が、点広がり関数に従う整数位置での周波数成分の重み付けに基づいて取得される、当該決定することと、
前記参照信号を前記新しい座標に適合させる新しい幾何変換を計算することと、
前記新しい幾何変換を用いて決定された位置で前記画像から符号化されたデジタルデータを抽出することと、
を行うように構成されている、装置。
［項目１１］
デジタルデータを抽出するために画像内の参照信号の幾何変換を決定する方法であって、
プログラムされたプロセッサ又はデジタル論理回路を用いて、
参照信号の複数の参照信号成分について、
候補幾何変換に従って、参照信号成分の座標を変換するステップ、
前記変換された参照信号成分と前記画像との間の相関を測定するステップであって、前記相関が、前記変換された参照信号成分の前記座標のあたりの隣接整数座標における前記画像の周波数領域変換の複素成分の組み合わせを含み、前記複素組み合わせが、前記隣接座標における位相関係に従って複素成分を組み合わせる、当該ステップ、及び
前記参照信号成分の前記座標を、前記変換された参照信号成分の前記座標のあたりの近傍内の位置へ更新するステップと、
前記参照信号成分を前記更新された座標に変換する新しい幾何変換を決定するステップと、
前記新しい幾何変換を適用して、符号化されたデジタルデータを前記画像から抽出するステップと、
を含む方法。
［項目１２］
前記位相関係が、右上隣接要素と左下隣接要素とで位相がマッチすること、及び左上と右下とで位相がマッチすることを含み、前記右上と前記左上との位相が１８０度異なる、項目１１に記載の方法。
［項目１３］
前記位相関係が、点広がり関数に従って隣接座標に重み付けすることを含む、項目１１に記載の方法。
［項目１４］
前記参照信号成分が、正弦曲線を含む、項目１１に記載の方法。
［項目１５］
前記新しい幾何変換を適用して画像ブロックの幾何歪みを近似することに基づいて、前記画像ブロックにおける参照信号についての信号信頼度メトリックを決定するステップと、
前記信号信頼度メトリックによって、前記画像ブロックから抽出されたデジタルメッセージ要素を重み付けするステップと、
を含む、項目１１に記載の方法。
［項目１６］
幾何変換候補について、前記変換、及び前記複数の参照信号成分のより低い周波数サブセットとの相関の前記測定を行って、絞り込むために前記幾何変換候補のサブセットを決定するステップと、
複数の絞り込み段階において、前記幾何変換候補の前記サブセットに対して、前記変換、相関の前記測定、座標の前記更新、及び新しい幾何変換の前記決定を行うステップと、
を含む、項目１１に記載の方法。
［項目１７］
１つ又は複数のプロセッサ上で命令を実行して、変換、測定、更新、前記新しい幾何変換を決定すること、及び前記新しい幾何変換を適用することの動作を実行するステップを含む、項目１１に記載の方法。
［項目１８］
専用デジタル論理回路において、変換、測定、更新、前記新しい幾何変換を決定すること、及び前記新しい幾何変換を適用することの動作を行うステップを含む、項目１１に記載の方法。
［項目１９］
命令が格納された非一過性のコンピュータ可読媒体であって、前記命令がプロセッサによって実行されたとき、デジタルデータを抽出するために画像内の参照信号の幾何変換を決定する方法を実施し、前記方法が、
参照信号の複数の参照信号成分について、
候補幾何変換に従って、参照信号成分の座標を変換するステップ、
前記変換された参照信号成分と前記画像との間の相関を測定するステップであって、前記相関が、前記変換された参照信号成分の前記座標のあたりの隣接整数座標における前記画像の周波数領域変換の複素成分の組み合わせを含み、前記複素組み合わせが、前記隣接座標における位相関係に従って複素成分を組み合わせる、当該ステップ、及び
前記参照信号成分の前記座標を、前記変換された参照信号成分の前記座標のあたりの近傍内の位置へ更新するステップと、
前記参照信号成分を前記更新された座標に変換する新しい幾何変換を決定するステップと、
前記新しい幾何変換を適用して、符号化されたデジタルデータを前記画像から抽出するステップと、
を含む、非一過性のコンピュータ可読媒体。
［項目２０］
デジタルデータ抽出のための装置であって、
画像センサと、
前記画像センサにより取り込まれた画像、及びソフトウェア命令を格納するためのメモリと、
前記メモリに結合された１つ又は複数のプロセッサと、
を備え、
前記１つ又は複数のプロセッサが、前記ソフトウェア命令を実行して、
幾何変換候補を参照信号成分に適用して、変換された座標を取得することと、
前記変換された参照信号成分についての相関メトリックを計算することであって、前記相関メトリックが、隣接座標における位相関係に従って、前記変換された座標の隣接座標における前記画像の周波数成分を組み合わせる、当該計算することと、
前記変換された参照信号成分の前記座標あたりの近傍内に前記参照信号成分の新しい座標を決定することと、
前記参照信号を前記新しい座標に適合させる新しい幾何変換を計算することと、
前記新しい幾何変換を用いて決定された位置で前記画像から符号化されたデジタルデータを抽出することと、
を行うように構成されている、装置。
［項目２１］
デジタルデータを抽出するために画像内の参照信号の幾何変換を決定する方法であって、
プログラムされたプロセッサ又はデジタル論理回路を用いて、
参照信号の複数の参照信号成分について、
候補幾何変換に従って、参照信号成分の座標を変換するステップ、
前記変換された参照信号成分と前記画像との間の相関を測定するステップ、及び
前記参照信号成分の前記座標を、前記変換された参照信号成分の前記座標のあたりの近傍内の位置へ更新するステップと、
前記参照信号成分を前記更新された座標に変換する新しい幾何変換を決定するステップと、
前記新しい幾何変換を適用して、符号化されたデジタルデータを前記画像から抽出するステップと、
幾何変換候補について、前記変換、及び前記複数の参照信号成分のより低い周波数サブセットとの相関の前記測定を行って、絞り込むために前記幾何変換候補のサブセットを決定するステップと、
複数の絞り込み段階において、前記幾何変換候補の前記サブセットに対して、前記変換、相関の前記測定、座標の前記更新、及び新しい幾何変換の前記決定を行うステップと、
を含む方法。
［項目２２］
前記相関が、前記複数の絞り込み段階における絞り込みのために幾何変換候補を選択するために評価される、項目２１に記載の方法。
［項目２３］
前記参照信号成分が、周波数領域におけるピークを含む、項目２１に記載の方法。
［項目２４］
前記参照信号成分が、正弦曲線を含む、項目２１に記載の方法。
［項目２５］
前記新しい幾何変換を適用して画像ブロックの幾何歪みを近似することに基づいて、前記画像ブロックにおける参照信号についての信号信頼度メトリックを決定するステップと、
前記信号信頼度メトリックによって、前記画像ブロックから抽出されたデジタルメッセージ要素を重み付けするステップと、
を含む、項目２１に記載の方法。
［項目２６］
１つ又は複数のプロセッサ上で命令を実行して、変換、測定、更新、前記新しい幾何変換を決定すること、及び前記新しい幾何変換を適用することの動作を実行するステップを含む、項目２１に記載の方法。
［項目２７］
専用デジタル論理回路において、変換、測定、更新、前記新しい幾何変換を決定すること、及び前記新しい幾何変換を適用することの動作を行うステップを含む、項目２１に記載の方法。
［項目２８］
命令が格納された非一過性のコンピュータ可読媒体であって、前記命令がプロセッサによって実行されたとき、デジタルデータを抽出するために画像内の参照信号の幾何変換を決定する方法を実施し、前記方法が、
参照信号の複数の参照信号成分について、
候補幾何変換に従って、参照信号成分の座標を変換するステップ、
前記変換された参照信号成分と前記画像との間の相関を測定するステップであって、前記相関が、前記変換された参照信号成分の前記座標のあたりの隣接整数座標における前記画像の周波数領域変換の複素成分の組み合わせを含み、前記複素組み合わせが、前記隣接座標における参照信号成分の位相関係に従って複素成分を組み合わせる、当該ステップ、及び
前記参照信号成分の前記座標を、前記変換された参照信号成分の前記座標のあたりの近傍内の位置へ更新するステップと、
前記参照信号成分を前記更新された座標に変換する新しい幾何変換を決定するステップと、
前記新しい幾何変換を適用して、符号化されたデジタルデータを前記画像から抽出するステップと、
を含む、非一過性のコンピュータ可読媒体。
［項目２９］
デジタルデータ抽出のための装置であって、
画像センサと、
前記画像センサにより取り込まれた画像、及びソフトウェア命令を格納するためのメモリと、
前記メモリに結合された１つ又は複数のプロセッサと、
を備え、
前記１つ又は複数のプロセッサが、前記ソフトウェア命令を実行して、
幾何変換候補を参照信号成分に適用して、変換された座標を取得することと、
前記変換された参照信号成分についての相関メトリックを計算することであって、前記相関メトリックが、参照信号成分の位相関係に従って、前記変換された座標の隣接座標における前記画像の周波数成分を組み合わせる、当該計算することと、
前記変換された参照信号成分の前記座標あたりの近傍内に前記参照信号成分の新しい座標を決定することと、
前記参照信号を前記新しい座標に適合させる新しい幾何変換を計算することと、
前記新しい幾何変換を用いて決定された位置で前記画像から符号化されたデジタルデータを抽出することと、
を行うように構成されている、装置。
［項目３０］
画像信号の幾何変換を決定するためのシステムであって、
参照信号と前記参照信号を含む画像とが格納されたメモリと、
プログラムされたプロセッサと、
を備え、
前記プログラムされたプロセッサは、命令を実行して、
幾何変換を前記参照信号の成分に適用することによって前記成分を変換することであって、前記幾何変換が、変換候補シードから始まり、前記変換候補シードが、回転角、スケール、せん断、及び差分スケールパラメータを含む、当該変換することと、
前記変換された参照信号成分と前記画像との間の相関を計算することと、
前記画像をサンプリングして、前記変換された成分に隣接する新しい位置を決定することと、
前記参照信号の前記成分を前記新しい位置に変換する最小二乗変換を決定することによって、前記幾何変換を更新することと、
前記画像と前記更新された幾何変換により変換された前記成分との間の相関に基づいて、前記更新された変換を評価することと、
前記画像と前記更新された幾何変換により変換された前記成分との間の相関に基づいて、前記幾何変換を絞り込むようにサンプリング及び更新をするために、前記命令の実行を繰り返すことと、
を行う、システム。
［項目３１］
画像信号の幾何変換を決定するためのデジタル論理回路であって、
参照信号と前記参照信号を含む画像とが格納されたメモリと、
幾何変換を前記参照信号の成分に適用することによって前記成分を変換するための変換ロジックであって、前記幾何変換が、変換候補シードから始まり、前記変換候補シードが、回転角、スケール、せん断、及び差分スケールパラメータを含む、当該変換ロジックと、
前記変換された参照信号成分と前記画像との間の相関を計算するための相関ロジックと、
前記画像をサンプリングして、前記変換された成分に隣接する新しい位置を決定するためのサンプリングロジックと、
前記参照信号の前記成分を前記新しい位置に変換する最小二乗変換を決定することによって、前記幾何変換を更新するための更新ロジックと、
前記画像と前記更新された幾何変換により変換された前記成分との間の相関に基づいて、前記変換、相関、サンプリング、及び更新ロジックの処理の反復を制御するためのロジックと、
を備えるデジタル論理回路。
［項目３２］
画像内に符号化されたデジタルデータからのデジタルメッセージ抽出のための方法であって、
電子メモリから、画像ブロックからの画像サンプルと、前記画像ブロックの前記画像サンプル内に符号化された前記デジタルデータの埋め込み位置の幾何変換を近似する幾何変換パラメータとを取得するステップと、
プロセッサにおいて命令を実行して、
前記画像ブロックのサブブロック内の参照信号の信号信頼度の尺度を取得することであって、前記幾何変換パラメータが、前記埋め込み位置と前記サブブロックとの間の幾何変換を用意するために適用される、当該取得することと、
前記画像ブロックの前記サブブロックの埋め込み位置からメッセージ推定値を抽出することと、
前記メッセージ推定値を、前記メッセージ推定値が抽出された前記サブブロックの前記信号信頼度によって重み付けすることと、
前記重み付けされたメッセージ推定値からメッセージを復号することと、
を行う、ステップと、
を含む方法。
［項目３３］
画像内に符号化されたデジタルデータからのデジタルメッセージ抽出のためのデジタル論理回路であって、
前記画像の埋め込み位置の座標と画像ブロックとの間の変換を決定するための座標変換ロジックであって、前記埋め込み位置と前記画像ブロックとの間の変換を近似する幾何変換を適用する当該座標変換ロジックと、
前記変換に基づいて前記画像ブロックをサンプリングするためのサンプリングロジックと、
前記画像ブロックのサブブロックのサンプルと参照信号との間の相関を決定するための相関ロジックであって、前記相関が、前記サブブロックについての信号信頼度メトリックを用意する、当該相関ロジックと、
前記サブブロック内の埋め込み位置からメッセージ推定値を抽出するためのメッセージ推定値抽出ロジックと、
前記サブブロック内の前記埋め込み位置のメッセージ推定値に対する重みとして、前記信号信頼度メトリックを適用するための重み付けロジックと、
前記重み付けされたメッセージ推定値からメッセージシンボルを復号するための復号ロジックと、
を備えるデジタル論理回路。
【図１】
0006741306.tif 000004
【図２】
0006741306.tif 000005
【図３】
0006741306.tif 000006
【図４】
0006741306.tif 000007
【図５】
0006741306.tif 000008
【図６】
0006741306.tif 000009
【図７】
0006741306.tif 000010
【図８】
0006741306.tif 000011
【図９】
0006741306.tif 000012
【図１０】
0006741306.tif 000013
【図１１】
0006741306.tif 000014
【図１２】
0006741306.tif 000015
【図１３】
0006741306.tif 000016
【図１４】
0006741306.tif 000017
【図１５】
0006741306.tif 000018
【図１６】
0006741306.tif 000019
【図１７】
0006741306.tif 000020
【図１８】
0006741306.tif 000021
【図１９】
0006741306.tif 000022
【図２０】
0006741306.tif 000023
【図２１】
0006741306.tif 000024
【図２２】
0006741306.tif 000025
【図２３】
0006741306.tif 000026
【図２４】
0006741306.tif 000027
【図２５】
0006741306.tif 000028
【図２６】
0006741306.tif 000029