---
title: INFO911 (TP3) Segmentation d'image hiérarchique
---
INFO911 (TP3) Segmentation d'image hiérarchique (scale sets)
===
[TOC]
> [name=Jacques-Olivier Lachaud][time=October 2025][color=#907bf7]
###### tags: `info911` `tp`
Retour à [INFO911 (Main) Traitement et analyse d'image](https://codimd.math.cnrs.fr/s/UE_B59gMy)
Ce TP étudie une méthode de segmentation hiérarchique appelée **scale sets** de ([Guigues, Cocquerez, Le Men, 2006](https://hal.science/hal-00705364v1/file/ijcv_scale-setV11.pdf)), qui construit de manière bottom-up une hiérarchie de partitions d'image de plus en plus simplifiée.
Il s'agit d'une approche *variationnelle*, où l'algorithme cherche à miniminiser une fonction coût $E$ définie sur l'image, et qui est paramétrée par une échelle $\lambda$. Cette approche est décrite dans la partie [Approche hiérarchique (scale sets)](https://codimd.math.cnrs.fr/s/5i8LT2Gnd) du cours.
:::info
Afin de maximiser les chances de succès d'implémentation de cette méthode, je vous donne un squelette de code assez complet qui comporte :
1. les structures de données pour représenter une hiérarchie de partitions d'image et les régions dedans (`Hierarchy`, `Hierarchy::Region`, etc),
2. les fonctions pour fusionner deux régions adjacentes (`Hierarchy::merge`).
3. un algorithme aléatoire de fusions aléatoire de régions.
4. un moyen de visualiser les contours.
:::
## 0. Prise en main du code
:::danger
**A faire**. Récupérez le **[code initial](https://jacquesolivierlachaud.github.io/teaching/info911/Tests/tp3/tp3-0.cpp)**, environ 550 lignes de c++.
:::
On peut le découper en 3 morceaux. Le premier morceau inclut les headers utiles et fournit quelques fonctions pratiques.
```cpp=
#include <iostream>
#include <set>
#include <opencv2/imgproc.hpp>
#include <opencv2/highgui.hpp>
#include <opencv2/core.hpp>
using namespace cv;
/// Given an image of labels, draw contours onto the image at region boundaries with
/// given color.
cv::Mat drawContours( cv::Mat labelled_img, cv::Vec3b color ) {...}
/// Resizes the input image to have a resolution divided by 2 along each axis.
cv::Mat downSample( cv::Mat input ) {...}
/// Returns a resized version of image img so that it has the size of image target.
cv::Mat rescaleLinear( cv::Mat target, cv::Mat img ) {...}
/// Displays a text into the input image.
void printText( cv::Mat input, std::string text,
double x, double y,
double font_scale = 1.0,
int thickness = 1,
cv::Scalar color = cv::Scalar( 255, 255, 255 ) ) {...}
```
Le deuxième morceau contient la classe principale `Hierarchy` ainsi que sa classe interne `Hierarchy::Region`. Notez les méthodes pour calculer les caractéristiques d'une région, ainsi que la méthode de fusion de région `Hierarchy::merge`. La stratégie de fusion progressive des régions est faite dans `Hierarchy::stupidMerge`.
```cpp=
struct Hierarchy {
/// Pixel
struct Pixel {int x; int y;};
/// A connected region of pixels.
struct Region {
int index;
Pixel start;
std::vector< int > pixel_indices;
std::vector< std::pair< int, int > > boundary;
std::set< int > neighbors;
Vec3f sum;
/// Default constructor. The object is invalid
Region() : index( -1 ){}
/// Construct a region that is the pixel p of index idx in image img.
Region( int idx, Pixel p, const cv::Mat& img ) {...}
/// Resets the region, which becomes invalid.
void clear() {...}
/// return the (discrete) perimeter of the region.
int perimeter() const {...}
/// return the area of the region.
int area() const {...}
/// return the average color of the region.
Vec3b averageColor() const {...}
/// returns a new region that is the fusion of this region with
/// region \a other.
Region virtualMerge( const Region& other,
std::vector<int>& linlabels ) const {...}
/// (Definitely) merges this region with region \a other.
/// @return the boundary that was lying between the two regions before fusion.
std::vector< std::pair< int, int > >
merge( const Region& other, std::vector<int>& linlabels ) {...}
/// Displays information about this region.
void display() {...}
}; // end of struct Region
/// Type for energy functions (takes a hierarchy and a region and ouputs a float).
typedef std::function< float ( const Hierarchy&, const Region& ) > EnergyFct;
/// data
cv::Mat input;
std::vector<Region> regions;
std::vector<int> linlabels;
std::set<int> active_regions;
double last_lambda;
cv::Mat saliency;
int nb_fusions;
EnergyFct Dfct;
EnergyFct Cfct;
/// Constructor from image, homogeneity function D and boundary
/// function C.
Hierarchy( cv::Mat image, EnergyFct D, EnergyFct C ) {...}
/// Initializer from image, homogeneity function D and boundary
/// function C.
void init( cv::Mat image, EnergyFct D, EnergyFct C ) {...}
/// Contour energy of region r.
float C( const Region& R ) const {...}
/// Homogeneity energy of region r.
float D( const Region& R ) const {...}
/// Total energy of region r at scale lambda.
float Energy( const Region& R, float lambda ) const {...}
/// Relabels region R2 in all its neighbors as the region R.
void relabel( int R2, int R ) {...}
/// Returns the image giving for each pixel its label (i.e. region index).
cv::Mat getLabels() const {...}
/// Main method merging region R2 into R et scale lambda.
void merge( int R, int R2, float lambda ) {...}
/// Illustrative (stupid) greedy fusion of regions
void stupidMerge( int N, float lambda ) {...}
/// Pixels are indexed/numbered, so this method returns the
/// index/number associated to the given pixel.
int number( Pixel p ) const {...}
/// Pixels are indexed/numbered, so this method returns the
/// pixel associated to the given index/number.
Pixel pixel( int idx ) const {...}
/// Updates the saliency image by setting the given range of
/// boundary linels to value.
void updateSaliency( const std::vector< std::pair< int, int > >& bdry,
int value ) {...}
/// If you do not build the hierarchy to the top (one region), it draws
/// the saliency of the current partition.
void finishSaliency( int value ) {...}
/// Draws the saliency on top of the doubled input image.
cv::Mat getSaliency( double level_cut, double power = 10.0 ) const {...}
}; // end of struct Hierarchy
```
Le dernier morceau contient le programme principal, l'ouverture de l'image ou du flux vidéo, et l'appel au calcul de la hiérarchie de partition et son affichage.
```cpp=
int main(int argc, char** argv)
{
...
VideoCapture* pCap = nullptr;
if ( argc > 1 )
input = imread( argv[ 1 ] );
else {
pCap = new VideoCapture( 0 );
...
}
...
/// Main loop
while ( true ) {
...
/// Get new frame in video in video stream mode.
if ( pCap != nullptr ) {
(*pCap) >> input;
input = downSample( input );
}
...
Hierarchy H( input, D1, C1 );
H.stupidMerge( iSuperPixels, lambdaSP );
/// Display contours or saliency.
if ( ! saliency )
{
cv::Mat L = H.getLabels();
cv::Mat contours = drawContours( L, cv::Vec3b { 255,255,255 } );
addWeighted( contours, 1.0, input, 1.0, 0, output_image);
}
else
{
double cut = double( iCut ) / 100.0;
H.finishSaliency( H.nb_fusions );
output_image = H.getSaliency( cut );
}
...
/// Display some information on output and output afterwards.
imshow( "Segmentation", output_image );
} // while (true ) {
return 0;
}
```
Récupérez ce code et testez-le. Vous devriez obtenir ce genre d'image (en bougeant peut-être quelques sliders).
|  |  |
| -------- | -------- |
| Contour visualisation (N sp = 6) | Saliency visualisation (N sp=9) |
:::danger
Pourquoi l'algorithme `stupidMerge` fait des régions presque rectangulaire ? Quelle énergie est minimisée ici pour décider quelles régions fusionner ?
:::
## 1. Visualisation de la couleur moyenne d'une région
Pour se faire la main, on va juste modifier l'affichage des régions en mode visualisation `contours`.
:::danger
**A faire**. Vous allez écrire une méthode `cv::Mat Hierarchy::drawRegions()` qui calcule une image de sortie telle que chaque pixel d'une région est affichée avec la couleur moyenne de la région (chercher `Region::averageColor`).
Ensuite, mettez à jour le mode visualisation `contours` de manière à ce qu'il affiche les contours et les couleurs moyennes de chaque région. Vous devriez obtenir ce genre d'images.
:::
|  | |
| -------- | -------- |
| Contour visualisation (N sp = 6) | Contour visualisation (N sp = 8) |
## 2. Energie de fusion favorisant l'homogénéité des régions
Telle quelle, on voit bien que la règle choisie de fusion des régions sur le seul critère de périmètre n'est pas très intéressante. On va tenir compte de la variance des couleurs d'une région pour favoriser la fusion de régions homogènes (i.e. de couleurs similaires). On rappelle que la moyenne et variance empirique d'un échantillon $X:=(x_i)_{i=1,\ldots,n}$ est
$$
\mu(X):=\frac{1}{N}\sum_{i=1}^n x_i, \quad
\sigma^2(X):=\frac{1}{N}\sum_{i=1}^n (x_i - \mu(X))^2.
$$
L'inconvénient de ces formules est que lorsqu'on fusionne deux régions disjointes $R_1$ et $R_2$, il faut les recalculer pour la nouvelle région $R_1 \cup R_2$. Il est donc plus astucieux de mémoriser par région les deux sommes suivantes:
$$
S(X):=\sum_{i=1}^n x_i, \quad
V(X):=\sum_{i=1}^n x^2_i.
$$
On vérifie aisément d'une part que
$$
\mu(X) = \frac{1}{N}S(X), \quad \sigma^2(X) = \left(\frac{V(X)}{N}\right)-\left(\frac{S(X)}{N}\right)^2.
$$
et d'autre part que mettre à jour ces sommes pour une fusion de régions est trivial, car il s'agit juste de les sommer. Un dernier point est que nous travaillons sur des images couleurs, donc il faut mémoriser $S$ et $V$ pour les 3 canaux RGB de couleurs. Pour résumer, si on note $(R_1,G_1,B_1)$ les échantillons de couleurs de la région 1, $(R_2,G_2,B_2)$ les échantillons de couleurs de la région 2, et $(R',G',B')$ les échantillons de couleurs des régions 1 et 2 fusionnées, on a:
$$
S(R'):=S(R_1)+S(R_2), \quad S(G'):=S(G_1)+S(G_2), \quad S(B'):=S(B_1)+S(B_2),\\
V(R'):=V(R_1)+V(R_2), \quad V(G'):=V(G_1)+V(G_2), \quad V(B'):=V(B_1)+V(B_2),\\
$$
:::danger
**A faire**. Ajoutez le calcul de la variance des couleurs d'une région. Il faudra rajouter une donnée membre `Vec3f sum2` (représentant $V$) à une région (notez que $S$ est déjà écrite avec `Vec3f sum`, l'initialiser correctement dans le constructeur de région, et la mettre à jour dans les méthodes `Hierarchy::virtualMerge` et `Hierarchy::merge`. Enfin, on écrira la méthode `float Region::variance() const` qui retourne la somme des variances de chaque canal de couleur R, G, B.
:::
:::danger
**A faire**. On va maintenant mettre à jour la façon dont on fusionne les régions. Dupliquer la méthode `Hierarchy::stupidMerge` pour faire une méthode `Hierarchy::superPixels`. Dans cette méthode, pour une région $R$, plutôt que d'utiliser l'énergie $C(R)$ qui retourne juste le périmètre, on va utiliser $D(R) + \lambda C(R)$, qui permet de tenir compte de la variance et de l'aire de la région. Si maintenant vous remplacez l'appel de `stupidMerge` par celui de `superPixels`, vous devriez obtenir des régions beaucoup plus pertinentes (jusqu'à une certaine échelle).
|  |  |  |
| --------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------- |
| $N sp=7$, $\lambda=0$ | $\lambda=0.5$ | $\lambda=5$ |
|  |  |  |
| $N sp=9$, $\lambda=0$ | $\lambda=1$ | $\lambda=5$ |
:::
## 3. L'algorithme de Scale Climbing
La méthode d'aggrégation précédente, dite *gloutonne* (*greedy* en anglais), est souvent un pré-traitement de flux vidéos. On parle de **super-pixels**, car cela crée des petites régions assez homogènes. Si l'on cherche à faire de trop grosse régions, on voit vite que l'algorithme devient instable.
Guigues, Cocquerez et Le Men proposent en 2006 un algorithme de calcul d'une hiérarchie de partitions, du plus fin (par exemple, chaque pixel est une région ou alors des super-pixels). L'énergie associée à une partition $\mathcal{P}$ est simplement la somme des énergies de chaque région. Ils combinent une énergie d'homogénéité $D$ avec une énergie de contour $C$ comme au-dessus. La hiérarchie est alors l'ensemble des partitions optimales obtenues pour différentes valeurs de $\lambda$:
$$
E(\mathcal{P}_\lambda):= \arg\min_\mathcal{P} \sum_{R \in \mathcal{P}} D(R) + \lambda C(R).
$$
Il n'est pas difficile de voir que, pour $D$ croissante et/ou $C$ décroissante, la partition optimale $\mathcal{P}_0$ pour $\lambda=0$ est simplement la partition la plus fine possible. A l'inverse, lorsque $\lambda$ tend vers l'infini, la partition optimale est une seule région couvrante toute l'image.
L'idée de l'algorithme de **scale climbing** est de partir de la partition fine $\mathcal{P}_0$ puis de trouver à chaque étape quelles sont les 2 prochaines régions à fusionner pour trouver la partition optimale juste au-dessus. Evidemment, le problème est NP-difficile pour des énergies quelconques, mais l'heuristique trouvée va être très efficace dans notre contexte. Le principe est de considérer **toutes** les paires de régions voisines $R_1$ et $R_2$ à une étape donnée, puis de comparer les énergies **avant** et **après** fusion en une région $R'=R_1 \cup R_2$. On a:
$$
E(R_1)+E(R_2)=\underbrace{D(R_1)+D(R_2)}_{b}+\lambda(\underbrace{C(R_1)+C(R_2)}_{a})=a \lambda + b\\
E(R')=D(\underbrace{R'}_{b'})+\lambda \underbrace{C(R')}_{a'}=a' \lambda + b'
$$
Il s'agit donc de **deux droites** de la forme $y=\alpha \lambda + \beta$. Lorsque $\lambda$ est petit, il vaut mieux que les régions $R_1$ et $R_2$ soient *séparées*. Lorsque $\lambda$ est grand, il vaut mieux que les régions $R_1$ et $R_2$ soient *fusionnées*. Leur **intersection** correspond au moment où les régions doivent être *fusionnées*. On cherche donc le paramètre $\lambda_+$ de leur intersection, solution de $a \lambda + b = a' \lambda + b'$.
On fait ce calcul pour chaque paire de région, et on détermine le plut petit $\lambda_+$. C'est celui-ci qui détermine la prochaine fusion à faire. On fusionne et on recommence.
:::warning
Cet algorithme fonctionne mais a une complexité supérieure à quadratique ($n^2/2$ étapes et chaque calcul de $\lambda_+$ coûte un temps proportionnel au nombre de pixels d'une région).
:::
Nous allons être plus gourmand, mais beaucoup plus rapide, en faisant le calcul précédent, en triant tous les résultats suivant leur $\lambda_+$, puis en fusionnant les $20 \%$ premiers (vous pouvez paramétrer par l'utilisateur). L'algorithme pseudo-code final devient:
```cpp=
// @param nbr le nombre de régions ciblés (1 pour toute la hiérarchie)
// @param prop la proportion de candidats max fusionnés à chaque appel.
// @return 'false' si on a fini de fusionner jusqu'à nbr régions.
bool scaleClimbing( int nbr, double prop = 0.20 )
{
Si nombre de regions actives < r, retourne faux
Q : pile de candidats
Pour chaque index r de région active faire:
Pour chaque voisin v de la région r faire:
R_1 = region(r), R_2 = region(v)
Rf = virtualMerge(r, v)
Calculer a,b,a',b' des énergies associées
Calculer lambda_plus
Q.push_back( r, v, lambda_plus )
Trier Q selon les lambda_plus
N = ceil( prop * nb de régions actives )
Pour tous les candidats de 0 à N-1 Faire:
Si nombre de regions actives < r, retourne faux
(r1,r2,l) = Q[i]
Si region[r1].index < 0 continue; //< région déjà fusionnée
Si region[r2].index < 0 continue; //< région déjà fusionnée
merge(r1,r2,l)
retourne vrai
}
```
Vous utiliserez une structure `Hierarchy::Candidate` pour stocker les candidats à la fusion ainsi:
```cpp=
/// Represents a possible merge between region r1 and r2.
struct Candidate {
int r1; // r1 < r2
int r2;
double lambda;
Candidate( int _r1, int _r2, float _lambda )
: r1(_r1), r2(_r2), lambda(_lambda) {}
};
```
Pour trier, utiliser `std::sort` avec la bonne fonction de comparaison sur les `lambda`.
:::danger
**A faire**. Ecrire la méthode `bool Hierachy::scaleClimbing(...)` et appelez-là après le calcul des superpixels. Mettez une touche `h` qui active ou non le calcul du scale climbing. Le mode `saliency` est beaucoup plus pertinent pour regarder le résultat du calcul. Vous obtiendrez des résultats similaires à ci-dessous.
|  |  |  |
| -------- | -------- | -------- |
| $N_{sp}=0$ | $N_{sp}=3, \lambda_{sp}=0$ | $N_{sp}=4, \lambda_{sp}=1$ |
:::
:::success
La hiérarchisation est beaucoup plus stable qu'auparavant, et encore plus si on choisit de partir des pixels ($N_{sp}=0$) plutôt que de super-pixels. Testez votre algorithme sur des images fixes aussi.
:::
## 4. Pour aller plus loin
### a. Meilleure fusion des couleurs (très facile)
Le critère de fusion mélange périmètre et aire multipliée par la somme des variances des 3 canaux rouge, vert, bleu. On peut un peu améliorer les résultats en tenant compte de notre propre perception des couleurs. On pourra essayer:
$$
\sigma_{rgb}^2 := 0.114 * \sigma^2(B) + 0.587 * \sigma^2(G) + 0.299 * \sigma^2(R).
$$
Faire une fonction `Region::variancePerceptuelle` et mettre une touche pour activer ou désactiver cette énergie. On définira opportunément une nouvelle énergie `D2` qui appelle cette fonction.
### b. Analyse des temps de calcul (facile)
On peut essayer de capturer empiriquement la complexité de l'agorithme de scale-climbing en stockant dans un fichier les temps de calcul.
On pourra tester l'influence sur le temps de calcul de:
1. la taille de l'image
2. le paramètre $N_{sp}$ donnant le nombre d'étapes de fusion super-pixels avant scale-climbing
3. le paramètre `prop` définissant la proportion de candidats fusionnés à chaque étape du scale-climbing.
### c. Energie de contour tenant compte du gradient de l'image (assez facile)
On peut tenir compte des différences de couleurs le long du contour de chaque région dans le critère de fusion. Si contour suit des pixels qui se ressemblent, alors il est naturel de vouloir fusionner, sinon on a envie de garder le contour séparant le plus longtemps possible.
Plutôt que de pénaliser par 1 chaque linel de contour entre 2 pixels $p$ et $q$, on va pénaliser par
$$
1-|I(p)-I(q)|/784, \quad \text{avec}\\
|I(p)-I(q)|=|R(p)-R(q)|+|G(p)-G(q)|+|B(p)-B(q)|
$$
Là encore, définir opportunément une nouvelle fonction d'énergie `C2` et choisir une touche pour activer/désactiver ce mode.
### d. Echelle d'interaction (moyen)
La mode `saliency` vous permet de discerner les différentes étapes de fusion. Parfois on veut juste la segmentation d'image à une échelle donnée. Comme on calcule toutes les échelles du scale-climbing, on peut les mémoriser dans un tableau. De plus on mémorise aussi dans l'image `saliency` le numéro de fusion (qui correspond à une échelle $\lambda$). On peut faire un slider qui choisit une échelle $\lambda$, et adapter l'affichage de `drawContour` ou `getSaliency` pour afficher les régions existantes à l'échelle spécifiée.
## 5. Evaluation
Pendant et à la fin de la séance, chaque groupe doit me montrer où il en est et ses réalisations fonctionnelles.