# Audio Watermarking Scheme Based on Singular Spectrum Analysis and Psychoacoustic Model with Self-Synchronization

Authors: Jessada Karnjana; Masashi Unoki; Pakinee Aimmanee; Chai Wutiwiwatchai
Journal: Journal of Electrical and Computer Engineering
 (2016)

---

## Abstract

This paper proposes a blind, inaudible, and robust audio watermarking scheme based on singular spectrum analysis (SSA) and the psychoacoustic model 1 (ISO/IEC 11172-3). In this work, SSA is used to analyze the host signals and to extract the singular spectra. A watermark is embedded into the host signals by modifying the singular spectra which are in the convex part of the singular spectrum curve so that this part becomes concave. This modification certainly affects the inaudibility and robustness properties of the watermarking scheme. To satisfy both properties, the modified part of the singular spectrum is determined by a novel parameter selection method based on the psychoacoustic model. The test results showed that the proposed scheme achieves not only inaudibility and robustness but also blindness. In addition, this work showed that the extraction process of a variant of the proposed scheme can extract the watermark without assuming to know the frame positions in advance and without embedding additional synchronization code into the audio content.


---

## Body

## 1. Introduction

Since the last decade, music sharing via the Internet has caused the music industry to lose annual sales of more than 3 billion US dollars [1] because the Internet is a good distribution system; that is, it distributes audio signals widely and very rapidly. In addition, all digital products have special characteristics; that is, they are expensive to produce for the first copy, but cheap to reproduce for duplicates [2]. One potential solution for protecting the digital content is audio watermarking [3]. Also, audio watermarking has been proposed as a solution for other purposes, such as ownership protection, content authentication, broadcast monitoring, information carrier, and covert communication [4–8].The audio watermarking system consists of two processes: the embedding process and the extraction process, as illustrated in Figure1. The first process embeds the watermark into the host audio signal. The second process extracts the watermark from the watermarked signal. Normally, the embedding process is frame-based. Therefore, the extraction process requires the frame positions in order to extract the watermark. The frame position requirement raises the frame synchronization problem. This problem is to be discussed in great detail in Section 3. Audio watermarking systems can be characterized by a number of properties [4]. Among them, there are five important properties [3, 9].Figure 1
Audio watermarking system.(i) Inaudibility. It is the property that the watermark does not affect the perceptual quality of the host signal.(ii) Robustness. It is the ability to extract the watermark correctly when attacks are performed on the watermarked signals.(iii) Blindness. It is the ability to be independent of the host signal in the extraction process. The system is blind when the extraction process does not require the host signal to be compared, in order to correctly extract the watermark. If the extraction process requires the host signal, as illustrated by the dashed line in Figure 1, it is nonblind.(iv) Confidentiality. It is the property that keeps the watermark secret.(v) Capacity. It is the quantity of the hidden information that is embedded into the host signals.These required properties normally conflict with each other. Some techniques that obtain high robustness may suffer in inaudibility [10]. Some techniques are good at inaudibility but do not meet the blindness property [11]. Some with high capacity are not robust [12]. The method based on the least-significant-bit coding [13] obtains good inaudibility but loses on the robustness. The phase-coding method [14] achieves the inaudibility but fails the capacity. The phase modulation method [15] survives the inaudibility but does not pass the blindness property. The trade-off between the inaudibility and the robustness can be found in the methods based on adaptive phase modulation as well [16]. The method based on cochlear delay characteristics [17] is robust and inaudible. However, it has a significant trade-off between the inaudibility and the capacity. In addition, the blind cochlear-delay-based scheme reduces the sound quality of the watermarked signals, compared with nonblind ones. The methods based on echo hiding [18, 19] are blind and robust, but they perform poorly in inaudibility and confidentiality. The spread-spectrum-based technique is good in robustness but is poor in inaudibility and capacity [20]. These examples show that balancing among the required properties has always been a difficult task.A literature review of audio watermarking has suggested that the schemes based on Singular-Value Decomposition (SVD) are robust [10, 11, 21–26]. In general, the SVD-based scheme extracts the singular values from the host signals and slightly changes some of those values with respect to the watermark bit. It is robust because the singular values are unchanged under common signal processing [27]. However, the balance between inaudibility and robustness for some audio signals needs to be further improved due to the fact that it has never taken the human perception into consideration.The motivation for this work has started from the idea of exploiting the advantages of the SVD-based method and combining it with a human perceptual model. We turn to the SSA, which is SVD-based, and adopt it as the main analysis tool. We choose SSA because when a signal is analyzed, the singular values can be interpreted and have the physical meanings [28]. The physical meanings are of importance because they help us understand a relationship between the SSA and the perceptual model. Recently, we proposed the audio watermarking schemes based on the SSA [28, 29]. Also, we showed the benefits of using the SSA over the SVD. To verify the effectiveness of the SSA-based scheme, we used thedifferential evolution to adjust the balance. The results were quite successful [29]. However, as the search space was very large, therefore, the embedding process was time-consuming.This work aims to show that SSA equipped with the perceptual model also gives the good balance between inaudibility and robustness. This work proposes a novel audio watermarking based on SSA and the human perceptual model. Also, it proposes a new method for automatic frame detection; that is, the frame positions are not required in the extraction process.The rest of this paper is organized as follows. The proposed scheme and necessary background information are detailed in Section2. Section 3 shows that we can slightly modify the proposed scheme to make it a self-synchronized one. The performance evaluation and experimental results are given in Section 4. The observations from the experiments are made and discussed in Section 5. Last, the whole work is summarized in Section 6.


## 2. Proposed Scheme

The proposed scheme is mainly based on the SSA-based audio watermarking scheme proposed by Karnjana et al. [28, 29]. The first two subsections are part of the embedding process, and the last two subsections are part of the extraction process. The proposed scheme with the self-synchronization is provided in Section 3.


### 2.1. Embedding Process

The embedding process consists of two major parts, as shown in Figure2. The first part is a core structure. In this core structure, the basic SSA is mainly used to analyze the host signals and to extract the singular spectra. The basic SSA has experimentally proved to be useful for extracting meaningful information from signals [30, 31]. The second part, which is shown in the gray box, is the parameter selection method based on a psychoacoustic model. In this work, we adopt the psychoacoustic model 1 (ISO/IEC 11172-3) [32] to the proposed scheme. The brief details of the psychoacoustic model and the parameter selection method are provided in the next subsection.Figure 2
Embedding process.The core structure of the embedding process consists of six steps which are described as follows.(1)
The host audio signal is segmented into nonoverlapping frames. The number of frames is equal to the number of the watermark bits since one bit is embedded into one frame. LetF=f0f1f2⋯fN-1T denote a frame of size N, where N is greater than 2. Remark that the embedding capacity is the sampling frequency of the host signal divided by N.(2)
The trajectory matrixX which represents each frame F is constructed. The construction of X is done as follows:(1)X=f0f1f2⋯fK-1f1f2f3⋯fKf2f3f4⋯fK+1⋮⋮⋮⋱⋮fL-1fLfL+1⋯fN-1,whereL, called awindow length of the matrix formation, is the only parameter of the basic SSA and not greater than N, and K=N-L+1.(3)
SVD is performed on each trajectory matrixX to obtain the singular spectrum {λ0,λ1,…,λL-1}, where λ0,λ1,…, and λL-1 denote the eigenvalues of XXT.(4)
When the watermark bit is1, we modify singular values λi, for i=u+1,u+2,…,l-1, given that λu is greater than λl, as follows.(2)λi=λl+0.9×λu-λl.When the watermark bit is0, the singular values are left unchanged. In this step, there are two parameters, u and l, and these parameters are determined by the parameter selection algorithm based on the psychoacoustic model.(5)
The modified trajectory matrix is constructed by SVD reversion, and then it is hankelized. The hankelization of a modified trajectory matrixY to a signal G=g0g1g2⋯gN-1T is defined as follows:(3)gk=1k+1∑m=1k+1ym,k-m+2∗,for0≤k<L∗-1,1L∗∑m=1L∗ym,k-m+2∗,forL∗-1≤k<K∗,1N-k∑m=k-K∗+2N-K∗+1ym,k-m+2∗,forK∗≤k<N, whereyij is an element at the row i and column j of the matrix Y, L∗=min⁡(L,K), K∗=max⁡(L,K), yij∗=yij if L<K, and yij∗=yji if L≥K. (6)
Finally, the watermarked signal is reconstructed by stacking those hankelized frames.


### 2.2. Parameter Selection Based on Psychoacoustic Model

The block diagram of the parameter selection method based on the psychoacoustic model1 is shown in the gray box of Figure 2. The psychoacoustic model 1, which is deployed in the MPEG-1 Layer 1, is adopted in order to deliver a signal-to-mask ratio (SMR) of the analyzed signal, and then the SMR is used as a criterion for selecting the parameters u and l.Basically, the psychoacoustic model1 is built based on three psychoacoustic principles: the absolute threshold of hearing, the simultaneous masking, and the upward spread of masking [33]. It consists of five steps [33, 34], as shown in Figure 3. According to the standard ISO/IEC: 11172-3, the overview of the process is summarized as follows. First, the FFT and the power spectral density (PSD) of the signal are calculated, and then the PSD is normalized with the maximum sound pressure level (SPL) of 96 dB. Next, the PSD is used to identify the tonal (more sinusoid-like) and nontonal (more noise-like) components of the signal. This identification is used for the calculation of the masking levels due to the tonal and nontonal maskers. Then, the irrelevant maskers are removed by applying two psychoacoustic principles in the following manner. The maskers which are lower than the absolute threshold of hearing are removed, and only the strongest masker within a distance of 0.5 Bark is kept. Subsequently, these survival maskers are used to calculate the individual masking levels. Finally, we combine all masking levels to calculate the global masking level. The output of the psychoacoustic model is SMR. The SMR is defined as the difference between the SPL of the global masking level and the PSD of the analyzed signal. Figure 4 shows an example of the SMR (red line) of one frame.Figure 3
Psychoacoustic model1.Figure 4
Signal PSD, global masking level, and SMR.In perceptual audio codings, such as MP3 compression, the SMR is used to allocate the quantization bits. The frequency components with the lower SMR are assigned with smaller numbers of bits since the human auditory system is less sensitive to those frequency components. In this work, the SMR is used as guidance to determine the appropriate parameters because embedding the watermark into the components with the low SMRs helps to improve the inaudibility. The algorithm that we use to deliver the parametersu and l consists of the following five steps:(1)
We first calculate the SMR of each frame. According to the standard, the frame size used for this calculation is512 samples. Note that the frame size from the segmentation of the core structure is not necessary to be the same as that of this psychoacoustic model.(2)
We use the SMRs obtained from the previous step to calculate the average SMR of the host signal.(3)
We identify the frequency band[f1,f2] with the average SMR lower than a predefined value, γ. If there are more than one band, the band with the lowest frequency is selected. If the frequency bandwidth f2-f1 is wider than a predefined bandwidth, it is limited to the predefined bandwidth. In our simulation, the predefined bandwidth is 10kHz. An example is shown in Figure 5.(4)
For each frame, we map the selected band to a singular-value interval. In this step, we have to find the relationship between the frequencies and the singular-value indices because the output of the psychoacoustic model, the SMR, is expressed as a function of frequency. When the basic SSA is used to decompose a signal, the singular values of the matrix representing the signal can be interpreted as the scale factors of the oscillatory components of the signal [28]. After analyzing each oscillatory component by the Fourier transform, we found that a frequency band of each oscillatory component is quite narrow compared with the signal bandwidth, as shown in Figure 6. We associate the index of the singular value with the peak frequency of its oscillatory components. Figure 7 shows an example of the relationship between the frequencies and the singular-value indices. Thus, to map the frequency range [f1,f2] to the interval [u,l], we first find the local minimum which is closest to f1, and set u the index of this local minimum. Then, we find the local maximum that is closest to f2 which must be on the right side of u, and then set l the index of this local maximum. An example of this mapping is shown in Figure 8. Note that different frames may have different intervals from one another, and the wordframe in this step means the frame from the segmentation process.(5)
Finally, the parametersu and l for embedding the watermark are selected using the arithmetic mean of boundaries of all intervals.Figure 5
Average SMR (red) and an example of selecting the frequency band[f1,f2] given the SMR criterion γ=18dB. If the frequency bandwidth f2-f1 is wider than 10 kHz, it is limited to 10 kHz.Figure 6
Examples of spectra of oscillatory components: the top-left panel is a spectrum of an audio signal, and the other panels show spectral of some oscillatory components. The numbers labeled on vertical axes are the orders of the components, which are indices of their associated singular values. Compared with the spectrum of the audio signal, the spectral of oscillatory components has narrower bandwidths.Figure 7
Relationship between frequency and singular-value index (frame size,N=1024).Figure 8
Example of parameter selection: frequency range[f1,f2] is mapped to the interval [u,l].


### 2.3. Extraction Process

The plot of singular spectra is normally convex, as shown in Figure9. However, after the watermark bit 1 is embedded into an interval [u+1,l-1] of the singular spectrum of a host frame, the embedding process causes the concave part on the interval [u+1,l-1] of the singular spectrum of the reconstructed, watermarked frame [29], as shown in Figure 10. We exploit this property to extract the watermark bit. The extraction process consists of five steps, as shown in Figure 11. The details of each step are as follows.(1)
We segment the watermarked signal into nonoverlapping frames. At this stage, we assume that we know the frame positions and the frame size.(2)
We construct the trajectory matrix in the same way we do in the embedding process.(3)
We perform the SVD operation on the trajectory matrix to obtain the singular spectrum.(4)
If the parametersu and l are not provided, automatic parameter estimation, which is illustrated in the gray box of Figure 11, is used to estimate them. The details of this parameter estimation are given in the upcoming subsection.(5)
We approximate all singular values of[u+1,l-1] using the quadratic equation, y(x)=ax2+bx+c, where y is the singular value and x is the index of the singular value. Since the coefficient a of the quadratic formula indicates the rate of change of the singular values, the sign of the coefficient a is used to determine the watermark bit. A minus sign indicates concavity or the watermark bit 1, and a plus sign indicates convexity or the watermark bit 0.Figure 9
Singular spectrum.Figure 10
Singular spectrum with a concave part due to embedding watermark bit1.Figure 11
Extraction process.


### 2.4. Automatic Parameter Estimation

To automatically estimate the parametersu and l, we use the fact that when watermark bit 1 is embedded into a frame, there exists a concave part in the singular spectrum plot. In other words, when watermark bit 1 is embedded into the frame, we can find some pairs of indices m and n, where m<n, such that the singular values of the interval [m,n] are mostly above the line segment connecting two singular values λm and λn. Thus, this automatic parameter estimation estimates the parameters from the width of the concave part.We first define the concavity density as a measurement of degree of the concavity. Given a singular spectrumλ1,λ2,…,λd, the concavity density Dm,n of singular values from λm to λn is defined as follows.(4)Dm,n=∑i=m+1n-1λi-Li,Li=λm+λm-λnm-ni-m,where L(i) is the function defining the line connecting λm and λn.Starting from the first singular value (m=1), a sequence of the singular values that is used to calculate the concavity density is shifted to the right by one singular-value point at a time to determine the set of the concavity density D1,n,D2,n+1,…,Di,n+i-1,…,Dd-n+1,d. An example of the positive and the negative concavity density of two sequences of the singular values is shown in Figure 12.Figure 12
Examples of regions with negative and positive concavity density.Figure13 shows an example of the concavity density curve of the singular spectrum in Figure 12 when a sequence of the singular values used to calculate the concavity density has a length of 30. It can be seen that the positive density roughly corresponds to the concave part of the singular spectrum. However, the concavity density depends upon the choice of the length of the sequence used to calculate the concavity density. In this work, we get around the problem by using the average density at the different lengths. Then, the average-density curve is refined as follows. First, any negative-density value is ignored because it implies convexity. Second, any positive density curve that is narrower than Γ×(l-u), where Γ is a user-defined real number around 1, is neglected because, practically, we can set the minimum value of l-u in advance.Figure 13
Concavity density set{D1,31,D2,32,…,D100,130}. Notice that there is a strong relationship between the region of positive density and the indices of modified singular values.Subsequently, the indices at the rising and falling edges of the consequent density curve, together with an offsetting constant, are used to estimate the parametersu and l for the given frame. Finally, the parameters u and l for the watermarked signal are calculated by averaging the estimated parameters u and l from all frames. The averaging algorithm is depicted in Figure 14 and detailed as follows.Figure 14
Averaging algorithm used in the automatic parameter estimation.Letu^i,j and l^i,j for j=1,2,…,ki denote the estimated parameters of the frame i. The subscripts j indicate that there can be more than one concave interval detected within one frame. The maximum number of intervals detected within the frame i is denoted by ki.The general idea of the averaging algorithm is as follows. Given two integral intervals[μ1,ι1] and [μ2,ι2], where μ1, ι1, μ2, and ι2 are integers and ι1-μ1≤ι2-μ2, we say that there is an overlap between those two intervals if μ2<ι1≤ι2 or μ2≤μ1<ι2. For a pair of overlapping intervals, μ1,ι1,μ2,ι2, we define the overlap degree η as(5)η=max⁡ι1,ι2-min⁡μ1,μ2min⁡ι2-μ1,ι1-μ2,where max⁡(·) and min⁡(·) are the maximum and minimum functions, respectively.Given a setE of the estimated parameter-interval [u^i,j,l^i,j], we can expect that the set E must contain many overlapping intervals u^i,j,l^i,j. By the same token, we know that there is no overlap between intervals u^i,j1,l^i,j1 and u^i,j2,l^i,j2 when j1≠j2. Then, the averaging algorithm is just the process of recursively grouping the overlapping members of the set E. The following is the procedure used in the averaging algorithm.(1)
We assign the frequency weight to each intervalu^i,j2,l^i,j2 in the set E. Initially, the frequency weight is set to 1.(2)
We calculate the overlap degreeη of a pair of estimated parameter-intervals. If η is greater than a predefined value η∗, the two intervals are merged to create a new interval. Then, the two old intervals are removed. The frequency weight of the new interval is the sum of the frequency weights of the two old intervals. The average of the lower bounds and that of the upper bounds of the old intervals are used for the new interval.(3)
Step (2) is repeated until set E has no overlapping members.(4)
The interval with the highest frequency is chosen as the estimated parametersu^ and l^. If there are multiple intervals with the highest frequency, the estimated parameters u^ and l^ are randomly chosen from them.


## 2.1. Embedding Process

The embedding process consists of two major parts, as shown in Figure2. The first part is a core structure. In this core structure, the basic SSA is mainly used to analyze the host signals and to extract the singular spectra. The basic SSA has experimentally proved to be useful for extracting meaningful information from signals [30, 31]. The second part, which is shown in the gray box, is the parameter selection method based on a psychoacoustic model. In this work, we adopt the psychoacoustic model 1 (ISO/IEC 11172-3) [32] to the proposed scheme. The brief details of the psychoacoustic model and the parameter selection method are provided in the next subsection.Figure 2
Embedding process.The core structure of the embedding process consists of six steps which are described as follows.(1)
The host audio signal is segmented into nonoverlapping frames. The number of frames is equal to the number of the watermark bits since one bit is embedded into one frame. LetF=f0f1f2⋯fN-1T denote a frame of size N, where N is greater than 2. Remark that the embedding capacity is the sampling frequency of the host signal divided by N.(2)
The trajectory matrixX which represents each frame F is constructed. The construction of X is done as follows:(1)X=f0f1f2⋯fK-1f1f2f3⋯fKf2f3f4⋯fK+1⋮⋮⋮⋱⋮fL-1fLfL+1⋯fN-1,whereL, called awindow length of the matrix formation, is the only parameter of the basic SSA and not greater than N, and K=N-L+1.(3)
SVD is performed on each trajectory matrixX to obtain the singular spectrum {λ0,λ1,…,λL-1}, where λ0,λ1,…, and λL-1 denote the eigenvalues of XXT.(4)
When the watermark bit is1, we modify singular values λi, for i=u+1,u+2,…,l-1, given that λu is greater than λl, as follows.(2)λi=λl+0.9×λu-λl.When the watermark bit is0, the singular values are left unchanged. In this step, there are two parameters, u and l, and these parameters are determined by the parameter selection algorithm based on the psychoacoustic model.(5)
The modified trajectory matrix is constructed by SVD reversion, and then it is hankelized. The hankelization of a modified trajectory matrixY to a signal G=g0g1g2⋯gN-1T is defined as follows:(3)gk=1k+1∑m=1k+1ym,k-m+2∗,for0≤k<L∗-1,1L∗∑m=1L∗ym,k-m+2∗,forL∗-1≤k<K∗,1N-k∑m=k-K∗+2N-K∗+1ym,k-m+2∗,forK∗≤k<N, whereyij is an element at the row i and column j of the matrix Y, L∗=min⁡(L,K), K∗=max⁡(L,K), yij∗=yij if L<K, and yij∗=yji if L≥K. (6)
Finally, the watermarked signal is reconstructed by stacking those hankelized frames.


## 2.2. Parameter Selection Based on Psychoacoustic Model

The block diagram of the parameter selection method based on the psychoacoustic model1 is shown in the gray box of Figure 2. The psychoacoustic model 1, which is deployed in the MPEG-1 Layer 1, is adopted in order to deliver a signal-to-mask ratio (SMR) of the analyzed signal, and then the SMR is used as a criterion for selecting the parameters u and l.Basically, the psychoacoustic model1 is built based on three psychoacoustic principles: the absolute threshold of hearing, the simultaneous masking, and the upward spread of masking [33]. It consists of five steps [33, 34], as shown in Figure 3. According to the standard ISO/IEC: 11172-3, the overview of the process is summarized as follows. First, the FFT and the power spectral density (PSD) of the signal are calculated, and then the PSD is normalized with the maximum sound pressure level (SPL) of 96 dB. Next, the PSD is used to identify the tonal (more sinusoid-like) and nontonal (more noise-like) components of the signal. This identification is used for the calculation of the masking levels due to the tonal and nontonal maskers. Then, the irrelevant maskers are removed by applying two psychoacoustic principles in the following manner. The maskers which are lower than the absolute threshold of hearing are removed, and only the strongest masker within a distance of 0.5 Bark is kept. Subsequently, these survival maskers are used to calculate the individual masking levels. Finally, we combine all masking levels to calculate the global masking level. The output of the psychoacoustic model is SMR. The SMR is defined as the difference between the SPL of the global masking level and the PSD of the analyzed signal. Figure 4 shows an example of the SMR (red line) of one frame.Figure 3
Psychoacoustic model1.Figure 4
Signal PSD, global masking level, and SMR.In perceptual audio codings, such as MP3 compression, the SMR is used to allocate the quantization bits. The frequency components with the lower SMR are assigned with smaller numbers of bits since the human auditory system is less sensitive to those frequency components. In this work, the SMR is used as guidance to determine the appropriate parameters because embedding the watermark into the components with the low SMRs helps to improve the inaudibility. The algorithm that we use to deliver the parametersu and l consists of the following five steps:(1)
We first calculate the SMR of each frame. According to the standard, the frame size used for this calculation is512 samples. Note that the frame size from the segmentation of the core structure is not necessary to be the same as that of this psychoacoustic model.(2)
We use the SMRs obtained from the previous step to calculate the average SMR of the host signal.(3)
We identify the frequency band[f1,f2] with the average SMR lower than a predefined value, γ. If there are more than one band, the band with the lowest frequency is selected. If the frequency bandwidth f2-f1 is wider than a predefined bandwidth, it is limited to the predefined bandwidth. In our simulation, the predefined bandwidth is 10kHz. An example is shown in Figure 5.(4)
For each frame, we map the selected band to a singular-value interval. In this step, we have to find the relationship between the frequencies and the singular-value indices because the output of the psychoacoustic model, the SMR, is expressed as a function of frequency. When the basic SSA is used to decompose a signal, the singular values of the matrix representing the signal can be interpreted as the scale factors of the oscillatory components of the signal [28]. After analyzing each oscillatory component by the Fourier transform, we found that a frequency band of each oscillatory component is quite narrow compared with the signal bandwidth, as shown in Figure 6. We associate the index of the singular value with the peak frequency of its oscillatory components. Figure 7 shows an example of the relationship between the frequencies and the singular-value indices. Thus, to map the frequency range [f1,f2] to the interval [u,l], we first find the local minimum which is closest to f1, and set u the index of this local minimum. Then, we find the local maximum that is closest to f2 which must be on the right side of u, and then set l the index of this local maximum. An example of this mapping is shown in Figure 8. Note that different frames may have different intervals from one another, and the wordframe in this step means the frame from the segmentation process.(5)
Finally, the parametersu and l for embedding the watermark are selected using the arithmetic mean of boundaries of all intervals.Figure 5
Average SMR (red) and an example of selecting the frequency band[f1,f2] given the SMR criterion γ=18dB. If the frequency bandwidth f2-f1 is wider than 10 kHz, it is limited to 10 kHz.Figure 6
Examples of spectra of oscillatory components: the top-left panel is a spectrum of an audio signal, and the other panels show spectral of some oscillatory components. The numbers labeled on vertical axes are the orders of the components, which are indices of their associated singular values. Compared with the spectrum of the audio signal, the spectral of oscillatory components has narrower bandwidths.Figure 7
Relationship between frequency and singular-value index (frame size,N=1024).Figure 8
Example of parameter selection: frequency range[f1,f2] is mapped to the interval [u,l].


## 2.3. Extraction Process

The plot of singular spectra is normally convex, as shown in Figure9. However, after the watermark bit 1 is embedded into an interval [u+1,l-1] of the singular spectrum of a host frame, the embedding process causes the concave part on the interval [u+1,l-1] of the singular spectrum of the reconstructed, watermarked frame [29], as shown in Figure 10. We exploit this property to extract the watermark bit. The extraction process consists of five steps, as shown in Figure 11. The details of each step are as follows.(1)
We segment the watermarked signal into nonoverlapping frames. At this stage, we assume that we know the frame positions and the frame size.(2)
We construct the trajectory matrix in the same way we do in the embedding process.(3)
We perform the SVD operation on the trajectory matrix to obtain the singular spectrum.(4)
If the parametersu and l are not provided, automatic parameter estimation, which is illustrated in the gray box of Figure 11, is used to estimate them. The details of this parameter estimation are given in the upcoming subsection.(5)
We approximate all singular values of[u+1,l-1] using the quadratic equation, y(x)=ax2+bx+c, where y is the singular value and x is the index of the singular value. Since the coefficient a of the quadratic formula indicates the rate of change of the singular values, the sign of the coefficient a is used to determine the watermark bit. A minus sign indicates concavity or the watermark bit 1, and a plus sign indicates convexity or the watermark bit 0.Figure 9
Singular spectrum.Figure 10
Singular spectrum with a concave part due to embedding watermark bit1.Figure 11
Extraction process.


## 2.4. Automatic Parameter Estimation

To automatically estimate the parametersu and l, we use the fact that when watermark bit 1 is embedded into a frame, there exists a concave part in the singular spectrum plot. In other words, when watermark bit 1 is embedded into the frame, we can find some pairs of indices m and n, where m<n, such that the singular values of the interval [m,n] are mostly above the line segment connecting two singular values λm and λn. Thus, this automatic parameter estimation estimates the parameters from the width of the concave part.We first define the concavity density as a measurement of degree of the concavity. Given a singular spectrumλ1,λ2,…,λd, the concavity density Dm,n of singular values from λm to λn is defined as follows.(4)Dm,n=∑i=m+1n-1λi-Li,Li=λm+λm-λnm-ni-m,where L(i) is the function defining the line connecting λm and λn.Starting from the first singular value (m=1), a sequence of the singular values that is used to calculate the concavity density is shifted to the right by one singular-value point at a time to determine the set of the concavity density D1,n,D2,n+1,…,Di,n+i-1,…,Dd-n+1,d. An example of the positive and the negative concavity density of two sequences of the singular values is shown in Figure 12.Figure 12
Examples of regions with negative and positive concavity density.Figure13 shows an example of the concavity density curve of the singular spectrum in Figure 12 when a sequence of the singular values used to calculate the concavity density has a length of 30. It can be seen that the positive density roughly corresponds to the concave part of the singular spectrum. However, the concavity density depends upon the choice of the length of the sequence used to calculate the concavity density. In this work, we get around the problem by using the average density at the different lengths. Then, the average-density curve is refined as follows. First, any negative-density value is ignored because it implies convexity. Second, any positive density curve that is narrower than Γ×(l-u), where Γ is a user-defined real number around 1, is neglected because, practically, we can set the minimum value of l-u in advance.Figure 13
Concavity density set{D1,31,D2,32,…,D100,130}. Notice that there is a strong relationship between the region of positive density and the indices of modified singular values.Subsequently, the indices at the rising and falling edges of the consequent density curve, together with an offsetting constant, are used to estimate the parametersu and l for the given frame. Finally, the parameters u and l for the watermarked signal are calculated by averaging the estimated parameters u and l from all frames. The averaging algorithm is depicted in Figure 14 and detailed as follows.Figure 14
Averaging algorithm used in the automatic parameter estimation.Letu^i,j and l^i,j for j=1,2,…,ki denote the estimated parameters of the frame i. The subscripts j indicate that there can be more than one concave interval detected within one frame. The maximum number of intervals detected within the frame i is denoted by ki.The general idea of the averaging algorithm is as follows. Given two integral intervals[μ1,ι1] and [μ2,ι2], where μ1, ι1, μ2, and ι2 are integers and ι1-μ1≤ι2-μ2, we say that there is an overlap between those two intervals if μ2<ι1≤ι2 or μ2≤μ1<ι2. For a pair of overlapping intervals, μ1,ι1,μ2,ι2, we define the overlap degree η as(5)η=max⁡ι1,ι2-min⁡μ1,μ2min⁡ι2-μ1,ι1-μ2,where max⁡(·) and min⁡(·) are the maximum and minimum functions, respectively.Given a setE of the estimated parameter-interval [u^i,j,l^i,j], we can expect that the set E must contain many overlapping intervals u^i,j,l^i,j. By the same token, we know that there is no overlap between intervals u^i,j1,l^i,j1 and u^i,j2,l^i,j2 when j1≠j2. Then, the averaging algorithm is just the process of recursively grouping the overlapping members of the set E. The following is the procedure used in the averaging algorithm.(1)
We assign the frequency weight to each intervalu^i,j2,l^i,j2 in the set E. Initially, the frequency weight is set to 1.(2)
We calculate the overlap degreeη of a pair of estimated parameter-intervals. If η is greater than a predefined value η∗, the two intervals are merged to create a new interval. Then, the two old intervals are removed. The frequency weight of the new interval is the sum of the frequency weights of the two old intervals. The average of the lower bounds and that of the upper bounds of the old intervals are used for the new interval.(3)
Step (2) is repeated until set E has no overlapping members.(4)
The interval with the highest frequency is chosen as the estimated parametersu^ and l^. If there are multiple intervals with the highest frequency, the estimated parameters u^ and l^ are randomly chosen from them.


## 3. Self-Synchronization

The embedding and extraction processes as described in previous section are frame-based. That means that the host signal is divided into frames, and one watermark bit is embedded into one frame. Thus, to correctly extract the watermark, the extraction process must know the frame positions. The assumption that the extraction process knows the frame positions in advance may not be practical in some situations. For example, an attacker can attack watermarked signals by cutting a few audio samples. This causes the extraction process to work improperly. This is known as a cropping attack. How the frame positions are acquired is the frame synchronization problem.There are two solutions to solve the frame synchronization problem [11]. The first solution is by binding the watermark with some invariant audio features of the host signal [35] or performing self-synchronization [36–38]. The second solution is by embedding the frame synchronization code into the host signal [39, 40].From experiments, we found that the proposed scheme can automatically detect the watermarked frames. In order to do that, we need to modify the scheme slightly. To fully grasp the idea behind the new rules, let us start with the basic findings from this work.Consider an audio signal with three frames of equal lengthN, where the watermark bit 1 is embedded in its middle frame by the method described in Section 2.1, as illustrated in Figure 15. The starting and the last indices of audio samples of the middle frame Gn,N are denoted by n and n+N-1, respectively. According to the embedding and extraction processes, if we use the frame Gn,N to construct the trajectory matrix, then we can detect the concave pattern in the singular spectrum plot. If τ is an integer which is less than N, then the frames Gn,N and Gn-τ,N are overlapping. We discovered that the singular spectrum curve of the trajectory matrix constructed by the frames Gn-τ,N also has a concave part if the overlapping region is large enough. A similar effect occurs to the frame Gn+τ,N as well. In general, if we construct matrices from frames Gi,N for i=0 to 2N, there are many matrices that we can interpret as having the watermark bit 1 embedded. Those matrices are the ones in which i is in the same neighborhood with n. This overlapping effect of embedding the watermark bit 1 is utilized in our automatic frame detection. We perform a scanning operation by first constructing the frames Gi,N for i=0 to the last possible frame and then extracting the watermark bit from those frames. This effect implies that we can localize the watermarked frame where watermark bit 1 is embedded by performing a scan operation. This is the reason why we need to modify the proposed scheme if we want to make it self-synchronizing. The modification is as follows.Figure 15
Example of an audio clip with3 frames and three segments from which trajectory matrices are constructed.We first divide the frame into4 equal subframes, where each subframe has a length of M. Each watermark bit is represented by the four-bit strings of either “0100” or “0110” depending upon the watermark bit. If the watermark bit is 0, four bits of “0100” are embedded into the 4 subframes. If the watermark bit is 1, “0110” are embedded into those subframes, as illustrated in Figure 16. For example, if the watermark bits are “001”, then the subframe-embedding bits are “010001000110”.Figure 16
Four bits of “0100” are embedded into4 subsegments of a frame, which represents embedding “0” (a), and 4 bits of “0110” are embedded into 4 subsegments of a frame, which represents embedding “1” (b).
(a) (b)Given a frameG=g0g1⋯g4M-1T of length 4M, we define the subframe-scan operator on G as follows.(6)ScanG=b0,b1,…,b3M/δ,(7)bi=ξu,l,Giδ,M,where δ is a scan-step size, Giδ,M is the subframes giδgiδ+1⋯giδ+M-1T, for i=0 to 3M, of the frame G, and ξ(u,l,Giδ,M) is 1 if the singular spectrum curve of the matrix constructed from the subframe Giδ,M on the interval [u+1,l-1] is concave; otherwise, ξ(u,l,Giδ,M) is 0.The meaning of this operator is that the scannerScan[·], which operates on M samples, scans through the frame G with step size δ and returns to 0 or 1, depending upon the characteristics of the singular spectra of the scanned subframes.We use the first appearance of “1” in “0100” and “0110” as the synchronization point of watermark bit0 and 1, respectively. If we can detect the next concavity, we interpret it as the watermark bit 1; otherwise, it is 0. Since the first detected concavity is used as the synchronization point, to ensure that all concavities are surrounded by convexities and that the distance between two concavities is far enough, “0” is added at the first and the last of the four-bit patterns. This is the concept behind our new proposed self-synchronization. An example of performing the subframe-scan operation according to (6) is shown in Figure 17.Figure 17
Illustration of performing the subframe-scan operation on a 3200-sample frame; that is,M=800, with δ=10, u=30, l=80, and “1” being embedded into the second subframe of the frame.To detect a watermarked frame, we define another scanner, which operates on4M samples, called theframe-scan operation. Given a watermarked audio signal Y=y0y1⋯yH-1T of length H greater than 4M, the frame-scan operation F[Y] scans from y0 with a scan step of Δ until it detects the first watermarked frame.GivenYi=yiΔyiΔ+1⋯yiΔ+4M-1T is a frame scanned at step i, we first perform Scan[Yi]=(b0,b1,…,b⌊3M/δ⌋).Let four rectangular windowsWj=(w0j,w1j,…,w⌊3M/δ⌋j), for j=1 to 4, where(8)wkj=1ifk∈σ,σ+Σ,forj=1,2,3,1ifk∈σ-Σ,σ,forj=2,3,4,0otherwise,and σ=⌊3M/4δ⌋(j-1), and Σ is a positive integer, called theoverlap margin. Then, each of these windows is element-wisely multiplied with Scan[Yi]; that is, Wj∗Scan[Yi]=(b0j,b1j,…,b⌊3M/δ⌋j), where the value of bkj is calculated by the following equation. (9)bkj=wkj×bk,for k=0,1,…,3M/δ.If∑k=0⌊3M/δ⌋bkj is greater than ⌈Σ/2⌉ for j=1 or 4, or if ∑k=0⌊3M/δ⌋bkj is greater than Σ+1 for j=2 or 3, we say that, by looking through the window Wj, the concavity of the singular spectrum is detected.The scannerF[Y] stops scanning and declares a watermarked frame only when the conditions described in Table 1 are satisfied. The extracted watermark bit 0 is detected if and only if the concavity of singular spectrum cannot be detected through the windows W1,W3, and W4 but can be detected through window W2. In comparison, the extracted watermark bit 1 is detected if and only if the concavity of the singular spectrum curve cannot be detected through the windows W1 and W4 but can be detected through windows W2 and W3. Otherwise, it continues scanning with a step size of Δ. The frame-scan operation is restarted repeatedly until it reaches the end of the watermarked signal Y.Table 1
Conditions for stopping frame-scan operation. Note that “∘” is “The concavity of singular spectrum can be detected,” and “×” is “The concavity of singular spectrum cannot be detected.”
W 1 W 2 W 3 W 4 Watermark bitw=0 × ∘ × × Watermark bitw=1 × ∘ ∘ ×An example of performing the four windows on one frame is shown in Figure18. In this figure, the second and third subframes are embedded so that the frame-scan operation can decode the pattern of bi as the watermarked bit 1.Figure 18
Example of performing the four windows onScan[Yi].


## 4. Evaluation

Twelve host signals from the RWC music-genre database (Track numbers01, 07, 13, 28, 37, 49, 54, 57, 64, 85, 91, and 100) [41] were used in our experiments. All have a sampling rate of 44.1 kHz, 16-bit quantization, and two channels. Unless stated otherwise, the hidden information was embedded in one channel, starting from the initial segment of host signals. The frame size N was set to 2450 samples. The embedding capacity was 18 bit per second (bps). We chose this capacity because the number is not too low or not too high, and it seems reasonable for general applications. The window length L for the matrix formation was 980. One hundred and fifty bits of the watermark were embedded in total. The audio duration of each signal was about 8.33 seconds.The parametersu and l, obtained from the parameter selection based on the psychoacoustic model 1, are shown in Table 2. The estimated parameters, obtained from the automatic parameter estimation, are shown in Table 3. We implemented the proposed scheme using an adaptive criterion for the predefined SMR level γ as follows. If the maximum SMR is greater than 25dB, γ=18. If the maximum SMR is less than 20dB, γ=12. Otherwise, γ=15.Table 2
Parametersu and l obtained from the parameter selection based on the psychoacoustic model 1.
01 07 13 28 37 49 54 57 64 85 91 100 Parameteru 30 40 20 45 40 40 30 75 30 60 40 35 Parameterl 90 90 60 110 120 100 90 160 90 140 100 93Table 3
Estimated parametersu and l obtained from the automatic parameter estimation in the extraction process.
01 07 13 28 37 49 54 57 64 85 91 100 Estimated parameteru^ 26 39 23 43 44 38 30 81 28 64 37 38 Estimated parameterl^ 90 93 66 110 120 99 90 155 90 140 100 95The proposed schemes were compared with the previously proposed schemes [28, 29] and the conventional SVD-based scheme [23]. There are three reasons for comparing with the conventional SVD-based scheme. First, it is one of a few blind SVD-based techniques. Second, its published results are promising. Last, both the SSA-based and SVD-based schemes belong to the same family of audio watermarking schemes; that is, they extract singular values from the host signals and embed the information into the signals by modifying those singular values. The following subsections report evaluations of the performance in the aspects of sound quality, robustness, and self-synchronization.


### 4.1. Sound-Quality Evaluation

Three distance measures were chosen to evaluate the sound quality of watermarked signals: the evaluation of audio quality (EAQUAL) [42], log-spectral distance (LSD), and the signal-to-distortion ratio (SDR). The EAQUAL measures the degradation of the watermarked signal, compared with the original, and covers a scale, called the objective difference grade (ODG), from -4 (very annoying) to 0 (imperceptible).The LSD is a distance measure between two spectra. GivenP(ω) and P^(ω) are power spectra of the original and the watermarked signals, respectively, the LSD is defined as the following formula:(10)LSD=12π∫-ππ10log⁡PωP^ω2dω.The SDR is a power ratio between the signal and the distortion. Given the amplitudes of original and watermarked signals,Aorg(n) and Awmk(n), the SDR is defined as follows.(11)SDR=10log⁡∑nAorgn2∑nAorgn-Awmkn2.The evaluation criteria for good sound quality are as follows. The ODG must be greater than-1 (not annoying), the LSD must be less than 0.4dB, and the SDR must be greater than 25dB. An ODG of -1 indicates that the noise perceived in the watermarked signal is perceptible but not annoying. Based on our simulations, ODG values between 0 and -1 mean excellent in sound quality. We set the criteria for LSD and SDR to 0.4dB and 25dB, respectively, because we found from our preliminary experiments that either an LSD greater than 0.4dB or an SDR lower than 25dB can cause an annoying perception.The comparison of the average ODGs, average LSDs, and average SDRs is shown in Table4. The proposed scheme satisfies the inaudibility criteria and is considerably improved when it is compared with the SSA-based method [28]. Compared with the conventional SVD-based method and the SSA-based method with differential evolution [29], the proposed method is less inaudible. However, the difference in the inaudibility among them is nonsignificant. Based on our listening-test experiment [29], we found that the signals that satisfy all conditions ODG>-1, LSD<0.4dB, and SDR>25dB are hardly distinguishable in terms of the sound quality. Therefore, these results show that we can use the psychoacoustic model to deliver the parameters u and l, in order to improve the sound quality of the watermarked signal obtained from the previously proposed SSA-based method [28]. However, the parameters determined by the differential evolution give the best performance in terms of sound quality.Table 4
ODGs, LSDs, and SDRs: comparison of the conventional SVD-based method (SVD), SSA-based scheme (SSA), SSA-based scheme with the differential evolution (SSA.DE), proposed scheme without the automatic parameter estimation (Prop.), and proposed one with the automatic parameter estimation (Prop.APE).
ODG LSD SDR SVD [23] −0.23 0.11 26.82 SSA [28] −0.70 0.36 20.96 SSA.DE [29] −0.10 0.16 35.25 Prop. −0.52 0.25 25.61 Prop.APE −0.52 0.25 25.61


### 4.2. Robustness Evaluation

The effectiveness of the proposed schemes in terms of robustness is measured by the watermark extraction precision. We use the bit-error rate (BER) to represent the watermark extraction precision. Given the embedded watermark bit-stringw(i) and the extracted watermark bit-string w^(i) for i=1 to the frame length N,(12)BER=1N∑i=1Nwi⊕w^i,where ⊕ is the bitwise XOR operator. The criterion for the robust scheme is that the BER must be less than 0.1 or 10%. At this level of BER, it is possible to reduce the BER further to close to 0 by adding error correction code. Furthermore, at this level, the BER can be reduced practically and effectively by the embedding-repetition scheme. That is, a frame is segmented into several subframes, and a watermark bit is embedded repeatedly into those subframes. Then the majority rule is applied in the extraction process to decode the extracted watermark bit.Five attacks were performed on watermarked signals: Gaussian-noise addition with average signal-to-noise ratio (SNR) of 36 dB, resampling with16 and 22.05 kHz, band-pass filtering with 100–6000 Hz and −12 dB/Oct, MP3 compression with 128 kbps joint stereo, and MP4 compression with 96 kbps.The results from the robustness evaluation are shown in Table5. The average BERs of the proposed schemes are less than 10% on almost all evaluation attacks except MP3 compression and the band-pass filtering (BPF). For MP3 and BPF, the average BERs are slightly above 10%. If we consider the overall average BERs, which is the average of BERs from all types of attacks, our proposed methods are still below 10% and less than that of the conventional SVD-based method. Table 6 shows the overall average of all methods.Table 5
Robustness evaluation using BERs (%): comparison of the conventional SVD-based method (SVD) [23], SSA-based scheme (SSA) [28], SSA-based scheme with the differential evolution (SSA.DE) [29], proposed scheme without the automatic parameter estimation (Prop.), and proposed one with the automatic parameter estimation (Prop.APE) when attacks (i.e., MP3 and MP4 compression, white-Gaussian-noise addition (AWGN), resampling with 16 and 22.05 kHz (RES 16 and RES 22.05, resp.), and band-pass filtering (BPF)) were performed. AV and SD are average and standard deviation, respectively.
#01 #07 #13 #28 #37 #49 #54 #57 #64 #85 #91 #100 AV SD No Attack SVD 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 SSA 0.00 0.00 4.00 0.00 0.67 0.00 2.67 0.00 0.00 0.00 0.00 0.67 0.67 1.30 SSA.DE 0.00 0.83 0.83 0.00 0.00 0.83 1.67 6.67 1.67 0.83 0.83 0.83 1.25 1.79 Prop. 0.00 0.00 2.00 0.00 0.00 0.67 0.00 12.67 1.33 0.67 1.33 0.67 1.61 3.54 Prop.APE 5.33 0.00 0.67 0.00 0.00 4.00 0.00 12.67 2.67 0.00 3.33 1.33 2.50 3.70  MP3 SVD 47.22 98.33 70.56 87.78 82.50 33.06 41.94 33.61 95.83 18.89 74.72 23.61 59.00 29.03 SSA 1.33 2.00 26.67 0.67 2.67 2.67 5.33 0.67 4.67 0.67 2.67 1.33 4.28 7.21 SSA.DE 0.00 2.50 15.00 3.33 3.33 2.50 8.33 5.00 1.67 6.67 9.17 4.17 5.14 4.11 Prop. 2.00 12.00 26.67 2.00 6.67 7.33 12.00 36.67 3.33 8.67 10.00 4.00 10.94 10.51 Prop.APE 12.00 6.00 17.33 4.67 4.67 7.33 8.67 21.33 0.67 4.67 24.67 1.33 9.44 7.80  MP4 SVD 0.28 0.00 13.89 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.28 1.20 4.00 SSA 0.67 1.33 16.00 0.67 4.00 0.67 3.33 0.67 2.67 0.00 2.67 1.33 2.83 4.33 SSA.DE 0.83 1.67 25.83 2.50 3.33 0.00 12.50 6.67 4.17 2.50 10.83 7.50 6.53 7.23 Prop. 0.00 2.00 16.00 0.67 3.33 2.00 4.00 20.00 5.33 2.00 5.33 2.00 5.22 6.25 Prop.APE 2.67 6.00 10.00 3.33 6.67 8.00 0.00 21.33 12.67 0.00 8.67 0.00 6.61 6.24  BPF SVD 25.83 48.61 47.78 43.61 56.67 21.39 40.56 28.89 62.22 0.83 50.56 30.00 38.08 17.30 SSA 0.00 0.67 40.00 0.00 12.67 0.67 1.33 2.67 0.67 0.67 0.67 0.00 5.00 11.57 SSA.DE 5.00 1.67 40.00 2.50 5.00 2.50 10.83 25.00 3.33 2.50 15.00 5.83 9.93 11.68 Prop. 0.67 0.67 40.00 0.00 14.00 0.00 0.00 15.33 2.67 0.00 2.67 0.67 6.39 11.90 Prop.APE 0.67 6.00 52.00 3.33 15.33 10.67 3.33 24.67 12.67 0.00 8.00 1.33 11.50 14.64  AWGN SVD 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 SSA 0.00 0.00 4.00 0.00 0.67 0.00 2.67 0.00 0.00 0.00 0.00 0.67 0.67 1.30 SSA.DE 0.00 0.83 0.83 0.00 0.00 0.83 1.67 6.67 1.67 0.83 0.83 0.83 1.25 1.79 Prop. 0.00 0.00 2.00 0.00 0.00 0.67 0.00 12.67 1.33 0.67 1.33 0.67 1.61 3.54 Prop.APE 5.33 0.00 0.67 0.00 0.00 4.00 0.00 12.67 2.67 0.00 3.33 1.33 2.50 3.70  RES 16 SVD 5.56 0.83 39.44 0.00 0.00 0.00 0.00 0.00 0.56 1.67 0.28 1.67 4.17 11.22 SSA 1.33 0.00 26.67 0.00 8.00 0.00 3.33 0.00 0.67 0.00 0.00 0.67 3.39 7.69 SSA.DE 1.67 0.00 37.50 0.83 3.33 1.67 3.33 7.50 1.67 0.83 5.83 2.50 5.56 10.29 Prop. 0.67 0.00 27.33 0.00 15.33 0.67 0.00 13.33 2.67 0.67 0.67 0.67 5.17 8.79 Prop.APE 6.67 0.00 30.67 3.33 36.00 2.00 0.00 17.33 6.67 0.00 2.00 1.33 8.83 12.47  RES 2205 SVD 1.67 0.00 12.83 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.67 1.35 3.67 SSA 0.67 0.00 5.33 0.00 4.67 0.00 2.67 0.00 0.00 0.00 0.00 0.67 1.17 1.95 SSA.DE 0.83 0.83 2.50 0.00 2.50 0.00 3.33 7.50 1.67 0.83 0.83 1.67 1.87 2.05 Prop. 0.00 0.00 4.00 0.00 6.67 0.67 0.00 12.67 2.00 0.67 1.33 0.67 2.39 3.81 Prop.APE 1.33 0.00 2.00 0.00 42.00 4.67 0.00 14.00 6.00 0.00 1.33 1.33 6.06 12.01Table 6
Overall average BERs (%): comparison of the conventional SVD-based method (SVD), SSA-based scheme (SSA), SSA-based scheme with the differential evolution (SSA.DE), proposed scheme without the automatic parameter estimation (Prop.), and proposed one with the automatic parameter estimation (Prop.APE).
Overall average BER SVD [23] 14.83 SSA [28] 2.57 SSA.DE [29] 4.50 Prop. 4.76 Prop.APE 6.78Compared with the conventional SVD-based method, the proposed schemes are slightly less robust in the case of “no attack,” “MP4,” “AWGN,” “RES16,” and “BPF.” However, the overall average BERs of the proposed schemes are better than that of the conventional SVD-based one. In general, when the BER is low enough (e.g., 10%), it can be reduced further by applying error correction code or by employing embedding repetitions. On the other hand, the proposed schemes outperform the conventional SVD-based method in the case of “MP3” and “BPF.” Since the average BERs of the conventional SVD-based method in both cases are close to the chance level, they are hard to be improved further by those techniques.Compared with the previously proposed SSA-based methods, it is less robust to some degree. Therefore, the overall performance of the proposed scheme seems to be slightly poorer than that of the SSA-based one with the differential evolution. The explanation concerning this issue is discussed in Section5.When the extraction process does not assume to know the parametersu and l in advance, the average BER increases about 2%. The root-mean-square deviation of the difference between the estimated values and actual values is about 2.83. Thus, the extraction process is sensitive to the correctness of the parameter values to some degree. When it extracts the watermark with less information, the BER increases.


### 4.3. Self-Synchronization Evaluation

To test the self-synchronization, we implemented the scheme with settings shown in Table7. Each test signal is randomly chosen as a segment of 98000 samples (about 2.2 seconds), and 10 bits of the watermark were embedded into the segment.Table 7
Simulation conditions for the self-synchronized SSA-based audio watermarking scheme.
Conditions Subframe lengthM 2450 Window lengthL 980 Subframe-scan stepδ 10 Frame-scan stepΔ 10 Overlap marginΣ 20 Embedding capacity 4.5 bps Payload 10 bits Total duration 2.22 secondsTo detect the watermarked frame and to extract the watermark, we randomly choose the initial sample, which is before the embedded segment, for the scan operation, as depicted in Figure19. The accuracy of the frame detection and the watermark extraction is defined as the number of correctly extracted watermark bits divided by the total number of embedded watermark bits. Since there is naturally the concavity on singular spectra, it is possible that our proposed method identifies an unwatermarked segment as a watermarked frame. In this case we will have a misidentified frame. The false positive rate is defined as the number of misidentified frames divided by the total number of frames identified by the algorithm. The test results show that the accuracy of the frame detection and the watermark extraction is 80%. The false positive detection rate is 6.42%.Figure 19
The initial sample, which is before the watermarked segment, is randomly chosen for the scan operation.


## 4.1. Sound-Quality Evaluation

Three distance measures were chosen to evaluate the sound quality of watermarked signals: the evaluation of audio quality (EAQUAL) [42], log-spectral distance (LSD), and the signal-to-distortion ratio (SDR). The EAQUAL measures the degradation of the watermarked signal, compared with the original, and covers a scale, called the objective difference grade (ODG), from -4 (very annoying) to 0 (imperceptible).The LSD is a distance measure between two spectra. GivenP(ω) and P^(ω) are power spectra of the original and the watermarked signals, respectively, the LSD is defined as the following formula:(10)LSD=12π∫-ππ10log⁡PωP^ω2dω.The SDR is a power ratio between the signal and the distortion. Given the amplitudes of original and watermarked signals,Aorg(n) and Awmk(n), the SDR is defined as follows.(11)SDR=10log⁡∑nAorgn2∑nAorgn-Awmkn2.The evaluation criteria for good sound quality are as follows. The ODG must be greater than-1 (not annoying), the LSD must be less than 0.4dB, and the SDR must be greater than 25dB. An ODG of -1 indicates that the noise perceived in the watermarked signal is perceptible but not annoying. Based on our simulations, ODG values between 0 and -1 mean excellent in sound quality. We set the criteria for LSD and SDR to 0.4dB and 25dB, respectively, because we found from our preliminary experiments that either an LSD greater than 0.4dB or an SDR lower than 25dB can cause an annoying perception.The comparison of the average ODGs, average LSDs, and average SDRs is shown in Table4. The proposed scheme satisfies the inaudibility criteria and is considerably improved when it is compared with the SSA-based method [28]. Compared with the conventional SVD-based method and the SSA-based method with differential evolution [29], the proposed method is less inaudible. However, the difference in the inaudibility among them is nonsignificant. Based on our listening-test experiment [29], we found that the signals that satisfy all conditions ODG>-1, LSD<0.4dB, and SDR>25dB are hardly distinguishable in terms of the sound quality. Therefore, these results show that we can use the psychoacoustic model to deliver the parameters u and l, in order to improve the sound quality of the watermarked signal obtained from the previously proposed SSA-based method [28]. However, the parameters determined by the differential evolution give the best performance in terms of sound quality.Table 4
ODGs, LSDs, and SDRs: comparison of the conventional SVD-based method (SVD), SSA-based scheme (SSA), SSA-based scheme with the differential evolution (SSA.DE), proposed scheme without the automatic parameter estimation (Prop.), and proposed one with the automatic parameter estimation (Prop.APE).
ODG LSD SDR SVD [23] −0.23 0.11 26.82 SSA [28] −0.70 0.36 20.96 SSA.DE [29] −0.10 0.16 35.25 Prop. −0.52 0.25 25.61 Prop.APE −0.52 0.25 25.61


## 4.2. Robustness Evaluation

The effectiveness of the proposed schemes in terms of robustness is measured by the watermark extraction precision. We use the bit-error rate (BER) to represent the watermark extraction precision. Given the embedded watermark bit-stringw(i) and the extracted watermark bit-string w^(i) for i=1 to the frame length N,(12)BER=1N∑i=1Nwi⊕w^i,where ⊕ is the bitwise XOR operator. The criterion for the robust scheme is that the BER must be less than 0.1 or 10%. At this level of BER, it is possible to reduce the BER further to close to 0 by adding error correction code. Furthermore, at this level, the BER can be reduced practically and effectively by the embedding-repetition scheme. That is, a frame is segmented into several subframes, and a watermark bit is embedded repeatedly into those subframes. Then the majority rule is applied in the extraction process to decode the extracted watermark bit.Five attacks were performed on watermarked signals: Gaussian-noise addition with average signal-to-noise ratio (SNR) of 36 dB, resampling with16 and 22.05 kHz, band-pass filtering with 100–6000 Hz and −12 dB/Oct, MP3 compression with 128 kbps joint stereo, and MP4 compression with 96 kbps.The results from the robustness evaluation are shown in Table5. The average BERs of the proposed schemes are less than 10% on almost all evaluation attacks except MP3 compression and the band-pass filtering (BPF). For MP3 and BPF, the average BERs are slightly above 10%. If we consider the overall average BERs, which is the average of BERs from all types of attacks, our proposed methods are still below 10% and less than that of the conventional SVD-based method. Table 6 shows the overall average of all methods.Table 5
Robustness evaluation using BERs (%): comparison of the conventional SVD-based method (SVD) [23], SSA-based scheme (SSA) [28], SSA-based scheme with the differential evolution (SSA.DE) [29], proposed scheme without the automatic parameter estimation (Prop.), and proposed one with the automatic parameter estimation (Prop.APE) when attacks (i.e., MP3 and MP4 compression, white-Gaussian-noise addition (AWGN), resampling with 16 and 22.05 kHz (RES 16 and RES 22.05, resp.), and band-pass filtering (BPF)) were performed. AV and SD are average and standard deviation, respectively.
#01 #07 #13 #28 #37 #49 #54 #57 #64 #85 #91 #100 AV SD No Attack SVD 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 SSA 0.00 0.00 4.00 0.00 0.67 0.00 2.67 0.00 0.00 0.00 0.00 0.67 0.67 1.30 SSA.DE 0.00 0.83 0.83 0.00 0.00 0.83 1.67 6.67 1.67 0.83 0.83 0.83 1.25 1.79 Prop. 0.00 0.00 2.00 0.00 0.00 0.67 0.00 12.67 1.33 0.67 1.33 0.67 1.61 3.54 Prop.APE 5.33 0.00 0.67 0.00 0.00 4.00 0.00 12.67 2.67 0.00 3.33 1.33 2.50 3.70  MP3 SVD 47.22 98.33 70.56 87.78 82.50 33.06 41.94 33.61 95.83 18.89 74.72 23.61 59.00 29.03 SSA 1.33 2.00 26.67 0.67 2.67 2.67 5.33 0.67 4.67 0.67 2.67 1.33 4.28 7.21 SSA.DE 0.00 2.50 15.00 3.33 3.33 2.50 8.33 5.00 1.67 6.67 9.17 4.17 5.14 4.11 Prop. 2.00 12.00 26.67 2.00 6.67 7.33 12.00 36.67 3.33 8.67 10.00 4.00 10.94 10.51 Prop.APE 12.00 6.00 17.33 4.67 4.67 7.33 8.67 21.33 0.67 4.67 24.67 1.33 9.44 7.80  MP4 SVD 0.28 0.00 13.89 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.28 1.20 4.00 SSA 0.67 1.33 16.00 0.67 4.00 0.67 3.33 0.67 2.67 0.00 2.67 1.33 2.83 4.33 SSA.DE 0.83 1.67 25.83 2.50 3.33 0.00 12.50 6.67 4.17 2.50 10.83 7.50 6.53 7.23 Prop. 0.00 2.00 16.00 0.67 3.33 2.00 4.00 20.00 5.33 2.00 5.33 2.00 5.22 6.25 Prop.APE 2.67 6.00 10.00 3.33 6.67 8.00 0.00 21.33 12.67 0.00 8.67 0.00 6.61 6.24  BPF SVD 25.83 48.61 47.78 43.61 56.67 21.39 40.56 28.89 62.22 0.83 50.56 30.00 38.08 17.30 SSA 0.00 0.67 40.00 0.00 12.67 0.67 1.33 2.67 0.67 0.67 0.67 0.00 5.00 11.57 SSA.DE 5.00 1.67 40.00 2.50 5.00 2.50 10.83 25.00 3.33 2.50 15.00 5.83 9.93 11.68 Prop. 0.67 0.67 40.00 0.00 14.00 0.00 0.00 15.33 2.67 0.00 2.67 0.67 6.39 11.90 Prop.APE 0.67 6.00 52.00 3.33 15.33 10.67 3.33 24.67 12.67 0.00 8.00 1.33 11.50 14.64  AWGN SVD 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 SSA 0.00 0.00 4.00 0.00 0.67 0.00 2.67 0.00 0.00 0.00 0.00 0.67 0.67 1.30 SSA.DE 0.00 0.83 0.83 0.00 0.00 0.83 1.67 6.67 1.67 0.83 0.83 0.83 1.25 1.79 Prop. 0.00 0.00 2.00 0.00 0.00 0.67 0.00 12.67 1.33 0.67 1.33 0.67 1.61 3.54 Prop.APE 5.33 0.00 0.67 0.00 0.00 4.00 0.00 12.67 2.67 0.00 3.33 1.33 2.50 3.70  RES 16 SVD 5.56 0.83 39.44 0.00 0.00 0.00 0.00 0.00 0.56 1.67 0.28 1.67 4.17 11.22 SSA 1.33 0.00 26.67 0.00 8.00 0.00 3.33 0.00 0.67 0.00 0.00 0.67 3.39 7.69 SSA.DE 1.67 0.00 37.50 0.83 3.33 1.67 3.33 7.50 1.67 0.83 5.83 2.50 5.56 10.29 Prop. 0.67 0.00 27.33 0.00 15.33 0.67 0.00 13.33 2.67 0.67 0.67 0.67 5.17 8.79 Prop.APE 6.67 0.00 30.67 3.33 36.00 2.00 0.00 17.33 6.67 0.00 2.00 1.33 8.83 12.47  RES 2205 SVD 1.67 0.00 12.83 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.67 1.35 3.67 SSA 0.67 0.00 5.33 0.00 4.67 0.00 2.67 0.00 0.00 0.00 0.00 0.67 1.17 1.95 SSA.DE 0.83 0.83 2.50 0.00 2.50 0.00 3.33 7.50 1.67 0.83 0.83 1.67 1.87 2.05 Prop. 0.00 0.00 4.00 0.00 6.67 0.67 0.00 12.67 2.00 0.67 1.33 0.67 2.39 3.81 Prop.APE 1.33 0.00 2.00 0.00 42.00 4.67 0.00 14.00 6.00 0.00 1.33 1.33 6.06 12.01Table 6
Overall average BERs (%): comparison of the conventional SVD-based method (SVD), SSA-based scheme (SSA), SSA-based scheme with the differential evolution (SSA.DE), proposed scheme without the automatic parameter estimation (Prop.), and proposed one with the automatic parameter estimation (Prop.APE).
Overall average BER SVD [23] 14.83 SSA [28] 2.57 SSA.DE [29] 4.50 Prop. 4.76 Prop.APE 6.78Compared with the conventional SVD-based method, the proposed schemes are slightly less robust in the case of “no attack,” “MP4,” “AWGN,” “RES16,” and “BPF.” However, the overall average BERs of the proposed schemes are better than that of the conventional SVD-based one. In general, when the BER is low enough (e.g., 10%), it can be reduced further by applying error correction code or by employing embedding repetitions. On the other hand, the proposed schemes outperform the conventional SVD-based method in the case of “MP3” and “BPF.” Since the average BERs of the conventional SVD-based method in both cases are close to the chance level, they are hard to be improved further by those techniques.Compared with the previously proposed SSA-based methods, it is less robust to some degree. Therefore, the overall performance of the proposed scheme seems to be slightly poorer than that of the SSA-based one with the differential evolution. The explanation concerning this issue is discussed in Section5.When the extraction process does not assume to know the parametersu and l in advance, the average BER increases about 2%. The root-mean-square deviation of the difference between the estimated values and actual values is about 2.83. Thus, the extraction process is sensitive to the correctness of the parameter values to some degree. When it extracts the watermark with less information, the BER increases.


## 4.3. Self-Synchronization Evaluation

To test the self-synchronization, we implemented the scheme with settings shown in Table7. Each test signal is randomly chosen as a segment of 98000 samples (about 2.2 seconds), and 10 bits of the watermark were embedded into the segment.Table 7
Simulation conditions for the self-synchronized SSA-based audio watermarking scheme.
Conditions Subframe lengthM 2450 Window lengthL 980 Subframe-scan stepδ 10 Frame-scan stepΔ 10 Overlap marginΣ 20 Embedding capacity 4.5 bps Payload 10 bits Total duration 2.22 secondsTo detect the watermarked frame and to extract the watermark, we randomly choose the initial sample, which is before the embedded segment, for the scan operation, as depicted in Figure19. The accuracy of the frame detection and the watermark extraction is defined as the number of correctly extracted watermark bits divided by the total number of embedded watermark bits. Since there is naturally the concavity on singular spectra, it is possible that our proposed method identifies an unwatermarked segment as a watermarked frame. In this case we will have a misidentified frame. The false positive rate is defined as the number of misidentified frames divided by the total number of frames identified by the algorithm. The test results show that the accuracy of the frame detection and the watermark extraction is 80%. The false positive detection rate is 6.42%.Figure 19
The initial sample, which is before the watermarked segment, is randomly chosen for the scan operation.


## 5. Discussion

Even though the proposed scheme satisfies the robustness and inaudibility criteria, there are other aspects that need to be improved. In this section, five issues concerning the performance and limitation of the proposed scheme are discussed. The first two issues are about the performance of the proposed scheme. The next two issues are about the limitation of the currently proposed self-synchronized scheme. The last one is a general problem in terms of the confidentiality property.First, we have shown that the psychoacoustic model can be used to determine the parametersu and l. These parameters are host-signal-dependent and of importance because their values determine the balance between the inaudibility and the robustness. In our previously proposed method, differential evolution was used to determine the parameters. Compared with using differential evolution, there are two advantages of using the psychoacoustic model.(i)
The computational time is reduced considerably because the differential evolution optimization has a large search space. The comparison of the computational time is shown in Table8. To determine the parameters u and l for one signal, differential evolution takes about 13 hours, whereas the psychoacoustic-model-based method takes about 4.3 seconds.(ii)
The optimal parameters from the differential evolution depends on many factors, such as the simulations included in the optimizer [29]. Moreover, the cost function has two additional parameters. In this sense, using the psychoacoustic model reduces the number of scheme parameters.Table 8
Comparison of the computational times for determining the parameters of an host signal when the automatic parameterization is based on the differential evolution [29] and when it is based on the psychoacoustic model. The simulations were operated on the Fujitsu CX250 Cluster (JAIST parallel computers), where each node is equipped with Two Intel Xeon E5-2680v2 2.80 GHz (10 cores each) and 64 GB memory.
Function Computational time of the function Search space/No. of operations Approximated total computational time Differential Evolution Cost function evalution 3 minutes 44 seconds 31815 possible vectors 13 hours 9 minutes Psychoacoustic Model SMR calculation 0.36 seconds 717 times 4.3 minutesHowever, the robustness of the proposed scheme is slightly poorer than that of the previously proposed methods. This is because only the SMR is used as the guidance for the parameter determination. The low SMR can gain inaudibility but may lose robustness because the lower SMRs associates with the lower singular-value indices. In addition, the components with the lower SMRs are more likely to be destroyed by the perceptual codings. To improve the robustness of the proposed scheme, we may include the other masking phenomena, such as the nonlinear excitatory masking, to the psychoacoustic model. This is one of our future work.Second, different from the previously proposed scheme, this scheme does not modify the singular spectrum when the watermark bit0 is embedded. We found that the effectiveness in terms of robustness is the same, but in terms of inaudibility, the objective scores improve slightly, as shown in Table 9. The previously proposed schemes, especially the one with the differential evolution optimization, can benefit from this fact because the optimization function directly handles the trade-off between inaudibility and robustness.Table 9
ODGs, LSDs, and SDRs: comparison of the proposed scheme when the singular spectrum is modified and when it is not modified to embed the watermark bit0.
ODG LSD SDR The singular spectrum is modified. 0.18 0.34 24.30 The singular spectrum is not modified. 0.18 0.25 25.61Third, the proposed self-synchronization is time-consuming. The extraction process with the self-synchronization takes up to(3M/δ+1) times that of one without. Based on our simulation, the extraction process without the self-synchronization took about 1.6 seconds to extract one watermark bit, whereas the one with the self-synchronized process took about 20 minutes. This explains why we separately simulated and evaluated the self-synchronization.Fourth, although the synchronization rate of80% of the proposed scheme with self-synchronization does not satisfy the criterion of BER being less than 10%, it can confirm the fundamental concepts on which the self-synchronized, proposed scheme is based. From our analysis, we found that the detection rate is determined by the algorithm that interprets the bit-string bi. In the proposed scheme, our algorithm uses the simplest rectangular windows to find the pattern of bi. Even in the case that the algorithm could not detect a watermark bit, we found that the string bi correctly presented the concavity on the singular spectra. Therefore, some effective pattern recognition techniques could be helpful to improve the situation.Also, the false positive detection rate indicates that the algorithm sometimes detects a watermark bit when no hidden information is embedded there. We investigated this problem by analyzing unwatermarked signals with the proposed automatic frame detection. We found that in those false positive detection cases, there is some concavities on the singular spectra. If the false positive detection is a serious concern, we can solve this problem by first detecting the natural concavity and then hiding the watermark only in the no-concavity frames. Otherwise, good pattern recognition is required due to our findings that the patterns of the stringbi of the natural concavity are different from those of the embedded watermark. This problem will be further investigated in the future.Fifth, since this work has shown that we can completely blindly scan and analyze the watermarked signals to detect and extract the watermark, there is a question on the confidentiality of the watermark. As a result, if the secrecy of the watermark is a concern, we may need to encrypt the watermark with an encryption key before it is embedded into the host signals. Later, in the extraction process, a decryption key is required to decrypt the extracted, encrypted watermark to obtain the original one.


## 6. Conclusion

The main objective of this work is to show that SSA, equipped with the psychoacoustic model, can give a good balance between inaudibility and robustness, so that it can overcome the problems in the previously proposed SSA-based method [28] and the SVD-based method. Even though the overall performance of the currently proposed schemes is poorer than that of the SSA-based one with differential evolution, the processing time is reduced considerably. Integrated with the psychoacoustic model, the SSA-based audio watermarking scheme achieves three required properties of the audio watermarking system: inaudibility, robustness, and blindness. Also, this paper presented a novel method for self-synchronization. The synchronization rate of the proposed self-synchronized scheme was about 80%. Improving the synchronization rate and reducing the computational time of the self-synchronized scheme are our future work.



---

*Source: 5067313-2016-11-30.xml*