84 COMMUNICATIONS OF THE ACM | MARCH 2015 | VOL. 58 | NO. 3
are easy to identify in image space; a threshold on color
differences suffices to differentiate edges from variations due to texture. This is a key aspect of our approach:
we generate new pyramid coefficients by working primarily on the input image itself, rather than altering the pyramid coefficients directly.
The overall design of our algorithm derives from this
insight: we build an approximation of the desired output image specific to each pyramid coefficient. This is a
major difference with the existing literature. Whereas
previous techniques are formulated in terms of optimization
(e.g., Farbman et al. 11), PDEs (e.g., Perona and Malik29), or
local averaging (e.g., Tomasi and Manduchi34), we express
our filter through the computation of these local image
approximations together with standard image pyramid
manipulations. In practice, we use locally processed versions of the input to recompute values for each pyramid
coefficient, and combine all of these new coefficient values into the final result. For each coefficient at location (x,
y) and level l, we first determine the region in the input
image on which this coefficient depends. To reduce the
amplitude of edges, for example, we clamp all the pixels
values in that region so that the difference to the average
value does not exceed a user-provided threshold. This processed image has the desired property that edges are now
limited in amplitude, to at most twice the threshold. This
also has the side effect of flattening the details across the
edge. As we discuss below, these details are not lost, they
are actually captured by pyramid coefficients centered on
the other side of the edge as illustrated in Figure 3. Then,
we compute the Laplacian pyramid of this processed image
to create coefficients that capture this property. In particular,
this gives us the value of the coefficient (x, y, l) that we seek.
Another way of interpreting our method is that we locally filter the image, for example, through a local contrast decrease,
and then determine the corresponding coefficient in the
Laplacian pyramid. We repeat this process, such that each
coefficient in the pyramid is computed.
Detail preservation. As mentioned earlier, a reasonable
concern at this point is that the clamped image has lost
details in the thresholded regions, which in turn could
induce a loss in the final output. However, the loss of
details does not transfer to our final result. Intuitively, the
clamped details are on “the other side of the edge” and are
represented by other coefficients. Applying this scheme to
all pyramid coefficients accurately represents the texture
on each side of the edge, while capturing the reduction in
edge amplitude (Figure 3). Further, clamping affects only
half of the edge and, by combining coefficients on “both
sides of the edge,” our approach reconstructs an edge pro-
file that closely resembles the input image, that is, the out-
put profiles do not suffer from oversmoothing. Examining
the pyramid coefficients reveals that our scheme fulfills
our initial objective, that is, that the edge coefficients are
scaled down while the other coefficients representing the
texture are preserved (Figure 2).
4. LOCAL LAPLACIAN FILTERING
We now formalize the intuition gained in the previous
section and introduce Local Laplacian Filtering, our new
method for edge-aware image processing based on the
Laplacian pyramid. A visual overview is given in Figure 4 and
the pseudo-code is provided in Algorithm 1.
In Local Laplacian Filtering, an input image is processed
by constructing the Laplacian pyramid {L[I¢]} of the output,
one coefficient at a time. For each coefficient (x, y, l), we
generate an intermediate image by applying a point-wise
monotonic remapping function rg,s(×) to the original full-resolution image. This remapping function, whose design
we discuss later, depends on the local image value from
the Gaussian pyramid g = Gl(x, y) and the user parameter s
which is used to distinguish edges from details. We compute
the pyramid for the intermediate image {L[ ]} and copy the
corresponding coefficient to the output {L[I¢]}. After all coefficients of the output pyramid have been computed, we collapse the output pyramid to get the final result.
A direct implementation of this algorithm yields a complexity in O(N2) with N being the number of pixels in the
image, since each coefficient entails the construction of
another pyramid with O(N) pixels. However, this cost can be
Input signal Right clipped Left clipped Merged
I
L0
L1
sr
sr
Figure 3. Simple view of our range compression approach, which is
based on thresholding and local processing. For a step-like signal
similar to the one in Figure 2, our method effectively builds two
Laplacian pyramids, corresponding to clipping the input based on
the signal value to the left and right of the step edge, then merging
their coefficients as indicated by the color coding.
Figure 4. Overview of the basic idea of our approach. For each pixel
in the Gaussian pyramid of the input (red dot), we look up its value g.
Based on g, we remap the input image using a point-wise function,
build a Laplacian pyramid from this intermediate result, then copy
the appropriate pixel into the output Laplacian pyramid. This process
is repeated for each pixel over all scales until the output pyramid
is filled, which is then collapsed to give the final result. For more
efficient computation, only parts of the intermediate pyramid need to
be generated.
Input image
Remapped
subimage
Gaussian
pyramid
Intermediate
Laplacian
pyramid
Output
Laplacian
pyramid
g
r(i)