蒙特卡罗算法综述Word格式文档下载.docx
《蒙特卡罗算法综述Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《蒙特卡罗算法综述Word格式文档下载.docx（11页珍藏版）》请在冰点文库上搜索。
光线碰到拍摄对象，反射正反射光或漫反射光，这就控制了色彩、物体间相互作用的反射、折射、焦散等光效，最后演绎了现实的自然光。
所以在渲染的时候，为了实现真实的场景效果，就要在渲染器中指定全局光照，全局光照有多种实现方法，例如辐射度、光线追踪、环境光遮蔽（ambientocclusion）、光子贴图、LightProbe等[1]。
当光从光源被发射出来后，碰到障碍物就反射和折射，经过无数次的反射和折射，物体表面和角落都会有光感，像真实的自然光。
全局光照占内存是很厉害的。
它属于间接照明，缩写为GI，全名为GlobalIllumination（全局光照）[1]
1986年，Ｋajiya首次将蒙特卡罗方法应用到全局光照领域，提出以建立从视点到光源的随机游动链为基础的蒙特卡罗光径跟踪算法来逐像素地生成图像。
须注意的是，蒙特卡罗光径跟踪属于蒙特卡罗全局光照方法，如目前应用广泛的PhtotonMapping算法，生成图像的基本框架。
蒙特卡罗光径跟踪的核心环节在于抽样穿过像素的光径样本，像素值即为所有光径样本光照值的均值。
光径的建立过程是：
在像素区域内随机地抽样一个以视点出发产生一条射线穿过
射进场景，计算该光线与第一个物体的交点1y，以1y为起点、根据1y所在物体表面的散射特性随机产生一个方向而形成一条射线，再求出另一个交点2y，上述过程反复进行，在任一交点处，光径均可以一定的概率而终止。
整个光径的光照值按照蒙特卡罗积分可以得到。
2007年中国天津大学徐庆老师提出了一种基于基于信息熵的蒙特卡罗全局光照的自适应抽样算法，在真实感图形生成领域里，[2]蒙特卡罗方法是计算整体光照问题的极佳选择。
但是，在用基于蒙特卡罗的全局光照算法生成的图像中，当没有足够多的采样量的时候，存在大量的噪声。
自适应抽样方法是减少这种噪声的一种很好的方法。
该文提出了一种新的基于信息熵的自适应抽样算法。
实验结果表明，该方法的效果优于香农信息熵等经典方法。
2来源
1946年，美国拉斯阿莫斯国家实验室的三位科学家JohnvonNeumann,StanUlam和NickMetropolis共同发明，被称为蒙特卡洛方法。
它的具体定义是：
在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，现在要计算这个不规则图形的面积，怎么计算呢?
蒙特卡洛（MonteCarlo）方法告诉我们，均匀的向该正方形内撒N（N是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个，那么，这个奇怪形状的面积与正方形的面积之比便近似于M/N，N越大，算出来的值便越精确。
在这里我们要假定豆子都在一个平面上，相互之间没有重叠。
蒙特卡洛方法可用于近似计算圆周率：
让计算机每次随机生成两个0到1之间的数，看这两个实数是否在单位圆内。
生成一系列随机点，统计单位圆内的点数与总点数，（圆面积和正方形面积之比为PI:
1，PI为圆周率），当随机点取得越多（但即使取10的9次方个随机点时，其结果也仅在前4位与圆周率吻合）时，其结果越接近于圆周率。
就数学特性而言,蒙特卡罗方法的发展可以追溯到18世纪著名的蒲丰问题.1777年,法国科学家蒲丰（Buffon）提出用投针试验计算圆周率π值的问题.这里我们用蒲丰问题来初步说明蒙特卡罗方法的基本原理和解决问题的基本手续.蒲丰问题是这样一个古典概率问题:
在平面上有彼此相距为2a的平行线,向此平面任意投一长度为2l的针,假定l<
a,显然,所投的针至多可与一条直线相交,那么,此针与任意条平行线相交的概率可以求出,由下面的分析可知,此概率与所取针长2l、平行线间距2a有关,并且包含有π值.在这里,任投一针的概率含义有以下三点:
（1）针的中点Ml在平行线之间等概率落入,即Ml距平行线的距离x均匀分布在区间[0,a]之内;
（2）针与线的夹角θ均匀分布在区间-π2,π2之内;
（3）x与θ互相独立.在某一条平行线上的x轴,不失一般性,假定针的中心处于图示中的x轴上.由于对称性,我们只需分析针中心处在x∈（0,a）范围的情况即可.令探针中心的坐标值为x,显然,只有x≤l时才可能发生相交的事件.我们来分析在条件x≤l满足时,针与线相交的概率:
只有当θ≤θ0=arccosxl时才能相交,且相交的概率为P1=2πarccosxl
（1）下面再来分析针中心位置在轴上的分布,显然,这是一个均匀分布,即针中心处于区间（x,x+dx）内的概率为dP2=dxa
（2）这样,一次投掷,针中心落入（x,x+dx）且与线相交的概率为dP=P1dP2=2πaarccosxldx（3）则一次投掷,针与线相交的总概率为P=∫dP=∫l0πaarccosxldx=2lπa（4）即:
π=2lPa从（5）式可见,可利用投针试验计算π值:
设投针N次,其中n次针与线相交,则可用频率值n/N作为概率P的估计值,从而求得π的估计值为π≈2laNn（6）这就是早期的用频率值作为概率近似值的方法的应用实例,表1是在历史上一些有名的用投针试验计算π值的结果[2],其中针长以a为单位。
需要指出的是,上述由投针试验求得π
的近似值的方法,是进行真正的试验,并统计试验结果,要使获得的频率值与概率值偏差小,就要进行大量的试验[3],这在实际中,往往难以做到.可以设想,对蒲丰问题这样一个简单的概率问题,若要进行10万次投针试验,以每次投针、作出是否相交判断并累加相交次数用时5秒钟计算,则需用时50万秒,即大约139个小时.那么,可以设想,对于象上述确定条件下的核裂变、直流气体放电中粒子的输运过程及粒子输运的总效应,若要用多次掷骰子的方法近似求出就是不可能的了.所以,在现代计算机技术出现之前,用频率近似概率的方法———抑或称为雏形时代的蒙卡罗方法———并没有得到实质上的应用.
若用数值模拟方法代替上述的真正的投针试验,是利用均匀分布于（0,1）之间的随机数序列,并构造出随机投针的数学模型,然后进行大量的随机统计并求得π的近似值.
3原理
蒙特卡罗方法的基本原理及思想如下：
当所要求解的问题是某种事件出现的概率，或者是某个随机变量的期望值时，它们可以通过某种“试验”的方法，得到这种事件出现的频率，或者这个随机变数的平均值，并用它们作为问题的解。
这就是蒙特卡罗方法的基本思想。
蒙特卡罗方法通过抓住事物运动的几何数量和几何特征，利用数学方法来加以模拟，即进行一种数字模拟实验。
它是以一个概率模型为基础，按照这个模型所描绘的过程，通过模拟实验的结果，作为问题的近似解。
可以把蒙特卡罗解题归结为三个主要步骤：
构造或描述概率过程；
实现从已知概率分布抽样；
建立各种估计量。
蒙特卡罗解题三个主要步骤：
构造或描述概率过程：
对于本身就具有随机性质的问题，如粒子输运问题，主要是正确描述和模拟这个概率过程，对于本来不是随机性质的确定性问题，比如计算定积分，就必须事先构造一个人为的概率过程，它的某些参量正好是所要求问题的解。
即要将不具有随机性质的问题转化为随机性质的问题。
实现从已知概率分布抽样：
构造了概率模型以后，由于各种概率模型都可以看作是由各种各样的概率分布构成的，因此产生已知概率分布的随机变量（或随机向量），就成为实现蒙特卡罗方法模拟实验的基本手段，这也是蒙特卡罗方法被称为随机抽样的原因[4]。
最简单、最基本、最重要的一个概率分布是（0,1）上的均匀分布（或称矩形分布）。
随机数就是具有这种均匀分布的随机变量。
随机数序列就是具有这种分布的总体的一个简单子样，也就是一个具有这种分布的相互独立的随机变数序列。
产生随机数的问题，就是从这个分布的抽样问题。
在计算机上，可以用物理方法产生随机数，但价格昂贵，不能重复，使用不便。
另一种方法是用数学递推公式产生。
这样产生的序列，与真正的随机数序列不同，所以称为伪随机数，或伪随机数序列。
不过，经过多种统计检验表明，它与真正的随机数，或随机数序列具有相近的性质，因此可把它作为真正的随机数来使用。
由已知分布随机抽样有各种方法，与从（0,1）上均匀分布抽样不同，这些方法都是借助于随机序列来实现的，也就是说，都是以产生随机数为前提的。
由此可见，随机数是我们实现蒙特卡罗模拟的基本工具。
建立各种估计量：
一般说来，构造了概率模型并能从中抽样后，即实现模拟实验后，我们就要确定一个随机变量，作为所要求的问题的解，我们称它为无偏估计。
建立各种估计量，相当于对模拟实验的结果进行考察和登记，从中得到问题的解。
例如：
检验产品的正品率问题，我们可以用1表示正品，0表示次品，于是对每个产品检验可以定义如下的随机变数Ti，作为正品率的估计量：
于是，在N次实验后，正品个数为：
显然，正品率p为：
不难看出，Ti为无偏估计。
当然，还可以引入其它类型的估计，如最大似然估计，渐进有偏估计等。
但是，在蒙特卡罗计算中，使用最多的是无偏估计。
用比较抽象的概率语言描述蒙特卡罗方法解题的手续如下：
构造一个概率空间（W,A,P），其中，W是一个事件集合，A是集合W的子集的s体，P是在A上建立的某个概率测度；
在这个概率空间中，选取一个随机变量q（w）,wÎ
W,使得这个随机变量的期望值正好是所要求的解Q，然后用q（w）的简单子样的算术平均值作为Q的近似值。
蒙特卡罗方法与一般计算方法有很大区别，一般计算方法对于解决多维或因素复杂的问题非常困难，而蒙特卡罗方法对于解决这方面的问题却比较简单。
其特点如下：
·
直接追踪粒子，物理思路清晰，易于理解。
采用随机抽样的方法，较真切的模拟粒子输运的过程，反映了统计涨落的规律。
不受系统多维、多因素等复杂性的限制，是解决复杂系统粒子输运问题的好方法。
MC程序结构清晰简单。
研究人员采用MC方法编写程序来解决粒子输运问题，比较容易得到自己想得到的任意中间结果，应用灵活性强。
MC方法主要弱点是收敛速度较慢和误差的概率性质，其概率误差正比于，如果单纯以增大抽样粒子个数N来减小误差，就要增加很大的计算量。
近十年来，蒙特卡罗方法发展很快，从1983年到1988年期刊论文数量增长了五倍[5]，有几本好书是关于电子¾
光子蒙特卡罗问题的[注1]，蒙特卡罗方法的代码被认为是黑匣子，它已成为计算数学中不可缺少的组成部分，这主要是因为以下原因[6]：
传统的分析方法受到了问题复杂性的限制。
MC方法直观，对实验者很有吸引力。
计算机变得更快更便宜。
量子理论的发展为我们提供了辐射与物质相互作用的截面数据。
4算法描述
它是一种以概率和统计理论方法为基础的一种计算方法。
将所求解的问题同一定的概率模型相联系，用计算机实现统计模拟或抽样，以获得问题的近似解。
比如，给定x=a，和x=b[7]，你要求某一曲线f和这两竖线，及x轴围成的面积，你可以起定y轴一横线y=c其中c>
=f（x）max，很简单的，你可以求出y=c，x=a，x=b及x轴围成的矩形面积，然后利用随机产生大量在这个矩形范围之内的点，统计出现在曲线上部点数和出现在曲线下部点的数目，记为：
dotUpCount，dotDownCount，然后所要求的面积可以近似为dotDownCount所占比例*矩形面积。
5问题描述
在数值积分法中，利用求单位圆的1/4的面积来求得Pi/4从而得到Pi。
单位圆的1/4面积是一个扇形[8]，它是边长为1单位正方形的一部分。
只要能求出扇形面积S1在正方形面积S中占的比例K=S1/S就立即能得到S1，从而得到Pi的值。
怎样求出扇形面积在正方形面积中占的比例K呢？
一个办法是在正方形中随机投入很多点，使所投的点落在正方形中每一个位置的机会相等看其中有多少个点落在扇形内[9]。
将落在扇形内的点数m与所投点的总数n的比m/n作为k的近似值。
P落在扇形内的充要条件是x^2+y^2<
=1。
6程序描述
/**//*
利用蒙特卡洛算法近似求圆周率PI[9]
VC++6.0
ZZH
*/
#include<
iostream>
cmath>
ctime>
#defineCOUNT500000//循环取样次数
usingnamespacestd;
boolInCircle（doublex,doubley）//是否在1/4圆范围之内
...{
if（（x*x+y*y）<
=1）returntrue;
returnfalse;
}
voidmain（）
doublex,y;
intnum=0;
inti;
srand（（unsigned）time（NULL））;
for（i=0;
i<
COUNT;
i++）
x=rand（）*1.0/RAND_MAX;
y=rand（）*1.0/RAND_MAX;
if（InCircle（x,y））num++;
cout<
<
"
PI:
（num*4.0）/COUNT<
endl;
结果：
测试5次的结果显示：
3.13958，3.14041，3.13729，3.13859，3.14186[1]
matlab利用蒙特卡洛算法近似求圆周率PIfunctiony=metekaro（nums）
%
蒙特卡罗算法的简单模拟，输入nums对绝对值x,y都小于1的数（x,y），通过落在圆内的点数来求pi%产生nums对坐标数据（x,y）D=unifrnd（-1,1,nums,2）;
%落在圆中的点数inCircle=0;
%获取行数,也即nums的值rows=size（D,1）;
%对每一对数据进行检测
fori=1:
rows%如果落在圆内，圆内的点数+1，落在正方形内的点数就为nums的数值if（D（i,1）^2+D（i,2）^2）<
1inCircle=inCircle+1;
end
%圆的面积/正方形的面积=圆内的点数/正方形内的点数
y=4*inCircle/rows;
%输出pi值
disp（['
pi的近似值为：
'
num2str（y）]）
计算结果：
>
metekaro（1000）;
3.088
metekaro（100000）;
3.1409
metekaro（10000000）;
3.1413
python利用蒙特卡洛算法近似求圆周率PI[11]
importrandom
importtime
random.seed（）
nums=100000
i=range（1,nums）
s=0
printnums
printtime.strftime（'
Str:
%Y-%m-%d%H:
%M:
%S'
time.localtime（time.time（）））
forxini:
a1=random.random（）
a2=random.random（）
if（a1*a1+a2*a2）<
1:
s=s+1
print1.0*s/nums*4
End:
运行结果：
3.14248
7蒙特卡罗方法的解题步骤和特点
在用蒙特卡罗方法解算问题时[12],一般需要这样几个过程:
构造或描述概率过程,对于本身就具有随机性质的问题,如粒子输运问题,主要是正确地描述和模拟这个概率过程.对于本来不是随机性质的确定性问题,比如计算定积分、解线性方程组、偏微分方程边值问题等,要用求蒙特卡罗方法求解,就必须事先构造一个人为的概率过程,它的某些参量正好是所要求问题的解.即要将不具有随机
性质的问题,转化为随机性质的问题.这构成了蒙特卡罗方法研究与应用上的重要问题之一.然后建立各种估计量,使其期望值是所要求解问题的解.最后根据所构造的概率模型编制计算程序并进行计算,获得计算结果.与其他的数值计算方法相比,蒙特卡罗方法有这样几个优点:
（1）收敛速度与问题维数无关,换句话说,要达到同一精度,用蒙特卡罗方法选取的点数与维数无关;
计算时间仅与维数成比例.但一般数值方法,比如在计算多重积分时,达到同样的误差,点数与维数的幂次成比例,即计算量要随维数的幂次方而增加.这一特性,决定了对多维问题的适用性.
（2）受问题的条件限制的影响小.
（3）程序结构简单,在电子计算机上实现蒙特卡罗计算时,程序结构清晰简单,便于编制和调试.
（4）对于模拟象粒子输运等物理问题具有其他数值计算方法不能替代的作用.蒙特卡罗方法的弱点是收敛速度慢,误差大的概率性质.
这一情况在解粒子输运问题中仍然存在.除此之外,经验证明,只有当系统的大小与粒子的平均自由程可以相比较时,一般在10个平均自由程左右,这方法算出的结果较为满意.而对于大系统深穿透问题,算出的结果往往偏低.对于大系统,其他数值方法往往很适应,能算出较好的结果.因此,已有人将数值方法与蒙特卡罗方法联合起来使用,克服这种局限性[13],取得了一定的效果.随着计算机技术的飞速发展,蒙特卡罗方法以其独特的优点广泛应用于计算及关照研究领域,对蒙特卡罗方法的推广必将使其对物理学及光学学科的发展发挥更大的作用.
8发展及我的想法
基于徐老师提出的一种新的基于信息熵的自适应抽样方法。
实验结果表明，用本文方法生成的图像在RMS的减小上有很大的提高，生成的图像的效果好于香农信息熵的和其他一些经典方法的效果。
本文方法实现简单，对复杂场景的适用性同样很强。
下一步将进一步研究更加高效的自适应抽样方法，现在蒙特卡罗算法用于光照方面的研究依然很少，我觉得在处理图像方面，尤其光照方面，我们应该继续研究，在此基础上加入具有限制条件的抽样方法。
通过此次课程学习及文献查找，我对计算机图形学有了更进一步的学习，可是自己掌握的远远不够，我应该继续深入学习，争取在这个领域有所发展。
参 考 文 献
1PohlmannKG.数字音频原理与应用[M].北京:
电子工业出版社,
2002.
2WolfW,OzerB,LvT.SmartCamerasasEmbeddedSystems[J].
Computer,2002,35（9）.
3BramM,DobA,MaierA,etal.DistributedEmbeddedSmart
CamerasforSurveillanceApplication[J].Computer,2006,39
（2）.
4TMS320C6711Datasheet[Z].（2002-08）..
5ISO/IECIS11172–3-1992CodingofMovingPicturesand
AssociatedAudioforDigitalStorageMediaatUptoAbout1.5Mbit/s
——Part3Audio[S].1992.
6李力利.基于定点DSP的MP3间频编码算法研究及实现[J].电子
技术应用,2005,31（4）.
7赵知劲.一种计算MDCT的快速算法[J].现代雷达,1997,19（5）.
8窦维蓓,刘若珩,王建昕.基于DSP的IMDCT快速算法[J].清华
大学学报,2000,40（3）.
9斯纳德.高级TCP/IP编程[M].北京:
中国电力出版社,2001.
10 裴鹿成,张孝泽.蒙特卡罗方法及其在粒子输运问题
中的应用.北京:
科学出版社,1980.
11 方再根.计算机模拟和蒙特卡罗方法论.北京:
北京工
业学院出版社,1988.
12 陈俊英.H2/CH4系统EACVD动力学过程研究.河北
大学硕士学位论文,2000.
13 张玉红.H2/C2H2系统电子助进热丝化学气相沉积动
力学过程研究.河北大学硕士学位论文,2001.
升级会员 