Jochen Meidow and Christian Beder and Wolfgang Förstner, "Reasoning with uncertain points, straight lines, and straight line segments in 2D", ISPRS Journal of Photogrammetry and Remote Sensing. Vol. 64(2), pp. 125-139. 2009.

• Abstract
• BibTeX
• DOI
• Download

Decisions based on basic geometric entities can only be optimal, if their uncertainty is propagated trough the entire reasoning chain. This concerns the construction of new entities from given ones, the testing of geometric relations between geometric entities, and the parameter estimation of geometric entities based on spatial relations which have been found to hold. Basic feature extraction procedures often provide measures of uncertainty. These uncertainties should be incorporated into the representation of geometric entities permitting statistical testing, eliminates the necessity of specifying non-interpretable thresholds and
enables statistically optimal parameter estimation. Using the calculus of homogeneous coordinates the power of algebraic projective geometry can be exploited in these steps of image analysis. This review collects, discusses and evaluates the various representations of uncertain geometric entities in 2D together with their conversions. The representations are extended to achieve a consistent set of representations allowing geometric reasoning. The statistical testing of geometric relations is presented. Furthermore, a generic estimation procedure is provided for multiple uncertain geometric entities based on possibly correlated observed geometric entities and geometric constraints.

@article{Meidow2009Reasoning,
  author = {Meidow, Jochen and Beder, Christian and F\"orstner, Wolfgang},
  title = {Reasoning with uncertain points, straight lines, and straight line segments in 2D},
  journal = {ISPRS Journal of Photogrammetry and Remote Sensing},
  year = {2009},
  volume = {64},
  number = {2},
  pages = {125--139},
  doi = {10.1016/j.isprsjprs.2008.09.013}
}

Jochen Meidow and Wolfgang Förstner and Christian Beder, "Optimal Parameter Estimation with Homogeneous Entities and Arbitrary Constraints", In Pattern Recognition (Symposium of DAGM). Denzler, J. and Notni, G. (Eds.) Jena, Germany, pp. 292-301. Springer. 2009.

• Abstract
• BibTeX
• DOI
• Download

Well known estimation techniques in computational geometry usually deal only with single geometric entities as unknown parameters and do not account for constrained observations within the estimation. The estimation model proposed in this paper is much more general, as it can handle multiple homogeneous vectors as well as multiple constraints. Furthermore, it allows the consistent handling of arbitrary covariance matrices for the observed and the estimated entities. The major novelty is the proper handling of singular observation covariance matrices made possible by additional constraints within the estimation. These properties are of special interest for instance in the calculus of algebraic projective geometry, where singular covariance matrices arise naturally from the non-minimal parameterizations of the entities. The validity of the proposed adjustment model will be demonstrated by the estimation of a fundamental matrix from synthetic data and compared to heteroscedastic regression [?], which is considered as state-ofthe- art estimator for this task. As the latter is unable to simultaneously estimate multiple entities, we will also demonstrate the usefulness and the feasibility of our approach by the constrained estimation of three vanishing points from observed uncertain image line segments.

@inproceedings{Meidow2009Optimal,
  author = {Meidow, Jochen and F\"orstner, Wolfgang and Beder, Christian},
  editor = {Denzler, J. and Notni, G.},
  title = {Optimal Parameter Estimation with Homogeneous Entities and Arbitrary Constraints},
  booktitle = {Pattern Recognition (Symposium of DAGM)},
  publisher = {Springer},
  year = {2009},
  pages = {292--301},
  doi = {10.1007/978-3-642-03798-6_30}
}

Christian Beder and Richard Steffen, "Incremental estimation without specifying a-priori covariance matrices for the novel parameters", In VLMP Workshop on CVPR. Anchorage, USA 2008.

• Abstract
• BibTeX
• DOI
• Download

We will present a novel incremental algorithm for the task of online least-squares estimation. Our approach aims at combining the accuracy of least-squares estimation and the fast computation of recursive estimation techniques like the Kalman filter. Analyzing the structure of least-squares estimation we devise a novel incremental algorithm, which is able to introduce new unknown parameters and observations into an estimation simultaneously and is equivalent to the optimal overall estimation in case of linear models. It constitutes a direct generalization of the well-known Kalman filter allowing to augment the state vector inside the update step. In contrast to classical recursive estimation techniques no artificial initial covariance for the new unknown parameters is required here. We will show, how this new algorithm allows more flexible parameter estimation schemes especially in the case of scene and motion reconstruction from image sequences. Since optimality is not guaranteed in the non-linear case we will also compare our incremental estimation scheme to the optimal bundle adjustment on a real image sequence. It will be shown that competitive results are achievable using the proposed technique.

@inproceedings{Beder2008Incremental,
  author = {Beder, Christian and Steffen, Richard},
  title = {Incremental estimation without specifying a-priori covariance matrices for the novel parameters},
  booktitle = {VLMP Workshop on CVPR},
  year = {2008},
  doi = {10.1109/CVPRW.2008.4563139}
}

Richard Steffen and Christian Beder, "Recursive Estimation with Implicit Constraints", In Proceedings of the DAGM 2007. F.A. Hamprecht and C. Schnörr and B. Jähne (Eds.) Heidelberg(4713), pp. 194-203. Springer. 2007.

• Abstract
• BibTeX
• DOI
• Download

Recursive estimation or Kalman filtering usually relies on explicit model functions, that directly and explicitly describe the effect of the parameters on the observations. However, many problems in computer vision, including all those resulting in homogeneous equation systems, are easier described using implicit constraints between the observations and the parameters. By implicit we mean, that the constraints are given by equations, that are not easily solvable for the observation vector. We present a framework, that allows to incorporate such implicit constraints as measurement equations into a Kalman filter. The algorithm may be used as a black-box, simplifying the process of specifying suitable measurement equations for many problems. As a byproduct, the possibility of specifying model equations non-explicitly, some non-linearities may be avoided and better results can be achieved for certain problems.

@inproceedings{Steffen2007Recursive,
  author = {Steffen, Richard and Beder, Christian},
  editor = {F.A. Hamprecht and C. Schn\"orr and B. J\"ahne},
  title = {Recursive Estimation with Implicit Constraints},
  booktitle = {Proceedings of the DAGM 2007},
  publisher = {Springer},
  year = {2007},
  number = {4713},
  pages = {194--203},
  doi = {10.1007/978-3-540-74936-3_20}
}

Christian Beder and Richard Steffen, "Determining an initial image pair for fixing the scale of a 3d reconstruction from an image sequence", In Pattern Recognition. K. Franke and K.-R. Müller and B. Nickolay and R. Schäfer (Eds.) Berlin(4174), pp. 657-666. Springer. 2006.

• Abstract
• BibTeX
• DOI
• Download

Algorithms for metric 3d reconstruction of scenes from calibrated image sequences always require an initialization phase for fixing the scale of the reconstruction. Usually this is done by selecting two frames from the sequence and fixing the length of their base-line. In this paper a quality measure, that is based on the uncertainty of the reconstructed scene points, for the selection of such a stable image pair is proposed. Based on this quality measure a fully automatic initialization phase for simultaneous localization and mapping algorithms is derived. The proposed algorithm runs in real-time and some results for synthetic as well as real image sequences are shown.

@inproceedings{Beder2006Determining,
  author = {Beder, Christian and Steffen, Richard},
  editor = {K. Franke and K.-R. M\"uller and B. Nickolay and R. Sch\"afer},
  title = {Determining an initial image pair for fixing the scale of a 3d reconstruction from an image sequence},
  booktitle = {Pattern Recognition},
  publisher = {Springer},
  year = {2006},
  number = {4174},
  pages = {657--666},
  doi = {10.1007/11861898_66}
}

Christian Beder and Wolfgang Förstner, "Direct Solutions for Computing Cylinders from Minimal Sets of 3D Points", In Proceedings of the European Conference on Computer Vision. A. Leonardis and H. Bischof and A. Pinz (Eds.) Graz, Austria(3951), pp. 135-146. Springer. 2006.

• Abstract
• BibTeX
• DOI
• Download

Efficient direct solutions for the determination of a cylinder from points are presented. The solutions range from the well known direct solution of a quadric to the minimal solution of a cylinder with five points. In contrast to the approach of G. Roth and M. D. Levine (1990), who used polynomial bases for representing the geometric entities, we use algebraic constraints on the quadric representing the cylinder. The solutions for six to eight points directly determine all the cylinder parameters in one step: (1) The eight-point-solution, similar to the estimation of the fundamental matrix, requires to solve for the roots of a 3rd-order-polynomial. (2) The seven-point-solution, similar to the sixpoint- solution for the relative orientation by J. Philip (1996), yields a linear equation system. (3) The six-point-solution, similar to the fivepoint- solution for the relative orientation by D. Nister (2003), yields a ten-by-ten eigenvalue problem. The new minimal five-point-solution first determines the direction and then the position and the radius of the cylinder. The search for the zeros of the resulting 6th order polynomials is e ciently realized using 2D-Bernstein polynomials. Also direct solutions for the special cases with the axes of the cylinder parallel to a coordinate plane or axis are given. The method is used to find cylinders in range data of an industrial site.

@inproceedings{Beder2006Direct,
  author = {Beder, Christian and F\"orstner, Wolfgang},
  editor = {A. Leonardis and H. Bischof and A. Pinz},
  title = {Direct Solutions for Computing Cylinders from Minimal Sets of 3D Points},
  booktitle = {Proceedings of the European Conference on Computer Vision},
  publisher = {Springer},
  year = {2006},
  number = {3951},
  pages = {135--146},
  doi = {10.1007/11744023_11}
}

Christian Beder and Wolfgang Förstner, "Direkte Bestimmung von Zylindern aus 3D-Punkten ohne Nutzung von Oberflächennormalen", In Photogrammetrie - Laserscanning - Optische 3D-Messtechnik. Thomas Luhmann and Christina Müller (Eds.) Oldenburg, pp. 206-213. Herbert Wichmann Verlag. 2006.

• Abstract
• BibTeX
• Download

Die automatische Extraktion von Zylindern aus 3D-Punktwolken ist von zentraler Bedeutung bei der Auswertung von Laserscannerdaten insbesondere bei Industrieanlagen. Das robuste Schätzverfahren RANSAC benötigt direkte Lösungen aus so wenig Datenpunkten wie möglich, um effizient zu arbeiten. Wir werden die algebraischen Bedingungen, die quadratische Formen erfüllen müssen, um einen Zylinder darzustellen, analysieren und verschiedene Verfahren für die Lösung dieses Problems vorstellen. Insbesondere werden wir eine minimale Lösung mit nur fünf 3D Punkten präsentieren. Anders als andere Ansätze benötigen wir keine Oberflächennormalen, deren Bestimmung im Allgemeinen schwierig ist.

@inproceedings{Beder2006Direkte,
  author = {Beder, Christian and F\"orstner, Wolfgang},
  editor = {Thomas Luhmann and Christina M\"uller},
  title = {Direkte Bestimmung von Zylindern aus 3D-Punkten ohne Nutzung von Oberfl\"achennormalen},
  booktitle = {Photogrammetrie - Laserscanning - Optische 3D-Messtechnik},
  publisher = {Herbert Wichmann Verlag},
  year = {2006},
  pages = {206--213}
}

Christian Beder, "Gruppierung unsicherer orientierter projektiver geometrischer Elemente mit Anwendung in der automatischen Gebäuderekonstruktion". Thesis at: Institute of Photogrammetry, University of Bonn. 2006.

• Abstract
• BibTeX

Summary
The fully automatic reconstruction of 3d scenes from a set of 2d images has always been a key issue in photogrammetry and computer vision and has not been solved satisfactory so far. Most of the current approaches match features between the images based on radiometric cues followed by a reconstruction using the image geometry. The motivation for this work is the conjecture that in the presence of highly redundant data it should be possible to recover the scene structure by grouping together geometric primitives in a bottom-up manner. Oriented projective geometry will be used throughout this work, which allows to represent geometric primitives, such as points, lines and planes in 2d and 3d space as well as projective cameras, together with their uncertainty. The first major contribution of the work is the use of uncertain oriented projective geometry, rather than uncertain projective geometry, that enables the representation of more complex compound entities, such as line segments and polygons in 2d and 3d space as well as 2d edgels and 3d facets. Within the uncertain oriented projective framework a procedure is developed, which allows to test pairwise relations between the various uncertain oriented projective entities. Again, the novelty lies in the possibility to check relations between the novel compound entities. The second major contribution of the work is the development of a data structure, specifically designed to enable performing the tests between large numbers of entities in an efficient manner. Being able to efficiently test relations between the geometric entities, a framework for grouping those entities together is developed. Various different grouping methods are discussed. The third major contribution of this work is the development of a novel grouping method that by analyzing the entropy change incurred by incrementally adding observations into an estimation is able to balance efficiency against robustness in order to achieve better grouping results. Finally the applicability of the proposed representations, tests and grouping methods for the task of purely geometry based building reconstruction from oriented aerial images is demonstrated. It will be shown that in the presence of highly redundant datasets it is possible to achieve reasonable reconstruction results by grouping together geometric primitives.
Zusammenfassung
Die vollautomatische Rekonstruktion von 3D Szenen aus einer Menge von 2D Bildern war immer ein Hauptanliegen in der Photogrammetrie und Computer Vision und wurde bisher noch nicht zufriedenstellend gelöst. Die meisten aktuellen Ansätze ordnen Merkmale zwischen den Bildern basierend auf radiometrischen Eigenschaften zu. Daran schließt sich dann eine Rekonstruktion auf der Basis der Bildgeometrie an. Die Motivation für diese Arbeit ist die These, dass es möglich sein sollte, die Struktur einer Szene durch Gruppierung geometrischer Primitive zu rekonstruieren, falls die Eingabedaten genügend redundant sind. Orientierte projektive Geometrie wird in dieser Arbeit zur Repräsentation geometrischer Primitive, wie Punkten, Linien und Ebenen in 2D und 3D sowie projektiver Kameras, zusammen mit ihrer Unsicherheit verwendet. Der erste Hauptbeitrag dieser Arbeit ist die Verwendung unsicherer orientierter projektiver Geometrie, anstatt von unsicherer projektiver Geometrie, welche die Repräsentation von komplexeren zusammengesetzten Objekten, wie Liniensegmenten und Polygonen in 2D und 3D sowie 2D Edgels und 3D Facetten, ermöglicht. Innerhalb dieser unsicheren orientierten projektiven Repräsentation wird ein Verfahren zum testen paarweiser Relationen zwischen den verschiedenen unsicheren orientierten projektiven geometrischen Elementen entwickelt. Dabei liegt die Neuheit wieder in der Möglichkeit, Relationen zwischen den neuen zusammengesetzten Elementen zu prüfen. Der zweite Hauptbeitrag dieser Arbeit ist die Entwicklung einer Datenstruktur, welche speziell auf die effiziente Prüfung von solchen Relationen zwischen vielen Elementen ausgelegt ist. Die Möglichkeit zur effizienten Prüfung von Relationen zwischen den geometrischen Elementen erlaubt nun die Entwicklung eines Systems zur Gruppierung dieser Elemente. Verschiedene Gruppierungsmethoden werden vorgestellt. Der dritte Hauptbeitrag dieser Arbeit ist die Entwicklung einer neuen Gruppierungsmethode, die durch die Analyse der Änderung der Entropie beim Hinzufügen von Beobachtungen in die Schätzung Effizienz und Robustheit gegeneinander ausbalanciert und dadurch bessere Gruppierungsergebnisse erzielt. Zum Schluss wird die Anwendbarkeit der vorgeschlagenen Repräsentationen, Tests und Gruppierungsmethoden für die ausschließlich geometriebasierte Gebäuderekonstruktion aus orientierten Luftbildern demonstriert. Es wird gezeigt, dass unter der Annahme von hoch redundanten Datensätzen vernünftige Rekonstruktionsergebnisse durch Gruppierung von geometrischen Primitiven erzielbar sind.

@phdthesis{Beder2006Gruppierung,
  author = {Beder, Christian},
  title = {Gruppierung unsicherer orientierter projektiver geometrischer Elemente mit Anwendung in der automatischen Geb\"auderekonstruktion},
  school = {Institute of Photogrammetry, University of Bonn},
  year = {2006},
  note = {Schriftenreihe des Instituts f\"ur Geod\"asie und Geoinformation}
}

Christian Beder, "Agglomerative Grouping of Observations by Bounding Entropy Variation", In Pattern Recognition. Kropatsch, Walter and Sablatnig, Robert and Hanbury, Allan (Eds.) Vienna, Austria(3663), pp. 101-108. Springer. 2005.

• Abstract
• BibTeX
• DOI
• Download

An information theoretic framework for grouping observations is proposed. The entropy change incurred by new observations is analyzed using the Kalman filter update equations. It is found, that the entropy variation is caused by a positive similarity term and a negative proximity term. Bounding the similarity term in the spirit of the minimum description length principle and the proximity term in the spirit of maximum entropy inference a robust and efficient grouping procedure is devised. Some of its properties are demonstrated for the exemplary task of edgel grouping.

@inproceedings{Beder2005Agglomerative,
  author = {Beder, Christian},
  editor = {Kropatsch, Walter and Sablatnig, Robert and Hanbury, Allan},
  title = {Agglomerative Grouping of Observations by Bounding Entropy Variation},
  booktitle = {Pattern Recognition},
  publisher = {Springer},
  year = {2005},
  number = {3663},
  pages = {101-108},
  doi = {10.1007/11550518_13}
}

Christian Beder, "Fast Statistically Geometric Reasoning About Uncertain Line Segments in 2D- and 3D-Space", In Proceedings of the DAGM Symposium. C.E.Rasmussen and H.H.Bülthoff and B.Schölkopf and M.A.Giese (Eds.) Tübingen(3175), pp. 375-382. Springer. 2004.

• Abstract
• BibTeX
• Download

This work addresses the two major drawbacks of current statistical uncertain geometric reasoning approaches. In the first part a framework is presented, that allows to represent uncertain line segments in 2D- and 3D-space and perform statistical test with these practically very important types of entities. The second part addresses the issue of performance of geometric reasoning. A data structure is introduced, that allows the efficient processing of large amounts of statistical tests involving geometric entities. The running times of this approach are finally evaluated experimentally.

@inproceedings{Beder2004Fast,
  author = {Beder, Christian},
  editor = {C.E.Rasmussen and H.H.B\"ulthoff and B.Sch\"olkopf and M.A.Giese},
  title = {Fast Statistically Geometric Reasoning About Uncertain Line Segments in 2D- and 3D-Space},
  booktitle = {Proceedings of the DAGM Symposium},
  publisher = {Springer},
  year = {2004},
  number = {3175},
  pages = {375--382}
}

Christian Beder, "A Unified Framework for the Automatic Matching of Points and Lines in Multiple Oriented Images", In Proc. 20th ISPRS Congress. Istanbul, Turkey, pp. 1109-1113. 2004.

• Abstract
• BibTeX
• Download

The accurate reconstruction of the three-dimensional structure from multiple images is still a challenging problem, so that most current approaches are based on semi-automatic procedures. Therefore the introduction of accurate and reliable automation for this classical problem is one of the key goals of photogrammetric research. This work deals with the problem of matching points and lines across multiple views, in order to gain a highly accurate reconstruction of the depicted object in three-dimensional space. In order to achieve this goal, a novel framework is introduced, that draws a sharp boundary between feature extraction, feature matching based on geometric constraints and feature matching based on radiometric constraints. The isolation of this three parts allows direct control and therefore better understanding of the different kinds of influences on the results. Most image feature matching approaches heavily depend on the radiometric properties of the features and only incorporate geometry information to improve performance and stability. The extracted radiometric descriptors of the features often assume a local planar or smooth object, which is by definition neither present at object corners nor edges. Therefore it would be desirable to use only descriptors that are rigorously founded for the given object model. Unfortunately the task of feature matching based on radiometric properties becomes extremely difficult for this much weaker descriptors. Hence a key feature of the presented framework is the consistent and rigorous use of statistical properties of the extracted geometric entities in the matching process, allowing a unified algorithm for matching points and lines in multiple views using solely the geometric properties of the extracted features. The results are stabilized by the use of many images to compensate for the lack of radiometric information. Radiometric descriptors may be consistently included into the framework for stabilization as well. Results from the application of the presented framework to the task of fully automatic reconstruction of points and lines from multiple images are shown.

@inproceedings{Beder2004Unified,
  author = {Beder, Christian},
  title = {A Unified Framework for the Automatic Matching of Points and Lines in Multiple Oriented Images},
  booktitle = {Proc. 20th ISPRS Congress},
  year = {2004},
  pages = {1109--1113}
}

Christian Beder, "An Optimisation Method for Obtaining the Fundamental Matrix from an Image Pair". Thesis at: Institute of Photogrammetry, University of Bonn
In Zusammenarbeit mit dem Institut für Informatik der Universität Bonn. 2002.

• Abstract
• BibTeX

Die Bestimmung der relativen Lage zweier Kameras zum Zeitpunkt der Aufnahmen, die sog. relative Orientierung der Bilder, stellt ein klassisches Problem der Photogrammetrie dar und ist Grundlage jeder Auswertung von Stereobildpaaren. Eine vollautomatische allgemeine Lösung dieses Problems existiert bisher nicht. Grund ist die Schwierigkeit, homologe Bilddetails, die sich auf denselben Objektpunkt beziehen, automatisch und unter beliebigen unbekannten Perspektiven zu finden. Sobald homologe Punkte vorliegen, existieren klassische Verfahren zur Bestimmung der sog. Fundamentalmatrix, die die gesamte Information der relativen Orientierung zweier geradentreu abbildender Kameras enthält. Die Fundamentalmatrix ermöglicht insbesondere die Formulierung eines geometrischen Kriteriums für Punkte, die sog. Koplanaritätsbedingung. Als zweites Kriterium für die Homologie von Punkten verwendet man ein radiometrisches Kriterium, meist die Ähnlichkeit der Intensitäts- oder Farbverteilung in der Umgebung der Punkte. Sie ist jedoch nur unter eingeschränkten Bedingungen leicht zu bestimmen, nicht etwa bei partiellen Verdeckungen. Ziel der Arbeit ist nun die Bestimmung der Fundamentalmatrix als Optimierungsverfahren zu formulieren, das gelichzeitig die geometrischen und die radiometrischen Bedingungen berücksichtigt. Intensitätsunterschiede und Abweichungen von der Koplanaritätsbedingung werden durch die Formulierung von normierten chi-quadrat-verteilten Distanzmaßen integriert. Dabei werden die Umgebungen homologer Punkte maßstabs- und rotationsinvariant verglichen. Die Zuordnung wird mit einem Annealingverfahren bestimmt. Die Leistungsfähigkeit und die Grenzen des Verfahrens wird an hand eines künstlichen Beispiels, für das die wahren Werte der Fundamentalmatrix bekannt sind, demonstriert.

@mastersthesis{Beder2002Optimisation,
  author = {Beder, Christian},
  title = {An Optimisation Method for Obtaining the Fundamental Matrix from an Image Pair},
  school = {Institute of Photogrammetry, University of Bonn
In Zusammenarbeit mit dem Institut f\"ur Informatik der Universit\"at Bonn},
  year = {2002},
  note = {Betreuung: Prof. Dr. Joachim Buhmann, Prof. Dr.-Ing. Wolfgang F\"orstner}
}