向 敏 王军伟

（1.海军装备部信息系统局 北京 100071）（2.武汉数字工程研究所 武汉 430205）

1 引言

形状上下文（shape contexts）是一种经典的轮廓描述子，许多研究工作是在它基础之上的改进或推广。然而，这些方法中的平面分割、区域点统计等处理去除了轮廓顺序关系这一全局形状特征，而且会造成量化误差以及参数不易选取等问题。针对这些问题，本文提出一种新的上下文描述子，直接根据轮廓点的顺序将上下文相对位置信息转化为特征向量。这样不仅避免了计算直方图时额外的计算量、可能造成的量化误差以及参数不易选取等问题，同时还通过轮廓的顺序关系显著增强了描述子中所含有的全局形状信息。

2 研究现状

形状上下文（shape contexts，SC）［1］是一种经典的轮廓描述子。它从轮廓点之间的空间位置关系出发，几何意义明确，直观、简单、易于计算、描述性强，能够取得较好的形状匹配效果。由于其优异的性能，它已经成为形状描述子研究工作的一个里程碑，是近二十年来该领域所取得的最重要和最具影响力的研究成果之一。

不少研究工作试图在原始的形状上下文描述子的基础之上做出优化、改进或推广，进一步挖掘这种形状特征在性能上的潜力。内距离形状上下文描述子（IDSC）［3］就是在SC基础上做出的经典推广性工作。文献［3］认为，对于非刚性物体（如人或其他动物）来说，在肢体变化（articulation）下，轮廓点之间的欧氏距离会发生显著变化，不是一种稳定的形状特征。为此，文献［3］提出一种新的轮廓点距离计算方式：内部距离（inner-distance），其定义为从物体的内部连接轮廓上两个点之间最短路径的长度。用内部距离代替欧氏距离，发明了一种新的描述子：内部距离形状上下文（inner-distance shape contexts，IDSC），该描述子最突出的性能优势是能够取得肢体不变性（articulat ioninvariance）。此外，IDSC在复杂形变下的区分能力也比较突出。

还有人注意到SC在统计各个区域所包含的轮廓点数时，将某个轮廓点赋予某个区域，这个过程本质上是对轮廓点在平面上的位置信息进行量化，即位置不同但都被某个区域所包含的点，它们的处理结果是完全相同的。假如某个轮廓点位于两个相邻区域的分界线附近，则轮廓点位置微小的扰动或误差就会得到完全不同的量化结果，这显然是不合理的。为此，Liu和Chen对SC进行软化改造，提出了软形状上下文描述子（soft shape contexts，SSC）［4］，其基本思路是利用概率式的软判决思想来计算两个SC描述子之间的相似度，相当于对原始的SC特征进行低通平滑滤波，可从一定程度上克服直方图相邻区域的量化误差。韩敏和郑丹晨提出模糊形状上下文特征（fuzzy shape context）［5］，该方法利用软判决思想，定义直方图每个栅格的中心，并根据一个隶属度函数计算每个轮廓点位于不同区域的概率，在此基础上获得一个模糊的直方图特征，相对于SC二值的量化方法能够更加精确地描述采样点的空间分布情况。Ling和Okada基于填土距离（earth mover's distance，EMD）提出了一种直方图距离度量的新方法［6］，可有效改善特征距离计算和形状匹配的效果。

另外，还有不少研究是在上下文思想基础之上的推广。Mori等［7］提出了一种广义的形状上下文特征（generalized shape context），用轮廓点的切向量代替采样点，进而用每个区域内切向量的主方向而不是轮廓点的数量来表示轮廓的空间分布。Roman-Rangel等［8］提出方向直方图形状上下文特征（histogram of orientation shape context），借鉴自然图像中经典的SIFT算法［9］的思想改进SC描述子，通过一个高维度的直方图来准确地表示目标形状的特征。Daliri和Torre［10］提出了一种将形状上下文描述子与符号串表示（string of symbols）相结合的方法，使用Procrustes分析方法来校准两个形状的对应关系，提高了形状匹配的效果。Kirkegaard和Moeslund［11］利用形状上下文的思想来表示三维物体的表面特性，提出了一种称为调和形状上下文（harmonic shape contexts）的描述子。Huang和Trivedi［12］将SC描述子推广到三维情况下对人体进行表示，提出了一套人体姿势分析和跟踪方法。Grundmann等［13］结合二维空间和时间信息，提出了一种三维形状上下文描述子，并结合距离变换技术（distance transform）进行行为识别。Kholgade和Savakis［14］针对视频中的人体行为识别问题，提出了一种四维的时空形状上下文描述子（spatiotemporal shape context）。

3 改进的形状上下文描述子

3.1 问题分析与改进思路

SC将轮廓点分配到各个区域中去，这种处理方式造成形状信息分散，破坏了轮廓原本具有的全局形状特征。针对SC的大部分改进方法或者是将二维直方图推广至更高维，或者是在原有直方图的基础之上进行一些后处理操作。这些改进方法不能从根本上解决问题，描述子性能的提升有限，而且还使得上下文描述子的计算变得更加复杂。

本文方法的基本思想是：在获取了所有轮廓点的相对空间位置信息（即上下文）后，直接通过轮廓的顺序关系，将这些上下文信息组合起来，转化为一个特征序列。这样做的优势在于：1）对于轮廓采样点来说，轮廓的顺序关系是原本就存在的信息，容易加以使用，而且可以与轮廓点之间的上下文特征有机相融合。2）上下文信息组合在一起的思想与SC描述子中区域分割的思想正好相反，组合的思想可以有效地保留轮廓的全局特征，体现形状整体上的信息。3）组合比分割简单，将局部组合成整体基本上不需要参数控制，将整体分割为局部却需要确定分割的粗细粒度，也就是确定形状上下文控制分割的那些参数。

3.2 改进的上下文描述子及其性质

设轮廓采样点序列为P=｛pi｝（i=1，2，…，N），其中N为采样点序列的长度（即轮廓采样点的数量）。假设pi为目前的参考点（referencepoint）。与SC描述子一致，以参考点pi为坐标原点，以形状轮廓P在参考点pi位置处的切线li为x轴，建立一个相对的坐标系，并计算除参考点pi以外的其他N-1个轮廓点在该坐标系中的相对坐标：

这样，就得到了其他N-1个轮廓点相对于参考点pi的相对坐标数据。与SC不同，本文使用一种全新的策略对这些相对坐标数据进行处理。由于除参考点pi以外的其他N-1个轮廓点在形状轮廓P上存在自然的先后顺序关系，我们直接根据它们在轮廓上的顺序关系，将式（1）所示的相对坐标数据fi，j排列成一个序列的形式，如以下式（2）所示：

需要注意的是，式（2）所定义的特征序列的每一个分量fi，j都是一个二元坐标数据，并非标量。

定义1 式（2）所定义的相对坐标序列Fi是在形状轮廓P上的、针对参考点pi所定义的保持轮廓顺序关系的形状上下文描述子（contoursequential order-preservedshapecontexts，CSOSC）。

图1给出了本文所定义的上下文描述子的示意图。

图1 保持轮廓顺序关系的上下文描述子

本文提出的描述子仍然建立在上下文信息基础之上，这使得它继承了SC描述子的线性变换不变性。为了使得所定义的上下文描述子满足尺度不变性，采用局部归一化（localnormalization）操作。将形状轮廓P上每一个轮廓点对应的上下文描述子Fi按照顺序排列，组成一个尺寸为（N-1）×N的矩阵：

则对矩阵E的每一行分别进行归一化：

其中，‖‖fjt表示二元的上下文坐标数据的模，即。

式（2）所定义的上下文相对坐标序列Fi中包含了除参考点pi以外的所有其他N-1个轮廓点的相对坐标数据。如果采纳所有轮廓点的数据，会导致序列Fi对形状轮廓P的描述过于精确和细致，从而对形状的局部变形过于敏感。为了在描述的准确性和对局部形变的不敏感性之间取得一个很好的折中，有效提高描述子对于噪声和局部形变的鲁棒性，对式（2）所定义的描述子的精确性上进行一定程度的弱化。

具体的，采用平滑化（smoothing）处理技术。具体过程如下。

根据式（2），原始的轮廓描述子可表示为

它是一个包含N-1个元素的序列，其中的任意一个分量 fij（j=1，2，…，N-1）是特征向量Fi中的第j个分量。将从1到N-1的正整数序列1，2，…，N-1均匀的划分为若干个互不相交的子序列［1，k］、［k+1，2*k］、［2*k+1，3*k］、…，其中k为一个预设的正整数。对于每一个子序列，分别计算特征向量中相应的一段分量的均值：

其中j=1，2，…，M，j表示所划分出来的M个子序列的标号，M的值由N和k的值确定，。这M个均值按顺序构成一个新的序列：

特征向量Gi就是对原始的描述子Fi经过平滑化技术处理以后的结果。经过平滑化处理，不仅使得原始描述子的特征维度得以降低，而且还有效提高了描述子对于轮廓噪声和局部形变的鲁棒性。

对于形状轮廓P上的每一个采样点pi（i=1，2，…，N），我们都可以将其作为参考点，基于相同的定义方式计算出一个由式（7）所表示的轮廓描述子Gi（i=1，2，…，N）。将这N个描述子对应的特征向量按照轮廓点的顺序排列起来，可以得到一个M×N尺寸的矩阵：

该矩阵是针对形状P定义的总的特征，矩阵Γ的第i列对应着轮廓P上某一点pi的形状描述子。

4 形状匹配与相似性度量

设两个形状P、Q对应的轮廓采样点序列为P=｛pi｝（i=1，2，…，N）和Q=｛qj｝（j=1，2，…，N）。在匹配这两个序列之前，首先计算任意一对分别来自不同形状P、Q上的采样点之间的不相似度或匹配代价c（pi，qj）（i=1，2，…，N；j=1，2，…，N）。该匹配代价定义为两个点pi、qj对应的描述子特征Gi与Gj之间的距离。由于式（7）定义的特征向量中的每一个分量不是标量值，而是二元的上下文坐标数据，这里采取一种直观的方式来比较两个坐标序列之间的差异：

计算获得任意一对轮廓点之间的匹配代价后，使用动态规划算法（DP）来求解寻找轮廓点序列P、Q之间对应关系的优化问题。

在基于动态规划算法所求得的成对形状相似性度量值基础上，进一步使用形状复杂性（shape complexity）因子进行调整。对于形状轮廓P=｛pi｝（i=1，2，…，N），假设已经获得了如式（8）所示的尺寸为M×N的特征矩阵Γ（且已经经过了式（4）的尺度归一化处理），则形状P的形状复杂性C（P）可由如下公式定义：

其中，xˉt与 yˉt分别表示 N个二元坐标的 x坐 标 与 y坐 标 的 均 值 ，即，。

5 实验结果与分析

为了验证本文所提出的保持轮廓顺序关系的上下文描述子的有效性，在两个标准形状测试集：MPEG-7［15］和 Kimia99［16］上进行了形状检索实验。在相关实验中，每个形状轮廓采样点数N的取值均为100。

5.1MPEG-7数据库

表1给出了CSOSC描述子和其他描述子在MPEG-7数据库上的检索精度。从结果来看，同样是基于上下文信息，本文描述子的检索性能明显超过了已有基于上下文信息的描述子。即使不使用形状复杂性因子改善形状相似性度量结果，CSOSC也能够取得最高的检索准确率，检索精度（88.75%）遥遥领先。准确率排在第二的方法是方面形状上下文描述子［17］，该方法相当于把SC和IDSC两种经典而有效的形状特征进行了信息融合，但即使如此，其结果也与本文的方法存在一定差距。

表1 不同的上下文方法在MPEG-7数据库［15］上的检索精度（bull'seye）

5.2 Kimia99数据库

表2列出了CSOSC描述子与一些典型的形状描述子在Kimia99数据库上的检索结果。从表中可以看出，本文的方法能够取得极其优异的检索精度，与最近的一些方法相当，与目前最好的方法——符号化表示［10］相比，仅仅在最后两位数字上存在一定差距。

5.3 噪声环境下的形状匹配与检索

为了验证本文的方法在噪声环境下的性能，本节开展带有噪声的形状轮廓检索实验。在Kimia99数据库的基础上，人为地对该数据库中的形状轮廓添加一些高斯噪声，然后对这些带有噪声的形状进行匹配与检索。检索精度的计算方式与在原始的Kimia99数据库上的评价方式一致。检索结果如表3所示。从表中可以看出，随着噪声变得越来越严重，检索准确率有一定下降，但仍可以接受，表明本文的方法对于轮廓噪声具有较高的鲁棒性。

表2 不同方法在Kimia99数据集［16］上的检索结果

表3 本文的方法在受到噪声污染的Kimia99数据集上的检索结果

本文的方法对轮廓噪声具有较高的鲁棒性。造成这一性能优势的原因有两个：1）本文的方法有效融合了轮廓顺序关系，而轮廓顺序信息是一种全局性的形状特征，对噪声和局部轮廓形变具有鲁棒性；2）本文的方法采用了平滑化处理技术，在降低特征向量维度的同时，也有效提高了本文的描述子对于轮廓噪声和局部形变的鲁棒性。

6 结语

针对经典的形状上下文描述子在特征定义与计算过程中存在的缺陷，本文抓住问题的本质——平面分割与区域点数统计，通过一种全新的方式组织上下文信息，不仅简化了描述子的定义和计算过程，而且将轮廓的顺序关系自然的添加进描述子中，增强了描述子的全局形状信息，有效提高了上下文描述子的表达和描述能力。实验表明，本文提出的轮廓描述子在各大、小型标准形状测试集上均能够取得优异的形状检索效果，检索精度不仅显著高于已有的上下文式的描述符，而且与目前效果最好的形状描述子接近。