Line detection with adaptive random samples

This paper examines the detection of parameterized shapes in multidimensional noisy grayscale images. A novel shape detection algorithm utilizing random sample theory is presented. Although the method can be generalized, line detection is detailed. Each line in the image corresponds to a point in the line parameter space. The method creates hypothesis lines by randomly selecting parameter space points and tests the surrounding regions for acceptable linear features. The information obtained from each randomly selected line is used to update the parameter distribution, which reducesi the required number of random trials. The selected lines are re-estimated within a smaller search space with a more accurate algorithm like the Hough transform (HT). Faster results are obtained compared to HT, without losing performance as in other faster HT variants. The method is robust and suitable for binary or grayscale images. Results are given from both simulated and experimental subsurface seismic and ground penetrating radar (GPR) images when searching for features like pipes or tunnels.

Anahtar Kelimeler:

Line detection, Hough Transform, Tunnel Detection, Random sampling, Subsurface shape detection

Line detection with adaptive random samples

Keywords:

Line detection, Hough Transform, Tunnel Detection, Random sampling, Subsurface shape detection,

PDF

___

J. Illingworth, J. Kittler, A survey of the Hough Transform, Computer Vision, Graphics and Image Processing 44 (1988) 87–116.
S. R. Deans, The Radon Transform and some of its applications, Krieger Publishing, 1993.
H. Bakircioglu, E. Gelenbe, T. Kocak, Image Enhancement and Fusion with the Random Neural Network, Turkish Journal of Electrical Engineering and Computer Science, 5 (1997) 65–77.
L. G. Shapiro, G. C. Stockman, Computer Vision, Prentice-Hall, 2001.
A. C. Copeland, G. Ravichhandran, M. M. Trivedi, Localized Radon transform-based detection of linear features in noisy images, in: IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1994, pp. –667.
M. Ekinci, E. Gedikli, Silhouette Based Human Motion Detection and Analysis for Real-Time Automated Video Surveillance, Turkish Journal of Electrical Engineering and Computer Science, 13 (2005) 199–229.
A. Dell’Acqua, A. Sarti, S. Tubaro, L. Zanzi, Detection of linear objects in GPR data, Elsevier Signal Processing (2004) 785–799.
P. Toft, K. V. Hansen, Fast Radon transform for detection of seismic reﬂections, in: EURASIP EUSIPCO94, Vol. 1, , pp. 229–232. P. V. C. Hough, A Method and Means for Recognizing Complex Patterns, in: US Patent 3069654, 1962.
G. Beylkin, Discrete Radon Transform, IEEE Trans. Acoustic, Speech, and Signal Processing 35 (1987) 162–172.
R. O. Duda, P. E. Hart, Use of Hough transformation to detect lines and curves in pictures, in: Comm. ACM, Vol. 15, 1972, pp. 11–15.
D. H. Ballard, Generalizing the Hough transform to detect arbitrary shapes, Pattern Recognition 13 (1981) 111–122.
P. Toft, Using the generalized Radon transform for detection of curves in noisy images, in: ICASSP-2006, Vol. 4, , pp. 2219–2222.
P.Toft, The Radon transform theory and implementation, Ph.D. thesis, Technical University of Denmark, Lyngby, Denmark (1996).
N. Kiryati, Y. Eldar, A. M. Bruckstein, A probabilistic Hough transform, Pattern Recognition 24 (1991) 303–316.
L. Xu, E. Oja, P. Kultanan, A new curve detection method: Randomized Hough Transform (RHT), Pattern Recognition Letters 11 (1990) 331–338.
L. Xu, E. Oja, Randomized Hough Transform (RHT): Basic mechanisms, algorithms, and computational complex- ities, CVGIP: Image Understanding 57 (1993) 131–154.
M. A. Fischler, R. C. Bolles, Random sample consensus: a paradigm for model Ştting with applications to image analysis and automated cartography, Comm. ACM 24 (1981) 381–395.
R. Liu, Z. Ruan, S. Wei, Line detection algorithm based on random sample theory, in: SPIE Second International Conf. on Image and Graphics, Vol. 4875, 2002.
T. Chen, K. Chung, A new randomized algorithm for detecting lines, Real Time Imaging 7 (2001) 473–481.
J. Matas, C. Galambos, J. Kittler, Robust detection of lines using the progressive probabilistic Hough transform, Computer Vision and Image Understanding 78 (2000) 119–137.
N. Kiryati, H. Kalviainen, S. Alaoutinen, Randomized and probabilistic Hough transform: uniŞed performance evaluation, Pattern Recognition Letters 21 (2000) 1157–1164.
H. Li, M. A. Lavin, R. J. L. Master, Fast Hough transform: A hierarchical approach, Computer Vision, Graphics and Image Processing 36 (1986) 139–161.
J. Illingworth, J. Kittler, The adaptive Hough transform, IEEE Trans. Pattern Analysis and Machine Intelligence (5) (1987) 690–698.
C. Olson, Locating geometric primitives by pruning the parameter space, Pattern Recognition 34 (2001) 1247–1256.
T. Breuel, Finding lines under bounded error, Pattern Recognition 29 (1) (1996) 167–178.
D. Chai, Q. Peng, Image feature detection as robust model Ştting, in: ACCV 7th Asian Conference on Computer Vision, Vol. 3852, 2006, pp. 673–682.
W. R. Scott, Jr., T. Counts, G. D. Larson, A. C. Gurbuz, J. H. McClellan, Combined ground penetrating radar and seismic system for detecting tunnels, in: IEEE IGARSS, 2006, pp. 1232–1235.
P. Gamba, S. Lossani, Neural detection of pipe signatures in ground penetrating radar images, IEEE Trans. Geoscience and Remote Sensing 38 (2000) 790–797.
A. C. Gurbuz, J. H. McClellan, W. R. Scott, Jr., Compressive Sensing for Subsurface Imaging using Ground Penetrating Radars, Signal Processing, 89 10 (2009) 1959-1972.
Y. Chen, Q. Yang, Y. Gu, J. Yang, Detection of roads in SAR images using particle Şlter, in: Proc. of ICIP, Atlanta, GA, 2006, pp. 2337–2340.
W. R. Scott, Jr., K. Kim, G. D. Larson, A. C. Gurbuz, J. H. McClellan, Combined seismic, radar, and induction sensor for landmine detection, in: Geoscience and Remote Sensing Symposium, Vol. 3, 2004, pp. 1613–1616.
A. C. Gurbuz, J. H. McClellan, W. R. Scott, Jr., A Compressive Sensing Data Acquisition and Imaging Method for Stepped Frequency GPRs, IEEE Trans. Signal Processing, 57 7 (2009) 2640–2650.
T. Counts, G. D. Larson, A. C. Gurbuz, J. H. McClellan, W. R. Scott, Jr., Investigation of the detection of shallow tunnels using electromagnetic and seismic waves, in: Proc. SPIE, Vol. 6553, May 2007.