請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/3943
標題: | 同步邊界標籤之演算法設計與分析 Algorithm Design and Analysis for Simultaneous Boundary Labeling |
作者: | Chia-Han Chung 鍾家涵 |
指導教授: | 顏嗣鈞 |
關鍵字: | simultaneous graph drawing,boundary labeling,crossing minimization,bipartite matching,barycenter algorithm, |
出版年 : | 2016 |
學位: | 碩士 |
摘要: | In boundary labeling, each feature point is connected to a label placed
on the boundary of a rectangular image by a leader, which may be a rectilinear or a straight line segment. Currently, all the research about boundary labeling focuses on how to generate label placements for one image with high readability. However, there may be a series of related images, which share all, or parts of the same feature and label set, need to be labeled. If we calculate label placements for each image separately, it is hard to keep track of the relationship between images. To overcome the above difficulty, in this thesis we propose a new problem called simultaneous boundary labeling. We keep the relationship between images by limiting common features and labels of a series of images in the same place, and find a common label placement for all images with minimal leader crossing number and minimal total leader length to increase the readability. We design some heuristic algorithms when there are two related images need to be labeled and show the problem to be NP-complete when there are more than four images in the series. The leader length minimization problem can be solved by a weighted bipartite matching algorithm. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/3943 |
DOI: | 10.6342/NTU201600238 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-1.pdf | 4.21 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。