System and method of retrieving a watermark within a signal

• US 7,529,941 B1
• Filed: 09/12/2006
• Issued: 05/05/2009
• Est. Priority Date: 06/04/2001
• Status: Expired due to Term

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Johnston, James David, Kuo, Shyh-Shiaw, Turin, William, Quackenbush, Schuyler Reynier
• Primary Examiner(s): Colin; Carl
• Assistant Examiner(s): Shiferaw; Eleni A
• Application Number:
  US11/531,083
• Time in Patent Office: 966 Days
• Field of Search: 380/200, 380/216, 380/218, 380/221, 380/237, 380/238, 380/250, 380/252, 283/113, 704/203, 704/500
• US Class Current: 713/176
• CPC Class Codes: G10L 19/018 Audio watermarking, i.e. embedding inaudible data in the audio signal

Abstract

A system and method of retrieving a watermark in a watermarked signal are disclosed. The watermarked signal comprises odd and even overlapped blocks where the watermark is contained in the even blocks. The method comprises, for each k-th even block, subtracting the two adjacent odd numbered blocks from the k-th even block of the watermarked signal to retrieve s*_k(n), transforming s*_k(n) into the frequency domain to generate S_k(f), calculating a phase of S_k(f) as φ(f) and a phase of S_k(f) as φ(f), calculating the difference Ψ(f) between φ(f) and φ(f), unwrapping Ψ(f) to obtain the phase modulation {tilde over (φ)}_k(f), and using a Viterbi search to retrieve the watermark embedded in {tilde over (Φ)}_k(f).

Claims

1. A computing device for retrieving a watermark in a watermarked signal, the watermarked signal comprising odd and even overlapped blocks where the watermark is contained in even blocks, the computing device comprising:

a processor;

a module configured to control the processor to subtract odd blocks from a k-th block of the watermarked signal to generate a first signal;

a module configured to control the processor to apply a Fast Fourier Transform (FFT) to the first signal to generate a phase S_k(f);

a module configured to control the processor to calculate a phase of S_k(f) as φ

(f) and a phase of an original signal S_k(f) as φ

(f);

a module configured to control the processor to calculate the difference Ψ

(f) between φ

(f) and φ

(f); and

a module configured to control the processor to use a Viterbi search to retrieve the watermark embedded in Ψ

(f), wherein if during a phase-modulation stage of generating the watermarked signal, the result of adding a phase-modulation to the phase of the original signal has an absolute value greater than π

, then the computing device further;

unwraps Ψ

(f) to obtain a correct phase modulation {tilde over (Φ

)}_k(f) only when φ

(f)>

π

/2 and Ψ

(f) is greater than a dynamic range of the phase modulation; and

uses the Viterbi search to retrieve the watermark embedded in {tilde over (Φ

)}_k(f).

2. A computing device of claim 1, wherein odd blocks subtracted from the k-th even block are the two adjacent odd blocks of the original signal to the k-th even block.

3. A computing device of claim 1, wherein the watermarked signal is an audio signal.

4. A tangible computer-readable medium storing instructions for controlling a computing device to perform steps to retrieve a watermark embedded in a watermarked signal, the watermarked signal comprising odd and even overlapped blocks where the watermark is contained in even blocks and wherein the absolute value of adding a phase modulation Φ

_k(f) to a phase of an original signal in a phase-modulation step of generating the watermarked signal is greater than π

, the steps comprising, for each k-th block of the watermarked signal;

subtracting odd blocks from a k-th block to generate a first signal;

applying a Fast Fourier Transform (FFT) to the first signal to generate a phase S_k(f);

calculating a phase of S_k(f) as φ

(f) and a phase of an original signal S_k(f) as φ

(f);

calculating the difference Ψ

(f) between φ

(f) and φ

(f);

unwrapping Ψ

(f) to generate {tilde over (Φ

)}_k(f), which contains the embedded watermark, wherein the uwrapping only occurs when φ

(f)>

π

/2 and Ψ

(f) is greater than a dynamic range of a phase modulation.

5. The tangible computer-readable medium of claim 4, the steps further comprising:

using a Viterbi search to retrieve the watermark embedded in {tilde over (Φ

)}_k(f).

6. A tangible computer-readable medium storing instructions for controlling a computing device to perform steps to retrieve a watermark embedded in a watermarked signal, the steps using the phase S_k(f) of an original signal, the watermarked signal comprising odd and even overlapped blocks where the watermark is contained in even blocks, the steps comprising, for each k-th even block:

(a) subtracting two adjacent odd blocks from a k-th even block of the watermarked signal to retrieve a first signal;

(b) transforming the first signal into a frequency domain to generate S_k(f);

(c) calculating a phase of S_k(f) as φ

(f) and a phase of S_k(f) as φ

(f);

(d) calculating the difference Ψ

(f) between φ

(f) and φ

(f);

(e) unwrapping Ψ

(f) to obtain a phase modulation {tilde over (Φ

)}_k(f) only if, during the phase-modulation step of generating the watermarked signal, the absolute value of the result of adding a phase modulation Φ

_k(f) to a phase of the original signal is greater than π

, when φ

(f)>

π

/2 and when Ψ

(f) is greater than the dynamic range of the phase modulation; and

(f) using a Viterbi search to retrieve the watermark embedded in {tilde over (Φ

)}_k(f).

7. The tangible computer readable medium of claim 6, wherein the watermarked signal is an audio signal.

8. A tangible computer readable medium storing instructions for controlling a computing device to perform steps to retrieve a watermark embedded in a watermarked signal, the steps using the phase S_k(f) of an original signal, the watermarked signal comprising odd and even overlapped blocks where the watermark is contained in even blocks, the steps comprising, for each k-th even block:

obtaining a phase modulation {tilde over (Φ

)}_k(f) within a k-th even block; and

performing a Viterbi search using an energy-weighted mean absolute error L₁ norm to retrieve the watermark embedded in {tilde over (Φ

)}_k(f), wherein the steps further comprise using the following cost function associated with the L₁ norm when performing the Viterbi search;

$c_{\mathrm{ij}}<br><br>\left(t\right)=\frac{1}{K}<br><br>\underset{f=0}{\overset{K-1}{\sum <br><br>}}<br><br><br><br>\underset{c}{\sum <br><br>}<br><br>\left(p_{\mathrm{ij}}<br><br>\left(f\right)-o_t<br><br>\left(f\right)\right)<br><br>w_t<br><br>\left(f\right)<br><br>,\mathrm{for}<br><br><br><br>\left(\begin{array}{cc}0\le <br><br>i,& j\le <br><br>1\\ 1\le <br><br>t\le <br><br>T,& \end{array}\right),$

where p_ij(f) is the path template between state i and j, K is the total number of frequency bins associated with the observation o_t, and w_t(f) are the weights which are based on spectrum energy.

9. The tangible computer readable medium of claim 8, wherein w_f(f) are the weights that are defined as:

$w_t<br><br>\left(f\right)=\min <br><br>\left({<br><br>S^{\mathrm{\prime <br><br>}}<br><br>\left(f\right)<br><br>}^2,{<br><br>{\stackrel{\_}{S}}_c^{\mathrm{\prime <br><br>}}<br><br>\left(f\right)<br><br>}^2\right),\mathrm{for}<br><br><br><br>f=0,\mathrm{\dots <br><br>}<br><br>,K-1$ $\underset{f}{\sum <br><br>}<br><br>w_t<br><br>\left(f\right)=1.$

10. The tangible computer readable medium of claim 8, wherein the signal is a multi-channel signal.

11. The tangible computer readable medium of claim 10, further comprising:

using the following cost function and spectrum energy weights associated with the L₁ norm when performing the Viterbi search;

$c_{\mathrm{ij}}<br><br>\left(t\right)=\frac{1}{K}<br><br>\underset{f=0}{\overset{K-1}{\sum <br><br>}}<br><br><br><br>\underset{c}{\sum <br><br>}<br><br>\left(p_{\mathrm{ij}}<br><br>\left(f\right)-o_{t,c}<br><br>\left(f\right)\right)<br><br>w_{t,c}<br><br>\left(f\right)<br><br>,<br><br>\mathrm{for}<br><br><br><br>\left(\begin{array}{cc}0\le <br><br>i,& j\le <br><br>1\\ 1\le <br><br>t\le <br><br>T,& \end{array}\right)$ $w_{\mathrm{tc}}<br><br>\left(f\right)=\min <br><br>\left({<br><br>S_c^{\mathrm{\prime <br><br>}}<br><br>\left(f\right)<br><br>}^2,{<br><br>{\stackrel{\_}{S}}_c^{\mathrm{\prime <br><br>}}<br><br>\left(f\right)<br><br>}^2\right),<br><br>\mathrm{for}<br><br><br><br>\left(\begin{array}{ccc}f=0,& \mathrm{\dots <br><br>}& K-1\\ c=1,& \mathrm{\dots <br><br>}& M<br><br>\left(\mathrm{Totalchannels}\right)\end{array}\right)$ $\underset{f}{\sum <br><br>}<br><br>\underset{c}{\sum <br><br>}<br><br>w_{t,c}<br><br>\left(f\right)=1.$

12. The tangible computer readable medium of claim 10, the steps further comprising:

(a) initializing parameters C₁(i)=c_ii, i=0, 1 and γ

_t(i)=0;

(b) using recursion to calculate;

$C_t<br><br>\left(j\right)=\underset{i=1,2}{\min }<br><br>\left[C_{t-1}<br><br>\left(i\right)+c_{\mathrm{ij}}<br><br>\left(t\right)\right],2\le <br><br>t\le <br><br>T,j=-0,2\le <br><br>t\le <br><br>T,j=-0,1$ $<br><br>{\mathrm{\gamma <br><br>}}_t<br><br>\left(j\right)=\arg <br><br><br><br>\underset{i=1,2}{\min }<br><br>\left[C_{t-1}<br><br>\left(i\right)+c_{\mathrm{ij}}<br><br>\left(t\right)\right],2\le <br><br>t\le <br><br>T,j=-0,2\le <br><br>t\le <br><br>T$

(c) using the following calculations to determine the minimum total cost associated with a best state sequence q;

$C^{*}=\underset{i=0,1}{\min }<br><br>\left[C_T<br><br>\left(i\right)\right]$ $q_T=\arg <br><br><br><br>\underset{i=0,1}{\min }<br><br>\left[C_T<br><br>\left(i\right)\right];<br><br>\mathrm{and}$

(d) state sequence backtracking to calculate;

q_t=γ

_t+1(q_t+1), t=T−

1, T−

2, . . . , 1.

13. The tangible computer readable medium of claim 8, the steps further comprising:

(a) initializing parameters C₁(i)=c_ii, i=0, 1 and γ

_t(i)=0;

(b) using recursion to calculate;

$C_t<br><br>\left(j\right)=\underset{i=1,2}{\min }<br><br>\left[C_{t-1}<br><br>\left(i\right)+c_{\mathrm{ij}}<br><br>\left(t\right)\right],2\le <br><br>t\le <br><br>T,j=-0,2\le <br><br>t\le <br><br>T,j=-0,1$ $<br><br>{\mathrm{\gamma <br><br>}}_t<br><br>\left(j\right)=\arg <br><br><br><br>\underset{i=1,2}{\min }<br><br>\left[C_{t-1}<br><br>\left(i\right)+c_{\mathrm{ij}}<br><br>\left(t\right)\right],2\le <br><br>t\le <br><br>T,j=-0,2\le <br><br>t\le <br><br>T$

(c) using the following calculations to determine the minimum total cost associated with a best state sequence q;

$C^{*}=\underset{i=0,1}{\min }<br><br>\left[C_T<br><br>\left(i\right)\right]$ $q_T=\arg <br><br><br><br>\underset{i=0,1}{\min }<br><br>\left[C_T<br><br>\left(i\right)\right];<br><br>\mathrm{and}$

(d) using the following to calculate state sequence backtracking;

q_t=γ

_t+1(q_t+1), t=T−

1, T−

2, . . . , 1.

14. A method of retrieving a watermark in a watermarked signal, the watermarked signal comprising odd and even overlapped blocks, the method comprising:

if during a phase modulation stage of generating the watermarked signal, a result of adding a phase modulation to the phase of an original signal has an absolute value greater than π

, then unwrapping the watermarked signal to obtain a correct phase modulation only when a phase of the original signal is greater than π

/2 and a parameter is greater than a dynamic range of the phase modulation; and

using a Viterbi search to retrieve the watermark embedded in the correct phase modulation.

15. The method of claim 14, wherein the parameter represents a difference between phases.