001/* 002 AUTOMATICALLY GENERATED BY jTemp FROM 003 /Users/jon/Work/openimaj/tags/openimaj-1.3.1/core/core-feature/src/main/jtemp/org/openimaj/feature/#T#FVComparison.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.feature; 035 036import gnu.trove.set.hash.TIntHashSet; 037 038import org.openimaj.math.util.distance.HammingUtils; 039 040/** 041 * Comparison/distance methods for IntFV objects. 042 * 043 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 044 */ 045public enum IntFVComparison implements IntFVComparator { 046 /** 047 * Euclidean distance 048 * d(H1,H2) = Math.sqrt( sumI( (H1(I)-H2(I))^2 ) ) 049 */ 050 EUCLIDEAN(true) { 051 @Override 052 public double compare(final int[] h1, final int[] h2) { 053 if (h1.length != h2.length) 054 throw new IllegalArgumentException("Vectors have differing lengths"); 055 056 double d = 0; 057 058 for (int i=0; i<h1.length; i++) { 059 double diff = (h1[i] - h2[i]); 060 d += (diff * diff); 061 } 062 063 return Math.sqrt(d); 064 } 065 }, 066 /** 067 * Sum-square distance 068 * d(H1,H2) = sumI( (H1(I)-H2(I))^2 ) 069 */ 070 SUM_SQUARE(true) { 071 @Override 072 public double compare(final int[] h1, final int[] h2) { 073 if (h1.length != h2.length) 074 throw new IllegalArgumentException("Vectors have differing lengths"); 075 076 double d = 0; 077 078 for (int i=0; i<h1.length; i++) { 079 double diff = (h1[i] - h2[i]); 080 d += (diff * diff); 081 } 082 083 return d; 084 } 085 }, 086 /** 087 * Correlation 088 * 089 * d(H1,H2) = sumI( H'1(I) * H'2(I) ) / sqrt( sumI[H'1(I)2]^2 * sumI[H'2(I)^2] ) 090 * where 091 * H'k(I) = Hk(I) - (1/N) * sumJ( Hk(J) ); N=number of FeatureVector bins 092 * 093 */ 094 CORRELATION(false) { 095 @Override 096 public double compare(final int[] h1, final int[] h2) { 097 if (h1.length != h2.length) 098 throw new IllegalArgumentException("Vectors have differing lengths"); 099 100 double N = h1.length; 101 double SH1=0, SH2=0; 102 103 for (int i=0; i<N; i++) { 104 SH1 += h1[i]; 105 SH2 += h2[i]; 106 } 107 SH1 /= N; 108 SH2 /= N; 109 110 double d = 0; 111 double SH1S = 0; 112 double SH2S = 0; 113 114 for (int i=0; i<N; i++) { 115 double h1prime = h1[i] - SH1; 116 double h2prime = h2[i] - SH2; 117 118 d += (h1prime * h2prime); 119 SH1S += (h1prime * h1prime); 120 SH2S += (h2prime * h2prime); 121 } 122 123 return d / Math.sqrt(SH1S * SH2S); 124 } 125 }, 126 /** 127 * Chi-squared distance 128 * d(H1,H2) = 0.5 * sumI[(H1(I)-H2(I))^2 / (H1(I)+H2(I))] 129 */ 130 CHI_SQUARE(true) { 131 @Override 132 public double compare(final int[] h1, final int[] h2) { 133 if (h1.length != h2.length) 134 throw new IllegalArgumentException("Vectors have differing lengths"); 135 136 double d = 0; 137 138 for (int i=0; i<h1.length; i++) { 139 double a = h1[i] - h2[i]; 140 double b = h1[i] + h2[i]; 141 142 if (Math.abs(b) > 0) d += a*a/b; 143 } 144 145 return d / 2; 146 } 147 }, 148 /** 149 * Histogram intersection 150 * d(H1,H2) = sumI( min(H1(I), H2(I)) ) 151 */ 152 INTERSECTION(false) { 153 @Override 154 public double compare(final int[] h1, final int[] h2) { 155 if (h1.length != h2.length) 156 throw new IllegalArgumentException("Vectors have differing lengths"); 157 158 double d = 0; 159 160 for (int i=0; i<h1.length; i++) { 161 d += Math.min(h1[i], h2[i]); 162 } 163 164 return d; 165 } 166 }, 167 /** 168 * Bhattacharyya distance 169 * d(H1,H2) = sqrt( 1 - (1 / sqrt(sumI(H1(I)) * sumI(H2(I))) ) * sumI( sqrt(H1(I) * H2(I)) ) ) 170 */ 171 BHATTACHARYYA(true) { 172 @Override 173 public double compare(final int[] h1, final int[] h2) { 174 if (h1.length != h2.length) 175 throw new IllegalArgumentException("Vectors have differing lengths"); 176 177 final int N = h1.length; 178 double SH1 = 0; 179 double SH2 = 0; 180 double d = 0; 181 for (int i=0; i<N; i++) { 182 SH1 += h1[i]; 183 SH2 += h2[i]; 184 d += Math.sqrt(h1[i] * h2[i]); 185 } 186 187 double den = SH1 * SH2; 188 if (den == 0) return 1; 189 190 d /= Math.sqrt(den); 191 192 return Math.sqrt(1.0 - d); 193 } 194 }, 195 /** 196 * Hamming Distance 197 * d(H1,H2) = sumI(H1(I) == H2(I) ? 1 : 0) 198 */ 199 HAMMING(true) { 200 @Override 201 public double compare(final int[] h1, final int[] h2) { 202 if (h1.length != h2.length) 203 throw new IllegalArgumentException("Vectors have differing lengths"); 204 205 int d = 0; 206 207 for (int i=0; i<h1.length; i++) 208 if (h1[i] != h2[i]) d++; 209 210 return d; 211 } 212 }, 213 /** 214 * Hamming Distance for packed bit strings 215 * d(H1,H2) = sumI(H1(I) == H2(I) ? 1 : 0) 216 */ 217 PACKED_HAMMING(true) { 218 @Override 219 public double compare(final int[] h1, final int[] h2) { 220 if (h1.length != h2.length) 221 throw new IllegalArgumentException("Vectors have differing lengths"); 222 223 int d = 0; 224 225 for (int i=0; i<h1.length; i++) { 226 d += HammingUtils.packedHamming(h1[i], h2[i]); 227 } 228 229 return d; 230 } 231 }, 232 /** 233 * City-block (L1) distance 234 * d(H1,H2) = sumI( abs(H1(I)-H2(I)) ) 235 */ 236 CITY_BLOCK(true) { 237 @Override 238 public double compare(final int[] h1, final int[] h2) { 239 if (h1.length != h2.length) 240 throw new IllegalArgumentException("Vectors have differing lengths"); 241 242 double d = 0; 243 244 for (int i=0; i<h1.length; i++) { 245 d += Math.abs(h1[i] - h2[i]); 246 } 247 248 return d; 249 } 250 }, 251 /** 252 * Cosine similarity (sim of 1 means identical) 253 * d(H1,H2)=sumI(H1(I) * H2(I))) / (sumI(H1(I)^2) sumI(H2(I)^2)) 254 */ 255 COSINE_SIM(false) { 256 @Override 257 public double compare(final int[] h1, final int[] h2) { 258 if (h1.length != h2.length) 259 throw new IllegalArgumentException("Vectors have differing lengths"); 260 261 double h12 = 0; 262 double h11 = 0; 263 double h22 = 0; 264 265 for (int i=0; i<h1.length; i++) { 266 h12 += h1[i] * h2[i]; 267 h11 += h1[i] * h1[i]; 268 h22 += h2[i] * h2[i]; 269 } 270 271 return h12 / (Math.sqrt(h11) * Math.sqrt(h22)); 272 } 273 }, 274 /** 275 * Cosine distance (-COSINE_SIM) 276 */ 277 COSINE_DIST(true) { 278 @Override 279 public double compare(final int[] h1, final int[] h2) { 280 return -1 * COSINE_SIM.compare(h1, h2); 281 } 282 }, 283 /** 284 * The arccosine of the cosine similarity 285 */ 286 ARCCOS(true) { 287 @Override 288 public double compare(final int[] h1, final int[] h2) { 289 return Math.acos( COSINE_SIM.compare(h1, h2) ); 290 } 291 }, 292 /** 293 * The symmetric Kullback-Leibler divergence. Vectors must only contain 294 * positive values; internally they will be converted to double arrays 295 * and normalised to sum to unit length. 296 */ 297 SYMMETRIC_KL_DIVERGENCE(true) { 298 @Override 299 public double compare(final int[] h1, final int[] h2) { 300 if (h1.length != h2.length) 301 throw new IllegalArgumentException("Vectors have differing lengths"); 302 303 double sum1 = 0; 304 double sum2 = 0; 305 for (int i=0; i<h1.length; i++) { 306 sum1 += h1[i]; 307 sum2 += h2[i]; 308 } 309 310 double d = 0; 311 for (int i=0; i<h1.length; i++) { 312 double h1n = h1[i] / sum1; 313 double h2n = h2[i] / sum2; 314 315 double q1 = h1n / h2n; 316 double q2 = h2n / h1n; 317 318 if (h1n != 0) d += (h1n * Math.log(q1) / Math.log(2)); 319 if (h2n != 0) d += (h2n * Math.log(q2) / Math.log(2)); 320 } 321 322 return d / 2.0; 323 } 324 }, 325 /** 326 * Jaccard distance. Converts each vector to a set 327 * for comparison. 328 */ 329 JACCARD_DISTANCE(true) { 330 @Override 331 public double compare(final int[] h1, final int[] h2) { 332 TIntHashSet union = new TIntHashSet(h1); 333 union.addAll(h2); 334 335 TIntHashSet intersection = new TIntHashSet(h1); 336 intersection.retainAll(h2); 337 338 return 1.0 - (((double)intersection.size()) / (double)union.size()); 339 } 340 } 341 ; 342 343 private boolean isDistance; 344 IntFVComparison(boolean isDistance) { 345 this.isDistance = isDistance; 346 } 347 348 @Override 349 public boolean isDistance() { 350 return isDistance; 351 } 352 353 @Override 354 public double compare(IntFV h1, IntFV h2) { 355 return compare(h1.values, h2.values); 356 } 357 358 /** 359 * Compare two feature vectors in the form of native arrays, 360 * returning a score or distance. 361 * 362 * @param h1 the first feature array 363 * @param h2 the second feature array 364 * @return a score or distance 365 */ 366 @Override 367 public abstract double compare(int[] h1, int[] h2); 368}