形状特征的描述识别是模式识别和计算机视觉的研究热点，广泛应用于基于内容的图像检索、空间数据的融合更新、图像分割与识别、机器人视觉等领域。形状是高级别的视觉信息，比颜色、纹理等更具有视觉表征性，是人类通过感知认识世界的关键信息之一^[1]。如何让计算机模拟人类高效、快速的识别形状，是目前亟需解决的问题。

现有的形状相似性描述与识别方法主要包括基于边界的形状描述模型和基于区域的形状描述模型两类。基于边界的形状描述模型主要有Hausdorff距离^[2]、形状上下文描述法SC(shape context)^[3]、内距离形状上下文描述法IDSC(inner-distance shape context)^[4]、多尺度形状上下文方法MSC(multiscal shape contest)^[5]、曲率尺度空间CSS(curvature scale space)^[6]、带符号的三角形面积形状描述法TAR(triangle area representation)^[7]、正切空间^[8]、顺序特征描述^[9]、不变多尺度描述^[10]、距离内比^[11]和基于变换域的形状描述法^[12-13]。基于边界的形状描述模型仅利用形状的边界信息，忽略形状的内部区域，对形状的形变比较敏感。基于区域的形状描述模型主要有基于距的形状描述^[14]、基于骨架的形状检索方法^[15]、惯性轴描述法(axis of least inertia)^[16]、TSS(tensor scale sector descriptor)^[17]和基于傅里叶变换的区域形状描述^[18]。基于区域的形状描述模型利用形状的所有特征信息，但对形状细节信息的描述能力不足。

针对基于边界和基于区域的形状描述模型的不足，本文通过形状主方向和形状顺序特征描述，拓展用于空间方位关系描述的F直方图模型^[15]，提出基于F直方图的形状全方向顺序特征描述方法。

1 F直方图模型

F直方图^[15]通过度量命题“对象A在对象B的α方向上”的真实性，描述一对二维对象A、B的空间方位关系，如图 1所示。在任一方向上，F直方图通过一组方向线与对象相交段的力作用关系，计算一个目标相对另一个目标在该方向上的力分布，快速评估两个目标间的方位关系。如图 1所示，A、B表示二维对象，F直方图的方向线Δ_α(v)，α为方向线Δ_α(v)与参考方向$ \mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( 0 \right) $的夹角。方向线通过两个对象时，会与两个对象相交，产生两个对象分割段的集合A_α(v)=A∩Δ_α(v)和B_α(v)=B∩Δ_α(v)。图 1中方向线与对象A、B相交的对象分割段集合分别为A_α(v)={x, e}、B_α(v)={z}。

对象A、B在某条方向线上的力就是该条方向线上各对象分割段之间的作用力，如图 1中对象分割段z、x之间的力为

$ \left\{ \begin{array}{l} f\left( {x, y, z} \right) = \smallint _{_{y + z}}^{^{x + y + z}}(\smallint _{_0}^{^z}\delta \left( {u-w} \right){\rm{d}}w){\rm{d}}u\\ \delta \left( {u-w} \right) = \frac{1}{{{{\left( {u-w} \right)}^2}}} \end{array} \right. $

(1)

式中：x、z为对象分割段长度，y为对象分割段间的距离，u、w分别为对象分割段x、z上的点。

若某条方向线与对象相交于多段，即$ {A_\alpha }\left( v \right) = \bigcup\limits_{i \in 1, 2, \cdots, n} {{I_i}} $、$ {B_\alpha }\left( v \right) = \bigcup\limits_{j \in 1, 2, \cdots, n} {{J_j}} $。则该条方向线上两个对象间的作用力为

$ F(\alpha, {A_\alpha }\left( v \right), {B_\alpha }\left( v \right)) = \sum\limits_{i \in 1, 2, \cdots, n, j \in 1, 2, \cdots, n} {f({d_{{I_i}}}, D_{_{{I_i}{J_j}}}^{^\alpha }, {d_{{J_j}}})} $

对任一角度α∈(0, 2π)做一组方向线，计算每条方向线上两对象间对象分割段的作用力，所有方向线上对象分割段间作用力的和，为该方向的力值。设方向$ \mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( 0 \right) $为初始方向，从初始方向开始，每次间隔特定角度d_angle做一组方向线，计算该方向的力值，回到初始方向为止，得到两对象的力直方图。

2 形状全方向顺序特征描述 2.1 全方向顺序特征描述量

本文在F直方图的基础上，通过对象形状主方向和形状顺序特征描述，提出一种新的对象形状描述模型。在任意特定方向下，求出与形状轮廓最外侧相交的两条方向线，作为边界线。如图 2中最外侧两条方向线为边界线。利用n条方向线将两条边界线之间的部分平均分割为n+1等份，如图 2中9条方向线将边界线之间的部分平均分割为10份。

某一条方向线与对象相交于m段(m≥1)，如图 2中方向线L₁与对象相交于ab、cd两段，方向线L₂与对象相交于mn一段。同一条方向线上的对象分割段均为直线，不存在形状差异，对象分割段之间有前后顺序。假定方向线为一维坐标轴，规定该坐标轴的正方向，图 2中方向线的箭头方向为正方向。图 2中方向线L₁的对象分割段cd领先于段ab，即段cd中任一点u均领先于段ab中任一点v，设函数φ(u-v)描述点u、v的顺序关系，函数φ(u-v)公式为

$ \left\{ \begin{array}{l} \varphi \left( {u-v} \right) = 1, u > v\left( {即u领先于v} \right)\\ \varphi \left( {u-v} \right) = 0, u \le v \end{array} \right. $

(2)

通过式(2)替换F直方图式(1)中的函数δ(u-w)，则分割段ab与分割段cd之间所有点的顺序关系描述即顺序特征描述量f为

$ f\left( {ab, cd} \right) = \smallint _{_{y + z}}^{^{x + y + z}}(\smallint _{_0}^z\varphi \left( {u-v} \right){\rm{d}}v){\rm{d}}u $

(3)

式中：x、z为分割段cd、ab的长度，u、v为分割段cd、ab上的点。y为点c与点b坐标值之差。当点c领先于点b时，y>0；当点c与点b重合时，y=0；当点b领先于点c时，y < 0。

更一般地，假设一条方向线上的对象分割段为I₁、I₂，则式(3)可表示为

$ f({I_2}, {I_1}) = \smallint _{_{y + z}}^{^{x + y + z}}\left( {\smallint _{_0}^{^z}\varphi \left( {u-v} \right){\rm{d}}v} \right){\rm{d}}u $

(4)

式中：x为段I₁的长度，z为段I₂的长度。y为段I₁的起点坐标与段I₂的终点坐标之差。u为段I₁上的点，v为段I₂上的点。

当某条方向线上的对象分割段多于两段时，假设该条方向线上的对象分割段为I₁, I₂, …, I_n，n≥2，则公式为

$ f = \sum\limits_{i \in 1, 2, \cdots, n} {\sum\limits_{j \in 1, 2, \cdots, n} {f({I_i}, {I_j})\;\;\;\;i \ne j} } $

(5)

当方向线上只有1个分割段时，如图 2中方向线L₂上的段mn所示。此时可认为段mn与段m′n′完全重合，根据式(4)可得

$ f(mn, m'n') = \smallint _{_{y + z}}^{^{x + y + z}}\smallint _{_0}^{^z}\varphi \left( {u-v} \right){\rm{d}}v{\rm{d}}u $

(6)

式中：x、z为段mn、m′n′的长度，x=z; y为m-n′即y=-z。

当方向线上只有一个对象分割段I时，则式(6)可表示为

$ f\left( I \right) = \smallint _{_0}^{^x}\smallint _{_0}^{^x}{\rm{d}}v{\rm{d}}u\;\;\;\;\;\;u > v $

(7)

式中：x为对象分割段I的长度，u、v为分割段I上的点。

通过式(5)、(7)计算出所有n条方向线的顺序特征描述量{f₁, f₂, …, f_n}。并计算出通过对象形状重心的方向线上的顺序特征描述量f_cen，如图 2中虚线所示。为使形状顺序特征描述量满足尺度不变性，令每条方向线的顺序特征描述量f_n均除以f_cen，得出该条方向线上的形状特征描述分量f_n。在特定方向下的形状顺序特征描述量公式为

$ \left\{ \begin{array}{l} F = \left\{ {{{\overline {f_1}}}, {{\overline {f_2}}}, \cdots ,{{\overline {f_n}}}} \right\}\\ {{\overline {f_n}}} = \frac{{{f_n}}}{{{f_{{\rm{cen}}}}}} \end{array} \right. $

(8)

式中：f_n为第n条方向线的顺序特征描述量，f_cen为通过重心的方向线上的顺序特征描述量。

从初始方向$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( 0 \right) $开始，每次间隔特定角度d_angle，利用方向线对形状进行分割，计算形状特定方向$ \mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( m \right) $上的顺序特征描述量$ F\left( {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( m \right)} \right)$，直到旋转回初始方向$ \mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( 0 \right) $为止，共有N=360/d_angle分割方向。间隔角度d_angle必须能被360整除，当间隔角度d_angle为1，分割方向N值最大为360。形状特定方向$ {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( m \right)}$的顺序特征描述量$ F\left( {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( m \right)} \right) $为

$ F\left( {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( m \right)} \right) = \{ {{\overline {f_1}}}\left( {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( m \right)} \right), {{\overline {f_2}}}\left( {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( m \right)} \right), \cdots, {{\overline {f_{\text{n}}}}}\left( {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( m \right)} \right)\} $

N个分割方向的形状顺序特征描述量共同构成形状的全方向顺序特征描述量F：

$ F = \left\{ {F\left( {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( 0 \right)} \right), F\left( {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( 1 \right)} \right), \cdots, F\left( {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( {N-1} \right)} \right)} \right\} $

从初始方向0°开始，每次间隔1°，分割图 2中的形状，10°方向和60°方向的分割示意图如图 3所示。图 4为图 2形状的全方向顺序特征描述三维示意图。

2.2 形状相似性度量

计算两个形状的相似性时，待匹配形状A和B可能发生过旋转，导致各分割方向不对应。为了确定对应的分割方向，需计算形状A、B的最小惯性轴，该轴不随形状转换而改变，唯一保存了形状的主方向。形状主方向位于通过形状重心且倾角为θ的直线上，倾角θ公式为^[16]

$ \theta = \frac{1}{2}\arctan \frac{{2{u_{11}}}}{{{u_{20}}-{u_{02}}}} $

式中u₁₁、u₀₂、u₂₀为形状的p+q阶中心矩。图 5中Hammer 15、5的主方向为带箭头的实线所示。

主方向可能会因形状的不均匀形变，产生一定改变，导致两个待匹配形状的对应分割方向出现误差。为了准确确定形状A、B的对应方向，以形状主方向为参考，计算两个形状主方向附近分割方向的顺序特征描述量差异，将差异最小的两个分割方向作为形状A、B的对应方向，图 5中带箭头的虚线表示主方向附近的分割方向。

设形状A的某一分割方向为$ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( a \right) $，则形状A分割方向$ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( a \right) $的顺序特征描述量$ {{F}_{A}}\left( \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( a \right) \right) $为$\left\{ \overline{{{f}_{A1}}}\left( \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( a \right) \right), \overline{{{f}_{A2}}}\left( \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( a \right) \right), \cdots, \overline{{{f}_{An}}}\left( \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( a \right) \right) \right\} $，形状B的某一分割方向为$ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( b \right)$，则形状B分割方向$ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( b \right) $的顺序特征描述量$ {{F}_{B}}\left( \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( b \right) \right) $为$ \left\{ \overline{{{f}_{B1}}}\left( \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( b \right) \right), \overline{{{f}_{B2}}}\left( \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( b \right) \right), \cdots, \overline{{{f}_{Bn}}}\left( \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( b \right) \right) \right\} $，则顺序特征描述量间的差异度为

$ D=\frac{1}{n}\sum\limits_{x=1}^{n}{\left| \overline{{{f}_{An}}}\left( \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( a \right) \right)-\overline{{{f}_{Bn}}}\left( \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{i}\left( b \right) \right) \right|} $

(9)

设形状A、B的对应方向为$ \mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( a \right) $、$ \mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftarrow$}} \over i} \left( b \right) $，从对应方向开始，通过式(9)计算形状A、B各对应分割方向的顺序特征描述量差异度，得到{D₀, D₁, …, D_N-1}，形状A、B全方向顺序特征描述量差异度为

$ {D_{{\rm{all}}}} = \frac{1}{N}\sum\limits_{i = 0}^{N-1} {{D_i}} $

形状A、B的形状相似度S为

$ S = 1-{D_{{\rm{all}}}} $

2.3 形状全方向顺序特征描述的性能分析

形状的全方向顺序特征描述满足尺度、平移和旋转不变性。

性质1  尺度不变性：形状全方向顺序特征描述使每条方向线上的顺序特征描述量f_n，均除以通过形状重心的方向线上的顺序特征描述量f_cen，如式(8)所示，得到形状该条方向线上的形状特征描述分量$ \overline {{f_{\rm{n}}}} $，该描述分量不随形状尺度变化而改变，保证本形状特征描述满足尺度不变性。

性质2  平移不变性：形状全方向顺序特征描述利用各分割方向下的方向线对形状进行分割，计算每条方向线上对象分割段之间的顺序特征描述量，与形状特征点的绝对位置无关，不会因形状的平移产生变化，保证本形状描述满足平移不变性。

性质3  旋转不变性：形状全方向顺序特征描述通过形状主方向确定两个待匹配形状的对应方向，形状主方向具有旋转不变性，保证本形状描述满足旋转不变性。

形状全方向顺序特征描述可以通过调节分割方向的数量和方向线的数量，决定形状整体和细节信息的描述程度，对形状进行多级描述。分割方向和方向线越多，越注重形状的细节相似性。分割方向和方向线越少，越注重形状的整体相似性。

形状全方向顺序特征描述可以精确描述对象形状的整体特征和细节信息，兼顾形状的边界和区域信息，对发生形变和扭曲的形状具有更强的识别能力，同时拓展了F直方图模型的空间信息描述能力，使F直方图可以描述空间方位关系和形状信息。

2.4 形状全方向顺序特征描述的时间复杂度分析

形状全方向顺序特征描述的时间复杂度分为全方向顺序特征描述量计算时间复杂度和形状匹配时间复杂度两部分。设形状特征点k个，分割方向N个，每个分割方向下方向线n条，主方向附近分割方向的搜索范围为w。

全方向顺序特征描述量利用每个分割方向上的方向线分割对象，计算方向线上对象分割段之间的顺序特征描述量。设方向线上的对象分割段数目最多为p个，全方向顺序特征描述量的计算时间复杂度为O(N×n×p²)，其中分割方向的数目N、方向线的数目n均为常量，则全方向顺序特征描述量的计算时间复杂度为O(p²)。因为方向线上对象分割段的数目p通常远小于形状特征点的数目k，而其他形状描述法如TAR^[6]、HSC^[10]的时间复杂度为O(k²)，IDSC^[4]的时间复杂度为O(k³)，所以本文全方向顺序特征描述量计算时间复杂度较低。

形状匹配包括主方向的计算、两个待匹配对象对应分割方向的计算、全方向顺序特征描述量差异度的计算。主方向的计算时间复杂度为O(k)^[16]。两个待匹配对象的对应分割方向的计算时间复杂度为O(w²×n)，w最大取值为10。全方向顺序特征描述量差异度的计算时间复杂度为O(N×n)，分割方向数N的最大值为360。形状匹配的时间复杂度为O(k+n×(N+w²))，w最大取值为10，分割方向数N的最大值为360。形状全方向顺序特征描述的形状匹配阶段的时间复杂度较低，小于IDSC^[4]的匹配时间复杂度O(k²)、TAR^[6]的匹配时间复杂度O(k³)，大于HSC^[10]的匹配时间复杂度O(Mlogk)。

3 形状全方向顺序特征描述测试

为评估本文提出的形状全方向顺序特征描述方法的检索识别性能，使用地物形状数据集、标准数据集MPEG-7 CE-1 Part B和瑞典叶子数据集三个图像数据库进行测试。

3.1 地物形状数据集测试

地物形状数据集是本文通过真实建筑形状和面状水系形状构建的，该数据集从北京市矢量地图中选取40个不同建筑的形状，从我国面状水系图层中选取30个不同面状水系的形状，共70个形状，如图 6中上方图所示，前三行为30个不同面状水系的形状，后四行为40个不同建筑的形状。对每一个形状分别缩放0.49、0.7、1.37倍，得到3个形状，如图 6中下方图第一行从左至右依次是原始形状、缩放0.49倍形状、缩放0.7倍形状、缩放1.37倍形状。对原始形状和3个缩放形状分别旋转45°、135°、225°得到12个形状，如图 6中下方图第二行、第三行、第四行所示。对原始形状进行四种仿射变换，得到4个形状，如图 6中下方图第五行所示。对每个形状共进行了19次变换，得到了19个形状，加上原始形状，构成一类相似形状的20种形变。70个原始形状共形成了70类，每类20个相似形状，共1 400个形状的数据集。

本测试性能评估使用通用的Bulls-eye测试方法^[10]，该方法对数据集中的每个形状均进行一次检索，共进行1 400次检索实验。在每次实验检索出的前40个相似性最高的形状中，计算检索形状的同类相似形状个数，并统计1 400次检索实验相似形状的总和。因一类相似形状有20个，共1 400次实验，相似形状总和最大为20×1 400=28 000。统计得到的相似形状总和除以28 000为Bulls-eye测试检索率。本文全方向顺序特征描述法与TAR^[6]、HSC^[10]等描述法在地物形状数据集上的检索率如表 1所示。

从表 1可以看出在地物形状数据集中本文全方向顺序特征描述的检索率高于其他5个形状描述法。全方向顺序特征描述法可以准确识别地物形状数据集中所有经过放大、缩小和旋转的形状，具有平移、旋转和尺度不变性，对因仿射变换造成的形状形变具有鲁棒性。但较大程度的仿射变换导致地物形变过大，造成误匹配和漏匹配，影响本文形状描述法的检索率。

3.2 标准数据集MPEG-7 CE-1 Part B测试

标准数据集MPEG-7 CE-1 Part B是被广泛用来测试形状检索性能的，该数据库包含按语义分类的70类形状，每类20个，共1 400个形状图像。本文形状全方向顺序特征描述法与TAR^[6]、HSC^[10]等形状描述法在MPEG-7 CE-1 Part B形状数据集上的检索率如表 2所示。

从表 2可以看出在MPEG-7 CE-1 Part B形状数据集中本文全方向顺序特征描述的检索率高于其他5个形状描述法，具有更强的形状描述识别能力。图 7为本文方法在MPEG-7 CE-1 Part B形状数据集中部分检索结果的示例，其中误匹配被用圆圈标出。

3.3 瑞典叶子数据集测试

瑞典叶子数据集来源于瑞典林雪平大学和瑞典自然历史博物馆的叶子分类项目，该数据集包含了来自瑞典的15种不同种类的叶子，每个种类有75个样本数据，如图 8所示。

从每类叶子中随机选取25个作为待检索形状，其余的作为测试形状。本文全方向顺序特征描述法与TAR^[6]、HSC^[10]等形状描述法在瑞典叶子数据集的检索率如表 3所示。

从表 3可以看出在瑞典叶子数据集中本文全方向顺序特征描述的检索率高于其他5个形状描述法，与地物形状数据集、MPEG-7 CE-1 Part B数据集的测试结果一致，说明本文形状全方向顺序特征描述具有较高的形状检索识别精度。

4 结论

1) 本文形状描述方法拓展了F直方图模型，使F直方图可以同时描述空间方位关系和形状信息。

2) 本文形状描述方法可以通过调节分割方向的数量和方向线的数量，精确描述对象形状的整体特征和细节信息，实现形状的多级描述。

3) 本文形状描述方法将形状的边界信息和区域信息融合，具有平移、尺度、旋转不变性和较高的形状检索准确率。