在影像處理和機器視覺中從數位影像做直線偵測是個重要且基本的作業。在直線偵測的領域中，植基於Hough轉換和隨機式的方法是最知名且成功的兩個方法。前者有著相當大的強健性但是卻相當耗時；後者的速度是相當快速的並且有著一定的強健性。本論文我們首先提出一個新的方向性淘汰式的策略，而且我們將描述如何引入這個策略應用在上述的兩種方法上，以至於達到加速的效果並且保存原有方法的強健性。根據一些真實的測試的影像，實驗結果說明我們的策略能夠加速上述現有的兩種直線偵測演算法，並達到及時的效果。

Detecting lines from a digital image is a very important and fundamental operation in image processing and machine vision. In line-detection area, Hough transform-based approach and the randomized approach are the most well-known and successful two approaches. The former is rather robust, but is some
time-consuming; the latter is very fast and modestly robust. In this paper, we first present a novel orientation-elimination strategy, and then we describe how to plug our proposed elimination strategy into the above two line-detection approaches to reduce the execution-time requirement significantly while preserving the robustness advantage. Based on some real testing images, experimental results demonstrated that our proposed strategy can speed up the existing two line-detection approaches significantly and it would meet the real-time demand.

[1] H. K. Aghajan and T. Kailath, “SLIDE: subspace-based line detection,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 16, No. 11, pp. 1057–1073, Nov. 1994.

[2] J. F. Canny, “A computational approach to edge detection,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 8, No. 6, pp. 679–698, Nov. 1986.

[3] T. C. Chen and K. L. Chung, “A new randomized algorithm for detecting lines,” Real-Time Imaging, Vol. 7, No.6, pp. 473–482, Dec. 2001.

[4] T. C. Chen and K. L. Chung, “An efficient randomized algorithm for detecting circles,”Computer Vision and Image Understanding, Vol. 83, No. 2, pp. 172–191, 2001.

[5] K. L. Chung, T. C. Chen and W. M. Yan, “New memory-and computation-efficient Hough transform for detecting lines,” Pattern Recognition, Vol. 37, No. 5, pp. 953–963, 2004.

[6] K. L. Chung and Y. H. Huang, “Speed up the computation of randomized algorithms for detecting lines, circles, and ellipses using novel tuning–and LUT–based voting platform,” Applied Mathematics and Computation, Vol. 190, No. 1, pp. 132-149, 2007.

[7] E. R. Davies, Maching Vision: Theory, Algorithms, and Practicalities, Third edition, Morgan Kaufmann, 2004.

[8] R. O. Duda and P. E. Hart, “Use of the Hough transformation to detect lines and curves in pictures,” Commun. ACM, Vol. 15, No. 1, pp. 11–15, Jan. 1972.

[9] M. A. Fischler and R. C. Bolles, “Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography,” Commun. ACM, Vol. 24, No. 6, pp. 381–395, 1981.

[10] M. A. Fischler and O. Firschein, Intelligence: The Eye, the Brain, and the Computer, Addison Wesley, pp. 279–280, 1978.

[11] D. A. Forsyth and J. Ponce, Computer Vision: A Modern Approach, Prentice Hall, 2002.

[12] R. C. Gonzalez and R. E. Wood, Digital Image Processing, second edition, Prentice Hall, New Jersey, 2002.

[13] D. Hearn and M. P. Baker, Computer Graphics, third edition, Prentice Hall, New York, 1997.

[14] R. M. Haralick and L. G. Shapiro, Computer and Robot Vision, Addison-Wesley, 1992.

[15] P. V. C. Hough, “Method and means for recognizing complex patterns,” U.S. Patent 3,069,654, 18, Dec. 1962.

[16] J. Illingworth and J. Kittler, “The adaptive Hough transform,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 9, No. 5, pp. 690–698, Aug. 1987.

[17] J. Illingworth and J. Kittler, “Surver: survey of the Hough transforms,” Computer Vision, Graphics, and Image Processing, 44, pp. 87–116, 1988.

[18] R. M. Inigo, “Application of machine vision to traffic monitoring and control,” IEEE Trans. Vehicular Technology, Vol. 38, No. 3, pp. 112–122, Aug. 1989.

[19] R. Jain, R. Kasturi, B. G. Schunck, Maching Vision, MacGraw Hill, 1995.

[20] H. Kぴalviぴainen and P. Hirvonen, “An extension to the randomized Hough transform exploiting connectivity,” Pattern Recognition Letters, Vol. 18, No. 1, pp. 77–85, 1997.

[21] H. Kぴalviぴainen, P. Hirvonen, L. Xu and E. Oja, “Probabilistic and nonprobabilistic Hough transforms: overview and comparison,” Image and Vision Computing, Vol. 13, No. 4, pp. 239–252, 1995.

[22] V. Kyrki and H. Kぴalviぴainen, “Combination of local and global line extraction, ”Real-Time Imaging, Vol. 6, No. 2, pp. 79–91, Apr. 2000.

[23] V. F. Leavers, “Survey: Which Hough transform,” CVGIP: Image Understanding, Vol. 58, No. 2, pp. 250–264, 1993.

[24] Q. Long and T. Kanade, “Affine structure from line correspondences with uncalibrated affine cameras,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 19, No. 8, pp. 834–845, Aug. 1997.

[25] K. Schindler, “Geometry and construction of straight lines in log-polar images,”Computer Vision and Image Understanding, Vol. 103, No. 3, pp. 196-207, Sep. 2006.

[26] T. M. van Veen and F. C. A. Groen, “Discretization errors in the Hough transform,” Pattern Recognition, Vol. 14, No. 1, pp. 137–145, 1981.

[27] L. Xu and E. Oja, “Randomized Hough transform (RHT): Basic mechanisms, algorithms, and computational complexities,” CVGIP: Image Understanding, Vol. 57, No. 2, pp. 131–154, 1993.

[28] L. Xu, E. Oja and P. Kultanan, “A new curve detection method: randomized Hough transforms (RHT),” Pattern Recognition Letters, Vol. 11, No. 5, pp. 331–338, 1990.