第7讲 模型拟合 深圳大学 机器视觉及应用 课件

1、2 2/ /3/4/H5/6/A7/Slide from Silvio Savarese8/H9/Slide from Derek Hoiem10/Slide from Derek Hoiem11/Slide from Derek Hoiem12/)()()(2111221112ApApyApyyyApTTTnnniiiyybmxxybmxE220TTdEdpA ApA yniiibxmyE12)(xi, yi)y=mx+byAAApyAApATTTT1Matlab: p = A y;Modified from S. Lazebnik13/Slide from S. Lazebnik14/(x

2、i, yi)ax+by+c=0Unit normal: N=(a, b)proof: http:/ yi)ax+by+c=0Unit normal: N=(a, b)niiicybxaE12)(16/niiicybxaE12)(xi, yi)ax+by+c=0Unit normal: N=(a, b)12()0niiiEaxbyccybxaxnbxnacniinii11ApApTTnnniiibayyxxyyxxyybxxaE21112)()(Solution is eigenvector corresponding to smallest eigenvalue of ATAppApAp pp

3、 ApApTTTTTTminimize1 s.t.minimize/wiki/Rayleigh_quotient17/ 1 s.t. minimizexxAxAxTTTxxAxAxTTTminimize0 osolution t lsq trivial-nonMx1.21:)eig(,vxAAvnTbAx osolution t squaresleast bAx2 minimizebAx bAAAxTT1(matlab)18/19/Problem: squared error heavily penalizes outliers20/21/ ;,xu

4、iiiThe robust function Favors a configuration with small residuals Constant penalty for large residualsn1i2ii)bxmy(u22/The effect of the outlier is minimized23/The error value is almost the same for everypoint and the fit is very poor24/Behaves much the same as least squares25/26/27/xybmy = m x + bG

5、iven a set of points, find the curve or line that explains the data points bestP.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959 Hough spaceSlide from S. Savarese28/xybmxym3533223 711 10432 31452210133b29/xyIssue : paramete

6、r space m,b is unboundedP.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959 Hough space siny cosx Use a polar representation for the parameter space 30/featuresvotesNoisy data31/cTemplate32/ModelTemplate33/ModelTest image34/B

7、. Leibe, A. Leonardis, and B. Schiele, Combined Object Categorization and Segmentation with an Implicit Shape Model, ECCV Workshop on Statistical Learning in Computer Vision 2004training imagevisual codeword withdisplacement vectors35/B. Leibe, A. Leonardis, and B. Schiele, Combined Object Categoriz

8、ation and Segmentation with an Implicit Shape Model, ECCV Workshop on Statistical Learning in Computer Vision 2004test image36/37/),(PfOminOPI,:such that:TTPPPPf1),(Model parameters(RANdom SAmple Consensus) :Learning technique to estimate parameters of a model by random sampling of observed data38/A

9、lgorithm: Sample (randomly) the number of points required to fit the model Solve for model parameters using samples Score by the fraction of inliers within a preset threshold of the modelRepeat 1-3 until the best model is found with high confidence39/Algorithm: Sample (randomly) the number of points

10、 required to fit the model (#=2) Solve for model parameters using samples Score by the fraction of inliers within a preset threshold of the modelRepeat 1-3 until the best model is found with high confidenceIllustration by SavareseLine fitting example40/Algorithm: Sample (randomly) the number of poin

11、ts required to fit the model (#=2) Solve for model parameters using samples Score by the fraction of inliers within a preset threshold of the modelRepeat 1-3 until the best model is found with high confidenceLine fitting example41/6INAlgorithm: Sample (randomly) the number of points required to fit

12、the model (#=2) Solve for model parameters using samples Score by the fraction of inliers within a preset threshold of the modelRepeat 1-3 until the best model is found with high confidenceLine fitting example42/14INAlgorithm: Sample (randomly) the number of points required to fit the model (#=2) So

13、lve for model parameters using samples Score by the fraction of inliers within a preset threshold of the modelRepeat 1-3 until the best model is found with high confidenceLine fitting example43/sepN11log/1logpeNs111proportion of outliers es5%10%20%25%30%40%50%2235671117334791119354359131734725461217

14、265714664716243797293748203354163588859264478272117744/45/Medical imaging: match brain scans or contoursRobotics: match point clouds46/47/A1A2A3B1B2B3Given matched points in A and B, estimate the translation of the objectyxAiAiBiBittyxyx48/A1A2A3B1B2B3Least squares solutionyxAiAiBiBittyxyx(tx, ty)Wr

15、ite down objective functionDerived solutionCompute derivativeCompute solutionComputational solutionWrite in form Ax=bSolve using pseudo-inverse or eigenvalue decompositionAnBnAnBnABAByxyyxxyyxxtt11111001100149/A1A2A3B1B2B3RANSAC solutionyxAiAiBiBittyxyx(tx, ty)Sample a set of matching points (1 pair

16、)Solve for transformation parametersScore parameters with number of inliersRepeat steps 1-3 N timesProblem: outliersA4A5B5B450/A1A2A3B1B2B3Hough transform solutionyxAiAiBiBittyxyx(tx, ty)Initialize a grid of parameter valuesEach matched pair casts a vote for consistent valuesFind the parameters with the most votesSolve using least squares with inliersA4A5A6B4B5B6Problem: outliers, mult