Publications by Klas Nordberg

In this article we describe a set of canonical transformations of the image spaces that make the description of three-view geometry very simple. The transformations depend on the three-view geometry and the canonically transformed trifocal tensor T' takes the form of a sparse array where 17 elements in well-defined positions are zero, it has a linear relation to the camera matrices and to two of the fundamental matrices, a third order relation to the third fundamental matrix, a second order relation to the other two trifocal tensors, and first order relations to the 10 three-view all-point matching constraints. In this canonical form, it is also simple to determine if the corresponding camera configuration is degenerate or co-linear. An important property of the three canonical transformations of the images spaces is that they are in SO(3). The 9 parameters needed to determine these transformations and the 9 parameters that determine the elements of T' together provide a minimal parameterization of the tensor. It does not have problems with multiple maps or multiple solutions that other parameterizations have, and is therefore simple to use. It also provides an implicit representation of the trifocal internal constraints: the sparse canonical representation of the trifocal tensor can be determined if and only if it is consistent with its internal constraints. In the non-ideal case, the canonical transformation can be determined by solving a minimization problem and a simple algorithm for determining the solution is provided. This allows us to extend the standard linear method for estimation of the trifocal tensor to include a constraint enforcement as a final step, similar to the constraint enforcement of the fundamental matrix.

Experimental evaluation of this extended linear estimation method shows that it significantly reduces the geometric error of the resulting tensor, but on average the algebraic estimation method is even better. For a small percentage of cases, however, the extended linear method gives a smaller geometric error, implying that it can be used as a complement to the algebraic method for these cases.

A runtime system for implementation of image processing operations is presented. It is designed for working in a flexible and distributed environment related to the software architecture of a newly developed UAV system. The software architecture can be characterized at a coarse scale as a layered system, with a deliberative layer at the top, a reactive layer in the middle, and a processing layer at the bottom. At a finer scale each of the three levels is decomposed into sets of modules which communicate using CORBA, allowing system development and deployment on the UAV to be made in a highly flexible way. Image processing takes place in a dedicated module located in the process layer, and is the main focus of the paper. This module has been designed as a runtime system for data flow graphs, allowing various processing operations to be created online and on demand by the higher levels of the system. The runtime system is implemented in Java, which allows development and deployment to be made on a wide range of hardware/software configurations. Optimizations for particular hardware platforms have been made using Java's native interface.

Tensors have become a popular tool for representation of local orientation and can be used also for estimation of velocity. A number of computational approaches have been presented for tensor estimation which, however, are difficult to analyze or compare since there has been no common framework in which analysis or comparisons can be made. In this article, we propose such a framework based on second-order filters and show how it applies to three different methods for tensor estimation. The framework contains a few conditions on the filters which are sufficient to obtain correctly oriented rank one tensors for the case of simple signals. It also allows the derivation of explicit expressions for the variation of the tensor across oriented structures which, e.g., can be used to formulate conditions for phase invariance. (c) 2005 Elsevier B.V. All rights reserved.

This Chapter presents a vision-based method for unmanned aerial vehicle (UAV) motion estimation that uses as input an image motion field obtained from matches of point-like features. The Chapter enhances visionbased techniques developed for single UAV localization and demonstrates how they can be modified to deal with the problem of multi-UAV relative position estimation. The proposed approach is built upon the assumption that if different UAVs identify, using their cameras, common objects in a scene, the relative pose displacement between the UAVs can be computed from these correspondences under certain assumptions. However, although point-like features are suitable for local UAV motion estimation, finding matches between images collected using different cameras is a difficult task that may be overcome using blob features. Results justify the proposed approach.

We propose a method for segmenting an arbitrary number of moving objects using the geometry of 6 points in 2D images to infer motion consistency. This geometry allows us to determine whether or not observations of 6 points over several frames are consistent with a rigid 3D motion. The matching between observations of the 6 points and an estimated model of their configuration in 3D space, is quantified in terms of a geometric error derived from distances between the points and 6 corresponding lines in the image. This leads to a simple motion inconsistency score, based on the geometric errors of 6points that in the ideal case should be zero when the motion of the points can be explained by a rigid 3D motion. Initial point clusters are determined in the spatial domain and merged in motion trajectory domain based on this score. Each point is then assigned to the cluster, which gives the lowest score.Our algorithm has been tested with real image sequences from the Hopkins155 database with very good results, competing withthe state of the art methods, particularly for degenerate motion sequences. In contrast to the motion segmentation methods basedon multi-body factorization, that assume an affine camera model, the proposed method allows the mapping from 3D space to the 2D image to be fully projective.

The paper describes a minimal set of 18 parameters that can representany trifocal tensor consistent with the internal constraints.  9parameters describe three orthogonal matrices and 9 parameters describe10 elements of a sparse tensor T' with 17 elements in well-defined positions equal to zero.  Any valid trifocal tensor isthen given as some specific T' transformed by the orthogonalmatrices in the respective image domain.  The paper also describes asimple approach for estimating the three orthogonal matrices in thecase of a general 3 x 3 x 3 tensor, i.e., when the internalconstraints are not satisfied.  This can be used to accomplish a leastsquares approximation of a general tensor to a tensor that satisfies the internal constraints.  This type of constraint enforcement, inturn, can be used to obtain an improved estimate of the trifocal tensorbased on the normalized linear algorithm, with the constraintenforcement as a final step.  This makes the algorithm more similar tothe corresponding algorithm for estimation of the fundamental matrix. An experiment on synthetic data shows that the constraint enforcementof the trifocal tensor produces a significantly better result thanwithout enforcement, expressed by the positions of the epipoles, giventhat the constraint enforcement is made in normalized image coordinates.

Point-of-interest detection is a way of reducing the amount of data that needs to be processed in a certain application and is widely used in 2D image analysis. In 2D image analysis, point-of-interest detection is usually related to extraction of local descriptors for object recognition, classification, registration or pose estimation. In analysis of range data however, some local descriptors have been published in the last decade or so, but most of them do not mention any kind of point-of-interest detection. We here show how to use an extended Harris detector on range data and discuss variants of the Harris measure. All described variants of the Harris detector for 3D should also be usable in medical image analysis, but we focus on the range data case. We do present a performance evaluation of the described variants of the Harris detector on range data.

A novel and computationally simple method is presented for triangulation of 3D points corresponding to the image coordinates in a pair of stereo images. The image points are described in terms of homogeneous coordinates which are jointly represented as the outer products of these homogeneous coordinates. This paper derives a linear transformation which maps the joint representation directly to the homogeneous representation of the corresponding 3D point in the scene. Compared to the other triangulation methods this approach gives similar reconstruction error but is numerically faster, since it only requires linear operations. The proposed method is projective invariant in the same way as the optimal method of Hartley and Sturm. The methods has a "blind plane"; a plane through the camera focal points which cannot be reconstructed by this method. For "forward-looking" camera configurations, however, the blind plane can be placed outside the visible scene and does not constitute a problem.

This paper describes a novel compact representation of local features called the tensor doublet. The representation generates a four dimensional feature vector which is significantly less complex than other approaches, such as Lowe's 128 dimensional feature vector. Despite its low dimensionality, we demonstrate here that the tensor doublet can be used for pose estimation, where the system is trained for an object and evaluated on images with cluttered background and occlusion.

 A novel method for estimating a second order scene tensor is described and results using that method on a synthetic image sequence are shown. It is shown that the tensors can be used to represent basic geometrical entities. A short discussion on what work needs to be done to extend the tensorial description here in to a framework of pose estimation is found at the end of the report.

 This paper presents a novel representation for 3D shapes in terms of planar surface patches and their boundaries. The representation is based on a tensor formalism similar to the usual orientation tensor but extends this concept by using projective spaces and a fourth order tensor, even though the practical computations can be made in normal matrix algebra. This paper also discusses the possibility of estimating the proposed representation from motion field which are generated by a calibrated camera moving in the scene. One method based on 3D spatio-temporal orientation tensors is presented and results from this method are included.

This paper presents and overview of the basic and applied research carried out by the Computer Vision Laboratory, Linköping University, in the WITAS UAV Project. This work includes customizing and redesigning vision methods to fit the particular needs and restrictions imposed by the UAV platform, e.g., for low-level vision, motion estimation, navigation, and tracking. It also includes a new learning structure for association of perception-action activations, and a runtime system for implementation and execution of vision algorithms. The paper contains also a brief introduction to the WITAS UAV Project.

One important problem within the WITAS project is detection of moving objects in aerial images. This paper presents an original method to estimate the displacement between two frames, based on multiscale local polynomial expansions of the images. When the displacement field has been computed, a plane + parallax approach is used to separate moving objects from the camera egomotion.

The WITAS Unmanned Aerial Vehicle Project is a long term basic research project located at Linköping University (LIU), Sweden. The project is multi-disciplinary in nature and involves cooperation with different departments at LIU, and a number of other universities in Europe, the USA, and South America. In addition to academic cooperation, the project involves collaboration with a number of private companies supplying products and expertise related to simulation tools and models, and the hardware and sensory platforms used for actual flight experimentation with the UAV. Currently, the project is in its second phase with an intended duration from 2000-2003.

This paper will begin with a brief overview of the project, but will focus primarily on the computer vision related issues associated with interpreting the operational environment which consists of traffic and road networks and vehicular patterns associated with these networks.

WITAS will be engaged in goal-directed basic research in the area of intelligent autonomous vehicles and other autonomous systems. In this paper an overview of the project is given together with a presentation of our research interests in the project. The current status of our part in the project is also given.

The tensor representation has proven a successful tool as a mean to describe local multi-dimensional orientation. In this respect, the tensor representation is a map from the local orientation to a second order tensor. This paper investigates how variations of the orientation are mapped to variation of the tensor, thereby giving an explicit equivariance relation. The results may be used in order to design tensor based algorithms for extraction of image features defined in terms of local variations of the orientation, \eg multi-dimensional curvature or circular symmetries. It is assumed that the variation of the local orientation can be described in terms of an orthogonal transformation group. Under this assumption a corresponding orthogonal transformation group, acting on the tensor, is constructed. Several correspondences between the two groups are demonstrated.

This thesis presents a signal representation in terms of operators. The signal is assumed to be an element of a vector space and subject to transformations of operators. The operators form continuous groups, so-called Lie groups. The representation can be used for signals in general, in particular if spatial relations are undefinied and it does not require a basis of the signal space to be useful.

Special attention is given to orthogonal operator groups which are generated by anti-Hermitian operators by means of the exponential mapping. It is shown that the eigensystem of the group generator is strongly related to properties of the corresponding operator group. For one-parameter orthogonal operator groups, a phase concept is introduced. This phase can for instance be used to distinguish between spatially even and odd signals and, therefore, corresponds to the usual phase for multi-dimensional signals.

Given one operator group that represents the variation of the signal and one operator group that represents the variation of a corresponding feature descriptor, an equivariant mapping maps the signal to the descriptor such that the two operator groups correspond. Suficient conditions are derived for a general mapping to be equivariant with respect to a pair of operator groups. These conditions are expressed in terms of the generators of the two operator groups. As a special case, second order homo-geneous mappings are considered, and examples of how second order mappings can be used to obtain different types of feature descriptors are presented, in particular for operator groups that are homomorphic to rotations in two and three dimensions, respectively. A generalization of directed quadrature lters is made. All feature extraction algorithms that are presented are discussed in terms of phase invariance.

Simple procedures that estimate group generators which correspond to one-parameter groups are derived and tested on an example. The resulting generator is evaluated by using its eigensystem in implementations of two feature extraction algorithms. It is shown that the resulting feature descriptor has good accuracy with respect to the corresponding feature value, even in the presence of signal noise.

This document is an addendum to the main text in A local geometry-based descriptor for 3D data applied to object pose estimation by Fredrik Viksten and Klas Nordberg. This addendum gives proofs for propositions stated in the main document. This addendum also details how to extract information from the fourth order tensor refered to as S₂₂ in the main document.

This report describes a fourth order tensor defined on projective spaces which can be used for the representation of medium-level features, e.g., one or more oriented segments. The tensor has one part which describes what type of local structures are present in a region, and one part which describes where they are located. This information can be used, e.g., to represent multiple orientations, corners, and line-endings. The tensor can be defined for arbitrary signal dimension, but the presentation focuses on the properties of the fourth order tensor for the case of 2D and 3D image data. A method for estimating the proposed tensor representation by means of simple computations directly from the structure tensor is presented. Given a simple matrix representation of the tensor, it can be shown that there is a direct correspondence between the number of oriented segments and the rank of the matrix provided that the number of segments is three or less. The \publication also presents techniques for extracting information about the oriented segments which the tensor represent. Finally, it shown that a small set of coefficients can be computed from the proposed tensor which are invariant to changes of the coordinate system.

This report defines the rank complement of a diagonalizable matrix (i.e. a matrix which can be brought to a diagonal form by means of a change of basis) as the interchange of the range and the null space. Given a diagonalizable matrix A there is in general no unique matrix Ac which has a range equal to the null space of A and a null space equal to the range of A, only matrices of full rank have a unique rank complement; the zero matrix. Consequently, the rank complement operation is not a distinct operation, but rather a characterization of any operation which makes an interchange of the range and the null space. One particular rank complement operation is introduced here, which eventually leads to an implementation of rank complement operations in terms of polynomials in A. The main result is that for each possible rank r of A there is a polynomial in A which evaluates to a matrix Ac which is a rank complement of A. The report provides explicit expressions for matrix polynomials which compute a rank complement of a symmetric matrix. These results are then generalized to the case of diagonalizable matrices. Finally, a Matlab function is described that implements a rank complement operation based on the results derived.

A robust, fast and general method for estimation of object properties is proposed. It is based on a representation of theses properties in terms of channels. Each channel represents a particular value of a property, resembling the activity of biological neurons. Furthermore, each processing unit, corresponding to an artificial neuron, is a linear perceptron which operates on outer products of input data. This implies a more complex space of invariances than in the case of first order characteristic without abandoning linear theory. In general, the specific function of each processing unit has to to be learned and a fast and simple learning rule is presented. The channel representation, the processing structure and the learning rule has been tested on stereo image data showing a cube with various 3D positions and orientations. The system was able to learn a channel representation for the horizontal position, the depth, and the orientation of the cube, each property invariant to the other two.

The topic of this report is signal representation in the context of hierarchical image processing. An overview of hierarchical processing systems is included as well as a presentation of various approaches to signal representation, feature representation and feature extraction. It is claimed that image hierarchies based on feature extraction, so called feature hierarchies, demand a signal representation other than the standard spatial or linear representation used today. A new representation, the operator representation is developed. It is based on an interpretation of features in terms of signal transformations. This representation has no references to any spatial ordering of the signal element and also gives an explicit representation of signal features. Using the operator representation, a generalization of the standard phase concept in image processing is introduced. Based on the operator representation, two algorithms for extraction of feature values are presented. Both have the capability of generating phase invariant feature descriptors. It is claimed that the operator representation in conjunction with some appropriate feature extraction algorithm is well suited as a general framework for defining multi level feature hierarchies. The report contains an appendical chapter containing the mathematical details necessary to comprehend the presentation.