帶容積約束Voronoi圖的理論和套用研究

《帶容積約束Voronoi圖的理論和套用研究》是依託廈門大學，由陳中貴擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：帶容積約束Voronoi圖的理論和套用研究
• 項目類別：青年科學基金項目
• 項目負責人：陳中貴
• 依託單位：廈門大學

項目摘要

本項目研究帶容積約束Voronoi圖（Capacity-constrained Voronoi Diagram，簡稱CcVD）的性質、快速計算方法和套用。首先給出CcVD在簡單平面區域上的存在條件，並推廣到三維區域和空間曲面上。研究連續空間上CcVD目標函式的連續性，並給出梯度的顯式計算公式，利用擬牛頓方法快速最佳化目標函式計算CcVD。針對CcVD目標函式的特點，設計高效的全局最佳化算法。初步實驗結果表明我們計算CcVD的方法比現有方法快了兩個數量級。在CcVD的套用方面，著重研究藍噪聲採樣問題。結合中心Voronoi圖方法，設計新的目標函式，通過最佳化方法得到高質量的藍噪聲採樣結果。在統一的最佳化框架下，處理平面區域、三維區域、空間曲面等不同區域上的藍噪聲採樣問題，以及動態區域和多類（Multi-Class）藍噪聲採樣問題。現有文獻中還沒有一種採樣方法能同時處理這些採樣問題。

結題摘要

本項目主要研究帶容積約束Voronoi圖（Capacity-constrained Voronoi Diagram，簡稱CcVD）的性質、快速計算方法和套用。我們利用變分的思想計算CcVD，給出了CcVD目標函式的梯度計算公式，並採用L-BGFS方法進行快速最佳化。由於CcVD函式與變數之間的高度複雜關係，它的精確梯度公式從未在文獻中出現過。我們第一次給出了CcVD函式梯度顯式計算公式，為 CcVD 的加速計算帶來了突破性的進展，實驗表明計算速度比原有算法加快了十倍左右。在對平面區域上CcVD的性質和快速計算方法研究成果的基礎上，我們將方法推廣到一般三維曲面上對CcVD的快速計算。以往關於平面上CcVD的計算方法依賴於平面區域的離散表示，比如表示為稠密的規則或者不規則點的集合，從而很難推廣到曲面上。我們的方法基於空間的連續表達，推廣到時曲面較為順利。Voronoi圖和Delaunay三角剖分有非常密切的關係，通過系統研究最優Delaunay剖分和重心Voronoi圖的聯繫和區別，我們給出了快速計算最優Delaunay剖分的方法。另外，基於對最優Delaunay剖分目標函式非凸和C0連續性的觀察，以往的局部最佳化方法一般很難得到滿意的結果，因此我們提出了利用全局方法最佳化目標函式的想法。一般的全局最佳化算法時間複雜度都較高，我們利用最優Delaunay剖分目標函式的特殊性，再結合局部最佳化算法，給出了一個高效的全局最佳化算法。 在套用方面，我們將Voronoi剖分的理論套用於藍噪聲採樣、格線生成、圖像逼近和樣條曲面的自適應節點設定等問題，取得了很好的效果。Voronoi剖分理論之所以能成功套用於這些問題，關鍵在於本質上它們都可以看成為是一個函式逼近問題。所以從函式逼近的角度，我們可以研究更加一般的Voronoi剖分和三角剖分的生成方法，為未來的研究打開一個全新的思路。