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-2023 Wilhelm Burger, Mark J. Burge. All rights reserved. 007 * Visit https://imagingbook.com for additional details. 008 ******************************************************************************/ 009 010package imagingbook.common.sift; 011 012import imagingbook.common.math.VectorNorm; 013import imagingbook.common.math.VectorNorm.NormType; 014 015import java.util.ArrayList; 016import java.util.Collection; 017import java.util.Collections; 018import java.util.List; 019 020/** 021 * <p> 022 * Instances of this class perform matching between SIFT features. See Secs. 25.5 of [1] for more details. 023 * </p> 024 * <p> 025 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing – An Algorithmic Introduction</em>, 3rd ed, Springer 026 * (2022). 027 * </p> 028 * 029 * @author WB 030 * @version 2022/11/20 removed inner Parameters class, changed constructor 031 */ 032public class SiftMatcher { 033 034 public static final NormType DefaultNormType = NormType.L2; 035 public static final double DefaultRMax = 0.8; 036 037 private final VectorNorm norm; 038 private final double rMax; 039 040 /** 041 * Constructor using specific parameters. 042 * 043 * @param normType the distance norm for comparing feature vectors 044 * @param rMax the max. distance ratio between best and second-best match 045 */ 046 public SiftMatcher(NormType normType, double rMax) { 047 this.norm = normType.getInstance(); 048 this.rMax = rMax; 049 } 050 051 /** 052 * Constructor using default parameters. 053 * @see #DefaultNormType 054 * @see #DefaultRMax 055 */ 056 public SiftMatcher() { 057 this(DefaultNormType, DefaultRMax); 058 } 059 060 /** 061 * Finds matches between two sets of SIFT descriptors. For each descriptor in the first set, the best and 062 * second-best fits are searched for in the second set. A valid match instance is created if the distance to the 063 * best-matching descriptor is significantly smaller than the distance to the second-best matching descriptor. The 064 * resulting list of matches is sorted by increasing match distance. 065 * 066 * @param setA the first set of SIFT descriptors 067 * @param setB the second set of SIFT descriptors 068 * @return a (possibly empty) list of {@link SiftMatch} instances 069 */ 070 public List<SiftMatch> match(Collection<SiftDescriptor> setA, Collection<SiftDescriptor> setB) { 071 List<SiftMatch> matches = new ArrayList<SiftMatch>(setA.size()); 072 073 for (SiftDescriptor si : setA) { 074 SiftDescriptor s1 = null; // best-matching feature 075 double d1 = Double.POSITIVE_INFINITY; // best match distance 076 double d2 = Double.POSITIVE_INFINITY; // second-best match distance 077 078 for (SiftDescriptor sj : setB) { 079 double d = si.getDistance(sj, norm); // dist(si, sj); 080 if (d < d1) { // new best match 081 d2 = d1; // demote current best match to second-best (keep distance only) 082 s1 = sj; // new best matching feature 083 d1 = d; // new best match distance 084 } 085 else // not a new absolute min., but possible second-best 086 if (d < d2) { // new second-best distance 087 d2 = d; 088 } 089 } 090 if (Double.isFinite(d2) && d2 > 0.001 && d1/d2 < this.rMax) { 091 SiftMatch m = new SiftMatch(si, s1, d1); 092 matches.add(m); 093 } 094 } 095 096 Collections.sort(matches); // sort matches by ascending descriptor distance 097 return matches; 098 } 099 100}