Wolfgang Förstner
Bonn, 2024
"Unlike the novel, a short story may be, for all purposes, essential."
Jorge Luis Borges
This is a collection of notes I wrote for preparing lectures, for publications or for communicating with collegues on interesting topics. They partially go back more than two decades. May be it is useful to make them public, though the relevance of each individual note, of cource, has to be evaluated by the reader. The complete text is in this pdf. The individual notes are linked to the corresponding pages of this pdf. Some of the notes refer to code. The Cinderella animations are a subset of a larger collection.
Preamble ![]() | These lecture notes on Information Theory cover basic concepts of self-information and entropy for characterizing the coding of probabilistic models and measures for comparing theoretical or empirical densities, both for discrete and continuous random variables. We address the principle of maximum entropy for choosing densities under uncertainty and relate the task of model selection to robust estimation. |
![]() | Signal Theory is the essential tool for understanding linear filters of one- or multi-dimensional signals. These lecture notes use the relation of cyclical matrices and their eigenvalue decomposition as basis for explaining the Fourier transformation. The lectures cover correlation and convolution, the Fourier transformation for discrete and continuous, and cyclical and infinite one- and multi-dimensional signals, the sampling theorem and other image transforms. |
![]() | Logistic Regression is a basic tool for classification. The first part of the note, taken from a lecture, provides the basics for two class classification, generalizes to multiple classes and nonlinear decision boundaries, and provides some examples. The second part, more of conceptual nature, had been an internal basis for the lecture, highlights the structure of the decision boundaries, and focusses on the structure of the Hessian matrix and its rank. |
![]() | Multi-layer Neural Networks and Convolutional neural networks play an important role in interpreting signals. We derive the basic relations for fully connected neural networks, especially the Jacobians for the backward propagation used for learning. Examples based on a simple Matlab-implementation demonstrate the usefulness for elementary classification tasks. The corresponding relations for convolutionally connected layers, which usually are defined by valid correlations, show a remarkably simple relation to those of fully connected layers. |
![]() | The principle of Bayesian estimation and Maximum likelihood estimates is explained and illustrated for the simple example of observing an unknown entity for the cases with and without outliers. It is generalized to the linear Gauss-Markov model, indicating the close relation between generalized least squares estimation, ML-estimation and Bayesian estimation. The relation to the iteration scheme of Levenberg-Marquardt are given. |
![]() | We give three examples for parameter estimation and evaluation. We provide the specific models and equations for the examples. The discussion includes general hints how to use the evaluation methods in other applications and how to report evaluation results in publications. The note served as an appendix to Chapt. 4 of Förstner/Wrobel (2016), GC 11, Springer. |
![]() | The Gauss--Helmert generalizes the well-known Gauss--Markov model by allowing implicit relations between the observations and the unknown parameters. The classical derivation of the estimation procedure refers to the statistical nature of the Maximum-Likelihood optimization. The note separates the description of the model and the optimization function from the generally iterative numerical optimization procedure, in order to elucidate the non-statistical properties of the intermediate steps before treating point of convergence as final estimate. |
![]() | Variance component estimation aims at statistically optimal finding factors for correcting additive components of the covariance matrices of observations. This note provides an efficient way to estimate these factors if the observations can be partitioned into mutually uncorrelated groups, which however show correlations within the groups. This is essential for handling coordinates, e.g. of image or GPS coordinates |
![]() | Deformation analysis based on point clouds taken at different times may require to take into account both pre-calibration and in situ self-calibration of the used instruments. We analyse the mutual effect of pre-calibration and in-situ self-calibration w.r.t. (1) the necessity to exploit the full covariance structure of the point cloud induced by the pre-alibration and (2) the possibility of increasing the computational efficiency during the self-calibration. |
![]() | For uncorrelated observations the accuracy of the mean increases with the number of observations. In case they are correlated, there is an upper limit for the accuracy. The note analyses the situation for constant correlation and for exponentially decaying correlation, autoregressive noise. |
![]() | Suboptimal, i.e., approximate solutions often are used or needed when estimating parameters. One of such simplifications refers to the stochastical model, especially the covariance matrix of the observations, which often is assumed to be a multiple of a unit matrix, implicitly assuming all observations have the same weight and are mutually uncorrelated. This note provides the general relation between the accuracy of the estimated parameters when using an approximate covariance matrix and exemplifies this using the mean of repeated observations. |
![]() | Bilinear forms of stochastic quantities lead to a bias caused by the nonlinear relation. The bias is analysed assuming a Gaussian distribution for the given variables. |
![]() | Transforming homogeneous vectors to non-homogeneous vectors leads to random variables without mean and variance, if the densities are non-zero on infinite support, e.g. when handling Gaussian random variables. Two remedies are proposed: (1) to limit the support of the given random variables, which corresponds to rejection of outliers, and (2) using first order approximations while avoiding critical configurations. |
![]() | We derive the covariance matrix of the inverse of a matrix of random variables, whose covariance matrix is given, assuming the given covariance matrix is regular. The covariance matrix of the given matrix may be singular, allowing to handle transformation matrices with a low degree of freedom. |
![]() | Gauge-transformations change the reference coordinate of the covariance matrix of the coordinates of a point cloud, leave the relative uncertainty of the points invariant, and result in a regular covariance matrix. Similarly, reducing uncertain homogeneous entities with a possibly regular covariance matrix to a tangent space, specified by some constraint, leads to what can be called reduced coordinates. These reduced coordinates have a regular covariance matrix and capture the full information of the uncertainty of the original homogeneous coordinates. We show that both concepts are equivalent. |
![]() | We present a Cincerella animation for exploring the effect of choosing a specific gauge/datum and of loop closing onto an uncertain polygon. The note provides the necessary derivations consistently using complex numbers for representing 2D points and observed distance ratios and angles. |
![]() | Geodetic networks are specific Markov random fields. This is shown by relating the usually sparse graph of observations to the information matrix, the normal equation matrix, which encodes the conditional independencies of the parameters, namely the coordinates. |
![]() | We address the ambiguity of representing uncertain motions. We analyse the relation between an exponential representation with a homogeneous 4x4 matrix and the representation with a rotation matrix, also represented exponentially, and a translation vector. The rotation parts turns out to be identical, while the translation parts differ, why a transparent documentation of the motion representation is necessary. As a sideline, the note addresses the inversion, the concatenation, and the difference between uncertain rotations and uncertain motions. |
![]() | A plane can be represented in various manners. We especially discuss the centroid form of an uncertain plane, which naturally results from estimating a plane from a given point set. We discuss the representation, its recursive estimation assuming isotropic point uncertainty and optimal estimation. |
![]() | We describe the statistically optimal estimation of a single and of multiple planes from a point cloud, where the full covariance matrix of all scene coordinates is available, e.g., from bundle adjustment. This procedure might be used to derive ground truth data for plane extraction or for homography estimation. |
![]() | We collect some direct solutions for determining the similarity (or motion) from corresponding plane pairs, representing point clouds. Some of the solutions are able to handle the case, where the sign of the normals are not consistent. |
![]() | We propose a statistical test for evaluating whether four points are co-circular. The test is invariant to the numbering of the points. It can be used to decide, whether an edge in a Delaunay triangulation is certain or uncertain. |
![]() | We discuss various representations for uncertain ellipses, since they regularly occur as perspective images of 3D circles. We treat them as special conics, and provide some of their relations. Especially we propose two minimal representations for ellipses. |
![]() | The note provides an example for the uncertainty of minimal solutions, namely the determination of a homography from four corresponding points. It provides the covariance matrix of the resulting homography for both cases, where only one set of coordinates is uncertain and where both sets of coordinates are uncertain. An algorithm including the conditioning of the points is given. |
![]() | We give an explicit expression for the standard deviation of the area of a polygonal region determined by n points of homogeneous uncertainty. For regularly spaced points it essentially depends on the length of the circumference of the polygon.The result is generalized to the standard deviation of volumes of spatial regions, which essentially depend on the surface of the region. |
![]() | We discuss how to statistically check the accuracy of least squares matching, which estimates affine geometric and radiometric transformations of image pairs, using the circular closure of the three transformations in an image triplet. |
![]() | The note addresses template matching and least squares matching of one- and two-dimensional signals useful for high precision image matching. We derive the method for linear geometric and radiometric transformations and for an asymmetric and a symmetric setup. The goal is to arrive at methods which provide reliable results not only for the estimated transformation parameters, but also for their covariance matrix and the estimated variance factor. This requires to also take the effects of interpolation and smoothing into account. We provide preliminary experimental results. |
![]() | The note is a report which describes the basics of symmetric least squares matching (Sym-LSM) which is useful for high-precision image matching and realized in Matlab. |
![]() | Estimating the relative pose of two images, for which the intrinsic camera parameters are known, can be based on affine matches. They contain 6 parameters and 3 of them are needed to estimate the essential matrix. We investigate the uncertainty of the essential matrix based on affine matches. |
![]() | We discuss how to derive the local slope of the surface from affine matches for rectified and non-rectified images. The methods are rigorous, in case the surface is locally planar and the perspective distortions are small, which usually is an acceptable assumption, except at depth or slow discontinuities. |
![]() | Image matching may be based on affine matches. The estimated affinity depends on local windows with a size depending on the scale {e.g., }of a keypoint detector. In case of locally planar scenes they approximate the Jacobian of a homography. On the other hand, the scale and rotation parameters provided by a keypoint detector, do not encode the local shears, but may be used as approximation for the local affinity, possibly refined by some intensity-based matching. We discuss the Jacobian of a homography, provide methods to determine the scaled rotation part of the affinity, and a criterion to identify the lack of shears. This enables to empirically determine the accuracy of the scale and rotation parameters derived from Lowe keypoints. |
![]() | We derive expressions for the scale dependent decrease of the variance of white noise images when being smoothed with a box, with a Binomial, with a Gaussian filter, and partial derivatives of a Gaussian filter of up to second order. |
![]() | We collect representations for circles and circle segments and their estimation from given points. Circle segments may be useful for geometric reasoning, especially if the angular support is small, since then the covariance matrix of the circle segment parameters have a much lower condition number than the covariance matrix of the corresponding circle. |
![]() | Geometric relations and constructions of projective elements usually are represented with homogeneous vectors and matrices. We analyse these relations and constructions using Geometric or Clifford algebra. It confirms all representations for relating homogeneous representations of 3D points, planes and 3D lines, especially the sign choices. |
![]() | We provide the Jacobian for two representations of uncertain 3D rotations: the Euler angles and the multiplicative representation of an uncertain rotation. The Jacobian is singular, in case the second rotation angle is 90 degrees, which in the chosen Euler representation corresponds to the Gimbal lock. |
![]() | We show a mapping of the complete projective space into the Euclidean space of the same dimension, exploiting the stereographic projection which guarantees that straight lines of the projective space map to circles in the Euclidean space. |
![]() | We show, that the determination of the rotation and translation from an estimated the essential matrix for an image pair yields the correct rotation matrix in case the basis is 0. |
![]() | For planning bundle adjustment configurations, the expected accuracy of triangulated points is an essential ingredient. We derive rules of thumb for the accuracy of multi-view triangulating by providing simple expressions for the depth and lateral accuracy of 3D points, for images arranged in a line, in a planar region and in a spherical region, covering the case of omnidirectional cameras. |
![]() | We provide simple solution to the optimal triangulation of a scene point from multiple views assuming isotropic uncertainty of the directions. As a special case we provide a simple expression for the distance of the triangulated point in case of homogeneous directional uncertainty and small basis, expressed as a function of the effective base line, the viewing angle and the resolution of an omnidirectional camera and the matching accuracy in pixels. |
![]() | When providing exercises with rotation matrices we may want the elements only contain rational numbers. This can be achieved by using a generalized version of Pythagoras' theorem for quintuples and apply it to the generation of integer quaternions. |
![]() | We address the Cayley transform relevant for representing rotations and present an excerpt of his paper (1946) |
![]() | We analyse under which conditions a piano can be moved around a corner connecting two mutually orthogonal corridors having different widths. In case the corridors have a width between the two sides of the piano, the second corridor needs to be wider if the first corridor is narrower. |
![]() | We provide a constructive solution to the following pose estimation problem: A car is driving on an unknown straight path with an unknown, but constant velocity. It is observed from another moving vehicle which knows it's own position (full pose: position and direction) and observes the bearing (direction) to the other car at constant time intervals. The task is to determine the location of the path and velocity of the other car. A geometric solution by Kuikueg is realized in Cinderella. |
![]() | We discuss the question which form a planarized mandarin peel has, in case it is peeled with a constant width, thus along a spherical Archimedean spiral. We formalize the problem and develop a scheme to visualize a planarized Archimedean spiral. |