代表著作說明
博士論文題目:三角網格關聯性之研究
Connectivity Compression for Triangular Meshes
內容摘要
三度空間立體模型之單一連接性(Single-Rate Connectivity)壓縮法之研究,可區分成以邊為礎 (EdgeBased) 及以頂點為基礎 (Vertex-Based) 兩類;Edgebreaker是以邊為基礎的代表方法,而Valence-Driven是以頂點為基礎的代表方法。此兩者均需要使用切割運算元將三度空間立體模型切割成兩個部份,也因為切割的影響將造成額外記錄距離的負擔或額外的運算位元來辨識切割處,進而降低壓縮的品質。Edgebreaker 演算法的主要缺點有二:第一為多次路徑 (Multiple Pass Traversals) 的壓縮三角片,此方式將造成執行時間的大量浪費。第二為反向的解壓縮程序,此操作程序將使得解壓縮的過程必須在離線 (Off-Line) 的狀態下進行。Valence-Driven 演算法的缺點是在不知道三角網格的分支資訊時,需要額外的演算程序,計算每一個頂點的分支度 (Degree) 。為了克服以上的限制,本論文提出了三個針對單一解析度 (Single-Resolution) 物體之壓縮演算法來解決三角網格連接性的問題。我們的演算法能夠單一路徑的壓縮及解壓縮,並且能在及時 (On-Line) 的模式下進行整個程序。
我們提出的三個演算法分別稱為Algorithm I 、Algorithm II及Algorithm III。在Algorithm I 的演算法中,我們提出了J運算元,其主要的功能是跳至作用邊的下一個邊,避免切割的情形發生造成額外的運算元浪費。並且藉由使用Q運算元一次壓縮兩片三角片,達到壓縮率的進一步提升。第二個演算法Algorithm II 主要是利用空間的區域性 (Spatial Locality) 減少切割所造成的額外浪費,也就是說經由考慮幾何特性提出適當的簡化規則,當切割發生時,省略最後一片三角片,減少分支所造成的浪費。最後一個演算法Algorithm III是將Algorithm I 及Algorithm II 做進一步的結合,以提升整體的壓縮效率及執行時間。
另一個被利用於本論文的演算技巧是適性算數編碼法(Adaptive Arithmetic Coder),它可進一步增加壓縮的效率。從大量的實驗數據觀察到,我們所提出的演算法其平均壓縮率均優於Valence-Driven 及 Edgebreaker 演算法。從熵/壓縮率(Entropy/Compression) 相對應的曲線比較也可得知,我們的演算法是較接近熵(Entropy)的壓縮方式的。此外我們的演算法只需要考慮固定的運算元數目及它們的值之間分布情形,即可得到最佳化壓縮率。
主要貢獻
1. 在本論文中,將我們的演算法壓縮率與J. Rossignac的演算法壓縮率作一個比較,並且對頂點暫存器的效能作一個統計,頂點暫存器所設定的容量為256,因此當邊界圈長度不超過256時,沒有頂點需要被重傳,所以當頂點傳輸次數超過頂點數,表示邊界圈長度曾經超過256。測試模型為Wavefront的檔案格式,我們已經將連接度的壓縮率由平均每片三角片1.62位元降低到0.98位元,在頂點傳輸次數也達到平均每個頂點傳輸1.01次。相對於之前的研究,我們將解壓縮演算法由需要兩次解讀降低到一次解讀即可,並且可以在有限的繪圖資源裡降低頂點重傳率。
2. 在本論文中將我們的演算法與J. Rossignac的演算法做比較,其中我們將CR兩個運算元合併為Q運算元,並且不須使用運算元E,以提昇演算法的壓縮率。我們共實驗了260個模型,從論文的實驗數據可以清楚的看出我們已經將連接度的壓縮率由平均每片三角片1.62位元降低到0.92位元。
3. 由於我們使用Q運算元來表示CR兩個運算元,以及利用幾何特徵來避免使用E運算元,所以我們的方法在壓縮率方面提高很多。為了進一步了解利用幾何特徵來避免使用E運算元可以獲得多少改善,因此我們不使用Q運算元而直接使用CR兩個運算元來編碼,由論文中的實驗數據可以看出平均每片三角片的壓縮率還是可以維持在1.22位元。
4. 另一方面在本論文中,提出改良型的編碼(Coding)方式,採用適性算術編碼法(Adaptive Arithmetic Coding)。利用Adaptive N-order Model 的特性控制運算元(Operator)出現的機率,並且採用區域性(Locality)避免某運算元出現機率過大造成其它運算元必須犧牲採用較大的浮點數表示式。
博士論文題目:三角網格關聯性之研究
Connectivity Compression for Triangular Meshes
內容摘要
三度空間立體模型之單一連接性(Single-Rate Connectivity)壓縮法之研究,可區分成以邊為礎 (EdgeBased) 及以頂點為基礎 (Vertex-Based) 兩類;Edgebreaker是以邊為基礎的代表方法,而Valence-Driven是以頂點為基礎的代表方法。此兩者均需要使用切割運算元將三度空間立體模型切割成兩個部份,也因為切割的影響將造成額外記錄距離的負擔或額外的運算位元來辨識切割處,進而降低壓縮的品質。Edgebreaker 演算法的主要缺點有二:第一為多次路徑 (Multiple Pass Traversals) 的壓縮三角片,此方式將造成執行時間的大量浪費。第二為反向的解壓縮程序,此操作程序將使得解壓縮的過程必須在離線 (Off-Line) 的狀態下進行。Valence-Driven 演算法的缺點是在不知道三角網格的分支資訊時,需要額外的演算程序,計算每一個頂點的分支度 (Degree) 。為了克服以上的限制,本論文提出了三個針對單一解析度 (Single-Resolution) 物體之壓縮演算法來解決三角網格連接性的問題。我們的演算法能夠單一路徑的壓縮及解壓縮,並且能在及時 (On-Line) 的模式下進行整個程序。
我們提出的三個演算法分別稱為Algorithm I 、Algorithm II及Algorithm III。在Algorithm I 的演算法中,我們提出了J運算元,其主要的功能是跳至作用邊的下一個邊,避免切割的情形發生造成額外的運算元浪費。並且藉由使用Q運算元一次壓縮兩片三角片,達到壓縮率的進一步提升。第二個演算法Algorithm II 主要是利用空間的區域性 (Spatial Locality) 減少切割所造成的額外浪費,也就是說經由考慮幾何特性提出適當的簡化規則,當切割發生時,省略最後一片三角片,減少分支所造成的浪費。最後一個演算法Algorithm III是將Algorithm I 及Algorithm II 做進一步的結合,以提升整體的壓縮效率及執行時間。
另一個被利用於本論文的演算技巧是適性算數編碼法(Adaptive Arithmetic Coder),它可進一步增加壓縮的效率。從大量的實驗數據觀察到,我們所提出的演算法其平均壓縮率均優於Valence-Driven 及 Edgebreaker 演算法。從熵/壓縮率(Entropy/Compression) 相對應的曲線比較也可得知,我們的演算法是較接近熵(Entropy)的壓縮方式的。此外我們的演算法只需要考慮固定的運算元數目及它們的值之間分布情形,即可得到最佳化壓縮率。
主要貢獻
1. 在本論文中,將我們的演算法壓縮率與J. Rossignac的演算法壓縮率作一個比較,並且對頂點暫存器的效能作一個統計,頂點暫存器所設定的容量為256,因此當邊界圈長度不超過256時,沒有頂點需要被重傳,所以當頂點傳輸次數超過頂點數,表示邊界圈長度曾經超過256。測試模型為Wavefront的檔案格式,我們已經將連接度的壓縮率由平均每片三角片1.62位元降低到0.98位元,在頂點傳輸次數也達到平均每個頂點傳輸1.01次。相對於之前的研究,我們將解壓縮演算法由需要兩次解讀降低到一次解讀即可,並且可以在有限的繪圖資源裡降低頂點重傳率。
2. 在本論文中將我們的演算法與J. Rossignac的演算法做比較,其中我們將CR兩個運算元合併為Q運算元,並且不須使用運算元E,以提昇演算法的壓縮率。我們共實驗了260個模型,從論文的實驗數據可以清楚的看出我們已經將連接度的壓縮率由平均每片三角片1.62位元降低到0.92位元。
3. 由於我們使用Q運算元來表示CR兩個運算元,以及利用幾何特徵來避免使用E運算元,所以我們的方法在壓縮率方面提高很多。為了進一步了解利用幾何特徵來避免使用E運算元可以獲得多少改善,因此我們不使用Q運算元而直接使用CR兩個運算元來編碼,由論文中的實驗數據可以看出平均每片三角片的壓縮率還是可以維持在1.22位元。
4. 另一方面在本論文中,提出改良型的編碼(Coding)方式,採用適性算術編碼法(Adaptive Arithmetic Coding)。利用Adaptive N-order Model 的特性控制運算元(Operator)出現的機率,並且採用區域性(Locality)避免某運算元出現機率過大造成其它運算元必須犧牲採用較大的浮點數表示式。
主要研究成果(一)
Bin-Shyan Jong, Tsong-Wuu Lin, Wen-Hao Yang and Juin-Ling Tseng “Improved Edge-Based Compression for the Connectivity of 3D Models,” IEICE Transactions on Information & Systems,Vol. E87-D, No. 12, pp. 2845-2854, Dec. 2004;(SCI/EI 期刊)(前兩位作者為申請人之指導教授)
發表於國外知名電子資訊系統期刊(IEICE),主要的研究成果說明如下:
將虛擬實境應用於網際網路可說是目前相當熱門的話題焦點,但是由於網路的頻寬有限,如果要將兩者搭配,其中最大問題就在於3D模型檔案的大小;為了視覺的享受,模型的品質必須控制在一定的精細度,因為有這方面的考量,檔案容量往往都非常的大,在網路上傳輸是非常不利的,而網際網路最重要的考慮因素就是速度,如果讓使用者的等待時間過長而失去耐性,即使內容再精采、畫面再細緻也是徒然。
基於上述的原因,如果將想要透過網路傳送的3D幾何圖形先行壓縮,將其檔案容量縮小,那麼傳輸的時間將大大地降低。若要描繪的3D模型,也事先予以壓縮而儲存在主記憶體中;當繪圖管線要進行描繪時,先透過即時的解壓縮處理器,就可以描繪出正確的模型;雖然多了壓縮和解壓縮的動作,但是,記憶體匯流排頻寬不足的問題卻可以迎刃而解,使得較低階的工作站也能克服原先無法處理的問題了。
在本篇論文中,我們提出一個新的三角形網狀壓縮法,以G. Taubin與J. Rossignac的壓縮率為比較對象,由於兩者的演算法都需要經過兩次讀取才能夠解壓縮。我們的改良型的三角形網狀壓縮法,只需一次讀取就可以解壓縮,且在所使用的編碼運算元上,比J. Rossignac所提出的編碼運算元少一個,我們共實驗了260個模型,並且我們已經將連接度的壓縮率由平均每片三角片1.67位元降低到0.92位元。不但壓縮率更佳,並且達到隨壓隨解隨繪的效果。
主要研究成果(二)
Bin-Shyan Jong, Wen-Hao Yang and Shawn Song “Efficient Edge-Based Compression Algorithm for 3D Models with Holes and Handles,” Journal of Information Science and Engineering, Vol.22, No.3, page: 401-423, 2006;(SCI/EI 期刊) (第一位作者為申請人之指導教授)
發表於國外知名電子資訊工程期刊(JISE),主要的研究成果說明如下:
自從電腦問世以來,電腦的執行速度快速的增加,人們對電腦的要求也與日俱增,單色、彩色、多媒體都已經沒有辦法滿足無止盡的視覺慾望,現在人們要的是虛擬實境。
隨著網際網路的發達,世界進入了一個新的領域,所有的資訊是以秒來當作傳遞的時間單位,在地球任何一個角落的訊息,只要手指輕按,畫面倏忽展開在眼前。原本平面的網際網路,現在立體起來了,虛擬商店、虛擬博物館、虛擬水族箱、虛擬樣品屋…等,如雨後春筍般佔據了各大網站,這一切的一切只是因為人們要的是虛擬實境。
虛擬實境與網際網路可說是目前相當熱門的話題焦點,由於網路的頻寬有限,如果要將兩者搭配,其中最大問題就在於立體模型檔案的大小,為了視覺的享受,模型的品質必須控制在一定的精細度,因為有這方面的考量,檔案容量往往都非常的大,在網路上傳輸是非常不利的,而網際網路最重要的考慮因素就是速度,如果讓使用者的等待時間過長而失去耐性,即使內容再精采、畫面再細緻也是徒然。
在此勢必要對立體模型檔案作壓縮,這時有三點是需要考量的因素:
第一、檔案壓縮率要高,以利遠端傳輸。
第二、演算法要簡單,能即時解讀。
第三、提供資料流(Stream),達到隨解隨繪的服務。
本論文所提出的演算法能夠兼顧到壓縮率與快速繪圖兩方面,前者的精髓在於連接性的壓縮,後者則希望能減少頂點在硬體中的重傳率,並且在繪圖時減少頂點的替換率。其結果在連接度的壓縮率由平均每片三角片1.62位元降低到0.98位元,而在頂點傳輸次數也達到平均每個頂點傳輸1.01次。
主要研究成果(三)
Bin-Shyan Jong, Juin-Ling Tseng and Wen-Hao Yang “Efficient and Low-Error Mesh Simplification Method Based on Torsion Detection” Visual Computer, 2006. Vol.22, No.1, page: 56-67; (SCI/EI 期刊) (第一位作者為申請人之指導教授)
國外知名虛擬電腦期刊(VC)小地方的修改,主要的研究成果說明如下:
近年來,在計算機圖學的領域中,許多的學者專家皆致力於顯像的逼真上。為了達到逼真的效果,通常會利用數萬片以上的三角片來建構所需之立體模型;如此一來,雖然可以達到“顯像逼真”的效果,但是相對地,也將導致計算量的增加。因此,如何在儘可能保持物體原來外形的前提下,減少三角形的數目(Triangle Reduction),便成為近年來最引人深究的主要課題之一,而此一問題也就是所謂 “網格簡化”(Mesh Simplification)的問題。
“網格簡化”的目的是希望能在保持一定品質的前提之下,減少物體模型所需的三角片個數。而在此領域之中,已有許多學者進行相關研究,其中,Garland所提出的點對收縮法是一個相當有效的簡化方法,但是,該方法僅利用頂點與相鄰三角片之間的距離關係做為簡化時之依據,並未考慮該點所在區域之副法向量變化情形。然而事實上,該頂點的副法向量變化情形卻隱含著該頂點的特徵強度;因此,為了儘可能維持該模型的主要特徵,本論文提出計算副法向量變化的扭率偵測法,來改善Garland所提出的點對收縮法,進而保留該模型所需之外觀特徵。為了驗證本論文的成效,本論文除了將呈現簡化後的效果,以及與Garland所提出的點對收縮法做比較之外,更將利用Metro誤差偵測工具以及影像比較法,來做為誤差的驗證工具,進一步驗證本論文所提方法的效能。
另外,在簡化效率方面,為了有效簡化物體模型,通常會花費比簡化更多的時間來進行分析及記錄,以便能獲得更好的簡化結果。在本論文中,我們所提出的方法亦將提供一個更有效率的特徵偵測方式;因此,除了在外觀上能有效保留模型特徵之外,在效率上期待能縮短因分析所花費的時間成本。
Bin-Shyan Jong, Tsong-Wuu Lin, Wen-Hao Yang and Juin-Ling Tseng “Improved Edge-Based Compression for the Connectivity of 3D Models,” IEICE Transactions on Information & Systems,Vol. E87-D, No. 12, pp. 2845-2854, Dec. 2004;(SCI/EI 期刊)(前兩位作者為申請人之指導教授)
發表於國外知名電子資訊系統期刊(IEICE),主要的研究成果說明如下:
將虛擬實境應用於網際網路可說是目前相當熱門的話題焦點,但是由於網路的頻寬有限,如果要將兩者搭配,其中最大問題就在於3D模型檔案的大小;為了視覺的享受,模型的品質必須控制在一定的精細度,因為有這方面的考量,檔案容量往往都非常的大,在網路上傳輸是非常不利的,而網際網路最重要的考慮因素就是速度,如果讓使用者的等待時間過長而失去耐性,即使內容再精采、畫面再細緻也是徒然。
基於上述的原因,如果將想要透過網路傳送的3D幾何圖形先行壓縮,將其檔案容量縮小,那麼傳輸的時間將大大地降低。若要描繪的3D模型,也事先予以壓縮而儲存在主記憶體中;當繪圖管線要進行描繪時,先透過即時的解壓縮處理器,就可以描繪出正確的模型;雖然多了壓縮和解壓縮的動作,但是,記憶體匯流排頻寬不足的問題卻可以迎刃而解,使得較低階的工作站也能克服原先無法處理的問題了。
在本篇論文中,我們提出一個新的三角形網狀壓縮法,以G. Taubin與J. Rossignac的壓縮率為比較對象,由於兩者的演算法都需要經過兩次讀取才能夠解壓縮。我們的改良型的三角形網狀壓縮法,只需一次讀取就可以解壓縮,且在所使用的編碼運算元上,比J. Rossignac所提出的編碼運算元少一個,我們共實驗了260個模型,並且我們已經將連接度的壓縮率由平均每片三角片1.67位元降低到0.92位元。不但壓縮率更佳,並且達到隨壓隨解隨繪的效果。
主要研究成果(二)
Bin-Shyan Jong, Wen-Hao Yang and Shawn Song “Efficient Edge-Based Compression Algorithm for 3D Models with Holes and Handles,” Journal of Information Science and Engineering, Vol.22, No.3, page: 401-423, 2006;(SCI/EI 期刊) (第一位作者為申請人之指導教授)
發表於國外知名電子資訊工程期刊(JISE),主要的研究成果說明如下:
自從電腦問世以來,電腦的執行速度快速的增加,人們對電腦的要求也與日俱增,單色、彩色、多媒體都已經沒有辦法滿足無止盡的視覺慾望,現在人們要的是虛擬實境。
隨著網際網路的發達,世界進入了一個新的領域,所有的資訊是以秒來當作傳遞的時間單位,在地球任何一個角落的訊息,只要手指輕按,畫面倏忽展開在眼前。原本平面的網際網路,現在立體起來了,虛擬商店、虛擬博物館、虛擬水族箱、虛擬樣品屋…等,如雨後春筍般佔據了各大網站,這一切的一切只是因為人們要的是虛擬實境。
虛擬實境與網際網路可說是目前相當熱門的話題焦點,由於網路的頻寬有限,如果要將兩者搭配,其中最大問題就在於立體模型檔案的大小,為了視覺的享受,模型的品質必須控制在一定的精細度,因為有這方面的考量,檔案容量往往都非常的大,在網路上傳輸是非常不利的,而網際網路最重要的考慮因素就是速度,如果讓使用者的等待時間過長而失去耐性,即使內容再精采、畫面再細緻也是徒然。
在此勢必要對立體模型檔案作壓縮,這時有三點是需要考量的因素:
第一、檔案壓縮率要高,以利遠端傳輸。
第二、演算法要簡單,能即時解讀。
第三、提供資料流(Stream),達到隨解隨繪的服務。
本論文所提出的演算法能夠兼顧到壓縮率與快速繪圖兩方面,前者的精髓在於連接性的壓縮,後者則希望能減少頂點在硬體中的重傳率,並且在繪圖時減少頂點的替換率。其結果在連接度的壓縮率由平均每片三角片1.62位元降低到0.98位元,而在頂點傳輸次數也達到平均每個頂點傳輸1.01次。
主要研究成果(三)
Bin-Shyan Jong, Juin-Ling Tseng and Wen-Hao Yang “Efficient and Low-Error Mesh Simplification Method Based on Torsion Detection” Visual Computer, 2006. Vol.22, No.1, page: 56-67; (SCI/EI 期刊) (第一位作者為申請人之指導教授)
國外知名虛擬電腦期刊(VC)小地方的修改,主要的研究成果說明如下:
近年來,在計算機圖學的領域中,許多的學者專家皆致力於顯像的逼真上。為了達到逼真的效果,通常會利用數萬片以上的三角片來建構所需之立體模型;如此一來,雖然可以達到“顯像逼真”的效果,但是相對地,也將導致計算量的增加。因此,如何在儘可能保持物體原來外形的前提下,減少三角形的數目(Triangle Reduction),便成為近年來最引人深究的主要課題之一,而此一問題也就是所謂 “網格簡化”(Mesh Simplification)的問題。
“網格簡化”的目的是希望能在保持一定品質的前提之下,減少物體模型所需的三角片個數。而在此領域之中,已有許多學者進行相關研究,其中,Garland所提出的點對收縮法是一個相當有效的簡化方法,但是,該方法僅利用頂點與相鄰三角片之間的距離關係做為簡化時之依據,並未考慮該點所在區域之副法向量變化情形。然而事實上,該頂點的副法向量變化情形卻隱含著該頂點的特徵強度;因此,為了儘可能維持該模型的主要特徵,本論文提出計算副法向量變化的扭率偵測法,來改善Garland所提出的點對收縮法,進而保留該模型所需之外觀特徵。為了驗證本論文的成效,本論文除了將呈現簡化後的效果,以及與Garland所提出的點對收縮法做比較之外,更將利用Metro誤差偵測工具以及影像比較法,來做為誤差的驗證工具,進一步驗證本論文所提方法的效能。
另外,在簡化效率方面,為了有效簡化物體模型,通常會花費比簡化更多的時間來進行分析及記錄,以便能獲得更好的簡化結果。在本論文中,我們所提出的方法亦將提供一個更有效率的特徵偵測方式;因此,除了在外觀上能有效保留模型特徵之外,在效率上期待能縮短因分析所花費的時間成本。