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.detector.dog.extractor;
031
032import gnu.trove.list.array.TFloatArrayList;
033
034import org.openimaj.image.FImage;
035import org.openimaj.image.feature.local.extraction.GradientScaleSpaceImageExtractorProperties;
036
037/**
038 * Extract the dominant orientations of a scale-space interest point by
039 * looking for peaks in its orientation histogram. 
040 * 
041 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
042 */
043public class DominantOrientationExtractor extends AbstractDominantOrientationExtractor {
044        /**
045         * Default value for the threshold at which other peaks are detected
046         * relative to the biggest peak. Lowe's IJCV paper suggests a
047         * value of 80%.
048         */
049        public static float DEFAULT_PEAK_THRESHOLD = 0.8f;
050        
051        protected OrientationHistogramExtractor oriHistExtractor;
052        
053        /**
054         * Threshold for peak detection. A value of 1.0 would
055         * result in only a single peak being detected.
056         */
057        protected float peakThreshold;
058        
059        /**
060         * Construct with default values.
061         */
062        public DominantOrientationExtractor() {
063                this(DEFAULT_PEAK_THRESHOLD, new OrientationHistogramExtractor());
064        }
065        
066        /**
067         * Construct with given parameters.
068         * @param peakThreshold threshold at which other peaks are detected relative to the biggest peak
069         * @param oriHistExtractor the orientation histogram extractor
070         */
071        public DominantOrientationExtractor(float peakThreshold, OrientationHistogramExtractor oriHistExtractor) {
072                this.peakThreshold = peakThreshold;
073                this.oriHistExtractor = oriHistExtractor;
074        }
075        
076        /**
077         * Extract an orientation histogram and find the dominant orientations
078         * by looking for peaks.
079         * 
080         * @param properties Properties describing the interest point in scale space.
081         * @return an array of the angles of the dominant orientations [-PI to PI].
082         */
083        @Override
084        public float [] extractFeatureRaw(GradientScaleSpaceImageExtractorProperties<FImage> properties) {
085                //extract histogram
086                float[] hist = getOriHistExtractor().extractFeatureRaw(properties);
087                
088                //find max
089                float maxval = 0;
090                for (int i = 0; i < getOriHistExtractor().numBins; i++)
091                        if (hist[i] > maxval)
092                                maxval = hist[i];
093
094                float thresh = peakThreshold * maxval;
095                
096                //search for peaks within peakThreshold of the maximum
097                TFloatArrayList dominantOrientations = new TFloatArrayList();
098                for (int i = 0; i < getOriHistExtractor().numBins; i++) {
099                        float prevVal = hist[(i == 0 ? getOriHistExtractor().numBins - 1 : i - 1)];
100                        float nextVal = hist[(i == getOriHistExtractor().numBins - 1 ? 0 : i + 1)];
101                        float thisVal = hist[i];
102                        
103                        if (thisVal >= thresh && thisVal > prevVal && thisVal > nextVal) {
104                                //fit a parabola to the peak to find the position of the actual maximum
105                                float peakDelta = fitPeak(prevVal, thisVal, nextVal);
106                                float angle = 2.0f * (float)Math.PI * (i + 0.5f + peakDelta) / getOriHistExtractor().numBins - (float)Math.PI;
107                                
108                                dominantOrientations.add(angle);
109                        }
110                }
111
112                return dominantOrientations.toArray();
113        }
114        
115        /**
116         * Fit a parabola to three evenly spaced samples and return the relative
117         * position of the peak to the second sample. 
118         */
119        float fitPeak(float a, float b, float c) {
120                //a is at x=-1, b at x=0, c at x=1
121                //y = A*x*x + B*x + C
122                //y' = 2*A*x + B
123                //solve for A,B,C then for x where y'=0
124                
125                return 0.5f * (a - c) / (a - 2.0f * b + c);
126        }
127
128
129        /**
130         * @return the orientation histogram extractor
131         */
132        public OrientationHistogramExtractor getOriHistExtractor() {
133                return oriHistExtractor;
134        }
135}