001/******************************************************************************* 002 * This software is provided as a supplement to the authors' textbooks on digital 003 * image processing published by Springer-Verlag in various languages and editions. 004 * Permission to use and distribute this software is granted under the BSD 2-Clause 005 * "Simplified" License (see http://opensource.org/licenses/BSD-2-Clause). 006 * Copyright (c) 2006-2023 Wilhelm Burger, Mark J. Burge. All rights reserved. 007 * Visit https://imagingbook.com for additional details. 008 ******************************************************************************/ 009 010package imagingbook.common.corners; 011 012import ij.process.FloatProcessor; 013import ij.process.ImageProcessor; 014import imagingbook.common.corners.SubpixelMaxInterpolator.Method; 015import imagingbook.common.filter.linear.GaussianFilterSeparable; 016import imagingbook.common.filter.linear.LinearFilterSeparable; 017import imagingbook.common.ij.DialogUtils; 018import imagingbook.common.image.ImageMath; 019import imagingbook.common.util.ParameterBundle; 020 021import java.util.ArrayList; 022import java.util.Collections; 023import java.util.List; 024 025import static imagingbook.common.ij.IjUtils.convolveX; 026import static imagingbook.common.ij.IjUtils.convolveY; 027import static imagingbook.common.math.Arithmetic.sqr; 028 029/** 030 * <p> 031 * Abstract super class for all corner detectors based on the local structure matrix (tensor). See Ch. 6 of [1] for 032 * details. 033 * </p> 034 * <p> 035 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing – An Algorithmic Introduction</em>, 3rd ed, Springer 036 * (2022). 037 * </p> 038 * 039 * @author WB 040 * @version 2022/03/30 041 * @see HarrisCornerDetector 042 * @see MopsCornerDetector 043 * @see ShiTomasiCornerDetector 044 */ 045public abstract class GradientCornerDetector { 046 047 /** For testing/example calculations only! */ 048 public static boolean RETAIN_TEMPORARY_DATA = false; 049 050 public static class Parameters implements ParameterBundle<GradientCornerDetector> { 051 @DialogUtils.DialogLabel("Apply pre-filter") 052 public boolean doPreFilter = true; 053 054 @DialogUtils.DialogLabel("Gaussian smoothing radius (\u03C3)")@DialogUtils.DialogDigits(3) 055 public double sigma = 1.275; 056 057 @DialogUtils.DialogLabel("Border margins") 058 public int border = 20; // TODO: replace 'border' by ROI rectangle 059 060 @DialogUtils.DialogLabel("Clean up corners") 061 public boolean doCleanUp = true; 062 063 @DialogUtils.DialogLabel("Min. distance between final corners")@DialogUtils.DialogDigits(1) 064 public double dmin = 10; 065 066 @DialogUtils.DialogLabel("Subpixel positioning method") 067 public Method maxLocatorMethod = Method.None; 068 069 @DialogUtils.DialogLabel("Corner response threshold (th)")@DialogUtils.DialogDigits(1) 070 public double scoreThreshold = 100; 071 072 @Override 073 public boolean validate() { 074 return sigma > 0 && border >= 0 && dmin >= 0 && scoreThreshold > 0; 075 } 076 } 077 078 protected static final float UndefinedScoreValue = 0; // to be returned when corner score is undefined 079 080 //filter kernels (one-dim. part of separable 2D filters) 081 private final static float[] hp = {2f/9, 5f/9, 2f/9}; // pre-smoothing filter kernel 082 private final static float[] hd = {0.5f, 0, -0.5f}; // first-derivative kernel 083// private final static float[] hb = {1f/64, 6f/64, 15f/64, 20f/64, 15f/64, 6f/64, 1f/64}; // original gradient blur filter kernel 084 085 protected final int M, N; 086 protected final Parameters params; 087 protected final FloatProcessor Q; 088 089 private final SubpixelMaxInterpolator maxLocator; 090// private final List<Corner> corners; 091 092 // retained mainly for debugging 093 private FloatProcessor A = null; 094 private FloatProcessor B = null; 095 private FloatProcessor C = null; 096 097 // --------------------------------------------------------------------------- 098 099 protected GradientCornerDetector(ImageProcessor ip, Parameters params) { 100 this.M = ip.getWidth(); 101 this.N = ip.getHeight(); 102 this.params = params; 103 this.maxLocator = params.maxLocatorMethod.getInstance(); 104 //(params.maxLocatorMethod == Method.None) ? null : 105 //SubpixelMaxInterpolator.getInstance(params.maxLocatorMethod); 106 this.Q = makeCornerScores(ip); 107 } 108 109 /** 110 * Calculates the corner response score for a single image position (u,v) from the elements A, B, C of the local 111 * structure matrix. The method should normalize the score value, such that 100 is returned for the default 112 * threshold value. To be implemented by concrete sub-classes. 113 * 114 * @param A = Ixx(u,v) 115 * @param B = Iyy(u,v) 116 * @param C = Ixy(u,v) 117 * @return the corner score 118 * @see HarrisCornerDetector 119 * @see ShiTomasiCornerDetector 120 */ 121 protected abstract float getCornerScore(float A, float B, float C); 122 123 // ------------------------------------------------------------- 124 125 private FloatProcessor makeCornerScores(ImageProcessor I) { 126 FloatProcessor Ix = I.convertToFloatProcessor(); 127 FloatProcessor Iy = (FloatProcessor) Ix.duplicate(); 128 129 // nothing really but a Sobel-type gradient: TODO: replace by LinearFilter 130 if (params.doPreFilter) { 131 convolveY(Ix, hp); // pre-filter Ix vertically 132 convolveX(Iy, hp); // pre-filter Iy horizontally 133 } 134 135 convolveX(Ix, hd); // get first derivative in x 136 convolveY(Iy, hd); // get first derivative in y 137 138 // gradient products: 139 A = ImageMath.sqr(Ix); // A(u,v) = Ixx(u,v) = (Ix(u,v))^2 140 B = ImageMath.sqr(Iy); // B(u,v) = Iyy(u,v) = (Iy(u,v))^2 141 C = ImageMath.mult(Ix, Iy); // C(u,v) = Ixy(u,v) = Ix(u,v)*Iy(u,v) 142 143 // blur the gradient components with a small Gaussian: 144 LinearFilterSeparable gf = new GaussianFilterSeparable(params.sigma); 145 gf.applyTo(A); 146 gf.applyTo(B); 147 gf.applyTo(C); 148 149 FloatProcessor Q = new FloatProcessor(M, N); 150 151 final float[] pA = (float[]) A.getPixels(); 152 final float[] pB = (float[]) B.getPixels(); 153 final float[] pC = (float[]) C.getPixels(); 154 final float[] pQ = (float[]) Q.getPixels(); 155 156 for (int i = 0; i < M * N; i++) { 157 pQ[i] = getCornerScore(pA[i], pB[i], pC[i]); 158 } 159 160 return Q; 161 } 162 163 164 /** 165 * Returns the corner score function as a {@link FloatProcessor} object. 166 * @return the score function 167 */ 168 public FloatProcessor getQ() { 169 return this.Q; 170 } 171 172 public FloatProcessor getA() { 173 return this.A; 174 } 175 176 public FloatProcessor getB() { 177 return this.B; 178 } 179 180 public FloatProcessor getC() { 181 return this.C; 182 } 183 184 public List<Corner> getCorners() { 185 List<Corner> cl = collectCorners(params.scoreThreshold, params.border); 186 if (params.doCleanUp) { 187 cl = cleanupCorners(cl); 188 } 189 return cl; 190 } 191 192 // ---------------------------------------------------------- 193 194 /* 195 * Returned samples are arranged as follows: 196 * s4 s3 s2 197 * s5 s0 s1 198 * s6 s7 s8 199 */ 200 private float[] getNeighborhood(FloatProcessor Q, int u, int v) { 201 if (u <= 0 || u >= M - 1 || v <= 0 || v >= N - 1) { 202 return null; 203 } 204 else { 205 final float[] q = (float[]) Q.getPixels(); 206 float[] s = new float[9]; 207 final int i0 = (v - 1) * M + u; 208 final int i1 = v * M + u; 209 final int i2 = (v + 1) * M + u; 210 s[0] = q[i1]; 211 s[1] = q[i1 + 1]; 212 s[2] = q[i0 + 1]; 213 s[3] = q[i0]; 214 s[4] = q[i0 - 1]; 215 s[5] = q[i1 - 1]; 216 s[6] = q[i2 - 1]; 217 s[7] = q[i2]; 218 s[8] = q[i2 + 1]; 219 return s; 220 } 221 } 222 223 private boolean isLocalMax(float[] s) { 224 if (s == null) { 225 return false; 226 } 227 else { 228 final float s0 = s[0]; 229 return // check 8 neighbors of q0 230 s0 > s[4] && s0 > s[3] && s0 > s[2] && 231 s0 > s[5] && s0 > s[1] && 232 s0 > s[6] && s0 > s[7] && s0 > s[8] ; 233 } 234 } 235 236 private List<Corner> collectCorners(double scoreThreshold, int borderWidth) { 237 float th = (float) scoreThreshold; //params.scoreThreshold; 238 //int border = params.border; 239 List<Corner> C = new ArrayList<>(); 240 for (int v = borderWidth; v < N - borderWidth; v++) { 241 for (int u = borderWidth; u < M - borderWidth; u++) { 242 float[] qn = getNeighborhood(Q, u, v); 243 if (qn != null && qn[0] > th && isLocalMax(qn)) { 244 Corner c = makeCorner(u, v, qn); 245 if (c != null) { 246 C.add(c); 247 } 248 } 249 } 250 } 251 return C; 252 } 253 254 private List<Corner> cleanupCorners(List<Corner> C) { 255 final double dmin2 = sqr(params.dmin); 256 // sort corners by descending q-value: 257 Collections.sort(C); 258 // we use an array of corners for efficiency reasons: 259 Corner[] Ca = C.toArray(new Corner[C.size()]); 260 List<Corner> Cclean = new ArrayList<>(C.size()); 261 for (int i = 0; i < Ca.length; i++) { 262 Corner c0 = Ca[i]; // get next strongest corner 263 if (c0 != null) { 264 Cclean.add(c0); 265 // delete all remaining corners cj too close to c0: 266 for (int j = i + 1; j < Ca.length; j++) { 267 Corner cj = Ca[j]; 268 if (cj != null && c0.distanceSq(cj) < dmin2) 269 Ca[j] = null; //delete corner cj from C 270 } 271 } 272 } 273 return Cclean; 274 } 275 276 /** 277 * Creates a new {@link Corner} instance. Performs sub-pixel position refinement if a {@link #maxLocator} is 278 * defined. 279 * 280 * @param u the corner's horizontal position (int) 281 * @param v the corner's vertical position (int) 282 * @param qn the 9 corner scores in the 3x3 neighborhood 283 * @return a new {@link Corner} instance 284 */ 285 private Corner makeCorner(int u, int v, float[] qn) { 286 if (maxLocator == null) { 287 // no sub-pixel refinement, use original integer coordinates 288 return new Corner(u, v, qn[0]); 289 } 290 else { 291 // do sub-pixel refinement 292 float[] xyz = maxLocator.getMax(qn); 293 return (xyz == null) ? null : new Corner(u + xyz[0], v + xyz[1], xyz[2]); 294 } 295 } 296 297 298}