基于有序NPsim矩阵的颜色近邻搜索  

A Nearest Neighbor Search Algorithm for Color Based on Sequential NPsim Matrix

作　　者：张廷 王功明[3] 

机构地区：[1]北京邮电大学计算机学院,北京100876 [2]中央民族大学信息工程学院,北京100081 [3]中国科学院生物物理研究所,北京100101

出　　处：《光谱学与光谱分析》2018年第2期377-385,共9页Spectroscopy and Spectral Analysis

基　　金：国家自然科学基金项目(61502475)资助

摘　　要：基于光谱表示法颜色近邻搜索的核心是高维向量近邻搜索,相似性度量和索引树构建是影响其性能的关键,前者存在等距性问题,后者存在构建困难、查询效率低、不易动态调整等问题,从而严重影响颜色近邻搜索算法的性能。使用NPsim函数计算颜色相似性,结合有序矩阵组织颜色空间数据,提出一种基于有序NPsim矩阵的颜色近邻搜索算法。首先,计算颜色空间中所有颜色之间的NPsim值,构建反映所有颜色相似性关系的NPsim矩阵;然后,按照每种颜色与其他颜色的相似性,对NPsim矩阵的每行元素降序排列,从而得到反映每种颜色与其他颜色相似性大小关系的有序NPsim矩阵;最后,对于颜色空间中任意给定的颜色,根据它在有序NPsim矩阵中的行号,就能够直接找到该颜色的所有近邻。采用蒙赛尔全光泽色系光谱构建有序NPsim矩阵,同时建立KD树和SR树,分别进行K近邻搜索,并从精度和速度两方面比较。在精度方面,本算法得到的颜色近邻与查询颜色距离最近、相似性最好,存在逆序现象的近邻个数最少;在速度方面,构建有序NPsim矩阵的时间比构建KD树和SR树的时间要长,但近邻搜索速度是KD树/SR树的1万倍左右,而且与K值无关;此外,构建有序NPsim矩阵易于并行化,而构建KD树和SR树不易并行化,并行化后构建有序NPsim矩阵的速度会超过构建KD树和SR树的速度。实验结果表明该方法适用于颜色近邻搜索。The core of color nearest neighbor search based on spectral representation is high dimensional nearest neighbor searching,which is affected by equidistance of similarity measurement and low query efficiency of indexed tree seriously.To solve this problem,a color nearest neighbor search algorithm based on sequential NPsim matrix was proposed.First of all,the NPsim values between every two colors in color space were calculated and stored into the corresponding position of the NPsim matrix.After that,the elements in each raw of NPsim matrix were sorted in descending order to represent the similarity degree from strong to weak.Finally,the Top-K neighbors of given color can be found directly according to its raw number in the sequential NPsim matrix.To validate this algorithm,the nearest neighbor search algorithms based on KD-tree or SR-tree were compared on Munsell spectral data set.Experimental results indicated that the precise was better than that of other algorithms,the construction time of sequential NPsim matrix was longer than that of them,but the searching speed was more than thousands times of others and independent of Kvalue.In addition,the construction of sequential NPsim matrix was easy to be paralleled to speed up,but the parallelization of construction of KD-tree or SR-tree was difficult.

关 键 词：颜色 近邻搜索 光谱 相似性 索引树 有序NPsim矩阵 蒙赛尔 

分 类 号：O433.4[机械工程—光学工程]