OutlineMultibody Epipolar ConstraintMultibody Fundamental MatrixGPCA-VotingNoise issueGPCA-VotingComparisonRobust GPCAOutlier IssueRobustifying GPCA via Influence and MVTComparisonApplicationsAffine Motion DetectionVanishing-Point DetectionConclusion and DiscussionConclusionFuture DirectionsOutline Multibody Epipolar Constraint GPCA-Voting Robust GPCA Applications ConclusionSegmentation of Subspace ArrangementsIII – Robust GPCAAllen Y. YangBerkeley CS 294-6, Lecture 25Dec. 3, 2006Allen Y. Yang Segmentation of Subspace Arrangements III – Robust GPCAOutline Multibody Epipolar Constraint GPCA-Voting Robust GPCA Applications ConclusionGeneralized Principal Component Analysis (GPCA): (an overview)x ∈ V1∪ V2⇒ (x3= 0)or(x1= x2= 0)⇒ {x1x3= 0, x2x3= 0}.Veronese Map: Given N samples x1, . . . , xN∈ R3,L2.= [ν2(x1), . . . , ν2(xN)] ∈ RM[3]2×N=··· (x1)2······ (x1x2) ······ (x1x3) ······ (x2)2······ (x2x3) ······ (x3)2···V1V2R3x3x1x2The null space of L2isc1= [0, 0, 1, 0, 0, 0]c2= [0, 0, 0, 0, 1, 0]⇒p1= c1ν2(x) = x1x3p2= c2ν2(x) = x2x3P(x).= [p1(x) p2(x)] = [x1x3, x2x3], then∇xP = [∇xp1∇xp2] =x300 x3x1x2.∇xP at one sample per subspace gives normal vectors that span V⊥1and V⊥2:x = [a, b, 0]T∈ V1⇒ ∇xP|x=h0 00 0a bi∈ V⊥1.y = [0, 0, c]T∈ V2⇒ ∇xP|y=hc 00 c0 0i∈ V⊥2.Segment samples and recover V1and V2.Allen Y. Yang Segmentation of Subspace Arrangements III – Robust GPCAOutline Multibody Epipolar Constraint GPCA-Voting Robust GPCA Applications Conclusion1Multibody Epipolar ConstraintMultibody Fundamental Matrix2GPCA-VotingNoise issueGPCA-VotingComparison3Robust GPCAOutlier IssueRobustifying GPCA via Influence and MVTComparison4ApplicationsAffine Motion DetectionVanishing-Point Detection5Conclusion and DiscussionConclusionFuture DirectionsAllen Y. Yang Segmentation of Subspace Arrangements III – Robust GPCAOutline Multibody Epipolar Constraint GPCA-Voting Robust GPCA Applications ConclusionMultibody Fundamental MatrixGiven K rigid bodies, an image correspondence (x1, x2) satisfies:f (x1, x2) = (xT2F1x1)(xT2F2x1) · · · (xT2FKx1) = 0.Two ways to rewrite the bilinear constraint:1f (x1, x2) = {(x1⊗ x2)TFs1} · · · {(x1⊗ x2)TFsK}.We treat z = x1⊗ x2∈ R9as the new feature vector, thenf (x1, x2) = νK(x1⊗ x2)Tc.2f (x1, x2) = νK(x2)TFνK(x1), where F ∈ RM[3]K×M[3]K.Which representation is more compact?1K = 2: For c, M[9]2=2+9−12= 45. For F , (M[3]2)2= 62= 36.2K = 4: For c, M[9]4= 495. For F , (M[3]4)2= 152= 225.Choose the second one.F is called the multibody fundamental matrix, comparing to the (single) fundamental matrix F .Allen Y. Yang Segmentation of Subspace Arrangements III – Robust GPCAOutline Multibody Epipolar Constraint GPCA-Voting Robust GPCA Applications ConclusionSegmentation of Multibody Motion∂∂x2f (x1, x2) =PKi=1Qj6=ixT2Fjx1(Fix1).Suppose (x1, x2) on Object k, thenQj6=ixT2Fjx1= 0 for all i 6= k:∂∂x2f (x1, x2) =Yj6=kxT2Fjx1(Fkx1) ∼ (Fkx1) ∼ l2k.Hence,∂∂x2f (x1, x2) ⊥ e2k.Given K rigid body motions, there exist K different epipoles e1, · · · , eKin the second view such that:(eT1l)(eT2l) · · · (eTKl) = 0,which is a standard subspace-segmentation problem.Allen Y. Yang Segmentation of Subspace Arrangements III – Robust GPCAOutline Multibody Epipolar Constraint GPCA-Voting Robust GPCA Applications ConclusionGPCA-Voting: A Stable ImplementationPDA on noisy dataV1V2RD=⇒νn(x)Null(Ln)=⇒=⇒∇xV1V2RM[D]nRM[D]np(x) = cTxRDThe noise affects the algebraic PDA process:1The data matrix LK(V ) is always full-rank.Solution: Use SVD to estimate Null(LK).2How to choose one point per subspace as the representative?Solution: Rule of thumb is to pick samples far away from the origin and intersections.3Even with a good sample, evaluation of ∇P is still perturbed away from the true position.Solution: We propose a voting algorithm to evaluate ∇P at all samples.Allen Y. Yang Segmentation of Subspace Arrangements III – Robust GPCAOutline Multibody Epipolar Constraint GPCA-Voting Robust GPCA Applications ConclusionA Voting SchemeGoal:1Averaging ∇xP at more samples of a subspace.2Recover correct rank of ∇xP.Difficulty: Do not know which samples belong to the same subspace, yet.GPCA-Voting (a simple example)1Assume subspaces (2, 1, 1) in R3.2hI(3) = 4 vanishing polynomials ⇒ ∇xP ∈ R3×4.3Vote on rank-1 & rank-2 codimensio ns with a tolerance threshold τ4Average normal vectors associated with highest votes.5(optional) Iteratively refine the segmentation via EM or K-Subspaces.Allen Y. Yang Segmentation of Subspace Arrangements III – Robust GPCAOutline Multibody Epipolar Constraint GPCA-Voting Robust GPCA Applications ConclusionSimulation Results1Illustrations(a) 8% (b)12%(c)16%Figure: (2, 1, 1) ∈ R3.(a) 8% (b)12%(c)16%Figure: (2, 2, 1) ∈ R3.2Segmentation simulationsTable: Segmentation errors. 4% Gaussian noise is added.Subspace Dimensions EM K-Subspaces PDA Voting Voting+K-Subspaces(2, 2, 1) in R329% 27% 13.2% 6.4% 5.4%(4, 2, 2, 1) in R553% 57% 39.8% 5.7% 5.7%(4, 4, 4, 4) in R520% 25% 25.3% 17% 11%Allen Y. Yang Segmentation of Subspace Arrangements III – Robust GPCAOutline Multibody Epipolar Constraint GPCA-Voting Robust GPCA Applications ConclusionOutlier IssueGPCA process:V1V2RD=⇒νn(x)Null(Ln)p(x) = cTx=⇒=⇒∇xRank(Ln) = M[D]n− hI(n)V1V2RM[D]nRM[D]nRDBreakdown of GPCA is 0% b eca use breakdown of PCA is 0%:a large outlier can arbitrarily perturb Null(Ln)V1V2RD=⇒νn(x)Null(Ln)=⇒RM[D]np(x) = cTxRM[D]n⇒⇒ Seek a robust PCA to estimate Null(Ln), where Ln= [νn(x1), · · · , νn(xN)].Allen Y. Yang Segmentation of Subspace Arrangements III – Robust GPCAOutline Multibody Epipolar Constraint GPCA-Voting Robust GPCA Applications ConclusionThree approaches to tackle outliers:1Probability-based: small-probability samples.Probability plots: [Healy 1968, Cox 1968]PCs: [Rao 1964, Ganadesikan & Kettenring 1972]M-estimators: [Huber 1981, Campbell 1980]multivariate trimming (MVT): [Ganadesikan & Kettenring 1972]2Influence-based: large influence on model parameters.Parameter difference with and without a sample: [Hampel et al.1986, Critchley 1985]3Consensus-based: not consistent with models of high consensus.Hough: [Ballard 1981, Lowe 1999]RANSAC: [Fischler & Bolles 1981, Torr 1997]Least Median Estimate (LME): [Rousseeuw 1984, Steward 1999]Allen Y. Yang Segmentation of
View Full Document
Unlocking...