Method and apparatus for searching, browsing and summarizing moving image data using fidelity of tree-structured moving image hierarchy

• US 20010033693A1
• Filed: 12/06/2000
• Published: 10/25/2001
• Est. Priority Date: 12/06/1999
• Status: Active Grant

• Current Assignee: Pantech Corporation (Ideahub, Inc.)
• Original Assignee: Pantech & Curitel Communications Incorporated (Pantech Incorporated)
• Inventors: Seol, Sang Hoon, Chang, Hyun Sung, Kim, Yu Nam, Kim, Jung Rim
• Granted Patent: US 6,792,163 B2
• Time in Patent Office: Days
• US Class Current: 382/219
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/7328 Query by example, e.g. a complete video frame or video sequence graphical querying G06F16/7335
• CPC Class Codes: G06F 16/739 in form of a video summary, e.g. the video summary being a video sequence, a composite still image or having synthesized frames
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A method and apparatus for searching, browsing and summarizing moving image data using the fidelity of a tree-structured moving image hierarchy, which can partition or divide the moving image data into predetermined units, extract a key frame or representative frame from each of the partitioned or divided units, create a tree-structured key frame hierarchy on the basis of the extracted key frames, store a fidelity value of each of the key frames, which is a sub-tree information representative degree of each key frame, at an edge between adjacent ones of the key frames and effectively and efficiently search, browse and summarize the moving image data using the stored fidelity values. Therefore, a query image or video clip desired by a user can more rapidly and accurately be searched for.

Claims

1. A method for expressing moving image data of a tree-structured moving image hierarchy, comprising the step of storing a fidelity value of each key frame of said tree-structured moving image hierarchy at an edge between adjacent ones of the key frames.

2. The method as set forth in

claim 1

, wherein said fidelity value is quantitative information or qualitative information.

3. The method as set forth in

claim 1

, wherein said fidelity value is a real number between 0 and 1 for normalization.

4. The method as set forth in

claim 1

, wherein said fidelity value is a maximum distance between a key frame and its progeny frames.

6. The apparatus as set forth in

claim 1

, wherein said key frame extractor includes:

a key frame extraction function unit for extracting a predetermined number of key frames from each of said moving image units partitioned by said unit boundary detector on the basis of a predetermined key frame extraction function;

a key frame storage unit for storing numbers of the key frames extracted by said key frame extraction function unit, corresponding respectively to said moving image units; and

a key frame fidelity calculator for calculating a fidelity value of each of the key frames stored in said key frame storage unit.

7. The apparatus as set forth in

claim 6

, wherein said key frame extraction function unit is adapted to use a key frame extraction function for extracting a minimum number of key frames within a predetermined error range using a visual content complexity indicator.

8. The apparatus as set forth in

claim 6

, wherein said fidelity value is quantitative sub-tree information.

9. The apparatus as set forth in

claim 6

, wherein said key frame storage unit is adapted to store the fidelity value calculated by said key frame fidelity calculator at an edge between adjacent ones of the key frames stored therein.

10. The apparatus as set forth in

claim 6

, wherein said moving image summary device application unit is adapted to process key frames of the number based on a user'"'"'s input or appropriate to a user'"'"'s environment.

5. An apparatus for searching, browsing and summarizing moving image data of a tree-structured moving image hierarchy, comprising:

a unit boundary detector for detecting the boundary of each moving image unit from the moving image data to partition said moving image data into the moving image units;

a key frame extractor for extracting a key frame from each of said moving image units partitioned by said unit boundary detector;

a search engine application unit for searching for a specific moving image on the basis of said key frame extracted by said key frame extractor;

a browsing device application unit for browsing information of said specific moving image on the basis of said key frame extracted by said key frame extractor; and

a moving image summary device application unit for expressing the information of said specific moving image significantly on the basis of said key frame extracted by said key frame extractor.

11. A method for searching for moving image data of a tree-structured moving image hierarchy, comprising the steps of:

a) allowing a user to enter a desired query frame;

b) comparing the query frame entered by the user with a highest-level key frame of an indexed moving image tree structure in a database to determine whether the two frames are similar to each other;

c) searching for a lower-level path if said query frame and said highest-level key frame are similar to each other;

d) determining whether said highest-level key frame has a high fidelity value if said query frame and said highest-level key frame are not similar to each other, pruning a search path to said highest-level key frame and searching for a new path if said highest-level key frame has the high fidelity value and searching for said lower-level path if said highest-level key frame has a low fidelity value;

e) determining whether a key frame currently compared with said query frame belongs to a lowest level after searching for said lower-level path, determining whether the currently compared key frame is similar to said query frame if it belongs to the lowest level, storing the currently compared key frame if it is similar to said query frame and searching for a new path if the currently compared key frame is not similar to said query frame; and

f) determining whether the search operation has been completed up to the lowest level after storing the currently compared key frame, displaying the stored frame if the search operation has been completed and returning to said step e) unless the search operation has been completed up to the lowest level.

15. The method as set forth in any one of

claim 11

to

claim 14

, further comprising the step of storing a fidelity value of each key frame of said tree-structured moving image hierarchy at an edge between adjacent ones of the key frames.

12. A method for searching for moving image data of a tree-structured moving image hierarchy, comprising the steps of:

a) allowing a user to enter a desired query frame and a threshold value for his satisfactory level;

b) comparing the query frame entered by the user with a highest-level key frame of an indexed moving image tree structure in a database to determine whether a dissimilarity value based on a metric property is higher than the sum of the threshold value entered by the user and a fidelity value of the highest-level key frame;

c) searching for a lower-level path if said dissimilarity value is higher than the sum of said threshold value and said fidelity value of said highest-level key frame;

d) pruning a search path to said highest-level key frame and searching for a new path if said dissimilarity value is not higher than the sum of said threshold value and said fidelity value of said highest-level key frame;

e) determining whether a key frame currently compared with said query frame belongs to a lowest level after searching for said lower-level path, determining whether the currently compared key frame is similar to said query frame if it belongs to the lowest level, storing the currently compared key frame if it is similar to said query frame and searching for a new path if the currently compared key frame is not similar to said query frame; and

f) determining whether the search operation has been completed up to the lowest level after storing the currently compared key frame, displaying the stored frame if the search operation has been completed and returning to said step b) unless the search operation has been completed up to the lowest level.

13. A method for browsing moving image data of a tree-structured moving image hierarchy, comprising the steps of:

a) allowing a user to request a server to browse and enter a desired threshold value;

b) comparing a fidelity value of a highest-level key frame in a database with the threshold value entered by the user;

c) storing said highest-level key frame in a buffer if the fidelity value of said highest-level key frame is higher than or equal to said threshold value;

d) comparing a fidelity value of a lower-level key frame with said threshold value if said fidelity value of said highest-level key frame is smaller than said threshold value, storing the lower-level key frame in said buffer if the fidelity value of the lower-level key frame is higher than or equal to said threshold value and comparing a fidelity value of a subsequent lower-level key frame with said threshold value if said fidelity value of said lower-level key frame is smaller than said threshold value; and

e) determining whether all paths have been searched up to a lowest level and displaying images stored in said buffer if all paths have been searched up to the lowest level.

14. A method for summarizing moving image data of a tree-structured moving image hierarchy, comprising the steps of:

a) allowing a user to enter a desired number of frames or a desired summary period of time;

b) storing a root key frame in a buffer;

c) storing a root of a sub-tree with a lowest one among fidelity values irrelevant to selection of the stored root key frame in said buffer; and

d) determining whether the number of frames stored in said buffer is smaller than the number of frames desired by the user, displaying the frames stored in said buffer if the number thereof is not smaller than said desired number of frames and repeating the above procedure until the number of frames stored in said buffer arrives at said desired number of frames if it is smaller than said desired number of frames.