1,: 69, 36, Groebner [2] 3 {x 1,x 2,,x m } 2 m,, π11,π12,,πm 1,πm 2, ( x 3, ) ;, π11 烄 T 烌烄 (1,0,-x 1 )P 1 烌 LM(Levenberg-Marquardt) π12 T (1,0,-y1)P

Size: px

Start display at page:

Download "1,: 69, 36, Groebner [2] 3 {x 1,x 2,,x m } 2 m,, π11,π12,,πm 1,πm 2, ( x 3, ) ;, π11 烄 T 烌烄 (1,0,-x 1 )P 1 烌 LM(Levenberg-Marquardt) π12 T (1,0,-y1)P"

霏绕郜
7 years ago
Views:

1 Vol24No1 JournalofComputer-AidedDesign & ComputerGraphics Jan2012, ( ) (qzhang@nlpriaaccn) :,, : 0 L2-, Sampson ;,2, : ;Sampson ; :TP391 IterativeAlgorithmsforMulti-ViewTriangulation ZhangQiangand WuFuchao (NationalLaboratoryof Patern Recognition,Instituteof Automation,Chinese Academyof Sciences,Beijing ) Abstract:Givenasetof measuredpointcorrespondencesacrossimagesandtheassociatedcamera projectionmatrices,themulti-viewtriangulationreferstotheprocessofestimatingthecorresponding 3D pointdueto variouserrorsin measured points,an optimality criterionisrequiredforthe triangulationthispaperproposesanew optimalitycriterion which minimizesthel 2-norm distance betweentheestimatedpointandthemeasuredpointundertheconstraintthattheleastsingularvalueof thespaceplane matrix mustbezerobasedonsampsonapproximationoftheconstraint,asimple iterativealgorithm is obtainedin addition,by using the conjugate gradient and enforcing the decreasingconditionoftheleastsingularvalueofthespaceplane matrixintheiterativeprocess, anotheriterativealgorithm withbeterconvergencerateisobtainedexperimentsshowthatourtwo proposedalgorithmsbothrequirelessnumberofiterationsandhavelessrunningtimethanthegold Standardalgorithm,whileyieldingcomparableestimationaccuracy Keywords:multi-viewtriangulation;Sampsonapproximation;conjugategradient,,, (, ),, ( ) 2 [1], 2, 16, 3 : ; : : ( , ) (1982 ),, (1957 ),,,,

2 1,: 69, 36, Groebner [2] 3 {x 1,x 2,,x m } 2 m,, π11,π12,,πm 1,πm 2, ( x 3, ) ;, π11 烄 T 烌烄 (1,0,-x 1 )P 1 烌 LM(Levenberg-Marquardt) π12 T (1,0,-y1)P 烄 x 1 烌 1 (goldstandardalgorithm,gsa) [3] A(x)= x 2 =, x=,lm, L 2- π T m 1 (1,0,-x m )P m [4], x π T m m (1,0,-ym)P 烆烎 L 2 - 烆 2 烎烆 m 烎, [5-7] {x - 1,x 2,,x m },, X πn T 1 X=0,π n T 2 X=0,n=1,,m, [8-10] L - ; L -, A(x)X=0 (1) L - (1) A(x),A(x) L 2 - ( σ4(x)=0,m,l 2 - ), min x-x ~ 2 2 stσ4(x ~ )=0 (2),, L 2 -,, Sampson ;, Sampson,,3 4, 2,,, 1 (2),, [12] L 2 -, : m,, 2 {x 1,x 2,,x m }, {P 1, P 2,,P m }, {x ~ 1,x ~ 2,,x ~ m}, L 2-2 Sampson ( ) ;,{x ~ 1,x ~ 2,,x ~ m} {x 1,x 2,,x m } (2), : 0, V={x ~ :G(x ~ )=0} x,x ~ V x L 2 - x n=(x n,yn) T, 2 x n l n1 =(1,0,-x n ),l n2 =(0,1,-yn) n min x-x ~ 2 2 stg(x ~ )=0 (3) 2, 2 Δx=x ~ -x, (3) [11] minδx T Δx stg(x+δx)=0 πn 烄 T 1 =l n1 P n=(1,0,-x n )P n 烅 πn 烆 T 2 =l n2 P n=(0,1,-yn)p n x n 2,, G(x+Δx) Sampson [13],

3 70 24 G(x+Δx) G(x)+J(x) T Δx=0, σ 4 J(x)G x Jacobi x =0 σ4 ε(ε ), Sampson, minδx T Δx stg(x)+j(x) T Δx=0 (4) v4 (: (4), Δx=-J(x)(J(x) T J(x)) -1 G(x); x Sampson x S =x-j(x)(j(x) T J(x)) -1 G(x), Sampson G,Sampson x S σ4(x) ;,G(x S ) 0,Sampson σ4(x) u u T 4u 4=v T 4 T 4v 4=1, u 4=0, vt 4 v 4= x i x i 0, x i x i, A M=(p11,p12,,pm1,pm2) T,p T n1p n2 T x,σ 4 P n 12;,(6) A,u 4 v 4 σ4 x T diag(dv 4) 2 x-2(v 4) T M T diag(dv 4)x+,σ 4 x i (v 4) T M T Mv 4 = (σ 4) 2 (7) σ 4 = ((u 4) T A v 4) = x i x i σ 4, A (u 4) T A u 4+(u 4) T v v 4+σ 4(v 4) T 4 = x i x i x i (u 4) T A x i v 4; x i =-e i p T 2 -i? -,,3 e i i 12 m,p n3 T P n 3, a - - a, Kronecer x ), x S Sampson x S V, Sampson x S +1σ +1 4 σ4, {σ 4} x S +1=x S -J(x S )J(x S ) T J(x S ) -1 G(x S ), 0, x0=x; S,x S Sampson G(x ) 0,, S Sampson 3 [14-15]Sampson, Sampson {σ 4}, (2), {σ 4}, (2)Sampson Sampson, σ4(x ) S σ4(x ) S x S +1=x - S σ4(x ) ( S x ) T σ4(x ) ( ( S x ) x ) ; {σ 4},,σ4(x)=u 4 (x) 31 T A(x)v 4 (x),u 4 (x),v 4 (x) {σ 4} x,a σ4 σ4(x) v 4, Sampson, x (v 4) T A(x) T A(x)v 4=(σ 4) 2 (6) A(x) A(x)=M-diag(x)D,,(7), x 1 x, x +1 (v 4) T A T +1A +1v 4<(σ 4) 2,σ +1 4 <σ 4 A T +1A +1, Rayleigh-Rize [16],A T +1A +1 (σ +1 (σ +1 4 ) 2 4 ) 2 (v 4) T A T +1A +1v 4;, (v 4) T A T +1A +1v 4<(σ 4) 2 4 <σ 4 σ +1 1, {σ 4}, σ 4 x +1 x x =diag (u 4)Dv 4 (5), x +1,D=(p13,p13,,pm3,pm3) T,diag(x)σ +1 4 [12],,

4 1,: 71 σ +1 4,, {σ 4} 4 32 x, (7) 2 Sampson d : =0, (iterativealgorithm basedonsampson d 0=-g0, g= σ 4 x σ4(x)x ;, appximation,isa) (iterativebasedonconjugategradient,icg), >0 d =-g+β d-1 (8) d d -1 diag(dv 4) 2, d -1 T diag(dv 4) 2 (8) d T -1diag(Dv 4) 2 d =-d T -1diag(Dv 4) 2 g+ β dt -1diag(Dv 4) 2 d -1=0 d-1 T diag (Dv 4 ) 2 d -1 = 0 d-1g T - d -1 g =0, d =-g; β = dt -1diag(Dv 4) 2 g d T -1diag(Dv 4) 2 d -1,x d =-g+ dt -1diag(Dv 4) 2 g d T -1diag(Dv 4) 2 d -1 d -1 (9) Sampson, x +1 x,x +1=x +λd, λ f(λ)=(v 4) T (A -λdiag(d )D) T (A -λdiag(d )D)v 4,,minf(λ), g=0 σ 4 ε (ε ), v 4 σ x 0 ε, = σ 05~5, 0, : ) σ2, Step1 A,A SVD 4,6,8,12,16,20,24,28,32,36 σ 4,u 4,v 4, g (5), 1000 Step2σ 4 ε g=0,, v4 ;, Step3 d=0,d0 = -g0; >0, d-1 T diag(dv 4 ) 2 d-1 d-1 T g - d-1 g 0:,d = -g;, (9) d Step4 (10) λ,x+1=x+λd,= +1,Step1 (directlineartransformation, DLT) DLT+GS(DLT ) 2,, F- 1, σ4(x) ε 10-7, 233GHzInterCore2 DUO CPU,2GB ,36, 10, λ= ( v4) T (A ) T diag(d )Dv 4 (10) (v 4) T D T diag(d ) 2 Dv 4 fu, 烄 0 u 0 烌烄烌 x ( v4) T (A ) K T diag(d )Dv 4 = 0 fv v 0 = , +1=x + (v 4) T D T diag(d ) d 2 Dv 4 ; 烆烎烆烎, {x } :1) 36, 2a,2c 3a,3c,2 3 DLT2b,2d 3b,3d 2 DLT+GS,

5 72 24, 1 2, 20,ICG , f 3f,, 2e 3e,ISA ICG DLT+GS 40 45, DLT+GS 2 ISA, Oxforddinosaur 2, Oxforddinosaur 1 4a, htp:?wwwrobotsoxacu?~vgg?

6 1,: ; 4c, 24 GS b4d ICG 2 ICG, 1 2,dinosaur 9326%, 2 DLT+GS 8277%), 2 3e, ( 10-4 ),, DLT+GS 6, ISA ;, DLT, 2 5, ICG 2, ISA 6 ( Oxford

74 24 4 2 ICG 1 Oxforddinosaur DLT DLT+GS ISA ICG 1515387 1467379 1467603 1467557? 404 28 28 10 5 7102 257233 32895 37888?

7 ICG 1 Oxforddinosaur DLT DLT+GS ISA ICG ? ?s (References): [1]HartleyR,Sturm PTriangulation[J]ComputerVisionand ImageUnderstanding,1997,68(2): [2]SteweniusH,SchafalitzyF,NisterDHowhardis3-view triangulation realy [C]?Proceedings of the 10th IEEE InternationalConference on Computer Vision Washington DC:IEEEComputerSocietyPress,2005: [3]Hartley R, Zisserman A Multiple view geometry in 2 computer vision [M] New Yor: Cambridge University Press,2003: DLT DLT+GS ISA ICG [4]Hartley R, Seo Y Verifying global minima for L ? ?s 5 minimization problems [C]?Proceedings of the IEEE ConferenceonComputerVisionandPaternRecognitionLos Alamitos:IEEEComputerSocietyPress,2008:1-8 [5]Olsson C, Kahl F, Hartley RProjectiveleast-squares: globalsolutionswithlocaloptimization [C]?Proceedingsof the IEEE Conference on Computer Vision and Patern RecognitionLosAlamitos:IEEE ComputerSocietyPress, 2009: [6]Lu F F, Hartley R A fast optimal algorithm for L2,, Sampson 2, triangulation [C]?Proceedingsofthe8th AsianConference oncomputervisionheidelberg:springer,2007: [7]KahlF,AgarwalS,ChandraerM K,etalPracticalglobal optimization for multiview geometry [J] International JournalofComputerVision,2008,79(3): ,

8 1,: 75 [8]Hartley R,Schafalitzy FL minimizationin geometric ( [M]2 : reconstruction problems [C]?Proceedings of the IEEE ConferenceonComputerVisionandPaternRecognitionLos Alamitos:IEEE ComputerSocietyPress,2004,1:I-504-I- 509 [9]Ke Q F,Kanade TQuasiconvex optimizationforrobust,2005: , ) [13]SampsonPDFitingconicsectionsto veryscatered data: an iterative refinement of the Boostien algorithm [J] ComputerGraphicsandImageProcessing,1982,18(1): [14] WuFC,ZhangQ,HuZYEficientsuboptimalsolutionsto geometricreconstruction [J]IEEE TransactionsonPatern the optimal triangulation [J] International Journal of Analysisand MachineInteligence,2007,29(10): ComputerVision,2011,91(1): [10]Kahl F, Hartley R Multiple-view geometry under the [15]KanataniK,SugayaY,NitsumaHTriangulationfromtwo L -norm[j]ieee Transactionson Patern Analysisand viewsrevisited:hartley-sturmvsoptimalcorrection[c]? MachineInteligence,2008,30(9): [11] WuFuchaoMathematicalmethodsincomputervision[M] Beijing:SciencePress,2008:54-56 (inchinese) Proceedings of the British Machine Vision Conference Malvern:British Machine Vision Association Press,2008: ( [M] :, [16] Wang Songgui, Wu Mixia, Jia Zhongzhen Matrix 2008:54-56) [12]ChenBaolinOptimizationtheoryandalgorithms[M]2nd edbeijing:tsinghuauniversitypress,2005: , (inchinese) Inequalities[M]Beijing:Science Press,2006:77-78 (in Chinese) (,, [M] :,2006:77-78)

1 : 2D?3D 15 ; 3D 2D 3D 3D 2D?3D [3] 2D 3D 1 2D?3D (1) ; 1 2D?3D 11 2 : (binocularstereoscopicrenderingbsr) 3D ; [4-5] 3D (depth image-basedrenderingd

1 : 2D?3D 15 ; 3D 2D 3D 3D 2D?3D [3] 2D 3D 1 2D?3D (1) ; 1 2D?3D 11 2 : (binocularstereoscopicrenderingbsr) 3D ; [4-5] 3D (depth image-basedrenderingd 24 1 2012 1 Vol24No1 JournalofComputer-AidedDesign & ComputerGraphics Jan2012 2D?3D ( 100190) (wliu@nlpriaaccn) :3D 3D 2D 3D 2D?3D 4 : 2D 3D; ; :TP391 ASurveyof2Dto3DConversionTechnologyforFilm Liu WeiWuYihongandHuZhanyi