Real-Time O(1) Bilateral Filtering
∗
Qingxiong Yang
∗
Kar-Han Tan
†
Narendra Ahuja
∗
∗
University of Illinois at Urbana Champaign
†
HP Labs, Palo Alto
http://vision.ai.uiuc.edu/
˜
qyang6/
Abstract
We propose a new bilateral filtering algorithm with com-
putational complexity invariant to filter kernel size, so-
called O(1) or constant time in the literature. By showing
that a bilateral filter can be decomposed into a number of
constant time spatial filters, our method yields a new class
of constant time bilateral filters that can have arbitrary spa-
tial
1
and arbitrary range kernels. In contrast, the current
available constant time algorithm requires the use of spe-
cific spatial or specific range kernels. Also, our algorithm
lends itself to a parallel implementation leading to the first
real-time O(1) algorithm that we know of. Meanwhile, our
algorithm yields higher quality results since we are effec-
tively quantizing the range function instead of quantizing
both the range function and the input image. Empirical ex-
periments show that our algorithm not only gives higher
PSNR, but is about 10× faster than the state-of-the-art. It
also has a small memory footprint, needed only 2% of the
memory required by the state-of-the-art for obtaining the
same quality as exact using 8-bit images. We also show
that our algorithm can be easily extended for O(1) median
filtering. Our bilateral filtering algorithm was tested in a
number of applications, including HD video conferencing,
video abstraction, highlight removal, and multi-focus imag-
ing.
1. Introduction
Originally introduced by Tomasi and Manduchi [2], bi-
lateral filters are edge preserving operators that have found
widespread use in many computer vision and graphics tasks
like denoising [3, 4, 5, 6, 7], texture editing and relighting
[8], tone management [9, 10], demosaicking [11], styliza-
tion [12], optical-flow estimation [13, 14] and stereo match-
ing [15, 16].
Until recently, bilateral filters were too computationally
intensive for real time applications. Several efficient numer-
ical schemes [9, 17, 18, 19, 20] enable it to be computed at
∗
This work is supported by a grant from HP lab. Part of this work was
done while Qingxiong Yang was an intern in HP Lab.
1
an IIR O (1) solution needs to be available for the kernel.
interactive speed or even video rate using GPU (Graphics
Processing Unit) implementation [21]. With the exception
of [19], which approximates the bilateral by filtering sub-
sampled copies of the image, these algorithms do not scale
well since they become more expensive as the filtering win-
dow size grows, which limits their utility in high resolution
real time applications. [19] actually becomes faster as the
size increases due to greater subsampling, but the exact out-
put is dependent on the phase of subsampling.
It was therefore a significant advance when Porikli [1]
demonstrated that bilateral filters can be computed at con-
stant time with respect to filter size for three types of bi-
lateral filters. (1) Box spatial and arbitrary range kernels.
Integral histogram is used to avoid the redundant opera-
tions and interactive speed is achieved by quantizing the
input image using a small number of bins, thus trading
memory footprint and image quality for speed. For a 8-
bit grayscale image, assume 256 bins are used to compute
and store the integral histogram, 256× the size of the im-
age memory are required. The memory could be reduced
but will also change single integral histogram computation
to be 256 times, which will be much slower. (2) Arbitrary
spatial
1
and polynomial range kernels. A bilateral filter of
this form can be interpreted as the weighted sum of the spa-
tial filtered responses of the powers of the original image.
No approximation is used in this method. (3) Arbitrary
spatial
1
and Gaussian range kernels. Taylor series is used
to approximate the Gaussian range function up to the four
order derivatives. However, this method is a bad approxi-
mation for small Gaussian variances.
AnewO(1) bilateral filtering method extending Durand
and Dorsey’s piecewise-linear bilateral filtering method [9]
is proposed in the paper. As in [9], we discretize the image
intensities into a number of values, and compute a linear
filter for each such value, the output of which is defined as
Principle Bilateral Filtered Image Component (PBFIC) in
this paper. The final output is then a linear interpolation
between the two closest PBFICs. Instead of confining the
kernels to be Gaussian spatial and Gaussian range and us-
ing Fast Fourier Transform (FFT) for Gaussian convolution
which has cost O(log r) (r is the filter radius), we show that
1