Multicore construction of k-d trees with applications in graphics and vision

computer graphics;vision;spatial data structures;k-d trees;multicore;parallel algorithms;ray-tracing;nearest neighbor search;image search;object detection;point cloud processing

Lu, Victor

关键词: computer graphics;    vision;    spatial data structures;    k-d trees;    multicore;    parallel algorithms;    ray-tracing;    nearest neighbor search;    image search;    object detection;    point cloud processing;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/46588/Victor_Lu.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

The k-d tree is widely used in graphics and vision applications for accelerating retrieval from large sets of geometric entities in R^k. Despite speeding up an otherwise brute force search, the time to construct and traverse the k-d tree remain a bottleneck in many applications. Increasing parallelism in modern processors offers hope for further speedups. But while traversal is easily parallelized over a large number of queries, construction is not as easily parallelized and will become a serial bottleneck if left unparallelized. This thesis studies parallel k-d tree construction and its applications. The results are new multicore parallelizations of SAH k-d tree and FLANN k-d tree variants, and new ways of utilizing these parallelizations for accelerating object detection and scripting point algorithms.