Handbook of Video Databases: Design and Applications (Internet and Communications)

5. Query Formation and Resolution Using the Model

The users may browse through the descriptions, set their preferences by model entities, and form complex queries that require matching a low-level criterion in one part of the scene and high-level constraints in another. We employ a single graph-based query formation and resolution framework for any of the above uses. In the framework, the queries are represented by graph patterns that can be formed by either editing an example description or the database scheme. In order to facilitate query formation by the user, we further define abstract models (model templates) as special graph patterns for certain events in a specific sports type. Then, the user can also form queries by editing an abstract event model from the model database. The relevant sections of the database can be retrieved by matching the query graph pattern with the graphs of the descriptions in the database. The similarity of the query graph pattern to each of the matching subgraphs in the database is calculated by matching both high- and low-level attributes.

5.1 Graph-Based Query Formation

The queries are represented by graph patterns, which are defined as instances of the database model with the exception of null or undefined values for some attributes [39]. Graph patterns can be obtained by editing the database scheme (or an example description) or by using abstract models, defined below. Editing the database scheme refers to modifying the model diagram in Figure 6.1 by copying, duplicating, identifying, and deleting some part of the scheme. Therefore, graph patterns conform to the database scheme, and syntactically incorrect queries cannot be formulated. In certain structured domains, such as sports, the number of popular queries may be limited, and model templates, called abstract models as special graph patterns, can be defined for specific events. An abstract model is the abstraction of a specific model instantiation from specific object, location, and time instances; for example, Figure 6.3 is the abstract model of free kick event. An abstract model conforms to the database scheme; therefore, the queries based on abstract models are also syntactically correct. A similar concept of abstraction has been included in the MPEG-7 standard, and it is called "formal abstraction" [24]. Browsing is a special case of querying with graph patterns where the query is limited to one or more specific vertices [40]. In Figure 6.18, the graph pattern refers to the query: "find all events where the ball object has a similar trajectory to the example trajectory and the event precedes header and score events." The queried event name is not important; hence, it is not specified (shown by asterisks). The low-level query constraint is specified as an EMU attribute of the actor entity. In addition to enabling the formation of a rich set of queries, the integration of low-level features in the queries removes the dependency to the annotations that may be subjective.

Figure 6.18: The query graph pattern for "find the events where the ball object has a similar trajectory to the example and the event precedes header and score events"

5.2 Query Resolution by Graph Matching

Queries are resolved by matching the query graph with the sub-graphs of the descriptions in the database. In our application, we use the following model-based constraints to reduce the search space in graph matching: 1) The type of vertices in the description is known to be an event, an object, or an actor with each type having distinguishing features from the others, and 2) The directed edges correspond to different types of relations with type-specific semantic-level and/or low-level attributes. A query as a graph pattern consists of a set of constraints that may be related to vertices, edges, or both. The proposed algorithm starts the search from the vertices and finds a set of matching vertices for each query vertex in each distinct database description. Then, starting with the most constrained query vertex, assumed to be inversely proportional to the number of matching vertices, edge constraints are compared. That is, the algorithm looks for the combinations of the resulting set of vertex matches for the edge constraints. The steps of the recursive search for graph matching are as follows:

Graph Matching Algorithm:

• For each query vertex, find the initial set of matching vertices using the query constraints

• Rank the query vertices from the one having the least number of matches to the most

• Check the edge constraints to find the combinations of the vertices that match the query graph. For this purpose, use a recursive search from the most constrained vertex to the least constrained one and return whenever an edge constraint fails

We use the vertex and edge attributes defined below to find the isomorphism or similarity between two graphs:

• Vertex Matching: When the graph element is a vertex, we have three choices: i) an event, ii) an object, or iii) an actor vertex. Therefore, the most distinguishing attribute for a vertex in finding a match is its type. Then, we evaluate the other specific attributes defined below for each vertex type:

  • Event: Event vertices are evaluated by the equivalence of the name attribute, such as goal in soccer and fumble in football.

  • Actor: The match between two actor vertices is found by comparing two high-level attributes: linguistic role and semantic role. Low-level descriptors for object motion can also be used for the same purpose.

  • Object: Object vertices are compared by the equivalence of the object class and the specified attribute-value pairs.

• Edge Matching: The match between two edges is defined by the equivalence of the semantic and segment relations.

We compute two different cost values to rank the matching graphs:

• Semantic Cost: Semantic cost of a match is determined as the cost due to the mismatches in the graph structure, in particular, those of event structure. That is, the graphs that differ in temporal structure of events will be penalized by the cost of the mismatch. The semantic cost value is defined as the sum of the cost of insertions and deletions of event vertices and temporal event edges to match each query event vertex:

  (6.2)

• Syntactic Cost: The syntactic cost is defined as the dissimilarity of two graphs due to their low-level features. As explained in Section 3, in the proposed model, low-level features are defined for actor vertices and actor-actor links as object motion parameters, such as object trajectories and spatio-temporal object interactions, respectively. The metrics to measure the dissimilarity (or similarity) of object motion descriptors are well defined and widely available in the literature. Binary decisions, as matching or not, for spatio-temporal relations are given by the equality of the corresponding reactions in the specified time interval.