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.pyramid; 031 032import org.openimaj.image.FImage; 033import org.openimaj.image.analysis.pyramid.Octave; 034import org.openimaj.image.analysis.pyramid.gaussian.GaussianOctave; 035 036/** 037 * <p> 038 * Class for finding extrema within {@link Octave}s using the 039 * approach in Section 4 of Lowe's IJCV paper (minus the bit on 040 * using Brown's interpolation approach to improve localisation). 041 * </p> 042 * Interest points are detected if: 043 * <ul> 044 * <li>They are at a local extremum in scale-space</li> 045 * <li>The ratio of the Eigenvalues of the edge response at the point is above 046 * a threshold (i.e. the point is not on a straight line, and has a certain 047 * amount of curvature). 048 * </li> 049 * </ul> 050 * 051 * <p> 052 * The AbstractOctaveExtremaFinder uses an event listener paradigm. Once 053 * interest points are found, the internal listener will be informed. 054 * </p> 055 * 056 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 057 * 058 * @param <OCTAVE> 059 */ 060public abstract class AbstractOctaveExtremaFinder< 061 OCTAVE extends GaussianOctave<FImage>> 062 extends 063 AbstractOctaveInterestPointFinder<OCTAVE, FImage> 064{ 065 /** The default threshold for the edge response Eigenvalue ratio */ 066 public static final float DEFAULT_EIGENVALUE_RATIO = 10.0f; 067 068 //Threshold on the ratio of the Eigenvalues of the Hessian matrix (Lowe IJCV, p.12) 069 protected float eigenvalueRatio = DEFAULT_EIGENVALUE_RATIO; 070 071 /** 072 * Construct an AbstractOctaveExtremaFinder with the default 073 * Eigenvalue ratio threshold. 074 */ 075 public AbstractOctaveExtremaFinder() { 076 this(DEFAULT_EIGENVALUE_RATIO); 077 } 078 079 /** 080 * Construct an AbstractOctaveExtremaFinder with the given 081 * Eigenvalue ratio threshold. 082 * @param eigenvalueRatio 083 */ 084 public AbstractOctaveExtremaFinder(float eigenvalueRatio) { 085 this.eigenvalueRatio = eigenvalueRatio; 086 } 087 088 @Override 089 public OCTAVE getOctave() { 090 return octave; 091 } 092 093 @Override 094 public int getCurrentScaleIndex() { 095 return currentScaleIndex; 096 } 097 098 @Override 099 public void process(OCTAVE octave) { 100 beforeProcess(octave); 101 102 this.octave = octave; 103 104 FImage[] images = octave.images; 105 int height = images[0].height; 106 int width = images[0].width; 107 int borderDist = octave.options.getBorderPixels(); 108 109 //search through the scale-space images, leaving a border 110 for (currentScaleIndex = 1; currentScaleIndex < images.length - 1; currentScaleIndex++) { 111 for (int y = borderDist; y < height - borderDist; y++) { 112 for (int x = borderDist; x < width - borderDist; x++) { 113 float val = images[currentScaleIndex].pixels[y][x]; 114 115 if (firstCheck(val, x, y, currentScaleIndex, images) && 116 isLocalExtremum(val, images[currentScaleIndex-1], x, y) && 117 isLocalExtremum(val, images[currentScaleIndex], x, y) && 118 isLocalExtremum(val, images[currentScaleIndex+1], x, y) && 119 isNotEdge(images[currentScaleIndex], x, y)) { 120 processExtrema(images, currentScaleIndex, x, y, octave.octaveSize); 121 } 122 } 123 } 124 } 125 } 126 127 /** 128 * Perform the first of the checks that determine whether 129 * a point is a valid interest point. This can be overridden 130 * to allow for cheaper tests to occur before more expensive ones. 131 * 132 * @param val the value at the point. 133 * @param x the x-coordinate of the point. 134 * @param y the y-coordinate of the point. 135 * @param scaleIndex the scale index at which the point was found 136 * @param images the scale images 137 * @return true if the point is potentially an interest point; false otherwise. 138 */ 139 protected boolean firstCheck(float val, int x, int y, int scaleIndex, FImage[] images) { 140 return true; 141 } 142 143 /** 144 * Called at the start of {@link AbstractOctaveExtremaFinder#process(OCTAVE)} 145 * @param octave the octave being processed 146 */ 147 protected void beforeProcess(OCTAVE octave) { 148 //do nothing 149 } 150 151 /** 152 * Test to see if a point is a local extremum by searching 153 * the +/- 1 pixel neighbourhood in x and y. 154 * 155 * @param val the value at x,y 156 * @param image the image to test against 157 * @param x the x-coordinate 158 * @param y the y-coordinate 159 * @return true if extremum, false otherwise. 160 */ 161 protected boolean isLocalExtremum(float val, FImage image, int x, int y) { 162 float pix[][] = image.pixels; 163 164 if (val > 0.0) { 165 for (int yy = y - 1; yy <= y + 1; yy++) 166 for (int xx = x - 1; xx <= x + 1; xx++) 167 if (pix[yy][xx] > val) 168 return false; 169 } else { 170 for (int yy = y - 1; yy <= y + 1; yy++) 171 for (int xx = x - 1; xx <= x + 1; xx++) 172 if (pix[yy][xx] < val) 173 return false; 174 } 175 return true; 176 } 177 178 179 /** 180 * Test if the pixel at x,y in the image is NOT on an edge. 181 * @param image the image 182 * @param x the x-coordinate 183 * @param y the y-coordinate 184 * @return true if the pixel is not an edge, false otherwise 185 */ 186 protected boolean isNotEdge(FImage image, int x, int y) { 187 float pix[][] = image.pixels; 188 189 //estimate Hessian from finite differences 190 float H00 = pix[y - 1][x] - 2.0f * pix[y][x] + pix[y + 1][x]; 191 float H11 = pix[y][x - 1] - 2.0f * pix[y][x] + pix[y][x + 1]; 192 float H01 = ((pix[y + 1][x + 1] - pix[y + 1][x - 1]) - (pix[y - 1][x + 1] - pix[y - 1][x - 1])) / 4.0f; 193 194 //determinant and trace of Hessian 195 float det = H00 * H11 - H01 * H01; 196 float trace = H00 + H11; 197 198 float eigenvalueRatio1 = eigenvalueRatio + 1.0f; 199 200 return (det * eigenvalueRatio1 * eigenvalueRatio1 > eigenvalueRatio * trace * trace); 201 } 202 203 /** 204 * Perform any additional checks on the point, and then inform 205 * the listener that a point has been found. 206 * 207 * @param images the stack of images in this octave 208 * @param s the interest-point scale 209 * @param x the x-coordinate of the interest-point 210 * @param y the y-coordinate of the interest-point 211 * @param octSize 212 */ 213 protected abstract void processExtrema(FImage[] images, int s, int x, int y, float octSize); 214}