\def\vect#1{\mbox{\boldmath$ #1 $}}
\def\smal#1{{\mbox{\tiny #1}}}
\def\mat#1{{\mbox{\normalsize\rm #1}}}
\def\smat#1{{\scriptscriptstyle #1}}
\def\R{{{\mbox I}\!{\mbox R}}}

\def\Ct{\cos\tau}
\def\St{\sin\tau}
\def\Cs{\cos\sigma}
\def\Ss{\sin\sigma}
\def\Cp{\cos\varphi}
\def\Sp{\sin\varphi}
\def\Ch{\cos\phi}
\def\Sh{\sin\phi}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\author[Colombo, Bimbo and Magistris]
{C. Colombo, A. Del Bimbo and  S. De Magistris\\
University of Brescia and University of Florence, Italy}
\chapter{Interfacing through Visual Pointers} 


%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
A key issue in advanced interface design
is the development of friendly tools for 
natural interaction between man and machine.
In this paper, we propose an approach
to non intrusive human-computer interfacing
in which the user's head and pupils are monitored
by computer vision for interaction control within on-screen 
environments. 
Two different {\em visual pointers} are defined,
which allow 
simultaneous and 
decoupled navigation and selection in 
3D and 2D graphic scenarios. The pointers intercept 
user actions, whose geometry is
then remapped onto the environment 
by a {\em drag and click metaphor} which
provides dialogue with a natural semantics.
\end{abstract}


%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{Col-SECT_INTRODUCTION}

In the last few years, a huge effort has been made towards
building advanced environments for man-machine
interaction and man-man communication mediated by computers.
Such environments can indeed 
improve both the activity and satisfaction of individual
users and computer supported cooperative work. 
Apart from some obvious implementation and design differences, 
virtual reality~\cite{Col-Rheingold91}, 
augmented reality~\cite{Col-Wellner93}
and smart room~\cite{G-Pentland96} environments
share the very same principle
of providing users with a more natural dialogue with (and through) 
the computer with respect to the past. This is achieved
through a careful design of the interface between the human
and the environment, both in terms of {\rm interface
languages} mimicking everyday experience
and advanced {\rm interaction tools}.

Recently,
the simultaneous 
growth of computing power and decrease of hardware costs,
together with the development of specific algorithms and techniques,
has encouraged the use of computer vision as a non intrusive technology for
the design of advanced man-machine interaction 
tools.
Experiments have been carried out
using computer vision for
gesture interpretation tasks such as lip-reading,
recognition of facial 
expressions, and head motion
understanding~\cite{G-Kaucic96,Col-Essa94b,G-Azarbayejani:93}. 
Vision-based interfaces allow user gestures and actions 
to be intercepted and used
to support interaction in a
wide semantic range. For example, 
in~\cite{G-starner95} vision-based hand gesture interpretation 
is used to develop an interface based on sign language, where
each sign is related to a specific
hand configuration pattern, which must be known 
a priori to the user. 
Such a rich interaction semantics 
at the user level is not always desirable,
as it may limit the
naturality of the dialogue.

In this paper, we propose a vision-based
technique to communicate with a computer
through pupil shifts and head motion;
a friendly interface is obtained
 by stressing the continuous-geometric aspects of
interaction and supporting natural
languages based on visual inspection and selection.
Interaction via head and eyes  
can be effective for both disabled users
affected by severe limb motor pathologies and
general users requiring non-intrusive man-machine 
interaction tools. 
The technique, which is
 presented in the context of
a virtual reality environment
 provided with hypertextual access,
can be easily adapted to 
other tasks and scenarios,
and support interaction in 
multimedia, videoconferencing, telepresence, 
usability monitoring, and
augmented reality environments. 

In our approach, a set of image features encoding
head and eye position is
 continuously tracked via
computer vision. 
The features are then remapped
onto the interaction environment, as the result of
a geometric/semantic interpretation of user action.
The location currently
observed and the user's interest are inferred
by monitoring head and pupil displacement
and geometric persistency.
This allows us to replicate the two basic
functions of dragging and clicking 
in 2D and 3D with a pair of {\em visual
pointers}, according to a paradigm which
allows pointing and navigation (geometric), 
and selection (semantic) actions. 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Visual pointers}
\label{Col-SUBSECT_VISION_BASED_INTERFACE}

Let our operating context be composed, as shown 
in Fig.~\ref{Col-FIG_SETUP}, by a 
camera (the front-end to the user) and
an on-screen multi-window environment.
%
%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
\begin{figure}
\vspace{2mm}
\centerline{\psfig{figure=Colombo_figs/silvio.eps,width=70mm}}
\caption{The basic elements of vision-based interaction:
 environment, user, camera.}
\label{Col-FIG_SETUP}
\end{figure}
%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
%
In such an environment, user actions are the result of a change
of interest, due either to the low-level visual content
of the environment (color, texture, etc.) or to some 
high-level user task, like purposively shifting the context
while browsing an hypertext, 
attempting to ameliorate interaction through a 
viewpoint change, exploring the scene, and so on.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Geometry}
\label{Col-SUBSUBSECT_TOOL}

To intercept shifts of interest, 
which involve the user's visuo-motor system,
a vision-based interaction tool 
can be designed to track and process simultaneously
the displacements of both the head --- 
rigid body in space, six degrees of freedom (DOF) --- and 
the eyeball --- two DOF, orientation of the visual axis in 
space\footnote{As for the eyeball DOF, 
we will actually refer to the intersection
of the visual axis, which gives the direction of gaze, 
with the screen plane,
which provides the location actually observed.} --- subsystems 
with respect to some fixed reference frame.
Such a tool is equivalent to the combination of a 3D pointing device
and a 2D pointer, respectively.  
Notice that, as the two subsystems are kinematically independent, 
the associated pointers can
also be made  independent one from the other by decoupling the 
measurement of head and eyeball displacements
through computer vision.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%
\begin{figure}[hbtp]
\vspace{2mm}
\centerline{\psfig{figure=Colombo_figs/_4frames.eps,width=10cm}}
\caption{Visual interaction: geometric aspects.}
\label{Col-FIG_3FRAMES}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%

From the geometric viewpoint, the basic elements of the 
interaction --- camera (image plane), 
screen and user's face --- can be modeled as planar surfaces in space.
We model
also the visible portions of the 
user's eyeballs, actually pseudo-spheres, as having a planar layout, 
and 
{\em regard 
any gaze shift related to an eyeball rotation as a translation of the 
pupil in the face plane}.
Let $A$, $B$ and $\Gamma$ denote respectively the screen, user 
and camera planes, and fix the local frames 
$\alpha$, $\beta$ and $\gamma$ as in Fig.~\ref{Col-FIG_3FRAMES}.

A first geometric aspect of the interaction concerns
the head's relative geometry (position and orientation)
w.r.t.~a given reference frame, say $\rho$.
This is encoded in the linear transformation 
 between the coordinate representations of
a generic point in space $\vect{p}$ in the $\beta$- and 
$\rho$-frames. 
Using homogeneous coordinates for $\vect{p}$, 
such a transformation
can be compactly described by means of 
$4 \times 4$ matrix
$^\smat{\beta}_\smat{\rho}     \mat{T}$
s.t.~$[^\smat{\beta} \vect{p}^\smal{T}\,\, 1]^\smal{T} = 
{}^\smat{\beta}_\smat{\rho}  \mat{T} 
\,\, [^\smat{\rho}  \vect{p}^\smal{T} \,\, 1]^\smal{T}$.
As changes of frame can be composed linearly, 
the $\rho \mapsto \beta$ transformation can be reconstructed
from the $\rho \mapsto \gamma$ 
and $\gamma \mapsto \beta$ transformations:
%
%
\begin{equation}
^\smat{\beta}_\smat{\rho}     \mat{T} =
{}^\smat{\beta}_\smat{\gamma}     \mat{T} \,
^\smat{\gamma}_\smat{\rho}     \mat{T} \quad,
\label{Col-EQ_T}
\end{equation}
%
%
thus letting the camera come into play as an element
of the interaction.
The former transformation
is time-independent, as long as the camera is fixed, while
the latter depends on the current position of
the user's head.

A second aspect of the interaction involves user's eyeball movements
and screen inspection. As the result of an eyeball
shift, a specific location of the screen is pointed, and
its visible content is projected through the pupil
onto the highest-resolution area of the retina, 
the fovea.
Thus, geometrically speaking,  we can regard at
each instant the pupil's
position in the face plane, $\vect{b}$, as the perspective image of the 
observed screen point $\vect{a}$, 
i.e.~$\vect{b} = {}^\smat{B}_\smat{A} f(\vect{a})$,
with
${}^\smat{B}_\smat{A} f: A \rightarrow B$
a nonlinear projection map depending, among other
parameters, on the entries of $^\smat{\beta}_\smat{\alpha}     \mat{T}$.
It is worth notice that the relative distance between the user and
the camera is such that,
in our context, conditions are met
to approximate the perspective camera with an {\rm affine camera}
model~\cite{G-Mundy:92}. This allows us to say that
a linear backprojection map 
 ${{{}^\smat{B}_\smat{A} h}^{-1}
={}^\smat{A}_\smat{B} h}: B \rightarrow A$ 
(with ${}^\smat{B}_\smat{A} h \approx {}^\smat{B}_\smat{A} f$) exists
 which brings pupil positions to screen locations.
 The same reasoning can be applied to define the 
 camera $\mapsto$ face backprojection 
 ${{}^\smat{B}_\smat{\Gamma} h}: \Gamma \rightarrow B$, and 
 write the map 
 ${}^\smat{A}_\smat{\Gamma} g$
 between camera-projected pupil positions $\vect{c}$
 and screen locations $\vect{a}$ as a composition of linear maps:
 %
 %
 \begin{equation}
 {}^\smat{A}_\smat{\Gamma} g = 
 {{}^\smat{A}_\smat{B} h}\, \circ \, 
{{}^\smat{B}_\smat{\Gamma} h}: \Gamma \rightarrow A \quad.
\label{Col-EQ_GAMMA}
 \end{equation}
 % %
Such a  camera $\mapsto$ screen 
backprojection 
map is a linear approximation to 
a {\rm perspectivity} (the ``picture of a picture''~\cite{G-Mundy:92})
and, as the product of two maps
which involve $\beta$, the user frame, it
is time-dependent.


The transformations of eqs.~(\ref{Col-EQ_T}) and (\ref{Col-EQ_GAMMA}) embed
the information used by our 3D and 2D pointers, respectively.
In Section.~\ref{Col-SECT_IMPLEMENTATION} we show how to compute and 
update such
information based on image data.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Semantics}
\label{Col-SUBSUBSECT_LANGUAGE}

The dialogue semantics currently 
implemented in our visual interface
 is based on a {\em drag and click metaphor}, which lets the user 
interact with the environment
 with his head and eyeballs to perform
 navigational, pointing and selection actions as with conventional 
pointing devices.

Explicitly, eyeball/head displacements with respect to a fixed reference
are interpreted as pointer drags, or {\em navigational actions}.
Pointers can trigger a {\em selection action} (click) as they persist
in the neighborhood of a geometric configuration
for a convenient time interval.
Since the production of discrete events is reduced here
to the on-off mechanism of time thresholding for selection, 
{\em pointers have basically the
same semantic 
expressivity of a 1-button mouse}. This design choice demands
virtually  the whole burden of expressivity from the interaction environment.


The semantics implemented attempts to assign a natural
meaning to the user's head and eye movements, which are basically
head's translations and rotations and pupil's shifts of fixation, 
so that even a naive user
can feel comfortable interacting with the system.
The head can be used to navigate or to displace
objects (drag) and to select, or ``freeze,'' a 3D scene of 
interest in it (click).
Eyeball drags, which take into account a displacement within the scene,
can be used e.g.,~for on-screen drawing or exploration, and
eyeball clicks to select relevant
2D information. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Implementation}
\label{Col-SECT_IMPLEMENTATION}

In this section, we discuss the implementation of 
our drag and click approach to vision-based interaction,
and describe our interface design choices in terms
of models and measurements.


\subsection{Projection and user modeling}
\label{Col-SUBSECT_CAMERA_USER}

\paragraph{Affine projection model.}

The relative geometry between any two frames is described
by six DOF. For example, the transformation
between the user and camera frames can be expressed as
%
%
\begin{equation}
^\smat{\gamma}_\smat{\beta}     \mat{T} = 
  \left [ { \matrix{
      {}&  \mat{R}(\tau,\sigma,\phi)&{}
           &  \vect{t} \cr
      0& 0& 0& 1 \cr
  } } \right ] \quad ,
\end{equation}
%
%
where $\vect{t} = [t_1~~ t_2~~ t_3]^\smal{T}$ is a translation 3-vector, and
$\mat{R}(\tau,\sigma,\phi)$
is a $3 \times 3$ rotation matrix, completely defined by the three
angles $\tau$ (tilt), $\sigma$ (slant) and $\phi$ (orientation). 
Specifically, defined each of 
the interaction frames with its third axis normal
to the associated plane (see again Fig.~\ref{Col-FIG_3FRAMES}),
$\sigma \in [0,{\pi}/2]$ is the angle between the
face and the image planes; this vanishes identically
if the two planes are parallel.

Affine perspective projection\footnote{We assume here that all 
intrinsic parameters
of the projection, and expecially the pixel size ratio, 
have their ideal values. In such a case, the affine projection
is called weak perspective~\protect\cite{G-Mundy:92}.} of a 
face point onto
the camera plane, ${{}^\smat{\Gamma}_\smat{B} h}$,
can be described in terms of a translation 
2-vector 
$\vect{h}$,
and a $2 \times 2$  projection
matrix
%
%
\begin{equation}
{ \mat{H}} =
\kappa \, \left [{\matrix{\cos \tau& - \sin \tau\cr \sin \tau& 
\cos \tau\cr}} \right ]
\left [{\matrix{- \cos \sigma& 0\cr  0& 1\cr}} \right ]
\left [{\matrix{\sin \phi&  - \cos \phi\cr  \cos \phi& \sin \phi\cr}} 
\right ] \quad ,
\label{Col-EQ_AFFINE}
\end{equation}
%
%
which is the composition of two planar rotations by $\tau$ and $\phi-\pi/2$,
of an anisotropic scaling by $\cos\sigma$ along a specific image
direction, and of an isotropic scaling of the imaged pattern by a factor
$\kappa$, which is proportional to the camera's focal 
length~\cite{Col-inproceedings:Colombo96}.

%%%%%%%%%%%%%%%%%%%%
\paragraph{User features being tracked.}

Head displacements and pupil positions can be estimated at one time
by tracking the visual appearance of the users' eyes. Indeed,
 the {\em external contour} of the eye, 
which is fixed to the head\footnote{Such a {\rm rigidity
constraint} assumes that any change of the visual appearance of the eye's
contour is related to a head displacement. Indeed, 
theoretically, even a nonrigid change of 
facial expression --- say, passing from normality to utmost stupor --- may
influence the external eye's appearance, but only at a very short time
scale. Thus, in practice, 
over longer time scales only geometric-driven changes
are significant.}, can be related to head displacements,
 while the internal {\em iris} contour, 
which is concentric with the pupil,
moves according to user pointing actions (eyeball shifts).
By analyzing separately the pupil pointing and 
head displacement characteristics of user's action allows us
to adopt a two-step eye tracking approach: 
%
%
\begin{enumerate}
\item {\em Track  the  external eye contour}. This
determines a search bound for the pupil's position in the image.
\item {\em Track the pupil inside the search bound}. 
\end{enumerate}
%
%
\noindent The latter condition is motivated by
the physiological constraint that {\rm the pupil must
always lie inside the external eye contour}. 

%
%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
\begin{figure}[hbtp]
\vspace{2mm}
\centerline{\psfig{figure=Colombo_figs/eyemodel.eps,width=\textwidth}}
\caption{Modeling the left and right eyes.}
\label{Col-FIG_EYEMODEL}
\end{figure}
%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
%


Image measurements for head  
tracking and pupil detection
are obtained by deforming a reference elastic template
so as to adapt it to current image data.
Let us assume now that the reference frame $\rho$ is
the $\beta$-frame at initialization time ($t=0$),
i.e.~$\rho = \beta(0)$. Assume also
that $\rho$ and $\gamma$ have mutually parallel 
third axes, i.e.~$\sigma(0) = 0$. 
Then, by eq.~(\ref{Col-EQ_AFFINE}), the reference template 
models a frontoparallel view of the eyes, possibly
translated by $\vect{h}(0)$, and scaled
and mirrored w.r.t the face plane's content by 
%
%
\begin{equation}
\mat{H}(0) = \kappa(0) \, 
\left [{\matrix{1& 0\cr 0& -1\cr}} \right ] \quad .
\label{Col-EQ_H0}
\end{equation}
%
%
The template 
is split in two sub-templates,
which capture the characteristics of the user's external eye and
iris, respectively (Fig.~\ref{Col-FIG_EYEMODEL}). 
The external eye sub-template, made of two semi-ellipses
sharing their major axis, depends on six parameters
($a$ through $f$ in the figure), namely the common major axis
($a$), the two minor axes ($b$, $c$), the ocular center's
image coordinates ($d,e$), and the common orientation ($f$).
A circle, parameterized
through the coordinates of its center ($i,j$) and its radius ($k$),
is used for the iris sub-template.
Notice that part of the iris is usually occluded by the eyelids,
a fact that is explicitly taken into account in our tracking strategy.

%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Sensing the user}
\label{Col-SUBSECT_MEASUREMENTS}

%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Template initialization.}

At system startup, a raw estimate of the eye location and shape 
in the image is derived, and the template is accordingly initialized. 
To speed up processing, 
the two image regions containing the eyes are
first roughly located by means of
{\em edge dominance maps}, i.e.,~maps
which take into account the dominance of brightness gradient
in a given direction~\cite{G-Brunelli93}. 
Fig.~\ref{Col-FIG_DOMAPS} shows pictorially the two-step
procedure for automatic eye localization. 

%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
\begin{figure}[hbtp]
\centerline{\psfig{figure=Colombo_figs/domaps.eps,height=3.5cm}}
\caption{Eye localization using dominance maps.}
\label{Col-FIG_DOMAPS}
\end{figure}
%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

 Once the regions including the eyes are found, the template
is adjusted against image data by an energy-minimization
criterion (see e.g.,~\cite{G-yuille92}). 
A quadratic energy term,
including the $9=6+3$ template parameters per eye, is minimized,
so that the template
is relaxed inside the eye regions by gradient descent.
After relaxation, 
the deformable template is
  used to initialize the run-time tracker, a lightweight
process which allows for fast system behavior.

%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Tracking the external eye.}

The tracker template is modeled after the external eyes only,
and is composed of a discrete set of points,
which are initialized soon after template relaxation,
by uniformly sampling the external eye contours.
At run-time,
the tracker's parameters are refined and updated
by means of a simple {\rm template-to-image fitting}
approach, based on least squares and the extraction of
brightness edge points (Fig.~\ref{Col-FIG_EYETRACKER_SEARCHIRIS}).
Thanks to our affine
projection model, the
tracker can be made quite robust by allowing it to deform
only in an affine fashion.


Explicitly, let 
the template at a generic time $t > 0$ be
$\{\vect{x}_i(t)\}$, $i = 1 \ldots N$,
its centroid be $\vect{x}_\smal{B}(t)$ and  the reference
template be $\{\vect{x}_i(0)\}$ with centroid $\vect{x}_\smal{B}(0)$.
Then template tracking proceeds as follows:
%
%
\begin{enumerate}
\item {\em Prediction.} In an image neighborhood of the previous 
template instance (time $t-1$),
      a  {\rm local search} of edge points (brightness gradient maxima)
       takes place at each of the $N$ template points
and along normal directions to the template itself. The set 
$\{\widetilde{\vect{x}}_i(t)\}$ of edge points (predicted set)
is computed by means of a 5-point, recursive coarse-to-fine algorithm
based on finite differences~\cite{Col-snakes:curwen2}. %\cite{Col-Cipolla94b}
Search intervals along each
direction are adaptively adjusted based on the previous tracking results.
\item {\em Least squares fit.} The LS approximation of
the new template centroid is simply the centroid (average point) of
the predicted set evaluated in the previous step, i.e.~
$\widetilde{\vect{x}}_\smal{B}(t) = \frac{1}{N} 
{\sum_i}~\widetilde{\vect{x}}_i (t)$.
A $2 \times 2$ matrix $\widetilde{\mat{L}}(t)$ is also evaluated via LS
as the best approximation of the affine transformation about 
the origin between
 the predicted set and the reference template. 
This is done by minimizing
the quadratic cost
${\sum_i}~\|{ (\widetilde{\vect{x}}_i(t) - \widetilde{\vect{x}}_\smal{B}(t)) -
\widetilde{\mat{L}}(t) \, ({\vect{x}}_i(0) - {\vect{x}}_\smal{B}(0)) } \|^2$
by solving the linear homogeneous system obtained
by partial differentiation w.r.t.~the unknown four parameters.
\item {\em Filtering.} The six parameters of the affine image transformation
$(\widetilde{\mat{L}}(t),\widetilde{\vect{x}}_\smal{B}(t))$ are smoothed 
using a mobile mean filter. For the generic parameter $p$, the filtered value
is 
$\widehat{p}\,(t) = w_p \, {p}(t) + (1 - w_p) \, \widehat{p}\,(t-1)$.
Notice that
to achieve a better control of the tracking process, a different filter 
gain $w_p \in [0,1]$ can be assigned to each parameter.
\item {\em Affine projection.} Once the  
 affine transformation $(\widehat{L}(t),\widehat{\vect{x}}_\smal{B}(t))$
is obtained,
the new tracker is finally computed as
${\vect{x}}_i(t) = {\vect{x}}_\smal{B}(t)  +
\widehat{\mat{L}}(t) \, ({\vect{x}}_i(0) - {\vect{x}}_\smal{B}(0))~~\forall i$,
 with
$\vect{x}_\smal{B}(t)=\widehat{\vect{x}}_\smal{B}(t)$.
This last step ensures that at each time $t>0$ the tracker is 
an affine-transformed
instance of the reference tracker, initialized at $t=0$. Besides, notice that
this tracking approach is independent of the specific tracker being used, 
so that
different shapes can be tracked
by simply changing the reference template --- say, using parabolic arcs instead
of elliptic arcs.
\end{enumerate}

%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
\begin{figure}[hbtp]
\centerline{\psfig{figure=Colombo_figs/etsi.eps,width=\textwidth}}
\caption{Affine-deformable eye tracker and
search of iris candidate points.}
\label{Col-FIG_EYETRACKER_SEARCHIRIS}
\end{figure}
%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

%%%%%%%%%%%%%%%%%%%%
\paragraph{Locating the pupil.}

Once the new tracker instance is found, 
the current 
iris shape and position are searched for inside it according to a 
technique akin to the one used before. However, some
important points of difference exist:

\begin{itemize}
\item {\em Affine model.} To deal with generic face views with 
nonzero slant angles\footnote{This
proves useful also when the intrinsic camera parameters such as the 
pixel size ratio
are not perfectly compensated.} which would produce an elliptic-shaped 
iris, an elliptic
template model is considered. This is initialized with the reference 
template's circular iris.
\item {\em Occlusions.} To avoid  erroneous results
due to possible partial iris occlusions,
the edge points belonging to the external eye tracker are 
automatically excluded from
LS fitting with the iris template; in this way, an external contour point 
is not taken into account as a predicted iris point $\widetilde{\vect{y}} = 
[\widetilde{x}~\widetilde{y}]^\smal{T}$.
To avoid occlusions, we use edge search lines
which are radial paths connecting external eye tracker's points
with the tracker's centroid: the search proceeds inwards and,
as shown in Figure~\ref{Col-FIG_EYETRACKER_SEARCHIRIS}, only
negative gradient points are taken into account.
\item {\em Matching.}  The steps of fitting and affine projection 
are simultaneous. This
is obtained by explicitly using the elliptic template's analytic expression
into the objective function.
Specifically, the new raw ellipse parameters are extracted 
by fitting predicted points with a generic conic via LS, and then
imposing the conic to be an ellipse.
That is, found the generic five conic parameters
$c_l$ which minimize
the squared error
%
%
%
$
{\sum_i}
\left [ {
{\widetilde{x}^{\,2}_i}+c_1\,{\widetilde{x}_i}{\widetilde{y}_i}
+c_2\,{\widetilde{y}^{\,2}_i}+c_3\,{\widetilde{x}_i}+
c_4\,{\widetilde{y}_i}+c_5
}
\right ]^2,
$
%
%
%
~these are  expressed  in terms of ellipse center, major 
and minor axes, and orientation~\cite{Col-inproceedings:Colombo95a}.
\end{itemize}

After the filtering step, the current center
of the  iris is taken as the new location of the pupil,
and used to update the 2D pointer.


%%%%%%%%%%%%%%%%%%%
\subsection{Controlling the environment}
\label{Col-SUBSECT_CONTROL}

%%%%%%%%%%%%%%%%%%%
\paragraph{Using the 3D pointer.}

Head displacements relative to the reference frame 
can be estimated from a comparison between the current and
reference trackers. 
At any time $t \geq 0$, the tracker is obtained by
a camera projection of the face plane
when the face frame
is $\beta(t)$;  following the notation of 
Subsection~\ref{Col-SUBSECT_MEASUREMENTS}, we denote
this projection 
as $(\mat{H}(t),\vect{h}(t))$,
where
the generic tracker is related to the reference tracker
through the affine transformation
$(\mat{L}(t),\vect{x}_\smal{B}(t))$ s.t.~$\vect{x}_\smal{B}(t) 
= \vect{h}(t)$ and
$\mat{L}(t) = \mat{H}(t)\,\mat{H}^{-1}(0)$.

If we can assume frontoparallel interaction, i.e.,~that
the user's face remains almost parallel to the screen during
the whole interaction time\footnote{The frontoparallel is a very natural way
to stand in front of a computer, 
as it is optimal in
terms of ergonomicity.}, 
 then $\sigma(t) \approx 0 \,\, \forall t>0$,
%
%
\begin{equation}
\mat{H} = \kappa \,
\left [{\matrix{- \sin\phi& \cos\phi\cr \cos\phi& \sin\phi\cr}} 
\right ] \quad ,
\end{equation}
%
%
and rotations are fully described by the orientation angle
 $\phi(t)$ in $[0,2\pi]$, initialized to $\phi(0) = - \pi/2$ to satisfy
eq.~(\ref{Col-EQ_H0}). 
Notice that during
frontoparallel interaction the head DOF are reduced
from six to four --- namely, a translation 3-vector
and a rotation in the face plane. 
The head DOF can be conveniently
referred to the $\rho$-frame
as $\vect{t}(0)-\vect{t}(t)$ and $\phi(t)$, and
related to 2D quantities as follows:
%
%
\begin{equation}
\vect{t}(0)-\vect{t}(t) = {1}/{\kappa(0)}\,
\left ( { 
\left [ \matrix{ \vect{h}(0) \cr \lambda } \right ] - 
\frac{\kappa(0)}{\kappa(t)} 
 \left [ \matrix{ \vect{h}(t) \cr \lambda} \right ] 
} \right ) \quad ;
\label{Col-EQ_T0TT}
\end{equation}
%
%
%
%
\begin{equation}
\left [{\matrix{\sin\phi(t)& \cos\phi(t)\cr - \cos\phi(t)& 
\sin\phi(t)\cr}} \right ] =
- \frac{\kappa(0)}{\kappa(t)} \, \mat{L}(t) \quad .
\label{Col-EQ_A}
\end{equation}
%
%
Given focal length $\lambda$ and an estimate 
of $\mat{L}(t)$, $\vect{h}(t)$ and $\vect{h}(0)$, it is possible
in principle
to recover rotation $\phi(t)$ and relative scaling ${\kappa(0)}/{\kappa(t)}$
from eq.~(\ref{Col-EQ_A}), and use the latter into eq.~(\ref{Col-EQ_T0TT})
to recover translation parameters up to an unknown
scale factor\footnote{This indetermination originates from 
 modeling not the eyes themselves in the face plane but 
their image appearance instead. 
} $1/\kappa(0)$. 

However, we prefer to use a more direct approach to evaluate relative
scale and rotation from the current and reference 
trackers --- Figures.~\ref{Col-FIG_4DOFREMAP} ({\em a},{\em b}) --- which 
does not involve eq.~(\ref{Col-EQ_A}) but exploits
the image located ocular centers instead.
Observe in fact that relative scaling
can be estimated as the interocular distance ratio 
 ${\delta(0)}/{\delta(t)}$ (Fig.~\ref{Col-FIG_4DOFREMAP}, {\em c}).
Similarly, as shown in Fig.~\ref{Col-FIG_4DOFREMAP} ({\em d}),
the relative inclination of the line connecting the ocular centers
can be used to estimate rotation. 

The estimated 3D parameters
correspond one-one to the four basic head displacements
which the user can mix together during parallel interaction.

%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
\begin{figure}[hbtp]
\centerline{\psfig{figure=Colombo_figs/4DOFremap.eps,width=\textwidth}}
\caption{The four head DOFs considered for the experiments.}
\label{Col-FIG_4DOFREMAP}
\end{figure}
%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF


%%%%%%%%%%%%%%%%%%%%%
\paragraph{Calibrating and using the 2D pointer.}

Remapping the 2D pointer 
has a more quantitative nature.
The key idea for such a pointer is in fact to be able
to know where the user is actually looking in the screen.
Such a strategy, referred to as ``what you look at
is what you get,'' is usually implemented using
precise but otherwise intrusive infrared light 
equipment~\cite{Col-Jacob93,Col-Hutchinson93}, and allows the eye pupil
to be used as a 2D mouse.

Denoted 
the affine eye projection map by $(\mat{K},\vect{k})$,  
defined a new camera projection map as $(\mat{H}^\prime,\vect{h}^\prime)$, 
with $\vect{h}^\prime$ the projection of the ocular center of the eye
where the pupil is located\footnote{Such a projection
is also the centroid of the external eye sub-tracker including
the pupil's image. Vectors 
$\protect\vect{h}$ of eq.~(\protect\ref{Col-EQ_T0TT})
and $\protect\vect{h}^\prime$
differ by the centroid of the remaining sub-tracker.},
and
expressed image and screen points $\vect{c}$ and $\vect{a}$
as 2-vectors
using their native coordinate frames $\gamma$ and $\alpha$
respectively, it holds:
%
%
\begin{equation}
^\smat{\alpha}\vect{a} = \mat{M}\,^\smat{\gamma}\vect{c} + 
\vect{m} \quad ,
\label{Col-EQ_CALEQUATION}
\end{equation}
%
%
where $\mat{M} = \left [ {\mat{H}^\prime \mat{K}} \right ]^{-1}$
and $\vect{m} = - \mat{M}\,\vect{h}^\prime - \mat{K}^{-1}\,\vect{k}$.


%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
\begin{figure}[hbtp]
\centerline{\psfig{figure=Colombo_figs/cal_gm00.eps,width=54mm} \hspace{1mm}
\psfig{figure=Colombo_figs/cal_gm01.eps,width=54mm}}
\caption{2D calibration. {\em Left}: Calibration grid.
{\em Right}: Remapped points.}
\label{Col-FIG_CALIBRATION}
\end{figure}
%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

The transformation $(\mat{M},\vect{m})$ involves
time-dependent quantities, some of which unknown or
difficult to know, 
such as the distance from eye to screen and 
eye focal length.
Nevertheless, such a camera $\mapsto$ screen mapping can be
estimated at startup via a two-phase plane-to-plane
{\rm calibration} procedure:
%
%
\begin{enumerate}
\item {\em Observation.}  A set of $M \geq 6$ image observations of 
pupil positions is collected and recorded, 
obtained by tracking the pupil while letting the user 
execute a ``scan-path,'' i.e.,~a sequence of gaze fixations, on 
a number of given screen locations.
Figure.~\ref{Col-FIG_CALIBRATION} ({\em left}) shows the case with $M = 9$,
where the locations to fix upon are
organized in a $3 \times 3$ calibration grid covering the entire screen.  
To reduce errors during this phase,
each new observation is obtained as an average of 
subsequent image measurements.
\item {\em Estimation.} The affine model is 
then estimated using data and observations, 
as the LS solution of an
overdetermined system obtained from eq.~(\ref{Col-EQ_CALEQUATION}). 
LS computations can be carried out in two steps, 
by first computing data and observation centroids
$^\alpha\vect{a}_\smal{B}$ and $^\gamma\vect{c}_\smal{B}$ and
estimating the matrix $\mat{M}$ as with affine tracking from 
$({}^\alpha\vect{a} - {}^\alpha\vect{a}_\smal{B}) = 
\mat{M}\,({}^\gamma\vect{c} - {}^\gamma\vect{c}_\smal{B})$, and then
obtaining the translation with
$\vect{m} = {}^\alpha\vect{a}_\smal{B} - \mat{M}\,^\gamma\vect{c}_\smal{B}$. 
\end{enumerate}

At run-time,
pupil positions in the image are remapped onto the screen
using the calibrated map.
 Figure.~\ref{Col-FIG_CALIBRATION} ({\em right}) shows
the qualitative results of a test on calibration accuracy.
In the test, the user was asked to fix successively
the calibration grid points,
while the corresponding computed pupil positions in the image, 
suitably averaged,
were remapped onto the screen 
according to eq.~(\ref{Col-EQ_CALEQUATION}).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{|c|c|c|c|} 
\hline\hline
{\sc Calibration Accuracy} & {\em Error on {\rm x}}       & 
{\em Error on {\rm y}} & {\em Uncertainty radius}        \\ \hline
{\em Average {\rm (mm)}}        & 6.23  &  10.69 & 12.38 \\ \hline
{\em Maximum {\rm (mm)}}           & 17.51  & 19.93 & 26.53 \\  
\hline\hline
\end{tabular}
\caption{Calibration accuracy.}
\label{Col-TAB_CALPERFORMANCE}
\end{center}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%

Quantitative
results on the same
 calibration test are shown in Tab.~\ref{Col-TAB_CALPERFORMANCE}. 
The table reports the average and maximum 
mismatch between the set of calibration points (``ground truth'') and
the remapped points both for the two coordinate directions and in magnitude.
Magnitude errors provide us with a resolution limit for our
2D pointer, which must be taken into account in the design of
the graphic interface.
To reduce map reconstruction errors during
calibration, head motions can be compensated
by normalizing the image plane observations w.r.t.~the
reference template. Similarly, the calibrated map can be updated
at remap-time based on current visual data~\cite{Col-Colombo97}.


%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Pointer timing.}
Choosing the right threshold value is of key importance to
have a good balance between speed of operation and
naturality of interaction. If the threshold value is too low,
then every action is interpreted as a click command,
an undesirable situation usually referred to as
{\em Midas touch}~\cite{Col-Jacob93}.
A good dwell time for the 2D pointer, which takes
into account the high mobility of the pupil, is $500$ ms, 
which on the one hand guarantees a fast response, and on the other
limits the occurrence of false alarms.
Since head motions are slower, a 
time threshold about four times longer ($2$ s) can be used
for the 3D pointer.

A second timing mechanism is implemented in the interface,
which avoids the occurrence
of ``interference'' between the pointers. Consider for example
the case of a 3D click, which occurs when the head persists in
a fixed position for one second or more. If, in the same time period,
the pupil is still too, then a 2D click event is generated, which
is most probably involuntary. To solve the interference problem,
the 2D and 3D pointers are decoupled, by letting the
pupil be actually remapped only if the head is in a suitable
neighborhood of its reference position --- i.e.,~if the
current tracker's parameters are not too dissimilar
from the reference tracker. 




%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Interface}
\label{Col-SECT_INTERFACE}

An interface has been implemented to support
interaction using our visual pointers 
within a virtual museum
containing
a digital collection of canvas by famous
20th century artists such as
Klimt, Picasso, Modigliani, etc.
The virtual environment is complemented
by a 2D on-screen hypertext providing the museum
with on-line catalogue facilities.

The graphic interface 
uses the OpenGL graphic libraries and runs
on a Silicon Graphics Indy workstation
(MIPS R4000/R4010 with 100 MHz clock).
The vision subsystem software also runs on the 
Indy, and gets raw image data through a VINO frame grabber 
board from an off-the-shelf B/W camera.

To achieve natural interaction, the loop
delay must be short enough to provide the
user with feedback about his latest action.
The overall interaction loop time 
for our system is the sum of the time spent
doing visual computations
and graphic environment manipulation.
Initializating visual algorithms involves
automatic eye extraction and template
initialization and takes around $450$ ms to complete.
At run-time visual tracking runs almost at
video rate ($50$ ms) instead, 
using $N=64$ sampling points for both
external eye and iris search.
Without special hardware for graphics acceleration,
most of the loop time
 is taken by graphic remapping
(some hundreds ms at an intermediate image quality).

%%%%%%%%%%%%%%%%%%%% 
\paragraph{3D viewpoint control and navigation.}
Examples of a typical interaction session 
using the 3D pointer are illustrated
in Figures.~\ref{Col-FIG_ZOOM} through~\ref{Col-FIG_PAN}
(sequences flow top to bottom and left to right).
The screen content and the image plane --- in particular, 
the face 
and eye region --- are shown, in order to emphasize the relationship 
between user action and environment changes.

Figure.~\ref{Col-FIG_ZOOM} shows a
zoom-in sequence. Zooming is obtained by approaching
the screen with the head; this causes
 the painting in the middle of
the wall to be displayed at full resolution. 
A new viewpoint can always be selected 
by head fixation. However, in this case the user
decides to go back to the initial view by moving
away from the screen (last image of the sequence).

%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
\begin{figure}[hbtp]
\centerline{\psfig{figure=Colombo_figs/zoomgm00.eps,width=54mm} 
            \hspace{1mm}
            \psfig{figure=Colombo_figs/zoomgm07.eps,width=54mm}}
            \vspace{3mm} 
\centerline{\psfig{figure=Colombo_figs/zoomgm10.eps,width=54mm}
            \hspace{1mm}
            \psfig{figure=Colombo_figs/zoomgm11.eps,width=54mm}}
\caption{3D pointer: zoom sequence.}
\label{Col-FIG_ZOOM}
\end{figure}
%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF


%%%%%%%%%% PAN
Viewpoint changes are produced by navigational 
actions corresponding to head translations 
parallel to the screen. Figure.~\ref{Col-FIG_PAN} actually 
shows a pan sequence, in which the 
constraint on frontoparallel interaction is not met.
Notice that, in the image, this produces
a rigid rightward head translation, which is correctly 
interpreted as a leftward environment shift, 
{\em and} a decrease of interocular distance, which is
incorrectly interpreted as a zoom-out. Thus, the correct
image resolution must be recovered by an additional
zoom-in action.

Besides, notice that proper semantics must be introduced
to generate rotations in the environment
using our four DOF pointer. In our interface, if a 
side museum wall is reached by a translational movement,
an environment rotation is automatically generated,
so as to show the paintings on that wall.


%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
\begin{figure}[hbtp]
\centerline{\psfig{figure=Colombo_figs/pan_gm00.eps,width=54mm} 
            \hspace{1mm}
            \psfig{figure=Colombo_figs/pan_gm04.eps,width=54mm}}
            \vspace{3mm}
\centerline{\psfig{figure=Colombo_figs/pan_gm06.eps,width=54mm} 
            \hspace{1mm}
            \psfig{figure=Colombo_figs/pan_gm08.eps,width=54mm}}
\caption{3D pointer: pan sequence.}
\label{Col-FIG_PAN}
\end{figure}
%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF


%%%%%%%%%%%%%%%%%%%%
\paragraph{2D inspection and selection.}

%% inspection
Once a specific viewpoint
has been selected by head rotation,
the user can go back to the reference position,
inspect the on-screen scene,
and possibly
learn more about a given
painting in it, or about its author, by 
selecting a canvas by pupil pointing (Figure.~\ref{Col-FIG_BIDI_1}).


%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
\begin{figure}[hbtp]
\centerline{\psfig{figure=Colombo_figs/bidigm06.eps,width=54mm} 
            \hspace{1mm}
            \psfig{figure=Colombo_figs/bidigm07.eps,width=54mm}}
            \vspace{3mm}
\centerline{\psfig{figure=Colombo_figs/bidigm08.eps,width=54mm} 
            \hspace{1mm}
            \psfig{figure=Colombo_figs/bidigm09.eps,width=54mm}}
\caption{2D selection. The 1st menu level is accessed
from level 0
by steadily pointing the eye to a specific painting.}
\label{Col-FIG_BIDI_1}
\end{figure}
%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF


An important aspect of the interface concerns the screen
regions which can accept eye-gaze commands, which we refer
to as {\em active windows}. At menu level 0, as commands are
issued directly by fixing a canvas, each canvas is an active
window. At menu level 1 (Figure.~\ref{Col-FIG_BIDI_1},~{\em bottom right}),
the screen is partitioned in two
regions. The left-hand region has six active windows,
four of which allow access to information about author, 
historical period, selected and related 
paintings; the remaining two windows are used for paging
control (``back,'' ``next''). The right-hand side of the screen
contains output information, and as such it can be fixed by the
user without timing constraints (passive window).
As the first menu level is accessed, the passive window
is filled by default 
with the painting which was selected in the museum.
Figure.~\ref{Col-FIG_BIDI_2} shows the process of getting information about
the author of such painting: the ``author'' button is 
repeatedly fixed, and this causes the author information to be pasted
into the passive window to be read.


%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
\begin{figure}[hbtp]
\centerline{\psfig{figure=Colombo_figs/bidigm11.eps,width=54mm}
            \hspace{1mm}
            \psfig{figure=Colombo_figs/bidigm13.eps,width=54mm}} 
\caption{2D selection: second menu level.}
\label{Col-FIG_BIDI_2}
\end{figure}
%FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF


Notice that the spacing and size of active windows
strictly depends on the 
magnitude of the pupil remapping error (see again 
Tab.~\ref{Col-TAB_CALPERFORMANCE}). Indeed, the average pointing error can be
used to properly designing the 2D interface
and size-up active windows in order
to reduce the risk of false alarms
during slightly incorrect pointing. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Innovation}
\label{Col-SECT_INNOVATION}

In this paper, we have presented an approach
to advanced man-machine interfacing based on
computer vision and computer graphics.
The basic idea is to use computer vision
to develop non intrusive pointer devices based
on user head and eye motions, and to couple them with
a simple drag and click semantics for
interaction in graphic 2D and 3D environments.
Basically, the pointers capture significant
parameters of user action, which are then remapped
onto the environment. The main operations which
the user can perform are environment 
exploration and data selection.
Head tracking is used to interact with
a 3D environment, while eye pupil tracking allows to
control interaction with 2D-based interfaces.
To implement the 3D pointer, we continuously track the
image of the external part of the user's eyes, 
and use its deformations to infer head motion parameters.
Concerning the 2D pointer, we propose an approach
derived from infrared technology applications,
and novel to computer vision:
To track eye pupils so as to 
measure gaze pointing actions in terms
of observed screen points rather than simply as 
directions in the 3D space.

Finally, we outline some directions for future work
with our visual pointer technique.
One way to cope with uncertainty
in measurements and human intentions alike is to use {\em adaptive
interfaces}. Such interfaces should cooperate with the user in making
a decision, either by allowing him to refine a command, or
by suggesting a series of alternatives during interaction.
The interaction framework can be
extended to deal with {\em remote environments}. Indeed,
while interaction 
with the on-screen environment always takes place
locally, the displayed scene needs not to be necessarily
a graphic environment, but could be e.g.~the output
of a remote, possibly motorized,
 camera. Thus our approach could be effectively 
extended to applications such as teleconferencing, telepresence and
teleoperation.
Other interesting applications are
in the field of {\em augmented reality}. 
Think of replacing the screen plane
with a real-world plane, say a desk, an office wall
or some other work panel. The approach
could be easily adapted to this new scenario.
Another extension of the approach could be to allow
for {\em richer semantics at the user level}. That is, besides
the basic interaction capabilities offered by our approach,
the user could be provided with other means of interfacing
with the machine. A way to extend semantics naturally in a 
computer vision context can be that of interpretation of gestures 
and expressions.



