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 approach in 039 * Section 4 of Lowe's IJCV paper (minus the bit on using Brown's interpolation 040 * 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 a 046 * threshold (i.e. the point is not on a straight line, and has a certain amount 047 * of curvature).</li> 048 * </ul> 049 * 050 * <p> 051 * The AbstractOctaveExtremaFinder uses an event listener paradigm. Once 052 * interest points are found, the internal listener will be informed. 053 * </p> 054 * 055 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 056 * 057 * @param <OCTAVE> 058 */ 059public abstract class AbstractOctaveExtremaFinder<OCTAVE extends GaussianOctave<FImage>> 060 extends 061 AbstractOctaveInterestPointFinder<OCTAVE, FImage> 062{ 063 /** The default threshold for the edge response Eigenvalue ratio */ 064 public static final float DEFAULT_EIGENVALUE_RATIO = 10.0f; 065 066 // Threshold on the ratio of the Eigenvalues of the Hessian matrix (Lowe 067 // IJCV, p.12) 068 protected float eigenvalueRatio = DEFAULT_EIGENVALUE_RATIO; 069 070 /** 071 * Construct an AbstractOctaveExtremaFinder with the default Eigenvalue 072 * ratio threshold. 073 */ 074 public AbstractOctaveExtremaFinder() { 075 this(DEFAULT_EIGENVALUE_RATIO); 076 } 077 078 /** 079 * Construct an AbstractOctaveExtremaFinder with the given Eigenvalue ratio 080 * threshold. 081 * 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 final FImage[] images = octave.images; 105 final int height = images[0].height; 106 final int width = images[0].width; 107 final 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 final 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 { 121 processExtrema(images, currentScaleIndex, x, y, octave.octaveSize); 122 } 123 } 124 } 125 } 126 } 127 128 /** 129 * Perform the first of the checks that determine whether a point is a valid 130 * interest point. This can be overridden to allow for cheaper tests to 131 * occur before more expensive ones. 132 * 133 * @param val 134 * the value at the point. 135 * @param x 136 * the x-coordinate of the point. 137 * @param y 138 * the y-coordinate of the point. 139 * @param scaleIndex 140 * the scale index at which the point was found 141 * @param images 142 * the scale images 143 * @return true if the point is potentially an interest point; false 144 * otherwise. 145 */ 146 protected boolean firstCheck(float val, int x, int y, int scaleIndex, FImage[] images) { 147 return true; 148 } 149 150 /** 151 * Called at the start of 152 * {@link AbstractOctaveExtremaFinder#process(OCTAVE)} 153 * 154 * @param octave 155 * the octave being processed 156 */ 157 protected void beforeProcess(OCTAVE octave) { 158 // do nothing 159 } 160 161 /** 162 * Test to see if a point is a local extremum by searching the +/- 1 pixel 163 * neighbourhood in x and y. 164 * 165 * @param val 166 * the value at x,y 167 * @param image 168 * the image to test against 169 * @param x 170 * the x-coordinate 171 * @param y 172 * the y-coordinate 173 * @return true if extremum, false otherwise. 174 */ 175 protected boolean isLocalExtremum(float val, FImage image, int x, int y) { 176 final float pix[][] = image.pixels; 177 178 if (val > 0.0) { 179 for (int yy = y - 1; yy <= y + 1; yy++) 180 for (int xx = x - 1; xx <= x + 1; xx++) 181 if (pix[yy][xx] > val) 182 return false; 183 } else { 184 for (int yy = y - 1; yy <= y + 1; yy++) 185 for (int xx = x - 1; xx <= x + 1; xx++) 186 if (pix[yy][xx] < val) 187 return false; 188 } 189 return true; 190 } 191 192 /** 193 * Test if the pixel at x,y in the image is NOT on an edge. 194 * 195 * @param image 196 * the image 197 * @param x 198 * the x-coordinate 199 * @param y 200 * the y-coordinate 201 * @return true if the pixel is not an edge, false otherwise 202 */ 203 protected boolean isNotEdge(FImage image, int x, int y) { 204 final float pix[][] = image.pixels; 205 206 // estimate Hessian from finite differences 207 final float H00 = pix[y - 1][x] - 2.0f * pix[y][x] + pix[y + 1][x]; 208 final float H11 = pix[y][x - 1] - 2.0f * pix[y][x] + pix[y][x + 1]; 209 final float H01 = ((pix[y + 1][x + 1] - pix[y + 1][x - 1]) - (pix[y - 1][x + 1] - pix[y - 1][x - 1])) / 4.0f; 210 211 // determinant and trace of Hessian 212 final float det = H00 * H11 - H01 * H01; 213 final float trace = H00 + H11; 214 215 final float eigenvalueRatio1 = eigenvalueRatio + 1.0f; 216 217 return (det * eigenvalueRatio1 * eigenvalueRatio1 > eigenvalueRatio * trace * trace); 218 } 219 220 /** 221 * Perform any additional checks on the point, and then inform the listener 222 * that a point has been found. 223 * 224 * @param images 225 * the stack of images in this octave 226 * @param s 227 * the interest-point scale 228 * @param x 229 * the x-coordinate of the interest-point 230 * @param y 231 * the y-coordinate of the interest-point 232 * @param octSize 233 */ 234 protected abstract void processExtrema(FImage[] images, int s, int x, int y, float octSize); 235}