|
ДокладыУскорение поиска k ближайших соседей в точечных множествахМосковский Государственный Университет им. М.В.Ломоносова, ф-т ВМК, каф. Суперкомпьютеров и квантовой информатики, nikolsky@cs.msu.ru Облако точек представляет собой набор точек, сканированных с некоторой поверхности . Различные алгоритмы обработки таких наборов точек (фильтрация, сегментация, восстановлении поверхности) требуют поиска ближайших соседей для каждой точек. Поскольку поиск соседей может занимать значительную долю общего времени работы прикладной программы, оптимизация алгоритма поиска является ключевым моментом повышения эффективности обработки облака точек. Одним из способов ускорения поиска соседей является индексация - построение дополнительной ускоряющей структуры, которая позволяет сделать быстрее поиск. Как правило в качестве индекса используется kd-дерево. Однако в работе [1] было указано, что на практике более простой способ - поиск на решётке - может быть не менее эффективен. К сожалению, в этой работе не было проведено сравнения поиска соседей на решётке с какими-либо другими способами индексации. В данной работе проведено сравнение поиска k ближайших соседей с использованием индексации на решётке и с помощью kd-дерева. Показано, что при определённом количестве ячеек поиск на решётке может быть быстрее. Исследована зависимость эффективность поиска соседей на решётке в зависимости от количества ячеек. Литература 1. A.Piegl, W. Tiller Algorithm for finding all k nearest neighbors // Computer-Aided Design Volume 34, Issue 2, 2002, pp 167-172
Материалы доклада |
