Image segmentation is a fundamental problem in computer vision, with applications ranging from medical
imaging to object recognition. Traditional neural network models, such as CNNs, require large amount of labeled data and extensive computational resources to perform image segmentation. In contrast graph-cut based
segmentation can perform one-shot segmentation and
also handle multi-label segmentation. In this project,
we explore graph cut algorithm to perform multi-label
segmentation.The code is available on GitHub


# Dynamic Hybrid Algorithms for MAP Inference in Discrete MRFs


## Objective

In this project, we implemented the following:

- Reimplementation of the max-flow/min-cut algorithm and comparison of our implementation against networkx and pymaxflow python modules.
- Multi-label segmentation with α-expansion.
- Comparison of performance with different pairwise and unary costs.
- Graph recycling to improve computational efficiency.
- Extensions: interactive binary (background/foreground) and multi-label segmentation.

## Problem Formulation

### Graph Cut and Energy Minimization

The image segmentation problem can be expressed as an energy minimization problem, where images are represented as a directed graph $ G = (V, E) $. $ V $ is the set of vertices corresponding to the image pixels, and $ E $ represents the edges. We consider a 4-connected neighborhood, where each pixel is connected with its right, left, above, and below neighbors (except on the edges). These connections are represented by the edges. If we denote by $ \mathcal{L} $ the set of labels, $ n $ the number of pixels, and $ x \in \mathcal{L}^n $ a possible labeling, we would like to minimize an energy $ E: \mathcal{L}^n \to \mathbf{R} $ that maps any possible labeling to a global cost.

The energy function typically adopted in computer vision, and considered herein, is expressed as a sum of unary $ \phi_i $ and pairwise $ \phi_{ij} $ potential terms:

$$
E(\mathbf{x}) = \sum_{i \in V} \phi_i(x_i) + \sum_{(i,j) \in E} \phi_{ij}(x_i, x_j).
$$

The **unary potential** $ \phi_i(x_i) $ acts as a data fidelity term. It represents the cost of assigning a pixel to a label. Conversely, the **pairwise potential** $ \phi_{ij}(x_i, x_j) $ enforces spatial coherence by penalizing label differences between neighboring pixels.

We detail the different unary potentials we considered in Section [Unary Potential](#unary-potential). For the pairwise potentials, we restrict ourselves to potential models like the Potts model with $ \gamma = 200 $.

The Potts model is defined as:

$$
\phi_{ij}(x_i, x_j) =
\begin{cases}
\gamma & \text{if } x_i = x_j \\
0 & \text{otherwise}
\end{cases}
$$

### α-expansion Algorithm

Since most multi-label energy functions are not submodular, proposed algorithms only focus on finding approximate or partially optimal solutions. In this project, we reimplemented the α-expansion algorithm. At each iteration, we choose a label and apply graph cut to find the optimal expansion that decreases the energy. At each iteration, we consider a binary sub-problem and separate the pixels between being labeled as α or keeping their old label. To do so, we construct a new graph at each iteration, introducing two additional nodes, the **source (α)** and **sink (ᾱ)**, as well as auxiliary nodes. The weights of the edges represent the unary and pairwise costs. We then compute the maxflow, and each node is assigned a label depending on the partition of the mincut it belongs to (label as α if it belongs to the source partition and keep the old label otherwise). We perform these expansion moves until the energy stops decreasing.

### Max-flow/Min-cut with Ford-Fulkerson Algorithm

We used the Ford-Fulkerson algorithm to calculate the maxflow from the source $ s $ to the sink $ t $ and find the minimum S/T-cut.

**Algorithm:**

1. Initialize flow $ f(u,v) = 0 $ for all edges.
2. While there exists an **augmenting path** from source $ s $ to sink $ t $ in the residual graph:
 - Find an augmenting path using BFS.
 - Compute the minimum residual capacity along the path.
 - Increase flow along this path by this capacity.
 - Update the residual capacities:
 $$
 c_f(u,v) = c(u,v) - f(u,v) \quad \text{and} \quad c_f(v,u) = f(u,v) \quad \text{(reverse flow)}
 $$
3. Repeat until no more augmenting paths exist.
4. Find the edges that have no residual capacity and are thus part of the cut.

For the project, we reimplemented the max-flow algorithm from scratch using only basic Python libraries like numpy. We then compared our performance against other libraries like pymaxflow, which is a Python wrapper for the C++ library, and networkx. We compared both the execution time and the maxflow value to ensure the correctness of our implementation for multiple node numbers, keeping the same type of 4-connected network.

While our implementation consistently produced correct max-flow values, it exhibited significantly slower execution times compared to the other libraries. For instance, processing a graph with 20,000 nodes required over six minutes, making it unsuitable for practical use, even for low-resolution images (e.g., $ 256 \times 256 \approx 65,000 $ nodes), which would entail prohibitively long runtimes.

Consequently, for the remainder of the project, we utilized `pymaxflow` due to its high efficiency stemming from its underlying C++ implementation. This performance limitation illustrates one of the challenges we encountered when developing graph algorithms in high-level interpreted languages such as Python.

## Results

One of the difficulties we encountered was finding the proper unary and pairwise costs that yield good quality segmentation.
<figure id="fig:test">
 <img src="images/cow_convergence_3l.png" style="width: 300px; display: block; margin: 0 auto;">
 <figcaption style="text-align: center;"> Result of the alpha-expansion on a cow </figcaption>

</figure>



### Unary Potential

We evaluated different formulations for the unary potential:

- **Semi-automatic approach:** Using the k-means clustering method, we computed histograms in the pixel space for each label. These histograms were then modeled as Gaussian distributions, which were used to define the corresponding unary terms.
- **L2-based potential:** Given the reference colors of each label, we computed the L2 norm in a color metric space between the assigned label colors and the actual pixel colors. Initially, this was performed in the standard RGB space. However, a limitation of the RGB space is that perceptually similar colors may not be close in Euclidean distance. To address this, we experimented with an alternative metric space that accounts for perceptual color differences: the CIELAB color space.

The results of the L2 norm in RGB and CIELAB spaces are promising. Applying the L2 norm in both RGB and CIELAB spaces improved segmentation accuracy, successfully identifying structural elements such as the cow's legs. The CIELAB-based unary potential further enhanced segmentation, even correctly identifying the cow’s horns.

However, increasing the number of labels introduced more noise. As a consequence, parts of the cow’s back and some regions of the grass were misclassified. These findings highlight the sensitivity of color-based segmentation using graph cuts to input parameters, unary potential formulations, and hyperparameter tuning, emphasizing the importance of proper scaling and term weighting.

### Energy Minimization with Graph Recycling

To enhance the efficiency of energy minimization, we implemented the graph recycling algorithm. Following the approach introduced by Kovtun, the method aims to reduce the number of unknown variables by solving a set of auxiliary binary problems $ P_m $, one for each label $ l_m \in \mathcal{L} $. This strategy allows partial labeling of the image before applying more computationally intensive multi-label optimization. We used the same unary potential as defined in the original article.

**Graph Recycling Algorithm:**

1. Initialize all pixels as unlabeled ($ \epsilon $).
2. For each label $ \alpha \in \mathcal{L} $, solve the binary subproblem:
 - Assign label $ \alpha $ to pixel $ i $ if $ x_i^\alpha = 1 $.
3. Update unary potentials for remaining unlabeled pixels and apply α-expansion on this subset.

After the recycling step, the majority of pixels are already labeled, significantly reducing the number of variables requiring optimization during the subsequent α-expansion phase. This leads to a substantial reduction in computational complexity while maintaining segmentation quality.

## Interactive Image Segmentation

We implemented an extension of our previous work where we allow user interaction and used pairwise costs based on pixel value instead of only pixel labeling.

At the beginning, the user must indicate with a small brush some pixels that belong to the background ($ \mathcal{B} $) and others that belong to the foreground ($ \mathcal{F} $). These pixels, named seeds, will be linked to the terminal nodes, which represent background (the sink) and foreground (the source). We implemented a simplified version where only seeds get strong unary costs. The pairwise cost between two pixels $ p $ and $ q $ was defined as $ V_{\{p,q\}} = \frac{1}{1 + \| I(p) - I(q) \|} $ where $ I $ maps a pixel to its color value and $ K = 10^9 $.

We compute the maxflow and find the min-cut to assign the labels. Nodes that belong to the source partition will be labeled as foreground and background otherwise.

We also extended this method to multi-label segmentation.

As the interactive segmentation was only an extension of our model, we implemented a simple model which could benefit from more complex unary costs that also take into account non-seeds pixels.

## Conclusion

We successfully applied the α-expansion algorithm and graph recycling strategies to perform multi-label segmentation within a reasonable computational time.

In this work, we adhered to the same qualitative evaluation criteria as defined in the original study. Commonly used image segmentation datasets are primarily designed for object segmentation tasks, which rely on complex priors and high-level semantic cues, thereby requiring more than color-based energy terms alone. Consequently, when such datasets are used in the context of purely color-based segmentation, the resulting masks often encompass large, semantically inconsistent regions that do not correspond to any meaningful object boundaries. Finding a dataset that encompasses these color priors constitutes an interesting and valuable direction for future research.

Furthermore, we encountered significant challenges in the definition and tuning of the unary and pairwise cost functions. These terms are inherently image-dependent and lack intuitive parametrization, which often led to suboptimal visual segmentations. Systematic approaches for estimating these parameters merit further investigation.

Re-implementation of Dynamic Hybrid Algorithms for MAP Inference in Discrete MRFs


The paper "Fast Learning of Signed Distance Functions from Noisy Point Clouds via Noise to Noise Mapping" introduces a novel framework that circumvents the need for clean data by leveraging a noise-to-noise mapping strategy. Instead of relying on ground truth supervision, the method utilizes multiple noisy observations to statistically infer the underlying geometry. This is achieved by formulating a denoising function that pulls noisy points toward the estimated surface, and by employing Earth Mover’s Distance (EMD) as a metric to measure the discrepancy between different noisy observations. Furthermore, the integration of multi-resolution hash encodings allows for a dramatic acceleration in training, achieving significant improvement over conventional methods. The authors proposed multiple use-cases such as multi-view reconstruction, point cloud denoising, upsampling, and surface reconstruction.

In our work, we studied the aforementioned paper in detail and sought to replicate its core ideas in a simplified setting. Although the authors propose several applications, including multi-view reconstruction, point cloud denoising, upsampling, and surface reconstruction, we will focus exclusively on surface reconstruction, as it directly aligns with the core principles of the proposed method. Due to resource constraints and for the sake of clarity in visualization and experimentation, our implementation is focused on a two-dimensional (2D) scenario rather than the full three-dimensional (3D) setup presented in the original paper. While the 2D data does not capture the full complexity of 3D point clouds, it retains the essential challenges of noise and the need for robust surface extraction. By implementing the noise-to-noise mapping approach in 2D, we aim to validate the effectiveness of the core concepts and establish a foundation for future extension to 3D data.

- Reimplementation of the original paper’s multi-resolution hash encoding and proposed loss function.
- Comparison of the proposed method with a simpler model, specifically a neural network with a sine activation function.
- Evaluation of model performance under constrained conditions, including increased noise and reduced input data.
- Application of the model to 3D samples.



Reimplementation of Fast Learning Signed Distance Functions from Noisy 3D Point Clouds via Noise to Noise Mapping

We modeled  the Synthetic Aperture radar with Gaussian processes. You can find the [report](https://github.com/gardiens/Inverse_Problem/blob/main/SAR_report.pdf)




Modelisation of Synthetic Aperture Radar

Our work focused on creating a colored mesh (mesh) from various satellite images of a location. The approach we followed extends the work done in the course's tutorials: taking pairs of images, (i) rectifying them, (ii) calculating their disparities (stereo-matching), and triangulating the 3D positions associated with each pixel to construct (iii) a point cloud or (iii') a 2.5D elevation map by flattening these points onto a grid.
The first method involves forming the mesh's triangles based on the connectivity in the initial image. We know the xyz coordinates of each pixel in image 1, for which we found the equivalent in image 2 (allowing us to triangulate its position). For each triplet of neighboring pixels in the image (e.g., at coordinates $(i,j)$, $(i+1,j)$, and $(i,j+1)$ for any $i$ and $j$), we can connect the corresponding xyz points (provided we have found the xyz coordinates of all three pixels). The second method performs a similar operation but relies on 2.5D Digital Elevation Models (DEMs) calculated at the end of the previous tutorial. The mesh coloring is achieved through z-buffering or rasterization by projecting each point of the cloud onto the scene's images. In both methods, we can construct a mesh from a single pair of images or multiple pairs by fusion. Additionally, using Multi-Spectral Images in addition to our initial grayscale images, we colored the meshes in RGB.



# Satellite Imaging: Construction of a 3D Mesh from Satellite Images of Urban Scenes
ddition to our initial grayscale images, we colored the meshes in RGB.

## Bibliography

The tutorials followed are from the course *Remote sensing data: from sensor to large-scale geospatial data exploitation*, following the S2P pipeline [1], and the approach described in [2]. To compare with the developments in this report, we tested a standard mesh construction method from a point cloud. Using the software [Cloud Compare](http://www.cloudcompare.org/) (seen in our point cloud course), it is possible to construct a mesh through Poisson surface reconstruction, as shown in Figure 1. This method relies on estimating normals at each point, calculated here using the 50 nearest points to each point.


### Other Recent Methods, via NeRF or 3D Gaussian Splatting

The success of NeRF [3] and 3D Gaussian Splatting [4] methods for generating new views of a scene opens possibilities for processing satellite images for environment reconstruction. Approaches like Sat-Mesh [5] and EO-Nerf [6] adapt NeRFs to satellite images, obtaining much higher quality results than the methods studied in this report, but at a much slower pace. In the Point Cloud course project (NPM3D), we studied Point-NeRF [7], one of the papers aiming to address the limitation of NeRFs and Gaussian Splatting: the need to reoptimize independently for each scene. The idea of Point-NeRF [7], MVS NeRF [8], and MVS Gaussian [9] is to pre-train a model to generate an initial representation of a scene, followed by per-scene optimization. A new scene can thus be processed much faster. MVS-Gaussian [9] claims to process a scene in less than a minute; however, their approach seems limited to generating views at angles close to the provided images' views (whereas the goal for satellite images is to generate views from the ground, perpendicular to the satellite views). These approaches rely on a deep network for Multi-View Stereo (MVS). Point-NeRF [7] deduces a point cloud and attaches a feature vector to each point via a 2D CNN on the images. The ray marching rendering network is also pre-trained since it is local (relying on the feature vectors of points near the ray) and not global (a single large MLP per scene). Pixel Splat [10] is another approach that pre-trains a network to quickly process a new scene via splatting. These methods seem particularly suited for satellite imagery, as processing a vast geographical area (e.g., an entire city) involves dividing the area into scenes with very similar local compositions. Thus, the pre-trained ray marching network should quickly yield good results for each scene. The point cloud construction can be done as learned during our course (whereas 3D Gaussian Splatting relies on [Colmap](https://colmap.github.io/)).

## Method 1 - Connectivity in the Image

The first implemented method is illustrated in Figure 2, with results shown in Figure 3. Stereo vision, as seen in the course, constructs a disparity map between two images. From this matrix, we triangulate the positions of pixels from image 1 for which we found the equivalent in image 2. By masking pixels for which we could not construct the corresponding point, we obtain a matrix as shown in Figure 2a. The idea is to connect triplets of neighboring pixels. Three neighboring pixels on the image have a good chance of belonging to the same surface element (building, tree, car, etc.), except at the border between two elements (see problem in image 3b). Thus, we initially pave the matrix with triangles, avoiding missing pixels, as shown in Figure 2c and result 3a. We also retrieve the colors of the points, associating pixels (matrix values, i.e., the image) with points. We then filter the triangles based on two rules: (1) Taking the longest edge of a triangle as its representative length, we filter out triangles with representative lengths 5 times greater than the median of the representative lengths. (2) We calculate a normal for each triangle $(A,B,C)$ via the cross product $BA \otimes CA$ and the incidence angle of the image. We then calculate the angle between the triangle's normal and the image's normal. If the angle is greater than 88° (or less than 88°), we consider it too close to perpendicular (90°). A triangle perpendicular to the image's incidence angle has a high risk of being an aberration. Unfortunately, this leads to a defect in this first method: the mesh is very patchy, especially on the rear facades of buildings. For an order of magnitude, in the example of image 3b, the number of triangles decreases from 563,040 to 555,461 after filtering by size, then to 541,915 after filtering by the normal's angle; see image 3c after filtering and images 3d and 3e for two colored viewpoints.



### Using Multiple Images

This method relies exclusively on the image for which we calculated the disparity map with another, so we cannot use multiple images in the mesh construction. However, as suggested by Gabriele Facciolo during the oral presentation of our work, we can superimpose meshes obtained from different image pairs. After a first attempt, we noticed that this superimposition partially addressed the issue of missing facades. The xy coordinates of the different point clouds are fairly well-aligned, but the z (or h) coordinates are not, as the elevation is relative (see image 4a). To roughly align the different meshes, we subtract the mean elevation of each mesh from the elevation of each point in that mesh, as shown in result 4b. The xy coordinates are fairly well-aligned, but this is not perfect, and we observe a spreading of the buildings (see image 4c). To limit the spreading, we can restrict the number of image pairs used, as shown in image 4d using only pairs relative to the same image. The results obtained by this method have the advantage of a dense point cloud and thus better resolution than Method 2. However, the combination of multiple meshes would need improvement (in essence, Method 2 aims to combine point clouds by projecting points onto an elevation grid). Despite superimposing all selected image pairs (see details below), many facades remain missing, especially on the central tower of the scene. We, unfortunately, use images with roughly the same view of the scene, seeing the same facades. We also notice noise in the mesh, more visible with the superimposition of multiple meshes and some aberrations in the air.



### Details on the Method

- For each square of coordinates $(i,j)$, $(i+1,j)$, $(i,j+1)$, and $(i+1,j+1)$, if none are missing, we have two choices for constructing the pair of triangles that will pave the square: either $<p_{(i,j)}, p_{(i+1,j)}, p_{(i,j+1)}>$ with $<p_{(i+1,j)}, p_{(i+1,j+1)}, p_{(i,j+1)}>$ or $<p_{(i,j)}, p_{(i+1,j)}, p_{(i+1,j+1)}>$ with $<p_{(i,j)}, p_{(i+1,j+1)}, p_{(i,j+1)}>$ (where $p_{((a,b))}$ is the point in the cloud associated with pixel $(a,b)$). To decide, we calculate the length of the two diagonals of the square: $d_0 = ||p_{(i,j)} - p_{(i+1,j+1)}||_2$ and $d_1 = ||p_{(i+1,j)} - p_{(i,j+1)}||_2$. We keep the pair of triangles that gives the smallest diagonal (see `technique1.py` line 87).
- All triangles are oriented clockwise so that all faces are rendered with the same shading.
- Our implementation is not specific to a set of images, and at the beginning of our Jupyter Notebook, you can choose between the Tokyo scene from TP7 and the IARPA images from Argentina from previous TPs. However, we focused our tests solely on the IARPA images. To work with images of the same luminosity (so that stereo matching works), we first tried filtering the images based on the attributes "NITF_USE00A_ROLL_ANG" and "NITF_CSEXRA_SUN_AZIMUTH". Following our supervisors' advice, we focused on the images from December 18, 2015, corresponding to numbers 37 to 42 (sorted by acquisition date). Image 40 did not fully cover the area (or we could not crop it with the aoi), so we removed it. Thus, we worked with 5 images, resulting in 10 different pairs. For versions with a single pair, we used pair (37,38).
- To obtain RGB colored meshes instead of grayscale, we perform pansharpening. On the IARPA images, in addition to high-resolution images, we recovered lower-resolution but multi-spectral MSI images (which also explains our focus on the IARPA scene in Argentina). The implementation is in the file `utils_color.py` and follows a tutorial sent by our supervisors: (i) Converting WorldView-3 spectra to RGB colors, then (ii) zooming via Fourier transform, and finally (iii) combining with high-resolution images (in grayscale). Note: the crop of aoi between the high-resolution image and the corresponding MSI is adjusted via a dictionary of differences, the `dict_diff` introduced in `rectification.affine_crop`. Results are shown in Figure 5.
- The display of meshes is done with MeshLab software, with shaders disabled. Our supervisors showed us how to use MeshLab to increase the resolution of a mesh, but we did not use these features. This choice is partly due to time constraints and partly to maintain clarity regarding our implementations and results. Improving the mesh through refinement would be additional work beyond what we have done.
- A minor detail regarding MeshLab: to avoid mesh flickering during display, we recentered the xyz coordinates of the mesh (by subtracting a random point). This is necessary because MeshLab stores coordinates in absolute terms, not relative, and with too few bytes. The x and y values hover around $3 \times 10^5$ and $6 \times 10^6$, respectively, but vary only slightly between points. Without recentering, the coordinates are rounded due to insufficient bytes, causing points to jump between displays.


## Method 2 - Connectivity in the Elevation Map

The results of the second method are shown in Figure 6. This method uses 2.5D DEMs, elevation maps produced at the end of the previous tutorial. These maps are calculated by projecting the points of the cloud onto a grid along the elevation axis. This method naturally allows combining multiple image pairs. (1) The first possible fusion consists of assembling all points into a single large cloud and then constructing the DEM of this cloud. (2) The second fusion, the chosen one, consists of taking the median of the elevation maps (nanmedian to fill gaps), as shown in Images 6a to 6e (ignore the color scales). The resulting DEM is a matrix with elevation values at the grid coordinates and missing values. We can then apply the tool developed for the first method (literally the same function, with the same details) to construct the mesh, with the advantage of being able to fill gaps in the elevation map through interpolation. We use Neumann interpolation, as shown in image 6f for the interpolated DEM. Additionally, we do not need to filter the mesh (by size or normal angles). Thus, we obtain a mesh without holes.


### Colorization by Rasterization

Unlike the first method, the matrix used to construct the mesh is not the image but the elevation map (in practice, we only use the coordinates of the points corresponding to each index and the missing cells), with the significant drawback of not having a color for each point. Colorization is achieved through rasterization on any image. This step can be performed independently on multiple images, combining the colors afterward.


- Given an image (not necessarily one used to generate the mesh), we use the RPC to project all points of the cloud onto the pixels.
- A point in the shadow of another (e.g., the hidden facade of a building) is not visible in the image, so the found pixel does not belong to it. To color only the points visible in the image, we tested two solutions: z-buffering and rasterization. Since z-buffering was not conclusive, we abandoned it (see the code `technique2.OLD_project_color`).
- **Rasterization** (illustrated in Figure 7): In the order of depth (following the image's incidence angle), we rasterize the triangles. Rasterization involves coloring the points included in each 2D triangle (based on the coordinates projected onto the image), superimposing the triangles one by one. For an efficient implementation, we use `rasterio`. We thus obtain a collage of triangles covering the coordinates of the image's points. A point in the cloud hidden by a triangle of which it is not a vertex is not colored.

### Colorization with Multiple Images

Rasterization on an image colors the points visible in that image. To aid understanding, we represent uncolored points in purple. Image 8a is a top-down view of the colorization obtained by projection onto image 37, and image 8b is colored by image 42. By taking the maximum of the colors of each point, we can cover the uncolored areas, as shown in image 8c. Taking the maximum ( rather than the average) helps to brighten the shaded areas. Thus, by multiplying the colorizations, we reveal the shaded areas left by the sun. For example, in image 8a, 24,614 points are colored (out of

Satellite Imaging, Construction of a 3D Mesh from Satellite Images of Urban Scenes


Gaussian splatting is an innovative approach to scene rasterization, utilizing Gaussian functions as input primitives instead of traditional geometric representations like polygons or voxels. Departing from conventional rendering techniques, this method projects 3D Gaussian distributions directly into 2D space as smooth, continuous blobs. This process significantly enhances rendering efficiency, providing smoother visual outputs while achieving substantial speed improvements by allowing for parallelized computing. These advantages position Gaussian splatting as a promising technique for real-time applications such as augmented reality, virtual reality, and video games, where achieving low-latency rendering is of paramount importance.

In this work, we review existing methods for rendering 3D scenes from multiple views. We analyze the techniques presented in the original 3D Gaussian Splatting paper and highlight its limitations and potential extensions.



## Contribution
- **Under-represented viewpoints**: Missing viewpoints in the scene result in holes in the 3D reconstruction (see Section~\ref{section:limitation-black}). We addressed this by using generative image techniques to fill in these gaps (see Section~\ref{section:extension-black-patches}).
- **Rendering boundaries and discontinuities**: 3D Gaussian Splatting struggles to accurately render sharp boundaries and discontinuities.
- **View artifacts and chromatic aberrations**: Artifacts and aberrations appear under certain angles (see Section~\ref{sec:view-artifacts}). To mitigate this, we experimented with adding noise and adjusting the degree of spherical harmonics .
- **Depth regularization**: We introduced depth information to the input images to regularize the training process and improve results .
- **SfM solver comparison**: We compared more extensively than the original paper the performance of two SfM solvers, GLOMAP and COLMAP, to evaluate their impact on Gaussian Splatting .

## Related Works
Prior to the emergence of Gaussian splatting, two primary approaches dominated the synthesis of novel views from input images: Neural Rendering and Radiance Fields (e.g., NeRF), and Point-based Rendering.

### Point-Based Rendering
Point-based methods efficiently render disconnected geometric samples by computing a point cloud. Each point represents a shape that spans more than a pixel, such as circular or elliptical representations. While faithful to the underlying data, point samples suffered from discontinuities and visible holes. There have also been efforts to augment points with neural features to enhance rendering. Although these methods share similarities with the foundational ideas of Gaussian splatting, they lacked a ready-to-use, fast rendering algorithm like the one proposed in the initial Gaussian splatting paper.

### Neural Rendering and Radiance Fields
Deep learning methods for novel-view synthesis were adopted early, with CNNs used to estimate blending weights. Then, Neural Radiance Fields (NeRF) introduced techniques like importance sampling and positional encoding to enhance quality but relied on large networks, which significantly impacted computational speed. The success of NeRF spurred an explosion of follow-up methods, with MiP-NeRF360 representing the state of the art at the time. While achieving impressive rendering quality, these methods required extensive training and relied on computationally expensive sampling during rendering.

To address these limitations, Instant NGP introduced hash grids and occupancy grids to accelerate computation. Similarly, Plenoxels leveraged a sparse voxel grid to interpolate a continuous density field. These approaches were the primary solutions for engineers prior to the publication of the 3D Gaussian Splatting method. The 3D Gaussian Splatting approach further improved on these techniques by offering significantly faster training and rendering times compared to traditional NeRF methods.

## Target Applications for this method
This method is applicable to various domains aiming to generate 3D scenes from images. For instance, gaming and virtual reality, where 3D Gaussian splatting enhances the rendering of complex environments. Its ability to handle large-scale 3D data at real-time speeds with smooth transitions between objects and surfaces makes it ideal for immersive experiences, such as VR simulations or augmented reality interfaces, where responsiveness and visual fidelity are critical.

Another significant application lies in autonomous systems and robotics, where 3D Gaussian splatting can be used for real-time scene reconstruction and mapping without any need for heavy sensors. Moreover, in medical imaging, this technique can help with novel Computed Tomography projections, but it should be noted that applying SfM to computed tomography images is especially challenging.

There are many uses for this technique in digital twins, where high-precision 3D duplicates of real-world objects are required for simulation in real-time tasks.

## Method
### Gaussian: a building block of 3D Gaussian 

The fundamental building block of this paper is the 3D Gaussian. One of
the key properties of Gaussians is that 3D Gaussians can be projected
and rendered as 2D Gaussians. Each gaussian will
be represented with a covariance matrix $\Sigma$, a mean $\mu$, an
opacity $\alpha$ and colors:
$$\mathcal{G}(x)=exp(-1/2(x)^{T}\times \Sigma^{-1}(x))$$

The corresponding 2D Gaussian for rendering is a Gaussian with
covariance $\sigma'$ given by : $$\sigma'= JW\Sigma W^T J^T$$ with the
corresponding Jacobian J of the projective transformation and W the
viewing transformation. Opacity $\alpha$ and colors will be used later.
### Storing RGB value for every Gaussian

To encode color information, each Gaussian stores view-dependent RGB
values using spherical harmonics along with an opacity value, $\alpha$.
\"Spherical harmonics\" are a widely used method for
representing colors on 3D objects, allowing the color to vary depending
on the camera's viewpoint.

Mathematically, we store the spherical harmonics up to a maximum degree
$l_{max}$. If we denote the view direction of point $i$ in image $j$ as
$v_{i}^{j}$ Then the color of the point is
given by :


### Rendering

To determine which pixels a Gaussian in 3D space will impact, we compute
its projection onto the 2D image plane. For a Gaussian and an image $j$,
its projection $p_{ij}$ is calculated in 2D space, along with its 2D
covariance matrix $\sigma'$. If the projection falls within the image
boundaries, we calculate a rectangle based on the eigenvalues of the
covariance matrix $\sigma'$. This rectangle defines the region of the
image influenced by the Gaussian during rendering.\
Since multiple Gaussians can influence the same pixel in a 2D image, it
is necessary to introduce a parameter to control how these Gaussians
interact in the pixel space. To address this, the authors included an
$\alpha$ parameter, which determines the contribution of each Gaussian
to the final color of the pixel.



### Rasterization and backpropagation

Since 2D images must be generated repeatedly from the 3D scene, a fast
algorithm for rasterization is essential. The main goal is to balance
quality with speed while maximizing the parallelization of the rendering
process. In the original paper, the authors divided the 2D screen into
$n \times n$ tiles and retained only the Gaussians likely to fall within
the view frustum. For each tile, they processed every pixel within it,
sorting the Gaussians by depth and accumulating the color and alpha
values depth-wise (from front to back). The process stops once the
accumulated alpha value in a pixel reaches a saturation threshold
$\alpha$. Unlike traditional ray tracing methods, this approach does not
rely on sampling and uses saturation as the sole stopping criterion.

In the backpropagation step, the per-pixel loss must be converted into
the 3D Gaussian space. For each tile, the process starts with the last
Gaussian that affected any pixel. Each pixel then tests and processes
Gaussians whose depth is less than that of the last contributing
Gaussian. This approach enables direct differentiation, ensuring
efficient gradient computation.


## Limitation 
### "Holes" Due to Missing Camera Views
A notable limitation of Gaussian splatting is the appearance of "holes," rendered as black patches in regions not observed by the training camera. Since Gaussian splatting relies on information from multiple viewpoints to reconstruct the scene, areas outside the field of view of the training images lack the necessary data to generate accurate visual representations. Consequently, these regions remain undefined or are rendered as black patches, as the algorithm cannot infer color or texture without sufficient spatial information. This limitation underscores a fundamental challenge in 3D reconstruction and view synthesis: the output quality is heavily dependent on the completeness of input camera coverage during training, with no extrapolation from other parts of the scene.

In practice, these missing regions could provide an important signal to users, highlighting areas where additional camera views are required. Identifying such gaps could prompt users to capture supplementary imagery, thereby improving the reconstruction.
![alt text](images/sky_box.PNG "Initial fine views")


### Difficulty Rendering Boundaries and Discontinuities
The Gaussian splatting algorithm also faces challenges in handling discontinuities and boundaries, particularly at the edges between objects. These discontinuities are common in scenes with sharp transitions between objects or materials, where the smooth, probabilistic nature of Gaussian splatting fails to accurately capture abrupt changes in geometry or color.

A plausible explanation for this limitation is that the Gaussian splatting algorithm inherently assumes a degree of continuity in the spatial distribution of Gaussians. While this assumption performs well for smooth surfaces, it proves insufficient for accurately representing sharp edges.
![alt text](images/boundary.png "Initial fine views")

### Color artifacts in Rendered Viewpoints
In this section, we detail several color anomalies observed while exploring the rendered scenes.

First, as described in , spherical harmonics provide a view-dependent color representation. While this approach is effective for thoroughly scanned 3D objects, visualizing novel viewpoints not captured during scanning can result in blurry artifacts.

Additionally, the blending of Gaussians at object boundaries can introduce chromatic aberrations, which hinder high-fidelity reconstruction in scenes with complex structural details.

Furthermore, in regions with sparse or no training views, black specks (Gaussian artifacts) were observed in areas devoid of objects.

We hypothesize that these issues arise because the Gaussians are optimized specifically for rendering the training scenes, without fully capturing the true 3D structure of the environment.

![alt text](images/box_bike.PNG "Initial fine views")
![alt text](images/box_another_view.PNG "Another view")


## Extensions

### Fixing the Black Patches Issue with Generative Image Generation 

Under-represented viewpoints
often result in black patches. To address this in a post-processing
step, we experimented with generative image libraries like Stable
Diffusion  to fill in the gaps for key images.
Initially, on
Figure we used a fixed prompt---\"fill in the
missing black sections\"---to seamlessly complete the image. However,
this approach produced incorrect results, as it inadvertently removed
objects such as bicycle tires and benches. We suspect the model interpreted
the black areas too broadly.

To improve the output, we refined the prompt to make it more
context-specific, changing it to \"fill in the missing black sky\". This
adjustment led to a more satisfactory result, as it focused the model's
attention on the sky, preserving other key elements of the image.

While this method offers some improvement, it has significant
limitations: it can only be applied to one image at a time at the end of
the pipeline and must be repeated for each new viewpoint. A potential
solution to this issue would involve retraining the model using these
example-filled images. However, developing the algorithm to find the
appropriate prompts and integrating these images into the training
process is beyond the scope of this paper, though it presents a
promising direction for future work.

First try of filling gaps in images with Stable Diffusion with the
prompt:\" fill in the missing gap sections\". The input image is
figure, the bike is not present
anymore.


Result with a more fine-tuned prompt: \"Fill in the black sky\". The
bike is back again.
<figure id="fig:test">
 <img src="images/base_bicycle.png" style="width: 300px; display: block; margin: 0 auto;">
 <figcaption style="text-align: center;"> Input Images, a black hole can be seen </figcaption>
 <img src="images/missing_bicycle_box.PNG" style="width: 300px; display: block; margin: 0 auto;">
 <figcaption style="text-align: center;"> Input naive prompt: " fill in the black patches" </figcaption>
 <img src="images/filled_in_sky.png" style="width: 300px; display: block; margin: 0 auto;">
 <figcaption style="text-align: center;"> More complex prompt:" fill in the missing sky" </figcaption>
<figcaption style="text-align: center;">Results of our experiments.</figcaption>
</figure>

## Color and Boundary Repair Experiments 

### Adjusting Spherical Harmonics Parameter

As discussed in
Section , spherical harmonics can introduce
chromatic aberrations or blurry artifacts. To address this issue, we
experimented with modifying the degree of spherical harmonics for each
Gaussian, testing values of 1 and 2. However, overall, we did not
observe significant visual differences.
We hypothesize that the large number of Gaussians in the scene
(approximately 1.2 million) compensates for any potential loss of color
information.

<figure id="fig:">
 <img src="images/bonsai_sh.PNG" alt="Scene rendered changing the number of spherical harmonics" style="width: 300px; display: block; margin: 0 auto;">

<figcaption style="text-align: center;">Scene rendered changing the number of spherical harmonics.
No major changes can be seen. </figcaption>
</figure>

### Effects of adding noise on images before training 

In this section, we explored the impact of introducing noise to the
input images. Specifically, we added salt-and-pepper noise
 with probabilities $p = 0$, $p = 0.05$, and
$p = 0.2$. The resulting loss values were affected.. While some colors became slightly
desaturated, the 3D scenes were still reconstructed correctly. We
hypothesize that the diversity of input images compensates for the added
noise, suggesting that the quantity of images plays a more critical role
in maintaining reconstruction quality than the individual image
fidelity.

Furthermore, as discussed in
Section , we hypothesized that adding
Gaussian noise to colors could act as a smoothing parameter by
distorting details. This smoothing effect could potentially soften hard
edges, thereby simplifying the geometry for the Gaussians to learn. Our
observations confirmed that adding noise with a small
magnitude helped better reconstruct edges, such as those between the
box, the door and the wall, as well as the upper part of the door.
However, increasing the noise magnitude too much ultimately degraded the
geometry of the edges. Based on these findings, we conclude that
introducing noise to input images can serve as a useful parameter for
improving the algorithm's ability to learn sharp geometries at a
relatively low computational cost.

<figure id="fig:additional_fig">
 <img src="images/bonsai_pepper_clean_box2.PNG" style="width: 300px; display: block; margin: 0 auto;">
 <figcaption style="text-align: center;"> Input Images without any noise </figcaption>
 <img src="images/bonsai_pepper_005_box2.PNG" style="width: 300px; display: block; margin: 0 auto;">
 <figcaption style="text-align: center;"> Bonsai with a noise of 0.05</figcaption>
 <img src="images/bonsai_pepper_02_box2.PNG" style="width: 300px; display: block; margin: 0 auto;">
 <figcaption style="text-align: center;"> Bonsai with a noise of 0.2
<figcaption style="text-align: center;">Scenes rendered with varying levels of salt-and-pepper
noise. As the noise probability p increases, the boundaries become
smoother and more defined, enhancing clarity. However, excessive noise
(e.g., p = 0.2) leads to
significant loss of detail and color fidelity, resulting in desaturation
and visual degradation across the image.</figcaption>
</figure>

# Conclusion

This paper provides a comprehensive analysis of 3D Gaussian Splatting,
highlighting its limitations and proposing several extensions to address
these challenges. Key limitations identified include the appearance of
black patches in unobserved regions, difficulties in rendering sharp
boundaries, and color artifacts in novel viewpoints. To mitigate some of
these issues, we proposed a variety of solutions, such as using
generative image techniques to fill in missing viewpoints, incorporating
depth regularization during training, modifying the
structure-from-motion (SfM) solver, adjusting spherical harmonics to
reduce artifacts, and introducing noise to input images to test the
model's robustness. For future work, we plan to investigate the
potential of Gaussian Splatting for 3D mesh reconstruction, seeking to
extend its utility beyond rendering tasks.

<figure id="fig:lossnoise">

3D Gaussian Splatting explained


Signed Distance Fields (SDFs) parameterized by neural networks have recently gained popularity as a fundamental geometric representation. However, editing the shape encoded by a neural SDF remains an open challenge. A tempting approach is to leverage common geometric operators (e.g., boolean operations), but such edits often lead to incorrect non-SDF outputs (which we call Pseudo-SDFs), preventing them from being used for downstream tasks. In this paper, we characterize the space of Pseudo-SDFs, which are eikonal yet not true distance functions, and derive the closest point loss, a novel regularizer that encourages the output to be an exact SDF. We demonstrate the applicability of our regularization to many operations in which traditional methods cause a Pseudo-SDF to arise, such as CSG and swept volumes, and produce a true (neural) SDF for the result of these operations.

We proposed a presentation of the paper that can be found [here](https://github.com/gardiens/gardiens.github.io/blob/main/public/projects/csg_nsdf/Slide_proj_mva_geom.pptx)





## Constructive Solid Geometry on Neural Signed Distance Fields

### Introduction

Signed Distance Functions (SDFs) provide a canonical representation for implicit functions, essential for 3D modeling and complex Boolean operations. Despite their utility, SDFs face challenges when undergoing shape editing operations, such as Boolean combinations, as these operations often disrupt the stability required for rendering (e.g., ray marching). A key question is how to recover a true SDF after such transformations. One promising approach involves applying morphological operations like erosion and dilation.

### Context: Taxonomy of Implicit Functions

In 3D modeling, various implicit functions allow for the representation and manipulation of shapes. However, SDFs stand out for their ability to precisely define the distance to the nearest surface, making them ideal for certain applications. The challenge lies in maintaining this precision across transformations and ensuring rendering robustness.

#### Shape Editing with SDFs
While SDFs enable easy execution of Boolean operations for shape editing, they are not inherently stable. This instability can lead to rendering inaccuracies and limits their usability in certain applications.

#### Proposed Solution
To address these limitations, the paper introduces a novel loss function designed to regularize the output of implicit functions. This loss enhances the stability of SDFs under transformations, providing a more robust foundation for advanced shape editing techniques.

### Highlights of the Loss Function

The new loss function is defined as:

\[
\theta^* = \arg \min_{\theta} \mathcal{L}(\theta) + \lambda_c E_{\text{CP}}(\theta, X) + \lambda_e E_{\text{eik}}(\theta, X),
\]

where:

- $ \mathcal{L}(\theta) $: A loss term that measures how far the model is from the initial approximation.
- $ E_{\text{CP}}(\theta, X) $: A **conservative loss** that enforces the implicit function to adhere to Signed Distance Function (SDF) properties.
- $ E_{\text{eik}}(\theta, X) $: The **eikonal loss**, which enforces the implicit function to satisfy the eikonal equation, ensuring smoothness and geometric consistency.
- $ \lambda_c $ and $ \lambda_e $: Regularization coefficients that balance the contributions of the respective loss terms.

1. **Construction**: The proposed loss function combines regularization with constraints tailored to maintain SDF properties. 
2. **Application**: It is versatile and can be seamlessly integrated into existing frameworks.
3. **Efficiency**: While initial implementations required significant computational effort (e.g., 4 hours for regularization of a simple shape), optimizations through targeted reimplementations demonstrate considerable speed-ups.

### Applications

1. **Constructive Solid Geometry (CSG)**:
   - Facilitates the composition of complex 3D models using Boolean operations.
   - Ensures stability of SDFs during these operations.

2. **Swept Volumes**:
   - Enables the modeling of shapes resulting from motion paths, a critical capability in animation and mechanical design.

### Results and Limitations

#### Results
- The proposed loss function effectively corrects SDFs for simple shapes.
- Integration with importance sampling further improves efficiency by focusing computation on points near the zero level set.

#### Limitations
- Computational cost remains high for complex shapes, necessitating manual parameter tuning.
- The regularization process, while improved, still requires refinement for practical applications.

### Importance Sampling

To enhance performance, importance sampling was employed. This technique prioritizes sampling near points of interest (e.g., the zero level set), reducing computational overhead compared to uniform random sampling.

### Conclusions

This work proposes a new loss function for regularizing implicit functions, significantly improving the stability of SDFs during transformations. The approach is adaptable and can be incorporated into existing frameworks, making it a valuable contribution to 3D modeling and shape editing. However, further optimization and automation are needed to fully realize its potential in practical settings.

---
**Future Work**:
- Investigating more efficient sampling strategies.
- Extending the method to handle more complex shapes.
- Exploring automated tuning of loss function parameters to enhance usability.

Constructive Solid Geometry on Neural Signed Distance Fields


In Deep Learning, automatic
image classification can suffer from
unstructured labels and loss functions.We Introduce semantic knowledge
in data labels, via a custom
tree-based loss, could reduce
critical misclassifications.
Our goal is to assess if this new
model-agnostic method performs
better than existing solutions on the
CIFAR-10 dataset.

Lost in Layers, Navigating through Semantic Segmentation

We published a [paper about it](https://isprs-archives.copernicus.org/articles/XLVIII-2-W8-2024/45/2024/)
With the rapid development of 3D sensing technologies, 3D point cloud semantic segmentation has seen a rise in adoption from many fields. Indeed, while RGB cameras remain a popular choice under good visibility conditions, such sensors are inefficient in indoor environments where visibility can be hindered, for example by dust or fog. The more robust LiDAR sensors therefore play a growing role in 3D building reconstruction, high-level task planning, and robot navigation. Traditionally, point clouds are generated using expensive, heavy, high-precision sensors, with practitioners focusing on constructing accurate reconstructions without any time constraint. 

However, when autonomously exploring an indoor environment, mobile vehicles typically construct an internal map of the environment on the go. As they have limited fuel/energy, they need to understand their environment with lightweight sensors in real-time to make decisions. Moreover, in certain real-time applications, such as high-level task planning, quick scene understanding is a helpful feature to support decision-making.

Most existing 3D semantic segmentation methods focus on sparse outdoor LiDAR scans for autonomous navigation. However, there is limited research on indoor semantic segmentation with mobile mapping platforms due to a lack of available open-source data. For example, S3DIS, a popular indoor dataset, does not provide any sensor trajectory, and the sensors used for acquisition were primarily RGBD sensors.

In this paper, we present a real-time capable semantic segmentation approach for LiDAR point clouds (at the example of an indoor UAV platform). The input point cloud is assumed to be acquired with a dome LiDAR scanner with a non-repeatable scan pattern and preprocessed with a real-time mapping and state estimation algorithm. Our goal is therefore to design a semantic segmentation pipeline that collects point cloud submaps every $n$ seconds and predicts per-point labels. Such point clouds may suffer from inaccuracies due to the cheaper sensor's accuracy and the time-optimized SLAM algorithm. Model inference is also made more challenging by the lack of RGB features, without which small items may be unrecognizable. In this uncooperative setup, we focus on important structural classes within indoor environments, specifically walls, ceilings, floors, doors, and windows.

Our contributions are as follows:

- We adapt the Superpoint Transformer model to near real-time semantic segmentation, which entails both robustness and speed improvements of the pipeline. Specifically, we increase the number of neighbors in the preprocessing pipeline by a factor of 10 from 50 to 500 and change the partitioning algorithm to a simple but efficient voxel grid. 
- We propose a training procedure to train semantic segmentation models on available open-source datasets without any sensor trajectory for semantic segmentation in near real-time indoor environments.
- We conduct a comprehensive analysis of the impact of near real-time constraints on a deep learning model's performance in this domain. For example, we analyze the effects of distance-based filtering and modifying the prediction interval.
- We collect a real-world dataset in an office building environment to validate our findings. On this dataset, our modifications improve the IoU significantly for hard classes (from 0.8 to 14.1 on windows, from 9.1 to 16 on doors, and from 32.6 to 44.9 on floor points) while maintaining similar performance on other classes (from 64.9 to 65.2 on ceiling and 57.4 to 55.4 on walls).




# Method

## Superpoint Transformer

We use Superpoint Transformer as our baseline model. It is designed to handle large and small point clouds by computing a superpoint-based intermediate representation. The model can be separated into four key components. First, the point cloud is enriched with handcrafted features such as local linearity or verticality. Second, it is partitioned into a superpoint representation. Third, a graph is built from those superpoints. Finally, an attention-based model segments the nodes in the graph.

## Training Procedure

When training with S3DIS, most works give complete point clouds or spherical sections to the model. However, this is unrealistic in a real-time mobile mapping setting due to the model having access to points in occluded areas. Motivated by use cases similar to others, we structure our training process in two stages. First, a pretraining phase on S3DIS gives us a benchmark to compare to and a simpler task to initialize our model. Then, different fine-tuning phases teach the model to avoid relying on data that wouldn't be visible in real scenarios and to be more robust to noise.

### S3DIS:

Pretraining on S3DIS without adding any new data augmentation proves insufficient in our setup. For example, the model fails to properly detect doors and windows.

### Hidden Point Removal (HPR):

We fine-tune the model with additional data augmentation using an HPR algorithm. To process each input point cloud at training time, a random point in the point cloud is chosen as the center for the algorithm, then points that would not be visible from this center are removed. This randomness simulates different viewpoints and helps the model generalize better by exposing it to various perspectives and occlusion scenarios. This data augmentation makes use of the original data and doesn't require any additional information or simulation.

### Simulating trajectory: S3DIS\_sim:

Given that meshes are available in public datasets such as S3DIS and a digital twin of our robot and sensor is available, we recreate the robot's trajectory in Gazebo within the mesh, from which we acquire a new dataset S3DIS\_sim. The collected sensor data is then split into 10-second intervals to form S3DIS\_10s. Fine-tuning on S3DIS\_sim and S3DIS\_10s provides a more realistic training environment for the model, which translates to higher robustness to our setup's difficulties.

## Noisier Point Clouds and the Lack of RGB Features

Most prior studies, including the original SuperPoint Transformer paper, use RGB as additional input features in the point cloud, which constitutes a very semantically rich feature. To compensate for its absence, we identify the anisotropy feature as a good discriminator for doors and windows against walls and ceilings. Furthermore, we remove the elevation feature which can no longer be reliably computed in our setup. Based on a hyperparameter search, we also remove the surface feature.

Because LiDAR SLAM point clouds are noisier than the point cloud from S3DIS, important features such as linearity might lack robustness due to their sensitivity to noise. To reduce this effect, we compute the features over a larger neighborhood of 500 points (from 50).

## Achieving Near Real-time Inference

### Prediction Interval Selection:

As we infer more often on smaller point clouds, we note a decrease in segmentation quality due to the reduced context. We opt to infer every $n=10$ seconds, as this interval produces results comparable to those obtained by processing the entire map. We provide an extensive analysis of the size of the time window in the paper.

### Computation Trade-off:

Although the authors of the Superpoint Transformer claim an inference time close to 2 seconds, preprocessing can take on average up to 20 seconds for 10-second intervals (on an Intel(R) Xeon(R) Silver 4116 CPU at 2.10 GHz, equipped with 48 CPUs and two GeForce RTX 3090 GPUs, each with 24 GiB of VRAM). As we aim to infer on mapped point clouds in near real-time, we identify the Cut-Pursuit partition algorithm as one major time expenditure. We replace Parallel Cut Pursuit with a voxel grid partition at no significant cost in accuracy for our setup.

# Experiments

## Datasets

### S3DIS

S3DIS is an RGB-D dataset that consists of 6 indoor areas. It is one of the most widely used indoor datasets in the literature, and meshes and point clouds are provided. We discard its RGB features.

### S3DIS\_sim and S3DIS\_10s

We simulate our robot's trajectory in S3DIS with Gazebo. SLAM is performed based on the UAV's trajectory. The resulting point cloud S3DIS\_sim is annotated by aligning the mesh with the resulting point cloud. This point cloud is then further split into 10-second intervals, which serve as the model's inputs. We denote this new data as S3DIS\_10s, which we will open-source.

### Office\_10s

Using our mobile mapping platform, we map a working office consisting of a building with two floors, one hall, and 16 rooms. We manually label the resulting point cloud. Small items such as tables and chairs exhibit significant noise due to the sensor and SLAM limitations.

## Results

We comprehensively analyze our proposed modifications and pretraining schemes for each different dataset. We notice that although our modifications improve the performance of the model across the board (for example, from 0.8 IoU on windows to up to 14.1 with our changes on our collected test data), they do not do so homogeneously across all datasets. We advance hypotheses to explain these differences between datasets. Finally, we analyze the impact of modifying the prediction interval and provide an extensive speed benchmark of every key component of Superpoints Transformers to bring the processing time below the duration of the prediction interval. We show encouraging results of 38% of mIoU with a prediction interval of 10s on real data (from 31.6% with no modifications), going up to 67.6% for 10s intervals of the S3DIS dataset (from 40% with no modifications).

# Conclusion

This paper presents a comprehensive analysis of indoor semantic segmentation under near-real-time processing. Specifically, we examine how to train such models using available datasets and how to adapt them to the constraints of a near real-time mobile mapping scenario. From a use


Semantic Segmentation on UAV


A project to solve to apply Time Series Transformers to prediction of human Skeleton. 
In particular, we focus on promising architecture such as FEDFormer and AutoFormer.
We submitted to JDSE 2023 and the paper can be found [here](https://github.com/gardiens/Time-Series-Library_skeleton/blob/master/9_Investigating_Transformers_f.pdf)




## Motivation 

The study at hand exists within the broader framework of identifying neurological pathologies in newborns through the analysis of spontaneous motor skills. We aim to develop pre-diagnostic tools for early detection. The central goal of this study
is to assess transformer-based models’ accuracy in forecasting motor skills for individuals without pathologies (normal data). We anticipate neurological abnormalities
(abnormal data) to disrupt movement patterns, heightening prediction complexity.
Presently, an inadequate number of videos capturing newborns’ motor activities are available for analysis. Thus, we turned our attention to the NTU RGB+D
dataset[2]. This dataset emerged as a suitable substitute for our research objectives.


## Methods 
We conducted various tests involving dataset modifications, preprocessing steps,
and model enhancements. As we cannot present all the experiments, we focus here
on FEDformer and specific preprocessing steps that yielded the best results.
Dataset We used the NTU RGB+D[2] dataset, which features motion sequences of
adults spanning durations of 2 to 10 seconds. Each 3D skeletal data contains the 3D
coordinates of 25 body joints at each frame.
Preprocessing Each data is normalized by removing the mean of each time series.
We divided the data into input and output segments, each consisting of 16 frames
(approximately 1 second) at a precise point corresponding to a change in movement.
Model FEDformer implementation was taken from TSLib library1.
Experimental Setup All computational tasks were performed within the LabIA2
computing environment at the University of Paris-Saclay. Using the given input data
for training, the model is required to predict both the input and output sequences.
Evaluation Metrics We adopted widely-used metrics such as Mean Squared Error
(MSE) and Mean Absolute Error (MAE). We also conducted visual evaluations by
comparing the ground truth movement patterns with the predictions generated by our
models


## Results 
showcases the performance of FEDformer both with and without specific
preprocessing steps aimed at enhancing its efficacy in human action forecasting. Visual
outputs are available, along with our code, on GitHub.
The table illustrates the enhancement in FEDformer’s performance due to our preprocessing interventions. In terms of the training set, we observed a 1.7-fold reduction
in MSE and a 20-fold decrease in MAE.
Nevertheless, upon visual inspection of the results, we noticed that the model
encountered difficulties in accurately predicting substantial movements. Its predictions
extended the termination of input movements, presenting a misalignment with actual
patterns.
We may explore alternative metrics and evaluation methodologies to gain insights
into the underlying reasons for the model’s suboptimal learning.



Transformers for Time Series

Une des problématiques de l’informatique quantique est de trouver le nombre minimal de portes
quantiques pour préparer synthétiser des circuits quantiques. Pour cela, nous avons étudié une piste
qui consiste à utiliser de Quantums Multiple Decisions Diagrams (QMDDs).Alors que certains auteurs se sont intéressés à la synthèse de QMDD à l’aide de la logique classique [6], nous nous sommes
concentrés à traduire le QMDD dans un langage graphique appelé ZX. Notre apport est une implémentation des QMDDs en python, une proposition de synthèse des générateurs des QMDDs et
une identification de pistes supplémentaires pour la synthèse en diagramme ZX. 
Un rapport détaillé est disponible [ici](https://github.com/gardiens/gardiens.github.io/tree/main/public/projects/QMDD_rapport.pdf)



## Main body


Lors de ce pôle projet, nous avons pu étudier la synthèse de circuit quantique à l’aide des QMDDs.
Pour cela, nous avons d’abord réimplémenté les QMDDs en python pour pouvoir être manipulable
avec une documentation clair, puis nous avons trouvé des équivalents en ZX des éléments fondamentaux des QMDDs. Ces générateurs peuvent se traduire en informatique quantique au prix de mesures
post-sélections.Nous avons obtenu des résultats à première vue prometteurs, mais qui nécessiterait
des travaux supplémentaires. En effet, il faudrait réussir à quantifier la probabilité d’obtenir le résultat à l’aide de nos mesures post-sélections et nous pourrions aussi regarder nos résultats avec des
librairies qui utilisent déjà les mesures post-sélections. Concernant les QMDDs en tant que tel, je
pense qu’ils existent plusieurs pistes d’amélioration.

— Il faudrait réussir à mieux comprendre l’interaction entre les QMDD et la synthèse des coefficients sur les arêtes. Pour cela, on pourrait étudier leurs interactions en ZH pour essayer de
trouver des représentations intermédiaires pour faire de simplifier ces coefficients.

— On pourrait aussi regarder à quelles conditions sur les arêtes un QMDD possède ou non un
g-flow [3], ce qui devrait être possible, car dans certains cas, il existe une traduction en circuit
quantique de ces QMDDs.

— Enfin, une autre piste d’amélioration serait de creuser l’interaction entre les QMDDs et les
BDDs. Une voie serait de regarder s’il est possible de voir à quelles conditions nous pourrions
utiliser les mêmes algorithmes que les BDDs mais appliqué sur les QMDDs.

Nous pensons que ces différentes voies permettraient d’améliorer nos résultats obtenus lors de ce
parcours recherche

Matrices synthesis with QMDD


A project to solve the $1|r_j|\sum_j w_jT_j$ Scheduling problem.

A task squedulling problem on **one machine** whith :
- $r_j$ : release dates
- $p_j$ : processing times
- $d_j$ : due dates
- $w_j$ : weights



# Schedulling Problem

## Problem

The problem to solve is the following : $1|r_j|\sum w_jT_j$

The objective is to minimize the sum of the weighted delays on one machine according to minimal starting dates ($r_j$) and due dates ($d_j$)

$$
(P)=\left\{ 
 \begin{array}{ll}
 \min & \sum w_jT^\sigma_j \\
 & T^\sigma_j = \max(0,c_{\sigma(j)}-d_j) & \forall j\\
 & c_{\sigma(j)} \geq r_j + p_j & \forall j \\
 & \sigma \in S(n) \text{ : permutation}
 \end{array}
\right.
$$

We want to find a permutation of the tasks $\sigma (j)$

### Heuristics

We defined 7 heuristics to solve the problem. The heuristics are the following :

- EDD : Earliest Due Date, by sorting the jobs by due date in ascending order
- LPT : Longest Processing Time, by sorting the jobs by processing time in descending order
- SPT : Shortest Processing Time, by sorting the jobs by processing time in ascending order
- Minimum Slack : by sorting the jobs by slack in ascending order. A slack is the difference between the due date and the processing time
- Weighted SPT : by sorting the jobs by the ratio of weight and processing time in ascending order
- FIFO : First In First Out, by sorting the jobs by their arrival time in ascending order
- Weight First : by sorting the jobs by weight in descending order

### Linear Programming


We can express it as a linear programming problem by adapting the formulation that we saw during the class :

$$
(LP)=\left\{ 
 \begin{array}{ll}
 \min & \sum w_jT_j \\
 & T_j \geq 0 & \forall j\\
 & T_j \geq c_j - d_j & \forall j\\
 & c_j \geq r_j + p_j & \forall j\\
 & x_{ij} + x_{ji} = 1 & \forall i,j, i \neq j\\
 & c_j \geq c_i + p_j + M(x_{ij} - 1)& \forall i,j, i\neq j\\
 & x_{ij} \in \{0,1\}, c_j \in \mathbb{N}& \forall i,j, i\neq j\\
 \end{array}
\right.
$$

$x_{ij}$ set to 1 if job i is before job j, otherwise set to 0

$M$ is set to a high value, so that $M \geq \max (c_i+p_j)$

#### Simplified Linear Programming Problem

We can keep only the top triangle of the matrix as the relation $x_{ij} = 1-x_{ji}$ stands for the bottom triange

$$
(LP')=\left\{
 \begin{array}{ll}
 \min & \sum w_jT_j \\
 & T_j \geq 0 & \forall j\\
 & T_j \geq c_j - d_j & \forall j\\
 & c_j \geq r_j + p_j & \forall j\\
 & c_j \geq c_i + p_j + M(x_{ij} - 1)& \forall i,j, i\text{<}j\\
 & c_j \geq c_i + p_j - Mx_{ji}& \forall i,j, i\text{>}j\\
 & x_{ij} \in \{0,1\}, c_j \in \mathbb{N}& \forall i,j, i\text{<}j
 \end{array}
\right.
$$

This way we get 2x fewer variables and less constraints


### Evaluation 

For small instances (n<10), we can compare the results with the optimal solution found with the linear programming problem. For bigger instances, we can compare the results with the best heuristic (tabou multi-start).

### Aim of the Study

We build an algorithm/formula that decides wich algorithm/heuristic to use according to the parameter distributions : which one performs the best