论文部分内容阅读
变分优化是指对于给定的问题,首先将问题建立优化模型函数,然后求解函数的极值的过程。变分优化方法是一门应用非常广泛的学科,它已经被广泛的应用到经济计划、工程设计、生产管理、交通运输、国防安全等重要领域,并逐渐受到政府部门和产业部门的高度重视。但是随着问题的复杂性越高,面对具体的问题,常规的变分优化方法已经不足以解决问题。对于不同的应用问题,我们应该采取不同的方法。能量图是Voronoi图的一种扩展形式。能量图也是计算几何领域一项及其重要的研究问题。由于能量图可以被看作是圆的Voronoi图,所以能量图非常适合求解涉及圆或者球的优化问题。所以,本文以变分优化方法的两个应用为主要研究内容:泊松圆盘采样和面向非均匀监测区域的无线传感器网络部署。针对这两个应用,我们基于能量图分别提出了相应的变分优化算法,并对算法进行了验证和分析。泊松圆盘分布是计算机图形学领域一个重要的研究方向。泊松圆盘分布是指任意两个点的距离都大于给定值的点集合。由于泊松圆盘分布具有随机性和均匀性,即蓝噪声性质,泊松圆盘分布在渲染、分布式光线追踪、点画、物体排列等领域具有广泛的应用。传统的泊松圆盘采样算法主要基于Lloyd松弛法和随机采样法。Lloyd松弛法能够保证均匀性,但是破坏了随机性,会引入较多的重复性六边形模式。随机采样法能够保证随机性,但是生成的结果均匀性较差。以往的方法不能同时较好地保持随机性和均匀性。我们利用能量图提出了一种新的泊松圆盘采样算法,该算法能够较好地保持结果的均匀性和随机性,并且算法本身比较容易控制。另外,我们对算法进行了扩展,使其可以对灰度图像做点画应用。我们的点画算法的优势是:点画结果中具有较少的重复性六边形模式,更接近手工绘制的点画作品。传统的无线传感器网络覆盖算法大多面向均匀监测区。而在实际生活中,大多数的监测区域上的时间发生概率是不均匀的。直接将以前的算法运用到非均匀监测区域上会使得传感器超载,即负载均衡问题。本文第一次提出了面向非均匀监测区域的无线传感器网络部署问题,我们的问题同时考虑到了覆盖和负载均衡两个方面。另外,我们基于能量图提出了变分优化算法来解决该问题。