劉海峰, 張 超, 羅 江, 林福良

?

一種用于中值濾波的改進均值劃分算法①

劉海峰, 張 超, 羅 江, 林福良

(北京控制與電子技術(shù)研究所信息系統(tǒng)工程重點實驗室, 北京 100038)

圖像濾波是很多圖像處理算法在圖像預(yù)處理階段采用的處理措施, 而中值濾波不僅能夠有效地去除圖像中的噪聲, 而且可以保持圖像的邊緣細節(jié), 從而成為首選的圖像濾波方法. 由于中值濾波需要使用排序操作, 其計算時間復(fù)雜度較高, 而且在濾波窗口較大時, 導(dǎo)致圖像濾波耗費較長的時間, 不能滿足海量、高分辨率圖像實時濾波處理的需求. 在研究中值濾波基礎(chǔ)上, 提出一種改進的基于均值劃分的快速中值濾波算法, 實驗表明, 該算法可以有效地降低圖像中值濾波的時間消耗, 特別是在大尺度圖像中, 當濾波窗口較大時, 能夠顯著降低圖像濾波時間, 同時, 能夠與傳統(tǒng)中值濾波保持一致的效果, 進一步增強了大尺度圖像實時處理能力.

圖像濾波; 中值濾波; 均值劃分; 濾波時間; 濾波效果

由于受到環(huán)境、采集設(shè)備等各種因素的影響, 傳感器獲取的圖像往往受到噪聲的干擾, 使得圖像存在質(zhì)量退化現(xiàn)象. 因此, 在絕大多數(shù)圖像處理過程中, 圖像預(yù)處理[1]通常是首要的操作, 如圖像濾波、圖像校正、灰度變換等, 其中圖像濾波是最重要的圖像預(yù)處理操作, 包括高斯濾波[2]、中值濾波[3]、雙邊濾波[4]、均值濾波[5]等.

中值濾波作為一種非線性平滑濾波方法, 不僅能夠有效的消除圖像中的隨機噪聲, 而且不會使圖像邊緣變得模糊, 能夠有效保護原始圖像信號, 得到了廣泛的應(yīng)用. 然而, 傳統(tǒng)中值濾波需要對濾波窗口內(nèi)的所有圖像數(shù)據(jù)進行排序操作, 排序操作需要大量的數(shù)據(jù)比較和移動, 使得中值濾波花費較長的時間, 不能滿足海量、大尺度圖像實時處理的要求.

為提高中值濾波的速度, 出現(xiàn)了很多改進算法. 例如, 針對灰度圖像, 文獻[6]提出了一種基于查表法的快速中值濾波方法, 然而, 該方法只適用于8位灰度圖像. 文獻[7]則充分利用濾波窗口之間的相關(guān)性, 提出了一種快速中值濾波算法, 該算法充分利用滑動窗口的先驗信息, 考慮移入像素值和移出像素值的位置關(guān)系, 達到像素數(shù)據(jù)的快速插入與刪除, 然而該方法不適用于序列相關(guān)性差的場合, 如前后兩次中值濾波的窗口不存在大量的重疊區(qū)域以及只對符合條件的區(qū)域進行濾波[8]. 文獻[9]提出了一種均值加速中值濾波算法, 雖然該算法可以有效提升濾波速度, 但是其濾波結(jié)果與傳統(tǒng)中值濾波結(jié)果相差較大, 本文受該算法啟發(fā), 提出了改進措施, 在提升濾波速度的同時, 使得濾波結(jié)果與傳統(tǒng)中值濾波結(jié)果保持一致.

1　傳統(tǒng)中值濾波算法

傳統(tǒng)的中值濾波算法就是從一個數(shù)據(jù)集合中找出其中值. 對于二維圖像信號, 以窗口中心為原點的中值濾波的定義為:

圖1 二維圖像中值濾波窗口示意圖

二維圖像的中值濾波算法對窗口的形狀沒有限制, 常用的窗口形狀[10]包括: 矩形、十字形、圓形等, 如圖2所示為窗口大小為5*5的窗口形狀:

(a) 矩形(b) 十字形(c) 圓形

中值濾波算法最核心的操作就是排序, 其主要使用快速排序算法, 而快速排序的平均時間復(fù)雜度為, 此處為待排序的數(shù)據(jù)數(shù)目. 快速排序需要進行大量的數(shù)據(jù)比較和移動操作, 當數(shù)據(jù)量較大時會耗費較多的時間, 從而使得中值濾波算法不能滿足實時性要求.

2　改進的均值劃分快速中值濾波算法

2.1 算法原理

傳統(tǒng)的中值濾波算法需要對所有數(shù)據(jù)進行排序, 對于大尺度圖像, 當濾波窗口較大時, 整個中值濾波需要耗費較長時間. 本文算法借鑒文獻[9]的“均值加速”思想, 提出改進的均值劃分法, 減少參與排序的數(shù)據(jù)量, 從而達到降低中值濾波時間的目的.

圖3給出了基于文獻[9]提出的均值加速中值濾波算法的一個分析示例.

圖3 文獻[9]濾波算法示例, 終止條件為當前集合元素數(shù)目大于N/2. 可以看出, 提取的中值存在錯誤

圖4 5*5的濾波窗口及濾波中心

從圖3可以看出, 其不能正確找出濾波窗口中真正的中值, 其原因就在于沒有設(shè)計好對排序集合選擇的策略, 導(dǎo)致選擇了一個不合適的集合進行排序, 從而得到錯誤的濾波中值.

本文提出的改進的基于均值劃分的快速中值濾波算法的基本原理與均值加速法相似, 即: 對于濾波窗口覆蓋的圖像像素集合, 首先計算該集合中所有像素值的均值, 然后以均值將集合劃分為大于等于均值的像素集合以及小于均值的像素集合, 分別記錄這兩類集合的像素數(shù)目, 接著, 只對像素數(shù)目超過濾波窗口總像素數(shù)目一半的集合重復(fù)以上操作, 并分別累加這兩類集合元素的數(shù)目, 直到某次分解的兩類集合元素數(shù)目都小于濾波窗口總像素數(shù)目的一半, 最后, 只對兩類集合累加數(shù)目超過濾波窗口總像素數(shù)目一半的集合進行排序.

相比較均值加速算法, 本文算法在劃分過程中增加了統(tǒng)計每類集合像素數(shù)目的策略, 從而解決了不能找到真正濾波中值的問題.

圖5給出了圖3中的示例采用本文提出的改進的基于均值劃分的快速中值濾波算法得到的濾波過程:

從圖5中可以看出, 采用本文設(shè)計的選擇劃分排序集合的策略后, 能夠正確的選擇排序集合, 在減少參與排序數(shù)據(jù)量的同時, 減少了排序劃分的時間, 而且取得與傳統(tǒng)中值濾波相同的效果.

2.2 算法原理及流程

本文提出改進的基于均值劃分的快速中值濾波算法, 通過引入排序集合選擇策略, 可以正確選擇對最后一次劃分得到的排序集合, 該策略的核心是: 在每次劃分后都重新統(tǒng)計大于等于均值的集合的元素數(shù)目, 以及小于均值的集合的元素數(shù)目, 當某次劃分得到的兩個集合的元素數(shù)目都小于濾波窗口總像素數(shù)目的一半時, 選擇累加元素數(shù)目超過濾波窗口總元素數(shù)目一半的集合作為最終的排序集合.

圖5 本文提出的改進的基于均值劃分的快速中值濾波算法的濾波過程, 可以得到正確的濾波中值

圖6給出了本文提出的改進的基于均值劃分的中值濾波算法的流程圖, 其基本步驟如下:

圖6 本文提出的改進的基于均值劃分的中值濾波算法流程圖, 增加了集合選擇策略

上述步驟中的第7)和第8)體現(xiàn)了集合選擇策略, 該策略是根據(jù)集合和集合累計元素數(shù)量與濾波窗口像素數(shù)目一半的關(guān)系進行集合選擇的, 同時, 不同的集合選擇, 采用的排序規(guī)則也不同, 即: 當集合的累計元素數(shù)目超過濾波窗口圖像像素數(shù)目的一半時, 則對集合進行排序, 排序規(guī)則為由大到小排序; 而當集合的累計元素數(shù)目超過濾波窗口圖像像素數(shù)目的一半時, 則對集合進行排序, 而采用的排序規(guī)則為由小到大排序.

考慮到在均值劃分過程中需要對數(shù)據(jù)進行移動, 如果移動的數(shù)據(jù)過多, 反而增加時間消耗, 為此, 本文將終止條件限制為原始濾波窗口的一半, 以便在移動數(shù)據(jù)量最小與排序量最小之間達到平衡.

圖8給出了采用本文提出的改進的基于均值劃分的快速中值濾波算法的另一個時間例子, 濾波窗口及濾波中心如圖7所示. 通過人工計算得出該實際例子的中值為76, 由圖8的濾波結(jié)果可以看出, 利用本文提出的濾波算法可以正確獲取濾波窗口的中值.

圖7 濾波窗口及濾波中心

此外, 由圖5與圖8可以看出, 對于選擇大于等于均值的集合(即)進行排序時采用的是由大到小的排序方式; 而對于選擇小于均值的集合(即)進行排序時采用的是由小到大的排序方式, 目的是保持提取中值位置公式的一致性.

3　實驗與分析

為驗證本文提出的改進的基于均值劃分的快速中值濾波算法的有效性, 將本文算法用于大尺度圖像的中值濾波處理, 并與傳統(tǒng)的中值濾波算法進行對比, 比較的指標為中值濾波耗費的時間. 同時, 與文獻[9]提出的均值加速中值濾波算法進行比較, 由于這兩種方法的計算時間復(fù)雜度相同, 因此, 此處采取的指標為中值濾波的效果, 即檢驗兩種算法是否能夠保持傳統(tǒng)中值濾波算法的效果.

圖8 本文提出的改進的基于均值劃分的快速中值濾波算法的另一個例子, 可以得到正確的中值

實驗采用的計算機為聯(lián)想臺式機, CPU主頻3.2GHz, 內(nèi)存4GB, 分別采用分辨率為256*256、512*512、1024*1024三種圖像進行濾波實驗, 通過改變?yōu)V波窗口大小來觀察濾波時間的變化, 濾波窗口大小范圍為3*3到25*25.

3.1 與傳統(tǒng)中值濾波時間比較

圖9到圖11分別給出了在256*256、512*512、1024*1024三種分辨率圖像上進行中值濾波的時間耗費對比曲線圖, 在計算時, 每取一種濾波窗口, 連續(xù)運行100次取平均濾波時間.

可以看出, 本文算法在較小的濾波窗口時, 并不比傳統(tǒng)中值濾波算法節(jié)省時間, 相反, 需要的濾波時間可能更多, 這主要是因為, 本文提出的改進的基于均值劃分的中值濾波算法需要對濾波窗口內(nèi)的像素進行劃分, 該過程涉及到較多的數(shù)據(jù)比較和移動, 在濾波窗口較小時, 雖然最后一次快速排序的數(shù)據(jù)量大量減少, 但是加上前期數(shù)據(jù)劃分產(chǎn)生的數(shù)據(jù)比較和移動開銷可能會超過對整個濾波窗口的快速排序的時間開銷, 因此, 導(dǎo)致整個圖像的耗時較長.

圖9 本文算法與傳統(tǒng)中值濾波算法在分辨率為256*256圖像上的對比

圖10 本文算法與傳統(tǒng)中值濾波算法在分辨率為512*512圖像上的對比

圖11 本文算法與傳統(tǒng)中值濾波算法在分辨率為1024*1024圖像上的對比

然而, 隨著濾波窗口的增大, 本文提出的算法優(yōu)勢越來越明顯, 特別是當濾波窗口大于9*9時, 本文算法耗時要少于傳統(tǒng)中值濾波算法, 而且隨著濾波窗口的增大, 節(jié)省的濾波時間越來越多, 而這種優(yōu)勢, 對于大尺度圖像濾波更明顯.

由此可以得出, 本文提出的算法更適用于較大的濾波窗口, 而且, 對于圖像分辨率越大的圖像, 采用本文提出算法的優(yōu)勢越明顯.

3.2 與文獻[9]濾波效果比較

本文算法還與文獻[9]提出的改進中值濾波算法進行了濾波效果對比, 圖12和圖13給出了三種中值濾波算法的效果圖, 分辨率分別為512*512的灰度圖像和256*256的彩色圖像, 濾波窗口大小都設(shè)定為11*11(注: 濾波窗口大小對比較濾波效果無影響).

從圖12中可以看出, 本文算法的濾波效果能夠保持與傳統(tǒng)中值濾波算法一致, 而文獻[9]提出的改進中值濾波算法由于提取濾波窗口中值時產(chǎn)生了錯誤, 導(dǎo)致圖像濾波結(jié)果出現(xiàn)了畸變, 在中值濾波后的圖像中出現(xiàn)了大片的斑點, 已經(jīng)導(dǎo)致圖像內(nèi)容的改變, 造成濾波圖像失真.

(a) 傳統(tǒng)中值濾波效果

(b) 本文算法濾波效果

(c) 文獻[9]中值濾波效果

由圖13同樣可以看出, 本文算法能夠保持與傳統(tǒng)中值濾波算法相同的效果, 而文獻[9]提出的改進中值濾波同樣出現(xiàn)了斑點, 造成彩色圖像顏色發(fā)生變化, 從而導(dǎo)致彩色圖像發(fā)生畸變.

(a) 傳統(tǒng)中值濾波效果

(b) 本文算法濾波效果

(c) 文獻[9]中值濾波效果

為了進一步進行對比, 分別計算本文提出的算法和文獻[9]提出的算法與傳統(tǒng)中值濾波算法的結(jié)果進行做差比較, 即: 將兩幅圖像中對應(yīng)的位置做圖像減法[11], 取絕對誤差, 并累加整幅圖像的所有絕對誤差以及計算整幅圖像平均絕對誤差(也可以采用均方誤差[12]), 比較結(jié)果如表1所示.

表1 本文算法和文獻[9]及傳統(tǒng)中值濾波效果計算對比結(jié)果(單位: 像素值)

通過表1可以看出, 本文提出的中值濾波算法與傳統(tǒng)中值濾波算法的結(jié)果圖像進行做差計算得到的絕對誤差和與平均絕對誤差都為0, 這說明了, 本文提出的濾波算法能夠保持與傳統(tǒng)中值濾波算法相同的濾波結(jié)果. 而文獻[9]中的濾波算法與傳統(tǒng)濾波結(jié)果的比較不管是絕對誤差和, 還是平均絕對誤差都不為零, 這說明了, 文獻[9]中的濾波算法不能保持與傳統(tǒng)中值濾波算法相同的濾波效果, 也即改變了中值濾波的本質(zhì)功能.

綜上所述, 可以得出, 本文提出的改進的基于均值劃分的中值濾波算法, 不僅能夠在濾波時間上要快于傳統(tǒng)的中值濾波算法, 而且, 在濾波效果上與傳統(tǒng)中值濾波算法保持了一致性, 同時, 本文算法也能夠適用于彩色圖像的中值濾波, 由算法原理可知, 本文算法既適用于8位位深的圖像, 也適用于16位甚至更高位深的圖像. 此外, 濾波效果要優(yōu)于文獻[9]提出的改進中值濾波算法. 通過與傳統(tǒng)中值濾波算法的比較可以得出, 本文算法具有較強的實用性, 特別是在較大濾波窗口條件下對大尺度圖像濾波時, 時間效能更加明顯, 進一步提升了海量、高分辨率圖像的實時處理能力.

4　結(jié)語

本文在研究傳統(tǒng)中值濾波以及其他的中值濾波算法的基礎(chǔ)上, 通過分析現(xiàn)有改進中值濾波算法存在的缺點, 引入排序集合選擇策略, 進而提出了一種用于中值濾波的改進均值劃分算法, 該算法不僅能夠加快大尺度圖像中值濾波的濾波速度, 而且避免了基于均值加速算法的不足, 能夠保持與傳統(tǒng)中值濾波算法具有相同的濾波效果, 對于海量、大尺度圖像的實時處理具有重要應(yīng)用價值. 此外, 本文提出的中值濾波算法不僅適用于灰度圖像, 而且也適用于彩色圖像; 同時, 本文算法也適用于其他需要中值濾波的應(yīng)用場景, 如雷達信號.

1 王紅君,施楠,趙輝,岳有軍.改進中值濾波方法的圖像預(yù)處理技術(shù).計算機系統(tǒng)應(yīng)用,2015,24(5):237–240.

2 王懷野,張科,李言俊.一種自適應(yīng)各項異性高斯濾波方法. 計算機工程與應(yīng)用,2004,(10):18–19.

3 Hanji G, Latte MV. Novel median filter for impluse noise suppression from digital images. International Journal of Computer Application, 2014, 106(8): 18–21.

4 楊學志,徐勇,方靜,盧潔,左美霞.結(jié)合區(qū)域分割和雙邊濾波的圖像去噪新算法.中國圖象圖形學報,2012,17(1): 40–48.

5 陳乃金,周鳴爭,潘冬冬.一種新的維納濾波圖像去高速噪聲算法.計算機系統(tǒng)應(yīng)用,2010,19(3):111–114.

6 Huang TS. A fast two-dimensional median filtering algorithm. IEEE Trans. on ASSP, 1979, 27(1): 13–18.

7 朱冰蓮,潘哲明,李單單.一種中值濾波的快速算法.信號處理,2008,24(4):684–686.

8 顧茂松,楊小岡,繆棟.一種基于局部差別的基準圖去噪方法. 彈箭與制導(dǎo)學報,2007,1:280–182.

9 張麗,陳志強,高文煥,康克軍.均值加速的快速中值濾波算法.清華大學學報(自然科學版),2004,44(9):1157–1159.

10 曹治華,宋斌恒.多種形狀窗口下的快速中值濾波算法.計算機應(yīng)用研究,2006,3:85–88.

11 李繼良,于策,孫濟洲,商朝暉,陳錦言,曹瑋,張旭明.基于OpenMP的并行圖像相減算法實現(xiàn)與分析.天文研究與技術(shù),2011,8(2):146–152.

12 Shukla HS, Kumar N, Tripathi RP. Median filter based wavelet transform for multilevel noise. International Journal of Computer Applications, 2014, 107(14): 11–14.

Improved Mean Division Algorithm for Median Filtering

LIU Hai-Feng, ZHANG Chao, LUO Jiang, LIN Fu-Liang

(Science and Technology on Information Systems Engineering Laboratory, Beijing Institute of Control and Electronic Technology, Beijing 100038, China)

Image filter is the method for image pre-processing in many image processing algorithms. Since, median filter not only can smooth image noise, but also can hold the image edge, it becomes the most used method in image filter. Median filter needs sorting operation, its time complex is very high. When filter window becomes larger, median filter will need more time, it cannot be used in large image real-time processing. Based on the median filter research, a faster median filter algorithm which is based median division is proposed. The proposed algorithm can reduce filter time effectively, especially in large scale image, when filter window is large, it becomes more remarkable. Compared with the traditional median filter algorithm, the proposed algorithm filter result can hold the preference as same as the traditional median filter algorithm, and it can be used on gray and color image. The experiment shows that the proposed median filter algorithm not only speeds up image filter speed, but also improves the real-time of image processing.

image filter; median filter; mean division; filter time; filter result

2016-06-20;

2016-08-11

[10.15888/j.cnki.csa.005673]