\newtheorem{definition}{Definition}
\newtheorem{property}{Property}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}

\author[John J. Weng \& Yuntao Cui]{
John J. Weng$^{\dag}$ and Yuntao Cui$^{\ddag}$\\
$^{\dag}$Department of Computer Science,  \ \  $^{\ddag}$Siemens Corporate Research \\
Michigan State University, \ \ 755 College Road East\\
East Lansing, MI, 48823 \ \ Princeton, NJ 08540
}

\chapter{Recognition of Hand Signs from Complex Backgrounds}

\Abstract{In this chapter, we present our approach to 
recognizing hand signs. It addresses three key aspects
of the hand sign interpretation, the hand location, the hand shape, 
and the hand movement. The approach has two major components:
(a) a prediction-and-verification segmentation scheme to segment the
moving hand from its background;
(b) a recognizer that recognizes the hand sign from the temporal 
sequence of segmented 
hand together with its global motion information. The segmentation scheme
can deal with a large number of different hand shapes against 
complex backgrounds. In the recognition part, we use
multiclass, multidimensional discriminant analysis in every internal node
of a recursive partition tree to 
automatically select the most discriminating linear features for gesture 
classification. The method has been tested to recognize 28 
classes of hand signs. The experimental 
results show that the system
can achieve a 93\% recognition rate for test sequences that have
not been used in the training phase.

\section{Introduction}

The ability to interpret the hand gestures is essential if computer
systems can interact with human users in a natural way. 
In this chapter, we present a new vision-based framework which allows
the computer to interact with users through hand signs.

Since its first known dictionary was printed in 1856 \cite{Wen-Brown1856},
American Sign Language (ASL) is widely used in the deaf community as
well as by the handicapped people who are not deaf \cite{Wen-Bonvillian76}.
The general hand sign interpretation needs a broad range of contextual
information, general knowledge, cultural background, and 
linguistic capabilities. 

Tremendous difficulties exist toward automatic hand-sign recognition
in general settings.  In order to concentrate on the focus
of research with a manageable scope,
we control the indoor environment so that the lighting is fixed and
the human signer sits in front of the computer, facing the camera.
In such an environment, the task of hand-sign
recognition still involves a series of challenging tasks, including
finding the location of the hand, segmenting hands from
the complex backgrounds such as texture of various clothes, distinguishing
various hand gestures, recognizing hand-signs which include
location, shape, local motion, and global motion.

In our
current research, we extract a set of hand gestures which have meaning
in human communication. Twenty-eight different signs \cite{Wen-Bornstein89}
used in our experiments 
are illustrated in Figure \ref{Wen-FG:sign_pict}. These hand signs have following
characteristics: 1) they represent a wide variation of hand shapes;
2) they include a wide variation of motion patterns; 
3) these hand signs are performed by one hand;
4) recognition of these signs does not depend on contextual
information. The gestures which require the hand to perform in a 
certain environment
or to point to a specific object are excluded.

In the linguistic description of ASL, Stokoe used a structural linguistic
framework to analyze sign formation \cite{Wen-Stokoe60}. He defined three
`�aspects�  that were combined simultaneously in the formation of
a particular sign - what acts, where it acts, and the act. These three
aspects translate into building blocks that linguists describe - the 
hand shape, the location, and the movement. There are two major components
in our framework to deal with above three building blocks. We have 
a prediction-and-verification scheme to locate hands from complex
backgrounds. The spatiotemporal recognition component combines
motion understanding (movement) with spatial recognition (hand shape) in
an unified framework.

\begin{figure}[tbhp]
\centerline{
        \psfig{figure=Weng_figs/angry.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/any.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/boy.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/yes.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/cute.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
}
\centerline{
                \makebox[2.0cm]{(1)}
                \makebox[2.0cm]{(2)}
                \makebox[2.0cm]{(3)}
                \makebox[2.0cm]{(4)}
                \makebox[2.0cm]{(5)}
}
\vspace*{0.2cm}
\centerline{
        \psfig{figure=Weng_figs/fine.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/funny.ps,width=2.0cm,height=2.0cm}
	\hspace*{0.005cm}
        \psfig{figure=Weng_figs/girl.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/happy.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/hi.ps,width=2.0cm,height=2.0cm}
}
\centerline{
                \makebox[2.0cm]{(6)}
                \makebox[2.0cm]{(7)}
                \makebox[2.0cm]{(8)}
                \makebox[2.0cm]{(9)}
                \makebox[2.0cm]{(10)}
}
\centerline{
        \psfig{figure=Weng_figs/high.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/hot.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/later.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/low.ps,width=2.0cm,height=2.0cm}
	\hspace*{0.005cm}
	\psfig{figure=Weng_figs/no.ps,width=2.0cm,height=2.0cm}
        }
\centerline{
                \makebox[2.0cm]{(11)}
                \makebox[2.0cm]{(12)}
                \makebox[2.0cm]{(13)}
                \makebox[2.0cm]{(14)}
                \makebox[2.0cm]{(15)}
                }
\vspace*{0.2cm}
\centerline{
        \psfig{figure=Weng_figs/nothing.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/ofcourse.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/ok.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/parent.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/pepper.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
}
\centerline{
                \makebox[2.0cm]{(16)}
                \makebox[2.0cm]{(17)}
                \makebox[2.0cm]{(18)}
                \makebox[2.0cm]{(19)}
                \makebox[2.0cm]{(20)}
                }
\vspace*{0.2cm}
\centerline{
        \psfig{figure=Weng_figs/smart.ps,width=2.0cm,height=2.0cm}
	\hspace*{0.005cm}
        \psfig{figure=Weng_figs/sour.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/strange.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/sweet.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/thankyou.ps,width=2.0cm,height=2.0cm}
        }
\centerline{
                \makebox[2.0cm]{(21)}
                \makebox[2.0cm]{(22)}
                \makebox[2.0cm]{(23)}
                \makebox[2.0cm]{(24)}
                \makebox[2.0cm]{(25)}
                }
\vspace*{0.2cm}
\centerline{
        \psfig{figure=Weng_figs/thirsty.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/welcome.ps,width=2.0cm,height=2.0cm}
        \hspace*{0.005cm}
        \psfig{figure=Weng_figs/wrong.ps,width=2.0cm,height=2.0cm}
        }
\centerline{
                \makebox[2.0cm]{(26)}
                \makebox[2.0cm]{(27)}
                \makebox[2.0cm]{(28)}
                }
\caption{\protect\small
The twenty eight different signs used in the experiment:
(1) sign of �angry�; (2) �any�'; (3) �:boy�';
(4) �yes�'; (5) �cute�'; (6) �fine�; (7) �funny�; (8) �girl�;
(9) �happy�; (10) �hi�; (11) �high�; 
(12) �hot�; (13) �later�; (14) �low�; (15) �no�; 
(16) �nothing�; (17) �of course�; (18) �okay�;
(19) �parent�; (20) �pepper�; (21) �smart�; (22) �sour�; 
(23) �strange�; (24) �sweet�;
(25) �thank you�; (26) �thirsty�; (27) �welcome�; (28) �wrong� 
(Bornstein and Saulnier 1989}
\label{Wen-FG:sign_pict}
\end{figure}

\section{Relation to Previous Work}
 
Recently, there has been a significant amount research on vision-based hand 
gesture recognition (%e.g. \cite{Wen-Blake94,Wen-Bobick95,Wen-Cho94,Wen-Cipolla93,Wen-Cui95b,
%Darrell93,Davis94,Downton91,Etoh91,Kervrann94,Kuch95,
%Starner95} and 
see \cite{G-Huang95} for a survey). The vision-based
approaches acquire visual information of a gesture using a single video
camera or a pair of cameras.
Once the visual information is acquired, the sign is extracted  
by analyzing the temporal image 
sequence.

The existing approaches typically include two partsa: modeling hands and
analysis of hand motion.
%vision-based systems use model-based approaches. 
%Typically, this kind of approaches
%consist of three parts, modeling hands, modeling hand motion, and recognition
%of hand motion. 
Models of the human hand include the three dimensional model (e.g., 
Downton and Drouet
\cite{Wen-Downton91} and Etoh {\em et al} \cite{Wen-Etoh91}: generalized cylindrical
model; Kuch and Huang \cite{G-Kuch95}: NURBS-based hand model), 
the region-based model (e.g., Darrell and Pentland 
\cite{G-Darrell93},
Bobick and Wilson \cite{Wen-Bobick95}, and Cui {\em et. al.} 
\cite{Wen-Cui95b}), 
the two dimensional
shape model (e.g., 
Starner and Pentland \cite{G-starner95}: elliptic shape models;
Cho and Dunn \cite{Wen-Cho94}: line segments shape model; 
Kervrann and Heitz \cite{Wen-Kervrann94} and Blake and Isard \cite{Wen-Blake94}: 
contour
shape model), and the fingertip model (e.g., Cipolla {\em et al} 
\cite{Wen-Cipolla93} and
Davis and Shah \cite{Wen-Davis94}). 

Different models of hands lead to different models of hand motion. 
The system which
uses the three dimensional hand model is capable of modeling the real
hand kinematics (e.g., \cite{G-Kuch95}).
%\cite{G-Kuch95}. 
For the system which uses
the two dimensional hand model, the motion is described as two dimensional
rotation, translation and scaling in the image plane \cite{Wen-Kervrann94}. 
The
trajectory of each fingertip is suitable to represent the motion in
the case when the
fingertip is used to model hands \cite{Wen-Davis94}. 
Typically, motion parameters are used to
perform gesture classification.

The vision-based approach is one of the most 
unobtrusive ways to enable users to interact with computers in a natural
fashion. However, it faces several difficult problems due to the limitations in
machine vision today. Among them, the problem of segmenting moving
hands from sometimes complex backgrounds is perhaps the most difficult one.
%; 2) how to handle various 
%lighting conditions and viewing positions.
Many current systems rely
on markers or marked gloves (e.g. \cite{Wen-Cipolla93,Wen-Davis94,G-starner95}). The
others simply assume uniform backgrounds 
(e.g. \cite{Wen-Bobick95,Wen-Cui95b,G-Darrell93}). Recently, Moghaddam and 
Pentland \cite{Wen-Moghaddam95}
proposed a maximum likelihood decision rule based on the
estimated probability density of the hand and its 2D contour to detect
hands from intensity images. 

The human hand can change its shape tremendously
in various hand signs.  Furthermore, the signer can wear any
clothes, which becomes a part of the background.  Some of the
backgrounds are shown in Figure .~\ref{Wen-FG:sam_seq}. 
Therefore, segmentation and recognition must be tightly
coupled --- {\em without segmentation, reliable
recognition is difficult; without recognition, reliable segmentation is
difficult}.  We address this fundamental problem using 
a prediction-and-verification scheme \cite{Wen-Cui96}.  The prediction is
based on partial views of the hand together with the learned relationship
between each partial view and the global contour of the hand.  
The verification first extracts the actual observed hand from 
its background using the predicted global contour 
and then the extracted hand is verified based on the learned information about
human hands.  Our segmentation scheme
does not use any background pixels in the prediction and verification 
and therefore is applicable to very complex backgrounds. 
 
Another major difference between our framework and most existing approaches
is that in our framework, motion understanding is tightly coupled with 
spatial recognition.  All the spatial and temporal information of the
hand sign is treated in a unified way. 
We do not separate the hand modeling and the motion
recognition into two different processes.  The 
automatically computed,  most discriminating 
features (MDF) will weight every spatial and temporal component in an optimal 
way.  Thus, it can effectively deal with different cases,
no matter which information is more important,
hand shape or hand motion.

\section{Overview of the Approach}
\label{Wen-sec:overview}
 
A hand gesture is a 
{\em spatiotemporal event}. 
A spatiotemporal event involves an object of interest and the motion of
the object.    
We treat hand sign recognition as a special case of spatiotemporal
understanding.  Our approach is called SHOSLIF (Self-Organizing
Hierarchical Optimal Subspace Learning and Inference Framework)
which as been applied to problems in several different application
domains \cite{Wen-Weng94,Wen-Weng96}.
We model the system at signal level and leave the complex
knowledge-level learning task to the actual real-world training
phase.  As system designers, we minimize modeling knowledge level,
but instead, emphasize modeling the system at signal level and designing
efficient {\em ways} in which the system organizes itself.  The tedious
task of actual organizing the system is accomplished 
automatically by the system itself
through interactive learning.  
 
In this section, we give some general discussion on how to
represent and recognize spatiotemporal events.
 
\subsection{Time as a Dimension}
 
A natural way to represent a spatiotemporal events is
to consider input image sequence as data in space and time
\cite{Wen-Cottrell87,Wen-Elman88} by 
associating the serial
order of the pattern with the dimensionality of the pattern vector.
The first temporal event is represented in the plane 
$t=0$ and the second temporal event by plane $t=1$, and so on. 
The entire spatiotemporal pattern vector is considered as a whole by 
the framework. Figure .~\ref{Wen-FG:tmp_pt} shows an example in which
the hand sign ``no'' is represented by a spatiotemporal sequence (three
images).
 
\begin{figure}[ht]
\centerline{
        \psfig{figure=Weng_figs/no.ps,width=2.0in}
        }
\centerline{
                \makebox[2.0in]{(a)}
                }
\vspace*{0.1in}
\centerline{
        \psfig{figure=Weng_figs/tmp_pt.ps,width=2.8in}
        }
\centerline{
                \makebox[2.0in]{(b)}
                }
\caption{\protect\small
The sign �no� and its image sequence representation:  (a)
the sign of �no�, snap middle finger, index, and thumb together,  (b) the
sequence representation of the sign �no�}
\label{Wen-FG:tmp_pt}
\end{figure}

\subsection{Recognition of Spatiotemporal Pattern}
 
As shown in Figure .~\ref{Wen-FG:tmp_pt}, a spatiotemporal event includes
two kinds of information: the object of interest and the movement
of the object. The movement of the object can be further
decomposed into two components: global and local motions. 
The global motion captures gross motion in terms of position.
The local motion characterizes deformation, orientation, and 
gesture changes. 
In the case of sign language, the hand is the object of interest. 
The position
change of the hand is a global movement and the change of the hand
gesture and orientation is a local movement. 

\begin{figure}[ht]
\centerline{
        \psfig{figure=Weng_figs/frame_idraw.ps,width=3.0in}
        }
\caption{\protect\small
The three-stage framework for spatiotemporal event recognition}
\label{Wen-FG:tmp_reg}
\end{figure}
 
In this chapter, we propose a three stage 
framework for spatiotemporal event recognition, as illustrated in Figure
\ref{Wen-FG:tmp_reg}. The first stage, sequence acquisition, acquires 
image sequences representing the event. This involves motion 
detection and motion-based visual attention.  The start and end of motion 
mark the temporal attention window in which the event occurs. 
We map this temporal window to a standard 
temporal length (e.g., 5) to form what is called 
{\em motion clip}, while the speed information is available from
the mapping performed in this stage.  
In a motion clip, only the temporal dimension is normalized.
 
The second stage is visual attention and object segmentation. This stage
directs the system to focus on the object of interest in the image.
%Given an image, the object of interest may appear anywhere
%in the image with certain size and orientation. Besides the object
%of interest, the image may contain complex background as well.
%Therefore, the first step is to determine where to look, or in other
%words, to select visual attention. 
If we assume that the object
of interest is moving in a stationary environment, it is not difficult to
roughly determine the position of a moving object in the image using motion
information. However, it is
not simple if the task is to extract the contour of the object from various
backgrounds.  Here, we present a prediction-and-verification 
segmentation scheme to locate hands from complex backgrounds. The scheme
uses the past experience to guide the search of the valid segmentation
and is more efficient and effective than other stochastic
approaches such as simulated annealing. 

After stage two, the object of interest in each image of a sequence is
segmented and mapped to a fovea image of a standard fixed size.
Segmented fovea images at different times 
form a standard {\em spatiotemporal fovea 
sequence}, in which both temporal and spatial dimensions are
normalized.  The global motion information of the object of 
interest is placed in a global motion vector, which 
records the size and position 
information of the segmented object in the original image. This
vector is necessary because once the object is segmented and mapped to a
fovea sequence with a standard spatiotemporal size, 
the global motion information is lost. 
 
Let a fovea image $f$ of $m$ rows and $n$ columns be an {\em (mn)}-dimensional vector.For example, 
the set of image pixels
$\{f(i,j)\; |\; 0\leq i < m, 0\leq j < n\}$ can be
written as a vector ${\bf V}=(v_1, v_2, \cdots , v_{d}) $ where
$v_{mi+j} = f(i,j)$ and $d=mn$.
Note that although pixels in an image are lined up to form a 1-D 
vector ${\bf V}$ this way, 2-D neighborhood information between pixels will be 
characterized by the scatter matrix of ${\bf V}$ to be discussed later.
Let $p$ be the standard temporal length and $f_i$ be the hand fovea image 
corresponding to the frame $i$. Then we create a new vector ${\bf X}$, called
the {\em fovea vector}, which is a concatenation of the hand foveas and global
motion vector $G$,
\begin{equation}
{\bf X}=(f_1,f_2,...,f_p,G).
\label{Wen-eq:fovea}
\end{equation}
The third stage
is to recognize the spatiotemporal event
from the fovea vector. 

We focus on the second and third stages in this work. The outline of the
chapter is as follows.  %%%% says as follows, but then nothing follows....?  
 We dedicate the next section to the hand segmentation.
In Section \ref{Wen-sec:recog}, we present our recognition scheme. Experimental
results are presented in Section \ref{Wen-sec:exp}. We end with conclusions and
a brief discussion of the future work.

\section{Hand Segmentation}

A general object segmentation system accepts
an input image ${\bf I}$ and an intention signal ${\bf P}$ which specifies
the type of object that it is looking for
and outputs the segmentation result ${\bf C}=S({\bf I},{\bf P})$. To check
the validation of the segmentation result, we need a verifier $f$.
In order to build such a segmentation system, we need to
answer two questions: 1) how to find ${\bf C}$ and 
2) how to construct $f$.

We present a prediction-and-verification scheme to 
answer the above 
questions. First, we
introduce the concept of {\em valid segmentation} and provide
criteria to evaluate whether a segmentation is valid or not. 
Secondly, we develop a
systematic approach to predict the valid segmentation using 
attention images of
multiple fixations as visual cues. 

\subsection{Valid Segmentation} 

Given an input image,
we can construct an attention image of the hand as shown in 
Figure  \ref{Wen-fig:seg_mapping}.

\begin{figure}[ht]
\centerline{
        \psfig{figure=Weng_figs/seg_mapping_idraw.ps,width=3.8in}
        }
\caption{\protect\small
The illustration of constructing attention images}
\label{Wen-fig:seg_mapping}
\end{figure} 
 
\subsubsection{The Most Expressive Features (MEF)}
\label{Wen-subsubsec:mef}

Let an attention image $F$ of $m$ rows and $n$ columns be an 
{\em (mn)}-dimensional vector.
For example, the set of image pixels
$\{f(i,j)\; |\; 0\leq i < m, 0\leq j < n\}$ can be
written as a vector ${\bf V}=(v_1, v_2, \cdots , v_{d}) $ where
$v_{mi+j} = f(i,j)$ and $d=mn$. Hand attention images in a training set can be considered as samples 
from a  
$d$-dimensional random vector ${\bf X}$. Typically $d$ is very large.
The Karhunen-Loeve projection \cite{Wen-Loeve55} is a very efficient way to 
reduce a high-dimensional space to a low-dimensional subspace.

A {\em d}-dimensional random vector ${\bf X}$ can be
expanded exactly by $d$ orthonormal vectors, ${\bf v}_1,
{\bf v}_2,\cdots,{\bf v}_d$, so that
\begin{equation}
{\bf X}=\sum_{i=1}^{d}y_i{\bf v}_i=V{\bf Y}
\end{equation}
where $V$ is an orthogonal $d\times d$ square matrix consisting
of orthonormal column vectors ${\bf v}_i$. Without loss of
generality, we can assume that the mean of the random vector 
${\bf X}$ is a zero vector, since we can always redefine 
${\bf X}-E{\bf X}$ as the vector to consider. 
The approximate representation is $\hat{{\bf X}}(m)=
\sum_{i=1}^{m}y_i{\bf v}_i$ $(m<d)$. It has been proved \cite{Wen-Loeve55}
that the best unit vectors ${\bf v}_1,{\bf v}_2, \cdots,{\bf v}_m$ that 
minimize 
\begin{equation}
\epsilon^{2}(m)=E\|\delta {\bf X}(m)\|^{2}=E\|{\bf X}-
\hat{{\bf X}}(m)\|^{2}
\end{equation}
are the $m$ unit eigenvectors of the covariance matrix $\Sigma_X$ of 
{\bf X}, associated with the $m$ largest eigenvalues.
 
We can choose $m$
so that the variation ratio $\sum_{i=m+1}^n\lambda_i/\sum_{i=1}^n\lambda_i$ is
smaller than a given percentage (e.g., 5\%).
These $m$ vectors are typically called the principle components.
We call these $m$
vectors $\{ {\bf v}_i \}$ the {\em most expressive features} (MEF) 
in that they best describe the sample population in the sense of linear
transform. For some earlier works on using MEF for recognition-related
problems, the reader is referred to 
Turk \& Pentland 1991 \cite{G-TurkPentland91} and Murase \& Nayar
1995 \cite{G-murase_nayar_95}. 

\subsubsection{Approximation as Function Sampling and Interpolation}

After projecting hand attention images to a low-dimensional MEF space, 
we are now ready to approximate the verifier $f$ using function interpolation.
 
\begin{definition}
Given a training vector ${\bf X}_{k,i}$ of gesture $k$ in the MEF space,
a Gaussian basis function $s_i$ is 
$s_i({\bf X})=e^{-\frac{\|{\bf X}-{\bf X}_{k,i}\|^2}{\sigma}}$,
where $\sigma$
is a positive damping factor, and $\|\cdot\|$ denotes the Euclidean distance.
\end{definition}
 
A very small $\sigma$ tends to reduce the contribution of neighboring
training samples. Gaussian is one of the widely used basis functions 
\cite{Wen-Poggio90}.

\begin{definition}
\label{Wen-def:cf_level} 
Given a set of n training samples
$L_k=\{{\bf X}_{k,1},{\bf X}_{k,2},\cdots,{\bf X}_{k,n}\}$ of gesture $k$, the 
confidence level of the input ${\bf X}$ belongs to class $k$ is
defined as:
$g_k({\bf X})=\sum_{i=1}^nc_is_i({\bf X})$,
where the $s_i$ is a Gaussian basis function and the 
coefficients $c_i$'s are to be determined by
the training samples.
\end{definition}
 
The coefficients $c_i$'s are determined as follows: given $n$ training
samples, we have $n$ equations
\begin{equation}
g_k({\bf X}_{k,i})=\sum_{i=1}^nc_is_i({\bf X}_{k,i}),
\end{equation}
which are linear with respect to the coefficients $c_i$'s.
If we set $g_k({\bf X}_{k,i})$ equal to $1$, we can solve the
above equations for $c_i$ using Gauss-Jordan elimination method 
\cite{Wen-Press86}. 
Figure  \ref{Wen-fig:view_infer} shows how the
interpolation function would look like in the case when two training
samples $(0,0)$ and $(1.4, 1.4)$ are used  and $\sigma=1$.
 
\begin{figure}[ht]
\centerline{
        \psfig{figure=Weng_figs/inter_mesh.eps,width=4.0in}
        }
\vspace{-1.0in}
\caption{\protect\small
Interpolation function with two training samples, 
(0,0) and (1.4,1.4)}
\label{Wen-fig:view_infer}
\end{figure} 
 
The confidence level defined in Definition \ref{Wen-def:cf_level} can be used to
verify a segmentation result. 
 
\begin{definition}
Given a segmentation result ${\bf S}$ and a confidence level $l$, the
verifier $f$ outputs valid segmentation for gesture $k$ if 
$g_k({\bf S})>l$.
\end{definition}
 
Intuitively, 
a segmentation result ${\bf S}$ is valid if there is a training sample
that is sufficiently close to it.

\subsection{Predication for Valid Segmentation}

This section investigates the problem how to find a valid segmentation.
Our approach is to use the attention images from multiple
fixations of training hand images. Given a hand attention image, an attention 
of a fixation is determined by its fixation position $(s,t)$ and a scale
$r$. Fig. \ref{Wen-fig:fixa} shows the attention images of
the $19$ fixations from one training sample. The scales $s$ and 
positions $(s,t)$ of these
$19$ fixations for an image with $m$ rows and $n$ columns are listed in
Table \ref{Wen-TB:fix}. 
\begin{table}[thb]
\begin{center}
\caption{The list of fixation scale and position}
\label{Wen-TB:fix}
\begin{tabular}{||c|c|c|c|c||}                        \hline
Scale & 1.0 & 0.75 & 0.5 & 0.33 \\ \hline
P1 & $(\frac{m}{2},\frac{n}{2})$ & $(\frac{m}{2},\frac{n}{2})$ & 
$(\frac{m}{2},\frac{n}{2})$ & \\ \hline
P2 & & & $(\frac{m}{3},\frac{n}{3})$ & $(\frac{m}{3},\frac{n}{3})$ \\ \hline
P3 & & & $(\frac{m}{3},\frac{n}{2})$ & $(\frac{m}{3},\frac{n}{2})$ \\ \hline
P4 & & & $(\frac{m}{3},\frac{2n}{3})$ & $(\frac{m}{3},\frac{2n}{3})$ \\ \hline
P5 & & & $(\frac{m}{2},\frac{n}{3})$ & $(\frac{m}{2},\frac{n}{3})$ \\ \hline
P6 & & & $(\frac{m}{2},\frac{2n}{3})$ & $(\frac{m}{2},\frac{2n}{3})$ \\ \hline
P7 & & & $(\frac{2m}{3},\frac{n}{3})$ & $(\frac{2m}{3},\frac{n}{3})$ \\ \hline
P8 & & & $(\frac{2m}{3},\frac{n}{2})$ & $(\frac{2m}{3},\frac{n}{2})$ \\ \hline
P9 & & & $(\frac{2m}{3},\frac{2n}{3})$ & $(\frac{2m}{3},\frac{2n}{3})$ \\ \hline

\end{tabular}
\end{center}
\end{table} 

\begin{figure}[tbhp]
\centerline{ 
\psfig{figure=Weng_figs/a_seg_cute1_1_0_100.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_0_075.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_0_050.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_1_033.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_1_050.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_2_033.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_2_050.ps,width=0.500000in}
}
\centerline{
\psfig{figure=Weng_figs/a_seg_cute1_1_3_033.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_3_050.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_4_033.ps,width=0.500000in}
\hspace*{-0.08in} 
\psfig{figure=Weng_figs/a_seg_cute1_1_4_050.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_5_033.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_5_050.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_6_033.ps,width=0.500000in}
}
\centerline{
\psfig{figure=Weng_figs/a_seg_cute1_1_6_050.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_7_033.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_7_050.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_8_033.ps,width=0.500000in}
\hspace*{-0.08in}
\psfig{figure=Weng_figs/a_seg_cute1_1_8_050.ps,width=0.500000in}
\hspace*{-0.08in}
}
\caption{The attention images from 19 fixations of a 
training sample. The first one is the same as the original hand
attention image.}
\label{Wen-fig:fixa}
\end{figure}

\subsubsection{Overview}
 
Given a training set $L=\{{\bf I}_1,{\bf I}_2,\cdots,{\bf I}_n\}$, where
${\bf I}_i$ is a training hand attention image, we obtain a set of attention 
images
from multiple fixations for each ${\bf I}_i$. We denote ${\bf F}_{i,j}$ be
an attention image from $j$th fixation of sample $i$ in $L$. 
The attention
images from the training set $L_{{\bf F}}$ is 
\[
L_{{\bf F}}=\{{\bf F}_{1,1},\cdots,{\bf F}_{1,m_1},
{\bf F}_{2,1},\cdots,{\bf F}_{1,m_2},\cdots,
{\bf F}_{n,1},\cdots,{\bf F}_{n,m_n}\},
\]
where $m_i$ is the number of the attention images generated from the training
image ${\bf I}_i$.
Each attention image from a fixation is associated with the segmentation mask
of original hand attention image, the scale $r$ and 
the position of the fixation $(s,t)$.
These information is necessary
to recover the segmentation for the entire object.
 
During the segmentation stage, we first use the motion information to select
visual attention. Then, we try different fixations on the 
input image. An attention image from a fixation of an input image is used
to query the training set $L_{{\bf F}}$. The segmentation mask
associated with the query result ${\bf F}_{i,j}$ is the predication. 
The predicted segmentation mask
is then applied to the input image. 
Finally, we verify the 
segmentation result to see if the extracted subimage corresponds to a hand
gesture that has been learned. If the answer is yes, we find the solution. This
solution can further go through a refinement process. 
Figure  \ref{Wen-fig:overview} gives the outline of the scheme.
 
\begin{figure}[ht]
\centerline{
        \psfig{figure=Weng_figs/overview_idraw.ps,width=4.2in}
        }
\caption{\protect\small
Overview of the segmentation scheme}
\label{Wen-fig:overview}
\end{figure} 

\subsubsection{Organization of Attention Images from Fixations}
 
Our objective is to achieve a retrieval with time complexity $O(\log n)$ for
a learning set of size $n$. With this goal in mind, we build a 
hierarchical structure to organize the data.
 
\begin{definition}
Given a set of points $V=\{V_1,V_2,\cdots,V_n\}$ in the
space $S$, the {\em Voronoi diagram} partitions $S$ into
$R=\{R_1,R_2,\cdots,R_n\}$ regions, where $R_i\cap R_j=0$ when $i\neq j$, 
$\bigcup_{i=1}^nR_i=S$, and for any $x\in S$, $x\in R_i$ if and only if 
$\|x-V_i\|<\|x-V_j\|$ for any $j\neq i$. We denote $V_i$ be the center of the
region $R_i$.
\end{definition}

\begin{definition}
A {\em hierarchical quasi-Voronoi diagram} $P$ of $S$ is a set
of partitions $P=\{P_1,P_2,\cdots,P_m\}$, where every 
$P_i=\{P_{i,1},\cdots,P_{i,n_i}\}$, $i=1,2,\cdots,m$ 
is 
a partition of $S$. 
$P_{i+1}=\{P_{i+1,1},\cdots,P_{i+1,n_{i+1}}\}$ is a finer 
Voronoi diagram partition of $P_i$
in the sense that corresponding to every element 
$P_{i,k}\in P_i$,
$P_{i+1}$ contains a Voronoi partition 
$\{P_{i+1,s},\cdots,P_{i+1,t}\}$ of $P_{i,k}$. 
\end{definition} 

\begin{figure}[ht]
\centerline{
   \psfig{figure=Weng_figs/space_parti_la.ps,width=2.1in}
   \hspace*{0.1in}
   \psfig{figure=Weng_figs/space_part_tree.ps,width=2.1in}
   }
\centerline{
   \makebox[3.0in]{(a)}
   \makebox[3.0in]{(b)}
   }
\caption{\protect\small
A 2-D illustration of a hierarchical quasi-Voronoi diagram and the 
corresponding recursive partition tree,  (a) The partition, where the
label indicates the center of a cell  (the label of the child to which its
parent's center belongs is not shown due to the lack of space), and  (b)
the corresponding recursive partition tree}
\label{Wen-FG:sp_part}
\end{figure}

The graphic description in Figure \ref{Wen-FG:sp_part}
gives an simplified but intuitive explanation of the hierarchical 
quasi-Voronoi 
diagram.  The structure is a tree. The root corresponds to the 
entire space of all the 
possible inputs.  The children of the root partition the 
space into large cells, as shown by thick lines in 
Figure  \ref{Wen-FG:sp_part}. The children of a parent subdivide the
parent's cell future into smaller cells, and so on. 
 
\subsubsection{Prediction as Querying the Training Set}
\label{Wen-subsubsec:qvd}
 
Given a training set $L$,
a hierarchical quasi-Voronoi diagram $P=\{P_1,P_2,\cdots,P_n\}$
corresponding to $L$ and a query sample ${\bf X}$, the prediction problem
is to find a training sample ${\bf X}'\in L$, such that 
$\|{\bf X}-{\bf X}'\|\leq \|{\bf X}-{\bf X}''\|$ for any
${\bf X}''\in L$ with ${\bf X}''\neq {\bf X}'$. 
 
The type of query mentioned above is a nearest neighbor problem,
also known as {\em post-office} problem \cite{Wen-Knuth73}.
The nearest neighbor problem has been 
studied extensively in the past. There are efficient query algorithms
$O(\log n)$ for two- or three- dimensional cases \cite{Wen-Chazelle85,Wen-Dobkin76}.
However, there still lacks of efficient solutions for the case with
dimension higher than three. 
$k$-d tree based nearest neighbor algorithms have been widely used
in computer vision \cite{Wen-Besl92,Wen-Zhang94}. $k$-d trees are extremely 
versatile and efficient to use in low dimensions. However, the
performance degrades exponentially in high dimensions. 
R-tree and its variants \cite{Wen-Guttman84,Wen-Sellis87,Wen-Beckmann90,Wen-Breiman93} have 
similar performance problem in nearest neighbor search for high dimensions.
In this 
section, we will present an efficient algorithm when the training set is 
$d$-supportive as defined below. 
 
\begin{definition}
Let $S$ be a set which contains all possible samples.
A training set $L=\{L_1,L_2,\cdots,L_n\}$
is a $d$-supportive training set if for any test sample ${\bf X}\in S$, there
exist $i$ such that $\|{\bf X}-L_i\|<d$, where $\|\cdot\|$ is the Euclidean
distance.
\end{definition}
 
Next two theorems show the fact that if the
training set is $d$-supportive, we have an efficient query algorithm.
 
\begin{theorem}
\label{Wen-TM:nn1}
We have a set of $d$-supportive training set
$L=\{L_1,L_2,\cdots,L_n\}$, 
a hierarchical quasi-Voronoi diagram $P=\{P_1,P_2,\cdots,P_n\}$
corresponding to $L$ and a query sample ${\bf X}\in S$. Let the $i$th
partition
be $P_i=\{P_{i,1},P_{i,2},\cdots,P_{i,n_i}\}$ and $C=\{C_1,C_2,\cdots,
C_{n_i}\}$ 
be the
corresponding centers of regions in $P_i$. Assume $C_1$ be the center to 
${\bf X}$ such that $\|C_1-{\bf X}\|\leq \|C_i-{\bf X}\|$ for any $i\neq 1$. 
Let $C_2$ be any other center and $P_1$ be a boundary hyperplane between 
regions 
represented by $C_1$ and $C_2$ as illustrated in Fig. \ref{Wen-FG:search}. 
Then the region
of $C_2$ does not contain the nearest training sample to ${\bf X}$ if the 
distance
between ${\bf X}$ and the hyperplane $P_1$ is greater than $d$.
\end{theorem}

\begin{figure}[ht]
\centerline{\psfig{figure=Weng_figs/pami_search.ps,width=3.8in}}
\caption{\protect\small
 A 2D illustration of nearest neighbor query theorems\}
\label{Wen-FG:search}
\end{figure}
 
In order to avoid to calculate the point to hyperplane distance in a high
dimensional space, we can use following equivalent theorem.
 
\begin{theorem}
\label{Wen-TM:nn2}
Let $\|C_1-C_2\|=r$, $f=\frac{r}{2}$, 
$e=\frac{r}{2}-d$, $\|C_1-{\bf X}\|=a$ and $\|C_2-{\bf X}\|=b$ as shown
in Fig. \ref{Wen-FG:search}. The region
of $C_2$ does not contain the nearest training sample to ${\bf X}$ if
$a^2-e^2<b^2-f^2$.
\end{theorem}
 
The proofs of Theorem \ref{Wen-TM:nn1} and \ref{Wen-TM:nn2} are regulated in
the Appendix A and B. Now we are
ready to present our query algorithm. 
 
\noindent
\begin{center}
\fbox{
\begin{minipage}[t]{6.5in}
\begin{tabbing}
\ \ \ \=\ \ \ \=\ \ \ \=\ \ \ \=\ \ \ \=\ \ \ \=\\
Given query sample ${\bf X}$, a hierarchical \\
quasi-Voronoi 
diagram $P$ corresponding 
to \\
a $d$-supportive 
learning set with $C_{i,j}$ denotes to 
the center\\
of the partition region $P_{i,j}$.\\
{\bf begin}\\
\>$nodes\_list=root$;\\
\>{\bf while} $nodes\_list$ $\neq$ {\bf nil} {\bf do}\\
\>\>Pop the first node $nd$ from $nodes\_list$;\\
\>\>{\bf if} $nd$ is leaf {\bf then}\\
\>\>\>add center $C_{nd}$ to the $center\_list$;\\
\>\>{\bf else}\\
\>\>\>{\bf for} regions under the node $nd$ {\bf do}\\
\>\>\>\>Add region which is closest ${\bf X}$ to $nodes\_list$; \\
\>\>\>\>Add regions which satisfy Theorem 3 to $nodes\_list$; \\
\>\>\>{\bf end for}\\
\>\>{\bf end if}\\
\>{\bf end while}\\
\>Output the center in the $center\_list$ that
minimizes 
$\|{\bf X}-C\|$.\\
{\bf end begin}\\
\end{tabbing}
\end{minipage}
}
\end{center}
\vspace{0.6cm}

The above algorithm has the average time complexity of 
$O(\log n)$ where $n$ is the size of the training set. The proof
of the time complexity is shown in \cite{Wen-Cui95d}.

\section{Hand Sign Recognition}
\label{Wen-sec:recog}

As we mentioned in Section \ref{Wen-sec:overview}, after the segmentation,
the object of interest in each image of a sequence is
segmented and mapped to a fovea image of a standard fixed size.
These fovea images in a sequence and the global motion vector
form a fovea vector.

An automatic hand gesture recognition system accepts an input fovea vector
${\bf X}$ and outputs the recognition result ${\bf C}$ which classifies the
${\bf X}$ into one of the gestures. Thus, a recognition system can be denoted
by a function $f$ that maps elements in the space of ${\bf X}$ to elements in
the space of ${\bf C}$. Our objective of constructing a recognition system 
is equivalent
to approximating function $f:S\mapsto C$ by another function 
$\hat{f}:S\mapsto C$.
The error of a approximation can be indicated by certain measure of the error
$\hat{f}-f$. One such measure is the mean square error:
\[
E(\hat{f}-f)=\int_{X\in S}(\hat{f}({\bf X})-f({\bf X}))^2dF({\bf X})
\]
where $F({\bf X})$ is the probability distribution function ${\bf X}$ in $S$. In other
words, $\hat{f}$ can defer a lot from $f$ in parts where ${\bf X}$ never 
occurs, 
without affecting the error measure. Another measure is the pointwise 
absolute error
$\|\hat{f}({\bf X})-f({\bf X})\|$ for any point ${\bf X}$ in $S'$, 
where $S'\subset S$
is a subset of $S$ that is of interest to a certain problem.
 
Of course, $f$ is typically high-dimensional and highly complex. A powerful 
method
of constructing $\hat{f}$ is using learning. Specifically, a series of cases is
acquired as the learning data set:
\[
L=\{({\bf X}_i,f({\bf X}_i))|i=1,2,\cdots,n\}.
\]
Then, construct $\hat{f}$ based on $L$. For notational convenience, the sample
points in $L$ is denoted by $X(L)$:
\begin{equation}
X(L)=\{{\bf X}_i|i=1,2,\cdots,n\}.
\label{Wen-eq:l_set}
\end{equation}
$X(L)$ should be drawn from the real situation so that the underlying 
distribution
of $X(L)$ is as close to the real distribution as possible. 
 
We propose a recursive partition tree in the most discriminating feature
(MDF) space to approximate the function $f$.

\subsection{The Most Discriminating Features (MDF)}

In Section \ref{Wen-subsubsec:mef}, we illustrated that using Karhunen-Loeve
projection we can reduce a very high dimensional image space to a lower
dimensional MEF space. One way to approximate $f$ is to use
the nearest neighbor approximator \cite{G-murase_nayar_95,G-TurkPentland91}. However,
the MEF's are, in general, not the best ones for classification, 
because the features that describe some major variations in the
class are typically irrelevant to how the subclasses are divided as 
illustrated in Figure  \ref{Wen-FG:mdf}.
 
\begin{figure}[ht]
\centerline{\psfig{figure=Weng_figs/mdf_idraw.ps,width=3.0in}}
\caption{\protect\small
 A 2D illustration of the most discriminating features (MDF).
The MDF is projection along $z_1$. The MEF along $y_1$ can not
separate the two subclasses.}
\label{Wen-FG:mdf}
\end{figure}
 
In this work, multiclass, multivariate 
discriminant analysis \cite{Wen-Wilks63} is used to select
the MDF's. It is a generalization of Fisher's linear discriminant
\cite{G-Duda73}. Suppose samples of {\bf Y} are {\em m}-dimensional
random vectors from $c$ classes. The {\em i}th class has a probability
$p_i$, a mean vector ${\bf m}_i$ and a scatter matrix $\Sigma_i$. The
{\em within-class scatter matrix} is defined by
\begin{equation}
S_w=\sum_{i=1}^{c}p_iE\{({\bf Y} - {\bf m}_i)({\bf Y} - {\bf 
m}_i)^t|\omega_i\}=\sum_{i=1}^cp_i\Sigma_i.
\end{equation}
The {\em between-class scatter matrix} is 
\begin{equation}
S_b=\sum_{i=1}^{c}p_i({\bf m}_i-{\bf m})({\bf m}_i-{\bf m})^t,
\end{equation}
where the grand mean {\bf m} is defined as 
${\bf m}=E{\bf Y}=\sum_{i=1}^cp_iM_i$.
The {\em mixture scatter matrix} is the covariance matrix of all
the samples regardless of their class assignments:
\begin{equation}
S_m=E\{({\bf (Y-m)(Y-m)}^t\}=S_w+S_b.
\end{equation}

Suppose we use {\em k}-dimensional linear features ${\bf Z}=W^t{\bf Y}$ where
$W$ is an $m\times k$ rectangular matrix whose column vectors are
linearly independent. The above mapping represents a linear projection
from {\em m}-dimensional space to {\em k}-dimensional space. The samples
${\bf Y}_1,{\bf Y}_2,\cdots,{\bf Y}_n$ project to a corresponding set of samples
${\bf Z}_1, {\bf Z}_2,\cdots,{\bf Z}_n$ 
whose within-class scatter, and between-class scatter 
matrices are ${S}_{Z_w} $ and ${S}_{Z_b} $, respectively. 
It is straightforward matter to show that
\begin{eqnarray}
{S}_{Z_w}=W^tS_wW \\
{S}_{Z_b}=W^tS_bW.
\end{eqnarray}
These equations show how the within-class and between-class scatter
matrices are transformed by the projection to the lower dimensional space.
What we seek is a transformation matrix $W$ that maximizes in some sense the
ratio of the between-class scatter to the within-class scatter. A
simple scalar measure of scatter is the determinant of the scatter matrix.
The determinant is the product of the eigenvalues, and hence is the 
product of the �variances�  in the principal directions, thereby
measuring the square of the hyperellipsoidal scattering volume. Using
this measure, we obtain the criterion function to maximize
\begin{equation}
J(W)=\frac{|W^tS_{b}W|}{|W^tS_{w}W|}.
\end{equation}
It can be proved \cite{Wen-Wilks63} that the optimal $W$ that maximizes the 
above function are the
generalized eigenvectors that correspond to the largest eigenvalues in
\begin{equation}
S_b{\bf w}_i=\lambda_iS_w{\bf w}_i.
\end{equation}
In order to avoid compute the inverse of $S_w$, we can find the
eigenvalues as the roots of the characteristic polynomial
\begin{equation}
|S_b-\lambda_iS_w|=0
\end{equation}
and then solve
\begin{equation}
(S_b-\lambda_iS_w){\bf w}_i=0
\end{equation}
directly for the eigenvectors ${\bf w}_i$. 
Since the rank of $S_b$ is at most $c-1$, we know that only 
at most $c-1$ features $\{ {\bf w}_i \}$ 
are needed and we call these features the
most discriminating features (MDFs).
 
\subsection{Recursive Partition Tree}
\label{Wen-subsec:RPT}

For large number of classes, the overall feature set may not be best
for specific pairs of classes. An alternative classification scheme
is the hierarchical classifier, where the most obvious discriminations 
are done first, postponing the more subtle distinctions to a later
stage \cite{Wen-Mui80,Wen-Sethi82}. Here, we present a recursive 
partition tree approximator in the MDF space. Unlike many other
tree classifiers which have a fixed set of features, our
feature set is adaptive. In the tree, each node is represented by a training
sample and the related subregion and the samples under the subregion are used
to generate the features. The graphic description in Figure 
\ref{Wen-FG:recog_sp_part} gives an simplified but intuitive explanation of the
recursive partition tree. 
\begin{figure}[htb]
\centerline{
   \psfig{figure=Weng_figs/part_tree_idraw.ps,width=2.0in}
   \hspace{-0.1in}
   \psfig{figure=Weng_figs/part_tree_1_idraw.ps,width=2.0in}
   }
\caption{\protect\small
A 2-D illustration of a recursive partition tree. The samples surrounded
by circles
or rectangulars are the centers of the subregions. 
Left: the partition. Right:
the corresponding recursive partition tree.}
\label{Wen-FG:recog_sp_part}
\end{figure}
The leaves of the partition tree correspond to 
the regions which contain
the training samples from a single class. 
The approximator uses the following decision rule to classify the query 
fovea vector ${\bf X}$ to the
class of a leaf cell.

\begin{definition}
Given a training set of fovea vectors $L=\{F_1,F_2,\cdots,F_n\}$ and
corresponding recursive partition tree, for any query fovea vector 
${\bf X}$, if the current level is not a leaf, the recursive partition tree
approximator (RPTA) selects the cell with center $C_i$ if
for any other cell with center $C_j$, we
have $R_d({\bf X},C_i)<R_d({\bf X},C_j)$. If the current level is a leaf
node, RPTA designates the label of the leaf to the query ${\bf X}$.
\end{definition}
 
Since each local cell has its own projection, in order to logically
compare between two different cells, we use a measurement called
mixture distance (MD). 
 
\begin{definition}
Let $C$ be the center of the region $P$, $V$ be the projection matrix to the 
MEF space and $W$ be the projection matrix to the MDF space. The mixture 
distance, $R_d({\bf X},C)$ from a query ${\bf X}$
fovea vector of the center $C$ is defined as follows.
\[
\sqrt{\|{\bf X}-VV^t{\bf X}\|^2+
\|VWW^tV^tC-VWW^tV^t{\bf X}\|^2}
\]
\end{definition}

Intuitively, what is being measured can be seen in Figure \ref{Wen-fig:MD}. In 
Figure  \ref{Wen-fig:MD}, the original image space is a 3D space, the MEF space
is a 2D 
subspace, and the MDF space is 1D subspace since two classes are well 
separated along the first MDF vector. 
%and we assume the mean vector is a zero vector
%since we can always redefine ${\bf F}-E{\bf F}$ as the vector to consider. 
The first term under the radical indicates the
distance of the original vector from the population which indicates
how well the MEF subspace represents the query vector ${\bf X}$. This
term is necessary since it is entirely possible that a query vector
that is miles away from a particular subregion's MEF subspace would
project very near to the region's center. The second term indicates the
distance between the MDF components of the query vector and 
the MDF components of the center vector in the original image  
space.
\begin{figure}[ht]
\centerline{
   \psfig{figure=Weng_figs/MD_idraw.ps,width=3.3in}
}
\caption{\protect\small
{Illustration of components in the mixture distance in a 3D original space}
\label{Wen-fig:MD}
\end{figure}

\section{Convergence of the Approximators}
 
An important issue to study here is how well the above approximators can
approximate a function $f$. Its answer is closely related to the way samples 
are generated for the learning set $L$. In \cite{Wen-Weng95a}, Weng and Chen 
have shown that the nearest neighbor 
approximator approaches $f$ {\em pointwise} in probability. In this section,
we are going to show that the same result also holds for the
recursive partition tree approximator.
 
Due to a high complexity and 
undetermined nature
of the way in which a learning set $L$ is drawn from the real world, it is 
effective to consider that $X(L)$, the set of samples in $S$, is generated 
randomly.
We know that a fixed $L$ is a special case of random $L$ in that the 
probability distribution is concentrate at the single location.
Thus, we consider ${\bf X}$ in $X(L)$ as a random sample from $S$. The 
learning set
$L$ is generated by acquiring samples from $S$ with a $d$-dimensional 
probability
distribution function $F({\bf X})$.
 
\begin{definition} A point ${\bf X}_0 \in S$ is positively supported
if for any $\delta>0$ we have $P\{\|{\bf X}-{\bf X}_0\|\leq\delta\}>0$, where
$P\{e\}$ denotes the probability of the event $e$. 
\end{definition}
 
If $S$ consists of a finite number of discrete points, a point ${\bf X}$ in 
$P$ is
positively supported means that the probability of selecting ${\bf X}$ as a
sample is not a zero-probability event. If $S$ consists of infinitely many 
points,
a point ${\bf X}$ in $P$ is positively supported means that in any small 
neighborhood centered at ${\bf X}$, the probability of selecting any point in
the neighborhood is not a zero-probability event. In practice, we are not
interested in cases that almost never appears in a real-world application. An
approximate function $\hat{f}$ can assume any value in subregions of $S$ that
will never be used in the application, without hurting the real performance 
of the system. Thus, we just need to investigate how well the approximation 
can do at points ${\bf X}$'s that are positively supported.
 
\begin{definition}
A point ${\bf X}_0 \in S$ is an interior point 
of a region $f({\bf X})=D$ if there is a $\delta >0$
such that for any ${\bf X}$ we have $f({\bf X}_0)=f({\bf X})=D$, where
$\|{\bf X}_0-{\bf X}\|<\delta $.
\end{definition}

For a classification problem, we have a set of discrete number of 
categories to be assigned to the input. Then, $f({\bf X})$ is 
continuous only at the interior points.
 
\begin{theorem}
\label{Wen-TM:converge}
Suppose the query vector ${\bf X}$ is an interior and
positively supported point in 
a bounded $S$. Let $n$ be the size of a training set $L$.
Given any small number $\epsilon>0$, there is a number $N$, so that
as long as we independently draw $n>N$ learning samples, the 
recursive partition tree approximator $\hat{f}$ has the following property
\[
P\{\hat{f}({\bf X})\neq f({\bf X})\}<\epsilon,
\]
where $\hat{f}'$ the approximator based on the 
recursive partition tree.
\end{theorem}
The proof is presented in Appendix C. Theorem \ref{Wen-TM:converge} means
that the RPTA approaches $f$ {\em pointwisely} in probability:
$P\{\hat{f}({\bf X})\neq f({\bf X})\}\rightarrow 0$, as the size
of training set $L$ increases without bound. 

\section{Experimental Results}
\label{Wen-sec:exp}

The framework has been applied to recognize the 
twenty eight different signs as illustrated in the Figure \ref{Wen-FG:sign_pict}. 
The image sequences are obtained while subjects perform hand
signs in front of a video camera. The variation of hand size in images
is limited. Two different lighting conditions are used.
In the current implementation, each hand sign was represented by five images 
sampled from the video. 
Figure .~\ref{Wen-FG:sam_seq} shows several examples of these sequences.

\begin{figure}[tbp]
 
\centerline{
        \psfig{figure=Weng_figs/sn_happy2_1.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_happy2_2.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_happy2_3.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_happy2_4.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_happy2_5.ps,width=2.1cm}
        }
\vspace*{0.01in}
\centerline{
        \psfig{figure=Weng_figs/hot1_1.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/hot1_2.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/hot1_3.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/hot1_4.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/hot1_5.ps,width=2.1cm}
        }
\vspace*{0.01in}
\centerline{
        \psfig{figure=Weng_figs/nothing_doug2_1.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/nothing_doug2_2.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/nothing_doug2_3.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/nothing_doug2_4.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/nothing_doug2_5.ps,width=2.1cm}
        }
\vspace*{0.01in}
\centerline{
        \psfig{figure=Weng_figs/sn_parent6_1.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_parent6_2.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_parent6_3.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_parent6_4.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_parent6_5.ps,width=2.1cm}
        }
\vspace*{0.01in}
\centerline{
        \psfig{figure=Weng_figs/sn_pepper2_1.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_pepper2_2.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_pepper2_3.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_pepper2_4.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_pepper2_5.ps,width=2.1cm}
        }
\vspace*{0.01in}
\centerline{
        \psfig{figure=Weng_figs/sn_smart2_1.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_smart2_2.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_smart2_3.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_smart2_4.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_smart2_5.ps,width=2.1cm}
        }
\vspace*{0.01in}
\centerline{
        \psfig{figure=Weng_figs/welcome_val1_1.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/welcome_val1_2.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/welcome_val1_3.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/welcome_val1_4.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/welcome_val1_5.ps,width=2.1cm}
        }
\vspace*{0.01in}
\centerline{
        \psfig{figure=Weng_figs/sn_yes6_1.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_yes6_2.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_yes6_3.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_yes6_4.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sn_yes6_5.ps,width=2.1cm}
        }
\caption{\protect\small
Eight sample sequences: from top to bottum, they represent the signs
�happy�, �hot�, �nothing�, �parent�,  �pepper�,  �smart�, �welcome�, and �yes�.}
\label{Wen-FG:sam_seq}
\end{figure}

\subsection{Hand Segmentation}

Two types of training were conducted in the experiments. The first type
of training is to get the approximation for verifier
$f$ which would be used later to check the validation of the segmentation.
For each gesture, a number between ($27$ and $36$) of training samples
were used to obtained the approximation of the verifier
$f$ for that gesture. Figure  \ref{Wen-fig:gest} shows 
a representative subset of hand shapes learned by the system.
Given a set of training
samples $L=\{l_1,l_2,\cdots,l_n\}$ for gesture $k$,
we empirically determined the damping factor
$\sigma$ in the interpolation function as follows:
\begin{equation}
\sigma=\frac{0.2\sum_{i=1}^{n-1}\|{\bf X}_{i}-{\bf X}_{i+1}\|}{n-1},
\end{equation}
where ${\bf X}_i$ is a projection of a training sample in the MEF
space.

\begin{figure}[tbhp]
\centerline{ 
\psfig{figure=Weng_figs/ext_seg_angry1_4.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_any1_2.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_any1_3.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_any1_4.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_boy1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_cute1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_cute1_4.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_fine1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_happy1_4.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_hi1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
}
\centerline{ 
\psfig{figure=Weng_figs/ext_seg_hi1_4.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_high1_3.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_hot1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_hot1_2.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_hot1_4.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_later1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_later1_2.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_later1_4.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_low1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_no1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
}
\centerline{ 
\psfig{figure=Weng_figs/ext_seg_no1_3.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_no1_4.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_nothing1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_nothing1_2.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_ofcourse1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_ofcourse1_4.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_parent1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_parent1_4.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_pepper1_4.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_smart1_4.ps,width=1.000cm}
\hspace*{-1.5mm}
}
\centerline{ 
\psfig{figure=Weng_figs/ext_seg_sour1_3.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_strange1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_sweet1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_sweet1_3.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_thankyou1_3.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_thankyou1_4.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_thirsty1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_welcome1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_wrong1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
\psfig{figure=Weng_figs/ext_seg_yes1_1.ps,width=1.000cm}
\hspace*{-1.5mm}
}
\caption{\protect\small
A representative subset of hand shapes learned by the system}
\label{Wen-fig:gest}
\end{figure}

The second type of training was to generate the attention images from 
multiple fixations of training samples. In the current implementation,
the selection of the fixations is mechanical. Totally $19$ 
fixations were used
for each training sample as illustrated in Figure  \ref{Wen-fig:fixa}.

In order to speed up the process of the segmentation, we utilize motion
information to find a motion attention window. The attention
algorithm can detect the rough position of a moving object, 
but the accuracy is not guaranteed. We solve this problem by doing 
some limited search based on the motion attention window.
In the current implementation, given a motion attention window 
with $m$ rows and
$n$ columns, we try the candidates with size from $(0.5m,0.5n)$ to $(2m,2n)$ 
using step size $(0.5m,0.5n)$.

We tested the system with 802 images (161 sequences) which were not 
used in the training. A result was rejected if the system could not find
a valid segmentation with a confidence level $l$. The segmentation was 
considered
as a correct one if the correct gesture segmentation ${\bf C}$ was 
retrieved and
placed in the right position of the test image. 
For the case of $l=0.2$, we have achieved 95\% correct segmentation rate
with 3\% false rejection rate. The results are summarized in 
Table \ref{Wen-TB:seg}.
The time was obtained on a SGI INDIGO 2 (MIPS 4400 and clock 150 MHz)
workstation. Figure  \ref{Wen-fig:seg_rslt} shows some 
segmentation results.

\begin{table}[thb]
\begin{center}
\caption{Summary of the segmentation results}
\label{Wen-TB:seg}
\begin{tabular}{||l||l|l|l|l||}                        \hline
\multicolumn{1}{||c||} {\em Training } &\multicolumn{4}{c||} 
{\em Testing  } \\ \hline
Number of & Number of & Correct  & False & Time \\
fixation images & test images  & segmentation & rejection & per image \\ \hline
1742 & 805 & 95\% & 3\% & 58.3 sec.\\ \hline
 
\end{tabular}
\end{center}
\end{table} 

\begin{figure}[tbhp]
\centerline{
        \psfig{figure=Weng_figs/sout_sn_parent6_1.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_parent6_2.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_parent6_3.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_parent6_4.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_parent6_5.ps,width=2.1cm}
        }
\vspace*{0.01in}
\centerline{
        \psfig{figure=Weng_figs/sout_sn_pepper2_1.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_pepper2_2.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_pepper2_3.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_pepper2_4.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_pepper2_5.ps,width=2.1cm}
        }
\vspace*{0.01in}
\centerline{
        \psfig{figure=Weng_figs/sout_sn_smart2_1.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_smart2_2.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_smart2_3.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_smart2_4.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_smart2_5.ps,width=2.1cm}
        }
\vspace*{0.01in}
\centerline{
        \psfig{figure=Weng_figs/sout_sn_yes6_1.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_yes6_2.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_yes6_3.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_yes6_4.ps,width=2.1cm}
        \hspace*{-1.0mm}
        \psfig{figure=Weng_figs/sout_sn_yes6_5.ps,width=2.1cm}
        }
 
\caption{\protect\small
The results of the segmentation are shown after masking off the background}
\label{Wen-fig:seg_rslt}
\end{figure}
 
\subsection{Recognition of Hand Sign}
 
The segmentation result was used as the input for sign recognition. The 
problem is 
now how to deal with the sequences which has some images that
have been rejected by the segmentation routine. In this case, we still output
those sequences because there are still good chances that they can be
recognized if only one or two images in the sequences are rejected while
the rest of them are fine. The number of images used in the training
is 3300 (660 sequences). The number of testing images is 805 
(161 sequences).
 
\subsubsection{Results of the Nearest Neighbor Approximator in the
MEF space}
 
\begin{figure}[ht]
\centerline{
   \psfig{figure=Weng_figs/mef_recog.ps,width=4.0in}
}
\caption{\protect\small
Performance of the nearest neighbor approximator in the MEF space.
The performance is given as a function of the number of MEF's used.}
\label{Wen-FG:rate_mef}
\end{figure}
 
We show some experimental results to indicate the performance of
the nearest neighbor approximator in the
MEF space. We computed MEF's using 660 training sequences. 
Figure \ref{Wen-FG:mefs} shows top 10 MEF's. 
 
\begin{figure}[ht]
\centerline{
\psfig{figure=Weng_figs/mef_0.ps,width=2.1in}
\hspace*{0.0in}
\psfig{figure=Weng_figs/mef_1.ps,width=2.1in}
}
\centerline{
\makebox[2.1in]{(MEF 1)}
\hspace*{0.0in}
\makebox[2.1in]{(MEF 2)}
}
\centerline{
\psfig{figure=Weng_figs/mef_2.ps,width=2.1in}
\hspace*{0.0in}
\psfig{figure=Weng_figs/mef_3.ps,width=2.1in}
}
\centerline{
\makebox[2.1in]{(MEF 3)}
\hspace*{0.0in}
\makebox[2.1in]{(MEF 4)}
}
\centerline{
\psfig{figure=Weng_figs/mef_4.ps,width=2.1in}
\hspace*{0.0in}
\psfig{figure=Weng_figs/mef_5.ps,width=2.1in}
}
\centerline{
\makebox[2.1in]{(MEF 5)}
\hspace*{0.0in}
\makebox[2.1in]{(MEF 6)}
}
\centerline{
\psfig{figure=Weng_figs/mef_6.ps,width=2.1in}
\hspace*{0.0in}
\psfig{figure=Weng_figs/mef_7.ps,width=2.1in}
}
\centerline{
\makebox[2.1in]{(MEF 7)}
\hspace*{0.0in}
\makebox[2.1in]{(MEF 8)}
}
\centerline{
\psfig{figure=Weng_figs/mef_8.ps,width=2.1in}
\hspace*{0.0in}
\psfig{figure=Weng_figs/mef_9.ps,width=2.1in}
}
\centerline{
\makebox[2.1in]{(MEF 9)}
\hspace*{0.0in}
\makebox[2.1in]{(MEF 10)}
}
\caption{\protect\small
Top ten MEF's}
\label{Wen-FG:mefs}
\end{figure}
 
 
The number of
MEF's was selected based on the variation ratio 
$r=\sum_{i=1}^m\lambda_i/\sum_{i=1}^n\lambda_i$, where
$m$ out of $n$ MEF vectors were used, 
as defined in Section \ref{Wen-subsubsec:mef}. 
Table \ref{Wen-TB:mef_num} shows the number of MEF's corresponding to the
variation ratio.
 
\begin{table}[thb]
\begin{center}
\caption{The number of MEF's vs. the variation ratio}
\label{Wen-TB:mef_num}
\begin{tabular}{||c|c||}                        \hline
The variation ratio & The number of MEF's \\ \hline  
10\% & 1 \\ \hline  
20\% & 2  \\ \hline  
40\% & 6 \\ \hline  
80\% & 48  \\ \hline 
95\% & 125 \\ \hline 
\end{tabular}
\end{center}
\end{table} 

Figure \ref{Wen-FG:rate_mef} shows the
performance of the nearest neighbor approximator under the different 
variation ratio. The performance first improves when the ratio $r$ 
increases. Then, at the point $r=0.4$, the performance 
saturates at the recognition rate 87.0\%. Table \ref{Wen-TB:speedup} shows
average computation time for each sequence on the SGI INDIGO 2. The time
was obtained based on the two different nearest
neighbor query approaches, namely, 
the linear search and the hierarchical quasi-Voronoi diagram in
Section \ref{Wen-subsubsec:qvd}. 
The use of the hierarchical quasi-Voronoi partition
dramatically improves the query time.
 
\begin{table}[thb]
\begin{center}
\caption{Time of two nearest neighbor query approaches}
\label{Wen-TB:speedup}
\begin{tabular}{||c|c|c||}                        \hline
Variation ratio & Time (sec., linear) & Time (sec., hierarchical)  \\ \hline  
0.1 & 1.39 & 0.021 \\ \hline  
0.2 & 1.56 & 0.026  \\ \hline  
0.4 & 1.87 & 0.034 \\ \hline  
0.6 & 7.28 & 0.140 \\ \hline 
0.95 & 10.64 & 0.266\\ \hline 
\end{tabular}
\end{center}
\end{table} 

\subsubsection{Result of the Recursive Partition Tree Approximator in the MDF 
Space}
 
In this experiment, same 660 training sequences were used to build a
recursive partition tree. For each nonterminal region, we selected an
adaptive radius $r$ as defined in Section \ref{Wen-subsec:RPT} to
split the region into subregions. Given $r$ for a nonterminal region,
we have $k>1$ training samples and the distance between each pair of these
$k$ samples is greater than $r$. These $k$ samples were the centers to
generate a Voronoi diagram. The distance here is the Euclidean distance
in the MDF space corresponding to the region. 
Figure \ref{Wen-FG:mdfs} shows
the top 10 MDF's at the root level. If we compare the MDF's in 
Figure \ref{Wen-FG:mdfs} with the MEF's in Fig. \ref{Wen-FG:mefs}, it is clear that
the top MDF's capture feature locations (edges) because it accounts for the
major between-sign variations.
 
\begin{figure}[ht]
\centerline{
\psfig{figure=Weng_figs/mdf_0.ps,width=2.1in}
\hspace*{0.0in}
\psfig{figure=Weng_figs/mdf_1.ps,width=2.1in}
}
\centerline{
\makebox[2.1in]{(MDF 1)}
\hspace*{0.0in}
\makebox[2.1in]{(MDF 2)}
}
\centerline{
\psfig{figure=Weng_figs/mdf_2.ps,width=2.1in}
\hspace*{0.0in}
\psfig{figure=Weng_figs/mdf_3.ps,width=2.1in}
}
\centerline{
\makebox[2.1in]{(MDF 3)}
\hspace*{0.0in}
\makebox[2.1in]{(MDF 4)}
}
\centerline{
\psfig{figure=Weng_figs/mdf_4.ps,width=2.1in}
\hspace*{0.0in}
\psfig{figure=Weng_figs/mdf_5.ps,width=2.1in}
}
\centerline{
\makebox[2.1in]{(MDF 5)}
\hspace*{0.0in}
\makebox[2.1in]{(MDF 6)}
}
\centerline{
\psfig{figure=Weng_figs/mdf_6.ps,width=2.1in}
\hspace*{0.0in}
\psfig{figure=Weng_figs/mdf_7.ps,width=2.1in}
}
\centerline{
\makebox[2.1in]{(MDF 7)}
\hspace*{0.0in}
\makebox[2.1in]{(MDF 8)}
}
\centerline{
\psfig{figure=Weng_figs/mdf_8.ps,width=2.1in}
\hspace*{0.0in}
\psfig{figure=Weng_figs/mdf_9.ps,width=2.1in}
}
\centerline{
\makebox[2.1in]{(MDF 9)}
\hspace*{0.0in}
\makebox[2.1in]{(MDF 10)}
}
\caption{\protect\small
Top ten MDF's}
\label{Wen-FG:mdfs}
\end{figure}
 
 
\begin{table}[thb]
\begin{center}
\caption{Summary of the Experimental Data for RPTA}
\label{Wen-TB:tree}
\begin{tabular}{||c|c||c| c||}                        \hline
\multicolumn{2}{||c||} {\em Training } &\multicolumn{2}{c||} 
{\em Testing  } \\ \hline
Number of & 600 & Number of &  161  \\ 
training samples & (3300 images) & testing sequences & (805 images) 
\\ \hline
Height of & &Recognition & 93.1 \% \\ 
the tree & 7 & rate & (87\% for MEF)\\ \hline
Number of  & & Time per & \\  
nodes & 90 & sequence (sec.) & 0.63 \\ \hline 
\end{tabular}
\end{center}
\end{table} 

Once we have created the recursive partition tree, we used it to recognize
the sign. As we did in the experiments for the nearest neighbor
approximator in the MEF space. The segmentation result was used as the 
input for sign recognition. The results are summarized in Table
\ref{Wen-TB:tree}.
The correct recognition rate of 161 testing
sequences is 93.2\% which is better than the recognition rate (87.0\%) of
the nearest neighbor approximator in the MEF space. The average
recognition time per sequence is 0.63 second on the SGI INDIGO 2. The time
is longer than the time (0.27 seconds) of nearest neighbor approximator 
when the quasi-Voronoi diagram is used in the query. This is because
each nonterminal node in the recursive partition tree has its own version
of DKL projection matrices and each time the query vector traverses the
node, it has to go through the local projection, whereas in the case of
the nearest neighbor approximator, only one projection is necessary. 
 
\subsection{Experiments Related to MDF}
 
We have shown that the approximator in the MDF space has better performance
than the one in the MEF space. This is because the pixel-to-pixel
distance, whether in the original image space or the MEF space, can not
well characterize the difference between two signs due to the effects
such as lighting, viewing angle, and hand variation between different
subjects. On the other hand, the MDF's are the features that best
characterize different categories. In this section, we show some
experimental results to indicate quantitatively how the MEF and the MDF
may perform very differently in classifying signs.
 
We computed MEF's and MDF's, respectively, using 50 sequences (10 for
each signs). These signs are obtained from different subjects and
the viewing positions are slightly different. Figure \ref{Wen-FG:cluster} (a)
shows the samples in the subspace spanned by the first two
MEFs and Figure \ref{Wen-FG:cluster} (b) shows them 
in the subspace spanned by the first two
MDFs.
\begin{figure}[ht]
\centerline{
   \psfig{figure=Weng_figs/top2mef.ps,width=2.2in}
   \hspace*{-0.1in}
   \psfig{figure=Weng_figs/top2mdf.ps,width=2.2in}
   }
\vspace{-0.8cm}
\centerline{
   \makebox[2.2in]{(a)}
   \makebox[2.2in]{(b)}
   }
\caption{\protect\small
The difference between MEF and MDF in representing samples, 
(a) samples represented in the subspace spanned by the first two
MEFs,  (b) samples represented in the subspace spanned by the first two
MDFs,  the numbers in the plot are the class labels of the samples.}
\label{Wen-FG:cluster}
\end{figure} 

As clearly shown, in the MEF subspace, samples from a 
single class spread out widely and samples of different classes
are not far apart. In fact, some samples from different
classes mingle together. However, in the MDF subspace, samples of each
class are clustered more tightly and samples from different classes
are farther apart. This shows that the MDFs are better in terms of
classification of signs.

\section{Conclusions and Future Work}
\label{Wen-sec:conc}
 
In this chapter, we have presented a new approach to 
recognizing hand signs.  The prediction-and-verification scheme
for segmentation tightly combines recognition with segmentation and
it is able to deal with very complex backgrounds.  
In our recognition method, motion understanding 
(the hand movement) is
tightly coupled with spatial recognition (hand shape) using a 
unified space. 
To achieve a high applicability and adaptability to various conditions, we
do not impose a priori features that the system must use, but rather the
system automatically selects features from images during learning.
The system uses multiclass, multidimensional discriminant analysis to 
automatically select the most discriminating linear features for gesture 
classification.  These features automatically weigh all the input components,
through a linear combination, according to each component's relative 
importance  
in classification.  The recursive partition tree approximator is proposed
to perform classification with a large number of learned samples.  
With this tree, a large and complex many-class
classification problem is recursively decomposed into smaller
and fewer-class classification problems.  This tree structure
allows automatic feature selection in a coarse-to-fine fashion.
Although the features we use belong to a linear type,
the method realizes piecewise linear decision boundaries at leaf
level, capable of approximating any smooth non-linear decision boundary
to a desired accuracy, as long as a sufficient number of training samples
is available. 
In addition, the tree also 
allows pruning far-away samples from consideration in each query, 
realizing a logarithmic time complexity in the number of leaf
nodes in the tree. 
The segmentation-recognition method addresses three key aspects
of the moving hand sign interpretation, the hand shape, the location,
and the movement. 

In the current segmentation scheme, 
the fixations are generated mechanically. The
number of fixations and the positions of fixation
are the same regardless of the type of gesture.
In order to achieve best possible performance,
different gestures may require different fixation sequences. 
The later fixation depends on earlier ones.
A future direction of research is to 
investigate dynamic generation of fixations based on learning. 
 
\section*{Acknowledgments}
The authors would like to thank Dan Swets and
Shaoyun Chen for providing us the programs for MEF and MDF computation.
Thanks also go to Yu Zhong, Kal Rayes, Doug Neal, and Valerie Bolster 
for making
themselves available for the experiments. This work was supported in part by
NSF grant No. IRI 9410741 and ONR grant No. N00014-95-1-0637.

\section*{Appendix A}
 
Proof of Theorem~\ref{Wen-TM:nn1}. If the distance from ${\bf X}$ to $P_1$ is 
greater than $d$, then according to the definition of the $d$, 
there is going to a
training sample ${\bf X_l}$ in $C_1$ 
such that $\|{\bf X}-{\bf X_l}\|<d$. Since for any samples ${\bf Y}$ in 
region $C_2$, $\|{\bf X}-{\bf Y}\|\geq d$, so the closest training
sample will not be in the region of $C_2$. 

\section*{Appendix B}
 
Proof of Theorem~\ref{Wen-TM:nn2}. Let $P_2$ be the hyperplane such that 
the distance between $P_1$ and $P_2$ is $d$
as shown in Fig. \ref{Wen-FG:search}. Notice according to the definition of 
Voronoi diagram,
$f$ is the distance from $C_2$ to hyperplane $P_1$ and $e$ is the
distance from $C_1$ to hyperplane $P_2$. Let $M$ be the intersection point 
between
line $C_1C_2$ and $P_2$, $\|{\bf X}-M\|=m$, and the angle 
$\angle C_1MS=\alpha$. Then, we have
\[
a^2-e^2=m^2-2em\cos\alpha
\]
\[
b^2-f^2=m^2-2fm\cos(180^{\circ}-\alpha).
\]
As we have shown in the Theorem~\ref{Wen-TM:nn1}, the $C_2$ region does not contain
the nearest neighbor if ${\bf X}$ is not in the region between hyperplane
$P_1$ and $P_2$. This means $\alpha<90^{\circ}$. Thus, we have
$a^2-e^2<m^2$ due to $\cos\alpha>0$ and $b^2-f^2>m^2$ due to
$\cos(180^{\circ}-\alpha)<0$. Therefore, we have $a^2-e^2<b^2-f^2$.
 

\section*{Appendix C}
 
Proof of Theorem \ref{Wen-TM:converge}. Let ${\bf X}'$ be the nearest neighbor
of the query ${\bf X}$ in the training set $\bigcup_{i=1}^nX(L_i)$. We 
show that as long as we independently draw the training samples,
the probability that ${\bf X}$ traverses the recursive partition tree
exactly same as ${\bf X}'$ approaches 1 as $n\rightarrow \infty$. Assume
at the subregion $P_{i,j}$, we have the projection matrices $V$ and
$W$. The mixture distance from ${\bf X}$ to a center
$C$ under region $P_{i,j}$ is
\[
R_d^2({\bf X},C)=\|{\bf X}-VV^t{\bf X}\|^2+\|VWW^tV^t{\bf X}-VWW^tV^tC\|^2
\]
Using the {\em triangle inequality} property of the mixture distance, we
have
\begin{eqnarray}
R_d^2({\bf X},C)&\leq& \|{\bf X}-{\bf X}'\|^2+\|{\bf X}'-VV^t{\bf X}'\|^2
\nonumber \\
&+&
\|VV^t({\bf X}-{\bf X}')\|^2 \nonumber \\
&+&\|VWW^tV^t{\bf X}'-VWW^tV^tC\|^2
\nonumber \\
&+&\|VWW^tV^t({\bf X}-{\bf X}')\|^2 
\nonumber \\
&=& R_d^2({\bf X}',C)+\|{\bf X}-{\bf X}'\|^2\nonumber \\
&+&\|VV^t({\bf X}-{\bf X}')\|^2+
\|VWW^tV^t({\bf X}-{\bf X}')\|^2 \nonumber
\end{eqnarray}
 
If the sum of the last three terms ($S_3$)
of the above equation $\rightarrow 0$, we would have
$R_d({\bf X},C)=R_d({\bf X}',C)$ which means that the approximator would
make the same decision for ${\bf X}$ and ${\bf X}'$. Let $D_n$ be the
event that the nearest neighbor of ${\bf X}$ in the training set 
$\bigcup_{i=1}^nX(L_i)$ has a distance larger than $\eta$ while $E_i$ denotes
the event that the the nearest neighbor of ${\bf X}$ in the single
$X(L_i)$ has a distance larger than $\eta$. Since each $L_i$ is independently
and identically drawn, we have
\[
P\{D_n,\eta\}=\prod_{i=1}^nP\{E_i,\eta\}.
\]
On the other hand, ${\bf X}$ is a positively supported, which
means that $1-P\{E_i,\eta\}=\beta>0$. Thus,
\[
P\{D_n,\eta\}=(1-\beta)^n
\]
which approaches zero when $n\rightarrow \infty$. So, given any value
$S_3=\eta$ and $\epsilon>0$, we can have a positive $N$, so that
for any $n>N$, we have
\[
P\{D_n,\eta\}<\epsilon.
\]
Now, we have shown that the approximator makes
the same decision for ${\bf X}$ and ${\bf X}'$ as $n\rightarrow \infty$
\footnote{This may not be true if ${\bf X}'$ lies on the decision boundary.
Here, we assume that in the feature space that two classes are well
separated so that we can have a clear boundary between them.}. 
Finally, the fact that ${\bf X}$ is an interior point guarantees that
$f({\bf X}$)=f(${\bf X}')$ as $n\rightarrow \infty$.
 


