高階Spline函數之波元轉換做快速表面重建

Abstract

在電腦立體視覺的研究領域中,三度空間物 體的表面重建處理(Surface reconstruction)扮演了重 要的角色.目前,該項技術的關鍵在於運算速度 的提昇.為達到快速表面重建的目標,在上一年 度所提的計畫中,我們發展了一套以波元轉換( Wavelettransform)為基礎的快速計算方法.根據初 步的研究結果顯示,經由波元轉換中的基底變 換(Basis transfer)技術,表面重建問題的計算速度 可以獲得大輻度的提昇.為了更深入探討波元 轉換在加速運算方面的實質原因,以期確切掌 握主導加速的關鍵因子.我們提出此一後續計 畫,目的在使所發展的快速表面重建計算方法 達到更實用與穩定的目標.在前期計畫中,我們以一階(First order)的三角波型為基底函數來展 開欲重建的表面,使問題離散化成一組線性方 程式.然後利用波元轉換對該線性系統做不同 解析度的基底變換,使問題在求解時的收斂條 件改善以達加速的目的.在實驗過程中,我們觀 察到在基底變換的操作下,會有諸如對角化( Diagonalization)節點相聯性加強(Node connection enhancement)、情況數值(Condition number)改變,以及 頻譜切割(Spectrum decomposition)等現象發生.這些 現象皆可能是主導計算加速的重要原因.為充 分掌握造成加速的實質因素,以使計算速度獲 得最大輻度的提昇,這些現象有必要做進一步 的分析與探討.在本計畫中,我們主要將利用不 同階數的各種基底函數來處理表面重建的問題 .觀察在不同的基底函數展開下,前敘各個現象 的變化情形.將計算速度推導成以這些現象為 變數的函數,從而歸納出主導加速運算的關鍵 因素.藉由這樣的分析結果,我們將可以了解造 成加速的主因以及不同基底組合對運算速度的 影響.同時,利用此結果輔助所發展的快速計算 方法,在最適當的基底組合以及加速因子控制 之下達到最有效且穩定的速度提昇.