---
title: INFO911 (5g) Représentations des régions, des contours, des hiérarchies
type: slide
slideOptions:
transition: slide
progress: true
slideNumber: true
---
# Représentations des régions, des contours, et des hiérarchies
## (Traitement et Analyse d'Image 5g)
>
> [name=Jacques-Olivier Lachaud][time=Decembre 2020][color=#907bf7] Laboratoire de Mathématiques, Université Savoie Mont Blanc
> (Les images peuvent être soumises à des droits d'auteur. Elles sont utilisées ici exclusivement dans un but pédagogique)
###### tags: `info911`
Retour à [INFO911 (Main) Traitement et analyse d'image](https://codimd.math.cnrs.fr/s/UE_B59gMy)
---
# Topologie des domaines discrets
==Topologie== = études des lieux. Il faut décider qui est voisin de qui.
| 4-adjacence| 8-adjacence | d'autres sont possibles ! |
| -------- | -------- | -------- |
|  |  | 6-adjacence non isotrope |
Soit un ensemble $S$ de pixels, $S$ est ==4-connexe== ssi $\exists$ un chemin dans $S$ de pixels 8-adjacents entre n'importe quelle paire de pixels de $S$ (même principe pour 8).
---
## Frontière d'une région
==Frontière== d'une région 8-connexe $R$, ensemble des points de $R$ 4-adjacents à $\mathbb{Z}^2 \setminus R$.
==Frontière== d'une région 4-connexe $R$, ensemble des points de $R$ 8-adjacents à $\mathbb{Z}^2 \setminus R$.
| Frontière 8-connexe | Frontière 4-connexe |
| --------------------------------------------------------------------------------------------------------- | --------------------------------------------------------------------------------------------------------- |
|  |  |
| => chemin 8-connexe | => chemin 4-connexe |
---
## Difficultés de ces définitions (Paradoxe de Rosenfeld)
1. 2 régions adjacentes n’ont pas de portion de frontière commune
2. une frontière 8-connexe n'est pas séparante en deux comp. 8-connexes distinctes.
3. une frontière 4-connexe peut séparer plus de 2 comp. 4-connexes distinctes.
| Int. et ext. sont 8-adjacents | 2 composantes 4-connexes |
| ----------------------------- | ------------------------ |
|  |  |
---
## Solution(s) au paradoxe de Rosenfeld
Choix de connexité différente pour objet et fond !
- soit 4-adjacence pour l'objet et 8-adjacence pour le fond
- soit 8-adjacence pour l'objet et 4-adjacence pour le fond
:::info
==Thm== Si on a un contour 4-connexe (resp. 8-connexe) **simple** de taille $\ge 4$ alors il sépare l'image en 2 composantes 8-connexes (resp. 4-connexes), l'une est finie.
:::
E.g. détecteur de Canny: contours 8-connexes, régions 4-connexes
---
## Frontières interpixel
Autre approche, codées entre des points à coordonnées 1/2 entières.
:::success
Frontière commune entre 2 régions adjacentes
Bonne propriétés si vous choisissez 4-adjacence pour région et 8 pour le fond.
Extensible en dimension quelconque
:::
---
---
## Extraction de composantes connexes par balayage
==Objectif== Même étiquette pour tous les pixels même région
2 parcours (4-connexe): balayage avant, puis arrière
au début: $\infty$ partout
| balayage avant $\begin{array}{c}\rightarrow \ldots \rightarrow \swarrow\\ \rightarrow \ldots \rightarrow \swarrow \end{array}$ | balayage arrière $\begin{array}{c}\nearrow \leftarrow \ldots \leftarrow \\ \nearrow \leftarrow \ldots \leftarrow \end{array}$ |
| ------------------------------------------------- | -------- |
| $\begin{array}{ccc} & & \fbox{k } \\ & & \downarrow \\ \fbox{n } & \rightarrow& \min(k,n) \\ \end{array}$ | $\begin{array}{ccc} \min(k,n) & \leftarrow & \fbox{k } \\ \uparrow & & \\ \fbox{n } & & \\ \end{array}$ |
Si $k$ et $n$ sont $\infty$ et que la case appartient à la région, on lui donne un nouveau label.
---
## Exercice
Lancez l'algorithme d'extraction de composantes connexes par balayage sur:
$$
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}\hline
. & . & . & O & . & O & O & O & O & O & .~ \\ \hline
. & O & O & O & . & O & . & . & . & O & .~ \\ \hline
. & O & O & . & O & O & . & O & . & O & .~ \\ \hline
. & . & O & . & O & . & . & O & . & O & .~ \\ \hline
. & O & O & . & O & O & O & O & O & O & .~ \\ \hline
\end{array}
$$
---
## Suivi de contour interpixel
Choix d'une connexité objet et fond.
Point de départ à l'interface objet et fond.
Observation de configurations locales 2x2.
---
# Codage des régions
Plusieurs codages, plus ou moins adaptés à des algorithmes
==image de labels== simple, adaptés aux agrégations, codage implicite des frontières
==codage par plages== simple, plus compact, moins adapté aux modifications
==codage par frontières== plus pratique pour calculer la géométrie, moins pour le reste
==graphe d'adjacence de régions== simple, haut niveau, agrégations ok, géométrie faible
==cartes== plus complexe, assez complet, géométrie/fusion/division
---
## Image de labels
Image I, image de labels L
Pixels $p,q$ dans la même région si et seulement si $L[p] = L[q]$
:+1: simple, adaptés aux agrégations, $region(p)$ en temps $O(1)$
:-1: codage implicite des frontières, géométrie ?
---
## Codage par plages
Chaque région a une liste de lignes contenant des intervalles
:+1: simple, plus compact, $region(p)$ en temps $O(\log n)$
:-1: certaines modifications complexes, géométrie ?
---
## Codage par frontières
| Frontières pixel | Frontières interpixel |
| -------- | -------- |
|  |  |
:+1: contours donnent la géométrie, fusions
:-1: complexe en cas de modification, inclusion entre régions ?
---
## Graphe d'adjacence de régions
(Utilisé avec image de labels, ou codage par plages)
:+1: simple, haut-niveau, agrégation/fusions
:-1: géométrie ?
---
## Cartes combinatoires
Structure décrivant ==exactement== la topologie des partitions du plan
| Etiquetage | Géométrie| Topologie/structure |
| -------- | -------- | -------- |
|  |  |  |
$\alpha \ \text{arêtes}, \sigma\ \text{sommets}\quad$
==cartes== plus complexe, assez complet, géométrie/fusion/division
---
## Cartes combinatoires (2)
$\phi=\sigma \circ \alpha\quad$
:+1: Peut tout faire :-1: plus complexe à coder
---
# Structures hiérarchiques (images, partitions)
Les images ou les partitions requièrent souvent une analyse multi-échelle
==pyramides== simplification hiérarchique régulière rigide des images
==quadtree== découpage hiérarchique régulier mais adaptatif
==pyramides irrégulières== découpage hiérarchique irrégulier
---
## Pyramides
Très utilisé en "scale-space image analysis".
Filtre ==passe-bas== entre chaque étage $\uparrow$
=> résume l'image en dessous à différentes échelles
`video-pyramid`
---
## Quadtree
Forme abrégée de pyramides => plus compact
| Feuilles quadtree | quadtree |
|:--------------------------------------------------------------------------------------------------------:|:--------------------------------------------------------------------------------------------------------:|
|  |  |
---
## Pyramide irrégulière
Pyramide issue de fusions en parallèle de régions
1. sélection de survivants non voisins 2 à 2 (min variance)
2. fusion non-survivants -> survivants (le plus ressemblant)
---
## Pyramide irrégulière (2)
3. on répète le processus
