Mixed Reality" (MR) can be used to describe Augmented Reality (AR) which primarily focuses on achieving photo-realism when augmenting the real world with virtual content. MR is applicable to a variety of immersive experiences, running the gamut from visual entertainment to simulation-based training, and for previsualization tasks with a emphasis on design.The realistic visual integration of virtual elements in a scene requires an accurate and up-to-date model of the real scene's geometry and semantic contents. The 3D structure of the environment impacts rendering tasks such as occlusion detection and physically-based lighting, but also influences the spatial layout of the virtual content and its interactions with the real world. Given the hardware and power constraints of widely available AR devices, it is impractical to perform an extensive geometry scan whenever these devices are used in a known environment. Still, even in a dynamic scene, a lot of structural information (e.g., solid walls) will remain constant over time and can be stored between sessions, only needing local updates to accurately represent the scene's current state.

The aim of this doctoral study has been to provide the means to identify and correct the areas of change through the detection of inconsistencies between a prior representation and an up-to-date view of the scene. In this thesis, we relate our contributions towards achieving this goal. In particular, we present the completion of a lightweight reprojection-based geometric change detection framework, as well as the elaboration of a semantic scene model representing the properties of the scene relevant to the MR experience using a graph structure. Following this, a scene analysis and registration method is implemented that showcases said graph model representation capabilities, and its performance as the basis of a robust localisation framework. The maintenance of an accurate geometric and semantic model of a real scene can ultimately be achieved with limited AR devices using the graph structure to interpret preliminary change detection results as changes in the scene's objects' properties. Contents 5.3.3.1 Basic descriptor using the adjacency matrix . . . . . . . .

I would like to express my gratitude to all my thesis advisors, Matthieu Fradet, Caroline Baillard, Guillaume Moreau, Maja Krivokuća and Jean-Marie Normand who -despite the many outside challenges we faced during those three years-helped me see it through to the end.

I would also like to thank my colleagues for making me feel part of the team even when I was isolated in my work, especially Koki, Sylvain, Rodrigo, Tomás and Gustavo, as well as our musical next-door neighbours.

I am also grateful to Tim and his family for their warm welcome in Rennes and for helping me make the most of my stay here. I extend this gratitude to all my friends who kept in touch during this thesis, most of which are now going through this experience themselves.

Lastly, I am grateful to have such a great family, who all supported me always, and without whom I could not have made it this far.

Résumé en français

Introduction En 2016, le regain d'intérêt pour la Réalité Virtuelle (RV) suivant la sortie de l'Oculus Rift et de l'HTC VIVE, a été partagé par la Réalité Augmentée (RA) pour ses capacités d'immersion [START_REF] Dave | Microsoft's answer to google glass: Hololens[END_REF]. Répondant à cette demande, en 2017 Microsoft a sorti le visiocasque Hololens et Apple a publié ARKit, un outil de développement permettant de produire des applications de RA sur leurs appareils. Avec la sortie de ARCore pour Android l'année suivante, une grande variété d'applications de RA grand public ont pu être développées. L'essor du télétravail [START_REF] Robinson | Remote work is here to stay and will increase into 2023, experts say[END_REF] a également renouvelé l'intérêt pour la RA en tant qu'outil de collaboration et communication [START_REF] Petre | The role of ar and vr in corporate communications[END_REF], étant intrinsèquement moins isolante que la RV. La RA soulève néanmoins des questions concernant l'incrustation réaliste de contenu virtuels dans une scène réelle [START_REF] Euronews | What's remote work like in the metaverse? these companies are building the tools to make it possible. euronews.next[END_REF].

Dans cette thèse, on utilisera le terme "Réalité Mixte" (RM) pour désigner les applications de RA cherchant à intégrer des éléments virtuels dans une scène réelle de manière photoréaliste. Le photoréalisme a été cité comme facteur d'immersion, quand les éléments virtuels se comportent également de manière réaliste [START_REF] Haller | Photorealism or/and non-photorealism in augmented reality[END_REF]. En effet, la RM a été utilisée dans des applications d'enseignement et de formation quand des situations réelles sont difficilement procurables [START_REF] Pratt | Developing an augmented reality environment for earth science education[END_REF][START_REF] Masrur | Immersive applications for informal and interactive learning for earth science[END_REF], ou présentent des dangers ou enjeux trop importants [START_REF] Stoyanov | Current issues of photorealistic rendering for virtual and augmented reality in minimally invasive surgery[END_REF]. De manière plus générale, le photoréalisme peut être bénéfique dans toutes les applications RA de prévisualisation ou simulation [START_REF] Agusanto | Photorealistic rendering for augmented reality using environment illumination[END_REF][START_REF] Li | Real-time occlusion handling for augmented reality assistance assembly systems with monocular images[END_REF][START_REF] Gimeno | An augmented reality (ar) cad system at construction sites[END_REF], ou quand il y a des enjeux esthétiques [START_REF] Dubská | Poor man's simulcam: Real-time and effortless matchmoving[END_REF][START_REF] Cook | Real-time photo-realistic augmented reality for interior design[END_REF][START_REF] Vazquez | Fused photo: Augmented reality staging for photorealistic visualization in online home retail[END_REF].

Les premiers travaux en RM [START_REF] Kanbara | Geometric and photometric registration for real-time augmented reality[END_REF][START_REF] Gibson | Photorealistic augmented reality[END_REF] s'attelaient au problème de réduction du temps de calcul pour accomplir trois tâches principales : l'estimation des paramètres de la caméra, la reconstruction de la géométrie de la scène, et l'estimation de son illumination [START_REF] Kanbara | Geometric and photometric registration for real-time augmented reality[END_REF][START_REF] Gruber | Efficient and robust radiance transfer for probeless photorealistic augmented reality[END_REF]. Contrairement à la RV, où la scène est entièrement modélisée au sein de l'application, une grande portion d'une scène de RA doit être reconstruite à partir d'observations partielles du monde réel. La qualité de cette reconstruction impacte directement le photoréalisme de tâches comme la gestion d'occlusions [START_REF] Wloka | Resolving occlusion in augmented reality[END_REF], la profondeur de champ [START_REF] Okumura | Augmented reality based on estimation of defocusing and motion blurring from captured images[END_REF], et l'éclairage simulé [START_REF] Kronander | Photorealistic rendering of mixed reality scenes[END_REF][START_REF] Agusanto | Photorealistic rendering for augmented reality using environment illumination[END_REF]. Par ailleurs, la modélisation de la scène devra également inclure des informations sémantiques pour garantir un réalisme "comportemental" [START_REF] Haller | Photorealism or/and non-photorealism in augmented reality[END_REF], affectant par exemple le placement des objets virtuels [START_REF] Lang | Virtual agent positioning driven by scene semantics in mixed reality[END_REF], leur comportement [START_REF] Chevaillier | Semantic modeling of virtual environments using MASCARET[END_REF], ou la simulation des interactions physiques [START_REF] Chen | Semantic augmented reality environment with material-aware physical interactions[END_REF]. La création d'un tel modèle en temps réel serait hors de la portée de la majorité des appareils de RA grand public, et dans une scène dynamique, le temps requis à chaque session de RA pour la scanner exhaustivement serait rédhibitoire.

Pour les applications de RM grand public, la solution est donc de conserver le modèle de la scène entre chaque session afin de pouvoir démarrer l'expérience immédiatement. Cependant, le modèle devra être régulièrement mis à jour afin de rester fidèle à la scène réelle, et trois problèmes seront à résoudre : créer une représentation de la scène permettant d'obtenir le niveau de réalisme souhaité;

détecter les changements entre la scène actuelle et le modèle, à partir d'observations partielles; modifier le modèle à partir des changements détectés en maintenant son degré de fidélité.

Le but de cette étude doctorale est donc de trouver une représentation de scène utile et maintenable pour la RM, et un processus à faible coût de calcul [START_REF] Simon | Automatic online walls detection for immediate use in ar tasks[END_REF] pour détecter les changements entre ladite représentation et des observations partielles de la scène réelle.

Il existe des travaux dont le but est de détecter des changements entre deux modèles d'une même scène, et d'agir en conséquence. En général, la nature de ces modèles dépend du domaine d'application de la méthode, car ce dernier impose des contraintes sur les moyens et le délai acceptables pour les produire. Certaines méthodes en navigation autonome [START_REF] Fuse | Development of a change detection method with lowperformance point cloud data for updating three-dimensional road maps[END_REF][START_REF] Postica | Robust moving objects detection in lidar data exploiting visual cues[END_REF] et robotique [START_REF] Tipaldi | Lifelong localization in changing environments[END_REF][START_REF] Qian | POCD: probabilistic object-level change detection and volumetric mapping in semi-static scenes[END_REF][START_REF] Fehr | Tsdf-based change detection for consistent long-term dense reconstruction and dynamic object discovery[END_REF]4,[START_REF] Katsura | Spatial change detection using voxel classification by normal distributions transform[END_REF][START_REF] Vaiapury | Can we speed up 3d scanning? A cognitive and geometric analysis[END_REF] comparent deux représentations 3D de l'environnement pour produire des résultats en 3D. Ces approches nécessitent cependant des capteurs spécifiques (LiDAR, laser) ou une puissance de calcul importante (algorithmes de shape-from-motion) pour fournir leurs résultats en temps réel, et sont difficilement applicables à la RM grand public. D'autres domaines d'application évitent ces coûts en utilisant des représentations 2D de la scène. En télédétection [START_REF] Daudt | Fully convolutional siamese networks for change detection[END_REF][START_REF] Daudt | Multitask learning for largescale semantic change detection[END_REF][START_REF] Gressin | Semantic approach in image change detection[END_REF][START_REF] De | Unsupervised change detection in satellite images using convolutional neural networks[END_REF][START_REF] Cheng | Semantic change pattern analysis[END_REF], des images aériennes sont utilisées et les résultats de la détection de changements sont similairement donnés en 2D au pixel-près. Pour des images produites au sol, notamment dans le domaine des villes intelligentes [START_REF] Guo | Learning to measure change: Fully convolutional siamese metric networks for scene change detection[END_REF][START_REF] Varghese | Changenet: A deep learning architecture for visual change detection[END_REF], des approches ont recours aux réseaux de neurones siamois pour être d'avantage robustes aux "pseudo-changements", introduisant ainsi la notion sémantique de pertinence des changements. La plupart des ces résultats ne sont cependant pas exploitables en RM sans avoir recours à une conversion coûteuse de la 2D à la 3D. Dans le contexte de la RM, où la quantité et qualité d'information disponible en temps réel est inférieure à celle contenue dans le modèle de référence, on peut utiliser des méthodes à données d'entrée hétérogènes [START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF][START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF][START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF]. Ces méthodes comparent des observations 2D à un modèle 3D afin d'obtenir directement des résultats sur la géométrie de la scène à moindre coût en termes de matériel ou calcul.

Parmi les travaux de détection de changements avec données hétérogènes, les approches photo-géométriques, qui comparent des images actuelles à un maillage 3D de référence, sont applicables au cas de la RM. Cependant, on remarque que ces méthodes, notamment celle proposée dans [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], sont souvent biaisées vers la détection d'objets apparaissant dans la scène, au détriments de ceux qui disparaissent. Notre première contribution sera donc la généralisation de cette méthode [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] vers une détection plus exhaustive des changements. Cette approche photo-géométrique est basée sur l'étude des erreurs introduites lors de la reprojection des images à différents points de vue à l'aide du maillage désuet. Les résultats 3D donnent une estimation de la forme et la position des objets ayant été introduits ou retirés dans la scène. Sur la base de cette première approche, on conclura que ce choix de représentation ne nous permettra pas d'obtenir une expérience photoréaliste en RA, et que le processus de détection de changements ne permet pas de la mettre à jour avec suffisamment de précision. Notre deuxième contribution sera ainsi l'introduction d'un modèle construit par analyse sémantique de la scène, fournissant une représentation segmentée par objets. On notera également l'évolution des appareils de RA grand public, auxquels auront été ajoutés de nouveaux capteurs 3D [START_REF] Wells | Apple doubles down on hardware with new ipad pro[END_REF]. Enfin, notre troisième contribution sera un processus de génération et exploitation de ce modèle, un "graphe de scène", pour la tâche de localisation dans une scène. Nous évaluerons si le graphe généré est fidèle à la sémantique de la scène réelle, afin de montrer que cette qualité du modèle peut être améliorée sans compromettre la précision de la localisation, ou sa robustesse aux changements dans des scènes dynamiques.

Détection de changements photo-géométrique

La méthode décrite dans [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] a été développée pour le domaine de la robotique et fonctionne en temps "interactif". Elle fait l'hypothèse de capteurs limités pendant l'observation de la scène : la détection de changements est faite entre un maillage 3D non-texturé désuet, et 5 images à jour, localisées relativement au maillage. A l'aide de cette localisation, on peut projeter les images d'un point de vue à un autre en utilisant la géométrie du maillage. Cependant, si des changements ont eu lieu, la reprojection aura des erreurs que l'on pourra détecter en comparant l'image projetée à une image de référence pour le point du vue étudié. Cette approche n'est pas efficace pour la détection des objets supprimés : ils sont présent dans le maillage mais pas dans les images, et donc n'introduisent pas de nouvelles textures qui pourraient donner lieu à de fortes incohérences photométriques. Notre contribution sera donc de permettre la détection des insertions et suppressions d'objets dans la scène, en améliorant tout d'abord l'algorithme de reprojection.

La reprojection de la méthode de l'état de l'art était faite en transformation "directe", où chaque pixel de l'image à transformer était déplacé dans l'image finale. Cela résulte en de nombreux pixels non coloriés dans l'image finale, qu'il faudrait interpoler : on utilise donc une transformation "inverse", où à chaque pixel de l'image finale est attribué un pixel de l'image à transformer. Certaines régions de l'image transformée resteront cependant non coloriées car elles correspondent à des régions 3D non visibles dans l'image de départ (car obscurcies par des objets au premier plan, ou en dehors de l'image). Déterminer si des régions sont visibles ou non se fait à l'aide d'un test de profondeur, et on remarque qu'en inversant ce test on peut donner à ces pixels la couleur des objets qui les masquent au premier plan. Cette reprojection alternative donne lieu à des images qu'on nomme "ombres texturées", et on remarque qu'en comparant ces ombres texturées à l'image de référence pour un point de vue donné, les régions cohérentes (en couleurs) correspondent aux régions des objets supprimés.

Pour un point de vue donné on peut donc produire une carte de détection de suppressions 2D. On prend une des 5 images comme référence, et on projette les 4 autres à ce point de vue (avec le test de profondeur inversé). Pour mesurer la cohérence, on crée 4 "delta maps" qui donnent la distance euclidienne pixel par pixel entre la valeur RGB dans la référence et celle dans une des 4 ombres texturées. Pour obtenir la position réelle des changements en 2D, on projette les pixels de ces delta maps au "premier plan", d'après le maillage et la caméra du point du vue étudié. On fusionne ces 4 delta maps de "premier plan" afin de réduire le bruit : on prend la valeur minimale de chaque pixel (les pixels non coloriés ayant une valeur maximale). Pour obtenir les suppressions d'objets en 2D, on fait un seuillage par valeur de pixel de cette delta map fusionnée. Contrairement à la méthode de [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], qui utilisait une valeur de seuil arbitraire, on effectue un seuillage automatique comme décrit dans [START_REF] Zack | Automatic measurement of sister chromatid exchange frequency[END_REF], le seuillage triangle.

Les pixels de la carte de suppression 2D sont groupés par régions par dilatation et érosion des pixels de changements. Une fois qu'une carte des régions de changements est générée pour les 5 points de vue, on peut obtenir les régions 3D en identifiant, à l'aide du maillage, quelles régions 2D correspondent au même changement 3D dans la scène. Une fois les régions identifiées, on crée des ellipsoïdes 3D décrivant la position et la taille des suppressions d'objets dans la scène, en utilisant l'algorithme de triangulation de [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF].

La méthode résultante peut être combinée avec l'approche de [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] avec un impact négligeable sur le temps de calcul, car les ombres texturées peuvent être générées en parallèle des images transformées de la méthode originale. On peut également améliorer la précision de la détection d'insertions en filtrant les résultats 2D avec nos résultats de détection de suppressions. Une implémentation de ce système complet a été réalisée sur GPU à l'aide de shaders, améliorant d'avantage la précision (la résolution des images transformées) et la vitesse.

Afin d'évaluer la qualité de la détection de suppressions, on utilise les métriques 2D proposées dans [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] : les ellipsoïdes sont projetés au point de vue de chaque image de la scène, et on calcule les Intersection over Union (IoU) et True Positive Rate (TPR) des régions de changements estimées avec celles de la vérité terrain. On modifie également le dataset d'origine afin d'introduire des suppressions d'objet dans les scènes (des objets sont rajoutés au maillage 3D), et on modifie des scènes d'un autre dataset : ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF]. Sur toutes ces scènes, notre méthode est capable de détecter des suppressions d'objets avec plus de précision et sensibilité que la méthode d'origine (respectivement 36% et 70% de IoU et TPR contre 12% et 22%). On évalue également positivement la qualité du choix de seuil automatique, à l'aide des courbes ROC (Receiver Operating Characteristic), comme décrit dans [START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF]. Notre méthode photo-géométrique est donc supérieure à l'état de l'art dans la majorité des cas, et est capable de différentier deux types de changements. Cependant, elle ne permet pas encore la mise à jour du maillage.

Description sémantique d'une scène

Les résultats de détection de changements de l'approche photo-géométrique ne sont pas suffisamment précis pour mettre à jour le maillage 3D de référence de la scène. Une analyse sémantique de cette scène permettrait de segmenter son contenu par objet pour améliorer l'approche. D'une part, les cartes de changements 2D pourraient être rendues plus précises en utilisant des contours d'objet obtenus à partir d'une segmentation 2D des images actuelles de la scène. D'autre part, un maillage 3D segmenté par objet serait plus simple à mettre à jour, en particulier pour le cas de la suppression ou du déplacement d'objets dans la scène. On note également que les résultats de l'analyse sémantique seraient exploitables pour localiser les images par rapport au maillage.

Au delà de l'amélioration de l'approche photo-géométrique, un modèle sémantique de la scène pourrait adresser le problème du réalisme comportemental des objets virtuels [START_REF] Haller | Photorealism or/and non-photorealism in augmented reality[END_REF] et leur attribuer des propriétés utiles en plus de leur géométrie (poids, matériaux, modèle photométrique). Une détection de changements ne peut être exhaustive pour toutes les applications de RM, et définir un "vocabulaire" pour la scène à l'aide de l'analyse sémantique permet d'identifier quelles propriétés sont pertinentes.

Afin d'organiser l'information sémantique, on utilise un graphe de scène. Un graphe de scène basique peut représenter les objets présents par ses sommets, et les relations entre ces objets par ses arrêtes. La représentation est cependant flexible et peut inclure des attributs et labels sur les sommets et arrêtes, ou avoir plusieurs couches représentant différents niveaux d'abstraction (les sommets pouvant représenter d'autres propriétés de l'environnement). Selon le domaine d'application, ces graphes peuvent être utilisés pour générer des scènes virtuelles (en rendu graphique [START_REF] Community | Blender -a 3D modelling and rendering package[END_REF][START_REF] Haas | A history of the unity game engine[END_REF]), ou pour décrire des scènes réelles (en robotique [START_REF] Kim | 3-d scene graph: A sparse and semantic representation of physical environments for intelligent agents[END_REF][START_REF] Yu | A bottom-up framework for construction of structured semantic 3d scene graph[END_REF]). En RA, ces deux cas d'usage sont pertinents, et l'utilisation de deux graphes permet également de faciliter les interactions entre le réel et le virtuel [START_REF] Royan | Towards an interoperable world representation for xr[END_REF].

Avec les avancées dans le domaine de la RA suivant le développement de notre première approche, on peut faire l'hypothèse que l'appareil de RA est capable de produire une carte de profondeur en plus de l'image RGB et de sa pose relative fournies par la caméra, et il existe des approches en robotique exploitant ces données d'entrée. La méthode décrite dans [START_REF] Kim | 3-d scene graph: A sparse and semantic representation of physical environments for intelligent agents[END_REF] génère des graphes (locaux) pour chaque image en entrée avec Factorizable-Net [START_REF] Li | Factorizable net: An efficient subgraph-based framework for scene graph generation[END_REF], et les fusionne dans un graphe 3D (global) en cherchant des sommets similaires dans ces graphes 2D. Cette mesure de similarité repose majoritairement sur le classe et la position absolue de l'objet représenté par le sommet, rendant son utilisation pour une relocalisation (ou détection de changements) entre différentes sessions de RA difficile. Les méthodes de localisation par graphe utilisent souvent uniquement ses attributs sémantiques et sa topologie pour comparer les sommets, cependant la topologie des graphes générés par [START_REF] Kim | 3-d scene graph: A sparse and semantic representation of physical environments for intelligent agents[END_REF] n'est pas assez informative. En effet, les graphes générés par Factorizable-Net [START_REF] Li | Factorizable net: An efficient subgraph-based framework for scene graph generation[END_REF] et d'autres méthodes 2D similaires se focalisent sur la description des actions dans la scène plutôt que sa structure, et les quelques arrêtes décrivant la structure 2D ne sont pas utilisables dans le graphe 3D ("à gauche de", "derrière"). Enfin, la génération de graphes 2D est trop instable d'une image à l'autre, et donnerait lieu à trop de faux positifs pour la détection de changements.

Suivant ces observations, on décide d'étudier les méthodes de génération de graphes utilisées pour la tâche de localisation plutôt que celle de description de scène, afin de favoriser la stabilité des graphes d'une session RA à la suivante. En conséquence, on choisit une représentation de graphe simple : les sommets ont deux attributs, un label et un vecteur 3D de position, et les arrêtes sont non-directionnelles et basées sur un seuil de proximité entre les sommets. Pour notre application, les méthodes de localisation par graphe devront pouvoir identifier les changements dans une scène, et pas seulement les ignorer pour des besoins de stabilité, mais également produire des graphes suffisamment fidèles à la scène pour être utiles en RM. On identifie 4 problèmes à résoudre pour l'utilisation de graphes sémantiques en détection de changements pour la RM: détecter les changements entre deux graphes de scène complets; détecter les changements entre un graphe partiel et un graphe de référence complet; créer un graphe partiel à partir des observations à l'aide de la référence complète; mettre à jour la géométrie du modèle de scène à partir de changements sémantiques.

Graphes pour l'alignement de modèles de scènes sémantiquement denses

Afin de résoudre le premier des 4 problèmes énoncés précédemment, et tester le modèle de scène choisi, on s'intéresse au problème de la localisation relative de deux vidéos par graphe. Dans ce problème, la pose locale de la caméra est connue dans le référentiel d'une vidéo donnée, mais la transformation 3D nécessaire pour passer du référentiel d'une vidéo à celui d'une autre est inconnue. Pour le résoudre, chaque vidéo est convertie en graphe de scène et les sommets (objets) similaires entre les deux graphes sont identifiés, et leur position relative dans le référentiel de chaque vidéo est utilisé pour calculer la matrice de transformation 3D.

La similarité entre deux sommets est quantitativement évaluée à l'aide de descripteurs, qui encodent pour chaque sommet la classe de l'objet qu'il représente (le label), ainsi que les classes des objets voisins d'après la topologie du graphe. Certains descripteurs se limitent aux voisins directs [START_REF] Stumm | Robust visual place recognition with graph kernels[END_REF], mais d'autres explorent la topologie locale du graphe par parcours aléatoire [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF][START_REF] Liu | Global localization with object-level semantics and topology[END_REF][START_REF] Wang | Lightweight objectlevel topological semantic mapping and long-term global localization based on graph matching[END_REF] ou exhaustivement [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF]. L'approche exhaustive est cependant limitée par la taille du descripteur qui croît en l d avec l le nombre de labels utilisés lors de l'analyse sémantique, et d la profondeur d'exploration (d -1 "pas" depuis le sommet d'origine). L'estimation de la transformation 3D est généralement évaluée avec l'erreur de translation par rapport à la vérité terrain, mais il existe des métriques plus informatives appliquées au problème d'alignement de nuages de points, notamment la RMSD (Root-Mean-Square Deviation) [START_REF] Myronenko | Point set registration: Coherent point drift[END_REF] qui moyenne l'erreur de position à chaque point du nuage.

Pour le cas des scènes en intérieur, qui sont sémantiquement riches et où l'erreur de translation n'est pas suffisante, on va donc contribuer un nouveau descripteur de sommet non-aléatoire dont la taille croît en l × d, ainsi qu'une métrique dérivée de la RMSD sur nuages de points. Enfin, on propose un nouveau processus de génération de graphes afin de produire des graphes de scènes exploitables au delà de la tâche de la localisation, comme représentation fidèle de la scène. Notre système complet, similaire à ceux décrits dans [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] et [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF] a 3 parties : l'extraction de graphes à partir de vidéos, la génération de descripteurs et l'isomorphisme de sous-graphes pour les graphes générés, et enfin l'estimation de la transformation 3D basée sur les sommets sémantiquement similaires.

Pour la génération de graphes, la vidéo en entrée est composée de cartes de segmentation par objets issues d'une analyse sémantique préalable, ainsi que des cartes de profondeur et poses de caméra (dans le référentiel de la vidéo) correspondantes. On peut générer des points 3D correspondant aux objets visibles dans une image en calculant les barycentres 2D des régions sémantiquement uniformes, et en extrapolant leurs positions 3D dans la scène à partir de la carte de profondeur et de la caméra. D'une image à la suivante, les mêmes objets restent souvent visibles, donc [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] ignore les nouveaux points 3D si ces derniers sont trop proches d'un point 3D précédemment observé avec le même label, d'après un seuil de proximité. En conséquence, la première observation d'un objet donne sa position 3D (son attribut spatial dans le graphe de scène) et est souvent approximative car généralement les objets sont d'abord partiellement visibles aux bords de l'image, et de plus, les objets plus grands que le seuil de proximité sont fragmentés en plusieurs sommets.

Notre approche alternative consiste à ne pas ignorer les nouveaux points 3D similaires, mais à les regrouper sous un même "super-sommet", dont l'attribut spatial est la moyenne de ces points 3D. Par ailleurs, on peut alors utiliser tous ces points 3D pour le test de proximité, et ainsi les grands objets ne sont plus fragmentés, et ont un attribut spatial plus proche de leur véritable barycentre 3D. La génération du graphe se termine avec l'ajout d'arêtes selon un autre seuil de proximité automatiquement calculé à partir de la distance moyenne entre les sommets. Le graphe est donc représenté par une matrice d'adjacence A binaire, symétrique et à diagonale nulle, et par un vecteur de labels, respectivement de taille n × n et n, le nombre de sommets.

Pour l'alignement des deux graphes, les descripteurs sont générés à partir des puissances A k de la matrice d'adjacence, où A k i,j donne le nombre de chemins de longueur k entre les sommets i et j du graphe. Pour chaque k < d, on va encoder l'histogramme des labels des sommets atteignables depuis le sommet étudié dans un vecteur de longueur l. On va également encoder le label du sommet en question avec un vecteur one-hot (de taille l), qu'on peut concaténer avec les d -1 histogrammes de voisinage, obtenant ainsi un descripteur de taille d × l.

Les méthodes de parcours aléatoire [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF] introduisent des règles d'exploration du graphe pour favoriser l'encodage d'information pertinente dans les descripteurs : on peut simuler ces règles en utilisant des variantes de la matrice d'adjacence. On crée les matrices B (k) qui approximent une exploration du graphe avec la règle "on ne peut pas passer deux fois par la même arrête". On pondère également les contributions des histogrammes de voisinage par l'inverse de la profondeur k qu'ils représentent, afin de réduire les erreurs dues aux approximations des B (k) ou à l'homogénéisation des A k pour les grandes valeurs de k. Les calculs matriciels sont accélérés en utilisant des opérateurs de logique booléenne, car les descripteurs ne sont pas affectés par le nombre de chemins entre deux sommets, seulement par leur existence.

Lors de la recherche d'isomorphisme de sous-graphes, la similarité entre deux sommets est donnée par le produit scalaire de leurs descripteurs respectifs. Une fois les sommets les plus similaires entre les deux graphes identifiés, on peut calculer la transformation 3D entre les référentiels de leurs vidéos respectives par régression à partir des attributs spatiaux (les coordonnées 3D des objets). Les couples de sommets dont les coordonnées sont des données aberrantes pendant la régression (erreurs d'extraction, changements dans la scène) peuvent être filtrés par algorithme de RANSAC [START_REF] Besl | A method for registration of 3-d shapes[END_REF] pour améliorer la localisation. Cependant, n'ayant pas de vérité terrain pour l'isomorphisme de sous-graphes, on rend cette option optionnelle afin de mieux évaluer la performance des descripteurs à partir de la vérité terrain de localisation.

L'erreur de localisation est calculée à partir d'une intégration formelle de la RMSD sur le volume de la scène, plutôt d'une sommation des erreurs sur les points du maillage ou nuage qui la représenterait. Une telle méthode est décrite dans [START_REF] Jenkinson | Measuring transformation error by rms deviation[END_REF] pour l'alignement de cerveaux représentés par des sphères, prenant ainsi en compte les possibles erreurs de translation et rotation. Nous adaptons cette méthode pour l'appliquer à la localisation dans des scènes en intérieur, qui sont alors modélisées par des parallélépipèdes à 3 dimensions. L'erreur correspond à l'intégrale sur ce volume de l'écart entre un point transformé par notre estimation et le même point transformé par la vérité terrain : elle est donc indépendante du contenu de la scène mais dépend de ses proportions.

On évalue notre méthode de localisation sur deux datasets de scènes en intérieur : ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] et ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF], contenant respectivement des scènes réelles et des scènes d'entrepôts virtuelles. Pour ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF], on calcule la vérité terrain d'alignement, et on utilise la vérité terrain de segmentation par instance d'objet pour comparer la fidélité des graphes de sommets de [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] et de nos super-sommets à la scène réelle. Pour ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF], on calcule les trajectoires de caméra, et on teste la robustesse de notre système à la présence de changements dans la scène. La qualité des graphes est quantitativement évaluée avec le ARI (Adjusted Rand Index), et l'utilisation de nos super-sommets produit des graphes plus fidèles à la réalité (0.705 de ARI contre 0.599 pour [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF], 1 indiquant une corrélation maximale et 0 aucune corrélation). Pour la tâche de localisation, nos nouveaux descripteurs donnent de meilleurs résultats que ceux de [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] sur les deux datasets, pour des temps de génération et comparaison (et taille en mémoire) bien inférieurs. On note enfin que l'utilisation de super-sommets ne dégrade pas la performance de localisation, et ces derniers pourront donc servir pour cette tâche aussi bien que pour d'autres propres à la RM.

Conclusion et perspectives

Dans cette thèse, nous avons présenté de nouvelles méthodes pour s'atteler au problème de la détection de changements pour les applications de Réalité Mixte. Ces travaux ont été menés afin de fournir un processus de maintenance du modèle d'un environnement réel, qui contiendrait les informations nécessaires à l'atteinte du niveau de réalisme souhaité pour des applications de RM.

Dans une première partie, nous avons souligné les différences entre les données requises par les applications de RM, et celles qui peuvent être acquises à l'aide d'un appareil de RA, en implémentant une méthode de détection de changements qui compare deux états d'une même scène représentés par ces données hétérogènes. Nous avons représenté l'état "passé" de la scène par un maillage 3D non-texturé (requis pour un rendu photoréaliste mais difficile à scanner avec un appareil de RA) et l'état "présent" par une série d'images (nécessitant un simple caméra). Dans ce contexte, la représentation 3D peut être mise à jour en détectant uniquement la géométrie qui aurait été ajoutée ou supprimée entre les deux états. Nous avons utilisé notre propre approche basée sur la reprojection d'images, qui corrige le penchant [START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF] des méthodes similaires [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF][START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF] pour la détection de l'ajout de géométrie, au détriment de la suppression.

A la fin des ces travaux sur la comparaison du maillage 3D à une série d'images, nous avons noté que notre analyse photo-géométrique ne pourrait pas fournir des résultats suffisamment précis pour mettre à jour la géométrie du modèle de scène. Nous avons donc conclu dans une deuxième partie qu'une connaissance du contenu sémantique de la scène, et une segmentation 3D et 2D (par objet) des données du modèle associé, nous permettraient de maintenir la fidélité de ce modèle vis-à-vis de l'environnement réel après sa mise à jour. Nous avons choisi de représenter la scène par un graph sémantique, où les sommets représentent des objets et les arrêtes les relations (spatiales) entre ces objets. Ce graphe de scène est mis à jour par une analyse sémantique de la scène, qui nous permet de définir quels changements sont "pertinents" (ceux qui affecteraient l'expérience de RM) et d'améliorer le réalisme comportemental des objets virtuels.

Enfin, nous avons introduit dans une troisième partie, une méthode pour aligner ces graphes sémantiques par l'identification de sommets similaires. En partant du principe que les appareils de RA modernes seraient maintenant équipés d'un LiDAR ou de caméras stéréoscopiques (contrairement à la première partie) nous avons présenté une nouvelle méthode de génération de graphes à partir de séries d'images RGB-D. Dans la même partie, nous avons également introduit un nouveau descripteur de sommet qui permet de mesurer la similarité entre les objets (sommets des graphes de scène) extraits de deux différentes séries RGB-D. A l'aide des méthodes proposées, deux modèles d'une scène peuvent être comparés et alignés par comparaison sémantique de leurs graphes, et du contenu virtuel persistant peut être réintégré à la scène à chaque session de RA.

En conclusion, à l'aide des nouvelles hypothèses introduites dans la deuxième partie, l'approche photo-géométrique de la première partie de détection de changements pourrait être utilisée sur un maillage segmenté par objet, ouvrant une opportunité pour sa maintenance sans perdre en fidélité. De plus, avec la présence de ces objets sous forme de sommets dans le graphe de scène, la localisation des images à jour, nécessaire pour le bon fonctionnement de l'approche photo-géométrique, pourrait être prise en charge par le système de localisation de la troisième partie. En cas de changements dans la scène, les objets retirés peuvent être simplement supprimés d'un maillage de scène segmenté, et les objets qui se déplacent dans la scène peuvent être similairement déplacés dans le maillage. Si l'appareil de RA est capable d'obtenir des images RGB-D pour la génération de graphe (comme dans la troisième partie), nous avons également accès à des informations géométriques 3D pour mettre à jour le maillage en cas d'ajout d'objet. En principe, une fois le problème de la détection de changements sémantiques dans la scène résolu, un modèle de scène segmenté pourrait être entièrement mis à jour pour des applications de RM dans des scènes changeantes.

Ce problème de la détection de changements sémantiques a été partiellement adressé par notre système d'alignement de graphes. En effet, l'approche décrite dans la troisième partie nous permet de comparer et coupler les sommets de deux graphes de scène, en mesurant leur similarité à l'aide des descripteurs. Pour obtenir une véritable détection de changements, le système d'alignement devra être capable d'identifier les sommets rendu "uniques" (qui n'ont pas d'équivalent dans l'autre graphe) par des changements dans la topologie du graphe de scène. La qualité d'un tel système devra être évaluée à l'aide d'une vérité terrain d'isomorphisme de graphe plutôt que d'alignement de scène. Par la suite, pour vérifier sa viabilité dans le contexte de la RA, le système de localisation devra être capable de fonctionner avec une vue limitée de la scène actuelle (à comparer à une référence globale). Cette perspective peut être simulée si les séries d'images RGB-D utilisées dans la troisième partie sont tronquées, ne montrant ainsi que la portion de l'environnement visible pendant une courte période. Cette hétérogénéité entre les observations et la référence conduira à un gain d'importance de cette dernière lors de l'analyse sémantique et géométrique de la scène, afin de définir les régions d'intérêt pour la détection de changements, basées sur les données contenues dans le modèle. Enfin, si on peut faire l'hypothèse que le modèle initial de la scène est "parfait" dans sa représentation des données requises pour la RM (le maillage, la topologie du graphe, les attributs des sommets...), un ultime problème serait de le garantir après plusieurs mises à jour successives. Les méthodes de détection de changements et le modèle de scène devront donc être choisis pour préserver la qualité de ce dernier sur plusieurs itérations, ou être capables de comparer deux états de la scène sur une plus longue période si le modèle d'origine (parfait) est toujours utilisé comme référence.

Une fois ces défis relevés, il sera possible d'envisager différentes extensions pour le modèle de scène, afin d'améliorer les interactions entre les éléments virtuels et réels, ainsi qu'avec l'utilisateur final. Notre modèle de scène ayant été inspiré par des avancements dans le domaine de la robotique, il pourrait également y être utilisé comme medium de traduction homme-machine pour la perception de l'environnement. Plus généralement, ce modèle est un outil pour communiquer l'information concernant une scène, et malgré le volume important des données 2D et 3D, le contenu sémantique et son organisation sont représentés efficacement par un graphe. En outre, un modèle prévu pour surveiller les changements dans une scène peut s'avérer efficace pour transmettre des instruction pour la modifier (i.e. prescrire des changements plutôt que les décrire). Avec une compréhension exhaustive de la scène au niveau sémantique, une grande partie des changements géométriques et sémantiques nécessaires à la description de ses portions dynamiques peut être résumée en une liste de changements sémantiques.

Introduction

After the resurgence of public interest in Virtual Reality (VR) following the 2016 launches of the Oculus Rift and HTC VIVE devices, the field of Augmented Reality (AR) also saw an attention gain despite earlier commercial failures [START_REF] Bilton | Why google glass broke[END_REF] for its own immersive capabilities [START_REF] Dave | Microsoft's answer to google glass: Hololens[END_REF]. This eventually resulted in the 2017 release of Microsoft's head-mounted display (HMD), the HoloLens, and Apple's ARKit development toolkit for their existing hand-held products -and its Android counterpart ARCore the following year-leading to the development of AR applications with broad appeal. The increase in remote work in the last few years [START_REF] Robinson | Remote work is here to stay and will increase into 2023, experts say[END_REF] has also renewed interest in AR as a collaboration and communication tool [START_REF] Petre | The role of ar and vr in corporate communications[END_REF] with its innate feature of letting reality through, distinguishing it from the more isolating VR experience. One of the concerns for AR applications is the seamless integration of virtual content into a real scene, such as realistically behaving user avatars [START_REF] Euronews | What's remote work like in the metaverse? these companies are building the tools to make it possible. euronews.next[END_REF].

In this thesis, we will use the term "Mixed Reality" (MR). Among its many definitions [START_REF] Speicher | What is mixed reality?[END_REF], we will consider MR as a branch of AR with a focus on immersivity through the blending of real and virtual elements in a photo-realistic manner. Photo-realism has been claimed to engage AR users by giving them a sense of "being there" as opposed to more stylized representations [START_REF] Haller | Photorealism or/and non-photorealism in augmented reality[END_REF]. Nevertheless the immersion is more easily broken as realistic behaviour is also expected [START_REF] Haller | Photorealism or/and non-photorealism in augmented reality[END_REF]. However, when both visual and behavioural realism are achieved, so-called Mixed Reality becomes a powerful and versatile tool. It has notably given birth to applications such as teaching in fields where real world experiences cannot be conveniently provided, such as in the study of far-away or otherwise unreachable spaces [START_REF] Pratt | Developing an augmented reality environment for earth science education[END_REF][START_REF] Masrur | Immersive applications for informal and interactive learning for earth science[END_REF], or in dangerous and high-stakes occupations. In medical training for instance, where there was once a need for dedicated tools for either realistic visualization or accurate mechanical simulation because of technological limitations, it has long been possible to merge the two tasks into a more encompassing teaching medium [START_REF] Stoyanov | Current issues of photorealistic rendering for virtual and augmented reality in minimally invasive surgery[END_REF]. More generally, photo-realism can be desirable in any AR application [START_REF] Agusanto | Photorealistic rendering for augmented reality using environment illumination[END_REF] involving previsualization and layout planning such as machining [START_REF] Li | Real-time occlusion handling for augmented reality assistance assembly systems with monocular images[END_REF] and construction [START_REF] Gimeno | An augmented reality (ar) cad system at construction sites[END_REF]. It is also relevant when there are aesthetic concerns e.g., in visual effect production [START_REF] Dubská | Poor man's simulcam: Real-time and effortless matchmoving[END_REF], for interior design [START_REF] Cook | Real-time photo-realistic augmented reality for interior design[END_REF] or to showcase products in retail experiences [START_REF] Vazquez | Fused photo: Augmented reality staging for photorealistic visualization in online home retail[END_REF]. The work in this thesis is motivated by MR uses in both outdoor urban environments, such as for the study of cultural heritage and architecture [START_REF] Haugstvedt | Mobile augmented reality for cultural heritage: A technology acceptance study[END_REF], and in indoor scenes, such as for remote collaboration [START_REF] Lukosch | Collaboration in augmented reality[END_REF].

In early works [START_REF] Kanbara | Geometric and photometric registration for real-time augmented reality[END_REF][START_REF] Gibson | Photorealistic augmented reality[END_REF], photo-realism in AR was framed as a problem of balancing rendering time and accurately performing three main tasks: geometric registration (estimating the camera's parameters), geometric reconstruction (estimating the scene geometry), and photometric registration [START_REF] Kanbara | Geometric and photometric registration for real-time augmented reality[END_REF][START_REF] Gruber | Efficient and robust radiance transfer for probeless photorealistic augmented reality[END_REF] (estimating the scene illumination). Indeed, compared to a VR experience where every asset is designed by or known to the author and goes through the same rendering pipeline, parts of the AR experience belong to the physical world and their unknown properties must be inferred through partial observations (see Figure 1.1). Specifically, when AR users are free to move within the environment, rendering effects such as occlusion handling [START_REF] Wloka | Resolving occlusion in augmented reality[END_REF] and depth of field [START_REF] Okumura | Augmented reality based on estimation of defocusing and motion blurring from captured images[END_REF] are more realistically achieved with knowledge of the 3D geometry of the space, as well as the light sources and surface materials within it [START_REF] Kronander | Photorealistic rendering of mixed reality scenes[END_REF][START_REF] Agusanto | Photorealistic rendering for augmented reality using environment illumination[END_REF]. The results were then evaluated on an image-basis [START_REF] Gibson | Photorealistic augmented reality[END_REF], not accounting for some of the perceptual issues inherent to AR like virtual object presence and depth perception [START_REF] Knecht | A framework for perceptual studies in photorealistic augmented reality[END_REF]. These works would also leave the task of geometry reconstruction to the user [START_REF] Gibson | Interactive reconstruction of virtual environments from photographs, with application to scene-of-crime analysis[END_REF], allowing them to use the AR display as a 2D window for the insertion and manipulation of geometric primitives -roughly representing the objects in the scene-in order to build a so-called "scene-graph" and calibrate the camera for the geometric registration.

With more standardized hardware and extensive methods to achieve unassisted geometric registration [START_REF] Comport | Real-time markerless tracking for augmented reality: The virtual visual servoing framework[END_REF][START_REF] Wagner | Realtime detection and tracking for augmented reality on mobile phones[END_REF], the focus of research in MR rendering shifted towards illumination simulation [START_REF] Kronander | Photorealistic rendering of mixed reality scenes[END_REF] through analysis and modelling of the environment. These processes were increasingly complexified, starting with representing real objects with rough "phantom" models to accurately cast virtual shadows [START_REF] Haller | A real-time shadow approach for an augmented reality application using shadow volumes[END_REF][START_REF] Pessoa | Photorealistic rendering for augmented reality: A global illumination and BRDF solution[END_REF], then expanding the scene representation to include sky boxes and virtual light sources [START_REF] Pessoa | Photorealistic rendering for augmented reality: A global illumination and BRDF solution[END_REF], and eventually attempting to discard physical probes -such as reflective balls and fiducial markers [START_REF] Kanbara | Geometric and photometric registration for real-time augmented reality[END_REF][START_REF] Kán | High-quality reflections, refractions, and caustics in augmented reality and their contribution to visual coherence[END_REF]-by relying on real-time observations [START_REF] Gruber | Efficient and robust radiance transfer for probeless photorealistic augmented reality[END_REF][START_REF] Prakash | Gleam: An illumination estimation framework for real-time photorealistic augmented reality on mobile devices[END_REF][START_REF] Jachnik | Real-time surface light-field capture for augmentation of planar specular surfaces[END_REF].

For the virtual elements' behaviour to match their visual counterparts in terms of realism [START_REF] Haller | Photorealism or/and non-photorealism in augmented reality[END_REF] (e.g., object placement [START_REF] Lang | Virtual agent positioning driven by scene semantics in mixed reality[END_REF], agent interactions [START_REF] Chevaillier | Semantic modeling of virtual environments using MASCARET[END_REF], physics simulation [START_REF] Chen | Semantic augmented reality environment with material-aware physical interactions[END_REF]), the scene representation should include semantic information, requiring a low or highlevel interpretation of its contents. While such a "thorough" representation of the scene can be hand-crafted in static scenes and controlled environments [START_REF] Lepetit | Fully automated and stable registration for augmented reality applications[END_REF][START_REF] Kronander | Photorealistic rendering of mixed reality scenes[END_REF], dynamic environments would require real-time exhaustive 2D and 3D structure scanning and processing of the raw observations to produce it. This can be performed using additional sensors, such as time-of-flight or laser scanners [START_REF] Lepetit | Fully automated and stable registration for augmented reality applications[END_REF][START_REF] Kronander | Photorealistic rendering of mixed reality scenes[END_REF], or RGB-D cameras [START_REF] Gruber | Efficient and robust radiance transfer for probeless photorealistic augmented reality[END_REF], which might be absent or too rudimentary in a widespread (hand-held) consumer-level AR Cameras are represented as triangles, scene geometry as rectangles and light sources as circles. In the AR scene, the camera pose needs to be known relative to the real (red) and virtual (green) scenes. Real scene assets also need to be simulated (dashed shapes).

setup. Alternatively, vision-based methods (such as structure from motion [START_REF] Szeliski | Structure from motion[END_REF]) can be used by exploiting simple RGB images [START_REF] Nakashima | Augmented reality image generation with virtualized real objects using view-dependent texture and geometry[END_REF], but are computationally expensive and do not account for the difficulties of recovering geometry in areas not visible from the point of view of the AR device [START_REF] Gibson | Photorealistic augmented reality[END_REF]. Indeed, [START_REF] Rohmer | Interactive near-field illumination for photorealistic augmented reality on mobile devices[END_REF] resorts to using multiple external cameras and a personal computer to perform the computations then transmitted to the device, to answer for its lack of power. Finally, the OpenRooms framework was introduced in [START_REF] Li | Openrooms: An open framework for photorealistic indoor scene datasets[END_REF] to provide the means to generate a photo-realistic indoor scene dataset, with the aim to train machine learning models to perform inverse rendering and scene understanding for robotics and MR. However the synthetic scenes it can produce have yet to be used in that latter field. Were these technologies to become more accessible in the future, the time taken to thoroughly examine the scene would still be prohibitively long for most applications, if performed at each immersive session or for every change in very dynamic scenes. Consequently, a representation of the scene needs to be preserved between each session for the MR experience to be able to (re-)start immediately. While this strategy assumes that the representation is sufficiently consistent with the current scene's state to simulate the effects of what is out of view [START_REF] Gibson | Photorealistic augmented reality[END_REF], it will eventually require updating (as in Figure 1.2). The problem of providing an up-to-date representation of the environment to be used in MR applications can thus be broken down into three main issues: designing said representation to contain sufficient data about the scene to achieve the desired level of realism from its exploitation; detecting the relevant differences between the current and previous scene states from limited current observations and a more exhaustive but outdated representation; modifying the representation based on the detected changes to maintain its original level of fidelity to the scene.

There is a need for a representation of the scene prior -the reference state of the scenethat facilitates its own maintenance and use in an MR context. In this doctoral study, the goal is to find such a representation and design a process to detect changes between the prior and the real scene, to then update said prior with only a partial perception of the current state at low computational cost [START_REF] Simon | Automatic online walls detection for immediate use in ar tasks[END_REF].

There are existing works that deal with the detection of changes between a prior representation of a scene and a current one, whose results can be used to act on those inconsistencies. Some works which apply to surveillance or monitoring tasks [START_REF] Thomaz | Anomaly detection in moving-camera video sequences using principal subspace analysis[END_REF], only deal with anomaly detection. Alternatively, other works are geared towards making regular updates to the scene representation, but separate the tasks of Change Detection (CD) and scene model maintenance [START_REF] Taneja | Geometric change detection in urban environments using images[END_REF]. In this case, the maintenance step is performed by re-examining the areas of change with specialized equipment, while the detection step can be accomplished with a simpler device. In general, the types of representation that are used for the prior and current scene states depend on the target application field, as the application imposes constraints on the means and acceptable time required to build them. For the purposes of MR, changes must be detected using the limited data available at runtime: the current scene's state is only partially observable, and the "quality" of its representation is poorer than that of the prior. Said quality can be defined as the quantity of raw data that can be captured and its reliability, and is governed by the AR device's sensors and processing power.

The rest of this thesis will be organised as follows. Chapter 2 will be dedicated to the exploration of the most relevant CD methods as they relate to MR, as well as fields where CD is a central issue. To that purpose the chapter will be divided by the types of representation (3D geometry, 2D geometry, semantics, etc.) used to compare the reference and current scene states.

Geometric CD Correct occlusions

Incorrect occlusions Input: live RGB + outdated mesh Some of the mentioned prior works deal with CD using heterogeneous representations [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] (e.g., a 3D mesh prior against an up-to-date image sequence), and while the detected changes cannot be directly used to update the prior, the underlying speed and hardware constraints imposed on the method are close to our MR use-case. For this reason, this photo-geometric approach [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] will be expanded into a more complete CD framework, described in Chapter 3. The new method will resolve some of the limitations of the previous works in terms of types of changes detected -namely object removalwhile testing its efficiency in the field of AR in changing environments. The core concept of the photo-geometric CD is the reprojection of up-to-date images (observations) aided by an outdated untextured 3D mesh (prior representation) into different points of view, and the evaluation of photometric inconsistencies in the resulting images introduced by the changes in scene geometry between the observations and the prior. The results will be quantitatively evaluated thanks to the pixel-wise ground truth introduced through the simulation of changes in an existing real indoor scene dataset.

From these results, it will be determined that this preliminary choice of scene representation is not able to yield photo-realistic results in all cases, and more importantly is impractical to update using the detectable changes. Therefore in Chapter 4, we will investigate alternative representations that are better suited to our needs, by observing that semantic analysis allows for a more practical object-level understanding of the scene, and that mainstream AR devices have been equipped with hardware such as LiDAR sensors [START_REF] Wells | Apple doubles down on hardware with new ipad pro[END_REF] since the beginning of this thesis.

Chapter 5 will be dedicated to the process of generating the semantic scene graph and its application to geometric registration. We will evaluate the fidelity of graph scene models to the real environment, and show that it can be improved without compromising the registration accuracy, or its robustness to changes in non-static scenes.

Finally, we will present our conclusions in Chapter 6, and show how geometric and semantic CD can allow us to maintain a scene model for MR applications using our contributions: a complete geometric CD framework -for insertion and removal of geometry-that operates at interactive time with minimum hardware requirements, a semantic scene graph model tailored to the CD task in an AR setting emanating from a survey of such representations in other fields, a scene graph generation and registration framework that produces a multi-purpose graph representation without compromising the precision of scene alignment.

We will also describe the future works that can be built upon the results presented in this thesis.

Chapter 2

Related work

As mentioned in the previous chapter, the main challenges of MR are: geometric registration: aligning the virtual and real contents of the scene, geometric reconstruction: understanding the real scene's geometry, photometric registration: detecting and modelling the light sources in the real scene.

The task of Change Detection has been used as a proxy to tackle similar challenges in many different fields: previous results can be updated rather than reproduced. However, outside of the context of MR, CD can refer to a variety of processes, involving the comparison of different types of input data and detection results tailored to specific applications.

For instance, in medical analysis or manufacturing monitoring, CD can be synonymous with anomaly detection between two images, and the expected result can be a caption -verbal description-of the changes [START_REF] Liao | Scene graph with 3d information for change captioning[END_REF]. Furthermore, in applications such as land surface remote sensing, where the changing nature and borders of terrains are extensively studied [START_REF] Kim | Graph neural network based scene change detection using scene graph embedding with hybrid classification loss[END_REF][START_REF] Cheng | Semantic change pattern analysis[END_REF][START_REF] Chen | Dasnet: Dual attentive fully convolutional siamese networks for change detection of high resolution satellite images[END_REF][START_REF] De | Unsupervised change detection in satellite images using convolutional neural networks[END_REF], in order to apply CD to scene analysis, the changes are expected to convey precise geometric information (e.g., a pixel map aligned with the input aerial images). Indeed, these works often deal with aligned image pairs, as the conditions of observation can be reproduced over time.

In contrast, the most susceptible fields to address the challenges of MR are those of ground-based applications, as 3D geometry and semantic analysis become more relevant when scanning [START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF] -or rendering-is performed from the ground: the perspective most AR users are expected to have. There are numerous works dealing with CD as it applies to smart cities [START_REF] Varghese | Changenet: A deep learning architecture for visual change detection[END_REF][START_REF] Ku | SHREC 2021: 3d point cloud change detection for street scenes[END_REF][START_REF] Vaiapury | Can we speed up 3d scanning? A cognitive and geometric analysis[END_REF][START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF], autonomous vehicles [3,[START_REF] Fuse | Development of a change detection method with lowperformance point cloud data for updating three-dimensional road maps[END_REF][START_REF] Postica | Robust moving objects detection in lidar data exploiting visual cues[END_REF] and human-robot collaboration in a shared space [START_REF] Looper | 3d VSG: long-term semantic scene change prediction through 3d variable scene graphs[END_REF][START_REF] Qian | POCD: probabilistic object-level change detection and volumetric mapping in semi-static scenes[END_REF][START_REF] Fehr | Tsdf-based change detection for consistent long-term dense reconstruction and dynamic object discovery[END_REF]4], as it makes localisation more robust and improves adaptability and interactivity. The following tables showcase the various input data types used that are compared by the CD algorithms of each previously mentioned fields (Table 2.1), as well as the nature of the CD results (Table 2.2). images [START_REF] Varghese | Changenet: A deep learning architecture for visual change detection[END_REF], point clouds [START_REF] Ku | SHREC 2021: 3d point cloud change detection for street scenes[END_REF][START_REF] Vaiapury | Can we speed up 3d scanning? A cognitive and geometric analysis[END_REF], both [START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF] Autonomous vehicles images [3,[START_REF] Blakeslee | Lambdanet: A novel architecture for unstructured change detection[END_REF], point clouds [START_REF] Fuse | Development of a change detection method with lowperformance point cloud data for updating three-dimensional road maps[END_REF], both [START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF][START_REF] Postica | Robust moving objects detection in lidar data exploiting visual cues[END_REF][START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF] Robotics 3D map and RGB-D images [4,[START_REF] Fehr | Tsdf-based change detection for consistent long-term dense reconstruction and dynamic object discovery[END_REF][START_REF] Qian | POCD: probabilistic object-level change detection and volumetric mapping in semi-static scenes[END_REF][START_REF] Katsura | Spatial change detection using voxel classification by normal distributions transform[END_REF] pixel map [START_REF] Varghese | Changenet: A deep learning architecture for visual change detection[END_REF][START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF], objects [START_REF] Ku | SHREC 2021: 3d point cloud change detection for street scenes[END_REF], vertices [START_REF] Vaiapury | Can we speed up 3d scanning? A cognitive and geometric analysis[END_REF] Autonomous vehicles pixel map [3,[START_REF] Blakeslee | Lambdanet: A novel architecture for unstructured change detection[END_REF][START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF][START_REF] Postica | Robust moving objects detection in lidar data exploiting visual cues[END_REF], vertices [START_REF] Fuse | Development of a change detection method with lowperformance point cloud data for updating three-dimensional road maps[END_REF], voxels [START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF] Robotics 3D objects [4,[START_REF] Fehr | Tsdf-based change detection for consistent long-term dense reconstruction and dynamic object discovery[END_REF][START_REF] Qian | POCD: probabilistic object-level change detection and volumetric mapping in semi-static scenes[END_REF][START_REF] Katsura | Spatial change detection using voxel classification by normal distributions transform[END_REF] Of note, these works assume semi-static input scenes, as opposed to dynamic ones. This means that detectable changes only occur between observations [START_REF] Tipaldi | Lifelong localization in changing environments[END_REF], and CD is performed between two static states: a prior -or "reference"-and a current -or "query"state. Depending on the type of scenes, we have identified three prevailing combinations of input data used for semi-static CD: homogeneous 3D representations for both states, homogeneous 2D representations, or heterogeneous representations between the two states. The following sections will give an overview of existing CD methods grouped according to those input data types, and assert their applicability to MR applications.

Change detection with 3D data

In the fields of self-driving vehicles [START_REF] Fuse | Development of a change detection method with lowperformance point cloud data for updating three-dimensional road maps[END_REF][START_REF] Postica | Robust moving objects detection in lidar data exploiting visual cues[END_REF] or robotics [START_REF] Tipaldi | Lifelong localization in changing environments[END_REF][START_REF] Qian | POCD: probabilistic object-level change detection and volumetric mapping in semi-static scenes[END_REF][START_REF] Fehr | Tsdf-based change detection for consistent long-term dense reconstruction and dynamic object discovery[END_REF]4,[START_REF] Katsura | Spatial change detection using voxel classification by normal distributions transform[END_REF][START_REF] Vaiapury | Can we speed up 3d scanning? A cognitive and geometric analysis[END_REF], CD is often performed directly between 3D representations of the environment in order to directly obtain 3D results. This is achieved by equipping the autonomous device with laser or LiDAR sensors or RGB-D cameras, and CD is usually used to maintain an accurate or otherwise "useful" map of the environment. More generally, many such methods use point clouds [START_REF] Fuse | Development of a change detection method with lowperformance point cloud data for updating three-dimensional road maps[END_REF]4] or voxel grids [START_REF] Fehr | Tsdf-based change detection for consistent long-term dense reconstruction and dynamic object discovery[END_REF] to compare observations of the environment in different states -with short [START_REF] Postica | Robust moving objects detection in lidar data exploiting visual cues[END_REF], long [4] or indeterminate [START_REF] Schauer | Removing non-static objects from 3d laser scan data[END_REF] elapsed time between them. When the observations are global (i.e., not partial) the data may still require alignment, which is achievable through gravitational registration [START_REF] Vaiapury | Can we speed up 3d scanning? A cognitive and geometric analysis[END_REF]. If the data are point clouds, temporal changes can be detected using a displacement threshold on the points' coordinates [START_REF] Vaiapury | Can we speed up 3d scanning? A cognitive and geometric analysis[END_REF]. While this approach gives an exact localisation of the changes -the displaced points-it requires an exact matching of all points between the compared point clouds, and therefore processing of the input 3D data if it is not synthetic. Assuming that the observations are already aligned, other works use Growing Least Square reconstruction [START_REF] Palma | Detection of geometric temporal changes in point clouds[END_REF] on the clouds which do not necessarily share the same exact points due to the random nature of laser scanning. A segmentation of the scene into "objects" is performed and then compared at different times, but the method is not meant to run in real time -despite speed improvements using downsampling-and requires noiseless and global clouds.

However, in the aforementioned fields, the more recent models of the scene are expected to be partial due to the limited field-of-view of the observation device. The registration of the data is done through localisation of the observer, using for instance SLAM [START_REF] Fehr | Tsdf-based change detection for consistent long-term dense reconstruction and dynamic object discovery[END_REF], pose graphs [START_REF] Qian | POCD: probabilistic object-level change detection and volumetric mapping in semi-static scenes[END_REF] or normal distribution transforms on a voxelized map of the scene [START_REF] Katsura | Spatial change detection using voxel classification by normal distributions transform[END_REF]. For example, by converting the input data to said 3D grid representation, [START_REF] Katsura | Spatial change detection using voxel classification by normal distributions transform[END_REF] is able to quickly perform CD and robust localisation by comparing the occupation of the voxels in the prior and current states. In the work, this allows the robot to compare a dense point cloud to up-to-date 3D range data from an onboard Kinect camera, but despite good performance on localisation, changes of small size will be undetected if the voxels are oversized due to speed requirements. For a more granular representation of the scene, a Truncated Signed Distance Function is often used [START_REF] Qian | POCD: probabilistic object-level change detection and volumetric mapping in semi-static scenes[END_REF][START_REF] Fehr | Tsdf-based change detection for consistent long-term dense reconstruction and dynamic object discovery[END_REF]4] and offers more precise CD results than the simple occupation of the grid's voxels. The CD results are further improved and filtered in [START_REF] Qian | POCD: probabilistic object-level change detection and volumetric mapping in semi-static scenes[END_REF] by clustering semantically consistent 3D input data into "objects", providing the robot with an up-to-date and segmented representation of its working environment to accurately navigate and perform tasks. When scanning the scene, said objects are stored in a library, which allows them to be recognized when they are encountered at a later time (using iterative closest point). This tracking of the movements of unique objects greatly improves the precision of the updated 3D map, but comes at a great computational cost as the number of objects increases. In earlier works [START_REF] Fehr | Tsdf-based change detection for consistent long-term dense reconstruction and dynamic object discovery[END_REF]4], the application of CD to map reconstruction differs slightly as it serves to filter out dynamic objects and obtain a "static map" of the scene. As a result, their methods are less computationally intensive than that of [START_REF] Qian | POCD: probabilistic object-level change detection and volumetric mapping in semi-static scenes[END_REF], but much less versatile or robust to dynamism in the scene, and produce more reconstruction artefacts.

Expanding the scope of this section to works dealing with "dynamic" scenes, we can also find relevant methods which still compare successive 3D scene observations, albeit on a shorter time scale. In [START_REF] Schauer | Removing non-static objects from 3d laser scan data[END_REF], different point clouds are turned into voxel grids, and the identification of "see-through" voxels provides the localisation of dynamic points.

In this context, see-through voxels contain points at a given time but do not prevent the device from capturing points located behind them at a different time, inducing the removal of their content. The authors also introduce the notion of "point shadow" that represents the ability of a 3D point to occlude parts of a scene from a given point of view. This multi-angle approach is however very costly in terms of memory, as it requires the storage of multiple points clouds at different known vantage points, since merging them into a single 3D map before CD would not allow to method to check for see-through voxels. The method described in [START_REF] Postica | Robust moving objects detection in lidar data exploiting visual cues[END_REF] detects dynamic objects in a point cloud as well, but also takes advantage of an RGB camera and real-time depth information to track patches of similar color in RGB or similar depth in a depth map. Although this makes the method perform in real time, the work does not focus on comparison to a prior map, and is not directly usable as a map reconstruction or maintenance framework. Finally, machine learning tools have more recently been introduced to process 3D data, such as PointNet [START_REF] Charles | Pointnet: Deep learning on point sets for 3d classification and segmentation[END_REF] and its variants [5,[START_REF] Li | Pointnetlk revisited[END_REF] and RPM-Net [START_REF] Yew | Rpm-net: Robust point matching using learned features[END_REF]. Convolution networks have therefore been used for CD with point clouds [START_REF] Ku | SHREC 2021: 3d point cloud change detection for street scenes[END_REF], taking into account the color and geometry of the compared object pairs in the environment. However these methods remain demanding computationally and hardware-wise. While some of these issues are addressed in [START_REF] Lin | Point cloud change detection with stereo V-SLAM: dataset, metrics and baseline[END_REF], where the current 3D observations are derived from stereovision over several frames, there exist more lightweight representations and methods for CD. Indeed, if 3D geometric information is very relevant to MR applications -for photorealism concerns-its scanning and manipulation comes at too great a computational cost in most situations. Moreover, these works are not themselves focused on producing a realistic model of the scene, and therefore rarely deal with the textures of the scene, or its light sources.

Change detection with 2D data

Avoiding the need for specialized 3D capture equipment, many CD techniques rely on the comparison of two pictures, particularly in the remote sensing field [START_REF] Daudt | Fully convolutional siamese networks for change detection[END_REF][START_REF] Daudt | Multitask learning for largescale semantic change detection[END_REF][START_REF] Gressin | Semantic approach in image change detection[END_REF][START_REF] De | Unsupervised change detection in satellite images using convolutional neural networks[END_REF][START_REF] Cheng | Semantic change pattern analysis[END_REF]. Many modern 2D methods are based on the use of Siamese Neural Networks, which can provide pixel-wise CD results. In [START_REF] Daudt | Fully convolutional siamese networks for change detection[END_REF], such networks are employed to compare two coregistered RGB or multi-spectral aerial images. More recent work focuses on developing robustness to pseudo changes [START_REF] Chen | Dasnet: Dual attentive fully convolutional siamese networks for change detection of high resolution satellite images[END_REF]. This notion is significant for the street-level applications in the smart city field [START_REF] Guo | Learning to measure change: Fully convolutional siamese metric networks for scene change detection[END_REF][START_REF] Varghese | Changenet: A deep learning architecture for visual change detection[END_REF], where images are less "flat": neighbouring pixels can represent 3D regions separated by large distances. In this situation, even slight lighting or viewpoint changes are likely to introduce noticeable -yet likely irrelevantchanges. Other works build on the foundation of Siamese networks to generalize the CD process, such as in [START_REF] Guo | Learning to measure change: Fully convolutional siamese metric networks for scene change detection[END_REF], where picture registration is not mandatory, and in [START_REF] Varghese | Changenet: A deep learning architecture for visual change detection[END_REF], where object segmentation is performed, making the approach more robust to changes in weather or scene illumination. The method from [START_REF] Guo | Learning to measure change: Fully convolutional siamese metric networks for scene change detection[END_REF] is also mostly robust to large viewpoint changes, being able to differentiate noise from meaningful changes. It is however not due to a 3D understanding of the images' contents but rather a robustness inherent to the large receptive field of its Convolutional Neural Network, and the focus on semantic analysis during training.

Efforts have also been made to further describe the nature of the changes themselves -rather than the objects affected. For instance, in [START_REF] Blakeslee | Lambdanet: A novel architecture for unstructured change detection[END_REF] the notion of "directional change" is introduced, which describes whether the change is detected due to the removal, the insertion or the exchange of pixels belonging to foreground objects. This is indeed more challenging using 2D data, since voxel grids or point clouds already represent geometry, and insertion and removals can be inherently inferred after CD. Moreover, several semantic-based 2D methods have been developed, which focus on the nature of the elements of a scene, for satellite [START_REF] Cheng | Semantic change pattern analysis[END_REF][START_REF] Daudt | Multitask learning for largescale semantic change detection[END_REF][START_REF] Gressin | Semantic approach in image change detection[END_REF] or ground-level images [START_REF] Sakurada | Weakly supervised silhouette-based semantic scene change detection[END_REF]. This approach is also put to use for unsupervised training [START_REF] De | Unsupervised change detection in satellite images using convolutional neural networks[END_REF], where such pictures are artificially altered with patches of different nature. The nature of change is further explored in change captioning methods, and more generally approaches used for captioning pairs of images. In [START_REF] Kataoka | Semantic change detection with hypermaps[END_REF], the nature of the semantically identified objects informs the nature of the change, whereas in [START_REF] Park | Robust change captioning[END_REF] both are independently identified. Still, the works based on semantic understanding from learning are most effective on the data they were trained on. For this reason, they cannot directly be used to thoroughly detect all the changes that would impact the scene geometry, as those could arise from objects unrecognizable to the networks.

In all of these works, inferring 3D CD results from the 2D images remains a challenge, yet can be necessary to correctly understand the scene. Indeed, to improve the captioning of 3D relationship change (and camera-robustness), [START_REF] Liao | Scene graph with 3d information for change captioning[END_REF] introduces scene graphs to represent the scene composition, as concept that will be furthered explored in Chapter 4. Finally, despite providing CD results in the shape of a 2D pixel map, [3] infers sparse 3D representations from the prior and current image sequences it compares, and uses said 3D models to reproject the 2D images to better align them prior to comparison. If the prior was assumed to be a 3D representation, this reprojection approach could be used without resorting to an estimation of the scene's geometry.

Change detection with heterogeneous data

While image-based CD methods are less computationally expensive than 3D-based ones, this is irrelevant when real-time interpretation of the 2D results is required to (re-)construct the 3D geometry of the environment. This has led to the development of hybrid methods that use heterogeneous data as input.

Methods described in [START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF] and [START_REF] Ulusoy | Image-based 4-d reconstruction using 3-d change detection[END_REF] aim at monitoring the evolution of a urban environment. This is achieved through the comparison of up-to-date images with an outdated 3D mesh [START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF] or with a dedicated 4D model [START_REF] Ulusoy | Image-based 4-d reconstruction using 3-d change detection[END_REF][START_REF] Ulusoy | Dynamic probabilistic volumetric models[END_REF] that represents the evolution of 3D data over time -considered the fourth dimension. The detected changes are provided in the shape of a 3D grid of change probabilities. For instance, in [START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF]: for every voxel in the grid, the corresponding pixels of the images it appears in are observed, then the probability of change is lowered if the colour is consistent between images (the Euclidean norm of the RGB vector). This approach primarily focuses on the structure of the environment as opposed to its texture and in practice, after this preliminary CD, some specialized equipment -such as vehicle or aerial laser scanners [START_REF] Hu | Approaches to large-scale urban modeling[END_REF][START_REF] Denis | Refining existing 3D building models with terrestrial laser points acquired from a mobile mapping vehicule[END_REF]-is deployed to the locations of detected changes in order to more precisely update the mesh.

These methods rely on an offline processing of the images and are still too computationally expensive to use on mainstream devices [START_REF] Simon | Automatic online walls detection for immediate use in ar tasks[END_REF]. In [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] a fast approach based on image reprojection is proposed for the purpose of autonomous exploration of an environment by a robot. In the absence of changes, the current 2D images should be identical when reprojected to the same point-of-view using the reference 3D mesh (not including the occluded areas). However, differences in the scene geometry between the capture of the mesh and that of the images would introduce inconsistencies in the reprojection which can be used to infer said geometry changes. While performing at an interactive rate, the technique is strongly biased toward the detection of object insertion in a scene rather than removal. This issue of false negatives induced by photometric homogeneity in the images is addressed in [START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF], which similarly reprojects current 2D observations using a 3D point cloud, but has to further process the latter as it contains "holes", unlike a mesh. Indeed, inconsistencies in the reprojection are only visible if the reprojected contents have great photometric variations. Removed objects are therefore harder to detect since the inconsistencies they introduce are entirely dependent on the background textures revealed by their removal, which are more likely to be uniform (i.e., a wall or the sky). In [START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF] this issue is dealt with by propagating 2D CD results using both color and semantic labelling, but this assumes a preliminary segmentation of the images.

Conclusion

For MR applications, CD should be able to provide results on the 3D geometry of the scene in order to preserve the realism of the experience. In Section 2.1, we found that attempting to directly scan the new geometry of the scene and updating the model imposes many hardware requirements (i.e., sensors, computing power) that mainstream AR devices cannot yet meet. Conversely, Section 2.2 showed that while an image-based approach could be taken to CD, the results of the detection would not be directly usable. We conclude that a 3D model is needed to represent the prior state of the scene, otherwise the updated geometry of the scene would have to be entirely reconstructed from the new observations. In this light, we find that the CD methods using heterogeneous input data presented in Section 2.3 are more applicable to the field of MR. As outlined in Table 2.3, they closely match the assumptions we can make for MR: an existing 3D model of the scene is available, but requires updating using the limited hardware of the AR device -sometimes limited to a camera and motion sensors. Using heterogeneous CD, the only geometry that needs to be reconstructed in the model, is that which corresponds to the detected changes. However, as outlined in Section 2.3, the bias towards changes that introduce the most photometric disturbances has to be addressed in order to obtain a complete CD framework.

Chapter 3

Photo-geometric change detection

In this chapter we propose a method for detecting the removal of objects in a scene using heterogeneous input data to represent its past and present states. Similarly to the other approaches that use such inputs [START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF][START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF][START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF] mentioned in Chapter 2, we will use a 3D reference model -an untextured mesh-and 2D observations -a sequence of images registered to said mesh. The removal detection is accomplished by studying the impact of ignoring all foreground objects from the scene during the projection of images onto the mesh, as to avoid the false negatives resulting from photometric homogeneity with regular reprojection [START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF].Indeed, a foreground object that is still present in the images will produce inconsistencies if ignored during the projection, while a removed object will not to the same extent. The removed objects can be found by highlighting the regions of most consistency between the projected images and a reference one, with an interactive processing time. The method properties are summarized in Table 3.1. 3D untextured mesh Registered image sequence 3D ellipsoids

Context and inputs

With the popularization of MR applications in an expanding number of fields, there is an increasing need for accurate and cost effective 3D model building techniques [START_REF] Freeman | Rapid scene modelling, registration and specification for mixed reality systems[END_REF][START_REF] Fuhrmann | Occlusion in collaborative augmented environments[END_REF].The naive approach to keep these models updated is to perform a regular and comprehensive 3D scan of the environment, which is time consuming, expensive [START_REF] Bauer | MetropoGIS: a feature based city modeling system[END_REF][START_REF] Döllner | Continuous level-of-detail modeling of buildings in 3D city models[END_REF][START_REF] Förstner | 3d-city models: Automatic and semiautomatic acquisition methods[END_REF][START_REF] Hu | Approaches to large-scale urban modeling[END_REF][START_REF] Ribarsky | From urban terrain models to visible cities[END_REF], and requires appropriate equipment [START_REF] Denis | Refining existing 3D building models with terrestrial laser points acquired from a mobile mapping vehicule[END_REF][START_REF] Izadi | Kinectfusion: Real-time 3D reconstruction and interaction using a moving depth camera[END_REF][START_REF] Sadeghi | 3D building façade reconstruction using handheld laser scanning data[END_REF]. A more efficient process is to compare an existing but outdated 3D mesh to current images of the environment to locate the 3D locations of changes and limit the updates to those areas [START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF]. Using images to describe only the up-to-date -and not the prior-state of a scene allows the detection to be independent of the illumination, poses, and devices used during the captures, since these factors generally do not affect the geometry of the scene and therefore the reference mesh. However, this asymmetry in the types of data used to represent the past and current states of the environment makes the identification of the nature of the changes more difficult. The attachment of such semantic information to changes often relies on the ability to match elements or locations of the scene at different times [START_REF] Park | Robust change captioning[END_REF].

For the purposes of updating the geometry of a 3D mesh, we can categorize changes in a scene as either "insertion of matter" or "removal of matter", since the displacements can be regarded as a combination of the two. Notably, insertions and removals also account for the "deformation of objects", as there is no object separation or texture information in the mesh to maintain: all 3D geometry is broken down into vertices and triangles. In this chapter, we propose a method for change detection which specifically focuses on the detection and the localisation of "matter", or objects, that has been removed from a scene using a reference mesh and images taken at a later time. The novelty of the solution is to focus on the parts of the scene that should be occluded by some foreground. The main contributions of this chapter are:

An image warping algorithm that generates textured shadows for the study of occluded areas in an image.

An improved object removal detection method that uses the aforementioned algorithm.

A complete fast change detection framework that combines our improved removal detection method with an existing change detection algorithm at no significant computational cost.

Our proposal is documented in Section 3.2, and the results are discussed in Section 3.3. Finally, our conclusions are summarized in Section 3.4.

Image-based object removal detection

As in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] and [START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF], a scene is represented by an outdated 3D mesh (see in Figure 3.1a) and changes are detected using pairs of up-to-date images registered to the mesh (see in Figure 3.1b). All images are taken within a narrow time frame, and we therefore assume that there are no structural or lighting changes between them.

Firstly, changes are evaluated in 2D from the point of view of each image: starting from a reference image, every other image is reprojected from the reference point of view. Note that this reprojection must take into account the original 3D scene to handle occlusions. Colour differences are computed between the reference image and each reprojected image and stored in delta maps. The plurality of delta maps per point of view is used to reduce noise and retrieve more accurate changes. Secondly, 3D changes are deduced by matching 2D changes together across multiple points of view. Location and size of the changes are estimated based on the delta maps.

To achieve removal detection, our approach differs from the state of the art in the choice of regions of interest for 2D change detection. The projection method used when warping images generates regions of occlusions as seen in Figure 3.2a which are ignored in other approaches but are the primary focus in ours. In summary, the proposed method is comprised of 5 steps:

1. For each image of the sequence, create reprojected copies to fit the points of view of the other images.

2. For each point of view, render the delta maps between the corresponding sequence's image and each accordingly reprojected image.

3. For each point of view, combine the delta maps into a single delta map to reduce false positives.

4. For each combined delta map, filter and group the pixels of detected changes into 2D areas of changes.

5. Match the 2D areas from one point of view to the other to infer the 3D locations and size of detected changes.

Image reprojection and occlusions handling

In this chapter, "reprojection" is not strictly used in its conventional meaning: it here amounts to back-projecting pixels onto the reference mesh and rendering them using another projection. This process is formalized in the next paragraphs, insisting on the impact of occlusions.

C j C i Q i X i P j X i =X j =X j I j (x i→j ) I i (x) I i (x ) I j→i (x) I j→i (x ) (a) Reprojection Ij→i with no change. C j C i X i =X j X j =X i X 0 I j (x i→j ) I j (x i→j ) I i (x) I i (x ) I j→i (x) I j→i (x )
(b) Reprojection Ij→i with an added object.

Figure 3.2:

Left: Reprojection from viewpoint j to i: foreground object (green) produces an occlusion (in black) of the background (yellow/pink). Right: Inserted object at X 0 (i.e. absent from mesh) introduces inconsistencies:

I i (x) = I j→i (x) , I i (x ) = I j→i (x ).
Let P j and P i be the projection matrices of cameras C j and C i . Then, a pixel x rendered by C i using P i can also be back-projected to the closest 3D point X i of the mesh. The back-projection function of C i is called Q i :

X i = Q i (x) . (3.1)
Using Q i and P j , any pixel x from point of view i can be associated to a pixel x i→j from point of view j:

x i→j = P j X i , with X i = Q i (x) . (3.2)
This process is illustrated in Figure 3.2a: every pixel x from point of view i is backprojected to its corresponding X i and then projected to x i→j in the point of view j. If performed on all the x pixels in i, it can be used to assign a pixel value I i (x) to their corresponding x i→j in j and render a "reprojected" image I i→j . Alternatively, the exact same transformation can be used to assign to each x in i a unique pixel value I j (x i→j ) and render I j→i (see Figure 3.4c) with Algorithm 1.

C j C i X i X i =X j =X j I j (x i→j ) I i (x) I i (x ) I j→i (x) I j→i (x )
(a) Reprojection Ij→i with a removed object.

C j C i X i X i =X j =X j I j (x i→j ) I i (x) I i (x ) S j→i (x) S j→i (x )
(b) Textured shadows Sj→i with a removed object.

I i (x) = I j→i (x). Its textured shadow is consistent with reference: I i (x ) = S j→i (x ).
Using this alternative, every point of the "reprojected" image is given a unique value, obviating the need for a depth-buffer and the necessity to interpolate any pixels that would have remained blank after the transformation. Indeed, multiple x can be reprojected to the same x i→j , but all x reproject to some x i→j if a corresponding 3D point can be found in the mesh.

When every pixel of the reprojected image is computed, some pixels are associated with 3D points that were occluded in the original view and therefore have no RGB value (see Figure 3.2a). We can check for such cases during the application of the transformation. For X i as defined in Equation 3.2:

X i occluded ⇔ X i -C j 2 > X j -C j 2 , with X j = Q j (x i→j ) . (3.3)
In Equation 3.3, X i and X j can be different from one another as the latter is obtained by back-projecting x i→j using C j , and is by definition the closest point to the camera. Since they are on the same axis, X j not occluding X i means they are equal. In contrast, in Figure 3.2a X i = X j , meaning X i is occluded.

In existing methods, occluded 3D points will be discarded when computing 2D changes (see Figure 3.4c). Conversely, our method systematically assigns an RGB value to these points: the one associated with the occluding point. Rendering those points with these RGB values has the effect of creating a textured shadow S j→i as in Figure 3.4d and 3.3 of the occluding points. Using Equation 3.2 and Equation 3.3 we can render S j→i with Algorithm 2. Algorithm 1: Base pseudo-code of our image "reprojection" process CreateReprojectedImage (i, j) inputs : points of view i and j; 3D mesh; image I j output: "Reprojected" image I j→i I j→i ← ∅ ; foreach x from point of view i do back-project x to its corresponding X i ; project X i to x i→j in the point of view j ;

I j→i (x) ← I j (x i→j ) ; return I j→i ;
Algorithm 2: Pseudo-code of our "textured shadows" rendering process CreateTexturedShadows (i, j) inputs : points of view i and j; 3D mesh; image I j output: "Texture shadows" image S j→i S j→i ← ∅ ; foreach x from point of view i do back-project x to its corresponding X i ; project

X i to x i→j in the point of view j ; if X i is occluded then S j→i (x) ← I j (x i→j ) ;
return S j→i ;

Photo-consistency in occluded pixels

When reprojecting, removed objects that are still present in the mesh have the effect of back-projecting the colours of the points they mask onto their surface (see Figure 3.4c, where the statue's podium is projected onto the middle red shape) and leaving those points untextured. Rendering the regions of occlusion using Algorithm 2 avoids this back-projection effect (see Figure 3.4d where the podium is correctly placed). More generally, the textured shadows of removed objects will be photo-consistent [START_REF] Kutulakos | A theory of shape by space carving[END_REF] with the reference image i.e., they will fill holes in the warped image with accurate data (compare the yellow shadows in Figure 3.4d to the reference in 3.4a). However for unchanged objects, such back-projections will not be textured by occluded points but by the object itself, and therefore will not be consistent with the reference image (see the lion statue's shadow to the left of Figure 3.4d). Our approach consists of looking for the regions of least change between the reference image and the textured shadow images from different points of view.

The delta maps δ j→i (see Figure 3.5a) are computed using the norm 2 distance between the RGB values of each rendered pixel in the textured shadow and in the reference images [START_REF] Gevers | Color in Computer Vision: Fundamentals and Applications[END_REF]. In order to account for the inaccuracies of the warping process, either in the camera pose or in the 3D mesh, the reference pixel's colour is compared to the colour of all pixels in its neighbourhood N in the warped image [START_REF] Taneja | Modeling dynamic scenes recorded with freely moving cameras[END_REF] and the minimum value is chosen:

∀x ∈ δ j→i , δ j→i (x) = min y∈Nx S j→i (y) -I i (x) 2 , with N x = {y ∈ S j→i | y -x 1 < d/2} , (3.4)
where d is the neighbourhood size and y ∈ S j→i if S j→i (y) is rendered.

Photo-consistency with multiple points of view

As we will further detail in the following paragraphs, a single delta map per point of view will generally not contain enough information to accurately retrieve the 2D location and shape of a change. Firstly, the regions of least change computed in Subsection 3.2.2 are located within the shadows of the foreground objects rather than in their actual positions in the frame. Secondly, only the parts of a removed object that cast such shadows will be detectable, which is why using several points of view can enable the method to more thoroughly retrieve the shape of the object, by uncovering new parts of it with each additional view.

Foreground projection

Before combining the multiple delta maps for different points of view, we first project the detected removals onto the foreground (see Figure 3.5b). For any pixel x of the delta map δ j→i , we can obtain the corresponding pixel x i→j in the original point of view j:

∀x ∈ δ j→i , x i→j = P j X i , with X i = Q i (x) . (3.5)
Moreover, if X i is occluded, back-projecting x i→j will return one of its occluding points X j . More specifically it will be the closest one to camera

C j : ∀x ∈ δ j→i , X j = Q j (x i→j ) , (3.6)
which corresponds to the pixel x (= x i→j→i ) in point of view i: ∀x ∈ δ j→i , x = P i X j .

We adapt Equation 3.3 to fit the point of view i and avoid rendering occluded objects (such as the bench to the left of Figure 3.4b visible in I j and S j→i , but not in I i ):

X j visible ⇔ X j -C i 2 ≤ X i -C i 2 , with X i = Q i (x ) . (3.8)
X i is the closest point to C i that could occlude X j . Equation 3.8 checks whether they are the same or not. We note that, as opposed to the reprojection process (Algorithm 2), this transformation is not reversible due to the repeated use of the back-projection, which always returns the closest point to the camera. In practice this means that not every pixel of the foreground is assigned a value (see the white holes inside the shapes of Figure 3.5b), while some pixels are given multiple values. The correct value is chosen using a depth buffer D j associated with C j and the foreground-projected delta map ∆ j→i , is then rendered using Algorithm 3.

Combination of projected delta maps

In ∆ j→i , not every pixel is assigned a value (see Algorithm 2 and 3 and the white pixels in Figure 3.5b). Therefore, we can define for each ∆ j→i a binary mask M j→i :

M j→i = {x | ∆ j→i (x) is assigned a value} .
(3.9)

Algorithm 3: Pseudo-code of our foreground projection process ForegroundProjection (i, j) inputs : points of view i and j; 3D mesh; delta map δ j→i output:

Projected map ∆ j→i ∆ j→i ← ∅ ; clear(D j ) ; foreach x from point of view i do back-project x to X i ; project X i to x i→j in point of view j ; back-project x i→j to X j ; project X j to x in point of view i ; if X j is visible in point of view i then if X j -C j 2 < D j (x ) then D j (x ) ← X j -C j 2 ; ∆ j→i (x ) ← δ j→i (x) ; return ∆ j→i ;
In order to uncover new parts of a potentially removed object, the combination of two projected delta maps with the same point of view involves the union of their binary masks. As for their values, the maximum per pixel of the two is chosen in order to reduce false positives. The maximum value is used to be more selective in the detection process. Foreground objects that are not removed could still share some RGB values with the background they occlude for a particular point of view (i.e., be photo-consistent), but it is unlikely they would for every point of view.

This approach is similar to the intersection process described in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF]. There, in a single delta map, when an object is inserted in a scene, changes are detected at the correct position of the object in the reference image and at an erroneous position resulting from the projection from another point of view (see Figure 3.2b). Since the actual 2D location of the change is the former, the erroneous positions are removed by intersecting two different delta maps, requiring 3 points of view in total. However, in this previous paper [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], the intersection process shrinks the area of the combined mask with every new point of view, instead of expanding it. This further reduces the chances of false positives but is not practical for the study of occluded regions, which potentially do not overlap for every point of view, even after foreground projection.

Using every available point of view, we define the combined delta map ∆ i as:

∀x ∈ j =i M j→i , ∆ i (x) = max j =i {∆ j→i (x) | x ∈ M j→i } . (3.10)
If x is not in any of the M j→i , then ∆ i (x) remains unassigned.

3D localisation of changes

Similarly to the process described in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], the 3D localisation relies on the segmentation of the combined delta map ∆ i into 2D regions of detected change, and the matching of those regions from one point of view i to another. From these matched regions' locations in the images, we can infer the 3D location of the change and its spread, as detailed in the following paragraphs.

Segmentation by region

The segmentation is achieved similarly to [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], namely the generation of the regions' contours using [START_REF] Suzuki | Topological structural analysis of digitized binary images by border following[END_REF] on a binarized ∆ i . Our contribution to this process is a more generalized binarization step that relies on a triangle threshold method described in [START_REF] Zack | Automatic measurement of sister chromatid exchange frequency[END_REF], rather than an arbitrary constant threshold value. This delta map binarization threshold is the main sensitivity threshold for the change detection algorithm. The darkest pixels in ∆ i are selected as candidates for the removal detection since they describe the regions of least change in the textured shadows. Isolated pixels are then removed through erosion and the contours are generated. A final threshold on the area of the regions is used to remove the smallest changes [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] (see Figure 3.6b).

Region matching

A 3D region of change that is visible for two or more points of view should have its projected 2D regions represented in several segmented delta maps. Although the 3D location of the changes could be retrieved through the use of back-projection, in practice the segmented maps are an approximation of the 2D projected changes, and a pixelwise depth estimation would be inaccurate. Indeed, every reprojection introduces slight numerical errors, as they are based on a discretized 3D model of the scene (i.e. the depth maps). Therefore, even taking into account the previously mentioned erosion process, neighbouring pixels in an region could belong to mesh faces separated by large distances. This is why we use moments [START_REF] Hu | Visual pattern recognition by moment invariants[END_REF] to compute the (2D) centroids of each region and then the same triangulation process described in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF]. Our method differs in the criteria used for matching the regions: instead of computing and comparing the HSV histograms of the regions in the corresponding images -as is done in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF]-we rely on the back-projection of the centroids on the mesh. This change is necessary because of the focus on the detection of removed objects, which by definition are present in the mesh but not in the images. This is a factor in the bias of detection toward inserted objects in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF]. If the back-projected centroid of a region in i is projected inside a region in j (or "reprojected" from i to j), and vice-versa, then the two regions are matched as in Figure 3.7: the orange and blue centroids belong to matched regions, as do the red and green ones.

The triangulation step produces 3D ellipses based on the size and location of the matched regions [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF]. This final output is presented in Figure 3.8.

Experimental evaluation and results

The algorithm from Section 3.2 was implemented in C++11 using the source code from [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] as a basis. Meshes and camera poses were handled using GLOW (OpenGL Object Wrapper) [START_REF] Behley | Glow (opengl object wrapper[END_REF], mathematical operations were computed with Eigen [70], and images were processed with OpenCV [START_REF] Bradski | The OpenCV Library[END_REF]. The code is available at: https://github.com/InterDigitalInc/ObjectRemovalDetection Our method was evaluated on several scenes that presented some changes: at least one object is removed, and in some cases, some are inserted. The sequences are made up of five pictures that display the location of the removals, which are introduced by adding 3D objects to an existing accurate mesh of the scene (as seen in Figure 3.8). Conversely, insertions are simulated by removing objects from that mesh. Meshes were taken from two sources: the dataset introduced in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], and the ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] dataset1 , which also provide estimated camera poses for the images.

The scenes in the dataset from [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] already showcase one or more insertions. Each mesh is already associated with five pictures that display the inserted objects. However, this dataset has some limitations: there are approximations in the meshes that can be detected as changes and the camera distortion coefficients are not available for every camera used which leads to inaccurate projection.

In contrast, the ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] images are noisier but have been corrected distortionwise. The scenes do not contain any insertion, and all meshes are associated with a video with thousands of frames, from which we picked five with the least motion blur possible to ensure that the camera poses were accurate.

Since we compare our method with the one from [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], the images were also chosen to showcase the location of the removed object we added to the mesh. For the sake of this comparison we also scaled the pictures to a width of 500px and used an area threshold of 50. Delta maps were computed using neighbourhoods N of size d = 3.

Quantitative evaluation

In order to evaluate the change detection quality, we used the same criteria as in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] and [START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF]: for each image point of view, we have a corresponding 2D ground truth which we compare to the results of our 3D detection. The 3D ellipses are rendered in 2D using each camera pose and numerical results are averaged across multiple points of view. The following numbers were computed for the evaluation:

IoU : area of the intersection of the ground truth and the 2D ellipse, divided by the area of their union, coverage: area of the aforementioned intersection, divided by the area of the ground truth, i.e. true positive rate (TPR), false positive rate: area of the intersection of the ground truth complementary and the 2D ellipse, divided by the area of the ground truth complementary.

For the scenes that contain inserted objects, we also took into account that the method described in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] detects changes of all natures indiscriminately. Therefore, we subtracted the shapes of the inserted objects from the image comparisons between the ground truth of removals and the 2D ellipses. Consequently, any insertion that was correctly reported by the algorithm is not to be considered as a false positive for object removal detection.

IoU and coverage with automatic thresholding

The chosen criteria favour detection that is accurate in 2D but not necessary correctly localised in 3D i.e., if there are several 3D regions of change accurately detected in 2D but incorrectly matched together. Since this does not happen with our removal detection, using a 3D-based criteria could improve the performance of our method comparatively to the one in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF].

In most cases, our method is the most accurate for both criteria. The IoU is often greater than 40% but there are particularly difficult scenes where it will drop below 30% while the algorithm from [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] does not detect anything (such as in Figure 3.18). Generally these scenes will have a 3D mesh that is incomplete or too dissimilar from the images in areas that should have remained unchanged.

As explained in Subsection 3.2.3.2, our approach to the combination of delta maps is based on mask union rather than intersection. This makes the detection more robust for objects near the edge of the frame. The ROC (receiver operating characteristic) curves in Figure 3.9, are used to compare the true positive rate and false positive rate of a binary operator for different discrimination thresholds [START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF], which in our case is the binarization threshold in the delta maps mentioned in Subsection 3.2.4.1. The automatic threshold is highlighted on the curves to evaluate its performance and the other threshold values are all the integers between 0 and 255. A threshold of 255 means that only the most consistent pixels of a delta map are considered (near the origin of the graphs). We note that the false positive rate never reaches the maximum value of 1 in the presented curves. This is due to the fact that ellipses are only generated for objects that cast shadows during reprojection, which generally only represents a small part of any given image. The value obtained for a threshold of 0, when any pixel in the delta map's mask is categorized as "changed" regardless of value, is the de facto maximum. In these curves, the best results are located to the top left. The automatic threshold value is generally chosen among those ideal values, but there are instances such as in "playground-car" (Figure 3.9b) where it is at a local minimum. These discontinuities are a consequence of the thresholding by the changes' areas and the following segmentation into 2D regions.

Qualitative evaluation

Filtering of the insertions detection results

While the method described in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] cannot reliably detect removed objects in the scene, it is also unable to differentiate them from inserted objects when detection occurs. To improve the performance of insertion detection, we can use the delta map produced by our removal detection process to filter the insertion delta maps. A naive approach consists of simply erasing the pixels from the insertions delta map where the corresponding removals delta map is positively identifying changes (as seen in Figure 3.10). In a real scenario, both an insertion and a removal could be occurring in the same 2D region of an image -the removed and added objects are aligned with the camera-but given enough different points of view, inserted objects would eventually be detectable. This is occurring in Figure 3.10b, where part of the insertion detection is removed due the filtering (the bottom part of the statue). Filtering reduces false positives in 3D (bottom).

Scenes from the Palazzolo et al. dataset

In the following figures, on the left is shown the ROC curve for removal detection in a scene while the right show the 3D results for the automatic threshold. The removed object is very close to the edge of the screen, making it harder to detect and leading to false positives on the trees in the background, whose geometries are approximated. The large inserted object does no affect the detection of removals. The same image sequence is used but the object is more centered in the frame, resulting in a much more accurate detection. The ROC curve is also less fragmented. The fragmentation is partly due to the grouping of changed pixels into regions, which can be discarded if their surface area falls under a certain threshold. The fragmentation occurs when there are multiple areas of detection (the trees and the object in the previous sequence). In the scene, an inserted object is in front of the removed object. As a result the object is only partially detected. The complexity of the scene also generates a lot of false positives because of the approximations in the mesh. In this particular scene, the automatic threshold is at a local minimum of performance. Also the results for the automatic threshold do not coincide with ones for any fixed threshold, as it can be different for each image of the sequence. This scene uses the same mesh and poses as the previous one, but the exposure in each image has been independently altered. This does not greatly affect the detection: the false positive rate is higher but it is the result of overestimating the size of the objects rather than detecting other objects altogether. The automatic threshold results are at a local maximum of performance: there is no other point to the top and left. This scene uses the same mesh and poses as the previous one, but the colour temperature in each image has been independently altered. This does not significantly impact the detection, and once again the automatic threshold results are at a local maximum. This scene uses the same mesh and poses as the previous one, but the colour temperature and exposure have been made more consistent across the images. This improves the results slightly. The object is detected but it is located in front of an inaccurately modelled part of the building, which greatly increases the false positive rate. It should be noted that a lower threshold would significantly improve the result. There is little parallax between the points of view as the camera is mostly rotating on it-self, and parts of the scene are inaccurately modeled. The true positive rate does not go over 0.45 signifying that some parts of the object cannot be detected. The presence of an inserted object does not significantly affect the removal detection. Even at the highest sensibility, some parts of the object cannot be recovered, they do not produce occlusions. The bottom of the table is merged with the background and cannot be recovered. However the legs are detected despite their narrowness. One arm of the foreground chair is wrongfully detected as removed since it does not perfectly align between the images and the mesh. The object does not produce any occlusion because of the camera is mostly rotating on itself, creating little to no parallax. The object is rarely seen in full, which makes evaluating its size more difficult. The power socket on the surface of the table does not produce a false positive, despite its very approximate 3D capture. However the size of the object is overestimated. In this scene the geometry of the object is very simple, and the object itself is in front of a distant background. Most threshold value are able to retrieve the object in its entirety.

Computation time

The methods were run on a CPU rather than a GPU to better reflect the limited hardware of portable AR devices. The execution time is on the same order of magnitude as the one reported in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] as interactive time. The processes of generating the delta maps and triangulating the changes in 3D never takes longer than a few seconds.

We note that of the two processes mentioned above, delta map generation is more computationally expensive. The reprojection operations as well as difference calculations on the images are each performed by looping once over the pixels each image. Empirically, we measured that the computation time was indeed proportional to the image resolution.

The computation time of the triangulation process cannot be evaluated as reliably, since it depends on the number of 2D areas detected in the first step. However, for a constant area threshold it will become less negligible when compared to the time of delta map generation, as the number of individual detected changes increases with the resolution. When the area threshold is increased in accordance with the resolution, this effect is less pronounced. The overall computation time is also tied to the number of images in the sequence, as every image is compared to every other one (i.e. for n images, n × (n -1) reprojections are made).

In a virtual machine with 16GB of RAM and four 2.60Ghz processors, both [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF]'s method and ours process sequences of five 500 pixel-wide images in less than 3 seconds. Compared to the implementation by [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], the computation time of our method remains low despite the addition of the removal detection process. This is because reprojection -the most time consuming operation-can be performed for both occluded (textured shadows) and visible pixels in a single pass by storing the rendered pixels in the corresponding images (respectively S j→i and I j→i ). In other words: most of the computations necessary to produce the textured shadows were already made in the original method from [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], but their results were not exploited, since only the visible pixels are used. In practice, both the algorithm from [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] and ours can be used at the same time in order to detect both insertions and removals with more accuracy (as mentioned in Subsection 3.3.2.1). It should also be noted that our reprojection process uses less memory thanks to the absence of a depth-buffer as described in Subsection 3.2.1. The reprojected image also has sharper features since no interpolation is required as shown in Figure 3.33.

Qualitative results from GPU implementation

For the reprojection and delta map rendering processes, we have reimplemented the existing algorithms using shaders directly applied to the mesh instead of functions run on the depth maps derived from said mesh. In this configuration, the execution time becomes tied to the precision of the mesh rather than the image resolution, because no depth map has to be generated. When such shaders were run an NVIDIA GeForce RTX 2060 GPU the computation time of the aforementioned processes was reduced by up to 95%.

Working directly with the mesh also eliminated the artefacts introduced by the pixelisation of the depth information. These include imprecisions over the computation of reprojected coordinates, as well as loss of definition in the geometries contours. The impact of this change is illustrated in Figure 3.34 for the object insertion detection pipeline, as it is more noticeable.

The foreground projection process is also more precise using the mesh, and allows us to avoid removal detection false negatives due to the presence of objects between the removed object and the background. In this case, as illustrated in Figure 3.35, the (consistent) textured shadows of the removed object are replaced by the (inconsistent) textured shadows of the objects behind it, making it undetectable. This can be avoided through a separate process of foreground projection of the reprojected images followed by the generation the delta maps. The inconsistencies between those delta maps provide the location of those removed objects at additional computational cost. The removed object in the foreground is undetected because the object behind it creates inconsistencies in the textured shadows.

C j C i X i X i =X j =X j I j (x i→j ) I i (x) I i (x ) I j→i (x) S j→i (x )

Limitations

Only studying regions occluded by a foreground object has a few side-effects. For instance, false positives can only be detected on objects that produce such occlusions. These false positives will only occur on the objects that are the most photo-consistent with their background (see "0001 00+dollhouse" Figure 3.23). Moreover, any removal accurately detected in 2D will be accurately localised in 3D. This differs from insertion detection where accurate 2D regions of change can be wrongly matched with other regions from a different change in another point of view.

In a scene, reflective surfaces might still pose a challenge. Instead of being detected as false positives as in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], they can make removed objects situated in their foreground difficult to detect i.e., generate false negatives.

Change size estimation can be an issue, as the detection size is proportional to the occlusion size of the removed object (see "0000 02+statue" Figure 3.22). If a removed object does not produce any occlusion it will not be detected by this method. Such an object could be detected using the method from [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] if it is far enough from its background to greatly distort its textures.

Not every image of the ScanNet dataset's sequences is perfectly aligned with its corresponding 3D mesh (see "0005 00+bucket" Figure 3.30). While this has not severely impacted the results of the detection in our experiments, in theory a misalignment of an image will generate 2D false positives and negatives for its point of view. On the one hand, false positives are still dealt with by using the other images of the sequence. On the other hand, false negatives can negatively impact the detection by reducing the areas of detection and lead to 3D false negatives or inaccurate size estimation. However, they occur less often, since they require that a removed object aligns with an object still present in the image.

Appendix A contains the image sequences used for all the scenes in the datasets and the resulting 2D change detection maps from which the errors are calculated.

Conclusion

In this chapter, we introduced a new approach for detecting the removal of objects between an outdated 3D mesh and a set of up-to-date pictures of a scene. The technique is based on the projection of the pictures' foreground textures to the background as defined by the 3D geometry and the pictures' points of view, and the comparison of the resulting images to the unmodified set of pictures. The definition and study of the foreground make our approach distinct from other reprojection-based approaches, which are not as effective at removal detection due to the low photometric disturbances caused by this type of change. The focus on object removals also simplifies the process of translating the results back into the 3D world, as we know their geometry is still present in the outdated mesh. It therefore allows us to make inferences on 3D geometry from images in which said geometry is absent, without relying on expensive depthestimation methods [START_REF] Fu | Deep ordinal regression network for monocular depth estimation[END_REF]. The technique is able to perform well even in environments with uniform textures or changes of different natures (the adding or removal of geometry) while remaining as fast as the state of the art methods that are meant to run on devices with low computational power. Thanks to its short computing time, this process can be repeatedly used over time, leading to an extension of the set of images used to describe the current scene. This would yield cleaner results -filtering out false positivesor uncover different layers of changes in the scene -observe the environment from new vantage points.

The results could be improved by basing the 3D shapes of the changes on the geometry of the mesh, rather than relying on standard shapes like ellipses. With more accurate shapes, the mesh could directly be altered to reflect the detected changes. This shape-level segmentation of the scene could be estimated through the study of the mesh's geometry and its properties (faces' sizes and normals, convexity, distance between vertices etc.). However it could be made part of the initial scene representation, and rely for instance on a semantic description of the scene's contents [START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF].

With removals now specifically identified, it is possible to ignore their impact in the change detection algorithm proposed in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], as the slight photometric disturbances they introduce during reprojection can be filtered out. As shown, this improves the detection of inserted objects in scenes, but also allows for the categorization of changes according to their nature: "insertion" or "removal". This categorization can be expanded on by including the notion of "displacement" of an object, when it is both removed and inserted into a scene. This would necessitate the ability to track said object over time, which could be accomplished photo-geometrically or through semantic analysis, as will be discussed in the next chapter.

Chapter 4

Semantic description of the scene

With the implementation of a full 3D CD framework based on the work presented in [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], we introduced a new reprojection method [START_REF] Roupin | Detection of removed objects in 3D meshes using up-to-date images for mixed-reality applications[END_REF] in Chapter 3 and used geometry-based matching in order to specifically detect and localise the removal of objects. This was accomplished without compromising the efficiency of the original work [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], as the new reprojection exploits computations that were already necessary but not fully taken advantage of. This focus on removals also allowed us to filter the results in the original CD process, resulting in a more accurate object insertion detection. The method returns as results 3D ellipsoids, which are produced through the detection and matching of 2D areas of changes across fives images.

While the matching and 3D localisation of the regions resulting from object removals can be performed with knowledge of the relevant 3D geometry in the scene, the process is still texture-based for inserted objects, making it less reliable than its removed object counterpart. Moreover, in both cases, the 2D region extraction also relies on the assumption that different objects in the scene have different textures. Parts of objects that are too photometrically similar to the background will not be detected if they were just inserted into the scene, or will falsely be identified as "removed" if they were present in the previous state. Inaccurate 2D or 3D estimation of the shape of changed areas prevents us from correctly updating the scene model, even when said shapes are improved through techniques such as active contours [START_REF] Ahlberg | Active contours in three dimensions[END_REF][START_REF] Krueger | Active contour based segmentation of 3d surfaces[END_REF], as those still require reference 3D geometry, which is unavailable for inserted objects.

Semantic analysis and motivations

In practice, the changes are generally correctly localised in 3D using our improved method [START_REF] Roupin | Detection of removed objects in 3D meshes using up-to-date images for mixed-reality applications[END_REF], but the ellipsoids used to represent their shapes are generally not precise enough to accurately modify the mesh. We attempted to improve the geometric precision of the removal detection by using a depth-based contour detection and flood-filling approach on the intermediary 2D results of the method (shown in Figure 3.7 of Chapter 3). While this made the CD framework perceptive to previously undetectable removed 3D geometry, it also led to more false positives, as it became an issue of correctly segmenting the geometry of the scene solely based on the depth maps. Likewise, insertion detection would not be improved with a preliminary color-contour detection, if the uniformity of the textures is the main issue. Therefore, in order to obtain a better object-level understanding of the scene, we decided to rely on a semantic analysis of its contents.

Object-level modelling

As mentioned in Chapter 2, the rise of Machine Learning and particularly Convolutional Neural Networks (CNNs) has led to the achievement of pixel-wise CD [START_REF] Chen | Dasnet: Dual attentive fully convolutional siamese networks for change detection of high resolution satellite images[END_REF][START_REF] Daudt | Fully convolutional siamese networks for change detection[END_REF][START_REF] Guo | Learning to measure change: Fully convolutional siamese metric networks for scene change detection[END_REF], where photometric techniques would have struggled. Such tools allow for captioning [START_REF] Park | Robust change captioning[END_REF] or pixel-wise labelling of the nature of the changes [START_REF] Blakeslee | Lambdanet: A novel architecture for unstructured change detection[END_REF][START_REF] Cheng | Semantic change pattern analysis[END_REF], of the objects affected [START_REF] Varghese | Changenet: A deep learning architecture for visual change detection[END_REF][START_REF] De | Unsupervised change detection in satellite images using convolutional neural networks[END_REF], or both [START_REF] Daudt | Multitask learning for largescale semantic change detection[END_REF]. However we also saw in Chapter 2, that they do not provide results pertaining to the 3D geometry of the scene, and that the cost of estimating said geometry from 2D inputs without a 3D reference is prohibitive -hence the heterogeneous approach taken in Chapter 3.

Given the amount of work dedicated to semantic analysis of images [START_REF] Ren | Faster R-CNN: towards real-time object detection with region proposal networks[END_REF][START_REF] He | Mask R-CNN[END_REF][START_REF] Kirillov | Panoptic segmentation[END_REF][START_REF] Wu | Detectron2[END_REF], this can also be used as a preemptive step to change detection, effectively translating the scene into a more easily comparable representation. For instance, in [START_REF] Kataoka | Semantic change detection with hypermaps[END_REF] the segmented maps are compared instead of the original images, and in [START_REF] De | Unsupervised change detection in satellite images using convolutional neural networks[END_REF] CD is performed in the feature-space of a network pre-trained for image segmentation. It should also be noted that CNNs have more recently been used for 3D point cloud processing [START_REF] Charles | Pointnet: Deep learning on point sets for 3d classification and segmentation[END_REF]5,[START_REF] Li | Pointnetlk revisited[END_REF].

In order to improve the 3D results of our method [START_REF] Roupin | Detection of removed objects in 3D meshes using up-to-date images for mixed-reality applications[END_REF] in Chapter 3, the 2D maps provided by image segmentation networks [START_REF] Ren | Faster R-CNN: towards real-time object detection with region proposal networks[END_REF][START_REF] He | Mask R-CNN[END_REF][START_REF] Kirillov | Panoptic segmentation[END_REF][START_REF] Wu | Detectron2[END_REF] could be used to filter out the noise -or false positives-in our 2D detection maps, or as a contour extractor for inserted objects. Being able to successfully identify objects across different scene states could also alleviate the need for accurate geometry estimation of the removed objects, if the 3D prior were appropriately segmented. Estimation and insertion of new geometry would remain difficult with few images, but the results would be more accurate. Finally, an object-level understanding of the scene and of its changes provides many features relevant to the final MR application, such as physical interactivity [START_REF] Chen | Semantic augmented reality environment with material-aware physical interactions[END_REF][START_REF] Chen | Context-aware mixed reality: A learning-based framework for semantic-level interaction[END_REF], agent interactivity [START_REF] Chevaillier | Semantic modeling of virtual environments using MASCARET[END_REF], and improved object positioning [START_REF] Lang | Virtual agent positioning driven by scene semantics in mixed reality[END_REF].

Feature-based localisation

In most MR applications, the user only observes a partial view of the world at any given time, that must be localised with respect to the prior representation said world (i.e., its state when previously scanned) to add content or fix inconsistencies through CD. Previously mentioned CD works make use of GPS data [START_REF] Taneja | Geometric change detection in urban environments using images[END_REF] followed by a refinement process, assume co-registered representations [START_REF] Palma | Detection of geometric temporal changes in point clouds[END_REF] while sometimes allowing for slight misalignment [START_REF] Guo | Learning to measure change: Fully convolutional siamese metric networks for scene change detection[END_REF], or ignore the issue of localisation [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF]. However, with semantic analysis of the scene, registration becomes easier.

There exists literature on feature-based localisation, particularly for SLAM problem, that involve CD as a means for robustness [START_REF] Murase | Change detection with global viewpoint localization[END_REF][START_REF] Derner | Towards life-long autonomy of mobile robots through feature-based change detection[END_REF]. Related works also include the place recognition process cited in [START_REF] Sünderhauf | Place recognition with convnet landmarks: Viewpoint-robust, condition-robust, training-free[END_REF], which is able to match images based on their contents using a pre-trained CNN classifier. Some localisation works also make use of a graph representation of the scene: for instance [START_REF] Qin | Semantic loop closure detection based on graph matching in multi-objects scenes[END_REF] uses the Kuhn-Munkres algorithm on graphs generated from the objects present in each image to detect loop closure, i.e., check if an area is being revisited to correct accumulated estimation errors in the pose. Other works use pose graphs in order to organise a multitude of relative pose estimations [START_REF] Rosinol | Kimera: an open-source library for real-time metric-semantic localization and mapping[END_REF][START_REF] Indelman | Multi-robot pose graph localization and data association from unknown initial relative poses via expectation maximization[END_REF] and infer localisation from it.

With the parallelization of the CD and localisation tasks, there is an opportunity to improve both processes by avoiding a negative feedback loop: localisation without CD can wrongly assume which landmarks are displaced between sessions, leading to incorrect pose estimation and following CD. It should nevertheless be noted that in those works, CD is a by-product of the main task of localisation, and is prone to false positives. Indeed, the purpose is only to find reliable landmarks in the environment, similarly to the static maps [START_REF] Fehr | Tsdf-based change detection for consistent long-term dense reconstruction and dynamic object discovery[END_REF]4] mentioned in Chapter 2. The scene representation required for MR applications will necessitate a more exhaustive description of its geometry, and ideally of its semantic contents.

Explicitly defining the relevancy of changes

Using semantic analysis, we can set the level of detail or define the changes that are relevant to the maintenance of our scene representation [START_REF] Han | Advanced deep-learning techniques for salient and category-specific object detection: A survey[END_REF]. Indeed, we have seen that CNN-based CD methods [START_REF] Guo | Learning to measure change: Fully convolutional siamese metric networks for scene change detection[END_REF][START_REF] Varghese | Changenet: A deep learning architecture for visual change detection[END_REF] use semantics to filter out photometric inconsistencies due to view-point or illumination variation between scene states. The ability to distinguish between different sources of photometric (pixel value) changes in images can improve the quality of detection when focusing on any of those sources (illumination, geometry, texture, semantics etc).

Through object-level understanding, suspected geometric changes that result from the inaccuracies of the MR device's sensors can be ignored. This is particularly useful where there is a large difference in data quality between the reference model and the current observations, or when the computational cost of CD and updating is non-negligible. Indeed, with the development of LiDAR technology and multi-view stereo on consumer devices, 3D geometry can be directly monitored, but the quality of the representation would inevitably degrade as the environment changes and updates are applied based on the low-detail readings of the devices' sensors. If changes can be understood as the manipulation of objects in the scene, the same can be done to its representation, preventing the loss of detail in the original photo-geometric contents, and allowing for faster updates and lighter storage.Scanning the scene directly -in 2D or 3D-would only be required to capture previously unknown objects.

In the context of MR, any change in geometry that affects the blending of virtual and real elements must be accounted for (photo-realism), as well as higher-level changes that will affect the MR experience (behavioural realism). This "exhaustivity" constraint is where the semantic analysis works mentioned in this chapter fall short, as their vocabulary is limited by their training data -as seen in Figure 4.1 where object detection is not exhaustive (left) and "panoptic" segmentation [START_REF] Kirillov | Panoptic segmentation[END_REF] (segmentation of both object instances and semantically consistent areas) lacks precision (right). To achieve exhaustive CD, we will need to structure the available semantic information in a way that allows for the identification and tracking of unknown object instances, when all that is available is their appearance.

Graphs to structure the scene information

When semantic segmentation tools such as Detectron2 [START_REF] Wu | Detectron2[END_REF] are used to improve our geometric understanding of a scene, we are ultimately limited by the number of object classes that can be detected. In order to avoid those limitations, we now focus on characterizing the contents of a scene using the objects' identifying features and relationships to one another, as recorded in a Scene Graph [START_REF] Johnson | Image retrieval using scene graphs[END_REF] (SG). A Scene Graph can be used to represent a 3-dimensional scene state, which itself is described by natural language, sensory readings, or visual representations such as images and 3D models.

Linking semantic information to photo-geometric data

In the works mentioned in the previous section, the semantic analysis results were provided in the shape of pixel-maps or 2D bounding boxes corresponding to each object or regions identified. For instance, in the ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] dataset of 3D annotated rooms, the semantic segmentation information is directly stored as indexed color maps of multiple angles of each room, which are then used as textures for a 3D annotated mesh. A much lighter representation was introduced in [START_REF] Johnson | Image retrieval using scene graphs[END_REF], called Scene Graphs: graphs where the nodes are objects in the scene, often with attributes, and the edges are semantic relationships between those objects, such as the ones in the Visual Relationship Detection dataset [START_REF] Lu | Visual relationship detection with language priors[END_REF]. While there are CNNs designed for relationship extraction [START_REF] Zhan | On exploring undetermined relationships for visual relationship detection[END_REF], other architectures [START_REF] Yang | Graph R-CNN for scene graph generation[END_REF][START_REF] Li | Factorizable net: An efficient subgraph-based framework for scene graph generation[END_REF][START_REF] Tajrobehkar | Align r-cnn: A pairwise head network for visual relationship detection[END_REF] directly produce graphs from images, making use of the Visual Genome dataset [START_REF] Krishna | Visual genome: Connecting language and vision using crowdsourced dense image annotations[END_REF]. In Section 4.3 we will explore the many applications of such data structures, but for our purposes, SGs are a means to efficiently store and analyse semantic information as it relates to the geometry of the scene. This can ultimately lead to better means of interactivity between the virtual and real actors, and provides the medium to achieve the lightweight geometric maintenance mentioned in the previous section.

4D graph representations which add a time attribute [START_REF] Brost | Temporal analysis and change detection via geospatial-temporal semantic graphs[END_REF][START_REF] Gutierrez | Temporal rdf[END_REF] also allow for the tracking of entities (areas of land in [START_REF] Brost | Temporal analysis and change detection via geospatial-temporal semantic graphs[END_REF] and semantic data in [START_REF] Gutierrez | Temporal rdf[END_REF]) over several iterations, where 3D representations can only be used to compare the current and previous states. Being able to monitor changes in the scenes over longer periods of time means that repeatedly disappearing and reappearing geometry can be reused without rescanning. Overall the CD task would have a larger prior to base its results on, and infer the variability of particular objects [START_REF] Looper | 3d VSG: long-term semantic scene change prediction through 3d variable scene graphs[END_REF].

Accounting for unknown objects

In a Scene Graph, the nodes representing objects can contain more information than the object's label, allowing us to differentiate between multiple instances of a similar object in a scene through appearance or context. This is beneficial for tracking specific objects between states, going beyond the simple model of insertion and removal of geometry, but also to provide information to differentiate between semantically unrecognisable or novel objects. Indeed, when nodes need to be compared in semantic graphs, the similarity metric can be a combination of the similarity of the nodes' attributes [START_REF] Kim | 3-d scene graph: A sparse and semantic representation of physical environments for intelligent agents[END_REF][START_REF] Yu | A bottom-up framework for construction of structured semantic 3d scene graph[END_REF] and that of their neighbours [START_REF] Stumm | Robust visual place recognition with graph kernels[END_REF][START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF][START_REF] Liu | Global localization with object-level semantics and topology[END_REF][START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF]. Incremental learning and anomaly detection could expand the semantic vocabulary of the scene analysis method, but it could lead to catastrophic interference [START_REF] Mccloskey | Catastrophic interference in connectionist networks: The sequential learning problem[END_REF] (abrupt forgetting of previously learned information), and therefore be unreliable over long periods of time.

In order to fully segment the scene, methods tailored to specific object classes can be more effective, and their results can be directly stored in the SGs. For instance, plane detection in 2D [START_REF] Qiu | Plane detection in stereo images based on homography[END_REF][START_REF] Haines | Recognising planes in a single image[END_REF][START_REF] De | Dominant plane recognition in interior scenes from a single image[END_REF][START_REF] Liu | Global localization with object-level semantics and topology[END_REF][START_REF] Simon | Automatic online walls detection for immediate use in ar tasks[END_REF], 2.5D [START_REF] Sousa | Hough transform for real-time plane detection in depth images[END_REF] or 3D [START_REF] Feng | Fast plane extraction in organized point clouds using agglomerative hierarchical clustering[END_REF] can be used to detect the boundaries of an indoor environment: the walls, floor and ceiling; using semantics, vanishing points or perspective correction methods. These surfaces can be hard to classify and localise using object detection networks due to their uniformity and size. It should also be noted that by detecting objects and planes separately, each process could improve the others' result. Masking the planes from the images during object detection could increase the precision [START_REF] Kiyokawa | Fully automated annotation with noise-masked visual markers for deep-learning-based object detection[END_REF] or improve the efficiency [START_REF] Wang | Cascade mask generation framework for fast small object detection[END_REF], as noisy textures could be removed and smaller objects become visible. Conversely, 3D data could be filtered to remove the objects' points before the plane detection.

In the absence of semantic labelling for some 2D or 3D geometry in the scene, the shape of the underlying objects can be inferred through observation of their known surroundings and be tracked by their geometric attributes. Depending on the available data, more general photometry [START_REF] Yang | Superpixel segmentation with fully convolutional networks[END_REF] or geometry-based [START_REF] Ückermann | 3d scene segmentation for autonomous robot grasping[END_REF] segmentation tools would help in reducing the size of the unknown entities, making them more trackable. The resulting geometry can be understood as "stuff" or "things" [START_REF] Caesar | Coco-stuff: Thing and stuff classes in context[END_REF] in the context of semantic understanding, and the concept of "blank node" [START_REF] Wood | RDF 1.1 concepts and abstract syntax[END_REF] is used to describe such unknown entities in Resource Description Framework (RDF) graphs. RDF graphs have been introduced to organise data for semantic web applications, and blank nodes serve as structural elements to organise pieces of knowledge relatively to each other. Recent works in robotics have started to apply this concept to scene graphs [START_REF] Sonogashira | Towards open-set scene graph generation with unknown objects[END_REF].

Acting as an intermediary representation

Finally, another benefit of SGs is their ability to be easily parsed by humans and machines, and to be used as a "translation medium" between different representations. This will be further illustrated in Section 4.3, as their applications to scene authoring and Human-machine Interaction (HMI) will be shown, which are both related to the MR field.

In graph-based localisation methods, such as X-View [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF], the graph structure is used as a means of converting RGB-D data captured from different perspectives -by a flying drone or a ground-based vehicle-into comparable spatial representations of the scene. In robotics, it is used as the intermediary representation between a controller's commands and the internal understanding of the scene by the agents [START_REF] Yu | A bottom-up framework for construction of structured semantic 3d scene graph[END_REF][START_REF] Kim | 3-d scene graph: A sparse and semantic representation of physical environments for intelligent agents[END_REF][START_REF] Rosinol | 3d dynamic scene graphs: Actionable spatial perception with places, objects, and humans[END_REF].

SGs can be used to generate text from images [START_REF] Yang | Auto-encoding scene graphs for image captioning[END_REF], or caption changes [START_REF] Liao | Scene graph with 3d information for change captioning[END_REF], while remaining close to the disposition of real and virtual assets in the scene. The focus on interactivity and clarity makes the SG particularly suited to scene representation in MR applications, where the goal is always to provide a human user with an immersive and convenient experience. This ability to serve as a intermediary for switching between different scene representations (images, text, 3D geometry...) further benefits applications with narrative or educational goals. SGs are able to represent scene states gathered from heterogeneous data -be it gathered from various sensors or synthetic-and making such states comparable for tasks such as localisation and CD.

Conclusion: Representation requirements for MR and CD

For MR applications and based on recent technological advances, we can now assume that the capture device is able to capture RGB images and depth maps with their associated camera intrinsic and extrinsic parameters, relative to where the MR session was started. The prior scene representation against which changes are detected would contain the scene geometry necessary to achieve photorealism, and associated semantic annotations for behavioural realism [START_REF] Haller | Photorealism or/and non-photorealism in augmented reality[END_REF]. The corresponding information for the current state of the scene would have to be inferred from the limited perspective of the capture device, whose interpretation could be facilitated by prior knowledge.

Both the semantic and geometric layers of the scene representation can be organised using a SG, where nodes describe objects' and edges' spatial or general relationships. Some the objects could be semantically labelled using 2D [START_REF] Ren | Faster R-CNN: towards real-time object detection with region proposal networks[END_REF][START_REF] He | Mask R-CNN[END_REF] or 3D [START_REF] Charles | Pointnet: Deep learning on point sets for 3d classification and segmentation[END_REF] processing, but unknown objects would still be identifiable through stored geometric and photometric attributes, as well as their neighbours' (defined by the edges). The relationship described by the edges have to be viewpoint-independent, in order to be usable in 3D.

In conclusion, SGs can effectively describe which changes are considered relevant with regards to the application. On the one hand, changes in the scene that impact the experience should be represented by modifications to the graph's topology or to the nodes' attributes. On the other hand, every element present in the graph should be maintainable using the available information on the current state of the scene, as to not diverge from reality.

In the following section we will survey works relating to scene graphs (generation and application) that are relevant to solving the problem of CD for MR applications.

Survey: Semantic Graphs for scene understanding

In the field of Augmented Reality, SGs may represent two different types of scenes: the real one and the virtual one. As outlined in [START_REF] Royan | Towards an interoperable world representation for xr[END_REF], a "scene graph" can be used to refer to the representation of the latter: an organised collection of virtual assets to be inserted into the scene. The graph used to represent the real world is referred to as the "world graph" and organises the various "trackables" (fiducial markers, objects, landmarks, etc.) in the scene in order to, for instance, localise the device. Both graphs can contain "anchors" which are used to interface between the real and virtual contents: they are locations defined relatively to the trackables in the world graph, and around which assets are organised in the scene graph.

Our change detection task relates to the study of the real scene and therefore to the "world graph", however, works relating to either category (virtual or real scenes) are relevant to our application. These works all refer to the graphs they use as "scene graphs", since "world graphs" are a notion specific to the AR field. Consequently, the following survey will also refer to them as "scene graphs" (SGs) when no distinction is required.

Prescriptive graphs for scene authoring

SGs were introduced as a database searching tool in [START_REF] Johnson | Image retrieval using scene graphs[END_REF][START_REF] Ganea | Graph object oriented database for semantic image retrieval[END_REF][START_REF] Ramnath | Scene graph based image retrieval -a case study on the clevr dataset[END_REF], but have been used to manipulate [START_REF] Dhamo | Semantic image manipulation using scene graphs[END_REF][START_REF] Su | Fully Functional Image Manipulation Using Scene Graphs in A Bounding-Box Free Way[END_REF] or generate [START_REF] Johnson | Image generation from scene graphs[END_REF] images. Their structured nature make them an efficient scene authoring tool when semantic constraints are placed before strict geometric ones. The graph representations used for this purpose are prescriptive (i.e., a set of instructions) rather than descriptive [START_REF] Cunningham | Lessons from scene graphs: using scene graphs to teach hierarchical modeling[END_REF].

In the context of 3D building software [START_REF] Community | Blender -a 3D modelling and rendering package[END_REF] or physics engines [START_REF] Haas | A history of the unity game engine[END_REF], graphs -and specifically "trees"-may be used to organise the different assets of a virtual scene. For example, spatial coordinates or material properties may be passed down the branches of an asset management tree, but the object-nodes may also be connected by edges describing relative transformation matrices. The graph is simply a representation of a set of constraints between files or models as defined by the user in the scene [START_REF] Cunningham | Lessons from scene graphs: using scene graphs to teach hierarchical modeling[END_REF].

By definition, these SGs provide an exhaustive representation of the scene while relying purely on geometric and photometric data [START_REF] Studios | Introduction to usd[END_REF]98]. Similarly, updates to the topology or the nodes' attributes are directly reflected in the scene, and there is little need for performing CD, beyond version control [START_REF] Chacon | Pro Git. The Expert's Voice[END_REF]. The study of prescriptive graphs still informs our choice of graph representation in two ways. Firstly, it helps in creating a world graph that is better interfaced with the virtual scene graphs for MR applications. Secondly, the design of these graphs makes explicit many of the attributes that are relevant to track to achieve realism (textures, materials, meshes, light sources etc. [98]), and that should therefore be present in our own SG.

Finally, we note that manually created SGs have been used to search for object patterns in a scene for AR applications [START_REF] Tahara | Retargetable ar: Contextaware augmented reality in indoor scenes based on 3d scene graph[END_REF]. This can be seen as a case where the anchors of the (real) scene graph and (virtual) world graph are the trackables [START_REF] Royan | Towards an interoperable world representation for xr[END_REF], and the SG ends up describing the scene, although not in an exhaustive manner.

2D Descriptive graphs and relationship extraction

Building on the idea that scene structure can help identify objects (as in Subsection 4.2.2), Relation R-CNN [START_REF] Chen | Relation r-cnn: A graph based relation-aware network for object detection[END_REF] (Region-based CNN) is a 2D object detection network which computes semantic and spatial relation features to improve its sensibility and precision. Although Relation R-CNN only returns the objects' classes and bounding boxes, there exist works that specifically detect the objects' relationships, yet do not directly provide their results in the shape of a graph [START_REF] Zhan | On exploring undetermined relationships for visual relationship detection[END_REF].

The works based on the Visual Genome [START_REF] Krishna | Visual genome: Connecting language and vision using crowdsourced dense image annotations[END_REF] and Visual Relationship Detection (VDR) [START_REF] Lu | Visual relationship detection with language priors[END_REF] datasets provide similar interaction-based relationships. Another dataset, namely, SpatialVOC2K [START_REF] Belz | Spa-tialVOC2K: A multilingual dataset of images with annotations and features for spatial relations between objects[END_REF], was developed for the purpose of spatial relationships annotation in images [START_REF] Belz | Exploring different preposition sets, models and feature sets in automatic generation of spatial image descriptions[END_REF]. This has led to the implementation of methods that employ mono-depth estimation [START_REF] Birmingham | Adding the third dimension to spatial relation detection in 2d images[END_REF] and k-means clustering [START_REF] Birmingham | Clustering-based model for predicting multispatial relations in images[END_REF] to improve the quality and quantity of the detected relations. It should also be noted that object pairs should be able to share multiple semantic relationships to fully describe the scene structure.

For image-based scene understanding, there are many methods for directly generating scene graphs as well: Graph R-CNN [START_REF] Yang | Graph R-CNN for scene graph generation[END_REF], Factorizable Net [START_REF] Li | Factorizable net: An efficient subgraph-based framework for scene graph generation[END_REF] and Align R-CNN [START_REF] Tajrobehkar | Align r-cnn: A pairwise head network for visual relationship detection[END_REF]. These methods are derived from object detection R-CNNs [START_REF] Ren | Faster R-CNN: towards real-time object detection with region proposal networks[END_REF][START_REF] He | Mask R-CNN[END_REF] where additional branches were added to provide information on the relationships between the objects. Such 2D scene graphs have proven useful as a translation tool between the natural language and geometric or photometric measurements [START_REF] Samih | Semantic graph representation and evaluation for generated image annotations[END_REF], as well as the applications mentioned in the previous subsection [START_REF] Johnson | Image retrieval using scene graphs[END_REF][START_REF] Ganea | Graph object oriented database for semantic image retrieval[END_REF][START_REF] Ramnath | Scene graph based image retrieval -a case study on the clevr dataset[END_REF][START_REF] Dhamo | Semantic image manipulation using scene graphs[END_REF][START_REF] Su | Fully Functional Image Manipulation Using Scene Graphs in A Bounding-Box Free Way[END_REF][START_REF] Johnson | Image generation from scene graphs[END_REF]. However, for all these applications, the contents of the scene are usually described with a focus on actions or interactions focus rather than on the structure of the scene [START_REF] Li | Factorizable net: An efficient subgraph-based framework for scene graph generation[END_REF][START_REF] Yang | Graph R-CNN for scene graph generation[END_REF].

Unlike 3D models or 2D floor plans, "realistic" images of scenes (i.e., ground-based photography) are not suited to spatial planning and often contain active subjects. The uniqueness and qualities of an image are often better conveyed through its implied narrative rather than the spatial arrangement of its contents. Indeed, converting such action-based captions into accurate visual layouts is an active area of research [START_REF] Elu | Inferring spatial relations from textual descriptions of images[END_REF]. Some relationships detectors are designed to extract more structural information about the scene, such as support relationships [START_REF] Silberman | Indoor segmentation and support inference from rgbd images[END_REF] (pairings of objects to the surfaces they are supported by), however most 2D SG generators are not. In practice, the resulting graphs usually contain a reduced number of edges with complex semantic meanings, and there have been efforts to increase the density of the graph by producing more edges per node pairs [START_REF] Tajrobehkar | Align r-cnn: A pairwise head network for visual relationship detection[END_REF]. However most of these relationships are dynamic or rely on the presence of active subjects, which makes them unlikely to be stable enough for long-term change detection and representation in semi-static MR scenes.

3D Descriptive graphs and graph fusion

When SGs are used to describe 3D environments, the focus usually shifts from recording the narrative of the scene to recording its layout, as they are meant to be used for interactivity and navigation rather than captioning. Semantic graphs can be directly constructed from 3D data [START_REF] Wald | Learning 3d semantic scene graphs from 3d indoor reconstructions[END_REF], using Machine Learning tools such as PointNet [START_REF] Charles | Pointnet: Deep learning on point sets for 3d classification and segmentation[END_REF] and Graph Convolutional Networks [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF], but the semantic analysis is generally performed with 2D images.

One approach consists in generating local 2D graphs from a video or image sequence [START_REF] Kim | 3-d scene graph: A sparse and semantic representation of physical environments for intelligent agents[END_REF][START_REF] Yu | A bottom-up framework for construction of structured semantic 3d scene graph[END_REF], which are incrementally merged into a global 3D graph in a process that will be further described in the next subsection. The method described in [START_REF] Kim | 3-d scene graph: A sparse and semantic representation of physical environments for intelligent agents[END_REF] uses graphs produced by Factorizable Net [START_REF] Li | Factorizable net: An efficient subgraph-based framework for scene graph generation[END_REF] and therefore requires filtering of the dynamic edges (actions) or nodes (actors) that do not serve to describe the scene structure, which further decreases the density of the local graphs before their merging. The density issue is compounded by the removal of 2D spatial relationships that do not translate directly into a 3D representation without ambiguity [START_REF] Pustejovsky | Image annotation with iso-space: Distinguishing content from structure[END_REF], and often only vertical structure is preserved as this axis is assumed to be aligned with the gravity vector (i.e., the normal to the ground).

In order to increase the number of structural edges with 2D semantic analysis, graph generators can use simpler metrics -such as proximity or contact-as opposed to learningbased methods, therefore decoupling the node and edge creation tasks. This is the approach taken in generating some "layered" graphs representations [START_REF] Armeni | 3d scene graph: A structure for unified semantics, 3d space, and camera[END_REF][START_REF] Rosinol | 3d dynamic scene graphs: Actionable spatial perception with places, objects, and humans[END_REF]. These data structures have been introduced to facilitate the instruction interpretation task in robotics, and to further organise data of differing scale or nature, and they employ "vertical" edges to correlate the information found on each layer, be it geometry, camera viewpoints, actors, or building layout.

In a similar fashion to multi-view object detection [START_REF] Chen | Multi-view 3d object detection network for autonomous driving[END_REF][START_REF] Tang | Multi-view object detection based on deep learning[END_REF][START_REF] Deng | Mlod: A multi-view 3d object detection based on robust feature fusion method[END_REF][START_REF] Wang | Vpfnet: Voxel-pixel fusion network for multi-class 3d object detection[END_REF][START_REF] Zhu | Vpfnet: Improving 3d object detection with virtual point based lidar and stereo data fusion[END_REF][START_REF] Li | Graph matching networks for learning the similarity of graph structured objects[END_REF][START_REF] Pon | Object-centric stereo matching for 3d object detection[END_REF][START_REF] Chen | Dsgn: Deep stereo geometry network for 3d object detection[END_REF], semantic analysis is improved by correlating the results found on different 2D points of view. In [START_REF] Armeni | 3d scene graph: A structure for unified semantics, 3d space, and camera[END_REF], object detection is performed on panoramic images registered to the 3D model, which is in turn textured using the segmentation results. Alternatively, [START_REF] Rosinol | 3d dynamic scene graphs: Actionable spatial perception with places, objects, and humans[END_REF] uses Kimera [START_REF] Rosinol | Kimera: an open-source library for real-time metric-semantic localization and mapping[END_REF], which generates the geometry from a stereo-camera and an inertial measurement unit, and provides semantic analysis through panoptic segmentation of the left-side camera. The 2D segmentation is then converted into a 3D voxel grid of label probabilities, which is finally used to texture the mesh with the most likely labels using marching cubes.

As we have seen, the exact structure of 3D graphs vary with their method of construction or the intended application. Some favour processing efficiency over human readability, and none are specifically tailored to the task of comprehensive scene change detection, or monitoring on a human-scale. However, the 2D graph fusion methods requirements are the closest to those of the MR scenario.

Object similarity for node matching

In Subsection 4.3.3 we introduced the process of constructing a global 3D SG from the fusion of local 2D graphs [START_REF] Yu | A bottom-up framework for construction of structured semantic 3d scene graph[END_REF][START_REF] Kim | 3-d scene graph: A sparse and semantic representation of physical environments for intelligent agents[END_REF]. This fusion requires the association of the nodes present in the local graph with the ones contained in the reference: the nodes that refer to the same object in the scene are matched and merged. Conversely, the ones that refer to new entities are simply attached to the global graph with the edges seen in the local graph. To determine if there is a match between a local node and a global node, there needs to be a means of measuring similarity between nodes and ascertain if it is significant enough.

The similarity metrics used in graph fusion methods are based on the object nodes' attributes, and a threshold value is set to indicate similarity. In [START_REF] Yu | A bottom-up framework for construction of structured semantic 3d scene graph[END_REF], the nodes' label and 3D position are compared, as the photometric aspects of the objects are considered too unstable over time. The label score is positive if the two nodes share the same label and is equal to the maximum of the nodes' "confidence score" for said label -the probability of the semantic labelling to be accurate reported by the 2D graph extractor. The position score is proportional to the nodes' distance normalized by the diameter of the largest of the two nodes. [START_REF] Kim | 3-d scene graph: A sparse and semantic representation of physical environments for intelligent agents[END_REF] uses more information: the position and size are stored as a 3D Gaussian distribution, photometric attributes are stored as a color histogram and the label is a probability vector over the whole set of object classes. The similarity metric is based on the 3 most likely labels for each object, the histograms' intersection and the Gaussian distribution overlap. All these individual values are weighted and summed into an overall similarity score used during the fusion.

A closely related approach to this similarity metric can be found in place recognition methods that use landmarks [START_REF] Sünderhauf | Place recognition with convnet landmarks: Viewpoint-robust, condition-robust, training-free[END_REF]. The second-to-last layer of an object classifier network [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF][START_REF] He | Deep residual learning for image recognition[END_REF] produces a vector-like descriptor that can be used to identify specific objects: there is enough information remaining to recognize them as individual instances rather than as members of a category. For the place recognition task, a database of the most recognizable, reoccurring and stable landmarks can be constructed containing said descriptors. The similarity metric can then simply be the cosine distance between two of those vectors -their scalar product divided by the product of their norms. If it were to be applied to graph fusion, this metric might need to be used in conjunction with other measurements, such as relative position, in order to compensate for the generic nature of most of the objects in the scene. However, this descriptor can act as a more relaxed substitute for the node's label probability vector, especially when the object is of an unknown class.

Switching to a graph structure for localisation [START_REF] Gu | Landmark graph-based indoor localization[END_REF], collecting landmarks of any nature in the environment and attaching them to their respective spatial points of capture, can also prove to be effective. These landmarks can be any type of sensory measurement (i.e., trackables: temperature, radar, LiDAR...) or miscellaneous properties such as the presence of WiFi hot-spots or connected items. During a later exploration of the scene, the graph is searched to find the spatial coordinates which correspond the most to the currently visible landmarks. In this graph, the directed edges correspond to the paths between landmarks pairs, and they store the distance and direction along those paths. The work in [START_REF] Gu | Landmark graph-based indoor localization[END_REF] notes that landmarks sometimes need to be disambiguated to be accurately matched, and this is achieved using a "belief" score based on the same relative spatial properties.

While changing the nodes' attributes could improve the performance of graph fusion methods [START_REF] Yu | A bottom-up framework for construction of structured semantic 3d scene graph[END_REF][START_REF] Kim | 3-d scene graph: A sparse and semantic representation of physical environments for intelligent agents[END_REF], their node-matching processes still ignore the relative spatial knowledge provided by the graphs' topology. The local and global graphs are practically reduced to a list of objects with attributes, and edges are only reintroduced when new nodes need to be attached the reference. As mentioned before, this can be attributed to the lack of stable relationships extracted from the images when forming the 2D graphs, which would make the edges an unreliable means of identification for the few nodes they connect. However, with a more robust way of generating the edges, the topology of the graph could be a determining factor in graph fusion processes.

Ignoring the graphs' topologies may provide the necessary time gain for those methods [START_REF] Yu | A bottom-up framework for construction of structured semantic 3d scene graph[END_REF][START_REF] Kim | 3-d scene graph: A sparse and semantic representation of physical environments for intelligent agents[END_REF] to produce and merge the local graphs at a sufficient frame rate so as to guarantee sufficient overlap in the content of the analysed images for real time analysis (such as for MR or robotics). However, matching individual nodes cannot sufficiently discriminate between multiple instances of the same objects in the scene, and ignores the benefits of a multi-view observation of the scene to determine spatial relationships. If the pose estimation of the capture device was to become unreliable or unavailable -due to, for instance, overly quick movements or loss of GPS information-similar objects at different places could be merged, leading to wrong edges to be drawn without ever being removed. Attempting to preserve graph topology during fusion can provide some stability during fusion and retain the spatial information contained in the edges. Only with said stability can changes be accurately detected.

Graph subsumption

A graph isomorphism is an equivalence relationship between two graphs for which there exists a bijection between the nodes of each graph which preserves adjacency. When two graphs are different -and therefore no bijection exists for all nodes-only subgraph isomorphism is possible and is referred to as "graph subsumption". In the context of semantic graphs, the constraint of matching the nodes' and edges' attributes is added on top of the preservation of topology. Graph-based localisation and "graph matching" are analogous when one graph -the query, which represents the current point of viewis much smaller than the other -the reference, which represents to global environment. Graph matching tools already are the backbone of previously mentioned applications, such as image database searching [START_REF] Johnson | Image retrieval using scene graphs[END_REF]. For instance, the searching process was improved upon by using a catalogue graph that links all the existing types of nodes and edges to the images in which they appear [START_REF] Ramnath | Scene graph based image retrieval -a case study on the clevr dataset[END_REF]. These works [START_REF] Johnson | Image retrieval using scene graphs[END_REF][START_REF] Ramnath | Scene graph based image retrieval -a case study on the clevr dataset[END_REF] are seemingly applicable to the field of MR as their visual-semantic graphs also use nodes to tally the objects of a scene and edges to describe their interactions or relationships.

In order to efficiently compare two graphs with attributes, "node descriptors" can be used to encode the local topology of the graphs around each node. When several nodes share similar attributes in the same graph, this helps in differentiating between said nodes. For SGs, this helps in recognizing specific instances of the same type of object in the scene, as they would share the same label. In the field of large-scale re-localisation in semi-static environments, where nodes correspond to semantically consistent contiguous areas, there exist several approaches for exploring and encoding the local topology around each node. Works such as [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF] ("X-View") and [START_REF] Liu | Global localization with object-level semantics and topology[END_REF] employ an arbitrary number of "random walks", which start at the studied node and take a constant number of steps from it along the edges. Alternatively, [START_REF] Stumm | Robust visual place recognition with graph kernels[END_REF] and [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] exhaustively explore the local topology, but with a usually smaller number of steps -in fact [START_REF] Stumm | Robust visual place recognition with graph kernels[END_REF] only checks each node's direct neighbours. The processes involved in the generation and comparison of each descriptor will be further developed in Chapter 5.

We notice that in the above-mentioned localisation methods, the edges of the graphs are considered unlabelled, as only the nodes' and their neighbours' attributes are stored in the descriptors. Edges merely reflect whether or not the relative distance based on two nodes' spatial attributes falls under an arbitrary threshold. Attempting to store the nature of the relationships in exhaustive descriptors such as those of [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] may be too costly in terms of memory -which is why the number of steps is limited in the first place. The random walk approach would not be impacted as severely but the increased amount of classes involved could necessitate a higher number of walks to better represent the local topology, especially if multiple relationships per node pair are allowed. Additionally, both [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] and [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF] are designed for outdoor scenes, which are more prone to environmental -photometric-changes but are less semantically dense and dynamic than indoor ones. Outdoor scenes present larger and more spread out objects, which makes each partial view of the environment more unique and camera pose estimation errors -specifically errors in translation-relatively less significant. Translating those methods to indoor applications requires consideration for the increased number of classes and relative size of the query graphs to the reference, and if the current definition of edges is suitable.

Finally, we must note that [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF] and [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] both take as input sequences of relatively registered RGB-D frames: the relative movements of the camera between each frame within a sequence are known, but the sequences do not share the same "global" coordinate system, hence the need for localisation. They therefore include their own graph fusion methods to produce the query and reference graphs, which rely on 2D semantic analysis and are exclusively node-based. The fusion process is not required to perfectly merge same-object nodes across frames, and the number of classes detected is limited to accommodate the descriptor used, i.e., to limit memory consumption and processing time. Therefore, contrary to the graph generation methods from Subsection 4.3.3, these localisation methods do not produce graphs useful for scene description, and [START_REF] Qin | Semantic loop closure detection based on graph matching in multi-objects scenes[END_REF] even remarks that object classification can be wrong as long as it is consistent.

Conclusion: Scene Graphs for Change Detection

Like the localisation task, the change detection task requires the existence of a reference -or prior-which can be of a different nature from the current view of the environment. In the case of X-View [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF], both the query and reference are built from the same rudimentary graph fusion process, whose inconsistencies can be ignored given the robustness of the final matching algorithm. This is true of most localisation methods, especially in dynamic scenes: the underlying goal of the task is to find enough of the most reliable -recognizable and stable-features of the scene to match the query to the reference [START_REF] Derner | Towards life-long autonomy of mobile robots through feature-based change detection[END_REF].

With these tools, performing change detection by listing the unmatched features of the query and prior would result in many false positives and untracked changes. The detected changes would also need to be translated back into a meaningful representation of the scene, which could include a filtering step but would not retrieve the missed changes. In conclusion, the state of the art methods in SGs generation and matching are not designed to adequately perform the scene CD and model maintenance tasks that are required for MR applications using current semantic graph tools.

Experiments with the scene representation

Using the capabilities of a standard MR device, the accessible data to produce the query graph is the RGB image and a corresponding depth map provided by the cameras with some positional information: as a consequence, we can use image-based graph generation. With this assumption, we first altered the graph fusion pipeline proposed in [START_REF] Kim | 3-d scene graph: A sparse and semantic representation of physical environments for intelligent agents[END_REF] (previously mentioned in Subsection 4.3.3) to include the localisation and comparison to a graph prior generated by the original algorithm. We found that its node matching process is reliable given an accurate pose estimate, but it is limited by the object detection capabilities of Factorizable-Net [START_REF] Li | Factorizable net: An efficient subgraph-based framework for scene graph generation[END_REF]. The detection is inconsistent from frame to frame and most objects in the scene are unaccounted for, even when only considering the classes the network was trained on. To improve the process, another 2D SG generator was experimented with, Graph R-CNN [START_REF] Yang | Graph R-CNN for scene graph generation[END_REF], which gave much more consistent results along the sequence but still recognized a limited number of objects. Both 2D SG generators also produced very few relationships edges, which were further filtered out during fusion. Switching to alternative generators designed to augment the number of edges -such as Align R-CNN [START_REF] Tajrobehkar | Align r-cnn: A pairwise head network for visual relationship detection[END_REF]-would not fix this issue, due to their focus on describing the events occurring in the image rather than the scene layout. Therefore, our graph representation should include edges provided by geometric analysis of the nodes' attributes [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF][START_REF] Guo | Learning to measure change: Fully convolutional siamese metric networks for scene change detection[END_REF], rather than 2D semantic analysis, as the former provide a more stable representation of the scene layout -thanks to the reliable extraction of nodes' geometric attributes-and would be better suited to CD.

For the purpose of evaluating a change detection method, it is more practical to assume that the prior is an exhaustive and accurate representation of the scene, from which the perceived current state differs. The problem of detecting the mistakes made during the construction of a prior using newly acquired information is more akin to robust scene representation generation, which could be tackled with or without actual changes. Using the knowledge that the scene prior is "perfect", the shortcomings of the change detection method can only come from the sensing of the scene's current state or failure to interpret the sensor's readings.

In summary, we will make the following hypotheses:

the AR device is equipped with sensors allowing it to produce a depth map in addition to the corresponding RGB image and camera pose estimation, these readings can be semantically analysed to identify the objects in the scene, which are the labelled nodes of our SG representation with geometric attributes, the edges of the SG are produced from geometric analysis of the nodes' attributes, giving the graph a topology based on the scene layout rather than object interactions, when evaluating a CD method, the prior representation must be accurate and exhaustively describe the properties that are tracked by the method.

Problems to solve to achieve the thesis goals

After focusing on a photo-geometric CD method in the previous chapter [START_REF] Roupin | Detection of removed objects in 3D meshes using up-to-date images for mixed-reality applications[END_REF], we have now chosen to work with a SG representation to deal with the scene's semantic contents.

With the new hypotheses made in Subsection 4.4.1, we have identified four problems to solve to achieve our current goal of change detection for MR with scene graphs:

1-Semantic change detection between two complete scene graphs.

We assume that the current state of the scene is described in a similar manner as the prior: it covers the same spatial regions with the same level of detail. The two graphs must first be aligned using graph subsumption, where the most similar nodes are matched. Once this is achieved, we can detect changes of two forms: the modification of graph topology (addition or removal of nodes) and the modification of node attributes (besides their label). This second form of change is the result of the flexibility of the matching algorithm: nodes with different attributes can be matched because we should not assume that properties such as illumination will remain constant over time. In addition, simply regarding a node's change of attributes as replacement by another node -consecutive removals and additions-would not allow for the tracking of changes of a specific object instance. Finally, we notice that spatial and visual attributes (colors, shape, material etc.) are necessary to track changes in unclassified nodes.

2-Semantic change detection with a partial query and a complete prior.

This problem will occur in MR applications, where change detection may need to be performed live without preemptively scanning the whole scene. An added challenge from the first problem lies in the complexity of the graph matching step, since less information will be available from a partial view of the scene than a global one. The criteria for matching nodes representing large objects (e.g., walls) also changes, as the areas they cover are unlikely to be fully visible. Once the query graph is directly localised in the prior, there is then the issue of differentiating between actual changes and the absence of nodes due to the limited field of view or occlusions. Occluded or out-ofview objects still matter during MR experiences, as they can affect the behaviour of virtual agents (on-screen or off-screen) or the rendering of virtual content (physicallybased lighting, reflections, shadows etc.) and therefore cannot simply be removed from the scene model. Limiting the scope of the CD to the partial scene may require the reconstruction of the camera's point of view -effectively finding the relevant sub-graph in the prior-based on current node visibility and the relative change in size and shape of nodes representing large areas (partial visibility). We note that this problem may be unsolvable if the information on the current state is too sparse, in which case the problem will reside in minimizing this minimum data requirements (i.e., the time and effort required from an MR user at the beginning of a session).

3-Local scene graph extraction guided by the global prior.

If we take into account the limitations of hardware of the MR device at the time that CD is performed, the use of the prior data is required to fill the knowledge gaps and accurately detect changes. Attempting to recreate the exhaustiveness of the prior from low quality observations will result in many missed or misidentified objects, where the use of the prior may provide additional information in the shape of regions of interest. The prior also defines contents of the scene relevant to the MR application, and failure to explicitly track their changes will therefore lead to issues during the experience.

However, if we were to use the prior to generate the local query, the matching process becomes two-fold: a preliminary query must be proposed and localised in the global prior to be able to use the local properties of the prior and to subsequently generate a more accurate query before CD. This may only be required at the start of the MR session or when the pose estimation becomes unavailable, and a preliminary query graph may be accurate enough to significantly reduce the number of potential matches in the prior.

4-Geometric update of the model from semantic CD.

In the three previous problems, we avoid the issue of the initial construction of the graph prior, since its efficient and accurate generation does not directly relate to the change detection task. However, the tools used to produce this prior graph and its contents will ultimately dictate the nature of the changes that can be detected and how the scene representation may be updated. We must design a prior and method to allow the conversion of semantic results of the change detection into geometric or photometric updates of the scene model. This can for instance be done using a layered SG representation [START_REF] Armeni | 3d scene graph: A structure for unified semantics, 3d space, and camera[END_REF][START_REF] Rosinol | 3d dynamic scene graphs: Actionable spatial perception with places, objects, and humans[END_REF], or any prescriptive graph-inspired structure that would allows us to link the relevant photo-geometric data to the nodes and their attributes (as explained in Subsection 4.2.1).

The only data that would need to be retrieved by the MR device would be that which relates to novel or altered objects in the scene. The textures and geometric data could be recovered and refined over time using the available sensors [START_REF] Furrer | Incremental object database: Building 3d models from multiple partial observations[END_REF], but accurate semantic analysis would allow us to duplicate such data from identical objects in the scene, or from an existing database [START_REF] Shao | An interactive approach to semantic modeling of indoor scenes with an RGBD camera[END_REF].

In the following Chapter 5, we will consequently tackle the first of the above-mentioned problems by introducing our graph generation and registration pipeline. In order to have graphs of similar nature for the query and reference, they will both be produced from sequences of relatively registered RGB-D frames, as to emulate the available sensors from an AR device. Finally, the registration of the SGs will be performed using node matching -based the graphs' topologies and the nodes' semantic labels. The elaboration of a robust node matching process for the registration should ultimately lead to an effective object tracking method to be used for CD.

Chapter 5

Graph-based model registration for semantically rich scenes

In an AR experience, persistent virtual content is content whose state and locations in the real world are preserved between AR sessions. When changes occurs in the real scene between sessions, the persistent content can be integrated in the new scene layout based on its spatial relationships with real world objects rather than absolute coordinates, for a more realistic behaviour [START_REF] Haller | Photorealism or/and non-photorealism in augmented reality[END_REF][START_REF] Lang | Virtual agent positioning driven by scene semantics in mixed reality[END_REF]. As shown in Chapter 4, the detection of such objects and relationships can be achieved through semantic analysis of the scene as perceived by the AR device, the results of which are stored in a semantic Scene Graph (SG) as nodes and edges respectively. Using graph matching, this semantic information is enough to register two instances of a scene -from a previous AR session and the current one-without additional extraction or reconstruction of 3D geometry. In this chapter, we propose a novel node descriptor to compute node similarity during the matching, which encodes the node's label (i.e., the object's class) as well as local topology (i.e., objects' relationships). The size of this new descriptor increases only linearly with the depth of the SG exploration as opposed to the exponential growth seen in the state-of-the-art, without sacrificing matching performance. We also introduce a graph generation algorithm that provides an object-level representation of the scene to improve its semantic understanding for AR applications, without compromising the registration performance. We prepare and use subsets of ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] and ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF] as scene registration datasets, and propose a specialised metric for evaluating said registration. The method properties are summarized in Table 5.1. In an AR session, the contents of the scene can be semantically and spatially represented by a scene graph so that virtual objects can behave in a realistic manner. Left: A reference graph captured during a past session and a virtual object attached to a "table" node (magenta arrow). Right: A query graph generated from the current state of the scene and must be registered to the reference to restore the virtual object. The registration is achieved through semantic node matching (blue arrows).

Introduction

In the previous Chapter 4, we noted that in a number of emerging AR applications such as photo-realistic rendering [START_REF] Rohmer | Interactive near-field illumination for photorealistic augmented reality on mobile devices[END_REF][START_REF] Prakash | Gleam: An illumination estimation framework for real-time photorealistic augmented reality on mobile devices[END_REF][START_REF] Pereira | Blending real and virtual objects in augmented reality environments[END_REF] and environment-guided storytelling [START_REF] Chen | Scenear: Scene-based micro narratives for sharing and remixing in augmented reality[END_REF][START_REF] Li | Interactive augmented reality storytelling guided by scene semantics[END_REF], being able to rapidly detect changes in the scene from one AR session to the next is critical in order to enable a realistic immersive experience for the user. This can be efficiently achieved when the real world is already segmented into objects or areas that are relevant to the application. For such applications [START_REF] Lang | Virtual agent positioning driven by scene semantics in mixed reality[END_REF][START_REF] Chen | Dasnet: Dual attentive fully convolutional siamese networks for change detection of high resolution satellite images[END_REF], the positioning of virtual objects in relation to the ones present in the real world is more relevant than their absolute coordinates [START_REF] Hebborn | Towards Believable Augmented Reality: Combining the Real and Virtual Worlds[END_REF]. This can offer more flexibility in the placement of virtual objects to improve the readability and facilitate user interaction [START_REF] Cheng | Semanticadapt: Optimizationbased adaptation of mixed reality layouts leveraging virtual-physical semantic connections[END_REF], or to help increase the realism of their interactions with real objects [START_REF] Liang | Scene-aware behavior synthesis for virtual pets in mixed reality[END_REF]. Previously, fiducial markers have been used to place virtual objects or to help user navigation [START_REF] Kato | Virtual object manipulation on a table-top ar environment[END_REF][START_REF] Olson | Apriltag: A robust and flexible visual fiducial system[END_REF], but semantic analysis of the scene has also been able to provide usable landmarks [START_REF] Liu | Spatial knowledge acquisition with virtual semantic landmarks in mixed reality-based indoor navigation[END_REF]. This has led to the use of semantically-oriented representations of the AR scene, which allow convenient storage and processing of the virtual and real objects and their relationships [START_REF] Tahara | Retargetable ar: Contextaware augmented reality in indoor scenes based on 3d scene graph[END_REF]. These representations often take the form of a scene graph [START_REF] Johnson | Image retrieval using scene graphs[END_REF], where the nodes represent objects or areas and the edges represent spatial or more general relationships between those objects. Such graphs provide a lightweight and versatile representation of the scene, especially on portable consumer devices that lack processing power or complex sensors.

At the start of a new AR session in a previously visited real environment, any persistent virtual content needs to be reintegrated in its correct location despite potential layout changes in the real world. For instance, virtual objects that appear to be resting upon a real table should follow the movements of said table between sessions (see in Figure 5.1). Regardless of the presence of such changes, the AR device will likely be started in a different position and orientation, and the video feed it captures will showcase different parts of the scene every time. In this chapter, we aim to register two image sequences of a real scene, which represent the AR device video feeds of two different sessions, using the same graph representation whose purpose is to integrate the AR content in the real scene. Our proposed registration method makes use of information that is already necessary to the execution of the AR application -i.e., the scene graph-and will ultimately simplify the tasks of detecting changes and updating this representation of the scene. From this process we obtain both a 3D transformation aligning the two scene instances' coordinate systems, as well as a list of matching graph nodes -i.e. a list of consistent real objects between the two sessions-onto which to anchor the virtual content (see Figure 5.1). We also noticed in Chapter 4 that the use of such semantic graph-based localisation methods is usually limited to outdoor environments [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF][START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF], so we evaluate the pertinence of our method for indoor scenes from the ScanNet dataset [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF], which contains a high variety of objects in spatially restricted environments. We also observe its behaviour in larger changing environments, such as the photo-realistic virtual warehouses present in the ChangeSim dataset [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF].

In our method, a scene graph is generated from each of the two image sequences captured at different times, and individual nodes are matched between the two graphs to identify corresponding areas in the scenes. The nodes of a graph represent the real objects in the scene using a semantic label -the object's class-and a 3D point -the object's center's local coordinates in the session-while the edges give a simplified account of the scene's structure by connecting objects close to each other. From the labels and edges, a node descriptor can be generated for each node in one graph and compared against the node descriptors in the other graph, to measure their similarity. Once nodes are matched based on their similarity, the 3D points of the matched nodes can be used to estimate the transformation between the sequences (scene instances). The quality of this estimation derives from the accuracy of the matching process, which in turn relies on the effectiveness of the descriptors used. The registration results from our method are compared to a state-of-the-art descriptor-based approach [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] to evaluate the usefulness of the descriptors. Compared to this earlier work, the size of our descriptor only increases linearly with the depth of graph exploration when generating the descriptor, or the number of different object classes, as opposed to exponentially. Furthermore, we tailor our approach to AR applications, where the SGs generated can be used for purposes beyond the registration -such as interactivity between real and virtual agents-and where additional node attributes can be provided by other processes -such as color or material for photorealistic rendering in MR experiences. As such, we propose a variant of the graph generation algorithm where the object segmentation of the scene (into graph nodes) more closely matches the real world instance segmentation.

Our contributions are the following:

A new lightweight and effective node descriptor based on the adjacency matrix of the scene graph.

An alternative scene graph generation algorithm from image sequences, which better preserves object instance segmentation.

A bounding box-based Root-Mean-Square Deviation (RMSD) metric applied to the evaluation of indoor scenes registration.

Methodologies to process and use ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] and ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF] as semantic model alignment datasets.

Section 5.2 is dedicated to an overview of the related graph-based scene registrations methods and the existing processes for evaluating said registration. Our proposal is documented in Section 5.3, and the preparation of the experiments and results are explained in Section 5.4. Finally, our conclusions are summarized in Section 5.5.

Related Work

In Chapter 4, we surveyed the works related to the use of semantic graphs for scene understanding. Notably, we found that such graphs would often be generated and compared against each other through node matching to provide quick and robust localisation within said scene. In this section, we will focus on the means by which these works can compute node similarity for matching, and their limitations in the context of indoor scene registration.

Graph-based localisation and descriptors

In this chapter, graph matching refers to a weaker variant of graph isomorphism, previously defined in Chapter 4. Instead of searching for a bijective mapping between the nodes of two graphs, the focus is on finding pairs of nodes which are similar according to a predefined metric. This process is closer to graph subsumption because there is no assumption that a perfect pairing can be found between the nodes or that the graphs have the same size. Therefore, the edges of the graph become the mean to identify individual nodes through the observation of their surroundings. In order to process this topological information efficiently when comparing nodes, it is encoded into node descriptors.

Neighbourhood vectors

The use of SGs as an retrieval tool from image database [START_REF] Johnson | Image retrieval using scene graphs[END_REF][START_REF] Ganea | Graph object oriented database for semantic image retrieval[END_REF][START_REF] Ramnath | Scene graph based image retrieval -a case study on the clevr dataset[END_REF] allows them to be effective in visual place recognition [START_REF] Pion | Benchmarking image retrieval for visual localization[END_REF]. Such a problem was tackled in [START_REF] Stumm | Robust visual place recognition with graph kernels[END_REF], where landmarks of the environment were stored as labelled nodes in a graph connected by edges weighted by the number of times the landmarks appeared together.

Inspired by the Weisfeiler-Lehman isomorphism test [START_REF] Shervashidze | Weisfeiler-lehman graph kernels[END_REF], the graph matching method used in [START_REF] Stumm | Robust visual place recognition with graph kernels[END_REF] substitutes each node's label with a vector representing its direct neighbourhood. The vector is sized according to the number of labels, and acts as a histogram where each bin is the sum of the weights of the edges going from the node to one of its neighbours' labels.

The similarity between two nodes can then be measured using a normalized dot product of the nodes' corresponding vectors, which serve as node descriptors. However, the topology is only recorded with a depth of 2, i.e., one step away from the node described.

Random walk

In order to record the local topology around nodes with an arbitrary depth, random walks can be used [START_REF] Liu | Global localization with object-level semantics and topology[END_REF][START_REF] Wang | Lightweight objectlevel topological semantic mapping and long-term global localization based on graph matching[END_REF]. To describe the nodes, X-View [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF] generates a fixed number of random walks with a fixed number of steps, and stores the explored labels in a 2D array. Each row corresponds to a specific walk and exploration rules can be added to avoid duplicated walks or to limit the number of times nodes can be visited, in order to provide more useful descriptors. Contrary to the vector approach [START_REF] Stumm | Robust visual place recognition with graph kernels[END_REF], the finite number of walks introduces an element of randomness during the generation of descriptors. Moreover, the measure of similarity between descriptors involves a time consuming process of finding identical walks which also limits the depth and number of walks that can be used.

Walk histograms

Solving the aforementioned issue of randomness, [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] performs an exhaustive tallying of the walks from each node and stores the result as a vector-like histogram. The search can be performed with any depth, but the number of steps in the walks is limited to 2 in the paper. This is due to the rapidly expanding size of the stored descriptors with increasing depth: like the neighbourhood vector [START_REF] Shervashidze | Weisfeiler-lehman graph kernels[END_REF], the size of the walk histogram increases with the number of labels in the scene. Since the walks can be seen as label triplets, the histogram's length is the number of labels cubed.

The exhaustiveness of this method allows for the use of the normalized dot product as a similarity metric, therefore combining the convenience of [START_REF] Shervashidze | Weisfeiler-lehman graph kernels[END_REF] with the descriptive powers of [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF]. However, this representation of the topology would be impractical in scenes with a large number of object labels, as the histogram's size would exponentially increase while most of its bins would remain empty.

In this chapter, we propose an alternative representation of the local topology around each node with only a linear increase in size with the depth or number of labels, thanks to the elimination of the redundant information contained in the walk histogram. This new adjacency matrix-based descriptor can also be compared using the normalized dot product, being a vector-like histogram. We therefore keep the advantages of the deterministic walk histogram approach while having more control over the size of the descriptors.

Quality metrics for scene registration

Point clouds are often used to represent the geometry of scenes as they can be directly obtained from real environments using the fusion of RGB-D images [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF], high-resolution laser scanning [START_REF] Baruch | ARKitscenes: A diverse real-world dataset for 3D indoor scene understanding using mobile RGB-d data[END_REF] or multi-view stereo reconstruction [START_REF] Schöps | A multi-view stereo benchmark with high-resolution images and multi-camera videos[END_REF]. As such, there are many works in scene registration whose performances are evaluated based on the use of clouds as input data, yet these quality metrics can also be applied to our graph-based method.

The registration of two clouds can be evaluated through the calculation of the rotation and translation errors compared to a ground truth transformation. However, [START_REF] Fontana | A benchmark for point clouds registration algorithms[END_REF] underlines that having two separate metrics or an arbitrarily weighted sum of the two is not convenient to compare registration methods. [START_REF] Fontana | A benchmark for point clouds registration algorithms[END_REF] cites RMSD [START_REF] Myronenko | Point set registration: Coherent point drift[END_REF] (or RMSE) as a suitable metric which can be computed by taking all "homologous" point pairings between the reference and the transformed source and measuring their squared distances, averaging the result and taking the square root. Homologous points in a point cloud pair, are points which correspond to the same region of space in both clouds. To avoid the need for finding such point pairings, [START_REF] Mazzotti | A measure of the distance between two rigid-body poses based on the use of platonic solids[END_REF] proposes to model the clouds as platonic solids, and only measure the distance for their vertices. RMSD can also be computed using only the points of the source, by comparing the cloud transformed using the estimation to one transformed using the ground truth [START_REF] Zhang | Fast and robust iterative closest point[END_REF]. Finally, an earlier work [START_REF] Jenkinson | Measuring transformation error by rms deviation[END_REF], deals with the registration of brains by abstracting such objects as "volumes", and replacing the numerical summation of distances over the points of a cloud -or a solid-by a formal integration of the RMSD function over a sphere of a given radius. Since the method in this chapter is focused on indoor scenes, we can perform a similar abstraction by using the scene's bounding box as its shape, and formally integrate the RMSD over the resulting volume. In effect, this will make the error independent of the scene's layout -i.e., the error is based on the scene's boundaries (walls) rather than its contents (objects)-which we assume to be desirable in changing environments.

Proposed method for scene registration

Pipeline

Since this work is mostly concerned with the elaboration and evaluation of the new node descriptor and graph extractor, the scene registration pipeline is similar to the ones described in [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF] and [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] as shown in Figure 5.2. The process takes as input two semantically segmented representations of the same scene, and outputs an estimation of the transformation between the two corresponding world coordinate systems. Scene registration from semantic information. Two instances "A" and "B" of the same scene are each represented by a sequence of semantically segmented images, with corresponding depth maps and camera poses. The two sets of poses do not use the same world coordinate system, so the semantic information from the images is used to register A and B through the construction and matching of two semantic graphs.

Input data

Each scene instance is represented as a semantically segmented image sequence with associated depth and pose information. These sequences are chronologically sorted sets of images taken at short regular intervals, a simulation of the footage captured by an AR device as an AR session is running. For the ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] sequences, the frame-rate of capture is 30Hz.

The images store the labels of the visible objects pixel-wise (as seen in Figure 5.1), and 3D geometric information can be recovered from the depth maps in conjunction with the intrinsic and extrinsic matrices of the capturing device for each frame.

Point Cloud extraction

The SGs are first generated through the extraction of 3D points from the sequences, corresponding to the graphs' nodes. For each segmented image, the barycentres of uniformly labelled regions whose area exceeds a fixed threshold are computed using a four-way flood-fill algorithm. These 2D barycentres are turned into 3D points using the depth and pose, and added to a sparse "labelled" point cloud -an edgeless graph of nodes with spatial attributes and a label each-unless they are filtered based on their proximity to existing points.

For instance, in [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] new points with the same label and within a 3D distance threshold T object of already present points in the cloud are ignored. This threshold allows for small regions/objects seen across multiple frames to be recorded as single nodes. As a side effect, objects whose diameter exceeds T object are broken up into several nodes, and since the objects' volume are not recorded, using multiple nodes helps in representing the structure of the scene. However, this is undesirable if the instance segmentation of the scene is to be preserved in the final graph, and increases the influence of the camera path during scene exploration. Indeed, the spatial attributes of a node will be inferred from the first detection of its corresponding region/object in the image sequence, which will likely be at the edge of the frame in question. The object may consequently only be partially visible for that first detection and the depth estimation may be less accurate far from the frame's center: the spatial attributes will not accurately reflect the position of the object in the scene.

In Subsection 5.3.2, we describe an alternative point processing method which addresses both the object fragmentation and localisation concerns, while preserving the necessary scene structure information. The resulting graph has two layers: a bottom layer containing the aforementioned -now unfiltered-3D points, and a top layer used to group those points into object instances using T object . We call the resulting nodes in the top layer "Super Nodes" (SN). SNs are similarly used for the semantic graph matching as the nodes produced by the algorithm from [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] -now referred to as "Legacy Nodes" (LN)-but represent whole objects in the scene rather than semantically consistent areas of arbitrary size.

Graph construction

To build the graph, every pair of nodes (i.e., SN or LN) whose distance falls under a threshold T edge based on the scene's size, is connected by an edge. When using LNs and setting this threshold higher than T object , large objects can always be represented by several interconnected nodes. In practice, we use an automatic threshold that scales with the average distance between nodes pairs in the graph based on their spatial attributes. T edge is set to avoid orphan nodes while not making the graph too dense, which would make the local topologies around each node less unique. Empirically, we found that setting T edge to 75% of the square root of the average squared node pair distance in the graph yielded 40% to 60% connectivity in the resulting topology. In this context, connectivity percentage refers to the number of existing edges in the graph over the total number of possible edges.

The edges give a simplified account of the spatial structure of the scene, where the distance between two objects can be represented by the number of steps they are separated by. The graphs' topologies are stored in symmetric binary adjacency matrices with zeros on their diagonals. They are considered "simple graphs": edges are undirected and unweighted, nodes cannot be connected to themselves, and node pairs can be connected by a single edge at most. Simple graphs with n nodes have at most n(n -1)/2 edges.

Graph matching

Once the graphs are generated, the local topology around each node is exploited to produce a node descriptor based exclusively on the labels and edges. This process is further detailed in Subsection 5.3.3. The descriptors are compared using a vector normalized dot product, similarly to [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF]. This results in a list of the most similar nodes in both graphs according to the semantics and simplified scene structure. This can also be seen as a list of matching 3D points between the two clouds.

Registration

The transformation between the two image sequences is estimated by minimizing the error when transforming nodes from one graph to their matches in the other.

The previous work [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] also uses the ICP-RANSAC algorithm [START_REF] Besl | A method for registration of 3-d shapes[END_REF] in order to filter out outliers that negatively affect the registration. The presence of those outliers is unavoidable even with a theoretically perfect graph matching. Indeed, as mentioned in Subsection 5.3.1.2, due to the sequential extraction of 3D points, when using LNs, the location of the objects is defined by the parts that first appear in the sequence. This can cause correctly matched nodes to be located at points that are separated by -at mostthe diameter of the object they represent. The effect is not as pronounced using SNs, but slight changes in the scene or imprecisions in the 3D point extractions will still lead semantically sound matches to be spatially inaccurate.

The graph matching quality is ultimately evaluated by the closeness of the estimated transform to the ground truth from the dataset. For this reason, node filtering through RANSAC can be disabled, therefore forcing the registration algorithm to use all the matches found, allowing for a better comparison the matching performance of the node descriptors.

Super Nodes for graph generation

For every frame in the input sequences, the regions of the segmentation map -which store the object labels (see Subsection 5.3.1.1)-are converted into 3D points based on their 2D barycentre and the associated pose and depth map. Since this is performed at every frame, with a high enough frame rate, the same regions in space are likely to be observed several times. Even when filtering out similar-looking consecutive frames, large objects and structures would likely be often visible, and the camera will eventually capture the same areas over time.

In order to limit the size of the resulting scene graph, and get a better objectlevel understanding of the scene, previous graph extraction methods such as [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] do not add new LNs if there is already a node with the same label within a distance T object (see Subsection 5.3.1.2). However, constructing the graphs with these LNs leads to the previously mentioned issues: a fragmentation of large objects, and spatial attributes that do not match the objects' actual 3D barycentre.

To solve this, we introduce SNs, which can contain a multitude of 3D points rather than a single attribute vector of 3D coordinates. Like LNs, every SN has a single label, which is the same label shared by all the points belonging to it. We define the distance between a 3D point and a SN as the smallest distance between the former and any point belonging to the latter. Consequently, the distance between two SNs can be defined as the smallest distance between one SN and any point belonging to the other. Using these metrics, a new 3D point is identified as a "duplicate" when its distance to an existing SN with the same label falls under T object . When this occurs, rather than being ignored, the new point is added to the corresponding SN. If the new point were to be added to multiple SNs using this criteria, they all are merged into a single SN -containing all their respective points and said new point. This greatly alleviates the problem of object fragmentation, as the delimitation threshold can be tested at the extremities of large objects, which are updated as they include more points, matching their spread in the real world. The volume of large objects can be inferred from the 3D points within their corresponding SN, rather than multiple LNs of the same label separated by T object . Consequently, it is the distance between two SNs that is used to create the graph topology.

The use of SNs also allows for filtering out a posteriori some of the errors introduced by the sensors. Indeed if the pose estimation momentarily fails or artefacts appear in the depth map, a few extracted points may be incorrectly identified as new objects and added to the graph. Once the extraction is over, those anomalies can be removed using a minimum threshold T super on the number of points a SN must contain. If we require the object to be visible for at least 5 frames to be added to the graph as a SN, we should set T super higher than 5, since several points can be extracted per frame. In practise we use T super = 10.

Figure 5.3 shows how LN and SN extraction processes differ for a specific object: a "counter", which only appears once in the scene. The counter is first detected in frame 165, and the corresponding LN and SN are added to their respective LN-graph and SN-graph. Initially, both the LN and the SN have the same spatial attribute, which corresponds to the 3D location of the object's first sighting (the SN contains a single 3D point). In frame 413, the location at which the "counter" is detected is further than T object away from its original detection, therefore a new LN is added to the LNgraph. The object has now been fragmented into multiple LNs, each localized at the extremities of the "counter" seen in frame 165 and 413. Conversely, in the SN-graph, the 3D location of the SN is simply averaged from all the counter's detection locations since the creation of the SN. The 3D points contained in said SN all have a neighbouring 3D point within a T object distance, and the two "counter" LNs in the LN-graph correspond to the extremities of the cloud formed by these 3D points at frame 413. Frame 978 is the last "counter" detection in the image sequence, no LNs have been added since frame 413, but the location of the SN has been updated based on all the object's sightings. In conclusion, rather than representing the object's size by breaking it into two LNs -neither giving an accurate location of the object's center position-a single SN can be used for a more faithful object-level representation of the scene.

It should be noted that generating a graph using SNs is momentarily more memory intensive than using LNs, as more 3D coordinate vectors are stored. The resulting graphs will however end up with fewer labelled nodes to be used during matching due to the diminished fragmentation, and therefore fewer descriptors will be generated. Moreover, the registration step described in Subsection 5.3.1.5 requires the SNs to have their own 3D coordinates, as using every single point within them to compute the 3D transform is too computationally expensive. Therefore, the final step of graph creation using SNs is the computation of the SNs' spatial attribute -their location in 3D space-by averaging the 3D coordinates of the points they contain. The resulting attribute should be closer to the real objects' barycentre, especially for small objects. Finally, following the creation of the edges, the SNs' 3D points are no longer required -only the SNs' labels and spatial attributes-allowing us to free the corresponding allocated memory if necessary.

Frame 165

Frame 413 Frame 978

LNs SNs "Counter"

Adjacency descriptor

Previous node descriptors relied on tallying the paths that can be taken from each node to describe its surrounding topology. The maximum number of unique possible walks of depth d -corresponding to d -1 steps-among nodes with one of l labels is l d . While only a fraction of these unique walks will be present in any graph, in the random walk approach from [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF] the number of walks in each descriptor must still be large enough to avoid cases where a lack of identical walks among descriptors makes matching impossible.

For the histogram method of [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF], the size s H (l, d) of each descriptor will always be l d , but most of the bins will remain empty: since a given node has only one label, only a maximum of l (d-1) bins are ever used, and for every label not present at depth k, there are an additional l (d-k) empty bins.

In order to describe the neighbourhood around each node with a larger depth and in scenes with a high diversity of objects, we propose a descriptor that tallies only the end label of each walk. Based on the adjacency matrix of the SG, the descriptor's size only increases linearly with the depth and number of labels.

Basic descriptor using the adjacency matrix

Given the adjacency matrix A of a graph G with n nodes, the element (i, j) of A k indicates the number of walks with k steps between two nodes i and j. Based on the symmetry of the adjacency matrix, each i-th column or row of A k will therefore give a description at depth k + 1 of the neighbourhood of node i.

We can fit this description into a histogram V k,i of size l using the list of nodes' labels L as a look-up table. L is of size n, and with values between 1 and l, mapping each node's index to its label's index. In practice, for every node j, if

A (k) i,j = (A k ) i,j is positive then V (k,i) L j is incremented.
Since V k,i only contains information for depth k + 1, we compute it for every k between 1 and d -1 (d being the desired exploration depth) to get a full account of the local topology. We also encode the node's label using a vector V 0,i of size l that is null except for its L i -th element that is set to 1. For a node i, its descriptor D d,i at depth d is obtained by concatenating the (V i,k ) for k between 0 and d -1. By tallying only the end points for walks of depth 1 to d, each D d,i is only of size s D (l, d) = l × d, and no space is wasted accounting for walks that cannot be taken in G.

Since A is already computed as the representation of the topology of G, increasing the depth of exploration comes at no great computational cost as only one symmetrical matrix product of size n is required to update all n descriptors.

The basic algorithm for computing all the descriptors for G is described in Algorithm 4 and an example with a small graph is shown in Figure 5.4.

Algorithm 4: Pseudo-code for our descriptor generation algorithm. The i-th element of a vector X j is noted as

X (j) i DescriptorGenerator (A, d, L) inputs : Adjacency matrix A; Depth d; Label vector L output: List of n descriptors (D d,i ) 1≤i≤n of size d × l for i ← 1 to n do D d,i ← 0 d×l ; D (d,i) L i ← 1; A 1 ← A; for k ← 1 to d -1 do A k+1 ← A k A ; for i ← 1 to n do for j ← 1 to n do D (d,i) kl+L j ← D (d,i) kl+L j + A (k+1) i,j > 0 ; return (D d,i ) 1≤i≤n ; 2 1 3 4 5 2 1 2 3 1                 L = 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0                 A = 1 0 1 1 0 0 3 1 1 1 1 1 2 1 1 1 1 1 3 0 0 1 1 0 1                 A 2 = 0 3 1 1 1 3 2 4 5 1 1 4 2 4 1 1 5 4 2 3 1 1 1 3 0                 A 3 = 1 0 0 0 2 1      D 4,2 = = V 0,2 = V 1,2 = V 2,2 = V 3,2
Figure 5.4: Generating the descriptor D 4,2 of depth 4 for node 2 of a graph with 5 nodes and 3 different labels (red has index "1", green has "2" and blue "3").

Improving the descriptor

As mentioned in [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF], different exploration strategies can be followed when producing random walks, to make the limited number of walks more descriptive. These include the exclusion of duplicate walks or forbidding back-and-forth motions between two nodes. While our approach is not limited by a sample size from a random distribution of walks, these strategies can be employed to fix some issues with our basic descriptor, by altering the framed line in Algorithm 4.

For instance, by using A k i,j to count the number of walks of depth k + 1 between i and j, we include the walks that involve repeated moves to reach the desired depth. In practice, this means that if d is divisible by x, every cycle of length x starting from i will be tallied in D (d,i) km+L i , making the (V i,k ) k≥1 histograms more correlated. To avoid this correlation issue, we define a series of "no-return" adjacency matrices B (k) whose elements (i, j) give the number of walks of depth k + 1 between i and j that do not pass through the same edge twice. We find for depths 2 and 3 that:

B (1) i,j = A i,j , and B (2)
i,j = A (2) i,j if i = j 0 otherwise. (5.1)
For depths k +1 greater than 2, the computation of B (k+1) is not trivial but its values can be approximated -without exhaustively exploring the graph-using the cardinality of the following sets:

B = p 1 ...p k (i 1 → p 1 2 → . . . k → p k k+1 → j), (5.2)
L = p 1 ...p k (i → p 1 1 → . . . k-1 → p k k → j), (5.3)
R = p 1 ...p k (i 1 → p 1 2 → . . . k → p k → j), (5.4)
C = p 1 ...p k (i → p 1 1 → . . . k-1 → p k → j), (5.5)
D = p 1 ...p k (i 1 → p 1 2 → . . . k-1 → p k 1 → j), (5.6)
E = k-1 c=1 k-1 d=1 p 1 ...p k (i c → p 1 1 → . . . k-1 → p k d → j), (5.7)
where (i → p 1 → . . . → p k → j) is the set of walks of depth k + 2 from i to j passing through nodes p 1 . . . p k and numbered arrows denote unique edges in the walk. Since our graphs are simple, these particular sets contain either 0 or 1 walk. We find that:

L ∩ R = B ∪ D, B ∩ D = ∅, (5.8)
C = L ∪ R ∪ E, (L ∪ R) ∩ E = ∅, (5.9
)

|B| = |L ∩ R| -|D| = |L| + |R| -|C| -|D| + |E|.
(5.10)

Therefore:

B (k+1) = AB (k) + B (k) A -AB (k-1) A -|D| + |E|.
(5.11)

Using equations (5.1) and (5.11) allows us to estimate B (k+1) through recursion for any value of k. However, since we use B in a similar fashion as A in Algorithm 4, the only information we require is whether or not its elements are positive.

If we consider A as a matrix of boolean values rather than integers, and the scalar product and sum as logical and and or in the matrix multiplication (or use the Roy-Warshall algorithm [START_REF] Roy | Transitivité et connexité[END_REF]), we notice that the powers of A will give the same information necessary to Algorithm 4. This not only speeds up the calculation of A k but also alleviates any issue of overflowing for large values of k.

Finally, we need to account for the homogenization of the A k matrices for high values of k, since they are eventually filled with true except for the rows and columns of orphan nodes. To achieve this we simply divide the values added to V k,i by k -1 when k > 1. This results in closer neighbours having more weight during the matching and also mitigates the effect of the increasing inaccuracies in the estimation of B (k) for large values of k. The validity of our estimation of B (k) can nonetheless be tested for the smaller values, as the correct matrix can be constructed from exhaustive exploration of the graph rather than matrix multiplication. This exploration process is similar to the one used to create the walk histograms H d at a depth d but the results are stored in the smaller adjacency descriptors D d , and we keep track of the edges already visited as to not reuse them in a given walk.

We will refer to this "exact" but computationally expensive version of the "no-return" adjacency matrix as C (k) . For simplicity, we will also refer to the adjacency descriptors generated with weights as

A (k) w , B (k) w and C (k)
w , even if the matrices themselves are not weighted, but rather their contribution to the descriptors (it is the (V i,k ) that are divided by k-1, not the A (k) , B (k) or C (k) ). The effect these improvements have on the adjacency descriptors is illustrated in Figure 5.5 which shows the same small graph example as in Figure 5.5. The resulting descriptors can then be compared using a normalized dot product.

                L = 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0                 B (1) = 0 0 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0                 B (2) = 0 0 1 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 1 1 1 0 0                 B (3) = 1 0 0 0 2 1 1 0.5 0.5 0.67 0.67 0.33                                                     D 4,2 = Figure 5
.5: Generating the improved descriptor D 4,2 (red has index "1", green has "2" and blue "3"). Changes in the adjacency matrices introduced by a "no-return" exploration strategy and descriptor values affected by depth-wise weighting are shown in red.

Comparison with the walk histogram

Our adjacency descriptor D d,i at depth d for node i can be seen as a compressed version of the walk histogram H d,i from [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF]. For each i, V d-1,i corresponds to the merging of the bins of (H d,i ) into bins of the label of the walk's last step, effectively reducing a histogram of size l d to a size of l. The descriptiveness of H d,i lost in this reduction, is regained through the V k,i with 0 ≥ k < d -1. While D 0,i and H 0,i are identical, their sizes grow linearly and exponentially, respectively, with regards to the depth, making a fair comparison of their effectiveness difficult since we have more granular control over the size of the adjacency descriptor. In order to produce results for more values of the descriptors' sizes for the walk histogram, without resorting to interpolation, we added a "merging" parameter m to its implementation, which reduces the number of histogram bins by merging labels on the last step.

Given a value of m that is a divisor of l, the last step of a walk is recorded as one of l/m "hyper-labels" -groupings of m labels. This results in a descriptor size s H (l, d, m) of l d /m. We note that changing the value of m for any given depth d does not greatly affect the complexity of the exploration algorithm, only the size of the histogram in which the results are stored.

Comparing the two approaches will determine if the trading of the descriptor's precision at a given depth for a lighter descriptor which explores the neighbourhood further is worthwhile. We describe our experimentations in the following section.

Experiments

We are looking to evaluate the performance of our novel node descriptor for the task of graph matching in an indoor environment with a high diversity of objects. The results of the graph matching are then used for the registration of two instances of the same scene captured with different world coordinate systems. It is the measure of the quality of the registration that ultimately allows us to compare different node descriptors, as the parts of the pipeline following descriptor generation remain unchanged (see Figure 5.2).

We are also checking if the new graph extractor using SNs gives as good results for the registration task as the original LN-based one, while also providing a representation that gives a better object-level understanding of the scene structure. The latter can be evaluated by measuring the performance of the extractors for clustering the 3D points extracted from the images that represent the same object into the same node in the graph.

Our code to generate the adjacency descriptors and SN-based graphs from the Scan-Net [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] and ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF] datasets, as well as optimized code to generate the walk histograms and LN-based graphs from [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] is made available here: https://github.com/InterDigitalInc/GraphBasedSceneRegistration

Datasets

To test our registration algorithm in semantically rich indoor scenes, we use the ScanNet dataset [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF], which contains 1513 models of scenes along with the localised RGB-D sequences used to generate them. The dataset includes semantically segmented versions of the models and images, convertible to the 40 labels of the NYU Depth dataset v2 [START_REF] Silberman | Indoor segmentation and support inference from rgbd images[END_REF] (as seen in Figure 5.1). Finally, the dataset also provides instance-segmented image sequences, which can be used to evaluate our graph extractors clustering ability. We also use the ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF] dataset to check our method's robustness to changes, namely: "new", "missing", "replaced", or "rotated" objects. This dataset contains 10 simulated photo-realistic warehouses scenes, which are explored twice by a virtual drone before and after changes occur (for a total of 40 sequences, not accounting for those with added visual disturbances). Similarly to ScanNet, localised RGB-D and label maps are included.

ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] contains 707 unique scenes, but many have been scanned and added multiple times in the dataset in order to reach the 1513 count. Those scenes with several instances can be used to perform registration in pairs, and Table 5.2 describes the dataset's composition with regards to instance pairs. Given that one can make x 2 pairs out of a scene with x instances, ScanNet's contribution to our registration dataset is of maximum size 1194. For each of these instances, the scene is represented by its semantically segmented RGB sequence, its depth map sequence with accompanying camera poses, as well as the camera's intrinsic matrix.

For each ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF] scene, the 2 scans before changes occur are referred to as Ref , and the 2 scans after as Query. Each of the 2 Ref scans can be compared to is corresponding Query scan, making for a total of 20 additional instance pairs for our registration dataset.

Preparing the ScanNet data

In order to use our pipeline on ScanNet's subset of interest, we need to find the ground truth for the alignment of any two instances of the same scene. The original dataset does not include such information but has for each model an alignTransformMatrix which permits the user to transform the scene's coordinates such that the origin is in the middle of the room's floor, and the walls are aligned with the X and Y axes (the floor's normal is already aligned with Z).

Assuming that two instances of the same scene showcase the same portions of the world, they should share the same room center. If we apply each alignTransformMatrix to their corresponding 3D models, the two instances should be aligned or be rotated around the Z axis by π 2 , π or 3π 2 , since the walls are aligned with X and Y . In order to check which of the 4 rotations (including the identity) will result in the alignment of the two instances, we choose a pose P from one of the instances and render a reference image I ref using the corresponding semantically segmented model M ref . We then convert this pose into the world coordinates of the other instance using the two matrices and a rotation matrix R θ (with θ being one of the 4 possible angles of rotation) to render an image I from the other model M. As I and I ref are segmentation maps (and not RGB images from a camera) we can count exactly how many of their pixels values are identical, and use the percentage of identical pixels as a similarity metric. We also assume that unlabelled objects (which appear as black pixels) are different from on instance to the other -they do not count as identical pixels-so that we only rely on known objects for similarity evaluation. If I and I ref are similar enough, we assume the rotation being tested is the correct one, otherwise we try the other rotations and then move on to another pose. The exact procedure to determine the correct orientation is described in Algorithm 5 and illustrated in Figure 5.6 (where we use a similarity metric between 0 and 1 rather than a percentage).

Between two instances, the dissimilarity between I and I ref when the rotation is correct can come from a translation error (the rooms have different centres) or a different semantic segmentation of the content. For this reason -and because of the unlabelled areas in the scenes-we cannot use a similarity threshold of 100% identical pixels in the images. Empirically, we found that using an similarity threshold of 80% would result in 450 instance pairs with a sufficiently reliable ground truth. 5 pairs were manually removed for having very different centres despite having cleared the threshold thanks to their lack of semantic variation. Contrary to ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF], in ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF] the matching Ref and Query sequences are already aligned, meaning that the registration ground truth is an identity matrix I 4 . However, we found that the provided trajectory.txt files do not match the virtual camera trajectories used in the images sequences, requiring additional preparation of the dataset before it can be used.

For the Query sequences with over 1000 frames, the inconsistencies in the trajectory files are caused by a sorting error, likely occurring during the merging of the individual files for each frame. This was solved by recreating them from the individual pose files provided in the pose folder with a Python script that would order them by filename. For the Ref sequences, the trajectory files do not contain the correct number of poses, and cannot be simply recreated due to the absence of a pose folder. Instead, they have to be extrapolated from the "raw" data shipped with the dataset.

Indeed, each Ref scan contains the aforementioned RGB, depth and label map sequences, as well as a raw folder containing additional RGB and depth map sequences. The raw sequences do not have the same number of frames as the "final" sequences, and are accompanied by a poses.g2o file which gives positional data for the virtual drone at certain keyframes. Those keyframes are themselves a subset of the raw frames and their poses were directly written into the trajectory.txt file, despite them not matching the frames in the final sequences. Finally, since the raw data does not include label maps, the keyframes cannot be used as input to the registration pipeline, making the generation of a new trajectory.txt file for the final data mandatory.

To generate the final poses, we notice that the final sequences follow the same trajectory as the raw sequences, but with different sampling (i.e., frames were not generated at the same times). With the exception of the warehouses scenes "2" and "4", there are always more raw frames than final ones. We therefore use a 3-step process, which we will describe in detail in the following paragraphs, based on the comparison of the raw and final depth maps:

1. Match each final depth map to a raw depth map, while preserving the sequence order, 2. Copy the poses for every matched raw frame that is a keyframe in the poses.g2o file, 3. Interpolate the missing poses for the matched raw frames using the closest known poses.

In to order to match the frames, we sequentially go through each depth map of the final sequence and find the most similar one in the raw sequence according pixel-wise L2 distance. The raw pixel values must be divided by 200 to match the final scaleconverting them to metric measurements, as we found experimentally. To preserve the sequence order, the search for a match is restricted to a selection of frames around the previous match. We define the reduction ratio r from the raw to the final sequences, as the number of frames of the former divided by the number of frames of the latter. We search for the next matching frame from 1r before the previous match to 6r after. We use that search window as it can successfully find matching frames for every scene save "2" and "4", and a larger window would result in a longer computation time. This approach does not work for "2" and "4" because of the too small r values, and both scenes have to be ignored due to their limited numbers of raw frames, which lead to issues with the interpolation step.

Once the keyframe poses are copied for the relevant raw frames, the missing ones must be interpolated from other -copied or not-keyframes. This process is illustrated in Figure 5.7. Poses in ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF] are given as a 3D vector t for translation and a quaternion q for the rotation, and keyframes are rarely separated by more than 10 frames. Therefore for a given raw frame, the interpolation is simply performed between the closest anterior and posterior keyframes poses: we use linear interpolation (Lerp) for the translation and spherical linear interpolation (Slerp) for the rotation [START_REF] Shoemake | Animating rotation with quaternion curves[END_REF]. This assumes a constant speed between consecutive keyframes, and the interpolation parameter is simply given by the difference between the current raw frame index and the previous keyframe index, over the difference between the two consecutive keyframes indexes (as seen in Figure 5.7).

Raw frames

Final frames

t 1 q 1 t 2 q 2 t 3 q 3 t 4 q 4
Lerp(t 1 , t 2 , 1/2) Slerp(q 1 , q 2 , 1/2) Lerp(t 3 , t 4 , 1/3) Slerp(q 3 , q 4 , 1/3) 2 frames 2 frames 1 frame 2 frames In our implementation, the 3 steps are performed in parallel thanks to the sequential matching. This process allowed us to add 16 instance pairs to register to our dataset.

Error metrics for model alignment

As mentioned in Section 5.2, as well as using the translation and rotation errors between the estimated transformation and the ground truth, we use the RMSD E RM S to provide a unique metric to compare the methods.

Firstly, if t and R are the estimated translation vector and rotation matrix and t GT and R GT the corresponding ground truth, then E t and E R are defined as:

E t = ||t -t GT || 2 , E R = ||R -1 GT R -I|| F , (5.12)
where ||.|| 2 and ||.|| F are the Euclidean norms for vectors (L 2 ) and matrices (Frobenius) respectively. Secondly, we call T and T GT the transformation matrices associated with those translation vectors and rotation matrices:

T = R t 0 0 0 1 , T GT = R GT t GT 0 0 0 1 . (5.13)
Following the approach given in [START_REF] Jenkinson | Measuring transformation error by rms deviation[END_REF], we formally integrate the transformation error over a volume V modelling the reference. The offset introduced by the error between an estimated transformation T and the ground truth T GT for any given point p in homogeneous coordinates is:

∆p = M p, M = T -1 GT T -I 4 .
(5.14)

Therefore the RMSD over the volume V is given by:

E RM S = V |∆p| 2 dp V dp , |∆p| 2 = p T M T M p.
(5.15)

[90] then calculates the integrals in (5.15) by assuming that V is a sphere with its radius as a parameter and working in spherical coordinates. In our dataset of indoor rooms, most of the scenes can be reasonably modelled as their 3D rectangular bounding boxes, with 3 dimensions in a Cartesian space (width, length and height):

V = [-X, X] × [-Y, Y ] × [-Z, Z], (5.16)
For ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] scenes, alignTransformMatrix can be used to align the bounding box's axes to the world's axes. By representing the scene in this way and integrating the distance error over every point inside the volume, we define a metric that is independent from the contents of the room.

In order to compare the estimated transform to the ground truth for our indoor datasets, we only need to measure the dimensions of the scene P = (X, Y, Z) and find its center, using the 3D models provided in ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] and ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF]. If we first assume that the box is centered on the origin, once T is estimated, we can use T GTprovided by the method in Subsection 5.4.1.1 for ScanNet-to calculate A, b (submatrices of M ) and D defined as:

M = A b 0 0 0 0 , D = diag(A T A) = -2   A 1,1 0 0 0 A 2,2 0 0 0 A 3,3   (5.17)
then with v, corresponding to p in non-homogeneous coordinates:

|∆p| 2 = v T A T Av + 2b T Av + b T b. (5.18) and V b T b dp = b T b V dp, V 2b T Av dp = 0. (5.19)
and finally

V v T A T Av dp = 1 3 P T DP V dp. (5.20)
Therefore the equation for the RMSD for a centered box is:

E RM S = b T b + 1 3 P T DP . (5.21)
As the origin of our aligned models is actually set to the center of the scene's floor, we need to move the box to a new center v c by updating M :

M = M M c , M c = I 3 v c 0 0 0 1 , (5.22)
then A = A and b = b + Av c , therefore:

E RM S = (b + Av c ) T (b + Av c ) + 1 3 P T DP . (5.23)
An illustration of the errors metrics for a rectangle is shown in Figure 5.8. In this 2D example, the relationship between the RMSD and the translation and rotation errors is made apparent, as well as the impact of the studied box's dimensions. We also note that E t does not directly appear in the 3D formula for the RMSD Equation 5.23 because the translation error is measured at the centre of the room's floor -the origin of the coordinate system of an aligned ScanNet model-whereas the RMSD uses the 3D center v c of the model. The vertical offset between these two definitions of the room's centre is not present in the 2D case from and the rotation error is

E R = 2 √ 1 -cosθ. Right: the RMSD is E RM S = E 2 t + 1 6 E 2 R (X 2 + Y 2 ).

Results

Since our dataset includes indoor scenes with a smaller scale than the outdoor scenes from the SYNTHIA [START_REF] Ros | The synthia dataset: A large collection of synthetic images for semantic segmentation of urban scenes[END_REF] or KITTI [START_REF] Geiger | Are we ready for autonomous driving? the kitti vision benchmark suite[END_REF] datasets used in [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF], we reduce the node fusion threshold T object from Subsection 5.3.1.2 from 10 meters [START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF] to 1 meter.

Graph extraction

In order to compare the LN-based [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] and SN-based graph extractors' abilities to preserve the object instance segmentation of the scenes, we use the Adjusted Rand Index (ARI) [START_REF] Hubert | Comparing partitions[END_REF]. The ARI is designed to compare the similarity between two clusterings of data, and has been used in previous work for evaluating point cloud segmentation [START_REF] Chen | Lrgnet: Learnable region growing for classagnostic point cloud segmentation[END_REF].

In our case we are clustering the 3D points extracted from the regions in the label maps.

We will be comparing to which object instance they belong in the ground truth, and to which node in the graph they are associated during extraction. The reference clustering is simply obtained by looking up the index of each region in the instance segmentation maps provided in ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF], as they are aligned with the label maps. During extraction, as explained in Subsection 5.3.2, the 3D points are converted into nodes for the graphs:

Using LNs, only a single 3D point is used to produce a new node, while the "duplicates" are ignored.

Using SNs, all points identified as duplicates of each other are bundled into a single node.

Therefore the estimated clustering -from graph extraction-can be inferred from which nodes are identified as duplicates of each other. For SNs this is directly detailed by the final graph structure, and for LNs we can keep track of the ignored nodes during the extraction to monitor the underlying clustering.

The ARI results over the ScanNet dataset [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] are detailed in Table 5.3. An ARI of 1 indicates identical clusterings -indices' permutations notwithstanding, which are indeed irrelevant in our case-while an ARI of 0 occurs for independent clusterings. Additionally, the ARI may be negative if the estimated clustering is "worse than random" (the clusterings are not independent). In this light, our SN-based extractor better preserves the 3D point clustering inferred from the instance segmentation maps. In practice this means that objects in the scene are less likely to be fragmented or merged with one another into nodes during graph extraction.

We also provide in the table the results for a Ground Truth-based (GT) extractor, which directly uses the instance segmentation maps to create the SN, therefore getting an ARI of 1. This shows that, on average, while the scenes from ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] contain 31 objects, the SN extractor recovers 19 and the LN extractor 50: meaning that the SN extractor tends to merge objects of the same label into a single node. The table shows a slight discrepancy in the number of points used between the SN and GT extractors, which is due to the filtering of nodes which have less than T super = 10 points (see Subsection 5.3.2).

Also in Table 5.3 are the number of nodes created and 3D points used on average per graph for ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF], for which we do not have the instance segmentation GT (therefore no ARI results). For LNs, the number of points is the same as the nodes since only one point is required to the computation of spatial attributes. For SNs, the number of points per node is 652.89 on average for ScanNet and 120.50 for ChangeSim, assuming that all scenes are weighted the same -which differ from the values obtained by dividing the number of points by the number of nodes, as those give larger weight to scenes with more nodes. Therefore a lot more memory is required when generating the spatial attributes for SNs. However, using SNs significantly reduces the number of nodes in the graph, which reduces the number descriptors to generate. Assuming the optimal descriptors H 3 described by [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] with the 40 NYU labels [START_REF] Silberman | Indoor segmentation and support inference from rgbd images[END_REF]: each descriptor is of size 64000, while each point only stores 3 coordinates. In conclusion, the SN extractor produces graphs that more closely match the scene instance segmentation, and the total memory cost must be evaluated by taking into account the descriptor types and depths used to achieve the desired quality of registration.

Variants of the adjacency descriptor

In this section, we evaluate which of the modifications introduced in Subsection 5.3.3.2 improve registration results. The ScanNet dataset [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] is processed using 4 variants of the adjacency descriptor with depth d (equivalent to walks of d-1 steps) going from 2 to 19 and then from 20 to 160 with increments of 20. The results are presented in Figure 5.9: the variant can either use the powers of the standard (Boolean) adjacency matrix (A k ) or the "no return" (Boolean) matrices (B (k) ), and it can either have constant weights or be inversely proportional to the depth (indicated by the w index).

As well as the 4 main variants, we also plot the results for depths 2 to 4 using the non-approximated "no return" matrices (C (k) ) and (C (k) w ) to validate our approximation. When comparing the variants, depths 1 and 2 result in the same descriptors, and we do not plot the d = 1 case, for which the node descriptor is simply its label. The registration error is plotted against the descriptors' size (using a logarithmic scale). We use the median over the dataset rather than the arithmetic mean in order to not let failed registrations influence the results too greatly, as the translation error and RMSD can get arbitrarily large due to numerical errors. We also avoid using the geometric or harmonic means for this reason: if an error metric for a single instance pair gets too close to 0, it nullifies the geometric and harmonic means over the dataset for that metric.

When using LNs, (B

w ) consistently gives better results than the other variants, especially after d = 4. All variants also seem to stabilize for higher values of d except (B (k) ). This is likely due to the compounding inaccuracies introduced by our estimation of (B (k) ), which is however accurate to (C (k) ) for the depths it was computed at.

When using SNs, better results are obtained at low depths, after which the registration deteriorates then stabilizes (except for (B (k) )). This is likely due to the smaller size of the SN-graphs. The degradation is more pronounced for (A (k) ), as the same paths are likely being taken repeatedly when extending the descriptors, giving the relevant information less weight during matching. Despite this, the results are generally better using SNs -even at less than optimal depths-and (B (k) w ) outperforms the other variants using either graph extractor.

Experiments

d × l RMSD (meters) A k A k w B (k) B (k) w C (k) C (k) w 10
A k A k w B (k) B (k) w C (k) C (k) w 10
A k A k w B (k) B (k) w C (k) C (k) w 10
A k A k w B (k) B (k) w C (k) C (k) w Figure 5
.9: Median errors metrics for ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] vs. d × l for 6 variants of the adjacency descriptor, starting at d = 2. Left: using LNs, right: using SNs. Lower is better.

Adjacency descriptor vs walk histogram

The weighted "no return" variant (B

w ) of our descriptor is compared to the walk histogram descriptor [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] (H d ) on the datasets. We run the pipeline for (H d ) for depths 1 to 4, and for d > 1 we use a merging m of 20, 10, 8, 5, 4, 2 or 1, all divisors of the number of classes l = 40.

We again calculate the registration error against the descriptor size: s D (l, d) for our descriptor and s H (l, d, m) for the walk histogram. The results for ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] are presented in Figure 5.10, and for ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF] in Figure 5.11.

Each method is evaluated with and without RANSAC filtering of the outliers, and we can see that the results for both methods are significantly improved when RANSAC is used, underlying the shortcomings of the point cloud extraction algorithm as mentioned in Subsection 5.3.1.5. The exception is ChangeSim using LNs, where (B (k) w ) manages to get as good of results with or without RANSAC filtering (see Figure 5.11 top row). However, studying the methods without filtering will be our focus, since their performance is more indicative of the quality of the graph matching process. Indeed, if the graphs are to be used for AR purposes beyond localisation as previously pointed out, we should maximize the number of correct matches.

Both the adjacency and walk histogram descriptors are identical at d = 1 ("node label" descriptor) but the adjacency descriptor quickly improves registration as d increases. At d = 2 both methods provide similar results but the adjacency descriptor is much lighter. At s(l, d, m) = 1600, the walk histogram explores only a neighbourhood of d = 2 while the adjacency descriptor explores d = 40, with significant RMSD reduction in all configurations except that of ScanNet with SNs (see Figure 5.10 right column).

As seen in the previous section, this is likely due to the small size of these graphs, since increasing the depth improves results for larger scenes (ChangeSim) or bigger graphs (LNs). Moreover, for ScanNet the results are still better using SNs at d = 2 rather than LNs at any depth (see Figure 5.10 left column). The performance of H 2 and its corresponding (B

w ) in depth (d = 2) and size (d = 40) over the whole dataset are detailed in Figure 5.12 for ScanNet and in Figure 5.13 for ChangeSim. We also provide results for H 3 as it was the optimal descriptor in [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF] in both figures, and the node label descriptor (d = 1) for ScanNet.

In Figure 5.12, we plot on the y-axis the percentage of successfully registered scene pairs according an error metric threshold on the x-axis. The 2 or 3 vertical dotted lines show on the x-axis when 90% of successful registrations is reached for the plain curves (not dashed) of the matching color. For ScanNet, 90% success is always reached first with (B (k) w ) at d = 40, then with H 2 , then with the node label. Figure 5.12 also shows that (B (k) w ) at d = 2 and H 2 give the same results despite the much smaller size of the former. Figure 5.12 and Figure 5.14 (left side) also show that after a fast growth, the SN curves (right column in Figure 5.12) do not near 100% by the time the LN curves do (left column in Figure 5.12): one is not consistently producing better results than the other on all scenes, but their performances are close on 90% of them.

In Figure 5.13, we plot the error metrics over the whole ChangeSim dataset, with each grouping of histogram columns representing the performance on one of the 16 instance pairs. It shows that (B Overall, for the walk histogram descriptor [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF], increasing the depth eventually degrades results despite the larger descriptor size. Since it should not have the same issue of homogenization with increased depth as our non-weighted variant, it is likely that the scarcity of unique walks in the graphs compared to the size of the histogram makes the calculation of the normalized dot products less reliable. [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] vs. an RMSD threshold for success, using the node's label and the best adjacency descriptor variant with LNs and SNs. Right: RMSD for each ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF] instance using the best adjacency descriptor variant with LNs and SNs.

Generation and matching times

The descriptor generation and matching time is also measured for the two descriptors and displayed in Figure 5.15. (B

w ) consistently shows lower RMSD than H d at equivalent times. The different is particularly noticeable for d = 2, as both descriptors contain the same information but said information is more quickly encoded and compared using the adjacency histograms. Figure 5.15 also shows that the speed gain from using the "plain" adjacency descriptor (A (k) ) are not significant enough to justify its use. As a conclusion, we note that descriptor generation lasts less than a millisecond for graphs containing hundreds of nodes using (B (k) w ), on a virtual machine with 16GB of RAM and four 2.60GHz processors. The matching step is also done in less than a millisecond on average on ScanNet, at most depths.

Impact of the depth

In the previous sections we have shown that at a given depth d or for the same descriptor size, our new descriptor provides similar or better results than H d . In addition, this compressed representation allows for a deeper exploration when constructing the descriptor. We can check the benefits of the deeper search by plotting how many instance pairs in the dataset are best registered at a given depth. As previously seen for ScanNet, increasing the depth over d = 2 benefits the registrations when using LNs but not SNs. This is shown in the depth histograms of Figure 5.16, where the dataset was processed using H d from depth 1 to 4 (the maximum possible depth on our hardware), and (B (k) w ) from depth 1 to 20. Once again using the node's label (d = 1) for the graph matching does not generally yield the best results, but it is more effective using SNs (right) than LNs (left). However, the optimal depth using (B (k) w ) is shown to be 2 for SN graphs, with much less positive results after d = 5 when compared to LN graphs. This confirms that a deep exploration of the graphs is not required when using the smaller SN graphs produced for ScanNet scenes.

In contrast, Figure 5.17 shows that there are advantages to deeper graph exploration when confronted with bigger scenes with more duplicate objects as with the warehouses of ChangeSim. A significant number of scenes reach their best result for d = 20 for (B

w ), and could benefit from further exploration, which is not possible using the walk histograms.

To conclude, the proposed adjacency descriptors offer more flexibility in allowing deeper exploration of large scenes when necessary. This can be done without prohibitively large execution time, memory cost, or without degrading the results as with the walk histograms, as the use of depth-wise weighting leads the error to stabilize rather than increase for large depth values.

Impact of graph quality

As mentioned in Subsection 5.4.3.1, to assess the quality of the graph extraction process, we also generated Ground-Truth (GT) graphs, that are based on the instance segmentation maps of ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] (as shown in Figure 5.18) rather than our object delimitation process (see Subsection 5.3.2). In Figure 5.19 and Figure 5.20, we show how the descriptors perform under those "ideal" conditions for graph extraction.

The RMSD curves (left of Figure 5.19) show a slight improvement of the registration over using the SN graphs (about 3% at the optimal depth), but notably, using GT graphs fixes the issue of quality degradation with increasing depths. Indeed, with the GT graphs, d = 2 does not account for more than 40% of the best registration results when using (B However, the performance is still the best using SN graphs when only the node label is used for matching (right of Figure 5.20). The most likely explanation is the reduced number of nodes in the graphs. In Subsection 5.4.3.1, we showed that GT graphs contained 31 nodes on average, while SN graphs tend to merge objects, resulting in a 19 nodes average. Reducing the graph's size reduces ambiguity when matching nodes solely on their label, seeing as only nodes of the same label are incorrectly merged using the SN extractor. To test the robustness of our registration method to a lowering of graph quality, we use an off-the-shelf image segmentation tool that has been trained on the 40 NYU labels [START_REF] Silberman | Indoor segmentation and support inference from rgbd images[END_REF]. We decided to use 2021's ESANet [START_REF] Seichter | Efficient RGB-D semantic segmentation for indoor scene analysis[END_REF], which we ran on the RGB images sequences provided in ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] to produce new label maps, replacing the accurate maps given by ScanNet we otherwise use (see Subsection 5.3.1.1). This approach makes the labelled region-based graph creation less reliable in 2D (as shown in Figure 5.21), but also makes the temporal segmentation of the scene inconsistent, leading to ambiguous 3D segmentation.

In practice, the images are segmented into more regions than the ground truth, which causes the average graph size to increase from 19 to 32 for SNs and from 50 to 124 for LNs (see Table 5.3). It also greatly affects the quality of the object instance segmentation, as the ARI drops to 0.133 for SNs and 0.179 for LNs. As for the registration task, the results using the ESANet label maps are presented in Figure 5.22 and Figure 5.23.

In Figure 5.22, we only plot the walk histogram descriptor's performance for m = 1 (no merging). Once again, it is outperformed by (B (k) w ) for most depths, and the performance of the adjacency descriptor improves with increased depth whether SNs or LNs are used, as the graph size is larger using the ESANet segmentation. However, in Figure 5.22 and Figure 5.23, SNs are outperformed by LNs for the localisation task when higher depth values are used for the descriptors. In Figure 5.23, it is especially visible that using SNs benefits the node label descriptor (d = 1) -as LNs w ). In conclusion, the quality of the localisation is correlated to the closeness of the graph representation with the actual semantic contents of the scene. Using the instance segmentation ground truth improves the results when descriptors encode a neighbourhood of depth 2 or more around each node. Conversely, not using the 2D label ground truth degrades the results but 90% of instance pairs are still registered within a RMSD of 0.80 meters if (B (k) w ) descriptors are used in conjunction with LNs at depth 40 (see left of Figure 5.23). We therefore note that LNs seem more robust to a degradation of the input labels, which makes their use over SNs in the localisation task still relevant when the scene contents are difficult to identify. w ). Left: using LNs, right: using SNs.

Conclusion

In this chapter, we presented a new graph node descriptor based on the adjacency matrix of a scene graph for indoor scenes. We evaluated its descriptive powers in the graph matching process as part of a pipeline for indoor scene registration. Compared to a similar state-of-the-art method [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF], we found that it produces a more precise alignment of the scene models. We also demonstrated the computing efficiency of our proposed descriptor in semantically rich scenes. Indeed, the size of the descriptor necessary to encode the many different object labels for large neighbourhoods is greatly reduced from existing works [START_REF] Guo | Semantic histogram based graph matching for real-time multi-robot global localization in large scale environment[END_REF][START_REF] Gawel | X-view: Graph-based semantic multi-view localization[END_REF], while improving its computing time. The ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] and ChangeSim [START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF] datasets were processed in order to be usable in our scene registration task: we generated the registration ground truth for ScanNet, and the camera poses ground truth for ChangeSim. The registration quality was evaluated using a metric for transformation error that we adapted from an earlier RMSD metric [START_REF] Jenkinson | Measuring transformation error by rms deviation[END_REF] to fit our data's profile.

We also experimented with an alternative graph representation and extraction method, which is much more representative of the object-level understanding of the scene required for tasks beyond localisation. This Super Node-based representation performed equivalently or better than the previous on this task, while the evaluation of its scene representation quality was quantitatively evaluated using a relevant clustering metric: the Adjusted Rand Index [START_REF] Hubert | Comparing partitions[END_REF].

Given a pair of scene graphs, preliminary registration can be performed rapidly and reliably using the proposed graph descriptor and graph representation. These methods also offer more flexibility to different types of scenes thanks to their slower scaling with the scene's dimensions, semantic density, or observation radius required to reliably identify objects with to their surroundings.

Chapter 6 Conclusion and Future Work

In this thesis, we introduced novel methods to tackle the problem of geometric Change Detection for Mixed Reality experiences. Said CD was performed between two states of a real-world scene, be it through photometric and geometric observations or semantic analysis of the scene's contents. We defined MR as photo-realistic Augmented Reality, and found that "behavioural realism" would also need to be achieved to preserve its immersive quality. Behavioural realism involves the recreation of believable physical interactions of the virtual contents with the real world, which requires semantic information about the scene beyond its geometry (the real objects' types, materials, relationships etc.). This work was undertaken in order to provide a means of maintaining a model of the real environment, which would include the necessary information to achieve the desired level of realism for MR applications.The use of CD to construct said model was motivated by the need to provide a fast and lightweight solution to the maintenance problem: gradually applying updates to the model to mirror reality. Indeed, the widely available AR devices are currently not equipped with the necessary scanning or computing resources to recreate such a model without a prior with a high enough fidelity, or within a time acceptable to the AR user. Additionally, devices such as AR glasses and smartphones can only partially observe the scene -due to sensor limitations or occlusions-making the use of a reference scene model mandatory for the experience to be able to begin as the application is launched.

We learned in our study of the state-of-the-art (Chapter 2) in the field of CD, that most existing methods are too demanding for the hardware of mainstream AR devices, or are not able to provide 3D geometric results in real-time as required by most applications in this field. Nevertheless, some of the works for robotics -in autonomous navigation and interaction for instance-do provide approaches that aim to solve the problem of scene understanding at interactive time, which we have been able to exploit to fit our purposes [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF][START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF][START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF].

In Chapter 3, we acknowledged the difference in nature between the data required for an MR application, and that which can be acquired using an AR device, by implementing a CD method that can compare scene states represented by said heterogeneous data. We made the hypothesis of a "semi-static" environment: an environment where changes occur between AR sessions but not while it is observed during said sessions. Consequently, changes could be studied by comparing two static models of this environment: one for its past state -the "prior" or "reference"-and one for its current state -the "observation" or "query". We chose to represent the past state as an untextured 3D mesh -required for photo-realistic rendering but difficult to capture with the AR device-and the current state as a sequence of images -readily available using a simple camera. In this context, the 3D representation can be updated solely by detecting geometry that was either added or removed between the two scene states. We used our own image reprojection-based method, which corrects the existing bias [START_REF] Qin | 3d change detection at street level using mobile laser scanning point clouds and terrestrial images[END_REF] of similar methods [START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF][START_REF] Taneja | Image based detection of geometric changes in urban environments[END_REF] toward the detection of geometry addition, to the detriment of removal detection.

Following the work in Chapter 3, we noticed that updating the geometry of the scene model would necessitate more precise results than our photo-geometric analysis could provide from an outdated mesh and up-to-date images. Therefore, we concluded in Chapter 4 that an object-level understanding of the scene, and subsequent segmentations of the 3D and 2D data from the scene model, would allow us to better preserve the model's fidelity to the real environment after maintenance. We settled on a semantic Scene Graph representation, where nodes would represent objects in the scene and edges their (spatial) relationships.In such a SG, the attributes of nodes -namely the location and type of object they represent-link semantic labels to the relevant scene geometry and textures. This SG is updated through semantic analysis of the scene, which allows us to better define the "relevancy" of changes -finding which changes affect the MR experience-as well as achieving behavioural realism.

Finally, we introduced a method to match our semantic SGs through the identification of similar nodes in Chapter 5. The purpose of this work was to show how this scene representation could be used for various tasks arising from general AR applications (i.e., not only MR), such as user localisation and virtual content integration based on semantic contents. With the assumption that modern AR devices are now equipped with a LiDAR sensor or stereo cameras -in contrast to Chapter 3-we presented a novel graph generation method from RGB-D sequences. In the same chapter, we also introduced a novel node descriptor that can be used to measure similarity between the objects (SG nodes) extracted from two different RGB-D sequences. Using these proposed methods, two scene states can now be compared and aligned through semantic matching of their graphs, and persistent virtual content can be reliably reintegrated into the scene between AR sessions.

In conclusion, using the new hardware and the reference data hypothesis introduced in Chapter 4, the photo-geometric CD approach from Chapter 3 could be used on an object-segmented mesh, opening up the possibility of fidelity-preserving updates to be made to said mesh. Additionally, with said objects being represented as nodes in a graph of the scene, the registration of the image sequence required for the CD framework from Chapter 3 could be handled by the SG-based method from Chapter 5. As outlined in Chapter 4, when changes are detected in the scene, the removed objects can simply be deleted from the segmented mesh, while displaced objects can have the corresponding mesh vertices match their trajectories. By using an AR device able to capture the RGB-D frames for the SG generation in Chapter 5, we now have access to 3D geometry relevant to the addition of novel objects to the mesh. In effect, a semantically semantic mesh of the scene can be updated using RGB-D observations of its current state thanks to our photo-geometric CD and semantic registration approaches. As such, only semantic CD remains to be solved in order to exhaustively describe the changes with the precision required to preserve the realism of MR experience in changing scenes.

We also found that our work on SGs could potentially be used in conjunction with higher precision scanning utilities as a scene authoring tool from real data, that would record and organise geometric, photometric and semantic information about the scene in our proposed lean and versatile SG representation. Considering this and the previously mentioned registration application, our SG generation method is relevant to both ends of an AR framework: the production and organisation of virtual assets and the analysis of the real environment. As graphs have been used as the translation medium between human instructions and robots' operations in robotics, they can also be used as a standardised interface between the real and virtual components of an AR application. Indeed, the ability to communicate a set of instructions relating to a real (or possibly virtual) scene will improve the behavioural realism of AR agents (useful for MR applications), and generally give them more ways to interact with the scene.

Future work

As previously mentioned, semantic CD would greatly benefit our scene model update framework for MR, yet remains to be addressed. In Chapter 4, starting from the semantic SG model, we outlined an approach to tackling CD for MR applications through the study of 4 problems: CD between two global SGs, CD between a partial query SG and a global reference SG, creation of the query SG guided by the prior knowledge contained in the reference, update of the scene geometry from semantic CD.

The first problem was partially addressed in Chapter 5, as being able to match the nodes of the two graphs is the first step towards tallying their differences. As we tackled the issue of registration through graph matching, we introduced a similarity metric between nodes (or objects) in the scene, which could be used to semantically match nodes whose other attributes (geometric or photometric properties) may differ. In our framework, the final registration step identifies the most geometrically coherent node matches when aligning the scene instances -not every match is required-which makes our approach robust to changes. CD will require the matching algorithm itself to identify "unmatchable" nodes due to changes in the scene impacting the graphs' topologies. This will be evaluated using a graph matching ground truth, rather than a registration one.

Following this, the context of AR would require an approach able to match a user's current limited view of the scene, against the global reference. This perspective can be emulated in our data used in Chapter 5 by simply shortening the image sequences used to simulate the observation of the scene. As outlined in Chapter 4, while SGbased localisation is addressed in the literature, CD will require an understanding of the difference between out-of-view and removed objects. Similar attention should be given to large objects that can only be partially observed at any time, as they can also help to define the boundaries of the AR device field of view. All these added concerns would impose new requirements on the scene model used, as a more thorough understanding of the objects' properties would be required to address them. This raises the question of how these new properties might be updated or checked against the current scene, given our assumed hardware limitations. Mirroring the method described in Chapter 3, semantic change detection and graph updates would be performed using heterogeneous data. Semantic and geometric analysis of the scene would be conducted with the help of the prior, so as to define regions of interest in the current observations and allow the maintenance of all that is stored in the scene model.

Finally, so far we have assumed that our reference was a perfect representation of the scene as far as its "tracked" properties were concerned (the scene, the nodes' attributes, the mesh...) but can this hypothesis hold after multiple updates to the model? If the scene only veered slightly from a stable reference state between AR sessions, updates to the model would not need to be permanent, and the updated version would only exist for that session. However, this hypothesis cannot be made in most real environments, and over time the reference state will differ too greatly from the current observations to be updated from change detection in real-time. Therefore, the scene representation and CD technique must be chosen to preserve the quality of the former over multiple iterations. This is especially true of geometric properties, which are the most difficult to capture with dedicated hardware.

Once the above-mentioned 4 problems have been solved, the resulting scene model will be able to provide the necessary data to MR applications to achieve the desired level of realism. It would then be possible to explore possible extensions to the scene model, which allow for better interactivity between the virtual and the real environments, or with the user. As our scene model was inspired by advancements in the field of robotics, it would likely be an effective translation medium between human and machine perceptions of the environment. More generally, the model is a means to communicate scene information, and while the raw 3D and 2D data may be sizeable, the semantic contents and layout represented by a graph are lightweight. This scene model tailored to monitoring scene changes may be as efficient as transmitting scene updates: the vocabulary of changes can be used to describe modification instructions. Once a scene is understood on a semantic level, the many geometric and photometric changes required to describe its dynamic parts can be effectively summarised as a set of semantic changes.

  Photometric registration

Figure 1 . 1 :

 11 Figure 1.1: Differences in knowledge between VR and AR experiences.Cameras are represented as triangles, scene geometry as rectangles and light sources as circles. In the AR scene, the camera pose needs to be known relative to the real (red) and virtual (green) scenes. Real scene assets also need to be simulated (dashed shapes).

Figure 1 . 2 :

 12 Figure 1.2: Geometric Change Detection for MR. Using an outdated 3D representation of the scene (top-center) causes an unrealistic integration of virtual elements (top-right) into the current scene view (top-left). Detecting changes between the past and current scene states (bottom-center) can allow us to correct this (bottom-right).

  (a) Outdated 3D mesh.(b) Up-to-date scene photograph.

Figure 3 . 1 :

 31 Figure 3.1: Insertions (green) and removals (red) over time.

Figure 3 . 3 :

 33 Figure 3.3: Removed object (i.e. absent from RGB image) is textured by the occluded background (pink) and introduces mild inconsistencies: I i (x) = I j→i (x). Its textured shadow is consistent with reference: I i (x ) = S j→i (x ).

( a )

 a Image Ii (the sky is not in the mesh). (b) Image Ij. (c) Image Ij→i (Ij seen from camera Ci).(d) Textured shadows Sj→i.

Figure 3 . 4 :

 34 Figure 3.4: Reprojecting image I j on image I i (removed objects in red, corresponding occlusions in yellow).

( a )

 a Delta map δj→i. (b) Projected map ∆j→i.

Figure 3 . 5 :

 35 Figure 3.5: Once photo-consistency is evaluated in the occluded parts of the image, the potential changes are located in the foreground.

  (a) ∆i. (b) Detected change regions.

Figure 3 . 6 :

 36 Figure 3.6: Segmentation in regions from point of view i.

( a )

 a Point of view i (detail). (b) Point of view j (detail).

Figure 3 . 7 :

 37 Figure 3.7: Region matching for two points of view. Circles: centroids of the regions, Crosses: reprojected centroids.

Figure 3 . 8 :

 38 Figure 3.8: Left: Scene model without the "removed objects". Right: 3D removal detection: red ellipsoids mark the estimated location and size of changes.

  True positive rate (b) playground-car.

Figure 3 . 9 :

 39 Figure 3.9: ROC curves. Blue points represent different threshold values, the red cross is the automatic threshold.

  (a) Original delta map. (b) Filtered delta map. (c) Final results without filter. (d) Final results with filter.

Figure 3 . 10 :

 310 Figure 3.10: Part of the insertions detection pipeline, without (left) and with (right) filtering of the removals detection results in 2D (top).Filtering reduces false positives in 3D (bottom).

Figure 3 . 11 :

 311 Figure 3.11: Removal detection for container-shelf.

Figure 3 . 12 :

 312 Figure 3.12: Removal detection for container-shelf2.

Figure 3 . 13 :

 313 Figure 3.13: Removal detection for playground-car.

  0 0.05 0.1 0.15 0.2 0.25 0.3 0

Figure 3 . 14 :

 314 Figure 3.14: Removal detection for statue-robot.

Figure 3 . 15 :

 315 Figure 3.15: Removal detection for statue-robot-bad-exp.

  0 0.05 0.1 0.15 0.2 0.25 0

Figure 3 . 16 :

 316 Figure 3.16: Removal detection for statue-robot-bad-temp.

Figure 3 . 17 :

 317 Figure 3.17: Removal detection for statue-robot-temp.

Figure 3 . 18 :

 318 Figure 3.18: Removal detection for toilet-stone.

Figure 3 . 19 :

 319 Figure 3.19: Removal detection for 0000 00+plant.

  0 0.05 0.1 0.15 0.2 0.25 0

Figure 3 . 20 :

 320 Figure 3.20: Removal detection for 0000 01+box.

Figure 3 . 21 :

 321 Figure 3.21: Removal detection for 0000 01-insert+box.

Figure 3 . 22 :

 322 Figure 3.22: Removal detection for 0000 02+statue.

Figure 3 . 23 :

 323 Figure 3.23: Removal detection for 0001 00+dollhouse.

Figure 3 . 24 :

 324 Figure 3.24: Removal detection for 0001 01+table.

Figure 3 . 25 :

 325 Figure 3.25: Removal detection for 0002 00+chair.

Figure 3 . 26 :

 326 Figure 3.26: Removal detection for 0002 01+extinguisher.

Figure 3 . 27 :

 327 Figure 3.27: Removal detection for 0003 00+cat.

Figure 3 . 28 :

 328 Figure 3.28: Removal detection for 0003 01+desklamp.

Figure 3 . 29 :

 329 Figure 3.29: Removal detection for 0004 00+ghost.

Figure 3 . 30 :

 330 Figure 3.30: Removal detection for 0005 00+bucket.

Figure 3 . 31 :

 331 Figure 3.31: Removal detection for 0005 01+pitcher.

Figure 3 . 32 :

 332 Figure 3.32: Removal detection for 0006 00+lamp.

  (a) Reprojection from[START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF], using direct transform. (b) Ours, using inverse transform (Algorithm 1).

Figure 3 . 33 :

 333 Figure 3.33: The reprojection step being performed with different algorithms. The direct transform results in interpolated or missing pixels.

  (a) Reprojection on the CPU (zoom). (b) Reprojection on the GPU (zoom). (c) Insertions delta map on the CPU (zoom). (d) Insertions delta map on the GPU (zoom).

Figure 3 . 34 :

 334 Figure 3.34: Parts of the insertions detection pipeline, as performed on the CPU and the GPU. During reprojection on the CPU, occluded geometry is wrongfully included (red square), and on the delta maps the contours of objects are more likely to produce false positives (purple square).

Figure 3 .

 3 Figure 3.35: The removed object in the foreground is undetected because the object behind it creates inconsistencies in the textured shadows.

  (a) Object detection trained on the LVISv0.5dataset[START_REF] Gupta | LVIS: A dataset for large vocabulary instance segmentation[END_REF].(b) Panoptic segmentation[START_REF] Kirillov | Panoptic segmentation[END_REF] trained on the COCO dataset[START_REF] Lin | Microsoft COCO: common objects in context[END_REF].

Figure 4 . 1 :

 41 Figure 4.1: Object-based semantic image segmentation, limited by the data the networks are trained on.

Figure 5 . 1 :

 51 Figure 5.1:In an AR session, the contents of the scene can be semantically and spatially represented by a scene graph so that virtual objects can behave in a realistic manner. Left: A reference graph captured during a past session and a virtual object attached to a "table" node (magenta arrow). Right: A query graph generated from the current state of the scene and must be registered to the reference to restore the virtual object. The registration is achieved through semantic node matching (blue arrows).

Figure 5 . 2 :

 52 Figure 5.2: Scene registration from semantic information. Two instances "A" and "B" of the same scene are each represented by a sequence of semantically segmented images, with corresponding depth maps and camera poses. The two sets of poses do not use the same world coordinate system, so the semantic information from the images is used to register A and B through the construction and matching of two semantic graphs.

Figure 5 . 3 :

 53 Figure 5.3: Node extraction for a "counter" (left side) shown in cyan in the segmentation maps (right side, top row), in the LN-graphs (middle row) and in the SN-graphs (bottom row). Frame 165 is the first detection of the object in the image sequence (right side, left column), while 978 is its last (right column). Frame 413 shows an occurrence of object fragmentation: a second LN is added to the LN-graph to represent the same object (right side, middle column). For clarity, 3D points are only displayed for the "counter" node (circled in magenta) in the SN-graphs (light cyan), and all other SNs are already shown at their final location.

Figure 5 . 6 :

 56 Figure 5.6: a) Bottom view of the aligned reference mesh, which can be registered to b) another aligned mesh from the same scene using successive rotations of π/2 around the Z axis. c) An image generated from the reference mesh is compared to one d) generated from the other mesh rotated by 0, π/2, π or 3π/2. A rotation of π registers the meshes.

Figure 5 . 7 :

 57 Figure 5.7: Finals frames (bottom row) are matched to raw frames (top row). When a raw frame has a known pose ("keyframe", blue contour), it can be used for a matched final frame (green contour). When a raw frame without known pose is matched to a final frame (red contour), said pose is interpolated from the last and next known poses.

Figure 5 Figure 5 . 8 :

 558 Figure 5.8: Error metrics for a 2D transformation. The ground truth is T GT = I 4 and the box's center v c is at the origin. The estimated transformation T differs from T GT by an horizontal offset x, a vertical offset y, and a rotation θ. Left: the translation error isE t = x 2 + y 2and the rotation error isE R = 2 √ 1cosθ. Right: the RMSD is E RM S = E 2 t + 1 6 E 2 R (X 2 + Y 2 ).

  Translation error (meters)

  Rotation error (no unit)

Figure 5 . 10 :

 510 Figure 5.10: Median errors metrics on ScanNet [37] vs. s(l, d, m) for the walk histogram descriptor and the best adjacency descriptor variant, with optional RANSAC filtering. For the walk histogram d = 1, 2, 3, 4 with m = 1 are shown as crosses. Left: using LNs, right: using SNs.

Figure 5 . 11 :

 511 Figure 5.11: Median errors metrics on ChangeSim [139] vs. s(l, d, m) for the walk histogram descriptor and the best adjacency descriptor variant, with optional RANSAC filtering. For the walk histogram d = 1, 2, 3, 4 with m = 1 are shown as crosses. Left: using LNs, right: using SNs.

w

  ) at d = 40 consistently outperforms H 2 , but once again the ranking of performances between the SN (right) and LN (left) representations depends on the scene (as seen also in Figure5.14).

3 B 3 B2 3 B2 3 Bw , d = 2 Figure 5 . 13 :Figure 5 . 14 :

 33332513514 Figure 5.13: Error metrics for each ChangeSim[START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF] instance, using the node's label, the walk histogram descriptor and the best adjacency descriptor variant. The adjacency descriptor's size at depth 40 matches the walk histogram's size at depth 2. Left: using LNs, right: using SNs.

Figure 5 . 15 :

 515 Figure 5.15: Average times on ScanNet [37] for the descriptors generation (per node, top) and matching (per graph, bottom) vs. the RMSD for the walk histogram descriptors and variants of the adjacency descriptor at different depths d. For the walk histogram d = 1, 2 with m = 1 are shown as crosses. Left: using LNs, right: using SNs.

Figure 5 . 16 :

 516 Figure 5.16: Distribution over the depth values in percent for when an instance pair from ScanNet[START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] reaches its lowest RMSD. Left: using LNs, right: using SNs.

Figure 5 . 17 :

 517 Figure 5.17: Distribution over the depth values in percent for when an instance pair from ChangeSim[START_REF] Park | Changesim: Towards end-toend online scene change detection in industrial indoor environments[END_REF] reaches its lowest RMSD. Left: using LNs, right: using SNs.

  right of Figure5.[START_REF] Caesar | Coco-stuff: Thing and stuff classes in context[END_REF]) as it did for SN graphs. Using GT graphs also narrows the performance gap between H 2 and (B (k) w ) at d = 40, but the latter still outperforms the former at all success thresholds in Figure5.20 (left side). The performance is also improved for (B (k) w ) when using the instance segmentation ground truth (right of Figure5.20) as success rates of 90% and 100% are reached earlier.

Figure 5 . 18 :Figure 5 . 19 :

 518519 Figure 5.18: Frame from a ScanNet [37] sequence (left), semantic segmentation (middle) and instance segmentation (right). The "walls" -semantically represented by a uniform (pale blue) regionare broken up into two distinct (pale orange and purple) instances.

Figure 5 . 20 :

 520 Figure 5.20: Percentage of successful registrations on ScanNet [37] vs. an RMSD threshold for success. Left: using the node's label, H d and (B (k) w ) with GT graphs. Right: using the node's label and (B (k) w ) with SNs and GT graphs.

Figure 5 . 21 :

 521 Figure 5.21: Frames from a ScanNet[START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] sequence (left column), ground truth semantic segmentation (middle column) and semantic segmentation using ESANet[START_REF] Seichter | Efficient RGB-D semantic segmentation for indoor scene analysis[END_REF] (right column). The labelling of 3D regions visible in both frames is inconsistent when using ESANet.

Figure 5 . 22 :

 522 Figure 5.22: Median on ScanNet [37] of the RMSD with ESANet [169] labels vs. s(l, d, m) for H d and (B (k) w ), with optional RANSAC filtering. Left: using LNs, right: using SNs.

3 B 3 Bw , d = 2 Figure 5 . 23 :

 332523 Figure 5.23: Percentage of successful registrations with ESANet [169] labels on ScanNet [37] vs. an RMSD threshold for success, using the node's label, H d and (B (k)

  (a) Outdated 3D mesh showing removed object (shelf): www.turbosquid.com/3d-models/1548060 (b) Up-to-date images showing inserted object (container) (c) Ground truth: insertions (green) and removals (red).

  (d) Projected 3D removal detection (white: false negative, green/cyan: true positive, red/magenta: false positive).

Figure A. 2 :

 2 Figure A.2: container-shelf2.

  (a) Outdated 3D mesh showing removed object (robot, rabbit): www.turbosquid.com/3d-models/? (b) Up-to-date images showing inserted object (statue) (c) Ground truth: insertions (green) and removals (red).

  (d) Projected 3D removal detection (white: false negative, green/cyan: true positive, red/magenta: false positive).

Figure A. 6 :

 6 Figure A.6: statue-robot-bad-temp.

( a )

 a Outdated 3D mesh showing removed object (stone): www.turbosquid.com/3d-models/1300107 (b) Up-to-date images showing inserted object (portable toilet) (c) Ground truth: insertions (green) and removals (red).

( d )

 d Projected 3D removal detection (white: false negative, green/cyan: true positive, red/magenta: false positive).

Figure A. 8 :

 8 Figure A.8: toilet-stone.

  (d) Projected 3D removal detection (white: false negative, green/cyan: true positive, red/magenta: false positive).

Figure A. 10 :

 10 Figure A.10: 0000 01+box.

  (a) Outdated 3D mesh showing removed object (statue): www.turbosquid.com/3d-models/1335035 (b) Up-to-date images. (c) Ground truth: removals (white).

  (d) Projected 3D removal detection (white: false negative, green/cyan: true positive, red/magenta: false positive).

Figure A. 12 :

 12 Figure A.12: 0000 02+statue.

( a )

 a Outdated 3D mesh showing removed object (table): www.turbosquid.com/3d-models/1578760 (b) Up-to-date images.(c) Ground truth: removals (white).

( d )

 d Projected 3D removal detection (white: false negative, green/cyan: true positive, red/magenta: false positive).

Figure A. 14 :

 14 Figure A.14: 0001 01+table.

  (a) Outdated 3D mesh showing removed object (fire extinguisher): www.turbosquid.com/3d-models/ 1447524 (b) Up-to-date images.(c) Ground truth: removals (white).

  (d) Projected 3D removal detection (white: false negative, green/cyan: true positive, red/magenta: false positive).

Figure A. 16 :

 16 Figure A.16: 0002 01+extinguisher.

  (a) Outdated 3D mesh showing removed object (desk lamp): www.turbosquid.com/3d-models/1522080 (b) Up-to-date images. (c) Ground truth: removals (white).

  (d) Projected 3D removal detection (white: false negative, green/cyan: true positive, red/magenta: false positive).

Figure A. 18 :

 18 Figure A.18: 0003 01+desklamp.

( a )

 a Outdated 3D mesh showing removed object (bucket): www.turbosquid.com/3d-models/1288741 (b) Up-to-date images.(c) Ground truth: removals (white).

( d )

 d Projected 3D removal detection (white: false negative, green/cyan: true positive, red/magenta: false positive).

Figure A. 20 :

 20 Figure A.20: 0005 00+bucket.

  .3.2 Qualitative evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2.1 Filtering of the insertions detection results . . . . . . . . 3.3.2.2 Scenes from the Palazzolo et al. dataset . . . . . . . . . . 3.3.2.3 Scenes from ScanNet dataset . . . . . . . . . . . . . . . . 3.3.3 Computation time . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.4 Qualitative results from GPU implementation . . . . . . . . . . . . 3.3.5 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	Contents Chapter 1
	1 Introduction
	2 Related work

2.1 Change detection with 3D data . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Change detection with 2D data . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Change detection with heterogeneous data . . . . . . . . . . . . . . . . . . 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Photo-geometric change detection 3.1 Context and inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Image-based object removal detection . . . . . . . . . . . . . . . . . . . . 3.2.1 Image reprojection and occlusions handling . . . . . . . . . . . . . 3.2.2 Photo-consistency in occluded pixels . . . . . . . . . . . . . . . . . 3.2.3 Photo-consistency with multiple points of view . . . . . . . . . . . 3.2.3.1 Foreground projection . . . . . . . . . . . . . . . . . . . . 3.2.3.2 Combination of projected delta maps . . . . . . . . . . . 3.2.4 3D localisation of changes . . . . . . . . . . . . . . . . . . . . . . . 3.2.4.1 Segmentation by region . . . . . . . . . . . . . . . . . . . 3.2.4.2 Region matching . . . . . . . . . . . . . . . . . . . . . . . 3.3 Experimental evaluation and results . . . . . . . . . . . . . . . . . . . . . 3.3.1 Quantitative evaluation . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1.1 IoU and coverage with automatic thresholding . . . . . . 3.3.1.2 ROC curves for different thresholds . . . . . . . . . . . . 3

Table 2 . 1 :

 21 Common types of input data for CD algorithms

	Field	Input data
	Medical, disaster	images [120, 138, 95]
	Remote sensing	images [67, 38, 39, 42, 30]
	Smart cities

Table 2 .

 2

		2: Common natures of results of CD algorithms
	Field	Results
	Medical, disaster	caption [120, 138, 95]
	Remote sensing	pixel map [67, 38, 39, 42, 30]
	Smart cities

Table 2 . 3 :

 23 Applicability of CD algorithms input types to MR applications

	Data types Benefits	Drawbacks
	3D vs 3D	Access to 3D geometry/changes Specialized sensors
	2D vs 2D	Simple RGB sensor (camera)	Entire geometry reconstruction
	2D vs 3D	3D changes from camera	Some reconstruction (changes)

Table 3 . 1 :

 31 Change detection using reprojection

	Prior model	Current observations	CD results

Table 3 . 2 :

 32 Removal detection: quantitative results (shown in %).

	Scene	Ours	Palazzolo et al.
	Palazzolo et al. dataset IoU TPR IoU	TPR
	container-shelf	31	80	0
	container-shelf2	39	100	20
	playground-car	16	64	5
	statue-robot	48	93	14
	statue-robot-bad-exp	51	94	3
	statue-robot-bad-temp	53	95	1
	statue-robot-temp	59	95	7
	toilet-stone	17	97	0
	Dataset average	39	90	6
	ScanNet dataset	IoU TPR IoU	TPR
	0000 00+plant	11	20	7
	0000 01+box	45	57	0
	0000 01-insert+box	42	53	1
	0000 02+statue	42	47	22
	0001 00+dollhouse	6	18	0
	0001 01+table	27	36	21
	0002 00+chair	40	80	8
	0002 01+extinguisher	15	66	0
	0003 00+cat	0	0	23
	0003 01+desklamp	61	69	27
	0004 00+ghost	44	83	8
	0005 00+bucket	62	89	52
	0005 01+pitcher	27	100	0
	0006 00+lamp	57	98	38
	Dataset average	34	58	15
	Global average	36	70	12

Table 5 . 1 :

 51 Graph-based registration from image sequences

	Raw data	Output representation Registration results
	RGB-D sequences Semantic SG	3D transform

Table 5 . 2 :

 52 Number of instance pairs to perform registration

	Instances in dataset Number of scenes Resulting pairs
	1	221	0
	2	211	211
	3	246	738
	4	19	114
	5	5	50
	6	4	60
	7	1	21
	total	707	1194

  Algorithm 5: Base pseudo-code of our instance alignment algorithm. Render produces an image given a mesh and a camera pose.AlignInstances (M ref ,M) inputs : Meshes M ref , M; Alignment matrices A ref , A; Similarity threshold T ; Number of frames i max ; Poses (P i ) 1≤i≤imax output: Rotation θ best ; Similarity t best θ min ← -1; t best ← 0; for i ← 1 to i max do I ref ← Render(M ref , P i ); for θ ∈ {0, π/2, π, 3π/2} do P ← A -1 R θ A ref P i ;

	5.4.1.2 Preparing the ChangeSim data
	I ← Render(M, P ); t ← mean(I = I ref ); if t > t best then
	t best ← t; θ best ← θ; if t best > T then
	return (θ best , t best );
	return (θ best , t best );

Table 5 . 3 :

 53 Average results of the graph extractors over the datasets

	ScanNet [37]	Number of nodes Number of points	ARI
	GT extractor	31.09	12374.80 1.000
	LN extractor	49.99	49.99 0.599
	SN extractor	18.80	12376.66 0.705
	ChangeSim [139] Number of nodes Number of points
	LN extractor	767.59	767.59
	SN extractor	172.28	17790.72

All images from the datasets are available in the appendix Appendix A.

Acknowledgements

Figure 5.12: Percentage of successful registrations on ScanNet [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF] vs. an error metric threshold for success, using the node's label, the walk histogram descriptor and the best adjacency descriptor variant. The adjacency descriptor's size at depth 40 matches the walk histogram's size at depth 2. Left: using LNs, right: using SNs.

Appendix A

Photo-geometric change detection dataset

This appendix showcases the datasets of scenes on which photo-geometric change detection was performed for our work in Chapter 3. Each scene's past and present states are respectively described by an outdated 3D mesh and a sequence of registered current images. All the images of a sequence are taken within a narrow time frame to reduce structural or lighting changes. For clarity, the virtual cameras chosen to render the meshes (first row of the figures) align with the estimated camera poses of the image sequences (second row), and a 2D ground truth is provided for each such pose (third row). The cameras' intrinsic and extrinsic matrices are taken from the original datasets [START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF][START_REF] Palazzolo | Fast image-based geometric change detection given a 3d model[END_REF] and are sometimes slightly inaccurate in their estimation of the camera's pose or image distortion from its optics. The last row presents the results of the 3D detection of removed objects from Chapter 3, projected in 2D for comparison with the ground truth. To simulate object removal (from a reference mesh to current images), 3D models of objects were downloaded from Turbosquid [193] and added to the meshes, and the download links are provided for each scene. More quantitative results are provided in Chapter 3, notably the ROC curves (true positive rate against false positive rate) produced by our removal detection algorithm. Title : Towards geometric and semantic change detection for mixed reality experiences Keywords : Mixed Reality, change detection, semantic analysis, 3D reconstruction Abstract : Photorealistic Augmented Reality (AR) -or "Mixed Reality"-is applicable to various immersive experiences, from entertainment to simulation-based training, and for previsualization tasks. The realistic integration of virtual elements requires an accurate and up-to-date model of the real scene's geometry and semantic contents. The 3D structure of the environment impacts the visual rendering as well as the spatial layout of the virtual content and its interactions with real objects. Given the hardware constraints of widely available AR devices, it is impractical to thoroughly scan the geometry of the scene with each use. Still, some the scene's structural information will remain constant over time only requiring local updates to accurately represent the scene's current state.

The aim of this doctoral study has been to provide the means to identify and correct areas of change in a scene through detection of inconsistencies between a prior representation and an current observations. In this thesis, we present the completion of a lightweight reprojection-based geometric change detection framework. We also present the elaboration of a graph-based semantic scene model for Mixed Reality, and a method for its generation from semantic analysis. This model will then be used in a 3D scene registration system, in order to test its applicability to the localization task in AR.