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.objectdetection.filtering;
031
032import java.util.ArrayList;
033import java.util.List;
034
035import org.openimaj.math.geometry.shape.Rectangle;
036import org.openimaj.util.pair.ObjectIntPair;
037
038/**
039 * Filter to perform the grouping of detection rectangles in the way OpenCV
040 * does. Basically the groups are formed by grouping together all the rectangles
041 * that overlap by a certain amount. For each group, the mean rectangle is
042 * calculated. Groups that have too little support are removed, as are groups
043 * that are enclosed by other groups.
044 * 
045 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
046 */
047public final class OpenCVGrouping implements DetectionFilter<Rectangle, ObjectIntPair<Rectangle>> {
048        /**
049         * The default eps value for determining whether two rectangles overlap
050         * enough to be considered as being of the same group.
051         */
052        public static final float DEFAULT_EPS = 0.2f;
053
054        /**
055         * The default value for the minimum number of rectangles required within a
056         * group.
057         */
058        public static final int DEFAULT_MINIMUM_SUPPORT = 3;
059
060        float eps;
061        int minSupport;
062
063        /**
064         * Construct a new {@link OpenCVGrouping} with the given parameters.
065         * 
066         * @param eps
067         *            The eps value for determining whether two rectangles overlap
068         *            enough to be considered as being of the same group.
069         * @param minSupport
070         *            The minimum number of rectangles required within a group.
071         *            Groups with less than this number of rectangles will be
072         *            removed.
073         */
074        public OpenCVGrouping(float eps, int minSupport) {
075                this.eps = eps;
076                this.minSupport = minSupport;
077        }
078
079        /**
080         * Construct a new {@link OpenCVGrouping} with the given minimum support
081         * number. The {@link #DEFAULT_EPS} value is used for the eps.
082         * 
083         * @param minSupport
084         *            The minimum number of rectangles required within a group.
085         *            Groups with less than this number of rectangles will be
086         *            removed.
087         */
088        public OpenCVGrouping(int minSupport) {
089                this(DEFAULT_EPS, minSupport);
090        }
091
092        /**
093         * Construct a new {@link OpenCVGrouping} with the default values of
094         * {@link #DEFAULT_EPS} for the eps and {@link #DEFAULT_MINIMUM_SUPPORT} for
095         * the support.
096         */
097        public OpenCVGrouping() {
098                this(DEFAULT_EPS, DEFAULT_MINIMUM_SUPPORT);
099        }
100
101        @Override
102        public List<ObjectIntPair<Rectangle>> apply(List<Rectangle> input) {
103                final int[] classes = new int[input.size()];
104                final int nClasses = partition(input, classes);
105
106                // Compute the mean rectangle per class
107                final Rectangle[] meanRects = new Rectangle[nClasses]; // mean rect
108                                                                                                                                // storage per
109                                                                                                                                // class
110                final int[] rectCounts = new int[nClasses]; // number of rectangles per
111                                                                                                        // class
112                for (int i = 0; i < nClasses; i++) {
113                        meanRects[i] = new Rectangle(0, 0, 0, 0);
114                }
115
116                for (int i = 0; i < classes.length; i++) {
117                        final int cls = classes[i];
118
119                        meanRects[cls].x += input.get(i).x;
120                        meanRects[cls].y += input.get(i).y;
121                        meanRects[cls].width += input.get(i).width;
122                        meanRects[cls].height += input.get(i).height;
123                        rectCounts[cls]++;
124                }
125
126                for (int i = 0; i < nClasses; i++) {
127                        final Rectangle r = meanRects[i];
128                        final float s = 1.0f / rectCounts[i];
129                        meanRects[i] = new Rectangle(Math.round(r.x * s), Math.round(r.y * s), Math.round(r.width * s),
130                                        Math.round(r.height * s));
131                }
132
133                // now filter out any classes that have too few rectangles, or is a
134                // small rectangles inclosed by another class.
135                final List<ObjectIntPair<Rectangle>> rectList = new ArrayList<ObjectIntPair<Rectangle>>();
136                for (int i = 0; i < nClasses; i++) {
137                        final Rectangle r1 = meanRects[i];
138                        final int n1 = rectCounts[i];
139
140                        if (n1 <= minSupport)
141                                continue;
142
143                        // filter out small face rectangles inside large rectangles
144                        int j;
145                        for (j = 0; j < nClasses; j++) {
146                                final int n2 = rectCounts[j];
147
148                                if (j == i || n2 <= minSupport)
149                                        continue;
150                                final Rectangle r2 = meanRects[j];
151
152                                final int dx = Math.round(r2.width * eps);
153                                final int dy = Math.round(r2.height * eps);
154
155                                if (i != j &&
156                                                r1.x >= r2.x - dx &&
157                                                r1.y >= r2.y - dy &&
158                                                r1.x + r1.width <= r2.x + r2.width + dx &&
159                                                r1.y + r1.height <= r2.y + r2.height + dy &&
160                                                (n2 > Math.max(3, n1) || n1 < 3))
161                                        break;
162                        }
163
164                        if (j == nClasses) {
165                                rectList.add(new ObjectIntPair<Rectangle>(r1, n1));
166                        }
167                }
168
169                return rectList;
170        }
171
172        private int partition(List<Rectangle> rects, int[] classes) {
173                int numClasses = 0;
174
175                for (int i = 0; i < rects.size(); i++) {
176                        boolean found = false;
177                        for (int j = 0; j < i; j++) {
178                                if (equals(rects.get(j), rects.get(i))) {
179                                        found = true;
180                                        classes[i] = classes[j];
181                                }
182                        }
183                        if (!found) {
184                                classes[i] = numClasses;
185                                numClasses++;
186                        }
187                }
188
189                return numClasses;
190        }
191
192        private boolean equals(Rectangle r1, Rectangle r2) {
193                final float delta = eps * (Math.min(r1.width, r2.width) + Math.min(r1.height, r2.height)) * 0.5f;
194
195                return (Math.abs(r1.x - r2.x) <= delta &&
196                                        Math.abs(r1.y - r2.y) <= delta &&
197                                        Math.abs(r1.x + r1.width - r2.x - r2.width) <= delta && Math.abs(r1.y + r1.height - r2.y - r2.height) <= delta);
198        }
199}