近年來，有鑑於更即時且高效率的機器人視覺相關技術之需求漸漸提高，使得各種智慧型偵測與辨識相關的研究迅速地成長。除了所選用之分類器的辨識效能外，一些快速又有效的特徵擷取方法也是左右一個智慧型機器人視覺辨識系統的重要關鍵；有鑑於此，我們在本論文中提出一個高效能的兩階段標記相連元件演算法，它係架構在兩次式掃描的標記流程上，主要創新的地方包括：標記的演算流程與標記關聯表的結構兩大部份。

在標記的演算流程上，我們所提的方法與一般的標記相連演算法最大不同的地方在於：一般的標記相連演算法會在每個物件像素上執行相同的標記步驟，而我們所提的方法會針對不同位置的物件像素來執行不同的標記步驟；藉此，我們可以大幅省去那些因重複執行所產生的多餘時間，進而提升整體的執行效能。

而在標記關聯表上，我們提出一個新的標記關聯表架構，它不僅能記錄以往表格式標記關聯表所能記錄的資訊，藉由我們提出的圓環架構，能有效利用表格欄位，而且只需要兩個一維陣列即可實做完成，比起以往的關聯表架構還少1/3的空間；除此之外，利用我們的擷取程序，可以在不影響整體執行效能的前提下，快速整理標記關聯資訊。

根據實驗結果顯示，在同為一般循序式執行的硬體平台下，我們所提方法的標記相連元件演算法無論在普通的測試圖或者是受雜訊干擾的測試圖都能優於目前學者所提的演算法。

Owing to the demand of more efficient technology about robot vision applications, the researches on intelligent pattern detection and recognition have been rapidly grown in recent years. In addition to that an adaptive pattern classifier may affect recognition results, one of the most important characteristics of an intelligent robot vision system is to employ a quick and efficient pattern extraction method. To achieve such a good, in this thesis, we present an efficient two-phase labeling connected components algorithm based on a two-scan structure.

In the labeling step, unlike conventional labeling algorithms using the same labeling operations for each object pixel for labeling or relation checking, our algorithm executes different labeling operations for each pixel depending on its location in a row of contiguous object pixels. Thus, we can reduce many unnecessary labeling operations and lessen the execution time.

As to the label relation table, we propose a novel table structure similar to a circle to resolve label equivalence between provisional label sets. It not only can record all information as same as conventional label relation tables, but also can reduce 1/3 memory space at most than the other so. The implementation of this structure only requires two 1-D arrays, and we can easily record the relation between provisional labels and their corresponding representative labels by use of our record procedure.

Experimental results reveal that the performance of our algorithm is superior to those of all conventional labeling algorithms for both ordinary and noisy images under the common sequential execution hardware.

[1] R. M. Haralick, “Some neighborhood operations,” in Real Time/Parallel Computing Image Analysis, New York, NY: Plenum, 1981, pp. 11–35.
[2] A. Hashizume, R. Suzuki, H. Yokouchi, H. Horiuchi, and S. Yamamato, “An algorithm of automated RBC classification and its evaluation,” Bio Med. Eng., vol. 28, no. 1, pp. 25–32, 1990.
[3] L. He, Y. Chao, and K. Suzuki, “A run-based two-scan labeling algorithm,” IEEE Trans. on Image Process., vol. 17, no. 5, pp. 749–756, 2008.
[4] L. He, Y. Chao, and K. Suzuki, “A linear-time two-scan labeling algorithm,” in Proc. the IEEE Int. Conf. on Image Process., Texas, USA, vol. 5, pp. 241–244, 2007.
[5] D. R. Lee, S. H. Jin, P. C. Thien, and J. W. Jeon, “FPGA based connected component labeling,” in Proc. the Int. Conf. on Contr. Automat. Syst., Seoul, Korea, pp. 2313–2317, 2007.
[6] R. Jain, R. Kasturi, and B. G. Shunck, Machine Vision, New York, NY: McGraw-Hill, pp. 44–47, 1995.
[7] R. M. Haralick and L. G. Shapiro, Computer and Robot Vision, Reading, MA: Addison-Wesley, vol. I, pp. 28–48, 1992.
[8] R. Lumia, L. Shapiro, and O. Zungia, “A new connected components algorithm for virtual memory computers,” Comput. Vis., Graphics, Image Process., vol. 22, no. 2, pp. 287–300, 1983.
[9] L. He, Y. Chao, K. Suzuki, and K. Wu, “Fast connected-component labeling,” Pattern Recognition, vol. 42, no. 9, pp. 1977–1987, 2009.
[10] K. Suzuki, I. Horiba, and N. Sugie, “Linear-time connected-component labeling based on sequential local operations,” Comput. Vis. Image Understand., vol. 89, no. 1, pp. 1–23, 2003.
[11] K. Suzuki, I. Horiba, N. Sugie, “Fast connected-component labeling based on sequential local operations in the course of forward raster scan followed by backward raster scan,” in Proc. the 15th Int. Conf. Pattern Recognition, Barcelona, Spain, vol. 2, pp. 434–437, 2000.
[12] A. Rosenfeld and A. C. Kak, Digital Picture Processing, 2nd ed., San Diego, CA: Academic Press, vol. 2, 1982.
[13] Y. Shima, T. Murakami, M. Koga, H. Yashiro, and H. Fujisawa, “A high-speed algorithm for propagation-type labeling based on block sorting of runs in binary images,” in Proc. the 10th Int. Conf. on Pattern Recognit., New Jersey, USA, pp. 655–658, 1990.
[14] F. Chang, C. J. Chen, and C. J. Lu, “A linear-time component-labeling algorithm using contour tracing technique,” Comput. Vis. Image Understand., vol. 93, no. 2, pp. 206–220, 2004.
[15] D. H. Ballard and C. M. Brown, Computer Vision, New Jersey, USA: Prentice-Hall, 1982.
[16] A. Rosenfeld and A. C. Kak, Digital Picture Processing, San Diego, CA: Academic Press, pp. 347–349, 1976.
[17] M. Manohar and H. K. Ramapriyan, “Connected component labeling of binary images on a mesh connected massively parallel processor,” Comput. Vis., Graph., Image Process., vol. 45, no. 2, pp. 133–149, 1989.
[18] P. Bhattacharya, “Connected component labeling for binary images on a reconfigurable mesh architectures,” Jour. Syst. Arch., vol. 42, no. 4, pp. 309–313, 1996.
[19] H. Samet and M. Taminen, “Efficient component labeling of images of arbitrary dimension represented by linear bintrees,” IEEE Trans. on Pattern Anal. Mach. Intell., vol. 10, no. 4, pp. 579–586, 1988.
[20] L. W. Tucker, “Labeling connected components on a massively parallel tree machine,” in Proc. the IEEE Conf. on Comput. Vision Pattern Recognit., Miami, FL, pp. 124–129, 1986.
[21] M. B. Dillencourt, H. Samet, and M. Tamminen, “A general approach to connected-component labeling for arbitrary image representations,” Jour. Association for Computing Machinery, vol. 39, no. 2, pp. 253–280, 1992.
[22] H. M. Alnuweiri and V. K. Prasanna, “Parallel architectures and algorithms for image component labeling,” IEEE Trans. on Pattern Anal. Mach. Intell., vol. 14, no. 10, pp. 1024–1034, 1992.
[23] S. Olariu, J. L. Schwing, and J. Zhang, “Fast component libeling and convex hull computation on reconfigurable meshes,” Image Vis. Comput., vol. 11, no. 7, pp. 447–455, 1993.
[24] J. Hecquard and R. Acharya, “Connected component labeling with linear octree,” Pattern Recognit., vol. 24, no. 6, pp. 515–531, 1991.
[25] SIDBA, http://sampl.ece.ohio-state.edu/data/stills/sidba/index.htm
[26] The USC-SIPI Image Database, http://sipi.usc.edu/database/
[27] MR-TIP, http://www.mr-tip.com
[28] N. Otsu, “A threshold selection method from gray-level histograms,” IEEE Trans. on Syst. Man Cybern., vol. 9, no. 1, pp. 62–66, 1979.