特殊半徑的中值模糊算法急速優化，在某些預處理過程中有着非常重要的應用，本文給出基于SSE的指令的3*3核大小中值優化的方法，實測能達到4000*4000灰階圖7.5ms實作的速度，并介紹了Photoshop中蒙塵和劃痕算法的原理及其和中值模糊的關系。
在本人的部落格裡，分享了有關中值模糊的O(1)算法，詳見：任意半徑中值濾波（擴充至百分比濾波器）O(1)時間複雜度算法的原理、實作及效果 ，這裡的算法的執行時間和參數是無關的。整體來說，雖然速度也很快，但是在某些特殊情況下我們還是需要更快的速度。特别是對于小半徑的中值，我們有理由去對其進一步的優化的。本文我們進一步探讨這個問題。
一、3*3中值模糊
首先我們來看看半徑為1的中值，此時涉及到的領域為3*3，共9個像素，那麼最傳統的實作方式就是對9個像素直接進行排序，這裡我們直接使用系統的排序函數qsort，一種簡單的代碼如下所示：
代碼很簡潔和清晰，我們沒有處理邊緣的那一圈像素，這無關精要，我們編譯後測試，結果如下所示：
1920*1080大小的24位圖像，平均用時1280ms，灰階圖像平均用時460ms，這相當的慢，無法接受。
下面我們稍微對其進行下提速。
對于9個資料的排序，我們可以對其進行特殊的處理，因為資料的個數是确定的，按照理論分析，沒有必要進行大規模的比較，實際隻需要進行19次比較就可以了。修改後算法如下所示：
看上去代碼的行數多了，但是實際上執行速度會更快，我們測試的結果如下：
1920*1080大小的24位圖像，平均用時155ms，灰階圖像平均用時45ms，比之前的原始實作速度要快了近10倍。
而在任意半徑中值濾波（擴充至百分比濾波器）O(1)時間複雜度算法的原理、實作及效果一文中的算法，采用了SSE優化，同樣大小的圖耗時為：
1920*1080大小的24位圖像，平均用時260ms，灰階圖像平均用時160ms，比上述的C語言版本要慢。
早期有朋友曾提示我在手機上使用Neon可以做到16MB的圖像半徑為1的中值模糊可以做到20ms，我真的一點也不敢相信。總覺得不太可思議。16MB可是4000*4000的大小啊，我用上述C的代碼處理起來要242ms，比手機端還慢了10倍。
經過朋友提醒，在https://github.com/ARM-software/ComputeLibrary/blob/master/src/core/NEON/kernels/NEMedian3x3Kernel.cpp#L113上看到了相關的Neon代碼，驚奇的發現他和我上面的C代碼幾乎完全一樣。但是就是這一點代碼提醒了我。
真是一語驚醒夢中人啊，這麼簡單的優化我怎麼沒想到呢。
我們自己看看上面的C代碼，每個像素的9次比較雖然不能用SIMD指令做，但是多個像素的比較之間是互相不關聯的，是以，這樣我就可以一次性處理16個像素了，改成SSE優化的方式也就很簡單了：
注意到上面我已經把灰階和彩色圖像的代碼寫成同一個方式處理了，這是因為對于彩色圖像，3個通道之間的處理時毫無聯系的。同時我們前面的Swap2個變量的過程時完全可以通過Min和Max兩個算子實作的，我們按下F5測試運作，驚人的速度出現了：
1920*1080大小的24位圖像，平均用時3ms，灰階圖像平均用時1ms，比上述的C語言版本快了近40倍。
順便也測試了下16MB的圖像，結果平均隻需要7.5ms。真是太厲害了。
二、5*5中值模糊
對于5*5的中值模糊，優化的方式還是一樣的，但是5*5共計25個像素，理論上需要131次比較，其他的過程類似，測試基于SSE的方式，5*5的中值1920*1080大小的24位圖像，平均用時40ms，灰階圖像平均用時20ms，雖慢了很多，但是還是O(1)那裡的速度快。
三、蒙塵和劃痕
在這裡提Photoshop的這個算法也許并不是很合适，但是我也是在研究中值模糊時順便把這個算法給攻破的，當我們打開蒙塵和劃痕界面時，發現其有半徑和門檻值兩個參數，細心比較，如果門檻值設定為0，則相同半徑設定時其結果圖像和雜色裡的中間值算法的結果一模一樣，這也可以從蒙塵和劃痕算法和中間值同樣都放在雜色菜單下可以看出端倪。
通過上述分析，我們可以肯定蒙塵和劃痕算法是基于中值模糊的，實際上，PS裡很多算法都是基于中值模糊的，特别是那些有平滑度參數的算法^_^。經過多次測試，我們得到的該算法的結果就是如下：
if Abs(Median - Src) > Threshold
Dest = Median
else
Dest = Src
對于彩色圖像，不是用彩色圖的中值，而是用其亮度值作為唯一的判斷标準，如果用彩色的中值作為标準來判斷每個分量的，很容易出現過多的噪點，因為有可能會出現Blue分量改變，而Red不變的情況，或其他類似現象。
蒙塵和劃痕的一個作用是去除噪點，特别的，我覺得他在小半徑的時候更為有用，小半徑中值不會改變原圖太多，加上這個門檻值則可以很容易去除噪點，同時，基本不會出現新的模糊問題。比如下面這個圖。
原圖 半徑為1的中值模糊
半徑為1，門檻值取20時的蒙塵和劃痕 半徑為2，門檻值取20時的蒙塵和劃痕
由以上幾圖，可以明顯的看出，帶門檻值的蒙塵和劃痕在抑制了噪音的同時對原圖其他細節基本沒有破壞，是以，是一種比較合适的初級的預處理算法，既然是預處理，那麼其效率就非常重要了，是以本文的快速3*3模糊的作用也就是相當有用。
還舉個例子，下面這個照片中有很多白色的小點點，如果直接用中值确實可以将白點去除，但是可能要半徑為四左右才可以去除，但是此時圖像整體也變得模糊了，如果使用蒙版和劃痕，則處理後的效果非常完美。
原圖 半徑4，門檻值100
本文相關算法代碼下載下傳位址：https://files.cnblogs.com/files/Imageshop/MedianBlur3X3.rar。
本人的SSE算法優化合集DEMO:測試Demo:https://files.cnblogs.com/files/Imageshop/SSE_Optimization_Demo.rar。