[PDF] Closed-Form Optimal Two-View Triangulation Based on Angular

View - Download Closed-Form Optimal Two-View Triangulation Based on Angular

Previous PDF

Next PDF

Closed-FormOptimalTwo-V iewTriangulation BasedonAngularErrors

SeongHunLee JavierCi vera

I3A,Univ ersityofZaragoza,Spain

{seonghunlee,jcivera}@unizar.es

Abstract

Inthispaper ,westudy closed-formoptimalsolutionsto two-viewtriangulationwithknowninternal calibrationand pose.Byformulatingthetriangulation problemas L1and L ∞minimizationofangular reprojection errors, wederive theexact closed-formsolutionsthatguaranteeglobal opti- malityunde rrespectivecostfunctions.Tothe bestofour knowledge,wearethefirst topresent suchsolutions.Since fisheyeoromnidirectional.Our methodsalsorequiresignif- icantlylesscomputation thanthee xistingoptimalmethods. Experimentalresults onsyntheticandrealdatasets validate ourtheoretical derivations.

1.Introduction

Recoveringthepositionofa3Dpoint given itsprojec-

tionsintw oormore camerasiscalledtriangulation.Itcon- stitutesafundamental buildingblock instereovision [ 33],
simultaneouslocalizationand mapping(SLAM)[

22]and

structure-from-motion(SfM)pipelines[

29].For largeprob-

lems,reconstructingthousands (ormillions)of pointsisnot uncommon,soachie vingfast andaccuratetriangulationis importantforthe performanceofsuch systems.

Ifoneassumes theexact knowledgeof cameramatrices

andnoiselessfeature measurements,triangulationamounts tointersectingtw obackprojectedrays thatcorrespondto thesame3D point.Inpractice, howev er,this assumptionis unrealistic,andthe raysdonot necessarilyintersect.There- fore,anontri vialmethodis requiredevenforjust twovie ws.

Thestandardapproach istofind the3Dpoint thatmin-

imizesachosen costfunctiongi venthe featuremeasure- ments.Themost commonarethe L1norm(sumof magni- tude),L2norm(sumof squares)andL∞norm(maximum) ofimagereprojection errors.Whilereasonable forperspec- tivecameras,theimagereprojectionerrordoes notgener- alizewellto differentcamera types(e.g.,omnidirectional orfullyspherical panoramiccameras).This motivates the

useofangularreprojectionerror, arotationallyinvariantal- ternativetotheimagereprojectionerrorthat isgenericand

independentofthe projectiongeometry[

21,24,27].

Inthisw ork,wederi ve,forthefirsttime toourkno wl- edge,thee xactclosed-formsolutions totheL1andL∞op- timaltriangulationfrom twovie wsbasedon theangularre- projectionerror. Unlikeiterativemethods (e.g.,[

13,17]),

theproposedmethods guaranteeglobaloptimality with- outany iterations,andunlikepolynomialmethods (e.g.,

10,23,32]),they donotinvolve findingtheroots ofa

ouslyprovide theglobaloptimality,speedand simplicity.

Wealsopresentouro wnderiv ationofthe L2optimalso-

lutionthatis muchmorecompact andgeometricallyintu- itivethantheexistingone[

24].Sinceall threemethodsare

basedonthe angularerror, theyare notlimitedto standard perspectivecamerasandcanalsobeused forfisheye, omni- directionalandfully sphericalpanoramiccameras. Thepaperis organized asfollows. Inthenextthreesec- tions,wediscuss therelatedw orkandpreliminaries. Sec- tion tionstothe L1,L2andL∞optimaltriangulation.T omake ourpapercompact andeasilyaccessible, weseparatedthe proofsfromour mainfindingsand putthemin theappendix.

Section

8addressesthecheirality constraint.Finally, exper-

imentalresultsare providedin Section

9,followed bythe

conclusionsinSection 10.

2.RelatedW ork

Themostwidespread approachtotriangulation istofind the3Dpoint thatminimizesthe L2normofimage reprojec- tionerrors[

8].Assumingthat imagepointsare perturbedby

Gaussiannoise,the L2optimalsolutiongi vesthe maximum likelihoodestimate(MLE).Thiscan beobtainedin closed formbysolving apolynomialof degree6 fortwo views

10]andde gree47for threeviews[32].Suchpolynomial

methodsare,ho wever ,computationallyexpensiveandsus- ceptibletoill-conditioning [

17].Besides,an iterative search

fortheroots mayconv ergeto alocalminimum [ 10].

Anothertwo-vie wmethodbyKanatanietal.[

13]iter-

ativelycorrectsthe2Dprojectionsofthe points.Although thismethod wasshowntobe fasterthantheoneby Hartley 2681
andSturm[ 10],itdoes notsatisfythe epipolarconstraint

19]ineach iteration.Lindstrom[ 17]solved thisproblem

withanimpro vediterati vealgorithmthatisevenmore sta- bleandf aster.Ho wever,neitherhismethodnorKanatani" s guaranteesglobaloptimality .Oliensis[

24]showed thatby

formulatingtheproblem asL2minimizationofthe sineof angularreprojectionerrors, anexact closed-formsolution canbederi vedfor two-viewtriangulation.

Insteadofminimizing theL2norm,onemay chooseto

minimizetheL1normofreprojection errors.Theadv an- tageofL1normisthat itismore robustto outliersasit placeslessemphasisonlargeerrors[

10,11].For twoviews,

HartleyandSturm[

10]showed thattheL1optimalsolution

canbeobtained inclosedform bysolvinga polynomialof degree8.Theyalso foundthatt heL1optimizationgiv es slightlymoreaccurate 3Dresultsthan theL2optimization. Ingeometric problems,anotherpopularnormisthe L∞ norm.TheL∞optimalsolutioncorresponds totheMLE undertheassumption ofuniformnoise intheimage points

6].Theadv antageofthe L∞costfunctiono verthe L2

costisthat itisrelati velysimpler andhasa singleminimum

9].For thecaseoftwovie ws,N´ıster[23]showed thatthe

optimalsolutioncan beobtainedin closedformby keeping therepro jectionerrorsequalinthetwoviewsandsolving theresultingquartic equation.Amain drawbackof theL∞ costisthat itisrelati velymore sensitive tooutliers[

9].This

beingsaid,such sensitivityw asshown tobeusefulforout- lierremov al[

30,26,16].

Whilemostof theaforementionedw orksformulatetheir

optimizationproblemin termsofthe imagereprojectioner - ror,theangularreprojectionerror isanotherpopular choice. Itembodiesa betternoise modelforfishe yeoromnidirec- tionalcameras[

24,20].Even forperspectivecameras,the

assumptionofGa ussiannoiseis notjustified[

6],andthe

angularreprojectionerror isjustas validas theimagere- projectionerror, ifnotmoreso.Inthe literature,ithas been proposedtominimize thesineof angularreprojectionerrors inL2norm[

24],thetangent inL2orL∞norm[7,9,12],

andthecosine inneg ative L1norm[

28,3].Incontrast to

thesemethods,our L1andL∞optimizationdonot involv e trigonometricfunctions.

3.Preliminaries on3DGeometry

Throughoutthepaper ,weadopt thefollowingnotation:

Weuseboldlettersfor vectorsandmatrices,andlightletters forscalars.The Euclideannormof avector visdenotedby ?v?,andthe unitvector by?v=v/?v?.Theangle between twolinesL0andL1isdenotedby ?(L0,L1)?[0,π/2]. Thefollowing vectoridentitieswillcomein handylater: ?a×?b?2=1-(?a·?b)2(2) Wealsomakefrequent useofthe followingformulas:1.Thedistance betweenapoint pandaplane Π0(x)= n

0·(x-c0)=0 isgiv enby?p-r0?wherer0isthe

projectionofpontoΠ0.Thisis computedasfollo ws: ?p-r0?=|?n0·(p-c0)|.(3)

2.Thedistance betweentwo skew linesL0(s0)=c0+

s

0m0andL1(s1)=c1+s1m1isgiv enby?r0-r1?

wherer0andr1arethepoints oneachline thatformthe closestpair. Lettingt=c0-c1andq=m0×m1,this iscomputedas follows: ?r0-r1?=|t·?q|.(4)

Thetwo pointscanalsobeobtainedindi vidually[

14]: r

0=c0+q·(m1×t)

?q?2m0,(5) r

1=c1+q·(m0×t)

?q?2m1.(6)

Equation(

4)canbe interpretedasthe minimumamount

oftranslationrequired forthetw olinesto intersect.In thiswork, itwillbealsoimportan ttokno wtheminimum amountofrotation (orpiv ot)requiredfor thetwo linesto intersect.We answerthisquestioninthefollo winglemma:

Lemma1(Minimum Pivot Anglefor Intersection)

Giventwosk ewlines L0(s0)=c0+s0m0andL1(s1)=

c

1+s1m1,letL?0betheline thatformsthe smallestangle

0?[0,π/ 2]toL0amongallpossible linesthatinter sect

bothpointc0andlineL1.Then,L?0isthepr ojectionof L

0ontotheplane thatcontainsc0andL1.Furthermore ,

lettingt=c0-c1andn1=m1×t, sin(θ0)=|?n1·?m0|.(7) Wecallθ0theminimumpiv otanglef orintersection,asit representsthesmallestanglerequired forpivotingline L0 atc0tomake itintersectL1.

Proof.RefertoAppendix

A.?

4.Preliminaries onTwo-ViewT riangulation

Considertwo camerasC0andC1observingthesame

3Dworld pointxw.Letc0andc1betheirpositions

inthew orldframe,and letRandtbetherotation ma- trixandtranslation vectorthat togethertransforma point fromthecamera frameC0toC1,i.e.,x1=Rx0+t, spondtoxwincameraframe C0andC1,respectiv ely. Sincetriangulationis impossibleforzero translation,we set?t?=?c0-c1?=1withoutlossof generality.Let u

0=(u0,v0,1)?andu1=(u1,v1,1)?bethehomoge-

neouspixel coordinatesoftheestimatedcorrespondenceto x wineachframe. Given thecameracalibration matrixK, thenormalizedimage coordinatesf0=[x0/z0,y0/z0,1]? andf1=[x1/z1,y1/z1,1]?arerelatedto u0andu1by u

0=Kf0andu1=Kf1.

2682
CC01 0 d0 1 d1

Rf0f1''

Rf0f1 t x'1 Figure1.The differencebetween theobserved features(f0,f1)and thetriangulationresult (f?0,f?1)canbe quantifiedbyei therimage reprojectionerrors( d0,d1)orangular reprojectionerrors( θ0,θ1).

Thetwo backprojectedraysinframeC1,i.e.,r1(s1)=

s

1f1andr0(s0)=s0Rf0+t,donot necessarilyintersect

duetoinaccuracies intheimage measurementsandcamera matrices.For theraystointersect,f0andf1mustbecor - rectedtof?0andf?1suchthatthe epipolarconstraint[ 19]is satisfied.Itenforces thecoplanarityof f?1,Rf?0andt,and isgiv enby f ?1·(t×Rf?0)=0 .(8) Thegoalof theoptimaltriangulation istominimallycor- rectthefeature rayssothat theysatisfy (

8)andintersect at

somepointx?1inframeC1.Whatis meantby“minimal"de- pendsonthe chosencostfunction anderrorcriterion. Fig. 1 illustratestwo mostpopularerrorcriteria,namely theimage reprojectionerrorand theangularreprojection error.F or- mally,theyaredefined asfollows: di:=?ui-u?i?=?K(fi-f?i)?,fori=0,1(9) i:=?(fi,f?i)=??K-1ui,K-1u?i?fori=0,1(10)

Inthisw ork,weminimize thelatterinL1,L2andL∞

norms.Oncewe have theoptimalf?0andf?1,thepoint of intersectionx?1canbeobtained usingeither(

5)or( 6):

x

1=t+z·(t×f?1)

?z?2???? 0Rf

0=z·(t×Rf?0)?z?2????

1f ?1(11) withz=f?1×Rf?0, whereλiequalsthedepth multipliedby?f?i?fori=0,1.

Notethatthe epipolarconstraint(

8)isa necessarycon-

ditionforintersecting thetwo rays,but notasuf ficientone. Fig.

2illustratesscenarioswhere thetwo raysarecoplanar ,

butdonotintersect.This happenswhenthe intersectionre- quiresneg ativedepth(s),violatingthecheiralityconstraint

8].Inthe followinganalysis (untilSection8),wewil ltem-

porarilyassumethat satisfyingtheepipolar constraint( 8)is sufficientforintersectingtherays.

5.Closed-Form L1Triangulation

TheL1triangulationbasedon theangularreprojection

error(

10)findsthe featureraysf?0andf?1thatminimize

0+θ1subjecttothe epipolarconstraint(

8).Thefollo wing

lemmarev ealsasurprisingfactthat(θ0+θ1)minisachiev ed bycorrectingeither oneoff0orf1,but notboth: (a) (b)t t CC f0f1R x' t (c)f

0Rf0Rf1

f 1 0 1C 0C1 C 1C 0' '1 x' 1x' 1 Figure2.Example scenariossatisfyingthe epipolarconstraint( 8). Theepipolarplane (shownin green)containsboth theraysandthe cameracenters.Cheirality conditionisviolated incase(b) and(c).

Lemma2( L1AngleMinimization)

Giventwosk ewlines L0(s0)=c0+s0m0andL1(s1)=

c

1+s1m1,considerany twointersecting linesthatalso

passc0andc1,respectively ,i.e.,L?0(s?0)=c0+s?0m?0and L

1(s?1)=c1+s?1m?1.Lett=c0-c1,n0=m0×t,

n (θ0+θ1)isminimizedfor thefollowingm?0andm?1: m

0=m0-(m0·?n1)?n1andm?1=m1.(12)

Otherwise,

m

0=m0andm?1=m1-(m1·?n0)?n0(13)

Proof.RefertoAppendix

B.?

Bysubstituting Rf0andf1intom0andm1intheabo ve

lemma,theresulting m?0andm?1becomethecorrected rays Rf

0andf?1thatsatisfythe L1optimality,andn0(orn1)

becomesthenormal ofthecorresponding epipolarplane.

6.Closed-Form L2Triangulation

Consideringthatthe angularerrorsare smallinpractice, the“relaxed" L2triangulationfindsthe featureraysf?0and f jecttothe epipolarconstraint(

8).Notethat thesmall-angle

approximationbysin(θ)ismoreaccurate thanbytan(θ)or

1-cos(θ)thathav ebeenusedinliterature[

7,9,12,28,3].

Thisiseasily seenbycomparing theirMaclaurine xpan- sions.Aswill beshown inthefollo winglemma(and previ- ouslyin[

24]),therelaxation withthesine functionallows

ustoderi vethe L2optimalsolutionin closedform.

Lemma3( L2AngleMinimization)

Giventwosk ewlines L0(s0)=c0+s0m0andL1(s1)=

c

1+s1m1,considerany twointersecting linesthatalso

passc0andc1,respectively ,i.e.,L?0(s?0)=c0+s?0m?0and L

1=?(L1,L?1).Then,?sin2θ0+si n2θ1?isminimizedfor

m i=mi-(mi·?n?)?n?fori=0,1,(14) where ?n?isthesecond columnofthe 3×3matrixVfrom 2683

USV?=SVD???m0?m1?

I-?t?t???

.(15)

Proof.RefertoAppendix

C.?

Analogouslytothe L1method,substitutingRf0andf1

intom0andm1intheabo velemma givesRf?0=m?0and f ?1=m?1thatsatisfythe L2optimality.

7.Closed-Form L∞Triangulation

TheL∞triangulationbasedon theangularreprojection error(

10)findsthe featureraysf?0andf?1thatminimize

max(θ0,θ1)subjecttothe epipolarconstraint(

8).Thefol-

lowinglemmastatesthatthis isachiev edwhenθ0=θ1:

Lemma4( L∞AngleMinimization)

Giventwosk ewlines L0(s0)=c0+s0m0andL1(s1)=

c

1+s1m1,considerany twointersecting linesthatalso

passc0andc1,respectively ,i.e.,L?0(s?0)=c0+s?0m?0andL?1(s?1)=c1+s?1m?1.Lett=c0-c1,na=

0=θ1.Thisis achieved for

m i=mi-(mi·?n?)?n?fori=0,1,(16) where n?=? n aif?na?≥? nb? n bohterwise(17)

Proof.RefertoAppendix

D.?

Analogouslytothe previoustw omethods,substituting

Rf

0andf1intom0andm1givesRf?0=m?0andf?1=m?1thatsatisfythe L∞optimality.

8.Cheirality, ParallaxandOutliers

Wehaveused thetermlinesinsteadofraysinalllemmas

sofar ,ignoringthecheiralityconstraint[

8].We arguethat

iftheoptimal solutionviolatesthe cheiralityconstraint,the mostreasonablechoice istosimply discardtheresult. In thefollowing, weprovidetherationalefor thischoice. Fig.

4illustratesfiv escenarioswheretheoptimalsolu-

tionviolates thecheiralityconstraint.Incase (a),bothrays havenegativedepths attheoptimalintersection.Increasing theallowed angularreprojectionerror ,thefirst intersection withpositiv edepthsoccurswhenthetwocorrectedrays be- comeparallel,resulting inapoint atinfinity. Thispoint cannotbetriangulated, soitshould bediscarded. Intheremaining cases,theoptimal intersectioninv olves onlyoneof theraysha vingane gativ edepth.F ollowingthe sameprocedure,the firstintersectionwith positive depths occurseitherat infinity(case(b)), atoneof thecameracen- ters(case(c)), alongtheray paralleltothe translation(case (d)),orat apointsome whereelse(case (e)). Incase(b), (c)and(d), thenewly triangulatedpointhas eitherinfinite,zero orambiguousdepth, soitis reasonable todiscardit. Incase(e), wefoundthat reattemptingthe triangulationwithpositi vedepths yieldseitheraverylarge

Input:Calib.matrix(K),relativ epose(R,t),anda

match(u0,u1)fromtw oviews (C0,C1).

Output:Triangulated3Dpoint(x?1)inref. frameC1.

2)ForL1triangulation:

m

0andm?1.Otherwise,use (

13).

ForL2triangulation:

Computem?0andm?1from(14)and( 15).

ForL∞triangulation:

Computem?0andm?1from(16)and( 17).

3)Rf?0←m?0andf?1←m?1.

4)Checkcheirality:

(i)Obtainλ0andλ1from(11). (ii)Discardthe pointandterminate ifeither

5)Checkangular reprojectionerrors:

(ii)Discardthe pointandterminate if max(θ0,θ1)>?1forsomesmall ?1.

6)Checkparallax:

(i)β←?(Rf?0,f?1) (ii)Discardthe pointandterminate if

2forsomesmall ?2.

7)Computeand returnx?1from(11).

Table1.Summaryofthe proposedmethods.

error,apointneart heepipoleor alow parallaxangle.T yp- ically,thesearetheindicators oflow accuracyor anoutlier

10,8],soa reasonablechoiceis todiscardthe match.This

procedureisoutlined inStep4-6 ofTab . 1.

9.ExperimentalResults

Weevaluatethe proposedmethodsincomparisontothe

midpointmethod[

2,10],Hartley andSturm"sL1andL2

method[

10],Lindstrom"s L2methodwithfi veiterations

17],andN ´ıster"sL∞method[23].Thee valuationw as

performedonboth syntheticandreal datasets.We gener- atedthesynthetic datasetsasfollo ws:Aset of8×4point cloudsof2,500 pointseachare generatedwitha Gaus- sianradialdistrib utionN(0,(d/4)2)wheredisthedis- tancefromthe worldorigin. Eachpointcloud iscenteredat [0,0,d]?ford=2nwithn=-1,0,...,+6,andtheir im- ageprojectionsare perturbedbyGaussian noiseN(0,σ2) forσ=0.5,1,2,4,8.Thesize andthefocal lengthof theimagesare 1,024×1,024pixelsand512pixel,re- spectively.Wehavethreeconfigurationsfor thecameraquotesdbs_dbs29.pdfusesText_35

[PDF] comment apprendre vite par coeur

[PDF] technique pour apprendre vite ses leçons

[PDF] technique de mémorisation de cours

[PDF] techniques de mémorisation efficaces

[PDF] objectif poésie cycle 3

[PDF] la poésie ? l'école

[PDF] savoir argumenter pdf

[PDF] savoir argumenter du dialogue au débat

[PDF] savoir argumenter du dialogue au débat pdf

[PDF] comment réussir un débat

[PDF] cour communication pdf

[PDF] bien communiquer au travail

[PDF] comment bien communiquer avec les autres

[PDF] comment trouver de bons arguments ? sa candidature

[PDF] comment gérer son argent pour devenir riche pdf