1 /**
2 * Copyright (c) 2011, The University of Southampton and the individual contributors.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification,
6 * are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 *
11 * * Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * * Neither the name of the University of Southampton nor the names of its
16 * contributors may be used to endorse or promote products derived from this
17 * software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
23 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
26 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30 package org.openimaj.image.processing.edges;
31
32 import java.util.ArrayDeque;
33 import java.util.Deque;
34
35 import org.openimaj.image.FImage;
36 import org.openimaj.image.analysis.algorithm.histogram.HistogramAnalyser;
37 import org.openimaj.image.pixel.Pixel;
38 import org.openimaj.image.processing.convolution.FSobel;
39 import org.openimaj.image.processor.SinglebandImageProcessor;
40 import org.openimaj.math.statistics.distribution.Histogram;
41
42 /**
43 * Canny edge detector. Performs the following steps:
44 * <ol>
45 * <li>Gaussian blur with std.dev. sigma</li>
46 * <li>Horizontal and vertical edge detection with Sobel operators</li>
47 * <li>Non-maximum suppression</li>
48 * <li>Hysteresis thresholding</li>
49 * </ol>
50 *
51 * The upper and lower thresholds for the hysteresis thresholding can be
52 * specified manually or automatically chosen based on the histogram of the edge
53 * magnitudes.
54 *
55 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
56 * @author Sina Samangooei (ss@ecs.soton.ac.uk)
57 */
58 public class CannyEdgeDetector implements SinglebandImageProcessor<Float, FImage> {
59 static final float threshRatio = 0.4f;
60
61 float lowThresh = -1;
62 float highThresh = -1;
63 float sigma = 1;
64
65 /**
66 * Default constructor. Sigma is set to 1.0, and the thresholds are chosen
67 * automatically.
68 */
69 public CannyEdgeDetector() {
70 }
71
72 /**
73 * Construct with the give sigma. The thresholds are chosen automatically.
74 *
75 * @param sigma
76 * the amount of initial blurring
77 */
78 public CannyEdgeDetector(float sigma) {
79 this.sigma = sigma;
80 }
81
82 /**
83 * Construct with all parameters set manually.
84 *
85 * @param lowThresh
86 * lower hysteresis threshold.
87 * @param highThresh
88 * upper hysteresis threshold.
89 * @param sigma
90 * the amount of initial blurring.
91 */
92 public CannyEdgeDetector(float lowThresh, float highThresh, float sigma) {
93 if (lowThresh < 0 || lowThresh > 1)
94 throw new IllegalArgumentException("Low threshold must be between 0 and 1");
95 if (highThresh < 0 || highThresh > 1)
96 throw new IllegalArgumentException("High threshold must be between 0 and 1");
97 if (highThresh < lowThresh)
98 throw new IllegalArgumentException("High threshold must be bigger than the lower threshold");
99 if (sigma < 0)
100 throw new IllegalArgumentException("Sigma must be > 0");
101
102 this.lowThresh = lowThresh;
103 this.highThresh = highThresh;
104 this.sigma = sigma;
105 }
106
107 float computeHighThreshold(FImage magnitudes) {
108 final Histogram hist = HistogramAnalyser.getHistogram(magnitudes, 64);
109
110 float cumSum = 0;
111 for (int i = 0; i < 64; i++) {
112 if (cumSum > 0.7 * magnitudes.width * magnitudes.height) {
113 return i / 64f;
114 }
115 cumSum += hist.values[i];
116 }
117
118 return 1f;
119 }
120
121 @Override
122 public void processImage(FImage image) {
123 processImage(image, new FSobel(sigma));
124 }
125
126 /**
127 * Apply non-max suppression and hysteresis thresholding based using the
128 * given {@link FSobel} analyser to generate the gradients. The gradient
129 * maps held by the {@link FSobel} object will be set to the gradients of
130 * the input image after this method returns.
131 *
132 * @param image
133 * the image to process (and write the result to)
134 * @param sobel
135 * the computed gradients
136 */
137 public void processImage(FImage image, FSobel sobel) {
138 image.analyseWith(sobel);
139 processImage(image, sobel.dx, sobel.dy);
140 }
141
142 /**
143 * Apply non-max suppression and hysteresis thresholding based on the given
144 * (Sobel) gradient maps and write the result to the given output image.
145 *
146 * @param output
147 * the output image
148 * @param dx
149 * the x gradients
150 * @param dy
151 * the y gradients
152 */
153 public void processImage(FImage output, FImage dx, FImage dy) {
154 // tmpMags will hold the magnitudes BEFORE suppression
155 final FImage tmpMags = new FImage(dx.width, dx.height);
156 // magnitudes holds the suppressed magnitude image
157 final FImage magnitudes = NonMaximumSuppressionTangent.computeSuppressed(dx, dy, tmpMags);
158 magnitudes.normalise();
159
160 float low = this.lowThresh;
161 float high = this.highThresh;
162 if (high < 0) {
163 // if high has not been set we use a similar approach to matlab to
164 // estimate the thresholds
165 high = computeHighThreshold(tmpMags);
166 low = threshRatio * high;
167 }
168
169 thresholdingTracker(magnitudes, output, low, high);
170 }
171
172 // private void thresholdingTracker(FImage magnitude, FImage output, float
173 // low, float high) {
174 // output.zero();
175 //
176 // for (int y = 0; y < magnitude.height; y++) {
177 // for (int x = 0; x < magnitude.width; x++) {
178 // if (magnitude.pixels[y][x] >= high) {
179 // follow(x, y, magnitude, output, low);
180 // }
181 // }
182 // }
183 // }
184 //
185 // private void follow(int x, int y, FImage magnitude, FImage output, float
186 // thresh) {
187 // final int xstart = Math.max(0, x - 1);
188 // final int xstop = Math.min(x + 2, magnitude.width);
189 // final int ystart = Math.max(0, y - 1);
190 // final int ystop = Math.min(y + 2, magnitude.height);
191 //
192 // for (int yy = ystart; yy < ystop; yy++) {
193 // for (int xx = xstart; xx < xstop; xx++) {
194 // if (magnitude.pixels[yy][xx] >= thresh && output.pixels[yy][xx] != 1) {
195 // output.pixels[yy][xx] = 1;
196 // follow(xx, yy, magnitude, output, thresh);
197 // }
198 // }
199 // }
200 // }
201
202 private void thresholdingTracker(FImage magnitude, FImage output, float low, float high) {
203 output.zero();
204
205 final Deque<Pixel> candidates = new ArrayDeque<Pixel>();
206 for (int y = 0; y < magnitude.height; y++) {
207 for (int x = 0; x < magnitude.width; x++) {
208 if (magnitude.pixels[y][x] >= high && output.pixels[y][x] != 1) {
209 candidates.add(new Pixel(x, y));
210
211 while (!candidates.isEmpty()) {
212 final Pixel current = candidates.pollFirst();
213
214 if (current.x < 0 || current.x > magnitude.width || current.y < 0 || current.y > magnitude.height)
215 continue;
216
217 if (output.pixels[current.y][current.x] == 1)
218 continue;
219
220 if (magnitude.pixels[current.y][current.x] < low)
221 continue;
222
223 output.pixels[current.y][current.x] = 1;
224
225 candidates.add(new Pixel(x - 1, y - 1));
226 candidates.add(new Pixel(x, y - 1));
227 candidates.add(new Pixel(x + 1, y - 1));
228 candidates.add(new Pixel(x - 1, y));
229 candidates.add(new Pixel(x + 1, y));
230 candidates.add(new Pixel(x - 1, y + 1));
231 candidates.add(new Pixel(x, y + 1));
232 candidates.add(new Pixel(x + 1, y + 1));
233 }
234 }
235 }
236 }
237 }
238 }