|

A Digital Watermark (van Schyndel et al., 1994)

Van Schyndel and colleagues embed a digital watermark, a hidden message, in an image by manipulating its least significant bit, or LSB. This is the lowest binary digit of a pixel’s brightness value. Their methods either replace that digit with a code pattern or add the pattern to the image. The authors envisage carrying authentication or authorisation codes and information needed to interpret the picture. They seek visually undetectable changes and accurate message recovery for image tagging, copyright protection and controlled access. R. G. van Schyndel, A. Z. Tirkel, and C. F. Osborne, A digital watermark, ICIP (1994).

Why hide the message in the lowest bit?

The authors want an image to carry identifying or interpretive information while retaining its visible contents. Their starting problem is embedding an undetectable message and extracting it accurately. They choose direct pixel manipulation: an eight-bit grayscale pixel holds a brightness from 0 to 255, and its LSB separates adjacent even and odd values. A bit plane collects the same binary digit from every pixel.

Section 2 argues that hardware imperfections or quantisation noise often already corrupt this plane. Quantisation means representing brightness with a finite set of levels. The authors therefore regard sacrificing the LSB as having limited significance in many imaging systems. They qualify visibility by image content: a pattern can become visible across large areas with little intensity variation. Their rationale links the embedding location to expected image noise and to the need to preserve the picture’s brightness range.

Why use an extended m-sequence and encode its phase?

The decoder needs a pattern it can distinguish from image content. An m-sequence is a maximal-length binary sequence generated by shifting stored bits and combining selected bits. Autocorrelation compares a sequence with shifted copies of itself. The authors choose m-sequences for their balance, random appearance and concentrated autocorrelation peak. They reject Costas arrays, two-dimensional patterns they studied, because the patterns are sparse.

The sequence length and the extended length are:

ordinary length = 2^n - 1
extended length = 2^n

Here n is the number of stored generator bits. Extension fits a power-of-two image dimension and creates a null, or zero response, around the main autocorrelation peak. Phase means the sequence’s starting position within its repeating cycle. The authors choose phase to carry the message for simplicity; changing the sequence or using its complement, which flips every bit, are other choices they discuss.

“For simplicity, we have chosen to encode the water mark by the choice of m-sequence phase.”

— van Schyndel et al. (1994), Section 1

How does replacement make room for the code?

Directly replacing brightness bits sacrifices image information. Section 3 first compresses the image’s eight-bit brightness representation to seven bits through adaptive histogram manipulation. A histogram counts pixels at each brightness. A compensating mapping then restores the dynamic range, the span of available brightness values. The authors describe the prepared image as practically indistinguishable from the original.

The replacement path proceeds row by row:

  1. Reduce brightness precision using the image histogram.
  2. Map the reduced levels across the brightness range, freeing the LSB.
  3. Select a sequence phase for the row’s message value.
  4. Write the shifted sequence into the row’s lowest-bit plane.
  5. Extract that plane and compare it with the stored reference to recover the phase.

For illustration, use the 7-bit sequence 1110010 from a 3-bit generator; the method uses longer sequences, with 512 bits in our test. Shifting it right by 3 gives 0101110. Writing those bits into prepared even pixels 100, 102, 104, 106, 108, 110, 112 gives 100, 103, 104, 107, 109, 111, 112. Mapping extracted and reference bits to minus one or plus one gives circular correlation 7 at shift 3 and −1 elsewhere.

A message carried by a circular shift An illustrative 3-bit generator produces reference 1110010, with period 7. Shifting right by 3 gives 0101110. Prepared even pixels 100, 102, 104, 106, 108, 110, 112 become 100, 103, 104, 107, 109, 111, 112 when their lowest bits hold that pattern. Reading the lowest bits returns 0101110. Map zero to minus one and one to plus one in both received and reference patterns. Multiply corresponding signs and sum for each circular shift. For shifts 0, 1, 2, 3, 4, 5, 6, the scores are -1, -1, -1, 7, -1, -1, -1. The peak 7 at shift 3 recovers the message value. These are prepared pixels, not the original image before brightness reduction. A message carried by a circular shift Illustrative 3-bit generator; period 7 Reference pattern Shift right by 3: message value 3 1 1 1 0 0 1 0 0 1 0 1 1 1 0 Write into one prepared pixel row Prepared even brightness values Marked brightness values Read back the lowest bits 100 102 104 106 108 110 112 100 103 104 107 109 111 112 0 1 0 1 1 1 0 Compare every circular shift Map both patterns: 0 to −1, 1 to +1 Multiply matching positions, then sum Correlation score −1 0 −1 1 −1 2 7 3 −1 4 −1 5 −1 6 Candidate shift Peak at shift 3: recovered message 3
A message carried by a circular shift

Why add the pattern instead of replacing a bit plane?

The authors also seek an embedding operation that preserves a linear relation between image and watermark. Linear addition adds the binary pattern to the brightness values. The abstract argues that this permits some processing, such as averaging, while retaining a recoverable watermark. The detector must examine the complete brightness pattern, making extraction dependent on image content.

In words and symbols, with x the image brightness, b the selected binary code and y the marked brightness:

y(i) = x(i) + b(i)

This expresses the addition operation described in Section 3. The authors attribute added security to an attacker having to perform the decoding operations without prior knowledge. Their implementation performs decoding off-line, which they identify as its principal disadvantage. Partial correlation between image and code also causes recovery errors. Correlation here means multiplying corresponding received and reference values and summing them; an image structure can contribute its own response at a candidate phase.

Why filter correlation before choosing a message?

An image can mask the watermark’s correlation peak. Section 3 describes a sharp message peak superimposed on a significant, slowly varying background. A differential filter combines nearby correlation values to separate this sharp feature from the background. The authors tested different filter lengths and repeated filtering, selecting this kernel for their image and sequence size:

kernel = [-1, -1, 4, -1, -1]
F(k) = 4 R(k) - R(k-2) - R(k-1) - R(k+1) - R(k+2)

R(k) is correlation at phase k; F(k) is its filtered value. The equation writes the stated kernel as a sum. Circular sequence shifts wrap at the row ends. Threshold detection accepts a candidate when its response exceeds a chosen level. The authors describe separating image and message peak distributions as evidence that thresholding is feasible. Their histogram analysis suggests reducing brightness from eight bits to five should permit successful detection. They also suggest longer sequences or improved filtering and detection algorithms.

All parts of the method

The message determines the sequence phase for each row. Replacement prepares brightness levels, inserts the pattern in the LSB and compares extracted bits with a reference. Addition inserts the pattern into full brightness values, correlates each received row with the reference, and filters the response to locate message peaks. The authors’ threshold proposal uses the separation between background and message responses. The diagram presents the two decoding paths, including the largest-peak choice used by our addition decoder.

Our decoder finds each row’s sequence shift Our decoder compares each received row with a known sequence, applies the addition filter once, and always selects the shift with the largest value. Our decoder finds each row's shift Both paths use the known reference pattern. Read the received rowCoding: lowest bits; addition: full values Correlate with shifted referenceAdd signed matches at every shift Addition: filter correlation onceFilter weights: -1, -1, 4, -1, -1 Choose the largest value's shiftCoding uses the unfiltered correlation Read the encoded row valueThe shift represents a message symbol Correlation means a sum of paired products. The original image is not a decoder input.
Our decoder finds each row’s sequence shift

What experiments did the authors run?

The authors examine embedding and visibility, filter selection and threshold separation, false detections, simultaneous messages, and recovery of repeated text.

Embedding and visibility

Section 3 reports experiments on 512-by-512, eight-bit grayscale images, encoded line by line with extended sequences of length 2^9. For replacement, the operation reduces brightness precision to seven bits and maps the levels back across the dynamic range. The authors describe this prepared image as practically indistinguishable from the original. For addition, they describe a composite image before and after watermark insertion and an enlarged detail, referenced as Figure 4(a–c).

The authors qualify invisibility by the expectation of low-level Gaussian noise, meaning random intensity variation with a bell-shaped distribution. Section 2 states that m-sequence encoding and one-bit Gaussian noise are statistically indistinguishable, while large areas of small intensity variation can reveal the changes. Section 3 says computer-generated images typically fall outside the stated noise condition.

Filter selection and threshold separation

For addition decoding on 512-by-512 images with a nine-bit sequence generator, the authors tested impulse-response filters of various lengths, in single-pass and multiple-pass configurations. An impulse response specifies the weights used to combine neighboring correlation samples. They report optimum results for the kernel [-1, -1, 4, -1, -1].

Section 3 describes image and message correlation histograms in Figure 3(a–b) as separated sufficiently to support threshold decoding. Histogram analysis suggests a three-bit dynamic-range reduction, from eight bits to five, should permit successful threshold detection. A sequence of length 2^15 or improved filtering is proposed as an alternative. The authors argue that these alternatives should similarly suppress interference from image content.

False positives and false negatives

The authors investigate image content’s effect on correlation for the same row-based addition method. A false positive is an image response accepted as a watermark; a false negative is a message response that the detector misses. They attribute imperfect extraction to partial correlation of the image data with the encoding sequence. Their account treats image-dependent background responses as the reason for filtering and brightness compression.

Simultaneous messages

Section 3 also describes adding two distinct messages to the same image. Each message uses a different m-sequence, and both patterns are added to the brightness data. The authors investigate mutual interference and recovery ability. Their stated application is an image carrying separate hospital and radiologist watermarks. They examine how each added sequence affects recovery of the other message.

Repeated-text recovery

The authors describe filtered correlation for an image with and without its added mark in Figure 4(d). Message peaks appear as single white dots whose positions determine letters. The displayed message is “aabbccAABBCC ” repeated four times. The result connects sequence phase to recovered characters in the marked composite image. The authors identify image dynamic range and the correlation output as the main difficulties in their conclusions. Section 5 assigns cropping, skew, rotation and translation experiments to future work; the abstract describes JPEG and MPEG compression compatibility as potential.

Our test: Which row values survive JPEG?

We re-implemented the method ourselves because we did not find the authors’ code. Our code and numeric results are on GitHub.

SettingValue
ImagesAirplane; Boat
Preparation512×512, eight-bit grayscale
MessageNine message bits per row
JPEG quality100, 95, 85, 75, 50

The inputs are USC-SIPI Airplane and Boat. Both methods receive the same message values. JPEG quality is the encoder setting that controls preservation of image detail.

The panels show each original, both marked outputs, and absolute pixel differences amplified 32 times. Absolute difference is the size of a brightness change without its sign. Peak signal-to-noise ratio, or PSNR, expresses average squared pixel error on a logarithmic scale in decibels, abbreviated dB. Message bit accuracy is the percentage of recovered message bits that match their inputs. Row recovery requires the entire phase value to match.

Airplane original, both LSB outputs, differences amplified 32 times, and known-pattern restoration
Boat original, both LSB outputs, differences amplified 32 times, and known-pattern restoration
Image / methodPSNR dBBits %Rows %
Airplane / coding48.35100.00100.00
Boat / coding47.46100.00100.00
Airplane / addition51.1454.6210.16
Boat / addition51.1452.003.91

These are the clean-image results. Subtracting the known inserted pattern restored every pixel in both addition images. Restoration uses the saved pattern. LSB coding replaces brightness information, so removing its code cannot restore the original.

Airplane coding and addition outputs after every tested JPEG quality, labeled by method and quality
Boat coding and addition outputs after every tested JPEG quality, labeled by method and quality
LSB coding: row recovery: our measurements Exact row recovery is the percentage of rows with the correct decoded shift; the horizontal axis is JPEG quality or the uncompressed clean output, and the vertical axis is percent. LSB coding: row recovery: our measurements Airplane Boat Rows recovered (%) 0 20 40 60 80 100 Clean 100.00 100.00 100 100.00 100.00 95 0.59 0.00 85 0.20 0.39 75 0.00 0.20 50 0.20 0.39 JPEG quality (Clean: no compression)
LSB coding: row recovery: our measurements
LSB addition: row recovery: our measurements Exact row recovery is the percentage of rows with the correct decoded shift; the horizontal axis is JPEG quality or the uncompressed clean output, and the vertical axis is percent. LSB addition: row recovery: our measurements Airplane Boat Rows recovered (%) 0 3 6 9 12 Clean 10.16 3.91 100 10.35 4.10 95 3.52 2.34 85 0.39 0.59 75 0.20 0.59 50 0.20 0.39 JPEG quality (Clean: no compression)
LSB addition: row recovery: our measurements

The charts show exact row recovery, including the clean outputs. Coding recovered every row at JPEG quality 100 on both images. At quality 95, row recovery was 0.59% for Airplane coding and 0.00% for Boat coding. Addition recovered 3.52% and 2.34% respectively at that quality.

Our coding preparation merges adjacent histogram groups and maps their averages to even brightness values before insertion. Addition uses full grayscale values, one filter pass, and the largest filtered value without a detection threshold. Values above 255 are limited to 255; no tested addition exceeded 255. Restoration subtracts the saved inserted pattern before JPEG compression.

ItemSetting
Random message starting value199409
PreparationGrayscale conversion; no resizing
SequenceNine stored bits, initially all ones; each new bit is the oldest bit exclusive-or the fifth-oldest bit
HistogramUp to 128 groups; even representatives
AdditionBinary 0 or 1; saturate at 255
JPEGQualities 100, 95, 85, 75, 50; grayscale

Exclusive-or returns a set bit when its input bits differ.

Conditions and limits

Decoding requires the reference sequence, its bit convention and the correct row boundaries. The authors tie visibility to expected low-level image noise and describe addition recovery as dependent on image content. They identify retaining the brightness range and separating correlation peaks as practical difficulties. They propose adaptive filtering and geometric-distortion experiments as future work. Our test keeps image dimensions and alignment fixed and uses photographs processed by JPEG compression. Its decoder selects the largest filtered response; the paper discusses threshold detection.

Implementation details

The same preparation and decoder settings apply to both photographs. The histogram limit controls brightness reduction in the coding path. The filter uses wraparound at the ends of the correlation sequence. Our restoration operation uses the saved insertion pattern. The authors describe hardware implementation in programmable gate arrays, integrated circuits whose logic can be configured, as a route to on-line, real-time execution.

References

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *