Video database indexing and query method and system

• US 5,819,286 A
• Filed: 12/11/1995
• Issued: 10/06/1998
• Est. Priority Date: 12/11/1995
• Status: Expired due to Term

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Yang, Hsiao-Ying, Liu, Chih-Chin, Ni, Cheng-Yao, Chen, Arbee L. P., Yu, Chih-Hsing
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HO, RUAY L
• Application Number:
  US08/570,212
• Time in Patent Office: 1,030 Days
• Field of Search: 395/601, 395/611, 395/612, 395/613, 395/614, 395/615, 395/616, 395/140, 395/200.02, 395/326, 395/333, 395/806, 348/1, 348/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/7335 Graphical querying, e.g. query-by-region, query-by-sketch, query-by-trajectory, GUIs for designating a person/face/object as a query predicate end-user interface involving hot spots associated with the video H04N21/4725; end-user interface for selecting a Region of Interest H04N21/4728
• CPC Class Codes: G06F 16/7343 Query language or query format
• CPC Class Codes: G06V 10/422 for representing the structure of the pattern or shape of an object therefor
• CPC Class Codes: G06V 20/46 Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A video indexing and query execution system includes a processor which indexes video clips by: (a) identifying each symbol of one or more graphical icons in each frame of each video clip, (b) determining the horizontal, vertical and temporal coordinates of each symbol of the identified graphical icons, and (c) constructing a database for each identified symbol of the graphical icons. The processor converts a video query from graphical form to string form by: (a) receiving a video query specifying the vertical, horizontal and temporal coordinates of a graphical icon to be matched in at least one frame to be retrieved, and (b) constructing a normal 3-D string from the video query indicating the distance between each symbol of each icon in the video query in each direction. The processor also executes a video query on a video database by: (a) identifying only those video clips of the database whose signatures contain the signature of the executed video query, (b) for each of the identified video clips: (b1) constructing a 1-D list for each of the horizontal, vertical and temporal directions, comprising a plurality of sets of symbols of icons contained in video query, each set containing a permutation of symbols of the icons which satisfy the video query in the respective direction of the 1-D list, and (b2) forming the intersection of the three 1-D lists, and (c) identifying the portions of the video clips, indicated by a corresponding set contained in an intersection set of at least one of the identified video clips, as satisfying the video query.

Claims

1. A method for executing queries to locate one or more frames of one or more video clips in a video database comprising the steps of:

(a) identifying each symbol of one or more graphical icons in each frame of each video clip,

(b) determining the horizontal, vertical and temporal coordinates of each symbol of said one or more identified graphical icons,

(c) constructing an index base for each identified symbol of said one or more graphical icons which includes said coordinates,

(d) receiving a video query indicating at least one frame of a video clip to be retrieved, said video query specifying the vertical, horizontal and temporal coordinates of at least one graphical icon to be matched to said at least one frame to be retrieved,

(e) constructing a 3-D string from said video query, which 3-D string indicates the distance between each symbol of each icon in said video query in said vertical, horizontal and temporal directions,

(f) identifying only those video clips of said database whose signatures contain the signature of said executed video query,

(g) for each of said identified video clips;

(g1) constructing a 1-D list for said horizontal direction, a 1-D list for said vertical direction and a 1-D list for said temporal direction, wherein each of said 1-D lists comprises a plurality of sets of symbols of icons, which icons are contained in said signature of said executed video query, and wherein each of said sets contains a permutation of symbols of said icons which satisfy said video query in said respective direction of said 1-D list,

(g2) forming the intersection of said 1-D list for said horizontal direction, said 1-D list for said vertical direction and said 1-D list for said temporal direction, and

(h) identifying the portions of at least one of said identified video clips, indicated by a corresponding set contained in an intersection set of at least one of said identified video clips, as satisfying said video query.

2. The method of claim 1 wherein step (a) further comprises, for each clip, only identifying each symbol of said one graphical icon in an earliest presented frame in which said symbol occurs.

3. The method of claim 1 further comprising the step of:

constructing a video signature of said video clip which contains the set of each graphical icon that occurs at least once in said video clip.

4. The method of claim 1 further comprising the step of:

depending on matching criterion of said video query, converting a normal 3-D string of said video query to an extended 3-D string which indicates;

(1) an undefined distance,

(2) an order of precedence, of unspecified distance,

(3) an equal distance, or

(4) a specific distance

between each pair of said icons of said video query in said horizontal, vertical and temporal directions of frames of said video clips.

5. The method of claim 4 further comprising the step of:

constructing a video signature of said video query which contains the set of each graphical icon that occurs at least once in said video query.

6. The method of claim 5 wherein step (g1) further comprises, for each of said horizontal, vertical and temporal directions, the steps of:

(i) forming a plurality of sets of symbols, including one set for each icon of said video query signature, each set containing each symbol, contained in said video clip, of said icon to which said set corresponds,

(ii) determining the rank of each symbol of each of said sets formed in step (i), wherein rank is an order of precedence, in said respective direction of said 1-D list, of said icons,

(iii) ordering the symbols of each set formed in step (i) in order of increasing rank, so as to form one sequence of symbols for each icon,

(iv) selectively segregating the symbols of each icon into equivalently ranked classes and linking each pair of icons in each class, each link being directed from a first symbol of a class to the very next symbol of equal or higher rank, of said same class, and

(v) using operators of a 1-D extended string of said extended 3-D string of said video query, which 1-D extended string corresponds to the same direction as said 1-D list, selectively linking said symbols, wherein each link of step (v) is directed from a symbol of one icon to a symbol of another icon which immediately succeeds said one icon in said extended 1-D string of said video query.

7. The method of claim 6 further comprising the step of:

discarding each symbol of said classes of said video sequence not continuously linked between a symbol of the first icon, and a symbol of the last icon, of said extended 1-D string of said video query.

8. The method of claim 6 further comprising the steps of:

using said linked classes of symbols of said icons of said video clip, forming each possible permutation of symbols, which permutations each include one symbol of each icon contained in said video query signature, by;

selecting a first symbol in a class associated with the first icon of said extended 1-D string of said video query,

selecting each subsequent symbol by traversing said links, in said direction of said links, from the last selected symbol to a symbol in another class associated with the icon which follows the icon, with which said last selected symbol is associated, in said extended 1-D string of said video query.

9. The method of claim 6 wherein said step (iv) further comprises the steps of:

determining that all symbols of a sequence have an equivalent rank if said 1-D extended string of said video query indicates that the icon of said symbol sequence;

(1) precedes the next icon, by an unspecified distance, and is preceded by the previous icon, by an unspecified distance,

(2) is an undefined distance from both the previous and next icon,

(3) precedes the next icon, by an unspecified distance, and is an undefined distance from the previous icon, or

(4) is an undefined distance from the next icon and is preceded by the previous icon, by an unspecified distance, and otherwise determining that only those symbols of a given icon having equal ranks are equivalent.

10. The method of claim 6, wherein icons G_a and G_b are contained in said video clip, wherein G_a immediately precedes, and is adjacent to, G_b in said extended 1-D string of said video query, where:

G_a,p designates a p^th subsequence of G_a, 1≦

p≦

last subsequence ordinate of G_a,

G_b,k designates a k^th subsequence of G_b, 1≦

k≦

last subsequence ordinate of G_b,

G_a,1 is the first, lowest ranked class of G_a

s_i is any symbol in G_a,1,

s_i+1 is the symbol of equal or higher rank which immediately follows s_i,

s_imax is the last symbol in the p^th subsequence G_a,p,

G_b,1 is the first, lowest ranked class of G_b,

s_j is any symbol in G_b,1, the first, lowest ranked class of G_b,

s_j-1 is the symbol of equal or lower rank which immediately precedes s_j,

s_jmin is the first symbol in the k^th subsequence G_b,k,

r(s) is the rank of s,

, |_n, ≡ and

? are operators in said 3-D extended string of said video query

indicates precedes, by an unspecified distance,

|_n indicates precedes by a distance of n,

≡

indicates equal distance,

? indicates undefined,

a₁ is the indicator which precedes G_a in said extended 3-D string,

a₂ is the indicator between G_a and G_b in said 3-D extended string, and

a₃ is the indicator which follows G_b in said 3-D extended string, said step (v) further comprising the steps of;

(i) linking s_i with s_j, if;

(1) a₁ is or ?,

(2) a₂ is ,

(3) a₃ is or ?,

(4) r(s_i)<

r(s_j),

(5) r(s_i+1)≧

r(s_j), and

(6) r(s_i)≧

r(s_j-1).

(ii) linking s_i with s_jmin if;

(1) a₁ is or ?,

(2) a₂ is ,

(3) a₃ is ≡

or |_n,

(4) r(s_i)<

r(s_jmin), and

(5) r(s_i+1)≧

r(s_jmin).

(iii) linking s_imax with s_i if;

(1) a₁ is ≡

or |_n,

(2) a₂ is ,

(3) a₃ is or ?,

(4) r(s_imax)<

r(s_j), and

(5) r(s_imax)≧

r(s_j-1)

(iv) linking s_imax with s_jmin if;

(1) a₁ is ≡

or |_n,

(2) a₂ is ,

(3) a₃ is ≡

or |_n,

(4) r(s_imax)<

r(s_jmin).

(v) linking s_imax with s_jmin if;

(1) a₂ is ≡

, and

(2) r(s_imax)=r(s_jmin)

(vi) linking s_imax with s_jmin if;

(1) a₂ is |_n, and

(2) r(s_jmin)-r(s_imax)=n, and

(vii) linking s_imax with s_jmin if;

(1) a₂ is ?.

11. A method for indexing a video clip comprising:

(a)

(a) identifying each symbol of one or more graphical icons in each frame of said video clip,

(b) determining the horizontal, vertical and temporal coordinates of each symbol of said one or more identified graphical icons, and

(c) constructing an index base for each identified symbol of said one or more graphical icons which includes said coordinates, horizontal, vertical and temporal, said index base being searchable using a 3-D string constructed from a video query, which 3-D search string indicates the distance between each symbol in each icon in said video query in said vertical, horizontal and temporal directions.

12. A method for executing a video query on a database containing at least one video clip comprising the steps of:

(a) identifying only those video clips of said database whose signatures contain the signature of said executed video query,

(b) for each of said identified sequences of video frames;

(b1) constructing a 1-D list for said horizontal direction, a 1-D list for said vertical direction and a 1-D list for said temporal direction, wherein each of said 1-D lists comprises a plurality of sets of symbols of icons, which icons are contained in said signature of said executed video query, and wherein each of said sets contains a permutation of symbols of said icons which satisfy said video query in said respective direction of said 1-D list,

(c) forming the intersection of said 1-D list for said horizontal direction, said 1-D list for said vertical direction and said 1-D list for said temporal direction, and

(d) identifying the portions of at least one of said identified video clips, indicated by a corresponding intersection set contained in at least one of said identified video clips, as satisfying said video query.

13. A system for indexing a video clip comprising:

a processor for identifying each symbol of one or more graphical icons in each frame of said video clip, determining the horizontal, vertical and temporal coordinates of each symbol of said one or more identified graphical icons, and constructing an index base for each identified symbol of said one or more graphical icons which includes said horizontal, vertical and temporal coordinates, said index base being searchable using a 3-D string constructed from a video query, which 3-D search string indicates the distance between each symbol in each icon in said video query in said vertical, horizontal and temporal directions.

14. A system for executing a video query on a database containing at least one video clip comprising:

a processor for identifying only those video clips of said database whose signatures contain the signature of said executed video query, for each of said identified sequences of video frames, constructing a 1-D list for said horizontal direction, a 1-D list for said vertical direction and a 1-D list for said temporal direction, wherein each of said 1-D list comprises a plurality of sets of symbols of icons, which icons are contained in said signature of said executed video query, and wherein each of said sets contains a permutation of symbols of said icons which satisfy said video query in said respective direction of said 1-D list, and forming the intersection of said 1-D list for said horizontal direction, said 1-D list for said vertical direction and said 1-D list for said temporal direction, and identifying the portions of at least one of said identified video clips, indicated by a corresponding intersection set at least one of said identified video clips, as satisfying said video query.