Fast Search Algorithm of Nonlinear LUT Based on K-D Tree

For the satisfaction of International Color Consortium (ICC) profile specification, it makes necessary to obtain the uniform profile data by interpolation. Color data sampled directly is usually not uniform for LUT (look-up table) created. Now color calibration is efficiently used for uniform data with tetrahedral interpolation. However, location of proper tetrahedron for interpolation for non-uniform data is computed costly for creating the profile data, especially for high-quality printing with a large of color data. This paper proposes a fast search algorithm using K-D tree as the data structure. Firstly the K-D tree is build by recursion in a large of non-uniform data. The fast search algorithm is realized by the establishment of search path, backtracking operation and traversal search path. A stack and filter are introduced to get a minimum hexahedron through filtering out the unnecessary points on the same quadrant, only reserve the point that the distance is smallest in a quadrant. The experiment shows that the algorithm is faster, especially for a large of sampled data.