1.

Introduction

Video matching techniques are motivated by various applications, including video retrieval, surveillance, and watermarking. In video retrieval,^{1, 2} frame matching is used to retrieve video clips, similar to a query clip, from a database. In video surveillance using multiple cameras,³ it is necessary to establish the correspondences in time and space to combine asynchronous multiview sequences. In video watermarking,^{4, 5, 6} temporal synchronization should be established between the original and watermarked videos before the extraction of frame-dependent watermarks.

Video matching techniques have different accuracy requirements, depending on their target applications. In video retrieval,^{1, 2} video matching need not be accurate at the frame level. It is acceptable that a retrieved frame does not match a query frame exactly, as long as they contain similar contents. In contrast, in video watermarking, more accurate matching is required, and two video sequences should be synchronized at the frame level, since the matching is a preprocessing step before the extraction of frame-dependent watermarks.⁸ For instance, in Ref. 6, the pattern of skipped frames is employed as a watermark, and the accurate frame-level synchronization between an original video and its watermarked version is an essential step in watermark detection.

In watermarking applications, Delannay, Roover, and Macq⁴ used an affine model to align video sequences. An affine model, however, cannot effectively describe irregular frame insertion and removal as well as frame shuffling, which are employed to attack watermarked video sequences. Cheng⁵ proposed a temporal registration algorithm to correct temporal misalignment, which occurs in frame rate conversion or video capturing. The two-frame integration model was employed to represent temporally overlapping frames in the acquisition procedures.

In video watermarking, the original video can be modified by various temporal attacks, such as frame removal, insertion, and shuffling. To establish frame-level synchronization between original and modified sequences in video watermarking applications, we propose a dynamic programming algorithm that matches each frame in the modified sequence to the corresponding frame in the original sequence. Although Ref. 5 also employed dynamic programming to match two sequences, they used only frame dissimilarity in the matching. On the other hand, we introduce the notion of adaptive unmatched cost in addition to the matching cost to achieve more accurate matching. Moreover, the unmatched cost is used to deal with frame shuffling attacks, as well as frame removal and insertion attacks.

2.

Matching Function and Matching Cost

Suppose that a video clip $\mathbf{X}=\{X_1,\dots ,X_{l_X}\}$ , where $X_j$ denotes the $j$ ’th frame, is modified from the original clip $\mathbf{Y}=\{Y_1,\dots ,Y_{l_Y}\}$ . A frame $X_j$ may be different from any frame $Y_k$ in the original clip, since the clip $\mathbf{X}$ may be a compressed version of $\mathbf{Y}$ . Moreover, some frames can be removed from or inserted into $\mathbf{X}$ , and then the resulting frames can be shuffled. We assume that the number of removed frames is less than a threshold ${\nu }_R$ . Similarly, let ${\nu }_I$ and ${\nu }_S$ denote the maximum numbers of inserted frames and shuffled frames, respectively.

We say that a frame $X_j$ in $\mathbf{X}$ matches a frame $Y_k$ in $\mathbf{Y}$ if $X_j$ originates from $Y_k$ . On the other hand, $X_j$ is called an unmatched frame if $X_j$ does not match any frame in $Y$ . Then, the temporal modification of a video can be represented by a function on the space of frame indices. Specifically, we define the matching function $\lambda$ as

Table 1

A matching function λ(j) that describes the temporal alignment between two sequences.

Let $d_m(j,k)$ denote the matching cost between two frames $X_j$ and $Y_k$ , which measures the dissimilarity between $X_j$ and $Y_k$ . The mean squared error (MSE) is employed as the matching cost.

3.

Proposed Matching Algorithm

Given a video clip $\mathbf{X}$ and its original $\mathbf{Y}$ , we attempt to find a matching function $\lambda \left(j\right)$ , such that $Y_{\lambda \left(j\right)}$ in $\mathbf{Y}$ is identical or similar to $X_j$ in $\mathbf{X}$ for each $1⩽j⩽l_X$ . The simplest matching can be achieved by the local minimization of matching costs (LMMC) via

We propose a globally optimal matching algorithm that minimizes the total matching cost subject to the one-to-one matching constraint. First, we assume that the original video clip is temporally modified by frame removal and insertion attacks only, and find the best matching function ${\lambda }^{*}$ under this monotonicity assumption. Later, in the second phase, we detect frame shuffling attacks by further matching the unmatched frames of ${\lambda }^{*}$ without imposing the monotonicity constraint.

Assuming frame removal and insertion attacks only, the matching function can be estimated by minimizing the sum of the costs of matched frames and unmatched frames, given by

In Eq. 3, when $i$ frames, $\max \{l_X-l_Y,0\}⩽i⩽{\nu }_I$ , are inserted into $\mathbf{X}$ , there are $\left(\genfrac{}{}{0ex}{}{l_X}{i}\right)$ possible choices of unmatched frames and $\left(\genfrac{}{}{0ex}{}{l_Y}{l_X-i}\right)$ possible choices of matched frames. Therefore, the complexity of the exhaustive minimization in Eq. 3 is proportional to ${\sum }_{i=\max \{0,l_X-l_Y\}}^{{\nu }_I}\left(\genfrac{}{}{0ex}{}{l_X}{i}\right)\left(\genfrac{}{}{0ex}{}{l_Y}{l_X-i}\right)$ , which is too demanding in most applications.

To reduce the complexity, we minimize the total cost function in Eq. 3 based on dynamic programming. The dynamic programming method in this work is similar to that for computing the Levenshtein distance, also called the edit distance, between two text strings.^{10, 11} The edit distance counts the minimum number of letter substitutions, insertions, or removals to convert a text string to another string. Similarly, the proposed algorithm matches a video sequence to another sequence by considering frame insertions and removals. However, whereas the distance between two letters is binary (identical or not), the distance between two frames should represent the similarity of those two frames. Thus, as compared with letter insertions or removals, it is more difficult to identify frame insertions or removals. To overcome this difficulty, the proposed algorithm defines the matching cost as MSE and the unmatched cost in Eq. 4 and minimizes the total cost in Eq. 3 to achieve reliable video matching.

Suppose that the first $j$ frames of $\mathbf{X}$ are obtained by removing $r$ frames from the first $k$ frames of $\mathbf{Y}$ and then inserting $i$ new frames. Note that $k=j-i+r$ , since $(j-i)$ frames in $\mathbf{X}$ match $(k-r)$ frames in $\mathbf{Y}$ . Let $s(j;i,r)$ denote the minimum sum of the matching costs for the first $j$ frames in $\mathbf{X}$ when $i$ frames are inserted and $r$ frames are removed.

We compute $s(j;i,r)$ recursively. First, we initialize $s(j;i,r)=\infty$ if $j<1$ , $i<0$ , or $r<0$ with the exception $s(0;0,0)=0$ . Then, $s(j;i,r)$ can be obtained by finding the minimum among three cases

Next, let us consider frame shuffling attacks, in addition to frame removal and insertion attacks. In Eqs. 3, 5, we impose the monotonicity constraint that the matching function for matched frames is monotonically increasing, and shuffled frames hence can be classified as unmatched frames. Therefore, when $X_j$ is classified as unmatched, it can be further matched to a frame in $\mathbf{Y}$ , which is not matched by the function in Eq. 3. More specifically, ${\lambda }^{*}\left(j\right)$ is refined by

4.

Experimental Results

The performance of the proposed algorithm is evaluated using five common intermediate format (CIF) sequences Foreman, Paris, Mobile, Tempete, and Carphone, each of which consists of 100 frames. We also use 33,220 video clips, selected from 20 Korean movies.¹² Each clip consists of 100 frames of resolution $360\times 240$ , and has a frame rate of either 24 or 30 frames per second. Thus, 3,322,500 frames are used in total.

To match a video clip with another clip, we minimize the total cost in Eq. 3. It can be shown that the dynamic programming method requires also $O\left(l_X{l}_Y\right)$ recursion steps. We use a personal computer with an Intel Pentium D $3\text{-}\mathrm{GHz}$ processor for simulations. To match a video clip of 100 frames to another clip, the proposed algorithm requires about $5.32\mathrm{ms}$ for the dynamic programming method.

Table 2 shows the matching error probabilities. A matching error probability is defined as the rate of an estimated matching function being different from the true matching function. The sequences are compressed by the H.264/AVC standard with QP 20 and 35, which yield about 42.0 and $30.8\mathrm{dB}$ peak signal-to-noise ratios (PSNRs) on average, respectively. The sequences then go through frame removal attacks $\left(R\right)$ , frame insertion attacks $\left(I\right)$ , and frame shuffling attacks $\left(S\right)$ . The numbers of removed and inserted frames are randomly selected from 1 to 10 and from 1 to 3 ( ${\nu }_R=10$ and ${\nu }_I=3$ ), respectively. An inserted frame is constructed by averaging two adjacent frames in the original sequences. For shuffling attacks, the number of pairs of adjacent frames is randomly selected from 1 to 3 $({\nu }_S=3)$ , and each pair of frames swaps their places.

Table 2

Comparison of matching error probabilities when a video is modified from its original through frame removal (R) , insertion (I) , shuffling (S) , and data compression attacks.

We compare the performance of the proposed algorithm with those of Cheng’s algorithm⁵ and the LMMC approach. In Ref. 5, frame shuffling attacks are not considered, and the matching fails under these attacks. Since the weights for the two-frame integration model are overparameterized for insertion attacks, matching errors occur even when QP is as low as 20. The LMMC approach is also vulnerable to insertion attacks, since it simply searches the best matching frame for each individual frame. On the other hand, the proposed algorithm provides much better performance by globally minimizing the total matching cost. For example, when QP is 35 and frame removal and insertion attacks are combined $(R+I)$ , the matching error probability of the proposed algorithm $(=0.10\%)$ is about 41 times lower than that of LMMC $(=4.11\%)$ and about 21 times lower than that of Cheng’s algorithm $(=2.12\%)$ . As QP increases, the qualities of modified videos degrade and the matching error probabilities get higher. However, the proposed algorithm provides significantly better performance than the conventional algorithm, even in these severe conditions.

5.

Conclusion

We propose a temporal alignment algorithm between two video sequences, when a video is modified from the other through frame removal, insertion, and shuffling attacks as well as data compression attacks. We define a cost function for global matching errors and develop a dynamic programming algorithm to minimize cost efficiently. Experimental results show that the proposed algorithm provides a significantly lower probability of matching errors than the conventional algorithm.