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.haar;
031
032import java.util.ArrayList;
033import java.util.List;
034
035import org.openimaj.citation.annotation.Reference;
036import org.openimaj.citation.annotation.ReferenceType;
037import org.openimaj.image.FImage;
038import org.openimaj.image.analysis.algorithm.SummedSqTiltAreaTable;
039import org.openimaj.image.objectdetection.AbstractMultiScaleObjectDetector;
040import org.openimaj.math.geometry.shape.Rectangle;
041
042/**
043 * Basic, single-threaded multi-scale Haar cascade/tree object detector. The
044 * detector determines a range of scales to search based on an optional minimum
045 * and maximum detection size (if not specified, minimum is the size of the
046 * {@link StageTreeClassifier} and maximum is the image size), and a
047 * scale-factor which determines the amount to change between scales. At a given
048 * scale, the entire image is searched. In order to speed-up detection, if no
049 * detection is made for a given (x, y) coordinate, the x-ordinate position is
050 * incremented by {@link #bigStep()}, otherwise it is incremented by
051 * {@link #smallStep()}.
052 * <p>
053 * <strong>Important note:</strong> This detector is NOT thread-safe due to the
054 * fact that {@link StageTreeClassifier}s are not themselves thread-safe. Do not
055 * attempt to use it in a multi-threaded environment!
056 * 
057 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
058 */
059@Reference(
060                type = ReferenceType.Inproceedings,
061                author = { "Viola, P.", "Jones, M." },
062                title = "Rapid object detection using a boosted cascade of simple features",
063                year = "2001",
064                booktitle = "Computer Vision and Pattern Recognition, 2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on",
065                pages = { " I", "511 ", " I", "518 vol.1" },
066                number = "",
067                volume = "1",
068                customData = {
069                                "keywords", " AdaBoost; background regions; boosted simple feature cascade; classifiers; face detection; image processing; image representation; integral image; machine learning; object specific focus-of-attention mechanism; rapid object detection; real-time applications; statistical guarantees; visual object detection; feature extraction; image classification; image representation; learning (artificial intelligence); object detection;",
070                                "doi", "10.1109/CVPR.2001.990517",
071                                "ISSN", "1063-6919 "
072                })
073public class Detector extends AbstractMultiScaleObjectDetector<FImage, Rectangle> {
074        /**
075         * Default step size to make when there is a hint of detection.
076         */
077        public static final int DEFAULT_SMALL_STEP = 1;
078
079        /**
080         * Default step size to make when there is definitely no detection.
081         */
082        public static final int DEFAULT_BIG_STEP = 2;
083
084        /**
085         * Default scale factor multiplier.
086         */
087        public static final float DEFAULT_SCALE_FACTOR = 1.1f;
088
089        protected StageTreeClassifier cascade;
090        protected float scaleFactor = 1.1f;
091        protected int smallStep = 1;
092        protected int bigStep = 2;
093
094        /**
095         * Construct the {@link Detector} with the given parameters.
096         * 
097         * @param cascade
098         *            the cascade or tree of stages.
099         * @param scaleFactor
100         *            the amount to change between scales (multiplicative)
101         * @param smallStep
102         *            the amount to step when there is a hint of detection
103         * @param bigStep
104         *            the amount to step when there is definitely no detection
105         */
106        public Detector(StageTreeClassifier cascade, float scaleFactor, int smallStep, int bigStep) {
107                super(Math.max(cascade.width, cascade.height), 0);
108
109                this.cascade = cascade;
110                this.scaleFactor = scaleFactor;
111                this.smallStep = smallStep;
112                this.bigStep = bigStep;
113        }
114
115        /**
116         * Construct the {@link Detector} with the given tree of stages and scale
117         * factor. The default step sizes are used.
118         * 
119         * @param cascade
120         *            the cascade or tree of stages.
121         * @param scaleFactor
122         *            the amount to change between scales
123         */
124        public Detector(StageTreeClassifier cascade, float scaleFactor) {
125                this(cascade, scaleFactor, DEFAULT_SMALL_STEP, DEFAULT_BIG_STEP);
126        }
127
128        /**
129         * Construct the {@link Detector} with the given tree of stages, and the
130         * default parameters for step sizes and scale factor.
131         * 
132         * @param cascade
133         *            the cascade or tree of stages.
134         */
135        public Detector(StageTreeClassifier cascade) {
136                this(cascade, DEFAULT_SCALE_FACTOR, DEFAULT_SMALL_STEP, DEFAULT_BIG_STEP);
137        }
138
139        /**
140         * Perform detection at a single scale. Subclasses may override this to
141         * customise the spatial search. The given starting and stopping coordinates
142         * take into account any region of interest set on this detector.
143         * 
144         * @param sat
145         *            the summed area table(s)
146         * @param startX
147         *            the starting x-ordinate
148         * @param stopX
149         *            the stopping x-ordinate
150         * @param startY
151         *            the starting y-ordinate
152         * @param stopY
153         *            the stopping y-ordinate
154         * @param ystep
155         *            the amount to step
156         * @param windowWidth
157         *            the window width at the current scale
158         * @param windowHeight
159         *            the window height at the current scale
160         * @param results
161         *            the list to store detection results in
162         */
163        protected void detectAtScale(final SummedSqTiltAreaTable sat, final int startX, final int stopX, final int startY,
164                        final int stopY, final float ystep, final int windowWidth, final int windowHeight,
165                        final List<Rectangle> results)
166        {
167                for (int iy = startY; iy < stopY; iy++) {
168                        final int y = Math.round(iy * ystep);
169
170                        for (int ix = startX, xstep = 0; ix < stopX; ix += xstep) {
171                                final int x = Math.round(ix * ystep);
172
173                                final int result = cascade.classify(sat, x, y);
174
175                                if (result > 0) {
176                                        results.add(new Rectangle(x, y, windowWidth, windowHeight));
177                                }
178
179                                // if there is no detection, then increase the step size
180                                xstep = (result > 0 ? smallStep : bigStep);
181
182                                // TODO: think about what to do if there isn't a detection, but
183                                // we're very close to having one based on the ratio of stages
184                                // passes to total stages.
185                        }
186                }
187        }
188
189        @Override
190        public List<Rectangle> detect(FImage image) {
191                final List<Rectangle> results = new ArrayList<Rectangle>();
192
193                final int imageWidth = image.getWidth();
194                final int imageHeight = image.getHeight();
195
196                final SummedSqTiltAreaTable sat = new SummedSqTiltAreaTable(image, cascade.hasTiltedFeatures);
197
198                // compute the number of scales to test and the starting factor
199                int nFactors = 0;
200                int startFactor = 0;
201                for (float factor = 1; factor * cascade.width < imageWidth - 10 &&
202                                factor * cascade.height < imageHeight - 10; factor *= scaleFactor)
203                {
204                        final float width = factor * cascade.width;
205                        final float height = factor * cascade.height;
206
207                        if (width < minSize || height < minSize) {
208                                startFactor++;
209                        }
210
211                        if (maxSize > 0 && (width > maxSize || height > maxSize)) {
212                                break;
213                        }
214
215                        nFactors++;
216                }
217
218                // run the detection at each scale
219                float factor = (float) Math.pow(scaleFactor, startFactor);
220                for (int scaleStep = startFactor; scaleStep < nFactors; factor *= scaleFactor, scaleStep++) {
221                        final float ystep = Math.max(2, factor);
222
223                        final int windowWidth = (int) (factor * cascade.width);
224                        final int windowHeight = (int) (factor * cascade.height);
225
226                        // determine the spatial range, taking into account any ROI.
227                        final int startX = (int) (roi == null ? 0 : Math.max(0, roi.x));
228                        final int startY = (int) (roi == null ? 0 : Math.max(0, roi.y));
229                        final int stopX = Math.round(
230                                        (((roi == null ? imageWidth : Math.min(imageWidth, roi.x + roi.width)) - windowWidth)) / ystep);
231                        final int stopY = Math.round(
232                                        (((roi == null ? imageHeight : Math.min(imageHeight, roi.y + roi.height)) - windowHeight)) / ystep);
233
234                        // prepare the cascade for this scale
235                        cascade.setScale(factor);
236
237                        detectAtScale(sat, startX, stopX, startY, stopY, ystep, windowWidth, windowHeight, results);
238                }
239
240                return results;
241        }
242
243        /**
244         * Get the step size the detector will make if there is any hint of a
245         * detection. This should be smaller than {@link #bigStep()}.
246         * 
247         * @return the amount to step on any hint of detection.
248         */
249        public int smallStep() {
250                return smallStep;
251        }
252
253        /**
254         * Get the step size the detector will make if there is definitely no
255         * detection. This should be bigger than {@link #smallStep()}.
256         * 
257         * @return the amount to step when there is definitely no detection.
258         */
259        public int bigStep() {
260                return bigStep;
261        }
262
263        /**
264         * Set the step size the detector will make if there is any hint of a
265         * detection. This should be smaller than {@link #bigStep()}.
266         * 
267         * @param smallStep
268         *            The amount to step on any hint of detection.
269         */
270        public void setSmallStep(int smallStep) {
271                this.smallStep = smallStep;
272        }
273
274        /**
275         * Set the step size the detector will make if there is definitely no
276         * detection. This should be bigger than {@link #smallStep()}.
277         * 
278         * @param bigStep
279         *            The amount to step when there is definitely no detection.
280         */
281        public void bigStep(int bigStep) {
282                this.bigStep = bigStep;
283        }
284
285        /**
286         * Get the scale factor (the amount to change between scales
287         * (multiplicative)).
288         * 
289         * @return the scaleFactor
290         */
291        public float getScaleFactor() {
292                return scaleFactor;
293        }
294
295        /**
296         * Set the scale factor (the amount to change between scales
297         * (multiplicative)).
298         * 
299         * @param scaleFactor
300         *            the scale factor to set
301         */
302        public void setScaleFactor(float scaleFactor) {
303                this.scaleFactor = scaleFactor;
304        }
305
306        /**
307         * Get the classifier tree or cascade used by this detector.
308         * 
309         * @return the classifier tree or cascade.
310         */
311        public StageTreeClassifier getClassifier() {
312                return cascade;
313        }
314}