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

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.

Authors:

• J. Prakash
• K. Rajesh

Keywords:

• Circular Hough transform
• covariance matrix
• Eigen values
• ellipse detection
• raster scan algorithm.

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.