形状是一种高层次的视觉特征, 其对应物体中不受位置、尺度、旋转因素影响的几何信息^[1], 形状分析在目标检测^[2]、医疗分析^[3]、古文字研究等^[4]领域都发挥着重要的作用.在形状分类、形状聚类、形状识别和形状检索等研究中, 如何选择有效的形状匹配方法来分析形状间距离都是需要解决的首要问题.

在众多的形状匹配研究中, 基于轮廓点空间位置关系特征的形状匹配方法能够较好地分析形状间距离, 是近年来最为重要的一类方法^[5].形状上下文(Shape context, SC)是二十一世纪初由Belongie等^[6]提出的一种形状描述符, 其通过分析轮廓上采样点的分布情况而生成, 可以兼顾形状的局部信息和全局信息.形状上下文作为最重要的形状描述符之一, 自提出以来得到广泛的关注.广义形状上下文(Generalized shape context)^[7]、骨架形状上下文(Skeletal shape context)^[8]、方向直方图形状上下文(Histogram of orientation shape context)^[4]、实心形状上下文(Solid shape context)^[9]等都是在其基础上改进得到的形状描述符, 对应形状匹配方法都表现出了很好的识别和检索效果.

在对形状上下文进行改进的诸多方法中, Ling等^[10]提出的内距离形状上下文(Inner-distance shape context, IDSC)是一种形状匹配效果较好的描述符.该方法引入对连接不敏感的内距离(Inner-distance, ID)替代欧几里得距离(Euclidean distance, ED), 进而可以得到更合理的采样点间距离.考虑到形状上下文和内距离形状上下文分别具有不同的适用范围, 文献[11]结合两种形状描述符的各自特点, 进一步提出了地貌形状上下文(Aspect shape context, ASC), 该描述符能够更好地平衡形状描述符的鲁棒性和区别能力.

虽然地貌形状上下文能够较好地结合形状区域信息描述轮廓采样点空间关系, 但该方法依然存在一些不足.在形状特征提取时, 计算测地距离(Geodesic distance, GD)的时间复杂度较高, 使得形状描述符构造缓慢, 影响了形状匹配的效率; 此外, 在特征匹配过程中, 原始方法仅选择一个地貌空间对应的形状距离作为最终结果, 难以综合不同地貌空间的信息来解决形状匹配问题.

鉴于目前存在的问题, 本文提出了一种基于改进地貌形状上下文的形状匹配方法.通过引入最短路径算法对地貌空间下轮廓采样点间的测地距离进行快速计算, 进而提升形状特征提取的效率.通过生成模糊直方图来提升形状描述符的表达能力, 构造出地貌模糊形状上下文(Aspect fuzzy shape context, AFSC), 其能够更好地描述轮廓采样点分布情况.考虑到轮廓点集顺序关系已知, 结合动态规划方法获取不同地貌空间下形状采样点间准确的对应关系, 进而获得准确的形状匹配结果.相比于传统的形状匹配方法, 改进后的方法能够在较高的运算效率下有效提升形状匹配的结果, 并获得较好的形状识别和检索结果.

1.   地貌形状上下文

地貌形状上下文是将地貌空间中测地距离引入对数极坐标直方图而得到的形状描述符.地貌空间的测地距离是对欧氏距离和内距离的折衷, 其能够更好地分析采样点间的位置关系.因此, 地貌形状上下文可以更好地反映轮廓采样点分布情况.

1.1   地貌空间下的测地距离

欧氏距离和内距离是分析形状采样点间关系的两种不同距离度量, 在形状匹配问题中, 二者表现出了不同的特点.欧氏距离能有效地克服噪声和局部形变所带来的干扰, 而内距离可以较好地解决非刚性物体运动所产生的变化问题.图 1给出了一组相似形状的示例, 对二者对应轮廓采样点间的距离进行分析, 分别利用$ED\left(\cdot, \cdot\right)$和$ID\left(\cdot, \cdot\right)$表示欧氏距离和内距离.从图中可以看出, 内距离对连接不敏感, 能更准确地表示图 1(b)中相似形状对应采样点间的距离关系; 欧氏距离则能消除噪声干扰, 更准确地反映图 1(c)中相似形状对应采样点间的距离关系.

图 1  以不同距离度量分析相似形状对应采样点关系的示例

Fig. 1  An example of analyzing the distances between corresponding points from two similar shapes with different measures

下载: 全尺寸图片 幻灯片

为了平衡欧氏距离和内距离, 文献[12]选择地貌空间(Aspect space)中的测地距离来分析形状上采样点间位置关系.对于图像$I\left(\cdot, \cdot\right):\Lambda\to\left[0, 1\right]$, $\Lambda\subset{{\bf R}^2}$为图像的区域, 其对应的地貌空间$\mathcal{A}\subset{{\bf R}^3}, \left(x, y\right)\in\Lambda, z={\eta}I\left(x, y\right)$, 参数$\eta\in\left[0, \infty\right)$.给定$\eta$, 地貌空间中两点$s_i$与$s_j$对应的测地线$L_{i, j}$, 则测地线可以定义为

利用$GD\left(\cdot, \cdot\right)$表示测地线距离, 进一步可以得到

以二值图像所表示的形状为例, 当$\eta=0$时, $GD\left(i, j\right)$对应欧氏距离; 当$\eta\to\infty$时, $GD\left(i, j\right)$对应内距离.因此, 随着参数$\eta$的变化, 可以构造出不同的地貌空间, 得到对应的测地距离, 进而更好地反映相似形状对应采样点间的关系.

1.2   形状上下文

形状上下文是一种基于轮廓点位置关系的形状描述符, 其基本假设是形状信息可以利用轮廓上有限数目的采样点进行表示, 通常在轮廓上均匀采样生成对应的点集合^[6].

假设集合$P=\{p_1, p_2, \cdots, p_\lambda\}$中包含形状轮廓上$\lambda$个采样点, 分别以每个点为参考建立对数极坐标直方图. $p_i\in{\bf{R}}^2$处对应的对数极坐标直方图$H_i=\{h_i\left({m, n}\right):1\le{m}\le{M}, 1\le{n}\le{N}\}$可表示为

其中, $\boldsymbol{1}_{B_{mn}}$为特征函数, $B_{mn}$为二维子集. $\left(q-p_i\right)\in{B_{mn}}$时, $\boldsymbol{1}_{B_{mn}}\left(q\right)=1$; 否则, $\boldsymbol{1}_{B_{mn}}\left(q\right)=0$.由于对数极坐标直方图结构比较特殊, 兼顾了形状的局部信息和全局信息, 能够很好地描述轮廓点分布情况.将$H_i$归一化即可得到$p_i$处对应的形状上下文.

假设$P$和$Q$分别为不同目标轮廓上得到的采样点集合, 则匹配损失函数$D_{ij}$可以表示为${\chi}^2$距离

其中, $p_i\in{P}$和$q_j\in{Q}$所对应的对数极坐标直方图分别为$H_i$和$H_j$.

构造标准的形状上下文和内距离形状上下文的过程中, 分别引入欧氏距离和内距离来分析形状轮廓采样点间关系, 二者分别适用于表示不同类型的形状特征.地貌形状上下文引入测地距离来建立对数极坐标系下的直方图, 由于地貌空间中的测地距离可以同时兼顾欧氏距离和内距离两种度量标准的自身特点, 其对应生成的形状描述符能够更准确地描述形状信息.

2.   改进的地貌形状上下文特征提取方法

在构造形状描述符的过程中, 测地距离能够较为准确地描述形状信息, 但分析计算测地距离的方法速度较慢, 如Fast marching算法等, 导致形状特征提取效率较低.考虑到二值图像对应的地貌空间结构比较特殊, 本文将特征提取过程中的测地距离计算问题近似为求解最短路径问题, 可以有效提升效率.同时引入模糊直方图更加合理地描述轮廓采样点的分布情况.

2.1   快速计算地貌空间测地距离

由于形状通常由目标范围的二值图像进行表示, 即$I\left(x, y\right)=1$或$I\left(x, y\right)=0$, 对应生成的地貌空间结构相对简单, 其可视作由三个面所围成:分别为平行于$x, y$轴的平面$\alpha, \gamma$, 及母线平行于$z$轴, 准线为形状轮廓方程$f\left(x, y \right)=0$的柱面$\beta$.其中, $\alpha$对应$z=\eta$, 即$I\left(x, y\right)=1$; $\beta$对应形状轮廓方程$f\left(x, y\right)=0$; $\gamma$对应$z=0$, 即$I\left(x, y\right)=0$.三个面之间有如下关系, $\alpha\cap\beta={\Gamma}, \beta\cap\gamma={H}$, ${\Gamma}$和${H}$分别表示两条闭合曲线.图 2给出了一幅二值图像和对应地貌空间的示例, 图 2(a)是一幅200像素$\times$ 230像素二值图像, 图 2(b)是$\eta=260$时对应生成的地貌空间.

图 2  一个二值图像对应生成的地貌空间示例

Fig. 2  An example of the aspect space obtained from a binary image

下载: 全尺寸图片 幻灯片

对于地貌空间$\mathcal{A}$中的测地线$L_{i, j}$, 对应的起点和终点分别为$s_i\in{\mathcal{A}}$和$s_j\in{\mathcal{A}}$, 参数方程定义为$L_{i, j}\left(t\right)=\left(x\left(t\right), y\left(t\right), {\eta}I\left(x, y\right)\right)$, $t\in\left[0, 1\right]$.当满足$L_{i, j}\subset\alpha$或$L_{i, j}\subset\gamma$时, 可知$\frac{\partial{I}}{\partial{t}}=0$, 进而由式(2) 可得

图 3(a)给出了分别位于$\gamma$平面和$\alpha$平面的两条测地线片段$L_{b, c}$, $L_{d, e}$的示例.

图 3  地貌空间中测地线路径示例

Fig. 3  An example of geodesic in the aspect space

下载: 全尺寸图片 幻灯片

当测地线片段满足$L_{i, j}\subset\beta$, 且$L_{i, j}$与曲线$\Gamma$和曲线${H}$分别交于两点$s_i$和$s_j$, 由于柱面$\beta$为可展曲面, 可将其所在面$\beta$展成平面, 则经过柱面$\beta$的测地线片段可对应为平面中连接两点的直线, 由式(2) 可得

其中, $C_{i, j}=\int_0^1 {{{\left( {\frac{{\partial {x^2}}}{\partial {t}} + \frac{{\partial {y^2}}} {{\partial{t}}}} \right)}^{\frac{1}{2}}}{\rm d}{t}}$为形状轮廓上曲线片段的长度.图 3(a)给出了两条经过柱面$\beta$的测地线片段$L_{a, b}$, $L_{c, d}$的示例; 图 3(b)给出了测地线片段$L_{a, b}$对应柱面$\beta$展开的示例.

对于形状轮廓上任意两点$p_1$和$p_K$, 将其映射至地貌空间$\mathcal{A}$中可以得到两点$s_1\in {\Gamma}$和$s_K\in{\Gamma}$, 其在$\mathcal{A}$中对应的测地线为$L_{1, K}$, 曲线依次经过点$s_1, s_2, \cdots, s_K$.根据测地线$L_{1, K}$经过曲面的不同, 将其划分为数个首尾相接的测地线片段, 可得到分别经过$\alpha$平面, $\beta$柱面和$\gamma$平面的测地线片段, 对应集合$\{L_{i, i+1}:1\le{i}\le{K-1}, L_{i, i+1}\subset\mathcal{A}\}$. 图 3(a)给出了一个地貌空间上测地线划分的示例.进一步可利用式(5) 和式(7) 直接求解$L_{i, i+1}$的长度.测地线$L_{1, K}$的长度即为集合中各测地线片段$L_{i, i+1}$长度之和, $1\le{i}\le{K-1}$, 即

已知形状轮廓上采样点集合$P=\{p_i:1\le{i}\le{\lambda}\}$, $p_i=\left(x_i, y_i\right)$, 将$P$映射至地貌空间$\mathcal{A}$中曲线${\Gamma}$上得到集合$S_{{\Gamma}}=\{s_i:1\le{i}\le{\lambda}\}$, $s_i=\left(x_i, y_i, \eta {I}\left(x_i, y_i\right)\right)$; 同时将$P$映射到地貌空间$\mathcal{A}$中曲线${H}$上得到集合$S_{{H}}=\{s_j:\lambda+1\le{j}\le{2\lambda}\}$, $s_j=\left(x_{j-\lambda}, y_{j-\lambda}, 0\right)$.进而可以得到地貌空间$\mathcal{A}$中的点集$S=S_{{\Gamma}} \cup{S_{{H}}}$.对于任意$s_i\in{S}$和$s_j\in{S}$, 当$\left|i-j\right|=1$或$\left|i-j\right|=\lambda-1$时, $GD\left(i, j\right)=\left\|s_i-s_j\right\|_2$.

进一步针对$S$建立对应的图模型$G=\{S, E\}$, 其中$e_{ij}\in{E}$可通过下式得到

其中, $ED\left(i, j\right)$表示$s_i$和$s_j$之间的欧氏距离.

形状上下文特征的基本假设是利用有限数目采样点描述形状信息, 本文也同样设置固定数目采样点对形状进行表示.对于任意轮廓上点$p_i\in{P}$和$p_j\in{P}$, 分析地貌空间中二者间测地距离的过程, 可以近似视作在集合$S=S_{{\Gamma}}\cup{S_{{H}}}$中分析解决$s_i$和$s_j$间最短路径的问题.当采样点个数$\lambda\to\infty$时, 求得的$s_i$与$s_j$之间最短路径即为测地距离, 即

其中, $k_1, \cdots, k_\Delta$为最优路径上中间节点对应的索引.

对于原始的测地距离计算方法, 如Fast marching算法等, 其是在均匀致密的网格划分下求取测地距离.而对于本文方法而言, 其可视作经过化简后仅保留轮廓采样点的结果, 进而利用最短路径方法求取测地距离.对于$N_b\times{N_b}$的二值图像, Fast marching算法时间复杂度为O$\left(\lambda\times{{N_b}^2}\times{\log{N_b}}\right)$, 其随图像尺寸$N_b$的增大显著增加.此外, 该算法底层运算是求解二次方程的最大值, 其过程复杂耗时.本文利用Bellman-Ford算法时间复杂度为O$\left(\lambda\times{2\lambda}\times{E_G}\right)$, 算法的底层运算是比较求和, 分析计算简单, 其中$E_G$为图模型$G$边的数目.可见, 本文方法的算法复杂度不受图像尺寸影响.此外, 由于$E$中已包含了很多最短路径, 也能有效减少算法迭代次数.第4.1节将通过实验对比两种方法的计算效率, 说明本文方法的优势.

2.2   地貌模糊形状上下文

为了更好地描述采样点的分布情况, 本文在特征提取过程中引入模糊直方图^[13], 进而构造出了地貌模糊形状上下文.

分别对$\log{r}$和$\theta$均匀划分得到$M$个模糊子集$F_1^{\log{r}}, \cdots, F_M^{\log{r}}$和$N$个模糊子集$F_1^\theta, \cdots, F_N^\theta$, 进而可得模糊隶属度函数$\mu_{F_m^{\log{r}}} \left({\log{r}}\right)$和$\mu_{F_n^\theta}\left(\theta\right)$如式(10) 和(11) 所示.

进一步可得二维模糊子集$F_{m, n}$.二维模糊子集$F_{m, n}$对应的模糊隶属度函数为

以集合$P=\{p_1, \cdots, p_\lambda\}$中的$p_i\in{\bf{R}}^2$为参考, 以$\mu_{F_{m, n}}^i\left(q\right)$表示$q\in{P}$的模糊隶属度函数, $q\ne{p_i}$, 可得模糊直方图$H_i^F=\{h_i^F\left({m, n}\right):1\le{m}\le{M}, 1\le{n}\le{N}\}, $

沿极角方向对直方图进行归一化, 可得$\bar{H}_i^F=\{\bar{h}_i^F\left({m, n}\right):1\le{m}\le{M}, 1\le{n}\le{N}\}$

在构造模糊直方图的过程中, 本文以地貌空间中测地距离分析表示采样点间距离.为了更好地反映采样点之间的空间关系, 引入不同参数$\eta$下地貌空间的测地距离分别构造形状描述符.

在地貌参数$\eta$取值逐渐增大的过程中, 采样点间测地距离发生改变的情况越来越少, 因而提取的形状特征也逐渐趋于不变.参照文献[12]在形状特征提取过程中选择8组地貌空间, 本文结合$\eta$与形状特征变化的关系, 设置$\eta_k=\left(1-\cos\left(\frac{\pi}{20}{\left(k-1\right)}\right)\right)\times{ED_{\rm{avg}}}$, $1\le{k}\le{7}$; 当$k=8$时, $\eta_k=\infty$, 其中$ED_{\rm{avg}}$表示采样点间欧氏距离的均值.

将在$\eta_k$对应的地貌空间中, 以采样点$p_i\in{P}$为参考生成的$\bar{H}_{i, k}^F=\{\bar{h}_{i, k}^F\left({m, n}\right):1\le{m}\le{M}, 1\le{n}\le{N}\}$定义为地貌模糊形状上下文.对于不同形状上两点$p_i\in{P}$和$q_j\in{Q}$, 在$\eta_k$对应地貌空间中的匹配损失函数可表示为

相对框架下构造对数极坐标直方图过程中, 不同采样点对应的全局信息通常比较接近, 难以起到判别作用.因此在形状特征提取过程中, 选择距离参考点较近的直方图片段分析匹配损失函数.因而本文选择在$\log{r}$方向下均匀划分8个模糊子集, 选取前6个模糊子集构造对数极坐标模糊直方图, 并沿$\theta$方向划分12个模糊子集, 即式(15) 中设置$M=6$, $N=12$.

3.   基于地貌模糊形状上下文的特征匹配

在基于轮廓点集的形状匹配方法中, 特征匹配对应了分析采样点间对应关系的过程.在构造地貌模糊形状上下文形状特征的基础上, 本节进一步结合动态规划方法分析不同形状轮廓采样点间对应关系, 进而得到形状匹配的结果.

传统方法选择一个合适的地貌空间分析两形状间距离, 通过选择折衷的测地距离代替内距离或欧氏距离.但是对于一对相似的形状而言, 很多情况下轮廓上不同位置片段在相同的地貌空间下难以很好地匹配, 往往需要在不同地貌空间下分析各轮廓片段间距离, 在此基础上进一步整合得到采样点间对应关系.

因此在形状特征匹配过程中, 本文首先筛选出不同地貌空间下地貌模糊形状上下文最优的匹配结果, 而后在得到对应距离矩阵的基础上进一步分析采样点对应关系.对于以$\lambda$个采样点表示的形状$P$和$Q$, 分别得到对应的形状特征集合$\{\bar{H}_{i, k}^F:1\le{i}\le{\lambda}, 1\le{k}\le{K}\}$和$\{\bar{H}_{j, k}^F:1\le{j}\le{\lambda}, 1\le{k}\le{K}\}$, 不同地貌空间下形状描述符匹配的最优结果构成的$\lambda\times{\lambda}$矩阵$D$可由下式得到

轮廓采样点顺序关系已知的基础上, 使用动态规划算法分析$P$和$Q$上各点间对应关系.对于$\lambda\times{\lambda}$维的矩阵$DT$, 初始化以下的元素

并利用下式更新其他元素

其中, $\tau$是惩罚参数, $1\le{i}\le\lambda$, $1\le{j}\le\lambda$.形状间距离可以表示为$Dis\left(P, Q\right)= DT(\lambda, \lambda)$.

为克服目标旋转对形状匹配造成的影响, 进一步将矩阵$D$进行$G$次循环移位, 第$g$次循环移位对应矩阵$D_g$

其中, $1\le{g}\le{G}$, $w_g=g\times{\rm{ceil}}\left({\frac{\lambda}{G}}\right)$.在利用动态规划进行特征匹配时, 设置$G$为较小的整数^[10], 本文实验过程中设置$G=8$.最终分析得到对应的$DT_g(\lambda, \lambda)$, 形状间距离$Dis\left(P, Q\right)$可以由下式得到

从本节的分析可知, 由形状特征计算得到矩阵$D$的时间复杂度为O$\left(K\times{{\lambda}^2}\right)$, 在此基础上分析采样点间对应关系的算法复杂度为O$\left(G\times{{\lambda}^2}\right)$.由于参数$K$和$G$均取值较小, 可知形状特征匹配时间复杂度为O$\left({\lambda}^2\right)$.

4.   数据仿真

为了验证本文所提方法的有效性, 将分别从形状特征提取效率和形状检索结果精度两个角度进行设计实验并加以分析.为了对比公平, 本文参考文献[10, 13]的工作, 实验中均设置形状轮廓的采样点数目为$100$, 即$\lambda=100$.

4.1   形状特征提取效率

首先, 通过设计实验对不同方法下测地距离计算时间进行分析比较.对于不同尺寸下三幅相同的二值图像, 分别分析计算采样点间的测地距离.

图 4(a)给出了实验所用的三幅具有不同特点的二值图像, 包含简单边界、复杂边界和不规则边界的情形, 实验过程中设图幅大小为$N_b$像素$\times{N_b}$像素, $N_b=50, 100, 150, \cdots, 500$.实验在相同环境下运行, 计算机配置是3.60 GHz和8 G内存, 两种方法均通过Matlab与VC混合编程实现.选择文献[11]中的Fast marching算法和本文提出了最短路径方法进行对比, 本文最短路径方法通过Bellman-Ford算法实现.不同方法下对同一幅图像分别进行$100$次实验, 取平均时间作为最终结果.

图 4  分析不同方法计算测地距离效率

Fig. 4  Efficiency comparison of computing geodesic distances by using different methods

下载: 全尺寸图片 幻灯片

图 4(b)给出了用这两种方法分别计算各采样点之间的测地距离所需时间的比较, 横坐标表示图幅的大小$N_b$, 纵坐标表示计算时间的对数${\rm{log}}\left(t\right)$.从图中可以看出, 无论目标的轮廓边界为何种情况, Fast marching算法计算时间远远大于本文提出方法, 且Fast marching算法的计算时间随图像大小的增大而显著增加, 而本文方法对于不同大小的二值图像均能得到较高的计算效率.

为了更好地说明不同方法下的形状特征提取效率, 进一步选择一个完整的形状数据集分析比较.这里选择Kimia-99数据集^[14]进行仿真实验, 该数据集包含9个类别各11个样本, 部分样本的示例如图 5所示.分别用两种方法对该数据集下的全部99个样本进行形状特征提取, 特征提取过程中按照第2.2节的分析进行参数设置, 表 1给出了两种方法特征提取时间的结果比较.从表中可以看出本文所提方法能够有效改善形状特征提取过程的计算速度.

图 5  Kimia-99数据集中形状样本示例

Fig. 5  Examples of shapes in Kimia-99 database

下载: 全尺寸图片 幻灯片

表 1  Kimia-99数据形状特征提取时间比较(s)

Table 1  Comparison of the time used for shape feature extraction on Kimia-99 database (s)

方法	特征提取时间(s)
Fast marching[11]	208.56
本文方法	11.77

下载: 导出CSV 

| 显示表格

4.2   形状检索精度

为了验证本文所提形状匹配方法的性能, 此部分给出对不同数据进行仿真实验的结果, 并与其他文献中方法进行详细地分析比较.在实验过程中, 按照第2.2节和第3节给出的参数设置规则对本文所提方法参数进行设置.为了确定惩罚参数$\tau$, 对Kimia-99数据集进行仿真实验并做对比分析.在固定其他参数取值不变的基础上, 分别取$\tau=0.8, 1.2, \cdots, 4.0$, 可以得到如图 6所示的PR曲线.从图中可以看出, 本文方法对特征匹配过程中的惩罚参数并不敏感, $\tau$取值在1.2 ~ 3.2之间均能得到较好的匹配结果, 本文后续试验中设置$\tau=2.0$.

图 6  参数τ变化对应的PR曲线

Fig. 6  Precision-recall curves for different τ

下载: 全尺寸图片 幻灯片

在Kimia-99数据集和Kimia-216数据集^[15]两个样本数较少的数据集下进行形状匹配实验. Kimia-99数据集在第4.1节用于进行了形状特征提取实验, Kimia-216数据集包含18个类别各12个样本, 部分示例如图 7所示. 表 2和表 3分别列出了不同形状匹配方法在Kimia-99和Kimia-216数据集上得到的形状检索结果. 表 2和表 3中各列分别表示与查询样本近邻的检索结果所属类别正确与否, 其中包含了最接近的1 ~ 10组相关样本数目及合计相关样本数目.由表中结果可以看出, 对于Kimia-99和Kimia-216两个包含样本数较少的数据集, 本文所提方法能够较好地分析得到形状间的距离关系, 对比其他方法可以得到更准确的形状检索结果.

图 7  Kimia-216数据集中形状样本示例

Fig. 7  Examples of shapes in Kimia-216 database

下载: 全尺寸图片 幻灯片

表 2  Kimia-99数据在不同方法下检索结果比较

Table 2  Comparison of retrieval rates for different algorithms tested on Kimia-99 database

方法	1st	2nd	3rd	4th	5th	6th	7th	8th	9th	10th	全部
SC[6]	97	91	88	85	84	77	75	66	56	37	756
Hierarchical parts[16]	99	99	98	98	98	97	96	94	93	82	954
IDSC + DP[10]	99	99	99	98	98	97	97	98	94	79	958
MDS + SC + DP[10]	99	98	98	98	97	99	97	96	97	85	964
GM + SC[17]	99	99	99	99	99	99	99	97	93	86	969
Height functions[18]	99	99	99	99	98	99	99	96	95	88	971
FSC + SCS[13]	99	99	99	99	98	99	98	95	94	91	972
Symbolic representation[19]	99	99	99	98	99	98	98	95	96	94	975
AFSC	99	99	99	99	99	99	99	99	98	92	982

下载: 导出CSV 

| 显示表格

表 3  Kimia-216数据在不同方法下检索结果比较

Table 3  Comparison of retrieval rates for different algorithms tested on Kimia-216 database

方法	1st	2nd	3rd	4th	5th	6th	7th	8th	9th	10th	全部
Generative model[20]	216	216	214	212	212	207	203	190	179	175	2024
Shock edit[21]	216	216	216	215	210	210	207	204	200	187	2081
SC + DP[10]	216	216	215	210	210	209	208	204	200	191	2079
FSC + SCS[13]	216	216	215	214	213	214	210	201	193	188	2080
Path similarity[22]	216	216	215	216	213	210	210	207	205	191	2099
IDSC + DP[10]	216	216	215	211	211	210	211	207	203	198	2098
AFSC	216	216	216	214	214	215	209	207	209	199	2115

下载: 导出CSV 

| 显示表格

为验证本文方法在不同数据集下的有效性, 这里选择样本数较多的Tari-1000^[23]数据集进行仿真实验. Tari-1000数据集中包含50个类别各20个样本, 图 8给出了部分样本的示例.实验中选用Bull's eye score作为检索精度的评价指标:在一次形状检索过程中, 选择与查询形状最相似的40个形状样本, 统计其中与查询形状属于相同类别的样本数目, 计算对应的查全率.

图 8  Tari-1000形状样本示例

Fig. 8  Examples of shapes in Tari-1000 database

下载: 全尺寸图片 幻灯片

表 4列出了不同形状匹配方法在Tari-1000数据集上的形状检索结果, 可以看出对比其他文献中给出的形状匹配方法, 本文所提方法能够得到更好的形状检索结果.通过给出的实验结果可以看出, 本文所提形状匹配方法在不同规模的形状数据集下均能够获得较好的形状检索结果.

表 4  Tari-1000数据在不同方法下的结果比较

Table 4  Comparison of results for different algorithms tested on Tari-1000 database

方法	Bull's eye score
Tree edit + Context[23]	86.42
Similar and discriminative parts[24]	91.37
COP[25]	92.18
SC + DP[4]	94.17
Group-wised[26]	94.58
IDSC + DP[10]	95.33
ASC + DP[11]	95.44
AFSC	97.21

下载: 导出CSV 

| 显示表格

参考文献[3, 9, 12]的做法, 本文方法引入了轮廓点顺序关系作为先验信息, 能够更好地反映形状全局信息.对于包含顺序关系的轮廓点集, 可以在提取目标边缘的基础上采样得到.

5.   结论

鉴于地貌形状上下文存在的不足, 本文提出了一种基于改进地貌形状上下文的形状匹配方法.将地貌空间测地距离的求解近似为最短路径问题, 相比于经典算法, 本文方法有效地提高了形状特征提取效率.通过引入对数极坐标模糊直方图, 构造地貌模糊形状上下文形状特征, 其能够更好地描述形状轮廓信息.进一步引入动态规划方法分析不同地貌空间下形状间采样点对应关系, 能够准确地计算得到形状距离.通过对不同数据集样本进行仿真实验, 证明了本文所提方法具有良好的形状检索效果.