《最優Voronoi剖分的理論和套用研究》是依託廈門大學，由陳中貴擔任項目負責人的面上項目。
基本介紹
- 中文名：最優Voronoi剖分的理論和套用研究
- 項目類別：面上項目
- 項目負責人：陳中貴
- 依託單位：廈門大學
項目摘要,結題摘要,
項目摘要
本項目提出了最優Voronoi剖分（Optimal Voronoi Tessellation，簡稱OVT）的全新概念，並研究OVT的完整理論系統，在很大程度上推廣了重心Voronoi剖分（CVT）方法，為圖形學領域的多個套用問題提供功能強大的統一解決方案。首先從任意給定函式的任意階分片多項式逼近角度定義OVT的目標函式，通過研究OVT函式的光滑性和梯度計算公式，給出OVT快速生成算法；結合高效的局部最佳化算法設計有效的全局最佳化算法，並研究OVT函式全局最優解對應的參數域剖分結構特點；系統比較OVT方法、CVT方法和最優Delaunay三角化（ODT）方法，揭示三種方法的內在關係和優缺點。最後基於統一的變分框架，將OVT方法套用於格線生成、重新格線化、函式/圖像逼近、藍噪聲採樣等問題。初步實驗結果已經顯示出OVT方法的有效性和優越性。
結題摘要
幾何區域的離散剖分生成是一個基礎而重要的問題，在很多領域具有重要的套用。雖然各向同性格線剖分的生成問題已經得到較好的研究，但是將複雜幾何區域轉換成各向異性格線的研究相對落後。各向異性剖分在節約計算成本和提高數值解精度方面通常是有利的，而且圖形學中的很多問題都可以歸結為求解最優剖分的問題。為生成最優格線剖分，本項目提出了最優Voronoi剖分的概念，取得的主要理論和套用成果如下。 我們擴展了先前用於生成各向同性多邊形/多面體剖分的重心Voronoi 剖分（CVT）能量函式。從函式逼近的角度來看，CVT能量函式描述了L1範數中凸函式與其下鑲嵌多面體之間的誤差。我們放寬了對CVT能量函式的近似和目標函式的約束。更確切地說，目標函式不一定是凸的，其通過在L2範數中的子區域上單獨定義的多項式函式來近似。我們使用更一般的Power圖來表示給定域的剖分，從而可以有效地解決能量最小化問題。Power圖是一種廣義的Voronoi剖分。最小化目標函式歸結為找到區域的最佳廣義Voronoi劃分，為了有效地解決我們提出的目標函式的最小化問題，我們設計了一種混合最佳化算法。由於目標函式的非光滑性、高度非線性和非凸性，使最小化能量函式非常具有挑戰性。我們的混合最佳化方法將局部搜尋與全局最佳化技術相結合，可以降低陷入較差局部最小值的可能性，並快速收斂到足夠深的局部最小值。此外，我們還提出了一種有效的初始化方法來極大地改善結果。我們將提出的最佳化框架套用於格線生成、函式/圖像逼近、藍噪聲採樣、點雲重採樣、超像素生成、拼貼畫生成、馬賽克圖像生成、不規則物體排樣等問題，取得了很好的實驗效果，並且展現出在更多問題上的套用前景。 項目共發表學術論文21篇，其中中國計算機學會（簡稱CCF）推薦的A類期刊論文3篇，CCF推薦B類期刊論文8篇，CCF推薦C類期刊論文2篇，SCI檢索論文14篇，EI檢索論文20篇。申請發明專利5項，其中已授權發明專利3項。
