# Projet c++ M1 MMAA : Détection de droites et de courbes dans une image
> [name=Soutenance le 27/03/25 à 13h15][color=#907bf7]

Une image numérique peut être considérée comme une application $I : Rect \subset \mathbb{Z}^2 \rightarrow V^3$ où $Rect$ est une grille de points et $V$ un ensemble fini de valeurs, souvent dans $[0,255]$. Nous nous interessons dans ce projet à une méthode pour détecter des segments/droites dans une image en temps réel par la **transformée de Hough**. Les segments devant être détectés peuvent être de n'importe quelle épaisseur.

## La transformée de Hough en bref
La transformée de Hough est une technique utilisée en traitement d'images pour détecter des formes géométriques, comme des lignes ou des cercles, dans une image. Elle représente les formes dans un espace paramétrique et détecte les paramètres correspondants aux formes recherchées. C'est une méthode puissante pour la détection de formes dans les images.
| Image | Image avec la droite détectée |
| ---------------------------------------------------------------- | ----------------------------------------------------------------- |
|  |  |

## Méthodes de résolution

### Méthode naïve (approche à implanter)
L’idée de la transformation de Hough est de représenter des formes dans un espace paramétrique qu’on appellera l’espace de Hough. Pour la méthode naïve, l’objectif est de détecter des droites dans une image, l'équation qu'on considère est celle d’une droite $y = mx +b$. Dans l'espace de Hough, chaque point de l'image aura un couple $(m, b)$ associé et donc une droite associée. Une droite dans l’espace de paramètre $(x, y)$ habituel que l’on appellera l’espace d’origine sera représenté par un point dans l’espace de Hough et un point dans l'espace d’origine sera représenté par une droite dans l’espace de Hough en suivant la formule ci-dessous:
$$
b = y - mx
$$

**Approche à implanter**
Le principe de l’algorithme utilisé est de récupérer toutes les coordonnées $(x, y)$ composant les pixels de l'image d’origine et pour chaque coordonnée, tracer la droite correspondante dans l’espace de Hough. L’objectif est ensuite de récupérer les coordonnées du pixel sur lequel se croisent le plus de droites dans l'espace de Hough. Pour cela, vous utilisez un accumulateur et récupérez la position (pixel) du maximum.

Quel peut être un inconvénient majeur de cette méthode ?

### Méthode moins naïve (approche à implanter)
On considère, dans cette section, l'équation en coordonnées polaire d’une droite
$$
y = -\frac{\cos(\theta)}{\sin(\theta)} x + \frac{\rho}{\sin(\theta)}
$$
$\theta$ correspond à l’angle entre la droite et l’axe des abscisse et $\rho$ à la distance entre la droite et l’origine, voir ci-dessous
Comme précédemment et en utilisant la formule ci-dessous, il est possible de parcourir les pixels dans l'espace d’origine et tracer dans l'espace de Hough une sinusoïdale :
$$
\rho = x \cos(\theta) + y \sin(\theta)
$$

Implanter et tester cette méthode. Quels avantages voyez-vous?

### Pour diminuer la complexité? (approche à implanter)
- Dans les deux sections précédentes, tous les pixels sont parcourus, ce qui peut être couteux en terme de temps de calcul. Sachant que les segments détectés appartiennent aux contours de l'image, proposer et implanter une méthode pour réduire la complexité.
- Une autre approche consiste à choisir un certain nombre de fois aléatoirement deux points dans l'image. Ces deux points définissent une droite et donc un couple $(m,p)$. Il s'agit ensuite de compter le nombre d'occurrences de chaque couple $(m,p)$. Une fois que le nombre d'occurences d'un couple dépasse un seuil donné en entrée, on trace la droite correspondante. Quels sont les avantages de cette méthode?

## Dessiner une droite (à implanter) : marche de Bresenham
Ce projet ne nécessite aucune bibliothèque graphique, il faut cependant pourvoir tracer une droite sur une image. Le paragraphe suivant explique la méthode utilisée pour dessiner une droite. Soit $(D) : y = mx + b$ la droite à tracer, la première étape, appelée line clipping, sert à délimiter parmi toute la droite la partie visible sur l’image. On ne trace en effet qu’un segment $[A,B]$ de cette droite dont il faut déterminer les coordonnées. Une fois les points $A$ et $B$ déterminés, il faut tracer le segment $[A, B]$. Soit $q_{i,j}$ le pixel situé sur la colonne $j$ de la ligne $i$, une première approche serait de parcourir les colonnes de $j = x_A$ à $x_B$ et de dessiner le pixel $q_{m.j+b,j}$. Malheureusement certains segments sont très mal dessinés avec cette méthode, notament les segments presque verticaux qui ne sont alors représentés que par deux ou trois pixels. Il y a donc deux cas à différencier. Soit $|m| \leq 1$ auquel cas la méthode précédente est satisfaisante. Soit $|m| > 1$ et il est alors préférable de parcourir les lignes de $i = y_A$ à $y_B$ et de dessiner les pixels $q_{i, i−b}$. Pour **minimiser les effets de crénelage**, une méthode d'antialising sera implanté, voir [ici](https://en.wikipedia.org/wiki/Spatial_anti-aliasing) (section Simplest approach to anti-aliasing)

## Supprimer deux droites proches (à implanter)
Pour un même segment épais présent dans une image, plusieurs droites peuvent être détéctées. Implanter un algorithme permettant de choisir une droite lorsque plusieurs droites sont détéctées dans un voisinage donné.

## Contraintes du rendu
Le but du projet est d'implanter en langage C++ un programme permettant de détecter des droites et des portions de droites sur une image couleur au format ppm (format P3), voir exemple ci-dessous et fichier .ppm sur Moodle.

P3
# resolution
2 2
# avec 255 comme val max
255
# debut de l image
255
0
0
255
0
0
0
255
0
0
0
255

Votre programme sera composé de fichiers .cpp et .h. Ce programme sera séparé au moins en trois parties : la première efféctuera une détection de droites avec la transformation de Hough et générera une réplique de cette image avec les droites détectées en surimpression. Dans cette partie, vous devrez pouvoir visualiser les différentes droites dans l'espace de Hough. La seconde partie consistera à choisir les droites les plus représentatives de l'image en utilisant une méthode de votre choix (suppression des doublons). La troisième permettra de n'effectuer le calcul de la transformée de Hough sur les contours de l'image. Vous devrez justifier le choix de vos structures et de vos fonctions pendant la soutenance. A l’issue du projet, le groupe d’étudiants devra remettre un **dépôt github ou gitlab** (notes sur l'utilisation de git [ici](https://hackmd.io/V7VRr1ljRly7OYEKGRVgaA)) présentant
- l’avancement de son travail,
- le code développé,
- un ```Readme.md``` expliquant le sujet, décrivant les points saillants du travail réalisé ainsi que comment se servir du code développé.
- Des exemples d’utilisation doivent être donnés.

## Pour aller plus loin
Que faut-il changer si on veut adapter la transformée de Hough pour des cercles? des ellipses? Essayer d'implanter une approche.