數據平滑處理演算法

1. 如何進行圖像進行直方圖平滑處理，請描述具體的演算法過程

width=dlg.m_width;
delta=dlg.m_delta;

sqdelta=delta*delta;
for(i=0;i<256;i++)
{
coef=1.0;
for(j=1;j<width;j++)
{
weight=(float)exp(-0.5*j*j*sqdelta);
if((i+j)<256)
{
coef+=weight;
m_Dib.probability[i]+=(prob[i+j]*weight);
}
if((i-j)>=0)
{
coef+=weight;
m_Dib.probability[i]+=(prob[i-j]*weight);
}
}
m_Dib.probability[i]/=coef;
}
sum=0;
for(i=0;i<256;i++)
sum+=m_Dib.probability[i];
for(i=0;i<256;i++)
m_Dib.probability[i]=(float)(m_Dib.probability[i]/sum);

2. 簡單理解 n-gram

N-Gram（有時也稱為N元模型）是自然語言處理中一個非常重要的概念，通常在NLP中，人們基於一定的語料庫，可以利用N-Gram來預計或者評估一個句子是否合理。另外一方面，N-Gram的另外一個作用是用來評估兩個字元串之間的差異程度。這是模糊匹配中常用的一種手段。本文將從此開始，進而向讀者展示N-Gram在自然語言處理中的各種powerful的應用。

基於N-Gram模型定義的字元串距離

模糊匹配的關鍵在於如何衡量兩個長得很像的單詞（或字元串）之間的「差異」。這種差異通常又稱為「距離」。這方面的具體演算法有很多，例如基於編輯距離的概念，人們設計出了 Smith-Waterman 演算法和Needleman-Wunsch 演算法，其中後者還是歷史上最早的應用動態規劃思想設計的演算法之一。現在Smith-Waterman 演算法和Needleman-Wunsch 演算法在生物信息學領域也有重要應用，研究人員常常用它們來計算兩個DNA序列片段之間的「差異」（或稱「距離」）。

我們除了可以定義兩個字元串之間的編輯距離（通常利用Needleman-Wunsch演算法或Smith-Waterman演算法）之外，還可以定義它們之間的N-Gram距離。N-Gram（有時也稱為N元模型）是自然語言處理中一個非常重要的概念。假設有一個字元串 ，那麼該字元串的N-Gram就表示按長度 N 切分原詞得到的詞段，也就是 中所有長度為 N 的子字元串。設想如果有兩個字元串，然後分別求它們的N-Gram，那麼就可以從它們的共有子串的數量這個角度去定義兩個字元串間的N-Gram距離。但是僅僅是簡單地對共有子串進行計數顯然也存在不足，這種方案顯然忽略了兩個字元串長度差異可能導致的問題。比如字元串 girl 和 girlfriend，二者所擁有的公共子串數量顯然與 girl 和其自身所擁有的公共子串數量相等，但是我們並不能據此認為 girl 和girlfriend 是兩個等同的匹配。

為了解決該問題，有學者便提出以非重復的N-Gram分詞為基礎來定義 N-Gram距離這一概念，可以用下面的公式來表述：

此處，|GN(s)| 是字元串 s 的 N-Gram集合，N 值一般取2或者3。以 N = 2 為例對字元串Gorbachev和Gorbechyov進行分段，可得如下結果（我們用下畫線標出了其中的公共子串）。

結合上面的公式，即可算得兩個字元串之間的距離是8 + 9 − 2 × 4 = 9。顯然，字元串之間的距離越小，它們就越接近。當兩個字元串完全相等的時候，它們之間的距離就是0。

利用N-Gram模型評估語句是否合理

從現在開始，我們所討論的N-Gram模型跟前面講過N-Gram模型從外在來看已經大不相同，但是請注意它們內在的聯系（或者說本質上它們仍然是統一的概念）。

為了引入N-Gram的這個應用，我們從幾個例子開始。
首先，從統計的角度來看，自然語言中的一個句子 s 可以由任何詞串構成，不過概率 P(s) 有大有小。例如：

顯然，對於中文而言 s1 是一個通順而有意義的句子，而s2 則不是，所以對於中文來說，P(s1)>P(s2) 。但不同語言來說，這兩個概率值的大小可能會反轉。

其次，另外一個例子是，如果我們給出了某個句子的一個節選，我們其實可以能夠猜測後續的詞應該是什麼，例如

the large green __ . Possible answer may be 「mountain」 or 「tree」 ?
Kate swallowed the large green __ . Possible answer may be 「pill」 or 「broccoli」 ?
顯然，如果我們知道這個句子片段更多前面的內容的情況下，我們會得到一個更加准確的答案。這就告訴我們，前面的（歷史）信息越多，對後面未知信息的約束就越強。

如果我們有一個由 m 個片語成的序列（或者說一個句子），我們希望算得概率 P(w1,w2,⋯,wm) ，根據鏈式規則，可得
P(w1,w2,⋯,wm)=P(w1)P(w2|w1)P(w3|w1,w2)⋯P(wm|w1,⋯,wm−1)

這個概率顯然並不好算，不妨利用馬爾科夫鏈的假設，即當前這個詞僅僅跟前面幾個有限的詞相關，因此也就不必追溯到最開始的那個詞，這樣便可以大幅縮減上訴算式的長度。即
P(wi|w1,⋯,wi−1)=P(wi|wi−n+1,⋯,wi−1)

特別地，對於 n 取得較小值的情況
當 n=1, 一個一元模型（unigram model)即為

當 n=2, 一個二元模型（bigram model)即為

當 n=3, 一個三元模型（trigram model)即為

接下來的思路就比較明確了，可以利用最大似然法來求出一組參數，使得訓練樣本的概率取得最大值。

使用N-Gram模型時的數據平滑演算法

有研究人員用150萬詞的訓練語料來訓練 trigram 模型，然後用同樣來源的測試語料來做驗證，結果發現23%的 trigram 沒有在訓練語料中出現過。這其實就意味著上一節我們所計算的那些概率有空為 0，這就導致了數據稀疏的可能性，我們的表3中也確實有些為0的情況。對語言而言，由於數據稀疏的存在，極大似然法不是一種很好的參數估計辦法。

這時的解決辦法，我們稱之為「平滑技術」（Smoothing）或者 「減值」 （Discounting）。其主要策略是把在訓練樣本中出現過的事件的概率適當減小，然後把減小得到的概率密度分配給訓練語料中沒有出現過的事件。實際中平滑演算法有很多種，例如：
▸ Laplacian (add-one) smoothing
▸ Add-k smoothing
▸ Jelinek-Mercer interpolation
▸ Katz backoff
▸ Absolute discounting
▸ Kneser-Ney

對於這些演算法的詳細介紹，我們將在後續的文章中結合一些實例再來進行討論。

搜索引擎（Google或者Bai）、或者輸入法的猜想或者提示。你在用網路時，輸入一個或幾個詞，搜索框通常會以下拉菜單的形式給出幾個像下圖一樣的備選，這些備選其實是在猜想你想要搜索的那個詞串。再者，當你用輸入法輸入一個漢字的時候，輸入法通常可以聯系出一個完整的詞，例如我輸入一個「劉」字，通常輸入法會提示我是否要輸入的是「劉備」。通過上面的介紹，你應該能夠很敏銳的發覺，這其實是以N-Gram模型為基礎來實現的，如果你能有這種覺悟或者想法，那我不得不恭喜你，都學會搶答了！

參考： https://blog.csdn.net/mafujinji/article/details/51281816

3. 平滑濾波的3×3演算法原理

平滑濾波
低頻增強的空間域濾波技術
平滑濾波是低頻增強的空間域濾波技術。它的目的有兩類：一類是模糊；另一類是消除噪音。空間域的平滑濾波一般採用簡單平均法進行，就是求鄰近像元點的平均亮度值。鄰域的大小與平滑的效果直接相關，鄰域越大平滑的效果越好，但鄰域過大，平滑會使邊緣信息損失的越大，從而使輸出的圖像變得模糊，因此需合理選擇鄰域的大小。
中文名
平滑濾波
外文名
Smoothing
拼音
píng huá lǜ bō
注音
ㄆㄧㄥˊ ㄏㄨㄚˊㄌㄩˋ ㄅㄛ
濾波目的處理要求濾波原因濾波方法其他方式TA說
濾波目的
濾波的本義是指信號有各種頻率的成分,濾掉不想要的成分,即為濾掉常說的雜訊,留下想要的成分.這即是濾波的過程,也是目的.
一是抽出對象的特徵作為圖像識別的特徵模式；另一個是為適應圖像處理的要求，消除圖像數字化時所混入的雜訊。
處理要求
一是不能損壞圖像的輪廓及邊緣等重要信息；二是使圖像清晰視覺效果好。
濾波原因
各類圖像處理系統在圖像的採集、獲取、傳送和轉換(如成像、復制掃描、傳輸以及顯示等)過程中，均處在復雜的環境中，光照、電磁多變，所有的圖像均不同程度地被可見或不可見的雜訊干擾。雜訊源包括電子雜訊、光子雜訊、斑點雜訊和量化雜訊。如果信噪比低於一定的水平，雜訊逐漸變成可見的顆粒形狀，導致圖像質量的下降。除了視覺上質量下降，雜訊同樣可能掩蓋重要的圖像細節，在對採集到的原始圖像做進一步的分割處理時，我們發現有一些分布不規律的椒鹽雜訊，為此採取相應的對策就是對圖像進行必要的濾波降噪處理。
濾波方法
圖像的雜訊濾波器有很多種，常用的有線性濾波器，非線性濾波器。採用線性濾波如鄰域平滑濾波，對受到雜訊污染而退化的圖像復原，在很多情況下是有效的。但大多數線性濾波器具有低通特性，去除雜訊的同時也使圖像的邊緣變模糊了。而另一種非線性濾波器如中值濾波，在一定程度上可以克服線性濾波器所帶來的圖像模糊問題，在濾除雜訊的同時，較好地保留了圖像的邊緣信息。
鄰域平滑濾波原理
鄰域平均法[2]是一種利用Box模版對圖像進行模版操作（卷積運算）的圖像平滑方法，所謂Box模版是指模版中所有系數都取相同值的模版，常用的3×3和5×5模版如下：
鄰域平均法的數學含義是：
（式4-1）
式中：x,y=0,1,…,N-1;S是以（x,y）為中心的鄰域的集合，M是S內的點數。
鄰域平均法的思想是通過一點和鄰域內像素點求平均來去除突變的像素點，從而濾掉一定雜訊，其優點是演算法簡單，計算速度快，其代價會造成圖像在一定程度上的模糊。
中值濾波原理
中值濾波[2]就是用一個奇數點的移動窗口，將窗口的中心點的值用窗口內的各點中值代替。假設窗口內有五點，其值為80、90、200、110和120，那麼此窗口內各點的中值及為110。
設有一個一維序列f1,f2,…,fn,取窗口長度（點數）為m（m為奇數）,對其進行中值濾波，就是從輸入序列中相繼抽出m個數fi-v,…,fi-1,fi,fi+1,…,fi+v(其中fi為窗口中心值,v=(m-1)/2),再將這m個點按其數值大小順序排序，取其序號的中心點的那個數作為濾波輸出。數學公式表示為：
Yi=Med{fi-v,…,fi-1,fi,fi+1,…,fi+v} i∈N v=(m-1)/2 （式4-2）
Yi稱為序列fi-v,…,fi-1,fi,fi+1,…,fi+v的中值
例如，有一序列{0，3，4，0，7}，重新排序後為{0，0，3，4，7}則Med{0，0，3，4，7}=3。此列若用平滑濾波，窗口也取5，那麼平滑濾波輸出為（0+3+4+0+7）/5=2.8。
把一個點的特定長度或形狀的鄰域稱作窗口。在一維情況下，中值濾波器是一個含有奇數個像素的滑動窗口。中值濾波很容易推廣到二維，此時可以利用二維形式的窗口。
對於平面圖像採用的二維中值濾波可以由下式表示：
（式4-3）
式中：A為窗口，{fij}為二維數據序列,即數字圖像各點的灰度值。
對於本系統，由於採集到的是24位真彩色圖像，每個像素點分別有R、G、B三個灰度分量，故要在窗口內分別找到這三個分量的中值，分別用這三個中值去代替窗口中心像素點的R、G、B三個灰度分量的值。

4. 圖像平滑處理的原理

這個可以使用均值濾波處理，它也叫圖像的平滑。均值濾波是典型的線性濾波演算法，它是指在圖像上對目標像素給一個模板，該模板包括了其周圍的臨近像素（以目標象素為中心的周圍8個象素，構成一個濾波模板，即去掉目標象素本身）。再用模板中的全體像素的平均值來代替原來像素值。

5. 線平滑的演算法實現都有哪些

線平滑的演算法實現都有二次指數平滑法求預測值，最小二乘法曲線擬合，5點3次平滑曲線，線平滑的演算法屬於數字幾何處理領域的問題，計算機圖形學和計算機輔助設計中，用多邊形網格可以表示復雜的三維實體。

線平滑的演算法中為了方便於在O(1)的時間內獲取點P的相鄰點與相鄰面，故需要提供輔助結構來存儲這些鄰接點面的信息。故用上面那個簡單的Mesh定義就不行了，應該將Mesh數據結構按如下方式定義，增加點鄰接信息的存儲，為實現這些，定義了PointAttachmentInfo結構和新的Mesh類。

還有一種實現的是拉普拉斯平滑，在前面的博客中，介紹了最為基礎的拉普拉斯平滑演算法的實現，簡單的拉普拉斯平滑演算法的原理是將每個頂點都移動到相鄰頂點的平均位置，即採用所謂傘狀運算元。

其具體的實現邏輯表述如下：初始化Mesh的鄰接點結構集，新建臨時點集，用來存儲點平滑後的位置，對所有Mesh中的頂點P，初始化臨時向量為零向量。

獲取P的鄰域點集Adj(P)，對所有領域點T，將其位置加到臨時向量里，臨時向量/=領域點集數，將臨時向量的位置存入臨時點集，對所有Mesh中的頂點P，將P的位置修改為臨時點集中對應點的位置。

6. 平滑移動演算法或函數

三角函數。朝由原點向(x1,y1)移動，每移動一段距離s,在x和y軸上的投影距離分別x1*s/sqrt(x1*x1+y1*y1)，y1*s/sqrt(x1*x1+y1*y1)