RECALAGE RIGIDE DE RELEVÉS LASER PAR MISE EN
CORRESPONDANCE ROBUSTE BASÉE SUR DES SEGMENTS

Martyna Poreba¹, François Goulette¹

1 : CAOR Centre de Robotique, Mathématiques et Systèmes, MINES ParisTech, 60, Bd Saint Michel, 75272 Paris
(martyna.poreba,francois.goulette@mines-paristech.fr)

Résumé

Le recalage se révèle indispensable pour assembler des relevés laser devant servir à l'analyse, à la documentation et à la reconstruction tridimensionnelle d'environnements. Ce problème apparaît lorsqu'une zone d'intérêt est numérisée, au fil du temps, deux ou plusieurs fois, ou quand sa complexité nécessite un accroissement du nombre de stations de scanner laser fixes. Aussi, en raison de la variété des techniques disponibles d'acquisition, l'intégration multi-données devient une question importante puisqu'elle permet de mettre en cohérence des données contenant souvent une information complé- mentaire. La vaste majorité des algorithmes existants s'appuient sur les éléments ponctuels. C'est pourquoi les méthodes ICP basées-point demeurent actuellement les plus répandues. Cet article propose l'utilisation des segments sous forme d'intersections entre les plans principaux, pour un recalage rigide des nuages de points mobiles avec d'autres données, qu'elles soient 2D ou 3D. Ces primitives peuvent être aisément extraites, même dans les données laser hétérogènes de faible densité. Quelques méthodes de recalage basées-lignes ont été examinées afin de vérifier leur précision et robustesse au bruit. Les erreurs des paramètres estimés ainsi qu'un nouveau critère – distance modifiée de Hausdorff ont été employés pour les besoins d'une analyse quantitative. Au vu de ces éléments, une chaîne complète nommée RLMR-FMII₂ comprenant un recalage grossier suivi par un recalage fin est proposée pour calculer les paramètres de pose à partir de segments appariés. Étant donné que la mise en correspondance automatique d'entités linéaires est ardue et influence l'estimation des paramètres optimaux de transformation, une méthode d'appariement étudiant la similitude relative est avancée. Enfin, l'efficacité de cette méthode de recalage par mise en correspondance préalable des segments est évaluée et discutée.

**Mots clés** : Nuage de points, mise en correspondance, recalage, segment de droite, distance.

Abstract

In the processes of analysing, documenting and modelling the surrounding environment, an accurate registration of point clouds is necessary in order to obtain high-quality data. This procedure arises whenever a particular area is scanned by a laser more than once or from several different positions. Due to the variety of surveying techniques available, fusing the multi-source, complementary information data into one model is a very important matter. The vast majority of existing registration algorithms operate on feature points, hence ICP-like methods are the prevalent approach. This article proposes the use of line segments obtained from intersecting planes modelled within individual point clouds for the accurate registration of mobile laser scans with other data, whether 2D or 3D. This type of primitives can be easily extracted, even from heterogeneous and low-density point clouds. Using simulated data, several existing line-based registration algorithms have been evaluated in terms of reliability and robustness to noise. For the purpose of quantitative assessment, a new accuracy criterion taking advantage of a modified Hausdorff distance between two sets of lines has been defined. Having regard to these elements, a two-steps fast algorithm RLMR-FMII₂ combining coarse and fine registration was proposed to calculate the rigid body transformation from matching line pairs. Since the automatic pairing of line segments is a challenging task influencing the accuracy of the estimated transformation parameters, a method that considers the relative similarity is introduced. Finally, the efficiency of this line-based registration method with an explicit matching is evaluated and discussed.

**Keywords** : Point cloud, matching, registration, line segment, distance metric.

1. Introduction

Au cours de ces dernières années, le progrès de
la technique d'acquisition est devenu de plus en plus
perceptible. Cette évolution trouve son origine dans les
besoins croissants d'information tridimensionnelle sur
l'environnement mais aussi dans la mise à jour des

cartes existantes. Cependant, la réalisation de levés
topographiques détaillés à l'aide de stations totales, de
scanners fixes, de récepteurs GNSS (Global Navigation
Satellite System) ou bien encore de photogrammétrie
terrestre, montre ses points faibles lorsqu'il s'agit de
numériser des scènes à grande échelle. Ainsi, un objet
ne peut être quasiment jamais mesuré à partir d'une seule station. Cette difficulté doit être contournée par une augmentation de stations (avec différents points de vue). Plusieurs raisons peuvent en être la cause. Ce sont principalement les artefacts tels que les voitures stationnées et les piétons cachant les objets situés derrière ou sous eux. Mais, la limitation du champ de vision, l'architecture complexe des objets et enfin leur dimension importante demeurent également des facteurs déterminants. De ce fait, les systèmes laser mobiles - terrestres et aériens - semblent indispensables pour répondre aux exigences de la cartographie des corridors. Ils fournissent, dans un laps de temps très court, des données géo-référencées ayant, selon le mode de numérisation choisi, un niveau de détail congruent. Néanmoins, toutes les plates-formes mobiles se localisant grâce à des systèmes hybrides IMU/GNSS souffrent d'un biais observable entre les nuages de points redondants. Or, les pertes du signal GNSS dues aux masques créés par les bâtiments s'avèrent être la cause d'un « shift » d'estimation de trajectoire du système terrestre. Parallèlement, les données laser collectées avec un scanner aéroporté sont entachées d'écarts planimétriques et altimétriques résultant, cette fois-ci, de la dérive de la centrale inertielle. Bien que rapide lors de la phase d'acquisition, les relevés laser mobiles doivent alors être toujours affinés dans un système de référence commun, autrement dit consolidés (recalés).

Le cœur de nos préoccupations, dans le cadre de ce travail, est le recalage rigide de relevés laser issus du système de cartographie mobile terrestre. C'est pourquoi deux tâches principales peuvent être imaginées. D'une part, l'intégration de multi-données visera à améliorer le géo-référencement absolu ainsi qu'à incorporer d'autres types de données, externes au système d'acquisition mais fournissant souvent des informations complémentaires. En revanche, le principe de co-recalage sera d'assembler, de manière relative, les nuages acquis lors de plusieurs passages du système. Sachant que les données mobiles peuvent se caractériser par une densité assez faible, un recalage basé sur les entités linéaires est proposé. Puisque la nature hétérogène des nuages de points ne permet pas de garantir que la ligne extraite corresponde fidèlement à l'arête réelle, nous envisageons des segments sous forme d'intersections de plans principaux.

Par essence, la consolidation relie quatre problématiques :

1. la reconstruction des primitives identifiables dans la scène balayée;

2. la mise en correspondance via un algorithme robuste d'appariement;

3. l'estimation des paramètres optimaux de pose;

4. l'évaluation de la qualité d'assemblage effectué.

De ce fait, une solution à chaque problème susmentionné est proposée. Cet article présente ainsi une chaîne complète nommée RLMR-FMII₂ (Robust Line Matching and Registration-FMII₂) permettant un recalage rigide basé-segments qui nécessite un appariement préalablement. Dans un premier temps, nous avançons une approche de mise correspondance qui examine la similitude des droites (Section 3.1). Cette méthode requiert que les deux ensembles de segments à apparier soient relativement proches l'un à l'autre. L'objectif est donc de rapprocher d'abord les segments dans l'in-tention d'améliorer et faciliter leur appariement ultérieur. Par conséquence, l'estimation des paramètres de pose se fait en deux pas : l'estimation grossière et ensuite raffinée. Le recalage grossier étant réalisé par une approche combinatoire RANSAC et FMII₂ permet de trouver un échantillon optimal à partir duquel les paramètres initiaux de transformation sont calculés (Section 3.3). En suite, la mise en correspondance explicite des segments sert à un recalage fin (Section 3.2), possible grâce à l'algorithme FMII₂. Au-delà, la distance modifiée de Hausdorff LHD (Line Hausdorff Distance) définie entre deux ensembles de segments servira à évaluer la qualité du recalage effectué. En définitive, les tests avec des données simulées et réelles, discutés dans la section 4, confirment que cette approche est fiable mais aussi robuste au bruit environnant. Pour terminer (Section 5), une brève discussion relative aux conclusions est soumise.

## 2. État de l'art

La consolidation, inextricablement liée à la laser-grammétrie terrestre, revient à procéder un recalage relatif entre les relevés laser. Elle se réalise par une identification des éléments correspondants sous forme soit de cibles aux caractéristiques bien identifiables, soit de points ou d'entités géométriques homologues, observables dans les deux nuages à consolider (Landes et al., 2011). La classification des méthodes de recalage dans (Gressin et al., 2013) peut être une démarche introducitive intéressante pour les algorithmes existants. En effet, trois familles d'approches sont considérées :

1. les méthodes basées sur les primitives géométriques telles que les sphères, plans, cylindres, cônes ou lignes;

2. les algorithmes employant un modèle de surface (ordinairement un maillage) à la place des nuages;

3. les techniques focalisées sur les points homologues et ne nécessitant ni extraction préalable de primitives, ni de phase de modélisation.

Ces dernières, bénéficiant de l'algorithmme ICP (Iterative Closest Point) de (Besl et McKay, 1992), sont probablement les plus fréquemment employées. Aussi, plusieurs améliorations y ont déjà été apportées (Rusinkiewicz et Levoy, 2001). Pour l'analyse des variantes les plus
récentes d'ICP le lecteur pourra se référer à (Bouaziz et al., 2013). Néanmoins, l'inconvénient majeur de méthodes de type ICP réside toujours dans le fait qu'elles exigent des valeurs approchées pour initialiser le calcul des paramètres de transformation liant les deux nuages. Cette opération laisse la main libre à l'opérateur pour sélectionner trois points correspondants, rendant, de ce fait, semi-automatique l'utilisation de ces algorithmes. Cependant, une telle situation ne se présente pas quand les méthodes basées sur la reconstruction de primitives géométriques sont employées. Ainsi, lorsque les appariements exacts sont connus, les paramètres les plus probables de transformation peuvent être déterminés. Ces méthodes étant dépendantes de détails proéminents dans le nuage, leur handicap se dévoile lors du manque d'éléments géométriques pouvant être extraits et par un temps de traitement adéquat. La tendance actuelle est ainsi à la combinaison des deux (Landes et al., 2011). Le premier recalage – grossier fournit les paramètres d'initialisation demandés par le calcul itératif réalisé avec l'ICP qui vise à affiner des relevés laser.

Puisque les éléments linéaires sont omniprésents dans les scènes urbaines aménagées par l'homme, le recalage rigide basé-segments paraît une solution adéquate. De plus, les droites sous forme d'intersections peuvent être facilement extraites et décrites, même si les nuages de points sont peu denses et assez bruités. Quant au nombre de paires de droites indispensables pour estimer les paramètres de pose, on note que seules deux lignes non-coplanaires sont suffisantes à cette étape (Alshawa, 2006; Yao et al., 2010). Toutefois, compte tenu des bruits affectant les données, il est souhaitable d'avoir un nombre plus élevé de paires de segments pour assurer la redondance des observations et la fiabilité du résultat.

## 2.1. Mise en correspondance

La raison principale pour laquelle le recalage automatique est ardu vient du fait que les appariements, c'est-à-dire les vraies associations entre les primitives géométriques, sont inconnues. Puisque la mise en correspondance sert ensuite à établir un système de contraintes à minimiser, la convergence de l'algorithme en dépend directement. Comme l'explique Latulippe (2013), le développement de méthodes précises permettant de reconnaître des régions semblables est notable. Une des façons d'y parvenir est d'effectuer des correspondances avec des descripteurs, à savoir, un ensemble de valeurs caractéristiques, attribuées à un point et décrivant la géométrie locale autour de celui-ci. Dans le sujet de la mise en correspondance des lignes, un certain nombre de travaux peuvent être cités. Une étude montre que la distance Euclidienne peut ne pas être suffisante pour créer un appariement relativement correct (Douadi, 2007). Par conséquent, l'une des mai nières envisageable est de prendre en compte d'autres

attributs de segments tels que la longueur, la direction, la position ou le taux de chevauchement (Wang et al., 2012). De plus, les algorithmes disponibles se heurtent aux difficultés suivantes : la sur-segmentation des segments et le bruit entachant ses extrémités.

La plupart des approches existantes profitent de la rigidité de droites lors de la transformation, ce qui revient à dire que les écartements et les angles entre elles restent toujours les mêmes. D'après Yao et al. (2010), deux segments sont homologues si est seulement si, ils satisfont à deux conditions : les valeurs absolues de différence de distances et celles d'angles sont inférieures à des seuils fixés.

Li et al. (2012) appliquent la même hypothèse afin d'établir de vrais associations entre les segments 3D. La solution proposée consiste à attribuer, à toutes les lignes de l'ensemble deux vecteurs, chacun comprenant quatre composantes décrivant leur relation angulaire et l'éloignement vis-à-vis des autres éléments. Il s'agit de former le vecteur contenant : le maximum, le minimum, l'écart-type et la moyenne de mesures calculées. Afin d'estimer les correspondances, il faut définir une mesure de distance entre les différentes combinaisons de vecteurs. L'algorithme de Jaw et Chuang (2008) suit le même principe, mais il s'applique en deux étapes. D'abord, les angles spatiaux entre un segment et son voisin successif sont déterminés. Se référant à ces valeurs, un appariement approximatif est créé, si et seulement si la différence angulaire notée pour cette paire ne dépasse pas un certain seuil. Se reportant à ces associations, un recalage préliminaire est réalisé dans le but de rapprocher les deux jeux de droites. La dernière phase nous amènera donc à calculer les distances spatiales servant, à leur tour, à retrouver les correspondances explicites.

Un regard tout à fait différent est énoncé avec des approches cherchant à apparier des points à la place des lignes. L'une des possibilités est de discrétiser chaque droite en un certain nombre de points et de s'en servir pendant le couplage réalisé avec l'ICP. On peut aussi évoquer à ce sujet les travaux de Belton et al. (2011) qui font appel à des vertex créés à travers des intersections de lignes. Ainsi, la technique mise en œuvre consiste à étudier, au sein de chaque ensemble, des distances entre toutes les combinaisons possibles de points. Finalement, la technique de vote permet d'indiquer, avec une certaine tolérance, des distances semblables. De même, Huh et al. (2013) cherchent à apparier des polygones. Cette problématique est similaire à la nôtre, puisqu'un polygone est considéré comme la réunion de segments appelés côtés. À cet effet, des sommets ainsi que des « vertex virtuels » sont extraits. Un algorithme de recherche de sous-chaîne est ensuite employé afin de déterminer des points homologues.
## 2.2. Estimation de la pose

Dans l'objectif de l'estimation des paramètres optimaux de la transformation (trois rotations et trois translations) à partir de lignes, Zhang et Faugeras (1991) analysent plusieurs approches de minimisation, y compris le Filtre de Kalman Étendu (EKF), la minimisation au sens des moindres carrés et la décomposition en valeurs singulières (SVD). Différents scénarios ont été étudiés (en supposant que l'appariement explicite des segments soit déjà connu), afin de juger la façon optimale de représenter la matrice de rotation et d'estimer la transformation optimale. La représentation par un axe et un angle avec l'utilisation simultanée du Filtre de Kalman garantit la solution la plus précise. En revanche, lorsque l'on considère exclusivement le temps de calcul, c'est l'approche EIGEN basée sur la rotation exprimée en tant que quaternion et estimée par la SVD qui paraît la plus prometteuse.

Dans le même contexte, Alshawa (2006) propose deux variantes de méthode ICL (Iterative Closest Line) permettant, en dehors de ce procédé, une mise en correspondance approximative. La première - ICL (forme ICP) - est identique à l'ICP de base si l'on envisage uniquement l'estimation de rotation. Mais, elle présente un regard différent sur la façon de calculer le vecteur de translation. La seconde solution inspirée de (Habib et al., 2004), étant une approche itérative fondée sur les moindres carrés, requiert une approximation initiale des paramètres recherchés. Son principe consiste à décrire, à l'aide de la transformation de similitude 3D dont : R - rotation, T - translation et s - facteur d'échelle (égal à l'unité puisque les scanners laser produisent les données à l'échelle réelle), une relation entre les points homologues d'une paire de segments. Nonobstant, cette procédure suppose que les segments appariés ont la même longueur et que leurs extrémités se conjuguent. Pour surmonter cet inconvénient, Alshawa (2006) suggère d'unifier la longueur de segments, ce qui permet d'employer l'algorithme (ICL forme alternative).

Une autre amélioration de l'algorithme de (Habib et al., 2004) est également apportée par Renaudin et al. (2011). Elle consiste à enrichir le modèle mathématique de base en prenant en compte un vecteur des écarts défini entre les extrémités de segments. De ce fait, une nouvelle définition des poids associés au vecteur d'erreur est introduite pour éliminer cette inconnue. L'évaluation qualitative et quantitative d'une telle méthode de recalage est réalisée par Canaz et Habib (2013). À cet effet, les paramètres de la transformation calculés ont été comparés avec ceux fournis par d'autres méthodes, notamment par le recalage baséplans (Ghanma, 2006) mais aussi par l'algorithme ICPP (Iterative Closest Projected Point) de (Al-Durgham et al., 2011) étant l'une des variantes d'ICP. Cependant, certains problèmes au niveau de l'alignement vertical ont été observés. L'une des causes de cette imprécision

peut provenir de la nature des lignes elles-mêmes. En conséquence, la droite extraite des données image et associée à l'arête reconstruite du nuage peut être sensiblement différente.

Sur cette base, Al-Durgham et al. (2014) proposent un processus en deux étapes : l'estimation de pose grossière à l'intermédiaire des lignes appariées et ensuite l'estimation raffinée par l'algorithme ICPP.

Sous un point de vue différent, Guerra et Pascucci (1999) suggèrent de s'appuyer uniquement sur un triplet de paires tiré aléatoirement parmi toutes les combinaisons possibles. L'objectif à atteindre est celui de tester un très large nombre de transformations et de garder, par la suite, celle assurant le recalage optimal. Toutefois, cette approche suppose implicitement que les milieux des segments correspondent les uns aux autres, ce qu'il n'y a pas lieu d'être vrai dans un cas général.

Enfin, les méthodes de (Kamgar-Parsi et Kamgar-Parsi, 2004), applicables quelles que soient les entités linéaires, méritent d'être mentionnées. La solution adaptée à des éléments linéaires de même longueur est présentée par (Kamgar-Parsi et Kamgar-Parsi, 1997). Mais, lorsque les segments de longueur différente sont traités, trois cas doivent être dissociés. En désignant des segments à déplacer par Image (I), et celles de référence comme Model (M), trois approches se distinguent :

1. FMFI (Finite Model, Finite Image) conçu pour dériver la transformation à partir de deux ensembles de segments;

2. IMII (Infinite Model, Infinite Image) destiné aux lignes infinies;

3. FMII (Finite Model, Infinite Image) approprié à des cas mixtes.

En revanche, tous les calculs, indépendamment de la variante envisagée, s'appuient sur le schéma développé pour les segments égaux. Mais à une différence près, cette fois-ci, la transformation se calcule itérativement à partir des points correspondants établis par le paramètre "shift".

Pour résumer, quelle que soit la méthode choisie, la procédure d'estimation des paramètres cherche à résoudre séparément deux tâches : le problème non-linéaire de rotation et celui linéaire de translation.

## 3. Méthode de recalage proposé

Dans le dessein de développer une méthode de recalage résistant au bruit et aux paires aberrantes, un processus en deux étapes est proposé. L'organigramme de la Figure 1 présente, de façon schématique, les démarches successives devant être mises en œuvre
pour déterminer simultanément l'appariement et les pa-
ramètres optimaux de transformation rigide. De manière
générale, les étapes suivantes seront à effectuer :

1. l'appariement approximatif de primitives linéaires ;

2. le recalage grossier à partir d'un triplet de paires ;

3. l'appariement fin ;

4. le raffinement du recalage.

Or, l'idée consiste à rapprocher, dans un premier temps,
des segments afin d'améliorer et de faciliter leur appa-
riement réalisé conformément à la procédure dévelop-
pée. Celle-ci, n'utilisant aucune information a priori, de-
vient de plus en plus performante lorsque la distance
réciproque des segments est petite. Afin de diminuer le
nombre de paires erronées (Faux Positifs) et de garantir
un bon appariement les entités linéaires sont initialement
couplées en relation 1 à 1 au plus (A<sub>ini</sub>). Mais, cette
contrainte n'est plus valable avec l'appariement explicite
Af. Grâce aux analyses effectuées, dont les résultats se-
ront présentés ultérieurement, l'approche itérative FMII<sub>2</sub>
est choisie comme l'algorithme de base. De ce fait, l'es-
timation de pose grossière et raffinée est calculée de la
même façon. La seule différence réside dans le fait que
la consolidation initiale est atteinte à partir d'un sous-
ensemble minimal (k=3) considéré comme le meilleur
possible. Une technique de tirage aléatoire (RANSAC)
de k paires de l'ensemble A<sub>ini</sub> amène à assurer un
échantillon optimal, ne contenant plus de mauvaises as-
sociations. Ainsi, la méthode combinée RANSAC-FMII<sub>2</sub>
fournit une estimation initiale de la transformation. Pour-
tant, la position des segments après un recalage grossier
étant suffisamment proche de l'optimum, un couplage
explicite A<sub>f</sub> peut être créé, servant, à son tour, au reca-
lage fin. En définitive, chacun de ces sous-algorithmes
constitue une partie intégrale de notre procédure nom-
mée RLMR-FMII<sub>2</sub>.

**3.1. Appariement de deux jeux de segments**

La mise en correspondance précise de deux en-
sembles de segments s'avère une tâche difficile. La so-
lution examinée dans ce paragraphe se base sur la si-
militude et des contraintes géométriques. De cette ma-
nière, la comparaison des segments a pour finalité de
repérer les entités linéaires de l'ensemble de référence
M (Model) identiques ou très proches de celles étudiées
X (Test). Étant donné que seuls les segments quasi-
parallèles peuvent être appariés, on se devra de prendre
en compte l'orientation et la position des segments. La
dissemblance entre toutes les combinaisons possibles
de droites est notée sous forme d'un score d(t, m). Celui-
ci étant le coefficient de la matrice de similarité, il fera,
par la suite, l'objet d'une étude particulière. On mémo-
risera uniquement ainsi les paires dont les scores sont
jugés négligeables, c'est-à-dire, inférieurs ou égaux à
un seuil que l'on s'est fixé automatiquement en fonction
de valeurs calculées. Toutes les paires retenues forment

<figure><img src="image_1.png" /><figcaption>FIGURE 1 : Schéma général de l'algorithme RLMR-FMII₂.</figcaption></figure>

ensuite la matrice binaire de correspondance systémati-
sant les relations entre les éléments linaire de deux en-
sembles. En d'autres termes, le couplage entre les seg-
ments se fait via un seuillage d'une matrice de similarité.
Une fois l'appariement déterminé, la distance de Haus-
dorff (LHD) est calculée pour mesurer l'écartement des
données traitées – notre mesure de qualité. La Figure 2
présente un aperçu général des étapes de calcul consti-
tuant l'approche d'appariement proposée.

<figure><img src="image_2.png" /><figcaption>FIGURE 2 : Mise en correspondance des segments avec le calcul de distance.</figcaption></figure>
### 3.1.1. Matrice de similarité

L'étape cruciale de l'algorithme d'appariement consiste à créer une matrice de similarité, dont chaque coefficient $(i, j)$ indiquera un score (une distance) $d(t, m)$ attribué à un couple étudié. Ainsi, la matrice de similarité de taille $(i, j)$ déterminée par le nombre d'éléments dans les ensembles respectifs Test et Model, est obtenue selon la formule 1 :

$$d(t_i, m_j) = \frac{\sqrt{W \cdot (d^{\alpha}(t_i, m_j))^2 + (d^{\|}(t_i, m_j))^2 + (d^{\perp}(t_i, m_j))^2}}{\sqrt{W \cdot (d^{\alpha}(t_i, m_j))^2 + (d^{\|}(t_i, m_j))^2 + (d^{\perp}(t_i, m_j))^2}} \quad (1)$$

Le score $d(t, m)$ étant la mesure de similitude, représente, en pratique, "l'effort" nécessaire pour superposer deux segments quelconques. Sa valeur intègre l'écart angulaire $d^{\alpha}(t, m)$, l'indicateur de recouvrement $d^{\|}(t, m)$ et la distance perpendiculaire entre les segments parallélisés $d^{\perp}(t, m)$. La constante W, étant choisie empiriquement, est égale à 10 et permet de mieux mettre en évidence l'éventuelle divergence d'orientation de droites. Pour plus d'information quant au sujet du calcul et de la définition des distances élémentaires, le lecteur pourra se référer au travail de Poreba et Goulette (2013).

### 3.1.2. Matrice de correspondance

Dès que la matrice de similarité est déterminée, l'analyse de celle-ci est effectuée pour fixer un seuil $\delta$, indispensable dans le processus du rejet des paires erronées. Bien entendu, les correspondances recherchées ne seront quasiment jamais de 1 à 1, mais plutôt de 1 à plusieurs, de plusieurs à 1, voire de 1 à nul. Afin d'établir la valeur appropriée de seuil, nous commençons par un appariement préliminaire des segments S. Cette opération revient à apparier, à chaque segment de l'ensemble Test, un homologue le plus semblable de Model, c'est-à-dire le segment le plus proche au sens de la distance $d(t, m)$ (Figure 3).

<figure><img src="image_3.png" /><figcaption>**FIGURE 3 :** Estimation des correspondances : a) Matrice de similarité ; b) Appariement préliminaire S (carrés blancs).</figcaption></figure>

La tâche est aisée à remplir, puisque l'on peut toujours relier deux segments entre eux, même si le score calculé est significatif et même si la paire formée

de cette manière n'existe pas en réalité.

Se fondant sur cet appariement grossier S, la recherche d'un seuil optimal se limite à l'analyse des différences entre les distances associées aux paires sélectionnées. La soustraction des éléments $d(t, m)$ d'une telle suite S est exécutée deux fois. D'abord, nous sous-trayons membre à membre des valeurs classées selon un ordre ascendant ce qui amène à créer une nouvelle liste $Diff_1$ (courbe verte sur la Figure 4). L'opération est effectuée encore une fois, mais cette fois-ci, pour les termes de $Diff_1$. Comme résultat, nous obtenons la courbe violette (Figure 4). Le premier pic (maximum local) parmi les valeurs $Diff_2$ ayant la hauteur supérieure à la sensibilité admise, désigne l'indice du couple de segments dont le score correspondra au seuil de couplage $\delta$.

<figure><img src="image_4.png" /><figcaption>**FIGURE 4 :** Recherche du seuil optimal $\delta$.</figcaption></figure>

Finalement, la matrice de correspondance (Cor) est générée lors du seuillage de la matrice de similarité comme suit :

$$Cor = \{(i, j) \in \mathbb{N}^2 : \forall (t_i \in T, m_j \in M), d(t_i, M_j) \leq \delta\} \quad (2)$$

Il convient, toutefois, de mentionner que la procédure décrite est menée bilatéralement, principalement pour des raisons de contrôle. Ainsi, deux matrices de correspondance sont indépendamment déterminées, en supposant pour la seconde fois que l'ensemble Test est la référence. L'appariement final contiendra alors les éléments appartenant, à la fois, aux deux opérandes (intersection).

### 3.1.3. Métrique de Hausdorff comme mesure d'écartement entre deux jeux de segments

Dès que l'on retrouve les vraies associations entre les segments, on procède à la dernière phase – le calcul de l'éloignement. Cette opération est conçue pour mesurer la distance résiduelle entre les segments recallés. La métrique de Hausdorff, perçue comme un indicateur de similarité, est employée. Considérant deux ensembles Test et Model, la distance de Hausdorff est le
maximum de deux quantités - la première $h(X, M) = \max_{t \in X} \min_{t \in M} d(t, m)$ étant le maximum des plus courtes distances des éléments de $X$ à l'ensemble $M$, et la seconde $h(M, X)$ étant définie pareillement mais en direction de calcul opposée. La difficulté majeure réside dans le choix de la métrique $d(t, m)$ qui, dans notre cas est définie selon la formule 1. Pour déterminer les deux distances relatives de Hausdorff $h(X, M)$ et $h(M, X)$, nous nous référons à la définition introduite par Gao et Leung (2002), à une différence près, les calculs sont menés à partir de segments appariés et ordonnées par la matrice de correspondance (Cor). La distance OLHD (Oriented Line Hausdorff Distance) se calcule de la manière suivante :

$$OLHD(X, M) = \frac{1}{\sum_{m_j \in M} L_{M_j}} \sum_{(i,j) \in Cor} L_{M_j} d(t_i, M_j), \quad (3)$$

où $L_{M_j}$ est la longueur du segment de l'ensemble Model et $d(t_i, M_j)$ est la distance obtenue selon la formule 1.

Une telle solution, fondée sur la moyenne pondérée, semble plus robuste lorsque les segments plus longs sont privilégiés. En tout état de cause, la distance indirecte de Hausdorff LHD (Line Hausdorff Distance) est finalement retrouvée avec l'équation 4.

$$LHD(X, M) = \max(OLHD(X, M), OLHD(M, X)). \quad (4)$$

## 3.2. Algorithme FMII_2 – estimation de pose

L'estimation des paramètres de la transformation se réalise à l'aide de l'algorithme FMII_2 étant la version modifiée de FMII de (Kamgar-Parsi et Kamgar-Parsi, 2004) et dédiée originalement à estimer la pose entre les lignes Test (infinies) et celles Model (finies). Ce choix peut s'expliquer, conformément à l'explication des auteurs, par le fait que la variante FMFI, conçue pour les droites finies, risque d'échouer si le segment plus court d'un couple n'est pas complètement inclus dans son homologue. L'alternative proposée serait de remplacer provisoirement des segments Test (X) par des droites et de suivre, par la suite, les démarches envisagées par l'approche FMII. Par conséquent, la définition du paramètre "shift" {$s_i$} a dû aussi être changée. Le paragraphe suivant détaille au fur et à mesure les principes de cet algorithme d'optimisation.

### 3.2.1. Principe général

Étant donné deux ensembles d'entités linéaires $M = \{m_1, ..., m_i, ..., m_n\}$ comprenant des segments de référence (Model) et $X = \{t_1, ..., t_i, ..., t_n\}$ se déplaçant (Test), leur représentation peut être la suivante :

$$M = (a_i, v_i, L_i) \quad X = (x_i, w_i), \quad (5)$$

où :

* $a_i, x_i$ est le milieu du segment ;

* $v_i, w_i$ est le vecteur directeur normalisé de la droite et

* $L_i$ est la longueur du segment Model.

Sachant que, quel que soit $a_i \in M_i$, il existe sur la ligne $X_i$ son homologue $x_i + s_i w_i$ pour $s_i \in \mathbb{R}$, la distance $D(M, TX)$ entre les points correspondants se calcule comme suit :

$$D(M, TX) = \sum_{i=1}^{n} \left[ L_i ||a_i - T - R(x_i + s_i w_i)||^2 + \frac{L_i^3 (1 - v_i^t R w_i)}{6} \right] \quad (6)$$

L'estimation de la transformation rigide consiste ainsi à minimiser la distance réciproque $D(M, TX)$ sur tous les $T$ et $s_i$ envisageables. La solution s'obtient autour du problème d'optimisation non-linéaire, résolu grâce à la technique itérative, d'un système à (6+N) inconnues, dont six paramètres de transformation (trois rotations et trois translations) et N variables nécessaires pour identifier les points homologues. Or, les calculs de paramètres optimaux $T$ seront répétés jusqu'à ce que le changement de valeurs {$s_i$} ne dépasse pas un certain seuil. La Figure 5 illustre les démarches à suivre.

<figure><img src="image_5.png" /><figcaption>FIGURE 5 : Schéma de l'approche FMII_2 (Les valeurs initiales recommandées pour tous les $s_i$ sont des zéros).</figcaption></figure>

Quant aux paramètres {$s_i$} - inconnus lors de la première itération, leurs valeurs doivent être successive-ment actualisées selon la formule ci-dessous :

$$s_i = (a_i - T - R x_i)^t R v_i \quad (7)$$

Cependant, afin de déterminer la rotation, la matrice de covariance croisée $\Sigma_{M,X}$ est créée pour les segments correspondants, selon la formule 8.

$$\Sigma_{M,X} = \sum_{i=1}^{n} \left[ L_i (a_i - \bar{a}) (x_i + s_i w_i - \bar{x})^t + \frac{L_i^3 v_i (w_i)^t}{12} \right] \quad (8)$$

où $\bar{a}$ et $\bar{x}$ sont donnés par l'équation 9,

$$\bar{a} = \frac{1}{P} \sum_{i=1}^{n} L_i a_i \quad ; \quad \bar{x} = \frac{1}{P} \sum_{i=1}^{n} L_i (x_i + s_i w_i) \quad (9) \\ P = \sum_{i=1}^{n} L_i$$
La matrice de rotation est représentée par un quaternion unitaire (Horn, 1987) nécessitant, dans un premier temps, l'élaboration d'une matrice symétrique $C_{4×4}$ (équation 10) dont les éléments sont définis à partir de $\Sigma_{M,X}$.

$$ 
\begin{aligned}
C_{11} &= \Sigma_{11} + \Sigma_{22} + \Sigma_{33}; \quad C_{12} = C_{21} = \Sigma_{23} - \Sigma_{32} \\
C_{13} &= C_{31} = \Sigma_{31} - \Sigma_{13}; \quad C_{14} = C_{41} = \Sigma_{12} - \Sigma_{21} \\
C_{22} &= \Sigma_{11} - \Sigma_{22} - \Sigma_{33}; \quad C_{23} = C_{32} = \Sigma_{12} + \Sigma_{21} \\
C_{24} &= C_{42} = \Sigma_{31} + \Sigma_{13}; \quad C_{33} = \Sigma_{22} - \Sigma_{33} - \Sigma_{11} \\
C_{34} &= C_{43} = \Sigma_{23} + \Sigma_{32}; \quad C_{44} = \Sigma_{33} - \Sigma_{11} - \Sigma_{22}
\end{aligned} 
\quad (10) $$

Finalement, le vecteur propre, correspondant à la plus grande valeur propre, représente la rotation optimale R exprimée en quaternion unitaire $q = [\lambda_0, \lambda_1, \lambda_2, \lambda_3]^t$. Cependant, le passage entre le quaternion et la matrice de rotation classique se réalise selon la formule 11.

$$ R = \begin{pmatrix} \lambda_0^2 + \lambda_1^2 - \lambda_2^2 - \lambda_3^2 & 2(\lambda_1\lambda_2 - \lambda_0\lambda_3) & 2(\lambda_1\lambda_3 + \lambda_0\lambda_2) \\ 2(\lambda_1\lambda_2 + \lambda_0\lambda_3) & 2(\lambda_2\lambda_3 + \lambda_0\lambda_1) & 2(\lambda_2\lambda_3 - \lambda_0\lambda_1) \\ 2(\lambda_1\lambda_3 - \lambda_0\lambda_2) & 2(\lambda_2\lambda_3 + \lambda_0\lambda_1) & \lambda_0^2 - \lambda_1^2 - \lambda_2^2 + \lambda_3^2 \end{pmatrix} \quad (11) $$

Une fois la rotation estimée, le vecteur de translation $T$ peut être retrouvé en minimisant l'équation 6 ce qui amène finalement à résoudre l'équation linéaire :

$$ T = \bar{a} - R\bar{x}. \quad (12) $$

### 3.3. Méthode combinant RANSAC et FMII₂ – recalage grossier

La finalité du recalage grossier cherche à rapprocher deux ensembles de segments pour faciliter leur apparition. En présumant l'existence de mauvaises paires au sein de l'appariement $A_{ini}$ résultant de la distance mutuelle importante, l'alignement initial semble alors indispensable. Se référant à l'étude menée par (Yao et al., 2010), trois paires représentatives sont optimales pour trouver les paramètres de la transformation préliminaire. Ainsi, l'objectif du recalage grossier se résume à calculer les paramètres de pose à partir d'un triplet de paires. Par conséquent, plusieurs tirages aléatoires doivent être effectués avec l'algorithme de RANSAC afin de découvrir le meilleur échantillon parmi ceux recueillis avec l'appariement initial $A_{ini}$. Le nombre d'itération $N_{iter}$, choisi dynamiquement en fonction du nombre d'inliers, se calcule comme suit :

$$ N_{iter} = \frac{\log(\epsilon)}{\log(1 - q)} \quad (13) $$

$$ q = \frac{\begin{pmatrix} N_I \\ k \end{pmatrix}}{\begin{pmatrix} N \\ k \end{pmatrix}} = \frac{N_I!(N-k)!}{N!(N_I-k)!} = \prod_{i=1}^{k-1} \frac{N_I - i}{N - i} \approx \left(\frac{N_I}{N}\right)^k \quad (14) $$

où :

* $N=\text{card}(A_{ini})$ : nombre de paires dans l'appariement initial $A_{ini}$;

* $N_I=\text{card}(EC)=N-N_A$ : nombre d'inliers;

* $k$ : nombre minimal de paires de segments pour estimer la transformation optimale (la valeur adoptée $k=3$);

* $\epsilon$ : taux de fausse alerte (la valeur adoptée $\epsilon=1e^{-6}$);

Pour chaque échantillon, la transformation optimale est calculée et appliquée aux segments Test. Dès lors, les distances $d(t_i, m_j)$ peuvent être recalculées selon l'équation 1 entre toutes les paires recalées et listées par $A_{ini}$. Le nombre de valeurs aberrantes ($N_A$) est désormais défini de la manière suivante :

$$ N_A = |\{ (i, j) \in A_{ini} : \forall (t_i \in T, m_j \in M), d(t_i, m_j) > \gamma \}| \quad (15) $$

Le meilleur échantillon retenu sera celui, pour lequel le nombre de segments ayant la distance réciproque inférieure au seuil prédéfini $\gamma$, est le plus grand. Ainsi, plus le nombre de segments est important, plus l'estimation grossière est meilleure.

## 4. Résultats et évaluation

La robustesse de notre algorithme du recalage RLMR-FMII₂ fondé sur la mise en correspondance des segments a été vérifiée avec des données simulées et réelles. Ces dernières ont été collectées au sein d'une zone de test située à Paris à proximité du croisement des rues du Vieux-Colombier et Madame. Des relevés laser y ont été acquis par le système mobile Stéréopolis II de l'IGN dans la configuration décrite par (Paparoditis et al., 2012). Trois passages de la plateforme ont été réalisés dans ce périmètre. En outre, un nuage de points a été mesuré avec un scanner Leica ScanStation 10 et ensuite géo-référencé dans le système Lambert-93. Ces deux types de données laser nous ont permis une extraction des arêtes de pli (intersection entre les plans principaux). Les segments détectés à partir de données mobiles sont marqués comme S1, S2 et S3, tandis que ceux de référence comme F (voir la Figure 6).

Les données simulées, quant à elles, sont générées par la modification de 64 arêtes provenant des relevés laser fixe (F) en appliquant les paramètres prédéfinis de transformation rigide : la rotation R exprimée avec ses angles d'Euler $[1,0,0^\circ; -1,0,0^\circ; 1,0,0^\circ]$ et la translation $T=[-1,0 \text{ m}; 0,5 \text{ m}; 1,0 \text{ m}]$. De plus, les extrémités de ces segments ont été bruitées par tirage aléatoire suivant une loi normale centrée d'écart-type $\sigma$. Les tests ont été menées pour différentes valeurs de bruit, en partant de $\sigma=0,0 \text{ m}$ et en finissant sur $\sigma=0,05 \text{ m}$, avec l'intervalle de 0,001 m. Il en résulte des centaines de nouveaux ensembles Test, chacun contenant 64 éléments et éloigné du Model (F) à environ 2,7 m (distance LHD).

### 4.1. Évaluation des méthodes d'estimation de pose

Dans un premier temps, la précision des paramètres de transformation obtenus avec l'algorithme FMII₂ et la procédure couplant FMII₂ et RANSAC a été étudiée et
<figure><img src="image_6.png" /><figcaption>FIGURE 6 : Segments extraits au sein de la zone de test (données réelles).</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>FIGURE 7 : Comparaison de différentes méthodes d'estimation de pose à l'aide des données simulées.</figcaption></figure>
juxtaposée avec celle fournie par deux méthodes de l'état de l'art, notamment l'approche EIGEN de (Zhang et Faugeras, 1991) et ICL (forme ICP) de (Alshawa, 2006). La qualité des estimations, exprimée par les erreurs $e_R$ et $e_T$ d'évaluation de la rotation et translation, est déterminée selon les équations 16 et 17 par rapport aux valeurs réelles.

$$e_R = 100\% \frac{\|r - \hat{r}\|}{\|r\|} \qquad (16)$$

$$e_T = 100\% \frac{\|T - \hat{T}\|}{\|T\|} \qquad (17)$$

où :

* $r, T$ sont les rotation et translation réelles (intro-duites en entrée) ;

* $\hat{r}, \hat{T}$ sont les rotation et translation estimées.

La formule 16 est valable pour la forme axe-angle de rotation définie par un angle $\theta$ et un axe orienté par un vecteur unitaire $r = [e_x, e_y, e_z]^t$. Il est donc nécessaire de remplacer la représentation classique de rotation $R$ par $r$ de la manière suivante :

$$\theta = \arccos \left( \frac{\text{trace}(R) - 1}{2} \right), \qquad (18)$$

$$r = \frac{1}{2 \sin \theta} \begin{pmatrix} R_{32} - R_{23} \\ R_{13} - R_{31} \\ R_{21} - R_{12} \end{pmatrix}. \qquad (19)$$

La Figure 7 illustre les erreurs sur $R$ et $T$ estimés par les algorithmes ICL (forme ICP), EIGEN et FMII₂ à partir des données simulées dont l'appariement était connu a priori. Également, la précision des paramètres obtenus lors du recalage grossier a été vérifiée. Ce dernier est réalisé par la méthode combinant FMII₂ et RANSAC, cette fois-ci, avec la mise en correspondance simultanément des segments.

Il en résulte que les algorithmes ICL (forme ICP) et EIGEN produisent des résultats à un niveau de précision similaire. Ils présentent une faible robustesse au bruit et ne peuvent être employés que sur des segments dont les extrémités ne sont pas bruitées. En effet, l'estimation de la rotation atteint une précision de l'ordre de 5% pour un écart-type de bruit $\sigma$ ne dépassant pas ou à peine 0,015 m. L'erreur de la translation $e_T$ est cependant plus importante et peut atteindre 100%. L'approche FMII₂ donne, quel que soit le bruit introduit, des résultats précis. Ainsi, l'erreur de la matrice de rotation $e_R$ est inférieure à 0,5% pour un $\sigma < 0,02$ m. Cette dernière oscille entre 0,5% et 3,6% pour les autres valeurs de $\sigma$, afin d'atteindre son maximum en $\sigma=0,047$ m. L'erreur de la translation $e_T$, quant à elle, est supérieure à $e_R$ et reste dans l'intervalle de 2,9% à 8,5%.

Quant au recalage grossier réalisé à partir d'un triplet de paires choisi parmi les segments appariés, il est moins précis que l'algorithme FMII₂ seul exécutée sur l'appariement idéal. En état ce n'est guère surprenant puisque la qualité de la solution reçue avec le FMII₂ augmente toujours, quand nous y ajoutons d'autres couples. Par

contre, le recalage grossier garantit une bonne estimation initiale ce qui nous permettra par la suite de rapprocher de façon optimale les deux jeux de segments et d'établir l'appariement explicite $A_f$.

## 4.2. Mise en correspondance des segments

La mise en correspondance des segments réels a été réalisée et comparée avec la vérité-terrain. De ce fait, la capacité de l'algorithme à prédire si une paire existe a été mesurée. À chaque fois, une matrice de confusion a été créée afin d'observer le nombre de paires de segments :

1. correctement appariées VP (Vrais Positif) ;

2. correctement rejetées VN (Vrais Négatifs) ;

3. mal identifiées FP (Faux Positifs) ;

4. omises FN (Faux Négatifs).

La Figure 8 visualise un exemple de résultats de la mise en correspondance de segments.

Trois critères servant à noter l'algorithme d'appariement ont été définis comme :

$$\text{Exactitude} = (VP + VN)/(n.m) \qquad (20)$$

$$\text{Sensibilité} = VP/(VP + FN) \qquad (21)$$

$$\text{Spécificité} = VN/(VN + FP) \qquad (22)$$

<figure><img src="image_8.png" /><figcaption>FIGURE 8 : Exemple de résultats – comparaison avec la vérité terrain.</figcaption></figure>

Le Tableau 1 résume les résultats pour toutes les données traitées. Il en ressort que l'appariement des segments est suffisamment exact. La probabilité que notre algorithme dissocie correctement N vraies paires parmi toutes les combinaisons possibles (Exactitude) est élevée et oscille autour de 99,6%. En moyenne 92,3% des paires (voir la Sensibilité) ont été retrouvées, indépendamment de l'éloignement de deux ensembles. Le nombre de FN (non-détection d'une paire présente) n'est ainsi pas marquant. Aussi, la probabilité de dénombrer les appariements erronés FP (détection d'une paire inexistante) est faible. Étant donné que la Spécificité atteint un niveau de 99,7%, le nombre de FP constitue 0,3% de
<table><caption>TABLE 1 : Validation de l'algorithmme (M-Model, X-Test).</caption><thead><tr><th rowspan="2"></th><th colspan="2">Nombre de segments</th><th rowspan="2">Nombre de paires (N)</th><th rowspan="2">Exactitude [%]</th><th rowspan="2">Sensibilité [%]</th><th rowspan="2">Spécificité [%]</th><th colspan="2">OLHD [m]</th><th rowspan="2">LHD [m]</th></tr><tr><th>Test (n)</th><th>Model (m)</th><th>X→M</th><th>M→X</th></tr></thead><tbody><tr><td>S1-S2</td><td>36</td><td>28</td><td>11</td><td>99,8</td><td>95,8</td><td>99,9</td><td>0,518</td><td>0,472</td><td>0,518</td></tr><tr><td>S1-S3</td><td>36</td><td>41</td><td>29</td><td>99,5</td><td>93,1</td><td>99,7</td><td>0,302</td><td>0,297</td><td>0,302</td></tr><tr><td>S2-S3</td><td>28</td><td>41</td><td>12</td><td>99,7</td><td>91,7</td><td>99,8</td><td>0,481</td><td>0,560</td><td>0,560</td></tr><tr><td>S1-F</td><td>36</td><td>64</td><td>21</td><td>99,6</td><td>90,5</td><td>99,7</td><td>0,671</td><td>0,656</td><td>0,671</td></tr><tr><td>S2-F</td><td>28</td><td>64</td><td>22</td><td>99,1</td><td>90,9</td><td>99,2</td><td>1,104</td><td>1,257</td><td>1,257</td></tr><tr><td>S3-F</td><td>41</td><td>64</td><td>24</td><td>99,6</td><td>91,7</td><td>99,7</td><td>0,563</td><td>0,657</td><td>0,657</td></tr><tr><td></td><td colspan="2">Moyenne</td><td></td><td>99,6</td><td>2,3</td><td>99,7</td><td></td><td></td><td></td></tr></tbody></table>

tous les VN. Par contre, le taux de FP paraît dépendre de la distance réciproque entre les segments. En réalité, cet impact sur l'écartement se traduit par une augmentation du nombre de segments couplés qui, dans le cas étudié, sont enrichis par 73% de paires de plus (pour une distance LHD égale à 1,257m). L'origine de ce problème réside dans la matrice de similarité elle-même dont l'analyse, en présence de décalage significatif, empêche de restituer de vraies relations entre les segments. Il est alors clair que plus les deux ensembles à recaler sont proches l'un de l'autre, plus la mise en correspondance sera fiable et précise. Sinon, faute de précision requise, il sera nécessaire de rapprocher des données avant d'exécuter l'algorithmhe d'appariement comme il est proposé dans ce travail.

### 4.3. Algorithme proposé RLMR-FMII₂

En dernier lieu, la chaîne complète RLMR-FMII₂, illustrée par le schéma de la Figure 1, a été vérifiée à l'aide de données simulées et réelles

#### 4.3.1. Évaluation avec données simulées

Tout d'abord, la précision des estimations a été analysée en déterminant, selon les formules 16 et 17, les erreurs $e_R$ et $e_T$. Ensuite, une comparaison de valeurs par rapport à celles obtenues par l'algorithmhe FMII₂ seul profitant de l'appariement fiable connu a priori, a été entreprise. De manière analogue, les tests ont été menés pour différentes valeurs d'écart-type $\sigma$. La Figure 9 illustre le résultat d'une telle étude. Nous pouvons constater que plus l'écart-type de bruit $\sigma$ est petit, plus l'appariement établi est précis et donc que les erreurs d'estimation sont du même ordre de grandeur. Au-delà, la méthode RLMR-FMII₂ paraît donner des résultats légèrement moins précis, surtout quand l'écart-type de $\sigma$ est supérieur à 0,025 m. Ceci est dû au fait que la qualité de la mise en correspondance dépend également du taux de bruitage de segments, moyennant quoi, l'appariement explicite $A_f$ peut toujours contenir de fausses paires. Pour mieux comprendre la grandeur de cette imprécision d'estimation de pose sur la position relative des segments recalés, la distance LHD (formule 4) a été calculée. La Figure 10 illustre les différences entre la distance

après le recalage basé sur l'algorithmhe FMII₂ et celle résultant du recalage mené selon la procédure RLMR-FMII₂. Ainsi, ces valeurs sont négligeables et ne dépassent pas 0,004 m, même si la présence de quelques appariements erronés avait été constatée. Ce constat confirme la robustesse de notre approche, étant capable, à la fois, d'apparier correctement des segments et d'estimer les paramètres optimaux de pose.

#### 4.3.2. Données réelles

La performance de l'approche RLMR-FMII₂ a été analysée grâce aux données réelles. À cet effet, les segments extraits depuis les relevés laser ont été recalés entre eux dans plusieurs configurations (S1-S2, S1-S3, S2-S3, S1-F, S2-F, S3-F). À chaque fois, une amélioration importante de l'appariement initiale $A_{ini}$ a été relevée. La vérification de l'ajustement des lignes après les deux recalages successifs grossier et fin a été réalisée à travers la distance LHD. Nous observons une réduction progressive de l'écartement entre les données traitées. Le Tableau 2 contient des valeurs numériques (les paramètres de pose estimés, l'éloignement de deux ensembles de segments, le temps de calcul) tandis que la Figure 11 visualise quelques exemples de résultats. Nous en ressortons que l'utilisation simultanée de l'algorithmhe de RANSAC, habituellement très coûteux en temps de calcul, est compensée par la mise en correspondance explicite des segments $A_f$. Par conséquent, la consolidation précise devient possible. Quant au temps de calcul, il est de l'ordre de dizaines de secondes (code non optimisé sous Matlab).

## 5. Conclusion

Dans cet article, le problème du recalage géométrique d'éléments linéaires est abordé. Trois méthodes basées-segments ICL (forme ICP), EIGEN et FMII₂ qui cherchent à estimer la pose relative à condition que l'appariement explicite des entités linéaires soit connu, sont évaluées face à différentes valeurs de bruit ajoutées aux extrémités de segments. La méthode la plus précise des trois, à savoir FMII₂, est utilisée dans un processus en deux étapes : l'estimation de pose grossière et ensuite
<figure><img src="image_9.png" /><figcaption>FIGURE 9 : Approche FMII₂ (exécutée à partir d'appariement connu a priori) vs Approche proposée RLMR-FMII₂.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>FIGURE 10 : Vérification des différences de distances LHD.</figcaption></figure>

<table><caption>TABLE 2 : Résultats obtenus avec l'approche proposée (données réelles) – Intel Core x2 T7600 2,33 Ghz/4 Go/ Win 7 64 bits</caption><thead><tr><th>Jeu de données</th><th>S1-S2</th><th>S1-S3</th><th>S2-S3</th><th>S1-F</th><th>S2-F</th><th>S3-F</th></tr></thead><tbody><tr><td>Distance initiale LHD [m]</td><td>0,518</td><td>0,297</td><td>0,560</td><td>0,671</td><td>1,257</td><td>0,657</td></tr><tr><td>Nombre d'itérations N<sub>iter</sub></td><td>248</td><td>58</td><td>563</td><td>88</td><td>1640</td><td>109</td></tr><tr><td>Distance LHD après le recalage grossier [m]</td><td>0,346</td><td>0,233</td><td>0,481</td><td>0,266</td><td>0,451</td><td>0,320</td></tr><tr><td>Distance LHD après le recalage fin [m]</td><td>0,304</td><td>0,213</td><td>0,377</td><td>0,189</td><td>0,220</td><td>0,140</td></tr><tr><td>Angles d'Euler [°]</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>ω</td><td>0,35196</td><td>-0,15530</td><td>0,68971</td><td>0,30821</td><td>-0,00763</td><td>0,03841</td></tr><tr><td>φ</td><td>-0,12854</td><td>-0,00760</td><td>-0,19781</td><td>-0,17301</td><td>-0,14627</td><td>-0,08465</td></tr><tr><td>K</td><td>-0,43047</td><td>-0,21210</td><td>0,28428</td><td>-0,01031</td><td>0,09351</td><td>0,18708</td></tr><tr><td>Translation [m]</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>X</td><td>0,950</td><td>-0,205</td><td>1,172</td><td>-0,646</td><td>-0,331</td><td>-0,205</td></tr><tr><td>Y</td><td>-0,833</td><td>0,108</td><td>-1,048</td><td>0,014</td><td>-0,525</td><td>-0,461</td></tr><tr><td>Z</td><td>0,189</td><td>0,177</td><td>-0,708</td><td>-0,494</td><td>-0,285</td><td>-0,507</td></tr><tr><td>Temps CPU [s]</td><td>18,1</td><td>10,4</td><td>50,4</td><td>7,8</td><td>183,6</td><td>16,4</td></tr></tbody></table>
<figure><img src="image_11.png" /><figcaption>FIGURE 11 : Exemple de résultats : a) Segments originaux ; b) Segments recalés.</figcaption></figure>
raffinée. Une telle procédure nommée RLMR-FMII₂ permet également une détection automatique préalable des segments homologues. Faisant appel à la similitude des lignes, celle-ci donne le meilleur résultat si les deux ensembles sont relativement proches. Pour cette raison, il est recommandé de rapprocher, dans un premier temps, des droites pour faciliter et améliorer leur couplage ultérieur. Cela explique la première étape - le recalage grossier réalisé à l'aide d'un algorithme combinant RANSAC et FMII₂. Par la suite, l'appariement explicite des segments peut être établi afin de servir au recalage fin effectué grâce à l'algorithme FMII₂ seul.

L'approche proposée est entièrement automatique et attend en entrée seulement des coordonnés de deux ensembles de segments et l'écart-type de bruit σ caractérisant l'incertitude du segment. L'algorithme délivre une solution optimale, c'est-à-dire, les paramètres de transformation rigide R et T ainsi que les paires créées (matrice de correspondance) et la distance (LHD) initiale et résiduelle entre les segments consolidés.
Les tests effectués confirment la robustesse et la fiabilité de l'approche. Les paramètres de pose sont estimés précisément, même en présence de quelques faux positifs au sein de l'appariement créé. Néanmoins, en l'absence de précision requise, le recalage basé-segments peut toujours servir à initialiser certains algorithmes de recalage. La méthode est valable si l'on cherche à recaler localement les relevés laser mobiles sur des données de référence, mais n'est pas valable pour un recalage global d'un scan de taille importante quand les déformations non-rigides sont significatives.

## Références

Al-Durgham M., Detchev I., Habib, A., 2011. Analysis of Two Triangle-Based Multi-Surface Registration Algorithms of Irregular Point Clouds. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XXXVIII-5/W12 : 61-66.

Al-Durgham, K., Habib, A., Mazaheri, M., 2014. Solution frequency-based procedure for automated registration of terrestrial laser scans using linear features. ASPRS Annual Conference, 23-28 March 2014, Louisville, KY, USA.

Alshawa M., 2006. Consolidation des nuages de points en Lasergrammétrie Terrestre. PhD thesis, École Nationale Supérieure d'Architecture de Nancy, Nancy, France.

Belton D., Mooney B., Snow T., Kwang-Ho B., 2011. Automated Matching of Segmented Point Clouds to As-built Plans. In : Proceedings of the Surveying & Spatial Sciences Biennial Conference, 21-25 November 2011, Wellington, New Zealand.

Besl P.J., McKay N.D., 1992. A method for registration of 3-D shapes. IEEE Transactions of Pattern Analysis and

Machine Intelligence, 14(2) :239-256.

Bouaziz, S., Tagliasacchi, A., Pauly, M., 2013. Sparse Iterative Closest Point. Computer Graphics Forum (Symposium on Geometry Processing), vol. 32, pp.1-11.

Canaz S., Habib A., 2013. Planar and linear feature-based registration of terrestrial laser scans with minimum overlap using photogrammetric data. In : Proceedings of the 8th International Symposium on Mobile Mapping Technology, Taiwan, Taiwan.

Chen J., Leung M.K., Gao Y., 2003. Noisy logo recognition using line segment Hausdorff distance. The Journal of the Pattern Recognition Society, 36 :943-955.

Douadi L., 2006. Contribution à l'étude du recalage de données 3D/couleur. PhD thesis, University Montpellier II, Montpellier, France.

Gao Y., Leung M.K., 2002. Line segment Hausdorff distance on face matching. The Journal of the Pattern Recognition Society, 35 :361-371.

Ghanma M., 2004. Integration of Photogrammetry and LIDAR. PhD thesis, University of Calgary, Canada.

Gressin A., Mallet C., Demantké J., David N., 2013. Towards 3D lidar point cloud registration improvement using optimal neighborhood knowledge. ISPRS Journal of Photogrammetry and Remote Sensing, 79 :240-251.

Guerra C., Pascucci V., 1999, On matching Sets of 3D Segments. Proceedings of SPIE, 3811 :157-167.

Habib A.F., Ghanma M.S., Tait M., 2004. Integration of LIDAR and photogrammetry for close range applications. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XXXV-B5, 1045-1050.

Horn, B.K.P., 1987. Closed-form solution of absolute orientation using unit quaternion. Journal of the Optical Society of America, vol. 4, pp. 629-642.

Huh Y., Yang S., Ga Ch., Yu K., Shi W., 2013. Line segment confidence region-based string matching method for map conflation. ISPRS Journal of Photogrammetry and Remote Sensing, 78 :69-84.

Jaw J-J., Chuang T-Y., 2008. Registration of ground-based LIDAR point clouds by means of 3D line features. Journal of the Chinese Institute of Engineers, 31(6) :1031-1045.

Kamgar-Parsi B., Kamgar-Parsi B., 1997. Matching Sets of 3D Line Segments with Application to Polygonal Arc Matching. IEEE Transactions on Pattern Analysis and
Machine Intelligence, 19(10) : 1090-1099,

Kamgar-Parsi B., Kamgar-Parsi B., 2004. Algorithms for Matching 3D Line Sets. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(5) : 361-371.

Landes T., Grussenmeyer P., Boulaassal, H., 2011. Les principes fondamentaux de la lasergrammétrie terrestre : acquisition, traitement des données et applications. Revue XYZ, 129(4) : 25-38.

Latulippe M., 2013. Calage robuste et accéléré de nuages de points en environnements naturels via l'ap-prentissage automatique. Msc thesis, Laval University, Quebec City, Canada.

Li W., Li X., Bian Y., Zhao H., 2012. Multiple View Point Cloud Registration Based on 3D Lines. In : Proceedings of the International Conference on Image Processing, Computer Vision & Pattern Recognition, Las Vegas, USA.

Paparoditis N., Papelard J-P., Cannelle B., Devaux A., Soheilian B., Nicolas N., Houzay E., 2012. Stéréopolis II : A multi-purpose and multi-sensor 3D mobile map-ping system for street visualization and 3D metrology. Revue Française de Photogrammétrie et de Télédétec-tion, 200 :69-79,

Poreba M., Goulette F., 2013. Line segment-based approach for Accuracy Assessment of MLS point clouds in urban areas. In : Proc. of the 8th International Sympo-sium on Mobile Mapping Technology, Taiwan, Taiwan.

Renaudin E., Habib E., Kersting A.P., 2011 Feature-Based Registration of Terrestrial Laser Scans with Minimum Overlap Using Photogrammetric Data. ETRI Journal, 33(4) :517-527.

Rusinkiewicz, S., Levoy, M., 2001. Efficient variants of the ICP algorithm. In : Proceedings of the International Conference on 3D Digital Imaging and Modeling (3DIM), Quebec City, Canada, pp. 145-152.

Wang W., Lou A., Wang J., 2012. The research of line matching algorithm under the improved homograph matrix constraint condition. The International Archives of Photogrammetry, Remote Sensing and Spatial Informa-tion Sciences, XXXIX-B3 :345-350.

Yao J., Ruggeri M.R., Taddei P., Sequeira V., 2010. Robust range image registration using 3D lines. Pro-ceedings of the 17th International Conference on Image Processing, Hong-Kong, China, 4321-4324.

Zhang Z., Faugeras O., 1991. Determining motion from 3D Line Segment Matches : a comparative Study. Image and Vision Computing, 9(1) :10-19,