Реализация R-дерева в Matlab
Пожалуйста, кто-нибудь расскажет мне, как мы можем реализовать структуру R-дерева в Matlab для ускорения системы поиска изображений, я хотел бы сообщить вам, что в моей базе данных имеется вектор признаков цветовой гистограммы (многомерный), а также I I имеет вектор расстояния для меры сходства...
Спасибо
3 ответа
Я не использую Matlab. Поэтому я не имею ни малейшего представления, сколько затрат связано с Matlab со структурами индекса. Кажется, он не предназначен для таких вещей.
R-деревья, кажется, имеют большое значение. Судя по http://elki.dbs.ifi.lmu.de/wiki/Benchmarking некоторые алгоритмы могут получить огромную пользу от хорошей структуры индекса. Числа на этой веб-странице в 5-7 раз быстрее в наборе данных цветовой гистограммы изображения 110250.
Исходя из моего опыта, R-Trees действительно может быть довольно сложно понять правильно. Но только если вы хотите пройти полный путь. Если у вас есть статическая база данных, вы можете легко избавиться от R-Tree с массовой загрузкой. Ни массовую загрузку, ни запросы не очень сложно сделать. R-Trees становятся беспорядочными, когда вы хотите выполнить оптимизацию R*-Tree со сложными стратегиями разделения, повторными вставками, балансировкой, и делать все это эффективно и на диске с помощью интеллектуального кэширования. Но пока вы работаете в оперативной памяти и не добавляете объекты динамически, R-дерево с массовой загрузкой STR очень поможет и будет намного проще в реализации.
Возможно, вам все-таки лучше построить что-то, на чем уже работает R-Tree. Скажите SQLite с помощью модуля rtree или ELKI, упомянутых выше.
Я не знаком с R-деревьями конкретно, но в целом деревья являются динамическими структурами данных. Matlab на самом деле не создает динамические структуры данных, пока вы не начнете использовать его возможности OO. Если вы не хотите этого делать, вы можете объединить дерево в массив ячеек. Например, я напишу (строго) двоичное дерево, сплющенное в массив ячеек, что избавит меня от необходимости рисовать дерево. Вот оно:
{1,{2},{3}}
который представляет двоичное дерево с корнем 1 и ветвями слева до 2, справа до 3. Я могу сделать это глубже:
{1,{2,{5,6}},{3,{7,8}}}
который добавляет еще один уровень к предыдущему дереву. Если вы хотите добавить данные в любой из узлов, то ваше (первое) дерево может выглядеть так:
{1,[a b c],{2,[e f]},{3,[h i j k l]}}
Альтернативой этому было бы определить ваши узлы отдельно, как это
node1 = [a b c]; node2 = [e f]; node3 = [h i j k l],
тогда твое дерево становится
{node1, node2, node3}
Тогда вашей задачей становится написание функций для построения и обхода дерева в выбранном вами представлении. Большинство функций дерева лучше всего писать как рекурсии. Любой хороший текст и множество интернет-сайтов расскажут вам все, что вы хотите знать о таких функциях.
Реализация R-дерева на самом деле не простая задача. Вы можете использовать связывание matlab для библиотеки LidarK, оно должно быть достаточно быстрым. Код здесь: http://graphics.cs.msu.ru/en/science/research/3dpoint/lidark
Если вы решите использовать kd-дерево (что типично для поиска изображений), то есть и хорошая реализация. http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN