X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/322d0e3286e2bc9cae4178aa7488b5631c57a8ba..a8bd04acf5ce24f5fe4686f33781d6127c7f1f49:/stegoyousra.tex?ds=sidebyside diff --git a/stegoyousra.tex b/stegoyousra.tex index dc17a7a..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,43 +27,36 @@ 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}. -\section{Derivatives in an Image}\label{sec:gradient} +\section{Des dérivées dans une image}\label{sec:gradient} -This section first recalls links between level curves, gradient, and -Hessian matrix (Section~\ref{sub:general}). -It next analyses them using kernels from signal theory -(Section~\ref{sub:class:1} and Section~\ref{sub:class:2}). +Cette section rappelle d'abord les liens entre lignes de niveau, gradient et +matrice hessienne puis analyse ensuite leur construction à l'aide +de noyaux de la théorie du signal. -\subsection{Hessian Matrix}\label{sub:general} -Let us consider that an image can be seen as a numerical function $P$ that -associates a value $P(x,y)$ to each pixel of coordinates $(x,y)$. -The variations of this function in $(x_0,y_0)$ -can be evaluated thanks to its gradient -$\nabla{P}$, which is the vector whose two components -are the partial derivatives in $x$ and in $y$ of $P$: - -\[\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). -\] - -In the context of two variables, the gradient vector -points to the direction where the function has the highest increase. -Pixels with close values thus follow level curve that is orthogonal -to the one of highest increase. - -The variations of the gradient vector are expressed in the -Hessian matrix $H$ of second-order partial derivatives of $P$. +\subsection{Matrice hessienne}\label{sub:general} +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 +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 accroissement. +Des pixels ayant des valeurs voisines sont sur des lignes de niveaux qui sont orthogonales +à ce vecteur. +Les variations du vecteur gradient s'expriment usuellement à l'aide de la matrice +hessienne $H$ des dérivées partielles de second ordre de $P$. \[ H = \begin{bmatrix} \dfrac{\partial^2 P}{\partial x^2} & @@ -73,87 +66,76 @@ H = \begin{bmatrix} \end{bmatrix}. \] - - - -In one pixel $(x_0,y_0)$, the larger the absolute values of this matrix are, -the more the gradient is varying around $(x_0,y_0)$. -We are then left to evaluate such an Hessian matrix. - -This task is not as easy as it appears since natural images are not defined -with differentiable functions from $\R^2$ to $\R$. -Following subsections provide various approaches to compute these -Hessian matrices. - -\subsection{Classical Gradient Image Approaches}\label{sub:class:1} -In the context of image values, the most used approaches to evaluate gradient vectors are the well-known ``Sobel'', ``Prewitt'', ``Central Difference'', and ``Intermediate Difference'' ones. +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. É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^+$ +dans $\R^+$. La suite montre comment obtenir des approximations de telles matrices. + +\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 `` 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 + $A * K$ est une approximation du gradient horizontal +\textit{i.e.}, $\dfrac{\partial P}{\partial x}$. +Soit $K\rl$ le résultat de la rotation d'un angle $\pi/2$ sur $K$. +La composante verticale du gradient, $\dfrac{\partial P}{\partial y}$ est obtenue +de manière similaire en évaluant $A * K\rl$. Lorsqu'on applique ceci sur toute +la matrice image, on obtient peu ou prou une matrice de même taille pour chacune des +dérivées partielles. + +Les deux éléments de la première ligne (respectivement de la seconde ligne) +de la matrice hessienne +sont le résultat du calcul du gradient sur la matrice $\dfrac{\partial P}{\partial x}$ +(resp. sur la matrice $\dfrac{\partial P}{\partial y}$). \begin{table}[ht] -\caption{Kernels of usual image gradient operators\label{table:kernels:usual} +\caption{Noyaux usuels pour évaluer des gradients d'images\label{table:kernels:usual} } \centering -\scriptsize \begin{tabular}{|c|c|c|} \hline - Name& Sobel & Prewitt \\ + Nom& Sobel & Prewitt \\ \hline - Kernel & $\textit{Ks}= \begin{bmatrix} -1 & 0 & +1 \\ -2 & 0 & +2 \\ -1 & 0 & +1 \end{bmatrix} $ & + 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 - Name & Central & Intermediate \\ - & Difference &Difference \\ + Nom & Différence & Différence \\ + & centrale & Intermédiaire \\ \hline - Kernel & $\textit{Kc}= \begin{bmatrix} 0&0&0 \\ -\dfrac{1}{2} & 0 & +\dfrac{1}{2} \\ 0&0&0 \end{bmatrix} $ & + 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} $ \\ \hline \end{tabular} \end{table} -Each of these approaches applies a convolution product $*$ between a kernel $K$ (recalled in Table~\ref{table:kernels:usual}) and - a $3\times 3$ window of pixel values $A$. The result - $A * K$ is an evaluation of the horizontal gradient, -\textit{i.e.}, $\dfrac{\partial P}{\partial x}$ -expressed as a matrix in $\R$. -Let $K\rl$ be the result of a $\pi/2$ rotation applied on $K$. -The vertical gradient $\dfrac{\partial P}{\partial y}$ is similarly obtained by computing $A * K\rl$, which is again expressed as a matrix in $\R$. - -The two elements of the first line -of the Hessian matrix are the result -of applying the horizontal gradient calculus -first on $\dfrac{\partial P}{\partial x}$ and next -on $\dfrac{\partial P}{\partial y}$. -Let us study these Hessian matrices in the next section. - - -\subsection{Hessian Matrices induced by Gradient Image Approaches}\label{sub:class:2} - -First of all, it is well known that -$\dfrac{\partial^2 P}{\partial x \partial y} $ is equal to -$\dfrac{\partial^2 P}{\partial y \partial x}$ if -the approach that computes the gradient and the -one which evaluates the Hessian matrix are the same. -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 + + +\subsection{Matrices hessiennes induites par des approches +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 gradient et le gradient du gradient (la matrice hessienne) +sont les mêmes. +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 \\ @@ -204,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}''= @@ -252,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} @@ -308,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}''$. - -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 +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: -\begin{small} \[ \arraycolsep=1.4pt \def\arraystretch{1.4} @@ -367,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} @@ -448,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'} @@ -480,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} = @@ -492,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'} @@ -502,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'} @@ -524,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'')} @@ -602,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 @@ -635,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 @@ -667,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( @@ -698,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 +\section{Experimentations}\label{sec:experiments} -%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. +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. -%The higher the second order derivatives are, -%the -%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$. -%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|} @@ -819,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\\ @@ -893,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 \\ @@ -907,7 +712,6 @@ the pixel function $P$. \hline \end{tabular} -\end{small} \end{table} @@ -932,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.