(57)【特許請求の範囲】
【請求項１】
カメラで撮った映像から抽出されたカメラ指紋をデバイスによって読み取り、
ランダムプロジェクション技術によって前記カメラ指紋の圧縮されたバージョンを計算するために、
提供される指紋照合及びカメラ識別のための方法であって、
前記計算は、センシング行列と前記カメラ指紋との乗算によって実行され、
前記センシング行列は、前記カメラ指紋のサイズより小さい行サイズを有し、
前記方法は、どのカメラが撮ったかが分かる映像から抽出されたカメラ指紋と、メモリ媒体のデータベースに格納された少なくとも１つのカメラ指紋との両方に前記センシング行列を適用する段階を提供し、
圧縮は、複数のカメラ指紋を含む前記メモリ媒体、特にデータベースに適用され、
前記方法は、前記センシング行列を生成することを可能にする、疑似乱数生成器のシードを前記データベースに格納する段階を提供し、
前記方法は、複数の圧縮された指紋のスケール不変で巡回したバージョンを前記データベースに格納する段階を提供し、
複数の圧縮された指紋の前記スケール不変のバージョンの計算は、センシング行列としてＢＣＣＢ行列、つまり巡回ブロックを含むブロック形巡回行列（Ｂｌｏｃｋ  Ｃｉｒｃｕｌａｎｔ  ｗｉｔｈ  Ｃｉｒｃｕｌａｎｔ  Ｂｌｏｃｋｓ）を用いて、２次元ＤＦＴ、つまり離散フーリエ変換によって実行され、適切にスケーリングされたランダムパターンから、すなわち前記カメラ指紋のサイズに基づき、ランダムプロジェクションを適切にクロップする且つリスケーリングすることによって取得される、
指紋照合及びカメラ識別のための方法。
【請求項２】
前記方法は、前記カメラ指紋の前記圧縮されたバージョンにスカラー量子化を適用する段階を提供し、
前記スカラー量子化は、任意の数のビット、特に１ビットで実行され得る、
請求項１に記載の方法。
【請求項３】
データベースに格納可能な一連のパラメータを用いて、基準指紋の前記ランダムプロジェクションをクロップし且つリスケーリングし、前記データベースに格納された圧縮された指紋と一致させるために提供され、
前記一連のパラメータは、クロップされる領域の位置及びサイズ、並びに圧縮されていない指紋のサイズから構成される、
請求項１に記載の方法。
【請求項４】
指紋照合及びカメラ識別用のデバイスであって、
複数のカメラ指紋を格納するメモリ媒体と通信し、請求項１から３の何れか一項に記載の方法を実行するために構成された、
デバイス。
【請求項５】
デバイスと、
メモリ媒体と、
を備え、
前記デバイスは、複数のカメラ指紋を格納する前記メモリ媒体と通信し、請求項１から３の何れか一項に記載の方法を実行するために構成される、
指紋照合及びカメラ識別のためのシステム。
【請求項６】
請求項１から３の何れか一項に記載の方法をコンピュータに実行させる、
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、指紋照合及びカメラ識別のための方法、デバイス、及びそのシステムに関する。
【背景技術】
【０００２】
画像センサの不完全性は、特定の取得デバイスを識別する一意の指紋とみなされることができ、２００９年のＪ．Ｆｒｉｄｒｉｃｈによる文献「デジタル画像鑑識（Ｄｉｇｉｔａｌ  ｉｍａｇｅ  ｆｏｒｅｎｓｉｃｓ）」に示されているように、デバイス識別、デバイスリンク、処理履歴の復元、デジタル偽造の検出などの様々な重要な鑑識作業を可能にする。最も一般的なカメラ指紋は、デジタル画像センサのＰＲＮＵ（「感度不均一性（Ｐｈｏｔｏ−Ｒｅｓｐｏｎｓｅ  Ｎｏｎ−Ｕｎｉｆｏｒｍｉｔｙ）」）である（Ｊ．Ｌｕｋａｓ、Ｊ．Ｆｒｉｄｒｉｃｈ、Ｍ．Ｇｏｌｊａｎ著の「センサの不完全性を用いたデジタル画像源の決定（"Ｄｅｔｅｒｍｉｎｉｎｇ  ｄｉｇｉｔａｌ  ｉｍａｇｅ  ｏｒｉｇｉｎ  ｕｓｉｎｇ  ｓｅｎｓｏｒ  ｉｍｐｅｒｆｅｃｔｉｏｎｓ，"  ｉｎ  Ｐｒｏｃ．  ＳＰＩＥ  Ｅｌｅｃｔｒｏｎｉｃ  Ｉｍａｇｉｎｇ，  Ｉｍａｇｅ  ａｎｄ  Ｖｉｄｅｏ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ａｎｄ  Ｐｒｏｃｅｓｓｉｎｇ，  ｖｏｌ．  ５６８５，  ２００５，  ｐｐ．  ２４９-２６０）」も参照）。
【０００３】
実際、感度不均一性パターンの形をしたセンサの不完全性は、映像とそれを取得したカメラセンサとをリンクさせるための確立された指紋技術である。ＰＲＮＵは個々のピクセルの特性におけるわずかなばらつきに起因しており、これにより、センサが撮ったあらゆる画像に影響を与えるノイズ状のさらに決定的なパターンが生じる。いくつかの研究により、ＰＲＮＵがロバストな指紋であり、不可逆圧縮及び画像サイズ変更のような処理をした後までたいてい残ることが示されている（Ｊ．Ｌｕｋａｓ、Ｊ．Ｆｒｉｄｒｉｃｈ、Ｍ．Ｇｏｌｊａｎ著の「センサのパターンノイズによるデジタルカメラ識別（"Ｄｉｇｉｔａｌ  ｃａｍｅｒａ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ｆｒｏｍ  ｓｅｎｓｏｒ  ｐａｔｔｅｒｎ  ｎｏｉｓｅ"  Ｉｎｆｏｒｍａｔｉｏｎ  Ｆｏｒｅｎｓｉｃｓ  ａｎｄ  Ｓｅｃｕｒｉｔｙ，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ，  ｖｏｌ．  １，  ｎｏ．  ２，  ｐｐ．  ２０５-２１４，  Ｊｕｎｅ  ２００６）」、及び、Ｍ．Ｃｈｅｎ、Ｊ．Ｆｒｉｄｒｉｃｈ、Ｍ．Ｇｏｌｊａｎ、Ｊ．Ｌｕｋａｓ著の「センサノイズを用いた画像源及び完全性の決定（"Ｄｅｔｅｒｍｉｎｉｎｇ  ｉｍａｇｅ  ｏｒｉｇｉｎ  ａｎｄ  ｉｎｔｅｇｒｉｔｙ  ｕｓｉｎｇ  ｓｅｎｓｏｒ  ｎｏｉｓｅ"，  Ｉｎｆｏｒｍａｔｉｏｎ  Ｆｏｒｅｎｓｉｃｓ  ａｎｄ  Ｓｅｃｕｒｉｔｙ，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ，  ｖｏｌ．  ３，  ｎｏ．  １，  ｐｐ．  ７４-９０，  Ｍａｒｃｈ  ２００８）」を参照）。
【０００４】
画像センサのＰＲＮＵは、光子を電子に変換する個々の光センサの能力の違いに起因して、各センサアレイに特有の特性であることにも留意されたい。この差異は主に、シリコンウェハーの不純物によりもたらされ、その影響はノイズパターンとなって、特定のセンサにより撮られたあらゆる画像に影響を与える。したがって、ＰＲＮＵは、特定の映像又は一連の映像を撮るのに用いられるセンサの広帯域指紋と考えられ得る。ＰＲＮＵは乗法的であり、すなわち、画像センサが均等な強度ｉで理想的に照らされ、他のノイズ源を無視できる場合、センサ出力はｏ＝ｉ＋ｉ×ｋとなり、ｋはＰＲＮＵ値の特性を示す行列を表し、ｉ×ｋは、ｉとｋとの間の要素ごとの積を示す。項目ｋは以下の特性を示す。つまり、ｋはセンサと同じピクセルサイズを有し、ｋを各センサに特有なものにするのに十分な情報を保持している。このことは、あらゆる光センサはＰＲＮＵを示すという意味では一般的である。ＰＲＮＵは、（その乗法的性質に起因して）完全に暗い映像を除き、センサにより撮られた各映像に存在する。ＰＲＮＵは、複数の異なる環境条件の下で安定しており、いくつかの信号処理演算に対してロバストである。あるセンサの特性を示すＰＲＮＵは、一連の画像（典型的には、２０〜５０個の滑らかな画像で十分）から抽出され得る。一連の映像からセンサの指紋を抽出する手順は、光センサの特性を示すのに用いられるモデルに依存する。
【０００５】
したがって、ＰＲＮＵの場合、カメラ指紋は実質的に、画像センサと同じサイズを有するパターンである。数千万ピクセルを数えるセンサを広く入手できることに起因して、数千個のセンサから成る現実的なデータベースは、１０１０個を超える個々のピクセル値を非圧縮フォーマットに格納する必要がある。さらに、大規模データベースで特定の指紋を探すという複雑性も非常に高く、典型的には、データベースの各指紋との相関関係を計算する必要がある。
【０００６】
ＰＲＮＵ指紋に関する別の問題は、基準画像がデータベースの指紋と幾何学的に整合されなくてはならないということである。可能性のある解決手法は、異なるスケーリング及び／又はクロップ係数で、同じ指紋のいくつかのバージョンを提供することであるが、さらに大規模データベースを管理するという代償を払うことになる。
【０００７】
最近、何人かの研究者が、カメラ指紋の大規模データベースの管理に関連した問題に取り組み始めた。
【０００８】
Ｍ．Ｇｏｌｊａｎ、Ｊ．Ｆｒｉｄｒｉｃｈ、Ｔ．Ｆｉｌｌｅｒ著の「カメラ指紋の大規模データベースの管理（"Ｍａｎａｇｉｎｇ  ａ  ｌａｒｇｅ  ｄａｔａｂａｓｅ  ｏｆ  ｃａｍｅｒａ  ｆｉｎｇｅｒｐｒｉｎｔｓ"，  ２０１０）」、及びＹ．Ｈｕ、Ｂ．Ｙｕ、Ｃ．Ｊｉａｎ著の「センサのパターンノイズから成る大規模データベースを用いたソースカメラ識別（"Ｓｏｕｒｃｅ  ｃａｍｅｒａ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ｕｓｉｎｇ  ｌａｒｇｅ  ｃｏｍｐｏｎｅｎｔｓ  ｏｆ  ｓｅｎｓｏｒ  ｐａｔｔｅｒｎ  ｎｏｉｓｅ"，  ２００９）という文献において、これらの著者は、いわゆる指紋ダイジェストを提案している。これは、一定数の最大指紋値及びその位置だけを保持することで動作し、これにより、結果として生じるデータベースはセンサ解像度から独立したものになる。
【０００９】
指紋ダイジェストに基づく検索手段の向上が、Ｙ．Ｈｕ、Ｃ．−Ｔ．Ｌｉ、Ｚ．Ｌａｉ、Ｓ．Ｚｈａｎｇ著の「ソースカメラ識別のための高速カメラ指紋検索アルゴリズム（"Ｆａｓｔ  ｃａｍｅｒａ  ｆｉｎｇｅｒｐｒｉｎｔ  ｓｅａｒｃｈ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｓｏｕｒｃｅ  ｃａｍｅｒａ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ"，  ２０１２）」という文献に提案されている。
【００１０】
指紋ダイジェストは、Ｍ．Ｇｏｌｊａｎ、Ｊ．Ｆｒｉｄｒｉｃｈ著の「幾何学的に歪んだ画像からの高速カメラ識別のためのセンサ指紋ダイジェスト（"Ｓｅｎｓｏｒ  ｆｉｎｇｅｒｐｒｉｎｔ  ｄｉｇｅｓｔｓ  ｆｏｒ  ｆａｓｔ  ｃａｍｅｒａ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ｆｒｏｍ  ｇｅｏｍｅｔｒｉｃａｌｌｙ  ｄｉｓｔｏｒｔｅｄ  ｉｍａｇｅｓ"，  ２０１３）」に示されるように、幾何学的に歪んだ画像の場合に、指紋登録を容易にするためにも用いられ得る。代替的な解決手法が、Ｓ．Ｂａｙｒａｍ、Ｈ．Ｓｅｎｃａｒ、Ｎ．Ｍｅｍｏｎ著の「指紋の二値化による効率的なセンサ指紋照合（"Ｅｆｆｉｃｉｅｎｔ  ｓｅｎｓｏｒ  ｆｉｎｇｅｒｐｒｉｎｔ  ｍａｔｃｈｉｎｇ  ｔｈｒｏｕｇｈ  ｆｉｎｇｅｒｐｒｉｎｔ  ｂｉｎａｒｉｚａｔｉｏｎ"，  ２０１２）」に示されるように、センサ指紋を二値量子化された形で表している。つまり、二値指紋のサイズがセンサ解像度でスケーリングされたとしても、二値化は指紋照合プロセスをかなり高速化し得る。
【００１１】
しかし、上記の引用文献の何れも、どのようにカメラ指紋データベースのサイズを大幅に縮小しながら、効果的な指紋照合及びカメラ識別プロセスを維持するかを示していない。
【００１２】
カメラ指紋データベースのサイズ縮小を可能にする、指紋照合及びカメラ識別のための方法、デバイス、及びシステムを示すことが、本発明の主目的である。
【００１３】
従来技術に対して、指紋照合及びカメラ識別プロセスの計算の複雑性を低減することが可能な、指紋照合及びカメラ識別のための方法、デバイス、及びシステムを示すことが、本発明の更なる目的である。
【００１４】
本発明のこれらの目的及び他の目的は、本明細書の重要な部分であるよう意図される添付の特許請求の範囲に請求された、指紋照合及びカメラ識別のための方法、デバイス、及びシステムによって達成される。
【００１５】
要約すれば、指紋照合及びカメラ識別のための方法が開示され、これは、ランダムプロジェクション技術、特に実数値又は量子化されたランダムプロジェクションを用いることでカメラ指紋を圧縮するために提供される。
【００１６】
さらに、巡回行列を特にその部分的な形で用いることで、ランダムプロジェクションの計算の複雑性は従来技術に対して低下している。したがって、この場合、圧縮された指紋を計算するのにＦＦＴ（「高速フーリエ変換（Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）」）を用いることが可能である。
【００１７】
本発明は、上記方法を実行するよう構成されているデバイス（特にコンピュータ）及びシステムにも言及する。
【００１８】
最後に、本発明は上記方法を実行するよう適合されたソフトウェアコードの部分を含むコンピュータ製品にも言及する。
【００１９】
本発明の更なる複数の特徴は添付の特許請求の範囲に説明されており、これらは本明細書の重要な部分であるよう意図されている。
【図面の簡単な説明】
【００２０】
上記複数の目的は、添付図面に特に関連して、指紋照合及びカメラ識別のための方法、デバイス、及びシステムに関する以下の発明を実施するための形態詳細な説明からより明らかになる。
【００２１】
【図１】本発明によるシステムを示す。
【００２２】
【図２】本発明による方法の性能データを示す。
【００２３】
【図３】本発明による方法の実験結果に関する第1のグラフを示す。
【００２４】
【図４】本発明による方法の実験結果に関する第２のグラフを示す。
【発明を実施するための形態】
【００２５】
図１を参照すると、本発明の発明を実施するための形態を説明するシステムシナリオの一例として用いられるシステム１が示されている。システム１は、デバイス３、特にコンピュータ又はスマートフォン又はタブレットと、デバイス３が関連付けられるメモリ媒体５、特にデータベース５とを備える。より詳細には、デバイス３は上記メモリ媒体５を含んでよい、又は上記メモリ媒体５はリモート位置にあり、コンピュータ３とテレマティックスを用いて接続可能である。したがって、デバイス３及びメモリ媒体５は互いに通信することができ、上記デバイス３はメモリ媒体５との間でデータの読み出し及び書き込みができる。
【００２６】
デバイス３は、以下により詳細に説明される本発明による方法を実行するよう構成され、データベース５はカメラ指紋推定値と、任意選択で同じ１つ又は複数のカメラにより取得された一連の映像とを含む。これらの画像は、指紋推定値及びそれに関連付けられた他の情報を抽出するのに用いられ得る。そのような情報は、カメラの名前及び／又はモデル及び／又は製造業者、又は本発明による圧縮方法の複数のパラメータであってよい。このように、上記カメラ指紋推定値は本発明の方法に従って圧縮されてよい。
【００２７】
指紋照合及びカメラ識別では、基準画像又は一連の画像（その画像を撮ったカメラが分かっていることが望ましい）が、その指紋を抽出するために処理される。目標は、データベース５に格納されたどのデバイス、すなわちカメラ（存在すれば）が与えられた映像（１つ又は複数の基準画像）を取得したかを決定することである。実質的に、１つ又は複数の基準画像の圧縮された指紋と全ての指紋推定値との間で相関演算が計算され、ある指紋が十分大きい相関関係をもたらす場合、それは正しいと断言される。
【００２８】
１つの画像又は一連の画像から指紋を抽出する場合、典型的にはＰＲＮＵが計算される。
【００２９】
本発明の方法は、わずかな情報損失で、又は理想的には情報損失がなく、指紋データベースを圧縮することを目指している。なぜなら、今日では、データベースのサイズが急激に増大し得るからである。上記方法は、ランダムプロジェクション（ＲＰ）技術に基づいている。ＲＰ技術は、次元削減のための、複雑性が低く強力な方法である。ＲＰの考え方は、ランダム行列
【数１】
0006780220.tif 000002
を用いて、元のｎ次元のデータをｍ次元の部分空間に投影することであり、ｍ＜ｎである。したがって、Ｎ個のｎ次元のデータ
【数２】
0006780220.tif 000003
の集合が、次式によって１つのｍ次元の部分空間
【数３】
0006780220.tif 000004
に削減される。
【数４】
0006780220.tif 000005
【００３０】
ＲＰを支持する主要特性は、高次元ユークリッド空間から低次元ユークリッド空間への歪みの少ない複数の点の埋め込みに関する、Ｊｏｈｎｓｏｎ-Ｌｉｎｄｅｎｓｔｒａｕｓｓの補題である。この補題は、複数の点の間の距離がほとんど維持されるような方法で、高次元空間の小規模の点がはるかに低次元の空間に埋め込まれ得るということを示している。
【００３１】
そのような前提で、本発明の方法は、カメラによって撮られた映像から抽出されたカメラ指紋を、デバイス３を通じて読み取る及び／又は取得する段階と、ランダムプロジェクションによって、すなわちセンシング行列と上記カメラ指紋との間の乗算によって、上記カメラ指紋の圧縮されたバージョンを計算する段階とを提供し、上記センシング行列は上記カメラ指紋より小さい行サイズを有する。
【００３２】
映像／画像は行列であり、列ごとに映像／画像の行列を読み取ることで取得された列ベクトルとして表現でき、同じ映像／画像から抽出された（圧縮されてない）カメラ指紋は同様に列ベクトルとして表現でき、映像／画像と同じ映像／画像から抽出された（圧縮されてない）カメラ指紋とは同じサイズを有する、すなわち、２つの対応する列ベクトルは同じ数の要素を有することに注意すべきである。
【００３３】
より詳細には、センシング行列は、好ましくはランダムな巡回行列、特にランダムな部分的巡回行列であり得る。用語「巡回」とは、行列の行が、第１行を巡回的にシフトしたバージョンであることを意味している。用語「部分的」とは、上記カメラ指紋のサイズより小さいセンシング行列、すなわち、列より行が少ない矩形行列の行サイズを意味している。用語「ランダム」とは、センシング行列の第１行が、選択の分布に従って生成された確率変数（例えば、ガウス確率変数）を含むという事実を意味している。
【００３４】
他のタイプのセンシング行列、例えば、独立同一分布（ｉ．ｉ．ｄ．）ガウス確率変数、又はｉ．ｉ．ｄ．ラデマッハー確率変数、又はベルヌーイ確率変数、又は決定的なセンシング行列でさえも含む完全ランダム行列が用いられ得る。
【００３５】
以下に、本発明による圧縮方法を用いた応用、すなわち、本発明の圧縮方法を、ランダムプロジェクションに基づき、どのように指紋照合及びカメラ識別などの鑑識作業に適用するかが説明されている。図１のシステム１、特にデバイス３がコンピュータであることが仮定されていることにも注意すべきである。
［指紋照合］
【００３６】
指紋照合問題が、複数の指紋推定値と、同じカメラで取得された、指紋推定値を抽出するのに用いられ得る一連の映像とから成るデータベース５とともに示されている。
【００３７】
ＰＲＮＵパターンとして取得される複数のカメラ指紋は、白色ガウスノイズとして近似され得る。これは、照合システムの性能を研究する文献で検討された典型的な前提である。これにはいくつかの重要な結果がある。第1に、ＰＲＮＵパターンは標準的な方法（例えば、ＪＰＥＧ圧縮）では圧縮されることができない。なぜなら、これらは、圧縮を実行するのに利用され得る冗長性を欠いているからである。さらに、指紋は互いに非常に一貫性を欠いている。一貫性のなさにより、２つの指紋は相関関係が非常に低い、又は言い換えれば、ｎ次元空間の点として指紋を表すと、任意の２つの指紋の間の角度は広く、直交性に近いことが意味される。指紋照合では、Ｎ個の既知のカメラの指紋ディクショナリが構築され、これは行列
【数２】
0006780220.tif 000006
として表され得る。典型的な指紋照合問題の目標は、コンピュータ３に提供されている基準指紋
【数５】
0006780220.tif 000007
と最も類似した列を見つけることである（なぜなら、データベース５では、各カメラ指紋が列ベクトルであるからである）。明確にするために、基準指紋
【数１２】
0006780220.tif 000008
は、画像から抽出されたカメラ指紋であり、その画像を撮ったカメラ（名前、モデル、製造業者など）を分かっていることが望ましい。
【００３８】
このために、最も用いられる類似度基準の１つが相関係数である。この説明において、サンプル反射相関ρが以下のように検討され、定義される。
【００３９】
【数６】
0006780220.tif 000009
ここで、ｄｉはディクショナリＤに属するｉ番目の指紋であり、
【数７】
0006780220.tif 000010
項はスカラー積であり、
【数８】
0006780220.tif 000011
であり、
【数９】
0006780220.tif 000012
である。
【００４０】
したがって、本発明による方法は、データベース５全体の圧縮を提供し、基準指紋
【数１２】
0006780220.tif 000013
は少数のランダムプロジェクションによってそれらを表す。この演算は、ｍ×ｎのセンシング行列Φとの積として理解され得る。
【数１０】
0006780220.tif 000014
【数１１】
0006780220.tif 000015
ここで、Ａはデータベース５に含まれるカメラ指紋の圧縮されたディクショナリであり、Ｄはデータベース５に含まれるカメラ指紋の元のディクショナリであり、ｙは基準指紋
【数１２】
0006780220.tif 000016
の圧縮された指紋である。
【００４１】
ランダムプロジェクションがデータベースに含まれる一連の指紋の形状をほぼ維持しているという事実のおかげで、ランダムプロジェクションは指紋の空間の次元を効果的に削減し得る。ランダムプロジェクションは任意の２つの指紋の間の角度をほぼ維持しているので、且つこの角度は、指紋の一貫性を欠いた性質のおかげで広いので、圧縮方法はロバストな性能を示すとともに、問題の大きさを著しく減少させる。本方法は、圧縮されたディクショナリＡをデータベース５に格納する段階と、同じセンシング行列Φを用いて、基準パターン（例えば、基準指紋
【数１２】
0006780220.tif 000017
）が示されるときは常に圧縮された指紋を生成する方法とを提供する。データベース５のサイズを制限するために、センシング行列Φ全体ではなく、センシング行列Φを生成することを可能にする疑似乱数生成器のシードだけを格納することが求められ得る。実際、データベース５に格納された異なる複数の指紋が、異なる複数のセンシング行列Φによって取得されていることは全く可能であり、これにより、センシング行列全体が格納された場合に、データベース５のサイズが増加するであろう。
【００４２】
すでに言及されたように、センシング行列Φの選択は非常に重要であり、実際に、独立同一分布（ｉ．ｉ．ｄ．）ガウス確率変数又は巡回行列又はその他を含むセンシング行列を用いることが可能である。ガウス行列は、形状維持に関して最高性能を提供し得るが、大規模な問題における使用をかなり複雑にするいくつかの欠点を示す。
【００４３】
第1に、シードからセンシング行列Φを生成するのにかかる時間を考慮することが重要である。実際にｎｍ個の乱数を生成する必要があり、ｎが数百万のオーダーである場合、著しく時間がかかり得る。実際には、言及されたように、センシング行列Φ全体を格納することは、過大なメモリを必要とするので、一般的に言ってできない。そのため、疑似乱数生成器のシードだけが格納され、センシング行列Φがオンザフライで毎回生成される。
【００４４】
第２に、ベクトル乗算による完全行列がディクショナリＤの複数の列のそれぞれに、すなわち複数の指紋のそれぞれに実行されなければならない。そのような演算は、多くの時間と高い計算の複雑性とを必要とする。そのような問題を回避するため、部分的な巡回行列を用いるのがより望ましい。そのような行列はランダムに（例えば、ｉ．ｉ．ｄ．ガウス変数を用いて）第１行を生成し、その他の全ての行は第１行を巡回的にシフトさせただけのバージョンである。巡回行列がほぼ完全なランダムガウス行列を実行し、Ｊｏｈｎｓｏｎ-Ｌｉｎｄｅｎｓｔｒａｕｓｓの補題の証明、及びＲＩＰ（「制限付等長性（Ｒｅｓｔｒｉｃｔｅｄ  Ｉｓｏｍｅｔｒｙ  Ｐｒｏｐｅｒｔｙ）」）の証明が、そのような行列に利用可能であることを、性能分析が示している。巡回行列が大きな利点を提供するのは、第１行をランダムに生成するだけでよいからであり、且つＦＦＴ（「高速フーリエ変換（Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）」）によって高速乗算が利用可能であるからである。ＦＦＴを用いるおかげで、センシング行列Φと指紋Ｄのディクショナリとの積は、完全ランダムｉ．ｉ．ｄ．行列により必要とされるＯ（Ｎｍｎ）の代わりに、Ｏ（Ｎｎｌｏｇｎ）演算を用いて実行され得る。ここで、ＮはＤの列の数、すなわちデータベース５のカメラの数であり、ｍはセンシング行列Φの行の数、すなわち圧縮された指紋のサイズであり、ｎはセンシング行列Φの列の数、すなわち圧縮されていない指紋のサイズである。
【００４５】
本発明の方法は、スカラー量子化をカメラ指紋の圧縮されたバージョンに適用する段階も提供し、スカラー量子化は任意の数のビットで、特に１ビットで実行され得る。圧縮カメラ指紋が１ビットで量子化される場合は、二値量子化とみなされる。
【００４６】
したがって、さらなる圧縮は、圧縮された指紋に浮動小数点値を保持する代わりに、圧縮された指紋を量子化することで達成され得る。さらに、１ビットの圧縮センシングの分野では、二値量子化によるランダムプロジェクションが、複数の信号間の角度をほぼ維持する埋め込みを実行することに留意されたい。角度の維持は照合問題の最大の関心事なので、次式で取得される、二値量子化によるランダムプロジェクションの場合を検討することも可能である。
【数１３】
0006780220.tif 000018
【００４７】
二値量子化で圧縮された指紋の場合において、相関係数は、基準距離としてハミング距離で置き換えられる。
【００４８】
したがって、圧縮された指紋の二値量子化は、例えばデータベース５のさらなる圧縮を可能にする。
【００４９】
元の角度が広いので、一致しない指紋からのハミング距離は、正しい指紋からの距離（理想的には０）よりはるかに大きくなる傾向がある。二値ランダムプロジェクションは大幅に圧縮することを可能にし、その一方で性能劣化は限定され、二値化に起因する劣化は小さく、スペースに関して著しい増加を取得することを可能にする。さらに、ハミング距離の計算は、非常に高速且つ効率的な演算である。
［カメラ識別］
【００５０】
カメラ識別問題は、指紋照合シナリオと概念的に非常に類似している。主な差異は、１つの基準画像が一連の画像の代わりに利用可能であるということである。この問題の最適類似度基準は、画像の残留ノイズとデータベースに格納された指紋の調整バージョンとの間の相関であり、調整項は基準画像であることに留意されたい。この基準を圧縮領域まで、すなわち本発明の方法まで拡張することは、基準画像とデータベースの複数の指紋との要素ごとの積により、不可能である。
【００５１】
したがって、この場合、本発明の方法は、圧縮領域に容易にマッピングされ得る２つの簡略化した類似度基準を用いる段階を提供する。
【００５２】
第1の簡略化した基準は、基準画像Ｉｔの残留ノイズｗとデータベース５に格納された複数の指紋との相互関係を示す。実質的に、この手法は基準画像Ｉｔの調整効果を除去する。したがって、この手法は、基準画像Ｉｔが一定のパターンでない限り準最適になる。どのカメラが撮ったかが分かっていることが望ましい基準画像Ｉｔの残留ノイズｗと、データベース５に格納された少なくとも１つの指紋との両方にセンシング行列Φを適用して、次式で示されるように、この基準を圧縮領域に移動させれば十分である。
【数１４】
0006780220.tif 000019
ここで、ρは式（２）で定義された相関係数であり、ｄｉはデータベース５のディクショナリＤに属するｉ番目の指紋である。
【００５３】
第２の簡略化した基準は、残留ノイズｗの代わりに１つの基準画像Ｉｔから抽出された指紋推定値
【数１２】
0006780220.tif 000020
の使用を検討する。次に第２基準は、次式で示されるように、この基準指紋推定値
【数１２】
0006780220.tif 000021
とディクショナリＤに格納された指紋との相互関係を示す。
【数１５】
0006780220.tif 000022
［性能分析］
【００５４】
以下に、本発明による指紋照合及びカメラ識別の方法により取得された性能が説明されている。
【００５５】
照合問題は、基準圧縮パターンと最も良く一致する、ディクショナリの列を見つけることに関係している。圧縮された基準指紋は、圧縮されたディクショナリの列ごとに二値仮説検定を受ける。２つの仮説が次のように定義されている。
Ｈ０（帰無仮説）：圧縮された基準指紋及び列参照は、同じカメラからのものではない。
Ｈ１（対立仮説）：圧縮された基準指紋及び列参照は、同じカメラからのものである。
【００５６】
帰無仮説は、基準距離（相関係数又はハミング距離）が予め定義された閾値τより上である場合は常に棄却される。この説明では、異なる事象を指すのに以下の呼称が用いられる。・フォールスアラーム：帰無仮説が間違って棄却された。・ディテクション：帰無仮説が正しく棄却された。・コレクトディテクション：帰無仮説が、正しいカメラにだけ棄却された。・フォールスディテクション：帰無仮説が、少なくとも１つの誤ったカメラに棄却された。
【００５７】
そのような分析に用いられるデータベースは、ドレスデン（Ｄｒｅｓｄｅｎ）画像データベースである。そのようなデータベースは、屋内環境及び屋外環境からのフラットフィールド画像とシーンとの両方から成る。フラットフィールド及びナチュラルフォトの両方を有する５３個のカメラが選択されている。データベースは、高品質の指紋を持つためにフラットフィールド画像から作成され、基準画像はナチュラルシーンから撮られている。ナチュラルフォトは、様々な詳細及び照明条件を示す。全ての写真が、同じセンサ方位に登録されている。
【００５８】
図２を参照すると、様々な条件下で、ドレスデンデータベースのバイト単位のサイズを含む表が示されている。参照番号７の「単精度」と呼ばれる第1列は、単精度（ＩＥＥＥ７５４規格に基づく３２ビット）浮動小数点値を有する圧縮された指紋を指し、参照番号９の「二値（１ビット）」と呼ばれる第２列は、圧縮された指紋の二値量子化を指す。項ｍは、センシング行列Φの行の数、したがって圧縮された指紋のサイズを表す。
【００５９】
圧縮されたデータベースのサイズが、同じデータベースの圧縮されていないバージョンよりはるかに小さいことに気づくのは容易である。さらに、ランダムプロジェクションの二値量子化が適用される場合、圧縮はさらに進む。
【００６０】
図３及び図４を参照すると、ＲＯＣ（「受信者動作特性（Ｒｅｃｅｉｖｅｒ  Ｏｐｅｒａｔｉｎｇ  Ｃｈａｒａｃｔｅｒｉｓｔｉｃ）」）曲線が、圧縮された指紋の要素の数ｍでパラメータ化されて示されている。
【００６１】
特に図３は、フォールスアラーム確率ＰＦＡ（横座標）とディテクション確率ＰＤ（縦座標）との関係を示す。参照番号１１の曲線は圧縮されていないデータベースを指し、参照番号１３の曲線は、本発明の方法によって二値量子化及びｍ＝３２０００で圧縮されたデータベースを指す。
【００６２】
図４は、フォールスディテクション確率ＰＦ（横座標）とコレクトディテクション確率ＰＣ（縦座標）との関係を示す。参照番号１５の曲線は圧縮されていないデータベースを指し、参照番号１７の曲線は、本発明の方法によって二値量子化及びｍ＝６４０００で圧縮されたデータベースを指す。
【００６３】
図３及び図４から、二値ランダムプロジェクションが良好な性能を持つことが実験的に検証されている。実数値の圧縮された指紋（量子化なし）に対する差は、記憶容量及び照合演算の複雑性に関する著しい節約と比べると小さい。概して、ｍ個の二値量子化されたランダムプロジェクションを用いるプロセスは、ｍ／２個の実数値のランダムプロジェクションを用いるプロセスのＲＯＣとほとんど重なり合うＲＯＣを示すことが観察されている。したがって、二値量子化されたランダムプロジェクションを用いる場合、経験則として、圧縮された指紋の要素の数には、2倍のペナルティが考慮されなければならない。しかし、記憶容量の必要条件が１／６４に削減されるので（倍精度の圧縮された指紋の場合）、二値量子化されたランダムプロジェクションは、極めて競争力のある性能を示す。
［スケーリング及び巡回］
【００６４】
本発明による方法は、別の態様、すなわち圧縮された指紋のスケール不変で巡回したバージョンを、特にそれをデータベース５に格納するために考慮する。
【００６５】
これまでに説明されたことは、各カメラセンサが１つのエントリに関連付けられる場合、圧縮された指紋のディクショナリの作成を考慮している。この考えの拡張は、スケーリング又は最も一般的な巡回などの変換に対する本方法のロバスト性を向上させるべく、複数のエントリを同じカメラセンサに関連付けることで可能である。このことは、計算時間とメモリとの間のトレードオフを表している。なぜなら、変換されたパターンのランダムプロジェクションは、照合時に基準指紋の変換を何も実行しないように格納されるからである。このディクショナリの構成は、「冗長ディクショナリ」と呼ばれる。
【００６６】
この態様において、本方法の目標は、ランダムプロジェクションをスケーリング変換に対してロバストにすることであり、これにより、スケーリングされた写真が示された場合、システム１は、ＰＲＮＵパターンのランダムプロジェクションのデータベース５を保持して、クエリパターンのランダムプロジェクションを計算するだけで、その写真を取得した画像センサを正しく識別し得る。この目標を達成するには、スケーリングに関する情報が圧縮領域にマッピングされていることが必要とされる。従って、圧縮される指紋のベクトル化されたバージョンを用いる代わりに、２次元表現が検討され、ＢＣＣＢ（「巡回ブロックを含むブロック形巡回行列（Ｂｌｏｃｋ  Ｃｉｒｃｕｌａｎｔ  ｗｉｔｈ  Ｃｉｒｃｕｌａｎｔ  Ｂｌｏｃｋｓ）」）センシング行列が用いられる。ＢＣＣＢセンシング行列を用いることで、圧縮された指紋のスケーリングに関する情報を維持し、２次元ＤＦＴ（「離散フーリエ変換（Ｄｉｓｃｒｅｔｅ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）」）によって上記圧縮された指紋の計算を効率的に実行することが可能になる。ランダムＢＣＣＢ行列はＲＩＰを満たす。
【００６７】
したがって、この場合、本発明による方法は、適切にスケーリングされたランダムパターンから取得されたＢＣＣＢ行列をセンシング行列Φとして用いる２次元ＤＦＴによって、すなわち、圧縮されるサイズｎｘ×ｎｙの指紋（カメラ指紋）に基づいて、そしてランダムプロジェクションを適切にクロップしリスケーリングすることによって、圧縮された指紋のスケール不変バージョンの計算が実行されることを規定する。本方法は、データベース５に格納された一連のパラメータを用いて、基準指紋のランダムプロジェクションを正しくクロップしてリスケーリングし、データベース５に格納された圧縮された指紋と一致させる技術も提供する。上記パラメータは、クロップされる領域の位置及びサイズ、並びに圧縮されていない指紋のサイズから構成されるのが好ましい。
【００６８】
圧縮されたデータベースのエントリを作成する手順は以下の通りである。
・サイズｎｘmax×ｎｙmaxのランダムパターンφ（ｉ．ｉ．ｄ．ガウス）を作成する。サイズは、システム１が処理する最大センササイズと一致する。
・サイズｎｘ×ｎｙのカメラ指紋Ｋが与えられると、圧縮された指紋を以下の方法で計算する。
−  φをｎｘ×ｎｙにサイズ変更してφ´を得る。
−  ランダムプロジェクションを、Ｙ＝ＩＤＦＴ２［ＤＦＴ２［Ｋ］ＤＦＴ２［φ´］］として計算する。これは、第１行がベクトル化されたバージョンのφ´であるＢＣＣＢ行列を用い、それをベクトル化されたバージョンのＫに乗じることに相当する。
−  サイズｍｘ×ｍｙのＹの隣接領域をクロップし、Ｙの任意にサイズ変更されたバージョンから同じ領域をクロップする方法を格納する（例えば、常に左上隅をクロップし、比率ｍｘ／ｎｘ及びｍｙ／ｎｙを格納する）。
【００６９】
基準指紋からの照合プロセスは以下の通りである。
・サイズｎ´ｘ×ｎ´ｙの基準指紋Ｋ´が与えられると、以下の方法で圧縮された指紋を計算する。
−  φをｎ´ｘ×ｎ´ｙにサイズ変更してφ´を得る。
−  ランダムプロジェクションを、Ｙ´＝ＩＤＦＴ２［ＤＦＴ２［Ｋ´］ＤＦＴ２［φ´］］として計算する。
−  データベース内と同じＹ´の隣接領域をクロップする（例えば、その領域が左上であった場合には、（ｍｘ／ｎｘ）ｎ´ｘ×（ｍｙ／ｎｙ）ｎ´ｙピクセルをクロップする）。
−  クロップされた領域をｍｘ×ｍｙにサイズ変更する。
・ディクショナリの現行のエントリとの相関関係を計算する。
【００７０】
基準指紋のクロップされたランダムプロジェクションのサイズ変更は、ｍｘ／ｎｘ及びｍｙ／ｎｙの異なる値により、ディクショナリのあらゆるエントリに対してやり直されなければならないことに留意されたい。
【００７１】
二値量子化された圧縮された指紋の場合、データベース５は、二値量子化されたバージョンのランダムプロジェクションを格納する。照合段階の間に、クロップされた圧縮された基準指紋はサイズ変更され、次に量子化される。最後に、ハミング距離が類似度基準として用いられるのが好ましい。
【００７２】
基準画像が回転を受けた場合にカメラを検出できるように、本発明の方法は、最も一般的な回転を含む、回転し反転したバージョンの指紋のランダムプロジェクションをディクショナリに含める段階を提供する。一例として、以下の変換、つまり９０°回転、１８０°回転、２７０°回転、上下を反転、左右を反転に対応する複数の圧縮された指紋を含めたいかもしれない。好ましくは、元の指紋を含む合計８つの組み合せが可能である。
【００７３】
本発明の複数の特徴、及びそれらの複数の利点は上記説明から明らかである。
【００７４】
本発明による指紋照合及びカメラ識別の方法の第1の利点は、カメラ指紋データベースのサイズを縮小することが可能であるということである。
【００７５】
本発明による指紋照合及びカメラ識別の方法の第２の利点は、従来技術に対して、指紋照合及びカメラ識別プロセスの計算の複雑性を低減することが可能であるということである。
【００７６】
本発明による指紋照合及びカメラ識別の方法の更なる利点は、指紋照合プロセスの間に拡張性を有することが可能であるということである。用語「拡張性」には、データベース５の検索に関する計算の複雑性、及びデータベース５とデバイス３との間の通信に必要とされる帯域幅に最適に適合するように、圧縮された指紋が任意の長さにトリミングされ得るという意味がある。
【００７７】
本明細書に例として説明される指紋照合及びカメラ識別の方法、デバイス、及びシステムは、本発明の概念の新規性から逸脱することなく、多くの可能な変形を受けてよい。本発明の実際の実装では、例示された詳細は異なる形態を有してよく、又は他の技術的に同等の要素と置き換えられてもよいことも明らかである。
【００７８】
従って、本発明は、指紋照合及びカメラ識別の方法、デバイス、及びシステムに限定されるものではなく、以下の特許請求の範囲に明確に規定されている本発明の概念から逸脱することなく、多くの修正、改善、又は同等なパーツ及び要素の置換を受けてよいことが容易に理解され得る。
本実施形態の例を下記の各項目として示す。
［項目１］
カメラで撮った映像から抽出されたカメラ指紋をデバイスによって読み取り、
ランダムプロジェクション技術によって前記カメラ指紋の圧縮されたバージョンを計算するために、
提供される、
指紋照合及びカメラ識別のための方法。
［項目２］
前記計算は、センシング行列と前記カメラ指紋との乗算によって実行され、
前記センシング行列は、前記カメラ指紋のサイズより小さい行サイズを有する、
項目１に記載の方法。
［項目３］
前記センシング行列は巡回行列である、
項目２に記載の方法。
［項目４］
前記センシング行列は、独立同一分布ガウス確率変数を含む、
項目２又は３に記載の方法。
［項目５］
前記センシング行列は、独立同一分布ラデマッハー確率変数を含む、
項目２から４の何れか一項に記載の方法。
［項目６］
前記センシング行列は、独立同一分布ベルヌーイ確率変数を含む、
項目２から４の何れか一項に記載の方法。
［項目７］
前記センシング行列と前記カメラ指紋との前記乗算は、ＦＦＴ、つまり高速フーリエ変換を用いて実行される、
項目２から６の何れか一項に記載の方法。
［項目８］
前記方法は、前記カメラ指紋の前記圧縮されたバージョンにスカラー量子化を適用する段階を提供し、
前記スカラー量子化は、任意の数のビット、特に１ビットで実行され得る、
項目１から７の何れか一項に記載の方法。
［項目９］
前記方法は、どのカメラが撮ったかが分かることが望ましい基準画像の残留ノイズと、メモリ媒体、特にデータベースに格納された少なくとも１つの指紋との両方に前記センシング行列を適用する段階を提供する、
項目２に記載の方法。
［項目１０］
圧縮は、複数のカメラ指紋を含む前記メモリ媒体、特にデータベースに適用され、
前記方法は、前記センシング行列を生成することを可能にする、疑似乱数生成器のシードを前記データベースに格納する段階を提供する、
項目９に記載の方法。
［項目１１］
前記方法は、複数の圧縮された指紋のスケール不変で巡回したバージョンを前記データベースに格納する段階を提供する、
項目１０に記載の方法。
［項目１２］
複数の圧縮された指紋の前記スケール不変のバージョンの計算は、センシング行列としてＢＣＣＢ行列、つまり巡回ブロックを含むブロック形巡回行列（Ｂｌｏｃｋ  Ｃｉｒｃｕｌａｎｔ  ｗｉｔｈ  Ｃｉｒｃｕｌａｎｔ  Ｂｌｏｃｋｓ）を用いて、２次元ＤＦＴ、つまり離散フーリエ変換によって実行され、適切にスケーリングされたランダムパターンから、すなわち前記カメラ指紋のサイズに基づき、ランダムプロジェクションを適切にクロップする且つリスケーリングすることによって取得される、
項目１１に記載の方法。
［項目１３］
データベースに格納可能な一連のパラメータを用いて、基準指紋の前記ランダムプロジェクションをクロップし且つリスケーリングし、前記データベースに格納された圧縮された指紋と一致させるために提供され、
前記一連のパラメータは、クロップされる領域の位置及びサイズ、並びに圧縮されていない指紋のサイズから構成される、
項目１２に記載の方法。
［項目１４］
指紋照合及びカメラ識別用のデバイスであって、
複数のカメラ指紋を格納するメモリ媒体と通信し、項目１から１３の何れか一項に記載の方法を実行するために構成された、
デバイス。
［項目１５］
デバイスと、
メモリ媒体と、
を備え、
前記デバイスは、複数のカメラ指紋を格納する前記メモリ媒体と通信し、項目１から１３の何れか一項に記載の方法を実行するために構成される、
指紋照合及びカメラ識別のためのシステム。
［項目１６］
項目１から１３の何れか一項に記載の方法をコンピュータに実行させる、
プログラム。
【図１】
0006780220.tif 000023
【図２】
0006780220.tif 000024
【図３】
0006780220.tif 000025
【図４】
0006780220.tif 000026