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.