物体的边界轮廓是物体的重要特征, 基于物体边界轮廓的物体识别是计算机视觉和模式识别领域重要的研究内容, 并在字符识别、手势识别、生物医学图像分析、步态识别、商标识别等领域得到了成功的应用。然而, 由于形状的复杂性和应用的多样性, 针对形状的分析, 包括形状的表示、相似性度量和检索仍是当前的研究热点。

在应用中, 对形状的检索是以形状的相似性度量为基础的, 而形状的相似性度量又是以形状的表示为基础的, 因此, 形状的表示是形状分析的核心。构建具有仿射不变性, 同时又具有较好的可区分性的形状表示方法(也称为形状描述符)是形状研究的中心问题, 也是具有挑战性的工作。Yang等人^[1]对典型的形状表示方法及其相应的匹配算法做了综述。

形状上下文方法(SC)^[2]是形状表示中最为经典的方法, 并已成为形状表示事实上的基准。SC方法通过对形状的边界采样, 计算每个采样点与其余采样点之间的距离关系和角度关系, 为每个采样点建立一个称为“形状上下文”的特征。为了度量两个形状的相似性, SC方法采用二分图匹配并计算特征之间的匹配误差来度量形状的相似性。为了改进SC方法的效果, Ling等人^[3]提出了基于内部距离的形状表示方法取代SC方法中的欧氏距离, 使SC方法在处理具有绞合结构的形状表示和相似性度量上获得较好的效果。

在形状的空间关系特征方法中, 链码是一种简单直观的形状表示方法。基本的链码方法将形状表示为一组具有特定方向的线段的有序集合。为了提升基本链码方法的有效性, 后续研究者对基本链码方法做了改进^[4]。由于链码固有的对噪音的敏感性, 导致基于链码的方法不能得到理想的效果。几何复变换方法是形状的空间特征表示方法^[5], 该方法通过将形状的边界点表示为以形状的中心为参考点的复数序列, 进而可高效准确地判定简单形状的相似性；基于距离的相似不变形状描述符^[6], 该方法通过统计位于以形状的中心点为圆心的各种同心圆上的点的数目为特征建立形状的特征描述符；径向对称的二分形状描述符^[7], 该方法先计算形状的主轴和副轴, 以主轴和副轴所切割的形状的面积为特征建立形状的特征描述符。

在形状的变换域, 有效的方法包括傅里叶描述子和基于Radon变换的方法。傅里叶描述子方法包括基于边界的傅里叶描述子^[8]和基于区域的傅里叶描述子^[9]。基于边界的傅里叶描述方法首先建立形状边界点的特征函数, 然后对特征函数做1维傅里叶变换, 并将傅里叶变换的系数作为形状的描述符。基于区域的傅里叶描述方法, 也称为通用傅里叶描述子(GFD), 首先将形状的笛卡儿坐标变换到极坐标, 然后在极坐标下对形状做傅里叶变换, 最后, 将变换得到的傅里叶系数归一化后作为形状的描述符。由于Radon变换在图像分析中的良好性质, 出现了多种基于Radon变换的形状表示方法^[10-13], 并且这些年得到了较快发展。对Radon变换进行扩展, Wang等人^[14]提出的结构积分变换则通过正交透视来分析形状的性质并对形状进行表示, 因此能够更为精细地对形状的结构进行表示。

在形状多尺度不变量表示方法中, 典型的方法包括曲率尺度空间方法^[15]、多尺度积分不变量^[16]、多尺度不变描述符(IMD)^[17]等。在多尺度积分不变量方法中, 采用高斯函数作为核函数, 以标准差δ作为尺度, 并在不同的尺度下, 计算形状与高斯核函数的卷积, 将卷积结果作为权重计算每个形状点的特征值, 最后, 积分所有形状点的特征值并除以形状的面积, 得到指定尺度下的形状特征。把在多个尺度下得到的形状特征作为元素组成形状的特征向量, 并采用Wasserstein距离来度量形状的相似性误差。多尺度积分不变量在对多个典型的数据集的测试验证中均获得较好的结果。

目前对形状相似性判定的所有方法中, 除了几何复变换^[5]和基于边界的傅里叶方法^[8]外, 其他方法都是不可逆的, 也就是不能通过所建立的形状描述符重建原形状, 因此, 无法保证所得到的形状描述符客观地描述了原形状。深入分析几何复变换和基于边界的傅里叶方法可以发现, 这两个可逆的方法只能描述简单的形状:形状存在可获取的封闭边界轮廓并且不存在空洞。因此, 它们的适用范围有限。

本文提出一种新的形状表示、匹配、相似性度量方法, 称为圆内距离变换(ICD)。这种方法可对任意复杂形状进行表示、匹配、相似性度量和检索, 并且与形状的缩放、旋转及移位无关。不仅如此, 在两个形状相似时, 该方法还可以计算形状之间的缩放尺度、旋转角度。更为有益的是, 通过该方法得到的形状描述符, 可以重建原形状, 因此, 可以断言, 本文ICD方法能够反映形状的本质特征。

在笛卡儿坐标系下考虑如图 1所示的任意形状:记形状的边界点坐标为($x_{\rm 1}$, $y_{\rm 1}$)、($x_{\rm 2}$, $y_{\rm 2}$)、($x_{\rm 3}$, $y_{\rm 3}$)、…、($x_{n}$, $y_{n}$)。从边界点坐标中求出最小的$x$坐标分量、最小的$y$坐标分量、最大的$x$坐标分量、最大的$y$坐标分量, 分别记为$x_{\rm min}$、$y_{\rm min}$、$x_{\rm max}$、$y_{\rm max}$。那么, 形状将包含在以点

$ \left( {\frac{{{x_{\max }} - {x_{\min }}}}{2},\frac{{{y_{\max }} - {y_{\min }}}}{2}} \right) $

(1)

为圆心、以

$ \sqrt[2]{{{{\left( {{x_{\max }} - {x_{\min }}} \right)}^2} + {{\left( {{y_{\max }} - {y_{\min }}} \right)}^2}}} $

(2)

为直径的圆中, 这个圆是形状的外接圆, 求出形状的最小外接圆的直径。

经过最小外接圆的最底部点作平行于$x$轴的直线, 记这条直线为$L$, 将区间[$x_{\rm min}$, $x_{\rm max}$]进行等间隔划分, 记这些分点为$x_{\rm 1}=x_{\rm min}、x_{\rm 2}、x_{\rm 3}、x_{\rm 4}、…、x_{k-1}、x_{\rm k}=x{\rm max}$, 过这些分点作垂直于$L$的直线, 求出每条等分间隔线与形状的交点, 记第$i$条等分间隔线与形状的交点为$x_{i, 1}、x_{\rm i, 2}、…、x{i,n}, i=1, 2, …, k$, 如图 2所示。

对每条等分间隔线与形状的交点, 求出相邻交点之间的距离(若只有一个交点, 则记距离为0), 并构建距离向量[$d_{i, 0}, d_{i, 1}, d_{ i, 2}, …, d_{ i, n-1}]^{\rm T}$, 其中$d_{\rm i, 0}$是第一个交点与直线$L$的距离, T表示转置, $i=1, 2, 3, …, k$。记距离向量的最大维度为$m$+1, 并且, 对维度小于$m$+1的距离向量通过在尾部补0的方式形成维度为$m$+1的距离向量, 则$k$条等分间隔线将构建一个维度为($m$+1) ×$k$的距离矩阵$\mathit{\boldsymbol{A}}_{\rm 1}$, 即

$ {\mathit{\boldsymbol{A}}_1} = \left[ {\begin{array}{*{20}{c}} {{d_{1,0}}}&{{d_{2,0}}}&{{d_{3,0}}}& \cdots &{{d_{k,0}}}\\ {{d_{1,1}}}&{{d_{2,1}}}&{{d_{3,1}}}& \cdots &{{d_{k,1}}}\\ {{d_{1,2}}}&{{d_{2,2}}}&{{d_{3,2}}}& \cdots &{{d_{k,2}}}\\ \vdots&\vdots&\vdots &{}& \vdots \\ {{d_{1,m}}}&{{d_{2,m}}}&{{d_{3,m}}}& \cdots &{{d_{k,m}}} \end{array}} \right] $

以最小外接圆的圆心为中心, 逆时针方向将形状旋转$θ$角, 重复上述过程, 如图 3所示, 得到形状的又一个距离矩阵$\mathit{\boldsymbol{A}}_{\rm 2}$。令$N$=[360/$θ$], 重复上述步骤$N$-2次, 得到形状的所有距离矩阵$\mathit{\boldsymbol{A}}_{\rm 1}、\mathit{\boldsymbol{A}}_{\rm 2}、…、\mathit{\boldsymbol{A}}_{N}$。

以距离矩阵$\mathit{\boldsymbol{A}}_{\rm 1}、\mathit{\boldsymbol{A}}_{\rm 2}、\mathit{\boldsymbol{A}}_{\rm 3}、…、\mathit{\boldsymbol{A}}_{N}$为元素, 构成形状的特征矩阵$\mathit{\boldsymbol{F}}, \mathit{\boldsymbol{F}} = [\mathit{\boldsymbol{A}}_{\rm 1}\mathit{\boldsymbol{A}}_{\rm 2}\mathit{\boldsymbol{A}}_{\rm 3}…\mathit{\boldsymbol{A}}_{N}]^{\rm T}$。通过这种变换方式可以将任意形状从笛卡儿坐标空间表示变换到距离特征空间的矩阵表示, 称这个变换为形状的圆内距离变换(ICD变换), 记参数为$k$和$θ$的ICD变换为ICD < $k, θ$>。

通过圆内距离变换, 将形状的笛卡儿坐标空间表示变换到了距离特征空间的矩阵表示。观察如图 4所示的4个形状, 其中图 4(a)—(c)是相似的形状, 但是在大小、朝向和位置上发生了变化, 图 4(d)则是与其他3个形状不同的形状。

取ICD变换中的参数$k$为100、$θ$为6, 对图 4中的4个形状做ICD < 100, 6>的变换, 得到4个形状的特征矩阵。采用图像映射的方式将4个形状的特征矩阵进行显示以便观察形状特征矩阵间的关系, 如图 5所示, 其中图 5的各子图分别对应图 4的4个形状。

观察图 5中的每个图像可以发现: 图 5(a)(b)几乎具有相同的显示外观；若将图 5(c)的图像在垂直方向上向上做循环移位, 则图 5(c)与图 5(b)也几乎具有相同形式的显示外观；图 5(d)与其他3个图像都不具有相似的显示外观。这种现象不是偶然的, 而是ICD变换所固有的性质。

定理  形状的圆内距离变换具有平移、缩放和旋转不变性, 即对两个发生了位置平移、尺度缩放或角度旋转的相似形状, 它们的ICD特征矩阵经过归一化处理后是相等的。

证明  设原形状$\mathit{\Omega }$的定义函数为$f(x, y$), 其定义域为$\mathit{\boldsymbol{D}}$, 即

$ \mathit{\Omega } = \left\{ {\left( {x,y} \right)\left| {f\left( {x,y} \right) = 0,\left( {x,y} \right) \in \mathit{\boldsymbol{D}}} \right.} \right\} $

考虑平移、缩放和旋转3种情况:

1) 平移不变性。假设形状$\mathit{\Omega }$在$x$轴和$y$轴上分别发生了$α$和$β$的位移, 则位移后的形状$\mathit{\Omega }_{\rm 1}$可表示为

$ {\mathit{\Omega }_1} = \left\{ {\left( {x,y} \right)\left| {f\left( {x - \alpha ,y - \beta } \right) = 0,\left( {x,y} \right) \in \mathit{\boldsymbol{D}}} \right.} \right\} $

考虑ICD变换中对形状实施第$i$次旋转后的第$j$条等分间隔线与形状的交点。对形状$\mathit{\Omega }$, 设这些交点为($x_{\rm 1}, y_{\rm 1})、(x_{\rm 2}, y_{\rm 2})、…、(x_{n}, y_{n}$), 则对$\mathit{\Omega }_{\rm 1}$, 这些交点为($x_{\rm 1}-α, y_{\rm 1}-β)、(x_{\rm 2}-α, y_{\rm 2}-β)、…、(x_{n}-α, y_{n}-β$), 显然, 对于$\mathit{\Omega }$和$\mathit{\Omega }_{\rm 1}$, 它们各自的第$j$条等分间隔线与形状的相邻交点之间的距离相等, 从而它们的距离向量是相等的, 因此, 它们的特征矩阵是相等的。

2) 缩放不变性。假设形状$\mathit{\Omega }$发生了因子为$δ$的缩放, 则缩放后得到的形状$\mathit{\Omega }_{\rm 2}$可表示为

$ {\mathit{\Omega }_2} = \left\{ {\left( {x,y} \right)\left| {f\left( {\delta x,\delta y} \right) = 0,\left( {x,y} \right) \in \mathit{\boldsymbol{D}}} \right.} \right\} $

考虑ICD变换中对形状实施第$i$次旋转后的第$j$条等分间隔线与形状的交点。对形状$\mathit{\Omega }$, 设这些交点为($x_{\rm 1}, y_{\rm 1})、(x_{\rm 2}, y_{\rm 2})、…、(x_{n}, y_{n}$), 则对$\mathit{\Omega }_{\rm 2}$, 这些交点为($δx_{\rm 1}, δy_{\rm 1})、(δx_{\rm 2}, δy_{\rm 2})、…、(δx_{n}, δy_{n}$), 显然, 形状$\mathit{\Omega }_{\rm 2}$的相邻交点之间的距离是形状$\mathit{\Omega }$的$δ$倍。对形状$\mathit{\Omega }_{\rm 2}$的相邻点间的距离都除以$δ$进行特征归一化, 则它们各自的第$j$条等分间隔线与形状的相邻交点之间的距离相等, 从而它们的距离向量是相等的, 因此, 它们的特征矩阵是相等的。

3) 旋转不变性。假设形状$\mathit{\Omega }$发生了逆时针角度为$θ$的旋转, 则旋转后得到的形状$\mathit{\Omega }_{\rm 3}$可表示为

$ \begin{array}{l} {\mathit{\Omega }_3} = \left\{ {\left( {x,y} \right)\left| {f\left( {x\cos \theta + y\sin \theta , - x\sin \theta + } \right.} \right.} \right.\\ \left. {y\cos \theta = 0,\left( {x,y} \right) \in \mathit{\boldsymbol{D}}} \right\} \end{array} $

首先将形状$\mathit{\Omega }_{\rm 3}$顺时针旋转$θ$角, 再考虑ICD变换中对形状实施第$i$次旋转后的第$j$条等分间隔线与形状的交点。对形状$\mathit{\Omega }$, 设这些交点为($x_{\rm 1}$, $y_{\rm 1}$)、($x_{\rm 2}$, $y_{\rm 2}$)、…、($x_{n}$, $y_{n}$), 则对$\mathit{\Omega }_{\rm 3}$, 这些交点为($x_{\rm 1}$cos($θ$)+$y_{\rm 1}$sin($θ$), -$x_{\rm 1}$sin($θ$)+$y_{\rm 1}$cos($θ$)、($x_{\rm 2}$cos($θ$)+$y_{\rm 2}$sin($θ$), -$x_{\rm 2}$sin($θ$)+$y_{\rm 2}$cos($θ$)、…、($x_{n}$cos($θ$)+$y_{n}$sin($θ$), -$x_{n}$sin($θ$)+$y_{n}$cos($θ$)。通过简单的数学推导可知, 对于$\mathit{\Omega }$和$\mathit{\Omega }_{\rm 3}$, 它们各自的第$j$条等分间隔线与形状的相邻交点之间的距离相等, 从而它们的距离向量是相等的, 因此, 它们的特征矩阵是相等的。

证毕。

由于形状在数字化时的离散误差、旋转形状时计算机存储精度误差和在数字图像中求直线与形状交点时的误差, 两个相似的形状的特征矩阵不会严格地相等。在实际应用中, 当两个形状的特征矩阵的误差小于某个阈值时, 可判定两个形状是相似的。

基于以上对ICD变换性质的分析, 对于任意两个需要进行相似性判定的形状$\mathit{\Omega }_{\rm 1}$、$\mathit{\Omega }_{\rm 2}$, 通过ICD < $k$, $θ$>变换求出它们的特征矩阵, 分别记为

$ {\mathit{\boldsymbol{F}}_1} = {\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{A}}_1}}&{{\mathit{\boldsymbol{A}}_2}}&{{\mathit{\boldsymbol{A}}_3}}& \cdots &{{\mathit{\boldsymbol{A}}_\mathit{\boldsymbol{N}}}} \end{array}} \right]^{\rm{T}}} $

$ {\mathit{\boldsymbol{F}}_2} = {\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{B}}_1}}&{{\mathit{\boldsymbol{B}}_2}}&{{\mathit{\boldsymbol{B}}_3}}& \cdots &{{\mathit{\boldsymbol{B}}_\mathit{\boldsymbol{N}}}} \end{array}} \right]^{\rm{T}}} $

式中, $N$=[360/$θ$], $\mathit{\boldsymbol{A}}_{i}$和$\mathit{\boldsymbol{B}}_{i}$分别是形状$\mathit{\Omega }_{\rm 1}$、$\mathit{\Omega }_{\rm 2}$在第$i$-1次旋转后的距离矩阵, $i$ =1, 2, …, $N$。采用如下计算公式可以计算两个形状的特征矩阵的相似性误差, 令

$ {S_1} = \sum\limits_{i = 1}^N {\sum\limits_{j = 1}^k {\sum\limits_{n = 1}^m {{\mathit{\boldsymbol{A}}_{i,j,n}}} } } $

(3)

$ {S_2} = \sum\limits_{i = 1}^N {\sum\limits_{j = 1}^k {\sum\limits_{n = 1}^m {{\mathit{\boldsymbol{B}}_{i,j,n}}} } } $

(4)

$ \lambda = {S_1}/{S_2} $

(5)

$ \begin{array}{*{20}{c}} {\eta = \mathop {\arg \min }\limits_{t,1 \le t \le N} \left( {\left| {{\mathit{\boldsymbol{A}}_1} - \lambda \times {\mathit{\boldsymbol{B}}_t}} \right| + } \right.}\\ {\left| {{\mathit{\boldsymbol{A}}_2} - \lambda \times {\mathit{\boldsymbol{B}}_{t + 1}}} \right| + \cdots + \left| {{\mathit{\boldsymbol{A}}_{N - t + 1}} - \lambda \times {\mathit{\boldsymbol{B}}_N}} \right| + }\\ {\left| {{\mathit{\boldsymbol{A}}_{N - t + 2}} - \lambda \times {\mathit{\boldsymbol{B}}_1}} \right| + \left| {{\mathit{\boldsymbol{A}}_{N - t + 3}} - \lambda \times {\mathit{\boldsymbol{B}}_2}} \right| + \cdots + }\\ {\left| {{\mathit{\boldsymbol{A}}_N} - \lambda \times {\mathit{\boldsymbol{B}}_{t - 1}}} \right|/{S_1}} \end{array} $

(6)

式中, $\mathit{\boldsymbol{A}}_{i, j, n}$是形状$\mathit{\Omega }_{\rm 1}$经过第$i$-1次旋转后, 第$j$条等分间隔线与形状产生的第$n$个交点与第$n$+1个交点之间的距离, 类似的, $\mathit{\boldsymbol{B}}_{i, j, n}$是形状$\mathit{\Omega }_{\rm 2}$经过第$i$-1次旋转后, 第$j$条等分间隔线与形状产生的第$n$个交点与第$n$+1个交点之间的距离。$N$=[360/$θ$], $θ$和$k$分别是ICD变换的参数, $m$是形状的距离特征向量的最大维度。

式(6) 中, 当矩阵$\mathit{\boldsymbol{A}}_{i}$与$\mathit{\boldsymbol{B}}_{j}$的维度不同时, 其中$i$=1, 2, …, $N$, $j$=1, 2, …, $N$, 通过在矩阵的末行或矩阵的末列补0使它们具有相同的维度。由式(6) 计算得到的参数$t$称为相似性位置参数, $\eta $为相似性误差。

根据应用的要求, 当相似性误差$\eta $小于等于一个指定的阈值时, 可判定形状$\mathit{\Omega }_{\rm 1}$、$\mathit{\Omega }_{\rm 2}$是相似的, 此时, 使用如下公式计算它们的旋转角度$r$和缩放尺度$s$分别为

$ r = \left( {t - 1} \right) \times \theta $

(7)

$ s = \lambda $

(8)

ICD能够对任意形状进行表示和相似性判定。为了验证这一点, 制作了如图 6所示的40幅形状, 存储它们的图像大小均为512×512像素。40幅形状分为8组, 每组包含5幅形状, 每组的第1幅形状为基础形状, 后续的4幅形状则是通过对第1幅形状进行少许形变或添加少许随机噪音构成的。

同时, 为了验证ICD算法与形状的位移、缩放和旋转无关, 对图 6所示的40幅基本形状中的每幅形状生成2幅相似的但是发生了随机位移、随机缩放和随机旋转的形状, 共生成80幅形状, 如图 7所示。

一个良好的形状表示和相似性度量方法应该能够对发生少许形变的形状的相似性进行精确地计算和判定。下面的实验将针对由图 6和图 7所示的120幅形状进行, 包括相似性判定和形状检索实验, 实验中取ICD参数$k$=100、$θ$=1。

为了能够直观地观察ICD在形状的相似性判定方面的有效性, 采用如表 1所示的列表形式对两组形状进行交叉相似性判定实验, 其中表 1的第1行由图 6所示的8个基础形状构成, 表 1的第1列则由图 7所示的部分形状构成。对其中的每对形状的相似性计算结果中包括3个参数:第1个参数为相似性误差, 第2个为旋转角度, 第3个为尺度缩放。

从表 1可以看出, 在形状的相似性判定上, ICD给出了与人类视觉一致的判定结果:对相似的形状对, ICD判定它们是相似的, 如表 1中加粗数字；而对于不是相似的形状对, ICD则判定它们不是相似的。一个有益的现象是, ICD计算得到的相似性误差的数值客观地反映了形状的相似性差异, 例如, 对表 1的第2列的正方形形状, 虽然第3行的曲边正方形与正方形不是相似的, 但是它与正方形的相似性误差要小于其他行的形状；再例如第3列的五角星形状, 虽然它与第5行的发生了缩放、旋转及扭曲的五角星形状不是相似的, 然而, 它们的相似性误差要小于其他行的形状。类似的情况还发生在第6列和第9列的形状。观察表 1还可以发现, 对于相似的形状, 它们的相似性误差均小于10.0这个值, 在实际应用中, 可根据对形状相似性要求的严格程度选取合适的阈值, 实验也同时表明, 10.0是一个理想的误差参考阈值。

度量检索方法优劣的传统指标是查准率和查全率, 但是对于形状检索, 更为常用和全面的测试指标则是称为“Bullseye score”^[16]的测试得分。具体方法是:以形状库中每类形状的每个形状为检索目标对形状库进行检索, 从形状库中检索出2倍于该类形状个数的最优匹配形状, 并从中统计正确的形状个数。采用“Bullseye score”方法针对图 6和图 7的所有形状进行测试, 结果如图 8所示, 其中, 横坐标表示图 6的基本形状编号, 也就是形状类型编号, 采用顺序编号, 第1个形状的编号为1, 第2个为2, 以此类推；纵坐标表示每类形状的测试得分。

从图 8可以看出, 40个类型的形状中, 除了编号为5和编号的20的形状类型外, 其余的所有形状类型的测试均得到了满分, 这说明ICD在形状特征描述和相似性判定方面有出色表现。观察编号为5和编号为20的形状类型, 发现它们分别是编号为1和编号为16的形状类型添加随机噪音而构成的形状类型, 这说明, ICD对噪音比较敏感: ICD能够发现形状类型之间的微小变化, 当然也包括噪音。

MPEG-7形状库是经典的形状库, 用于检验形状表示和检索算法的性能。基于这个基准的形状库, 可对各种形状表示和分类算法的性能进行比较。MPEG-7形状库包含70个类, 每个类包含20个类似但有些形变的形状, 因此, MPEG-7形状库共有1 400个形状。图 9所示的形状由MPEG-7形状库70个类的第1个形状构成。

为了测试本文算法的有效性, 将本文算法与文献[2]的SC方法、文献[10]的HRT方法和文献[9]的GFD方法进行比较实验。由于本文算法、SC算法只能针对形状边界, HRT方法针对形状的全部像素点, GFD方法既可以针对于形状边界又可以针对形状的全部像素点, 为此, 提取MPEG-7每个形状的边界。图 10所示的形状是图 9的示例形状的边界形状。

对SC方法, 按文献[2]的建议对边界点进行均匀采样, 对每个形状采样100个边界点, 径向半径数目取5, 角度数目取12；对HRT方法, 按文献[10]的建议, 选取直方图数目$N$=16；对GFD方法, 按文献[9]的建议, 选择径向数目参数为5, 角度数目参数为12。测试方法是将70个类型的第1个形状作为检索目标从1 400个形状中进行检索, 并从40个最优结果中计算正确形状的数目, 测试得分结果如图 11所示, 其中横坐标表示形状类型编号, 纵坐标表示各个方法的测试得分。

从图 11可以看出, 针对不同类型的形状, ICD方法、SC方法、HRT方法和GFD方法都有各自的特点, 从图 11中难以辨识它们的优势和不足。为了能够直观地观察4种方法的得分, 取所有形状类型的平均得分作为各个方法的最后检索得分, 结果如图 12所示。

从图 12可以看出, 总体上, ICD方法在形状检索上的综合得分要高于其他3个方法近20%。不仅如此, 在判定形状相似的情况下, ICD方法还能判定相似形状之间的尺寸缩放和角度旋转, 因此, 相比于其他方法, ICD方法能够给出形状间的更多信息。

ICD方法是可逆的, 也就是说, 可以通过ICD的特征矩阵重建原形状, 这也是ICD方法优于其他方法又一特性。由于ICD可以重建原形状, 因此可以断言, ICD方法所建立的形状特征矩阵能反映原形状的本质特征。采用实验方式验证ICD的可逆性。

对如图 13所示的MPEG-7测试库中的几个形状, 分别取ICD的参数$k$为30、50、150和$θ$为1、6时, 对$k$和$θ$的不同组合对图 13的形状做ICD变换后重建, 结果如图 14所示。

从图 14可以看出, 当ICD的参数$k$取较小的值时, 重建的形状在轮廓上存在明显的不连续点。例如, 当$k$取30时, 如图 14的第2列和第3列所示, 所重建的形状存在明显的断点, 其中在第4个重建的形状中尤为明显(因为第4个形状的图像尺寸大于其他形状的图像尺寸)。当$k$逐步增大, 例如$k$为50时, 如图 14的第4列和第5列所示, 从视觉上看, 不连续点也逐步减少。当$k$为150时, 如图 14的第6列和第7列所示, 所重建的形状已经没有不连续点, 从视觉上, 重建的形状与原形状也非常相似。

通过这个重建实验还可以看出, ICD中的$θ$参数对建立形状特征的贡献不大, 但是$k$的取值对建立形状的特征是至关重要的。实验结果证明, 如果在应用中仅需要判定形状的相似性, 而不关注形状之间的角度旋转, 则$θ$取3是一个理想的经验值。

形状的描述和相似性判定是计算机视觉和模式识别的基本问题, 虽然已经出现一些成功的方法, 但是由于应用的多样性和复杂性, 仍然需要根据应用的不同需要研究新的方法。本文提出的形状圆内距离变换, 不仅能够计算形状之间的相似性误差及相似形状之间的尺度缩放和旋转角度, 还能通过形状的描述符重建原形状。理论证明和实验验证均表明本文方法是可行和有效的。由于本文方法是可逆的, 因此, 在特定的应用, 例如图像配准和刻度式图像数据读取的应用中, 能够更加精确地描述图像的本质特征。目前, 对于ICD方法, 当计算形状的相似性时, 如果还要精确地计算形状之间的角度旋转和缩放尺度, 则需要使用较大的$k$参数和较小的$θ$参数, 导致ICD方法在生成的形状特征矩阵及在度量特征矩阵的相似性误差时计算复杂度较高, 如何降低形状描述符的数据维度进而降低计算复杂度从而提升计算效率是本文后续的研究任务。