$\forall i\in\{1,...,n\}$, alors les systèmes ayant un nombre d'éléments
différent de $2^k$, ne peuvent avoir que des codes de Gray équilibrés avec
$\textit{TC}_n(i)=\lfloor\frac{2^n}{n}\rfloor$ ou
-$\textit{NT}_n(i)=\lceil\frac{2^n}{n}\rceil, \forall i\in\{1,...,n\}$ et
+$\textit{TC}_n(i)=\lceil\frac{2^n}{n}\rceil, \forall i\in\{1,...,n\}$ et
vérifiant $\sum_{i=1}^n\textit{TC}_n(i) = 2^n$.
\begin{xpl}
\]
\end{xpl}
-On remarque que dans cette marche on reste sur place avec une probabilité
-
-
+On remarque que dans cette marche on reste sur place avec une probabilité égale
+à $\frac{1}{2}+\frac{1}{2\mathsf{N}}$ et l'on passe d'un sommet à son voisin
+lorsque c'est possible avec une probabilité $\frac{1}{2\mathsf{N}}$.
+Les probabilités usuelles que l'on appliquerait aux transitions de
+l'algorithme~\ref{CI Algorithm} serait quant à elles uniformément égales
+à $\frac{1}{\mathsf{N}}$.
+Cette manière paresseuse d'itérer (puisqu'on reste plus souvent sur place) n'est donc pas équivalente à celle issue de l'algorithme.
+Cependant, l'étude théorique de référence~\cite{LevinPeresWilmer2006}
+considère cette marche comme cadre. S'inspirant de
+celle-ci, le travail suivant se replace donc dans ce cadre théorique.
Tout d'abord, soit $\pi$ et $\mu$ deux distributions sur
et
$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-
-Un résultat classique est
-
-$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
-
-
-
-
-Soit $(X_t)_{t\in \mathbb{N}}$ une suite de variables aléatoires de
-$\Bool^{\mathsf{N}}$.
-Une variable aléatoire $\tau$ dans $\mathbb{N}$ est un
-\emph{temps d'arrêt} pour la suite
-$(X_i)$ si pour chaque $t$ il existe $B_t\subseteq
-(\Bool^{\mathsf{N}})^{t+1}$ tel que
-$\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$.
-En d'autres termes, l'événement $\{\tau = t \}$ dépend uniquement des valeurs
-de
-$(X_0,X_1,\ldots,X_t)$, et non de celles de $X_k$ pour $k > t$.
-
-Soit $(X_t)_{t\in \mathbb{N}}$ une chaîne de Markov et
-$f(X_{t-1},Z_t)$ une représentation fonctionnelle de celle-ci.
-Un \emph{temps d'arrêt aléatoire} pour la chaîne de
-Markov est un temps d'arrêt pour
-$(Z_t)_{t\in\mathbb{N}}$.
-Si la chaîne de Markov est irréductible et a $\pi$
-comme distribution stationnaire, alors un
-\emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire
-(qui peut dépendre de la configuration initiale $X$),
-tel que la distribution de $X_\tau$ est $\pi$:
-$$\P_X(X_\tau=Y)=\pi(Y).$$
-
-
-Un temps d'arrêt $\tau$ est qualifié de \emph{fort} si $X_{\tau}$
-est indépendant de $\tau$. On a les deux théorèmes suivants, dont les
-démonstrations sont données en annexes~\ref{anx:generateur}.
+Intuitivement, $t_{\rm mix}(\varepsilon)$ est le nombre d'itérations nécessaire
+pour être proche de la distribution stationnaire à $\varepsilon$ prêt,
+peut importe la configuration de départ. On a le théorème suivant démontré en annexes~\ref{anx:generateur}.
-\begin{theorem}
-Si $\tau$ est un temps d'arrêt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
-\P_X(\tau > t)$.
-\end{theorem}
-
-
-Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction
-telle que pour $X \in \Bool^{\mathsf{N}} $,
-$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$.
-La fonction $\ov{h}$ est dite {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$,
-$\ov{h}(\ov{h}(X))\neq X$.
+\begin{restatable}[Temps de mixage sans chemin hamiltonien]{theorem}{theotpsmix}
+\label{theo:tmps:mix}
+On considère un $\mathsf{N}$-cube dans lequel un chemin hamiltonien a été supprimé et la fonction de
+probabilités $p$ définie sur l'ensemble des arcs comme suit:
+\[
+p(e) \left\{
+\begin{array}{ll}
+= \frac{1}{2} + \frac{1}{2\mathsf{N}} \textrm{ si $e=(v,v)$ avec $v \in \Bool^{\mathsf{N}}$,}\\
+= \frac{1}{2\mathsf{N}} \textrm{ sinon.}
+\end{array}
+\right.
+\]
+La chaîne de Markov associée converge vers la distribution uniforme et
-\begin{restatable}[Majoration du temps d'arrêt]{theorem}{theostopmajorant}
-\label{prop:stop}
-Si $\ov{h}$ est bijective et anti involutive
-$\ov{h}(\ov{h}(X))\neq X$, alors
-$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$.
+\[
+\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le 32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1) = O(N^2).
+\]
\end{restatable}
-Les détails de la preuve sont donnés en annexes~\ref{anx:generateur}.
-On remarque tout d'abord que la chaîne de Markov proposée ne suit pas exactement
-l'algorithme~\ref{CI Algorithm}. En effet dans la section présente,
-la probabilité de rester dans une configuration donnée
-est fixée à $\frac{1}{2}+\frac{1}{2n}$.
-Dans l'algorithme initial, celle-ci est de $\frac{1}{n}$.
-Cette version, qui reste davantage sur place que l'algorithme original,
-a été introduite pour simplifier le calcul d'un majorant
-du temps d'arrêt.
Sans entrer dans les détails de la preuve, on remarque aussi
On peut évaluer ceci pratiquement: pour une fonction
$f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ et une graine initiale
-$x^0$, le code donné à l'algorithme ~\ref{algo:stop} retourne le
+$x^0$, le code donné à l'algorithme~\ref{algo:stop} retourne le
nombre d'itérations suffisant tel que tous les éléments $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ sont équitables. Il permet de déduire une approximation de $E[\ts]$
en l'instanciant un grand nombre de fois: pour chaque nombre $\mathsf{N}$,
$ 3 \le \mathsf{N} \le 16$, 10 fonctions ont été générées comme dans
\section{Conclusion}
-Ce chaptitre a montré comment construire un PRNG chaotique, notamment à partir
+Ce chapitre a montré comment construire un PRNG chaotique, notamment à partir
de codes de Gray équilibrés. Une méthode complètement automatique de
construction de ce type de codes a été présentée étendant les méthodes
existantes.
distribution uniforme de la sortie est discutée dans cette section.
La chaoticité du générateur est ensuite étudiée en
section~\ref{prng:unaire:chaos}.
-La section~\ref{sub:prng:algo} a été publiéeà~\cite{bcgw11:ip,bcgr11:ip}.
+La section~\ref{sub:prng:algo} a été publiée à ~\cite{bcgw11:ip,bcgr11:ip}.
\section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo}
\item il y a un arc libellé $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ entre les n{\oe}uds $x$ et $y$ si et seulement si $p_i$ est un élément de
$\mathcal{P}$ (\textit{i.e.}, on peut itérer $p_i$ fois), et pour chaque
$k$, $0 \le k \le p_i-1$, on a
- $u_k$ qui apaprtient à $[\mathsf{N}]$ et
+ $u_k$ qui appartient à $[\mathsf{N}]$ et
$y=F_{f_u,p_i} (x, (u_0, \hdots, u_{p_i-1})) $.
\end{itemize}
Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{giu}(f)$.
Ce chapitre a proposé un algorithme permettant de construire un
PRNG chaotique à partir d'un PRNG existant. Pour ce faire, il est nécessaire
et suffisant que la fonction $f$ qui est itérée un nombre $b$ de fois
-possède un $\textsc{giu}_{\{b\}}(f)$ fortement connexe et que sa matrice de Markov assosiée soit doublement stochastique.
+possède un $\textsc{giu}_{\{b\}}(f)$ fortement connexe et que sa matrice de Markov associée soit doublement stochastique.
Le chapitre suivant montre comment construire une telle fonction.
selon le nouveau vecteur de positions ${x'}$.
\end{enumerate}
-Voyons comment extraire une marque d'une document PDF.
+Voyons comment extraire une marque d'un document PDF.
\subsection{Extraction de la marque}
-\begin{theorem}
-La condition de l'algorithme de marquage est nécressaire et suffisante
-pour permettre l'extraction du message du média marqué.
-\end{theorem}
+
+\marquagecorrectioncompl*
\begin{proof}
-For sufficiency, let $d_i$ be the last iteration (date) the element $i \in \Im(S_p)$
-of $x$ has been modified:% is defined by
+Pour la suffisance, soit $d_i$ la dernière itération où l'élément $i \in \Im(S_p)$
+de la configuration $x$ a été modifié:% is defined by
$$
d_i = \max\{j | S^j_p = i \}.
$$
-Let $D=\{d_i|i \in \Im(S_p) \}$.
-The set $\Im(S_c)_{|D}$ is thus
-the restriction of the image of $S_c$ to $D$.
+Soit $D=\{d_i|i \in \Im(S_p) \}$.
+L'ensemble $\Im(S_c)_{|D}$ est donc la restriction de l'image de $S_c$ à $D$.
-The host that results from this iteration scheme is thus
-$(x^l_0,\ldots,x^l_{\mathsf{N}-1})$ where
-$x^l_i$ is either $x^{d_i}_i$ if $i$ belongs to $\Im(S_p)$ or $x^0_i$ otherwise.
-Moreover, for each $i \in \Im(S_p)$, the element $x^{d_i}_i$ is equal to
+Le vecteur qui résutle de ces itérations est donc
+$(x^l_0,\ldots,x^l_{\mathsf{N}-1})$ où
+$x^l_i$ est soit $x^{d_i}_i$ si $i$ appartient à $\Im(S_p)$ ou $x^0_i$ sinon.
+De plus, pour chaque $i \in \Im(S_p)$, l'élément $x^{d_i}_i$ est égal à
$m^{d_i-1}_{S^{d_i}_c}$.
-Thanks to constraint \ref{itm2:Sc}, all the indexes
-$j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ belong to
+Sous hypothèse que la contrainte imposée soit réalisée, tous les indices
+$j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ appartiennent à
$\Im(S_c)_{|D}$.
-Let then $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ s.t.
+On a alors $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ tel que
$S^{d_i}_c=j$.
-Thus we have all the elements $m^._j$ of the vector $m$.
-Let us focus now on some $m^{d_i-1}_j$.
-Thus the value of $m^0_j$ can be immediately
-deduced by counting in $S_c$ how many
-times the component $j$ has been switched
-before $d_i-1$.
+On retrouve ainsi tous les éléments $m^._j$ du vecteur $m$.
+A partir de $m^{d_i-1}_j$,
+la valeur de $m^0_j$ peut être déduite en comptant dans $S_c$ combien de fois
+l'élément $j$ a été invoqué avant $d_i-1$.
-Let us focus now on necessity.
-If $\Im(S_c)_{|D} \subsetneq
+Réciproquement, si $\Im(S_c)_{|D} \subsetneq
\llbracket 0 ;\mathsf{P} -1 \rrbracket$,
-there exist some $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ that
-do not belong to $\Im(S_c)_{|\Im(S_p)}$.
-Thus $m_j$ is not present in $x^l$ and the message cannot be extracted.
+i lexiste un $j \in \llbracket 0 ;\mathsf{P} -1 \rrbracket$ qui n'appartient pas à $\Im(S_c)_{|\Im(S_p)}$.
+Ainsi, $m_j$ n'est pas présent dans $x^l$ et le message ne peut pas extrait.
\end{proof}
-When the constraint \ref{itm2:Sc} is satisfied, we obtain a scheme
-that always finds the original message provided the watermarked media
-has not been modified.
-In that context, correctness and completeness are established.
-
-
-Thanks to constraint~\ref{itm2:Sc}, the cardinality $k$ of
-$\Im(S_p)$ is larger than $\mathsf{P}$.
-Otherwise the cardinality of $D$ would be smaller than $\mathsf{P}$
-and similar to the cardinality of $\Im(S_c)_{|D}$,
-which is contradictory.
-
-One bit of index $j$ of the original message $m^0$
-is thus embedded at least twice in $x^l$.
-By counting the number of times this bit has been switched in $S_m$, the value of
-$m_j$ can be deduced in many places.
-Without attack, all these values are equal and the message is immediately
-obtained.
- After an attack, the value of $m_j$ is obtained as mean value of all
-its occurrences.
-The scheme is thus complete.
-Notice that if the cover is not attacked, the returned message is always equal to the original
-due to the definition of the mean function.
-\begin{theorem}\label{th:stego}
-Soit $\epsilon$ un nombre positif,
-$l$ un nombre de LSBs,
-$X \sim \mathbf{U}\left(\mathbb{B}^l\right)$,
-un adapteur de stratégie uniformémement distribué indépendant de $X$
-$f_l$ un mode tel que
-$\textsc{giu}(f_l)$ est fortement connexe et la
-matrice de Markov associée à $f_l$ est doublement stochastique.
-Il existe un nombre $q$ d'itérations tel que
-$|p(Y|K)- p(X)| < \epsilon$.
-\end{theorem}
+Prouvons le théorème suivant.
+\theoremstegoscureepsilon*
\begin{proof}
-Let $\textit{deci}$ be the bijection between $\Bool^{l}$ and
-$\llbracket 0, 2^l-1 \rrbracket$ that associates the decimal value
-of any binary number in $\Bool^{l}$.
-The probability $p(X^t) = (p(X^t= e_0),\dots,p(X^t= e_{2^l-1}))$ for $e_j \in \Bool^{l}$ is thus equal to
-$(p(\textit{deci}(X^t)= 0,\dots,p(\textit{deci}(X^t)= 2^l-1))$ further denoted by $\pi^t$.
-Let $i \in \llbracket 0, 2^l -1 \rrbracket$,
-the probability $p(\textit{deci}(X^{t+1})= i)$ is
+Soit $\textit{deci}$ la bijection
+entre $\Bool^{l}$ et
+$\llbracket 0, 2^l-1 \rrbracket$ qui associe la valeur décimale
+à chaque nombre binaire dans $\Bool^{l} $.
+La probabilité $p(X^t) = (p(X^t= e_0),\dots,p(X^t= e_{2^l-1}))$ pour $e_j \in \Bool^{l}$ est égale à
+$(p(\textit{deci}(X^t)= 0,\dots,p(\textit{deci}(X^t)= 2^l-1))$, notée par la suite $\pi^t$.
+Pour $i \in \llbracket 0, 2^l -1 \rrbracket$,
+la probabilité $p(\textit{deci}(X^{t+1})= i)$ est
\[
\sum\limits^{2^l-1}_{j=0}
\sum\limits^{l}_{k=1}
p(\textit{deci}(X^{t}) = j , S^t = k , i =_k j , f_k(j) = i_k )
\]
\noindent
-where $ i =_k j $ is true iff the binary representations of
-$i$ and $j$ may only differ for the $k$-th element,
-and where
-$i_k$ abusively denotes, in this proof, the $k$-th element of the binary representation of
+où $ i =_k j $ est vraie si et seulement si les représentations binaires de
+$i$ et de $j$ ne diffèrent que le $k^{\textrm{ème}}$ élément et
+où
+$i_k$ représente dans cette preuve le $k^{\textrm{ème}}$ élément dans la représentation binaire
+du nombre
$i$.
-Next, due to the proposition's hypotheses on the strategy,
-$p(\textit{deci}(X^t) = j , S^t = k , i =_k j, f_k(j) = i_k )$ is equal to
+En raison des hypothèses sur la stratégie, la probabilité
+$p(\textit{deci}(X^t) = j , S^t = k , i =_k j, f_k(j) = i_k )$ est égale à
$\frac{1}{l}.p(\textit{deci}(X^t) = j , i =_k j, f_k(j) = i_k)$.
-Finally, since $i =_k j$ and $f_k(j) = i_k$ are constant during the
-iterative process and thus does not depend on $X^t$, we have
+Enfin, puisque $i =_k j$ et $f_k(j) = i_k$ sont constant
+et sont donc indépendants de $X^t$, on a
\[
\pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
\pi^t_j.\frac{1}{l}
p(i =_k j, f_k(j) = i_k ).
\]
-Since
+Puisque
$\frac{1}{l}
\sum\limits^{l}_{k=1}
p(i =_k j, f_k(j) = i_k )
-$ is equal to $M_{ji}$ where $M$ is the Markov matrix associated to
- $f_l$ we thus have
+$ est égal à $M_{ji}$ où $M$ est la matrice de Markov associée à
+ $f_l$, on a ainsi
\[
\pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
-\pi^t_j. M_{ji} \textrm{ and thus }
+\pi^t_j. M_{ji} \textrm{ et donc }
\pi^{t+1} = \pi^{t} M.
\]
% The calculus of $p(X^{t+1} = e)$ is thus equal to
% $\pi^{t+1}_i$.
-First of all,
-since the graph $\Gamma(f)$ is strongly connected,
-then for all vertices $i$ and $j$, a path can
-be found to reach $j$ from $i$ in at most $2^l$ steps.
-There exists thus $k_{ij} \in \llbracket 1, 2^l \rrbracket$ s.t.
+Maintenant, puisque le graphe $\Gamma(f)$ est fortement connexe,
+pour chaque couple de sommets $(i,j)$, un chemin peut être trouvé de $i$ jusqu'à $j$
+de longueur au plus égale à $2^l$.
+Il existe donc $k_{ij} \in \llbracket 1, 2^l \rrbracket$ t.q.
${M}_{ij}^{k_{ij}}>0$.
-As all the multiples $l \times k_{ij}$ of $k_{ij}$ are such that
-${M}_{ij}^{l\times k_{ij}}>0$,
-we can conclude that, if
-$k$ is the least common multiple of $\{k_{ij} \big/ i,j \in \llbracket 1, 2^l \rrbracket \}$ thus
-$\forall i,j \in \llbracket 1, 2^l \rrbracket, {M}_{ij}^{k}>0$ and thus
-$M$ is a regular stochastic matrix.
+
+Comme tous les multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que
+${M}_{ij}^{l\times k_{ij}}>0$, on peut conclure que si
+$k$ est le PPCM de $\left\{k_{ij} \big/ i,j \in \llbracket 1, 2^l \rrbracket \right\}$ alors
+$\forall i,j \in \llbracket 1, 2^l \rrbracket, {M}_{ij}^{k}>0$ et donc
+$M$ est une matrice stochastique régulière.
+
-Let us now recall the following stochastic matrix theorem:
-\begin{theorem}[Stochastic Matrix]
- If $M$ is a regular stochastic matrix, then $M$
- has an unique stationary probability vector $\pi$. Moreover,
- if $\pi^0$ is any initial probability vector and
- $\pi^{t+1} = \pi^t.M $ for $t = 0, 1,\dots$ then the Markov chain $\pi^t$
- converges to $\pi$ as $t$ tends to infinity.
+\begin{theorem}
+ Si $M$ est une matrice stochastique régulière, alors $M$
+ possède un unique vecteur stationnaire de probabilités $\pi$
+ ($\pi.M = \pi$).
+ De plus, si $\pi^0$ est un vecteur de probabilité
+ et si on définit
+ la suite $(\pi^{k})^{k \in \Nats}$ par
+ $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$
+ alors la chaîne de Markov $\pi^k$
+ converge vers $\pi$ lorsque $k$ tend vers l'infini.
\end{theorem}
-Thanks to this theorem, $M$
-has an unique stationary probability vector $\pi$.
-By hypothesis, since $M$ is doubly stochastic we have
+Grâce à ce théorème, $M$ admet un unique vecteur stationnaire de probabilité $\pi$.
+Par hypothèses, puisque $M$ est doublement stochastique, on a
$(\frac{1}{2^l},\dots,\frac{1}{2^l}) = (\frac{1}{2^l},\dots,\frac{1}{2^l})M$
-and thus $\pi = (\frac{1}{2^l},\dots,\frac{1}{2^l})$.
-Due to the matrix theorem, there exists some
-$q$ s.t.
-$|\pi^q- \pi| < \epsilon$
-and the proof is established.
-Since $p(Y| K)$ is $p(X^q)$ the method is then $\epsilon$-stego-secure
-provided the strategy-adapter is uniformly distributed.
+et donc $\pi = (\frac{1}{2^l},\dots,\frac{1}{2^l})$.
+Il existe donc $q$ t.q.
+$|\pi^q- \pi| < \epsilon$.
+Puisque $p(Y| K)$ est $p(X^q)$, la méthode est donc $\epsilon$-stego-secure
+pour peu que l'adapteur de stratégie soit uniformément distribué.
\end{proof}
-On considère le mode
+On considère le mode
$f_l: \Bool^l \rightarrow \Bool^l$ t.q. le $i^{\textrm{ème}}$ composant
est défini par
\begin{equation}
{f_l}(x)_i =
\left\{
\begin{array}{l}
-\overline{x_i} \textrm{ if $i$ is odd} \\
-x_i \oplus x_{i-1} \textrm{ if $i$ is even}
+\overline{x_i} \textrm{ si $i$ est impair} \\
+x_i \oplus x_{i-1} \textrm{ si $i$ est pair}
\end{array}
\right.
-\end{equation}\label{eq:fqq}
+\tag{\eqref{eq:fqq}}
+\end{equation}
-Prouvons que la matrice de Markov associée est doublement stochastique.
-the Markov chain is stochastic by construction.
+Prouvons que la matrice de Markov associée est doublement stochastique par induction
+sur la longueur $l$.
+Pour $l=1$ et $l=2$ la preuve est évidente.
+Considérons que le résulat est établi jusqu'à $l=2k$ avec $k \in \Nats$.
-Let us prove that its Markov chain is doubly stochastic by induction on the
-length $l$.
-For $l=1$ and $l=2$ the proof is obvious. Let us consider that the
-result is established until $l=2k$ for some $k \in \Nats$.
-
-Let us then firstly prove the doubly stochasticity for $l=2k+1$.
-Following notations introduced in~\cite{bcgr11:ip},
-Let $\textsc{giu}(f_{2k+1})^0$ and $\textsc{giu}(f_{2k+1})^1$ denote
-the subgraphs of $\textsc{giu}(f_{2k+1})$ induced by the subset $\Bool^{2k} \times\{0\}$
-and $\Bool^{2k} \times\{1\}$ of $\Bool^{2k+1}$ respectively.
-$\textsc{giu}(f_{2k+1})^0$ and $\textsc{giu}(f_{2k+1})^1$ are isomorphic to $\textsc{giu}(f_{2k})$.
-Furthermore, these two graphs are linked together only with arcs of the form
-$(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},1)$ and
+On montre d'abord que la double stochasticité est établie pour $l=2k+1$.
+En suivant les notations introduites à la section~\ref{anx:sccg}, soit
+$\textsc{giu}(f_{2k+1})^0$ et $\textsc{giu}(f_{2k+1})^1$ les sous-graphes
+de $\textsc{giu}(f_{2k+1})$ induits par les ensembles $\Bool^{2k} \times\{0\}$
+et $\Bool^{2k} \times\{1\}$ de $\Bool^{2k+1}$ respectivement.
+Les graphes $\textsc{giu}(f_{2k+1})^0$ et $\textsc{giu}(f_{2k+1})^1$ sont isomorphes à $\textsc{giu}(f_{2k})$.
+De plus, ils ne sont liés dans $\textsc{giu}(f_{2k+1})$ que par
+des arcs de la forme
+$(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},1)$ et
$(x_1,\dots,x_{2k},1) \to (x_1,\dots,x_{2k},0)$.
-In $\textsc{giu}(f_{2k+1})$ the number of arcs whose extremity is $(x_1,\dots,x_{2k},0)$
-is the same than the number of arcs whose extremity is $(x_1,\dots,x_{2k})$
-augmented with 1, and similarly for $(x_1,\dots,x_{2k},1)$.
-By induction hypothesis, the Markov chain associated to $\textsc{giu}(f_{2k})$ is doubly stochastic. All the vertices $(x_1,\dots,x_{2k})$ have thus the same number of
-ingoing arcs and the proof is established for $l$ is $2k+1$.
+Dans $\textsc{giu}(f_{2k+1})$, deux sortes d'arcs pointent vers $(x_1,\dots,x_{2k},0)$.
+Ceux qui sont de la forme $(y_1,\dots,y_{2k},0)$, où un seul des $y_i$ est différent de $x_i$,
+et leur nombre est celui des arcs qui pointent vers $(x_1,\dots,x_{2k})$ dans $\textsc{giu}(f_{2k})$.
+L'arc $(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},0)$ qui existe d'après la définition de $f_l$
+De même pour le nombre d'arcs dont l'extrémité est de la forme $(x_1,\dots,x_{2k},1)$.
+Par hypothèse d'induction, la chaîne de Markov associée à $\textsc{giu}(f_{2k})$
+est doublement stochastique.
+Ainsi tous les sommets $(x_1,\dots,x_{2k})$ ont le même nombre d'arcs entrants et la preuve est établie pour $l= 2k+1$.
-Let us then prove the doubly stochasticity for $l=2k+2$.
-The map $f_l$ is defined by
-$f_l(x)= (\overline{x_1},x_2 \oplus x_{1},\dots,\overline{x_{2k+1}},x_{2k+2} \oplus x_{2k+1})$.
-With previously defined notations, let us focus on
-$\textsc{giu}(f_{2k+2})^0$ and $\textsc{giu}(f_{2k+2})^1$ which are isomorphic to $\textsc{giu}(f_{2k+1})$.
-Among configurations of $\Bool^{2k+2}$, only four suffixes of length 2 can be
-obviously observed, namely, $00$, $10$, $11$ and $01$.
-Since
+Montrons à présent la double stochasticité pour $l=2k+2$.
+La fonction $f_l$ est définie par $f_l(x)= (\overline{x_1},x_2 \oplus x_{1},\dots,\overline{x_{2k+1}},x_{2k+2} \oplus x_{2k+1})$. On se concentre sur
+$\textsc{giu}(f_{2k+2})^0$ et $\textsc{giu}(f_{2k+2})^1$ qui sont isomorphes à $\textsc{giu}(f_{2k+1})$.
+Parmi les configurations de $\Bool^{2k+2}$, seuls quatre suffixes de longueur 2 peuvent appraître:
+$00$, $10$, $11$ et $01$.
+Puisque
$f_{2k+2}(\dots,0,0)_{2k+2}=0$, $f_{2k+2}(\dots,1,0)_{2k+2}=1$,
-$f_{2k+2}(\dots,1,1)_{2k+2}=0$ and $f_{2k+2}(\dots,0,1)_{2k+2}=1$, the number of
-arcs whose extremity is
+$f_{2k+2}(\dots,1,1)_{2k+2}=0$ et $f_{2k+2}(\dots,0,1)_{2k+2}=1$, le nombre d'arcs dont les extrémités est
\begin{itemize}
\item $(x_1,\dots,x_{2k},0,0)$
- is the same than the one whose extremity is $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (loop over configurations $(x_1,\dots,x_{2k},0,0)$).
+est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},0)$ dans $\textsc{giu}(f_{2k+1})$
+ auquel on ajoute 1 (une boucle autours des configurations $(x_1,\dots,x_{2k},0,0)$);
\item $(x_1,\dots,x_{2k},1,0)$
- is the same than the one whose extremity is $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (arc from configurations
-$(x_1,\dots,x_{2k},1,1)$ to configurations
-$(x_1,\dots,x_{2k},1,0)$)
+est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$
+ auquel on ajoute 1 (l'arc entre les configurations $(x_1,\dots,x_{2k},1,1)$ et les configurations
+$(x_1,\dots,x_{2k},1,0)$);
\item $(x_1,\dots,x_{2k},0,1)$
- is the same than the one whose extremity is $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (loop over configurations $(x_1,\dots,x_{2k},0,1)$).
+est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$
+ auquel on ajoute 1 (une boucle autours des configurations $(x_1,\dots,x_{2k},0,1)$);
\item $(x_1,\dots,x_{2k},1,1)$
- is the same than the one whose extremity is $(x_1,\dots,x_{2k},1)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (arc from configurations
-$(x_1,\dots,x_{2k},1,0)$ to configurations
+est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},1)$ in $\textsc{giu}(f_{2k+1})$
+auquel on ajoute 1 (l'arc entre les configurations
+$(x_1,\dots,x_{2k},1,0)$ et les configurations
$(x_1,\dots,x_{2k},1,1)$).
\end{itemize}
-Thus all the vertices $(x_1,\dots,x_{2k})$ have the same number of
-ingoing arcs and the proof is established for $l=2k+2$.
+Chacun des sommets $(x_1,\dots,x_{2k+2})$ a donc le même nombre d'arcs entrants,
+la preuve est donc établie pour $l=2k+2$.
-\section{Quantifier l'écart par rapport à la distribution uniforme}
-%15 Rairo
+L'objectif principal de cette section est de démontrer le théorème~\ref{theo:tmps:mix} rappelé en fin de section.
-
-
-
-Let thus be given such kind of map.
-This article focuses on studying its iterations according to
-the equation~(\ref{eq:asyn}) with a given strategy.
-First of all, this can be interpreted as walking into its iteration graph
-where the choice of the edge to follow is decided by the strategy.
-Notice that the iteration graph is always a subgraph of
-${\mathsf{N}}$-cube augmented with all the self-loop, \textit{i.e.}, all the
-edges $(v,v)$ for any $v \in \Bool^{\mathsf{N}}$.
-Next, if we add probabilities on the transition graph, iterations can be
-interpreted as Markov chains.
-
-\begin{xpl}
-Let us consider for instance
-the graph $\Gamma(f)$ defined
-in \textsc{Figure~\ref{fig:iteration:f*}.} and
-the probability function $p$ defined on the set of edges as follows:
-$$
-p(e) \left\{
-\begin{array}{ll}
-= \frac{2}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\
-= \frac{1}{6} \textrm{ otherwise.}
-\end{array}
-\right.
-$$
-The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is
-\[
-P=\dfrac{1}{6} \left(
-\begin{array}{llllllll}
-4&1&1&0&0&0&0&0 \\
-1&4&0&0&0&1&0&0 \\
-0&0&4&1&0&0&1&0 \\
-0&1&1&4&0&0&0&0 \\
-1&0&0&0&4&0&1&0 \\
-0&0&0&0&1&4&0&1 \\
-0&0&0&0&1&0&4&1 \\
-0&0&0&1&0&1&0&4
-\end{array}
-\right)
-\]
-\end{xpl}
-
-
-% % Let us first recall the \emph{Total Variation} distance $\tv{\pi-\mu}$,
-% % which is defined for two distributions $\pi$ and $\mu$ on the same set
-% % $\Bool^n$ by:
-% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$
-% % It is known that
-% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$
-
-% % Let then $M(x,\cdot)$ be the
-% % distribution induced by the $x$-th row of $M$. If the Markov chain
-% % induced by
-% % $M$ has a stationary distribution $\pi$, then we define
-% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$
-% Intuitively $d(t)$ is the largest deviation between
-% the distribution $\pi$ and $M^t(x,\cdot)$, which
-% is the result of iterating $t$ times the function.
-% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time}
-% with respect to $\varepsilon$ is given by
-% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-% It defines the smallest iteration number
-% that is sufficient to obtain a deviation lesser than $\varepsilon$.
-% Notice that the upper and lower bounds of mixing times cannot
-% directly be computed with eigenvalues formulae as expressed
-% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work
-% only consider reversible Markov matrices whereas we do no restrict our
-% matrices to such a form.
-
-
-
-
-
-
-
-This section considers functions $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}} $
-issued from an hypercube where an Hamiltonian path has been removed.
-A specific random walk in this modified hypercube is first
-introduced. We further detail
-a theoretical study on the length of the path
-which is sufficient to follow to get a uniform distribution.
-Notice that for a general references on Markov chains
-see~\cite{LevinPeresWilmer2006}
-, and particularly Chapter~5 on stopping times.
-
-
-
-
-First of all, let $\pi$, $\mu$ be two distributions on $\Bool^{\mathsf{N}}$. The total
-variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is
-defined by
-$$\tv{\pi-\mu}=\max_{A\subset \Bool^{\mathsf{N}}} |\pi(A)-\mu(A)|.$$ It is known that
-$$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$ Moreover, if
-$\nu$ is a distribution on $\Bool^{\mathsf{N}}$, one has
-$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$
-
-Let $P$ be the matrix of a Markov chain on $\Bool^{\mathsf{N}}$. $P(X,\cdot)$ is the
-distribution induced by the $X$-th row of $P$. If the Markov chain induced by
-$P$ has a stationary distribution $\pi$, then we define
-$$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}.$$
-
-and
-
-$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-One can prove that
+Un résultat classique est
$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
-
-
-% It is known that $d(t+1)\leq d(t)$. \JFC{references ? Cela a-t-il
-% un intérêt dans la preuve ensuite.}
-
-
-
-%and
-% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-% One can prove that \JFc{Ou cela a-t-il été fait?}
-% $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
-
-
-
-Let $(X_t)_{t\in \mathbb{N}}$ be a sequence of $\Bool^{\mathsf{N}}$ valued random
-variables. A $\mathbb{N}$-valued random variable $\tau$ is a {\it stopping
- time} for the sequence $(X_i)$ if for each $t$ there exists $B_t\subseteq
-(\Bool^{\mathsf{N}})^{t+1}$ such that $\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$.
-In other words, the event $\{\tau = t \}$ only depends on the values of
-$(X_0,X_1,\ldots,X_t)$, not on $X_k$ with $k > t$.
+Soit $(X_t)_{t\in \mathbb{N}}$ une suite de variables aléatoires de
+$\Bool^{\mathsf{N}}$.
+Une variable aléatoire $\tau$ dans $\mathbb{N}$ est un
+\emph{temps d'arrêt} pour la suite
+$(X_i)$ si pour chaque $t$ il existe $B_t\subseteq
+(\Bool^{\mathsf{N}})^{t+1}$ tel que
+$\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$.
+En d'autres termes, l'événement $\{\tau = t \}$ dépend uniquement des valeurs
+de
+$(X_0,X_1,\ldots,X_t)$, et non de celles de $X_k$ pour $k > t$.
-Let $(X_t)_{t\in \mathbb{N}}$ be a Markov chain and $f(X_{t-1},Z_t)$ a
-random mapping representation of the Markov chain. A {\it randomized
- stopping time} for the Markov chain is a stopping time for
-$(Z_t)_{t\in\mathbb{N}}$. If the Markov chain is irreducible and has $\pi$
-as stationary distribution, then a {\it stationary time} $\tau$ is a
-randomized stopping time (possibly depending on the starting position $X$),
-such that the distribution of $X_\tau$ is $\pi$:
+Soit $(X_t)_{t\in \mathbb{N}}$ une chaîne de Markov et
+$f(X_{t-1},Z_t)$ une représentation fonctionnelle de celle-ci.
+Un \emph{temps d'arrêt aléatoire} pour la chaîne de
+Markov est un temps d'arrêt pour
+$(Z_t)_{t\in\mathbb{N}}$.
+Si la chaîne de Markov est irréductible et a $\pi$
+comme distribution stationnaire, alors un
+\emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire
+(qui peut dépendre de la configuration initiale $X$),
+tel que la distribution de $X_\tau$ est $\pi$:
$$\P_X(X_\tau=Y)=\pi(Y).$$
+Un temps d'arrêt $\tau$ est qualifié de \emph{fort} si $X_{\tau}$
+est indépendant de $\tau$.
-A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is
-independent of $\tau$.
-
+On rappelle le théorème suivant~\cite[Proposition 6.10]{LevinPeresWilmer2006}.
-\begin{theorem}
-If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
+\begin{theorem}\label{thm-sst}
+Si $\tau$ est un temps d'arrêt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
\P_X(\tau > t)$.
\end{theorem}
-%Let $\Bool^n$ be the set of words of length $n$.
-Let $E=\{(X,Y)\mid
-X\in \Bool^{\mathsf{N}}, Y\in \Bool^{\mathsf{N}},\ X=Y \text{ or } X\oplus Y \in 0^*10^*\}$.
-In other words, $E$ is the set of all the edges in the classical
+Soit $E=\{(X,Y)\mid
+X\in \Bool^{\mathsf{N}}, Y\in \Bool^{\mathsf{N}},\ X=Y \text{ ou } X\oplus Y \in 0^*10^*\}$.
+En d'autres mots, $E$ est l'ensemble des tous les arcs du
${\mathsf{N}}$-cube.
-Let $h$ be a function from $\Bool^{\mathsf{N}}$ into $\llbracket 1, {\mathsf{N}} \rrbracket$.
-Intuitively speaking $h$ aims at memorizing for each node
-$X \in \Bool^{\mathsf{N}}$ which edge is removed in the Hamiltonian cycle,
-\textit{i.e.} which bit in $\llbracket 1, {\mathsf{N}} \rrbracket$
-cannot be switched.
+Soit $h: \Bool^{\mathsf{N}} \to [{\mathsf{N}}]$
+qui mémorise pour chaque n{\oe}ud $X \in \Bool^{\mathsf{N}}$ quel
+arc est supprimée à partir du cycle hamiltonien,
+\textit{i.e.} quel bit dans $[{\mathsf{N}} ]$
+ne peut pas être inversé.
-We denote by $E_h$ the set $E\setminus\{(X,Y)\mid X\oplus Y =
-0^{{\mathsf{N}}-h(X)}10^{h(X)-1}\}$. This is the set of the modified hypercube,
-\textit{i.e.}, the ${\mathsf{N}}$-cube where the Hamiltonian cycle $h$
-has been removed.
+On définit ensuite l'ensemble $E_h = E\setminus\{(X,Y)\mid X\oplus Y =
+0^{{\mathsf{N}}-h(X)}10^{h(X)-1}\}$. C'est l'ensemble de tous les arcs
+appartenant à l'hypercube modifié,
+\textit{i.e.}, le ${\mathsf{N}}$-cube où le cycle hamiltonien $h$
+a été enlevé.
-We define the Markov matrix $P_h$ for each line $X$ and
-each column $Y$ as follows:
+On définit la matrice de Markov $P_h$ pour chaque ligne $X$ et
+chaque colonne $Y$ comme suit:
\begin{equation}
\left\{
\begin{array}{ll}
P_h(X,X)=\frac{1}{2}+\frac{1}{2{\mathsf{N}}} & \\
-P_h(X,Y)=0 & \textrm{if $(X,Y)\notin E_h$}\\
-P_h(X,Y)=\frac{1}{2{\mathsf{N}}} & \textrm{if $X\neq Y$ and $(X,Y) \in E_h$}
+P_h(X,Y)=0 & \textrm{si $(X,Y)\notin E_h$}\\
+P_h(X,Y)=\frac{1}{2{\mathsf{N}}} & \textrm{si $X\neq Y$ et $(X,Y) \in E_h$}
\end{array}
\right.
\label{eq:Markov:rairo}
\end{equation}
-We denote by $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ the function
-such that for any $X \in \Bool^{\mathsf{N}} $,
-$(X,\ov{h}(X)) \in E$ and $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$.
-The function $\ov{h}$ is said {\it square-free} if for every $X\in \Bool^{\mathsf{N}}$,
+
+
+
+
+Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction
+telle que pour $X \in \Bool^{\mathsf{N}} $,
+$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$.
+La fonction $\ov{h}$ est dite {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$,
$\ov{h}(\ov{h}(X))\neq X$.
+
+%Let $\Bool^n$ be the set of words of length $n$.
+
\begin{lemma}\label{lm:h}
-If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(X))\neq h(X)$.
+Si $\ov{h}$ est bijective et anti-involutive, alors
+$h(\ov{h}^{-1}(X))\neq h(X)$.
\end{lemma}
\begin{proof}
-Let $\ov{h}$ be bijective.
-Let $k\in \llbracket 1, {\mathsf{N}} \rrbracket$ s.t. $h(\ov{h}^{-1}(X))=k$.
-Then $(\ov{h}^{-1}(X),X)$ belongs to $E$ and
+Soit $\ov{h}$ bijective.
+Soit $k\in \llbracket 1, {\mathsf{N}} \rrbracket$ t.q. $h(\ov{h}^{-1}(X))=k$.
+Alors $(\ov{h}^{-1}(X),X)$ appartient à $E$ et
$\ov{h}^{-1}(X)\oplus X = 0^{{\mathsf{N}}-k}10^{k-1}$.
-Let us suppose $h(X) = h(\ov{h}^{-1}(X))$. In such a case, $h(X) =k$.
-By definition of $\ov{h}$, $(X, \ov{h}(X)) \in E $ and
+Supposons $h(X) = h(\ov{h}^{-1}(X))$. Dans un tel cas, $h(X) =k$.
+Par définition $\ov{h}$, $(X, \ov{h}(X)) \in E $ et
$X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1} = 0^{{\mathsf{N}}-k}10^{k-1}$.
-Thus $\ov{h}(X)= \ov{h}^{-1}(X)$, which leads to $\ov{h}(\ov{h}(X))= X$.
-This contradicts the square-freeness of $\ov{h}$.
+Ainsi $\ov{h}(X)= \ov{h}^{-1}(X)$, ce qui entraine $\ov{h}(\ov{h}(X))= X$ et
+qui contredit le fiat que $\ov{h}$ est anti-involutive.
\end{proof}
-Let $Z$ be a random variable that is uniformly distributed over
-$\llbracket 1, {\mathsf{N}} \rrbracket \times \Bool$.
-For $X\in \Bool^{\mathsf{N}}$, we
-define, with $Z=(i,b)$,
-$$
+Soit $Z$ une variable aléatoire suivant une distribution uniforme sur
+$[ {\mathsf{N}}] \times \Bool$.
+Pour $X\in \Bool^{\mathsf{N}}$, on définit avec $Z=(i,b)$,
+\[
\left\{
\begin{array}{ll}
-f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{if } b=1 \text{ and } i\neq h(X),\\
+f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{ si } b=1 \text{ et } i\neq h(X),\\
f(X,Z)=X& \text{otherwise.}
\end{array}\right.
-$$
+\]
-The Markov chain is thus defined as
-$$
-X_t= f(X_{t-1},Z_t)
-$$
+La chaîne de Markov est ainsi définie par
+\[
+X_t= f(X_{t-1},Z_t).
+\]
-%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
-%\section{Stopping time}
-An integer $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ is said {\it fair}
-at time $t$ if there
-exists $0\leq j <t$ such that $Z_{j+1}=(\ell,\cdot)$ and $h(X_j)\neq \ell$.
-In other words, there exist a date $j$ before $t$ where
-the first element of the random variable $Z$ is exactly $l$
-(\textit{i.e.}, $l$ is the strategy at date $j$)
-and where the configuration $X_j$ allows to traverse the edge $l$.
+Un entier $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ est \emph{équitable}
+ au temps $t$ s'il existe $0\leq j <t$ tel que $Z_{j+1}=(\ell,\cdot)$ et $h(X_j)\neq \ell$. En d'autres mots, il existe une date $j$ anérieure à $t$
+où le premier élément de la variable aléatoire $Z$ est $l$
+(\textit{i.e.}, la stratégie vaut $l$ à la date $j$)
+et où le n{\oe}ud $X_j$ permet de traverser l'arc $l$.
-Let $\ts$ be the first time all the elements of $\llbracket 1, {\mathsf{N}} \rrbracket$
-are fair. The integer $\ts$ is a randomized stopping time for
-the Markov chain $(X_t)$.
+Soit $\ts$ le premier tempsoù touis les éléments de $\llbracket 1, {\mathsf{N}} \rrbracket$
+sont équitables. On a le lemme suiant:%L'entier $\ts$ est un temps d'arrêt pour la chaîne de Markov $(X_t)$.
\begin{lemma}
-The integer $\ts$ is a strong stationary time.
+L'entier $\ts$ est un temps stationnaire fort.
\end{lemma}
\begin{proof}
-Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable
-$Z_{\tau_\ell}$ is of the form $(\ell,b)$ %with $\delta\in\{0,1\}$ and
-such that
-$b=1$ with probability $\frac{1}{2}$ and $b=0$ with probability
-$\frac{1}{2}$. Since $h(X_{\tau_\ell-1})\neq\ell$ the value of the $\ell$-th
-bit of $X_{\tau_\ell}$
-is $0$ or $1$ with the same probability ($\frac{1}{2}$).
+Soit $\tau_\ell$ la première date où $\ell$ est équitable.
+La variable aléatoire $Z_{\tau_\ell}$ est de la forme $(\ell,b)$ %with $\delta\in\{0,1\}$ and
+et telle que
+$b=1$ avec la probabilité $\frac{1}{2}$ et $b=0$ avec la probabilité
+$\frac{1}{2}$. Comme $h(X_{\tau_\ell-1})\neq\ell$,
+la valeur du $\ell^{\textrm{ème}}$
+bit de $X_{\tau_\ell}$
+est $0$ ou $1$ avec la même probabilité ($\frac{1}{2}$).
+
+A chaque étape, le $l^{\textrm{ème}}$ bit est inversé de $0$ à $1$ ou de $1$ à $0$, chaque fois avec la même
+probabilité. Ainsi, pour $t\geq \tau_\ell$, le
+$\ell^{\textrm{ème}}$ bit de $X_t$ est $0$ ou $1$ avec la même probabilité,
+et ce indépendament de la valeur des autres bits.
+\end{proof}
- Moving next in the chain, at each step,
-the $l$-th bit is switched from $0$ to $1$ or from $1$ to $0$ each time with
-the same probability. Therefore, for $t\geq \tau_\ell$, the
-$\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the
-lemma.\end{proof}
-\theostopmajorant*
-For each $X\in \Bool^{\mathsf{N}}$ and $\ell\in\llbracket 1,{\mathsf{N}}\rrbracket$,
-let $S_{X,\ell}$ be the
-random variable that counts the number of steps
-from $X$ until we reach a configuration where
-$\ell$ is fair. More formally
-$$S_{X,\ell}=\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ and }Z_t=(\ell,.)\text{ and } X_0=X\}.$$
-% We denote by
-% $$\lambda_h=\max_{X,\ell} S_{X,\ell}.$$
+
+
+
+Pour chaque $X\in \Bool^{\mathsf{N}}$ et $\ell\in [{\mathsf{N}}]$,
+soit $S_{X,\ell}$ une variable aléatoire qui compte le nombre d'itérations
+tel qu'en démarant de la configuration $X$ on en atteigne une où
+$\ell$ est équitable. Plus formellement,
+$$S_{X,\ell}=\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ et }Z_t=(\ell,.)\text{ et } X_0=X\}.$$
+On peut majorer l'espérance de cette variable aléatoire comme suit.
\begin{lemma}\label{prop:lambda}
-Let $\ov{h}$ is a square-free bijective function. Then
-for all $X$ and
-all $\ell$,
-the inequality
-$E[S_{X,\ell}]\leq 8{\mathsf{N}}^2$ is established.
+Soit $\ov{h}$ un fonction bijective et anti-involutive. Alors pour tout
+ $X\in \Bool^{\mathsf{N}}$ et $\ell\in [{\mathsf{N}}]$,
+l'inégalité $E[S_{X,\ell}]\leq 8{\mathsf{N}}^2$ est établie.
\end{lemma}
\begin{proof}
-For every $X$, every $\ell$, one has $\P(S_{X,\ell})\leq 2)\geq
-\frac{1}{4{\mathsf{N}}^2}$.
-Let $X_0= X$.
-Indeed,
+Montrons tout d'abord que pour chaque $X$ et chaque $\ell$, on a $\P(S_{X,\ell})\leq 2)\geq
+\frac{1}{4{\mathsf{N}}^2}$. Soit $X_0= X$.
+
\begin{itemize}
-\item if $h(X)\neq \ell$, then
+\item Si $h(X)\neq \ell$, alors
$\P(S_{X,\ell}=1)=\frac{1}{2{\mathsf{N}}}\geq \frac{1}{4{\mathsf{N}}^2}$.
-\item otherwise, $h(X)=\ell$, then
-$\P(S_{X,\ell}=1)=0$.
-But in this case, intuitively, it is possible to move
-from $X$ to $\ov{h}^{-1}(X)$ (with probability $\frac{1}{2N}$). And in
-$\ov{h}^{-1}(X)$ the $l$-th bit can be switched.
-More formally,
-since $\ov{h}$ is square-free,
-$\ov{h}(X)=\ov{h}(\ov{h}(\ov{h}^{-1}(X)))\neq \ov{h}^{-1}(X)$. It follows
-that $(X,\ov{h}^{-1}(X))\in E_h$. We thus have
-$P(X_1=\ov{h}^{-1}(X))=\frac{1}{2{\mathsf{N}}}$. Now, by Lemma~\ref{lm:h},
-$h(\ov{h}^{-1}(X))\neq h(X)$. Therefore $\P(S_{x,\ell}=2\mid
-X_1=\ov{h}^{-1}(X))=\frac{1}{2{\mathsf{N}}}$, proving that $\P(S_{x,\ell}\leq 2)\geq
+\item Sinon, $h(X)=\ell$, alors
+$\P(S_{X,\ell}=1)=0$. Dans ce cas, intuitivement, il est possible de passer de $X$ à $\ov{h}^{-1}(X)$
+(avec la probabilité $\frac{1}{2N}$). De plus, dans la configuration
+$\ov{h}^{-1}(X)$, le $l^{\textrm{ème}}$ bit peut être inversé.
+Plus formellement, puisque $\ov{h}$ est anti-involutive,
+$\ov{h}(X)=\ov{h}(\ov{h}(\ov{h}^{-1}(X)))\neq \ov{h}^{-1}(X)$. On en déduit
+que $(X,\ov{h}^{-1}(X))\in E_h$. On a ainsi
+$P(X_1=\ov{h}^{-1}(X))=\frac{1}{2{\mathsf{N}}}$.
+D'après le lemme~\ref{lm:h},
+$h(\ov{h}^{-1}(X))$ est différent de $h(X)$.
+Ainsi, $\P(S_{x,\ell}=2\mid X_1=\ov{h}^{-1}(X))=\frac{1}{2{\mathsf{N}}}$,
+prouvant ainsi que $\P(S_{x,\ell}\leq 2)\geq
\frac{1}{4{\mathsf{N}}^2}$.
\end{itemize}
-Therefore, $\P(S_{X,\ell}\geq 3)\leq 1-\frac{1}{4{\mathsf{N}}^2}$. By induction, one
-has, for every $i$, $\P(S_{X,\ell}\geq 2i)\leq
+Ainsi, $\P(S_{X,\ell}\geq 3)\leq 1-\frac{1}{4{\mathsf{N}}^2}$. Par induction, on a,
+pour chaque $i$, $\P(S_{X,\ell}\geq 2i)\leq
\left(1-\frac{1}{4{\mathsf{N}}^2}\right)^i$.
- Moreover,
-since $S_{X,\ell}$ is positive, it is known~\cite[lemma 2.9]{proba}, that
-$$E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i).$$
-Since $\P(S_{X,\ell}\geq i)\geq \P(S_{X,\ell}\geq i+1)$, one has
-$$E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i)\leq
-\P(S_{X,\ell}\geq 1)+\P(S_{X,\ell}\geq 2)+2 \sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq 2i).$$
-Consequently,
+De plus,
+puisque $S_{X,\ell}$ est positive, on sait~\cite[lemme 2.9]{proba} que
+\[
+E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i).
+\]
+Puisque $\P(S_{X,\ell}\geq i)\geq \P(S_{X,\ell}\geq i+1)$, on a
+\[
+E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i)\leq
+\P(S_{X,\ell}\geq 1)+\P(S_{X,\ell}\geq 2)+2 \sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq 2i).\]
+Ainsi,
$$E[S_{X,\ell}]\leq 1+1+2
\sum_{i=1}^{+\infty}\left(1-\frac{1}{4{\mathsf{N}}^2}\right)^i=2+2(4{\mathsf{N}}^2-1)=8{\mathsf{N}}^2,$$
-which concludes the proof.
+ce qui conclut la preuve du lemme.
\end{proof}
-Let $\ts^\prime$ be the time used to get all the bits but one fair.
+Soit $\ts^\prime$ la variable aléatoire comptant le nombre d'itérations pour avoir exactement
+$\mathsf{N}-1$ bits équitables. On peut majorer son espérance.
\begin{lemma}\label{lm:stopprime}
-One has $E[\ts^\prime]\leq 4{\mathsf{N}} \ln ({\mathsf{N}}+1).$
+On a $E[\ts^\prime]\leq 4{\mathsf{N}} \ln ({\mathsf{N}}+1).$
\end{lemma}
\begin{proof}
-This is a classical Coupon Collector's like problem. Let $W_i$ be the
-random variable counting the number of moves done in the Markov chain while
-we had exactly $i-1$ fair bits. One has $\ts^\prime=\sum_{i=1}^{{\mathsf{N}}-1}W_i$.
- But when we are at position $X$ with $i-1$ fair bits, the probability of
- obtaining a new fair bit is either $1-\frac{i-1}{{\mathsf{N}}}$ if $h(X)$ is fair,
- or $1-\frac{i-2}{{\mathsf{N}}}$ if $h(X)$ is not fair.
-
-Therefore,
+C'est un problème classique de collectionneur de vignettes. Soit $W_i$ la variable aléatoire
+comptant le nombre de déplacements dans la chaîne de Markov pour avoir exactement
+$i-1$ bits équitables. On a $\ts^\prime=\sum_{i=1}^{{\mathsf{N}}-1}W_i$.
+Dans la configuration $X$ avec $i-1$ bits équitables,
+la probabilité d'obtenir un nouveau bit équitable est soit
+$1-\frac{i-1}{{\mathsf{N}}}$ si $h(X)$ est équitable,
+et $1-\frac{i-2}{{\mathsf{N}}}$ si $h(X)$ ne l'est pas.
+
+Ainsi,
$\P (W_i=k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}}.$
-Consequently, we have $\P(W_i\geq k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}-i+1}.$
-It follows that $E[W_i]=\sum_{k=1}^{+\infty} \P (W_i\geq k)\leq {\mathsf{N}} \frac{{\mathsf{N}}-i+2}{({\mathsf{N}}-i+1)^2}\leq \frac{4{\mathsf{N}}}{{\mathsf{N}}-i+2}$.
-
-
+On a par conséquent $\P(W_i\geq k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}-i+1}.$
+On en déduit que
+\[
+E[W_i]=\sum_{k=1}^{+\infty} \P (W_i\geq k)\leq {\mathsf{N}} \frac{{\mathsf{N}}-i+2}{({\mathsf{N}}-i+1)^2}\leq \frac{4{\mathsf{N}}}{{\mathsf{N}}-i+2},
+\]
+et donc que
-It follows that
-$E[W_i]\leq \frac{4{\mathsf{N}}}{{\mathsf{N}}-i+2}$. Therefore
-$$E[\ts^\prime]=\sum_{i=1}^{{\mathsf{N}}-1}E[W_i]\leq
+\[
+E[\ts^\prime]=\sum_{i=1}^{{\mathsf{N}}-1}E[W_i]\leq
4{\mathsf{N}}\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{{\mathsf{N}}-i+2}=
-4{\mathsf{N}}\sum_{i=3}^{{\mathsf{N}}+1}\frac{1}{i}.$$
+4{\mathsf{N}}\sum_{i=3}^{{\mathsf{N}}+1}\frac{1}{i}.\]
-But $\sum_{i=1}^{{\mathsf{N}}+1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}+1)$. It follows that
+Or $\sum_{i=1}^{{\mathsf{N}}+1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}+1)$. On en déduit que
$1+\frac{1}{2}+\sum_{i=3}^{{\mathsf{N}}+1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}+1).$
-Consequently,
-$E[\ts^\prime]\leq
+Ainsi, on a la majoration suivante
+\[
+E[\ts^\prime]\leq
4{\mathsf{N}} (-\frac{1}{2}+\ln({\mathsf{N}}+1))\leq
-4{\mathsf{N}}\ln({\mathsf{N}}+1)$.
+4{\mathsf{N}}\ln({\mathsf{N}}+1),
+\]
+ce qui termine la preuve du lemme.
\end{proof}
-One can now prove Theorem~\ref{prop:stop}.
-
+Tous les éléments sont en place pour majorer l'espérance de $\ts$.
+\begin{theorem}
+\label{prop:stop}
+Si $\ov{h}$ est bijective et anti involutive
+$\ov{h}(\ov{h}(X))\neq X$, alors
+$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$.
+\end{theorem}
\begin{proof}
-Since $\ts^\prime$ is the time used to obtain $\mathsf{N}-1$ fair bits.
-Assume that the last unfair bit is $\ell$. One has
-$\ts=\ts^\prime+S_{X_\tau,\ell}$, and therefore
-$E[\ts] = E[\ts^\prime]+E[S_{X_\tau,\ell}]$. Therefore,
-Theorem~\ref{prop:stop} is a direct application of
-lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
+Sans perte de généralité, considérons que le dernier bit
+non équitable est $\ell$. On a
+$\ts=\ts^\prime+S_{X_\tau,\ell}$ et donc
+$E[\ts] = E[\ts^\prime]+E[S_{X_\tau,\ell}]$. Ainsi, le théorème
+est une application directe des lemmes~\ref{prop:lambda} et~\ref{lm:stopprime}.
\end{proof}
-Notice that the calculus of the stationary time upper bound is obtained
-under the following constraint: for each vertex in the $\mathsf{N}$-cube
-there are one ongoing arc and one outgoing arc that are removed.
-The calculus does not consider (balanced) Hamiltonian cycles, which
-are more regular and more binding than this constraint.
-In this later context, we claim that the upper bound for the stopping time
-should be reduced.
+Montrons alors le théorème~\ref{theo:tmps:mix} rappelé ci-dessous
+
+\theotpsmix*
+
+\begin{proof}
+Comme $\tau$ est positive, on peut appliquer l'inégalité de Markov:
+\[
+\P_X(\tau > t)\leq \frac{E[\tau]}{t}.
+\]
+
+En posant $t_n=32N^2+16N\ln (N+1)$, on obtient:
+\[
+\P_X(\tau > t_n)\leq \frac{1}{4}.
+\]
+
+
+D'après la définition de $t_{\rm mix}$ et d'après le théorème~\ref{thm-sst},
+on en déduit
+\[
+t_{\rm mix}\leq 32N^2+16N\ln (N+1)=O(N^2)
+\].
+\end{proof}
-\begin{theorem}\label{th:cplxt:hugo}
-Le schéma HUGO a une complexité de l'ordre de
-$\theta(2 \times n^2(343^2 + \ln(n)))$
-\end{theorem}
+Démontrons le théorème suivant:
+
+\theocplstegano*
First of all, HUGO starts with computing the second order SPAM Features.
\part{Application au marquage de média}
-\chapter{Des embarquement préservant le chaos}\label{chap:watermarking}
+\chapter{Des embarquements préservant le chaos}\label{chap:watermarking}
\input{oxford}
\chapter{Une démarche de marquage de PDF}
\input{ahmad}
-
\chapter{Une démarches plus classique de dissimulation: STABYLO}
\input{stabylo}
\section{Codes de Gray équilibrés par induction}
\input{annexePreuveGrayEquilibre}
-\section{Majoration du temps d'arrêt}
+\section{Majoration du temps de mixage}
\input{annexePreuveStopping}
\chapter{Preuves sur le marquage de média}\label{anx:marquage}
\section{Le marquage est correct et complet}\label{anx:preuve:marquage:correctioncompletue}
\input{annexePreuveMarquageCorrectioncompletude}
-\backmatter
-\section{Complexités d'algorithmes de stéganographie}
-\label{anx:preuve:cplxt}
-\input{annexePreuvesComplexiteStego}
+% \section{Complexités d'algorithmes de stéganographie}
+% \label{anx:preuve:cplxt}
+% \input{annexePreuvesComplexiteStego}
\bibliography{abbrev,biblioand}
\listoffigures
\listoftables
-\listofdefinitions
+
\end{document}
Dans ce chapitre, le processus d'embarquement d'un message dans
un média est formalisé en section~\ref{sec:watermarking:formulation}.
La sécurité des approches de watermarking est étudiée selon deux approches:
-l'approche probabiliste~\ref{sec:watermarking:security:probas}
-et l'approche chaotique~\ref{sec:watermarking:security:chaos}.
+l'approche probabiliste (section~\ref{sec:watermarking:security:probas})
+et l'approche chaotique (section~\ref{sec:watermarking:security:chaos}).
Une proposition d'embarquement dans le domaine fréquentiel est abordée
en section~\ref{sec:watermarking:frequentiel}.
Le processus de marquage est fondé sur les itérations unaires d'une fonction
selon une stratégie donnée. Cette fonction et cette stratégie
sont paramétrées par un entier naturel permettant à la méthode d'être
-appliquable à un média de n'importe quelle taille.
+applicable à un média de n'importe quelle taille.
On parle alors respectivement de \emph{mode} et d'\emph{adapteur de stratégies}
\subsection{Embarquement}
de $\Nats$ dans l'ensemble des séquences d'entiers
qui associe à chaque entier naturel
$\mathsf{N}$ la suite
- $S \in \llbracket 1, n\rrbracket^{\mathds{N}}$.
+ $S \in [\mathsf{N}@]^{\mathds{N}}$.
\end{Def}
On définit par exemple l'adapteur CIIS (\emph{Chaotic Iterations with Independent Strategy})
paramétré par $(K,y,\alpha,l) \in [0,1]\times [0,1] \times ]0, 0.5[ \times \mathds{N}$
-qui associe à chque entier $n \in \Nats$ la suite
+qui associe à chaque entier $\mathsf{N} \in \Nats$ la suite
$(S^t)^{t \in \mathds{N}}$ définie par:
\begin{itemize}
\item $K^0 = \textit{bin}(y) \oplus \textit{bin}(K)$: $K^0$ est le nombre binaire (sur 32 bits)
entre les décompositions binaires sur 32 bits des réels $y$ et $K$
(il est aussi compris entre 0 et 1),
\item $\forall t \leqslant l, K^{t+1} = F(K^t,\alpha)$,
- \item $\forall t \leqslant l, S^t = \left \lfloor n \times K^t \right \rfloor + 1$,
+ \item $\forall t \leqslant l, S^t = \left \lfloor \mathsf{N} \times K^t \right \rfloor + 1$,
\item $\forall t > l, S^t = 0$,
\end{itemize}
-où est la fonction chaotique linéaire par morceau~\cite{Shujun1}.
+où $F$ est la fonction chaotique linéaire par morceau~\cite{Shujun1}.
Les paramètres $K$ et $\alpha$ de cet adapteur de stratégie peuvent être vus
comme des clefs.
On remarque que cette stratégie est unaire.
Cette fonction peut dépendre du message $y$ à embarquer, ou non.
\end{Def}
-Pour alléger le discours, par la suite, on nottera $(u^k(x))$ pour $(u^k)$
-lorsque cela n'est pas ambigüe.
+Pour alléger le discours, par la suite, on notera $(u^k(x))$ pour $(u^k)$
+lorsque cela n'est pas ambiguë.
Il reste à partionner les bits de $x$ selon qu'ils sont
peu, moyennement ou très significatifs.
\begin{Def}[Signification des bits]\label{def:msc,lsc}
Soit $u$ une fonction de signification,
$m$ et $M$ deux réels t.q. $m < M$. Alors:
-$u_M$, $u_m$ et $u_p$ sont les vecteurs finis respectivements des
+$u_M$, $u_m$ et $u_p$ sont les vecteurs finis respectivement des
\emph{bits les plus significatifs (MSBs)} de $x$,
\emph{bits les moins significatifs (LSBs)} de $x$
\emph{bits passifs} of $x$ définis par:
\end{eqnarray*}
\end{Def}
-On peut alors définir une fonction de décompostion
+On peut alors définir une fonction de décomposition
puis de recomposition pour un hôte $x$:
\mathfrak{B}
$ tel que
\begin{itemize}
-\item les ensembles $u_M$, $u_m$ et $u_p$ forment une partition de $[n]$;
+\item les ensembles $u_M$, $u_m$ et $u_p$ forment une partition de $[\mathsf{N}]$;
\item $|u_M| = |\varphi_M|$, $|u_m| = |\varphi_m|$ et $|u_p| = |\varphi_p|$.
\end{itemize}
Soit la base canonique sur l'espace vectoriel $\mathds{R}^{\mid x \mid}$ composée des vecteurs
\begin{Def}[Embarquement dhCI étendu]
\label{def:dhCI:ext}
-Soit $\textit{dec}(u,m,M)$ une function de décomposition,
+Soit $\textit{dec}(u,m,M)$ une fonction de décomposition,
$f$ un mode,
$\mathcal{S}$ un adapteur de stratégie,
$x$ un hôte,
\begin{itemize}
\item le mode $f$ est instancié avec le paramètre $l=|u_m|$, engendrant la
fonction $f_{l}:\Bool^{l} \rightarrow \Bool^{l}$;
-\item l'adapteur de stratégie $\mathcal{S}$ est intancié avec le paramètre
+\item l'adapteur de stratégie $\mathcal{S}$ est instancié avec le paramètre
$y$, engendrant une stratégie $S_y \in [l]$;
\item on itère la fonction $G_{f_l}$ en prenant la configuration
initiale $(S_y,\phi_{m})$ selon le schéma défini
-\subsection{Détection d'un media marqué}\label{sub:wmdecoding}
+\subsection{Détection d'un média marqué}\label{sub:wmdecoding}
On caractérise d'abord ce qu'est un média marqué selon la méthode énoncée
à la section précédente. On considère que l'on connaît
$z$.
-\begin{definition}[Média marqué]
+\begin{Def}[Média marqué]
Soit $\textit{dec}(u,m,M)$ une fonction de décomposition
$f$ un mode,
$\mathcal{S}$ un adapteur de stratégie
$(u_M,u_m,u_p,\phi_{M},\phi_{m},\phi_{p})$ l'image par
$\textit{dec}(u,m,M)$ du média $x$.
Alors, $z$ est \emph{marqué} avec $y$ si l'image
-par $\textit{dec}(u,m,M)$ of $z$ is
+par $\textit{dec}(u,m,M)$ of $z$ est
$(u_M,u_m,u_p,\phi_{M},\hat{y},\phi_{p})$, où
$\hat{y}$ est le second membre de $G_{f_l}^q(S_y,\phi_{m})$.
-\end{definition}
+\end{Def}
% Plusieurs stratégies peuvent être utilisées pour déterminer si une image $z$
% est marquée, en particulier si l'image a été attaquée entre temps.
Récemment~\cite{Cayre2005,Perez06} ont proposé des classes de sécurité pour le
-marquage d'information. Parmis celles-ci, la stego-sécurité a été au centre
+marquage d'information. Parmi celles-ci, la stego-sécurité a été au centre
des travaux puisqu'elle représente la classe la plus élevée dans le contexte où
l'attaquant n'a accès qu'à l'hôte marqué $z$.
Cette définition probabiliste est rappelée ci-après.
-Soit $\mathds{K}$ un ensemble de clefs, $p(X)$ un modèle porbabiliste
+Soit $\mathds{K}$ un ensemble de clefs, $p(X)$ un modèle probabiliste
de $N_0$ hôtes, et $p(Y|K)$ le modèle probabiliste de $N_0$ contenus marqués avec la
même clé $K$ et le même algorithme d'embarquement.
-\begin{definition}[Stégo-Sécurité~\cite{Cayre2008}]
+\begin{Def}[Stégo-Sécurité~\cite{Cayre2008}]
\label{Def:Stego-security}
-La fonction d'embarquement is \emph{stégo-sécure}
+La fonction d'embarquement est \emph{stégo-sécure}
si la propriété $\forall K \in \mathds{K}, p(Y|K)=p(X)$ est établie.
-\end{definition}
+\end{Def}
Il a déjà été démontré~\cite{guyeuxphd,gfb10:ip}
que l'algorithme de marquage dont le mode est la fonction
négation est stégo-sécure.
Un des intérêts de l'algorithme présenté ici est qu'il est paramétré par un mode.
Lorsque celui-ci a les même propriétés que celles vues pour la création de PRNG (\textit{i.e.} graphe des itérations fortement connexes et matrice de Markov doublement
-stochastique), on a un marquage qui peut être rendu stego-secure à $\epsilon$ pret,
-ce que précise le théorème suivant:
+stochastique), on a un marquage qui peut être rendu stégo-sécure à $\varepsilon$ prêt,
+ce que précise le théorème suivant. La preuve de ce théorème est donnée
+en annexes~\ref{anx:marquage}.
+
-\begin{theorem}\label{th:stego}
-Soit $\epsilon$ un nombre positif,
+\begin{restatable}[$\varepsilon$-stego sécurité]{theorem}{theoremstegoscureepsilon}
+\label{th:stego}
+Soit $\varepsilon$ un nombre positif,
$l$ un nombre de LSBs,
$X \sim \mathbf{U}\left(\mathbb{B}^l\right)$,
-un adapteur de stratégie uniformémement distribué indépendant de $X$
+un adapteur de stratégie uniformément distribué indépendant de $X$
$f_l$ un mode tel que
$\textsc{giu}(f_l)$ est fortement connexe et la
matrice de Markov associée à $f_l$ est doublement stochastique.
Il existe un nombre $q$ d'itérations tel que
-$|p(Y|K)- p(X)| < \epsilon$.
-\end{theorem}
+$|p(Y|K)- p(X)| < \varepsilon$.
+\end{restatable}
introduite dans~\cite{guyeuxphd}.
-\begin{definition}[Chaos-sécurité]
+\begin{Def}[Chaos-sécurité]
\label{DefinitionChaosSecure}
Un schéma de marquage $S$ est chaos-sécure sur un espace topologique
$(\mathcal{X},\tau)$
si sa version itérative
-a un comprtement chaotique sur celui-ci.
-\end{definition}
+a un comportement chaotique sur celui-ci.
+\end{Def}
Tout repose ainsi sur la capacité que l'on a à produire des fonctions
dont le graphe des itérations unaires sera fortement connexe.
\right.
\end{equation}\label{eq:fqq}
-on peut déduire imédiatement du théorème~\ref{th:Adrien} (chap.~\ref{chap:carachaos})
+on peut déduire immédiatement du théorème~\ref{th:Adrien} (chap.~\ref{chap:carachaos})
que le graphe $\textsc{giu}(f_l)$ est fortement connexe.
La preuve de double-stochasiticité de la matrice associée
à $f_l$ est donnée en annexes~\ref{anx:marquage:dblesto}.
-On dispose ainsi d'un nouvel algorithme de marquage $\epsilon$-stego-secure et
+On dispose ainsi d'un nouvel algorithme de marquage $\varepsilon$-stégo-sécure et
chaos-sécure.
\section{Applications aux domaines fréquentiels}\label{sec:watermarking:frequentiel}
\subsection{Fonction de signification pour l'embarquement dans les DCT}
-On considère un hôte $x$ de taille $H \times L$ dans le domaine fréqentiel DCT.
+On considère un hôte $x$ de taille $H \times L$ dans le domaine fréquentiel DCT.
Dans chaque bloc de taille $8\times 8$, à chaque bit
la fonction de signification $u$ associe
\begin{itemize}
-\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur d'un coefficient dont les coordonnées appartiennent à $\{(1,1),(2,1),(1,2)\}$,
-\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur
+\item 1 si c'est un bit apparaissant dans la représentation binaire de la valeur d'un coefficient dont les coordonnées appartiennent à $\{(1,1),(2,1),(1,2)\}$,
+\item 1 si c'est un bit apparaissant dans la représentation binaire de la valeur
d'un coefficient dont les
coordonnées appartiennent à $\{(3,1),(2,2),(1,3)\}$ et qui n'est pas un des trois
bits de poids faible de cette représentation,
-\item -1 si c'est un bit appraissant dans la représentation binaire
+\item -1 si c'est un bit apparaissant dans la représentation binaire
de la valeur d'un coefficient dont les
coordonnées appartiennent à $\{(3,1),(2,2),(1,3)\}$ et qui est un des
des trois bits de poids faible de cette valeur,
\end{itemize}
Le choix de l'importance de chaque coefficient est défini grâce aux seuils
$(m,M)=(-0.5,0.5)$
-permetant d'engendrer les MSBs, LSBs, et bits passifs.
+permettant d'engendrer les MSBs, LSBs, et bits passifs.
\subsection{Fonction de signification pour l'embarquement dans les DWT}
-On considère un hôte dnas le domaine des DWT. La fonction de signification
+On considère un hôte dans le domaine des DWT. La fonction de signification
se concentre sur les seconds niveaux de détail (\textit{i.e.}, LH2, HL2 et HH2).
Pour chaque bit, on dit qu'il est peu significatif si c'est un des trois bits de
poids faible d'un coefficient de LH2, HL2 ou de HH2.
la fonction de signification $u$ associe
\begin{itemize}
-\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur d'un coefficient de type LL2,
-\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur d'un coefficient de type LH2, HL2, HH2 et qui n'est pas un des trois
+\item 1 si c'est un bit apparaissant dans la représentation binaire de la valeur d'un coefficient de type LL2,
+\item 1 si c'est un bit apparaissant dans la représentation binaire de la valeur d'un coefficient de type LH2, HL2, HH2 et qui n'est pas un des trois
bits de poids faible de cette représentation,
-\item 1 si c'est un bit appraissant dans la représentation binaire de la valeur d'un coefficient de type LH2, HL2, HH2 et qui est un des trois
+\item 0 si c'est un bit apparaissant dans la représentation binaire de la valeur d'un coefficient de type LH2, HL2, HH2 et qui est un des trois
bits de poids faible de cette représentation,
-\item 0 sinon.
+\item -1 sinon.
\end{itemize}
Le choix de l'importance de chaque coefficient est encore défini grâce aux seuils
$(m,M)=(-0.5,0.5)$
-permetant d'engendrer les MSBs, LSBs, et bits passifs.
+permettant d'engendrer les MSBs, LSBs, et bits passifs.
\subsection{Etude de robustesse}
Cette partie synthétise une étude de robustesse de la démarche présentée ci-avant.
Dans ce qui suit, {dwt}(neg),
{dwt}(fl), {dct}(neg), {dct}(fl)
-correpondent respectivement aux embarquements en fréquenciel
+correspondant respectivement aux embarquements en fréquentiels
dans les domaines DWT et DCT
avec le mode de négation et celui issu de la fonction $f_l$
détaillé à l'équation~\ref{eq:fqq}.
de la base du concours BOSS~\cite{Boss10}. Chaque hôte est une image
en $512\times 512$ en niveau de gris et la marque $y$ est une suite de
4096 bits.
-La resistance à la robustesse est évaluée en appliquant successivement
+La résistances à la robustesse est évaluée en appliquant successivement
sur l'image marquée des attaques de découpage, de compression, de
transformations géométriques.
Si les différences entre $\hat{y}$ and $\varphi_m(z)$.
-sont en desous d'un seuil(que l'on définit),
+sont en dessous d'un seuil (que l'on définit),
l'image est dite marquée (et non marquée dans le cas contraire).
-Cette différence exprimée en pourcentage est rappellée pour chacune des ataques
+Cette différence exprimée en pourcentage est rappelée pour chacune des attaques
à la figure~\ref{fig:atq:dhc}.
\subfigure[Compression JPEG 2000]{
\includegraphics[width=0.45\textwidth]{atq-jp2}\label{Fig:atq:jp2:curves}
}
- \subfigure[Modification du contrast]{
+ \subfigure[Modification du contraste]{
% \includegraphics[width=0.45\textwidth]{atq-contrast.pdf}\label{Fig:atq:cont:curve}}
\includegraphics[width=0.45\textwidth]{atq-contrast}\label{Fig:atq:cont:curve}
}
\end{figure}
-\subsection{Evaluation de l'embarquement}\label{sub:roc}
+\subsection{Évaluation de l'embarquement}\label{sub:roc}
Pour évaluer le seuil qui permet de dire avec la plus grande précision
si une image est marquée ou non, nous avons appliqué la démarche suivante.
A partir d'un ensemble de 100 images du challenge BOSS, les trois
ensembles suivants sont construits: celui des images marquées $W$,
-celui contenant des imges marquées puis attaquée $\textit{WA}$,
-et celui des images uniquement attaquées $A$. Les attaques sont choisiés parmi
+celui contenant des images marquées puis attaquée $\textit{WA}$,
+et celui des images uniquement attaquées $A$. Les attaques sont choisies parmi
celles données ci dessus.
Pour chaque entier $t$ entre 5 et 55
Pour les deux modes dans le domaine DCT,
la détection est optimale pour le seuil de 44\%
(correspondant aux points (0.05, 0.18) et (0.05, 0.28)).
-On peut alors donner des intervales de confiance pour les attaques évaluées.
+On peut alors donner des intervalles de confiance pour les attaques évaluées.
L'approche est résistante à:
\begin{itemize}
\item tous les découpages où le pourcentage est inférieur à 85\%;
ne permet de savoir, \textit{in fine},
que si l'image est marquée ou pas. Cet algorithme ne permet pas
de retrouver le contenu de la marque à partir de l'image marquée.
-C'est l'bjectif de l'algorithme présenté dans cette section et introduit
+C'est l'objectif de l'algorithme présenté dans cette section et introduit
dans~\cite{fgb11:ip}.
-On des raisons de lisibilité, il n'est pas
+Pour des raisons de lisibilité, il n'est pas
présenté pas dans le formalisme de la première section et
est grandement synthétisé.
Il a cependant été prouvé comme étant chaos-sécure~\cite{fgb11:ip}.
\item $\mathbb{S}_\mathsf{k}$ est l'ensemble des stratégies unaire sur $[k]$;
\item $m^0 \in \mathbb{B}^{\mathsf{P}}$ est un vecteur de $\mathsf{P}$ bits
représentant la marque;
-\item comme précédement,
+\item comme précédemment,
$x^0 \in \mathbb{B}^\mathsf{N}$ est le vecteurs des
$\mathsf{N}$ bits sélectionnés où la marque est embarquée.
\item $S_p \in \mathbb{S}_\mathsf{N}$
\end{array}
\right.
\end{equation*}
-%\end{definition}
+%\end{Def}
\noindent où $\overline{m_j^{n-1}}$ est la négation booléenne de $m_j^{n-1}$.
On impose de plus la contrainte suivante.
Soit $\Im(S_p) = \{S^1_p, S^2_p, \ldots, S^l_p\}$
Sans attaque, le schéma doit garantir qu'un utilisateur qui dispose des bonnes
clefs de création des stratégies est capable d'extraire une marque et que
celle-ci est la marque insérée.
-Ceci correspond respectivement aux propriétés de complétudes et de correction
+Ceci correspond respectivement aux propriétés de complétude et de correction
de l'approche.
L'étude de ces propriétés est l'objectif de la section qui suit.
On ne donne ici que le théorème. La preuve est placée en annexes~\ref{anx:preuve:marquage:correctioncompletue}.
-\begin{theorem}
-La condition de l'algorithme de marquage est nécressaire et suffisante
+\begin{restatable}[Correction et complétude du marquage]{theorem}{marquagecorrectioncompl}
+La condition de l'algorithme de marquage est nécessaire et suffisante
pour permettre l'extraction du message du média marqué.
-\end{theorem}
+\end{restatable}
-Sous ces hypothèes, on peut donc extraire un message.
+Sous ces hypothèse, on peut donc extraire un message.
De plus, le cardinal $k$ de
$\Im(S_p)$ est supérieur ou égal à $\mathsf{P}$.
Ainsi le bit $j$ du message original $m^0$ peut être
-embarqué plusieur fois dans $x^l$.
-Or, en compte le nombrede fois où ce bit a été inversé dans
+embarqué plusieurs fois dans $x^l$.
+Or, en comptant le nombre de fois où ce bit a été inversé dans
$S_m$, la valeur de $m_j$ peut se déduire en plusieurs places.
Sans attaque, toutes ces valeurs sont identiques
-et le messageest obtenus immédiatement.
+et le message est obtenus immédiatement.
Si attaque il y a, la valeur de $m_j$ peut s'obtenir en prenant la valeur
-moyenne de toutes les valeurs obtenues. On a donc la correction et la complétude.
+moyenne de toutes les valeurs obtenues.
\subsection{Détecter si le média est marqué}\label{sub:ci2:distances}
On considère un média $y$ marqué par un message $m$.
Soit $y'$ une version altérée de $y$, c.-à-d. une version
où certains bits on été modifiés et soit
-$m'$ le message extrait de from $y'$.
+$m'$ le message extrait de $y'$.
Pour mesurer la distance entre $m'$ et $m$, on
-considère repsectivement
+considère respectivement
$M$ et $M$ l'ensemble des indices de $m$ et de $m'$
où $m_i$ vaut 1 et ou $m'_1$ vaut 1.
corrélés et des ceux qui ne le sont pas.
La distance entre $m$ et $m'$ est construite selon cette mesure
et produit un réel dans $[0;1]$. Si elle est inférieure à un certain
-seuil (à définir), le média $y'$ est declaré
+seuil (à définir), le média $y'$ est déclaré
comme marqué et le message doit pouvoir être extrait.
\subsection{Etude de robustesse}\label{sec:watermarking:robustesse}
\section{Conclusion}
-Grace à la formalisation du processus de watermarking par itérations discrètes, nous avons pu dans ce chapitre montrer que le processus possédait les propriétés
+Grâce à la formalisation du processus de watermarking par itérations discrètes, nous avons pu dans ce chapitre montrer que le processus possédait les propriétés
attendues, à savoir stego-sécurité, chaos sécurité et une robustesse relative.
Pour étendre le champ applicatif, nous avons proposé un second algorithme
permettant de particulariser la marque à embarquer et donc à extraire.
Pour détecter de la présence ou non d'un message dans une image,
on peut demander l'oracle à un
un \emph{stéganalyseur}~\cite{LHS08,DBLP:conf/ih/Ker05,FK12}.
-Usuellement, un outil de cette fammille, après
+Usuellement, un outil de cette famille, après
une démarche d'apprentissage, classifie les images
en fonction de caractéristiques numériques.
A partir de caractéristiques de voisinage nommées
-SPAM~\cite{DBLP:journals/tifs/PevnyBF10}, HUGO mesure la distortion
+SPAM~\cite{DBLP:journals/tifs/PevnyBF10}, HUGO mesure la distorsion
qui serait induite par la modification
de chaque pixel. Similairement,
-WOW et UNIWARD construisent une carte de distortion mais celle-ci est
+WOW et UNIWARD construisent une carte de distorsion mais celle-ci est
issue caractéristiques directionnelles calculées à partir d'ondelettes.
-A partir de ces cartes de distortions, chacun de ces algorithmes selectionne
-les pixels dont les modifications induisent la distortion la plus faible
+A partir de ces cartes de distorsion, chacun de ces algorithmes sélectionne
+les pixels dont les modifications induisent la distorsion la plus faible
possible. Ceci revient à définir une fonction de signification $u$.
La complexité du schéma de stéganographie est peu ou prou celle du calcul
de cette carte, et elle est élevée dans le cas
\end{figure*}
-La sécurité de l'encryptage est garantie par le système asymmétrique
+La sécurité de l'encryptage est garantie par le système asymétrique
de Blum-Goldwasser~\cite{Blum:1985:EPP:19478.19501} basé sur le PRNG
Blum Blum Shub~\cite{DBLP:conf/crypto/ShubBB82}.
Ainsi, à partir d'une clef $k$ et un message \textit{mess},
L'idée d'embarquer dans des bords dans une image
repose sur le fait que les pixels de ceux-ci représentent déjà une
rupture de continuité entre pixels voisins.
-Une faible modification de ceux-ci n'a donc pas un grand impact sur la qualité
-de l'image, condition nécéessaire lorsqu'on prétend être indétectable.
+Une faible modification de ceux-ci n'aurait donc pas un grand impact sur la qualité
+de l'image, condition nécessaire lorsqu'on prétend être indétectable.
STABYLO est basé sur les
filtres de Canny~\cite{Canny:1986:CAE:11274.11275}, comme démarche de détection
bits les plus significatifs (pratiquement $b$ vaut $6$ ou $7$)
et un masque de sélection $T$ $T=3,5,7$).
Plus élevée est la valeur de ce masque, plus grand est le nombre
-de pixels de bors mais plus grossière est l'approche.
+de pixels de bord mais plus grossière est l'approche.
Dans le diagramme de flux, cette étape de sélection
est représentée par ``x=Edge Detection(b, T, X)''.
La section suivante montre comment le schéma s'adapte
aux valeurs de $m$ et de $x$.
-\subsection{Un embarquement adaptif}\label{sub:adaptive}
+\subsection{Un embarquement adaptatif}\label{sub:adaptive}
Nous argumentons que le schéma d'embarquement doit s'adapter
au message $m$ et au nombre de bits disponibles pour cet embarquement.
Deux stratégies sont possibles dans STABYLO.
-Dans la première, dite \emph{adaptive}, le taux d'embarquement
+Dans la première, dite \emph{adaptative}, le taux d'embarquement
(rapport entre le nombre de bits embarqués par rapport au nombre de pixels
modifiés) dépend du nombre de bits disponibles à l'issue de l'extraction
des pixels de bords. Si ce nombre de bits est inférieur au double de
la taille du message, celui-ci est découpé en plusieurs parties.
La justification de ce rapport de 1 à 2 à donné ci dessous dans la partie STC.
Dans la seconde dite \emph{fixe}, ce taux est fixe et l'algorithme augmente
-iterativement la valeur de $T$ jusqu'à obtenir à nouveau deux fois plus de bits
+iterrativement la valeur de $T$ jusqu'à obtenir à nouveau deux fois plus de bits
de bords qu'il n'y en a dans le message.
STABYLO applique alors
-par défaut l'agorithme STC~\cite{DBLP:journals/tifs/FillerJF11}
-pour ne modifier aussi peu que posible les bits parmi ceux dont il dispose.
-Dans le cas où c'est la stratégie adaptive qui est choisie, le paramètre
-$\rho$ de cet algorithme vaut 1 pour chaqun des bits.
+par défaut l'algorithme STC~\cite{DBLP:journals/tifs/FillerJF11}
+pour ne modifier aussi peu que possible les bits parmi ceux dont il dispose.
+Dans le cas où c'est la stratégie adoptive qui est choisie, le paramètre
+$\rho$ de cet algorithme vaut 1 pour chacun des bits.
Dans le cas contraire, la valeur de ce paramètre varie en
fonction du seuil $T$ de l'algorithme de détection de bord comme suit:
$$
comparant l'ordre de grandeur de son temps d'exécution avec ceux des
principaux schémas existants à savoir HUGO~\cite{DBLP:conf/ih/PevnyFB10},
WOW~\cite{conf/wifs/HolubF12} et UNIWARD~\cite{HFD14}.
-Chacune de ces quatre méthodes commence par calculer un carte de distortion
+Chacune de ces quatre méthodes commence par calculer un carte de distorsion
de l'ensemble des pixels et se termine en appliquant l'algorithme STC.
Comme cette dernière étape est commune à toutes les approches, on évalue
sa complexité à part.
Dans tout ce qui suit, on considère une image carrée de taille
$n \times n$.
-Les preuves de ces théorèmes sont données en annexes~\ref{anx:preuve:cplxt}.
+Les preuves de ces théorèmes sont données dans~\cite{ccg15:ij}
-\begin{theorem}\label{th:cplxt:hugo}
-Le schéma HUGO a une complexité de l'ordre de
-$\theta(2 \times n^2(343^2 + \ln(n)))$
-\end{theorem}
-
-\begin{theorem}\label{th:cplxt:wow}
-Le schéma WOW a une complexité de l'ordre de
-$\theta(6n^4\ln(n) + n^2)$.
-\end{theorem}
-
-
-\begin{theorem}\label{th:cplxt:uniward}
-Le schéma UNIWARD a une complexité dont l'ordre est supérieur à
+\begin{restatable}[Complexité d'algorithmes de stéganographie]{theorem}{theocplstegano}
+\label{th:cplxt:stegano}
+\begin{itemize}
+\item Le schéma HUGO a une complexité de l'ordre de $\theta(2 \times n^2(343^2 + \ln(n)))$
+\item Les schémas WOW et UNIWARD ont une complexité de l'ordre de
$\theta(6n^4\ln(n) + n^2)$.
-\end{theorem}
-
-\begin{theorem}\label{th:cplxt:stabylo}
-Le schéma STABYLO a une complexité dont l'ordre est
-$\theta((5^3+4T+1)n^2)$.
-\end{theorem}
-
+\item Le schéma STABYLO a une complexité dont l'ordre est $\theta((5^3+4T+1)n^2)$.
+\end{itemize}
+\end{restatable}
D'après~\cite{DBLP:journals/tifs/FillerJF11}, la complexité de
STC est le l'ordre de $\theta(2^h.n)$ où $h$
-est la taille de la matrice dupliquée. Cett complexité linéaire
+est la taille de la matrice dupliquée. Cette complexité linéaire
est donc négligeable par rapport au reste.
\begin{center}
\includegraphics[scale=0.4]{images/complexity}
\end{center}
-\caption{Evaluation de la complexité de WOW/UNIWARD, HUGO et STABYLO}
+\caption{Évaluation de la complexité de WOW/UNIWARD, HUGO et STABYLO}
\label{fig:compared}
\end{figure}
Le schéma STABYLO a été systématiquement comparé à HUGO,
EAISLSBMR~\cite{Luo:2010:EAI:1824719.1824720}, WOW et UNIWARD
-pour les stratégies fixes (10\%) et adaptives.
+pour les stratégies fixes (10\%) et adaptatives.
Pour établir la valeur de cette dernière stratégie, le filtre de Canny a été
paramétré avec une valeur de $T=3$.
-Lorsque $b$ vaut 7, la taile moyenne du message pouvant être embarqué est de
+Lorsque $b$ vaut 7, la taille moyenne du message pouvant être embarqué est de
16,445, \textit{i.e.}, un taux d'embarquement moyen de 6,35\%.
Pour chaque image, le nombre de bits embarqué par STABYLO est mémorisé et il
est demandé à chacun des autres schémas d'embarquer ce même nombre de bits.
\hline
Schéma & \multicolumn{3}{c|}{STABYLO} & \multicolumn{2}{c|}{HUGO}& \multicolumn{2}{c|}{EAISLSBMR} & \multicolumn{2}{c|}{WOW} & \multicolumn{2}{c|}{UNIWARD}\\
\hline
-Strétégie & fixe & \multicolumn{2}{c|}{adapt. ($\approx$6.35\%)} & fixe & adapt. & fixe & adapt. & fixe & adapt. & fixe & adapt. \\
+Stratégie & fixe & \multicolumn{2}{c|}{adapt. ($\approx$6.35\%)} & fixe & adapt. & fixe & adapt. & fixe & adapt. & fixe & adapt. \\
\hline
Ratio & 10\% & +STC(7) & +STC(6) & 10\%& $\approx$6.35\%& 10\%& $\approx$6.35\% & 10\%& $\approx$6.35\%& 10\%& $\approx$6.35\%\\
\hline
\end{tabular}
\end{small}
\end{center}
-\caption{Steganalyse de STABYLO\label{table:steganalyse}.}
+\caption{Stéganalyse de STABYLO\label{table:steganalyse}.}
\end{table*}
-Etant considéré comme le plus exact
+Étant considéré comme le plus exact
stéganalyseur dans le domaine spatial,
Ensemble Classifier~\cite{DBLP:journals/tifs/KodovskyFH12}
a été exécuté avec les caractéristiques
\begin{table}[ht]
-\caption{ Noyaux pour les dérivéees secondes en $x$ et $y$ lors de l'interpolation polynomiale\label{table:sod:diag:poly}
+\caption{ Noyaux pour les dérivées secondes en $x$ et $y$ lors de l'interpolation polynomiale\label{table:sod:diag:poly}
}
\centering
%\scriptsize
\]
-\section{Experimentations}\label{sec:experiments}
+\section{Expérimentations}\label{sec:experiments}
Tout d'abord, l'ensemble du code est accessible en ligne\footnote{\url{https://github.com/stego-content/SOS}}.
La Figure~\ref{fig:oneimage} représente les résultats d'embarquement de données dans
Les deux méthodes présentées ici dépendent de noyaux dont la taille va jusqu'à
$(2N+1)\times(2N+1)$. Cette section montre comment évaluer $N$ pour maximiser
le niveau de sécurité.
-Pour chaque approche, 1,000 images stegos avec
+Pour chaque approche, 1,000 images stégos avec
$N=2$, $4$, $6$, $8$, $10$, $12$ et $14$ et dont les supports appartiennent
à l'ensemble des 10000 images du challenge BOSS.
LA sécurité de l'approche a été évaluée avec le stéganalyseur
La principale contribution de ce chapitre est de proposer des
fonctions de distorsion basées sur des approximations de dérivées
secondes, l'idée sous-jacente étant qu'une zone où les lignes de niveau
-ne sont pas clairement définies est peu prédictible.
+ne sont pas clairement définies est peu prévisible.
Deux approches d'approximation ont été présentées.
La première basée
sur un produit de convolution, exploite des noyaux déjà intégrés dans des
algorithmes de détection de bords.
La seconde s'appuie sur une interpolation polynomiale de l'image.
-Ces deux méthodes onté été complètement implantées et leur sécurité
+Ces deux méthodes ont été complètement implantées et leur sécurité
face à des stéganalyseurs a été étudiée. Les résultats encouragent
à poursuivre dans cette direction.
\ No newline at end of file
