固定点数的二维等半径最大化泊松圆盘采样方法及系统

技术领域

本发明实施例涉及技术领域，具体涉及一种固定点数的二维等半径最大化泊松圆盘采样方法及固定点数的二维等半径最大化泊松圆盘采样系统，但绝不限于此。

背景技术

在计算机图形学领域，泊松圆盘采样是一个基础的研究问题，采样得到的点集分布既满足随机性又满足均匀性，并具有蓝噪声特性的频谱。它在很多实际应用中扮演着重要的角色，如图像渲染[1]，数字半色调[2,3]，物体分布[4,5]以及纹理合成[6]等。

一个理想的泊松圆盘采样点集需要满足三个条件：1.无偏差采样性质(每个采样区域没有被覆盖的点都有相同的概率接受一个新的采样点)；2.最小距离性质(任意两个采样点之间的距离大于给定的采样半径)；3.最大化性质(采样区域被所有的采样圆盘完全覆盖)。满足这三个条件的采样方法称为最大化泊松圆盘采样(Maximal Poisson-disk Sampling--MPS)。

产生泊松圆盘采样的经典方法叫做投镖法(Dart Throwing--DT)[7]。该方法的基本思想是设定采样半径，然后每次随机产生一个采样点，如果新的采样点与已有的采样点不冲突，则接受该采样点，否则，拒绝该采样点。针对传统的投镖法在效率和质量方面的不足，后续研究者提出许多有效的数据结构对投镖法进行加速和改进，如扇区[8]、Voronoi图[9]、动态四叉树[10,11,12]、隐性四叉树[13]、Power图[14]等。虽然投镖法及其变种可以生成高质量的采样点集。但是，这类方法有一个共同的缺点，即无法精确地控制采样点的数目。鉴于此，等[15]提出了最远点采样优化(Farthest Point Optimization--FPO)，其主要思想是最大化采样点集的全局最短距离。但是，FPO是一个确定性的方法，它每次将新的采样点插入到“最远点”(剩余点集构成的Delaunay三角化的最大空圆的圆心)。借鉴FPO的思想，Yan等[16]提出了最短边移除算法(Shortest Edge Removal--SER)。该方法每次选择一个最短边并随机地移除其中一个端点，然后把它插入到“最远点”。但是，SER方法不能保证达到最大化采样属性。

有鉴于此，特提出本发明。

有关文献参见如下：

[1]Mitchell D P.Generating antialiased images at low sampling densities.In Proc.the 14th ACM SIGGRAPH,1987,65-72；

[2]Yellot J.I.Spectral analysis of spatial sampling by photoreceptors:Topological disorder prevents aliasing.Vision Research,1982,22:1205-1210；

[3]Yellot J.I.Spectral consequences of photoreceptor sampling in the rhesus retina.Science 221,1983,382-385；

[4]Deussen O.,Hanrahan P.,Lintermann B.,Mech R.,Pharr M.,Prusinkiewicz P.Realistic modeling and rendering of plant ecosystems.Proceedings of ACM SIGGRAPH 1998,1998,275-286；

[5]Cohen M.F.,Shade J.,Hiller S.,Deusseno.Wang tiles for image and texture generation.ACM Transactions on Graphics,2003,287-294；

[6]Wu F,Dong W,Kong Y,Mei X,Yan D.M et.al.Feature-aware natural texture synthesis.The Visual Computer,2014:1-13；

[7]Cook R.L.,Stochastic sampling in computer graphics,ACM Trans.on Graphics,1986,5(1):69-78；

[8]Dunbar D.,Humphreys G..A spatial data structure for fast Poisson-disk sample generation.ACM Trans.on Graphics(Proc.SIGGRAPH),2006,25(3):503-508；

[9]Jones T.R..Efficient generation of Poisson-disk sampling patterns.Journal of Graphics Tools,2006,11(2):27-36；

[10]White K.B.,Cline D.,Egbert P.K..Poisson disk point sets by hierarchical dart throwing.in:Proceedings of the IEEE Symposium on Interactive Ray Tracing,2007,129–132；

[11]GamitoM.N.,MaddockS.C.,Accurate Multidimensional Poisson-Disk Sampling.ACM Trans.on Graphics,2009,29(1):8:1-8:19；

[12]EbeidaM.S.,PatneyA.,Mitchell S.A.,P.M.K.Andrew Davidson,Owens J.D.,Efficient maximal Poisson-disk sampling,ACM Trans.on Graphics(Proc.SIGGRAPH),2011,30(4):49:1–49:12；

[13]EbeidaM.S.,Mitchell S.A.,PatneyA.,Davidson A.A.,Owens J.D.,A simple algorithm for maximal Poisson-disk sampling in high dimensions,Computer Graphics Forum(Proc.EUROGRAPHICS),2012,31(2):785–794；

[14]Yan D.-M.,Wonka P.,Gap Processing for Adaptive Maximal Poisson-Disk Sampling,ACM Trans.on Graphics,2013,32(5):148:1-148:15；

[15]T.,Heck D.,Deussen O.,Farthest-Point Optimized Point Sets with Maximized Minimum Distance,in:High Performance Graphics Proceedings,2011,35-142；

[16]Yan D.-M.,Guo J.,Jia X.,Zhang X.,Wonka P.,Blue-Noise Remeshing with Farthest Point Optimization,Computer Graphics Forum(Proc.SGP),2014,33(5):167-176；

[17]T.,DeussenO.,Accurate Spectral Analysis of Two-Dimensional PointSets,Journal of Graphics,GPU,and Game Tools,2011,15(3):152-160；

[17]A.C.,Gross M.,Analysis and synthesis of point distributions based on pair correlation,ACM Trans.on Graphics(Proc.SIGGRAPH Asia),2012,31(6):170。

发明内容

本发明实施例的主要目的在于提供一种固定点数的二维等半径最大化泊松圆盘采样方法，以解决如何实现点数固定的最大化泊松圆盘采样的技术问题。此外，本发明实施例还提出一种固定点数的二维等半径最大化泊松圆盘采样系统。

为了实现上述目的，根据本发明的一个方面，提供了以下技术方案：

一种固定点数的二维等半径最大化泊松圆盘采样方法。所述方法可以包括：

步骤1：根据用户指定的采样点数目和采样区域，生成第一采样点集；

步骤2：对所述第一采样点集进行Delaunay三角化，并提取Delaunay三角化结果中的最短边长作为第一采样半径；

步骤3：确定所述第一采样点集是否达到所述最大化泊松圆盘采样；

步骤4：在所述第一采样点集达到所述最大化泊松圆盘采样的情况下，记录所述第一采样点集及所述第一采样半径。

进一步地，所述方法还可以包括：

步骤5：在所述第一采样点集未达到最大化泊松圆盘采样的情况下，从所述第一采样点集中移除全局最短边中邻域平均边长大的采样点，得到第二采样点集且对所述第二采样点集进行Delaunay三角化，以上述三角化结果中的最短边长为第二采样半径来计算空隙区域，并采用投镖法将一随机采样点随机插入到所述第二采样点集的空隙区域，得到第三采样点集；

步骤6：对所述第三采样点集进行Delaunay三角化，提取Delaunay三角化结果中的最短边作为第三采样半径，以更新所述第一采样半径并执行所述步骤3。

进一步地，所述步骤2中提取Delaunay三角化结果中的最短边长作为第一采样半径具体可以包括：

将进行Delaunay三角化后得到的所有三角形边长进行排序，将最短边长作为所述第一采样半径。

进一步地，所述步骤3具体可以包括：根据所述采样区域中是否存在空隙三角形，来确定所述第一采样点集是否达到所述最大化泊松圆盘采样。

进一步地，所述步骤5具体可以包括：

根据以下公式确定所述全局最短边上的二采样点的邻域平均边长：

$E_{avg}=\frac{1}{N\left(v\right)}{\Sigma }_{i=1}^{N\left(v\right)}{l}_i$

其中，所述N(v)表示采样点的邻域边的数目；所述l_i表示邻域边的长度；所述E_avg表示邻域平均边长；所述i取正整数；

从所述第一采样点集中移除所述全局最短边中邻域平均边长大的采样点，得到所述第二采样点集；

对所述第二采样点集进行Delaunay三角化；

以上述三角化结果中的最短边长作为第二采样半径来计算空隙区域；

采用所述投镖法将所述一随机采样点随机插入到所述第二采样点集的空隙区域，得到所述第三采样点集。

进一步地，所述对所述第二采样点集进行Delaunay三角化还可以包括：

调整移除的全局最短边中邻域平均边长大的采样点所在三角形区域相邻的所有三角形所构成的局部区域。

进一步地，所述步骤6中对所述第三采样点集进行Delaunay三角化还可以包括：

调整步骤5插入的所述随机采样点所在三角形区域相邻的所有三角形所构成的局部区域。

为了实现上述目的，根据本发明的另一个方面，还提供了一种固定点数的二维等半径最大化泊松圆盘采样系统。该系统可以包括：

生成模块，用于根据用户指定的采样点数目和采样区域，生成第一采样点集；

第一提取模块，用于对所述生成模块生成的所述第一采样点集进行Delaunay三角化，并提取Delaunay三角化结果中的最短边长作为第一采样半径；

确定模块，用于确定所述生成模块生成的所述第一采样点集是否达到所述最大化泊松圆盘采样；

记录模块，用于在所述确定模块确定所述第一采样点集达到所述最大化泊松圆盘采样的情况下，记录所述生成模块生成的所述第一采样点集及所述第一提取模块提取的所述第一采样半径。

进一步地，所述系统还可以包括：

处理模块，用于在所述确定模块确定所述第一采样点集未达到最大化泊松圆盘采样的情况下，从所述第一采样点集中移除全局最短边中邻域平均边长大的采样点，得到第二采样点集且对所述第二采样点集进行Delaunay三角化，以上述三角化结果中的最短边长作为采样半径计算空隙区域，并采用投镖法将一随机采样点随机插入到所述第二采样点集的空隙区域，得到第三采样点集；

第二提取模块，用于对所述处理模块得到的所述第三采样点集进行Delaunay三角化，提取Delaunay三角化结果中的最短边作为第三采样半径，以更新所述第一采样半径并触发所述确定模块。

进一步地，所述确定模块具体可以包括：

确定单元，用于根据所述采样区域中是否存在空隙三角形，来确定所述生成模块生成的所述第一采样点集是否达到所述最大化泊松圆盘采样。

与现有技术相比，上述技术方案至少具有以下有益效果：

本发明实施例提出了一种固定点数的二维等半径最大化泊松圆盘采样方法和采样系统。其中，根据用户指定的采样点数目和采样区域，随机初始化一个采样点集，对该采样点集进行Delaunay三角化，并提取Delaunay三角化结果中的最短边长作为采样半径；确定采样点集是否达到最大化泊松圆盘采样；在采样点集达到所述最大化泊松圆盘采样的情况下，记录采样点集及采样半径。本发明实施例借助空隙处理方法，不断调整采样点的位置，使得全局最短距离不断增加，继而使得空隙面积不断减小，最终达到最大化属性，具有简单、易于实现、性能稳定且能够收敛的优点。本发明实施例解决了现有的最大化泊松圆盘采样算法不能精确地控制采样点数的问题，使得采样点集具有很好的蓝噪声性质，可应用于图像渲染和纹理合成等应用中。

附图说明

附图作为本发明的一部分，用来提供对本发明的进一步的理解，本发明的示意性实施例及其说明用于解释本发明，但不构成对本发明的不当限定。显然，下面描述中的附图仅仅是一些实施例，对于本领域普通技术人员来说，在不付出创造性劳动的前提下，还可以根据这些附图获得其他附图。在附图中：

图1为根据一示例性实施例示出的固定点数的二维等半径最大化泊松圆盘采样方法的流程示意图；

图2为根据另一示例性实施例示出的固定点数的二维等半径最大化泊松圆盘采样方法的流程示意图；

图3为根据一示例性实施例示出的空隙三角形的示意图；

图4为根据一示例性实施例示出的空隙基元的示意图；

图5a为根据一示例性实施例示出的最短边中邻域平均边长大的端点的示意图；

图5b为根据一示例性实施例示出的更新空隙后在空隙采样得到的新的采样点的示意图；

图5c为根据一示例性实施例示出的将采样点插入到采样点集中的示意图；

图6为根据一示例性实施例示出的根据SER、FPO、MPS和本发明实施例提出的方法得到的采样点集质量比较示意图；

图7为根据一示例性实施例示出的本发明实施例提出的方法在非周期边界的采样结果示意图；

图8为根据一示例性实施例示出的FPO和本发明实施例提出的方法的相对半径的分布情况示意图；

图9为根据一示例性实施例示出的对采样点数为0.5K、1K、2K、20K的点集进行PCF分析的结果示意图；

图10为根据一示例性实施例示出的固定点数的二维等半径最大化泊松圆盘采样系统的结构示意图；

图11为根据另一示例性实施例示出的固定点数的二维等半径最大化泊松圆盘采样系统的结构示意图。

这些附图和文字描述并不旨在以任何方式限制本发明的保护范围，而是通过参考特定实施例为本领域技术人员说明本发明的概念。

具体实施方式

下面结合附图以及具体实施例对本发明实施例解决的技术问题、所采用的技术方案以及实现的技术效果进行清楚、完整的描述。显然，所描述的实施例仅仅是本申请的一部分实施例，并不是全部实施例。基于本申请中的实施例，本领域普通技术人员在不付出创造性劳动的前提下，所获的所有其它等同或明显变型的实施例均落在本发明的保护范围内。本发明实施例可以按照权利要求中限定和涵盖的多种不同方式来具体化。

需要说明的是，在下面的描述中，为了方便理解，给出了许多具体细节。但是很明显，本发明的实现可以没有这些具体细节。

还需要说明的是，在没有明确限定或不冲突的情况下，本发明中的各个实施例及其中的技术特征可以相互组合而形成技术方案。

在实际应用中，现有的最大化泊松圆盘采样算法不能精确地控制采样点数。为此，本发明实施例提出一种固定点数的二维等半径最大化泊松圆盘采样方法。如图1和2所示，该方法可以通过步骤S100至步骤S150来实现。其中：

S100：根据用户指定的采样点数目和采样区域，生成第一采样点集。

在本步骤中，可以根据采样区域的形状，一次性地以随机数的形式指定采样区域内的一个点的坐标(例如：x,y坐标)，从而得到一个随机点。反复执行N次，即可得到N个随机点。

作为示例，假设用户指定的采样点数为N，采样区域为Ω，采样点集(也即随机点集)为X；则，在采样区域Ω中随机采样N个点，得到采样点集

S110：对第一采样点集进行Delaunay三角化，并提取Delaunay三角化结果中的最短边长作为第一采样半径。

其中，Delaunay三角化(DT)是对采样区域Ω内的有限点集P进行三角剖分，使得在采样区域Ω中的点严格处于DT(P)中任意一个三角形外接圆的外部。Delaunay三角化最大化了此三角剖分中三角形的最小角，尽量避免出现“极瘦”的三角形。其命名来源于BorisDelaunay，以纪念他自1934年在此领域的工作，是本领域中公知的算法，在此不再赘述。

在本步骤中，提取Delaunay三角化结果中的最短边长作为第一采样半径具体可以包括：将进行Delaunay三角化后得到的所有三角形边长进行排序，将最短边长作为第一采样半径。

S120：确定第一采样点集是否已经达到最大化泊松圆盘采样。若是，则执行步骤S130；否则，执行步骤S140。

其中，达到最大化泊松圆盘采样是指Delaunay三角化结果中不存在空隙三角形。如果一个三角形的Voronoi中心未被三角形三个顶点对应的采样圆盘覆盖，则该三角形就是空隙三角形。点所对应的采样圆盘是指以点为中心，以当前采样半径为半径的圆。图3示例性地示出了空隙三角形。其中，P_i、P_j、P_k表示三角形t的三个顶点，C_t表示Voronoi图的一个顶点。

具体地，本步骤可以根据采样区域中是否存在空隙三角形，来确定是否已经达到最大化泊松圆盘采样。

S130：记录第一采样点集及第一采样半径。

S140：从第一采样点集中移除全局最短边中邻域平均边长大的采样点，得到第二采样点集且对第二采样点集进行Delaunay三角化，以上述三角化的最短边长为第二采样半径来计算空隙区域，并采用投镖法将一随机采样点随机插入到第二采样点集的空隙区域，得到第三采样点集。

具体地，本步骤可以包括：

S141：根据以下公式确定全局最短边上的两个采样点的邻域平均边长：

$E_{avg}=\frac{1}{N\left(v\right)}{\Sigma }_{i=1}^{N\left(v\right)}{l}_i$

其中，N(v)表示采样点的邻域边的数目；l_i表示邻域边的长度；E_avg表示邻域平均边长；i取正整数。

在本步骤中，根据上述公式确定全局最短边的两个端点的邻域平均边长，上述公式中的N(v)也就是表示端点v的邻域边(设边的一个端点为v)的数目。

S142：从第一采样点集中移除全局最短边中邻域平均边长大的采样点，得到第二采样点集。

示例性地，在Delaunay三角化(DT)结果中寻找最短的边，该最短的边有两个端点，每个端点分别有各自的邻域，比较这两个端点的邻域平均边长，将大的邻域平均边长所对应的端点移除，即从采样点集X中删除这个端点。

S143：对第二采样点集进行Delaunay三角化。

在具体实施过程中，本步骤对移除了端点的采样点集重新进行Delaunay三角化，并执行空隙检测操作。在重新进行Delaunay三角化时，需要重新调整移除的全局最短边中邻域平均边长大的采样点所在三角形区域相邻的所有三角形所构成的局部区域。

需要注意的是，由删除操作引起的Delaunay三角化(DT)的改变是动态的和局部的，更新的时间复杂度是O(1)。

S144：以上述三角化结果中的最短边长为第二采样半径来计算空隙区域。

本步骤在具体实施过程中，通过执行空隙基元(如图4所示)提取操作，来提取未被采样圆盘覆盖的空隙区域；设定采样半径为步骤S143中得到的三角化结果的最短边长。

下面结合附图对空隙处理进行详细的说明。

基于Voronoi图的理论，Yan等[14]给出了空隙存在的充要条件。如果一个三角形t满足Π(t)>0，则t是一个空隙三角形，通过处理空隙三角形可以计算空隙区域。

其中，Π(t)的定义为：

Π(t)＝dis(p,ct)-r>0(1)

其中，t表示三角形；p表示三角形t的一个顶点；r表示采样半径；c_t表示Voronoi图的一个顶点，也叫做三角形t的Voronoi中心；dis(p,c_t)表示p到c_t的欧氏距离。

其中，空隙区域是指：采样区域Ω中没有被采样顶点的采样圆盘覆盖的那部分区域。采样顶点的采样圆盘是指以采样点为中心，当前记录的采样半径为半径的圆。

上述公式(1)可以描述为：如果一个三角形的Voronoi中心未被三角形三个顶点对应的采样圆盘覆盖，则该三角形就是空隙三角形。

空隙处理主要包含两个操作，其分别为空隙检测和空隙基元提取。

对于空隙检测操作，主要是分析当前采样点集中是否存在空隙以及它们的具体位置。如果不存在空隙，则可以确认采样点集已经达到最大化。因为空隙三角形的Voronoi中心可以在空隙三角形的外部(如图3中中间位置的小图所示)，所以一个空隙三角形未必意味着这个三角形自身包含有未被覆盖的区域。同时，一个空隙区域可能包含若干个三角形的Voronoi中心，相应地，这个空隙就有好几个空隙三角形与之对应。

因此，在实际操作中，遍历所有的Delaunay三角形，计算相应的Voronoi中心和Π(t)。如果Π(t)满足(1)式，则将其标记为空隙三角形，从而得到一系列的空隙三角形。

对于空隙基元提取操作，将所有的空隙划分为若干个简单且不重叠的凸多边形(其至多为六个边)，并将其分配给每个空隙三角形。图4示例性地示出了从深色线段围成的三角形、四边形、五边形到六边形不同类型的空隙基元。对于一个空隙三角形来说，提取与之对应的间隙基元的时间复杂度是常数(每一个空隙基元至多有六条边)，所以整个空隙基元提取的时间复杂度是O(n)，其中，n表示空隙三角形的个数。

S145：采用投镖法将一随机采样点随机插入到第二采样点集的空隙区域，得到第三采样点集。

在步骤S144提取的空隙区域中随机产生一个采样点，并将此采样点插入到采样点集X中，也就是采用投镖法将该采样点随机插入到以当前采样半径计算得到的空隙区域内，从而得到第三采样点集。

S150：对第三采样点集进行Delaunay三角化，提取Delaunay三角化结果中的最短边作为第三采样半径，以更新第一采样半径并执行步骤S120。

在本步骤中，当返回执行步骤S120时，将第三采样点集作为第一采样点集，将第三采样半径作为第一采样半径，继续判断是否已经达到最大化泊松圆盘采样，直至达到终止条件。

由插入操作引起的Delaunay三角化的改变也是动态的和局部的，其局部更新的时间复杂度是O(1)。

具体地，本步骤在对第三采样点集进行Delaunay三角化时，还可以包括：需要重新调整步骤S140新插入的随机采样点所在三角形区域相邻的所有三角形所构成的局部区域。

图5a-5c示例性地示出了一次完整的迭代过程。其中，深灰色的多边形表示近似的空隙区域，浅灰色的圆表示采样圆盘。图5a中虚线框中的点P是选中的最短边中邻域平均边长大的端点。首先移除点P，并局部更新DT，以当前的最短边长为采样半径绘制圆盘。然后，更新空隙，并在空隙采样得到新的点Q，如图5b中的虚线框所示。最后，将Q点插入到采样点集中，如图5c所示。这样就完成了一次迭代过程。

对于区域Ω的边界非周期的情况下，在尖锐的角点处(例如：四边形的四个角点)进行采样，并将其固定，这些点不参与后续的优化过程。其次，执行迭代优化方法，然后，将Voronoi单元与边界相交的采样点投影到边界上，重新执行本发明实施例提出的方法。重复进行以上过程，直到相对半径没有明显变化为止，在实际应用中这一过程一般只需要重复5～10次即可收敛。通过投影处理后，可以进一步地增大相对半径。

图6示例性地示出了根据SER[16]、FPO[15]、MPS[14]和本发明实施例提出的方法(即OURS)得到的采样点集质量比较示意图。其中，采样区域是周期边界的正方形区域，采样点数为1024，由于MPS方法不能精确控制采样点数，所以其点数近似为1024。图6从上到下分别为：采样点集、PSA分析结果[17]、PCF分析结果[18]。其中，PSA分析包括：功率谱(图6的第二行)，半径平均(图6的第三行)和各向异性(图6的第四行)；PCF分析包括：成对相关函数(图6的第五行)和不规则性(图6的第六行)。从图6的第二列可以看出，相较于其他方法，FPO方法得到的点集更规则。另外，从采样点集结果和PCF的分析结果可以看出，SER和MPS的不规则性(随机性)最强，它们的PCF很快趋于平坦且不规则性略微大一些；本发明实施例提出的方法(即OURS)的不规则性次之，FPO最后，主要原因是MPS和本发明实施例提出的方法的新的采样点是随机产生的，相比FPO有更多的随机性。值得注意的是，虽然SER和MPS方法的采样策略完全不同，但是它们具有非常相似的点集质量。另外，从PSA的分析结果可以看出，本发明实施例提出的方法所产生的采样点集具有很好的蓝噪声品质。

下面以优选实施例的方式对网格质量进行分析与比较。

表1统计了SER、FPO、MPS和本发明实施例提出的方法(即OURS)四种方法的采样点集和三角化网格的质量。采样点数为4096，取100次运行结果的平均值。其中，δ_X＝d_min/d_max表示相对半径，d_min表示点集X任何点对之间的全局最短距离，表示任何点对之间的理论最大最小距离。用于衡量一个三角形的质量,a_t表示三角形t的面积，p_t表示t的半周长，l_t表示t的最长边长；Q_min和Q_avg分别表示最小和平均三角形质量。θ_min和θ_max分别表示最小和最大角度，表示所有三角形的最小角度的平均。θ<30°和θ>90°分别表示θ_min小于30°和θ_max大于90°的三角形比例。V₅₆₇％表示度数为5,6,7的顶点百分比。其中，对于δ_X、FPO的质量是最高的，本发明实施例提出的方法(即OURS)次之，MPS和SER基本相同。FPO是通过最大化最短距离来调整点集的，因此该方法的相对半径可以达到很大，而本发明实施例提出的方法介于FPO和MPS之间。从表1中可以看出，SER和MPS的结果很接近，而且SER略微地好于MPS，如图6所示。另外，除了θ_min，本发明实施例提出的方法(即OURS)的绝大部分性能指标均优于SER和MPS。如图7示例性地示出了本发明实施例提出的方法在非周期边界的采样结果，其中从左到右分别为：Wavy、Face、Dolphin、S。同时，统计了采样点集和三角化网格的质量，如表2所示。表2说明了本发明实施例提出的方法对于非周期边界采样的有效性。

表1：

表2：

本发明实施例还统计了FPO和本发明实施例提出的方法的相对半径的分布情况，如图8所示。其中，第一行对应FPO的结果；第二行对应本发明实施例提出的方法的结果。直方图的横坐标是相对半径，纵坐标是在特定相对半径范围内的实验次数。从左到右，采样点数分别为N＝0.5k、2k、10k。每一种情况执行1000次。从图8中可以看出FPO的相对半径比较集中，而本发明实施例提出的方法的相对半径有一个相对较大的变化区间，主要原因是本发明实施例提出的方法将新的采样点随机地插入到空隙区域，而不是固定的位置(采样点集最大空圆的圆心)。一定程度上，也说明了本发明实施例提出的方法具有更强的随机性。

下面以优选实施例的方式对稳定性进行分析。本发明实施例统计了数百个点到数十万个点的点集的各性能指标的变异系数CV(Coefficient of Variation)，如表1的最后一行所示。其计算方法为，性能指标的平均值除以相应的标准差。变异系数衡量不同点集的性能指标的变异程度，变异系数越小，变异(偏离)程度越小，它在一定程度上可以分析算法的稳定性，因为，对于一种采样算法，得到的不同数目的采样点集应该具有基本一致的质量。从表1可以看出，对于各个指标，本发明实施例提出的方法相应的CV值是很低的(<3.5％)，这说明本发明实施例提出的方法是很稳定的。同时，为了进一步验证算法的稳定性，可以对采样点数N＝0.5K、1K、2K、20K的点集进行PCF分析，其结果如图9所示。第一行对应PCF，第二行对应Irregularity。从图9中可以看出，不同点数的PCF分析结果基本一致。

上述实施例中虽然将各个步骤按照上述先后次序的方式进行了描述，但是本领域技术人员可以理解，为了实现本实施例的效果，不同的步骤之间不必按照这样的次序执行，其可以同时(并行)执行或以颠倒的次序执行，这些简单的变化都在本发明的保护范围之内。

基于与方法实施例相同的技术构思，本发明实施例还提供一种固定点数的二维等半径最大化泊松圆盘采样系统。该系统可以执行上述方法实施例。如图10所示，该系统可以包括生成模块11、第一提取模块12、确定模块13和记录模块14。其中，生成模块11用于根据用户指定的采样点数目和采样区域，生成第一采样点集。第一提取模块12用于对生成模块11生成的第一采样点集进行Delaunay三角化，并提取Delaunay三角化结果中的最短边长作为第一采样半径。确定模块13用于确定生成模块11生成的第一采样点集是否达到最大化泊松圆盘采样。记录模块14用于在确定模块13确定第一采样点集达到最大化泊松圆盘采样的情况下，记录所述生成模块11生成的第一采样点集及第一提取模块12提取的第一采样半径。

在一个可选的实施例中，还可以在上述系统实施例的基础上设置处理模块15和第二提取模块16。其中，处理模块15用于在确定模块13确定第一采样点集未达到最大化泊松圆盘采样的情况下，从第一采样点集中移除全局最短边中邻域平均边长大的采样点，得到第二采样点集且对第二采样点集进行Delaunay三角化，以上述三角化结果的最短边长为第二采样半径来计算空隙区域，并采用投镖法将一随机采样点随机插入到第二采样点集的空隙区域，得到第三采样点集。第二提取模块16用于对处理模块15得到的第三采样点集进行Delaunay三角化，提取Delaunay三角化结果中的最短边作为第三采样半径，以更新所述第一采样半径并触发确定模块13。

在一个可选的实施例中，上述系统实施例中的确定模块还可以包括确定单元。该确定单元用于根据采样区域中是否存在空隙，来确定生成模块生成的第一采样点集是否达到最大化泊松圆盘采样。

需要说明的是，上述实施例提供的固定点数的二维等半径最大化泊松圆盘采样系统在进行采样时，仅以上述各功能模块的划分进行举例说明，在实际应用中，可以根据需要而将上述功能分配由不同的功能模块来完成，即将系统的内部结构划分成不同的功能模块，以完成以上描述的全部或者部分功能。

本领域技术人员可以理解，上述固定点数的二维等半径最大化泊松圆盘采样系统还包括一些其他公知结构，例如处理器、控制器、存储器等，为了不必要地模糊本公开的实施例，这些公知的结构未在图10-11中示出。

应该理解，图10-11中的各个模块的数量仅仅是示意性的。根据实际需要，可以具有任意数量的各模块。

上述系统实施例可以用于执行上述方法实施例，其技术原理、所解决的技术问题及产生的技术效果相似，所属技术领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的系统的具体工作过程及有关说明，可以参考前述方法实施例中的对应过程，在此不再赘述。

应指出的是，上面分别对本发明的系统实施例和方法实施例进行了描述，但是对一个实施例描述的细节也可应用于另一个实施例。对于本发明实施例中涉及的模块、步骤的名称，仅仅是为了区分各个模块或者步骤，不视为对本发明的不当限定。本领域技术人员应该理解：本发明实施例中的模块或者步骤还可以再分解或者组合。例如上述实施例的模块可以合并为一个模块，也可以进一步拆分成多个子模块。

以上对本发明实施例所提供的技术方案进行了详细的介绍。虽然本文应用了具体的个例对本发明的原理和实施方式进行了阐述，但是，上述实施例的说明仅适用于帮助理解本发明实施例的原理；同时，对于本领域技术人员来说，依据本发明实施例，在具体实施方式以及应用范围之内均会做出改变。

需要说明的是，本文中涉及到的流程图或框图不仅仅局限于本文所示的形式，其还可以进行其他划分和/或组合。

还需要说明的是：附图中的标记和文字只是为了更清楚地说明本发明，不视为对本发明保护范围的不当限定。

再需要说明的是，本发明的说明书和权利要求书及上述附图中的术语“第一”、“第二”等是用于区别类似的对象，而不是用于描述或表示特定的顺序或先后次序。应该理解这样使用的数据在适当的情况下可以互换，以便这里描述的本发明的实施例能够以除了在这里图示或描述的那些以外的顺序实施。

术语“包括”、“包含”或者任何其它类似用语旨在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备/装置不仅包括那些要素，而且还包括没有明确列出的其它要素，或者还包括这些过程、方法、物品或者设备/装置所固有的要素。

如本文中所使用的，术语“模块”可以指代在计算系统上执行的软件对象或例程。可以将本文中所描述的不同模块实现为在计算系统上执行的对象或过程(例如，作为独立的线程)。虽然优选地以软件来实现本文中所描述的系统和方法，但是以硬件或者软件和硬件的组合的实现也是可以的并且是可以被设想的。

本发明的各个步骤可以用通用的计算装置来实现，例如，它们可以集中在单个的计算装置上，例如：个人计算机、服务器计算机、手持设备或便携式设备、平板型设备或者多处理器装置，也可以分布在多个计算装置所组成的网络上，它们可以以不同于此处的顺序执行所示出或描述的步骤，或者将它们分别制作成各个集成电路模块，或者将它们中的多个模块或步骤制作成单个集成电路模块来实现。因此，本发明不限于任何特定的硬件和软件或者其结合。

本发明提供的方法可以使用可编程逻辑器件来实现，也可以实施为计算机程序软件或程序模块(其包括执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件或数据结构等等)，例如根据本发明的实施例可以是一种计算机程序产品，运行该计算机程序产品使计算机执行用于所示范的方法。所述计算机程序产品包括计算机可读存储介质，该介质上包含计算机程序逻辑或代码部分，用于实现所述方法。所述计算机可读存储介质可以是被安装在计算机中的内置介质或者可以从计算机主体上拆卸下来的可移动介质(例如：采用热插拔技术的存储设备)。所述内置介质包括但不限于可重写的非易失性存储器，例如：RAM、ROM、快闪存储器和硬盘。所述可移动介质包括但不限于：光存储介质(例如：CD－ROM和DVD)、磁光存储介质(例如：MO)、磁存储介质(例如：磁带或移动硬盘)、具有内置的可重写非易失性存储器的媒体(例如：存储卡)和具有内置ROM的媒体(例如：ROM盒)。

以上所述的具体实施例，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施例而已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。