Embedding and extracting supplemental data in an information signal

[0002] The invention relates to a method and arrangement for embedding supplemental data in an information signal, comprising the step of embedding supplemental data samples at predetermined positions of said information signal. The invention also relates to a method and arrangement for extracting the supplemental data from such an information signal.

[0003] There is a growing need to accommodate watermarks in audio and video signals. Watermarks are supplemental data messages embedded in multimedia assets, preferably in a perceptually invisible manner. They comprise information, for example, about the source or copyright status of documents and audiovisual programs. They can be used to provide legal proof of the copyright owner, and allow tracing of piracy and support the protection of intellectual property.

[0004] A known method of embedding supplemental data in an information signal as defined in the opening paragraph is disclosed, inter alia, in International Patent Application WO-A-98/33324. In this prior-art method, a watermark pattern is embedded in a (sigma-)delta-modulated audio signal. The watermark is embedded in the encoded audio signal by modifying selected bits thereof. For example, every 100^thbit is replaced by a bit of the watermark pattern. The step of modifying the encoded audio signal is carried out inside the feedback loop of the encoder so as to compensate the effect of the modification in subsequent encoding steps.

[0005] The prior-art method is envisaged for recording high-quality audio on the audio version of the Digital Versatile Disk (DVD). A sampling frequency of 2,822,400 Hz (64*44,100) will be used to yield a signal-to-noise ratio of 115 dB. Replacing every 100^thbit of the sigma-delta-modulated audio signal by a watermark bit at the expense of only 1 dB increases the quantization noise. This corresponds to watermark bit rate of about 28000 bits per second.

[0006] The above-mentioned patent application WO-A-98/33324 also discloses an arrangement for extracting the watermark. A synchronization bit pattern (hereinafter sync pattern for short) is accommodated in the bit stream to identify the supplemental data bit positions. The arrangement comprises a divider stage and a sync detector. The divider stage divides the bit rate by the number of bits by which the watermark bits are spaced apart (e.g. 100 if every 100^thbit of the signal is a supplemental data bit). The sync detector changes the phase of the divider stage until the sync pattern is found. Such a sync detector includes a relatively long shift register or serial-to-parallel converter to store a portion of the bit stream. If every M^thbit of the signal is a supplemental data bit and the sync pattern comprises N bits, the sync detector must necessarily store (N−1)·M+1 bits.

[0007] German Patent Application DE-A-37 17 315 discloses such a known sync detector in more detail. In this publication, every 15^thbit of a signal is a supplemental bit and the sync pattern is a 4-bit word. In accordance therewith, the shift register (serial-to-parallel converter 5 in FIG. 2 of DE-A-37 17 315) holds 46 bits.

[0008] In order to reduce the length of the shift register, it is proposed in Applicant's non-published co-pending patent application PHN 17.148 to make the spacing between the sync pattern bits considerably smaller than the spacing between the watermark bits. However, this solution affects the coding performance and increases the signal-to-noise ratio of the sigma-delta modulator.

[0009] It is an object of the invention to provide a method of embedding supplemental data in an information signal, which allows the supplemental data bit positions to be detected in an alternative manner.

[0010] To this end, the method in accordance with the invention is characterized in that the information signal comprises at least two signal channels, the method including the step of embedding the same supplemental data samples at corresponding positions of said channels. The transmission of a sync pattern can now be omitted because the position of the embedded watermark bits can easily be found by searching the positions in which the at least two channel samples are identical.

[0011] The corresponding method of extracting the supplemental data from the information signal comprises the steps of comparing a first sequence of predetermined first channel signal samples with a corresponding second sequence of second channel signal samples, displacing said first and second sequence by one sample position, and repeating said comparison step for said displaced first and second sequence as long as the sequences are not identical.

[0012] FIG. 1 shows a schematic diagram of a preferred embodiment of an arrangement for embedding supplemental data in a sigma-delta-modulated audio signal in accordance with the invention.

[0013] FIGS. 2 and 3 show waveforms to illustrate the operation of the sigma-delta modulators that are shown in FIG. 1.

[0014] FIG. 4 shows waveforms to illustrate the operation of the arrangement for embedding supplemental data in a signal in accordance with the invention.

[0015] FIG. 5 shows a schematic diagram of an embodiment of an arrangement for extracting the supplemental data from a signal.

[0016] FIG. 6 shows a flow chart of method steps to illustrate an embodiment of a method of extracting the supplemental data from a signal.

[0017] The invention will be explained with reference to FIG. 1, which shows a schematic diagram of a preferred embodiment of an arrangement for embedding supplemental data in a sigma-delta-modulated audio signal in accordance with the invention. The arrangement receives a stereo audio signal comprising a left channel signal x₁and a right channel signal x₂. The channels x₁and x₂are applied to conventional sigma-delta modulators 1 and 2, respectively. Both sigma-delta modulators are identical so that only one of them will be described.

[0018] Sigma-delta modulator 1 comprises a subtracter 11, a loop filter 12, a polarity detector 13 and a feedback path 14. The subtracter 11 subtracts the encoded output signal z₁(having a level of +1V or −1V) from the input signal x₁. The loop filter 12 filters the difference signal. The filtered signal is applied to the polarity detector 13 which produces, at a rate determined by a sampling frequency f_s, an encoded signal y₁having the bit value “1” (+1V) or “0” (−1V).

[0019] FIG. 2 shows waveforms to explain the operation of the conventional sigma-delta modulator. More particularly, the Figure shows an input signal x and the encoded signal y. The sigma-delta modulator produces more positive samples as the input signal becomes larger. As the Figure shows, an input voltage of −0.5V is encoded as a bit sequence 0001 (three −1V pulses and one +1V pulse), an input voltage of 0V is encoded as a high-frequency bit pattern 01010 (alternating −1V and +1V pulses), and an input voltage of +0.5V is encoded as a bit sequence 1110 (three +1V pulses and one −1V pulse).

[0020] The encoded signal is decoded at the receiving end by reshaping the received pulses and passing them through a low-pass filter. In this simplified example, it is assumed that the encoded signal is demodulated by averaging 13 samples of the signal. The demodulated signal x′ is also shown in FIG. 2, apart from a time delay caused by said low-pass filter operation. In the Figure, the demodulated signal x′ is thus time-aligned with the input signal x.

[0021] Modification circuits 3 and 4 are connected between the polarity detector 13 and the feedback path 14 of the respective sigma-delta modulators. In response to a control signal c delivered by a control circuit 5, the modification circuits (multiplexers) replace every M^thbit of the encoded signals y₁and y₂by a watermark bit w. The modified encoded signals z₁and Z₂are combined by a multiplexer 6 to form a single bit stream for transmission to a receiver or recording on a storage medium. The watermark message W is stored in a register 501 of the control circuit 5. It is important to note that the same watermark W is applied to both modification circuits 3 and 4.

[0022] FIG. 3 shows waveforms to explain the operation of the sigma-delta modulator if the respective modification circuit is active. The Figure shows the same input signal x as shown in FIG. 2 and the modified encoded signal z. In the example, a “−1” sample 20 (FIG. 2) of the encoded signal y has been replaced by a “+1” sample 30 so as to represent a watermark bit w=1. Because the modification is fed back to the input, the adverse effect of the modification will subsequently be compensated by the encoding stage. Thus, a portion of the output signal z immediately following the supplemental data bit 30 differs from the corresponding portion shown in FIG. 2. In accordance therewith, the demodulated signal x′ in FIG. 3 is also temporarily different from the same signal in FIG. 2. Note that the time alignment in the Figures causes the difference to become already manifest before the supplemental data bit is embedded.

[0023] As will be appreciated from a comparison of FIGS. 2 and 3, the difference is hardly noticeable in practice. A sigma-delta modulator for encoding high-quality audio signals at a sampling frequency f_s=2,822,400 Hz (64*44,100) has a signal-to-noise ratio of 115 dB. It has been found that replacing 1 sample per 100 samples increases the quantization noise by only 1 dB.

[0024] FIG. 4 shows a simplified example of a multi-channel audio bit stream which is produced by the arrangement shown in FIG. 1. In this simple example, every 10^thbit of the channel bit streams z₁and z₂is a supplemental data bit. The embedded watermark data bits w are shaded in the Figure. They are the same in both channels. The encoded signal bits are generally not the same. This is even true in practice if the audio signal is a mono signal. The bit positions m within each series of M bits are numbered 0 . . . M−1.

[0025] It will be appreciated that it is the objective of a receiver arrangement to identify the bit position of the supplemental data bits (m=2 in FIG. 4). This is accomplished by searching the bit positions of the multi-channel bit stream in which the signal samples z₁and z₂are identical. Once this objective has been formulated, an arrangement for searching these bit positions can easily be designed by a person skilled in the art. For illustration, two embodiments will now be described.

[0026] FIG. 5 shows a schematic diagram of a hardware implementation of an arrangement for extracting the supplemental data from the bit stream z which is produced by the encoder shown in FIG. 1. The arrangement comprises a demultiplexer 50 for demultiplexing the audio bit stream z into the bit stream z₁representing the left audio channel and the bit stream z₂representing the right audio channel. The arrangement further comprises a divide-by-M counter 51. Every M^thbit period, said counter produces a timing pulse representing a current bit position m (m=0 . . . M−1) being tested. The bit streams z₁and z₂are applied to a comparator 52. In response to the timing pulse m, the comparator produces a pulse EQ if the currently applied bits are the same, or a pulse NQ if they are different.

[0027] If the bits are the same, they are potential watermark bits. In that case, the potential watermark bit z₂(or z₁) is shifted in a shift register 53 in response to the EQ pulse. The next timing pulse now occurs M bit periods later. Thus, as long as every M^thbit of z₁and the corresponding bit of z₂are identical, that particular bit is shifted in the shift register. If the bits are not the same, the comparator 52 produces the pulse NQ. This pulse is applied to a shift input S of the counter 51 so as to shift the phase of this divide-by-M counter by one bit period. The pulse NQ is also applied to a clear input C of the shift register 53 to clear the register.

[0028] The arrangement shown in FIG. 5 is simple and cost-effective but has the disadvantage that a relatively long period of time must be observed until it may be assumed that the watermark bit position has been found, and that the watermark message has not fully been acquired from the beginning. The expected time to be observed until the arrangement has found the watermark bit position depends on the number of bits (M) by which the watermark bits are spaced apart and the probability (p) that the bits in both channels are identical (p≈½ for sigma-delta-modulated audio signals). The expected period of time until a false lock is recognized is: $T_{\mathrm{false}}=\mathrm{Mp}\sum _{k=0}^{\infty }{k\left(1-p\right)}^k=\frac{\mathrm{Mp}}{1-p}$

[0029] The average period of time to detect the watermark bit position is: $T_{\mathrm{lock}}=\frac{M^{2}p}{2\left(1-p\right)}$

[0030] Using a number of parallel detection circuits, each processing a displaced sequence of potential watermark bits, can accelerate the detection and extraction of the watermark.

[0031] The detection and extraction of the watermark can also be performed by a microprocessor which is loaded with a suitable software program. FIG. 6 shows a flow chart of operation steps that are carried out by such a microprocessor in accordance with a further embodiment of the arrangement. It is again assumed that every M^thbit of each channel bit stream is a watermark bit.

[0032] The microprocessor uses for each bit position m (m=0 . . . M−1, see FIG. 4) an array element R(m) to indicate whether a potential watermark bit on said bit position has been detected (R(m)=1) or not (R(m)=0). In a first step 60 of the program, all array elements R(0) . . . R(M−1) are initially given the value 1. In a step 61, the bit position m being tested obtains an initial value 0. The program then awaits the reception of a new bit from the channel bit streams z₁and z₂. In a step 62, both bits are compared. If they are identical, an optional step 63 is carried out which will be described later. The corresponding array element R(m) remains unaffected. If the channel bits are not identical, the corresponding array element R(m) is given the value 0 (step 64) to indicate that the current bit position m is definitely not the watermark bit position being looked for. In a step 65, the bit position is incremented. In step 66, it is checked whether the incremented bit position is still within the range 0 . . . M−1. If that is the case, the program returns to the step 62 to test the next bit position. If that is not the case, the program first performs an optional step 67, which will be described later, and then returns to the step 61 (in which the bit position number m is reset) to test the next series of M channel bits.

[0033] After the first series of M channel bits has been processed in this manner, a number of bit positions have already been found not to be watermark bit positions. With reference to the example shown in FIG. 4, this applies to bit positions 1, 5 and 7. The corresponding array elements R(1), R(5) and R(7) have now obtained the value 0 and will not be modified anymore, even if the bits at said positions will later be the same.

[0034] Whenever a series of M channel bits is processed, a further number of bit positions will be excluded from being a candidate watermark bit position. In the example shown in FIG. 4, the bit positions 0, 4, 8 and 9 will be excluded during the second run, bit position 6 will be excluded during the third run, and, finally, bit position 3 will be excluded during the fourth run. The arrangement has now identified the watermark bit position m=2 in this simple example.

[0035] The method shown in FIG. 6 has detected the watermark bit position m as soon as one array element R(m) has the value 1 and all other array elements have the value 0. To signify this, the program further includes the processing step 67 in which it is tested whether the sum of all array elements is 1. The processing step 67 may be located at various places of the program. In this example, the test is carried out when the bit position m has assumed the value M, i.e. whenever a series of M candidate bit positions has been processed.

[0036] The acquisition of the watermark data message may be postponed until the watermark bit position has been found. However, it is possible to acquire the watermark message while the search for its position is running. To this end, the arrangement includes a further array W in which each candidate watermark message received so far is acquired. To this end, the program shown in FIG. 6 includes the step 63 in which the received watermark bit w is added to the currently received message. As soon as the watermark bit position m has been found, the corresponding array element W(m) has already acquired the watermark message received so far.

[0037] It should be noted that the arrangement for detecting the watermark bit positions can further be extended to check whether an accidental shift has occurred in one of the channels. For example, if the watermark is embedded in three or more channels, the arrangement can be arranged to search for the offset of one of the channels. Or the arrangement is arranged to intentionally introduce a shift in one of the channels if the watermark has not been identified in a predetermined portion of the signal or within a predetermined period of time.

[0038] Although the invention has been described with reference to a sigma-delta-modulated (unity-bit coded) two-channel audio signal, it is not limited to audio or unity-bit coded signals. The signal samples may be multi-bit samples (e.g. PCM samples), the watermark being embedded in one or more less significant bits of said samples. The coding algorithm is irrelevant (it may, for example, be pulse code modulation), nor is it required that the step of embedding the supplemental data is carried out within the feedback loop of an encoder. The essential feature of this invention is that the same supplemental data samples are embedded at corresponding positions of two or more channels of a multi-channel information signal.

[0039] In summary, a method and an arrangement are disclosed for embedding supplemental data in an information signal such as a sigma-delta-modulated audio signal. The encoded signal includes two or more channels, e.g. a left channel bit stream (z₁) and a right channel bit stream (z₂). The same supplemental data (w) is accommodated at corresponding predetermined bit positions, e.g. every M^thbit position, of the bit streams. This allows detection and extraction of the supplemental data without the need for accommodating a sync pattern in the signal. At the receiving end, a sequence of M^thbits from the first channel is compared with a corresponding sequence of M^thbits from the second channel. If they are identical, the sequence is a candidate supplemental data sequence. This is done for different sequence positions (m) until the supplemental data has been found.