In this paper, the use of wireless sensor networks for networked control loop is analyzed. As the non beacon-enabled mode of IEEE 802.15.4/ZigBee does not ensure the stability for the control loop since non mechanism can prevent the perturbation coming from other applications sharing the same network, the quality of control has to be guaranteed for the control loop. Several possible solutions are investigated. The first one is the CSMA/CA with probabilistic priority by adjusting the minimum waiting time. The second one consists on a deterministic priority black burst mechanism in IEEE 802.15.4/ZigBee. The third one is the beacon-enabled mode using the Guaranteed Time Slot (GTS) mechanism.

INTRODUCTION

Networked Control Systems (NCS) [START_REF] Zampieri | Trends in networked control systems[END_REF] are getting an increasing interest from both industrials and researchers. However, they suffer from limitations in mobility and flexibility because of the network wires. Wireless Networked Control Systems (WNCS) are an alternative to overcome this problem since they offer easier configuration and maintenance especially in case of several networked control loops and in shared communication medium. As an example, RUNES project [RUN] has been interested in it and showed its importance.

The IEEE 802.15.4/ZigBee seems to be one of interesting wireless networks comparing to the others since it is a low-cost low-power Wireless Sensor Networks (WSN). Moreover, even an industrial standard as WirelessHART [START_REF] Hart | [END_REF], which was designed to meet the requirements of wireless networks operating in industrial environments, uses IEEE 802.15.4-based Physical layer and MAC PDU.

However, IEEE 802.15.4/ZigBee with non beacon-enabled mode suffers from random delays because of CSMA/CA, frame losses and limited data rate. Moreover, the control traffic is perturbable by the other traffics sharing the communication medium.

First, a service's differentiation mechanism is proposed in order to improve the performances of the ZigBee for control loop in two senses. The first consist on making the medium access more deterministic. The second one aims to minimize the influence of the perturbation's traffics on the control one. Both issues are linked because minimizing the perturbation's influence on the control traffic reduces the access delay. The service differentiation will be ensured by providing a higher range of backoff exponents to the stations others than the control loop nodes to reduce the probability of stations choosing the same number of backoff periods to sense the channel. Thus, the nodes are divide into two classes: high priority nodes and normal nodes. Probabilistic priority is assigned by changing the minimum backoff exponent (macMinBE) depending on the priority level of the node. In this paper, it is shown that this mechanism improves the QoS of the network offered to the control loop.

Second, the black burst mechanism [START_REF] Sobrino | Quality of service in ad hoc carrier sense multiple access networks. Selected Areas in Communications[END_REF] is used instead of CSMA/CA in IEEE 802.15.4/ZigBee to guarantee the quality of service for the higher priority nodes. When using this mechanism, high priority stations jam the medium for period of time ( black burst) proportional to their priority. After completing the black burst, the stations sense the medium to see if another station is sending a longer black burst. The station with the longest black burst will gain access to the medium.

Third, the beacon enabled-mode in IEEE 802.15.4/ZigBee can offer medium access delay guarantees by means of the Guaranteed Time Slot (GTS) mechanism. A node can reserve a timeslot that it can use to transmit periodically its message. Hence, using the beacon enabled mode makes IEEE 802.15.4/ZigBee suitable for implementing closed-loop for real-time systems. In this paper, the capacity of IEEE 802.15.4/ZigBee to support closed control loops applications is investigated. The impact of network performance variations is evaluated in terms of Quality of Control (QoC). In particular, the limits of IEEE 802.15.4/ZigBee are shown: the lower bound of the sampling period of the control loop is 0.01536s, the number of control loops having the same sampling period is limited to two. A guideline is given to configure network parameters in order to meet QoC requirement of a control loop. Often, one needs to simulate the process, the control and the wireless network. There are several tools which allow the co-design of control loops and networks configurations. TrueTime [START_REF] Ohlin | TrueTime1.5-Reference Manual[END_REF], a Matlab/Simulink simulator, is used since it allows the simulation of the temporal aspects of multi-tasking real-time kernels and wireless networks within Simulink together with the continuous-time dynamics of the controlled plant. TrueTime does not implement the beacon-enabled mode of IEEE 802.15.4/Zig-Bee. So, this mode is added to TrueTime in order to study the effect of the GTS mechanism on wireless networked control systems. This package can be downloaded at http://www.loria.fr/equipes/TRIO/packageGTS.zip. This paper is organized as follows. In Section 2 related works are discussed. Then, the considered NCS is described in Section 3. A brief overview of the IEEE 802.15.4/ZigBee is presented in Section 4. Section 5 presents analysis of the WNCS in CSMA/CA of the non beacon-enabled mode. In Section 6, the CSMA/CA with probabilistic priority is presented. The black burst mechanism is introduced and analyzed in Section 7. Section 8 deals with an analysis of GTS. Then, this paper concludes in Section 9.

RELATED WORK

Guaranteeing the network Quality of Service (QoS), especially for industrial process control architecture, is a common problem that has been addressed in several research work. In [START_REF] Mouney | On the implementation of one process control application type through a network. considering three LANs: CAN, WiFi, ZigBee[END_REF], the case of a dedicated network (CAN, WIFI, IEEE 802.15.4/ZigBee) to the process control application has been studied but the realistic case with other nodes than control loop nodes sharing the network has not been analyzed. In [START_REF] Colandairaj | Analysis of an IEEE 802.11b wireless networked control system[END_REF], the suitability of IEEE 802.11b for wireless networked control system has been analyzed and it has been shown that the network bandwidth is important for the performance of WNCS. Koubâa et al. [START_REF] Koubâa | Improving the ieee 802.15.4 slotted csma/ca for time-critical events in wireless sensor networks[END_REF] proposed a simple differentiated service scheme for slotted CSMA/CA in IEEE 802.15.4 to improve the performance of time sensitive message. In [START_REF] Rao | Adaptive backoff exponent algorithm for zigbee[END_REF], the authors have modified the initial value of backoff exponent in IEEE 802.15.4 MAC (slotted CSMA/CA) and proposed an adapted backoff exponent (ABE) algorithm. These works was restrained to the slotted CSMA/CA and was not analyzed in the case of wireless networked control systems.

The blackburst mechanism [START_REF] Sobrino | Quality of service in ad hoc carrier sense multiple access networks. Selected Areas in Communications[END_REF] was introduced in the IEEE 802.11 to minimize the delay for real time traffic. Blackburst requires that all high priority stations try to access the medium with constant interval, and the ability to jam the wireless medium for a period of time. This mechanism was not designated for IEEE 802.15.4. Moreover, the length of the black burst is determined by the time the station has been waiting to access the medium and not it's priority. Some other works have dealt with the IEEE 802.15.4/Zig-Bee and especially the synchronization of the GTS mechanism. Francomme et al. [START_REF] Francomme | Beacon synchronization for GTS collision avoidance in an IEEE 802.15.4 meshed network[END_REF] proposed a new synchronization method for beacons and GTSs in meshed networks using IEEE 802.15.4. Koubâa et al. [START_REF] Koubâa | A time division beacon scheduling mechanism for IEEE 802.15.4/Zig-Bee cluster-tree wireless sensor networks[END_REF] proposed a synchronization mechanism based on time division beacon scheduling to construct cluster-tree WSNs. Moreover, they proposed a methodology for an efficient duty-cycle management in each router to ensure the fairest use of bandwidth resources. Those works are centric over network Quality of Service (QoS) and do not include any actual real-time applications.

These works show that the differentiation of service is a promising solution to guarantee the QoS required by the network and so the QoC needed by the control loop. Thus in this work we will analyze the WNCS using the probabilistic priority, the deterministic priority through the blackburst and the GTS mechanism in order to ensure the stability.

THE CONSIDERED NETWORKED CONTROL SYSTEM

The considered system consists on a cart whose movement is guided along a rail [START_REF] Felicioni | Impact of a (m,k)-firm data dropouts policy on the quality of control[END_REF]. We aim to control the cart's position. The variable characterizing the system's state x T = d ḋ are: d, the cart position along the rail measured from a reference point, and, ḋ its velocity. The simplified model of the system is described by the following differential equation where u is the input and k 1 , k 2 two parameters :

d = -k 1 ḋ + k 2 u (1)
where k 1 = 12.6559 and k 2 = 1.9243. A wireless sensor network containing the sensor (S), the controller (C) and the actuator (A) is introduced as shown in Figure 1. The network add new delays: τ sc is the delay between the sensor and the controller, and τ ca is the delay between the controller and the actuator ( Figure 2). The controller behaviour is characterised by the transfer function G C (s) and the process (the cart here) by G P (s). U (s) is the command, E(s) the error , Y (s) the system response, and R(s) is the reference. The sampling period should be higher than 0.010s [START_REF] Felicioni | Impact of a (m,k)-firm data dropouts policy on the quality of control[END_REF].

In the rest of the paper, the impact of the network's performance on the controlled system is studied in both ideal and realistic cases. Besides, some solutions for some possible problems are presented.

IEEE 802.15.4/ZIGBEE PROTOCOL OVERVIEW

The MAC protocol supports two operational modes that may be selected by the coordinator: beacon-enabled mode and non beacon-enabled mode.

• Non beacon-enabled mode : Medium access control is provided by an unslotted CSMA/CA (Carrier Sense Multiple Access/ Collision Avoidance) mechanism (using a random backoff time based on backoff period and Backoff Exponent (BE). There is no priority mechanism so no way to isolate a particular flow among all traffic. • Beacon-enabled mode : Beacons are periodically sent by Zigbee coordinator to synchronize nodes that are associated with it, and to identify the Personal Area Network (PAN). Superframe is contained between two consecutive beacon frames. The superframe structure is used to manage communication between these devices. The superframe contains a Contention-Access Period and Contention-Free Period (CFP), and it may include an inactive period.

The inter frame space (IFS) defines the amount of time that separates the transmission of two consecutive frames.

The MAC sublayer needs a finite amount of time to process data received by the physical layer. In an acknowledgment transmission, the IFS follows the acknowledgement frame, otherwise it follows the frame itself. The length of an IFS frame depends on the frame size. The transmission of short frames, which sizes are lower than aM axSIF SF rameSize = 18Bytes, is followed by short IFS (SIFS). The transmission of long frames, whose size are greater than aM axSIF SF rameSize, is followed by long IFS (LIFS).

CSMA/CA

Ideal case: dedicated WSN

The entire communication channel is dedicated to the control loop. The distances between sensor, actuator and controller are small enough so that they can receive the signals from each other.

In [START_REF] Mouney | On the implementation of one process control application type through a network. considering three LANs: CAN, WiFi, ZigBee[END_REF], the lower bound for the sampling period T e for IEEE 802.15.4 (non beacon-enabled mode) was evaluated as follows :

T e ≥
The RBD is evaluated as RBD = Rand[0, 2 3 -1] * BP . The backoff period (BP) is equal to 320µs. The DFD is equal to 352µs. As the aT urnaroundT ime(T T ) ≤ t ack , the t ack = T T is considered equal to (192µs). The AFD is set to 160µs. As the SIFS must be greater than the TT and the minimal value of SIFS is aM inSIF SP eriod = 12symbols, then the SIFS value is equal to 13symbols which is equivalent to 208µs since 1symbol = 16µs. Figure 3 shows flows in a sampling period. The limit of the sampling period was calculated equal to 6304µs. In practice, it is not reasonable to dedicate the entire communication channel to the control loop. In fact, the communication channel is shared by 2 cyclops (sensors equipped with camera) and a main control unit as shown in Figure 1. Hence, the wireless network is used to transmit image packets from cyclops to the main control unit. The image sensor has CIF resolution (352×288). Each cyclops sends, periodically, 133octets. In the following, the plant behavior is studied for different perturbation load. The transmission period is modified in order to see the effect of the new additional network load on the NCS. Our NCS can stay stable if the additional network load is less than 44% of the total bandwidth. However, if this additional network load reaches 44% ( the transmission period of each cyclops = 0.02s), the cart becomes instable. Thus, the additional load of 44% of the total bandwidth is the upper limit for the stability of our WNCS. Hence, the unslotted CSMA/CA of the non beacon-enabled mode is not convenient for WNCSs.

CSMA/CA WITH PROBABILISTIC PRIORITY

The CSMA/CA mechanism for IEEE 802.15.4 uses the random waiting delay for collision avoidance. It uses the backoff exponent (BE) which is related to how many backoff period (BP) a device must wait before attempting to assess the channel activity. The algorithm attempts to avoid collision by waiting during a given delay randomly generated in the range of [0, 2 BE -1] × BP . If batterylife extension is activated then, BE = min(2, macM inBE) else, BE = macM inBE where macMinBE attribute specifies the minimum of backoff exponent, which is set to 3 by default. This aspect is exploited in order to differentiate the services offered by the WSN. We propose to vary the randomly generated waiting delay depending on the priority of the packet. Thus, by choosing a higher macMinBE for the applications different from the control loop, the probability to have a longer delay is increased and the control loop nodes are allowed to send their data packets.

The nodes are divided into two classes: the first class contains the nodes of the WNCS (sensor, controller, and actuator), the second class is composed of the other nodes present in the WSN. The BE CL represents the BE of the control loop nodes macM inBE CL its macM inBE, and it is set to the default value 3. The macM inBE OA and BE OA are the macM inBE and the BE of the other applications sharing the WSN. When the batterylife extension is not activated, the control loop nodes have to wait random[0, 2 BECL -1] × BP ( random[0, 7] × BP ).

Modifying macMinBE

The macM inBE OA is increased for the applications with non critical real-time needs. Thus, their data packets wait during a delay randomly generated in a longer range (random[0, 2 macM inBEOA -1] × BP ) than the one for the control loop. This is ensured via an assignment of a probabilistic priority to the nodes in the WSN. This probabilistic priority is ensured by modifying the range for the random delay. Hence, the higher priority nodes (the control loop nodes here) have more chance to send their data packets. Figure 5 shows the macM inBE OA , obtained by simulations, which allows the control loop to be stable for different loads. For a small load (less than 35%), there is no need to increase the macM inBE since the default value 3 can afford the stability for the WNCS. When the disturbing load becomes important, the control loop becomes to be instable because of the long delay and the packets losses. Thus, increasing the macM inBE OA allows the control loop to reach the stability in spite of the perturbing load.

In fact, for the considered control loop, the value of 7 for macM inBE afford the stability for the control loop for a perturbation load of 90% of the total bandwidth.

Collisions still exist since the nodes of WSN can choose the same waiting delay.

Modifying the minimum waiting time and the macMinBE

We are interested in minimizing the collisions between nodes of the two classes (control loop and other applications). The lower-priority applications will wait during a delay randomly generated in the range of [variable, 2 BEOA -1] backoff periods. The question is how to choose the variable's value. This variable is set to be equal to 2 BECL so that there is no collision between the members of the two classes ( variable = 8). Figure 6 presents the evolution of the macM inBE OA which allow the WNCS to be stable for different perturbation loads. The value of macM inBE OA using this method is less than the one found when only the macM inBE is modified. Thus, separating the ranges of random waiting value of the two classes improve the QoS offered to the WNCS.

Discussion This mechanism can lead to the under-use of the network resources due to the new waiting delay. Even when the communication medium is free and no one from the class of the control loop wants to send, the nodes of the other class have to choose their waiting period in a large range. This leads to under-use of the network resources. Moreover, this mechanism is not deterministic. Thus, the blackburst or the GTS mechanism can be used.

BLACKBURST MECHANISM TO ACHIEVE DETERMINISTIC PRIORITY

The goal of black burst [START_REF] Sobrino | Quality of service in ad hoc carrier sense multiple access networks. Selected Areas in Communications[END_REF] is to minimize the delay for the real-time traffic. The black burst mechanism requires that:(i) all stations try to access the medium with equal, constant interval, blackburst period as shown in Figure 8; (ii) the ability to jam the medium for a period of time.

When a new cycle starts, each station who wants to send a frame, sends a blackburst to jam the channel. The length of the blackburst is determined by the priority of the application, and is calculated as a number of black slots. The duration of a black slot t bslot is at least equal to the turn around time (TT) (t bslot ≥ T T ). After transmitting the blackburst, the station listens to the medium for an observation time t obs (t obs < t bslot ) to see if another station is sending a longer blackburst. This would imply that this station has higher priority, so it should access the medium first. If the medium is idle, the station will then send its frame, otherwise it will wait until the medium becomes idle again and enter another black burst period. As it is supposed that there is different priority for each station, the black burst mechanism will yield to a unique winner. Fig. 7. Competition to access to the communication medium Figure 7 shows three nodes competing to access to the communication medium. Node N 3 has the lowest priority, thus it is the first one to finish the transmission of black burst. Then, it listens to the medium during a t obs and it finds that there is someone else sending. Hence, N 3 quits. The same thing for node N 2. When node N 1 (with the highest priority) transmits its black bursts and then listens to the medium, it finds it free. Thus, N 1 is the winner and start to send its data packet.

where aT urnaroundT ime ≤ t ack ≤ (aT urnaroundT ime +aU nitBackof f P eriod) (12 symbols ≤ t ack ≤ 32 symbols). The length of the Maximum Data Frame Duration, in the IEEE 802.15.4, is fixed to 133 octets, so the transmission duration is equal to 4256µs. The same value, as used in the CSMA/CA, is maintained for ACK Frame Duration (160µs), the t ack (32 symbols, 512µs) and the LIFS (40 symbols, 640µs). The duration of the black slot is set to TT, so t bslot = 192µs. Besides, the observation time t obs is fixed to 180µs.

T bb = maxP rio × t bslot + cste (4)
For the studied system , the maximum priority value is fixed to five ( since we have five nodes in the network). Thus, the black burst period is equal to 6708µs. Using static priority in this part and ensuring that messages have different priorities, we guarantee that each black burst contention period will yield a unique winner.

Implementation and results

The black burst mechanism is implemented and added to the TrueTime package. The used configuration is shown in Figure 1. Higher priority is assigned to the control loop nodes, so that, whenever one of them has a data packet, he can send it no later than a T bb . For important perturbation loads (more than 90% of the total bandwidth), the simulation results show that the cart answer follows the reference. Thus, the black burst mechanism ensures that our wireless networked control system remains stable.

Discussion This approach is interesting when the sampling period of the control loop is greater than the black burst period (T e > T bb ). Thus, if the control loop nodes have the highest priority then their data packets will be sent and the controlled system will reach the required QoC.

The maximal priority value is given by

maxP rio ≤ ⌊ T e -cste t bslot ⌋. (5)
If the highest priority in the WSN do not satisfy the inequation (5) the black burst mechanism will not guarantee anymore the stability for the WNCS. Thus, the GTS mechanism is an interesting alternative to resolve this problem.

GTS MECHANISM

To ensure the stability of the WNCS, we are interested in the beacon-enabled mode of the IEEE 802.15.4. Indeed, network resources are reserved using the GTS mechanism. The superframe duration (SD) is given by SD = aBaseSuperf rameDuration.2 SO for 0 ≤ SO ≤ BO ≤ 14 where SO is the Superframe Order. SD is divided into 16 equally-sized time slots, during which frame transmissions are allowed. GTSs are allocated by the PAN coordinator. The PAN coordinator can allocate at most seven GTSs and each GTS may occupy more than one time slot.

Each node in the control loop will have a reserved GTS whose size will be 1 slot since the control data is not big (small frame). Figure 9 shows that 3 GTSs (3 slots) are needed, but as the superframe has at least 16 slots (if the inactive part is omitted), the WNCS sampling period T e has to be at least equal to the superframe duration. Indeed, T e must be greater than SD. As the smallest superframe duration (for SO = 0) is equal to 0.01536s, then the WNCS sampling period T e is greater then T emin = 0.01536s. Besides, since the number of GTS is restricted to 7, the GTS mechanism cannot afford QoS guarantees to more than two control loops with the same sampling period. Otherwise, one should use the scheduling policy in [START_REF] Francomme | Beacon synchronization for GTS collision avoidance in an IEEE 802.15.4 meshed network[END_REF]. The considered system is shown in Figure 1. This system is simulated using the IEEE 802.15.4/ZigBee beacon-enabled mode. Moreover, in these simulations the mechanism of signal adaptation is disabled since it creates messages and disturbs the GTS mechanism (more than one GTS are needed for each node). Besides, only two GTS are used, one for the controller and another for the sensor because, in TrueTime the acknowledgement is fictive.

It is assumed that there is no energy problem for the nodes (infinite amount of energy). Moreover, the controller is considered as the PAN coordinator. The mobility problem (nodes are static) is not addressed for the moment. Besides, in the simulation example, the acknowledgement is not taken into account. So, only two GTSs are needed. The nodes send only in their reserved GTS and without packet loss. Several perturbation's loads higher than 44% are tested. The plant behavior follows almost exactly the reference. Thus, using the GTS mechanism guarantees the network QoS and the required QoC for the control loop.

CONCLUSIONS

In this paper, three mechanisms of service differentiation are presented: the CSMA/CA using the probabilistic priority, the IEEE 802.15.4 using the blackburst mechanism, and the GTS mechanism of the beacon-enabled mode of the IEEE 802.15.4. These mechanisms are implemented and tested on the considered networked control system using TrueTime. From this study, we show that IEEE 802.15.4 can be used for the WNCS with the proposed mechanisms. As future work, we aim to manage the QoS offered to the WNCS depending on the state of the controlled system.

Fig. 1 .Fig. 2 .

 12 Fig. 1. IEEE 802.15.4/Zigbee using CSMA/CA: shared network

  Random backoff duration (RBD) +Data frame duration (DF D) +time for acknowledgment (t ack ) +ACK frame duration (AF D) +Short Inter-Frame Space (SIFS) +RBD +DFD +t ack + AFD + SIF S.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Flows in a sampling period IEEE 802.15.4/Zigbee non beacon-enabled mode Figure 4 shows the behavior of the plant Y (cart) and the reference R. The plant follows instantaneously the reference and it is stable.

Fig. 5 .

 5 Fig. 5. macM inBE OA variation depending on the perturbation load

Fig. 6 .

 6 Fig. 6. macM inBE OA variation depending on the perturbation load

Fig. 8 .

 8 Fig. 8. Flows in a black burst period Figure 8 shows flows in a black burst period T bb . The black burst period is evaluated as T bb = maxP rio × t bslot + t obs +Maximum Data Frame Duration +t ack + ACK frame duration +Long Inter-Frame Space (LIFS)(3)

Fig. 9 .

 9 Fig. 9. Used GTSs by the WNCS

Fig. 10 .

 10 Fig. 10. The IEEE 802.15.4/ZigBee with beacon enabled mode in TrueTime

⋆ This work is partially supported by Safe-NECS project funded by ANR under ANR05SSIA001503.


Iris De Gélis
email: iris.de-gelis@irisa.fr

Sébastien Lefèvre

Thomas Corpetti

A Preprint

DC3DCD: UNSUPERVISED LEARNING FOR MULTICLASS 3D POINT CLOUD CHANGE DETECTION A PREPRINT

Keywords: 3D point clouds, Change detection, Unsupervised Deep learning, Deep clustering

In a constant evolving world, change detection is of prime importance to keep updated maps. To better sense areas with complex geometry (urban areas in particular), considering 3D data appears to be an interesting alternative to classical 2D images. In this context, 3D point clouds (PCs) obtained by LiDAR or photogrammetry are very interesting. While recent studies showed the considerable benefit of using deep learning-based methods to detect and characterize changes into raw 3D PCs, these studies rely on large annotated training data to obtain accurate results. The collection of these annotations are tricky and time-consuming. The availability of unsupervised or weakly supervised approaches is then of prime interest. In this paper, we propose an unsupervised method, called DeepCluster 3D Change Detection (DC3DCD), to detect and categorize multiclass changes at point level. We classify our approach in the unsupervised family given the fact that we extract in a completely unsupervised way a number of clusters associated with potential changes. Let us precise that in the end of the process, the user has only to assign a label to each of these clusters to derive the final change map. Our method builds upon the DeepCluster approach, originally designed for image classification, to handle complex raw 3D PCs and perform change segmentation task. An assessment of the method on both simulated and real public dataset is provided. The proposed method allows to outperform fully-supervised traditional machine learning algorithm and to be competitive with fully-supervised deep learning networks applied on rasterization of 3D PCs with a mean of IoU over classes of change of 57.06% and 66.69% for the simulated and the real datasets, respectively. The code is available at https://github.com/IdeGelis/torch-points3d-DC3DCD.

Introduction

While urban environments are continuously and rapidly evolving, change detection between several temporal acquisitions is a way to quickly highlight modified areas in order to update maps [START_REF] Begüm Demir | Updating land-cover maps by classification of image time series: A novel change-detection-driven transfer learning approach[END_REF] or to identify damaged objects [START_REF] Dong | A comprehensive review of earthquake-induced building damage detection with remote sensing techniques[END_REF] in case of natural disasters. With regard to the complexity of urban landscapes, sensing the area using also vertical information appears to be judicious. Indeed, such three-dimensional (3D) information allows to better characterize environment geometry and to avoid two-dimensional (2D) image problems such as the difference of viewing angles between distinct acquisitions, spectral variability of objects over time, perspective, and distortion effects [START_REF] Qin | 3D change detection -approaches and applications[END_REF]. 3D data are acquired thanks to Light Detection And Ranging (LiDAR) sensor or photogrammetric process, both resulting in 3D Point Clouds (PCs). No matter the type of acquisition (LiDAR, photogrammetry for example), multi-temporal 3D data are generalizing. Indeed, more and more national mapping agencies opt for full territory Aerial Laser Scanning (ALS) campaign, as in the Netherlands with Actueel Hoogtebestand Nederland (AHN) multi-temporal campaigns [START_REF] Van Der Sande | Assessment of relative accuracy of ahn-2 laser scanning data using planar features[END_REF], or in France with the LiDAR high density (HD) project whose objective is to propose a complete 3D high resolution coverage of France with regular updates in the future. In the same time satellites mission for 3D sensing are multiplying, e.g., Pléiades [START_REF] Bernard | 3d capabilities of pleiades satellite[END_REF], Pléiades Néo [START_REF] Jérôme | Shaping the future of earth observation with pléiades neo[END_REF], 3D Optical Constellation (CO3D) [START_REF] Lebègue | Co3d, a worldwide one-meter accuracy dem for[END_REF] missions. In civil engineering, Terrestrial Laser Scanning (TLS) or unmanned aerial vehicle (UAV) photogrammetry are becoming unavoidable for an accurate sense of complex objects. Thereby, this calls for methods able to analyze these multi-temporal 3D data.

Whether related to urban environment [START_REF] Stilla | Change detection of urban objects using 3d point clouds: A review[END_REF] or geosciences [START_REF] Okyay | Airborne lidar change detection: An overview of earth sciences applications[END_REF], many studies have been focused on handling 3D data for accurate change extraction. Recently, some methods based on deep learning proved their efficiency over traditional distance-based methods and machine learning. While the first deep learning methods for 3D change detection where based on 2.5D rasterization of PCs into Digital Surface Model (DSM) [Zhang et al., 2018a[START_REF] Zhang | Detecting building changes between airborne laser scanning and photogrammetric data[END_REF] or range image [START_REF] Nagy | Changegan: A deep network for change detection in coarsely registered point clouds[END_REF], most recent works are dealing directly with the raw 3D data. Indeed, although easing the computation, any rasterization process implies a significant loss of information for instance on building facades but also due to aggregation of several points in a cell. [START_REF] Ku | Shrec 2021: 3d point cloud change detection for street scenes[END_REF] propose to represent PCs by graphs and apply graph convolution operator (EdgeConv) [START_REF] Wang | Dynamic graph cnn for learning on point clouds[END_REF] to extract discriminative features. However, their proposed method, called Siamese Graph Convolutional Network (SiamGCN), results only in change detection at the scene level, i.e., solving a change classification task. On the opposite, de Gélis et al. [2023] proposed a network to solve change segmentation task, i.e., providing multiclass change information at point level (so coarser results than change classification). To handle raw 3D PCs, they rely on Kernel Point Convolution (KPConv) [START_REF] Thomas | Kpconv: Flexible and deformable convolution for point clouds[END_REF]. Their network, named Siamese KPConv enables to outperform other machine learning methods or DSM-based deep learning methods. More recently, a study [de Gélis et al., 2023] suggests improving Siamese KPConv by making the network focusing more on change-related features. To do so, the authors propose to provide an hand-crafted feature related to change as input to Siamese KPConv along with 3D point coordinates. They also developed three other architectures for this particular task. OneConvFusion and Triplet KPConv contain specific change-related encoder that takes as input only feature difference. Encoder Fusion SiamKPConv (EFSKPConv) concatenates both change and mono-date information directly in the encoder. This latter achieves the best results compared to previous state-of-the-art methods.

Although efficient, these deep learning-based methods are supervised, i.e., require large databases for the training of the network. For change segmentation, millions of points should be annotated according to the change type. This annotation is often performed manually because any automatization process is not obvious due to PCs characteristics such as the lack of point-to-point correspondence, sparsity, or occlusions (see the example of AHN Change Detection (AHN-CD) dataset [de Gélis et al., 2023]). Therefore, it is interesting to develop methods that require none or at least less annotations to perform 3D change segmentation. As stated in recent surveys [START_REF] Kharroubi | Three dimensional change detection using point clouds: A review[END_REF], Xiao et al., 2023], the literature still lacks of methods for unsupervised or weakly supervised learning when dealing with 3D PCs change detection. Indeed, nowadays unsupervised methods are mostly traditional rule-based methods that are often very specific to a dataset. Also, recently an adaptation of Deep Change Vector Analysis (DCVA) [START_REF] Saha | Unsupervised deep change vector analysis for multiple-change detection in vhr images[END_REF] to 3D PCs change detection has been proposed based on self-supervised learning [de Gélis et al., 2023]. However, this unsupervised method only deals with binary change segmentation, thus the method is not able to distinguish between multiple classes of changes. Thereby, in this paper, we propose an unsupervised learning strategy to deal with multiclass 3D PCs change segmentation. The strategy is based on deep clustering principle and in particular on DeepCluster [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF]. Deep clustering consists in jointly optimizing deep representation of the data and performing clustering with learned features [START_REF] Yazhou Ren | Deep clustering: A comprehensive survey[END_REF][START_REF] Zhou | A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions[END_REF]. This strategy has received increasing interest for 2D image unsupervised representation learning in computer vision [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF][START_REF] Jang | Picie: Unsupervised semantic segmentation using invariance and equivariance in clustering[END_REF]. However, as far as the change detection task is concerned, the use of deep clustering is less common. Zhang et al. [2018b] and [START_REF] Dong | A multiscale self-attention deep clustering for change detection in sar images[END_REF] propose to rely on an unsupervised clustering of deep feature representations to further train their network to perform change detection. In Zhang et al. [2018b] a stack of fully-connected layers is used to learn Gaussian-distributed and discriminative difference representations for non-change and different types of changes. [START_REF] Dong | A multiscale self-attention deep clustering for change detection in sar images[END_REF] further improve the latter by using a Convolutional Neural Network (CNN) relying on multi-scale self-attention. Another study partially uses deep clustering principle for 2D binary change detection by introducing a deep clustering loss jointly with contrastive and appealing losses to make a CNN network learn discriminative mono-date features. These features are further compared using DCVA principle to extract binary changes in multi-modal optical and Synthetic Aperture Radar (SAR) images [START_REF] Saha | Self-supervised multisensor change detection[END_REF]. This principle was adapted in de Gélis et al. [2023] for 3D PCs binary change detection. Finally, to the best of our knowledge, Zhang et al. [2021] is the first and unique study using the deep clustering principle on 3D data. However, the approach relies on a voxelisation of the PC instead of dealing with the raw PC directly, and performs classification at the scene level and not at the point level (a.k.a. segmentation).

The contributions of this work are thus as follows:

1. To the best of our knowledge, we propose the first unsupervised learning strategy for multiclass change segmentation into raw 3D PCs.

3. After analyzing the learning behavior, we evaluate our method on both real and simulated public datasets, and provide comparisons with supervised methods and weakly-supervised methods.

The description of our method is given in Section 2. The results are provided in Section 3 and discussed in Section 4. Finally, the conclusion is provided in Section 5. The implementation of our method is available at https://github.c om/IdeGelis/torch-points3d-DC3DCD.

Unsupervised 3D change detection

Before describing our method for 3D PCs multiple change segmentation, an overview of DeepCluster [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF] is given, as it is an important component of our model.

DeepCluster principle

Among the variety of studies related to deep clustering [START_REF] Yazhou Ren | Deep clustering: A comprehensive survey[END_REF][START_REF] Zhou | A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions[END_REF]], DeepCluster appears to be among the most fundamental ones. Proposed by [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF], this method resides in a rather simple idea of alternatively clustering deep latent representation of data to obtain pseudo-labels further used to train a CNN. In particular, the convolutional network is trained in a supervised manner using pseudo-labels as objective for prediction.

In a traditional supervised approach, giving a set of N images x n (n ∈ [1, N ]), a parametrized classifier g W predicts the correct labels (y n ) using the features extracted by f θ (x n ) (W and θ being the parameters from the classifier and the back-bone convolutional model, respectively). They are optimized according to the following problem:

min θ,W 1 N N n=1 (g W (f θ (x n )), y n ) (1)
where is the loss function, a classical negative log-likelihood (NLL) in their method. This cost function is minimized using standard mini-batch stochastic gradient descent and backpropagation to compute the gradient. The difficulty in an unsupervised setting is therefore to define y n .

In DeepCluster, [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF] proposed to rely on a classical clustering algorithm such as k-means [START_REF] Macqueen | Classification and analysis of multivariate observations[END_REF] or power iteration clustering (PIC) [START_REF] Lin | Power iteration clustering[END_REF] to obtain a pseudo-label (y P Ln ) that is used instead of y n . [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF] showed that the choice of the clustering algorithm is not crucial. Thereby, for illustration purposes, we continue with the example of k-means algorithm. This clustering method matches data to k groups (pseudo-clusters) by minimizing distance between each data and its corresponding cluster center, called centroid (and contained in the centroid matrix C in practice).

Finally, the unsupervised training process alternates between i) clustering the output features of the back-bone convolutional model (f θ (x n )) (clustering step), and ii) updating parameters θ and W using the obtained pseudo-labels (y P Ln ) thanks to Equation 1 (training step). This relies on the fact that a Multi-Layer Perceptron (MLP) classifier on top of a standard CNN with randomly initialized weights (θ) provides results far above from the chance (i.e., random) level [START_REF] Noroozi | Unsupervised learning of visual representations by solving jigsaw puzzles[END_REF].

In practice, a few tricks are required to avoid trivial solutions, e.g., assigning all the inputs to the same cluster. First, the authors get rid of empty clusters by randomly dividing in two groups the largest cluster when an empty cluster appears. Second, if the pseudo-cluster representation of data is largely imbalanced, the deep model will tend to assign all data to the most represented pseudo-cluster. To counter this, they propose to sample input images during the training based on a uniform distribution over the pseudo-labels.

They showed the robustness of their method by training different architectures (Alexnet [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] and VGG-16 [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF]) on ImageNet [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF] or YFCC100M [START_REF] Thomee | Yfcc100m: The new data in multimedia research[END_REF] images datasets.

In the following, we adapt this principle to 3D PCs change detection.

DC3DCD: unsupervised learning for 3D multiple change extraction

Whereas the task and the data (2D image classification) of DeepCluster is far from 3D PCs multiple change segmentation, we nevertheless decided to adapt this method to our task and particular data. By replacing the CNN by a 3D PCs change detection back-bone, some change-related features can be extracted. Thereby, the clustering of these deep features results in change-related pseudo-clusters. We further rely on these pseudo-clusters to optimize the trainable parameters θ of the change detection back-bone. Figure 1 illustrates our method called DeepCluster 3D Change Detection (DC3DCD). The overall training process of our method is given in the Algorithm 1. Even if the general idea of DeepCluster remains, some specific features of DC3DCD distinguishing it from the original DeepCluster idea should be noted, as described in the following.

Back-bone model

Because of the unstructured nature of 3D PCs, traditional CNN models cannot be applied on them and furthermore, they do not output change-related deep features, but they rather characterize each input independently. To cope these issues, some studies have recently proposed different architectures for supervised change detection in 3D PCs (see section 1). These architectures can therefore be used as a back-bone to our unsupervised method. In practice, both Siamese KPConv [de Gélis et al., 2023] and Encoder Fusion SiamKPConv [de Gélis et al., 2023] will be experimented. Siamese KPConv architecture is chosen because it is the first architecture to perform change segmentation into raw 3D PCs. It extends the idea of Siamese networks with the KPConv convolution principle, as can be seen in Figure 2a. The very recent Encoder Fusion SiamKPConv is experimented as well since it has been shown in de Gélis et al. [2023] that it outperforms other state-of-the-art methods including Siamese KPConv. The main idea behind this architecture is no more to encode the two PCs independently (as Siamese KPConv do) but rather to include the change information along the encoding process, as can be seen in Figure 2b where the encoding in the bottom part takes into account also the differences between features.

Thus, parameters θ to be optimized are parameters of these back-bone architectures.

Use of a prototype layer

In the original version of DeepCluster, the final classification layer of g W is re-initialized before each parameter optimization session (i.e., training steps) because there is no correspondence between two consecutive cluster assignments.

The authors further proposed an improved version of DeepCluster (DeepCluster-V2) by replacing the classifier g W by the prototypes, i.e., cluster centers. This ends up with an explicit comparison of the features and the centroid matrix C, and tends to improve stability and performance of DeepCluster [START_REF] Caron | Unsupervised learning of visual features by contrasting cluster assignments[END_REF]. According to preliminary experiments, we also decided to use the centroid matrix C defining pseudo-cluster centers. Therefore, the last fully connected layer parameters of the back-bone are set using the centroid matrix C. This so-called prototype layer is updated after each clustering step and fixed during the training step.

Input data

We aim at detecting changes into raw 3D PCs. In addition of using a specific back-bone able to compute features directly in 3D PCs, some pairs of bi-temporal vertical cylinders need to be used as input to the network. In a context of change detection, cylinders are preferred to spheres when point clouds have a privileged orientation, as for airborne 3D PCs where the vertical direction embeds different information than horizontal ones [de Gélis et al., 2023].

Furthermore, in their experimentation, [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF] provide Sobel-filtered images as input to the CNN instead of Red Green Blue (RGB) images. Sobel filtering acts as an edge detector thanks to the computation of gradients on the image. This seems an important step in their method [START_REF] Caron | Self-supervised learning of deep visual representations[END_REF][START_REF] Mustapha | A deep dive into deep cluster[END_REF] and acts as a pre-computation of relevant features. However, when dealing with 3D PCs, there is no direct equivalent to Sobel filtering. Thus, we rely on some predefined features commonly used to characterize 3D PCs. Let us note that using such features can help the network, as already shown in a supervised scenario [de Gélis et al., 2023]. As such, we consider here some handcrafted features already used in a Random Forest (RF)-based change detection context [START_REF] Tran | Integrated change detection and classification in urban areas based on airborne laser scanning point clouds[END_REF]:

• Point distribution represented by point normals and information on the distribution of points in the neighborhood (i.e., linearity, planarity, and omnivariance).

• Height information characterized by rank of the point on vertical axis in the neighborhood, maximum range of elevation of points in the neighborhood, and normalized height according to the local Digital Terrain Model (DTM) (rasterization of the PC at the ground level).

• Change information described through a feature called stability (ratio of the number of points in the neighborhood of the current PC to the number of points in the neighborhood in the other PC).

We refer the reader to the original paper [START_REF] Tran | Integrated change detection and classification in urban areas based on airborne laser scanning point clouds[END_REF] for a detailed description of these features.

Size of the training set

Change segmentation task implies assigning a pseudo-label to each point of the second PC (of pairs of the training set).

To fit in memory, a mini-batch k-means [START_REF] Sculley | Web-scale k-means clustering[END_REF] clustering is used. The principle of splitting the largest cluster when an empty cluster appears is used as in DeepCluster.

Imbalanced dataset

Change detection datasets are highly imbalanced. To avoid falling in a trivial solution where the back-bone predicts all points with the same label, after each clustering step weights W k (considering pseudo-labels distribution) are computed. These weights are further used to both select training cylinders and weight the loss (L N LL ). Let us note that this cylinder selection process was also applied in the supervised context [de Gélis et al., 2023] (on the real labels though). It aims at giving more training samples of underrepresented pseudo-clusters. It also acts as a kind of data augmentation because from one epoch to another, selected cylinders differ according to the random drawing of the cylinder's central point. Without this trick, the method is likely to collapse to a single class prediction. For the K predicted clusters, a mapping with the corresponding real class is performed by a user to obtain the final change segmentation of the PC. 5 mappings are provided for the sake of illustration. Segmenting the whole dataset requires K annotations only. This is far less than the millions of points that need to be annotated in order to build training and validation sets in a supervised setting.

3D PCs data augmentation

During the training step, data augmentation appears to be crucial for stability and performance of the method. In particular, the following data augmentation strategies are used: random cylinders rotation around the vertical axis (same angle for both cylinders of a pair), and addition of a Gaussian noise at point level.

From predicted pseudo-labels to real labels

The above training using DC3DCD method is fully unsupervised, thereby no use of a ground truth is required. At the end of the overall training process, the back-bone predicts labels for all points of the second PC according to the change. Predicted labels do not directly correspond to the real labels. There is an oversegmentation of PCs inducted by the choice of K, the number of pseudo-clusters, which is often large compared to the number of real classes. By opting for such an oversegmentation setting, we expect to be able to address various use cases with different size and precision of classes. One real class is then composed of several predicted clusters, while we assume a predicted cluster to contain only one real class. To map a real label onto each predicted label, a mapping step is necessary. For this mapping, we consider that the user should be involved in order to select the kind of changes that is of interest given the use case. DC3DCD enables to train a back-bone to segment the PC into small areas containing the same types of change or unchanged objects. Thus, the user just has to select for each predicted cluster a corresponding real class. It can be viewed as a kind of active learning process. This is illustrated in Figure 3. This strategy finally involves K annotations to obtain a final change segmentation over the whole testing set (no matter its size). K corresponds to the number of pseudo-clusters used during the training. This hyper-parameter has to be set beforehand. For this reason, our method can be viewed as weakly supervised since K annotations by a user are required in the end of the process. However, these annotations (smaller than the millions of points contained in the dataset) are not taken into account in the learning process, and we therefore classify our approach in the family of unsupervised methods. In practice, for the experimental assessment of our method, we map a predicted cluster onto a real class taking into account the real majority class it contains.

3 Experimental results

Experimental settings and protocol

We detail here how we set the main hyper-parameters and we describe our experimental settings.

Datasets

Both simulated and real datasets will be experimented, considering Urb3DCD-V2 in low density LiDAR configuration [START_REF] De Gélis | Change detection in urban point clouds: An experimental comparison with simulated 3d datasets[END_REF][de Gélis et al., , 2023] ] and AHN-CD [de Gélis et al., 2023]. To the best of our knowledge, these are the only public datasets for change segmentation. The Urb3DCD dataset is composed of simulated ALS PCs over a french city model (Lyon, France). A simulator is used in order to obtain an accurate annotation of 3D points concerning multiclass changes. Conversely, AHN-CD dataset is made of real ALS PC from AHN campaigns over the Netherland [START_REF] Van Der Sande | Assessment of relative accuracy of ahn-2 laser scanning data using planar features[END_REF]. The change ground-truth is obtained thanks to a semi-automatic process. In de Gélis et al. [2023], it has been shown that this process is not perfect since it results in a lot of misclassifications. Therefore, the test set of this dataset will be used for qualitative assessment only. As for quantitative assessment, AHN-CD comes with a manually annotated sub-part of the test set, on which we will report and compare quality scores. Note that during the training, we make no use of the ground truth unless for the method assessment purpose (see Section 3.2). The first sub-sampling rate dl 0 is set to 1 m and the cylinder radius to 50 m for Urb3DCD-V2-1. While for AHN-CD dl 0 is set to 0.5 m and the cylinder radius to 20 m because of the difference of density between both datasets.

Number of pseudo-clusters K

As shown in different studies related to DeepCluster [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF][START_REF] Mustapha | A deep dive into deep cluster[END_REF], choosing the number of pseudo-clusters is important. We experimented several values for K on the simulated dataset and found that K = 1000 was an adequate compromise to ensure a stable training and a reasonable oversegmentation. A too small value may not reflect all different types of changes (and thus not allow the user to select the changes of interest), while a too large value leads to high training and annotation times. The same value will also be used with the real dataset AHN-CD.

Training step and parameters optimization

For the training process, a Stochastic Gradient Descent (SGD) with momentum of 0.98 is applied to minimize a point-wise NLL loss using the pseudo-labels defined in the clustering step. A batch size of 10 is used. The initial learning rate is set to 10 -3 and scheduled to decrease exponentially. As in [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF], we experimentally verified that reassigning the clustering after each epoch is better than an update after each n epochs. Indeed, if several training epochs are conducted, the model seems to converge in the first local minimum associated with a non-optimal pseudo-clustering. In each epoch, 3,000 cylinder pairs are seen by the model. A total of 55 epochs, i.e., 55 clustering and training steps, is performed. et al. [2018] networks to DSM inspired by [START_REF] Zhang | Detecting building changes between airborne laser scanning and photogrammetric data[END_REF]). Results of a RF algorithm trained on hand-crafted features [START_REF] Tran | Integrated change detection and classification in urban areas based on airborne laser scanning point clouds[END_REF]] are also given.

Comparisons with supervised methods

Adaptation of a supervised method to a weakly supervised setting

To evaluate the benefit of our method, we propose a comparison with deep learning-based supervised methods tuned to a weakly supervised setting. In practice, we use Encoder Fusion SiamKPConv, the best of supervised techniques according to de Gélis et al. [2023]. To this end, we trained it with the same amount of annotated data as our DC3DCD setting. However, this is not straightforward since this network cannot be trained with only 1,000 points. Indeed, as during the supervised training of this network, labels should be provided for each point of the second PC of the pair, and as a cylinder contains more than 1,000 points (about 3,500), we cannot directly compare the supervised training with the same amount of labels (i.e., K = 1000). Thus, for both training and validation sets, we chose 7 cylinders, each one centered on one of the 7 classes contained in Urb3DCD-V2 to be sure that each class is represented. Note that with this minimal training configuration, the number of annotated points in the 14 cylinders is around 50,000. As 7 cylinders are less than the batch size of 10 used for all other deep learning-based methods, we also provide results with a batch size of 2.

Comparisons with unsupervised methods

To the best of our knowledge, there is no other weakly supervised or unsupervised deep learning method tackling 3D PCs multiple change segmentation. Thereby, we provide a comparison with a k-means algorithm applied on the ten hand-crafted features of [START_REF] Tran | Integrated change detection and classification in urban areas based on airborne laser scanning point clouds[END_REF] dedicated to change detection in 3D PCs. Note that LiDAR specific features (e.g., intensity or number of echoes) used in [START_REF] Tran | Integrated change detection and classification in urban areas based on airborne laser scanning point clouds[END_REF] are ignored here since the simulated dataset does not contain such information. For fair comparison, the k-means is set to predict also K = 1, 000 pseudo-clusters. The same user-guided mapping is done as proposed in the previous section (Figure 3) to assign the final classes.

Before presenting the quantitative results, we analyze in the next section the behavior of the network during the training process.

Analysis of the learning process

Before presenting the results on the different datasets, we propose to study the behavior of DC3DCD during the training phase. To do so, we rely on the Encoder Fusion SiamKPConv back-bone and the configuration without the use of the ten hand-crafted features as input, so considering only 3D points coordinates. Note that the same tendencies are obtained with hand-crafted features or with Siamese KPConv back-bone, but we prefer to show results with a network that takes into account the minimum information regarding changes. In practice, we compute criteria associated with the clustering quality and the pseudo-cluster distribution along the training process.

Clustering quality

The evolution of the clustering quality during training epochs is computed by comparing the pseudo-clusters obtained thanks to the k-means on deep features, and the real classes. More precisely, we compute the normalized mutual information (NMI) given by the following formula:

NMI(Y, Y C ) = I(Y, Y C ) H(Y )H(Y C ) (2)
where Y and Y C contain the probabilities p i , p Ci , of each label i = {1...N } associated with the true and pseudo-labels.

H is the entropy defined as:

H(Y ) = - N i=1 p i log 2 p i ( 3
)
and I is the mutual information, defined as:

I(Y, Y C ) = H(Y ) -H(Y |Y C ) (4)
Intuitively, the NMI is a measure of the information shared between two clusterings, i.e., in our case the clustering of deep features and real classes. If the NMI is equal to 0, the two clusterings are totally independent. On the opposite, if the NMI is equal to 1, there is a perfect correlation between the two clusterings, i.e., one of them is deterministically predictable from the other.

We present the evolution of the clustering quality along the epochs in Figure 4a by giving the NMI between the clustering and the real labels of Urb3DCD-V2 dataset. As can be seen, the clustering tends to get closer to real classes along with the training process. It seems to stabilize after 30-40 epochs. Let us remark that at the end of the training, the NMI is around 0.35. It is still far to 1, but the same trend was observed in DeepCluster training quality assessment by [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF]. In Figure 4b, we evaluate the number of reassignments of cluster from one epoch to the following using the NMI between the clustering of the two epochs. It seems that during the first epochs, there is an important evolution of the clustering, but the training rapidly converges to a rather stable clustering (N M I > 0.8). Again, the same tendency was obtained by [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF] for DeepCluster on ImageNet dataset.

Pseudo-cluster distribution

As for the pseudo-cluster distribution, we remind that, ideally, a pseudo-cluster contains only one real class, and a real class can be distributed into several pseudo-clusters. To measure the purity of a pseudo-cluster, we propose to investigate the entropy H (Equation 3) of each pseudo-cluster. If it is near 0, then the pseudo-cluster contains almost only one real class. However, if a pseudo-cluster is divided into several classes, the entropy is higher. In Figure 5 is given the pseudo-cluster distribution at epoch 10 and 50. Pseudo-clusters are sorted in increasing entropy values. First, as can be seen, there is an improvement between epoch 10 and 50. The area under the entropy curves (dotted points in Figure 5) is indeed smaller at epoch 50 (0.24 of mean entropy) than at epoch 10 (0.39 of mean entropy), meaning that entropy values are globally smaller. Then, after 50 epochs of training, 80% of the pseudo-clusters have a "purity level" greater or equal to 93%. These results confirmed the relevance of the proposed user-guided strategy to automatically map a pseudo-cluster onto the majority real class for the evaluation, as stated in the method description section (see Section 2.3).

After having studied the training behavior of the DC3DCD method, we will now compare it to the state-of-the-art on the testing set of both simulated and real datasets.

Results on simulated Urb3DCD dataset

Quantitative evaluation of DC3DCD on the simulated Urb3DCD-V2-1 dataset is given in Tables 1 and2. In these tables, we also recall supervised results for the sake of comparison. Let us first analyze DC3DCD results without hand-crafted features (two first lines of the bottom part of Tables 1 and2). As can be seen, results for both Siamese KPConv and Encoder Fusion SiamKPConv back-bones are rather low. Indeed, while requiring the same annotation effort, k-means algorithm trained on the same hand-crafted as the RF method proposed in [START_REF] Tran | Integrated change detection and classification in urban areas based on airborne laser scanning point clouds[END_REF] provides better results (cf. first line of middle part in Table 1). However, these results are interesting because the two experimented back-bones provide significantly different results. In particular, Encoder Fusion SiamKPConv ends up with a mIoU ch 1.5 times higher than Siamese KPConv. While in a supervised setting, the improvement of Encoder Fusion SiamKPConv was of 5 points of mIoU ch , in the unsupervised context the choice of the architecture seems even more crucial.

Then, when hand-crafted features are added to the input of the network, results are largely improved (cf. the two last lines of Table 1). While DC3DCD with Siamese KPConv architecture and hand-crafted features provides results comparable to the k-means algorithm, DC3DCD provide interesting results with both hand-crafted features and the Encoder Fusion SiamKPConv architecture. Indeed, in this configuration there is more than 15 points of mIoU ch of improvement compared to k-means. Furthermore, DC3DCD with this configuration is better than a fully supervised RF, and provides results comparable with fully supervised deep architectures trained on 2.5D rasterization of 3D PCs. Thereby, providing hand-crafted features is an important step in unsupervised settings. One possible interpretation is that the unsupervised version is very tricky to train in reason of the large number of possible local minima. Adding hand-crafted features probably helps the initialization to be closer to the global minimum.

Notice that the Encoder Fusion SiamKPConv in a weakly supervised setting provides rather low results given the higher annotation effort required (about 50,000 annotated points). Results with a batch size of 10 are not stable. This is explained by the fact that only one batch is seen per epoch, and the same learning rate scheduler as with a batch size of 2 is used. Thus, this training is more prone to fall in a local minimum. Even with a reduced batch size, leading to more stable results, we can see the benefit of using DC3DCD for the training of Encoder Fusion SiamKPConv network because the effort of annotation is lower. Weakly supervised methods with our proposed DC3DCD evaluated in 4 different settings: with Siamese KPConv (SKPConv) or Encoder Fusion SiamKPConv (EFSKPConv) architectures and with or without the addition of 10 hand-crafted features as input to the network. Veg. stands for vegetation; b. s. for batch size; i.f. for input features.

Two different examples are given for a qualitative assessment of the method in Figures 6 and7. As visible in Figure 7, main changes (e.g., new buildings or demolitions) seem quite well retrieved by the k-means and both DC3DCD configurations. However, when going more into details, some misclassifications can be seen on new building facades (Figure 6) or vegetation. For new building facades, a slight improvement over k-means is reached by DC3DCD, but it is still not perfect. The k-means technique has the same tendency as the RF method (see de Gélis et al. [2023]) and confuses small new buildings with new vegetation, surely because they have the same height as visible in Figure 6. As depicted in Table 2, main difficulties of the DC3DCD method concern vegetation growth and missing vegetation. Note that this was already the most difficult classes in the supervised context. The missing vegetation is almost always confused with demolition in DC3DCD with hand-crafted input features and the Encoder Fusion SiamKPConv architecture. This is even worse with the k-means and missing vegetation is never predicted with DC3DCD without hand-crafted input features. However, this make sense, since the 'missing vegetation' and 'demolition' classes are both negative changes. Surprisingly, mobile objects are quite well retrieved, especially for DC3DCD with hand-crafted input features and the Encoder Fusion SiamKPConv architecture (Table 2).

Results on real AHN-CD dataset

Concerning the real AHN-CD dataset, quantitative results on the manually annotated testing set are given in Table 3, and Table 4 for per class results. For comparison purpose, we also provide results of supervised methods. However, we recall that they have been trained on the semi-automatically annotated AHN-CD dataset containing several ground truth errors [de Gélis et al., 2023]. This explains lower results of the RF compared to the k-means which have been mapped onto real classes using the manually annotated set (as for DC3DCD method). As already observed with the simulated dataset, we can see that DC3DCD provides better results than the k-means algorithm. Figure 8 shows that main changes are well retrieved for both methods. However, in the k-means results, larger objects of the clutter class such as trucks are mixed up with buildings. There are also lots of misclassifications in unchanged vegetation and unchanged building facades (see region of interest in Figure 8f). As far as DC3DCD is concerned, unchanged vegetation is well classified. A few mistakes are visible in some 'new clutter' objects. We recall that this class is a mix of a lot of objects, from vegetation to cars or garden sheds, surely explaining why its classification score is lower. Complementary results on a larger AHN-CD testing tile are shown in Figure 9. The ground truth is given by the semi-automatic process detailed in de Gélis et al. [2023]. The mapping onto the real classes is performed using this ground truth for both k-means method and DC3DCD. As visible in this example, most of 'new clutter' class objects are omitted or mixed up with the new building class, also the demolition class is totally omitted by the k-means algorithm (Figure 9d). In the DC3DCD results in Figure 9e, clutter class seems better retrieved, even though it is not perfect implying the main differences with the ground truth (Figure 9g). In the areas of interest depicted by the black rectangles in Figure 9, we observe that DC3DCD seems to better adapt to the user context (i.e., by the ground truth defined by the user) than the k-means, even Top: supervised methods. In supervised settings, the training is performed on the semi-automatically annotated AHN-CD dataset containing some errors (see de Gélis et al. [2023]). Bottom: Weakly supervised methods with k-means and our proposed DC3DCD with Encoder Fusion SiamKPConv architecture and with the addition of 10 hand-crafted features as input to the network.

Improving DC3DCD with contrastive learning

As mentioned, the problem in an unsupervised setting is to train a network to extract appropriate features for a specific task. In a task involving comparison of similar and dissimilar data (like change detection task), the contrastive loss is often used to force the network to extract identical features for similar data. Therefore, an idea can be to force the network to predict similar features for unchanged areas. To test this principle, we propose to introduce the following contrastive term in the loss function:

L cont = 0.5 × y sim × F 2 CD with y sim = 1 if similar 0 else. ( 5
)
where F CD is the L 2 -norm of output features and y sim is the similarity term (set to 1 for unchanged points, and 0 elsewhere). Using this contrastive term in the loss aims at forcing to 0 change-related features in unchanged areas. To test this idea, we combine the contrastive loss in Equation 5 with the deep clustering loss (NLL using the pseudo-label) taking the mean, and train the Encoder Fusion SiamKPConv network since it gave the best results.

We first carried out experiments by taking the similarity y sim from the ground truth (as y sim is not available in practice, we first test the idea by taking real values of y sim ). Results were really interesting since, as visible in Tables 5 and6, DC3DCD reached 73.51% of mIoU ch without the use of hand-crafted features and 82.63% of mIoU ch with the use of hand-crafted features on Urb3DCD-V2-1 dataset. We recall that on this dataset and in a fully supervised setting, Siamese KPConv and Encoder Fusion SiamKPConv networks obtained 80.12% and 85.19% of mIoU ch respectively. Thus, the addition of the contrastive part allows meeting fully supervised results (in an ideal case where y sim is known).

This first experience validated the idea of using the contrastive loss. However in practice, y sim needs to be estimated.

To obtain the similarity y sim , we first used the significant changes given by Multi-Scale Model-to-Model Cloud Comparison (M3C2) or a binary thresholding of cloud-to-cloud (C2C) distance. Results are mitigated (see Tables 5 and6) since the best results obtained using M3C2 for y sim allow us to improve by only 2 points DC3DCD without hand-crafted input features. With hand-crafted input features, results are worsened when the contrastive term is added during the training (using y sim based on M3C2, obtained mIoU ch is 46.42%). Another idea is to rely on multi-task learning [Vandenhende et al., 2021, Zhang and[START_REF] Zhang | A survey on multi-task learning[END_REF]: a multi-task framework based on DC3DCD that jointly extracts mono-date features that can be used for similarity computation has been designed. As illustrated in Figure 10, we added decoders for mono-date semantic segmentation to the back-bone architectures to also obtain semantic segmentation of PCs. Both Siamese KPConv and Encoder Fusion SiamKPConv have encoders to extract mono-date features, therefore we just added a decoder taking as input these mono-date features instead of feature differences for Siamese KPConv for example. Thereby, we used the same idea as before to train the network but with two separate clusterings, performed on output features of the change decoder on one side, as in previous experiments, and on output features of decoders on the other side. This results in both change pseudo-labels and mono-date pseudo-labels which are used to modulate change encoder-decoder and mono-date encoders-decoders respectively. In practice, we shared trainable parameters between mono-date encoders and decoders. We trained first the semantic segmentation part and then apply a binary clustering (using k-means) on the nearest point mono-date features difference to obtain the similarity y sim used in the contrastive term of the change detection loss. Concerning, the number of pseudo-clusters for mono-date K mono-date , 4 and 500 have been tested (4 is the number of semantic segmentation classes in Urb3DCD-V2 dataset, 500 is considered as a sample large bound). While semantic segmentation scores, using the same user-guided mapping for mono-date semantic segmentation, are very promising Table 5: Quantitative evaluation of DC3DCD-V2 on Urb3DCD-V2 low density LiDAR dataset. Top: supervised methods. Middle: Weakly supervised methods with our proposed DC3DCD and DC3DCD-V2 with Encoder Fusion SiamKPConv architecture without the addition of 10 hand-crafted features as input to the network. Bottom: Weakly supervised methods with our proposed DC3DCD and DC3DCD-V2 with Encoder Fusion SiamKPConv architecture and with the addition of 10 hand-crafted features (i. f.) as input to the network.

(90.79% of mean of IoU (mIoU) on the 4 semantic segmentation classes of Urb3DCD-V2 with hand-crafted input features and K mono-date = 500), using the associated y sim still leads to unsatisfactory results (see Tables 5 and6). Indeed, when K mono-date is set to 500, we obtain 50.14% of mIoU ch (with hand-crafted features) which is better than with distance-based methods (M3C2 or C2C) but worse than without the contrastive part of the loss. Thereby, computing similarity from the nearest point mono-date features difference does not seem adapted. Two main reasons for this non-success can be advanced: i) the nearest point comparison is not optimal in occluded parts as well as in dense urban areas (which is the case for Urb3DCD datasets that are acquired on models of Lyon city center), and ii) the method predicts 500 different mono-date semantic classes (far more than existing real classes) and nothing forces that two clusters that are near in semantics (e.g., belonging to the same real class) are near in the feature space, leading to differences of features likely to be very high. To counterbalance this last point, we tested using only 4 mono-date pseudo-clusters, but results are even worse, probably due to the fact that the DeepCluster strategy to train a network required a number of pseudo-clusters greater than the number of real classes.

Qualitative assessment of these results is supported by Figure 7(g-h) and 11. When the similarity comes from the binary change ground truth, visual results really lookalike the multi-change ground truth (Figure 7h and11f). Qualitative results of multi-task learning are quite encouraging. Surprisingly, borders of 'missing vegetation' seems well retrieved, but the center is still confused with demolition.

All these experiments aim at evaluating the potential of contrastive losses to improve our unsupervised results. Results with the similarity y sim issued from ground truth are very promising since they reach comparable results than the fully supervised networks. However, the method is highly dependent on the quality of this binary change annotation, and in case of mitigated binary annotation, it worsens DC3DCD results. These first perspective experimentation are, to our opinion, encouraging to limit the annotation effort while preserving interesting results. Our future work will concentrate on the estimation of precise y sim .

Conclusion

In this paper, we proposed an unsupervised learning method based on the DeepCluster principle to tackle multiclass change segmentation in raw 3D PCs. Following the unsupervised training, we propose a user-guided mapping of pseudo-clusters to real class in order to better to fit to the use case. Given the experiments on both synthetic and real dataset, we saw the importance of the choice of an appropriate architecture to extract valuable change-related features. Also, guiding the network using hand-crafted input features along with 3D points coordinates is advocated. Using these recommended configuration, our proposed method, DeepCluster 3D Change Detection (DC3DCD), allows obtaining better results than a fully supervised traditional machine learning algorithm relying on hand-crafted features and to reach scores of fully supervised deep networks trained on 2.5D rasterization of PCs (i.e., the only existing models in the literature before this thesis). We further proposed to improve DC3DCD by introducing a contrastive loss leading to comparative results as fully supervised deep network (89.04% of mean of accuracy) in an ideal case where the similarity Bottom: Weakly supervised methods with our proposed DC3DCD and DC3DCD-V2 with Encoder Fusion SiamKPConv architecture and with the addition of 10 hand-crafted features (i. f.) as input to the network.

boolean used in the contrastive loss is faultless. However, there are still improvements to be made to find a right manner to obtain the similarity.

Figure 1 :

 1 Figure 1: Illustration of our proposed method: DC3DCD. It is trained by alternatively clustering deep features to match a pseudo-label to each point of PC 2. These pseudo-labels are used to optimize the back-bone trainable parameters. Algorithm 1 Fully unsupervised DeepCluster 3DCD training Initialize the back-bone trainable parameters θ for e ← 1 to E do Run mini-batch k-means to obtain centroids C on the whole training set Assign to each point of the training set a pseudo-cluster Replace parameters of the prototype layer by C Compute the weights W k considering pseudo-label distribution in the training set Training sample selection: random drawing considering W k for i ← 1 to I do Use L N LL (weighted by W k ) to modulate the back-bone trainable parameters (θ) considering pseudo-labels

Figure 2 :

 2 Figure 2: Back-bone architectures used in our experiments.

Figure 3 :

 3 Figure3: User guided mapping of predicted clusters to real classes. For the K predicted clusters, a mapping with the corresponding real class is performed by a user to obtain the final change segmentation of the PC. 5 mappings are provided for the sake of illustration. Segmenting the whole dataset requires K annotations only. This is far less than the millions of points that need to be annotated in order to build training and validation sets in a supervised setting.

A

  comparison with the only existing deep supervised methods is provided, namely Siamese KPConv [de Gélis et al., 2023], Encoder Fusion SiamKPConv [de Gélis et al., 2023], DSM-based deep learning methods (adaptation of Daudt

Figure 4 :

 4 Figure 4: Analysis of the behavior of DC3DCD during the training. The evolution of clustering quality (a) is given thanks to the NMI between the clustering and the real labels of Urb3DCD-V2 dataset. The NMI between the clustering at epoch t and the clustering at epoch t -1 gives the cluster reassignment (b).

Figure 5 :

 5 Figure 5: Ground truth class distribution in pseudo-clusters sorted by increasing entropy value at epoch 10 (a) and 50 (b). Each pseudo-cluster entropy is given by the dotted black curve.

Figure 6 :

 6 Figure 6: Visual change detection results on Urb3DCD-V2 low density LiDAR sub-dataset (area 1): (a-b) the two input point clouds; (c) ground truth (GT): simulated changes; (d) k-means results; (e) DC3DCD with the Encoder Fusion SiamKPConv architecture results; (f) DC3DCD with the Encoder Fusion SiamKPConv architecture and the addition of 10 hand-crafted features as input results.

Figure 8 :

 8 Figure 8: Qualitative results on the manually annotated sub-part of AHN-CD dataset: (a-b) PCs at date 1 and 2; (c) ground truth; k-means results (d) and errors (f); DC3DCD results (e) and errors (g) using the Encoder Fusion SiamKPConv architecture and the 10 hand-crafted features in input. Regions of interest specifically discussed in the text are highlighted with ellipses.

Figure 9 :Figure 12 :

 912 Figure 9: Qualitative results on the semi-automatically annotated AHN-CD dataset: (a-b) PCs at date 1 and 2; (c) ground truth; k-means results (d) and corresponding errors (f); DC3DCD results (e) and corresponding errors (g) using the Encoder Fusion SiamKPConv architecture and the 10 hand-crafted features in input. Regions of interest specifically discussed in the text are highlighted with rectangles.

Table 1 :

 1 Quantitative evaluation of DC3DCD on Urb3DCD-V2 low density LiDAR dataset. Top: supervised methods. DSM-based methods are adaptation of[START_REF] Caye Daudt | Fully convolutional siamese networks for change detection[END_REF] networks to DSM inspired by[START_REF] Zhang | Detecting building changes between airborne laser scanning and photogrammetric data[END_REF] and RF refers to Random Forests. Middle: Weakly supervised methods with k-means and Encoder Fusion SiamKPConv results using 7 training cylinders in the training and validation set (equivalent to about 50,000 annotated points). Bottom: Weakly supervised methods with our proposed DC3DCD evaluated in 4 different settings: with Siamese KPConv or Encoder Fusion SiamKPConv architectures and with or without the addition of 10 hand-crafted features as input to the network.

	A PREPRINT

Table 2 :

 2 Per-class IoU scores of DC3DCD on Urb3DCD-V2 low density LiDAR dataset. Top: supervised methods.

DSM-based methods are adaptation of

[START_REF] Caye Daudt | Fully convolutional siamese networks for change detection[END_REF]

networks to DSM inspired by

[START_REF] Zhang | Detecting building changes between airborne laser scanning and photogrammetric data[END_REF]

and RF refers to Random Forests. Middle: Weakly supervised methods with k-means and Encoder Fusion SiamKPConv results using 7 training cylinders in the training and validation set (equivalent to about 50,000 annotated points). Bottom:

Table 3 :

 3 Qualitative assessment of DC3DCD on the manually annotated sub-part of AHN-CD dataset. Top: supervised methods. DSM-based methods are adaptation of[START_REF] Caye Daudt | Fully convolutional siamese networks for change detection[END_REF] networks to DSM inspired by[START_REF] Zhang | Detecting building changes between airborne laser scanning and photogrammetric data[END_REF] and RF refers to Random Forests. In supervised settings, the training is performed on the semi-automatically annotated AHN-CD dataset containing some errors (see deGélis et al. [2023]). Bottom: Weakly supervised methods with k-means and our proposed DC3DCD with Encoder Fusion SiamKPConv architecture and with the addition of 10 hand-crafted features as input to the network.

	Method

Table 4 :

 4 Per class IoU DC3DCD results on the manually annotated testing part of AHN-CD dataset given in %.

Table 6 :

 6 Per class quantitative evaluation of DC3DCD-V2 on Urb3DCD-V2 low density LiDAR dataset. Top: supervised methods. Middle: Weakly supervised methods with our proposed DC3DCD and DC3DCD-V2 with Encoder Fusion SiamKPConv architecture without the addition of 10 hand-crafted features as input to the network.

	Per class IoU (%)

We build upon DeepCluster[START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF] to tackle the change segmentation task in 3D PCs. To do so, we experiment our model with several 3D PCs change segmentation architectures.

Acknowledgements

This research was funded by Magellium, Toulouse and the CNES, Toulouse. This work was granted access to the HPC resources of IDRIS under the allocation 2022-AD011011754R2 made by GENCI.

though the same ground truth-guided mapping step has been performed. Indeed, here buildings are not set as new in the ground truth and in DC3DCD, conversely to k-means. Finally, on this tile, if we compare to the ground truth, DC3DCD obtains 55.91% of mIoU ch , while the k-means only 24.63%.

Discussion

In this section, we have proposed an unsupervised change detection method with a weakly user-guided mapping to real classes providing interesting results. This problem is still open and complex and in the following, we point out some observations and discussions about possible improvements.

Importance of network's architectures and input features

We saw in the result section that the choice of the back-bone architecture and the addition of hand-crafted features as input along with 3D point coordinates are crucial. This is in agreement with the original publication of DeepCluster, where authors provided gradient of images as input to obtain interesting results [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF]. These results in an unsupervised context also emphasizes conclusions of de Gélis et al. [2023] on the necessity of applying convolution on features difference. To explain this, let us note that the unsupervised context is a largely unconstrained problem. While the annotation allows counterbalancing architectures weaknesses, this is indeed no longer possible for the unsupervised setting. Thereby the choice of an architecture that more specially extracts change-related features through convolutions of difference of features from both inputs at multiple scales, and the addition of well-designed hand-crafted features, allows guiding the training of the network toward a relevant minimum, leading to a reliable change segmentation.