Dix-neuf méthodes de seuillage sont présentées dans cette annexe. Les dix premières sont explicitées dans un article de synthèse (voir Article:Survey) écrit par des traiteurs d'images ; la onzième a été construite par nous à partir de considérations faites à propos de la méthode d'analyse spectrale music ; et les deux suivantes sont utilisées entre autres pour le débruitage de signaux à partir de leur décomposition en paquets d'ondelettes : voir Rapport:Don1 et Rapport:Don3. Nous trouvons ces références aux adresses http suivantes :
http://stat.Stanford.EDU/reports/donoho
La quatorzième est celle proposée par Sahoo, Soltani et Wong dans Article:Survey ; et la dix-neuvième est une amélioration de cette méthode, due à quelques constatations que nous avons faites. Les autres ont été glanées ici et là. Bien sûr, nous ne prétendons pas avoir été exhaustif : certainement, un grand nombre d'autres méthodes de seuillage existent.
Nous considérons chacune de nos fonctions d'observation. Ses échantillons se répartissent en deux classes. Il s'agit de discriminer ces classes. Si nous supposons que les observations correspondant à chacune de ces deux classes obéissent à des suites aléatoires gaussiennes, la première, correspondant aux parties stables du signal, a une moyenne et une variance petites, alors que la seconde, correspondant aux pics à détecter, a une moyenne plus grande et une variance elle aussi plus grande. De plus, la première classe est représentée par la très grande majorité des échantillons : la seconde classe est représentée par très peu de points.
Nous classons par ordre de grandeur les échantillons, du plus petit au plus grand. Le tableau 
est obtenu. Nous déterminons les valeurs 
. Nous faisons l'hypothèse que les deux modes sont bien séparés, c'est-à-dire que nous supposons qu'il y a, une fois que nous avons classé les échantillons de la fonction d'observation par ordre de grandeur, un saut brusque quand nous passons d'un mode à l'autre. Nous supposons que le contraste est important. Le moment de la cassure a lieu dès que le saut 
dépasse un certaine valeur 
, fixée. Le problème est de déterminer la valeur 
du saut limite.
En fait, nous avons utilisé plutôt cet algorithme :
de taille 
en ordre croissant (nous obtenons 
)
(pour 
variant de 
à 
)
(nous ne prenons pas en compte les sauts concernant les plus petits échantillons et ceux concernant les plus grands) nous donne le plus grand saut (contraste) : 
et son indice 
dans le tableau des sauts
(au lieu de 
comme dans la section ssec:primetsau)
qui, avec le signal du premier test effectué ci-dessous (voir la section tests, pour plus de détails au sujet des tests), nous donne les meilleurs résultats pour des valeurs de 
de l'ordre de 
-- 
.
est un paramètre libre, que nous avons fixé : dans la suite, nous avons travaillé avec 
.
Voir les figures con1, con2 et con3 pour les résultats de la méthode avec les tests définis dans la section tests.
Il s'agit de la méthode utilisée dans le programme tran original de Laurent Cerveau : voir la section tran de la partie part:seg_mon_har. Appelons 
la fonction d'observation : le programme tran nous fournit 
.
Nous calculons l'histogramme 
de l'ensemble des 
. Celui-ci présente deux modes : l'un, proche de 1 (ce mode correspond à une dissemblance maximale entre les deux modèles : l'une des fenêtres d'analyse couvre une partie d'une note et l'autre une partie d'une autre note), correspondant à l'état instable ; et l'autre, proche de 0 (ce mode correspond à une dissemblance minimale : les fenêtres d'analyse couvrent deux parties de la même note), correspondant à l'état stable. Il s'agit donc de déterminer la position 
de la césure séparant ces deux modes. Les marques de segmentation sont posées aux instants 
tels que : 
.
Nous déterminons les 
minimums locaux de l'histogramme , c'est-à-dire tous les points 
tels que 
, pour 
variant de 2 à 
, 
étant le nombre de cases de l'histogramme, numérotées de 
à 
.
Pour chacun de ces 
triplets de points 
, 
, 
, nous déterminons le polynôme d'ordre 2 qui passe par ses trois points. La position de césure possible 
correspond à la valeur à laquelle s'annule la dérivée du polynôme, et le minimum correspondant est 
.
La valeur minimale de l'ensemble 
à 
éléments est déterminée. La position optimale 
de la césure est la position 
, avec 
tel que 
est la valeur minimale de l'ensemble 
.
Des discussions sur les justifications de cet algorithme, sur le nombre de classes à prendre pour l'histogramme, etc. sont disponibles dans Rapport:Cerveau.
Voir les figures his1, his2 et his3 pour les résultats de la méthode avec les tests définis dans la section tests.
Cette extension n'est pas implémentée dans le programme segmentation. Elle correspond à une approche probabiliste de l'exploitation de l'ensemble des 
.
Nous supposons que les densités de probabilité des variables aléatoires 
et 
sont des gaussiennes. Il s'agit d'approximer au mieux, par les moindres carrés par exemple, l'histogramme par la somme de deux gaussiennes de moyennes 
et 
, de variances 
et 
, et de probabilités a priori 
et 
inconnues.
Une fois que nous avons estimé 
, 
, 
, 
, 
et 
, nous pouvons utiliser la stratégie classique permettant de déterminer 
, c'est-à-dire celle de Bayes.
Le critère de Bayes consiste à minimiser une fonction de risque, qui évalue le << coût >> d'une mauvaise décision. En général, la probabilité d'erreur est choisie comme fonction à minimiser.
Il y a deux configurations :
:
Si en plus 
, 
.
) :
Cette méthode est basée sur l'histogramme 
normalisé 
de la fonction d'observation.
Il s'agit de maximiser la variance inter-classes 
suivant 
le numéro de la case de l'histogramme courante. Cette variance inter-classe est égale à :
Avec :
et 
Et, si nous posons :
et 
avec :
et
Soit 
l'abscisse de la case 
de l'histogramme. Le seuil est égal à 
, où 
est le 
tel que 
soit maximale.
Voir les figures ots1, ots2 et ots3 pour les résultats de la méthode avec les tests définis dans la section tests.
Cette méthode est basée sur l'histogramme 
normalisé 
de la fonction d'observation.
Les entropies a posteriori des deux modes (mesures de l'information a posteriori associée à chaque mode) sont respectivement (avec 
le numéro de la case de l'histogramme courante) :
et 
Il s'agit de maximiser suivant 
le terme 
.
Pun prouve qu'il est équivalent de maximiser 
suivant 
le numéro de la case de l'histogramme courante, avec :
où :
et
et
Voir la figure pu11 pour les résultats de la méthode avec les tests définis dans la section tests.
Nous supposons que nous connaissons le nombre de marques à détecter. En traitement de l'image, cela correspond à : nous savons que cet objet occupe 
des pixels.
Dans notre cas, si nous supposons qu'un échantillon sur dix correspond à une transition, il s'agit simplement de ne garder que les 
plus grands.
Cette méthode est basée sur l'histogramme 
normalisé 
de la fonction d'observation.
Cette fois, nous considérons le coefficient d'anisotropie 
:
où 
est le plus petit entier tel que :
et où 
(numéro de la case de l'histogramme courante : le 
correspondant est le seuil) est tel que :
Voir la figure pu21 pour les résultats de la méthode avec les tests définis dans la section tests.
Cette méthode est basée sur l'histogramme 
(non normalisé) de la fonction d'observation. Nous avons :
et
avec : 
Il faut maximiser suivant 
le terme 
.
Voir les figures kap1, kap2 et kap3 pour les résultats de la méthode avec les tests définis dans la section tests.
Cette méthode est basée sur l'histogramme 
normalisé 
de la fonction d'observation.
Elle est utilisée en traitement de l'image : elle est basée sur la minimisation de l'interdépendance, au sens de la théorie de l'information, entre deux groupes de pixels, classés suivant leurs niveaux de gris.
Le seuil 
est égal au 
(les 
correspondent aux abscisses des cases de l'histogramme) qui minimise la fonction :
tel que 
avec :
Voir les figures joh1, joh2 et joh3 pour les résultats de la méthode avec les tests définis dans la section tests.
Cette méthode est basée sur l'histogramme 
(non normalisé) de la fonction d'observation.
La valeur du seuil est calculée de telle manière que les moments du signal à seuiller et les moments du signal seuillé (les échantillons de bruit sont mis à 
et les échantillons correspondant à des transitions sont mis à 
) soient préservés.
Les moments 
d'ordre 
sont égaux à :
où 
est la taille du signal.
Alors, le 
qui nous donne le seuil 
est égal à :
Avec :
,
et
Voir les figures mom1 et mom2 pour les résultats de la méthode avec les tests définis dans la section tests.
Cette méthode est basée sur l'histogramme 
normalisé 
de la fonction d'observation.
Nous supposons que l'histogramme du signal est la somme de deux gaussiennes de densités de probabilité 
et 
et de probabilité a priori 
et 
. Pour chaque case 
de l'histogramme nous avons donc :
La valeur du seuil est égale au 
tel que :
Hélas, nous ne connaissons pas 
, 
, 
, 
, 
et 
.
Pour les déterminer, Kittler et Illingworth introduisent le critère :
avec :
et 
et 
et 
Il faut minimiser ce critère suivant 
. Alors, 
est le seuil.
Voir les figures gau1, gau2 et gau3 pour les résultats de la méthode avec les tests définis dans la section tests.
Nous sommes parti de considérations sur la séparation en vecteurs propres de bruit et en vecteurs propres de signal d'une matrice d'autocorrélation. Les valeurs propres correspondantes, rangées dans l'ordre décroissant, sont représentées sur la figure figu:vapr pour laquelle nous avons 6 sources présentes. Voir Rapport:RossignolDEA1 et Article:Friedlander.
Nous voyons que la courbe obtenue peut être approximée par deux droites dont le point d'intersection correspond à la limite entre la partie signal et la partie bruit.
Nous appliquons dans notre cas une procédure similaire. Nous classons les échantillons du plus grand au plus petit, en conservant en index leur position temporelle. Nous appelons la courbe obtenue 
. Puis nous cherchons à déterminer en quel endroit cette courbe se casse en deux : les plus petits échantillons correspondent aux zones stables du signal et les plus grands à des zones instables. La méthode pose les mêmes problèmes ici qu'aux techniques de séparation en un espace bruit et en un espace signal d'où elle vient : l'estimation du point de césure n'est pas évidente. Pour résoudre ce problème, nous modélisons 
par deux segments de droites. L'un, 
, partant du premier point du classement et s'arrêtant au point 
. L'autre, 
, partant de 
et s'arrêtant au dernier point du classement. Si 
est le nombre d'échantillons, nous faisons varier 
de 
à 
. Pour effectuer cette modélisation, nous minimisons par les moindres carrés chacune des erreurs quadratiques :
Nous obtenons l'erreur quadratique totale : 
.
Nous constatons qu'il existe bien un minimum global pour 
(et qu'il est même souvent l'unique minimum). Ce minimum survient pour un certain indice 
. Nous positionnons alors le seuil à 
. Grâce aux index, nous pouvons poser les marques de segmentation.
La << valeur absolue de la dérivée de 
>>, entre 
et 
, pour l'extrait de flûte, est représentée sur la figure derelf0. La courbe 
qui correspond à cette fonction d'observation est donnée sur la figure ederelf0. Le seuil trouvé vaut alors 
.
L'une des limitations de cette méthode est qu'elle est terriblement gourmande en temps de calcul.
Voir les figures deu1, deu2 et deu3 pour les résultats de la méthode avec les tests définis dans la section tests.
Cette méthode est une méthode d'ondelettistes, utilisée pour le débruitage. Les ondelettistes ont en fait le même problème que nous. Les plus petits coefficients obtenus par une décomposition en paquets d'ondelettes correspondent à du bruit et les plus grands, qui sont beaucoup moins nombreux, à du signal. Voir Rapport:Don1 et Rapport:Don3.
Le signal est : 
. Sa variance est 
.
Le seuil 
est égal au 
qui minimise :
où la fonction 
renvoie 
si 
est inférieur à 
et 
sinon.
Voir les figures sur1, sur2 et sur3 pour les résultats de la méthode avec les tests définis dans la section tests.
Nous décidons que tous les pics supérieurs à 3 
, où 
est l'écart-type du << bruit >> (observé dans les zones stables), sont des pics ne correspondant pas à du << bruit >> (correspondant donc à des transitions).
Il y a une justification théorique à ce seuil, avec le << seuil universel >> (<< universal threshold >>), défini par Donoho dans Rapport:Don1 et Rapport:Don3. Ce seuil est égal à 
, où 
est la taille du signal en nombre d'échantillons. Donoho prouve que quand 
tend vers l'infini la probabilité qu'un échantillon de bruit dépasse ce seuil tend vers 0. Et 
, pour un 
de valeur << raisonnable >> pour nous, c'est-à-dire de l'ordre de 
, par exemple, est très proche de 
(
).
Le problème est de parvenir à déterminer 
correctement. Pour ce faire, nous classons les échantillons en ordre croissant et nous calculons 
avec les 
% plus petits (avec 
égale à 
, par exemple : comme il est montré dans la section tests sur la figure perdifseu, nous obtenons des résultats consistants, c'est-à-dire que la méthode est relativement robuste à 
). Cependant, le seuil dépend de 
, la taille du signal, ce qui n'est pas très intéressant.
Voir les figures tro1, tro2 et tro3 pour les résultats de la méthode avec les tests définis dans la section tests.
Dans leur article de revue (<< survey >>) des techniques de seuillage, Sahoo, Soltani et Wong donnent encore une autre méthode de seuillage. Elle est basée sur la mesure de l'uniformité :
où 
est la position du seuil (variant entre 
et 
, 
étant la taille du signal) ; 
un << facteur de normalisation >> ; 
est la variance du premier mode, supposé comprenant tous les échantillons inférieurs ou égaux à 
; et 
est la variance du second mode, supposé comprenant tous les échantillons strictement supérieurs à 
. Il s'agit de maximiser cette mesure. En fait, il est tout à fait équivalent de minimiser suivant 
cette fonction :
Voir les figures sesa1, sesa2 et sesa3 pour les résultats de la méthode avec les tests définis dans la section tests.
Cette méthode est itérative. À l'origine, elle est utilisée avec l'histogramme, mais elle peut être adaptée pour être utilisée directement avec les échantillons ordrés. La taille du signal est 
. Les échantillons sont : 
. L'algorithme est le suivant :
), 
. C'est-à-dire que 
, la position du seuil initial, est posée à 
.
et 
.
telle que 
.
, retour à l'étape blurp
Sinon, nous nous arrêtons et la valeur du seuil est 
Voir les figures seis1, seis2 et seis3 pour les résultats de la méthode avec les tests définis dans la section tests.
Cette méthode et la suivante sont basées sur l'étude de l'histogramme. Ces deux méthodes, basées sur la << symétrie >>, font l'hypothèse que l'un des deux modes produit un pic dominant : c'est-à-dire que la probabilité a priori de ce mode est plus grande que celle de l'autre, et/ou sa variance est plus petite que celle de l'autre. Ceci correspond à la plupart des cas étudiés par les tests définis dans la section tests : ce n'est pas vrai quand les deux modes ont autant de points. Cependant, le maximum qui nous intéresse appartenant toujours à la première partie de l'histogramme, même ce cas peut être traité par la méthode.
Le maximum de l'histogramme est détecté. Il a lieu pour la case numérotée 
. Nous cherchons la case 
, avec 
telle qu'au moins 95 % (dans le cas général : 
%) des points compris entre la case 
et la case 
(y compris la case 
et la case 
) soient compris entre la case 
et la case 
(y compris la case 
et la case 
). La position du seuil est alors 
et la valeur du seuil est 
. Ceci est illustré sur la figure sym1. En fait, nous avons constaté que le seuil trouvé est systématiquement trop petit, alors nous lui ajoutons une valeur, arbitraire : pour obtenir les résultats présentés dans cet exposé, nous l'avons fixée à 0,6. Nous devrions faire dépendre cette valeur du nombre de points dans le second mode (voir la figure sesy11), de 
, etc. : il s'agit de perspectives.
Voir les figures sesy11, sesy12 et sesy13 pour les résultats de la méthode avec les tests définis dans la section tests.
Cette fois, la position 
nous permet d'obtenir une estimée de la variance du << bruit >> : 
, avec 
le nombre de points compris dans les cases de 
à 
, 
, 
le nombre de points dans la 
case de l'histogramme et 
la coordonnée de cette case. Nous pouvons donc relier cette méthode à la règle des 
. Nous estimons 
, puis le seuil est fixé à 
(ou mieux à 
, où 
est la moyenne du bruit). Ainsi, nous nous affranchissons de ce 
(voir la section seuil:3sig) qui correspondait à un seuil fixe, fixé arbitrairement.
Une perspective est envisagée : nous pourrions évaluer la variance du bruit en utilisant directement les échantillons du signal inférieurs à 
.
Voir les figures sesy21, sesy22 et sesy23 pour les résultats de la méthode avec les tests définis dans la section tests.
Cette méthode est basée elle aussi sur l'étude de l'histogramme (composé de 
cases). Nous détectons le maximum de l'histogramme. Sa position est 
, et sa valeur 
: 
. Nous relions par un segment de droite ce maximum au dernier point de l'histogramme (
). Pour chaque case 
(
) tel que 
nous calculons sa distance euclidienne minimale 
au segment de droite. Le plus grand des 
, 
, est obtenu pour la case 
. Alors la position du seuil est 
.
Voir les figures setr1 (nous remarquons que quand les deux modes ont à peu près le même nombre de points, les performances de la méthode se dégradent : en fait, cette méthode est particulièrement adaptée au cas où l'un des modes est rare et a une variance grande, c'est-à-dire à nos fonctions d'observation), setr2 et setr3 pour les résultats de la méthode avec les tests définis dans la section tests.
Nous prouvons (voir l'annexe ann:varsig) que la variance de l'estimée à partir de 
échantillons (
) de la variance 
d'un bruit gaussien 
est égale à :
dans le cas biaisé, c'est-à-dire quand nous estimons la variance ainsi :
et qu'elle est égale à :
dans le cas non biaisé, c'est-à-dire quand nous estimons la variance ainsi :
.
Elle dépend donc d'un terme en 
. L'idée est d'ajouter un terme qui dépend du nombre de points utilisés pour calculer chacune des deux variances utilisées dans la mesure de l'uniformité (voir la section mseuil14) : plus le nombre de points est grand, plus nous pouvons faire confiance en l'estimée de la variance. Ainsi, il s'agit à présent de minimiser suivant 
l'expression :
Nous avons choisi 
.
Voir les figures seam1, seam2 et seam3 pour les résultats de la méthode avec les tests définis dans la section tests.
Nous constatons que pour le premier test (voir la section ssect:test1) cet estimateur n'est pas biaisé, ni quand il estime le nombre de bonnes détections, ni quand il estime le nombre de fausses alarmes. Par rapport à la méthode de Sahoo originale, l'amélioration, pour les trois tests, est nette. Nous pourrions aussi tenir compte du terme en 
, en prenant des puissances inférieures à 2 pour les écarts-types. Nous aurions, dans le cas général :
Trois problèmes se posent :
Nous avons simulé ce signal :
.
. Ils suivent une loi normale 
.
. Ils suivent une loi normale 
.
Puis nous avons utilisé chacune des méthodes de seuillage pour seuiller ce signal. Nous décidons que tous les échantillons supérieurs à ce seuil correspondent à des transitions. Puisque nous savons les positions des échantillons qu'il faut détecter (disons, les 
premiers sur 
) et les positions des points réellement détectés, nous pouvons calculer le nombre de fausses alarmes (un échantillon de bruit a été donné comme étant un échantillon de transition) et le nombre de bonnes détections obtenus.
Nous avons pris :
et 
variant de 
à 
et 
et 
Les résultats sont présentés sur les figures con1, his1, ots1, pu11, pu21, kap1, joh1, mom1, gau1, deu1, sur1, tro1, sesa1, seis1, sesy11, sesy21, setr1 et seam1.
Les courbes de droite correspondent au nombre de bonnes détections obtenu (trait plein) en fonction de 
. Les courbes de gauche représentent le nombre de fausses alarmes obtenu (trait plein) en fonction de 
.
Les courbes en pointillés représentent le nombre de bonnes détections attendu (à droite) et le nombre de fausses alarmes attendu (à gauche). Pour obtenir ces nombres, nous considérons que nous connaissons le nombre de marques à trouver et nous comptons, pour avoir le nombre de fausses alarmes, le nombre de pics de bruit plus grands que le plus petit pic de signal. En fait, toutes ces courbes en pointillés correspondent aux résultats que nous obtiendrions idéalement[Note : C'est-à-dire si nous connaissions exactement le nombre de marques à trouver !] avec la cinquième méthode de seuillage (<< Nombre de marques connu, ou méthode du pourcentile >> : voir la section mseuil5).
Les résultats donnés sont les moyennes obtenus pour un grand nombre de coups (1000 signaux de 
échantillons).
Il est normal que la méthode des 
échoue, puisque l'importance relative des deux modes varie énormément. Les résultats donnés sont ceux obtenus pour 
. Nous conservons cette méthode dans la suite.
D'autres méthodes ont échoué. Il s'agit des deux méthodes entropiques de Pun (voir les sections mseuil4 et mseuil6). Ces méthodes sont adaptées aux cas où les deux modes sont équiprobables ou presque équiprobables. Nous ne les utiliserons plus dans la suite.
Nous avons pris :
et 
et 
varie entre 1 et 4
et 
Les résultats sont présentés sur les figures con2, his2, ots2, kap2, joh2, mom2, gau2, deu2, sur2, tro2, sesa2, seis2, sesy12, sesy22, setr2, seam2.
Une méthode a échoué. Il s'agit de la méthode << Préservation des moments >> (voir la section mseuil9). Nous ne l'utiliserons plus dans la suite.
Nous avons pris :
et 
variable (entre 3 et 10) et 
et 
Les résultats sont présentés sur les figures con3, his3, ots3, kap3, joh3, gau3, deu3, sur3, tro3, sesa3, seis3, sesy13, sesy23, setr3, seam3 et sur la figure perdifseu.
Considérons la figure perdifseu. À gauche, la courbe en pointillés donne le nombre de bonnes détections que nous pouvons espérer. Plus 
est petit plus ce nombre est petit. En effet, plus 
est petit plus il y a de pics de bruit plus grands que les plus petits pics de signal. Pour 
, nous sommes à 
environ. À droite, la courbe en pointillés donne le nombre de fausses alarmes obtenues si nous connaissions le nombre de pics à détecter : ce nombre est donc 100 moins le nombre de bonnes détections.
En haut, nous présentons les résultats obtenus avec la règle des 
, pour différents 
. Plus 
est petit, plus 
est sous-estimé, et donc plus le nombre de fausses alarmes augmente. Nous voyons que la méthode reste robuste, même quand nous faisons une grande erreur sur 
.
Et en bas, nous présentons les résultats obtenus avec huit autres méthodes de seuillage. Parmi celles-ci, la plus classique, c'est-à-dire celle qui est basée sur la détection des deux modes de l'histogramme (voir la section mseuil2), est la moins fiable.
Dans le programme segmentation, seul le seuillage à 
a été implémenté (avec 
).