Algorithms and system for object-oriented content-based video search

• US 6,741,655 B1
• Filed: 02/22/2000
• Issued: 05/25/2004
• Est. Priority Date: 05/05/1997
• Status: Active Grant

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Chang, Shih-Fu, Meng, Horace J., Chen, William, Zhong, Di, Sundaram, Hari
• Primary Examiner(s): RAO, ANAND SHASHIKANT
• Application Number:
  US09/423,409
• Time in Patent Office: 1,554 Days
• Field of Search: 348/10-17, 375/240-1-2, 382/230-233, 707/1-4
• US Class Current: 375/240.26
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/7335 Graphical querying, e.g. query-by-region, query-by-sketch, query-by-trajectory, GUIs for designating a person/face/object as a query predicate end-user interface involving hot spots associated with the video H04N21/4725; end-user interface for selecting a Region of Interest H04N21/4728
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06F 16/7854 using shape G06F16/7837 takes precedence
• CPC Class Codes: G06F 16/7857 using texture G06F16/7837 takes precedence
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion

Abstract

Object-oriented methods and systems for permitting a user to locate one or more video objects from one or more video clips over an interactive network are disclosed. The system includes one or more server computers (110) comprising storage (111) for video clips and databases of video object attributes, a communications network (120), and a client computer (130). The client computer contains a query interface to specify video object attribute information, including motion trajectory information (134), a browser interface to browse through stored video object attributes within the server computers, and an interactive video player.

Claims

1. A method for extracting video objects from a video clip which includes at least one recognizable attribute, comprising the steps of:

a. quantizing a present frame of video data therein by determining and assigning values to different variations of said at least one attribute represented by said video data to thereby generate quantized frame information;

b. performing edge detection on said frame of video data based on said at least one attribute to determine edge points in said frame to thereby generate edge information;

c. receiving information defining one or more segmented regions from a previous frame, and

d. extracting regions of video information from said present frame which share said at least one attribute by comparing said received segmented regions to said quantized frame information and said generated edge information.

2. The method of claim 1, wherein said attribute is color, and quantizing step comprises converting said current frame into uniform color space information, adaptively quantizing said color space information into palettes, and filtering said palettes to remove noise therefrom.

3. The method of claim 2, wherein said adaptive quantizing step comprises quantization with a clustering algorithm.

4. The method of claim 1, wherein said edge detection step comprises applying Canny edge detection to said current frame to generate said edge information as an edge map.

5. The method of claim 1, wherein said extracting step comprises:

a. performing interframe projection to extract regions in the current frame of video data by projecting one of the received regions onto the current quantized, edge detected frame to temporally track any movement of the region; and

b. performing intraframe segmentation to merge neighboring extracted regions in the current frame.

6. The method of claim 5, wherein said attribute is color, and wherein said interframe projection step comprises the steps of:

a. projecting said received regions from said previous into said current frame to temporally track regions;

b. labelling each non-edge pixel in said current frame consistent with said received regions or as new a new region; and

c. generating a connection graph from said labels to link neighboring regions.

7. The method of claim 6, wherein said intraframe segmentation step comprises the steps of:

a. merging all adjoining regions having a color distance smaller than a predetermined threshold into a new region;

b. determining a mean color for said new region;

c. updating said connection graph;

d. assigning said new region a new label from labels previously assigned to said merged regions; and

e. dropping said merged regions.

8. The method of claim 5, wherein said extracting step further comprises the step of labeling all edges in the current frame which remain after intraframe segmentation to neighboring regions, so that each labeled edge defines a boundary of a video object in the current frame.

9. The method of claim 8, wherein said extracting step further comprises the step of simplifying said extracted regions by eliminating any regions having a size below a predetermined threshold.

10. The method of claim 1, further comprising the steps of:

e. receiving a future frame of video information;

f. determining the optical flow of said present frame of video information by performing hierarchical block matching between blocks of video information in said current frame and blocks of video information in said future frame; and

g. performing motion estimation on said extracted regions of video information based on said optical flow.