使用蒙特卡洛方法求解不規(guī)則圖形的面積

周緒達(dá)

（重慶市朝陽(yáng)中學(xué)，重慶 400700）

1 引言

蒙特卡洛方法是一種以統(tǒng)計(jì)抽樣理論為基礎(chǔ)，以計(jì)算機(jī)為手段，通過(guò)有關(guān)隨機(jī)變量的統(tǒng)計(jì)抽樣檢驗(yàn)或隨機(jī)模擬，從而估計(jì)和描述函數(shù)的統(tǒng)計(jì)量、求解問(wèn)題近似解的一種數(shù)值計(jì)算方法[1]。該方法既可以解決隨機(jī)性問(wèn)題，又可以解決確定性問(wèn)題，其處理實(shí)際問(wèn)題的基本步驟是：構(gòu)造概型，定義隨機(jī)變量，通過(guò)模擬獲得子樣，統(tǒng)計(jì)計(jì)算。由于蒙特卡洛模擬方法具有程序結(jié)構(gòu)簡(jiǎn)單、模擬過(guò)程靈活、不受問(wèn)題條件限制、適于求解多維問(wèn)題等優(yōu)點(diǎn)，因而被廣泛應(yīng)用。本文使用Python語(yǔ)言實(shí)現(xiàn)了一種基于蒙特卡洛方法的求取不規(guī)則圖形的算法。

2 算法描述

在圖1所示的不規(guī)則圖形中，其面積無(wú)法使用常規(guī)的幾何圖形面積計(jì)算公式進(jìn)行計(jì)算。但是仔細(xì)觀察圖形可以發(fā)現(xiàn)，該不規(guī)則圖形有較為明顯的邊界，且圖形內(nèi)部的顏色與外部顏色有著較大的差異，這兩種因素使得圖形內(nèi)部與外部有明顯界限，這是使用蒙特卡洛方法計(jì)算不規(guī)則圖形面積的前提。當(dāng)圖像不符合以上前提時(shí)，需要使用圖像處理工具對(duì)其進(jìn)行處理，使得圖像中的不規(guī)則圖形具有較為明顯的邊緣，并且圖形內(nèi)部與圖像其他部分具有對(duì)比度較為強(qiáng)烈的顏色。

圖1 不規(guī)則圖形示例

蒙特卡洛方法計(jì)算圖形面積是基于以下原理：當(dāng)向整幅圖像中撒入一些隨機(jī)點(diǎn)時(shí)，一部分點(diǎn)會(huì)落入圖形內(nèi)部，另外一部分點(diǎn)則落入圖形之外。當(dāng)撒入點(diǎn)符合均勻隨機(jī)分布時(shí)，落入不規(guī)則圖形內(nèi)部的點(diǎn)的數(shù)量，與不規(guī)則圖形所占據(jù)的整幅圖像大小的比例成正比。

假設(shè)撒入的點(diǎn)數(shù)總數(shù)量為count（圖1中三角形表示），落入待求取面積圖形內(nèi)部的點(diǎn)（圖1中紅色三角形）的數(shù)量為in_count，則圖中不規(guī)則圖形的面積可由公式(1)近似求得。

在式(1)中，s表示待求取不規(guī)則圖形的面積，sfull表示整幅圖像的面積。由于整幅圖像的形狀往往是規(guī)則圖形（多為矩形），因此sfull較容易求取。

隨著隨機(jī)點(diǎn)數(shù)量count的增加，所求取的不規(guī)則圖形的面積將會(huì)逐漸逼近真實(shí)的圖形面積，如圖2所示。

圖2 撒入100萬(wàn)隨機(jī)點(diǎn)圖像

以上就是使用蒙特卡洛方法求取不規(guī)則圖形面積的基本原理。本文使用Python語(yǔ)言實(shí)現(xiàn)以上算法流程，所用到的第三方庫(kù)包括圖像處理庫(kù)PIL，數(shù)據(jù)處理庫(kù)Numpy，以及可視化庫(kù)Matplotlib[2]。

算法的主要流程如下所示：

①讀取圖像文件像素點(diǎn)的顏色到矩陣pixel中，矩陣的行數(shù)與列數(shù)分別對(duì)應(yīng)圖像的寬度w和高度h。

②使用均勻隨機(jī)數(shù)發(fā)生器生成數(shù)量的隨機(jī)點(diǎn)，點(diǎn)的橫坐標(biāo)和縱坐標(biāo)范圍分別為[0,w)和[0,h)。

③循環(huán)次，統(tǒng)計(jì)所有隨機(jī)點(diǎn)中落在不規(guī)則圖形內(nèi)部的隨機(jī)點(diǎn)的數(shù)量。隨機(jī)點(diǎn)是否在不規(guī)則圖形內(nèi)部，是通過(guò)其對(duì)應(yīng)的RGB顏色值進(jìn)行判斷得到的。

④通過(guò)式(1)計(jì)算不規(guī)則圖形的面積。

3 實(shí)驗(yàn)

選取兩幅形狀不規(guī)則的圖形如圖3和圖4所示。

圖3 不規(guī)則圖形1

圖4 不規(guī)則圖形2

實(shí)驗(yàn)參數(shù)如表1所示：

在表1中，圖形的實(shí)際面積是通過(guò)圖像中不規(guī)則圖形所占的像素點(diǎn)數(shù)計(jì)算出來(lái)的，其意義是為了方便與本文所實(shí)現(xiàn)的基于蒙特卡洛方法求取的不規(guī)則圖形的面積進(jìn)行對(duì)比。

圖5和圖6分別顯示了采樣點(diǎn)數(shù)在10～10000范圍內(nèi)變化時(shí)，使用蒙特卡洛方法求取的近似圖形面積（以像素點(diǎn)數(shù)表示）。

表1 實(shí)驗(yàn)參數(shù)

圖5 不同采樣數(shù)下圖形1的近似面積

圖6 不同采樣數(shù)下圖形2的近似面積

從圖5和圖6中可見(jiàn)，隨著采樣點(diǎn)數(shù)的增加，使用蒙特卡洛方法求取的不規(guī)則圖形面積的近似值逐漸逼近其實(shí)際值，在應(yīng)用時(shí)，可根據(jù)實(shí)際問(wèn)題的精度要求和圖像大小選取合適的采樣點(diǎn)數(shù)。

4 結(jié)論

基于蒙特卡洛方法，我們描述并實(shí)現(xiàn)了一種求取不規(guī)則圖形的方法，并通過(guò)實(shí)驗(yàn)驗(yàn)證了該方法的有效性。實(shí)驗(yàn)表明，蒙特卡洛方法能夠很好地求得不規(guī)則圖形面積的近似值。