(57)【要約】閾値を決定するための方法および装置であって、所望される偽結果確率を選択し、所望される偽結果確率に対応する、閾値テーブルからの閾値を選択することを含むものが記述される。また、所望される偽結果確率に対応する閾値を決定するための方法および装置であって、偽結果確率を計算し、計算された偽結果確率と所望される偽結果確率との間の差の値を計算し、前記差の値を第一の所定の値と比較し、第一の比較工程の結果が正であれば前記差の値を第二の所定の値と比較することを含むものも記載される。
2010529810.tif 000002
【特許請求の範囲】
【請求項１】
閾値を決定する方法であって：
所望される偽結果確率を選択する段階と；
前記所望される偽結果確率に対応する、閾値テーブルからの閾値を選択する段階とを有する、
方法。
【請求項２】
前記閾値テーブルを生成する段階をさらに有する請求項１記載の方法であって、
前記生成する段階がさらに：
前記閾値テーブル中の各偽結果確率エントリーを
【数１】
2010529810.tif 000022
を使って計算する段階と；
前記閾値テーブル中に前記計算された偽結果確率および前記偽結果確率エントリーを計算するのに使われた前記閾値を記憶する段階とを有する、
方法。
【請求項３】
前記計算する段階が、第一の閾値、第二の閾値および閾値きざみを使って、前記第一の閾値を前記閾値きざみだけ逐次的にインクリメントして、前記第一の閾値が前記第二の閾値に等しくなるまで前記閾値テーブルの前記の各偽結果確率エントリーを計算していくことによって実行される、請求項２記載の方法。
【請求項４】
前記偽結果確率が偽陽性確率であり、さらに、前記第一の閾値が偽陰性確率の下限であり、前記第二の閾値が前記偽陽性確率の上限である、請求項３記載の方法。
【請求項５】
前記選択する段階が前記閾値を前記閾値テーブルから取得し、前記閾値が、前記所望される偽結果確率より小さい偽結果確率をもつ最大の閾値である、請求項１記載の方法。
【請求項６】
閾値を決定する方法であって：
所望される偽結果確率を選択する段階と；
偽結果確率を計算する段階と；
前記の計算された偽結果確率と前記の所望される偽結果確率との間の差の値を計算する段階と；
前記差の値を第一の所定の値と比較する段階と；
前記の第一の比較工程の結果が正であれば前記差の値を第二の所定の値と比較する段階とを有する、
方法。
【請求項７】
前記偽結果確率が偽陽性確率である請求項６記載の方法であって、さらに：
第一の閾値を選択する段階と；
前記両方の比較する段階の結果が両方とも正でない場合には前記第一の閾値を修正する段階とを有する、
方法。
【請求項８】
閾値を決定する装置であって：
所望される偽結果確率を選択する手段と；
前記所望される偽結果確率に対応する、閾値テーブルからの閾値を選択する手段とを有する、
装置。
【請求項９】
前記閾値テーブルを生成する手段をさらに有する請求項８記載の装置であって、
前記生成する手段がさらに：
前記閾値テーブル中の各偽結果確率エントリーを
【数２】
2010529810.tif 000023
を使って計算する手段と；
前記閾値テーブル中に前記計算された偽結果確率および前記偽結果確率エントリーを計算するのに使われた前記閾値を記憶する手段とを有する、
装置。
【請求項１０】
前記計算する手段が、第一の閾値、第二の閾値および閾値きざみを使って、前記第一の閾値を前記閾値きざみだけ逐次的にインクリメントして、前記第一の閾値が前記第二の閾値に等しくなるまで前記閾値テーブルの前記の各偽結果確率エントリーを計算していくことによって実行される、請求項９記載の装置。
【請求項１１】
前記偽結果確率が偽陽性確率であり、さらに、前記第一の閾値が偽陰性確率の下限であり、前記第二の閾値が前記偽陽性確率の上限である、請求項１０記載の装置。
【請求項１２】
前記選択する手段が前記閾値を前記閾値テーブルから取得し、前記閾値が、前記所望される偽陽性確率より小さい偽結果確率をもつ最大の閾値である、請求項８記載の装置。
【請求項１３】
所望される偽結果確率に対応する閾値を決定する装置であって：
偽結果確率を計算する手段と；
前記の計算された偽結果確率と前記の所望される偽結果確率との間の差の値を計算する手段と；
前記差の値を第一の所定の値と比較する手段と；
前記の第一の比較工程の結果が正であれば前記差の値を第二の所定の値と比較する手段とを有する、
装置。
【請求項１４】
前記偽結果確率が偽陽性確率である請求項６記載の方法であって、さらに：
第一の閾値を選択する手段と；
前記両方の比較する段階の結果が両方とも正でない場合には前記第一の閾値を修正する段階とを有する、
装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検出閾値を設定することに、特に所望される偽陽性確率が与えられたときに検出閾値を設定することに関する。
【背景技術】
【０００２】
多くの透かしアプリケーションにおいて、透かし〔ウォータマーク〕検出器の偽陽性確率が所与の値未満であることが決定的に重要である。偽陽性は、透かし検出器が透かし入れされていない作品を透かし入れされていると誤って識別するときに起こる。これが重要になるシステムの一例は、ビデオ素材がコピーされるべきではないことをレコーダーまたは記録装置に示すための、ビデオ・コンテンツにおける透かしの使用である。記録の際に偽陽性が起こると、その透かしをモニタリングしている記録装置は、ビデオ・コンテンツがコピーされるべきでないと誤って結論し、記録が停止されることになる。もしこれが結婚式の記録の際に起こると、カメラ製造業者は非常に不幸な新郎新婦に直面することになる。もしこれが人気のある番組のテレビ放送の際に起こると、レコーダー製造業者の多くの顧客が不幸になる。こうして、レコーダー製造業者は典型的には、そのようなコピー・コントロール透かしがハードウェア・コンポーネントの故障の確率に近い偽陽性確率、すなわち109回の検出に１回の誤りから1012回の検出に１回の誤りの範囲の偽陽性確率をもつことを要求してきた。
【０００３】
偽陽性確率の問題をさらに理解するために、図２ａに示される図を考えてみる。図２ａは二つの分布を示している。左側の分布は、透かし検出器が透かしを含まないコンテンツに適用されるときに期待されうる検出値を表す。この分布の平均は0であり、最もしばしば、0に近いことが期待されうる。これは確率曲線であり、よって曲線の下側の面積は1.0に等しい。右側の分布は、検出器が透かし入れされたコンテンツに適用されるときに期待されうる検出値を表す。ここで、平均はMであり、検出値は通例Mに近い。閾値の役割は、これら二つの分布からの標本値の間の区別をすることである。Tとマークされた点にある閾値を考える。検出値がTを超えるときは、そのコンテンツは右側の分布から来ると結論できる。検出値がTを下回るときは、そのコンテンツは左側の分布から来ると結論できる。図２ａから見て取れるように、右側分布からの標本値で閾値Tを下回るものがある。これらは、時に偽陰性と呼ばれる、検出が失敗する透かし入れされた作品である。同様に、左側分布からの標本値で閾値を上回るものがある。これらは、検出器が透かし入れされているとラベル付けするであろう、透かし入れされていない作品である。これらが偽陽性である。
【０００４】
偽陰性の確率は、閾値を下げることによって改善できる。しかしながら、この操作は同時に、偽陽性指示の確率を上げる。図示した例では、二つの分布は重なり合っている。これは、誤りをなくす閾値を選択することはできないということを意味している。多くの透かし入れアプリケーションでは、検出閾値Tはアプリケーション固有の偽陽性確率要件に基づいて選択される。偽陽性確率は透かし埋め込みアルゴリズムとは独立であることを注意しておくべきである。偽陽性確率は単に、左側曲線の閾値Tより大きい部分の下側の面積である。
【０００５】
図２ｂは、閾値の近傍における左側曲線のクローズアップを示している。曲線の閾値Tより大きい部分の下側の面積は網掛けで示されている。この面積が偽陽性確率、つまりマークされていない作品中に透かしが検出される確率を表す。
【０００６】
偽陽性確率要件が与えられたとき、その偽陽性確率要件を満たす最低の閾値を確立するための方法およびシステムをもつことが有利であろう。
【０００７】
本稿での用法では、「／」は同じまたは同様のコンポーネントまたは構造についての代替名を表す。すなわち、本稿での用法では「／」は「または」を意味するものと解釈できる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】M.  L.  Miller  and  J.  A.  Bloom,  "Computing  the  Probability  of  False  Watermark  Detection",  Proceedings  of  the  Third  International  Workshop  on  Information  Hiding,  pp.146-158,  1999
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明は、透かし入れの分野、特にオーディオおよびビデオ・コンテンツのデジタル透かし入れの分野における問題を解決しようとする努力の結果である。
【００１０】
この偽陽性確率は、規格化された相関検出指標（normalized  correlation  detection  measure）を使用する検出器についてよく理解される。しかしながら、透かしの堅牢さを増そうとする努力において、一部の研究者は、複数の規格化された相関を組み合わせる検出指標を提案してきた。一つのそのような指標は、抽出されたベクトルが複数の参照ベクトルと比較されるときの、最大の規格化された相関と二番目に大きなものとの比である。本願の原理は、透かし入れされていない作品の分布についての合理的な想定のもとでの相関比検出指標（correlation  ratio  detection  measure）の偽陽性確率の解析に依拠する。
【００１１】
研究者たちは、検出指標が規格化された相関であるときにこの問題を調査してきた。非特許文献１。検出指標が二つの規格化された相関の比であるときはこの問題についてまだ誰も取り組んでいないと思われる。
【課題を解決するための手段】
【００１２】
そこで、本発明は、検出指標が最大の正規化された相関と二番目に大きい正規化された相関との比であり、所望される偽陽性確率が与えられているときの透かし検出システムにおいて検出閾値を自動的に設定するための方法および対応するシステムに向けられる。本発明は、偽陽性確率（false  positive  probability）に対応する閾値を決定することに関して記述されるが、それに限定されるものではない。本発明の閾値決定方法および装置は、いかなる偽結果確率（false  result  probability）、たとえば偽陰性確率（false  negative  probability）に対応する閾値の決定に使われることもできる。本発明の閾値決定方法は透かし検出に関して説明されるが、医療撮像、画像または音声位置合わせ（registration）、画像または音声認識、パターン認識およびオブジェクト検出・識別および分類の分野など、閾値決定が決定的である他の多くの分野がある。レーダーおよびソナーのシグネチャ解析を含むパターン認識の分野では、「敵味方識別」シナリオにおける閾値決定は、本発明のきわめて決定的な使用の一例である。「敵味方識別」シナリオでは、味方または敵を誤って識別するといういかなるミスも致命的となりうる。
【００１３】
閾値を決定するための方法および装置であって、所望される偽結果確率を選択し、所望される偽結果確率に対応する、閾値テーブルからの閾値を選択することを含むものが記述される。また、所望される偽結果確率に対応する閾値を決定するための方法および装置であって、偽結果確率を計算し、計算された偽結果確率と所望される偽結果確率との間の差の値を計算し、前記差の値を第一の所定の値と比較し、第一の比較工程の結果が正であれば前記差の値を第二の所定の値と比較することを含むものも記載される。
【００１４】
本発明は、付属の図面と併せて読んだときに以下の詳細な説明から最もよく理解される。図面は、下記で簡単に説明する次の図を含む。図面において、諸図における似たような符号は同様の要素を表す。
【図面の簡単な説明】
【００１５】
【図１ａ】m＝2の場合の解析的公式の幾何学的解釈を描いた図である。
【図１ｂ】m＝3の場合の解析的公式の幾何学的解釈を描いた図である。
【図１ｃ】合成ベクトルと解析的公式を使った予測との比較の結果を示す図である。
【図２ａ】二つの分布――マークされた作品とマークされていない作品についての検出値の確率――を示す図である。
【図２ｂ】閾値Tの領域における、図１に描かれたマークされていない作品についての検出値の分布のクローズアップを示す図である。
【図３ａ】本発明の閾値決定方法のある実施形態のフローチャートである。
【図３ｂ】本発明の閾値決定装置またはモジュールのブロック図である。
【図４ａ】本発明の閾値決定方法のある実施形態のフローチャートである。
【図４ｂ】閾値決定装置またはモジュールのブロック図である。
【図５ａ】本発明の閾値決定方法の代替的な実施形態のフローチャートである。
【図５ｂ】本発明の閾値決定装置の代替的な実施形態のブロック図である。
【発明を実施するための形態】
【００１６】
本発明の方法および装置について記述できる前に、数学的基礎を据えておくことが必要である。多くの透かし入れアプリケーションにとっての決定的な問題は、透かし検出器がマークされていない作品を透かし入れされていると誤って識別する確率である。この偽陽性確率は、規格化された相関検出指標（normalized  correlation  detection  measure）を使用する検出器についてよく理解される。しかしながら、透かしの堅牢さを増そうとする努力において、一部の研究者は、複数の規格化された相関を組み合わせる検出指標を提案してきた。一つのそのような指標は、抽出されたベクトルが複数の参照ベクトルと比較されるときの、最大の規格化された相関と二番目に大きなものとの比である。偽陽性確率についての解析的な公式が導出され、経験的データを用いて検証される。相関は、空間領域処理と周波数領域処理を離散フーリエ変換（DFT:  Discrete  Fourier  Transform）を介して関係させる定理をもつ。このように、相関は時間領域または周波数領域において実行できる。相関は、データ・セットの間の類似の度合いを決定するために用いられる。
【００１７】
デジタル透かし入れは、デジタル作品（オーディオ・タイル、スチール画像または画像シーケンスのような）に、その作品についての情報を伝達する目的のために不可視メッセージを埋め込む処理である。用途としては、著作権伝達、コンテンツ認証、偽造抑止または検出、法的追跡および放送モニタリングが含まれる。
【００１８】
最良の設計の透かし入れシステムであっても誤りは避けられない。偽陽性誤りは、透かし検出器が、透かし入れされていない作品中に透かしの存在を示すときに起こる。そのような誤りは、合法的な操作の誤った防止や無実の顧客の訴追につながる。よって、偽陽性は多くの透かし入れアプリケーションにとって決定的な問題となっている。この確率は透かし検出アルゴリズム、検出器が使用される仕方および透かし入れされていない作品の分布に依存する。
【００１９】
偽検出挙動を解析する問題は、透かし文献においてほとんど注目を集めてこなかった。一つの従来技術の方式は、相関ベースの透かし入れ方法における偽陽性確率を予測し、透かしの非白色スペクトルのために画像コンテンツが透かし検出に干渉することを示す。別の従来技術方式は、透かし入れシステムを論じるためのフレームワークにおいて偽検出確率を含める。さらにもう一つの従来技術方式は、規格化相関検出器を使うときの偽陽性確率を計算する精密な方法を提起する。偽陽性確率についての厳密な公式が、透かし入れされていない作品から抽出されるベクトルが放射対称な（radially  symmetric）分布から引かれているという想定のもとで提供される。さらにもう一つの従来技術方式は、網羅的な幾何学的探索における偽陽性確率を研究する。そこでは、透かし検出器における画像および鍵依存性が、複数の幾何学的探索について異なる偽陽性確率につながることが示される。
【００２０】
多くのアプリケーションについて、抽出されるベクトルがいくつかの異なる透かし参照ベクトルと比較される。各参照ベクトルは異なるメッセージ・シンボルと関連付けられている。抽出されたベクトルに対して最高の類似度をもつ参照ベクトルに関連付けられたメッセージ・シンボルが検出されたシンボルとして報告される。検出の確かさは類似の度合いである。最も一般的な類似性指標は規格化された相関（normalized  correlation）である。従来技術の方式の一つの公式を使うことによって、そのアプリケーションの偽陽性確率要件が閾値を設定するために使用できる。検出値がその閾値を超えるとき、シンボルは存在すると報告され、そうでないときは検出器はシンボルなしと報告する。
【００２１】
そのような技法の堅牢さを改善する努力において、一部の研究者は、最大の相関値を二番目に大きい相関値と組み合わせる確度指標（certainty  measure）を提案している。一つのそのようなアプローチは、これらの二つの値の差を前記確度と考え、別のアプローチは二つの値の比を前記確度と考える。いずれの場合にも、偽陽性解析は欠けており、これなしでは、閾値を設定し、フェアな堅牢さ比較を実行するすべはない。本稿では、相関比指標についての偽陽性の確率について解析的公式が導出され、この解析を支持するための経験的データが提示される。
【００２２】
偽透かし検出の確率は、透かし検出器の設計およびそれによって処理される透かし入れされていないコンテンツの分布によって決定される。透かしが埋め込まれていないと想定されるので、埋め込みアルゴリズムはこの確率の計算には重要ではない。
【００２３】
特定的だが典型的な規格化された相関透かし検出器を考える。入力作品はまず、n次元特徴ベクトル（feature  vector）Vを抽出するよう処理される。透かし抽出の例は、周波数変換、ブロック平均、スペクトル整形、白色化およびサブサンプリングのさまざまな組み合わせを含む。これらのプロセスは、堅牢さを増す、信号対雑音比を高める、検出効率を高める、および／または検出指標によって想定される分布を実施する（enforce）ために意図される。
【００２４】
抽出された特徴ベクトルVは次いで一組のn次元参照ベクトル{W1,W2,…,Wm}  m≦nと比較されて、相関比検出指標Dvが得られる。各参照ベクトルは典型的にはm個のメッセージ・シンボルの一つを表し、抽出されたベクトルに最も類似している参照ベクトルに関連付けられたシンボルが報告されるシンボルである。検出指標が検出閾値Tを超えるときにのみ、検出器は陽性検出を報告する。そうでないときは、透かしが検出されたとは報告されない。
【００２５】
検出指標を計算するための厳密な公式は、偽陽性確率の決定に対して決定的である。規格化された相関は、検出指標において用いられる最も一般的な技法の一つである。二つのn次元ベクトルVとWiの間の規格化された相関は
【数１】
2010529810.tif 000003
である。ここで、記号・は内積である。規格化された相関に基づくもう二つの公知の検出指標は、最大の相関と二番目に大きな相関との間の差および最大の相関と二番目に大きな相関との間の比である。
【００２６】
相関比検出指標を考える。m個の参照ベクトルWiすべてについて|CV,Wi|の組が計算される。これらは次いで大きい順にソートされる。
【００２７】
|CV,Wi1|≧|CV,Wi2|≧…≧|CV,Wim|
すると、相関比検出指標は
【数２】
2010529810.tif 000004
と定義され、Dvが検出閾値より大きいとき、Wi1に関連付けられたメッセージ・シンボルが報告される。Dvが常に1以上であることを注意しておく。
【００２８】
次に、相関比検出指標(1)について研究し、偽陽性確率についての解析的公式が導出される。偽陽性確率とはすなわちP(Dv＞T)で、透かし入れされていない作品についてDv＞Tとなる確率である。ここで、Tは検出閾値である。
【００２９】
参照ベクトルの集合{W1,W2,…,Wm}を考える。ここで、|Wi|＝√(Wi・Wi)＝1であり、i≠jについてはWi・Wj＝0である。換言すれば、集合{W1,W2,…,Wm}はm次元ベクトル空間の正規直交基底である。m＜nのときは、この集合は、該集合に、それぞれが他のすべてと直交しかつ{Wi}の各ベクトルと直交するn−m個の単位長さのベクトルを加えることによって、Vおよび{Wi}が存在するn次元ベクトル空間の正規直交基底に拡張できる。n次元での正規直交基底は{W1,W2,…,Wm,em+1,em+2,…,en}と表される。
【００３０】
線形代数において、内積空間における二つのベクトルは、両者が直交し、いずれも単位長さであれば正規直交である。直交するベクトルは、互いに垂直である。すなわち、それらの内積は0である。
【００３１】
ある正規直交基底から別の正規直交基底への二つのベクトルの投影は、軸の回転を表し、これはベクトル間の角度を変えない。よって、二つのベクトルの間の規格化された相関および検出指標DVは直交変換に対して不変である。Vのこの新しい基底{W1,W2,…,Wm,em+1,em+2,…,en}への投影を考え、この空間での係数を{v1,v2,…,vn}と表すことにする。すると、規格化された相関は
【数３】
2010529810.tif 000005
と書くことができる。1/√V・Vは、i＝1,2,…,mとしてすべてのCV,Wiにおける共通因子なので、落とすことができ、|vi|は
|vi1|≧|vi2|≧…≧|vim|
と直接ソートできる。相関比検出指標は
【数４】
2010529810.tif 000006
となり、偽陽性イベントDv＞Tは
すべてのj≠i1について、|vi1|＞T・|vj|      (3)
と等価である。各|vi|が最大になる同じ確からしさをもつとすると（透かしが埋め込まれなかった場合を考えていることからすると、合理的な想定である）、任意の規格化された相関が偽陽性を起こすのに十分な大きさである確率は、V1が偽陽性を起こす確率よりm倍の大きさである。すなわち、
Pfp＝P(DV＞T)＝m・P(DV＞T  /i1＝1)      (4)
となる。
【００３２】
式(2)から、偽陽性イベントがスカラー不変であることが明らかである。すなわち、何らかの特徴ベクトルVについて、その検出指標DVが閾値Tより大きければ、αを0でない定数として、スケーリングされたバージョンα・V＝{α・v1,α・v2,…,α・vn}について、Dα・VもTより大きい。よって、Vはそのl1ノルムが1に等しくなる、すなわち
【数５】
2010529810.tif 000007
となるよう規格化されることができる。これは、単位超平面
【数６】
2010529810.tif 000008
（これは実際には次元n−1の2n個の超平面の和集合である）上の一点を記述する。単位超平面Hn上でのVの分布は、検出振る舞い、より特定的には偽陽性確率の解析にとって重要である。
【００３３】
この解析は、透かし入れされていない作品については単位超平面Hn上の一様分布から引き出されるランダム変数によって近似できる規格化された特徴ベクトルVを与える検出特徴の使用に当てはまる。第一の想定として、透かし入れされていない作品からの規格化された特徴ベクトルVは、単位超平面Hn上に一様に分布する。想定１は、偽陽性イベントがスカラー不変であるという事実と組み合わされると、偽陽性確率P(DV＞T)が、単位超平面Hn上の規格化された諸特徴ベクトルのうち、その検出指標が閾値Tより大きいものの割合に等しいということを示唆する。
【００３４】
【数７】
2010529810.tif 000009
正の超平面
【数８】
2010529810.tif 000010
が定義される。ここで、Hn+はHnにおける2n個の超平面の一つで、すべての座標が非負であるものである。すると、対称性により、式(5)は
【数９】
2010529810.tif 000011
と等価である。
【００３５】
式(6)における偽陽性確率は、VおよびWiが存在するベクトル空間の次元であるnとは独立である。この証明は次のとおりである。P、VおよびHに次元を示すために添え字を付けると、Vn＝{v1,v2,…,vn}として、
【数１０】
2010529810.tif 000012
となる。ここで、
【数１１】
2010529810.tif 000013
であることを注意しておく。
【００３６】
上記すべてを組み合わせると、
【数１２】
2010529810.tif 000014
となる。
【００３７】
このように、偽陽性確率P(DV＞T)は特徴ベクトルの次元nとは独立である。特に、P(DV＞T)はn＝mと置くことによって計算できる。
【００３８】
P(DV＞T)についての解析的公式は、式(6)の幾何学的な解釈を通じて導出でき、それをこれから与える。手始めに、m＝2、H2+＝{(x1,x2)|xi＞0かつx1＋x2＝1}とする。図１ａにおいて、O＝(0,0)、A＝(1,0)、B＝(0,1)である。すべてのマークされていないコンテンツは、線分AB上の検出を与えるであろう。線分ABがH2+である。c1＝T・c2として点C＝(c1,c2)は陽性検出と陰性検出との間の境界を表す。すべての陽性検出は偽検出なので、偽陽性の確率は、線分ACの長さと線分ABの長さ全体との比である。線分AO上に点D＝(c1,0)を追加する。これはCのx1上への投影である。すると、|AO|＝|AD|＋|DO|＝c2＋c1＝c2＋Tc2＝(T＋1)c2なので、
【数１３】
2010529810.tif 000015
となる。よって、
【数１４】
2010529810.tif 000016
となる。
【００３９】
m＝3、H3+＝{(x1,x2,x3)|xi＞0かつx1＋x2＋x3＝1}のとき。図１ｂにおいて、O＝(0,0,0)、A＝(1,0,0)、B＝(0,1,0)、C＝(0,0,1)である。平面区画ABCがH3+である。点D＝(d1,d2,0)はd1＝T・d2となるような線分AB上の点であり、点E＝(e1,0,e3)はe1＝T・e3となるような線分AC上の点である。点FはCDとBEの交点である。すると、
【数１５】
2010529810.tif 000017
となる。よって、
【数１６】
2010529810.tif 000018
となる。
【００４０】
m＝4、H4+＝{(x1,x2,x3,x4)|xi＞0かつx1＋x2＋x3＋x4＝1}のとき。このときは、
【数１７】
2010529810.tif 000019
となる。よって、
【数１８】
2010529810.tif 000020
となる。
【００４１】
演繹によって続けていくと、任意のmについての偽陽性確率P(DV＞T)の解析的公式
【数１９】
2010529810.tif 000021
を導出できる。
【００４２】
式(7)の公式が正しいことを検証するために、その予測された結果が、単位超平面一様分布から引き出された10万個の合成ベクトルから得られた結果に対して比較された。特徴ベクトルの次元は1024である（n＝1024）。検出器には８つの直交透かしベクトルがある（m＝8）。図１ｃは、合成ベクトルの式(7)によってなされた予測に対する比較の結果を示す。解析的公式の予測は、実験結果と非常によく、少なくともPfp＝10-4まで一致する。
【００４３】
図３ａは、本発明の閾値決定方法のある実施形態のフローチャートである。３０５において、所望される偽陽性確率が受け入れられる。この要求は透かし検出が行われるアプリケーション環境に固有である。３１０で閾値が決定され、３１５で透かし検出器に出力される。上記の記述に従って、初期化時または最初の閾値決定に先立つもしくは最初の閾値決定の間の他の何らかの時点において、閾値のテーブルが生成されてもよい。上記の式(7)が閾値のテーブル（閾値テーブル）を生成するために使用される。テーブル生成器は式(7)を初期または最小閾値、最終または最大閾値およびきざみ（interval）サイズとともに使用する。閾値テーブルは、閾値の選択と閾値が含意する偽陽性確率との間の対応を作り出す。
【００４４】
本稿で記載される本発明の実施形態の目的のためには、初期閾値はユーザーによって入力され、あるいは選択されることができる。選択される場合、一つの可能な初期閾値は偽陰性確率の下限である。さらに、対応して、最終閾値については、選択される場合、一つの可能な最終閾値は偽陽性確率の上限である。計算において使用される増分または閾値きざみは、他の因子の中でも、閾値テーブルを記憶するために利用可能な記憶容量または所望される計算精度に基づいて選択される。
【００４５】
図３ｂは、本発明の閾値決定装置またはモジュールのブロック図である。閾値決定装置またはモジュールは、所望される偽陽性確率を入力として受け入れ、閾値を決定し、その閾値を透かし検出器に出力する。
【００４６】
図４ａは、本発明の閾値決定方法の一つの実施形態のフローチャートである。４０５において、所望される偽陽性確率が受け入れられる。４１０で、初期化時または他の時点で前もって用意された閾値テーブルへのインデックスが初期化される。４１５で、そのインデックスに基づいて前記テーブルからテーブル・エントリーが取得される。インデックスが必ずしも最初のテーブル・エントリーに初期化されなくてもよいことは留意しておくべきである。従来技術において知られているさまざまなテーブル探索方式のうちには、テーブル・インデックスがテーブル中のほぼ真ん中の点に初期化される二分法も含まれる。これが繰り返されるので、テーブル全体が探索される必要はない。４２０では、取得されたテーブル・エントリーが所望される偽陽性確率と比較され、もし所望される偽陽性より少なく、取得された閾値より大きくかつ所望される偽陽性確率より小さい閾値エントリーが他になければ、４２５で決定された閾値が透かし生成器に出力される。取得された閾値テーブル・エントリーより大きくかつ所望される偽陽性確率より小さくもある閾値エントリーがありえれば、４３０でテーブル・インデックスが調整される。
【００４７】
図４ｂは、テーブル探索モジュール４４０および比較器４４５を含む、閾値決定装置またはモジュール４３５のブロック図である。テーブル探索モジュールは、以前に生成された閾値テーブルからインデックスを使って閾値テーブル・エントリーを取得する。比較器４４５は比較を実行し、基準が満たされたら閾値を透かし検出器に出力し、基準が満たされなかったらテーブル・インデックスを調整してテーブル探索モジュールに戻る。テーブル・インデックスの調整は、テーブル探索モジュールまたは比較器またはその機能を実行する他のモジュール（図示せず）によって行われうる。
【００４８】
図５ａは、本発明の閾値決定方法の代替的な実施形態のフローチャートである。この実施形態では、閾値テーブルは前もって用意されず、閾値は逐次的計算を通じて決定される。５０５において、所望される偽陽性確率が入力として受領されるまたは受け入れられる。５１０で、初期閾値が選択される。初期閾値がユーザーによって入力されてもよいことは注意しておくべきであろう。５１５で、選択または入力された初期閾値に現在の閾値が初期化される。その現在の閾値が、５２０で、偽陽性確率を計算するのに使われる。５２５で、所望される偽陽性確率と計算された偽陽性確率との差の値が計算される。５３０で、差の値が0と比較され、所定の値εと比較される。差の値が0以上かつ所定の値ε未満であれば、システムは５４０で現在の閾値Tを透かし検出器に出力する。差の値が負であるか、値εより大きければ、５３５で、現在の閾値が差の値の符号および絶対値に応じて修正される。修正された現在の閾値は、該現在の閾値を使って新しい偽陽性確率を計算し直すために使われる。このプロセスは、差の値が0以上かつ値ε未満となるまで続けられる。そうなったとき、５４０で、現在の閾値Tが透かし検出器に出力される。現在の閾値は、要求／所望される偽陽性確率より高々ε小さい偽陽性確率を与える。
【００４９】
図５ｂは、偽陽性確率計算器モジュール５５０および比較器５５５を含む本発明の閾値決定装置５４５の代替的な実施形態のブロック図である。偽陽性確率計算器５５０は、（現在の）閾値を使って偽陽性確率値を計算し、所望／要求される偽陽性確率値と計算された偽陽性確率値との間の差をも計算する。比較器５５５は、差の値と0との間の比較を実行し、また差の値と所定の値εとの間の比較をも実行する。差の値が0以上かつ所定の値ε未満であれば、システムは現在の閾値Tを透かし検出器に出力する。差の値が負であるか、値εより大きければ、現在の閾値が差の値の符号および絶対値に応じて修正される。修正された現在の閾値は、該現在の閾値を使って新しい偽陽性確率を計算し直すために使われる。このプロセスは、差の値が0以上かつ値ε未満となるまで続けられる。そうなったとき、現在の閾値Tが透かし検出器に出力される。現在の閾値は、要求／所望される偽陽性確率より高々ε小さい偽陽性確率を与える。
【００５０】
本発明は、ハードウェア（たとえばASICチップ）、ソフトウェア、ファームウェア、特殊目的プロセッサまたはそれらの組み合わせのさまざまな形で、たとえばサーバー、中間デバイス（無線アクセス・ポイントまたは無線ルータのような）またはモバイル・デバイスの内部に実装されうる。好ましくは、本発明は、ハードウェアおよびソフトウェアの組み合わせとして実装される。さらに、ソフトウェアは好ましくは、プログラム記憶デバイス上に具体的に実現されたアプリケーション・プログラムとして実装される。アプリケーション・プログラムはいかなる好適なアーキテクチャを有する機械にアップロードされ、それに実行されてもよい。好ましくは、機械は、一つまたは複数の中央処理ユニット（CPU）、ランダム・アクセス・メモリ（RAM）および入出力（I/O）インターフェース（単数または複数）といったハードウェアを有するコンピュータ・プラットフォーム上で実装される。コンピュータ・プラットフォームはまた、オペレーティング・システムおよびマイクロ命令コードをも含む。本稿に記載されたさまざまなプロセスおよび機能は、オペレーティング・システムを介して実行される、マイクロ命令コードの一部またはアプリケーション・プログラムの一部（またはそれらの組み合わせ）であってもよい。さらに、追加的なデータ記憶装置および印刷装置のようなさまざまな他の周辺デバイスがコンピュータ・プラットフォームに接続されていてもよい。
【００５１】
さらに、付属の図面に描かれている構成要素となるシステム・コンポーネントおよび方法ステップのいくつかは好ましくはソフトウェアにおいて実装されるので、システム・コンポーネント（またはプロセス・ステップ）間の実際の接続は、本発明がプログラムされる仕方に依存して変わりうることは理解しておくべきである。本稿での教示を与えられれば、当業者は本発明のこれらおよび同様の実装または構成を考えることができるであろう。
【図１ａ】
2010529810.tif 000024
【図１ｂ】
2010529810.tif 000025
【図１ｃ】
2010529810.tif 000026
【図２ａ】
2010529810.tif 000027
【図２ｂ】
2010529810.tif 000028
【図３ａ】
2010529810.tif 000029
【図３ｂ】
2010529810.tif 000030
【図４ａ】
2010529810.tif 000031
【図４ｂ】
2010529810.tif 000032
【図５ａ】
2010529810.tif 000033
【図５ｂ】
2010529810.tif 000034
【手続補正書】
【提出日】平成21年12月15日(2009.12.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
閾値を決定する方法であって：
所望される偽結果確率を選択する段階と；
前記所望される偽結果確率に対応する、閾値テーブルからの閾値を選択する段階とを有する、
方法。
【請求項２】
前記閾値テーブルを生成する段階をさらに有する請求項１記載の方法であって、
前記生成する段階がさらに：
前記閾値テーブル中の各偽結果確率エントリーを
【数１】
2010529810.tif 000035
を使って計算する段階と；
前記閾値テーブル中に前記計算された偽結果確率および前記偽結果確率エントリーを計算するのに使われた前記閾値を記憶する段階とを有し、Tは前記閾値である、
方法。
【請求項３】
前記計算する段階が、第一の閾値、第二の閾値および閾値きざみを使って、前記第一の閾値を前記閾値きざみだけ逐次的にインクリメントして、前記第一の閾値が前記第二の閾値に等しくなるまで前記閾値テーブルの前記の各偽結果確率エントリーを計算していくことによって実行される、請求項２記載の方法。
【請求項４】
前記偽結果確率が偽陽性確率であり、さらに、前記第一の閾値が偽陰性確率の下限であり、前記第二の閾値が前記偽陽性確率の上限である、請求項３記載の方法。
【請求項５】
前記選択する段階が前記閾値を前記閾値テーブルから取得し、前記閾値が、前記所望される偽結果確率より小さい偽結果確率をもつ最大の閾値である、請求項１記載の方法。
【請求項６】
閾値を決定する方法であって：
所望される偽結果確率を選択する段階と；
偽結果確率を計算する段階と；
前記の計算された偽結果確率と前記の所望される偽結果確率との間の差の値を計算する段階と；
前記差の値を第一の所定の値と比較する段階と；
前記の第一の比較工程の結果が正であれば前記差の値を第二の所定の値と比較する段階とを有する、
方法。
【請求項７】
前記偽結果確率が偽陽性確率である請求項６記載の方法であって、さらに：
第一の閾値を選択する段階と；
前記両方の比較する段階の結果が両方とも正でない場合には前記第一の閾値を修正する段階とを有する、
方法。
【請求項８】
閾値を決定する装置であって：
所望される偽結果確率を選択する手段と；
前記所望される偽結果確率に対応する、閾値テーブルからの閾値を選択する手段とを有する、
装置。
【請求項９】
前記閾値テーブルを生成する手段をさらに有する請求項８記載の装置であって、
前記生成する手段がさらに：
前記閾値テーブル中の各偽結果確率エントリーを
【数２】
2010529810.tif 000036
を使って計算する手段と；
前記閾値テーブル中に前記計算された偽結果確率および前記偽結果確率エントリーを計算するのに使われた前記閾値を記憶する手段とを有し、Tは前記閾値である、
装置。
【請求項１０】
前記計算する手段が、第一の閾値、第二の閾値および閾値きざみを使って、前記第一の閾値を前記閾値きざみだけ逐次的にインクリメントして、前記第一の閾値が前記第二の閾値に等しくなるまで前記閾値テーブルの前記の各偽結果確率エントリーを計算していくことによって実行される、請求項９記載の装置。
【請求項１１】
前記偽結果確率が偽陽性確率であり、さらに、前記第一の閾値が偽陰性確率の下限であり、前記第二の閾値が前記偽陽性確率の上限である、請求項１０記載の装置。
【請求項１２】
前記選択する手段が前記閾値を前記閾値テーブルから取得し、前記閾値が、前記所望される偽結果確率より小さい偽結果確率をもつ最大の閾値である、請求項８記載の装置。
【請求項１３】
所望される偽結果確率に対応する閾値を決定する装置であって：
偽結果確率を計算する手段と；
前記の計算された偽結果確率と前記の所望される偽結果確率との間の差の値を計算する手段と；
前記差の値を第一の所定の値と比較する手段と；
前記の第一の比較工程の結果が正であれば前記差の値を第二の所定の値と比較する手段とを有する、
装置。
【請求項１４】
前記偽結果確率が偽陽性確率である請求項１３記載の装置であって、さらに：
第一の閾値を選択する手段と；
前記両方の比較する段階の結果が両方とも正でない場合には前記第一の閾値を修正する段階とを有する、
装置。
【国際調査報告】
2010529810.tif 000037
2010529810.tif 000038
2010529810.tif 000039