在维 n空间 Rn中, M个点构成集合 S={S1, S2, …, SM}, 每个点 Si={Si1, Si2, …, Sij, …, Sin}, i=1, 2, …, M, j=1, 2, …, n, Sij是点 Si的第 j个属性。设 X和 Y是集合 S任意两点, Dist(X, Y)和 Sim(X, Y)分别为 X和 Y的距离和相似性。一般来说, Sim(X, Y)随Dist(X, Y)增大而减少, 当X和Y重合时, Sim(X, Y)=1, 当二者无限远时, Sim(X, Y)=0。因此, Sim(X, Y)可视为度量S上点之间距离远近的二元函数 F: S×S→[0, 1]满足性质:

(1)有界性: F(X, Y)∈ [0, 1];

(2)对称性: F(X, Y)=F(Y, X)。

通常采用距离函数Dist(X, Y)间接度量Sim(X, Y), 主要方法有: 曼哈顿距离、 欧几里德距离等, 这些方法适用于低维空间。 但是, 随着维度增加, 传统方法的最近距离和最远距离趋于相同, 相似性不再具有区分度。 针对该问题, 研究人员重新定义适用于高维空间的相似性度量方法, 包括: Hsim(X, Y), Gsim(X, Y), Close(X, Y), Esim(X, Y)等。 但是, 它们仅对某些特定类型数据有效, 不适用于所有数据。 易莉桦提出的Psim(X, Y)适用于多种类型数据, 但其值域依赖于空间维度n, 不利于数据降维分析。 本工作将其修改为式(1)形式, 在保持效果不变情况下, 值域约束在[0, 1]。

NPsim(X, Y)=∑j=1n1nδ(Xj, Yj)1-|Xj-Yj|mj-njE(X, Y)n(1)

其中, X_j和Y_j是X和Y在第j维的值, δ (X_j, Y_j)是判别函数, 当X_j和Y_j处于同一区间[n_j, m_j]时, δ (X_j, Y_j)=1, 计算X和Y在第j维相似性; 否则, δ (X_j, Y_j)=0, 认为第j维是噪声维或稀疏维, 不予计算; m_j和n_j是X_j和Y_j共同隶属的区间端点; E(X, Y)是X和Y具有相同区间编号的维度个数。 关于不同维度上数据区间划分方法。

为了验证该方法效果, 采用Matlab生成三种不同分布类型数据: 独立同分布IID、 相关同分布Uniform、 非独立同分布DID。 每种类型按照维度10, 30, 50, 100, 150, 200, 250, 300, 350和400各生成1 000条数据。 按照式(2)计算最远邻和最近邻的相对差^[4]。

ν=Dmaxn-DminnDavgn  (2)

其中, D_maxn, D_minn, D_avgn分别表示数据在n维空间的最大、 最小、 平均相似度。 分别测试曼哈顿距离、 欧几里德距离Hsim(X, Y), Gsim(X, Y), Close(X, Y), Esim(X, Y), Psim(X, Y)和NPsim(X, Y), 结果如图1— 图3所示。

按照结果特征, 测试方法分两类。 第一类包括曼哈顿距离、 欧几里德距离Hsim(X, Y), Gsim(X, Y), Close(X, Y), Esim(X, Y); 第二类包括Psim(X, Y)和NPsim(X, Y)。 后者比前者的相对差高出两到三个数量级, 所以第二类方法性能远远优于第一类方法。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 独立同分布IID数据的相对差Fig.1 Relative difference of independent identical distribution data

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 相关同分布Uniform数据的相对差Fig.2 Relative difference of relative identical distribution data

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 非独立同分布DID数据的相对差Fig.3 Relative difference of dependent identical distribution data

为了比较NPsim(X, Y)和Psim(X, Y)的效果差异, 分别采用NPsim(X, Y)和Psim(X, Y), 计算DID数据的相似性, 其最大值、 最小值和平均值随维度变化如图4所示。 可以看出, Psim(X, Y)的值域随维度增加而增大, 不利于比较数据在不同维度下的相似性, 而NPsim(X, Y)的相似性范围是[0, 1], 不受维度影响。 在不同维度下, Psim(X, Y)相似性超过1的个数如表1所示。 本组实验共计得到1 000× 1 000=100万个相似性, 但Psim(X, Y)方法却有6%~15%的结果超过1, 不同维度数据相似性不再具有可比性。 因此, 使用NPsim(X, Y)方法, 可以满足不同维度下相似性比较的需要。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 采用DID数据比较两种方法的效果Fig.4 Effect comparison of two methods with DID data

表1

Table 1

表1(Table 1)

表1 在不同维度下, Psim(X, Y)方法相似性超过1的个数 Table 1 The number of calculated distance that is more than 1 with Psim(X, Y) method in different dimensionalities 维度 个数 维度 个数 10 159 192 200 105 570 30 131 236 250 74 285 50 112 364 300 84 341 100 11 456 350 50 898 150 97 624 400 63 114

表1 在不同维度下, Psim(X, Y)方法相似性超过1的个数 Table 1 The number of calculated distance that is more than 1 with Psim(X, Y) method in different dimensionalities

在给定的颜色空间中, 采用光谱表示颜色, 可以将每个颜色表示为唯一的高维数据。 NPsim的核心是将差异较大的维度视为噪声维, 不参与相似度计算; 人眼分辨颜色时, 对于颜色上与整体差异较大、 没有明显含义的区域, 视为噪声不参与比较。 可以看出, NPsim函数计算相似性的原理和人眼-颜色感知模型原理相似。 因此, 采用NPsim(X, Y)计算方法, 能准确得到颜色空间中任意颜色之间的相似性。 与其他方法相比, 该方法减少高维数据“ 维度灾难” 对颜色相似性计算的影响, 提高计算精度。

在n维空间Rⁿ中, M个点S₁, S₂, …, S_M构成M× N矩阵NPsimMat, 称为NPsim矩阵, 该矩阵元素NPsimMat[p][q]保存点S_p和S_q(1≤ p, q≤ M)之间的NPsim信息, 包括三个属性: 下标p, q, NPsim值。 可以看出, NPsim矩阵能够表示任意点之间的相似性。

对NPsim矩阵每行元素按照NPsim值降序排列, 得到有序NPsim矩阵SortNPsimMat。 该矩阵表示点之间的相似性大小, 对第p行元素来说, 随着列号增加, 点S_p和对应点的相似性逐渐降低。

将颜色空间中的颜色表示为对应光谱, 然后计算出所有颜色之间的有序NPsim矩阵。 该矩阵每行元素的NPsim值逐渐递减, 表示其他颜色与该行所表示颜色的相似性逐渐减弱, 视为以NPsim值为索引的递减数据序列。 由此可知, 整个有序NPsim矩阵构成给定颜色空间所有颜色的索引树, 进一步提高颜色近邻搜索的效率。

在给定颜色空间中, 构建有序NQsim矩阵表示颜色索引树, 能够直接找到任意颜色的所有近邻, 该方法整体框架如图5所示。

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 算法整体框架Fig.5 Whole algorithm framework

首先, 计算颜色空间中所有颜色之间的NPsim值, 构建NPsim矩阵; 然后按照相似性, 对NPsim矩阵的每行元素降序排列, 得到有序NPsim矩阵。 根据有序NPsim矩阵, 可以进行颜色近邻搜索。

3.2.1 构建NPsim矩阵

本阶段生成表示所有颜色相似性关系的NPsim矩阵, 设颜色空间中有多种颜色, 每种颜色采用长度为n的光谱表示。 主要步骤如下:

Step 1: 将光谱表示为n维空间Rⁿ中的点S_i, i=1, 2, …, M, 逐行保存在M× n矩阵DataSet中;

Step 2: 对DataSet每列元素按照升序排列, 得到矩阵SortDataSet;

Step 3: 将SortDataSet每列元素划分为G=$\lceil$θ · n$\rceil$个区间, 每个区间点的个数T=$\lceil$M/G$\rceil$; 同时, 按照升序将每个区间端点保存在矩阵FirCutBound中;

Step 4: 参照矩阵FirtCutBound, 将矩阵DataSet元素值转换为所在维度区间编号, 得到区间编号矩阵FirNumSet;

Step 5: 建立M× M矩阵SameDimNum, 其元素SameDimNum[p][q]保存点S_p和S_q在所有维中区间编号相同维的个数;

Step 6: 将矩阵SortDataSet每列元素划分为G'=G-1个区间, 每个区间点的个数T'=|M/G'|, 同时, 按照升序将每个区间端点保存在矩阵SecCutBond中;

Step 7: 仿照Step 4, 得到区间编号矩阵SecNumSet;

Step 8: 仿照Step 5, 修改矩阵SameDimNum, 如果点S_p和S_q某一维在Step 4区间编号不同, 但在Step 7区间编号相同, 那么SameDimNum[p][q]增加1;

Step 9: 根据式(1), 以及Step 3— Step 9的数据, 构建NPsim矩阵NPsimMat, 该矩阵规模M× M。

3.2.2 相似矩阵有序化

本阶段生成表示每种颜色与其他颜色相似性大小关系的有序NPsim矩阵, 主要步骤如下:

Step 1: 建立M× M矩阵SortNPsimMat, 初始值与NPsimMat相同;

Step 2: 对SortNPsimMat的每行元素, 按照NPsim值降序排列。

3.2.3 近邻搜索

在SortNPsimMat中对第i种颜色进行K近邻搜索方法如下:

遍历该矩阵的第i行, 找出最前面K个NPsim矩阵元素, 在这些元素所对应颜色中, 异于第i种颜色的颜色, 就是第i种颜色的K近邻。

由附录1可知, 构建有序NPsim矩阵时间复杂度O(M²n), KD树近邻搜索算法和SR树近邻搜索算法构建索引树时间复杂度均是O(Mlog₂M· n)^[9], 所以本算法在构建阶段性能亟待改进。 但是, 在K近邻搜索时, 本算法时间复杂度为O(1), 能直接确定给定颜色的K个近邻, 且搜索时间与K值无关; 而其他两种方法需要遍历索引树, 时间复杂度O(Klog₂M), 搜索时间随K值增加而增加, 所以本算法在搜索阶段性能优秀。

由附录2可知, 通过修改数据结构, 能够将第三类和第四类中间矩阵构建阶段的时间复杂度降低一个幂次; 通过预先存储、 代码外提等策略, 可以降低有序NPsim矩阵的生成时间。 此外, 第一类中间矩阵的逐列元素排序和第四类中间矩阵的逐列元素比较具有独立性, 所以这两类矩阵易于并行构建, 但索引树不易并行构建。 因此, 通过并行构建, 能够将本算法时间复杂度降低为O(Mn), 超过传统算法的速度。

蒙赛尔全光泽色系包含1 600种颜色, 所有颜色按照色调(H)、 亮度(V)、 饱和度(C)三个维度排列在蒙赛尔色立体中, 表示为HV/C。 其中, 色调包括10种基本色调: 红(R)、 黄红(YR)、 …、 紫(P)、 红紫(RP), 每种基本色调又划分为10等分, 在基本色调字母前面添加数字1~10; 亮度共分11级: 0, 1, …, 10, 其中0最暗, 10最亮; 纯度共分14种: 1, 2, …, 14, 其中1表示纯度为0, 14表示纯度为100%。

从光谱颜色研究中心(http: //www.uef.fi/fi/spectral/home)下载蒙赛尔全光泽色系所有颜色的光谱反射比数据。 测量设备是Perkin-Elmer Lambda 18 UV/VIS光谱仪, 测量范围是380~780 nm, 测量步长是1 nm。 因此, 这套数据包含1 600条数据, 每条数据是对应颜色在401种不同波长下的光谱反射比, 构成长度为401的高维数据。

首先, 使用蒙赛尔色系光谱建立有序NPsim矩阵; 同时建立KD树和SR树, 统计构建有序NPsim矩阵、 KD树和SR树的时间。 然后, 在蒙赛尔色立体上选择颜色, 进行K近邻搜索。 因为蒙赛尔色立体具有色彩连续性。 所以, 对蒙赛尔色立体颜色进行近邻搜索时, 查询颜色和近邻在色立体上的位置必定接近或连续。

因此, 从实际距离和视觉效果两方面比较精度。 一方面, 比较不同算法的查询颜色与K近邻距离的均值。 按照蒙赛尔色系颜色表示方式, 分别用HV/C和H_KV_K/C_K表示查询颜色和K近邻, 则二者之间的距离如式(3)

Distance=|HK-H|+|VK-V|+|CK-C|(3)

式(3)即查询颜色和K近邻之间的曼哈顿距离, 亮度和饱和度已经量化, 可以直接计算|V_K-V|和|C_K-C|; 但色调没量化, 不能直接计算|H_K-H|。 色调量化方法: 保持亮度和饱和度不变, 从1R开始, 环绕蒙赛尔色立体一周, 到10RP结束, 将中间100个点设置为1, 2, …, 100。 色调量化后可以直接计算|H_K-H|。

另一方面, 选择一个颜色代表所有待查询颜色, 比较该颜色在三种算法下的K近邻颜色差异。

在速度分析方面, 因为KD树和SR树进行K近邻搜索的时间与K有关, 所以让K从1逐渐增加, 计算平均搜索时间; 同时, 也计算本方法在不同K值下的平均搜索时间。

根据4.2节的方法, 从蒙赛尔色立体中选择1 000个查询颜色, 采用本方法、 基于KD树和SR树的方法进行K近邻搜索, 并在速度和精度两方面比较。 实验环境: 处理器AMD Athlon(tm) II X2 250 Processor 3.01 GHz、 内存韩国现代2G、 操作系统Windows XP SP3、 开发环境VS 2013, 无并行加速措施。

4.3.1 精度分析

采用三种方法, 在不同K值下, 所有查询颜色与其K近邻距离的均值和方差如图6和图7所示, 可以看出, 与基于KD树/SR树的颜色近邻搜索算法相比, 本方法得到的颜色近邻在整体上与查询颜色距离更近, 距离波动性更低。 说明本算法精度高、 稳定性强。

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 所有查询颜色的K近邻距离均值Fig.6 Mean KNN distance of all queried colors

图7

Fig.7

	Figure Option ViewDownloadNew Window
	图7 所有查询颜色的K近邻距离方差Fig.7 KNN distance variance of all queried colors

选择的查询颜色为5BG3/2, 色彩如图8所示, 令K=6, 三种算法的K近邻如表2— 表4所示。 表2的K近邻距离是NPsim函数相似性, 其值越来越小; 表3和表4的K近邻距离是欧式距离, 其值越来越大。 为了更直观度量色彩差异, 还计算查询颜色和其K近邻在RGB颜色空间的距离(RGB分量差绝对值之和)。 从色彩角度可知, 基于NPsim矩阵的颜色近邻搜索算法, 所得近邻与查询颜色最相似; 基于KD树/SR树的颜色近邻搜索算法, 所得某些近邻, 其颜色与查询颜色存在差异。 从蒙赛尔距离角度可知, 本算法所得近邻距离小于其他两种方法, 而且存在逆序现象(近邻距离在近邻序列中的相对次序与其序号的相对次序不同, 即近邻序列中某近邻前驱、 近邻本身、 近邻后继与查询颜色的距离不满足递增关系)的近邻个数也较少, 表2逆序近邻有2个(10BG3/2和5BG3/1), 表3逆序近邻有4个(10BG3/2, 2.5BG3/2, 5B3/4和5G3/4), 表4逆序近邻有4个(10BG3/2, 2.5BG3/2, 7.5BG4/6和10G3/2)。

图8

Fig.8

	Figure Option ViewDownloadNew Window
	图8 5BG3/2的颜色Fig.8 Color of 5BG3/2

表2

Table 2

表2(Table 2)

表2 基于有序NPsim矩阵的颜色近邻搜索算法结果 Table 2 Color neighbor searching result based on sequential NPsim matrix

表2 基于有序NPsim矩阵的颜色近邻搜索算法结果 Table 2 Color neighbor searching result based on sequential NPsim matrix

表3

Table 3

表3(Table 3)

表3 基于KD树的颜色近邻搜索算法结果 Table 3 Color neighbor searching result based on KD tree

表3 基于KD树的颜色近邻搜索算法结果 Table 3 Color neighbor searching result based on KD tree

表4

Table 4

表4(Table 4)

表4 基于SR树的颜色近邻搜索算法结果 Table 4 Color neighbor searching result based on SR tree

表4 基于SR树的颜色近邻搜索算法结果 Table 4 Color neighbor searching result based on SR tree

在表2中, 颜色近邻的视觉差异很小, 但光谱存在一定差异, 属于“ 同色异谱” 现象。 采用传统色差公式, 如蒙赛尔距离、 RGB距离等, 计算结果的差异不大, 区分度不好。 但是, 采用NPsim函数计算距离, 结果具有明显的区分度。 由此可知, NPsim函数在高维度颜色差异评价时优势明显。

4.3.2 速度分析

在构建阶段, 三种方法耗时如表5所示。 可以看出, 构建有序NPsim矩阵的时间比构建KD树和SR树的时间要长。

在搜索阶段, 这些方法在不同值下近邻搜索的平均响应时间如图9所示。 可以看出, 本算法响应时间数量级在10^-6左右, 而其他两种方法响应时间数量级在10^-2左右, 本算法速度是其他两种方法的1万倍左右; 此外, 本方法响应时间与值无关, 而其他两种方法响应时间随K值增加而增加, 所以本方法速度优势明显。

表5

Table 5

表5(Table 5)

表5 构建阶段三种方法消耗的时间 Table 5 Running time in the establishment stage of three methods 有序NPsim矩阵 KD树 SR树 构建耗时/s 18.6 1.6 2.4

表5 构建阶段三种方法消耗的时间 Table 5 Running time in the establishment stage of three methods

图9

Fig.9

	Figure Option ViewDownloadNew Window
	图9 三种方法在不同K值下近邻搜索的平均响应时间Fig.9 Average searching time of three KNN methods in different K

本算法构建有序NPsim矩阵的时间复杂度O(M²n), 而构建KD树和SR树的时间复杂度O(Mlog₂M· n); 所以本算法在构建阶段耗时大。 但是, 构造出有序NPsim矩阵后, 本算法可以直接访问矩阵得到颜色近邻, 时间复杂度O(1), 而其他两种方法都需要在KD树或SR树中进行检索, 时间复杂度O(Klog₂M), 所以本算法在搜索阶段速度优势明显。