Image analysis – Image transformation or preprocessing – Image storage or retrieval
Reexamination Certificate
2000-12-06
2004-09-14
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Image transformation or preprocessing
Image storage or retrieval
C382S199000, C382S266000, C382S227000, C382S236000, C382S276000, C382S240000, C358S403000, C707S793000
Reexamination Certificate
active
06792163
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to a method and apparatus for searching, browsing and summarizing moving image data, and more particularly to 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 (for example, shots or segments), extract a key 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.
2. Description of the Prior Art
Conventional methods for searching and browsing moving image data have carried out the searching and browsing using key frames. However, such conventional searching and browsing methods have had a limitation in effectively and efficiently searching and browsing moving image data, because they did not consider the fidelity of key frames. One such method may be, for example, a still image searching and browsing method proposed by Purdue University, which is capable of raising a searching speed by a considerable degree using a branch and bound searching technique based on triangle inequality obtained by applying tree-structured vector quantization (TSVQ) to still image data. The browsing method proposed by Purdue University is an active browsing method based on a hierarchical similarity pyramid, each level of which includes a cluster of similar images created in a 2-D grid. The similarity pyramid has a smaller cluster at its lower level and a structure representative of each image at its lowest level. This proposed browsing method has pruning and reorganization functions as its fundamental functions, thereby effectively performing the browsing operation on the basis of user relevance feedback information. However, the above-mentioned browsing method is only a one-sided mode of a server and provides no benchmark for a user to determine how effective the browsing is.
In conclusion, the still image searching and browsing method proposed by Purdue University merely leads a user to a one-sided still image searched result of a server without setting a threshold value for a user's satisfactory level. Further, the proposed browsing method extracts key frames from moving image data and performs the browsing operation using the extracted key frames, but does not present how effectively the browsing operation represents the moving image data. Moreover, this searching and browsing method is not very efficient because it utilizes not one tree structure, but individual tree structures formed by different mechanisms.
On the other hand, considering studies on rate-constraints moving image summary, there has been proposed a key frame extraction technology based on a restriction in time. However, this technology provides not a moving image summary method for satisfying a user's desired time, but an algorithm for extracting respective key frames from clusters of similar frames at intervals of a predetermined threshold range, or a predetermined period of time or more. In other words, the proposed key frame extraction technology does not provide a moving image summary method capable of summarizing, for example, a two hours-required moving image to a ten minutes-required amount. In conclusion, there is a keen need for the development of a moving image search, browsing and summary method capable of effectively summarizing moving image data to the amount required for a time period desired by a user.
SUMMARY OF THE INVENTION
Therefore, the present invention has been made in view of the above problems, and it is an objective of the present invention to provide a method and apparatus for effectively and efficiently searching, browsing and summarizing moving image data using the fidelity of a key frame hierarchy.
It is another objective of the present invention to provide a method and apparatus for searching, browsing and summarizing moving image data using the fidelity of a key frame hierarchy, which can apply a threshold value to a fidelity value of each key frame, effectively perform the browsing operation within the range of the applied threshold value, extract key frames of the number desired by a user from the moving image data and summarize the moving image data on the basis of fidelity values of the extracted key frames.
In accordance with one aspect of the present invention, the above and other objectives can be accomplished by a provision of 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 the tree-structured moving image hierarchy at an edge between adjacent ones of the key frames.
In accordance with another aspect of the present invention, there is provided 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 the moving image data into the moving image units; a key frame extractor for extracting a key frame from each of the moving image units partitioned by the unit boundary detector; a search engine application unit for searching for a specific moving image on the basis of the key frame extracted by the key frame extractor; a browsing device application unit for browsing information of the specific moving image on the basis of the key frame extracted by the key frame extractor; and a moving image summary device application unit for expressing the information of the specific moving image significantly on the basis of the key frame extracted by the key frame extractor.
In accordance with yet another aspect of the present invention, there is provided a method for searching for moving image data of a tree-structured moving image hierarchy, comprising six steps. The first step is allowing a user to enter a desired query frame. The second step is 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. The third step is searching for a lower-level path if the query frame and the highest-level key frame are similar to each other. The fourth step is determining whether the highest-level key frame has a high fidelity value if the query frame and the highest-level key frame are not similar to each other, pruning a search path to the highest-level key frame and searching for a new path if the highest-level key frame has the high fidelity value and searching for the lower-level path if the highest-level key frame has a low fidelity value, the fifth step is determining whether a key frame currently compared with the query frame belongs to a lowest level after searching for the lower-level path, determining whether the currently compared key frame is similar to the query frame if it belongs to the lowest level, storing the currently compared key frame if it is similar to the query frame and searching for a new path if the currently compared key frame is not similar to the query frame. The sixth step is 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 the above fifth step unless the search operation has been completed up to the lowest level.
REFERENCES:
patent: 4989258 (1991-01-01), Takahashi et al.
patent: 5559562 (1996-09-01), Ferster
patent: 5995095 (1999-11-01), Ratakonda
patent: 6026179 (2000-02-01), Brett
patent: 6028645 (2000-02-01), Reid et al.
patent: 6097853 (2000-08-01
Chang Hyun Sung
Kim Jung Rim
Kim Yu Nam
Seol Sang Hoon
Choobin Barry
Hyundai Curitel Co., Ltd.
Mehta Bhavesh M.
Merchant & Gould, P.C. (23552)
LandOfFree
Method and apparatus for searching, browsing and summarizing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for searching, browsing and summarizing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for searching, browsing and summarizing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3217315