Qian LiuCaiming ZhangQiang Guoand Yuanfeng Zhou

A nonlocal gradient concentration method for image smoothing

Qian Liu1,Caiming Zhang1,2,Qiang Guo1,2,and Yuanfeng Zhou1

It is challenging to consistently smooth natural images,yet smoothing results determine the quality of a broad range of applications in computer vision.To achieve consistent smoothing,we propose a novel optimization model making use of the redundancy of natural images,by de fi ning a nonlocal concentration regularization term on the gradient.This nonlocal constraint is carefully combined with a gradientsparsity constraint,allowing details throughout the whole image to be removed automatically in a datadriven manner.As variations in gradient between similar patches can be suppressed e ff ectively,the new model has excellent edge preserving,detail removal, and visual consistency properties.Comparisons with state-of-the-art smoothing methods demonstrate the e ff ectiveness of the new method.Several applications, including edge manipulation, image abstraction, detail magni fi cation,and image resizing,show the applicability of the new method.

image smoothing;nonlocal similarity;L0norm;edge detection

1 Introduction

Image smoothing is a fundamental and important issue in computer vision.Natural images contain both clear structural edges of objects and abundant details caused by lightness,textures,and so on. Psychological studies show that human beings tend to pay more attention to the outlines of objectsthan trivial details[1].Indeed,images containing main structures but without details can be of use in many applications such as edge extraction,image abstraction,and tone mapping.Image smoothing aims to produce images which discard insigni fi cant details while preserving the main structural edges. Because of the complexity of natural images,it still remains difficult to give explicit de fi nitions that a computer can use to distinguish between main edges and trivial details:human beings can make fl exible decisions.

During the past decades,image smoothing has attracted much research.In terms of approaches, previous methods can be loosely classi fied into two groups,edge-preserving methods and structurepreserving methods.Edge-preserving methods[2-7] consider that human eyes are sensitive to color changes between neighboring pixels, so they aim to preserve strong-contrast edges.However, they cannot remove fi ne-scale details with large or oscillatory gradient amplitudes. Structurepreserving methods[8-17]design smoothing models based on the assumption that sliding windows containing di ff erent patterns,such as structure and oscillatory details,behave di ff erently with suitable measurement.Although fi ne-scale details can be smoothed out,edges tend to be shifted from their original positions for natural images because of the patch-wise operator.In fact,all previous works share a common defect that the quantization measure cannot re fl ect visual importance properly.Using contrast or local statistical responses,computer cannot distinguish details from structures exactly. Therefore,the main goals of image smoothing,detail removal,and edge preserving,are often in con fl ict.

It is worth noting again that we aim to smooth out details while preserving main structures in a consistent manner.The output image shouldbe composed ofsharp structuraledges and homogeneous regions.After analyzing the properties of gradient maps in natural images,we fi nd it is reasonable and practical to assume the ideal gradient map of a smoothed image should be sparse in space and nonlocally concentrating in amplitude.In order to achieve consistent smoothing performance,we propose a novel image smoothing method which we call the nonlocal gradient concentration(NGC) method.

NGC is data-driven and can be formulated as an optimization problem.In the new model,a nonlocal self-similarity property is assumed,leading to a nonlocal concentration constraint on the gradient map.Speci fi cally,under the guidance of nonlocally similarpatch groups,unstabledetailscan be reduced,and meaningful structures which are lower in contrast can be kept.Nonlocal self-similarity is an intrinsic and useful property for natural images, arising due to redundancy.Typically,it is easy to fi nd similar patches to a given patch.In computer vision and image processing,this property has been adopted as prior knowledge to achieve signi fi cant and surprising improvements.Exploiting self-similarity in color and intensity space and in the transform domain,has led to many state-of-the-art algorithms for various applications[18].However,it has not been fully adopted in image smoothing.As far as we know,our work is the first to use nonlocal similarity on the gradient map for image smoothing.Some results produced by our method are illustrated in Fig.1,showing that our method can remove details while keeping structural edges.

The main contributions of our work are as follows:

·We introduce a nonlocal constraint on the gradientmap forthe firsttimein image smoothing,and use it as a basis for a new optimization framework.

·We present an efficient iterative algorithm for optimizing the new energy model.

·We demonstrate the ability of our method in several applications.

2 Previous work

Thissection reviewssomerepresentativeedgepreserving and structure-preserving smoothing methods and analyzes them with an example shown in Figs.2 and 3.

2.1 Edge-preserving methods

Filtering using a weighted-averaging operation is a common scheme.Tomasi and Manduchi[2]proposed the simple and popular bilateral fi lter(BLF)in 1998. For each pixeliin input imagef,the outputuiis computed as

Fig.1 Image smoothing examples.Top:input images.Bottom:corresponding smoothed results using our method.

Fig.2 Results of various smoothing methods.

Fig.3 A scanline extracted from each image in Fig.2,as marked by arrows in Fig.2(a).The green channel is shown as it is representative of the main image content.Each blue curve represents the input signal,and the red curve represents the smoothed signal.

where{wi,j}are weights for all pixels inf.These are in inverse proportion to the spatial distance, and color or intensity di ff erence. This prevents strong edges from being over-smoothed.He et al.[3] proposed a guided fi lter in 2010,where a separate image is adopted to guide the linear translationvariant fi ltering procedure.It is similar to BLF in its edge-preserving properties,but it solves the gradient reversal problem in BLF and performs better near edges.The local Laplacian fi lter[4]was proposed in 2011 by Paris et al.It manipulates multi-scale details to give halo-free smoothing results.The advantage of this fi lter is its simplicity.As can be seen from Figs.2(b)-2(d),the output neither fully preserves the really important edges,nor completely removes some meaningless textures.

Optimization methods with regularization involving edgesareanotherpopularapproach. The general form used in such optimization methods is to solve

Edge-preserving methods assume that pixels with large gradient magnitudes are located on important edges explicitly or implicitly.As shown in Figs.2(b)-2(f),these methods are unable to remove small-scale textural details.

2.2 Structure-preserving methods

Structure-preserving methods rely on statistical features within local sliding windows to remove oscillations and extract structures.

Mode fi lters can suppress details by analyzing the histogram within a local sliding window;the median fi lter is the classic example.Subr et al.[8]proposed use of local extrema envelopes in 2009.First, maximum and minimum envelops are constructed respectively using extrema detected in local sliding windows.Highly contrasting oscillations can be removed simply by computing the smoothed mean envelope.Xu et al.[11]proposed the relative total variation(RTV)method in 2012.They observed that the inherent variation(aggregation of signed gradient)in sliding windows with texture is much smaller than in windows with structure.RTV can remove textures in mosaic images well,but it performs less well for natural images because complex lighting and perspective distortion make RTV over-smooth details.Karacan etal.[12] proposed aregion covariance(RC)methodin 2013.They made use of covariance matrices of simple image features to capture local structure and texture information in localpatches.It can preserve prominent edges and shading while removing texture, butthe resulting structure edges lack sharpness.A novel image decomposition method [13]wasproposed by Su etal.in 2013.They applied a Gaussian decomposition and an asymmetric sampling operator to separate texture from structure,and then used a joint bilateral correction to suppress blurring.However,it does not perform well in practice because too many variables are involved.The tree fi lter[15]was proposed by Bao et al.in 2014.It is a trilateral fi lter in which for weighted-averaging,a tree distance is adopted as well as the two factors in BLF.The minimum tree can deal with fi ne-scale details.

As shown in Figs.2(g)-2(j),with these methods, the edges are either blurred heavily or shifted mistakenly.As shown in Fig.2(l),details on the ostrich are removed and edges of the ostrich are kept consistently by our method.Figure 3 analyzes a scanline further.Figure 3(l)shows that the oscillations on the neck are smoothed thoroughly, while contrast near the two main features is retained well without being over-smoothed.

3 Model

As noted in Section 2, smoothing methods with gradient constraints have been studied,but their performance is unsatisfactory. To achieve consistently smoothed results,we propose a nonlocal optimization model in Section 3.3 based on the observations made in Section 3.2.Before describing our new model, we firstreview the general formulation of optimization with gradient constraint in Section 3.1.

3.1 Background

Gradient information is vital to the human visual system. Making useofpixel-wisegradients provides the advantage that edges do not shift from theiroriginalpositions. Therefore,we focus on optimization based methods with gradient constraints in this paper. The general form of a gradient-based optimization model for image smoothing is

wherefanduare the vectorized input and output images respectively,and?u=(?xu,?yu) denotes gradient.R(?u)is a regularization term constructed from prior knowledge concerning the gradient map of the ideal smoothed image. The regularization parameterλbalances the smoothing regularization termR(?u)with the fi delity termto control the degree of smoothing.

Fig.4 Gradient map of an example natural image and two representative sub-images.(a)Input image.(b)Visualized gradient amplitude map;amplitudes are normalized to[0,1]and colorized according to the colormap on the right.

3.2 Motivation

The key to the model de fi ned in Eq.(3)is to make reasonable and practical assumptions about the gradient map of the ideal smoothed image.An ideal smoothed image should be composed of sharp structural boundaries between di ff erent objects and consistently fl at components within homogeneous regions.Correspondingly,the gradient map of the ideal smoothed image should have the following two properties.

Property 1.The gradients of pixels on structural edges should be non-zero,and gradients of pixels belonging to the same structural edge should be consistent.In Fig.4(a),the left sub-image contains a structural edge segment for the squirrel.As shown in Fig.4(b),along the structural edge,gradient amplitudes of most pixels are large,but some have globally lower gradient amplitudes.

Property 2. The gradients of pixels in homogeneous regions should be zero.In Fig.4(a), the right sub-image is a representative texture-detail region of a stone.As shown in Fig.4(b),amplitudes of the gradients in this sub-image are oscillatory and can be seen as stochastic perturbations.Some pixels have even higher contrast compared to structural edges elsewhere in the image,while some have low gradient amplitudes.

In order to make use of the above observed properties to guide the smoothing procedure,we need to quantify them by calculable measures. Consider the spatial distribution of non-zero gradients described in Property 1.One quantitative measure of the gradient map can be provided by a discrete counting scheme.It involves theL0norm, as suggested by Ref.[7].

Use of this first measure can avoid edge-blurring and can give impressive results with strong-contrast edges.However,Property 1 relies on the pixelwise gradient amplitudes of the input image to implicitly determine structural edges.Any textures and details will a ff ect the edges in the input image,so it is unreliable.As shown in Fig.4, for natural images,the gradient amplitudes of the input image cannot completely distinguish pixels on structural edges from pixels in homogeneous regions. Firstly,some parts of structural edges have comparatively low gradient amplitudes in the input image.Secondly,many fi ne-scale texture-like details have high contrast. Therefore,the model should not completely rely on pixel-wise gradients of the input image.To achieve better smoothing performance,the gradient amplitudes of the ideal smoothed image should be estimated carefully to better guide separating structural pixels from detail pixels.Based on this observation,we propose a new prior as the second measure to help estimate the ideal gradient map.

3.3 De fi nition

We now give a de fi nition of our new model which subtly combines the above quantitative measures.

New model.Assuming the ideal gradient map can be estimated well and is denoted byg=(gx,gy), a smoothed image of high quality can be estimated by the following model:

where the first regularization term is the sparsity constraint on?u,and the second regularization term constraints?uto followg.λandβare regularization parameters.The new model involves a novelVnorm,which is explained in detail next.

As elements in?u=(?xu,?yu)are binary tuples,it cannot be measured by traditional norms. We concisely denote the regularization terms by using a superscriptV.The second term in Eq.(4) denotes the following formulation:

where#represents the cardinality of a set:this term is the number of pixels with non-zero gradient amplitudes.The third term in Eq.(4)expands to

TheL2norm has been adopted in various image processing fields,and its ability to preserving fi delity has already been demonstrated.This de fi nition ensures that the resulting gradient map?utends to follow the accurate values ing.

Nonlocal estimation ofg.In practice,it is not possible to get the exact gradient mapgof the ideal smoothed image as described in Eq.(4). However,the redundancy of natural images provides a natural way to estimateg.Because information is redundant in natural images,there are typically many repetitive or similar patches within a single image.In the ideal image,similar features should be removed or preserved in the same way,so gradients of similar patches should be consistent.Based on this observation,we propose a nonlocal gradient estimation method forg.Using this method,the gradient of a pixel can be constrained by nonlocally similar patches.

This leads to the following model:

whereNL(·)representsa nonlocalestimation operation.Speci fi cally,each pixelshould have gradient consistent with the gradients of pixels with similar patterns.A patch centered at pixeluiis denoted by.In a search windowSaroundfi,a group of similar patchescan be collected.The nonlocal gradient estimate ofuican be expressed as

where the weights are calculated in theYchannel ofYCbCrcolor space as follows:

andhacts as a parameter controlling the decay rate of the exponential function.

By combining nonlocal estimation andL0gradient minimization in a single optimization model,our new model can achieve consistent detail removal and edge preserving e ff ects.

3.4 Explanation

Asthenew modelexploitsinformation about nonlocally similar patches to constrain each pixel,it can preserve structure while removing details,to give consistent smoothed results.We now demonstrate the smoothing ability by analyzing in turn four representative patterns in natural images.Figure 5 illustrates four kinds of central patches and their corresponding similar groups.

(a)Strong structural edges(patch A in Fig.5). Both the gradient?fiand the gradients?fGare strong.During globally optimization,the gradient is kept and resulting edges are sharp.

(b)Details in homogeneous regions(patch B in Fig.5).In this situation,both the gradient?fiand the gradients?fGin the related patches are globally weak. In this case,the gradient of the current center pixel is modi fied to 0 by optimization, removing details.

Fig.5 Four representative patches A,B,C,and D(red rectangles),and for each patch,several similar patches(yellow rectangles).

(c)Weak and slender edges(patch C in Fig.5). The gradient?ficon fl icts with the gradients?fGin the related patches.In the similar pacthes, the gradients are large,indicating that there is a structural edge.However,the gradient of the current patch is weak as it is a weak piece of a structural edge.In this case,the patch group promotes and enhances the weak edge,preserving it in the resulting image.

(d)Fine-scale and high-contrast details(patch D in Fig.5).As in(c),the gradients are con fl icting. The gradients in the group have globally lowamplitudes,while the gradient of the current patch is large and is an outlier for a texture-like regions. After optimization,this outlier is removed.

In summary,the new method can deal with both detail removal and structure preservation.The nonlocal constraint can e ff ectively and automatically select important structures to preserve.Figure 6 illustrates a synthetic image with various kinds of noise.Figure 6(e)shows that our method can handle texture-like details(simulated by random salt and pepper noise)while at the same time keeping structural edges sharp.

4 Numerical solution

In this section we show how to numerically solve the nonlocal model de fi ned by Eq.(5),give the whole algorithm,and discuss the parameters involved.

4.1 Solver

Energy optimization. As solving the original modelisNP-hard,a splitting method which iteratively optimizes subproblems alternately[19] can be used as an e ff ective technique.We give closedform solutions to the two subproblems respectively. Replacing theunknown gradient(?xu,?yu) by auxiliary variables(b,d),the model in Eq.(5) can be made more fl exible.The new model can be represented as

where

and

This can be split into two subproblems which can be optimized iteratively.In each iteration,the following two steps are used.

Step 1.Fix(b,d)and solve foru.The following subproblem can be extracted from Eq.(7):

which has the optimality condition:

The solution to Eq.(9)is unique,but it is computationally complex to solve directly,requiring a large matrix inversion.Instead,Gauss-Seidel iteration can be used to solve it approximately; Fourier transforms are taken for further speed. Under periodic boundary conditions for the variableu,using a 2D discrete Fourier transform,we can diagonalize the Hessian matrix on the left hand side of Eq.(9),giving an explicit solution which only requires componentwise operations.

Step 2. Fixuand solve for(b,d). The correspondingsubproblem can beexpressed as follows:

Fig.6 Synthetic image example for image smoothing.

The nonlocal estimationNL(bi)is intractable whenbiis unknown,and it is difficult perform optimization ifNL(bi)is treated as an unknown variable.An e ff ective and practical way is to split this into two stages.Firstly,estimate the nonlocal variableNL(bi)using the estimated imageufrom the previous iteration,i.e.,replaceNL(bi)byNL(?ui).Secondly,estimatebisupposingNL(bi) known.

Furthermore, the above functionalhasthe useful property that it can be split into|{fi}|individual subproblems.For anyi,the corresponding subproblem can be formulated as optimizing the following energy functional with(bi,di)unknown. The objective functional for thei-th pixel can be written alternatively as

whereH(·)represents the Heaviside function,i.e.,H(a)=1 whena/=0 andH(a)=0 otherwise. It is easy to see that when all subproblems{Ei}are solved,the whole functional in Eq.(10)is optimized.

Equation (11) involves a discrete counting function,and its solution is made tractable by using:

Weight updating. In Step 2,the nonlocal estimationNL(?ui)involves calculation of weightswi,jas de fi ned in Eq.(6).As iteration proceeds, the estimated image?uwill get closer to the ideal smoothed image,so the results of block matching will be more accurate.Therefore,in thek-th iteration, we update the nonlocally similar group using the latest updated imageuk?1,and recalculate the weights as

In practice,block matching and weight updating can be performed everyK0iterations for speed.

Finally,the whole procedure for our method for image smoothing is summarized in Algorithm 1.

Algorithm 1:Nonlocal gradient concentration method for image smoothing Input:Original imagef,parametersλ,β,γ,ratesκ1,κ2, and number of iterationsK. Output:Smoothed imageu.

4.2 Analysis of parameters

In this section the various parameters involved are analyzed.

Regularization parametersλ,β,γ. The parameterλcontrols the degree of smoothing.In order to satisfy the requirements of the variable splitting scheme,the parametersβandγshould increase as iteration proceeds.When iteration stops, the two parameters should be large enough to guarantee the gradient map of the output image is close to the estimated gradients(b,d).

Ratesκ1,κ2. The variablesκ1andκ2control the rate of increase ofβandγviaβk=κ1βk?1andγk=κ2γk?1.

Relationship ofβandγ. From the update formula for(b,d)in Eq.(12),we can see thatβandγbalance the impact of the nonlocal estimated gradient and the local gradient for thei-th pixel.Ifβ＞γ,the nonlocal estimation dominates the local gradient,and the result will be more consistent,and vice versa.The nonlocal method degenerates to theL0model ifβ=0.

Figure 7 showsan example using varying parameters.In each row,β/γis fi xed.From left to right,asλincreases,further details are eliminated and the images become coarser.Experiments showλ=0.01?0.04 is suitable in most cases.

In each column,λis fi xed and the ratioβ/γadjusts the relative importance of nonlocal and local gradients for locating details and manipulating gradients.In the extreme case ofβ=0,our model degenerates toL0smoothing,meaning only local pixel-wise gradients are considered.Comparing the first row to the others,we can see that small scale details are retained even for largeλ.Ifβgoes beyondγ,nonlocally estimated gradients will help to handlesmall scale details,so the smoothed images are cleaner and more uniform.Values forβ/γ=0.3?2 balance nonlocal and local gradients well for most cases.

Fig.7 Images processed with varying parameters.

5 Comparison

We now compare our method to a series of smoothing methods in this section.A good smoothing method should satisfy the following requirements:structural edges should be well-preserved without being oversmoothed orblurred,whiledetailsshould be smoothed out completely.As pointed out earlier, our method degenerates toL0smoothing method if we set parameterβto 0.

As shown in Fig.8(a),the“small-house”input image is composed of explicit large-scale structures, including house and road boundaries,and highcontrast details on the roof,grass,and road.Figures 8(b)-8(j)present results of other methods whose parameters have been tuned carefully using our best e ff orts. As shown in Figs.8(b)-8(e),in order to suppress details,edge-preserving methods,including the bilateral fi lter,WLS,guided fi lter,and local Laplacian fi lter,cause blurring on structural edges. Furthermore,details cannot be removed.AlthoughL0smoothing can keep structural edges sharp,it cannot smooth out high-contrast details,as shown in Fig.8(f).

From Figs.8(g)-8(k),we can see that structurepreserving methodscan preventedgeblurring. However,some details still remain in the result for local extremal envelops as shown in Fig.8(h).RTV can remove details,but the edges are not preserved naturally as shown in Fig.8(i).Region covariance and tree fi lter methods cannot produce clear images as shown in Fig.8(j)and Fig.8(k),respectively. Compared to these methods,our method performs well in both edge preserving and detail removing. In Fig.8(l),texture details are fl attened naturally and structural edges are preserved without blurring. In summary,our method can consistently remove details and preserve structural edges.

6 Applications

Asafundamentaltechnique,imagesmoothing has many applications for base and detail layer manipulation.As can be seen from the previous section, our smoothing method can preserve structural edges well while smoothing details out. In this section,we show some applications of our method including edge detection,edge manipulation, detail magni fi cation,and content-aware resizing, to illustrate its advantage of retaining important features.

6.1 Edge detection and manipulation

Edge detection.There are rich details in natural images which can interfere with the progress of edge detection.Our method can remove trivial details, so it can help retain clean and accurate edges.As illustrated in Fig.9,many fi ne edges are included in the original gradient map,while our smoothed result can produce a gradient map mainly containing meaningful edges.The edge map detected on our smoothed image by the Canny operator is much cleaner and contains fewer unimportant edges.

Image abstraction. Image abstraction is a practical application given the developing demand for image editing tools for amateur users[20].Our method can serve as the abstracting tool.First the input image is smoothed as shown in Fig.10(b). Then edges are detected in the smooth image. Finally,an enhanced version of the edge map is computed and added back to the smoothed image. This gives a new image with enhanced edges.An example is illustrated in Fig.10(c).

Fig.8 Comparison.

Pencil sketching.Pencil sketching is a useful image editing tool for generating non-photorealistic images[21].It can be accomplished in three steps: firstly,smooth the input image via our method, secondly,detect edges with a Canny operator,and thirdly,randomly select small edge segments with a fi xed-length according to the gradient amplitude and add them to the extracted edges.The gray-level is proportional to the gradient amplitude,and the direction is the tangent direction of the edge.Asshown in Fig.10(d),the result is visually pleasing and re fl ects the main objects in the input image.

Fig.9 Edge detection.

Fig.10 Image abstraction and pencil sketching.

6.2 Detail magni fi cation

Detail magni fi cation aims to output an image with similar content but enhanced details relative to the input image.For a given image, first we can get two layers,a smooth layer and a detail layer,via our smoothing method.Then some enhancement operation is performed on the detail layer,e.g.,using a di ff erence of Gaussian(DoG)operator.Finally,the enhanced detail layer is composed with the smooth layer.In the composed image details are magni fied. As illustrated in Fig.11,details in the resulting image are much clearer than in the input image.

6.3 Image resizing

Seam carving[22]is a popular content based image resizing method.It aims to keep the shape of the most important objects during the resizing procedure.But textures and details which are common in natural images may also be considered as salient in the contrast-based measurement.Figure 12 illustrates two examples scaled to 0.6 of the size of the input images.From Fig.12(b)we can see that the grass and wave are considered important,and the stone and sailing boat are distorted mistakenly by the original seam carving method[22].While our method can suppress the features of grass and wave, as shown in Fig.12(c),seam carving on our output can e ff ectively keep the shapes of the stone and the sailing boat.

7 Conclusions

Fig.11 Detail magni fi cation.

Fig.12 Seam carving.(a)Input.(b)Seam carving results on images in(a).(c)Seam carving results on images smoothed by our method.

This paper provides a novel image smoothing model based on a nonlocal consistency constraint on the gradient map.Nonlocal estimation provides a datadriven way to distinguish details from structural edges.The method works well for both detail removal in complex areas and feature preservation in less notable areas,and achieves more consistently smoothed results than previous methods.Moreover, as the new model can be solved efficiently by the algorithm described in this paper,it can be fl exibly embedded into various techniques,and is able to help improve the performance of many content-aware applications.

The limitation of our method is that it may fail for some mosaic images.In future we will explore proper estimation of the ideal gradient map especially for mosaic images.

Acknowledgements

This work was supported by the National Natural ScienceFoundation ofChina (Nos.61332015, 61373078,61272245,61202148,and 61103150),and the NSFC-Guangdong Joint Fund(No.U1201258).

Open Access This article is distributed under the terms of the Creative Commons Attribution License which permits any use,distribution,and reproduction in any medium,provided the original author(s)and the source are credited.

[1]Arnheim,R.Art and Visual Perception:A Psychology of the Creative Eye.University of California Press, 1954.

[2]Tomasi,C.;Manduchi,R.Bilateral fi ltering for gray and color images.In: Proceedings of the Sixth International Conference on Computer Vision,839, 1998.

[3]He,K.;Sun,J.;Tang,X.Guided image fi ltering.Lecture Notes in Computer ScienceVol.6311,1-14, 2010.

[4]Paris,S.;Hasino ff,S.W.;Kautz,J.Local Laplacian if lters:Edge-aware image processing with a Laplacian pyramid.ACM Transactions on GraphicsVol.30,No. 4,Article No.68,2011.

[5]Rudin,L.I.;Osher,S.;Fatemi,E.Nonlinear total variation based noise removal algorithms.Physica D: Nonlinear PhenomenaVol.60,Nos.1-4,259-268, 1992.

[6]Farbman,Z.;Fattal,R.;Lischinski,D.;Szeliski, R.Edgepreserving decompositionsformulti-scale tone and detail manipulation.ACM Transactions on GraphicsVol.27,No.3,Article No.67,2008.

[7]Xu,L.;Lu,C.;Xu,Y.;Jia,J.Image smoothing viaLgradient minimization.ACM Transactions on GraphicsVol.30,No.6,Article No.174,2011.

[8]Subr,K.;Soler,C.;Durand,F.Edge-preserving multiscale image decomposition based on local extrema.ACM Transactions on GraphicsVol.28,No. 5,Article No.147,2009.

[9]Steidl,G.;Teuber,T.Anisotropic smoothing using doubleorientations.LectureNotesinComputer ScienceVol.5567,477-489,2009.

[10]Kyprianidis,J.E.;Kang,H.Imageand video abstraction by coherence-enhancing fi ltering.Computer Graphics ForumVol.30,No.2,593-602,2011.

[11]Xu,L.; Yan,Q.; Xia,Y.; Jia,J.Structure extraction from texture via relative total variation.ACM Transactions on GraphicsVol.31,No.6,Article No.139,2012.

[12]Karacan,L.;Erdem,E.;Erdem,A.Structurepreserving image smoothing via region covariances.ACM Transactions on GraphicsVol.32,No.6,Article No.176,2013.

[13]Su,Z.; Luo, X.; Artusi,A.A novelimage decomposition approach and its applications.The Visual ComputerVol.29,No.10,1011-1023,2013.

[14]Li,X.-Y.;Gu,Y.;Martin,R.R.;Hu,S.-M. Mixed-domain edge-aware image manipulation.IEEE Transactions on Image ProcessingVol.22,No.5, 1915-1925,2013.

[15]Bao,L.;Song,Y.;Yang,Q.;Yuan,H.;Wang,G.Tree fi ltering: Efficientstructure-preserving smoothing with a minimum spanning tree.IEEE Transactions on Image ProcessingVol.23,No.2,555-569,2014.

[16]Zhang,Q.;Shen,X.;Xu,L.;Jia,J.Rolling guidance fi lter.Lecture Notes in Computer ScienceVol.8691, 815-830,2014.

[17]Zang,Y.;Huang,H.;Zhang,L.Efficient structureaware image smoothing by local extrema on spacefi lling curve.IEEE Transactions on Visualization and Computer GraphicsVol.20,No.9,1253-1265,2014.

[18]Buades,A.;Coll,B.;Morel,J.-M.A non-local algorithm for image denoising.In:IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Vol.2,60-65,2005.

[19]Wang,Y.;Yang,J.;Yin,W.;Zhang,Y.A new alternating minimization algorithm for total variation imagereconstruction.SIAMJournalonImaging SciencesVol.1,No.3,248-272,2008.

[20]Zhang,S.-H.;Li,X.-Y.;Hu,S.-M.;Martin,R.R. Online video stream abstraction and stylization.IEEE Transactions on MultimediaVol.13,No.6,1286-1294, 2011.

[21]Wong,F.J.;Takahashi,S.Abstracting images into continuousline artistic styles.The Visual ComputerVol.29,Nos.6-8,729-738,2013.

[22]Avidan,S.;Shamir,A.Seam carving for content-aware image resizing.ACM Transactions on GraphicsVol. 26,No.3,Article No.10,2007.

Qian Liu is currently a Ph.D.candidate in theSchoolofComputerScience and Technology at Shandong University, China.She received the bachelor’s degree from the same institution in 2010.Herresearch interestsinclude image processing,computer vision,and machine learning

Caiming Zhang is a professor and doctoral supervisor of the School of Computer Science and Technology in Shandong University.He received B.S.and M.E.degrees in computer science from Shandong University in 1982 and 1984,respectively,and a Dr.Eng.degreein computerscience from Tokyo Institute of Technology,Japan,in 1994. From 1997 to 2000,Dr.Zhang held visiting position at University of Kentucky,USA.His research interests include CAGD,CG,information visualization,and medical image processing

Qiang Guo is currently an associate professor in the School of Computer Science and Technology at Shandong University of Finance and Economics, China.He received the B.S.degree in information and computing science from Shandong University ofTechnology, China,in 2002,and the M.S.and Ph.D. degrees in computer science from Shanghai University, China,in 2005 and 2010,respectively.His research interests include image restoration,sparse representation,and defect detection.

Yuanfeng Zhou is currently an associate professor in the School of Computer Science and Technology, Shandong University.He received his master’s degree and doctor’s degree in the Department of Computer Science and Technology at Shandong University in 2005 and 2009,respectively.He worked as a post-doctor at the Department of Computer Science of the University of Hong Kong from 2009 to 2011. His interested research fields include geometric modeling, information visualization,and image processing.He has published more than 20 papers on high level conferences and journals such asGraphical Models,Computer Animation and Virtual Worlds,Computer Graphics Forum,andPaci fi c Graphics.

Other papers from this open access journal are available at no cost from http://www.springer.com/journal/41095. To submit a manuscript,please go to https://www. editorialmanager.com/cvmj.

1School of Computer Science and Technology,Shandong University,Jinan 250101,China.E-mail:yfzhou@sdu. edu.cn.

2Shandong University ofFinance and Economics, Shandong Provincial Key Laboratory of Digital Media Technology,Jinan 250014,China.

Manuscript received:2014-12-19;accepted:2015-04-02