The Modified Algorithm Of Hough Transform And Line Segment Detection

In this paper, a new algorithm of Hough transform (HT) is proposed, and is applied to line segment detection.Hough transform (HT), which was proposed by Hough in 1962, is essentially a voting process where each point belonging to the lines votes for all the possible lines passing through the point. These votes are accumulated in an accumulator array, and the pattern receiving the maximum votes is recognized as the desired line. It is widely applied to computer vision and pattern recognition in recent years.A lot of modified algorithms had appeared in recent years. Some are focus on the process of the program; and others are focus on improving the Hough space, so that the algorithm is more effective than before. But two parameters are used in the space of the great mass of those modified algorithms, as will need more storage in the Hough space. A modified Hough transform, in which only one parameter is used in their algorithm, is proposed by Chutatape & Guo in 1999, the performance and efficiency of it is more evaluated than the algorithm that use two parameters.But the existing Hough transform and its modified ones share in a common drawback that the detection region is not effective enough. The detection region of the algorithm where two parameters are used in the Hough space would be X-shape, and that of the algorithm where only one parameter is used would be sector shape. Many feature points belonging to the line would not be detected; moreover many noise points that are not in the line would be wrongly looked as belonging to the line, owing to the X-shape and the sector-shape detection region. So the results of the detected lines would be incorrect. To overcome the drawback of existing algorithm, a new algorithm of Hough transform will be proposed in the Chapter 2. The new algorithm has three characteristics:(1) Many-to-one Mapping. HT methods can be grouped into two classes according to the mapping schemes, i.e., one-to-many and many-to-one. It will require less storage and compute times in the algorithm that takes the many-to-one mapping scheme.(2) Effective detection region. The detection region of the new algorithm is strip-shape. In the strip-shape detection region all of the feature points belonging to the line will be detected and the noise will be not. It is significance to detect the parameters of extracted lines.(3) Less storage requirement. The required storage of the Hough space in new algorithm is only 1 byte.It has some drawback, when we apply the Hough transform to detect the line. (1) In nature, the discontinuousness feature points in a line would be detected as an extracted line. That is to say, the wrong line would be extracted. (2) Only one line is detected if there are two or more line segments in a line. (3) Line segment is a translation-, and rotation- invariant feature of the symbol image. The extraction of the exact line segment is very significant to the recognition ratio of system. In Chapter 3, we apply the new algorithm to extract the line segment. The robustness of the algorithm is very good owing to the strip-shape detection region.Experimental results show the robustness of the two algorithms proposed in this paper are excellent, and they can be used into some recognition system, such as mathematical expression recognition system etc.