MARCH 2015 | VOL. 58 | NO. 3 | COMMUNICATIONS OF THE ACM 85
variations smaller than s should be considered fine-scale
details and larger variations are edges. As a center point for
this function we use g = Gl(x, y), which represents the image
intensity at the location and scale where we compute the output pyramid coefficient. Intuitively, pixels closer than s to g
should be processed as details and those farther than s away
should be processed as edges. We differentiate their treatment by defining two functions rd and re, such that r(i) = rd(i)
if |i − g| £ s and r(i) = re(i) otherwise. Since we require r to
be monotonically increasing, rd and re must have this property as well. Furthermore, to avoid the creation of spurious
discontinuities, we constrain rd and re to be continuous by
requiring that rd( g ± s) = re( g ± s).
The function rd modifies the fine-scale details by altering the
oscillations around the value g. In our applications we process
positive and negative details symmetrically, letting us write:
rd(i, g, s) = g + sign (i – g)s fd(|i − g|/s) ( 1)
where fd is a smooth function mapping from [0, 1] to [0, 1]
that controls how details are modified. The advantage of this
formulation is that it depends only on the amplitude of the
detail |i − g| relative to the parameter s, that is, |i − g|/s = 1
corresponds to a detail of maximum amplitude according
to the user-defined parameter. Analogously, re is a function
that modifies the amplitude of edges that we again formulate in a symmetric way:
re(i, g, s) = g + sign (i – g)( fe(|i − g|−s) + s) ( 2)
where fe is a smooth nonnegative function defined over [0, ¥).
In this formulation, re depends only on the amplitude above
the user threshold s, that is, |i − g| − s. The function fe controls how the edge amplitude is modified since an edge of
amplitude s + fe(a) becomes an edge with amplitude s + fe(a).
For our previous 1D range compression example, clipping
edges corresponds to fe = 0, which limits the amplitude of all
edges to s. Useful specific choices for rd and re are described
in the next section and are illustrated in Figure 5.
The advantage of the functional forms defined in
Equations ( 1) and ( 2) is that they ensure that r is continuous
and increasing, and the design of a specific filter boils down
to defining the two point-wise functions fd and fe that each
reduced in a straightforward way by processing only the sub-
pyramid needed to evaluate Ll[ ](x, y), illustrated in Figure 4.
The base of this subpyramid lies within a K × K subregion
R of the input image I, where K = O(2l); for Laplacian pyramids built using a standard 5-tap interpolation filter, it can
be shown that K = 3(2l+ 2 − 1). Put together with the fact that
level l contains O(N/2l) coefficients, each level requires the
manipulation of O(N) coefficients in total. Since there are
O(log N) levels in the pyramid, the overall complexity of our
algorithm is O(N log N). Later we will see that some applications only require a fixed number of levels to be processed or
limit the depth of the subpyramids to a fixed value, reducing
the complexity of our algorithm further.
Remapping function for gray-scale images. We assume
the user has provided a parameter s such that intensity
Figure 5. Family of point-wise functions for edge-aware manipulation described in Sections 5. 2 and 5. 3. The parameters a and b let us control
how detail and tone are processed respectively. To compute a given Laplacian coefficient in the output, we filter the original image point-wise
using a nonlinear function r(i) of the form shown. This remapping function is parametrized by the Gaussian pyramid coefficient g, describing
the local image content, and a threshold s used to distinguish fine details (red) from larger edges (blue).
r(i)
Detail smoothing
gg
Edge-aware detail manipulation
Detail enhancement Tone mapping Inverse tone mapping
Edge-aware tone manipulation
gi gi gi
sr sr sr sr sr sr
gi
r(i)
gg
gi
r(i)
g
0 ≤ b < 1
0 < a < 1a > 1
b = 1
0 < a < 1
b = 1
a = 1
0 ≤ b < 1
a = 1
b > 1
Algorithm 1 O(N log N) Version of Local Laplacian Filtering
input: image I, parameter s, remapping function r
output: image I¢
1: compute input Gaussian pyramid {G[I ]}
2: for all coefficients at position (x, y) and level l do
3: g ¬ Gl(x, y)
4: determine subregion R of I needed to evaluate Ll(x, y)
5: create temporary buffer of the same size
6: for all pixels (u, v) of R do
7: apply remapping function: (u, v) ¬ r(R(u, v), g, s)
8: end for
9: compute subpyramid {L[ ]}
10: update output pyramid: Ll[I¢](x, y) ¬ Ll[ ](x, y)
11: end for
12: collapse output pyramid: I¢ ¬ collapse({Ll[I¢]})
Our algorithm considers the pyramid coefficients one by one
(Step 2). Each of them is computed using the pixels from the
finest resolution (Step 4) by applying the remapping function to them (Step 7) and building a Laplacian pyramid of the
remapped data (Step 9). We copy the relevant coefficient into
the output pyramid (Step 10) and once all the coefficients have
been computed, we collapse pyramid the get the final result
(Step 12).