1 /**
2 * Copyright (c) 2011, The University of Southampton and the individual contributors.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification,
6 * are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 *
11 * * Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * * Neither the name of the University of Southampton nor the names of its
16 * contributors may be used to endorse or promote products derived from this
17 * software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
23 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
26 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30 package org.openimaj.image.feature.dense.gradient.binning;
31
32 import org.openimaj.image.analysis.algorithm.histogram.GradientOrientationHistogramExtractor;
33 import org.openimaj.image.analysis.algorithm.histogram.WindowedHistogramExtractor;
34 import org.openimaj.image.analysis.algorithm.histogram.binning.SpatialBinningStrategy;
35 import org.openimaj.image.feature.dense.gradient.binning.FixedHOGStrategy.BlockNormalisation;
36 import org.openimaj.math.geometry.shape.Rectangle;
37 import org.openimaj.math.statistics.distribution.Histogram;
38
39 /**
40 * A {@link SpatialBinningStrategy} very much like the {@link FixedHOGStrategy},
41 * but with flexibly sized cells that grow/shrink such that the number of cells
42 * in any given window is constant. Coupled with a
43 * {@link GradientOrientationHistogramExtractor}, this provides a way to
44 * efficiently extract the HOG descriptor of any rectangular window.
45 *
46 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
47 */
48 public class FlexibleHOGStrategy implements SpatialBinningStrategy {
49 int numCellsX = 8;
50 int numCellsY = 16;
51 int cellsPerBlockX = 2;
52 int cellsPerBlockY = 2;
53 BlockNormalisation norm = BlockNormalisation.L2;
54
55 private int numBlocksX;
56 private int numBlocksY;
57 private int blockLength;
58 private int blockArea;
59 private int blockStepX;
60 private int blockStepY;
61
62 private transient Histogram[][] blocks;
63 private transient Histogram[][] cells;
64
65 /**
66 * Construct with the given number of cells per window (or image). Square
67 * blocks are constructed from the given number of cells in each dimension.
68 * Blocks overlap, and shift by 1 cell (i.e. overlap is cellsPerBlock - 1).
69 * {@link BlockNormalisation#L2} is used for block normalisation.
70 *
71 * @param numCellsX
72 * the number of cells per window in the x direction
73 * @param numCellsY
74 * the number of cells per window in the y direction
75 * @param cellsPerBlock
76 * the number of cells per block
77 */
78 public FlexibleHOGStrategy(int numCellsX, int numCellsY, int cellsPerBlock) {
79 this(numCellsX, numCellsY, cellsPerBlock, 1, BlockNormalisation.L2);
80 }
81
82 /**
83 * Construct with the given number of cells per window (or image). Square
84 * blocks are constructed from the given number of cells in each dimension.
85 * Blocks overlap, and shift by 1 cell (i.e. overlap is cellsPerBlock - 1).
86 *
87 * @param numCellsX
88 * the number of cells per window in the x direction
89 * @param numCellsY
90 * the number of cells per window in the y direction
91 * @param cellsPerBlock
92 * the number of cells per block
93 * @param norm
94 * the normalisation scheme
95 */
96 public FlexibleHOGStrategy(int numCellsX, int numCellsY, int cellsPerBlock, BlockNormalisation norm) {
97 this(numCellsX, numCellsY, cellsPerBlock, 1, norm);
98 }
99
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 }