在許多資訊領域當中，如多媒體系統、影像處理等，影像資料總是大且繁瑣，但在影像資料中，常常包含了許多不重要的資訊，而事實上，只有重要的資訊才是我們有興趣的。然而在本研究當中，我們使用一組利用基因演算法產生較佳的補片(patches)來表示、索引出影像資料中較重要的部份。而使用了這些patch來表示影像，可以降低使用的儲存空間，以及增加處理影像資訊的效率。

In many areas of computer applications, such as MultiMedia Systems and Image Information Systems , image data is always huge and complicated.  However, it includes some information which is not important.  In fact, we are only interested in the information of importance.  In this paper, we use the genetic algorithm to find a set of patches to represent and index the important part of an image.  By using the set of patches to represent the image, the storage required can be reduced and the efficiency of processing can be increased.

目錄
第1章	緒論	1
1.1	研究背景與動機	1
1.2	研究目的	1
1.3	論文架構	1
第2章	相關研究	3
2.1	補片(Patching)	3
2.2	基因演算法	6
2.3	Greedy Method	10
第3章	以基因演算法產生補片	12
3.1	初始族群( Initial Population )	12
3.2	適應函式( Fitness Function )	14
3.3	選擇函式( Selection Function )	17
3.4	交配方式( Crossover )	18
3.5	突變方式( Mutation )	18
3.6	產生補片之演算法	19
第4章	實驗與分析	22
4.1	測試資料	23
4.2	實驗結果	33
4.3	實驗結果數據	43
4.4	實驗分析	44
第5章	結論	46

圖目錄
圖 1.影像處理圖中的物件	4
圖 2.利用一組patch來表示圖中的物件	4
圖 3. tiling 配置patch的結果	5
圖 4. patch可重疊配置的結果	6
圖 5利用patch切割原圖之範例	13
圖 6.染色體的結構	13
圖 7.說明適應值二之範例	16
圖 8.說明適應值三之範例	17
圖 9.單點交配方式	18
圖 10.突變方式	19
圖 11.演算法執行流程圖	21
圖 12.測試資料一的原圖	23
圖 13.測試資料一	23
圖 14.測試資料二的原圖	24
圖 15.測試資料二	24
圖 16.測試資料三的原圖	25
圖 17.測試資料三	25
圖 18.測試資料四的原圖	25
圖 19.測試資料四	26
圖 20.測試資料五的原圖	26
圖 21.測試資料五	26
圖 22.測試資料六的原圖	27
圖 23.測試資料六	28
圖 24.測試資料七的原圖	29
圖 25.測試資料七	29
圖 26.測試資料八的原圖	30
圖 27.測試資料八	31
圖 28.測試資料九的原圖	32
圖 29.測試資料九	32
圖 30.測試資料一(Greedy Method)的結果	33
圖 31.測試資料一(GA)的實驗結果	34
圖 32.測試資料二(Greedy Method)的結果	34
圖 33.測試資料二(GA)的實驗結果	34
圖 34.測試資料三(Greedy Method)的結果	35
圖 35.測試資料三(GA)的實驗結果	35
圖 36.測試資料四(Greedy Method)的結果	36
圖 37.測試資料四(GA)的實驗結果	36
圖 38.測試資料五(Greedy Method)的結果	37
圖 39.測試資料五(GA)的實驗結果	37
圖 40.測試資料六(Greedy Method)的結果	38
圖 41.測試資料六(GA)的實驗結果	38
圖 42.測試資料七(Greedy Method)的結果	39
圖 43.測試資料七(GA)的實驗結果	40
圖 44.測試資料八(Greedy Method)的結果	41
圖 45.測試資料八(GA)的實驗結果	41
圖 46.測試資料九(Greedy Method)的結果	42
圖 47.測試資料九(GA)的實驗結果	43


表目錄
表 1三種方式所計算結果數據	44
表 2基因演算法相較其他方法之百分比	44

[1] 梁恩輝, 林詠翔. “利用基因演算法產生表示影像之補片之方法”，接受發表於2008資訊科技國際研討會論文集，台灣，2008。
[2] Chambers, L., “The Practical Handbook of Genetic Algorithms Applications”, CHAPMAN & HALL / CRC, 2001.
[3] Goldberg, D. E., “Genetic Algorithms in Search, Optimization and Machine Learning”, Addison-Wesley, 1998.
[4] Tanimoto, S. L., R. J. Fowler, “Covering image subsets with patches”, NATO Conference Series, (Series) 4: Marine Sciences 2, pp. 835-839, 1980
[5] Tanimoto, S. L., “Covering and indexing an image subset” Proc. Recognition and Image Processing .IEEE Computer Society Conf., IL, 239-245 , 1979
[6] Holland, J. H., “Adaptation in Natural and Artificial System”, Ann Arbor: The University of Michigan Press, 1975.
[7] Koza, J. R., “Survey of Genetic Algorithms and Genetic Programming”, Wescon Conference Record, pp. 589-594, 1995.
[8] Kumar, A., R. M. Pathak, M. C. Gupta, “Genetic algorithm based approach for designing computer network topology”, 1993 ACM Computer Science Conference, pp. 358-365, 1993.
[9] Bhuyan, J. N., V. V. Raghavan, V. K. Elayavalli, “Genetic algorithm for clustering with an ordered representation”, Belew and Booker, pp. 408-415, 1991.
[10] De Lit, P., Falkenauer, E., Delchambre, A. “Grouping genetic algorithms: An efficient method to solve the cell formation problem ”, Mathematics and Computers in Simulation 51 (3-4), pp. 257-271
[11] Haupt, R. L., “An introduction to genetic algorithms for electromagnetics”, Antennas and Propagation Magazine, IEEE, Vol.37 , pp.7-15, 1995.
[12] Jones, D. R., M. A. Beltramo, “Solving partitioning problems with genetic algorithms”, Belew and Booker, pp. 442-449, 1991.
[13] Fowler , R. J.,  M. S. Paterson, and S. L. Tanimoto, “Optimal packing and covering in the plane are NP-complete” Inform. Processing Lett., vol. 12, pp. 133-137, Apr. 1981.
[14] Rigaux, P., M. Scholl, A. Voisard, “Spatial Databases with application to GIS”, Morgan Kaufmann, 2002.
[15]Li, X. and Yeh, A.G.-O., “Integration of genetic algorithms and GIS for optimal location search” International Journal of Geographical Information Science, 19, pp. 581-601, 2005.
[16] Miller, H.J., “GIS and geometric representation in facility location problems” International Journal of Geographical Information Science, 10, pp. 791-816, 1996.
[17]Mehrez, A. and Stulman, A., “The maximal covering location problem with facility placement on the entire plane” Journal of Regional Science, 22, pp. 361-365, 1982.