局部描述子

局部描述子（共7篇）

局部描述子 篇1

1 引言

一般而言, 关键点检测、描述子生成与描述子匹配构成图像匹配的三个步骤。其中, 描述子的生成, 旨在构造具有鉴别力强、鲁棒性高且计算复杂度小的描述子。特征描述子广泛用于人脸识别[1]、场景分类[2]、图像检索[3]、视频动态行为分析[4]等领域。局部特征描述子的基本思想是利用关键点构造领域块, 采用不同的方法构造该块的描述信息, 通常表示为特征描述向量, 继而根据不同特征空间的相似度度量准则 ( 比如欧式空间的欧式距离、汉明空间的汉明距离等) , 找出相似匹配的关键点。现实图像的拍摄, 由于存在着不同时期、不同角度、不同光照和不同距离等的因素, 寻求具有高鉴别力的描述子显得至关重要。与此同时, 由于应用需求而需要处理更大数据量[5,6], 或者需要在具有限制计算能力的移动设备上运行[7], 好的描述子不仅具有很高的鉴别性, 而且具有快速生成、快速匹配和合理利用内存的特性。由于本文主要针对于局部特征, 文中涉及的二值描述子和实值描述子均为局部描述子, 即用于描述关键点周围图像块的特征信息。

传统的描述子采用欧式空间表示, 并根据欧式距离作为其度量准则, 选择距离最小的作为其相似对。比如SIFT[8]描述子, 从生成复杂度考虑, 在关键点周围提取16×16领域块 ( 尺度均一化后) 构造4×4子区域, 计算区域内每个像素的梯度并建立8个方向的梯度直方图, 总共构成4×4×8 =128维的特征向量, 至少需要1280次乘法、512次加法; 从利用内存角度考虑, 一个整型数据 ( int型) 在32位编译器中占据4个字节 ( 即32位) , 每个SIFT特征共需4096位; 从匹配复杂度考虑, 两个整型数据的欧式距离需要2次乘法、1次加法。从内存使用情况考虑, 传统的描述子SURF[9], GLOH[10]在欧式空间分别是64维, 272维整型数据, 即2048位和8704位, 具有很高的维度。PCA - SIFT[11]采用PCA降维的方法将SIFT降到20维或者更低, 实验表明, 640位的描述子仍具有很高的维度。

二值字符串描述子采用汉明空间表示, 根据汉明距离、Cayley距离或者Kendall’s tau距离[12]描述其空间距离, 同样选择距离最小的作为其相似对, 常见二值特征有BRIEF[5,6], ORB[13], BRISK[14]等。比如BRIEF描述子, 考虑其采用矩形滤波器 ( 积分图计算) 和256维度, 从生成角度考虑, 构造48×48领域块, 只需要768次加法; 从利用内存角度考虑, 只占有256位; 从匹配复杂度考虑, 汉明距离只需在相同位求异或操作, 复杂度远远低于欧式距离的计算。二值化特征在内存使用情况和匹配策略上占据很大的优势。

Miksik和Mikolajczyk[15]评估了最新实值描述子与二值描述子: 并表明二值描述子为运行时间最快的描述子, 其中实值描述子包括SIFT、SURF、LIOP[16]、MRRID和MROGH[17]; 二值描述子包括BRIEF、BRISK和ORB。实值描述子的匹配策略采用随机K - D树计算最小欧式距离, 二值描述子采用贪婪算法计算最小汉明距离。ORB和BRIEF ( 32×8维) 匹配速度近似与采用K -D树的SURF描述子, 5.6倍于采用K -D树的SIFT描述子。没有一种特征适合于所用情况, 对于传统经典的描述子 ( 比如SIFT、PCA - SIFT、SURF) , SIFT鲁棒于旋转、尺度变化和仿射变化, 但运行速度慢且敏感光照变化; SURF运行速度快且拥有与SIFT近似的性能, 但是对于旋转变化和光照变化敏感; PCA -SIFT相比SIFT在运行时间和仿射变化性能有所提升, 但是敏感于尺度变化和平滑模糊[18]。ORB描述子———一种基于主方向的二值描述子———相比于经典SIFT、SURF描述子, 对于室内数据集表现出相似效果, 而对于室外数据集表现更好的效果[13]。另一方面, 采用子区域的差值可以有效的去除测光变化 ( 比如, 光照对比度变化、平滑、噪声等) [5, 6, 19]。

由于基于像素值的二值化描述子, 对于采样方式、尺度和旋转敏感。对于旋转问题, 传统的实值描述子常常采用求取主方向[13,14]或者区域像素值排序[16,17]的策略, 二值描述子 ( ORB) 即采用主方向解决旋转问题; 对于采样方式问题, BRIEF采用高斯随机采样、ORB采用贪婪搜索采样、BinBoost[20]和LDB ( Local Difference Binary) [7]采用Adaboost学习采样, D - BRIEF[21]进行学习采样等。由于直接对像素值二值化鲁棒性低[20], 目前研究者将像素值做一次变换, 得到实值特征后进行二值化处理, 比如LDAHash[22]采用SIFT特征作为其实值特征, Simonyan等[23]利用梯度组合作为其实值特征。

以下论文安排如下: 第二章从三方面具体介绍目前二值描述子; 第三章介绍二值描述子在标准数据库的实验比较; 第四章进行总结和讨论。

2 局部二值描述子

本章主要从三方面具体介绍二值描述子: 采样方式比较; 人工设计的二值描述子 ( hand - crafted binarydescriptors) ; 学习 ( 监督学习) 的二值描述子。

2. 1 二值描述子采样方式

二值描述子通过比较图象块内特定子块特征的灰度值、梯度等形式二值描述, 如对子块进行采样, 是获取二值描述子的一个基本方式。不同的采样方式, 导致不同的二值序列。一种方案是选择不同区域的像素值计算检验子 ( 比较大小方式) 。BRIEF[5,6]考虑靠近块中心的像素点比边缘像素点稳定的事实, 采用各向同性的高斯分布采样点对, 如图1 ( a) 。只考虑两个区域的像素值, 可能不具有很好鉴别性, D -Brief[21]将其推广多个不同的区域, 通过给定一组字典将每个特征表示为不同字的线性组合, 如图1 ( d) , 构造可以快速计算的滤波器, 比如用积分图快速计算的矩形滤波器 ( 箱滤波器) 和高斯滤波器, 通过训练样本学习线性投影矩阵, 最后二值化得到二值特征。ORB[13]采用BRIEF采样策略, 根据所求主方向进行旋转标准化后, 采样序列之间的相关性增大、方差降低, 故ORB采用生成大量的二值序列, 贪婪选取前N个二值特征作为其描述子, 其中该二值特征具有高方差、平均值接近0.5和低相关性, 最后选择的采样方式如图1 ( c) 。BRISK[14]采用类DASIY[25]方式采样, 如图1 ( b) , 靠近块中心采样圆区域半径小, 靠近边缘圆区域半径大, 也是考虑块中心的像素点比边缘像素点稳定的事实。

考虑直接计算像素值可能不具有鲁棒性, 另一种方案采用将像素值做一次变换来计算相应的检验子。LDB[7]采样像素值和梯度值采样, 如图1 ( e) 左图, 将块分成N×N网格, 分别计算像素值总和、x方向梯度和与y方向梯度和, 采用一阶梯度可以有效的提高准确度, 对于测光变化, 梯度值相比像素值更具有鲁棒性。BinBoost[20]采用监督学习方法学习采样策略, 别针对像素值与梯度值学习, 图1 ( f) 基于像素值学习后的空间采样布局, 其中S为高斯平滑核大小, 分布给出S =3和学习得到S的空间采样布局, 可以看到经过AdaBoosting学习的基于像素值的空间采样兼容BRIEF和ORB两种采样方式的优点, 即采样点尽可能的靠近块中心区域和采样点对尽可能的满足垂直趋势。采用基于梯度的采样策略, 性能高于基于像素值采样策略[20], 这也证明梯度值比像素值更具有鲁棒性和鉴别性。表1给出目前二值描述子的计算方法, 并列出关于块大小、尺度处理、空间采样方式、检验子计算和默认的特征维度的详细情况。

Simonyan等[23]将局部特征描述子的学习建模为凸优化学习, 考虑到旋转不变性, Simonyan等采用分组策略, 如图1 ( g) 定义不同池区域 ( PR, Pooling Region) , 蓝色圆环 ( 只有中心一个) 为一组, 红色圆环为一组 ( 位于垂直和水平方向) , 绿色圆环为一组 ( 位于斜对角方向) , 将选择PR转换为凸优化求解。

2. 2 人工设计的二值描述子

本节主要介绍三种人工设计的二值描述子, 重点介绍不同的检验子和二值描述子的构造。

( 1) BRIEF描述子[6]: BRIEF描述子采用经过高斯滤波或者矩形滤波后S×S大小的块p, 定义二值检验子:

其中I ( p, x) 为块p在位置的像素值。BRIEF描述子采用个二值检验子构成:

( 2) ORB描述子[13]: 考虑BRIEF对旋转敏感, ORB采用主方向[24]调控BRIEF描述子。由于旋转后BRIEF描述子之间方差变小, 关联性增强, 故ORB采用贪婪算法选取前n个检验子。如图1 ( c) 左右图比较, 右图具有比较稳定的分布且对之间的相关性降低。

( 3) BRISK描述子[14]: BRISK描述子采用类似DAISY[25]方式采样, 如图1 ( b) , BRISK定义N个均匀空间分布圆。对于旋转问题, BRIEF采用类似主方向方式得到a。BRISK的二值检验子定义如下:

其中, 为在旋转角度后的块在尺度的像素值。为BRISK定义的短距离对。

2. 3 学习型的二值描述子

理想的描述子应该具有很好的鲁棒性和鉴别性。基于像素值的二值描述子对采样方式及其敏感: 所选区域过小, 由于获取块细节部分, 具有良好的鉴别性, 但鲁棒性降低; 所选区域过大, 具有良好的鲁棒性, 但鉴别性降低。理想的描述子也应该具有①匹配点之间的距离相对较小, 非匹配点之间的距离相对较大; ②不同维度之间相关性较小。研究者常采用首先生成高维的二值描述特征, 然后根据这两个约束条件选择相应的维度 ( 即bit -selection) 。目前主要指进行有监督的学习的二值描述子。

( 1) D -Brief[21]: 考虑到BRIEF的采样方式, 只选择两个点计算其检验子, D -BRIEF扩展为多个区域的线性组合, 并将其阈值化得到二值特征。数学公式为, 其中表示描述子维度, 为投影矩阵, 为阈值。目标是优化求解。为了快速计算, D -Brief采用学习为字典D的字的线性组合, 即, 并约束为稀疏向量 ( 即其中多数元素为零) 。故问题建模为

其中, 分别为匹配对与非匹配对, 为稀疏诱导范数, 为权衡系数。

求出后, 采用公式得到实值特征, 并根据阈值化得到二值特征。论文字典D采用三种字典, 分别为箱滤波器、高斯滤波器和矩形滤波器。

( 2) LDB[7]: 由于AdaBoosting方法在区分人脸与非人脸之间有很好的效果[26], 直观的认为AdaBoosting方法可以用于选择采样对, 然后在每次选择过程中, 重新赋值权重, 加大非匹配点的权重, 可以有效降低将被选择的位与已经选择位的关联性。

二值的基于AdaBoost的方法不同于实值, ①采用实值的权重导致最后位选择为非二值化, 加大匹配运算复杂度; ②在级联每次循环中, 原始算法选择最优的分开正样本和负样本的特征, 而二值描述子为在每次级联循环中, 选中位与已选择位应集合一起计算对之间的汉明距离。LDB做法为针对①将所有选中位的权重赋值为相等值; ②修改特征选择准则: 替代一次循环中的最小分类误差为每次循环后的累计误差。

( 3) BinBoost[20]: 考虑在块x寻求二值描述子c ( x) =[C1 ( x) , …, CD ( x) ], 其中Cd ( x) =sgn ( bTdhd ( x) ) , 考虑到该函数, 类似于AdaBoost最后的总体分类判决函数。故采用Boosting方法建模该函数, 其中hd ( x) =[hd, 1 ( x) …hd, k ( x) ]T为K个弱分类器, bd=[bd, 1…bd, k]T为权重系数。考虑{ ( xn, yn, ln) }Nn = 1训练集合, 其中ln= 1表示xn, yn为匹配对, 对ln= - 1表示xn, yn为非匹配对, 建立如下目标函数:

其中cd ( xn, yn; bd, hd) =Cd ( x) Cd ( y) =sgn ( bTdhd ( x) ) sgn ( bTdhd ( y) ) , 最小化该公式表示降低匹配点之间的汉明距离, 同时增大非匹配点之间的汉明距离。

( 4) 凸优化学习局部特征描述子: 该方法借鉴于Brown等人的学习局部描述子的方法流程[27], 如图2, 同样采用高斯进行平滑预处理, 计算梯度并将梯度幅度当作权重赋给梯度方向, 得到p =8个特征通道, 并归一化处理, 论文考虑将采样过程 ( 选择PR) 和降维过程分别转换为凸函数, 并优化求解, 其中PR如图1 ( g) 。选择PR过程:

可分。前一

∈个约束建模为满足:dw ( x, y) +1 <dw ( u, v) ,  ( x, y) ∈P, ( u, v) ∈N

其中:

并且θ ( x, y) = ( x) - ( y) 和A =WTW为马氏矩阵。此约束关于W为非凸函数, 但关于A为凸函数, 考虑到A为半正定矩阵, 存在一个投影矩阵W, 使得A =WTW故对W的优化求解, 可以转换为对A的优化求解。类似PR选择方法, 将公式建模为

其中, 核范数︱︱A︱︱*为表示为矩阵A的奇异值之和, μ*> 0为权衡系数。

4 实验比较

用于图像匹配的常见的两个标准数据库包括牛津大学特征测试图①和学习局部描述子块数据集②, 如图3。

牛津大学特征测试数据库包括五组, 分别测试在以下条件下的鲁棒性:

( 1) 2维视觉变化 ( Viewpoint Changes: VC) : Wall, Graffiti;

( 2) JPEG压缩 ( Compression Artifacts: CA) : Ubc;

( 3) 光照变化 ( Illumination Changes: IC) : Leuven;

( 4) 图像平滑 ( Image Blur: IB) : Bikes, Trees;

( 5) 尺度 +旋转变化 ( Zoom + Rotation: ZR) : Bark, Boat。

测试准则为针对不同的数据库的参考图和测试图, 分别提取, 个关键点, 通过单一性矩阵求取匹配对, 标记为真实匹配对; 针对每两组的点集, 分别根据不同的描述子计算最近邻, 标记为实验所得匹配对; 最后计算实验所得匹配对中的真实匹配对, 并计算正确匹配率。表二给出二值描述子在此数据库的测试结果, 此表只给出第一幅测试图与第六幅测试图 ( 相对具有较大的变化) 的结果。可以看出LTD[19]采用三位编码要强于两位编码。

学习局部描述子块数据集包括三个数据子集: Liberty ( Lib) , Notre Dame ( NoD) 和Yosemite ( Yos) 。每个子集中包括400k - 尺度和旋转归一化的64* 64块。根据差分高斯检测关键点, 并提取围绕关键点的块, 并利用多视角的立体视觉算法得到匹配对。每个数据集包括匹配的图像块对的数目:100K, 200K, 500K, 分别包含50%的正确匹配点对和50%错误匹配点对。实验结果采用ROC曲线, 并报告召回率 ( recall rate) 95%的错误率 ( error rate) 。

表3给出二值描述子在学习局部描述子数据测试结果。实验结果分析如下, 采用基于像素值计算检验子性能远差于采用基于梯度值计算的检验子, 说明梯度值相比于像素值在小尺度和小旋转变化范围内更稳定。采用梯度计算的检验子性能高于实值描述子的性能, 并考虑二值描述子在计算复杂度和匹配时间上的优势, 二值描述子在图像匹配中体现越来越重要的地位。

5 结束语

二值描述子具有计算复杂度低, 占用内存低, 正确匹配率高的优势, 逐渐成为当今研究者研究的热门方向。局部特征描述子, 往往是根据检测出的关键点, 围绕关键点提取特征大小的图像块, 计算不同的描述子。然而局部的二值描述子由于采用二值字符串作为其描述子, 对于块大小、空间采样方式、检验子的求取、特征维度敏感, 本文总结了目前二值描述子计算的方法, 包括人工设计和监督学习进行空间采样。

二值描述子采用基于像素值计算检验子, 对于光照、平滑和JPEG压缩[5,6], 小角度的视角变化、非统一的高斯亮点、12度内的旋转和小尺度变化有一定的鲁棒性[19]。人工设计的二值描述子表明一种事实, 即采样方式依据中心的像素点比边缘像素点稳定。为了进一步的隐低二值特征描述子的维度与满足旋转不变性。一方面, 研究者采用不同的监督学习办法, 根据匹配点对之间的汉明距离小、非匹配点对之间的汉明距离大和选中的二值序列之间相关性最低等原则学习新的空间采样方式, 极大的提高了二值描述子的正确匹配率, 同时也降低了二值描述子维度[21,22]; 另一方面, 考虑基于梯度值比像素值稳定的事实, 研究者将梯度替代像素值计算检验子, 在大数据库测试结果表明, 二值描述子的正确匹配率高于传统经典描述子 ( 比如SIFT、SURF和学习得到的特征描述子[27]) 。将基于像素值得到的二值描述子, 采用主方向解决旋转问题和采用建立多尺度金字塔解决尺度问题后, 二值描述子表现性能从时间运行、内存占有和正确匹配精度上, 超过传统的经典的描述子[7]。

融合轮廓和区域特征的形状描述子 篇2

在基于内容的图像检索中,形状是一种主要的低层特征,它是人对图像理解的重要内容之一,相比于颜色和纹理特征,它更能从语义上描述目标图像。有关形状分析的研究至今已有几十年历史。文献[1]将现有的形状描述子分为两大类,一类是基于轮廓的描述子,另一类是基于区域的描述子。

轮廓形状描述了图像的边界信息,由于轮廓描述法具有易于提取的特点,因此在很多场合得以应用。轮廓法又分为两个子类,一类将边界作为整体,从中提取表示形状的参数(轮廓曲线坐标、质心距离[1]、三角形面积函数[2]、拱高[3]等等),再进行后续处理,形成诸如曲率尺度空间[4]、傅立叶描述子[1,5]、小波描述子[6]等形状描述法。另一类根据一定的准则,将边界用原语表示,最终的形状特征通常用字符串或树来表示。

在第二类形状描述法的提取过程中,区域的所有像素都参与形状描述。其中,矩是一种有效的描述法,常见的矩有Hu不变矩[7]、Zernike矩等。除此之外形状的分区描述法也是一类有效的区域描述法。

形状的轮廓描述和区域描述各有利弊。前者主要对目标边界上的像素进行处理,从视觉生理的角度讲,这类方法更接近人眼识别形状的机理,而且该类方法参与计算特征的数据量小。后者是对整个区域像素进行处理,其参与计算的数据量大,相比前者,该类方法在抵抗噪声等外部干扰上具有较强优势。文献[8]给出一个评价形状特征优劣的准则:较高的检索准确率,紧凑的描述性,具有通用性,计算复杂度低,并且对图形的检索具有鲁棒性等。其中较高的准确率是最基本也是最重要的准则。

为了提高检索的性能,现提出一种综合轮廓与区域描述优点的形状特征。该算法从图像的边界曲线中提取表示形状内容的空域和频域描述,为了克服轮廓法过于依赖边缘检测结果的弊端,算法结合形状矩阵这一区域描述,组合形成具有较高检索性能的混合形状描述子。

1 混合形状特征的提取

1.1 轮廓特征

一般描述形状的图像可分为目标区域与背景区域,因此往往用1和0两个值来表示图像,即对图像进行二值化。为提取目标图形的边界描述,首先通过边缘检测获取二值图像的边界曲线,然后在曲线上进行采样。为了后继处理中能够使用FFT提高算法速度,采样点数目N取2的整数次幂。设曲线长度为L,在对轮廓曲线进行采样时,首先在曲线上任取一点,每隔[L/N]个点采样一次(“[]”表示取整数),形成用于描述形状轮廓的有序采样点列表。

图像的质心距离定义为边界轮廓上的像素点到图像质心像素之间的距离。设区域形状图像I={f(x,y); 0≤x<M, 0≤y<N},区域形状I大小为M×N,其质心坐标(xc,yc)定义为:

$x{}_c=\frac{1}{A}{\displaystyle \sum _{x=0}^{{\rm M}-1}{\displaystyle \sum _{y=0}^{{\rm N}-1}x}}f(x,y)(1)$

$y{}_c=\frac{1}{A}{\displaystyle \sum _{x=0}^{{\rm M}-1}{\displaystyle \sum _{y=0}^{{\rm N}-1}y}}f(x,y)(2)$

其中A是区域面积,定义为:

$A={\displaystyle \sum _{x=0}^{{\rm M}-1}{\displaystyle \sum _{y=0}^{{\rm N}-1}f}}(x,y)(3)$

则质心距离定义为:

$r=\sqrt{(x-x{}_c){}^2+(y-y{}_c){}^2}(4)$

获得质心及质心距离后,对所有采样点进行跟踪获取邻点。对某个采样点a分别顺时针和逆时针沿着图像边界跟踪距离S(S是该采样点处质心距离的1/2)获得邻点b和c(如图1所示)。获得邻点后可以获取a到bc连线的垂直距离作为拱高的值。拱高的符号由采样点a相对bc连线的位置确定,将bc看作从b指向c的有向线段,若a在bc的右边,拱高的符号定义为正, 反之定义为负[3]。 拱高的符号可以反映图形边界的凸凹情况,如图1(a) 拱高符号为正,对应点的边界是凸的,而图1(b)符号为负,对应边界是凹的。显然,线段bc的长度也可以反映凸凹的程度。这样对于N个采样点,每个点获得相邻点距离,拱高以及质心距离3个参数,用于表示该点处的形状信息。

为了进一步分析上述3个参数对形状的描述能力,图2给出了两幅图形的拱高,相邻点距离,以及质心距离3个参数的函数曲线。其中图(a)和图(e)是苹果形状的边界,图(b)和(f)是拱高函数曲线,图(c)和(g)是相邻点距离曲线,图(d)和(h)是质心距离曲线。由于图(a)与(e)仅在一些细节上存在差异,因此边界采样点到质心之间的距离曲线的形状相似,因而质心距离可以用于描述形状之间的相似性。而由图可以发现,拱高与相邻点距离的函数曲线存在差异,这恰恰表明了这两个函数能够反映形状的细节特征。

在数理统计中,均值反映一组数据平均水平和集中趋势,极差反映数据的变化范围,方差反映数据偏离均值的情况,方差越大,数据波动越大,因此分别求取3个函数的均值、方差和极差3个统计量作为形状特征的子特征。

为了获取更多的形状信息,算法通过傅立叶变换将图像从空域转换到频域,在频域中提取图像的形状内容。具体方法是:将描述形状相似性信息的质心距离作为实部,将描述形状细节内容的拱高作为虚部,构成拱高半径复函数[3]。对复函数进行离散傅立叶变换,获得低频傅立叶系数作为傅立叶描述子,形成算子的第2个子特征。

1.2 区域特征

上述两个子特征都是针对图像轮廓提取的,因此存在轮廓特征的一些固有缺点,比如易受噪声干扰,以及过于依赖边缘检测的结果。为了增强算法的鲁棒性,考虑增加一个区域形状子特征。

形状矩阵是一种有效的描述图像区域内容的工具,它实质是对图像区域的重新采样,用一个矩阵来描述图像的形状内容。获取一幅图像的形状矩阵的具体操作过程是:以图像质心为圆心,以最大质心距离为半径形成目标区域的最小外接圆。将圆半径等距离划分成P份,形成P个同心圆,极轴从(0～360)°逆时针旋转,记录极角为360/Q的K倍(K为0～Q-1之间的整数)时极轴与同心圆交点处的像素信息,形成一个记录图像形状信息的、大小为P×Q的形状矩阵。矩阵的行对应同心圆,列对应半径。由于极坐标极点位于区域质心,且是对最大质心距离进行等距离划分,所以形状矩阵满足对图像的平移和缩放不变性[9]。

图3给出了不同图像及它们对应的形状矩阵的图像。其中(a)和(c)是仅在细节上存在差异的苹果形状,如苹果梗处的叶子不同,另外(c)图形出现残缺,这两个形状相似,由图可以发现其对应的形状矩阵的图形(b)和(d)在形状上也相似。而图3(e)和前两个苹果图形在形状上存在较大差异,其形状矩阵图形(f)也与(b)和(d)存在较大差异。由此可见,形状矩阵可以描述图形的区域形状信息,通过提取图像的形状矩阵,可以减少参与后继计算的数据量。如原图尺寸256×256,对图像重采样获得的形状矩阵的大小是50×50,则形状矩阵的数据量是原图数据量的0.04。

由于图像的能量主要集中在低频部分,而高频部分的分量很弱,仅仅揭示了图像的某些细节。通过离散傅立叶变换,将形状矩阵由空间域转换到频域,可以获得表示图像形状信息的低频傅立叶系数作为形状描述子。

1.3 特征融合

在进行特征融合时,不同子特征的特征向量的取值范围可能存在很大差异,为了使子特征在特征相似性比较中具有公平的贡献,在进行特征组合前,需要对子特征进行归一化,公式为

fi′=(fi-fmin)/(fmax-fmin) ;1≤i≤D (5)

式(5)中fi是第i个特征量,fi′是归一化后的特征量,fmin与fmax分别是子特征向量中最小和最大的值,D是特征维数,经过公式(5)处理后,特征向量的取值范围在0～1之间的概率达到100%。

1.4 形状特征提取流程

检索算法的基本思想是:首先对图像库中的所有图像提取形状特征,形成特征库,在检索时,将待检索图像的特征与特征库中的其余特征进行比较,并按相似性大小返回检索结果。对形状特征提取的步骤总结如下:

(1)对图像进行边缘检测,并等间隔采样N个点;

(2)求取图像的质心(xc,yc),以及采样点到质心的距离r;

(3)对采样点在顺时针和逆时针两个方向跟踪距离r/2,在边界上获得两个邻点,计算拱高函数,以及两邻点间的距离;

(4)对采样点处的质心距离、拱高函数以及邻点距离进行统计,获取3个函数的统计量作为第1个子特征;

(5)以质心距离为实部,拱高为虚部构成复函数,在频域中提取表示形状内容的子特征作为第2个子特征;

(6)对图像区域进行重新采样,获得形状矩阵,并提取关于形状矩阵的傅里叶描述子,作为第3个子特征;

(7)对3个子特征分别进行归一化,组合成混合形状描述子。

2 实验结果和讨论

2.1 图形库

MPEG—7多媒体内容描述接口(Multimedia Content Description Interface),目标是为了产生一种通用的多媒体数据内容描述接口,以满足各种多媒体信息系统对多媒体数据的管理和检索的需求。MPEG—7图形库(set B)包含1 400幅图形,70大类,每类图形包含20幅在形状上存在差异的图片,它是用于形状特征描述算子的标准验证库,主要用于进行图像相似性检索实验,测试形状描述子对任意形状畸变的鲁棒性。

2.2 相似性比较

在进行检索时,需要进行特征之间的相似性比较。若图像A与B的第i个子特征fiA与fiB之间的距离表示为D(fiA,fiB),则本文利用3个子特征进行相似性比较时引入权值,采用式(6)的方式进行:

D(A,B)=w1D(f1A,f1B)+w2D(f2A,f2B)+w3D(f3A,f3B) (6)

式(6)中,w1、w2和w3依次是子特征1、2、3的权值,并且w1+w2+w3=1,权值w1、w2、w3的具体取值可以通过实验确定。

2.3 实验过程

信息检索中衡量一个算法性能的指标通常是查全率和查准率。其中,查全率表示从图像库中成功检索出相似图像的能力;查准率表示检索返回的图像中相似图像所占的比例。查全率和查准率之间具有互逆的关系,一般查全率较高时查准率较低,而当查准率较高时查全率又较低。为了客观反映检索的性能,可以将查全率与查准率绘制在一个图形中,即PVR指数曲线。

在测试形状描述子检索性能的实验中,对图形库中的每一幅图片都进行检索匹配。具体过程是:将图形库中的某一幅作为待查询图形,在剩余的图形中检索同类图形,总共需要进行1400次匹配。其中每次检索都记录查全率分别为10%、20%、30%……100%时对应的查准率,最终绘制PVR指数曲线。

2.4 检索结果

图4是4种不同算法的检索结果示例,第一列是待检索图像,每个算法返回最相似的9幅图像。其中第一行是现算法的检索结果,第二行是拱高半径复函数的结果,第三、四、五行分别是三角形函数、质心距离傅立叶描述子和Hu不变矩算法的检索结果。从图中可以看出,该算法在针对这一形状时的检索结果明显优于其它3种算法。

为了能够客观地测试算法的性能,将其与另外4种算法在Mpeg—7图形库上进行了对比实验,其中Hu不变矩是一种经典的区域形状描述法,其余参与比较的3种算法是轮廓描述法。具体结果如图5所示,其中横轴表示查全率,纵轴表示准确率,每种算法计算所有图像在10种查全率取值时的平均准确率,绘制图5所示的曲线。可以看出5种算法中三角形面积函数的检索性能相对最差,Hu不变矩其次,拱高半径复函数的检索平均准确率较前两者分别高出9%和6%。而现算法又比拱高半径复函数算法的平均准确率高出近16%。实验数据显示,该算法的检索性能显著优于参与比较的其余4种算法。

BEP(Bull’s Eye Percentage)性能指标[10]也是对检索性能进行评价的标准,它定义为检索返回的前40幅图像中相似图像所占的比例。假设每次检索实际匹配数为ni,则总的实际匹配数为${\displaystyle \sum _{i=1}^{S}n}{}_i$,其中S为图像库中图像的总数。每类图形的数目为M,则总的理想正确匹配数为SM。对于MPEG—7 Set B图像库,S=1 400,M=20。则BEP定义为实际的正确匹配数与理想正确匹配数的比例,即:

$BE{\rm P}=\frac{{\displaystyle \sum _{i=1}^{1400}n}{}_i}{1400\times 20}(7)$

表1给出了本文算法与其它4种形状特征的BEP检索性能,从数据可以看出该算法的BEP性能要远远高于参与比较的其余算子。这与PVR指数曲线显示的结果是一致的。

3 结论

现有的形状特征一般分为基于轮廓和区域两类方法。为克服轮廓描述法易受噪声等因素干扰的缺点,将两种描述法结合,提出一种融合轮廓和区域信息的新的形状描述算法。 该算法将包含形状信息的轮廓采样点的相邻点之间的距离函数,以及采样点的拱高函数和质心距离函数进行数理统计,并获取由拱高和质心距离组成的函数在频域中的低频系数,构成轮廓形状特征。再对图形区域进行采样获得形状矩阵,同样获得表示区域形状信息的傅里叶变换的系数。最后对两种形状特征进行组合,构成形状描述子。在对MPEG—7图形库的检索结果显示,该算法具有较高的检索准确率。今后将结合其它特征及相关反馈技术来获取更好的检索性能。

参考文献

[1] Zhang D S,Lu G J.Study and evaluation of different Fourier methodsfor image retrieval.Image and Vision Computing,2005;23(1):33—49

[2] Alajlan N,Kamel M S,Freeman G.Multi-object image retrieval baseon shape and topology.Signal Processing:Image Communication,2006;21:904—918

[3]王斌.一种用于形状描述的拱高半径复函数.电子学报,2011;39(4):831—836

[4] Mokhtarian F,Ung Y K,Wang Z T.Automatic fitting of digitisedcontours at multiple scales through the curvature scale space tech-nique.Computers&Graphics,2005;29(6):961—971

[5] Kunttu I,Lepisto L.Shape-based retrieval of industrial surfacedefectsusing angular radius Fourier descroptor.IET Image Processing,2007;1(2):231—236

[6] Yaday R B,Nishchal N K,Gupta A K.Retrieval and classificationof shape-based objects using Fourier,generic Fourier,and wavelet-Fourier descriptors technique:a comparative study.Optics and lasersin Engineering,2007;45(6):695—708

[7] Hu M K.Visual pattern recognition by moment invariants.IRE Trans-actions on Information Theory,1962;11(2):179—187

[8] Datta R,Toshi D,Li jia.Image retrieval ideas influences and trendsof the new age.ACM Computiong Surveys,2008;40(2):1—60

[9] Goshtasb A.Description and discrimination of planar shape usingshape matrices.IEEE Trans Pattern Anal Mach Intell,1985;7(6):738—743

局部描述子 篇3

关键词：SQP方法,信赖域,滤子,二阶校正,Maratos效应,局部收敛

最近十年来,解决含约束的非线性规划问题的方法有很大发展,具有代表性的方法有Byrd,Nocedal[1]的信赖域内点法、无二次子规划法[2,3],和Fletcher和Leyffer[4]的信赖域滤子方法等。所谓的滤子方法就是用一组被接受的滤子对来代替传统的价值函数的方法,这样就避免了罚因子的选取,而选取适当的罚因子有时是困难的。滤子方法不同于其他方法的关键是,一个迭代点(通过解信赖域二次规划(QP)子问题得到)被接受,当且仅当目标函数值,或者约束违反度函数值有充分的下降。滤子方法的算例计算结果表明,此法解决含约束的非线性规划问题是非常有效的。信赖域SQP滤子方法的全局收敛性也得到了证明[5,6]。除了在信赖域SQP方法中用了滤子技术,在其他许多方法中滤子技术也得到应用,例如线搜索SQP方法[7,8];内点法[9,10,11,12];捆集法[13]和模式搜索算法[14]。

本文讨论信赖域SQP滤子方法的局部超收敛性。 Fletcher和Leyffer[4,20]所提到的,滤子方法也会遇到Maratos效应[15,19]。尽管完全牛顿步可能是一个超线性收敛收敛步,但是当迭代点充分靠近原问题的严格局部解时,完全牛顿步可能会使目标函数值和约束违反度都上升,从而不被滤子接受,于是就影响了算法的收敛速度。本文对文献[5]中的信赖域SQP滤子方法进行了修改,提出了当全牛顿步不被滤子接受时,通过增加二阶校正步(SOC)来避免Maratos效应,使得它容易被滤子接受。本文给出具有二阶校正步的新算法,证明了此新算法具有局部超线性收敛性,算例计算结果表明具有二阶校正步的新算法确实可以减少迭代次数。

首先给出本文中一些符号的说明。记列向量v∈Rn的第个i元素为v(i)。记vk=O(dk)为满足$\left|v{}_k\right|\le \beta d{}_k$的序列$\left\{v{}_k\right\}$,这里β>0是个常数。记vk=o(dk)是满足$\left|v{}_k\right|\le \beta {}_{k}d{}_k$的序列$\left\{v{}_k\right\}$,这里$\left\{\beta {}_k\right\}$是个正数列,且$\underset{k\to \infty }{{\displaystyle \lim }}\beta {}_k=0$。

1 信赖域SQP滤子方法

考虑非线性优化问题(NP):

$\min f(x)\text{s}.\text{t}.c(x)=0$ (1)

(1)式中目标函数f:Rn→R和等式约束c:Rn→Rm(m<n)是二次连续可微的。

在当前迭代点xk,原问题(NP)的信赖域QP子问题TRQP(xk,Δk)为

$\begin{array}{l}\min m{}_k(d)=f{}_k+g{}_k^{\text{Τ}}d+\frac{1}{2}d{}^{\text{Τ}}{\rm H}{}_{k}d\\ \text{s}.\text{t}.c(x{}_k)+A(x{}_k)d=0\\ \parallel d\parallel \le \Delta {}_k(2)\end{array}$

(2)式中fk=f(xk),gk=g(xk)=ᐁxf(xk),A(xk)是等式约束函数c(x)在xk点的雅克比阵 (Jacobian),Hk是个对称阵。

为求解TRQP(xk,Δk)的近似解dk,把完全步dk分成两部分dk=nk+tk,其中nk称为法向步,tk称为切向步。法向步nk要求满足问题TRQP(xk,Δk)的约束条件,即

c(xk)+A(xk)nk=0 (3)

而完全步dk要求满足问题TRQP(xk,Δk)的约束,同时使目标函数值有所下降,即

$c(x{}_k)+A(x{}_k)d{}_k=0,\left|d{}_k\right|\le \Delta {}_k$ (4)

若方程(3)不相容,则法向步nk可由下列问题求出近似解

(5)式中$\xi \in \left(0,1\right)$。而完全步dk=nk+tk可由下列问题求出近似解

上述完全步的近似求解问题(6)一定有可行解,如d=nk 就是一个可行解。

滤子方法是由Fletcher和Leyffer[4]最先提出来的。基本思想是多目标优化,使得min f(x)和min h(x)同时满足,这里约束违反度h(x):$=\parallel c(x)\parallel {}_1$。

若nk满足(3)式且满足

‖nk‖≤κΔΔkmin[1,κμΔ${}_k^{\mu }$] (7)

或nk是问题(5)的解,且满足(7)式,则称问题TRQP(xk,Δk)为相容的。其中κΔ∈(0,1],κμ>0,μ∈(0,1)。

引入一个尺度

χk=$\underset{\parallel t\parallel \le 1}{{\displaystyle \underset{c(x{}_k)+A(x{}_k)(n{}_k+t{}_{})=0}{{\displaystyle \underset{A(x{}_k)t=0}{{\displaystyle \min }}}}}}\left(g{}_k+{\rm H}{}_{k}n{}_k\right){}^{\text{Τ}}t$ (8)

当TRQP(xk,Δk)相容时,且tk满足

$m{}_k(x{}_k+n{}_k)-m{}_k(x{}_k+n{}_k+t{}_k)\ge \kappa {}_{tmd}\chi {}_k\min \left[\frac{\chi {}_k}{\beta {}_k},\Delta {}_k\right]‚(9)$

则能确保tk使mk达到充分下降[16]。其中κtmd>0 是个常数,$\beta {}_k=1+\parallel {\rm H}{}_k\parallel$。

记函数

L(x,λ)=f(x)+c(x)Tλ (10)

则称其为(NP)问题(1)的Lagrange函数。称λ是相应的Lagrange乘子。

(NP)问题(1)的Karush-Kuhn-Tucker(KKT)条件为

g(x)+AT(x)λ=0, c(x)=0 (11)

记向量,则由牛顿迭代公式

其中$\Phi \left(x,\lambda \right)$为$\phi \left(x,\lambda \right)$的雅克比阵 (Jacobian)。上式可恒等变形为

$\left(\begin{array}{cc}{\rm H}{}_k& A{}_{{\rm K}}^{{\rm T}}\\ A{}_k& 0\end{array}\right)\left(\begin{array}{c}d{}_k\\ \lambda {}_k^{+}\end{array}\right)=-\left(\begin{array}{c}\nabla f{}_k\\ c{}_k\end{array}\right)(12)$

(12)式中Ak:=A(xk),gk:=g(xk),;Ck:=C(xk);Hk是Lagrange函数L(x,λ)的Hessain阵,λ+k=λk+δλk。(12)式中的λ+k可以作为λk+1的近似值,在近似求解牛顿迭代步dk时,(12)式中的Hk可由Hessain阵的近似阵代替[21]。

在当前迭代点xk得到试探点xk+dk,如果满足

h(xk+dk)≤(1-γh)h(xk) 或 f(xk+dk)≤f(xk)-γfh(xk) (13)

常数γh、γf∈(0,1),则试探点xk+dk被点xk接受。但是,为了使目标函数值达到充分下降,将(13)式用下面的条件替换

mk(0)-mk(xk)≥0 或 [mk(0)-mk(xk)]θΔ${}_k^{1-\theta }$≥κhh${}_k^{\tau }$ (14)

(14)式中$\kappa {}_h\in \left(0,1\right),\tau \in (0,1)$,θ>2τ。

在第3节我们将证明满足(14)式的迭代是成功的。若假设近似Hessain阵Hk到约束函数$c\left(x{}_k\right)$的雅克比阵A${}_k^{}$零空间上的投影是一致正定的,则当迭代点可行,但并非最优时,(14)式是可以成立的。

记一组滤子,

2 二阶校正步(SOC)与算法

Fletcher和Leyffer[4]提出,滤子方法和罚函数方法一样,也会遇到Maratos效应。当迭代点x${}_k^{}$充分靠近局部最优解x*时,完全步d${}_k^{}$会使得目标函数值和约束违反度同时增大,这样完全步就不被接受,影响了算法的收敛速度。我们可用二阶校正的方法来避免这种情况的发生。

二阶校正的思想是,在试探点xk+dk加上一个二阶校正步d${}_k^{soc}$来改善试探点的不可行性。计算d${}_k^{soc}$的方法有很多种,有一种类似于求解牛顿步d${}_k^{}$的线性系统(12)式的方法,即d${}_k^{soc}$可有下面的线性系统

$\left(\begin{array}{cc}{\rm H}{}_k^{soc}& (A{}_k^{soc}){}^{\text{Τ}}\\ A{}_k^{soc}& 0\end{array}\right)\left(\begin{array}{c}d{}_k^{soc}\\ \lambda {}_k^{soc}\end{array}\right)=-\left(\begin{array}{c}g{}_k^{soc}\\ c(x{}_k+d{}_k)+c{}_k^{soc}\end{array}\right)(17)$

求得,其中H${}_k^{soc}$是n×n阶对称矩阵,A${}_k^{soc}$∈Rm×n,g${}_k^{soc}$∈Rn,c${}_k^{soc}$∈Rm。通过求解线性系统(17)式得二阶校正步d${}_k^{soc}$的方法是由Conn,Could和Toint[13]提出的。

d${}_k^{soc}$的求解线性系统(17)式中,H${}_k^{soc}$,g${}_k^{soc}$,c${}_k^{soc}$,A${}_k^{soc}$一般有以下几种可能的选择:

(SOC1). H${}_k^{soc}$=I,g${}_k^{soc}$=0,c${}_k^{soc}$=0,A${}_k^{soc}$=Ak,或A${}_k^{soc}$=A(xk+dk);这种选择与约束的最小二乘步一致。

(SOC2). H${}_k^{soc}$=Hk,g${}_k^{soc}$=0,c${}_k^{soc}$=0,A${}_k^{soc}$=Ak;这种选择的计算量比较小。

(SOC3). H${}_k^{soc}$是Lagrangian函数L(x,λ)的Hessian阵在点的xk+dk近似值,

g${}_k^{soc}$=g(xk+dk)+AT(xk+dk)λ+k,c${}_k^{soc}$=0,A${}_k^{soc}$=A(xk+dk);这种选择是在假设xk+dk被xk接受的基础上进行的,所以这种方法适用于Watchdog方法。

(SOC4). 如果d${}_k^{soc}$是dk的二阶校正步,$\tilde{d}$${}_k^{soc}$是dk+d${}_k^{soc}$的二阶校正步,那么$d{}_k^{soc}+\tilde{d}{}_k^{soc}$可以看作是dk的二阶校正步(这种情况下有c${}_k^{soc}$≠0)。类似地,几个连续的二阶校正步也可以被当作一个二阶校正步来看。

算法

①初始化。

给出初始点x0,初始信赖域半径Δ0>0,初始对称矩阵H0,hmax∈(h(x0),+∞),0<r0<r1≤1≤r2,0<η1≤η2<1,γh、γf∈(0,1),κh∈(0,1),κΔ∈(0,1],κμ>0,μ∈(0,1),$\tau >\frac{1}{1+\mu }$,κtmd∈(0,1)。初始化滤子F0:={(h,f)∈R2:h≥hmax},k=0。

②最优化检验。

如果hk=χk=0,停止。

③计算nk。

如果TRQP(xk,Δk)相容,转步④。否则,把xk加入到滤子中去,转入可行性恢复阶段计算得一试探步rk,使得TRQP(xk+rk,Δk+1)相容,而且不被滤子接受。如果这样的rk不存在,停止。否则,令xk+1=xk+rk,转入步⑧。

④计算试探步。

计算tk,令dk=nk+tk。

⑤测试试探步是否被算法接受。

[5.1]如果xk+dk被滤子接受,即(h(xk+dk),f(xk+dk))∈Fk,转[5.2]。

否则,Ⅰ.CaseI:设(14)式成立,若ρk:$=\frac{f(x{}_k)-f(x{}_k+d{}_k)}{m{}_k(0)-m{}_k(d{}_k)}\ge \eta {}_2$,转步⑦;否则,转[5.2]

Ⅱ.CaseII:设(14)式不成立,若(13)式成立,转步⑦;否则,转[5.2]。

[5.2]计算SOC 步。解线性系统(17)式得SOC步d${}_k^{soc}$,令

$\overline{x}{}_{k+1}=x{}_k+d{}_k+d{}_k^{soc}$。

[5.3]、检验$\overline{x}$k+1是否被滤子接受。若(h($\overline{x}$k+1),f($\overline{x}$k+1))∈Fk,拒绝d${}_k^{soc}$,转[5.5]。

[ 5.4]检验在当前迭代点是否有充分下降

Ⅰ.CaseI:设替换条件(14)式成立,若ρ${}_k^{soc}$:$=\frac{f(x{}_k)-f(x{}_k+d{}_k+d{}_k^{soc})}{m{}_k(0)-m{}_k(d{}_k+d{}_k^{soc})}\ge \eta {}_2$,令$x{}_{k+1}=\overline{x}{}_{k+1}$,转步⑦;否则,转[5.5]。

Ⅱ.CaseII:设替换条件(14)式不成立,如果

$\begin{array}{l}h(\overline{x}{}_{k+1})\le (1-\gamma {}_h)h(x{}_{k+1})\text{或}f(\overline{x}{}_{k+1})\le \\ f(x{}_k)-\gamma {}_{f}h(x{}_k)(18)\end{array}$

成立,令$x{}_{k+1}=\overline{x}{}_{k+1}$转步⑦;否则,转[5.5]。

[ 5.5]令xk+1=xk,k←k+1,转步②。

⑥更新滤子:xk+1∈[r0Δk,r1Δk]。

若替换条件(14)不成立,用(16)式的方法更新滤子;否则,滤子不变,即Fk+1:=Fk。

⑦增大信赖域半径,Δk+1=[Δk,r2Δk]。

⑧定出Hk+1,k←k+1,转步②。

3 局部收敛性

本节将给出经过二阶校正后的信赖域SQP滤子算法的局部收敛性证明。在给出证明以前,先给出如下假设:

假设L 假设算法产生的无穷点列{xk}收敛于问题(1)的局部解{x*},而且以下几条成立。

(L1)目标函数f(x)和约束函数c(x)在x*的某个邻域内是二次连续可微的。

(L2){x*}满足二阶充分最优条件:

·存在λ*∈Rm使得在(x*,λ*)满足KKT条件。

·约束函数的雅克比阵A(x*)T是满秩的。

·Lagrangain函数的Hessain阵W*=ᐁ${}_{xx}^2$L(x*, λ*)在A(x*)的零空间上是正定的。

(L3)在(11)式中,Hk在A(x*)的零空间上是一致正定有界的。

(L4)在(17)式中,H${}_k^{soc}$在A(x*)的零空间上是一致正定的,且满足

$g{}_k^{soc}=o(\left|d{}_k\right|)$,$A{}_k-A{}_k^{soc}={\rm O}(\left|d{}_k\right|)$,$c{}_k^{soc}=o(\left|d{}_k\right|){}^2$, (19)

(L5)(11)式中的矩阵Hk满足

$(W{}_k-{\rm H}{}_k)d{}_k=o(\left|d{}_k\right|)(20)$

首先证明几个引理,

引理1 假设L成立,则存在x*的某个邻域U1,使得对任意xk∈U1,有

$\begin{array}{l}d{}_k^{soc}=o(\left|d{}_k\right|)(21)\\ c(x{}_k+d{}_k+d{}_k^{soc})=o(\left|d{}_k\right|{}^2)(22)\end{array}$

证明:由假设L,知线性系统(17)式中的系数矩阵在x*的某个邻域内为一致有界的可逆阵。又因为(17)式等号右式是$o(\left|d{}_k\right|)$,所以(21)式成立。由(17)式,(19)式和(21)式知

$\begin{array}{l}c(x{}_k+d{}_k+d{}_k^{soc})\\ =c(x{}_k+d{}_k)+A(x{}_k+d{}_k){}^{\text{Τ}}d{}_k^{soc}+{\rm O}(\left|d{}_k\right|{}^2)=\\ -c{}_k^{soc}-(A{}_k^{soc}){}^{\text{Τ}}d{}_k^{soc}+(A{}_k+{\rm O}(\left|d{}_k\right|)){}^{\text{Τ}}d{}_k^{soc}+\\ {\rm O}(\left|d{}_k^{soc}\right|{}^2)=o(\left|d{}_k\right|{}^2)+{\rm O}(\left|d{}_k\right|\left|d{}_k^{soc}\right|)+\\ {\rm O}(\left|d{}_k^{soc}\right|{}^2)=o(\left|d{}_k\right|{}^2)。\end{array}$

定理得证。

为了证明局部超线性收敛,我们引用文献[17]两个中的结果。先给出两个函数,一个是精确罚函数

$\phi {}_{\sigma }(x)=f(x)+\sigma h(x)(23)$

另一个是下面形式的罚函数

$q{}_{\sigma }(x{}_k,d)=f(x{}_k)+g{}_k^{{\rm T}}d+\frac{1}{2}d{}^{{\rm T}}{\rm H}{}_{k}d+\sigma \left|A{}_k^{}d+c{}_k\right|(24)$

这两个罚函数只用于理论证明,实际算法中并不用到。

由文献[17]中的定理15.3.7可得下面的引理2。

引理2 假设L成立。φσ,qσ分别由(23)式,(24)式定义,且$\sigma >\left|\lambda {}_{*}\right|{}_D$。则

$\underset{k\to \infty }{{\displaystyle \lim }}\frac{\phi {}_{\sigma }(x{}_k)-\phi {}_{\sigma }(x{}_k+d{}_k+d{}_k^{soc})}{q{}_{\sigma }(x{}_k,0)-q{}_{\sigma }(x{}_k,d{}_k)}=1$。

由文献[17]中的定理15.3.2可得下面的引理3。

引理3 假设L成立。设(dk,λ+k)是(11)式的解,且$\sigma >\left|\lambda {}_k^{+}\right|{}_D$,则

$q{}_{\sigma }(x{}_k,0)-q{}_{\sigma }(x{}_k,d{}_k)\ge 0(25)$

下面的引理4证明了,在x*某个邻域内,如果dk+d${}_k^{soc}$是个f-型迭代步,则算法中步[5.4]的CaseI是成功的。

引理4 假设L成立,且存在x*的某个邻域U2(⊆U1),使得(14)式成立,则有ρk≥η2。

证明:设U1是引理1中提到的x*的邻域,对任意xk∈U2,因为满足(14)式,所以

因为$\eta {}_f<\frac{1}{2}$,由引理2和(25)式得,存在一个自然数K,对任意的k≥K和正常数$\sigma >\left|\lambda {}_k^{+}\right|{}_D$,有

φσ(xk)-φσ(xk+dk+d${}_k^{soc}$)≤(1+ηf)[qσ(xk,0)-qσ(xk,dk)] (27)

于是有

$\begin{array}{l}f(x{}_k)-f(x{}_k+d{}_k+d{}_k^{soc})=\\ \phi {}_{\sigma }(x{}_k)-\phi {}_{\sigma }(x{}_k+d{}_k+d{}_k^{soc})-\sigma [h(x{}_k)-\\ h(x{}_k+d{}_k+d{}_k^{soc})]\le (1+\eta {}_f)[q{}_{\sigma }(x{}_k,0)-\\ q{}_{\sigma }(x{}_k,d{}_k)]+o(\left|d{}_k\right|{}^2)=-(1+\eta {}_f)\\ (g{}_k^{\text{Τ}}d{}_k+d{}_k^{\text{Τ}}{\rm H}{}_{k}d{}_k)+o(\left|d{}_k\right|{}^2)(28)\end{array}$

根据文献[6],迭代步可以做以下分解,

$\begin{array}{l}d{}_k=q{}_k+p{}_k,q{}_k:=Y{}_k\overline{q}{}_k‚p{}_k:={\rm Z}{}_k\overline{p}{}_k,\\ \overline{q}{}_k:=-[A{}_k^{\text{Τ}}Y{}_k]{}^{-1}c{}_k,\\ \overline{p}{}_k:=-[{\rm Z}{}_k^{{\rm T}}{\rm H}{}_k{\rm Z}{}_k]{}^{-1}{\rm Z}{}_k^{{\rm T}}(g{}_k+{\rm H}{}_{k}q{}_k)(29)\end{array}$

(29)式中Yk∈Rn×m和Zk∈Rn×(n-m)组成的矩阵(YkZk)是Rn上的正交阵,Zk的列向量是ATk的零空间的基向量。假设L保证了(29)式的成立,而且λ+k是有界的,所以

$\begin{array}{l}m{}_k(0)-m{}_k(d{}_k+d{}_k^{soc})-\eta {}_2(f(x{}_k)-f(x{}_k+d{}_k+\\ d{}_k^{soc}))=-g{}_k^{\text{Τ}}(d{}_k+d{}_k^{soc})+(d{}_k+d{}_k^{soc}){}^{\text{Τ}}{\rm H}{}_k(d{}_k+\\ d{}_k^{soc})-\eta {}_2(f(x{}_k)-f(x{}_k+d{}_k+d{}_k^{soc}))\ge -\\ g{}_k^{{\rm T}}(d{}_k+d{}_k^{soc})+(d{}_k+d{}_k^{soc}){}^{{\rm T}}{\rm H}{}_k(d{}_k+d{}_k^{soc})+\\ \eta {}_2(1+\eta {}_f)[g{}_k^{{\rm T}}d{}_k+d{}_k^{{\rm T}}{\rm H}{}_{k}d{}_k]+o(\left|d{}_k\right|{}^2)\\ =2\overline{p}{}_k^{\text{Τ}}{\rm Z}{}_k^{\text{Τ}}{\rm H}{}_k{\rm Z}{}_k\overline{p}{}_k+{\rm O}(\left|q{}_k\right|)+o(\left|d{}_k\right|{}^2)(30)\end{array}$

由(YkZk)的正交性,有

$\begin{array}{l}q{}_k={\rm O}(\overline{q}{}_k)={\rm O}(h(x{}_k))=o(\left|d{}_k\right|{}^2)=\\ o(p{}_k^{\text{Τ}}p{}_k+q{}_k^{\text{Τ}}q{}_k)=o(\left|\overline{p}{}_k\right|{}^2)+o(\left|q{}_k\right|{}^2)。\end{array}$

因此,有$q{}_k=o(\left|\overline{p}{}_k\right|{}^2)$,且

$\begin{array}{l}d{}_k={\rm O}(\left|q{}_k\right|)+{\rm O}(\left|p{}_k\right|)=o(\left|\overline{p}{}_k\right|{}^2)+\\ {\rm O}(\left|\overline{p}{}_k\right|)={\rm O}(\left|\overline{p}{}_k\right|)\end{array}$

因为xk→x*时,$\overline{p}{}_k\to 0$,所以由(30)式得到ρk→η2。 证毕。

引理5 假设L成立。则存在x*的某个邻域U3(⊆U2)(U2是引理4中所指的邻域)和满足下面关系的常数σ1,σ2,σ3>0。

$\begin{array}{l}\sigma {}_3=(1-\gamma {}_h)\sigma {}_2-\gamma {}_f(31)\\ 2\gamma {}_h\sigma {}_2<(1+\gamma {}_h)(\sigma {}_2-\sigma {}_1)-2\gamma {}_f(32)\\ 2\sigma {}_3\ge (1+\gamma {}_h)\sigma {}_1+(1-\gamma {}_h)\sigma {}_2(33)\end{array}$

使得对任意xk∈U3,有$\left|\lambda {}_k^{+}\right|{}_D<\sigma {}_i‚i=1,2,3$。而且,对任意xk∈U3,有

$\begin{array}{l}\phi {}_{\sigma {}_i}(x{}_k)-\phi {}_{\sigma {}_i}(x{}_k+d{}_k+\tilde{d}{}_k^{soc})\ge \frac{1+\gamma {}_h}{2}\\ (q{}_{\sigma {}_i}(x{}_k,0)-q{}_{\sigma {}_i}(x{}_k,d{}_k))\ge 0(34)\end{array}$

i=2,3,其中$\tilde{d}$${}_k^{soc}$有以下几种可能的形式

$\begin{array}{l}\tilde{d}{}_k^{soc}=d{}_k^{soc},\\ \tilde{d}{}_k^{soc}=\delta {}_{k}d{}_k^{soc}+d{}_{k+1}+\delta {}_{k+1}d{}_{k+1}^{soc},\\ \tilde{d}{}_k^{soc}=\delta {}_{k}d{}_k^{soc}+d{}_{k+1}+\delta {}_{k+1}d{}_{k+1}^{soc}+d{}_{k+2}+\delta {}_{k+2}d{}_{k+2}^{soc},\\ \tilde{d}{}_k^{soc}=\delta {}_{k}d{}_k^{soc}+d{}_{k+1}+\delta {}_{k+1}d{}_{k+1}^{soc}+d{}_{k+2}+\delta {}_{k+2}d{}_{k+2}^{soc}+\\ d{}_{k+3}+\delta {}_{k+3}d{}_{k+3}^{soc}(35)\end{array}$

这里$\delta {}_{k,}\delta {}_{k+1,}\delta {}_{k+2}\in \left\{0,1\right\}$。

证明 因为对任意xk∈U2,其对应的λ+k是一致有界的,所以存在$\sigma {}_1>\left|\lambda {}_{*}\right|{}_D$,对任意xk∈U2有

$\sigma {}_1>\parallel \lambda {}_k^{+}\parallel {}_D(36)$

定义

$\sigma {}_2:=\frac{1+\gamma {}_h}{1-\gamma {}_h}\sigma {}_1+\frac{3\gamma {}_f}{1-\gamma {}_h}。$

由(31)式,容易验证$\sigma {}_2,\sigma {}_3\ge \sigma {}_1>\left|\lambda {}_k^{+}\right|{}_D$且(32)式,(33)式成立。因为(1+γh)<2,由引理2知存在x*的一个邻域U3(⊆U2),使得对任意xk∈U3,(34)式成立。

再由本文第2节的(SOC-3)和(SOC-4)知(34)式成立。证毕。

若U2和σ3分别是引理5中所指得邻域和常数。因为$\underset{k\to \infty }{{\displaystyle \lim }}x{}_k=x{}_{*}$,可以找到一个自然数K1,使得对任意k≥K1,有xk∈U3 。定义水平集

M:={xk∈U3:φσ3(x)≤φσ3(x*)+κ}。

易知,可以选择适当的κ>0,使得对任意x∈M,(h(x), f(x))∉Fk1。

给出几个定义,

$\begin{array}{l}A:=\{k|F{}_k\subseteq F{}_{k+1}\}‚\\ G{}_k:=\{(h,f):h\ge (1-\gamma {}_{\theta })h(x{}_k),f\ge f(x{}_k)-\\ \gamma {}_{f}h(x{}_k)\},{\rm I}{}_{k{}_1}^{k{}_2}:=\{l=k{}_1,\cdots ,k{}_2-1:l\in A\}(37)\end{array}$

由(16)式和A的定义,对k1≤k2,有

$F{}_{k{}_2}=F{}_{k{}_1}{\displaystyle \underset{l\in {\rm I}{}_{k{}_1}^{k{}_2}}{\cup }}G{}_l(38)$

下面的引理6告诉我们,一旦迭代点到达水平集M,完全步总是被当前滤子接受的。

引理6 假设L成立,对l≥K1有h(xl)>0。则对x∈Rn下面的命题成立,

(a)如果$\phi {}_{\sigma {}_2}(x{}_l)-\phi {}_{\sigma {}_2}(x)\ge \frac{1+\gamma {}_h}{2}(q{}_{\sigma {}_2}(x{}_l,0)-q{}_{\sigma {}_2}(x{}_l,d{}_l))$,则(h(x),f(x))∉Gl。

(b)如果x∈M且$\phi {}_{\sigma {}_2}(x{}_{{\rm K}{}_2})-\phi {}_{\sigma {}_2}(x)\ge \frac{1+\gamma {}_h}{2}(q{}_{\sigma {}_2}(x{}_{{\rm K}{}_2},0)-q{}_{\sigma {}_2}(x{}_{{\rm K}{}_2},d{}_{{\rm K}{}_2}))$,则(h(x),f(x))∉FK2。这里K2是K1后第一个满足xK2∈M的下标.

证明 对(a):因为$\sigma {}_1>\left|\lambda {}_l^{+}\right|{}_D$,由引理3,qσ1(xl,0)-qσ1(xl,dl)≥0。所以,由定义(24)式和Aldl+cl=0,得到

$\begin{array}{l}\phi {}_{\sigma {}_2}(x{}_l)-\phi {}_{\sigma {}_2}(x)\ge \frac{1+\gamma {}_h}{2}(q{}_{\sigma {}_2}(x{}_l,0)-\\ q{}_{\sigma {}_2}(x{}_l,d{}_l))=\frac{1+\gamma {}_h}{2}(q{}_{\sigma {}_1}(x{}_l,0)-q{}_{\sigma {}_1}(x{}_l,d{}_l)+\\ (\sigma {}_2-\sigma {}_1)h(x{}_l))\ge \frac{1+\gamma {}_h}{2}(\sigma {}_2-\sigma {}_1)h(x{}_l)(39)\end{array}$

如果f(x)<f(xl)-γfh(xl),命题显然成立。否则,即f(x)≥f(xl)-γfh(xl),有

$\begin{array}{l}h(x{}_l)-h(x)\ge \frac{1+\gamma {}_h}{2\sigma {}_2}(\sigma {}_2-\sigma {}_1)h(x{}_l)+\\ \frac{1}{\sigma {}_2}(f(x)-f(x{}_l))\ge \frac{1+\gamma {}_h}{2\sigma {}_2}(\sigma {}_2-\sigma {}_1)h(x{}_l)-\\ \frac{\gamma {}_f}{\sigma {}_2}h(x{}_l)>\gamma {}_{h}h(x{}_l)(40)\end{array}$

所以,(h(x),f(x))∉Gl。

对(b):因为x∈M,所以由κ在水平集M中的选择,(h(x),f(x))∉FK2。再由(38)式,对所有的l∈I${}_{k{}_1}^{k{}_2}$,(h(x),f(x))∉Gl。取l∈I${}_{k{}_1}^{k{}_2}$,由(39)式

$\phi {}_{\sigma {}_2}(x{}_{{\rm K}{}_2})-\phi {}_{\sigma {}_2}(x)\ge \frac{1+\gamma {}_h}{2}(\sigma {}_2-\sigma {}_1)h(x{}_{{\rm K}{}_2})。$

因为x∈M,K2是K1后第一个满足xK2∈M的下标,而且l<K2,所以

$\begin{array}{l}\phi {}_{\sigma {}_3}(x{}_l)>\phi {}_{\sigma {}_3}(x{}_{{\rm K}{}_2})=\phi {}_{\sigma {}_2}(x{}_{{\rm K}{}_2})+\\ (\sigma {}_3-\sigma {}_2)h(x{}_{{\rm K}{}_2})\ge \phi {}_{\sigma {}_2}(x)+(\sigma {}_3-\frac{1+\gamma {}_h}{2}\sigma {}_1\\ -\frac{1-\gamma {}_h}{2}\sigma {}_2)h(x{}_{{\rm K}{}_2})\ge \phi {}_{\sigma {}_2}(x)。\end{array}$

如果f(x)<f(xl)-γfh(xl),命题显然成立。否则,即f(x)≥f(xl)-γfh(xl)。有

$\begin{array}{l}h(x)<\frac{1}{\sigma {}_2}(f(x{}_l)+\sigma {}_3)h(x{}_l)-f(x)\ge \\ \frac{\sigma {}_3+\gamma {}_f}{\sigma {}_2}h(x{}_l)=(1-\gamma {}_h)h(x{}_l)。\end{array}$

所以(h(x),f(x))∉FK2。定理得证。

最后证明局部收敛性定理。

定理1 假设L成立。则对充分大的k,形如xk+1=xk+dk或xk+1=xk+dk+d${}_k^{soc}$的完全步一定能被接受,并且xk超线性收敛于x*。

证明:K2是K1后第一个满足xK2∈M⊆U3的下标。下面证明对k≥K2+2,下列命题是成立的,

$(i{}_k)\phi {}_{\sigma {}_i}(x{}_l)-\phi {}_{\sigma {}_i}(x{}_k)\ge \frac{1+\gamma {}_h}{2}(q{}_{\sigma {}_i}(x{}_l,0)-q{}_{\sigma {}_i}(x{}_l,d{}_l))$,对$i\in \left\{2,3\right\},{\rm K}{}_2\le l\le k-2$。

(iik)xk∈M。

(iiik)xk=xk-1+dk-1+δk-1d${}_{k-1}^{soc}$,对δk-1∈{0,1}。

假设xK2-dK2不被接受。定义$\overline{x}{}_{{\rm K}{}_2+1}=x{}_{{\rm K}{}_2}+d{}_{{\rm K}{}_2}+d{}_{{\rm K}{}_2}^{soc}$,由(34)式中取i=3,k=K2,(35)式和xK2∈M,得$\overline{x}$K2+1∈M。由(34)式中取i=2,k=K2,(35)式和引理6(b),得(h($\overline{x}$K2+1), f($\overline{x}$K2+1))∉FK2,即xK2+1在步[5.3]不被拒绝。所以,如果替换条件(14)式成立,由引理4得ρ${}_{{\rm K}{}_2}^{soc}$≥η2;如果替换条件(14)式不成立,由(34)式中取i=2,k=K2,(35)式和引理6(a)l=K2,推出(13)式成立。所以,$\overline{x}$K2+1在步[5.4]被接受作为下一个迭代。

xK2+1=xK2+dK2+δK2d${}_{{\rm K}{}_2}^{soc}$,δK2∈{0,1}。

现在考虑第K2+1 次迭代。对δK2+1∈{0,1},由(34)式,k=K2和(35)式有

$\begin{array}{l}\phi {}_{\sigma {}_i}(x{}_{{\rm K}{}_2})-\phi {}_{\sigma {}_i}(x{}_{{\rm K}{}_2+1}+d{}_{{\rm K}{}_2+1}+\delta {}_{{\rm K}{}_2+1}d{}_{{\rm K}{}_2+1}^{soc})\ge \\ \frac{1+\gamma {}_h}{2}(q{}_{\sigma {}_i}(x{}_{{\rm K}{}_2},0)-q{}_{\sigma {}_i}(x{}_{{\rm K}{}_2},d{}_{{\rm K}{}_2}))(i=2,3)(41)\end{array}$

成立。所以

$x{}_{{\rm K}{}_2+1}+d{}_{{\rm K}{}_2+1}+\delta {}_{{\rm K}{}_2+1}d{}_{{\rm K}{}_2+1}^{soc}\in {\rm M}(42)$

如果xK2+1+dK2+1被接受为下一个迭代点xK2+2,则由(41)式和(42)式马上得到(iK2+2)-(iiiK2+2)成立。否则,考虑δK2+1=1的情形。由(41)式,(42)式和引理6(b),对$\overline{x}{}_{{\rm K}{}_2+2}=x{}_{{\rm K}{}_2+1}+d{}_{{\rm K}{}_2+1}+d{}_{{\rm K}{}_2+1}^{soc}$,有(h($\overline{x}$K2+2),f($\overline{x}$K2+2))∉FK2。因为K2∈I${}_{{\rm K}{}_2}^{{\rm K}{}_2+1}$,所以h(xK2)>0,则由(41)式中取i=2和引理6(a),得(h($\overline{x}$K2+2),f($\overline{x}$K2+2))∉GK2,再由(38)式,知(h($\overline{x}$K2+2),f($\overline{x}$K2+2))∉FK2+1,所以$\overline{x}$K2+2在步[5.3]不被拒绝。因此$x{}_{{\rm K}{}_2+2}=\overline{x}{}_{{\rm K}{}_2+2}$。再由(41)式和(42)式,得到对δK2+1=1 ,(iK2+2)-(iiiK2+2)成立。

当k≥K2+2时,假设对任意K2+2≤l≤k中的l,(il)-(iiil) 成立。如果xk+dk被接受,令δK:=0;否则令δK=1。令$\overline{x}{}_{k+1}=x{}_k+d{}_k+\delta {}_{k}d{}_k^{soc}$。由(34)式和(35)式,对i=2,3,有

$\begin{array}{l}\phi {}_{\sigma {}_i}(x{}_{k-1})-\phi {}_{\sigma {}_i}(x{}_{k+1})\ge \frac{1+\gamma {}_h}{2}(q{}_{\sigma {}_i}(x{}_{k-1},0)\\ -q{}_{\sigma {}_i}(x{}_{k-1},d{}_{k-1}))(43)\end{array}$

选l为:K2≤l≤k-1 ,则有下面两种情况:

Ⅰ.若k=K2+2,则l=K2,(34)式和(35)式,对i=2,3,有

$\begin{array}{l}\phi {}_{\sigma {}_i}(x{}_l)-\phi {}_{\sigma {}_i}(\overline{x}{}_{k+1})\ge \frac{1+\gamma {}_h}{2}(q{}_{\sigma {}_i}(x{}_l,0)-\\ q{}_{\sigma {}_i}(x{}_l,d{}_l))\ge 0(44)\end{array}$

Ⅱ.若k≥K2+2,由(43)式得$\phi {}_{\sigma {}_i}(\overline{x}{}_{k+1})\le \phi {}_{\sigma {}_i}(x{}_{k-1})$,再由(ik-1) 知(44)式仍然成立。(44)式表明$\phi {}_{\sigma {}_3}(\overline{x}{}_{k+1})\le \phi {}_{\sigma {}_3}(x{}_{{\rm K}{}_2})$,而且因为xK2∈M,可得到

$\overline{x}$k+1∈M。

如果xk+dk被接受,由(43)式,(44)式和(45)式,得(ik+1)-(iiik+1)成立。若xk+dk不被接受,由(45)式,(44)式中取i=2,l=K2和引理6(b),$\left(h(\overline{x}{}_{{\rm K}+1}),f(\overline{x}{}_{{\rm K}+1})\right)\notin F{}_{{\rm K}{}_2}$。而且,对l∈I${}_{{\rm K}{}_2}^k$和引理6(a),得$\left(h(\overline{x}{}_{{\rm K}+1}),f(\overline{x}{}_{{\rm K}+1})\right)\notin G{}_l$,从而由(38)式知$\overline{x}$k+1在步[5.3]不被拒绝,所以取$x{}_{k+1}=\overline{x}{}_{k+1}$,(ik+1)-(iiik+1)成立。

综上可知,若满足(20)式,则$\left\{x{}_k\right\}$超线性收敛于xk[18]。

局部描述子 篇4

手势识别在当前是比较热门的研究课题，由于人们的研究目的需求不同，在具体的处理方面就产生了不同的处理技术。手势是一种自然而直观的人际交流模式。基于视觉的手势识别是实现新一代人机交互所不可缺少的一项关键技术。然而，由于手势本身具有的多样性、多义性以及时间和空间上的差异性等特点，加之人手是复杂变形体以及视觉本身的不适定性，因此基于视觉的手势识别是一个极富挑战性的多学科交叉研究课题。

1 手势模型分析

手模型是指人手特征的描述。因为手势中的手和手指的姿态以及运动状况能为更高层的手势理解提供丰富的信息。而手势可分为静态手势和动态手势。静态手势是一种手的特殊形状或姿势，而动态手势是运动的手势，它由一组序列图像组成。

1.1 手的结构

手是一个多肢节的系统，它由27块骨骼组成，分为腕骨，掌骨和指骨，手可看成由4个相邻的手指，一个大拇指以及手掌组成的。每个手指由指段和关节组成，因此手是一种由关节相连的结构，随着关节运动，手的形状在不断变化。手势的这种变化可以通过指段和关节的状态空间上的变化来描述。

1.2 手运动分析及约束

手在运动时，手指间的交叠经常出现，有时会融入多种含义，而关节附近的皮肤表面会随着关节的运动变化而变化，从而难于估计其位置的变化。因此，必须根据手的自然运动建立对其施加约束的手模型。

1.2.1 手运动分析

图1所示为手模型的关节表示及它们可能具有的运动类型。每一个手指(Ⅱ-Ⅴ)具有4个自由度，其中手指的基部(MP)有2个自由度，弯曲和旋转，手指的中间关节处(PIP)和末端关节处(DIP)分别各有一个自由度，主要是弯曲运动。大拇指除了与其他4个手指一样具有4个自由度外，还有一个外展运动，所以大拇指具有5个自由度。外加手掌的前后左右运动2个自由度，因此，手运动总共具有23个自由度，及状态空间为23维。设每种状态的平均变化为G。则该状态空间所描述的孤立状态应为G23。

1.2.2 手关节运动约束

手关节运动主要可分为关节弯曲或伸展运动，以及手指侧向运动，并定义了手指和拇指的局部坐标，由于手上的某一部分的运动是由它绕其他关节点的旋转运动产生，则可用沿这3个坐标轴的旋转变换表示成(γ)，其中α表示旋转轴，β表示关节，γ表示手指。由于所定义的手势或手势语言，都应具有准确的含义，我们对其运动类型及所涉及的关节，在手模型中加入如下约束：

约束1MP, PIP, DIP关节以及手指“中轴”始终处于某一平面。除大拇指的MP关节可能有弯曲、伸展或侧向运动外，PIP和DIP只能在同一平面上作弯曲、伸展运动。

约束2DIP和PIP之间弯曲角度具有线性关系，其相关性表示为：

约束3除大拇指外的每个手指中的MP侧向移动的动态最大角度为：

其中。dmax是关节运动最大动态角度;smax是关节运动最大静态角度。

1.3 手势分类

手势一般可以分为以下几类:

(1)交互性手势与操作性手势。前者手的运动表示特定的信息(如乐队指挥)，靠视觉来感知;后者不表达任何信息(如弹琴)。

(2)自主性手势和非自主性手势。后者与语音配合用来加强或补充某些信息(如演讲者用手势描述动作、空间结构等信息)。

(3)离心手势和向心手势。前者直接针对说话人，有明确的交流意图，后者只是反应说话人的情绪和内心的愿望。

手势的另一种分类方法是将手的运动分解为两个可测量分量:

(1)手掌位置和方向;

(2)手势弯曲度。并根据这两个分量的不同组合对手势做了完备的分类。

可见手势的各种组合相当复杂，因此，在实际的手势识别系统中通常需要对手势做适当的分割、假设和约束。例如，可以给出如下的约束:

(1)如果整个手处于运动状态，那么手指的运动和状态就不重要;

(2)如果手势主要由各手指之间的相对运动构成，那么手就应该处于静止状态。

1.4 手数据结构

从上述的分析可知，每个手指除大拇指外都具有4个自由度，从而可以建立一条链，以协调手指的机构及运动，每条链可以获取4个参数，从而5个手指以手掌为根节点构成一个树型结构，树中的每个节点代表一个关节，关节通过指段具有相互关联的运动特性。由于手势是处于三维空间的姿态和位置，其定位难度较大。因此在定义手树结构时，对它的每一个节点都提供了模型中与其相关指段信息。手树结构的父节点(手掌)的定位应根据手树结构中的各子节点的偏移量来计算。使算法具有了从顶到底和从底到顶遍历模型树的能力。

2 基于傅立叶描述子的手势特征提取

傅立叶变换是线型变换的一种，它提供了一种解决线型系统问题的解决办法。傅立叶变换在很多学科的理论中起着重要作用，尽管可以象对待其他变换一样，把傅立叶变换看做纯数学的函数，但在许多领域，傅立叶变换也同样产生它们的函数一样的明确的物理意义。

傅立叶描述子(Fourier Descriptors)是物体形状边界曲线的傅立叶变换系数，它是物体边界曲线信号的频域分析的结果，是一种描述不受原点的移动及旋转影响的曲线的方法。

傅立叶描述子的基本思想是:假定物体的形状是一条封闭的曲线，沿边界曲线上所有点的序列为:{x (l), y (l):l=0, 1, K, n-1}，用复数的形式表示为：

这样，边界就可以在一维空间上表示。

一维序列的离散傅立叶系数定义为：

z是p的傅立叶变换，是点序列在频域中的表示。其傅立叶逆变换为：

利用傅立叶系数的性质z (k)=z*(n-k) (z*是z的共轭复数)，在系数z中，消去从k+1 (0≤K

傅立叶描述子与形状的尺度、方向和曲线的起始点位置有关。为了识别具有旋转、平移和尺度不变性的形状，需要对傅立叶描述子进行归一化。根据傅立叶变换性质，将物体形状边界起始点位置平移a长度，物体放大r倍，旋转角度φ和平移位移(x0, y0)后，新的形状的傅立叶变换系数z'(k):

其中：k=0, 1, Λ, n-1, x'(l)+y'(l)=x (l+a)+iy (1+a)

由上式可以看出，用傅立叶系数描述形状时，系数幅值‖Z (k)‖，k=1, 2, Λ，n-1具有旋转不变性和平移不变性(Z (0)不具有平移不变性)，而且与曲线起点的选择无关。当物体平移时，仅仅改变其Z (0)分量F (x0+iy0)的值。把每一个系数(Z (0)除外)的幅值‖Z (k)‖除以‖Z (1)‖，则是不随尺度变化而变化的，所以时具有旋转、平移和尺度不变性，并且与曲线的起点位置的选择无关，我们把它作为傅立叶描述子，故归一化的傅立叶描述子d (k)定义为:

实验中，我们取除Z (0)外的前12个系数，得到12维的特征向量，该特征向量具有旋转、平移和尺度不变性，而且与曲线的起点位置的选择无关，我们采用快速傅立叶变换计算傅立叶系数，并对有关系数进行处理，得到归一化的傅立叶描述子。

3 手势识别

手势识别就是把模型参数空间里的轨迹(或点)分类到该空间里某个子集的过程。静态手势对应着模型参数空间里一个点，而动态手势则对应着模型参数空间里的一条轨迹。手势识别属于模式识别的一种，故其基本的识别方法有两种:统计识别方法和结构(句法)识别方法。与此相对应的识别系统应有两个过程组成，即设计和实现，设计是指用一定数量的样本(又称训练集或学习集)进行分类器的设计，实现是指用所设计的分类器对待识别的样本进行分类决策。

本识别系统是基于统计识别方法的，它的训练过程如图2所示:

本文分别提取了手势的形状特征和傅立叶描述子作为手势的特征向量，在判断输入图像与标准图像间的相似程度时，分别使用了较常用的类似度和欧氏距离。在基于傅立叶描述子的识别中，由于傅立叶变换的各频率分量互相正交，可采用欧氏距离计算输入图像与标准图像的相似度。在基于形状特征的识别中，考虑到类似度最便于分析和计算，我们采用了类似度来判别输入手势图像与各类图像间的距离。由于输入图像很可能是图像库之外的手势图像，所以需要一个临界值T来判定输入图像的可识别性，根据计算出的最小距离是否符合临界值T的判断标准来决定是否拒绝识别该图像。

4 实验结果及结论

在基于傅立叶描述子的识别实验中，我们取除Z (0)外的前12个系数(k=1, 2, Λ, 12)并对其归一化，从而构建唯一标识手势图像的12维特征向量。设X表示为输入字母手势经过归一化的特征向量，X=(dx (1), dx (2), K, dx (12));G表示为样本库中某一标准手势经过归一化的特征向量，G=(dg (1), dg (2), K, dg (12))，则X和G的欧式距离(Euclidean distance)为：

当D=0时，两个形状完全相似;D越大，物体形状的差异越大。通过计算欧式距离D，可判别输入手势和标准手势中的哪一个最接近。实验中，计算输入手势与样本库中每一类手势的距离D，求出最小值min，并取临界值T=0.4，当min≤T时，即可判定输入手势属于哪一类。利用上述算法可以计算输入手势与标准手势之间的欧式距离D，表1所示的是部分字母手势的计算结果，横向字母表示标准手势，纵向字母表示输入手势，标准手势和输入手势的交点数据为它们的欧式距离，对输入手势计算它和每个标准手势之间的欧式距离，距离最小者为识别结果。从表1中可以看出同一字母的标准手势和输入手势会有细微差别，D一般不会为0。

实验中，使用摄像头采集了中国手语中30个字母手势的图像，每个手势采集3次，共形成3套手势图像，再从中选择1套手势作为标准手势，构成样本库，其他构成测试集。在测试集中，我们对手势图像进行了适当的平移、旋转和尺度变化。实验结果表明，归一化的傅立叶描述子能够更加鲁棒地识别和区分具有旋转、平移和尺度变化的手势图像，其识别率达到87.6%，是快速识别和分析物体形状的一种有效方法。同时，采用形状特征的二级分类策略进行识别，粗分类的分类率为90.5%，最终识别率达到84.5%，每个手势的识别时间比直接使用基于类似度的模板匹配进行识别缩短了0.45s，这表明二级分类及所提取的形状特征向量也是有效的。

5 结束语

本文对手模型及关节运动做了较为深入的分析，因此构造了基于规则约束的手模型数据结构，从而有利于手势的分析与采用傅立叶描述子的手势识别，取得了较好的效果。

由于手具有弹性，同一手势有时会出现较大差别，手的位置又处在三维空间，难于定位，使手势的精确度差，因而增加了识别的难度。该课题研究的下一步工作将在智能化和自然手势等方面做进一步探索。

参考文献

[1]Rijpkema H, Girard M.Computer animation of knowledge based human grasping.Computer Graphics, 1994 (4) .

[2]汪成为, 高文.灵境 (虚拟现实) 技术的理论、实践及应用[M].北京:清华大学出版社, 1996.

基于傅立叶描述子的多边形综合 篇5

从遥感影像上提取的地物边界的多边形, 具有点数多, 形状复杂的特点, 然而在地图信息综合过程中, 需要对多边形进行综合, 以满足实际需要。多边形的综合往往归结于曲线的综合。迄今为止, 国内外学者已经提出了大量不同的曲线综合方法, 其中比较典型的有Reumann-Witkam法、Douglas-Peucker法、Li-Openshaw法、Opheim法、光栅法、分形法、小波变换法、QTM网格法和Delaunay三角网法等曲线化简综合算法[1,2,3,4,5,6]。虽然现今有许多多边形综合的算法, 但在实际生活生产中, 针对不同的多边形会才去不同的多边形综合方法。

傅立叶描述子具有的平移、旋转、尺度伸缩不变性的特性。本文基于傅立叶描述子的多边形综合能对从遥感影像上提取的多边形地物起到较好的平滑作用, 对多边形的毛刺剔除和顶点数的减少, 有较好的效果。

2 离散傅立叶变换与傅立叶描述子

2.1 离散傅立叶变换

傅立叶变换是线型变换的一种, 提供了一种解决线型系统问题的解决办法, 在很多学科的理论中起着重要作用。尽管可以象对待其他变换一样, 把傅立叶变换看做纯数学的函数, 但在许多领域, 傅立叶变换也同样产生它们的函数一样的明确的物理意义。

用N个互相间隔x单位采样函数f (x) , 使其成为系列

规定f (x) f (xÁxx)

2.2 傅立叶描述子

傅立叶描述子是物体形状边界曲线的傅立叶变换系数, 它是物体边界曲线信号的频域分析的结果, 是一种描述不受原点的移动及旋转影响的曲线的方法。傅立叶描述子的基本思想是:假定物体的形状是一条封闭的曲线, 沿边界曲线上所有点的序列为:

复数的形式为:

以为序列的离散傅立叶系数定义为:

z是p的傅立叶变换, 是点序列在频域中的表示。其傅立叶逆变换为:

傅立叶系数z中, 消去从 到n范围内的高频成分。再进行傅立叶逆变换, 将得到和原曲线近似的曲线, 但原曲线中突变的部分将变得平滑, 这个近似的曲线称为原曲线的第K近似曲线。这个意义下的傅立叶系数子集 成为傅立叶描述子。由于傅立叶系数有能量向低频集中的特性, 故用较少的系数就可以打到区分描述不同形状边界的目的。傅立叶低阶系数能够反映大体形状, 高阶系数可以精确定义形状特征, 少数傅里叶描述子携带了形状信息, 能够反映边界的大略本质。

3 算法流程

首先从遥感影像上提取得到地物的边界点串, 然后判断边界点个数是否为偶数, 如果不是, 用最后一对坐标补上一行, 以确保坐标对为偶数对。对横、纵坐标分别进行正负变换, 然后用这两组数据进行离散傅立叶变换, 得到经过一系列的傅立叶系数。选取合适的边界重构的傅立叶系数个数, 把除了最中间的一定个数坐标点之外其余坐标点都置0。再把这两组组数据作傅立叶逆变换, 再对横纵坐标进行一次正负变换, 还原坐标值。最后得到变换后的边界坐标, 把它们输出就得到了平滑后的边界图。算法流程图如图1所示。

4 实验及分析

为了验证基于傅立叶变化多边形综合算法的有效性, 本文设计了一组对比实验。图2为原始地物多边形边界。该多边形原始数据是利用图像分割技术从遥感影像上得到的地物边界, 共535个点, 其中最小横坐标值为3338, 最大横坐标值为3462, 最小纵坐标值为2215, 最大值为2443。在vs2010环境中应用步骤3中的流程进行处理, 得到综合后的多边形最小横坐标值为3340, 最大横坐标值为3459, 最小纵坐标值为2217, 最大值为2441。从实验结果可以看出, 综合后的多边形比原始多边形更为光滑, 坐标点的范围与原始坐标范围相差较小, 这是因为去除了多边形局部细节的原因, 该方法对从遥感影像提取的多边形提出毛刺有较好的效果。

5 结论与展望

本文提出了一种基于傅立叶描述子的多边形综合方法, 该方法是从频率域的角度对多边形进行综合, 毛刺的去除有一定的效果。多边形综合的基本要求是保持其形状结构特征, 但如何体现图形的形状结构特征, 现阶段还缺乏适合于计算机处理的量化指标。经综合处理后, 原有多边形不同部分复杂程度的对比需要得到应有的保持, 但目前还缺乏有效的技术措施, 仍有许多问题急需解决。

摘要：傅立叶描述子具有的平移、旋转、尺度伸缩不变性, 在数字图像处理中得到广泛的应用。本文针对从遥感影像上提取的多边形地物边界点数多、形状复杂的特点, 提出了一种基于傅立叶描述子的多边形综合的方法, 该方法对地物的边界能起到较好的平滑作用。

关键词：傅立叶描述子,多边形综合,边界平滑

参考文献

[1]Douglas D H&Peucker T K.Algorithms for the Reduction of the Number of Points Required to Represent a Line or Its Caricature[J].The Canadian Cartographer, 1973, 10 (2) :112-122.

[2]张传明, 潘懋, 吴焕萍等.保持拓扑一致性的等高线化简算法研究[J].北京大学学报:自然科学版, 2007, 43 (2) :216-222.

[3]朱长青, 王玉海, 李清泉, 等.基于小波分析的等高线数据压缩模型[J].中国图象图形学报, 2004, 9 (7) :841-845.

[4]焦健, 魏立力, 曾琪明.基于QTM的线状图形自动化简算法探讨[J].测绘科学, 2005, 30 (5) :89-91.

[5]Tinghua Ai.The drainage network extraction from contour lines for contour line generalization.ISPRS Journal of Photogrammetry&Remote Sensing, 2007, 62:93-103.

局部描述子 篇6

随着多媒体技术、网络技术的迅速发展, 图像信息的应用日益广泛, 对规模越来越大的图像数据库、可视信息, 进行有效的管理成为信息时代人们迫切需要解决的问题, 基于内容的图像检索是解决这一问题的关键技术之一。由于许多图像检索系统都把重点放在基于颜色或者纹理的方法上。但是对于某些图像来说, 纹理和颜色信息不够丰富, 如商标图像, 这时基于颜色和纹理的方法就无法满足检索需要, 而必须从图像的形状着手。形状特征是图像的核心特征之一, 图像的形状信息不随图像颜色的变化而变化, 是物体的稳定特征[1,2]。用形状特征区别物体非常直观, 是人们分类不同图像的主要特征之一。因此, 利用形状特征检索图像可以提高检索的准确性和效率, 对目标的形状描述可以作为图像检索和索引的依据, 主要用于快速检索, 它是基于内容的图像检索系统的重要方法[3,4,5]。

为了快速、准确地获得所需多媒体信息, MPEG-7于2001年9月成为国际标准, 它提供了一整套多媒体内容描述工具, 进一步发展了基于内容的描述和检索规范。MPEG-7标准只是规范信息的描述格式和语法, 如何取得这些信息以及如何利用这些信息进行检索等内容不在MPEG-7标准规定的范围内[6]。对形状特征, MPEG-7推荐了3种描述符[7]:区域的形状, 轮廓的形状和3-D形状。

矩是进行图像区域形状描述的经典方法[8], 在此采用MPEG-7标准视觉区域形状描述子-角半径变换 (ART) 系数, 作为对图像内容的形状描述。商标图像检索要求具有旋转不变性, 因此将ART变换系数的模值作为区域形状不变性特征。文中提出在离散情况下ART变换算法的实现方法, 并利用极坐标系的对称性和三角函数性质, 提出了ART变换的快速算法。构建了一个基于形状特征的自动图像检索系统, 并将其应用于商标图像检索。实验结果表明, 该方法具有一定的可行性和有效性, 提出的快速算法只需计算图像区域大小的1/4, 大大降低了数据冗余。

1 形状描述符的提取

1.1 ART (Angular Radial Transform) 算法

在MPEG-7推荐的一个形状描述符——基于区域的形状描述符中, 使用了一组角半径变换 (ART) 系数, 它是一种基于矩的图像描述符, 可用于描述单连通和多连通区域, 并且对旋转和小变形具有鲁棒性。ART是在极坐标系定义的单位圆上的一个二维复变换。它是一种正交变换, 对噪声具有鲁棒性[9]。ART变换系数定义为:

$\begin{array}{l}F{}_{nm}=\langle V{}_{nm}(\rho ,\theta ),f(\rho ,\theta )\rangle =\\ {\displaystyle {\int }_0^{2\text{π}}{\displaystyle {\int }_0^{1}V}}{}_{nm}^{*}(\rho ,\theta )f(\rho ,\theta )\rho \text{d}\rho \text{d}\theta V{}_{nm}(\rho ,\theta )=\frac{\text{e}{}^{\text{j}m\theta }R{}_n(\rho )}{2\text{π}}\\ n=0,R{}_n(\rho )=1,\text{e}\text{l}\text{s}\text{e}R{}_n(\rho )=2\cos (n\text{π}\rho )\end{array}$

式中:n=0, 1, 2;m=0, 1, …, 11;Fnm是在序数 (n, m) 的ART系数;f (ρ, θ) 是在极坐标系的一个图像函数, Vnm (ρ, θ) 是ART的基函数, 它沿角度和半径方向是可分的;V*nm (ρ, θ) 是Vnm (ρ, θ) 的共轭。

1.2 算法实现

(1) 将区域分割[10]后的数字图像Imn (m, n均为奇数) 放入极坐标系, 由于一般的数字图像原点在矩阵的左上角, 可通过线性变换将图像的中心点 ([m/2], [n/2]) , ([]表示取整) 定义为原点, 且与极坐标系的原点重合, 以便进行后续变换。

(2) 建立从 (x, y) 到 (ρ, θ) 的映射。对于二值图像函数I (x, y) , 其值为1或0。所以极坐标系下的图像函数f (ρ, θ) , 其值为1或0。其中$\rho =\sqrt{x{}^2+y{}^2}‚\theta =\arctan y/x$。用ρ=ρ/ (ρmax) 将极坐标的图像归一化到单位圆上。

(3) 将ART变换双重积分化为求和运算。由于ART变换是定义在极坐标系下角度和半径方向的正交变换, 所以双重积分可以化为分别对半径和角度方向的积分的乘积。根据定积分近似求和的原则, 可以得到ART变换在序数 (n, m) 的近似值。所以定积分近似求和可用如下的公式计算:

$\begin{array}{l}F{}_{nm}=\langle V{}_{nm}(\rho ,\theta ),f(\rho ,\theta )\rangle =\\ {\displaystyle {\int }_0^{2\text{π}}{\displaystyle {\int }_0^{1}V}}{}_{nm}^{*}(\rho ,\theta )f(\rho ,\theta )\rho \text{d}\rho \text{d}\theta =\\ \frac{1}{2\text{π}}{\displaystyle {\int }_0^{2\text{π}}{\displaystyle {\int }_0^1\text{e}}}{}^{-\text{j}m\theta }R{}_n(\rho )f(\rho ,\theta )\rho \text{d}\rho \text{d}\theta =\\ \frac{1}{2\text{π}}{\displaystyle \sum \text{e}}{}^{-\text{j}m\theta }{\displaystyle \sum R}{}_n(\rho )f(\rho ,\theta )\rho \end{array}$

1.3 ART的旋转不变性

考虑一幅图像, 设其以α角度旋转, 旋转后的图像用f′表示, 则f′ (ρ, θ) =f (ρ, θ-α) 。计算图像在旋转后的ART变换系数。

$\begin{array}{l}F{}_{nm}^{´}=\langle V{}_{nm}(\rho ,\theta ),f(\rho ,\theta -\alpha )\rangle =\\ \frac{1}{2\text{π}}{\displaystyle {\int }_0^{2\text{π}}{\displaystyle {\int }_0^1\text{e}}}{}^{-\text{j}m\theta }R{}_n(\rho )f(\rho ,\theta -\alpha )\rho \text{d}\rho \text{d}\theta =\\ \frac{1}{2\text{π}}{\displaystyle {\int }_0^{2\text{π}}{\displaystyle {\int }_0^1\text{e}}}{}^{-\text{j}m(\theta {}_1+\alpha )}R{}_n(\rho )f(\rho ,\theta {}_1)\rho \text{d}\rho \text{d}\theta \end{array}$

令θ1=θ-α, 则:

$=\frac{1}{2\text{π}}{\displaystyle {\int }_0^{2\text{π}}{\displaystyle {\int }_0^1\text{e}}}{}^{-\text{i}m\theta }R{}_n(\rho )f(\rho ,\theta )\rho \text{d}\rho \text{d}\theta$

令θ=θ1, 则:

$\begin{array}{l}=\left(\frac{1}{2\text{π}}{\displaystyle \sum \text{e}}{}^{-\text{j}m\theta }{\displaystyle \sum R}{}_n(\rho )f(\rho ,\theta )\rho \right)\text{e}{}^{-\text{j}m\alpha }\\ =F{}_{nm}\text{e}{}^{-\text{j}m\alpha }\end{array}$

上式表明, ART变换系数仅具有相位的移动。它的模值保持不变, 所以对于数字图像将$\left|F{}_{nm}\right|$作为区域形状的不变性特征。

1.4 ART的快速算法

由欧拉公式知:e-jmθ=cos mθ-jsin mθ。令θ1, θ2, θ3, θ4分别是直角坐标系中第一、二、三、四象限点 (x, y) , (-x, y) , (-x, -y) , (x, -y) 所对应极坐标的角度。ρ1, ρ2, ρ3, ρ4分别是对应极坐标的半径。由极坐标原点是图像区域的中心和正、余弦三角函数的性质知:θ1=-θ2, θ4=π-θ1, θ3=-θ4, ρ1=ρ2=ρ3=ρ4, cos θ1=-cos θ2=-cos θ3=cos θ4, sin θ1=sin θ2=-sin θ3=-sin θ4, 所以只需求1/4图像区域形状的ρ, θ, cos θ和sin θ值, 这样就大大降低了数据冗余。

2 相似性度量检索

对上述特征提取产生的36个特征值$\left|F{}_{nm}\right|$, 共同组成特征向量$\mathit{F}=[\left|F{}_{nm}(1)\right|,\left|F{}_{nm}(2)\right|,\cdots ,\left|F{}_{nm}(36)\right|]$, 对其进行高斯归一化, 即F= (F-M) /σ, 其中M, σ分别表示特征值的均值和标准差。对归一化后的特征向量用欧式距离进行相似性度量。

3 实验及结果分析

为了检验本检索方法的可行性和有效性。在Windows XP, Matlab 7.0环境下, 构建了一个基于形状特征的商标图像自动检索系统进行测试。测试图像库是由720幅来自Internet商标图像组成。

3.1 评价准则

为了使评价更具客观性, 使用MPEG-7形状核心实验的评价准则[11], ANMRR (Average Normalized Modified Retrieval Rank) 平均归一化调整后的检索秩和AR (Average Recall) 平均查全率是用于MPEG-7核心实验的评价准则。AR, ANMRR∈[0, 1]。AR值越高, 查全性能越好;ANMRR值越低, 查准性能越好, 说明更多正确的结果排在前面, 这也是文中对检索方法的评价依据。具体方法如下:

(1) 首先挑选出一个查询图像的集合Q, 对每个查询图像主观地选取一组视觉相似的图像作为标准, 也称正确答案 (Ground Truth) 。

(2) 查询图像q的相似图像的个数为ng (q) 。对于查询图像q, 检索结果的截断值K定义为min{4×ng (q) , 2GTM}, 其中, GTM是在所有查询图像中最大的相似图像个数, 即GTM=max{ng (q) }。

(3) 对于查询图像q, 在前K个检索结果中正确的个数记为nr (q) , 漏掉的个数记为M (q) =ng (q) -nr (q) 。查全率记为R (q) =nr (q) /ng (q) 。

(4) 每个正确答案在检索结果中都有一个秩 (Rank) r (i) , i=1, 2, …, ng (q) 。在前K个检索结果中, 正确的图像的秩r (i) 就是它的序号, 其余被漏掉的图像的秩r (i) 都设定为K+1。

(5) 对于某个查询图像q, 它的平均检索秩和调整后的检索秩分别定义为:

$\begin{array}{l}\text{A}\text{R}(q)={\displaystyle \sum _{i=1}^{n{}_g(q)}\frac{r(i)}{n{}_g(q)}}\\ \text{Μ}\text{R}\text{R}(q)=\text{A}\text{R}(q)-n{}_g(q)/2-0.5\end{array}$

(6) 将MRR (q) 归一化至[0, 1]范围内, 得到归一化调整后的检索秩NMRR (q) :

$\text{Ν}\text{Μ}\text{R}\text{R}(q)=\frac{\text{Μ}\text{R}\text{R}(q)}{{\rm K}-n{}_g(q)/2+0.5}$

(7) 对Q中所有的查询图像q的NMRR (q) 和R (q) 做平均, 得到ANMRR和AR:

$\begin{array}{l}\text{A}\text{Ν}\text{Μ}\text{R}\text{R}=\frac{1}{Q}{\displaystyle \sum _{q=1}^Q\text{Ν}}\text{Μ}\text{R}\text{R}(q)\\ \text{A}\text{R}=\frac{1}{Q}{\displaystyle \sum _{q=1}^{Q}R}(q)\end{array}$

3.2 商标图像测试及结果

对720幅商标图像库中24类包含形状的旋转变换的图像进行24个查询。24类不同形状的商标, 各包含有10种旋转变换 (旋转系数i×36°, i=0, 1, 2, …, 9) , 其中旋转变换是采用Matlab工具箱中的旋转工具进行数字图像处理后的图像。实验各参数设置如下:Q=24, ng=10, K=40。为了使实验结果更具客观性, 重复实验10次, 每次在每一个类中所选择的查询图像各不相同, 计算AR和ANMRR的平均值。实验结果如表1所示。

由表1可以看出, 每一次实验AR和ANMRR的值都有差别, 这也说明了随着实验重复次数的增加, AR和ANMRR的值将更具有客观性。

3.3 提取形状特征描述符用时比较

基于内容的图像检索系统中提取图像特征描述符的所用时间是评价该算法的一个重要数据。在AMD Athlon (tm) 64 Processor 3 500+/2.21 GHz/1.00 GB配置的PC机上。在720幅商标图像数据库中随机取80幅, ART算法的平均提取时间是8.401 2 s, 而文中提出的快速算法的平均提取时间是2.830 1 s。可见快速算法用时约为ART算法的34%。大大降低了数据冗余。

4 结 语

通过对MPEG-7视觉形状描述子的分析研究, 重点讨论了区域形状描述子——ART变换。ART变换是一个二维正交复变换, 鉴于其复变换系数模值具有旋转不变性, 以及ART的描述单连通和多连通区域的性质, 提出离散情况下, ART算法实现方法。考虑到极坐标系的对称性和三角函数性质, 进而提出ART变换的快速算法。构建一个基于形状特征的自动图像检索系统, 并将其应用于商标图像检索。实验结果表明, 该方法具有一定的可行性和有效性, 提出的快速算法大大降低了数据冗余。如果将该系统结合轮廓特征, 或加入相关反馈, 系统检索正确率将会进一步提高, 这项工作将在其他文章详细介绍。

参考文献

[1]付玮, 曾接贤.基于形状特征的图像检索技术研究[J].计算机技术与发展, 2007, 17 (11) :228-232.

[2]田卉, 覃团发, 梁琳.综合颜色、纹理、形状和相关反馈的图像检索[J].计算机应用研究, 2007 (11) :292-294.

[3]刘涛, 张艳宁, 孙瑾秋.一种基于目标区域的图像检索方法[J].计算机工程与应用, 2006, 42 (26) :68-70.

[4]周静, 郝红卫.基于用户感兴趣区域的图像检索方法[J].计算机应用研究, 2007, 24 (9) :282-283.

[5]闫雅楠, 夏定元.结合边缘检测和区域分割的形状特征提取[J].电视技术, 2007, 31 (3) :12-15.

[6]陈慧.基于内容的图像检索与MPEG-7[J].福建电脑, 2007 (12) :146-147.

[7]纪敏.MPEG-7颜色、纹理和形状描述子[J].计算机工程与应用, 2004, 40 (26) :44-47.

[8]张素芳, 李剑中, 冯刚.基于内容的图像检索技术概述及其发展趋势[J].仪器仪表学报, 2006 (Z1) :297-299.

[9]张李义, 李欲.基于MPEG-7的图像内容描述方案研究[J].情报学报, 2004, 23 (3) :313-320.

[10]郭丽.基于内容的商标图像检索研究[D].南京:南京理工大学, 2003.

局部描述子 篇7

轮廓[1,2]作为图像的重要特征已成共识,对于丧失了颜色信息的灰度图像,特别是红外图像更是如此。在实际应用中,要求对目标轮廓的描述具有平移、旋转和缩放不变性[3](统称畸变不变性),并且提取速度快、方法简单。对于轮廓的描述子有很多,例如:常用的傅里叶描述子[4,5],基于轮廓曲率的描述子[6],感知轮廓描述子[7],边界链码以及各式各样的形状描述函数[8,9,10]。傅里叶描述子具有良好的畸变不变性,但对于形状相似的轮廓无法识别(第二章将加以验证)。其它的轮廓描述子都牵扯着重要的一步,即特征提取时起始点的选择。这本质上也就是确定图像的方向,解决旋转不变性的问题。人们一直在寻找一种确定方向方法简单,而又能对轮廓进行精确描述的轮廓描述子。通过找出图像的主轴[11]方可以很方便的确定轮廓的方向,但是这种方法精度不是很高,对起始点会产生错位的影响。本文用扇区投影的方法将起始点的选择转化为起始区域的选择问题,这样的好处二点:其一对轮廓方向归一化的精度要求不是很高,最简单的主轴方法就可以满足要求;其二通过选择合适的扇区个数可以更加的突出两轮廓的不同之处,尤其对一些差别细微的轮廓可以更好的体现出其识别的优越性。

2 轮廓的扇区投影-小波描述

2.1 定义

现考虑一个由N个点组成的封闭边界,其坐标系的原点取在边界曲线的质心上。从任一点开始绕边界一周就得到一个复数序列:

若对s(k)进行傅里叶变换则成了傅里叶描述子。而在此,对s(k)进行取模,即

式(2)也就是轮廓上的相素点与其质心的距离。下面对|s(k)|进行扇区投影,即将轮廓图像划分为n个扇区Δ1,Δ2,…,Δn每个扇区的角度为2π/n,对落入各个扇区内的|s(k)|序列进行相加变为新序列中的一个点:

若对落入每个扇区内轮廓相素点的个数或灰度值进行相加,这就成了普通的扇区投影了。这种做法体现不出轮廓序列各点的位置关系,所以对其与质心点的距离进行相加,相当于对落入每个扇区内的相素点分配了一个权值。

新的序列中序列点的个数恰好就是扇区划分的个数,多分辨率分析[12,13,14]是图像分析领域中的常用方法,接下来的工作就是对扇区投影出来的新序列进行多分辨率分析:

p和d分别代表小波分析的平滑逼近和细节信号。为方便表述,将p和d统称为小波分析的值w。而通过特征选择过程选择出来的一系列特征就构成了一组用来识别的特征向量(w1,w2,…,wn)。

2.2 方向归一化对|s(k)|的影响

确定轮廓方向最常用的方法有两种:一是选离质心最远的点作为参考点,并把此点与质心之间的连线约束到某一固定方向如横轴方向;另一种方法是求出边界主轴,以主轴上离重心最远的点作为标记起点。后一种方法考虑了边界上所有的点,因此计算量较大但也比较可靠。

第一种方法虽然简单但其实现起来往往是不可行的,两个不同方向的图像由于离散误差会造成它们离质心最远的点往往不是同一个参考点。对一些对称的图像更是如此,因为对称的图像中离质心最远的点是不止一个的,所以多用第二种方法。

图1(a)中给出了同一类飞机轮廓24个不同角度经方向归一化后的图像,采用的是将主轴方向[11]约束到横轴的方法。

图1(b)是对其中两幅图像(第二个与第二十个飞机轮廓)的放大,通过图1(b)可以清晰的看出方向归一化的不精确性,这种不精确性是由不可消除的旋转离散化误差造成的。图2给出了方向归一化不精确性对轮廓复数序列模|s(k)|的影响。本应该相互重合的24条曲线沿着横轴的方向发生了平移。

2.3 扇区投影法

轮廓序列模曲线对方向归一化精度敏感的问题,引入扇区投影的方法加以解决。扇区投影的方法可以把起始点的选择问题转化为起始区域的选择,区域对方向归一化精度的要求远没有点那么敏感。而且,对于两类差别很小的图像来说,他们之前的差别也不可能仅仅是个别相素点的差别,而是某一小块区域的不同。对扇区投影而言,在选择合适的扇区个数的前提下,这一小块不同的区域很大可能就落在某一个扇区中,所以更容易实现对不同细小差别的描述。

图3给出了扇区投影一般流程图,计算时将[-π,π]的一个圆周划分为32个扇区。从图3的第二部分可以看出两个轮廓的细小区别主要体现在11∼14,18∼22扇区。经过扇区投影后,从两个轮廓的序列模曲线上(图3的第三部分)可以明显的看出区别,说明了通过扇区投影可以更容易对细小差别的轮廓进行区别。

从图3的第二部分可以看出扇区投影计算并不是每个扇区内轮廓所包含的面积。当且仅当是特殊一些的轮廓,即满足在(r,θ)极坐标系中是一一对应关系时,计算的才是轮廓所包含面积。

图4给出了这两类飞机24个不同方向的样本轮廓复数序列模经过扇区投影后的曲线,24条曲线画在了同一张图中。24根不同的曲线相对于原曲线(图2)已基本看不出错位。24个不同方向的飞机样本所对应的曲线在同一坐标中大致重合说明了方向归一化的问题已获得了解决。

2.4 扇区个数的选择

在扇区投影中,扇区个数的选择很重要,选择不同的扇区个数对识别的结果是有很大影响的。

观察图4与图5,扇区个数分别为128,64,32和16时,可以发现:随着扇区个数的减少,曲线越来越平滑,同时体现在曲线上的差异也越来越少,当扇区的个数减少为16时,已基本上看不出两类图像的差别。但是当扇区个数太多例如当扇区个数为128时,曲线中高频部分很多,这会给后续的小波分析带来一定的复杂性。所以对于不同的样本集来说,总存在着一个特定最优的扇区个数使得识别效果最优。根据经验分析来说,对于大多数的样本集,一般取32个扇区就足以将它们分开。

用扇区投影的方法从二维的轮廓信息中提取出来了一维的特征,再用小波的方法对一维曲线进行分析,就可以提取出来更多的特征。

3 扇区投影-小波描述的特性比较研究

傅里叶描述子[4,5]对一些差别比较大的轮廓类别具有着很好的分类效果,但是其不能实现细小差别轮廓的分类。因为傅里叶描述子在对轮廓复数序列处理时用了傅里叶变换,而傅里叶变换的过程相当于对复数序列作各个频率成份的统计,正是这样的一个过程淹没了轮廓复数序列中的细小差别。图6是图3两类差别细小的飞机轮廓作傅里叶变换的结果以及识别效果的聚类图与扇区投影小波描述子作比较。

从两类飞机轮廓序列的频谱上是看不出区别的,识别结果更证明了这一点:傅里描述子对于细小的轮廓是区别不了的。而用扇区投影-小波描述子可以区别。在小波的选用上,haar小波就可以达到很好的分类效果。对24个训练样本提取出来的特征量作高斯分布假设,根据文献[12]的方法提取出来haar小波中最好的两组特征参数是:

m=0,n=12时扇区投影小波描述子作为第一个特征量w1;

m=1,n=12时扇区投影小波描述子作为第一个特征量w2。

还可以选用更多的特征量,但两个构成的特征向量(w1,w2)已经可以满足分类要求。图6给出了各类24个测试样本的聚类图。

在特征提取和选择后,紧接着的问题就是分类器的设计,分类器简单复杂不一,往往是特征提取和选择的方法已决定了分类器的设计。一个好的特征往往用比较简单的分类器就可以将其进行分类。而相对不是很优的特征其分类器必然也很复杂。由于本文中都是选择最好的两个特征组成的特征向量组,所以分类器设计也就比较简单。

选用线性分类器就可以将上述测试样本100%的分开。求出线性判别函数为

环投影[13]的方法已被证明是一种很好的解决旋转不变性的方法。但对于图7所示的两幅轮廓图像却是无法区分的,用扇区投影小波描述子可以完全区分,图8给出了二类测试样本的聚类效果图。

为了说明此得法具有普遍性,又选择样本集三如图9所示进行分类实验。样本集三是多类样本,并且轮廓之间的差别比较大。图10给出了三类测试样本的聚类效果图。

对于图7和图9运用和第一个样本集同样的方法进行特征选择与分类器的设计,不再赘述。

对于噪声图像对此描述子影响主要体现在轮廓提取的算法上,此处不加以讨论。

4 结论