JP2007519986A - 導出されたフィンガープリントのマッチングによるデータオブジェクトのマッチング - Google Patents

Abstract

本発明は、問い合わせデータオブジェクトを候補データオブジェクトのマッチングを、両データオブジェクトのフィンガープリントを抽出して比較することによって行うための方法および装置に関する。本発明のある実施形態では、フィンガープリント抽出モジュール（１１０）、フィンガープリントマッチングモジュール（２１０）、統計モジュール（１２０）および識別モジュールを有する装置が提供される。フィンガープリント抽出モジュール（１１０）は、問い合わせオブジェクトの一部をなしていて問い合わせフィンガープリントを構築する情報信号を受信する。フィンガープリントマッチングモジュール（２１０）は、前記問い合わせフィンガープリントを少なくとも一つの潜在的な最良一致候補を見出すためにデータベース（２１５）中に保存されている候補と比較する。一方、統計モジュールは、前記問い合わせフィンガープリントの統計的モデルを決定して、それによりたとえば、前記問い合わせフィンガープリントの内部におけるある種の情報の統計分布を決定する。閾値決定器（１２０）は、前記問い合わせフィンガープリントの分布に基づいて、前記問い合わせフィンガープリントとある潜在的最良一致候補とが識別モジュール（１３０）によって同様であると宣言されうる範囲の適応的閾値距離Tを導出するよう構成される。閾値を問い合わせおよび／または候補フィンガープリントから導出される統計的データに依存しうるよう設定することによって、他人受入率FARの改善が達成されうる。

Description

本発明はフィンガープリントのマッチングのための方法および装置に関する。

フィンガープリント技術はメディアコンテンツ（オーディオまたはビデオのような）を識別するのに使われる。オーディオまたはビデオセグメントは、それからフィンガープリントを抽出し、該抽出されたフィンガープリントを既知コンテンツのフィンガープリントが保存されているデータベース内で検索することによって識別される。抽出されたフィンガープリントと保存されているフィンガープリントとの間の類似性が十分であると見なされた場合にコンテンツが識別される。

マルチメディアフィンガープリントの第一の目的は、二つのマルチメディアオブジェクトの知覚上の等価性を確立するための効率的な機構である：それも（典型的には大きな）オブジェクトそのものを比較するのではなく、関連付けられたフィンガープリント（設計により小さい）を比較することによってである。フィンガープリント技術を使うたいていのシステムでは、多数のマルチメディアオブジェクトのフィンガープリントがその関連付けられたメタデータ（たとえば楽曲情報、アーチスト名、タイトルおよびアルバム）とともにデータベースに保存されている。フィンガープリントはメタデータへのインデックスの役割をする。よって、未識別マルチメディアコンテンツは、フィンガープリントを計算し、これを前記フィンガープリント／メタデータデータベースにおける問い合わせとして使うことによってメタデータが検索される。マルチメディアコンテンツそのものの代わりにフィンガープリントを使うことの利点は三つある：フィンガープリントが比較的小さいことによる必要メモリ／記憶容量の低減、知覚的に重要でない情報がすでにフィンガープリントから除去されていることによる効率的な比較、そして検索すべきデータセットがより小さいことによる効率的な検索である。

フィンガープリントはオブジェクトの短い要約と見なすことができる。したがって、フィンガープリント関数は、多数のビットからなるオブジェクトXを限られた数のビットのみのフィンガープリントFにマッピングすべきである。フィンガープリントシステムには５つの主要なパラメータがある：堅牢性、信頼性、フィンガープリントサイズ、粒度および検索速度（またはスケーラビリティ）である。

システムの堅牢性の度合いは、信号劣化があるような場合にフィンガープリントから特定のオブジェクトが正しく識別できるかどうかを決める。高い堅牢性を実現するためには、フィンガープリントFは、信号劣化に関して不変な（少なくともある程度まで）知覚的特徴に基づくべきである。好ましくは、ひどく劣化した信号でも元来の劣化していない信号のフィンガープリントと同様のフィンガープリントを与える。フィンガープリントシステムの堅牢性の尺度を表すのには、一般に「本人拒否率」（FRR: false rejection rate）が使われる。本人拒否は、知覚上同様のオブジェクトのフィンガープリントに、肯定的な識別を生じるには大きすぎる違いがある場合に生じる。

フィンガープリントシステムの信頼性は、オブジェクトが誤って識別される頻度に関する。言い換えれば、信頼性は「他人受入率」（FAR: false acceptance rate）――すなわち、二つの異なるオブジェクトが同一であると誤って宣言されうる確率に関係する。

フィンガープリントサイズがいかなるフィンガープリントシステムにも重要であることは明らかである。一般に、フィンガープリントサイズが小さいほど多くのフィンガープリントをデータベースに保存できる。フィンガープリントサイズはしばしばビット毎秒で表され、フィンガープリントデータベースサーバーのために必要とされるメモリリソースをかなりの部分まで決定する。

粒度は用途に依存しうるパラメータであるが、あるオブジェクトを識別するためにそのオブジェクトのどのくらい長い（大きな）具体的標本が必要とされるかに関係している。

検索速度（またはスケーラビリティ）はその名の通り、フィンガープリントデータベースでフィンガープリントをみつけるのに必要とされる時間に関する。

上記の５つの基本パラメータは互いに大きく影響し合っている。たとえば、より低い粒度を実現しようとすれば、同じ信頼性を得るためにはより大きなフィンガープリントを抽出する必要がある。これは、他人受入率がフィンガープリントサイズに対して逆の関係にあるという事実のためである。別の例では、より堅牢なフィンガープリントを設計すると、検索速度は一般に増加する。

フィンガープリントシステムの基本パラメータを議論したところで、これから典型的なフィンガープリントシステムの一般的な記述をすることにする。

フィンガープリントは、もとになるオーディオまたはビデオ信号から特徴ベクトルを抽出することに基づくものでもよい。そのようなベクトルは、関連するメタデータ（たとえばタイトル、作者など）への参照とともにデータベース中に保存される。未知の信号の受信に際して、該未知の信号から特徴ベクトルが抽出される。これがその後、フィンガープリントデータベース上での問い合わせとして使用される。問い合わせ特徴ベクトルとデータベース中の最良一致との間の距離が所与の閾値よりも小さければ、二つの項目は等価と宣言され、関連付けられたメタデータが返される：すなわち、受け取ったコンテンツが識別されたのである。

マッチング・プロセスにおいて使われる閾値は、他人受入率（FAR）と本人拒否率（FRR）との間のかねあいによる。たとえば、閾値を上げれば（すなわち、二つのフィンガープリントが同様であると判断されるための両フィンガープリント間の許容できる「距離」を上げる）、FARは上がるが、同時にFRRは低下する。FARとFRRとの間のかねあいは、通例、いわゆるネイマン・ピアソン法（Neyman-Pearson approach）を通じてなされる。これは、閾値を、FARを事前に指定された許容可能なレベル未満に保つ最小値となるように選ぶことを意味している。FRRは閾値を決定するためには使われず、単に選択された閾値の値の結果として決まる。

US2002/0178410A1（Haitsma, Kalker, Baggen and Oostveen）は、マルチメディアコンテンツのフィンガープリントを生成してマッチングを行うための方法および装置を開示している。この文書の４ページには、二つの３秒のオーディオクリップが、二つの導出されたフィンガープリントブロックH₁とH₂との間のハミング距離がある閾値T未満である場合に同様であると宣言される方法が記載されている。

閾値Tの選択を解析するため、US2002/0178410A1の著者らは、フィンガープリント抽出プロセスがランダムなi.i.d.（independent and identically distributed［独立かつ一様分布］）ビットを与えると想定している。その場合、ビット誤りの数は、nを抽出されたビット数、p（＝0.5）を0または1のビットが抽出される確率として、パラメータ(n,p)をもつ二項分布をもつことになる。nが大きいので、二項分布は平均μ＝np、標準偏差σ＝√(np(1−p))の正規分布によって近似できる。フィンガープリントブロックH₁が与えられたとすると、ランダムに選ばれたフィンガープリントブロックH₂のH₁に対する相違がT＝αnより少ない確率は次式によって与えられる。

しかし、実際上は、堅牢なフィンガープリントは時間軸に沿って高い相関をもつ。これは、根底にあるビデオシーケンスの大きな時間相関、あるいはオーディオフレームの重なりに起因するものでありうる。オーディオフィンガープリントについての実験の結果、誤りビットの数は正規分布をしているが、標準偏差はi.i.d.の場合より約３倍大きいことが示されている。したがって、式（１）はこの因子３を含むよう修正される。

上記の手法は、フィンガープリント間の分布が定常的であると想定している。これはある種の技術分野については当を得た想定のように思われるが、ビデオフィンガープリントの場合にそうでないことは確かである。ビデオフィンガープリントにおいては、ビデオ中の「活動」の量が、フィンガープリントビットの相関に直接的に反映される：長引くスチールは一定の（すなわち相関が非常に高い）フィンガープリントにつながり、一方、「派手な」ミュージッククリップはフィンガープリントビット間の相関が非常に低いことにつながることになる。この非定常性は、閾値について適切な値を決定する際の問題につながる。

適応的な閾値処理技術を提供するための装置を提案することが、本発明の諸実施形態の目的の一つである。

本発明の第一の側面によれば、問い合わせフィンガープリントを候補フィンガープリントと比較する方法が提供される。該方法は：問い合わせフィンガープリントおよび／または候補フィンガープリントの統計的モデルを決定し、該統計的モデルに基づいて前記問い合わせフィンガープリントと前記候補フィンガープリントとが同様であると宣言されうる範囲の閾値距離を導出する、ことを含むことを特徴としている。

本発明の第二の側面は、問い合わせオブジェクトを既知のオブジェクトとマッチングする方法を提供する。該方法では、複数の候補オブジェクトを表す複数の候補フィンガープリントがデータベースにあらかじめ保存されており、当該方法は、前記問い合わせオブジェクトの一部をなす情報信号を受信してそれから問い合わせフィンガープリントを構築し、前記問い合わせフィンガープリントをデータベース中のある候補フィンガープリントと比較することを含んでおり、当該方法は：問い合わせフィンガープリントおよび／または候補フィンガープリントの統計的モデルを決定し、該統計的モデルに基づいて前記問い合わせフィンガープリントと前記候補フィンガープリントとが同様であると宣言されうる範囲の閾値距離を導出する、ステップをさらに含むことを特徴としている。

第一および第二の側面の方法において、特定のフィンガープリントの統計的モデルに基づく閾値の導出は、問い合わせフィンガープリントの型／内的特性に従ってFARを最適化しうる適応的閾値設定を提供し、任意の閾値処理システムの適用に対して改善されたマッチング品質を与える。

好ましくは、候補フィンガープリントが問い合わせフィンガープリントから前記閾値距離未満の距離だけ離れていると見出され、その候補と問い合わせフィンガープリントとの間の距離が他のいかなる候補フィンガープリントと当該問い合わせフィンガープリントとの間の距離よりも小さい場合には、その候補フィンガープリントが最良一致候補フィンガープリントと宣言され、該最良一致候補フィンガープリントによって表される候補オブジェクトと当該問い合わせフィンガープリントによって表される問い合わせオブジェクトとは同じであると見なされる。

好ましくは、前記統計的モデルは、前記問い合わせフィンガープリントおよび／または候補フィンガープリントに対して内的相関導出を実行した結果を有する。

好ましくは、前記フィンガープリントは二進値を有し、前記統計的モデルを前記問い合わせフィンガープリントについて計算するのは、問い合わせフィンガープリントフレームF(m,k)のうち直前のフィンガープリントフレームF(m,k−1)での対応するビットと異なるものがいくつあるかを決定し、前記遷移数を、全フィンガープリントビットが直前の対応するビットと逆の状態であるとした場合に得られる最大値M(k−1)で割ることによって前記問い合わせフィンガープリントについての遷移確率qを決定することによる。ここで、各フィンガープリントは1フレームあたりMビットを含んでKフレームにまたがっており、kはフレーム添え字（0からKの範囲）、mはフレーム内でのビット添え字（0からMの範囲）である。

このとき、閾値（threshold）距離Tは、所望の他人受入率（FAR）に基づいて次式から計算されうる。

第三の側面では、本発明は問い合わせオブジェクトを既知のオブジェクトとマッチングする装置を提供する。当該装置は、問い合わせオブジェクトの一部をなす情報信号を受信してそれから問い合わせフィンガープリントを構築するためのフィンガープリント抽出モジュールと、前記問い合わせフィンガープリントを一つまたは複数の候補フィンガープリントのデータベース中に保存されている候補フィンガープリントと比較するためのフィンガープリントマッチングモジュールとを有しており、当該装置はさらに：前記問い合わせフィンガープリントおよび／または前記一つもしくは複数のフィンガープリントのうちの一つまたは複数の統計的モデルを決定するための統計モジュールと、該統計的モデルに基づいて前記問い合わせフィンガープリントとある候補フィンガープリントとが同様であると宣言されうる範囲の閾値距離Tを導出する閾値決定器と、ある候補フィンガープリントが前記問い合わせフィンガープリントから前記閾値距離T未満の距離だけ離れていると見出され、前記候補と前記問い合わせフィンガープリントとの間の距離が他のいかなる候補フィンガープリントと当該問い合わせフィンガープリントとの間の距離よりも小さい場合には、その候補フィンガープリントが最良一致候補フィンガープリントと宣言され、該最良一致候補フィンガープリントによって表される候補オブジェクトと当該問い合わせフィンガープリントによって表される問い合わせオブジェクトとは同じであると見なされるよう構成された識別モジュール、とを有することを特徴としている。

本発明のよりよい理解のため、そしてその諸実施形態が実施されうる仕方を示すため、これから例として付属の図式的な図面を参照する。

図１を参照すると、機能ブロック図がクライアント側１００とデータベースサーバー側２００とに分けて示されている。クライアント側では、オブジェクトがフィンガープリント抽出モジュール１１０によって受信され、フィンガープリントFがそのオブジェクトについて計算される。問い合わせフィンガープリントFは一方では統計モジュール１２０に渡され、他方ではデータベースサーバー側２００にも渡される。統計モジュール１２０は、前記問い合わせフィンガープリントFのランダム性／相関性を決定し（たとえば、内的相関を決定しうる）、この情報を閾値決定器１３０に渡す。閾値決定器１３０は、モジュール１２０からの情報に基づいて、閾値レベルTを適応的に設定し、この閾値レベルTをデータベースサーバー側２００に渡す。

データベースサーバー側２００では、マッチングモジュール２１０がクライアント側１００から問い合わせフィンガープリントFを受信し、既知のフィンガープリントのデータベース内で前記フィンガープリントの最良一致を探す。最良一致情報は次いで閾値比較モジュール２２０に渡され、最良一致候補フィンガープリントが当該問い合わせフィンガープリントに十分近い（閾値距離T内）かどうかが判定され、それにより入力オブジェクトと前記候補フィンガープリントに対応する一致したオブジェクトとの同一性が判定される。フィンガープリントFが二進値をとる場合、前記閾値比較モジュール２２０はたとえばフィンガープリントブロックH₁とデータベース２１０中の最良一致に関係するフィンガープリントブロックH₂との間のハミング距離を比較し、その二つのブロックの間のハミング距離が、閾値決定モジュール１３０から比較モジュール２２０に供給される閾値距離Tより小さいかどうかを調べてもよい。同一性決定は、識別モジュール２３０によってなされるが、その際、二つの導出されたフィンガープリントブロックの間のハミング距離が前記閾値距離Tより小さければ、未識別の問い合わせオブジェクトがデータベース中に見つかったオブジェクトと同様であると宣言され、関連するメタデータが返される。

上の記述では、問い合わせフィンガープリントFと閾値Tとはクライアント側１００からデータベースサーバー側２００に送られる。ここで、もちろん、閾値Tがデータベースサーバー側２００で決定されることもでき、したがって上述したブロック図の修正がもちろん可能であることを注意しておく。

ここで図２を参照すると、フィンガープリントを見出し、マッチングする際における図１のブロック図の構成要素の動作を一般的な形で説明するフローチャートが示されている。

ステップＳ１００では、オブジェクト標本（たとえば、ビデオの場合、短い「クリップ」）が受信され、問い合わせフィンガープリントがその標本に基づいて決定される。この問い合わせフィンガープリントは、いかなる好適な従来技術の方法（US2002/0178410A1）に従って決定されてもよい。ステップＳ２００（経路「A」によって到達する）では、問い合わせフィンガープリントに対する閾値が、問い合わせフィンガープリントの特定の特性（ランダム性／相関性）に基づいて決定される。

ステップＳ２００と並行して実行されうるステップＳ３００では、問い合わせフィンガープリントはデータベースサーバー側２００で保持されているフィンガープリントとマッチングされ、最良一致候補が返される。ここでもまた、このマッチング・プロセスは従来技術の仕方で実行することができ、問い合わせフィンガープリントに対して最も近い一致を返す。

ステップＳ３００において、問い合わせフィンガープリントと最良一致候補との間の「距離」が決定され、ステップＳ４００においてその「距離」がステップＳ２００で決定された閾値距離よりも小さいか否かが調べられる。ステップＳ４００で問い合わせフィンガープリントと最良一致候補との間の距離が閾値よりも大きいと見出された場合、ステップＳ５００において、問い合わせオブジェクトには一致するオブジェクトがみつからなかったという結果が返される。他方、ステップＳ４００で問い合わせフィンガープリントと最良一致候補フィンガープリントとの間の距離が閾値距離よりも小さかった場合には、ステップＳ６００において、問い合わせオブジェクトと最良一致候補に関係するデータベース内のオブジェクトとの間の一致が宣言される。その際、最良一致オブジェクトのメタデータなどがユーザーに返されてもよい。

図２では、ステップＳ１００からＳ２００につながる点線で示された経路「A」は、問い合わせフィンガープリントに基づいて閾値をT＝T1と設定する一つのオプションを表す。しかし、代替的に、経路「A」は破棄してもよく、最良一致候補の特性に基づいて閾値T＝T2としてもよい。この可能性は、Ｓ３００からＳ２００への代替的な経路Bによって表される。

さらなる代替では、閾値Tは、問い合わせフィンガープリントと最良一致候補フィンガープリントとの両方の特性の組み合わせに基づいて設定されてもよい。たとえば、閾値を二つの導出された適応的閾値T1、T2の間の平均に設定するのである。

図３は、所与の閾値を適応的に決定するための一般的な方法論を示すフローチャートである。

ステップＳ２１０において、問い合わせ候補フィンガープリントが受信され、フィンガープリントのランダム性の測度が決定され、次いでステップＳ２１０において見出されたランダム性の測度に基づいてステップＳ２２０において閾値距離が設定される。

上記から、および図１に関する説明から理解されるであろうように、比較において使われる閾値T（T1またはT2）は、問い合わせフィンガープリントまたは／および最良一致候補におけるランダム性／相関性に対して適応される。より具体的には、問い合わせフィンガープリントについての閾値決定の場合、問い合わせフィンガープリントの相関が決定され、この相関からマッチングの間に使われるべき閾値が計算される。内的相関のランダム性が低いと見出されるほど、より小さな閾値距離Tを設定してもFRRに悪影響を及ぼさずにすむ。

上述したように、閾値は問い合わせフィンガープリントの内的相関、最良一致候補フィンガープリントの内的相関または両者の組み合わせに基づいて決定される。フィンガープリントが二進値であり、フィンガープリントビットがマルコフ過程のように振る舞う場合には、閾値を適応的に設定するための解を導出できる。

適応的閾値設定問題への解が図４に示されている。ステップＳ２２１において、問題となっているフィンガープリントの内的相関が決定され、ステップＳ２２２において前記内的相関に基づいて当該フィンガープリントについての遷移確率が決定され、ステップＳ２２３において、遷移確率（以下に説明）と所望の他人受入率との両方に基づいて閾値距離が適応的に設定される。

フィンガープリントが1フレームあたりMビットからなり、Kフレームにまたがるとする。この場合、フィンガープリントはF(m,k)で表せる。ここで、kはフレーム添え字（0からK−1の範囲）、mはフレーム内でのビット添え字（0からM−1の範囲）である。フレームkから抽出されたフィンガープリントビットがフレームk−1からの対応するフィンガープリントビットと等しくない確率をqで表すものとする（すなわち、q＝Prob［bit(m,k)≠bit[m,k−1]］）。この確率qが遷移確率と呼ばれる。この場合、相関は（q＝1/2である純粋にランダムなビットの場合に比べて）次の因子だけ大きくなる。

結果として、他人受入率FARは次の関係式によって記述される。

所望のFARと計算された遷移確率qから適応的閾値を計算するために上記の関係式を使用するプロセスは、次のようにまとめることができる：
フィンガープリントFを抽出する
フィンガープリントFについての遷移確率qを次のようにして決定する：
(a)フィンガープリントビットF(m,k)のうち直前のものF(m,k−1)と異なっているものの個数を決定する
(b)ステップ(a)で計算された遷移数を、各フレームについて全フィンガープリントビットが直前のフレームでのビットと逆であるとした場合に得られる理論的な最大値M(K−1)で割って、遷移確率q＝(ビット遷移の数)／(M(k−1))を決定する。

この特定の問い合わせフィンガープリントFのマッチングのために使われるべき閾値Tを、前記の計算された値qと所定のあらかじめ承認された他人受入率とから、関係式（３）を使って決定する。

上記から、閾値Tは、適応的にT=T1（上記の問い合わせフィンガープリントの相関に基づく）あるいはT＝T2（上記の最良一致フィンガープリントの相関に基づく）あるいはT＝T3（T1、T2の組み合わせに基づく［たとえばT＝(T1＋T2)/2］）として設定することができる。次いで、決定段階において、ハミング距離がTより小さければ、もとになった両オブジェクトが同じであると宣言する。

本発明のついての上記の個別的な例においては、閾値距離はある特定の問い合わせ標本の、あるいは、実際、ある特定の候補標本または標本集合の内的特性に基づいて適応的に設定されている。しかし、記述された個別的な例は問題になっている内的特性をランダム性／相関性としているものの、情報信号の種類によっては他の種類の統計分布が適用されうること、したがって本発明が、問い合わせ標本または候補標本フィンガープリントが従うと期待されるいかなる所与の適用可能な「統計モデル」に基づいて適応的閾値を提供することにも合理的に拡張されうることは認識されるであろう。

さらに、当業者は、図２ないし４のフローチャートが本発明を実施するための一つの構成を示しているものの、他の構成も可能であることを認識するであろう。たとえば、図２のステップＳ３００において単一の最良一致候補を返すのではなく、ある閾値距離内の複数の近似一致候補を返して、その後「最良」一致を計算するために並列に（あるいはそれほど有利ではないが直列に）処理してもよい。本発明はまた、データベース中の一部の候補が一致し得ないことが明らかである場合にすぐさま破棄できるという、いわゆる「剪定」（pruning）技法を使って適用することもできる――その場合、検索／マッチングはずっと縮小された検索空間内で行うことができる。

本発明の諸実施形態に基づいて、閾値がフィンガープリントの特定の特性に依存するような、適応的閾値を設定するための諸方法および装置が開示される。特定の方法はビデオコンテンツのマッチングにおける使用のために非常に好適であるが、これに限定されるものではない。記載されている諸技法はさまざまな異なる技術分野およびさまざまな異なる種類の信号に適用されうるもので、それにはオーディオ信号、ビデオ信号、マルチメディア信号が含まれるがこれに限られるものではない。

当業者は、記載されている諸プロセスがソフトウェア、ハードウェアまたはいかなる好適な組み合わせにおいても実施しうることを認識するであろう。

まとめると、本発明は、フィンガープリントマッチングのための方法および装置に関する。本発明のある実施形態では、フィンガープリント抽出モジュール（１１０）、フィンガープリントマッチングモジュール（２１０）、統計モジュール（１２０）および識別モジュールを有する装置が提供される。フィンガープリント抽出モジュール（１１０）は、問い合わせオブジェクトの一部をなしていて問い合わせフィンガープリントを構築する情報信号を受信する。フィンガープリントマッチングモジュール（２１０）は、前記問い合わせフィンガープリントを少なくとも一つの潜在的な最良一致候補を見出すためにデータベース（２１５）中に保存されている候補と比較する。一方、統計モジュールは、前記問い合わせフィンガープリントの統計的モデルを決定して、それによりたとえば、前記問い合わせフィンガープリントの統計分布を決定する。閾値決定器（１２０）は、前記問い合わせフィンガープリントの分布に基づいて、前記問い合わせフィンガープリントとある潜在的最良一致候補とが識別モジュール（１３０）によって同様であると宣言されうる範囲の適応的閾値距離Tを導出するよう構成される。閾値を問い合わせフィンガープリントの統計的分布に基づいて適応的な仕方で設定することによって、他人受入率FARの改善およびその他の利点が達成されうる。

本発明のある実施形態に基づく適応的な閾値を用いたフィンガープリント法を図解する機能ブロック図である。 本発明のある実施形態に基づいてフィンガープリントを見出し、マッチングするのに関わるプロセスを一般的な形で説明するフローチャートである。 本発明のある実施形態に基づく適応的閾値を決定するための方法論を一般的な形で示すフローチャートである。 本発明の諸実施形態に基づく、特定の適応的閾値設定方法論を示すフローチャートである。

Claims (10)

1. 問い合わせフィンガープリントを候補フィンガープリントと比較する方法であって：前記問い合わせフィンガープリントおよび／またはある候補フィンガープリントの統計的モデルを決定し、該統計的モデルに基づいて、その範囲内なら前記問い合わせフィンガープリントと前記候補フィンガープリントとが同様であると宣言されうる閾値距離を導出する、ことを含むことを特徴とする方法。
2. 問い合わせオブジェクトを既知のオブジェクトとマッチングする方法であって、該方法では、複数の候補オブジェクトを表す複数の候補フィンガープリントがデータベースにあらかじめ保存されており、当該方法は、前記問い合わせオブジェクトの一部をなす情報信号を受信してそれから問い合わせフィンガープリントを構築し、前記問い合わせフィンガープリントを前記データベース中のある候補フィンガープリントと比較することを有しており、当該方法がさらに：
   前記問い合わせフィンガープリントおよび／または前記候補フィンガープリントについての統計的モデルを決定し、
   該統計的モデルに基づいて、その範囲内なら前記問い合わせフィンガープリントと前記候補フィンガープリントとが同様であると宣言されうる閾値距離を導出する、
   ステップを有することを特徴とする方法。
3. 請求項１または２記載の方法であって、ある候補フィンガープリントが当該問い合わせフィンガープリントから前記閾値距離未満の距離だけ離れていると見出され、その候補と当該問い合わせフィンガープリントとの間の距離が他のいかなる候補フィンガープリントと当該問い合わせフィンガープリントとの間の距離よりも小さい場合には、その候補フィンガープリントが最良一致候補フィンガープリントと宣言され、該最良一致候補フィンガープリントによって表される候補オブジェクトと当該問い合わせフィンガープリントによって表される問い合わせオブジェクトとが同じであると見なされることを特徴とする方法。
4. 請求項１ないし３のうちいずれか一項記載の方法であって、前記統計的モデルが、前記問い合わせフィンガープリントおよび／または前記候補フィンガープリントに対する内的相関導出を実行した結果を有することを特徴とする方法。
5. 前記フィンガープリントは二進値を含む複数のフレームを有し、前記統計的モデルを前記問い合わせフィンガープリントについて計算するのは、前記問い合わせフィンガープリントのフレームF(m,k)のうち直前のフィンガープリントフレームF(m,k−1)での対応するビットと異なるものがいくつあるかを決定し、前記遷移数を、全フィンガープリントビットが直前の対応するビットと逆の状態であったとした場合に得られるはずの最大値M(k−1)で割ることによって前記問い合わせフィンガープリントについての遷移確率qを決定することによっており、ここで、各フィンガープリントは1フレームあたりMビットを含んでKフレームにまたがっており、kはフレーム添え字（0からKの範囲）、mはフレーム内でのビット添え字（0からMの範囲）である、ことを特徴とする、請求項４記載の方法。
6. 閾値距離Tが、所望の他人受入率（FAR）に基づいて式
   

   

   から計算されることを特徴とする、請求項５記載の方法。
7. 問い合わせオブジェクトを既知のオブジェクトとマッチングする装置であって、当該装置は、問い合わせオブジェクトの一部をなす情報信号を受信してそれから問い合わせフィンガープリントを構築するためのフィンガープリント抽出モジュールと、前記問い合わせフィンガープリントを一つまたは複数の候補フィンガープリントのデータベース中に保存されている候補フィンガープリントと比較するためのフィンガープリントマッチングモジュールとを有しており、当該装置はまた：
   前記問い合わせフィンガープリントおよび／または前記一つもしくは複数のフィンガープリントのうちの一つまたは複数の統計的モデルを決定するための統計モジュールと、
   該統計的モデルに基づいて、その範囲内なら前記問い合わせフィンガープリントとある潜在的な最良一致候補フィンガープリントとが同様であると宣言されうる閾値距離Tを導出する閾値決定器と、
   ある候補フィンガープリントが前記問い合わせフィンガープリントから前記閾値距離T未満の距離だけ離れていると見出され、前記候補と前記問い合わせフィンガープリントとの間の距離が他のいかなる候補フィンガープリントと当該問い合わせフィンガープリントとの間の距離よりも小さい場合には、その候補フィンガープリントが最良一致候補フィンガープリントと宣言され、該最良一致候補フィンガープリントによって表される候補オブジェクトと当該問い合わせフィンガープリントによって表される問い合わせオブジェクトとが同じであると見なされるよう構成された識別モジュール、
   とをも有することを特徴とする装置。
8. 請求項７記載の装置であって、前記統計モジュールが、前記問い合わせフィンガープリントおよび／または前記一つまたは複数の候補フィンガープリントに対する内的相関導出を実行することを特徴とする装置。
9. 前記フィンガープリントは二進値を含む複数のフレームを有し、前記統計モジュールが前記統計的モデルを前記問い合わせフィンガープリントまたは／および前記候補フィンガープリントについて計算するのは、前記問い合わせフィンガープリントのフレームF(m,k)のうち直前のフィンガープリントフレームF(m,k−1)での対応するビットと異なるものがいくつあるかを決定し、前記遷移数を、全フィンガープリントビットが直前の対応するビットと逆の状態であったとした場合に得られるはずの最大値M(k−1)で割ることによって遷移確率qを決定することによっており、ここで、各フィンガープリントは1フレームあたりMビットを含んでKフレームにまたがっており、kはフレーム添え字（0からKの範囲）、mはフレーム内でのビット添え字（0からMの範囲）である、ことを特徴とする、請求項８記載の装置。
10. 前記閾値決定器が前記閾値距離Tを、所望の他人受入率（FAR）に基づいて式
    

    

    から計算することを特徴とする、請求項９記載の装置。

Images