\documentclass[times, 10pt,twocolumn]{article} 
\usepackage{latex8}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{times}

%\documentstyle[times,art10,twocolumn,latex8]{article}

%------------------------------------------------------------------------- 
% take the % away on next line to produce the final camera-ready version 
\pagestyle{empty}

%------------------------------------------------------------------------- 
\begin{document}

\title{A Recognizer for Free-Hand Graph Drawings}

\author{\small Hamdi Dibeklioglu\\
Bogazici University\\ 
Dept. of Computer Eng.\\
%Dept. of Comp. Eng. \\
Istanbul, Turkey\\
%Hamdi.Dibeklioglu@cmpe.boun.edu.tr\\
hamdimail@gmail.com \\
\and
Tevfik Metin Sezgin\\
University of Cambridge\\ 
Computer Laboratory\\
Cambridge, UK \\
Metin.Sezgin@cl.cam.ac.uk\\
\and
Ender Ozcan\\
Yeditepe University\\ 
Dept. of Computer Eng.\\
%Dept. of Comp. Eng. \\
Istanbul, Turkey\\
eozcan@cse.yeditepe.edu.tr\\
}

\maketitle
\thispagestyle{empty}

\begin{abstract}
Interactive multimedia such as computer simulations and animations received
increased attention over the years as supplementary teaching tools and have
now become integral components of most engineering and science curriculums.
We believe one way to boost the utility of such simulations and animations
is to make them easier to use. In this paper, we describe a pen-based 
interface for constructing weighted and unweighted graphs which functions 
as a front-end to a shortest path algorithm simulator that we have developed.
We compare the usability of this pen-based interface to that of a WIMP-based 
interface and a hybrid interface that uses a mixture of pen-based and 
WIMP-based input methods.  We report evaluation results on the 
usability of the three types of interfaces that we have developed. Our results
show that a purely pen-based approach to graph creation may actually suffer 
from the relatively higher misrecognition rates of the harder-to-recognize
symbols and inhibit usability. We conclude that a hybrid approach which 
combines a soft-keyboard with graph recognition outperforms interfaces that
are purely pen-based or WIMP-based.

% We report on our findings on the 
% We allow the graph structure and the weights to be entered using 
% traditional WIMP-based interfaces or through ink-recognition. 




\end{abstract}



%------------------------------------------------------------------------- 
\Section{Introduction}
Interactive multimedia such as computer simulations and animations received
increased attention over the years as supplementary teaching tools and have
now become integral components of most engineering and science curriculums.

Although there is a wealth of resources for interactive animations,
these applications usually employ traditional WIMP-based interfaces 
regardless of the appropriateness of such interfaces for the task at hand.
For example, a quick web search for shortest path graph algorithms returns
over a hundred applets/applications with WIMP-based interfaces despite the
fact that drawing a graph -- the first step of interaction for all these 
applications -- could naturally be done using a pen-based interface due to 
its diagrammatic nature. 

Pen-based interfaces are not only better suited 
for this task, but also make it possible to interact with the application in question
in a relatively standard diagrammatic language unlike their WIMP counterparts. 
For example, quick examination of the WIMP-based shortest-path animation
applications reveals that they show considerable variation on how the
user is expected to construct the graphs. For adding nodes to the graph 
some applications use buttons with images, text, or both. Some use pull-down 
menus, some use a drag-and-drop interface while others use a combination of 
choice menus and buttons. Textual labels associated with the GUI elements also
show variation. For example, the words ``node/vertex,'' and
``edge,'' ``link,'' ``arc,'' ``line'' and ``connector'' are used 
interchangeably although they conceptually refer to the same thing and have
standard graphical/visual representations. 

The above observations give us reasonable support to believe that an 
intelligent pen-based interface which interprets free-hand pen input would be 
preferred over traditional WIMP-based interfaces for constructing graphs in 
our target domain of shortest path graphs. The usefulness of such a system will
depend on many factors including the degree to which we can correctly interpret
free-hand ink, the perceived ease-of-use for the users, the efficiency of the 
input method and the overall satisfaction of the users. To answer these
questions, we have built three interfaces for constructing graphs:

\begin{enumerate}
\item{{\em a pen-based interface} where the graph structure and weights are entered
using free-hand ink}
\item{{\em a WIMP-based PowerPoint-like interface} for graph construction and a 
soft-keyboard for inputting edge weights}
\item{{\em a hybrid interface} using pen input for graph construction and a 
soft-keyboard for inputting edge weights}
\end{enumerate}

All of these three interfaces function as front-ends to a shortest path 
algorithm simulator that we have developed. 
In the rest of this paper, we describe the architecture of our application 
including a summary of each front-end interface in detail. % We also 
%report quantitative results on the accuracy of our ink-recognition methods. 
We also report evaluation results on the usability of each 
interface. Our results show that the benefits of
a purely pen-based approach to graph creation may actually be undermined
by the relatively poor recognition rates of the harder-to-recognize symbols 
and inhibit usability. We conclude with a discussion of the related and 
future work.
%There is evidence that animations are useful teaching tools in general, and 
%for algorithms in particular. There are all there applets on the web for 
%simulating graph algorithms. They all have their own interface, and their own 
%vocabulary, but we already know how to draw graphs.
%------------------------------------------------------------------------- 


\section{Application Architecture}
We have designed our application to have a clear separation between the graph 
construction module and the algorithm animation module. We use a graph 
adjacency matrix representation to interface the front-end and the 
animation modules. This makes it easy to extend the system by adding a new 
input method or a new animation module.

\SubSection{Graph Construction Front-Ends}
\subsubsection{Ink recognition method}
The ink-based graph construction method has three components that respectively
support graph structure recognition, digit recognition, and editing. The control
flow chart in Fig.~\ref{control-flow} shows how the graph structure recognition
and the editing modules fit together. The digit recognition component is
a separate module.

\begin{figure}
\centerline{
\hbox{
	\includegraphics[width=3.35in]{figures/rec_architecture2}
}}
\vspace{-.15in}
\caption{Flowchart for the ink recognition process.}
\label{control-flow}
\end{figure}

\vspace{.1in}
\noindent
{\em \bf Recognizing the graph structure}

\noindent
As seen in Fig.~\ref{control-flow}, the graph structure is constructed by
recognizing circles and lines (for nodes and edges) and points (for entering
the edge-weight editing mode). We only support single stroke objects. So we 
assume that the users draw nodes and links using single strokes, and also 
write digits in single strokes.  

\vspace{.1in}
\noindent{\em \bf Node and edge recognition}

\noindent
In our pen-based interface, nodes and edges are recognized by fitting circles
and lines to the input stroke, and choosing the interpretation that has a 
lower least squares error. 

To find a line fit, we use the first and last points in the stroke,
$(x_1,y_1)$ and $(x_n,y_n)$, to derive the line equation $ax+by+c=0$ using 
the following equation of a line with two known points:

$$(y-y_1)(x_n-x_1)=(y_n-y_1)(x-x_1)$$

To fit a circle, we find the rectangular bounding box with corner positions
$(x_{min}, y_{min})$ and $(x_{max},y_{max})$ for the stroke at hand where
$x_{min}, y_{min}, x_{max}$ and $y_{max}$ are the minimum and maximum 
values for the $x$ and $y$ positions of the points in the stroke. Then 
the equation $(x-h)^2+(y-k)^2=r^2$ gives us the circular fit to the stroke 
where $(h,k)$ is the center of the circle and $r$ is the radius and

$$h = \frac{x_{min}+x_{max}}{2},$$
$$k = \frac{y_{min}+y_{max}}{2}.$$

After the line and circle fits are computed, we compute the distance of each 
point $(p_x,p_y)$ in the stroke to the line and circle fits using the 
following error functions: 

$$Error_{line}(p_x,p_y)= \left|\frac{a p_x + b p_y + c}{\sqrt{a^2+b^2}}\right|,$$
$$Error_{circle}(p_x,p_y)= \sqrt{(h-p_x)^2+(k-p_y)^2} - r.$$

We compute the average fitting error for circle and line fits using all 
points in the stroke and classify it to have the label of the fit with the lowest
average error. Circles indicate that the user has drawn a node, and lines 
indicate an edge. If the end points of the stroke lie on previously drawn 
nodes, then those nodes become the source and destination nodes. If the user
is drawing a directed graph, the direction of the stroke also determines
the direction of the edge. If either of the stroke's end-points don't lie 
inside a node, then the stroke is ignored.

If the recognized shape is a circle that surrounds a set of nodes, then it 
is interpreted as a selection operation and passed onto the graph editing 
module. 

\vspace{.1in}
\noindent
{\em \bf Handwritten digit recognition}

\noindent
Digit recognition allows the edge weights to be specified by pen input.
We have implemented two digit recognition methods. The first one 
uses Kohonen networks \cite{kohonen}. The other recognition method is based
on the iterative closest point \cite{ICP_algorithm} and parallel sampling
algorithms, and we describe it in detail in \cite{hamdi_thesis}. The 
method based on Kohonen networks has outperformed the latter algorithm and
it was our algorithm of choice for the version of the system used in 
the evaluation. 

\begin{figure}
\centerline{
\begin{tabular}{c}
	\includegraphics[scale=.5]{figures/digit_delete} \\
	(a)\\
	\includegraphics[scale=.5]{figures/digit_ok}\\
	(b)
\end{tabular}}
\caption{Gestures for indicating deletion (a), and the completion of the
edge-weight specification.}
\label{gestures}
\end{figure}

In addition to digits, we have trained the system to recognize two simple 
gestures as shown in Fig.~\ref{gestures}. A leftward dash deletes the last 
digit that was recognized, and a checkmark signals that the user is done 
entering the current weight. 

The users can edit their graphs using the pen interface. Nodes are 
selected by drawing a closed loop around them. Once the nodes are selected,
the selection can be dragged around to move the nodes. Drawing a line 
across the selection deletes the selected nodes and any edges connected to
them. Tapping the weight of an edge with the stylus puts the system into 
edge-weight editing mode where the user can update the weight value using 
the pen interface.

\subsubsection{Hybrid Method}
The hybrid method uses the graph recognition method described above for
specifying the graph structure. We use a soft-keyboard for entering the
edge weights. Fig.~\ref{soft-keyboard} shows the layout of our soft-keyboard.
It works much like the soft-keyboard included with the Windows XP Tablet PC
version. The user taps in the keys with a stylus or another pointing device
to enter the edge weights. Editing in the hybrid method works the same way
as in the ink recognition method, except the edge weights are entered 
using the soft keyboard.

\begin{figure}
\centerline{
	\includegraphics[scale=.5]{figures/soft-keyboard}
}
\caption{The soft-keyboard interface used for entering edge weights in the
hybrid and WIMP-based interfaces.}
\label{soft-keyboard}
\end{figure}


\subsubsection{WIMP-based method}
Fig.~\ref{WIMP} shows our WIMP based interface.
The WIMP based method uses image-buttons with textual labels for constructing
the graph structure. The image-buttons form a toolbar, and the user selects
the operation that needs to be performed by clicking on the appropriate button
in the toolbar. This interface is representative of most WIMP-based tools 
such as MS PowerPoint. As it was the case for the hybrid method, the edge
weights are entered using the soft-keyboard interface. The graph editing 
operations are selected using the toolbar.

\begin{figure}
\centerline{
\includegraphics[width=3.5in]{figures/WIMP}
}
\caption{The WIMP-based interface.}
\label{WIMP}
\end{figure}

\subsection{Graph Animation Module}
All three interfaces have a "RUN" button that the user can click or tap
to launch the graph algorithm simulation module once the graph construction
step is completed. Fig.~\ref{screenshot} shows a snapshot of the 
graph animation module simulating Dijkstra's shortest path algorithm on 
a problem specified by the user. As seen in the figure, the graph is 
color coded, and there is an English annotation of the algorithm's current
status displayed in the bottom of the window. We support all combinations of
directed/undirected and weighted/unweighted graphs and have implemented 
simulation modules for Dijkstra's and Kruskall's shortest path algorithms.

\begin{figure}
\centerline{
\includegraphics[width=3.5in]{figures/screenshot}
}
\caption{The graph animation module showing the simulation of the Dijkstra's
algorithm on a problem specified by the user.}
\label{screenshot}
\end{figure}

\Section{Evaluation} To find out how each of the three interfaces compare, 
we have conducted a user study. Among the goals of the user study were 
to determine which interface would best suit users who were somewhat 
knowledgeable in graph theory. 

For the user study, we recruited 10 students who had recently taken an 
undergraduate algorithms course. One subject was left-handed, while the rest 
were right-handed. 

The study consisted of three parts. In part 1, the subjects were shown a
weighted directed graph with five nodes and 10 edges. They were asked to:
\begin{itemize}
\item{construct the graph}\vspace{-.1in}
\item{remove three edges} \vspace{-.1in}
\item{remove a node and all the edges connected to that node}\vspace{-.1in}
\item{edit the weights of three edges}\vspace{-.1in}
\item{move two of the nodes}
\end{itemize}

In part 2, the subjects were shown a weighted undirected graph with nine
nodes and 13 edges. They were asked to:
\begin{itemize}
\item{construct the graph}\vspace{-.1in}
\item{remove three nodes and all connected edges} \vspace{-.1in}
\item{move the nodes around to obtain a specified layout}\vspace{-.1in}
\end{itemize}

In part 3, we asked the subjects to draw an undirected graph depicting 
the relative positions of five cities that the subjects were familiar with.
They were then asked to add at least seven edges to their graph labeled 
by the pairwise distance between the source and destination cities to the
best of their knowledge. The goal of part 3 was to have the subjects draw
a graph from memory, as opposed to copying one that they were shown. 

The subjects were asked to complete all three parts using the pen-based,
hybrid and the WIMP-based interfaces in an arbitrary order. For each task in 
the three parts, we also measured the time spent for the task as well as
the number of recognition/input errors and the number of corrections 
the users had perform. At the end of the study, the subjects have completed 
a survey. 

We have observed that 8 of the participants drew the weighted graphs starting 
with the vertices first. After drawing all vertices, they filled in the
edges. On average, all parts were completed in an hour. Based on the 
average time spent, the hybrid method ranked first and the pen-based 
method ranked last.


\begin{figure*}
 \begin{center}
   \begin{tabular}{l||c|c|c||}
     \cline{2-4}
              & \multicolumn{3}{|c|}{Input Method}\\
     \cline{2-4}
                                                       &\scriptsize Pen-based     &\scriptsize Hybrid     &\scriptsize WIMP \\
     \hline
     \multicolumn{1}{|l||}{\small 1.	The functions I expected to complete the tasks were available}              &\scriptsize 2.40 &\scriptsize 1.60 &\scriptsize 2.40 \\
     \hline
     \multicolumn{1}{|l||}{\small 2.	The interface was intuitive} 	                         &\scriptsize2.40	 &\scriptsize1.50	 &\scriptsize 2.70 \\
     \hline
     \multicolumn{1}{|l||}{\small 3.	I was satisfied with how the interface worked} 	 &\scriptsize2.40	 &\scriptsize1.30	 &\scriptsize 2.20\\
     \hline
     \multicolumn{1}{|l||}{\small 4.	The interface was simple to use} 	         &\scriptsize 2.50	 &\scriptsize 1.30	 &\scriptsize 2.30\\
     \hline
     \multicolumn{1}{|l||}{\small 5.	I could effectively complete the tasks} 	 &\scriptsize2.60	 &\scriptsize1.90	 &\scriptsize2.60 \\
     \hline
     \multicolumn{1}{|l||}{\small 6.	I could complete the tasks quickly} 	 &\scriptsize3.10	 &\scriptsize1.60	 &\scriptsize2.70 \\
     \hline
     \multicolumn{1}{|l||}{\small 7.	I could complete the tasks efficiently} 	 &\scriptsize2.90	 &\scriptsize1.70	 &\scriptsize2.60 \\
     \hline
     \multicolumn{1}{|l||}{\small 8.	I thought the "look" of interface was pleasant} 	         &\scriptsize2.20	 &\scriptsize1.50	 &\scriptsize2.90\\
     \hline
     \multicolumn{1}{|l||}{\small 9.	Drawing the nodes and the edges was easy}	 &\scriptsize1.80	 &\scriptsize1.00	 &\scriptsize2.10\\
     \hline
     \multicolumn{1}{|l||}{\small 10.	Entering the weights was easy}	         &\scriptsize4.90	 &\scriptsize2.00	 &\scriptsize2.20\\
     \hline
     \multicolumn{1}{|l||}{\small 11.	I could easily recover from errors} 	                 &\scriptsize2.40	 &\scriptsize1.70	 &\scriptsize1.80\\
     \hline
     \multicolumn{1}{|l||}{\small 12.	I really liked using the GUI.}	                         &\scriptsize3.00	 &\scriptsize1.30	 &\scriptsize2.80\\
     \hline
     \multicolumn{1}{|l||}{\small average score}                                                      &\scriptsize2.72	 &\scriptsize1.53	 &\scriptsize2.44\\
     \hline
   \end{tabular}
 \end{center}
 \vspace{-.15in}
 \caption{Aggregated results for the exit survey given to the users. The first column lists a number of statements. The users were asked to assign scores to each interface based on how much they agreed with the statements.}
\label{results-table}
\end{figure*}

Fig.~\ref{results-table} lists the questions that the subjects answered
at the end of the study. They were asked to assign a score 1-7 for each 
question, based on how much they agreed with each statement. The scores
were defined as: 1 {strongly agree}, 2  {somewhat agree}, 
3 {slightly agree}, 4 {neural}, 5 {slightly disagree}, 
6 {disagree}, 7 {strongly disagree}. We applied the Friedman's non-parametric
test with a degree of freedom 2 to evaluate the consistency of the ratings 
for the GUIs. The results show that the changes obtained for the statements 
\#6, \#7, \#10 and \#12 were significant within a confidence 
interval of 95\%. In summary, the participants preferred the hybrid interfaces
over the other two and they felt it allowed them to complete the tasks more efficiently.
The task completion times that we have measured, which are summarized in 
Fig.~\ref{statistics-table}, agree with this statement. 
Furthermore, the users found it easier to enter the weights with 
the hybrid method. Again, the figures summarized in Fig.~\ref{statistics-table}
support this. The table also shows that the pen-based interface had
the most number of errors during drawing and weight entry. 

Finally, although the ratings for statement \#9 in Fig.~\ref{results-table} 
were not consistent across users, the average rating is better for the hybrid
and pen-based interfaces compared to the WIMP-based interface. It 
seems that with a better digit recognizer, a purely pen-based approach 
would have been preferred. 

\begin{figure*}
 \begin{center}
   \begin{tabular}{l||c|c|c|c|c|c|c|c|c||}
     \cline{2-10}
              & \multicolumn{3}{|c|}{Part 1}& \multicolumn{3}{|c|}{Part 2}& \multicolumn{3}{|c|}{Part 3}\\
     \cline{1-10}
\multicolumn{1}{|l||}{Input Method}	&{\scriptsize Pen-based}&{\scriptsize Hybrid}&{\scriptsize WIMP}&{\scriptsize Pen-based}&{\scriptsize Hybrid}&{\scriptsize WIMP}&{\scriptsize Pen-based}&{\scriptsize Hybrid}&{\scriptsize WIMP}\\
     \hline
\multicolumn{1}{|l||}{$\mu$}   		&0.8	&0.9	&0.6	&0.4	&0.7	&0.3	&0.3	&0.2	&0.5 \\
     \hline
\multicolumn{1}{|l||}{$\sigma$}   	&0.63	&0.99	&0.84	&0.70	&0.67	&0.67	&0.67	&0.42	&0.53 \\
     \hline
   \end{tabular}\\
	Statistics for the number of errors made during graph structure specification.
 \end{center}
 \begin{center}
   \begin{tabular}{l||c|c|c|c|c|c|c|c|c||}
     \cline{2-10}
              & \multicolumn{3}{|c|}{Part 1}& \multicolumn{3}{|c|}{Part 2}& \multicolumn{3}{|c|}{Part 3}\\
     \cline{1-10}
\multicolumn{1}{|l||}{Input Method}	&{\scriptsize Pen-based}&{\scriptsize Hybrid}&{\scriptsize WIMP}&{\scriptsize Pen-based}&{\scriptsize Hybrid}&{\scriptsize WIMP}&{\scriptsize Pen-based}&{\scriptsize Hybrid}&{\scriptsize WIMP}\\
     \hline
\multicolumn{1}{|l||}{$\mu$}   		&2.90	&1.00	&1.20	&3.40	&1.10	&1.00	&3.00	&0.40	&0.70 \\
     \hline
\multicolumn{1}{|l||}{$\sigma$}   	&1.29	&1.41	&1.14	&1.51	&1.10	&1.15	&0.94	&0.52	&1.25 \\
     \hline
   \end{tabular}\\
	Statistics for the number of errors made during weight specification.
 \end{center}
 \begin{center}
   \begin{tabular}{l||c|c|c|c|c|c|c|c|c||}
     \cline{2-10}
              & \multicolumn{3}{|c|}{Part 1}& \multicolumn{3}{|c|}{Part 2}& \multicolumn{3}{|c|}{Part 3}\\
     \cline{1-10}
\multicolumn{1}{|l||}{Input Method}	&{\scriptsize Pen-based}&{\scriptsize Hybrid}&{\scriptsize WIMP}&{\scriptsize Pen-based}&{\scriptsize Hybrid}&{\scriptsize WIMP}&{\scriptsize Pen-based}&{\scriptsize Hybrid}&{\scriptsize WIMP}\\
     \hline
\multicolumn{1}{|l||}{$\mu$}   		&268.4	&217.3	&252.7	&276.1	&191.4	&250.1	&230.1	&140.3	&183.1\\
     \hline
\multicolumn{1}{|l||}{$\sigma$}   	&101.71	&56.88	&54.70	&77.67	&40.37	&86.07	&69.82	&54.63	&67.23\\
     \hline
   \end{tabular}\\
	Statistics for the amount of time spent on each of the three parts in seconds.
 \end{center}
 \caption{Mean ($\mu$) and standard error ($\sigma$) for the number of errors made during graph structure specification,
weight entry and the amount of time spent for each part by the subjects.}
\label{statistics-table}
\end{figure*}



\Section{Related Work}
Previous research in interpreting free-hand pen input can be categorized as
online methods that interpret ink as it is laid on the drawing surface, and
offline systems that interpret previously recorded drawings. Our system 
uses online recognition.

SILK and DENIM \cite{sis} are amongst the earliest tools to demonstrate the 
use of intelligent processing of free-hand input in enhancing user interfaces.
Work in \cite{kara_sr,saund_pccw,heloise,szummer,zeleznik-music-notepad,viola_shilman,sezgin_cga,tracy_uml,gross} and \cite{christine_uist} describe sketch 
recognition systems for a number of domains including electrical circuit diagrams, 
UML diagrams, graphs and family trees. Among these systems, some put more
emphasis on the usability and user interface issues of their application, while 
others aim to push forward the state of the art in sketch recognition. 
From this perspective, our work is closer to the first group of work, because
our main contribution is our user study which compares three different
user interfaces of varying degrees of intelligent ink processing to achieve 
the same task. Rather than focusing on developing the best recognition techniques,
we have explored the trade-off between the added convenience of doing intelligent
ink-processing and the inconvenience created by misrecognitions. We believe we 
have identified a mixture of pen-based and WIMP-based input methods that 
significantly outperform either method alone. 

\Section{Discussion and Future Work}
We have presented a pen-based interface for constructing weighted and 
unweighted graphs which functions as a front-end to a shortest path 
algorithm simulator that we have developed. We compare the usability 
of this pen-based interface to that of a WIMP-based interface and a 
hybrid interface that uses a mixture of pen-based and WIMP-based input 
methods.  Our evaluation of the three types of interfaces has revealed
that the hybrid interface is preferred by users over only pen-based
and only WIMP-based input methods. We believe the main reason for this 
is the high error rates for digit recognition as indicated by values
in Fig.~\ref{statistics-table}. It
is very likely that a combination of the relatively low resolution 
sampling rates for pen-based input and the kinesthetic properties 
of writing on a capturing device as opposed to paper is responsible 
for the low recognition rates. This suggests that building robust 
user independent digit recognizers as a critical research problem despite
the high recognition rates obtained for scanned images of digits. 



%------------------------------------------------------------------------- 
\bibliographystyle{latex8}
\bibliography{latex8}

\end{document}
