物体识别是计算机视觉、图像处理和模式识别应用中活跃的研究领域。视觉上，物体具有两类典型的可识别特征：物体的形状和物体的色彩纹理。因此，对物体的识别研究也基于物体的形状和色彩纹理这些可识别特征展开。

基于物体色彩纹理特征的物体识别是基于内容的图像检索的重要研究内容。典型的基于物体色彩纹理的识别方法包括基于色彩直方图的方法、基于纹理特征的方法和基于图像基元的方法等。在这方面的研究虽然取得了一定的研究成果，但目前还没有形成一个通用的可广泛应用的方法^[1-2]。

基于物体形状的物体识别则是模式识别的重要研究内容。经典的用于检测和识别数字图像中几何形状的方法是基于Hough变换进行的^[3-8]。原生的Hough变换将直线方程y=kx+b从平面坐标系统变换到ab参数空间，因此，通过Hough变换可以高效地检测和识别数字图形中的直线。对Hough变换进行拓展，可以识别规则的几何圆，但是，计算的时间复杂度和空间复杂度相比于识别直线将有所增加。通过Hough变换识别其他的非规则几何图形，由于复杂度的急剧增长而变得不适用。

为了能够识别数字图像中任意几何图形并对几何图形进行相似性判定、分类和检索，目前的研究方法是将这个过程分为两个阶段：第1阶段是建立形状的特征描述符；第2阶段是基于所建立的特征描述符对形状进行相似性判定、分类和检索。因此，所建立的形状特征描述符的完整性和可区分性，以及对所建立的特征描述符的相似性度量方法的优劣将直接决定形状的相似性判定、分类和检索的效果。

在形状的空间域，为了建立形状的特征描述符，有两种主要的方法：基于形状边界点特征建立形状的特征描述符和基于形状区域像素点特征建立形状的特征描述符。在基于形状边界点特征建立形状的特征描述符的方法中，由于形状的边界点决定了图形的形状，通过边界点的特征和边界点链码对形状的边界进行编码并建立形状的特征描述符^[9-10]是一种直观和直接的方法，但是这种基于边界点的特征和边界点链码的方法不能处理形状的旋转、缩放等几何变换。为了解决形状的几何变换的不变性问题，更为一般的方法是基于形状边界点的特征不变量来建立形状的特征描述符^[11-13]，通过边界点特征不变量，例如Shape Context，以及对面积、弧长及边界点到中心点的距离等特征进行归一化处理后的特征值，并通过多尺度计算来寻求特征的完整性和可区分性。采用边界点的特征不变量所建立的形状特征描述符可以较好地适应形状的几何变换，但是，建立形状特征描述符的时间复杂度非常高。在基于形状像素点特征建立形状的特征描述符的方法中，积分不变量和矩^[14-16]是建立形状的特征描述符的一种常用方法，在这种方法中，针对形状中的每个像素点，使用核函数建立每个像素点的局部特征，并通过特征筛选构建形状的特征描述符。与基于形状边界点的特征建立形状的特征描述符的方法类似，这类方法在建立形状的特征描述符时的时间复杂度也非常高。

在形状的变换域，为了建立形状的特征描述符，典型的方法包括：傅里叶描述子^[17]、小波描述符^[18]、角半径变换(ART)^[19]、R变换^[20]等，傅里叶描述子是其中较为常用的方法。在傅里叶描述子中，通过建立形状边界点的复坐标函数、曲率函数或者质心距离函数等特征函数来描述形状，然后通过傅里叶变换得到特征函数的复数形式的傅里叶系数，并由此构建形状的特征描述符。这些系数的高频分量表示形状的细节，而低频分量则表示形状的整体轮廓。由于傅里叶描述子只使用部分低频分量来近似地描述形状，对于轮廓有较突出变化或被区分对象仅有微小差别的识别问题中，这种方法不能得到理想的效果。

一旦建立了形状的特征描述符，基于所建立的特征描述符，需要对特征描述符的相似度进行度量。由于所建立的特征描述符一般采用特征向量的形式，因此，如果特征向量的维度相同，则可以使用向量的欧氏距离或向量的余弦夹角来度量特征描述符的相似性；如果采用不同维度的特征向量来表示几何形状的特征描述符，则使用动态规划算法或匈牙利算法计算最小花费并确定向量各个分量之间的映射关系，并取算法的最小值作为度量两个特征描述符的相似度。

目前最新的^[11]和经典的^[12]对图形形状的特征表示、相似性判定和分类算法中，对经典的MPEG-7^[21]形状库可以获得较好的分类结果，但是，在图形形状的相似性定量方面，这些算法都未能获得与人类视觉一致的判定结果。

本文提出一种称为GCT( geometry complex transform)变换的方法。通过GCT变换，将几何形状从实数空间的坐标表示变换到复数空间的特征向量表示，并在复数空间建立几何形状的特征描述符，进而将判定两个几何形状的相似性问题转化为判定它们的复数空间特征向量的相似性问题。与傅里叶描述子类似，GCT变换在复数空间建立形状的特征描述符，但是GCT变换采用不同的方法生成形状的复数空间特征。GCT变换优于傅里叶描述子的地方在于GCT变换在能够描述形状的全局特征的同时又能够描述形状的局部特征。GCT变换具有平移、旋转、尺度缩放不变性，它不仅可以判定数字图像中几何形状的相似性，给出与人类的视觉判断一致的相似性度量结果，对于两个相似的几何形状，该方法还可以计算出它们的旋转角度和尺度变换。

考虑如图 1所示的一个封闭的几何形状。

从平行于x轴、过形状的中心点且与x轴同向的射线为起始射线，沿逆时针方向对该封闭的几何形状进行360°角的整数k份等分(k为大于0的正整数，且为偶数)，如图 2所示。

求出每条射线在以中心点为起始点的射线及其反方向延长线与封闭的几何形状的交点坐标(数字图像矩形像素点概念下的交点，下同)，记这两个点到中心点距离分别为a_j和b_j。以距离a_j、b_j为参数构建复数a_j + b_ji，然后构建该封闭的几何形状的复数空间特征向量F=<a₁+b₁i,a₂+b₂i,a₃+b₃i,…,a_k+b_ki>。称这种将封闭的几何形状从实数空间变换到复数空间的变换为几何复变换( GCT)。k为GCT参数，记参数为k的GCT变换为GCT<k>。

定义1 封闭的数字几何形状。 对数字图像中的一个几何形状，如果从该几何形状边界的任一点为起始点出发，沿顺时针(或逆时针)方向对该几何形状的边界点进行遍历，经过有限步后将回到起始点，则称该数字几何形状是封闭的。

定义2 封闭的数字几何形状的中心。 假设封闭的数字几何形状的边界点在数字图像的坐标为(x₁,y₁),(x₂,y₂),(x₃,y₃),…,(x_n,y_n)。称坐标点(x₀，y₀)为该封闭的数字几何形状的中心，计算为

$\eqalign{ & {x_0} = {1 \over n}\sum\limits_{i = 1}^n {{x_i}} \cr & {y_0} = {1 \over n}\sum\limits_{i = 1}^n {{y_i}} \cr} $

(1)

坐标点(x₀，y₀)也称为封闭的数字图形的几何中心或重心。

定义3 GCT变换可判定的几何形状。 数字图像中的任意一个封闭的几何形状，如果该几何形状的中心位于该几何形状的内部且过中心点的任一直线与该几何形状有且只有两个交点，则称该几何形状是GCT变换可判定的，简称GCT可判定的。

由于GCT变换可判定的几何形状的中心点在几何形状内部，并且过中心点的任一直线与该几何形状有且只有两个交点，因此，GCT变换中用于构建复数空间特征向量的实部a与虚部b是存在的，也就是a≠0、b≠0并且a<+∞、b<+∞。

通过GCT变换，将GCT可判定的几何形状从实数空间的坐标表示变换到复数空间的特征向量表示，进而将判定两个几何形状的相似性问题转化判定它们的复数空间特征向量的相似性问题，而复数空间特征向量的相似性判定问题就是判定它们相位序列的相似性和强度序列的相似性问题。

定义4 复数空间特征向量的相位序列 。设一个GCT可判定的几何形状经过GCT<k>变换后得到的复数空间特征向量为F=<a₁+b₁i,a₂+b₂i,a₃+b₃i,…,a_k+b_ki>，复数空间特征向量F的相位序列S定义为

$S = \left( {{{{b_1}} \over {{a_1}}},{{{b_2}} \over {{a_2}}},{{{b_3}} \over {{a_3}}}, \ldots ,{{{b_k}} \over {{a_k}}}} \right)$

(2)

定义5 复数空间特征向量的强度序列。 设一个GCT可判定的几何形状经过GCT<k>变换后得到的复数空间特征向量为F=<a₁+b₁i,a₂+b₂i,a₃+b₃i,…,a_k+b_ki>，复数空间特征向量F的强度序列M定义为

$M = \left( {\root 2 \of {a_1^2 + b_1^2} ,\root 2 \of {a_2^2 + b_2^2} ,\root 2 \of {a_3^2 + b_3^2} , \ldots ,\root 2 \of {a_k^2 + b_k^2} } \right)$

(3)

定义6 相似的相位序列。 对于两个GCT变换可判定的几何形状Ω₁、Ω₂，使用GCT<k>变换得到它们的复数空间特征向量，分别记为F₁、F₂，计算它们各自的相位序列，分别记为S₁、S₂。令

$\eqalign{ & \delta = \mathop {min}\limits_{t,1 \le t \le k} \left( {\left| {{S_{2,t}} - {S_{1,1}}} \right| + {\rm{ }}\left| {{S_{2,t + 1}} - {S_{1,2}}} \right| + \ldots + } \right. \cr & \left| {{S_{2,k}} - {S_{1,k - t + 1}}} \right| + \left| {{S_{2,1}} - {S_{1,k - t + 2}}} \right| + \ldots + \cr & \left. {\left| {{S_{2,t - 1}} - {S_{1,k}}} \right|} \right)/\sum\limits_{i = 1}^k {{S_{1,i}}} \cr} $

(4)

式中，S_1,i是复数空间特征向量F₁的相位序列的第i个元素，S_2,i是复数空间特征向量F₂的相位序列的第i个元素，i=1,2,3,…,k。若δ为0，则称相位序列S₁与S₂是相似的，并称δ为相位序列相似性误差参数，t为相似性位置参数。

通俗地说，δ值的含义就是：在对S₂做一个周期拓展形成的序列S_T中寻找长度为k且与S₁序列的对应项的差的绝对值的和为最小的连续子序列，记这个子序列在S_T中起始位置为t，将这个子序列与S₁序列对应项的差的绝对值的和除以S₁的和记为δ。

定义7 相似的强度序列。 设复数空间特征向量F₁、F₂的相位序列在相似性位置参数t处相似，记F₁、F₂的强度序列分别记为M₁、M₂。设λ为一实数，令

$\begin{align} & \eta =\left( \left| {{M}_{2,t}}-\lambda \times {{M}_{1,1}} \right|+\left| {{M}_{2,t+1}}-\lambda \times {{M}_{1,2}} \right|+\ldots + \right. \\ & \left| {{M}_{2,k}}-\lambda \times {{M}_{1,k-t+1}} \right|+\left| {{M}_{2,1}}-\lambda \times {{M}_{1,k-t+2}} \right|+\ldots + \\ & \left. \left| {{M}_{2,t-1}}-\lambda \times {{M}_{1,k}} \right| \right)/\sum\limits_{i=1}^{k}{{{M}_{1,i}}} \\ \end{align}$

(5)

式中，M_1,i是复数空间特征向量F₁的强度序列的第i个元素，M_2,i是复数空间特征向量F₂的强度序列的第i个元素，i=1,2,3,…,k。若η等于0，则称强度序列M₁与M₂在位置参数t处是相似的，并称η为强度序列相似性误差参数。

定义8 相似的复数空间特征向量。 称复数空间特征向量F₁、F₂是相似的，当且仅当它们的相位序列是相似的，并且它们的强度序列也是相似的。

定理1 若两个数字图像中GCT可判定的几何形状Ω₁、Ω₂是相似的，则存在GCT变换参数k，使得它们的复数空间特征向量F₁、F₂也是相似的。

证明 在对两个相似的GCT可判定的几何形状Ω₁、Ω₂做参数为k的GCT变换之前，对它们的边界点坐标进行适当调整，使它们的中心点在平面直角坐标系中重合。考虑Ω₁相对于Ω₂的旋转，有两种需要考虑的情况：

情况1 Ω₁相对于Ω₂发生了360/k的整数倍的逆时针角度旋转，设这个整数为n。

由于Ω₁相对于Ω₂发生了360/k的整数倍的逆时针角度旋转，所以如果将Ω₁顺时针旋转(360/k)×n，它们的GCT<k>变换的k条射线及其反防线延长线将完全重合，如图 3所示。

因此，如果设Ω₂的复数空间特征向量F₂ =<a₁+b₁i,a₂+b₂i,a₃+b₃i,…,a_k+b_ki>，则Ω₁的复数空间特征向量F₁=<λ×a_n+λ×b_ni,λ×a_n+1 + λ×b_n+1i,…,λ×a_k + λ×b_ki,λ×a₁ + λ×b₁i,λ×a₂ + λ×b₂i,…,λ×a_n-1 + λ×b_n-1i>，其中λ为一实数标量，它是Ω₁相对于Ω₂的尺度缩放。计算F₁、F₂的相位序列S₁、S₂，强度序列M₁、M₂，显然，S₁与S₂在相似位置参数为n处是相似的，强度序列M₁与M₂在相似位置参数为n处也是相似的。因此，在情况1下，定理1是成立的。

情况2 Ω₁相对于Ω₂发生了360/k的非整数倍逆时针角度旋转。设这个旋转角度除以360/k的整数部分为n。

由于Ω₁相对于Ω₂发生了360/k的非整数倍的逆时针角度旋转，所以如果将Ω₁顺时针旋转(360/k)×n，它们的GCT<k>变换的射线将产生一个小于360/k的夹角，设这个夹角为β，如图 4所示。

由于Ω₁与Ω₂是相似的，所以Ω₁是Ω₂经过尺度缩放得到的，因此，Ω₁是Ω₂依据一定的像素点为参考点并且通过升采样或降采样像素点而得到的，称这些参考点为关键点。所以，虽然Ω₁与Ω₂的GCT<k>变换的射线存在一个β夹角，然而，由于几何形状是GCT变换可判定的，考虑到像素点的离散特性，当β小于某个值时，Ω₁与Ω₂的对应关键点虽然分布在不同的射线上，但是却是对应同一个关键点，因此，它们的GCT<k>变换的射线关系只能是如图 5所示的3种情况中的一种，其中虚线射线与实线射线的夹角为β。

因此，如果设Ω₂的复数空间特征向量F₂=<a₁+b₁i,a₂+b₂i,a₃+b₃i,…,a_k+b_ki>，则Ω₁的复数空间特征向量F₁=<λ×a_n + λ×b_ni,λ×a_n+1 + λ×b_n+1i,…,λ×a_k + λ×b_ki,λ×a₁ + λ×b₁i,λ×a₂ + λ×b₂i,…,λ×a_n-1 + λ×b_n-1i,>，其中λ为一实数标量，它是Ω₁相对于Ω₂的尺度缩放。计算F₁、F₂的相位序列S₁、S₂，强度序列M₁、M₂，显然，S₁与S₂在相似位置参数为n处是相似的，强度序列M₁与M₂在相似位置参数为n处也是相似的。

现在证明β是存在的。如果β的角度足够大，使得夹角为β的Ω₁与Ω₂的GCT<k>变换的射线不对应同一个关键点。此时，可对Ω₁与Ω₂使用参数为2×k的GCT<2×k>变换，这时，β将减小为原来的1/2，以此类推。所以，满足条件的β是一定存在的。因此，在情况2下，定理1也是成立的。证毕。

定理2 给定一个GCT变换的复数空间特征向量F，通过边界像素点线性插值，可以生成一个唯一的几何形状。

证明 采用作图法证明。

设复数空间特征向量F=<a₁+b₁i,a₂+b₂i,a₃+b₃i,…,a_k+b_ki>，其维度为k。

在平面直角系中，任选一点，设该点的坐标为(x₀，y₀)。

过该点作平行于x轴的射线，在以(x₀，y₀)为起始点的射线上截取一段线段，使其长度为a₁，设其端点坐标为(a_1,x，a_1,y)，再在该射线的反方向延长线上截取一段线段，使其长度为b₁，设其端点坐标为(b_1,x，b_1,y)。

重复以下步骤k/2次。在第j(2≤j≤k/2) 次：过点(x₀，y₀)逆时针作一条射线，使其与x轴的夹角为(360/k)×(j-1) ，在以(x₀，y₀)为起始点的射线上截取一段线段，使其长度为a_j，设其端点坐标为(a_j,x，a_j,y)，再在该射线反方向延长线上截取一段线段，使其长度为b_j，设其端点坐标为(b_j,x，b_j,y)。使用线性插值方式连接(a_j-1,x，a_j-1,y)与(a_j,x，a_j,y)，(b_j-1,x，b_j-1,y)与(b_j,x，b_j,y)。

最后使用线性插值方式连接(a_k,x，a_k,y)与(a_1,x，a_1,y)，(b_k,x，b_k,y)与(b_1,x，b_1,y)。这时，基于给定的复数空间特征向量F生成了一个几何形状。由于在作图中每一步方法都是唯一确定的，因此，生成的几何形状也是唯一的。证毕。

定理2说明，GCT变换是可逆的，也就是说，通过GCT变换得到的复数特征向量可以近似地重建原几何图形形状。

由于在数字图像中，任何封闭的几何形状都是多边形的近似，从定理2的证明过程可知，两个相似的复数空间特征向量所构建的几何形状经过相位相似位置参数t乘以360/k角度的旋转后，它们的对应边是平行的，并且对应边的比值也是相等的。基于定理1和定理2，有以下推论：

推论 两个GCT变换可判定的几何形状是相似的，当且仅当存在参数为k的GCT变换，使得它们的GCT<k>变换所生成的复数空间特征向量是相似的。

根据推论可知，为了判定两个几何形状的相似性，可以先使用GCT变换生成它们的复数空间特征向量，在生成它们的复数空间特征向量的同时，可以判断它们是否是GCT变换可判定的几何形状，若是，再在复数空间判定它们特征向量的相似性，进而根据推论判断两个几何形状的相似性。

在判定两个几何形状相似的情况下，由定理1的证明过程可知，两个相似的几何形状的旋转角度为

$A=\frac{360}{k}\times t$

(6)

并且，对于两个相似的几何图形，它们的强度比值就是它们的尺寸缩放因子，即

$\lambda =\sum\limits_{i=1}^{k}{{{M}_{2,i}}}/\sum\limits_{i=1}^{k}{{{M}_{1,i}}}$

(7)

式中，k为GCT变换参数，参数t为两个复数空间特征向量的相位相似性位置参数，式(7) 中的M_1,i、M_2,i分别为两个复数空间特征向量的强度序列元素，i=1,2,3,…,k。

定理1说明，对于两个相似的几何图形，一定存在GCT变换参数k，使两个几何图形的GCT变换的特征向量是相似的。

在使用推论判定两个复数空间特征向量的相似性时，理论上说，它们的相位序列相似性误差参数δ和强度序列相似性误差参数η都必须为0，但是，考虑到在对几何形状进行GCT变换时的离散性误差及几何形状的数字离散化误差，根据应用中对相似性要求的严格程度，可对δ和η各设置一个合理的阈值，当δ和η小于等于各自指定的阈值，则判定两个几何形状是相似的。

为了分析GCT变换在判定几何形状相似性中参数k的取值、相似性阈值δ及η的取值对判定结果的影响，制作了200幅大小、形状不同的几何形状测试库，其中的部分形状是相似的，部分形状是通过对原始形状进行变形而得到的几何形状。存储每幅几何形状的数字图像的大小为512×512像素。所制作的部分几何形状如图 6所示。

实验针对GCT变换参数k的存在性、δ及η的阈值选取对相似性判定结果的影响、GCT变换的时间复杂度3个方面进行，通过实验验证GCT变换相关性质的正确性。

在使用GCT变换对几何形状的相似性判定中，δ及η的取值直接影响到对相似性结果的判定，而δ及η的值又受到GCT变换参数k值的选取的影响。选取k分别为20、50、100、200、300、360、400、600、720时对几何形状进行实验，以检验k的取值对δ及η的影响。

表 1是针对图 7所示的一组梯形形状的交叉实验结果，这组梯形是通过对这组梯形的第1个形状进行平移、旋转、缩放及变形而得到的。表 1列出不同的参数k，对每对形状，计算δ及η的值，δ及η的精度为小数点后的两位。限于篇幅，表 1只列出k为20、100、360、400时δ及η的值。

从表 1可以看出，当k的取值从20变化到100时，针对测试用的类似梯形的几何形状，存在24对发生变化的δ及η的值；当k的取值从100变化到360时，存在10对发生变化的δ及η的值；而当取k=360及以上的值时，每组测试形状的δ及η的值将稳定为一确定的值，不再发生抖动，例如，在表 1中，观察k=360和k=400时，每组测试图形的δ及η的值已不再变化。

针对本文测试库中的所有GCT可判定的几何形状，分别取k为20、50、100、200、300、360、400、600、720对它们进行交叉测试，针对测试得到的δ及η值的变化总数进行统计，结果如图 8所示。

从图 8可以看出，随着k值增大，δ及η的变化总数逐渐减少，当取k=360及以上的值时，每组测试形状的δ及η的值将稳定为一确定的值。因此，针对GCT变换参数k对δ及η的影响，可以得出这样的结论：对于本文的测试库，当GCT变换的参数k的取值大于等于360时，对于任意一组几何形状，通过GCT变换生成它们的复数空间特征向量并计算它们之间的δ及η的值，δ及η将稳定为一确定的值。

这个结论与定理1的理论结果是一致的：定理1的理论证明过程说明这个结论具有一般性，而不仅仅只针对本文的测试库。可以断言，对任何一组几何图形，一定存在GCT变换参数k，使得使用GCT变换生成这组几何图形的复数特征向量是稳定和唯一的。基于这样的结论，针对本文的测试库，后续的实验中取GCT变换的参数k为360。

数学上对几何图形的相似性有严格的定义。例如图 9所示的几个几何图形中，只有第1号与第2号、第4号与第5号图形、第7号与第8号是相似的，虽然它们发生了一定的角度旋转及位置变化。观察图 9中的第1号与第3号图形，严格地说，它们不是相似的，但是它们“看起来有点相似”。在计算机模式识别及计算机视觉中，既需要对严格相似的几何图形也需要对“看起来有点相似”的几何图形给出一个定量的相似性度量。

GCT变换通过δ及η对两个几何图形的相似性给出了定量的度量结果。本文认为，δ及η在图形相似性度量中是同等重要的，为了计算几何图形相似性的定量度量，定义相似性综合参数为

$\psi =0.5\times \delta +0.5\times \eta $

ψ值越小则相似性越好。表 2给出图 9中的形状与测试基准库中的其他几何图形的相似性度量：给出了按ψ值从小到大的排序结果及相应的δ、η值。

表 2的测试1，使用几何图形圆与图 9中的几何图形进行相似性实验，并对结果按ψ从小到大进行排序。可以观察到，对于测试结果中ψ值小于等于0.05的几何图形，也就是编号为1、2、3的图形与待测试图形具有“一定的相似性”，其中编号为1、2的几何图形与待测试图形具有完全相似性，编号为3的几何图形的相似性没有编号为1、2的几何图形好：结果参数ψ如实的反应了它们的相似程度。不仅如此，ψ的数量值与人类视觉对相似性的直观观察是一致的。

表 2的测试2，使用一个不规则的几何图形与图 9中的几何图形进行相似性实验，并对结果按ψ从小到大进行排序。可以观察到，编号为5、4的几何图形与待测试图形在视觉上是完全相似的，可是对于编号为4的几何图形，它与待测试图形的结果参数值ψ并不为0，而是0.02。出现这种现象的原因是由于在制作这个测试基准库的图形时，对原始图形的坐标进行仿射变换(包括图形缩放和旋转)及对图形边界进行离散化处理的误差造成的(例如图形旋转后产生的斜边锯齿等)。虽然编号为4的几何图形与待测试图形存在仿射变换误差及离散化处理误差，但是编号为4的几何图形与待测试图形的参数ψ值(ψ=0.02) 仍小于具有一定形变的编号为6的几何图形的ψ值(ψ=0.05) 。从测试2可以看出，对于测试结果中ψ值小于等于0.05的几何图形，结果参数ψ反应了它们的相似程度。

表 2的测试3具有类似的结果。

表 2的测试4，待测试图形是一个不规则的七边形，它与编号为3的几何图形具有“一定的相似性”：这是因为在离散化的数字图像中，任何几何形状其本质都是多边形的近似，其中也包括规则的“圆”和不规则的“近似圆”。测试4还揭示了一个现象：待测试图形与编号为3的不规则“近似圆”的相似程度要好于编号为1和2的规则“圆”。

表 2的测试5和测试6，待测试图形与图 9中的几何图形不具有相似性，一个有趣的现象是，实验结果的ψ值所反映出来的事实与人类的视觉判断是一致的：对ψ值的排序结果反应了人类的视觉直观判断。

表 2的测试7的待测试图形，由于该图形不是GCT可判定的，因此，GCT直接给出了不可判定的结果，表示待测试图形不是GCT可判定的。

对表 2的数据做整体分析以及对本文的测试基准库中形状进行检索实验，从结果分析可以得到如下结论：对于本文提供的几何图形测试基准库，当ψ值小于等于0.05时，可以判定两个几何形状是相似的，并且这种相似性与人类的视觉判断是一致的。

对于ψ小于等于0.05的几何图形对，GCT变换判定它们是相似的，ψ值给出了相似性定量度量结果。通过GCT变换，在判定几何图形相似的情况下，利用式(6) (7) 还可以求出它们的旋转角度和缩放尺度，也就是求出angle的值和scale的值，其中angle值表示待测试图形相对于目标图形的顺时针旋转角度，scale的值表示待测试图形相对于目标图形的尺度缩放。对于表 2中判定为相似的几何图形，它们的旋转角度和尺度缩放如表 3所示。

观察表 3中的第1个待测试图形，它是编号为1的圆。当目标图形就是其本身时，ψ值为0，且angle为0，scale为1.00，这是正确的；当目标图形为编号为2的圆时，ψ值为0，scale为1.66，表示编号为1的待测试图形是目标图形的1.66倍，也就是待测试图形是编号为2的圆的1.66倍，这是正确的，但是angle却为359.1，其原因是因为在数字图像中，任何几何图形都是多边形的数字近似，因此，在GCT变换计算两个复数空间特征向量的相位序列相似性误差参数时，在位置参数t处能使δ达到最小。基于这个相似性位置参数t，可计算得到angle为360/k×t。从数字图像上也可以观察到这个现象：如果将待测试图形与目标图形按原始尺寸显示，图形将由于数字近似的原因而出现锯齿，如果将待测试图形旋转angle角度，则待测试图形与目标图形在这个角度有最佳的吻合度。同样的现象出现在表 3的第3个待测试图形与编号为8的目标图形中。表 3中的第2个待测试图形及表 3中的第4个待测试图形相对于目标图形的旋转角度和缩放尺度是正确的。

数字图像中的几何形状相似性判定算法的时间复杂度主要取决于生成几何形状的复数空间特征向量的时间复杂度和对两个复数空间特征向量计算δ及η值的时间复杂度。

首先分析生成几何图形的复数空间特征向量的时间复杂度。假设几何形状的边界点的数目为m，采用GCT<k>对几何形状生成复数空间特征向量。由于在生成复数空间特征向量时，需要对k条射线找到其与几何形状的交点(数字图像矩形像素点概念下的交点)，进而得到特征元素a+bi，因此，生成几何形状的复数空间特征向量的时间复杂度为O(m×k)。再分析对两个复数空间特征向量计算δ及η值的时间复杂度。因为相似位置参数可能为1到k的任何位置，所以，为了求得最小的δ，需要进行k×k次乘积及减法运算，因此，对两个复数空间特征向量计算δ及η值的时间复杂度为O(k×k)。由于数字图像的边界点数目m一般远大于GCT变换参数k，因此，GCT变换判定几何形状相似性算法的时间复杂度为O(m×k)。

通过以下实验验证对时间复杂度的分析结论：

1) 对测试库中的几何形状分别取GCT参数k为20、50、100、200、300、360、400、600、720，生成它们的复数空间特征向量，并计算时间消耗，结果如图 10(a)所示；

2) 固定GCT参数k为360，对图像边界点为546、718、959、1 046、1 174、1 424，生成它们的复数空间特征向量，并计算时间消耗，结果如图 10(b)所示；

3) 对生成的复数空间特征向量的相似性进行判定，并计算时间消耗，结果如图 10(c)所示。

从图 10(a)可以看出，对于一幅固定的几何形状，当取不同的GCT变换参数k值生成其对应的复数特征向量时，算法所消耗的时间与参数k是线性关系；从图 10(b)可以看出，固定GCT变换参数k为360，对于由不同的边界点数目所表示的几何形状，生成其对应的复数特征向量的时间消耗与几何图形边界点的数目也是线性关系。图 10(a)(b)的实验结果与对GCT变换的时间复杂度的分析结果是一致的。

图 10(c)的实验结果说明，度量两个复数特征向量相似性的时间消耗为一个常数。这是因为所生成的复数特征向量的维度为均为360，因此，度量任何两个复数特征向量相似性的时间消耗是相同的。同时注意到，度量两个复数特征向量相似性的时间消耗非常小，这也说明GCT变换在度量几何形状的相似性方面是高效的。

一个对几何形状有良好的表示性和区分性的表示方法和相似性度量方法，对产生了微小变化的几何图形形状，也能客观地反映出这种变化。例如，对图 11(a)(b)所示的两对几何形状，图 11(a)所示的两个几何形状的相似性要好于图 11(b)所示的两个几何形状。一个良好的几何形状表示方法及相似性度量方法需要准确地反映这一事实。

表 4是将GCT变换与直观的基于链码特征的方法^[10]、最新的多尺度不变量方法^[11]及经典的Shape Context方法^[12] 在几何形状的相似性定量度量上的比较实验结果。其中文献^[10]的方法返回值越大表示两个形状的相似性越好，文献^[11]及文献^[12]的方法返回值越小则表示两个形状的相似性越好。

从表 4可以看出，对于测试用的6组成对的几何形状，文献^[10]能正确判定序号为1和3中的成对几何形状的相似度关系，而对于序号为2、4、5、6的成对几何形状的相似度关系的判定与人类的视觉判定是不一致的。文献^[11]和文献^[12]的方法对相对复杂的形状，例如MPEG-7的数据集有较好的分类表现，但是，对于不具有复杂特征的几何图形，不能给出形状之间相似关系的正确度量结果：文献^[11]可以正确判定序号为1、2中的成对几何形状的相似度关系，而对于序号为3、4、5、6的成对几何形状的相似度关系的判定与人类的视觉判定是不一致的；文献^[12] 以正确判定序号为1、2中的成对几何形状的相似度关系，而对于序号为3、4、5、6的成对几何形状的相似度关系的判定与人类的视觉判定是不一致的。

观察表 4的最后一列，GCT变换可以判定表 4中的6对相似度不同的几何图形形状对，并给出与人类的视觉判定一致的相似性度量结果，不仅如此，GCT变换还正确给出了相似形状之间的角度旋转关系和尺度缩放关系。

本文提出了几何图形的GCT变换。通过GCT变换，将在实平面空间中难以量化的几何形状变换到复数空间并进行量化，进而将几何形状的相似性判定问题转化为复数空间特征向量的相似性判定问题。理论证明与实验验证，GCT变换是可行及高效的。

对本文的测试图形库，当GCT变换参数k取值大于等于360时，δ及η值将稳定为固定的值，并且，当相似性参数ψ小于等于0.05时，GCT变换判定为相似的几何图形与人类的视觉判断是一致的。在判定两个几何形状是相似的情况下，GCT变换还能计算出它们的角度旋转和尺度缩放。

利用GCT变换，可以解决一大类几何形状的相似性判定问题。使用GCT变换首先建立一组常见的几何形状的特征库，则可以对常见的几何形状进行判定和识别；在图像配准应用中，通过边界检测算法，如拉普拉斯算子、Sobel算子及Canny算子得到物体的外部边界，由于GCT算法可以判定相似图形的旋转角度和尺度缩放，因此GCT变换可应用于图像配准的相关应用中。这些也是本文后续的研究内容。