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.List;
034
035import org.openimaj.feature.ArrayFeatureVector;
036import org.openimaj.feature.FeatureVector;
037import org.openimaj.feature.local.LocalFeature;
038import org.openimaj.feature.local.SpatialLocation;
039import org.openimaj.math.geometry.shape.Rectangle;
040import org.openimaj.util.concatenate.Concatenatable;
041
042/**
043 * A {@link BlockSpatialAggregator} performs spatial pooling of local features
044 * by grouping the local features into non-overlapping, fixed-size spatial
045 * blocks, and applying a {@link VectorAggregator} (i.e. a
046 * {@link BagOfVisualWords}) to the features within each block before combining
047 * the aggregated results into a single vector (by passing through the blocks in
048 * a left-right, top-bottom fashion).
049 * 
050 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
051 * 
052 * @param <T>
053 *            Primitive array type of the backing array of each local feature
054 * @param <AGGREGATE>
055 *            Type of the aggregate {@link FeatureVector} produced
056 */
057public class BlockSpatialAggregator<T, AGGREGATE extends FeatureVector & Concatenatable<AGGREGATE, AGGREGATE>>
058                implements
059                SpatialVectorAggregator<ArrayFeatureVector<T>, SpatialLocation, Rectangle>
060{
061        protected VectorAggregator<ArrayFeatureVector<T>, AGGREGATE> innerAggregator;
062        protected int blocksX;
063        protected int blocksY;
064
065        /**
066         * Construct with the given aggregator and number of blocks in the X and Y
067         * dimensions.
068         * 
069         * @param innerAggregator
070         *            the aggregator
071         * @param blocksX
072         *            the number of blocks in X
073         * @param blocksY
074         *            the number of blocks in Y
075         */
076        public BlockSpatialAggregator(VectorAggregator<ArrayFeatureVector<T>, AGGREGATE> innerAggregator, int blocksX,
077                        int blocksY)
078        {
079                this.innerAggregator = innerAggregator;
080                this.blocksX = blocksX;
081                this.blocksY = blocksY;
082        }
083
084        @Override
085        public AGGREGATE aggregate(
086                        List<? extends LocalFeature<? extends SpatialLocation, ? extends ArrayFeatureVector<T>>> features,
087                        Rectangle bounds)
088        {
089                final List<List<LocalFeature<? extends SpatialLocation, ? extends ArrayFeatureVector<T>>>> spatialFeatures =
090                                new ArrayList<List<LocalFeature<? extends SpatialLocation, ? extends ArrayFeatureVector<T>>>>(blocksX
091                                                * blocksY);
092
093                for (int i = 0; i < blocksX * blocksY; i++)
094                        spatialFeatures
095                                        .add(new ArrayList<LocalFeature<? extends SpatialLocation, ? extends ArrayFeatureVector<T>>>());
096
097                final float stepX = (bounds.width - bounds.x) / blocksX;
098                final float stepY = (bounds.height - bounds.y) / blocksY;
099
100                for (final LocalFeature<? extends SpatialLocation, ? extends ArrayFeatureVector<T>> f : features) {
101                        final SpatialLocation l = f.getLocation();
102
103                        final int xbin = (int) Math.floor((l.x - bounds.x) / stepX);
104                        final int ybin = (int) Math.floor((l.y - bounds.y) / stepY);
105                        final int idx = xbin + blocksX * ybin;
106
107                        spatialFeatures.get(idx).add(f);
108                }
109
110                final AGGREGATE first = innerAggregator.aggregate(spatialFeatures.get(0));
111
112                final List<AGGREGATE> others = new ArrayList<AGGREGATE>(spatialFeatures.size() - 1);
113                for (int i = 1; i < spatialFeatures.size(); i++) {
114                        others.add(innerAggregator.aggregate(spatialFeatures.get(i)));
115                }
116
117                return first.concatenate(others);
118        }
119}