一种多尺度轮廓方向变化率的角点检测算法

一种多尺度轮廓方向变化率的角点检测算法

0基于局部极值设计的角点检测算法角点是图像的一个重要局部特征之一，决定图像中的目标形状。因此，角点检测对图像的构成、运动跟踪、目标识别和其他领域非常重要。另一方面,尺度空间作为表示图像特征信息的一种重要思想方法,它在图像特征信息处理模型中引入尺度参数,通过尺度参数的连续变化获得不同尺度下的视觉特征信息,然后综合这些特征信息就可以深入挖掘图像的本质特征。所以,尺度空间方法是研究角点特征点提取及其性质的一种重要方法。例如,经典的Harris角点检测算法把图像看成一个三维的几何曲面,而角点被定义为曲面上两个主曲率都较大的点,从而根据反映曲面主曲率的自相关矩阵构造了角点的响应函数,但该算法缺乏多尺度检测特性。于是,陈白帆等人通过高斯尺度空间引入尺度参数使Harris算法获得了多尺度检测的能力。Mokhtarian等人和Rattarangsi等人都把角点定义为轮廓曲率的局部极值点,并分别提出了基于高斯曲率尺度空间的角点检测算法。他们所提出的角点算法首先提取图像轮廓,并用不同尺度的高斯核对轮廓做演化,得到在各个尺度下的轮廓演化版本。然后把高尺度下的图像轮廓曲率的局部极值点作为候选角点,并从高尺度到低尺度对候选角点进行跟踪定位,从而得到准确的角点位置。文献分析了Mokhtarian算法的不足,并利用角点处的局部信息改进了该算法。Lee等人提出了基于小波变换的多尺度角点检测方法,该方法对图像的轮廓方向做小波变换,并把小波变换模极大值点作为候选角点。Quddus等人运用SVD方法进一步确定了小波变换检测角点的最优尺度问题。值得注意的是,这些方法虽然都运用了多尺度方法,但存在共同的缺点:确定候选角点时,仅使用了单一尺度,并没有有机地融合各个尺度的特征信息。这使得确定候选角点时,尺度过大容易丢失真实角点,尺度过小容易受噪声的影响。本文基于轮廓方向和B-样条尺度空间理论以及多尺度乘积思想提出了一种新的角点检测算法。该算法首先利用B-样条尺度空间的优良特性构造了轮廓方向变化率多尺度表示,然后在此基础上定义了轮廓方向变化率的多尺度乘积,并把多尺度乘积的局部极值点作为候选角点。所定义的多尺度乘积包含了多个尺度的特征信息,使得候选角点检测真正实现了多尺度检测,从而有效地解决了候选角点检测的单一尺度问题。论文不但分析了多尺度乘积算法的检测定位性能,而且通过对比实验验证了多尺度乘积的有效性。1b-样本的多尺度表示轮廓方向的变化率本章将依据B-样条尺度空间理论逐步构造基于B-样条尺度空间的轮廓方向变化率多尺度表示。1.1轮廓方向的估计设C(u)表示从图像中提取出来以u为参数的一条轮廓,即:C(u)=(x(u),y(u))(1)其中,x(u)和y(u)分别表示以u为参数的轮廓横坐标和纵坐标,轮廓上第i个离散点可以由ui来表示。则,由式(1)表示的轮廓在任意点处的轮廓方向φ(u)可以定义为:φ(u)=arctan(dy/dudx/du)(2)φ(u)=arctan(dy/dudx/du)(2)在文献,为了计算轮廓方向,使用一阶差分替代式(2)的导数,但轮廓方向的分辨率仅为π/4。为了提高轮廓方向的分辨率,将任意点ui处的轮廓方向定义为:φ(ui)=arctan(y(ui+q)-y(ui-q)x(ui+q)-x(ui-q))(3)φ(ui)=arctan(y(ui+q)−y(ui−q)x(ui+q)−x(ui−q))(3)式中,整数q≥1,q越大表示轮廓方向的分辨率越大。文献直接对轮廓方向φ(ui)做B-样条小波变换,并把大尺度下的大于给定阈值的小波变换模极大值点定义为候选角点。为了提高角点的定位精度,从大尺度到小尺度对候选角点进行跟踪定位,从而得到小尺度下的角点的精确位置。但该方法明显地存在以下几个缺点:受轮廓噪声和量化噪声的影响,式(3)容易出现奇异或病态值,使得轮廓方向极其不稳定;检测候选角点的尺度只在单一的尺度下进行,其尺度的选择存在如下的矛盾,尺度大容易丢失真实角点,尺度小产生伪角点;参数q的决定依赖于两个相互矛盾的因素,也就是轮廓方向的分辨率和角点的辨别能力。q的取值越大,轮廓方向的分辨率越高,角点辨别能力却越低。1.2bmbng在图像的轮廓模型式(1)中引入尺度参数,让其在B-样条尺度空间中演化,,从而形成B-样条的轮廓尺度空间。设n阶尺度为m的离散B样条函数为:Bnm=n+1⌢B0m*B0m*⋯*B0m(4)Bnm=B0m*B0m*⋯*B0mue150ue151ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154ue154n+1(4)其中,B0m0m=(1/m)[1,1,…,1]表示宽为m的归一化的采样脉冲。那么,轮廓C(u)在不同尺度下的演化版本就可以通过与B-样条函数做卷积而得到:C(u,m)=(X(u,m),Y(u,m))(5)式中,X(u,m)=x(u)*Bnmnm,Y(u,m)=y(u)*Bnmnm,Bnmnm表示n阶尺度为m的离散B-样条函数,*表示卷积算子。通常把式(5)叫作轮廓的B-样条尺度空间,注意该空间的特性与热扩散方程驱动的高斯尺度空间非常相似。这是由于,当B-样条的阶数n趋于无穷时,根据中心极限定理,B-样条将逼近高斯函数。而且,根据文献,式(5)的高计算复杂度的卷积运算可以转化为复杂度仅为O(N)的加法运算,所以本文使用B-样条来表示轮廓的多尺度演化版本,从而可以获得有效计算方法。1.3轮廓方向变化率多尺度当轮廓用B-样条尺度空间来表示时,基于式(5)的轮廓C(u)在尺度m下的轮廓方向φ(u,m)可以表示为:φ(u,m)=arctan(dY(u,m)/dudX(u,m)/du)(6)φ(u,m)=arctan(dY(u,m)/dudX(u,m)/du)(6)显然,与式(2)的区别在于式(6)的轮廓方向包含了尺度信息。由式(6),轮廓方向变化率就等于关于参数u的导数D(u,m):D(u,m)=dφ(u,m)du=X¨Y⋅-Y¨X⋅X⋅2+Y⋅2(7)D(u,m)=dφ(u,m)du=X¨Y⋅−Y¨X⋅X⋅2+Y⋅2(7)式中,X·=dX(u,m)/du,X¨=d2X(u,m)/du2,Y·=dY(u,m)/du,Y¨=d2Y(u,m)/du2。我们知道,信号与B-样条函数的一阶和二阶导数的卷积就是信号的一阶和二阶小波变换。于是,轮廓与B-样条函数的一阶和二阶导数就可以分别定义为轮廓演化版本的一阶和二阶小波变换W1C(u,m)、W2C(u,m),则有:{W1C(u,m)=∇uC(u,m)W2C(u,m)=∇2uC(u,m)(8){W1C(u,m)=∇uC(u,m)W2C(u,m)=∇2uC(u,m)(8)如果定义∇uf(u,m)=f(u+12,m)-f(u-12,m)∇uf(u,m)=f(u+12,m)−f(u−12,m),则式(8)所表示的一阶和二阶小波变换是光滑轮廓C(u,m)的一阶和二阶差分。根据式(8)的定义,我们进一步可以得到离散点ui在尺度mj下的轮廓方向变化率多尺度小波表示:D(ui,mj)=W2X(ui,mj)W1Y(ui,mj)-W1X(ui,mj)W2Y(ui,mj)(W1X(ui,mj))2+(W1Y(ui,mj))2(9)D(ui,mj)=W2X(ui,mj)W1Y(ui,mj)−W1X(ui,mj)W2Y(ui,mj)(W1X(ui,mj))2+(W1Y(ui,mj))2(9)我们把式(7)或式(9)叫作轮廓方向变化率的B-样条多尺度表示。式(9)与由式(3)的差分计算轮廓方向变化率相比,其思想有根本的改变,式(9)把轮廓进行演化之后再做小波变换,这样使得轮廓噪声和量化噪声在演化的过程中得到抑制,从而计算轮廓方向变化率将变得更加稳定。而式(3)直接使用边界轮廓离散点,这非常容易受量化噪声和轮廓随机噪声的影响,从而导致轮廓方向变化率的计算极不稳定。更为重要的是,式(9)表示了不同尺度下的轮廓方向变化率,而式(3)只是单一尺度下的轮廓方向变化率。2基于多尺度积的角点检测算法本章将在前面所构造的基于轮廓方向变化率B-样条多尺度表示的基础上,提出一种基于多尺度积的角点检测方法,并对算法的定位性能进行了分析和比较。2.1轮廓方向变化率多尺度积的检测当轮廓从小尺度到大尺度进行演化时,受轮廓噪声和量化噪声干扰的轮廓边界点的特征信息将得到抑制,而真实角点的特征信息将保留下来。图1中的(a)和(b)分别是人工图像和它的边缘图像。图2表示图1(b)的轮廓方向变化率,其中,图2(a)表示了轮廓没有演化的轮廓方向变化率,从该图中可以看出,轮廓方向变化率极容易受到轮廓量化噪声的影响。而图2(b～d)分别表示mj等于4,5,6的轮廓方向变化率。显然,轮廓方向变化率从小尺度到大尺度的变化规律是:轮廓的重要几何特征不但保留了下来,而且轮廓的噪声随着尺度的增加得到了抑制,但轮廓重要的几何特征的位置发生了小移位。轮廓方向变化率的这种特性,与文献中所分析的边缘特征信息的变化特性极其相似。而该文献充分利用图像边缘特征信息的这种多尺度特性,构造了多尺度乘积的方法,使得边缘特征信息增强,同时抑制噪声的影响。于是,本文利用轮廓方向变化率的特征信息,构造如下的多尺度乘积:Μ(u)=S∏j=1D(u,mj)(10)M(u)=∏j=1SD(u,mj)(10)式中,S表示离散B-样条函数的尺度数目,M(u)表示轮廓方向变化率多尺度积。根据B-样条尺度空间的因果性,轮廓重要几何特征不会随尺度的递增而增加,并且噪声在大尺度下会被迅速减弱,而真正的角点处的变化率会因为乘积而相对增大,从而多尺度乘积可以很好地检测出真实角点,且保持了角点的位置和对噪声良好的鲁棒性。图3表示了图1(b)轮廓的多尺度乘积,明显地,M(u)可以增强角点的轮廓方向变化率,同时极大地抑制其他点的轮廓方向变化率。这样,用一个全局阈值就可以获得全部的真实角点。图1中(c)中的角点,是通过取阈值等于0.002,mj(j=1,2,3)分别选取4,5,6而得到的好的检测结果。于是,由轮廓方向变化率多尺度乘积的特性,可以建立一种新的角点检测方法。该方法首先提取图像的轮廓,然后在B-样条尺度空间中对轮廓进行多尺度演化,得到不同尺度下轮廓的演化版本,最后,利用式(10)计算轮廓方向变化率多尺度积,并把它的绝对值的局部极大值点作为候选的角点。算法步骤如下:1)运用Canny算法提取图像的边缘轮廓C(u);2)根据式(5),计算轮廓在不同尺度下的演化版本C(ui,mj),1≤i≤N,1≤j≤S,其中N表示原始轮廓的采样点数,S表示所选择的尺度数目;3)根据式(10)计算轮廓方向变化率多尺度积;4)把轮廓方向变化率多尺度积的绝对值的局部极大值且大于给定的全局阈值t的点作为角点。2.2方向变化率的曲线图放在乘积M(u)中,融入了几个尺度下的轮廓方向变化率,把M(u)的局部极大值定义为角点,该角点的检测就自然包含了各个尺度的特征信息。这样,算法既保留了小尺度的精确定位特征,又有大尺度的抗噪性能,从而可以有效地抑制单一尺度下引入的噪声,提高了算法的鲁棒性,如图3所示。为了分析该检测算法的定位性能,可以把轮廓方向变化率的曲线图放大。例如,图4表示了图2(b～d)的轮廓离散点从500到650的轮廓方向变化率。从该图可以观察到这样一个事实,相邻尺度之间的同一个几何特征的位置偏移量变化很小,可以假设|Δuj|≤1(1<j≤S);同时,角点邻域内的局部曲线近似于高斯函数的曲线,于是第j个尺度下任意角点u处的局部邻域的轮廓方向变化率可以表示为bjexp(-(x-u-Δuj)2/aj),其中,常数aj随B-样条尺度因子增大而增大,则在该点u处邻域上的多尺度乘积可以表示为:Μ(x)=S∏j=1bj[exp(-(x-u-Δuj)2/aj]=Bexp(-S∑j=1[(x-u-Δuj)2/aj])=Bexp(-(x-u-ΔU)2/A+C)(11)其中,S表示离散B-样条函数的尺度数目,B=S∏j=1bj,而ΔU,A,C是把高斯函数的指数配方之后的值。显然,角点定位精度就由ΔU来确定。角点定位的最坏情形是,Δuj=1而且aj相等。此时可以得到,当S=3时,ΔU=1,这表明定位误差不会大于一个像素,从而证明了所提出算法的定位准确性。3实验结果与分析为了说明所提出算法的优越性,下面将通过对比实验来验证。这些实验包括了Plessey、Kitchen、SUSAN、CSS和增强CSS等算法。为了叙述方便,本文所提出的算法用MSM(Multi-ScaleMultiplication)来表示。为了验证算法,我们做了大量的实验,但本文只给出了方块和房屋图像的检测结果,这两幅图像被广泛地用于展示角点检测的实验结果,其中房屋图像拥有很多的细节和纹理特征。MSM算法中的边缘提取直接使用了Matlab中所提供Canny边缘检测函数,其参数选取为默认值。MSM算法的尺度参数因子mj(j=1,2,3)分别选取了4,5,6。而阈值t选取0.0001至0.0005之间的任意值。其他算法检测结果都是通过调节参数达到的最好结果。实验结果显示MSM检测器都获得了6种检测器中的最佳效果。木块图像的角点检测较为复杂,从图5中可以看到前面三个检测器的效果不太理想,后三者均能检测出较多的正确角点,不过与MSM相比,CSS