发布时间 : 星期日 文章外文文献参考 使用特征值、光栅扫描算法和Hough变换相结合的方法提取线性特征更新完毕开始阅读
内蒙古工业大学毕业设计外文翻译
Linear Feature Extraction using combined approach of Hough transform, Eigen values and
Raster scan Algorithms
In this paper we propose a new method for linear geometric primitive identification which uses the generalized standard Hough transform (HT), Eigen value based statistical parameter analysis and Bresenham's raster scan algorithms. In this method, we use the sparse matrix to find the Hough transform of the given image. Since sparse matrices squeeze zero elements and contain a small number of nonzero elements they provide an advantage in matrix storage space and computational time. Hough peaks are identified based on neighborhood suppression scheme. After finding the meaningful and distinct Hough peaks, coordinates of linear features in Hough space can be obtained using Bresenham 's raster scan algorithm. Since quantization in parameter space of the HT gives both the real and false primitives because of quantization in the space of digital image, quantization in parameter space of HT as well as the fact that the edges in typical images are not perfectly constitutes the geometrical features, a statistical analysis is done using the eigen values to characterize and identifying the geometrical primitives. The proposed method has the advantages of small storage, high speed, and accurate digitization of Hough space and less line extraction error ratio over previously presented HT based techniques and its invariants.
1. INTRODUCTION
Extracting geometric primitives in digital images is one of the basic tasks of computer vision and image segmentation. The HT and its variants [1] constitute a popular method for extracting geometrical primitives like straight lines, circles and ellipses. Over decades, many researchers themselves modified the basic HT [2] to extract geometrical primitives more efficiently. The modified HT based on the combined use of random sampling in the image space, score accumulation in the parameter space and converging mapping as the bridge between two spaces constitutes the Randomized Hough Transform(RHT)[3][6][7]. In RHT one can sample randomly 'n' pixels directly from an image with each pixel being picked with equal probability. The main drawback of this method is that the elements
1
内蒙古工业大学毕业设计外文翻译
which are not constituent of geometrical primitives will participate in evidence gathering, which enhances the computational complexity. In Probabilistic Hough Transform (PHT) [4], the fraction of points used for voting is specified by ad hoc or using prior knowledge of geometrical primitives. In the first step of PHT a random subset of points is selected and a Standard Hough Transform (SHT) [2] is subsequently performed on the subset. To minimize the computational requirement, the Progressive Probabilistic Hough Transform (PPHT) [5] exploiting the difference in the fraction of votes needed to reliably detect lines with different number of supporting points. The PPHT which reflects the progressive nature of the process in line detection finds the longest line first and proceeds to the shortest lines. A hierarchical approach to line detection based on the HT developed by Josef Kittler et al [8] used the pyramid structure with each layer in pyramid splitting the complete image into a number of subimages. At the bottom level of the pyramid short line segments are detected. The algorithm proceeds bottom up by grouping line segments within local neighborhoods into longer lines. On the other hand, D.S. Guru et al [9] proposed statistical and geometrical properties of the small Eigen values of the covariance matrix of a set of edge pixels over a connected region of support are explored for the purpose of straight line identification. In this method small eigen value analysis is used to decide on the prominence of a pixel as a linear pixel.
From the above discussion, it is evident that, parametric space analysis of HT, statistical analysis of edge images and geometrical properties of objects are the three parametersused to detect the geometrical primitives in images. In our proposed method, we utilized the features of all the three parameters. After finding the Hough peak for a corresponding primitive, digitization of the Hough space can be done using Bresenham's raster scan line algorithm, which give the accurate locations of points of interest. Small Eigen value analysis is used to find the role of identified locations in the object identification, noise removal and feature extraction.
2. PROPOSED METHOD
The proposed method for detecting geometrical primitives like straight lines in images consists of six steps.
Step 1: For the given grayscale images find the edge image using suitable edge detection
2
内蒙古工业大学毕业设计外文翻译
operators.
Step 2: Obtain the HT for edge image using sparse matrices which provides advantages over matrix storage and computational time.
Step 3: Find the meaningful set of distinct Hough peaks using the following steps: i) Find the accumulator cell containing the highest value and record its location.
ii) Set to zero the accumulator cells in the immediate neighborhood of the maximum found. Select the window size based on the accuracy needed.
iii) Repeat the above steps until the desired peaks have been found
Step 4: Once the candidate peaks and their locations are identified, digitize the Hough space with respect to a particular primitive using Bresenham's algorithm.
Step 5: Construct a full matrix for the nonzero pixels obtained from step 4 for a corresponding primitive. This gives the sub image which has real geometric primitive and other elements with same slope and orientations.
Step 6: Find the covariance matrix for the sub image, perform the Eigen value analysis to detect the real geometrical feature.
3. STRAIGHT LINE DETECTION
The problem of line detection is one of establishing meaningful groups of edge points which lie along straight lines. A classical way to detect edge points which satisfy collinearity constraint is the HT [1]. The HT could be called a global detection method since it examines purely the collinearity of feature points. The HT which attempts to identify lines on the basis of collinearity alone can encounter problems in real world images. This is because edge detection is a local measurement process and therefore, given a discrete, finite resolution image actual measurement of edge properties can be quite inaccurate. If the local information is inaccurate, the global grouping constraint must be relatively weak and therefore a large number of accidental groupings can occur in complex real world images and noisy images. To eliminate these groupings distribution around the peaks of HT is analyzed using patterns of butterfly [10], introducing a random sampling mechanism and converging mapping mechanism into the conventional HT methods (RHT) [3], exploiting the difference in the fraction of votes needed to detect reliable lines with different numbers of supporting points (PPHT) [5] and a hierarchical approach is used to
3
内蒙古工业大学毕业设计外文翻译
detect different length line segments [8].
The number of points used to construct the covariance matrix will affect the Eigen values of given boundary. The effective approach for determining the region of support at each individual boundary point based on local properties of that point. The region of support for the computation of the covariance matrix at each boundary point can also be adaptively selected. From Table-I we observe that the small Eigen values Xs for different line lengths segments with different slope angle and orientations are approximately zero. In our method after finding the Hough transform for the given edge image the Hough peaks can be identified using neighborhood suppression technique discussed in step(3) of section 2. If the length of the desired line is priori known the number of votes in the accumulator cell can be easily found by finding the local maxima of the Hough peaks. For unknown lines the threshold value can varied until to get the correct lines are obtained.
4. EXPERIMENTAL RESULTS
This section gives the results of experiment obtained by using both synthetic and real world images with additive impulse noise and Gaussian noise. The use of synthetic images for which ground truth is known enables us to give some quantitative estimate of the accuracy obtained. In real images the definition of what should and should not be detected as a geometric primitive is subjective or application dependent. In performance evaluation the correctness of output can be measured by the error factor which is the ratio of real line points to the number of mismatched (false positive/false negative) points.
Figure l(a) shows a typical synthetic image with different object shapes. To test the robustness and noise withstanding capability additive impulse noise with noise density of 0.05 and Gaussian noise with mean m=0 and variance v=0.01 are added and is shown in fig l(b). The Hough transform and theidentified Hough peaks for testing are shown in figure l(c).After selecting a particular Hough peak discritization and mapping of Hough space can be done by using Bresenham's algorithm.
4