Statistical Optimization for Geometric Computation Theory and Practice

by Kanatani, Kenichi

• ISBN13: 9780486443089
• ISBN10: 0486443086
• Format: Paperback
• Copyright: 2005-07-26
• Publisher: Dover Publications

Summary

This text discusses the mathematical foundations of statistical inference for building 3-dimensional models from image and sensor data that contain noise a task involving autonomous robots guided by video cameras and sensors. The text employs a theoretical accuracy for the optimization procedure, which maximizes the reliability of estimations based on noise data. 1996 edition.

Table of Contents

1 Introduction	1	(26)
1.1 The Aims of This Book	1	(5)
1.1.1 Statistical optimization for image and sensor data	1	(1)
1.1.2 What are the issues?	2	(2)
1.1.3 Why is a new statistical theory necessary?	4	(2)
1.2 The Features of This Book	6	(3)
1.2.1 Theoretical accuracy bound	6	(1)
1.2.2 Evaluation of reliability and testing of hypotheses	6	(1)
1.2.3 Geometric models as manifolds	7	(1)
1.2.4 Numerical schemes for optimization	8	(1)
1.3 Organization and Background	9	(14)
1.3.1 Fundamentals of linear algebra	9	(1)
1.3.2 Probabilities and statistical estimation	9	(1)
1.3.3 Representation of geometric primitives	10	(2)
1.3.4 Geometric correction	12	(1)
1.3.5 3-D computation by stereo vision	13	(1)
1.3.6 Parametric fitting	14	(1)
1.3.7 Optimal filter and renormalization	14	(1)
1.3.8 Applications of geometric estimation	15	(2)
1.3.9 3-D motion analysis	17	(3)
1.3.10 3-D interpretation of optical flow	20	(2)
1.3.11 Information criterion for model selection	22	(1)
1.3.12 General theory of geometric estimation	22	(1)
1.4 The Analytical Mind: Strength and Weakness	23	(4)
1.4.1 Criticisms of statistical approaches	23	(1)
1.4.2 Gaussian noise assumption and outlier detection	24	(1)
1.4.3 Remaining problems	25	(2)
2 Fundamentals of Linear Algebra	27	(34)
2.1 Vector and Matrix Calculus	27	(10)
2.1.1 Vectors and matrices	27	(2)
2.1.2 Determinant and inverse	29	(2)
2.1.3 Vector product in three dimensions	31	(3)
2.1.4 Projection matrices	34	(1)
2.1.5 Orthogonal matrices and rotations	35	(2)
2.2 Eigenvalue Problem	37	(8)
2.2.1 Spectral decomposition	37	(2)
2.2.2 Generalized inverse	39	(1)
2.2.3 Rayleigh quotient and quadratic form	40	(1)
2.2.4 Nonsingular generalized eigenvalue problem	41	(2)
2.2.5 Singular generalized eigenvalue problem	43	(1)
2.2.6 Perturbation theorem	44	(1)
2.3 Linear Systems and Optimization	45	(9)
2.3.1 Singular value decomposition and generalized inverse	45	(2)
2.3.2 Linear equations	47	(2)
2.3.3 Quadratic optimization	49	(1)
2.3.4 Matrix inner product and matrix norm	50	(3)
2.3.5 Optimal rotation fitting	53	(1)
2.4 Matrix and Tensor Algebra	54	(7)
2.4.1 Direct sum and tensor product	54	(1)
2.4.2 Cast in three dimensions	55	(3)
2.4.3 Linear mapping of matrices in three dimensions	58	(3)
3 Probabilities and Statistical Estimation	61	(34)
3.1 Probability Distributions	61	(4)
3.1.1 Mean, variance, and covariance	61	(2)
3.1.2 Geometry of probability distributions	63	(2)
3.2 Manifolds and Local Distributions	65	(3)
3.2.1 Manifolds and tangent spaces	65	(2)
3.2.2 Local distributions	67	(1)
3.2.3 Covariance matrix of a 3-D rotation	67	(1)
3.3 Gaussian Distributions and Χ² Distributions	68	(8)
3.3.1 Gaussian distributions	68	(4)
3.3.2 Moment generating functions and moments	72	(1)
3.3.3 Χ² distributions	73	(1)
3.3.4 Mahalanobis distance and Χ² test	74	(2)
3.4 Statistical Estimation for Gaussian Models	76	(7)
3.4.1 Maximum likelihood estimation	76	(2)
3.4.2 Optimization with linear constraints	78	(1)
3.4.3 Maximum a posteriori probability estimation	79	(2)
3.4.4 Kalman filter	81	(2)
3.5 General Statistical Estimation	83	(4)
3.5.1 Score and Fisher information matrix	83	(2)
3.5.2 Unbiased estimator and Cramer-Rao lower bound	85	(2)
3.6 Maximum Likelihood Estimation	87	(3)
3.6.1 Maximum likelihood estimator and the exponential family	87	(2)
3.6.2 Asymptotic behavior	89	(1)
3.7 Akaike Information Criterion	90	(5)
3.7.1 Model selection	90	(1)
3.7.2 Asymptotic expression for the expected residual	91	(4)
4 Representation of Geometric Objects	95	(36)
4.1 Image Points and Image Lines	95	(7)
4.1.1 Representation of image points	95	(2)
4.1.2 Representation of image lines	97	(2)
4.1.3 Incidence, intersections, and joins	99	(3)
4.2 Space Points and Space Lines	102	(7)
4.2.1 Representation of space points	102	(1)
4.2.2 Representation of space lines	103	(4)
4.2.3 Incidence, intersections, and joins	107	(2)
4.3 Space Planes	109	(4)
4.3.1 Representation of space planes	109	(1)
4.3.2 Incidence, intersections, and joins	110	(3)
4.4 Conics	113	(5)
4.4.1 Classification of conics	113	(2)
4.4.2 Canonical forms of conics	115	(3)
4.5 Space Conics and Quadrics	118	(6)
4.5.1 Representation in three dimensions	118	(2)
4.5.2 Polarity and conjugate direction	120	(1)
4.5.3 Visualization of covariance matrices	121	(3)
4.6 Coordinate Transformation and Projection	124	(7)
4.6.1 Coordinate transformation	124	(3)
4.6.2 Perspective projection	127	(4)
5 Geometric Correction	131	(40)
5.1 General Theory	131	(13)
5.1.1 Basic formulation	131	(2)
5.1.2 Optimal solution	133	(3)
5.1.3 Practical considerations	136	(2)
5.1.4 A posteriori covariance matrices	138	(3)
5.1.5 Hypothesis testing and noise level estimation	141	(2)
5.1.6 Linear constraint	143	(1)
5.2 Correction of Image Points and Image Lines	144	(6)
5.2.1 Optimal correction for coincidence	144	(3)
5.2.2 Optimal correction for incidence	147	(3)
5.3 Correction of Space Points and Space Lines	150	(6)
5.3.1 Optimal correction for coincidence	150	(3)
5.3.2 Optimal correction for incidence	153	(3)
5.4 Correction of Space Planes	156	(7)
5.4.1 Optimal correction for coincidence	156	(1)
5.4.2 Optimal incidence with space points	157	(3)
5.4.3 Optimal incidence with space lines	160	(3)
5.5 Orthogonality Correction	163	(5)
5.5.1 Correction of two orientations	163	(2)
5.5.2 Correction of three orientations	165	(3)
5.6 Conic Incidence Correction	168	(3)
6 3-D Computation by Stereo Vision	171	(38)
6.1 Epipolar Constraint	171	(4)
6.1.1 Camera imaging geometry	171	(1)
6.1.2 Epipolar equation	172	(2)
6.1.3 Parallel stereo system	174	(1)
6.2 Optimal Correction of Correspondence	175	(4)
6.2.1 Correspondence detection and optimal correction	175	(2)
6.2.2 Correspondence test and noise level estimation	177	(2)
6.3 3-D Reconstruction of Points	179	(7)
6.3.1 Depth reconstruction	179	(2)
6.3.2 Error behavior of reconstructed space points	181	(2)
6.3.3 Mahalanobis distance in the scene	183	(3)
6.4 3-D Reconstruction of Lines	186	(2)
6.4.1 Line reconstruction	186	(1)
6.4.2 Error behavior of reconstructed space lines	187	(1)
6.5 Optimal Back Projection onto a Space Plane	188	(7)
6.5.1 Back projection of a point	188	(5)
6.5.2 Back projection of a line	193	(2)
6.6 Scenes Infinitely Far Away	195	(5)
6.6.1 Space points infinitely far away	195	(3)
6.6.2 Space lines infinitely far away	198	(2)
6.7 Camera Calibration Errors	200	(9)
6.7.1 Errors in base-line	200	(2)
6.7.2 Errors in camera orientation	202	(2)
6.7.3 Errors in focal length	204	(5)
7 Parametric Fitting	209	(38)
7.1 General Theory	209	(11)
7.1.1 Parametric fitting	209	(1)
7.1.2 Maximum likelihood estimation	210	(3)
7.1.3 Covariance matrix of the optimal fit	213	(3)
7.1.4 Hypothesis testing and noise level estimation	216	(3)
7.1.5 Linear hypothesis	219	(1)
7.2 Optimal Fitting for Image Points	220	(6)
7.2.1 Image point fitting	220	(2)
7.2.2 Image line fitting	222	(4)
7.3 Optimal Fitting for Image Lines	226	(4)
7.3.1 Image point fitting	226	(2)
7.3.2 Image line fitting	228	(2)
7.4 Optimal Fitting for Space Points	230	(8)
7.4.1 Space point fitting	230	(1)
7.4.2 Space line fitting	231	(4)
7.4.3 Space plane fitting	235	(3)
7.5 Optimal Fitting for Space Lines	238	(4)
7.5.1 Space point fitting	238	(1)
7.5.2 Space line fitting	239	(2)
7.5.3 Space plane fitting	241	(1)
7.6 Optimal Fitting for Space Planes	242	(5)
7.6.1 Space point fitting	242	(1)
7.6.2 Space line fitting	243	(2)
7.6.3 Space plane fitting	245	(2)
8 Optimal Filter	247	(20)
8.1 General Theory	247	(4)
8.1.1 Bayesian approach	247	(1)
8.1.2 Maximum a posteriori probability estimation	248	(3)
8.2 Iterative Estimation Scheme	251	(5)
8.2.1 Optimal update rule	251	(3)
8.2.2 Bayesian interpretation	254	(2)
8.3 Effective Gradient Approximation	256	(4)
8.4 Reduction from the Kalman Filter	260	(4)
8.5 Estimation from Linear Hypotheses	264	(3)
9 Renormalization	267	(28)
9.1 Eigenvector Fit	267	(6)
9.1.1 Least-squares approximation	267	(2)
9.1.2 Statistical bias of eigenvector fit	269	(4)
9.2 Unbiased Eigenvector Fit	273	(5)
9.2.1 Unbiased least-squares approximation	273	(2)
9.2.2 Analysis of residual	275	(3)
9.3 Generalized Eigenvalue Fit	278	(5)
9.3.1 Noise level estimation	278	(1)
9.3.2 Accuracy of generalized eigenvector fit	279	(2)
9.3.3 Analysis of residual	281	(2)
9.4 Renormalization	283	(3)
9.4.1 Iterations for generalized eigenvalue problem	283	(1)
9.4.2 Iterations for weight update	284	(2)
9.5 Linearization	286	(4)
9.5.1 Linearized algorithm	286	(2)
9.5.2 Decomposability condition	288	(2)
9.6 Second Order Renormalization	290	(5)
9.6.1 Effective value of nonlinear data	290	(2)
9.6.2 Second order unbiased estimation	292	(3)
10 Applications of Geometric Estimation	295	(30)
10.1 Image Line Fitting	295	(5)
10.1.1 Optimal line fitting	295	(1)
10.1.2 Unbiased estimation and renormalization	296	(4)
10.2 Conic Fitting	300	(6)
10.2.1 Optimal conic fitting	300	(2)
10.2.2 Unbiased estimation and renormalization	302	(4)
10.3 Space Plane Fitting by Range Sensing	306	(8)
10.3.1 Optimal space plane fitting	306	(3)
10.3.2 Noise model of range sensing	309	(2)
10.3.3 Unbiased estimation and renormalization	311	(3)
10.4 Space Plane Fitting by Stereo Vision	314	(11)
10.4.1 Optimal space plane fitting	314	(3)
10.4.2 Unbiased estimation and renormalization	317	(8)
11 3-D Motion Analysis	325	(44)
11.1 General Theory	325	(7)
11.1.1 Camera and object motion	325	(2)
11.1.2 Optimal estimation of motion parameters	327	(2)
11.1.3 Theoretical bound on accuracy	329	(3)
11.2 Linearization and Renormalization	332	(4)
11.2.1 Linearization	332	(2)
11.2.2 Unbiased estimation and renormalization	334	(2)
11.3 Optimal Correction and Decomposition	336	(5)
11.3.1 Correction of the essential matrix	336	(2)
11.3.2 Decomposition into motion parameters	338	(3)
11.4 Reliability of 3-D Reconstruction	341	(7)
11.4.1 Depth and its variance	341	(3)
11.4.2 Effect of errors in the motion parameters	344	(4)
11.5 Critical Surfaces	348	(3)
11.5.1 Weak critical surfaces	348	(2)
11.5.2 Strong critical surfaces	350	(1)
11.6 3-D Reconstruction from Planar Surface Motion	351	(13)
11.6.1 Optimal solution and planarity test	351	(3)
11.6.2 Unbiased estimation and renormalization	354	(2)
11.6.3 Computation of surface and motion parameters	356	(8)
11.7 Camera Rotation and Information	364	(5)
11.7.1 Rotation test	364	(3)
11.7.2 Information in motion images	367	(2)
12 3-D Interpretation of Optical Flow	369	(46)
12.1 Optical Flow Detection	369	(5)
12.1.1 Gradient equation	369	(2)
12.1.2 Reliability of optical flow	371	(3)
12.2 Theoretical Basis of 3-D Interpretation	374	(4)
12.2.1 Optical flow equation	374	(2)
12.2.2 Epipolar equation for optical flow	376	(1)
12.2.3 3-D analysis from optical flow	377	(1)
12.3 Optimal Estimation of Motion Parameters	378	(5)
12.3.1 Optimal estimation	378	(2)
12.3.2 Theoretical bound on accuracy	380	(3)
12.4 Linearization and Renormalization	383	(3)
12.4.1 Linearization	383	(1)
12.4.2 Unbiased estimation and renormalization	384	(2)
12.5 Optimal 3-D Reconstruction	386	(8)
12.5.1 Optimal correction and decomposition	386	(3)
12.5.2 Optimal correction of optical flow	389	(3)
12.5.3 Computation of depth	392	(2)
12.6 Reliability of 3-D Reconstruction	394	(6)
12.6.1 Effect of image noise	394	(1)
12.6.2 Effect of errors in the motion parameters	395	(5)
12.7 Critical Surfaces for Optical flow	400	(2)
12.7.1 Weak critical surfaces	400	(1)
12.7.2 Strong critical surfaces	401	(1)
12.8 Analysis of Planar Surface Optical Flow	402	(6)
12.8.1 Optical flow equation for a planar surface	402	(1)
12.8.2 Estimation of the flow matrix	403	(2)
12.8.3 Planarity test	405	(1)
12.8.4 Computation of surface and motion parameters	406	(2)
12.9 Camera Rotation and Information	408	(7)
12.9.1 Rotation estimation	408	(2)
12.9.2 Rotation test	410	(1)
12.9.3 Information in optical flow	411	(1)
12.9.4 Midpoint flow approximation	412	(3)
13 Information Criterion for Model Selection	415	(36)
13.1 Model Selection Criterion	415	(5)
13.1.1 Model estimation	415	(3)
13.1.2 Minimization of expected residual	418	(2)
13.2 Mahalanobis Geometry	420	(3)
13.2.1 Mahalanobis projection	420	(2)
13.2.2 Residual of model fitting	422	(1)
13.3 Expected Residual	423	(5)
13.3.1 Evaluation of the expected residual	423	(2)
13.3.2 Accuracy of parametric fitting	425	(3)
13.4 Geometric Information Criterion	428	(6)
13.4.1 Model selection by AIC	428	(3)
13.4.2 Model comparison by AIC	431	(3)
13.4.3 Model selection vs. testing of hypotheses	434	(1)
13.5 3-D Reconstruction by Stereo Vision	434	(4)
13.5.1 General model	434	(2)
13.5.2 Planar surface model	436	(1)
13.5.3 Infinity model	437	(1)
13.5.4 Model comparison	437	(1)
13.6 3-D Motion Analysis	438	(8)
13.6.1 General model	438	(2)
13.6.2 Planar surface model	440	(1)
13.6.3 Rotation model	441	(1)
13.6.4 Model comparison	442	(4)
13.7 3-D Interpretation of Optical Flow	446	(5)
13.7.1 General model	446	(2)
13.7.2 Planar surface model	448	(1)
13.7.3 Rotation model	449	(1)
13.7.4 Model comparison	450	(1)
14 General Theory of Geometric Estimation	451	(34)
14.1 Statistical Estimation in Engineering	451	(1)
14.2 General Geometric Correction	452	(8)
14.2.1 Definition of the problem	452	(1)
14.2.2 The rank of the constraint	453	(2)
14.2.3 Cramer-Rao lower bound for geometric correction	455	(1)
14.2.4 Proof of the main theorem	456	(4)
14.3 Maximum Likelihood Correction	460	(7)
14.3.1 Maximum likelihood estimator	460	(2)
14.3.2 Geometric correction of the exponential family	462	(1)
14.3.3 Computation of maximum likelihood correction	463	(3)
14.3.4 Locally Gaussian model	466	(1)
14.4 General Parametric Fitting	467	(8)
14.4.1 Definition of the problem	467	(1)
14.4.2 The rank of the hypothesis	468	(2)
14.4.3 Cramer-Rao lower bound for parametric fitting	470	(2)
14.4.4 Proof of the main theorem	472	(3)
14.5 Maximum Likelihood Fit	475	(10)
14.5.1 Maximum likelihood estimator	475	(3)
14.5.2 Fitting of the exponential family	478	(2)
14.5.3 Computation of maximum likelihood fit	480	(5)
References	485	(16)
Index	501