Method and apparatus for detecting abrupt and gradual scene changes in image sequences

• US 6,055,025 A
• Filed: 12/21/1993
• Issued: 04/25/2000
• Est. Priority Date: 12/21/1993
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Shahraray, Behzad
• Primary Examiner(s): LEE, RICHARD J
• Application Number:
  US08/171,136
• Time in Patent Office: 2,317 Days
• Field of Search: 348/384, 348/700, 348/420, 348/413, 348/416, 348/699
• US Class Current: 348/700
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/231 using full search
• CPC Class Codes: G11B 2220/65 wherein solid state memory is used for storing indexing information or metadata
• CPC Class Codes: G11B 27/031 Electronic editing of digitised analogue information signals, e.g. audio or video signals
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence
• CPC Class Codes: H04N 19/142 Detection of scene cut or scene change
• CPC Class Codes: H04N 19/179 the unit being a scene or a shot
• CPC Class Codes: H04N 19/80 Details of filtering operations specially adapted for video compression, e.g. for pixel interpolation H04N19/635, H04N19/86 take precedence
• CPC Class Codes: H04N 19/87 involving scene cut or scene change detection in combination with video compression
• CPC Class Codes: H04N 5/144 Movement detection for video coding H04N19/503; analysis of motion in general G06T7/20
• CPC Class Codes: H04N 5/147 Scene change detection

Abstract

A method is capable of detecting both abrupt and gradual scene changes. Consecutive frames of an image sequence (e.g., a video program) are first acquired and digitized. The images are subdivided into a plurality of rectangular regions. Block matching is performed between the current frame and the Dth previous frame to determine match signals that represent the likelihood that the regions of the first frame contain visual information substantially similar to respective matching regions of the second frame. The match signals are ordered beginning with the match signals defining the best match and ending with the match signals defining the worst match. The first S match signals are selected and averaged together, to obtain an instantaneous match (IM) signal S is user definable and is greater than zero and less than or equal to the number of regions into which each frame is divided. The IM signal provides a criteria for determining whether the first frame belongs to a scene different from the second frame. Finally, a scene change is indicated when the IM signal meets certain decision criteria.

Claims

1. A method of determining scene changes in a sequence of visual information-bearing frames, comprising the steps of:

(a) dividing a first digitized frame into a first plurality of regions and a second digitized frame into a second plurality of regions that respectively correspond in location to the first plurality of regions;

(b) block-matching the regions of the first digitized frame to the regions of the second digitized frame to produce regional match signals that represent a likelihood that the regions of the first digitized frame contain visual information substantially similar to respective matching regions of the second digitized frame;

(c) ordering, to obtain an ordered sequence, the regional match signals beginning with a best regional match signal defining a best match and ending with a worst regional match signal defining a worst match;

(d) averaging together a predetermined number of the regional match signals that are selected in the ordered sequence of step (c) beginning with the best match signal, to obtain an instantaneous match (IM) signal, said IM signal providing a criteria for determining whether the first digitized frame represents a scene different from a scene represented by the second digitized frame; and

(e) indicating a scene change when the IM signal meets a predetermined decision criterion.

2. The method of claim 1 wherein said first and second digitized frames define a first pair of frames and further comprising the step of:

(f) repeating steps (a)-(d) a plurality of times for a sequentially chosen plurality of pairs of frames of a sequence of frames.

3. The method of claim 2 further comprising the step of temporally filtering a plurality of IM signals before the step of indicating a scene change.

4. The method of claim 3 in which the filtering step comprises the step of subtracting a constant noise value from the IM signal.

5. The method of claim 4 wherein the step of temporally filtering the IM signals comprises the step of temporally filtering the IM signals with an infinite-impulse-response digital filter having a variable gain and a range limiter.

6. The method of claim 3 further comprising the step of varying the gain during the step of temporally filtering the IM signals in response to a predefined condition.

7. The method of claim 6 wherein the predefined condition is a function of a regional match signal and a motion vector.

8. The method of claim 7 wherein the regional match signal is the ratio of a minimum block matching error to an average value of the block matching error.

9. The method of claim 3 wherein the regional match signal for each of the regions of the first digitized frame and the second digitized frame upon which block matching is performed is the ratio of a minimum block matching error to an average value of the block matching error.

10. The method of claim 3 wherein the step of temporally filtering the IM signal produces a cumulative match CM signal and the step of indicating a scene change includes the step of indicating a scene change when both the IM and the CM signals meet certain decision criteria.

11. The method of claim 10 wherein each frame has a contrast value associated therewith, and further comprising the step of

determining an image contrast (IC) signal representing the contrast value associated with at least one frame of the pair of frames;

and

indicating a scene change when the IM, the CM, and the IC signals meet certain decision criteria.

12. The method of claim 1 wherein the regional match signal for each of the regions of the first digitized frame and the second digitized frame upon which block matching is performed is a ratio of a minimum block matching error to an average value of the block matching error.

13. The method of claim 1 wherein the first digitized frame is divided into K regions and further comprising the step of:

(f) repeating steps (c) and (d) for each of said K regions to obtain K minimum values and K normalized minimum values respectively corresponding to the K regions.

14. The method of claim 13 further comprising the steps of:

(g) ordering by magnitude the K normalized minimum values, beginning with a smallest normalized minimum value and ending with a largest normalized minimum value;

(h) calculating an instantaneous match (IM) signal having a value determined by selecting and averaging together a first S of the K ordered normalized minimum values, where S≦

K and is user definable, said IM signal providing a criteria for determining whether the first digitized frame belongs to a scene different from the second digitized frame.

15. The method of claim 14 wherein said first and second digitized frames define a first pair of frames and further comprising the steps of:

(i) repeating steps (a)-(h) a plurality of times for a sequentially chosen plurality of pairs of frames of a sequence of frames in place of the first pair of frames to calculate a plurality of values of the IM signal such that said IM signal provides a criterion for determining whether one frame of one of the pairs of frames belongs to a scene different from another frame of the pair of frames.

16. The method of claim 15 further comprising the step of:

(j) preselecting an upper threshold value and a lower threshold value of the IM signal such that a change in the value of the IM signal to a value below the lower threshold value after having been above the upper threshold value at a previous time corresponds to a scene change at the point in the sequence between the pair of frames at which the IM signal changed from the value above the upper threshold value to below the lower threshold value.

17. The method of claim 15 further comprising the step of temporally filtering said IM signal with a digital filter having a variable gain to generate a cumulative match signal, said cumulative match signal providing a criterion for determining whether a scene change has occurred over a plurality of frames.

18. The method of claim 17 further comprising the step of subtracting a constant noise value from the IM signal before the step of temporally filtering the IM signal.

19. A method of determining scene changes in a sequence of visual information-bearing frames, comprising the steps of:

(a) digitizing at least first and second frames of the sequence;

(b) dividing the first frame into a first plurality of regions and the second frame into a second plurality of regions respectively corresponding in location and size to the first plurality of regions of the first frame;

(c) block-matching by

(i) determining values of a first match distance between a first region of the first plurality of regions and a plurality of regions of the same size as said first region within a portion of the second frame encompassing the corresponding region in the second frame; and

(ii) finding a minimum value among said values, said minimum value corresponding to the location of a matching region of the second frame that is defined relative to the location of the corresponding region in the first frame, said matching region being a region of the second frame most likely to contain visual information substantially similar to the first region of the first frame;

(d) calculating an average value of all the values of the first match distance and normalizing the minimum value of the first match distance by dividing said minimum value by said average value to obtain a normalized minimum value, said normalized minimum value representing the likelihood that the matching region contains information substantially similar to the first region of the first frame.

20. The method of claim 19 further comprising the step of:

generating a motion vector, said motion vector equalling a distance defined by the location of the matching region relative to the location of the corresponding region of the second frame.

21. The method of claim 19 wherein said first and second frames are consecutive frames in the sequence.

22. The method of claim 19 wherein said first and second frames are spaced apart a predetermined number of frames.

23. The method of claim 22 further comprising the step of detecting single frame noise.

24. The method of claim 23 wherein the single frame noise is produced by a camera flash.

25. A method of determining scene changes in a sequence of visual information-bearing frames, said method comprising the steps of:

comparing in a sequential order a plurality of pairs of frames to generate an instantaneous match (IM) signal representing a similarity between the frames of each pair;

temporally filtering the IM signal to generate a cumulative match (CM) signal; and

indicating a scene change when the IM signal and the CM signal meet a predetermined decision criterion.

26. Apparatus for determining scene changes in a sequence of visual information-bearing frames, comprising:

means for comparing in a sequential order a plurality of pairs of frames to generate an instantaneous match (IM) signal representing a similarity between the frames of each pair;

means for temporally filtering the IM signal to generate a cumulative match (CM) signal; and

means for indicating a scene change when the IM signal and the CM signal meet certain decision criteria.

27. Apparatus for determining scene changes in a sequence of visual information-bearing frames, comprising:

(a) means for dividing a first digitized frame into a first plurality of regions and a second digitized frame into a second plurality of regions that respectively correspond in location to the first plurality of regions;

(b) means for block-matching the regions of the first digitized frame to regions of the second digitized frame to produce regional match signals that represent a likelihood that the regions of the first digitized frame contain visual information substantially similar to respective matching regions of the second digitized frame;

(c) means for ordering the regional match signals beginning with a best regional match signal defining a best match and ending with a worst regional match signal defining a worst match;

(d) means for averaging together a predetermined number of the best regional match signals that are selected in the ordered sequence obtained by said ordering means, beginning with the best match signal, to obtain an instantaneous match (IM) signal, said IM signal providing a criteria for determining whether the first digitized frame represents a scene different from a scene represented by the second digitized frame; and

(e) means for indicating a scene change when the IM signal meets a predetermined decision criterion.