以遺傳演算法作鏈結式金字塔切割

Genetic Algorithm For Segmentation On a Linked Pyramid

邱鸞嬌(Luan-Jiau Chiu)

指導教授 ： 陳淑媛

元智大學/工程學院/電機與資訊工程研究所/碩士(1997年)

摘要

本研究擬提出一套以遺傳演算法進行鏈結規則金字塔架構(linked regular pyramid
structure)的影像切割方式。將原始影像置於規則金字塔結構的底層，並由遺傳演算法
進行金字塔建構與演化過程。一般而言，遺傳演算法通常可提供最佳整域解，而金字塔演
算法能提供影像分析多重解析度的快速平行處理，因此，我們的方法整合了兩者優點而獲
得近似最佳的切割結果。在我們規則性金字塔架構中，納入了數個非規則性金字塔
(irregular pyramid)演算法的優點，如叢集(clustering)和保持連接性的
重鏈結(connectivity preserving relinking) ，以建構一個簡單有效的運算
結構。由於遺傳演算法的進化作用，我們可以獲得近似最佳解的"父值"(parent
value)和"父子鏈"(child-parent link) ，因而得到比傳統鏈結金字塔所提供
的更精確層次資料(level data) ，這些資料用於切割出不同解析度的效果。
同時在本研究中，我們也提出幾個新穎的觀念，如依金字塔的層次的不同，而設立不同尺
寸的染色體( chromosome)，以利於每一層次的遺傳運算，另外,我們還採用一個
可調的"父候選者"窗口，以獲得不同的切割結果。一般而言，小型窗口偏向產生較簡
潔的連接切割(connected segment)，大窗口則偏向較精緻但有時會散落的連接切
割。實驗結果將證明我們演算法是可行且效果良好。

關鍵字

金字塔架構 ； 遺傳演算法 ； 保持連接性的重鏈結

並列摘要

In this study, we propose a genetic algorithm for image segmentation on a linked regular pyramid with connectivity preserving. The hierarchy of pyramid is placed into a GA processing for evolution. Since the genetic algorithms always provide global optimal solutions and pyramid algorithms support fast parallel processing for multiresolution image
analysis, near-optimal multiresolution segmentation results
can be obtained. Some attributes of irregular pyramid, such
as clustering and connectivity preserving relinking, are also
involved in our regular hierarchy to construct a simple and
powerful computational structure. Since GA evolution makes the
parent values and child-parent links computation reach
near-optimal result, a more efficient pyramid data can be
obtained. Consequently, these pyramid data can be used to
produce the multiresolution segmentation results. Moreover,
some novel ideas are also proposed in this study. First, the
chromosome sizes dependent on level sizes are used to
facilitate the GA evolution on each level. Then, an adaptable
candidate parent window is used to obtain different segmented
results. In general, small window leads to compact connected
segment, while large window leads to fine
(sometimes scattered) connected segment. Experimental results
prove the effectiveness, robustness and feasibility of our
algorithm.

並列關鍵字

linked regular pyramid structure ； genetic algorithm ； connectivity preserving relinking

參考文獻

[1] Bister, M., Cornelis, J., Rosenfeld, A., "A critical view of pyramid segmentation algorithms," Pattern Recognition Letters, vol. 11, pp. 605-617, 1990.

[2] Burt, P.J., Hong, T.H., Rosenfeld, A., "Segmentation and estimation of image region properties through cooperative hierarchical computation," IEEE Trans. on Sysntems, Man and Cybernetics, vol. SMC-11, no. 12, pp. 802-809, 1981.

[3] Chun, D. N., Yang, H. S.,"Robust image segmentation using genetic algorithm with a fuzzy measure," Pattern Recognition, vol. 29, no. 7, pp. 1195-1211, 1996.

[4] Davis, L., Genetic Algorithms and Simulated Annealing, Pittman, London, 1987.

[5] Hwang, D. S., "Genetic algorithm for color image segmentation," Master Thesis of the Institute of Electrical engineering and Computer Engineering and Science, Yuan-Ze University, Taiwan, 1997.