(57)【特許請求の範囲】
【請求項１】
データベースを含むオーディオ指紋検出システムによるオーディオ指紋探索方法であって、
ａ．既知のオーディオファイルをオーバーラップするフレームに分割するステップと、
ｂ．既知のオーディオファイルからの各フレームのためのオーディオ指紋を抽出するステップと、
ｃ．前記オーディオ指紋を前記データベースにアーカイブするステップと、
ｄ．入力されるオーディオストリームの指紋と前記データベースにアーカイブされている指紋との一致の範囲を算出することを含み、入力されたオーディオストリームを比較および分類するステップと、
を含み、
前記一致の範囲を算出するステップ（ｄ）は、
１．未知のオーディオストリームの指紋とあるノードの重心との比較と、
２．前記重心の子ノードの比較が必要な場合の判定のための閾値の使用と、
３．子ノードがないノードに到達するまで、ステップ（１）とステップ（２）とを繰り返すことと、
４．ステップ（３）において到達した前記ノード内の前記指紋を検査するためのマスクの適用と、
５．一致したデータを前記オーディオ指紋検出システムに返すことと、
を含み、
前記比較および分類は、入力されたオーディオストリームの指紋と前記データベースにアーカイブされている指紋との一致の範囲に基づく、
方法。
【請求項２】
前記フレームはゼロのオーバーラップファクタを有する、請求項１に記載の方法。
【請求項３】
前記フレームは２０ミリ秒の長さを有する、請求項１に記載の方法。
【請求項４】
前記ステップ（ｃ）のアーカイブは、
６．前記指紋のクラスタへの割り当てと、
７．前記クラスタの指紋ツリーの分岐への割り当てと、
８．前記指紋ツリーの所望の深さが得られるまでステップ（６）とステップ（７）とを繰り返すことと、
をさらに含む、請求項１乃至３のいずれか一項に記載の方法。
【請求項５】
前記閾値は、２つのバイナリ文字列を一致判定するためのトグル操作の回数を含むハミング距離を備える、請求項１乃至４のいずれか一項に記載の方法。
【請求項６】
前記重心は、クラスタ内の各指紋位置において頻発するバイナリ値を含む、請求項１乃至５のいずれか一項に記載の方法。
【請求項７】
前記閾値は、連続瞬間にわたる連続した知覚フィルタバンクの振幅の方向性差分を含む、請求項１乃至４のいずれか一項に記載の方法。
【請求項８】
前記閾値は、連続した知覚フィルタバンクの振幅値の方向性差分を含む、請求項１乃至４のいずれか一項に記載の方法。
【請求項９】
前記振幅値は、異なる強度に対してバイナリ値の並列セットの維持によって記録される、請求項８に記載の方法。
【請求項１０】
データベースを含むオーディオ指紋検出システムによるオーディオ指紋探索方法であって、
ａ．既知のオーディオファイルをオーバーラップするフレームに分割するステップと、
ｂ．前記既知のオーディオファイルからの各フレームのためのオーディオ指紋を抽出するステップと、
ｃ．各指紋が複数の分解能でアーカイブされている前記データベースに前記オーディオ指紋をアーカイブするステップと、
ｄ．入力されるオーディオストリームの指紋と、前記データベースにアーカイブされている指紋との一致の範囲を算出することを含み、該一致の範囲に基づいて入力されたオーディオストリームを比較および分類し、かつ、分解能に基づいて前記一致を判定するステップと、
を含み、
前記指紋の一致判定は、
１．未知のオーディオストリームの指紋とあるノードの重心との比較と、
２．前記重心の子ノードの比較が必要な場合の判定のための閾値の使用と、
３．子ノードがないノードに到達するまで、ステップ（１）とステップ（２）とを繰り返すことと、
４．ステップ（３）において到達した前記ノード内の前記指紋を検査するためのマスクの適用と、
５．一致したデータを前記オーディオ指紋検出システムに返すことと、
を含む、
方法。
【請求項１１】
前記フレームはゼロのオーバーラップファクタを有する、請求項１０に記載の方法。
【請求項１２】
前記フレームは２０ミリ秒の長さを有する、請求項１０に記載の方法。
【請求項１３】
前記ステップ（ｃ）のアーカイブは、
６．分解能に基づいて割り当てられているクラスタへの前記指紋の割り当てと、
７．前記クラスタの指紋ツリーの分岐への割り当てと、
８．前記指紋ツリーの所望の深さが得られるまでステップ（６）とステップ（７）とを繰り返すことと
をさらに含む、請求項１０乃至１２のいずれか一項に記載の方法。
【請求項１４】
前記分解能は、高分解能と低分解能を含む、請求項１３に記載の方法。
【請求項１５】
前記高分解能は、１６ビットを含む、請求項１４に記載の方法。
【請求項１６】
前記低分解能は、２ビットを含む、請求項１４に記載の方法。
【請求項１７】
前記重心は、クラスタ中の各指紋位置において頻発するバイナリ値を含む、請求項１０乃至１６のいずれか一項に記載の方法。
【請求項１８】
前記閾値は、２つのバイナリ文字列を一致判定するためのトグル操作の回数を含むハミング距離を含む、請求項１０乃至１７のいずれか一項に記載の方法。
【請求項１９】
前記一致判定は、より低分解能の指紋から開始され、より高分解能の指紋へと処理される、請求項１０乃至１８のいずれか一項に記載の方法。
【請求項２０】
前記一致判定をより高分解能で行っている際に指紋マスクが適用される、請求項１９に記載の方法。
【発明の詳細な説明】
【背景技術】
【０００１】
本発明は、概して音声認識ならびに通信システムと方法に関する。特に、本発明はオーディオ指紋法に関係する。
【発明の概要】
【０００２】
オーディオ指紋探索の最適化のためのシステムと方法が示される。ある実施形態において、オーディオ指紋は、互いに類似していない指紋セットを含む異なる分岐を持つ再帰的ツリーに編成されている。当該ツリーは、類似尺度に基づくクラスタリングアルゴリズムを利用して構築される。類似尺度は、バイナリ指紋のためのハミング距離または連続した値を持つ指紋のためのユークリッド距離を含むことができる。別の実施形態において、各指紋は、複数の分解能で格納され、クラスタリングは、階層的に行われる。入力された指紋の認識はツリーの根から始まり、一致または不一致が宣言されるまでその分岐の下方に進む。さらに別の実施形態において、以前の定義よりもさらに詳細なオーディオ情報を含めるために指紋の定義は一般化される。
【０００３】
ある実施形態において、オーディオ指紋検出システム内のデータベースに格納されているオーディオ指紋探索方法であって、既知のオーディオファイルをオーバーラップするフレームに分割するステップと、前記既知のオーディオファイルからの各フレームのためのオーディオ指紋を抽出するステップと、前記オーディオ指紋を前記データベースにアーカイブするステップと、前記未知のオーディオストリームの前記指紋と前記データベースにアーカイブされている前記指紋との一致の範囲に基づいて、入力された未知のオーディオストリームを比較および分類するステップとを含む方法が示される。
【０００４】
別の実施形態において、オーディオ指紋検出システム内のデータベースに格納されているオーディオ指紋探索方法であって、既知のオーディオファイルをオーバーラップするフレームに分割するステップと、前記既知のオーディオファイルからの各フレームのためのオーディオ指紋を抽出するステップと、各指紋が複数の分解能でアーカイブされている前記データベースに前記オーディオ指紋をアーカイブするステップと、前記一致判定は分解能に基づいて行われ、前記未知のオーディオストリームの前記指紋と、前記データベースにアーカイブされている前記指紋との一致の範囲に基づいて比較および分類される、入力された未知のオーディオストリームを比較および分類するステップとを含む方法が示される。
【図面の簡単な説明】
【０００５】
【図１】オーディオ指紋システムの実施形態の工程を示したフローチャートである。
【０００６】
【図２】指紋ツリーの生成の工程の実施形態を示したフローチャートである。
【０００７】
【図３】クラスタリングの工程の実施形態を示したフローチャートである。
【０００８】
【図４】指紋認識の工程の実施形態を示したフローチャートである。
【発明を実施するための形態】
【０００９】
本発明の原理を理解するのを促す目的で、図面に表されている実施形態を参照し、具体的な用語を使用してそれらの実施形態を説明する。それにもかかわらず、本発明の範囲の限定はそれによって意図されていないことが理解されよう。説明されている実施形態における任意の変更およびさらなる修正、ならびに本明細書に記載されている本発明の原理の任意のさらなる応用は、本発明が関連する技術分野における当業者に一般的に想起されるように企図されている。
【００１０】
オーディオ指紋は小さなメモリフットプリントとして定義されることができる。それは、音楽、音声、または他の特性を含むオーディオフレームによって取り込まれた連続した値の低次元表現であり、（コデックおよびネットワークルータ全体のデータの通過によってもたらされる音量、マイナー転換、下落、歪みの）規模の変化に関して頑健である必要がある。
【００１１】
フィリップスアルゴリズムは（下記参考文献記載の通り：Ｈａｉｔｓｍａ，Ｊａａｐ，Ａｎｔｏｎｉｕｓ  Ｋａｌｋｅｒ，２００２，「Ａ  Ｈｉｇｈｌｙ  Ｒｏｂｕｓｔ  Ａｕｄｉｏ  Ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ  Ｓｙｓｔｅｍ」音楽情報検索の国際シンポジウム（ＩＳＭＩＲ），ｐｐ．１０７−１１５）、指紋法システムの信号対ノイズ比を大きく向上し、指紋の情報量の多い部分にラベルをつける一致判定バイナリマスクで補強されたバイナリ指紋を構築するために利用することができる。この工程のより詳細な情報は、２０１４年３月２５日に公告された米国特許第８，６８１，９５０号「Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ  Ｄａｔａｓｅｔｓ」発明者Ｋｅｖｉｎ  Ｖｌａｃｋ，Ｆｅｌｉｘ  Ｉ．Ｗｙｓｓに見ることができる。指紋は、知覚フィルタバンク値のエネルギーと時間の導関数に相当する各オーディオフレームのための１６ビットバイナリストリーム（１７の知覚フィルタバンク値と１６の連続した差異）を含む。８つの連続した指紋は、指紋同定に利用される基本単位である１つの指紋ブロック（１２８ビットと時間で１６０ミリ秒）に結合される。
【００１２】
オーディオ指紋検出システムは、多様な適用のためにオーディオファイルを認識し種々の型に分類するのに利用されることができる。このような適用は、いくつか非限定的な例を挙げると、音楽アルバムの同定、アーティストの同定、電話の呼のサブタイプ（たとえば、ライブスピーカ、留守番電話、ネットワークメッセージ、話中音）への分類を含むことができる。これらのシステムは、各オーディオファイルをオーバーラップするフレームに分割し、各フレームの指紋を抽出する。抽出された指紋は、データベースにアーカイブされ、入力された未知のオーディオストリームは、それと比較され、アーカイブされている既存のファイルとの一致の度合によって分類される。
【００１３】
指紋のアーカイブの格納方法は、指紋の一致判定と検索のための探索時間に影響を及ぼすことができる。アーカイブから一致判定する指紋の検索は高速でありかつ指紋の格納と表示方法に直接的な影響を持つ必要がある。
【００１４】
オーディオ指紋法システムは、利用可能な指紋の大量のセットを探索する能力を持たなければならない。したがって、当該システムは、探索時間を減少させ誤検出（誤った一致判定）と偽陰性（誤り）を減少させることによって指紋検出のリアルタイムパフォーマンスを向上させる最適な探索方法の恩恵を受けることができる。
【００１５】
図１は、オーディオ指紋システムのある実施形態の工程を表すフローチャートである。図１において指紋法システムの全体の流れを全体として見ることができる。ある実施形態において、スライディングバッファは、長さ１６０ミリ秒の指紋を含む。しかし、ここで述べる実施形態は、他の適用の中で、スペクトルピークと、ウェーブレット係数を利用して格納された二次元画像とを利用した他の指紋の定義に適用することができる。
【００１６】
動作１０５において、オーディオファイルが入力される。制御は動作１１０に移され、工程１００は継続する。
【００１７】
動作１１０において、オーディオファイルにフレーム分解が行われる。たとえば、入力されたオーディオファイルはオーバーラップのないデータフレームに分解されることができ、各フレームのサイズは２０ミリ秒（たとえば、８キロヘルツサンプリングと仮定すると１６０サンプル）であり、すべての完全なフレームが解析される。制御は動作１１５に移され、工程１００は継続する。
【００１８】
動作１１５において、フレームが解析を受けるか否かが判定される。フレームが解析を受けると判定された場合、制御は動作１２５に移され、工程１００は継続する。フレームが解析を受ける必要がないと判定された場合、制御は動作１２０に移され、工程１００は終了する。
【００１９】
動作１１５における判定は、任意の適切な基準に基づいて行われることができる。たとえば、フレームの完了が検査される。フレームが完了していない場合、特にフレームの最後のフラグメントが完了していない場合、そのフレームはスキップされ、解析は行われない。
【００２０】
動作１２５において、指紋が抽出される。指紋は１６ビットデジタル指紋を含むことができる。ある実施形態において、デジタル指紋は、オーディオのチャンクを代表する、音量の微細な変化とノイズの出現とに対して頑健であるバイナリ列を含む。（前述のＶｌａｃｋ特許で述べられたとおり）この頑健さをもたらすマスクされたビットのセットが利用されることができる。制御は動作１３０に移され、工程１００は継続する。
【００２１】
動作１３０において、指紋のバッファが更新される。ある実施形態において、指紋のバッファは、８つの連続したオーディオ指紋からなる指紋ブロックを得るために必要な最新の８つのオーディオフレームを格納する。指紋ブロックは、このように長さが１２８ビットであり８つの連続のオーディオセグメント（１６０ミリ秒）を同定する。制御は動作１３５に移され、工程１００は継続する。
【００２２】
動作１３５において、バッファがフルであるか否かが判定される。バッファがフルであると判定された場合、制御は動作１４０に移され、工程１００は継続する。バッファがフルでないと判定された場合、制御はバック動作１１５に移され、工程は継続する。
【００２３】
動作１３５における判定は、任意の適切な基準に基づいて行われることができる。たとえば、ひとたびバッファがフルになると、最新のオーディオ指紋に譲るためにバッファの最も古い要素は破棄される。これによって、バッファは完全な指紋ブロックを形成するのに必要な少なくとも８つの指紋を含むことが確実となる。最初の８フレームの後、最後の完全な指紋が解析されるまで、バッファは連続解析に備えて用意される。
【００２４】
動作１４０において、指紋ツリーが探索され、最新の指紋ブロックと一致する候補のリストが生成される。ある実施形態において、探索される指紋ツリーは、図３において下記にさらに詳しく開示される工程で構築されることができる。現在の指紋ブロックが既存の指紋ブロックに拡張されたと判定された場合は、以前に生成された候補との一致判定もまた拡張される。制御は動作１４５に移され、工程１００は継続する。
【００２５】
動作１４５において、一致判定が同定できるか否かが判定される。一致判定が同定できると判定された場合、制御は動作１５０に移され、探索は終了する。一致判定が同定できないと判定された場合、制御はバック動作１１５に移され、工程は継続する。
【００２６】
ある実施形態において一致宣言をするための決定は、一致が偶然生じる確率を含む一致の重要性を計算した後に行われる。この確率がある一定の閾値を下回る場合、結果が宣言される。一致の重要性は、正規分布に従うと仮定されるビット誤り率（ＢＥＲ）から計算される。ビット誤り率は、ハミング距離から計算されることができる。
【００２７】
動作１５０において、一致が返され工程は終了する。
【００２８】
図２は、指紋ツリーを生成するための工程のある実施形態を表すフローチャートである。指紋ツリーは、結果の候補のリストを生成するための図１の動作１４０において探索されることができる。
【００２９】
動作２０５において、オーディオファイルのリストがコンパイルされる。たとえば、オーディオファイルは、ＨａｉｔｓｍａとＶｌａｃｋ参考文献に前述された工程を利用してアーカイブされ、抽出されることができる。制御は動作２１０に移され、工程２００は継続する。
【００３０】
動作２１０において、指紋リストはオーディオファイルから形成される。ある実施形態において、各オーディオファイルは、４つの等しいセグメントに分割されることができ、各セグメントの先頭からの指紋ブロックは、リストに蓄積される。この手順は前述のＶｌａｃｋ特許にさらに詳しく記述されている。制御は動作２１５に移され、工程２００は継続する。
【００３１】
動作２１５において、指紋リストの再帰的なクラスタリングは、入力として選択されたツリーパラメータを用いて行われる。ある実施形態において、クラスタリングは、距離尺度としてハミング距離を用いた最近傍のＫ平均クラスタリングを利用して行われることができる。ある実施形態において、指紋マスクは、クラスタリングのこの段階では利用されない。指紋のセットのクラスタ重心は、各ビット位置における過半数のビット値を表すビット列であるように選択される。クラスタはツリーの異なる分岐に割り当てられ、クラスタ構築はある特定の深さのツリーが得られるまで繰り返されることができる。ツリーの深さと分岐ファクタはある一定の性能レベルを得るために適切に選択される。入力パラメータは、各クラスタ（またはノード）における分岐ファクタと、ツリーの最大深さとを含む。制御は動作２２０に移され、工程２００は継続する。
【００３２】
動作２２０において、指紋ツリーが生成され、工程が終了する。ある実施形態において、ツリー形成はクラスタサイズが非常に小さくなった場合に中止されてもよい。バランスの良いツリーがより有利である可能性はあるが、ツリーは、バランスが良いツリーである必要はなく、任意の形状を有することができる。各オーディオファイルのポインタやラベルは、クラスタリング工程中は指紋リストがより無作為に組み替えられるため、個々のファイルに素早くアクセスできるよう生成時にツリーに伝えられる。ある実施形態において、ツリー構築はオフライン状態で生じ、指紋探索のリアルタイムパフォーマンスには影響を及ぼさない。
【００３３】
図３は、クラスタリングのための工程のある実施形態を表すフローチャートである。クラスタリングは、図２の動作２１５における指紋ツリーの生成のために単一または多重分解能にて発生することができる。ある実施形態において、分岐ファクタと最大の深さとは、ツリーを構築するために必要な唯一のパラメータである。オーディオ指紋は良い近似値に無作為に分散するため、クラスタリング動作は指紋セット全体のタイリングを表す。ある特定のタイル中の指紋とそのすぐ近傍の指紋のみが、クラスタに分類される。図３の結果は、互いに類似した指紋がツリーのノードにおいてクラスタを形成するような指紋ツリーである。各クラスタは、ツリーがある特定の最大深さを有するまで再帰的に分解される。
【００３４】
動作３０５において、ツリーのパラメータと、データベースからの指紋とが入力される。ある実施形態において、ツリーのパラメータは、所望の正確さのレベルと探索速度のために調整することによって設定された所定の指紋のために選択される。制御は動作３１０に移され、工程３００は継続する。
【００３５】
動作３１０において、指紋リストがオーディオファイルから形成される。各オーディオファイルは、４つの等しいセグメントに分割され、各セグメントの先頭からの指紋ブロックは、リストに蓄積される。この手順は前述のＶｌａｃｋ特許においてより詳細に記述されている。制御は動作３１５に移され、工程３００は継続する。
【００３６】
動作３１５において、指紋が利用可能か否かが判定される。指紋が利用可能であると判定された場合、制御は動作３２０に移され、工程３００は継続する。指紋が利用可能でないと判定された場合、制御は動作３２５に移され、工程３００は継続する。
【００３７】
動作３１５における判定は、任意の適切な基準に基づいて行われることができる。たとえば、指紋が利用可能か否かの判定は、動作３１０において生成されたリストを通して反復処理することによって行われることができる。
【００３８】
動作３２０において、指紋は、クラスタ重心とのハミング距離を計算し、それに最も近いものを選択することによってクラスタに割り当てられる。制御は動作３１５に戻され、工程３００は継続する。
【００３９】
動作３２５において、クラスタ重心が判定される。ある実施形態において、指紋のセットの重心は、その平均の２進等価数であり、所定のクラスタ中の各指紋位置において最も頻繁に発生しているバイナリ値からなる。クラスタ重心は、動作３１５の最後に生成されたクラスタから判定される。制御は動作３３０に移され、工程３００は継続する。
【００４０】
動作３３０において、反復処理が終了したか否かが判定される。反復処理が終了したかまたは到達したと判定された場合は、制御は動作３３５に移され、工程３００は継続する。反復処理が終了していないかまたは到達していないと判定された場合は、制御は動作３１０に戻され、工程３００は継続する。
【００４１】
動作３３０における判定は、任意の適切な基準に基づいて行われることができる。たとえば、反復処理の最大回数は、あらかじめ定められることができる。この回数が得られる場合、制御は動作３３５に移される。それぞれの新規反復処理は、前回と同じ指紋リストを用いるが最新の計算されたクラスタ重心を用いて工程を繰り返す。クラスタ重心は、初期設定された指紋セットから無作為に選択することができ、形成するクラスタの数は分岐ファクタとして参照される。
【００４２】
動作３３５において、クラスタは分類されツリーの深さが増加する。ある実施形態において、ツリーの最大の深さのパラメータは、ある一定の性能レベルを得るために適切に選択されることができる。クラスタのリストが生成され、Ｋ平均法クラスタリングが各クラスタの内容に適用される。この手順は、クラスタのリストをツリーを形成するより小さなクラスタへと再帰的に分解し、ツリーがある特定の最大深さに到達するまで停止する。制御は動作３４０に移され、工程３００は継続する。
【００４３】
動作３４０において、利用可能なクラスタがあるか否かが判定される。利用可能なクラスタがあると判定された場合、制御は動作３４５に移され、工程３００は継続する。利用可能なクラスタがないと判定された場合、制御は動作３５０に移され、工程３００は継続する。
【００４４】
動作３４０の判定は、任意の適切な基準に基づいて行われることができる。ある実施形態において、クラスタのリストは利用可能なクラスタを探すために通して反復処理される。
【００４５】
動作３４５において、ツリーの深さが最大深さより小さいか否かが判定される。ツリーの深さが最大深さより小さいと判定された場合、制御は動作３１０に戻され、工程３００は継続する。ツリーの深さが最大深さより小さくないと判定された場合、制御は動作３３５に移され、工程３００は継続する。
【００４６】
動作３４５の判定は、任意の適切な基準に基づいて行われることができる。ある実施形態において、既存のクラスタからのクラスタまたは最初からのクラスタが形成される度に、その深さは１ずつ増加する。ツリー構築前の指紋リストの深さはゼロであり、所定のリストがクラスタに分解される度に、それぞれの子の深さは１ずつ増加する。ある実施形態において、ツリーの底辺のクラスタが最大深さを有する。
【００４７】
動作３５０において、深さが１と同等か否かが判定される。深さが１と同等である場合、制御は動作３５５に移され、工程３００は終了する。深さが１と同等でない場合、制御は動作３６０に移され、工程３００は継続する。
【００４８】
動作３５０の判定は、任意の適切な基準に基づいて行われることができる。ある実施形態において、根の最後の子が処理され、これが１の深さを有した後は工程が停止する。これは、ツリーの頂点における最後のクラスタを表す。
【００４９】
動作３６０において、ツリーの深さが減少する。ある実施形態において、減少は１ずつ行われることができる。この工程は、ツリーを１ステップずつ登り、そのレベルにおける次のクラスタを探索することに対応している。制御は動作３４０に戻され、工程３００は継続する。
【００５０】
多重分解能の手法のある実施形態において、各指紋は複数の分解能で格納される。ある実施形態において、少なくとも２つの分解能が使用される。たとえば１６ビットと２ビットのように、一方の分解能がより高く、もう一方の分解能がより低くてもよい。
【００５１】
ある実施形態において、ツリーは、低分解能（たとえば、３つの知覚フィルタバンクとの差異に相当する２ビット）の指紋をクラスタリングすることによって最初に分岐することができ、次により高い（１６ビット）分解能の指紋を含む個々の分岐を格納することができる。これらは、必要ならより小さなクラスタにさらに分割される。
【００５２】
認識ステップのある実施形態において、入力された各指紋はそれぞれ低分解能と高分解能で抽出される。より低分解能の指紋は前述のようにノード重心と一致判定され、所属するクラスタを同定するのに利用される。高分解能の指紋の一致判定は、適切なクラスタ内で実行される。より高い分解能において、指紋マスクはビット誤り率を計算するために利用されることができる。多重分解能ツリーの構築はオフラインであり、リアルタイムパフォーマンスに影響を及ぼさない。別の実施形態において、いくつかの分解能（２ビット、４ビット、１６ビットなど）の指紋は、階層ツリーを構築するために利用されることができる。分解能はある一定の性能レベルを得るために選択されることができる。
【００５３】
図４は、指紋認識工程のある実施形態を表すフローチャートである。ある実施形態において、認識工程は、１２８ビットを含む指紋ブロックのための工程である。ある実施形態において、クラスタをスキップするための追加の閾値パラメータを有する既存ツリーが必要である。探索は、頂点から始まり、下方に向かって葉、すなわちツリーの最下辺のメンバーに到達するまで継続する。ある実施形態において、探索は、探索が次の子に移る前にある特定のノードの全ての子が探索される深さ優先探索として構築される。閾値は、ある一定の性能レベルを得るために適切に選択されることができる。
【００５４】
動作４０５において、ツリーのパラメータと、データベースからの指紋とが入力される。ある実施形態において、ツリーのパラメータは、所望の正確さのレベルと探索速度のために調整することによって設定された所定の指紋のために選択される。制御は動作４１０に移され、工程４００は継続する。
【００５５】
動作４１０において、指紋リストが形成される。ある実施形態において、入力された（不明な）指紋は、指紋ツリーの現在の深さにおけるメンバーと一致判定される。当該深さは、ツリーの１（最小値であるが最高位に相当する）に初期設定される。制御は動作４１５に移され、工程４００は継続する。
【００５６】
動作４１５において、メンバーが利用可能か否かが判定される。メンバーが利用可能であると判定された場合、制御は動作４４５に移され、工程４００は継続する。メンバーが利用可能でないと判定された場合、制御は動作４２０に移され、工程４００は継続する。
【００５７】
動作４１５における判定は、任意の適切な基準に基づいて行われることができる。たとえば、メンバーが利用可能か否かの判定は、動作４１０中に生成されたリストを通して反復処理することによって行われることができる。
【００５８】
動作４２０において、ツリーの深さが１より大きいか否かが判定される。深さが１より大きいと判定された場合、制御は動作４３０に移され、工程４００は継続する。深さが１より大きくないと判定された場合、制御は動作４２５に移され、工程は終了する。
【００５９】
動作４２０における判定は、任意の適切な基準に基づいて行われることができる。ある実施形態において、ツリーの各メンバーはクラスタ（ノード）であり、各クラスタは１から最高値までの間の深さを有する。深さ１のすべてのメンバーを探索した後、ツリーが全探索され、さらに探索することがない。
【００６０】
動作４３０において、探索位置の深さが低減される。制御は動作４１０に移され、工程４００は継続する。
【００６１】
動作４４５において、メンバーが葉であるか否かが判定される。メンバーが葉であると判定された場合、制御は４５０に移され、工程４００は継続する。メンバーが葉でないと判定された場合、制御は動作４６０に移され、工程４００は継続する。
【００６２】
動作４４５における判定は、任意の適切な基準に基づいて行われることができる。たとえば、葉は、サブクラスタに分割されておらず、したがって子ノードがないノードとして定義されることができる。ツリーのノードは、所望の分解能で各指紋を格納する。多重分解能ツリーにおいて、ツリーのノードは、各指紋を複数の分解能において格納する。
【００６３】
動作４５０において、指紋は葉のすべてのメンバーと一致判定される。ある実施形態において、葉ノードの内側にある指紋は前述のＶｌａｃｋ特許で定義されたマスクを適用することによって検査される。ある実施形態において、ビット誤り率はマスクされたビットに対してのみ計算される。最高分解能の指紋はツリーの葉において対応するマスクを適用した後にのみ一致判定される。葉ではないクラスタを探索するために利用される指紋の分解能は、ツリーの深さによって異なる。制御は動作４５５に移され、工程４００は継続する。
【００６４】
動作４５５において、指紋の一致候補のリストが生成される。制御は動作４１５に戻され、工程４００は継続する。
【００６５】
動作４６０において、指紋は重心と比較される。ある実施形態において、ノードの重心からの指紋の距離が計算され、結果の値は、閾値と比較される。制御は動作４６５に移され、工程４００は継続する。
【００６６】
動作４６５において、一致が発見されたか否かが判定される。一致が発見されなかったと判定された場合、制御は動作４１５に移され、工程４００は継続する。一致が発見されたと判定された場合、制御は動作４７０に移され、工程４００は継続する。
【００６７】
動作４６５の判定は、任意の適切な基準に基づいて行われることができる。ある実施形態において、一致を判定するために重心と指紋間の距離が判定され、閾値と比較される。
【００６８】
動作４７０において、ツリーの深さが大きくなり、子ノードの内容が探査される。ある実施形態において、計算されたハミング距離が検査される。重心と指紋間の距離が閾値を下回る場合、すべての子ノードが順に探査される。２つのバイナリ文字列と一致判定するための累積トグル操作の回数として定義されることができるハミング距離は、高速ＸＯＲおよびポップカウントルーティンを利用して実行される。重心と指紋間の距離が閾値を超えている場合、すべての子ノードがスキップされる。制御は動作４１０に戻され、工程４００は継続する。
【００６９】
前述のＨａｉｔｓｍａの方法は、連続瞬間にわたる連続した知覚フィルタバンクの振幅の方向性差分のみを測定する。実際の値は測定しない。これら振幅の実際の値は、異なる強度のバイナリ値の並列セットを維持することによって記録される。たとえば、正の差異（または負の０ビット）から生じる１ビットは、異なる値の幅によって０または１としてさらに詳しく記述される。保持された詳細なレベルによって、追加の並列ビットストリームは、前述のＶｌａｃｋ特許に開示された方法と同様に計算された個々のマスクとともに生成される。２つの指紋がビット誤り率を下回るハミング距離を有する場合、詳細の次のレベルにおける一致判定を確認するか拒絶するために、並列詳細ビットストリーム間のハミング距離が測定される。
【００７０】
多重分解能の手法において、ツリーの各ノードは、２つ以上の分解能で指紋を格納する。探索工程は、最高ノードにある最低の分解能の指紋を一致判定し、より大きい深さにおいてより高い分解能を漸進的に使用することによって最上位から開始される。最高分解能の一致判定は葉ノードにおいてのみ行われる。入力された指紋は２つ以上の分解能にてまた利用可能でなければならないだろう。数個の分解能が存在するが、２つの分解能（２と１６、または４と１６）のみのツリーがこの手法において大変有効である場合には、多重分解能のツリーは、非常に複雑になることがある。工程４００のステップは、重心の比較がツリーの深さによってある分解能において行われる動作４６０における差異以外は不変である。動作４０５から入力されたパラメータと指紋は、利用可能な指紋の総個数を減じ、精度に悪影響を与えずに自動的に探索範囲を減じる多重分解能にて利用可能である必要がある。
【００７１】
図および前述の説明において本発明を詳細に表し、記述したが、これらは単に説明であり、特徴を限定するものではない。好ましい実施形態のみが表され、記述されていると理解すべきであって、ここに記載されている本発明の精神と、後述の保護を求める特許請求の範囲にある本発明の精神の少なくとも一方の範囲内からくるすべての均等物、変更、修正が含まれると理解すべきである。
【００７２】
ゆえに本発明の適切な範囲は、添付の特許請求の範囲の最も広い解釈によって決めるべきであり、そのようなすべての修正ならびに図面に表された事項および明細書に記載された事項と均等の関係にあるすべての事項が含まれる。
【図１】
0006587625.tif 000002
【図２】
0006587625.tif 000003
【図３】
0006587625.tif 000004
【図４】
0006587625.tif 000005