??? 摘 要: 提出了一種面向硬件的任意均值、方差的高斯" title="高斯">高斯隨機噪聲生成方法。改進了傳統(tǒng)的采用蒙特卡洛方法實現(xiàn)均勻分布" title="均勻分布">均勻分布噪聲到隨機分布噪聲的快速轉(zhuǎn)化,采用映射函數(shù)方法實現(xiàn)這個轉(zhuǎn)變,最大限度地降低了運算量。實驗證明本方法具有快速、高精度等優(yōu)點。
?? ?關(guān)鍵詞: 高斯隨機噪聲 實時 圖像
?
??? 高斯隨機噪聲在信號分析和處理中具有重要的價值。本文具體討論了一種面向硬件的高斯噪聲快速生成算法。算法原理為通過映射表法將均勻噪聲轉(zhuǎn)化生成高斯隨機噪聲。本方法占有內(nèi)存小、運算速度快、精度高。實驗證明該方法能夠為視頻圖像實時添加高斯噪聲。
??? 原理框圖如圖1所示。圖1左半部分為均勻噪聲生成部分,采用模數(shù)取余法,依靠已有的K個隨機數(shù)" title="隨機數(shù)">隨機數(shù)種子,不斷生成新的隨機數(shù),并將之向外輸出。圖1右半部分采用左半部分的輸出值生成映射表地址,將查表" title="查表">查表后得到的結(jié)果輸出,即為所要求的高斯噪聲值結(jié)果。
?
1 生成均勻分布噪聲
??? 設(shè)x(1),…,x(k)是給定的k個隨機數(shù),在(-X,X)內(nèi)均勻分布,相互獨立。第k+1個隨機數(shù)由x(1)和x(k)按照模X相加得到:
??? 
??? 即x(k+1)仍然是(-X,X)之間的隨機數(shù)。在下一次運算時,將x(k+1)移到x(k)的位置,x(k)移到x(k-1),……,x(2)移到x(1),然后再做模X運算,相加得到x(k+2),如此循環(huán),產(chǎn)生序列{xn}。
??? 首先討論上面的模X運算。對于采用補碼運算的處理器而言,只要取X為處理器字長,則在不考慮進位的情況下,通常的加法就是模加運算。
??? 然后采用數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上面的循環(huán)機制。設(shè)兩個指針:頭指針head和尾指針tail。每計算完一次噪聲值后,兩個指針都要向下移動一個位置。已到序列尾部,則重新指到序列的頭部,即按照加1模K運算:
??? head=(head+1)mod(K)
?? ?tail=(tail+1)mod(K)
??? 為了計算方便,選K為256。若用head和tail指針做相對偏移地址,則可以采用1個字節(jié)存儲。加1運算之后若不考慮溢出,就等價于加1模256操作。
2 映射高斯噪聲
??? 為了由均勻噪聲快速產(chǎn)生高斯噪聲,采用了映射函數(shù)法。其算法原理如圖2所示。
?
??? 將正態(tài)分布函數(shù)的自變量y進行合理的離散化,得到一系列函數(shù)值,構(gòu)成一個數(shù)列。再將此數(shù)列中的任一個數(shù)yi映射到數(shù)軸x上的某個小區(qū)間段[xi0,xi1],其中||xi1-xi0||=yi。取遍數(shù)列中所有的數(shù)值,得到一系列的小區(qū)間。將所有的小區(qū)間依次連接起來,中點置于數(shù)軸的零點,則構(gòu)成變量x的取值區(qū)間[-x,x]。將數(shù)軸x上的各個小區(qū)間與y序列建立映射關(guān)系,則可以證明,如果采樣間隔足夠小,那么x域中的隨機分布將對應(yīng)于y域中的高斯分布" title="高斯分布">高斯分布。
??? 這個映射關(guān)系可以函數(shù)表示為:y=f(x)。
??? 其中x服從(-X,X)區(qū)間內(nèi)均勻分布,而y服從均值為u、方差為σ的高斯分布。f函數(shù)曲線如圖3所示。
?
??? 在算法實現(xiàn)時,對y對應(yīng)的高斯分布值進行量化處理,并為x分配一塊連續(xù)的內(nèi)存區(qū)域[0,2X],每個內(nèi)存單元的(偏移地址-X)值代表了x值大小,單元內(nèi)容存放了該單元對應(yīng)的y值。這片內(nèi)存區(qū)域就是所需要的映射查找表。這個表具有通用性,可以預(yù)先計算好,在需要時可以直接使用,不必再計算。
??? 對于(0,1)正態(tài)分布,圖4中的zi都小于1,沒有實際意義,所以將其放大了200倍:
?
??? 則原始映射表描述為:
??? 原始映射表比較大,實際使用時對其做了粗采樣。對y對應(yīng)的高斯分布值進行的量化也沒有采用圖4中的標(biāo)準(zhǔn)階梯形式,而是采用了如下粗采樣形式:
??? 
?? ?其中:采樣間隔d=Σyj/M,量化處理曲線如圖5所示。
?
??? 從圖5可以發(fā)現(xiàn),兩邊較小處并沒有像階梯圖那樣截止為0,而是允許以小的概率出現(xiàn)非零值。試驗證明這種方式更好一些。
??? 考慮高斯分布的實際情況,并經(jīng)過試驗驗證y僅在[-4,4]之間取值,就能夠達(dá)到令人滿意的精度。圖6給出了X大小對噪聲精度的影響曲線,縱軸為平均誤差。
?
??? 可以看出,當(dāng)2X大于5500時,誤差達(dá)到了極小穩(wěn)定狀態(tài)。為了方便計算,選擇2X=213=8192,即X=212=4096。
??? 圖7給出了實驗結(jié)果(均值為120,方差為40):虛線部分為標(biāo)準(zhǔn)高斯分布的曲線,實線部分為噪聲直方圖,驗證了本方法的有效性。
?
?
3 精度討論
??? 該方法主要利用兩個表:一個是循環(huán)產(chǎn)生均勻噪聲的表;另一個是映射表。這兩個表的數(shù)值都可以由前面介紹的方法計算,下面只討論它們的精度取舍。
??? 循環(huán)表中256個種子的精度要求與映射表的大小有直接關(guān)系,對映射表采用了8192(8K)個單元。因此循環(huán)表的任務(wù)就是要在區(qū)間[-4096,4096]內(nèi)產(chǎn)生均勻分布的隨機數(shù)。所以循環(huán)表中的種子序列x(1),…,x(256)在[-4096,4096]內(nèi)均勻分布。為了方便計算,將種子序列的分布調(diào)整到[-(215-1),(215-1)]之間,即X=215=32767。所以可以采用包含1位符號位共計16位來存儲種子數(shù)的補碼?熏這樣可以通過丟掉進位的補碼加法來實現(xiàn)模X加運算。補碼運算結(jié)果的高13位或右移3位,可以直接作映射表的偏移地址進行后續(xù)查表操作,并且滿足在[-4096,4096]內(nèi)均勻分布。
??? 考慮實際情況下,待求的高斯噪聲分布的方差一般介于(0,100)之間,均值一般介于[-255,255]之間。而實際圖像灰度值是以整數(shù)[0,255]形式存在,所以噪聲的精度只要控制在整數(shù)范圍內(nèi)即可,映射表的精度只要達(dá)到0.01就足夠了。而映射表中數(shù)據(jù)的分布介于[-4.00,4.00]之間,若以整數(shù)形式存儲,將原始數(shù)據(jù)乘以128后就完全可以存放在16位長度單元中。
??? 也可以在此基礎(chǔ)上對表進行修改,使得經(jīng)過映射后高斯分布的均值和方差直接等于用戶給定的均值u和方差σ。修改比較簡單,將映射表中的每一個單元值y做如下替換:
??? y=(y*σ)>>7+u
??? 此表中數(shù)據(jù)可以是原碼形式也可以是補碼形式,依具體需要而定。
參考文獻(xiàn)
1 尹 力,馬忠梅.一種快速產(chǎn)生數(shù)字式高精度高斯噪聲的新方法. 應(yīng)用聲學(xué),1996:15(3):23～25
2 方再根.計算機模擬和蒙特卡洛方法.北京?押北京工業(yè)學(xué)院出版社,1988
3 Istvan Manno.Introduction to the Monte-Carlo Method. Akademiai Kiado.1999:(10)