Computer Vision EECS 442
Popular in Course
verified elite notetaker
Popular in Engineering Computer Science
This 246 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 442 at University of Michigan taught by Staff in Fall. Since its upload, it has received 7 views. For similar materials see /class/231535/eecs-442-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Computer Vision
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
EECS 442 Computer vision Stereo systems 39Stereo vision 39 Rectification 39Correspondence problem Active stereo vision systems Reading HZ Chapter 11 FP Chapter 11 Stereo vision d 0 Goal estimate the position of P given the observation of P from two view points Assumptions known camera parameters and position K R T S rereo vision d 0 Subgook Solve the correspondence problem Use corresponding observations to rriongulo re Correspondence problem 039 0 Given a point in 3d discover corresponding observations in left and right images also called binocular fusion problem Triangulation 01 Intersecfing the two lines of sight gives rise to P Epipolar geometry Epipolar Plane 0 Epipoles e1 e2 intersections of baseline with image planes projections of the other camera center 0 Epipolar Lines vanishing points of camera motion direction 0 Baseline Parallel image planes P Rectification making 1wo images quotparallelquot gtvv39 Parallel image planes P 0 0 0 EtXR 0 0 T vv39 0 T 0 K1K2 known x parallel to 0102 Parallel image planes P o X T o pEp0 00 Ou39 0 uvlo 0 T 390 uvl T O Tvav39 Making image planes parallel 0 x ll39lquot l l E H t I 39 P g p a w ll I l l l n u I 0 O O 039 GOAL Estimate the perspective transformation H that makes the images parallel Proiec rive transformation Now we donquott have the destination image Making image planes parallel t I u I IIIII l 1 f I H r I P g p a w ll39l I gquot I quotI II 0 1 l 0 I O O 0 GOAL Estimate the perspective transformation H that makes the images parallel Impose v39v gt How gt Map eto infinity Making image planes parallel P gtKI 0P P P gtK39R TP Making image planes parallel P gtKI 0P P P gtK39R TP 1 Map e to the xaxis at loca rion 1 OlllT H1RHTH ee1 e2 1T gt 1 o 1T Making image planes parallel x i o I i c 39 I I 39 39 v 5 P P g P 39 w Ill o e I quot x 39c v u I o O OI O 2Send epipoletointinity gt e1 0 0T 1 0 0 H2 0 1 0 1 0 1 e1 0 1T gt 1 o 0T Minimizes the distortion in a neighborhood approximates id mapping Making image planes parallel l H Hl 0 l I i c 39 t vi p q I 39 39 Ia e e P I quotquotquot 39 1x c O p x I O O OI O 3 Define H H1 H2 4 Align epipolar lines No re H is not unique Proiec rive transformation of a line in 2D A t H 139H T1 Making image planes parallel H Hl 0 innu I I i v r I v 5 P P g P I 139 39 39l I I l e n l e I II I 1 I u c 1 x I O O OI O 3 Define H H1 H2 T T 4 Align epipolar lines H l H 1 Hz Ch We H see 3912 H H39 called matched pair of transformation Making image planes parallel Courtesy figure 5 Lazebnik Why rectification is useful 39 Makes the correspondence problem easier 39 Makes triangulation easy Computing dep rh Computing depth P Note Disparity is inversely proportional to depth Dispari ry maps Disparity map depth map httpvisionmiddleburyedustereo Stereo pair Disparity map with occlusions Stereo systems Stereo vision 39 Rectification 39Correspondence problem Active stereo vision systems Correspondence problem 039 0 Given a point in 3d discover corresponding observations in left and right images also called binocular fusion problem Correspondence problem 39A Cooperative Model Morr and Poggio 1976 Correlation Methods 1970 MultiScole Edge Matching Morr Poggio and Grimson 197981 FP Chapters 11 Correlation Methods 1 970 11 ll V w Slide the window along the epipolar line until ww is maximized courtesy slide to J Ponce Correlation Methods 1 970 HI 1 u l rW P v 2 e vj W gt lt l 3 w2 W WW39 W39 Normalized Correlation mInImIze W WW W Correlation methods Left Rig hf I N orm corr Credio slide 5 Lazebnik Correlation me rhods Smaller window More detail More noise Larger window Smoother dispa rity maps Less prone to noise Credii slide 5 anehnik Issues 39 Fore shortening effect 0 39 aquot 139 Il 1 I 39 n I 39Occlusions If is desirable to have small Bz ra rio Issues 39 small Bz ratio Small error in measurements implies large error in estimating depth Issues 39Homogeneous regions Hard to match pixels in these regions Issues Herns Repefi ive pa Correspondence problem is difficult Occlusions Fore shortening Baseline tradeoft Homogeneous regions Repetitive potterns Apply nonlocal constraints to help enforce the correspondences Results with window search Ground truth Windowbased matching 7 gt17 Vfrlii I7quot 7 39 quot y 7 39L39 39 i Credii slide 5 anehnik Improving correspondence Nonlocal constraints 39 Uniqueness For any point in one image there should be at most one matching point in the other image o Violates uniqueness constraint OC39 Left image Right image Oc courtesy slide to J Ponce Improving correspondence Nonlocal constraints 39 Uniqueness For any point in one image there should be at most one matching point in the other image 39 Ordering Corresponding points should be in the same order in both views courtesy slide to J Ponce Improving correspondence Nonlocal constraints 39 Uniqueness For any point in one image there should be at most one matching point in the other image 39 Ordering Corresponding points should be in the same order in both views Not always in presence of occlusions Dynamic Programming Bakerand Binford1981 Uses ordering constraint 1 z 3 4 5 5 39Nodes matched feature points eg edge points Arcs matched intervals along the epipolar lines Arc cost discrepancy between intervals Find the minimumcost path going monotonically down and right from the topleft corner of the graph to its bottomright corner courtesyslide to J Ponce Dynamic Programming Bakerand Binford1981 l 2 3 4 5 6 quotIE Loop over all nodes In I in asceudhlg order fnr k 1 to m do for I Initiallze optimal cost XL1 and backward pointer 30 I 7031 400 Bkl 4 ml 0 Loop aver all inferiar neighbors i j of In 1 far i j E Inferior 7 Na ghborsULJ do cu Compute new path cost and update backward pointer if necessary d F Cij Arc 7Jmtijkl ifd lt Ck l then CkJ lt7 d Bk l 7 ij endif endfor endfar endfur Construct cp ma path by following backward pointers from m n P F quotIvnll iaj F quotn n while 3m m1 do Lj F mm P F 111 u P 9ndwhilp coudesyslide 0 1 Ponce Dynamic Programming Ohio and Kanade 1985 Reprinted from quotStereo by Intra and InletScanline Search by Y Ohio and T Kanade IEEE Trans on Pattern Analysis and Machine Intelligence 72139154 1985 1985 IEEE Improving correspondence Nonlocal constraints Uniqueness For any point in one image there should be at most one matching point in the other image Ordering Corresponding points should be in the same order in both views 0 Smoothness Disparity is typically a smooth function of x expect in occluding boundaneg Smoo rhness Stereo matching as energy minimization m aEdataIlIZD Esm00LhD ZltVKi W21Di2 neighbors 1 ZpDz39 Dj 0 Energy funcfions of This form can be minimized using graph cufs Y Boykov o Veksler and R Zabih FasiApproximaie Energy Minimizaiion via Graph Cuis PAMI 01 c reansmes Luzebnik Stereo matching as energy minimization Ground truth Wind W4fmsed Graph cuts matching Y Boykov O Veksler and R Zabih Fast Approximate Energy Minimization via Graph Cuts PAMI Oi Twoframe s rereo correspondence algorithms Click here h p Zwwwmiddleburxedqufereoz Sfereo SDK sfereo vision soffwore developmenf kit A Criminisi A Blake and D Robe son M DSDR 7 Stereo SDK Demo video Realtime dense stereo matching Application foregroundbackground separation V Kolmogorov A Criminisi A Blake G Cross and C Rolher Bilayer seqmenlalion of binocular stereo video CVPR 2005 Click on ACriminisi i2i BilaxerSegmenfa onwmv h presea rch microso coman1crimdemosAC riminisiRecogni onCowDemowmv Application 3D Urban Scene Modeling 3D Urban Scene Modeling Integrating Recognition and Reconstruction N Cornelis B Leibe K Cornelis L Van Gool lJCV 08 Click on corneliscoqnitiveloopsvpcvpr06cwi httpwwwvisioneeethzchshowroomindexenhtml Stereo systems Stereo vision 39 Rectification 39Correspondence problem Active stereo vision systems Active stereo point D proiector 02 Replace one of the two cameras by a proiector Single camera Projector geometry calibrated Correspondence problem solved Ac rive s rereo s rripe proiec ror Proiec ror and camera are parallel Correspondence problem solved Laser scanning Digital Michelangelo Project http g raphicssta nford ed uprojectsmich 0 Optical triangulation Project a single stripe of laser light Scan it across the surface of the object This is a very precise version of structured light scanning Source 8 Seitz Laser scanning The Digital Michelangelo Proiecl Levoy el al Source S Seitz Active stereo shadows J Bouguet amp P Perona 99 Light source b O 1 camera1 light source very cheap setup calibrated the light source Active stereo shadows Click here Ac rive s rereo dense ll ro39ecfor P 0 o Dense reconsfruc on Correspondence problem again Ge around if by using color codes L Zhang B Curless and s M Seiiz Rapid Shape Acquisition Using Color Structured Light and Multi pass Dynamic Programming SDFVTZOOZ L Zhang B Curless and s M Seiiz Rapid Shape Acquisition Using Color Structured Light and Multi pass Dynamic Programming SDFVTZOOZ Rapid shape acquisition Proiecfor sfereo cameras Nex r lecture Volumetric s rereo Human Stereopsis n FHTE39ETF E 7 LARK i i 17 ESEFail N fquot L v l C MEI MMCF f39Equot3939nquotlLquot u 3 V r V V r 739 v 77 Figure from US Navy Manual of Basic Optics and Optical Instruments prepared by Bureau of Naval Personnel Reprinted by Dover Publications Inc 1969 Credit slide J Ponce H u ma n Sfereopsis Reconstruction ViethML39l39ller Circ Disparate dot Disparity d rI DF dlt0 In 3D the horopfer Credit dide J Ponce H uman Stereopsis Reconstruction What if F is not known Helmoltz 1909 0 There is evidence showing the vergence angles cannot be measured precisely Humans get fooled by basrelief sculptures Credit slide J Ponce Human S rereopsis Binocular Fusion Credit slide J Ponce EECS 442 Computer vision Detectors part I Edge feature detectors Corner feature detectors Reading FP Chapters 89 Some slides of this lectures are courtesy of prof F Li prof S Luzebnik and various other lecturers Goal Identity interesting regions from the images edges corners blobs Matching Indexing Recognition Linear filtering Convolution fgmn Zfkl gm kn l Smoothing 39 Differentiation Smoothing with a Gaussian 39 Weight contributions of neighboring pixels by neorness 0003 0013 0022 0013 0003 0013 0059 0097 0059 0013 0022 0097 0159 0097 0022 0013 0059 0097 0059 0013 0003 0013 0022 0013 0003 5X5o1 Slide credit Christopher Rasmussen Smoothing with a Gaussian Differentiation and convolution a z fxnly my x Ax Original Image 64 2DKerne 2DKerne 21012 101 21012 101 21012 101 21012 21012 Rudimentary edge etector Edg e re rion What causes an edge Identifies sudden changes in an image Depth discontinuity Surface orientation discontinuity Reflectance discontinuity ie change in surface material properties Illumination discontinuity eg shadow Edge Detection Criteria for optimal edge detection Canny 86 Good detection minimize the probability of false positives detecting spurious edges caused by noise false negatives missing real edges Good localization edges must be detected as close as possible to the true edges Sinqle response constraint minimize the number of local maxima around the true edge ie detector must return single point for each true edge point Edge Detection Examples True Poor robustness Poor edge to noise localization Too many responses Designing an edge detector 39 Edge a location with high gradient thus use derivatives 39 Need two derivatives in x and y direction 39 Need smoothing to reduce noise prior to taking derivative S1gma 50 7Q fg d 30 1 A w 1 x 1 0 200 400 600 1000 1200 1400 1600 1000 2000 1 1 1 1 1 1 2 g 1 gt 1 1 1 81 1 1 0 200 400 600 E00 1000 1200 1400 1600 1000 2000 E 1 3 1 1 3 1 1 1 E 1 N a E 1 1 1 50 1 1 1 1 1 0 200 400 600 000 1000 1200 1400 1600 1300 2000 Source S Seitz Edge by Derivative of Gaussian 39 We can use derivative of Gaussian filters I Why Gaussian filter is needed for smoothing the image Ditferentiation can be modeled by a convolution Convolution is associative D Gl I Edge by Derivative of Gaussian Canny Edge Detection Most widely used edge detector in computer vision First derivative of the Gaussian closely approximates the operator that optimizes the product of signalfo nOIIse ratio and localization Analysis based on quotstepedgesquot corrupted by lladditive Gaussian noisequot Canny Edge Detection Steps 1 Gaussian smoothing 2 amp Derivative Derivative of Gaussian 3 Find magnitude and orientation of gradient 4 Extract edge points Nonmaximum suppression39 5 Linking and thresholding Hysteresis 39 Matlab edge I canny Canny Edge Detector First 2 Steps Smoothing C 2 e 2039 139 gX9 1 81 g 0 Derivative SVg1Vg1 1 gx 1 gx Vg gy gy Canny Edge De rec ror Derivative of Gaussian Canny Edge De rec ror First 2 Steps S X S y gradient vec ror Canny Edge De rec ror Third S rep magnitude and direction of S S X S y magnitude 1Si Si S direction 49 tan 1 S y X gradient magnitude Canny Edge Detector Fourth Step Non maximum suppression 0 Slice gradient magnitude along the gradient direction 0 Mark the point along the slide where the magnitude is max Nonmaximum suppression I I Gradient I 139 I E Linking to the next edge point Assume the marked point is an edge point Take the normal to the gradient at that point and use this to predict continuation points either r or s Examples NonMaximum Suppression EDD LJ L4 a W Nonmaxima suppressed Original image Gradient magnitude Slide credit Christopher Rasmussen Canny Edge Detector Step 5 Thresholding 39 Set a threshold T to suppress gradients with magnitude lt T strong edges weak edges high threshold low threshold Canny Edge Detector Step 5 Hysteresis Thresholding Hysteresis A lag or momentum factor Idea Maintain two thresholds khigh and kIOW Use khigh to find strong edges to start edge chain Use klow to find weak edges along the edge chain 0 Typical ratio of thresholds is roughly khigh klow 2 E O L U G L L L U G L G U gt L Effect Of 0 Gaussian kernel spreadsize original Canny with 039 1 Canny with r 2 The choice of 6 depends on desired behavior large a deiecis large scale edges small a deiecis fine features Source 5 Sen Demo httpwwwcswashinqtoneduresearChimagedatabasedemoedge O rher edge detectors Sobel CannyDeriche Differential Corners H Eovm Repeatability The same feature can be found in several images despite geometric and photometric transformations Saliency Each feature is found at an quotinterestingquot region of the image Locality A feature occupies a quotrelatively small area of the image Repeatability Illumination invariance Scale invariance Pose invariance Harris corner de rec ror CHarris and MStephens quotA Combined Corner and Edqe Detector Proceedings of the 4th Alvey Vision Conference pages 147151 Harris Detector Basic Idea f 21 l 1 H i I l WW7 I I X quotflatquot region no change in all directions quotedgequot no change along the edge direction quotcornerquot significant change in all directions Harris Detector Mathematics Change of intensity for the shift UV 2 Eu v Z wx y 1x u y v 3 y xay Wi d w Window function WXy Shifted intensity 1 in window 0 outside Gaussian Harris Detector Mathematics For small shifts UV we have a biI39nearapproximation u Euv E uv M v where M is a 2x2 matrix computed from image derivatives 2 I I 12 11 M WXy x x y 2 2 X Z Xzy ny Z IXIy 21y Secondmoment matrix Gradient with respect to x times gradient with respect to y Sum over a small region around I gy I the hypothetical corner 1i Matrix is symmetric Slide credit David Jacobs Secondmoment matrix First consider case where dominant gradient directions aligned with x or y El 2211 if 1 O O O Secondmoment matrix First consider case where dominant gradient directions aligned with x or y M 21 ZIXIy 21 0 ZIXIY 21 0 x12 o If either A is close to 0 then this is an edge Secondmoment matrix First consider case where dominant gradient directions aligned with x or y M 21 ZIXIy 21 0 ZIXIY 21 0 22 I O no If both As are close to 0 then this is a flat region Secondmoment matrix First consider case where dominant gradient directions aligned with x or y 1 1ng ZIXIY 21y or 0 22 Lambda 1 2 are the eigenvalues of C Harris Detector Mathematics Classi cation of 7V2 image points using Comer elgenvalues ofM M and A2 are large 7V1 quot 7V2 E increases in all directions XI and K2 are Small I 1aniorl E is almost constant in all directions F 39 0 Hi In 12 7 MI 3 m 3 mm H E h Harris Detector Mathematics Measure Of COI IICI39 I39CSpOIlSCI R detM kt1raceM2 det M 2 X112 traceM A 12 k empirical constant k 004006 Harris Detector Mathematics 7V2 R depends only on eigenvalues of M R is large for a corner R is negative with large magnitude for an edge R is small for a at region Corner Harris Detector Algorithm Filter image with Gaussian to reduce noise Compute magnitude of the x and y gradients at each pixel Construct M in a window around each pixel Harris uses a Gaussian window Compute ks of M Compute R detM ktraceM2 If Rgt T a corner is detected retain point of local maxima Ha rris De rec ror Workflow Ha rris De rec ror Workflow Compute corner response R Ha rris De rec ror Workflow Find points with large corner response Ri threshold Ha rris De rec ror Workflow Take only the points of local maxima of R Ha rris De rec ror Workflow Harris De rec ror Some Properties 0 Ro ra rion invariance I Comer response R is invariant to image rotation C U 1 Aquot 0 U 39 0 A gt R Rt1 7t doesn 1 change 2 Harris De rec ror Some Properties 0 But noninvariant to image scale nu gt Er All points Will be Corner classi ed as edges Harris Detector Some Properties Partial invariance to affine Ihfensifychange invariance to intensity shift gt 19 only derivatives are used 0 Intensity scale gt a AVA A M A A W W x image coordinate x image coordinate EECS 442 Computer vision Multiple view geometry Affine structure from Motion Affine structure from motion problem Algebraic methods Factorization methods Reading HZ Chapters 61418 FP Chapter 12 Some slides of this lectures are courtesy of prof J Ponce prof FF Li prof S Lazebnikamp prof M Hebert S rruc rure from motion problem Given m images of nfixed 3D poin rs XUMin i1 j1 Structure from motion problem estimate From the mxn correspondences Xi m proiection matrices M mo on 7 3D pOims X structure Affine structure from motion simpler problem Image From the mxn correspondences X estimate 139 m proiection matrices M affine cameras n 3D points X Fini re cameras XKR TX M Perspective projection matrix ax 3 X0 K O ay yO M K3X O O 1 Homography in 2D Affine cameras xKm X Proiective case a X 1 O O X 0 R T K 0 yo MK 0 1 0L 1 O 1 0 O O Attinecase ax 1 0 0 0 R T K O MK O 1 0 0L 1 0 0 0 1 Parallel projection matrix points at infinity are mapped as points at infinity Orthographic Proiec rion r R 1 0 0 q K 0 1 0 39Q 0 0 1 p 12 WeakPerspective Proiec rion r R a 0 0 VlSccing1 unc onoffhedismnce K 0 ay 0 9 Q 0 0 1 T Orthographic Proiec rion r R 100 q K2010 399 001 p 12 WeakPerspective Proiec rion Affine cameras X KR T X Homogeneous ax s 0 1 0 0 0 R T Kan0 MK010001 0 0 1 0 0 0 1 1 0 0 0 a11 a12 a13 b1 A b M3gtlt3af ne 0 1 0 0 4x4af ne a21 a22 2123 b2 0 I 0 0 0 1 0 0 0 1 X b X x X all an 2113 Y 1 AbMEuc nonhomogeneous y 2121 122 2123 Z b2 1 imagecoordinafes MEuc M Affine cameras M camera matrix To recap from now on we define M as the camera matrix for the affine case x X AXbMX MA b y 1 The Affine StructuretromMotion Problem Given m images of ntixed points Xi we can write P pi J VL I Ain t bl for t 1m and j 1 in Problem estimate the m 2x4 matrices Mi and the n positions Pi from the mgtltn correspondences pii How many equations and how many unknown 2m x n equations in 8m3n unknowns Two approaches Algebraic approach affine epipolar geometry Factorization method Algebraic analysis 2view case Homogeneous sy em pAPb A PHJ Betti 520 au ualm lyl60 Algebraic analysis 2view case mu 53931 If21 lm 5 U 3911 139 U 1 H11 1 vquot 0 Where F E quot If 0 1 1quot f3 5 The Affine Fundamental Ma rrix Affine Epipolar Geometry Note The epipolar lines are parallel Estimating F mu t I milMl 5quot ill I 5 139 0 Measurements u u39 v v39 From at least 4 correspondences we obtain a linear system on the unknown alpha beta etc I I 111 V1111 V11 Computed by least square and by enforcing t 1 Estimating proiection matrices from epipolar constraints If Mi and Pi are solutions then Mi39 and Fi39 are also solutions where I MMQ and I and d Cquot 7C 1d Q0T l w1th QlOT 1 Proof 1 1 We ltgllt 7gtmltpgt Affine ambiguity w ltii gt 5gt x PX mg QA X Estimating proiection matrices from epipolar constraints Estimating proiection matrices from epipolar constraints MCA b M A b P t t t MMQ Memo 39 P Choose Q such that 1r00 0010 MU100Mab C 113 Canonical affine cameras N 0 01 100 At t A 010 N T N T b O O b El Function of the parameters of F Estimating proiection matrices from epipolar constraints MCA b M A b P t t t MMQ Memo 39 P Choose Q such that 1r00 0010 MU100Mab C 113 By reenforcing the epipolar constraint we can compute a b c d directly from the measurements Reminder epipolar consfrainf Homogeneoussy em A m AIPM A p 1 0 au w a u l v 6 O Estimating proiection matrices from epipolar constraints MA b M A b P MMQ M 2M Q P QIP Chooseruch that 0010 Mi010 0 Mabcd P A b Reenforce the Epipolar constraint 1 0 D u p b 0 l 0 39L Bat A 10 bi D gt Bat Jr 0 1 u U a b c 13 d Estimating proiection matrices from epipolar constraints MA b M39A39 b P M M9 M M Q P 9113 Choose Q such that 0010 Jim 01 JIM ab Cd P A b 1 O O u I 1 0 7U I 1 I I 391 D91 0 D 1 u cm bL l cu 1 d U a b C 11 d Estimating proiection matrices from epipolar constraints 1 U l u 0 l U 3911 D91 0 U 1 I an bi CH L d l a b c 1quot d Linear relationship between measurements and unknown Unknown a b c d Measurements u u v v From at least 4 correspondences we can solve this linear system and compute a b c ol via least square The cameras can be computed How about the structure Estimating the structure from epipolclr constraints 10 0 u U 10 U 13 0 01 u 710 a h H rl Can be solved by least square again A factorization method Tomasi amp Kanade algorithm C Tomasi and T Kanade Shape and motion from imaqe streams under orthoqraphy A factorization method IJCV 9237154 November 1992 Centering the data 39 Factorization A factorization method Centering the data Centering subtract the centroid of the image points A factorization method Centering the data Centering subtract the centroid of the image points 12 xi x AiXJ 10i liAiXk bi J k1 A factorization method Centering the data Centering subtract the centroid of the image points 1 1 A 1 n 1 xi 2x1 Hxik AiXJ 1i 1Aixk b 1 n A AiXj HXkAin Assume that the origin of the world coordinate system is at the of the 3D points After centering each normalized point xi is related to the 3D point X by Xi AiXJ A factorization me rhod Centering the data A factorization method factorization Let39s create a 2m gtltn data measurement matrix X11 X21 gt4 m1 X12 quot39 Xln i i 22 2 cameras 2 m Xm2 i an points 1 A factorization method factorization Let39s create a 2m x n data measurement matrix A1 D 21 22 Zn 2 X2 A A A 39 Xm1 sz an LA 2 quot X n 2m x 3 The measurement matrix D M S must have rank 3 it39s a product of a 2mx3 matrix and 3xn matrix Factorizing the measurement ma rrix Source M Hebert Foc rorizing The measurement ma rrix Singular value decomposition of D II I H n D U X W VT 17 l g Source M Heber Foc rorizing The measurement ma rrix Singular value decomposition of D l II II W VT Source M Heber Factorizing the measurement matrix Obtaining a factorization from SVD ll 3 lt gt lt gtA 2171 D 3 X VJ if structure Motion cameras What is the issue here D has rankgt3 because of measurement noise affine approximation Factorizing the measurement matrix Obtaining a factorization from SVD I1 gt 2171 D V T I 3 structure Theorem Vhen D has a rank greater than p LIPVVPVw is the best possible rankp approximation of D in the sense of the Frobenius IlOI39IIL An L13 D ugwgvg 7 WM Affine ambiguity D x The decomposition is not unique We get the same D by using any 3X3 matrix C and applying the transformations M gt MC S gtC39lS We can enforce some Euclidean constraints to resolve The ambiguity more on this next lecture Algorithm summary Given m images and n features x For each image 139 center the feature coordinates Construct a 2m X n measurement matrix D Column contains the proiection of point 39in all views Row 139 contains one coordinate of the proiections of all the n points in image 139 Factorize D Compute SVD D U WVT Create U3 by taking the first 3 columns of U Create V3 by taking the first 3 columns of V Create W3 by taking the upper left 3 X 3 block of W Create the motion and shape matrices M U3W3V2 and S W3V2 V3T or M U3 and S W3V3T Eliminate affine ambiguity Reconstruction results 20 C Tomasi and T Kanade heoeandmO39tionfrom imagestreamwnderorthography A factorization method lJCV 92137154 November 1992 EECS 442 Computer vision Epipolar Geometry 39 Why is stereo usefula 39 Epipolar constraints 39 Essential and fundamental matrix 39 Estimating F Examples Reading AZ Chapters 4 9 11 FP Chapters 10 Recovering structure from a single view ow c Scene Calibration rig Camera K From calibration rig gt locationpose of the rig K From points and lines at infinity orthogonal lines and planes gt SlrUClure Of lhe scene39 K Knowledge about scene point correspondences geometry of lines amp planes etc Recovering structure from a single view Calibration rig Camera K Why is it so difficult Intrinsic ambiguity of the mapping from 3D to image 2D Recovering structure from a single view Intrinsic ambiguity of the mapping from 3D to image 2D Cmrtesyshdes mer Two eyes help Two eyes help 02 V O This is called triangulation Triangulation 0 Find X that minimizes d2x19P1X d2x29P2X Stereoview geometry Scene geometry Find coordinates of 3D point from its proiection into 2 or images Correspondence Given a point in one image how can I find the corresponding point x39 in another one 53 Camera geometry Given corresponding points in two images find camera matrices position and pose Epipolar geometry Epipolar Plane 0 Epipoles e1 e2 intersections of baseline with image planes projections of the other camera center 0 Epipolar Lines vanishing points of camera motion direction 0 Baseline Example Converging image planes Example Parallel image planes Baseline intersects the image plane at infinity Epipoles are at infinity Epipolar lines are parallel to x axis Example Parallel image planes e at aquot e quot at Exa mple Forwa rd translation Oz The e ipoles have same position in both images Epipole called FOE focus of expansion Two views ot the sarne obied Suppose I know the camera positions and camera matrices Given a point on iett image how can Mind the corresponding point on right irnagez Epipolar Constraint 0 Potential matches for p have to lie on the corresponding epipolar line 0 Potential matches for p have to lie on the corresponding epipolar line Epipolar Constraint Epipolar Constraint R T 039 V pT T x 0 K1 and K2 are known calibrated cameras Perpendicular ro epipolar plane Cross product as matrix multiplication agtltb a2 0 a by axb Epipolar Constraint OI RT V pTTXR p 0 gtpTTxRp390 E essential ma rrix LonguefHiggins 1981 Epipolar Constraint E x2 is the epipolar line associated with x2 I1 E x2 ET x1 is the epipolar line associated with x1 I2 ET x1 E is singular rank two Ee20 and ETe1 0 E is 3x3 matrix 5 DOF Epipolar Constraint unknown Epipolar Constraint p K39pI OI pT TxRp39 0 gtK 1 pf LlR p390 pT KT Kr l pr0gtp Epipolar Constraint p gtKp p39 gtK39p39 pTF 0 F Fundamental Ma rrix Faugeras and Luong 1992 Epipolar Constraint F x2 is the epipolar line associated with x2 I1 F x2 FT x1 is the epipolar line associated with x1 I2 FT x1 F is singular rank two Fe20 and FTe1 0 F is 3x3 matrix 7 DOF Suppose F is known No additional information abouHhe scene and camera is given Given a point on left image how can Ifind the corresponding point on right irnagez Why F is useful 0 F captures information about the epipolar geometry of 2 views camera parameters MORE IMPORTANTLY F gives constraints on how the scene changes under view point transformation without reconstructing the scene 0 Powerful tool in 0 3D reconstruction Multiview obiectscene matching Estimating F The EightPoint Algorithm Longue rHiggins 1981 Hartley 1995 O 0 u u39 P gtp V P gtp39 V39 pTFp3920 Estimating F T r p F p 0 gt F11 F12 F13 1139 11 711 7 Pigg F2 7 0 quot31 1 32 Far 1 I I I I I I 7M77MU77U771U7U7U71 1 q Let s take 8 corresponding points Estimating F IJH CI 4 iqu Aq uounlos 39bs1 lt 8ltNJ V enbgun s4sgxe uounlos OJGZUOUV 4 8 IUDH o 0 JAA warss snoeue oon E18 lt J J N r I 8 n En 5338 nm 8n ringn nsm AA quot n quotin in air nin in fan sn lirain 9a an 9n 5 2939fit Ej39ragn 9n Eg ragn Einu lrr I1 r 111 1 j 1 I 1 JLE If quotIt 143 INJQ 4 ringn IE zra g JI39L 11 En Fa Em infra m a 5m En in rm n 31 9n EerETn 51113 1 LITn El n Fl 139 I39 E J 1 I n n Er grain nal1 in Efrain Elinan 1 EH 11 ERIE Eula In Efll ERIN l Buunwusg Rank2 constraint pT 0 The estimated F may have full rank detF 0 F should have rank2 instead F zo Frobenius norm Find F that minimizes Subiect to detFO SVD again can be used to solve this problem Normalization Is the accuracy in estimating F function of the ref system in the image plane Eg under similarity transformation T scale translation qi Ti pi ql Ti pl Does the accuracy in estimating F change if a transformation T is applied EIgt QEI A L a A Data courtesy ofR Mohr and B Boufama With transformation Without transformation 9 pixel 1 Oplxel 09pixel Mean errors 10 Oplxel Mean errors Normalization The accuracy in estimating F does change if a transformation T is appHed Why Wf0 Hft1 gt F The constrain under which W H is minimized is not invariant under similarity transformation Same issue for the DLT algorithm XI 2 H Xi Section 44 inAZ Normalization Transform image coordinate system T translationscaing such that Origin centroid of image points Mean square distance of the data points from origin is 2 pixels 1i 2 Ti pi qi Ti p normalization The Normalized EightPoint Algorithm 0 Compute Ti and Ti39 1 Normalize coordinates qi Ti pi ql Ti pl 2 Use the eightpoint algorithm to compute F39Cl from the points q iand q39i qT Fq q39 0 detFqO l Enforce the rank2 constraint gt Fq 2 Denormalize Fq F T39TFqT Example Parallel image planes X 01 X 02 K1K2 known 2 Hin r xpc1rc1llel roO1O2 E 39 RI tT00 Example Parallel image planes X K1 K2 known E2 EtXR 0 0 T 0 T 0 x parallel to 0102 Example Parallel image planes X Rectification making two images quotparallelquot Why it is useful Epipolar constraint gt y y39 Application view morphing S M Sei rz and C R Dyer Proc SIGGRAPH 96 1996 2130 rvIr I39rj f 1 39i Mia J g Virtual Cameras x39 r t N II L FH Morphing without using geometry Rectification I m ll C E II 6 r m m 0 r F EECS 442 Computer vision Fitting methods Problem formulation Least square methods RANSAC Hough transforms Multimodel fitting Fitting helps matching Reading HZ Chapters 4 11 FP Chapters 16 Some slides ofthis lectures are courtesy of profs S Lazebnik amp K Grauman Fitting Goal Choose a parametric model to fit a certain quantity from data Lines Curves Homographic transformation Fundamental matrix Shape model Example Computing vanishing points Example Estimating an homographic transformation Example Estimating F Example fi r ring cm 2D shape rempla re 20 JD ED 8 HIM Example fitting a 3D obiec r model Fitting Goal Choose a parametric model to fit a certain quantity from data Critical issues noisy data outliers missing data Critical issues noisy data 2 I Critical issues noisy data infraclass variability 20 JD ED 8 HIM Critical issues outliers Critical issues missing data occlusions Fitting Goal Choose a parametric model to fit a certain quantity from data Techniques Least square methods l 0 RAN SAC Hough transform EM Expectation Maximization forthcoming lecture Least squares me rhods fitting a line 0 Data x1y1 xmyn 0 Line equation 32 mxl b 0 Find m b to minimize E 2 211 yi m xi b2 Least squares me rhods fitting a line E yi mxi by 2 Ezzyi xi 1m y llY XBIIZ yn Xn Y XBTY XB YTY 2XBTYXBTXB d1 2XTXB 2XTY 0 dB T T 1 X XB X Y 39 B XTY Normal equafon Least squares methods fitting a line Axb 0 More equations than unknowns 0 Look for solution which minimizes AXb AXbTAXb Solve aAx bTAx b 6x1 0 0 LS solution x ATA 1ATb Least squares me rhods filling a line Solving x AZA1Atb A AtAYlAt pseudoinverse of A A UZVt SVD decomposition of A A 1 VZ1U A VZ U 1 WI rh 2 equal to Z for all nonzero smgular values and zero otherwise Least squares methods fitting a line E 21371 mXi b2 B XTX 1XTY B Limitations 0 Not rotationinvariant Fails completely for vertical lines Least squares methods 0 Distance between point xmyn and line axbyd 0 Find a b d to minimize the sum of squared perpendicular distances fitting a line EZZ11 a xi byi 12 UTU data model parameters Least squares me rhods fitting a line AhO MinimizeAh subject to h1 AUDVT h 2 last column of V Least squares methods fitting on homography ma h 1 1 II 12 1713 wy h 1 I122 123 y W 113 1 1132 h 33 l Least squares methods fi ing an homography 1111Xl112yl1137131XXih32yxlix 0 hm hzzy 1123 i 173190 hazyy39 y 0 From ngt4 corresponding points x 1 1 l 0 O 0 7X1 Vr l 7y 1 X l ix l 0 0 0 X1 yl 1 any1 ylyll ay l hu 0 y l 0 O 0 iszquot avgx z ix z h 0 O 0 xz yg 1 7x2quot argy z 7 v2 I I h3 3 X11 n l 0 0 O XnVfl 7quotsz11 7X11 7 0 0 O X11 yn 1 XLYL iyllyfl yfz 0 Least squares Robustness to noise Least squares Robustness to noise 2 outlier i 39 o it oNI Problem squared error heavily penalizes outliers Critical issues outliers CONCUMSHGN Least square is not robust wrt outliers 7 m i Least squares Robust estimators General approach minimize Zpuixi0o39 1 MI 96 6 residual of i 1 point wrt model parameters 6 p robust function with scale parameter 6 u 210 mX b2 The robust function p favors a configuration with small residuals Penalizes large residuals Least squares Robust estimators I3 4 Good scale parameter 0 2quotle 2 4 n M 5 ff a 4 ff b firx x 3 x x 1D 12 14 I 14 1 1 3 B 4 2 U 2 4 E The effect of the outlier is eliminated Least squares Robus r es rima rors 4 Bad scale parameter 0 too small 0 w Least squares Robust estimators 4 Bad scale parameter 0 too large Same as standard LSQ 2 393 vulg f FJ quot39 2 f f 4 B B CONCLUSON2 Robust estimator useful it prior info about the distribution of points is known Robust fitting is a nonlinear optimization problem iterative solution Least squares solution provides good initial condition Fitting Goal Choose a parametric model to fit a certain quantity from data Techniques Least square methods RAN SAC Hough transform
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'