Audio and Video Signatures for Synchronization
Regunathan Radhakrishnan, Kent Terry and Claus Bauer
Dolby Laboratories Inc
100 Potrero Ave, San Francisco, CA
Email: {regu.r,kbt,cb}@dolby.com

Abstract— We propose a framework based on signatures extracted from audio and video streams for automatically measuring and maintaining synchronization between the two streams.
The audio signature is based on projections of a coarse representation of the spectrogram onto random vectors. The video
signature is based on projections of a coarse representationof the difference image between two consecutive frames onto
random vectors. The time alignment present at the signature
generator between the two streams is recorded by combining
audio and video signatures into a combined synchronization
signature. At the detector after video and audio streams go
through different processing operations, we extract the signatures
again. The signatures extracted before and after processing fromthe audio and the video are compared independently usinga Hamming distance based correlator to estimate the relative
misalignment introduced due to processing in each of the streams.
Then, the estimated relative misalignment between the audio
and video streams is used to preserve the same alignment
between the streams that was present before processing. Our
experimental results show that we can achieve > 93.0% accuracy
in synchronization.

I. I NTRODUCTION
Audio and video streams though initially synchronized in
the front-end of a broadcast system can often go out ofsynchronization after going through different signal processing operations independently, resulting in lip synchronization
errors. It is impractical to measure and maintain synchronism
between these two streams manually. Hence, there is a needfor an automatic mechanism to achieve this.
Past work on synchronizing audio and video using features
has relied on ﬁrst extracting certain audio or video features
and then synchronously attaching these to the other signal.
This could be achieved by watermarking and hence limitedby the robustness of the watermarking method to recover thesynchronization data [10].
In this paper, we propose a framework based on audio-visualsignatures for automatically measuring and maintaining thetime alignment between the audio and video streams. In thisframework, the alignment present at the signature generator
between the audio and video streams is recorded by combining
audio and video signatures into a synchronization signature.
It extracts certain video signatures and audio signatures ata point when the two streams are assumed to be in timealignment. The audio signatures are based on the projectionsof a coarse spectrogram onto random vectors [9] and thevideo signatures are based on the projections of a coarse
difference image onto random vectors [8]. The extracted
signatures from the audio and the video are content-based anddo not change drastically as the audio and video streams go

978-1-4244-2571-6/08/$25.00 ©2008 IEEE

Fig. 1.

Audio and Video Signature Generation

through signal processing operations that preserve the content.
During synchronization, the same signatures are extracted andcompared with the reference signatures to estimate the relative
temporal misalignment between the two streams. Then, theestimated relative misalignment is used to achieve the samealignment between the audio and video streams that waspresent before processing. Note that the reference signatures
for audio and video and their alignment information, do notneed to follow the signal processing paths that the audio andvideo streams follow. They are assumed to arrive intact at thedetector through a reliable meta-data path.
II. P ROPOSED F RAMEWORK
Figure 1 shows the procedure for signature generation foraudio and video. The extracted signatures are referred toas reference signatures. In practical applications, the audio
and video streams are assumed to have the correct relativesynchronization in terms of time alignment. Even if they are
not aligned, the proposed system would measure and preserve
whatever the alignment is between the audio and video streams
at the signature generation end. The alignment information isrecorded by combining audio and video signatures that occur
together.
Figure 2 shows the procedure for synchronization at thedetector. First, signatures are extracted from processed audio
and video data. Then, the extracted signatures are comparedwith corresponding reference signatures using a Hamming
distance based correlator. The output of hamming distancebased correlator is estimated delay are relative to each of
the corresponding reference signature. Finally, the estimateddelays are used to correct the relative misalignment between
the audio and video streams.
In the following subsections, we describe each of thecomponents of the proposed framework.

1549

ICME 2008

Fig. 2.

Fig. 3.

Audio Feature Extraction

Fig. 4.

Video Feature Extraction

Synchronization procedure at the detector

A. Audio Signature Extraction
The goal of audio feature extraction is to create a signaturethat is robust against a wide set of processing applied to theaudio stream such as compression, time scale modiﬁcation etc.
The proposed method consists of two steps: Feature extraction
is explained here and calculation of the signature bits is
described in section II-C.
We use our audio signature extraction method proposed in[9]. The method in [9] creates a low-dimensional representation of a coarse spectrogram of the input audio frame byprojecting the spectrogram onto random vectors, which canbe thought of as basis vectors. For the sake of completeness,
we provide a brief description here. In general, we could use
any of other audio signature extraction methods proposed inliterature [2],[5],[3],[4].
The generation of the coarse spectrogram itself is illustrated
in Figure 3. The input audio is ﬁrst divided into chunks ofduration Tch with an overlap of To between adjacent chunks.
For each chunk of audio data (Xch ) we compute a spectrogram with certain time resolution and frequency resolution.
Then, we mark time-frequency blocks within the computed
spectrogram for Xch . Finally, we sum up the magnitude of thespectrum within each of the time-frequency blocks to obtain acoarse representation of the spectrogram. Let us represent the
spectrogram by S. We obtain a coarse representation (Qa ) of S
by averaging the magnitude of frequency coefﬁcients in timefrequency blocks of size Wf × Wt such that F × Wf = 129
and T ×Wt = 142 . F is the number of blocks along frequency
axis and T is the number of blocks along time axis and hence
Qa is of size (F*T). Qa is computed as given below:
1
Qa (k, l) =Wf ∗ Wt

kWf



lWt


B. Video Signature Extraction
The goal of the video feature extraction block is to comeup with robust features that are invariant to certain signal
processing operations on the video. This set of features would
have to survive a variety of processing of the video, including
compression, color space conversion, intensity adjustment,
addition of computer generated graphic objects, format conversions etc. In this section, we use the video signature extraction
method proposed in [8].We provide a brief description below
for the sake of completeness. In general, any of the other video
signature methods proposed in literature could be used [6],[7].
Figure 4 illustrates the proposed video feature extraction
approach in [8]. An absolute difference image is computed
between adjacent video frames (frame(n) and frame(n+1)).
Then, the absolute difference image is downsampled andcropped so that the extracted features are invariant to interlaced
and progressive video formats and addition of graphics andletterboxes on the corners of the individual frames. Then, thecropped absolute difference image is tiled horizontally andvertically. Finally, the intensities of the absolute difference
image within each tile are summed up to obtain a coarse absolute difference image. Let us represent the cropped absolutedifference image by Δ. We obtain a coarse representation (Qv) of Δ by averaging pixel intensities in image blocks of size
Wx × Wy such that K × Wx = 120 and L × Wy = 160 . Qv
is of size (K × L)

S(i, j)Qv (k, l) =i=(k−1)Wf j=(l−1)Wt

f = 1, 2...F ; t = 1, 2...T
Here, i and j represent the indices of frequency and timein the spectrogram and k and l represent the indices of thetime-frequency blocks in which the averaging operation is
performed. Note that the size of To (typically 10 ms) relative
to inter frame duration (typically 30ms) in video determines
the accuracy of alignment.

1
Wx ∗ Wy

kW
x

lWy


Δ(i, j)i=(k−1)Wx j=(l−1)Wy

k = 1, 2...K; l = 1, 2...L
Here i and j represent the indices for the horizontal andvertical dimensions for the absolute difference image Δ. k
and l represent the indices of the sub-blocks of the absolutedifference image Δ. This coarse representation (Qv ) helps us1550

achieve robustness by allowing for certain variations within a
block while preserving the average intensity within a block.
C. Robust Hash
This block takes as input the matrix, Q (Q = Qv forvideo and Q = Qa for audio), and generates the signature by
generating K hash bits. We use a robust hash function for thispurpose as small perturbations in the audio and video featurescaused by signal processing operations such as compression,ﬁltering etc would not change the hash bits drastically. The
Robust hash function also serves to reduce the bit-rate of
the signature stream. Let us represent the dimensions of thematrix Q by (M × N ). By using a robust hash, instead ofsending (M × N ) values we only send few bits. A robust
hash function is unlike a regular cryptographic hash function.
A cryptographic hash function changes its output for every
single bit change in the input. However, we would like ourhash output to change slowly with small changes in features.
This would enable us to allow for certain signal processing
operations on the content which do not change the content
but only slightly disturb the features. We use one such robust
hash function proposed in [1] for generating the hash bits fromthe feature matrix, Q. We generate K random matrices eachwith the same dimensions as the matrix, Q (M × N ). The
matrix entries are uniformly distributed random variables in[0, 1]. The state of the random number generator is set basedon a key. Let us denote these random matrices by P1 , P2 , ...PK
each of dimension (M × N ). We compute the mean of matrix
Pi and subtract it from each matrix element in Pi (i goes from
1 to K). Then, the matrix Q is projected onto these K random
vectors as shown below:
Hk =

N
M 


Q(i, j) ∗ Pk (i, j)

i=1 j=1

Here Hk is the projection of the matrix Q onto the random
vector Pk . Using the median of these projections ( Hk , k =1, 2K) as a threshold, we generate K hash bits for the matrix
Q. We generate a hash bit ’1’ for k th hash bit if the projection
Hk is greater than the threshold. Otherwise, we generate a hashbit of ’0’.
D. Hamming Distance based Correlator
The goal of the Hamming distance based correlator is tocompare a sequence of reference signatures (R) and a sequenceof attacked signatures (A) extracted from processed audio orvideo and estimate the relative temporal alignment (delay)
between the two. Let us represent the reference signaturesfor video as Rv and the reference signatures for audio as
Ra . These signatures are extracted at a point where theaudio and video are assumed to be temporally aligned. The
audio and video may go through different signal processing
operations and incur different delays δv and δa . Then, at thedetector we extract the attacked signatures. Let us represent theattacked signatures for video as Av and the attacked signatures
for audio as Aa . The Hamming distance based correlator
compares Rv and Av and outputs a delay estimate γv of δv .

It also compares Ra and Aa and outputs a delay estimate γaof δa . Then, by using the delay estimates (γv and γa ), we
can achieve the same alignment between the audio and video
streams that was present while the reference signatures wereextracted.
Now let us look at how the Hamming distance based
correlator computes the delay estimates. We will drop the
sufﬁces v and a from Rv , Ra , Av and Aa as the Hamming
distance based correlator is the same for comparing audio andvideo signatures. The inputs to the correlator are two set ofsignatures: R (reference) and A (attacked). The correlator hasa search range of L signatures. For every signature from R(i)from R, it tries to search within L a matching window (W )of signatures from A by computing the following score:D(m, i) =j=W


Hammingdist(R(i + j), A(m + j))

j=0m = i − L, ..1...i + L; i = 1, 2...I
Here I is the total of number signatures in R and Hammingdist
refers to the Hamming distance between two signatures. By
computing this score, we are searching for a matching sequence of signatures R(i) through R(i + W ) in the reference signature, a corresponding sequence of signatures A(m)through A(m + W ) in A. γi = arg minm D(m, i); m =i − L, ...i + L; is the index ’m’ for which the score isminimum within the search window. This means that we founda matching signature at index ’m’ in A for the reference
signature at index ’i’ in R. If there is no processing delay,
then the matching index γi would be same as i. If there is aprocessing delay equal to 3 frames, then the matching index
γi would be i + 3. Therefore, the relative delay estimate forthe signature for frame ’i’ is the offset value between ’i’ and’γi ’.
III. E XPERIMENTAL R ESULTS
A. Test Content
The test content used for the performance assessment of
the proposed signature extraction based audio/video synchronization consisted of 36 one-minute audio video clips ofa variety of content types in various formats. The video
formats include standard broadcast formats such as Standard
Deﬁnition 480/30i, High Deﬁnition 1080/30i and 720/60p.
The audio for the content was both stereo and 5.1 channel
formats at 48khz. Each of the test clips were processedin a variety of ways to simulate the processing in modern
broadcasting and post production facilities. For video, theconsidered processing operations include: Fast/Slow play by
5%, Brightness modiﬁcation by 10%, Median noise reduction,
Addition of random ﬁlm grain type noise, MPEG compression
and decompression at 2,4,8 and 12Mbps, Down conversion
from HD to SD, Logo and Graphic insertions. For audio, theconsidered processing operations include: 5% speedup/slow
down without pitch correction, 5% speedup/slowdown withpitch correction, Down mixing, Gain modiﬁcation by 15db,
Equalization, Dynamic Range Compression, Dolby Digital1551

Video Source

Accuracy

Audio Source

AccuracyStandard Deﬁnition
High Deﬁnition (1080i)
High Deﬁnition (720p)

94.0%
97.0%
93.0%

StereoMulti-Channel

94.0%
97.0%

TABLE IIP ERFORMANCE OF AUDIO S IGNATURE

TABLE IP ERFORMANCE OF V IDEO S IGNATURE

Encoding/Decoding (320,480,640 kbps for 5.1 channel and
192 and 128kbps for stereo), MPEG1 layer II encoding anddecoding at 128 and 256kbps for stereo. Overall, we created
432 test cases for video and 645 test cases for audio.

alignment estimates are correct. In other scenarios, a higher
level of logic is needed that combines them intelligently.
Our initial results based on ﬁltering out spurious alignment
estimates provide slightly better results than those in Table I
and II.

B. Parameter Settings
The signature extraction parameters for video were set as
described below. The size of coarse difference image was set
to be 8 × 9 (K = 8, L = 9). The number of random vectors
for the hash was chosen to be 36. This means for every pair offrames we create a signature of length 36 bits. The parameters
for comparing two video signatures at the hamming distancebased correlator were set as described below. The search range
was set to be 3 seconds and the window (W ) was set to be
one second worth of signatures.
The signature extraction parameters for audio were set
as described below. The time-frequency resolution for the
spectrogram was set to be 10 × 20 (T = 10, F = 20). The
number of random vectors for the hash was chosen to be 18.
The chunk size (Tch ) was chosen to be 90ms and the step size(To ) was set to be 512 samples at 48khz sampling rate. The
parameters for comparing two audio signatures at the hamming
distance based correlator were set as described below. The
search range was set to be 2 seconds and the window (W ) was
set to be 0.25 second worth of signatures. These parameters
were chosen empirically based on performance on a wide
variety of content.

IV. C ONCLUSION
We proposed an audio/video signature extraction based
framework for measuring and maintaining synchronism between audio and video streams. The proposed system extracts
reference signatures from audio and video at a point where
the two streams are assumed to be aligned. Then, the audio
and video streams take independent processing paths. The
reference signatures along with the alignment information isavailable at detector where they are to be re-synchronized. At
the detector, audio and video signatures are extracted fromprocessed/modiﬁed content and compared with the reference
signatures to extract the relative misalignment between audio
and video. This information is used to preserve the samealignment between the two streams that was present when
the reference signatures were extracted. We presented experimental results on a wide variety of content with different
kinds of processing on the original source. For video, wewere able to achieve 93%-97% accuracy in estimating therelative delay between the reference signature and the attacked
signature. Similarly, for audio, we were able to achieve 94%97% accuracy. In our future work, we would explore thetradeoff in accuracy and number of signature bits.

C. Algorithm Performance
Before we present the results, we ﬁrst describe the criteria
for success in Audio/Video synchronization. We consider ita success if the estimated relative alignment between thereference signature of source audio and the extracted signatureof processed audio is within 10ms of the actual relativealignment between the two. For video, we consider it a
success if relative alignment between the reference signatureof source video and the extracted signature of processed video
is within 1 frame duration of the actual relative alignment
between the two. As long as we can accurately estimate
these relative alignments for audio and video signatures in
the hamming distance based correlator, we would be able tocorrect the temporal misalignment between audio and video.
The synchronization accuracy is therefore measured in termsof percentage number of times for which the estimated relativealignment is within actual relative alignment.
Tables I and II present the accuracy of the alignment
estimates for video and audio respectively. Note that we canachieve synchronism only when both the audio and video

R EFERENCES[1] J.Fridrich and M.Goljan, “Robust Hash Functions for Digital Watermarking”, Proc. of ITCC, 2000.
[2] Burges, C.J.C. Platt, J.C. Jana, S, “Distortion discriminant analysis for audio ﬁngerprinting”, IEEE Transactions on Speech and Audio Processing,May 2003.
[3] Chun-Shien Lu, “Audio ﬁngerprinting based on analyzing time-frequency
localization of signals”, IEEE Workshop on Multimedia Signal Processing, 2002.
[4] E.Batlle, J.Masip, E. Guaus, “Automatic Song Identiﬁcation in Noisy
Broadcast Audio”, Proc. Of SIP, Aug 2002.
[5] J.Haitsma and T.Kalker, “A Highly Robust Audio Fingerprinting System”,
In Proc. ISMIR 2002
[6] Kozat, S.S. Venkatesan, R. Mihcak, M.K. , “Robust perceptual image
hashing via matrix invariants”, ICIP 2004.
[7] A.Swaminathan, Y.Mao and Min Wu, “Image Hashing Resilient To
Geometric and Filtering Operations”, MMSP 2004.
[8] R.Radhakrishnan and C.Bauer, “Content-based video signatures based on
projections of difference images”, MMSP, 2007.
[9] R.Radhakrishnan, C.Bauer, C.Cheng and K.Terry, “Audio signature extraction based on projections of spectrograms”, ICME, 2007.
[10] US patent 6211919.

1552