001/*
002        AUTOMATICALLY GENERATED BY jTemp FROM
003        /Users/jsh2/Work/openimaj/target/checkout/machine-learning/nearest-neighbour/src/main/jtemp/org/openimaj/knn/pq/#T#SDCNearestNeighbours.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 */
034 
035 package org.openimaj.knn.pq;
036
037import org.openimaj.citation.annotation.Reference;
038import org.openimaj.citation.annotation.ReferenceType;
039import org.openimaj.feature.ByteFVComparison;
040import org.openimaj.util.pair.IntFloatPair;
041import org.openimaj.util.queue.BoundedPriorityQueue;
042/**
043 * Nearest-neighbours using Symmetric Distance Computation (SDC) on Product
044 * Quantised vectors. In SDC, both query and the database points are quantised.
045 * Distances are calculated by look-up from precomputed tables of the distance
046 * between all centroids for each subvector.
047 * <p>
048 * <strong>SDC has the same computational cost as ADC, but a higher error in the
049 * computed distance, so its use is not recommended. This implementation is
050 * provided for completeness only.</strong>
051 * 
052 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
053 */
054@Reference(
055                type = ReferenceType.Article,
056                author = { "Jegou, Herve", "Douze, Matthijs", "Schmid, Cordelia" },
057                title = "Product Quantization for Nearest Neighbor Search",
058                year = "2011",
059                journal = "IEEE Trans. Pattern Anal. Mach. Intell.",
060                pages = { "117", "", "128" },
061                url = "http://dx.doi.org/10.1109/TPAMI.2010.57",
062                month = "January",
063                number = "1",
064                publisher = "IEEE Computer Society",
065                volume = "33",
066                customData = {
067                                "issn", "0162-8828",
068                                "numpages", "12",
069                                "doi", "10.1109/TPAMI.2010.57",
070                                "acmid", "1916695",
071                                "address", "Washington, DC, USA",
072                                "keywords", "High-dimensional indexing, High-dimensional indexing, image indexing, very large databases, approximate search., approximate search., image indexing, very large databases"
073                })
074public class ByteSDCNearestNeighbours extends ByteADCNearestNeighbours {
075        byte[][][] distances;
076
077        /**
078         * Construct the SDC with the given quantiser, centroids (corresponding to
079         * the quantiser's internal assigners), and data.
080         * 
081         * @param pq
082         *            the Product Quantiser
083         * @param pqCentroids
084         *            the centroids corresponding to the the Product Quantiser's
085         *            internal assigners.
086         * @param dataPoints
087         *            the data to index
088         */
089        public ByteSDCNearestNeighbours(ByteProductQuantiser pq, byte[][][] pqCentroids, byte[][] dataPoints) {
090                super(pq, dataPoints);
091
092                this.distances = new byte[pq.assigners.length][][];
093
094                for (int i = 0; i < pq.assigners.length; i++) {
095                        final byte[][] centroids = pqCentroids[i];
096
097                        distances[i] = new byte[centroids.length][centroids.length];
098
099                        for (int j = 0; j < centroids.length; j++) {
100                                for (int k = j; k < centroids.length; k++) {
101                                        distances[i][j][k] = (byte) ByteFVComparison.SUM_SQUARE.compare(centroids[j], centroids[k]);
102                                        distances[i][k][j] = distances[i][j][k];
103                                }
104                        }
105                }
106        }
107
108        @Override
109        protected void computeDistances(byte[] fullQuery, BoundedPriorityQueue<IntFloatPair> queue, IntFloatPair workingPair)
110        {
111                final byte[] query = pq.quantise(fullQuery);
112
113                for (int i = 0; i < data.length; i++) {
114                        workingPair.first = i;
115                        workingPair.second = 0;
116
117                        for (int j = 0; j < query.length; j++) {
118                                workingPair.second += distances[j][query[j] + 128][data[i][j] + 128];
119                        }
120
121                        workingPair = queue.offerItem(workingPair);
122                }
123        }
124}