You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@sis.apache.org by de...@apache.org on 2016/06/02 04:57:06 UTC
svn commit: r1746518 [2/6] - in /sis/site/trunk: book/en/ book/fr/
book/math/ content/book/en/ content/book/fr/
Copied: sis/site/trunk/book/math/AxisSwapping2D.html (from r1745833, sis/site/trunk/book/fr/referencing.html)
URL: http://svn.apache.org/viewvc/sis/site/trunk/book/math/AxisSwapping2D.html?p2=sis/site/trunk/book/math/AxisSwapping2D.html&p1=sis/site/trunk/book/fr/referencing.html&r1=1745833&r2=1746518&rev=1746518&view=diff
==============================================================================
--- sis/site/trunk/book/fr/referencing.html (original)
+++ sis/site/trunk/book/math/AxisSwapping2D.html Thu Jun 2 04:57:06 2016
@@ -20,886 +20,32 @@
under the License.
-->
-<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="fr"
- xmlns:xi = "http://www.w3.org/2001/XInclude">
+<html xmlns="http://www.w3.org/1999/xhtml">
<head>
- <title>Systèmes de références spatiales par coordonnées</title>
+ <title>Axis swapping in a two-dimensional coordinate system</title>
<link rel="stylesheet" type="text/css" href="../book.css"/>
</head>
<body>
- <header>
- <h1 id="Referencing">Systèmes de références spatiales</h1>
- </header>
- <p>
- Pour donner une position sur la Terre on peut utiliser des noms tels que celui d’une ville ou une adresse postale
- — on parle alors de références spatiales par <cite>identifiants</cite> —
- ou on peut donner des valeurs numériques valides dans un système de coordonnées donné
- — on parle alors de références spatiales par <cite>coordonnées</cite>.
- Chaque système implique des approximations telles que:
- </p>
- <ul>
- <li>Le choix de la forme géométrique (géoïde, ellipsoïde, <i>etc.</i>) utilisée comme approximation de la forme de la Terre.</li>
- <li>Le choix des propriétés géométriques (angles, distances, <i>etc.</i>) à préserver lors de la représentation d’une carte sur une surface plane.</li>
- <li>Les pertes de précision lorsque l’on doit transformer des positions exprimées selon un système vers des positions exprimées selon un autre système.</li>
- </ul>
- <p>
- En l’absence d’indication contraire, la précision recherchée pour les coordonnées sur la Terre est de 1 centimètre.
- Mais la maîtrise de cette précision nécessite le respect de certaines conditions:
- </p>
- <ul>
- <li>Rester dans la zone de validité du système telle que donnée par <code>ReferenceSystem.getDomainOfValidity()</code>.</li>
- <li>Savoir que les mesures de distances dans une projection cartographique donnée ne sont vraies qu’à certains endroits,
- appelés par exemple « parallèles standards ».</li>
- <li>Vérifier la précision des transformations de coordonnées, par exemple avec
- <code>CoordinateOperation.getCoordinateOperationAccuracy()</code>.</li>
- </ul>
- <p>
- Le module <code>sis-referencing</code> de Apache <abbr>SIS</abbr> fournit un ensemble de classes implémentant
- les différentes spécialisations de l’interface <code>ReferenceSystem</code> ainsi que leurs composantes.
- Ces implémentations permettent de stocker une description des systèmes de références spatiales
- ainsi que leurs méta-données telles que la zone de validité.
- Toutefois ces objets n’effectuent aucune opération sur les coordonnées.
- Ces opérations sont le travail d’une autre famille de classes, dont la racine est l’interface <code>CoordinateOperation</code>.
- Ces classes seront discutées dans <a href="#CoordinateOperation">une autre section</a>,
- mais nous mentionnons ici deux spécialisations en rapport avec le sujet de la précision des coordonnées:
- </p>
- <ul>
- <li>
- <p>Les <strong>conversions</strong> de coordonnées sont entièrement définies par une formule mathématique.
- Les conversions s’effectueraient avec une précision infinie s’il n’y avait pas les inévitables
- erreurs d’arrondissements inhérents aux calculs sur des nombres réels.</p>
- <div class="example"><p><b>Exemple:</b> les projections cartographiques.</p></div>
- </li><li>
- <p>Les <strong>transformations</strong> de coordonnées sont définies de manière empirique.
- Elles ont souvent des erreurs de quelques mètres qui ne sont pas dues à des limites de la précision des ordinateurs.
- Ces erreurs découlent du fait que la transformation utilisée n’est qu’une approximation d’une réalité plus complexe.</p>
-
- <div class="example"><p><b>Exemple:</b> les changements de référentiels tel que le passage de la
- <cite>Nouvelle Triangulation Française</cite> (<abbr>NTF</abbr>) vers le
- <cite>Réseau Géodésique Français 1993</cite> (<abbr>RGF93</abbr>),
- même lorsque la méthode de projection cartographique (Lambert conique conforme) ne change pas.</p></div>
- </li>
- </ul>
-
-
-
- <h2 id="CRS_Components">Composantes d’un système de références par coordonnées</h2>
- <p>
- Les systèmes de références spatiales par coordonnées fournissent les informations nécessaires pour faire
- correspondre des coordonnées numériques à des positions dans le monde réel. Dans Apache <abbr>SIS</abbr>,
- ils sont pratiquement tous représentés par des classes dont le nom se termine en <abbr>CRS</abbr>
- (l’abréviation de <i>Coordinate Reference System</i> en anglais). Ces objets contiennent:
- </p>
- <ul>
- <li>Un référentiel (<i>datum</i> en anglais),
- qui indique entre autres quel ellipsoïde utiliser comme approximation de la forme de la terre.</li>
- <li>Une description de chaque axe (nom, direction, unité de mesure, limites).</li>
- <li>Parfois une liste de paramètres permettant de convertir les coordonnées d’un autre système.
- C’est le cas notamment lorsqu’on utilise des projections cartographiques.</li>
- </ul>
- <p>
- Ces systèmes sont décrits par la norme <abbr>ISO</abbr> 19111 (<i>Referencing by Coordinates</i>),
- qui remplace en grande partie une norme plus ancienne mais encore utilisée pour certains aspects,
- <abbr>OGC 01-009</abbr> (<i>Coordinate Transformation Services</i>).
- Ces normes sont complétées par deux autres standards définissant des formats d’échanges:
- <abbr>ISO</abbr> 19136 et 19162 pour respectivement
- le <cite>Geographic Markup Language</cite> (<abbr>GML</abbr>) — un format <abbr>XML</abbr> précis mais verbeux —
- et le <cite>Well-Known Text</cite> (<abbr>WKT</abbr>) — un format texte plus facile à lire par les humains.
- </p>
-
- <h3 id="Ellipsoid">Géoïde et ellipsoïde</h3>
- <p>
- La surface topographique réelle étant difficile à représenter mathématiquement, elle n’est pas utilisée directement en cartographie.
- Une autre surface un peu plus facilement utilisable est le géoïde,
- une surface sur laquelle la force gravitationnelle a partout la même valeur (surface équipotentielle du champ de gravité terrestre).
- Cette surface est en tout point perpendiculaire à la direction indiquée par un fil à plomb (verticale du lieu).
- Le géoïde coïnciderait avec le niveau moyen des mers s’il n’y avait ni vent ni courants marins permanents comme le Gulf Stream.
- </p><p>
- Tout en étant nettement plus lisse que la surface topographique,
- le géoïde présente des creux et des bosses liés à l’inégale distribution des masses de la Terre.
- Pour une utilisation mathématiquement plus aisée, le géoïde est donc approximé par un ellipsoïde.
- Cette « figure de la Terre » est représentée dans GeoAPI par l’interface <code>Ellipsoid</code>,
- qui constitue un élément fondamental des systèmes de références de type <code>GeographicCRS</code> et <code>ProjectedCRS</code>.
- Plusieurs dizaines d’ellipsoïdes sont couramment employés pour la définition de référentiels.
- Certains offrent une excellente approximation pour une région précise
- au détriment des régions pour lesquelles le référentiel n’a pas été conçu,
- et d’autres offrant un compromis pour l’ensemble de la planète.
- </p>
- <div class="example"><p><b>Exemple:</b>
- au début du XX<sup>e</sup> siècle aux États-Unis, l’état du Michigan utilisait pour ses cartes un ellipsoïde basé
- sur l’ellipsoïde « Clarke 1866 » mais auquel la longueur des axes a été allongée de 800 pieds.
- Cette modification visait à tenir compte du niveau moyen de l’état au dessus du niveau de la mer.</p>
- </div>
-
- <h3 id="GeodeticDatum">Référentiel géodésique</h3>
- <p>
- Pour définir un système géodésique dans un pays, l’état met en place un ellipsoïde de référence
- qui épouse au mieux sur l’ensemble du pays la forme locale du géoïde.
- L’écart entre cet ellipsoïde de référence et les creux et les bosses du géoïde reste généralement inférieur à 100 mètres.
- Les paramètres qui permettent de lier un <code>Ellipsoid</code> à la surface de la Terre (par exemple la position de son centre)
- sont représentées par un objet de type <code>GeodeticDatum</code>, que l’on traduit en français par « référentiel géodésique ».
- Plusieurs <code>GeodeticDatum</code> peuvent utiliser le même <code>Ellipsoid</code>, mais centré ou orienté différemment.
- </p><p>
- Avant l’avènement des satellites, les mesures géodésiques se déroulaient exclusivement à la surface de la terre.
- En conséquence, deux îles ou continents qui ne sont pas à portée visuelle l’un de l’autre n’étaient pas rattachés géodésiquement entre eux.
- Ainsi les référentiels <cite>North American Datum 1983</cite> (<abbr>NAD83</abbr>) et
- <cite>European Datum 1950</cite> (<abbr>ED50</abbr>) sont indépendants l’un de l’autre:
- leurs ellipsoïdes de référence ont des centres distincts et des dimensions différentes.
- Une même coordonnée géographique correspondra à des positions différentes dans le monde réel
- selon que la coordonnée se réfère à l’un ou l’autre de ces référentiels.
- </p><p>
- L’invention du <abbr title="Global Positioning System">GPS</abbr> a précipité la création d’un système géodésique mondial,
- nommé <abbr title="World Geodetic System 1984">WGS84</abbr>.
- L’ellipsoïde de référence est alors unique et centré au centre de gravité de la terre.
- Les <abbr>GPS</abbr> donnent à tout moment la position absolue du récepteur rapportée à ce système géodésique.
- Mais <abbr>WGS84</abbr> étant un système mondial, il peut diverger significativement des systèmes locaux.
- Par exemple l’écart entre <abbr>WGS84</abbr> et le système européen <abbr>ED50</abbr> est de l’ordre de 150 mètres,
- et l’écart moyen par rapport au système de l’île de la Réunion 1947 est de 1,5 kilomètres.
- Il ne faut donc pas rapporter aveuglement des positions <abbr>GPS</abbr> sur une carte.
- Des correspondances avec les systèmes régionaux peuvent être nécessaires
- et sont représentées dans GeoAPI sous forme d’objets de type <code>Transformation</code>
- (une classe d’opérations mentionnée dans l’<a href="#Referencing">introduction de ce chapitre</a>).
- </p><p>
- Les généralisation de l’usage du système <abbr>WGS84</abbr> tend à réduire le besoin d’utiliser
- les objets <code>Transformation</code> pour les données récentes, mais ne l’élimine pas complètement.
- La Terre bouge sous l’effet de la tectonique des plaques et de nouveaux systèmes sont définis chaque année pour en tenir compte.
- Par exemple bien que le référentiel <abbr>NAD83</abbr> a été défini à l’origine comme pratiquement équivalent à <abbr>WGS84</abbr>,
- il existe maintenant (en 2016) un écart d’environ 1.5 mètres entre ces deux systèmes.
- Le référentiel <cite>Japanese Geodetic Datum 2000</cite> était aussi défini comme pratiquement équivalent à <abbr>WGS84</abbr>,
- mais le nouveau référentiel <cite>Japanese Geodetic Datum 2011</cite> s’en écarte.
- Le référentiel <abbr>WGS84</abbr> lui-même, sensé correspondre à une définition à un instant donné,
- a subit des révisions dues notamment à l’amélioration de la précision des instruments.
- Ainsi il existe aujourd’hui au moins six versions de <abbr>WGS84</abbr>.
- En outre beaucoups de bordures ont été définies légalement dans des référentiels plus anciens, par exemple <abbr>NAD27</abbr> aux États-Unis.
- Mettre à jour dans un nouveau référentiel peut obliger à transformer des lignes droites ou des formes géométriques simples en des formes plus irrégulières
- si on ne veut pas que des parcelles de terrain changent de propriétaire.
- </p>
- <article>
- <header>
- <h1>Bibliothèques de type « early binding » versus « late binding »</h1>
- </header>
- <p>
- Le caractère universel du système <abbr>WGS84</abbr> rend tentante l’idée de l’utiliser comme système pivot,
- afin de simplifier l’implémentation d’une bibliothèque de transformation de coordonnées.
- La transformation d’une coordonnée d’un référentiel <var>A</var> vers un référentiel <var>B</var>
- pourrait se faire en transformant d’abord de <var>A</var> vers <abbr>WGS84</abbr>, puis de <abbr>WGS84</abbr> vers <var>B</var>.
- Il suffirait ainsi de stocker dans chaque objet <code>GeodeticDatum</code> les informations nécessaires à la transformation vers <abbr>WGS84</abbr>.
- Cette approche était encouragée dans la version 1 du format <abbr>WKT</abbr>, qui définissait un élément <code>TOWGS84[…]</code> remplissant ce rôle.
- Cette approche est désignée par <abbr>EPSG</abbr> sous le nom de « early binding »
- car elle associe des informations sur la transformations de coordonnées très tôt dans la définition des objets géodésiques,
- souvent directement au moment de la construction d’un object <code>GeographicCRS</code>.
- Bien que <abbr>EPSG</abbr> reconnaisse que cette approche soit couramment employée, elle n’est pas recommandée pour plusieurs raisons:
- </p>
- <ul>
- <li>Il existe parfois plusieurs transformations allant d’un référentiel <var>A</var> vers <var>B</var>,
- chacune étant plus précise pour une région géographique donnée.</li>
- <li>Certaines opérations sont conçues spécifiquement pour transformer de <var>A</var> vers <var>B</var>
- et n’ont pas la même précision qu’aurait une autre transformation faisant un détour par <abbr>WGS84</abbr>.</li>
- <li><abbr>WGS84</abbr> lui-même subit parfois des révisions, ce qui en fait une cible mouvante (bien que très lentement)
- pour les bibliothèques de transformations de coordonnées.</li>
- <li>Il existe d’autres systèmes globaux qui pourraient servir de pivot, par exemple le <cite>Galileo Reference Frame</cite> (<abbr>GTRF</abbr>)
- mis en place par le concurrent européen du <abbr>GPS</abbr>.</li>
- </ul>
- <div class="example"><p><b>Exemple:</b>
- la base de données géodésiques <abbr>EPSG</abbr> définie une cinquantaine de transformations de <abbr>NAD27</abbr> vers <abbr>NAD83</abbr>.
- Dans une approche de type « early binding », le même système de référence « <abbr>NAD27</abbr> » représenté dans le format <abbr>WKT</abbr> 1
- aurait besoin d’être défini avec un élément <code>TOWGS84[-8, 160, 176]</code> pour des coordonnées aux États-Unis,
- ou avec un élément <code>TOWGS84[-10, 158, 187]</code> pour coordonnées aux Canada.
- Différents paramètres existent aussi pour d’autres régions telles que Cuba.
- Il n’est donc pas possible de représenter une telle diversité en associant un seul élément <code>TOWGS84[…]</code> à un système de référence des coordonnées.
- Même en restreignant l’usage d’un référenciel au domaine de validité de son élément <code>TOWGS84[…]</code>,
- ces transformations resteraient approximatives avec une précision de 10 mètres dans le cas des États-Unis.
- Des transformations plus précises existent sous la forme des grilles de changements de référentiel <abbr>NADCON</abbr>,
- mais ces grilles sont pour des transformations de <abbr>NAD27</abbr> vers <abbr>NAD83</abbr>
- (qui se déplacent ensemble sur la même plaque continentale) et non vers <abbr>WGS84</abbr> (qui se déplace indépendamment).
- Cette différence était souvent ignorée lorsque l’on considérait que <abbr>NAD83</abbr> et <abbr>WGS84</abbr>
- étaient pratiquement équivalents, mais cette supposition est aujourd’hui à prendre avec plus de précautions.
- </p></div>
- <p>
- <abbr>EPSG</abbr> recommande plutôt d’utiliser une approche dite « late binding »,
- selon laquelle les méthodes et paramètres nécessaires aux transformations de coordonnées sont définis pour des paires
- de référentiels « <var>A</var> vers <var>B</var> » (éventuellement complétées par leurs domaines de validité)
- plutôt qu’associés à des référentiels pris isolément.
- Apache <abbr>SIS</abbr> est une implémentation de type « late binding »,
- bien qu’une réminiscence de l’approche « early binding » existe toujours
- sous la forme de la propriété <code>DefaultGeodeticDatum.getBursaWolfParameters()</code>.
- <abbr>SIS</abbr> n’utilise cette dernière que comme solution de dernier recours
- s’il ne peut pas appliquer l’approche « late binding » avec les systèmes de références donnés.
- </p>
- </article>
-
- <h3 id="CoordinateSystem">Systèmes de coordonnées</h3>
- <p style="color: red">TODO</p>
-
- <h3 id="GeographicCRS">Systèmes géographiques</h3>
- <p style="color: red">TODO</p>
-
- <h4 id="GeographicWKT">Format <i>Well-Known Text</i></h4>
- <p style="color: red">TODO</p>
-
- <h3 id="ProjectedCRS">Projections cartographiques</h3>
- <p>
- Les projections cartographiques représentent une surface courbe (la Terre) sur une surface plane (une carte ou un écran d’ordinateur)
- en contrôlant les déformations: on peut préserver les angles ou les surfaces, mais pas les deux à la fois.
- Les propriétés géométriques à conserver dépendent de l’objet d’étude et du travail à effectuer.
- Par exemple les pays plutôt allongés dans le sens Est-Ouest utilisent souvent une projection de Lambert,
- alors que les pays plutôt allongés dans le sens Nord-Sud préfèrent une projection de Mercator Transverse.
- </p>
- <p style="color: red">TODO</p>
-
- <h4 id="ProjectedWKT">Format <i>Well-Known Text</i></h4>
- <p style="color: red">TODO</p>
-
- <h3 id="CompoundCRS">Dimensions verticales et temporelles</h3>
- <p style="color: red">TODO</p>
-
- <h4 id="CompoundWKT">Format <i>Well-Known Text</i></h4>
- <p style="color: red">TODO</p>
-
-
-
- <h2 id="GetCRS">Obtention d’un système de référence spatial</h2>
- <p style="color: red">TODO</p>
-
- <h3 id="CRSAuthorityFactory">Systèmes prédéfinis par des autorités</h3>
- <p style="color: red">TODO</p>
-
- <h3 id="CRSParsing">Lecture d’une définition au format GML ou WKT</h3>
- <p style="color: red">TODO</p>
-
- <h3 id="CRSFactory">Construction programmatique explicite</h3>
- <p style="color: red">TODO</p>
-
- <h3 id="CRS_UserCode">Ajout de définitions</h3>
- <p style="color: red">TODO</p>
-
-
-
- <h2 id="CoordinateOperation">Opérations sur les coordonnées</h2>
- <p style="color: red">TODO</p>
-
- <h3 id="MathTransform">Exécution de opérations</h3>
- <p style="color: red">TODO</p>
-
- <h4 id="AffineTransform">Les transformations affines</h4>
- <p>
- Parmi les sortes d’opérations qu’un <abbr>SIG</abbr> doit effectuer sur les coordonnées spatiales, il en est une à la fois simple et très fréquente.
- Ce sont les opérations linéaires, constituées uniquement d’une combinaison d’additions et de certaines multiplications.
- Ces opérations n’effectuent pas de projections cartographiques, plus complexes, mais couvrent de nombreux autres cas:
- </p>
- <ul>
- <li>Changer l’ordre des axes, par exemple de (<var>latitude</var>, <var>longitude</var>) vers (<var>longitude</var>, <var>latitude</var>).</li>
- <li>Changer la direction des axes (par exemple l’axe des <var>y</var> des images pointe souvent vers le bas).</li>
- <li>Changer de méridien d’origine (par exemple de <cite>Paris</cite> vers <cite>Greenwich</cite>).</li>
- <li>Changer le nombre de dimensions (par exemple passer des coordonnées 3D vers 2D).</li>
- <li>Convertir des unités de mesures (par exemple convertir des pieds en mètres).</li>
- <li>Convertir les coordonnées pixels d’une image en coordonnées géographiques
- (par exemple la conversion exprimée dans les fichiers <code>.tfw</code> qui accompagnent certaines images <abbr>TIFF</abbr>).</li>
- <li>Prendre en charge une petite partie des projections cartographiques
- (par exemple les paramètres <cite>False Easting</cite>, <cite>False Northing</cite> et <cite>Scale factor</cite>).</li>
- <li>Appliquer des rotations, translations, échelles ou cisaillements (des transformations dites <cite>affines</cite>).</li>
- </ul>
- <p>
- Les opérations linéaires peuvent se combiner efficacement:
- peu importe le nombre d’opérations linéaires que l’on enchaîne, le résultat sera exprimable par une seule opération linéaire.
- Cette propriété est plus facilement visible lorsque les opérations linéaires sont exprimées sous forme de matrices:
- pour combiner les opérations, il suffit de multiplier les matrices.
- </p>
- <div class="example"><p><b>Example:</b>
- supposons que nous disposons d’une image dont les coordonnées des pixels sont représentées par (<var>i</var>,<var>j</var>).
- Supposons que la taille de chaque pixel correspond à un nombre fixe de degrées de longitude et de latitude
- dans un système géographique donné et qu’il n’y a pas de rotation.
- La conversion des coordonnées pixels (<var>i</var>,<var>j</var>) vers les coordonnées géographiques (<var>λ</var>,<var>φ</var>)
- est alors linéaire et peut être représentée par la matrice suivante:</p>
-
- <table class="hidden"><tr><td>
- <xi:include href="../math/PixelToGeographic.html"/>
- </td><td style="vertical-align: middle; padding-left: 30px">
- où
- </td><td style="vertical-align: middle">
- <ul>
- <li><var>S</var> est un facteur d’échelle (<cite>Scale</cite>) correspondant dans cet exemple à la taille des pixels en degrés.</li>
- <li><var>H</var> est un terme de cisaillement (<cite>Shear</cite>), habituellement zéro sauf si l’image a une rotation.</li>
- <li><var>T</var> est une translation (<cite>Translation</cite>) correspondant dans cet exemple à la coordonnée géographique d’un coin de l’image.</li>
- </ul>
- </td></tr></table>
- <p>
- Concentrons notre attention sur la matrice du milieu dans l’équation ci-dessus.
- Si nous n’interchangeons ni n’inversons la direction d’aucun axe, alors une conversion des coordonnées pixels vers les coordonnées géographiques
- pourrait s’exprimer par la matrice « conversion originale » ci-dessous.
- Mais si l’on veut en outre inverser la direction de l’axe des <var>j</var> pour se conformer à la convention la plus courante appliquée aux images
- (« changement 1 ») et interchanger l’ordre des axes pour exprimer la latitude avant la longitude (« changement 2 »),
- alors on peut exprimer ces modifications par des multiplications matricielles comme suit
- (l’ordre dans laquelle les opérations sont effectuées sur les coordonnées se lit de droite à gauche):
- </p>
- <table class="hidden"><tr>
- <th>Changement 2</th><th></th>
- <th>Changement 1</th><th></th>
- <th>Conversion originale</th><th></th>
- <th>Conversion modifiée</th>
- </tr><tr>
- <td style="vertical-align: middle">
- <math xmlns="http://www.w3.org/1998/Math/MathML" display="block" alttext="MathML capable browser required">
- <mfenced open="[" close="]">
- <mtable>
- <mtr>
- <mtd><mn>0</mn></mtd>
- <mtd><mn>1</mn></mtd>
- <mtd><mn>0</mn></mtd>
- </mtr>
- <mtr>
- <mtd><mn>1</mn></mtd>
- <mtd><mn>0</mn></mtd>
- <mtd><mn>0</mn></mtd>
- </mtr>
- <mtr>
- <mtd><mn>0</mn></mtd>
- <mtd><mn>0</mn></mtd>
- <mtd><mn>1</mn></mtd>
- </mtr>
- </mtable>
- </mfenced>
- </math>
- </td>
- <td style="vertical-align: middle; padding-left: 15px; padding-right: 15px">×</td>
- <td style="vertical-align: middle">
- <math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
- <mfenced open="[" close="]">
- <mtable>
- <mtr>
- <mtd><mn>1</mn></mtd>
- <mtd><mn>0</mn></mtd>
- <mtd><mn>0</mn></mtd>
- </mtr>
- <mtr>
- <mtd><mn>0</mn></mtd>
- <mtd><mn>-1</mn></mtd>
- <mtd><mo>(</mo><msub><mi>j</mi><mrow>max</mrow></msub><mo>-</mo>
- <msub><mi>j</mi><mrow>min</mrow></msub><mo>)</mo></mtd>
- </mtr>
- <mtr>
- <mtd><mn>0</mn></mtd>
- <mtd><mn>0</mn></mtd>
- <mtd><mn>1</mn></mtd>
- </mtr>
- </mtable>
- </mfenced>
- </math>
- </td>
- <td style="vertical-align: middle; padding-left: 15px; padding-right: 15px">×</td>
- <td style="vertical-align: middle">
- <math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
- <mfenced open="[" close="]">
- <mtable>
- <mtr>
- <mtd><mfrac>
- <mrow>
- <msub><mi>λ</mi><mrow>max</mrow></msub><mo>-</mo>
- <msub><mi>λ</mi><mrow>min</mrow></msub>
- </mrow><mrow>
- <msub><mi>i</mi><mrow>max</mrow></msub><mo>-</mo>
- <msub><mi>i</mi><mrow>min</mrow></msub>
- </mrow>
- </mfrac></mtd>
- <mtd><mn>0</mn></mtd>
- <mtd><msub><mi>λ</mi><mrow>min</mrow></msub></mtd>
- </mtr>
- <mtr>
- <mtd><mn>0</mn></mtd>
- <mtd><mfrac>
- <mrow>
- <msub><mi>φ</mi><mrow>max</mrow></msub><mo>-</mo>
- <msub><mi>φ</mi><mrow>min</mrow></msub>
- </mrow><mrow>
- <msub><mi>j</mi><mrow>max</mrow></msub><mo>-</mo>
- <msub><mi>j</mi><mrow>min</mrow></msub>
- </mrow>
- </mfrac></mtd>
- <mtd><msub><mi>φ</mi><mrow>min</mrow></msub></mtd>
- </mtr>
- <mtr>
- <mtd><mn>0</mn></mtd>
- <mtd><mn>0</mn></mtd>
- <mtd><mn>1</mn></mtd>
- </mtr>
- </mtable>
- </mfenced>
- </math>
- </td>
- <td style="vertical-align: middle; padding-left: 15px; padding-right: 15px">=</td>
- <td style="vertical-align: middle">
- <math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
- <mfenced open="[" close="]">
- <mtable>
- <mtr>
- <mtd><mn>0</mn></mtd>
- <mtd><mo>-</mo><mfrac>
- <mrow>
- <msub><mi>φ</mi><mrow>max</mrow></msub><mo>-</mo>
- <msub><mi>φ</mi><mrow>min</mrow></msub>
- </mrow><mrow>
- <msub><mi>j</mi><mrow>max</mrow></msub><mo>-</mo>
- <msub><mi>j</mi><mrow>min</mrow></msub>
- </mrow>
- </mfrac></mtd>
- <mtd><msub><mi>φ</mi><mrow>max</mrow></msub></mtd>
- </mtr>
- <mtr>
- <mtd><mfrac>
- <mrow>
- <msub><mi>λ</mi><mrow>max</mrow></msub><mo>-</mo>
- <msub><mi>λ</mi><mrow>min</mrow></msub>
- </mrow><mrow>
- <msub><mi>i</mi><mrow>max</mrow></msub><mo>-</mo>
- <msub><mi>i</mi><mrow>min</mrow></msub>
- </mrow>
- </mfrac></mtd>
- <mtd><mn>0</mn></mtd>
- <mtd><msub><mi>λ</mi><mrow>min</mrow></msub></mtd>
- </mtr>
- <mtr>
- <mtd><mn>0</mn></mtd>
- <mtd><mn>0</mn></mtd>
- <mtd><mn>1</mn></mtd>
- </mtr>
- </mtable>
- </mfenced>
- </math>
- </td>
- </tr></table>
- <p>
- L’idée principale est qu’il n’y a pas besoin d’écrire un code dédié à l’inversion des axes.
- Cette opération, et bien d’autres, est prise en compte naturellement par l’algèbre matricielle.
- On y gagne en généricité du code et en performance.
- </p>
- </div>
-
- <p style="color: red">TODO</p>
-
- <article>
- <header>
- <h1>Particularités d’une bibliothèque de calculs matriciels pour un <abbr>SIG</abbr></h1>
- </header>
- <p>
- Les <abbr>SIG</abbr> font un usage intensif de matrices afin d’afficher leurs cartes ou transformer des coordonnées.
- On pourrait croire que le marché est suffisamment bien pourvu en excellentes bibliothèques de calculs matriciels, libres ou commerciales.
- Pourtant, les <abbr>SIG</abbr> ont des besoins spécifiques qui divergent un peu des objectifs de plusieurs bibliothèques existantes.
- Des manipulations de matrices comme l’exemple précédent interviennent dans quasiment toutes les opérations
- appliquées par Apache <abbr>SIS</abbr> sur des coordonnées.
- Mais l’analyse de ces opérations révèle quelques patterns:
- </p>
- <ul>
- <li><p>Ces matrices sont presque toujours de petites tailles, dépassant rarement 5 lignes par 5 colonnes.</p></li>
- <li><p>Les opérations matricielles « lourdes » (multiplications ou inversions de matrices) ne surviennent pas dans des endroits où la performance est importante.
- Dans la quasi-totalité des cas, elles ne sont effectuées qu’une fois pour toute, à la lecture d’un fichier,
- ou lors des étapes de préparation avant de convertir des coordonnées.
- Elles ne surviennent quasiment jamais dans la boucle convertissant chacune des coordonnées.</p></li>
- <li><p>Dans une succession de multiplications et d’inversions de matrices, les erreurs d’arrondissement s’accumulent et grandissent rapidement
- au point de se confondre avec certaines opérations légitimes, notamment les changements de référentiel.
- Ces dernières s’expriment souvent par un changement de la taille, position et orientation de l’ellipsoïde
- choisi comme approximation de la forme de la Terre. Les changements de la taille s’expriment en parties par million et
- les rotations en arc-secondes. Retranscrites dans une matrice, ces valeurs sont donc assez petites.</p></li>
- <li><p>Il arrive fréquemment que des matrices s’annulent en tout ou en partie,
- c’est-à-dire que leurs multiplications ramènent des facteurs d’échelles à 1 et des translations à 0.
- Toutefois les erreurs d’arrondissements font que les valeurs obtenues sont rarement exactes,
- mais plutôt des valeurs s’en rapprochant telles que 0,9999…97 à la place de 1.
- Malheureusement, les erreurs d’arrondissement sont parfois telles qu’il est difficile de savoir
- si certains coefficients de la matrices sont des artefacts ou proviennent d’un réel changement de référentiel.</p></li>
- </ul>
- <p>
- Ces points font que, pour un <abbr>SIG</abbr>, la précision d’une bibliothèque de calculs matriciels
- est plus importante que la performance. Paradoxalement, un bon moyen de gagner en performance est justement d’investir davantage de temps de CPU
- pour effectuer des opérations matricielles plus précises, car on augmente ainsi les chances de détecter correctement quelles opérations s’annulent.
- L’effort investit dans cette détection permet de sauver du temps là où ça compte: quand viendra le moment de boucler sur des millions de coordonnées à transformer.
- </p><p>
- Mais les bibliothèques dédiées aux calculs matriciels sont souvent conçues pour opérer de manière très performante
- sur des matrices de grandes tailles, ayant par exemple des milliers de lignes et colonnes.
- Elles sont ainsi conçues pour être capable de résoudre efficacement des systèmes d’équations linéaires comportant des centaines d’inconnues.
- Les problèmes qu’elles résolvent sont certes difficiles, mais assez différents de ceux qui intéressent Apache <abbr>SIS</abbr>.
- Pour cette raison, et aussi à cause d’un autre besoin spécifique détaillé dans les paragraphes suivants,
- Apache <abbr>SIS</abbr> utilise ses propres fonctions de calculs matriciels.
- Ces fonctions tentent de résoudre le problème de précision en utilisant l’arithmétique « double-double »
- (une technique permettant de simuler une précision d’environ 120 bits)
- au prix de la performance dans une partie du code où elle n’est pas jugée critique.
- </p>
- <h2>Que faire des matrices qui ne sont pas carrées (et pourquoi)</h2>
- <p>
- Apache <abbr>SIS</abbr> a très souvent besoin d’inverser des matrices,
- afin d’obtenir une conversion de coordonnées qui fasse le contraire de la conversion originale.
- Mais on n’inverse habituellement que des matrices carrées.
- Or, Apache <abbr>SIS</abbr> a besoin d’effectuer des inversions de matrices non-carrées.
- Selon que l’on ait plus de lignes ou plus de colonnes:
- </p>
- <ul>
- <li>Pour <abbr>SIS</abbr>, une matrice non-carrée est une conversion qui ajoute ou supprime une dimension aux coordonnées.</li>
- <li>Pour les bibliothèques d’algèbre linéaire, une matrice non-carrée est un système d’équations sous-déterminé ou surdéterminé.</li>
- </ul>
- <p>
- Pour mieux comprendre les difficultés que causerait une transposition trop directe des bibliothèques d’algèbre linéaire aux <abbr>SIG</abbr>,
- imaginons une conversion qui projetterait les points d’un espace 3D vers une surface 2D:
- </p>
- <table class="hidden">
- <tr>
- <td>(λ₁, φ₁, <var>h</var>) → (λ₂, φ₂)</td>
- <td style="padding-left: 30px">où</td>
- <td><ul style="margin-top: 0">
- <li>λ est la longitude.</li>
- <li>φ est la latitude.</li>
- <li>(λ₂, φ₂) n’égale pas forcement (λ₁, φ₁) si la hauteur <var>h</var> n’est pas perpendiculaire à la surface.</li>
- </ul></td>
- </tr>
- </table>
- <p>
- Pour des bibliothèques d’algèbre linéaire, la matrice représentant cette conversion serait un système d’équations sous-déterminé, et donc insoluble.
- C’est-à-dire qu’on ne peut pas inverser cette conversion pour obtenir (λ₂, φ₂) → (λ₁, φ₁, <var>h</var>) puisqu’on ne sait pas quelle valeur donner à <var>h</var>,
- ce qui implique qu’on ne peut pas trouver (λ₁, φ₁) non-plus car ces valeurs dépendent peut-être de <var>h</var>.
- Toutefois, dans le cas des <abbr>SIG</abbr>, l’axe des <var>h</var> est très souvent perpendiculaire à la surface sur laquelle sont exprimées les coordonnées (<var>λ</var>,<var>φ</var>).
- Cette perpendicularité rend λ₁ et φ₁ indépendants de <var>h</var>. Dans ce cas particulier, et ce cas seulement, on peut encore sauver les meubles.
- </p><p>
- Apache <abbr>SIS</abbr> procède en vérifiant si les coordonnées <var>h</var> sont indépendantes des coordonnées λ et φ.
- Nous reconnaissons ce cas en vérifiant quels coefficients de la matrice ont la valeur zéro.
- Si <abbr>SIS</abbr> arrive à identifier des dimensions indépendantes,
- il peut les exclure temporairement de manière à inverser sans ambiguïté la conversion dans les dimensions restantes.
- S’il ne trouve pas de dimension indépendante, alors une exception est levée.
- </p><p>
- Si une inversion a été possible, alors il reste à décider du sort des dimensions que <abbr>SIS</abbr> avait temporairement exclues.
- Dans notre exemple, <abbr>SIS</abbr> assignera la valeur <code>NaN</code> (<cite>Not-a-Number</cite>) aux valeurs de <var>h</var> dans la conversion (λ₂, φ₂) → (λ₁, φ₁, <var>h</var>).
- Là encore, le choix du coefficient à mettre à <code>NaN</code> dans la matrice est basé sur la présomption qu’elle représente une conversion de coordonnées.
- </p><p>
- Le traitement particulier fait par <abbr>SIS</abbr> permet donc d’inverser des matrices que l’on rencontre couramment dans les <abbr>SIG</abbr>,
- même si en principe le système est sous-déterminé.
- Dans notre exemple la coordonnée <var>h</var> reste inconnue – nous ne faisons pas surgir de l’information du néant – mais au moins les coordonnées (<var>λ</var>,<var>φ</var>) ont pu être récupérées.
- </p><p>
- Le problème inverse, celui des systèmes surdéterminés, est plus subtil.
- Une approche classique des bibliothèques d’algèbre linéaire est de résoudre les systèmes surdéterminés par la méthode des moindres carrées.
- Transposée à notre exemple, cette approche proposerait une conversion (λ₂, φ₂, <var>h</var>) → (λ₁, φ₁)
- qui semble le meilleur compromis pour diverses valeurs de λ₂, φ₂ et <var>h</var>, tout en n’étant (sauf cas particuliers) une solution exacte pour personne.
- De plus, les éventuelles combinaisons linéaires entre ces trois variables sont délicates compte tenu de l’hétérogénéité des unités de mesures,
- où les <var>h</var> sont en mètres et (<var>λ</var>,<var>φ</var>) en degrés.
- Apache <abbr>SIS</abbr> procède plutôt comme pour les systèmes sous-déterminés: en exigeant que certaines dimensions soient indépendantes des autres,
- faute de quoi la matrice sera considérée non-inversible.
- Dans le cas des systèmes surdéterminés <abbr>SIS</abbr> refusera donc d’effectuer certaines opérations que les bibliothèques d’algèbre linéaire auraient faite,
- mais garantira que les conversions obtenues seront exactes (aux erreurs d’arrondissement prêts).
- </p>
- <p>
- En résumé, les besoins qui ont amené Apache <abbr>SIS</abbr> à fournir ses propres fonctions de calculs matriciels sont:
- </p>
- <ul>
- <li>Structure légère pour les petites matrices, particulièrement celles de taille 3×3.</li>
- <li>Précision accrue avec l’arithmétique « double-double », quitte à sacrifier un peu de performance dans des endroits où elle n’est pas critique.</li>
- <li>Traitement particulier de l’inversion des matrices non-carrées pour des conversions de coordonnées.</li>
- </ul>
- </article>
-
- <h3 id="TransformDerivative">Dérivées partielles des opérations</h3>
- <p>
- La section précédente indiquait comment calculer les coordonnées d’un point géographique dans une projection au choix.
- Mais il existe une autre opération moins connue, qui consiste à calculer non pas la <em>coordonnées projetée</em> d’un point,
- mais plutôt la <em>dérivée de la fonction de projection cartographique</em> en ce point.
- Cette opération était définie dans une ancienne spécification du consortium Open Geospatial,
- <a href="http://www.opengeospatial.org/standards/ct">OGC 01-009</a>, aujourd’hui un peu oubliée mais pourtant encore utile.
- </p>
-
- <p>
- Appelons <var>P</var> une projection cartographique qui convertit une longitude et latitude (<var>λ</var>,<var>φ</var>) en degrés
- vers une coordonnée projetée (<var>x</var>,<var>y</var>) en mètres.
- Dans l’expression ci-dessous, nous représentons le résultat de la projection cartographique
- sous forme d’une matrice colonne (la raison sera plus claire bientôt):
- </p>
-
- <math xmlns="http://www.w3.org/1998/Math/MathML" display="block" alttext="MathML capable browser required">
- <mi>P</mi><mo>(</mo><mi>λ</mi><mo>,</mo><mi>φ</mi><mo>)</mo>
- <mo>=</mo>
- <mfenced open="[" close="]">
- <mtable>
- <mtr><mtd><mi>x</mi><mo>(</mo><mi>λ</mi><mo>,</mo><mi>φ</mi><mo>)</mo></mtd></mtr>
- <mtr><mtd><mi>y</mi><mo>(</mo><mi>λ</mi><mo>,</mo><mi>φ</mi><mo>)</mo></mtd></mtr>
- </mtable>
- </mfenced>
- </math>
-
- <p>La dérivée de la projection cartographique en ce même point peut se représenter par la matrice Jacobienne définie tel que:</p>
-
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block" alttext="MathML capable browser required">
- <msup><mi>P</mi><mo>′</mo></msup><mo>(</mo><mi>λ</mi><mo>,</mo><mi>φ</mi><mo>)</mo>
- <mo>=</mo>
- <msub><mi>JAC</mi><mrow><mi>P</mi><mo>(</mo><mi>λ</mi><mo>,</mo><mi>φ</mi><mo>)</mo></mrow></msub>
- <mo>=</mo>
<mfenced open="[" close="]">
<mtable>
<mtr>
- <mtd><mfrac><mrow><mo>∂</mo><mi>x</mi><mo>(</mo><mi>λ</mi><mo>,</mo><mi>φ</mi><mo>)</mo></mrow><mrow><mo>∂</mo><mi>λ</mi></mrow></mfrac></mtd>
- <mtd><mfrac><mrow><mo>∂</mo><mi>x</mi><mo>(</mo><mi>λ</mi><mo>,</mo><mi>φ</mi><mo>)</mo></mrow><mrow><mo>∂</mo><mi>φ</mi></mrow></mfrac></mtd>
+ <mtd><mn>0</mn></mtd>
+ <mtd><mn>1</mn></mtd>
+ <mtd><mn>0</mn></mtd>
</mtr>
<mtr>
- <mtd><mfrac><mrow><mo>∂</mo><mi>y</mi><mo>(</mo><mi>λ</mi><mo>,</mo><mi>φ</mi><mo>)</mo></mrow><mrow><mo>∂</mo><mi>λ</mi></mrow></mfrac></mtd>
- <mtd><mfrac><mrow><mo>∂</mo><mi>y</mi><mo>(</mo><mi>λ</mi><mo>,</mo><mi>φ</mi><mo>)</mo></mrow><mrow><mo>∂</mo><mi>φ</mi></mrow></mfrac></mtd>
+ <mtd><mn>1</mn></mtd>
+ <mtd><mn>0</mn></mtd>
+ <mtd><mn>0</mn></mtd>
+ </mtr>
+ <mtr>
+ <mtd><mn>0</mn></mtd>
+ <mtd><mn>0</mn></mtd>
+ <mtd><mn>1</mn></mtd>
</mtr>
</mtable>
</mfenced>
</math>
-
- <p>
- Dans la suite de ce texte nous abrégerons ∂<var>x</var>(<var>λ</var>,<var>φ</var>) par ∂<var>x</var> et de même pour ∂<var>y</var>,
- mais il faut garder à l’esprit que chacune de ces valeurs dépendent de la coordonnée (<var>λ</var>,<var>φ</var>) originale.
- Le premier élément de la matrice (∂<var>x</var>/∂<var>λ</var>) nous indique à quel déplacement vers l’Est
- (<var>x</var> en mètres) correspond un déplacement de un degré de longitude (<var>λ</var>).
- De même, le dernier élément de la matrice (∂<var>y</var>/∂<var>φ</var>) nous indique à quel déplacement vers le Nord
- (<var>y</var> en mètres) correspond un déplacement de un degré de latitude (<var>φ</var>).
- Les autres éléments (∂<var>x</var>/∂<var>φ</var> et ∂<var>y</var>/∂<var>λ</var>) sont des termes croisés (par exemple à quel déplacement
- en mètres vers le <em>Nord</em> correspond un déplacement de un degré de <em>longitude</em>).
- Ces valeurs ne sont généralement valides qu’à la position géographique (<var>λ</var>,<var>φ</var>) donnée.
- Si on se déplace un peu, ces valeurs changent légèrement.
- Cette matrice nous donne toutefois une bonne idée du comportement de la projection dans le voisinage du point projeté.
- </p>
-
- <p>
- On peut se représenter visuellement cette matrice comme ci-dessous.
- Cette figure représente la dérivée en deux points, <var>P</var><sub>1</sub> et <var>P</var><sub>2</sub>,
- pour mieux illustrer le fait que le résultat varie en chaque point.
- Dans cette figure, les vecteurs <var>U</var> et <var>V</var> désignent respectivement
- la première et deuxième colonne des matrices de dérivées.
- </p>
-
- <table class="hidden"><tr>
- <td><img style="border: solid 1px" src="../images/Derivatives.png" alt="Exemple de dérivées d’une projection cartographique"/></td>
- <td style="padding-left: 30px; vertical-align: middle">
- <p>où les vecteurs sont reliés à la matrice par:</p>
- <math xmlns="http://www.w3.org/1998/Math/MathML" display="block" alttext="MathML capable browser required">
- <mtable><mtr>
- <mtd>
- <mover><mi>U</mi><mo>→</mo></mover><mo>=</mo>
- <mfenced open="[" close="]">
- <mtable>
- <mtr>
- <mtd><mfrac><mrow><mo>∂</mo><mi>x</mi></mrow><mrow><mo>∂</mo><mi>λ</mi></mrow></mfrac></mtd>
- </mtr>
- <mtr>
- <mtd><mfrac><mrow><mo>∂</mo><mi>y</mi></mrow><mrow><mo>∂</mo><mi>λ</mi></mrow></mfrac></mtd>
- </mtr>
- </mtable>
- </mfenced>
- </mtd>
- <mtd><mtext>et</mtext></mtd>
- <mtd>
- <mover><mi>V</mi><mo>→</mo></mover><mo>=</mo>
- <mfenced open="[" close="]">
- <mtable>
- <mtr>
- <mtd><mfrac><mrow><mo>∂</mo><mi>x</mi></mrow><mrow><mo>∂</mo><mi>φ</mi></mrow></mfrac></mtd>
- </mtr>
- <mtr>
- <mtd><mfrac><mrow><mo>∂</mo><mi>y</mi></mrow><mrow><mo>∂</mo><mi>φ</mi></mrow></mfrac></mtd>
- </mtr>
- </mtable>
- </mfenced>
- </mtd>
- </mtr></mtable>
- </math>
- </td>
- </tr></table>
-
- <p>
- Cette figure nous montre déjà une utilisation possible des dérivées:
- elles donnent la direction des parallèles et des méridiens à une position donnée dans une projection cartographique.
- Par extension, on peut aussi s’en servir pour déterminer si des axes sont interchangés,
- ou si la direction d’un axe est renversée. Mais l’intérêt des dérivées ne s’arrête pas là.
- </p>
-
- <h4 id="DerivativeAndEnvelope">Utilité des dérivées pour la reprojection d’enveloppes</h4>
- <p>
- Les systèmes d’information géographiques ont très fréquemment besoin de projeter une enveloppe.
- Mais l’approche naïve, qui consisterait à projeter chacun des 4 coins du rectangle, ne suffit pas.
- La figure ci-dessous montre une enveloppe avant le projection, et la forme géométrique que l’on obtiendrait
- si on projetait finement l’enveloppe (pas seulement les 4 coins). Cette forme géométrique est plus complexe
- qu’un simple rectangle à cause des courbures induites par la projection cartographique.
- Construire une enveloppe rectangulaire qui engloberait les 4 coins de cette forme géométrique ne suffit pas,
- car la surface en bas de la forme est plus basse que les 2 coins du bas.
- Cette surface serait donc en dehors du rectangle.
- </p>
- <table class="hidden">
- <tr>
- <th>Enveloppe avant la projection</th>
- <th>Forme géométrique après la projection</th>
- </tr>
- <tr>
- <td><img style="border: solid 1px; margin-right: 15px" src="../images/GeographicArea.png" alt="Envelope in a geographic CRS"/></td>
- <td><img style="border: solid 1px; margin-left: 15px" src="../images/ConicArea.png" alt="Shape in a projected CRS"/></td>
- </tr>
- </table>
- <p>
- Une façon simple d’atténuer le problème est d’échantillonner un plus grand nombre de points sur chacun des
- bords de la forme géométrique. On trouve ainsi des bibliothèques de <abbr>SIG</abbr> qui vont par exemple
- échantillonner 40 points sur chaque bord, et construire un rectangle qui englobe tout ces points.
- Mais même avec 40 points, les échantillons les plus proches peuvent encore être légèrement à côté du point le plus bas de la figure.
- Une petite portion de la forme géométrique peut donc toujours se trouver en dehors du rectangle.
- Il est tentant de considérer cette légère erreur comme négligeable, mais quelques pixels manquants
- entraînent divers artefacts comme une apparence de quadrillage lors de l’affichage d’images tuilées,
- ou une “pointe de tarte” manquante lors de la projection d’images sur un pôle.
- Augmenter artificiellement d’un certain pourcentage la taille de l’enveloppe projetée peut éliminer ces artefacts dans certains cas.
- Mais un pourcentage trop élevé fera traiter plus de données que nécessaire
- (en particulier lorsque cela entraîne le chargement de nouvelles tuiles d’images),
- alors qu’un pourcentage trop faible laissera quelques artefacts.
- </p><p>
- Les dérivées des projections cartographiques permettent de résoudre ce problème d’une manière plus efficace que la force brute.
- La figure ci-dessous reprend la forme projetée en exagérant des déformations.
- L’approche consiste à calculer la projection cartographiques des 4 coins comme dans l’approche naïve,
- mais en récupérant aussi les dérivées de la projection de ces 4 coins.
- Entre deux coins et avec leurs dérivées, on peut faire passer une et une seule courbe cubique
- (de la forme <i>f(<var>x</var>)</i> = <var>C</var>₀ + <var>C</var>₁<var>x</var> + <var>C</var>₂<var>x</var>² + <var>C</var>₃<var>x</var>³),
- dont on peut calculer les coefficients <var>C</var>.
- Cette approximation (représentée en rouge ci-dessous) ne correspond pas tout-à-fait à la courbe désirée (en bleue) mais s’en rapproche.
- Ce qui nous intéresse n’est pas vraiment les valeurs de l’approximation, mais plutôt la position de son minimum,
- en particulier la longitude λ où se trouve ce minimum dans notre exemple (ligne pointillée verte).
- L’avantage est que la position du minimum d’une courbe cubique est facile à calculer lorsque l’on connaît les valeurs de <var>C</var>.
- En supposant que la longitude du minimum de la courbe cubique est proche de la longitude du minimum de la courbe réelle,
- il suffit de calculer la projection cartographique d’un point à cette longitude plutôt que d’échantillonner 40 points sur le bord de l’enveloppe.
- </p>
- <table class="hidden"><tr><td>
- <img src="../images/Approximation.png" alt="Approximation cubique d’un bord d’une enveloppe"/>
- </td><td style="padding-left: 60px">
- Légende:
- <ul>
- <li><b>En bleue:</b> la forme géométrique correspondant à la projection de l’enveloppe.
- C’est la forme dont on souhaite avoir le rectangle englobant.</li>
- <li><b>En rouge</b> (sous les hachures): L’approximation
- <var>y</var> = <var>C</var>₀ + <var>C</var>₁λ + <var>C</var>₂λ² + <var>C</var>₃λ³.</li>
- <li><b>En vert</b> (pointillés): La position λ<sub>m</sub> du minimum de l’approximation, trouvée en résolvant
- 0 = <var>C</var>₁ + 2<var>C</var>₂λ<sub>m</sub> + 3<var>C</var>₃λ<sub>m</sub>².
- Il peut y avoir jusqu’à deux minimums pour une même courbe cubique.</li>
- </ul>
- </td></tr></table>
- <p>
- Dans la pratique Apache <abbr>SIS</abbr> utilise 8 points, soit les 4 coins plus un point au centre de chaque bord du rectangle à projeter,
- afin de réduire le risque d’erreur qu’induirait une courbe trop tordue entre deux points.
- Selon nos tests, l’utilisation de ces seuls 8 points avec leurs dérivées comme décrit ci-haut
- donne un résultat plus précis que l’approche « force brute » utilisant un échantillonnage de 160 points sur les 4 bords du rectangle.
- La précision de <abbr>SIS</abbr> pourrait être encore améliorée en répétant le processus à partir du minimum trouvée
- (une ou deux itérations suffiraient peut-être).
- </p><p>
- Une économie de 150 points n’est pas énorme vu les performances des ordinateurs d’aujourd’hui.
- Mais toute la discussion précédente utilisait une forme géométrique à deux dimensions en guise d’exemple,
- alors que l’algorithme est applicable dans un espace à <var>n</var> dimensions.
- Et de fait, l’implémentation de Apache SIS fonctionne pour un nombre arbitraire de dimensions.
- Les économies apportées par cet algorithme par rapport à la force brute augmentent de manière exponentielle avec le nombre de dimensions.
- </p><p>
- L’approche décrite dans cette section est implémentée dans Apache <abbr>SIS</abbr>
- par la méthode statique <code>Envelopes.transform(CoordinateOperation, Envelope)</code>.
- Une méthode <code>Envelopes.transform(MathTransform, Envelope)</code> existe aussi comme alternative,
- mais cette dernière ne devrait être utilisée que si on ne connaît pas l’objet <code>CoordinateOperation</code> utilisé.
- La raison est que les objets de type <code>MathTransform</code> ne contiennent pas d’information sur le système de coordonnées sous-jasent,
- ce qui empêche la méthode <code>Envelopes.transform(…)</code> de savoir comment gérer les points aux pôles.
- </p>
-
-
- <h4 id="DerivativeAndRaster">Utilité des dérivées pour la reprojection d’images</h4>
- <p>
- La projection cartographique d’une image s’effectue en préparant une image initialement vide qui contiendra le résultat de l’opération,
- puis à remplir cette image en itérant sur tous les pixels. Pour chaque pixel de l’image <em>destination</em>, on obtient la coordonnées
- du pixel correspondant dans l’image source en utilisant <em>l’inverse</em> de la projection cartographique que l’on souhaite appliquer.
- La position obtenue ne sera pas nécessairement au centre du pixel de l’image source, ce qui implique qu’une interpolation de la valeur
- (ou de la couleur dans l’image ci-dessous) peut être nécessaire.
- </p>
- <table class="hidden">
- <tr>
- <th style="text-align: left">Image source</th>
- <th style="text-align: right">Image destination</th>
- </tr>
- <tr>
- <td colspan="2"><img src="../images/RasterProjection.png" alt="Intersection of derivatives"/></td>
- </tr>
- </table>
- <p>
- Toutefois, calculer la projection inverse pour chacun des pixels peut être relativement lent.
- Afin d’accélérer les calculs, on utilise parfois une <cite>grille d’interpolation</cite>
- dans laquelle on a pré-calculé les <em>coordonnées</em> de la projection inverse de seulement quelques points.
- Les coordonnées des autres points se calculent alors par des interpolations bilinéaires entre les points pré-calculés,
- calculs qui pourraient éventuellement tirer parti d’accélérations matérielles sous forme de <cite>transformations affines</cite>.
- Cette approche est implémentée par exemple dans la bibliothèque <cite>Java Advanced Imaging</cite> avec l’objet <code>WarpGrid</code>.
- Elle offre en outre l’avantage de permettre de réutiliser la grille autant de fois que l’on veut si on a plusieurs images de même
- taille à projeter aux mêmes coordonnées géographiques.
- </p><p>
- Mais une difficulté de cette approche est de déterminer combien de points il faut pré-calculer pour que l’erreur
- (la différence entre une position interpolée et la position réelle) ne dépasse pas un certain seuil (par exemple ¼ de pixel).
- On peut procéder en commençant par une grille de taille 3×3, puis en augmentant le nombre de points de manière itérative:
- </p>
- <table class="hidden"><tr>
- <td><img src="../images/WarpGrid.png" alt="Intersection of derivatives"/></td>
- <td style="padding-left: 60px">
- Légende:
- <ul>
- <li><b>Points bleus:</b> première itération (9 points).</li>
- <li><b>Points verts:</b> seconde itération (25 points, dont 16 nouveaux).</li>
- <li><b>Points rouges:</b> troisième itération (81 points, dont 56 nouveaux).</li>
- </ul>
- Si l’on continue…
- <ul>
- <li>Quatrième itération: 289 points, dont 208 nouveaux.</li>
- <li>Cinquième itération: 1089 points, dont 800 nouveaux.</li>
- <li>Sixième itération: 4225 points, dont 3136 nouveaux.</li>
- <li>…</li>
- </ul>
- </td></tr></table>
- <p>
- L’itération s’arrête lorsque, après avoir calculé de nouveaux points, on a vérifié que la différence entre les
- coordonnées projetées et les coordonnées interpolées de ces nouveaux points est inférieure au seuil qu’on s’est fixé.
- Malheureusement cette approche nous permet seulement de déterminer <strong>après</strong> avoir calculé de nouveaux points…
- que ce n’était pas la peine de les calculer. C’est un peu dommage vu que le nombre de nouveaux points requis par chaque itération
- est environ 3 fois la <em>somme</em> du nombre de nouveaux points de <em>toutes</em> les itérations précédentes.
- </p><p>
- Les dérivées des projections cartographiques nous permettent d’améliorer cette situation en estimant
- si c’est la peine d’effectuer une nouvelle itération <strong>avant</strong> de la faire.
- L’idée de base est de vérifier si les dérivées de deux points voisins sont presque pareilles,
- auquel cas on présumera que la transformation entre ces deux points est pratiquement linéaire.
- Pour quantifier « presque pareil », on procède en calculant l’intersection entre les tangentes aux deux points
- (une information fournie par les dérivées), et en calculant la distance entre cette intersection et la droite
- qui relie les deux points (la ligne pointillée dans la figure ci-dessous).
- </p>
- <p style="text-align:center"><img style="border: solid 1px" src="../images/IntersectionOfDerivatives.png" alt="Intersection of derivatives"/></p>
- <p>
- Dans l’approche sans dérivées, l’itération s’arrête lorsque la distance entre la ligne pointillée (positions interpolées)
- et la ligne rouge (positions projetées) est inférieure au seuil de tolérance, ce qui implique de calculer la position projetée.
- Dans l’approche avec dérivées, on remplace la position projetée par l’intersection des deux tangentes (carré bleu foncé).
- Si la courbe n’est pas trop tordue – ce qui ne devrait pas être le cas entre deux points suffisamment proches –
- la courbe réelle passera à quelque part entre la droite pointillée et l’intersection.
- On s’évite ainsi des projections cartographiques, en apparence une seule dans cette illustration,
- mais en fait beaucoup plus dans une grille de transformation d’image (3× la somme des itérations précédentes).
- </p>
-
- <h4 id="GetDerivative">Obtention de la dérivée en un point</h4>
- <p>
- Cette discussion n’aurait pas un grand intérêt si le coût du calcul des dérivées des projections cartographiques
- était élevé par rapport aux coût de la projection des points. Mais lorsque l’on dérive analytiquement les équations
- des projections, on constate que les calculs des positions et de leurs dérivées ont souvent plusieurs termes en commun.
- En outre le calcul des dérivées est simplifié lorsque le code Java effectuant les projections ne se concentre que sur le « noyau » non-linéaire,
- après s’être déchargé des parties linéaires en les déléguant aux transformations affines comme le fait <abbr>SIS</abbr>.
- Les implémentations des projections cartographiques dans Apache <abbr>SIS</abbr> tirent parti de ces propriétés
- en ne calculant les dérivées que si elles sont demandées,
- et en offrant une méthode qui permet de projeter un point et obtenir sa dérivée en une seule opération
- afin de permettre à <abbr>SIS</abbr> de réutiliser un maximum de termes communs.
- Exemple:</p>
-
-<pre>AbstractMathTransform projection = ...; // Une projection cartographique de Apache SIS.
-double[] sourcePoint = {longitude, latitude}; // La coordonnée géographique que l’on veut projeter.
-double[] targetPoint = new double[2]; // Là où on mémorisera le résultat de la projection.
-Matrix derivative = projection.<code class="SIS">transform</code>(sourcePoint, 0, targetPoint, 0, true);</pre>
-
- <p>
- Si seule la matrice Jacobienne est désirée (sans la projection du point), alors la méthode
- <code>MathTransform.derivative(DirectPosition)</code> offre une alternative plus lisible.
- </p><p>
- Apache <abbr>SIS</abbr> est capable combiner les dérivées des projections cartographiques de la même façon que pour les projections de coordonnées:
- concaténation d’une chaîne de transformations, inversion, opérer sur un sous-ensemble des dimensions, <i>etc.</i>
- Les opérations inverses (des systèmes projetés vers géographiques)
- sont souvent beaucoup plus compliquées à implémenter que les opérations originales (des systèmes géographiques vers projetés),
- mais par chance la matrice Jacobienne d’une fonction inverse est simplement l’inverse de la matrice Jacobienne de la fonction originale.
- Une fonction inverse peut donc implémenter le calcul de sa dérivée comme suit:
- </p>
-<pre>@Override
-public Matrix derivative(DirectPosition p) throws TransformException {
- Matrix jac = inverse().derivative(transform(p));
- return Matrices.inverse(jac);
-}
-</pre>
</body>
</html>