用于指纹匹配和相机识别的改进的方法、设备和系统

摘要

描述了一种用于指纹匹配和相机识别的方法，其中该方法被提供为通过设备读取从由相机拍摄的图片所提取的相机指纹，并且通过随机投影技术计算所述相机指纹的压缩版本。

说明书

技术领域

本发明涉及用于指纹匹配和相机识别的方法、其设备和系统。

背景技术

成像传感器缺陷可以被考虑为识别特定采集设备、使能各种重要的司法鉴定(forensic)任务(诸如，设备识别、设备链接、恢复处理历史、检测数字伪造)的独特的指纹，如在J.Fridrich的文献“Digital image forensics”,2009中所示的那样。最常见的相机指纹是数字成像传感器的PRNU(“光响应不均匀性”)(还参见J.Lukas,J.Fridrich和M.Goljan,“Determining digital image origin using sensor imperfections,”inProc.SPIE Electronic Imaging,Image and Video Communication and Processing,vol.5685,2005,pp.249–260)。

实际上，形式为光响应不均匀性图案的传感器缺陷是将图片链接到获取图片的相机传感器的完善的指纹识别(fingerprinting)技术。PRNU是由于单独的像素的性质的微小变化，这产生影响由传感器拍摄的每一个图像的类似于噪声的但是确定性的图案。多项工作已经展示PRNU是鲁棒的指纹，一般耐受如有损压缩和图像重新调整大小这样的处理(参见J.Lukas,J.Fridrich和M.Goljan,“Digital camera identification from sensorpattern noise”Information Forensics and Security,IEEE Transactions on,vol.1,no.2,pp.205–214,2006年6月,以及M.Chen,J.Fridrich,M.Goljan和J.Lukas,“Determining image origin and integrity using sensor noise”,InformationForensics and Security,IEEE Transactions on,vol.3,no.1,pp.74–90,2008年3月)。

还注意到的是，由于每一个单独的光学传感器将光子转换成电子的不同能力，成像传感器的PRNU是每一个传感器阵列独特的性质。该不同主要是由硅晶片中的杂质引起的，并且它的效果是影响由那个特定的传感器拍摄的每一个图像的噪声图案。因此，PRNU可以被认为是用于拍摄特定图片或图片的集合的传感器的宽带指纹。PRNU是可乘的，即，如果成像传感器用均匀强度i理想地照亮，忽略其他噪声源，那么传感器的输出将是o＝i+i·k，其中k代表表征PRNU值的矩阵，并且i·k表示i和k之间的按元素的积。项k展现出下面的性质：项k具有与传感器相同的像素大小，并且携带足够的信息以使其对于每个传感器而言是独特的。从这个意义上来说，普遍的是，每一个光学传感器展现出PRNU。它存在于由传感器拍摄的每一个图片中，除了完全黑的图片之外(由于其可乘的本质)。它在不同的环境条件下是稳定的，并且它对几种信号处理操作是鲁棒的。可以从图像的集合(通常，20到50个平滑图像是足够的)提取表征一个传感器的PRNU。从图片的集合提取传感器的指纹的过程依赖于用来表征光学传感器的模型。

因此，在PRNU的情况下，相机指纹实质上是具有与成像传感器相同的大小的图案。由于对数千万个像素进行计数的传感器的广泛可用性，几千个传感器的实际的数据库将要求以未压缩的格式储存多于10¹⁰个单独的像素值。此外，在大的数据库中查找特定的指纹的复杂度也非常高，通常要求计算与数据库中的每一个指纹的相关性。

PRNU指纹的另一个问题是测试图像应该与数据库中的指纹几何地对齐。可能的解决方案是提供具有不同缩放因子和/或裁剪因子的相同指纹的几个版本，然而代价是管理甚至更大的数据库。

最近，几位作者开始解决与相机指纹的大的数据库的管理有关的问题。

在文献M.Goljan,J.Fridrich和T.Filler,“Managing a large database ofcamera fingerprints”,2010以及Y.Hu,B.Yu和C.Jian,“Source camera identificationusing large components of sensor pattern noise”,2009中，作者提出所谓的指纹摘要，其通过仅保留固定数量的最大指纹值和它们的位置而工作，以便所产生的数据库独立于传感器分辨率。

在文献Y.Hu,C.-T.Li,Z.Lai和S.Zhang,“Fast camera fingerprint searchalgorithm for source camera identification”,2012中提出了基于指纹摘要的改进的搜索策略。

指纹摘要还可以用来在几何失真图像的情况下使指纹注册变得容易，如在M.Goljan和J.Fridrich,“Sensor fingerprint digests for fast cameraidentification from geometrically distorted images”,2013中所示的那样。可替代的解决方案是以二进制量化的形式表示传感器指纹，如在S.Bayram,H.Sencar和N.Memon,“Efficient sensor fingerprint matching through fingerprint binarization”,2012中所示的那样：尽管二进制指纹的大小随传感器分辨率缩放，但是二进制化可以可观地加速指纹匹配处理。

然而，上面引用的文献没有一个指示如何在维持有效的指纹匹配和相机识别处理的同时显著地减小相机指纹数据库大小。

本发明的主要目标是指示允许减小相机指纹数据库大小的用于指纹匹配和相机识别的方法、设备和系统。

本发明的进一步的目标是指示允许相对于现有技术降低指纹匹配和相机识别处理的计算复杂度的用于指纹匹配和相机识别的方法、设备和系统。

本发明的这些和其它目标是通过用于指纹识别和相机识别的方法、设备和系统来实现的，如在所附权利要求中所请求保护的那样，其旨在成为本说明书的组成部分。

发明内容

简而言之，公开了用于指纹匹配和相机识别的方法，其中该方法被提供为通过使用随机投影技术、尤其是实值(real-valued)或量化随机投影来压缩相机指纹。

此外，相对于现有技术，通过使用循环矩阵、尤其是其部分形式，已经减少了计算随机投影的复杂度。因此，在这种情况下，可以使用FFT(“快速傅里叶变换”)来计算压缩的指纹。

本发明还涉及被配置成实现所述方法的设备、尤其是计算机和系统。

最后，本发明还涉及包括适于实现所述方法的软件代码的部分的计算机产品。

本发明的其他特征在所附的权利要求中陈述，其旨在成为本说明书的组成部分。

附图说明

根据下面对用于指纹匹配和相机识别的方法、设备和系统的详细描述，尤其是参考附图，上面的目标将变得更加清楚，其中：

图1示出根据本发明的系统；

图2示出根据本发明的方法的性能数据；

图3示出根据本发明的方法的实验结果的第一曲线图；

图4示出根据本发明的方法的实验结果的第二曲线图。

具体实施方式

参考图1，示出了用作系统场景的示例以解释本发明的详细描述的系统1。系统1包括设备3、尤其是计算机或智能电话或平板，和存储器装置5、尤其是设备3所能关联到的数据库5。更详细地，设备3可以包括所述存储器装置5，或者所述存储器装置5位于远程位置处并且它们可与计算机3远程通信地连接。因此，设备3和存储器装置5能够彼此通信，并且所述设备3能够从存储器装置5读取数据以及向存储器装置5写入数据。

设备3被配置成实现将在下面更详细地描述的根据本发明的方法；数据库5包括相机指纹估计、和可选地由相同的一个或多个相机获取的图片的集合，图片的集合可被用来提取指纹估计和与其相关联的其它信息。这样的信息可以是根据本发明的压缩方法的参数或相机的名称和/或型号和/或制造商。因此可以根据本发明的方法压缩所述相机指纹估计。

对于指纹匹配和相机识别，期望知道拍摄测试图像/图像集合的相机的测试图像或图像集合被处理以提取其指纹。目标是确定储存在数据库5中的哪个设备(即，相机)(如果存在)已经获取了给定的图片(测试图像/多个图像)。实质上，在测试图像/多个图像的压缩指纹与所有指纹估计之间计算相关性操作，并且如果一个指纹产生足够大的相关性，那么它被宣告为正确的。

对于从图像或图像的集合提取指纹，通常计算PRNU。

本发明的方法旨在以微小的或理想地无信息损失来压缩指纹数据库，因为如今数据库在大小上会迅速增长。所述方法基于随机投影(RP)技术。RP技术是用于降维的低复杂度和强大的方法。RP的想法是使用随机矩阵将原始的n维数据投影到m维子空间，m＜n。因此，通过下面的公式将N个n维数据的集降低到m维子空间

A＝ФD (1)

RP背后的关键性质是约翰逊-林登施特劳斯(Johnson–Lindenstrauss)引理，关注从高维欧式空间(Euclidean space)到低维欧式空间的点的低失真嵌入。引理声明高维空间中的点的小集合可以以点之间的距离几乎被保持的方式嵌入到维度低很多的空间中。

利用这种假设，本发明的方法被提供为通过设备3读取和/或获取从由相机拍摄的图片所提取的相机指纹，并且通过随机投影、也就是通过传感矩阵和所述相机指纹之间的乘法来计算所述相机指纹的压缩版本；所述传感矩阵具有小于所述相机指纹的行大小。

应当考虑的是：图片/图像是矩阵，并且图片/图像可表示为通过逐列读取图片/图像的矩阵而获得的列向量；从相同的图片/图像提取的(未压缩的)相机指纹相似地可表示为列向量，并且图片/图像和从相同的图片/图像提取的(未压缩的)相机指纹具有相同的大小，也就是两个对应的列向量具有相同数量的元素。更详细地，传感矩阵可以优选地是随机循环矩阵、尤其是随机部分循环矩阵。术语“循环”指的是这样的矩阵，该矩阵的行是第一行的循环地移位的版本。术语“部分”指的是传感矩阵的行大小小于所述相机指纹的大小，也就是行比列少的矩形矩阵。术语“随机”指的是这样的事实：传感矩阵的第一行包括根据选择的分布生成的随机变量(例如，高斯随机变量)。

可以使用其他类型的传感矩阵，例如，包括独立同分布(i.i.d.)高斯随机变量、或i.i.d.拉德马赫(Rademacher)随机变量、或伯努利随机变量的完全随机矩阵，或者甚至是确定性传感矩阵。

在下文中，描述使用根据本发明的压缩的方法的应用；也就是如何将本发明的基于随机投影的压缩方法应用到司法鉴定任务(诸如，指纹匹配和相机识别)。还应当考虑的是，假设图1的系统1、尤其是设备3为计算机。

指纹匹配

利用可以用来提取指纹估计的由相同的相机获取的图片集合和指纹估计的数据库5来呈现指纹匹配问题。

作为PRNU图案获得的相机指纹可以被近似为白高斯噪声，一种在研究匹配系统的性能的文献中考虑的典型假设。这具有一些重要的结果：首先，PRNU图案无法通过标准方法(例如，JPEG压缩)压缩，因为它们缺少可以被利用以执行压缩的冗余。此外，指纹彼此非常不相干。不相干的意思是两个指纹具有非常低的相关性，或者换言之，将它们表示为n维空间中的点，任意一对指纹之间的角度是宽的并且接近正交。在指纹匹配中，构建N个已知相机的指纹的字典，其可以表示为矩阵经典指纹匹配问题的目标是找到最类似于向计算机3呈现的测试指纹的列(因为在数据库5中每一个相机指纹是列向量)。为了清楚，测试指纹是从期望知道拍摄图像的相机(名称、型号、制造商等)的该图像所提取的相机指纹。

为了这个目的，最常使用的相似度准则中的一个是相关系数。在该说明书中，将考虑样本反射相关性ρ，其被如下定义：

其中，d_i是属于字典D的第i个指纹，项是内积(scalar product)，并且

因此，根据本发明的方法被提供为压缩整个数据库5和测试指纹从而通过少量的随机投影来表示它们。该操作可被视为与m×n传感矩阵Ф的积:

A＝ФD (3)

其中，A是包括在数据库5中的相机指纹的压缩字典，D是包括在数据库5中的相机指纹的原始字典，y是测试指纹的压缩指纹。

随机投影可以有效地降低指纹空间的维度，这是由于随机投影近似地保持包括在数据库中的指纹的集合的几何结构(geometry)。由于随机投影近似地保持任意两个指纹之间的角度并且由于该角度因为它们的不相干本质是宽的，所以压缩方法展现出鲁棒的性能，同时显著地减小问题大小。该方法被提供为在数据库5中储存压缩字典A和每当测试图案(例如，测试指纹)出现时使用相同的传感矩阵Ф生成压缩指纹的方式。为了限制数据库5的大小，可以期望仅储存允许生成传感矩阵Ф的伪随机数生成器的种子，而不是整个传感矩阵Ф。实际上，完全有可能已经通过不同的传感矩阵Ф获得了储存在数据库5中的不同指纹，并且如果储存整个传感矩阵Ф，这将增加数据库5的大小。

如已经提到的那样，传感矩阵Ф的选择是非常重要的，事实上可以使用包括独立同分布(i.i.d.)高斯随机变量的传感矩阵或循环矩阵或其他矩阵。尽管高斯矩阵可以在几何结构保持方面提供最佳性能，但是它们存在一些缺点，这使得它们在大规模问题中的使用相当复杂。

首先，考虑从种子生成传感矩阵Ф所花费的时间量是重要的，实际上人们需要生成nm个随机数，当n是数百万数量级时，这会花费显著的时间量。在实际中，如所引用的那样，人们通常无法储存整个传感矩阵Ф，因为这会要求太多存储器，所以仅储存伪随机数生成器的种子并且每次即时(on-the-fly)生成传感矩阵Ф。

其次，对于字典D的每一列，也就是对于每一个指纹，必须执行全矩阵乘以向量的乘法；这样的操作要求大量的时间和高计算复杂度。为了避免这样的问题，最好使用部分循环矩阵。这样的矩阵随机地生成第一行(例如，具有i.i.d.高斯变量)，并且所有其他行仅仅是第一行的循环移位版本。性能分析已经示出循环矩阵与全随机高斯矩阵几乎表现一样好，并且证明约翰逊-林登施特劳斯(Johnson–Lindenstrauss)引理和RIP(“约束等距性”)可用于这样的矩阵。循环矩阵提供巨大的优点，因为仅必须随机地生成第一行，并且因为快速乘法通过FFT(“快速傅里叶变换”)是可用的。由于FFT的使用，传感矩阵Ф和指纹字典D之间的积可以利用O(Nnlogn)次操作而不是全随机i.i.d.矩阵所要求的O(Nmn)次操作来实现，其中N是D的列的数量，也就是数据库5中相机的数量，m是传感矩阵Ф的行的数量，也就是压缩指纹的大小，以及n是传感矩阵Ф的列的数量，也就是未压缩指纹的大小。

本发明的方法还被提供为将标量量化应用到相机指纹的压缩版本；可以利用任意数量的比特、尤其是利用1比特来执行标量量化。其中利用1比特来量化压缩相机指纹的情况被称为二进制量化。

因此，可以通过量化压缩指纹来实现进一步的压缩，而不是在压缩指纹中保留浮点值。此外，注意，在1比特压缩传感的领域中，利用二进制量化的随机投影实现近似地保持信号之间的角度的嵌入。由于角度的保持是匹配问题的主要兴趣，也可以考虑利用二进制量化的随机投影的情况，其被获得为：

A＝sign(ФD) (5)

在利用二进制量化的压缩指纹的情况下，由汉明距离替代相关系数作为测试度量。

因此，压缩指纹的二进制量化允许例如对数据库5的进一步的压缩。

由于原始角较宽，与非匹配指纹的汉明距离倾向于比与正确指纹的距离(其理想地为零)大得多。二进制随机投影允许显著地压缩，同时性能劣化是有限的，并且由二进制化产生的劣化较小，但是它允许在空间方面获得显著的增益。此外，计算汉明距离是非常快和高效的操作。

相机识别

相机识别问题概念上非常类似于指纹匹配场景。主要的不同是可用的是单个测试图像而不是它们的集合。注意，用于这个问题的最优相似度准则是储存在数据库中的指纹的调制版本和图像的噪声残差之间的相关性，其中调制项是测试图像。由于数据库中的指纹和测试图像之间的按元素的积，不可能将这个准则扩展到压缩域、也就是本发明的方法。

因此，在这种情况下，本发明的方法被提供为使用两种可以容易地映射到压缩域的简化的相似度准则。

第一种简化的准则将储存在数据库5中的指纹与测试图像I_t的噪声残差w进行相关。实质上，这个方法消除了测试图像I_t的调制效果，因此除非测试图像I_t是恒定的图案，否则该方法将是次优的。足够的是，将传感矩阵Ф应用到储存在数据库5中的至少一个指纹和期望知道哪个相机拍摄了测试图像I_t的该测试图像的噪声残差w这两者，以由下面的公式所示的那样将这个准则转换到压缩域：

ρ(w,d_i)→ρ(Фw,Фd_i)>

其中，ρ是在公式(2)中定义的相关系数，并且d_i是属于数据库5中的字典D的第i个指纹。

第二种简化的准则考虑使用从单个测试图像I_t提取的指纹估计而不是噪声残差w。第二准则然后将这个测试指纹估计与储存在字典D中的指纹进行相关，由下面的公式所示：

性能分析

在下文中描述由根据本发明的用于指纹匹配和相机识别的方法所获得的性能。

匹配问题关注于找到最匹配测试压缩图案的字典的列。对于压缩字典中的每一列，测试压缩指纹经历二进制假设测试。两个假设被定义为：

H0(空假设)：压缩测试指纹和列参考不是来自相同的相机；

H1(替代假设)：压缩测试指纹和列参考来自相同的相机。

每当测试度量(相关系数或汉明距离)在预定的阈值τ以上时，空假设就被拒绝。在该说明书中，下面的名称将用来指不同的事件：

·假警报：空假设被错误地拒绝；

·检测：空假设被正确地拒绝；

·正确检测：空假设仅对于正确的相机被拒绝；

·假检测：空假设对于至少一个错误的相机被拒绝。

用于这种分析的数据库是Dresden图像数据库。这样的数据库包括平场图像和来自室内和室外环境的场景这两者。已经选择了具有平场照片和自然照片这两者的53个相机。从平场图像创建数据库以便具有高质量指纹，而从自然场景拍摄测试图像。自然照片呈现细节和照明条件的变化的量。所有照片注册到相同的传感器取向。

参考图2，示出包括在各种条件下的Dresden数据库的字节大小的表。具有被称为“单精度”的参考标号7的第一列指的是具有单精度(根据IEEE 754标准的32比特)浮点值的压缩指纹，而具有被称为“二进制(1比特)”的参考标号9的第二列指的是压缩指纹的二进制量化。项m表示传感矩阵Ф的行的数量，因此表示压缩指纹的大小。

容易注意到的是，压缩数据库的大小比相同数据库的未压缩版本小得多。此外，当应用随机投影的二进制量化时，压缩变得更大。

参考图3和图4，示出由压缩指纹的元素个数m所参数化的ROC(“接收器操作特征”)曲线。

具体地，图3示出假警报概率P_FA(横坐标中)对检测概率P_D(纵坐标中)。具有参考标号11的曲线指的是未压缩数据库，而具有参考标号13的曲线指的是通过利用二进制量化并且m＝32000的本发明的方法的压缩数据库。

图4示出假检测概率P_F(横坐标中)对正确检测概率P_C(纵坐标中)。具有参考标号15的曲线指的是未压缩数据库，而具有参考标号17的曲线指的是通过利用二进制量化并且m＝64000的本发明的方法的压缩数据库。

根据图3和图4，在实验上验证了二进制随机投影具有良好的性能。相比于在匹配操作的复杂度和储存方面的显著节省，关于实值(real-valued)压缩指纹(无量化)的差距较小。观察到的是，具有m个二进制量化的随机投影的处理通常示出与具有m/2个实值随机投影的处理的ROC几乎重叠的ROC。因此，作为经验法则，当使用二进制量化的随机投影时，必须考虑压缩指纹的元素数量中的因子2的惩罚。然而，按照因子64降低了储存要求(在双精度压缩指纹的情况下)，所以二进制量化的随机映射展现出极具竞争力的性能。

缩放和旋转

根据本发明的方法考虑了另一个方面，也就是压缩指纹的缩放不变版本和旋转版本，尤其是用于在数据库5中储存它们。

至此已经描述的内容考虑了压缩指纹的字典的创建，其中每一个相机传感器关联到单个条目。通过将多个条目关联到相同的相机传感器以便提高该方法对变换(诸如，缩放或最常见的旋转)的鲁棒性，可以扩展这个概念。这表示计算时间和存储器之间的权衡，因为经变换的图案的随机投影被储存以便在匹配时不执行测试指纹的任何变换。词典的这种构建称为“冗余词典”。

在这个方面，该方法的目标是使得随机投影对缩放变换变得鲁棒，以便当呈现缩放的照片时，通过仅保留PRNU图案的随机投影的数据库5并且计算查询图案的随机投影，系统1就可以正确地识别获取该照片的成像传感器。为了实现这个目标，要求关于缩放的信息被映射到压缩域。因此，考虑二维表示并且使用BCCB(“具有循环块的块循环”)传感矩阵，而不是使用待压缩的指纹的向量化版本。BCCB传感矩阵的使用允许在压缩指纹上保持关于缩放的信息，并且经由二维DFT(“离散傅里叶变换”)有效地实现所述压缩指纹的计算。随机BCCB矩阵满足RIP。

因此，在这种情况下，根据本发明的方法提供的是，经由二维DFT，将从适当地缩放的随机图案获得的、即基于待压缩的指纹(相机指纹)的大小n_x×n_y的BCCB矩阵用作传感矩阵Ф，并且经由适当地裁剪和重新缩放随机投影，实现压缩指纹的缩放不变版本的计算。该方法还提供这样的技术，该技术使用储存在数据库5中的参数的集合正确地裁剪和重新缩放测试指纹的随机投影，以匹配储存在数据库5中的压缩指纹。所述参数优选地包括待裁剪的区域的位置和大小以及未压缩指纹的大小。

创建压缩数据库条目的过程如下：

·创建大小的随机图案(i.i.d.高斯)，其中大小与系统1处理的最大传感器大小一致；

·给定大小n_x×n_y的相机指纹K，以下面的方式计算压缩指纹：

-将重新调整大小到n_x×n_y以得到

-将随机投影计算为这等同于使用其中第一行是的向量化版本的BCCB矩阵并且将其乘以K的向量化版本；

-裁剪大小m_x×m_y的Y的连续区域，并且储存裁剪与Y的任意重新调整大小版本相同的区域的方式(例如，总是裁剪左上角并且储存比例和)。

与测试指纹的匹配处理如下：

·给定大小n′_x×n′_y的测试指纹K'，以下面的方式计算压缩指纹：

-将重新调整大小到n′_x×n′_y以得到

-将随机投影计算为

-裁剪与数据库中相同的Y'的连续区域(例如，如果它是左上，那么裁剪个像素)；

-将经裁剪的区域重新调整大小到m_x×m_y；

·计算与字典的当前条目的相关性。

应当注意，由于和的不同的值，必须对于字典的每一个条目重新进行测试指纹的经裁剪的随机投影的重新调整大小。

在二进制量化的压缩指纹的情况下，数据库5储存随机投影的二进制量化的版本。在匹配阶段期间，经裁剪的测试压缩指纹被重新调整大小并且然后被量化。最后，优选地使用汉明距离作为相似度度量。

为了能够在测试图像已经经受了旋转时检测相机，本发明的方法被提供为将指纹的旋转版本和翻转版本的随机投影包括在字典中，包括最常见的旋转。作为示例，人们可能想要包括对应于下面的变换的压缩指纹：旋转90°、180°、270°、上下翻转、左右翻转。优选地，可以有总共8种组合，包括原始的指纹。

通过上面的描述，本发明的特征以及其优点是清楚的。

根据本发明的用于指纹匹配和相机识别的方法的第一优点是该方法允许减小相机指纹数据库大小。

根据本发明的用于指纹匹配和相机识别的方法的第二优点是该方法允许相对于现有技术降低指纹匹配和相机识别处理的计算复杂度。

根据本发明的用于指纹匹配和相机识别的方法的其他优点是该方法允许在指纹匹配处理期间具有可缩放性。术语“可缩放性”的意思是压缩指纹可以被修剪成任意长度，以最优地适应数据库5中的搜索的计算复杂度和数据库5与设备3之间的通信所要求的带宽。

在不偏离本发明思想的创新精神的情况下，通过示例的方式在本文中描述的用于指纹匹配和相机识别的方法、设备和系统可以经受许多可能的变型；还清楚的是，在本发明的实际实现中，所说明的细节可以具有不同的形状或者用其他技术上等同的元件替代。

因此容易理解的是，本发明不限于用于指纹匹配和相机识别的方法、设备和系统，而是可以在不偏离如下面的权利要求中清楚地指定的本发明思想的情况下经受等同部分和元件的许多修改、改进或替代。