A Nearest Neighbor Search Algorithm for Color Based on Sequential NPsim Matrix
ZHANG Ting1,2, WANG Gong-ming3*
1. School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
2. College of Information Engineering, Minzu University of China, Beijing 100081, China
3. Institute of Biophysics, Chinese Academy of Sciences, Beijing 100101, China
Abstract：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 K value. 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矩阵的颜色近邻搜索[J]. 光谱学与光谱分析, 2018, 38(02): 377-385.
ZHANG Ting, WANG Gong-ming. A Nearest Neighbor Search Algorithm for Color Based on Sequential NPsim Matrix. SPECTROSCOPY AND SPECTRAL ANALYSIS, 2018, 38(02): 377-385.
[1] Ji Y K, Chang Y K, Yang S S, In S K. Pattern Recognition, 2001, 34(6): 1189.
[2] Warren B P. Approximate Dynamic Programming: Solving the Curses of Dimensionality(2nd Edition). John Wiley & Sons Press，2011.
[3] Jia P, Dinesh M. Sigspatial Special, 2012, 41(4): 211.
[4] YANG Feng-zhao, ZHU Yang-yong(杨风召, 朱扬勇). Journal of Computer Research and Development(计算机研究与发展), 2004, 41(2): 361.
[5] HUANG Si-da, CHEN Qi-mai(黄斯达, 陈启买). Computer Applications and Software(计算机应用与软件), 2009, 26(9): 102.
[6] SHAO Chang-sheng, LOU Wei, YAN Li-min(邵昌昇, 楼 巍, 严利民). Computer Technology and Development(计算机技术与发展), 2011, 21(2): 1.
[7] WANG Xiao-yang, ZHANG Hong-yuan, SHEN Liang-zhong, et al(王晓阳, 张洪渊, 沈良忠, 等). Computer Technology and Development(计算机技术与发展), 2013, 23(5): 30.
[8] JIA Xuan-yao(郏宣耀). Computer Applications(计算机应用), 2005, 25(S1): 176.
[9] Russell A B. Journal of Computer Graphics Techniques, 2015, 4(1): 50.
