\title{Google Summer of Code pour la g\'eomatique}
\author{Jan Je\v{z}ek, traduit par Sidonie Christophe}

\maketitle

\section{R\'esum\'e}

%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.

Ces derni\`eres ann\'ees, le module de r\'ef\'erencement de GeoTools est devenu un des outils les plus puissants de transformation de syst\`emes de coordonn\'ees de r\'ef\'erence dans le monde SIG Java. Le module de r\'ef\'erencement, avec le module de "couverture", poss\`ede un outil r\'eellement puissant pour les op\'erations, du genre re-projection et transformation de donn\'ees matricielles.

%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.

Le but de cet article est de d\'ecrire une nouvelle fonctionnalit\'e qui a \'et\'e d\'evelopp\'ee par l'auteur pendant les projets des Google Summer of Code 2006 et 2007. Ses potentialit\'es d'utilisation seront aussi discut\'ees en rapport avec les besoins sp\'ecifiques sur les syst\`emes de coordonn\'ees de r\'ef\'erence utilis\'es en R\'epublique Tch\`eque. Il sera aussi question du Google Summer of Code lui-m\^eme.

%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).

La nouvelle fonctionnalit\'e qui a \'et\'e d\'evelopp\'ee, et est toujours en d\'eveloppement, concerne les m\'ethodes bas\'ees sur l'interpolation. Ces proc\'edures sont g\'en\'eralement utilis\'ees dans les cas o\`u la transformation entre les syst\`emes de coordonn\'ees n'est pas une relation math\'ematique exacte (comme la projection cartographique ou la transformation affine par exemple).

%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.

Ce sujet est \'etroitement li\'e \`a la rectification des cartes anciennes, ainsi qu'\`a la transformation des syst\`emes de coordonn\'ees de r\'ef\'erence pour ces r\'ef\'erentiels, qui ont \'et\'e d\'eriv\'ees avant que les techniques GPS soient clairement d\'efinies, ce qui rend leur transformation dans les syst\`emes globaux comme le WGS 84, probl\'ematique et beaucoup moins pr\'ecise que pr\'evu. 

\section{Google Summer of Code pour la g\'eomatique}

%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}.

Le Google Summer of Code (GSoC) est un \'ev\`enement bien connu, rassemblant des \'etudiants int\'eress\'es par les logiciels open-source avec des d\'eveloppeurs de projets vari\'es. D'\'enormes projets comme KDE, Ubuntu Linux, Apache Software Foundatoin, etc. participent \`a ce programme chaque ann\'ee.  Le but du GSoC est de faire en sorte que les \'etudiants int\'eress\'es participent \`a ce projet. Google joue le r\^ole de sponsor (entre autres) au sein du programme en entier et offre des bourses aux \'etudiants qui participent avec succ\`es. Pour plus de d\'etails sur le GSoC, voir \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}.

La troisi\`eme \'edition de cet \'ev\`enement a eu lieu \`a l'\'et\'e 2007. La communaut\'e g\'eospatiale open source a commenc\'e \`a participer au GSoC en 2006 quand Refractions est devenu organisateur. Les projets concern\'es se concentraient sur la librairie GeoTools et la plateforme SIG uDig. Pour plus d'information au sujet du GSoC 2006 encadr\'e par Refractions, voir \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}.

L'OSGEO a rejoint le programme cet \'et\'e 2007 et a permis d'obtenir le parrainage de 12 \'etudiants qui ont contribu\'e \`a une large s\'erie de projets FOSS4G (GRASS, GDAL, GeoTools, GeoServer et uDig). Pour des informations d\'etaill\'ees, voir \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{Fonctions additionnelles pour les conversions de syst\`emes de coordonn\'ees dans GeoTools et 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.

Cette partie d\'ecrit le travail r\'ealis\'e par l'auteur pendant les GSoC 2006 et 2007. Le projet \'etait encadr\'e par Jesse Ficher et 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}.

Le package GeoTools Referencing pr\'esente un des outils les plus puissants permettant de re-projeter et r\'ealiser des transformations dans le monde des SIG Java. Le package respecte les sp\'ecifications d'impl\'ementation OGC \cite{ogc}. Il offre aussi un m\'ecanisme de plugin, qui permet aux utilisateurs de se connecter \`a des bases persistantes de r\'ef\'erentiels et de param\`etres de projection, comme une base de donn\'ees EPSG \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.

Le projet sur lequel j'ai travaill\'e durant 2006 et 2007 concernait de nouveaux algorithmes de conversion de syst\`emes de coordonn\'ees. Le but \'etait d'impl\'ementer des outils qui aident \`a r\'esoudre la t\^ache de transformation inverse : nous connaissons quelques coordonn\'ees dans la source et le syst\`eme de coordonn\'ees de r\'ef\'erence de la cible (coordonn\'ees mapp\'ees), et nous cherchons une d\'efinition de la transformation.

\subsection{Transformations lin\'eaires}

%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.

%SV : in\'egalement d\'efinies ??? \c{c}a me sonne vraiment vraiment pas beau... mais je ne vois pas bien ce qu'il veut dire en fait !!
%SCH: suis cplt ok, je vois pas non plus 

Il existe deux m\'ethodes de transformation, in\'egalement d\'efinies, \`a partir des coordonn\'ees connues dans la source et le syst\`eme de coordonn\'ees de r\'ef\'erence (CRS). Ces m\'ethodes peuvent \^etre divis\'ees en deux cat\'egories : les transformations lin\'eaires et les m\'ethodes sans r\'esidus.

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

Les nouveaux outils d\'evelopp\'es peuvent \^etre utilis\'es pour calculer les param\`etres de transformation pour ces m\'ethodes lin\'eaires :

\begin{itemize}
  \item Transformation similaire
  \item Transformation lin\'eaire
  \item Transformation affine
  \item Transformation projective
  \item Transformation des vecteurs-position (Bursa Wolf) (7 param\`etres comme en 3D)
%SV : cet item semble avoir \'echapp\'e \`a la trad
%SV : \item Transformation des vecteurs-position (Bursa Wolf) (7 param\`etres comme en 3D)
\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.

Ces m\'ethodes sont in\'egalement d\'efinies par diff\'erents nombres de positions cartographi\'ees (une transformation dite similaire en n\'ecessite 2, par exemple). Quand il y a plus de coordonn\'ees que n\'ecessaires, on utilise la m\'ethode des moindres carr\'e pour minimiser le carr\'e de la distance entre la cible et le point source transform\'e. Actuellement, seule la distance cart\'esienne est prise en compte. 

\subsection{Algorithmes non r\'esiduels}

%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.

%SV : warp = par d\'eformation

Un autre ensemble d'algorithmes qui ont \'et\'e impl\'ement\'es concerne les possibilit\'es de calculer des transformations qui vont faire correspondre exactement les positions sources et les positions cibles, peu importe combien de positions ont \'et\'e d\'efinies (on appelle ceci une transformation par d\'eformation). Apr\`es avoir \'etudi\'e les possibilit\'es de d\'efinir de telles m\'ethodes gr\^ace aux conventions d'une base de donn\'ees EPSG, nous avons choisi l'approche suivante.

%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:  

%SV : phrase bancale ; je pr\'ef\`ererais
% Pour d\'efinir ces transformations, on utilise, comme dans la base EPSG, une m\'ethode bas\'ee sur une grille r\'eguli\`ere de coordonn\'ees. Dans cette grille, on applique une interpolation bi-lin\'eaire. 
%SV - remarque g\'en\'erale : en math, le "you" se traduit plus volontiers par le "on" car le matheux fran\c{c}ais est plus impersonnel que le matheux anglophone...

 Pour d\'efinir ces transformations, on utilise, comme dans la base EPSG, une m\'ethode bas\'ee sur une grille r\'eguli\`ere de coordonn\'ees. Dans cette grille, on applique une interpolation bi-lin\'eaire ; donc une fois qu'on connait les valeurs de grille, on peut appliquer la transformation assez rapidement. La famille des m\'ethodes bas\'ees sur des grilles comprend :

%\begin{itemize}
% \item  NADCON (EPSG dataset coordinate operation method code 9613) which is used by the US National Geodetic Survey for transformation between USsystems 
% \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}

\begin{itemize}
 \item  NADCON (EPSG dataset coordinate operation method code 9613) qui est utilis\'e par le US National Geodetic Survey pour des transformations entre les syst\`emes US
 \item NTv2 (EPSG dataset coordinate operation method code 9615) qui a \'et\'e cr\'e\'e \`a l'agence nationale de cartographie du Canada et qui a \'et\'e ensuite adopt\'ee par l'Australie et la Nouvelle Z\'elande.
 \item  OSTN (EPSG dataset coordinate operation method code 9633) utilis\'e en Grande Bretagne.
\end{itemize}

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

Pour plus d'informations, voir [\cite{epsg}].

%There have been 3 algorithms implemented that enable users to calculate the grid. These methods are:

%SV : je propose
% Trois algorithmes ont \'et\'e impl\'ement\'es pour permettre aux utilisateur de calculer cette grille.

Trois algorithmes ont \'et\'e impl\'ement\'es pour permettre aux utilisateur de calculer cette grille. Ces m\'ethodes sont :

%\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}

\begin{description}
 \item[Interpolation par inverse de la distance pond\'er\'ee :] 
 Les valeurs offset sont calcul\'ees selon la distance depuis les positions cartographi\'ees connues
\item[Interpolation par splines de plaques minces (thin plate spline) :] 
Le nom de cette m\'ethode fait r\'ef\'erence \`a une analogie physique impliquant la flexion d'une mince feuille de m\'etal. En physique, la d\'eflection est en $z$, perpendiculaire au plan \cite{wiki}. Les d\'ecalages dans les deux directions ($x$ et $y$) sont calcul\'es de cette mani\`ere.
\item[M\'ethode de la couverture de caoutchouc (Rubber Sheeting) :] 
La surface est divis\'ee en triangles particuliers en utilisant l'algorithme de Delaunay sur le champ des positions cartographi\'ees.
 Ensuite, une transformation affine est appliqu\'ee sur chaque triangle. Cette m\'ethode devrait aussi \^etre appliqu\'ee par morceaux, mais le calcul de la grille la rend plus g\'en\'erale, r\'eutilisable et plus rapide.
\end{description}


\subsection{D\'etails d'impl\'ementation}

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

Les fonctions d\'ecrites ont \'et\'e con\c{c}ues afin d'\^etre int\'egr\'ees dans le module de r\'ef\'erencement de GeoTools.

%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). 

Les algorithmes permettent de g\'en\'erer des fichiers de grilles qui peuvent \^etre r\'eutilis\'es dans d'autres logiciels --- dans tous ceux qui supportent les m\'ethodes EPSG expliqu\'ees ci-dessus. La transformation bas\'ee sur grille est con\c{c}ue pour \^etre utilis\'ee avec la transformation par d\'eformation du Java Advance Imaging (JAI) Ceci am\'eliore grandement les performances, sp\'ecialement lors de la transformation de jeux de donn\'ees raster (JAI utilise une librairie native). 

%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}.

D'autres r\'esultats int\'eressants apparaissent quand on essaie de visualiser les grilles calcul\'ees en convertissant les valeurs calcul\'ees en images. De cette fa\c{c}on, on peut voir la distribution des d\'ecalages et aussi les diff\'erences entre les diverses m\'ethodes appliqu\'ees. Vous pouvez voir les grilles interpol\'ees par les 3 m\'ethodes utilisant le m\^eme ensemble de positions cartographi\'ees sur la 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/}}

Toutes les fonctionnalit\'es d\'ecrites sont en ligne. \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}}

La migration dans GeoTools 2.5 se fera dans les mois \`a venir. D'autres documentations et des exemples de codes peuvent \^etre r\'ecup\'er\'es sur le site GeoTools.\footnote{GeoTools website: \url{http://geotools.codehaus.org/ New+Transformation+Algorithms+for+GeoTools+and+uDig}}


\subsection{Plugin uDig}

%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.

Pour finir, nous avons cr\'ee un plugin uDig qui permet aux utilisateurs de calculer et d'appliquer les m\'ethodes d\'ecrites. Le plugin pr\'esente une interface graphique pour acc\'eder \`a ces fonctions. Un premier brouillon de ce plugin est disponible sur le site de la communaut\'e (see \cite{update}) et vous permet de tranformer des donn\'ees vecteur en utilisant seulement quelques m\'ethodes (ceci a \'et\'e d\'evelopp\'e pendant le GSoC 2006). Un plugin qui inclus toutes les caract\'eristiques d\'ecrites, a \'et\'e d\'evelopp\'e seulement pour la version CVS de uDig ; il est toujours en cours de modification et donc la version stable sera op\'erationnelle pour la version 1.2 de uDig. 

\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}
}
