Method and apparatus for video cut detection

• US 5,642,294 A
• Filed: 12/15/1994
• Issued: 06/24/1997
• Est. Priority Date: 12/17/1993
• Status: Expired due to Term

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Taniguchi, Yukinobu, Tonomura, Yoshinobu
• Primary Examiner(s): Ramirez, Ellis B.
• Assistant Examiner(s): COLE, TONY MITCHELL
• Application Number:
  US08/356,712
• Time in Patent Office: 922 Days
• Field of Search: 364/514 R, 348/700, 348/701, 348/699, 348/415, 348/403, 348/405, 348/409, 348/416, 348/452, 348/595, 382/107, 358/311, 358/335, 358/346, 352/38, 352/87
• US Class Current: 348/700
• 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/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
• CPC Class Codes: H04N 5/253 Picture signal generating by scanning motion picture films or slide opaques, e.g. for telecine scanning details therefor H04N3/36 ; standard conversion therefor H04N7/0112

Abstract

A buffer memory buffers a sequence of image data I₀, I₁, . . . of respective frames while shifting them step by step and discarding the least recent one of them for each step. An inter-image distance calculating means calculates the distance d(t-i, t-j) between respective pieces of image data held in the buffer memory and stores such distance values in a distance table part in a sequential order. A scene changing ratio calculating part calculates the scene changing ratio C(t-j_c) at time t while referring to the distance table part. A decision part compares the scene changing ratio C(t-j_c) with a predetermined threshold value to determine if the image of a preceding frame j_c -th from the time t is a cut point.

Claims

1. A video cut detection method for detecting a cut point from a video data sequence, comprising the steps of:

(a) calculating the distance d(t-i, t-j) between image data of every pair of images I_t-i and I_t-j having a frame interval therebetween equal to or smaller than J in a sequence of latest J+1 frames of images I_t, I_t-1, . . . , I_t-J which have been supplied sequentially at current time point t, and generating a distance table having a data of the distance d(t-i, t-j) at each position (i, j) of the table, J being a fixed integer equal to or greater than 3 and i and j being all variable integers within the range of 0≦

i<

j≦

J;

(b) calculating a scene changing ratio C(t-j_c) for the range from the J-th preceding frame (t-J) to the current time point t, on the basis of the inter-image distances held on said distance table, j_c being a predetermined constant integer in the range of 0<

j_c ≦

J; and

(c) comparing said scene changing ratio with a predetermined threshold value and, on the basis of the result of said comparison, deciding whether the image of said j_c -th preceding frame is a cut point.

2. The method of claim 1, wherein said step (a) includes a step of calculating, as a value corresponding to said inter-image distance d(t-i, t-j), a difference sum obtained by adding absolute values of intensity differences between pixels at corresponding positions (x, y) of images I_t-i and I_t-j over the entire areas of i-th and j-th frames preceding the current time point t.

3. The method of claim 1, wherein said step (a) includes a step of generating intensity histograms having a predetermined number of classes for images I_t-i and I_t-j of i-th and j-th frames preceding the current time point t and calculating, as a value corresponding to said inter-image distance d(t-i, t-j), a difference sum obtained by adding absolute values of frequency differences between corresponding classes of said histograms.

4. The method of claim 1, wherein said step (a) includes a step of calculating intensity differences between pixels at corresponding positions (x, y) of images I_t-i and I_t-j over the entire areas of i-th and j-th frames preceding the current time point t and providing a standard deviation of said intensity differences as a value corresponding to said inter-image distance d(t-i, t-j).

5. The method of claim 1, wherein said step (a) includes a step of:

calculating intensity differences between pixels at corresponding positions (x, y) of images I_t-i and I_t-j over the entire areas of i-th and j-th frames preceding the current time point t;

calculating a standard deviation of said intensity differences;

counting the number of pixels having absolute values of said intensity differences larger than said standard deviation; and

providing said count value as a value corresponding to said inter-image distance d(t-i, t-j).

6. The method of claim 1, wherein said step (a) includes a step of:

calculating, as first differences, intensity differences between pixels at corresponding positions (x, y) of the images I_t-i and I_t-j over the entire areas of i-th and j-th frames preceding the current time point t;

calculating, as second differences, intensity differences between pixels at corresponding positions (x, y) of images I_t-i-m and I_t-j-m over the entire areas of m-th frames preceding the images I_t-i and I_t-j ;

calculating a standard deviation of said second differences;

counting the number of pixels having absolute values of said first differences larger than said standard deviation; and

providing said count value as a value corresponding to said inter-image distance d(t-i, t-j).

7. The method of claim 1, wherein said step (a) includes a step of:

calculating intensity differences between pixels at corresponding positions (x, y) of images I_t-i-k and I_t-j-k over the entire areas of (k+i)-th and (k+j)-th frames preceding the current time point t;

calculating a standard deviation of said intensity differences repeatedly for k=1, . . . , n;

calculating a mean value T of the resulting n standard deviations, n being a predetermined integer equal to or greater than 1;

calculating intensity differences between pixels at corresponding positions (x, y) of images I_t-i and I_t-j ;

counting the number of pixels having absolute values of said intensity differences larger than said mean standard deviation T; and

providing said count value as a value corresponding to said inter-image distance d(t-i, t-j).

8. The method of claim 1, wherein said step (a) includes a step of:

dividing an image I_t-i of an i-th frame preceding the current time point t into blocks each composed of p by q pixels;

making a check to determine for each of said blocks if said image I_t-j has an area matching said block;

counting the number of blocks which do not match any area in said image I_t-j ; and

providing said count value as a value corresponding to said inter-image distance d(t-i, t-j).

9. The method of claim 1, wherein said step (a) includes a step of shifting distance data at the positions (i, j) in said distance table generated at time point t-1 to positions (i+1, j+1), calculating new distances d(t, t-1), d(t, t-2), . . . , d(t, t-J) as said distances at the current time point t, and writing said calculated values into positions (0, 1), (0, 2), . . . , (0, J) of said distance table, thereby generating said distance table at the time point t.

10. The method of claim 1, wherein the range over which to obtain said inter-image distance in said step (a) is limited to a range which satisfies j-i≦

g, g being a predetermined constant positive integer smaller than J.

11. The method of claim 10, wherein said step (a) includes a step of shifting distance data at the positions (i, j) in said distance table generated at a time point t-1 to positions (i+1, j+1), calculating new distances d(t, t-1), d(t, t-2), . . . , d(t, t-g) as said distances at the current time point t, and writing said calculated values into positions (0, 1), (0, 2), . . . , (0, g) of said distance table, thereby generating said distance table at the time point t.

12. The method of claim 11, wherein said step (b) includes a step in which, letting a first area be defined on said distance table by j_c ≦

j≦

J, 0≦

i<

j_c and j-i≦

g, letting the total sum of distances in said first area be represented by a(j_c), letting a second area be defined on said distance table by 0≦

i<

j≦

j_c -1, j-i≦

g, letting the total sum of distances in said second area be represented by b(j_c), letting a third area be defined on said distance table by j_c ≦

i<

j≦

J, j-i≦

g and letting the total sum of distances in said third area be represented by b'"'"'(j_c), said scene changing ratio is calculated as follows;

space="preserve" listing-type="equation">C(t-j.sub.c)={a(j.sub.c)-β

MAX[b(j.sub.c), b'"'"'(j.sub.c)]}/S

where β

is a predetermined coefficient for making the data numbers in said first area equivalent to the data number in one of said second and third areas corresponding to larger one of b(j_c) and b'"'"'(j_c) and S is the number of data in said first area.

13. The method of claim 11, wherein said step (b) includes a step wherein, letting a first area be defined on said distance table by j_c ≦

j≦

J, 0≦

i<

j_c and j-i≦

g, letting the total sum of distance in said area be represented by a(j_c), letting a second area be defined on said distance table by 0≦

i<

j≦

j_c -1, j-i≦

g, letting the total sum of distances in said second area be represented by b(j_c), letting a third area be defined on said distance table by j_c ≦

i<

j≦

J, j-i≦

g and letting the total sum of distances in said third area be represented by b'"'"'(j_c), said scene changing ratio is calculated as follows;

space="preserve" listing-type="equation">C(t-j.sub.c)={a(j.sub.c)-β

[b(j.sub.c)+b'"'"'(j.sub.c)]}/S

where β

is a predetermined coefficient for making the data number in said first area equivalent to the data number in said second and third areas and S is the number of data in said first area.

14. The method of claim 9, wherein said step (b) includes a step of calculating, as said scene changing ratio, the similarity between a predetermined template of the same size as that of said distance table for the detection of a cut of at least one desired kind and said distance table generated at the time point t.

15. The method of claim 14, wherein said similarity is a cross-correlation coefficient of said distance table and said template.

16. A video cut detection apparatus which detects a cut point from an image data sequence, comprising:

buffer memory means for sequentially buffering image data of at least J+1 temporally successive frames;

inter-image distance calculating means for calculating a distance d(t-i, t-j) between image data of every pair of images I_t-i and I_t-j in the range of 0≦

i<

j≦

J in a sequence of latest J+1 frames of images I_t, I_t-1, . . . , I_t-j which have been supplied at the current time point t, where J is a fixed integer equal to or greater than 3 and i and j are variable integers within the range of 0≦

i≦

j≦

J;

distance table means for storing said inter-image distances calculated by said inter-image distance calculating means;

scene changing ratio calculating means for calculating a scene changing ratio C(t-j_c) for the range from the J-th preceding frame to the current time point t on the basis of said distance table means, j_c being a predetermined constant integer which satisfies 0<

j_c ≦

J; and

decision means for comparing said calculated scene changing ratio with a predetermined threshold value and for deciding whether said frame (t-j_c) is a cut point.

17. The apparatus of claim 16, wherein said buffer memory means includes at least first through (J+1)th frame buffers for temporarily holding image data I_t, I_t-1, . . . , I_t-J of at least J+1 frames ranging from a frame t to the J-th preceding frame;

said inter-image distance calculating means includes first through J-th inter-image distance calculating parts which are supplied with image data I_t-1, I_t-2, . . . , I_t-J from said second through (J+1)th frame buffers, respectively, and supplied, in common, with image data I_t from said first frame buffer, and calculate distances d(t, t-1), . . . , d(t, t-J) between said image data I_t and said image data I_t-1, . . . , I_t-J, respectively; and

said distance table means includes means for generating a distance table by shifting distance data at positions (i, j) on said table means to positions (i+1, j+1) and writing distance data into positions (0,

     1), . . . , (0, J) on said table means, respectively.

18. The apparatus of claim 16, wherein said inter-image distance calculating means is means for calculating said inter-image distances in a further limited range which satisfies i-j≦

g, g being a predetermined constant positive integer smaller than J.

19. The apparatus of claim 17, wherein said distance table means includes means for generating a distance table by shifting distance data at positions (i, j) in said distance table means generated at a time point t-1 to positions (i+1, j+1) and writing new inter-image distances d(t, t-1), d(t, t-2), . . . , d(t, t-g) calculated by said inter-image distance calculating means at the current time point t into positions (0, 1), (0, 2), . . . , (0, g) of said distance table means.

20. The apparatus of claim 19, wherein said scene changing ratio calculating means is means whereby, letting a first area be defined on said distance table means by j_c ≦

j≦

J, 0≦

i<

j_c and j-i≦

g, letting the total sum of distances in said first area be represented by a(j_c), letting a second area be defined on said distance table means by 0≦

i<

j≦

j_c -1, j-i≦

g, letting the total sum of distances in said second area be represented by b(j_c), letting a third area be defined on said distance table means by j_c ≦

i<

j≦

J, j-i≦

g, and letting the total sum of distances in said third area be represented by b'"'"'(j_c), said scene changing ratio is calculated as follows;

space="preserve" listing-type="equation">C(t-j.sub.c)={a(j.sub.c)-β

MAX[b(j.sub.c), b'"'"'(j.sub.c)]}/S

where β

is a predetermined coefficient for making the data numbers in said first area equivalent to the data number in one of said second and third areas corresponding to larger one of said b(j_c) and b'"'"'(j_c) and S is the number of data in said first area.

21. The apparatus of claim 19, wherein said scene changing ratio calculating means is means whereby, letting a first area be defined on said distance table means by j_c ≦

j≦

J, 0≦

i<

j_c and j-i≦

g, letting the total sum of distances in said first area be represented by a(j_c), letting a second area be defined on said distance table means by 0≦

i<

j≦

j_c -1, j-i≦

g, letting the total sum of distances in said second area be represented by b(j_c), letting a third area be defined on said distance table means by j_c ≦

i<

j≦

J, j-i≦

g, and letting the total sum of distances in said third area be represented by b'"'"'(j_c), said scene changing ratio is calculated as follows;

space="preserve" listing-type="equation">C(t-j.sub.c)={a(j.sub.c)-β

[b(j.sub.c)+b'"'"'(j.sub.c)]}/S

where β

is a predetermined coefficient for making the data number in said first area equivalent to the data number in said second and third areas and S is the number of data in said first area.

22. The apparatus of claim 16, wherein said scene changing ratio calculating means is means which has a predetermined template of the same size as that of said distance table means for the detection of a cut of at least one desired kind, for calculating, as said scene changing ratio, the similarity between said template and said distance table means generated at the time point t.