\documentstyle[twocolumn,subfigure]{article}
\input{epsf}
\long\def\ignore#1{}
\pagestyle{empty}
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}
\makeatletter
\def\@normalsize{\@setsize\normalsize{10pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip 
\abovedisplayskip \abovedisplayshortskip \z@ 
plus3pt\belowdisplayshortskip 6pt plus3pt 
minus3pt\let\@listi\@listI}
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}
\def\section{\@startsection {section}{1}{\z@}{1.0ex plus 
1ex minus .2ex}{.2ex plus .2ex}{\large\bf}}
\def\subsection{\@startsection {subsection}{2}{\z@}{.2ex 
plus 1ex} {.2ex plus .2ex}{\subsize\bf}}
\makeatother

\begin{document}

\def\qvsize{.25\vsize}
\def\qhsize{.25\hsize}
\def\hvsize{.5\vsize}

\def\mmxsize{.5\textwidth}
\def\mmysize{.255\textheight}



\date{}
\title{\Large\bf Video Browsing Using Edges and Motion}
\author{\begin{tabular}[t]{c@{\extracolsep{8em}}c@{\extracolsep{8em}}c} 
Ramin Zabih & Justin Miller & Kevin Mai\\ \\
\multicolumn{3}{c}{Computer Science Department}\\
\multicolumn{3}{c}{Cornell University}\\
\multicolumn{3}{c}{Ithaca, NY, 14853}\\
\multicolumn{3}{c}{\tt rdz@cs.cornell.edu}
\end{tabular}}
\maketitle
\thispagestyle{empty}
\subsection*{\centering Abstract}
% Important: speed and compression tolerance
{\em Automatic video browsing requires algorithms for detecting a variety of
events, including production effects (e.g., scene breaks and captions) and
moving objects.  We present new methods that use edges and motion for
detecting production effects and for motion segmentation.  Production effects,
such as cuts, dissolves, wipes and captions, can be detected by
looking for new edges that are far from previous edges.  A global motion
computation is used to register consecutive images.  We have also developed a
method for motion segmentation, which does not require computing local optical
flow.  Our methods run at several frames per second on a Sparc workstation,
and also tolerate compression artifacts.
%end italics mode
}


\section{Introduction}

With modern compression techniques and the plummeting costs of secondary
storage, it is becoming feasible to have thousands of hours of digital image
sequences available on-line.  Several recent research projects have
investigated tools for querying such large image databases
\cite{QBIC-IEEE,HJW:journal}.  Automatic browsing of image sequences requires
algorithms for detecting a variety of events, such as production effects (such
as scene breaks and captions) and moving objects.  Browsers can then be
constructed to search for these events.

This is a fertile area for developing and applying computer vision 
algorithms.  Compression artifacts are a major challenge, since lossy 
compression is commonplace in such applications.  In this paper, we 
describe new methods for detecting production effects and moving objects.  
By using edges and motion we have designed solutions that withstand 
compression artifacts.

We begin by reviewing existing work on automatic video browsing, which has
focused on scene break detection and (to a lesser extent) motion.  In
section~\ref{sec:scene-breaks} we present our solutions for detecting scene
breaks, and in section~\ref{sec:data} we supply experimental evidence that our
methods perform well.  In section~\ref{sec:extensions} we extend these methods
to handle other production effects (such as captions and subtitles) and to
perform motion segmentation.  

\section{Related work}
\label{sec:related}

Existing work has focused on detecting scene breaks, although there has also
been some work on motion-based browsing.  The problem is also important for a
number of multimedia applications besides video browsing including compression
and automatic keyframing.  Motion-based compression algorithms like MPEG can
obtain higher compression rates without sacrificing quality when the locations
of scene breaks are known.  Knowledge about scene breaks can be used to look
for higher-level structures (such as a sequence of cuts between cameras), or
to ensure that keyframes come from different scenes.

\subsection{Scene break detection}

Scene breaks mark the transition from one sequence of consecutive images (or
scene) to another.  A cut is an instantaneous transition from one scene to the
next.  A fade is a gradual transition between a scene and a constant image
({\em fade out}) or between a constant image and a scene ({\em fade in}).
During a fade, images have their intensities multiplied by some value
$\alpha$.  During a fade in, $\alpha$ increases from 0 to 1, while during a
fade out $\alpha$ decreases from 1 to 0.  The speed with which $\alpha$
changes controls the fade rate.  A dissolve is a gradual transition from one
scene to another, in which the first scene fades out and the second scene
fades in.  Typically, fade out and fade in begin at the same time, and the
fade rate is constant.  Another common scene break is a wipe, in which a line
moves across the screen, with the new scene appearing behind the line.

Scene breaks are detected by computing a similarity measure between 
consecutive images.  The similarity measure is thresholded to detect scene 
breaks.  Existing work has relied directly on intensity data, using such 
techniques as image differencing and intensity histogramming.  Most 
approaches are based on intensity histograms, and concentrate on cuts 
\cite{Nagasaka:indexing,Otsuji:projection-detection} These methods have 
difficulty with ``busy'' scenes, in which intensities change substantially 
from frame to frame.  Such changes often result from camera or object 
motion.

Dissolves are more difficult to detect than cuts, especially if the scenes 
may involve motion.  False positives resulting from motion can be supressed 
by setting a sufficient threshold.  Cuts usually result in a dramatic 
change in image intensities, so they can still be detected much of the 
time.  However, a dissolve is a gradual change of all the intensities, and 
thus cannot be easily distinguished from motion.  A dissolve can even occur 
between two scenes which each contain motion.

Hampapur, Jain and Weymouth \cite{HJW:journal} use an explicit model of the 
video production process to detect a variety of scene breaks.  While their 
approach is intensity-based, it does not involve histogramming.  Instead, 
they compute a {chromatic image} from a pair of consecutive images.  Its 
value at each pixel is the change in intensity between the two images 
divided by the intensity in the later image.  Ideally, the chromatic image 
should be uniform and non-zero during a fade.

The difficulties caused by motion and by dissolves are well-known.  For
example, Hampapur, Jain and Weymouth note in their discussion of dissolves
that their measure ``is applicable if the change due to the editing dominates
the change due to motion''\cite[page 11]{HJW:journal}, and describe both
object and camera motion as causes of false positives for their method.
Another recent paper \cite{Zhang:partitioning} describes motion as a major
limitation of histogram-based methods.

Zhang, Kankanhalli and Smoliar \cite{Zhang:partitioning} have extended 
conventional histogram-based approaches to handle dissolves and to deal 
with certain camera motions.  They use a dual threshold on the change in 
the intensity histogram to detect dissolves.  In addition, they have a 
method for avoiding the false positives that result from certain classes of 
camera motion, such as pans and zooms.  They propose to detect such camera 
motion and suppress the output of their scene-break measure during camera 
motion.

Their method does not handle false positives that arise from object motion, or
from more complex camera motions.  Nor does their method handle false
negatives, which would occur in dissolves between scenes involving motion.  In
section~\ref{sec:data} we will provide an empirical comparison of our method
with histogram-based techniques and with chromatic scaling.

\subsection{Motion-based browsing}

A number of groups are currently investigating the use of motion for automatic
browsing of videos.  For example, researchers are exploring motion-based
extensions to QBIC \cite{QBIC-IEEE} and to Photobook \cite{Pentland:advanced}.
However, little work on motion-based browsing of videos has been published.

There has, of course, been a great deal of work on related problems, such 
as computing motion or motion segmentation.  Most work on motion 
segmentation involves some kind of local computation of motion (often 
called optical flow).  For example, Adiv \cite{Adiv:motionandstructure} 
partitions the flow field into connected segments whose motion is 
consistent with a planar surface moving rigidly.  Another approach 
\cite{Adelson:layered,Ayer:layered-ICCV} focuses on layered representations 
of multiple motions, which computes optical flow and performs a 
segmentation into regions.

% Section 2, PAMI

\section{An Edge-Based Approach}
\label{sec:scene-breaks}

During a cut or a dissolve, new intensity edges appear far from the 
locations of old edges.  In addition, old edges disappear far from the 
location of new edges.  These simple observations allow us to detect and 
classify scene breaks.  We define an edge pixel that appears far from an 
existing edge pixel as an {\em incoming} edge pixel, and an edge pixel that 
disappears far from an existing edge pixel as an {\em outgoing} edge pixel.  
By counting the incoming and outgoing edge pixels, we can detect and 
classify cuts, fades and dissolves.  By analyzing the spatial distribution 
of incoming and outgoing edge pixels, we can detect and classify wipes.

Our method can be easily extended in order to handle motion.  We can use any
registration technique to compute a global motion between frames.  We can then
apply this global motion to align the frames before detecting incoming or
outgoing edge pixels.

The algorithm we propose takes as input two consecutive images $I$ and $I'$.
We first perform an edge detection step, resulting in two binary images $E$
and $E'$.  Let $\rho_{in}$ denote the fraction of edge pixels in $E'$ which
are more than a fixed distance $r$ from the closest edge pixel in $E$.
$\rho_{in}$ measures the proportion of incoming edge pixels.  It should assume
a high value during a fade in, or a cut, or at the end of a
dissolve.\footnote{Due to the quantization of intensities, new edges will
generally not show up until the end of the dissolve.}

Similarly, let $\rho_{out}$ be the fraction of edge pixels in $E$ which are
farther than $r$ away from the closest edge pixel in $E'$.
$\rho_{out}$ measures the proportion of outgoing edge pixels.  It should assume
a high value during a fade out, or a cut, or at the beginning of a dissolve.

Our basic measure of dissimilarity is
\begin{equation}
\rho = \max(\rho_{in},\rho_{out}).
\end{equation}
This represents the fraction of changed edges; this fraction of the edges have
entered or exited.  Scene breaks can be detected by looking for peaks in
$\rho$, which we term the {\em edge change fraction}.
In our experiments, we have used a Canny-style edge detector.  We smooth the
image with a Gaussian of width $\sigma$, threshold the gradient magnitude at a
value of $\tau$, and perform non-maximum suppression.  

\subsection{Motion compensation}
\label{sec:motion}

Our algorithm handles small motions through the use of dilated edges.  
Edges which move no farther than the dilation radius $r$ will not result in 
changing pixels (i.e., incoming or outgoing edge pixels).  Even if every 
edge moves by $r$ pixels, there will still be no changing pixels.  A slow 
camera pan, for example, will be handled in this manner.  Other examples 
that give rise to small motions include rotations, zooms and non-rigid 
motions.  The table tennis sequence, which is a standard MPEG benchmark, 
includes zooms and non-rigid motions; as discussed in \cite{Zabih:MM95}, 
our approach handles this sequence easily.

A single larger motion requires a motion compensation step before computing 
the edge change fraction.  In our experience, it has been sufficient to 
restrict the motion to be purely translational.  While it is easy to handle 
affine or projective motions, they incur significant additional overhead, 
and do not seem to result in better performance.  

We have explored two algorithms for computing motion, both of which have 
given satisfactory results.  The algorithms are based on correlation, but 
also tolerate the presence of multiple motions.  In our initial experiments 
we used the Hausdorff distance \cite{Huttenlocher:hausdorff-PAMI}, a method 
described in section~\ref{sec:HD} that operates on edge images.  More 
recently, we have used correlation based on non-parametric local 
transforms, an approach described in \cite{Zabih:ECCV}.

Note that the simple motion compensation scheme described does not handle
multiple, distinctive motions.  For example, if the camera pans to follow a
fast-moving object, motion compensation will stabilize either the object or
the background.  Edges undergoing the secondary motion will appear to move; if
the relative motion is larger than $r$, this will result in incoming and
outgoing pixels.  To handle this case requires motion segmentation, which we
will discuss in section~\ref{sec:motion-extension}.

\subsection{Peak detection and classification}
\label{sec:classify}

There are thus 3 basic steps to our algorithm: motion compensate $I$and 
$I'$; perform edge detection; and compute $\rho_{in}$ and $\rho_{out}$ (and 
thus, $\rho$).  Once this is done, scene breaks can be detected by looking 
for peaks in $\rho$.

[{\bf JMiller}: This section has to be re-written in accordance with 
current practice!] We have designed a simple thresholding scheme for peak 
detection.  We use an {\em event threshold} and an {\em event horizon}.  A 
frame where $\rho$ exceeds the event threshold may be a scene break.  To 
localize scene breaks that occur over multiple frames, we restrict scene 
breaks to occur only when $\rho$ is a local maximum within a fixed window 
of consecutive frames.  The width of this window is the event horizon.

Once a peak has been detected, the next problem is to classify it as a cut,
dissolve, fade or wipe.  Cuts are easy to distinguish cuts from the other
scene breaks, because a cut is the only scene break that occurs entirely
between two consecutive frames.  As a consequence, a cut will lead to a single
isolated frame with a high value of $\rho$, while the other scene breaks will
lead to an interval where $\rho$'s value is elevated.  This allows us to
classify cuts.

Fades and dissolves can be distinguished from each other by looking at the
relative values of $\rho_{in}$ and $\rho_{out}$ in a local region.  During a
fade in, $\rho_{in}$ will be much higher than $\rho_{out}$, since there will
be many incoming edge pixels and few outgoing edge pixels.  Similarly, at a
fade out, $\rho_{out}$ will be higher than $\rho_{in}$, since there will be
many outgoing edge pixels, but few incoming edge pixels.  A dissolve, on the
other hand, consists of an overlapping fade in and fade out.  During the first
half of the dissolve, $\rho_{in}$ will be greater, but during the second half
$\rho_{out}$ will be greater.

Wipes are distinguished from dissolves and fades by looking at the spatial
distribution of incoming and outgoing edge pixels.  During a wipe, each frame
will have a portion of the old scene and a portion of the new scene.  Between
adjacent frames, a single strip of the image will change from the old scene to
the new scene.  For a horizontal wipe there is a vertical strip that passes
either left-right or right-left, depending on the direction of the wipe.
Since the between-scene transition occurs in this strip, the number of edge
pixels that either enter or exit should be higher inside the strip and lower
in the other areas of the image.  

When computing the edge change fraction, the location of the changing edge
pixels can be recorded and their spatial distribution analyzed.  There are
many ways to analyze the spatial distribution of changing pixels, but we have
identified a simple scheme which has yielded good results.  We calculate the
percentage of such pixels in the top half and the left half of the images, and
use this to classify vertical and horizontal wipes.  For a left-to-right
horizontal wipe, the majority of changing pixels will occur in the left half
of the images during the first half of the wipe, then in the right half of the
images during the rest of the wipe.  Likewise, for a top-to-bottom vertical
wipe, the majority of changing pixels will concentrate in the top half, and
then in the bottom half.  The other two cases (right-to-left and bottom-to-top
wipes) can be handled similarly.

Our wipe detection method is aided by the ability of our motion computation
follow the predominant motion.  This is particularly important during a wipe,
since there can be two rather different motions on the image at the same time.
Another aid in discriminating wipes from other scene breaks is that there is
no pattern in the values of $\rho_{in}$ and $\rho_{out}$ as there was with
dissolves and fades.  Also the relative differences between $\rho_{in}$ and
$\rho_{out}$ will be small, since the changing pixels only occurs a limited
strip in the image.

\subsection{The Hausdorff distance}
\label{sec:HD}

Our measure is related to the Hausdorff distance, which has been used to
search for the best match for a model in an image
\cite{Huttenlocher:hausdorff-PAMI} The Hausdorff distance, which originates in
point set topology, is a metric for comparing point sets.  The distance from
the point set $A$ to the point set $B$ is defined as
\begin{equation}
h(A,B) \qquad = \qquad \max_{a\in A} \min_{b\in B} \| a - b \|.
\label{eq:HD-orig}
\end{equation}
If $h(E',E) \leq r$ then every edge pixel in $E'$ is within $r$ of the closest
edge pixel in $E$, there are no incoming edge pixels, and so $\rho_{in} = 0$.
Similarly, if $h(E,E') \leq r$ then there are no outgoing edge pixels and
$\rho_{out} = 0$. 

Most applications of the Hausdorff distance use a generalization called the
partial Hausdorff distance, which is
\begin{equation}
h_K(A,B) \qquad = \qquad K^{th}_{a\in A} \min_{b\in B} \| a - b \|.
\end{equation}
This selects the $K^{th}$ ranked distance from a point in $A$ to its closest
point in $B$.  If we select the largest such distance, we have the original
Hausdorff distance defined in equation~\ref{eq:HD-orig}.  

Applications which use the partial Hausdorff distance for matching can provide
a fixed fraction $f = K/|A|$, which is $1 - \rho$.  This specifies what
fraction of the points in $A$ should be close to their nearest neighbor in $B$
at the best match.  Alternatively, a fixed distance can be supplied, and the
fraction of points in $A$ within this distance of their nearest neighbor in
$B$ can be minimized.  

\subsection{Algorithm parameters}

Because our algorithm is based on edges, it relies on the performance of 
the edge detector.  Clearly our solution will not work on image sequences 
with minimal contrast, or in circumstances in which edge detection fails.

Our algorithm has several parameters that control its performance:
\begin{itemize}
\item the edge detector's smoothing width $\sigma$ and threshold $\tau$,
\item the expansion distance $r$,
\end{itemize}
We have gotten good performance from a single set of parameters across
all the image sequences we have tested.  These parameters are $\sigma = 1.2$
and $\tau = 24$, for the edge detector, and $r = 6$.  Except where otherwise
noted, these were the parameters used to generate the data shown in this paper.

\subsection{Compression tolerance}

Most video will undergo some form of compression during its existence, and
most compression methods are lossy.  It is therefore important that our
algorithm degrade gracefully in the presence of compression-induced artifacts.
While edge detection is affected by lossy compression, especially at high
compression ratios, we do not rely on the precise location of edge pixels.  We
only wish to know if another edge pixel is with $r$ of an edge.  As a
consequence, the precise location of edge pixels can be changed by image
compression without seriously degrading our algorithm's performance.  The
experimental evidence we present in the next section comes from images that
were highly compressed with the lossy MPEG compression scheme.

[JMiller: do we have new data for this??]
To demonstrate the compression tolerance of our approach, we have taken an
uncompressed image sequence, added a few scene breaks, and compressed it with
a variety of different compression ratios.  Although MPEG is the dominant
compression scheme for video sequences, we have chosen to use JPEG compression
for this benchmark.  There are a number of reasons for this, but they center
on the fact that the behavior of an MPEG encoder is not specified by the MPEG
standard.  The MPEG standard defines what MPEG-compressed streams look like,
but leaves compressors considerable latitude in how they produce them.  As a
result, the quality of MPEG-compressed video depends greatly upon which
encoder is used.

There are a large number of MPEG coders available, with very different schemes
for computing motion vectors.  In addition, an individual MPEG-encoder will
produce different artifacts depending on the pattern of I-, P- and B-frames it
uses during encoding.  We have used JPEG compression to benchmark the
compression tolerance of our algorithms because it introduces similar
artifacts to MPEG, but is more standardized.  (Note that this is only for the
data shown in figure~\ref{fig:tt-jpeg} --- the data shown in section~\ref{sec:data}
came from MPEG compressed images.)

Figure~\ref{fig:tt-jpeg} shows the results from the table tennis sequence when
JPEG-compressed to .18 bits per pixel (with a quality factor of 3).  Our
algorithm performed correctly even though the compression artifacts were so
enormous as to make the sequence almost unviewable.  Figure~\ref{fig:tt-jpeg}
also shows frame \#20 at this compression rate.

\begin{figure}
\centerline{\epsfxsize=\mmxsize
\epsfbox{figures/tt-jpeg-03.eps}}
\vspace{.2in}
\centerline{\epsfxsize=\mmxsize
\epsfbox{figures/tt-jpeg-03-imgs.eps}}
\caption{Table tennis sequence results at .18 bits/pixel
\protect\label{fig:tt-jpeg}}
\end{figure}

% Section 3, MM95
\section{Experimental Results}
\label{sec:data}

We have tested our algorithm on a number of image sequences, containing
various scene breaks.  To provide a comparison, we have also implemented two
other intensity-based measures used to detect scene breaks.  The first measure
is the intensity histogram difference, which is used with slight variations in
most work on scene breaks
\cite{Nagasaka:indexing,Otsuji:projection-detection,Zhang:partitioning}.  The
second measure is the chromatic scaling method of Hampapur, Jain and Weymouth
\cite{HJW:journal}, a recent method for classifying scene breaks.  We
implemented a histogramming variant used by Zhang, Kankanhalli and Smoliar.
For each of the 3 color channels we used the 2 most significant bits, for a
total of $N = 64$ bins in the histogram; histograms are compared using the
$L_1$ distance.

\subsection{Sources of data}
\label{sec:data-source}

The image sequences used for testing are MPEG movies.  We obtained a number of
MPEG encoded movies from {\tt http:://www.acm.uiuc.edu/rml/Mpeg/}
which include segments from a number of different sources including music
videos, television advertisements, documentaries, and NASA recordings.  We
selected a number of MPEG movies which contained scene breaks.

In addition, we created some additional MPEG movies.  Because the MPEG movies
we obtained from the network did not contain enough scene breaks to generate
significant data, we spliced together scenes from existing MPEG movies and
inserted a variety of scene breaks.  These spliced movies have several
advantages: they show many different scene breaks at known locations, but the
video itself was shot and compressed by third parties.  Finally, we created
one movie, called {\tt andy}, from video which we shot.  We inserted several
scene breaks during the editing process, and then compressed it using the
Berkeley MPEG encoder.

The data we used is highly compressed.  The following table
summarizes the compression parameters of several of the image sequences we used.
\begin{center}
\begin{tabular}{|l||r|r|r|r|}
\hline
Sequence & Bits per pixel &
Dimensions \\
\hline
{\tt clapton}&		0.91&	$160\times 120$\\
{\tt spacewalk}&	0.82&	$160\times 120$ \\
{\tt andy}&		0.35&	$160\times 112$ \\
\hline
\end{tabular}
\end{center}
All these sequences are color, so the compression ratios (from 24-bit color
images) range from 26:1 to 69:1.  These high compression ratios probably
result from using videos available on the World-Wide Web, which places a
premium on compression to minimize bandwidth and storage costs.  However, this
makes our data set representative of the kind of video that is widely
available today.

All of the test sequences shown use the parameter values mentioned above.  The
chromatic scaling method and the histogram difference, which we show for
comparison, involve no parameters.  All of these methods are intended to
produce distinctive peaks at cuts and dissolves.

\subsection{Some comparative results on difficult sequences}

The image sequences we have collected fall into three classes.  Several image
sequences had easy scene breaks, which could be detected by all the methods we
tried.  For example, there may only be cuts, or there may be minimal motion.
Another class of image sequences caused errors for conventional
intensity-based methods, but were handled correctly by our feature-based
method.  Examples include sequences with motion, and especially ones with both
motion and dissolves.  Finally, certain image sequences yielded incorrect
answers, no matter what method we used.  Examples include commercials with
very rapid changes in lighting and with fast-moving objects passing right in
front of the camera.

In our discussion we will concentrate on sequences where some algorithm had
difficulty detecting the scene breaks.  On the 50 MPEG movies we examined, we
did not find an example where our method failed but where intensity-based
methods worked.  Two example sequences where we had better performance are
{\tt clapton} and {\tt andy}.  The performance of various algorithms on these
sequences are shown in figure~\ref{fig:hard-compare}.

\ignore{
\begin{figure}
  \begin{center}
    {\setlength{\tabcolsep}{1.5em}
    \begin{tabular}{cc}
      \subfigure%
      [Edge change fraction ({\tt clapton})]%
      {\epsfysize=\mmysize
       \epsfbox{figures/clapton.eps}\label{fig:clapton-ecf}} &
      \subfigure%
      [Edge change fraction ({\tt andy})]%
      {\epsfysize=\mmysize
       \epsfbox{figures/newandy-ecf.eps}\label{fig:andy-ecf}} \\
%
      \subfigure%
      [Intensity histogram difference ({\tt clapton})]%
      {\epsfysize=\mmysize
       \epsfbox{figures/clapton-smo.eps}\label{fig:clapton-smo}} &
      \subfigure%
      [Intensity histogram difference ({\tt andy})]%
      {\epsfysize=\mmysize
       \epsfbox{figures/newandy-smo.eps}\label{fig:andy-smo}}\\
%
      \subfigure%
      [Chromatic scaling feature ({\tt clapton})]%
      {\epsfysize=\mmysize
       \epsfbox{figures/clapton-hjw.eps}\label{fig:clapton-hjw}} & 
      \subfigure%
      [Chromatic scaling feature ({\tt andy})]%
      {\epsfysize=\mmysize
       \epsfbox{figures/newandy-hjw.eps}\label{fig:andy-hjw}}\\
    \end{tabular}}
  \end{center}
  \caption{Results from the {\tt clapton} (left) and
 {\tt  andy} (right) sequences
 \label{fig:hard-compare}}
\end{figure}
}

\subsubsection{The Clapton sequence}

\ignore{
\begin{figure}
\centerline{
\epsfysize=\qvsize\epsfbox{figures/clapton0042.eps}
\goodgap
\epsfysize=\qvsize\epsfbox{figures/clapton0126.eps}}
\caption{Images from {\tt clapton} sequence detected as dissolves by our method
\label{fig:clapton-imgs}}
\end{figure}
}

One MPEG video that we obtained is part of an Eric Clapton music video.  It is
an interesting sequence because it contains two dissolves, as well as a moving
object (the singer).  It has been used to benchmark other algorithms (e.g.,
\cite{HJW:journal}).  Figure~\ref{fig:hard-compare} shows the performance
of several measures on this sequence.  Our edge change fraction detects and
classifies both dissolves correctly.  The image from each dissolve with the
highest value of $\rho$ is shown in figure~\ref{fig:clapton-imgs} (these are
the images that are at the center of the two dissolves according to our
detection method described in section~\ref{sec:classify}).

The intensity histogram difference, shown in figure~\ref{fig:clapton-smo}, is
a noisier measure on this sequence.  It does show a rise during the first
dissolve, and it is possible that the dual threshold scheme
of~\cite{Zhang:partitioning} would detect this (depending on the exact
thresholds used).  However, the second dissolve appears to be
indistinguishable from the noise.  Their method for handling motion would not
help here, since the problem is a false negative rather than a false positive.

The chromatic scaling feature of \cite{HJW:journal} is shown in
figure~\ref{fig:clapton-hjw}.  As the authors state, their method has
difficulty with dissolves involving motion.

\subsection{Results on our data set}

Our algorithm has been tested on an initial dataset of 50 MPEGs obtained from
the website mentioned in section~\ref{sec:data-source}.  These MPEGS were
decoded and stored as a sequences of gray-level frames.  There are 7788 frames
with a total of 118 cuts, 8 dissolves, and 3 fades.  Our current
classification algorithm correctly identifies 115 of 118 cuts, all dissolves
and all fades.  The algorithm currently identifies 17 false positives,
including 14 cuts and 3 fades.  The falsely detected fades are all cases where
the video becomes very dim and no edges are generated using a constant
threshold.  Since our current collection of MPEGs does not include any wipes,
we are currently developing a test set featuring special effects that we
insert ourselves.

\subsection{Performance}

Our initial implementation of our algorithm is optimized for simplicity rather
than for speed.  However, its performance is still reasonable.  Most of the
processing time comes from the global motion computation.  We have implemented
our algorithm on a Sparc workstation with a single 50-MHz processor, and with
4 50-MHz processors.  Because it is so easy to perform the motion compensation
in parallel, we have obtained near linear speedups.

The table below shows our implementation's performance with motion compensation
disabled, when running on the table tennis sequence.
\begin{center}
\begin{tabular}{|l||r|r|r|r|}
\hline
Image dimensions & 1 processor & 4 processors \\
\hline
$88\times 60$ & 11.03 Hz & 44.13 Hz \\
$176\times 120$ & 2.91 Hz & 11.63 Hz \\
$352\times 240$ & .62 Hz & 2.48 Hz \\
\hline
\end{tabular}
\end{center}
The next table shows the performance when using a simple Hausdorff-distance
based motion compensation scheme.  The running time is linear in the number of
disparities considered.  Data is shown for a range of disparities which has
been adequate for images of these sizes.
\begin{center}
\begin{tabular}{|l||r|r|r|r|}
\hline
Image dimensions & 1 processor & 4 processors \\
\hline
$88\times 60$ &  9.14 Hz & 36.57 Hz \\
$176\times 120$ & 1.49 Hz & 5.95 Hz \\
$352\times 240$ & .15 Hz & .6 Hz \\
\hline
\end{tabular}
\end{center}
The performance on our corpus of MPEG movies was typically around 2 frames per
second on a single processor.

% Subsample in disparity space?

Since the methods we use are fundamentally non-linear, it seems unlikely that
we will be able to operate directly on compressed data streams without
decompressing.  However, our scheme is reasonably fast, and can be optimized
further.  Our method also appears to give good results on reduced resolution
imagery, as shown in figure~\ref{fig:tt-sub}.  Finally, much of the overhead
of MPEG decompression is due to dithering.  Since our approach only uses
intensity information, this phase of MPEG decompression can be bypassed.

\subsection{Limitations}

In our experience, our algorithm's failures involve false negatives, and
result from the edge detection method not producing any edges.  The current
edge detector we use is fairly unsophisticated, so it may be possible to
address this problem.


\section{Extensions}
\label{sec:extensions}

We have also addressed two problems in video browsing beyond scene break
detection.  First, incoming and outgoing pixels can be used to identify other
production effects, such as textual overlays.  Second, our motion estimation
methods can be extended to perform motion segmentation without requiring
computing local optical flow.  

\subsection{Production effects}

We have extended our work on scene break detection to handle other production
effects involving overlays.  Many broadcast videos also provide some kind of
textual overlay.  For example, news broadcasts often begin a story by
overlaying the location of the reporter.  Similarly, a number of movies and
television shows overlay the opening credits on top of a scene.

These textual overlays contain significantly more information than scene
breaks, but they share some similarities.  Textual overlays can suddenly
appear and disappear (like a cut), or gradually fade in and fade out (like a
dissolve).  The pixels in the textual overlay should show up as incoming
pixels when they appear, and as outgoing pixels when they disappear.

Examples are shown in figure~\ref{fig:waterfall}.  In this sequence, two title
captions are overlayed on a ``busy'' sequence of a waterfall.  The first
caption is present from the start of the sequence, and the disappears.  The
second caption appears later.  In each case the caption appears
instantaneously (in other words, like a cut rather than like a dissolve).
There are significant edges in the background, which causes some degradation
in the output.  However, the captions clearly show up in the incoming edges.

\begin{figure}
\centerline{\epsfxsize=\mmxsize
\epsfbox{CVPR/water0034.pbm.eps}}
\vspace{.2in}
\centerline{\epsfxsize=\mmxsize
\epsfbox{CVPR/water0079.pbm.eps}}
\caption{Examples of caption localization\protect\label{fig:waterfall}}
\end{figure}

\subsection{Motion segmentation}
\label{sec:motion-extension}

We have developed a simple scheme for motion segmentation that does not
require estimating local optical flow.  It is based on the motion compensation
scheme described in section~\ref{sec:motion}, which performs a single estimate
of global image motion.  The advantage of our approach is that global image
motion can be estimated much more efficiently than local motion.
% Justin data goes here
We address two related problems: first, computing the secondary motion; and
secondly, segmenting the image into pixels undergoing different motions.
As an example, we will analyze a sequence where a camera pans to track a
fast-moving ice skater.

\subsubsection{Computing the secondary motion}

Correlation-based methods for computing motion compute the shift
(displacement) that makes the two images most similar.  The similarity of the
two images is a scalar function of the displacement; this similarity forms an
{\em error surface}.  The motion estimate is the displacement with the highest
peak in the error surface.\footnote{For ease of viewing, we have displayed the
similarity between the images.  But we will use the ``error surface''
terminology, since it is standard.}  Figure~\ref{fig:error-surfaces-1} shows
the error surfaces for several motion algorithms, for a scene with only one
motion.  Besides the standard sum of squared differences ($L_2$) error
measure, we also show the results from using non-parametric transforms
\cite{Zabih:ECCV} to compute motion.  Two algorithms are shown, namely the
census transform and the rank transform.  (In our experience, the census
transform tends to give better results than the rank transform.)

\ignore{
\begin{figure}
\begin{center}
  \subfigure[$L_2$ correlation]{%
 {\epsfxsize=\thsize\epsfbox{CVPR/k01-ssd.eps}}\label{fig:SSD-1peak}}%
\goodgap
  \subfigure[Census transform correlation]{%
 {\epsfxsize=\thsize\epsfbox{CVPR/k01-cen.eps}}\label{fig:census-1peak}}% 
\goodgap
  \subfigure[Rank transform correlation]{%
 {\epsfxsize=\thsize\epsfbox{CVPR/k01-rank.eps}}\label{fig:rank-1peak}}%
\end{center}
\caption{Error surfaces for motion algorithms, for a scene with one motion
\label{fig:error-surfaces-1}}
\end{figure}
}

It is well known that multiple motions cause difficulties.
Figure~\ref{fig:error-surfaces-2} shows the error surface for a sequence with
two distinct motions.  Note that the standard ($L_2$) correlation method
yields an error surface which does not show the presence of the second motion.
The non-parametric transforms, on the other hand, show the second motion
clearly as a second bump.

\ignore{
\begin{figure}
\begin{center}
  \subfigure[$L_2$ correlation]{%
 {\epsfxsize=\thsize\epsfbox{CVPR/k02-ssd.eps}}\label{fig:SSD-2peak}}%
\goodgap
  \subfigure[Census transform correlation]{%
 {\epsfxsize=\thsize\epsfbox{CVPR/k02-cen.eps}}\label{fig:census-2peak}}% 
\goodgap
  \subfigure[Rank transform correlation]{%
 {\epsfxsize=\thsize\epsfbox{CVPR/k02-rank.eps}}\label{fig:rank-2peak}}%
\end{center}
\caption{Error surfaces for motion algorithms, for a scene with two motions
\label{fig:error-surfaces-2}}
\end{figure}
}

We observed that in sequences with two motions there was always a clear
secondary peak in the error surface.  This suggested a simple method for
computing the second motion, namely finding the second highest isolated peak.
Note that such dual-peak detecting methods have been used with local motion
estimation before, to compute discontinuities
\cite{Black:constraints,Spoerri:detection} and to segment objects
\cite{Woodfill:PhD}.  Results from this approach are shown in
figure~\ref{fig:kerrigan-motions}.  The $x$ displacements are displaced for
the primary (shown as a line) and secondary (shown with asterixes) motions.
Note that around frame 60 the primary motion and the secondary motion switch.
This occurs because the skater is moving towards the camera, and becomes
larger than the background.

\ignore{
\begin{figure}
\centerline{{\epsfysize=\hvsize\epsfbox{Proposal/kerr-x.eps}}}
\caption{Primary and secondary motions in ice skater sequence.
\label{fig:kerrigan-motions}}
\end{figure}
}

\subsubsection{Segmenting the image}

Once the primary and secondary motion have been computed, we next attempt to
classify the individual pixels.  Our solution to this problem involves the
individual pixel error scores when the images are shifted by the primary
motion, and when they are shifted by the secondary motion.
Figure~\ref{fig:kerrigan-scores} shows the error scores for one pair from the
ice skater sequence.  Smaller error scores as shown as lighter, and larger
error scores as darker.

\ignore{
\begin{figure}
\centerline{
   {\epsfysize=\thsize\epsfbox{CVPR/ker-firstm.pgm.g.eps}}\goodgap
   {\epsfysize=\thsize\epsfbox{CVPR/ker-secondm.pgm.g.eps}}
}
\caption{Census error scores at primary displacement (left) and
census error scores at secondary displacement (right).\label{fig:kerrigan-scores}}
\end{figure}
}

We can now classify pixels based on their error scores at the primary and
secondary displacements.  Indistinct pixels (for example, those from areas
with low texture) will have similar error scores at both displacements.
Pixels with small errors at the primary displacement but large errors at the
secondary displacement will be classified as undergoing the primary
displacement.  Similarly, pixels in the opposite situation will be classified
as undergoing the secondary displacement.

The results of this approach can be improved by first box-filtering the error
scores.  Figure~\ref{fig:kerrigan-mask} shows some results on the ice skater
sequence.  Pixels determined to be undergoing the primary motion are displayed
at right, while other pixels are shown in black.  Note the two small black
patches on the skater's torso; these are regions with minimal texture.  

\ignore{
\begin{figure}
\centerline{
   {\epsfysize=\thsize\epsfbox{Proposal/frame74.eps}}\goodgap
   {\epsfysize=\thsize\epsfbox{CVPR/ker-maskedS.pgm.eps}}
}
\caption{Original image, and pixels segmented as undergoing primary motion.
\label{fig:kerrigan-mask}}
\end{figure}
}

\section*{Conclusions}

We have shown how by using edges and motion it is possible to detect scene
breaks, find captions, and perform motion segmentation.  There are a number of
obvious extensions to this work.  For example, it is possible that the output
of our caption detector can be piped into an OCR system.  This would provide
an automatic source of textual information about video without relying on
manual annotation or speech recognition.

\subsection*{Acknowledgements} 
Justin Miller is supported by a grant from the GTE Research Foundation.


\bibliographystyle{plain}
\bibliography{ALL}

\end{document}
