001/*******************************************************************************
002 * This software is provided as a supplement to the authors' textbooks on digital
003 *  image processing published by Springer-Verlag in various languages and editions.
004 * Permission to use and distribute this software is granted under the BSD 2-Clause 
005 * "Simplified" License (see http://opensource.org/licenses/BSD-2-Clause). 
006 * Copyright (c) 2006-2016 Wilhelm Burger, Mark J. Burge. All rights reserved. 
007 * Visit http://imagingbook.com for additional details.
008 *******************************************************************************/
009
010package imagingbook.pub.sift;
011
012import imagingbook.lib.math.VectorNorm;
013import imagingbook.lib.math.VectorNorm.NormType;
014
015import java.util.ArrayList;
016import java.util.Collections;
017import java.util.List;
018
019public class SiftMatcher {
020        
021        public static class Parameters {
022                /** Specify type of distance norm */
023                public NormType norm = NormType.L2;
024                /** Max. ratio between best and second-best match */
025                public double rho_max = 0.8;
026                /** Set true to sort matches */
027                public boolean sort = true;
028        }
029        
030        private final Parameters params;
031        private final SiftDescriptor[] fA;
032        private final VectorNorm am;
033
034        // constructor - using default parameters
035        public SiftMatcher(List<SiftDescriptor> sfA) {
036                this(sfA, new Parameters());
037        }
038        
039        // constructor - using specific parameters
040        public SiftMatcher(List<SiftDescriptor> sfA, Parameters params) {
041                this.fA = sfA.toArray(new SiftDescriptor[0]);
042                this.params = params;
043                am = params.norm.create();
044        }
045        
046        public List<SiftMatch> matchDescriptors(List<SiftDescriptor> sfB) {
047                SiftDescriptor[] fB = sfB.toArray(new SiftDescriptor[0]);
048                List<SiftMatch> matches = new ArrayList<SiftMatch>(fA.length);
049                                
050                for (int i = 0; i < fA.length; i++) {
051                        SiftDescriptor si = fA[i];
052                        int i1 = -1;
053                        int i2 = -1;
054                        double d1 = Double.MAX_VALUE;
055                        double d2 = Double.MAX_VALUE;
056                        
057                        for (int j = 0; j < fB.length; j++) {
058                                double d = dist(si, fB[j]);
059                                if (d < d1) {   // new absolute minimum distance
060                                        i2 = i1;        // old best becomes second-best
061                                        d2 = d1;
062                                        i1 = j;
063                                        d1 = d;
064                                }
065                                else // not a new absolute min., but possible second-best
066                                        if (d < d2) { // new second-best
067                                                i2 = j;
068                                                d2 = d;
069                                        }
070                        }
071                        if (i2 >= 0 && d2 > 0.001 && d1/d2 < params.rho_max) {
072                                SiftDescriptor s1 = fB[i1];
073                                SiftMatch m = new SiftMatch(si, s1, d1);
074                                matches.add(m);
075                        }
076                }
077                if (params.sort) Collections.sort(matches);  // sort matches to ascending distance d1
078                return matches;
079        }
080        
081        double dist(SiftDescriptor d1, SiftDescriptor d2) {
082                //final ArrayMatcher matcher = params.norm.matcher;
083                return am.distance(d1.getFeatures(), d2.getFeatures());
084        }
085
086}