Closed form line-segment extraction using the Hough transform. (English) Zbl 1394.68346
Pattern Recognition 48, No. 12, 4012-4023 (2015); corrigendum ibid. 60, 647 (2016).
Summary: This paper proposes a novel closed-form solution to complete line-segment extraction. Given a voting angle in image space, the voting distribution is analyzed and two functional relationships are deduced. Regarding the corresponding column in Hough space, voting along the distance axis is considered as being a random variable, and voting values in cells are considered as forming a probability distribution. Statistical characteristics of this distribution are used to fit a quadratic polynomial curve and a linear curve. Direction, length, and width of a line segment are simultaneously computed in a closed form based on coefficients of fitted quadratic polynomial curves. The midpoint of a line segment is determined based on the fitted linear curve. The method is tested on simulated and real-world images; results show that the proposed closed-form solution is feasible in the presence of quantization errors or image noise.
Keywords:
line-segment extraction; Hough transform; line-segment parameters; curve fitting; pattern analysisReferences:
| [1] | Google map. 〈https://maps.google.com/〉, 2015. |
| [2] | Otsu, N., A threshold selection method from gray-level histograms, IEEE Trans. Syst. Man Cybern., 9, 62-66, (1979) |
| [3] | Klette, R., Concise computer vision, (2014), Springer London · Zbl 1282.68003 |
| [4] | Netanyahu, N. S.; Weiss, I., Analytic line Fitting in the presence of uniform random noise, Pattern Recognit., 34, 703-710, (2001) · Zbl 0991.68073 |
| [5] | Qjidaa, H.; Radouane, L., Robust line Fitting in a noisy image by the method of moments, IEEE Trans. Pattern Anal. Mach. Intell., 21, 1216-1223, (1999) |
| [6] | Weiss, I., Line Fitting in a noisy image, IEEE Trans. Pattern Anal. Mach. Intell., 11, 325-329, (1989) · Zbl 0709.62609 |
| [7] | P.V.C. Hough, Methods and means for recognizing complex patterns, U.S. Patent 3.069.654 (1962). |
| [8] | Duda, R. O.; Hart, P. E., Use of the Hough transformation to detect lines and curves in pictures, Comm. ACM, 15, 11-15, (1972) · Zbl 1296.94027 |
| [9] | Xu, Z.; Shin, B.-S.; Klette, R., Determination of length and width of a line-segment by using a Hough transform, Proc. Discrete Geom. Comput. Imaging LNCS, 8668, 190-201, (2014) · Zbl 1419.94012 |
| [10] | Xu, Z.; Shin, B.-S.; Klette, R., Accurate and robust line segment extraction using minimum entropy with Hough transform, IEEE Trans. Image Process., 24, 813-822, (2015) · Zbl 1408.94744 |
| [11] | Z. Xu, B.-S. Shin, R. Klette, A statistical method for line segment detection, Comput. Vis. Image Underst |
| [12] | Luengo Hendriks, C. L.; Ginkel, M. V.; Verbeek, P. W., The generalized Radon transformsampling, accuracy and memory considerations, Pattern Recognit., 38, 12, 2494-2505, (2005) |
| [13] | Mukhopadhyay, P.; Chaudhuri, B. B., A survey of Hough transform, Pattern Recognit., 48, 3, 993-1010, (2015) |
| [14] | El Mejdani, S.; Egli, R.; Dubeau, F., Old and new straight-line detectorsdescription and comparison, Pattern Recognit., 41, 6, 1845-1866, (2008) · Zbl 1134.68485 |
| [15] | Chung, K.-L.; Chen, T.-C.; Yan, W.-M., New memory- and computation-efficient Hough transform for detecting lines, Pattern Recognit., 37, 5, 953-963, (2004) |
| [16] | Ulrich, M.; Steger, C.; Baumgartner, A., Real-time object recognition using a modified generalized Hough transform, Pattern Recognit., 36, 11, 2557-2570, (2003) · Zbl 1059.68118 |
| [17] | Cheng, H. D.; Guo, Y.; Zhang, Y., A novel Hough transform based on eliminating particle swarm optimization and its applications, Pattern Recognit., 42, 9, 1959-1969, (2009) · Zbl 1178.68487 |
| [18] | Fernandes, L. A.F.; Oliveira, M. M., Real-time line detection through an improved Hough transform voting scheme, Pattern Recognit., 41, 1, 299-314, (2008) · Zbl 1122.68529 |
| [19] | Kiryati, N.; Eldar, Y.; Bruckstein, A. M., A probabilistic Hough transform, Pattern Recognit., 24, 4, 303-316, (1991) |
| [20] | Walsh, D.; Raftery, A. E., Accurate and efficient curve detection in imagesthe importance sampling Hough transform, Pattern Recognit., 35, 7, 1421-1431, (2002) · Zbl 1016.68085 |
| [21] | W. Niblack, D. Petkovic, On improving the accuracy of the Hough transform: theory, simulation, and experiments, in: Proceedings of IEEE Conference on Computer Vision Pattern Recognition, 1988, pp. 574-579. |
| [22] | Niblack, W.; Petkovic, D., On improving the accuracy of the Hough transform, Mach. Vis. Appl., 3, 87-106, (1990) |
| [23] | Du, S.; Tu, C.; Sun, M., High accuracy Hough transform based on butterfly symmetry, Electron. Lett., 48, 199-201, (2012) |
| [24] | Leavers, V. F.; Boyce, J. F., The Radon transform and its application to shape parameterization in machine vision, Image Vis. Comput., 5, 161-166, (1987) |
| [25] | Z. Xu, B.-S. Shin, A statistical method for peak localization in Hough space by analysing butterflies, in: Proceedings of Pacific-Rim Symposium on Image Video Technology. LNCS 8333, 2013. |
| [26] | Z. Xu, B.-S. Shin, Line segment detection with Hough transform based on minimum entropy, in: Proceedings of Pacific-Rim Symposium on Image Video Technology, LNCS 8333, 2013. |
| [27] | Yang, M. C.K.; Lee, J.-S.; Lien, C.-C.; Huang, C.-L., Hough transform modified by line connectivity and line thickness, IEEE Trans. Pattern Anal. Mach. Intell., 19, 905-910, (1997) |
| [28] | Dahyot, R., Statistical Hough transform, IEEE Trans. Pattern Anal. Mach. Intell., 31, 1502-1509, (2009) |
| [29] | Barinova, O.; Lempitsky, V.; Kholi, P., On detection of multiple object instances using Hough transforms, IEEE Trans. Pattern Anal. Mach. Intell., 34, 1773-1784, (2012) |
| [30] | Aggarwal, N.; Karl, W., Line detection in images through regularized Hough transform, IEEE Trans. Image Process, 15, 582-591, (2006) |
| [31] | Lee, D.; Park, Y., Discrete Hough transform using line segment representation for line detection, Opt. Eng., 50, 87004-87008, (2011) |
| [32] | Kiryati, N.; Bruckstein, A. M., What׳s in a set of points?, IEEE Trans. Pattern Anal. Mach. Intell., 14, 496-500, (1992) |
| [33] | Kiryati, N.; Bruckstein, A. M., Heteroscedastic Hough transform (htht)an efficient method for robust line Fitting in the ‘errors in the variables’ problem׳, Comput. Vis. Image Underst., 78, 69-83, (2000) |
| [34] | Guerreiro, R.; Aguiar, P., Connectivity-enforcing Hough transform for the robust extraction of line segments, IEEE Trans. Image Process., 21, 4819-4829, (2012) · Zbl 1373.94146 |
| [35] | Yamato, J.; Ishii, I.; Makino, H., Highly accurate segment detection using Hough transformation, Syst. Comput. Jpn., 21, 68-77, (1990) |
| [36] | L.F. Costa, B. Ben-Tzvi, M. Sandler, Performance improvements to the Hough transform, in:Proceedings of UK IT 1990 Conference, 1990, pp. 98-103. |
| [37] | T.T. Nguyen, X.D. Pham, J. Jeon, An improvement of the standard Hough transform to detect line segments, in: Proceedings of IEEE International Conference on Industrial Technology, 2008, pp. 1-6. |
| [38] | Furukawa, Y.; Shinagawa, Y., Accurate and robust line segment extraction by analyzing distribution around peaks in Hough space, Comput. Vis. Image Underst., 92, 1-25, (2003) |
| [39] | Ji, J.; Chen, G.; Sun, L., A novel Hough transform method for line detection by enhancing accumulator array, Pattern Recognit. Lett., 32, 1503-1510, (2011) |
| [40] | Akhtar, M. W.; Atiquzzaman, M., Determination of line length using Hough transform, Electron. Lett., 28, 94-96, (1992) |
| [41] | Ioannou, D., Using the Hough transform for determining the length of a digital straight line segment, Electron. Lett., 31, 782-784, (1995) |
| [42] | Cha, J.; Cofer, R. H.; Kozaitis, S. P., Extended Hough transform for linear feature detection, Pattern Recognit., 39, 6, 1034-1043, (2006) · Zbl 1096.68712 |
| [43] | Richards, J.; Casasent, D. P., Extracting input-line position from Hough transform data, Appl. Opt., 30, 2899-2905, (1991) |
| [44] | Chung, K.-L.; Huang, Y.-H.; Wang, J.-P.; Chang, T.-C.; Liao, H.-Y. M., Fast randomized algorithm for center-detection, Pattern Recognit., 43, 8, 2659-2665, (2010) · Zbl 1207.68440 |
| [45] | Song, J.; Lyu, M. R., A Hough transform based line recognition method utilizing both parameter space and image space, Pattern Recognit., 38, 4, 539-552, (2005) |
| [46] | Jang, J.-H.; Hong, K.-S., Linear band detection based on the Euclidean distance transform and a new line segment extraction method, Pattern Recognit., 34, 9, 1751-1764, (2001) · Zbl 0995.68163 |
| [47] | Zhang, Q.; Couloigner, I., Accurate center line detection and line width estimation of thick lines using the Radon transform, IEEE Trans. Image Process., 16, 310-316, (2007) |
| [48] | von Gioi, R.; Jakubowicz, J.; Morel, J.; Randall, G., Lsda fast line segment detector with a false detection control, IEEE Trans. Pattern Anal. Mach. Intell., 32, 722-732, (2010) |
| [49] | Atiquzzaman, M.; Akhtar, M. W., Complete line segment description using the Hough transform, Image Vis. Comput., 12, 267-273, (1994) |
| [50] | Atiquzzaman, M.; Akhtar, M. W., A robust Hough transform technique for complete line segment description, Real-Time Imaging, 1, 419-426, (1995) |
| [51] | V. Kamat, S. Ganesan, A robust Hough transform technique for description of multiple line segments in an image, in:Proceedings of International Conference on Image Processing, 1998, pp. 216-220. |
| [52] | Kamat-Sadekar, V.; Ganesan, S., Complete description of multiple line segments using the Hough transform, Image Vis. Comput., 16, 597-613, (1998) |
| [53] | Du, S.; Tu, C.; van Wyk, B. J.; Ochola, E. O.; Chen, Z., Measuring straight line segments using HT butterflies, PLoS ONE, 7, e33790, (2012) |
| [54] | Du, S.; Tu, C.; van Wyk, B. J.; Chen, Z., Collinear segment detection using HT neighborhoods, IEEE Trans. Image Process., 20, 3912-3920, (2011) · Zbl 1374.94091 |
| [55] | G. Gerig, F. Klein, Fast contour identification through efficient Hough transform and simplified interpretation strategies, in: Proceedings of International Conference on Pattern Recognition, 1986, pp. 498-500. |
| [56] | EISATS: .enpeda.. image sequence analysis test site. 〈http://ccv.wordpress.fos.auckland.ac.nz/eisats/〉, 2015. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
