Lossless data embedding methods for digital images and detection of steganography

Data hiding and digital watermarking together with the well-established field of cryptography has been proposed as a means of achieving security of digital multimedia.; However, one common drawback of virtually all current data embedding methods for images is the fact that the original image is inevitably distorted due to data embedding itself. This distortion typically cannot be removed completely due to quantization, bit-replacement, or truncation at the grayscales 0 and 255. Although the distortion is often quite small and perceptual models are used to minimize its visibility, the distortion may not be acceptable for medical imagery (for legal reasons) or for military images inspected under non-standard viewing conditions (after enhancement or extreme zoom). In the first half of this dissertation, we introduce a new paradigm for data embedding in images—the lossless data embedding—that has the property that the distortion due to embedding can be completely removed from the watermarked image after the embedded data has been extracted. We present lossless embedding methods for the uncompressed formats (BMP, TIFF) and palette formats (PNG, GIF). We also show how the concept of lossless data embedding can be used as a powerful tool to achieve a variety of non-trivial tasks, including lossless authentication using fragile watermarks, steganalysis of least significant bit (LSB) embedding, and distortion-free robust watermarking.; With a vast number of publicly available steganographic tools on the Internet, the danger of their misuse has recently created a pressing need for detection of steganography. In the second half of this dissertation, we describe a reliable, accurate, and fast method for detecting random changes in the LSBs in digital images stored in uncompressed raster formats. The secret message length is derived by inspecting two dual LSB-sensitive statistics during LSB randomization. We also introduce another method designed for detection of LSB embedding in palette images.