Transparent lossless audio watermarking

Abstract

An encoding method and encoder is provided for transparent lossless audio watermarking by quantizing an original PCM audio signal twice, each quantization quantizing to a quantization grid. As a PCM signal is inherently already quantized, there are three quantization grids to consider, the first being the quantization grid of the original PCM signal, the second being that of the watermarked signal and the third being that of an intermediate signal. The technique reduces the amount of introduced quantization error, spectrally shapes the error and fully decorrelates signal alterations from the original audio, thus making the error more similar to additive noise. A decoding method and decoder is also provided, as is a method of altering the watermark without fully decoding the encoded signal.

Claims

1. A method for losslessly watermarking a first audio signal to generate a second audio signal, wherein the first and second audio signals are pulse code modulated PCM signals, the method comprising: receiving the first audio signal as samples quantised on a first quantisation grid; determining a third quantisation grid coarser than the first quantisation grid; applying a quantised mapping to the first audio signal to furnish a third audio signal having sample values that lie on the third quantisation grid; generating first data when multiple values of the first quantisation grid would be mapped to the value of the third audio signal by the quantised mapping, wherein the first data is reconstruction data that indicates which of the multiple values is the value of the first audio signal; combining the first data with watermark data to produce second data; determining a second quantisation grid different than the first and third quantisation grids in dependence on the second data; and, generating samples of the second audio signal by quantising the third audio signal onto the second quantisation grid in dependence on previous samples of at least one of the second and third audio signals.

2. A method according to claim 1, wherein at least one of the first and third quantisation grids varies from sample to sample.

3. A method according to claim 1, wherein the third quantisation grid is determined in dependence on the output of a pseudo-random sequence generator.

4. A method according to claim 1, wherein the first, second and third audio signals are multichannel and at least one of the second and third quantisation grids is not formed as the Cartesian product of an independent quantisation grid on each channel.

5. A method according to claim 1, wherein the quantised mapping is preceded by a filter whose output is quantised more finely than the first quantisation grid.

6. A method according to claim 1, wherein the second data also comprises initialisation data relating to consecutive samples of the third audio signal.

7. A method according to claim 6, wherein the total number of bits within the initialisation data does not exceed 8 times the number of channels times the number of consecutive samples of the third audio signal.

8. A method for retrieving a first audio signal and watermark data from a portion of a second audio signal, wherein the first and second audio signals are pulse code modulated PCM signals, and wherein the second audio signal is a losslessly watermarked PCM signal and the first audio signal has samples that lie on a first quantisation grid, the method comprising: determining a third quantisation grid; receiving the second audio signal as quantised samples; retrieving first data and the watermark data from the second audio signal, wherein the first data is reconstruction data for use in retrieving the first audio signal; generating samples of a third audio signal, quantised onto the third quantisation grid, by quantising samples of the second audio signal in dependence on previous samples of at least one of the second and third audio signals; applying a quantised mapping to the third audio signal in dependence on the first data to furnish a mapped signal; and, furnishing the first audio signal in dependence on the mapped signal.

9. A method according to claim 8, wherein the first audio signal replicates a portion of an original PCM audio signal having samples that lie on a first quantisation grid and the second audio signal is a watermarked version of the original PCM audio signal.

10. A method according to claim 9, wherein the third quantisation grid is coarser than the first quantisation grid.

11. A method according to claim 8, wherein at least one of the first and third quantisation grids varies from one sampling instant to another.

12. A method according to claim 8, wherein the third quantisation grid is determined in dependence on the output of a pseudo-random sequence generator.

13. A method according to claim 8, wherein the first, second and third audio signals are multichannel and at least one of the second and third quantisation grids is not formed as the Cartesian product of an independent quantisation grid on each channel.

14. A method according to claim 8, wherein the mapped signal is the first signal.

15. A method according to claim 8, further comprising the steps of: determining a fourth quantisation grid finer than the first quantisation grid; computing an adjustment sample dependent on previous samples of at least one of the first audio signal and the mapped signal, the adjustment sample having a value lying on the fourth quantisation grid; and, adding the adjustment sample to the mapped signal.

16. A method according to claim 8, wherein the second audio signal was generated using the method and wherein the step of retrieving comprises: retrieving a replica of the second data from the second audio signal; extracting the first data and the watermark data from the replica of the second data.

17. A method according to claim 8, the method further comprising: retrieving initialisation data from the second audio signal; and, using the initialisation data to determine a selection of bits from consecutive samples of the third audio signal.

18. A method according to claim 17, where the initialisation data is no greater than 8 bits times the number of channels times the number of values of the third audio signal.

19. A method for altering the watermark in an input audio signal that is a losslessly watermarked PCM signal, the method comprising the steps of: receiving the input audio signal as quantised samples; retrieving input data comprising embedded watermark data from the input audio signal; generating samples of an intermediate audio signal, quantised onto an intermediate quantisation grid, by quantising the input audio signal in dependence on previous samples of at least one of the input audio and intermediate audio signals; producing output data by altering the embedded watermark data in the input data; determining an output quantisation grid in dependence on the output data; and, quantising the intermediate audio signal to an output audio signal on the output quantisation grid in dependence on previous samples of at least one of the output and intermediate audio signals.

20. A method according to claim 19, wherein the intermediate quantisation grid varies from one sampling instant to another.

21. A method according to claim 19, wherein the intermediate quantisation grid is determined in dependence on the output of a pseudo-random sequence generator.

22. An encoder adapted to losslessly watermark a first signal comprising a pulse code modulated (PCM) audio signal to generate a second signal, the encoder comprising: a receiver configured to receive a first audio signal as samples quantised on a first quantisation grid; and a signal processor configured to: determine a third quantisation grid coarser than the first quantisation grid, apply a quantised mapping to the first audio signal to furnish a third audio signal having sample values that lie on the third quantisation grid, generate first data when multiple values of the first quantisation grid would be mapped to the value of the third audio signal by the quantised mapping, wherein the first data is reconstruction data that indicates which of the multiple values is the value of the first audio signal, combine the first data with watermark data to produce second data; determine a second quantisation grid different than the first and third quantisation grids in dependence on the second data, and generate samples of the second audio signal by quantising the third audio signal onto the second quantisation grid in dependence on previous samples of at least one of the second and third audio signals.

23. A decoder for retrieving a first audio signal and watermark data from a second audio signal, wherein the first and second audio signals are pulse code modulated PCM signals, the second audio signal is a losslessly watermarked PCM signal, and the first audio signal has samples that lie on a first quantisation grid, the decoder comprising: a receiver configured to receive the second audio signal as quantised samples; and a processor configured to: retrieve first data and the watermark data from the second audio signal, wherein the first data is reconstruction data for use in retrieving the first audio signal, determine a third quantisation grid, generate samples of a third audio signal, quantised onto the third quantisation grid, by quantising samples of the second audio signal in dependence on previous samples of at least one of the second and third audio signals, apply a quantised mapping to the third audio signal in dependence on the first data to furnish a mapped signal, and furnish the first audio signal in dependence on the mapped signal.

24. A non-transitory computer-readable storage medium comprising program instructions that when executed by a processor cause the process to perform a method for losslessly watermarking a first audio signal to generate a second audio signal, wherein the first and second audio signals are pulse code modulated (PCM) signals, the method comprising: receiving the first audio signal as samples quantised on a first quantisation grid; determining a third quantisation grid coarser than the first quantisation grid; applying a quantised mapping to the first audio signal to furnish a third audio signal having sample values that lie on the third quantisation grid; generating first data when multiple values of the first quantisation grid would be mapped to the value of the third audio signal by the quantised mapping, wherein the first data is reconstruction data that indicates which of the multiple values is the value of the first audio signal; combining the first data with watermark data to produce second data; determining a second quantisation grid different than the first and third quantisation grids in dependence on the second data; and generating samples of the second audio signal by quantising the third audio signal onto the second quantisation grid in dependence on previous samples of at least one of the second and third audio signals.

25. A non-transitory computer-readable storage medium comprising program instructions that when executed by a processor cause the process to perform a method for retrieving a first audio signal and watermark data from a portion of a second audio signal, wherein the first and second audio signals are pulse code modulated PCM signals, and wherein the second audio signal is a losslessly watermarked PCM signal and the first audio signal has samples that lie on a first quantisation grid, the method comprising: determining a third quantisation grid; receiving the second audio signal as quantised samples; retrieving first data and the watermark data from the second audio signal, wherein the first data is reconstruction data for use in retrieving the first audio signal; generating samples of a third audio signal, quantised onto the third quantisation grid, by quantising samples of the second audio signal in dependence on previous samples of at least one of the second and third audio signals; applying a quantised mapping to the third audio signal in dependence on the first data to furnish a mapped signal; and, furnishing the first audio signal in dependence on the mapped signal.

26. A watermark modifier adapted to alter a watermark in an input audio signal that is a losslessly watermarked, the watermark modifier comprising: a receiver configured to receive the input audio signal as quantised samples; and a signal processor configured to: retrieve input data comprising embedded watermark data from the input audio signal, generate samples of an intermediate audio signal, quantised onto an intermediate quantisation grid, by quantising the input audio signal in dependence on previous samples of at least one of the input audio and intermediate audio signals, produce output data by altering the embedded watermark data in the input data, determine an output quantisation grid in dependence on the output data, and quantize the intermediate audio signal to an output audio signal on the output quantisation grid in dependence on previous samples of at least one of the output and intermediate audio signals.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Examples of the present invention will be described in detail with reference to the accompanying drawings, in which:

(2) FIG. 1A is a signal-flow diagram of an encoder according to an embodiment of the invention;

(3) FIG. 1B is a signal-flow diagram of a decoder corresponding to the encoder of FIG. 1A;

(4) FIG. 2 shows detail of the operation of quantiser 211 in FIG. 1B for use with a two-channel signal;

(5) FIG. 3 shows detail of the operation of quantiser 112 in FIG. 1A for use with a two-channel signal;

(6) FIG. 4 shows detail of the operation of quantiser 212 in FIG. 1B for use with a two-channel signal;

(7) FIG. 5A shows a graph of a Veroni region of quantiser 111 in FIG. 1A when adapted for use with a two-channel signal, and FIG. 5B shows an expanded graph of the Veroni region;

(8) FIG. 6 represents a stream of PCM audio watermarked according to the invention showing two restart points and restart assistance data encoded prior to each of the two restart points;

(9) FIG. 7 shows an alternative configuration for part of the decoder shown in FIG. 1B, for use immediately after a restart point;

(10) FIG. 8A shows how a PCM audio signal by may be modified by adding a more finely quantised function of previous sample values to the signal;

(11) FIG. 8B shows how the latter stage of the decoder shown in FIG. 1B may be modified in order to permit the signal modification of FIG. 8A to be inverted losslessly;

(12) FIG. 9 shows how the part of a decoder shown in FIG. 8B can be modified in order temporarily to provide lossy reconstruction of an original signal pending receipt of the restart information required to provide initialise the lossless reconstruction shown in FIG. 8A; and,

(13) FIG. 10 shows how watermark data may be extracted from a stream watermarked according to the invention, then how the stream may be watermarked with alternative watermarking data, without full decoding and re-encoding of the audio signal.

DETAILED DESCRIPTION

(14) In the process known as subtractive dither, a random deviate is added to a signal, the resultant value is then quantised and the same deviate then subtracted again. Subtractive dither is known to increase the transparency of a quantisation by making the quantisation error noiselike and independent of the signal being quantised, as discussed by M. Gerzon and P. Craven in A High Rate Buried Data Channel for Audio CD, preprint 3551 presented at the 94th AES Berlin Convention 1993 (hereinafter Gerzon).

(15) As Gerzon points out, true subtractive dither requires the random deviate to be drawn from a continuous distribution. In our embodiments we will need the deviates to have a finite number of bits so as to control the wordwidth of the subtractively dithered signal which will be used as an input to multipliers. 8 bits of random deviate is adequate for our purposes, moving any quantisation artifacts down from around the 16 bit level to around the 24 bit level whilst still allowing plenty of room for 16 bit audio in a 32 bit word.

(16) Generally, a lattice quantiser is used so that, prior to subtraction, the quantised value lies on a quantisation lattice. One could just as well subtract before the quantisation and add afterwards. In this case the resultant values lie on the quantisation lattice plus an offset given by the random deviate. This offers an alternative perspective on subtractive dither, that the whole operation is one of quantisation onto a randomised grid.

(17) We shall use the term quantisation offset to denote the offset of this grid from the lattice defining the quantisation. We shall frequently consider quantisation offsets that vary from sample to sample of the audio signal, usually generated by a pseudorandom sequence generator, but sometimes with some modification and sometimes generated by other means.

(18) We shall also use the term quantisation grid to mean the set of points that the quantiser could output, which is a combination of the quantisation lattice and the offset. If the quantisation offset varies from sample to sample then so will the quantisation grid.

(19) Where we talk of using pseudorandom number generators we will require their outputs to match between encoder and decoder. This can be done by including sample number data in the overhead to be conveyed alongside the watermark. When a decoder commences operation partway through a track it can use that sample number data to seek to the correct place in the pseudorandom sequences so that the subsequent output of its pseudorandom number generator will match that used in the encoder.

(20) The invention now will be explained with reference to an embodiment which processes 2 channels of 16-bit PCM audio. There is nothing special about the number 16 however and the skilled person will have no difficulty in adapting the disclosure to other bit-depths or quantisation schemes. The person familiar with Gerzon should also have no difficulty in generalising to one or many channels.

(21) Input to the watermarker may come from a source such as CD whose samples on each channel are quantised on a lattice {2.sup.16 k}, k consisting of all integer multiples of 2.sup.16. However we keep open the possibility that it has been generated by a subtractive dither process and has a pseudo-random quantisation offset known to the watermarker and programmed into the watermark restorer or decoder. We thus speak of the input to the watermarker and the output from a subsequent restorer having a first quantisation offset. In the CD case this will be zero for all samples, in the case where audio is provided by a subtractive dither process it will be given by an agreed pseudorandom sequence.

(22) Our watermarker will follow WO2013061062 in applying a gain of g.sup.1 (where g<1) to the audio and cope with any resultant overload by soft clipping the resultant audio (using the clip unit 133 and the inverse operation, the unclip unit 233). The combination of gain and clipping corresponds to the sigmoid gain function of WO2004066272.

(23) The invention will be described with reference to FIGS. 1A and 1B. A two channel 16 bit PCM audio signal is considered as comprising samples each of which is a two dimensional vector whose components are quantised to 16 bits. In FIG. 1A, such a signal 101 quantised to a lattice having a quantisation offset O.sub.1 is presented to the encoder. The sample values of the PCM signal are divided 131 by a gain g (where g<1) and then quantised 111 onto a coarser quantisation lattice to yield an intermediate signal 103. This coarser grid jointly quantises both channels to a 15.5 bit level where the quantisation lattice is defined by {[2.sup.16, 2.sup.16] [2.sup.16, 2.sup.16]}, with a pseudorandom offset O.sub.3. Hence the quantisation grid is [2.sup.16(j+k), 2.sup.16(jk)]+O.sub.3 where j, k.

(24) Assuming for now that the clip unit 133 does not modify the signal (as is true for much of the range), then signal 104 is a replica of signal 103. Signal 104 is then quantised again 112 onto the same 15.5 bit lattice but with an offset chosen in dependence on data 143 (comprising the watermark) to yield an output signal 102 which has the effect of embedding data 143 into the output signal 102. The offset is [0,0] to embed a 0 and [0, 2.sup.16] to embed a 1, so data 143 is contained in the parity of the lsbs of the two channels in a similar manner to that described in Gerzon.

(25) As shown in FIG. 1B, a corresponding decoder receives a replica 202 of the audio output 102 from the encoder. Data 243, a replica of 143, is recovered by determining which quantisation offset O.sub.2 was used by inspection of the sample values. Signal 202 is then quantised 212 onto the 15.5 bit lattice above, with quantisation offset O.sub.3 such that the quantisation error introduced by quantiser 212 is the opposite of that introduced by quantiser 112 so that signal 204 replicates signal 104. Unclip unit 233 inverts clip unit 133, so signal 203 replicates signal 103. This signal is then multiplied by g 231 and quantised 211 onto the 16 bit lattice with quantisation offset O.sub.1. Quantiser 211 does not always output the nearest quantised value to its input as will be later described with reference to FIG. 2. It takes in reconstruction data which may adjust its output by +2.sup.16 on either channel, which is arranged to replicate the value on signal 101 establishing lossless operation.

(26) Filters 121, 221, 122, 222 are also arranged so that the decoder versions receive input signals replicating those in the encoder and consequently, subject to suitable initialisation on startup, their outputs also match. Their effect is to shape the quantisation error introduced by the quantisers, so that the overall quantisation error in the watermarked signal 102 is spectrally shaped for reduced audibility and thus increased transparency of the watermark. They shape the white quantiser noise with an all-pole transfer function, as in FIG. 7 of Gerzon. A reasonable filter G(z) for operation at 44.1 kHz is:
G(z)=1+1.2097z.sup.1+0.2578z.sup.2+0.1742z.sup.3+0.0192z.sup.40.2392z.sup.5
For later reference, the sum of the absolute values of the impulse response of 1/G(z) is less than 27.

(27) The 15.5 bit quantisations are coarser than the 16 bit quantisation of the encoder input signal. Consequently, even though g<1, there are sometimes multiple input values to 111 which quantise to the same value of 103. When this occurs, ambiguity resolver 113 (which sees signal 105, a scaled version of the quantiser error introduced by 111) outputs data 141 indicating which of the possible input values was actually presented. Along with formatting overhead, this reconstruction data 141 is multiplexed with the desired watermark into data 143.

(28) Correspondingly, the decoder extracts reconstruction data 241 from 243 and uses it to adjust the output from 211 on those occasions when multiple input values to 111 could have produced the same value 103. Quantiser 211 is expanded in FIG. 2. FIG. 2 shows how the input signal is first quantised 213 to the nearest value and the quantisation error 205 fed to adjuster 215. It turns out that for any gain value g, the quantisation error 205 suffices to indicate how many input values to 111 could have produced the 103. If the answer is more than one, adjuster 215 consumes data from 241 to determine the adjustment 207 to add to the output of 213. Consequently, this ancillary data 241 ensures that 201 replicates 101 even when some other quantised value may be slightly closer to the input of quantiser 211.

(29) The use of a 15.5 bit quantiser above does complicate operation compared to the 15 bit quantiser described in WO2004066272. It is useful though because it means the watermarking adds half as much noise as if a 15 bit quantiser is used making the watermarker more transparent. The process could be taken further, for example using a 15.75 bit quantiser that jointly quantised 4 samples, 1 on each of 4 samples or 2 successive samples on each of 2 channels would halve the added noise again. However, our embodiment only processes 2 channels and there would be greater complexity in jointly quantising successive samples.

(30) FIG. 3 shows an example of a 15.5 bit quantiser 112. Box 301 implements a 15.5 bit lattice quantiser which takes its two channel input and forms half sum and difference of the channels by elements 304-307. 16 bit quantisers 308 and 309 then quantise the channels and the output is formed by a further sum and difference. The possible outputs of 301 are pairs of integers whose lsbs are either both 0 or both 1.

(31) Box 301 is expanded to box 112 by subtracting 302 a bit of data 143 (scaled to be 0 or 2.sup.16) from one channel prior to box 301 and adding it back 303 afterwards. If the bit is a zero, then 112 quantises onto the lattice quantisation grid with offset [0,0]. If it is a one, then 112 quantises onto the lattice grid with offset [0,2.sup.16], where the lsb of one channel is 0 and the other 1.

(32) Referring back to FIG. 1B, data 243 is produced by inspecting the parity of pairs of lsbs of corresponding samples from the two channels to determine which offset was used in the 15.5 bit quantisation. If the channels have the same lsb, then a zero is produced into 243 or if different lsbs then a one is produced.

(33) Quantiser 212 quantises to the same resolution as 112. As shown in FIG. 4 it is very similar to quantiser 112, except that the offset O.sub.3 is pseudo-randomly chosen rather than a data driven selection between two offsets. Accordingly, two samples from a pseudorandom number generator (PRNG) generating values between 0 and 2.sup.15 are used to create a 2D offset for the quantisation grid G.sub.3 from the constant grid 301 quantises to. This offset is subtracted from the input to 301 and added to the output of 301.

(34) There are other ways of achieving the same effect, for example the outputs of 312 and 313 could be subtracted immediately prior to quantisers 308 and 309 and added back immediately afterwards. Such schemes differ however in the mapping between values from 312 and 313 and the choice of offset O.sub.3, so a compatible choice needs to be made between decoder quantiser 212 and encoder quantiser 111.

(35) So long as the lattice quantisers 308 and 309 used in 112 and 212 are compatible with each other, decoder quantiser 212 will remove the quantisation error introduced by 112, restoring signal 203 to be a replica of signal 103. However, compatible does not mean identical. In this embodiment Q.sub.112(x)=(ceiling(.sup.1x0.5)) and Q.sub.212(x)=(floor(.sup.1x+0.5)) where is the stepsize 2.sup.16. Sufficient conditions for compatibility are Q.sub.112(x)=Q.sub.212(x)=Q.sub.112(x)+ for all x.

(36) Quantiser 111, also quantises to 15.5 bits with offset O.sub.3 and the architecture should match that of 212 so that it has the same mapping from pseudo-random numbers to O.sub.3. The choice of offset O.sub.3 needs to match in both encoder and decoder, so the pseudorandom number generators in 212 must be synchronised to match those in 111. This can be done by embedding synchronisation information (such as sample number) periodically in data 143.

(37) FIGS. 5A and 5B shows how data 141 is produced from scaled error quantiser error signal 105. (To avoid confusing the diagram, the output from noise shaping filter 121 is supposed to be zero).

(38) In the graph shown in FIG. 5A, the axes are the left and right channel of signal 101, with the grid of horizontal and vertical lines corresponding to allowable quantised values that could be presented on the input (as given by the 16 bit lattice and offset O.sub.1).

(39) One of these intersections is labelled as representing the actual value presented on this illustrative occasion. After division by g, quantisation by 111 and multiplication by g, an illustrative value for signal 106 is shown. The Veroni region for quantiser 111 described above is a diamond shape. It is shown scaled by g on the graph of FIG. 5A. Of course, the actual value of 101 lies within this region since signal 101 divided by g quantised to signal 106. If it were the only value that did then a corresponding decoder would be able to uniquely identify the actual value of 101 from the value of 106. In the case shown there is one other possible value shown that would also have produced the given value of 106, so the decoder will need a bit of additional information 141 to resolve which of the quantised values lying in the Veroni region it should output.

(40) The graph shown in FIG. 5B expands the Veroni region, which is centred on signal 105=0. If signal 105 lies within any of the dashed diamonds, then there is another possible value for signal 101 lying in the opposite dashed diamond (which is translated in one dimension by g) and ambiguity resolver 113 needs to send a bit of information in data 141 to resolve which of the two opposites should be produced by the decoder. For example, if signal 105 lay in the left diamond then a zero could be sent whilst if it lay in the right diamond then a 1 could be sent. Likewise a 0 could be sent for the bottom diamond and a 1 for the top diamond. Alternatively, if the value for signal 105 lies in no dashed diamond, then it must lie in the central cross region. Here there is no alternative possibility for signal 101 and no data need be sent. For this choice of quantiser, there is never any possibility of more than 2 values lying in the Veroni region so data 141 has at most 1 bit per sample.

(41) The width of each dashed diamond is 2 g1, so if g<0.5 then the dashed diamonds disappear and there is never any ambiguity to resolve. Also for g=1, the cross disappears and so the datarate on 141 is always 1 bit per sample which saturates the data capacity of quantiser 112 leaving no spare capacity for overhead or watermark. Hence the requirement that g<1.

(42) Under certain circumstances, inaccuracies in computing the dashed regions can be tolerated. It is important that the encoder computations must exactly match the computations performed in the decoder (else encoder and decoder operation would diverge). It is also important that the dashed regions are not computed too small, otherwise there could be values of signal 201 which the decoder cannot produce. But it isn't a big problem if the dashed regions are a little larger than strictly required. This consequence of this inaccuracy is that occasionally a data 141 carries a bit of data it didn't need to, slightly wasting data capacity.

(43) Small errors in the computation of signal 105 (such as fine quantisation if the decoder multiplication 231 by g produces an inconveniently large wordwidth) can thus be accommodated so long as the decoder makes matching approximations (in 231) and they both pad out the size of the dashed diamonds to accommodate the worst case inaccuracy.

(44) In the decoder, the output of quantiser 213 is one possible value that might have been presented to the encoder. Adjuster 215 can make a corresponding decision to ambiguity resolver 113 as to whether a reconstruction bit needs pulling in from data 241. If it is needed and the bit indicates the opposite dashed diamond to the one 205 lies in, then adjuster 215 outputs an adjustment signal 207 to adjust the output of quantiser 211 to the correct value to replicate signal 101. Any adjustment will be 1 lsb on either the left or the right channel.

(45) Clip

(46) Due to the gain element 131, signal 103 will exceed the representable range of 16 bit audio, and clip 133 is there to bring the signal back into the representable range so that the watermarked output 102 does not overload.

(47) For much of the signal range, the clip unit 133 makes no modification of the signal. Near full scale it has a small signal gain of <1 and maps multiple values of its input onto specific values of its output. When this occurs, it generates clip reconstruction data 142 specifying which of the multiple values was actually presented. The clip reconstruction data 142 is combined with the reconstruction data 141 and watermark to form the data 143.

(48) The unclip unit 233 is the inverse of the clip unit. For much of the signal range it makes no modification of the signal. Near full scale it has a small signal gain of <1 and maps specific values of its input onto multiple values of its output. When this occurs, it consumes clip reconstruction data 242 to choose which of those multiple values it actually outputs. Clip reconstruction data 242 is extracted along with reconstruction data 141 and the watermark from data 243. The operation here is as described in WO2013061062, for example as shown in FIG. 11 thereof.

(49) For simplicity in this embodiment we have both signals 103 and 104 quantised to a 15 bit lattice (with no offset) which is a subset of the 15.5 bit lattice and so does not alter the quantisation offset of signal 104. When a channel is not clipping, we desire it to pass through the clip completely unmodified and so when a channel does clip we choose it to alter the signal by a multiple of 2.sup.15 in order that we stay on the same quantisation offset without altering the other channel.

(50) This 15 bit quantisation of the adjustment due to clipping is as loud as the other noise sources put together and not noise shaped. We consider that acceptable in our quest for higher transparency because it only occurs during clipping when the signal is loud, and undergoing distortion from the soft clip. Moreover in a later embodiment we describe the use of filtering which can greatly reduce the incidences of signal clipping. The combination of gain and clip gives the sigmoid transfer function C of WO2004066272. One might well wonder why we choose to combine a linear gain with a sigmoid clipping function rather than perform it all in one stage, especially as if it was performed in one stage the additional 15 bit noise source wouldn't be introduced.

(51) The answer is that we expect to wish to alter the gain g from sample to sample and believe that the complexities of constructing the ambiguity resolver 113 and adjuster 215, especially given our randomised 15.5 bit joint quantisation grid G.sub.3 would outweigh the disadvantage of the noise introduced by this method.

(52) Initialisation

(53) As described above, lossless reconstruction of signal 201 requires the outputs from filters 221 and 222 to match those of filters 121 and 122 in the encoder. This requirement is satisfied if the decoder was operating losslessly on the preceding samples, and it is also satisfied at the start of an encoded track when both encoder and decoder can have their respective filter states initialised to a common value such as zero. However, useful operation of a decoder also requires the ability to start up part way through an encoded stream, which makes spectrally shaping the quantisation noise trickier than one might at first suppose.

(54) In our embodiment, we provide for certain points in the stream to be restart points, as illustrated in FIG. 6. The watermarked audio 102 is shown, with the data channel 143 as the XOR of its lsbs. 400, 401 and 402 are restart points where the decoder will be able to commence lossless decoding of the original audio. Restart point 400 is at the start of the track, and here filters 221 and 222 can be initialised to 0, matching a similar reset at the encoder. Restart points 401 and 402 however are in mid-track and so the buried data 143 has to contain restart assistance information 411 and 412 which will be used to initialise filter state for starting up the decoder to decode losslessly from 401 or 402.

(55) Now the restart assistance information 411 is buried before the corresponding restart point 401 so that the decoder can be armed with the data when it needs to use it to initialise filter state at 401. Now altering the buried data 143 at a point affects the quantisation of 112 and the filter 122 means that this altered data affects subsequent quantisations as well. If the restart assistance data 411 depended on the state of the filter 122 at the restart point 401, we would have an awkward circularity for the encoder to resolve since that state depends on the earlier buried data.

(56) Fortunately, an all-pole noise shaping architecture in which (G1) is a Finite Impulse Response (FIR) filter allows this circularity to be avoided. The state of filter 122 is the difference between recent values of the intermediate signal 104 and the watermarked signal 102. As the decoder approaches restart point 401, it has access to signal 202 prior to the restart point, a replica of 102. So it suffices for the restart information to allow reconstruction of intermediate signal 104 for n samples immediately prior to 401, where the output of filter 122 is a function of the previous n values of its input. Since signal 104 does not depend on the buried data 143, the circularity is avoided.

(57) The restart information could contain a complete copy of those n samples of signal 104 but if restart points are frequent then this could be an inconveniently large amount of data. We now present a method which allows rather less restart information to suffice.

(58) Signals 104 and 102 only differ by a noise shaped quantisation, and so their difference is bounded. This bound can be computed from the impulse response of the noise shaping transfer function and the magnitude of the quantisation error. In our embodiment the quantiser 211 produces a maximum absolute error on a channel of 2.sup.16 g<2.sup.16. And the sum of the absolute values of the impulse response of the noise shaping filter 1/G(z) is less than 27. So the difference between signals 104 and 102 lies in the range (272.sup.16,272.sup.16). Moreover the lsbs of signal 104 on any sample are known to the decoder from the defined quantisation grid G.sub.3. Thus, only 6 bits of restart assistance data per sample are needed (this is quite a conservative bound and fewer will often suffice).

(59) Startup operation for filter 222 is illustrated in FIG. 7. In contrast to normal operation, the output from filter 222 is ignored. Rather quantiser 431 generates 204 by quantising 202 to a coarse subset of the 15.5 bit quantisation with offset O.sub.3 as discussed below. With the correct value for signal 204 computed, we have the correct input for filter 222 and after n samples later filter 222 has correct state and we can revert to normal operation.

(60) In our example, quantiser 431 is a 10 bit lattice quantiser and the offset is given by the sum of 6 bits of restart assistance data scaled by 2.sup.16 and the output of PRNG 312 (or 313 for the other channel). PRNG 312 ensures that signal 204 has the correct offset O.sub.3 compared to a 15.5 bit quantisation and the restart assistance selects the correct value nearby to the input signal 202.

(61) The encode side of this would ideally requires that bits 11 to 16 of signal 104 are pushed to the restart assistance. However, the PRNG value ranged up to 2.sup.15, so there is one bit of overlap between the PRNG and the assistance. Since the decoder adds the values, the encoder must subtract the top bit of the PRNG output from the lsb end of bits 11 to 16 of signal 104 to generate the restart assistance. Filter 221 can be initialised in a similar manner.

(62) Filtering

(63) As discussed in WO2013061062, it can be useful to precede such a histogram altering lossless watermarker with pre-emphasis filtering. There it was done as an entirely separate preprocess, which of necessity involves requantisation back to the 16 bit level.

(64) According to a further embodiment of the invention, the encoder is preceded by a filter with unity first impulse response and whose output is quantised to a finer precision than 16 bits, say 24 bits.

(65) A generalised form of such a filter is shown in FIG. 8A. A function 520 is computed of n delayed values of the filter input 501 and output 503 and the result quantised 530 to produce signal 502, whose value at any instant we will call A (for adjustment). The filter output 503 is formed by adding signal 502 to signal 501. If the quantiser 530 were to quantise to the 16 bit precision that the encoder operates on, then this is not materially different to the lossless preemphasis filter in WO2013061062. However, the quantiser 530 is then an extra source of unshaped 16 bit noise which is undesirable.

(66) Surprisingly however, the filter-encoder combination is still invertible even if the quantiser 530 quantises to finer precision, for example 24 bits. Now the noise introduced by quantiser 530 is far lower and does not make a material contribution to the overall noise introduced by the invention.

(67) Signal 501 is quantised to a 16 bit lattice with offset O.sub.1, and A is a function of previous samples. Despite A being higher precision, signal 503 can thus be said to be quantised to a 16 bit quantisation grid (O.sub.1+A). This does not affect subsequent encoder operation (since the operation of ambiguity resolver 113 only depends on the input using a 16 bit lattice, not the quantisation offset), but it does affect decoder operation.

(68) Decoder operation is shown in FIG. 8B which shows modifications to the left hand side of the decoder shown in FIG. 1B. Assuming previous lossless operation, the decoder can compute the same function 521 of the replicated previous samples as the encoder and perform the same quantisation 531 to produce signal 512 whose value is also A, replicating signal 502.

(69) However, it does not subtract A from the output of quantiser 211, since this would alter the quantisation offset. Instead it subtracts A before quantiser 211. The output of quantiser 211 is thus the filtered signal, quantised with offset O.sub.1 as required for signal 511 to replicate signal 501 and serve as the decoder output and one of the inputs into function 521.

(70) A is then added which gives a signal with quantisation offset (O.sub.1+A) replicating signal 503 which is exactly as required for the other input into function 501 and the subtraction node feeding noise shaping filter 221. For interest, we point out that the dashed box 214 forms a 16 bit quantiser with quantisation offset (O.sub.1+A).

(71) As with the noise shaping though, the above logic fails when starting decoder operation in the middle of a track and restart assistance data is required to bootstrap lossless operation. Most simply, the restart assistance could comprise a snapshot of the correct filter state but if restart points are frequent then this could be an inconveniently large amount of data.

(72) We now explain how the amount of restart assistance data can be substantially reduced. We make the following preliminary observations: The feedback of signal 512 to quantiser 214 means that the quantiser and filter need bootstrapping as a combined unit. There is no point initialising 214's noise shaping if we don't also bootstrap the filter because wrong values of signal 512 cause quantiser 214 to quantise to the wrong grid and so not operate in a lossless manner. This is a key difference from the preemphasis in WO2013061062 which was not integrated into the quantiser. As with the noise shaping, if signal 513 and 511 are correct for n samples, then signal 512 will be correct and lossless operation will follow if quantiser 214's noise shaping is also correct. Signal 513 is also the signal that needs to be correct to bootstrap the noise shaping.

(73) Signal 513 is close to signal 206, differing only by the noise shaped alteration introduced by quantiser 214. However, signal 511 is a filtered version of 513 and substantially different.

(74) If the decoder is started at an arbitrary point within a stream, it will in general not immediately see a restart point at which restart assistance data is provided, and will run in a lossy mode initially, as shown in FIG. 9. FIG. 9 is derived from FIG. 8B by eliminating the noise shaped quantisation 214, subtracting the adjustment A and finally quantising the result so the output conforms to being 16 bit with offset O.sub.1, even though it does not replicate signal 501 provided to the encoder.

(75) We operate in this lossy mode for sufficient time to allow signal 511 to converge towards the correct value it would have in lossless operation. How long this needs to be is related to the length of the impulse response of the filter, which is in general IIR because of the feedback path round the function 521 and quantiser 531. But there is a limit to how close signal 511 will converge, set by its input being inaccurate because quantiser 214 isn't operational in lossy mode. Restart assistance is needed at the restart point to snap approximate delayed values of 511 and 513 to the correct values.

(76) As in the previously discussed case of initialising just the noise shaping, the restart information can be verbatim bits of the lossless signals. For signal 511, the bits below 16 are defined by quantisation offset O.sub.1, so each delayed datum needs some number of lsbs from the 16.sup.th bit upwards specifying, with the number depending on how much error there may be in the approximate signal 511. Eight bits is likely to suffice if the IIR filter comprising function 521 and quantiser 531 has had adequate time to settle and does not have too extreme a response. For signal 513 we need more bits than in the noise-shaping-only case because the signal is quantised on a grid (O.sub.1+A) and we don't know A accurately. So, if 6 bits would have sufficed for the noise shaper and A is quantised to 24 bits, we now need 14 bits per datum, conveying the 11-24.sup.th bits of the lossless signal.

(77) Sprinkler

(78) FIG. 10 shows another embodiment of the invention, where a losslessly watermarked audio file 202 has its watermark altered to produce a different losslessly watermarked audio file 102.

(79) This is done by using the initial part of the decoder from FIG. 1B to regenerate the internal signal 204 quantised to grid G.sub.3, which then passes into the latter part of the encoder from FIG. 1A to embed altered data 143. Only the watermark part of data 143 is altered, reconstruction data and restart assistance pass unchanged.