论文部分内容阅读
【摘 要】蒙特卡洛方法是一种以计算机为工具,通过抽样统计作为手段的一种解决问题的方法,在许多领域都有广泛应用。论文基于蒙特卡洛方法,利用Python编程语言实现了对不规则图形面积的近似求解算法,并通过两组实验证明了所实现算法的有效性。
【关键词】蒙特卡洛方法;不规则图形; 面积
【Keywords】 Monte Carlo method; irregular figure; area
【中图分类号】TP18 【文献标志码】A 【文章编号】1673-1069(2019)01-0147-02
1 引言
蒙特卡洛方法是一种以统计抽样理论为基础,以计算机为手段,通过有关随机变量的统计抽样检验或随机模拟,从而估计和描述函数的统计量、求解问题近似解的一种数值计算方法[1]。该方法既可以解决随机性问题,又可以解决确定性问题,其处理实际问题的基本步骤是:构造概型,定义随机变量,通过模拟获得子样,统计计算。由于蒙特卡洛模拟方法具有程序结构简单、模拟过程灵活、不受问题条件限制、适于求解多维问题等优点,因而被广泛应用。本文使用Python语言实现了一种基于蒙特卡洛方法的求取不规则图形的算法。
2 算法描述
在图1所示的不规则图形中,其面积无法使用常规的几何图形面积计算公式进行计算。但是仔细观察图形可以发现,该不规则图形有较为明显的边界,且图形内部的颜色与外部颜色有着较大的差异,这两种因素使得图形内部与外部有明显界限,这是使用蒙特卡洛方法计算不规则图形面积的前提。当图像不符合以上前提时,需要使用图像处理工具对其进行处理,使得图像中的不规则图形具有较为明显的边缘,并且图形内部与图像其他部分具有对比度较为强烈的颜色。
蒙特卡洛方法计算图形面积是基于以下原理:当向整幅图像中撒入一些随机点时,一部分点会落入图形内部,另外一部分点则落入图形之外。当撒入点符合均匀随机分布时,落入不规则图形内部的点的数量,与不规则图形所占据的整幅图像大小的比例成正比。
假设撒入的点数总数量为count(图1中三角形表示),落入待求取面积图形内部的点(图1中红色三角形)的数量为in_count,则图中不规则图形的面积可由公式(1)近似求得。
s=sfull·(1)
在式(1)中,s表示待求取不规则图形的面积,sfull表示整幅图像的面积。由于整幅图像的形状往往是规则图形(多为矩形),因此sfull较容易求取。
随着随机点数量count的增加,所求取的不规则图形的面积将会逐渐逼近真实的图形面积,如图2所示。
以上就是使用蒙特卡洛方法求取不规则图形面积的基本原理。本文使用Python语言实现以上算法流程,所用到的第三方库包括图像处理库PIL,数据处理库Numpy,以及可视化库Matplotlib[2]。
算法的主要流程如下所示:
①读取图像文件像素点的颜色到矩阵pixel中,矩阵的行数与列数分别对应图像的宽度w和高度h。
② 使用均匀随机数发生器生成数量的随机点,点的横坐标和纵坐标范围分别为[0, w)和[0, h)。
③循环次,统计所有随机点中落在不规则图形内部的随机点的数量。随机点是否在不规则图形内部,是通过其对应的RGB颜色值进行判断得到的。
④通过式(1)计算不规则图形的面积。
3 实验
实验参数如表1所示:
在表1中,图形的实际面积是通过图像中不规则图形所占的像素点数计算出来的,其意义是为了方便与本文所实现的基于蒙特卡洛方法求取的不规则图形的面积进行对比。
从图5和图6中可见,随着采样点数的增加,使用蒙特卡洛方法求取的不规则图形面积的近似值逐渐逼近其实际值,在应用时,可根据实际问题的精度要求和图像大小选取合适的采样点数。
4 结论
基于蒙特卡洛方法,我们描述并实现了一种求取不规则图形的方法,并通过实验验证了该方法的有效性。实验表明,蒙特卡洛方法能够很好地求得不规则图形面积的近似值。
【参考文献】
【1】康崇禄. 蒙特卡洛方法理论和应用[M]. 北京:科学出版社,2015.
【2】Plas J. V. Python数据科学手册[M]. 陶俊杰, 陳小莉译.北京:人民邮电出版社,2018.
【关键词】蒙特卡洛方法;不规则图形; 面积
【Keywords】 Monte Carlo method; irregular figure; area
【中图分类号】TP18 【文献标志码】A 【文章编号】1673-1069(2019)01-0147-02
1 引言
蒙特卡洛方法是一种以统计抽样理论为基础,以计算机为手段,通过有关随机变量的统计抽样检验或随机模拟,从而估计和描述函数的统计量、求解问题近似解的一种数值计算方法[1]。该方法既可以解决随机性问题,又可以解决确定性问题,其处理实际问题的基本步骤是:构造概型,定义随机变量,通过模拟获得子样,统计计算。由于蒙特卡洛模拟方法具有程序结构简单、模拟过程灵活、不受问题条件限制、适于求解多维问题等优点,因而被广泛应用。本文使用Python语言实现了一种基于蒙特卡洛方法的求取不规则图形的算法。
2 算法描述
在图1所示的不规则图形中,其面积无法使用常规的几何图形面积计算公式进行计算。但是仔细观察图形可以发现,该不规则图形有较为明显的边界,且图形内部的颜色与外部颜色有着较大的差异,这两种因素使得图形内部与外部有明显界限,这是使用蒙特卡洛方法计算不规则图形面积的前提。当图像不符合以上前提时,需要使用图像处理工具对其进行处理,使得图像中的不规则图形具有较为明显的边缘,并且图形内部与图像其他部分具有对比度较为强烈的颜色。
蒙特卡洛方法计算图形面积是基于以下原理:当向整幅图像中撒入一些随机点时,一部分点会落入图形内部,另外一部分点则落入图形之外。当撒入点符合均匀随机分布时,落入不规则图形内部的点的数量,与不规则图形所占据的整幅图像大小的比例成正比。
假设撒入的点数总数量为count(图1中三角形表示),落入待求取面积图形内部的点(图1中红色三角形)的数量为in_count,则图中不规则图形的面积可由公式(1)近似求得。
s=sfull·(1)
在式(1)中,s表示待求取不规则图形的面积,sfull表示整幅图像的面积。由于整幅图像的形状往往是规则图形(多为矩形),因此sfull较容易求取。
随着随机点数量count的增加,所求取的不规则图形的面积将会逐渐逼近真实的图形面积,如图2所示。
以上就是使用蒙特卡洛方法求取不规则图形面积的基本原理。本文使用Python语言实现以上算法流程,所用到的第三方库包括图像处理库PIL,数据处理库Numpy,以及可视化库Matplotlib[2]。
算法的主要流程如下所示:
①读取图像文件像素点的颜色到矩阵pixel中,矩阵的行数与列数分别对应图像的宽度w和高度h。
② 使用均匀随机数发生器生成数量的随机点,点的横坐标和纵坐标范围分别为[0, w)和[0, h)。
③循环次,统计所有随机点中落在不规则图形内部的随机点的数量。随机点是否在不规则图形内部,是通过其对应的RGB颜色值进行判断得到的。
④通过式(1)计算不规则图形的面积。
3 实验
实验参数如表1所示:
在表1中,图形的实际面积是通过图像中不规则图形所占的像素点数计算出来的,其意义是为了方便与本文所实现的基于蒙特卡洛方法求取的不规则图形的面积进行对比。
从图5和图6中可见,随着采样点数的增加,使用蒙特卡洛方法求取的不规则图形面积的近似值逐渐逼近其实际值,在应用时,可根据实际问题的精度要求和图像大小选取合适的采样点数。
4 结论
基于蒙特卡洛方法,我们描述并实现了一种求取不规则图形的方法,并通过实验验证了该方法的有效性。实验表明,蒙特卡洛方法能够很好地求得不规则图形面积的近似值。
【参考文献】
【1】康崇禄. 蒙特卡洛方法理论和应用[M]. 北京:科学出版社,2015.
【2】Plas J. V. Python数据科学手册[M]. 陶俊杰, 陳小莉译.北京:人民邮电出版社,2018.