\chapter{What is to be done}
It took me 36 hours to read carefully and correct pages 1 through 180, September 2006.
\section{Global corrections to be done at the end}
\begin{itemize}
\item Correction dans Midway d'Adina Ciomaga:
Cher Jean-Michel,

Voici les petites remarques du chapitre 12.

page 159, Definition 12.4. - specification of an image on a cumulative Histogram
                 $\tilde u = G^{(-1)}\cdot H_u(u)$
                instead of two parenthesis.

page 160, Exercise 12.4. <<Prove that if we take as definition the cumulative histogram   $...$ >> and we define
the specification of an image on $G$ via the formula
              $\tilde u = G^{((-1))}\cdot H_u(u)$
then for two constant images $u=a$ and $u=b$ the midway image is not equal to $(a+b)/2$.

Tous les détailles sont sur la feuille que je vous ai donne vendredi. Je mentionne juste que les deux pseudo
inverses jouent un rôle de symétrie: notamment la formule (12.2) est vérifié, donc il faut applique PseudoInverse1
a la PseudoInverse2 et inversement.
 

\item insérer dans Midway le petit programme Matlab de Julie Delon:
Non midway n'est pas dans megawave, je l'avais envoyé à Lionel mais je crois qu'il était trop débordé pour
l'inclure dans la dernière version. Pour tes étudiants, il y a un moyen très simple de leur faire faire
l'expérience pourvu qu'ils aient un ordinateur avec matlab (ou équivalent) d'installé :

 si les 2 images sont u et
v (de même taille), il suffit de créer un vecteur x qui contient les valeurs ordonnées de u, un vecteur y qui
contient les valeurs ordonnées de v, et de moyenner ces deux vecteurs avant de respécifier les deux images u et v
sur ce vecteur moyen. En matlab, ça donne :
 [x,index] = sort(u(:));
 [y,index2] = sort(v(:));
 u(index) = 0.5*x+0.5*y;
 v(index2) =0.5*x+0.5*y;

\item faire un résumé pour le chapitre Midway
\item harmoniser la notation de la transposée: voir dans chapitreASIFTExperimental "transposee"
\item in Chapter ASIFT: the formula of Theorem 8.1 has to be deduced geometrically by affine projective geometry from
Fig. 8.3. In fact the formula is contravariant for $\psi$, $t$, $\phi$: $-\psi$, $t^{-1}$, $\phi$.
\item add back the Uccello painting to illustrate Fig. 8.2 and the affine approximation in the Taylor formula of 8.1
\item add a more complex curve evolution for Mackworth-Mockhtarian II
\item insert the new version of the gauss-aliasing study in SIFT-Formalization-v6
\item $\relative$ fait  un symbole bizarre: arranger
\item in notation and background : use $u$, not $f$ as generic function
\item compress the first ten pages of the  introduction
\item remove the last part of the introduction on Shape retrieval: replace by SIFT!
\item ?? Remove definition of periodization and figure, it is not considered necessary anymore (also the role of
$[-1,1]^N$ has decayed, probably also remove references to it
 \item define characteristic function of a set (notation, index)
\item add a figure to proposition 0.1 (homeomorphism of sphere and plane)
\item problem of $\bm x$ and $\fxx$ that sometimes do not look like the same: see introduction
\item replace everywhere $\setB$ by $\mathcal B$ and $\setT$  by $\mathcal T$ and $S_N$ by $\SN$
\item for each chapter give short but clear advice to implement the main algorithms: take all computing  assignments
that I gave to students and put them in the  book as a part of the exercise
section, but with a different style.
\item give short versions to all titles. Some are missing.
\item adapt the width of figures to maximal size allowed (in particular follow Mumford's advice : better show a piece
of the image or make it big enough to see details)
\item track all cross-references with explicit numbers (particularly chapters and sections and replace them by
references to labels! To do so, search : "roposition 1", "roposition 2", etc. (for all numbers between 1 and 9) and the
same with heorem, emma, ormula (in this case check "mula (" ),  efinition, xercise, orrolary, ... There are many!
\item Euclidean (no : Euclidian !), euclidean (no, euclidian), Laplacian, laplacian : choose!!
\item introduce to elementary topology (open, closed sets, compact sets, continuity and connectedness: in particular:
"where $X^\circ$ denotes the interior of $X$ and $\overline{X}$ denotes the closure of $X$"
\item  introduce to measure theory (borelians, measurable functions, negligible sets
\item : and ; glued to the former word. Check also ).
\item  an index of all notations is absolutely necessary
\item make a general index
\item make a list of figures
\item list of Figures like in the former Guichard-Morel version
\item decide whether we put uppercase or lower case when quoting a formula, a theorem, a proposition, a chapter, etc.
\item search everywhere $L_C$, $L_{C}$, $L^\infty_C$, $L^{\infty}_{C}$, etc and replace by $\cal F$.  Alternatively
search $C$
\item Find a good name for $\SMTCII$  operators : "Morpho" operators?
\item labels of figures must be inside the  caption to avoid mistakes
\item Track the notation $Curv$ and replace by $\bm{\kappa}$
\item curv is sometimes just italic and sometimes ${\rm curv}$. And sometimes the rm encloses u, which  is bad
\item check that all exercises end up with $\finex$
\item add references to the SIFT method in the applications of the heat  equation
\item check that in the integral the notation $dt$ is homogeneous: in fact $\rmd \tau$.
\item add a figure for the proof of Proposition \ref{limitedeuhestsolution} showing the plane $(t,\fxx)$ with the lines $t=nh$, the
positions of $\fxx_h$ and $\fxx$ and the ball around $\fxx$.
\item homogeneize also the notation for $measure$ ($meas$, ?)
\item arrange the proof of Theorem \ref{convergencemedianitere}. There is  a notation consistency problem since the holder estimate
is done   with $nh^2\leq t$ while the used convergence theorem must be with a median $k_{h^\frac 12}$.  See also how
the problem bounces back for the of convergence of iterated filters toward  the snake equation!
\item check titles of sections upper or lower case.
\item check size of captions in new figures (snakes). Is the caption font the same as the rest of the text?
\item
ARRANGE TEX IN FIGURE fig04.03.1.eps
\item Do a figure for Theorem \ref{{theorem4.5}}  and Proposition \ref{figureafaire}.
\item redo  figure \ref{fig43} (Latex bizzare in this  figure).
\item METTRE APRES THEOREM \ref{Graysontheorem} UNE FIGURE D'EVOLUTION DE DEUX FORMES BRUITEES DIFFEREMMENT MONTRANT LA CONVERGENCE
\item In section \ref{Ilmanque}, an experiment on affine invariant scheme is missing, namely Figure \ref{figure_amss_affine_char}
 is
referenced but  missing.
\item Refer to the problem of the definition of generalized curve shortening and its equivalence with MCM and the
outcome a scale invariant median (cite Adina Ciomaga).

 \end{itemize}

\subsection*{Missing chapters or sections}

\begin{itemize}
\item METTRE DANS CHAPITRE Main Curvature Equations, section 1, UNE FIGURE D'EVOLUTION DE DEUX FORMES BRUITEES
DIFFEREMMENT MONTRANT LA CONVERGENCE


\item snakes
\item non flat, whose used labels are : nonflat, ChapNonflat
\item  movies
\item schemes
\item textures
\end{itemize}

\subsection*{Comments chapter by chapter}

\begin{itemize} \item {\bf Introduction:}
\item not clear whether the introduction should'nt be spread over most chapters. In some extent it discloses what is
being done in the chapters but in a wide extent it contains extensions which can become exercises or bibliographical
comments (and there is much overlap between the introduction  and the chapters for these bibliographical comments.)

\item Include in the introduction a very brief list of chapters with what is being done in each.


\item Insert in the Finite difference scheme or a chapter on affine scale space the following image:

\begin{figure}[!htb]
\centerline{\psfig{figure=moisan_image_noisy.eps,width=75mm}} \vspace{3mm}
\centerline{\psfig{figure=moisan_curves_noisy.eps,width=75mm}} \vspace{3mm}
\centerline{\psfig{figure=moisan_curves_smooth.eps,width=75mm}} \caption{ Smoothing curves with the Affine Scale Space.
Top: a text image corrupted by noise. Middle: thresholding the image reveals characters as irregular level lines.
Bottom: the same level lines, smoothed with the affine scale space. The smoothing process produces curves almost
independent of the noise, which is a requirement for robust pattern recognition.  Algorithm used follows the affine
erosion introduced in \cite{Moisan}. -Experiment courtesy of Lionel Moisan-} \label{fg-affineshapesmooth}
\end{figure}


\item Exercice à vérifier : 12.3 (iii)

\item Exo 12.1 : prendre g stritement croissante. Changer la notation pour g qui apparaît deux fois.
\end{itemize}

\item Insert in Chapter on Affine math. morpho a couple of photographs of a painting taken from different angles at
some distance, displaying roughly parallelograms.

\item Arrange figure fig15.01.1.eps (realign)

\section{Add in the  bibliography gmBiblio.bib}

\section{Devoirs numériques à intégrer}


------------------------------------------------------------

DEVOIR 1 sur les chapitres 1 et 2 :

a) Exercices recommandés: Lecture très attentive des démonstrations du chapitre 1 Exercice 1.1 Exercice 1.2 Exercice
1.3 Exercice 2.1 Exercice 2.4



b) Manipulations sur ordinateur:

-calculer et visualiser le gradient d'une image (ne visualiser que les gradients supérieurs à un seuil, typiquement 5
ou 10)

-refaire la même opération  après convolution de l'image avec une gaussienne

-Faire les expériences décrites dans les figures 1.1, 1.3 et 2.2 et en faire des variantes.
--------------------------------------------------------

DEVOIR 2 sur les chapitres 3 et 4:

a)  Exercices recommandés:

Exercice 3.1 (Erratum : rajouter les parenthèses:  |Du(...)|

b) Manipulations sur ordinateur:

-Faire sur une image une moyenne locale itérée où on remplace la valeur en un pixel par la moyenne des neuf pixels
formant un carré 3x3 autour.

-Faire sur une image un filtre médian itéré où on remplace la valeur en un pixel par la la valeur médiane des neuf
pixels formant un carré 3x3 autour.

Comparer ces deux  algorithmes

-essayer l'algorithme de Bence-Merriman-Osher sur une forme simple avec des gaussiennes de tailles variables.

===============POLYCOPIE COMPLET==========================
Vous pouvez le télécharger à l'adresse

http://www.cmla.ens-cachan.fr/Utilisateurs/morel/MVAPolycopieMorelOctobre2006.pdf

Un tirage de la deuxième partie du polycopié (pages 77 à 205) sera effectué dans les délais les plus brefs possibles.

===============DEVOIR N° 3================================
Le devoir n° 3 vous demande de:

-lire attentivement le chapitre 4 -faire l'exercice 4.1

Expérimentation sur ordinateur:

Implémenter l'équation de la chaleur sur une courbe polygonale paramétrée par sa longueur (Mackworth-Mokhtarian I)
Implémenter l'équation de la chaleur renormalisée (Mackworth-Moktharian II)

Cela donne:

Algorithme 1 -paramétrer la courbe de départ $x_0(s)$ par la longueur -convoler chaque coordonnée avec une "grosse"
gaussienne de paramètre t


Algorithme 2 A l'étape n: -paramétrer la courbe $x_n(s)$ par sa longueur -convoler chaque coordonnée de $x_n$ avec une
"petite" gaussienne de paramètre h pour obtenir $x_{n+1}$. Itérer.

Comparer les résultats sur la même  courbe quand t=nh Construire  une courbe en  "peigne" telle que l'Algorithme 1 la
fasse se croiser elle-même.

===============DEVOIR N°4==============================
Je vous le donne d'avance. Il consiste en:

-faire tous les exercices du chapitre 5. L'exercice 5.9 est toutefois facultatif.  Tous les autres se font en deux ou
trois lignes.

Expérimentation sur ordinateur:

-binariser une image en la seuillant à sa valeur médiane -implémenter le "principe de superposition" qui permet de
sélectionner des ensembles de niveau est de reconstruire à partir de ces ensembles de niveau seulement -faire la
manipulation suivante:

a) filtre médian sur une image u_0, ce qui donne w = med u_0 b) même filtre médian sur chaque ensemble de niveau de u_0
c) construire par superposition une image v à partir de ces ensembles de niveau filtrés d) vérifier que v=w !!!

=============================DEVOIR n° 5========================

EXERCICES:

Il y a 20 exercices dans le chapitre 7. Essayer d'en faire le plus possible, si possible tous. Les exercices de la fin
donnent les exemples et contrexemples permettant de comprendre les hypothèses des théorèmes permettant de passer d'un
filtre d'ensemble à un filtre de fonctions et vice-versa.

EXPERIMENTATION:

La grande et belle chose à tester est le "tueur d'extrema". Vous avez le choix de l'implémenter, ou d'utiliser une
version auto-duale de ce fitre dans MegaWave, dont le nom est fgrain.   L'implémentation du tueur d'extrema est plus
délicate que celle des filtres précédents. Vous pouvez l'implémenter comme un filtre à pile en utilisant un programme
de calcul des composantes connexes, ou directement sur l'image en partant des maxima, puis des minima.


Vous pouvez essayer ce filtre sur des images avec diverses valeurs pour la surface du grain, et faire la différence
entre le résultat Tu et l'image u.

-Si l'aire est inférieure ou égale à 10 environ vous ne verrez presque pas de différence entre l'image et l'image
filtrée.

-appliquer un bruit impulsionnel à l'image. Cela consiste à tirer au hasard une certaine proportion de pixels (de 10% à 70%) et à remplacer la valeur du pixel par une valeur aléatoire.

-appliquer le filtre de grain à l'image bruitée. Trouver expérimentalement la valeur de l'aire qu'il faut choisir pour
restaurer l'image.

-Vous verrez que la restauration peut être très bonne, voire spectaculaire.

-toutefois des défauts restent dans l'image après application  du filtre. Lesquels?  montrer qu'on améliore encore un
peu la restauration en appliquant un petit filtre médian.

-comparer les résultats de restauration avec ceux obtenus avec un filtre médian itéré appliqué directement.  Vérifier
qu'un filtre médian avec petit voisinage itéré marche mieux qu'un filtre médian avec un gros voisinage.

%================
Chapitre 8
%================

Plusieurs d'entre vous m'ont demandé de préciser les expériences à mener pour le chapitre 8. Les voici. Je m'excuse
pour  le retard  à répondre.

-Implémenter un algorithme qui, étant donné un ensemble de sous-ensembles de pixels $\mathcal B$, calcule

$$Tu(x):=\sup_{B\in \mathcal B}\inf_{y\in x+B}u(y).$$

Essayer pour $\mathcal B$:

a) le cas où $\mathcal B$ est réduit à un seul ensemble, notamment un point (pas nécessairement 0), une paire de
points, une boule, un intervalle centré en 0 et tout autre ensemble que vous aurez en tête.

b) le cas où $\mathcal B$ est invariant par le groupe des rotations: prendre par exemple tous les intervalles de
longueur fixe centrés en 0, ou toutes les paires de points centrées en 0.

c) le cas où $\mathcal B$ est appromiativement invariant par transformée linéaire de déterminant 1: prendre toutes les
ellipses discrètes d'aire fixée.

d) essayer à chaque fois l'opérateur dual, $\inf\sup$. Visualiser aussi $Tu-u$.

Inventez d'autres ensembles structurants intéressants! Essayez d'en trouver un auto-dual! (T(-u)=-T(u)).

%=======================================

Chapitres 9 et 10:
%++++++++++++++++++++++++++++++++++++++++++
-expérimentation: implémenter dilatation, érosion pour diverses formes, convexes et non convexes de l'élément
structurant. Par exemple B est un point (différent de 0), B est une paire de points, B est un segment centré en zéro.
Implémenter également ouverture et fermeture avec les mêmes opérateurs. Vérifier ainsi, en suivant les idées des
expériences menées dans le chapitre,

-implémenter le médian pour diverses formes de k.  Vérifier que si on fait le médian sur un nombre impair de pixels il
est autodual et que si on le fait sur un nombre pair il ne l'est pas.

-tester ces opérateurs en ajoutant du bruit impulsionnel sur les images et en ajoutant ou enlevant des lignes (une
perturbation classique pour le fax et les vieux films).
%=====================================================

Chapitres 11, 12, 13:
%++++++++++++++++++++++++++++++++++++++++++++++++++

Il faut implémenter le schéma numérique  (FDS) de la mean curvature motion, l'appliquer à une forme, et "seuiller à
128" pour afficher l'évolution de la forme et afficher aussi la valeur absolue, la partie positive et la partie
négative de la différence entre deux itérations, pour voir que cela correspond à un détecteur de coins.

Il faut également comparer une longue itération du FDS avec une longue itération  du médian itéré pour se convaincre
que le médian itéré discret est aveugle aux courbures trop petites. En fait le médian itéré s'arrète et ne fait plus
rien au bout de quelques itérations alors que le FDS de la mean curvature motion continue jusqu'à ce que toutes les
lignes de niveau de l'image deviennent droites (le vérifier sur  une petite image).

Enfin il faut faire l'exercice d'implémentation de l'érosion et de la dilatation par EDP (ci-joint, exercice 9.4).



Implémenter le FDS de AMSS (affine curvature motion), qui est une variante du précédent. Là, l'exercice amusant est de:


¤ Appliquer une distorsion affine à une image (du type v(x,y)= (Au)(x,y)=: u(2x+y, y/2), de sorte que vous ayiez une
vraie distorsion affine transformant un carré en parallélogramme).

¤ Comme la distorsion précédente est de déterminant 1, vous devez vous attendre à ce que les deux  images suivantes
soient semblables:

-(FDS)^n (u) -A^{-1}(FDS^n (Au))= A^{-1}(FDS^n(v)),

où A^{-1} désigne l'inverse de la matrice à deux lignes et deux colonnes, A= (2, 1// 0 1/2) et FDS^n désigne
l'itération n fois du FDS.


%%%%%%%%%%%%%%%%%%%Chapitres 19 et 20%%%%%%%%%%%%%%%%%%%%%%%%
M'étant rendu compte en révisant les deux chapitres que je viens d'exposer, je viens de me rendre compte qu'ils avaient
dangereusement peu d'exercices et qu'en conséquence vous aviez fort peu de travail. Aussi, je me permets de vous
renvoyer ces deux chapitres, corrigés et avec quelques exercices en plus (attention, la première page est blanche).

Je précise aussi les manipulations que vous pouvez faire pour déterminer si les théorèmes prouvés sont effectifs.

Nous disposons de trois schémas numériques pour lisser une forme, théoriquement équivalents:

A) Prendre la courbe de Jordan qui entoure la forme et lui appliquer Mackworth-Mokhtarian II (lissage gaussien itéré et
alterné avec une reparamétrisation de la courbe par sa longueur).


B) Median itéré (Bence, Merriman, Osher). Le voisinage peut  être gaussien, ou même juste une boule discrète.

C)  FDS : une implémentation en différences finies de la mean curvature motion, suivie d'un seuillage à 1/2 (à 127,5 si
la forme est blanche (255) sur fond noir (0))


Chacun de ces schémas génère une succession de formes, obtenues après chaque itération. L'ennui, c'est que les temps ne
sont pas calibrés. Chacun des algorithmes étant itératif, à chaque image est associée son "temps" dans l'algorihtme,
qui est juste le nombre d'itérations qui l'a produite.

Le problème pratique est de déterminer une correspondance entre les temps de chaque algorithme, qu'on appelle une
calibration temporelle.

Pour ce faire, on utilise une image faite de disques noirs de différents rayons entiers n et on détermine pour chaque
algorithme le nombre d'itérations f(n) auquel le cercle de centre n disparaît.

Appelons f(n), g(n) et h(n) les temps pour les trois algorithmes concernés. La mise en correspondance de ces temps
donne la calibration en un temps unique qui leur est commun, que l'on peut appeler le "temps de disparition d'un disque
de rayon n".


Vous  vérifierez alors en faisant l'image de différence (et en regardant) qu'une forme évolue presque  de la même
manière par les trois algorithmes.  Toutefois, vous  verrez que ceci est faux pour le median itéré, qui  stoppe quand
la courbure est trop petite.  Aussi, on ne peut comparer favorablement le filtre médian aux deux autres algorithmes que
pour des formes ayant  des courbures assez grandes.


%%%%%%%%%%%%%%COMMENTAIRES ET REPONSE%%%%%%%%%%%%%%%%%
Chacun des algorithmes est consistent, c'est-à-dire qu'il est tangent à la bonne évolution à chaque instant. Mais il y
a un terme d'erreur et ces erreurs s'accumulent et se propagent. Pour avoir parfaite adéquation des algorihtmes il faut
faire effectivement nh\to t, donc h tend vers zéro (un très petit pas de temps, ce qui veut dire un très petit
voisinage : ce n'est pas possible pour FDS).

La différence peut en particulier être due au fait que FDS n'est pas vraiment invariant par rotation à cause des effets
des discrétisations axiales. Pour le voir, faire tourner la forme de pi/4 ou pi/8 et comparer FDS avec le FDS composé
avec cette rotation, puis la rotation inverse.

Le FDS ferait évoluer chaque ensemble de niveau selon l'EDP s'il était contraste invariant, mais le schéma ne l'est pas
du tout! Il y a un terme d'erreur, que l'on peut essayer d'ailleurs d'écrire en poussant le développement de Taylor
plus loin.

L'idée de seuiller à 1/2 est que pour cette valeur on a un algorithme qui est autodual (invariant par u \to 255-u), ce
qui veut dire qu'il n'y a aura pas en pratique d'effet de type dilatation ou érosion.

Pour voir cet effet, prenez un cercle blanc sur fond noir et un cercle noir sur fond blanc dans une image séparée en
deux (Heaviside). C'est seulement en seuillant à 127,5 que vous devriez observer que les deux cercles évoluent à la
même vitesse.

Merci de ces questions, et de me dire ce que cela donne.


Bien cordialement, JMM

Maël Primet a écrit :

> Bonjour,
> lorsque je compare les algorithmes, même si le 'ratio' trouvé en faisant
> disparaître des cercles de différentes tailles est stable (quelque soit
> la taille du cercle), lorsque je compare des figures, l'alignement entre
> la courbe MM2 et la forme pour le FDS ne sont pas parfaitement alignés,
> même si elles se ressemblent plus ou moins. Est-ce que c'est juste les
> erreurs de calcul, d'approximation, etc., ou est-ce qu'il y a réellement
> moyen de faire coller ces formes "au plus près" ?
>
> Autre chose, il me semble que le FDS fait évoluer chaque ensemble de
> niveau selon l'EDP, mais crée des "nouveaux niveaux". Puisque l'on part
> d'une image binaire, pourquoi est-ce que l'on seuille à 127.5 et pas à
> 255 puisqu'a priori, le niveau 255 évolue depuis le début comme il
> devrait ?
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
