With the rapid growth of multimedia data, there is an increasing need for robust multimedia database model. Such a model should be able to index spatio-temporal data thus efficient access to data whose geometry changes over time can be provided. In this paper, a spatio-temporal multimedia database model for managing transportation surveillance video data is proposed. The objective is to build a spatio-temporal database schema for transportation surveillance videos, in which queries can be answered easily and efficiently. The proposed spatio-temporal model for transportation surveillance videos combines the strength of two general-purpose spatio-temporal multimedia database models - the Multimedia Augmented Transition Network model (MATN) and the Common Appearance Interval (CAI) model. While MATN model is good at modeling the replay of the multimedia presentation and the spatial-temporal relations of semantic objects in the video, it is not efficient in modeling or querying the trajectories of moving objects. In the mean time, while Common Appearance Interval (CAI) model can be used to better answer trajectorybased queries, it explicitly stores the spatial relations of pairs of objects in the model, which is considered redundant in transportation video databases. The proposed model bases its structure on MATNs and adopts the concept of CAI to segment transportation surveillance videos. Since this model is motivated by transportation surveillance applications, it has some domain specific features. It models each traffic light phase in a MATN-like network and models the corresponding video segment using CAIs. In addition, CAIs are further divided into subintervals and modeled by the sub-network structure in MATNs. In this paper, the proposed model, together with a brief introduction of the vehicle extraction/tracking/classification, is presented with its formal definition and some sample queries. The advantages of our model in comparison with other models are also demonstrated.
specific data, there is still a need for designing domainspecific spatio-temporal models. In this paper, we proposed a spatio-temporal multimedia database model for storing, indexing, and querying transportation surveillance videos. It is worth mentioning that the proposed work focuses on designing a conceptual model, which serves as a basis for defining entities, attributes, and relationships. As this is our initial work, details such as GUI interface, physical layers, access strategy or operations will be addressed separately in our future work.
In our previous work, we proposed a vehicle
extraction, vehicle tracking, and vehicle classification
framework [
MATN model is good at modeling the replay of multimedia presentations. It also provides an efficient mechanism in modeling the spatial relations of semantic objects in the video. One disadvantage of MATN is that it cannot be efficiently applied to modeling the trajectories of moving objects. However, trajectories of vehicles are often queried in a transportation video database. Therefore, in our model, MATN is adjusted to suit our specific needs.
The MATN model proposed by S.-C. Chen [
Some background information on transportation surveillance video processing is introduced in Section 2. The proposed model is formally defined in Section 3. Section 4 shows query methods and some sample queries. Section 5 analyzes the advantages of the proposed model. Section 6 concludes the paper.
In this section, the processing of transportation
surveillance videos is introduced to provide some
background information on building an intelligent
transportation system. In our previous work [
(xcentroid, ycentroid) (xhigh, yhigh)
(xlow, ylow) Figure 1 An example vehicle segment.
The framework in [
With this framework, lots of useful data and information is generated. This provides a basis for an intelligent transportation system. The whole process is automatic. In this paper, a spatio-temporal database model is proposed to further organize, index and query these information.
While the proposed model is a combination of S.-C. Chen
et al.’s MATN model [
Multimedia Augmented Transition Network (MATN)
model originates from the Augmented Transition Network
(ATN) [
MATN is a general purpose spatio-temporal model. To fit the specific needs of transportation video modeling, the original MATN model needs to be adjusted. This is for the ease of searching and querying the transportation video database. For example, velocity and driving direction are two very important properties of a moving vehicle but they are not explicitly modeled in a MATN model. In L. Chen’s CAI model, a concept called Common Appearance Interval is defined to model an interval where a certain set of objects appear in the frame together. We incorporate this concept into our model.
CAIs can be automatically generated from the tracking and segmentation phase.In the proposed model, moving vehicles are explicitly modeled, which correspond to the moving objects in CAI model. A Common Appearance Interval is further broken down into sub-intervals in which the relative positions (as defined in MATN models) of vehicles remain unchanged.
In MATN models, the spatial relations of moving vehicles are recorded based on 27 three dimensional relative positions. That is, the 3-D space is evenly divided into 27 positions with one of them being the reference position. The coordinates of moving vehicles are then compared with this reference position to decide their relative positions. The details of these 27 positions are shown in Figure 2, where position #1 is the reference position. The first and the third columns indicate the relative position numbers, while the second and the fourth columns are the relative coordinates. (xt,, yt, zt) and (xs, ys, zs) represent the X-, Y-, and Z-coordinates of the reference position and the position of a vehicle object, respectively. The ‘§ ’ symbol means the difference between two coordinates is within a threshold value. For example, the relative position number 25 indicates an object’s X- and Y-coordinates (xs and ys) are greater than that (xt, yt) of the reference position, while their Zcoordinates are approximately the same. We adopt this approach in modeling the spatial relations of moving vehicle objects. In the proposed model, the center of a video frame is chosen to be the reference position and each vehicle object is mapped to a point object represented by its centroid as illustrated in Figure 1. The centroid point of each vehicle object is then used to derive the relative position of that object to the reference position. However, it is worth mentioning that we only use the 2-D relative positions in MATN models as the z values (or the depth information) of all vehicle objects in a 2-D video sequence are zeros. Therefore, there are only 9 relative positions in our model, which are used to record the relative positions of vehicles in a video frame at a coarse granularity. More or fewer numbers may be used to divide an image or a video frame into sub-regions to allow more fuzzy or more precise queries as necessary.
For this specific application, the driving direction of a vehicle is also recorded. However, there is no need to record this information for all video frames as this will introduce a large amount of inter-frame redundancy. Only the changes of directions between intervals are computed and recorded in the proposed model.
Before the formal definition of the proposed model is presented, we first define the terms and concepts that will be used in the rest of the paper.
Definition 1. A Vechile Object (VO) is a 3-tuple (OID, MBR, VSFs). ID is the unique identifier of a distinct vehicle in the database. MBR is the Minimal Bounding Rectangle of the Vehicle Object. (xlow, ylo, zlow) and (xhigh, yhigh, zhigh) are the 3-D coordinates of the bottom right point and the upper left point of the rectangle. The coordinates of the centroid of the MBR is used to determine the object’s relative position in 27 positions.
However, since only 2-D information is available, we will
use the 9 positions as shown in Figure 2 only. VSFs stands
for Vehicle Segment Features, which can be used for
vehicle classification and tracking purpose. In our
previous work [
It includes the allowed driving directions, the duration of the phase, etc.
Definition 3. Traffic Video Clip (TVC) is a contiguous trunk of traffic video. It consists of TLPs and can be denoted as a 2-tuple (CID, META). CID is its clip ID.
META is the meta-data of this clip which can include such information as the time the clip is shot, the road/intersection location, camera settings, etc.
TVCs, TLPs and VOs are the constituting units of a transportation surveillance video database with VO being the smallest unit. Next we will give the formal definition of the proposed model and explain in detail how it can be used for transportation video database modeling.
Number Relative Coordinates Number Relative Coordinates Number Relative Coordinates 1 xs§ xt, ys§ yt, zs§ zt 10 xs<xt, ys§ yt, zs§ zt 19 xs>xt, ys§ yt, zs§ zt 2 xs§ xt, ys§ yt, zs<zt 11 xs<xt, ys§ yt, zs<zt 20 xs>xt, ys§ yt, zs<zt 3 xs§ xt, ys§ yt, zs>zt 2 xs<xt, ys§ yt, zs>zt 21 xs>xt, ys§ yt, zs>zt 4 xs§ xt, ys<yt, zs§ zt 13 xs<xt, ys<yt, zs§ zt 22 xs>xt, ys<yt, zs§ zt 5 xs§ xt, ys<yt, zs<zt 14 xs<xt, ys<yt, zs<zt 23 xs>xt, ys<yt, zs<zt 6 xs§ xt, ys<yt, zs>zt 15 xs<xt, ys<yt, zs>zt 24 xs>xt, ys<yt, zs>zt 7 xs§ xt, ys>yt, zs§ zt 16 xs<xt, ys>yt, zs§ zt 25 xs>xt, ys>yt, zs§ zt 8 xs§ xt, ys>yt, zs<zt 17 xs<xt, ys>yt, zs<zt 26 xs>xt, ys>yt, zs<zt 9 xs§ xt, ys>yt, zs>zt 18 xs<xt, ys>yt, zs>zt 27 xs>xt, ys>yt, zs>zt 13 10 16 4 1 7 22 19 25
Y
Z X
For convenience, we call the proposed model TVDM (Transportation Video Database Model). TVDM can be formally defined as follows.
Definition 4. A TVDM is an 8-tuple ( 6 m , 6 s , : , G , Qm , Qs , F, S ). 6 m , 6 s are the alphabets of the traffic video streams that can be expressed by regular expressions. The meaning of the regular expression symbols used in this model is illustrated in Table 1.
Table 1. Meaning of Regular Expression Symbols
Symbol Unquoted Characters ‘…’ = […] {…}+ {…} & …|… ; , [c1 – c2]
Meaning Non-terminal symbols
Terminal symbols
Is defined as
Optional symbols One or more repetitions Zero or more repetitions
Concurrent
Or Rule terminator
Concatenation
ASCII Characters
1. 6 m is the Transportation Video Stream alphabet in the
main network. A Transportation Video Stream in the main
network is a Common Appearance Interval (CAI) as
proposed in L. Chen’s CAI model [
CAI = CID, PID, CAID, {OID, [‘&’]}; CID = ‘C’, {‘0’-‘9’}; PID = ‘P’, {‘0’-‘9’}; CAID = ‘CA’, {‘0’-‘9’};
OID = ‘O’, {‘0’-‘9’}; where ‘&’ means concurrent appearance of multiple vehicle objects, CID, PID, CAID, and OID stand for the ID’s of Clip, Phase, CAI and Object(s). 2. 6 s is the Transportation Video Stream alphabet in the sub-network. A Transportation Video Stream in the subnetwork corresponds to a sub-interval of a CAI. In the proposed model, sub-network models a CAI in a way that a CAI is further divided into sub-intervals. In each subinterval, the relative positions of all objects in the CAI remain unchanged. We call such an interval CAIsub. Therefore, we have
CAIsub = CID, PID, CAID, CAISUBID, {OID, (‘1’ | ‘2’ | …| ‘27’), (‘N’ | ‘NW’ | ‘NE’ | ‘S’ | ‘SW’ | ‘SE’ | ‘E’ | ‘W’), [‘&’]}; CAISUBID = ‘CAS’, {‘0’-‘9’};
From the above regular expression, we can see that in each CAIsub, a vehicle object is denoted by an object ID followed by a number and a symbol. The number is one of the 27 3-D relative positions as illustrated in Figure 1. (‘N’ | ‘NW’ | ‘NE’ | ‘S’ | ‘SW’ | ‘SE’ | ‘E’ | ‘W’) denotes the moving direction of that vehicle object, where N stands for north, NW stands for northwest and so forth. The driving direction can be induced from the change of relative positions between sub-intervals. This direction information is kept here for easily capturing the trajectory of a vehicle which is frequently queried in transportation video database. 3. : is the special input symbol alphabet. : = {&&, ||, ~, *, D ,E }. The meaning of these special symbols is shown in Table 2. These symbols are used in querying the transportation video database.
Symbol && || ~ * 4. Qm is the set of nodes (states) in the main network. Each node in Qm is defined as a 4-tuple (NID, FID, OIDin, OIDout). NID is the node ID. FID is the frame ID. This frame is the starting frame of the next CAI that is on the outgoing arc of this node (state). OIDin is the list of IDs of the vehicle objects that newly appear in the next CAI. OIDout is the list of IDs of the vehicle objects that disappear in the next CAI. However, these two lists cannot be both empty. If both of them are empty, there is no new CAI generated. 5. Qs corresponds to a sub-network. It is defined as a 2tuple (NIDsub, FID). NIDsub is the ID of a node in the subnetwork. Each node is associated with a FID which is a frame ID. This frame is the starting frame of the next CAIsub that is on the outgoing arc of this node (state). 6. G is a set of the transition functions from one node (state) to another. In the proposed model, two nodes are connected by an arc that is denoted by a transportation video stream. G : Qm u CAI o Qm or Qs u CAI sub o Qs .
Q . s
Q . s
In this section, the above-defined TVDM is applied to model a transportation video database. Details will be explained in an example shown in a TVDM diagram (Figure 3).
In the diagram, circles are nodes/states of the network. For simplicity, only the node ID is shown in the figure. However, the identification of a node is also dependent on the traffic light phase and the video segment it is in. The network flow can be easily traced by following the arcs (arrows) in the diagram. The solid arcs are the flow in the main network while the dotted ones are in the subnetwork. Each arc can be distinguished by the unique traffic media stream on it. Again for simplicity, the full name of each vehicle object in the video streams (CAI/CAIsub) is not given in the figure. Instead, characters such as ‘A’ and ‘B’ are used as the symbols to represent the vehicle objects.
In this example, a traffic video clip shot at a major intersection is modeled. A video frame is divided into nine 2-D sub-regions. The entire traffic video clip is divided into phases according to the change of traffic lights. Each phase can be modeled with a network as shown in Figure 3. By connecting each such network with an arc, the network of the entire traffic video clip can be set up. There are two key frames shown in this figure. FID2, FID3 are the IDs of the two frames which are the turning points of two consecutive CAIs. Starting from the node NID3, two new vehicle objects (E and F) move into the scene, signifying the end of the previous CAI and the beginning of the next CAI. The video stream between NID2 and NID3 is denoted as ‘A&B&C&D’, meaning the concurrent appearance of vehicle objects A, B, C and D.
In the sub-network originating from NID2 and ending at NID3, the corresponding traffic video stream (A&B&C&D) is further modeled by the vehicle objects’ relative positions and driving directions. Each such substream is called a CAIsub in which the relative positions of all vehicle objects remain unchanged. For example, the first arc of this subnetwork carries the sub-stream (A10E&B10E&C7E&D16E) in which vehicle A is in position 10 heading east; vehicle B is in position 10 heading east; vehicle C is in position 7 heading east; vehicle D is in position 16 also heading east. The arc originating from NIDsub2 is the sub-stream in which vehicle A is still in position 10 but heading northeast; vehicle B is still in position 10 heading east; vehicle C has moved to position 25 and is still heading east; vehicle D has moved to position 7 heading east. In this traffic light phase, we can tell that vehicles are either driving west/east or northeast i.e. left turn. By storing this information in the meta-data of each traffic light phase, the vehicles driving toward illegal directions can be easily detected.
In the following sections, we will discuss the transportation video database queries with the proposed model and explore some typical scenarios that may be of users’ interest in querying the transportation video database.
As introduced in Section 3.1, the inputs of MATN models are Multimedia Input Strings (MIS) together with condition/action tables. An MIS is to simulate the input of an ATN, which is a natural language sentence. In MATN, there are two types of basic inputs. One is “Control_Command”. It represents a control message that may occur during the multimedia presentation. A “Control_Command” is composed of conditions and actions. For example, a “Control_Command” can be “if the bandwidth < ș , display the compressed version of the specified media stream”. “Bandwidth < ș ” is the condition and “display the compressed version of the specified media stream” is the action. However, since multimedia presentation is not the focus of this paper, we concentrate on the other type of multimedia input strings which is “Media_Stream”. In this paper, we designed our own input strings by following the basic idea of MATN’s “Media_Stream”. It has been used in Section 3 to define the traffic video stream in a CAI or CAIsub.
Query strings are constructed based on Media_Streams. Query strings are used as the query input of the proposed model for querying the transportation video database. They include some special input symbols which have special meanings. The list of such symbols is in Table 2. For example, the symbol ‘||’ means one of the conditions on the two sides has to be satisfied. “CAI.(A&B)||CAI.(A&C)” is the query string used to find CAIs containing “A&B” or “A&C”. “CAIsub.(A*N&B*S)” means moving vehicles A and B are in the same CAIsub with A driving northward and B driving southward. “*” is the wild card symbol meaning that A and B can be in any relative positions. It is obvious that the first query string can easily find its matches (or no match) in the main network. The answer to the second query string can only be found in sub-networks of the model. However, the search shall start from the main network to find all video streams containing “A&B” and delve into the sub-network thereafter.
In [
In the proposed model, there are 6 classes of objects. The class names and properties are illustrated in Table 3, which is a generalization of the definitions introduced in Section 3. The first three classes are defined in Definitions 1, 2, and 3. The NODE class is defined in the formal definition of TVDM. For CAI/CAIsub class, there are four important properties i.e. the starting node (NIDs) and the ending node (NIDe) in the main network, the starting nodes (NID/NIDsub) in the main/sub network, and the traffic video streams in main/sub network as defined in Section 3.3. The FRAME class contains the actual video frames in the definition of nodes of the network. Its properties include FID (frame ID), the Video Clip it is in i.e. CID and the actual frame in the form of an image file. A VO object corresponds to a distinct vehicle object. For example, if there is a vehicle object A, A.OID is its ID. Note that the MBR property in VO class is actually a list <mbrf1, mbrf2, …, mbrfn> denoting the MBR property of a VO across the frames f1, f2, …, fn.
Table 3. Objects and Properties Class VO TLP TVC
NODE CAI/CAIsub FRAME
Properties OIDˈ MBRˈ VSF PID, PSF, PEF, META
CID, META
NID, OIDin, OIDout, FID NIDs, NIDe, NID/NIDsub, Media_Stream
FID, CID, Frame
In order to test the effectiveness of the proposed spatiotemporal model, some typical transportation video database queries are studied in this section. In transportation video database, the user is often more interested in retrieving video data through queries on vehicle objects’ properties and spatio-temporal relations among them.
This is a simple query in which only the information of spatial relations between vehicles is needed. Suppose this vehicle A is in position 1 and the target vehicle is B. The user can issue this query using a high-level language which will then be translated into a Media_Stream together with some arithmetic and logic operations:
CAIsub.(A1*&B4*)||
(CAIsub.(A1*&B1*)&&
(B.mbr(CAIsub.NIDsub.FID).y < A.mbr(CAIsub.NIDsub.FID).y))
The meaning of the above expression is that in some
CAIsub, vehicle object A is in position 1 and B is in
position 4 OR both A and B are in position 1 with the
ycoordinate of B’s centroid less than that of A’s. It does
not matter in what directions the two vehicles are moving.
In either of these two situations, B is considered north to
A. In the CAI model [
(Dist(A.mbr(CAIsub.NIDsub.FID).high, B.mbr(CAIsub.NIDsub.FID).low)<
Dist(C1, C2) is the subroutine to calculate the distance between two points whose coordinates are C1 and C2. A.mbr.high is the coordinates of the upper left corner of A’s MBR and A.mbr.low is the coordinates of the bottom right corner. The meanings of B.mbr.low, A.mbr.low and B.mbr.high are similar.
(A.OID Node1.OIDin)&&(Node2.OIDout A.OID) && (dist(A.mbr(Node1.FID).centroid, A.mbr(Node2.FID).centroid) / ((Node2.FID – Node1.FID) / TVC.META.FR) > T ) This query can be conducted on the main network. Node1 and Node2 are two nodes in the main network where one of the incoming vehicles in Node1 is an outgoing vehicle in Node2. From the frame IDs of these two nodes, the number of frames in between can be calculated, which is divided by the frame rate (TVC.META.FR). In this way, the average velocity of the vehicle when passing the intersection can be calculated. If a vehicle’s velocity is larger than ș , the allowed maximum speed, this vehicle is considered speeding. “dist(A.mbr(Node1.FID).centroid, A.mbr(Node2.FID).centroid)” is the subroutine that computes the travel distance of the vehicle in passing this intersection. “FR” in TVC.META.FR” means the frame rate (frs/sec) which is stored in the meta-data of that video clip.
Query Example 4. Find vehicles that take a U-turn. ((CAIsub1.(A*S)&&CAIsub2.(A*N))|| (CAIsub1.(A*N)&&CAIsub2.(A*S))|| (CAIsub1.(A*E)&&CAIsub2.(A*W))|| (CAIsub1.(A*W)&& CAIsub2.(A*E))|| (CAIsub1.(A*NW)&& CAIsub2.(A*SE))|| (CAIsub1.(A*SE)&& CAIsub2.(A*NW))|| (CAIsub1.(A*NE)&& CAIsub2.(A*SW))|| (CAIsub1.(A*NE)&& CAIsub2.(A*SW))) && ((CAIsub2.NIDsub.FID – CAIsub1.NIDsub.FID)/ TVC.META.FR < G )
In this query, the sub-networks are searched for any vehicle that drives toward opposite directions within reasonable time duration G when passing the intersection.
illegal direction in the traffic light phase when only north-bound and south-bound vehicles are allowed.
~(CAIsub.(A*S)||CAIsub.(A*N)) The south-bound and the north-bound allowed directions are information extracted from the meta-data of that traffic light phase. According to this information, we can detect vehicles driving at wrong directions by using similar queries as the above.
CAI.(A*)&& (dist(A.mbr (CAI.NIDs.FID).centroid, A.mbr (CAI.NIDe.FID).centroid) / ((CAI.NIDs.FID –CAI.NIDe.FID) / TVC.META.FR) == 0)
A vehicle’s velocity when passing the intersection cannot be zero. Otherwise, it is considered to have stopped. This can be used in identifying accidents or traffic jams. If one or more vehicles stay still for a long consecutive sequence of CAIs, there might be an accident or jam occurring in the intersection.
Query Example 7. Given a vehicle A that is driving eastward, find a vehicle B that overtakes A.
(CAIsub1.(A*E&B*E)&& (B.mbr(CAIsub1.NIDsub.FID).x<A.mbr(CAIsub1.NIDsub.FID).x)&& (B.mbr(CAIsub1.NIDsub.FID).y | A.mbr (CAIsub1.NIDsub.FID).y))&& (CAIsub2.(A*E&B*E)&& (B.mbr(CAIsub2.NIDsub.FID).x>A.mbr(CAIsub2.NIDsub.FID).x)&& (B.mbr(CAIsub2.NIDsub.FID).y | A.mbr (CAIsub2.NIDsub.FID).y)) The condition of an overtaking is that both vehicles are driving in the same direction with one behind another. The one behind overtakes the other by using an empty lane next to the lane both vehicles are on. Therefore, initially the x-coordinate of A (the leading vehicle) is larger than that of B’s. After overtaking, A’s x-coordinate is smaller than that of B’s. As the whole process may not finish within one CAIsub, CAIsub1, and CAIsub2 do not have to be two consecutive intervals (the same applies to all the previous queries.) However, we do need to find out the closest pair of CAIsub2 and CAIsub1, since any CAIsub after/before CAIsub2/CAIsub1 with A and B in it may also satisfy the above conditions.
The goal of this paper is not to design a master-of-all spatiotemporal database model, which is often not feasible. Instead, the proposed model in this paper is domain-specific. That is, it focuses on modeling the transportation surveillance video database. Targeting at the specific characteristics of transportation video, the proposed model can extract, index, and store the key information in the video. With these information stored in the database, transportation video data can be efficiently accessed and queried. This is one of the major advantages of our model.
The proposed model combines the strength of two general purpose spatio-temporal database models – MATN and CAI. We follow MATN’s basic structure as well as its way of modeling spatial relations among objects. The key concept in L. Chen’s model – CAI is also adopted in our model. This provides a way in partitioning transportation videos into “meaningful” segments and extracting the spatio-temporal information out of that. By combining the advantages of the two general-purpose models, our proposed model can better meet the needs of a transportation surveillance video database.
More specifically, motivated by this specific application, the proposed model only stores information that is frequently queried. Therefore, unlike CAI model, the proposed model does not record spatial relations between each pair of moving objects as this is not the frequent query type in the transportation video database. Furthermore, this will introduce redundancy into the database. The proposed model only records the relative spatial-relation of moving objects at a coarse granularity based on MATN model. The direction information of a moving vehicle is also recorded since this is a big concern of the user’s queries. For example, the illegal driving direction and U-turn can be easily detected in our model, while it is not that easy in either the MATN or the CAI model. In order to further extract useful information from the video, CAIs are further divided into sub-intervals in which all moving vehicles’ relative positions remain unchanged. We call this sub-interval CAIsub. This subdivision enables us to model the video streams at a finer granularity instead of simply using CAIs.
This paper proposed a spatio-temporal multimedia database model for transportation surveillance video. The formal definition of the model provides the basis for constructing a transportation surveillance video database, which is a key in building an Intelligent Transportation System. The proposed model combines the strength of two general-purpose spatio-temporal models –MATN and CAI. The proposed model is also adjusted to suit the specific needs of this specific application. To avoid redundancy, only the frequently queried information is stored in the database. Thus the extraction of key information from the transportation video is performed in a way to facilitate queries in this specific domain. With this model design, data indexing and database queries can be performed more efficiently.