Thesis (M.S.)--Worcester Polytechnic Institute. / Keywords: Embeddings; graph theory; pseudo-triangulations. Includes bibliographical references (leaves 30-31).

Diplomarbeit - Technische Universität Berlin / Title from title screen (viewed on June 17, 2008). Abstract in German and English. Title from document title page. Includes bibliographical references. Available in PDF format via the World Wide Web.

Thesis (Ph.D.)--Memorial University of Newfoundland, 2003. / Restricted until May 2004. Bibliography: leaves 162-176.

Techn. University, Diss., 2000--Berlin.

An autonomous robot able to navigate inside an unknown environment and reconstruct full 3D scene models using monocular video has been a long term goal in the field of Machine Vision. A key component of such a system is the reconstruction of surface models from estimated scene structure. Sparse 3D measurements of real scenes are readily estimated from N-view image sequences using structure-from-motion techniques. In this thesis we present a geometric theory for reconstruction of surface models from sparse 3D data captured from N camera views. Based on this theory we introduce a general N-view algorithm for reconstruction of 3D models of arbitrary scenes from sparse data. Using a hypothesise and verify strategy this algorithm reconstructs a surface model which interpolates the sparse data and is guaranteed to be consistent with the feature visibility in the N-views. To achieve efficient reconstruction independent of the number of views a simplified incremental algorithm is developed which integrates the feature visibility independently for each view. This approach is shown to converge to an approximation of the real scene structure and have a computational cost which is linear in the number of views. Surface hypothesis are generated based on a new incremental planar constrained Delaunay triangulation algorithm. We present a statistical geometric framework to explicitly consider noise inherent in estimates of 3D scene structure from any real vision system. This approach ensures that the reconstruction is reliable in the presence of noise and missing data. Results are presented for reconstruction of both real and synthetic scenes together with an evaluation of the reconstruction performance in the presence of noise.

No description available.

No description available.

No description available.

We explore the problem of transforming plane triangulations using simultaneous diagonal flips. Wagner showed that any n-vertex plane triangulation can be transformed to any other plane triangulation on equal number of vertices using a finite sequence of diagonal flips. Later on it has been established that O(n) individual flips suffice to complete this transformation. Bose et al. showed that the transformation can also be done in 4 × ( 2 / log 54/53 + 2 / log 6/5 ) logn + 2 ≈ 327.1 log n simultaneous flips. This bound is asymptotically tight. We present two algorithms to improve the leading coefficient of this bound for transforming any plane triangulation into any other. The first of the two algorithms lowers this bound down to 4 × ( 2 / log 12/11 + 2 / log 9/7 ) logn + 2 ≈ 85.8 log n. By processing and preprocessing the interior and exterior of the triangulation’s Hamiltonian cycle parallelly in an interlaced fashion, we make further improvement of the algorithm from ≈ 327.1 log n down to 12 / log 6/5 logn + 2 ≈ 45.6 log n.

Creation of accurate and coherent surface models is vital to the effective planning and construction of flood control and hurricane protection projects. Typically, topographic surface models are synthesized from Delaunay triangulations or interpolated raster grids. Although these techniques are adequate in most general situations, they do not effectively address the specific case where topographic data is available only as cross-section and profile centerline data, such as the elevation sampling produced by traditional hydrographic surveys. The hydraulic spline algorithm was developed to generate irregular two-dimensional channel grids from hydrographic cross-sections at any desired resolution. Hydraulic spline output grids can be easily merged with datasets of higher resolution, such as LIDAR data, to build a complete model of channel geometry and overbank topography. In testing, the hydraulic spline algorithm faithfully reproduces elevations of known input cross-section points where they exist, while generating a smooth transition between known cross-sections. The algorithm performs particularly well compared to traditional techniques with respect to aesthetics and accuracy when input data is sparse. These qualities make the hydraulic spline an ideal choice for practical applications where available data may be limited due to historic or budgetary reasons.