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.analysis.algorithm;
31
32 import static java.lang.Math.PI;
33 import static java.lang.Math.cos;
34 import static java.lang.Math.round;
35 import static java.lang.Math.sin;
36 import static java.lang.Math.sqrt;
37
38 import java.util.ArrayList;
39 import java.util.Iterator;
40 import java.util.List;
41
42 import org.openimaj.image.FImage;
43 import org.openimaj.image.analyser.ImageAnalyser;
44 import org.openimaj.image.pixel.FValuePixel;
45 import org.openimaj.math.geometry.line.Line2d;
46 import org.openimaj.math.geometry.point.Point2dImpl;
47
48 /**
49 * Implementation of the Hough Transform for lines as an {@link ImageAnalyser}.
50 * The input image should have the lines to detect zeroed in the image (black).
51 * All other values will be ignored. That means you usually need to invert
52 * images created with edge detectors.
53 * <p><pre>
54 * {@code
55 * CannyEdgeDetector2 ced = new CannyEdgeDetector2();
56 * FImage i = ced.process( ImageUtilities.readF( new File( 'test.jpg' ) );
57 *
58 * HoughLines hl = new HoughLines();
59 * i.inverse().analyse( hl );
60 * double d = hl.calculatePrevailingAngle();
61 * }
62 * </pre>
63 * <p>
64 * The analyser is iterable over the lines that are found within the
65 * accumulator space. Iterated lines will be returned in strength order.
66 * Once an iterator has been created, the object contains a copy of the
67 * accumulator space until {@link #clearIterator()} is called.
68 * You can use the Java 5 for construct:
69 * <pre>
70 * int maxLines = 20;
71 * for( Line2d line: hl ) {
72 * System.out.println( "Line: "+line );
73 * if( --maxLines == 0 )
74 * break;
75 * }
76 * hl.clearIterator();
77 * </pre>
78 * <p>
79 * To convert a bin into a degree, use bin*360d/{@link #getNumberOfSegments()}.
80 * To convert a degree into a bin, use degree/360d/{@link #getNumberOfSegments()}.
81 *
82 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
83 * @author David Dupplaw (dpd@ecs.soton.ac.uk)
84 * @created 8 Aug 2011
85 */
86 public class HoughLines implements
87 ImageAnalyser<FImage>,
88 Iterable<Line2d>,
89 Iterator<Line2d>
90 {
91 /** The accumulator images */
92 private FImage accum = null;
93
94 /** The number of segments in the accumulator space */
95 private int numberOfSegments = 360;
96
97 /**
98 * When the iterator is being used, this contains the accumulator
99 * that is being iterated over. This accumulator will have the lines
100 * that have already been returned via the iterator set to zero.
101 */
102 private FImage iteratorAccum = null;
103
104 /** The current accumulator pixel (line) in the iterator */
105 private FValuePixel iteratorCurrentPix = null;
106
107 private float onValue;
108
109 /**
110 * Default constructor that creates an accumulator space for 360 degrees with a "on value" of 0.0f
111 */
112 public HoughLines()
113 {
114 this( 360 , 0f);
115 }
116
117 /**
118 * Constructor that creates a default accumulator space with
119 * a specified value for pixels considered to be "on"
120 * @param onValue value of pixels considered on
121 */
122 public HoughLines(float onValue)
123 {
124 this( 360 , onValue);
125 }
126
127 /**
128 * Constructor that creates an accumulator space for the given number
129 * of segments.
130 *
131 * @param nSegments The number of segments.
132 * @param onValue value of pixels considered on
133 */
134 public HoughLines( int nSegments , float onValue)
135 {
136 this.setNumberOfSegments( nSegments );
137 this.onValue = onValue;
138 }
139
140 /**
141 * {@inheritDoc}
142 * @see org.openimaj.image.analyser.ImageAnalyser#analyseImage(org.openimaj.image.Image)
143 */
144 @Override
145 public void analyseImage(FImage image)
146 {
147 int amax = (int) round(sqrt((image.getHeight()*image.getHeight()) + (image.getWidth()*image.getWidth())));
148
149 if( accum == null ||
150 accum.height != amax ||
151 accum.width != getNumberOfSegments() )
152 accum = new FImage( getNumberOfSegments(), amax );
153 else accum.zero();
154
155 for( int y = 0; y < image.getHeight(); y++ )
156 {
157 for( int x = 0; x < image.getWidth(); x++ )
158 {
159 if( image.getPixel(x,y) == onValue )
160 {
161 for( int m = 0; m < getNumberOfSegments(); m++ )
162 {
163 // double mm = PI*m*360d/getNumberOfSegments()/180d;
164 double mm = ((double)m / (double)getNumberOfSegments()) * (2 * PI);
165 int a = (int) round( x * cos(mm) + y * sin(mm) );
166 if( a < amax && a >= 0)
167 accum.pixels[a][m]++;
168 }
169 }
170 }
171 }
172 }
173
174 /**
175 * Returns the accumulator space.
176 * @return The accumulator space {@link FImage}
177 */
178 public FImage getAccumulator()
179 {
180 return accum;
181 }
182
183 /**
184 * Calculates a projection across the accumulator space.
185 * Returns an image that has width {@link #getNumberOfSegments()}
186 * and height of 1. Effectively sums across the distances from origin
187 * in the space such that you end up with a representation that gives you
188 * the strength of the angles in the image irrespective of where those
189 * lines occur.
190 *
191 * @return A horizontal projection on the accumulator space as an
192 * FImage with dimensions {@link #getNumberOfSegments()} x 1
193 */
194 public FImage calculateHorizontalProjection()
195 {
196 return calculateHorizontalProjection( accum );
197 }
198
199 /**
200 * Calculates a projection across the given accumulator space.
201 * Returns an image that has width the same as the input
202 * and height of 1. Effectively sums across the distances from origin
203 * in the space such that you end up with a representation that gives you
204 * the strength of the angles in the image irrespective of where those
205 * lines occur.
206 *
207 * @param accum The accumulator space to project
208 * @return A horizontal projection on the accumulator space as an
209 * FImage with same width as input image but only 1 pixel high
210 */
211 public FImage calculateHorizontalProjection( FImage accum )
212 {
213 FImage proj = new FImage( accum.getWidth(), 1 );
214
215 for( int x = 0; x < accum.getWidth(); x++ )
216 {
217 float acc = 0;
218 for( int y = 0; y < accum.getHeight(); y++ )
219 acc += accum.getPixel(x,y)*accum.getPixel(x,y);
220 proj.setPixel(x,0, (float)Math.sqrt(acc) );
221 }
222
223 return proj;
224 }
225
226 /**
227 * Returns the most frequent angle that occurs within the accumulator
228 * space by calculating a horizontal projection over the accumulator
229 * space and returning the angle with the most votes. The prevailing
230 * angle is given in degrees. If it is less than zero, then no angle
231 * could be extracted (there was no local maxima in the accumulator).
232 *
233 * @return The prevailing angle (degrees) in the accumulator space; or
234 * Double.MIN_VALUE if the value cannot be calculated
235 */
236 public double calculatePrevailingAngle()
237 {
238 return calculatePrevailingAngle( accum, 0, 360 );
239 }
240
241 /**
242 * Returns the most frequent angle that occurs within the given accumulator
243 * space by calculating a horizontal projection over the accumulator
244 * space and returning the angle with the most votes. The prevailing
245 * angle is given in degrees. If it is less than zero, then no angle
246 * could be extracted (there was no local maxima in the accumulator).
247 *
248 * @param accum The accumulator space to use
249 * @param offset The offset into the accumulator of the 0 degree bin
250 * @param nDegrees The number of degrees covered by the accumulator space
251 * @return The prevailing angle (degrees) in the accumulator space; or
252 * Double.MIN_VALUE if there is no prevailing angle
253 */
254 public double calculatePrevailingAngle( FImage accum, int offset, double nDegrees )
255 {
256 FValuePixel maxpix = calculateHorizontalProjection(accum).maxPixel();
257 if( maxpix.x == -1 && maxpix.y == -1 )
258 return Double.MIN_VALUE;
259 return (maxpix.x+offset) *
260 (nDegrees/accum.getWidth());
261 }
262
263 /**
264 * Returns the most frequent angle that occurs within the given accumulator
265 * space with a given range of angles (specified in degrees)
266 * by calculating a horizontal projection over the given accumulator
267 * space and returning the angle with the most votes. The prevailing
268 * angle is given in degrees. If it is less than zero, then no angle
269 * could be extracted (there was no local maxima in the accumulator).
270 *
271 * @param minTheta The minimum angle (degrees)
272 * @param maxTheta The maximum angle (degrees)
273 * @return The prevailing angle within the given range; or Double.MIN_VALUE
274 * if the value cannot be calculated
275 */
276 public double calculatePrevailingAngle( float minTheta, float maxTheta )
277 {
278 // Swap if some numpty puts (50,40)
279 if( minTheta > maxTheta )
280 {
281 float tmp = minTheta;
282 minTheta = maxTheta;
283 maxTheta = tmp;
284 }
285
286 if( minTheta >= 0 )
287 {
288 int mt = (int)(minTheta / (360d/getNumberOfSegments()));
289 int xt = (int)(maxTheta / (360d/getNumberOfSegments()));
290 FImage f = accum.extractROI( mt, 0, xt-mt, accum.getHeight() );
291 return calculatePrevailingAngle( f, mt, (xt-mt)*(360d/getNumberOfSegments()) );
292 }
293 else
294 {
295 // If minTheta < maxTheta, the assumption is that someone has
296 // entered something like (-10,10) - between -10 and +10 degrees.
297
298 // Create an accumulator space that's shifted left by the right number of bins
299 int mt = (int)(minTheta / (360d/getNumberOfSegments()));
300 int xt = (int)(maxTheta / (360d/getNumberOfSegments()));
301 FImage a = accum.shiftRight( -mt ).extractROI(0,0,(xt-mt),accum.getHeight());
302 return calculatePrevailingAngle( a, mt, (xt-mt)*(360d/getNumberOfSegments()) );
303 }
304 }
305
306 /**
307 * Returns the top line in the accumulator space.
308 * The end points of the line will have x coordinates at -2000 and 2000.
309 *
310 * @return The strongest line in the accumulator space
311 */
312 public Line2d getBestLine()
313 {
314 return getBestLine( accum, 0 );
315 }
316
317 /**
318 * Returns the top line in the given accumulator space.
319 * The end points of the line will have x coordinates at -2000 and 2000.
320 *
321 * @param accumulatorSpace The accumulator space to look within
322 * @param offset The number of bins offset from zero degrees
323 * @return The strongest line in the accumulator space
324 */
325 public Line2d getBestLine( FImage accumulatorSpace, int offset )
326 {
327 FValuePixel p = accumulatorSpace.maxPixel();
328
329 // Remember accumulator space is r,theta
330 int theta = p.x + offset;
331 int dist = p.y;
332
333 return getLineFromParams( theta, dist, -2000, 2000 );
334 }
335
336 /**
337 * Returns the best line within a certain angular range. Angles
338 * should be provided in degrees (0..359). If the best line has
339 * the maximum or minimum angles it will be returned.
340 *
341 * @param minTheta Minimum angle of the best line
342 * @param maxTheta Maximum angle of the best line
343 * @return The best line that has an angle within the given range.
344 */
345 public Line2d getBestLine( float minTheta, float maxTheta )
346 {
347 // Swap if some numpty puts (50,40)
348 if( minTheta > maxTheta )
349 {
350 float tmp = minTheta;
351 minTheta = maxTheta;
352 maxTheta = tmp;
353 }
354
355 if( minTheta >= 0)
356 {
357 int mt = (int)(minTheta / (360d/getNumberOfSegments()));
358 int xt = (int)(maxTheta / (360d/getNumberOfSegments()));
359 FImage f = accum.extractROI( mt, 0, xt-mt, accum.getHeight() );
360 return getBestLine( f, mt );
361 }
362 else
363 {
364 // If minTheta < maxTheta, the assumption is that someone has
365 // entered something like (-10,10) - between -10 and +10 degrees.
366
367 // Create an accumulator space that's shifted left by the right number of bins
368 int mt = (int)(minTheta / (360d/getNumberOfSegments()));
369 int xt = (int)(maxTheta / (360d/getNumberOfSegments()));
370 FImage a = accum.shiftRight( -mt ).extractROI(0,0,(xt-mt),accum.getHeight());
371 return getBestLine( a, mt );
372 }
373 }
374
375 /**
376 * Returns the top n lines from the given accumulator space within the range.
377 * The end points of the lines will have x coordinates at -2000 and 2000.
378 *
379 * @param n The number of lines to return
380 * @param minTheta The minimum angle (degrees)
381 * @param maxTheta The maximum angle (degrees)
382 * @return A list of lines
383 */
384 public List<Line2d> getBestLines( int n, float minTheta, float maxTheta )
385 {
386 // Swap if some numpty puts (50,40)
387 if( minTheta > maxTheta )
388 {
389 float tmp = minTheta;
390 minTheta = maxTheta;
391 maxTheta = tmp;
392 }
393
394 if( minTheta >= 0)
395 {
396 int mt = (int)(minTheta / (360d/getNumberOfSegments()));
397 int xt = (int)(maxTheta / (360d/getNumberOfSegments()));
398 FImage f = accum.extractROI( mt, 0, xt-mt, accum.getHeight() );
399 return getBestLines( n, f, mt );
400 }
401 else
402 {
403 // If minTheta < maxTheta, the assumption is that someone has
404 // entered something like (-10,10) - between -10 and +10 degrees.
405
406 // Create an accumulator space that's shifted left by the right number of bins
407 int mt = (int)(minTheta / (360d/getNumberOfSegments()));
408 int xt = (int)(maxTheta / (360d/getNumberOfSegments()));
409 FImage a = accum.shiftRight( -mt ).extractROI(0,0,(xt-mt),accum.getHeight());
410 return getBestLines( n, a, mt );
411 }
412 }
413
414 /**
415 * Returns the top n lines from the accumulator space.
416 * The end points of the lines will have x coordinates at -2000 and 2000.
417 *
418 * @param n The number of lines to return
419 * @return A list of lines
420 */
421 public List<Line2d> getBestLines( int n )
422 {
423 return getBestLines( n, accum, 0 );
424 }
425
426 /**
427 * Returns the top n lines from the given accumulator space.
428 * The end points of the lines will have x coordinates at -2000 and 2000.
429 *
430 * @param n The number of lines to return
431 * @param accumulatorSpace The space to look within
432 * @param offset The offset into the accumulator of 0 in this space
433 * @return A list of lines
434 */
435 public List<Line2d> getBestLines( int n, FImage accumulatorSpace, int offset )
436 {
437 FImage accum2 = accumulatorSpace.clone();
438 List<Line2d> lines = new ArrayList<Line2d>();
439 for( int i = 0; i < n; i++ )
440 {
441 FValuePixel p = accum2.maxPixel();
442 lines.add( getLineFromParams( p.x+offset, p.y, -2000, 2000 ) );
443 accum2.setPixel( p.x, p.y, 0f );
444 }
445
446 return lines;
447 }
448
449 /**
450 * From a r,theta parameterisation of a line, this returns a {@link Line2d}
451 * with endpoints at the given x coordinates. If theta is 0 this will return
452 * a vertical line between -2000 and 2000 with the x-coordinate the appopriate
453 * distance from the origin.
454 *
455 * @param theta The angle bin in which the line lies (x in the accumulator space)
456 * @param dist The distance bin in which the line lies (y in the accumulator space)
457 * @param x1 The x-coordinate of the start of the line
458 * @param x2 The x-coordinate of the end of the line
459 * @return A {@link Line2d}
460 */
461 public Line2d getLineFromParams( int theta, int dist, int x1, int x2 )
462 {
463 if( theta == 0 )
464 {
465 return new Line2d(
466 new Point2dImpl( dist, -2000 ),
467 new Point2dImpl( dist, 2000 )
468 );
469 }
470
471 double t = theta * (360d/getNumberOfSegments()) * Math.PI/180d;
472 return new Line2d(
473 new Point2dImpl(
474 x1, (float)(x1*(-Math.cos(t)/Math.sin(t)) + (dist/Math.sin(t)) ) ),
475 new Point2dImpl(
476 x2, (float)(x2*(-Math.cos(t)/Math.sin(t)) + (dist/Math.sin(t)) )
477 ) );
478 }
479
480 /**
481 * {@inheritDoc}
482 * @see java.lang.Iterable#iterator()
483 */
484 @Override
485 public Iterator<Line2d> iterator()
486 {
487 clearIterator();
488 checkIteratorSetup();
489 return this;
490 }
491
492 /**
493 * Used to clone the accumulator space when an iterator
494 * function is used.
495 */
496 private void checkIteratorSetup()
497 {
498 if( iteratorAccum == null )
499 iteratorAccum = accum.clone();
500 }
501
502 /**
503 * {@inheritDoc}
504 * @see java.util.Iterator#hasNext()
505 */
506 @Override
507 public boolean hasNext()
508 {
509 return iteratorAccum.maxPixel().value > 0f;
510 }
511
512 /**
513 * {@inheritDoc}
514 * @see java.util.Iterator#next()
515 */
516 @Override
517 public Line2d next()
518 {
519 iteratorCurrentPix = iteratorAccum.maxPixel();
520 Line2d l = getBestLine( iteratorAccum, 0 );
521 iteratorAccum.setPixel( iteratorCurrentPix.x, iteratorCurrentPix.y, 0f );
522 return l;
523 }
524
525 /**
526 * {@inheritDoc}
527 * @see java.util.Iterator#remove()
528 */
529 @Override
530 public void remove()
531 {
532 iteratorAccum.setPixel( iteratorCurrentPix.x, iteratorCurrentPix.y, 0f );
533 }
534
535 /**
536 * Remove the temporary objects created during iteration.
537 */
538 public void clearIterator()
539 {
540 this.iteratorAccum = null;
541 this.iteratorCurrentPix = null;
542 }
543
544 /**
545 * Set the number of segments used in the accumulator space. By default
546 * this value is 360 (one accumulator bin per degree). However, if you
547 * require greater accuracy then this can be changed. It is suggested
548 * that it is a round multiple of 360.
549 *
550 * @param numberOfSegments Set the number of directional bins in
551 * the accumulator space
552 */
553 public void setNumberOfSegments( int numberOfSegments )
554 {
555 this.numberOfSegments = numberOfSegments;
556 }
557
558 /**
559 * Get the number of directional accumulator bins.
560 *
561 * @return the number of directional bins in the accumulator space.
562 */
563 public int getNumberOfSegments()
564 {
565 return numberOfSegments;
566 }
567 }