基于最小点对成本的二维轮廓精确匹配与分析方法

李向军,周 勇,刘 韬,刘伯成,罗 铭

(南昌大学 a.信息工程学院; b.软件学院,南昌 330031)

0 概述

人类通过视觉、触觉和听觉等多模态来识别物体,视觉是其中极为重要的一种模态。经过亿万年的进化,生物通过三维视觉进行对象识别时获得了极高的效率与较好的鲁棒性,且与视点和对象取向无关,即使是在复杂环境中也能轻松识别出目标对象。在对物体进行识别的过程中,人类使用了多种特征,如轮廓、纹理等,且轮廓相对纹理而言更加稳定,原因是其不易受到光照变化和颜色变化的影响。文献[1]对比了人类视觉和由深度神经网络驱动的机器视觉系统,发现两者处理对象信息的方式存在显著差异,人类在识别物体时倾向于轮廓,而由深度神经网络驱动的机器视觉系统更倾向于纹理。虽然人类在识别图像中的物体时是基于大量的先验知识,如轮廓、纹理、颜色和上下文等[2],但是即使只给定轮廓,人类也能迅速识别出其类别,这说明轮廓在物体识别中起重要作用。物体的形状识别作为物体识别的主要内容,一直是计算机视觉领域的研究热点之一,这类方法[3-4]一般通过轮廓匹配来实现,可以将其统称为基于轮廓的识别方法。二维轮廓匹配方法应当具有人类视觉所具备的平移不变性、旋转不变性、尺度不变性以及镜像不变性4个基本特性。

自然界中的生物受到物理规律的约束,不同部位的尺寸大小与其整体重量存在一定的关系。在观察物体时,人类的眼睛会将三维世界投影为二维图像,但大脑会根据环境而构建出相应的三维模型[5]。将三维世界物体转换为二维轮廓图像时,不同部位的尺寸大小与其整体重量的关系就转变为距离关系和面积关系。本文通过交互式分割法学习上述关系,分割出符合人类视觉特性的轮廓段,对轮廓进行点对匹配以度量轮廓间的相似性,从而提取尽量多的轮廓全局特征和局部特征,减少信息丢失。

1 相关工作

文献[6]总结了近年来相继出现的二维形状表示及匹配方法。早期的形状描述符[7-9]主要是获取轮廓的全局特征,如傅里叶描述符[7]、矩描述符[8-9],其通过计算特征向量之间的距离进行物体识别,但是,类内轮廓差异大的物体识别率不高且轮廓细节匹配能力弱。形状上下文[10]是一种经典的描述符,其实现了轮廓点的局部分布编码,对识别率有较大的改善。形状上下文以采样点为极点构建极坐标系,将极角划分为m份,极径划分为n份,得到m×n个区域,统计每个区域内采样点的出现次数,构建对应的直方图,该直方图表示了其他采样点相对于当前点的局部分布。形状上下文统计的是采样点的分布,对噪声数据不敏感,但是其也丢失了全局信息。文献[4]将轮廓点顺序作为全局形状特征并与形状上下文相结合,提高了描述符的全局特征编码能力。文献[3]分析部位及其结构在计算机视觉和人类视觉中的重要性,采用内距离来代替形状上下文中的欧氏距离,提出内距离形状上下文IDSC(Inner-Distance Shape Context),其中,内距离定义为轮廓上标记点与其他采样点在轮廓内的最短路径长度。对于具有关节部位的轮廓,内距离比欧氏距离能更有效地捕获部位结构从而建立更准确的描述符。文献[11]为了降低匹配的复杂度并提高检索速度,提出轮廓点分布直方图(Contours Points Distribution Histogram,CPDH)描述符,其基于极坐标系下对象轮廓采样点的分布而忽略了轮廓的局部特征。文献[12]提出封闭曲线和开放曲线的相似性度量方法,其将轮廓作为一条封闭曲线,利用曲线采样点的有序集合来表示轮廓,然后将该集合视为有限维矩阵李群的元素,通过李代数的L2-范数在轮廓之间进行相似性度量,该方法计算出的点对关系优于形状上下文。

曲率尺度空间描述符[13]通过曲率变化来表示形状,即寻找轮廓上的曲率过零点来构建轮廓的曲率空间直方图,其实质是对关键局部信息进行编码,但是不同的轮廓可能会产生类似的曲率空间直方图。文献[14]利用离散曲率演化算法提取轮廓段作为局部信息,将其与从骨架中提取的全局信息相结合以表示形状。BCF(Bag of Contour Fragments)[15]是受BoW(Bag of Words)模型启发而被提出的新的形状表示,其首先将形状分解为轮廓片段,然后采用形状上下文描述符对每个轮廓片段进行处理并将其编码为形状代码,最后利用轮廓片段的形状代码的统计直方图来表示形状。文献[16]改进BCF方法,将骨架信息也作为形状特征,在BoF(Bag of Features)框架下引入适用于输入形状特征的可学习的池化函数,该池化函数是最大池化和平均池化的加权和,权重可以使用形状分类器通过梯度下降学习获得,该方法在轮廓识别方面获得了较高的识别率。文献[17]提出一种基于三角形质心距离(Triangular Centroid Distances,TCD)的形状描述符TCDs,使用TCDs形状描述符来解决部位之间的部分形状匹配问题,该方法在整体匹配和部位匹配中均获得了较好的效果。上述方法均能在一定程度上提高匹配效果,但是普遍存在的问题是提取到的轮廓段与人类视觉分割的轮廓段不一致。

2 轮廓精确匹配与分析方法

人类在利用轮廓识别物体时,通常先识别出大致轮廓的类别,然后通过判断其部位与该类别的部位是否相似来确定最终的轮廓类别。受此启发,本文提出一种基于最小点对成本的轮廓精确匹配与分析方法,该方法主要分3步实现:首先通过交互式学习类别的轮廓原型、部位原型及其轮廓分析参数;然后删除轮廓中大于点对比率阈值的轮廓段以获得该轮廓的主体轮廓,通过粗匹配获得轮廓的候选类别;最后分割出轮廓的部位,将其与候选类别的部位轮廓进行匹配找到相似度最高的候选类别,该类别即为最终的匹配类别。

2.1 交互式学习

本文通过交互式分割法学习不同类别的原型及轮廓分析参数,该阶段不仅学习类别整体轮廓原型,而且通过人工分割学习类别不同部位的轮廓原型,前者可用于类别轮廓的匹配,后者可用于类别部位的轮廓匹配。本文通过人工来选择需要学习的原型,在交互式学习中采用的是闭合轮廓,交互式学习的其中一个目标是学习类别及其部位在不同的主视角下的轮廓。考虑到基于最小点对成本的精确匹配方法需要使用轮廓图像,形状描述符就必须具有可恢复性,本文采用链码[18]作为形状描述符,其编码方式如图1所示,其中,P表示当前像素点,0～7用于编码不同的方向。

图1 链码的编码规则Fig.1 Coding rule of chain codes

交互式学习的另一个目标是学习类别的轮廓分析参数,主要包括点对曲率、点对面积距离比、部位端点最大距离、部位端点最小距离、部位最小面积比、部位最大面积比和部位类别名称等,其中,点对曲率和点对面积距离比的定义分别如下:

定义1(点对曲率) 令lp为轮廓上任意可连通2点之间的像素点数量,dp为2点之间的距离,则由这2点组成的点对曲率Cp可表示为:

(1)

定义2(点对面积距离比) 令p为轮廓上任意可连通2点之间的最短长度线段的边界点集,Ap为边界点集所围成的面积,dp为2点之间的距离,则由这2点组成的点对面积距离比Rp可表示为:

(2)

点对曲率、点对面积距离比、部位最小面积比和部位最大面积比本身就具有尺度不变性,而部位端点最大距离和部位端点最小距离与轮廓的尺寸相关,本文针对轮廓中最长的点对距离进行归一化处理,以获得参数的尺度不变性。交互式学习过程主要分为3步:

1)读入选定的类别图像,将其调整为固定尺寸的轮廓图像。

2)人工分割出轮廓中的不同部位。

3)根据分割出的轮廓图像学习类别的轮廓分析参数,并将类别轮廓和部位轮廓存储到知识库中。

图2所示为通过人工分割获得的类别部位分割效果。

图2 交互式工具获得的类别组件分割效果Fig.2 Segmentation effect of category componentsobtained by interactive tool

2.2 基于最小点对成本的精确匹配方法

IDSC、BCF、CPDH和基于形状上下文的匹配方法各有优点,但它们都不能实现精确匹配。本文提出一种基于最小点对成本的精确匹配方法,其通过计算2个边界图之间的最小成本对应关系[19]来实现精确匹配。基于最小点对成本的精确匹配方法将轮廓匹配转换为点分配,轮廓边界点集S1中任意一点与轮廓边界点集S2中的点都有一条边相连,边的权重即为点与点之间的匹配成本,其距离度量公式可表示为:

(3)

其中,pi和qj分别表示轮廓边界点集S1和S2中的像素点,C(pi,qj)表示2个轮廓之间的点对成本,本文将点对之间的欧氏距离作为点对的匹配成本。

为了满足人类视觉所具有的基本特性,还需对基于最小点对成本的精确匹配方法进行优化。首先对匹配轮廓进行归一化和镜像(无镜像、X镜像、Y镜像)处理,然后以轮廓的质心为旋转中心,将360°划分为n份,最后将每一次旋转后的图像与原型进行匹配,找到与待匹配轮廓具有最小匹配成本的原型。通过以归一化后的轮廓质心为基准进行旋转和镜像处理,使得优化后的最小点对成本匹配方法具备平移不变性、旋转不变性、镜像不变性和尺度不变性。

虽然基于最小点对成本的精确匹配方法可实现像素级的匹配,但是其无编码能力并且丢失了像素间的空间关系。人类在判断2个轮廓之间的相似性时不仅依赖轮廓之间的点对距离,还与轮廓中点与点之间的空间关系有关。基于形状上下文的匹配方法能有效捕获轮廓中点与点之间的空间关系,将形状上下文匹配方法融合到最小点对成本匹配方法中,使其具有局部分布编码能力。此时,轮廓之间的相似性由2个轮廓之间的点对距离和形状上下文成本表示,其距离度量公式可改写为:

Df=dmin+αdSC

(4)

其中,α表示形状上下文的匹配成本权重。式(4)的距离度量公式体现出需要找到与待匹配轮廓具有最小点对距离、边界点集分布最相似的轮廓原型。

虽然基于最小点对成本的精确匹配方法在引入形状上下文距离后获得了局部分布编码能力,但同时也导致异常点多时匹配效果差、对轮廓细节的变化较敏感等问题。为了解决异常点多时匹配效果差的问题,本文在进行形状上下文匹配时只选取在最小点对成本匹配中已配对的点集,这样可以避免异常点对形状上下文匹配的影响。与特征匹配方法相比,基于最小点对成本的精确匹配方法能以可视化的方式呈现出符合观察习惯的匹配结果。

2.3 轮廓精确匹配与分析

人类在进行轮廓匹配时通常不考虑相似度低的轮廓而主要关注大致相似的轮廓。受此启发,在实际的轮廓匹配处理中,往往采用预处理的方式找出大致相似的轮廓,然后再进行轮廓精确匹配,这样可以有效提升匹配速度。限于篇幅,本文主要讨论轮廓精确匹配阶段,预处理阶段不做赘述。

虽然基于最小点对成本的精确匹配方法已经避免了异常点的影响,但对轮廓细节变化比较敏感的问题并未解决,如果直接对轮廓进行匹配将达不到预期效果。受到人类识别物体的启发,本文在该方法中引入粗到精的二级匹配策略,该策略与文献[14-15,20]中的匹配策略有相似之处,都是将轮廓分割为轮廓段,从而降低对轮廓细节变化的敏感性,但文献[14-15,20]中的匹配策略提取的轮廓段往往与人类在进行轮廓识别时分割出的轮廓段不一致。

粗到精的二级匹配策略的第一级为粗匹配,第二级为精匹配。粗匹配主要实现类别主体轮廓的匹配,具体过程为:首先对轮廓进行处理,删除点对曲率大于阈值的轮廓段,获得稳定的主体轮廓;然后通过基于最小点对成本的精确匹配方法寻找相似的原型,将满足阈值要求的轮廓原型的类别作为待匹配轮廓的候选类别。精匹配可以认为是对粗匹配分析结果的进一步优化,其仍然采用基于最小点对成本的精确匹配方法,具体过程为:首先对每一种候选类别进行轮廓分析获得轮廓的部位;然后对其部位进行匹配;最后将候选类别的部位匹配成本和粗匹配成本平均值作为该候选类别的匹配成本,将相似度最高的候选类别作为最终的匹配结果。无论是粗匹配阶段的主体轮廓还是精匹配阶段的部位轮廓,相比于整体轮廓而言已经极大降低了轮廓复杂性,从而利于形状上下文捕获边界点之间的空间关系。

图3所示为轮廓分析的处理过程,其中,第1行是待匹配的轮廓图像,从左到右为原始轮廓、主体轮廓、轮廓分割图像和轮廓分析结果,第2行是知识库中的一些轮廓原型(鸭子、鸟类、牛、蝴蝶)的主体轮廓,最后一行是待匹配的主体轮廓和第2行中原型主体轮廓的点对匹配图像,所有图片来源于Animal数据集(http://cloud.eic.hust.edu.cn:8071/～xbai/softwares.html)。轮廓分析是指分割出轮廓中的部位并识别出轮廓类别及其部位类别。本文将原型知识库和二级匹配策略的最小点对成本匹配方法应用于轮廓分析,提出一种基于最小点对成本的轮廓精确匹配与分析算法,其伪代码如算法1所示。首先通过粗匹配找到相似的原型,并将满足阈值要求的轮廓原型的类别作为待匹配轮廓的候选类别;然后处理每一个候选类别,假定该候选类别即为轮廓类别,从原型知识库中读取该类别的轮廓分析参数,随后利用分析参数对轮廓进行分割,找出符合要求的部位,如图3第1行第3幅图所示;最后将部位与原型库中的该候选类别的部位轮廓原型进行匹配,并将该候选类别的主体轮廓匹配成本和部位轮廓匹配成本的平均值作为候选类别的匹配成本。将候选类别中匹配成本最低的类别及其部位分割和识别结果作为最终的轮廓分析结果,如图3第1行第4幅图所示。

图3 基于最小点对成本的轮廓匹配与分析算法效果Fig.3 Contour matching and analysis algorithm effect based on minimum point-pair cost

算法1基于最小点对成本的轮廓精确匹配与分析算法

输入图像Iin,原型知识库PK,点对曲率阈值h

输出轮廓类别Cc,组件类别Cp

步骤1获得轮廓图像。

步骤2从知识库中读取轮廓原型信息。

步骤3删除轮廓中点对曲率大于阈值h的轮廓线段,并将其余轮廓段作为轮廓主体。

步骤4将主体轮廓与原型的主体轮廓进行匹配,并使用符合要求的原型类别作为候选类别。

步骤5处理每个候选类别并使用候选类别的分析参数分析轮廓。

步骤6将分割出的组件与候选类别的组件原型进行匹配以获得匹配成本。

步骤7将候选类别的主体匹配成本和组件匹配成本的平均成本作为候选类别的匹配成本。

步骤8轮廓类别Cc为候选类别中匹配成本最低的类别,该候选类别对应的组件匹配结果即为轮廓的组件类别Cp。

3 实验结果与分析

为了验证匹配方法的有效性,选取MPEG-7[21]数据集和Animal[14]数据集作为实验数据集。首先,在MPEG-7数据集上比较不同匹配方法对刚性物体的识别率;然后,在Animal数据集上比较不同匹配方法对非刚性物体的识别率。考虑到人类可能有额外的机制来处理遮挡和扭曲的情况,在对非刚性物体的识别任务中仅选用通过轮廓即可识别出其类别的图像作为数据集,图像全部选自Animal数据集。实验在微软Windows 10(64位)操作系统、酷睿i7-6500U CPU 2.5 GHz频率、内存8 GB的计算机上完成,采用分类准确率作为评价指标。

表1所示为MPEG-7数据集中的实验结果,从表1可以看出,对于刚性物体,本文匹配方法、SC[10]、BCF[15]、CSM[12]、TCDs[17]和BoSCP-LP[16]方法均有较高的识别率,这是由于刚性物体的类内差异较小。

表1 MPEG-7数据集上不同匹配方法的识别率对比Table 1 Comparison of recognition rates of differentmatching methods on MPEG-7 dataset

图4显示了部分类别的部位识别结果,表2所示为Animal数据集中部分类别的粗匹配、精匹配、组件分割和组件识别的识别率。

图4 Animal数据集上部分类别的组件识别结果Fig.4 Component recognition results of some categories on Animal dataset

表2 Animal数据集上部分类别的实验结果Table 2 Experimental results of some categories on Animal dataset

从图4和表2可以看出,精匹配的识别率相比粗匹配有一定提升,说明部位识别在一定程度上有利于整体轮廓的识别,鸭、蝴蝶、牛的类内轮廓变化不大,而鸟、鳄鱼有着较大的类内轮廓差异,类内差异小的类别有较高的识别率,其中,鸟的精匹配准确率较高是由于其增加了部位的原型数量,而鳄鱼在未增加部位原型数量的情况下识别率显著降低。图4中第1行最后一幅鸟类部位分割图由于脚与尾巴相似而识别错误,第4行最后一幅蝴蝶部位分割图中尾巴曲率不满足要求而没有被分割出来,第5行鳄鱼的嘴、尾、脚有时很相似导致识别时出错。上述实验结果表明各方法均有较高的部位分割与识别准确率。

表3所示为Animal数据集上本文粗匹配、精匹配、SC方法[10]、BCF方法[15]、CSM方法[12]、TCDs方法[17]和BoSCP-LP方法[16]的实验结果对比。从表3可以看出,对于类内差异较大的鳄鱼,所有匹配方法的识别率均较低,这表明轮廓细节的变化对匹配结果有较大影响。粗匹配的识别率与其他匹配方法相近,而精匹配具有较高的识别率,这说明粗到精的策略有利于轮廓识别。基于形状上下文的匹配方法虽然可以对轮廓边界点之间的关系进行编码以提高对轮廓的识别效果,但是鸭子脖子和鳄鱼尾巴在整个轮廓中所占比例较大且相对于轮廓主体位置不固定,因此该方法对鸭子和鳄鱼的识别率较低。TCDs形状描述符本质上仍然是傅里叶描述子,不能有效区分类间的差异,不同类别轮廓的傅里叶描述子可能极为相似,TCDs对于类内形变较大的鳄鱼识别率较低,该形状描述符适用于开放轮廓段间的匹配。BCF、CSM和BoSCP-LP在不同类中均有较高的识别率,但是BCF、BoSCP-LP获得的轮廓段并非人类视觉分割结果[15],BCF和CSM也未识别出类别的部位。总体而言,轮廓中部位的位置变化不利于轮廓识别,本文提出的两级匹配策略可有效降低部位的位置变化对轮廓识别结果的影响,并且能够识别出其部位的类别。

表3 Animal数据集上不同匹配方法的识别率对比Table 3 Comparison of recognition rates of different matching methods on Animal dataset

4 结束语

针对物体识别中轮廓精确匹配与部位识别问题,本文通过交互式分割法学习不同类别的轮廓原型数据和轮廓分析参数,构建类别轮廓原型知识库,提出一种可以实现精确匹配的最小点对成本匹配方法,其能有效地从轮廓原型知识库中找到与待匹配轮廓具有最小点对距离、边界点集分布最相似的轮廓原型。多数已有匹配方法对类内轮廓的差异比较敏感,本文匹配方法引入粗到精的二级匹配策略,从而降低匹配方法对轮廓细节变化的敏感性。在此基础上,结合类别轮廓原型知识库和最小点对成本匹配方法,提出一种基于最小点对成本的轮廓精确匹配与分析方法,该方法可以识别出轮廓类别及其部位类别,具有平移不变性、旋转不变性、尺度不变性和镜像不变性等特点。实验结果表明,基于原型匹配的物体识别策略具有可行性,本文所提方法能实现精确匹配并在部位分割、轮廓识别和部位识别方面具有较高的准确率。

在二维空间采用基于原型匹配的物体识别方法时仍然存在一定不足,例如,由于视点的不同,三维物体的轮廓经过投影变换后有无数种二维形状,这不仅增加了二维轮廓的原型数量而且也提高了二维轮廓匹配的难度。此外,从二维轮廓中获得的部位和整体关系与三维轮廓中的部位和整体关系存在差异,更好的基于原型匹配的物体识别策略是模拟人脑构建出不同类别的三维原型知识库,然后通过三维轮廓匹配与分析方法来进行物体识别。下一步将通过上述策略提高物体识别的效率和准确率。