Imagewarping/morphingDigitalVisualEffectsYung-YuChuangwithslidesbyRichardSzeliski,SteveSeitz,TomFunkhouserandAlexeiEfrosImagewarpingImageformationABSamplingandquantizationWhatisanimageWecanthinkofanimageasafunction,f:R2

R:f(x,y)givestheintensityatposition(x,y)definedoverarectangle,withafiniterange:f:[a,b]x[c,d]

[0,1]AcolorimagexyfAdigitalimageWeusuallyoperateondigital(discrete)

images:Samplethe2DspaceonaregulargridQuantizeeachsample(roundtonearestinteger)IfoursamplesareDapart,wecanwritethisas:

f[i,j]=Quantize{f(iD,jD)}TheimagecannowberepresentedasamatrixofintegervaluesImagewarpingimagefiltering:changerangeofimageg(x)=h(f(x))fxhgxfxhgximagewarping:changedomainofimageg(x)=f(h(x))h(y)=0.5y+0.5h(y)=2yImagewarpinghhffggimagefiltering:changerangeofimageg(x)=h(f(x))imagewarping:changedomainofimageg(x)=f(h(x))h(y)=0.5y+0.5h([x,y])=[x,y/2]Parametric(global)warpingtranslationrotationaspectaffineperspectivecylindricalExamplesofparametricwarps:Parametric(global)warpingTransformationTisacoordinate-changingmachine:p’=T(p)WhatdoesitmeanthatTisglobal?Isthesameforanypointpcanbedescribedbyjustafewnumbers(parameters)RepresentTasamatrix:p’=M*pTp=(x,y)p’=(x’,y’)ScalingScalingacoordinatemeansmultiplyingeachofitscomponentsbyascalarUniformscalingmeansthisscalaristhesameforallcomponents:

2fgNon-uniformscaling:differentscalarspercomponent:Scalingx2,

y

0.5ScalingScalingoperation:Or,inmatrixform:scalingmatrixSWhat’sinverseofS?2-DRotationThisiseasytocaptureinmatrixform:Eventhoughsin(q)andcos(q)arenonlineartoq,x’isalinearcombinationofxandyy’isalinearcombinationofxandyWhatistheinversetransformation?Rotationby–qForrotationmatrices,det(R)=1soR2x2MatricesWhattypesoftransformationscanbe

representedwitha2x2matrix?2DIdentity?2DScalearound(0,0)?2x2MatricesWhattypesoftransformationscanbe

representedwitha2x2matrix?2DRotatearound(0,0)?2DShear?2x2MatricesWhattypesoftransformationscanbe

representedwitha2x2matrix?2DMirroraboutYaxis?2DMirrorover(0,0)?All2DLinearTransformationsLineartransformationsarecombinationsof…Scale,Rotation,Shear,andMirrorPropertiesoflineartransformations:OriginmapstooriginLinesmaptolinesParallellinesremainparallelRatiosarepreservedClosedundercomposition2x2MatricesWhattypesoftransformationscannotbe

representedwitha2x2matrix?2DTranslation?Onlylinear2Dtransformationscanberepresentedwitha2x2matrixNO!TranslationExampleoftranslationtx=2

ty

=1HomogeneousCoordinatesAffineTransformationsAffinetransformationsarecombinationsof…Lineartransformations,andTranslationsPropertiesofaffinetransformations:OrigindoesnotnecessarilymaptooriginLinesmaptolinesParallellinesremainparallelRatiosarepreservedClosedundercompositionModelschangeofbasisProjectiveTransformationsProjectivetransformations…Affinetransformations,andProjectivewarpsPropertiesofprojectivetransformations:OrigindoesnotnecessarilymaptooriginLinesmaptolinesParallellinesdonotnecessarilyremainparallelRatiosarenotpreservedClosedundercompositionModelschangeofbasisImagewarpingGivenacoordinatetransformx’

=T(x)andasourceimageI(x),howdowecomputeatransformedimageI’(x’)

=

I(T(x))?I(x)I’(x’)xx’T(x)ForwardwarpingSendeachpixelI(x)toitscorrespondinglocationx’

=

T(x)inI’(x’)I(x)I’(x’)xx’T(x)Forwardwarpingfwarp(I,I’,T){for(y=0;y<I.height;y++)for(x=0;x<I.width;x++){(x’,y’)=T(x,y);I’(x’,y’)=I(x,y);}}II’xx’TForwardwarpingSomedestinationmaynotbecoveredManysourcepixelscouldmaptothesamedestinationForwardwarpingSendeachpixelI(x)toitscorrespondinglocationx’

=

T(x)inI’(x’)f(x)g(x’)xx’h(x)Whatifpixellands“between”twopixels?Willbethereholes?Answer:add“contribution”toseveralpixels,normalizelater(splatting)Forwardwarpingfwarp(I,I’,T){for(y=0;y<I.height;y++)for(x=0;x<I.width;x++){(x’,y’)=T(x,y);

Splatting(I’,x’,y’,I(x,y),kernel);}}II’xx’TInversewarpingGeteachpixelI’(x’)fromitscorrespondinglocationx

=

T-1(x’)inI(x)I(x)I’(x’)xx’T-1(x’)Inversewarpingiwarp(I,I’,T){for(y=0;y<I’.height;y++)for(x=0;x<I’.width;x++){(x,y)=T-1(x’,y’);I’(x’,y’)=I(x,y);}}II’xx’T-1InversewarpingGeteachpixelI’(x’)fromitscorrespondinglocationx

=

T-1(x’)inI(x)Whatifpixelcomesfrom“between”twopixels?Answer:resamplecolorvaluefrominterpolated(prefiltered)sourceimagef(x)g(x’)xx’Inversewarpingiwarp(I,I’,T){for(y=0;y<I’.height;y++)for(x=0;x<I’.width;x++){(x,y)=T-1(x’,y’);

I’(x’,y’)=Reconstruct(I,x,y,kernel);}}II’xx’T-1InversewarpingNohole,butmustresampleWhatvalueshouldyoutakefornon-integercoordinate?Closestone?InversewarpingItcouldcausealiasingReconstructionReconstructiongeneratesanapproximationtotheoriginalfunction.Erroriscalledaliasing.samplepositionsamplevaluesamplingreconstructionReconstructionComputedweightedsumofpixelneighborhood;outputisweightedaverageofinput,whereweightsarenormalizedvaluesoffilterkernelkwidthdcolor=0;weights=0;forallq’sdist<widthd=dist(p,q);w=kernel(d);color+=w*q.color;weights+=w;p.Color=color/weights;

pqTrianglefilterGaussianfilterSamplingbandlimitedReconstructionThereconstructedfunctionisobtainedbyinterpolatingamongthesamplesinsomemannerReconstruction(interpolation)Possiblereconstructionfilters(kernels):nearestneighborbilinearbicubicsinc(optimalreconstruction)Bilinearinterpolation(trianglefilter)AsimplemethodforresamplingimagesNon-parametricimagewarpingSpecifyamoredetailedwarpfunctionSplines,meshes,opticalflow(per-pixelmotion)Non-parametricimagewarpingMappingsimpliedbycorrespondencesInversewarpingP’?Non-parametricimagewarpingP’BarycentriccoordinatePBarycentriccoordinatesNon-parametricimagewarpingBarycentriccoordinateNon-parametricimagewarpingradialbasisfunctionGaussianthinplatesplineImagewarpingWarpingisausefuloperationformosaics,videomatching,viewinterpolationandsoon.Anapplicationofimagewarping:

facebeautificationData-drivenfacialbeautificationFacialbeautificationFacialbeautificationFacialbeautificationTrainingsetFaceimages92youngCaucasianfemale33youngCaucasianmaleFeatureextractionFeatureextractionExtract84featurepointsbyBTSMDelaunaytriangulation->234Ddistancevector(normalizedbythesquarerootoffacearea)BTSMscatterplotforalltrainingfaces234DvectorBeautificationengineSupportvectorregression(SVR)SimilarconcepttoSVM,butforregressionRBFkernelsfb(v)BeautificationprocessGiventhenormalizeddistancevectorv,generateanearbyvectorv’sothatfb(v’)>fb(v)TwooptionsKNN-basedSVR-basedKNN-basedbeautification4.34.55.13.14.65.3vv'SVR-basedbeautificationDirectlyusefbtoseekv’Usestandardno-derivativedirectionsetmethodforminimizationFeatureswerereducedto35DbyPCASVR-basedbeautificationProblems:itsometimesyieldsdistancevectorscorrespondingtoinvalidhumanfaceSolution:addlog-likelihoodterm(LP)LPisapproximatedbymodelingfacespaceasamultivariateGaussiandistributionu’sprojectioninPCAspace’si-thcomponenti-theigenvaluePCAλ1λ2EmbeddingandwarpingDistanceembeddingConvertmodifieddistancevectorv’toanewfacelandmarkAgraphdrawingproblemreferredtoasastressminimizationproblem,solvedbyLMalgorithmfornon-linearminimization1ifiandjbelongtodifferentfacialfeatures10otherwiseDistanceembeddingPostprocessingtoenforcesimilaritytransformforfeaturesoneyesbyminimizingOriginalK=3K=5SVRResults(intrainingset)UserstudyResults(notintrainingset)BypartsfullmoutheyesDifferentdegrees50%100%FacialcollageImagemorphingImagemorphingThegoalistosynthesizeafluidtransformationfromoneimagetoanother.image#1image#2dissolvingCrossdissolvingisacommontransitionbetweencuts,butitisnotgoodformorphingbecauseoftheghostingeffects.Artifactsofcross-dissolving/ImagemorphingWhyghosting?Morphing=warping+cross-dissolvingshape(geometric)color(photometric)morphingcross-dissolvingImagemorphingimage#1image#2warpwarpMorphingsequenceFaceaveragingbymorphingaveragefacesImagemorphingcreateamorphingsequence:foreachtimetCreateanintermediatewarpingfield(byinterpolation)WarpbothimagestowardsitCross-dissolvethecolorsinthenewlywarpedimagest=0t=1t=0.33Anidealexample(in2004)t=0t=1t=0.25t=0.5t=0.75morphingAnidealexamplemiddleface(t=0.5)t=0t=1Warpspecification(meshwarping)Howcanwespecifythewarp?1.Specifycorrespondingsplinecontrolpointsinterpolatetoacompletewarpingfunctioneasytoimplement,butlessexpressiveWarpspecificationHowcanwespecifythewarp2.SpecifycorrespondingpointsinterpolatetoacompletewarpingfunctionSolution:converttomeshwarpingDefineatriangularmeshoverthepointsSamemeshinbothimages!Nowwehavetriangle-to-trianglecorrespondencesWarpeachtriangleseparatelyfromsourcetodestinationHowdowewarpatriangle?3points=affinewarp!JustliketexturemappingWarpspecification(fieldwarping)Howcanwespecifythewarp?SpecifycorrespondingvectorsinterpolatetoacompletewarpingfunctionTheBeier&NeelyAlgorithm

Beier&Neely(SIGGRAPH1992)Singleline-pairPQtoP’Q’:Algorithm(singleline-pair)ForeachXinthedestinationimage:Findthecorrespondingu,vFindX’inthesourceimageforthatu,vdestinationImage(X)=sourceImage(X’)Examples:AffinetransformationMultipleLineslength=lengthofthelinesegment,dist=distancetolinesegmentTheinfluenceofa,p,b.ThesameastheaverageofXi’FullAlgorithmResultingwarpComparisontomeshmorphingPros:moreexpressiveCons:speedandcontrolWarpinterpolationHowdowecreateanintermediatewarpattimet?li