Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-01-02
2001-01-30
Ho, Ruay Lian (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C382S260000, C707S793000
Reexamination Certificate
active
06182069
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a computer-executed procedure for searching an image database that includes video by use of queries based on the image characteristics of segmented video frames.
In the prior art, the storage, indexing, and retrieval of video images in a computer database is known. See, for example, the article by M. Flickner, et al entitled
Query by Image and Video Content: The QBIC System
, in COMPUTER, September 1995, pp. 23-32. This article describes an image database that includes still images and video. For query processing of video in a database, images that represent contents of stored video are used. These images are typically in the form of frames, and may comprise individual frames extracted from a sequence of frames (key frames), as well as synthesized frames that are composites of such sequences. Such synthesized frames are very desirable in searching video since they include data respecting motion in the sequences of frames from which they are composed. This permits queries based upon motion, among other things.
Video frames (either key frames or synthesized frames) may be processed by being segmented into objects. In the prior art, an object is a dominant figure in an image. Objects may be identified (automatically or manually) as members of a restricted class of predetermined images, or by user-guided algorithms. In the described prior art image database, queries are allowed on objects, frames, or any combination thereof. In this regard, a query is presented in a form called a “query image” having a semantic significance (“Find images with a yellow star”). The query specifies values of image characteristics such as color, texture, and shape. Similarity is supported by specification of location, distance, and weight. A query response is returned that includes a user-defined number of images that most closely match the query, ranked in order of similarity, based upon the specified image characteristic values and the similarity factors.
Unfortunately, prior art video image databases provide a query capability that is limited to segmentation of images and frames into objects alone. Manifestly, a richer segmentation vocabulary would support greater precision in query specification.
SUMMARY OF THE INVENTION
The invention is based on the inventors critical realization that segmentation of images and frames into one or more objects and background would enrich the query semantics of a video image database system, by permitting specification not only of objects, but also of background.
For the purpose of this invention “background” may be one component of an image or a frame, an object being another component. Intuitively, background would be that portion of an image or frame that remains when one or more objects have been segmented from the image or frame. Further, background would be the visual information that occupies most of the image or frame and is “behind” objects that the image or frame contains. The background of an image or frame is frequently that content of an image or frame that extends to the edges of the image or frame, or to any objects in the image or frame that frame it, or any portion of it.
Although the prior art does have some sense of background as differentiated from objects, the background is monochromatic, non-textured, static, and useful only to define objects of interest. In this regard see, for example, M. Joka, “A Method of Defining the Similarity of Images On The Basis of Color Information”, Bulletin of the National Museum of Ethnology, Special Issue, pp. 229-244, No. 17, November 1992. Typically, in such instances, the background is not specified in a query.
Accordingly, the inventor describes a system and method that process a database including video by segmenting a representative video frame into pixels that belong to one or more objects and pixels that belong to background. Values for standard characteristics such as color content, color layout, texture, and size are computed on object pixels. In addition, values for motion characteristics, such as centroid, speed and direction of movement are computed for object pixels. For each group of object pixels that are contained within a respective object, values for image characteristics including color content, color layout, size, and motion of the object's centroid are computed. Similarly, values for standard image characteristics for the background pixels, as well as those for motion, are computed. The computed characteristic values for objects and background are organized and stored in the database. In order to search the database contents, a user can specify, among other parameters, whether to query on background alone, on objects alone, or on a combination of background and objects. A query is executed and results are returned, ranked in order of similarity.
Preferably a plurality of representative frames are segmented and stored in the database, each representing a sequence of frames in one or more video programs. Each of the one or more video programs may be stored in, or in association with, the database.
Accordingly, an object of this invention is to provide a database system containing video with the ability to query database contents based upon segmentation of representative frames into one or more objects and a background. Other advantages of the invention will be understood with reference to the drawings and the detailed description.
REFERENCES:
patent: 5579471 (1996-11-01), Barber et al.
patent: 5664227 (1997-09-01), Mauldin et al.
patent: 5802361 (1998-09-01), Wang et al.
patent: 5819288 (1998-10-01), Bonet
patent: 5835667 (1998-11-01), Wactlar et al.
patent: 5852823 (1998-12-01), Bonet
patent: 5867605 (1999-02-01), Oliveras et al.
patent: 5870768 (1999-02-01), Hekmatpour
patent: 5875446 (1999-02-01), Brown et al.
patent: 5893095 (1999-04-01), Jain et al.
“Query by Image And Video Content: The QBIC System”, M. Flickener, Computer Sep. 1995, pp/ 23-32.
“A Method Of Defining The Similarity of images On The Basis Of Color Information”, M. Ioka, Bulletin of the National Museum of Ethnology Special Issue, pp. 229-244, No. 17, Nov. 1992, from National Museum of Ethnology, Osaka, Japan.
“Model-based 2D & 3D Dominant Motion Estimation For Mosaicing And Video Representation”, H. Sawhney, Jan. 1995, published online at ftp//eagle.almaden.ibm.com.
“Automatic Video Database Indexing and Retrevial”, E. Ardizzone, et al, Multimedia Tools and Applications 4, pp. 29-56, (1997).
“Visual Information Retrivial Technology A VIRAGE Perspective” (Revision 2), A. Gupta, A VIRAGE Perspective, pp. 1-10, Aug. 18, 1995.
“Image Recognition Meets Content Management For Authoring, Editing & More”, C. Okon, Advanded Imaging, pp. 60-62.
“Video Indexing Using Optical Flow Field”, E. Ardizzone & M. L{overscore (a)} Cascia, International Conference On Image Processing, vol. III of III, pp. 931-834, Sep. 16-19, 1996.
“Searching Images Using Ultimedia Manager”, H. Treat et al, IBM Santa Teresa Lab.
“A. Method For Retrieving Sequences Of Images on The Basis of Motion Analysis”, M. Ioka & Kurokawa, SPIE vol. 1662 Image Storage And Retrieval Systems (1992), pp. 35-46.
“Ultimedia Manager 1.1 and Client Search”, Hot Picks brochure.
“QuickTime VR—An Overview of Apple's QuickTime VR Technology”, Apple Computer, Inc., 1995.
“Panoramic Overviews For Navigating Real-World Scenes”, L. Teodosio& M. Mills, pp. 359-364.
“Salient Video Stills: Content and Context Preserved”, L. Teodosio & W. Bender, ACM Multimedia 93, Aug. 1-6, 1993, pp. 39-46.
“VideoMAP and VideoSpacelcon: Tools For Anatomizing Video Content” Y. Tonomura, A. Akutsu, K. Otsuji & T. Sadakata, INTERCHI '93, Apr. 24-29, 1993, pp. 131-136.
“Automatic, Object-Based Indexing for Assisted Analysis Of Video Data”, J. Courtney, Proceedings ACM Multimedia 96, Nov. 18-22, 1996, pp. 423-424.
“Image Segmentation”, http://ciips.ee.uwa.edu.au/~williams/research/complete1995/.
“Image Segmentation Workshop 1996”, The Australian Pattern Recognition Society , http://www.dms.csiro.au/~edb/Segment96/.
Niblack Carlton Wayne
Petkovic Dragutin
Ho Ruay Lian
International Business Machines - Corporation
McGinn & Gibb, P.C.
Tran, Esq. Khanh O.
LandOfFree
Video query system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Video query system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Video query system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2446250