1%Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. 2%Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved. 3% 4%THE BSD LICENSE 5% 6%Redistribution and use in source and binary forms, with or without 7%modification, are permitted provided that the following conditions 8%are met: 9% 10%1. Redistributions of source code must retain the above copyright 11% notice, this list of conditions and the following disclaimer. 12%2. Redistributions in binary form must reproduce the above copyright 13% notice, this list of conditions and the following disclaimer in the 14% documentation and/or other materials provided with the distribution. 15% 16%THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17%IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18%OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19%IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20%INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21%NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22%DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23%THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24%(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25%THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 27function [indices, dists] = flann_search(data, testset, n, search_params) 28%NN_SEARCH Fast approximate nearest neighbors search 29% 30% Performs a fast approximate nearest neighbor search using an 31% index constructed using flann_build_index or directly a 32% dataset. 33 34% Marius Muja, January 2008 35 36 37 algos = struct( 'linear', 0, 'kdtree', 1, 'kmeans', 2, 'composite', 3, 'lsh', 6, 'saved', 254, 'autotuned', 255 ); 38 center_algos = struct('random', 0, 'gonzales', 1, 'kmeanspp', 2 ); 39 log_levels = struct('none', 0, 'fatal', 1, 'error', 2, 'warning', 3, 'info', 4); 40 41 default_params = struct('algorithm', 'kdtree' ,'checks', 32, 'eps', 0.0, 'sorted', 1, 'max_neighbors', -1, 'cores', 1, 'trees', 4, 'branching', 32, 'iterations', 5, 'centers_init', 'random', 'cb_index', 0.4, 'target_precision', 0.9,'build_weight', 0.01, 'memory_weight', 0, 'sample_fraction', 0.1, 'table_number', 12, 'key_size', 20, 'multi_probe_level', 2, 'log_level', 'warning', 'random_seed', 0); 42 43 if ~isstruct(search_params) 44 error('The "search_params" argument must be a structure'); 45 end 46 47 params = default_params; 48 fn = fieldnames(search_params); 49 for i = [1:length(fn)], 50 name = cell2mat(fn(i)); 51 params.(name) = search_params.(name); 52 end 53 if ~isnumeric(params.algorithm), 54 params.algorithm = value2id(algos,params.algorithm); 55 end 56 if ~isnumeric(params.centers_init), 57 params.centers_init = value2id(center_algos,params.centers_init); 58 end 59 if ~isnumeric(params.log_level), 60 params.log_level = value2id(log_levels,params.log_level); 61 end 62 63 if (size(data,1)==1 && size(data,2)==1) 64 % we already have an index 65 [indices,dists] = nearest_neighbors('index_find_nn', data, testset, n, params); 66 else 67 % create the index and search 68 [indices,dists] = nearest_neighbors('find_nn', data, testset, n, params); 69 end 70end 71 72function value = id2value(map, id) 73 fields = fieldnames(map); 74 for i = 1:length(fields), 75 val = cell2mat(fields(i)); 76 if map.(val) == id 77 value = val; 78 break; 79 end 80 end 81end 82function id = value2id(map,value) 83 id = map.(value); 84end 85