In this paper we present a new accurate steganalysis method for the LSB
replacement steganography. The suggested method is based on the changes that occur in the
histogram of an image after the embedding of data. Every pair of neighboring bins of a
histogram are either inter-related or unrelated depending on whether embedding of a bit of
data in the image could affect both bins or not. We show that the overall behavior of all
inter-related bins, when compared with that of the unrelated ones, could give an accurate
measure for the amount of the embedded data. Both analytical analysis and simulation
results show the accuracy of the proposed method. The suggested method has been
implemented and tested for over 2000 samples and compared with the RS Steganalysis
method. Mean and variance of error were 0.0025 and 0.0037 for the suggested method
where these quantities were 0.0070 and 0.0182 for the RS Steganalysis. Using 4800
samples, we showed that the performance of the suggested method is comparable with
those of the RS steganalysis for JPEG filtered images. The new approach is applicable for
the detection of both random and sequential LSB embedding.