【機器視覺】6. 圖像處理的基礎知識

05-25

【機器視覺】6. 圖像處理的基礎知識

來自專欄 Let Machine See

圖像的基本處理

機器視覺中需要用些許多數字圖像處理方面的演算法，本文對圖像處理方面的一些基礎知識進行補充。

圖像直方圖與像素距離

感測器獲取的圖像是平面上的連續函數，將連續函數採樣(sampled)為M行N列的矩陣，將每個連續樣本量化(quantization)為一個整數值，即圖像函數的連續範圍被分成了K個區間，採樣後得到的矩陣構成了離散圖像，柵格中無限小的採樣點對應於數字圖像中的像元，即像素(pixel) 。

灰度圖像中，最低值對應黑，最高值對應白；黑白之間的亮度值是灰度階(gray-level) ，彩色圖像則通過矢量函數（三階張量）描述，可以將一幅彩色圖像看做由R,G,B三種基礎色進行堆疊形成，而這三種基礎色又對應了三個大小相同的矩陣，矩陣的數值表徵這一通道顏色的深淺。有時除了考慮RGB三種顏色外，還考慮像素的透明度a，稱為RGBA描述。

色彩在人類視覺感知中極其重要，色彩與物體反射不同波長的電磁波的能力相關，一般將這三種顏色（三種不同波長的光）作為三原色：紅(700nm)、綠(546.1nm)、藍(438.5nm)，灰度圖像的矩陣元素數值與彩色圖像間滿足Y=0.299R+0.587G+0.114B；RGB數字圖像中，以(0,0,0)表示黑色，(255,255,255)表示白色；灰度圖像中，以0表示黑色，以255表示白色；二值圖像中，以0表示黑色，1表示白色。

圖像每個位置[i,j]必定對應一個[0,255]的數值，統計每個數值所對應的像素點個數可以得到圖像的亮度直方圖，直方圖（亮度直方圖，brightness histogram）給出了圖像中各個亮度值出現的概率，一幅k階圖像的直方圖由具有k個元素的一維數組表示。

Def.(灰度級變換) 灰度級變換是這樣一種（線性）變換，它將原來在範圍[p0,pk]內的亮度p變換為一個新範圍[q0,qk]內的亮度。

直方圖均衡化（histogram equlization）的目標是創建一幅在整個亮度範圍內具有相同亮度分布的圖像，輸入直方圖H[p]，輸入亮度範圍為[p0,pk]，直方圖均衡化的目標是找到一個單調的像素亮度變換q=T(p)，使輸出直方圖G[q]在整個輸出亮度範圍[q0,qk]內是均勻的；增強了靠近直方圖極大值附近的亮度的對比度，減小了極小值附近的對比度。在對圖像做進一步處理之前，直方圖均衡化通常是對圖像灰度值進行歸一化的一個非常好的方法，並且可以增強圖像的對比度，原先圖像灰色區域的細節變得清晰。

直方圖均衡化的步驟如下：

1. 對於k(256)個亮度級、大小為M × N的圖像，創建長為k的數組H，初始化為0

2. 形成圖像直方圖H

3. 形成累計直方圖Hc，Hc[p]=Hc[p-1]+H[p], Hc[0]=H[0]

4. 設置 $T(p)= ext{int} frac{(k-1)Hc[p]}{MN}$

5. 重新掃描圖像，根據查找表獲得變換結果

（更加詳細的解釋參考：說說直方圖均衡化）

坐標為(m,n)和(h,k)兩點之間的距離有如下定義

- [歐氏距離（Euclid distance）] $d_e=sqrt{(m-h)^2+(n-k)^2 }$
- [城區距離（曼哈頓距離，Manhattan distance）] d_4=|m-h|+|n-k|
- [棋盤距離（chess distance）] 因相當於國際象棋中王走一步能到達的位置而得名： d_8=max ?(|m-h|,|n-k|)

Def.[像素鄰接性(adjacency)]
4－鄰接：任意兩像素之間的距離為D4＝1
8－鄰接：任意兩像素之間的距離為D8＝1

Def.[區域（region）] 由一些彼此鄰接的像素組成的集合
Def.[連通性（continuous）] 一幅圖像的兩個像素之間存在一條路徑；連通關係具有自反性、對稱性和傳遞性；區域中沒有孔，稱為簡單連通，有孔的區域稱為復連通

距離變換（distance transform）給出圖像中的每個像素與某個圖像子集的距離，步驟如下：

1. 創建大小為M 乘 N的矩陣F，子集S初始化為0，其他位置初始化為INF

2. 按行遍歷圖像，從上到下，從左到右，對上方和左側鄰接像素（AL集合）計算 $F(p)=min_{q in AL}? [F(p),D(p,q)+F(q)]$

3. 按行遍歷圖像，從下到上，從右到左，對下方和右側鄰接像素（BR集合）計算 $F(p)=min_{q in BR}? [F(p),D(p,q)+F(q)]$

4. 返回數組F的結果

圖像閾值化與二值圖像的處理

Def.[圖像二值化（閾值化）] 設輸入圖像為f，輸出為g，則
$$g(m,n)=
egin{cases}
1 & f(m,n)>t 0 & f(m,n) ge t
end{cases}
$$
其中t稱為閾值（thresh）。一種最優閾值選擇演算法的偽代碼如下

另一種選擇方法，Otsu方法，選擇使得類間方差最大的值作為閾值，設圖像的歸一化直方圖為p，亮度階為k（例如元素值取0~255，則k=256），則設

$s_0=sum_{i=0}^{t-1} p_i ,s_t=sum_{i=t}^{k-1} p_i ,s=sum_{i=0}^{k-1} p_i =1$

令期望 $mu_0=sum_{i=0}^{t-1} i frac{p_i}{s_0},mu_t=sum_{i=t}^{k-1} i frac{p_i}{s_t},mu=sum_{i=0}^{t-1} i frac{p_i}{s}=sum_{i=0}^{t-1}ip_i$

則類間方差 $sigma_b^2=s_0 (mu_0-mu)^2+s_t (mu_t-mu)^2$

數學形態學（morphology）又稱圖像代數（image algebra），是以形態為基礎對二值圖像進行分析的數學工具，基本思想是用具有一定形態的結構元素去度量和提取圖像中的對應形狀，以達到圖像分析和識別的目的。

Def.[膨脹（dilation）] 將結構元素B的原點移至集合A的某一點，將結構元素B中的點與該點取「或」（只要兩者中有一個值為1，結果就為1），得到對集合中該點的膨脹結果，對集合A中所有元素重複該過程，用$A oplus B$表示。如圖所示。

Def.[腐蝕（erosion）] 將結構元素B的原點移至集合A的某一點，對兩者進行「與」運算，用$A ominus B$表示。如圖所示。

以下對比了膨脹和腐蝕操作的結果：

Def.[開運算（opening）] 開運算（opening）是指先腐蝕再膨脹的過程。開運算是結構元素B在集合A內完全匹配的並集，完全刪除了不能包含結構元素的對象區域。開運算使圖像的輪廓變得光滑，斷開狹窄的間斷，去掉細小的突出物。
Def.[閉運算（closing）] 閉運算（closing）是先膨脹再腐蝕的過程。結構元素B在集合A外側平移，這些平移的並集就是閉運算的結果。閉運算使圖像的輪廓變得光滑，但與開運算不同的是，它會將狹窄的缺口連接形成細長的彎口，並填充比結構元素小的洞。
Def.[形態學梯度運算] 求取膨脹與腐蝕結果間的差分，其效果是突出邊緣輪廓。

Def.[頂帽（top hat）變換] 求取輸入圖像與其開運算間的差分。
Def.[黑帽（black hat）變換] 求取輸入圖像閉運算與其本身間的差分。

Def.[擊中擊不中（hit miss）變換] 元素B={ B1,B2 }，用B1去腐蝕X，然後用B2去腐蝕X的補集，得到的結果求交集就是擊中擊不中變換，這一變換用於查找局部特徵。如圖所示。

在灰度圖像中，一幅圖像的膨脹/腐蝕運算定義為：對每個像素賦值為其鄰域內輸入圖像灰度級的最大值/最小值，二值形態學的結構元素代表一個鄰域，灰度圖像形態學的結構元素是一個二元函數，它規定了希望的局部灰度級性質。

連通區域檢測是圖像處理、模式識別中常用的一個基本方法，在目標分割，邊緣檢測，區域檢測中有著廣泛的應用。

首先，連通區域是對二值圖像進行處理的，即，該圖像只有黑（0）和白（255）兩種顏色，這裡，假設目標為白色，背景為黑色。標記演算法首先對二值圖像進行一次完整的掃描，標記所有目標像素點的同時，得到並記錄等價標記對。等價標記對（以下簡稱等價對）的產生是由於掃描次序的不同，導致開始時認為是兩個不同的連通區域，後來隨著掃描的深入，又發現這兩個區域是連通的。所以，需要記錄等價對，以表明它們隸屬於同一個連通區域，以便第一次掃描結束後進行修正。標記演算法首先對二值圖像的每一個像素進行8連通區域的標記，即:對任意一個像素的上、下、左、右、左上、右上、右下、左下，共8個相鄰像素進行比較。

由於不是每個像素都有8個相鄰像素，對於一些特殊位置的像素點需要特殊考慮，其中包括：

- 二值圖像左上角的像素，由於是第一個要掃描的像素，無需進行8連通區域的檢測，也無需考慮記錄等價對的問題。
- 二值圖像第一行的像素，只需要考慮左邊相鄰像素的連通性，無需考慮記錄等價對。
- 二值圖像第一列的像素，只需要考慮上和右上2個相鄰像素的連通性。
- 二值圖像最後一列的像素，只需要考慮左、左上、上3個相鄰像素的連通性。

除了以上4種情況，其它像素，都需要考慮其8個相鄰像素的連通性，如果出現不同連通標記的相鄰像素，還需要考慮記錄等價對的問題。步驟如下：

1. 標記圖像左上角，即，第一行第一列的像素。如果其像素值為255，則標記該點的值為1，否則，開始掃描第一行第二列的像素。

2. 標記第一行的其它像素，此時，不會產生等價對的情況，不必考慮記錄等價對。對該行的每一個像素，如果其值為255，檢測左邊像素是否為255，若是，則該點標記為左邊像素點的標記；否則，該點的標記為前一個標記值加一；若該點的像素值為0，繼續掃描下一個像素。

3. 對除了第一行以外的像素行進行標記，此時會出現等價對的情況，需要進行記錄。

4. 首先對第一列進行處理，若該點像素值為0，則掃描該行下一個像素，否則，檢測上、右上兩個像素位置的像素值。若上被標記過，該點標記為上像素點的標記值。這時，再看右上是否被標記過，若也被標記過，比較上和右上的標記值是否相等，如果不相等，則記錄上和右上為一個等價對，並將其記錄在等價對記錄表中。若上沒有被標記，而右上被標記了，則該點標記為右上的標記值。如果上和右上都沒有被標記，該點的標記值為上一個標記值加一。

5. 對中間列進行處理，若該像素的像素值為255，則檢測左、左上、上、右上位置的像素值。若上述四個位置的像素值都為0，則該點的標記值為上一個標記值加一。如果上述四個位置中只有一個的像素值為255，則該點就標記為那個像素點的標記值。如果其中有m（m大於1，小於等於4）個像素點的像素值為255，則按照左、左上、上、右上的優先順序來確定該點的標記值，然後對這m個像素位置的標記值進行等價對的分析，並進行相應的記錄。

6. 對最後一列進行處理，步驟同上。

7. 依次掃描，直到所有像素值都被掃描。

8. 對等價記錄表中的所有等價對進行處理，得到最終的連通區域標記。

圖像卷積與濾波

一維信號的卷積（convolution） $g(t)=int_0^{infty} f(t- au)h( au) d au$

離散化得 $g(m)=sumlimits_{k=0}^{M_1-1} f(k)h(m-k)$

定義二維函數f(x,y)與h(x,y)的卷積 $f*h=int_{-infty}^{+infty} int_{-infty}^{+infty} f(x-a,y-b)h(a,b)dadb$

在離散系統中，定義矩陣卷積

$g(m,n)=sum_{k=0}^{M_2-1} sum_{l=0}^{N_2-1} f(m-k,n-l)h(k,l)=sum_{k=0}^{M_1-1} sum_{l=0}^{N_1-1} f(k,l)h(m-k,n-l)$

其中寬（矩陣列數）M1=f.shape[1]，高（矩陣行數）N1=f.shape[0]，輸出矩陣尺寸是M1+M2-1,N1+N2-1，稱為full形式；same返回尺寸為M1,N1的矩陣；valid形式輸出矩陣尺寸是M1-M2+1,N1-N2+1

利用傅里葉變換的卷積定理（頻域相乘相當於時域卷積，時域相乘相當於頻域卷積）可以實現卷積與 FFT 的互相轉化。既然卷積與傅里葉變換可以互化，那麼將圖像與某些特定的卷積核（kernel）進行卷積（或將這些矩陣看做卷積掩膜， mask），就可以實現濾波的效果。

圖像差分（圖像梯度，gradient）顯然可以由 $I_x(x,y)=I(x+1,y)-I_x(x-1,y)$

計算，如果寫成卷積形式，即 $I_x=I*h_x, I_y=I*h_y$

就可以得到Roberts運算元

$h_x=egin{pmatrix} -1 & 0 \ 0 & 1 end{pmatrix},h_y=egin{pmatrix} 0 & -1 \ 1 & 0 end{pmatrix}$

假如同時考慮用周圍8鄰域的數據來計算，就可以得到Prewitt運算元

$h_x=egin{pmatrix} -1 & -1 & -1 \ 0 & 0 & 0\ 1 & 1 & 1 end{pmatrix},h_y=egin{pmatrix} -1 & 0 & 1 \-1 & 0 & 1 \ -1 & 0 & 1 end{pmatrix}$

假如對中間一行（列）進行加權，就得到Sobel運算元

$h_x=egin{pmatrix} -1 & -2 & -1 \ 0 & 0 & 0\ 1 & 2 & 1 end{pmatrix},h_y=egin{pmatrix} -1 & 0 & 1 \-2 & 0 & 2 \ -1 & 0 & 1 end{pmatrix}$

如不聲明，圖像差分是指圖像與Sobel運算元的卷積，其幅值與相角

$G(x,y)=sqrt{I_x^2 (x,y)+I_y^2 (x,y)}, heta (x,y)= an^{-1} frac{I_y^2 (x,y)}{I_x^2 (x,y)}$

圖像積分

$J(x,y)=sum_{a<x,b<y} I(a,b)$

假設每個像素上的雜訊是一個均值為0，標準差為σ的獨立隨機變數，則可通過多次採集相同的靜態景物來獲得一幅平均圖像，平均圖像中的雜訊仍是隨機變數，均值為0，標準差為$ $sigma/sqrt{k}$ $，若只能獲得一幅帶有雜訊的圖像，則通過圖像的局部鄰域平均完成濾波，這就是均值濾波，均值濾波屬於線性濾波，如果雜訊大小小於圖像中感興趣的最小尺寸，處理結果是可以接受的，但仍存在邊緣模糊的問題，卷積核

$k=frac{1}{9}egin{pmatrix} 1 & 1 & 1 \ 1 & 1 & 1\ 1 & 1 & 1 end{pmatrix}$

有時也採用

$k=frac{1}{10}egin{pmatrix} 1 & 1 & 1 \ 1 & 2 & 1\ 1 & 1 & 1 end{pmatrix}quad ext{or} quad k=frac{1}{16}egin{pmatrix} 1 & 2 & 1 \ 2 & 4 & 2\ 1 & 2 & 1 end{pmatrix}$

Def.(雜訊) 實際圖像常受一些隨機誤差的影響而退化，這些退化稱為雜訊(noise)，在圖像獲取、傳輸或處理中都可能出現雜訊，雜訊可能依賴於圖像內容，也可能與其無關。

Note.

- [白雜訊(white noise)] 具有常量的功率譜，強度不隨頻率的增加而衰減

- [高斯雜訊(Gaussian noise)] 服從正態分布的隨機變數

- [加性雜訊(additive noise)] 雜訊與出現的圖像信號無關，g=f+noise

- [乘性雜訊(additive noise)] 雜訊與出現的圖像信號有關，g=f(1+noise)

- [信噪比] 信號平方和與誤差平方和之比 $SNR=frac{sum_{(m,n)} f^2 (m,n)}{sum_{(m,n)} noise^2 (m,n)}$

椒鹽雜訊（salt-and-pepper noise）又稱脈衝雜訊，它隨機改變一些像素值，在二值圖像上表現為使一些像素點變白，一些像素點變黑；是由圖像感測器，傳輸信道，解碼處理等產生的黑白相間的亮暗點雜訊，往往由圖像切割引起。

椒鹽雜訊是指兩種雜訊，一種是鹽雜訊（salt noise），另一種是胡椒雜訊（pepper noise）。鹽為白色，胡椒為黑色，因此鹽雜訊又稱白雜訊，胡椒雜訊又稱黑雜訊。前者是高灰度雜訊，後者屬於低灰度雜訊。一般兩種雜訊同時出現，呈現在圖像上就是黑白雜點。

Note. 其他均值濾波器

- [幾何均值濾波器] $f(x,y)=left(prod_{(s,t)in S_{xy}} g(s,t) ight)^{1/mn}$ 與算術均值濾波器相比，它的優勢在於在濾波過程中丟失的圖像細節更少

- [諧波均值濾波器（調和均值濾波器）] $f(x,y)={mn}{prod_{(s,t)in S_{xy}} frac{1}{g(s,t)}}$ 處理高斯雜訊和鹽雜訊效果好，但不適合胡椒雜訊

- [逆諧波均值濾波器] $f(x,y)=frac{prod_{(s,t)in S_{xy}} g(s,t)^{Q+1}}{prod_{(s,t)in S_{xy}} g(s,t)^{Q}}$ 其中Q為濾波的階數。它適合消除或減少椒鹽雜訊，當Q>0時，用於消除胡椒雜訊，當Q<0時，用於消除鹽雜訊，因此不能同時消除這兩種雜訊

關於高斯濾波和拉普拉斯濾波，本文參考了高斯金字塔與拉普拉斯金字塔和拉普拉斯運算元

高斯濾波基於高斯函數的形狀形成卷積掩模，對於去除服從正態分布的雜訊很有效；高斯濾波的特點：

- 高斯函數具有旋轉對稱性，高斯濾波在各個方向上的平滑程度是相同的，從而使後續的邊緣檢測不會偏向某一方向；
- 高斯函數是單值函數，高斯濾波器用像素鄰域的加權均值來代替該點的像素值，而每一鄰域像素點權值是隨該點與中心點的距離單調增減的；
- 高斯函數具有特殊的形狀，可通過調節高斯函數的標準差，在圖像過於模糊（過平滑）與圖像雜訊/細紋理過多（欠平滑）之間進行折中；
- 由於高斯函數的可分離性，大高斯濾波器可以得以有效地實現。二維高斯函數卷積可以分兩步來進行，首先將圖像與一維高斯函數進行卷積，然後將卷積結果與方向垂直的相同一維高斯函數卷積．因此，二維高斯濾波的計算量隨濾波模板寬度成線性增長而不是成平方增長；
- 高斯函數的DFT結果仍是高斯函數，因此，高斯函數的傅里葉變換頻譜是單瓣的；這意味著，平滑圖像不會被不需要的高頻信號所污染，高斯濾波器是一種低通濾波器，圖像中的雜訊一般是高頻信號，高斯濾波可以在一定程度上抑制較高頻率的雜訊，同時保留大部分所需的低頻信號。

圖像的二階導數一般用拉普拉斯運算元表示，即 $abla^2 I=frac{partial^2 I}{partial x^2 }+frac{partial^2 I}{partial y^2 }$

由一維情況下 $frac{partial^2f}{partial x^2} = f(x+1)-f(x)-f(x)+f(x-1)$

$frac{partial^2f}{partial y^2} = f(y+1)-f(y)-f(y)+f(y-1)$

那麼得到上述二階微分：

$abla^2f = frac{partial^2f}{partial x^2}+frac{partial^2f}{partial y^2}\=[f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)]-4f(x,y)$

上述是數學表達形式的拉普拉斯運算元，那麼我們可以將其表達為卷積核的形式，它相當於I與如下運算元進行卷積

$L= egin{pmatrix} 0 & 1 & 0\ 1 & -4 & 1\ 0 & 1 & 0 end{pmatrix}$

以上是基本的拉普拉斯運算元，其變形有

$L_1=egin{pmatrix} 1 & 1 & 1\ 1 & -8 & 1\ 1 & 1 & 1 end{pmatrix}quad L_2= egin{pmatrix} 0 & -1 & 0\ -1 & 4 & -1\ 0 & -1 & 0 end{pmatrix}quad L_3=egin{pmatrix} -1 & -1 & -1\ -1 & 8 & -1\ -1 & -1 & -1 end{pmatrix}$

如果在圖像中的一個比較暗的區域出現了一個亮點，那麼經過拉普拉斯運算元處理後，這個亮點將變得更亮，因為在一個很暗的區域內，很亮的點和其周圍的點屬於差異比較大的點，基於二階微分的拉普拉斯運算元就是求取這種像素值發生突然變換的點或線.此運算元卻可用二次微分正峰和負峰之間的過零點來確定，對孤立點或端點更為敏感，因此特別適用於以突出圖像中的孤立點、孤立線或線端點為目的的場合。

同梯度運算元一樣，拉普拉斯運算元也會增強圖像中的雜訊，有時用拉普拉斯運算元進行邊緣檢測時，可將圖像先進行平滑處理。但是在進行銳化的過程中，我們又不希望這個濾波器改變了圖像中其他pixel的信息，所以保證了每個濾波器的元素數值和加起來為0

如果拉普拉斯掩模中心元素為負，那麼拉普拉斯銳化 $f(x,y)leftarrow f(x,y)- abla^2 f(x,y)$ 如果拉普拉斯掩模中心元素為正，那麼拉普拉斯銳化 $f(x,y)leftarrow f(x,y)+ abla^2 f(x,y)$ 這種簡單的銳化方法既可以產生拉普拉斯銳化處理的效果，同時又能保留背景信息，將原始圖像疊加到拉普拉斯變換的處理結果中去，可以使圖像中的各灰度值得到保留，使灰度突變處的對比度得到增強，最終結果是在保留圖像背景的前提下，突現出圖像中小的細節信息。

常用的平滑濾波器：高斯函數，滿足

$h(x,sigma )=frac{1}{sqrt{2pi} sigma } exp left(-frac{x^2}{2sigma ^2} ight)$

推廣到二維

$h(x,y,sigma )=frac{1}{2pi sigma^2 } exp left(-frac{x^2+y^2}{2sigma ^2} ight)$

那麼一階微分濾波器

$egin{gather} frac{partial h}{partial x}=-frac{1}{sqrt{2 pi} sigma }exp left(-frac{y^2}{2sigma^2 } ight) cdot frac{x}{sqrt{2 pi} sigma ^3 } exp left(-frac{x^2}{2sigma^2 } ight)\ frac{partial h}{partial y}=-frac{1}{sqrt{2 pi} sigma } exp left(-frac{x^2}{2sigma ^2 } ight) cdot frac{x}{sqrt{2 pi} sigma ^3 } exp left(-frac{y^2}{2sigma^2 } ight) end{gather}$

二階微分濾波器（高斯-拉普拉斯運算元，Laplacian of Gaussian, LoG）

$abla^2 h=frac{1}{2pi sigma ^4 } left( frac{x^2+y^2}{sigma ^2} -2 ight) exp left(-frac{x^2+y^2}{2sigma ^2} ight)$

Note.
- 線性平滑的問題：圖像的邊緣被模糊了
- 非線性平滑方法：根據指定標準，將當前像素鄰域分成兩個子區域，僅使用鄰域中與被處理像素有類似性質的點完成平滑
- 限制數據有效性下的平均僅使用滿足某種標準的像素做平均，從而避免模糊；設定非法數據範圍[min,max]，只有在[min,max]內的像素值才被其鄰域的平均所取代，只有有效的數據才對鄰域的平均有貢獻

使用旋轉掩模的平均通過搜索當前像素鄰域的一致性部分來避免邊緣模糊，像素的均值操作只在具有一致性的區域內進行；設區域R的像素數目是n，且輸入圖像是f，用亮度散布度量區域的一致性:

$sigma^2 = frac{1}{n} sum_{(i,j) in R} [f(i,j)-frac{1}{n} sum_{(i,j) in R} f(i,j)]^2$

這樣，比掩模小的細節信息將會損失，演算法可以迭代使用，迭代過程會較快收斂到一個穩定狀態。

中值濾波用像素點鄰域灰度值的中值來代替該像素點的灰度值，不依賴於鄰域內與典型值差別很大的灰度值，可以減少邊緣的模糊，對去除椒鹽雜訊非常有效。

中值濾波的步驟：

- 確定掩模大小和掩模中心
- 在掩模內將像素點按亮度值大小排序
- 選擇序列的中間值作為掩模中心的新像素值，如果像素點數為偶數，中值取排序像素中間兩點的平均值。

不同於圖像積分，箱式濾波的數組A中的每個元素的值是該像素鄰域內的像素和（或像素平方和），在需要求某個矩形內像素和的時候，直接訪問數組中對應的位置就可以了。因此可以看出它的複雜度是O(1)，步驟如下：

1. 給定一張圖像，寬高為（M,N），確定待求矩形模板的寬高(m,n)

2. 開闢一段大小為M的數組，記為buff, 用來存儲計算過程的中間變數；

3. 將矩形模板（紫色）從左上角（0，0）開始，逐像素向右滑動，到達行末時，矩形移動到下一行的開頭（0，1），如此反覆，每移動到一個新位置時，計算矩形內的像素和，保存在數組A中；

4. 計算sum[i] = sum[i-1] - buff[x-1] + buff[x+m-1]

5. 對buff進行更新。加上一個新進來的像素，再減去一個出去的像素，然後便開始新的一行的計算了。

Note.(ROF（Rudin-Osher-Fatemi）去噪模型) 一幅（灰度）圖像 I 的全變差（Total Variation， TV）定義為梯度範數之和。在連續表示的情況下，全變差表示為： $J(I)=int abla I(x,y)dxdy$
在 Chambolle 提出的 ROF 模型里，目標函數為尋找降噪後的圖像 U，使下式最小： $min_U? ||I-U||^2+2lambda IU$

Note.(方向濾波器) 設(x,y)是(x,y)經仿射變換旋轉θ之後的坐標，則 $I(x,y)*f( heta)=frac{1}{c} int_{-infty}^{+infty} h(t)I(x,y)dt \ ext{where }h(t)=exp (-frac{t^2}{2sigma^2}),c=int_{-infty}^{+infty} h(t)dt$

Note.(自適應濾波器)

$f(x,y)leftarrow f(x,y)-frac{sigma_1^2}{sigma_2^2}[f(x,y)-mu]$

其中 $sigma_1^2,sigma_2^2$ 分別表示雜訊方差和圖象局部方差，μ為均值。

圖像的分裂、歸併、分割

在處理圖像的過程中，由於圖像中某個像素與相鄰像素之間的有很強的相關性，即不管是從紋理還是從灰度級都很相似。所以如果物體的尺寸很小或者說對比度不高，通常則需要採用較高的解析度來觀察。如果物體的尺寸很大或者說對比度很強，那麼就僅僅需要較低的解析度就能夠來傳觀了。如果現在物體的尺寸有大有小，對比度有強有弱，這些關係同時存在，這個時候，只能用多解析度進行處理。圖像金字塔就是為了以多解析度來解釋圖像而誕生的一種簡單有效的方法。

一幅圖像的金字塔，是以一系列以金字塔形狀排列的解析度初步降低的圖像的集合。金字塔的底部是待處理圖像的高解析度的表示，而頂部是低解析度的表示；當金字塔向上層移動的時候，尺寸和解析度都會降低。

假設基礎級（也就是最底層）的尺寸為 $2^J imes 2^J$ 即 $N imes N ,J = log_2 N$ ，那麼金字塔中間任意一級j的尺寸大小為： $2^j imes 2^j, j in [0,J]$ ，所以說，一個完整的圖像金字塔可以由 J+1 個解析度集所組成。

Def.[區域歸併] 根據預先定義的標準，把像素或者子區域集合成較大區域，特殊的演算法區別在於初始分割的定義和歸併標準，區域歸併的結果通常與歸併的順序有關。步驟如下：

定義某種初始化方法將圖像分割很多具有一致性的小區域
為歸併兩個鄰接區域定義一個標準
將滿足歸併標準的所有鄰接區域歸併起來，如果不再有兩個區域歸併後滿足一致性要求，則停止

區域歸併的基本方法：使用區域 $2 imes 2, 4 imes 4, 8 imes 8$ 像素的區域作為起始，使用區域灰度直方圖描述區域一致性，將區域描述與相鄰區域的描述進行比較，如果相互匹配，就將它們歸併成一個較大的區域且計算新區域的描述；否則，區域標記為非匹配。對所有區域的相鄰區域（包括新生成的區域）連續地進行歸併，如果一個區域不能和其任何鄰接的區域歸併，則將其標記為「最終」，當所有區域都被標記為最終的，歸併結束。

區域分裂是區域歸併的反過程，首先將整個圖像作為一個區域，然後連續地對每個存在的區域進行一致性測試，對不滿足測試條件的區域進行分裂，直到所有區域均滿足一致性條件。注意，即使使用相同的一致性測試條件，也不能保證區域歸併和區域分裂的結果相同。

區域分裂與歸併結合的方法可以集中兩種方法的優點。分裂與歸併方法使用金字塔形圖像表示，區域是方形的，對應著金字塔表示的某層元素：

- 分裂如果在任一層次上（不包括最低層）的任何區域不滿足一致性測試條件，則將其分裂為四個子區域，它們是下一層較高解析度元素，分裂過程對應於金字塔的降採樣（pyramid-down）過程，即自上而下（top-down）的採樣，可以使用差分高斯運算元（DoG）作為掩膜來實現，稱為高斯金字塔。

- 歸併如果在任一層次上存在四個具有接近相同的一致性度量的相鄰區域，則將其歸併為金字塔中上一層中的單個區域，歸併過程對應於金字塔的升採樣（pyramid-up）過程，即自下而上（bottom-up）的採樣，可以使用差分拉普拉斯運算元作為掩膜來實現，稱為拉普拉斯金字塔。拉普拉斯金字塔是高斯金字塔的逆過程，作用是重建高斯金字塔。

- 降採樣 對第i層圖像金字塔進行高斯內核卷積，將所有偶數行和列去除，得到的圖像即為第i+1層的圖像，顯而易見，結果圖像只有原圖的四分之一，向下取樣會逐漸丟失圖像的信息，縮小圖像。

- 升採樣 將圖像在每個方向擴大為原來的兩倍，新增的行和列以0填充，使用先前同樣的內核(乘以4)與放大後的圖像卷積，獲得「新增像素」的近似值，得到的圖像即為放大後的圖像，但是與原來的圖像相比會發覺比較模糊，因為在縮放的過程中已經丟失了一些信息，如果想在縮小和放大整個過程中減少信息的丟失，就需要與原圖進行比較。

可以採用分割四叉樹的數據結構描述這一過程，葉子結點表示一致區域，區域分裂與歸併對應於分割四叉樹的刪除或建立部分，分割結束後，樹的葉子節點數對應於分割後的區域數。步驟如下：

1. 初始化：定義一個劃分為區域的初始分割、一致性準則、金字塔數據結構

2. 在金字塔數據結構中，如果任意一個區域不是一致的，將其分裂為四個子區域；如果具有相同父節點的四個區域具有一致性，則歸併它們；如果沒有區域可以分裂或歸併，繼續執行下一步驟

3. 如果任意兩個鄰接區域具有一致性，（即使它們在金字塔的不同層或沒有相同的父節點），則歸併它們

4. 如果必須刪除小尺寸區域，則將小區域與其最相似的鄰接區域歸併

Def.[圖像分割（image segment）] 將圖像劃分為與其中含有的真實世界的物體或區域有強相關性的組成部分。

[完全分割] 分割結果是一組唯一對應於輸入圖像中物體的互不相交的區域集合

[部分分割] 分割後的區域並不直接對應於物體，圖像被劃分一些同性質區域

若將圖像數據看做地形表面，梯度圖像的灰度值表示高度，則區域邊緣對應著高的分水嶺（watershed），低梯度值的區域內部對應著集水盆地。顯然，集水盆地區域具有如下性質：同一集水盆地的所有像素與該盆地的最小高程（灰度）區域有一條像素的簡單路徑相連，沿著該路徑的灰度是單調遞減的。分水嶺分割演算法的目標，就是找到集水盆地和分水嶺脊線。

分水嶺圖像分割方法之一

- 從圖像的每個像素，開始尋找到圖像表面高度局部最小值的下降路徑；

- 定義集水盆地為滿足如下條件的像素集合：下降路徑終止於相同的高度最小點。

分水嶺圖像分割方法之二（部分文獻中稱為泛洪填充演算法，即floodfill）

- 從底部填充集水盆地，從而標識下降路徑

- 設每個局部最小值處存在一個孔，將地形表面浸泡在水中

- 水從極小值位置開始，填充所有的集水盆地，如果兩個集水盆地交匯，需要在交匯處修建一條高達最高高度的水壩，水壩表示分水嶺脊線

步驟如下：

1. 對輸入梯度圖像計算亮度直方圖，創建一張具有灰度值的像素指針表

2. 設填充過程達到k層，則每個灰度小於等於k的像素被分配了唯一的集水盆地標號

3. 通過指針表獲取灰度為k+1的元素，如果像素鄰域至少有一個已經具有標號l，將其放入FIFO隊列等待處理

4. 計算測定的集水盆地的測地學影響區域，即鄰近集水盆地卻未標註的圖像像素所在地，進行標號

5. 隊列中的元素按照順序處理，沒有分配已有標號的像素代表新發現的集水盆地，用新的標號標註。

泛洪填充演算法又稱洪水填充演算法，是在很多圖形繪製軟體中常用的填充演算法，如同windows畫圖中的油漆桶功能。演算法的原理很簡單，就是從一個點開始附近像素點，填充成新的顏色，直到封閉區域內的所有像素點都被填充新顏色為止。泛洪填充實現最常見有四鄰域像素填充法，八鄰域像素填充法，基於掃描線的像素填充方法。根據實現又可以分為遞歸與非遞歸（基於棧）。