Language selection

Search

Patent 2272064 Summary

Third-party information liability

Some of the information on this Web page has been provided by external sources. The Government of Canada is not responsible for the accuracy, reliability or currency of the information supplied by external sources. Users wishing to rely upon this information should consult directly with the source of the information. Content provided by external sources is not subject to official languages, privacy and accessibility requirements.

Claims and Abstract availability

Any discrepancies in the text and image of the Claims and Abstract are due to differing posting times. Text of the Claims and Abstract are posted:

  • At the time the application is open to public inspection;
  • At the time of issue of the patent (grant).
(12) Patent: (11) CA 2272064
(54) English Title: METHOD OF PROCESSING A VIDEO STREAM
(54) French Title: PROCEDE DE TRAITEMENT D'UN FLUX DE DONNEES VIDEO
Status: Term Expired - Post Grant Beyond Limit
Bibliographic Data
(51) International Patent Classification (IPC):
  • H04N 5/14 (2006.01)
(72) Inventors :
  • HIRZALLA, NAEL (United States of America)
  • MACLEAN, ROGER (Canada)
  • STREATCH, PAUL (Canada)
  • MENARD, ROB (Canada)
(73) Owners :
  • MARCH NETWORKS CORPORATION
(71) Applicants :
  • TELEXIS CORPORATION (Canada)
(74) Agent: MARKS & CLERK
(74) Associate agent:
(45) Issued: 2005-11-22
(86) PCT Filing Date: 1997-11-20
(87) Open to Public Inspection: 1998-05-28
Examination requested: 2002-10-04
Availability of licence: N/A
Dedicated to the Public: N/A
(25) Language of filing: English

Patent Cooperation Treaty (PCT): Yes
(86) PCT Filing Number: PCT/CA1997/000881
(87) International Publication Number: WO 1998023085
(85) National Entry: 1999-05-17

(30) Application Priority Data:
Application No. Country/Territory Date
2,190,785 (Canada) 1996-11-20

Abstracts

English Abstract


A method of processing a video stream, involves contemporaneously selecting
first and second pairs of frames in the video stream
with a predetermined period. The second pairs of frames have a longer period
than the first pairs. For each of the first and second pairs
of frames, there is determined a difference value representing the number of
pixels whose value has changed between the first and second
frames of the pair. A particular logic level is generated depending on whether
this difference value exceeds a predetermined threshold. The
generated logic levels are then compared with a decision map to identify cuts
in the video stream.


French Abstract

Ce procédé de traitement d'un flux de données vidéo consiste à choisir simultanément, dans ce flux, des premières et secondes paires de trames possédant une période déterminée, les secondes paires de trames ayant une période plus longue que celle des premières paires. Pour chacune des premières et secondes paires de trames, il est procédé à la détermination d'une valeur de différence représentant le nombre de pixels dont la valeur a changé entre les première et seconde trames de la paire, ainsi qu'à la production d'un niveau de logique particulier dans le cas où cette valeur de différence excède un seuil déterminé. Il est enfin procédé à la comparaison des niveaux logiques produits à l'aide d'une carte de décision, afin d'identifier des coupures dans le flux de données vidéo.

Claims

Note: Claims are shown in the official language in which they were submitted.


-8-
Claims:
1. A method of processing a video stream, comprising the steps of:
selecting first pairs of frames in the video stream with a predetermined
temporal
spacing;
selecting second pairs of frames in the video stream, said second pairs of
frames
having a longer temporal spacing than said first pairs of frames;
for each of said first and second pairs of frames, determining a difference
value
representing the degree of change between the first and second frames of the
pair and
generating a particular logic level depending on whether this difference value
exceeds a
predetermined threshold; characterized in that
the change in interframe difference value for successive pairs of frames is
determined for each of said first and second pairs of frames and compared with
a
threshold to generate additional logic levels dependent on the change in
interframe
difference values for said successive frame pairs; and
the generated logic levels are compared with a decision map to identify cuts
in the
video stream.
2. A method as claimed in claim 1, wherein the degree of change between frames
of
a pair is represented by the number of pixels for which a value has changed.
3. A method as claimed in claim 1 or claim 2, wherein said threshold is
different for
each of said first and second pairs of frames.
4. A method as claimed in claim 3, wherein said change in interframe
difference
value is determined by comparing the interframe difference for the current
pair of frames
with the average interframe difference for previous pairs of frames.
5. A method as claimed in claim 3, wherein said change in interframe
difference
value is determined by comparing the interframe difference for the current
first or second
pair of frames with the interframe difference for the respective previous
first or second
pair of frames.
6. A method as claimed in any of claims 1 to 5, wherein said value is the
pixel
intensity.

-9-
7. A method as claimed in any of claims 1 to 6, wherein said frames are
divided into
at least one window and said processing steps are carried out within a
selected window.
8. A method of detecting scene changes in a video stream comprising detecting
cuts
by a method as claimed in any one of claims 1 to 7.
9. A method of creating a video index which includes detecting cuts by a
method as
claimed in any one of claims 1 to 7.
10. A method of transforming from video to pictorial transcripts which
includes
detecting cuts by a method as claimed in any one of claims 1 to 7.
11. A method of recognizing video sequences which includes detecting cuts by a
method as claimed in any one of claims 1 to 7.
12. A method of motion detection which includes detecting cuts by a method as
claimed in any one of claims 1 to 7.
13. A method of motion tracking which includes detecting cuts by a method as
claimed in any one of claims 1 to 7.
14. A method of bandwidth reduction which includes detecting cuts by a method
as
claimed in any one of claims 1 to 7.
15. Video processing apparatus comprising:
means for selecting first pairs of frames in the video stream with a
predetermined
temporal spacing;
means for selecting second pairs of frames in the video stream, said second
pairs
of frames having a longer temporal spacing than said first pairs of frames;
means for determining, for each of said first and second pairs of frames, a
difference value representing the degree of change between the first and
second frames of
the pair and generating a particular logic level depending on whether this
difference value
exceeds a predetermined threshold; characterized in that it further comprises
means for computing the change in interframe difference value for successive
pairs of frames for each of said first and second pairs of frames and
comparing said
change with a threshold to generate additional logic levels dependent on the
change in
interframe difference values for said successive frame pairs; and

-10-
means for comparing the generated logic levels with a decision map to identify
cuts in the video stream.
16. Video processing apparatus as claimed in claim 15, wherein said
determining
means determines the number of pixels for which a value has changed.
17. Video processing apparatus as claimed in claim 15, characterized in that
said
means for computing the change in interframe difference value compares the
interframe
difference for the current pair of frames with the average interframe
difference for
previous pairs of frames.
18. Video processing apparatus as claimed in claim 15, characterized in that
said
means for computing the change in interframe difference value compares the
interframe
difference for the current first or second pair of frames with the interframe
difference for
the respective previous first or second pair of frames.

Description

Note: Descriptions are shown in the official language in which they were submitted.


CA 02272064 2004-11-23
-1
METHOD OF PROCESSING A VIDEO STREAM
This invention relates to a method of processing a video stream, to detect
changes,
for example, a cut in scenes.
In video terminology, a video stream consists of a number of frames that are
displayed successively to create the illusion of motion. A sequence of frames
can be
considered to form a "scene", which is considered to be a continuous action in
space and
time (i.e. with no camera breaks). A "cut" is a discontinuity between scenes.
A cut is
sharp if it can be located between two frames and gradual if it takes place
over a
sequence of frames. A keyframe is a frame that represents a whole scene. It
can either be
calculated or selected from the frames of the scene it represents.
There are many situations where it is desirable to select a cut. For example,
selecting keyframes to transmit over a network, save onto a hard disk, or use
to browse a
video can reduce bandwidth, capacity and time than considering the whole video
data.
However, video segmentation is a difficult process in view of the various
types of camera
breaks and different operations that can take place.
Video parameters include intensity, red-green-blue (RGB), hue-value-chroma
(HVC), and a motion vector. A traditional approach for detecting a cut is to
compare one
or more of these parameters, such as intensity, of the corresponding pixels in
a pair of
consecutive frames. If the number of pixels whose intensity values have
changed from
one frame to the next exceeds a certain threshold, a cut is presumed. However,
such an
approach results in low detection rates and result in the detection of false
cuts or missing
real cuts. False cuts may result from camera operations, object movements or
flashes
within a video clip, while missed cuts may result from gradual scene changes.
EP 696 016A describes a cut detection method wherein a scene changing ratio is
computed taking into account the frame difference between temporally spaced
images as
well as temporally successive images. EP 660327describes a method for
detecting abrupt
and gradual scene changes wherein matching is performed between a current
frame and a
D~' previous frame. Neither of these patents satisfactorily solves the
problems outlined
above.
An object of the invention is to alleviate the afore-mentioned problems.

CA 02272064 2004-11-23
-2-
According to the present invention there is provided a method of processing a
video stream, comprising the steps of selecting first pairs of frames in the
video stream
with a predetermined temporal spacing; selecting second pairs of frames in the
video
stream, said second pairs of frames having a longer temporal spacing than said
first pairs
S of frames; for each of said first and second pairs of frames, determining a
difference value
representing the degree of change between the first and second frames of the
pair and
generating a particular logic level depending on whether this difference value
exceeds a
predetermined threshold; characterized in that the change in interframe
difference value
for successive pairs of frames is determined for each of said first and second
pairs of
frames and compared with a threshold to generate additional logic levels
dependent on the
change in interfi~ame difference values for said successive frame pairs; and
the generated
logic levels are compared with a decision map to identify cuts in the video
stream.
The degree of change may be represented by the number of pixels for which a
particular value, such as intensity, has changed. Alternatively, the
difference value may be
arrived at by, for example, taking the root mean square of the differences in
pixel values.
In this case, the difference in intensity value of each corresponding pair of
pixels is
determined, the results squared, and the square root taken of the sum. This
rms value can
then be compared to a threshold. A value other than intensity, for example
hue; can be
chosen for the value.
By this method, gradual cuts between scenes can be more accurately detected
and
the occurrence of false detections can be reduced.
In a preferred embodiment, the change in difference value between each of the
first and second pairs of fi~ames and the corresponding previous pairs is
determined, and
additional logic levels are generated that depend on whether the change in
difference
values exceeds a predetermined threshold. The additional logic levels are also
compared
with the decision map to assist in identifying the cuts. This additional step
enhances the
detection process.
The invention also provides video processing apparatus comprising means for
selecting first pairs of frames in the video stream with a predetermined
temporal spacing;
means for selecting second pairs of frames in the video stream, said second
pairs of
frames having a longer temporal spacing than said first pairs of frames; means
for

CA 02272064 2004-11-23
-3-
determining, for each of said first and second pairs of frames, a difference
value
representing the degree of change between the first and second frames of the
pair and
generating a particular logic level depending on whether this difference value
exceeds a
predetermined threshold; characterized in that it further comprises means for
computing
the change in interframe difference value for successive pairs of frames for
each of said
first and second pairs of frames and comparing said change with a threshold to
generate
additional logic levels dependent on the change in interframe difference
values for said
successive frame pairs; and means for comparing the generated logic levels
with a
decision map to identify cuts in the video stream.
The invention will now be described in more detail, by way of example, only
with
reference to the accompanying drawings, in which:-
Figure 1 is a block diagram of an apparatus for detecting cuts in a video
stream;
Figure 2 illustrates the main processing routine;
Figure 3 illustrates the detection processing routine;
Figure 4 illustrates the compare frames processing routine;
Figure S illustrates the change detection routine;
Figure 6 illustrates the set tag routine; and
.Figure 7 shows typical threshold values.
The system illustrated is typically implemented on a Pentium 133 MHz computer.
A digital video stream, for example, from a digital video camera or an analog
feed passed
through an analog-to-digital converter (not shown), is split and passed to
short and long
period units l, 2. The short period comparison unit identifies a pair of
fi~mes in a stream,
for example, the fourth and fifth frames, and determines the number of pixels
whose
values have changed. This number is then compared with a threshold and
allocated a logic
level 1 if it exceeds the threshold and otherwise a logic level 0. The pixel
values can be
any suitable value, but typically the intensity is used.
The long period comparison unit 2 carnes out the same operation, except on
pairs
of frames that are temporally further apart, for example, first and eighth
frames in the

CA 02272064 2004-11-23
-4-
video stream. It generates a logical 1 if the number of pixels whose intensity
values have
changed exceeds a predetermined threshold. Otherwise it generates a logical 0.
The video stream is then passed to the short period change detection unit 3
and the
long period change detection unit 4. The short period change detection unit 3
compares
the current interframe difference value, derived in unit l, namely the number
of pixels
whose intensity values have changed between each pair of pixels, with the
previous pair,
or the average of all the previous pairs, of interframe difference values to
derive the
change. If the change in interframe difference values exceeds a predetermined
threshold, a
logical 1 is generated, otherwise a logical 0 is generated.
The long period change detection unit 4 does the same as the short period
change
detection unit, except with frames separated by a longer period, the first and
eighth frames
in this example. The threshold for the long period change detection unit is
typically higher
than for the short period detection unit.
A decision map shown below is stored in unit 5.
Short- Short- Long- Long-Period Type of Cut?
Change Period Change Cut Change
Cut
0 X X 0 - No
X X 0 1 Action No
X 0 1 1 Gradual Yes
0 1 1 1 Action No
1 X X 0 Flashes No
1 1 1 1 Shar Yes
This contains a table of all possible values of the logic outputs of units 1
to 4,
logic level 0 representing a comparison below the threshold, logic 1 being a
comparison
above the threshold and X, where X means "don't care". i.e. 0 or 1. For
example, in the
short change column, a 1 means that unit 3 detects a change in difference
values between
successive pairs of frames above a threshold, 0 means any change was below the
threshold, and X means that the outcome of the short change comparison is not
relevant to
the decision.

CA 02272064 2004-11-23
-S-
The system shown in Figure 1 moves through successive frames as follows. For
example, if the system processes six frames at a time, frames l and 6 would
form the long
pair and frames 3 and 4 might form the short pair. If no cuts are detected in
this block, the
next block will be made of frames 2 to 7, with frames 2 and 7 forming the long
pair, and
frames 4 and 5 forming the short pair and so on. However, if a cut is
detected, the next
block will contain frames 6 to 11 since the block size is very small compared
to a typical
scene length and no two cuts can be detected within one block.
On looking at the table above, it will be observed that a positive result for
all four
comparisons indicates a true sharp cut, whereas a positive result in the long
change and
long period detector without a corresponding result in the short period
detector indicates a
probable gradual cut.
A frame may contain one or more windows to which the above described process
can be applied. The use of windows allows the system to focus on specific
areas of a
frame instead of considering the frame as a whole. This can save considerable
processing
time.
The main processing routine is shown in Figure 2. Starting at block 10, the
routine
determines at process blockl 1 whether the frame is decompressed. If not, it
is
decompressed in process block 12. At process block.13, the frame number is
incremented.
Decision block 14 determines whether variable jump (set in the Tag routine to
be
described) is greater than 0 and the number of sectors is greater than 1. If
not, and the
FrameNo variable is greater than the Blocksize variable, block 15 calls the
call detection
routine shown in Figure 3. If the output of Decision block 14 is true, block l
6 decrements
the jump variable.
Figure 3 shows the cut detection routine. Starting from process block 21,
block 22
performs the short frame comparison and block 23 performs the long frame
comparison to
determine the number of pixels whose intensity values have changed for each
pair frames.
Process blocks 27, 28 determine whether the percentage change is above the
threshold for the associated window, and if so generate a logical 1, otherwise
they
generate a logical zero.

CA 02272064 2004-11-23
-6-
Process blocks 2S and 26 perform the short and long change detection
operations
following which block 29 calls the set tag routine described with reference to
Figure 4.
Process block 30 causes the routine to loop for all windows of interest
assuming the
system is operating on the basis that there is more than one window. Of
course, there
S could only be one window that represents a whole frame.
Figure 4 shows the compare frames routine in more detail. Processing blocks
40,
41 loop for all the pixels in a row and column respectively. Block 42 then
finds the
differences between the corresponding pixels in the first and second frames of
each pair.
If the decision unit 43 finds a difference greater than a threshold, the CP
variable, which
represents the percentage change of the window containing the pixels is
incremented.
Figure S shows the change detection routine identified in blocks 2S, 26 in
Figure 3
in more detail. Block 50 finds the difference between the change period CP for
the
window and the average change period CPA. If this change is greater than a
threshold, as
determined in decision unit S3, and the condition in block S4 is met, process
block SS sets
1 S the output to logical 1 to indicate a change. The change detection routine
shown in Figure
S works for both long period and short period changes.
Referring now to Figure 6, the tag routine essentially implements the decision
map
table shown in Figure 7. Starting from process block 60 called by process
block 29 in
Figure 3, the routine determines whether there has been a short period change
in block 61.
If yes, decision block 63 determines whether there has been a short period
cut, long period
cut, and long period change. If yes, the block 67 creates a cut tag. If.no,
the block 68
determines whether there has been long period cut. If yes, block 71 creates a
flash tag.
If the result of decision block 68 is true, block 69 checks the condition
!SPcut, and
LPcut and LPchange is met, where ! SPcut means that the SPcut variable is
logical 0, or in
2S other words no cut was detected in the short period. If yes, block 73
creates a cut tag. If
no, block 74 creates an action tag.
If the result of decision block 61 is no, decision block 62 determines whether
the
condition !SPcut and LPcut and Lpchange has been met. If yes, block 64 creates
a cut tag
and sets the variable jump equal to the block size. If no, block 65 determines
whether

CA 02272064 2004-11-23
_'
there has been an LP cut. If no, block 70 creates a no cut tag; if yes, block
74 creates an
action tag.
The program then moves on to a following block of frames to repeat the
process,
continually creating tags identifying cuts and indicating whether a cut has
been detected
in the processed block.
Figure 7 shows typical short-period interframe difference values expressed as
a
percentage vs. Frame number. Although Threshsold~oNCpExroD is applied on the
corresponding long-term chart, it is shown in this figure as well.
The described method has many uses. -For example, it can be applied to scene
. change detection with automatic cut detection and flagging, visual index
creation for
videos, video transformation from video to pictorial transcripts and
illustrated audio,
video sequence recognition, motion detection, motion tracking and sizing, and
bandwidth
reduction by extracting only changing information from a scene.
The described method can achieve a high and robust video cut detection rate in
. part due to the change detection routine, satisfy real-time requirements. It
can easily be
applied only to specific windows of interest within a frame in the manner
described. It can
be applied to automatic television monitoring and be situated either at the
network access
point or at the user end. It can also be integrated with any database
management system
that needs to index or store video.

Representative Drawing
A single figure which represents the drawing illustrating the invention.
Administrative Status

2024-08-01:As part of the Next Generation Patents (NGP) transition, the Canadian Patents Database (CPD) now contains a more detailed Event History, which replicates the Event Log of our new back-office solution.

Please note that "Inactive:" events refers to events no longer in use in our new back-office solution.

For a clearer understanding of the status of the application/patent presented on this page, the site Disclaimer , as well as the definitions for Patent , Event History , Maintenance Fee  and Payment History  should be consulted.

Event History

Description Date
Inactive: Expired (new Act pat) 2017-11-20
Grant by Issuance 2005-11-22
Inactive: Cover page published 2005-11-21
Inactive: Final fee received 2005-08-25
Pre-grant 2005-08-25
Inactive: Delete abandonment 2005-03-03
Letter Sent 2005-03-03
Notice of Allowance is Issued 2005-03-03
Notice of Allowance is Issued 2005-03-03
Inactive: Adhoc Request Documented 2005-03-03
Inactive: Abandoned - No reply to Office letter 2005-02-04
Amendment Received - Voluntary Amendment 2004-11-23
Letter Sent 2004-11-04
Inactive: Approved for allowance (AFA) 2004-10-26
Letter Sent 2003-12-30
Letter Sent 2002-11-15
Request for Examination Requirements Determined Compliant 2002-10-04
All Requirements for Examination Determined Compliant 2002-10-04
Request for Examination Received 2002-10-04
Letter Sent 1999-12-22
Inactive: Single transfer 1999-11-25
Inactive: Cover page published 1999-08-13
Inactive: First IPC assigned 1999-07-09
Inactive: Courtesy letter - Evidence 1999-06-22
Inactive: Notice - National entry - No RFE 1999-06-18
Application Received - PCT 1999-06-15
Application Published (Open to Public Inspection) 1998-05-28

Abandonment History

There is no abandonment history.

Maintenance Fee

The last payment was received on 2005-08-24

Note : If the full payment has not been received on or before the date indicated, a further fee may be required which may be one of the following

  • the reinstatement fee;
  • the late payment fee; or
  • additional fee to reverse deemed expiry.

Please refer to the CIPO Patent Fees web page to see all current fee amounts.

Owners on Record

Note: Records showing the ownership history in alphabetical order.

Current Owners on Record
MARCH NETWORKS CORPORATION
Past Owners on Record
NAEL HIRZALLA
PAUL STREATCH
ROB MENARD
ROGER MACLEAN
Past Owners that do not appear in the "Owners on Record" listing will appear in other documentation within the application.
Documents

To view selected files, please enter reCAPTCHA code :



To view images, click a link in the Document Description column. To download the documents, select one or more checkboxes in the first column and then click the "Download Selected in PDF format (Zip Archive)" or the "Download Selected as Single PDF" button.

List of published and non-published patent-specific documents on the CPD .

If you have any difficulty accessing content, you can call the Client Service Centre at 1-866-997-1936 or send them an e-mail at CIPO Client Service Centre.


Document
Description 
Date
(yyyy-mm-dd) 
Number of pages   Size of Image (KB) 
Representative drawing 1999-08-09 1 7
Cover Page 1999-08-09 1 48
Abstract 1999-05-17 1 57
Description 1999-05-17 7 616
Claims 1999-05-17 3 148
Drawings 1999-05-17 5 115
Representative drawing 2004-10-22 1 8
Description 2004-11-23 7 347
Claims 2004-11-23 3 112
Cover Page 2005-10-28 1 40
Notice of National Entry 1999-06-18 1 194
Reminder of maintenance fee due 1999-07-21 1 114
Courtesy - Certificate of registration (related document(s)) 1999-12-22 1 115
Reminder - Request for Examination 2002-07-23 1 127
Acknowledgement of Request for Examination 2002-11-15 1 176
Commissioner's Notice - Application Found Allowable 2005-03-03 1 162
Correspondence 1999-05-17 2 100
PCT 1999-05-17 20 785
Correspondence 1999-06-22 1 30
Correspondence 2005-08-25 1 31
Fees 2005-08-24 1 35