le site d'un prof d'informatique

Binarisation


Champs de Markov


Du fait de la forte variabilité inhérente aux documents, une modélisation formelle de la structure est difficilement envisageable, car trop rigide. Les modèles stochastiques s'accommodent mieux des incertitudes. Les champs de Markov permettant de représenter une relation de voisinage, ils sont particulièrement adaptés à la segmentation puisqu'il existe beaucoup de relations spatiales dans une image. La théorie des champs Markoviens a donc été largement développée ces dernières décennies et appliquée dans différents domaines du traitement d'image \cite{Li95}. La segmentation (et \textsl{a fortiori} la binarisation) se ramenant à la définition de la classe $X$ d'un pixel en fonction de sa valeur $Y$, le problème est donc de calculer la configuration optimale du champ d'étiquettes $X$ qui maximise la probabilité a posteriori $P(X/Y)$. Grâce au théorème de Bayes, on a $P(X/Y)=\frac{P(Y/X)*P(X)}{P(Y)}$, ce qui est plus facile à caractériser. En appliquant les hypothèses Markoviennes et d'indépendance entre les observations, on obtient :
Calcul de l'energie d'une image (10)

avec
- $NG(s)$ désigne le voisinage du site s ;
- vraisemblance représente la vraisemblance de la classe par rapport à l'observation ;
- Contexte image représente la connaissance contextuelle introduite par le modèle.
Il s'agit de la probabilité a priori de la configuration $x$ du champ $X$. Afin de rendre calculable cette estimation, ce terme peut être réécrit ainsi :
Markov (11)

avec :
- $C$ un ensemble de cliques associés au voisinage $NG$ (Une clique étant un sous-ensemble de sites mutuellement voisins) ;
- $V_{c}$ est la fonction de potentiel de la clique $c$ ;
- $Z$ est un terme de normalisation.
On peut ainsi introduire la notion d'énergie en calculant le logarithme négatif de la probabilité jointe $P(X,Y)$, soit :
Calcul de l'énergie (12)


Algorithme (13)

Finalement le problème de la segmentation revient à un problème de minimisation de la fonction d'énergie : Champs de Markov. Cette fonction d'énergie peut être minimisée en utilisant un algorithme d'optimisation, comme le recuit simulé. Pour simplifier les calculs de binarisation, on suppose que le bruit qui vient perturber les observations suit une loi de Gauss. Ainsi, $P(Y/X)$ est approximé de cette manière :
minimisation(14)

en prenant $X$={0,255} et $\theta _{n}^2$ la variance. Cependant, cette estimation est trop réductrice car les valeurs de $X$ ne sont pas toujours aussi extrêmes : le texte n'est pas toujours à 0 mais peut être à 10 par exemple, à cause du bruit. L'idée de Wolf est alors d'ajouter une fonction $C$ pour modifier les valeurs de $X$ lors du calcul du bruit résiduel ($\Vert C(X) - Y\Vert$). Hélas, la fonction $C$, qui revient à trouver l'incidence du bruit sur chaque pixel, n'est pas calculable simplement. Il décide alors d'utiliser le calcul de Sauvola [#!Sauvola00!#] pour adapter localement le calcul du bruit résiduel. La fonction d'énergie devient alors $\Vert X - Y + T - 127.5\Vert$, avec $T$ le seuil calculé avec la méthode de Sauvola. Donc le problème du maximum a posteriori peut se calculer ainsi :
traitement signal (15)

, soit
Calcul et algorithme (16)

La variance $\theta _{n}^2$ est approximée en regardant dans une fenêtre centrée autour du pixel et séparant l'histogramme en deux classes en utilisant le critère d'Otsu (qui revient à maximiser la variance intra classe) [#!Otsu79!#]. $\theta$ est alors calculé en multipliant par une constante (fixé à $0,5$) la variation intra classe. Enfin, le calcul de $P(X)$, ou plutôt d'après l'équation 2.11, le calcul de $V_{c}(X)$ se fait d'après la fréquence d'occurrence dans une clique de chaque classe, par apprentissage. Le calcul de $V_{c}(X)$ est celui ci :
Restauration (17)


Binarisation Lelore (18)

$P_i(x_i)$ est la probabilité de trouver la classe $x_i$ dans la clique $i$.
$d(i,j)$ est le nombre de bits différents entre deux cliques de classes $x_i$ et $x_j$.
$u(i,j)$ est le nombre de bits identiques entre deux cliques de classes $x_i$ et $x_j$.
$k$ est un coefficient de lissage. L'algorithme de Wolf constitue ainsi l'extension de la méthode de Sauvola et les résultats présentés montrent un gain important par rapport à cette méthode, ce qui justifie l'utilisation de champs de Markov.


Bouygues ImmobilierGuides Cours informatiqueHit-Parade des sites francophones Annuaire gratuit Compare le Net