Line detection algorithms : application of digital line segment properties

In the field of computer vision, features extraction plays an important role on the performance of objects or scenes analysis. In this thesis, work is mainly concentrated on the development of line segment extraction algorithm. In the world, most of the man-made objects can be interpreted using line segment. Moreover, line segment matching has become a popular research topic in the field of stereo vision. Hence, the performance of line segment extraction, both in the computational efficiency and the quality of extraction, evolves an important factor in the whole vision system. The scope of this thesis is to investigate properties of digital line segment - the Equidistance Property and the Orientation Convergence Property which are useful in digital line segment description. Accordingly, two line detection algorithms are proposed - Simple Line Tracing (SLIT) and Direction Convergence Line Detection (DECLINE). According to Duda and Hart, the connectivity of a line is defined as a set of collinear points without regard to contiguity. This definition is useful in the description of straight lines in both continuous domain and discrete domain. In addition to the Duda and Hart's definition of connectivity, we define the relative connectivity of a line as the relationship of a set of collinear and equidistant points with regard to contiguity. The displacement between the equidistant points is defined as relative displacement. In discrete domain, a continuous line segment can be considered as the gathering of sets of periodic pattern. The term - Periodic Subset, is defined to describe the periodic pattern of a digital line segment. Points between periodic subsets contain Equidistance Property. With the help of periodicity of digital line segment, two terms are defined - Global Interpretation Subsets (GSs) and Local Interpretation Subsets (LSs). Hence, a continuous line segment in the discrete domain can be interpreted as the gathering of its corresponding GSs and/ or LSs. Based on this notion, we formulated the detection of digital line segment as 1) detection of evenly spaced linear dotted lines and 2) merging the corresponding dotted lines to form the origin line segment. The proposed algorithm is named as Simple Line Tracing (SLIT). As stated in the above paragraph, a digital line segment can be considered as the gathering of sets of periodic pattern. In SLIT, the relative displacement of the GSs and LSs may be greater than one. In the special case, when the relative displacement is limited to one so that only the adjacent pixels are considered (i.e. connected line segment), the detection of line segment can be considered as only the combination of sets of short line segments with direction 0°, 45°, 90°, 135°. These short line segments are defined as Quantized Directional Elements (QDEs). Considering a digital straight line segment with eight quantized directions, Freeman suggested that the chain codes of a one pixel width line segment must meet the three criteria 1) at most two basic directions are present and they differ only by unity, modulo eight, 2) one of these two symbols always occurs singly and, 3) successive occurrences of a single symbol are as uniformly spaced as possible. With the help of Freeman's criteria and the periodicity of digital line, the equation representing the orientation deviation of digital line when more QDEs are connected is derived. Moreover, the orientation deviation is proved to be converged (Orientation Convergence Property of Digital Line Segment). A new model on the determination of the collinearity and similarity of QDEs is developed. Hence, a simple and efficient line detection algorithm, named as Direction Convergence Line Detection (DECLINE), is proposed. Experimental results show that the two proposed algorithms are efficient and noise insensitive. They accomplish proper results from simple to complex environments and from linear to curve boundaries. A comparison between the two proposed algorithms is made.