臺灣博碩士論文加值系統

提供適當的註釋幫助使用者體驗三維環境是基礎且重要的工作。以往的三維空間建築標籤研究都是考量攝影機處於高空俯視的情況，將標籤以三維貼圖的方法貼附於建築物表面上。然而若將此類方法套用於攝影機處於低高度的街景視角，透視變形現象的影響將嚴重降低標籤的可讀性，導致使用者難以辨識標籤進而造成混淆。

本篇論文提出一套適用於街景視角的三維建築標籤演算法，使用內部標籤方法避免透視變形現象的影響以保持可讀性，結合三維空間與螢幕空間的資訊建立一套線性規劃模型，設計對應的啟發式演算法使標籤能夠在不互相重疊的前提下，最大化標籤顯示時間。最後實驗顯示在街景視角情境下我們方法的標籤顯示時間較過往方法有明顯改善。

Appropriate annotation to help users experience the 3D environment is a fundamental and essential task. The related research on 3D building labeling algorithm mainly considers the high altitude view and then labeling by attached 3D labels to building surfaces. However, when such a method has been applied to the low altitude street-view, the effect of perspective distortion will seriously degrade the readability of 3D labels such that making it difficult for users to recognize.

In this thesis, we provide a 3D building labeling algorithm for low altitude street-view, maintain readability through internal labeling to avoid perspective distortion. We design an integer linear programming formulation with the information of 3D environment space and screen space and given a corresponding heuristic algorithm that labels can maximize the label display time without overlapping each other. In the experiment, our approach significant improvement over existing approaches.

致謝 i
摘要 ii
Abstract iii
目錄 iv
圖目錄 vi
表目錄 viii
第一章 緒論 1
1.1研究背景與動機 1
1.2論文架構 3
第二章 相關研究文獻回顧 4
2.1二維平面標籤演算法 5
2.2三維空間標籤演算法 7
第三章 三維街景建築標籤演算法 10
3.1名詞定義與問題描述 10
3.2演算法架構 12
3.2.1初始化 13
3.2.2選擇標籤滑桿 14
3.2.3排除標籤重疊狀況 18
第四章 實驗與討論 23
4.1標籤方法 24
4.2實驗環境 26
4.3實驗方法與觀測變數 26
4.4實驗結果與分析 29
第五章 結論與未來發展 36
5.1結論 36
5.2未來發展 36
參考文獻 37

[1]J. Ahn and H. Freeman. A program for automatic name placement. Auto­Carto 6,page 444–455, 1983.
[2]K. Been, E. Daiches, and C. Yap. Dynamic map labeling. IEEE Transactions on Visualization and Computer Graphics, 12(5):773–780, 2006.
[3]M. Bekos, M. Nöllenburg, and A. Symvonis. Boundary labeling with octilinear leaders. Algorithmica, 57:436–461, 07 2008.
[4]M. Bekos, K. Potika, and A. Symvonis. Polygon labelling of minimum leader length. APVIS 2006. Proc. Asia Pacific Symp. on Inform. Visualisation, CRPIT, 60:15–21,01 2006.
[5]M. Bekos, A. Symvonis, and A. Wolff. Boundary labeling: Models and efficient algorithms for rectangular maps. Computational Geometry, 36:215–236, 04 2007.
[6]M. Benkert, H. Haverkort, M. Kroll, and M. Nöllenburg. Algorithms for multi criteria one­sided boundary labeling. Journal of Graph Algorithms and Applications,13, 01 2009.
[7]http://www.lighthouse3d.com/tutorials/view­frustum­culling.
[8]H. Freeman. Automated cartographic text placement. Pattern Recognition Letters,26:287–297, 02 2005.
[9]A.Gemsa, B. Niedermann, and M. Nöllenburg. Trajectory­-based dynamic map labeling. In L. Cai, S.­W. Cheng, and T.­W. Lam, editors, Algorithms and Computation, pages 413–423, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
[10]T. Götzelmann, K. Ali, K. Hartmann, and T. Strothotte. Form follows function: Aesthetic interactive labels. InCAe, 2005.
[11]K. Hartmann, T. Götzelmann, K. Ali, and T. Strothotte. Metrics for functional and aesthetic label layouts. InProceedings of the 5th International Conference on SmartGraphics, SG’05, page 115–126, Berlin, Heidelberg, 2005. Springer­Verlag.
[12]Y. Huang, D. Kong, and Y. Zhang. Study on dynamic labeling of building in 3d vir­tual city.2012 IEEE Symposium on Electrical and Electronics Engineering., pages156–162, 2012.
[13]E. Imhof. Positioning names on maps. The American Cartographer, 2(2):128–144,1975.
[14]C. Lehmann and J. Döllnery. Annotating 3d content in interactive, virtual worlds christine. Proceedings of the 18th International Conference on 3D Web Technology. ,pages 67–70, 2013.
[15]M. Löffler, M. Nöllenburg, and F. Staals. Mixed map labeling. Journal of Spatial Information Science, 13, 12 2016.
[16]OpenStreetMap. OpenStreetMap Unity Libraries and resources,2020(accessed December 10, 2020). Available at https://wiki.openstreetmap.org/wiki/Unity.
[17]J. She, X. Li, J. Liu, Y. Chen, J. Tan, and G. Wu. A building label placement method for 3d visualizations based on candidate label evaluation and selection. International Journal of Geographical Information Science, pages 2033–2054, 2019.
[18]J. She, J. Liu, C. Li, J. Li, and Q. Wei. A line­ feature label placement algorithm for interactive 3d map. Computers l& Graphics., pages 86–94, 2017.
[19]M. Tatzgern, D. Kalkofen, R. Grasset, and D. Schmalstieg. Hedgehog labeling: View management techniques for external labels in 3d space. Proceedings ­ IEEE Virtual Reality, 04 2014.
[20]Y. Yoshimoto, T. H. Dang, A. Kimura, F. Shibata, and H. Tamura. Interaction design of 2d/3d map navigation on wall and tabletop displays. ITS '11: Proceedings of the ACM International Conference on Interactive Tabletops and Surfaces, page 254–255, 2011.
[21]S. Zechmeister, D. Cornel, and J. Waser. 3d annotations for geospatial decision support systems. Journal of WSCG, pages 141–150, 2019.