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 */ 030/** 031 * 032 */ 033package org.openimaj.video.processing.shotdetector; 034 035import org.openimaj.citation.annotation.Reference; 036import org.openimaj.citation.annotation.ReferenceType; 037import org.openimaj.feature.DoubleFVComparison; 038import org.openimaj.image.MBFImage; 039import org.openimaj.image.colour.RGBColour; 040import org.openimaj.image.pixel.statistics.HistogramModel; 041import org.openimaj.math.geometry.shape.Rectangle; 042import org.openimaj.util.array.ArrayUtils; 043import org.openimaj.video.Video; 044 045/** 046 * A shot detector implementing the Steiner et al. local histogram comparison. 047 * 048 * @author David Dupplaw (dpd@ecs.soton.ac.uk) 049 * @created 28 Jan 2013 050 * @version $Author$, $Revision$, $Date$ 051 */ 052@Reference( 053 type = ReferenceType.Inproceedings, 054 author = { "{S}teiner, {T}homas", "{V}erborgh, {R}uben", "{G}abarr{\'o} {V}all{\'e}s, {J}oaquim", "{T}roncy, {R}apha{\"e}l", "{H}ausenblas, {M}ichael", "{V}an de {W}alle, {R}ik", "{B}rousseau, {A}rnaud" }, 055 title = "{E}nabling on-the-fly video shot detection on {Y}ou{T}ube", 056 year = "2012", 057 booktitle = "{WWW} 2012, 21st {I}nternational {W}orld {W}ide {W}eb {C}onference {D}eveloper's {T}rack, {A}pril 16-20, 2012, {L}yon, {F}rance", 058 url = "http://www.eurecom.fr/publication/3676", 059 month = "04", 060 customData = { 061 "address", "{L}yon, {FRANCE}" 062 } 063 ) 064public class LocalHistogramVideoShotDetector 065 extends VideoShotDetector<MBFImage> 066{ 067 /** The histogram model used to estimate the histogram for each frame */ 068 private final HistogramModel histogramModel = new HistogramModel( 4,4,4 ); 069 070 /** The histogram of the previous frame */ 071 private double[][][] lastHistogram = null; 072 073 /** The number of grid elements in the grid */ 074 private int nGridElements = 20; 075 076 /** The percentage of tiles to use as the most similar */ 077 private final double pcMostSimilar = 0.1; 078 079 /** The percentage of tiles to use as the most dissimilar */ 080 private final double pcMostDissimilar = 0.1; 081 082 /** The boosting factor to use */ 083 private final double boostFactor = 1.1; 084 085 /** The limiting factor to use */ 086 private final double limitingFactor = 0.9; 087 088 /** 089 * If you use this constructor, your timecodes will be messed up 090 * unless you call {@link #setFPS(double)} before you process 091 * any frames. 092 * @param nGridElements The number of x and y grid elements 093 * (there will be this number squared in total) 094 */ 095 public LocalHistogramVideoShotDetector( final int nGridElements ) 096 { 097 this.nGridElements = nGridElements; 098 this.lastHistogram = new double[this.nGridElements][this.nGridElements][]; 099 this.threshold = 0.2; 100 } 101 102 /** 103 * 104 * @param video The video to process 105 * @param nGridElements The number of x and y grid elements 106 * (there will be this number squared in total) 107 */ 108 public LocalHistogramVideoShotDetector( final Video<MBFImage> video, 109 final int nGridElements ) 110 { 111 super( video ); 112 this.nGridElements = nGridElements; 113 this.lastHistogram = new double[nGridElements][nGridElements][]; 114 this.threshold = 0.2; 115 } 116 117 /** 118 * {@inheritDoc} 119 * @see org.openimaj.video.processing.shotdetector.VideoShotDetector#getInterframeDistance(org.openimaj.image.Image) 120 */ 121 @Override 122 protected double getInterframeDistance( final MBFImage frame ) 123 { 124 // The histogram distance at each element 125 final double[][] avgHisto = new double[this.nGridElements][this.nGridElements]; 126 127 // Work out the size of each grid element in pixels 128 final int gw = frame.getWidth() / this.nGridElements; 129 final int gh = frame.getHeight() / this.nGridElements; 130 131 // Loop through the grid elements 132 for( int y = 0; y < this.nGridElements; y++ ) 133 { 134 for( int x = 0; x < this.nGridElements; x++ ) 135 { 136 // Extract the local image 137 final MBFImage img = frame.extractROI( x*gw, y*gh, gw, gh ); 138 139 // Estimate the histogram 140 this.histogramModel.estimateModel( img ); 141 final double[] histogram = this.histogramModel. 142 histogram.asDoubleVector(); 143 144 // If we have a grid element histogram to compare against, 145 // we will implement the algorithm 146 if( this.lastHistogram[y][x] != null ) 147 { 148 final double dist = DoubleFVComparison.EUCLIDEAN.compare( 149 histogram, this.lastHistogram[y][x] ); 150 avgHisto[y][x] = dist; 151 } 152 153 // Store the histogram for this grid element for next time 154 this.lastHistogram[y][x] = histogram; 155 } 156 157 } 158 159 // We'll work now with a 1D array 160 double[] flattenedAvgHisto = ArrayUtils.reshape( avgHisto ); 161 162 // --- Calculate most similar and dissimilar tiles for boosting --- 163 // Sort the avgHisto values retaining their original indices 164 final int[] indices = new int[this.nGridElements*this.nGridElements]; 165 166 // Sort the histogram distance array. The smallest values will end 167 // up at the end of the array - the smallest values are the most similar. 168 ArrayUtils.parallelQuicksortDescending( flattenedAvgHisto, 169 ArrayUtils.fill( indices ) ); 170 171 // Create an array with the boost/limit factors in it 172 final double[][] similarDissimilar = 173 new double[this.nGridElements][this.nGridElements]; 174 175 // Set the boost/limit factors 176 for( int index = 0; index < indices.length; index++ ) 177 { 178 double factor = 1; 179 if( index < this.nGridElements * this.nGridElements * this.pcMostDissimilar ) 180 factor = this.limitingFactor; 181 else 182 if( index >= this.nGridElements * this.nGridElements * (1-this.pcMostSimilar) ) 183 factor = this.boostFactor; 184 else factor = 1; 185 186 final int y = indices[index] / this.nGridElements; 187 final int x = indices[index] % this.nGridElements; 188 similarDissimilar[y][x] = factor; 189 } 190 191 // DEBUG 192// this.drawBoxes( frame, similarDissimilar ); 193 194 // Boost the avgHisto values based on the distance measures 195 for( int y = 0; y < this.nGridElements; y++ ) 196 for( int x = 0; x < this.nGridElements; x++ ) 197 avgHisto[y][x] *= similarDissimilar[y][x]; 198 199 // Calculate the average histogram distance (over all the grid elements) 200 flattenedAvgHisto = ArrayUtils.reshape( avgHisto ); 201 double avgDist = ArrayUtils.sumValues( flattenedAvgHisto ); 202 avgDist /= this.nGridElements * this.nGridElements; 203 204 // Calculate the stddev 205 ArrayUtils.subtract( flattenedAvgHisto, avgDist ); 206 final double stdDev = Math.sqrt( ArrayUtils.sumValuesSquared( 207 flattenedAvgHisto ) / (this.nGridElements*this.nGridElements) ); 208 209 return stdDev; 210 } 211 212 /** 213 * Draws the boxes to show movements. 214 * @param img The image to draw to 215 */ 216 protected void drawBoxes( final MBFImage img, final double[][] sim ) 217 { 218 final int gw = img.getWidth() / this.nGridElements; 219 final int gh = img.getHeight() / this.nGridElements; 220 for( int y = 0; y < this.nGridElements; y++ ) 221 { 222 for( int x = 0; x < this.nGridElements; x++ ) 223 { 224 Float[] c = new Float[]{0f,0f,0f,0f}; 225 if( sim[y][x] == this.boostFactor ) 226 c = RGBColour.RED; 227 else 228 if( sim[y][x] == this.limitingFactor ) 229 c = RGBColour.BLUE; 230 else c = RGBColour.BLACK; 231 img.drawShape( new Rectangle(x*gw,y*gh,gw,gh), c ); 232 } 233 } 234 } 235}