三維街景建築標籤演算法之設計與實作

Design and Implementation of Algorithms for Labeling Street Buildings in 3D

劉定岳(Ding-Yue Liu)

指導教授 ： 顏嗣鈞

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2021年)

https://doi.org/10.6342/NTU202100327

摘要

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

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

關鍵字

標籤計算 ； 建築標籤 ； 三維視覺化

並列摘要

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.

並列關鍵字

Label evaluation ； Building label ； 3D visualization

參考文獻

[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.