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).