%* Last edited: Sep 10 18:21 1995 (misha)
\documentstyle[11pt,twoside,epsf,/homes/kbs/tex/kbs]{article}

\oddsidemargin -36pt
\oddsidemargin -36pt
\oddsidemargin -36pt
\evensidemargin -36pt
\topmargin 0pt
\textheight 8.75in
\textwidth 6.5in

\begin{document}                        

\bibliographystyle{alpha}


\begin{titlepage}


{\bf
\begin{center}
  Massachusetts Institute of Technology\\
  Department of Electrical Engineering and Computer Science\\
  Proposal for Thesis Research in Partial Fulfillment\\
  of the Requirements for the Degree of\\
  Doctor of Philosophy
\end{center}}


\begin{flushleft}

\vspace{.5in}

{\bf Title:} \phdtitle

\vspace{.5in}

\begin{tabular}{llc}
{\bf Submitted by:}  & Karen B. Sarachik      &  \underline{\hspace{2.5in}} \\
                     & Rm. 703                &  (Signature of author)      \\
                     & MIT AI Lab             &                             \\
                     & 545 Technology Square  &                             \\
                     & Cambridge, MA  02139   &                            
\end{tabular}

\vspace{.5in}

{\bf Date of Submission:}  September 30, 1992

\vspace{.5in}

{\bf Expected Date of Completion:}  September, 1993

\vspace{.5in}

{\bf Laboratory where thesis will be done:}  Artificial Intelligence Laboratory

\end{flushleft}

\vspace{.5in}

{\bf Brief Statement of the Problem:} 

Several methods exist for recognizing 2D or 3D objects from their 2D
images, but any system implementer knows that it one thing to design
an algorithm, and quite a different thing to actually achieve the
performance that the algorithm promises. It is a relatively new
phenomenon in vision to try to gauge the effect of sensor error on any
particular method.

I have done an error analysis of a specific technique, called {\em
geometric hashing}, in the domain of 2D object recogition. The result
of the work so far has been to explicitly demonstrate the connection
between input sensor error (modeled as 2D Gaussian noise) and
confidence of the output of the hashing method. For the thesis I
intend to do a similar analysis for a different method in the same
domain, and show how a recognition system could improve performance by
choosing the output of one or the other method, depending on its
knowledge of the input noise characteristics of each module.

\end{titlepage}

\section{Introduction}

For my thesis work I plan to investigate how the presence of noise
affects the performance of a small class of visual recognition
algorithms, and how to use this information to predict these
algorithm's threshholds and optimal performance. To explain exactly
how this work fits into the general problem of recognition, it is
useful to abstract the recognition problem as a process of recovering
a set of original parameters about a source. In this abstraction,
there is some sort of information exchange between the source and the
observer, the information might be corrupted in some fashion, the
observer receives some subset of the information with added noise, and
finally, processes the observed information in one or several stages
to settle upon a hypothesis about the parameters of interest.

\begin{center}
\vfill
\csfig{4in}{recog.ps}
\vfill
\end{center}

For example, in the case of message transmission, the parameters of
interest are the message itself, the noise is introduced by the
channel, and the observer tries to recover the original transmitted
message. In sonar based distance measurement, the parameter of
interest is the free distance along a particular direction from a
source, the information is the reflected sonar beam, and the perceived
information is the time delay between sending and receiving the
beam. The observer then processes this information to come up with a
hypothesis about the free space along the particular direction.

In model based vision, the parameters of interest are the presence or
absence of a model in a scene, and its pose in three dimensional
space. The information is the light which is reflected from a source
by the objects in the scene, and the perceived information is the
light which enters the lens of a camera. The information goes through
several processing stages to get transformed into a two dimensional
array of brightness values representing an image, and then through
several more steps to come to a hypothesis about the presence and pose
of any particular model.

There is a large body of work which deals with the problem of
recovering an original signal which has been corrupted by a noisy
channel, a field which was pioneered by Shannon in his formulation of
information theory. In the domain of robotics and vision, recovering
such a signal (recognition) is complicated by the fact that there are
often many sophisticated modules between the perceived information to
the conclusion, each of which transforms the original information in
some complicated way. Many of the processing modules which make up the
recognition system are designed such that the image, in the
mathematical sense, of a particular point through the system is
understood, and the decision criteria of each module are based on the
location of the point's image. However, if one were to look at the
point as a probability distribution, which is a common representation
of a signal plus noise, the image of the entire distribution is not
taken into account.

\begin{center}
\csfig{4in}{noise.ps}
\end{center}

In the figure of our hypothetical system we are trying to recognize
the letters 'A' and 'B' in an image. Processing an unnoisy image of an
'A' maps the sensory input to the point labeled 'A' in the
interpretation space, so our recognition criterion is simply: does the
input point map to the interpretation point 'A'? According to this
criterion, we would say the input is a picture of a 'B'. However if we
consider the possibility that the information we received is somehow
noisy and that our source might just have easily produced information along an
entire range of values, then the image of the set of possible points
maps to a region in interpretation space which is consistent with
both the 'A' and 'B' hypotheses. 

Failure to take into account the effect of noise on a module can lead
to both positive and negative errors when these effects are large.
What I am trying to do in my work is to study how the noise is
transformed through a system from module to module and in so doing,
understand what sort of performance and confidence levels one can
expect from the output of any of the modules taken separately or
together, and how to set the inevitable decision criteria that many
modules use.

The motivating factor for this problem formulation arose during my
master's work in which I designed a system which, based on a narrow
sequence of information transformations, attempted to map the
dimensions of an enclosing room from a small amount of sensory input.
The design was straightforward, however in implementing the system it
became apparent that the system was not very robust, the reason being
that every step depended on the output of the previous step and
assumed error-free information.  This assumption led to a system with
unpredictable behavior because the manner in which an error input to a
module was magnified by that module were not analyzed. Difference in
lighting conditions, the effect of automatic gain control, errors in
stereo correspondence, and assumptions of distance away from viewed
objects, all led to errors which caused catastrophic failures. In
addition, many of the threshholds internal to each module were set
using heuristics whose applicability under different conditions were
assumed but not explicity known.

Thus I became interested in the questions: given noisy information
input to a processing module, how much ``information'' can really be
extracted from it? How well can one ``fine tune'' the module? How sure
can we be that the module has given us a good answer? When is the
noise too high to ever be able to get a good answer? For instance,
does automatic gain control introduce so much noise into our image
that doing stereo correspondence based on gradient strength is a
useless technique? And many more.

System robustness in not by any means a new problem in any area of
engineering. In the area of robotics and vision specifically, some
notable techniques of addressing the problem include:

\begin{itemize} 

\item Multisensor integration and system redundancy \cite{Durrant-Whyte},
\cite{Anita}. In this approach, redundancy is built into the system by
incorporating into it several different sensors or processing modules
for same feature. Each sensor or module has a weighting attached to
its output which is related to its assumed reliability. The confidence
of any reading is based on some sort of heuristic such as, ``If your
light meter isn't registering, then anything your vision module says
probably isn't of much use''.

\item Minimizing the effect of error by not making any module too
complex. This approach is evident in the approach of Rod Brooks. The
assumption is that the effect of setting any one module's threshhold
will be easily understood. This is certainly true if one looks at the
effect of this threshhold on the output of this module alone. However,
the effect at the systemwide level, which consists of many interacting
modules, may not always be clear.

\item Take many readings and use the average as the 'true' value. This
is mere common sense, but it does assume that the noise of the system has
mean 0.

\end{itemize}

These methods attempt to make the system robust by minimizing the
input noise to the system, not tracing the image of the noise through
a system.  My work is quite different in approach; instead of
concentrating on eliminating noise, I'm interested in understanding
the effects of noise by attempting to characterize the input
distributions to a module and understand how the distributions are
transformed by the module, and what confidence the output has. In this
way one can build a module whose effect on the system is understood.

For instance, if one can characterize the input distribution to a
module, perform the error analysis and then show that the output of
such a module under these conditions has only a confidence of 50\%,
this will effect a system into which one would put this module. For
instance, a multisensor integration scheme might use the information
to assign weights to this module's output. Alternatively, if one could
show that a 10\% reduction in error to this module would result in
an output with 85\% confidence, then one might concentrate on
eliminating the noise bottleneck at this point in the system.

In the next section I present an analysis done in this vein with
respect to a specific domain, namely, recognition of planar objects in
three dimensional space using geometric hashing.

\section{Error Analysis of Geometric Hashing}

In this section we look at the effectiveness of geometric hashing using
a Gaussian model for the sensor error. We compare the results using
this error model to previous work in which a bounded uniform
distribution for sensor error is assumed \cite{GHJ}, and show that
given a fixed probability of false negatives in both schemes, the
Gaussian error model results in a lower probability of false
positives.

In this problem, our input is an image of a 2D object with an
associated 3D pose. Assuming orthographic projection, we can represent
the image location $[u_i, v_i, 1]^T$ of each model
point $[x_i,y_i,1]^T$ with a simple linear transformation:

$$\left[\begin{array}{c} u_i \\ v_i \\ 1 \end{array}\right] = 
\left[\begin{array}{ccc} a & b & t_x \\ c & d & t_y \\ 0 & 0 & 1\end{array}\right]
\left[\begin{array}{c} x_i \\ y_i \\ 1 \end{array}\right]$$

where the upper left of the transformation matrix is a $2 \times 2$
non-singular matrix, and $[t_x,t_y]^T$ is the translation vector.

It is a fact that if a point has coordinates $\vec{X}$ with respect to
a given basis, then a linear transformation on the entire space leaves
the coordinates of the point unchanged with respect to the transformed
coordinates of the basis. The coordinates of $\vec{X}$ with respect to
the basis are called {\em affine} coordinates, and it is their
invariance under linear operations which is utilized in the geometric
hashing technique, outlined below.

\section{Restatement of the Geometric Hashing Algorithm}

First we look at the the geometric hashing algorithm assuming exact
measurements. The algorithm consists of two stages, a model
preprocessing stage and a recognition stage. During the preprocessing
stage, all models are entered into a hashing table in the following
way:

\begin{itemize}
\item[(1)] for every ordered model triplet $B_i = (m_0, m_1, m_2)$
\begin{itemize}
\item[(a)] for every other model point $m_j$
\begin{itemize}
\item[(i)] find coordinates $m_j = (\alpha_j, \beta_j)$ with respect to basis $B_i$
\item[(ii)] enter basis $B_i$ at location $(\alpha_j, \beta_j)$ in the
hash table.
\end{itemize}
\end{itemize}
\end{itemize}

The running time for this stage is $O(m^4)$. At recognition time:

\begin{itemize}
\item[(2)] for every unordered image triplet $(i_0, i_1, i_2)$
\begin{itemize}
\item[(a)] for every other image point $i_j$
\begin{itemize}
\item[(i)] find coordinates $i_j = (\alpha_j, \beta_j)$ with respect
to basis $(i_0, i_1, i_2)$
\item[(ii)] Index into the hash table at location $(\alpha_j,
\beta_j)$ and increment a histogram count for all bases found there.
\end{itemize}
\item[(b)] If the weight of the vote for any basis $B$ is sufficiently
high, stop and output the correspondence between triple $(i_0, i_1,
i_2)$ and basis $B$ as a correct hypothesis.
\end{itemize}
\end{itemize}

Note that we need to order the points either at the preprocessing
stage or at recognition time, but not both (or there would be a
sixfold redundancy of correspondences). We choose to order the points
at the preprocessing stage and enter every model point with respect to
a single unordered basis set 6 times, once for every ordering of the
basis set. This makes the table 6 times denser, but then at
recognition time we need only to choose an unordered image triple and
impose a single arbitrary ordering upon it. This way, when we use the
remaining image points to index into the hash table, we vote for the
ordering of the model basis set as well as model basis set itself.

The termination condition is exactly the issue we investigate in this
paper.  The worst case running time of the recognition stage is
$O(n^4)$, leading to a total runtime of $O(m^4+n^4)$.

\section{Modifications to the Algorithm in the Presence of Error}

The geometric hashing algorithm is a more sophisticated version of a
``generate and test'' method, in which a hypothesis is a model pose
implied by a size 3 correspondence of image to model points, and the
test is the number of additional projected model points which align
with the image. A straight ``generate and test'' algorithm would take
time $O(m^4n^4)$, since there are $O(m^3n^3)$ correspondences, and for
each one of these, every model point has to be tested against every
image point for a possible match.

The geometric hashing algorithm does the same thing, but cuts down the
running time by taking advantage of the invariance of a point's
coordinates with respect to a fixed basis under any affine
transformation. Since a size 3 correspondence between a $2D$ model and
image is expressible as an affine transformation, a given point will
have the same affine coordinates with respect to a fixed basis no
matter what set of image points this basis is set to correspond to.
This is what allows the decoupling of the model search space and the
image search space into two parallel phases ($m^4 + n^4$) instead of
sequential ($m^4 \cdot n^4$).

The assumption of circularly distributed error in the measured
location of image points gives rise to a circular disk of possible
image locations for any projected fourth point arising from a size 3
correspondence. In contrast, the corresponding possible hash table
locations for the fourth point is ellipsoid in shape. Because of this
complication we choose to test our analysis using the analogous
generate and test method, keeping in mind that the results we find
will be valid for both methods.

For the modified algorithm, instead of incrementing a histogram count
for every eligible basis by $1$, we increment the basis count by a
number between $0$ and $1$ according to some ``goodness'' criterion,
which in our case is a function of the distance of the point from its
expected location. Because of this, we must look at the density
function of the accumulated values for correct and incorrect
hypotheses, instead of the discrete probability of a particular vote.
We will use the term ``weight of a hypothesis'' to denote this concept.

\section{Overview}

The key difference between the evaluation of data using the Gaussian
error model as opposed to the bounded uniform error model is that in
the uniform case, any point falling inside an error disk contributes a
full vote for the model basis giving rise to that disk, whereas in the
Gaussian case, the vote is weighted by the point's proximity to the
center of the error disk.

The main claim of the paper is supported by the argument whose steps are as
follows:

\begin{itemize}

\item A $2D$ circular Gaussian distribution is a reasonable model for
sensor error, as opposed to a model assuming bounded uniform
distribution \cite{WW}.

\item Using this Gaussian distribution, the following is true: given a
correspondence between 3 image points and 3 model points (referred to
as a {\em hypothesis} for the rest of the article), and assuming a
fixed standard deviation $\sigma_0$ for the sensed error of the image
points, the location of a fourth model point with affine coordinates
$(\alpha, \beta)$ (with respect to the 3 image basis points) will also
have a $2D$ circular normal distribution with standard deviation
$\sigma_e$:

$$\sigma_e = \sigma_0((1-\alpha-\beta)^2 +\alpha^2+\beta^2+1)^{1/2}$$

Note that the possible distance of a fourth model point from its
predicted location is now unbounded. In our scheme we will pick a
cutoff search distance of $2\sigma_e$, which will imply a
probability of false negative identification of $13.5\%$.

\item As in \cite{GHJ}, we find the distribution of
$\sigma_e$ for a random model subject to some configuration
constraints to limit instabilities:

$$f(\sigma_e) = ({1 \over {b\sigma_e}})^2$$

where $b = 0.58$.

\item Next, we modify the geometric hashing recognition algorithm to
use this distribution to assign {\em weights} to points found within
the error disk, as opposed to a single $1/0$ vote. Though there are many
possible evaluation criteria which we could pick, in the following
analysis we use the weighting scheme:

$$v = \twodgauss{d^2}{\sigma_e}$$

where $d = $distance from the point's hypothesized to actual location.
This is the value of the $2D$ Gaussian density function whose center
is at the hypothesized location.

\item Define random variables $V_H=$ the weight that a model point's
projection contributes to its supporting basis, and $V_{\overline{H}}=$
the weight that a random image point contributes to a given basis. To
demonstrate what this means, we look at the simpler bounded uniform
error case in which the distribution of $V_H$ is:

$$f(V_H = v) = \cases{(1-c) & $v=1$ \cr
                        c   & $v=0$ \cr
                        0   & otherwise}$$

{\em i.e.}, the probability that a fourth model point will contribute a
weight of $1$ to a correct hypothesis is $1-c$, where $c$ is the
probability of occlusion. A more complicated expression was derived in
\cite{GHJ} for $V_{\overline{H}}$.

In the Gaussian error scheme with a cutoff distance of $2\sigma_e$
these distributions are:
        
\begin{eqnarray*}
f(V_H = v) & = & \cases{c+e^{-2}(1-c) & v=0 \cr
                        {{2\pi} \over b^2}(s_2 - {1 \over {e\sqrt{2\pi v}}})(1-c) &
                                $\ell_1 < v \leq \ell_2$ \cr
                        {{2\pi} \over b^2}{{e-1} \over {e\sqrt{2\pi v}}}(1-c) & 
                                $\ell_2 < v \leq \ell_3$ \cr
                        {{2\pi} \over b^2}({1 \over \sqrt{2\pi v}} - s_1)(1-c) &
                                $\ell_3 < v \leq \ell_4$ \cr
                        0 & otherwise}          \\
f(V_{\overline{H}} = v) & = & \cases{1 - {{4\pi(s_2-s_1)} \over {R^2b^2}} &
                                         v=0 \cr
                        {{2\pi} \over {R^2b^2v}}(s_2 - {1 \over {e\sqrt{2\pi v}}}) &
                                $\ell_1 < v \leq \ell_2$ \cr
                        {{2\pi} \over {R^2b^2v}}{{e-1} \over {e\sqrt{2\pi v}}} & 
                                $\ell_2 < v \leq \ell_3$ \cr
                        {{2\pi} \over {R^2b^2v}}({1 \over \sqrt{2\pi v}} - s_1) &
                                $\ell_3 < v \leq \ell_4$ \cr
                        0 & otherwise}          \\
&\ell_1 & = {1 \over {2\pi {s_2}^2 e^2}}        \\
&\ell_2 & = {1 \over {2\pi {s_2}^2}}            \\
&\ell_3 & = {1 \over {2\pi {s_1}^2 e^2}}        \\
&\ell_4 & = {1 \over {2\pi {s_1}^2}}
\end{eqnarray*}

and $s_1, s_2$ are the minimum and maximum allowable values for
$\sigma_e$, respectively.

\item For a model of size $m$ and a correct hypothesis, the weight of the
total vote for this hypothesis is the sum of weights over all $m-3$
other projected model points. We will call this random variable
$W_{H_m} = V_{H_1} + V_{H_2} + \ldots + V_{H_{m-3}}$, which (assuming
independence of the random variables $V_{H_i}$) follows the distribution:

$$f(W_{H_m} = v) = f(V_{H_1}) \otimes f(V_{H_2}) \otimes \ldots \otimes f(V_{H_{m-3}})$$

We will use the central limit theorem to avoid actually having to compute this
distribution. An incorrect hypothesis is calculated differently: For a
single point in an image with $m$ projected model points, the
distribution is:

\begin{eqnarray*}
f(V_{\overline{H}_m}) &=&\cases
        {1 - (m-3){{4\pi} \over {R^2b^2}}[s_2-s_1] & v=0 \cr
        (m-3){{2\pi} \over {R^2b^2v}}[s_2 - {1 \over {e\sqrt{2\pi v}}}] &
                                $\ell_1 < v \leq \ell_2$ \cr
        (m-3){{2\pi} \over {R^2b^2v}}[{{e-1} \over {e\sqrt{2\pi v}}}] & 
                                $\ell_2 < v \leq \ell_3$ \cr
        (m-3){{2\pi} \over {R^2b^2v}}[{1 \over \sqrt{2\pi v}} - s_1] &
                                $\ell_3 < v \leq \ell_4$ \cr
                0 & otherwise} 
\end{eqnarray*}

Dropping $n$ points convolves this distribution with itself $n-3$
times:

\begin{eqnarray*}
f(W_{\overline{H}_{m,n}} = v) &= &f(V_{\overline{H}_{m,1}}) \otimes
\ldots \otimes f(V_{\overline{H}_{m,n-3}})
\end{eqnarray*}

\item A random image gives rise only to incorrect hypotheses. The problem of
deciding whether a model of size $m$ is present in an image of size
$n$ now becomes the problem of distinguishing whether a particular
accumulation of weights for a hypothesis could arise from such a
distribution. In particular, the probability of a positive
identification for an incorrect hypothesis (false positive) in an
image with $n$ points is:

$$P(W_{\overline{H}_{m,n}} > \theta) = 1 - \int_0^\theta f(W_{\overline{H}_{m,n}} = v)dv = b$$

Similarly, the probability of a false negative upon testing a single
correct hypothesis (correspondence) is:

$$P(W_{H_m} < \theta) = \int_0^\theta f(W_{H_m} = v)dv = a$$

where $\theta$ is the threshold above which we decide that our
hypothesis is correct. Also, we can amplify or decrease our chances of
making a mistake by repeated samplings.

\item We can now make a direct comparison to the uniform case: we will
accept an image basis if it contributes $\geq \theta$ to any model
basis. This is analogous to the probability of collision in the hash
table for any model basis, as was derived in \cite{GHJ}, and is
found in our model by sampling the previous distribution ${m \choose
3} \times 6$ times: for a fixed sensor (image) basis:
\begin{eqnarray*}
P(\mbox{false positive}) &= &P(\mbox{any incorrect hypothesis yields
weight }>\theta) \\
        &= & 1 - P(\mbox{all incorrect hypotheses yield
weight}<\theta) \\
&= & 1 - (1 - b)^{{m \choose 3}6}
\end{eqnarray*}

While the probability of a false negative for a correct image basis is
simply $a$.  We compare the two models by graphing the false versus
true positives at different threshhold values for each curve. The
results are shown in a later section.
\end{itemize}

The following sections show the derivation of these distributions, and
the results of the analysis both analytically and empirically.

\section{Deriving the Projected Gaussian Distribution}

\noindent The two dimensional Gaussian probability density of a random
variable $\vec a$ with $0$ covariance is denoted as:

\begin{eqnarray*}
f(\vec a = (x,y))       & =     & {1 \over {2\pi \sigma_x \sigma_y}}
e^{-{{x^2 \over {2\sigma_x^2}} + {y^2 \over {2\sigma_y^2}}}}            \\
        & =     & (\onedgauss{x}{\sigma_x})(\onedgauss{y}{\sigma_y})    \\
        & =     & f(a_x = x)f(a_y = y)
\end{eqnarray*}

\noindent Note that the two components are independent. Therefore the
probability density of the sum of two random variables with $2D$
Gaussian distribution and $0$ covariance is:

$$f(\vec a + \vec b = (x,y)) = f(a_x+b_x=x,a_y+b_y=y)$$

\noindent Convolution in each dimension yields:

$$= {1 \over {\sqrt{2\pi(\sigma_{ax}^2+\sigma_{bx}^2)}}}e^{-{x^2 \over
{2(\sigma_{ax}^2+\sigma_{bx}^2)}}}{1 \over
{\sqrt{2\pi(\sigma_{ay}^2+\sigma_{by}^2)}}}e^{-{y^2 \over {2
(\sigma_{ay}^2+\sigma_{by}^2)}}}$$

\noindent Multiplying by a scalar yields:

$$f(c\vec a = (x,y)) = f(a_x= {x \over c},a_y={y \over c})$$ 

$$= \onedgauss{x}{(c\sigma_x)}\onedgauss{y}{(c\sigma_y)}$$

\noindent Therefore, assuming $\vec e_i, i\leq 3$ to have $2D$ Gaussian
distributions with $\sigma_{ix}=\sigma_{jy}, i,j \leq 3$, then the
distribution of the vector:

$$(1-\alpha-\beta)\vec e_1 + \alpha \vec e_2 + \beta \vec e_3 + \vec e_0$$

\noindent is a $2D$ Gaussian with covariance $0$ and standard deviation:

$$\sigma((1-\alpha-\beta)^2 +\alpha^2+\beta^2+1)^{1/2}$$

\noindent in both the $x$ and $y$ direction.

We choose our error disk to have radius $2\sigma_e$, so we will find
an image feature arising from a model point $86.5\%$ of the time (this
is demonstrated in a later section).  Note that this expression is
always smaller than its analogous expression for disk radius in the
uniform bounded error model:

$$\epsilon[\mid 1-\alpha-\beta \mid + \mid \alpha \mid + \mid \beta
\mid + 1]$$

because of the triangle inequality. Here, $\epsilon=2\sigma$.


\section{Determining the Distribution for $\sigma_e$}

As in \cite{GHJ}, we empirically estimate the distribution for
$\sigma_e$ by generating a random model of size $25$, then for each
ordered triple of model points as basis, we increment a histogram for
the value of $\sigma_e = f(\alpha, \beta)$ for all the other model
points with respect to that basis. 

The model is constrained such that the maximum distance between any
two model points is not greater than 10 times the minimum distance,
and in the basis selection, no basis is chosen such that the angle $\phi$
between the two axes is $0 \leq \mid \psi \mid \leq {\pi \over {16}}$
or ${{15} \over {16}}\pi \leq \psi \leq {{17} \over {16}}\pi$.

The trial was repeated 10 times and the results were similar; a
typical normalized histogram is shown in figure \ref{sigma}.
$\sigma_e$ ranges between the limits $s_1 = 2.875$ and $s_2 = 120$ and
roughly fits the curve $f(\sigma_e) = (b\sigma_e)^{-2}$, $b = 0.58$,
shown superimposed on the empirical distribution. The integral of the
analytic expression thus defined $= 1.009$.

\begin{figure}
\csfig{4in}{distsigma.ps}
\caption{The distribution of $\sigma$ for $m=25$.}
\label{sigma}
\end{figure}

\section{Derivation of the Single Point Distributions}

In this section we show the derivation of the distributions $f(V_H =
v)$ and $f(V_{\overline{H}} = v)$. We begin with the former.

\subsection{Deriving $f(V_H)$}

Given a correct hypothesis and and in the absence of occlusion, the
location of a projected model point can be modeled as a vector
$\vec{{\bf d}}$ centered at the predicted location with Gaussian
distribution (expressed in polar coordinates)

$$f(\vec{{\bf d}} = (r, \theta)) = \twodgauss{r^2}{\sigma_e}$$

We now choose an evaluation function $g(\vec{{\bf d}})$, and we
want to find its density, {\em i.e.}, we want $f(v = g(\vec{{\bf d}}))$,
where the distribution of $\vec{{\bf d}}$ is as stated. As mentioned
earlier, we chose the evaluation function

$$g(\vec{{\bf d}} = (r, \theta)) = \twodgauss{r^2}{\sigma_e}$$

Since the evaluation function $g$ is a really function of $r$ alone,
we need to know the density function of $r$. To find this, we integrate
$f(r,\theta)$ over $\theta$:

$$f(r) = \int_0^{2\pi} f(r, \theta) rd\theta = {r \over
\sigma_e^2}e^{-r^2 \over {2\sigma_e^2}}$$

Next, we want to find the density of the weight function $v= g(r)$.
The change of variables formula for a monotonically decreasing
function is:

$$\mbox{dens}(g(r) = v)  = {-f(g^{-1}(v)) \over g'(g^{-1}(v))}$$

Doing the math, we get:

\begin{eqnarray*}
g(r)    & =     & \twodgauss{r^2}{\sigma_e}             \\
g'(r)   & =     & -{r \over \sigma_e^2}g(r)             \\
f(r)    & =     & {r \over \sigma_e^2}e^{-r^2 \over {2\sigma_e^2}}      \\
        & =     & 2\pi r g(r)                           \\
f(g^{-1}(v)) &  =       & 2\pi g^{-1}(v) g(g^{-1}(v))   \\
        & =     & 2 \pi v g^{-1}(v)                     \\
g'(g^{-1}(v))   & =     & - {g^{-1}(v) \over \sigma_e^2}g(g^{-1}(v))    \\
        & =     & -{g^{-1}(v) \over \sigma_e^2}v        \\
\Longrightarrow f(v=g(r))       & =     & {-f(g^{-1}(v)) \over g'(g^{-1}(v))} \\
        & =     & 2 \pi v g^{-1}(v) {\sigma_e^2 \over {vg^{-1}(v)}}     \\
        & =     & 2 \pi \sigma_e^2
\end{eqnarray*}

However, since we only search out to a radius of $2\sigma_e$, the
effective distribution is:

$$f(V_H = v) = \cases{\int_{v=g(\infty)}^{v=g(2\sigma_e)} 2\pi\sigma_e^2
                        dv = e^{-2} & $v=0$ \cr
                        2 \pi \sigma_e^2 & ${1 \over {2 \pi\sigma_e^2e^2}}
                        \leq  v \leq  {1 \over {2 \pi\sigma_e^2}}$\cr
                        0 & otherwise}$$

{\em i.e.}, we will miss a good point $e^{-2} = 13.5\%$ of the time.
This expression correctly integrates to $1$.  Now, note that we have
this expression for a fixed $\sigma_e$, i.e., we actually have derived
$f(v = g(r) \mid \sigma_e)$. We need to integrate this expression over
all values of $\sigma_e$, that is:

\begin{eqnarray*}
f(V_H = v)& =   & \int f(V_H = v \mid \Sigma =  \sigma)f(\Sigma = \sigma)d\sigma \\
        & =     & \int (2\pi\sigma^2)(b\sigma)^{-2}d\sigma \\
        & =     & {{2\pi} \over b^2}\int d\sigma
\end{eqnarray*}

There are two things to take into consideration when calculating the
limits for this expression: first, the possible values of $\sigma$
range from $s_1 = 2.875$ to $s_2 = 120$. Second, we note that for a particular value
$v$, the only values for $\sigma$ such that $g(\vec{\bf d} \mid
\sigma)$ could equal $v$ are in the range $({1 \over {\sqrt{2 \pi
v}e}}, {1 \over \sqrt{2 \pi v}})$. Therefore  the lower bound on
the integral is $\sigma = \mbox{max}(s_1, {1 \over {\sqrt{2 \pi v}e}})$,
and the upper bound is $\sigma = \mbox{min}({1 \over \sqrt{2 \pi v}},
s_2)$. We split this integral into 3 regions, and deal with the case
where $v=0$ separately. Integrating, we get:

\begin{eqnarray*}
f(V_H = v)      & =     & \cases{e^{-2} & v=0 \cr
                        {{2\pi} \over b^2}(s_2 - {1 \over {e\sqrt{2\pi v}}}) &
                                $\ell_1 < v \leq \ell_2$ \cr
                        {{2\pi} \over b^2}{{e-1} \over {e\sqrt{2\pi v}}} & 
                                $\ell_2 < v \leq \ell_3$ \cr
                        {{2\pi} \over b^2}({1 \over \sqrt{2\pi v}} - s_1) &
                                $\ell_3 < v \leq \ell_4$ \cr
                        0 & otherwise}          \\
&\ell_1 = &{1 \over {2\pi {s_2}^2 e^2}}         \\
&\ell_2 = &{1 \over {2\pi {s_2}^2}}             \\
&\ell_3 = &{1 \over {2\pi {s_1}^2 e^2}}         \\
&\ell_4 = &{1 \over {2\pi {s_1}^2}}
\end{eqnarray*}

\subsubsection{Adding Occlusion}

It is easy to add occlusion into this distribution by considering an
independent process whose probability of occluding any given point is
$c$. Therefore, the above distribution is multiplied by another
factor:

$$f_c(V_H = v) = \cases{f(V_H = 0)(1-c) + c & $v = 0$ \cr
                        f(V_H = v)c     & otherwise}$$

We will use the distribution $f$, not $f_c$, in the rest of the paper,
and will reconsider the rate of occlusion only in the context of
calculating false negatives in a later section.

\subsection{Deriving $f(V_{\overline{H}})$}

We do the same derivation for the distribution $f(V_{\overline{H}})$. 
Given a hypothesis and a random point, we calculate the distribution
as follows: let event $A$ = ``point falls in hypothesized error
disk''. This is the area of the error disk over the size of the image $R^2$,
{\em i.e.},

\begin{eqnarray*}
P(A \mid \sigma_e)                      & =     & {{4\pi\sigma_e^2} \over R^2} \\
P(\overline{A} \mid \sigma_e)   & =     & {{R^2 - 4\pi\sigma_e^2} \over R^2}
\end{eqnarray*}

Now we calculate the probability that a point which is uniformly
distributed inside a disk of radius $2\sigma_e$ contributes value $v$ for an
incorrect hypothesis, using the evaluation function defined in the
previous section. As before, we must express a uniform distribution in
polar coordinates and then integrate over $\theta$ to get the
distribution in terms of $r$ alone, since the evaluation function $g$
is a function of $r$:

\begin{eqnarray*}
f(r, \theta)    & =     & {1 \over {\pi (2\sigma_e)^2}}         \\
f(r)            & =     & \int_0^{2\pi} {1 \over {\pi (2\sigma_e)^2}} rd\theta  \\
                & =     & {r \over {2\sigma^2}}
\end{eqnarray*}

As before, we calculate the density of $(v = g(r) \mid A \wedge \sigma_e)$ with the new
distribution for $r$:

\begin{eqnarray*}
g(r)    & =     & \twodgauss{r^2}{\sigma_e}             \\
g'(r)   & =     & -{r \over \sigma_e^2}g(r)             \\
f(r)    & =     & {r \over {2\sigma_e^2}}                       \\
f(g^{-1}(v)) &  =       & {{g^{-1}(v)} \over {2\sigma_e^2}}     \\
g'(g^{-1}(v))   & =     & -{g^{-1}(v) \over \sigma_e^2}v        \\
\Longrightarrow f(v=g(r) \mid A)        & =     & {-f(g^{-1}(v)) \over g'(g^{-1}(v))} \\
        & =     & {1 \over 2}v^{-1}
\end{eqnarray*}

Therefore, the density function of $v$ for a fixed $\sigma_e$ is:

$$f(V_{\overline{H}} = v \mid \sigma_e) = \cases{P(\overline{A} \mid \sigma_e)={{R^2 - 4\pi\sigma_e^2} \over R^2} & $v=0$ \cr
                        f(v \mid A \wedge \sigma_e)P(A \mid \sigma_e)={{2\pi\sigma_e^2} \over R^2v}  &
                        ${1 \over {2 \pi\sigma_e^2e^2}}
                        \leq  v \leq  {1 \over {2 \pi\sigma_e^2}}$\cr
                        0 & otherwise}$$

Again, this expression correctly integrates to $1$. As before, we
need to integrate this expression over all values of $\sigma_e$:

\begin{eqnarray*}
f(V_{\overline{H}} = v)& =& \int f(V_H = v \mid \Sigma =  \sigma)f(\Sigma = \sigma)d\sigma \\
        & =     & \int ({{2\pi\sigma^2} \over R^2v})(b\sigma)^{-2}d\sigma \\
        & =     & {{2\pi} \over {b^2R^2v}}\int d\sigma
\end{eqnarray*}

Dealing with $v=0$ as a separate case, and with the same upper and
lower bounds as in the previous case. Integrating yields:

\begin{eqnarray*}
f(V_{\overline{H}} = v) & = & \cases{1 - {{4\pi(s_2-s_1)} \over {R^2b^2}} &
                                         v=0 \cr
                        {{2\pi} \over {R^2b^2v}}(s_2 - {1 \over {e\sqrt{2\pi v}}}) &
                                $\ell_1 < v \leq \ell_2$ \cr
                        {{2\pi} \over {R^2b^2v}}{{e-1} \over {e\sqrt{2\pi v}}} & 
                                $\ell_2 < v \leq \ell_3$ \cr
                        {{2\pi} \over {R^2b^2v}}({1 \over \sqrt{2\pi v}} - s_1) &
                                $\ell_3 < v \leq \ell_4$ \cr
                        0 & otherwise}                  \\
&\ell_1 & = {1 \over {2\pi {s_2}^2 e^2}}                \\
&\ell_2 & = {1 \over {2\pi {s_2}^2}}                    \\
&\ell_3 & = {1 \over {2\pi {s_1}^2 e^2}}                \\
&\ell_4 & = {1 \over {2\pi {s_1}^2}}
\end{eqnarray*}

We ran an experiment to test the analysis of this section, and the
results are shown in Figure \ref{dists}.  Both graphs show a
normalized histogram of the results of a $15,000$ independent trials.
There is a good correspondence between predicted and actual results.

\begin{figure}
\parbox{6.5in}{
\begin{center}
\parbox{4in}{\csfig{4in}{distwithm.ps}} \\
\parbox{4in}{\csfig{4in}{distwom.ps}}
\end{center}}
\caption{Distributions, $f(v)$, with and without model}
\label{dists}
\end{figure}

\section{Finding the Weight Density of a Model in an Image}

The next step is to find the weight density of a correct and incorrect
hypothesis using these distributions.  For a model of size $m$ and an
image of size $n$, a correct hypothesis should have weight density

$$f(W_{H_m} = v) = f_c(V_{H_1}) \otimes f_c(V_{H_2}) \otimes \ldots \otimes f_c(V_{H_{m-3}})$$

assuming that each point contributes weight to its supporting
basis independently of any other.  In order to avoid convolving the
distributions from the previous section, we find the expected value and
the standard deviation of the distributions and invoke the central
limit theorem to claim that the combined weight of a correct
hypothesis of a size $m$ model in a size $n$ image with should roughly
follow the distribution:

$$N(mE_H, m\sigma_H^2)$$

in which 

\begin{eqnarray*}
E_H(v)  & =     &\int_0^0 vf_c(v)dv + \int_{\ell_1}^{\ell_2} vf_c(v)dv +
                \int_{\ell_2}^{\ell_3} vf_c(v)dv + \int_{\ell_3}^{\ell_4}v f_c(v)dv \\
        & =     & 0 + (1-c){{3e^4-4e^3+1} \over {12\pi b^2 s_2^3 e^4}} + (1-c)\left({{e-1} \over {3
                        \pi b^2 e}}\right)\left[{1 \over {s_1^3e^3}} - {1 \over s_2^3}\right]
                        +(1-c){{e^4-4e+3} \over {12\pi b^2 s_1^3 e^4}}  \\
        & =     & (1-c)3.26 \times 10^{-4} \\
E_H(v^2)        &=      &\int_0^0 v^2f_c(v)dv + \int_{\ell_1}^{\ell_2} v^2f_c(v)dv +
                \int_{\ell_2}^{\ell_3} v^2f_c(v)dv + \int_{\ell_3}^{\ell_4}v^2f_c(v)dv \\
        &=      & 0 + (1-c){{5e^6 - 6e^5 + 1} \over {60 \pi^2 b^2 s_2^5 e^6}}
                + (1-c)\left({{e-1} \over {10 \pi^2 b^2 e}}\right) \left[{1 \over {s_1^5 e^5}} - {1 \over {s_2^5}}\right]
                + (1-c){{e^6 - 6e + 5} \over {60 \pi^2 b^2 s_1^5e^6}} \\
        &=      & (1-c)2.55 \times 10^{-5}              \\
\sigma_H^2      & =     & E_H(v)^2 - E_H(v^2) \\
        &=      & ((1-c)3.26 \times 10^{-4})^2 - (1-c)2.55 \times 10^{-5} \\
        &=      & 1.49 \times 10^{-5} \mbox{ (for c = 0)}
\end{eqnarray*}

For an incorrect hypothesis we look at the problem in two steps. First
we derive, as above, the mean and standard deviation of the process in
which $n=m=4$, {\em i.e.}, a single random image point drops into a
single error circle. From the distribution of $f(V_{\overline{H}})$,
we find:

\begin{eqnarray*}
E_{\overline{H}}(v) & = &\int_0^0 vf(V_{\overline{H}}=v)dv + \int_{\ell_1}^{\ell_2} vf(V_{\overline{H}}=v)dv +
                \int_{\ell_2}^{\ell_3} vf(V_{\overline{H}}=v)dv + \int_{\ell_3}^{\ell_4}v f(V_{\overline{H}}=v)dv \\
                & =     & 0 + {(e-1)^2 \over {R^2 b^2 e^2 s_2}} + {{2(e-1)} \over {R^2
                        b^2 e}}\left[{1 \over {s_1e}} + {1 \over s_2}\right] +
                        {(e-1)^2 \over {R^2 b^2 e^2 s_1}}       \\
        & =     & 3.49 \times 10^{-6} \\
E_{\overline{H}}(v^2)&= &\int_0^0 v^2f(V_{\overline{H}}=v)dv + \int_{\ell_1}^{\ell_2} v^2f(V_{\overline{H}}=v)dv +
                \int_{\ell_2}^{\ell_3} v^2f(V_{\overline{H}}=v)dv + \int_{\ell_3}^{\ell_4}v^2f(V_{\overline{H}}=v)dv \\
        &=      & 0 + {{3e^4 - 4e^3 + 1} \over {12 \pi R^2 b^2 s_2^3 e^4}}
                + \left({{e-1} \over {3 \pi R^2 b^2 e}}\right) \left[{1 \over {s_1^3 e^3}} - {1 \over {s_2^3}}\right]
                + {{e^4 - 4e + 3} \over {12 \pi R^2 b^2 s_1^3e^4}} \\
        &=      & 1.30 \times 10^{-8}           \\
\sigma_{\overline{H}}^2(v)      & =     & E_{\overline{H}}(v)^2 - E_{\overline{H}}(v^2) \\
        &=      & 1.30 \times 10^{-8}
\end{eqnarray*}

for $R=500$.

Now, consider a single random image point (i.e., $n=4$; three for the
hypothesis and one left over) dropped into an image where a model
of size $m>4$ is hypothesized to be. In this case the event that the
random point will contribute weight $v$ to this hypothesis is
calculated as follows: Let event $A_i=$ ``point drops in the $i$th
circle.'' Then,

\begin{eqnarray*}
f(V_{\overline{H}_m} = v \mid v \neq 0) &= &f(v \wedge A_1) + f(v \wedge A_2)
+ \ldots + f(v \wedge A_{m-3}) \\
&= &(m-3)f(v \wedge A_1)
\end{eqnarray*}

Note that because we are assuming the circles are disjoint, we are
overestimating the probability of the point falling in any circle.
The actual rate of detection will be lower than our assumption,
especially as the $m$ grows large.

\begin{eqnarray*}
f(V_{\overline{H}_m}) &=&\cases
        {1 - (m-3){{4\pi} \over {R^2b^2}}[s_2-s_1] & v=0 \cr
        (m-3){{2\pi} \over {R^2b^2v}}[s_2 - {1 \over {e\sqrt{2\pi v}}}] &
                                $\ell_1 < v \leq \ell_2$ \cr
        (m-3){{2\pi} \over {R^2b^2v}}[{{e-1} \over {e\sqrt{2\pi v}}}] & 
                                $\ell_2 < v \leq \ell_3$ \cr
        (m-3){{2\pi} \over {R^2b^2v}}[{1 \over \sqrt{2\pi v}} - s_1] &
                                $\ell_3 < v \leq \ell_4$ \cr
                0 & otherwise} 
\end{eqnarray*}

As $m$ grows large, $(1-(m-3){{4\pi} \over {R^2b^2}}[s_2-s_1]) < 0$ so
this expression is no longer a density function. This is the point at which the model
covers so much of the image that a random point will {\em always}
contribute to some incorrect hypothesis. Therefore, this analysis only
applies to models for which which $m < {{R^2b^2} \over
{r\pi[s_2-s_1]}}+3$. For $R=500, m \leq 60$, and for $R=256, m \leq
18$.

The mean and standard deviation for one random point dropping into $m-3$
random circles is:

\begin{eqnarray*}
E_{\overline{H}_m}(v) & = &\int_0^0 vf(V_{\overline{H}_m})dv +
                        \int_{\ell_1}^{\ell_2}vf(V_{\overline{H}_m})dv + 
                        \int_{\ell_2}^{\ell_3}vf(V_{\overline{H}_m})dv +
                        \int_{\ell_3}^{\ell_4}vf(V_{\overline{H}_m})dv \\
                & = & 0 + \int_{\ell_1}^{\ell_2}v[(m-3)f(V_{\overline{H}})]dv +
                        \int_{\ell_2}^{\ell_3}v[(m-3)f(V_{\overline{H}})]dv +
                        \int_{\ell_3}^{\ell_4}v [(m-3) f(V_{\overline{H}_m})]dv \\
                & = &(m-3)\left[\int_{\ell_1}^{\ell_2}vf(V_{\overline{H}})dv +
                        \int_{\ell_2}^{\ell_3}vf(V_{\overline{H}})dv + 
                        \int_{\ell_3}^{\ell_4}v f(V_{\overline{H}})dv \right]\\
                & = &(m-3)E_{\overline{H}}(v) \\
E_{\overline{H}_m}(v^2) & = &\int_0^0 v^2f(V_{\overline{H}_m})dv +
                        \int_{\ell_1}^{\ell_2}v^2f(V_{\overline{H}_m})dv + 
                        \int_{\ell_2}^{\ell_3}v^2f(V_{\overline{H}_m})dv +
                        \int_{\ell_3}^{\ell_4}v^2f(V_{\overline{H}_m})dv \\
                & = & 0 + \int_{\ell_1}^{\ell_2}v^2[(m-3)f(V_{\overline{H}})]dv +
                        \int_{\ell_2}^{\ell_3}v^2[(m-3)f(V_{\overline{H}})]dv +
                        \int_{\ell_3}^{\ell_4}v^2[(m-3) f(V_{\overline{H}_m})]dv \\
                & = &(m-3)\left[\int_{\ell_1}^{\ell_2}v^2f(V_{\overline{H}})dv +
                        \int_{\ell_2}^{\ell_3}v^2f(V_{\overline{H}})dv + 
                        \int_{\ell_3}^{\ell_4}v^2f(V_{\overline{H}})dv \right]\\
                & = &(m-3)E_{\overline{H}}(v^2) \\
\sigma_{\overline{H}_m}^2(v)    & =     & E_{\overline{H}_m}(v)^2 - E_{\overline{H}_m}(v^2) \\
        &=      & (m-3)^2E_{\overline{H}}(v)^2 - (m-3)E_{\overline{H}}(v^2) \\
\end{eqnarray*}

Dropping $n$ points convolves this distribution with itself $n-3$ times:

\begin{eqnarray*}
f(W_{\overline{H}_{m,n}} = v) &= &f(V_{\overline{H}_{m_1}}) \otimes
\ldots \otimes f(V_{\overline{H}_{m_{n-3}}}) \\
\end{eqnarray*}

And therefore the weight that an $n$-size random image contributes to
an incorrectly hypothesized model of size $m$ follows the distribution:

$$N((n-3)E_{\overline{H}_m}, (n-3)\sigma_{\overline{H}_m}^2)$$

Note that this is the weight density of a single incorrect hypothesis.

The means for both distributions were tested empirically from the
same experiment as shown in Figures \ref{dists}.  A table of values is
given in figure \ref{disttable}.

\begin{figure}
\begin{center}
\begin{tabular}{|| l | c | c | c | c | c | c ||} \hline
& \multicolumn{3}{c |} {Mean} & \multicolumn{3}{c ||} {Variance} \\ \hline
With $M$ & Predicted & Empirical & Pred/Emp & Predicted & Emp & Pred/Emp \\ \hline
m-3=n-3=1 & 3.2574E-3 & 3.7156E-3 & 0.876 & 1.4883E-5 & 1.4380E-5 & 1.035 \\
m-3=n-3=5 & 1.6287E-2 & 1.9860E-2 & 0.820 & 7.4415E-5 & 1.3944E-4 & 0.532 \\
m-3=n-3=10 & 3.2574E-2 & 4.0926E-2 & 0.796 & 1.4883E-4 & 5.1346E-4 & 0.290 \\
m-3=n-3=20 &  6.5147E-2 & 8.3265E-2 & 0.782 &  2.9766E-4 & 1.5543E-3 & 0.191 \\
\hline \hline
& \multicolumn{3}{c |} {Mean} & \multicolumn{3}{c ||} {Variance} \\ \hline
Without $M$& Predicted & Empirical & Pred/Emp & Predicted & Emp & Pred/Emp \\ \hline
m-3=1,n-3=1 & 3.4905E-6 & 3.2672E-6 & 1.068 & 1.3017E-8 & 1.6757E-8 & 0.777 \\
m-3=1,n-3=5 &  1.7452E-5 & 2.3562E-5 & 0.741 &  6.5086E-8 & 1.6520E-7 & 0.394 \\
m-3=1,n-3=10 & 3.4905E-5 & 4.9344E-5 & 0.707 &  1.3017E-7 & 3.2191E-7 & 0.404 \\
m-3=1,n-3=20 &  6.9809E-5 & 8.6947E-5 & 0.803 &  2.6034E-7 & 4.6661E-7 & 0.558 \\
m-3=5,n-3=1 & 1.7452E-5 & 1.5938E-5 & 1.095 & 6.4843E-8 & 8.9322E-8 & 0.726 \\
m-3=10,n-3=1 & 3.4905E-5 & 3.3353E-5 & 1.047 &  1.2908E-7 & 2.6706E-7 & 0.483 \\
m-3=20,n-3=1 &  6.9809E-5 & 3.7706E-5 & 1.852 & 2.5572E-7 & 2.5121E-7 & 1.018 \\
\hline
\end{tabular}
\end{center}
\caption{}
\label{disttable}
\end{figure}

\section{Comparing Results to the Uniform Case}

We compare the results of the previous section to the case of bounded
uniform error by plotting the results as an ROC curve for different
$(m,n)$ pairs. An ROC curve (receiver operating characteristic) is a
concept loosely borrowed from EE in which we plot P(Detection) vs
P(False Alarm) for different numbers of model and image points and
different threshold levels. A single ROC curve is formed by the
$(\theta, Pf, Pd)$ triples associated with a fixed $(m,n)$ pair.

For example, in figure \ref{ROCex} we show 4 different ROC curves for
the Gaussian error model analysis; for all four curves $m-3=1$, and from
top to bottom we have $n-3=1,10,100,1000$. Though an ROC curve is a 3D
entity, we display it projected along the $\theta=0$ plane and can
easily find the associated $\theta$ value for any $(Pf, Pd)$ pair.

\begin{figure}
\csfig{4in}{ROCex2.ps}
\caption{ROC curves for $m-3=1$, and from top to bottom, $n-3=1,10,100,1000$}
\label{ROCex}
\end{figure}

When the threshhold is high there is a 0 probability of false
negative, but a 0 probability of correct identification as well.  As
the threshhold goes down, the probabilities of both occurences go up
until the threshhold is so low that both positive and false
identification are certain. The goal is to pick a threshold such that
we have a very high probability of identification and a low
probability of false positives, i.e., we are interested in points
above the diagonal $x=y$. Note that when $n-3=1$, there exists a
threshhold such that $Pd=.78$ and $Pf=0$, However when $n-3=1000$ there
exists no threshhold such that even $Pd>Pf$.

The next examples show the predicted comparison of the gaussian model
to the uniform model. Figure \ref{ROCs0} shows the ROC curves for the
Gaussian model and uniform models, $m-3=10$,$n-3=10,50,100,500,1000$,
occlusion=0. We can see that in the case of no occlusion, both models
predict good Pf vs Pd curves, though the uniform model will always
better because there is no possibility of false negative for
occlusion=0. We see that at $n-3=500$, the gaussian model breaks down
while the uniform model still performs well.  However, the moment we
allow for {\em any} weakening of the no occlusion assumption, the
uniform model breaks down rapidly.  Figure \ref{ROCs25} shows the
same two plots, but for a more realistic assumption of occlusion =
0.25.  Here was see the uniform case degrading rapidly as clutter goes
up, while the gaussian model still performs well for the same amount
of clutter and occlusion.

Using this technique, we can predict threshholds for actual
experiments whose results are shown in the next section.

\begin{figure}
\parbox{6,5in}{
\begin{center}
\parbox{4in}{\csfig{4in}{uROC0.ps}} \\
\parbox{4in}{\csfig{4in}{gROC0.ps}}
\end{center}}
\caption{Comparisons of uniform and Gaussian error models for
$m-3=10$, $n-3=10,50,100,500$, occlusion=0.}
\label{ROCs0}
\end{figure}


\begin{figure}
\parbox{6.5in}{
\begin{center}
\parbox{4in}{\csfig{4in}{uROC25.ps}} \\
\parbox{4in}{\csfig{4in}{gROC25.ps}}
\end{center}}
\caption{Comparisons of uniform and Gaussian error models for
$m-3=10$, $n-3=10,50,100,500$, occlusion=.25.}
\label{ROCs25}
\end{figure}

\section{Experiment}

The predictions of the previous section were tested in the following
experiment: to test an ROC curve for model size $m$, image size $n$,
we run two sets of trials, one to test the probability of detection
and one to test the probability of false alarm. For the former, a
random model of size $m$ consisting of point features was generated
and projected into an image, with gaussian noise ($\sigma = 2.5$)
added to both the x and y positional components of each point feature.
Occlusion ($c$) is simulated by adding a $c$ probability of not
appearing in the resulting image for each point. Only correct
correspondences are tested, and the weight of each of these correct
hypotheses is found using the algorithm:

\begin{itemize}
\item[(a)] for a correct hypothesis $(m_0:i_0, m_1:i_1, m_2:i_2)$
\begin{itemize}
\item[] for every other model point $m_j$
\begin{itemize}
\item[(i)] find coordinates $m_j = (\alpha_j, \beta_j)$ with respect
to basis $(m_0, m_1, m_2)$, and from this,  $\sigma_e = f(\alpha_j,\beta_j)$.
\item[(ii)] Project $m_j$ into the image and find the minimum distance $d$
between $i_j$ and any other image point such that $d \leq 2\sigma_e$.
Add $v = \twodgauss{d^2}{\sigma_e}$ to the supporting weight for this
hypothesis.
\end{itemize}
\end{itemize}
\item[(b)] If the weight of the vote for this hypothesis is greater
than some threshhold $\theta$, stop and output this as a correct
instance of the model.
\end{itemize}

For our experiment, we loop through thresholds from 0 to $E_H(v)$, and
for every threshold we run the above algorithm enough times to get
$100$ sample points. The result for $m-3=10$, occlusion $c=0.25$ are
shown in figure \ref{Pd10.25}.

To test the probability of false alarm, we run the same experiment
exactly, except we use random images which do not contain the model we
are looking for. We loop through the same thresholds as in the
previous case to get a set of $(Pf,Pd)$ pairs for each threshold. The
resulting $Pf$ curves are shown in \ref{Pf+ROC.25} for $n-3 = 10, 50,
100$, occlusion $c=0.25$. The ROC curves for the same parameters are
shown alongside.

From the results we see that the predictions for the Pd curve are
slightly lower than the empirical results, and that the predictions
for the Pf curve are higher. The discrepancy in the latter curve can
be tracked down to one of our original assumptions, namely, that the
distribution $f_{\overline{H}}$ convolved with itself a sufficiently
large number of times yields a Gaussian distribution. Apparently, for
$n-3=100$ the resulting distribution is not sufficiently Gaussian and
the bulk of the area under the distribution still occurs very close to
$0$. Therefore, $\int f(W_{\overline{H}_{m,n}})$ goes to $1$
almost immediately, and so $1-\int f(W_{\overline{H}_{m,n}})$ goes to
$0$ much faster than predicted.

Despite this discrepancy we still have what we want, for the
underprediction of the Pf curve has the effect of placing a predicted
$(Pf,Pd)$ point over to the right of its actual location, and the
overprediction serves to move it a little lower than its actual
location. Therefore, any threshhold we pick by inspecting the
predicted ROC curve will actually perform better than our prediction,
and what we have achieved is reliable lower bound for the performance
of our technique.

\begin{figure}
\csfig{4in}{Pd10100.25.ps}
\caption{Comparison of predicted to empirical curve for probability of detection,
$m-3=10$, occlusion $c=0.25$.}
\label{Pd10.25}
\end{figure}

\begin{figure}
\parbox{6.5in}{
\begin{center}
\parbox{3in}{\csfig{3in}{Pf1010.25.ps}}
\parbox{3in}{\csfig{3in}{ROC1010.25.ps}} \\
\parbox{3in}{\csfig{3in}{Pf1050.25.ps}}
\parbox{3in}{\csfig{3in}{ROC1050.25.ps}} \\
\parbox{3in}{\csfig{3in}{Pf10100.25.ps}}
\parbox{3in}{\csfig{3in}{ROC10100.25.ps}}
\end{center}}
\caption{Comparison of predicted to empirical curve for probability of
false alarm, and alongside, the implied ROC curve using the results of
the previous figure. From top to bottom, $n-3=10,50,100$.}
\label{Pf+ROC.25}
\end{figure}

\section{Related Work and Directions for the PhD Research}

The geometric hashing method was introduced by Lamdan, Schwartz and
Wolfson in 1987. The first error analysis of the geometric hashing
technique was done by Grimson, Huttenlocher and Jacobs, who showed
that with even very small amounts of noise and spurious features, the
technique had a very high probability of false positives. However,
they assumed that the error was uniform and bounded, which is a
worst-case scenario and places an upper bound on the error rate. As we
have shown here, with a Gaussian error assumption we can do much
better.

Costa, Haralick, and Shapiro demonstrated another error analysis
\cite{CHS}  also based on a 2D Gaussian noise distribution associated
with each point. Their analysis differs from this one technically in
many respects, but the main focus of their work is specifically to
make the geometric hashing method work as well as possible, not to
analyze the effects of noise and to characterize under what conditions
it will and will not prove effective. 

In closing, there are several areas in this work which have not been
discussed. First of all, it is important to point out that this is not
a Bayesian technique since it makes no assumptions about the {\em a
priori} presence or absence of the model we are looking for. However,
if one did have such a distribution, it could easily be factored into
the ROC formulation, as well as the cost associated with making a
mistake in either direction.

There are several assumptions I have made in this work whose validity
should be tested, for instance, the assumption that our sensor noise
is Gaussian with mean 0. Also, there are times at which I assume that
adding the sum of $n$ equidistributed random variables produces a
distribution which is Gaussian. In the limit this is true, but the
question remains as to how large $n$ should be for the assumption to
be adequately close to reality. Also, the evaluation function I chose
was somewhat arbitrary, and it would be interesting to show whether an
optimal evaluation function exists and how to find it.

The probability distributions that I have assumed in this analysis
have been the most random possible. Sometimes though, we may know
something more about these distributions --- for instance, the models
we're working with may all be rectangular, or possibly there are
certain poses which are far more likely to occur (for instance, you
would hardly ever expect to see an upside-down pyramid), or the noise
is not Gaussian but rather skewed in some way. It would be interesting
to investigate how we can incorporate the extra knowledge we have
about the distributions into this analysis.

There are many areas of vision in which an analysis of this sort has
not been done and would be useful --- for instance, Hough transforms
or stereo matching. My goal for this thesis however is to do an
analysis in the same domain, namely, recognition of planar objects,
but using line segments to do hypothesis formulation instead of point
features. With the results of this analysis I plan to demonstrate the
usefulness of the approach by building a small example of a
multi-sensor fusion system consisting of three modules: a recognizer
based on point features, a recognizer based on line segments, and a
third module which conceptually sits above these two and is able to
choose between the outputs of both modules, based on the
characteristics of the input noise and their effect upon the certainty
of each module's outputs. Though I have not yet done preliminary
tests, it is not unreasonable to assume the input noise to be
dependent on environmental conditions such as lighting, distance
between camera to the scene of interest, or other as yet unanticipated
factors. I expect that changes in conditions will affect the noise of
each module differently, and that given some other sensor to assess
the environmental conditions (a light meter for example), the
integrated system will be able to perform better than a system
consisting of only one or the other module separately.

\nocite{LSW}

\bibliography{bib}

\end{document}
