ELGEON 2 Жалоба Опубликовано May 7, 2012 http://www.compvision.ru/forum/index.php?showtopic=864 лекция №4 Спасибо =) Начал читать, затянуло =) Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
ELGEON 2 Жалоба Опубликовано May 7, 2012 http://www.compvision.ru/forum/index.php?showtopic=864 лекция №4 Нашел одну статью: K-d дерево строится по следующему правилу: • начальное множество разбивается по значениям векторов в одной из координат, например, по i = 1,…k, на два подмножества; • i выбирается таким образом, чтобы разброс значений по данной координате был максимальным; • разбиение проводится по медиане m, так что одинаковое количество точек оказывается с одной и с другой стороны; • в вершине дерева хранятся значения i , m, разброс значений векторов по каждой координате; • для полученных вершин процесс повторяется. Для поиска n ближайших соседей к вектору q в построенном дереве: • сначала дерево обходится вниз до листа содержащего «ближайшую» к q точку. Эта точка не обязана быть ближайшей, это только первое приближение; • во время спуска по дереву заполняется список поддеревьев, которые еще не обходили. Также запоминаются расстояния до них, которое определяется как минимальное расстояние от точки q до любой точки, находящейся в границах значений поддерева; • из списка выбираем ближайшее к q поддерево и продолжаем поиск в нём; • расстояние до каждого нового найденного претендента сравнивается с радиусом сферы найденных точек с центром в точке q. Если данное расстояние меньше, то точку на сфере заменяем этим претендентом. Алгоритм работает до тех пор, пока в списке есть поддеревья с расстоянием, меньшим радиуса сферы найденных точек. 2 Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
mrgloom 242 Жалоба Опубликовано January 18, 2017 Наверно уже не актуально, но на GSoC 2012 был проект как я понял посвященный изначальной теме поста. http://correlatorgsoc2012.blogspot.ru Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах