IEICETRANS.INF.&SYST.,VOL.???JULY ,NO.??????
`
`PAPERSpecialIssueonMachineVisionApplications
`RandomizedAdaptiveAlgorithmsforMosaicingSystems(cid:3)
`FrankNIELSENy,Nonmember
`SUMMARY Givenasetofstillimagestakenfromahand-
`isthatwecaninterpretthecompositestitchingasthe
`heldcamera,wepresentafastmethodformosaicingtheminto
`imagethatwouldhavebeentakenbyabiggersensing
`asingleblendedpicture.Wedesigntime-andmemory-e(cid:14)cient
`device(e.g.,CCD).
`stillimagemosaicingalgorithmsbasedongeometricpointfea-
`Therearetwowidelyusedtechniquesthathave
`turematchingsthatcanhandlebotharbitraryrotationsandlarge
`beenusedsofarinthepastformosaicing:the(cid:12)rstone
`zoomfactors.Wediscussextensionsofthemethodologytore-
`latedproblemsliketherecoveringoftheepipolargeometryfor
`consistsofimageregistrationwherethecollineationis
` dreconstructionandobjectrecognitiontasks.
`oftenrestrictedtosimilitudesontheplane(id.trans-
`keywords:
`imageprocessing,registration,warping,mosaicing,
`lation,rotationandscaling).Localimageregistra-
`pointpatternmatching,bucketting
`tionisusuallyeitherperformedbygradientdescentor
`Levenberg-Marquadtoptimizationprocedure.Global
` .
`Introduction
`imageregistrationisreached(sometimes)byhierar-
`chicalmatchingusingpyramidalimagerepresentation.
`Mosaicing(alsocalledimagestitching)consistsoftak-
`ThesecondmethodisbasedonFourierprinciplesandis
`ingasequenceofstillimagepicturesandprovidinga
`calledthephasecorrelationmethod.Thistechniquees-
`collectionoftransformationstojoin/mergetheminto
`timatesaglobaldtranslationbycomputingthephase
`oneblendedpicture(seeFigure and ).Manysoft-
`di(cid:11)erencesoftherespectiveimagefrequencysignalsbut
`warecompaniesalreadyproposestitchersforcreat-
`losestheperspectiveinformationasitgoestothefre-
`ingpanoramasandbrowsersfornavigatingthrough
`quencydomain.Moreoverforlargerotationsordi(cid:11)er-
`themviaenvironmentmaps(image-basedrendering
`entzoomscales,thismethodfails.SzeliskiandShum
`systems).Basically,thoseprogramsproceedasfollows:
`presentedanelegantandrobustmethodforcreating
`( )(cid:12)ndoraskforcameraparameters,()warpimages
`fullmosaicsandtexturingthemontoapolyhedron[],
`accordingtotheseparameters(linesbendtoquadratic
`givenroughimagematchings.
`curves)and( )stitchimagesbymeansofa d-ord-
`Ourproposedfullyautomaticmethodhandles
`translationandeventuallysmalltilting,and()adjust
`largezoom((cid:24)=(cid:2) )andarbitraryrotationvalueswhile
`andblendcolorintensities.Panoramicimagesdonot
`keepingtherunningtimeattractiveforresponsiveap-
`preservelines.Wereferthereadertothecoursenote[]
`plications.Itscurrentlimitations,asdiscussedinsec-
`foranup-to-datesurveyonimageregistrationandim-
`tion,aremostlyduetothedetectionofreliablefea-
`agewarpingtechniques.
`tures(sometimescalled\repeatable"or\stable"fea-
`Inthispaper,weconsiderperspectivemosaicing
`tures)inimageshavinglargedi(cid:11)erentscalingsrather
`wherestraightnessoflinesispreserved.Ourmethodis
`thanthematchingprocessinitself.Indeed,ourmethod
`automaticanddoesnotassumeanyuserinputnorany
`isbasedonplanarpointsetpatternmatchinghaving
`aprioriknowledgeofthecameraparameters.Images
`agivenprecisiontolerance.Asthezoomrangegrows,
`canalsobetakenbyseveralpinholecamerashaving
`saylinearly,thetolerancewindowneedsmorethanlin-
`di(cid:11)erentintrinsic/extrinsicparameters.Inthecaseof
`eargrowthbecauseofthedetectedfeatureimprecisions.
`imagestakenbyanidealpinhole-modelcamerafrom(a)
`OurmethodisbasedonMonte-Carlo/LasVegasalgo-
`thesamethree-dimensionalviewpointor(b)aplanar
`rithmsthatcombinebothrandomizationandgeometric
`surfacetakenfromtwodi(cid:11)erentviewpoints,thetrans-
`featureselection.
`formationsrelatedtheseimagesareknowntobehomo-
`Mosaicingisacoretechnologyusedincomposite
`graphies(alsocalledcollineations[ ]),lineartransfor-
`scanning,image-basedrendering(e.g.,newviewgener-
`mationsde(cid:12)neduptoascalarfactor,intheprojective
`ationwithouthaving(cid:12)ne dmodeldescription),high-
`planeP.Akeydi(cid:11)erencefrompanoramicmosaicing
`de(cid:12)nitionpictures,imagecompression,imagestabiliza-
`tion,etc.Stillimagemosaicingtechniqueslargelydi(cid:11)er
`Manuscriptreceived stOctober
`fromvideomosaicingtechniques[]becausenovideo
`Manuscriptrevised thJanuary
`stream(optical(cid:13)ow)isgivenfortrackinglocallypoints
`ySonyComputerScienceLaboratoriesInc,FRL
`(cid:3)ThispaperwaspresentedatMVA' ,Pages - ,
`ofinterestinaprescribedwindow.Inthispaper,we
`concentrateoure(cid:11)orton(cid:12)ndingthoseglobalfeature
`ISBN- - - (alsoavailableastechnicalreport
`SCSL-TR- - |see[ ])
`
`Prime Focus Ex 1039-1
`Prime Focus v Legend3D
`IPR2016-01243
`
`
`
`PAPERSpecialIssueonMachineVisionApplications
`RandomizedAdaptiveAlgorithmsforMosaicingSystems(cid:3)
`FrankNIELSENy,Nonmember
`SUMMARY Givenasetofstillimagestakenfromahand-
`isthatwecaninterpretthecompositestitchingasthe
`heldcamera,wepresentafastmethodformosaicingtheminto
`imagethatwouldhavebeentakenbyabiggersensing
`asingleblendedpicture.Wedesigntime-andmemory-e(cid:14)cient
`device(e.g.,CCD).
`stillimagemosaicingalgorithmsbasedongeometricpointfea-
`Therearetwowidelyusedtechniquesthathave
`turematchingsthatcanhandlebotharbitraryrotationsandlarge
`beenusedsofarinthepastformosaicing:the(cid:12)rstone
`zoomfactors.Wediscussextensionsofthemethodologytore-
`latedproblemsliketherecoveringoftheepipolargeometryfor
`consistsofimageregistrationwherethecollineationis
` dreconstructionandobjectrecognitiontasks.
`oftenrestrictedtosimilitudesontheplane(id.trans-
`keywords:
`imageprocessing,registration,warping,mosaicing,
`lation,rotationandscaling).Localimageregistra-
`pointpatternmatching,bucketting
`tionisusuallyeitherperformedbygradientdescentor
`Levenberg-Marquadtoptimizationprocedure.Global
` .
`Introduction
`imageregistrationisreached(sometimes)byhierar-
`chicalmatchingusingpyramidalimagerepresentation.
`Mosaicing(alsocalledimagestitching)consistsoftak-
`ThesecondmethodisbasedonFourierprinciplesandis
`ingasequenceofstillimagepicturesandprovidinga
`calledthephasecorrelationmethod.Thistechniquees-
`collectionoftransformationstojoin/mergetheminto
`timatesaglobaldtranslationbycomputingthephase
`oneblendedpicture(seeFigure and ).Manysoft-
`di(cid:11)erencesoftherespectiveimagefrequencysignalsbut
`warecompaniesalreadyproposestitchersforcreat-
`losestheperspectiveinformationasitgoestothefre-
`ingpanoramasandbrowsersfornavigatingthrough
`quencydomain.Moreoverforlargerotationsordi(cid:11)er-
`themviaenvironmentmaps(image-basedrendering
`entzoomscales,thismethodfails.SzeliskiandShum
`systems).Basically,thoseprogramsproceedasfollows:
`presentedanelegantandrobustmethodforcreating
`( )(cid:12)ndoraskforcameraparameters,()warpimages
`fullmosaicsandtexturingthemontoapolyhedron[],
`accordingtotheseparameters(linesbendtoquadratic
`givenroughimagematchings.
`curves)and( )stitchimagesbymeansofa d-ord-
`Ourproposedfullyautomaticmethodhandles
`translationandeventuallysmalltilting,and()adjust
`largezoom((cid:24)=(cid:2) )andarbitraryrotationvalueswhile
`andblendcolorintensities.Panoramicimagesdonot
`keepingtherunningtimeattractiveforresponsiveap-
`preservelines.Wereferthereadertothecoursenote[]
`plications.Itscurrentlimitations,asdiscussedinsec-
`foranup-to-datesurveyonimageregistrationandim-
`tion,aremostlyduetothedetectionofreliablefea-
`agewarpingtechniques.
`tures(sometimescalled\repeatable"or\stable"fea-
`Inthispaper,weconsiderperspectivemosaicing
`tures)inimageshavinglargedi(cid:11)erentscalingsrather
`wherestraightnessoflinesispreserved.Ourmethodis
`thanthematchingprocessinitself.Indeed,ourmethod
`automaticanddoesnotassumeanyuserinputnorany
`isbasedonplanarpointsetpatternmatchinghaving
`aprioriknowledgeofthecameraparameters.Images
`agivenprecisiontolerance.Asthezoomrangegrows,
`canalsobetakenbyseveralpinholecamerashaving
`saylinearly,thetolerancewindowneedsmorethanlin-
`di(cid:11)erentintrinsic/extrinsicparameters.Inthecaseof
`eargrowthbecauseofthedetectedfeatureimprecisions.
`imagestakenbyanidealpinhole-modelcamerafrom(a)
`OurmethodisbasedonMonte-Carlo/LasVegasalgo-
`thesamethree-dimensionalviewpointor(b)aplanar
`rithmsthatcombinebothrandomizationandgeometric
`surfacetakenfromtwodi(cid:11)erentviewpoints,thetrans-
`featureselection.
`formationsrelatedtheseimagesareknowntobehomo-
`Mosaicingisacoretechnologyusedincomposite
`graphies(alsocalledcollineations[ ]),lineartransfor-
`scanning,image-basedrendering(e.g.,newviewgener-
`mationsde(cid:12)neduptoascalarfactor,intheprojective
`ationwithouthaving(cid:12)ne dmodeldescription),high-
`planeP.Akeydi(cid:11)erencefrompanoramicmosaicing
`de(cid:12)nitionpictures,imagecompression,imagestabiliza-
`tion,etc.Stillimagemosaicingtechniqueslargelydi(cid:11)er
`Manuscriptreceived stOctober
`fromvideomosaicingtechniques[]becausenovideo
`Manuscriptrevised thJanuary
`stream(optical(cid:13)ow)isgivenfortrackinglocallypoints
`ySonyComputerScienceLaboratoriesInc,FRL
`(cid:3)ThispaperwaspresentedatMVA' ,Pages - ,
`ofinterestinaprescribedwindow.Inthispaper,we
`concentrateoure(cid:11)orton(cid:12)ndingthoseglobalfeature
`ISBN- - - (alsoavailableastechnicalreport
`SCSL-TR- - |see[ ])
`
`Prime Focus Ex 1039-1
`Prime Focus v Legend3D
`IPR2016-01243
`
`
`
`
`correspondencese(cid:14)ciently.
`.Feature-basedmosaicing
`LetI andIbetwopicturestakenfromthesame
`opticalcenter.We(cid:12)rststartbydetectinggeomet-
`ricfeature(points,edges,triplejunctions,etc.)
`sets
`S =fL ;:::;Ln g(n =jS j)andS=fR ;:::;Rng
`(n=jSj).Forexample,pointsareextractedby
`aHarris-Stephenscornerdetectororevenmorereli-
`ably(attheexpenseofasmallincreaseoftherunning
`time)byaKanade-Lucas-Tomasi'sintensitygradient
`approach.Acollineationorhomographyisde(cid:12)nedby
`thepairingLi$RiofpointsfLigiofS withother
`pointsfRigiofSingeneralposition.LetHbesuch
`atransformation.LetLiandQibethepixelpointsin
`imageI andIthataretherespectiveperspectivepro-
`jectionofthesamephysicalthree-dimensionalpoints
`Mi.UsingthehomogeneousdcoordinatesforLiand
`Ri,weget:
`h h h A @xiyizi A
`Ri= @x iy iz i A=HLi= @h h h
`h hh
`withLi=(xiziyizi)andRi=(x iz iy iz i).
`LetP=
`(LT LTLT LT)andQ=(RT RTRT RT)be xmatri-
`ces.Then,wegetH=QPT(PPT)(cid:0) :
`
`Fig. Mosaicingofimages(StanfordUniversity).
`Consideringonlyhomographiesde(cid:12)nedbyfeature
`
`IEICETRANS.INF.&SYST.,VOL.???JULY ,NO.??????
`correspondences,wehaveasmanyas!(cid:0)n (cid:1)(cid:0)n(cid:1)pos-
`sibletransformations(Example:forn =n= we
`havemorethan billioninducedhomographies.In
`comparison,wehaveonlyabout .millionspanoramic
`transformations).Thenaivealgorithmwhichconsists
`inscoringone-by-oneeachhomographyandreporting
`onewhichhasthebestscoreisthereforenotscaleable
`(O(n)homographies,wheren=maxfn ;ng).
`
`Image Understanding, Data Fusion
`
`Image 1
`
`Image 2
`
`million(s) of pixels
`
`Feature Space
`
`DIGITAL CAMERA
`CAMCORDERS
`ETC ...
`
`optic zoom x10s
`digital zoom x100s
`
`GEOMETRIC
`FILTERING
`
`Transformation Space
`
`space of matrices
`
`ALIGNMENT
`
`hundred(s) of features
`
`BOUNDED ALIGNMENT
`
`BRANCH AND BOUND
`
`Minimizer
`
`(Levenberg-Marquadt, etc.)
`
`Scoring function
`
`Haussdorf
`Bottleneck
`Cross-Correlation
`
`Registrationprocesssynopsis:Geometric(cid:12)lteringse-
`Fig.
`lectspotentialfeaturecandidates(featurespace)thatgenerate
`plausibletransformations,i.e.reasonablezoomvalues,nottoo
`largerotations,etc.(transformationspace)
`Ifweconsideranchoredcorners(acornerpoint
`andtwohalf-linesegmentsemanatingfromit)asfea-
`tures[],thehomographycanbefoundbypairingonly
`twoanchoredcorners.Althoughtherunningtimein-
`creasesfordetectingtheseelaboratedtemplatedfea-
`turesbynon-linearminimizationtechniques,thecore
`bottleneckisstilltheO(n)combinatoricsoftheall-
`pairingapproach.Inthispaper,wepresentane(cid:14)cient
`schemetoselectonlyafew(homographies)ofthem
`thatareplausibletogivebirthtopotentialsolutions.
`Theoutlineoftheproposedalgorithmisasfollows
`(seealsoFigure):
`(cid:15)Extractfeaturesfromimages(e.g.corners).
`(cid:15)GiveasetTofhomographiessatisfyinggeometric
`constraintsandmatchingatleastagivenfraction
`ofthepointsets.
`(cid:15)ScoreeachhomographyofTandchooseonewith
`highestquality(eg.,score).
`Oncethisglobalmatchinghasbeenfound,were-
`(cid:12)netheimagequalitybythefollowingprocess:
`
`Prime Focus Ex 1039-2
`Prime Focus v Legend3D
`IPR2016-01243
`
`
`
`NIELSEN:ALGORITHMSFORMOSAICINGSYSTEMS
`(cid:15)Performlocaloptimization(subpixelanalysis)on
`features.Thisstepisrequiredbecausewedealwith
`pixelsandnotpoints!Wecanusealsoagradient
`descentorLevenberg-Marquadtmethodonpixel
`intensities.
`(cid:15)Performlocaloptimizationbyperturbatingcoe(cid:14)-
`cientsofthehomographymatrix(compensatefor
`lensaberration).
`(cid:15)Warpimages(deghostingtechniquesandpixelam-
`pli(cid:12)cation).
`(cid:15)Correctintensityandblendimages.
` .Scoringtransformations
`OnceatransformationHhasbeenchosenasapotential
`candidate(Hisinducedbycorrespondencepairs),we
`havetoevaluateitsscore.Weinitiallyattachtoeach
`detectedfeatureavectorofcharacteristicsdescribing
`theneighborhoodwherethefeaturehasbeenextracted
`(e.g.,intensityvalues,qualitativemeasures).Wesay
`thatapointL inS matchesapointR inSfor
`acollineationHifd(R ;HL )<=(cid:15)(forsomepre-
`scribed(cid:15)>= )andiftheircorrespondingqualitative
`featurescorrelatesatisfactorily.Wecallthismatchan
`(cid:15)-match.LetHS bethesetofpointsfHLjLS g.
`Thecommonfeaturepointsarecalledinliersandfea-
`turespresentinonlyoneofthetwoimagesarecalled
`outliers.Wedistinguishbetweenfourfamiliesofscorings
`thatexhibittrade-o(cid:11)sbetweenrunningtimeandrelia-
`bilityoftheirscores:
`( )PixelCross-Corellation.Weuseasascoring
`functionforHthezeromeancross-correlation
`onsubwindowscenteredatextractedpoints.
`OnRGBpictures,apixelpwithcolortriple
`(pR;pG;pB)hasintensityI(p)= : pR+ : pG+
` : pB.Thequalityisde(cid:12)nedasfollows:
`Q(H)= PpW(I(Hp)(cid:0)I(p))
`qPpWI(Hp)qPpWI(p);
`whereWisthecorrelationwindow.
`()TheHaussdorfmatching.EachpointRSis
`associatedtoitsclosestneighborofHS provided
`thatitsdistanceislessthanaprescribed(cid:15)(see
`Figure ).EventuallyseveralpointsofSmay
`beattachedtothesamepointofHS (especially
`whenzoomfactorsdi(cid:11)er).Eachassociatedpair
`ofpointsde(cid:12)nesanedgeofthegraphwhosenodes
`arethevertexsetHS [S(SeeFigure ,top).
`ThescoreofaHaussdorfmatchingissettobethe
`weigthednumberofedgesofanypairofmatched
`points.(SeealsothedirectedpartialHaussdorf
`
`
`distancethattakesintoaccountinliers/outliers.)
`Thismeasure,however,isnotsuitablefordi(cid:11)er-
`entimagescalings.
`bottleneck
`( )Thebottleneckmatching.The
`measure[],[]re(cid:13)ectsinabetterwaythe $
`matchingofpointsets.Weconsiderthecomplete
`bipartitegraphG=(HS ;S;E),whereEisthe
`setofallweightededgese=(L;R)wherew(e)=
`d(L;R).LetG(cid:15)betherestrictedbipartitegraph
`ofGcontainingalledgesofweightslessthan(cid:15):
`G(cid:15)=(HS ;S;E(cid:15)),st.E(cid:15)=f(HLi;Rj)jLi
`S ;RjS;d(HLi;Rj)<=(cid:15)g.Thebottleneck
`matchingisamaximummatchingy,oftennotper-
`fectmatching,ofG(cid:15)(seeFigure ,bottom).
`
`Haussdorfmatching(top).Bottlebeckmatching
`Fig.
`(down).
`()Discreteapproximatematching.
`Sinceourpointsetsaredenseandofboundeddi-
`ameter(namelytheimagediameter),wecanuse
`buckettingtechniques.ForeachpointLHS
`wecheckwhetherthereisapointRSinits
`neighborhood(seeFigure).
`Wereportthenumberofmatchingpointsap-
`proximately.(Bucketsintroduceaninherentp-
`approximationfactor).Notethatthemotifofthe
`booleanbucketcanbecomputedbeforehandand
`doesnotdependonHbutonS.
`Runningtimes.
`( )canbecomputedintimeproportionaltothenumber
`ofpixelcorrelations(windowsizes,alsoproportional
`yAmatchingisasetofpairwisedisjointedges.
`
`Prime Focus Ex 1039-3
`Prime Focus v Legend3D
`IPR2016-01243
`
`
`
`Filled bucket
`
`Empty Bucket
`
`Boolean bucketted motif
`
`
`BooleanbucketonsetS:greybucketsaremarkedto
`Fig.
`containapointofSintheirneighborhood.
`tothenumberoffeatures).()canbecomputede(cid:14)-
`cientlyinO(nlogn)-timeusingVoronoidiagramsbutis
`notappropriatefordi(cid:11)erentscalings.(Wemayusethe
`hardwaregraphicspipelineassuggestedin[ ]toaccel-
`eratethiscomputation.)( )requiresmoreprocessing
`time;EfratandItai[]usinganimplicitformofthe
`geometricgraphreportednearlyO(n )-timealgorithm
`forcomputingalonguestmatchingthatminimizesthe
`maximumedgelengthamongallmatchededges.More
`precisely,letm=jE(cid:15)jbethenumberofedgesofG(cid:15)
`andn=n +nbethenumberofvertices.Per-
`fect/maximummatchingsingeneralweightedgraph,
`whereonewantstominimizethesumofmatchededges,
`requireO(n )time[ ]usingtheso-calledHungarian
`method.Ontheotherhand,onunweightedbipartite
`graphs,amaximummatchingcanbefoundwheneverit
`existsintimeO(mpn)[ ].Whenconsideringgeomet-
`ricgraphs,i.e.,graphsobtainedfromageometricscene,
`Vaidya[ ]gaveanO(n)-timealgorithmformatching
`twopointssetssothatthesumofthematchededges
`isminimized.ConsideringtheL distanceinsteadof
`theLdistance,VaidyaobtainedanO(nlog n)-time
`algorithm.Lateron,thoseresultswhereimprovedby
`Agarwaletal.[ ]toO(n+(cid:13))foranyarbitrarysmall
`positive(cid:13)>