Structure from MotionRoadmapStructure and Motion spaceStructure Estimation - BackgroundPriniciple of FactorizationSlide 6Kanade-Lucas-Tomasi (KLT) trackerSlide 8Slide 9Affine CameraSlide 11Rigid Body FactorizationRigid Body Factorization (contd.)Experiments – Rigid Body FactorizationSlide 15Slide 16Rigid Multi body FactorizationShape Interaction MatrixMulti-body factorization algorithmNon-Rigid 3D Shapes from Image StreamsNon-rigid Body FactorizationSlide 22Slide 23Rank-Constrained Tracking(1)Rank-Constrained Tracking(2)Rank-Constrained Tracking(3)Rank-Constrained Tracking(4)Experiments – Non-rigid Body FactorizationSlide 29Slide 30Slide 31Slide 32Slide 33ConclusionThank you!!!Structure from MotionMani ThomasCISC 489/689RoadmapStructure from MotionBackgroundFeature based motion estimationKLT trackerFactorizationRigid body FactorizationMulti-body factorizationNon rigid body factorizationConclusionsStructure and Motion spaceStructure Estimation - BackgroundMany methods have been developed to tackle the Structure from Motion problemSzeliski and Kang, ‘93Azarbayejani and Pentland, ‘95Calway, ‘05Broida and Chellappa, ‘91Most methods involved an iterative minimization of an energy functionalComputationally expensiveFactorization – non-iterative solution to the structure from motion problemLeast squares estimate of structureComputationally inexpensivePriniciple of FactorizationFactorization principleStructure of an object resides in a low rank subspacePrincipal Component Analysis of the shape spaceCapture the subspace of the shape spaceReconstruct the structure using the projected components from this subspace instead of the actual spaceRank 3 subspace for a single rigid body (Tomasi and Kanade, ’92)Rank 6 subspace for scene with objects under constant velocity (Han and Kanade, ‘01)Rank 3K subspace for a non rigid body (Bregler et al., ’00)RoadmapStructure from MotionBackgroundFeature based motion estimationKLT trackerFactorizationRigid body FactorizationMulti-body factorizationNon rigid body factorizationConclusionsKanade-Lucas-Tomasi (KLT) trackerFeature based motion estimationExtract cornersCompute the motion parameters from the best bipartite graph Correspondence between the feature points in one image with those in the otherCorner extractionZ must be a well-conditioned 2 £ 2 matrixBoth the eigenvalues must be large and should not differ by several orders of magnitudeTwo small eigenvalues means a roughly constant intensity profileA large and a small eigenvalue corresponds to a unidirectional texture patternIn practice, when the smaller eigenvalue is large enough, Z is well conditionedmin(1, 2) >  where  is a predefined constantFor more information: J. Shi and C. Tomasi, “Good Features to Track”, CVPR ’94yyxyyxxxIIIIIIIIZKanade-Lucas-Tomasi (KLT) trackerKLT is a C implementation of a feature tracker for the computer vision communityPublic domain code that is maintained by S. Birchfield at http://www.ces.clemson.edu/~stb/klt/Available for Unix/Linux and Visual StudioDemo of the KLT program to track features across a sequence of imagesFor more information: J. Shi and C. Tomasi, “Good Features to Track”, CVPR ’94RoadmapStructure from MotionBackgroundFeature based motion estimationKLT trackerFactorizationRigid body FactorizationMulti-body factorizationNon rigid body factorizationConclusionsAffine CameraPix and Piy are the projection vectors that take the point [X, Y, Z] to (x, y)Pix and Piy are 1 £ 4 row vector, i is the frame number and j is one of the 3D pointAffine projection preserves the center of gravity 1 10001 1jjjyixiijijjjjyixiijijZYXvuZYXvuPPPP ~~44jjjyixiijijyiijxiijZYXvuPvPuPPAffine CameraRepeating the same with all the 3D pointsLHS is the collection of the points detected in the imageRHS has the 3D points with the projection matrix    ~~~~~~P32121213222121PPPyixiPiPiiiPiiZZZYYYXXXvvvuuuPPRigid Body FactorizationDeveloped by Tomasi and Kanade in 1992Compute the measurement matrix WP feature points tracked across F framesPerform PCA using Singular Value Decomposition of the registered measurement matrixReconstruct the M (Motion) and S (Shape) using the top 3 singular valuesTPFPF 33332332ˆˆˆ~VUSMWTVUTWW ~PFPFFPFFFPFFPPvvvuuuvvvuuu332221211121111211SMW“Shape and Motion from Image Streams under Orthography: A Factorization Method”, IJCV, 1992Rigid Body Factorization (contd.)Rotation constraintsValid up to a linear transformation ARotational constraints to compute the parameters of AAAT is symmetricCan be estimated using eigen decompositionComputing the M and S after estimating the linear transformation APFPF 31333332332ˆˆSAAMSM011 fTTffTTffTTfjAAijAAjiAAiTPPFF 3213313333321333232ˆˆ,ˆˆVASAUMExperiments – Rigid Body FactorizationImplementation of the rigid body factorization30 Frames tracked using KLT trackerOnly tracks available over the entire sequence consideredMotion and Shape estimated using Singular Value DecompositionStructure estimated after computing the linear transformation Adata obtained from CMU image database http://vasc.ri.cmu.edu/idbExperiments – Rigid Body Factorization50 Frames tracked using KLT trackerEstimation of motion and structure using SVD of the tracked featuresViewing angle changed continuously to help visualize the hotel structuredata obtained from CMU image database http://vasc.ri.cmu.edu/idbRigid Body FactorizationAssumptions of the methodModeling of a Single BodyThe body is rigidThe camera projection is OrthographicRelaxation of the assumptionsSturm and Triggs, ’96 -