From: couchot Date: Mon, 29 Aug 2016 18:54:07 +0000 (+0200) Subject: -> prng inclus X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/02fd942d6a30fe7197b732c94450ca466b7a49f5 -> prng inclus --- diff --git a/11FCT.tex b/11FCT.tex index 0e9c64f..45d91c9 100644 --- a/11FCT.tex +++ b/11FCT.tex @@ -90,4 +90,3 @@ Deux fonctions sont équivalentes si leurs \textsc{giu} sont isomorphes \end{center} \caption{Exemple de graphe d'interactions vérifiant le théorème~\ref{th:Adrien}} \label{fig:Adrien:G} \end{figure} - diff --git a/14Secrypt.tex b/14Secrypt.tex index f1fae6f..bc59ba1 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -1,16 +1,29 @@ On a vu dans le chapitre précédent que pour avoir un générateur à sortie uniforme, il est nécessaire que la matrice d'adjacence du graphe d'itération du -système soit doublement stochastique. Nous présentons dans cette partie une -méthode permettant de générer de telles matrices. - -Les approches théoriques basées sur la programmation logique par contraintes sur -domaines finis ne sont pas envisageables en pratique dès que la taille des -matrices considérées devient suffisamment grande. - +système soit doublement stochastique. Nous présentons dans cette partie +des méthodes effectives permettant de générer de telles matrices. +La première est basée sur la programmation logique par contraintes +(Section~\ref{sec:plc}). +Cependant celle-ci souffre de ne pas passer à l'échelle et ne fournit pas +une solution en un temps raisonnable dès que la fonction à engendrer +porte sur un grand nombre de bits. Une approche plus pragmatique consiste à supprimer un cycle hamiltonien dans le -graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graphe une -arête sortante et une arête entrante. +graphe d'itérations $\textsc{giu}(\neg)$ (section~\ref{sec:hamiltonian}). +Pour obtenir plus rapidement une distribution uniforme, l'idéal serait +de supprimer un cycle hamiltonien qui nierait autant de fois chaque bit. +Cette forme de cycle est dit équilibré. La section~\ref{sub:gray} établit le +lien avec les codes de Gray équilibrés, étudiés dans la litérature. +La section suivante présente une démarche de génération automatique de code de Gray équilibré (section~\ref{sec:induction}). +La vitesse avec laquelle l'algorithme de PRNG converge en interne vers +une distribution unifiorme est étduiée théoriquement et pratiquement à la +section~\ref{sec:mixing}. +L'extension du travail aux itérations généralisées est présenté à la +section~\ref{sec:prng:gray:general}. +Finalement, des instances de PRNGS engendrés selon les méthodes détaillées dans +ce chapitre sont présentés en section~\ref{sec:prng;gray:tests}. +Les sections~\ref{sec:plc} à~\ref{sub:gray} ont été publiées +à~\ref{chgw+14:oip}. % This aim of this section is to show @@ -442,7 +455,7 @@ Ces fonctions étant générées, on s'intéresse à étudier à quelle vitesse un générateur les embarquant converge vers la distribution uniforme. C'est l'objectif de la section suivante. -\section{Quantifier l'écart par rapport à la distribution uniforme} +\section{Quantifier l'écart par rapport à la distribution uniforme}\label{sec:mixing} On considère ici une fonction construite comme à la section précédente. On s'intéresse ici à étudier de manière théorique les itérations définies à l'équation~(\ref{eq:asyn}) pour une @@ -651,7 +664,7 @@ $\textit{fair}\leftarrow\emptyset$\; -\section{Et les itérations généralisées?} +\section{Et les itérations généralisées?}\label{sec:prng:gray:general} Le chaptire précédent a présenté un algorithme de PRNG construit à partir d'itérations unaires. On pourrait penser que cet algorithme est peu efficace puisqu'il @@ -924,7 +937,7 @@ $$ -\section{Tests statistiques} +\section{Tests statistiques}\label{sec:prng;gray:tests} La qualité des séquences aléatoires produites par le générateur des itérations unaires ainsi que @@ -1072,4 +1085,16 @@ Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hl \end{table} -% +\section{Conclusion} +Ce chaptitre a montré comment construire un PRNG chaotique, notamment à partir +de codes de Gray équilibrés. Une méthode completement automatique de +construction de ce type de codes a été présentée étendant les méthodes +existantes. +Dans le cas des itérations unaires, +l'algorithme qui en découle a un temps de mélange qui a +une borne sup quadratique de convergence vers la distribution uniforme. +Pratiquement, ce temps de mélange se rapproche de $N\ln N$. +Les expérimentations au travers de la batterie de test de NIST ont montré +que toutes les propriétés statistiques sont obtenues pour + $\mathsf{N} = 4, 5, 6, 7, 8$. + diff --git a/chaosANN.tex b/chaosANN.tex index b814c12..4ea34b9 100644 --- a/chaosANN.tex +++ b/chaosANN.tex @@ -1,5 +1,3 @@ -% \section{Introduction} -% \label{S1} Les réseaux de neurones chaotiques ont été étudiés à de maintes reprises par le passé en raison notamment de leurs applications potentielles: @@ -28,8 +26,6 @@ fonctions chaotiques. - - Ces réseaux de neurones partagent le fait qu'ils sont qualifiés de ``chaotiques'' sous prétexte qu'ils embarquent une fonction de ce type et ce sans aucune preuve rigoureuse. Ce chapitre caractérise la @@ -37,23 +33,13 @@ classe des réseaux de neurones MLP chaotiques. Il s'intéresse ensuite à l'étude de prévisibilité de systèmes dynamiques discrets chaotiques par cette famille de MLP. -\JFC{revoir plan} - -The remainder of this research work is organized as follows. The next -section is devoted to the basics of Devaney's chaos. Section~\ref{S2} -formally describes how to build a neural network that operates -chaotically. Section~\ref{S3} is devoted to the dual case of checking -whether an existing neural network is chaotic or not. Topological -properties of chaotic neural networks are discussed in Sect.~\ref{S4}. -The Section~\ref{section:translation} shows how to translate such -iterations into an Artificial Neural Network (ANN), in order to -evaluate the capability for this latter to learn chaotic behaviors. -This ability is studied in Sect.~\ref{section:experiments}, where -various ANNs try to learn two sets of data: the first one is obtained -by chaotic iterations while the second one results from a non-chaotic -system. Prediction success rates are given and discussed for the two -sets. The paper ends with a conclusion section where our contribution -is summed up and intended future work is exposed. +La section~\ref{S2} définit la construction d'un réseau de neurones +chaotique selon Devanay. La section~\ref{S3} présente l'approche duale +de vérification si un réseau de neurones est chaotique ou non. +La section~\ref{sec:ann:approx} s'intéresse à étudier pratiquement +si un réseau de +neurones peut approximer des itération unaires chaotiques. Ces itérations +étant obtenues à partir de fonction générées à l'aide du chapitre précédent. \section{Un réseau de neurones chaotique au sens de Devaney} @@ -159,7 +145,7 @@ $\textsc{giu}(f)$ est fortement connexe. \section{Un réseau de neurones peut-il approximer -des itération unaires chaotiques?} +des itération unaires chaotiques?}\label{sec:ann:approx} Cette section s'intéresse à étudier le comportement d'un réseau de neurones face à des itérations unaires chaotiques, comme définies à @@ -424,6 +410,11 @@ Nous avons présenté ensuite comment vérifier si un réseau de neurones Nous avons enfin montré en pratique qu'il est difficile pour un réseau de neurones d'apprendre le comportement global d'itérations chaotiques. +Comme il est difficile (voir impossible) d'apprendre le comportement +de telles fonction, il paraît naturelle de savoir si celles ci peuvent être +utilisées pour générer des nombres pseudo aléatoires. + + % \appendix{} % \begin{Def} \label{def2} diff --git a/demandeInscription/avis_jef_hdr.pdf b/demandeInscription/avis_jef_hdr.pdf index d706ae7..81569ce 100644 Binary files a/demandeInscription/avis_jef_hdr.pdf and b/demandeInscription/avis_jef_hdr.pdf differ diff --git a/main.tex b/main.tex index 217f8f4..c6f86cd 100644 --- a/main.tex +++ b/main.tex @@ -175,19 +175,28 @@ Blabla blabla. \part{Réseaux Discrets} \chapter{Iterations discrètes de réseaux booléens} -\JFC{chapeau à refaire} -\section{Formalisation} + +Ce chapitre formalise tout d'abord ce qu'est +un réseau booléen (section~\ref{sec:sdd:formalisation}. On y revoit +les différents modes opératoires, leur représentation à l'aide de +graphes et les résultats connus de convergence). +Ce chapitre montre ensuite à la section~\ref{sec:sdd:mixage} +comment combiner ces modes pour converger aussi +souvent sans, mais plus rapidement. Cette dernière section +a fait l'objet du rapport~\cite{BCVC10:ir}. + +\section{Formalisation}\label{sec:sdd:formalisation} \input{sdd} -\section{Combinaisons synchrones et asynchrones} +\section{Combinaisons synchrones et asynchrones}\label{sec:sdd:mixage} \input{mixage} \section{Conclusion} -\JFC{Conclusion à refaire} Introduire de l'asynchronisme peut permettre de réduire le temps d'exécution global, mais peut aussi introduire de la divergence. -Dans ce chapitre, nous avons exposé comment construire un mode combinant les +Dans ce chapitre, après avoir introduit les bases sur les réseaux bouléens, +nous avons exposé comment construire un mode combinant les avantage du synchronisme en terme de convergence avec les avantages de l'asynchronisme en terme de vitesse de convergence. @@ -209,12 +218,18 @@ au chaos} discrets chaotiques]{Caracterisation des systèmes discrets chaotiques pour les schémas unaires et généralisés}\label{chap:carachaos} -La première section rappelle ce que sont les systèmes dynamiques chaotiques. -Dire que cette caractérisation dépend du type de stratégie : unaire (TIPE), -généralisée (TSI). Pour chacune d'elle, -on introduit une distance différente. - -On montre qu'on a des résultats similaires. +La suite de ce document se focalise sur des systèmes dynamiques discrets qui ne +convergent pas. Parmi ceux-ci se trouvent ceux qui sont \og chaotiques\fg{}. +La première section de ce chapitre rappelle ce que sont les systèmes +dynamiques chaotiques et leur caractéristiques. Celles-ci dépendent +tout d'abord de la stratégie itérée. La section~\ref{sec:TIPE12} +se focalise sur le schéma unaire tandis que la section~\ref{sec:chaos:TSI} +considère le mode généralisé. Pour chacun de ces modes, +une distance est définie. Finalement, la section~\ref{sec:11FCT} +exhibe des conditions suffisantes premettant d'engendrer +des fonctions chaotiques seon le mode unaire. +Les sections~\ref{sec:TIPE12} et~\ref{sec:11FCT} ont été publiées +dans~\cite{bcgr11:ip}. \section{Systèmes dynamiques chaotiques selon Devaney} \label{subsec:Devaney} @@ -223,13 +238,23 @@ On montre qu'on a des résultats similaires. \section{Schéma unaire}\label{sec:TIPE12} \input{12TIPE} -\section{Schéma généralisé} +\section{Schéma généralisé}\label{sec:chaos:TSI} \input{15TSI} \section{Générer des fonctions chaotiques}\label{sec:11FCT} \input{11FCT} +\section{Conclusion} +Ce chapitre a montré que les itérations unaires sont chaotiques si +et seulement si le graphe $\textsc{giu}(f)$ est fortement connexe et +que les itérations généralisées sont chaotiques si +et seulement si le graphe $\textsc{gig}(f)$ est aussi fortement connexe. +On dispose ainsi à priori d'une collection infinie de fonctions chaotiques. +Le chapitre suivant s'intéresse à essayer de prédire le comportement +de telles fonctions. + + \chapter{Prédiction des systèmes chaotiques} \input{chaosANN} diff --git a/modelchecking.tex b/modelchecking.tex index 1919416..2a7107f 100644 --- a/modelchecking.tex +++ b/modelchecking.tex @@ -1,6 +1,4 @@ - - L'étude de convergence de systèmes dynamiques discrets est simple à vérifier pratiquement pour le mode synchrone. Lorsqu'on introduit des stratégies pseudo périodiques pour les modes unaires et généralisées, le problème @@ -43,7 +41,7 @@ Les théorèmes de correction et de complétude de la démarche sont ensuite donnés à la (\Sec{sec:spin:proof}). Des données pratiques comme la complexité et des synthèses d'expérimentation sont ensuite fournies (\Sec{sec:spin:practical}). - +Ce chapitre a fait l'objet du rapport~\cite{Cou10:ir}. @@ -782,7 +780,7 @@ pour établir un verdict. $\bot$ & 374 & 7.7s& $\bot$ & 370 & 0.51s \\ \hline %\cline{2-13} - AC2D + \cite{RC07} &$\bot$ & 2.5 & 0.001s % RC07_async_mixed.spin &$\bot$ & 2.5 & 0.01s % RC07_async_mixed_all.spin &$\bot$ & 2.5 & 0.01s % RC07_async.spin @@ -816,7 +814,7 @@ du graphe complet. L'exemple \textit{RE} a été prouvé comme universellement convergent. -\JFC{statuer sur AC2D} +%\JFC{statuer sur AC2D} Comme la convergence n'est déjà pas établie pour les itérations synchrones de~\cite{RC07}, il en est donc de même pour les itérations asynchrones. @@ -826,16 +824,13 @@ $\{1,2\};\{1,2\};\{1\};\{1,2\};\{1,2\}$ et débute avec $x=(0,0)$. En raison de la dépendance forte entre les éléments de~\cite{BM99}, $\delta_0$ est réduit à 1. Cela aboutit cependant à $2^{100}$ -configurations dans le mode des itérations asynchrones. - -\JFC{Quid de ceci?} -La convergence des itérations asynchrones de l'exemple~\cite{BCVC10:ir} n'est pas établie -lorsque pour $\delta_0$ vaut 1. Il ne peut donc y avoir convergence universelle. +configurations dans le mode des itérations asynchrones, montrant les limites de +l'approche. \begin{figure} \centering \includegraphics[scale=0.6]{images/RC07ce.eps} -\caption{Contre exemple de convergence pour~\ref{fig:RC07CE}} \label{fig:RC07CE} +\caption{Contre exemple de convergence pour~~\cite{RC07}} \label{fig:RC07CE} \end{figure} @@ -868,7 +863,17 @@ lorsque pour $\delta_0$ vaut 1. Il ne peut donc y avoir convergence universelle. \section{Conclusion} \label{sec:spin:concl} - +L'idée principale de ce chapitre est que l'on peut, +pour des réseaux bouléens à délais bornés de petite taille, obtenir +une preuve de la convergence ou de sa divergence et ce +de manière automatique. +L'idée principale est de traduire le réseau en PROMELA et de laisser +le model checker établir la preuve. +Toute l'approche a été prouvée: le verdict rendu par a donc valeur de vérité. +L'approche a cependant ses limites et ne peut donc pas être +apliquée qu'à des modèles simplifiés de programmes. +La suite de ce travail consiste à se focaliser sur les systèmes qui ne +convergent pas. diff --git a/sdd.tex b/sdd.tex index 355e33c..69e09b6 100644 --- a/sdd.tex +++ b/sdd.tex @@ -1,17 +1,7 @@ -\JFC{Chapeau chapitre à faire} -% Cette section énonce quelques notions suffisantes -% à la compréhension de ce document. -% Elle commence par formaliser ce que sont les systèmes dynamiques booléens -% (section \ref{sub:sdd}) -% et montre comment en extraire leur graphe d'itérations (section~\ref{sub:grIter}) -% et d'interactions (section~\ref{sub:sdd:inter}). -% Elle se termine en définissant une distance sur l'espace -% $\llbracket 1;n\rrbracket^{\Nats}\times \Bool^n$ (section~\ref{sub:metric}). - diff --git a/stegoyousra.tex b/stegoyousra.tex index efd326d..cfda20f 100644 --- a/stegoyousra.tex +++ b/stegoyousra.tex @@ -1,6 +1,6 @@ La plupart des schémas de stéganographie sont conçus de sorte à minimiser une -fonction de distortion. Dans les exemples du chapitre précédent, -ces fonctions de distortion sont construites dans l'obejctif de préserver +fonction de distorsion. Dans les exemples du chapitre précédent, +ces fonctions de distorsion sont construites dans l'objectif de préserver les caractéristiques de l'images. On comprend aisément que dans des régions uniformes ou sur des bords clairement définis, une modification même mineure de l'image est facilement détectable. @@ -10,7 +10,7 @@ dont ces zones ont été modifiées sont ainsi similaires à celles des images initiales. Ces régions sont caractérisées par des courbes de niveau très perturbées. -Ce chapitre présente une nouvelle fonction de distortion pour la stéganographie +Ce chapitre présente une nouvelle fonction de distorsion pour la stéganographie qui est basée sur les dérivées du second ordre, l'outil mathématique usuel pour les courbes de niveau. @@ -27,11 +27,11 @@ de pixels. Ordonner alors les pixels selon la matrice hessienne contient de nombreuses valeurs pour un seul pixel donné. On verra dans ce chapitre comment des approximations des dérivées -premières et secondes pour des images numriques (Section~\ref{sec:gradient}) on peu être +premières et secondes pour des images numériques (Section~\ref{sec:gradient}) on peu être obtenues. Deux propositions de dérivées secondes sont ensuite données et prouvées (Section~\ref{sec:second} et Section~\ref{sec:poly}). -Une adaptation d'une fonction de distortion existante est étudiée +Une adaptation d'une fonction de distorsion existante est étudiée en Section~\ref{sec:distortion} et des expériences sont présentées en Section~\ref{sec:experiments}. @@ -48,10 +48,10 @@ de noyaux de la théorie du signal. On considère qu'une image peut être assimilée à une fonction de $\R^+\times \R^+$ dans $\R^+$ telle que la valeur $P(x,y)$ est associée à chaque pixel de coordonnées $(x,y)$. Les variations d'une telle fonction en $(x_0,y_0)$ peuvent être évaluées -grace au gradient +grâce au gradient $\nabla{P}(x_0,y_0) = \left(\frac{\partial P}{\partial x}(x_0,y_0),\frac{\partial P}{\partial y}(x_0,y_0)\right). $ -Le vecteur gradient pointe dans la direction où la fonction a le plus fort acroissement. +Le vecteur gradient pointe dans la direction où la fonction a le plus fort accroissement. Des pixels ayant des valeurs voisines sont sur des lignes de niveaux qui sont orthogonales à ce vecteur. @@ -67,7 +67,7 @@ H = \begin{bmatrix} \] En un pixel $(x_0,y_0)$, plus les valeurs de cette matrice sont éloignées de zéro, -plus le gradient varie en ce point. Evaluer ce type de matrice est ainsi primordial +plus le gradient varie en ce point. Évaluer ce type de matrice est ainsi primordial en stéganographie. Cependant cette tâche n'est pas aussi triviale qu'elle n'y paraît puisque les images naturelles ne sont pas définies à l'aide de fonction différentiables de $\R^+\times \R^+$ @@ -75,7 +75,7 @@ dans $\R^+$. La suite montre comment obtenir des approximations de telles matric \subsection{Approches classiques pour évaluer le gradient dans des images}\label{sub:class:1} Dans ce contexte, les approches les plus utilisées pour évaluer un gradient -sont ``Sobel'', ``Prewitt'', ``Différence centrale'' et `` Difference intermediaire''. +sont ``Sobel'', ``Prewitt'', ``Différence centrale'' et `` Différence intermédiaire''. Chacune de ces approches applique un produit de convolution $*$ entre un noyau $K$ (rappelé dans le tableau~\ref{table:kernels:usual}) et une fenêtre $A$ de taille $3\times 3$. Le résultat @@ -97,7 +97,6 @@ sont le résultat du calcul du gradient sur la matrice $\dfrac{\partial P}{\part \caption{Noyaux usuels pour évaluer des gradients d'images\label{table:kernels:usual} } \centering -\scriptsize \begin{tabular}{|c|c|c|} \hline Nom& Sobel & Prewitt \\ @@ -105,8 +104,8 @@ sont le résultat du calcul du gradient sur la matrice $\dfrac{\partial P}{\part Noyau & $\textit{Ks}= \begin{bmatrix} -1 & 0 & +1 \\ -2 & 0 & +2 \\ -1 & 0 & +1 \end{bmatrix} $ & $\textit{Kp}= \begin{bmatrix} -1 & 0 & +1 \\ -1 & 0 & +1 \\ -1 & 0 & +1 \end{bmatrix} $\\ \hline\hline - Nom & Difference & Différence \\ - & centrale & Intermediaire \\ + Nom & Différence & Différence \\ + & centrale & Intermédiaire \\ \hline Noyau & $\textit{Kc}= \begin{bmatrix} 0&0&0 \\ -\dfrac{1}{2} & 0 & +\dfrac{1}{2} \\ 0&0&0 \end{bmatrix} $ & $\textit{Ki}= \begin{bmatrix} 0&0&0 \\ 0 & -1 & 1 \\ 0&0&0 \end{bmatrix} $ \\ @@ -122,29 +121,21 @@ de gradient d'images}\label{sub:class:2} Il est connu que $\dfrac{\partial^2 P}{\partial x \partial y} $ est égal à $\dfrac{\partial^2 P}{\partial y \partial x}$ si -les méthode qui calculent le grandient et le gradient du gradient (la matrice hessienne) +les méthode qui calculent le gradient et le gradient du gradient (la matrice hessienne) sont les mêmes. - -For instance, in the Sobel approach, -it is easy to verify that the calculus of -$\dfrac{\partial^2 P}{\partial x \partial y}$ -and of -$\dfrac{\partial^2 P}{\partial y \partial x}$ -are both the result -of a convolution product with the Kernel -$\textit{Ks}''_{xy}$ given in Table~\ref{table:hessian:usual}. -This one summarizes kernels -$K_{x^2}''$ and +Le tableau~\ref{table:hessian:usual} résume les les noyaux +$K_{x^2}''$ et $K_{xy}''$ -that allow to respectively compute -$\dfrac{\partial^2 P}{\partial x^2}$ and -$\dfrac{\partial^2 P}{\partial x \partial y}$ with a convolution product -for each of the usual image gradient operator. +qui permettent de calculer respectivement +$\dfrac{\partial^2 P}{\partial x^2}$ et +$\dfrac{\partial^2 P}{\partial x \partial y}$ comme un produit de convolution +pour chacun des opérateurs de gradient rappelés à la section précédente. + \begin{table}[ht] -\caption{Kernels of second order gradient operators\label{table:hessian:usual} +\caption{Noyaux usuels pour évaluer des gradients de second ordre d'images +\label{table:hessian:usual} }\centering -\tiny \begin{tabular}{|c|c|} \hline Sobel & Prewitt \\ @@ -195,8 +186,8 @@ for each of the usual image gradient operator. $ \\ \hline\hline - Central & Intermediate \\ - Difference &Difference \\ + Différence & Différence \\ + centrale &intermédiaire \\ \hline $ \textit{Kc}_{x^2}''= @@ -243,45 +234,34 @@ for each of the usual image gradient operator. \end{table} -The Sobel kernel $\textit{Ks}_{x^2}''$ allows to detect whether the central -pixel belongs to a ``vertical'' edge, even if this one is noisy, by considering its -vertical neighbours. The introduction of these vertical neighbours in this kernel is meaningful -in the context of finding edges, but not very accurate when the objective is to -precisely find the level curves of the image. -Moreover, all the pixels that are in the second and the fourth column in this kernel -are ignored. -The Prewitt Kernel has similar drawbacks in this context. - - -The Central Difference kernel $\textit{Kc}_{x^2}''$ is not influenced by -the vertical neighbours of the central pixel and is thus more accurate here. -However, the kernel $\textit{Kc}_{xy}''$ again looses the values of the pixels that -are vertically and diagonally aligned with the central one. - -Finally, the Intermediate Difference kernel $\textit{Ki}_{x^2}''$ shifts -to the left the value of horizontal variations of $\dfrac{\partial P}{\partial x}$: -the central pixel $(0,0)$ exactly receives the value +Le noyau $\textit{Ks}_{x^2}''$ permet de détecter si le le pixel central +pixel central appartient à une bord ``vertical'', même si celui contient du bruit, +en considérant ces voisins verticaux. Ces derniers sont vraiment +pertinents dans un objectif de détecter les bords. Cependant, leur lien avec +les lignes de niveau n'est pas direct. De plus tous les pixels qui sont dans la +deuxième et la quatrième colonne de ce noyau sont ignorés. +Le noyau de Prewitt a des propriétés similaires. +Le noyau de différence centrale $\textit{Kc}_{x^2}''$ n'est pas influencé par les +voisins verticaux du pixel central et peu paraître plus adapté ici. +Cependant, le noyau $\textit{Kc}_{xy}''$ perd aussi les valeurs des pixels +qui sont alignés verticalement et diagonalement avec le pixel central. +Enfin, le noyau de différence intermédiaire $\textit{Ki}_{x^2}''$ décale +à gauche la valeur des variations horizontales de $\dfrac{\partial P}{\partial x}$: +Le pixel central $(0,0)$ reçoit exactement la valeur $\dfrac{P(0,2)-P(0,1)}{1} - \dfrac{P(0,1)-P(0,0)}{1}$, -which is an approximation of -$\dfrac{\partial P}{\partial x}(0,1)$ and not of +qui est une approximation de +$\dfrac{\partial P}{\partial x}(0,1)$ et non de $\dfrac{\partial P}{\partial x}(0,0)$. -Furthermore the Intermediate Difference kernel $\textit{Ki}_{xy}''$ only deals -with pixels in the upper right corner, loosing all the other information. - -Due to these drawbacks, we are then left to produce another approach to find the level curves with strong accuracy. - -\section{Second Order Kernels for Accurate Level Curves}\label{sec:second} - -This step aims at finding -accurate level curve variations in an image. -We do not restrict the kernel to have a fixed size (\textit{e.g.}, $3\times3$ or $5 \times 5$ as in the -aforementioned schemes). -This step is thus defined with kernels of size -$(2n+1)\times (2n+1)$, $n \in \{1,2,\dots,N\}$, where -$N$ is a parameter of the approach. - -The horizontal gradient variations are thus captured thanks to $(2n+1)\times (2n+1)$ square kernels -\begin{small} +De plus, le noyau de différence intermédiaire $\textit{Ki}_{xy}''$ ne concerne +que les pixels du coin supérieur droit, en perdant toutes les autres informations. +La section suivante propose une autre approche pour calculer les lignes de niveau avec une précision accrue. + +\section{Des noyaux pour des lignes de niveau}\label{sec:second} +On ne restreint pas aux noyaux de taille fixe (comme $3\times3$ or $5 \times 5$ +dans les schémas précédents). Au contraire, on considère des noyaux de taille variable +$(2n+1)\times (2n+1)$, $n \in \{1,2,\dots,N\}$, où +$N$ est un paramètre de l'approche. +Les variations horizontales du gradient sont extraites grâce au noyau de taille $(2n+1)\times (2n+1)$: \[ \arraycolsep=1.4pt \def\arraystretch{1.4} @@ -299,24 +279,22 @@ The horizontal gradient variations are thus captured thanks to $(2n+1)\times (2n \end{array} \right) \] -\end{small} -When the convolution product is applied on a $(2n+1)\times(2n+1)$ window, -the result is -$\dfrac{1}{2}\left(\dfrac{P(0,n)-P(0,0)}{n} - \dfrac{P(0,0)-P(0,-n)}{n}\right)$, which is indeed -the variation between the gradient around the central pixel. -This proves that this calculus is a correct approximation of +Lorsque le produit de convolution est appliqué sur une fenêtre $(2n+1)\times(2n+1)$, +le résultat est +$\dfrac{1}{2}\left(\dfrac{P(0,n)-P(0,0)}{n} - \dfrac{P(0,0)-P(0,-n)}{n}\right)$, +qui représente en effet les variation horizontales de la partie horizontale +du gradient autour du pixel central. On obtient donc bien une approximation de $\dfrac{\partial^2 P}{\partial x^2}$. +Lorsque $n$ vaut 1, ce noyau est une version centrée du noyau horizontal de différence +intermédiaires. $\textit{Ki}_{x^2}''$ à un facteur $1/2$ près). +Lorsque $n$ vaut 2, on retrouve $\textit{Kc}_{x^2}''$. -When $n$ is 1, this kernel is a centered version of the horizontal Intermediate Difference kernel $\textit{Ki}_{x^2}''$ modulo a multiplication by $1/2$. When $n$ is 2, this kernel is equal to $\textit{Kc}_{x^2}''$. +Les variations verticales du gradient sont aussi obtenus en faisant subir +à $\textit{Ky}_{x^2}''$ une rotation d'angle $\pi/2$. +Les variations diagonales sont obtenues à l'aide du gradient +$\textit{Ky}_{xy}''$ défini par: -The vertical gradient variations are again obtained by applying -a $\pi/2$ rotation to each horizontal kernel $\textit{Ky}_{x^2}''$. - -The diagonal gradient variations are obtained thanks to the $(2n+1)\times (2n+1)$ square kernels -$\textit{Ky}_{xy}''$ defined by - -\begin{small} \[ \arraycolsep=1.4pt \def\arraystretch{1.4} @@ -358,79 +336,24 @@ $\textit{Ky}_{xy}''$ defined by \end{array} \right). \] -\end{small} -When $n$ is 1, $\textit{Ky}_{xy}''$ is equal to the kernel -$\textit{Kc}_{xy}''$, and %. -% -%When $n$ is 1, -the average vertical variations of the horizontal variations are -\[ -\begin{array}{l} -\dfrac{1}{4} -\left[ -\left((P(0,1)-P(0,0))-(P(1,1)-P(1,0))\right)+ \right.\\ -\quad \left((P(-1,1)-P(-1,0))-(P(0,1)-P(0,0))\right)+\\ -\quad \left((P(0,0)-P(0,-1))-(P(1,0)-P(1,-1))\right)+\\ -\quad \left. \left((P(-1,0)-P(-1,-1))-(P(0,0)-P(0,-1))\right) -\right] \\ -=\dfrac{1}{4} -\left[ P(1,-1) -P(1,1) - P(-1,-1) + P(-1,1)\right]. -\end{array} -\] -which is $\textit{Ky}_{xy}''$. - -Let us now consider any number $n$, $1 \le n \le N$. -Let us first investigate the vertical variations related to -the horizontal vector $\vec{P_{0,0}P_{0,1}}$ -(respectively $\vec{P_{0,-1}P_{0,0}}$) -of length 1 that starts from (resp. that points to) $(0,0)$. -As with the case $n=1$, there are 2 new vectors of -length 1, namely -$\vec{P_{n,0}P_{n,1}}$ and $\vec{P_{-n,0}P_{-n,1}}$ -(resp. -$\vec{P_{n,-1}P_{n,0}}$, and $\vec{P_{-n,-1}P_{-n,0}}$) -that are vertically aligned with $\vec{P_{0,0}P_{0,1}}$ -(resp. with $\vec{P_{0,-1}P_{0,0}}$). - -The vertical variation is now equal to $n$. Following the case where $n$ is 1 to compute the average variation, -the coefficients of the first and last line around the central -vertical line are thus from left to right: -$\dfrac{1}{4n}$, -$\dfrac{-1}{4n}$, -$\dfrac{-1}{4n}$, and -$\dfrac{1}{4n}$. - -Cases are similar with vectors $\vec{P_{0,0}P_{0,1}}$, \ldots -$\vec{P_{0,0}P_{0,n}}$ which respectively lead to coefficients -$-\dfrac{1}{4 \times 2n}$, \ldots, -$-\dfrac{1}{4 \times n.n}$, and the proof is omitted. -Finally, let us consider the vector $\vec{P_{0,0}P_{0,1}}$ -and its vertical variations when $\delta y$ is $n-1$. -As in the case where $n=1$, we thus obtain the coefficients -$\dfrac{1}{4 \times (n-1)n}$ and -$-\dfrac{1}{4 \times (n-1)n}$ - (resp. $-\dfrac{1}{4 \times (n-1)n}$ and -$\dfrac{1}{4 \times (n-1)n}$) -in the second line (resp. in the -penultimate line) since the vector has length $n$ -and $\delta y$ is $n-1$. -Coefficient in the other lines are similarly obtained and the proof is thus omitted. - -We are then left to compute an approximation of the partial second order derivatives -$\dfrac{\partial^2 P}{\partial x^2}$, $\dfrac{\partial^2 P}{\partial y^2}$, and $\dfrac{\partial^2 P}{\partial x \partial y}$ -with the kernels, -$\textit{Ky}_{x^2}''$, $\textit{Ky}_{y^2}''$, and $\textit{Ky}_{xy}''$ respectively. -However, the size of each of these kernels is varying from $3\times3$ to $(2N+1)\times (2N+1)$. -Let us explain the approach on the former partial derivative. -The other can be immediately deduced. - -Since the objective is to detect large variations, the second order derivative is approximated as -the maximum of the approximations. More formally, -let $n$, $1 \le n \le N$, be an integer number and -$\dfrac{\partial^2 P}{\partial x^2}_n$ be the result of applying the Kernel -$\textit{Ky}_{x^2}''$ of size $(2n+1)\times (2n+1)$. The derivative -$\dfrac{\partial^2 P}{\partial x^2}$ is defined by + + +En effet, lorsque $n$ vaut 1, $\textit{Ky}_{xy}''$ se retrouve en calculant la moyenne +des variations horizontales de la composante verticale du gradient calculé à l'aide de +$\textit{Ky}_{y}'$. Pour cette valeur de $n$, on a +$\textit{Ky}_{xy}'' = \textit{Kc}_{xy}''$. +Pour chaque nombre $n$, $1 < n \le N$, $\textit{Ky}_{xy}''$ se retrouve de la même +manière, c'est-à-dire en effectuant des moyennes de variations. +Une preuve de la construction se trouve dans l'article~\cite{ccfg16:ip}. + + + +L'objectif est de détecter les grandes variations des dérivées premières. +Ainsi les dérivées secondes seront approximées comme les maximums des +matrices hessiennes obtenues lorsque $n$ varie entre $1$ et $ N$. + +La dérivée partielle $\dfrac{\partial^2 P}{\partial x^2}$ est définie par \begin{equation} \dfrac{\partial^2 P}{\partial x^2} @@ -439,28 +362,30 @@ $\dfrac{\partial^2 P}{\partial x^2}$ is defined by \right \}. \label{eq:d2p_dx2} \end{equation} - -The same iterative approach is applied to compute approximations of +où $\dfrac{\partial^2 P}{\partial x^2}_n$ est le résultat de l'application +du noyau $\textit{Ky}_{x^2}''$ de taille $(2n+1)\times (2n+1)$. +La même approche itérative est appliquée pour construire les +approximations de $\dfrac{\partial^2 P}{\partial y \partial x}$ -and of +et de $\dfrac{\partial^2 P}{\partial y^2}$. -Next section studies the suitability of approximating second order derivatives -when considering an image as a polynomial. +La section suivante étudie la pertinence d'interpoler une image par un polynome +lorsqu'on cherche a obtenir ces dérivées secondes. -\section{Polynomial Interpolation of Images for Hessian Matrix Computation}\label{sec:poly} -Let $P(x,y)$ be the discrete value of the pixel $(x,y)$ in the image. -Let $n$, $1 \le n \le N$, be an integer such that the objective is to find a polynomial interpolation -on the $(2n+1)\times(2n+1)$ window where the central pixel has index $(0,0)$. -There exists an unique polynomial $L : \R\times \R \to \R$ of degree $(2n+1)\times(2n+1)$ defined -such that $L(x,y)=P(x,y)$ for each pixel $(x,y)$ in this window. -Such a polynomial is defined by + +\section{Interpolation polynomiale pour le calcul de la matrice hessienne}\label{sec:poly} +Soit $P(x,y)$ la valeur du pixel $(x,y)$ et soit $n$, $1 \le n \le N$, +tel que l'objectif est de trouver un polynome d'interpolation dans la fenêtre de taille +$(2n+1)\times(2n+1)$ dont le pixel central a pour indice $(0,0)$. +Il existe un unique polynôme $L : \R\times \R \to \R$ +de degré $(2n+1)\times(2n+1)$ tel que $L(x,y)=P(x,y)$ pour chaque pixel +$(x,y)$ de cette fenêtre et ce polynome est défini par \begin{equation} \begin{array}{l} L(x,y) = \sum_{i=-n}^{n} -\sum_{j=-n}^{n} \\ -\quad P(i,j) +\sum_{j=-n}^{n}P(i,j) \left( \prod_{\stackrel{-n\leq j'\leq n}{j'\neq j}} \frac{x-j'}{i-j'} @@ -471,9 +396,7 @@ L(x,y) = \right) \end{array} \end{equation} - -It is not hard to prove that the first order horizontal derivative of the polynomial $L(x,y)$ -is +On peut facilement prouver que les dérivées partielles de $L$ selon $x$ est \begin{equation} \begin{array}{l} \dfrac{\partial L}{\partial x} = @@ -483,8 +406,7 @@ P(i,j) \left( \prod_{\stackrel{-n\leq j'\leq n}{j'\neq j}} \frac{y-j'}{j-j'} -\right)\\ -\quad +\right) \left( \sum_{\stackrel{-n\leq i'\leq n}{i'\neq i}} \frac{1}{i-i'} @@ -493,20 +415,17 @@ P(i,j) \right) \end{array} \end{equation} -\noindent and thus to deduce that the -second order ones are - -\begin{equation} -\begin{array}{l} -\dfrac{\partial^2 L}{\partial x^2} = +\noindent et ainsi en déduire que les dérivées partielles de second ordre +sont +\begin{eqnarray} +\dfrac{\partial^2 L}{\partial x^2} &=& \sum_{i=-n}^{n} \sum_{j=-n}^{n} P(i,j) \left( \prod_{\stackrel{-n\leq j'\leq n}{j'\neq j}} \frac{y-j'}{j-j'} -\right)\\ -\quad +\right) \left( \sum_{\stackrel{-n\leq i'\leq n}{i'\neq i}} \frac{1}{i-i'} @@ -515,74 +434,33 @@ P(i,j) \prod_{\stackrel{-n\leq i'''\leq n}{i'''\neq i,i',i''}} \frac{x-i'''}{i-i'''} \right) -\end{array} -\label{eq:deriv:poly:x2} -\end{equation} - -\begin{equation} -\begin{array}{l} -\dfrac{\partial^2 L}{\partial y \partial x} = +\label{eq:deriv:poly:x2} \\ +\dfrac{\partial^2 L}{\partial y \partial x} &= & \sum_{i=-n}^{n} -P(i,j) \\ -\quad +P(i,j) \left( \sum_{\stackrel{-n\leq j'\leq n}{j'\neq j}} \frac{1}{j-j'} \prod_{\stackrel{-n\leq j''\leq n}{j''\neq j, j'}} \frac{y-j''}{j-j''} -\right)\\ -\quad +\right) \left( \sum_{\stackrel{-n\leq i'\leq n}{i'\neq i}} \frac{1}{i-i'} \prod_{\stackrel{-n\leq i''\leq n}{i''\neq i, i'}} \frac{x-i''}{i-i''} \right) -\end{array} \label{eq:deriv:poly:yx} -\end{equation} - -These second order derivatives are computed for each moving -window and are associated to the central pixel, \textit{i.e.}, to the pixel $(0,0)$ inside this one. - -Let us first simplify $\dfrac{\partial^2 L}{\partial x^2}$ when $(x,y)=(0,0)$ -defined in Equation~(\ref{eq:deriv:poly:x2}). If $j$ is not null, the index $j'$ -is going to be null and the product -$\left( -\prod_{\stackrel{-n\leq j'\leq n}{j'\neq j}} -\frac{-j'}{j-j'} -\right)$ is null too. -In this equation, we thus only consider $j=0$. -It is obvious that the product indexed with $j'$ is thus equal to 1. -This equation can thus be simplified in: - -\begin{equation} -\begin{array}{l} -\dfrac{\partial^2 L}{\partial x^2} = -\sum_{i=-n}^{n} -P(i,0)\\ -\quad -\left( -\sum_{\stackrel{-n\leq i'\leq n}{i'\neq i}} -\frac{1}{i-i'} -\sum_{\stackrel{-n\leq i''\leq n}{i''\neq i,i'}} -\frac{1}{i-i''} -\prod_{\stackrel{-n\leq i'''\leq n}{i'''\neq i,i',i''}} -\frac{i'''}{i'''-i} -\right) -\end{array} -\label{eq:deriv:poly:x2:simpl} -\end{equation} - - -and then in: +\end{eqnarray} +Ces dérivées secondes sont calculées pour chaque pixel central, \textit{i.e.} le pixel dont l'indice est $(0,0)$ dans la fenêtre. +En considérant cette particularisation, l'équation~(\ref{eq:deriv:poly:x2}) peut +se simplifie en \begin{equation} \begin{array}{l} \dfrac{\partial^2 L}{\partial x^2} = \sum_{i=-n}^{n} -P(i,0)\\ -\quad +P(i,0) \left( \sum_{\stackrel{-n\leq i' < i'' \le n}{i',i''\neq i}} \frac{2}{(i-i')(i-i'')} @@ -593,19 +471,9 @@ P(i,0)\\ \label{eq:deriv:poly:x2:simpl:2} \end{equation} -From this equation, the kernel allowing to evaluate horizontal -second order derivatives -can be computed for any $n$. -It is further denoted as $Ko''_{x^2}$. -Instances of such matrix when $n=2$, $3$, and $4$ -are given in Table~\ref{table:sod:hori:poly}. - \begin{table}[ht] - \caption{Kernels $Ko''_{x^2}$ - for second order horizontal derivatives induced - by polynomial interpolation} + \caption{Noyaux $Ko''_{x^2}$ pour calculer des dérivées de second ordre à partir d'interpolation polynomiale} \centering - \scriptsize \def\arraystretch{1.4} \begin{tabular}{|c|c|} \hline @@ -626,11 +494,10 @@ are given in Table~\ref{table:sod:hori:poly}. \begin{table}[ht] -\caption{Kernels for second order diagonal derivatives induced - by polynomial interpolation \label{table:sod:diag:poly} +\caption{ Noyaux pour les dérivéees secondes en $x$ et $y$ lors de l'interpolation polynomiale\label{table:sod:diag:poly} } \centering -\scriptsize +%\scriptsize \def\arraystretch{1.5} \begin{tabular}{|c|c|} \hline @@ -658,29 +525,26 @@ $\\ \end{tabular} \end{table} +Cette dérivée partielle peut s'écrire comme un produit de convolution avec un noyau +noté $Ko''_{x^2}$. Des instances de tels noyaux, pour $n=2$, $3$ et $4$ +sont données au tableau~\ref{table:sod:hori:poly}. De manière similaire, +le tableau~\ref{table:sod:diag:poly} donne deux exemples pour $n=1$ et $n=2$ +de noyaux $Ko''_{xy}$ permettant de calculer directement les dérivées +de second ordre selon $x$ et $y$ en $(0,0)$. +On remarque que pour $n=1$, le noyau est égal à $Kc''_{xy}$. -From Equation~(\ref{eq:deriv:poly:yx}), kernels allowing to evaluate diagonal -second order derivatives (\textit{i.e.}, -$\dfrac{\partial^2 L}{\partial y \partial x}$) are computed. -They are denoted as $Ko''_{xy}$. -Table~\ref{table:sod:diag:poly} gives two examples of them when $n=1$ and $n=2$. -Notice that for $n=1$, the kernel $Ko''_{xy}$ is equal to $Kc''_{xy}$. -\section{Distortion Cost}\label{sec:distortion} - -The distortion function has to associate to each pixel $(i,j)$ -the cost $\rho_{ij}$ of its modification -by $\pm 1$. - -The objective is to map a small value to a pixel when all its second order derivatives -are high and a large value otherwise. -%\YF{The WOW use the wavelet relative distortion (UNIWARD) as a function to force the embedding operation to the noisy areas and avert the smooth areas.} -In WOW and UNIWARD the distortion function is based on the H\"older norm with +\section{Fonction de distorsion}\label{sec:distortion} +Une fonction de distorsion associe à chaque pixel $(i,j)$ +le coût $\rho_{ij}$ du modification par $\pm 1$. L'objectif est d'associer une +valeur faible aux pixels dont toutes les dérivées secondes sont éloignées de 0 +et une valeur rédhibitoire sinon. +Dans WOW comme dans UNIWARD la fonction de distorsion est définie par \[ \rho_{ij}^w = \left( @@ -689,119 +553,79 @@ In WOW and UNIWARD the distortion function is based on the H\"older norm with \abs{\xi_{ij}^d}^{p} \right)^{-\frac{1}{p}} \] -where $p$ is a negative number and -$\xi_{ij}^h$ (resp. $\xi_{ij}^v$ and $\xi_{ij}^d$) -represents the horizontal (resp. vertical and diagonal) suitability. -A small suitability in one direction means an inaccurate position to embed a message. - -We propose here to adapt such a distortion cost as follows: +où $p$ est un nombre négatif et +$\xi_{ij}^h$ (resp. $\xi_{ij}^v$ et $\xi_{ij}^d$) +représentent la pertinence horizontale (resp. verticale et diagonale) de modification. +Une faible pertinence dans une direction signifie que l'embarquement +dans ce pixel est inapproprié. +La fonction de distorsion que l'on a retenu est une particularisation ($p=-1$) +de cette dernière: \[ \rho_{ij} = \left( -\abs{\dfrac{\partial^2 P}{\partial x^2}(i,j)} + -\abs{\dfrac{\partial^2 P}{\partial y^2}(i,j)} + -\abs{\dfrac{\partial^2 P}{\partial y \partial x}(i,j)} -\right)^{-\frac{1}{p}} +\abs{\dfrac{\partial^2 P}{\partial x^2}(i,j)}^{-1} + +\abs{\dfrac{\partial^2 P}{\partial y^2}(i,j)}^{-1} + +\abs{\dfrac{\partial^2 P}{\partial y \partial x}(i,j)}^{-1} +\right) \] -It is not hard to check that such a function has large -value when at least one of its derivatives is null. Otherwise, -the larger the derivatives are, the smaller the returned value -is. - - - - -%Practically, it is computed as a double convolution product with Daubechies Wavelet Kernels. - -%It is not hard to see that this approach -%does not consider the range of the values. For %instance, if one direction only has large suitability -%absolute values, all the elements $\abs{\xi_{ij}}^{p}$ are so small, and -%suitable pixels cannot be distinguished from inaccurate ones. The distortion function has to -%provide a way to discriminate pixels even when the distribution has small deviation -%Because of each pixel value ranges in $[0,255]$, each first order derivative belongs to -%$[-255,255]$ and thus each second order derivative has a real value in -%$[-255,255]$. -%Due to the definition of the approximation of $\dfrac{\partial^2 P}{\partial x^2}$, -%this one is a positive or null real number lower than 255. -%The higher the second order derivatives are, -%the +\section{Experimentations}\label{sec:experiments} -%To enlarge the discrimination power, -%data are firstly linearly mapped to $[0,1]$. -%The tuple -%$(\dfrac{\partial^2 P}{\partial x^2} , \dfrac{\partial^2 P}{\partial y^2}, \dfrac{\partial^2 %P}{\partial x \partial y})$ belongs to $[0,1]\times[0,1]\times[0,1] = [0,1]^3$. +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 +l'image 38 du challenge BOSS~\cite{Boss10} en suivant les deux schémas basés +sur les dérivées secondes présentés dans ce chapitre. +Le taux d'embarquement $\alpha$ est fixé à 0.4 bits par pixel et les noyaux sont +construits avec $N=4$. On remarque bien que les pixels dans les zones uniformes +et les pixels dans les bords bien définis ne sont pas modifiés par l'approche tandis +qu'au contraire les zones peu prévisibles (le monument par exemple) +concentrent les changements. -%Basically, for each dimension the idea is to select a subset of pixels of size $k$ and next to retain those which have been selected three times, \textit{i.e.}, those with large values -%in any element of -%$(\dfrac{\partial^2 P}{\partial x^2} , \dfrac{\partial^2 P}{\partial y^2}, \dfrac{\partial^2 %P}{\partial x \partial y})$. -%Since the dimension is $3$, the size $k$ can be defined by -%\[ -%k = W \times H \times \alpha ^{\dfrac{1}{3}} -%\] -%where $W$ and $H$ respectively stand for the width and the length of the image (expressed in pixels) -%and $\alpha$ is the payload. For instance if $\alpha$ is 0.1, -%about $0.46\%$ of the image pixels with higher values in $\dfrac{\partial^2 P}{\partial x^2}$ should be selected, and similarly with $\dfrac{\partial^2 P}{\partial y^2}$ and $\dfrac{\partial^2 P}{\partial x \partial y}$. -% Dire comment on les ordonne, les autres et le sens -\begin{figure*} +\begin{figure}[ht] \centering \begin{tabular}{|c|c|c|} \hline - Scheme & Stego. content & Changes with cover \\ + Schéma & Image. Stego. & Différence avec le support \\ \hline - $Ky$ based approach &\includegraphics[scale=0.20]{images/38_dp}& + Approche à base de $Ky$ &\includegraphics[scale=0.20]{images/38_dp}& \includegraphics[scale=0.20]{images/38_dp_diff} \\ \hline - $Ko$ based approach & \includegraphics[scale=0.20]{images/38_poly} & + Approche à base de $Ko$ & \includegraphics[scale=0.20]{images/38_poly} & \includegraphics[scale=0.20]{images/38_poly_diff} \\ \hline \end{tabular} - \caption{Embedding changes instance with payload $\alpha = 0.4$} + \caption{Exemple de changements dus à un embarquement avec $\alpha = 0.4$} \label{fig:oneimage} -\end{figure*} - - -\section{Experiments}\label{sec:experiments} - -First of all, the whole steganographic approach code is available online\footnote{\url{https://github.com/stego-content/SOS}}. - -Figure~\ref{fig:oneimage} presents the results of embedding data in a cover image -from the BOSS contest database~\cite{Boss10} with respect to the two second order derivative schemes presented in this work. -The $Ky$ based approach (resp. the $Ko$ based one) -corresponds to the scheme detailed in Section~\ref{sec:second} -(resp. in Section~\ref{sec:poly}). -The payload $\alpha$ is set to 0.4 and kernels are computed with $N=4$. -The central column outputs the embedding result whereas the right one displays -differences between the cover image and the stego one. -It can be observed that pixels in smooth area (the sky, the external access steps) and pixels in clean edges (the columns, -the step borders) are not modified by the approach. -On the contrary, an unpredictable area (a monument for example) concentrates pixel changes. - - -\subsection{Choice of parameters} - -The two methods proposed in Section~\ref{sec:second} and -in Section~\ref{sec:poly} are based on kernels of size up to -$(2N+1)\times(2N+1)$. This section aims at finding the -value of the $N$ parameter that maximizes the security level. -For each approach, we have built 1,000 stego images with -$N=2$, $4$, $6$, $8$, $10$, $12$, and $14$ where the covers belong -to the BOSS contest database. -This set contains 10,000 grayscale $512\times 512$ images in a RAW format. -The security of the approach has been evaluated thanks to the Ensemble Classifier~\cite{DBLP:journals/tifs/KodovskyFH12} based steganalyser, -which is considered as a state of the art steganalyser tool. -This steganalysis process embeds the rich model (SRM) features~\cite{DBLP:journals/tifs/FridrichK12} -of size 34,671. -For a payload $\alpha$, either equal to $0.1$ or to $0.4$, average testing errors (expressed in percentages) have been studied and are summarized in -Table~\ref{table:choice:parameter}. +\end{figure} + + + + + +\subsection{Choix des paramètres} + +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 +$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 +Ensemble Classifier~\cite{DBLP:journals/tifs/KodovskyFH12}. +Pour un taux d'embarquement $\alpha$ égal soit à $0.1$ ou soit à $0.4$, +l'erreur moyenne de test (exprimée en pourcentage) a été calculée. +Le tableau~\ref{table:choice:parameter} synthétise les résultats. +On observe que la taille $N=4$ (respectivement $N=12$) +permet d'obtenir des erreurs suffisamment élevées pour l'approche basée sur $Ky$ +(resp. pour celle basée sur $Ko$). +Ces deux valeurs de paramètre sont retenues par la suite. \begin{table}[ht] -\caption{Average Testing Errors with respect to the the Kernel Size} -\begin{scriptsize} +\caption{Erreur moyenne de test en fonction de la taille du noyau} \centering \setlength{\tabcolsep}{3pt} \begin{tabular}{|c|c|c|c|c|c|c|c|c|} @@ -810,58 +634,48 @@ Table~\ref{table:choice:parameter}. \cline{3-9} \multicolumn{1}{c|}{}& & $2$ & $4$& $6$& $8$& $10$& $12$ & $14$ \\ \hline{} -Average testing +Erreur moyenne & \textit{0.1} & 39& 40.2& 39.7& 39.8& 40.1& $39.9$& $39.8$ \\ \cline{2-9} -error for Kernel $K_y$ & \textit{0.4}& 15& 18.8& 19.1& 19.0& 18.6& 18.7 & 18.7 \\ +de test pour le noyau $K_y$ & \textit{0.4}& 15& 18.8& 19.1& 19.0& 18.6& 18.7 & 18.7 \\ \hline -Average testing & \textit{0.1} & 35.2 & 36.6& 36.7& 36.6& 37.1& 37.2 & 37.2 \\ +Erreur moyenne & \textit{0.1} & 35.2 & 36.6& 36.7& 36.6& 37.1& 37.2 & 37.2 \\ \cline{2-9} -error for Kernel $K_o$ & \textit{0.4} & 5.2 & 6.8& 7.5 & 7.9 & 8.1 & 8.2 & 7.6 \\ +de test pour le noyau $K_o$ & \textit{0.4} & 5.2 & 6.8& 7.5 & 7.9 & 8.1 & 8.2 & 7.6 \\ \hline \end{tabular} \label{table:choice:parameter} -\end{scriptsize} + \end{table} -Thanks to these experiments, we observe that the size $N=4$ (respectively $N=12$) obtains sufficiently large average testing errors for the $Ky$ based approach -(resp. for the $Ko$ based one). In what follows, these values are retained for these two methods. - -\subsection{Security Evaluation} -As in the previous section, the BOSS contest database has been retained. -To achieve a complete comparison with other steganographic tools, -the whole database of 10,000 images has been used. -Ensemble Classifier with SRM features is again used to evaluate the security of the approach. - -We have chosen 4 different payloads, 0.1, 0.2, 0.3, and 0.4, as in many steganographic evaluations. -Three values are systematically given for each experiment: -the area under the ROC curve (AUC), -the average testing error (ATE), -and the OOB error (OOB). - -All the results are summarized in Table~\ref{table:experiments:summary}. -%and in Figure~\ref{fig1}, Figure~\ref{fig2}, and Figure~\ref{fig3}. -Let us analyse these experimental results. -The security approach is often lower than those observed with state of the art tools: -for instance with payload $\alpha=0.1$, the most secure approach is WOW -with an average testing error equal to 0.43 whereas our approach reaches 0.38. -However these results are promising and for two reasons. -First, our approaches give more resistance towards Ensemble Classifier (contrary to HUGO) -for large payloads. -Secondly, without any optimisation, our approach is not so far from state of the art steganographic tools. -Finally, we explain the lack of security of the $Ko$ based approach with large payloads as follows: -second order derivatives are indeed directly extracted from polynomial interpolation. -This easy construction however induces large variations between the polynomial $L$ and -the pixel function $P$. + +\subsection{Évaluation de la sécurité} +Comme dans ce qui précède, la base du challenge BOSS a été retenue. +Ici c'est cependant l'ensemble des 10000 images qui a été utilisé pour évaluer +la sécurité. +C'est aussi les caractéristiques SRM et Ensemble Classifier qui ont été utilisées +pour évaluer la sécurité de l'approche.. +Quatre taux d'embarquement 0.1, 0.2, 0.3 et 0.4 +ont été retenus. Pour chaque expérience, +l'aire sous la courbe de ROC (AUC), +l'erreur moyenne de test (ATE), +l'erreur OOB (OOB) sont données et tous les résultats sont synthétisés +dans le tableau~\ref{table:experiments:summary}. +Même si la sécurité est souvent plus faible que celle observée +pour les outils les plus récents, +les résultats concernant $K_y$ sont encourageants car ils ne sont pas éloignés de +ceux de l'état de l'art sans aucune optimisation. +Enfin la faible sécurité de $K_o$ s'explique par le fait que le polynôme interpole +exactement l'image en tous les points de la fenêtre, mais il ne tient pas forcément +compte des variations dans celle-ci. Les dérivées secondes sont certes faciles +à exprimer, mais elles ne représentent pas nécessairement fidèlement celles de l'image. \begin{table} -\caption{Summary of experiments}\label{table:experiments:summary} -\begin{small} +\caption{Évaluation de la sécurité}\label{table:experiments:summary} \centering \begin{tabular}{|l|l|l|l|l|} \hline - - & Payload & AUC & ATE & OOB \\ \hline + & Taux & AUC & ATE & OOB \\ \hline {WOW} & 0.1 & 0.6501 & 0.4304 & 0.3974\\ & 0.2 & 0.7583 & 0.3613 & 0.3169\\ @@ -884,13 +698,13 @@ the pixel function $P$. & 0.3 & 0.8720 & 0.2557 & 0.2212 \\ & 0.4 & 0.9517 & 0.1472 & 0.1230 \\ \hline -{$Ky$ based approach} +{Approche à base de $Ky$} & 0.1 & 0.7378 & 0.3768 & 0.3306 \\ & 0.2 & 0.8568 & 0.2839 & 0.2408 \\ & 0.3 & 0.9176 & 0.2156 & 0.1710 \\ & 0.4 & 0.9473 & 0.1638 & 0.1324\\ \hline -{$Ko$ based approach} +{Approche à base de $Ko$} & 0.1 & 0.6831 & 0.3696 & 0.3450 \\ & 0.2 & 0.8524 & 0.1302 & 0.2408 \\ & 0.3 & 0.9132 & 0.1023 & 0.1045 \\ @@ -898,7 +712,6 @@ the pixel function $P$. \hline \end{tabular} -\end{small} \end{table} @@ -923,23 +736,23 @@ the pixel function $P$. %\end{figure} -\section{Conclusion} - -The first contribution of this paper is to propose of a distortion -function which is based on second order derivatives. These -partial derivatives allow to accurately compute -the level curves and thus to look favorably on pixels -without clean level curves. -Two approaches to build these derivatives have been proposed. -The first one is based on revisiting kernels usually embedded -in edge detection algorithms. -The second one is based on the polynomial approximation -of the bitmap image. -These two methods have been completely implemented. -The first experiments have shown that the security level -is slightly inferior the one of the most stringent approaches. These first promising results encourage us to deeply investigate this research direction. - -Future works aiming at improving the security of this proposal are planned as follows. The authors want first to focus on other approaches to provide second order derivatives with larger discrimination power. -Then, the objective will be to deeply investigate whether the H\"older norm is optimal when the objective is to avoid null second order derivatives, and to give priority to the largest second order values. +% \section{Conclusion} + +% The first contribution of this paper is to propose of a distortion +% function which is based on second order derivatives. These +% partial derivatives allow to accurately compute +% the level curves and thus to look favorably on pixels +% without clean level curves. +% Two approaches to build these derivatives have been proposed. +% The first one is based on revisiting kernels usually embedded +% in edge detection algorithms. +% The second one is based on the polynomial approximation +% of the bitmap image. +% These two methods have been completely implemented. +% The first experiments have shown that the security level +% is slightly inferior the one of the most stringent approaches. These first promising results encourage us to deeply investigate this research direction. + +% Future works aiming at improving the security of this proposal are planned as follows. The authors want first to focus on other approaches to provide second order derivatives with larger discrimination power. +% Then, the objective will be to deeply investigate whether the H\"older norm is optimal when the objective is to avoid null second order derivatives, and to give priority to the largest second order values.