CSE486, Penn StateRobert CollinsLecture 14Parameter EstimationReadings T&V Sec 5.1 - 5.3CSE486, Penn StateRobert CollinsSummary: TransformationsprojectiveaffinesimilarityEuclideanCSE486, Penn StateRobert CollinsParameter EstimationWe will talk about estimating parameters of1) Geometric models (e.g. lines, planes, surfaces)2) Geometric transformations (any of the parametric transformations we have been talking about)Least-squares is a general strategy to address both!CSE486, Penn StateRobert CollinsParameter Estimation:Fitting Geometric ModelsGeneral Idea:• Want to fit a model to raw image features (data) (the features could be points, edges, even regions)• Parameterize model such that model instance is an element of Rn i.e. model instance = (a1,a2,…,an)• Define an error function E(modeli , data) that measures how well a given model instance describes the data• Solve for the model instance that minimizes ECSE486, Penn StateRobert CollinsExample : Line FittingGeneral Idea:• Want to fit a model to raw image features (data) (the features could be points, edges, even regions)• Parameterize model such that model instance is an element of Rn i.e. model instance = (a1,a2,…,an)• Define an error function E(modeli , data) that measures how well a given model instance describes the data• Solve for the model instance that minimizes ECSE486, Penn StateRobert CollinsPoint Feature Datapts = [... 17 81; 23 72; 35 73; 37 58; 45 50; 57 56; 61 36; 70 32; 80 32; 84 19]Point features = {(xi,yi) | i = 1,…,n}x yCSE486, Penn StateRobert CollinsExample : Line FittingGeneral Idea:• Want to fit a model to raw image features (data) (the features could be points, edges, even regions)• Parameterize model such that model instance is an element of Rn i.e. model instance = (a1,a2,…,an)• Define an error function E(modeli , data) that measures how well a given model instance describes the data• Solve for the model instance that minimizes ECSE486, Penn StateRobert CollinsLine Parameterizationy = m * x + bm = slopeb = y-intercept (where b crosses the y axis)Model instance = (m,b)xybdydxm = dy/dx(The astute student will note a problem with representing vertical lines)CSE486, Penn StateRobert CollinsExample : Line FittingGeneral Idea:• Want to fit a model to raw image features (data) (the features could be points, edges, even regions)• Parameterize model such that model instance is an element of Rn i.e. model instance = (a1,a2,…,an)• Define an error function E(modeli , data) that measures how well a given model instance describes the data• Solve for the model instance that minimizes ECSE486, Penn StateRobert CollinsLeast Squares• Given line (m,b)• distance of point (xi,yi) to line is vertical distance• E is sum of squared distances over all pointsdixiyim xi + b(m,b)(L.S. is just one type oferror function)CSE486, Penn StateRobert CollinsExample : Line FittingGeneral Idea:• Want to fit a model to raw image features (data) (the features could be points, edges, even regions)• Parameterize model such that model instance is an element of Rn i.e. model instance = (a1,a2,…,an)• Define an error function E(modeli , data) that measures how well a given model instance describes the data• Solve for the model instance that minimizes ECSE486, Penn StateRobert CollinsCalculus to Find Extrema• Take first derivatives of E with respect to m, b• Set equations to zero• Solve for m, b*DOING DERIVATION ON THE BOARD*Note equivalenceto linear regressionCSE486, Penn StateRobert CollinsLeast Squares Solutionm = -0.8528 b = 94.3059CSE486, Penn StateRobert CollinsProblem with Parameterization•There is a problem with our parameterization, namely (m,b) is undefined for vertical lines•More general line parameterization such that•Question for class: why do we need the quadratic constraint?•Another question: what is relation of this to y=mx+b?CSE486, Penn StateRobert CollinsLS with Algebraic DistanceAlgebraic DistanceWill derive on board. Result: (a,b,c) is eigenvector associated with smallest eigenvalue(it will only be 0 if there is no noise, and therefore allthe points lie exactly on a line)CSE486, Penn StateRobert CollinsLS with Algebraic DistanceNote much different from linear regression line (in this case)but we can rest assured that our program won’t blow up whenit sees a vertical line!CSE486, Penn StateRobert CollinsAlgebraic Least Squares Issues• Note: I didn’t draw the error vectors on the plot• That’s because I don’t know what to draw…• Main problem with algebraic distances: Hard to say precisely what it is you are minimizing, since algebraic distances are rarely physically meaningful quantitiesCSE486, Penn StateRobert CollinsOrthogonal Least Squares•Minimize orthogonal (geometric) distance.•Makes sense physically, but harder to derive•Representation: such that(compare with algebraic distance)Distance measuredperpendicular to lineCSE486, Penn StateRobert CollinsOrthogonal Least SquaresHarder to derive.Key insight: best fit line must pass through the center of mass of the set of points!Move center of mass to the origin.This reduces the problem to finding a unit vector normal to the line: (a,b) s.t. a2+b^2=1This will be minimum eigenvector of scatter matrix of the points. Finally, solve for cCSE486, Penn StateRobert CollinsOrthogonal Least Squares Solution“distance” means what we intuitively expect(i.e. distance to closest point on line, or minimum distance to line)center of massCSE486, Penn StateRobert CollinsParameter Estimation:Estimating a TransformationGeneral Strategy• Least-Squares estimation from point correspondencesTwo important (related) questions:•How many degrees of freedom?•How many point correspondences are needed?Let’s say we have found point matches between two images, andwe think they are related by some parametric transformation (e.g. translation; scaled Euclidean; affine). How do we estimate theparameters of that transformation?CSE486, Penn StateRobert CollinsExample: Translation Estimationequationsmatrix formHow many degrees of freedom?How many point correspondences are needed?How many independent variables are there?TwoEach correspondence