Adaptive image compression of arbitrarily shaped objects using wavelet packets

M ULTISCALE M ODEL.S IMUL.c 2005Society for Industrial and Applied Mathematics Vol.4,No.2,pp.490–530A REVIEW OF IMAGE DENOISING ALGORITHMS,WITH A NEWONE∗A.BUADES†,B.COLL†,AND J.M.MOREL‡Abstract.The search for efficient image denoising methods is still a valid challenge at the crossing of functional analysis and statistics.In spite of the sophistication of the recently proposed methods,most algorithms have not yet attained a desirable level of applicability.All show an out-standing performance when the image model corresponds to the algorithm assumptions but fail in general and create artifacts or remove imagefine structures.The main focus of this paper is,first, to define a general mathematical and experimental methodology to compare and classify classical image denoising algorithms and,second,to propose a nonlocal means(NL-means)algorithm ad-dressing the preservation of structure in a digital image.The mathematical analysis is based on the analysis of the“method noise,”defined as the difference between a digital image and its denoised version.The NL-means algorithm is proven to be asymptotically optimal under a generic statistical image model.The denoising performance of all considered methods are compared in four ways; mathematical:asymptotic order of magnitude of the method noise under regularity assumptions; perceptual-mathematical:the algorithms artifacts and their explanation as a violation of the image model;quantitative experimental:by tables of L2distances of the denoised version to the original image.The most powerful evaluation method seems,however,to be the visualization of the method noise on natural images.The more this method noise looks like a real white noise,the better the method.Key words.image restoration,nonparametric estimation,PDE smoothingfilters,adaptive filters,frequency domainfiltersAMS subject classification.62H35DOI.10.1137/0406160241.Introduction.1.1.Digital images and noise.The need for efficient image restoration meth-ods has grown with the massive production of digital images and movies of all kinds, often taken in poor conditions.No matter how good cameras are,an image improve-ment is always desirable to extend their range of action.A digital image is generally encoded as a matrix of grey-level or color values.In the case of a movie,this matrix has three dimensions,the third one corresponding to time.Each pair(i,u(i)),where u(i)is the value at i,is called a pixel,short for“picture element.”In the case of grey-level images,i is a point on a two-dimensional(2D)grid and u(i)is a real value.In the case of classical color images,u(i)is a triplet of values for the red,green,and blue components.All of what we shall say applies identically to movies,three-dimensional(3D)images,and color or multispectral images.For the sake of simplicity in notation and display of experiments,we shall here be content with rectangular2D grey-level images.∗Received by the editors September30,2004;accepted for publication(in revised form)Janu-ary10,2005;published electronically July18,2005./journals/mms/4-2/61602.html†Universitat de les Illes Balears,Anselm Turmeda,Ctra.Valldemossa Km.7.5,07122Palma de Mallorca,Spain(vdmiabc4@uib.es,tomeu.coll@uib.es).These authors were supported by the Ministerio de Ciencia y Tecnologia under grant TIC2002-02172.During this work,thefirst author had a fellowship of the Govern de les Illes Balears for the realization of his Ph.D.thesis.‡Centre de Math´e matiques et Leurs Applications,ENS Cachan61,Av du Pr´e sident Wilson94235 Cachan,France(morel@cmla.ens-cachan.fr).This author was supported by the Centre National d’Etudes Spatiales(CNES),the Office of Naval Research under grant N00014-97-1-0839,the Direction G´e n´e rale des Armements(DGA),and the Minist`e re de la Recherche et de la Technologie.490ON IMAGE DENOISING ALGORITHMS 491The two main limitations in image accuracy are categorized as blur and noise.Blur is intrinsic to image acquisition systems,as digital images have a finite number of samples and must satisfy the Shannon–Nyquist sampling conditions [31].The second main image perturbation is noise.Each one of the pixel values u (i )is the result of a light intensity measurement,usually made by a charge coupled device (CCD)matrix coupled with a light focusing system.Each captor of the CCD is roughly a square in which the number of incoming photons is being counted for a fixed period corresponding to the obturation time.When the light source is constant,the number of photons received by each pixel fluctuates around its average in accordance with the central limit theorem.In other terms,one can expect fluctuations of order √n for n incoming photons.In addition,each captor,if not adequately cooled,receives heat spurious photons.The resulting perturbation is usually called “obscurity noise.”In a first rough approximation one can writev (i )=u (i )+n (i ),where i ∈I ,v (i )is the observed value,u (i )would be the “true”value at pixel i ,namely the one which would be observed by averaging the photon counting on a long period of time,and n (i )is the noise perturbation.As indicated,the amount of noise is signal-dependent;that is,n (i )is larger when u (i )is larger.In noise models,the normalized values of n (i )and n (j )at different pixels are assumed to be independent random variables,and one talks about “white noise.”1.2.Signal and noise ratios.A good quality photograph (for visual inspec-tion)has about 256grey-level values,where 0represents black and 255represents white.Measuring the amount of noise by its standard deviation,σ(n ),one can define the signal noise ratio (SNR)asSNR =σ(u )σ(n ),where σ(u )denotes the empirical standard deviation of u ,σ(u )= 1|I | i ∈I(u (i )−u )212,and u =1|I | i ∈I u (i )is the average grey-level value.The standard deviation of the noise can also be obtained as an empirical measurement or formally computed whenthe noise model and parameters are known.A good quality image has a standard deviation of about 60.The best way to test the effect of noise on a standard digital image is to add a Gaussian white noise,in which case n (i )are independently and identically distributed (i.i.d.)Gaussian real variables.When σ(n )=3,no visible alteration is usually ob-served.Thus,a 603 20SNR is nearly invisible.Surprisingly enough,one can add white noise up to a 21ratio and still see everything in a picture!This fact is il-lustrated in Figure 1and constitutes a major enigma of human vision.It justifies the many attempts to define convincing denoising algorithms.As we shall see,the results have been rather deceptive.Denoising algorithms see no difference between small details and noise,and therefore they remove them.In many cases,they create new distortions,and the researchers are so used to them that they have created a492 A.BUADES,B.COLL,AND J.M.MORELFig.1.A digital image with standard deviation55,the same with noise added(standard deviation3),the SNR therefore being equal to18,and the same with SNR slightly larger than2. In this second image,no alteration is visible.In the third,a conspicuous noise with standard deviation25has been added,but,surprisingly enough,all details of the original image still are visible.taxonomy of denoising artifacts:“ringing,”“blur,”“staircase effect,”“checkerboard effect,”“wavelet outliers,”etc.This fact is not quite a surprise.Indeed,to the best of our knowledge,all denoising algorithms are based on•a noise model;•a generic image smoothness model,local or global.In experimental settings,the noise model is perfectly precise.So the weak point of the algorithms is the inadequacy of the image model.All of the methods assume that the noise is oscillatory and that the image is smooth or piecewise smooth.So they try to separate the smooth or patchy part(the image)from the oscillatory one.Actually, manyfine structures in images are as oscillatory as noise is;conversely,white noise has low frequencies and therefore smooth components.Thus a separation method based on smoothness arguments only is hazardous.1.3.The“method noise.”All denoising methods depend on afiltering pa-rameter h.This parameter measures the degree offiltering applied to the image.For most methods,the parameter h depends on an estimation of the noise varianceσ2. One can define the result of a denoising method D h as a decomposition of any image v as(1.1)v=D h v+n(D h,v),where1.D h v is more smooth than v,2.n(D h,v)is the noise guessed by the method.Now it is not enough to smooth v to ensure that n(D h,v)will look like a noise. The more recent methods are actually not content with a smoothing but try to recover lost information in n(D h,v)[19,25].So the focus is on n(D h,v).Definition 1.1(method noise).Let u be a(not necessarily noisy)image and D h a denoising operator depending on h.Then we define the method noise of u as the image difference(1.2)n(D h,u)=u−D h(u).This method noise should be as similar to a white noise as possible.In addition, since we would like the original image u not to be altered by denoising methods,theON IMAGE DENOISING ALGORITHMS 493method noise should be as small as possible for the functions with the right regularity.According to the preceding discussion,four criteria can and will be taken into account in the comparison of denoising methods:•A display of typical artifacts in denoised images.•A formal computation of the method noise on smooth images,evaluating how small it is in accordance with image local smoothness.•A comparative display of the method noise of each method on real images with σ=2.5.We mentioned that a noise standard deviation smaller than 3is subliminal,and it is expected that most digitization methods allow themselves this kind of noise.•A classical comparison receipt based on noise simulation:it consists of taking a good quality image,adding Gaussian white noise with known σ,and then computing the best image recovered from the noisy one by each method.A table of L 2distances from the restored to the original can be established.The L 2distance does not provide a good quality assessment.However,it reflects well the relative performances of algorithms.On top of this,in two cases,a proof of asymptotic recovery of the image can be obtained by statistical arguments.1.4.Which methods to compare.We had to make a selection of the denoising methods we wished to compare.Here a difficulty arises,as most original methods have caused an abundant literature proposing many improvements.So we tried to get the best available version,while keeping the simple and genuine character of the original method:no hybrid method.So we shall analyze the following:1.the Gaussian smoothing model (Gabor quoted in Lindenbaum,Fischer,andBruckstein [17]),where the smoothness of u is measured by the Dirichlet integral |Du |2;2.the anisotropic filtering model (Perona and Malik [27],Alvarez,Lions,andMorel [1]);3.the Rudin–Osher–Fatemi total variation model [30]and two recently proposediterated total variation refinements [35,25];4.the Yaroslavsky neighborhood filters [41,40]and an elegant variant,theSUSAN filter (Smith and Brady [33]);5.the Wiener local empirical filter as implemented by Yaroslavsky [40];6.the translation invariant wavelet thresholding [8],a simple and performingvariant of the wavelet thresholding [10];7.DUDE,the discrete universal denoiser [24],and the UINTA,unsupervisedinformation-theoretic,adaptive filtering [3],two very recent new approaches;8.the nonlocal means (NL-means)algorithm,which we introduce here.This last algorithm is given by a simple closed formula.Let u be defined in a bounded domain Ω⊂R 2;thenNL (u )(x )=1C (x )e −(G a ∗|u (x +.)−u (y +.)|2)(0)2u (y )d y ,where x ∈Ω,G a is a Gaussian kernel of standard deviation a ,h acts as a filtering parameter,and C (x )= e −(G a ∗|u (x +.)−u (z +.)|2)(0)h 2d z is the normalizing factor.In orderto make clear the previous definition,we recall that(G a ∗|u (x +.)−u (y +.)|2)(0)= R 2G a (t )|u (x +t )−u (y +t )|2d t .494 A.BUADES,B.COLL,AND J.M.MORELThis amounts to saying that NL(u)(x),the denoised value at x,is a mean of the values of all pixels whose Gaussian neighborhood looks like the neighborhood of x.1.5.What is left.We do not draw into comparison the hybrid methods,in particular the total variation+wavelets[7,12,18].Such methods are significant improvements of the simple methods but are impossible to draw into a benchmark: their efficiency depends a lot upon the choice of wavelet dictionaries and the kind of image.Second,we do not draw into the comparison the method introduced recently by Meyer[22],whose aim it is to decompose the image into a BV part and a texture part(the so called u+v methods),and even into three terms,namely u+v+w, where u is the BV part,v is the“texture”part belonging to the dual space of BV, denoted by G,and w belongs to the Besov space˙B∞−1,∞,a space characterized by the fact that the wavelet coefficients have a uniform bound.G is proposed by Meyer as the right space to model oscillatory patterns such as textures.The main focus of this method is not yet denoising.Because of the different and more ambitious scopes of the Meyer method[2,36,26],which makes it parameter-and implementation-dependent, we could not draw it into the st but not least,let us mention the bandlet[15]and curvelet[34]transforms for image analysis.These methods also are separation methods between the geometric part and the oscillatory part of the image and intend tofind an accurate and compressed version of the geometric part. Incidentally,they may be considered as denoising methods in geometric images,as the oscillatory part then contains part of the noise.Those methods are closely related to the total variation method and to the wavelet thresholding,and we shall be content with those simpler representatives.1.6.Plan of the paper.Section2computes formally the method noise for the best elementary local smoothing methods,namely Gaussian smoothing,anisotropic smoothing(mean curvature motion),total variation minimization,and the neighbor-hoodfilters.For all of them we prove or recall the asymptotic expansion of thefilter at smooth points of the image and therefore obtain a formal expression of the method noise.This expression permits us to characterize places where thefilter performs well and where it fails.In section3,we treat the Wiener-like methods,which proceed by a soft or hard threshold on frequency or space-frequency coefficients.We examine in turn the Wiener–Fourierfilter,the Yaroslavsky local adaptive discrete cosine trans-form(DCT)-basedfilters,and the wavelet threshold method.Of course,the Gaussian smoothing belongs to both classes offilters.We also describe the universal denoiser DUDE,but we cannot draw it into the comparison,as its direct application to grey-level images is unpractical so far.(We discuss its feasibility.)Finally,we examine the UINTA algorithms whose principles stand close to the NL-means algorithm.In section5,we introduce the NL-meansfilter.This method is not easily classified in the preceding terminology,since it can work adaptively in a local or nonlocal way.We first give a proof that this algorithm is asymptotically consistent(it gives back the conditional expectation of each pixel value given an observed neighborhood)under the assumption that the image is a fairly general stationary random process.The works of Efros and Leung[13]and Levina[16]have shown that this assumption is sound for images having enough samples in each texture patch.In section6,we com-pare all algorithms from several points of view,do a performance classification,and explain why the NL-means algorithm shares the consistency properties of most of the aforementioned algorithms.ON IMAGE DENOISING ALGORITHMS4952.Local smoothingfilters.The original image u is defined in a bounded domainΩ⊂R2and denoted by u(x)for x=(x,y)∈R2.This continuous image is usually interpreted as the Shannon interpolation of a discrete grid of samples[31]and is therefore analytic.The distance between two consecutive samples will be denoted byε.The noise itself is a discrete phenomenon on the sampling grid.According to the usual screen and printing visualization practice,we do not interpolate the noise samples n i as a band limited function but rather as a piecewise constant function, constant on each pixel i and equal to n i.We write|x|=(x2+y2)12and x1.x2=x1x2+y1y2as the norm and scalar productand denote the derivatives of u by u x=∂u∂x ,u y=∂u∂y,and u xy=∂2u∂x∂y.The gradientof u is written as Du=(u x,u y)and the Laplacian of u asΔu=u xx+u yy.2.1.Gaussian smoothing.By Riesz’s theorem,image isotropic linearfiltering boils down to a convolution of the image by a linear radial kernel.The smoothing requirement is usually expressed by the positivity of the kernel.The paradigm of suchkernels is,of course,the Gaussian x→G h(x)=1(4πh2)e−|x|24h2.In that case,G h hasstandard deviation h,and the following theorem is easily seen.Theorem2.1(Gabor1960).The image method noise of the convolution with a Gaussian kernel G h isu−G h∗u=−h2Δu+o(h2).A similar result is actually valid for any positive radial kernel with bounded variance,so one can keep the Gaussian example without loss of generality.The preceding estimate is valid if h is small enough.On the other hand,the noise reduction properties depend upon the fact that the neighborhood involved in the smoothing is large enough,so that the noise gets reduced by averaging.So in the following we assume that h=kε,where k stands for the number of samples of the function u and noise n in an interval of length h.The spatial ratio k must be much larger than1to ensure a noise reduction.The effect of a Gaussian smoothing on the noise can be evaluated at a referencepixel i=0.At this pixel,G h∗n(0)=i∈IP iG h(x)n(x)d x=i∈Iε2G h(i)n i,where we recall that n(x)is being interpolated as a piecewise constant function,the P i square pixels centered in i have sizeε2,and G h(i)denotes the mean value of the function G h on the pixel i.Denoting by V ar(X)the variance of a random variable X,the additivity of variances of independent centered random variables yieldsV ar(G h∗n(0))=i ε4G h(i)2σ2 σ2ε2G h(x)2d x=ε2σ28πh2.So we have proved the following theorem.Theorem2.2.Let n(x)be a piecewise constant white noise,with n(x)=n i on each square pixel i.Assume that the n i are i.i.d.with zero mean and varianceσ2. Then the“noise residue”after a Gaussian convolution of n by G h satisfiesV ar(G h∗n(0)) ε2σ2 8πh2.496 A.BUADES,B.COLL,AND J.M.MORELIn other terms,the standard deviation of the noise,which can be interpreted as thenoise amplitude,is multiplied by εh √8π.Theorems 2.1and 2.2traduce the delicate equilibrium between noise reductionand image destruction by any linear smoothing.Denoising does not alter the image at points where it is smooth at a scale h much larger than the sampling scale ε.The first theorem tells us that the method noise of the Gaussian denoising method is zero in harmonic parts of the image.A Gaussian convolution is optimal on harmonic functions and performs instead poorly on singular parts of u ,namely edges or texture,where the Laplacian of the image is large.See Figure 3.2.2.Anisotropic filters and curvature motion.The anisotropic filter (AF)attempts to avoid the blurring effect of the Gaussian by convolving the image u at x only in the direction orthogonal to Du (x ).The idea of such a filter goes back to Perona and Malik [27]and actually again to Gabor (quoted in Lindenbaum,Fischer,and Bruckstein [17]).SetA F h u (x )=G h (t )u x +t Du (x )⊥|Du (x )|dt for x such that Du (x )=0and where (x,y )⊥=(−y,x )and G h (t )=1√2πh e −t 22h 2is theone-dimensional (1D)Gauss function with variance h 2.At points where Du (x )=0an isotropic Gaussian mean is usually applied,and the result of Theorem 2.1holds at those points.If one assumes that the original image u is twice continuously dif-ferentiable (C 2)at x ,the following theorem is easily shown by a second-order Taylor expansion.Theorem 2.3.The image method noise of an anisotropic filter A F h isu (x )−A F h u (x ) −12h 2D 2u Du ⊥|Du |,Du ⊥|Du | =−12h 2|Du |curv (u )(x ),where the relation holds when Du (x )=0.By curv (u )(x ),we denote the curvature,i.e.,the signed inverse of the radius of curvature of the level line passing by x .When Du (x )=0,this means thatcurv (u )=u xx u 2y −2u xy u x u y +u yy u 2x(u 2x +u 2y )32.This method noise is zero wherever u behaves locally like a one-variable function,u (x,y )=f (ax +by +c ).In such a case,the level line of u is locally the straight line with equation ax +by +c =0,and the gradient of f may instead be very large.In other terms,with anisotropic filtering,an edge can be maintained.On the other hand,we have to evaluate the Gaussian noise reduction.This is easily done by a 1D adaptation of Theorem 2.2.Notice that the noise on a grid is not isotropic;so the Gaussian average when Du is parallel to one coordinate axis is made roughly on √2more samples than the Gaussian average in the diagonal direction.Theorem 2.4.By anisotropic Gaussian smoothing,when εis small enough with respect to h ,the noise residue satisfiesVar (A F h (n ))≤ε√2πhσ2.ON IMAGE DENOISING ALGORITHMS 497In other terms,the standard deviation of the noise n is multiplied by a factor at mostequal to (ε√2πh)1/2,this maximal value being attained in the diagonals.Proof .Let L be the line x +t Du⊥(x )|Du (x )|passing by x ,parameterized by t ∈R ,and denote by P i ,i ∈I ,the pixels which meet L ,n (i )the noise value,constant on pixel P i ,and εi the length of the intersection of L ∩P i .Denote by g (i )the averageof G h (x +t Du⊥(x )|Du (x )|)on L ∩P i .Then one has A F h n (x )i εi n (i )g (i ).The n (i )are i.i.d.with standard variation σ,and thereforeV ar (A F h (n ))= i ε2iσ2g (i )2≤σ2max(εi ) iεi g (i )2.This yieldsVar (A F h (n ))≤√2εσ2 G h (t )2dt =ε√2πhσ2.There are many versions of A F h ,all yielding an asymptotic estimate equivalent to the one in Theorem 2.3:the famous median filter [14],an inf-sup filter on segments centered at x [5],and the clever numerical implementation of the mean curvature equation in [21].So all of those filters have in common the good preservation of edges,but they perform poorly on flat regions and are worse there than a Gaussian blur.This fact derives from the comparison of the noise reduction estimates of Theorems2.1and 2.4and is experimentally patent in Figure3.2.3.Total variation.The total variation minimization was introduced by Ru-din and Osher [29]and Rudin,Osher,and Fatemi [30].The original image u is supposed to have a simple geometric description,namely a set of connected sets,the objects,along with their smooth contours,or edges.The image is smooth inside the objects but with jumps across the boundaries.The functional space modeling these properties is BV (Ω),the space of integrable functions with finite total variation T V Ω(u )= |Du |,where Du is assumed to be a Radon measure.Given a noisy image v (x ),the above-mentioned authors proposed to recover the original image u (x )as the solution of the constrained minimization problemarg min uT V Ω(u ),(2.1)subject to the noise constraintsΩ(u (x )−v (x ))d x =0and Ω|u (x )−v (x )|2d x =σ2.The solution u must be as regular as possible in the sense of the total variation,while the difference v (x )−u (x )is treated as an error,with a prescribed energy.The constraints prescribe the right mean and variance to u −v but do not ensure that it is similar to a noise (see a thorough discussion in [22]).The preceding problem is naturally linked to the unconstrained problem arg min u T V Ω(u )+λΩ|v (x )−u (x )|2d x (2.2)498 A.BUADES,B.COLL,AND J.M.MORELfor a given Lagrange multiplierλ.The above functional is strictly convex and lower semicontinuous with respect to the weak-star topology of BV.Therefore the minimum exists,is unique,and is computable(see,e.g.,[6]).The parameterλcontrols the tradeoffbetween the regularity andfidelity terms.Asλgets smaller the weight of the regularity term increases.Thereforeλis related to the degree offiltering of the solution of the minimization problem.Let us denote by TVFλ(v)the solution of problem(2.2)for a given value ofλ.The Euler–Lagrange equation associated with the minimization problem is given by(u(x)−v(x))−12λcurv(u)(x)=0(see[29]).Thus,we have the following theorem.Theorem2.5.The image method noise of the total variation minimization(2.2) isu(x)−TVFλ(u)(x)=−12λcurv(TVFλ(u))(x).As in the anisotropic case,straight edges are maintained because of their small curvature.However,details and texture can be oversmoothed ifλis too small,as is shown in Figure3.2.4.Iterated total variation refinement.In the original total variation model the removed noise,v(x)−u(x),is treated as an error and is no longer studied.In practice,some structures and texture are present in this error.Several recent works have tried to avoid this effect[35,25].2.4.1.The Tadmor–Nezzar–Vese approach.In[35],the authors have pro-posed to use the Rudin–Osher–Fatemi model iteratively.They decompose the noisy image,v=u0+n0,by the total variation model.So taking u0to contain only ge-ometric information,they decompose by the very same model n0=u1+n1,where u1is assumed to be again a geometric part and n1contains less geometric informa-tion than n0.Iterating this process,one obtains u=u0+u1+u2+···+u k as a refined geometric part and n k as the noise residue.This strategy is in some sense close to the matching pursuit methods[20].Of course,the weight parameter in the Rudin–Osher–Fatemi model has to grow at each iteration,and the authors propose a geometric seriesλ,2λ,...,2kλ.In that way,the extraction of the geometric part n k becomes twice more taxing at each step.Then the new algorithm is as follows:1.Starting with an initial scaleλ=λ0,v=u0+n0,[u0,n0]=arg minv=u+n|Du|+λ0|v(x)−u(x)|2d x.2.Proceed with successive applications of the dyadic refinement n j=u j+1+n j+1,[u j+1,n j+1]=arg minn j=u+n|Du|+λ02j+1|n j(x)−u(x)|2d x.3.After k steps,we get the following hierarchical decomposition of v:v=u0+n0=u0+u1+n1=.....=u0+u1+···+u k+n k.ON IMAGE DENOISING ALGORITHMS 499The denoised image is given by the partial sum k j =0u j ,and n k is the noise residue.This is a multilayered decomposition of v which lies in an intermediate scale of spaces,in between BV and L 2.Some theoretical results on the convergence of this expansion are presented in [35].2.4.2.The Osher et al.approach.The second algorithm due to Osher et al.[25]also consists of an iteration of the original model.The new algorithm is as follows:1.First,solve the original total variation model u 1=arg min u ∈BV|∇u (x )|d x +λ(v (x )−u (x ))2d x to obtain the decomposition v =u 1+n 1.2.Perform a correction step to obtain u 2=arg min u ∈BV|∇u (x )|d x +λ(v (x )+n 1(x )−u (x ))2d x ,where n 1is the noise estimated by the first step.The correction step adds this first estimate of the noise to the original image and raises the decomposition v +n 1=u 2+n 2.3.Iterate:compute u k +1as a minimizer of the modified total variation mini-mization,u k +1=arg min u ∈BV|∇u (x )|d x +λ (v (x )+n k (x )−u (x ))2d x ,wherev +n k =u k +1+n k +1.Some results are presented in [25]which clarify the nature of the above sequence:•{u k }k converges monotonically in L 2to v ,the noisy image,as k →∞.•{u k }k approaches the noise-free image monotonically in the Bregman distanceassociated with the BV seminorm,at least until u ¯k −u ≤σ2,where u isthe original image and σis the standard deviation of the added noise.These two results indicate how to stop the sequence and choose u ¯k .It is enoughto proceed iteratively until the result gets noisier or the distance u ¯k −u 2gets smallerthan σ2.The new solution has more details preserved,as Figure 3shows.The above iterated denoising strategy being quite general,one can make the computations for a linear denoising operator T as well.In that case,this strategyT (v +n 1)=T (v )+T (n 1)amounts to saying that the first estimated noise n 1is filtered again and its smooth components are added back to the original,which is in fact the Tadmor–Nezzar–Vese strategy.2.5.Neighborhood filters.The previous filters are based on a notion of spatial neighborhood or proximity.Neighborhood filters instead take into account grey-level values to define neighboring pixels.In the simplest and more extreme case,the de-noised value at pixel i is an average of values at pixels which have a grey-level value close to u (i ).The grey-level neighborhood is thereforeB (i,h )={j ∈I |u (i )−h <u (j )<u (i )+h }.。

FLUENT 软件操作界面中英文对照File 文件Read 读取文件：scheme 方案journal 日志 profile 外形 Write 保存文件 Import :进入另一个运算程序 Interpolate :窜改，插入Hardcopy :复制，Batch opti ons —组选项Save layout 保存设计 Grid 网格| F 屆 Grid Define Solve i-Read► Write►Import ► Export-, Interpolate —Hardcopy...Batch Options.^Save LayoutRun...RSF...ExitDefine Models模型：solver解算器Pressure based 基于压力Den sity based基于密度末解用丁 pressure based,雀改用Censity based 岀观不苻合秦相36的摄不，请甸pres 羊WE base d Al density based 慎仆则迢.41刊卜 IS 况？北外.血OC ・EHU ^ cotipled ＞（/^ ptiaw ccupl ed simple 可这孔 & pimple ijEpiso 逞划.--■轟=Sortg 冲-丸布时制* ^jfe-5-6 1844DOden ba&ed 亘工F 吋.压聲血ptessurt ba$«i 适可于那可乐册斤"dens Ply based 把丸“河悴掏t ：至殳嗟之一.刑牛可爪門d 的创R 监當歎1一，般如人锻暮叫人丄有用 轴怀，火薩墟迭牛才H5）-0 程：yje8D8-丸布门 1叫；20GS-3-7 10-2ODQ歆；I ：谢PrflSsdrfl-Bawd Soker ^Fluflnt 它星英于压力快的束解孤便丹的圮压力修止畀法"求释旳控制片悝足标联式的，擅K 家鮮不町压縮舐Mb 对于町压砂也可旦索麟；Fk«nl 6-3 tl 前的I 板』冷孵臥 B fjS4^r«^at«d &Olvar fli Cfruptod Solvtr,的实也fltje Pr#4iurft-ea5<KJ ScFvAi 约两种虽幵方ib应理拈Fluent 氐J 眇坝犢型小的.它拈垒于曲喪红旳求聲塞，最辑的出H .也桿 艮先■那式的.丰誓■載密式冇Roz AU$hk>谏方法的初和&让Fhwrt 耳有比我甘的求IT 可压胃（说 劫謹力，們耳帕榕式淮冇琴加IF 科限闾辉，倒比还丰A 完荐匚Coupted 的算送t 对子慨站何Hh 地们足便用円匕口讷油皿购 加£未处為 性上世魅端计棒低逢刈趾.擁说的DansJty-Bjiwd Solver F ft St SiMPLEC, P 怡DE 些选以的.闪为進些ffliQl ；力修止鼻袪・不金在这种类崖的我押■中氏现泊I 建址祢匹足整用Fw»ur 护P.sed Solver 堺决昧的利底*implicit 隐式， explicit 显示Space 空间：2D , axisymmetric （转动轴）， axisymmetric swirl （漩涡转动轴）；Time 时间 :steady 定常，unsteady 非定常 Velocity formulatio n 制定速度： absolute 绝对的；relative 相对的Gradient option 梯度选择：以单元作基础；以节点作基础；以单元作梯度的最小正方形。

自适应分割的视频点云多模式帧间编码方法陈 建 1, 2廖燕俊 1王 适 2郑明魁 1, 2苏立超3摘 要 基于视频的点云压缩(Video based point cloud compression, V-PCC)为压缩动态点云提供了高效的解决方案, 但V-PCC 从三维到二维的投影使得三维帧间运动的相关性被破坏, 降低了帧间编码性能. 针对这一问题, 提出一种基于V-PCC 改进的自适应分割的视频点云多模式帧间编码方法, 并依此设计了一种新型动态点云帧间编码框架. 首先, 为实现更精准的块预测, 提出区域自适应分割的块匹配方法以寻找最佳匹配块; 其次, 为进一步提高帧间编码性能, 提出基于联合属性率失真优化(Rate distortion optimization, RDO)的多模式帧间编码方法, 以更好地提高预测精度和降低码率消耗. 实验结果表明, 提出的改进算法相较于V-PCC 实现了−22.57%的BD-BR (Bjontegaard delta bit rate)增益. 该算法特别适用于视频监控和视频会议等帧间变化不大的动态点云场景.关键词 点云压缩, 基于视频的点云压缩, 三维帧间编码, 点云分割, 率失真优化引用格式 陈建, 廖燕俊, 王适, 郑明魁, 苏立超. 自适应分割的视频点云多模式帧间编码方法. 自动化学报, 2023, 49(8):1707−1722DOI 10.16383/j.aas.c220549An Adaptive Segmentation Based Multi-mode Inter-frameCoding Method for Video Point CloudCHEN Jian 1, 2 LIAO Yan-Jun 1 WANG Kuo 2 ZHENG Ming-Kui 1, 2 SU Li-Chao 3Abstract Video based point cloud compression (V-PCC) provides an efficient solution for compressing dynamic point clouds, but the projection of V-PCC from 3D to 2D destroys the correlation of 3D inter-frame motion and re-duces the performance of inter-frame coding. To solve this problem, we proposes an adaptive segmentation based multi-mode inter-frame coding method for video point cloud to improve V-PCC, and designs a new dynamic point cloud inter-frame encoding framework. Firstly, in order to achieve more accurate block prediction, a block match-ing method based on adaptive regional segmentation is proposed to find the best matching block; Secondly, in or-der to further improve the performance of inter coding, a multi-mode inter-frame coding method based on joint at-tribute rate distortion optimization (RDO) is proposed to increase the prediction accuracy and reduce the bit rate consumption. Experimental results show that the improved algorithm proposed in this paper achieves −22.57%Bjontegaard delta bit rate (BD-BR) gain compared with V-PCC. The algorithm is especially suitable for dynamic point cloud scenes with little change between frames, such as video surveillance and video conference.Key words Point cloud compression, video-based point cloud compresion (V-PCC), 3D inter-frame coding, point cloud segmentation, rate distortion optimization (RDO)Citation Chen Jian, Liao Yan-Jun, Wang Kuo, Zheng Ming-Kui, Su Li-Chao. An adaptive segmentation based multi-mode inter-frame coding method for video point cloud. Acta Automatica Sinica , 2023, 49(8): 1707−1722点云由三维空间中一组具有几何和属性信息的点集构成, 通常依据点的疏密可划分为稀疏点云和密集点云[1]. 通过相机矩阵或高精度激光雷达采集的密集点云结合VR 头盔可在三维空间将对象或场景进行6自由度场景还原, 相较于全景视频拥有更真实的视觉体验, 在虚拟现实、增强现实和三维物体捕获领域被广泛应用[2−3]. 通过激光雷达反射光束经光电处理后收集得到的稀疏点云可生成环境地收稿日期 2022-07-05 录用日期 2022-11-29Manuscript received July 5, 2022; accepted November 29, 2022国家自然科学基金(62001117, 61902071), 福建省自然科学基金(2020J01466), 中国福建光电信息科学与技术创新实验室(闽都创新实验室) (2021ZR151), 超低延时视频编码芯片及其产业化(2020年福建省教育厅产学研专项)资助Supported by National Natural Science Foundation of China (62001117, 61902071), Fujian Natural Science Foundation (2020J01466), Fujian Science & Technology Innovation Laborat-ory for Optoelectronic Information of China (2021ZR151), and Ultra-low Latency Video Coding Chip and its Industrialization (2020 Special Project of Fujian Provincial Education Depart-ment for Industry-University Research)本文责任编委 刘成林Recommended by Associate Editor LIU Cheng-Lin1. 福州大学先进制造学院 泉州 3622512. 福州大学物理与信息工程学院 福州 3501163. 福州大学计算机与大数据学院/软件学院 福州 3501161. School of Advanced Manufacturing, Fuzhou University, Quan-zhou 3622512. College of Physics and Information Engineer-ing, Fuzhou University, Fuzhou 3501163. College of Com-puter and Data Science/College of Software, Fuzhou University,Fuzhou 350116第 49 卷 第 8 期自 动 化 学 报Vol. 49, No. 82023 年 8 月ACTA AUTOMATICA SINICAAugust, 2023图, 以实现空间定位与目标检测等功能, 业已应用于自动驾驶、无人机以及智能机器人等场景[4−7]. 但相较于二维图像, 点云在存储与传输中的比特消耗显著增加[8], 以经典的8i 动态点云数据集[9]为例, 在每秒30帧时的传输码率高达180 MB/s, 因此动态点云压缩是对点云进行高效传输和处理的前提.N ×N ×N 3×3×3为了实现高效的动态点云压缩, 近年来, 一些工作首先在三维上进行帧间运动估计与补偿, 以充分利用不同帧之间的时间相关性. 其中, Kammerl 等[10]首先提出通过构建八叉树对相邻帧进行帧间差异编码, 实现了相较于八叉树帧内编码方法的性能提升; Thanou 等[11]则提出将点云帧经过八叉树划分后, 利用谱图小波变换将三维上的帧间运动估计转换为连续图之间的特征匹配问题. 然而, 上述方法对帧间像素的运动矢量估计不够准确. 为了实现更精确的运动矢量估计, Queiroz 等[12]提出一种基于运动补偿的动态点云编码器, 将点云体素化后进行块划分, 依据块相关性确定帧内与帧间编码模式, 对帧间编码块使用提出的平移运动模型改善预测误差; Mekuria 等[13]则提出将点云均匀分割为 的块, 之后将帧间对应块使用迭代最近点(Iterative closest point, ICP)[14]进行运动估计,以进一步提高帧间预测精度; Santos 等[15]提出使用类似于2D 视频编码器的N 步搜索算法(N-step search, NSS), 在 的三维块区域中迭代寻找帧间对应块, 而后通过配准实现帧间编码. 然而,上述方法实现的块分割破坏了块间运动相关性, 帧间压缩性能没有显著提升.为了进一步提高动态点云压缩性能, 一些工作通过将三维点云投影到二维平面后组成二维视频序列, 而后利用二维视频编码器中成熟的运动预测与补偿算法, 实现三维点云帧间预测. 其中, Lasserre 等[16]提出基于八叉树的方法将三维点云投影至二维平面, 之后用二维视频编码器进行帧间编码; Bud-agavi 等[17]则通过对三维上的点进行二维平面上的排序, 组成二维视频序列后利用高效视频编码器(High efficiency video coding, HEVC)进行编码.上述方法在三维到二维投影的过程中破坏了三维点间联系, 重构质量并不理想. 为改善投影后的点间联系, Schwarz 等[18]通过法线将点映射于圆柱体上确保点间联系, 对圆柱面展开图使用二维视频编码以提高性能. 但在圆柱上的投影使得部分点因遮挡丢失, 影响重构精度. 为尽可能保留投影点数, Mam-mou 等[19]根据点云法线方向与点间距离的位置关系, 将点云划分为若干Patch, 通过对Patch 进行二维平面的排列以减少点数损失, 进一步提高了重构质量.基于Patch 投影后使用2D 视频编码器进行编码, 以实现二维上的帧间运动预测与补偿的思路取得了最优的性能, 被运动图像专家组(Moving pic-ture experts group, MPEG)正在进行的基于视频的点云压缩(Video-based point cloud compres-sion, V-PCC)标准[20]所采纳, 但将Patch 从三维到二维的投影导致三维运动信息无法被有效利用, 使得帧间压缩性能提升受到限制. 针对这一问题, 一些工作尝试在V-PCC 基础上实现三维帧间预测,其中, Li 等[21]提出了一种三维到二维的运动模型,利用V-PCC 中的几何与辅助信息推导二维运动矢量以实现帧间压缩性能改善, 但通过二维推导得到的三维运动信息并不完整, 导致运动估计不够准确.Kim 等[22]提出通过点云帧间差值确定帧内帧与预测帧, 帧内帧用V-PCC 进行帧内编码, 预测帧依据前帧点云进行运动估计后对残差进行编码以实现运动补偿, 但残差编码依旧消耗大量比特. 上述方法均在V-PCC 基础上实现了三维点云的帧间预测,但无论是基于二维的三维运动推导还是帧间残差的编码, 性能改善都比较有限.在本文的工作中, 首先, 为了改善三维上实现运动估计与补偿中, 块分割可能导致的运动相关性被破坏的问题, 本文引入了KD 树(K-dimension tree,KD Tree)思想, 通过迭代进行逐层深入的匹配块分割, 并定义分割块匹配度函数以自适应确定分割的迭代截止深度, 进而实现了更精准的运动块搜索;另外, 针对V-PCC 中二维投影导致三维运动信息无法被有效利用的问题, 本文提出在三维上通过匹配块的几何与颜色两种属性进行相似性判别, 并设计率失真优化(Rate distortion optimization, RDO)模型对匹配块分类后进行多模式的帧间编码, 实现了帧间预测性能的进一步改善. 实验表明, 本文提出的自适应分割的视频点云多模式帧间编码方法在与最新的V-PCC 测试软件和相关文献的方法对比中均取得了BD-BR (Bjontegaard delta bit rate)的负增益. 本文的主要贡献如下:1)提出了针对动态点云的新型三维帧间编码框架, 通过自动编码模式判定、区域自适应分割、联合属性率失真优化的多模式帧间编码、结合V-PCC 实现了帧间编码性能的提升;2)提出了一种区域自适应分割的块匹配方法,以寻找帧间预测的最佳匹配块, 从而改善了均匀分割和传统分割算法导致运动相关性被破坏的问题;3)提出了一种基于联合属性率失真优化模型的多模式帧间编码方法, 在改善预测精度的同时显著减少了帧间编码比特.1 基于视频的点云压缩及其问题分析本文所提出的算法主要在V-PCC 基础上进行1708自 动 化 学 报49 卷三维帧间预测改进, 因此本节对V-PCC 的主要技术做简要介绍, 并分析其不足之处. 其中, V-PCC 编码框架如图1所示.图 1 V-PCC 编码器框架Fig. 1 V-PCC encoder diagram首先, V-PCC 计算3D 点云中每个点的法线以确定最适合的投影面, 进而将点云分割为多个Patch [23].接着, 依据对应Patch 的位置信息, 将其在二维平面上进行紧凑排列以完成对Patch 的打包. 之后,依据打包结果在二维上生成对应的图像, 并使用了几何图、属性图和占用图分别表示各点的坐标、颜色及占用信息. 鉴于Patch 在二维的排列不可避免地存在空像素点, 因此需要占用图表示像素点的占用与否[24]; 由于三维到二维的投影会丢失一个维度坐标信息, 因此使用几何图将该信息用深度形式进行表示; 为了实现动态点云的可视化, 还需要一个属性图用于表示投影点的颜色属性信息. 最后, 为了提高视频编码器的压缩性能, 对属性图和几何图的空像素进行了填充和平滑处理以减少高频分量; 同时, 为了缓解重构点云在Patch 边界可能存在的重叠或伪影, 对重构点云进行几何和属性上的平滑滤波处理[25]. 通过上述步骤得到二维视频序列后, 引入二维视频编码器(如HEVC)对视频序列进行编码.V-PCC 将动态点云帧进行二维投影后, 利用成熟的二维视频编码技术实现了动态点云压缩性能的提升. 但是, V-PCC 投影过程将连续的三维物体分割为多个二维子块, 丢失了三维上的运动信息,使得三维动态点云中存在的时间冗余无法被有效利用. 为了直观展示投影过程导致的运动信息丢失,图2以Longdress 数据集为例, 展示了第1 053和第1 054两相邻帧使用V-PCC 投影得到的属性图.观察图2可以发现, 部分在三维上高度相似的区域,如图中标记位置1、2与3所对应Patch, 经二维投影后呈现出完全不同的分布, 该结果使得二维视频编码器中帧间预测效果受到限制, 不利于压缩性能的进一步提升.2 改进的动态点云三维帧间编码为了在V-PCC 基础上进一步降低动态点云的时间冗余性, 在三维上进行帧间预测和补偿以最小化帧间误差, 本文提出了一个在V-PCC 基础上改进的针对动态点云的三维帧间编码框架, 如图3所示. 下面对该框架基本流程进行介绍.首先, 在编码端, 我们将输入的点云序列通过模块(a)进行编码模式判定, 以划分帧内帧与预测帧. 其思想与二维视频编码器类似, 将动态点云划分为多组具有运动相似性的图像组(Group of pic-tures, GOP)以分别进行编码. 其中图像组中的第一帧为帧内帧, 后续帧均为预测帧, 帧内帧直接通过V-PCC 进行帧内编码; 预测帧则通过帧间预测方式进行编码. 合理的GOP 划分表明当前图像组内各相邻帧均具有较高运动相关性, 因此可最优化匹配块预测效果以减少直接编码比特消耗, 进而提高整体帧间编码性能. 受文献[22]启发, 本文通过对当前帧与上一帧参考点云进行几何相似度判定,以确定当前帧的编码方式进行灵活的图像组划分.如式(1)所示.Longdress 第 1 053 帧三维示例Longdress 第 1 054 帧三维示例Longdress 第 1 053 帧 V-PCC投影属性图Longdress 第 1 054 帧 V-PCC投影属性图11223图 2 V-PCC 从三维到二维投影(属性图)Fig. 2 V-PCC projection from 3D to2D (Attribute map)8 期陈建等: 自适应分割的视频点云多模式帧间编码方法1709cur ref E Gcur,ref Ωmode mode E O R 其中, 为当前帧点云, 为前帧参考点云, 表示两相邻帧点云的几何偏差, 为编码模式判定阈值. 当 值为1时表示当前帧差异较大, 应当进行帧内模式编码; 当 值为0时则表示两帧具有较大相似性, 应当进行帧间模式编码. 另外, 在动态点云重构误差 的计算中, 使用原始点云 中各点与重构点云 在几何和属性上的误差均值表示, 即式(2)所示.N O O (i )R (i ′)i i ′E O,R O R 其中, 为原始点云点数, 和 分别表示原始点云第 点与对应重构点云 点的几何或属性值, 即为原始点云 与重构点云 间误差值.N ×N ×N K 接着, 在进行帧间编码模式判断后, 通过模块(b)进行预测帧的区域自适应块分割. 块分割的目的在于寻找具有帧间运动一致性的匹配块以进行运动预测和补偿. 不同于 等分或 均值聚类, 所提出的基于KD 树思想的区域自适应块匹配从点云质心、包围盒和点数三个角度, 判断分割块的帧间运动程度以进行分割深度的自适应判定,最终实现最佳匹配块搜索.之后, 对于分割得到的匹配块, 通过模块(c)进行基于联合属性率失真优化的帧间预测. 在该模块中, 我们通过帧间块的几何与颜色属性联合差异度,结合率失真优化模型对匹配块进行分类, 分为几乎无差异的完全近似块(Absolute similar block, ASB)、差异较少的相对近似块(Relative similar block,RSB)以及存在较大差异的非近似块(Non similar block, NSB). 完全近似块认为帧间误差可忽略不计, 仅需记录参考块的位置信息; 而相对近似块则表示存在一定帧间误差, 但可通过ICP 配准和属性补偿来改善几何与属性预测误差, 因此除了块位置信息, 还需记录预测与补偿信息; 而对于非近似块,则认为无法实现有效的帧间预测, 因此通过融合后使用帧内编码器进行编码.最后, 在完成帧间模式分类后, 为了在编码端进行当前帧的重构以作为下一帧匹配块搜索的参考帧, 通过模块(d)对相对近似块进行几何预测与属性补偿, 而后将几何预测与属性补偿后的相对近似块、完全近似块、非近似块进行融合得到重构帧. 为了在解码端实现帧间重构, 首先需要组合预测帧中的所有非近似块, 经由模块(e)的V-PCC 编码器进行帧内编码, 并且, 还需要对完全近似块的位置信息、相对近似块的位置与预测补偿信息通过模块(f)进行熵编码以实现完整的帧间编码流程.至此, 整体框架流程介绍完毕, 在接下来的第3节与第4节中, 我们将对本文提出的区域自适应分割的块匹配算法与联合属性率失真优化的多模式帧间编码方法进行更为详细的介绍, 并在第5节通过实验分析进行算法性能测试.3 区域自适应分割的块匹配N B j cur j ref j ∆E cur j ,ref j 相较于二维视频序列, 动态点云存在大量空像素区域, 帧间点数也往往不同. 因此, 对一定区域内的点集进行帧间运动估计时, 如何准确找到匹配的邻帧点集是一个难点. 假设对当前帧进行帧间预测时共分割为 个子点云块, 第 块子点云 与其对应参考帧匹配块 间存在几何与属性综合误差 . 由于重构的预测帧实质上是通过组合相应的参考帧匹配块而估计得到的, 因此精准的帧间块匹配尝试最小化每个分割块的估计误差,以提高预测帧整体预测精度, 如式(3)所示:图 3 改进的三维帧间编码框架Fig. 3 Improved 3D inter-frame coding framework1710自 动 化 学 报49 卷K K N N ×N ×N 为了充分利用帧间相关性以降低时间冗余, 一些工作尝试对点云进行分割后寻找最佳匹配块以实现帧间预测. Mekuria 等[13]将动态点云划分为若干个大小相同的宏块, 依据帧间块点数和颜色进行相似性判断, 对相似块使用迭代最近点算法计算刚性变换矩阵以实现帧间预测. 然而, 当区域分割得到的对应匹配块间存在较大偏差时, 预测效果不佳.为了减少匹配块误差以提高预测精度, Xu 等[26]提出使用 均值聚类将点云分为多个簇, 在几何上通过ICP 实现运动预测, 在属性上则使用基于图傅里叶变换的模型进行运动矢量估计. 但基于 均值聚类的点云簇分割仅在预测帧中进行, 没有考虑帧间块运动相关性, 匹配精度提升受到限制. 为了进一步提高匹配精度, Santos 等[15]受到二维视频编码器中 步搜索算法的启发, 提出了一种3D-NSS 方法实现三维上的匹配块搜索, 将点云分割为 的宏块后进行3D-NSS 以搜索最优匹配块, 而后通过ICP 进行帧间预测.K 上述分割方法均实现了有效的块匹配, 但是,基于宏块的均匀块分割与基于传统 均值聚类的块划分均没有考虑分割块间可能存在的运动连续性, 在分割上不够灵活. 具体表现为分割块过大无法保证块间匹配性, 过小又往往导致已经具有运动连续性的预测块被过度细化, 出现相同运动预测信息的冗余编码. 为了避免上述问题, 本文引入KD 树思想, 提出了一种区域自适应分割算法, 该算法通过迭代进行逐层深入的二分类划分, 对各分割深度下块的运动性质与匹配程度进行分析, 确定是否需要继续分割以实现精准运动块匹配. 算法基本思想如图4所示, 若满足分割条件则继续进行二分类划分, 否则停止分割.Ψ(l,n )其中, 准确判断当前分割区域是否满足运动连续性条件下的帧间运动, 是避免过度分割以实现精准的运动块搜索的关键, 本文通过定义分割块匹配函数来确定截止深度, 如式(4)所示:ρ(n )=max [sign (n −N D ),0]n N D ρ(n )=1ξ(l )l 其中, 为点数判定函数,当点数 大于最小分割块点数阈值 时, ,表示满足深入分割的最小点数要求, 否则强制截止; 为当前深度 下的块运动偏移度, 通过衡量匹配块间的运动变化分析是否需要进一步分割.ξξw ξu 提出的 函数分别通过帧间质心偏移度 估计匹配块间运动幅度, 帧间包围盒偏移度 进行匹ξn ξw ξu ξn T l ξ(l )配块间几何运动一致性判定, 点数偏移度 进行点云分布密度验证, 最后通过 、 与 累加值与分割截止阈值 的比值来整体衡量当前块的运动程度与一致性. 即对于当前分割深度 , 可进一步细化为式(5):其中,w cur w ref u cur u ref n cur n ref l P Max P Min 并且, 、 、 、 、与分别表示当前分割深度下该区域与其前帧对应区域的质心、包围盒与点数,和分别为当前块对角线对应点.ρ(n )=1ξ(l)lξξξξ在的前提下,值反映当前KD 树分割深度下该区域点云的帧间运动情况.值越大帧间运动越显著,当值大于1时,需对运动块进行帧间运动补偿,如果继续分割将导致块的运动一致性被破坏或帧间对应块无法实现有效匹配,从而导致帧间预测失败;值越小说明当前区域点云整体运动变化越小,当值小于1时,需进一步分割寻找可能存在的运动区域.l +1d 对于需要进一步分割的点云块,为了尽可能均匀分割以避免分割后匹配块间误差过大, 将待分割匹配块质心均值作为分割点, 通过以包围盒最长边作为分割面来确定 深度下的分割轴 , 分割轴l = 0l = 1l = 2l = m l = m + 1条件满足, 继续分割条件不满足, 停止分割图 4 区域自适应分割块匹配方法示意图Fig. 4 Schematic diagram of region adaptive segmentation based block matching method8 期陈建等: 自适应分割的视频点云多模式帧间编码方法1711如式(6)所示:Edge d,max Edge d,min d 其中, 和 分别为待分割块在 维度的最大值和最小值.总结上文所述, 我们将提出的区域自适应分割的块匹配算法归纳为算法1. 算法 1. 区域自适应分割的块匹配cur ref 输入. 当前帧点云 与前帧参考点云 输出. 当前帧与参考帧对应匹配块j =1N B 1) For to Do l =02) 初始化分割深度 ;3) Docur j ref j 4) 选取待分割块 和对应待匹配块 ;w u n 5) 计算质心 、包围盒 与块点数 ;ξ(l )6) 根据式(5)计算运动块偏移度 ;ρ(n )7) 根据函数 判定当前分割块点数;Ψ(l,n )8) 根据式(4)计算分割块匹配函数 ;Ψ(l,n )9) If 满足匹配块分割条件:d 10) 根据式(6)确定分割轴 ;cur j ref j 11) 对 与 进行分割;12) 保存分割结果;l +113) 分割深度 ;Ψ(l,n )14) Else 不满足匹配块分割条件:15) 块分割截止;16) 保存匹配块;17) End of if18) While 所有块均满足截止条件;19) End of for图5展示了本文提出的区域自适应分割的块匹配算法对帧Longdress_0536和其参考帧Longdress_0535进行分割后的块匹配结果. 在该序列当前帧下, 人物进行上半身的侧身动作. 观察图5可发现,在运动变化较大的人物上半身, 算法在寻找到较大的对应匹配块后即不再分割; 而人物下半身运动平缓, 算法自适应提高分割深度以实现帧间匹配块的精确搜索, 因而下半身的分块数目大于上半身.4 联合属性率失真优化的多模式帧间编码P Q在动态点云的帧间编码中, 常对相邻帧进行块分割或聚类后依据匹配块相似性实现帧间预测, 并利用补偿算法减少预测块误差以改善帧间编码质量. 其中迭代最近点算法常用于帧间运动估计中,其通过迭代更新待配准点云 相较于目标点云 S t E (S,t )间的旋转矩阵 和平移向量 , 进而实现误差 最小化, 如式(7)所示:N p p i P i q i ′Q p i 其中 为待配准点云点数, 为待配准点云 的第 个点, 为目标点云 中与 相对应的点.但是, 完全依据ICP 配准进行动态点云的三维帧间预测存在两个问题: 首先, ICP 仅在预测块上逼近几何误差的最小化而没考虑到颜色属性偏差引起的匹配块差异, 影响了整体预测精度; 其次, 从率失真角度分析, 对运动变化极小的匹配块进行ICP 配准实现的运动估计是非必要的, 该操作很难改善失真且会增加帧间编码比特消耗.为改善上述问题, 提出了联合属性率失真优化的多模式帧间编码方法. 提出的方法首先在确保几何预测精度的同时, 充分考虑了可能的属性变化导致的预测精度下降问题, 而后通过率失真优化模型,对块依据率失真代价函数得到的最优解进行分类后, 应用不同的编码策略以优化帧间编码方案, 旨在有限的码率约束下最小化编码失真, 即式(8)所示:R j D j j N B R C λ其中, 和 分别表示第 个点云块的编码码率和对应的失真; 是当前帧编码块总数; 表示总码率预算.引入拉格朗日乘子 ,式(8)所示的带约束优化问题可以转换为无约束的最优化问题, 即式(9)所示:当前帧分割可视化当前帧分割效果参考帧分割效果图 5 区域自适应分割的块匹配方法分割示例Fig. 5 Example of block matching method based onadaptive regional segmentation1712自 动 化 学 报49 卷。

图像检索（imageretrieval）-13-Smooth-AP：Smoothingth。

Smooth-AP: Smoothing the Path Towards Large-Scale Image RetrievalAbstract优化⼀个基于排名的度量，⽐如Average Precision(AP)，是出了名的具有挑战性，因为它是不可微的，因此不能直接使⽤梯度下降⽅法进⾏优化。

为此，我们引⼊了⼀个优化AP平滑近似的⽬标，称为Smooth-AP。

Smooth-AP是⼀个即插即⽤的⽬标函数，允许对深度⽹络进⾏端到端训练，实现简单⽽优雅。

我们还分析了为什么直接优化基于AP度量的排名⽐其他深度度量学习损失更有好处。

我们将Smooth-AP应⽤于标准检索基准:Stanford Online products和VehicleID，也评估更⼤规模的数据集:INaturalist⽤于细粒度类别检索，VGGFace2和IJB-C⽤于⼈脸检索。

在所有情况下，我们都改善了最先进的技术的性能，特别是对于更⼤规模的数据集，从⽽证明了Smooth-AP在真实场景中的有效性和可扩展性。

1 Introduction本⽂的⽬标是提⾼“实例查询”的性能，其任务是:给定⼀个查询图像，根据实例与查询的相关性对检索集中的所有实例进⾏排序。

例如，假设你有⼀张朋友或家⼈的照⽚，想要在你的⼤型智能⼿机图⽚集合中搜索那个⼈的所有图⽚;或者在照⽚授权⽹站上，您希望从⼀张照⽚开始查找特定建筑或对象的所有照⽚。

在这些⽤例中，⾼recall是⾮常重要的，不同于“Google Lens”应⽤程序从图像中识别⼀个物体，其中只有⼀个“hit”(匹配)就⾜够了。

检索质量的基准度量是Average Precision(AP)(或其⼴义变体，Normalized Discounted Cumulative Gain，其中包括⾮⼆进制相关性判断)。

随着深度神经⽹络的兴起，端到端训练已经成为解决特定视觉任务的实际选择。

Digital Image Processing Using MATLAB®Second EditionRafael C. GonzalezUniversity of TennesseeRichard E. WoodsMedData InteractiveSteven L. EddinsThe MathWorks, Inc.Gatesmark Publishing®A Division of Gatesmark,® LLCLibrary of Congress Cataloging-in-Publication Data on FileLibrary of Congress Control Number: 2009902793© 2009 by Gatesmark, LLCAll rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, without written permission from the publisher.Gatesmark Publishing ® is a registered trademark of Gatesmark, LLC, .Gatesmark ® is a registered trademark of Gatesmark, LLC, .MATLAB ® is a registered trademark of The MathWorks, Inc., 3 Apple Hill Drive, Natick, MA 01760-2098The authors and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The authors and publisher shall not be liable in any event for incidental or consequential damages with, or arising out of, the furnishing, performance, or use of these programs.Printed in the United States of America10 9 8 7 6 5 4 3 2 1ISBN 978-0-9820854-0-0Gatesmark Publishing A Division of Gatesmark, LLCPrefaceThis edition of Digital Image Processing Using MATLAB is a major revision ofthe book. As in the previous edition, the focus of the book is based on the factthat solutions to problems in the field of digital image processing generallyrequire e xtensive experimental work involving software simulation and testingwith large sets of sample images. Although algorithm development typically isbased on theoretical underpinnings, the actual implementation of these algorithmsalmost always r equires parameter estimation and, frequently, algorithm revisionand comparison of candidate solutions. Thus, selection of a flexible, comprehen-sive, and well-documented software development environment is a key factor thathas important i mplications in the cost, development time, and portability of imageprocessing solutions.Despite its importance, surprisingly little has been written on this aspect of thefield in the form of textbook material dealing with both theoretical principles andsoftware implementation of digital image processing concepts. The first edition ofthis book was written in 2004 to meet just this need. This new edition of the bookcontinues the same focus. Its main objective is to provide a foundation for imple-menting image processing algorithms using modern software tools. A complemen-tary objective is that the book be self-contained and easily readable by individualswith a basic background in digital image processing, mathematical analysis, andcomputer programming, all at a level typical of that found in a j unior/senior cur-riculum in a technical discipline. Rudimentary knowledge of M ATLAB also is de-sirable.To achieve these objectives, we felt that two key ingredients were needed. Thefirst was to select image processing material that is representative of material cov-ered in a formal course of instruction in this field. The second was to select soft-ware tools that are well supported and documented, and which have a wide rangeof applications in the “real” world.To meet the first objective, most of the theoretical concepts in the followingchapters were selected from Digital Image Processing by Gonzalez and Woods,which has been the choice introductory textbook used by educators all over theworld for over three decades. The software tools selected are from the MATLAB®Image Processing Toolbox™, which similarly occupies a position of eminence inboth education and industrial applications. A basic strategy followed in the prepa-ration of the current edition was to continue providing a seamless integration ofwell-established theoretical concepts and their implementation using state-of-the-art software tools.The book is organized along the same lines as Digital Image Processing. Inthis way, the reader has easy access to a more detailed treatment of all the imageprocessing concepts discussed here, as well as an up-to-date set of references forfurther reading. Following this approach made it possible to present theoreticalmaterial in a succinct manner and thus we were able to maintain a focus on thesoftware implementation aspects of image processing problem solutions. Becauseit works in the MATLAB computing environment, the Image Processing Toolboxoffers some significant advantages, not only in the breadth of its computationalxiiitools, but also because it is supported under most operating systems in use today. Aunique feature of this book is its emphasis on showing how to develop new code toenhance existing MATLAB and toolbox functionality. This is an important featurein an area such as image processing, which, as noted earlier, is characterized by theneed for extensive algorithm development and experimental work.After an introduction to the fundamentals of MATLAB functions and program-ming, the book proceeds to address the mainstream areas of image p rocessing. Themajor areas covered include intensity transformations, fuzzy image processing, lin-ear and nonlinear spatial filtering, the frequency domain filtering, image restora-tion and reconstruction, geometric transformations and image registration, colorimage processing, wavelets, image data compression, morphological image pro-cessing, image segmentation, region and boundary representation and description,and object recognition. This material is complemented by numerous illustrationsof how to solve image processing problems using MATLAB and toolbox func-tions. In cases where a function did not exist, a new function was written and docu-mented as part of the instructional focus of the book. Over 120 new functions areincluded in the following chapters. These functions increase the scope of the ImageProcessing Toolbox by approximately 40% and also serve the important purposeof further illustrating how to implement new image processing software solutions.The material is presented in textbook format, not as a software manual.Although the book is self-contained, we have established a companion web site(see Section 1.5) designed to provide support in a number of areas. For studentsfollowing a formal course of study or individuals embarked on a program of selfstudy, the site contains tutorials and reviews on background material, as well asprojects and image databases, including all images in the book. For instructors, thesite contains classroom presentation materials that include PowerPoint slides of allthe images and graphics used in the book. Individuals already familiar with imageprocessing and toolbox fundamentals will find the site a useful place for up-to-datereferences, new implementation techniques, and a host of other support materialnot easily found elsewhere. All purchasers of new books are eligible to downloadexecutable files of all the new functions developed in the text at no cost.As is true of most writing efforts of this nature, progress continues after workon the manuscript stops. For this reason, we devoted significant effort to the selec-tion of material that we believe is fundamental, and whose value is likely to remainapplicable in a rapidly evolving body of knowledge. We trust that readers of thebook will benefit from this effort and thus find the material timely and useful intheir work.R afael C. G onzalezR iChaRd e. W oodss teven l. e ddins xiv。

FINAL PROGRAMTHE 2007 ACM SIGAPPSYMPOSIUM ON APPLIED COMPUTING/conferences/sac/sac2007Seoul, Korea March 11 - 15, 2007Organizing CommitteeRoger L. Wainwright Hisham M. Haddad Sung Y. ShinSascha Ossowski Ronaldo MenezesLorie M. Liebrock Mathew J. Palakal Jaeyoung Choi Tei-Wei Kuo Jiman HongSeong Tae Jhang Yookun Cho Yong Wan KooH OSTED BYSeoul National University, Seoul, Korea Suwon University, Gyeonggi-do, KoreaSPONSORED BYSAC 2007 I NTRODUCTIONSAC 2007 is a premier international conference on applied com-puting and technology. Attendees have the opportunity to hear from expert practitioners and researchers about the latest trends in research and development in their fields. SAC 2007 features 2 keynote speakers on Monday and Wednesday, from 8:30 to 10:00. The symposium consists of Tutorial and Technical programs. The Tutorial Program offers 3 half-day tutorials on Sunday March 11, 2007, starting at 9:00am. The Technical Program offers 38 tracks on a wide number of different research topics, which run from Monday March 12 through Thursday March 15, 2007. Regular sessions start at 8:30am and end at 5:00pm in 4 parallel sessions. Honorable ChairsYookun Cho, Honorable Symposium ChairSeoul National University, KoreaYong Wan Koo, Honorable Program ChairUniversity of Suwon, KoreaOrganizing CommitteeRoger L. Wainwright, Symposium ChairUniversity of Tulsa, USAHisham M. Haddad, Symposium Chair, Treasurer, Registrar Kennesaw State University, USASung Y. Shin, Symposium ChairSouth Dakota State University, USASascha Ossowski, Program ChairUniversity Rey Juan Carlos, Madrid, SpainRonaldo Menezes, Program ChairFlorida Institute of Technology, Melbourne, FloridaJaeyoung Choi, Tutorials ChairSoongsil University, KoreaTei-Wei Kuo, Tutorials ChairNational Taiwan University, ChinaMathew J. Palakal, Poster ChairIndiana University Purdue University, USALorie M. Liebrock, Publication ChairNew Mexico Institute of Mining and Technology, USAJiman Hong,Local Organization ChairKwangwoon University, KoreaSeong Tae Jhang,Local Organization ChairUniversity of Suwon, KoreaSAC 2007 Track OrganizersArtificial Intelligence, Computational Logic, and Image Analysis (AI)C.C. Hung, School of Computing and Soft. Eng., USAAgostinho Rosa, LaSEEB –ISR – IST, PortugalAdvances in Spatial and Image-based Information Systems (ASIIS)Kokou Yetongnon, Bourgogne University, FranceChristophe Claramunt, Naval Academy Research Institute, France Richard Chbeir, Bourgogne University, FranceKi-Joune Li, Prusan National University, KoreaAgents, Interactions, Mobility and Systems (AIMS)Marcin Paprzycki, SWPS and IBS PAN, PolandCostin Badica, University of Craiova, RomaniaMaria Ganzha, EUH-E and IBS PAN, PolandAlex Yung-Chuan Lee, Southern Illinois University, USAShahram Rahimi, Southern Illinois University, USAAutonomic Computing (AC)Umesh Bellur, Indian Institute of Technology, IndiaSheikh Iqbal Ahamed, Marquette University, USABioinformatics (BIO)Mathew J. Palakal, Indiana University Purdue University, USALi Liao, University of Delaware, USAComputer Applications in Health Care (CACH)Valentin Masero, University of Extremadura, SpainPierre Collet, Université du Littoral (ULCO), France Computer Ethics and Human Values (CEHV)Kenneth E. Himma, Seattle Pacific University, USAKeith W. Miller, University of Illinois at Springfield, USADavid S. Preston, University of East London, UKComputer Forensics (CF)Brajendra Panda, University of Arkansas, USAKamesh Namuduri, Wichita State University, USAComputer Networks (CN)Mario Freire, University of Beira Interior, PortugalTeresa Vazao, INESC ID/IST, PortugalEdmundo Monteiro, University of Coimbra, PortugalManuela Pereira, University of Beira Interior, PortugalComputer Security (SEC)Giampaolo Bella, Universita' di Catania, ItalyPeter Ryan, University of Newcastle upon Tyne, UKComputer-aided Law and Advanced Technologies (CLAT) Giovanni Sartor, University of Bologna, ItalyAlessandra Villecco Bettelli, University of Bologna, ItalyLavinia Egidi, University of Piemonte Orientale, ItalyConstraint Solving and Programming (CSP)Stefano Bistarelli, Università degli studi "G. D'Annunzio" di Chieti-Pescara, ItalyEric Monfroy, University of Nantes, FranceBarry O'Sullivan, University College Cork, IrelandCoordination Models, Languages and Applications (CM) Alessandro Ricci, Universita di Bologna, ItalyBernhard Angerer, Michael Ignaz Schumacher, EPFL IC IIF LIA, SwitzerlandData Mining (DM)Hasan M. Jamil, Wayne State University, USAData Streams (DS)Jesus S. Aguilar-Ruiz, Pablo de Olavide University, SpainFrancisco J. Ferrer-Troyano, University of Seville, SpainJoao Gama, University of Porto, PortugalRalf Klinkenberg, University of Dortmund, GermanyDatabase Theory, Technology, and Applications (DTTA) Ramzi A. Haraty, Lebanese American University, LebanonApostolos N. Papadopoulos, Aristotle University, GreeceJunping Sun, Nova Southeastern University, USADependable and Adaptive Distributed Systems (DADS)Karl M. Göschka, Vienna University of Technology, AustriaSvein O. Hallsteinsen, SINTEF ICT, NorwayRui Oliveira, Universidade do Minho, PortugalAlexander Romanovsky, University of Newcastle upon Tyne, UK Document Engineering (DE)Rafael Dueire Lins, Universidade Federal de Pernambuco, Brazil Electronic Commerce Technologies (ECT)Sviatoslav Braynov, University of Illinois at Springfield, USADaryl Nord, Oklahoma State University, USAFernando Rubio, Universidad Complutense de Madrid, Spain Embedded Systems: Applications, Solutions and Techniques (EMBS)Alessio Bechini, University of Pisa, ItalyCosimo Antonio Prete, University of Pisa, ItalyJihong Kim, Seoul National University, KoreaEvolutionary Computation (EC)Bryant A. Julstrom, St. Cloud State University, USA Geoinformatics and Technology (GT)Dong-Cheon Lee, Sejong University, KoreaGwangil Jeon, Korea Polytechnic University, KoreaGeometric Computing and Reasoning (GCR)Xiao-Shan Gao, Chinese Academy of Sciences, ChinaDominique Michelucci, Universite de Bourgogne, FrancePascal Schreck, Universite Louis Pasteur, FranceHandheld Computing (HHC)Qusay H. Mahmoud, University of Guelph, CanadaZakaria Maamar, Zayed University, UAEInformation Access and Retrieval (IAR)Fabio Crestani, University of Strathclyde, UKGabriella Pasi, University of Milano Bicocca, ItalyMobile Computing and Applications (MCA)Hong Va Leong, Hong Kong Polytechnic University, Hong KongAlvin Chan, Hong Kong Polytechnic University, Hong KongModel Transformation (MT)Jean Bézivin, University of Nantes, FranceAlfonso Pierantonio, Università degli Studi dell’Aquila, ItalyAntonio Vallecillo, Universidad de Malaga, SpainJeff Gray, University of Alabama at Birmingham, USAMultimedia and Visualization (MMV)Chaman L. Sabharwal, University of Missouri-Rolla, USAMingjun Zhang, Agilent Technologies, USAObject-Oriented Programming Languages and Systems (OOP) Davide Ancona, DISI - Università di Genova, ItalyMirko Viroli, Università di Bologna, ItalyOperating Systems and Adaptive Applications (OSAA)Jiman Hong, Kwangwoon University, KoreaTei-Wei Kuo, National Taiwan University, TaiwanOrganizational Engineering (OE)José Tribolet, Technical University of Lisbon, PortugalRobert Winter, University of St. Gallen, SwitzerlandArtur Caetano, Technical University of Lisbon, Portugal Programming for Separation of Concerns (PSC)Corrado Santoro, Catania University, ItalyEmiliano Tramontana, Catania University, ItalyIan Welch, Victoria University, New ZealandYvonne Coady, Victoria Univeristy, CanadaProgramming Languages (PL)Chang-Hyun Jo, California State University at Fullerton, USAMarjan Mernik, University of Maribor, SloveniaBarrett Bryant, University of Alabama at Birmingham, USAReliable Computations and their Applications (RCA)Martine Ceberio, University of Texas at El Paso, USAVladik Kreinovich, University of Texas at El Paso, USAMichael Rueher, Universite de Nice ESSI, FranceSemantic Web and Application (SWA)Hyoil Han, Drexel University, USASemantic-Based Resource Discovery, Retrieval and Composition (SDRC)Eugenio Di Sciascio, SinsInfLab Politecnico di Bari, ItalyFrancesco M. Donini, University of Tuscia, ItalyTommaso Di Noia, SinsInfLab Politecnico di Bari, ItalyMassimo Paolucci, DoCoMo Euro-Labs, GermanySoftware Engineering (SE)W. Eric Wong, University of Texas at Dallas, USAChang-Oan Sung, Indiana University Southeast, USASoftware Verification (SV)Zijiang Yang, Western Michigan University, USALunjin Lu, Oakland University, USAFausto Spoto, Universita di Verona, ItalySystem On Chip Design and Software Supports (SODSS) Seong Tae Jhang, Suwon University, KoreaSung Woo Chung, Korea University, KoreaTrust, Recommendations, Evidence and other Collaborative Know-how (TRECK)Jean-Marc Seigneur, University of Geneva, SwitzerlandJeong Hyun Yi, Samsung Advanced Institute of Technology, South Korea Ubiquitous Computing: Digital Spaces, Services and Content (UC)Achilles Kameas, Hellenic Open University, GreeceGeorge Roussos, University of London, UKWeb Technologies (WT)Fahim Akhter , Zayed University, UAEDjamal Benslimane, University of Lyon, FranceZakaria Maamar, Zayed University, UAEQusay H. Mahmoud, University of Guelph, CanadaLocal SupportLocal support for SAC 2007 is provided by the Seoul National University in Seoul, Suwon University in Gyeonggi-do, Ministry of Education and Human Resources Development, Samsung, mds technology, KETI, MIC, CVB, and ETRI. The SAC organizing committee acknowledges and thanks the local supporters for their generous contributions to SAC 2007. Their support has been essential to the success of Symposium, and is greatly appreciated. ACM SIGAPPThe ACM Special Interest Group on Applied Computing is ACM's primary applications-oriented SIG. Its mission is to further the interests of the computing professionals engaged in the development of new computing applications and applications areas and the transfer of computing technology to new problem domains. SIGAPP offers practitioners and researchers the opportunity to share mutual interests in innovative application fields, technology transfer, experimental computing, strategic research, and the management of computing. SIGAPP also promotes widespread cooperation among business, government, and academic computing activities. Its annual Symposium on Applied Computing (SAC) provides an international forum for presentation of the results of strategic research and experimentation for this inter-disciplinary environment. SIGAPP membership fees are: $30.00 for ACM Non-members, $15.00 for ACM Members, and $8.00 for Student Members. For information contact Barrett Bryant at bryant@. Also, checkout the SIGAPP website at /sigapp/M ESSAGE FROM THE S YMPOSIUM C HAIRSRoger WaiwrightUniversity of Tulsa, USAHisham M. HaddadKennesaw State University, USASung Y. ShinSouth Dakota State University, USAOn behalf of the Organization Committee, it is our pleasure to welcome you to the 22nd Annual ACM Symposium on Applied Computing (SAC 2007). This year, the conference is hosted by Seoul National University and Suwon University in Gyeonggi-do, Korea. Many thanks for your participation in this international event dedicated to computer scientists, engineers, and practitioners seeking innovative ideas in various areas of computer applications. The sponsoring SIG of this Symposium, the ACM Special Interest Group on Applied Computing, is dedicated to further the interests of computing professionals engaged in the design and development of new computing applications, interdisciplinary applications areas, and applied research. The conference provides a forum for discussion and exchange of new ideas addressing computational algorithms and complex applications. This goal is reflected in its wide spectrum of application areas and tutorials designed to provide variety of discussion topics during this event. The conference is composed of various specialized technical tracks and tutorials. As in past successful meetings, talented and dedicated Track Chairs and Co-Chairs have organized SAC 2007 tracks. Each track maintains a program committee and group of highly qualified reviewers. We thank the Track Chairs, Co-Chairs, and participating reviewers for their commitment to making SAC 2007 another high quality conference. We also thank our invited keynote speakers for sharing their knowledge with SAC attendees. Most of all, special thanks to the authors and presenters for sharing their experience with the rest of us and to all attendees for joining us in Seoul, Korea.The local organizing committee has always been a key to the success of the conference. This year, we thank our local team from Seoul National University and Suwon University. In particular, we thank Dr. Jiman Hong, from Kwangwoon University, and Dr. Seong Tae Jhang, from Suwon University, for chairing the local organization effort. We also thank Dr. Jaeyoung Choi, from Soongsil University, and Dr. Tei-Wei Kuo, from National Taiwan University, for organizing the Tutorials Program. Other committee members we also would like to thank are Lorie Liebrock for her tremendous effort putting together the conference proceedings, Mathew Palakal for coordinating another successful Posters Program, and Sascha Ossowski and Ronaldo Menezes for bringing together the Technical Program. Finally, we extend outthanks and gratitude to our honorable Symposium and Program Chairs Drs. Yookun Cho of Seoul National University and Dr. Yong Wan Koo of Suwon University. Many thanks for hosting the conference and coordinating governmental and local support. Again, we welcome you to SAC 2007 in the lively city of Seoul. We hope you enjoy your stay in Seoul and leave this event enriched with new ideas and friends. Next year, we invite you to participate in SAC 2008 to be held in the costal city of Fortaleza, Brazil. The symposium will be hosted by the University of Fortaleza (UNIFOR) and the Federal University of Ceará (UFC). We hope to see there!M ESSAGE FROM THE P ROGRAM C HAIRSSascha OssowskiUniversity Rey Juan Carlos, SpainRonaldo MenezesFlorida Institute of Technology, USAWelcome to the 22nd Symposium on Applied Computing (SAC 2007). Over the past 21 years, SAC has been an international forum for researchers and practitioners to present their findings and research results in the areas of computer applications and technology. The SAC 2007 Technical Program offers a wide range of tracks covering major areas of computer applications. Highly qualified referees with strong expertise and special interest in their respective research areas carefully reviewed the submitted papers. As part of the Technical Program, this year the Tutorial Program offers several half-day tutorials that were carefully selected from numerous proposals. Many thanks to Jaeyoung Choi from the Soongsil University and Tei-Wei Kuo from the National Taiwan University for chairing the Tutorial Program. Also, this is the fourth year for SAC to incorporate poster papers into the Technical Program. Many thanks to Mathew Palakal from Indiana University Purdue University for chairing the poster sessions. SAC 2007 would not be possible without contributions from members of the scientific community. As anyone can imagine, many people have dedicated tremendous time and effort over the period of 10 months to bring you an excellent program. The success of SAC 2007 relies on the effort and hard work of many volunteers. On behalf of the SAC 2007 Organizing Committee, we would like to take this opportunity to thank all of those who made this year's technical program a reality, including speakers, referees, track chairs, session chairs, presenters, and attendees. We also thank the local arrangement committee lead by Jiman Hong from the Kwangwoon University and Seong Tae Jhang from Suwon University. We also want to thank Hisham Haddad from Kennesaw State University for his excellent job again as the SAC Treasurer, Webmaster, and Registrar.SAC's open call for Track Proposals resulted in the submission of 47 track proposals. These proposals were carefully evaluated by the conference Executive Committee. Some proposals were rejected on the grounds of either not being appropriate for the areas that SAC covers traditionally or being of rather narrow and specialized nature. Some others tracks were merged to form a single track. Eventually, 38 tracks were established, which then went on to produce their own call for papers. In response to these calls, 786 papers were submitted, from which 256 papers were strongly recommended by the referees for acceptance and inclusion in the Conference Proceedings. This gives SAC 2007 an acceptance rate of 32.5% across all tracks. SAC is today one of the most popular and competitive conferences in the international field of applied computing.We hope you will enjoy the meeting and have the opportunity to exchange your ideas and make new friends. We also hope you will enjoy your stay in Seoul, Korea and take pleasure from the many entertainments and activities that the city and Korea has to offer. We look forward to your active participation in SAC 2008 when for the first time SAC will be hosted in South America, more specifically in Fortaleza, Brazil. We encourage you and your colleagues to submit your research findings to next year's technical program. Thank you for being part of SAC 2007, and we hope to see you in sunny Fortaleza, Brazil for SAC 2008.O THER A CTIVITIESReview Meeting: Sunday March 11, 2007, from 18:00 to 19:00 in Room 311A. Open for SAC Organizing Committee and Track Chairs and Co-Chairs.SAC 2008 Organization Meeting: Monday March 12, 2007, from 18:00 to 19:00 in Room 311A. Open for SAC Organizing Committee.SAC Reception: Monday March 12, 2007 at 19:00 to 22:00. Room 402. Open for all registered attendees.Posters Session: Tuesday March 13, 2007, from 13:30 to 17:00 in the Room 311C. Open to everyone.SIGAPP Annual Business Meeting: Tuesday March 13, 2007, from 17:15 to 18:15 in Room 311A. Open to everyone.SAC Banquet: Wednesday March 14, 2007. Rooms 331-334. Open for Banquet Ticket holders. See your tickets for full details. Track-Chairs Luncheon: Thursday April 27, 2006, from 12:00 to 13:30. Hosu (Lake) Food-mall. Open for SAC Organizing Committee, Track Chairs and Co-Chairs.SAC 2008SAC 2008 will be held in Fortaleza, Ceará, Brazil, March 16 – 20, 2008. It is co-hosted by the University of Fortaleza (UNIFOR) and the Federal University of Ceará (UFC). Please check the registration desk for handouts. You can also visit the website at /conferences/sac/sac2008/.M ONDAY K EYNOTE A DDRESSA New DBMS Architecture for DB-IRIntegrationDr. Kyu-Young WhangDirector of Advanced Information Technology Research Center, Korea Advanced Institute ofScience and Technology, Daejeon, Korea M ONDAY M ARCH 12, 2007, 9:00 – 10:00ROOM 310 A, B AND CABSTRACTNowadays, there is an increasing need to integrate the DBMS (for structured data) with Information Retrieval (IR) features (for unstructured data). DB-IR integration becomes one of major challenges in the database area. Extensible architectures provided by commercial ORDBMS vendors can be used for DB-IR integration. Here, extensions are implemented using a high-level (typically, SQL-level) interface. We call this architecture loose-coupling. The advantage of loose-coupling is that it is easy to implement. But, it is not preferable for implementing new data types and operations in large databases when high performance is required. In this talk, we present a new DBMS architectureapplicable to DB-IR integration, which we call tight-coupling. In tight-coupling, new data types and operations are integrated into the core of the DBMS engine in the extensible type layer. Thus, they are incorporated as the "first-class citizens" within the DBMS architecture and are supported in a consistent manner with high performance. This tight-coupling architecture is being used to incorporate IR features and spatial database features into the Odysseus ORDBMS that has been under development at KAIST/AITrc for over 16 years. In this talk, we introduce Odysseus and explain its tightly-coupled IR features (U.S. patented in 2002). Then, we demonstrate excellence of tight-coupling by showing benchmark results. We have built a web search engine that is capable of managing 20~100 million web pages in a non-parallel configuration using Odysseus. This engine has been successfully tested in many commercial environments. In a parallel configuration, it is capable of managing billons of web pages. This work won the Best Demonstration Award from the IEEE ICDE conference held in Tokyo, Japan in April 2005.W EDNESDAY K EYNOTE A DDRESS The Evolution of Digital Evidence asa Forensic ScienceDr. Marc RogersChair of the Cyber Forensics Program,Department of Computer and InformationTechnology, Purdue University, USAW EDNESDAY M ARCH 14, 2007, 9:00 –10:00ROOMS 310 A, B AND CABSTRACTThe field of Digital Evidence while garnering significant attention by academia, the public, and the media, has really just begun its journey as a forensic science. Digital Forensic Science (DFS) in general is an immature discipline in comparison to the other more traditional forensic sciences such as latent fingerprint analysis. Digital Evidence, which falls under the larger umbrella of DFS, truly encompasses the notion of being an applied multi-disciplinary science. The areas of Computer Science, Technology, Engineering, Mathematics, Law, Sociology, Psychology, Criminal Justice etc. all have played and will continue to play a very large role in maturing and defining this scientific field. The presentation will look at the history of Digital Forensic Science and Digital Evidence, the current state of the field, and what might be in store for the future.S EOUL R EPRESENTATIVE A DDRESSKoran IT policy - IT839Dr. Jung-hee SongAssistant MayorChief of Information OfficerInformation System Planning DivisionSeoul Metropolitan Government, KoreaW EDNESDAY M ARCH 14, 2007, 18:30 – 19:00ROOMS 331-334(DURING BANQUET)ABSTRACTKorean IT policy initiated by Ministry of Information and Communication called IT839 Strategy will be introduced. By defining government role in the u-Korea vision pursuit, it removes uncertainties for IT industry and increases its active participation. As capital of Korea, Seoul presented a grand plan to be u-Seoul. An overview of u-Seoul masterplan will be delivered with introduction of 5 specific projects.SAC 2007 S CHEDULES UNDAY M ARCH 11, 200709:00 – 17:00 L OBBYR EGISTRATION09:00 – 10:30 R OOMS 310 A AND BAM T UTORIALS IT1: Introduction to Security-enhanced Linux(SELinux)Dr. Haklin Kimm, Professor, omputer Science Department, ast Stroudsburg University of Pennsylvania, USAT2: Similarity Search - The Metric Space Approach Pavel Zezula, Masaryk University, Brno, Czech RepublicGiuseppe Amato, ISTI-CNR, Pisa, ItalyVlastislav Dohnal, Masaryk University, Brno, Czech Republic10:30 – 11:00 L OBBYC OFFEE B REAK11:00 – 12:30 R OOMS 310 A AND BAM T UTORIALS IIT1: Introduction to Security-enhanced Linux(SELinux)Dr. Haklin Kimm, Professor, omputer Science Department, ast Stroudsburg University of Pennsylvania, USAT2: Similarity Search - The Metric Space Approach Pavel Zezula, Masaryk University, Brno, Czech RepublicGiuseppe Amato, ISTI-CNR, Pisa, ItalyVlastislav Dohnal, Masaryk University, Brno, Czech Republic 12:00 – 13:30 H OSU (L AKE) F OOD-MALL,1ST F LOORL UNCH B REAK13:30 – 15:00 R OOM 310 APM T UTORIAL IT3: Introduction to OWL Ontology Developmentand OWL ReasoningYoung-Tack Park, Professor, School of Computing, SoongsilUniversity,Seoul, Korea15:00 – 15:30 L OBBYC OFFEE B REAK15:30 – 17:00 R OOM 310 APM T UTORIAL IIT3: Introduction to OWL Ontology Developmentand OWL ReasoningYoung-Tack Park, Professor, School of Computing, SoongsilUniversity,Seoul, Korea18:00 – 19:00 R OOM 311A SAC 2007 R EVIEW M EETINGM ONDAY M ARCH 12, 200708:00 – 17:00 L OBBYR EGISTRATION08:30 – 09:00 R OOM 310O PENING R EMARKS09:00 – 10:00 R OOM 310K EYNOTE A DDRESSA New DBMS Architecture for DB-IRIntegrationDr. Whang, Kyu-YoungDirector of Advanced Information TechnologyResearch CenterKorea Advanced Institute of Science andTechnologyDaejeon, Korea10:00 – 10:30 L OBBYC OFFEE B REAK10:30 – 12:00 R OOM 310A(DS) Data StreamsJoao Gama, University of Porto (UP), Portugal RFID Data Management for Effective ObjectsTrackingElioMasciari, CNR, ItalyA Priority Random Sampling Algorithm for Time-based Sliding Windows over Weighted StreamingDataZhang Longbo, Northwestern Polytechnical University, China Li Zhanhuai, Northwestern Polytechnical University, ChinaZhao Yiqiang, Shandong University of Technology, ChinaMin Yu, Northwestern Polytechnical University, China Zhang Yang, Northwest A&F University, ChinaOLINDDA: A Cluster-based Approach forDetecting Novelty and Concept Drift in DataStreamsEduardo Spinosa, University of Sao Paulo (USP), BrazilAndré Carvalho, University of Sao Paulo (USP), Brazil Joao Gama, University of Porto (UP), PortugalA Self-Organizing Neural Network for DetectingNoveltiesMarcelo Albertini, Universidade de Sao Paulo, BrazilRodrigo Mello, Universidade de São Paulo, Brazil10:30 – 12:00 R OOM 310B (AI) Artificial Intelligence, ComputationalLogic and Image AnalysisChih-Cheng Hung, Southern Polytechnic State University, USA Toward a First-Order Extension of Prolog'sUnification using CHRKhalil Djelloul, University of Ulm, GermanyThi-Bich-Hanh Dao, University d'Orléans, FranceThom Fruehwirth, University of Ulm, GermanyA Framework for Prioritized Reasoning Based onthe Choice EvaluationLuciano Caroprese, University of Calabria, ItalyIrina Trubitsyna, University of Calabria, ItalyEster Zumpano, University of Calabria, ItalyA Randomized Knot Insertion Algorithm for Outline Capture of Planar Images using CubicSplineMuhammad Sarfraz, King Fahd University of Petroleum andMinerals, Saudi ArabiaAiman Rashid, King Fahd University of Petroleum and Minerals,Saudi ArabiaEstraction of Arabic Words from Complex ColorImagesRadwa Fathalla, AAST, EgyptYasser El Sonbaty, AAST College of Computing, Egypt Mohamed Ismail, Alexandria University, Egypt10:30 – 12:00 R OOM 310C (PL) Programming LanguagesMarjan Mernik, University of Maribor, Slovenia Implementing Type-Based Constructive Negation Lunjin Lu, Oakland University, USATowards Resource-Certified Software: A Formal Cost Model for Time and its Application to anImage-Processing ExampleArmelle Bonenfant, University of St Andrews, UKZehzi Chen, Heriot-Watt University, UKKevin Hammond, Univestiy of St Andrews, UKGreg Michaelson, Heriot-Watt University, UKAndy Wallace, Heriot-Watt University, UKIain Wallace, Heriot-Watt University, UK。

alevel计算机原题
摘要：
1.Actin 灰度值的定义和作用
2.Actin 灰度值的计算方法
3.Actin 灰度值在计算机视觉和图像处理中的应用
4.Actin 灰度值的优势和局限性
正文：
Actin 灰度值是计算机视觉和图像处理领域中常用的一种表示图像亮度的指标。

它能够反映图像的明暗程度，是图像处理中重要的参数之一。

Actin 灰度值的定义和作用：Actin 灰度值是指图像中每个像素点的亮度值。

在计算机视觉中，Actin 灰度值是判断图像明暗程度的重要依据，也是图像增强、滤波等操作的基础。

Actin 灰度值的计算方法：Actin 灰度值的计算方法通常是通过对图像中
每个像素点的RGB 颜色值进行加权求和得到。

其中，RGB 颜色值分别代表红、绿、蓝三个颜色通道的亮度值，加权系数通常根据不同的应用场景和需求进行设定。

Actin 灰度值在计算机视觉和图像处理中的应用：Actin 灰度值在计算机视觉和图像处理中有广泛的应用。

例如，在图像增强中，通过调整Actin 灰度值，可以改变图像的亮度和对比度，从而提高图像的质量。

在图像滤波中，Actin 灰度值也可以作为判断图像纹理复杂度的依据，帮助滤除图像中的噪声。

Actin 灰度值的优势和局限性：Actin 灰度值的优势在于它能够直观地反映图像的亮度信息，便于人们理解和操作。