Elliptical Features Extraction Using Eigen Values of Covariance Matrices, Hough Transform and Raster Scan Algorithms

Authors: J. Prakash, K. Rajesh

Abstract:

In this paper, we introduce a new method for elliptical object identification. The proposed method adopts a hybrid scheme which consists of Eigen values of covariance matrices, Circular Hough transform and Bresenham-s raster scan algorithms. In this approach we use the fact that the large Eigen values and small Eigen values of covariance matrices are associated with the major and minor axial lengths of the ellipse. The centre location of the ellipse can be identified using circular Hough transform (CHT). Sparse matrix technique is used to perform CHT. Since sparse matrices squeeze zero elements and contain a small number of nonzero elements they provide an advantage of matrix storage space and computational time. Neighborhood suppression scheme is used to find the valid Hough peaks. The accurate position of circumference pixels is identified using raster scan algorithm which uses the geometrical symmetry property. This method does not require the evaluation of tangents or curvature of edge contours, which are generally very sensitive to noise working conditions. The proposed method has the advantages of small storage, high speed and accuracy in identifying the feature. The new method has been tested on both synthetic and real images. Several experiments have been conducted on various images with considerable background noise to reveal the efficacy and robustness. Experimental results about the accuracy of the proposed method, comparisons with Hough transform and its variants and other tangential based methods are reported.

Keywords: Circular Hough transform, covariance matrix, Eigen values, ellipse detection, raster scan algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1059627

References:

[1] R. O. Duda, P. E Hart, "Use of Hough transformation to detect lines and curves in pictures", Comm. Assoc. Comput, 15(1), pp. 11-15., 1972.
[2] D. H. Ballard, "Generalizing the Hough transform to detect arbitrary shapes", Pattern Recogn., 13(2), pp. 111-122, 1981.
[3] E. R. Davis, "Finding ellipses using the generalized Hough transform", Pattern Recogn., pp. 87-96, Feb 1989.
[4] Lei XU, Erkki OJA, Pekka Kultanen, "A new curve detection method: Randomized Hough transform (RHT)", Pattern Recogn, pp. 331-338, May 1990.
[5] Robert A. McLaughlin, "Randomized Hough transform: Improved ellipse detection with comparison", Pattern Recogn, pp. 299-305, 1998.
[6] Wen-Yen Wu, Mao-Jiun J. Wang, "Elliptical object detection by using geometric properties", Pattern Recogn, Vol. 26, No. 20, pp. 1499-1509, April. 1993.
[7] Chun-Ta Ho, Ling-Hwei Chen, "A Fast ellipse/circle detector using geometric symmetry", Pattern Recogn., Vol. 28, No. 1, pp. 117-124, June 1994.
[8] S. Tsuji, F. Matsumoto, "Detection of ellipses by a modified Hough transform", IEEE Trans. Computers., 27(8), pp. 777-781, 1978.
[9] H.T. Sheu, H.Y. Chen, W.C. Hu, "Consistent symmetric axis method for robust detection of ellipses", IEE Proc. Vision, Image signal Process., Vol. 144, No. 6, pp. 332-338, , Dec 1997.
[10] D. S. Guru B, H. Shekar, P. Nagabhushan, "A simple and robust line detection algorithm based on small Eigen value analysis", Pattern Recogn., 25, pp. 1-13, Aug 2003.
[11] J. Prakash, K. Rajesh, "Linear feature extraction using combined approach of Hough transform, Eigen values and raster scan algorithms", Proceeding of International conference on intelligent sensing and information processing (ICISIP), pp. 65-70, Dec 2006.
[12] J. Prakash, K. Rajesh, "A novel and accurate method for circular object identification - Combined approach of Hough transform, Eigen values and raster scan algorithms", Proceedings of IEEE International conference on signal and image processing, Vol. 2, pp. 815-820, Dec 2006.
[13] Du-Ming Tsai, H. T. Hou, H.J. Su, "Boundary based corner detection using Eigen values of covariance matrices", Pattern. Recogn. 20, pp. 31- 40, Sept 1998.
[14] J. Prakash, K. Rajesh, "Extracting geometric primitives: Combined approach of Hough transform, Eigen values and raster scan algorithms", International Journal of systemics, Cybernetics and Informatics (IJSCI), pp. 48-55, Jan 2007.
[15] Rafael C. Gonzalez, Richard E. Woods, "Digital Image processing " (5th ed), Addison Wesley, 2000.
[16] Donald Hearn, M. Pauline Baker, "Computer graphics" (2nd ed), Pearson Education, 2003.