臺灣博碩士論文加值系統

影像分割是一種將影像切割成數個具有相同性質區塊的步驟。然而，並無一個標準來定義影像分割應將影像分割至何種程度為止，換句話說影像分割是影像處理中一個難以處理的問題。
在本研究中，我們採用視覺注意模型為輔助，以提出一種以混合評估函數及粒子群最佳化的影像分割技術，我們使用了色彩量化、特徵擷取、小區塊去除、及以粒子群最佳化做區塊合併等四個步驟來產生符合語意的影像分割。我們使用色彩和紋理作為低階影像特徵，並利用人眼視覺系統的特性作為含有影像語意的高階影像特徵。本研究之實驗結果顯示，與其他兩個影像分割方法相比較，所提方法能產生較好的影像分割結果。

Image segmentation can be treated as a process of dividing an image into some constituent regions and each region is homogeneous. However, no standard can be used to define the level of division of image segmentation, i.e., image segmentation is an ill-posed problem in image processing.
In this study, image segmentation using particle swarm optimization (PSO) and a hybrid evaluation function is proposed, in which a visual attention model is employed. The proposed image segmentation approach contains four stages, i.e., color quantization, feature extraction, small region elimination, and region merging using a modified PSO algorithm. Color and texture are used as low-level image features, whereas several properties of the human visual system are used as high-level image semantics. Based on the experimental results obtained in this study, as compared with two comparison methods, the proposed approach will provide the better image segmentation results.

TABLE OF CONTENTS
摘 要 i
ABSTRACT ii
ACKNOWLEDGMENTS iii
TABLE OF CONTENTS iv
LIST OF FIGURES vi
LIST OF TABLES xi
CHAPTER 1 INTRODUCTION 1
1.1 Motivation 1
1.2 Survey of Related Researches 2
1.3 Thesis Organization 5
CHAPTER 2 IMAGE SEGMENTATION METHODS 6
2.1 Introduction to Image Segmentation Methods 6
2.2 Feature Clustering Using Particle Swarm Optimization 6
2.3 Mean Shift Algorithm 9
2.4 Visual Features in Image Segmentation 12
CHAPTER 3 PROPOSED IMAGE SEGMENTATION APPORACH 14
3.1 Overview of the Proposed Approach 14
3.2 Color Quantization and Feature Extraction 15
3.2.1 Color quantization 15
3.2.2 Feature Extraction 16
3.3 Image Segmentation Using Modified Particle Swarm Optimization 22
CHAPTER 4 EXPERIMENTAL RESULTS 28
CHAPTER 5 DISCUSSIONS AND CONCLUSIONS 71
5.1 Discussions 71
5.2 Conclusions 72
REFERENCES 73

LIST OF FIGURES
Fig. 2.1 The original PSO algorithm 8
Fig. 2.2 The mean shift algorithm 11
Fig. 2.3 Visualization of mean-shift based filtering and segmentation for an image [8]: (a) input image, (b) mean shift paths for pixels, (c) results after smoothing filtering, (d) segmentation results 12
Fig. 3.1 The proposed image segmentation approach 15
Fig. 3.2 (a) An input image and (b) the corresponding class-map of the quantized image with 13 color vectors 17
Fig. 3.3 Local binary pattern of an illustrated texture unit [54] 19
Fig. 3.4 The texture spectrum of the input image shown in Fig. 3.2(a) 19
Fig. 3.5 General architecture of the visual attention model [10]. 20
Fig. 3.6 The saliency map of Fig. 3.2(a) 22
Fig. 3.7 The salient regions of the quantized image in Fig. 3.2(b) 22
Fig. 3.8 The small region elimination procedure 23
Fig. 3.9 (a) The class-map of the quantized image after small region elimination; (b) coarse crude segmentation of the input image in Fig. 3.2(a) 24
Fig. 3.10 Fine segmentation using the modified PSO algorithm 26
Fig. 3.11 The segmentation results of the proposed approach 27
Fig. 4.1 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 30
Fig. 4.2 (a)-(b) Image segmentation by DCPSO with PRI = 0.7782; (c)-(d) image segmentation by the mean shift approach with PRI = 0.7979; (e)-(f) image segmentation by the proposed approach with PRI = 0.8121 31
Fig. 4.3 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 32
Fig. 4.4 (a)-(b) Image segmentation by DCPSO with PRI = 0.7068; (c)-(d) image segmentation by the mean shift approach with PRI = 0.8735; (e)-(f) image segmentation by the proposed approach with PRI = 0.8863 33
Fig. 4.5 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 34
Fig. 4.6 (a)-(b) Image segmentation by DCPSO with PRI = 0.9034; (c)-(d) image segmentation by the mean shift approach with PRI = 0.9168; (e)-(f) image segmentation by the proposed approach with PRI = 0.9147 35
Fig. 4.7 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 36
Fig. 4.8 (a)-(b) Image segmentation by DCPSO with PRI = 0.8611; (c)-(d) image segmentation by the mean shift approach with PRI = 0.8835; (e)-(f) image segmentation by the proposed approach with PRI = 0.9164 37
Fig. 4.9 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 38
Fig. 4.10 (a)-(b) Image segmentation by DCPSO with PRI = 0.8204; (c)-(d) image segmentation by the mean shift approach with PRI = 0.9729; (e)-(f) image segmentation by the proposed approach with PRI = 0.9812 39
Fig. 4.11 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 40
Fig. 4.12 (a)-(b) Image segmentation by DCPSO with PRI = 0.6909; (c)-(d) image segmentation by the mean shift approach with PRI = 0.6915; (e)-(f) image segmentation by the proposed approach with PRI = 0.8547 41
Fig. 4.13 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 42
Fig. 4.14 (a)-(b) Image segmentation by DCPSO with PRI = 0.6647; (c)-(d) image segmentation by the mean shift approach with PRI = 0.7489; (e)-(f) image segmentation by the proposed approach with PRI = 0.8322 43
Fig. 4.15 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 44
Fig. 4.16 (a)-(b) Image segmentation by DCPSO with PRI = 0.7554; (c)-(d) image segmentation by the mean shift approach with PRI = 0.8793; (e)-(f) image segmentation by the proposed approach with PRI = 0.8564 45
Fig. 4.17 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 46
Fig. 4.18 (a)-(b) Image segmentation by DCPSO with PRI = 0.7140; (c)-(d) image segmentation by the mean shift approach with PRI = 0.8205; (e)-(f) image segmentation by the proposed approach with PRI = 0.8829 47
Fig. 4.19 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 48
Fig. 4.20 (a)-(b) Image segmentation by DCPSO with PRI = 0.5754; (c)-(d) image segmentation by the mean shift approach with PRI = 0.6260; (e)-(f) image segmentation by the proposed approach with PRI = 0.6936 49
Fig. 4.21 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 50
Fig. 4.22 (a)-(b) Image segmentation by DCPSO with PRI = 0.8870; (c)-(d) image segmentation by the mean shift approach with PRI = 0.9281; (e)-(f) image segmentation by the proposed approach with PRI = 0.9403 51
Fig. 4.23 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 52
Fig. 4.24 (a)-(b) Image segmentation by DCPSO with PRI = 0.6394; (c)-(d) image segmentation by the mean shift approach with PRI = 0.7985; (e)-(f) image segmentation by the proposed approach with PRI = 0.9322 53
Fig. 4.25 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 54
Fig. 4.26 (a)-(b) Image segmentation by DCPSO with PRI = 0.5437; (c)-(d) image segmentation by the mean shift approach with PRI = 0.7654; (e)-(f) image segmentation by the proposed approach with PRI = 0.8215 55
Fig. 4.27 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 56
Fig. 4.28 (a)-(b) Image segmentation by DCPSO with PRI = 0.6309; (c)-(d) image segmentation by the mean shift approach with PRI = 0.7029; (e)-(f) image segmentation by the proposed approach with PRI = 0.9937 57
Fig. 4.29 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 58
Fig. 4.30 (a)-(b) Image segmentation by DCPSO with PRI = 0.4745; (c)-(d) image segmentation by the mean shift approach with PRI = 0.5747; (e)-(f) image segmentation by the proposed approach with PRI = 0.8886 59
Fig. 4.31 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 60
Fig. 4.32 (a)-(b) Image segmentation by DCPSO with PRI = 0.7678; (c)-(d) image segmentation by the mean shift approach with PRI = 0.9265; (e)-(f) image segmentation by the proposed approach with PRI = 0.9361 61
Fig. 4.33 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 62
Fig. 4.34 (a)-(b) Image segmentation by DCPSO with PRI = 0.3217; (c)-(d) image segmentation by the mean shift approach with PRI = 0.8422; (e)-(f) image segmentation by the proposed approach with PRI = 0.8663 63
Fig. 4.35 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 64
Fig. 4.36 (a)-(b) Image segmentation by DCPSO with PRI = 0.7640; (c)-(d) image segmentation by the mean shift approach with PRI = 0.9589; (e)-(f) image segmentation by the proposed approach with PRI = 0.9657 65
Fig. 4.37 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 66
Fig. 4.38 (a)-(b) Image segmentation by DCPSO with PRI = 0.7413; (c)-(d) image segmentation by the mean shift approach with PRI = 0.5120; (e)-(f) image segmentation by the proposed approach with PRI = 0.7774 67
Fig. 4.39 (a) The original color image; (b)-(f) the corresponding five ground truth hand segmentations [37] 68
Fig. 4.40 (a)-(b) Image segmentation by DCPSO with PRI = 0.8004; (c)-(d) image segmentation by the mean shift approach with PRI = 0.7498; (e)-(f) image segmentation by the proposed approach with PRI = 0.9331 69

LIST OF TABLES
Table 4.1 PRI statistics of DCPSO, the mean shift approach, and the proposed approach (Proposed) for 20 test images 70

[1] N. R. Pal and S. K. Pal, “A review on image segmentation techniques,” Pattern Recognition, vol. 26, no. 9, pp. 1277-1294, Sept. 1993.
[2] R. C. Gonzalez and R. E. Woods, Digital Image Processing. 2nd Edition, New Jersey: Prentice Hall, 2002.
[3] Y. Deng and B. S. Manjunath, “Unsupervised segmentation of color-texture regions in images and video,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 23, no. 8, pp. 800-810, Aug. 2001.
[4] W. Tao, H. Jin, and Y. Zhang, “Color image segmentation based on mean shift and normalized cuts,” IEEE Trans. on Systems, Man, and Cybernetics, vol. 37, no. 5, pp. 1382-1389, Oct. 2007.
[5] W. M. Smeulders, et al., “Content-based image retrieval at the end of the early years,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 22, no. 12, pp. 1349-1379, Dec. 2000.
[6] M. E. Farmer and A. K. Jain, “A wrapper-based approach to image segmentation and classification,” IEEE Trans. on Image Processing, vol. 14, no. 12, pp. 2060-2072, Dec. 2005.
[7] J. Chen, T. N. Pappas, A. Mojsilovic, and B. E. Rogowitz, “Adaptive perceptual color-texture image segmentation,” IEEE Trans. on Image Processing, vol. 14, no. 10, pp. 1524-1536, Oct. 2005.
[8] D. Comaniciu and P. Meer, “Mean shift: a robust approach toward feature space analysis,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 24, no. 5, pp. 603-619, May 2002.
[9] R. Unnikrishnan, C. Pantofaru, and M. Hebert, “Toward objective evaluation of image segmentation algorithms,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 29, no. 6, pp. 929-944, Jun. 2007.
[10] L. Itti, C. Koch, and E. Niebur, “A model of saliency-based visual attention for rapid scene analysis,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 20, no. 11, pp. 1254-1259, Nov. 1998.
[11] U. Rutishauser, D. Walther, C. Koch, and P. Perona, “Is bottom-up attention useful for object recognition,” in Proc. of IEEE Int. Conf. on Computer Vision and Patter Recognition, Jun. 2004, pp. 37-44.
[12] K. Haris, S. N. Efstratiadis, N. Maglaveras, and A. K. Katsaggelos, ”Hybrid image segmentation using watersheds and fast region merging,” IEEE Trans. on Image Processing, vol. 7, no. 12, pp. 1684-1699, Dec. 1998.
[13] S. Das, A. Abraham, and A. Konar, “Spatial information based image segmentation using a modified particle swarm optimization algorithm,” in Proc. of 6th IEEE Int. Conf. on Intelligent Systems Design and Applications, Oct. 2006, pp. 438-444.
[14] W. Y. Ma and B. S. Manjunath, “Edge flow: a framework of boundary detection and image segmentation,” in Proc. of IEEE Int. Conf. on Computer Vision and Patter Recognition, Jun. 1997, pp. 744-749.
[15] S. Wang and J. M. Siskind, “Image segmentation with ratio cut,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 25, no. 6, pp. 675-690, Jun. 2003
[16] Z. Y. Wu and R. Leahy, “An optimal graph theoretic approach to data clustering: theory and its application to image segmentation,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 15, no. 11, pp. 1101-1113, Nov. 1993.
[17] J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888-905, Aug. 2000.
[18] X. Jin and C. H. Davis, “A genetic image segmentation algorithm with a fuzzy-based evaluation function,” in Proc. of 12th IEEE Int. Conf. on Fuzzy Systems, May 2003, pp. 938-943.
[19] M. G. H. Omran, A. Salman, and A. Engelbrecht, “Dynamic clustering using particle swarm optimization with application in image segmentation,” Pattern Analysis and Applications, vol. 8, no. 4, pp. 332-344, Nov. 2005.
[20] B. S. Manjunath, J.-R. Ohm, V. V. Vasudevan, and A. Yamada, “Color and texture descriptors,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 11, no. 6, pp. 703-715, Jun. 2001.
[21] B. Bhanu, S. Lee, and S. Das, “Adaptive image segmentation using genetic and hybrid search method,” IEEE Trans. on Aerospace Electronic Systems, vol. 31, no. 4, pp. 1268-1291, Oct. 1995.
[22] A. K. Jain, M. N. Murty, and P. J. Flynn, “Data clustering: a review,” ACM Computing Surveys, vol. 31, no. 3, pp. 264-323, Sept. 1999.
[23] D. W. Jacobs, D. Weinshall, and Y. Gdalyahu, “Classification with nonmetric distance: image retrieval and class representation,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 22, no. 6, pp. 583-600, Jun. 2000.
[24] A. K. Jain and D. Zongker, “Representation and recognition of handwritten digits using deformable templates,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 19, no. 12, pp. 1386-1391, Dec. 1997.
[25] J. T. Tou and R. C. Gonzalez, Pattern Recognition Principles. London: Addision-Wesley, 1974
[26] M. M. Trivedi and J. C. Bezdek, “Low-level segmentation of aerial images with fuzzy clustering,” IEEE Trans. on Systems, Man, and Cybernetics, vol. 16, no. 4, pp. 589-598, Jul. 1986.
[27] V. Grau, et al., “Improved watershed transform for medical image segmentation using prior information,” IEEE Trans. on Image Processing, vol. 23, no. 4, pp. 447-458, Apr. 2004.
[28] L. Vincent and P. Soille, “Watershed in digital spaces: an efficient algorithm based on immersion simulation,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 13, no. 6, pp. 583-597, Jun. 1991.
[29] S. Makrogiannis, G. Economou, and S. Fotopoulos, “A region dissimilarity relation that combines feature-space and spatial information for color image segmentation,” IEEE Trans. on Systems, Man, and Cybernetics B, Cybernetics, vol. 35, no. 1, pp. 44-53, Feb. 2005.
[30] J. Canny, “Computational approach to edge detection,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 8, no. 6, pp. 679-698, Nov. 1986.
[31] S. Horowitz and T. Pavlidis, “Picture segmentation by a tree traversal algorithm,” Journal of Assoc. Comput. Mach., vol. 23, pp. 368-388, Apr. 1976.
[32] O. J. Morris, J. Lee and A. G. Constantinidies, “Graph theory for image analysis: an approach based on the shortest spanning tree,” in Proc. of Inst. Electr. Eng., vol. 133, Apr. 1986, pp. 146–152.
[33] S. X. Yu and J. Shi, “Multiclass spectral clustering,” in Proc. of IEEE Int. Conf. on Computer Vision, Oct. 2003, pp. 313-319.
[34] Y. Weiss, “Segmentation using eigenvectors: a unifying view,” in Proc. of IEEE Int. Conf. on Computer Vision, Sept. 1999, pp. 957-982.
[35] Y. Shi and R. Eberhart, “A modified particle swarm optimizer,” in Proc. of IEEE Int. Conf. on Evolutionary Computation, May 1998, pp. 69-73.
[36] B. Bhanu, S. Lee, and J. Ming, “Adaptive image segmentation using a genetic algorithms,” IEEE Trans. on Systems, Man, and Cybernetics, vol. 25, no. 12, pp. 1543-1567, Dec. 1995.
[37] D. Martin, C. Fowlkes, D. Tal, and J. Malik, “A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics,” in Proc. of IEEE Int. Conf. on Computer Vision, Jul. 2001, pp. 416-425.
[38] J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proc. of IEEE Int. Conf. on Neural Networks, Dec. 1995, pp. 1942-1948.
[39] D. Bratton and J. Kennedy, “Defining a standard for particle swarm optimization,” in Proc. of IEEE Symp. on Swarm Intelligence, Apr. 2007, pp. 120-127.
[40] J. Kennedy and R. Mendes, “Neighborhood topologies in fully-informed and best-of-neighborhood particle swarms,” in Proc. of IEEE Int. Workshop on Soft Computing in Industrial Applications, Jun. 2003, pp. 45-50.
[41] J. Kennedy, “Some issues and practices for particle swarms,” in Proc. of IEEE Symp. on Swarm Intelligence, Apr. 2007, pp. 162-169.
[42] F. van den Bergh and A. P. Engelbrecht, “A cooperative approach to particle swarm optimization,” IEEE Trans. on Evolutionary Computation, vol. 8, no. 3, pp. 225-239, Jun. 2004.
[43] J. J. Liang, A. K. Qin, P. N. Suganthan, and S. Baskar, “Comprehensive learning particle swarm optimizer for global optimization of multimodal functions,” IEEE Trans. on Evolutionary Computation, vol. 10, no. 3, pp. 281-295, Jun. 2006.
[44] M. Scheutz, “Real-time hierarchical swarms for rapid adaptive multi-level pattern detection and tracking,” in Proc. of IEEE Symp. on Swarm Intelligence, Apr. 2007, pp. 234-241.
[45] A. Ratnaweera, S. K. Halgamuge, and H. C. Watson, “Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients,” IEEE Trans. on Evolutionary Computation, vol. 8, no. 3, pp. 240-255, Jun. 2004.
[46] S. C. M. Cohen and L. N. de Castro, “Data clustering with particle swarms,” in Proc. of IEEE Congress on Evolutionary Computation, Jul. 2006, pp. 1792-1798.
[47] D. van der Merwe and A. P. Engelbrecht, “Data clustering using particle swarm optimization,” in Proc. of IEEE Congress on Evolutionary Computation, Dec. 2003, pp. 215-220.
[48] K. Chandramouli and E. Izquierdo, “Image classification using chaotic particle swarm optimization,” in Proc. of IEEE Int. Conf. on Image Processing, Oct. 2006, pp. 3001-3004.
[49] Y. Owechko and S. Medasani, “A swarm-based volition/attention framework for object recognition,” in Proc. of IEEE Int. Conf. on Computer Vision and Pattern Recognition, Jun. 2005, pp. 91-98.
[50] P. Saisan, S. Medasani, and Y. Owechko, “Multi-view classifier swarms for pedestrian detection and tracking,” in Proc. of IEEE Inf. Conf. on Computer Vision and Pattern Recognition, Jun. 2005, pp. 18-25
[51] Y. Owechko, S. Medasani, and N. Srinivasa, “Classifier swarms for human detection in infrared imagery,” in Proc. of IEEE Int. Conf. on Computer Vision and Pattern Recognition, Jun. 2004, pp. 121-127.
[52] L. Anton-Canalis, M. Hernandez-Tejera, and E. Sanchez-Nielsen, “Particle swarms as video sequence inhabitants for object tracking in computer vision,” in Proc. of the 6th IEEE Int. Conf. on Intelligent Systems Design and Applications, Oct. 2006, pp. 604-609.
[53] S. K. Weng, C. M. Kuo, and W. C. Kang, “Unsupervised texture segmentation using color quantization and color feature distributions,” in Proc. of IEEE Int. Conf. on Image Processing, Sept. 2005, pp. 1136-1139.
[54] T. Ojala, M. Petrou, and D. Harwood, “A comparative study of texture measures with classification based on feature distribution,” Pattern Recognition, vol. 29, no. 1, pp. 51-59, 1996.
[55] Y. Cheng, “Mean shift, mode seeking, and clustering,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 17, no. 8, pp. 790-799, Aug. 1995.
[56] R. H. Turi, “Clustering-based colour image segmentation,” PhD Thesis, Monash University, Australia, 2001.