发布时间: 2018-08-16
摘要点击次数:
全文下载次数:
DOI: 10.11834/jig.180016
2018 | Volume 23 | Number 8

图像理解和计算机视觉

典型的基于区域的形状表示方法比较

吴绍根¹, 聂为清², 路利军³, 刘娅琴³

1. 广东轻工职业技术学院, 广州 510300;

2. 广州无线电集团, 广州 510656;

3. 南方医科大学生物医学工程学院, 广州 510515

收稿日期: 2018-01-08; 修回日期: 2018-03-08

基金项目: 国家自然科学基金项目（61628105）

第一作者简介: 吴绍根, 1968年生, 男, 副教授, 1993年于大连理工大学获计算机应用技术专业硕士学位, 主要研究方向为计算机视觉、模式识别和图像处理。E-mail:bill3000@126.com;
聂为清, 男, 博士, 主要研究方向为生物识别及应用。E-mail:wqnie0902@163.com;
路利军, 男, 副教授, 博士, 主要研究方向为图像重建。E-mail:lulijun@smu.edu.cn.

中图法分类号: TP391

文献标识码: A

文章编号: 1006-8961(2018)08-1242-12

摘要

目的形状的表示和匹配是计算机视觉和模式识别领域的重要问题。在基于区域的形状表示方法中出现了一批典型的方法，包括Hu不变矩方法（Hu不变矩）、角径向变换方法（ART方法）、通用傅里叶描述子方法（GFD方法）、拉东柱状图方法（HRT方法）和多尺度积分不变量方法（MSⅡ方法）等。由于这些方法出现的时间跨度长且在以往的对比研究中研究维度单一，因此需要对这些方法的综合性能做一个全面的比较分析和研究，为下一步的理论研究和实际应用提供方向和指导。方法采用3个基准形状库，包括简单几何图形形状库、MPEG-7形状库和汽车商标形状库，从3个维度，包括检索得分、检索稳定性和方法的计算复杂度，使用加权综合评估模型对典型的基于区域的形状表示方法进行比较分析，综合评估各种方法的综合性能指标。结果在综合性能上GFD方法具有最优的效果，其次是ART方法；由于HRT方法在匹配计算阶段具有较高的时间复杂度，在大规模形状库匹配的场景下性能会下降；Hu不变矩和MSⅡ方法的实验效果均不理想。通过比较研究还发现，将形状正交投影到正交基函数是提取形状视觉特征的有效方式。进一步猜想，将图像正交投影到正交基函数也是提取图像视觉特征的有效方式。因此，未来的研究中，寻找理想的正交基函数是提取形状乃至图像视觉特征的重要研究方向。结论在5种比较研究的方法中，GFD方法和ART方法在综合效果要好于HRT方法、Hu不变矩方法和MSⅡ方法，并且寻找理想的正交基函数是未来形状表示的重要研究方向。

关键词

计算机视觉; 模式识别; 形状投影; 形状描述符; 形状匹配

Comparative study of classic region-based shape descriptors

Wu Shaogen¹, Nie Weiqing², Lu Lijun³, Liu Yaqin³

1. Guangdong industry technical college, Guangzhou 510300, China;

2. Guangzhou Radio Group, Guangzhou 510656, China;

3. Southern Medical University, Guangzhou 510515, China

Supported by: National Natural Science Foundation of China(61628105)

Abstract

Objective Shape representation and shape matching are the basic tasks in computer vision and pattern recognition. Among all the region-based methods, several classic methods are already available, including Hu moment invariants (Hu method), angular radial transform (ART method), generic Fourier descriptor (GFD method), histogram of Radon transform (HRT method), and multi-scale integral invariant (MSⅡ method). Given the long time spans between all these proposed methods and the fact that only one factor (i.e., retrieval accuracy) is always compared in the past studies, we need a comprehensive comparative study of all these methods to help in application engineering and in future studies. Method To compare the different aspects of the five shape descriptors, we utilize three shape databases. The first shape database, which is a group of simple geometry and one that we modified, includes ten seed shapes. From each of these ten seed shapes, we construct three more shapes through non-rigid deformation, with increasing deformation from the first one to the third one, that is, 40 basic shapes constructed in total. Finally, for each of these 40 basic shapes, we obtain another three more similar shapes by random scale, random rotation, and random translation. Consequently, 160 shapes in the first shape database are constructed. In the retrieval test of the first database, we define a new rule of test scoring, which not only count the retrieval score but also considered the retrieval result order. Therefore, this new test score rule can inspect the intrinsic representation and retrieval ability of the shape descriptor. The second shape database we used in our comparative experiments is the MPEG-7, which consists of 70 different shape categories with each category consisting of 20 shapes of the same category modulo with various rigid and non-rigid deformations and is the standard shape database for shape descriptor and shape retrieval. The experiments are performed on 1400 shape images. Test score for MPEG-7 shape database is based on bullseye score, which counts the number of shapes in the same category (20 shapes in this case) within 40 best matching shapes. The third shape database we used in our experiments is the collection of vehicle trademark shapes. We collect 100 common vehicle flags, such as from Bents, BMW, and Toyota. For each of these 100 vehicle flag shapes, we construct three additional shapes by random scale, random rotation, and random translation and another three shapes using the random perspective parameters. Thus, we obtain a total of 700 vehicle flag shapes. The test score we used for this third database is also based on bullseye score, which counts the number of shapes in the same category (seven shapes in this case) within 14 best matching shapes. In all retrieval experiments for all the three shape databases, we not only compute the test scores but also the retrieval stability using the standard deviations of retrieval scores. We analyze and verified the computation complexity of the compared shape descriptors. After obtaining the test scores, retrieval stability, and computation complexity, a weighted formula, which considers all the three factors, is also defined to measure their comprehensive performances. Result In the retrieval experiments of the first simple geometry shape database, the HRT method achieves the best test score and lowest standard deviation, with the GFD method following, which indicates that HRT is not sensitive to noise in comparison with the other methods. In the retrieval experiments of the second shape database, ART and GFD methods obtain almost the same retrieval scores. In the retrieval experiments of the third shape database, GFD, ART, and HRT methods almost achieve the same retrieval score. In all of the retrieval experiments, the five compared methods are all invariant to scale, rotation, and translation, which are the fundamental requirements for a shape descriptor. We analyze and verify the computation complexity of the 5 methods and find that in the stage of feature creation, Hu method has the lowest computation complexity, and in the stage of feature matching, except for HRT method, all the other four methods have low matching computation complexity. The comprehensive performances of these five methods are measured by a weighted formula, and the GFD method has the best performance with ART as the next. HRT method can degrade with large number of shapes, because HRT method has higher complexity in matching phase than the other methods. The performances of Hu and MSⅡ methods are not satisfactory in all our experiments. The visual features of a shape can also be captured practically by the method of projecting shape onto a basis of orthogonal base functions. In this study, we suppose that the visual features of an image can also be captured practically by the same projection method. Conclusion Among all the evaluated region-based methods, GFD and ART methods have the best performance, and we suppose that they can be employed in engineering applications. Finding new basis of orthogonal base functions may be a fruitful research direction in shape visual feature extraction, as well as in image visual feature extraction, because projecting a shape onto the orthogonal base functions can capture its intrinsic vision features.

Key words

computer vision; pattern recognition; shape projection; shape descriptor; shape matching

0 引言

物体的形状是物体的重要特征。相比于物体的其他特征，如颜色、纹理、角点、关键点等，物体的形状承载更多的语义信息，因此，基于形状物体的识别广泛于字符识别、符号识别、商标识别和基于内容的图像检索应用中。由于物体形状的复杂性和应用的多样性，针对形状的分析，包括形状的表示和相似性判定仍是计算机视觉和模式识别领域的研究热点。

目前有多种形状表示及其相应的形状匹配方法。从总体上可将这些方法划分为两大类：基于形状边界轮廓的方法和基于形状区域的方法。基于形状边界轮廓的方法包括：形状上下文方法^[1-2]、链码方法^[3-4]、1维傅里叶方法^[5-6]、曲率尺度空间的方法^[7]和边界点空间距离关系方法^[8-11]等。基于区域的形状表示和匹配方法包括：区域矩方法^[12-17]、变换域方法^[18-25]、多尺度积分不变量方法^[26-27]等。Yang等人^[28]对这些方法做了综述。

在形状表示和匹配的两大类方法中，基于形状轮廓的方法需要首先获得形状的边界轮廓，然而对某些形状又难以获得形状的边界轮廓，因此，基于形状边界轮廓的表示方法在应用上受到一些限制。相比于基于形状边界轮廓的方法，基于形状区域的方法将整个形状的有效点用于形状表示，因此，基于区域的形状表示方法具有较好的适应性。

在基于区域的形状表示方法中，典型的表示方法包括：角径向变换方法^[19](ART)、不变矩方法^[12](Moment Invariants，简称矩不变量，或Hu不变矩)、通用傅里叶描述符方法^[18](GFD)、拉东变换直方图方法^[21](HRT)和多尺度积分不变量方法^[27](MSII)。其中，ART方法是MPEG-7^[29]推荐的基于区域的形状表示和匹配方法；Hu不变矩方法是著名且广泛使用的开源计算机视觉库OpenCV推荐的形状表示和匹配方法；傅里叶变换在图像处理中得到了广泛应用，同时，Zhang等人^[5]对GFD方法与MPEG-7推荐的基于形状边界轮廓的曲率尺度空间方法^[7]做了比较研究，发现GFD在MPEG-7的标准库上的检索效果要好于曲率尺度空间方法，并且，相比于Zernike方法^[16]，GFD方法在检索效果上也好于Zernike方法^[18]；拉东变换在图像表示和重建上具备完备的理论体系，基于拉东变换的形状表示方法是近年来的一个研究热点^[21-25]，本文选取基础的HRT方法作为这类方法的代表；MSII方法^[27]则是近期提出的较具有影响的基于区域的形状表示方法。

本文使用3个基准形状库，并从3个维度对这5种方法进行比较研究，发现GFD方法具有较好的综合性能，其次是ART方法。进一步分析还发现，通过将形状正交投影到一组正交基函数来提取形状视觉特征是提取形状特征的有效方式，说明正交投影在形状视觉特征提取乃至图像视觉特征提取上具有优于其他方式的独特优势。

1 典型的基于区域的形状表示方法

1.1 ART方法

ART方法是基于矩的形状表示方法，也是MPEG-7推荐的基于形状区域的表示方法。

对2D平面的任意形状，ART方法在极坐标下通过定义在单位圆上的一组正交基函数对形状做正交投影，并将得到的复数系数强度归一化后作为形状的特征。ART阶为$n$、$m$的系数${F_{nm}}$定义为

$ {F_{nm}} = \int_0^{2{\rm{ \mathsf{ π} }}} {\int_1^1 {{V_{nm}}\left( {\rho ,\theta } \right)f\left( {\rho ,\theta } \right)\rho {\rm{d}}\rho {\rm{d}}\theta } } $

式中，$f\left( {\rho , \theta } \right)$是形状在极坐标下的表示，${V_{nm}}\left( {\rho , \theta } \right)$是ART正交基函数。

由于${V_{nm}}\left( {\rho , \theta } \right)$函数在径向方向和角度方向是可分的，因此，${V_{nm}}\left( {\rho , \theta } \right)$可进一步表示为

$ {V_m}\left( {\rho ,\theta } \right) = {A_m}\left( \theta \right){R_n}\left( \rho \right) $

$ {A_m}\left( \theta \right) = \frac{1}{{2{\rm{ \mathsf{ π} }}}}{{\rm{e}}^{{\rm{j}}m\theta }} $

$ {R_n}\left( \rho \right) = \left\{ \begin{array}{l} 1\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;n = 0\\ 2\cos \left( {{\rm{ \mathsf{ π} }}n\rho } \right)\;\;\;\;\;n \ne 0 \end{array} \right. $

j是虚数单位。

MPEG-7建议取$n$从0到2、$m$从0到11的共36个系数，并以${F_{00}}$的强度作为归一化因子对其余系数的强度做归一化处理后的有序序列作为形状的特征向量，然后使用向量差的L₁范数作为两个形状的相似性误差值。

1.2 Hu不变矩方法

Hu不变矩是归一化的一组几何中心矩，共包括7个量。Hu不变矩具有位移、缩放和旋转无关性。这7个Hu不变矩是

$ {h_1} = {v_{20}} + {v_{02}} $

$ {h_2} = {\left( {{v_{20}} + {v_{02}}} \right)^2} + 4v_{11}^2 $

$ {h_3} = {\left( {{v_{30}} - 3{v_{12}}} \right)^2} + {\left( {3{v_{21}} - {v_{03}}} \right)^2} $

$ {h_4} = {\left( {{v_{30}} + {v_{12}}} \right)^2} + {\left( {{v_{21}} + {v_{03}}} \right)^2} $

$ \begin{array}{l} {h_5} = \left( {{v_{30}} - 3{v_{12}}} \right)\left( {{v_{30}} + {v_{12}}} \right) \times \\ \left[ {{{\left( {{v_{30}} + {v_{12}}} \right)}^2} - 3{{\left( {{v_{21}} + {v_{03}}} \right)}^2}} \right] + \\ \left( {3{v_{21}} - {v_{03}}} \right)\left( {{v_{21}} + {v_{03}}} \right) \times \\ \left[ {3\left( {{v_{30}} - {v_{12}}} \right) - \left( {{v_{21}} + {v_{03}}} \right)} \right] \end{array} $

$ \begin{array}{l} {h_6} = \left( {{v_{20}} - {v_{02}}} \right)\left[ {{{\left( {{v_{30}} + {v_{12}}} \right)}^2} - {{\left( {{v_{21}} + {v_{03}}} \right)}^2}} \right] + \\ 4{v_{11}}\left( {{v_{30}} + {v_{12}}} \right)\left( {{v_{21}} + {v_{03}}} \right) \end{array} $

$ \begin{array}{l} {h_7} = \left( {3{v_{21}} - {v_{03}}} \right)\left( {{v_{30}} + {v_{12}}} \right)\\ \left[ {{{\left( {{v_{30}} + {v_{12}}} \right)}^2} - 3{{\left( {{v_{21}} + {v_{03}}} \right)}^2}} \right] - \\ \left( {{v_{30}} - 3{v_{12}}} \right)\left( {{v_{21}} + {v_{03}}} \right) \times \\ \left[ {3{{\left( {{v_{30}} + {v_{12}}} \right)}^2} - {{\left( {{v_{21}} + {v_{03}}} \right)}^2}} \right] \end{array} $

式中，${v_{pq}} = {\mu _{pq}}/{m_{00}}^{\left( {\frac{{p + q}}{2} + 1} \right)}$，${\mu _{pq}} = \sum\limits_{x, y} {\left( {f\left( {x, y} \right){{\left( {x - \bar x} \right)}^p} \times {{\left( {y - \bar y} \right)}^q}} \right)} $。${f\left( {x, y} \right)}$是形状的图像函数，$\left( {\bar x、\bar y} \right)$是形状的几何重心，${m_{00}}{\rm{ = }}\sum\limits_{x, y} {f\left( {x, y} \right)} $。

获得形状的Hu不变矩后，由这7个矩为元素组成形状的特征向量。然后计算两个向量之间的距离，即

$ \Delta = \sum\limits_{i = 1}^7 {\left| {\frac{{\rho _i^A - \rho _i^B}}{{\rho _i^A}}} \right|} $

式中，$\rho _i^A = {\mathop{\rm sgn}} \left( {h_i^A} \right)\log \left( {h_i^A} \right)$，$\rho _i^B = {\mathop{\rm sgn}} \left( {h_i^B} \right)\log \left( {h_i^B} \right)$。${h_i^A}$、${h_i^B}$分别是两个形状的Hu不变矩，i=1，…，7。

1.3 GFD方法

GFD方法首先将形状变换到极坐标下，然后对在极坐标下表示的形状在2D的笛卡儿坐标下做傅里叶变换，这个过程称为MPFT (modified polar fourier transform)。对任意给定的形状图像函数${f\left( {x, y} \right)}$，MPFT定义为

$ PF\left( {\rho ,\phi } \right) = \sum\limits_r {\sum\limits_i {f\left( {r,{\theta _i}} \right)\exp \left[ {{\rm{j}}2{\rm{ \mathsf{ π} }}\left( {\frac{r}{R}\rho + \frac{{2{\rm{ \mathsf{ π} }}i}}{T}\phi } \right)} \right]} } $

式中，0≤$r$=$\sqrt {{{\left( {x - {x_c}} \right)}^2} + {{\left( {y - {y_c}} \right)}^2}} $＜$R$，${\theta _i} = i\left( {2{\rm{ \mathsf{ π} /}}T} \right)$，0≤$i$＜$T$，(${x_{c}}$, ${y_{c}}$)是形状的重心，0≤$\rho $＜$R$，$0 \le \phi < T$，j是虚数单位，$R$和$T$分别是径向和角度解析度。GFD方法的本质是将形状在正交的正弦基函数上做正交投影。

类似于笛卡儿坐标系下的图像傅里叶变换，MPFT可以在较少的一组低频系数下捕获原形状的信息。文献[18]对$\rho $和$\phi $的取值做了比较分析，建议使用$\rho $=0，…，4和$\phi $=0，…，11的共60个系数即可较紧凑的表示原形状的信息。基于获得的MPFT系数，使用如下的向量表示原形状的特征，即

$ \mathit{\boldsymbol{G}} = \left( \begin{array}{l} \frac{{PF\left( {0,0} \right)}}{{area}},\frac{{\left| {PF\left( {0,1} \right)} \right|}}{{\left| {PF\left( {0,0} \right)} \right|}}, \cdots ,\\ \frac{{\left| {PF\left( {0,n} \right)} \right|}}{{\left| {PF\left( {0,0} \right)} \right|}}, \cdots ,\frac{{\left| {PF\left( {m,n} \right)} \right|}}{{\left| {PF\left( {0,0} \right)} \right|}} \end{array} \right) $

式中，“|·|”表示求复数的强度，$area$表示形状的面积，$m$为$\rho $的最大取值，$n$为$\phi $的最大取值。

对两个形状的GFD特征向量，文献[18]建议使用向量差的L₁范数作为两个形状的相似性误差值。

1.4 HRT方法

radon变换在图像表示和重建上具备完备的理论体系，基于radon变换的形状表示是近年来的研究热点，并出现了一系列的形状表示方法^[21-25]。

对于任意的图像${f\left( {x, y} \right)}$，其radon变换定义为

$ Rf\left( {t,\theta } \right) = \int {f\left( {x,y} \right){\delta _{\left\{ {x\cos \theta + y\sin \theta = t} \right\}}}\left( {x,y} \right){\rm{d}}x{\rm{d}}y} $

式中，$\delta $(.)是狄拉克函数。radon变换是沿指定的直线对图像做线积分。

柱状图以统计的形式反映数据的分布情况。对于定义域为$\mathit{\boldsymbol{X}}$的任意函数$\mathit{f}\left( x \right)$，其柱状图定义为

$ H\left( f \right)\left( y \right) = \frac{{\# \left\{ {x \in \mathit{\boldsymbol{X}}\left| {y = f\left( x \right)} \right.} \right\}}}{{\left| \mathit{\boldsymbol{X}} \right|}} $

式中，#表示集合中元素的个数，|.|表示定义域的大小或元素个数。

HRT方法通过统计图像函数${f\left( {x, y} \right)}$的拉东变换在每个角度(也就是直线斜率)的直线上的线积分的大小来描述形状的特征。精确地，对任意的图像函数${f\left( {x, y} \right)}$和radon变换的每一个角度，HRT定义为

$ HR{T_f}\left( {y,\theta } \right) = H\left( {Rf\left( { \cdot ,\theta } \right)} \right)\left( y \right)\;\;\;\;\;\theta \in \left[ {0,{\rm{ \mathsf{ π} }}} \right) $

为了降低直方图的数据维度，在统计函数的直方图时，将函数的值域均匀地划分为等间距的$N$个区间。在HRT方法中，文献[24]建议将radon变换直方图的区间个数$N$取为16。在获得了两个形状的HRT特征后，计算两个形状的相似性误差为

$ \begin{array}{*{20}{c}} {Sim\left( {HR{T_A},HR{T_B}} \right) = }\\ {\mathop {\arg \min }\limits_{\alpha \in \left[ {0,\pi } \right)} {{\left\| {HR{T_A}\left( {y,\theta } \right) - HR{T_B}\left( {y,\theta } \right)} \right\|}_2}} \end{array} $

式中，$HR{T_A}$、$HR{T_B}$分别是两个形状的HRT特征。

1.5 MSII方法

MSII方法将形状定义为指定定义域$\mathit{\Omega }$上的一个区域$D$，并使用特征函数来描述形状，即

$ {\chi _D}\left( x \right) = \left\{ \begin{array}{l} 1\;\;\;\;x \in D\\ 0\;\;\;x \in \mathit{\Omega }\backslash D \end{array} \right. $

首先将形状${\chi _D}\left( x \right)$与高斯核做卷积，得到形状在指定尺度$\sigma $下的局部特征

$ {\cal F}_D^\sigma = {\chi _D}\left( x \right) \cdot \left( {1 - {G_\sigma } * {\chi _D}\left( x \right)} \right) $

式中，“*”是卷积运算，“·”是算术乘积运算，${G_\sigma }$是2维平面上标准差为$\sigma $的高斯核函数。精确地，${G_\sigma }$定义为

$ {G_\sigma }\left( x \right) = \frac{1}{{2{\rm{ \mathsf{ π} }}{\sigma ^2}}}{{\rm{e}}^{ - \frac{{{{\left\| x \right\|}^2}}}{{2{\sigma ^2}}}}} $

获得了形状在尺度$\sigma $下的特征$\mathcal{F}_{D}^{\sigma }$之后，计算形状在指定尺度$\sigma $下的特征签名

$ \begin{array}{*{20}{c}} {{S_D}\left( \sigma \right) = \frac{{\int_\Omega {{\cal F}_D^\rho \left( x \right){\rm{d}}x} }}{{\int_D {{\rm{d}}x} }} = }\\ {\frac{{\int_\Omega {{\chi _D}\left( x \right) \cdot \left( {1 - {G_\sigma } * {\chi _D}\left( x \right)} \right){\rm{d}}x} }}{{\int_\Omega {{\chi _D}\left( x \right){\rm{d}}x} }}} \end{array} $

式中，$\rho $定义为

$ \rho = \sigma \sqrt {\int_\Omega {{\chi _D}\left( x \right){\rm{d}}x} } $

取$\sigma $为一系列不同值，得到形状在不同尺度下的特征签名，将所有签名作为元素来构建形状的特征向量，然后使用Wasserstein距离作为两个形状的相似性误差值。两个向量的Wasserstein距离定义为

$ d\left( {{D_1},{D_2}} \right) = \int\limits_0^\infty {\left| {{S_{{D_1}}}\left( \sigma \right) - {S_{{D_2}}}\left( \sigma \right)} \right|{\rm{d}}\sigma } $

式中，${D_1}$、${D_2}$表示两个形状，${S_{{D_1}}}\left( \sigma \right)$、${S_{{D_2}}}\left( \sigma \right)$表示两个形状的MSII特征向量。

2 检索实验及结果分析

使用3个基准形状数据库对五种表示方法进行比较：1)通过对一组发生仿射变换和少许非刚性形变的简单形状库的检索来比较各种方法对形状的检索能力；2)对MPEG-7基准形状库，使用Bullseye Score来比较各种方法对形状的检索能力；3)通过一组相对复杂的汽车商标图标，并对商标图标进行仿射变换和少许透视变换来比较各种方法在复杂场景下对形状的表示和区分能力。

2.1 对简单图形形状的检索

对形状的平移、缩放和旋转不变性是对任何形状表示方法的最基本要求。除此之外，对于发生少些非刚性形变的形状，表示方法所生成的特征向量也要能进行区分，并在相似性度量上给出视觉上合理的结果。为此，制作了如图 1所示的40个简单的形状。

图 1 简单的区域形状

Fig. 1 Sample of simple geometry shapes

图 1所示的40个形状由10个类组成，每类4个形状，每类形状的第1个形状为初始基本形状，其他3个形状通过对第1个形状做少许非刚性形变形成的。同时，为了检测5种形状表示方法对平移、缩放和旋转是否具有无关性，对这40个形状的每个形状，通过随机的位移、缩放和旋转参数对每个形状做仿射变换形成3个相似的形状，进而共形成120个形状，如图 2所示。

图 2 对图 1的形状做仿射变换形成的形状

Fig. 2 Affine transformed shapes of simple geometry shapes in Fig. 1

在检索实验中，以图 1中每类形状的第1个也就是初始形状为检索模板，从图 2的120个形状中检索出12个最为相似的形状，并根据检索得到的正确形状个数和形状出现的位置进行计分。由于目前没有通用的类似本文所述的对检索结果的精细评判方法，本文规定了如下的统计计分规则：如果该类形状出现在检索结果中，并且与本应该出现的分组位置相差$n$，$n$=0、1、2、3，则计10-2$n$分。例如，以图 1的第1个形状为检索模板，某个方法得到的检索结果如图 3所示。

图 3 某个方法的检索结果

Fig. 3 A sample retrieval result

图 3中，第1、2、3个形状是与检索模板最为相似的形状，并且出现在检索结果的第1组中，所以每个结果形状计10-2×0=10分，共30分；图 3中的第4、5个形状不是与检索模板相似的形状，不计分；图 3中的第6个形状，是与检索模板相似的形状，并且出现在了第2组正确的组内，计10-2×0=10分；图 3中的第7个形状本该出现在第2组，然而却出现在第3组，组间相差1，所以计10-2×1=8分；图 3中的第8个形状与本该出现的组相差1，因此计10-2×1=8分；图 3中的第10个形状出现在本应该出现的组内，计10分。将以上所有得分相加，得到本次检索的得分总分为66分。

采用本文所述计分方法，对ART方法、Hu不变矩方法、GFD方法、HRT方法和MSII方法进行检索结果评分，针对每类形状，各方法的检索得分如图 4(a)所示。

图 4 5种方法对图 3形状的检索结果

Fig. 4 The retrieval result for shapes in Fig. 3

为了便于显示各个方法的检索得分，图 4(a)对每个方法针对每个形状的检索得分从小到大做了排序。从图 4(a)可以看出，HRT方法要优于其他方法，其次是GFD方法，再其次是ART方法，再其次是MSII方法，最后是Hu不变矩方法，这种分析结果从图 4(b)显示的对每个方法的检索得分求平均值的结果是一致的。同时，为了度量各个方法检索得分的稳定性，图 4(c)给出了各个方法检索得分的标准差。针对图 2的简单形状，从标准差的结果来看，HRT方法的稳定性要好于其他4个方法，其次是ART方法，再其次是GFD方法。

从5种方法对图 2、图 3所示的简单形状的表示和检索结果的实验可以得出，HRT方法在综合效果上要好于其他4个方法，GFD方法和ART方法在效果上基本相当，在效果上稍稍弱于HRT方法。

2.2 对MPEG-7标准形状库的检索

为了度量形状表示和匹配方法的性能，MPEG-7制作了标准的形状库，该形状库由70个类，每类20个形状，共1 400个形状组成。这个库是事实上的用于度量形状表示方法效果的基准库。图 5显示了70类形状的第一个形状。

图 5 MPEG-7形状库的部分形状

Fig. 5 Sample shapes of MPEG-7 shape base

在度量方法上采用采用MPEG-7建议的Bullseye Score方法。具体是：以形状库中每类形状的每个形状为检索目标对形状库进行检索，从形状库中检索出2倍于该类形状个数的最优匹配形状，并从中统计正确的形状个数。5种方法的得分情况如图 6(a)所示。

图 6 五种方法对MPEG-7形状库的检索结果

Fig. 6 The retrieval result for shapes of MPEG-7 shape base

从图 6(a)可以看出，对MPEG-7形状库，GFD方法和ART方法的检索效果明显好于其他检索方法，并且，GFD方法和ART方法几乎表现出同等的效果。这种结果从图 6(b)的检索平均分中也可以清晰的看到。同时，从图 6(c)的标准差中可以看到，针对MPEG-7形状库，出现一个较为奇特的现象：相比于得分较高的ART方法、GFD方法和HRT方法，检索得分不高的Hu不变矩方法和MSII方法表现地较为稳定，而得分较高的其他3个方法却没有这两个方法稳定。分析这个原因，由于Hu不变矩方法和MSII方法对MPEG-7的多类形状的检索得分均比较低，只有对较少数的形状得分较高；而其他3个方法得分的分布较为均匀，导致得分的标准差偏高。

综合来看，从5种方法对MPEG-7的形状表示和检索结果的实验可以得出，GFD方法和ART方法在效果上比较突出。

2.3 对相对复杂的汽车商标图标的检索

为了度量这5种方法对形状的综合检索效果和在实际应用中的检索效果，收集了100种常见汽车的商标图标，如图 7所示。同时，为了度量方法针对复杂图标的检索效果，对这100种汽车商标的每一种图标做随机的位移、旋转和缩放变换生成3个相似但是发生了位移、旋转和缩放的图标，共300个，图 8所示的是部分仿射变换后的图标。再者，为了验证5种方法对透视变换形状的检索能力，对这100种汽车图标的每一种图标做随机参数透视变换生成3个透视变换的图标，共300个，图 9是部分透视变换后的图标。原汽车形状加上仿射变换和透视变换形成，共有700个汽车形状。

图 7 100种汽车商标图标

Fig. 7 100 vehicle trademarks shapes

图 8 对图 7的商标形状做仿射变换后的部分形状

Fig. 8 Affine transformed vehicle shapes in Fig. 7

图 9 对图 7的商标形状做透视变换的部分形状

Fig. 9 Perspective transformed vehicle shapes in Fig. 7

将这700个汽车形状作为数据集，并使用MPEG-7的Bullseye Score对检索结果进行统计。实验结果如图 10(a)所示。

图 10 5种方法对汽车商标形状的检索结果

Fig. 10 The retrieval result for shapes of vehicle shape base

从图 10(a)可以看出，对汽车商标形状库，ART方法、GFD方法和HRT方法的检索效果要好于其他两个检索方法，并且具有几乎相同的检索平均得分，这种结果从图 10(b)的检索平均分中也可以清晰的看到。同时，从检索结果的稳定性来看，HRT方法在稳定性上要好于ART方法和GFD方法。

综合分析5种方法对简单几何形状的检索、MPEG-7形状的检索和汽车图标形状的检索结果可以看出，相比于其他两个方法，ART方法、GFD方法和HRT方法在能够得到较好的检索结果。

3 时间复杂度及实验结果分析

设形状图像的尺寸为$M \times N$像素。首先从理论上对5种方法生成形状特征的时间复杂度进行分析。在ART方法中，需要对每个角度和径向参数做积分运算，因此，ART方法在生成形状特征时的时间复杂度为${\rm{O}}\left( {M \times N \times n \times m} \right)$，其中$n$、$m$分别为角分辨率和径向分辨率；在Hu不变矩方法中，只需要计算7个Hu不变矩，因此，Hu不变矩的计算复杂度为O($M$×$N$)；GFD方法的计算复杂度与ART方法类似，需要为每个角度和径向计算MPFT的系数，因此，GFD方法的时间复杂度为O($M$×$N$×$\rho $×$\phi $)，其中$\rho $、$\phi $分别为径向分辨率和角度分辨率；在HRT方法中，针对每一个$t$和$\theta $，需要计算形状的线积分，因此，HRT方法的时间复杂度为O($M$×$N$×$t$×$\theta $)，其中，$t$是距离分辨率，$\theta $是角度分辨率。由于在拉东变换中，$t$和$\theta $的选取影响变换的效果，一般$\theta $取180°；在MSII方法中，需要在每一个尺度下做图像与高斯核的卷积运算，并且尺度的选取以形状面积的平方根为基本尺度，因此，MSII方法的时间复杂度为${\rm{O}}\left( {M \times N \times \sqrt {M \times N} } \right)$。从理论分析可以看出，5种方法在生成形状特征中，HRT方法和MSII方法都有较高的时间复杂度。

再对5种方法在特征匹配阶段的时间复杂度进行分析。除HRT方法之外，其他4种方法均采用特征向量之间的距离来度量形状之间的误差，因此，它们的时间复杂度为O(1)。而在HRT方法中，由于需要使用argmin函数求取两个特征向量的最小距离，因此，HRT方法在特征匹配时的时间复杂度为O($\theta $)，这显然是5种方法中最大的。

采用实验方式对理论分析的进行验证。在对5种方法实现中，均直接采用方法所使用的数学模型对算法进行实现，在实现上不对算法做技术优化。实验以第2节中的700个汽车商标形状为测试库，取700形状的平均时间为每个方法的计算时间。5种方法在生成形状特征的时间复杂度和在特征匹配时的时间复杂度如图 11所示。

图 11 5种方法的时间复杂度

Fig. 11 Computation complexity of five methods

从图 11可以看出，对5种方法的时间复杂度的理论分析结果与实验结果是一致的。具体的，在形状的特征生成阶段，如图 11(a)所示，ART方法、Hu不变矩方法和GFD方法的计算时间均小于100 ms；在特征匹配阶段，如图 11(b)所示，除HRT方法外，其他四个方法的计算时间均小于0.007 ms，这是非常重要的，因为这个时间将直接决定对大规模形状库检索时的总检索时间。

4 研究结论

从5种方法对3种类型形状库的检索结果可以看出，ART方法、GFD方法和HRT方法在检索效果上明显优于Hu不变矩方法和MSII方法；但从时间复杂度上看，HRT方法在生成特征时的计算复杂度和匹配特征时的计算复杂度又要明显复杂于其他4个方法。为了综合度量这5种方法的性能，需要同时将检索效果、检索稳定性和时间复杂度纳入考虑范畴。由于目前对形状表示和匹配方法的度量上，都没有将时间复杂度和检索稳定性纳入其中，这在一定程度上会导致应用中对方法选取的误区，因此，需要一个将检索效果、检索稳定性和时间复杂度均纳入其中的数学模型来综合度量方法的性能。

在影响方法综合度量结果的3个因素中，检索得分无疑是最为重要的，其次是方法的时间复杂度，再其次是方法的检索稳定性。通过分配不同的权重来体现指标的重要性。为此，设计了如下数学模型来度量5种方法的综合性能：

$ \begin{array}{*{20}{c}} {\rho = 0.7 \times \sum\limits_{i = 1}^3 {\frac{{{Q_i}}}{3}} + }\\ {0.1 \times \left( {100 - \sum\limits_{i = 1}^3 {\frac{{{S_i}}}{3}} } \right) + }\\ {0.2 \times \left( {100 - 100 \times M} \right)} \end{array} $

式中，$\rho $是方法的综合性能，系数0.7、0.1和0.2为检索得分、检索稳定性和计算复杂度的权重，${Q_i}$是方法对简单形状、MPEG-7形状和汽车商标形状的检索得分，${S_i}$是方法对简单形状、MPEG-7形状和汽车商标形状检索得分的标准差，$M$是方法在计算形状匹配时的计算时间，$i$=1, 2, 3。根据综合性能计算公式，5种方法的综合性能如图 12所示。

图 12 5种方法的综合性能

Fig. 12 The final comprehensive performance

从图 12可以看出，在综合性能上，GFD方法要好于其他方法，其次是ART方法。这种分析结果与第2节和第3节的实验结果从直觉上的判断是一致的。由于HRT方法在特征匹配时的较高时间复杂度，建议不用于大规模形状检索应用中。

基于以上实验及结果分析，在实际工程应用中，相比于本文比较的其他方法，GFD方法和ART方法会有较好的适应性和较好的表现。Hu不变矩方法虽然对噪音极为敏感，但是在特征生成阶段和特征匹配阶段均比较高效，因此，在无噪音并且形状只存在缩放、旋转和平移这些变换时，Hu不变矩方法会有较好的表现。在工程应用中本文不建议使用HRT方法和MSII方法。

分析以上检索实验和计算复杂度实验还可以看出，对形状在正交基函数上做正交投影，相比于其他的方法，能更好地提取形状的特征。类似傅里叶变换中将图像正交投影到正弦基函数可以完美提取图像的频域特征，进一步泛化这种思想：可否从数学空间上寻找到一组正交基函数，通过这组正交基函数可以完美地提取形状的视觉特征？ART方法、GFD方法从一定程度例证了这种可能性。

5 结论

形状的描述和匹配是模式匹配和计算机视觉重要和活跃的研究领域。在众多的基于区域的形状描述方法中，精选GFD方法、ART方法、HRT方法、MSII方法和Hu不变矩方法进行比较研究，不仅可以为应用提供向导，也可以为研究提供路径。通过比较研究还发现，ART方法和GFD方法都是基于函数正交投影来提取形状特征的，可以猜想，在形状乃至图像的视觉特征提取中，基于基函数的正交投影方法能够更为精准地反映形状或图像的本质。本文下一步将寻找新的可用于区域形状表示的正交基函数，并对这一猜想进行证实或证伪。

参考文献

[1] Belongie S, Malik J, Puzicha J. Shape matching and object recognition using shape contexts[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(4): 509–522. [DOI:10.1109/34.993558]

[2] Ling H B, Jacobs D W. Shape classification using the inner-distance[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(2): 286–299. [DOI:10.1109/TPAMI.2007.41]

[3] Livarinen J, Visa A J E. Shape recognition of irregular objects[C]//Proceedings of Volume 2904, Intelligent Robots and Computer Vision XV. Boston, MA: SPIE, 1996: 25-32. [DOI: 10.1117/12.256280]

[4] Liu Y K, Wei W, Wang P J, et al. Compressed vertex chain codes[J]. Pattern Recognition, 2007, 40(11): 2908–2913. [DOI:10.1016/j.patcog.2007.03.001]

[5] Zhang D S, Lu G J. A comparative study of curvature scale space and Fourier descriptors for shape-based image retrieval[J]. Journal of Visual Communication and Image Representation, 2003, 14(1): 39–57. [DOI:10.1016/S1047-3203(03)00003-8]

[6] Zhang D S, Lu G J. A comparative study of Fourier descriptors for shape representation and retrieval[C]//Proceedings of the 5th Asian Conference on Computer Vision. Melbourne, Australia: ACCV, 2002: 646-651.

[7] Mokhtarian F, Mackworth A K. A theory of multiscale, curvature-based shape representation for planar curves[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(8): 789–805. [DOI:10.1109/34.149591]

[8] Wu S G, Wang K, Lu L J, et al. GCT transform and similarity determination of geometry shapes[J]. Journal of Image and Graphics, 2016, 21(12): 1671–1684. [吴绍根, 王康, 路利军, 等. GCT变换及几何图形形状相似性判定[J]. 中国图象图形学报, 2016, 21(12): 1671–1684. ] [DOI:10.11834/jig.20161212]

[9] Yang J Y, Wang H X, Yuan J S, et al. Invariant multi-scale descriptor for shape representation, matching and retrieval[J]. Computer Vision and Image Understanding, 2016, 145: 43–58. [DOI:10.1016/j.cviu.2016.01.005]

[10] Presles B, Debayle J. A distance-based shape descriptor invariant to similitude and its application to shape classification[C]//Proceedings of the 23rd International Conference on Pattern Recognition. Cancun, Mexico: IEEE, 2017: 2598-2603. [DOI: 10.1109/icpr.2016.7900027]

[11] Wu S G, Nie W Q, Lu L J, et al. Inside-circle distance transform for shapes[J]. Journal of Image and Graphics, 2018, 23(1): 39–51. [吴绍根, 聂为清, 路利军, 等. 形状的圆内距离变换[J]. 中国图象图形学报, 2018, 23(1): 39–51. ] [DOI:10.11834/jig.170362]

[12] Hu M K. Visual pattern recognition by moment invariants[J]. IRE Transactions on Information Theory, 1962, 8(2): 179–187. [DOI:10.1109/TIT.1962.1057692]

[13] Taubin G, Cooper D B. Recognition and positioning of rigid objects using algebraic moment invariants[C]//Proceedings Volume 1570, Geometric Methods in Computer Vision. San Diego, CA: SPIE, 1991: 175-186. [DOI: 10.1117/12.48423]

[14] Mukundan R, Ong S H, Lee P A. Image analysis by Tchebichef moments[J]. IEEE Transactions on Image Processing, 2001, 10(9): 1357–1364. [DOI:10.1109/83.941859]

[15] Hmimid A, Sayyouri M, Qjidaa H. Image classification using a new set of separable two-dimensional discrete orthogonal invariant moments[J]. Journal of Electronic Imaging, 2014, 23(1): 013026. [DOI:10.1117/1.jei.23.1.013026]

[16] Khotanzad A, Hong Y H. Invariant image recognition by Zernike moments[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990, 12(5): 489–497. [DOI:10.1109/34.55109]

[17] Zhu H Q. Image analysis using separable two-dimensional discrete orthogonal moments[C]//Proceedings of the 18th IEEE International Conference on Image Processing. Brussels, Belgium: IEEE, 2011: 817-820. [DOI: 10.1109/icip.2011.6116681]

[18] Zhang D S, Lu G J. Shape-based image retrieval using generic Fourier descriptor[J]. Signal Processing:Image Communication, 2002, 17(10): 825–848. [DOI:10.1016/S0923-5965(02)00084-X]

[19] Ricard J, Coeurjolly D, Baskurt A. Generalization of angular radial transform[C]//Proceedings of 2004 International Conference on Image Processing. Singapore: IEEE, 2004: 2211-2214. [DOI: 10.1109/icip.2004.1421536]

[20] Khalil M I, Bayoumi M M. A dyadic wavelet affine invariant function for 2d shape recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(10): 1152–1164. [DOI:10.1109/34.954605]

[21] Tabbone S, Terrades O R, Barrat S. Histogram of radon transform. A useful descriptor for shape retrieval[C]//Proceedings of the 19th International Conference on Pattern Recognition. Tampa, FL, USA: IEEE, 2008: 1-4. [DOI: 10.1109/ICPR.2008.4761555]

[22] Santosh K C, Lamiroy B, Wendling L. DTW-radon-based shape descriptor for pattern recognition[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2013, 27(3): 1350008. [DOI:10.1142/s0218001413500080]

[23] Hasegawa M, Tabbone S. Amplitude-only log radon transform for geometric invariant shape descriptor[J]. Pattern Recognition, 2014, 47(2): 643–658. [DOI:10.1016/j.patcog.2013.07.024]

[24] Hasegawa M, Tabbone S. Histogram of radon transform with angle correlation matrix for distortion invariant shape descriptor[J]. Neurocomputing, 2016, 173: 24–35. [DOI:10.1016/j.neucom.2015.04.100]

[25] Wang B, Gao Y S. Structure integral transform versus radon transform:a 2D mathematical tool for invariant shape recognition[J]. IEEE Transactions on Image Processing, 2016, 25(12): 5635–5648. [DOI:10.1109/TIP.2016.2609816]

[26] Manay S, Cremers D, Hong B W, et al. Integral invariants for shape matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(10): 1602–1618. [DOI:10.1109/TPAMI.2006.208]

[27] Hong B W, Soatto S. Shape matching using multiscale integral invariants[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37(1): 151–160. [DOI:10.1109/TPAMI.2014.2342215]

[28] Yang M Q, Kidiyo K, Joseph R. A survey of shape feature extraction techniques[J]. Pattern Recognition, 2008: 43–90. [DOI:10.5772/6237]

[29] Latecki L J, Lakamper R, Eckhardt T. Shape descriptors for non-rigid shapes with a single closed contour[C]//Proceedings of 2000 IEEE Conference on Computer Vision and Pattern Recognition. Hilton Head Island, SC, USA: IEEE, 2000: 424-429. [DOI: 10.1109/cvpr.2000.855850]