001/*
002        AUTOMATICALLY GENERATED BY jTemp FROM
003        /Users/jsh2/Work/openimaj/target/checkout/machine-learning/nearest-neighbour/src/main/jtemp/org/openimaj/knn/approximate/#T#NearestNeighboursKDTree.jtemp
004*/
005/**
006 * Copyright (c) 2011, The University of Southampton and the individual contributors.
007 * All rights reserved.
008 *
009 * Redistribution and use in source and binary forms, with or without modification,
010 * are permitted provided that the following conditions are met:
011 *
012 *   *  Redistributions of source code must retain the above copyright notice,
013 *      this list of conditions and the following disclaimer.
014 *
015 *   *  Redistributions in binary form must reproduce the above copyright notice,
016 *      this list of conditions and the following disclaimer in the documentation
017 *      and/or other materials provided with the distribution.
018 *
019 *   *  Neither the name of the University of Southampton nor the names of its
020 *      contributors may be used to endorse or promote products derived from this
021 *      software without specific prior written permission.
022 *
023 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
024 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
025 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
026 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
027 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
028 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
029 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
030 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
031 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
032 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
033 */
034package org.openimaj.knn.approximate;
035
036import java.util.Arrays;
037import java.util.List;
038
039import org.openimaj.citation.annotation.Reference;
040import org.openimaj.citation.annotation.ReferenceType;
041import org.openimaj.knn.FloatNearestNeighbours;
042import org.openimaj.knn.NearestNeighboursFactory;
043import org.openimaj.util.pair.*;
044
045/**
046 * Fast Nearest-Neighbours for float data using an ensemble of Best-Bin-First KDTrees. 
047 * <p>
048 * Implementation inspired by http://www.robots.ox.ac.uk/~vgg/software/fastann/
049 * 
050 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
051 * @author Sina Samangooei (ss@ecs.soton.ac.uk)
052 */
053@Reference(
054        type = ReferenceType.Inproceedings,
055        author = { "Marius Muja", "David G. Lowe" },
056        title = "Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration",
057        year = "2009",
058        booktitle = "International Conference on Computer Vision Theory and Application VISSAPP'09)",
059        pages = { "331", "340" },
060        publisher = "INSTICC Press"
061)
062public class FloatNearestNeighboursKDTree extends FloatNearestNeighbours {
063    /**
064         * {@link NearestNeighboursFactory} for producing
065         * {@link FloatNearestNeighboursKDTree}s.
066         * 
067         * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
068         */
069    public static final class Factory implements NearestNeighboursFactory<FloatNearestNeighboursKDTree, float[]> {
070        int ntrees;
071        int nchecks;
072        
073        /**
074         * Construct the factory the default number of trees and checks.
075         */
076        public Factory() {
077            this.ntrees = FloatNearestNeighboursKDTree.DEFAULT_NTREES;
078            this.nchecks = FloatNearestNeighboursKDTree.DEFAULT_NCHECKS;
079        }
080        
081        /**
082         * Construct the factory the given number of trees and checks.
083         * 
084                 * @param ntrees 
085                 *          the number of trees 
086         * @param nchecks 
087         *          the number of checks during search
088         */
089        public Factory(int ntrees, int nchecks) {
090            this.ntrees = ntrees;
091            this.nchecks = nchecks;
092        }
093        
094        @Override
095        public FloatNearestNeighboursKDTree create(float[][] data) {
096            return new FloatNearestNeighboursKDTree(data, ntrees, nchecks);
097        }
098    }
099    
100    /**
101         * The default number of checks performed during search when in exact mode.
102         */
103        public static final int DEFAULT_NCHECKS = 768;
104
105        /**
106         * The default number of kdtrees when not in exact mode.
107         */
108        public static final int DEFAULT_NTREES = 8;
109    
110        /** The ensemble of KDTrees */
111        public final FloatKDTreeEnsemble kdt;
112        
113        /** The number of checks */
114    public final int nchecks;
115        
116        /** 
117         * Construct the FloatNearestNeighboursKDTree with the given options.
118         * 
119         * @param pnts the data
120         * @param ntrees the number of trees 
121         * @param nchecks the number of checks during search
122         */
123    public FloatNearestNeighboursKDTree(final float [][] pnts, int ntrees, int nchecks) {
124        kdt = new FloatKDTreeEnsemble(pnts, ntrees);
125        this.nchecks = nchecks;
126    }
127    
128        @Override
129        public int numDimensions() {
130                return kdt.pnts[0].length;
131        }
132
133        @Override
134        public int size() {
135                return kdt.pnts.length;
136        }
137
138        @Override
139        public void searchKNN(float[][] qus, int K, int[][] argmins, float[][] mins) {
140                // Fix for when the user asks for too many points.
141        K = Math.min(K, kdt.pnts.length);
142     
143        IntFloatPair[] nns = new IntFloatPair[K];
144        final int N = qus.length;
145        
146        for (int n=0; n < N; ++n) {
147            kdt.search(qus[n], K, nns, nchecks);
148            for (int k=0; k < K; ++k) {
149                argmins[n][k] = nns[k].first;
150                mins[n][k] = nns[k].second;
151            }
152        }
153        }
154
155        @Override
156        public void searchNN(float[][] qus, int[] argmins, float[] mins) {
157                final int N = qus.length;
158                IntFloatPair [] nn = new IntFloatPair[1];
159                
160                for (int n=0; n < N; ++n) {
161            kdt.search(qus[n], 1, nn, nchecks);
162            
163            argmins[n] = nn[0].first;
164            mins[n] = nn[0].second;
165        }
166        }
167        
168        @Override
169        public void searchKNN(List<float[]> qus, int K, int[][] argmins, float[][] mins) {
170                // Fix for when the user asks for too many points.
171        K = Math.min(K, kdt.pnts.length);
172     
173        IntFloatPair[] nns = new IntFloatPair[K];
174        final int N = qus.size();
175        
176        for (int n=0; n < N; ++n) {
177            kdt.search(qus.get(n), K, nns, nchecks);
178            for (int k=0; k < K; ++k) {
179                argmins[n][k] = nns[k].first;
180                mins[n][k] = nns[k].second;
181            }
182        }
183        }
184
185        @Override
186        public void searchNN(List<float[]> qus, int[] argmins, float[] mins) {
187                final int N = qus.size();
188                IntFloatPair [] nn = new IntFloatPair[1];
189                
190                for (int n=0; n < N; ++n) {
191            kdt.search(qus.get(n), 1, nn, nchecks);
192            
193            argmins[n] = nn[0].first;
194            mins[n] = nn[0].second;
195        }
196        }
197        
198        @Override
199        public List<IntFloatPair> searchKNN(float[] query, int K) {
200                // Fix for when the user asks for too many points.
201                K = Math.min(K, kdt.pnts.length);
202
203                final IntFloatPair[] nns = new IntFloatPair[K];
204
205                kdt.search(query, K, nns, nchecks);
206
207                return Arrays.asList(nns);
208        }
209
210        @Override
211        public IntFloatPair searchNN(float[] query) {
212                final IntFloatPair[] nn = new IntFloatPair[1];
213
214                kdt.search(query, 1, nn, nchecks);
215                
216                return nn[0];
217        }
218}