%* 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}