La complexité du schéma de stéganographie est peu ou prou celle du calcul
de cette carte, et elle est élevée (cf partie~\ref{XXXXXXXX}) dans le cas
de ces algorithmes.
+Nous avons proposé un algorithme~\cite{ccg15:ij}
+de complexité beaucoup plus faible
+et dont la détectabilité est satisfaisante.
+Ce chapitre détaille les clefs de ce schéma
+
+
+
+\section{Présentation de l'approche}
+
+Le diagramme de flux donnés à la Fig.~\ref{fig:sch} résume l'approche
+du schéma STABYLO (pour STeganography with Adaptive, Bbs, binarY embedding
+at LOw cost). L'embarquement est synthétisé à la Fig.~\ref{fig:sch:emb} et
+l'extraction à la Fig.~\ref{fig:sch:ext}.
+
+\begin{figure*}%[t]
+ \begin{center}
+ \subfigure[Data Embedding]{
+ \begin{minipage}{0.4\textwidth}
+ \begin{center}
+ %\includegraphics[scale=0.45]{emb}
+ \includegraphics[scale=0.4]{images/emb}
+ \end{center}
+ \end{minipage}
+ \label{fig:sch:emb}
+ }
+\hfill
+ \subfigure[Data Extraction]{
+ \begin{minipage}{0.49\textwidth}
+ \begin{center}
+ \includegraphics[scale=0.4]{images/dec}
+ \end{center}
+ \end{minipage}
+ \label{fig:sch:ext}
+ }%\hfill
+ \end{center}
+ \caption{Présentation générale de STABYLO}
+ \label{fig:sch}
+\end{figure*}
+
+
+La sécurité de l'encryptage est garantie par le système asymmé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},
+ce cryptosystem construit
+le message $m$.
+
+
+\subsection{Un embarquement dans les bords}\label{sub:edge}
+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.
+
+STABYLO est basé sur les
+filtres de Canny~\cite{Canny:1986:CAE:11274.11275}, comme démarche de détection
+de bords retenue pour sa complexité faible et ses possibilités d'implantation
+sur plusieurs supports (GPU, FPGA notamment). Rien n'interdirait cependant
+de l'appliquer à d'autres approches de détection de bord (Sobel, à base de
+logique floue~\cite{KF11},\ldots).
+Cette détection de bords ne considère que les $b$
+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.
+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}
+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
+(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
+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.
+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:
+$$
+\rho_X= \left\{
+\begin{array}{l}
+1 \textrm{ pour un bord défini par $T=3$,} \\
+10 \textrm{ pour un bord défini par $T=5$,} \\
+100 \textrm{ pour un bord défini par $T=7$.}
+\end{array}
+\right.
+$$
+
+
+
+
+\subsection{Extraction du message}\label{sub:extract}
+Résumée à la figure~\ref{fig:sch:ext}, l'extraction du message
+reproduit le processus d'embarquement dans l'ordre inverse
+puisque chaque étape est inversible.
+
+
+
+\section{Analyse de Complexité}
+Dans cette section, on justifie qualificatif \og LOw cost\fg{} de STABYLO en
+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
+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}.
+
+
+\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 à
+$\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}
+
+
+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 donc négligeable par rapport au reste.
+
+
+La figure~\ref{fig:compared} représente graphiquement les complexités
+des étapes d'embarquement des schémas WOW/UNIWARD, HUGO, and STABYLO en
+considérant des images de la taille $n \times n$ où $n$ varie entre
+512 et 4096. L'axe des $y$ est exprimé selon une échelle logarithmique.
+Cette figure illustre bien le fait que le qualificatif de \og LOw cost\fg{}
+attribué à STABYLO.
+\begin{figure}
+\begin{center}
+\includegraphics[scale=0.4]{images/complexity}
+\end{center}
+\caption{Evaluation de la complexité de WOW/UNIWARD, HUGO et STABYLO}
+\label{fig:compared}
+\end{figure}
+
+
+
+
