Page 348 - 《软件学报》2021年第5期
P. 348
1572 Journal of Software 软件学报 Vol.32, No.5, May 2021
m=1,2,…,T}和Ψ B ={ω B (t n ),n=1,2,…,T}.这里,我们采用文献[26]提出的增强型 Hausdorff 距离来度量集合Ψ A 和
Ψ B 的距离.
首先,我们定义两个集合的任意两个元素ω A (t m )和ω B (t n )的距离为
d(ω A (t m ),ω B (t n ))=||ω A (t m )−ω B (t n )|| 1 (22)
这里,||⋅|| 1 是 L1 范数.然后,我们定义集合Ψ A 到集合Ψ B 的距离为
1 T
t
t
,
D ( ΨΨ B ) = ∑ min d (ω A ( ),ω B ( )) (23)
m
n
A
T η− A m= 1 n= 1,...,T
其中,η A 的计算步骤如下.
(1) 定义一个数组ζ(1:T),并设置每个元素为−1;
(2) 对于集合Ψ A 中的每个元素ω A (t m ),在集合Ψ B 中找到其最佳匹配,即与其距离最小的元素ω B (t n ),作累加
操作:ζ(n)←ζ(n)+1;
(3) 将数组ζ中所有的值大于 0 的元素相加赋值给η A .
容易看出,变量η A 的值范围为 0 到 T−1 的整数.当η A =0 时,集合Ψ A 中的所有元素匹配到了集合Ψ B 中的不同
元素,即产生的是一对一映射,这是理想的匹配情况;而η A =T−1 表示集合Ψ A 中的所有元素都匹配到了集合Ψ B 中
的同一个元素;而 0<η A <T−1,则表示存在集合Ψ A 中的不同元素匹配到了集合Ψ B 中的同一元素的情况.
以相同的方式计算从集合Ψ B 到集合Ψ A 的距离 D(Ψ B ,Ψ A ),则叶片形状 A 和形状 B 之间的差异度量定义为
Diff(A,B)=max(D(Ψ A ,Ψ B ),D(Ψ B ,Ψ A )) (24)
若 Diff(A,B)的值越大,则表示形状 A 和形状 B 差异越大;反之,则越小.
3 算法时间复杂度分析
本文提出的方法的计算时间复杂度分为两个部分:一个是特征抽取的计算时间,另一个是特征匹配的计算
时间.在特征抽取阶段,在给定的尺度下,对于每一个轮廓点,通过计算其左右卷积向量得到高斯卷积角的计算
2
时间复杂度为 O(T),因此,计算所有 T 个轮廓点的高斯卷积角的计算时间复杂度为 O(T ),则所有轮廓点的 k 个
2
尺度的高斯卷积角的计算复杂度为 O(kT ),即为特征抽取阶段的计算时间复杂度.
在特征匹配阶段,通过计算两个形状的高斯卷积角特征向量集合的增强 Hausdorff 距离来比较两个形状的
差异.其中,计算两个高斯卷积角特征向量集合的任意两个元素的距离(公式(22))的计算复杂度为 O(k),计算公
式(23)中的 ∑ T min d (ω ( ),t ω ( ))t 的计算复杂度为 O(kT ).而对于计算公式(23)中η A 的算法的第 2 步:为集
2
m= 1 n= 1,...,T A m B n
合Ψ A 中的每个元素ω A (t m ),在集合Ψ B 中找到其最佳匹配,已在前面的计算 min d (ω ( ),t ω ( ))t 时得到,因此,额
n= 1,...,T A m B n
2
2
外计算η A 的时间为 O(T).从而得到整个特征匹配阶段的计算时间复杂度为 O(kT +T)=O(kT ).
4 实验结果和分析
为了评估本文所提出的高斯卷积角形状描述方法的性能,我们用公开的植物叶片图像数据库 CVIP100 数
据集 [17] 和中欧木本植物(MEW)数据集 [27] 测试本文提出的算法的叶片图像检索性能,用公开的 Kimia 形状数据
集 [28] 的形状检索实验评估本文提出的方法的通用性.为了检验本文所提出的方法的有效性和优越性,我们选择
[9]
了 4 种具有较高性能的形状检索算法进行实验比较,它们是内部距离形状上下文(IDSC+DP) 、多尺度距离矩
阵(MDM) [16] 、高度函数(height function) [29] 和分层弦切法(HSC) [17] .此外,在实验中,我们还将本文提出的高斯卷
积角描述子与近年来提出的深度特征进行检索性能对比,我们选用了近年来比较先进与流行的预训练网络模
型 VGGNet-19 [30] 和 RESNet-152 [31] .实验平台是一台 CPU 为 Intel(R) Core(TM) i5,操作系统为 Windows 10,内存
为 8GB 的个人计算机,实现算法的编程工具为 MATLAB R2014a.而运行两个深度学习方法的平台是 CPU 为
Intel(R) Core(TM) i9-9900k,内存为 32GB,显卡为 NVIDIA RTX 2080 的计算机.本文提出的方法的参数设置为:
叶片轮廓均匀采样的点的个数为 256,所使用的尺度个数 k 设置为 8.