Video database indexing and query method and system
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
14 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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.
- (a)
-
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.
Specification