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 square cells of the given size (in pixels). Square blocks 067 * are constructed from the given number of cells in each dimension. Blocks 068 * 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 square cells of the given size (in pixels). Square blocks 084 * are constructed from the given number of cells in each dimension. Blocks 085 * 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 square cells of the given size (in pixels). Square blocks 102 * 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 square cells of the given size (in pixels). Square blocks 121 * are constructed from the given number of cells in each dimension. 122 * 123 * @param numCellsX 124 * the number of cells per window in the x direction 125 * @param numCellsY 126 * the number of cells per window in the y direction 127 * @param cellsPerBlockX 128 * the number of cells per block in the x direction 129 * @param cellsPerBlockY 130 * the number of cells per block in the y direction 131 * @param blockStepX 132 * the amount to shift each block in terms of cells in the x 133 * direction 134 * @param blockStepY 135 * the amount to shift each block in terms of cells in the y 136 * direction 137 * @param norm 138 * the normalisation scheme 139 */ 140 public FlexibleHOGStrategy(int numCellsX, int numCellsY, int cellsPerBlockX, int cellsPerBlockY, 141 int blockStepX, int blockStepY, BlockNormalisation norm) 142 { 143 super(); 144 this.numCellsX = numCellsX; 145 this.numCellsY = numCellsY; 146 this.cellsPerBlockX = cellsPerBlockX; 147 this.cellsPerBlockY = cellsPerBlockY; 148 this.norm = norm; 149 this.blockStepX = blockStepX; 150 this.blockStepY = blockStepY; 151 152 numBlocksX = 1 + (numCellsX - cellsPerBlockX) / blockStepX; 153 numBlocksY = 1 + (numCellsY - cellsPerBlockY) / blockStepY; 154 } 155 156 @Override 157 public Histogram extract(WindowedHistogramExtractor binnedData, Rectangle region, Histogram output) { 158 if (cells == null || cells[0][0].values.length != binnedData.getNumBins()) { 159 cells = new Histogram[numCellsY][numCellsX]; 160 blocks = new Histogram[numBlocksY][numBlocksX]; 161 162 for (int j = 0; j < numCellsY; j++) 163 for (int i = 0; i < numCellsX; i++) 164 cells[j][i] = new Histogram(binnedData.getNumBins()); 165 166 for (int j = 0; j < numBlocksY; j++) 167 for (int i = 0; i < numBlocksX; i++) 168 blocks[j][i] = new Histogram(binnedData.getNumBins() * cellsPerBlockX * cellsPerBlockY); 169 170 blockLength = blocks[0][0].values.length; 171 blockArea = cellsPerBlockX * cellsPerBlockY; 172 } 173 174 computeCells(binnedData, region); 175 computeBlocks(cells); 176 177 if (output == null || output.values.length != blocks[0].length * blocks.length * blockLength) 178 output = new Histogram(blocks[0].length * blocks.length * blockLength); 179 180 for (int j = 0, k = 0; j < blocks.length; j++) { 181 for (int i = 0; i < blocks[0].length; i++, k++) { 182 norm.normalise(blocks[j][i], blockArea); 183 184 System.arraycopy(blocks[j][i].values, 0, output.values, k * blockLength, blockLength); 185 } 186 } 187 188 return output; 189 } 190 191 private void computeBlocks(Histogram[][] cells) { 192 for (int y = 0; y < numBlocksY; y++) { 193 for (int x = 0; x < numBlocksX; x++) { 194 final double[] blockData = blocks[y][x].values; 195 196 for (int j = 0, k = 0; j < cellsPerBlockY; j++) { 197 for (int i = 0; i < cellsPerBlockX; i++) { 198 final double[] cellData = cells[y * blockStepY + j][x * blockStepX + i].values; 199 200 System.arraycopy(cellData, 0, blockData, k, cellData.length); 201 202 k += cellData.length; 203 } 204 } 205 } 206 } 207 } 208 209 private void computeCells(WindowedHistogramExtractor binnedData, Rectangle region) { 210 final int cellWidth = (int) (region.width / numCellsX); 211 final int cellHeight = (int) (region.height / numCellsY); 212 213 for (int j = 0, y = (int) region.y; j < numCellsY; j++, y += cellHeight) { 214 for (int i = 0, x = (int) region.x; i < numCellsX; i++, x += cellWidth) { 215 binnedData.computeHistogram(x, y, cellWidth, cellHeight, cells[j][i]); 216 cells[j][i].normaliseL2(); 217 } 218 } 219 } 220}