[發明專利]基于簡單互斥操作的藍噪聲采樣方法

有效

• 申請號: 201611069196.5
• 申請日: 2016-11-28
• 公開（公告）號: CN106780746B
• 公開（公告）日: 2020-03-27
• 發明（設計）人: 郭建偉;嚴冬明;王逸群;張曉鵬
• 申請（專利權）人: 中國科學院自動化研究所
• 主分類號: G06T17/30
• 分類號: G06T17/30
• 代理公司: 北京瀚仁知識產權代理事務所(普通合伙) 11482
• 代理人: 宋寶庫

本發明涉及一種基于簡單互斥操作的藍噪聲采樣方法，應用于藍噪聲的采樣區域中，包括以下步驟：步驟A，在所述采樣區域中進行隨機采樣，得到采樣點集；步驟B，在所述采樣點集中選取任一采樣點；步驟C，根據預設的空間約束參數，對所述采樣點集做優化處理；步驟D，若優化處理后的采樣點集完全收斂，得到基于所述采樣點收斂的采樣點集；否則轉到步驟C，對所述優化處理后的采樣點集做迭代優化處理；步驟E，重復上述步驟B～D，直至所述采樣點集基于每一個采樣點的優化處理后完全收斂，得到最終的藍噪聲采樣點集。本發明中，不僅實現了產生優質的藍噪聲采樣，并直接實施空間約束，同時提升了重新網格化的質量。

技術領域

本發明屬于計算機圖形處理技術領域，具體涉及計算機圖形學處理中的采樣方法，特別涉及一種基于簡單互斥操作的藍噪聲采樣方法。

背景技術

在計算機圖形學中，頂點集合是無處不在的。在不同的應用之中，要求點集所具有的特征也是不同的。在眾多的點集中，具有藍噪聲特性的各向同性的點集具有重要的應用，被廣泛的應用于抖動抗鋸齒、圖像點繪、物體分布、網格化和重新網格化等領域。

藍噪聲可以用一種傅里葉頻譜來描述，這種頻譜在低頻時具有低能量，在頻率上升時會出現一個尖銳的峰值(對應相鄰點的平均距離)，之后在高頻時又產生平坦的頻譜。從幾何的角度來看，其對應的點集分布是均勻而不規則的。均勻意味著一個均勻密度的點集，沒有顯見的簇或者洞，就像低頻能量一樣。不規則意味著點與點之間并不和諧，因此在高頻段十分平坦，在出現峰值之后會快速下降的諧波。對于簇，可以利用點集中的最小近鄰距離來檢測，洞則可以利用鄰近點的最大距離表示，這兩種表示方法通常用來衡量等密度的三角網格質量。最后，對于不規則的點集，還可以用相等的Voronoi細胞容積表示其全局的均勻性質。

藍噪聲采樣(Blue Noise Sampling)通常初始化為一個隨機的采樣點集(具有平坦的頻譜)，然后利用一些局部約束使其低頻能量變小。產生泊松圓盤采樣點集的經典方法是投擲法，該方法首先由Cook提出，并在此之后又被較大的改進。然而，該方法噪聲很大，往往具有很大的洞和過小的，導致狹窄的低能量帶，因此不是理想的各向同性采樣方法。之后，為了增大泊松圓盤采樣的半徑，McCool和Fiume提出了使用Lloyd(勞埃德)算法來松弛點集，使其形成一個重心Voronoi(沃羅諾伊)圖。然而Voronoi圖的問題是它太規則了，導致能量集中在一些諧波頻率上，從而導致混疊效應。在過去的幾年中，許多優化算法被提出來替代Lloyd方法，產生更好的藍噪聲性質，如CCVT(Capacity Constrained VoronoiTessellations，約束Voronoi細胞容積方法)、BNOT(Blue Noise through OptimalTransport，最優傳輸算法)、FPO(Farthest Point Optimization，最遠點優化方法)、CCDT(Capacity Constrained Delaunay Triangulation，約束Delaunay三角性容積)方法等。此外，除了使用顯式的空間約束，還有一些方法采用一個模擬仿真的方法來類似約束。比如，用核代表點集，利用統計力學的方法模擬核之間的交互、或者是利用平滑粒子流體動力學仿真的方法等。這些方法產生相似但不完全相同的點集，從而導致不同的藍噪聲特性

雖然現在有許多基于簡單互斥操作的藍噪聲采樣方法，但是每一個方法都存在以下一個或幾個方面存在缺點：速度、內存消耗、編程復雜度、采樣點數控制等。就我們所知，沒有單一的算法可以理想地解決上述所有問題，因此需要進行權衡。例如，FPO方法達到了最大泊松圓盤半徑(沒有簇)，但是卻會產生洞，CCDT消除洞但卻會產生簇，CCVT和BNOT雖然更平均，但是泊松圓盤半徑卻不能達到最大。

另外一方面，現有方法的優化目標過于單一，比如僅僅考慮容積限制，或者是最大化最小距離等。因此空間約束并沒有用盡，所以藍噪聲采樣方法的探索始終活躍，以產生高效或更好的藍噪聲特性。