Browsing contents of a given video sequence

• US 5,521,841 A
• Filed: 03/31/1994
• Issued: 05/28/1996
• Est. Priority Date: 03/31/1994
• Status: Expired due to Term

• Current Assignee: Siemens Corp. (Siemens AG)
• Original Assignee: Siemens Corporate Research Incorporated (Siemens AG)
• Inventors: Depommier, Remi, Chiu, Ming-Yee, Arman, Farshid, Hsu, Arding
• Primary Examiner(s): Ramirez, Ellis B.
• Assistant Examiner(s): Assouad, Patrick J.
• Application Number:
  US08/221,221
• Time in Patent Office: 789 Days
• Field of Search: 364/514 A, 364/514 B, 364/514 C, 364/514 R, 395/154, 395/100, 395/106, 395/109, 358/311, 345/112, 345/121, 345/115
• US Class Current: 715/723
• CPC Class Codes: G06F 16/745 the internal structure of a single video sequence
• 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 3/0485 Scrolling or panning
• CPC Class Codes: G09B 5/065 Combinations of audio and video presentations, e.g. videotapes, videodiscs, television systems
• CPC Class Codes: G11B 27/034 on discs G11B27/036, G11B27/038 take precedence
• 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: G11B 27/34 Indicating arrangements indicating means incorporated in magazine or cassette G11B23/046 and G11B23/0875; indicating measured values in general G01D
• CPC Class Codes: H04N 5/147 Scene change detection

Abstract

A method for representing contents of a video sequence for allowing a user to rapidly view a video sequence in order to find a particular desired point within the sequence and/or to decide whether the contents of a video sequence are relevant to a user, the video sequence having been pre-processed to detect scene changes and to build Rframes, and for allowing a user to scroll through the Rframes and to stop at a selected Rframe for processing, comprises playing the video sequence from a point of the selected Rframe, detecting all Rframes having respective degrees of similarity to the Rframe selected by the user, and presenting the similar Rframes to the user in a size or scale representative of the degrees of similarity.

Claims

1. A computer-implemented method for representing contents of a video sequence for allowing a user to rapidly view a video sequence in order to find a particular desired point within said sequence and/or to decide whether said contents of a video sequence are relevant to a user, said video sequence having been pre-processed to detect scene changes and to build Rframes, an Rframe being a representation of a sequence of images, and for allowing a user to scroll through said Rframes in a given manner and to stop at a selected Rframe for processing, said method comprising:

(a) playing said video sequence from the beginning of a shot represented by said selected Rframe to the end of said shot;

(b) detecting all Rframes having respective degrees of similarity to said Rframe selected by said user; and

(c) presenting said similar Rframes to said user in a size or scale representative of said degrees of similarity.

2. A method for representing contents of a video sequence in accordance with claim 1, wherein step (b) is performed by evaluating Rframe shape properties represented by using a respective moment for each Rframe image.

3. A method for representing contents of a video sequence in accordance with claim 2, wherein said moment of said R frame image is defined as:

space="preserve" listing-type="equation">m.sub.pq =Σ

Σ

x.sup.p y.sup.q ƒ

(x,y) (2)

where, in reference to an image f(x,y), m₀₀ corresponds to a total mass of a frame and m₂₀ correspond to moments of inertia about the x and y axes, and a moment invariant derived therefrom is defined as ##EQU9## and the first few moment invariants are defined as

space="preserve" listing-type="equation">φ

.sub. =η

.sub. 2 +η

.sub. 02

space="preserve" listing-type="equation">φ

.sub.2 =(η

.sub.20 -η

.sub.02).sup.2 +4η

.sub.11.sup.2 (

     4)

space="preserve" listing-type="equation">φ

.sub.3 =(η

.sub.30 -3η

.sub.12).sup.2 +(3η

.sub.21 -η

.sub.03).sup.2

The shape of each Rframe is then represented using the vector σ

defined as;

space="preserve" listing-type="equation">σ

={φ

.sub.1, φ

.sub.2, φ

.sub.3, . . . , φ

.sub.7 }(5)

and a "metric distance" ψ

(α

,β

) is used to measure the similarity of two Rframes;

space="preserve" listing-type="equation">ψ

(α

,β

)=|σ

.sub.α

-σ

.sub.β

|.sup.2

4. A method for representing contents of a video sequence in accordance with claim 1, wherein step (b) is performed by evaluating Rframe color properties represented by using color histograms.

5. A method for representing contents of a video sequence in accordance with claim 1, wherein step (b) is performed by evaluating shape properties represented by using moments and Rframe color properties represented using color histograms.

6. A method for representing contents of a video sequence in accordance with claim 5, wherein said moment of said R frame is defined as:

space="preserve" listing-type="equation">m.sub.pq =Σ

Σ

x.sup.p y.sup.q ƒ

(x,y) (2)

and a moment invariant derived therefrom is defined as ##EQU10## the first few moment invariants are defined as

space="preserve" listing-type="equation">φ

.sub. =η

.sub. 2 +η

.sub. 02

space="preserve" listing-type="equation">φ

.sub.2 =(η

.sub.20 -η

.sub.02).sup.2 +4η

.sub.11.sup.2 (

     4)

space="preserve" listing-type="equation">φ

.sub.3 =(η

.sub.30 -3η

.sub.12).sup.2 +(3η

.sub.21 -η

.sub.03).sup.2

The shape of each Rframe is then represented using the vector σ

defined as;

space="preserve" listing-type="equation">σ

={φ

.sub.1, φ

.sub.2, φ

.sub.3, . . . , φ

.sub.7 }(5)

and a "metric distance" is used to measure the similarity of two Rframes;

space="preserve" listing-type="equation">ψ

(α

,β

)=|σ

.sub.α

-σ

.sub.β

|.sup.2

and

wherein a color histogram is obtained by counting how many times each color appears in each Rframe, using hue and saturation components of the HSI color space to calculate the color histogram for each Rframe; and

measuring similarity by the technique of histogram intersection, defined as;

##EQU11## where α and

β

are the two histograms, whereby the result of this intersection indicates how many pixels in one image have corresponding pixels of the same color in the other image, and the measure is normalized using;

##EQU12## where β

_i is the ith histogram.

7. A computer-implemented method for representing contents of a video sequence for allowing a user to rapidly view a video sequence in order to find a particular desired point within said sequence and/or to decide whether said contents of a video sequence are relevant to a user, said video sequence having been pre-processed to detect scene changes and to build Rframes, an Rframe being a representation of a sequence of images, and for allowing a user to scroll in a given order through said Rframes and to stop at a selected Rframe for processing, said method comprising:

(a) playing said video sequence from the beginning of a shot represented by said selected Rframe to the end of said shot;

(b) detecting all Rframes having respective degrees of similarity to said Rframe selected by said user; and

(c) presenting Rframes having one of a predetermined degree of similarity to said Rframe selected by said user and predetermined degree of dissimilarity to said Rframe selected by said user.

8. A method for representing contents of a video sequence in accordance with claim 7, comprising the steps of:

comparing remaining, non-selected Rframes in said video sequence using moment and color histogram-based descriptions;

mapping similarity measures using;

##EQU13## where ζ

=ε

(α

, β

_i) for mapping of color histogram intersection output of the equation

space="preserve" listing-type="equation">Ω

.sub.histogram [ε

(α

,β

.sub.i)] ε

{1,2,3}

and ζ

=(α

,β

_i) for mapping moment distance measure of the equation

space="preserve" listing-type="equation">Ω

.sub.moment [(α

,β

.sub.i)] ε

{1,2,3}, where

Ω

=3signifies very similar, Ω

=2 somewhat similar, and Ω

=1 not similar.

9. A method for representing contents of a video sequence in accordance with claim 8, wherein

if Ω

moment=1 then the output of said comparing using said color-histogram-based description is ignored;

if Ω

moment=3 then a final output is very similar, an only exception being when color-based output Whistogram=1 in which case said final output will also be 2, or somewhat similar; and

utilizing mapping from using said color-histogram-based description when Wmoment is not conclusive.