Mining Video Associations for Efficient Database Management

1 Introduction

Since the 1990s, data mining has been a very active area for re­ search and applications. Many successful techniques have been implemented through academic research and industrial applications [Agrawal and Srikant, 1994][Agrawal and Srikant, 1995][Wu, 1995] [Han and Kamber, 2000]. However, these approaches deal with various databases (like transaction datasets) in which the rela­ tionship between data items is explicitly given. Video and image databases are different from these databases. The most distinct feature of video and image databases is that the relationship be­ tween any two of their items cannot be explicitly (or precisely) figured out. This inherent complexity of the multimedia data has suggested that mining knowledge from multimedia materials is even harder than from general databases [Zhu et a!., 2003 ][Thuraisingham, 2001 ][Zaiane, et a!., 1998]. Generally, there are two types of video mining techniques: (I) special pattern detec­ tion [Zhu eta!., 2003], which detects some predefined special pat­ terns; and (2) video clustering and classification [Oh et a!., 2002][Pan and Faloutsos, 2002], which clusters and classifies video units into different categories.

Different from these two types of video mining schemes, we address a new research area of video mining, video association mining, in this paper, where associations from video units are used to explore video knowledge. We will present a definition for video associations, and design a video association mining algorithm. As shown in Fig. I, we first segment a video sequence into shots and cluster shots into groups. Then, we assemble the class information of each shot to form a shot cluster sequence. We mine sequential associations from the sequence to find clusters with strong correla­ tions and take strongly correlated clusters as video associations.

2 Video Association Mining

Generally, most videos from our daily life are edited by editors, where various kinds of shots are packed as scenes to convey video scenarios, as shown in Fig. 2. There are two typical video scenes: (I) scenes that consist of visually similar shots, as demonstrated in Fig. 2(a); and (2) scenes that consist of visually distinct shots, as shown in Fig. 2 (b). In the first type of scenes, most video shots are visually similar. Take Fig. 2(a) as an example, if we denote each of the shots by "A", all shots form a sequence "AAAAAAA", and the self-coherence of "A" indicates an association of itself. We name this type of association as an intra-association, i.e., all items in the association are the same. In the second type of scenes, sequential associations exist too. In Fig.2(b ), if we denote the actor by "A", the actress by "B" and the shot containing both of them by "C", all shots form a sequence "ABABACAB". The co-occurrence of "A" and "B" implies an association. We name this type of association as an inter-association, i.e., items in the association are different.

Based on the above observations, we define a video association as a sequential pattern with {X1 . .X; . .XL; X'< X' for any i < j}, I J where X; is a video item (see definition below), L denotes the length of the association. x: denotes the temporal order of X;, and X' <X' indicates that X; happens before ~- For an inter-, J association, X1n .. IIXL=0; and for an intra-association, X1n .. IIXL=Xk> k=V[1,L]. For simplicity, we use {X} as the abbre­ viation of an association.

Due to the fact that the temporal information in a video se­ quence plays an important role in conveying the video content, we integrate traditional association measures (support and confidence) and video temporal information to evaluate video associations. Some definitions are given as follows:

• An item is a basic unit, which denotes a shot cluster.
• Given a shot cluster sequence, the temporal distance (TD) be­ rween rwo items is the number of shots berween them. E.g, given sequence "ABDEC", the temporal distance of "AB" is TD(AB)=O, and for "AC" is TD(AC) =3.
• An L-ltemAssociation is a video association that consists of L sequential items. E.g., "ABC" is a 3-ltemAssociation.
• The L-ItemSet is an aggregation of all L-ltemAssociations, with each of its members being an L-ItemAssociation.
• Given a temporal distance threshold (TD1) TDT=T, the tempo­ ral support (TS) of an association {X1 ... .XL} is defined as the number of times that this association appears sequentially in the sequence. In addition, each time this association appears, the temporal distance berween any two neighboring items of the association should be no more than T shots. That is, given any X; andX;+I (i ~ 1, i+l -:5,L), TD(X;. X;+1)-::;, T.
• Given TDT=T, the confidence of an association {X1 · .X; . .XL} is defined as the ratio between the temporal support of {X} when TDT=T and the number of maximal possible occurrences of the association {X} . For an inter-association, the maximal possible occurrence of the association is determined by the number of occurrences of the item with the minimal support. Its confi­ dence is defined by Eq.(l). For an intra-association, all items are the same, the maximal possible occurrence of the associa­ tion is determined by the support of the item and the associa­ tion length (L), as defined by Eq.(2), where (x) indicates the maximal integer which is not larger than x.

• The L-LltemSet is an aggregation of all L-ltemAssociations that each of their temporal support is no less than a given threshold.

2.1 Association Mining Algorithm

Our video mining algorithm consists of the following phases:

1. Transform Phase. Given video V, this step transforms V from continuous frames into a sequence dataset D.
2. L-LitemSet Phase. In this phase, we mine both intra­ associations and inter-associations from D. We first find the L­ ItemSet, and then use L-ItemSet and a user-specified threshold to find L-LitemSet. We will iteratively execute this phase until no more non-empty L-LitemSet can be found.
3. Collection & Pruning Phase. This phase prunes and selects valuable associations from all L-LitemSets.

Since Phase 3 is quite obvious, we focus on Phases I and 2. Meanwhile, due to the fact that all items in intra-associations are the same, mining this. type of associations is relatively easy, we hereby introduce mechanisms on mining inter-associations only.

In the transform phase, we adopt some video processing tech­ niques to segment a video sequence into shots, and execute shot clustering to explore relationships among shots. To detect video shots, we use our existing algorithm in [Zhu eta!., 2003] . For the sake of simplicity, we select the I O'h frame of each shot as its key­ frame. After the shot segmentation, we adopt a modified split-and­ merge clustering algorithm [Horowitz and Pavlidis, 1974] to clus­ ter video shots into groups where visually similar shots are first merged into groups and the groups with large visual variances are split into two clusters. After shot clustering, each shot will receive a class label, we sequentially aggregate the class information of each shot by its original temporal order to form a shot cluster se­ quence D. As shown in Fig. 2, each icon image denotes one shot and the letter below it indicates its class label, and the acquired shot cluster sequences are given in Fig. 2 (c). Table 2 gives an example of the video association mining, where the first column presents the video shot cluster sequence.

In the L-LitemSet phase, we use the large ltemSet from the previous pass to generate the candidate ltemSet and then measure their temporal support by making a pass over the database D, as shown in Fig. 3. At the end ofthe pass, the support of each candi­ date is used to determine the L-LitemSet. The candidate generation is similar to the method in [Agrawal and Srikant, 1995]. It takes the set of all k-1-/temAssociations in Lk-I and all their items as input, and works as shown in Fig. 4. Take the 3-LitemSet L3 in the fourth column of Table 2 as an example. If L3 is given as the input, we will get the ltemSet shown in the fifth column after the join. After pruning out sequences whose subsequences are not in L3, the sequences shown in the sixth column are left. E.g., {ABDC} is pruned out because its subsequence {BDC} is not in L3.

1. Given user specified TDTand TS thresholds.
2. / 1={1-/temSet}; L1={1-LltemSet}; II Find {1-L/temSet} by using {1-/temSet} and the user-specified thresholds.
3. For( k= 2; Lk_1 t:0; k++) Begin:
4. h=New candidates generated from Lk-I (see Fig. 5).
5. For each k-ltemAssociation in h, we count its temporal support by considering the user's specification with TDT.
6. Lk=Candidates in h with the minimum temporal support. End

Fig. 3 The L-LitemSet Phase of the mining algorithm

• (1). Join the items of associations in Lk-I·
• (2). Insert the join results into h select {p.ItemJ. .. , p.ltemk-J.q.ltemk-I} from {Lk_1.p, Lk-f-q, p ~q} where {p.Item1=q.Item1& .. & p.Itemk_2=q.Itemk_2 }
• (3). Delete any member xE Jk such that some {k-1-/temAssociation} ofx is not in Lk-I·

Fig. 4 Candidate generation

In Fig. 3 and Fig. 4, Lk denotes the k-LltemSet and h the k-ltemSet.

3 Experimental Results and Discussion

Traditional video database systems use video shots as the units to index and manage video data where the visual similarities among shots arc used to construct the index structure. Unfortunately, a single shot which is separated from its context has less capability to convey semantics; Moreover, the index considering only visual similarities ignores the temporal information among shots. Conse­ quently, the constructed cluster nodes may contain shots that have considerable variances both in semantics and visual content and hereby do not make much sense to human perception. Accord­ ingly, a semantic video database management framework has been presented [Zhu et a!., 2003] where video semantic units (events, scenes or other scenario information) are used to construct a data­ base index. To facilitate this goal, one of the most important tasks is to detect the video semantic units. In this section, our experi­ mental results will demonstrate that the proposed video association mining technique could be used to explore semantic units for the management of video database systems.

To evaluate the ability of video associations in addressing local event and scenario information and figure out the relationship be­ tween TDT and the mined associations, we set TDT with different values T (T=I, 3, 5, 7, 9 and oo) and assess the associations. For each acquired association, we scan the dataset to check whether all items in the association belong to the same scene each time when the association appears. We define the Scene Coverage (SC) of an association as the ratio between the frequency of the association's items belonging to the same scene and the frequency of the asso­ ciation's appearance. The higher the SC, the better the association addresses the scene and event information. On the other side, with an adopted temporal support, the smaller the TDT, the less is the number of mined associations. This indicates that the TDT also acts as a factor for pruning associations. We hereby define the Pruning Rate (PR) as the ratio between the number of associations when TDT is T (T=1, 3, 5, 7, 9) and oo. We have performed our experiments with 5 news videos and 20 medical videos (about 700 minutes), and the results are given in Table 2.

Table I demonstrates that when the TDT increases, the mined associations become worse in addressing the local sce­ nario and event information. One reason for this declination is that the clustering process may cluster semantically unrelated shots into one group, and consequently, when evaluating the scene coverage, the items of an association would come from different events. However, with relatively small TDT values, this type of errors can be reduced, because items with a small temporal distance would more likely belong to one semantic unit. On the other hand, Table I also indicates that the smaller the TDT, the less is the number of mined associations, but the better are the mined associations in addressing event and sce­ nario information. Depending on the user's objectives of asso­ ciation mining, a balance between the number of associations and the SC is necessary to select a reasonable value for TDT.

4 Conclusions

To facilitate video database management, we have explored a new research area of video data mining. A video association mining algorithm has been proposed. Given video V, we first transform it from sequential frames to a relational dataset by shot segmentation, clustering, and constructing a shot cluster sequence. The video mining scheme mines sequentially associated video items from this sequence. In addition to using the traditional association measures, we have integrated temporal features among video shots into the video association evaluation. The experimental results have dem­ onstrated the ability of our mined associations in addressing se­ mantic information for video database management.

Acknowledgments

This research has been supported by the U.S. Army Research Laboratory and the U.S. Army Research Office under grant num­ ber DAAD 19-02-1-0178.