Significant scene detection and frame filtering for a visual indexing system

• US 6,137,544 A
• Filed: 06/02/1997
• Issued: 10/24/2000
• Est. Priority Date: 06/02/1997
• Status: Expired due to Term

• Current Assignee: Pendragon Wireless LLC (Pendrell Corporation)
• Original Assignee: Philips Electronics North America Corporation (Koninklijke Philips N.V.)
• Inventors: Dimitrova, Nevenka, McGee, Thomas, Elenbaas, Jan Hermanus
• Primary Examiner(s): Kostak, Victor R.
• Application Number:
  US08/867,140
• Time in Patent Office: 1,240 Days
• Field of Search: 348/700, 348/701, 348/154, 348/155, 348/400, 348/401, 348/180, 348/407, 348/409, 348/420, 348/722, 386/69, 386/70, 382/107, 382/235, 382/236
• US Class Current: 348/700
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06F 16/7864 using domain-transform features, e.g. DCT or wavelet transform coefficients
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44
• CPC Class Codes: H04N 19/179 the unit being a scene or a shot
• CPC Class Codes: H04N 19/87 involving scene cut or scene change detection in combination with video compression
• CPC Class Codes: H04N 21/458 Scheduling content for creating a personalised stream, e.g. by combining a locally stored advertisement with an incoming stream; Updating operations, e.g. for OS modules ; time-related management operations arrangements for replacing or switching information during the broadcast or during the distribution H04H20/10
• CPC Class Codes: H04N 21/812 involving advertisement data advertising per se G06Q30/02

Abstract

A video indexing system analyzes contents of source video and develops a visual table of contents using selected images. A system for detecting significant scenes detects video cuts from one scene to another, and static scenes based on DCT coefficients and macroblocks. A keyframe filtering process filters out less desired frames including, for example, unicolor frames, or those frames having a same object as a primary focus or one primary focuses. Commercials may also be detected and frames of commercials eliminated.

Claims

1. A system for detecting significant scenes and selecting keyframes of source video, comprising:

a receiver for receiving source video as macroblocks including blocks of DCT coefficients and frames;

a summer calculating a sum for each type of block within a macroblock based on;

##EQU6## where;

k is the number of macroblocks in width of a frame, k=1 to Frame-width/16,

j is the number of macroblocks in height of a frame, j=1 to Frame-height/16,

I is the number of blocks in a macroblock, I=1 to number of blocks in macroblock,

DCT1_k,j and DCT2_k,j are DCT coefficients for the specified macroblock for a previous and a current frame, respectively, and

ABS is an absolute value function;

a threshold calculator calculating a first threshold and a second threshold;

a first comparator for comparing each SUM[i] to the first and second thresholds and saving the current frame as a keyframe in a frame memory if SUM[i] is greater than the first threshold, incrementing a static scene counter if less than the second and saving the previous frame in a temporary memory, and resetting the static scene counter otherwise; and

a second comparator for comparing the static scene counter to a predetermined number and transferring the most previous video frame saved in the temporary memory to the frame memory as a keyframe.

2. A system as recited in claim 1, wherein the first threshold ##EQU7## and the second threshold ##EQU8##

3. A system for detecting significant scenes and selecting keyframes of source video, comprising:

a receiver for receiving source video as macroblocks including blocks of DCT coefficients and frames;

a summer calculating a sum for each macroblock based on;

##EQU9## k is the number of macroblocks in width of a frame, k=1 to Frame-width/16, j is the number of macroblocks in height of a frame, j=1 to Frame-height/16,

I is the number of blocks in a macroblock, I=1 to number of blocks in macroblock,

DCT1_k,j,i and DCT2_k,j,i are DCT coefficients for the specified macroblock and block for a previous and a current video frame, respectively, and

ABS is an absolute value function;

a threshold calculator calculating a first threshold and a second threshold;

a first comparator for comparing each SUM to the first and second thresholds and saving the current frame as a keyframe in a frame memory if SUM is greater than the first threshold, incrementing a static scene counter if less than the second and saving the previous frame in a temporary memory, and resetting the static scene counter otherwise; and

a second comparator for comparing the static scene counter to a predetermined number and transferring the most previous video frame saved in the temporary memory to the frame memory as a keyframe.

4. A system as recited in claim 3, wherein the first threshold ##EQU10## and the second threshold ##EQU11##

5. A system for detecting significant scenes and selecting keyframes of source video, comprising:

a receiver for receiving source video as macroblocks including blocks of DCT coefficients and frames;

a summer calculating a sum for each type of block within a macroblock based on;

##EQU12## where;

k is the number of macroblocks in width of a frame, k=1 to Frame-width/16,

j is the number of macroblocks in height of a frame, j=1 to Frame-height/16,

I is the number of blocks in a macroblock, I=1 to number of blocks in macroblock,

DCT1_k,j and DCT2_k,j are DCT coefficients for the specified macroblock for a previous and a current frame, respectively, and

ABS is an absolute value function;

a threshold calculator calculating a first threshold and a second threshold;

a first comparator for comparing each SUM[i] to the first and second thresholds and saving the current frame as a keyframe in a frame memory if SUM[i] is greater than the first threshold, incrementing a static scene counter if less than the second and saving the previous frame in a temporary memory, and resetting the static scene counter otherwise; and

a second comparator for comparing the static scene counter to a predetermined number and transferring the most previous video frame saved in the temporary memory to the frame memory as a keyframe.

6. A system as recited in claim 5, wherein the first threshold ##EQU13## and the second threshold ##EQU14##

7. A system for detecting significant scenes and selecting keyframes of source video, comprising:

a receiver for receiving source video as macroblocks including blocks of DCT coefficients and frames;

a summer calculating a sum for each type of block within a macroblock based on;

##EQU15## where;

k is the number of macroblocks in width of a frame, k=1 to Frame-width/16,

j is the number of macroblocks in height of a frame, j=1 to Frame-height/16,

I is the number of blocks in a macroblock, I=1 to number of blocks in macroblock,

MB1k,j and MB2_k,j macroblocks for a previous and a current video frame, respectively, and

Mbdiff is a function that determines the number of blocks which are different from each other between two macroblocks, and outputs a first value if this difference is higher than a certain threshold and a second value otherwise;

said summer comprising;

a subsum calculator calculating a subsum for each block, where subsum[i]_j,k =ABS(DCT1[i]_j,k -DCT2[i]_j,k) and DCT1_k,j and DCT2_k,j are DCT coefficients for the specified macroblock;

a subsum comparator comparing each subsum to a first predetermined subsum threshold and if greater than the first predetermined subsum threshold, incrementing a first block counter and comparing each subsum to a second predetermined subsum threshold and if less than the second predetermined subsum threshold, incrementing a second block counter;

a block comparator comparing the first block counter and if above a first predetermined block threshold, incrementing a first macroblock counter and resetting the first block counter for analysis of a next macroblock, and comparing the second block counter and if above a second predetermined block threshold, incrementing a second macroblock counter and resetting the second block counter for analysis of a next macroblock;

a macroblock comparator for comparing the first macroblock counter and if the first macroblock counter is above a first predetermined frame threshold, saving the current frame in frame memory and resetting the first macroblock counter for analysis of a next frame, and comparing the second macroblock counter and if the second macroblock counter is above a second predetermined frame threshold, setting a frame counter and resetting the second macroblock counter; and

a frame comparator comparing the frame counter to a predetermined scene threshold and if greater than the predetermined threshold, saving the previous frame in frame memory as a keyframe.

8. A system as recited in claim 7, wherein:

the first predetermined subsum threshold is th1 is 0.3*subsum[i], and the second predetermined subsum threshold is 0.02*subsum[i].

9. A system for filtering frames from a video source, comprising:

a receiver receiving frames in a frame memory and macroblocks comprising blocks of DCT coefficients in a temporary memory;

a block signature creator for creating a block signature for each block;

a region grower for detecting regions of each frame and a respective size;

a centroid determiner for determining a centroid of each region;

a region signature creator for assigning each region one of the block signatures of the blocks within the region, the respective size, and the centroid;

a frame signature creator for creating a frame signature for a first frame, based on the region signatures; and

a frame comparator for comparing the first frame to a second frame to determine a frame difference and saving or discarding the frame based on the frame difference.

10. A system as recited in claim 9, further comprising an object filter for filtering frames out of frame memory which have a same object as a primary focus or one of the primary focuses of the frame.

11. A system as recited in claim 9, wherein:

each block comprises DCT coefficients including a DC value; and

the block signature comprises a DC signature representative of an interval within which the respective DC value falls.

12. A system as recited in claim 11, further comprising a unicolor filter for detecting unicolor frames which counts the number of blocks having the same DC signature and if the number is greater than a prespecified count, filtering out the frame.

13. A system as recited in claim 9, further comprising a region filterer for filtering out regions not meeting prespecified criteria.

14. A system as recited in claim 9, wherein:

each block comprises DCT coefficients including a DC value; and

the block signature comprises an AC signature of bits such that a prespecified number of bits represents whether a corresponding AC value is above a prespecified value.

15. A system as recited in claim 9, further comprising a unicolor filter for comparing the corresponding size of each region within the frame to a prespecified number and if the corresponding size is greater than the prespecified number, discarding the frame from frame memory.

16. A system as recited in claim 9, wherein said frame comparator comprises:

a region orderer which orders the regions based on prespecified criteria;

a frame difference calculator which calculates a difference between a current frame and a previous frame based on region size; and

a difference comparator which compares the difference to a prespecified frame count and if less than the prespecified frame count, filters the current frame from the frame memory.

17. A system as recited in claim 10, wherein said object filter comprises:

a distance calculator for comparing centers of regions to retrieve a center distance; and

a center distance comparator for filtering the current frame from the frame memory if the center distance is less than or equal to a prespecified value.

18. A system as recited in claim 14, further comprising an object filter for filtering frames out of frame memory which have a same object as a primary focus or one of the primary focuses of the frame, said object filter comprising:

a DC comparator which compares the DC signatures of corresponding blocks of a current frame and a previous frame to determine if the DC signatures match;

an AC comparator which compares the AC signatures of corresponding blocks, each AC value at a time, of the current frame and the previous frame, and counting the number of AC values that match as an AC counter;

a block counter for incrementing a block counter if the DC signatures match and the AC count is greater than a prespecified value and filtering out the current frame from frame memory if otherwise;

a macroblock counter for incrementing a macroblock counter if the block counter is greater than a prespecified value after all blocks in a macroblock have been checked; and

a macroblock comparator for comparing the macroblock counter and if the macroblock counter is greater than a prespecified value, filtering out the current frame from frame memory.

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

a time stamper for associating time stamp for each frame based on a relative time;

a minute density computer for computing a minute density of keyframes in a first time period, based on respective time stamps;

a period density computer for computing a period density of keyframes in a second time period where the first time period is less than the second time period, based on respective time stamps; and

a density comparator for comparing the minute density to a prespecified value based on the period density and if a time stamp of a last frame of a scene is greater than a prespecified time amount, discarding keyframes within the first time period.