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 ******************************************************************************/ 009package imagingbook.common.image; 010 011import ij.process.ImageProcessor; 012import imagingbook.common.geometry.basic.Pnt2d; 013import imagingbook.common.util.ClassUtils; 014import imagingbook.common.util.SortedVector; 015 016import java.util.Comparator; 017import java.util.Locale; 018 019/** 020 * <p> 021 * Provides methods for detecting local maxima or minima in images or 2D data arrays. A local maximum (minimum) is 022 * defined as a pixel position whose value is larger (smaller) than all its eight neighboring values. The detection is 023 * controlled by a 'threshold' parameter specifying the minimum difference between the center value and the surrounding 024 * values. There is also a 'borderWidth' parameter specifying the outer image margins to be ignored. This implementation 025 * deliberately provides separate methods {@link #getMaxima(int)} and {@link #getMinima(int)} for detecting maxima and 026 * minim, respectively. An alternative would be to have only one method and invert the data to obtain the other, but 027 * inversion of float-data is not well defined and we wanted the original data values preserved with the returned point 028 * sets. (This may change eventually.) 029 * </p> 030 * <p> 031 * Note that this form of local extremum detection is simple but may fail on ridge points or locally flat spots. See 032 * {@link ij.plugin.filter.MaximumFinder} for a more robust (but also more complicated) implementation. 033 * </p> 034 */ 035public class LocalMinMaxFinder { 036 037 private final int W, H; 038 private final float threshold; 039 private final int borderWidth; 040 private final float[][] fpixels; 041 private final float[] nh = new float[9]; 042 043 /** 044 * Constructor accepting a 2D data array of type float. 045 * 046 * @param fpixels the 2D data array 047 * @param threshold the minimum difference between a center value and its 8 surrounding values to be accepted as a 048 * local extremum 049 * @param borderWidth width of border margin to be ignored (> 0) 050 */ 051 public LocalMinMaxFinder(float[][] fpixels, double threshold, int borderWidth) { 052 this.fpixels = fpixels; 053 this.W = fpixels.length; 054 this.H = fpixels[0].length; 055 this.threshold = (float) threshold; 056 this.borderWidth = Math.max(1, borderWidth); 057 } 058 059 /** 060 * Constructor accepting an {@link ImageProcessor} instance. Color images are converted to scalar float values for 061 * extremum detection. 062 * 063 * @param ip the input image 064 * @param threshold the minimum difference between a center value and its 8 surrounding values to be accepted as a 065 * local extremum 066 * @param borderWidth width of border margin to be ignored 067 */ 068 public LocalMinMaxFinder(ImageProcessor ip, double threshold, int borderWidth) { 069 this(ip.getFloatArray(), threshold, borderWidth); 070 } 071 072 /** 073 * Constructor accepting an {@link ImageProcessor} instance using default parameters. 074 * @param ip the input image 075 */ 076 public LocalMinMaxFinder(ImageProcessor ip) { 077 this(ip, 0.0, 0); 078 } 079 080 081 // -------------------------------------------------------------------- 082 083 /** 084 * Returns the detected local maxima as an array of type {@link ExtremalPoint}. The resulting array is sorted such 085 * that the position with the maximum score value ({@link ExtremalPoint#q}) comes first. The array is never larger 086 * than the specified count. 087 * 088 * @param maxCount the maximum number of extrema to search for 089 * @return a sorted array of {@link ExtremalPoint} instances 090 */ 091 public ExtremalPoint[] getMaxima(int maxCount) { 092 Comparator<ExtremalPoint> cprt = ClassUtils.getComparator(ExtremalPoint.class); 093 SortedVector<ExtremalPoint> sv = new SortedVector(new ExtremalPoint[maxCount], cprt); 094 for (int v = borderWidth; v < H - borderWidth; v++) { 095 for (int u = borderWidth; u < W - borderWidth; u++) { 096 if (getNeighborhood(u, v) && isLocalMax(threshold)) { 097 ExtremalPoint p = new ExtremalPoint(u, v, nh[0]); 098 sv.add(p); 099 // System.out.println("adding max " + p + ": " + Arrays.toString(sv.getArray())); 100 } 101 } 102 } 103 return sv.getArray(); 104 } 105 106 /** 107 * Returns the detected local minima as an array of type {@link ExtremalPoint}. The resulting array is sorted such 108 * that the position with the minimum score value ({@link ExtremalPoint#q}) comes first. The array is never larger 109 * than the specified count. 110 * 111 * @param maxCount the maximum number of extrema to search for 112 * @return a sorted array of {@link ExtremalPoint} instances 113 */ 114 public ExtremalPoint[] getMinima(int maxCount) { 115 Comparator<ExtremalPoint> cprt = ClassUtils.getComparator(ExtremalPoint.class).reversed(); 116 SortedVector<ExtremalPoint> sv = new SortedVector(new ExtremalPoint[maxCount], cprt); 117 for (int v = borderWidth; v < H - borderWidth; v++) { 118 for (int u = borderWidth; u < W - borderWidth; u++) { 119 if (getNeighborhood(u, v) && isLocalMin(threshold)) { 120 ExtremalPoint p = new ExtremalPoint(u, v, nh[0]); 121 sv.add(p); 122 // System.out.println("adding min " + p + ": " + Arrays.toString(sv.getArray())); 123 } 124 } 125 } 126 return sv.getArray(); 127 } 128 129 /** 130 * Fills the neighborhood array s as follows: 131 * <pre> 132 * s4 s3 s2 133 * s5 s0 s1 134 * s6 s7 s8 135 * </pre> 136 * Returns true of the neighborhood could be filled completely, false otherwise. 137 */ 138 private boolean getNeighborhood(int u, int v) { 139 if (u <= 0 || u >= W - 1 || v <= 0 || v >= H - 1) { 140 return false; 141 } 142 else { 143 final float[][] q = this.fpixels; 144 nh[0] = q[u][v]; 145 nh[1] = q[u+1][v]; 146 nh[2] = q[u+1][v-1]; 147 nh[3] = q[u][v-1]; 148 nh[4] = q[u-1][v-1]; 149 nh[5] = q[u-1][v]; 150 nh[6] = q[u-1][v+1]; 151 nh[7] = q[u][v+1]; 152 nh[8] = q[u+1][v+1]; 153 return true; 154 } 155 } 156 157 private boolean isLocalMax(float threshold) { 158 if (nh == null) { 159 return false; 160 } 161 else { 162 final float nh0 = nh[0] - threshold; 163 return // check 8 neighbors of q0 164 nh0 > nh[4] && nh0 > nh[3] && nh0 > nh[2] && 165 nh0 > nh[5] && nh0 > nh[1] && 166 nh0 > nh[6] && nh0 > nh[7] && nh0 > nh[8] ; 167 } 168 } 169 170 private boolean isLocalMin(float threshold) { 171 if (nh == null) { 172 return false; 173 } 174 else { 175 final float nh0 = nh[0] + threshold; 176 return // check 8 neighbors of q0 177 nh0 < nh[4] && nh0 < nh[3] && nh0 < nh[2] && 178 nh0 < nh[5] && nh0 < nh[1] && 179 nh0 < nh[6] && nh0 < nh[7] && nh0 < nh[8] ; 180 } 181 } 182 183 // ---------------------------------------------------------------------- 184 185 /** 186 * A 2D point with integer coordinates and a score value ({@link #q}) attached. 187 */ 188 public static class ExtremalPoint extends Pnt2d.PntInt implements Comparable<ExtremalPoint> { 189 190 /** The score value. */ 191 public final float q; 192 193 /** 194 * Constructor. 195 * @param x horizontal position 196 * @param y vertical position 197 * @param q score value 198 */ 199 public ExtremalPoint(int x, int y, float q) { 200 super(x, y); 201 this.q = q; 202 } 203 204 @Override 205 public int compareTo(ExtremalPoint other) { 206 // sort by increasing score value 207 return Float.compare(this.q, other.q); 208 } 209 210 private static final String ClassName = ExtremalPoint.class.getSimpleName(); 211 212 @Override 213 public String toString() { 214 return String.format(Locale.US, "%s[%d, %d, q=%.3f]", ClassName, x, y, q); 215 } 216 } 217 218}