Communications of the ACM

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.