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.demos; 031 032import gnu.trove.map.hash.TIntObjectHashMap; 033import gnu.trove.map.hash.TObjectIntHashMap; 034import gnu.trove.procedure.TObjectIntProcedure; 035 036import java.io.IOException; 037import java.net.MalformedURLException; 038import java.net.URL; 039import java.util.ArrayList; 040import java.util.Collections; 041import java.util.Comparator; 042import java.util.HashSet; 043import java.util.List; 044import java.util.Set; 045 046import org.openimaj.citation.annotation.Reference; 047import org.openimaj.citation.annotation.ReferenceType; 048import org.openimaj.feature.local.filter.ByteEntropyFilter; 049import org.openimaj.image.FImage; 050import org.openimaj.image.ImageUtilities; 051import org.openimaj.image.MBFImage; 052import org.openimaj.image.colour.Transforms; 053import org.openimaj.image.feature.local.engine.DoGSIFTEngine; 054import org.openimaj.image.feature.local.keypoints.Keypoint; 055import org.openimaj.image.processing.resize.ResizeProcessor; 056import org.openimaj.lsh.functions.DoubleGaussianFactory; 057import org.openimaj.lsh.sketch.IntLSHSketcher; 058import org.openimaj.util.filter.FilterUtils; 059import org.openimaj.util.hash.HashFunction; 060import org.openimaj.util.hash.HashFunctionFactory; 061import org.openimaj.util.hash.modifier.LSBModifier; 062import org.openimaj.util.pair.ObjectIntPair; 063 064import cern.jet.random.engine.MersenneTwister; 065 066/** 067 * <p> 068 * An in-memory image duplicate database. Stores hashes of features as the basis 069 * of determining duplicates. 070 * </p> 071 * <p> 072 * This is a basic in-memory implementation of the approach described by Dong, 073 * Wang and Li for high-confidence duplicate detection. It does not currently 074 * implement the query expansion phase based on a graph cut of the duplicity 075 * graph, but instead relies directly on a simple thresholded count of 076 * collisions. 077 * </p> 078 * 079 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 080 * 081 * @param <T> 082 * type of metadata being stored 083 * 084 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 085 */ 086@Reference( 087 author = { "Wei Dong", "Zhe Wang", "Kai Li" }, 088 title = "High-Confidence Near-Duplicate Image Detection", 089 type = ReferenceType.Inproceedings, 090 year = "2012", 091 booktitle = "ACM International Conference on Multimedia Retrieval", 092 customData = { "location", "Hong Kong, China" }) 093public class BasicDuplicateImageDatabase<T> { 094 private final int ndims = 128; 095 private final double w = 6.0; 096 private final int nbits = 128; 097 private final float LOG_BASE = 0.001f; 098 private final int maxImageSize = 150; 099 private final int seed = 0; 100 private int minScore = 10; 101 102 private DoGSIFTEngine engine; 103 final ByteEntropyFilter filter; 104 private IntLSHSketcher<double[]> sketcher; 105 protected List<TIntObjectHashMap<Set<T>>> database; 106 107 public BasicDuplicateImageDatabase() { 108 engine = new DoGSIFTEngine(); 109 engine.getOptions().setDoubleInitialImage(false); 110 111 filter = new ByteEntropyFilter(); 112 113 final MersenneTwister rng = new MersenneTwister(seed); 114 final DoubleGaussianFactory gauss = new DoubleGaussianFactory(this.ndims, rng, w); 115 final HashFunctionFactory<double[]> factory = new HashFunctionFactory<double[]>() { 116 @Override 117 public HashFunction<double[]> create() { 118 return new LSBModifier<double[]>(gauss.create()); 119 } 120 }; 121 122 sketcher = new IntLSHSketcher<double[]>(factory, nbits); 123 database = new ArrayList<TIntObjectHashMap<Set<T>>>(sketcher.arrayLength()); 124 125 for (int i = 0; i < sketcher.arrayLength(); i++) 126 database.add(new TIntObjectHashMap<Set<T>>()); 127 } 128 129 /** 130 * Perform log-scaling element-wise on a feature 131 * 132 * @param v 133 * the feature 134 * @return the scaled feature 135 */ 136 private double[] logScale(double[] v) { 137 final double[] dfv = new double[v.length]; 138 final double s = -Math.log(LOG_BASE); 139 140 for (int i = 0; i < v.length; i++) { 141 double d = (v[i] + 128.0) / 256.0; 142 143 if (d < LOG_BASE) 144 d = LOG_BASE; 145 d = (Math.log(d) + s) / s; 146 if (d > 1.0) 147 d = 1.0; 148 149 dfv[i] = d; 150 } 151 return dfv; 152 } 153 154 /** 155 * Extract hashed features from an image 156 * 157 * @param image 158 * the image to index 159 * @return the features 160 */ 161 public int[][] extractFeatures(FImage image) { 162 image = ResizeProcessor.resizeMax(image, maxImageSize); 163 164 final List<Keypoint> features = engine.findFeatures(image); 165 final List<Keypoint> filtered = FilterUtils.filter(features, filter); 166 167 final int[][] sketches = new int[filtered.size()][]; 168 for (int i = 0; i < filtered.size(); i++) { 169 final Keypoint k = filtered.get(i); 170 final double[] fv = logScale(k.getFeatureVector().asDoubleVector()); 171 sketches[i] = sketcher.createSketch(fv); 172 } 173 174 return sketches; 175 } 176 177 /** 178 * Extract hashed features from an image 179 * 180 * @param image 181 * the image to index 182 * @return the features 183 */ 184 public int[][] extractFeatures(MBFImage image) { 185 return extractFeatures(Transforms.calculateIntensityNTSC(image)); 186 } 187 188 /** 189 * Index a new image based on its features 190 * 191 * @param features 192 * the image to index 193 * @param metadata 194 * the metadata for the image 195 */ 196 public synchronized void indexImage(int[][] features, T metadata) { 197 for (final int[] sketch : features) { 198 for (int i = 0; i < sketch.length; i++) { 199 final int sk = sketch[i]; 200 Set<T> s = database.get(i).get(sk); 201 if (s == null) 202 database.get(i).put(sk, s = new HashSet<T>()); 203 204 s.add(metadata); 205 } 206 } 207 } 208 209 /** 210 * Search for a given image (represented by its features) in the database 211 * 212 * @param features 213 * the features 214 * @return the list of matching images and their scores (bigger == more 215 * chance of match) 216 */ 217 public List<ObjectIntPair<T>> search(int[][] features) { 218 final TObjectIntHashMap<T> counter = new TObjectIntHashMap<>(); 219 220 for (final int[] sketch : features) { 221 for (int i = 0; i < sketch.length; i++) { 222 final int sk = sketch[i]; 223 final Set<T> s = database.get(i).get(sk); 224 if (s != null) { 225 for (final T key : s) { 226 counter.adjustOrPutValue(key, 1, 1); 227 } 228 } 229 } 230 } 231 232 final List<ObjectIntPair<T>> result = new ArrayList<>(); 233 234 counter.forEachEntry(new TObjectIntProcedure<T>() { 235 @Override 236 public boolean execute(T a, int b) { 237 if (b > minScore) 238 result.add(ObjectIntPair.pair(a, b)); 239 return false; 240 } 241 }); 242 243 Collections.sort(result, new Comparator<ObjectIntPair<T>>() { 244 @Override 245 public int compare(ObjectIntPair<T> o1, ObjectIntPair<T> o2) { 246 return Integer.compare(o2.second, o1.second); 247 } 248 }); 249 250 return result; 251 } 252 253 public static void main(String[] args) throws MalformedURLException, IOException { 254 // Construct DB 255 final BasicDuplicateImageDatabase<String> database = new BasicDuplicateImageDatabase<>(); 256 257 // add some images 258 final int[][] f1 = database.extractFeatures(ImageUtilities.readF(new URL( 259 "http://comp3204.ecs.soton.ac.uk/cw/dog.jpg"))); 260 database.indexImage(f1, "dog"); 261 262 final int[][] f2 = database.extractFeatures(ImageUtilities.readF(new URL( 263 "http://comp3204.ecs.soton.ac.uk/cw/cat.jpg"))); 264 database.indexImage(f2, "cat"); 265 266 // test to see that the images can be found 267 System.out.println(database.search(f1).get(0).first); // should be dog 268 System.out.println(database.search(f2).get(0).first); // should be cat 269 270 // test with an unindexed image 271 final int[][] f3 = database.extractFeatures(ImageUtilities.readF(new URL( 272 "http://comp3204.ecs.soton.ac.uk/cw/hybrid_image.jpg"))); 273 System.out.println(database.search(f3)); // should be an empty list 274 } 275}