100+ Times Faster Weighted Median Filter

The Chinese Univeristy of Hong Kong

This figure is an overview of our proposed acceleration techniques including joint-histogram, median tracking, and necklace table.

Abstract

Weighted median, in the form of either solver or filter, has been employed in a wide range of computer vision applications for its beneficial properties in sparsity representation. But it is hard to be accelerated due to both the spatial varying weight and median property compared with other local filters. We propose an efficient scheme to reduce computation complexity from O(r²) to O(r) where r is the kernel size. Our contribution is on a new joint-histogram representation, median tracking, and a new data structure that enables fast data access. The effectiveness of this scheme is demonstrated on optical flow estimation, stereo matching, structure-texture separation, image filtering, to name a few. The running time is largely shortened from several minutes to less than 1 second.

Downloads

"100+ Times Faster Weighted Median Filter"
Qi Zhang, Li Xu, Jiaya Jia
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2014

	[Paper (pdf, 2.1MB)]
	[Excutable]
	[Source Code (C++ code file)]
	[Source Code (MATLAB Interface)]
	[Source Code (VS Project)]

Applications

Our fast weighted median filter has various applications in many computer vision and image processing topics, such as edge-aware image filtering, guided filtering in optical flow and stereo matching, removing JPEG artifacts and texture smoothing. Other applications of our filter include: solving sparse-norm optimization problem, cross image filtering, detail enhancement and tone-mapping, non-photorealistic rendering, guided order filtering and guided sparse-norm filtering.

Application in Optical Flow
The weighted median filter (WMF) can function as a non-local regularizer in different computer vision systems. The connection between WMF and non-local regularizer is firstly proposed in [1], and further used for solving optical flow problem in [2]. However, the WMF in [2] is a brute-force implementation which becomes a major performance bottleneck due to slowness. Our accelerated WMF can be also used in this case to accelerate the optimization process. We replace the WMF step in "Classic+NL" method [2] by ours. Similar quality results are obtained with EFE difference smaller than 1%. Meanwhile, the system is accelerated in WMF step by at least 30 times. Althrough the window radius is as small as 7 in classic+NL, obvious acceleration is achieved by our method comparing with the bruteforce one.
Input Frame	Classic+NL with original WMF (850 seconds)	Classic+NL WITH our WMF (20 seconds)



Duing zooming in, use mouse wheel to control the magnification ratio.

Application in Stereo Matching
We also demonstrate accleration using our weighted median filter (WMF) in stereo matching. We replace the WMF step of [4] with ours. The execution time of our WMF is only 198ms on average for the four cases in the Middlebury Stereo Dataset. The original WMF implementation of [4] takes 20000+ms only for filtering occluded region, which is much slower than ours. The figures below show the raw depth maps computed by [4] and the filtered depth maps after performing hole-filling and our WMF.
Input Frame	Depth Map	Depth Map filtered by our WMF


Duing zooming in, use mouse wheel to control the magnification ratio.

Application in Removing JPEG Artifacts
Our weighted median filter (WMF) can be used to remove JPEG artifacts. Thanks to the robustness and edge preserving properties of weighted median filter, our smoothing results are visually compelling, as shown in the results below. Notably, in this application, WMF is better than L0 gradient minization [3] because it also removes large scale artifacts but [3] does not. On the other hand, WMF is better than average-based filter such as bilateral filter, because the former completely removes the artifacts while the later only averages them. In terms of performance, our method takes only 0.1 second on average to process each image. The size of the images is around 400x300.
Input Image	JPEG Artifacts Removed



Duing zooming in, use mouse wheel to control the magnification ratio.

References

[1] Y. Li and S. Osher. A new median formula with applications to pde based denoising. Commun. Math. Sci, 7(3):741–753, 2009.

[2] D. Sun, S. Roth, and M. J. Black. Secrets of optical flow estimation and their principles. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2010.

[3] L. Xu, C. Lu, Y. Xu, and J. Jia. Image smoothing via L0 gradient minimization. ACM Trans. Graph., 30(6), 2011.

[4] C. Rhemann, A. Hosni, M. Bleyer, C. Rother, and M. Gelautz. Fast cost-volume filtering for visual correspondence and beyond. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011.