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.image.feature.dense.gradient.binning; 031 032import org.openimaj.citation.annotation.Reference; 033import org.openimaj.citation.annotation.ReferenceType; 034import org.openimaj.image.analysis.algorithm.histogram.WindowedHistogramExtractor; 035import org.openimaj.image.analysis.algorithm.histogram.binning.SpatialBinningStrategy; 036import org.openimaj.math.geometry.shape.Rectangle; 037import org.openimaj.math.statistics.distribution.Histogram; 038import org.openimaj.util.array.ArrayUtils; 039 040/** 041 * Implementation of an {@link SpatialBinningStrategy} that extracts normalised 042 * HOG features in the style defined by Dalal and Triggs. In this scheme, 043 * histograms are computed for fixed size cells (size in pixels), and are 044 * aggregated over fixed size blocks of cells. Blocks may overlap. The 045 * aggregated histogram for each block is then normalised before being appended 046 * into the final output histogram. 047 * 048 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 049 */ 050@Reference( 051 type = ReferenceType.Inproceedings, 052 author = { "Dalal, Navneet", "Triggs, Bill" }, 053 title = "Histograms of Oriented Gradients for Human Detection", 054 year = "2005", 055 booktitle = "Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1 - Volume 01", 056 pages = { "886", "", "893" }, 057 url = "http://dx.doi.org/10.1109/CVPR.2005.177", 058 publisher = "IEEE Computer Society", 059 series = "CVPR '05", 060 customData = { 061 "isbn", "0-7695-2372-2", 062 "numpages", "8", 063 "doi", "10.1109/CVPR.2005.177", 064 "acmid", "1069007", 065 "address", "Washington, DC, USA" 066 }) 067public class FixedHOGStrategy implements SpatialBinningStrategy { 068 /** 069 * Block normalisation schemes 070 * 071 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 072 * 073 */ 074 public enum BlockNormalisation { 075 /** 076 * L1 normalisation 077 */ 078 L1 { 079 @Override 080 final void normalise(Histogram h, int blockArea) { 081 h.normaliseL1(); 082 } 083 }, 084 /** 085 * L2 normalisation 086 */ 087 L2 { 088 @Override 089 final void normalise(Histogram h, int blockArea) { 090 // each cell is l2 normed, so it follows that the l2 norm of the 091 // block is simply the values divided by the area 092 ArrayUtils.divide(h.values, blockArea); 093 } 094 }, 095 /** 096 * L1 normalisation followed by element-wise sqrt 097 */ 098 L1sqrt { 099 @Override 100 final void normalise(Histogram h, int blockArea) { 101 h.normaliseL1(); 102 103 for (int x = 0; x < h.values.length; x++) 104 h.values[x] = Math.sqrt(h.values[x]); 105 } 106 }, 107 /** 108 * L2 normalisation; clipping values above 0.2; L2 normalisation 109 */ 110 L2clip { 111 @Override 112 final void normalise(Histogram h, int blockArea) { 113 // each cell is l2 normed, so it follows that the l2 norm of the 114 // block is simply the values divided by the area 115 double sumsq = 0; 116 for (int x = 0; x < h.values.length; x++) { 117 h.values[x] = h.values[x] / blockArea; 118 if (h.values[x] > 0.2) 119 h.values[x] = 0.2; 120 sumsq += h.values[x] * h.values[x]; 121 } 122 123 final double invNorm = 1.0 / Math.sqrt(sumsq); 124 for (int x = 0; x < h.values.length; x++) { 125 h.values[x] *= invNorm; 126 } 127 } 128 }; 129 130 abstract void normalise(Histogram h, int blockArea); 131 } 132 133 int cellWidth = 6; 134 int cellHeight = 6; 135 int cellsPerBlockX = 3; 136 int cellsPerBlockY = 3; 137 int blockStepX = 1; 138 int blockStepY = 1; 139 BlockNormalisation norm = BlockNormalisation.L2; 140 141 /** 142 * Construct with square cells of the given size (in pixels). Square blocks 143 * are constructed from the given number of cells in each dimension. Blocks 144 * overlap, and shift by 1 cell (i.e. overlap is cellsPerBlock - 1). 145 * 146 * @param cellSize 147 * the size of the cells in pixels 148 * @param cellsPerBlock 149 * the number of cells per block 150 * @param norm 151 * the normalisation scheme 152 */ 153 public FixedHOGStrategy(int cellSize, int cellsPerBlock, BlockNormalisation norm) { 154 this(cellSize, cellsPerBlock, 1, norm); 155 } 156 157 /** 158 * Construct with square cells of the given size (in pixels). Square blocks 159 * are constructed from the given number of cells in each dimension. 160 * 161 * @param cellSize 162 * the size of the cells in pixels 163 * @param cellsPerBlock 164 * the number of cells per block 165 * @param blockStep 166 * the amount to shift each block in terms of cells 167 * @param norm 168 * the normalisation scheme 169 */ 170 public FixedHOGStrategy(int cellSize, int cellsPerBlock, int blockStep, BlockNormalisation norm) { 171 this(cellSize, cellSize, cellsPerBlock, cellsPerBlock, blockStep, blockStep, norm); 172 } 173 174 /** 175 * Construct with square cells of the given size (in pixels). Square blocks 176 * are constructed from the given number of cells in each dimension. 177 * 178 * @param cellWidth 179 * the width of the cells in pixels 180 * @param cellHeight 181 * the height of the cells in pixels 182 * @param cellsPerBlockX 183 * the number of cells per block in the x direction 184 * @param cellsPerBlockY 185 * the number of cells per block in the y direction 186 * @param blockStepX 187 * the amount to shift each block in terms of cells in the x 188 * direction 189 * @param blockStepY 190 * the amount to shift each block in terms of cells in the y 191 * direction 192 * @param norm 193 * the normalisation scheme 194 */ 195 public FixedHOGStrategy(int cellWidth, int cellHeight, int cellsPerBlockX, int cellsPerBlockY, int blockStepX, 196 int blockStepY, BlockNormalisation norm) 197 { 198 super(); 199 this.cellWidth = cellWidth; 200 this.cellHeight = cellHeight; 201 this.cellsPerBlockX = cellsPerBlockX; 202 this.cellsPerBlockY = cellsPerBlockY; 203 this.norm = norm; 204 this.blockStepX = blockStepX; 205 this.blockStepY = blockStepY; 206 } 207 208 @Override 209 public Histogram extract(WindowedHistogramExtractor binnedData, Rectangle region, Histogram output) { 210 final Histogram[][] cells = computeCells(binnedData, region); 211 final Histogram[][] blocks = computeBlocks(cells); 212 213 final int blockSize = blocks[0][0].values.length; 214 final int blockArea = cellsPerBlockX * cellsPerBlockY; 215 216 if (output == null || output.values.length != blocks[0].length * blocks.length * blockSize) 217 output = new Histogram(blocks[0].length * blocks.length * blockSize); 218 219 for (int j = 0, k = 0; j < blocks.length; j++) { 220 for (int i = 0; i < blocks[0].length; i++, k++) { 221 norm.normalise(blocks[j][i], blockArea); 222 223 System.arraycopy(blocks[j][i].values, 0, output.values, k * blockSize, blockSize); 224 } 225 } 226 227 return output; 228 } 229 230 private Histogram[][] computeBlocks(Histogram[][] cells) { 231 final int numBlocksX = 1 + (cells[0].length - cellsPerBlockX) / this.blockStepX; 232 final int numBlocksY = 1 + (cells.length - cellsPerBlockY) / this.blockStepY; 233 final Histogram[][] blocks = new Histogram[numBlocksY][numBlocksX]; 234 235 for (int y = 0; y < numBlocksY; y++) { 236 for (int x = 0; x < numBlocksX; x++) { 237 final Histogram[] blockData = new Histogram[cellsPerBlockX * cellsPerBlockY]; 238 239 for (int j = 0, k = 0; j < cellsPerBlockY; j++) { 240 for (int i = 0; i < cellsPerBlockX; i++) { 241 blockData[k++] = cells[y * blockStepY + j][x * blockStepX + i]; 242 } 243 } 244 245 blocks[y][x] = new Histogram(blockData); 246 } 247 } 248 return blocks; 249 } 250 251 private Histogram[][] computeCells(WindowedHistogramExtractor binnedData, Rectangle region) { 252 final int numCellsX = (int) ((region.width + cellWidth / 2) / cellWidth); 253 final int numCellsY = (int) ((region.height + cellHeight / 2) / cellHeight); 254 255 final Histogram[][] cells = new Histogram[numCellsY][numCellsX]; 256 for (int j = 0, y = (int) region.y; j < numCellsY; j++, y += cellHeight) { 257 for (int i = 0, x = (int) region.x; i < numCellsX; i++, x += cellWidth) { 258 cells[j][i] = binnedData.computeHistogram(x, y, cellWidth, cellHeight); 259 cells[j][i].normaliseL2(); 260 } 261 } 262 263 return cells; 264 } 265}