001/*
002        AUTOMATICALLY GENERATED BY jTemp FROM
003        /Users/jsh2/Work/openimaj/target/checkout/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.TLongHashSet;
037
038import org.openimaj.math.util.distance.HammingUtils;
039
040/**
041 * Comparison/distance methods for LongFV objects.
042 * 
043 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
044 */
045public enum LongFVComparison implements LongFVComparator {
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 long[] h1, final long[] 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 long[] h1, final long[] 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         * s(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 long[] h1, final long[] 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                        if (d==0) return 0;
124
125                        return d / Math.sqrt(SH1S * SH2S);
126                }
127        },
128        /**
129         * Chi-squared distance
130         * d(H1,H2) = 0.5 * sumI[(H1(I)-H2(I))^2 / (H1(I)+H2(I))]
131         */
132        CHI_SQUARE(true) {
133                @Override
134                public double compare(final long[] h1, final long[] h2) {
135                        if (h1.length != h2.length)
136                            throw new IllegalArgumentException("Vectors have differing lengths");
137
138                        double d = 0;
139
140                        for (int i=0; i<h1.length; i++) {
141                            double a = h1[i] - h2[i];
142                            double b = h1[i] + h2[i];
143                            
144                            if (Math.abs(b) > 0) d += a*a/b;
145                        }
146
147                        return d / 2;
148                }
149        },
150        /**
151         * Histogram intersection
152         * s(H1,H2) = sumI( min(H1(I), H2(I)) )
153         */
154        INTERSECTION(false) {
155                @Override
156                public double compare(final long[] h1, final long[] h2) {
157                        if (h1.length != h2.length)
158                            throw new IllegalArgumentException("Vectors have differing lengths");
159
160                        double d = 0;
161
162                        for (int i=0; i<h1.length; i++) {
163                                d += Math.min(h1[i], h2[i]);
164                        }
165
166                        return d;
167                }
168        },
169        /**
170         * Bhattacharyya distance
171         * d(H1,H2) = sqrt( 1 - (1 / sqrt(sumI(H1(I)) * sumI(H2(I))) ) * sumI( sqrt(H1(I) * H2(I)) ) )
172         */
173        BHATTACHARYYA(true) {
174                @Override
175                public double compare(final long[] h1, final long[] h2) {
176                        if (h1.length != h2.length)
177                            throw new IllegalArgumentException("Vectors have differing lengths");
178
179                        final int N = h1.length;
180                        double SH1 = 0;
181                        double SH2 = 0;
182                        double d = 0;
183                        for (int i=0; i<N; i++) {
184                                SH1 += h1[i];
185                                SH2 += h2[i];
186                                d += Math.sqrt(h1[i] * h2[i]);
187                        }
188
189                        double den = SH1 * SH2;
190                        if (den == 0) return 1;
191
192                        d /= Math.sqrt(den);
193
194                        return Math.sqrt(1.0 - d);
195                }
196        },
197        /**
198         * Hamming Distance
199         * d(H1,H2) = sumI(H1(I) == H2(I) ? 1 : 0)
200         */
201        HAMMING(true) {
202                @Override
203                public double compare(final long[] h1, final long[] h2) {
204                        if (h1.length != h2.length)
205                            throw new IllegalArgumentException("Vectors have differing lengths");
206
207                        int d = 0;
208
209                        for (int i=0; i<h1.length; i++)
210                                if (h1[i] != h2[i]) d++;
211
212                        return d;
213                }               
214        },
215        /**
216         * Hamming Distance for packed bit strings
217         * d(H1,H2) = sumI(H1(I) == H2(I) ? 1 : 0)
218         */
219        PACKED_HAMMING(true) {
220                @Override
221                public double compare(final long[] h1, final long[] h2) {
222                        if (h1.length != h2.length)
223                            throw new IllegalArgumentException("Vectors have differing lengths");
224
225                        int d = 0;
226
227                        for (int i=0; i<h1.length; i++) {
228                                d += HammingUtils.packedHamming(h1[i], h2[i]);
229                        }
230
231                        return d;
232                }       
233        },
234        /**
235         * City-block (L1) distance
236         * d(H1,H2) = sumI( abs(H1(I)-H2(I)) )
237         */
238        CITY_BLOCK(true) {
239                @Override
240                public double compare(final long[] h1, final long[] h2) {
241                        if (h1.length != h2.length)
242                            throw new IllegalArgumentException("Vectors have differing lengths");
243
244                        double d = 0;
245
246                        for (int i=0; i<h1.length; i++) {
247                                d += Math.abs(h1[i] - h2[i]);
248                        }
249
250                        return d;
251                }
252        },
253        /**
254         * Cosine similarity (sim of 1 means identical)
255         * s(H1,H2)=sumI(H1(I) * H2(I))) / (sumI(H1(I)^2) sumI(H2(I)^2))
256         */
257        COSINE_SIM(false) {
258                @Override
259                public double compare(final long[] h1, final long[] h2) {
260                        if (h1.length != h2.length)
261                            throw new IllegalArgumentException("Vectors have differing lengths");
262
263                        double h12 = 0;
264                        double h11 = 0;
265                        double h22 = 0;
266                        
267                        for (int i=0; i<h1.length; i++) {
268                                h12 += h1[i] * h2[i];
269                                h11 += h1[i] * h1[i];
270                                h22 += h2[i] * h2[i];
271                        }
272
273                        return h12 / (Math.sqrt(h11) * Math.sqrt(h22));
274                }
275        },
276        /**
277         * Cosine distance (-COSINE_SIM)
278         */
279        COSINE_DIST(true) {
280                @Override
281                public double compare(final long[] h1, final long[] h2) {
282                        return -1 * COSINE_SIM.compare(h1, h2);
283                }
284        },
285        /**
286         * The arccosine of the cosine similarity
287         */
288        ARCCOS(true) {
289                @Override
290                public double compare(final long[] h1, final long[] h2) {
291                        return Math.acos( COSINE_SIM.compare(h1, h2) );
292                }
293        },
294        /**
295         * The symmetric Kullback-Leibler divergence. Vectors must only contain
296         * positive values; internally they will be converted to double arrays 
297         * and normalised to sum to unit length.
298         */
299        SYMMETRIC_KL_DIVERGENCE(true) {
300                @Override
301                public double compare(final long[] h1, final long[] h2) {
302                        if (h1.length != h2.length)
303                                throw new IllegalArgumentException("Vectors have differing lengths");
304                        
305                        double sum1 = 0;
306                        double sum2 = 0;
307                        for (int i=0; i<h1.length; i++) {
308                                sum1 += h1[i];
309                                sum2 += h2[i];
310                        }
311                        
312                        double d = 0;
313                        for (int i=0; i<h1.length; i++) {
314                                double h1n = h1[i] / sum1;
315                                double h2n = h2[i] / sum2;
316                                
317                                double q1 = h1n / h2n;
318                                double q2 = h2n / h1n;
319                                
320                                if (h1n != 0) d += (h1n * Math.log(q1) / Math.log(2)); 
321                                if (h2n != 0) d += (h2n * Math.log(q2) / Math.log(2));
322                        }
323
324                        return d / 2.0;
325                }
326        },
327        /**
328         * Jaccard distance. Converts each vector to a set
329         * for comparison.
330         */
331        JACCARD_DISTANCE(true) {
332                @Override
333                public double compare(final long[] h1, final long[] h2) {
334                        TLongHashSet union = new TLongHashSet(h1);
335                        union.addAll(h2);
336
337                        TLongHashSet intersection = new TLongHashSet(h1);
338                        intersection.retainAll(h2.clone()); //retainAll sorts the input, so we need to make a copy
339
340                        return 1.0 - (((double)intersection.size()) / (double)union.size());
341                }
342        },
343        /**
344         * Inner product
345         * s(H1,H2)=sumI(H1(I) * H2(I))
346         */
347        INNER_PRODUCT(false) {
348                @Override
349                public double compare(final long[] h1, final long[] h2) {
350                        if (h1.length != h2.length)
351                            throw new IllegalArgumentException("Vectors have differing lengths");
352
353                        double h12 = 0;
354                        
355                        for (int i=0; i<h1.length; i++) {
356                                h12 += h1[i] * h2[i];
357                        }
358
359                        return h12;
360                }
361        }
362        ;
363
364        private boolean isDistance; 
365        LongFVComparison(boolean isDistance) {
366                this.isDistance = isDistance;
367        }
368
369        @Override
370        public boolean isDistance() {
371                return isDistance;
372        }
373
374        @Override
375        public double compare(LongFV h1, LongFV h2) {
376                return compare(h1.values, h2.values);
377        }
378
379        /**
380         * Compare two feature vectors in the form of native arrays, 
381         * returning a score or distance.
382         * 
383         * @param h1 the first feature array
384         * @param h2 the second feature array
385         * @return a score or distance
386         */     
387        @Override
388        public abstract double compare(long[] h1, long[] h2);
389}