透過您的圖書館登入
IP:54.166.200.255
  • 學位論文

蟻群最佳化演算法在影像分割問題之研究

Study of Ant Colony Optimization - in the Application of Image Segmentation

指導教授 : 梁韵嘉

摘要


臨界值法是影像分割方法中非常重要的一種方法,其主要目的是將影像中所關心的目標物從背景中過濾分割出來。傳統的影像分割法已經廣泛的應用在二階影像分割問題,但是在處理多階影像分割問題時,由於採用窮舉法搜尋最佳臨界值,因此花費的運算時間非常可觀。整體臨界值法(Global histogram-based algorithms)是非常受歡迎的臨界值分割法,可分為參數法(parametric approach)及非參數法(nonparametric approach),研究指出非參數法比參數法簡單且更有效率,但影像分割的品質卻往往不如參數法,然而,參數法由於計算較為複雜,運算時間也相對較長。 在1970年後期,出現了一種新類型的演算法稱為萬用啟發式方法(metaheuristic),它將基礎啟發式演算法(heuristic)、人工智慧、生物演化、自然科學等結合在高階架構上,透過遞迴求解及學習策略,有效率(efficiently)且有效益(effectively)的探索搜尋空間(search space),其中的蟻群最佳化演算法,不論在求解的品質或是求解的效率上均有非常好的表現。本論文第一個主題是利用蟻群最佳化演算法在求解的品質與求解的效率上的優異表現,取代傳統影像分割法所使用的窮舉法,與Otsu法結合發展出新的ACS-Otsu影像分割方法,透過全新設計的階層式搜尋機制(Hierarchical search range, HSR),降低處理多階分割的問題的複雜度,改善搜尋最佳臨界值的效率與效能。本論文的第二個主題是以第一個主題的研究為基礎,利用ACS-Otsu演算法作為產生期望值最大化演算法(Expectation Maximization Algorithm;EM)估計參數初始值之前導程序,結合EM演算法的特性,以雙目標的概念,在達到預設的分割階層數(target level)時,產生兩個分割影像,以改善複雜影像的分割處理品質。本論文的第三個主題的研究重心則是將Modified CACS (MCACS)與ACOR兩種最近提出的連續型蟻群最佳化演算法與期望值最大化演算法相結合,在高斯混合模型(Gaussian Mixture Model;GMM)機率分配模型的假設之下,發展出應用在多階影像分割問題。這兩種新的參數估計演算法,可以在保有參數法優點的同時亦能改善其運算時間過長的問題,經過實驗的驗證,已證實這兩種新的演算法均為高品質與高效率的影像分割方法,可提供產業界與醫學界影像處理使用。

並列摘要


Thresholding is an important technique for image segmentation. The aim of an effective segmentation is to separate objects from the background and to differentiate pixels having nearby values for improving the contrast. Traditional optimal thresholding methods are very popular and efficient in the case of bi-level thresholding. However, they are very computationally expensive for multilevel thresholding since they utilize the exhaustive search to find the optimal thresholds. Global histogram-based algorithms are widely employed to determine the threshold and can be classified into parametric and nonparametric approaches. In parametric approaches, the gray-level distribution of each group has the probability density function that is assumed to obey a Gaussian distribution while nonparametric approaches find the thresholds that separate the gray-level regions of an image in an optimal manner according to some discriminating criteria. Nonparametric approaches are proven to be more computationally efficient and simpler to apply. However, some previous research found that the quality of image obtained from parametric approaches was better than those obtained form nonparametric approaches. Problems of thresholding have been quite extensively studied for many years; yet, the automatic determination of an optimum threshold value continues to be of great challenge. For that, meta-heuristics in recent years have become alternative ways to solve multilevel thresholding. In order to make the traditional optimal thresholding methods more practical for on-line applications, to find a faster and high quality search algorithm becomes a very important issue. Just like other meta-heuristics inspired by the natural process, Ant Colony Optimization (ACO) has been proven to an efficient and versatile tool for combinational optimization problems. Therefore, the purpose of our research is to hybrid two different kinds of ACO algorithms (combinatorial and continuous) with parametric and nonparametric approaches to develop efficient and effective multilevel thresholding techniques. Thus, in the first topic, a fast hybrid multilevel thresholding approach is proposed based on Ant Colony System (ACS). A hierarchical search range (HSR) which takes advantage of the efficiency and effectiveness of the Otsu’s method at bi-level exhaustive search is embedded in ACS. The HSR will determine the search range of each threshold automatically according to the optimal thresholds generated from the previous segmented level. Moreover, a predefined uniformity value is used as the stopping criterion of the proposed ACS-Otsu algorithm to determine the optimal number of thresholds. In the second topic, an optimization algorithm (named as AOE) combining parametric and nonparametric approaches is proposed. The ACS-Otsu algorithm proposed in the first topic is hybridized with the EM algorithm. The AOE algorithm is designed to find two optimal threshold sets based on two criteria respectively: between-class variance and the overall fitting error of probability distributions, and then generate two thresholded images simultaneously. The proposed AOE algorithm can overcome the drawbacks of the one criterion optimization methods and deal with various images more efficiently and effectively in practice. In the last topic, we consider multilevel thresholding problem as a continuous optimization problem and present two fast estimation algorithms based on the Modified CACS (MCACS) and ACOR algorithms hybridized with the EM algorithm (named MCACS-EM and ACOR-EM). The EM algorithm is applied as a local searching approach and a new initialization strategy is designed to obtain a more quality initial population for EM algorithm. All algorithms can provide effective and efficient solving approaches for both the industrial and medical image processing.

參考文獻


100.Zhang, Y., C. Zhang, J. Chi, and R. Zhang
2.Abutaleb, A.S., “Automatic Thresholding of Gray-level Pictures using Two-dimensional Entropy,” Computer Vision, Graphics, and Image Processing, 47, pp. 22-32, 1989.
3.Arora, S., J. Acharya, A. Verma, and P.K. Panigrahi, “Multilevel Thresholding for Image Segmentation though a Fast Statistical Recursive Algorithm,” Pattern Recognition Letters, 29, pp. 119-125, 2008.
4.Bazi, Y., L. Bruzzone, and F. Melgani, “Image Thresholding based on the EM Algorithm and the Generalized Gaussian distribution,” Pattern Recognition, 40, pp. 619-634, 2007.
5.Belkasim, S., A. Ghazal, and O.A. Basir, “Phase-based Optimal Image Thresholding,” Digit. Signal Processing, 13, pp. 636-655, 2003.

延伸閱讀