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.local.aggregate;
031
032import java.util.ArrayList;
033import java.util.Arrays;
034import java.util.List;
035
036import org.openimaj.feature.ArrayFeatureVector;
037import org.openimaj.feature.FeatureVector;
038import org.openimaj.feature.local.LocalFeature;
039import org.openimaj.feature.local.SpatialLocation;
040import org.openimaj.math.geometry.shape.Rectangle;
041import org.openimaj.util.concatenate.Concatenatable;
042
043/**
044 * A {@link PyramidSpatialAggregator} performs spatial pooling of local features
045 * by grouping the local features into fixed-size spatial blocks within a
046 * pyramid, and applying a {@link VectorAggregator} (i.e. a
047 * {@link BagOfVisualWords}) to the features within each block before combining
048 * the aggregated results into a single vector (by passing through the blocks in
049 * a left-right, top-bottom fashion over the pyramid levels from the top down).
050 * 
051 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
052 * 
053 * @param <T>
054 *            Primitive array type of the backing array of each local feature
055 * @param <AGGREGATE>
056 *            Type of the aggregate {@link FeatureVector} produced
057 */
058public class PyramidSpatialAggregator<T, AGGREGATE extends FeatureVector & Concatenatable<AGGREGATE, AGGREGATE>>
059                implements
060                SpatialVectorAggregator<ArrayFeatureVector<T>, SpatialLocation, Rectangle>
061{
062        protected VectorAggregator<ArrayFeatureVector<T>, AGGREGATE> innerAggregator;
063        boolean[][][] levels;
064
065        /**
066         * Construct with the given aggregator and pyramid description (i.e.
067         * "1x1-2x2-4x4").
068         * 
069         * @param innerAggregator
070         *            the aggregator
071         * @param description
072         *            the pyramid description
073         */
074        public PyramidSpatialAggregator(VectorAggregator<ArrayFeatureVector<T>, AGGREGATE> innerAggregator, String description)
075        {
076                this.innerAggregator = innerAggregator;
077                this.levels = parseLevelsSimple(description);
078        }
079
080        /**
081         * Construct with the given aggregator and number of blocks per level.
082         * 
083         * @param innerAggregator
084         *            the aggregator
085         * @param numBlocks
086         *            number of blocks (in X and Y) for each level of the pyramid
087         */
088        public PyramidSpatialAggregator(VectorAggregator<ArrayFeatureVector<T>, AGGREGATE> innerAggregator, int... numBlocks)
089        {
090                this.innerAggregator = innerAggregator;
091                this.levels = new boolean[numBlocks.length][][];
092
093                for (int i = 0; i < numBlocks.length; i++) {
094                        this.levels[i] = new boolean[numBlocks[i]][numBlocks[i]];
095
096                        for (int j = 0; j < numBlocks[i]; j++)
097                                Arrays.fill(levels[i][j], true);
098                }
099        }
100
101        private static boolean[][][] parseLevelsSimple(String simple) {
102                final String[] parts = simple.split("-");
103                final boolean[][][] levels = new boolean[parts.length][][];
104
105                for (int i = 0; i < parts.length; i++) {
106                        final String part = parts[i];
107                        final String[] tmp = part.split("x");
108
109                        if (tmp.length != 2)
110                                throw new IllegalArgumentException("Invalid specification string");
111
112                        final int binsX = Integer.parseInt(tmp[0]);
113                        final int binsY = Integer.parseInt(tmp[1]);
114
115                        levels[i] = new boolean[binsY][binsX];
116
117                        for (int j = 0; j < binsY; j++)
118                                Arrays.fill(levels[i][j], true);
119                }
120
121                return levels;
122        }
123
124        protected static boolean[][][] parseLevelsAdvanced(String description) {
125                final String[] parts = description.split("[+]");
126                final List<boolean[][]> levels = new ArrayList<boolean[][]>();
127
128                for (int i = 0; i < parts.length; i++) {
129                        final List<String> levelDesc = new ArrayList<String>();
130
131                        levelDesc.add(parts[i]);
132                        final String key = parts[i].substring(0, parts[i].indexOf("#") + 1);
133
134                        for (; i < parts.length; i++) {
135                                if (parts[i].startsWith(key)) {
136                                        levelDesc.add(parts[i]);
137                                } else {
138                                        i--;
139                                        break;
140                                }
141                        }
142
143                        final int x = Integer.parseInt(key.substring(1, key.indexOf("x")));
144                        final int y = Integer.parseInt(key.substring(key.indexOf("x") + 1, key.indexOf("#")));
145                        final boolean[][] level = new boolean[y][x];
146
147                        for (int yy = 0; yy < y; yy++) {
148                                for (int xx = 0; xx < x; xx++) {
149                                        final String curr = key + (xx + yy * x);
150                                        if (levelDesc.contains(curr)) {
151                                                level[yy][xx] = true;
152                                        } else {
153                                                level[yy][xx] = false;
154                                        }
155                                }
156                        }
157
158                        levels.add(level);
159                }
160
161                return levels.toArray(new boolean[levels.size()][][]);
162        }
163
164        protected static String levelsToString(boolean[][][] levels) {
165                final StringBuilder sb = new StringBuilder();
166
167                for (int i = 0; i < levels.length; i++) {
168                        final int y = levels[i].length;
169                        final int x = levels[i][0].length;
170                        sb.append("Level " + i + " (" + x + "x" + y + "):\n");
171
172                        for (int yy = 0; yy < y; yy++) {
173                                for (int xx = 0; xx < x; xx++) {
174                                        sb.append(levels[i][yy][xx] ? "X" : "-");
175                                }
176                                sb.append("\n");
177                        }
178                        sb.append("\n");
179                }
180
181                return sb.toString();
182        }
183
184        @SuppressWarnings("unchecked")
185        @Override
186        public AGGREGATE aggregate(
187                        List<? extends LocalFeature<? extends SpatialLocation, ? extends ArrayFeatureVector<T>>> features,
188                        Rectangle bounds)
189        {
190                final List<AGGREGATE> levelFeatures = new ArrayList<AGGREGATE>(levels.length);
191
192                for (int l = 0; l < levels.length; l++) {
193                        final boolean[][] level = levels[l];
194                        final int blocksX = level[0].length;
195                        final int blocksY = level.length;
196
197                        final Object[][] spatialData = new Object[blocksY][blocksX];
198                        for (int y = 0; y < blocksY; y++) {
199                                for (int x = 0; x < blocksX; x++) {
200                                        if (level[y][x])
201                                                spatialData[y][x] = new ArrayList<LocalFeature<? extends SpatialLocation, ? extends ArrayFeatureVector<T>>>();
202                                }
203                        }
204
205                        final float stepX = (bounds.width - bounds.x) / blocksX;
206                        final float stepY = (bounds.height - bounds.y) / blocksY;
207
208                        for (final LocalFeature<? extends SpatialLocation, ? extends ArrayFeatureVector<T>> f : features) {
209                                final SpatialLocation spatialLoc = f.getLocation();
210
211                                final int xbin = (int) Math.floor((spatialLoc.x - bounds.x) / stepX);
212                                final int ybin = (int) Math.floor((spatialLoc.y - bounds.y) / stepY);
213
214                                if (level[ybin][xbin]) {
215                                        ((List<LocalFeature<? extends SpatialLocation, ? extends ArrayFeatureVector<T>>>) spatialData[ybin][xbin])
216                                                        .add(f);
217                                }
218                        }
219
220                        final List<AGGREGATE> spatialFeatures = new ArrayList<AGGREGATE>(blocksX * blocksY);
221                        for (int y = 0; y < blocksY; y++) {
222                                for (int x = 0; x < blocksX; x++) {
223                                        if (spatialData[y][x] != null) {
224                                                final AGGREGATE fv = innerAggregator
225                                                                .aggregate((List<LocalFeature<? extends SpatialLocation, ? extends ArrayFeatureVector<T>>>) spatialData[y][x]);
226
227                                                spatialFeatures.add(fv);
228                                        }
229                                }
230                        }
231                        levelFeatures.add(join(spatialFeatures));
232                }
233
234                return join(levelFeatures);
235        }
236
237        private AGGREGATE join(List<AGGREGATE> fvs) {
238                final AGGREGATE first = fvs.get(0);
239                final List<AGGREGATE> others = new ArrayList<AGGREGATE>(fvs.size() - 1);
240                for (int i = 1; i < fvs.size(); i++) {
241                        others.add(fvs.get(i));
242                }
243
244                return first.concatenate(others);
245        }
246}