]> AND Private Git Repository - canny.git/blobdiff - intro.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
reprise texte coutu
[canny.git] / intro.tex
index 745751fd2ce63effdb2e630fadc6be8887d84172..a13492f227af5587a6fb87be838f91d953f73dde 100644 (file)
--- a/intro.tex
+++ b/intro.tex
-
-This work considers digital images as covers and foundation is
-spatial least significant-bit (LSB) replacement.
-In this data hiding scheme a subset of all the LSB of the cover image is modified 
-with a secret bit stream depending on to a key, the cover, and the message to embed.
-This well studied steganographic approach  never decreases (resp. increases)
-pixel with even value (resp. odd value) and may break structural symmetry.
-These structural modification can be detected  by statistical approaches 
-and thus by steganalysis methods~\cite{DBLP:journals/tsp/DumitrescuWW03,DBLP:conf/mmsec/FridrichGD01,Dumitrescu:2005:LSB:1073170.1073176}.
-
-This drawback is avoided in LSB matching (LSBM) where
-the $+1$ or $-1$ is randomly added to the cover pixel LSB value 
-only if this one does not match the secret bit.
-Since probabilities of increasing or decreasing pixel value are the same, statistical approaches 
-cannot be applied there to discover stego-images in LSBM.
-The most accurate detectors for this matching are universal steganalysers such as~\cite{LHS08,DBLP:conf/ih/2005,FK12}
-which classify images thanks to extracted features from neighboring elements of noise residual.  
-
-
-LSB matching revisited (LSBMR)~\cite{Mielikainen06} have been recently introduced. 
-For a given pair of pixels, in which the LSB
-of the first pixel carries one bit of secret message, and the relationship
-(odd–even combination) of the two pixel values carries
-another bit of secret message. 
-
-
-
-In such a way, the modification
+This research work takes place in the field of information hiding, considerably developed these last two decades. The proposed method for 
+steganography considers digital images as covers.
+It belongs to the well-known large category
+of spatial least significant bits (LSBs) replacement schemes.
+Let us recall that, in this LSB replacement category, a subset of all the LSBs of the cover image is modified 
+with a secret bit stream depending on: a secret key, the cover, and the message to embed.
+In this well-studied steganographic approach,
+if we consider that a LSB is the last bit of each pixel value,  
+pixels with an even value (resp. an odd value) 
+are never decreased (resp. increased), 
+thus such schemes may break the 
+structural symmetry of the host images.
+And these structural alterations can be detected by 
+well-designed statistical investigations, leading to well-known 
+steganalysis methods~\cite{DBLP:journals/tsp/DumitrescuWW03,DBLP:conf/mmsec/FridrichGD01,Dumitrescu:2005:LSB:1073170.1073176}.
+
+Let us recall too that this drawback 
+can be fixed by considering the LSB matching (LSBM) subcategory, in which
+a $+1$ or $-1$ is randomly added to the cover pixel's LSB value 
+only if this one does not correspond to the secret bit.
+%TODO : modifier ceci
+By considering well-encrypted hidden messages, the probabilities of increasing or decreasing the value of pixels  are equal. Then usual statistical approaches 
+cannot be applied here to discover stego-contents in LSBM.
+The most accurate detectors for this matching are universal steganalysers such as~\cite{LHS08,DBLP:conf/ih/Ker05,FK12},
+which classify images according to extracted features from neighboring elements of residual noise.  
+
+
+Finally, LSB matching revisited (LSBMR) has recently been introduced in~\cite{Mielikainen06}. 
+It works as follows: for a given pair of pixels, the LSB
+of the first pixel carries a first bit of the secret message, while the parity relationship
+(odd/even combination) of the two pixel values carries
+a second bit of the message. 
+By doing so, the modification
 rate of pixels can decrease from 0.5 to 0.375 bits/pixel
 (bpp) in the case of a maximum embedding rate, meaning fewer
 rate of pixels can decrease from 0.5 to 0.375 bits/pixel
 (bpp) in the case of a maximum embedding rate, meaning fewer
-changes to the cover image at the same payload compared to
-LSB replacement and LSBM. It is also shown that such a new
+changes in the cover image at the same payload compared to both
+LSBR and LSBM. It is also shown in~\cite{Mielikainen06} that such a new
 scheme can avoid the LSB replacement style asymmetry, and
 scheme can avoid the LSB replacement style asymmetry, and
-thus it should make the detection slightly more difficult than the
+thus it should make the detection slightly more difficult than in the
 LSBM approach. % based on our experiments
 
 
 
 
 
 LSBM approach. % based on our experiments
 
 
 
 
 
-Instead of (efficiently) modifying LSBs, there is also a need to select pixels whose value 
+Additionally to (efficiently) modifying LSBs, there is also a need to select pixels whose value 
 modification minimizes a distortion function.
 modification minimizes a distortion function.
-This distortion may be computed thanks to feature vectors that are embedded for instance in steganalysers
-given above. 
-Highly Undetectable steGO (HUGO) method~\cite{DBLP:conf/ih/PevnyFB10} is one of the most efficient instance of such a scheme.
-It takes into account SPAM features (whose size is larger than $10^7$) to avoid overfitting a particular 
-steganalyser. Thus a distortion measure for each pixel is individually determined as the sum of differences between
-features of SPAM computed from the cover and from the stego images.
-Thanks to this feature set, HUGO allows to embed $7\times$ longer messages with the same level of 
-indetectability than LSB matching. 
-However, this improvement is time consuming, mainly due to the distortion function
-computation. 
+This distortion may be computed thanks to feature vectors that
+ are embedded for instance in the steganalysers
+referenced above. 
+The Highly Undetectable steGO (HUGO) method~\cite{DBLP:conf/ih/PevnyFB10},
+WOW~\cite{conf/wifs/HolubF12}, and UNIWARD~\cite{HFD14}
+are some of the  most efficient instances of such a scheme.
+
+HUGO takes into account so-called SPAM features.
+Thus a distortion measure for each
+pixel is individually determined as the sum of the differences between
+the features of the SPAM computed from the cover and from the stego images.
+The features embedded in WOW and UNIWARD are based on Wavelet-based 
+directional filter. Thus, similarly, the distortion function is 
+the sum  of the differences between these wavelet coefficients  
+computed from the cover and from the stego images.
+Due to this distortion measures, HUGO, WOW and UNIWARD allow
+to embed messages that are $7$ times longer than the former
+ones with the same level of 
+indetectability as LSB matching. 
+However, this improvement has a larger computation cost, mainly due to
+ the distortion function
+computation.
 
 
 There remains a large place between random selection of LSB and feature based modification of pixel values.
 We argue that modifying edge pixels is an acceptable compromise. 
 
 
 There remains a large place between random selection of LSB and feature based modification of pixel values.
 We argue that modifying edge pixels is an acceptable compromise. 
-Edges form the outline of an object: they are the boundary between overlapping objects or between an object
-and the background. A small modification of pixel value in the stego image should not be harmful to the image quality:
-in cover image, edge pixels already break its continuity  and thus already contains large variation with neighbouring 
-pixels. In other words, minor changes in regular area are more dramatic than larger modifications in edge ones. 
-Our proposal is thus to embed message bits into edge shapes while preserving other smooth regions. 
-
-Edge based steganographic schemes have been already studied~\cite{Luo:2010:EAI:1824719.1824720,DBLP:journals/eswa/ChenCL10}.
-In the former, the authors show how to select sharper edge regions with respect 
-to embedding rate: the larger the number of bits to be embedded, the coarse the edge regions are.
-Then the data hiding algorithm is achieved by applying LSBMR on pixels of this region. 
-The authors show that this method is more efficient than all the LSB, LSBM, LSBMR approaches 
-thanks to extensive experiments.
-However, it has been shown that the distinguish error with LSB embedding is fewer than 
+Edges form the outline of an object: they are the boundaries between overlapping objects or between an object
+and its background. When producing the stego-image, a small modification of some pixel values in such edges should not impact the image quality, which is a requirement when
+attempting to be undetectable. Indeed,
+in a cover image, edges already break the  continuity of pixels' intensity map and thus already present large variations with their neighboring 
+pixels. In other words, minor changes in regular areas are more dramatic than larger modifications in edge ones. 
+Our first proposal is thus to embed message bits into edge shapes while preserving other smooth regions. 
+
+Edge based steganographic schemes have already been  studied, 
+the most interesting 
+approaches being detailed in~\cite{Luo:2010:EAI:1824719.1824720} and 
+in~\cite{DBLP:journals/eswa/ChenCL10}.
+In the former, the authors present the Edge Adaptive
+Image Steganography based on LSB matching revisited further denoted as  
+EAISLSBMR. This approach selects sharper edge
+ regions with respect 
+to a given embedding rate: the larger the number of bits to be embedded is, the coarser
+the edge regions are.
+Then the data hiding algorithm is achie\-ved by applying LSBMR on some of the pixels of these regions. 
+The authors show that their proposed method is more efficient than all the LSB, LSBM, and LSBMR approaches 
+through extensive experiments.
+However, it has been shown that the distinguishing error with LSB embedding is lower than 
 the one with some binary embedding~\cite{DBLP:journals/tifs/FillerJF11}.
 the one with some binary embedding~\cite{DBLP:journals/tifs/FillerJF11}.
-We thus propose to take benefit of these optimized embedding, provided it is not too time consuming.
-In the latter, an hybrid edge detector is presented followed by an ad'hoc
-embedding approach. 
-The Edge detection is computed by combining fuzzy logic~\cite{Tyan1993} 
-and Canny~\cite{Canny:1986:CAE:11274.11275} approaches. The goal of this combination 
-is to enlarge the set of modified bits to increase the payload. 
-
-
-But, one can notice that all the previous referenced 
-schemes~\cite{Luo:2010:EAI:1824719.1824720,DBLP:journals/eswa/ChenCL10,DBLP:conf/ih/PevnyFB10}
-produce stego content 
-with only considering the payload, not the type of image signal: the higher the payload is, 
-the better the approach is said to be. 
-Contrarely, we argue that some images should not be taken as a cover because of the nature of their signal.
-Consider for instance a uniformly black image: a very tiny modification of its pixels can be easily detectable.  
-The approach we propose is thus to provide a self adaptive algorithm with a high payload, which depends on the 
-cover signal.
-
-
-\JFC{Christophe : énoncer la problématique du besoin de crypto et de ``cryptographiquement sûr'',  les algo déjà cassés....
-l'efficacité d'un encodage/décodage ...} 
-To deal with security issues, message is encrypted... 
-
-In this paper, we thus propose to combine tried and 
-tested techniques of signal theory (the adaptive edge detection), coding (the binary embedding), and cryptography 
-(the encrypt the message) to compute an efficient steganography 
-scheme, which takes into consideration the cover image 
-an which is amenable to be executed on small devices.  
-
-The rest of the paper is organised as follows. 
-Section~\ref{sec:ourapproach} presents the details of our steganographic scheme.
-Section~\ref{sec:experiments} shows experiments on image quality, steganalytic evaluation, complexity of our approach 
-and compare them to state of the art steganographic schemes.
-Finally, concluding notes and future works are given in section~\ref{sec:concl}
-
-
+We thus propose to take advantage of this optimized embedding, provided they are not too time consuming.
+In the latter, an hybrid edge detector is presented followed by an ad hoc
+embedding. 
+The Edge detection is computed by combining fuz\-zy logic~\cite{Tyan1993} 
+and Canny~\cite{Canny:1986:CAE:11274.11275} approaches. 
+The goal of this combination 
+is to enlarge the set of modified bits to increase the payload of the data hiding scheme. 
+
+
+One can notice that all the previously referenced 
+sche\-mes~\cite{Luo:2010:EAI:1824719.1824720,DBLP:journals/eswa/ChenCL10,DBLP:conf/ih/PevnyFB10}
+produce stego contents 
+by only considering the payload, not the type of image signal: the higher the payload is, 
+the better the approach is said to be.
+For instance, studied payloads range from 0.04 to 0.4 modified bits per pixel.
+Contrarily, we argue that some images should not be taken 
+as a cover because of the nature of their signals.
+Consider for instance a uniformly black image: a very tiny modification of its 
+pixels can be easily detected.
+Practically speaking, if Alice would send
+a hidden message to Bob, she would never consider
+such kind of image and a high embedding rate.   
+The approach we propose here is thus to provide a small complexity 
+self adaptive algorithm
+with an acceptable payload, which 
+depends on the  cover signal. 
+The payload is further said to  
+ be acceptable if it  allows to embed a sufficiently 
+long message in the cover signal. 
+Practically speaking, our approach is efficient enough for
+payloads close to 0.06 bit per pixel which allows to embed 
+messages of length larger than 15,728 bits in an 
+image of size $512\times 512$ pixels. 
+
+% Message extraction is achieved by computing the same
+% edge detection pixels set for the cover and the stego image. 
+% The edge detection algorithm is thus not applied  on all the bits of the image,
+% but to exclude the LSBs which are modified. 
+
+Finally, even if the steganalysis discipline
+ has known  great innovations these last years, it is currently impossible to prove rigorously
+that a given hidden message cannot be recovered by an attacker.
+This is why we add to our scheme a reasonable
+message encryption stage, to be certain that,
+even in the worst case scenario, the attacker
+will not be able to obtain the original message content.
+Doing so makes our steganographic protocol, to a certain extend, an asymmetric one.
+
+To sum up, well-studied and experimented
+techniques of signal processing (adaptive edges detection), 
+coding theory (syndrome-trellis codes), and cryptography 
+(Blum-Goldwas\-ser encryption protocol) are combined in this research work.
+The objective is to  compute an efficient steganographic
+sche\-me, whose principal characteristic is to take into 
+consideration the cover image and to be compatible with small computation resources.  
+
+The remainder of this document is organized as follows. 
+Section~\ref{sec:ourapproach} presents the details of the proposed steganographic scheme and applies it on a running example. Among its technical description, 
+its adaptive aspect is emphasized.
+Section~\ref{sub:complexity} presents the overall complexity of our approach
+and compares it to HUGO, WOW, and UNIWARD.
+Section~\ref{sec:experiments} shows experiments on image quality, steganalysis evaluation, and compares them to the state of the art steganographic schemes.
+Finally, concluding notes and future work are given in Section~\ref{sec:concl}.