形状是物体非常重要的一类视觉属性, 是人的视觉系统对目标进行识别和分类的一个重要依据.在计算机视觉中, 形状分析的焦点之一就是如何有效地抽取目标具有辨识力的形状特征并用于后续的识别、分类、检索等任务.人的视觉对目标的轮廓非常敏感, 甚至目标的二维轮廓也能给人的视觉系统传递足够的形状信息对其进行准确的识别^[1].图 1给出了一个树叶图像的完整轮廓线(图 1右上图)和不完整的轮廓线(图 1右下图)的一个示例.从该图可以看出:人的视觉仅需借助于目标的轮廓线, 甚至在得到的目标的轮廓不完整的情况下, 也能正确地识别目标.因此在很多情况下, 我们仅需对目标的边界像素点进行分析, 就可以抽取出具有强的辨识能力的形状特征, 由此产生了一类形状分析方法, 该类方法通常被称为基于轮廓线的形状分析方法^[2].

在轮廓线形状分析方法中, 获得大量研究的是参数化曲线的形状分析方法^[1].该类方法将目标外轮廓上的像素点按照它们在图像中的邻接关系(8-邻接或4-邻接)进行有序化表示, 形成一条像素点的序列, 从而构成一条参数化的简单曲线.图 1右上图最右边的树叶图像给出了参数化轮廓线的一个示例, 这种有序表示要通过轮廓追踪算法^[3]获得.近年来, 参数化曲线形状分析得到广泛和深入的研究, 产生了大量的形状描述和识别方法^[4-11].这类将目标外轮廓表示为一条参数化曲线的形状分析方法, 在形状描述阶段可以对曲线的几何性质如凸凹性进行分析, 从而抽取到具有辨识能力的形状特征; 而在形状匹配阶段, 可以借助像素点的有序信息进行轮廓线的精确匹配, 如采用动态规划的匹配方法.这些方法在标准测试集上(如MPEG-7形状测试集)都取得了非常高的识别正确率.但这类方法因严重依赖于目标外轮廓像素点的有序化信息, 从而存在很大的局限性.当从目标图像中抽取的边界像素点不完整时(如图 1右下图), 则这种对外轮廓像素点的有序化操作将无法完成, 即, 参数化曲线无法获得.在一些情况下, 即使这种参数化曲线能够获取, 也相当不准确, 如当目标图像的轮廓线出现自交叉现象时, 获取的参数化曲线显然无法正确表示原来的形状, 图 2给出了这一问题的示例.此外, 由于边界噪声的干扰, 也使得获取的参数化曲线非常不稳定.

基于轮廓线的形状分析方法的另一个思路是:将目标边界(包括内边界和外边界)看成一个无序的点集, 直接抽取点集的几何特征作为形状的描述子, 我们称为基于边界无序点集的形状分析方法.该类方法因不需要预先对边界像素点进行有序化处理, 所以在抽取的边界轮廓不完整的情况和边界噪声干扰的情况下, 都能够有效地工作, 也当然避免了对曲线进行有序化操作所引入的误差和不稳定性, 因此相较于参数化曲线形状分析方法更具鲁棒性和一般性.但是到目前为止, 该类方法的研究还相对较少.其面临的挑战在于:

(1) 相较于参数化曲线形状分析方法, 从无序的点集中提取具有强的形状辨识能力的特征将更困难.在参数化曲线方法中, 点的有序性这一非常有价值的信息, 在基于无序点集的形状分析中将无法使用.在参数化曲线分析方法中被大量使用的数学工具, 如小波变换、傅里叶变换、微分几何等, 在基于边界无序点集的形状分析中一般也无法使用.因此, 该类方法虽具鲁棒性和一般性, 但在高辨识能力的形状特征抽取方面具有挑战性;

(2) 该类方法在形状匹配阶段, 为获得较高的识别正确率, 往往需要以非常高的形状匹配的计算耗费为代价, 如用于点集匹配的Hungarian方法^[30], 在已知点到点的匹配的耗费情况下, 完成两个点集匹配的时间复杂度达到了O(N³), 这里, N是点集中点的个数.

因此, 该类方法只适合在小规模目标边界采样点集上的匹配任务.而目标边界的小规模采样点集又忽略了目标形状的很多细节信息, 所以现有的基于边界点集的较高计算复杂度, 也限制了该类方法在对时间要求很高的识别任务中的应用.而本文的研究工作则专注于基于边界无序点集的形状分析新方法的研究, 旨在从目标边界的无序点集表示中抽取鲁棒的、具有强的辨识能力的形状特征, 在较低的计算代价下获得理想的目标识别效果.

1 相关工作

到目前为止, 在形状的参数化曲线分析方面, 现有的工作已经非常丰富, 但在基于边界无序点集的形状分析方面的研究工作却相对较少.本节对这方面的代表性的研究工作进行综述.

形状上下文(shape contexts)^[13]是经典的基于边界无序点集的形状分析方法, 该方法将边界像素点集中的每一个点作为参考点, 通过在该点放置一个极坐标栅格来统计点集中的其他各点相对于该点的空间分布, 并产生直方图作为该点的描述子, 也称为该点的形状上下文.在形状匹配阶段, 用两个形状的点集中各点的形状上下文来建立两个点集之间的优化0的匹配关系, 然后计算各对匹配点的匹配误差的和, 并将其作为两个形状的距离.该方法有效抽取了轮廓线上点的空间分布信息和相对位置关系, 抽取的形状特征具有较强的辨识能力, 在MPEG-7形状测试集上取得了76.51%的识别准确率.但该方法的计算量非常可观, 根据文献[13]的报告, 执行一次两个形状的匹配计算, 在每个形状仅用100个采样点的情况下, 仍然要耗费0.2s.为提高计算的效率, 文献[14]提出了一种称为轮廓点分布直方图的改进的形状描述子.不同于形状上下文方法将极坐标栅格放置于每个轮廓点的局部描述机制, 该方法将极坐标栅格放置于整个形状的质心, 从而得到一个描述整个形状轮廓像素点的空间关系的轮廓点分布直方图.形状相似性用EMD (earth mover’s distance)距离进行度量.该方法实质上是一种全局描述子, 因不需要为点集中的每一个点准备描述子, 因此无论在形状的描述还是在形状的匹配阶段, 都减少了计算量.该方法在MPEG-7形状测试集报告的识别准确率与形状上下文方法相当.

距离集(distance sets)是文献[15]提出的另外一种基于边界无序点集的形状分析方法.该方法对大小为n的点集合中的每一个点, 计算点集中与其最邻近的N≪n个点到它的距离构成一个距离集合, 经过规一化处理的距离集合构成关联于该点的局部描述子, 用以描述该点与其邻近各点的空间关系.而由各点的距离集构成的集合, 即距离集的集合, 构成了描述整个点集的空间安排.对两个形状的相似性比较, 则通过求解两个距离集的集合的优化匹配关系, 该优化问题可归结为经典的二次指派问题.因此, 距离集形状分析方法跟形状上下文方法一样具有很高的计算复杂度.该方法报告, 在250个采样点的情况下, 执行两个形状的匹配要耗费0.7s.但该方法的描述能力非常强, 在MPEG-7形状测试集获得了78.38%的识别准确率, 高于形状上下文方法报告的结果.

近年来, 随着对复杂网络研究的兴起^{[16, 17]}, 一些研究工作将复杂网络模型、理论与方法应用于形状分析.文献[18]提出将目标边界建模为一个小世界复杂网络.在该模型中, 形状边界像素点对应网络中的节点, 像素点间的连线对应网络中的边, 像素点间归一化的欧式距离作为边的权重.通过网络的动态演化, 抽取各时刻网络的度分布和联合度分布特征组合成一个特征向量, 作为形状的描述子, 而形状的差异度则通过计算其相应的特征向量的欧式距离来确定.基于该模型, 文献[19]提出用演化阈值和度分布特征(包括最小度、最大度和平均度)计算复杂网络的多尺度分形维数描述子, 以抽取用于形状识别的不规则模式.文献[20]用内部距离^[5]替代该模型中的欧氏距离来建立形状的复杂网络模型, 用度特征和聚类系数特征, 再结合内部距离上下文特征来度量形状之间的距离.文献[21]则在用内部距离建立的复杂网络模型的基础上设计了一种k近邻的演化机制, 得到不同时刻的有向子网络, 然后提取有向网络的特征来描述形状.

用复杂网络建模形状, 为基于边界无序点集表示的形状分析带来了便利.边界点集中的节点很自然地对应复杂网络中的节点, 点集中点的相互联系则用网络的边的有关信息来表达, 而网络的动态演化行为也为多尺度形状特征的抽取创造了条件.本文提出一种用于边界无序点集形状分析的复杂网络模型, 虽然用复杂网络模型进行形状分析的想法并不是新的, 前述工作^[18-21]都是基于该想法而展开的, 但本文做出了如下创新和贡献:

(1) 提出了一种新的网络动态演化机制.现有的用于形状分析的复杂网络模型需要预先设定一系列的阈值作为参数(一般设置阈值的初始值、步长值和终止值)来控制网络的动态演化过程.这种策略一方面因为需要对多个参数进行设置, 从而不便于算法的一般使用; 另一方面, 对不同形状的复杂网络的动态演化都采用相同的阈值参数进行控制, 这种没有考虑网络内部特性的阈值选择机制并不有易于具有辨识力的形状特征的抽取.本文提出了一种自组织的网络动态演化机制, 网络的动态演化不需要预先设定阈值参数, 完全交由网络根据其内部信息确定其当前演化的阈值.该机制使得算法更易使用, 且抽取形状特征更具识别能力;

(2) 提出了一种不同的复杂网络特征抽取和匹配方法.现有的基于复杂网络的形状分析都只考虑了复杂网络的无权网络特征(如度分布、联合度分布特征、聚集系数等), 使得抽取的特征仅能反映形状的拓扑结构, 而不能描述边界像素点之间的空间关系.本文提出了一种带权的复杂网络模型, 既抽取了网络的无权特征, 又抽取网络的加权特征, 同时对网络既进行了全局测量, 又进行了局部测量, 从而更为全面地描述形状.而在形状匹配阶段, 对形状既进行了全局特征的比较, 又进行了局部的特征匹配(点到点的匹配), 使得对形状差异的度量更为精细.

通过采用公认的标准测试集所进行的性能评估以及与现有的基于边界无序点集表示的形状分析方法的比较, 验证了本文提出的方法的有效性.

2 形状的复杂网络建模

从统计物理学看, 网络是由大量的相互作用、相互依赖的个体组成的系统.据钱学森给出的定义, 复杂网络是具有自组织、自相似、吸引子、小世界、无标度中的部分或全部性质的网络.复杂网络是呈现出高度复杂性的网络, 可以灵活表达任何自然的结构以及拓扑结构的动态变化特性^[17].

同文献[13]一样, 我们首先将形状表示为离散点集V={v₁, v₂, …, v_N}, 这些点取自于目标形状的内外轮廓.由于通过边界检测算子获得的像素点个数太多, 需要重新采样, 我们采用文献[13]中的方法, 对获得的边界像素点采样成大小为N的像素点集, 这里, 正整数N是预先指定的参数.跟文献[13]中的方法略有不同的是:如果一个目标形状通过边界检测算法获得的像素点的个数已经小于指定的参数N, 则不需要进行重新采样.

由形状的离散点集V和点集中任意两点的欧式距离d_ij可构造一个加权的无向图G=(V, E), 这里, E是图G中边的集合, 由邻接矩阵A={a_ij}_N×N给定, a_ij=1表示有一条边连接点v_i和v_j; 而a_ij=0则表示两个点之间无边相连, 图中的每一条边带有权重, 其值由矩阵W={w_ij}_N×N确定.这里, $ {w_{ij}} = {d_{ij}}/\mathop {\max }\limits_{1 \le i, j \le N} ({d_{ij}}) $.显然有w_ij≤1.复杂网络不同于一般的图的是它的动态演化特性, 即, 网络的节点或边在不同的时刻可以增加或减少.为此, 我们为形状复杂网络建模设计了动态演化机制.令A^(t)为G在t时刻的邻接矩阵, 此时, 网络的平均权重定义为w^(t)

$ {\bar w^{(t)}} = \frac{{\sum\nolimits_{ij} {{w_{ij}}a_{ij}^{(t)}} }}{{\sum\nolimits_{ij} {a_{ij}^{(t)}} }} $

(1)

则网络G在t+1时刻的邻接矩阵变化为

$ a_{ij}^{(t + 1)} = \left\{ {\begin{array}{*{20}{l}} {a_{ij}^{(t)}, {\rm{ if }}{w_{ij}} < {{\bar w}^{(t)}}}\\ {0, {\rm{ otherwise}}} \end{array}} \right. $

(2)

网络G中, 那些权重大于或等于当前网络平均权重的边将被去掉.我们定义网络在t=0时刻的邻接矩阵A⁽⁰⁾={1}_N×N, 即:此时网络中的每两个节点都有边连接, G构成一个完全图.那么依据公式(1)和公式(2), 后续的t=1, 2, …各个时刻的网络图都可以唯一地确定.图 3给出了狗的形状复杂网络模型(60个节点)的从t=0到t=4的各个时刻的网络演化图(从左到右列出的是狗的形状复杂网络模型在t=0, 1, 2, 3, 4时刻演化出的网络图).值得指出的是, 本文提出网络演化机制不同于文献[18-20]提出的方法:本文提出的演化机制是由当前形状网络中内部特性(平均权重)来决定下一个时刻的演化图, 因此是一种自组织的演化机制, 不需要预先设置一系列的阈值参数来控制网络的动态演化.这也是本文提出的复杂网络模型与文献[18-20]给出的复杂网络模型不同的地方.根据该演化机制, 后一个时刻的图是前一个时刻的子图, 从t=0时刻开始, 演化产生的各个时刻的图一起构成了一个分层的形状描述框架, 基于该框架, 我们将对各个时刻的网络图进行测量, 以分层的抽取形状的结构特征.

3 形状特征抽取

本节对前面建立的复杂网络进行局部和全局的测量来抽取形状的分层结构特征, 以用于后面的形状识别任务.

3.1 网络的局部测量

这里, 网络的局部测量的主要任务是, 针对每一时刻的网络中的每一节点构造描述子.对网络中的每一

个节点v_i, 我们用其在t刻的度特征K_i^(t)、单位权特征U_i^(t)、聚集系数特征C_i^(t)、加权聚集系数特征$ \tilde C_i^{(t)} $来构造描述子, 定义这4个特征的数学公式如下:

$ K_i^{(t)} = \sum\limits_j {a_{ij}^{(t)}} $

(3)

$ U_i^{(t)} = \frac{{\sum\nolimits_j {{w_{ij}}a_{ij}^{(t)}} }}{{\sum\nolimits_j {a_{ij}^{(t)}} }} $

(4)

$ C_i^{(t)} = \frac{{\sum\nolimits_{k > j} {a_{ij}^{(t)}a_{ik}^{(t)}a_{jk}^{(t)}} }}{{\sum\nolimits_{k > j} {a_{ij}^{(t)}a_{ik}^{(t)}} }} $

(5)

$ \tilde C_i^{(t)} = \frac{{\sum\nolimits_{k > j} {{w_{ij}}{w_{ik}}{w_{jk}}a_{ij}^{(t)}a_{ik}^{(t)}a_{jk}^{(t)}} }}{{\mathop {\max }\limits_{k > j} ({w_{jk}}a_{jk}^{(t)})\sum\nolimits_{k > j} {a_{ij}^{(t)}a_{ik}^{(t)}} }} $

(6)

对网络中的每个节点v_i, 组合t=0, …, T-1个时刻的度、单位权、聚集系数、加权聚集系数这4类特征, 构成一个4×T维的特征向量:

$ {\varphi _i} = \{ K_i^{(0)}, ..., K_i^{(T-1)}, U_i^{(0)}, ..., U_i^{(T-1)}, C_i^{(0)}, ..., C_i^{(T-1)}, \tilde C_i^{(0)}, ..., \tilde C_i^{(T - 1)}\} $

(7)

作为节点v_i的描述子, 这里, T是给定参数, 用以控制网络演化的代数.描述子φ_i既抽取了网络的无权特征-度和聚集系数, 又抽取了网络的加权特征--单位权和加权聚集系数, 从而对网络的拓扑结构和节点的空间分布都进行了描述.

3.2 网络的全局测量

除了对网络进行局部测量, 用无权特征和有权特征为网络的每一个节点构造局部描述子之外, 我们还对网络进行全局测量, 对网络中的所有节点对的无权特征和有权特征的数字值分别进行比较, 并进行组合统计, 由此得到4类反映网络全局特性的统计特征:$ R_{KU}^{(t)}, R_{K\tilde C}^{(t)}, R_{CU}^{(t)} $和$ R_{C\tilde C}^{(t)} $, 其数学定义如下:

$ R_{KU}^{(t)} = \frac{{|\{ \langle {v_i}, {v_j}\rangle :(K_i^{(t)}-K_j^{(t)})(U_i^{(t)}-U_j^{(t)}) < 0\} |}}{{N(N-1)}} $

(8)

$ R_{K\tilde C}^{(t)} = \frac{{|\{ \langle {v_i}, {v_j}\rangle :(K_i^{(t)}-K_j^{(t)})(\tilde C_i^{(t)}-\tilde C_j^{(t)}) < 0\} |}}{{N(N-1)}} $

(9)

$ R_{CU}^{(t)} = \frac{{|\{ \langle {v_i}, {v_j}\rangle :(C_i^{(t)}-C_j^{(t)})(U_i^{(t)}-U_j^{(t)}) < 0\} |}}{{N(N-1)}} $

(10)

$ R_{C\tilde C}^{(t)} = \frac{{|\{ \langle {v_i}, {v_j}\rangle :(C_i^{(t)}-C_j^{(t)})(\tilde C_i^{(t)}-\tilde C_j^{(t)}) < 0\} |}}{{N(N-1)}} $

(11)

这里, |·|表示集合的势, < v_i, v_j>是由节点v_i和v_j构成的节点对, N是网络中节点的个数.

令$ \xi = \{ R_{KU}^{(0)}, ..., R_{KU}^{(T-1)}, R_{K\tilde C}^{(0)}, ..., R_{K\tilde C}^{(T-1)}, R_{CU}^{(0)}, ..., R_{CU}^{(T-1)}, R_{C\tilde C}^{(0)}, ..., R_{C\tilde C}^{(T - 1)}\} $为组合t=0, …, T-1时刻的这4类统计特征而成的向量, 该4×T维的特征向量ξ构成了形状的全局描述子.

4 形状距离 4.1 点到点的特征匹配

在第3.1节, 我们为形状边界点集中的每一个点构造了一个描述子, 通过比较两个点集中的点的描述子来度量两个形状的差异度.令形状A和B形状的局部描述子分别为$ \{ \varphi _i^A, i = 1, ..., M\} $和$ \{ \varphi _j^B, j = 1, ..., N\} $, 这里, M和N分别是形状A和形状B的边界点集表示中点的个数.定义两个点集的距离的常用方法是Hausdorff距离, 这里我们用文献[22]提出的增强Hausdorff距离来定义两个形状的差异度.我们首先定义形状A点集中的任意一点v_i^A和形状B点集中的任意一点v_j^B之间的距离为

$ d(v_i^A, v_j^B) = ||\varphi _i^A-\varphi _j^B|{|_1} $

(12)

这里, ||·||表示1的范数, 则点集A到点集B的距离定义为

$ h(A, B) = \frac{1}{{M-{\eta _A}}}\sum\limits_i {\mathop {\min }\limits_j d(v_i^A, v_j^B)} $

(13)

这里, η_A的计算步骤为

(1) 设置一个数组ζ(1:N), 将其每一个元素的初始值设置为-1;

(2) 对点集A中的每一个点v_i^A, 在点集B中寻找其最邻近点v_j^B, 满足, 并置$ d(v_i^A, v_j^B) = \mathop {\min }\limits_k d(v_i^A, v_k^B) $:

$ \zeta (j) \leftarrow \zeta (j) + 1; $

(3) 将数组ζ(1:N)中所有大于0的元素进行求和, 并赋值给η_A.

该计算实质上将点集A中的每一个点用公式(11)中定义的距离按最邻近原则映射到B中的某个点, 然后对B中所有被映射两次或两次以上的点的被映射次数减1后进行求和, 即得到η_A的值.η_A=0, 表明A中的所有点都映射到了B中不同的点; 而η_A=M-1, 则表明A中的所有点都映射到了B中的同一个点.

同样, 定义点集B到点集A的距离为

$ h(B, A) = \frac{1}{{N-{\eta _B}}}\sum\limits_j {\mathop {\min }\limits_i d(v_j^B, v_i^A)} $

(14)

这里, η_B的计算步骤同η_A, 即:将点集B中的每一个点用公式(11)中定义的距离, 按最邻近原则映射到A中的某个点, 然后对A中所有被映射两次或两次以上的点的被映射次数减1后进行求和.点集A和点集B的Hausdorff距离定义为

$ {D_l}(A, B) = {\rm{max}}(h(A, B), h(B, A)) $

(15)

增强Hausdorff距离^[22]是对文献[23]提出的Hausdorff距离的一个改进, 在距离的计算中加入了两个点集之间的映射信息(公式中的变量η_A和η_B记录了这方面的信息).

4.2 全局特征匹配

这里用第3.2节给出的全局特征向量, 通过比较两个形状的全局特征的差异来计算形状的全局匹配距离.记形状A和形状B的全局特征向量分别为ξ_A和ξ_B, 定义形状A和B之间的全局匹配距离为

$ {D_g}(A, B) = ||{\xi ^A}-{\xi ^B}|{|_1} $

(16)

4.3 形状差异度度量

组合前面给出的局部匹配距离D_i(A, B)和全局匹配距离D_g(A, B), 得到如下形状A和形状B的差异度度量:

$ D(A, B) = {D_l}(A, B) + W \cdot {D_g}(A, B) $

(17)

这里, 0≤W≤1是权重因子, 用以平衡两种距离在形状差异度量中的贡献, 在实际应用中经验给定.

5 实验结果和讨论

为评估本文提出的形状分析方法的性能, 我们将Kimia^[24]和MPEG-7^[25]这两个被广泛采用的形状图像测试集作为基准测试集, 通过3组实验来验证本文提出的形状分析方法的识别精确率和鲁棒性.

值得指出的是:本文提出的是基于边界无序点集的形状分析方法, 因此在比较对象的选择方面, 那些参数化曲线的形状分析方法^[4-11], 尽管它们在这两个测试集上都报告了较高的识别精确率, 由于都利用了目标边界点的有序信息, 与本文提出的方法都属于不同类方法, 因此不被列入比较对象.在实验中, 我们选取了经典的形状上下文方法(shape context)^[13]、距离集方法(distance set)^[15]、轮廓点分布直方图(CPDH)^[14]和两种基于复杂网络的形状分析方法^{[18, 20]}作为比较对象.这些方法都是基于边界无序点集的形状分析方法, 与本文提出的方法同类.本文提出的方法在特征抽取阶段将形状边界重采样成不超过300个点, 设置的网络动态演化的迭代次数为T=5, 在特征匹配阶段的权重因子为W=0.25.

5.1 Kimia形状测试集

Kimia^[24]图像数据库是一个被广泛采用的标准形状测试集, 该库有9类形状, 每类11个样本, 同类形状存在边缘扭曲、局部缺损或遮挡、类内形变等复杂的变化(如图 4所示).在该测试集上, 标准的性能评估方法是将99个样本中的每一个作为检索形状, 与图像库中的其余形状进行差异性比较(共产生99×98次比较), 对每一个检索形状, 将比较的结果按差异度由小到大排序, 检查排在前10的形状, 统计在每一个排名位置上匹配正确的形状个数.显然, 在前10的排名位置上, 每一个最多会有99个正确的匹配(每一个待匹配的形状在该位置产生1个).

表 1给出了本文提出的方法和参与比较的各方法在该测试集上的形状检索结果.检索结果给出了前10个排名位置的正确匹配的形状个数.在第1个排名位置, 即最近邻匹配, 采用本文给出的方法, 每一个检索形状都找到了其正确的匹配, 而Shape Contexts^[13], CPDH^[14], Complex Networks^[18]分别产生了2个、1个和2个错误的匹配; 在后面的各个排名位置, 本文提出的方法匹配正确的形状个数都大于参与比较的各方法.在前10个位置, 本文提出的方法共产生了932个正确的匹配, 平均检索正确率(AP)可以计算为932/990=94.14%, 比Shape Contexts (775/990=78.28%), CPDH (849/990=85.76%), Complex Networks (759/990=76.67%)这3种方法分别高出了15.86%, 8.38%, 17.47%.该实验结果表明, 本文提出方法的检索正确率要优于参与比较的各种方法.

表 2则给出了本文提出的方法与Shape Contexts^[13]和Complex Networks^[18]的计算效率的比较.这里, 检索时间定义为一个检索形状与图像库中的所有形状进行匹配的时间, 对于本实验, 则是进行99次匹配的时间.从该表可以看出:本文提出的算法耗费了0.16s就完成了一次形状的检索, 而经典的Shape Contexts^[13]则要耗费19.58s, 其耗时超过本文提出的方法122倍.值得指出的是, 本文提出的方法要慢于Complex Networks^[18]方法.这是因为本文提出的方法既有全局特征匹配, 又执行了点到点的特征匹配, 而后者仅进行了全局特征匹配.从综合平衡检索效率和检索精度两个方面, 本文提出的方法要优于参与比较的各方法.

5.2 MPEG-7形状测试集

MPEG-7形状图像数据库^[25]是另一个用于形状检索性能评估的标准测试集, 该测试集由70类形状(每类20个样本), 总共1 400幅图像组成(部分样本如图 5所示).在该测试集上, 被广泛采用的形状检索性能评估方法是“bulls-eye test”测试^{[4-11, 13]}.采用该测试, 将图像库中的每一个样本作为一个查询样本, 跟测试集中的所有样本进行差异性比较, 然后根据差异度值进行由小到大排序, 统计前2×20=40幅图像中与查询样本属于同一类的样本数(记为r), 显然有r≤20, 计算r/20×100%的值作为该查询样本的检索率, 计算1 400个检索样本的检索率的平均值, 作为整个测试的检索率(bulls-eye test score).

表 3列出了本文提出的方法和其他参与比较的4种方法的检索结果.本文提出的方法获得78.18%的检索精确率, 在表格列出的所有方法中排名第2.排名第1的方法Distance Sets获得了78.38%, 比本文提出的方法仅高出0.2个百分点.但该方法跟Shape Contexts方法^[13]一样, 在形状匹配阶段都采用了时间复杂度非常高的Hungarian^[12]方法(该算法的时间复杂度为O(N³)^[13], 这里, N是点集的大小).也就是说, 该方法较高检索精确率的取得是以高的计算时间复杂度为代价.而本文提出的方法在形状匹配阶段采用计算复杂度较低的Hausdorff距离^[26](其时间复杂度为O((M+N) log (M+N))^{[22, 26]}, 这里, M和N分别是待匹配的两个点集的大小, 如两个点集大小相等, 则时间复杂度为O(NlogN), 要远低于Distance Sets方法^[15]和Shape Contexts方法^[13].据文献[15]报告:采用Distance Sets方法, 执行一次两个形状的匹配(250个采样点), 在一台Pentium Ⅲ/667MHZ的计算机上大约耗时7×10^-1s.根据文献[13]报告的结果, 采用Shape Contexts方法, 执行一次两个形状的匹配计算(100个采样点), 在一台Pentium Ⅲ/500MHZ的计算机上需要耗时2×10^-1s.文献[14]则报告, 采用CPDH^[14]方法, 执行一次两个形状的匹配(200个采样点), 在一台Pentium Ⅳ/2.66GHZ的计算机上大约耗时1.4×10^-2s.而采用本文提出的方法, 在一台CPU为Intel Core i7-4770/3.4GHZ的计算机上, 执行一次两个形状的匹配计算(300个采样点), 仅用时9.4×10^-4s.在表 4中, 我们给出了本文提出的方法和经典的Shape Contexts^[13]方法和Complex Network^[18]的计算时间的比较.从表中可以看出:本文提出的方法检索时间仅为1.91s, 而Shape Contexts^[13]要耗时328.77s, 其检索速度要原低于本文提出的方法.尽管Complex Network^[18]的计算速度要快于本文提出的方法, 但其检索精确率要比本文提出的方法低15.78个百分点.因此, 本文提出的方法有着相对较少的计算耗费和更好的检索精度, 更适合图像的在线检索的需要.

行了比较.该方法在报告的实验中选取了MPEG-7形状测试集中的18类形状, 构成了18×20=360幅图像的测试集, 然后在该测试集中进行图像检索实验, 采用“bulls-eye test”检索性能评估方法, 报告的检索率为86.47%.为便于与该方法的比较, 我们对本文提出的方法在该测试集上进行了同样的测试, 在实验中, 我们取得了95.26%的检索率, 高于文献[20]提出的方法超过8个百分点, 进一步证明了本文提出的用于形状分析的复杂网络模型的优越性.

5.3 鲁棒性测试

为评估本文提出的方法的鲁棒性, 我们进行了另外两组实验:第1组实验测试当形状的轮廓线上的点发生了缺失后, 算法的鲁棒性; 第2组实验测试算法对噪声的鲁棒性, 实验方案类似于文献[18]介绍的方法.

针对第1组实验, 将前面Kimia测试中用到的形状轮廓线随机地分别移去20%, 40%和60%的点(图 6给出了对狗的形状轮廓进行该操作的一个例子), 由此得到3个测试集.在得到的这3个形状测试集中分别进行Kimia测试, 实验结果在表 5中列出(轮廓线上的点发生缺失).

从表 5可看出:当移去20%的点时, 匹配正确的形状个数达到901个, 平均检索正确率AP达到了901/990=91.01%, 比原来的93.43%的检索率仅降低了2.42个百分点; 而当移去的点达到60%(观察图 6最右边的图可以看出:在这种情况下, 有多个成段的轮廓线被去掉, 此时轮廓线上的点已变得非常稀疏), 本文提出的方法仍然检索到了777个正确的形状, 检索率达到了78.49%, 表明算法仍然能工作.在该表中, 我们还列出经典算法Shape Contexts^[13]的相应的实验结果, 以资对比.通过对比可以看出:对于每一组实验, 本文提出的方法平均检索正确率比Shape Contexts^[13]都高出了至少11个百分点以上.该组实验结果表明了本文提出的算法对轮廓线上点缺失的鲁棒性.

在噪声鲁棒性测试实验中, 将前面Kimia测试中用到的每一个采样后的形状轮廓的所有点的x坐标和y坐标分别看成一维信号, 并在其中加入信噪比(SNR)分别为40dB, 35dB, 40dB, 25dB的随机高斯噪声(加入噪声后的形状样本如图 7所示), 由此得到4个加入不同强度噪声的形状测试集.在得到的这4个形状测试集中分别进行Kimia测试, 实验结果在表 6中列出.

从表 6可看出:在4种强度的噪声影响下, 本文提出的算法仍然分别取得了912/990=92.12%, 898/990=90.71%, 886/990=89.49%, 834/990=84.24%的平均检索正确率.特别是在高强度噪声干扰下(SNR=25dB), 本文提出的方法仍然取得了较高的检索率84.24%.在与经典算法Shape Contexts^[13]的比较中, 对于4组实验, 本文提出的算法每一组实验都要比之高出12个百分点以上, 表明了本文提出的算法对噪声干扰的鲁棒性.

6 结论

本文提出了一种新的基于复杂网络模型的目标轮廓无序点集形状的分析方法.该方法用自主的网络动态演化机制, 分层地抽取形状特征, 通过对网络的局部测量和全局测量获取网络的无权特征和加权特征, 构成形状的局部描述子和全局描述子.该描述子为目标形状的识别提供了强辨识能力的特征, 仅用低计算复杂度的Hausdorff距离(局部匹配)和L₁距离(全局匹配), 就能有效地进行形状的识别.用基准的图像测试集和标准性能评估方法对本文提出的方法进行了测试, 实验结果表明:本文提出的方法具有较高的识别精确率和鲁棒性, 其综合性能要优于同类方法--形状上下文^[13]、距离集^[15]、轮廓点分布直方图(CPDH)^[14]和其他两种基于复杂网络的形状分析方法^{[18, 20]}, 能够有效地用于解决边界无序点集的形状识别这一形状分析任务中的具有挑战性的问题.将该方法拓展到一般的点集模式的描述与匹配, 将是下一步的研究工作.