Title of Invention

A METHOD OF EMBEDDING AND DETECTING A WATERMARK IN A ONE-DIMENSIONAL INFORMATION SIGNAL.

Abstract A method and arrangement are disclosed for watermarking in one-dimensional information signals, particularly audio signals. The Watermark, e.g. a binary signal (W(t) having uniformly distributed zeroes and ones, is embedded in the audio signal (I(t) by warping (23) salient points such as zero crossings (22) to such an extent that the statistics of the time distribution of the salient point of the watermarked signal (Iw(t) are significantly changed with respect to the watermark signal.
Full Text FIELD OF THE INVENTION
The invaition relates to a method and apparatus for embedding a wateraiaric in one-dimensional infoimation signal, for example, an audio signal. The invention also relates a method and apparatus for detecting such a watermark in an information signal.
\CKGROUND OF THE INVENTION
With the advent of modem audio compression standards such as MPS, the nger of piracy and illegal use of audio contents is growing. Therefore, the industry is eager find means of protection against illegal activities. Watermarking is a method of certifying mership of digital multimedia contents such as images, video, audio, text and data. It is a ]] for realizing copy protection.
Usually, a watermark is embedded by adding a specific low-amplitude noisy ttem to the signal. The noisy pattern represents the watermark- The presence or absence of embedded given watennark in a suspect signal is detected at the receiver end by computing ; correlation of the suspect image with an applied version of said watermark, and comparing : correlation with a threshold. If the correlation is larger than the threshold, the applied teraiark is said to be present, otherwise it is said to be absent.
IJECT AND SUMMARY OF THE INVENTION
It is an object of the invention to provide a novel method and apparatus for bedding a watermark in a one-dimensional infonnation signal, and a coiresponding method I apparatus for detecting the watennark m a suspect signal.
In accordance with the invention, the method of embedding a watennark nprises the steps of determining salient points of the infonnation signal and modifying the jrmation signal so that the salient points of the modified signal have a statistically lificant conelation with an applied watennark signal.
Salient points of a signal are herein understood to mean the temporal locations of points of interest of a given saliency function. A saliency function is i function that assigns a saliency measure to each audio signal sample. The saliency function iu quite arbitrary.

provided that the saliency measure is a local property (i.e. depends only on a small neighboring time interval), and is preserved as much as possible under signal operations such as conqjression, noise addition, cut and paste, translation, sub-sampling, scaling, etc. A simple but yet illustrative and usefiil example of salient points is zero crossings of an audio signal.
The watermark signal can be thought of as a binary signal, the 0 and I values of which are sufScientiy random and uniformly distributed. Since there is no correlation between the salient points of an ariDitrary audio signal and a random watermark signal, 50% of flie salient points will coincide with a 1 of the watemnark signal. The audio signal is now watermarked by time warping the salient points so that a significant majority of the salimt points coincides with a 1 of the watermark signal.
The corresponding method of detecting the watemoark comprises the st^s of determining salient points of the information signal, detennining the correlation of said salirat points with an af^lied watermark signal, and detecting that the ^plied watermark has been embedded in said information signal if said correlation is statistically significant.
It is to be noted that AppUcant"s International Patent Application WO-A-99/35836 discloses a method of embeddmg a watermark in images by warping salient
image points. However, the image and the vratermark signal are two-dimensional signals in this prior art publication, and geometiic warping is allied in the spatial kaagp domain, Ttw inventors of this invention have recognized that similar techniques can be applied to the one-dimensional (e.g. audio) signal domain, the watermark signal beii^ a time-dependent signal and the warping operation being carried out in the time domaiiL
Further aspects of the invention relating to advantageous embodiments for deriving salient points and difTerent watermari: signal formats are apparent fit)m and will be elucidated with reference to the embodiments described hereinafter.
BRIEF DESCRIPTION OF THE DRAWINGS
Fig. 1 shows schematically an arrangement for embeddii^ a binary-valued wratermaik in accordance with the invention.
Figs. 2 and 3 show waveforms to illustrate the operation of the watermark embedder which is shown in Fig. 1 ■
Fig. 4 shows schematically an arrangement for detecting a watermark in accordance with the invention.
Fig. 5 shows an embodiment of the watermark embedder ncluding a pre¬processing circuit, and Fig. 6 shows an embodiment of the detector including such a circuit.

Figs. 7 and 8 show waveforms to illustrate the opCTation of the embedder and the detector wAich are shown in Figs. S and 6.
Fig. 9 shows an embodiment of the pre-processing circuit
Fig. 10 shows schematically a fiirthcr embodimem of the watermark embedder in accordance with the invention.
Fig. 11 shows waveforms to illustrate the operation of an arrangement for en^)edding a real-valued watermark signal.
Fig. 12 shows schematically a generic arrangement for detecting a watermark in accordance with the invention.
Fig. 13 shows a device for playing back an audio signal, comprising a watermark detector In accordance with the invention.
DESCRIPTION OF EMBODIMENTS
Fig. 1 shows schematically a watermark embedder in accordance with the invention. The embedder receives an audio signal I(t) and a watennaik signal W(t) to be embedded in said audio signal. The audio signal I(t) and the watermark signal W(t) are continuous functions of time and have a duration T. In practice, the audio signal will be applied in digital form. Its digital representation has a finite number N of audio samples I(tj) taken at discrete points of time ti. The time period between two successive time sanq)les ti and ti+i is constant and denoted AT. The truly continuous signal I(t) is derived &om the digital signal by interpolation or sub-sampling (not shown). The watermark signal W(t) is a binary signal in this embodiment. Its transitions are assumed to lie in the mi ddle of sampling periods
AT.
- The arrangement comprises a salimt point ex^ctOT_n, a warp signal generator 12, and a modifier circuit 13. Its operation will he described with reference to waveforms that are shown in Figs. 2 and 3. Fig. 2 shows the watermark signal W(t) and the audio signal I(t). (jhe salient point extractor 11 extracts salient points, fiiom the audio si^i^^ The instants of time wiien salient points occur are referred to as Sj. A simple but yet practical example of the saiient points extractor is a zero-cross detector which produces a Dirac pulse for each zero crossing. The series of Dirac pulses defining the locations of the salient points constitutes a salient point signal P(t) which is also shown in Fig. 2.
Some salient points coincide with a " I" ofthe watermark signal W(t). These salient points are said to He "on" the watermark. Other salient points coincide with a "0" ofthe watermark signal W(t). They are said to lie "off" the watermaric The Os and Is ofthe

watermari: signal are sufSciently random and imifonnly distributed across the signal, with equal probability. Due to this property signal, about 50% of the salient points will lie on the wateimaik and 50% will not. The audio signal shown in Fig. 2 has four salient points 21 on die watermark and four salient points 22 off the watermark.
As will be described hereinafter, the embedder moves the salient points not lying on the watermaric along the time axis, such that afterwards the majority of salient points lies on the watermark. This typeflf processing is known in the art as "time warping". In Fig. 2, the process of time warping salient points is illustrated by arrows 23 denoting the direction and extent by which the salient points are moved away from their original positions.
Tlie du-ection and extent by which the audio signal is to be waiped is controlled by the"waip signal generator 12. This circuit receives the salient point signal F(t) from ibz salient point extractor 11 and the watennark signal W(t). It detennines a time warp vector v(si) to be ^}plied to each salient point s\ and calculates the value of the time waip v(t) for all other values oft. The time warp v(t) is a continuous signal and is referred to as the continuous warp signal v(t).

sampling period. Note that the temi (1 -W(Sj)) in this equation prevents salient points already lying on the watermark from being warped. The quantity c in the equation represents the embedding strength. The larger c is, the more a salient point is moved away from its initial position. To avoid audible jitter in the watermarked signal, c should be £s small as possible. For robustness of the watermark, c should be large. Note that c can be chosen in order to mask the audibility of the watermark in accordance with a human psycho-acoustic model.
The audio signal values between the salient points are to be waiped by an amoimt vkiiich gradually declines from v(sj) for salient points lyii^ off the watermark to zero for salient points akeady lying on the watormaric. To this end, the waip signal generator 12 derives the continuous waip signal v(t), vAdch defines the warp to be applied at time t, from the discrete warps v(Si) by applying a suitable form of interpolation. The continuous warp signal v(t) should be as smooth as possible. This is achieved by an ^ipropriate inteipolation algorithm. The waveform v(t) shown in Fig. 2 is an example.

The waiping is actually carried out by the modification circuit 13. This circuit receives the audio signal I(t) and the continuous warp signal v(t) and produces the wateimaiked signal Iw(t) in accordance with:

Fig. 4 shows this operation for a small part of the audio signal. In this Figure, I(t) is the unwatermarked audio signal and Iw(t) is the watennarked signal. The salient points 21 lying on the watermark are not waiped (v(t)=0). Salient point 22 lies off the watermark and is warped by the amount cAT so as to constitute a salient point 25 of !„{!). The other audio signal values are warped by an amount v(t) wiiich gradually declines fiom cAT to zero. Reference numeral 24 denotes v(t) for an arbitrary instant of time. Discrete audio output samples of the watermariced signal are eventually obtained by computing Iw(ti) from the ^xive equation.
Note that, for a given maximal embedding strength, waiping does not necessarily cause all the salient points of the watennarked signal to lie on the watermark. Some salient points will generally lie too far &om transitions of the watermark signal to become points on the watermark after waiping by cAT. Such salient points are said to be "unwarpable". Tlie occuirence of unwarpable salient points is a typical property of binary watermark signals. In Fig. 2, the extreme left one and the extreme right one of the salient points 22 are imwaipable. It is possible to refrain from waiping these salient points, but it is not certain beforehand whether this yields the best performance in terms of perceptibility of the embedded watermark. Sometimes, it is preferred to warp unwarpable salient points (note the contradiction of this wording) in order to render the warp signal v(t) as smooth as possible. In Fig. 2, the extreme left one of the salient points 22 is warped whereas the extreme right one is not. It is also possible to recursively repeat the warping operation until a desired number of salient points lies on the watermarfc, or to warp each salient point Sj to die closest time sample tj for which W(tj)=l.
Fig. 4 shows schematically the corresponding watermark detector in accordance with the invention. The detector receives a suspect audio signal J(t) and comprises the same salient point extractor llW the embedder, a matching cireuit 14, and a decision circuit IS. The /matching cireiut 14 receives the salient point signal P(t) and the watermark signal W(t) to be detected. )It counts the number S i of salient points lying on the watermark and the number So of salient points lymg off the watermark. In mathematical notation:


where T is the duration of the signal. The numbers Si and So are subsequraitly applied to the decision cireuit 15. If a statistically high percentage of the salient points lies on the watennaik, i.e. if Si»So, the watermark W(t) is said to be present in the suspect signal, o&erwise it is not
Fig. 5 shows a further embodiment of the watermark embedder. This embodiment diSers &om the one shown in Fig. 1 in that the audio signal I(t) is pre-processed by a pre-processing circuit 16 before being ^iplied to the saJient point extractor 11. The purpose of pre-processing is to derive from I(t) a more robust signal R(t) which varies as litde as possible under common audio signal processing operations such as compression. Tlie salient points, and thus the warp signal v(t) are now extracted from the robust signal R(t). However, the actual warping is ^qipiied to the original signal I(t).
Fig. 6 shows the correspondmg vratermark detector. It differs from the one shown in Fig. 4 in that the suspect audio signal J(t) is pre-processed by the same pre¬processing circuit 16 before being ^plied to the salient point extractor 11.
In a simple embodiment of pre-processing circuit 16, the robust signal R(t) is a smoothed version of I(t), obtained by low-pass filtering. An example thereof is shown in Fig. 7. Note that R(t) has fewer zero crossings than I(t), but their positions are more stable. The robust signal may also be obtained by band-pass filtering. A motivation for band-pass filtering is thai it removes the DC-component from the audio signal so that the embedded watermark is robust against translation of the audio signal along the signal"s amplitude axis.
A further embodiment of the pre-processing circuit 16 is based on the recognition that information signals generally convey the so-called "semantic essence" of the information. The semantic essence of a signal is the part of the signal which is to be preserved under v/hatevcz distortions introduced by (re)production and (de)coding devices, where these distortions are assumed to be below the human perceptual limit. For audio, and particularly music, one can intuitively think of characteristics such as pitch, loudness, attack, decay, staccato, legato, tremolos, slurs, etc. A signal representing the semantic essence as a function of time is a good example of a robust signal. The salient points extracted from such a robust signal will most likely survive couimon audio signal processing including compression such as MPS. By way of example. Fig. 8 shows various waveforms to illustrate an embodiment of such a watermaric embedder and detector. In this embodiment, the pre-processor 16 extracts the dominant frequency (pitch) of the audio signal, and salient point extnictor 11 detects significant changes of said pitch. In Fig. 8, W(t) is tiie watermark signal, I(t) is the audio signal

to be watennaiked, R(t) is the robust signal derived &om the audio signal and rqiresenting the pitch as a function of time, and P(t) is the salient point signal (here shown as points instead of Dirac pulses). The salient points are local extremes of the derivative of the robust signal R(t) in this embodiment. As the Figure shows, salient point 81 lies already on the watermaric and is therefore not warped. Salient point 82 lies ofifthe watermark and is waiped by an amount 83 to a new location 84. Iw(t) is the watemiarked signal. It is also the suspect signal J(t) applied to the detector. R"(t) is the robust signal derived &om J(t) in the detector, and P"(t) is the saUent point signal as extracted in the detector. The salient points are 85 and 86. Both salient points now lie on the watennark and the detector will thus decide that the watennark W(t) is indeed embedded.
Instead of using one robust signal for the extraction of salient points, it may be useiul to have an array of robust signal components. A filter bank can construct such an array of signal components. There are two reasons to believe that such an onay is robust First, splitting up the audio signal in frequency bands provides protection against attacks that damage the watermariced signal in a specific frequency range. Secondly, the human ear can actually be modeled by a filter bank. If the signal is corrupted in such a manner that the filter outputs are affected, the human ear will detect this. Fig. 9 shows schematically an airangement of pre-processor 16 and salient point extractor 11 aloi^ these lines. The arrangement comprises N band-pass filters 91-1...91-N. The different fi^uency components are squared (92-1-92-N) and then each fed to a respective low-pass filter 93-1..93-N w4iich computes a moving average. The outputs R| ..R^ of this process collectively form the array of robust signal components. The components actually represent the energy-time development of the signal in the different fipquency bands. The outputs Ri are each subjected to salient point extraction C94-1..94-N); Here, salient points are points of time at which the second derivative of R, is zero and the first derivative is large. The salient point signal PCt) is the conjugation (95) of the salient points of ail RjS.
In the above examples of the watennark embedder with a pre-processing circuit 16 for creating a robust signal R(t), the actual warpmg is still ^plied to the original audio signal I(t). The inventors have found that warping may also be ^plied to the robust signal itself, provided that the audio signal can be reconstructed from said robust signal. The latter condition is fulfilled, for example, if the robust signal is an array of signals obtained fiom an analysis filter bank w^ch, in combination with a complementary synthesis filter bank, constimtes a perfect reconstructing (in tenns of perceptibility) filter bank. Fig. 10 shows an embodiment of such a watermark embedder. The anangement comprises an analysis filter

bank 101 and a synthesis filter bank 102, coUectively forming a perfect reconstructing filter bank. Such fiiter banks are known in the art The analysis filter bank 101 provides a plurality of signals R](t). JlN(t) that are each ^iplied to a respective one of watermark embeddeis 103-1»]03-N. As has been shown in more detail for embedder 103-i, each embedder has the structure and function of the embedder which is shown in Fig. 1. All embedders receive die same watermark signal W(t) and modify the respective Rj(t) into a warped signal Rwi(t) in response to the salient points that were foimd in the signal. The synthesis filter bank 102 receives the wateimaiked components and synthesises the watermarked audio signal Iw(t)- The embedders 103-i may also be located in the synthesis filter bank 102 between the synthesis filter- and - conjugation circuit 1021.
It has ahvady been noted that binary watermark signals have the property that a number of salient points is unwarpable. They lie too far fixim transitions of the watemiaric signal to become points on the watermark after warping by an amount cAT. Iteal-valued watcrmaik signals W(t) do not have this property. Real-valued watermark signals have real values between, for example, -1 and +1. The values are uniformly distributed, the polarity of the signal changes sufficiently often, and the signal is preferably nou4iere constant An example is shown in Fig. 11. In diis example, the watermark is defined as a set of -1 and +1 values along the time axis. The continuous watermark signal W(t) is obtained therefix)m by linear mterpolaiion. The averse of W(t) should be 0.
Fig. 11 shows the same audio signal I(t) and corresponding salient point signal P(t) as shown in Fig. 2. The salient points are also shown in the watermark signal waveform as dots 31. For the unwatemiarked signal I(t), the correlation D of the watennark signal W(t) and the salient point signal P(t) equals approximately zero:

where T is the duration of the audio signal. The audio signal is now watermariced by warping the salient points "iqj-hill", i.e. towards the maxima of W(t) as illustrated by arrows 32 m Fig. II. The discrete warps v(Si) to be applied to the salient points at Ifae times t=Sj is denoted by arrows 33. The warps v(si) are now defined by:

where ti and ti-f i are successive sampling points of the digital audio signal and AT is the
sampling period. Note that almost ail s ts will now be warped, in contrast to the warp
signal for binary-valued watermark sif note that the expression f ignQ in the above


Fig. 12 shows schematically a watennaik detector which cairies out the above described operations. The detector comprises the same salient point extractor 11 as shown in Fig. 4, a correlation detector 17 for calculating the correlation D as a function of the watermaric signal W(t) and salient point signal P(t) in accordance with the equation defined above, and a decision circuit 18 which compares tiie correlation D with a threshold Di.


The watermark whjcfa is embedded in the audio signal may identiiy, for example, the copyriglit holder or a description of the contents. It allows material to be labeled as "copy once", "never copy", "no restriction", "copy no more", etc. Fig. 13 shows a device for playing back an audio bitstream which is recorded on a disc 131. The reicorded signal is £^piied to a reproduction device 133 via a switch 132. It is assumed that the device may not play back video signals with a predetermined embedded watermaric, unless other conditions are ful^Ied which are not relevant to the invention. For example, watermaifced signals may only be played back if the disc 131 includes a given physical "Svobble" key. In order to detect the watennark, the device comprises a watennaik detector 134 as described above. The detector receives the recorded signal and controls the switch 132 in response to whether or not the wateimaric is detected.
In summary, a method and arrangement are disclosed for watermarking in one-dimensional signals, particularly audio signals. The watermark, e.g. a binary signal (W(t)) having uniformly distributed zeroes and ones, is embedded in the audio signal (I(t)) by warping (23) salient points such as zero crossings (22) to such an extent that the statistics of

he time distribution of the salient points of the wateimarked signal (Iw(t)) are significantly Ranged with respect to the watennaik signal.


WE CLAIMS:
1. A method of embedding a watennark in a one-dimensional information signal,
comprising the steps of;
- determining salient points of the information signal,
- modifying the infomation signal so that the salient points of the modified signal have a statistically significant correlation with an applied watennark signal.

2. A method as claimed in claim I, wherein the watennark signal is a binary signal and the step of modifying the information signal comprises time-warping salient points so as to coincide with a predetemined value of the binary watermark signal.
3. A method as claimed in claim 1, wherein the watennark signal is a real-valued signal and the step of modifying the information signal comprises time-warping salient points in the direction of local extremes of the watermark signal.
4. A method as claimed in claim 1, further comprising a processing step of deriving from said information signal a robust signal representing the semantic essence of the infomiation signal, the salient points of the infomiation signal being represented by the salient points of said robust signal.
5. A method as claimed in claim 4, wherein the processing step comprises decomposing the information signal into a plurality of robust signal components and determining the salient points of each signal component.
6. A method as claimed in claim 5, wherein said decomposing includes sub-band filtering of the information signal.
7. A method as claimed in claim 5, wherein the step of modifying the information signal comprises modifying each signal component and combining the modified signal components to constiture the modified information signal.

8. A method of detecting a watennark in an information signal, comprising the
steps of:
- determining salient points of the infoimation signal,
- determining the correlation of said salient pomts with an applied watermark signal, and
- detecting that the applied watennark has been embedded in said information signal if said correlation is statistically significant.

9. A method as claimed in claim 8, wherein the applied watermark signal is a binary signal and the step of determining the correlation comprises determining the percentage of salient points that coincide with a predetermined value of the binary watermark signal.
10. A method as claimed in claim 8, further comprising a processing step of deriving from said information signal a robust signal representing the semantic essence of the infoimation signal, the salient points of the information signal being represented by the salient points of said robust signal.
11. A method as claimed in claim 10, wherein the processing step comprises decomposing the information signal into robust signal components and determining the sahent points of each signal component
12. A method as claimed in claim 11, wherein said decomposii^ mcludes sub-band filtering of the information signal.
13. An arrangement for embedding a watermark in an information signal, comprising:

- means for determining salient points of the information signal,
- means for modifying the information signal so that the salient points of the modified information signal have a statistically significant correlation with an applied watermark signal.
14. An arrangement for detecting a watennark in an information signal, comprising;
- means for determining salient points of the information signal.

- means for determimng the correlation of said salient points with an applied watermark signal, and
means for detecting that the applied watermark has been embedded in said information
lal if said correlation is statistically significant
15. A device for recording and/or playing back an information signal, comprising
means (132) for disabling recording and/or playing back of the information signal in dependence upon the presence of a watermark in said signal, characterized in that the device comprises an arrangement (134) for detecting said watennaik as claimed in claim 14.
16. A method of embedding a watermark in a one-dimensional information signal, substantially as hereinabove described and illustrated with reference to the accompanying drawings.

Documents:

in-pct-2001-0781-che abstract- duplicate.jpg

in-pct-2001-0781-che abstract- duplicate.pdf

in-pct-2001-0781-che claims- duplicate.pdf

in-pct-2001-0781-che claims.pdf

in-pct-2001-0781-che correspondence-others.pdf

in-pct-2001-0781-che correspondence-po.pdf

in-pct-2001-0781-che description (complete)-duplicate.pdf

in-pct-2001-0781-che description (complete).pdf

in-pct-2001-0781-che drawings- duplicate.pdf

in-pct-2001-0781-che drawings.pdf

in-pct-2001-0781-che form-1.pdf

in-pct-2001-0781-che form-19.pdf

in-pct-2001-0781-che form-26.pdf

in-pct-2001-0781-che form-3.pdf

in-pct-2001-0781-che form-5.pdf

in-pct-2001-0781-che pct search report.pdf

in-pct-2001-0781-che pct.pdf

in-pct-2001-0781-che petition.pdf


Patent Number 208675
Indian Patent Application Number IN/PCT/2001/781/CHE
PG Journal Number 35/2007
Publication Date 31-Aug-2007
Grant Date 07-Aug-2007
Date of Filing 04-Jun-2001
Name of Patentee M/S. KONINKLIJKE PHILIPS ELECTRONICS N.V.
Applicant Address Groenewoudseweg 1 NL-5621 BA Eindhoven,
Inventors:
# Inventor's Name Inventor's Address
1 GOEY, Zoe, M. K. Y. Holstlaan 6, NL-5656 AA Eindhoven,
2 RONGEN, Peter, M. Holstlaan 6, NL-5656 AA Eindhoven,
3 VAN OVERVELD, Cornelis, W. A. M. Holstlaan 6 NL-5656 AA Eindhoven
4 MAES, Maurice, J.J.B. Holstlaan 6, NL-5656 AA Eindhoven,
PCT International Classification Number G11B 20/00
PCT International Application Number PCT/EP00/09606
PCT International Filing date 2000-09-28
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 99203258.1 1999-10-06 Netherlands