Method and apparatus for classifying and querying temporal and spatial information in video

[0002] This application claims the benefit of Provisional application Ser. No. 60/117,906, filed Jan. 29, 1999.

[0003] The present invention relates to a method and apparatus for classifying and querying temporal and spatial information in media content; for representing objects, regions, events, actions, scenes, and visual features using symbols; for constructing symbol string descriptors that order the symbols in time or space to represent temporal or spatial information; for computing precedence template descriptor matrices from the symbol strings to describe the temporal and spatial ordering of the symbols statistically; for comparing precedence template descriptor matrices in order to compare the temporal or spatial information in the video or images; for classifying video and images using symbols strings and precedence template descriptors; and for querying video and images using symbol strings and precedence template descriptors.

[0004] The growing proliferation of digital photographs and video is increasing the need for more sophisticated methods for automatically analyzing, cataloging, and searching for digital representations of media content. The recent development of content-based query systems has advanced the capabilities for searching for images and video by color, texture, shape, motion and other features. Content-based methods are effective in allowing searching by feature similarity but are limited in capability of automatically deriving higher semantic level understanding of the content. Content-based methods can improve searching and attain better understanding of the content by capturing spatial and temporal information in addition to these features. In particular, effective methods are needed for describing scene and temporal information represented by the composition of region, objects or events in space or time.

[0005] Since humans perceive images by breaking the scenes into surfaces, regions, and objects, the spatial, temporal and feature attributes of the objects and the relationships to each other are important characteristics of visual information. Content-based retrieval systems that use global descriptors, such as color histograms miss the important spatial information. Furthermore, in a large collection of photographs, many regions recur, such as those that correspond to blue skies, oceans, grassy regions, orange horizons, mountains, building facades, and so forth. For photographic images, therefore, the detection and description of these regions and their spatial relationships is essential for truly characterizing the images for searching, classification and filtering purposes. Similarly, in video, the temporal relationships of events and objects are important features of the video content. Effectively describing the temporal composition features is essential for searching and filtering video by content.

[0006] There are many ways to capture the region information in images. Some recent approaches include 2-D strings, θ-R representations, local histograms, co-occurrence matrices, and region or event tables. However, composition descriptors such as the 2-D string and its variants are brittle in the sense that minor changes in region locations can greatly affect the comparison of two images. Descriptors such as θ-R and co-occurrence matrices are not widely applicable due to sensitivity to scale, which is problematic when comparing images of different resolutions or video segments of different temporal durations. Region or event tables are general in the sense that they capture the spatial and temporal locations, however, they do not provide a solution for measuring spatial or temporal similarity.

[0007] What is needed, therefore, and what is an object of the present invention, is to provide a system and method for characterizing media content by spatial and/or temporal ordering of regions, objects, or events.

[0008] It is another object of the invention to provide a system and method for classifying media content by the representations of spatial and/or temporal ordering.

[0009] Yet another object of the invention is to provide a system and method for searching stored media content by use of the classification by representations of spatial and/or temporal ordering.

[0010] In accordance with the aforementioned needs and objects, the present invention is directed towards an apparatus and method for classifying and querying temporal and spatial information in video; for representing objects, regions, events, actions, scenes, and visual features using symbols; for constructing symbol string descriptors that order the symbols in time or space to represent temporal or spatial information; for computing precedence template descriptor matrices from the symbol strings to describe the temporal and spatial ordering of the symbols statistically; for comparing precedence template descriptor matrices in order to compare the temporal or spatial information in the video or images; for classifying video and images using symbols strings and precedence template descriptors; and for querying video and images using symbol strings and precedence template descriptors.

[0011] Precedence Template (PT) descriptors of the present invention can be used for classifying or annotating image and video content by assigning each class of event, action, region or object a unique symbol and then building symbol strings to represent sequences in space or time. The symbol strings can be decoded using a library of annotated PT descriptors to automatically label the image and video content. Furthermore, the PT descriptors can be used for searching by sketch or searching by example where the search query input is converted to symbol strings, which are efficiently compared based on the presence and relative counts of PT descriptors. The Precedence Template (PT) descriptor can be used for classifying and querying video based on the spatial and temporal orderings of regions, objects, actions or events. Applied to video, the PT descriptors provide a way to compare the temporal order of events, actions, or objects such as those represented in a scene transition graph, key-frame list, or event string. Applied to images, the PT descriptors provide a way to compare the spatial arrangement of image regions or objects. By capturing the spatial and temporal relationships statistically, the PT descriptors provide a robust way to measure similarity in the presence of insertions, deletions, substitutions, replications and relocations of events, actions, regions or objects.

[0012] The invention will now be described in detail with specific reference to the appended drawings wherein:

[0013] FIG. 1A provides a symbol table with symbols corresponding to actions and FIG. 1B shows a comparison of temporal sequences of actions by comparison of two symbol strings;

[0014] FIG. 2 shows a comparison of symbol strings using PT descriptor matrices, wherein each entry in a PT descriptor matrix counts the number of times a symbol precedes another symbol in the symbol string;

[0015] FIG. 3A shows a table of symbols corresponding to scenes and FIG. 3B shows a scene transition graph which provides a way to describe the temporal transitions between scenes in video by providing a visualization of the scene lists;

[0016] FIG. 4 shows how a PT descriptor matrix can be automatically generated from images by segmenting the image, assigning a symbol to each region, scanning the regions, and counting the number of PT instances; and

[0017] FIG. 5 shows example graphical image queries in which the PT descriptors are generated by graphically placing color regions on a query grid.

[0018] Under the present invention, it is understood that a descriptor of interest for each region, object or event of the media content belongs to a finite and countable set of descriptors. Each descriptor is represented by a symbol and the implication is that the symbol dictionary is finite. By definition, therefore, a symbol s corresponds to the index value of an annotation or feature descriptor prototype in a finite dictionary of annotations or prototypes.

[0019] For example, in a dictionary of activities D_activity={run, swim, jump, rest}, each symbol corresponds to an activity as follows: s₀=run, and s₁=swim, and so forth. In a dictionary of color prototypes, D_color={red, blue, green, dark green, yellow}, each symbol corresponds to a color as follows: s₀=“red”, s₁=“blue” and so forth.

[0020] In order to represent the spatial or temporal order of the regions, objects, or events of media content, the present invention provides symbol strings. A symbol string S is a series of symbols S=s₀s₁s₂, . . . ,s_N−1that gives the order of the symbols in time or space, where S[i] and S[i+] are consecutive in time or space.

[0021] For example, in the temporal activity symbol string corresponding to the dictionary D_activity={run, swim, jump, rest}, symbol string S=s₀s₂s₁s₀s₃describes the order of activities, where the order is run, jump, swim, run, rest. A symbol string forms the starting point for the PT descriptors, where the symbols represent attributes or descriptors of regions, objects or events of the content, and the strings represent the order of the regions, objects or events in space or time. In practice, the symbol strings can represent many types of spatial or temporal information. For example, the symbol strings can represent the vertical order of color regions in a spatial scan of color photographs. Symbol strings can also be used to represent the series of actions in a movie, or scene locations in a television program. As another example, a symbol string can represent the motion direction of an object over time or a series of annotations of person, time or place.

[0022] Once symbol strings have been constructed for representing the spatial or temporal ordering of the content represented by the symbols, the ordering information can be utilized for providing statistical information useful in classifying and storing representations and for querying the stored representations. Using the symbol strings, a precedence template (hereinafter “PT”) can be developed. A precedence template (PT), T, defines a relative ordering of M symbols, T=t₀t₂, . . . ,t_M−1, where T[i] precedes T[i+j] in a symbol string S for j>0.

[0023] For example, given the dictionary D_activity={run, swim, jump, rest}, and the symbol string S=s₀s₂s₁s₃, then T=s₂s₁gives that run preceded swim in S. While the preferred embodiment provides for ordering based on precedence, it will be understood that another established ordering relationship could be used as the template. The instances of the PTs in a symbol string can be counted using a PT test. The PT test for T=t₀t₁in symbol string S is given by the indicator function I(S,T),

[0024] where $I\left(T,S\right)=\sum _{n=0}^{N-1}\sum _{m=n+1}^{N-1}\{\begin{array}{cc}1& S\left[n\right]=T\left[0\right]\mathrm{and}S\left[m\right]=T\left[1\right]\\ 0& \mathrm{ow}\end{array}$

[0025] where $I\left(T,S\right)=\sum _{n=0}^{N-1}\sum _{m=n+1}^{N-1}\{\begin{array}{cc}1& S\left[n\right]=T\left[0\right]\mathrm{and}S\left[m\right]=t\left[1\right]\\ 0& \mathrm{ow}\end{array}$

[0026] For example, the PT test gives that I(T,S)=2for T=s₀s₃in symbol string S=s₀s₂s₁s₃. For D_activity={run, swim, jump, rest}, this indicates that the activity run was carried out before the activity rest. The PT test forms the basis for generating a PT descriptor matrix which summarizes the counts of the PTs in the symbol string.

[0027] A precedence template (PT) descriptor matrix, M[i,j], of a symbol string S, gives the count of each PT T=s_is_jin S. Each symbol is mapped to a vertical column location and a horizontal row location, as depicted in FIG. 2 (further detailed below). Each entry in the PT descriptor matrix provides a count of the number of times that a given symbol (the symbol for the matrix row) preceded another particular symbol (the symbol for the matrix column) in the symbol string. The PT descriptor matrices form the basis of the information needed for comparing the symbol strings for searching and classifying spatial and temporal information.

[0028] With specific reference to the drawings, for developing the PT descriptor relating to a temporal sequence of events or spatial series of regions, first each event or region is assigned a symbol value, as illustrated in FIG. 1A. Each symbol value (125) can represent an attribute or descriptor of the event, such as name, place, action (130), and so forth, or a feature of a region, such as color, texture, shape or motion. In practice, for video, the temporal sequence can represent a list of scenes derived from shot detection and key-frame selection algorithms. The spatial and temporal order of the events, actions, regions, and so forth, can be represented as symbol strings (110, 115). In order to compare the video or images by spatial or temporal content, the symbol strings (110 and 115) need to be compared (120), as illustrated in FIG. 1B. Several problems emerge, including the following: how to deal with insertions, deletions, substitutions, replications and relocations of symbols; how to deal with sequences of different lengths; and, how to do partial matching.

[0029] Many of the problem cases are illustrated in FIG. 1B. For example, the action sequence represented in symbol string “C-A-B-D” (115) differs from that represented in the symbol string “A-C-B-A-D” (110) in that the order of the two initial activities has been reversed (“A”=run, “B”=swim) (125) in the second string. Also, in the second action sequence, one of the instances (130) of an action (“A”=run) is missing.

[0030] The Precedence Template (PT) descriptors of the present invention provide a way to compare the symbol sequences in a statistical fashion in order to provide a measure for similarity. The PT descriptors are generated by mapping the symbol strings into a PT descriptor matrix, where entry (i,j) in the PT descriptor matrix indicates the count n(i,j) of the instances in which symbol i preceded symbol j in the symbol string.

[0031] FIG. 2 shows how the symbols strings (205 and 210) can be compared using PT descriptors. For example, in the string “A-C-B-A-D” (205), A preceded D twice, and B preceded A once, and so forth. This is represented in the PT descriptor matrix (215) as an entry of 2 (240) in row “A”—column “D”, and as an entry of “1” (245) in row “B”—column “A”. These counts in the PT descriptor matrices form the basis for comparing (at 225) the symbol strings (205 and 210) in the presence of insertions, deletions, substitutions, replications, and relocations of symbols by comparing (230) the PT descriptor matrices (215 and 220). By generating and comparing the PT descriptor matrices for stored content, the content can be classified and more readily searched based on the PT descriptors. The process by which a classified database is constructed parallels the query and comparison process for searching, as further detailed below.

[0032] For classification and search applications, the query system typically needs to return the top-ranked items that are most similar to the query item. Where each target item has a symbol string, or PT descriptor matrix, the query is generated by constructing a symbol string or descriptor matrix as the search input. This can be done automatically by supplying a query image, by choosing one of the target images as an example image, or by sketching the query image. Once the system has the query input, it will assign one or more symbol strings to the input and then construct a PT descriptor matrix from those symbol strings using the PT Test described above. It is also possible that the query input comprises an input symbol string or a symbol string selected from a query menu. If symbol strings are given, then the PT descriptor matrices are automatically generated using the PT Test.

[0033] In order to compare the items based on spatial and temporal information, the query computes the similarity of query PT descriptor matrix M_qto those of the target items M_tas follows: Precedence Template (PT) Descriptor similarity. The similarity of PT descriptor matrices M_qand M_tis given by ${\Theta }_{q,t}=\sum _i\left(\frac{1}{C_q\left[i\right]}\frac{1}{C_t\left[i\right]}\right)\sum _j{M}_q\left[i,j\right]M_t\left[i,j\right],$

[0034] where C_q[i] and C_q[i] give the count of the instances of each symbol S_iin the query and target symbols strings, which is computed from: $C_i=\left|\sum _{j}M\left[i,j\right]-\sum _{j}M\left[j,i\right]\right|.$

[0035] For classifying stored content, given a set of semantic classes, a PT descriptor library is generated by pooling together the PT descriptors in each semantic class. For each semantic class, the PT library gives the likelihood that each PT is found in that class. The pooling process is carried out as follows: the frequency of each PT, T_i, in a set of symbol strings {S_j} is then given by P(T_i), where $P\left(T_i\right)=\sum _{j}I\left(T_i,S_j\right).$

[0036] The frequency of each PT, T_i, in the set of symbol strings {S_j}_kfrom semantic class C_kis given by P(T_i|C_k), where $P\left(T_i\right|C_k)=\sum _{{\forall }_j{S}_j\in C_k}I\left(T_i,S_j\right).$

[0037] The pooled PTs form the PT library wherein the precedence template(PT) library is given by the set of tuples:

[0038] [T_i, P(T_i), P(T_i|C₀), P(T_i|C₁), . . . , P(T_i|C_k−1)],

[0039] where K is the number of semantic classes. The P(T_i|C_k)'s reflect the frequencies of the PT descriptors in the semantic classes. For each T_i, the PT library gives the frequencies in which T_iis found in each semantic class, P(T_i|C_k), and in the entire collection, P(T_i). The symbol strings and the PT library form the basis for content classification by assigning each item to the closest semantic class in the PT library.

[0040] Content is classified as follows: for each T′_ifrom the unknown image, P(C_k|T′_i) is computed from the entries in the PT library: $P\left(C_k\right|T_i^{\prime })=\frac{P\left(T_i^{\prime }\right|C_k)}{P\left(T_i^{\prime }\right)}.$

[0041] The items are classified by the following Precedence Template (PT) Descriptor classification process whereby the system assigns item i to class l when ${\forall }_{l\ne k},\underset{}{\sum _i}P\left(C_l❘T_i^{\prime }\right)\ge \sum _{i}P\left(C_k❘T_i^{\prime }\right).$

[0042] For video, the PT descriptor can be used to describe the temporal order of events, actions, regions or objects. For example, the PT descriptor can be used to compare (340) scene transition graphs (315 and 320), as illustrated in FIGS. 3A and 3B. The scene-transition graphs of FIG. 3B can be generated from the symbol strings (325 and 330) that represent the temporal order of scenes (310) in terms of the scene symbols (305) which are assigned according to the table of FIG. 3A. In the case of scene transitions, a PT descriptor matrix counts the number of times each scene has preceded each other scene.

[0043] For images, the PT descriptor can be used to describe the spatial order of regions or objects (440). The PT descriptor process can work in conjunction with image segmentation algorithms (420). For example, considering the case of color segmentation of images, the PT descriptors can be generated as illustrated in FIG. 4. In the case of color region segmentation, the system first segments the image (405) into regions (420) and assigns each region a symbol that indicates its color (435). Then, the system extracts a number of symbol strings by scanning the segmented images in vertical scans (440) and reading-off the symbols to generate (425) the symbol strings (410). The system compute the PTs for the symbol strings and pools them together (430) to create a PT descriptor matrix (445). The system uses the PT descriptors (415) in order to compare, classify and search for images.

[0044] In image and video retrieval, the query can be formulated either graphically or by example. In graphical querying, the user sketches the query by placing regions on a query grid. In query by example, the user selects an image that typifies those the user is looking for. In both cases, the query system computes the symbol strings and PT descriptors for the query image and uses them to retrieve (510) the target images from the collection. The PT method allows fast matching of images in graphical querying, as illustrated in FIG. 5. The user places the color regions on a grid to construct a coarse depiction of the scenes of interest (505). The set of query PT descriptors are obtained by scanning the query grid and generating and consolidating the symbol strings for the query. The matching is then performed directly between the query PT descriptors and those for the target images.

[0045] For example, in the first query in FIG. 5, the user places two regions, one for blue sky, and another for green field on the query grid (515). The retrieved images have the best match to the query in terms of the composition of the color regions (520). The best six matches are illustrated on the right in FIG. 5. In the next example query, the user places a pale blue region above a brown region. The scenes in the retrieved images match the query in terms of color and location of the regions. In the last example query, the user places a blue region above a tan region. The first five retrieved images in which the blue region matches to sky and the tan region matches to sand.

[0046] The Precedence Template (PT) descriptor provides a way for classifying and querying video based on the spatial and temporal orderings of regions, objects, actions or events. Applied to video, the PT descriptors provide a way to compare the temporal order of events, actions, or objects such as those represented in a scene transition graph, key-frame list or event string. Applied to images, the PT descriptors provide a way to compare the spatial arrangement of image regions or objects. By capturing the spatial and temporal relationships statistically, the PT descriptors provide a robust way to measure similarity in the presence of insertions, deletions, substitutions, replications and relocations of these events, actions, regions or object.

[0047] While the invention has been described with reference to the preferred embodiment, it will be apparent to one having skill in the art that modifications can be made without departing from the spirit and scope of the invention as set forth in the appended claims.