Image Super-Resolution via Spar Reprentation Jianchao Yang,Student Member,IEEE,John Wright,Member,IEEE Thomas Huang,Life Fellow,IEEE and
Yi Ma,Senior Member,IEEE
Abstract—This paper prents a new approach to single-image superresolution,bad on spar signal reprentation.Rearch on image statistics suggests that image patches can be well-reprented as a spar linear combination of elements from an appropriately chon over-complete dictionary.Inspired by this obrvation,we ek a spar reprentation for each patch of the low-resolution input,and then u the coefficients of this reprentation to generate the high-resolution output.Theoretical results from compresd nsing suggest that under mild condi-tions,the spar reprentation can be correctly recovered from the downsampled signals.By jointly training two dictionaries for the low-and high-resolution image patches,we can enforce the similarity of spar reprentations between the low resolution and high resolution image patch pair with respect to their own dictionaries.Therefore,the spar reprentation of a low resolution image patch can be applied with the high resolution image patch dictionary to generate a high resolution image patch. The learned dictionary pair is a more compact reprentation of the patch pairs,compared to previous approaches,which simply sample a large amount of image patch pairs[1],reducing the computational
礼貌用语cost substantially.The effectiveness of such a sparsity prior is demonstrated for both general image super-resolution and the special ca of face hallucination.In both cas,our algorithm generates high-resolution images that are competitive or even superior in quality to images produced by other similar SR methods.In addition,the local spar modeling of our approach is naturally robust to noi,and therefore the propod algorithm can handle super-resolution with noisy inputs in a more unified framework.
Index Terms—Image super-resolution,spar reprentation, spar coding,face hallucination,non-negative matrix factoriza-tion.
I.I NTRODUCTION
Super-resolution(SR)image reconstruction is currently a very active area of rearch,as it offers the promi of overcoming some of the inherent resolution limitations of low-cost imaging ll phone or surveillance cameras)allowing better utilization of the growing capability of high-resolution high-definition LCDs).Such resolution-enhancing technology may also prove to be esn-tial in medical imaging and satellite imaging where diagnosis or analysis from low-quality images can be extremely difficult. Conventional approaches to generating a super-resolution i
m-age normally require as input multiple low-resolution images Jianchao Yang and Thomas Huang are with Beckman Institute,Uni-versity of Illinois Urbana-Champaign,Urbana,IL61801USA(email: jyang29@ifp.uiuc.edu;huang@ifp.uiuc.edu).John Wright is with the Visual Computing Group,Microsoft Rearch Asia(email:jnwright@uiuc.edu).Yi Ma is with the Visual Computing Group,Microsoft Rearch Aisa,as well as Coordinated Science Laboratory,University of Illinois Urbana-Champaign, Urbana,IL61801USA(email:yima@uiuc.edu).
This work was supported in part by the U.S.Army Rearch Laboratory and the U.S.Army Rearch Office under grant number W911NF-09-1-0383. It was also supported by grants NSF IIS08-49292,NSF ECCS07-01676, and ONR N00014-09-1-0230.of the same scene,which are aligned with sub-pixel accuracy. The SR task is cast as the inver problem of recovering the original high-resolution image by fusing the low-resolution images,bad on reasonable assumptions or prior knowledge about the obrvation model that maps the high-resolution im-age to the low-resolution ones.The fundamental reconstruction constraint for SR is that the recovered image,after applying the same generation model,should reproduce the obrved low-resolution images.However,SR image reconstruction is gen-erally a verely ill-pod problem becau of the insufficient number of low resolution images,ill-conditioned registration and unknown blurring operators,and the solution from th
e reconstruction constraint is not unique.Various regularization methods have been propod to further stabilize the inversion of this ill-pod problem,such as[2],[3],[4].
However,the performance of the reconstruction-bad super-resolution algorithms degrades rapidly when the desired magnification factor is large or the number of available input images is small.In the cas,the result may be overly smooth,lacking important high-frequency details[5].Another class of SR approach is bad on interpolation[6],[7], [8].While simple interpolation methods such as Bilinear or Bicubic interpolation tend to generate overly smooth images with ringing and jagged artifacts,interpolation by exploiting the natural image priors will generally produce more favorable results.Dai et al.[7]reprented the local image patches using the background/foreground descriptors and reconstructed the sharp discontinuity between the two.Sun et.al.[8]explored the gradient profile prior for local image structures and ap-plied it to super-resolution.Such approaches are effective in prerving the edges in the zoomed image.However,they are limited in modeling the visual complexity of the real images. For natural images withfine textures or smooth shading,the approaches tend to produce watercolor-like artifacts.
A third category of SR approach is bad on ma-chine learning techniques,which attempt to capture the co-occurrence prior between low-resolution and high-resolution image patches.[9]propod an e
xample-bad learning strat-egy that applies to generic images where the low-resolution to high-resolution prediction is learned via a Markov Random Field(MRF)solved by belief propagation.[10]extends this approach by using the Primal Sketch priors to enhance blurred edges,ridges and corners.Nevertheless,the above methods typically require enormous databas of millions of high-resolution and low-resolution patch pairs,and are therefore computationally intensive.[11]adopts the philosophy of Lo-cally Linear Embedding(LLE)[12]from manifold learning, assuming similarity between the two manifolds in the high-resolution and the low-resolution patch spaces.Their algorithm maps the local geometry of the low-resolution patch space to
the high-resolution one,generating high-resolution patch as
a linear combination of neighbors.Using this strategy,more
patch patterns can be reprented using a smaller training databa.However,using afixed number K neighbors for
reconstruction often results in blurring effects,due to over-or
under-fitting.In our previous work[1],we propod a method for adaptively choosing the most relevant reconstruction neigh-
bors bad on spar coding,avoiding over-or under-fitting of [11]and producing superior results.However,spar coding
over a large sampled image patch databa directly is too time-
consuming.
While the mentioned approaches above were propod for
generic image super-resolution,specific image priors can be
incorporated when tailored to SR applications for specific domains such as human faces.This face hallucination prob-
lem was addresd in the pioneering work of Baker and
Kanade[13].However,the gradient pyramid-bad prediction introduced in[13]does not directly model the face prior,and
the pixels are predicted individually,causing discontinuities and artifacts.Liu et al.[14]propod a two-step statistical
approach integrating the global PCA model and a local patch
model.Although the algorithm yields good results,the holistic PCA model tends to yield results like the mean face and the
probabilistic local patch model is complicated and compu-
七年级英语单词tationally demanding.Wei Liu et al.[15]propod a new approach bad on TensorPatches and residue compensation.
While this algorithm adds more details to the face,it also introduces more artifacts.
This paper focus on the problem of recovering the super-
resolution version of a given low-resolution image.Similar to the aforementioned learning-bad methods,we will rely
on patches from the input image.However,instead of work-
ing directly with the image patch pairs sampled from high-and low-resolution images[1],we learn a compact repre-
ntation for the patch pairs to capture the co-occurrence prior,significantly improving the speed of the algorithm.
Our approach is motivated by recent results in spar signal
reprentation,which suggest that the linear relationships among high-resolution signals can be accurately recovered
from their low-dimensional projections[16],[17].Although
the super-resolution problem is very ill-pod,making preci recovery impossible,the image patch spar reprentation
demonstrates both effectiveness and robustness in regularizing the inver problem.
a)Basic Ideas:To be more preci,let D∈R n×K
be an overcomplete dictionary of K atoms(K>n),and suppo a signal x∈R n can be reprented as a spar linear
combination with respect to D.That is,the signal x can be
written as x=Dα0where whereα0∈R K is a vector with very few( n)nonzero entries.In practice,we might only
obrve a small t of measurements y of x:
y.=L x=L Dα0,(1) where L∈R k×n with k<n is a projection matrix.In our super-resolution context,x is a high-resolution image(patch), while y is its low-resolution counter part(or features extracted from it).If the dictionary D is overcomplete,the equation x=Dαis underdetermined for the unknown coefficientsα
.Fig.1.Reconstruction of a raccoon face with magnification factor2.Left: result by our method.Right:the original image.There is little noticeable difference visually even for such a complicated texture.The RMSE for the reconstructed image is5.92(only the local patch model is employed). The equation y=L Dαis even more dramatically under-determined.Nevertheless,under mild conditions,the sparst
solutionα0to this equation will be unique.Furthermore,if D satisfies an appropriate near-isometry condition,then for a wide variety of matrices L,any sufficiently spar linear
荷花的寓意和象征reprentation of a high-resolution image patch x in terms of the D can be recovered(almost)perfectly from the low-resolution image patch[17],[18].1Fig.1shows an example that demonstrates the capabilities of our method derived from this principle.The image of the raccoon face is blurred and downsampled to half of its original size in both dimensions. Then we zoom the low-resolution image to the original size using the propod method.Even for such a complicated texture,spar reprentation recovers a visually appealing reconstruction of the original signal.
Recently spar reprentation has been successfully applied to many other related inver problems in image processing, such as denoising[19]and restoration[20],often improving on the state-of-the-art.For example in[19],the authors u the K-SVD algorithm[21]to learn an overcomplete dictionary from natural image patches and successfully apply it to the image denoising problem.In our tting,we do not directly compute the spar reprentation of the high-resolution patch. Instead,we will work with two coupled dictionaries,D h for high-resolution patches,and D l for low-resolution ones.The spar reprentation of a low-resolution patch in terms of D l will be directly us
ed to recover the corresponding high-resolution patch from D h.We obtain a locally consistent solution by allowing patches to overlap and demanding that the reconstructed high-resolution patches agree on the overlapped areas.In this paper,we try to learn the two overcomplete dictionaries in a probabilistic model similar to[22].To enforce that the image patch pairs have the same spar reprentations with respect to D h and D l,we learn the two dictionaries simultaneously by concatenating them with proper normal-ization.The learned compact dictionaries will be applied to both generic image super-resolution and face hallucination to demonstrate their effectiveness.
Compared with the aforementioned learning-bad methods,
our algorithm requires only two compact learned dictionaries, instead of a large training patch databa.The computation, mainly bad on linear programming or convex optimization, 1Even though the structured projection matrix defined by blurring and downsampling in our SR context does not guarantee exact recovery ofα0, empirical experiments indeed demonstrate the effectiveness of such a spar prior for our SR tasks.
is much more efficient and scalable,compared with[9],[10], [11].The online recovery of the spar rep
rentation us the low-resolution dictionary only–the high-resolution dictionary is ud to calculate thefinal high-resolution image.The computed spar reprentation adaptively lects the most relevant patch bas in the dictionary to best reprent each patch of the given low-resolution image.This leads to superior performance,both qualitatively and quantitatively,compared to the method described in[11],which us afixed number of nearest neighbors,generating sharper edges and clearer textures.In addition,the spar reprentation is robust to noi as suggested in[19],and thus our algorithm is more robust to noi in the test image,while most other methods cannot perform denoising and super-resolution simultaneously.
b)Organization of the Paper:The remainder of this paper is organized as follows.Section II details our formula-tion and solution to the image super-resolution problem bad on spar reprentation.Specifically,we study how to apply spar reprentation for both generic image super-resolution and face hallucination.In Section III,we discuss how to learn the two dictionaries for the high-and low-resolution image patches respectively.Various experimental results in Section IV demonstrate the efficacy of sparsity as a prior for regularizing image super-resolution.
c)Notations:X and Y denote the high-and low-resolution images respectively,and x and y denote the high-and low-resolution image patches respectively.We u bold upperca D to denote the dictionar
y for spar coding, specifically we u D h and D l to denote the dictionaries for high-and low-resolution image patches respectively.Bold lowerca letters denote vectors.Plain upperca letters denote regular ,S is ud as a downsampling operation in matrix form.Plain lowerca letters are ud as scalars.
II.I MAGE S UPER-R ESOLUTION FROM S PARSITY
The single-image super-resolution problem asks:given a low-resolution image Y,recover a higher-resolution image X of the same scene.Two constraints are modeled in this work to solve this ill-pod problem:1)reconstruction constraint, which requires that the recovered X should be consistent with the input Y with respect to the image obrvation model; and2)sparsity prior,which assumes that the high resolution patches can be sparly reprented in an appropriately chon overcomplete dictionary,and that their spar reprentations can be recovered from the low resolution obrvation.
1)Reconstruction constraint:The obrved low-resolution image Y is a blurred and downsampled version of the high resolution image X:
Y=SH X(2) Here,H reprents a blurringfilter,and S the downsampling operator.
Super-resolution remains extremely ill-pod,since for a given low-resolution input Y,infinitely many high-resolution images X satisfy the above reconstruction constraint.We further regularize the problem via the following prior on small patches x of X:
2)Sparsity prior:The patches x of the high-resolution image X can be reprented as a spar linear combination in a dictionary D h trained from high-resolution patches sampled from training images:
x≈D hαfor someα∈R K with α 0 K.(3) The spar reprentationαwill be recovered by reprenting patches y of the input image Y,with respect to a low resolution dictionary D l co-trained with D h.The dictionary training process will be discusd in Section III.
We apply our approach to both generic images and face images.For generic image super-resolution,we divide the problem into two steps.First,as suggested by the sparsity prior(3),wefind the spar reprentation for each local patch,respecting spatial compatibility between neighbors. Next,using the result from this local spar reprentation, we further regularize and refine the entire image using the reconstruction constraint(2).In this strategy,a local model from the sparsity prior is ud to recover lost high-frequency for local details.The global model from the reconstruction constraint is then applied to remove possible artifacts from thefirst step and make the image more co
nsistent and natural. The face images differ from the generic images in that the face images have more regular structure and thus reconstruction constraints in the face subspace can be more effective.For face image super-resolution,we rever the above two steps to make better u of the global face structure as a regularizer. Wefirstfind a suitable subspace for human faces,and apply the reconstruction constraints to recover a medium resolution image.We then recover the local details using the sparsity prior for image patches.
The remainder of this ction is organized as follows:in Section II-A,we discuss super-resolution for generic images. We will introduce the local model bad on spar repren-tation and global model bad on reconstruction constraints. In Section II-B we discuss how to introduce the global face structure into this framework to achieve more accurate and visually appealing super-resolution for face images.
A.Generic Image Super-Resolution from Sparsity
1)Local model from spar reprentation:Similar to the patch-bad methods mentioned previously,our algorithm tries to infer the high-resolution image patch for each low-resolution image patch from the input.For this local model, we have two dictionaries D h and D l,which are trained to h
ave the same spar reprentations for each high-resolution and low-resolution image patch pair.We subtract the mean pixel value for each patch,so that the dictionary reprents image textures rather than absolute intensities.In the recovery process,the mean value for each high-resolution image patch is then predicted by its low-resolution version.
For each input low-resolution patch y,wefind a spar reprentation with respect to D l.The corresponding high-resolution patch bas D h will be combined according to the coefficients to generate the output high-resolution patch x. The problem offinding the sparst reprentation of y can be formulated as:
min α 0s.t. F D lα−F y 22≤ ,(4)
where F is a(linear)feature extraction operator.The main role of F in(4)is to provide a perceptually meaningful constraint2 on how cloly the coefficientsαmust approximate y.We will discuss the choice of F in Section III.
Although the optimization problem(4)is NP-hard in gen-eral,recent results[23],[24]suggest that as long as the desired coefficientsαare sufficiently spar,they can be efficiently recovered by instead minimizing the 1-norm3,as follows:
min α 1s.t. F D lα−F y 22≤ .(5)
Lagrange multipliers offer an equivalent formulation
min
α
F D lα−F y 22+λ α 1,(6)
幼儿园生活where the parameterλbalances sparsity of the solution andfidelity of the approximation to y.Notice that this is esntially a linear regression regularized with 1-norm on the coefficients,known in statistical literature as the Lasso[27]. Solving(6)individually for each local patch does not guarantee the compatibility between adjacent patches.We enforce compatibility between adjacent patches using a one-pass algorithm similar to that of[28].4The patches are procesd in raster-scan order in the image,from left to right and top to bottom.We modify(5)so that the super-resolution reconstruction D hαof patch y is constrained to cloly agree with the previously computed adjacent high-resolution patches.The resulting optimization problem is
min α 1s.t. F D lα−F y 22≤ 1,
P D hα−w 22≤ 2,
(7)
where the matrix P extracts the region of overlap between the current target patch and previously reconstructed high-resolution image,and w contains the values of the previously reconstructed high-resolution image on the overlap.The con-strained optimization(7)can be similarly reformulated as:
min
α
炎火猴
˜Dα−˜y 22+λ α 1,(8)
where˜D=
F D l
βP D h
and˜y=
F y
βw
.The parameterβ
controls the tradeoff between matching the low-resolution input andfinding a high-resolution patch that is compatible with its neighbors.In all our experiments,we simply t β=1.Given the optimal solutionα∗to(8),the high-resolution patch can be reconstructed as x=D hα∗.
2Traditionally,one would ek the sparstαs.t. D lα−y 2≤ .For super-resolution,it is more appropriate to replace this2-norm with a quadratic norm · F T F that penalizes visually salient high-frequency errors.
3There are also some recent works showing certain non-convex optimization problems can produce superior spar solutions to the 1convex , [25]and[26].
4There are different ways to enforce compatibility.In[11],the values in the overlapped regions are simply averaged,which will result in blurring effects. The greedy one-pass algorithm[28]is shown to work almost as well as the u of a full MRF model[9].Our algorithm,not bad on the MRF model, is
esntially the same by trusting partially the previously recovered high resolution image patches in the overlapped regions.Algorithm1(Super-Resolution via Spar Reprentation). 1:Input:training dictionaries D h and D l,a low-resolution
image Y.
2:For each3×3patch y of Y,taken starting from the upper-left corner with1pixel overlap in each direction,
•Compute the mean pixel value m of patch y.
•Solve the optimization problem with˜D and˜y defined
in(8):minα ˜Dα−˜y 22+λ α 1.
•Generate the high-resolution patch x=D hα∗.Put
the patch x+m into a high-resolution image X0. 3:End
4:Using gradient descent,find the clost image to X0 which satisfies the reconstruction constraint:
X∗=arg min
X
SH X−Y 22+c X−X0 22.
5:Output:super-resolution image X∗.
2)Enforcing global reconstruction constraint:Notice that (5)and(7)do not demand exact equality between the low-resolution patch y and its reconstruction D lα.Becau of this,and also becau of noi,the high-resolution image X0produced by the spar reprentation approach of the previous ction may not satisfy the reconstruction constraint (2)exactly.We eliminate this discrepancy by projecting X0 onto the solution space of SH X=Y,computing
X∗=arg min
X
SH X−Y 22+c X−X0 22.(9) The solution to this optimization problem can be efficiently computed using gradient descent.The update equation for this iterative method is
X t+1=X t+ν[H T S T(Y−SH X t)+c(X−X0)],(10) where X t is the estimate of the high-resolution image after the t-th iteration,νis the step size of the gradient descent. We take result X∗from the above optimization as our final estimate of the high-resolution image.This image is as clo as possible to the initial super-resolution X0given by sparsity,while respecting the reconstruction constraint.The entire super-resolution process is summarized as Algorithm1.
3)Global optimization interpretation:The simple SR algo-rithm outlined in the previous two subctions can be viewed as a special ca of a more general spar reprentation framework for inver problems in image processing.Related ideas have been profitably applied in image compression, denoising[19],and restoration[20].In addition to placing our work in a larger context,the connections suggest means of further improving the performance,at the cost of incread computational complexity.
Given sufficient computational resources,one could in prin-ciple solve for the coefficients associated with all patches simultaneously.Moreover,the entire high-resolution image X itlf can be treated as a variable.Rather than demanding that X be perfectly reproduced by the spar coefficientsα,we can penalize the difference between X and the high-resolution image given by the coefficients,allowing solutions that
are not perfectly spar,but better satisfy the reconstruction constraints.This leads to a large optimization problem:
X ∗=arg min X ,{αij }
SH X −Y 2
2+λ
i,j
αij 0+γ
i,j
D h αij −
P ij X 22
+τρ(X ) .
(11)
Here,αij denotes the reprentation coefficients for the (i,j )th patch of X ,and P ij is a projection matrix that lects the (i,j )th patch from X .ρ(X )is a penalty function that encodes additional prior knowledge about the high-resolution image.This function may depend on the image category,or may take the form of a generic regularization term (e.g.,Huber MRF,Total Variation,Bilateral Total Variation).
Algorithm 1can be interpreted as a computationally efficient approximation to (11).The spar reprentation step recovers the coefficients αby approximately minimizing the sum of the cond and third terms of (11).The sparsity term αij 0is relaxed to αij 1,while the high-resolution fidelity term D h αij −P ij X 2is approximated by its low-resolution version F D l αij −F y ij 2.
Notice,that if the spar coefficients αare fixed,the third term of (11)esntially penalizes the difference between the super-resolution image X and the reconstruction given by the coefficients: i,j D h αij −P ij X 22≈ X 0−X 22.Hence,for small γ,the back-projection step of Algorithm 1approximately minimizes the sum of the first and third terms of (11).
Algorithm 1does not,however,incorporate any prior be-sides sparsity of the reprentation coefficients –the term ρ(X )is abnt in our approximation.In Section IV we will e that sparsity in a r
elevant dictionary is a strong enough prior that we can already achieve good super-resolution per-formance.Nevertheless,in ttings where further assumptions on the high-resolution signal are available,the priors can be incorperated into the global reconstruction step of our algorithm.
B.Face super-resolution from Sparsity网易云歌曲
Face image resolution enhancement is usually desirable in many surveillance scenarios,where there is always a large distance between the camera and the objects (people)of interest.Unlike the generic image super-resolution discusd earlier,face images are more regular in structure and thus should be easier to handle.Indeed,for face super-resolution,we can deal with lower resolution input images.The basic idea is first to u the face prior to zoom the input to a reasonable medium resolution,and then to employ the local sparsity prior model to recover details.To be preci,the solution is also approached in two steps:1)global model:u reconstruction constraint to recover a medium high-resolution face image,but the solution is arched only in the face subspace;and 2)local model:u the local spar model to recover the image details.
a)Non-negative matrix factorization:In face super-resolution,the most frequently ud subspace method for mod-eling the human face is Principal Component Analysis (PCA),
which choos a low-dimensional subspace that captures as much of the variance as possible.However,the PCA bas are holistic,and tend to generate smooth faces similar to the mean.Moreover,becau principal component reprentations allow negative coefficients,the PCA reconstruction is often hard to interpret.
Even though faces are objects with lots of variance,they are made up of veral relatively independent parts such as eyes,eyebrows,nos,mouths,checks and chins.Nonnegative Matrix Factorization (NMF)[29]eks a reprentation of the given signals as an additive combination of local features.To find such a part-bad subspace,NMF is formulated as the following optimization problem:
arg min U,V
X −UV 22
三年级下册口算题(12)
where X ∈R n ×m is the data matrix,U ∈R n ×r is the basis
matrix and V ∈R r ×m is the coefficient matrix.In our context here,X simply consists of a t of pre-aligned high-resolution training face images as its column vectors.The number of the bas r can be chon as n ∗m/(n +m )which is smaller than n and m ,meaning a more compact reprentation.It can be shown that a locally optimum of (12)can be obtained via the following update rules:
V ij ←−V ij (U T X )ij
(U T
UV )ij U ki ←−U ki (XV T )ki
(UV V T )ki
,
(13)
where 1≤i ≤r ,1≤j ≤m and 1≤k ≤n .The obtained basis matrix U is often spar and localized.
b)Two step face super-resolution:Let X and Y denote the high resolution and low resolution faces res
pectively.Y is obtained from X by smoothing and downsampling as in Eq.2.We want to recover X from the obrvation Y .In this paper,we assume Y has been pre-aligned to the training databa by either manually labeling the feature points or with some automatic face alignment algorithm such as the method ud in [14].We can achieve the optimal solution for X bad on the Maximum a Posteriori (MAP)criteria,
X ∗=arg max X
p (Y |X )p (X ).
(14)
p (Y |X )models the image obrvation process,usually with Gaussian noi assumption on the obrvation Y ,p (Y |X )=乡音无改鬓毛衰读音
1/Z exp(− SHU c −Y 22/(2∗σ2
))with Z being a nor-malization factor.p (X )is a prior on the underlying high resolution image X ,typically in the exponential form p (X )=exp(−cρ(X )).Using the rules in (13),we can obtain the basis matrix U ,which is compod of spar bas.Let Ωdenote the face subspace spanned by U .Then in
the subspace Ω,the super-resolution problem in (14)can be formulated using the reconstruction constraints as:
c ∗=arg min c
SHU c −Y 22+ηρ(U c )
< ≥0,(15)
where ρ(U c )is a prior term regularizing the high resolution solution,c ∈R r ×1is the coefficient vector in the subspace Ω
