%% LyX 1.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
%\textheight26cm
%\textwidth15.5cm
%\hoffset-2cm
%\voffset-3cm

%chargement des drivers Subfigures
\usepackage{french}
\usepackage{subfigure}
%chargement des drivers EPIC et EEPIC
\usepackage{amsfonts}
\usepackage{fullpage}
\sloppy

% Chargement des drivers Postscript
\input{psfig}

%%%%%%%%%%%%%%%
\makeatother

\begin{document}


\title{\textbf{\huge TTI :TP}{\huge }\\
 {\huge }\textbf{\huge Segmentation par Fusion de régions}  }


\author{\textbf{2 séances}}

\maketitle

\section{Objectifs}


\subsection{Algorithme}

Le but de ce TP est de réaliser un algorithme de segmentation par fusion de
régions en manipulant le graphe d'adjacence des régions. La segmentation recherchée
doit vérifier~:

\begin{itemize}
\item toutes les régions sont connexes
\item le critère d'homogénéité \( D(R)<seuil \) est vrai pour chaque région, et faux
pour 2 régions adjacentes.
\end{itemize}
L'objectif est de produire l'image d'etiquettes de la segmentation obtenue.


\subsection{Mise en oeuvre}

Pour réaliser cette segmentation, vous disposerez d'une bibliothèque C++ que
l'on peut se procurer gratuitement sur certains sites ftp. Il s'agit de la bibliothèque
LEDA contenant des classes graphes, listes etc.... Vous allez ainsi être confronté
à des structures C++ complexes. Une documenation HTML en anglais vous est cependant
accessible.

En raison de la complexité de l'algorithme à mettre en oeuvre, la plupart des
méthodes vous seront fournies.


\section{Description de l'algorithme}

Le principe de l'algorithme est le suivant~:

\begin{itemize}
\item on produit une segmentation initiale de l'image (ici, on prendra un pixel=1
région).
\item on construit le graphe d'adjacence associé~: c'est un graphe valué non orienté
de type \textsl{UGRAPH}.

\begin{itemize}
\item chaque noeud représente une région ; les attributs de la régions sont conservés
dans un objet de type \textsl{RegionAttrib} associé au noeud.
\item deux noeuds sont reliés par un arc si ils représentent deux régions connexes
(on choisit la 4-connexité) ; la distance entre les deux régions est conservée
dans un objet de type \textsl{ArcAttrib} associé à l'arc.
\end{itemize}
\item on fusionne ensuite les régions jusqu'à obtention de la segmentation finale~:

\begin{itemize}
\item on cherche l'arc de valeur minimale. Celui-ci correspond aux 2 régions les plus
semblables.
\item on fusionne les 2 régions
\item on remet à jour les arcs adjacents
\end{itemize}
\item lorsqu'il n'existe plus d'arc de valeur inférieure au seuil, la segmentation
finale est obtenue. On crée alors l'image d'étiquettes.
\end{itemize}

\section{A faire}

Vous aurez principalement trois méthodes à programmer~:

\begin{itemize}
\item le main~: l'algorithme vous est donné sous forme de commentaires. Chaque commentaire
correspond à une ligne de code à écrire. Vous devrez rechercher dans les fichiers
régions.{*} les méthodes répondant à vos attentes.
\item la méthode \textit{void AdjGraph::merge\( _{-} \)adj\( _{-} \)regions(edge
e)}~: il vous faudra ici trouver le corps de l'algorithme. Cette méthode doit
permettre~:

\begin{itemize}
\item de fusionner deux régions en une seule
\item de lui associer la plus petite des deux étiquettes
\item de mettre à jour la table des synonymes
\item de remettre à jour le graphe (rajouter les nouvelles arêtes)
\end{itemize}
Vous utiliserez pour l'implémentation les méthodes proposées par LEDA ainsi
que celles déja implémentées dans le fichier region.cc.

\item la méthode \textit{Image\( < \)int\( > \) AdjGraph::create\( _{-} \)label\( _{-} \)ima
(const int nbl, const int nbc)} qui vous permettra de construire l'image d'étiquettes
à partir de la table des synonymes (celle-ci ayant été préalablement mise à
jour).
\end{itemize}
Vous donnerez également un ou plusieurs critères de fusion un peu plus compliqués
que max-min mais qui permettent d'obtenir de meilleures segmentations. Vous
motiverez votre choix. Si le temps vous le permet, vous pourrez modifier les
structures qui vous sont données afin de prendre en compte ce critère que vous
pourrez alors tester.


\section{Données}

\begin{itemize}
\item LEDA~: l'ensemble des includes de la librairies LEDA est disponible sous le
répertoire \\
 tptti/tp6/LEDA/incl/LEDA. La documentation HTML est quant à elle disponible
à l'adresse~:\\
 /home/junon/d02/diic2/donnees/unix/tptti/tp6/LEDA/MANUAL/MANUAL.html
\item Vous disposez également d'une petite image test: image-raw.pgm
\end{itemize}
\textbf{REMARQUE~:} avant de pouvoir éxecuter votre programme veiller à taper
une fois la commande~: \\
 \hspace*{-1.5cm}setenv LD\( _{-} \)LIBRARY\( _{-} \)PATH~\char`\"{}/home/junon/d02/diic2/donnees/unix/tptti/tp6/LEDA:\( \$ \)\{LD\( _{-} \)LIBRARY\( _{-} \)PATH\}\char`\"{}

\end{document}