%********************************************************************
%*
%*          SAMPLE LaTeX SOURCE FILE FOR CASCON PAPERS
%*
%* You have received three files.  The PostScript file describes the
%* requirements for papers submitted to CASCON'96.  It also demonstrates
%* the required format.
%*
%* If you plan on using LaTeX to format your CASCON'96 paper, the
%* second and third files can be used as LaTeX templates.  The one
%* you are reading is the LaTeX that was used to produce the PostScript
%* file described above.  The third file is the bibliography file that
%* contains references used in the LaTeX file.  It must be named "refs.bib".
%*
%* Run with:
%*           latex <your-file-name>
%*           bibtex <your-file-name>
%*           latex <your-file-name>
%*           latex <your-file-name>
%*
%* Problems? Contact cascon@vnet.ibm.com
%*
%********************************************************************
\documentstyle[twocolumn,psfig]{article}
%********************************************************************
%* Two commands are needed for the hard copy version with no page
%* numbers.  Under the "\documentstyle..." command use
%* '\pagestyle{empty}' and after the '\maketitle' command use
%* '\thispagestyle{empty}' (see below).
%* Comment these two commands out for the soft copy version.
%********************************************************************
%\pagestyle{empty}

\newcommand{\cut}[1]{}


\textheight 8.5in
\textwidth 6.0in
\columnsep 0.37in
\oddsidemargin 0.25in   \evensidemargin 0.25in
\topmargin -.3in   \headheight 0in   \footheight 1in




\title{Live WWW  and its Agents: the CAS-LWWW Project}

\author{Yiming Ye \hspace{0.15in} John K. Tsotsos \\
Department of Computer Science \\
University of Toronto \\
Toronto Ontario \\
\vspace{0.15in}
Canada M5S 1A4 \\
Karen Bennet \\
IBM Centre for Advanced Studies \\
Stn. 2G, Dept. 894 \\
1150 Eglinton Avenue East \\
North York, Ontario \\
Canada M3C 1H7 }

\date{}
 
\begin{document}

%********************************************************************

%********************************************************************
\bibliographystyle{plain}

\maketitle
%********************************************************************
%* Two commands are needed for the hard copy version with no page
%* numbers.  Under the "\documentstyle..." command use
%* '\pagestyle{empty}' (see above) and after the '\maketitle' command
%* use '\thispagestyle{empty}'.
%* Comment these two commands out for the soft copy version.
%********************************************************************
%\thispagestyle{empty}

%********************************************************************
%* Abstract
%********************************************************************
\begin{abstract}


This paper
proposes the idea of vision agents over Internet,
outlines the performance models of Live WWW with agents,
 and describes
an object  search agent and its communications with other agents.
The goal is to reduce the traffic on the Internet for Live WWW
by integrating the WWW technology, agent theory and computer vision
technology together.



\end{abstract}

%********************************************************************
%* Section 1
%********************************************************************


\section{Introduction }
\label{IntroductiontheLWWWConcept}



The most significant recent developments enabling the creation of 
global information resources and world-wide
computer-based interpersonal communications 
are the incredible growth of the Internet and the success of the World Wide
Web (WWW). 
The Web
implements a global hypermedia that ultimately could incorporate 
much of the world's knowledge that exists in tangible
form. The Net implements a global communications system 
that ultimately could facilitate dialogue and interaction among
many of the world's people.


The sheer joy of browsing the world and finding the 
right nugget of information 
in the form of hypermedia has attracted
researchers from many fields to
 the problem of how to solve 
 core technical problems posed by the growth of global networks,
how to improve the current WWW and Internet
 technology, and how to predict or influence
what  the Internet or intranet will look like.
 
The WWW technology has advanced so rapidly
that even graphics, audio, and video can be
integrated into the Web.
Most previous research has concentrated on handling pre-recorded
data on the WWW. Recently, efforts have been made to make the
WWW live.
One spawn of these efforts is the MBONE 
(Multicast Backbone) \cite{Larsen} 
technology -----
an interconnected set of routers and subnets that provides
IP multicast delivery in the Internet.
The MBONE is a virtual network. It is layered on top of portions
of the physical Internet to support routing of IP multicast packets
since that function has not yet been integrated into many 
production routers. The network is composed of islands that can
directly support IP multicast, such as multicast LANs like
Ethernet, linked by virtual point-to-point links called ``tunnels".
The tunnel endpoints are typically workstation-class machines having
operating system support for IP multicast and running the 
``mrouted" multicast routing daemon.
In the IP multicast tunnels,
IP multicast packets are encapsulated for transmission
through tunnels, so that they look like normal unicast
datagrams to intervening routers and subnets. 
A
multicast router that wants to send a multicast packet
across a tunnel will prepend another IP header, set the
destination address in the new header to be the unicast
address of the multicast router at the other end of the tunnel,
and set the IP protocol field in the new header
such that the next protocol is IP.
The multicast router at the other end of the tunnel receives the 
packet, strips off the encapsulating IP header, and
forwards the packet as appropriate.
Driven by the availability of popular new multicast applications,
particularly those providing real-time audio and video teleconferencing
capabilities to Internet hosts,
the MBONE has grown exponentially.
Another effort to make the WWW live is represented by 
the WWW browser {\em Vosaic}, or {\em Video Mosaic},
which extends the architecture of the WWW to encompass the dynamic,
real time information space of video and audio
\cite{Chen95}.
In {\em Vosaic}, video and audio transfers occur in real time;
there is no file retrieval latency.
The video and audio result in compelling Web pages. Real time
video and audio data can be effectively served over the
present day Internet with the proper transmission protocol.
A real time protocol VDP is used to handle real time video
over the WWW.
VDP reduces inter-frame jitter and dynamically adapts to
the client CPU load and network congestion.
{\em Vosaic} dynamically changes transfer protocols, adapting
to the request stream and the meta-information in requested
documents.
Bellcore \cite{PaulWWW96} also proposes the
real-time data services for the Web, RAVE.
RAVE supports live and stored video and audio as well as less
typical real-time services such as information services
(e.g., news or stock market feeds).
The system is extensible so that new real-time services can easily be
added.
It supports unicast and multicast, as well as both real-time 
data sources and sinks.
RAVE integrates well into the Web so that many
multimedia applications may be written using simple HTML
extensions.
When acting as a live-data source, the RAVE server can connect
to hardware input devices
(e.g., a video capture device, a sound card, or a serial interface
connected to an external text feed). The real time data is packaged
in a uniform format and sent to clients over the network.
Right now, various Internet sites offer 
 the possibility to view an image captured by a computer with refresh
rates varying from one frame every few second to one 
frame every four hours. In net lingo these
images came to be known as ``live" in contrast with the rest of the usually static sites. 
The MCS-WebCam might be one of the most popular site
\cite{Jacqueshttp}.
The WebCam  
 is an easy to install real time video server that allows 
transmission of live video and
audio to a number of remote clients. Rather than go the beaten 
path of plug-ins, the WebCam server
seeks to use established standards such a server-push and JPEG
and it works 
 without any change to the configuration of the end-users machine. 
\cut{For WebCam,
the various ways of connecting to 
``the net" result in various frame rates.
Several possibilities are:
1.5 frames per second (fps) without audio for 
a 14k4 modem;
3   fps without audio for 
a  28k8 modem;
8   fps without audio for 
a ISDN 1 B Channel;
10  fps without audio for 
 ISDN 2 B Channels.
}

The live WWW opens many exciting application areas for WWW.
Several problems, however, make the real time transmission
of the video data from the server site to the client site
unappealing,
such as  the intense use of bandwidth, poor quality of
video image, and high price.
When the modem at the client site is too slow, the real time
video transmission simply does not work.


The goal of the CAS-LWWW
(Centre for Advanced Studies-Live World Wide Web)
 project is to solve the above
problems and reduce the Internet traffic
by integrating
computer vision technology, agent theory and
WWW technology
 together.
Instead of frequently transmitting the image data grabbed from
the camera
to the client and let the client to analyze the video
image, we simply build agents at the
server site  and ask the agents to
help
executing the tasks required by the
clients.
Therefore, the image grabbed from the camera
is first {\bf pre-processed} by the agents, only
those images that are of interest to the client
are sent through the Internet.
Thus the bandwidth used is greatly reduced.
This strategy can be applied to many areas,
such as security surveillance, etc.
It is even more interesting when the
camera need to be controlled
in order to perform a certain task,
such as searching for an object in the server's site.
The client does not need
to
interactively control the camera and get
 the video data
over the Internet again and again. The search agent
will control the camera and perform
the image processing operation at the server's site,
and only the most promising images that might contain the
target are transmitted to the client over the Internet.

\section{The High Bandwidth Requirement for Live WWW}

It can be predicated that as more and more people begin to 
use live WWW, the WWW will burst at the seams due to 
the lack of bandwidth from servers to clients.
To make the video over Internet to appear ``live",
a high-bandwidth is required.
A large percentage of web clients, however, are run
over low-speed 28.8 or 14.4 modems, and users are increasingly
considering wireless services such as cellular modems
at 4800-9600 baud.
A recent study by a popular server of shareware, Jumbo, revealed
that about 1 in 5 users were connecting with graphics
turned off, to eliminate the annoying latency of loading
web pages \cite{Armando96}, not to say when live video is included
in the web pages.
To make the live video over Internet popular,
a study of how to reduce the bandwidth used by the live 
WWW is required.

A nature step in reducing the bandwidth used is 
to reduce the amount of data that has to transmit
over the Internet.
Thus, image compression, that is to remove the
data redundancy, code redundancy,
inter-pixel redundancy, and psycho-visual redundancy
in an image before it is transmitted,
 is a necessary step in
live WWW. 
Various compression standards, most of which are based on JPEG
\cite{JPEG}
and MPEG \cite{Didier91}, have been used for live 
WWW and other multi-media WWW.
JPEG offers four modes of operation: lossless encoding,
sequential encoding, progressive encoding, and hierarchical
encoding.
The basic JPEG algorithm first represents the original image
in the frequency domain and then achieves data compression
by concentrating most of the signal power in the lower
spatial frequencies and reducing to zero the high frequencies
with small coefficients during the quantization step.
The progressive JPEG encodes the image in multiple 
coarse-to-detailed passes, thus when displayed,
 a blurry image first appears and it is refined as more image
data arrives.
The hierarchical JPEG encode the image at multiple resolutions,
thus lower-resolution versions may be accessed without first
having to decompress the image at its full resolution.
The MPEG is based on two basic techniques.
One is block-based motion compression for the reduction of temporal
redundancies, which is achieved by motion prediction and motion
interpolation with the assumption that
the blocks of the current picture can be modeled as a translation
of blocks of some previous picture or a combination of references
to past and future pictures.
The other is Discrete Cosine Transform
based  compression for the reduction of spatial
redundancies.

The sizes of the images or video sequences
 compressed by JPEG and MPEG
can be  greatly reduced.
JPEG achieves a 15:1 average compression ratio
and MPEG achieves compression ratios 
up to 200:1 on average by storing only the difference
 between successive frames.
In spite of the high compression ratio achieved by JPEG and MPEG,
the amount
of data needed to be transmitted over the Internet
is still large for live video.
Thus, in order to make the site appear ``live", many live
WWW sites have  to reduce the transmitting rate.
For example, Telepresence Systems, Inc. \cite{Ron}
is working on the  ProRata system
which provides groups of geographically separated people
with a sense of shared presence.
It takes video snapshots of participating
individuals every 5 minutes, merging the pictures into
a composite and then sending the composite image back to
each person in the group via the Internet.

All of the above
 approaches for reducing the bandwidth used over
the Internet does not involve intelligent
agent. There is no consideration
of the browser's requirement at the browsing time.
All the images are processed in a fixed mode,
with no consideration of the perception ability of the 
browser and the usefulness of the image to be transmitted.
We propose an idea of reducing the data 
 by using {\em vision agents }
to intelligently select and 
transmit only the images that are interesting
to the browser and compress the original image
according to the perception abilities of the browser. 

\section{Vision Agents Over Internet}

The concept of an agent has become important
in user interfaces, artificial intelligence,
and  mainstream computer science.
Research on and discussion about  agents has mushroomed
in the past few years.
Although it is not easy to provide a
 universally accepted definition,
we can say that
an {\em agent} is
a hardware or software-based computer system
that has some of
the following properties:

\begin{itemize}
\item {\em Awareness}: agents have knowledge
      about itself
      and the world;
\item {\em Autonomy}: agents operate without the direct intervention
   of humans or others, and have some kind of control over
their actions and internal state;
\item {\em Social ability}: agents can interact with other agents
      (and possibly humans) via certain communication methods;
\item {\em Reactivity and knowledge adaptation}:
       agents can perceive their environment (which can
       be the physical world, a user via a graphical user interface,
       a collection of other agents, the Internet, or perhaps all
       of them combined) and respond in a timely fashion to changes
       that occur in it;
\item {\em Pro-activity}: agents do not simply respond
       to their environment: they can  exhibit goal-directed
       behavior by initiating actions;
\item {\em Trust}: agents  usually do what they are
       supposed to do according to their perception of the task and
       the world situation;
\end{itemize}

An Internet agent refers to an agent that acts on the
browser's behalf \cite{EtzioniExpert}
\cite{Daigle95} \cite{Riecken}.
The most popular agents on the Web are indexing agents such as
Lycos, the WebCrawler, and InfoSeek.
Indexing agents carry out a massive, autonomous search of the WWW, 
and store an index of words in document title and document
texts. The user can then query the agent by asking for documents
containing certain key words.
The indexing agents
operate by suggesting locations
on the Web to the user based on a relatively weak model of what
the user wants, and what information is available at the
suggested location. The Internet Softbot, however,
represents a more ambitious attempt to both determine
what the user wants and understand the contents of information
services in order to provide better responses to information
requests.

The Live WWW agents are new kind of agents
that aims at reducing the bandwidth used by 
Web pages that contain live video.  
They  act as intelligent assistants
between the camera and the server or between other agents
to perform different kinds
of image processing, vision, or robotics
tasks required by the remote browser.
The general system architecture
for Live WWW with agents (LWWW-A) 
is shown
in Figure ~\ref{Syatem-Arch}.
The LWWW-A is basically a traditional
WWW architecture plus a set of agents that connect the
camera and the server.

\begin{figure}[htbp]
   \centerline{
    \psfig{figure=LWWW.Ark.fig.ps,width=1.9in,height=2.5in}
    }
  \caption{\label{Syatem-Arch}
           The LWWW system architecture. It is basically a traditional
           WWW architecture plus a set of agents that connecting the
           camera and the server to perform tasks required by the
           browser.}
\end{figure}


\section{Performance Modeling}

\subsection{LWWW With Passive Camera}

LWWW with passive camera means that the
zoom, pan, and tilt of the camera
 at the server's site is fixed.
So, when the vision agent is not used, 
the camera grabs images at a certain rate,
and the grabbed images are transmitted through the
Internet. 
In many situations, vision agents can be used to 
reduce the bandwidth used.
For example, a security person is responsible
for the security of a warehouse.
In the warehouse, there are several cameras fixed in various places
such that any part of the warehouse can be examined by at least
one of the cameras.
The images of the cameras are transmitted through Internet
to a LWWW site that is used by the security person
to check the situations of the warehouse.
Since the number of images displayed at the Web site is large
(which equals the number of cameras within the warehouse),
the bandwidth used by this LWWW site is also large.
The security person has to check every image on the computer 
screen, thus he might easily get tired. 
Vision agents can be used in order to 
reduce the bandwidth used and to make the task of the 
security person easier. Instead of immediately sending
the image grabbed by a camera to the browser,
a change detection agent  is employed to analyze the
image first, only those images that have enough
changes are sent through the Internet and displayed at
the client site.
The number of images transmitted is decreased,
thus 
the bandwidth used is also decreased. 
The security person's task is also easier, because he has 
less images to check.
Another example is to  reduce the size of the image
at the server's site by using vision agents that can act
according to the browser's requirement
and perception ability.
For example, a browser visiting a LWWW page is first asked
several questions about his understanding of image processing
technology. If the browser is an image processing
expert and he has a deep understanding of the line detection
technology. Then the images grabbed by the camera can be first
processed by a line detector and only the resulted images
that contain only lines or curves are transmitted through the
Internet.
Because the compressed line images take very few space,
the bandwidth used is greatly reduced.
In this case, we can even increase the frame rates
such that the browser can see a ``true" live video without
feeling the interval between the frames.

\subsubsection{The Waiting Time for a Single Image }
For Live WWW, we define the waiting time
for a single image frame  as the time between the
submission of the viewer's request and the display update
resulting from the request.

When agents are not used,
the waiting time $T_{wait}$ for a single image frame is given by


\begin{eqnarray}
\label{equWaitNoA}
T_{wait} & = & T_{setup} + T_{grab} + T_{prop}
               \nonumber   \\
         &   & + T_{trans} + T_{comDecompre}
               \nonumber   \\
         &   & + T_{display}
\end{eqnarray}
where $T_{setup}$
 is the network connection setup time
(the overhead in setting up the connection between
the source and the destination computer);
$T_{grab}$ is the image grabbing time for the camera;
$T_{prop}$ is the {\em propagation delay} of the connection
(the difference between the time the last bit is transmitted
at the head node of the link and the time the last bit is
received at the tail node);
$T_{trans}$ is  the 
  network transmission time for the
compressed image 
(the difference between the time the first bit of the first
packet of the communication packets that form the image object
and the last bit of the last 
packet of the communication packets that form the image object
are transmitted);
$T_{comDecompre}$ is the compression and decompression time
(the time needed to compress the image before it is transmitted
at the server site and the time 
needed to decompress the image before it is displayed at the browser's
site);
$T_{display}$ is the time needed to display the decompressed 
image at the browser's site.

When agents are used,
the waiting time is given by


\begin{eqnarray}
\label{equWaitA}
T_{wait_{A}} & = & T_{setup_{A}} + T_{grab_{A}} + T_{prop_{A}}
               \nonumber   \\
         &   & + T_{trans_{A}} + T_{agent} 
               \nonumber   \\
         &   & + T_{comDecompre_{A}}+ T_{display_{A}}
\end{eqnarray}
where
 $T_{setup_{A}}$ is the network connection setup time;
$T_{grab_{A}}$ is the image grabbing time;
$T_{prop_{A}}$ is the {\em propagation delay} of the connection;
$T_{agent}$ is
the agents operation time (the time for the agent to process 
the grabbed image);
$T_{trans_{A}}$ is the network transmission time for the
image after being processed by agents and being compressed;
$T_{comDecompre_{A}}$ is the compression and decompression time;
$T_{display_{A}}$ is the time needed to display the decompressed
image at the browser's site.

 


For the above two equations,
we can assume that 
$T_{setup} = T_{setup_{A}}$,
$T_{grab}= T_{grab_{A}}$, 
$T_{comDecompre}=T_{comDecompre_{A}}$, and 
$T_{prop}=T_{prop_{A}}$.
From the aspect of waiting time for a single image,
the network setup time and transmission time can occupy
a significant portion of the total waiting time.
The services provided by the Internet architecture
are {\em best effort} services
----- they  perform their functions as well as
possible, using as much of a shared resource as available,
but do not guarantee their performance or resource availability.
When the number of  users, especially the
LWWW users of the  Internet
increases,
several simultaneous high-bandwidth sessions might easily
saturate network links and routers.
As a result, the bandwidth available decreases and the transmission
increases.
To maintain an acceptable waiting time and send a useful stream,
it is very important to reduce the data to be transmitted over the 
Internet.
The Internet agents are used for this purpose.

From Equation ~\ref{equWaitNoA} and Equation ~\ref{equWaitA},
we get

\begin{eqnarray}
T_{wait} - T_{wait_{A}} & = & T_{trans} + T_{display}
               \nonumber   \\
         &   &               - T_{agent} - T_{trans_{A}}
               \nonumber   \\
         &&                    - T_{display_{A}}
\end{eqnarray}


Given a fixed network bandwidth, the transmission times
$T_{trans}$ grow proportionally with the size of the file
being transmitted.
It can be obtained by the size of the
image file to be transmitted $S_{image}$
\footnote{which is proportional to the dimensions
of the $2D$ image, its resolution (including color quantization),
and its quality.}
and the average network bandwidth $B$,
\[
 T_{trans} = \frac{S_{image}}{B}
\]

The value of $T_{display}$ can also be approximated by the
size of the image to be displayed 
\[T_{display} = cS^{dis}_{image}\]
where $c$ is a constant. 

Similarly,
$T_{trans_{A}} =  \frac{S_{image_{A}}}{B}$
and $T_{display_{A}} = cS^{dis}_{image_{A}}$.
$S_{image_{A}}$ is the size of the
image file to be transmitted after the transformation
by vision agents.
$S^{dis}_{image_{A}}$ is the size of the
image file to be displayed at the browser's side.
Since $S_{image_{A}}$ (e.g. the image only contain lines) 
and $S^{dis}_{image_{A}}$
can be much smaller than $S_{image}$ and $S^{dis}_{image}$
respectively, 
the waiting time
by using agents $T_{wait_{A}}$ can be much smaller than the
waiting time  without using agents $T_{wait}$,
although the agents have to spend some time to process the 
image.


\subsubsection{Transmitted Data for a Video Sequence}

We study how the vision agents can reduce the 
Internet traffic 
in this section.

Suppose the video sequence contains $N$ image frames.
When agents are not used,
the amount of 
data that is  transmitted over the Internet
is:

\begin{equation}
M_{data} = N S_{image}
\end{equation}

When agents are used,
suppose they filtered out $N^{*}$ images that are not
interesting,
then the amount of 
data that is  transmitted is:

\begin{equation}
M_{data_{A}} = (N - N^{*}) S_{image_{A}}
\end{equation}

Thus, the amount of data that is reduced by using
agents is

\begin{eqnarray}
M_{data} - M_{data_{A}} & = & N S_{image} 
               \nonumber   \\
         &   & - (N - N^{*}) S_{image_{A}}
\end{eqnarray}


Since $S_{image_{A}}$ can be much smaller than $S_{image}$ 
(e.g., in the line image case)
and $N^{*}$ can be pretty large (e.g., in the security person
case), the bandwidth used when the agents are used
can be much smaller than the bandwidth used when the agents
are not used.


\subsection{LWWW with Active Camera}

The spontaneous growth of the WWW over the past several years
has resulted in a plethora of remote controlled mechanical
devices which can be accessed via the WWW.
LWWW with active camera means that the zoom, tilt, pan,
and even the position of the camera at the server's
site can be interactively controlled by the remote
browser.
The use of an on-line controlled camera can
make the browser experience the state at a particular moment
in time as if he is in the actual remote space
where the camera is situated.

Right now, there are more than a hundred interesting
mechanical devices are connected to the WWW
\cite{Paulos95}.
For example, Paul Cooper et. al
developed a interactive, telerobotic system InterCam
\cite{Abrams}.
 Ken Goldberg et al. \cite{Goldberg} 
 developed a three axis telerobotic 
system where users were
able to explore a remote world with buried objects and  
alter it by blowing
bursts of compressed air into its sand filled world. 
Eric Paulos and John Canny \cite{Paulos95}
developed a WWW  browser  Mechanical Gaze,
which allows multiple remote WWW users to actively
control up to six degrees of freedom of a robot 
arm with an attached camera to explore a real
remote environment. The initial environment is a collection of physical museum exhibits which
WWW users can view at various positions, 
orientations, and levels of resolution. 
Cooperstock et. al \cite{Jeremy}
proposed
the idea of World-Wide Media Space (WMS)
for video-conferencing,
which supports navigation with an active floor plan
and exploits sensors to provide additional
information for remote activity.


LWWW with active camera requires a high bandwidth to operate
because the browser need to check the images constantly
while interactively controlling the camera.
Vision agents can be used to greatly reduce the  bandwidth used.

\subsubsection{Waiting Time}

For LWWW with active camera,
we define the waiting time  as the time
between the submission of the viewer's request 
and the display of a image at the client's site
that satisfies the viewer's request.

When agents are not used, the browser controls
the  camera remotely and check the images transmitted
over the Internet until a satisfactory image arrives.
Suppose the satisfactory image is the $N$th
image that is transmitted over the Internet,
then
the waiting time $T_{wait}$ is given by

\begin{eqnarray}
\label{equLWWWWaitNoA}
T_{wait} & = & T_{setup} 
               \nonumber   \\
         &   & + N\Big( T_{grab} + T_{prop}
               \nonumber   \\
         &   &              T_{trans} + T_{comDecompre}
               \nonumber   \\
         &   &             + T_{display} \Big)
\end{eqnarray}

When agents are used, instead of directly
transmitting each image
that is grabbed by the camera,
the agents analyze the image and decide whether it is the
one the browser required.
If the agents believe that the image is not a wanted one,
they will control the camera intelligently and grab
the next image to analyze.
If the agents believe that the image is a wanted one,
they will send the image through the Internet
to the browser.
When the browser checks the transmitted image and
is satisfied, the task is finished. If the browser is not satisfied
with the result, he/she will inform the agents to try 
again.
Suppose the camera grabbed totally $N^{*}$ images
when the browser is satisfied during the above process,
and suppose among them there are $N^{'}$ images are transmitted
through the Internet, then the 
waiting time is:



\begin{eqnarray}
\label{LWWWequWaitNoA}
T_{wait_{A}} & = & T_{setup}  + N^{*} T_{grab} + N^{*}T_{agent}
               \nonumber   \\
         &   & + N^{'} T_{prop} + N^{'} T_{trans_{A}}
               \nonumber   \\
         &   &  + N^{'} T_{comDecompre}
\nonumber   \\
         &   & + N^{'} T_{display}
\end{eqnarray}

Generally speaking,
$N$ is smaller than $N^{*}$ (because agents are not as 
smart as the browser),
but much bigger than $N^{'}$ (because many unwanted images
are filtered out by agents).
So, when the value of $T_{agent}$  
is not significantly large, the waiting time by using agents
can be much smaller than  the waiting time without using agents.





\subsubsection{Transmitted Data Reduced}

We study in this section
 the Internet traffic reduction
by using agents that intelligently control the camera and
analyze the images.

It is clear that
\begin{equation}
M_{data} = N S_{image}
\end{equation}

\begin{equation}
M_{data_{A}} = N^{'} S_{image_{A}}
\end{equation}

The amount of transmitted data that is reduced by using agents
is given by

\begin{equation}
M_{data} - M_{data_{A}} = N S_{image} - N^{'} S_{image_{A}}
\end{equation}

The above data reduction can be very significant when the agents
are ``smart" enough,
that is, when $N^{'}$ is kept very small compared to $N$.
 














\section{An Example: the LWWW Object Search Agent}
\label{LWWWObjectSearchAgent}


In the following section, we formulate the LWWW Object Search Agent
(LWWW-OSA), outline its working mechanism,
and present experimental results to illustrate how the agent
performs its task.

The LWWW-OSA is a useful feature of LWWW equipped with an active camera.
For example, a researcher of CAS wants to play baseball after
work.
The researcher is supposed to bring the baseball to the game, but 
cannot find it in the office.
The researcher wants to know whether the baseball is in someone
else's office.
The researcher can open the home page of the the possible
person and pass the request to the server site of LWWW.
At this time, the WWW agent can be activated to automatically
control the camera to search for the baseball.





\subsection{The LWWW Object Search Agent Formulation}
\label{LWWWObjectSearchAgentFormulation}

The LWWW Object Search Agent (LWWW-OSA) is a software package
that assists the server in its searching for an object in the server
site's space environment. It has the properties of autonomy,
social ability, reactivity, proactivity, trust, and knowledge
about itself and the environment.


\subsubsection{Awareness}
\label{KnowledgeItselfWorld}

The LWWW-OSA has the following knowledge about the sensor
 and the
environment.

The sensor unit is a camera with zoom, pan, and tilt capabilities.
The state of the sensor unit is uniquely determined
 by $7$
parameters $(x_{c},y_{c},z_{c},p,t,w,h)$,
here $(x_{c},y_{c},z_{c})$ is the position of the
unit center which cannot be changed,
$(p,t)$ is the direction of the camera viewing axis ($p$ is
the amount of pan $0 \leq p < 2 \pi$, $t$ is the amount of tilt
$0 \leq t < \pi$),
and $w,h$
are the width and height of the solid viewing angle of the camera.

The LWWW-OSA has a set of recognition algorithms that can be used
to analyze the image grabbed by the camera control agent to detect
the target.

The LWWW-OSA knows the geometric configuration
of the  search region $\Omega$.
It tessellates the region
$\Omega$ into a series of elements  $c_i$,
\( \Omega = \bigcup_{i=1}^{n}  c_{i} \) and \( c_{i} \bigcap c_{j} = 0 \)
for $i \neq j$. $c_{o}$ is the region outside $\Omega$.

According to the information the browser supplies about
the possible position of the target, the LWWW-OSA 
forms  a target probability distribution function
${\bf p}$.
The ${\bf p}(c_{i})$ gives the probability  that
the center of the target is within cube $c_{i}$.
The  LWWW-OSA uses ${\bf p}(c_{o})$ to represent the probability
that the target is {\em not} in the environment.

\subsubsection{Reactivity and Knowledge Adaptation}
\label{ReactivityKnowledgeAdaptation}

The LWWW-OSA perceives the physical world by executing actions
and adjusting its knowledge.

An operation \( {\bf f} = {\bf f}(p,t,w,h,a) \)
is an action of the searcher
within the region $\Omega$,
here
$a$ is the recognition algorithm used to detect the target.
 An operation ${\bf f}$ entails
two tasks: (1) the LWWW-OSA 
instructs the LWWW-CCA (Live World Wide Web ----- Camera 
Control Agent)
to take a
{\bf perspective} projection image
according to the camera configuration of ${\bf f}$ and to pass
 the image to LWWW-OSA; (2)
the  LWWW-OSA 
analyzes
 the result image
using the recognition algorithm $a$.

The
 cost ${\bf t_{o}(f)}$
gives the total time LWWW-CCA needed to 
manipulate the hardware
to the status specified by ${\bf f}$, 
take a picture and pass the image data to LWWW-OSA,
and
 run the recognition algorithm
   and update the environment if the target is not detected.



Each operation is associated with 
a detection function.
 The detection function on $\Omega$
is a function ${\bf b}$, such that
$ {\bf b}( c_{i},{\bf f} )$ gives the conditional
probability of detecting the target, given that the
                 center of the target is located within $c_{i}$ and
                 that the operation is ${\bf f}$.
   It is obvious that the probability of detecting the target
by applying action ${\bf f}$ is given by
$P({\bf f}) = \sum_{i=1}^{n} {\bf p}(c_{i})
                    {\bf b}(c_{i},{\bf f})$.


The LWWW-OSA not only senses the environment, it also updates
its knowledge according to the sensing result.
It uses  Bayes' formula
to update the probability
distribution whenever an action  fails (the target is not 
detected).
 Let $\alpha_{i}$ be the event that the center of the target
is in cube $c_{i}$; let
 $\alpha_{o}$ be the event that the center of the target
is outside the search region; and let $\beta$ be the event that after applying
a recognition action, the recognizer successfully detects the target.
Then $P(\neg \beta \mid \alpha_{i})= 1 - {\bf b} ( c_{i}, {\bf f} )$
and
 $ P( \alpha_{i} \mid \neg \beta ) = {\bf p}(c_{i},t_{{\bf f}+})$,
where $t_{{\bf f}+}$ is the time after ${\bf f}$ is applied.
Because
 the  events \(\alpha_{1}, \ldots,\alpha_{n},\alpha_{o} \)
 are mutually complementary and
exclusive,  the following updating rule holds

\small
\[
  {\bf p}(c_{i},t_{{\bf f}+}) \leftarrow
    \frac{ {\bf p}(c_{i},t_{{\bf f}}) (1 - {\bf b} ( c_{i}, {\bf f} ))}
    { {\bf p}(c_{o},t_{{\bf f}}) +
      \sum_{j=1}^{n} {\bf p}(c_{j},t_{{\bf f}}) (1 - {\bf b} ( c_{j}, {\bf f} ))
} 
\]
\normalsize
where $i=1,\ldots,n,o$.

\subsubsection{Trust and Pro-activeness}
\label{TrustPro-activeness}

According to the search task assigned by the browser,
LWWW-OSA can explicitly represent the goal of
the  task and analyze its difficulties and propose
a practical solution.

Let ${\bf  O_{\Omega}  }$ be the set of all the
 possible operations that can be applied.
The effort allocation \( {\bf F} = \{ {\bf f}_{1}, \ldots, {\bf f}_{k} \} \)
gives the ordered set of operations applied in the search, where
${\bf f}_{i} \in {\bf O_{\Omega}}$.
The probability of detecting the target by this allocation
is as follows:

\begin{eqnarray}
P[{\bf F}] &=& P({\bf f}_{1}) + [1 - P({\bf f}_{1})]P({\bf f}_{2})
               \nonumber   \\
           & &  + \; \ldots  + \; \nonumber   \\
           & &  \{ \: \prod^{k-1}_{i=1}[1 - P({\bf f}_{i}
)]\}
                                       P({\bf f}_{k})
\nonumber
\end{eqnarray}





The total cost for applying this allocation is
\begin{displaymath}
     T[{\bf F}] =  \sum_{i=1}^{k} {\bf t_{o}}({\bf f}_{i})
\nonumber
\end{displaymath}


If $K$ is the total time that is allowed for the search, then
the goal of object search  can be defined as
  finding  an allocation \( {\bf F} \subset
{\bf O_{\Omega}} \), which satisfies \( T{\bf (F)} \leq K \)
and maximizes $P[{\bf F}]$.


Because the above task is NP-Complete (for details of our proof, 
refer to \cite{YimingAIM} and \cite{YimingPhD})
and  the number of
the available candidate actions is usually  large, 
it is necessary to simplify the original problem.
Instead of looking for an algorithm that always generates
an optimal solution, LWWW-OSA  simply uses heuristics
that will generate a feasible solution for the original problem.
Here, the greedy strategy is used,
which suggests that one can devise an algorithm that 
works in stages, considering one input at a time. At each stage,
based on some optimization measure, the next candidate is
selected and is included into the partial solution
developed so far.
The objective function for the selection of the next action
is $ E({\bf f}) = \frac{P({\bf f})}{{\bf t_{o}}({\bf f})} $.
It is interesting to note that the above 
greedy strategy can generate the optimal answers
in many situations and that it can generate
a sequence of actions so that the expected
time  used to detect the target is minimized
(for detail of our proof,  refer to \cite{YimingAIM}\cite{YimingPhD}).

\subsubsection{Autonomy}
\label{Autonomy}

The LWWW-OSA selects the camera's state parameters 
$(p,t,w,h)$
without the intervention of the browser or the server. 
It determines the next action according to its
perception of the world and passes its decision to 
LWWW-CCA.

For  a given recognition algorithm,
there are many possible camera
 viewing angle sizes
to select from.
However,
 the whole
search region can be examined with high probability of detection
using only a small number of them.
For a specified angle, the probability of successfully
 recognizing the target is high only when the target is within a certain
range of distance from the camera.
This range is called the effective range for the given angle size.
The LWWW-OSA only considers 
angles whose effective ranges cover
the
entire depth $D$ of the search region and 
have no overlap of their effective ranges.
If the largest viewing angle
for the camera is $w_{0} \times h_{0} $
 and  its
effective range is $[N_{0}, F_{0}]$,
then the necessary angle sizes $<w_{i},h_{i}>$
 and the corresponding
effective ranges $[N_{i},F_{i}]$ are as follows:

\[
 w_{i} = 2arctan[ (\frac{N_{0}}{F_{0}})^{i}tan(\frac{w_{0}}{2}) ]
\]
\[
h_{i} = 2arctan[ (\frac{N_{0}}{F_{0}})^{i}tan(\frac{h_{0}}{2}) \]
\[ N_{i} = F_{0} ( \frac{F_{0}}{N_{0}})^{i-1}
\]
\[
F_{i} = F_{0} ( \frac{F_{0}}{N_{0}})^{i}
\]
where
$1 \leq i \leq \lfloor \frac{ ln(\frac{D}{F_{0}})}{ln(\frac{F_{0}}{N_{0}})} - 1
             \rfloor
$.

For each angle size derived, an infinite number
of camera viewing directions  can be considered. We have designed
an algorithm that can generate only
 the directions that
 can cover the whole viewing
sphere without
overlap. The  LWWW-OSA
only uses as candidate actions
 the viewing angle sizes and
the corresponding directions obtained by the above method.
An infinity of  
possible sensing actions is reduced to a finite
                set of actions that must
 be tried.
The LWWW-OSA uses $E({\bf f})$ to select
the best viewing angle size and direction  from 
the candidate actions.
For each recognition algorithm, LWWW-OSA can find a best action.
The next action to be executed is then selected from these 
best actions.

After the next action is selected, LWWW-OSA passes the result 
to LWWW-CCA. If the selected action does not find the target,
LWWW-OSA  updates its world knowledge according to 
Section ~\ref{ReactivityKnowledgeAdaptation} and selects another action to execute.



\subsection{The Behaviors of LWWW-OSA}
\label{BehaviorsLWWW-OSA}
The behavior of LWWW-OSA can be summarized as follows:

\begin{enumerate}
\item The LWWW-OSA receives an object search request
      from the server.  The request contains
      the target for which to search, the time allowed, and the possible 
      locations of the target that are supplied by
      the remote browser.
\item The LWWW-OSA initializes the target probability distribution
      according to
      the information provided by the browser, and
      collects the
      available object recognition algorithms needed to
      detect the target.
\item For each available recognition algorithm,
      the LWWW-OSA  selects a best action.
      \begin{enumerate}
        \item The LWWW-OSA selects possible camera 
              angle sizes $<w,h>$ needed to  examine the
              search region.
        \item The LWWW-OSA selects the best direction $<p_{k},t_{k}>$
              for each camera angle size $<w_{k},h_{k}>$.
        \item The LWWW-OSA compares the best directions for each camera angle
              size to find the best action for the given
              recognition algorithm.
      \end{enumerate}
\item The LWWW-OSA compares the best actions for each available
      recognition algorithm to find the parameters
      $<w,h,p,t,a>$ for the  next action.
\item The LWWW-OSA sends the best $<w,h,p,t,a>$ to LWWW-CCA.
\item The LWWW-CCA manipulates the hardware, grabs  an image,  and sends the
      image data to LWWW-OSA.
\item The LWWW-OSA analyzes the image by using recognition algorithm $a$.
      If the target is detected, it sends the FOUND signal to the server and 
      performs EXIT. 
\item If the allocated  time is used up, LWWW-OSA 
      sends the FAILURE signal to the server and performs EXIT. 
\item The LWWW-OSA updates the probability distribution and goes back to Step 3.    
\end{enumerate}


\subsection{Experiments}
\label{Experiments}

Experiments are performed to test the LWWW-OSA.
The Laser Eye sensor shown in Figure ~\ref{LWWW-Experiment}(b)
is  used in the experiment.
It is a sensing unit with pan and tilt capabilities,
and
consists
of a camera with controlled focal length (zoom), 
a laser range-finder,
and two mirrors. The mirrors  ensure collinearity
of effective optical axes of the camera lens and the
range finder.
The laser emits from the center of the camera
(see \cite{Jasiobedzki93} for details) 
 to measure the distance from the center of the camera
to  objects
in the environment in a specified
direction.
The direction of the camera's viewing axis and the
size of the camera's viewing angle can be adjusted
according to the visual task.
The search task assigned by the browser is to search for a baseball
in the environment
as shown in  Figure ~\ref{LWWW-Experiment}(a).
The browser also specifies to LWWW-OSA that the baseball
is probably on tables.
After LWWW-OSA initializes the probability distribution
of the search environment, the search begins.
Figure ~\ref{LWWW-Experiment}(c) shows the first action
selected by LWWW-OSA. The camera viewing angle size is
$41^{o} \times 39^{o}$.
Although the baseball is in the image, the given recognition
algorithm does not detect the target because the target
is outside the effective range of the view angle size
$41^{o} \times 39^{o}$.
Figure ~\ref{LWWW-Experiment}(e) shows the third action
selected by LWWW-OSA. The camera viewing angle size
is $20.7^{o} \times 19.7^{o}$. This action detects the target.
Figures ~\ref{LWWW-Experiment}(f) and ~\ref{LWWW-Experiment}(g) show
the image analyze result, where the baseball is detected
(refer to \cite{YimingIEEE}\cite{YimingPhD}
 for a more detailed discussion
 of the experiments).

\begin{figure}[!htbp]
   \centerline{
    \psfig{figure=/work0/yiming/SearchByZoomCamera/PS_For_Paper/Environment/image2.ps,width=35mm,height=35mm}
    \hspace{-7.5mm}
    \psfig{figure=/work0/yiming/SearchByZoomCamera/PS_For_Paper/Environment/image1.ps,width=35mm,height=35mm}
    }
   \centerline{\makebox[70mm]{(a)}}
   \centerline{
    \psfig{figure=/tsotsos2/yiming/LaserEyeImage/head-left.ps,width=14mm,height=35mm}
    \hspace{5.5mm}
    \psfig{figure=/work0/yiming/IJCAI/RealDecting/PS-Data/image_3.ps,width=35mm,height=35mm}
   }
   \centerline{\makebox[14mm]{(b)} \hspace{5.5mm}
               \makebox[35mm]{(c)}
    }
   \centerline{ 
    \psfig{figure=/work0/yiming/IJCAI/RealDecting/PS-Data/image_2.ps,width=35mm,height=35mm}
    \psfig{figure=/work0/yiming/IJCAI/RealDecting/PS-Data/image_1.ps,width=35mm,height=35mm}
    }
   \centerline{\makebox[35mm]{(d)}
               \makebox[35mm]{(e)}
    }
   \centerline{
    \psfig{figure=/work0/yiming/IJCAI/RealDecting/PS-Data/output_image.ps,width=35mm,height=35mm}
    \psfig{figure=/work0/yiming/IJCAI/RealDecting/PS-Data/outimage.ps,width=35mm,height=35mm}
    }
   \centerline{\makebox[35mm]{(f)}
               \makebox[35mm]{(g)}
    }
  \caption{\label{LWWW-Experiment}
           The search experiment by LWWW-OSA.
       (a) The search region. The Laser Eye is on one of the
           tables.
       (b) Laser Eye sensor;
        (c) The first action selected by LWWW-OSA;
        (d) The second action selected by LWWW-OSA;
        (e) The third action selected by LWWW-OSA;
        (f) and (g) The image analyzing result of (e), in which
           the
         target is detected.
}
\end{figure}

\section{Conclusion}
\label{Conclusion}

This paper proposes the concept of vision
agents over Live World Wide Web. 
It outlines the general architecture of the LWWW agent
technology
and gives the performance model for this architecture.
To illustrate the LWWW agent idea, 
a LWWW agent LWWW-OSA
is described and its formulation is 
presented.


The World Wide Web network information system is now
driving the Internet 
expansion throughout the world.
 It is estimated that the Net now links over 40,000 local
networks, 4 million computers, and over 40 million people.
 The Web now contains over
100 million documents, and is said to be doubling in size every 52 days.
The incredible interest in the Net and the Web, and in the more 
general concept of information highways,
is evident in the media today and is shared by 
peoples of various background. 
We believe that by offering the vision agents over Internet
can make the Live WWW more  attractive
and open more applications of WWW technology.
 Vision agents over Internet
will become one of the
features of the future  Internet technology.

The results presented in this paper can be taken as a starting
point for further study of the LWWW technology.
It opens  new avenues of research, such as,
how to extend the current
communication protocol so  that it is suitable for
LWWW technology, how to integrate  real time 
channels to make LWWW work effectively, and how to 
maintain the consistency, integrity and security of 
LWWW.

\vspace{15mm}

\noindent
{\Large\bf Acknowledgments}

\vspace{15mm}

\noindent
This work\footnote{The CAS-LWWW team now consists
Karen Bennet and Abhay Shah from IBM side,
  and John K. Tsotsos and Yiming Ye
from University of Toronto side.}
 was supported by IBM Centre for Advanced Studies and
ARK (Autonomous Robot for a Known environment) Project,
which receives its funding from PRECARN Associates Inc.,
Industry Canada, the National Research Council
of Canada, Technology Ontario, Ontario Hydro Technologies,
and Atomic Energy of Canada Limited.
The authors are grateful to 
Karel Vredenburg and  Don Hameluck 
for stimulating discussions and
to CASCON96 reviewers for valuable comments.

\vspace{15mm}

\noindent
{\Large\bf About the Author}
\vspace{15mm}

Yiming Ye is a Ph.D candidate at Department of Computer Science,
University of Toronto and a Research Fellow student at
IBM Canada Centre for Advanced Studies.
He has papers in the areas of
Internet agent and WWW, computer vision and image processing,
robotics, computational geometry, machine translation,
computational complexity,
and knowledge based systems
 been
published in journals and conference proceedings
such as:
{\em Proceedings of CASCON96},
{\em Proceedings of Second International Conference on Multiagent Systems (ICMAS96)},
{\em Proceedings of the
International Symposium on Intelligent Robotic Systems (SIRS96)},
{\em Proceedings of 1995
IEEE International Symposium for Computer Vision (ISCV95)},
{\em Proceedings of the
 4th International Symposium on Artificial Intelligence
and Mathematics (AIM95)},
{\em Proceedings of the
 Second Asian Symposium on Computer Mathematics (ASCM96)},
{\em Proceedings of the
IJCAI Workshop for handicapped Children},
{\em Proceedings of 1990 ACM Eighteenth Annual Computer Science
     Conference},
and {\em Science in China} etc.
His current research interests are
multimedia, image processing, computer vision,
robotics, Internet agent, and multiagent system, etc.
He can be reached at
yiming@vis.toronto.edu.


John K. Tsotsos is a professor of Department of Computer Science,
University of Toronto and 
a Fellow of Canadian Institute of Advanced Studies.
He can be reached at tsotsos@vis.toronto.edu.

Karen Bennet  
is a Principal Investigator and Operational Manager for
Center for Advanced Studies, IBM Canada.
She can be reached at bennet@vnet.ibm.com.



%\bibliographystyle{plain}

%\bibliography{robot_ref,shape_ref}
\bibliography{reference}


\newpage
.
\newpage
\cite{YimingTech}
\cite{YimingBeiJing95}
\cite{Lashkari}
\cite{Maes}
\cite{Wooldridge}
\cite{Wooldridge}
\cite{Chris}
\cite{Ossenbruggen}
\cite{Frank}
\cite{Tsot90}
\cite{Corina}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}
\cite{}


\end{document}
