Advances and Challenges in Super

AdvancesandChallengesinSuper-Resolution

SinaFarsiu,

1121

DirkRobinson,MichaelElad,PeymanMilanfar

1

2

ElectricalEngineeringDepartment,UniversityofCalifornia,SantaCruzCA95064

ComputerScienceDepartment,TheTechnion–IsraelInstituteofTechnology,Israel

Received30January2004;accepted15March2004

ABSTRACT:Super-Resolutionreconstructionproducesoneorat

ofhigh-resolutionimagesfromaquenceoflow-resolutionframes.

ThisarticlereviewsavarietyofSuper-Resolutionmethodspropod

inthelast20years,andprovidessomeinsightinto,andasummary

of,ourrecentcontributionstothegeneralSuper-Resolutionproblem.

Intheprocess,adetailedstudyofveralveryimportantaspectsof

Super-Resolution,oftenignoredintheliterature,isprented.Spe-

cifically,wediscussrobustness,treatmentofcolor,anddynamic

operationmodes.Novelmethodsforaddressingtheissuesare

accompaniedbyexperimentalresultsonsimulatedandrealdata.

Finally,somefuturechallengesinSuper-Resolutionareoutlinedand

discusd.

©2004WileyPeriodicals,Inc.IntJImagingSystTechnol,14,

47–57,2004;PublishedonlineinWileyInterScience(.

com).DOI10.1002/ima.20007

Keywords:Super-Resolution;demosaicing;inverproblem;dy-

namicSuper-Resolution;image-reconstruction;robustestimation;

robustregularization

I.INTRODUCTION

Onthequesttoachievehighresolutionimagingsystems,one

quicklyrunsintotheproblemofdiminishingreturns.Specifically,

theimagingchipsandopticalcomponentsnecessarytocapturevery

high-resolutionimagesbecomeprohibitivelyexpensive,costingin

themillionsofdollarsforscientificapplications(Parulskietal.,

1992).Super-resolutionisthetermgenerallyappliedtotheproblem

oftranscendingthelimitationsofopticalimagingsystemsthrough

theuofimageprocessingalgorithms,whichpresumablyare

relativelyinexpensivetoimplement.Theapplicationofsuchalgo-

rithmswillcertainlycontinuetoproliferateinanysituationwhere

high-qualityopticalimagingsystemscannotbeincorporatedorare

tooexpensivetoutilize.

ThebasicideabehindSuper-Resolutionisthefusionofa-

quenceoflow-resolutionnoisyblurredimagestoproduceahigher-

resolutionimageorquence.EarlyworksonSuper-Resolution

showedthatthealiasingeffectsinthehigh-resolutionfudimage

Correspondenceto:S.Farsiu;e-mail:farsiu@

Grantsponsor:ThisworkwassupportedinpartbytheNationalScienceFounda-

tionGrantCCR-9984246,USAirForceGrantF49620-03-1-0387,andbytheNational

ScienceFoundationScienceandTechnologyCenterforAdaptiveOptics,managedby

theUniversityofCaliforniaatSantaCruzunderCooperativeAgreementNo.AST-

9876783.

©2004WileyPeriodicals,Inc.

canbereduced(orevencompletelyremoved),ifarelativesub-pixel

motionexitsbetweentheundersampledinputimages(Huangand

Tsai,1984).However,contrarytothenaivefrequencydomain

descriptionofthisearlywork,weshallethat,ingeneral,super-

resolutionisacomputationallycomplexandnumericallyill-pod

problem.AllthismakesSuper-Resolutiononeofthemostappealing

rearchareasforimageprocessingrearchers.

Althoughveralarticleshavesurveyedthedifferentclassical

Super-Resolutionmethodsandcomparedtheirperformances(e.g.,

BormanandStevenson,1998;KangandChaudhuri,2003),the

intentionofthisarticleistopinpointthevariousdifficultiesinherent

totheSuper-Resolutionproblemforavarietyofapplicationttings

oftenignoredinthepast.Wereviewmanyofthemostrecentand

popularmethods,andoutlinesomeofourrecentworkaddressing

theissues.

Theorganizationofthisarticleisasfollows.InSectionIIwe

studySuper-Resolutionasaninverproblemandaddressrelated

regularizationissues.InSectionIIIweanalyzeageneralmodelfor

imagingsystemsapplicabletovariousscenariosofSuper-Resolu-

tion.InSectionIVwedescribethreedifferentapplicationttings

andourapproachestodealingwiththem.Specifically,weaddress

theproblemofrobustSuper-Resolution,thetreatmentofcolor

imagesandmosaicedsources,anddynamicSuper-Resolution.Fi-

nally,weconcludewithalistofchallengestobeaddresdinfuture

workonSuper-Resolution.

II.SUPER-RESOLUTIONASANINVERSEPROBLEM

Super-resolutionalgorithmsattempttoextractthehigh-resolution

imagecorruptedbythelimitationsoftheopticalimagingsystem.

Thistypeofproblemisanexampleofaninverproblem,wherein

thesourceofinformation(high-resolutionimage)isestimatedfrom

theobrveddata(low-resolutionimageorimages).Solvingan

inverproblemingeneralrequiresfirstconstructingaforward

model.Byfar,themostcommonforwardmodelfortheproblemof

Super-Resolutionislinearinform:

Y͑t͒ϭM͑t͒X͑t͒ϩV͑t͒,(1)

whereYisthemeasureddata(singleorcollectionofimages),M

reprentstheimagingsystem,Xistheunknownhigh-resolution

imageorimages,Vistherandomnoiinherenttoanyimaging

system,andtreprentsthetimeofimageacquisition.Weuthe(X)ϭʈTXʈ

underscorenotationsuchasXtoindicateavector.Inthisformula-

tion,theimageisreprentedinvectorformbyscanningthe2D

imageinarasteroranyotherscanningformatregularizationhasbeenmotivatedfromananalyticstandpointto

1

to1D.

Armedwithaforwardmodel,thepractitionerofSuper-Resolu-

tionmustexplicitlyorimplicitly[e.g.thePOCS-badmethodsof

Pattietal.(1997)]defineacostfunctiontoestimateX(fornowweprovablyuniqueandstablesolution.Often,however,littleattention

ignorethetemporalaspectofSuper-Resolution).Thistypeofcost

functionassuresacertainfidelityorclonessofthefinalsolutionto

themeasureddata.Historically,theconstructionofsuchacost

functionhasbeenmotivatedfromeitheranalgebraicorastatistical

perspective.Perhapsthecostfunctionmostcommontobothper-

spectivesistheleast-squares(LS)costfunction,whichminimizes

theL

2

normoftheresidualvector,

X

ˆ

ϭargmin

J͑X͒ϭargmin.(2)

ʈYϪMXʈ

2

2

XX

ForthecawherethenoiVisadditivewhite,zeromeanGauss-

ian,thisapproachhastheinterpretationofprovidingthemaximum

likelihoodestimateofX(EladandFeuer,1997).Weshallshowin

thispaperthatsuchacostfunctionisnotnecessarilyadequatefor

Super-Resolution.

Aninherentdifficultywithinverproblemsisthechallengeof

invertingtheforwardmodelwithoutamplifyingtheeffectofnoi

inthemeasureddata.Inthelinearmodel,thisresultsfromthevery

high,possiblyinfinite,conditionnumberforthemodelmatrixM.

Solvingtheinverproblem,asthenamesuggests,requiresinvert-

ingtheeffectsofthesystemmatrixM.Atbest,thissystemmatrix

isillconditioned,prentingthechallengeofinvertingthematrixin

anumericallystablefashion(GolubandLoan,1994).Furthermore,

findingtheminimizerof(2)wouldamplifytherandomnoiVin

thedirectionofthesingularvectors(intheSuper-Resolutionca

thearethehighspatialfrequencies),makingthesolutionhighly

nsitivetomeasurementnoi.Inmanyrealscenarios,theproblem

iswornedbythefactthatthesystemmatrixMissingular.Fora

singularmodelmatrixM,thereisaninfinitespaceofsolutions

minimizing(2).Thus,fortheproblemofSuper-Resolution,some

formofregularizationmustbeincludedinthecostfunctionto

stabilizetheproblemorconstrainthespaceofsolutions.

Traditionally,regularizationhasbeendescribedfromboththe

algebraicandstatisticalperspectives.Inbothcas,regularization

takestheformofconstraintsonthespaceofpossiblesolutionsoften

independentofthemeasureddata.Thisisaccomplishedbywayof

Lagrangiantypepenaltytermsasin

J͑X͒ϭʈYϪMXʈ

2

2

ϩ͑X͒.(3)

␭␳

Thefunction(X)posapenaltyontheunknownXtodirectitto

␳

abetterformedsolution.Thecoefficientdictatesthestrengthwith

␭

whichthispenaltyisenforced.Generallyspeaking,choosing

␭

couldbeeitherdonemanually,usingvisualinspection,orautomat-

icallyusingmethodslikegeneralizedcross-validation(Lukas,1993;

Nguyenetal.,2001a)L-curve(HannandO’Leary,1993)and

othertechniques.

1atm

Notethatthisconversionismanticandbearsnolossinthedescriptionoftheisusuallyignoredintheliterature(Farsiu

relationbetweenmeasurementsandidealsignal.etal.,2004a).

48Vol.14,47–57(2004)

Tikhonovregularization,oftheform

␳

2

2

,isawidely

employedformofregularization,whereTisamatrixcapturingsome

aspectoftheimagesuchasitsgeneralsmoothness.Thisformof

justifycertainmathematicalpropertiesoftheestimatedsolution.For

instance,aminimalenergyregularization(TϭI)easilyleadstoa

isgiventotheeffectsofsuchsimpleregularizationonthesuper-

resolutionresults.Forinstance,theregularizationoftenpenalizes

energyinthehigherfrequenciesofthesolution,optingforasmooth

andhenceblurrysolution.Fromastatisticalperspective,regulariza-

tionisincorporatedasaprioriknowledgeaboutthesolution.Thus,

usingthemaximuma-posteriori(MAP)estimator,amuchricher

classofregularizationfunctionsemerges,enablingustocapturethe

specificsoftheparticularapplication[e.g.,SchultzandStevenson

(1996)capturedthepiecewi-constantpropertyofnaturalimages

bymodelingthemasHuber-Markovrandomfielddata].

UnlikethetraditionalTikhonovpenaltyterms,robustmethods

arecapableofperformingadaptivesmoothingbadonthelocal

structureoftheimage.Forinstance,inSectionIV.Aweoffera

penaltytermcapableofprervingthehigh-frequencyedgestruc-

turescommonlyfoundinimages.Theedge-prervingpropertyof

thismethodhasbeenextensivelystudied(Elad,2002;Farsiuetal.,

2004a;Rudinetal.,1992;Sochenetal.,1998).

Inrecentyearstherehasalsobeenagrowingnumberoflearn-

ing-badMAPmethods,wheretheregularization-likepenalty

termsarederivedfromcollectionsoftrainingsamples(Atkinsetal.,

1999;BakerandKanade,2002;HaberandTenorio,2003;Zhuand

Muford,1997).Forexample,inBakerandKanade(2003)anex-

plicitrelationshipbetweenlow-resolutionimagesoffacesandtheir

knownhigh-resolutionimageislearnedfromafacedataba.This

learnedinformationislaterudinreconstructingfaceimagesfrom

low-resolutionimages.Becauoftheneedtogatheravastamount

ofexamples,oftenthemethodsareeffectivewhenappliedtovery

specificscenarios,suchasfacesortext.

Needlesstosay,thechoiceofregularizationplaysavitalrolein

theperformanceofanySuper-Resolutionalgorithm.

III.ANALYSISOFTHEFORWARDMODEL

A.GeneralStructureoftheLinearModel.Inthisction,

wefocusontheconstructionofthemodelmatrixM.Specifically,

weexploretheeffectsofvariousmodelingassumptionsrelating

tothecomputationalefficiencyandperformanceofSuper-Reso-

lutionalgorithms.Primarily,thethreetermsnecessarytocapture

theimageformationprocessareimagemotion,opticalblur,and

thesamplingprocess.Thethreetermscanbemodelledas

paratematricesby

MϭDAHF,(4)

whereFreprentstheintensityconrving,geometricwarpoper-

ationcapturingimagemotion,Histheblurringoperationduetothe

opticalpointspreadfunction

2

(PSF),andDandAreprentthe

effectofsamplingbytheimagensor.WeubothDandAto

2atmatm

AmoregeneralimagingmodelisdefinedasMϭDAHFH,whereHrepre-

ntstheeffectoftheatmosphereandmotionblur(LertrattanapanichandBo,2002).

However,asinconventionalimagingsystems(suchasvideocameras),cameralens/

CCDblurhasmoreimportanteffectthantheatmosphericblur(whichisveryimportant

forastronomicalimages),theeffectofH

Figure1.Blockdiagramreprentationof(4),whereXistheoriginal

high-resolutioncolorimage,Vistheadditivenoi,andYisthe

resultinglow-resolutionblurredcolorfilteredimage.

distinguishbetweenagenericdown-samplingoperation(orCCD

decimationbyafactorr)andthesamplingoperationsspecifictothe

colorspace(colorfiltereffects).Althougheachofthecomponents

couldintheoryvaryintime,formostsituations,thedown-sampling

Figure2.Effectofup-samplingD

T

matrixona3ϫ3imageand

down-samplingmatrixDonthecorresponding9ϫ9up-sampled

image(resolutionenhancementfactorof3).Inthisfigure,togivea

betterintuitiontheimagevectorsarereshapedasmatrices.

andblurringoperationsremainconstantovertime.Figure1illus-

tratestheeffectofeachtermin(4).

Inidealsituationsthemodelingtermswouldcapturetheactual

effectsoftheimageformationprocess.Inpractice,however,the

modelsudreflectacombinationofcomputationalandstatistical

limitations.Forinstance,itiscommontoassumesimpleparametric

space-invariantblurringfunctionsfortheimagingsystem.This

allowsthepractitionertoutilizeefficientandstablealgorithmsfor

estimatinganunknownblurringfunction.Or,thechoiceofresolu-

tionenhancementfactorroftendependsonthenumberofavailable

low-resolutionframes,thecomputationallimitations(exponentialin

r),andtheaccuracyofmotionestimates.Althoughthisapproachis

reasonable,itmustbeunderstoodthatincorrectapproximationscan

leadtosignificantreductioninoverallperformance.

Inourexperience,theperformanceofmotionestimationisof

paramountimportancetotheperformanceofSuper-Resolution.In

fact,weoffertheobrvationthatdifficultiesinestimatingmotion

reprentthelimitingfactorinpracticalSuper-Resolution.Inreality,

performanceofmotionestimationtechniquesishighlydependenton

thecomplexityofactualmotion.Forinstance,estimatingthecom-

pletelyarbitrarymotionencounteredinreal-worldimagescenesis

anextremelydifficulttaskwithalmostnoguaranteesofestimator

performance.Inpractice,incorrectestimatesofmotionhavedisas-

trousimplicationsonoverallSuper-Resolutionperformance(Farsiu

etal.,2004a).Inanotheraspectofourwork,wehavestudied

Figure3.MDSPResolutionEnhancementProgramscreenshot.

Vol.14,47–57(2004)49

fundamentalperformancelimitsforimageregistration(Robinson

andMilanfar,2004).Weshallsaymoreonthistopiclater.

B.ComputationalAspectsofSuper-resolution.

AcharacteristicdifficultyoftheSuper-Resolutionproblemisthe

dimensionalityoftheproblem.Thisdifficultywillbeinfluenced

bothbythedimensionalityoftheunknown,X,andthedimensionof

themeasurementvector,Y,andinbothcasthenumbersinthe

hundredsofthousandsandbeyond.Thedimensionalityoftheprob-

lemdemandshighcomputationalefficiencyofanyalgorithm,ifthe

algorithmistobeofpracticalutility.Onesuchmechanismfor

simplifyingtheproblemofSuper-Resolutioncomesfromacareful

studyofparticularmodelingscenarios.Thisthemeplaysavitalrole

intheworkprentedinthispaper.Thisdimensionalityproblemis

alsothereasonforthepopularityofiterativesolversforthesuper-

resolutionproblemingeneral.

Forthecaofquadraticpenaltyterms(LS)andTikhonov

regularization,thetaskofminimizationisreducedtothatofsolving

averylargelinearsystemofequations.Manynovelandpowerful

algebraictechniqueshavebeenpropodtominimizethecomplex-

ityandmaximizetheperformanceforthisclassofroutines.For

example,Nguyenetal.(2001)propoefficientblockcirculant

preconditionerstoaccelerateconvergenceofaconjugategradient

minimizationalgorithm.Althoughthemethodsaremathemati-

callyjustifiableandnumericallystable,theyoftenbelieadepen-

denceonunrealisticassumptionssuchasperfectmotionestimation.

Asweshallshow,applyingnonquadraticpenaltytermsoffersmuch

inthewayofaccuracyandatthesametimerealizingimportant

speedupsinminimization.

Thespeedupcomesfromtheapplicationofthematrixoperators

F,H,D,A,andtheirtransposdirectlyasthecorrespondingimage

operationsofshifting,blurring,anddecimation(ZometandPeleg,

2000;Farsiuetal.,2004a).Forexample,theoperationofthe

decimation(down-sampling)matrixDanditstranspo(up-sam-

pling)matrixD

T

isillustratedinFigure2.

Applicationofthe

operationsintheimagedomainobviatestheneedtoexplicitly

constructthematrices.

Throughoutthisarticle,wefocusonthesimplestofmotion

models,namelythetranslationalmodel.Thereasonsforthisare

veral.First,thereexistefficientandaccurateestimationalgorithms

withwellstudiedperformancelimits(RobinsonandMilanfar,2004;

LinandShun,2004).Second,althoughsimple,themodelfairlywell

approximatesthemotioncontainedinimagequenceswherethe

sceneisstationaryandonlytheimagingsystemmoves.Third,for

sufficientlyhighframeratesmostmotionmodelscanbe(atleast

locally)approximatedbythetranslationalmodel.Finally,andmost

importantly,webelievethatanin-depthstudyofthissimpleca

allowsmuchinsighttobegainedabouttheproblemsinherentto

Super-Resolution.

Oneinterestingimplicationofthetranslationalmotionmodelis

theabilitytogreatlysimplifythetaskofSuper-Resolution.Ifthe

opticalbluroftheimagingsystemistranslationinvariant,thenthe

orderoftheoperationsoftheimageshiftandimageblurare

commutative(EladandHel-Or,2001).BysubstitutingZϭHX,the

inverproblemmaybeparatedintothemuchsimplersub-tasks

offusingtheavailableimagestoestimatetheblurryimageZ

followedbyadeblurring/interpolationstepestimatingXfromZ,the

ˆ

estimateoftheblurredimage.InSectionIV,wemakeuofthis

propertytoexplainandconstructhighlyefficientSuper-Resolution

algorithms.

50Vol.14,47–57(2004)

IV.RECENTWORK

Inthisction,weexplorethreespecificSuper-Resolutionscenarios,

eachofwhichaddressaparticularaspectofthegeneralsuper-

resolutionchallenge.Also,wehighlightsomeoftheimportant

contributionswehavemadetoeachscenario.Thescenarioshave

emergedfromourefforttocreateageneralSuper-Resolutionsoft-

waretoolcapableofhandlingawidevarietyofinputimagedata.

Figure3showsasamplescreenshotofourSuper-Resolutiontool.

3

Itisourhopethatthisworkprovidesthefoundationforfuturework

addressingthemorecompleteSuper-Resolutionproblem.

A.RobustSuper-resolution.AsindicatedinSectionIII,often

theparametersoftheimagingsystem(suchasmotionandPSF)

mustbeeitherassumedorestimatedfromthedatatoconstructa

forwardmodel.Whenthetermsinthemodelareassumedor

estimatedincorrectly,thedatanolongermatchthemodel,leadingto

dataoutliers.Outliers,whicharedefinedasdatapointswithdiffer-

entdistributionalcharacteristicsthantheassumedmodel,willpro-

duceerroneousestimateswhenanonrobustalgorithmisapplied.We

havepreviouslyaddresd(Farsiuetal.,2003a,2004a)theproblem

ofestimatingasinglehigh-resolutionmonochromeimageXfroma

collectionoflowresolutionimagesY(t).

Drawingonthetheoryofrobuststatistics(Huber,1981),wehave

developedanovelframeworkcombiningarobustdatafidelityterm

androbustregularizationtermtobuildanefficientSuper-Resolution

frameworkexhibitingimprovedperformanceforreal-worldimage

quences.Ithasbeenshown(Huber,1981)thattheLStype

estimatorof(2)ishighlysusceptibletotheprenceofoutliersin

thedata,producingquitepoorresults.Thelackofrobustnessis

attributedtotheuoftheL

2

normtomeasuredatafidelity,which

isonlyoptimalforthecaofGaussiannoi.Astatisticalstudyof

thenoipropertiesfoundinmanyrealimagequences,however,

suggestsaheavy-tailednoidistributionsuchasLaplacian(Farsiu

etal.,2003b).InsteadofLS,wepropoanalternatedatafidelity

termbadontheL

1

norm,whichhasbeenshowntobeveryrobust

todataoutliers.Also,wepropoanovelregularizationtermcalled

Bilateral-TV,whichprovidesrobustperformancewhileprerving

theedgecontentcommontorealimagequences.Thepropod

methodisageneralizationoftheTotalVariationprincipleofRudin

etal.(1992),whichhasbeenpropodasanedge-prervingreg-

ularizationterm.

Combiningthetwoterms,weformulateourrobustestimation

frameworkasthefollowingcostfunction

4

J͑X͒ϭ

΄

͸

ʈD͑t͒H͑t͒F͑t͒XϪY͑t͒ʈ

1

t

ϩʈXϪS

␭␣

lϭϪPmϭ0

͸͸

PP

͉m͉ϩ͉l͉

lm

xy

SXʈ,(5)

1

lϩmՆ0

΅

3

AllthemultiframeSuper-Resolutionmethods(robust,color,demosaic,dynamic)

discusdinthisctionplusmanyotherSuper-Resolutionandmotionestimation

methodshavebeenincludedinoursoftwarepackage.Moreinformationonthissoftware

toolisavailableat/ϳmilanfar

4

Inthisctionweonlyconsidertheresolutionenhancementproblemformono-

chromaticimages.Later,inSectionIV.B,weextendthismethodforthecaofcolor

Super-Resolution.

wherethefirstexpressionisrelatingthemeasurementstothedesired

imageXthroughthemodelwedescribed.S

lm

xy

andSaretheoperators

correspondingtoshiftingtheimagereprentedbyXbylpixelsin

thehorizontaldirectionandmpixelsintheverticaldirection,re-

spectively.Theactasderivativesacrossmultiplescales.The

scalarweight

␣␣

,0ϽϽ1,isappliedtogiveaspatiallydecaying

effecttothesummationoftheregularizationterm.Theshiftingand

differencingoperationsareverycheaptoimplement.

AsmentionedinSectionII,forthespecialcaoftranslational

motionandcommonspaceinvariantblurringoperation,wherethe

blurandmotionoperatorscommute,wesuggestaveryefficient

two-stagemethodforminimizing(5).Theoptimalityofthismethod

wasextensivelydiscusdin(Farsiuetal.,2004a).Thefirststage

estimatestheblurryhigh-resolutionimageZfromthecollectionof

lowresolutionimagesas

Z

ˆ

ϭargmin

ʈDF͑t͒ZϪY͑t͒ʈ

1

Z

ͫ

͸

t

ͬ

.(6)

Weshowed(Farsiuetal,2004a)thatforagivenhigh-resolution

pixelthiscostfunctionisminimizedbyperformingapixel-wi

medianofallthemeasurementsafterproperzerofillingandmotion

compensation.WecallthisoperationMedianShift-And-Add,which

bearssomesimilaritytothemedian-badalgorithmpropodby

Zometetal.(2001).

Thecondstageofdeblurring/interpolatingtheimageZis

ˆ

performedusinganiterativeminimizationmethod.Thisstepisboth

adeblurringandinterpolationstepbecauitispossibletohaveno

measurementsassociatedwithsomepixelsintheimageZdefinedon

ˆ

thehigh-resolutiongrid.Thefollowingexpressionformulatesour

minimizationcriterionforobtainingXfromZ:

ˆˆ

X

ˆˆ

ϭargminʈB͑HXϪZ͒ʈ

1

X

΄

ϩʈXϪS

␭␣

͉m͉ϩ͉l͉

lϭϪPmϭ0

͸͸

PP

lm

xy

SXʈ.(7)

1

lϩmՆ0

΅

Again,weethatthefirsttermencouragesarobustfidelitytothe

fudimageZandthecondtermreprentstherobustregulariza-

ˆ

tionterm.Here,thematrixBisadiagonalmatrixwithdiagonal

valuesequaltothesquarerootofthenumberofmeasurementsthat

contributed.ThisweightingensuresthattomakeeachelementofZ

ˆ

pixelsofZthathavemoremeasurementsareweightedhigherthan

ˆ

thothathavelittleornomeasurements.

Asanexample,Figure4(a)showsoneof55imagescaptured

withacommercialwebcamera.Inthisquence,twoparate

sourcesofmotionwereprent.First,randomlyshakingthecamera

introducedapproximatelyglobaltranslationalmotionbetweeneach

frame.Second,thealpacastatuewasrepositionedveraltimes

throughouttheinputframes[noticethisrelativemotioninFigs.4(a)

and4(b)].ThenonrobustL

2

normreconstructionwithTikhonov

regularizationresultsinFigure4(d)wheretheshadow-likeartifacts

toleftofthealpacaduetothealpacamotionareapparent.The

robustestimationmethods,however,revealtheabilityofthealgo-

rithmtoremovesuchartifactsfromtheimageasshowninFigures

4(e)and4(f).Here,wealsoethattheperformanceofthefaster

methodshowninFigure4(f)isalmostasgoodastheoptimal

methodshowninFigure4(e).

B.RobustMultiframeDemosaicingandColorSuper-Res-

olution.Thereisverylittleworkaddressingtheproblemofcolor

Super-Resolution,andthemostcommonsolutioninvolvesapplying

monochromeSuper-Resolutionalgorithmstoeachofthecolorchan-

nelsindependently(TomandKatsaggelos,2001).Anotherapproach

istransferringtheproblemtoadifferentcolorspacewherechromi-

nancelayersareparatedfromluminance,andwhereSuper-Res-

olutionisappliedtotheluminancechannelonly(IraniandPeleg,

1991).Inthisction,wereviewtheworkofFarsiuetal.(2004),

whichdetailstheproblemsinherenttocolorSuper-Resolutionand

proposanovelalgorithmforproducingahigh-qualitycolorimage

fromacollectionoflow-resolutioncolor-filteredimages.

Acolorimageisreprentedbycombiningthreeparatemono-

chromaticimages.Ideally,eachpixelreflectsthreedatameasure-

ments:oneforeachofthecolorbands.Inpractice,toreduce

productioncost,manydigitalcamerashaveonlyonecolormeasure-

ment(red,green,orblue)perpixel.Thedetectorarrayisagridof

CCDs,eachmadensitivetoonecolorbyplacingacolorfilter

array(CFA)infrontoftheCCD.TheBayerpatternshownonthe

left-handsideofFigure5isaverycommonexampleofsuchacolor

filter.Thevaluesofmissingcolorbandsateverypixelareoften

synthesizedusingsomeformofinterpolationfromneighboring

pixelvalues.Thisprocessisknownascolordemosaicing.

Numeroussingle-framedemosaicingmethodshavebeenpro-

podthroughtheyears(e,e.g.,Alleyssonetal.,2002;Hel-Orand

Keren,2002;KerenandOsadchy,1999;Kimmel,1999;Laroche

andPrescott,1994),yetalmostnoneofthem[butZometandPeleg’s

(2002)method]todatearedirectlyapplicabletotheproblemof

multiframecolordemosaicing.Infact,thegeometryofthesingle-

frameandmulti-framedemosaicingproblemsarefundamentally

different,makingitimpossibletosimplycross-applytraditional

demosaicingalgorithmstothemultiframesituation.Tobetterun-

derstandthemultiframedemosaicingproblem,weofferanexample

forthesimplecaoftranslationalmotion.Figure5illustratesthe

patternofnsormeasurementsinthehigh-resolutionimagegrid.In

suchsituations,thesamplingpatternisquitearbitrarydependingon

therelativemotionofthelow-resolutionimages.Thisnecessitatesa

differentdemosaicingalgorithmthanthodesignedfortheoriginal

Bayerpattern.

ThechallengeofmultiframecolorSuper-Resolutionismuch

moredifficultthanthatofmonochromeimagingandshouldnotbe

solvedbyapplyingmonochromemethodsforveralreasons.First,

theadditionaldown-sampling(matrixA)ofeachcolorchanneldue

tothecolorfilterarraymakestheindependentreconstructionofeach

channelmuchharder.Formanysituations,theinformationcon-

tainedinasinglecolorchannelisinsufficienttosolvesuchahighly

ill-podproblem,andthereforeacceptableperformanceisvirtually

impossibletoachieve.Second,therearenaturalcorrespondences

betweenthecolorchannelsthatshouldbeleveragedduringthe

reconstructionprocess.Third,thehumanvisualsystemisvery

nsitivetocertainartifactsincolorimageswhichcanonlybe

avoidedbyprocessingallofthecolorchannelstogether.Merely

applyingasimpledemosaicingalgorithmpriortoSuper-Resolution

wouldonlyamplifysuchartifactsandleadtosuboptimalperfor-

Vol.14,47–57(2004)51

Figure4.Resultsofdifferentresolutionenhancementmethodsappliedtothealpacaquence.Outliereffectsareapparentinthenonrobust

reconstructionmethod(d).However,therobustmethods(e)–(f)werenotaffectedbytheoutliers.

mance.Instead,allthreechannelsmustbeestimatedsimultaneouslyction,thefasttwo-stagemethodforthecaofconstant,space-

tomaximizetheoverallcolorSuper-Resolutionperformance.invariantblurandglobaltranslationisalsoapplicabletothemulti-

Wepropod(Farsiuetal.,2004),acomputationallyefficient

methodtofuanddemosaicatoflow-resolutioncolorframesAddoperationonBayer-filteredlow-resolutiondatafollowedbya

(whichmayhavebeencolorfilteredbyanyCFA)resultinginacolordeblurringstep.Thus,thefirststageofthealgorithmistheMedian

imagewithhigherspatialresolutionandreducedcolorartifacts.ToShift-And-Addoperationofproducingablurryhigh-resolutionim-

addressthechallengesspecifictocolorSuper-Resolution,additionalageZ

regularizationpenaltyfunctionsarerequired.Tofacilitatetheex-

planation,wereprentthehigh-resolutioncolorchannelsasX

GB

,X,

andX

R

.Thefinalcostfunctionconsistsofthefollowingterms:

1)DataFidelity:Again,wechooadatafidelitypenaltyterm

usingtheL

1

normtoaddrobustness:

framedemosaicingmethod,leadingtoaninitialMedianShift-And-

ˆ

R,G,B

(e.g.,theleftsideoftheaccoladeinFig.5).Inthisca,

however,themedianoperationisappliedinapixel-wifashionto

eachofthecolorchannelsindependently(formoredetails,e

Farsiuetal.,2004).

2)LuminanceRegularization:Here,weuapenaltytermreg-

ularizingtheluminancecomponentofthehigh-resolution

imageinsteadofeachcolorchannelparately.Thisisbe-

cauthehumaneyeismorensitivetothedetailsinthe

luminancecomponentofanimagethanthedetailsinthe

chrominancecomponents(Hel-OrandKeren,2002).There-

fore,weapplytheBilateral-TVregularizationtothelumi-

nancecomponenttoofferrobustedgeprervation.Thelu-

minanceimagecanbecalculatedastheweightedsumX

L

J͑X͒ϭH͑t͒F͑t͒X,

iϭR,G,Btϭ1

͸

͸

N

ʈ͑D͑t͒AϪY͑t͒͒ʈ

iii1

whereA

ii

andY(t)arethered,green,orbluecomponentsofthecolor

filterandthelow-resolutionframe,respectively.Asintheprevious

52Vol.14,47–57(2004)

JSX.(8)

1LL1

͑X͒ϭʈXϪSʈ

lϭϪPmϭ0

͸͸

PP

␣

͉m͉ϩ͉l͉

lm

xy

lϩmՆ0

Figure5.Fusionof7Bayerpatternlow-resolutionimageswithrelative

translationalmotion(thefiguresintheleftsideoftheaccolade)resultsin

ˆ

)thatdoesnotfollowaBayerpattern(theahigh-resolutionimage(Z

figureintherightsideoftheaccolade).Thesymbol“?”reprentsthe

high-resolutionpixelvaluesthatwereundeterminedaftertheShift-And-

Addstep(asaresultofinsufficientlow-resolutionframes).

3)ChrominanceRegularization:Thispenaltytermensuresthe

smoothnessinthechrominancecomponentsofthehigh-

resolutionimage.Thisremovesmanyofthecolorartifacts

objectionabletothehumaneye.Again,thetwochrominance

channelsX

C1C2

andXcanbecalculatedastheweighted

combinationoftheRGBimagesusingtheweights(Ϫ0.169,

Ϫ0.331,0.5)forC1and(0.5,Ϫ0.419,Ϫ0.081)forC2(Pratt,

2001).Asthehumaneyeislessnsitivetothechrominance

channelresolution,itcanbesmoothedmoreaggressively.

Therefore,thefollowingregularizationisanappropriate

methodforsmoothingthechrominanceterm:

22

J

2C1C2

͑X͒ϭʈ⌳Xʈϩʈ⌳Xʈ

22

,(9)

where⌳isthematrixrealizationofahigh-passoperatorsuchasthe

Laplacianfilter.

4)OrientationRegularization:Thistermpenalizesthenonho-

mogeneityoftheedgeorientationacrossthecolorchannels.

Althoughdifferentbandsmayhavelargerorsmallergradient

magnitudesataparticularedge,itisreasonabletoassumethat

ϭ0.299Xϩ0.597Xϩ0.114X

RGB

asexplainedbyPratt

(2001).Theluminanceregularizationtermissimilarto(5)in

SectionIIIA:

Figure6.Ahigh-resolutionimage(a)ispasdthroughourmodelofcameratoproduceatoflow-resolutionimages.Oneofthe

low-resolutionimages,demosaicedbyLarocheandPrescott’s(1994)method,isshownin(b).Theresultofsuper-resolvingeachcolorband

parately,consideringonlybilateralregularization,isshownin(c).And,finally,(d)istheresultofapplyingthepropodmethodtothisdatat

(factorof4resolutionenhancement).

Vol.14,47–57(2004)53

allcolorchannelshavethesameedgeorientation.Thatis,if

avertical(orhorizontal)edgeappearsintheredband,a

vertical(orhorizontal)edgewithsimilarorientationinthe

samelocationislikelytoappearinthegreenandbluebands.

FollowingKerenandOsadchy(1999),minimizingthevector

productnormofanytwoadjacentcolorpixelsforcesdifferent

bandstohavesimilaredgeorientation.Withsomemodifica-

tionstowhatwaspropodbyKerenandOsadchy(1999),

ourorientationpenaltytermisadifferentiablecostfunction:

11

JSXSXSX

3GBBGBR

͑X͒ϭ͑ʈXJSϪXJSʈϩʈXJS

lϭϪ1mϭ0

͸͸

llm2lmm

xyxy2xy

lϩmՆ0

ϪXJSϩʈXJS͉ʈϪXJS͒(10)

RRRBGG

l2lmlm2m

XSXSXS

xy2xyxy2

whereJistheelement-by-elementmultiplicationoperator.

Theoverallcostfunctionisthesummationofthecostfunctions

describedintheprevioussubctions:

X

ˆ

ϭargmin

͓J͑X͒ϩ͑X͒ϩ͑X͒ϩ͑X͔͒.(11)

␭␭␭

112233

JJJ

X

Wepreviouslypropod(Farsiuetal.,2004)amethodforapplying

asteepestdescentalgorithmtominimizethiscostfunction.Inter-

estingly,thiscostfunctioncanalsobeappliedtocolorimageswhere

anunknowndemosaicingalgorithmhasalreadybeenappliedprior

totheSuper-Resolutionprocess.

Figure6illustratestheperformanceofthepropodmethodwith

respecttoothermethods.Figure6(a)showsanimageacquiredwith

ahigh-resolution3-CCDcamera.Atof10low-resolutioncolor

filteredimageswasconstructedfollowingtheforwardimaging

modeltosimulatetheeffectofimagingwithalow-resolutionsingle

CCDBayer-CFAcamera.Figure6(b)showsoneoftheimages

demosaicedbythemethodofLarocheandPrescott(1994),whichis

employedinKodakDCS-200digitalcameras(Ramanathetal.,

2002).InFigure6(c)themethodofFarsiuetal.(2004a)isudto

futheimagesandincreatheresolutionbyafactorof4ineach

colorband,independently.Thecolorartifactsarestillapparentin

thisresult.Theresultofapplyingourmethodonthisquenceis

showninFigure6(d),wherecolorartifactsaresignificantlyreduced.

Asmentionedearlier,thatthismethodmayalsobeappliedtoa

tofcolorlow-resolutionframespreviouslydemosaicedtoenhance

theirspatialresolutionwhilereducingcolorartifacts.Figure7offers

anexampleofthisapplicationonarealdataquencecourtesyof

AdyoronIntelligentSystemsLtd.,TelAviv,Israel.Theavailable

colorimageswerepreviouslydemosaicedusinganunknownalgo-

rithm.Clearly,thecolorartifactsarereducedusingourmethod.

C.DynamicSuper-Resolution.Inthisctionweaddressthe

computationalchallengesinherenttodynamicSuper-Resolution.By

dynamicSuper-Resolution,werefertothesituationinwhicha

quenceofhigh-resolutionimagesareestimatedfromaquence

oflow-resolutionframes.Althoughitmayappearthatthisproblem

isasimpleextensionofthestaticSuper-Resolutionsituation,the

memoryandcomputationalrequirementsforthedynamiccaare

sotaxingastoprecludeitsapplicationwithouthighlyefficient

algorithms.Wereviewthemethodintroducedpreviously(Farsiuet

al.,2004b),whichoffersanextremelyefficientrecursivealgorithm

54Vol.14,47–57(2004)

Figure7.Multi-framecolorSuper-Resolutionimplementedona

real-worlddataquence.(a)showsoneoftheinputlow-resolution

imagesand(b)istheresultofimplementingthepropodmethod

whichhasincreadthespatialresolutionbyafactorof4,removed

thecompressionartifacts,andalsoreducedthecolorartifacts.

fordynamicSuper-Resolution.Althoughsucharecursivesolution

forSuper-Resolutionhasbeenaddresdbefore(EladandFeuer,

1999),wenowshowthespeedupsapplicableforthecaoftrans-

lationalmotionandcommonspace-invariantblur.Thissimplified

modelempowersustouthetwostepalgorithmthatwasdescribed

inSectionIV.Aforsolvingthedynamicca.

Accordingto(1),wetuptheforwardmodelofthedynamic

Super-Resolutionproblemas

Y͑t͒ϭDH͑t͒F͑t͒X͑t͒ϩV͑t͒.(12)

Anefficientandintuitiveapproachofacquiringthehigh-resolu-

tionimageisusingweightedleastsquareoptimization(Eladand

Feuer,1999):

NϪ1

X

ˆ

͑t͒ϭargmin

␥␶␶

␶

ʈDHF͑tϪ͒X͑t͒ϪY͑tϪ͒ʈ

T

2

2

,(13)

X

ͫͬ

␶

͸

ϭ0

whereisaparameterbetween0and1.Theweighting

␥␥

␶

places

moreemphasisonrecentimagedatathanonpreviousdata.Notethat

inordertoconsiderthevaryingreliabilityofmeasurementsgatheredallowstheiterativedeblurringalgorithmtoconvergeinonlyafew

ateachlocation,theweightingcanalsobeappliedonapixel-by-steps.

pixelbasis[(Farsiuetal.,2004b)].WeutheLFigure8showsanexampleofthedynamicSuper-Resolution

2

normtofollow

EladandFeuer’s(1999)model(arobustdatafusiontermusingL

1

normminimizationispartofourongoingwork).

Asbefore,wefirstconsidertheestimationoftheunknownblurry

high-resolutionimageZ(t)beforeconsideringthetaskofdeblurring.

Forthisformulation,wehaveshown(Farsiuetal.,2004)thatthe

updateoftheblurryhigh-resolutionestimateisgivenbytherecur-

siveequation(14)below.Notethatonlythopixelsinthehigh-

resolutionimagethathavenewmeasurementsfromY(t)areupdated,indevelopingagenericSuper-Resolutionalgorithmcapableof

andallotherpixelsareleftunaltered.Thepixelsthatsatisfythis

criterion(indexedbym)areupdatedaccordingto

͓Z͑t͔͒

1

mmm

ϭ͓Dϩ͓F͑t͒Z͑tϪ1͔͒

␤

m