In this thesis, a new line detection method(FLDA: Fast Line Detection using $A^{\ast}$ algorithm) is proposed. The method uses line following method which is quantitatively analyzed in this thesis and $A^{\ast}$ algorithm which is used in graph theory to find optimum path in a graph. In order to find line using $A^{\ast}$ algorithm, the image is converted to a graph form and then $A^{\ast}$ algorithm is applied. The cost function of $A^{\ast}$ algorithm is weighted sum of gray value of candidate pixel and that of the front pixel of candidate pixel. The effectiveness of the proposed algorithm is shown by comparison with other conventional algorithms. The view points of comparison are the performance, the speed, and a priori information. As a result, its performance is very good. And the speed of the algorithm is seven times as fast as other algorithms. It takes so little operation time that it can be used for a lot of applications which have to be done fast.
본 논문에서는 그래프이론에서 최적 경로를 찾는데 이용되는 $A^{\ast}$ 알고리즘을 사용하여 새로운 line검출기법을 제안하였다. 이 방법은 근본적으로 주위의 화소중 gray값이 가장 큰 화소를 따라가는 line following방법을 이용하였는데 먼저 본 논문에서는 이 line following방법에 대해 정량적 해석을 시도하였다.
Line을 찾는 방법에 $A^{\ast}$ 알고리즘을 이용하기 위하여 먼저 영상을 그래프형태로 바꾸고 여기에 $A^{\ast}$ 알고리즘을 적용하였는데 이 때 이용한 cost함수로는 후보화소의 밝기값과 후보화소 앞에 있는 화소값의 weighted sum을 이용하였다.
제안된 알고리즘의 효율성을 알아보기 위하여 정확성, 속도, 그리고 사전정보의 양의 관점에서 기존의 알고리즘들과 성능을 비교하였다. 그 결과 제안된 알고리즘은 기존의 알고리즘과 같은 성능을 가지면서 매우 빠른 수행속도를 가짐을 알 수 있었다.
