標記放置(label placement)向來是製圖學領域中的一項基礎且重要的程序，也是一項熱門的研究議題，在標記放置的過程中，除了要確保標記可明確表達所標示之地物外，還需盡可能避免標記之間發生過於擁擠甚至重疊之情況，因此標記放置作業的複雜性非常高。以往的相關研究，為了降低此問題的複雜程度，大多先限制標記可放置之位置並給予其優先順序，之後再解決重疊的問題，此策略雖然可大幅降低運算量，並且縮短計算時間，但由於可放置位置受到限制，當標記數量漸增時，便會發生無法避免之重疊現象，造成成果品質不佳，標記難以辨識。本研究提出一全新方法，將標記放置視為一最佳化的問題，藉由基因演算法(Genetic Algorithm ,GA)以及目標函數(objective function)之給定以進行求解。在基因演算法中，本文將各標記的候選位置視為一個基因，並且透過區域最小值以及規則網格的初始值給定方式進行初始族群之產生，配合基因演算法後續的運算操作求解，以期能產生最佳的標記放置成果。本研究藉由旅遊地圖(tourist map)的設計概念，利用影像作為各景點之標記，並且利用上述的方法進行各標記放置位置之最佳化求解，實驗結果顯示本研究之方法可提供一良好的標記放置成果，並且在標記數量大幅增加時，亦可減少標記重疊的現象，以增加標記的可辨識性，進而大幅提升地圖的實用性。

Label placement is a fundamental and important process and also a hot topic in the field of cartography. The goal of label placement is to clearly represent the labeled objects and thus, must avoid overcrowded labeling and label-label overlap. Thus, the label placement problem has a very high computational complexity. In order to reduce the complexity of this problem, some of researches reduce and fix the search space of labeling and give a prior priority for each position to solve the problem of label overlapping. Although this strategy can conspicuously reduce the computational complexity, the problem of label-label overlap may still occur when the number of labels is very large. In this thesis, a novel label placement approach is introduced to place the selected image labels according to a significance map which combines the importance of all visual elements. The image label placement is regarded as an optimization problem and solved by a genetic algorithm with an objective function. In the proposed genetic algorithm, a label position is encoded as a gene and a non-random approach is adopted to select the initial population for the purpose of speeding up convergence of the iterative process. By utilizing the genetic operators, crossover and mutation, a near optimal result can be obtained. The experimental results show that the proposed approach can reduce label-label overlap when the number of label increases largely, and can generate exceptional label placement results.

許舜翔，”自動化符號選擇方法應用於旅遊景點特徵表示”，國立成功大學測量及空間資訊學系研究所碩士論文，台南，第1-92頁，2010。

Agrawala, M., and Stolte, C., “Rendering Effective Route Maps: Improving Usability Through Generalization”. ACM Transactions on Graphics (SIGGRAPH Proc.), pp. 241–249, 2001.

Ahn, J., and Freeman, H., “A Program for Automatic Name Placement”. Cartographica, Vol.21, No.3, pp.101-109, 1984.

Cerny, V., “Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulated Annealing”. Journal of Optimization Theory and Application, Vol. 45, pp. 41-51, 1985.

Chen, W. C., Battestini A., Gelfand, N., and Setlur, V., “Visual Summaries of Popular Landmarks from Community Photo Collections”. ACM Transactions on Graphics (SIGGRAPH Proc.), pp. 789-792, 2009.

Christensen, J., Marks, J., and Shieber, S., “An Empirical Study of Algorithms for Point-feature Label Placement”. ACM Transactions on Graphics (SIGGRAPH Proc.), Vol. 14, No. 3, pp. 203-232, 1995.

Dorigo, M., Maniezzo, V., and Colorni, A., “Ant System: Optimization by a Colony of Cooperation Agents”. IEEE Transactions on Systems, Man and Cybernetics, Part B: Cybernetics, Vol.26, No. 99, pp. 29-41, 1996.

Eberhart, R. C., and Kennedy, J., “A New Optimizer Using Particle Swarm Theory”. Proceedings of Sixth International Symposium on Micro Machine and Human Science, Nagoya, pp.39-43, 1995.

Ebinger, L. R., and Goulette, A. M., “Automated Names Placements in Non-Interactive Environment”. Auto-Caro9, ACSM/ASPRS, pp. 205-214, 1989.

Glover, F., “Future Paths for Integer Programming and Links to Artificial Intelligence”. Computers and Operation Research, Vol.13, No.5, pp. 533-549, 1986.

Grabler, F., Agrawala, M., Sumner, R. W., and Pauly, M., “Automatic Generation of Tourist Maps”. ACM Transactions on Graphics (SIGGRAPH Proc.), Vol. 27, No. 3, pp. 1–11, 2008.

Hirsch, S. A., “An Algorithm for Automatic Name Placement Around Point Data”. The American Cartographer, Vol.9, No.1, pp.5-17, 1982.

Holland, J. H., “Adaptation in Natural and Artificial Systems”. University of Michigan Press, Michigan, USA, 1975.

Imhof, E., “Positioning Names on Maps”. The American Cartographer, Vol.2, No.9, pp.128-144, 1975.

Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P., “Optimization by Simulated Annealing”. Science, Vol. 200, No. 4956, pp. 671-680, 1983.

Langran, G. E., and Poiker, T. K., “Integration of Name Selection and Name Placement.” Proceedings of Second International Symposium of Spatial Data Handling, pp.50-64, 1986.

Lee, L. H., and Fan, Y., “Developing a Self-learning Adaptive Genetic Algorithm.” Proceeding of Third World Congress on Intelligent Control and Automation, pp. 619-624, 2000.

Luboschik, M., Schumann, H., and Cords, H., “Particle-based Labeling: Fast Point-Feature Labeling without Obscuring Other Visual Features.” IEEE Transactions on Visualization and Computer Graphics, Vol. 14, No. 6, pp. 1237-1244, 2008.

Man, K. F., Tang, K. S., and Kwong, S., “Genetic Algorithm: Concepts and Applications.” IEEE Transactions on Industrial Electronics, Vol. 43, No. 5, pp. 519-534, 1996.

Marks, J., and Shieber, S., “The Computational Complexity of Cartographic Label Placement”. Technical Report TR-05-91, Harvard CS, 1991.

Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., and Teller, E., “Equation of State Calculations by Fast Computing Machines”. Journal of Chemical Physics 21, pp. 1087–1092, 1953.

Mitchell, M., “An Introduction of Genetic Algorithm.” MIT Press, London, 1992.

Mote, K., “Fast point-feature label placement for dynamic visualizations.” Information Visualization, Vol. 6, No. 4, pp.249-260, 2007.

Raidl, G., “A Genetic Algorithm for Labeling Point Features”. Proceedings of the International Conference on Imaging Science, Systems, and Technology, pp. 189-196, 1998.

Perez, J.-C., and Vidal, E., “Optimum polygonal approximation of digitized curves”. Pattern Recognition Letters, Vol. 15, pp. 743-750, 1994.

Petzold, I., “Beschriftung von Bildschirmkarten in Echtzeit - Konzept Und Struktur”. PhD thesis, University of Bonn, Germany, 2003.

Roy, S., Bhattacharjee, S., Das, S., and Nandy, S. C., “A fast algorithm for point labeling problem.” Proceedings of the 17th Canadian Conference on Computational Geometry, pp. 155-158, 2005.

Roy, S., Bhattacharjee, S., Das, S., and Nandy, S. C., “A New Fast Heuristic for Labeling Points.” Information Processing Letters, pp. 478-484, 2009.

van Dijk, S., Thierens, D., and de Berg, M., “Using Genetic Algorithms for Solving Hard Problems in GIS”. GeoInformatica, Vol. 6, No.4, pp. 381-413, 2002.

Wood, C. H., “A Descriptive and Illustrated Guide for Type Placement on Small Scale Maps”. The Cartographic Journal, Vol. 37, No. 1, pp. 5-18, 2000.

Yamamoto, M., Camara, G., and Lorena, L. A. N., “Tabu Search Heuristic for Point-feature Cartographic Label Placement”. GeoInformatica, Vol. 6, No. 1, pp.77-90, 2002.

Yoeli, P., “The Logic of Automated Map Lettering”. The Cartographic Journal, Vol.9, No.2, pp.99-108, 1972.