
\title{Google Summer of Code for Geoinformatics}
\author{Jan Je\v{z}ek}

\maketitle

\section{Abstract}

The GeoTools Referencing module has been becoming one of the most powerful tools focused on coordinate reference system transformations in the Java GIS world in recent years. The Referencing module in conjunction with the Coverage module presents a really strong tool for raster operations like re-projecting and transforming.

The aim of this paper is to describe new functionality that has been developed by author during the Google Summer of Code 2006 and 2007 projects. The usability of these new features will be discussed also with relation to the specific needs of reference coordinate systems that are used in the Czech Republic. Google Summer of Code itself will be also mentioned.

New functionality that was and still is being developed is focused on transformation methods based on interpolation. These procedures are usually applied in cases when transformation between coordinate systems is not some kind of exact mathematical relationship (such as cartographic projection or affine transformation for example).

This topic is closely related to rectification of old maps as well as the transformation of coordinate reference systems for those datums, that have been derived before GPS techniques started to rule and so their transformation into the global systems like WGS 84 is problematic and not as accurate as needed.

\section{Google Summer of Code for Geoinformatics}

Google Summer of Code (GSoC) is well known event that brings together students that are interested in open source software with core developers of projects from all branches. Huge projects like KDE, Ubuntu Linux, Apache Software Foundation, etc. participate in this program every year. The aim of GSoC is to get interested students involved in these project.  Google plays the sponsor roll (among others) in the whole program and offer stipends for students that successfully participate. For detailed information about GSoC see \cite{gsoc}.


The summer of 2007 saw the third volume of this event. The open source geospatial community started to participate in GSoC in 2006 when Refractions Research took the roll of mentoring organization. The projects that had been worked on were focused on the GeoTools library and the uDig desktop GIS. For more information about GSoC 2006 mentored by Refractions Research see \cite{refr}.

OSGeo joined the program in the summer of 2007 and helped to get sponsorship for 12 students that contributed to a wide range of FOSS4G projects (GRASS, GDAL, GeoTools, Geoserver and uDig). For detailed information see \cite{osgeo}.

\begin{figure*}
  \centering
  \subfloat[Inverse distance weighted interpolation.]{\label{fig:meth_iter_A}%
    \includegraphics[width=0.3\textwidth]{proceedings/jezek/images/rbs.png}}%
  \quad%
  \subfloat[Thin plate spline.]{\label{fig:meth_iter_B}%
    \includegraphics[width=0.3\textwidth]{proceedings/jezek/images/tps.png}}
  \quad%
  \subfloat[Rubber sheeting.]{\label{fig:meth_iter_C}%
    \includegraphics[width=0.3\textwidth]{proceedings/jezek/images/idw.png}}
  \caption{Output of three interpolation methods}
  \label{fig:meth_iter_ABC}
\end{figure*}

\section{Additional functions for coordinate system transformations in GeoTools and uDig}

This part describes the work that has been done by the author during Summer of Code 2006 and 2007. The project was mentored by Jesse Eicher and Martin Desruisseaux.

The GeoTools Referencing package presents one of the most powerful tool for re-projecting and transforming in the Java GIS world. The package follows the OGC implementation specification \cite{ogc}. The package also offers a plugin mechanism, that lets users connect to persistent storage of datums and projection parameters such as an EPSG database \cite{epsg}.

The project that I've been working on during 2006 and 2007 has been focused on new coordinate system transformation algorithms.  The aim was to implement tools that helps to solve the opposite transformation task --- the task when we know some coordinates in source and target coordinate reference systems (mapped coordinates) and we are searching for the definition of transformation.

\subsection{Linear transformations}

There are a couple of transformation methods that can be unequally defined from known coordinates in source and target coordinate reference systems (CRS). This methods can be divided into two main branches --- linear transformation and no residual methods.

New implemented tools can be used to calculate transformation parameters for these linear methods:

\begin{itemize}
  \item Similar Transformation
  \item Linear Transformation
  \item Affine Transformation
  \item Projective Transformation
  \item Position vectors (Bursa Wolf) transformation (3D similar 7 parameters)
\end{itemize}

These methods are unequally defined by different number of mapped position (Similar transformation needs 2, for example). When there are more coordinates than needed the least square method is used to minimize the square of distance between target and transformed source point. Currently there is just Cartesian distance taken into account.

\subsection{No Residual algorithms}

Another set of algorithms that has been implemented is focused on possibilities to calculate transformations that will exactly fit the source positions to target positions  no matter how many mapped positions are defined (this is also called warp transformation). After studying the possibilities to define such methods through EPSG database conventions we choose the following approach.

One of the most general transformation that is defined in the EPSG database is the method based on a regular grid of coordinate offsets. Within this grid simple bi-linear interpolation is used so once you know the grid values you can apply the transformation quite fast.  The family of grid-based methods includes:  
\begin{itemize}
 \item  NADCON (EPSG dataset coordinate operation method code 9613) which is used by the US National Geodetic Survey for transformation between US systems 
 \item NTv2 (EPSG dataset coordinate operation method code 9615) which originated in the national mapping agency of Canada and was subsequently adopted in Australia and New Zealand 
 \item  OSTN (EPSG dataset coordinate operation method code 9633) used in Great Britain
\end{itemize}

For more information see [\cite{epsg}].

There have been 3 algorithms implemented that enable users to calculate the grid. These methods are:
\begin{description}
 \item[Inverse distance weighted Interpolation:] 
 The offset values are calculated according to the distance from the known mapped positions
\item[Thin plate spline interpolation:] 
The name thin plate spline refers to a physical analogy involving the bending of a thin sheet of metal. In the physical setting, the deflection is in the z direction, orthogonal to the plane \cite{wiki}. The offsets in both direction (x and y or easting and northing) are calculated in this manner.
\item[Rubber Sheeting method:] 
The surface is divided into particular triangles by applying Delaunay's algorithm on the field mapped positions. Then the affine transformation on each triangle is applied. This method should be applied also  as a piece-wise but calculation of the grid makes it more general, reusable an faster.
\end{description}

\subsection{Implementation details}

Described functions have been designed to become a part of the GeoTools referencing module. 

The algorithms let you generate grid files that can be reused also in other software --- in all that support EPSG methods explained above.The grid based transformation is designed to be performed using Java Advance Imaging (JAI) warp transform. This greatly helps improve performance especially when transforming raster datasets (JAI is using native library). 

Other interesting results are when we try to visualise the calculated grids by converting calculated values to images. In this manner we can  nicely see the distribution of the offsets and also the differences between applying particular method. You can see interpolated grids by all three methods using the same set of mapped positions in Figure \ref{fig:meth_iter_ABC}.
 
All described functionality are currently located online.\footnote{GSOC transformations page: \url{http://svn.geotools.org/geotools/trunk/spike/jan/gsoc-transformations/}}

Migration into GeoTools 2.5 will take place during upcoming months. Other documentation and code examples can be found on the GeoTools website.\footnote{GeoTools website: \url{http://geotools.codehaus.org/ New+Transformation+Algorithms+for+GeoTools+and+uDig}}

\subsection{uDig plugin}

Finally, the simple uDig plugin that lets users calculate and apply described methods has been made. The plugin presents a GUI for accessing the described functions. First draft of this plugin is available from the community update site (see \cite{update}) and lets you transform vector data using only a few methods (this was developed during Summer of Code 2006).   A plugin that includes all described features has been developed only for trunk version of uDig, that is currently changing a lot so the stable version of plugin  will be done after first milestone release of uDig 1.2.

\begin{footnotesize}

\begin{thebibliography}{99}
\bibitem{wiki} Wikipedia, the free encyclopedia, Thin plate spline, available at \url{http://en.wikipedia.org/wiki/Thin_plate_spline} , [29.10.2007].
\bibitem{epsg} EPSG, Coordinate Conversions and Transformation including Formulas, available at \url{http://www.epsg.org}, [29.10.2007].
\bibitem{ogc} OGC, Coordinate Transformation Service Implementation Specification, available at \url{http://www.opengeospatial.org/standards/ct}, [29.10.2007].

\bibitem{gsoc} Google, Google Summer of Code, available at \url{http://code.google.com/soc/}, [29.10.2007].
\bibitem{refr} Refractions Research, Refractions Research project ideas, available at \newline \url{http://code.google.com/soc/2006/refract/about.html}, [29.10.2007].
\bibitem{osgeo} OSGeo, OSGeo project ideas, available at \url{http://code.google.com/soc/2007/osgeo/about.html}, [29.10.2007].
\bibitem{update} Refractions Research, uDig update site,  available at \url{http://udig.refractions.net/confluence/display/UDIG/uDig+Update+Site}, [29.10.2007].

\end{thebibliography}
\end{footnotesize}

\address{Jan Je\v{z}ek\\
 \email{h.jezek AT centrum.cz}
}
