臺灣博碩士論文加值系統

本論文提出兩種新的影像分割技術，分別為結合watershed analysis和模糊理論的同步特徵調整(Fuzzy-based Feature Tuning, FFT)及分群合併(Clustering Merging, CM)方法。由於watershed analysis是以偵測影像上的灰階變化(視為地勢的起伏)來分割影像，所以存在不可避免的過度分割(Over-segmentation)問題。傳統演算法乃事先指定最終區塊數目，再藉由循序兩兩合併最相似的區塊直到該指定的區塊數，來減輕過度分割的問題，然而這種方法的計算時間會隨著區塊數目的增加而線性的增加。
基於此，吾人提出兩種無須事先決定區塊數目的快速區塊合併方法來解決過度分割問題。在經過watershed analysis後得到的所有區塊先以該區塊Ri中每一個像素的平均灰階值mi來代表，接下來同步特徵調整(FFT)方法根據每一個區塊的鄰居與它的灰階值差異大小來同步(即同時)調整灰階值，使得屬於相同物件的小區塊會在下一個遞迴中合併在一起。由於同步的策略，因此可以達成快速的區塊合併並極有可能完全由平行的硬體架構來實現，當兩個遞迴中所得到的區塊數目相同時這個方法會自動終止。
另外一個快速區塊合併方法是分群合併(CM)。在分群合併中，區塊合併的過程被視為是一個引進空間限制條件的分群演算法。由watershed analysis求得的每一個小區塊被視為一個虛擬的資料點而所有資料點依其特徵被群聚成數個不同的群集。若有兩個小區塊屬於同一群集並且相鄰，則吾人視其為應屬同一物件而將之合併。最後，實驗結果將顯示吾人所提出的技術在計算時間以及分割結果的精確度上都優於其他演算法。

Over-segmentation is a serious problem in conventional watershed analysis owing to the topographic relief inherent in the input image. To this problem, currently existing watershed methods merge two regions in sequence. However, sequential merging would require heavy computation load. This thesis presents two novel approaches that incorporate the watershed analysis and fuzzy theory, namely the synchronous Fuzzy-based Feature Tuning (FFT) and Clustering Merging (CM), to perform image segmentation.
Both FFT and CM need not pre-specify the final number of regions. Each region Ri obtained from watershed analysis is first represented by the mean intensity (noted as mi) of gray pixels in Ri. FFT simultaneously adjust mi values of all regions by referencing their adjacent neighboring regions. Due to the use of synchronous strategy, FFT can achieve fast merging and provides great potentiality for a fully parallel hardware implementation. The iterative algorithm of FFT is terminated when the number of merged regions of two successive iterations is identical.
In the CM method, the region merging processing has been formulated as clustering with special constraint. Each small region is regarded as a virtual data point and all the small regions are clustered if they share great similarity. When two small regions are adjacent and are clustered into an identical cluster, we say that they are of the same object and can be merged. Finally, empirical results are provided to show that the proposed approaches outperform other methods in terms of computation efficiency and segmentation accuracy.

CHAPTER 1 INTRODUCTION
1-1.REVIEW OF IMAGE SEGMENTATION
A.Histogram-Based Techniques
B.Edge-Based Techniques
C.Region-Based Techniques
D.The Hybrid Approach
1-2.OUTLINE OF THE THESIS
CHAPTER 2 WATERSHED ANALYSIS
2-1.BASICS OF WATERSHED ANALYSIS
2-2.VARIOUS IMPLEMENTATIONS OF WATERSHED ANALYSIS
2-3.THE HARIS ALGORITHM
2-4.SUMMARY
CHAPTER 3 THE PROPOSED SEGMENTATION METHODS
3-1.MOTIVATION
3-2.FAST MERGING ALGORITHMS
3-3.FFT INCORPORATED WITH WATERSHED ANALYSIS
3-4. CLUSTERING MERGING INCORPORATED WITH WATERSHED ANALYSIS
3-5.SUMMARY
CHAPTER 4 EXPERIMENTAL RESULTS
4-1.SYNTHETIC IMAGE
4-2.REAL IMAGES
CHAPTER 5 CONCLUSIONS AND DISCUSSIONS
REFERENCE

[1] K. Mardia and T. Hainsworth, “A spatial thresholding method for image segmentation,” IEEE Trans. Pattern Anal. Machine Intell., vol. 10, pp. 919-927, Nov. 1988.
[2] Wonho Oh and W. Brent Lindquist, “Image thresholding by indicator kriging,” IEEE Trans. Pattern Anal. Machine Intell., vol. 21, pp. 590-602, Jul. 1999.
[3] R. C. Gonzalez and R. E. Woods, Digital Image Processing, Addison-Wesley, Reading, Mass., 1993.
[4] R. M. Haralick, “Digital step edges from zero crossing of second directional derivatives,” IEEE Trans. Pattern Anal. Machine Intell., vol. 6, pp. 58-68, 1984.
[5] J. F. Canny, “A computational approach to edge detection,” IEEE Trans. Pattern Anal. Machine Intell., vol. 8, pp. 679-698, 1986.
[6] J. Basak, B. Chanda, and D. D. Majumder, “On edge and line linking with connectionist models,” IEEE Trans. System, Man, and Cybernetics, vol. 24, pp. 413-428, Mar. 1994.
[7] S. A. Hojjatoleslami and J. Kittler, “Region growing: a new approach,” IEEE Trans. Image Processing, vol. 7, pp.1079-1084, Jul. 1998.
[8] T. Pavlidis and Y. Liow, “Integrating region growing and edge detection,” IEEE Trans. Pattern Anal. Machine Intell., vol. 12, pp. 225-233, Mar. 1990.
[9] L. D. Griffin, A. C. F. Colchester, and G. P. Robinson, “Scale and segmentation of grey-level images using maximum gradient paths,” Image Vis. Comput., vol. 10, pp. 389-402, 1992.
[10] L. Vincent and P. Soille, “Watersheds in digital spaces: An efficient algorithm based on immersion simulations,” IEEE Trans. Pattern Anal. Machine. Intell., vol. 13, pp. 583-598, June 1991.
[11] J. M. Gauch and S. M. Pizer, “Multiresolution analysis of ridges and valleys in gray-scale images,” IEEE Trans. Pattern Anal. Machine. Intell., vol. 15, pp. 635-646, June 1993.
[12] Y. W. Yu, “Image segmentation Based on improved watershed technique,” Master Thesis, National Taiwan Ocean University, Jun. 2000.
[13] K. Haris, S. N. Efstratiadis, N. Maglaveras, and A. K. Katsaggelos, “Hybrid image segmentation using watersheds and fast region merging,” IEEE Trans. Image Processing, vol. 7, no. 12, pp. 1684-1699, Dec. 1998.
[14] M. Matheron, Random Seys and Integral Geometry, New York: Wiley, 1975.
[15] J. Serra, Image Analysis and Mathematical Morphology, Lonon: Academic, 1982.
[16] S. R. Sternberg, “Grayscale morphology,” Comput. Vision, Graphics, Image Processing, vol. 35, pp. 333-355, 1986.
[17] J. M. Gauth, “Image segmentation and analysis via multiscale gradient watershed hierarchies,” IEEE Trans. Image Processing., vol. 8, no. 1, pp. 69-79, Jan. 1999.
[18] A. N. Moga and M. Gabbouj, “Parallel image component labeling with watershed transformation,” IEEE Trans. Pattern Anal. Machine. Intell., vol. 19, no.5, pp. 441-450, May 1997.
[19] D. Hagyard, M. Razaz and P. Atkin, “Analysis of watershed algorithms for greyscale images,” Proc. Int. Conf. Image Processing, pp. 41-44, 1996.
[20] S. Beucher and C. Lantuejoul, “Use of watersheds in contour detection,” Proc. Int. Conf. Image Processing, Real-Time Edge and Motion Detection/Estimation., pp. 17-21, Sep. 1979.
[21] L. A. Zadeh, “Fuzzy sets,” Inform. Control, vol. 8, pp. 338-353, 1965.
[22] E. Gose, R. Johnsonbaugh and S.Jost, Pattern Recognition and Image Analysis, Prentice Hall, 1996.
[23] F. Hoppner, F. Klawonn, R. Kruse and T. Runkler, Fuzzy Cluster Analysis, Wiley, 1999
[24] J. C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum Press, New York, 1981.
[25] R. Krishnapuram and J. M Keller, “A possibilistic approach to clustering,” IEEE Trans. Fuzzy System, vol. 1, no. 2, pp.98-110, 1993.
[26] J. C. Bezdek, and J. M. Keller, “The possibilistic c-means algorithm: insights and recommendations,” IEEE Trans. Fuzzy Systems, vol. 4 no. 3, pp. 385-393, 1996.
[27] R. R. Yager, and D. P. Filev, “Approximate clustering via the mountain method,” IEEE Trans. System Man and Cyber., vol. 24, no. 8, pp.1279-1284, 1994.
[28] Y.A. Tolias, and S. M. Panas, “On applying spatial constraints in fuzzy image clustering using a fuzzy rule-based system,” IEEE Signal Processing Letters, vol. 5, pp. 245-247, 1998.
[29] G. Qiu, “Functional optimization properties of median filtering,” IEEE Signal Processing Letters, vol. 1, pp. 64-65, April 199