1. mean filter的加速
mean filter的特性是，1.線性 2.均值。
這兩個性質告訴我們兩件事，線性的意思對我們來說是我們可以把它拆成其他的矩陣的組合，均值的意思是我們在迴圈中取到的座標(i,j)是不會改變系數的。
但是mean filter實在是太簡單了，我們可以用更快速的方法，那就是積分影像
甚麼是積分影像？就是某點上表示的不是像素了，而是向左和向上所有像素的和
1
|
2
|
4
|
1
|
3
|
2
|
1
|
8
|
2
|
1
|
3
|
1
|
2
|
3
|
4
|
2
|
1
|
2
|
4
|
1
|
3
|
2
|
1
|
8
|
2
|
1
|
3
|
1
|
2
|
3
|
4
|
2
|
1
|
3
|
4
|
1
|
3
|
2
|
1
|
8
|
2
|
1
|
3
|
1
|
2
|
3
|
4
|
2
|
1
|
3
|
7
|
1
|
3
|
2
|
1
|
8
|
2
|
1
|
3
|
1
|
2
|
3
|
4
|
2
|
1
|
3
|
7
|
8
|
3
|
2
|
1
|
8
|
2
|
1
|
3
|
1
|
2
|
3
|
4
|
2
|
1
|
3
|
7
|
8
|
4
|
2
|
1
|
8
|
2
|
1
|
3
|
1
|
2
|
3
|
4
|
2
|
1
|
3
|
7
|
8
|
4
|
9
|
1
|
8
|
2
|
1
|
3
|
1
|
2
|
3
|
4
|
2
|
1
|
3
|
7
|
8
|
4
|
9
|
17
|
33
|
6
|
16
|
36
|
80
|
8
|
27
|
77
|
159
|
他有甚麼意義呢？
我們看第三列第三行的36就等於這個範圍的面積
於是我們知道只要36-7-6=23就可以算出來了
回到mean filter，跟積分影像完美的契合在一起。
我們也是在算面積，而且是固定大小的面積，只是會一直移動座標而已
於是程式碼就變得非常簡單
1.利用原影像生成積分影像
2.基本巢狀迴圈利用積分影像算出面積除以filter大小給值即可
只要這兩步就可以完成了，至於加速的時間有多少呢？
根據執行環境硬體配備不同，花費時間會因人而異，不過可以從執行時間找到一些性質
左邊是單純用基本巢狀迴圈的5X5大小的mean filter，右邊是利用積分影像加速的一樣是5X5大小的mean filter結果
可以看到一個花了3.22秒，積分影像只要用1.9秒，
接下來我們把mean filter的大小從5X5提升到11X11看看
左邊一樣是普通的巢狀迴圈，右邊則是積分影像加速後的
11X11的情況下，普通的演算法時間增加到了10.4秒，但是積分影像的演算法仍然維持在不到2秒的1.83秒，這就是積分影像加速的程度。
原本花費的時間應該是O(M*N*P*Q)，積分影像只需要O(M*N)的時間，換句話說，當filter的大小越大的時候，積分影像的優勢就會更加明顯，因為不管filter size有多大多小都不會影響到積分影像演算法的複雜度，都會保持在O(M*N)。
2.binomail filter的加速
之前我們把高斯濾波器改成使用二項式濾波器來使用，其實有一個更重要的原因，原因就在這裡，為了加速。
當然如果二項式濾波器可以使用積分影像的演算法加速是最好的，但是問題就在這裡，二項式濾波器只有一個性質：線性，也就是說我們只能利用矩陣組合這個特性，不能使用mean filter的均質特性使用積分影像。
但是也因為線性我們掌握了一個加速的直覺方式－－用更小維度的矩陣
來看看原本的二項式濾波器的長相，5X5為例
1
|
4
|
6
|
4
|
1
|
4
|
16
|
24
|
16
|
4
|
6
|
24
|
36
|
24
|
6
|
4
|
16
|
24
|
16
|
4
|
1
|
4
|
6
|
4
|
1
|
其實可以拆成兩個只有一維的矩陣相乘
1
|
4
|
6
|
4
|
1
|
1
|
4
|
6
|
4
|
1
|
我們可以改成先乘上只有X方向的1X5的矩陣然後先給值
接下來在乘上只有Y方向的5X1的矩陣然後在給值
記得這第二步一定要使用第一步乘完的結果
這個就是可拆分(seperabel)的性質，基本上只要有可拆分性質的濾波器都可以靠這個方法加速
下面是一些可拆分的例子
那加速的程度有多少呢？我們來看看
這是5X5普通的巢狀迴圈花費大約6.35秒
使用拆分法加速後2.6秒
接下來看看filter大小是否會影響加速的時間
11X11普通的巢狀迴圈花費大約21.4秒
使用拆分法加速後5.39秒
拆分法比較快這點我們早就可以確定了，這裡的討論部分在於，果然拆分法花費的時間會被filter大小給影響呢，之前的積分影像方法是因為複雜度與filter大小無關只與影像本身像素多寡有關，但是到了沒辦法使用積分影像的binomail filter，我們確實使用了拆分法加速，從O(P*Q)的方式降低到只要O(P+Q)，所以整體而言從原本的O(M*N*P*Q)降低到O(M*N*(P+Q))，所以filter大小增加，加速演算法仍然會被影響而增加，這也是因為binomial filter只剩下拆分性質可以讓我們來作加速的緣故。
3.Bilateral filter的加速
接下來就是條件更加嚴苛的雙邊濾波器的加速，雙邊濾波器就沒有剛剛所說的「線性」和「均值」的性質了，他完完全全是因地制宜，完全看當時的像處與周遭像素的差距來決定矩陣的內容，我們沒辦法預測也沒辦法先算出來，可是如果不從迴圈下手基本上我們加速的程度也只是枝微末節而已，減少的時間幅度非常小，所以這裡我們要引進一個新的filter－－sobel filter。
sobel filter長這樣，他有兩個形式
回到雙邊濾波器，缺少剛剛講到可以加速的兩個重要性質，
因此想要加速的話只有把演算的的過程簡化到至少有「線性」的性質，至於要怎麼簡化呢？
基本上模糊化的函數可以我早就知道可以用二項式濾波器去逼近然後可以利用拆分性質來加速，但是重點就在於「非線性」的相似度函數，這裡為了簡化，所以決定了sobel filter去決定邊緣所在的位置，然後直接用二分法：如果是邊緣，那麼就不要用距離函數的計算結果，直接用原像素來保留邊緣；反之非邊緣的話就直接帶入距離函數的結果。如此一來我們可以一個用binomial filter先算出一張模糊後的圖，一個用sobel filter算出一張只有邊緣有值的邊緣影像，這麼一來我們只要跑一次loop然後用邊緣影像的結果設為條件去決定是否要放模糊後的數值還是原本清晰的數值。
因此程式碼非常簡單
1.直接計算二項式濾波後的影像
利用拆分法，先計算出X方向的值，即某點(i,j)是往左一個半徑(i-diameter,j)，往右一個半徑(i+diameter,j)分別乘上mask係數的結果，接下來再往Y方向做一次就可以達到原本的基本迴圈計算的內容，但是只要花O(P+Q)的時間，而非原本的O(P*Q)的時間。
2.直接用未處理的原影像利用sobel filter計算出邊緣影像
當然一樣利用可拆分的性質去加速運算。
首先要先轉成灰階影像
cvtColor(temp_mat, gray_mat, CV_RGB2GRAY);
要注意的是cvtColor()會直接把src矩陣的type複製到dst矩陣，如果src矩陣是32FC3的彩色影像，那麼dst矩陣就是32FC1的灰階影像
8U : 0~255
32F：0.0~1.0
至於為什麼都要轉flaot來計算呢？原因很簡單，因為float的像素顏色會自動設在介在0~1之間，所以不會有溢出的可能，如果數字不小心大於1只有在影像輸出時會自動上限為1，但是內容並不會被強制改成1，所以沒溢出的麻煩就可以保留住計算的數值是非常方便的，
最後利用X以及Y方向的梯度決定出一張邊緣影像。
3.利用前面兩個的陣列結果，用二分法決定Bilateral filter之後的值。
對每一個點去找其邊緣結果圖是否為1，是的話代表他是邊緣上的像素把它保留直接等於原圖的值；否就讓他等於二項式濾波後的影像值直接等於模糊化後的成果
就這麼簡單，讓我們來看看加速的成果吧。
首先是11X11大小的filter結果
簡化加速前的版本
簡化加速後的版本
可以看出結果圖基本上是一樣的，Bilateral filter在模糊影像讓影像變的平滑細緻的同時把邊緣部分的關鍵像素也保留起來它的輪廓，兩者的結果十分接近，但是時間可就天差地遠了，也許簡化後的計算會遺失一些更細緻的邊緣，但是時間從原本的78.9秒一口氣下降到9.7秒，差了8倍之多，我們已經把O(M*N*P*Q)的演算法降低維度到O(M*N*(P+Q))了，所以簡化所遺失的細緻的部分比起時間我們是很可以接受的。
比較未使用相似度函數的普通binomial filter(上3.2.2)與有使用相似度函數Bilateral filter(下3.3.3)的結果，11X11大小的filter
應該可以看出在臉部邊緣，睫毛和瞳孔以及背景部分的髮絲是否有保留下來
X,Y兩個方向的sobel filter後的梯度函數
最後是sobel filter後的影像，門檻值0.5結果，可以看到睫毛眼睛部分以及頭髮的髮絲部分都被標示成邊緣，所以他們就會在之後的Bilateral filter之中被保存下來，也就避免到了所謂邊緣之真的結果了。
如果還是覺得不夠明顯，可以看看有毛這種細緻的地方的影像處理的結果
左邊是原影像，右邊bilateral filter
白色的毛都被保留下來了，代表我們這定的邊緣真的都是這些毛髮的地方沒錯，直接看看sobel filter所保留的邊緣影像
果然真的是如此。
到這裡上一章講到的所有filter的加速就完成了。
參考資料：wiki、google圖片
參考網址：Bilateral Filtering for Gray and Color Images、雙邊濾波器 (Bilateral Filter)
沒有留言:
張貼留言