Collected Notes
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
Content
Lecturenotes
Information Theory
Signal Theory
Logistic Regression
Forward and Backpropagation in a Neural Network
Bayes and MaximumLikelihoodEstimation
Technical Notes
Statistics and Estimation Theory
Estimation of Geometric Entities
Image Analysis
Notes on Geometry
Bundle Adjustment and Surface Reconstruction
On Mathematics
Miscelleaneous Notes
to top
Lecturenotes

Information Theory
[bibtex]
[pdf]
 These lecture notes on Information Theory cover basic concepts of selfinformation 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
[bibtex]
[pdf]
 Signal Theory is the essential tool for understanding linear filters of one or multidimensional 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 multidimensional signals, the sampling theorem and other image transforms. 

Logistic Regression
[bibtex]
[pdf]
 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. 

Forward and Backpropagation in a Neural Network
[bibtex]
[pdf]
 Multilayer 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 Matlabimplementation 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. 

Bayes and MaximumLikelihoodEstimation
[bibtex]
[pdf]
[code]
[cdy]
 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 GaussMarkov model, indicating the close relation between generalized least squares estimation, MLestimation and Bayesian estimation. The relation to the iteration scheme of LevenbergMarquardt are given. 
to top
Technical Notes on Statistics and Estimation Theory

Evaluation of Estimation Results  An Example
[bibtex]
[pdf]
 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. 

GaussHelmert Model as Optimization Problem
[bibtex]
[pdf]
 The GaussHelmert generalizes the wellknown GaussMarkov 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 MaximumLikelihood 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 nonstatistical properties of the intermediate steps before treating point of convergence as final estimate. 

Variance Component Estimation with Observational Groups
[bibtex]
[pdf]
 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 

Precalibration and insitu Selfcalibration with Correlated Observations
[bibtex]
[pdf]
[cdy]
 Deformation analysis based on point clouds taken at different times may require to take into account both precalibration and in situ selfcalibration of the used instruments. We analyse the mutual effect of precalibration and insitu selfcalibration w.r.t. (1) the necessity to exploit the full covariance structure of the point cloud induced by the prealibration and (2) the possibility of increasing the computational efficiency during the selfcalibration. 

The Mean of Correlated Observations
[bibtex]
[pdf]
 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. 

Accuracy of the Mean when using a Wrong Covariance Matrix
[bibtex]
[pdf]
[cdy]
 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. 

Bias of Uncertain Bilinear Forms of Stochastic Quantities
[bibtex]
[pdf]
 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. 

Bounded Quasi Normal Distribution
[bibtex]
[pdf]
 Transforming homogeneous vectors to nonhomogeneous vectors leads to random variables without mean and variance, if the densities are nonzero 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. 

Precision of the Inverse of an Uncertain Matrix
[bibtex]
[pdf]
 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. 

Remarks on the Equivalence of Gauge or Stransformations and Reducing Homogeneous Coordinates
[bibtex]
[pdf]
 Gaugetransformations 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. 

Gauge Choice and Loop Closing of Uncertain Polygons
[bibtex]
[pdf]
[cdy]
 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. 

MarkovRandom Fields and Geodetic Networks
[bibtex]
[pdf]
 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. 
to top
Technical Notes on Estimation of Geometric Entities

Motions and their Uncertainty
[bibtex]
[pdf]
[code]
 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. 

Centroid Form of an Uncertain Plane
[bibtex]
[pdf]
[cdy]
 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. 

Planes from Points
[bibtex]
[pdf]
 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. 

Direct Solutions for the Similarity from Plane Pairs
[bibtex]
[pdf]
 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. 

A Permutation Invariant Test Statistic for the Circularity of Four Points
[bibtex]
[pdf]
 We propose a statistical test for evaluating whether four points are cocircular. 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. 

Uncertain Ellipses
[bibtex]
[pdf]
 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. 

Minimal homography and its uncertainty from point pairs
[bibtex]
[pdf]
[code]
 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. 

Uncertainty of Areas and Volumes
[bibtex]
[pdf]
 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. 
to top
Technical Notes on Image Analysis

Checking of Least Squares Matching Using Image Triplets
[bibtex]
[pdf]
 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. 

Asymmetric and Symmetric Matching with experiments
[bibtex]
[pdf]
 The note addresses template matching and least squares matching of one and twodimensional 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. 

Symmetric Least Squares Matching  SymLSM
[bibtex]
[pdf]
 The note is a report which describes the basics of symmetric least squares matching (SymLSM) which is useful for highprecision image matching and realized in Matlab. 

Essential Matrix from Affine Matches and its Precision
[bibtex]
[pdf]
[code]
 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. 

Surface Slope from Affine Matches
[bibtex]
[pdf]
 We discuss how to derive the local slope of the surface from affine matches for rectified and nonrectified 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. 

Local Affinity of a Homography and its Approximation
[bibtex]
[pdf]
 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 intensitybased 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. 

Noise Suppression with Box, Binomial, and Gaussian Filters
[bibtex]
[pdf]
 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. 
to top
Technical Notes on Geometry

Circles and Circular Segments
[bibtex]
[pdf]
 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 Algebra and Projective Geometry for Representing Relations between Geometric Elements
[bibtex]
[pdf]
[code]
 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. 

Euler Angles and Small Multiplicative Rotation Vector
[bibtex]
[pdf]
 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. 

Visualization of the Projective Space using Stereographic Projection
[bibtex]
[pdf]
 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. 
to top
Technical Notes on Bundle Adjustment and Surface Reconstruction

Rotation from the Essential Matrix for ZeroBasis
[bibtex]
[pdf]
 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. 

Rule of Thumb for Precision of Points from Multiview Triangulation
[bibtex]
[pdf]
 For planning bundle adjustment configurations, the expected accuracy of triangulated points is an essential ingredient. We derive rules of thumb for the accuracy of multiview 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. 

MultiView Triangulation with Directions
[bibtex]
[pdf]
 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. 
to top
Technical Notes on Mathematics

Rational Rotation Matrices
[bibtex]
[pdf]
 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. 

On the Cayley Transform
[bibtex]
[pdf]
 We address the Cayley transform relevant for representing rotations and present an excerpt of his paper (1946) 
to top
Miscellaneous Notes

Necessary Width of a Corridor to Transport a Piano around a Corner
[bibtex]
[pdf]
[cdy]
 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. 

Line from Four Observed Lines Passing through Equidistant Points
[bibtex]
[pdf]
[cdy]
 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. 

Peeling a Mandarin or the Spherical Archimedean Spiral
[bibtex]
[pdf]
 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. 
to top