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.image.analysis.algorithm.histogram.GradientOrientationHistogramExtractor; 033import org.openimaj.image.analysis.algorithm.histogram.WindowedHistogramExtractor; 034import org.openimaj.image.analysis.algorithm.histogram.binning.SpatialBinningStrategy; 035import org.openimaj.image.feature.dense.gradient.binning.FixedHOGStrategy.BlockNormalisation; 036import org.openimaj.math.geometry.shape.Rectangle; 037import org.openimaj.math.statistics.distribution.Histogram; 038 039/** 040 * A {@link SpatialBinningStrategy} very much like the {@link FixedHOGStrategy}, 041 * but with flexibly sized cells that grow/shrink such that the number of cells 042 * in any given window is constant. Coupled with a 043 * {@link GradientOrientationHistogramExtractor}, this provides a way to 044 * efficiently extract the HOG descriptor of any rectangular window. 045 * 046 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 047 */ 048public class FlexibleHOGStrategy implements SpatialBinningStrategy { 049 int numCellsX = 8; 050 int numCellsY = 16; 051 int cellsPerBlockX = 2; 052 int cellsPerBlockY = 2; 053 BlockNormalisation norm = BlockNormalisation.L2; 054 055 private int numBlocksX; 056 private int numBlocksY; 057 private int blockLength; 058 private int blockArea; 059 private int blockStepX; 060 private int blockStepY; 061 062 private transient Histogram[][] blocks; 063 private transient Histogram[][] cells; 064 065 /** 066 * Construct with the given number of cells per window (or image). Square 067 * blocks are constructed from the given number of cells in each dimension. 068 * Blocks overlap, and shift by 1 cell (i.e. overlap is cellsPerBlock - 1). 069 * {@link BlockNormalisation#L2} is used for block normalisation. 070 * 071 * @param numCellsX 072 * the number of cells per window in the x direction 073 * @param numCellsY 074 * the number of cells per window in the y direction 075 * @param cellsPerBlock 076 * the number of cells per block 077 */ 078 public FlexibleHOGStrategy(int numCellsX, int numCellsY, int cellsPerBlock) { 079 this(numCellsX, numCellsY, cellsPerBlock, 1, BlockNormalisation.L2); 080 } 081 082 /** 083 * Construct with the given number of cells per window (or image). Square 084 * blocks are constructed from the given number of cells in each dimension. 085 * Blocks overlap, and shift by 1 cell (i.e. overlap is cellsPerBlock - 1). 086 * 087 * @param numCellsX 088 * the number of cells per window in the x direction 089 * @param numCellsY 090 * the number of cells per window in the y direction 091 * @param cellsPerBlock 092 * the number of cells per block 093 * @param norm 094 * the normalisation scheme 095 */ 096 public FlexibleHOGStrategy(int numCellsX, int numCellsY, int cellsPerBlock, BlockNormalisation norm) { 097 this(numCellsX, numCellsY, cellsPerBlock, 1, norm); 098 } 099 100 /** 101 * Construct with the given number of cells per window (or image). Square 102 * blocks are constructed from the given number of cells in each dimension. 103 * 104 * @param numCellsX 105 * the number of cells per window in the x direction 106 * @param numCellsY 107 * the number of cells per window in the y direction 108 * @param cellsPerBlock 109 * the number of cells per block 110 * @param blockStep 111 * the amount to shift each block in terms of cells 112 * @param norm 113 * the normalisation scheme 114 */ 115 public FlexibleHOGStrategy(int numCellsX, int numCellsY, int cellsPerBlock, int blockStep, BlockNormalisation norm) { 116 this(numCellsX, numCellsY, cellsPerBlock, cellsPerBlock, blockStep, blockStep, norm); 117 } 118 119 /** 120 * Construct with the given number of cells per window (or image). 121 * Rectangular blocks are constructed from the given number of cells in each 122 * dimension. 123 * 124 * @param numCellsX 125 * the number of cells per window in the x direction 126 * @param numCellsY 127 * the number of cells per window in the y direction 128 * @param cellsPerBlockX 129 * the number of cells per block in the x direction 130 * @param cellsPerBlockY 131 * the number of cells per block in the y direction 132 * @param blockStepX 133 * the amount to shift each block in terms of cells in the x 134 * direction 135 * @param blockStepY 136 * the amount to shift each block in terms of cells in the y 137 * direction 138 * @param norm 139 * the normalisation scheme 140 */ 141 public FlexibleHOGStrategy(int numCellsX, int numCellsY, int cellsPerBlockX, int cellsPerBlockY, 142 int blockStepX, int blockStepY, BlockNormalisation norm) 143 { 144 super(); 145 this.numCellsX = numCellsX; 146 this.numCellsY = numCellsY; 147 this.cellsPerBlockX = cellsPerBlockX; 148 this.cellsPerBlockY = cellsPerBlockY; 149 this.norm = norm; 150 this.blockStepX = blockStepX; 151 this.blockStepY = blockStepY; 152 153 numBlocksX = 1 + (numCellsX - cellsPerBlockX) / blockStepX; 154 numBlocksY = 1 + (numCellsY - cellsPerBlockY) / blockStepY; 155 } 156 157 @Override 158 public Histogram extract(WindowedHistogramExtractor binnedData, Rectangle region, Histogram output) { 159 if (cells == null || cells[0][0].values.length != binnedData.getNumBins()) { 160 cells = new Histogram[numCellsY][numCellsX]; 161 blocks = new Histogram[numBlocksY][numBlocksX]; 162 163 for (int j = 0; j < numCellsY; j++) 164 for (int i = 0; i < numCellsX; i++) 165 cells[j][i] = new Histogram(binnedData.getNumBins()); 166 167 for (int j = 0; j < numBlocksY; j++) 168 for (int i = 0; i < numBlocksX; i++) 169 blocks[j][i] = new Histogram(binnedData.getNumBins() * cellsPerBlockX * cellsPerBlockY); 170 171 blockLength = blocks[0][0].values.length; 172 blockArea = cellsPerBlockX * cellsPerBlockY; 173 } 174 175 computeCells(binnedData, region); 176 computeBlocks(cells); 177 178 if (output == null || output.values.length != blocks[0].length * blocks.length * blockLength) 179 output = new Histogram(blocks[0].length * blocks.length * blockLength); 180 181 for (int j = 0, k = 0; j < blocks.length; j++) { 182 for (int i = 0; i < blocks[0].length; i++, k++) { 183 norm.normalise(blocks[j][i], blockArea); 184 185 System.arraycopy(blocks[j][i].values, 0, output.values, k * blockLength, blockLength); 186 } 187 } 188 189 return output; 190 } 191 192 private void computeBlocks(Histogram[][] cells) { 193 for (int y = 0; y < numBlocksY; y++) { 194 for (int x = 0; x < numBlocksX; x++) { 195 final double[] blockData = blocks[y][x].values; 196 197 for (int j = 0, k = 0; j < cellsPerBlockY; j++) { 198 for (int i = 0; i < cellsPerBlockX; i++) { 199 final double[] cellData = cells[y * blockStepY + j][x * blockStepX + i].values; 200 201 System.arraycopy(cellData, 0, blockData, k, cellData.length); 202 203 k += cellData.length; 204 } 205 } 206 } 207 } 208 } 209 210 private void computeCells(WindowedHistogramExtractor binnedData, Rectangle region) { 211 final int cellWidth = (int) (region.width / numCellsX); 212 final int cellHeight = (int) (region.height / numCellsY); 213 214 for (int j = 0, y = (int) region.y; j < numCellsY; j++, y += cellHeight) { 215 for (int i = 0, x = (int) region.x; i < numCellsX; i++, x += cellWidth) { 216 binnedData.computeHistogram(x, y, cellWidth, cellHeight, cells[j][i]); 217 cells[j][i].normaliseL2(); 218 } 219 } 220 } 221}