\documentstyle[12pt,aim2col, psadobe-kl]{article} \begin{document} \onecolumn \begin{titlepage} \advance\topmargin by 0.5in \begin{center} \vspace{1.0in} {\large MASSACHUSETTS INSTITUTE OF TECHNOLOGY\\} \vspace{.05in} {\large ARTIFICIAL INTELLIGENCE LABORATORY\\} \vspace{.05in} \end{center} \vspace{.2in} {\large A.I. Memo No.\ ??? \hfill July, 1995 \par} \vspace{.2in} \begin{center} {\huge\bf Model Based Correspondence for Object Recognition} \\ \bigskip \bigskip {\Large\bf Pamela Lipson and Shimon Ullman}\\ {\normalsize This publication can be retrieved by anonymous ftp to publications.ai.mit.edu.} \end{center} \vfill \begin{abstract} {\normalsize\noindent Most model-based methods for object recognition require a detailed knowledge of the correspondence between model and image features. Correspondence, however, is a difficult problem in its own right. We suggest a model-based technique to establish image-to-model correspondence and, therefore, to facilitate the recognition of objects. Our correspondence approach uses the model to guide and constrain the matching process. We use the model to roughly align image and model features. We then derive an estimate of a sparse number of matching model and image contours. Finally, we constrain the rest of the matches via global information from the model. These stages can repeated to refine the resulting correspondence. We have incorporated our technique into the linear combination object recognition scheme and have tested the entire system successfully on a variety of objects. There are four benefits to our approach. First, it is computationally simple. Second it is efficient; the use of models constrains the matches in a linear fashion. Third, it is effective; experiments show that our procedure quickly converges to a solution, if one exists. Finally, the procedure is robust; errors in the rough alignment stage do not impair the subsequent correspondence procedure. \par} \end{abstract} \vfill \begin{center} \footnotesize Copyright \copyright\ Massachusetts Institute of Technology, 1995 \end{center} \vspace{.25in} {\footnotesize \noindent This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the laboratory's artificial intelligence research is provided in part by National Science Foundation, contract number IRI 8900267, and in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-85-K-0124. The addresses of the authors are : Pamela Lipson, NE43-739, MIT AI Laboratory, 545 Technology Square, Cambridge, MA 02139, USA. Email: lipson@ai.mit.edu. Shimon Ullman, Dept. of Applied Math and Computer Science, Weizmann Institute of Science, Rehovot, 76100, Israel. Email: shimon@wisdom.weizmann.ac.il \vfill \par} \end{titlepage} \bibliographystyle{plain} \twocolumn \section{Introduction} Object recognition, by definition, is a model based task. The goal of a recognition system is to decide whether an input image contains one or more objects seen previously. This requires a comparison of the observed image with prestored representations (or models) of known objects. A key task of many model-based recognition schemes involves establishing a correspondence between the image and a stored model. For instance, alignment style recognition uses correspondences between image and model features to recover a valid transformation that takes the model and maps it onto the image \cite{Ullbasri89}. If the resulting warped model is similar to the image, the image is said to be an instance of the model. Full alignment schemes require exact point to point correspondence. Examples include recognition techniques based on linear mappings and generalized radial basis functions \cite{Ullbasri89,Poggio90}. Minimal alignment techniques such as the linear combination of views approach utilizes a correspondence between a few key image and model features. Other examples of minimal alignment techniques which utilize feature correspondences include \cite{Grimson89,GrimHut89,GrimTlp84,Huttenlocher88,HutUllman87,Lowe84,Pollard87}. Another type of model-based object recognition is the invariant properties approach. This approach assumes the existence of object properties that remain constant under changes in object pose, scale, lighting, and small non-rigid deformations. Many such schemes require image and model feature coordinates in a fixed or corresponding order for the construction of the invariant in question. Examples include Vijayakumar {\it et al.} who extract bitangents from the image in a fixed order and use the distances between them to compute an invariant \cite{Kriegman95}. Other invariant approaches which require initial correspondences include \cite{Mundy92} and \cite{Shashua}. There do exist some schemes such as Grossberg's ART system \cite{Grossberg82} which utilize model and image feature matches as an input to a verification step, rather than in the initial part of the recognition process. Although a correspondence stage is a critical component of many recognition schemes, it is difficult to compute due to the complexity of the space of possible image and model pairs. If there are $m$ model features and $i$ image features, the upper bound on the number of possible pairings is $m^i$. Some minimal alignment techniques have reduced this upper bound to one that is polynomial in the number of image and model features \cite{HutUllman87}. However, even this is a daunting number for all but the very simplest scenarios. Traditional techniques for computing correspondence follow a "bottom up" approach, which implies a uni-directional flow of computation beginning with an analysis of image properties at the pixel level and producing successively more abstract/complex features. These abstract image features are then matched with all possible features in the model. Most techniques of this flavor use heuristic rules based on local image feature and model feature properties to rule out incorrect matches. We argue that there are two problems which hamper such an approach from efficiently and reliably finding model and image correspondences. First, the abstraction process of translating image attributes into more abstract features is performed without the use of any model/scene specific knowledge. As a result, the chosen image features may not have much meaning with respect to the features present in the model \cite{Brooks81}. In addition, the heuristic rules to eliminate incorrect matchings are often ineffective because local image feature and model feature properties are usually insufficient to rule out possible pairings (see figure~\ref{fig:local}). We suggest that a more efficient and robust correspondence technique can be created by introducing ``top down'' or model-specific knowledge in the matching process. This type of approach would allow model-based knowledge to influence the extraction of features from the input images and to constrain the set of possible matches. (In essence, this allows model information to be compared to image information at any level in the flow of computation.) The use of model-driven data, we argue, has three main advantages. First, such an approach offers a great latitude in the types of features to match. Model and image features may no longer be constrained to non-distinctive constructions such as points, T-junctions, and corners nor to non-robust constructions such as complex blobs. Constraints from the model may allow us to match robust {\it and} distinctive (but hard to characterize) features such as curves. A second advantage is that we can roughly distort the model to match the image. This has the advantage of bringing model features into closer spatial correspondence thereby shrinking the search space and reducing the number of false matches. The third advantage is that we can choose the set of model and image correspondences that are globally consistent with the model. This added constraint further reduces the problem's complexity (see figure~\ref{fig:global}). \begin{figure} \fbox{\psadobepercent{50}{/home/vg/lipson/CorrespIJCV/local.epsf}} \caption{\it One of the disadvantages of using only ``bottom up'' information in the matching process. Two pictures of a VW are shown. One represents the model and the other the image. The goal is to find a correspondence between image and model features. One model corner feature and one image corner feature are highlighted. Looking at these two features in isolation, or in a ``bottom up'' manner, it is difficult to decide whether these are a matching pair.} \label{fig:local} \end{figure} \begin{figure} \fbox{\psadobepercent{50}{/home/vg/lipson/CorrespIJCV/global.epsf}} \caption{\it The advantages of adding ``top down'' information to the matching process. The two pictures of the VW are replicated from figure~\ref{fig:local}. (a) Using ``top down'' information, we can distort the model to match some characteristics of the image in order to bring model and image features into closer spatial proximity. (b) We can choose image and model feature pairs that are globally consistent with the model. This figure shows two corner features highlighted on both the image and the model. Unlike the ambiguity we found in figure~\ref{fig:local}, our model-based constraints suggest we reject the match of the model feature in the circle and image figure in the square for the more globally consistent match of model and image feature in the circles and the match of the model and image figures enclosed in squares. Both (a) and (b) shrink the space of possible matches and reduce the possibility of false correspondences.} \label{fig:global} \end{figure} In this paper, we present a solution to the correspondence problem that utilizes model driven information. The remainder of this paper presents our model-guided approach to correspondence within the framework of a particular model-based recognition system. The particular system we implemented uses view-based models, contours as features, and a linear combination recognition engine. Sections~\ref{sec:models} and~\ref{sec:features} discuss the motivation behind our choice of pictorial models and contour features. Section~\ref{sec:contours} argues that our approach to correspondence is especially effective in these domains. In section~\ref{sec:algorithm}, we present the details of our model-guided contour matching algorithm. Section~\ref{sec:implementation} describes our implementation. In section~\ref{sec:results}, we show examples of our approach tested on a range of synthetic and natural models and images within a recognition application. \section{Why view-based models?} \label{sec:models} The choice of object model representations is critical to the correspondence stage. The chosen representation influences the type of model features used, the type of image features extracted, and the internals of the matching process. Models fall into either the two-dimensional or three-dimensional category. Orthogonally, they range in complexity from sparse to detailed representations. It would seem that the obvious way to model a three-dimensional object is via a three-dimensional representation of that object since such a representation implicitly contains full knowledge about all the views of the object, the connectivity of subparts, and depth information. The disadvantages of this model type include the difficulty of generating and storing the detailed model and determining a transformation of the model to 2D views so that it can be compared with the two-dimensional observed image. In addition, recent psychophysical evidence has shifted the attention away from using full three-dimensional models \cite{Bultoff92,Edelman90,EdelmanPog90}. Studies suggest that the human visual system recognizes images by matching them with previously stored two-dimensional views without the use of three-dimensional representations. Given the computational disadvantages of 3D models and the psychophysical evidence against them, some recent approaches have attempted to treat models as sets of two-dimensional pictures (see figure~\ref{fig:2D-models}). This modeling strategy is known as the pictorial approach. One scheme which uses pictorial models is recognition by linear combination of views \cite{Ullbasri89}. The linear combination approach utilizes the fact that a picture of an object decomposed into points can be represented by a linear combination of the corresponding points on a fixed number of other 2D views of the same object. The benefits of incorporating pictorial models into a model-based recognition scheme are that 1) the models are simple to generate and store and 2) that they are in the same format as the images. \begin{figure} \begin{center} \fbox{\psadobepercent{70}{/home/vg/lipson/CorrespIJCV/pictorial-vw.epsf}} \end{center} \caption{\it Example of a pictorial model of a VW.} \label{fig:2D-models} \end{figure} \section{Why contours as image and model features?} \label{sec:features} A good feature representation should be distinguishable, reliable in the face of noise and occlusion, stable over changes in viewpoint, easy to compute, and sparse in terms of description. Unfortunately, no single feature type explored thus far has been able to satisfy these hefty criteria. Features that are distinguishable such as object parts are often prone to noise, prone to occlusion, unstable over changes in viewpoint, difficult to compute, and expensive in terms of storage. Alternatively, those that are easy to compute and robust such as points or vertices are often indistinguishable from each other. A poor feature representation can greatly hinder the success of any correspondence process. Figure~\ref{fig:car_contours} shows a line representation of a car. Most methods to determine correspondence attempt to extract explicit features from images like this one and then match them to their equivalents in models. Some examples of local explicit features are points, corners, vertices (where several edges meet), blobs, cusps, and inflection points. Object parts and centers of salient features typify more global explicit features \cite{Ullman89}. Some of these explicit features are highlighted in figure~\ref{fig:car_contours}b. \begin{figure} \fbox{\psadobepercent{55}{/home/vg/lipson/CorrespIJCV/car_contours.epsf}} \caption{\it Representations for Features. (a) A real image. (b) Some possible explicit features such as points, lines, corners, and parallel lines. (c) A few contours that could be used as features are highlighted.} \label{fig:car_contours} \end{figure} Looking again at the explicit features in ~\ref{fig:car_contours}b, it is obvious that a lot of information in the image is lost in the translation process from raw image data to explicit features. In particular, the curved segments, which constitute a large majority of images, are ignored. The curves, however, can provide a wealth of data to the correspondence process. In addition, they can be viewed as local features and also seen as a global arrangement, providing a solution to the distinctiveness vs. robustness problem. They also allow for some invariance to lighting and changes in viewpoint, to which explicit shape features are quite sensitive. If features like contours could be matched, one might be more confident in the correspondence recovery process. We choose to define contours as collections of points that are roughly connected in the image. Given this definition, contours are easy to generate, via a rudimentary edge-detection processing step. (No further abstraction beyond edge-detection is required.) Additionally, they are simple to store as image data. \section{``Top down'' information is important for contour matching} \label{sec:contours} Contours traditionally have been ruled out as a possible feature representations. There is an inherent ambiguity in matching contours. Additionally, they are hard to characterize, and therefore, difficult to use as "explicit" features. Both issues must be addressed before they can be used as features in a model-based recognition system. The idea of general contour matching is best formulated in work related to the recovery of optical flow fields from short-range motion. The basic idea is to best recover the structure of a moving three-dimensional object from a series of two-dimensional pictures, taken over short temporal and spatial intervals \cite{Hildreth84,Horn81}. This is performed by tracking a set of features in each of the frames. The major problem in computing optical flow fields is that only motion perpendicular to these features can be accurately established \cite{Marr}. The other components of motion must be inferred. This is commonly known as the aperture problem (see figure~\ref{fig:aperture}). \begin{figure} \begin{center} \fbox{\psadobepercent{80}{/home/vg/lipson/CorrespIJCV/new_aperture.epsf}} \end{center} \caption{\it The aperture problem - Looking through a local aperture a point on contour 1 may match with any of an infinite number of points on contour 2.} \label{fig:aperture} \end{figure} Because contour matching is ambiguous, attempts to resolve the problem within the optical flow domain have been based on general constraints such as smoothness or assumptions of local affine motion fields \cite{Bachelder91,Hildreth90}. It seems as though one could utilize the ideas developed in the field of apparent motion to match contours in a recognition application. In the domain of object recognition we actually have additional information to aid the situation. In recognition we are dealing by definition with familiar objects and therefore can use the knowledge associated with these objects to try counteract the aperture problem. The downside is that within a recognition domain we have no time varying imagery to work with. Thus, we cannot technically compute the normal component of motion required in each of the optical flow schemes described above. In addition, different views of an object often appear highly dissimilar, violating the close spatial proximity assumption of short-range motion. "Bottom up" correspondence strategies do not utilize any of the benefits derived from model information. Without any global information there is no meaningful way to interpret the image as a global arrangement of local contours. In addition, "bottom up" strategies have no ammunition to counteract the aperture problem. Therefore, they are insufficient to cope with the disadvantages of characterizing and matching contours. We suggest that the addition of ``top down'' or model information acts as an appropriate constraint for the interpretation of the image data. The model provides information regarding the arrangement or structure of the contours. Anchor points in both the model and the image can bring the two into close registration. The model also provides the information necessary to compute an analog of the "normal component'' of motion. Finally, given this model-based ``normal component of motion'' one can incorporate techniques related to motion analysis to determine a fine correspondence between contours. \section{ Model-guided correspondence} \label{sec:algorithm} The purpose of this paper is show that the model ("top down data"), in conjunction with "bottom up'' data, may provide valuable information which can direct or guide the correspondence process. Traditional "bottom up approaches" may have to match all image features to all possible model features before the search for a consistent pairing is terminated. We suggest that an efficient algorithm for computing correspondence is to first roughly distort the image to match the model to constrain the possible search space, then to get a rough match of a minimal set of features in a "bottom up" fashion, and finally use the model to constrain and refine the rest of the matches. The reduction in complexity of the problem through such an approach is illustrated in figure~\ref{fig:complexity}. \begin{figure} \begin{center} \fbox{\psadobepercent{40}{/home/vg/lipson/CorrespIJCV/new_complexity.epsf}} \end{center} \caption{\it The advantages of using the model to guide the correspondence process over a purely "bottom-up" approach. (a) The "bottom" up approach may have to evaluate all the possible pairings of image and model features. The graphic depicts a search tree where every model feature is compared to every image feature. The leaves of the tree represent the set of all the possible image-model feature pairings (b) Our technique uses the model to constrain the complexity in two ways. Looking at the tree above the horizontal dotted line, we reduce the search for a few initial correspondences by roughly distorting the model to match the image. The rest of the search tree below the dotted line is eliminated as we employ "top down" information to constrain and refine the rest of the feature correspondences without any additional search.} \label{fig:complexity} \end{figure} Our proposed algorithm for computing correspondence between a model and an image is summarized pictorially in figure~\ref{fig:overview}. The inputs to the system are a set of two-dimensional model pictures and an image. We use contours as both image and model features. The correspondence algorithm proceeds in four distinct steps: \begin{figure} \begin{center} \fbox{\psadobepercent{70}{/home/vg/lipson/CorrespIJCV/new_main_alg.epsf}} \end{center} \caption{\it Summary of the proposed correspondence process. The process begins by roughly aligning the image with a model picture. We then postulate rough matches between a few model and image contour points in a "bottom up" fashion. These rough matches are sent to the next stage where they are refined using constraints from the model. Using these matches, we are able compute a transformation that maps the model features onto the image features. The transformed or warped model is compared to the image. We can refine the transformation by feeding the warped model back into the process as one of the model pictures.} \label{fig:overview} \end{figure} 1. {\it Rough Alignment}. We roughly align one of the model pictures to the image, bringing the model and image features into close spatial registration. The decision of which model picture to pick can either be arbitrary or be guided by some simple criteria such as similarity of dominant orientations between the model picture and the image or a least sum of squares analysis. The result is a new image which contains a superimposition of the transformed model and the image. Although this paper does not concentrate on ways to perform rough alignment, experimentally we found that a few simple techniques can be used effectively to achieve this coarse registration. 2. {\it Sparse "Bottom-up" Correspondences}. We first compute a sparse number of "bottom-up" correspondences between contour points from the model picture and contour points from the image. However, because of the aperture problem, described in the previous section, we cannot specify an exact matching between contour points. We, thus, give a range of possible matchings to the next step for refinement. 3. {\it Model-guided matching}. The model-guided matching or fine alignment stage relies heavily on information from the model to produce exact contour matches and to achieve a full point-to-point correspondence. The algorithm capitalizes on our result that the information from the model allows contour matching to become possible within a recognition application. We incorporate some ideas from recovery of optical flow to implement this procedure. The basic premise is to match image and model curves using local tangential constraint lines and global model information. In this step, the contours are matched simultaneously to achieve a stable, globally consistent solution. 4. {\it Verification and Iterative Refinement}. The resulting correspondence is used to determine a transformation that takes the model and brings it into alignment with the image. A verification stage determines the validity of the transformation. It is possible to further refine the transformation by repeating the whole process again using the warped model and the image as inputs. Our theoretical and our experimental results demonstrate that our technique is efficient, proceeding a linear fashion with few iterations, and robust, allowing for errors in the rough alignment stage. In the next section, we elaborate on the details of our correspondence algorithm. \section{Our Implementation} \label{sec:implementation} In our implementation, we make several assumptions about the contents of the image and the model used in the recognition process. First, we assume that segmentation has already been performed, meaning that there is only one object in the image, and that the image was generated under orthographic projection. Also, our algorithm utilizes two-dimensional edge data. Therefore, both the image and model pictures should contain only contours. Furthermore, we desire a detailed model of an object. Pictures which comprise the model should be taken at reasonably small changes in viewing geometry to allow for a detailed representation. We assume at most 30 degree rotations between model pictures. We also assume that we know the correspondence between points in different model images. This is not an unreasonable assumption given the fact that we construct the models before the start of the recognition process. \subsection{The Linear Combination Approach to Recognition} We have chosen to test our model-driven approach to correspondence by embedding it in the linear combination of views framework for model-based object recognition \cite{Ullbasri89}. Ullman and Basri showed that one can model all the possible views of an object by a linear combination of a small number of fixed two-dimensional views, $\bf m_1, m_2,...m_n$, of the same object. Given an observed image, $\bf{\hat{p}}$, the goal of the recognition procedure is to find coefficients, $\alpha_i$, for each of the pictures in the model, such that the result of the coefficients applied to the model pictures approximates the image (see equation~\ref{eq:linear_comb}). If such coefficients exist, the observed image is ``recognized'' as an instance of the model. The coefficients for the linear combination encode the three-dimensional rotation, translation, and scaling transformations that map a model onto a viewed object. The process of recovering these transformations, mapping the model into image space, and comparing the result with the image is known as alignment. \begin{equation} {\bf \hat{p}} = \alpha_{1}{\bf m_1} + \alpha_2{\bf m_2} + \cdots + \alpha_n{\bf m_n} \label{eq:linear_comb} \end{equation} The crux of the problem is to find a correspondence between the model and image features. If a pointwise correspondence is known, it is relatively simple to determine the alignment coefficients by solving an overdetermined set of linear equations. Ullman and Basri showed that within this framework it is possible to use only a small number of corresponding points to align a model of pictures with an observed image \cite{Ullbasri89}. \subsection{Rough Alignment} \label{subsec:rough-alignment} Our correspondence process begins by trying to partially compensate for gross changes in the viewing geometry between an image and a model using only minimal information \cite{Shoham88}. The rough alignment involves an affine transformation of the image (or model) to account for differences in in-plane translations, in-plane rotations, in-depth displacements, small in-depth rotations, and small non-rigid transformations \cite{Ullman89}. We utilize a 4 stage rough alignment procedure. In general, the compensatory rough alignment transformations must be robust in the face of noise and especially in the case of occlusion. Although a complete solution to this problem is beyond the scope of this paper, we do suggest some simple procedures to determine a coarse registration of object and model. Experimentally, we found our 4-stage process to be effective. We illustrate our proposals with the model and image picture pair shown in the first row of figure~\ref{fig:ra}. \begin{figure} \begin{center} \fbox{\psadobepercent{80}{/home/vg/lipson/CorrespIJCV/new_rough-alignment.epsf}} \end{center} \caption{\it The four compensatory transformations involved in our rough alignment process. (a) Aligning the centers of mass compensates for translation in the x-y plane. (b) Aligning the dominant orientations compensates for rotations in the x-y plane. (c) Independent scaling compensates for small rotations in depth, while (d) uniform scaling compensates for translations in depth. (e) shows the net result after all the compensations. (f) After the rough alignment stage, the model and image should be in approximate registration.} \label{fig:ra} \end{figure} 1. {\it Compensating for translations in xy plane}. Looking at the top row in figure~\ref{fig:ra}, the figure of the guitar has been translated to the upper left corner of the image with respect to the model picture. We find that we can compensate for this translation in the $xy$ plane by aligning the centers of mass of the figure in the image and in the model picture. (As previously stated, we assume the existence of only one object in both the image and model picture.) The centers of mass can be determined by calculating the first moments of the image and model points. 2. {\it Compensating for rotations in xy plane}. One method to account for in-plane rotations is to align the dominant orientations of the figures in the image and model pictures. Computing the axis of least inertia of the points in a picture will approximate the dominant orientation of the figure. There is, however, a problem with this technique. The axis of least inertia does not specify a unique direction for the dominant orientation. Some global clues to eliminate the two-way ambiguity are symmetry, distribution of mass, and long lines. More local components such as tangential points, blobs and local texture can be integrated into the process. We, however, assume that our model is detailed enough such that the dominant orientations of one of the model pictures will differ only slightly in angle from the dominant orientation of the image figure. 3. {\it Compensating for rotations in depth}. Small rotations in depth of a 3D object cause its 2D projection to appear as if it has been scaled independently in the $x$ and $y$ directions. This is illustrated in the third row of figure~\ref{fig:ra}. We can measure the overall and dimensions of the figures in the image and model picture. Such a procedure is analogous to determining a bounding box for the figures. Scaling independently in the and directions can compensate for small in-depth rotations or shearing transformations. 4. {\it Compensating for translation in depth}. Translations in depth of a 3D object cause its 2D projection to appear as if it has been scaled uniformly in the $x$ and $y$ directions. We can measure the overall difference in size between the image and model figures. (Some measures of difference include comparing the dimension of greater magnitude between the image figure and model figure or comparing the average $x$ and $y$ dimensions of the boxes bounding the image figure and model figure.) We can scale the image figure uniformly in both dimensions to compensate for this difference. After transforming the image based on compensations for translation, rotation, shearing, and scale we can compare the new image to the model. The result is a good but not perfect alignment of the image and model picture. The subsequent correspondence stages will refine this alignment. \subsection{``Bottom Up'' Matching of Sparse Features} \label{subsec:bottom-up matching} The goal of this stage is to estimate correspondences between a small number of model and image contours. Let $\bf m$ be the model picture that, based on a least sum of squares error analysis, most resembles the observed image, $\bf \hat{p}$. Assume $\bf m$ and $\bf \hat{p}$ have been roughly aligned and that we have a new work image containing a superimposition of the two. From the previous rough alignment step, we assume that model and image features are in reasonably close spatial registration, meaning that the model and image contours are in the same approximate area on the new work image. Using this assumption we approach the matching of contours in a "bottom up" fashion. The output of this stage is a set of possible matching points between the chosen contours. The process of matching contours begins with choosing points which lie on contours in $\bf m$. A sparse number of points are chosen by an arbitrary but uniform sampling of all the model points. Based only on "bottom up" information of proximity, we attempt to match each chosen model contour point $m$ with its corresponding point on an image contour. For each of these points $m$, using a radial search, we produce a guess $i$, where $i$ is the closest image point to the model point $m$. Given our assumptions of a roughly aligned image and model, the true corresponding point to $m$ should be either $i$ or a point somewhere close $i$ along the image contour containing $i$. We represent contours as a collection of local tangent lines. We use the tangent constraint to estimate the matches between image and model contour points. Our tangent representation for contours simplifies the problem of choosing a point along a non-parameterized contour to choosing a point along a parameterized line. We now specify that the corresponding point to $m$ is either point $i$ or some point which lies on the tangent to the image curve at $i$ (see figure~\ref{fig:tan}). It is the goal of the subsequent fine alignment stage to condense the guess from all the points on the tangent to a tangent point $i'$ that is closest to the true corresponding image point. \begin{figure} \begin{center} \fbox{\psadobepercent{80}{/home/vg/lipson/CorrespIJCV/new_tan_line.epsf}} \end{center} \caption{\it We represent contours by local tangent lines. Our assumption is that the match to a model contour point, $m$, is either the radially closest image point, $i$, or a point, $i'$, along the contour-tangent at $i$.} \label{fig:tan} \end{figure} We argue that the local tangent of the contour is a sufficient approximation to the curve. Although the final decision may not be a point lying on the image contour, we have designed the procedure such that we will eventually choose the tangent point which is closest to the real corresponding match. Let $v_x$ and $v_y$ be respectively the $x$ and $y$ components of the tangent vector to the local image curve at $i$. Let $t$ be the distance between $i$ and $i'$ along the tangent vector. Our tangential assumption states that \begin{equation} (i'_x,i'_y)-(i_x,i_y)=t(v_x,v_y) \label{eq:tan} \end{equation} Looking back at equation~\ref{eq:tan}, the known or derivable variables are $(i_x,i_y)$ and $(v_x,v_y)$. $(i_x,i_y)$ is determined from "bottom-up" inspection of the model and image data. $(v_x,v_y)$, which is the local orientation of the tangent to the curve at $i$, can be computed using second moment analysis. We can remove $t$ from the equation by uncoupling the $x$ and $y$ components of equation~\ref{eq:tan} and solving for $t$. The result is the equality \begin{equation} v_{y}i'_{x} - v_{x}i'_{y} = v_{y}i_{x} - v_{x}i_{y} \label{eq:tan2} \end{equation} The only resulting unknowns are $(i'_x,i'_y)$. It is the goal of the next stage to resolve these unknowns using the local tangent constraints and the global model constraints. \subsection{Model-guided Matching} \label{subsec:model-matching} The model-guided matching stage now uses model information to resolve the contour matches in order to produce a detailed pointwise correspondence. This stage simultaneously picks a unique correspondence for each chosen model point via model based constraints. The final solution is the one that best satisfies these constraints (see figure~\ref{fig:model-match}). According to the linear combination approach, a new image of an object can be represented as a linear combination of known (model) pictures of the same object (see equation~\ref{eq:linear_comb}). Equivalently, the coordinates of a point on that image can be calculated by taking a linear combination of the coordinates of its corresponding model points. Thus, given an image point $i'$, if $m_1,m_2,m_3,...,m_n$ are corresponding points in model pictures $1$ through $n$ respectively, then we can write the equations \begin{equation} i'_x = \alpha_{1x}m_{1x} + \alpha_{2x}m_{2x} + \cdots + \alpha_{nx}m_{nx} \label{eq:lin_comb_x} \end{equation} \begin{equation} i'_y = \alpha_{1y}m_{1y} + \alpha_{2y}m_{2y} + \cdots + \alpha_{ny}m_{ny} \label{eq:lin_comb_y} \end{equation} We will use this set of constraints to recover the coordinates for $i'$ (which, as described in the last section is the matching point in the image for the given model point). In the last section, we constrained $i'$ to lie along a tangent line to the image contour at point $i$. We can substitute the right hand sides of equations~\ref{eq:lin_comb_x} and~\ref{eq:lin_comb_y} for $(i'_x,i'_y)$ in equation~\ref{eq:tan2} to achieve equation~\ref{eq:total}. \begin{eqnarray} \lefteqn{v_yi_x - v_xi_y =} \nonumber \\ & & v_y(\alpha_{1x}m_{1x} + \alpha_{2x}m_{2x} + \cdots +\alpha_{nx}m_{nx}) - \nonumber \\ & & v_x(\alpha_{1y}m_{1y} + \alpha_{2y}m_{2y} + \cdots +\alpha_{ny}m_{ny}) \label{eq:total} \end{eqnarray} Now the only unknowns are the linear combination coefficients $(\alpha_{1x},\alpha_{2x},...,\alpha_{nx})$ and $(\alpha_{1y},\alpha_{2y},...,\alpha_{ny})$. We have, thus, reduced the correspondence problem to solving for these coefficients such that they satisfy equation~\ref{eq:total}. Once we recover these coefficients, we can use equations~\ref{eq:lin_comb_x} and~\ref{eq:lin_comb_y} to determine the coordinates of $i'$, which is our ultimate goal. Our technique to determine $(\alpha_{1x},\alpha_{2x},...,\alpha_{nx})$ and $(\alpha_{1y},\alpha_{2y},...,\alpha_{ny})$ generates more than $2n$ equations of the form of equation~\ref{eq:total}. There is one equation for each of the chosen model contour points in $\bf m$. As a result, we can construct an overdetermined set of linear equations and use linear algebra techniques to solve for the unknowns (see \cite{Lipson93} for more details). The following is equation~\ref{eq:total} in matrix form. \begin{eqnarray} \pmatrix{m_{1x}v_y\ldots m_{nx}v_y &-m_{1y}v_x \ldots -m_{ny}v_x} \pmatrix{\alpha_{1x}\cr \vdots\cr \alpha_{nx}\cr \alpha_{1y}\cr \vdots\cr \alpha_{ny}} = \nonumber \\ v_yi_x - v_xi_y \label{eq:matrix} \end{eqnarray} \begin{figure} \begin{center} \fbox{\psadobepercent{60}{/home/vg/lipson/CorrespIJCV/new_model_matching.epsf}} \end{center} \caption{\it The fine alignment stage takes as input the set of possible image contour points that match the selected model contour points. It then uses model guided constraints to pick a unique correspondence for each model point.} \label{fig:model-match} \end{figure} Once we recover the linear combination coefficients that transform the model onto the observed image, we can determine a detailed pointwise model to image correspondence. \subsection{Verification and Iterative Refinement} \begin{figure} \begin{center} \fbox{\psadobepercent{60}{/home/vg/lipson/CorrespIJCV/new_verification.epsf}} \end{center} \caption{\it The process of iterative refinement. After we compute the linear combination coefficients by matching one of the original model pictures and the novel image, we can transform the model and compare the result to the observed image. If we desire a refinement of the coefficients, the transformed model picture can take the place of one of the original model images. We can then repeat the correspondence process with this modified set of model pictures.} \label{fig:verification} \end{figure} The coefficients recovered in the model-guided matching stage represent a {\it hypothesis} as to the transformation that takes the model onto observed image. We can {\it verify} our hypothesis by computing the linear combination of the model pictures and then comparing the result with the observed image. If we have some estimate of tolerance for error in the mapping, we can determine if our solution is correct. One of the benefits of our algorithm is that the reconstructed picture, produced by the linear combination of model pictures, in addition to the image can be fed back into the process and new coefficients determined. The reconstructed picture takes the place of $\bf m$, the chosen model picture . It can be compared to the image using the same techniques described in sectionss~\ref{subsec:rough-alignment},~\ref{subsec:bottom-up matching}, and~\ref{subsec:model-matching} (see figure~\ref{fig:verification}). If the image is truly an instance of the model, repeated refinements of the coefficients should converge to an improved solution. \subsection{Analysis} An analysis of the correspondence technique shows two potential causes of error during the "bottom up" matching of image and model features. Errors usually come at places where the model and image curves violate the local spatial proximity assumption and at also at contour points of high curvature. In the first case, it is possible for a large displacement between model and image contours to remain past the rough alignment stage . Figure~\ref{fig:two-problems}a depicts the scenario where contour points from the model are incorrectly matched to contour points in an image because of an uncorrected large displacement. Experimentally, we found that effect on the process by these incorrect matches can be partially compensated for by correct contour matches at other places in the model and image. Through a series of iterations of the correspondence process, the local spatial proximity assumption becomes valid for an increasing number of image and model contours. To make the process more robust and to decrease the number of iterations, it may be advisable to incorporate more information into the contour correspondence process. One suggestion is to look for geometric similarities between contours as a matching criteria. Another suggestion is to use information about whether contours are labeled as interior or boundary curves. Figure~\ref{fig:two-problems}b depicts the problem arising from high curvature contours. Here the model contour point $m$ is being compared to a high curvature image contour. Although the corresponding image point should be at the image contour peak, the local tangent line at the closest image point does not come close to this true corresponding point. One way to avoid this error, is to ignore the high curvature contour areas. Because the system is already highly overdetermined, it is possible to ignore the problematic contours without affecting the performance of the correspondence technique. \begin{figure} \begin{center} \fbox{\psadobepercent{60}{/home/vg/lipson/CorrespIJCV/new_two_problems.epsf}} \end{center} \caption{\it Two potential sources of error in the "bottom up" feature matching stage: (a) errors due to large displacements between the image and model contours (b) and errors due to high curvature contours.} \label{fig:two-problems} \end{figure} \section{Results} \label{sec:results} The results of our approach to computing correspondence can be evaluated in terms of accuracy and speed. We implemented our method in C on a Sun workstation IPC. We tested our procedure on two-dimensional polygons, two-dimensional closed curves, synthetic three dimensional polyhedra, and real imagery. All images are pixel binary contour images. The models are in the same format. The models consist of two pictures for the synthetic two-dimensional objects, three pictures for the synthetic three-dimensional objects, three pictures for natural objects rotated around one axis, and five pictures for natural objects depicted in different three-dimensional rotations. For each of these models one more picture is included to compensate for translational transformations (see \cite{Ullbasri89} for an explanation of the number of images that makeup a model). The model pictures each contained between 1000-1500 contour points. Typically, the number of points used in the sparse bottom up matching phase (see section~\ref{subsec:bottom-up matching}) ranged from 50 points for the synthetic objects to 100 points for the real imagery. A quantitative measure of the goodness of the computed results is provided by the mean squared error between the input image and the transformed model. For most purposes, visual assessment seemed sufficient. In each of the following examples we try to compute correspondences between a model and a novel image. For a given model, we tested our procedure on novel images that were instances that model and novel images that came from different objects. Each of the example figures show the set of model pictures, the novel image, the novel image superimposed on one of the model pictures before the matching process, the warped model superimposed on the input image after one iteration, and, after a number of iterations, the final warped model picture superimposed on the novel image. If the novel image is an instance of the model, the final warped model picture and the novel image should be very similar. \subsection{Results with Accurate Rough Alignment} In this section, we report the results of our experiments on synthetic polyhedra and real imagery. In each of these examples, the rough alignment stage was able to bring the chosen model image and input image into reasonable registration. \subsubsection{Synthetic Polyhedra} Figure~\ref{fig:hand} shows the results of our correspondence process on a synthetic three-dimensional hand. The model contains three pictures of the hand in different poses as a result of rotation around one axis. We added a fourth picture, containing points only at (1,1), to account for any translational component not compensated for in the rough alignment stage. The pose of the novel image is half way between the pose of the second model picture ($\bf m_2$) and and third model picture ($\bf m_3$). To fully test the system, we used the most dissimilar model picture to the image, model picture 1 ($\bf m_1$), to compute the contour matches. Figure~\ref{fig:hand}a shows the novel image. Figure~\ref{fig:hand}b shows the image and model picture 1 roughly aligned and superimposed before the start of the matching process. Figure~\ref{fig:hand}c contains the result after the first contour matching iteration. Here the transformed model is superimposed on the image. Finally, Figure~\ref{fig:hand}d shows the transformed model superimposed on the image after 3 iterations of the correspondence process. The transformed model and image are visually indistinguishable. (A sum of squares error analysis show that they differ on average by 0.4 pixels/ model contour point) \subsubsection{Real Imagery} We used real pictures of a toy Volkswagen, a toy Saab, and a face to further test our correspondence technique. We divided the testing into parts. The first part restricts the possible transformations of the objects. Here we specified that only rotations around one axis could be used to generate the model pictures and images. The second part utilizes full 3D rotations. Figures~\ref{fig:vw} and~\ref{fig:sung} are examples of the ability of our system to compute correspondences with real imagery. With the computed correspondences, our system was able to recognize new images of the cars and faces using only a few prestored pictures. In figure~\ref{fig:vw}, a toy VW was rotated around the $y$ axis to create three model pictures. The image, shown in figure~\ref{fig:vw}a, is derived from a linear combination of the three model pictures. The recipe for this particular image is $0.5{\bf m_1} + 0.5{\bf m_2}$. We compute feature correspondences between the first model picture ($\bf m_1$) and the image. In figure~\ref{fig:vw}b, we show the differences between the image and model picture 1. Figure~\ref{fig:vw}c shows transformed model superimposed on the image after 1 iteration. The final picture illustrates the effectiveness of our correspondence technique by superimposing the final transformed model, derived from 10 iterations of the matching process, onto the novel image. The two are almost visually indistinguishable. The five model pictures in figure~\ref{fig:sung} show a human face (KKS) under various three-dimensional rotations. The novel image shown in~\ref{fig:sung}a is a new image of the face whose pose lies between the pose of the face in model pictures 2 and 3 ($\bf m_2$ and $\bf m_3$). For the first iteration of the correspondence process, we compare the image to model picture 4 ($\bf m_4$). We specifically chose this model picture for the matching because it was quite dissimilar to the image. Figure~\ref{fig:sung}b shows the comparison of the image to model picture 4. Figure~\ref{fig:sung}c shows the result of the first iteration of correspondence process. Figure~\ref{fig:sung}d shows the final result; the transformed model after 10 iterations superimposed on the novel image. Even though the new image is not precisely a linear combination of the model pictures, we were able to compute a reasonable model to image transformation. Our procedure recovered coefficients that correctly expressed that the novel image ($\bf \hat{p}$) was a combination of model pictures 2 and 3 (see equation~\ref{eq:KKS} for the exact coefficients). Using a sum of squares error analysis, we found that the average displacement per pixel between the novel image and the transformed model was small; 2.2 pixels/model contour point. \begin{eqnarray} {\bf \hat{p}_x} & = & 0.91{\bf m_{2_x}} + 0.14{\bf m_{3_x}} \nonumber \\ {\bf \hat{p}_y} & = & 0.63{\bf m_{2_y}} + 0.34{\bf m_{3_y}} \label{eq:KKS} \end{eqnarray} We also compared a novel image of a different face (DB) to our original face model (KKS). Figure~\ref{fig:beymer} shows the results of this experiment. As expected, our correspondence technique was unable obtain a good transformation of the face model of KKS to the novel image of DB. Figure~\ref{fig:beymer}e shows the transformed model after 10 iterations of the matching process. The average sum of squares displacement per pixel between corresponding image and transformed model points was 4.7 pixels/model contour point; more than twice the error than in the previous experiment. We also compared images of our toy cars to our face model. In these cases, the cars had few features in common with the face model and the iteration process quickly diverged. \subsection{Results with Inaccurate Rough Alignment} The assumption of accurate rough alignment may not be valid in many real world cases. Rough alignment is composed of compensations for translation, scale, and orientation. Mistakes in the rough alignment can occur, for instance, if the image or model pictures have no discernible dominant orientations or if we cannot resolve the two-way orientation ambiguity problem. Experimentally, we found that our method can compensate quite accurately for incorrect compensations in translation and scale. However, grossly inaccurate registration of orientation remains a problem. The subsequent example uses an image and a model picture that differ by a rotation in the $x-y$ plane. For the most part, the system could tolerate rotations of at most 24 degrees. After 24 degrees, the majority of the image and model contours violated our spatial proximity assumption. As a result, there was no evidence of convergence despite repeated refinements. Below the 24 degree mark the system required at approximately 10 additional refinements before a converging to a final solution. Figure~\ref{fig:saab} shows a Saab model created from various three-dimensional rotations of the car In this case, the image is an inplane rotation of model picture 1 (${\bf m_1}$) by 18 degrees. The inputs to the correspondence process are model picture 1 and the image without any in-plane rotation compensation. Figures~\ref{fig:saab}c and~\ref{fig:saab}d show a comparison of the transformed model and the image after first and 10th iterations respectively. By the tenth iteration, the process has converged to a reasonably good solution. \section{Conclusion} Our goal was to create an robust and efficient technique which could compute a model to image correspondence. We achieve this by successfully blending both "bottom up" and "top down" information. There are four benefits to our approach. First, it is efficient; the use of models constrains the matches in a linear solution. Second, the matching process is computationally simple. Third it is is effective; experimentally we have found that iterative refinement of the process quickly converges to a good solution, if one exists. Finally, the procedure is robust; even significantly large errors in the rough alignment stage do not impair the subsequent correspondence procedure. We could enhance the behavior of the system as a whole by further developing the rough alignment stage. In section~\ref{subsec:rough-alignment}, we have presented some simple techniques to compensate for differences in viewing geometry used to generate the model picture and the image. These techniques for rough alignment, however do not sufficiently handle large in-depth rotations, objects without a dominant orientation, non-rigid objects, or occlusion. If the rough alignment procedure were more robust, the subsequent correspondence stage would benefit greatly. First, we could perform fewer "bottom up" contour matches. Secondly, the need for repeated refinements of the correspondence would be reduced. Also, an improved rough alignment procedure would allow the technique to use model views which coarsely sample the view space. We also desire a more sophisticated verification criteria. Once we transform the model, we compare the resulting picture to the image using the sum of the squared displacements between corresponding model and image points. This measure is inadequate to distinguish between a non- rigid transformation of the model and a completely new object. In the future, we would like to incorporate our procedure for correspondence into other model-based recognition systems. We are especially interested in testing our technique in conjunction with recognition using view approximation by regularization networks and recognition by linear mapping. Since these both require exact point to point matches, we feel they will be greatly benefited by our efficient and robust correspondence algorithm. \section*{Acknowledgments} The authors would like to thank Ronen Basri, David Beymer, and Greg Klanderman for their help in generating the object models and novel images. We would also like to acknowledge Ivan Bachelder for his help with the graphical user interface. Finally, we would like to thank Pawan Sinha for his helpful comments regarding this work. \onecolumn \begin{figure} \begin{center} \fbox{\psadobepercent{90}{/home/vg/lipson/CorrespIJCV/new_hand_comp.epsf}} \end{center} \caption{\it Results of the correspondence technique on a three-dimensional synthetic hand. The top three pictures comprise the model. (a) The novel image ($0.5{\bf m_2} + 0.5{\bf m_3}$). (b) The system matched the novel image to model picture 1 (${\bf m_1}$). The two are shown here roughly aligned and superimposed (c) The result of the matching process after 1 iteration; the transformed model is superimposed on the original image. (d) The final result of the matching process after 3 iterations; the transformed model is superimposed on the original image. The two are visually indistinguishable.} \label{fig:hand} \end{figure} \begin{figure} \begin{center} \fbox{\psadobepercent{100}{/home/vg/lipson/CorrespIJCV/new_vw_comp.epsf}} \end{center} \caption{\it Example of our recognition process on a toy VW. The model images were created by rotating the car around one axis. (a) The novel image ($0.5{\bf m_1} + 0.5{\bf m_2}$). (b) We used the first model picture ${\bf m_1}$ in the matching process. A comparison of the image to this picture before the rough alignment stage is shown. The result sections contains (c) the transformed model superimposed on the novel image after one iteration and (d) the transformed model superimposed on the novel image at the end of 10 iterations.} \label{fig:vw} \end{figure} \begin{figure} \begin{center} \fbox{\psadobepercent{100}{/home/vg/lipson/CorrespIJCV/book_sung_comp.epsf}} \end{center} \caption{\it Example of the correspondence process on a human face (KKS). The five model pictures of the face are shown above the horizontal line. (a) A real novel image of KKS whose face pose is between the face poses in model pictures 2 and 3. (b) The novel image is compared to model image 4. A superimposition of the two prior to the matching process is shown here. The result of the matching process (c) after 1 iteration and (d) after 10 iterations; the transformed model is superimposed on the image.} \label{fig:sung} \end{figure} \begin{figure} \begin{center} \fbox{\psadobepercent{100}{/home/vg/lipson/CorrespIJCV/book_beymer_comp.epsf}} \end{center} \caption{\it Example of the correspondence process acting on a model of a face of KKS and a novel image from a different person (DB). (a) The novel image of DB. (b) A comparison of DB to KKS model image 4 prior to the matching process. (c) The result of matching the novel image to KKS model image 4 after one iteration; the transformed model is superimposed on the image. The result of the correspondence process after 10 iterations; (d) the transformed model is superimposed on the image and (e) the transformed model is shown alone} \label{fig:beymer} \end{figure} \begin{figure} \begin{center} \fbox{\psadobepercent{80}{/home/vg/lipson/CorrespIJCV/new_saab_comp.epsf}} \end{center} \caption{\it Experiment using incorrect compensation for rotation in the $xy$ plane. Five model pictures of a toy Saab are shown above the horizontal line. (a) The novel image was created by rotating model picture 1 (${\bf m_1} $) by 18 degrees. (b) The correspondence process initially compares the novel image to model picture 1 without any compensatory adjustment. The results of the process are shown in (c) the transformed model superimposed on the image after the first iteration and in (d) the final result; a comparison of the transformed model and the novel image after 10 iterations} \label{fig:saab} \end{figure} \twocolumn \begin{thebibliography}{99} \bibitem{Bachelder91} I. Bachelder. Contour Matching Using Local Affine Transformations. Master's thesis, Massachusetts Institute of Technology, June 1991. \bibitem{Brooks81} R.A. Brooks. {\em Model-Based Computer Vision}. UMI Research Press, Ann Arbor, MI 1981. \bibitem{Bultoff92} H.H. Bulthoff and S. Edelman. Psychophysical Support for a Two-Dimensional View Interpolation Theory of Object Recognition. Proceedings of the National Academy of Science, Vol. 89, pages 60-64, January 1992. \bibitem{Edelman90} S. Edelman and H.H. Bulthoff. Viewpoint-Specific Representations in Three Dimensional Object Recognition. A.I. Memo 1239, The Artificial Intelligence Lab, MIT, 1990. \bibitem{EdelmanPog90} S. Edelman and T. Poggio. Bringing the Grandmother Back into the Picture: A Memory- Based View of Object Recognition. A.I. Memo 1181, The Artificial Intelligence Lab, M.I.T., 1990. \bibitem{Grimson89} W.E.L. Grimson. On the recognition of curved objects. {\em IEEE Transactions on Pattern Analysis and Machine Intelligence}, 11(6):632-643, 1989. \bibitem{GrimHut89} W.E.L. Grimson and D.P. Huttenlocher. On the verification of hypothesized matches in model-based recognition. A.I. Memo 11110, The Artificial Intelligence Lab., M.I.T., 1989. \bibitem{GrimTlp84} W.E.L. Grimson and T. Lozano-Perez. Model-based recognition and localization from sparse range or tactile data. {\em The International Journal of Robotics Research}, 3(3):3-35,1984. \bibitem{Grossberg82} S. Grossberg. {\em Studies of Mind and Brain}. Reidel, Boston, MA, 1982. \bibitem{Hildreth84} E.C. Hildreth. The Measurement of Visual Motion. The MIT Press, Cambridge, 1984. \bibitem{Hildreth90} E.C. Hildreth. The neural computation of the velocity field. In {\em Vision and the Brain}, pages 139-164, 1990. \bibitem{Horn81} B.K.P. Horn and B.G. Schunk. Determining optical flow. Artif. Intell. 17:185-203, 1981. \bibitem{Huttenlocher88} D.P. Huttenlocher. Three-Dimensional Recognition of Solid Objects from a Two-Dimensional Image. Ph.D. thesis, Massachusetts Institute of Technology, April 1988. \bibitem{HutUllman87} D.P. Huttenlocher and S. Ullman. Object recognition using alignment. {\em International Conference on Computer vision}, pages 102-111,1987. \bibitem{Lipson93} P. Lipson. Model Guided Correspondence. Master's thesis, Massachusetts Institute of Technology, June 1993. \bibitem{Lowe84} D.G. Lowe. Perceptual organization and visual recognition. Technical Report STAN-CS-84-1020, Stanford University, 1984. \bibitem{Marr} D.Marr and S.Ullman. Directional selectivity and its use in early visual processing. {\em Proc. R. Soc. London Ser.}, B211:151-180. \bibitem{Mundy92} J.L. Mundy and A.Zisserman. editors, {\em Geometrical Invariance in Computer Vision}, MIT Press, 1992. \bibitem{Poggio90} T. Poggio and S. Edelman. A network that learns to recognize three-dimensional objects. {\em Nature},343:263-265,January 18, 1990. \bibitem{Pollard87} S.B. Pollard, J. Porrill, J.E.W. Mayhew, and J.P. Frisby. Matching geometrical descriptions in three-space. {\em Image and Vision Computing},5(2):73-78, May 1987. \bibitem{Shoham88} D. Shoham and S. Ullman. Aligning a model to an image using minimal information. IEEE, pages 259-263, 1988. \bibitem{Ullman89} S. Ullman. Aligning pictorial descriptions: An approach to object recognition. Cognition, 32(3):193-254, August 1989. \bibitem{Ullbasri89} S. Ullman and R. Basri. Recognition by linear combinations of models. A.I. Memo 1152, The Artificial Intelligence Lab., M.I.T., 1989. \bibitem{Kriegman95} B.Vijayakumar, D.J. Kriegman, and J. Ponce. Invariant-based recognition of complex curved 3D objects from image contours, 1995. \end{thebibliography} \end{document}