特征向量场和特征匹配

模式识别43（2010）3273-32811/18特征向量场和特征匹配F.C.Wu*,Z.H.Wang,X.G.Wang模式识别国家重点实验室，中国科学院自动化研究所，北京100190，中国文章历史：2008年10月22日收到稿件；2010年2月2日收到修订后的稿件；2010年5月2日收录。摘要：本文中，我们提出基于图像梯度内、外积的图像特征向量场。这个特征向量场有效地表示了包括拐角和大曲率边缘点在内的图像边缘和特征点。使用它就可以为点匹配和曲线匹配构建一些新颖的描述符。这些描述符对于欧氏变换和线性强度变化都有不变性。实验结果表明，对小图像仿射变换、JPEG压缩和非线性强度变化也有良好的适应性。2010ElsevierLtd.保留所有权利。关键字：内积，外积，特征匹配，特征描述。1引言包括点匹配和曲线匹配的特征匹配在许多如图像定位、三维重建、对象识别和视频理解的计算机视觉课题中扮演着重要的角色。近年来，我们在特征匹配领域已经有了重大进展，并且提出了大量算法。下面，简要地回顾一下文献中一些相关方法。点匹配：点匹配方法主要分为两类：基于强度分布的方法和基于梯度分布的方法；且都使用描述符来表示局部图像区域中的强度分布或梯度分布。交叉相关[1-3]是一个基于强度分布的经典描述符，而旋转图像[4]的描述符则要更加出众。在基于梯度分布的描述中，由Lowe[5]提出的尺度不变特征变换（SIFT）是最著名的一个。之后[5]，又有了许多相似的变体，如前后形态关系[6]、GLOH[7]和模式识别43（2010）3273-32812/18SURF[8]等。除了上述两种主要类型，文献中也有介绍一些其他技术，像局部喷射[9]、可操作滤波器[10]、不变矩[11]和复杂滤波器[12,13]。Mikolajczy和Schmid[7]对这些主流描述符在真实图像上做了评估，并得出以下结论：第一，这些描述符表现的性能就是一个独立的特征检测器；其次，基于SIFT的描述符在多维描述符中效果最好。最后，最好的低维描述符是梯度矩和可操作滤波器。曲线匹配：近年来，相对于点匹配，曲线匹配（包括线性匹配）一直进展不大。到目前为止，只有少数曲线匹配方法在文献提出。对于平面图像，Lourakisetal.[14]提出了对于线性匹配使用“2线+2点”射影不变量的方法，Herbertetal.[15]提出了一种彩色图像中的自动匹配方法。这种方法的主要缺陷在于它对颜色信息的严重依赖。当色彩中有强烈的不同时可以区别，但当颜色特征不鲜明时，例如灰度图像或遥感图像，就会区分不出来。Schmid和Zisserman[16]应用几何约束（对极几何、单应参数系和曲线曲率）和互相关来进行线性匹配和曲线匹配。由于更多的几何信息可用于消除含糊不清的地方，还可以应付更显著的摄像机运动，Deng和Lin[17]提出的分组匹配方法更有优势。然而，它往往具有很高的复杂性，而且对线拓扑连接和不确定端点有一定的灵敏性。通过总结SIFT点描述符，Mikolajczyketal.[18]也提出了曲线描述符，Orrite和Herrero[19]提出了在射影变换下闭合曲线匹配部分连续Hausdorff距离不变。大多数曲线匹配的现有方法或要求初始条件，或限于特定场景，比如图像或平面场景。本文中，使用图像梯度内、外积介绍了表示图像边缘和特征点包括高曲率拐角与边缘点在内的图像特征向量场。然后，在已提出的特征向量场的基础上，构建了若干对于点匹配与曲线匹配，图像欧式变换和线性强度变化不变的新颖描述符。这些描述符很容易构建，只需要计算支持区域子区域中定义的特征向量的均值和标准差。实验表明，该描述符对于图像仿射失真、JPEG压缩和非线性强度变化是健全的，并且有良好的适应性。本文组织结构如下所示。第2部分介绍内、外相关性，并定义了图像的特征向量场。第3部分详细阐述了如何构建特征匹配的描述符。第4部分记录了实验结果，第5部分对特征向量场和描述符作了一些讨论，第6部分则是总结全文。模式识别43（2010）3273-32813/182特征向量场2.1内积和外积本文所使用的图像梯度为高斯梯度，点x处的梯度可表示为()((),())xyfxfxfx?，传统方式上，两个梯度的内、外积可定义为()()()()()()xxyyfxfyfxfyfxfy蜒=??o（2.1）()()()()()()xyyxfxfyfxfyfxfy奄???（2.2）在几何学中，外积是平行四边形由两个梯度()fxÑ和()fyÑ指向的区域，由于下面()()()()sinfxfyfxfyq奄?炎?（2.3）下面的方程式表明了内、外积之间的关系：/2()()()()fxfyfxRfyp奄?蜒o（2.4）这里/2Rp是/2p的旋转。不难证明，内、外积对于图像变换有以下性质：（1）对于欧式变换()()()gxfxxRxtⅱ==+，()()()(),()()()()gxgyfxfygxgyfxfyⅱⅱ蜒=蜒奄?奄?oo（2.5）（2）对于尺度变换()()()gxfxxxsⅱ==，22()()(1/)()(),()()(1/)()()gxgyfxfygxgyfxfyssⅱ蜒=蜒ⅱ奄?奄?oo（2.6）（3）对于仿射变换()()()gxfxxAxtⅱ==+，21()()det()()()gxgyAfxfy-ⅱ奄?籽傺（2.7）（4）对于线性强度变换()()gxfxab=+，22()()()(),()()()()gxgyfxfygxgyfxfyaa蜒=蜒奄?奄?oo（2.8）模式识别43（2010）3273-32814/182.2特征向量场内相关：使(){:}xyyxeeW=-?，它是一个中心为x，半径为e的圆形区域。点x到eW的正负内相关可定义为(|()()|()())/2iiiyxfyfxfyfxIpe+蜽=蜒+蜒åoo（2.9）(|()()|()())/2iiiyxfyfxfyfxIpe-蜽=蜒-蜒åoo（2.10）下面这个向量：()((),())IpVxIxIxpp+-=（2.11）称为点x到eW的正负内相关。图1内相关a)输入图像b)正内相关c)负内相关d)内相关的模图1显示了图像内相关的分布。（a）是输入图像，（b）是正内相关，（c）是负内相关，（d）是内相关的模，并定义为221/2()(()())IpVxIxIxpp+-=+。从图上可以看出，正内相关对图像边缘有鲜明的反映，而负内相关对高曲率的边缘点有鲜明的反映；因此，内相关的模很好地反映了图像边缘。从而，我们可以考虑用内相关的模衡量边缘点，即沿梯度方向内相关模的最大值被定义为边缘点。外相关：同样，因为图像梯度的外积，我们还可以定义外相关。点x到eW的正负外相关可定义为(|()()|()())/2iiiyxfyfxfyfxEpe+蜽=奄?奄?å（2.12）(|()()|()())/2iiiyxfyfxfyfxEpe-蜽=奄?奄?å（2.13）下面这个向量：()((),())EpVxExExpp+-=（2.14）模式识别43（2010）3273-32815/18称为点x到eW的正负外相关。图2外相关a)输入图像b)正外相关c)负外相关d)外相关的模图2显示了图像外相关的分布。（a）是输入图像，（b）是正外相关，（c）是负外相关，（d）是外相关的模，并定义为221/2()(()())EpVxExExpp+-=+。正、负外相关都对图像拐角和高曲率的边缘点有鲜明的反映，并且外相关的模很好地反映了它们。因此，我们可以使用外相关的模衡量特征点，并将其局部最大值作为特征点的定义。图3边缘检测和点检测a)输入图像b)内（外）相关的模c)检测边缘（特征点）图3显示了一个使用内、外相关进行图像边缘检测和特征点检测的例子。（a）是输入图像，（b）是正（外）相关的模，（c）是检测边缘（特征点）。特征向量场：在定义了内、外相关后，由每个图像的一个4维向量，点x可以推出4()((),())IpEpxxxRFVVV=?（2.15）由于图像的边缘和特征点是两个最重要的图像特征，矢量()FVx被称为点x的特模式识别43（2010）3273-32816/18征向量，向量场(){()|}FIFVxxI=?被称为图像I的特征向量场。从图像变换的内、外积性质，对于特征向量场，我们有以下属性：：（1）对于欧式变换()()()gxfxxRxtⅱ==+，()()gfxxFVFV¢=（2.16）（2）对于尺度变换()()()gxfxxxsⅱ==，2()(1/)()gfxxFVFVs¢=（2.17）（3）对于仿射变换()()()gxfxxAxtⅱ==+，21()()()detggEpEpxAxVV-¢=?（2.18）（4）对于线性强度变换()()gxfxab=+，2()()gfxxFVFVa=（2.19）3特征描述在本部分中，特征向量场用于构建点匹配和曲线匹配的描述符。3.1点描述使(){|}rxyyxrW=-?为一个特征点为x，半径为r的圆形邻域。为了考虑邻域rW内特征向量的统计特性，我们把rW分为子区域12,,,MRRRL。通过计算子区域iR内特征向量的均值和标准差，我们获得了两个4维向量。211()(),()(()())##iiiiixRxRiixFVxsdxFVxmxRRm挝==-邋（3.1）使1212()((),(),()),()((),(),,())MMxxxxsdxsdxsdxsdxmmmm==KK（3.2）分别标准化()xm和()sdx为单位模，幷连接成一个向量，我们可以获得一个8M维向量。模式识别43（2010）3273-32817/188()(),()()()()MmxsdxmxsdxMSDPxR=?（3.3）这个向量被称为点x的均值—标准差描述符，记为MSDP。根据rW的不同划分，我们可以得到不同的MSDP描述符。在本文中，我们认为只有以下三种划分：R-MSDP描述符：如下划分邻域rW为M个环：{|(1)//},1,2,,iyriMyxriMiMR=--?L。如此划分的MSDP描述符称为R-MSDP描述符。S-MSDP描述符：如下划分邻域rW为M个等距扇形：{|2(1)/()2/},1,2,,mainmainiSyiMArgyxiMiMpqpq=-+-?=L。这里mainq特征点X[5]的主要方向。如此划分的MSDP描述符称为S-MSDP描述符。RS-MSDP描述符：邻域rW被同时分为M个环和N个扇形，从而我们得到MN个子区域。如此划分的MSDP描述符称为RS-MSDP描述符。由等式（2.16）和（2.19），我们可以证明，所有这三种描述符，R-MSDP，S-MSDP和RS-MSDP对图像欧氏变换和线性强度变换有不变性。在本文的实验中，我们设定r=16，并且只低维使用这三种MSDP描述符所示，如图4所示，这分别是64维R-MSDP描述符（R-MSDP64），64维S-MSDP描述符（S-MSDP64）和64维RS-MSDP描述符（RS-MSDP64）。图4本文中的三种MSDP描述符模式识别43（2010）3273-32818/183.2曲线描述支持区域：为了描述曲线C，需要先定义一个支持区域。假设C由N个点组成，记为12{,,,}NCxxx=L。对于每一个ixCÎ，中心在这里，大小为m(2n+1)m，沿点ix梯度方向的矩形区域，就是支持区域。如图所示，图5中的矩形区域iRT，图中所有的iRT就是C的支持区域，记为()CW。图5曲线支持区域和分区为了更详细地表征支持区域，每一个iRT被分为大小同为mm´的（2n+1）个子区域，并且这些子区域记为,1,2,,21ijRTjn=+L，方向是梯度方向id，因此，我们对于iRT可以获得一组有序子区域。12(21){,,,}iiiinOSRTRTRT+=L（3.4）定义1(1,2,,21)NjiijRRTjn==?+L（3.5）这是我们得到的支持区域()CW有序组iOS所有第j列元素。211()niiCR+=W=?（3.6）由于在有序分区iRT使用了梯度方向id，支持区域()CW的分区具有旋转不变性。基于