\newcommand{\minus}{\mbox{\rm -}}
\newcommand{\plus} {\mbox{\rm +}}
\newcommand{\mod} {\mbox{ mod }}
\newcommand{\OA}{{\sf A}}
\newcommand{\OB}{{\sf B}}
\newcommand{\OC}{{\sf C}}
\newcommand{\OD}{{\sf D}}
\newcommand{\OI}{{\sf I}}
\newcommand{\OO}{{\sf O}}
\newcommand{\OR}{{\sf R}}
\newcommand{\OS}{{\sf S}}
\newcommand{\OT}{{\sf T}}
\newcommand{\OTau}{\tau }

\newcommand{\MA}{{\bf A}}
\newcommand{\MB}{{\bf B}}
\newcommand{\MC}{{\bf C}}
\newcommand{\MD}{{\bf D}}
\newcommand{\MO}{{\bf O}}
\newcommand{\MF}{{\bf F}}
\newcommand{\MI}{{\bf I}}
\newcommand{\MK}{{\bf K}}
\newcommand{\MJ}{{\bf J}}
\newcommand{\MR}{{\bf R}}
\newcommand{\MS}{{\bf S}}
\newcommand{\MT}{{\bf T}}
\newcommand{\MW}{{\bf W}}
\newcommand{\Msigma}{{\bf \Sigma}}

\newcommand{\VO}{{\bf 0}}
\newcommand{\Va}{{\bf a}}
\newcommand{\Vb}{{\bf b}}
\newcommand{\Vc}{{\bf c}}
\newcommand{\Vd}{{\bf d}}
\newcommand{\Ve}{{\bf e}}
\newcommand{\Vf}{{\bf f}}
\newcommand{\Vg}{{\bf g}}
\newcommand{\Vi}{{\bf i}}
\newcommand{\Vl}{{\bf l}}
\newcommand{\VF}{{\bf F}}
\newcommand{\Vn}{{\bf n}}
\newcommand{\Vp}{{\bf p}}
\newcommand{\Vq}{{\bf q}}
\newcommand{\Vr}{{\bf r}}
\newcommand{\Vs}{{\bf s}}
\newcommand{\Vt}{{\bf t}}
\newcommand{\Vtau}{{\bf \tau}}
\newcommand{\VV}{{\bf V}}
\newcommand{\Vx}{{\bf x}}
\newcommand{\Vy}{{\bf y}}
\newcommand{\Vz}{{\bf z}}
\newcommand{\VPhi}{{\bf \Phi}}
\newcommand{\sign}{{\rm sign}}

\newcommand{\dx}{{\alpha}}
\newcommand{\dy}{{\beta}}
\newcommand{\dI}{{\gamma}}
\newcommand{\dw}{{\delta}}
\newcommand{\dt}{{\tau}}
\newcommand{\ds}{{\sigma}}
\newcommand{\Vdx}{{\vec{\alpha}}}
\newcommand{\Vdy}{{\vec{\beta}}}
\newcommand{\VdI}{{\vec{\gamma}}}
\newcommand{\Vdt}{{\vec{\tau}}}
\newcommand{\Vds}{{\vec{\sigma}}}
\newcommand{\Vw}{{\vec{\delta}}}

\newtheorem{theorem}{Theorem}

\author[M. Bichsel]{M. Bichsel \\
University of Zurich\\
Department of Computer Science\\ MultiMedia Laboratory\\ 
Winterthurerstrasse 190\\ CH-8057 Zurich, Switzerland} 
\chapter[Face and Gesture Recognition in Real and Virtual Worlds]{Seeing Environments:
Face and Gesture Recognition in Real and Virtual Worlds}
%\setcounter{page}{3}
%\setcounter{equation}{7}

\begin{abstract}
This paper presents a frame-work for creating seeing environments
that react to conscious and unconscious human behavior by 
processing video sequences. Starting with a discussion of motion
detection techniques it presents methods for recognizing human faces
and interpreting human actions in general office or household
environments.
\end{abstract}



\section{Introduction}
Today, man-made equipment is basically blind and deaf. The user has to
interact with the technical world by physical contact: he must press
buttons and switches, type on a terminal or move a mouse. Interaction
with virtual worlds is similarly encumbered: the user must wear data
gloves and VR-helmets. One of the few exceptions is the ALIVE space by
Maes et al. \cite{G-maes96} or the system by Maggioni \cite{G-maggioni95}. 
Communication between people, on the other hand, is mostly contactless
and is based on speech and gestures where gestures include leg, body,
arm, and head movements, as well as facial expressions. 

In recent years the price of image acquisition hardware has rapidly
decreased while increased computer power became available at
decreasing cost. There are good reasons to believe that this trend
will continue in the following years. Therefore, a number of seeing
environment applications can be realized for a realistic prize today.
Many more will follow in the near future.

While current research mainly concentrates on interpreting intentional
user commands, the most useful system responds to user {\em actions} rather
than to user {\em commands}. Such a system behaves like a good secretary who
acts independently and is hardly noticed when present but is
missed when absent. In this way the user can carry out his work
in the most efficient way. In fact, our experience with seeing
environments has shown that one of the biggest challenges to a seeing
environment in a real-world application is not to react to most user
actions but react very selectively to a few specific actions.

\section{Seeing Environments}
A seeing environment needs the capability to detect people in a
general office or household environment and should have one or more of
the following additional capabilities:
\begin{enumerate}
\item Interpretation of people's daily actions
\item Recognition of people
\item Interpretation of specific user commands
\end{enumerate}
One of the biggest advantages of having a seeing environment is the
fact that it can react over a distance without requiring physical
contact. On the other hand, it is just this distant reaction that
creates an urgent need for the capabilities of interpreting people's
daily actions and of recognizing people. Without these capabilities, a
seeing environment will respond unspecifically to many user actions
and might confuse visitors that are not used to this new type of 
environment. 


\section{Segmenting People in General Scenes}\label{Bic-sec:segment}
The segmentation of people in a general office or household
environment is a central task for a seeing environment. First,
segmented people provide the basis for contour-based recognition of
daily actions and gestures. Second, segmentation provides the initial
parameters for a detailed analysis of specific parts of the body, such
as face recognition and drastically reduces search times.

Segmentation should be fast and, therefore, computationally simple.
Additionally it should be fully automatic. Motion segmentation of gray
value images provides an elegant solution to these design criteria and
profits from the fact that in most office and household environments only
people, and perhaps animals, are in motion.

As computer power increases, color segmentation becomes an interesting
alternative to simple gray value processing. In fact, our recent
experiments showed that a combination between color-based skin
detection and motion segmentation leads to improved segmentation results.

Our implementation of motion segmentation starts with a Bayes
probability estimator for estimating the local probabilities of having
a background or object pixel based on the local brightness gradient. In a second step we 
exploit the fact that people are compact objects without holes and assume that the 
background is connected and that at least a single point is known to belong to the 
background (Figure 
\ref{Bic-fig:SegmentPath}). This means that for every background point we
have at least one path lying completely within the background and
leading from a known background point to the current point. For an
object point, in contrast, such a path does not exist. Therefore, for
each image point, we search the path that most probably lies completely
within the background. This search can be implemented efficiently with
an iterative algorithm \cite{Bic-Bichsel94c} and leads to an improved
estimate of the local background probability that is finally 
thresholded (Fig. \ref{Bic-fig:segment}).

\begin{figure} %%[tbh]
  \centerline{
    \epsfysize=2.0in
    \epsfbox{Bichsel_figs/Segment-Path.eps}
  }
  \hfil\parbox{6.0in}{
  \caption{
    \label{Bic-fig:SegmentPath}
  }
}\hfil
\end{figure}

\begin{figure} [tbh]
  \centerline{
   a)\epsfysize=1.7in
    \epsfbox{Bichsel_figs/martinaseg1.eps} 
   b)\epsfysize=1.7in
    \epsfbox{Bichsel_figs/martinaseg2.eps} 
   }	
  \caption{
    \label{Bic-fig:segment} Segmented images  \protect\\
    a) Person standing   \protect\\
    b) Person pointing.  \protect\\
  }
\end{figure}

People often move very slowly. Therefore, a motion detection algorithm
comparing only two subsequent video images will fail whenever people
stand or sit still. Comparing the current video image with an image of
the empty room leads to much more reliable motion segmentation. In a
general office or household environment, however, the room is modified
once in a while. Doors open and close, chairs and other equipment move
and lead to variations in the background. Therefore, we have
implemented an automatic learning of the background by using a Kalman
filter technique.

Varying illumination requires further modifications of the motion
segmentation algorithm. Two different effects lead to variations of
the image brightness. The first type of effects is related to true
illumination effects such as variations due to clouds in the sky or
switching of lights. These effects are either slow or rare, and can be
handled by the automatic background learning. 

The second type of
effects stems from the automatic gain control (AGC) of standard video
cameras. While the AGC can be switched off in most video cameras it is
a useful mechanism to keep image brightness at a reasonable level
and is needed in unconstrained environments since the illumination
level changes by orders of magnitude from illumination by standard 
lightbulbs to daylight. If AGC is switched on, however, user actions
lead to rapid variations of the gain and thus to rapid variations of
the background brightness. This problem has been solved
 by normalizing the local brightness gradients by the
local brightness mean \cite{Bic-Bichsel94b} and thus using local
illumination invariant quantities for object-background segmentation. 
\vspace{1cm}

\section{Interpretation of Daily Actions}
An analysis of a number of video sequences revealed that the most
important user actions are walking, standing still, sitting, and
picking things up,  as well as transitions between these actions. Our
analysis of people's actions starts by interpreting the contour of a
moving person in terms of  head, arms, and legs. By exploiting the
fact that people usually enter a room on their feet and that they walk
and stand on the floor, we infer the 3D position of the user's feet
based on  knowledge about  camera  position  and orientation with
respect  to the  room (Fig. \ref{Bic-fig:feet3d}).

\begin{figure} [tbh]
  \centerline{
   \epsfysize=2.0in
    \epsfbox{Bichsel_figs/Body3DfromFeet.eps} 
   }
  \caption{
    \label{Bic-fig:feet3d} Calculating 3D-position of feet by
intersecting viewing ray with floor plane.
  }
\end{figure}

Once we know the distance from the user to the camera we can calculate
the physical body height and infer the length of arms and legs based
on the fact that the ratio between the length of these joints 
and the body height varies only within a narrow
range among humans. The location of head, arms, legs, and body is
then estimated by fitting a generic body model to the measured contours.


Based on the physical user model an interpretation of sitting and
picking movements may be realized by analyzing head and arm movements.

Motion segmentation is most easy with a static camera. A static camera
is  also the cheapest hardware solution for implementing a seeing room.
Interpreting human actions with a single camera, however, requires a
wide angle lens with a viewing angle of at least 90 degrees. 
Our experience with such lenses showed that they lead to significant 
radial distortion of up to 50\% which, in good approximation, is
of the form
\begin{equation}
(x',y') = (x_c,y_c)+ (1+\alpha \;((x-x_c)^2+(y-y_c)^2))\;(x-x_c,y-y_c)
\end{equation}
where  $(x,y)$ are the image coordinates that are expected from
perspective projection, $(x',y')$ are the measured image coordinates,
$(x_c,y_c')$ is the focal point, and $\alpha$ is an experimental
constant that has to be determined by measuring the image coordinates
of a calibration object. This distortion model is the first order term
of a more general distortion model presented by Beyer \cite{Bic-Beyer94}.
Due to this radial distortion, 
the image of a straight line is
a curve rather than a straight line as expected from perspective projection.

This distortion is clearly visible in Fig. \ref{Bic-fig:distort} and
should be corrected  
during the image analysis process.

\begin{figure} [bth]
  \centerline{
   \epsfysize=1.5in
    \epsfbox{Bichsel_figs/radialdistortion.eps} 
  }
  \caption{
    \label{Bic-fig:distort} Typical radial distortion of wide angle lens.
  }
\end{figure}
\vspace{1.0cm}

\section{Recognizing People}
Recognizing people with face recognition techniques 
gives additional power to a seeing environment. 
If the identity of the people in a room is known, the system can adapt
to specific user needs and can, for example, treat working staff 
differently from
visitors or cleaning personnel.   

Recognizing faces in a general office or household environment,
however, is a difficult task since we have to cope with
varying illumination and varying head orientation.
An elegant but computationally expensive solution consists of 
reconstructing a 3D head model for each user based on shape from
multiple views. In the recognition algorithm,  these models are used to generate
a user image that is similar to the current video image
\cite{Bic-Bichsel95} (Figs.\ \ref{Bic-fig:Maja}, \ref{Bic-fig:model} and \ref{Bic-
fig:rendered}).

\begin{figure} %%[tbh]
  \centerline{
   \epsfysize=1.3in
    \epsfbox{Bichsel_figs/ebnerred_330.eps} 
   \epsfysize=1.3in
    \epsfbox{Bichsel_figs/ebnerred_340.eps} 
   \epsfysize=1.3in
    \epsfbox{Bichsel_figs/ebnerred_350.eps} 
   }
  \centerline{
   \epsfysize=1.3in
    \epsfbox{Bichsel_figs/ebnerred_000.eps} 
   \epsfysize=1.3in
    \epsfbox{Bichsel_figs/ebnerred_010.eps} 
   }
  \centerline{
   \epsfysize=1.3in
    \epsfbox{Bichsel_figs/ebnerred_020.eps} 
   \epsfysize=1.3in
    \epsfbox{Bichsel_figs/ebnerred_030.eps} 
   }
  \caption{
    \label{Bic-fig:Maja} Test images (only facial subwindow shown).
  }
\end{figure}
\begin{figure} %%[tbh]
  \centerline{
   \epsfysize=1.3in
    \epsfbox{Bichsel_figs/ebnerheight.eps} 
   \epsfysize=1.3in
    \epsfbox{Bichsel_figs/ebnerrefl.eps}
   }
  \caption{
    \label{Bic-fig:model} Reconstructed model: depth map (left) and
    map of local reflectance coefficient (right).
  }
\end{figure}

\begin{figure} %%[bth]
  \centerline{
   a)\epsfysize=1.3in
    \epsfbox{Bichsel_figs/ebnerrendX0Y25.eps} 
   b)\epsfysize=1.3in
    \epsfbox{Bichsel_figs/ebnerrendX0Y40.eps} 
   }
  \centerline{
   c)\epsfysize=1.3in
    \epsfbox{Bichsel_figs/ebnerrendX30Y0.eps} 
   d)\epsfysize=1.3in
    \epsfbox{Bichsel_figs/ebnerrendX0Y0L.eps} 
   }
  \caption{
    \label{Bic-fig:rendered} Rendered images.\protect\\
    a) Rotation around vertical axis by 25 degrees   \protect\\
    b) Rotation around vertical axis by 40 degrees   \protect\\
    c) Rotation around horizontal axis by 30 degrees  \protect\\
    d) Illumination from the right side.\protect\\
  }
\end{figure}

An interesting alternative consists of calculating morphs, {\it i.e.}
a geometrical distortion field and a brightness correction field,
that interpolate among a number of characteristic views
of a person. A person's video image is then recognized by finding
 the linear combination of morph fields that result
in the best fit. Examples of morph interpolation are shown in Figs.
\ref{Bic-fig:mit} and \ref{Bic-fig:steinview} where the top left and the
bottom right sub-image correspond to the original images and
the interpolation parameter increases from left to right and from top
to bottom.

\begin{figure} [tbh]
  \centerline{
   \epsfxsize=2.8cm
    \epsfbox{Bichsel_figs/mitwarp0.eps}
   \hspace{0.8mm}\epsfxsize=2.8cm
    \epsfbox{Bichsel_figs/mitwarp1.eps}
   \hspace{0.8mm}\epsfxsize=2.8cm
    \epsfbox{Bichsel_figs/mitwarp2.eps}
    }
  \centerline{
    \epsfxsize=2.8cm
    \epsfbox{Bichsel_figs/mitwarp3.eps}
   \hspace{0.8mm}\epsfxsize=2.8cm
    \epsfbox{Bichsel_figs/mitwarp4.eps}
   \hspace{0.8mm}\epsfxsize=2.8cm
    \epsfbox{Bichsel_figs/mitwarp5.eps}
  }	
  \caption{
    \label{Bic-fig:mit} Morphing of face 7676 (top left most) into face 7669
(bottom right most) based on calculated morph field.
  }
\end{figure}

\begin{figure} [tbh]
  \centerline{
   \epsfxsize=2.8cm
   \epsfbox{Bichsel_figs/steinemanng1b1warp0.eps}
   \hspace{0.8mm}\epsfxsize=2.8cm
   \epsfbox{Bichsel_figs/steinemanng1b1warp1.eps}
   \hspace{0.8mm}\epsfxsize=2.8cm
   \epsfbox{Bichsel_figs/steinemanng1b1warp2.eps}
    }
  \centerline{
   \epsfxsize=2.8cm
   \epsfbox{Bichsel_figs/steinemanng1b1warp3.eps}
   \hspace{0.8mm}\epsfxsize=2.8cm
   \epsfbox{Bichsel_figs/steinemanng1b1warp4.eps}
   \hspace{0.8mm}\epsfxsize=2.8cm
   \epsfbox{Bichsel_figs/steinemanng1b1warp5.eps}
  }	
  \caption{
    \label{Bic-fig:steinview} Automatic morphing of two face images taken
under different viewing conditions.
  }
\end{figure}
\vspace{1cm}

\section{Interpreting Specific User Commands}
User interaction by gestures should rely on gestures that are used in
everyday communication. Most users are not willing to learn sign
language or some specific gesture vocabulary application to
communicate with the seeing environment. Some important international
gestures in daily communication are
\begin{itemize}
\item rising hand, often amplified by waving hand, means pay attention
\item rising hand during an ongoing action means stop
\item pointing refers to next object in the direction of the pointing arm
\end{itemize}

The most important problem is: how to determine the start and end of
intentional user interaction. 
Implemented gestures are
\begin{itemize}
\item rising hand first time means start communication
\item rising hand second time means stop communication
\item pointing during a certain time (for example 2 seconds) refers to
the next object in the direction of the pointing arm
\end{itemize}
Thus, a user interaction is started and terminated with the rising hand gesture.
Gesture examples are shown in Fig. \ref{Bic-fig:gest}.
\begin{figure} [bth]
  \centerline{
   a)\epsfysize=1.8in
    \epsfbox{Bichsel_figs/martinagest1.eps} 
   b)\epsfysize=1.8in
    \epsfbox{Bichsel_figs/martinagest2.eps} 
   }
  \caption{
    \label{Bic-fig:gest} Gesture commands   a) typical start and stop signal,  b) pointing 
gesture.\protect\
  }
\end{figure}

These gestures can replace general user interactions that are implemented with
mouse movements in traditional user interfaces.
\vspace{1cm}

\section{Applications}
We have implemented the key components of a seeing environment and
tested them in three applications:
\begin{itemize}
\item the �automatic doorkeeper�, a system that recognizes faces at the
entrance door and opens the door only for authorized users.
\item communication �yes� and �no� answers by evaluating the head
orientation in a time sequence.
\item directing a robot by gesture commands.
\end{itemize}
An image of an experiment with the robot is shown in Fig. \ref{Bic-fig:robot}.
These applications show that seeing environments provide a direct and
intuitive communication from man to machine. 
\begin{figure} [bth]
  \centerline{
   \epsfysize=2.5in
    \epsfbox{Bichsel_figs/robotandmartin.eps} 
   }
  \caption{
    \label{Bic-fig:robot} View of a robot experiment.\protect\\
  }
\end{figure}

They, however, also reveal a
number of problems that are related to the unconstrained nature of
these applications. In particular, cast
shadows and mirror reflections on glass doors and other reflecting
materials can lead to false scene interpretations  and require additional research.
\vspace{1cm}


\section*{Acknowledgements}
The author would like to thank Prof.\ P. Stucki for providing a
stimulating working environment.
He would also like to thank  A.\ P.\ Pentland and Ch.\ Maggioni
for a number of stimulating discussions.



