Efficient appearance distances between windows V1.0 ==================================================== B. Alexe, V. Petrescu, V. Ferrari {bogdan, petrescu, ferrari}@vision.ee.ethz.ch vferrari@staffmail.ed.ac.uk This software was developed under Linux with Matlab R2011b (version 7.13) on a 64 bit machine. There is no guarantee it will run on other operating systems or Matlab versions (though it probably will). Introduction ------------ Welcome to this software release of our method for efficiently computing the distance of high-dimensional appearance descriptor vectors between image windows. In [1] we propose two efficient algorithms for computing distances of appearance descriptors between two sets of image windows, by taking advantage of the spatial overlap structure in the sets. These algorithms greatly reduce the number of appearance distances computed when solving the following two tasks: T1. find all pairs of windows with distance smaller that a threshold T2. find the single pair with the smallest distance This release covers the functionality described in [1]. Input: two sets of image windows and their appearance descriptors Output: approximate solution to task T1 or T2, computed very efficiently Installation ------------ Let be the directory where you uncompressed the release archive. Open a new shell and enter the following commands: 1. cd 2. matlab 3. compile # (this compiles the necessary MEX files) Usage ----- After installation, you can run the code with the following Matlab functions: For task T1: resultStruct = computeSmallerThanThresholdPairs(windowsImage1, descriptorsImage1, windowsImage2, descriptorsImage2, params, threshold); For task T2: resultsStruct = computeSmallestPair(windowsImage1, descriptorsImage1, windowsImage2, descriptorsImage2, params); Input: windowsImage1 – input windows for image 1 as an N1 x 4 array. Each row i of this array represents the [xmin ymin xmax ymax] coordinates of window i in image 1; descriptorsImage1 - input descriptors for windows in image 1 (windowsImage1) as an N1 x D array, where D is the dimensionality of the descriptor. Each row i of this array is the descriptor of window i in image 1; windowsImage2 - input windows for image 2 as an N2 x 4 array. descriptorsImage2 - input descriptors for windows in image 2 (windowsImage2) params - parameters of the algorithm, estimated beforehand on an external set of images (see below ‘Pre-learned parameters’ section). threshold - input threshold (used only for T1). Output: resultStruct - matlab structure with the following fields: - distanceMatrix - N1 x N2 matrix; element (i,j) is the distance between the descriptor of window i in image 1 and the descriptor of window j in image 2. The distances not computed are marked by ‘inf’. - outputPairs – M x 2 matrix containing the pairs (i,j) returned by the algorithm for the corresponding task. For task T1: 0<= M <= N1*N2; for task T2: M = 1. Example ------- In order to check that the code is working properly we provide precomputed descriptors of three types (GIST [2], Color Histograms, bag-of-words on SURF [4]) for an example pair of images. This data is in folders ExampleGIST, ExampleCHIST, ExampleSURF. Each folder also contains a MAT file with pre-learned parameters suitable for a descriptor (in struct ‘params’). Run the demo function with the input argument being the path to the folder. For example, for the GIST descriptors the function should be called as: [resultStructTask1 resultStructTask2] = demo([ ‘/ExampleGIST/’]) The function will solve tasks T1 and T2 for the case where N1 = N2 = 3000, D = 960 (the dimensionality of the GIST descriptor). Pre-learned parameters ---------------------- In this release we include the parameters (struct ‘params’) estimated from 1300 images from the PASCAL VOC 2007 dataset and ready to run on new test data (see [1]). Note how the parameters are estimated in an unsupervised manner, i.e. given just the images, with no manual annotation. This means you can use these pre-estimated parameters on any images without worrying about training/testing separation. The parameters used in [1] for three types of descriptors can be found in file [ '/Example/example.mat']. The parameters (matlab struct named 'params') consist of bound tables which relate spatial overlap to appearance distance, and are specific to a combination of an appearance descriptor and a distance function (e.g. GIST+L2, or SURF+Chi^2). The fields of the struct 'params' are: - descriptorDistance - the appearance distance function; - binSizeDescriptorDistance - bin size in the descriptor distance space, used to quantize the bound table; - maxDescriptorDistance - maximum possible appearance distance; - minimumOverlap - minimum overlap from eq. 10 in [1]; - percentageSampleTask1 - F used by algorithm 1 in [1]; - percentageSampleTask2 - F used by algorithm 2 in [1]; - alpha - specifies the confidence alpha used in eq. 6 in [1]. Re-estimating parameters on your dataset ---------------------------------------- In some cases you might wish to re-estimate parameters for your dataset, which might result in greater speedups (e.g. for a dataset with limited appearance variability, tighter bounds might be estimated). Or you might wish to estimate parameters suitable for another appearance descriptor and/or distance function. We include here software for re-estimating the parameters of our method using another training set. For this do: 1. for each training image create a MAT file containing the windows coordinates and their descriptors. The MAT file should contain two variables: "windows" (array N x 4) and "descriptors" (array N x D); 2. put all the MAT files in a folder (called hereafter 'NewTrainingFolder'); 3. learn the parameters by running in Matlab the following command: params = trainBound(pathNewTrainingFolder,handleDistanceFunction) Input: pathNewTrainingFolder - absolute path to NewTrainingFolder; handleDistanceFunction - handle to the descriptor distance function (e.g: @chiSquareDistance, @euclideanDistance) Output: params - learned parameters Example ------- We include in these release three folders, trainingDataGIST, trainingDataCHIST, trainingDataSURF that contain part of the training data (MAT files) used in [1] for each of three descriptors: GIST [2], Color Histograms, BOW-SURF [3]. To learn the parameters for Color Histograms from the data provided in the folder trainingDataCHIST you should run the following Matlab command: params = trainBound([ '/trainingDataGIST'],@chiSquareDistance); Note how this training data is provided only as an example to help understanding the code. The parameters learned from it are not exactly the same as those learned from the full 1300 images we used in [1]. We release the full parameters in this package as well (see above). Support ------- For any query/suggestion/complaint or simply to say you like/use this software, just drop us an email: bogdan@vision.ee.ethz.ch (please contact this address first) petrescu@vision.ee.ethz.ch ferrari@vision.ee.ethz.ch vferrari@staffmail.ed.ac.uk We wish you a good time using this software, Bogdan Alexe Viviana Petrescu Vittorio Ferrari References ---------- [1] Bogdan Alexe, Viviana Petrescu and Vittorio Ferrari Exploiting spatial overlap to efficiently compute appearance distances between image windows, NIPS 2011 [2] A. Oliva and A. Torralba Modeling the shape of the scene: a holistic representation of the spatial envelope. IJCV, 42(3):145–175, 2001 [3] H. Bay, A. Ess, T. Tuytelaars, and L. van Gool SURF: Speeded up robust features. CVIU, 110(3):346–359, 2008 Version history --------------- 1.0 --- - first public release