System of updating an index file of frame sequences so that it indexes non-overlapping motion image frame sequences

• US 5,428,774 A
• Filed: 03/16/1993
• Issued: 06/27/1995
• Est. Priority Date: 03/24/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hashihara, Hideharu, Takahashi, Junichi
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/033,686
• Time in Patent Office: 833 Days
• Field of Search: 395/600, 395/100, 395/154, 360/14.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/78 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: Y10S 345/96 Iterative display of preconfigured images
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

In the creation of the index file, one index record is allocated to each set consisting of one retrieval key and the initial and final positions in the motion image of one frame to which the retrieval key is allocated, and information on this set is stored therein. In the query processing, for a query specified by a Boolean expression of retrieval keys, records whose keywords match any of the retrieval keys included in the query are retrieved from the index file. Thereafter, all the initial and final positions of the matching records are arranged along a time axis. For each of intervals defined by those positions, a truth table is created in which the allocation of the retrieval keys included in the query is expressed by truth values, and the logical condition of the query is evaluated based on the table.

Claims

1. A computer-implemented method for allocating retrieval keys to frame intervals that form portions of an entire sequence of frames that constitute a stored motion image and updating an index file of motion image frame intervals on a storage medium, said index file comprising records that contain information on initial and final positions of said intervals in said motion image as well as information on said retrieval keys, said method comprising the steps of:

a. receiving as input a designation of one of said retrieval keys as a currently designated retrieval key;

b. receiving as input a designation of initial and final positions of one of said intervals;

c. extracting, from said index file, records that contain information on said currently designated retrieval key, in response to the designation of said initial and final positions;

d. checking for the existence of any overlaps between said initial and final positions of said designated interval and the intervals defined by said extracted records;

e. if any overlaps are detected in step (d), updating said index file so that it does not include any records associated with intervals that cause an overlap, but includes a record that contains information indicating initial and final positions of an interval that includes all the intervals that cause the overlaps, as well as information on the currently designated retrieval key;

f. if no overlaps are detected in step (d), inserting into said index file a record that contains information on said designated initial and final positions as well as on said currently designated retrieval key; and

g. iterating steps (b) through (f) until the designation of a new retrieval key is received as input.

2. A computer system for allocating retrieval keys to frame intervals that form portions of an entire sequence of frames that constitute a stored motion image and for updating an index file of motion image frame intervals on a storage device, said index file comprising records having information on initial and final positions of said intervals in said motion image as well as related information on said retrieval keys, said system comprising:

a. buffer means for receiving as input a designation of one retrieval key as a currently designated retrieval key;

b. means for receiving as input a record having a designation of initial and final positions of one of said frame intervals;

c. means for adding records received by said receiving means having information on frame intervals with designated initial and final positions related to said currently designated retrieval key to said buffer means that can be accessed faster than said storage device;

d. means for iterating the operation of said adding means until the addition of frame ,intervals for said currently designated retrieval key is complete; and

e. means for updating the contents of said buffer means to eliminate any overlaps of intervals defined by records related to the same retrieval key in said buffer means, said updating means for each record in said buffer means comprising;

f. means for extracting, from said index file, records that contain frame interval information on the same retrieval key as said each buffer record;

means for checking for the existence of any overlaps

g. means for checking for the existence of any overlaps between the initial and final positions of an interval defined by said each buffer record and intervals defined by said extracted index file records for the same retrieval key;

h. means, responsive to the detection of any overlaps, for updating said index file so that it does not include any records related to the same retrieval key with intervals that cause an overlap, but includes a record that contains information indicating the initial and final positions of an interval that includes all the intervals that cause tile overlaps, as well as information on said same related retrieval key; and

i. means, responsive to the detection of no overlaps for inserting said each buffer record into said index file.

3. A computer-implemented method for allocating retrieval keys to frame intervals that form portions of an entire sequence of frames that constitute a stored motion image and updating an index file of motion image frame intervals on an external storage device, said index file comprising records that contain information on initial and final positions of said intervals in said motion image as well as information on said retrieval keys, said method comprising the steps of:

a. creating a temporary file in which records are sorted according to their retrieval keys, each record of which stores one keyword and information on initial and final positions of one interval to which said keyword is allocated;

b. extracting, from said temporary file, records that contain identical keywords and placing them in a buffer that can be accessed faster than said external storage device;

c. updating the contents of said buffer to eliminate any overlaps of initial and final positions of intervals defined by records in said buffer, said updating comprising for each record in said buffer,

d. extracting, from said index file, records that contain information on an identical retrieval key as that of said buffer record;

e. checking for the existence of any overlaps between intervals defined by said buffer record and intervals defined by said extracted records;

f. if any overlaps are detected in step (e), updating said index file so that it does not include any records associated with intervals that cause an overlap, but includes a record that contains information indicating initial and final positions of an interval that includes all intervals that cause overlaps, as well as information on said identical retrieval key; and

g. if no overlaps are detected in step (e), inserting said buffer record into said index file.

4. A computer-implemented method for allocating retrieval keys of frame intervals that form portions of an entire sequence of frames that constitute a stored motion image and updating an index file of motion image frame intervals on a storage medium, said index file comprising records that contain information on initial and final positions of said intervals in said motion image as well as information on said retrieval keys, said method comprising the steps of:

a. receiving an instruction for release of a retrieval key allocation, wherein the instruction includes a retrieval key and initial and final positions of an interval as parameters;

b. extracting from said index file, records that contain information on said retrieval key of said instruction;

c. checking for the existence of any overlaps between intervals defined by said extracted records and said interval of said instruction;

d. if any intervals defined by said extracted records are completely included in said interval of said instruction, deleting records defining such intervals from said index file; and

e. if there are any overlaps between intervals defined by said extracted records and said interval of said instruction, updating said index file so that initial and final positions defining such intervals are changed so as to eliminate the overlaps.

5. A computer-implemented method for retrieving frame sequences, that constitute portions of a stored motion image, by the use of an index file maintained on a storage medium, wherein each record in said index file contains one keyword and information on initial and final positions in said motion image of one frame sequence interval for which said keyword is allocated, said method comprising the steps of:

a. receiving a query specified by a Boolean expression of retrieval keys related to said keywords;

b. extracting, from said index file, records that contain information with a keyword related to any retrieval key included in said query; and

c. dividing the whole interval of said motion image into a plurality of candidate intervals on the basis of initial and final positions stored in said extracted records and the initial and final positions of said whole interval of said motion image, and evaluating said Boolean expression according to whether a keyword related to a retrieval key has been allocated to each candidate interval to determine the candidate intervals to which all retrieval keys included in said query have been allocated.

6. A method as set forth in claim 5, wherein, in said index file, there are no overlaps between frame sequence intervals defined by initial and final positions of records that contain identical information on a keyword related to a retrieval key.

7. A method as set forth in claim 5, wherein, in step (c), the evaluation of said Boolean expression is sequentially performed for consecutive candidate intervals.

8. A computer system for retrieving records associated with frame sequences that constitute a motion image, said records being stored in an index file and each having a retrieval key and information on the initial and final positions of a respective frame sequence interval within the whole interval constituting said motion image, said system comprising:

a. means for inputting a record retrieving query specified by a Boolean expression of retrieval keys;

b. means for extracting, from said index file, records that contain information on any retrieval key included in said query; and

c. a means for dividing the whole interval constituting said motion image into a plurality of candidate intervals on the basis of initial and final positions stored in said extracted records and the initial and final positions of said whole interval constituting said motion image; and

d. query processing means for evaluating said Boolean expression according to whether a retrieval key has been allocated to each candidate interval and determining the candidate intervals to which all retrieval keys included in said query have been allocated, and including the records corresponding to said determined intervals in a retrieval result.

9. A system as recited in claim 8, further comprising:

means for storing and displaying a motion image; and

display control means for controlling said means for storing and displaying so as to display an image of at least one frame of a sequence included in an interval determined as a retrieval result by said query processing means.

10. A system as set forth in claim 8 further comprising:

a means for storing still images of representative frames in frame sequence intervals selected from the whole interval constituting said motion image;

a display control means; and

a display means; and

wherein said display control means extracts, from said means for storing still images of representative frames, still images of the representative frames included in an interval determined as a retrieval result by said query processing means and transfers them to said display means.

11. A computer-implemented method for creating an index file on a storage medium, said index file comprising index records for retrieving frame sequences that form portions of an entire sequence of frames that constitute a stored motion image, said method comprising the steps of:

creating frame sequence record sets, each record set comprising;

indices of the initial and final positions of the interval of a respective frame sequence in said sequence of motion image frames; and

a retrieval key allocated to the respective frame sequence;

allocating an index record to each record set and storing each set in said allocated index record;

storing said index records in said index file;

updating said index file by consolidating index records therein having

record sets with the same retrieval key and indices defining initial and final positions which overlap,

said consolidating comprising combining said record sets with overlapping indices into a single record set defining a frame sequence interval having initial and final positions indicative of the extremes of said indices.

12. A method as set forth in claim 11 further comprising the step of retrieving frame sequences from said index file using said retrieval keys to identify the index records sought.

13. A method as set forth in claim 12 wherein said retrieving step is achieved with Boolean logic.

14. A method as set forth in claim 12 wherein said retrieving step further comprises the steps of:

storing still images of representative frames in frame sequence intervals selected from the entire motion image sequence;

extracting from said stored still images, a still image of the representative frame in a retrieved frame sequence from said index records sought; and

displaying said extracted still image.

15. A computer system for creating an index file on a storage medium, said index file comprising index records for retrieving frame sequences that form portions of an entire sequence of frames that constitute a stored motion image, comprising:

means for creating frame sequence record sets, each record set comprising;

indices of the initial and final positions of the interval of a respective frame sequence in said sequence of motion image frames; and

a retrieval key allocated to the respective frame sequence;

means for allocating an index record to each record set and storing each set in said allocated index record;

means for storing said index records in said index file;

means for updating said index file by consolidating index records therein having record sets with the same retrieval key and indices defining initial and final positions which overlap, said updating means comprising;

means for combining said record sets with overlapping indices into a single record set defining a frame sequence interval having initial and final positions indicative of the extremes of said indices.

16. The system set forth in claim 15 further comprising means for retrieving frame sequences from said index file using said retrieval keys to identify the index records sought.

17. The system set forth in claim 16 wherein said retrieving means comprises means for executing Boolean logic.

18. The system set forth in claim 16 wherein said retrieving means comprises:

means for storing still images of representative frames in frame sequence intervals selected from the entire motion image sequence;

means for extracting from said stored still images, a still image of the representative frame in a retrieved frame sequence from said index records sought; and

means for displaying said extracted still image.