用于形状的仿射不变识别的方法和装置

摘要

本发明涉及用于至少一幅数字图像中对象识别的方法，包括：a)根据所述数字图像模拟多个数字旋转和至少两个不同于1的数字倾斜，以便对于每个旋转—倾斜对产生模拟图像；以及b)将产生在平移、旋转和缩放过程中不变的值的算法应用于所述模拟图像上，以便确定用于识别对象的所谓的SIF(尺度不变特征)的局部特征。SIFT方法可以用于步骤b中。

说明书

本发明涉及用于至少一幅数字图像中对象识别的方法和装置。

通常，形状识别方法的目的是当对象和真实或模拟拍照装置的相对位置未知时或者当对象可能已经畸变时识别已被拍照的对象或一类对象。对象本身可以是图形对象和非物理对象(例如数字标识或者模拟结果)。为了简明，在下文中将拍照装置(或者用于模拟拍照的装置)称为“照相机”，但是本发明涉及图像的任何采集，以及由照相机相对于对象的位置上的改变或者由用于图像采集或者图像模拟的装置的具体特征导致的对象图像的任何畸变或几何变形。此外，被拍照的或者被模拟的对象不需要相同，它们相似就足够了，对象的常见情况产生于工业生产或者图形生产。待识别的对象的一个或者多个图像是可获得的，这些图像是“查询”图像。在图像中寻找对象的那幅图像或者那些图像不必须包含对象。目的是找到用于知道对象是否存在于所分析的图像中的可靠标记，并且给出对象在图像中的位置。

由处理识别问题的全部方法提出的第一简化假设：对于目标图像中待解释为查询图像的平面仿射变形的局部变形，对象具有足够规则的凹凸。大多数感兴趣的物理对象实际上是表面具有平坦的或者轻微弯曲的面的体积。例外是少见的。作为例外的例子，考虑没有树叶的树，当改变观察角时，树的外观可以显著地改变；或者考虑液体的波纹。现在，在(可微分)项的数学意义上的任何规则的变形局部地在图像中近似于仿射变形。具体地对于相当规则对象的光学图像的明显变形，情况就是如此，此时由照相机的运动、或者由照相机的光学畸变、或者由对象的运动，或者甚至由对象本身的逐渐变形导致图像的该明显变形。例如，在扁平对象的情况中，由观察扁平对象的照相机的位置改变导致的扁平对象图像变形是平面单应性，平面单应性在与仿射应用相切的每个点处。此外，如果照相机距观察对象很远，图像的该变形越来越类似于总体仿射变换。相反，可以将具有正行列式的图像平面的任何仿射变换理解为由于观察图像且远离图像(实际上在无限远处)的照相机在空间中的运动导致的图像变形。应当回忆(x，y)坐标平面的仿射变形写成如下形式：

x’＝ax+by+e，y’＝cx+dy+f，

且参数a、b、c、d形成具有两行和两列的矩阵，我们将该矩阵指定为A。因此图像u(x，y)的仿射变形写成：

u(x’，y’)＝u(A(x，y)+(e，f))

由于上面给出的原因，可以将形状识别问题缩小至查找图像的局部特征，该图像的局部特征是以仿射变换为模的不变量。则这些特征对于以下变形或畸变是鲁棒的：由对象和照相机的相对运动导致的明显局部变形；以及由采集装置导致的畸变(例如透镜的光学畸变)；和最后由对象本身的变形导致的畸变。

在下文中，将使用术语“倾斜”和“数字”。这些是本领域技术人员常用的术语，其分别表示倾斜和数字的意思。还将使用术语SIF和SIFT，这些是本领域技术人员已知的缩写，分别表示“尺度不变特征”和“尺度不变特征变换”。

美国6711293号文献(Lowe)描述了用于“尺度不变特征变换”的称作SIFT方法的方法，该方法使得识别由照相机从正面获取的图像中的对象成为可能。该美国6711293号文献认为探究全部仿射空间将是禁止的且低效的。Lowe最后评论，通过采用间隔30度的3D对象的真实视图可以补偿他的SIFT方法的不变性的缺陷。

Eurographics 2003/volume 22，Number 3(2003年欧洲图形学大会/卷22，第3号)的D.Pritchard和W.Heidrich的文献“Cloth motion Capture(布料运动捕获)”描述了用于确定SIFT特征的方法，其中，根据从正面获得的初始图像，以等于2的倾斜产生4幅模拟图像。对于在水平线上实现的倾斜获得第一模拟图像，在垂直线上获得第二模拟图像，在45度的两条轴线上获得第三模拟图像和第四模拟图像。因此，该方法提供了4幅模拟图像以便改进识别。

本发明涉及一种对已经经受任意仿射变换的平面图像一部分进行识别的新颖方法。本发明的目的还将允许在偏斜地(与对象对面的正面视点比较)拍照的或者也是偏斜的图像中的对象识别。因此本发明的目的是在不考虑视点的情况下改进识别率。

借助用于至少一幅数字图像中对象识别的方法实现至少一个前述目的，其中：

a)根据所述数字图像模拟多个数字旋转和不同于1的至少两个数字倾斜，以便对于每个旋转—倾斜对产生模拟图像；以及

b)将产生在平移、旋转和缩放过程不变的值的算法应用于所模拟的图像上以便确定称为SIF(尺度不变特征)的用于识别对象的局部特征。

换句话说，从数字图像开始，模拟了在无限远处观察数字图像的照相机光轴的几个方向改变。虽然旋转—倾斜对限定了照相机的每个位置，但本领域技术人员将容易地理解具有变化复杂性的其它变形可以用于限定照相机的位置。然而，本发明的显著之处在于照相机轴线的任何方向改变可以表示为旋转后面跟随倾斜。

根据本发明的方法基于下面的观察，即可以将平面的任何仿射变换理解为由无限远处的照相机位置改变导致的图像变换。基于该理解，可以将仿射变换分解为以下的产物：

-照相机沿光轴运动，或者缩放(1个参数)，

-平行于焦平面的平移(2个参数)，

-照相机的轴向旋转(1个参数)，

-以及照相机光轴方向的改变(2个参数)。

现有技术的算法(如SIFT方法)使图像能够被识别，对于该图像开始的三个变换是任意的。它们对应于照相机的轴向旋转、缩放和平行于焦平面的平移(因此垂直于光轴)的4个参数。SIFT方法使得确定SIF(“尺度不变特征”)成为可能，即通过图像的缩放、平移和旋转的更精确的不变特征，但是不考虑与照相机光轴方向改变有关的最后2个参数。Lowe提供附加的视图来改进SIFT方法的灵敏度，但是这些是真实的视图。意味着附加的操作以及待处理数据的大量增加。Pritchard仅提供了4幅模拟图像，因为据认为，就计算时间而言再进一步将是起反作用的和阻止性的。本发明超越通常假设的偏见，根据该通常假设的偏见，如果增加模拟图像的数目，那么计算时间将是阻止性的。

使用根据本发明的方法，可以以足够的精度模拟由于SIFT方法中未处理的2个参数(即照相机的光轴方向改变的参数)的改变导致的图像的全部畸变。

使用本发明，首先关于通过旋转和倾斜描述的所述最后两个参数产生最初几幅模拟图像。特别地，旋转—倾斜对可以内接于数字图像上方的半球中。旋转和倾斜被视为分别对应于空间中的经度和纬度。Pritchard实际上描述了来自正面图像的4个旋转和单个倾斜值。使用本发明，通过非正面视点(即直到约80度的倾斜)可以获得初始图像。

对于导致直到3或4的实际倾斜的照相机轴线方向改变，现有技术的系统允许带有偏差的对象识别。根据本发明的方法可以处理直到超过40的值的倾斜。实际上，在照相机已经获取了具有倾斜t和t’的扁平对象的两幅视图的情况中，这些偏斜视图之一的从另一个开始的模拟可能需要模拟直到值tt’的倾斜。例如，对于80°的纬度，倾斜是5.76，并且当偏斜的视图具有等于90°的经度差时，组合的倾斜等于5.76²＝33.2。因此比2大得多(例如直到30或者更多)的倾斜是可能的，并且根据本发明的方法使识别互相偏斜的这种视图成为可能。

因此该方法能够识别无限远处图像的全部可能视图，因为借助SIF的计算，所模拟的视图现在仅需要一种通过平移、旋转和缩放的不变识别算法(已经在本领域的技术状态中被很好地掌握的问题)。

根据本发明方法所基于的远离不是假设整个图像已经经受单仿射变换，这仅对于完全平坦的对象和在无限远处的照相机是正确的。相比之下，通过应用将图像的全部仿射变换考虑在内的识别算法，确定地获得完全识别，因为每个变形局部相切于仿射应用。该情况可以被概括为下面的说法，即全部仿射变换的模拟足以有效地模拟图像的全部局部变形。

根据本发明的实施方式，将本方法应用于称为查询的图像和称为目标的图像，将查询的模拟图像的SIF与目标的模拟图像的SIF相比较，以便识别查询和目标之间相似或者相同的对象。

作为非限制性的实施例，当将根据本发明的方法应用于一幅或者多幅称为查询的图像以及一幅或者多幅称为目标的图像时，在前面的校准阶段过程中可以确定与查询有关的SIF，以便构成SIF的词典。且在操作阶段过程中，可以依次确定与目标有关的SIF，在操作阶段中将从每个目标获得的SIF与所述词典中的SIF相比较。

为了实验确定待实现的旋转—倾斜对的数量和最佳位置以便确保可接受的结果，执行根据本发明的方法，其中查询包含对象的任何获得的视图，该对象具有与来自任何视图的目标中包含的另一对象的形状相似或者相同的形状，并且确定旋转—倾斜对，即对于大量的测试对象来说，该最佳数量和这些最佳位置是两个对象的SIF是相似的那些数量和位置。

根据本发明的方法设想对于查询和对于目标以及对于相同的旋转—倾斜对产生完全相同数量的模拟图像。但是其还设想当对于查询和对于目标产生不同数量的模拟图像(特别地具有不同或者相同倾斜)时的情况。

有利地，当倾斜值增加时，每倾斜的旋转数量同时增加。优选地，将倾斜定义为数字图像上方的半球中的纬度的函数，且当倾斜增加时，两个连续倾斜之间的纬度差降低。特别地，纬度可以通过0度到90度范围内的参数θ或者可选地通过由t＝1/|cos(θ)|定义的倾斜参数来测量。当纬度趋于90°时，这些特征使得具有越来越接近照相机的模拟位置成为可能。

根据本发明的有利特征，对于给定的旋转，将考虑的倾斜近似地(即具有偏差)形成有限几何级数1，a，a²，a³，...，aⁿ，a为大于1的数。作为非限定的实施例，a大约是方根并且如果既在目标上又在查询上应用旋转—倾斜对那么n可以从2到6，如果仅在两幅图像之一上应用旋转—倾斜对那么n可以从2到12。

根据本发明的另一有利特征，对于给定的倾斜t，例如从倾斜t＝a开始的数字旋转近似地(即具有偏差)形成等差级数0度、b/t度、2b/t度、...，kb/t度，b是度数且k为整数。

优选地，b大约是72度且k是使得kb/t小于180度的最后整数值。使用这些典型值，对每个测试的倾斜t，模拟了(180/72)·t幅图像＝2.5·t幅图像。

有利地，应用倾斜t包括用等于t的值在一个方向上对数字图像进行欠采样，这将数字图像的面积除以t。倾斜还可以通过将根据一个方向的数字图像的欠采样与在垂直于前面方向的方向上的过采样结合来应用。

为了防止模拟的总面积超过初始图像的总面积太多，我们可以使用例如a＝方根2和n＝4。如果通过欠采样获得每个倾斜t，这将倾斜后图像的面积除以t。因此，对于每个t模拟了图像总面积为180·t/(72·t)＝2.5倍初始图像面积的图像。因此处理的面积等于2.5倍初始图像的面积乘以倾斜的数量。因此模拟的面积为2.5·n＝10倍初始图像的面积。然而，如果将根据本发明的方法应用于查询图像和目标图像的具有因子3的缩小，则所模拟的面积仅为10/9＝1.11倍的初始面积。因此，根据本发明的方法采用可与SIFT方法相比较的时间，例如当允许识别直到16的过渡倾斜的偏斜视图时，根据本发明的方法花费可与SIFT方法相比较的时间。然而，倾斜可以通过将在一个方向上的过采样和正交方向上的欠采样结合来模拟，使得图像的面积保持恒定且不减少(见后面的倾斜的定义)。

因此，使用根据本发明的方法使得对依赖于两个参数的全部视图进行模拟同时保持合理的计算时间和存储容量成为可能，因为对于每个参数用十分少的值对两个参数旋转和倾斜的空间进行采样，以及因为对由偏斜视图导致的畸变的模拟可能通过欠采样减少图像的尺寸。这使得以给定的精度产生几乎全部可能视图同时不过度地扩展需求的存储能力成为可能。

根据本发明的有利实施方式，与所述数字图像或者所述数字图像的变换(例如轴对称)相比，根据本发明的方法可以应用于同一数字图像，以便确定该数字图像中的对称性、重复形状或者具有周期性的形状。

根据本发明的另一方面，为了应用根据本发明的用于至少一幅数字图像中对象识别的方法，设想了装置。该装置包括为下面配置的处理电路：

a)根据所述数字图像应用多个数字旋转和至少两个不同于1的数字倾斜，以便对于每个旋转—倾斜对产生模拟图像；以及

b)将平移、旋转和缩放不变的算法应用于模拟图像上，以便确定称为SIF(尺度不变特征)的用于识别对象的局部特征。

该装置有利地包括存储空间，在存储空间中存储了SIF的词典；且配置处理电路，以便将所述数字图像(初始图像)的SIF与所述词典的SIF相比较。

根据本发明，可以配置处理电路以便并行处理任意数量的图像。

当考察绝非限定性的实施方式的详细描述和附图时，本发明的其它优势和特征将变得显而易见，其中：

图1是实现根据本发明方法的装置的总图；

图2是根据本发明方法的步骤的简化流程图；

图3是示出了描述照相机位置的4个主要参数的总图；

图4是示出了模拟图像之间的多个对比的总图；

图5是示出了球的总图，在球中内接了旋转—倾斜对；

图6是示出了模拟倾斜和旋转在图5中的球上的位置分布的总图；

图7和8是示出了绝对倾斜和相对倾斜之间或者过渡倾斜之间差异的视图。

图1示出了处理单元1，如计算机，其配备有对于其正常操作必需的软件和外围设备。其具体地包括处理电路2，如微处理器或者专用微控制器，配置该处理电路2以便根据本发明的方法处理图像。还有特别适于存储呈词典形式的SIF的常规存储空间3。该计算机配备有显示监控器4，在显示监控器4上可以显示已处理图像。

照相机5通过连接线缆连接到计算机1。然而可以使用其它连接方式，尤其是无线。恢复先前获得并存储在计算机的固定存储装置或者便携存储装置中的图像也是可能的。

虽然本发明不限制于此，但现在将描述并且为了目标图像和查询图像之间的对象识别应用根据本发明的识别方法。

在图2中，流程图示出了两幅图像查询6和目标10的并行处理。

从两幅图像查询6和目标10开始，对于旋转7、11和倾斜8、12对产生第一幅模拟图像，并且执行几次(例如p次)步骤7、11和8、12以便在9和13处产生p幅模拟图像。换句换说，每幅图像经受同样的处理，包括模拟由照相机轴线方向改变导致的全部可能畸变，照相机轴线方向是具有称为经度和纬度的两个参数的空间。在图3中，例如，角θ(theta)是纬度，角φ(phi)是经度。

借助使有效模拟的视图数量少(几十)的采样，对于有限数量的P对经度和纬度产生这些模拟图像，同时保证几十幅模拟的图像保持接近于任何其它可能视图。

在图2的步骤14中，然后通过已有算法中的任一个将这样模拟的图像互相比较，已有算法执行以图像旋转(＝照相机关于其光轴的旋转)、平移(＝照相机垂直于其轴线的运动)和缩放(＝照相机在其光轴上的运动)为模的有效识别。这种算法具体地是在美国6711293号文献中描述的SIFT算法。图4示出了在模拟图像上执行的多个比较的图示。两幅图像查询A和目标B通过两个方格来表示，两幅图像周围环绕着通过两个倾斜和关联的旋转获得的两幅图像的模拟视图(平行四边形)。将图像之一的平行四边形连接到另一图像的一些平行四边形的箭头表明在一幅图像的模拟视图和另一图像的模拟视图之间进行的比较。

输出15可以是查询和目标的多对子图像的列表(可选地为空)，该列表包括在两幅图像上识别的对象以及被识别为使得将子图像之一变换成另一个成为可能的仿射变换。

图3示出了导致由照相机获得的图像变形的4个主要参数：照相机可以在角ψ内旋转，其光轴可以关于正面轴线采取角θ(纬度)，并且在与固定方向构成角φ(经度)的垂直平面中执行通过该角θ的倾斜。

根据本发明的方法使得产生全部仿射畸变成为可能，全部仿射畸变可能是由于在无限远处正面地观察平面图像的照相机轴线方向的改变导致的，因此这些畸变取决于两个参数——经度和纬度，对这两个参数进行采样使得产生的视图数量为几十。当纬度增加时，模拟的经度变得越来越多。但是当纬度增加时，图像在一个方向也可选择地越来越被欠采样，因此越来越小，于是欠采样率成为几何级数。

甚至更精确地，通过0到90度范围内参数θ或者可选地通过由t＝1/|cos(θ)|限定的倾斜参数测量纬度。通过参数φ(见图3)描述经度。倾斜t的值对数地交错，φ的值算术地交错。

通过下面给出的变换A可以定义照相机从一个位置到另一位置的位移：

$A=H_{\lambda }{R}_1\left(\psi \right)T_1{R}_2\left(\phi \right)=\lambda \left(\begin{array}{cc}\cos \psi & -\sin \psi \\ \sin \psi & \cos \psi \end{array}\right)\left(\begin{array}{cc}t& 0\\ 0& 1\end{array}\right)\left(\begin{array}{cc}\cos \phi & -\sin \phi \\ \sin \phi & \cos \phi \end{array}\right)$

变换A是与具有4个元素(a，b，c，d)的2×2矩阵相关联的平面的线性变换。给定图像u(x，y)，将其理解为由光学照相机正面地观察的图像，则将应用u(x，y)-＞u(A(x，y))理解为当下面情况发生时将观察到的图像的变形：1)当照相机在角度ψ内在其光轴上旋转时，2)当其在其光轴上滑动在该轴线上通过因子λ(lambda)移动离开(或者如果λ＜1则更接近)时，以及3)当其光轴通过纬度θ的变化和经度φ的变化的结合远离其正面位置时。照相机还可以开始垂直于其光轴平移运动，这导致在前面的公式中未将图像(e，f)的前面平移考虑在内。该平移(e，f)、缩放λ和旋转ψ是由本领域的技术状态掌握的4个参数。本发明涉及当图像额外经受由纬度和经度的变化导致的变形时识别图像的方式。

图5示出了球，在球上定位了倾斜和旋转。该图示出了分别对于倾斜2、和4(即对于角度60°、69.30°和75.52°)将模拟的照相机位置的透视图。当倾斜增加时有越来越多的旋转角度。

图6示出倾斜和旋转的位置分布。每个圆对应于倾斜。最接近中心的圆用于与θ＝45°关联的倾斜，且接下来的圆对应于θ＝60°、70°、75°和80°。倾斜增长得越多，越需要增加圆上位置的数量，即经度φ的数量。因此指示的点具有这样的坐标sin(θ)cos(φ)和sin(θ)sin(φ)。矩形指示由每个倾斜导致的方块图像的畸变。

根据本发明的方法涉及本领域技术人员已知的一定数量的术语，概括如下：

数字图像u(x，y)的旋转：通过从值u(x，y)到图像的像素(x，y)的内插，计算值v(x，y)＝u(R(x，y))，其中R是通过具有两行和两列的参数(cos(φ)，-sin(φ)，sin(φ)，cos(φ))的矩阵描述的角φ的平面旋转。视觉效果是图像在角φ内在计算机荧屏上旋转。该操作具体模拟由在正面视图中获取图像的照相机绕其光轴旋转可能产生的效果。

数字图像在x方向上的倾斜：设v(x，y)＝u(xa，y/b)，且ab＝t是“倾斜因子”，缩写为“倾斜”。对于假设由无限远处的照相机的正面观察的图像，该操作模拟该照相机的光轴在x方向上的倾斜的结果。光轴对法线方向的角是角θ在-90°和+90°之间的两值之一，使得t＝1/|cos(θ)|。图像u(x，y)是正面视图，因此图像v(x，y)是在x方向上通过角θ的倾斜t后的偏斜视图。在数字图像上，可以通过在y方向上用因子b对图像进行过采样以及在x方向上用因子a对图像进行欠采样获得倾斜，其中b是1和t之间的任意因子。如果a＝t，b＝1，在x方向中仅有欠采样，且如果a＝1，b＝t，在y方向仅有过采样。在欠采样的情况中，必须通过图像与一维低通滤波器的卷积在x方向上事先平滑图像。如果a＝t，b＝1，倾斜后的数字图像具有被t除的面积(且如果则该面积不变)。

数字图像的缩小：通过低通滤波器G_h(x，y)＝(1/h²)G(x/h，y/h)对图像u(x，y)应用卷积v(x，y)＝(G*u)，接下来是欠抽样v(x，y)＝(G_h*u)(xh，yh)，其中h是缩小因子。该操作模拟照相机相对于图像的远离，远离前到对象的距离与远离后的距离的比为h。函数G(x，y)(通常是高斯分布)模拟照相机的光学卷积核。通过简单的内插获得数字放大。缩小或者放大是很短的缩放。

绝对倾斜和相对倾斜：绝对倾斜是用于一个方向上的图像压缩的因子t＝1/|cos(θ)|的术语，该一个方向产生自照相机从平面对象对面的正面位置过渡到偏斜视图。现在想象已由照相机在两个位置上拍照的同一平面对象，对于该两个位置，光轴通过图像的同一点。第一照相机的轴线位置通过两个角θ和φ来描述，第二照相机的轴线位置通过两个角θ’和φ’来描述。当φ＝φ’时，必须应用于两个图像之一以直接传给另一个(除缩放以外)的倾斜等于比率t’/t，其中t’表示两个倾斜中较大的，t表示较小的。当φ＝φ’+90°时，必须应用于两幅图像u(tx，y)之一以传给另一个u(x，t’y)的该同一倾斜为最大值且等于tt’的积。这解释了为什么对于比较偏斜视图而言，模拟可以超过40的大倾斜是有利的。图7和8具体地示出绝对倾斜和相对倾斜之间或者过渡倾斜之间差异的图解。在左边的图7中，我们看到照相机位于具有φ＝φ’的对应于θ＝30°和60°值的两个位置上。倾斜之一等于2，另一个等于因此从v转变到v’的相对过渡倾斜是其小于从u转变到v’的倾斜。因此当倾斜在同一平面(φ＝φ’)中发生时，可以看出待模拟的倾斜小于原始倾斜。在右边，倾斜平面已经改变：我们有φ-φ’＝90°，且倾斜是从u到v的t＝2和从u到v’的t’＝4。在该情况下，倾斜被倍增，且从v到v’过渡的相对倾斜为2×4＝8。

SIF(“尺度不变特征”)：数字或者多组数字，附属于数字图像的并且当旋转图像时或者当平移图像时几乎不变，且当向图像应用缩放时还可以在几乎不变的情况下被保持。因此，SIF使得独立于其位置、图像定位、方向和缩放识别图像中的像素成为可能。通过SIFT(“尺度不变特征变换”)方法获得这种指示的经典示例。

本发明可以有效地应用到以下领域之一：

-一部电影的不同图像的比较或者几部电影的图像的比较；

-由置于连续或者同步位置上的一架照相机或者几架照相机获得的不同图像的比较；

-在装配了照相机的车辆上的使用，例如用于其导航；

-通过将本方法应用于图像和应用于关于任意直线对称的图像，图像中的偏斜对称的检测；

-运动对象(人、动物、机器)的识别；

-照片、图画和一般的视觉艺术作品的比较或者分类；

-大的单独的或者集合的图像数据库的组织和管理；

-来自几幅视图的场景或者对象的凹凸感的重建；

-通过一架或者多架照相机获得的图像的校准或者分级；

-通过空中视图、空间视图或者地面视图的比较的地图绘制、平面或者浮雕；

-符号、字、印刷字符或者标记的识别；以及

-应用于电影以跟踪在一个完整序列中出现的对象。

当然，本发明不限于刚描述的实施例，并且在不超出本发明范围的前提下可以对这些实施例进行多种调整。