臺灣博碩士論文加值系統

影像切割在影像處理為一大挑戰工作，在影像分析和圖像識別的前處理極為重要，並決定了分析之最後結果的品質。影像切割是用來把一張影像切成好多不同且非重疊的同質區域，在此同質區域基於不同的條件像是灰階值、顏色或紋理，而組成。因此，我們希望去找出一些新的切割演算法去滿足不同的需求。
在這篇論文中，首先我們簡單介紹快速掃描演算法(fast scanning algorithm)，它的每個像素只需要被處理一次。基於快速掃描演算法，我們改變它的距離區間，並加入了邊緣資訊，然後使原本不能分開的兩個區域，能夠分成兩個不同的區塊。模擬結果顯示我們的演算法使切割結果變的更好。
從人類的觀點，現存的切割演算法之切割結果不是足夠好，或者可以說，它與實物匹配(matching physical objects)能力不好。在此我們結合優角(大於180度的角)運算以及使用簡單方法去找代表點。實驗證明我們的方法改善了現存方法的實物匹配能力。此外，我們演算法的處理時間比使用形態學運算更快。
由於物體表面的明亮度改變，陰影和亮光對於電腦視覺研究者來說，都是極為困難的挑戰。對於很多的影像分析和應用，像是物件抓取和描述來說，陰影干擾是基本要處理的工作。此外，對於影像測量上物體、陰影和鏡面反射的幾何性質變異極大，因此，單一材料反射率的切割也是相當具有挑戰性的問題。
換句話說，對於影像分析來說，陰影切割是一重要步驟。基於快速掃描演算法，我們提出一正規化方法去解決陰影和亮光所產生的問題。模擬結果顯示我們的演算法可以成功幫助我們切割含有陰影的影像。此外，我們演算法對於含有陰影的影像之物體與背景之切割完整性，比其它存在演算法好。
顯著區域偵測被使用在很多方面，像是物件識別、自適性壓縮技術和物件切割。在此論文中，我們介紹一顯著區域偵測的方法，並用山脊分佈分析(Ridge-based Analysis of Distributions (RAD)) 演算法以及快速掃描演算法當作預切割的方法。山脊分佈分析演算法結合物理、特徵方法，以及單一材料反射率的分佈之觀察。
最後，我們利用正確解答的圖形資料庫，並使用不同預切割的方法包括山脊分佈分析演算法、快速掃描演算法，以及平均位移演算法(mean shift algorithm)，去計算精確率(precision)和召回率(recall)。實驗結果證明在精確率接近的情況下，不論使用固定或是適應性參數，使用快速掃描演算法的召回率皆優於山脊分佈分析演算法與平均位移演算法。

Image segmentation is a big challenging task in image processing. Moreover, it isvery important pre-processing in image analysis and pattern recognition, and determinesthe quality of the final result of analysis. A process of partitioning an image into different non-overlapping homogeneous regions is called image segmentation, where
the homogeneous regions may be composed based on different criteria such as gray-level, color or texture. Therefore, we hope to find and propose some new segmentation algorithms for satisfying various requirements.
In the thesis, first of all, we briefly introduce the fast scanning algorithm that eachpixel is processed only once. Based on the fast scanning algorithm, we change its
distance interval and add in the edge information which can make the two original inseparable regions divide into two different regions. The simulation results show that our algorithm makes the segmentation result become be better.
From human’s point of view, the segmentation result of the existing segmentation algorithm is not good enough, or to be precise, its ability for matching physical objects
is not good. Here we combine the reflex angle operation with the method of finding representative points which a simple method. The experimental results show that the
improved method improves the existing segmentation algorithm’s the ability for matching physical objects. Moreover, the processing time of our algorithm is faster than using the morphology operation.
Due to variance in the brightness on the surfaces of the objects under consideration, shadows and highlights present a challenge to the computer vision researchers. Shadows
interfere with fundamental tasks in many image analysis and interpretation applications such as object extraction and description. Furthermore, owing to the great variation in
image measurements caused by the geometry of the object, shadows, and specularities, the segmentation of a single material reflectance is a quite challenging problem.
In a word, shadow segmentation is an important step in image analysis. We propose normalized method to solve the shadow and highlight problem based on the fast scanning algorithm. The simulation results show that our algorithm can successfully help us to segment the shadowed images. Moreover, the completeness of the segmentation results of the object and the background of the shadowed images are
better for our algorithm than the other existing algorithms.
Salient region detection is used in many applications, such as object recognition, adaptive compression, and object segmentation. We introduce a method for salient
region detection in the thesis, and use the Ridge-based Analysis of Distributions (RAD) and the fast scanning algorithm for the pre-segmentation algorithm. The RAD algorithm combines the strengths of physics with feature-based methods, and is based on the
observation that the distribution of single material reflectance.
Finally, we compare the salient object segmentation result of using the RAD and the fast scanning algorithm with the mean shift segmentation algorithm and calculate
the precision and recall by means of the ground truth image database. The experimental results show that no matter using fixed or adaptive parameters, the recall values of using the fast scanning algorithm are better than using the RAD or mean shift segmentation algorithm under the close precision value condition.

口試委員會審定書 #
誌謝 i
中文摘要 iii
ABSTRACT v
CONTENTS vii
LIST OF FIGURES xi
LIST OF TABLES xxi
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Existing Segmentation Methods 1
1.3 Proposed Method 4
1.4 Context Summary 5
Chapter 2 Overview of Existing Segmentation Methods 7
2.1 Thresholding 8
2.1.1 Concept of Thresholding 8
2.1.2 Simulation Results and Discussions 9
2.2 K-means Clustering Algorithm 10
2.2.1 Concept of K-means Clustering Algorithm 10
2.2.2 Simulation Results and Discussions 12
2.3 Region Growing Algorithm 13
2.3.1 Concept of Region Growing Algorithm 13
2.3.2 Seeded Region Growing (SRG) Algorithm 14
2.3.3 Unseeded Region Growing (USRG) Algorithm 16
2.3.4 Simulation Results and Discussions 17
2.4 Mean Shift 20
2.4.1 Concept of Mean Shift 20
2.4.2 Mean Shift for Image Segmentation 23
2.4.3 Simulation Results and Discussions 24
2.5 Watershed Algorithm 27
2.5.1 Concept of Watershed Algorithm 27
2.5.2 Simulation Results and Discussions 28
2.6 Fast Scanning Algorithm 30
2.6.1 Concept of Fast Scanning Algorithm 30
2.6.2 Simulation Results and Discussions 36
2.7 Performance Comparison 39
Chapter 3 Fast Scanning Algorithm with Horizontal/Vertical Difference 45
3.1 Distance Interval Change of Fast Scanning Algorithm 45
3.1.1 Concept of Distance Interval Change of Fast Scanning Algorithm 45
3.1.2 Fast Scanning Algorithm by Using Euclidean Distance for One Variable 48
3.1.3 Fast Scanning Algorithm by Using Euclidean Distance for Three Variables 49
3.1.4 Simulation Results and Discussions 49
3.2 Fast Scanning Algorithm with Horizontal/Vertical Difference 53
3.2.1 Concept of Fast Scanning Algorithm with Horizontal/Vertical Difference 53
3.2.2 Fast Scanning Algorithm with Horizontal/Vertical Difference for Gray-level Images 54
3.2.3 Fast Scanning Algorithm with Horizontal/Vertical Difference for Color Images 56
3.3 Simulation Results and Discussions 57
3.4 Performance Comparison 63
Chapter 4 Improvement of Image Segmentation Algorithm Using Reflex Angle 73
4.1 Finding Representative Points 75
4.2 Concept of Reflex Angle 77
4.3 Definition of Criterion 79
4.4 Using Reflex Angle to Improve Segmentation Algorithm 83
4.5 Improvement of Image Segmentation Algorithm Using Morphology 86
4.5.1 Binary Morphology 86
4.5.2 Gray-level Morphology 88
4.6 Simulation Results and Discussions 89
4.7 Summarization 95
Chapter 5 Improved Segmentation Techniques for Shadowed Images 97
5.1 What is a shadow? 98
5.2 Improved Segmentation Techniques for Shadowed Images 99
5.3 Simulation Results and Discussions 101
5.4 Summarization 117
Chapter 6 Applying Salient Region Detection in Image Segmentation 119
6.1 Overview of Existing Saliency Methods 119
6.2 Frequency Domain Analysis of Saliency Detectors 121
6.3 How to Compute Saliency Maps 124
6.4 Salient Region Segmentation Algorithm 125
6.5 Simulation Results and Discussions 127
6.6 Summarization 135
Chapter 7 Conclusions and Future Work 137
7.1 Conclusions 137
7.2 Future Work 138
7.2.1 Using Other Color Space for Shadowed Images 139
7.2.2 Using Other Normalized Color Representation Space for Shadowed Images 140
7.2.3 Changing Salient Maps or Using Other Segmentation for Pre-segmentation 140
REFERENCE 143

REFERENCE
A.Thresholding
[1]R. C. Gonzalez, and R. E. Woods, "Chapter 10: Image Segmentation," Digital Image Processing 3rd Ed., pp.738-763, Prentice-Hall, 2008.
[2]S. Arora, J. Acharya, A. Verma, and Prasanta K. Panigrahi, "Multilevel thresholding for image segmentation through a fast statistical recursive algorithm," Pattern Recognition Letters, vol. 29, Issue 2, pp. 119-125, Jan. 2008.
[3]F. Yan, H. Zhang, and C. R. Kubeb, "A multistage adaptive thresholding method," Pattern Recognition Letters, vol. 26, Issue 8, pp. 1183-1191, June 2005.
[4]F. Kurugollu, B. Sankur, and A.E. Harmanci, "Color Image Segmentation Using Histogram Multithresholding and Fusion," Image and Vision Computing, vol. 19, issue 13, pp. 915-928, Nov. 2001.

B.K-means Clustering Algorithm
[5]E. Alpaydin, "Chapter 7: Clustering," Introduction to Machine Learning, pp.135-139, The MIT Press, 2004.
[6]A. Ng, "CS 229 Lecture Notes 7a." http://www.stanford.edu/class/cs229/notes/
[7]L. Lucchese and S. K. Mitra, "Color image segmentation: A state-of-art survey," in Proc. Indian Nat. Sci. Acad. (INSA-A), vol. 67-A, New Delhi, India, pp. 207–221, Mar. 2001.

C.Region Growing Algorithm
[8]R. Adams and L. Bischof, "Seeded region growing," in IEEE Trans. Pattern Anal. Mach. Intelligence, vol. 16, no.6, pp. 641–647, June 1994.
[9]Jianping Fan, D.K.Y. Yau, A.K. Elmagarmid, and W.G. Aref, "Automatic image segmentation by integrating color-edge extraction and seeded region growing," in IEEE Trans. Image Processing, vol. 10, no.10, pp. 1454–1466, Oct. 2001.
[10]R. C. Gonzalez, and R. E. Woods, "Chapter 10: Image Segmentation," Digital Image Processing 3rd Ed., pp.763-766, Prentice-Hall, 2008.
[11]Z. Lin, J. Jin and H. Talbot, "Unseeded region growing for 3D image segmentation, " in ACM International Conference Proceeding Series, vol. 9, pp. 31-37, 2000.

D.Mean Shift
[12]Yizong Cheng, "Mean Shift, Mode Seeking, and Clustering," in IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 8, pp. 790-799, Aug. 1995.
[13]Dorin Comaniciu and Peter Meer, "Mean Shift: A Robust Approach Toward Feature Space Analysis," in IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 5, pp. 603-619, May 2002.
[14]M. V. Sudhamani and Dr. C. R. Venugopal "Segmentation of Color Images using Mean Shift Algorithm for Feature Extraction," in IEEE 9th International Conference on Information Technology, 2006.
[15]D. Comaniciu and P. Meer, "Mean Shift Analysis and Applications," in Proc. the 7th IEEE Intl. Conf. on Computer Vision, vol.2, pp.1197-1203, 1999.
[16]D. Comaniciu, V. Ramesh, and P. Meer, "The variable bandwidth mean shift and data-driven scale selection," in Proc. 8th Intl. Conf. on Computer Vision, vol. 1, pp. 438–445, July 2001.
[17]Dorin Comaniciu and Peter Meer, "Mean Shift: A Robust Approach Toward Feature Space Analysis, " in IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 5, pp. 603-619, May 2002.

E.Watershed Algorithm
[18]R. C. Gonzalez, and R. E. Woods, "Chapter 10: Image Segmentation," Digital Image Processing 3rd Ed., pp.769-778, Prentice-Hall, 2008.
[19]L. Najiman and M. Schmitt, "Geodesic saliency of watershed contours and hierarchical segmentation," IEEE Trans. Pattern Anal. Machine Intell., vol. 18, pp. 1163–1173, 1996.
[20]S. Beucher, "The watershed transformation applied to image segmentation, " in Proc. 10th Pfefferkorn Conf. on Signal and Image Processing in Microscopy and Microanalysis, Cambridge, U.K., pp. 299–314, Sept. 16–19, 1991.
[21]S. Beucher, "Watershed, hierarchical segmentation and waterfall algorithm," in Mathematical Morphology and its Applications to Image Processing, pp. 69-76, Kluwer Academic Publishers, 1994.

F.Fast Scanning Algorithm
[22]C. J. Kuo, "A New Compression-Oriented Fast Image Segmentation Technique," M.S. thesis, National Taiwan University, Taipei, Taiwan, R.O.C, 2009.
[23]W. C. Hong, "Improvement Techniques for Fast Segmentation and Compression for Boundary Information," M.S. thesis, National Taiwan University, Taipei, Taiwan, R.O.C, 2010.

G.Other Segmentation
[24]H. D. Cheng, X. H. Jiang, Y. Sun, and J. L. Wang, "Color image segmentation: Advances and prospects," Pattern Recognition, vol. 34, issue 12, pp. 2259-2281, Dec. 2001.
[25]L. Lucchese and S. K. Mitra, "Color image segmentation: A state-of-art survey, " in Proc. Indian Nat. Sci. Acad. (INSA-A), vol. 67-A, pp. 207–221, New Delhi, India, Mar. 2001.
[26]H. Choi and R. G. Baraniuk, "Multiscale image segmentation using wavelet-domain hidden Markov models," IEEE Trans. Image Processing, vol. 10, issue 9, Sept. 2001.
[27]J. Shi and J. Malik, "Normalized Cuts and Image Segmentation," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888-905, Aug. 2000.
[28]W. Wei and Y. Xin, "Rapid, man-made object morphological segmentation for aerial images using a multi-scaled, geometric image analysis," Image and Vision Computing, vol. 28, issue 4, pp. 626-633, Apr. 2010.
[29]A. Yezzi, A. Tsai, and A. Willsky, "A Fully Global Approach to Image Segmentation via Coupled Curve Evolution Equations," Journal of visual Communication and Image Representation, vol. 13, issues 1-2, pp. 195-216, March 2002.
[30]W. Y. Ma and B. S. Manjunath, "EdgeFlow: A technique for boundary detection and image segmentation," IEEE Trans. Image Processing, vol. 9, issue 8, pp. 1375-1388, Aug. 2000.
[31]P. Felzenszwalb and D. Huttenlocher, "Efficient graph-based image segmentation," International Journal of Computer Vision, vol. 59, no. 2, pp. 167–181, 2004.
[32]J. Chen, T. N. Pappas, A. Mojsilovic, and B. E. Rogowitz, "Adaptive Perceptual Color-Texture Image Segmentation," IEEE Trans. Image Proc., vol. 14, no. 10, pp. 1524–1536, Oct. 2005.
[33]C. Botte-Lecocq, O. Losson, and L. Macaire, "Color image segmentation by compacigram analysis," in Proceedings of the 14th International Conference on Image Analysis and Processing, pp. 212–215, Modena, Italy, Sep. 2007.
[34]Dr. H. B. Kekre and Saylee Gharge, "SAR Image Segmentation using co-occurrence matrix and slope magnitude," ACM International Conference on Advances in Computing, Communication and Control (ICAC3-2009), pp. 357-362, Fr. Conceicao Rodrigous College of Engg., Mumbai, 23-24 Jan 2009. Available on ACM portal.
[35]H. Deng and D. A. Clausi, "Unsupervised image segmentation using a simple MRF model with a new implementation scheme," Pattern Recognition, vol. 37, no. 12, pp. 2323–2335, Dec. 2004.
[36]J. Z. Wang, J. Li, R. M. Gray, and G. Wiederhold, "Unsupervised multiresolution segmentation for images with low depth of field," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, issue 1, pp. 85–90, Jan. 2001.

H.Edge Detection
[37]R. C. Gonzalez, and R. E. Woods, "Chapter 10: Image Segmentation," Digital Image Processing 3rd Ed., pp.769-778, Prentice-Hall, 2008.
[38]A. Rosenfeld and M. Thurston, "Edge and curve detection for visual scene analysis," IEEE Trans. Cornput., vol. C-20, issue 5, May 1971.
[39]V. Torre and T. Poggio, "On Edge Detection," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, pp. 147-163, March 1986.
[40]L. S. Davis, "A survey of edge detection techniques," Cornput. Graphics Image Process., vol. 4, issue 3, pp. 248-270, Sept. 1975.
[41]J. Shen and S. Castan, "An optimal linear operator for step edge detection," Computer Vision, Graphics and Image Processing, vol. 54, issue 2, pp.112–133, March 1992.
[42]J. H. Elder and S. W. Zucker, "Local Scale Control for Edge Detection and Blur Estimation," IEEE Trans. Pattern Analysis and Machine Analysis, vol. 20,issue 7, pp. 699-716, July 1998.
[43]X. Jiang and H. Bunke, "Edge detection in range images based on scan line approximation," Computer Vision and Image Understanding, vol. 73, issue 2, pp. 183-199, Feb. 1999.
[44]W.Y. Ma and B.S. Manjunath, "Edge Flow: A Framework of Boundary Detection and Image Segmentation," Proc. Computer Vision and Pattern Recognition, pp. 744-749, June 1997.
[45]J. S. J. Lee, R. M. Haralick, and L. G. Shapiro, "Morphologic edge detection," IEEE Trans. Rob. Autom., vol. RA-3, no. 2, pp. 142-156, Apr. 1987.
[46]A. Cumani, "Edge detection in multispectral images," CVGIP: Graph. Models Image Processing, vol. 53, issue 1, pp. 40-51, Jan. 1991.

I.Reflex Angle
[47]W. C. Hong, "Improvement Techniques for Fast Segmentation and Compression for Boundary Information," M.S. thesis, National Taiwan University, Taipei, Taiwan, R.O.C, 2010.
[48]R. C. Gonzalez, and R. E. Woods, "Chapter 9: Morphological Image Processing," Digital Image Processing 3rd Ed., pp.738-763, Prentice-Hall, 2008.
J.Improved Segmentation Techniques for Shadowed Images
[49]S. Shafer, "Using color to separate reflection components," COLOR Research and Application, vol. 10, no. 4, pp. 210-218, 1985.
[50]G. J. Klinker, S. A. Shafer, and T. Kanade, "A physical approach to color image understanding," Int’ J. Computer Vision, vol. 4, pp. 7-38, 1990.
[51]E. Vazquez, R. Baldrich, J. van de Weijer, and M. Vanrell, "Describing reflectances for colour segmentation robust to shadows, highlights and textures," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 5, pp. 917–930, May 2011.
[52]H. D. Cheng, X. H. Jiang, Y. Sun, and Jingli Wang, "Color image segmentation: advances and prospects," Pattern Recognition, vol. 34, issue 12, pp. 2259-2281, Dec. 2001.
[53]G. J. Klinker, S. A. Shafer, and T. Kanade, "The measurement of highlights in color image," Int. J. Comput. Vision, vol. 2, no. 1, 1988.
[54]Yong Shan, Fan Yang, Runsheng Wang, "Color Space Selection for Moving Shadow Elimination," Fourth International Conference on Image and Graphics (ICIG 2007), pp.496-501, 2007.
[55]K. Barnard and G. Finlayson, "Shadow identification using colour ratios," in IS and T/SID 8th Color Imaging Conference: Color Science, Systems and Appl., pp. 97–101, 2000.
[56]E. Salvador, A. Cavallaro, and T. Ebrahimi, "Cast shadow segmentation using invariant color features, " Computer Vision and Image Understanding, vol. 95, issue 2, pp. 238-259, Aug. 2004.
[57]H. Fleyeh, "Shadow and Highlight Invariant Colour Segmentation Algorithm for Traffic Signs," IEEE Conf. on Cybernetics and Intelligent Systems, pp. 1-7, June 2006.
[58]R. Nevatia, "A color edge detector and its use in scene segmentation", IEEE Trans. Syst., Man., Cybern., vol. 7, pp.820 - 826 , 1977.

K.Salient Region Detection
[59]R. Achanta, S. Hemami, F. Estrada, and S. Süsstrunk, "Frequency-tuned salient region detection," IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1597-1604, June 2009.
[60]L. Itti, C. Koch, and E. Niebur, "A model of saliency-based visual attention for rapid scene analysis," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, issue 11, pp. 1254–1259, Nov. 1998.
[61]C. Koch and S. Ullman, "Shifts in selective visual attention: Towards the underlying neural circuitry," Human Neurobiology, vol. 4, pp. 219-227, 1985.
[62]S. Frintrop, M. Klodt, and E. Rome, "A real-time visual attention system using integral images," International Conference on Computer Vision Systems (ICVS), 2007.
[63]Y. F. Ma and H. J. Zhang, "Contrast-based image attention analysis by using fuzzy growing," In ACM International Conference on Multimedia, 2003.
[64]Y. Hu, X. Xie, W. Y. Ma, L. T. Chia, and D. Rajan, "Salient region detection using weighted feature maps based on the human visual attention model," Pacific Rim Conference on Multimedia, 2004.
[65]X. Hou and L. Zhang, "Saliency detection: A spectral residual approach," IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1-8, June 2007.
[66]R. Achanta, F. Estrada, P. Wils, and S. Süsstrunk, "Salient region detection and segmentation," International Conference on Computer Vision Systems (ICVS), vol. 5008, pp. 66-75, 2008.
[67]D. Gao and N. Vasconcelos, "Bottom-up saliency is a discriminant process," IEEE Conference on Computer Vision (ICCV), 2007.
[68]J. Harel, C. Koch, and P. Perona, "Graph-based visual saliency," Advances in Neural Information Processing Systems 19, pp. 545–552, 2007.
[69]N. Bruce and J. Tsotsos, "Attention based on information maximization," Journal of Vision, vol. 7, no. 9, pp. 950–950, June 2007.
[70]L. Itti and C. Koch, "Comparison of feature combination strategies for saliency-based visual attention systems," SPIE Human Vision and Electronic Imaging IV, vol. 3644, pp. 473–482, Jan. 1999.
[71]R. Achanta, and S. Süsstrunk, "Saliency detection using maximum symmetric surround," 17th IEEE International Conference on Image Processing (ICIP), pp. 2653 – 2656, Sept. 2010.