001/**
002 * Copyright (c) 2011, The University of Southampton and the individual contributors.
003 * All rights reserved.
004 *
005 * Redistribution and use in source and binary forms, with or without modification,
006 * are permitted provided that the following conditions are met:
007 *
008 *   *  Redistributions of source code must retain the above copyright notice,
009 *      this list of conditions and the following disclaimer.
010 *
011 *   *  Redistributions in binary form must reproduce the above copyright notice,
012 *      this list of conditions and the following disclaimer in the documentation
013 *      and/or other materials provided with the distribution.
014 *
015 *   *  Neither the name of the University of Southampton nor the names of its
016 *      contributors may be used to endorse or promote products derived from this
017 *      software without specific prior written permission.
018 *
019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029 */
030package org.openimaj.feature.local.matcher;
031
032import java.util.ArrayList;
033import java.util.List;
034
035import org.openimaj.image.feature.local.keypoints.Keypoint;
036import org.openimaj.knn.approximate.ByteNearestNeighboursKDTree;
037import org.openimaj.util.pair.Pair;
038
039/**
040 * A {@link LocalFeatureMatcher} that only matches points that
041 * are self similar with other points. 
042 * 
043 * Target points that match have a distance less than a threshold
044 * to the query point. The number of points less than the threshold
045 * must be greater than the limit to be counted as matches. 
046 * 
047 * @author Sina Samangooei (ss@ecs.soton.ac.uk)
048 *
049 * @param <T> Type of {@link Keypoint} being matched
050 */
051public class MultipleMatchesMatcher<T extends Keypoint> implements LocalFeatureMatcher<T> {
052        private int count;
053        protected List <Pair<T>> matches;
054        private ByteNearestNeighboursKDTree modelKeypointsKNN;
055        private double thresh;
056        private List<T> modelKeypoints;
057        
058        /**
059         * Construct with the given minimum number of similar features
060         * and threshold for defining similarity. 
061         * @param count number of matches with a distance less than thresh to be counted.
062         * @param thresh the threshold.
063         */
064        public MultipleMatchesMatcher(int count, double thresh) {
065                this.count = count;
066                if(this.count < 2) this.count = 2;
067                this.thresh = thresh;
068                matches = new ArrayList<Pair<T>>();
069        }
070        
071        @Override
072        public void setModelFeatures(List<T> modelkeys) {
073                this.modelKeypoints = modelkeys;
074                byte [][] data = new byte[modelkeys.size()][];
075                for (int i=0; i<modelkeys.size(); i++)
076                        data[i] = modelkeys.get(i).ivec;
077                
078                modelKeypointsKNN = new ByteNearestNeighboursKDTree(data, 1, 100);
079        }
080
081        @Override
082        public boolean findMatches(List<T> keys1) {
083                byte [][] data = new byte[keys1.size()][];
084                for (int i=0; i<keys1.size(); i++)
085                        data[i] = keys1.get(i).ivec;
086                
087                int [][] argmins = new int[keys1.size()][this.count];
088                float [][] mins = new float[keys1.size()][this.count];
089                
090                modelKeypointsKNN.searchKNN(data, this.count, argmins, mins);
091                double threshProp = (1.0 + thresh) * (1.0 + thresh) ;
092                
093                for (int i=0; i<keys1.size(); i++) {
094                        // Get the first distance
095
096                        boolean matchesMultiple = true;
097                        if(mins[i].length > 0 && mins[i].length >= this.count) {
098                                double distsq1 = mins[i][0];
099                                
100                                for (int j = 1; j < this.count; j++) {
101                                        double distsq2 = mins[i][j];
102                                        
103                                        if (distsq2 > distsq1 * threshProp) {
104                                                // Then there is a mismatch within the first this.count, break
105                                                matchesMultiple = false;
106                                                break;
107                                    }
108                                }
109                        } else {
110                                matchesMultiple = false;
111                        }
112                        
113                        if(matchesMultiple) {
114                                // Add each of the pairs that match
115                                for (int j = 0; j < this.count; j++) {
116                                        matches.add(new Pair<T>(keys1.get(i), modelKeypoints.get(argmins[i][j])));
117                                }
118                        }
119                }
120                
121                return true;
122        }
123
124        @Override
125        public List<Pair<T>> getMatches() {
126                return this.matches;
127        }
128
129}