We demonstrate a symbolic elimination technique to solve a nine-parameter 3D affine transformation when only three known points in both systems are given. The system of nine equations is reduced to six by subtracting the equations and eliminating the translation parameters. From these six equations, five variables are eliminated using a Gröbner basis to get a quadratic univariate polynomial, from which the solution can be expressed symbolically. The main advantage of this result is that we do not need to guess initial values of the nine parameters, which is necessary in the case of the traditional solution of the nonlinear system of equations. This result can be useful in geodesy, robotics, and photogrammetry when occasionally only three known points in both systems are given or when a Gauss-Jacobi combinatorial solution may be required for certain reasons, for example detecting outliers by using variance-covariance matrices.

Introduction

Three-dimensional data transformations play a central role in contemporary Euclidean point positioning. In precise positioning with a global positioning system (GPS), coordinates given in the World Geodetic System 1984 (WGS84) often have to be transformed into a local geodetic coordinate system. The transformation between the traditional terrestrial coordinate system and the derived network of satellite observations is a difficult task due to the heterogeneity of the data.

Due to the distortions between the traditional terrestrial and the GPS-derived networks, the seven-parameter similarity transformations may not offer satisfactory precision in some cases. To reduce the remaining residuals after the transformation, other transformation models with more parameters can be used. The nine-parameter affine transformation is not only a logical extension but even a generalization of the seven-parameter similarity transformation model; when the three scale parameters are equal, we get the similarity transformation model. This transformation modifies the Helmert transformation, where three different scales are used in the corresponding coordinate axes instead of only one scale factor. Späth [1] estimated the model parameters by using a numerical minimization technique of the residual vector and Papp [2] used a linearized least-squares method. Watson [3] pointed out that the Gauss-Newton method or its variants can be easily implemented for the nine-parameter problem using separation of variables and iteration with respect to the rotation parameters alone, while other parameters can be calculated via a simple linear least-squares solution. The method he suggested is analogous to other methods for separated least-squares problems, which go back at least to Golub and Pereyra [4]. The nine-parameter affine transformation is also included in some coordinate-transformation software developed at the request of GPS users (e.g., see Mathes [5] and Fröhlich and Bröker [6]). Here we should mention transformation models with more than nine parameters. Wolfrum [7] even added one more parameter to the previous nine, a (horizontal) direction of maximal scale distortion. Grafarend and Kampmann [8] applied a ten-parameter conformal group for geodetic data transformation employing maximum likelihood estimations for numerical estimation of the parameter values. There are other models with even more parameters, like polynomial transformations (Volgyesi et al [9], Cai and Grafarend [10]) and models using artificial neural networks (Barsi [11], Zaletnyik [12]).

Definition of the Problem

A 3D affine transformation is one possible generalization of the Helmert transformation, using three different scale parameters , , instead of a single one. In this case the scale factors can be modeled by a diagonal matrix ,

(1)

where

(2)

, , are the three translation parameters, and is the rotation matrix expressed in terms of the skew-symmetric matrix (see Awange and Grafarend [13]),

(3)

The rotation matrix is

(4)

where is the 3×3 identity matrix.

Let and .

To determine the nine parameters of the transformation (, , , , , , , , ) we need three noncollinear points with known coordinates in both coordinate systems. Instead of the scale parameters , , , we use , , to get simpler equations.

The following commands define the matrices in Mathematica.

Expressing the rotation matrix with the skew-symmetric matrix and using the inverse of the scale matrix , this is the nonlinear system.

Elimination of the Translation Parameters

Solutions of the nonlinear system of equations in geodesy have received wide coverage, as evidenced in the works of Bancroft [14], Grafarend and Schaffrin [15], Singer et al. [16], Kleusberg [17, 18], Lichtenegger [19], and Awange [20]. Similarly to the problem (see Awange and Grafarend [21]), we can reduce the system by subtracting the equations, eliminating the translation parameters.

Introduction of Relative Coordinates

Employing a Gröbner basis, the reduced equation system can easily be reduced further if we introduce some new variables. Let us call these relative coordinates.

It is clear that introducing the following variables can simplify the description of the system.

This is the new system.

We verify the equivalence.

Symbolic Solution for the Scale Parameters (, , )

Our intention is to reduce the computation time of the three-point solution because (eg., in the case of a Gauss-Jacobi method for points) it is very important to use an effective method for solving one of the many combinations. This reduction can be done by a reduced Gröbner basis.

The polynomials providing the solution for , , are quadratic, therefore their solution can be expressed in analytic form (in all of these three cases, only the positive root is correct).

The univariate polynomial for , , can also be computed by employing the accelerated Dixon resultant by the early discovery factors algorithm (Dixon’s EDF), which was suggested and implemented in the computer algebra system Fermat by Lewis [22].

Symbolic Solution for the Rotation Parameters (a, b, c)

The parameters of the skew-symmetric matrix can also be computed using a reduced Gröbner basis. Let us express a from equations and .

Then this finds a.

The parameter b is given by one of the two equations, let us say from .

The parameter c comes from .

Symbolic Solution for the Translation Parameters (, , )

The translation parameters can be similarly computed, but now from the original system of equations, .

Numerical Example

Let us consider the numerical values of three Hungarian points in the system of ETRS89 (European Terrestrial Reference System 1989) and in the local Hungarian system HD72 (Hungarian Data 1972) .

Using the Analytical Form of the Symbolic Solution

Now, we proceed with the numerical computation of the parameters, substituting the numerical values into the symbolic formulas.

Here are the numerical values of the scale parameters.

We continue similarly.

These are the parameters in the skew-symmetric matrix.

These are the translation parameters.

The total time for the numerical computation of the parameters from the symbolic solution is practically zero.

Using Numerical Global Polynomial Solver

In order to compare this result with the direct numerical solution, we solve the original system with NSolve.

The solution provides all roots.

From the eight solutions we need only the one where the scale variables are positive, .

The results of the numerical and symbolic solutions are the same, but the numerical solution is slower than the symbolic solution (which is practically zero instantaneous) and the numerical solution gives more than one solution, from which the single good solution must be selected.

Conclusion

A fully symbolic solution was suggested to solve the 3D affine data transformation problem. We demonstrated that an elimination technique (like the reduced Gröbner basis) can be used effectively to solve this problem. The symbolic reduction can be carried out “offline,” only once, so it does not influence the computing time. This feature can be very useful when one needs to solve a three-point problem multiple times, for example in the case of the Gauss-Jacobi solution of an -point problem. In addition, the result of the three-point problem can provide a good initial guess for solving an -point problem with local numerical methods.

Numerical computations were carried out with Mathematica 7 running on an HP xw 4100 workstation with Windows XP operating system, 3 GHz P4 Intel processor, and 1 GB RAM.

Acknowledgments

The authors are grateful to the reviewer for his/her remarks and suggestions and are indebted also to Daniel Lichtblau (Wolfram Research) for his valuable help in calling their attention to the proper application of the reduced Gröbner basis.

References

[1]	H. Späth, “A Numerical Method for Determining the Spatial Helmert Transformation in the Case of Different Scale Factors,” Zeitschrift für Geodäsie, Geoinformation und Landmanagement, 129, 2004 pp. 225-257.
[2]	E. Papp and L. Szucs, “Transformation Methods of the Traditional and Satellite Based Networks,” (in Hungarian with English abstract), Geomatikai Közlemenyek, VIII, 2005 pp. 85-92.
[3]	G. A. Watson, “Computing Helmert Transformations,” Journal of Computational and Applied Mathematics, 197(2), 2006 pp. 387-394. dx.doi.org/doi:10.1016/j.cam.2005.06.04.
[4]	G. H. Golub and V. Pereyra, “The Differentiation of Pseudo-Inverses and Nonlinear Least Squares Problems Whose Variables Separate,” SIAM Journal on Numerical Analysis, 10(2), 1973 pp. 413-432. www.jstor.org/stable/2156365.
[5]	A. Mathes, EasyTrans Pro-Edition: Professionelle Koordinatentransformation für Navigation, Vermessung und GIS (CD-ROM mit Benutzerhandbuch), Berlin: Herbert Wichmann Verlag, 2002.
[6]	H. Fröhlich and G. Bröker. “Trafox Version 2.1: 3d-kartesicsche Helmert-Transformation.” (2003).
[7]	O. Wolfrum, “Merging Terrestrial and Satellite Networks by a Ten-Parameter Transformation Model,” Manuscripta Geodaetica, 17(4), 1992 pp. 210-214.
[8]	E. Grafarend and G. Kampmann, “: The Ten-Parameter Conformal Group as a Datum Transformation in Three-Dimensional Euclidean Space,” Zeitschrift für Vermessungswesen, 2, 1996 pp. 68-77. www.uni-stuttgart.de/gi/research/paper/1996/Grafarend_Kampmann.pdf.
[9]	L. Völgyesi, G. Tóth, and J. Varga, “Conversions between Hungarian Map Projection Systems,” Periodica Polytechnica Civil Engineering, 40(1), 1996 pp. 73-83. www.pp.bme.hu/ci.
[10]	J. Cai and E. W. Grafarend, “Systematische Analyse der Transformation zwischen Gauss-Krüger” (poster presentation), Koordinaten/DHDN und UTM—Koordinaten/ETRS89 angewandt auf Baden-Württemberg, Geodätische Woche 2004, Stuttgart, 2004.
[11]	A. Barsi, “Performing Coordinate Transformation by Artificial Neural Network,” Allgemeine Vermessungs-Nachrichten, 108(4), 2001 pp. 134-137. www.wichmann-verlag.de/avn-ausgabe-04-2001/ performing-coordinate-transformation-by-artificial-neural-network.html.
[12]	P. Zaletnyik, “Coordinate Transformation with Neural Networks and with Polynomials in Hungary,” in Proceedings of International Symposium on Modern Technologies, Education and Professional Practice in Geodesy and Related Fields, Sofia, Bulgaria: Union of Surveyors and Land Managers in Bulgaria (USLMB), 2004 pp. 471-479. mycite.omikk.bme.hu/doc/37231.pdf.
[13]	J. L. Awange and E. W. Grafarend, Solving Algebraic Computational Problems in Geodesy and Geoinformatics, Berlin: Springer, 2005.
[14]	S. Bancroft, “An Algebraic Solution of the GPS Equations,” IEEE Transactions on Aerospace and Electronic Systems, AES-21(1), 1985 pp. 56-59. dx.doi.org/doi:10.1109/TAES.1985.310538.
[15]	E. Grafarend and B. Schaffrin, Ausgleichungsrechnung in linearen Modellen, Mannheim: B.I. Wissenschaftsverlag, 1993.
[16]	P. Singer, D. Ströbel, R. Hördt, J. Bahndorf, and K. Linkwitz, “Direkte Lösung des räumlichen Bogenschnitts,” Zeitschrift für Vermessungswesen, 118, 1993 pp. 20-24.
[17]	A. Kleusberg, “Die direkte Lösung des räumlichen Hyperbelschnitts,” Zeitschrift für Vermessungswesen, 119(4), 1994 pp. 188-192.
[18]	A. Kleusberg, “Analytical GPS Navigation Solution,” Geodesy—The Challenge of the 3rd Millennium, (E. W. Grafarend, F. W. Krumm, and V. S. Schwarze, eds.) New York: Springer, 2003 pp. 93-96.
[19]	H. Lichtenegger, “Eine direkte Lösung des räumlichen Bogenschnitts,” Österreichische Zeitschrift für Vermessung und Geoinformation, 83, 1995 pp. 224-226.
[20]	J. L. Awange, “Gröbner Bases, Multipolynomial Resultants and the Gauss-Jacobi Combinatorial Algorithms—Adjustment of Nonlinear GPS/LPS Observations,” Dissertation (D93), Geodätisches Institut der Universität Stuttgart, 2002. www.ifp.uni-stuttgart.de/publications/schriftenreihe/Awange.html.
[21]	J. L. Awange and E. W. Grafarend, “Closed Form Solution of the Overdetermined Nonlinear 7 Parameter Datum Transformation,” Allgemeine Vermessungs-Nachrichten (AVN), 110, 2003 pp.130-148.
[22]	R. H. Lewis, “Heuristics to Accelerate the Dixon Resultant,” Mathematics and Computers in Simulation, 77(4), 2008 pp. 400-407. dx.doi.org/doi:10.1016/j.matcom.2007.04.007.
B. Paláncz and Z. Piroska, “A Symbolic Solution of a 3D Affine Transformation,” The Mathematica Journal, 2011. dx.doi.org/doi:10.3888/tmj.13-9.

About the Authors

Béla Paláncz is a professor of computer science. He received his D.Sc. from the Hungarian Academy of Sciences in 1993, and has extensive experience in education and research in the field of mathematical modeling and numeric-symbolic computations (RWTH Aachen, Germany; Imperial College, London; Wolfram Research Inc., Champaign, IL, USA).

Piroska Zaletnyik (Ph.D., Budapest University of Technology and Economics [BUTE], Hungary) is currently working as an assistant professor in the Department of Geodesy and Surveying of BUTE. She was previously a visiting scholar in Germany at Stuttgart University and at the Ohio State University. She has experience using computer algebra systems in geodesy.

Béla Paláncz
Department of Photogrammetry and Geoinformatics
Budapest University of Technology and Economy, H – 1521, Hungary
palancz@epito.bme.hu

Zaletnyik Piroska
Department of Geodesy and Surveying
Budapest University of Technology and Economy, H – 1521, Hungary
zaletnyikp@gmail.com