FORM -2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
PROVISIONAL
Specification


(See Section 10 and rule 13)
ANALYZING VIDEO CONTENT

TATA CONSULTANCY SERVICES LTD.,
an Indian Company of Bombay House, 24, Sir Homi Mody Street, Mumbai 400 001
Maharashtra, India
THE FOLLOWING SPECIFICATION DESCRIBES THE INVENTION


Field of the Invention:
This invention relates to the field of analyzing video content.
Background of the Invention:
With increased availability and an exponential growth in the number of image and video applications, the issue of analyzing, automatically indexing and summarizing video content by retrieving highly representative information is of paramount importance and an active area of research. A shot in a video sequence is a contiguous sequence of one or more video frames recorded by a single camera. The nature of transitions or boundaries between shots is varied. Depending on the nature, shot boundaries may be classified as being a cut, a fade, a wipe or a dissolve.
A cut is an abrupt shot change that occurs in a single frame. A fade is a slow change in brightness usually resulting in or starting with a black frame. A dissolve occurs when the frames of the first shot get dimmer and the frames of the second get brighter, with frames within the transition showing one image superimposed on the other. A wipe occurs when pixels from the second shot replace those of the first shot in a regular pattern such as in a line from the left edge of the frames. Of course, other types of gradual transitions are possible.
Video shot boundary detection techniques are an active area of research in recent years and have to challenge the difficulty of finding shot boundaries in the presence of camera, object motion and illumination variations.
2

Several approaches have been reported in the literature for automatic shot
boundary detection. Of them, one class of algorithms exploit color intensity
variations, the second class of algorithms exploits classification based on
mathematical and statistical models; other methods exploit edge difference
and edge comparisons between successive frames. Most of the cut detection
schemes are threshold based. They identify a cut if the frame difference
between consecutive frames exceeds a certain threshold. Similarity between
frames is expressed by extracting features between frames. Various types of
features have been reported in literature. The features are based on:
Luminance/color - The average grayscale luminance is used as a feature but
it is susceptible to illumination changes.
Color Histogram - Because of its insensitivity to camera motion, this
technique is widely used.
Transform Coefficients- They can be used to describe texture which can be
used as a feature.
Edges- Edge features have been used to detect cuts as they are invariant to
illumination and motion.
The size of the region from which features are extracted plays a significant
role on the performance of any shot detection algorithm. If the ROI is large,
there is a tendency to miss transitions between similar shots. The spatial
features used in literature include the following:
Single frame pixel per picture e.g. luminance, edge strength.
Arbitrary shaped region- In order to extract discontinuous regions better,
arbitrary regions have been made the ROI for each frame to exploit
homogeneity.
Whole frame- They have the advantages to be resistant to motion but the
performance may be poor in detecting transition between shots.

The proposed shot boundary detection technique extracts block features from each frame of the video. Motion based features are extracted by taking the statistical moments over an accumulator. Accumulator represents motion histogram over the entire frame. A feature vector is generated using a sliding window over time. These features are trained using a Support Vector Machine (supervised learning) to classify the cut and normal scenes of the video.
An object of this invention is the detection of cuts (shot boundaries) of video sequences.
In particular, this invention envisages a novel way of estimating the motion of frames of input videos using the concept of motion histogram.
In particular, this invention envisages a novel way of shot boundary detection (cut) of a video using Support Vector Machine (SVM).
Further, this invention provides means for automatic detection of cuts from an input video sequence.
In particular, this invention discloses a non-threshold based technique for detection of cuts in an input sequence.
Summary of the Invention:
Browsing video databases has become an extremely difficult job with the ever increasing magnitude of video data. To facilitate the user's access to
4

this huge data, indexing, retrieval and summarization have become an active area of research. Temporal video segmentation is a fundamental step in that direction. The objective of shot boundary detection is to partition the video into meaningful, basic structural units called shots.
In this invention, a shot boundary detection technique is disclosed for cuts. The method extracts block feature based similarities from the frames of the input video. Statistical moments of second order are used to measure the total motion of the frames. Feature vectors are generated using a sliding window over time and are trained by a SVM to identify the cuts.
Brief Description of the Accompanying Drawings:
The invention will now be described with reference to the accompanying drawings, in which
Figure 1: Spiral Search for use in the method in accordance with this
invention
Figure 2: Accumulator for use in the method in accordance with this
invention
Detailed Description of Invention:
The invention envisaged uses both block based minimum features as well as statistical moment based motion histogram approach to extract features. Feature vector has been constructed using a sliding window over time. These features have been trained using Support Vector Machine (SVM). The SVM classifies the video frames as a cut or a normal scene.
5

The frames of the input video have been decomposed into rectangular blocks of sizeMxN. This was done because block based computation tends to reduce detection invariance while a large region tends to miss transitions between similar shots. This approach is invariant to small camera and object motion.
Each block of the current frame has been compared with the previous frame blocks by choosing a window around the corresponding previous frame block. For comparison of blocks, normalized SAD (NSAD) in R, G, and B planes have been used separately. The distance between two blocks in each of R, G and B plane is given by the following equation:
255 xMxN where P is either of R, G or B;(x,y) and (x'yf) denotes the co-ordinates of the
top left of the current and previous blocks respectively. distp is the error between the current block at and previous block at position (.*>'). To get the best fit block, a spiral search [Figure 1] has been made around the (x\y') position in the previous frame. The search window has been defined to be between (-M/2, M/2) along the row direction and between (-N/2, N/2) along
the column direction thereby giving (M+l) (N+l) values for"'^. The minimum error among all these distances was computed as

This range of spiral search may change depending on the fps of the input video.
6

Equation 1 gives the minimum error in two blocks of current and previous frames. The normalized total error in R, G and B planes for the entire frame was computed as:

Here i represents either of R, G or B.
Now we get a total of three errors for a current frame from previous frame in
each of R, G, and B plane. Along with the errors in the R, G and B planes,
the motion of the block also played an important role in determining the cuts
from the normal scenes. We have introduced a novel motion estimation
technique for the entire frame.
Corresponding to the best match, the block movement in both the x and y
directions have been measured for each block in the current frame. The x
and y directional movements have been calculated for each block. If the
increments are represented as Ax and Ay, then
Ax = x — x'
and Ay = y- y' where x' and y' are the best matched block position in
previous frame.
An accumulator [Figure 2] has been designed to capture the motion
histogram of a frame. Let A denote the set of integers{0,l,....M-l}and B
denote the set of integers{0,1....,N-1}. Accumulator f(i ,j) is a function
f :AxB → Z+ {o} where Z+ denotes the set of positive integers. For each
block, (Δx, Δy) is computed and the accumulator f(Δx, Δy) is updated by the
following equation.
f(Δx, Δy) = f(Δx, Δy) ÷ 1;
7

The function f{i,j) is the motion histogram of the whole frame. The index of the accumulator ranges from -M/2 to M/2 along row direction and -N/2 to N/2 along column direction.
Statistical moments provide an ideal feature to capture the amount of dispersion of blocks between frames. Dispersion of order (p, q) is given by:
These moments on motion histogram accumulator will give the amount of block dispersion in each frame.
Four normalized central moments are used as additional features to the three errors in R, G and B plane to prepare the feature vector. A sliding window over time has been constructed in order to prepare the
feature vectors. Corresponding to the current frame F', the
frames have been taken and each provides for 7 features
making a total of 35 features.
Having prepared the feature vector for cuts and normal frames of the video,
it is needed to classify the frames as positive (cuts) and negative (normal
frames).For classification, the well known concept of Support Vector
Machine (SVM) has been used.
The SVM, introduced by Vapnik is a powerful supervised learning algorithm
which is primarily a two class classifier. The optimization criterion of an
SVM is the width of the margin between the positive and the negative
8

examples. An SVM with a large margin yields a good generalization performance. The inputs to a SVM are n-dimensional vectors and the machine classifies the vectors by using a hyperplane. The SVM works in the following manner: Given a training dataset of the form:

Each c' indicates to which class the p-dimensional vector belongs to. Any hyperplane is a set of points x satisfying the equation w x-f-6=0; all training points should satisfy

The parameter b/ || w || determines the offset of the hyperplane from the origin in the direction of the normal vector w. w and b are to be chosen so as to maximize the margin. Since it has been proven mathematically that the
2
margin is , so finding the hyperplane which separates the data with
|| w ||
maximum margin leads to the following optimization problem:
2 II W II
Minimize 2 Subject to

Writing the classification rule in its dual form reveals that the maximum
margin hyperplane and therefore the classification task is only a function of
the support vectors which is nothing but the training data that lie on the
margin.
The dual of the SVM is as follows:
9


In order to handle non-separable data, equation (A) becomes

The optimization problem is reformulated as
Minimize 2
are the upper bounds on training
error and c is the regularization parameter. The dua] formulation is
Maximize
Subject t0
For non-linear SVM, the training vectors are mapped to some higher
dimensional data using a transformation function' in Eqn (3)
becomes
By using a suitable kernel function we do
not need to calculate For our work, we used Gaussian kernel of the form
In order to avoid overfitting, a four fold cross validation of training data was done. The training dataset was partitioned into four sub sets and one of them was tested iteratively with the SVM being trained with the remaining three subsets.
10

While considerable emphasis has been placed herein on the specific steps and elements of the preferred embodiment, it will be appreciated that many alterations can be made and that many modifications can be made in the preferred embodiment without departing from the principles of the invention. These and other changes in the preferred embodiment as well as other embodiments of the invention will be apparent to those skilled in the art from the disclosure herein, whereby it is to be distinctly understood that the foregoing descriptive matter is to be interpreted merely as illustrative of the invention and not as a limitation.
Dated this 29th day of August 2008.

APPLICANTS' PATENT ATTORNEY