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.feature.local.filter; 031 032import org.openimaj.citation.annotation.Reference; 033import org.openimaj.citation.annotation.ReferenceType; 034import org.openimaj.feature.ByteFV; 035import org.openimaj.feature.local.LocalFeature; 036import org.openimaj.image.feature.local.engine.DoGSIFTEngine; 037import org.openimaj.util.function.Predicate; 038 039/** 040 * Filter {@link LocalFeature}s typed on {@link ByteFV} by rejecting those that 041 * have a low feature entropy. Such features are those that tend to have little 042 * variation; for example, in the case of SIFT features, the removed features 043 * are typically the ones that mismatch easily. 044 * <p> 045 * This filter is an implementation of the approach described by Dong, Wang and 046 * Li; the default threshold is taken from the paper, and will work with 047 * standard SIFT features, such as those produced by a {@link DoGSIFTEngine}. 048 * 049 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 050 */ 051@Reference( 052 author = { "Wei Dong", "Zhe Wang", "Kai Li" }, 053 title = "High-Confidence Near-Duplicate Image Detection", 054 type = ReferenceType.Inproceedings, 055 year = "2012", 056 booktitle = "ACM International Conference on Multimedia Retrieval", 057 customData = { "location", "Hong Kong, China" }) 058public class ByteEntropyFilter implements Predicate<LocalFeature<?, ByteFV>> { 059 double threshold = 4.4; 060 061 /** 062 * Construct with the default threshold of 4.4 as suggested in the original 063 * paper. 064 */ 065 public ByteEntropyFilter() { 066 } 067 068 /** 069 * Construct with a custom threshold. 070 * 071 * @param threshold 072 * The threshold. 073 */ 074 public ByteEntropyFilter(double threshold) { 075 this.threshold = threshold; 076 } 077 078 @Override 079 public boolean test(LocalFeature<?, ByteFV> object) { 080 return entropy(object.getFeatureVector().values) >= threshold; 081 } 082 083 /** 084 * Compute the entropy of the given byte vector. 085 * 086 * @param vector 087 * the vector. 088 * @return the entropy. 089 */ 090 public static double entropy(byte[] vector) { 091 final int[] counts = new int[256]; 092 for (int i = 0; i < vector.length; i++) { 093 counts[vector[i] + 128]++; 094 } 095 096 final double log2 = Math.log(2); 097 double entropy = 0; 098 for (int b = 0; b < counts.length; b++) { 099 final double p = (double) counts[b] / (double) vector.length; 100 101 entropy -= (p == 0 ? 0 : p * Math.log(p) / log2); 102 } 103 return entropy; 104 } 105}