Geospatial Algebraic Computations

This chapter presents the concepts of ring theory from a geodetic and geoinformatics perspective. The presentation is such that the mathematical formulations are augmented with examples from the two fields. Ring theory forms the basis upon which polynomial rings operate. As we shall see later, exact solution of algebraic nonlinear systems of equations are pinned to the operations on polynomial rings. In Chap. 3, polynomials will be discussed in detail. In order to understand the concept of polynomial rings, one needs first to be familiar with the basics of ring theory. This chapter is therefore a preparation for the understanding of the polynomial rings presented in Chap. 3. Ring of numbers which is presented in Sect. 2.2 plays a significant role in daily operations. They permit operations addition, subtraction, multiplication and division of numbers. For those engaged in data collection, ring of numbers play the following role;

In geodesy and geoinformatics, most observations are related to unknowns parameters through equations of algebraic (polynomial) type. In cases where the observations are not of polynomial type, as exemplified by the GPS meteorology problem of Chap. 18, they are converted into polynomials. The unknown parameters are then be obtained by solving the resulting polynomial equations. Such solutions are only possible through application of operations addition and multiplication on polynomials which form elements of polynomial rings. This chapter discusses polynomials and the properties that characterize them. Starting from the definitions ofmonomials, basic polynomial aspects that are relevant for daily operations are presented. Amonomial is defined as

This chapter presents you the reader with one of the most powerful computer algebra tools, besides the polynomial resultants (discussed in the next chapter), for solving algebraic nonlinear systems of equations which you may encounter. The basic tools that you will require to develop your own algorithms for solving problems requiring closed form (exact) solutions are presented. This powerful tool is the “Gröbner basis” written in English as Groebner basis.

Besides Groebner basis approach discussed in Chap. 4, the other powerful algebraic tools for solving nonlinear systems of equations are the polynomial resultants approaches. While Groebner basis may require large storage capacity during its computations, polynomial resultants approaches presented herein offers remedy to users who may not be lucky to have computers with large storage capacities. This chapter presents polynomial resultants approaches starting from the resultants of two polynomials, known as the “Sylvester resultants”, to the resultants of more than two polynomials in several variables known as “multipolynomial resultants”. In normal matrix operations in linear algebra, one is often faced with the task of computing determinants. Their applications to least squares approach are well known.

A fundamental task in geodesy is the solving of systems of equations. Many geodetic problems are represented as systems of multivariate polynomials. A common problem in solving such systems is improper initial starting values for iterative methods, leading to the convergence to solutions with no physical meaning, or convergence that requires global method . Although symbolic methods such as Groebner bases or resultants have been shown to be very efficient, i.e., providing solutions for determined systems such as 3-point problem of 3D affine transformation, the symbolic algebra can be very time consuming, even with special Computer Algebra Systems (CAS). This Chapter proposes the Homotopy method that can be implemented easily in high level computer languages like C++ and Fortran, which are faster than the interpreter type CAS by at least two orders of magnitude. Using Mathematica, the power of Homotopy is demonstrated by solving three nonlinear geodetic problems: resection, GPS positioning and affine transformation. The method enlarging the domain of convergence is found to be efficient, less sensitive to rounding errors, and has a lower complexity compared to other local methods like Newton-Raphson.

In geodesy and geoinformatics, field observations are normally collected with the aim of estimating parameters. Very frequently, one has to handle overdetermined systems of nonlinear equations. In such cases, there exist more equations than unknowns, therefore “the solution” of the system can be interpreted only in a certain error metric, i.e., least squares sense.

In Chap. 7, we have seen that overdetermined nonlinear systems are common in geodetic and geoinformatic applications, that is there are frequently more measurements than it is necessary to determine unknown variables, consequently the number of the variables n is less then the number of the equations m. Mathematically, a solution for such systems can exist in a least square sense. There are many techniques to handle such problems, e.g.,:

This chapter presents the minimization approach known as “Procrustes” which falls within the multidimensional scaling techniques discussed in Sect. 9.2.2. Procrustes analysis is the technique of matching one configuration into another in-order to produce a measure of match. In adjustment terms, the partial Procrustes problem is formulated as the least squares problem of transforming a given matrix \(\mathbf{A}\) into another matrix \(\mathbf{B}\) by an orthogonal transformation matrix \(\mathbf{T}\) such that the sum of squares of the residual matrix \(\mathbf{E} = \mathbf{A} -{\boldsymbol BT}\) is minimum.

In some geospatial parametric modeling, the objectives to be minimized are often expressed in different forms, resulting in different parametric values for the estimated parameters at non-zero residuals. Sometimes, these objectives may compete in a Pareto sense, namely a small change in the parameters results in the increase of one objective and a decrease of the other, as is often the case in multiobjective problems. Such is often the case with errors-in-all-variables (EIV) models, e.g., in the geodetic and photogrammetric coordinate transformation problems often solved using total least squares solution (TLS) as opposed to ordinary least squares solution (OLS). In this Chapter, the application of Pareto optimality to solving parameter estimation for linear models with EIV is presented. The method is tested to solve two well known geodetic problems of linear regression and linear conformal coordinate transformation. The results are compared to those from OLS, Reduced Major Axis Regression (TLS solution), and the least geometric mean deviation (GMD) approach. It is shown that the TLS and GMD solutions applied to the EIV models are just special cases of the Pareto optimal solution, since both of them belong to the Pareto-set. The Pareto balanced optimum (PBO) solution as a member of this Pareto optimal solution set has special features, and is numerically equal to the GMD solution.

Symbolic regression (SR) is the process of determining the symbolic function, which describes a data set-effectively developing an analytic model, which summarizes the data and is useful for predicting response behaviors as well as facilitating human insight and understanding. The symbolic regression approach adopted herein is based upon genetic programming wherein a population of functions are allowed to breed and mutate with the genetic propagation into subsequent generations based upon a survival-of-the-fittest criteria. Amazingly, this works and, although computationally intensive, summary solutions may be reasonably discovered using current laptop and desktop computers.

In many fields of geosciences such as robotics [413], computer vision [351], digital photogrammetry [538], surface reconstruction [388], computational geometry [336], digital building modelling [48], forest planning and operational activities [386] to list but a few, it is a fundamental task to extract plane features from three-dimensional (3D) point clouds, – i.e., a vast amount of points reflected from the surface of objects collected – using the cutting edge remote sensing technology of laser scanning, e.g., [450]. Due to the physical limitations of the sensors, occlusions, multiple reflectance, and noise can produce off-surface points, thereby necessitating robust fitting techniques. Robust fitting means an estimation technique, which is able to estimate accurate model parameters not only consisting of small error magnitudes in the data set but occasionally large scale measurement errors (outliers). Outliers definition is not easy. Perhaps considering the problem from a practical point of the view, one can say that data points, whose appearance in the data set causes dramatically change in the result of the estimated parameters can be labeled as outliers. Basically, there are two different methods to handle outliers;

Since the advent of the Global Navigation Satellite System (GNSS), in particular the Global Positioning System (GPS), many fields within geosciences, such as geodesy, geoinformatics, geophysics, hydrology etc., have undergone tremendous changes. GPS satellites have in fact revolutionized operations in these fields and the entire world in ways that its inventors never imagined. The initial goal of GPS satellites was to provide the capability for the US military to position themselves accurately from space. This way, they would be able to know the positions of their submarines without necessarily relying on fixed ground stations that were liable to enemy attack. Slowly, but surely, the civilian community, led by geodesists, began to devise methods of exploiting the potential of this system. The initial focus of research was on the improvement of positioning accuracies since civilians only have access to the so called coarse acquisition or C/A-code of the GPS signal. This code is less precise when compared to the P-code used by the US military and its allies. The other source of error in GPS positioning was the Selective Availability (SA), i.e., intentional degradation of the GPS signal by the US military that would lead to a positioning error of ±100 m. However, in May 2000, the then president of the United States Bill Clinton, officially discontinued this process.

In establishing a proper reference frame of geodetic point positioning, namely by the Global Positioning System (GPS) – the Global Problem Solver – we are in need to establish a proper model for the Topography of the Earth, the Moon, the Sun or planets. By the theory of equilibrium figures, we are informed that an ellipsoid, two-axes or three-axes is an excellent approximation of the Topography. For planets similar to the Earth the biaxial ellipsoid, also called “ellipsoid-of-revolution” is the best approximation.

Throughout history, position determination has been one of the fundamental task undertaken by man on daily basis. Each day, one has to know where one is, and where one is going. To mountaineers, pilots, sailors etc., the knowledge of position is of great importance. The traditional way of locating one’s position has been the use of maps or campus to determine directions. In modern times, the entry into the game by Global Navigation Satellite Systems GNSSthat comprise the Global Positioning System (GPS), Russian based GLONASSand the proposed European’s GALILEOhave revolutionized the art of positioning.

In Chap. 15, ranging method for positioning was presented where distances were measured to known targets. In this chapter, an alternative positioning technique which uses direction measurements as opposed to distances is presented. This positioning approach is known as the resection. Unlike in ranging where measured distances are affected by atmospheric refraction, resection methods have the advantage that the measurements are angles or directions which are not affected by refraction.

The similarity between resection methods presented in the previous chapter and intersection methods discussed herein is their application of angular observations. The distinction between the two however, is that for resection, the unknown station is occupied while for intersection, the unknown station is observed. Resection uses measuring devices (e.g., theodolite, total station, camera etc.) which occupy the unknown station. Angular (direction) observations are then measured to three or more known stations as we saw in the preceding chapter. Intersection approach on the contrary measures angular (direction) observations to the unknown station; with the measuring device occupying each of the three or more known stations. It has the advantage of being able to position an unknown station which can not be physically occupied. Such cases are encountered for instance during engineering constructions or cadastral surveying. During civil engineering construction for example, it may occur that a station can not be occupied because of swampiness or risk of sinking ground. In such a case, intersection approach can be used. The method is also widely applicable in photogrammetry. In aero-triangulation process, simultaneous resection and intersection are carried out where common rays from two or more overlapping photographs intersect at a common ground point (see e.g., Fig. 15.1).

In Chap. 7, we introduced parameter estimation from observational data sample and defined the models applicable to linear and nonlinear cases. In-order for the estimates to be meaningful however.

The 7-parameter datum transformation \(\mathbb{C}_{7}(3)\) problem involves the determination of seven parameters required to transform coordinates from one system to another. The transformation of coordinates is a computational procedure that maps one set of coordinates in a given system onto another