Changeset 12283

Timestamp:

06/30/2009 08:32:08 PM (14 months ago)

Author:

dstn

Message:

remove the entire section on our approach

File:

• trunk/documents/theses/dstn/review.tex (modified) (1 diff)

trunk/documents/theses/dstn/review.tex

@@ -1359 +1359 @@
 
 
-\section{Our approach}
-\label{ourapproach}
-
-\subsection{Preprocessing}
-
-Astronomers have developed computational methods for detecting and
-localizing stars, galaxies, and other objects in astronomical images.
-In astronomy this process is known as \emph{source extraction}.
-Telescopes are designed to produce a predictable point-spread function
-which covers several pixels, and this allows stars, which are
-effectively point sources, to be localized with subpixel accuracy.
-Sources that have image profiles larger than the point spread function
-must be extended objects, and this allows stars to be differentiated
-from galaxies and other objects.  Cosmic rays (single, energetic
-particles) deposit energy in single pixels; since no distant object
-can produce such an image profile, this source of noise can easily be
-filtered from the image.
-
-
-The result of source extraction is a list of object positions (with
-subpixel resolution), along with the brightness of each object.  If
-the telescope has been properly calibrated, this brightness is
-proportional to the electromagnetic \emph{flux} from the object, but
-in general we simply treat the brightness as a means of ordering the
-objects.  It is also possible to classify each source as a star or
-galaxy, and even classify the galaxy type, but we currently do not use
-this information.
-
-
-For the purposes of this paper, we will assume that source extraction
-has been performed as a preprocessing step, so we are given a list of
-source positions sorted by brightness.
-
-
-
-\subsection{Quad features}
-
-\begin{figure}
-  \begin{center}
-    \includegraphics[width=0.5\textwidth]{quad-fig}
-  \end{center}
-  \caption{The local coordinate frame of a quad.  The most distant pair of sources, $A$ and $B$,
-        define the origin and $(1,1)$ of the coordinate frame, respectively.
-        The remaining two sources $C$ and $D$ are required to lie inside the circle with diameter $AB$.
-        To resolve ambiguities, the points must be labelled such that $C_x \le \smallhalf$ and
-        $C_x + D_x \le 1$.  The geometric feature descriptor is $(C_x, C_y, D_x, D_y)$.}
-  \label{quad}
-\end{figure}
-
-We have taken a geometric feature-matching approach to this problem.
-Since individual sources can be well localized but have no distinctive
-properties, we build distinctive features by describing the relative
-geometry of small sets of objects.
-
-
-To solve the blind astrometry problem, we need to index a large number
-of features: we want to solve images that cover $10^{-6}$ or less of
-the area of the sky, and we want to have tens of features per image in
-order to increase our robustness to distractors, dropouts, and
-occlusion.
-
-
-We are matching two-dimensional objects, and we assume that
-astronomical images can be well described by similarity
-transformations: scaling, rotation and translation.  Therefore, we
-require two sources to define a local coordinate system.
-
-
-The standard geometric hashing recipe would have us use triangle
-features.  However, the positional noise in astronomical image is
-sufficiently large that triangles are not distinctive: with the number
-of features we require, \emph{any} triangle will match an excessively
-large number of triangles in our index due to feature aliasing.  In
-order to building a more distinctive feature, we consider sets of
-\emph{four} sources-- \emph{quads}.  Two of the sources are the basis
-set that defines the local coordinate system, and our geometric
-feature descriptor is composed of the positions of the remaining two
-sources in this coordinate system.
-
-Using a quad feature can be seen as a way of incorporating a voting
-scheme directly into the feature-matching phase: a quad is essentially
-the conjunction of two triangles.  We are effectively squaring the
-distinctiveness of our geometric features by demanding that \emph{two}
-triangles be matched simultaneously.
-
-One disadvantage of using quads rather than triangles is that we
-become more sensitive to distractors and dropouts: if the proportion
-of distractors and dropouts is $d$, the proportion of overlapping
-sources is $(1-d)$, and we expect about $(1-d)^3$ triangles but
-$(1-d)^4$ quads to overlap.
-
-
-In standard geometric feature-matching, one enumerates all basis sets,
-then lists the positions of all the remaining interest points within
-that basis.  Since we have a two-dimensional basis and we list the
-positions of pairs of sources, this would yield $\mathcal{O}(n^4)$
-features.  Astronomical images typically contain hundreds to thousands
-of sources, and our reference catalog contains $10^9$ sources, so this
-would be prohibitively expensive.  We therefore impose two constraints
-on the properties of the quads we create.  See Figure \ref{quad}.
-
-Given a set of four sources, we first find the two sources most
-distant from each other and label them $A$ and $B$.  If the distance
-from $A$ to $B$ is outside a specified range, we reject the quad.
-Next, we demand that the two remaining sources lie inside the circle
-that has $AB$ as a diameter.  We place $A$ at the origin of the local
-coordinate system, and place $B$ at position $(x, y) = (1, 1)$.  We
-then compute the $(x,y)$ coordinates of the two remaining sources.
-The source with the smaller $x$ coordinate is labelled $C$, and the
-last source is labelled $D$, so we have $C_x \le D_x$.  The geometric
-feature descriptor is $(C_x, C_y, D_x, D_y)$.
-
-Observe that this feature has one redundancy: we labelled $A$ and $B$
-arbitrarily, and if we swap their labels then the coordinate system is
-rotated $180$ degrees about $(\half, \half)$.  The feature descriptor
-becomes $(1 - C_x, 1 - C_y, 1 - D_x, 1 - D_y)$.  We can deal with this
-redundancy by demanding that $A$ and $B$ be labelled such that $C_x +
-D_x \le 1$.
-
-
-Recall the idea mentioned earlier in this paper of solving images of unknown
-scale by building a cascade of indices, each covering a range of scales.
-We use this approach with a scale factor of $2$ or $\sqrt{2}$.
-This allows us to assume that the image scale is known to
-within a small factor.  When deciding what range of quad sizes ($AB$ distances) we wish to
-allow, we are faced with a tradeoff: if we use quads with large
-diameter, then the probability that all four stars will be within the bounds of
-the image decreases.  Meanwhile, the number of quads of diameter $d$ that
-can be created is $\mathcal{O}(d^5)$, assuming a uniform distribution
-of sources and ignoring edge effects.\footnote{%
-  For a given star $A$, the number of
-  stars that can become star $B$ goes as $d$, while the number of stars
-  $C$ and $D$ goes as $d^2$, so the number of $BCD$ combinations goes as $d^5$.}
-On the other hand, if we build small quads, then the relative positional error
-will be larger, which means that when we search for matching quads in the index
-we must use a larger search radius, which means that many more false matches
-will be found.  We have not yet found an analytic solution to optimize this
-tradeoff; we currently set the desired quad scale to about
-a third of the size of the images we wish to solve.
-
-
-Our quad features have good noise properties: a small change of
-position of any one of sources $ABCD$ leads to a small change in the
-feature descriptor.  The noise is nearly isotropic: movement of a
-source in any direction yields an almost equal change in the feature
-descriptor.  The feature has some edge effects: $A$ and $B$ are
-defined to be the most distant pair, but if $C$ and $D$ are nearly
-diametrically opposite each other then a small amount of positional
-noise can push them further apart so that they become the most distant
-pair.  As a result, $C$ and $D$ will be labelled $A$ and $B$, and vice
-versa, and a completely different geometric feature will be produced.
-This is a minor effect since it only occurs when both $C$ and $D$ have
-extreme values; we ignore it.  Another edge effect is that $C$ and $D$
-are required to lie inside the circle with diameter $AB$; at test time
-we simply expand the allowed diameter of the quad enough to compensate
-for a given level of positional noise.  Finally, if the distance $AB$
-is near the limit of the allowed range of scales, then the quad can
-become invalid due to noise.  This effect is equally easy to correct
-by expanding the range slightly at test time.
-
-
-Notice that our constraints on the quads we accept has the effect of
-restricting the regions of feature space in which valid quads live.
-Since $C$ and $D$ are required to fall inside a circle with $AB$ on
-the diameter, we have:
-\begin{eqnarray*}
-\left(C_x - \smallhalf\right)^2 + \left(C_y - \smallhalf\right)^2 & \le & \smallhalf \\
-\left(D_x - \smallhalf\right)^2 + \left(D_y - \smallhalf\right)^2 & \le & \smallhalf
-\end{eqnarray*}
-We also have the constraints $C_x + D_x \le 1$ and $C_x \le D_x$ to
-eliminate the redundancy of the labelling of the source pairs $AB$ and
-$CD$.  As a result, our feature space is rather strangely shaped, so a
-grid-based hashing scheme would result in poor utilization of the hash
-table storage.  Also note that since our noise is nearly isotropic and
-our quads are restricted to a known range of scales, we can use the
-Euclidean distance metric with a fixed search radius $r$ to do quad
-feature matching.
-
-
-
-
-\subsection{Indexing}
-
-
-We want our index to satisfy the following constraints.  It should
-have uniform source and quad density over the whole sky, because we
-want to be equally likely to solve images over the whole sky.  We want
-to build quads from bright stars, because we expect these to be more
-likely to be visible in test images, yet because of distractors,
-dropouts, and occlusions, we don't want to depend too heavily on any
-one star; we want to trade off using bright stars and using a variety
-of stars.
-
-
-We achieve this by first selecting a spatially uniform subset of the
-brightest sources in the reference catalog.  We place a grid over the
-sky whose cells are sized so that a typical image is a few cells wide,
-then we take the $n$ brightest sources in each cell.
-
-
-Next, we place another similarly-sized grid over the sky and in each
-cell we try to build a quad whose center is within the cell.  We try
-building quads in order of source brightness, but we also keep track
-of how many times each source has been used.  In our first pass
-through the cells we only allow each star to be used once, and in each
-subsequent pass we increase the number of times a source can be used.
-
-
-Once we have built all the quads, we build a \kdtree in feature space.
-This allows us to rapidly find all the quads in our index whose
-geometric feature descriptor is close to a query feature.
-
-We also build a \kdtree over the spatially uniform subset of sources;
-this is used for our verification scheme.
-
-
-\subsection{Solving}
-
-At test time, we begin enumerating all valid quads in the image,
-starting with those that can be built from the brightest sources.  For
-each quad we perform a range search in the \kdtree in order to find
-matching quads.  Typically each image quad results in a few matches.
-We run a verification process on each match.
-
-The verification process first computes a least-squares transformation
-between image coordinates and celestial coordinates.  We then search
-in the \kdtree of sources for all sources that should be visible in
-the image.  We apply the transformation to bring them into image
-coordinates, and for each one find the nearest source in the image.
-We use a probabilistic model of the positional noise to compute the
-odds ratio between the match being a true positive and a false
-positive.  If this ratio exceeds a threshold we declare the image
-solved.  By using an odds ratio threshold, we allow the user to trade
-off the probability of false negatives and false positives.
-
-
-
-\comment{
-  We build an \emph{index} which maps these features
-  back to their locations on the sky.\footnote{%
-        In the database community (and some early computer science literature)
-        this would be called an \emph{inverted} index, but we feel this
-        is contrary to common usage: the index of a book maps from concepts
-        (features) to pages (locations); the inverse mapping is called a
-        \emph{table of contents}.}
-  
-  At test time, we extract features from the image, then search our
-  index for matching features.  Each matched feature is a hypothesized
-  astrometric solution.  We use a separate probabilistic verification
-  stage to test these hypotheses.
-
-
-  Since our input images have unknown scale, rotation, and
-  translation, we want our features to be invariant under these
-  transformations.  One option is to consider triangles of stars and
-  use the interior angles (or relative edge lengths) as a
-  two-dimensional feature descriptor, as in \cite{pal2006}.  Since
-  both the image and reference catalog are noisy, we must allow each
-  feature in the image to match a region in feature space.  When using
-  geometric features, we are faced with a tradeoff: if we consider
-  sets of stars that span a large portion of the image, then the
-  relative positional error is smaller (and hence each feature matches
-  a smaller region of feature space - features are more distinctive),
-  but there are \emph{many} features to test.  If we choose smaller
-  features, there are fewer features to test, but the relative error
-  is larger so each feature matches a larger region in feature space;
-  features can be confused more easily.
-
-
-  Although triangles are appealing features from a theoretical
-  perspective, in practice they are problematic due to the magnitude
-  of positional noise in typical images we wish to solve.  Any
-  triangle we find in an image will generate a large number of false
-  matches to triangles in our index because triangles aren't
-  distinctive enough.  We therefore use sets of four stars --
-  \emph{quads} -- as our features.  The two most widely separated
-  stars (A and B) define the corners of a coordinate system, and we
-  list the positions of the remaining two stars (C and D) in that
-  coordinate system.  We demand that stars C and D lie inside the
-  circle centered at the midpoint of stars A and B and diameter AB.
-  We impose an arbitrary order to decide which star is labelled C and
-  which is labelled D, based on their positions in the local
-  coordinate system.  This yields a four-dimensional feature
-  descriptor.  If we exchange the labels of A and B, then the local
-  coordinate system is flipped and a different feature descriptor is
-  produced.  We store one of these descriptors in our index, and at
-  test time we search for matches to both descriptors.
-
-  
-  This choice of feature and feature descriptor (\emph{code}) has
-  several desirable properties.  If stars are distributed uniformly in
-  space, then codes are distributed uniformly in \emph{code space}.
-  The error propagation properties are good: small positional errors
-  in any of the four stars yield small errors in the code value, and
-  isotropic errors in the positions of the stars produce nearly
-  isotropic errors in the code value.  This allows us to find matching
-  codes based on Euclidean distance in code space.
-
-  Our index is composed of a large number of code values and mappings
-  back to locations on the sky.  When given a new image to solve, we
-  extract many quads, compute their codes, and for each one search for
-  matching codes in the index.  Due to the isotropic error properties
-  of codes, searching for matching codes is simply \emph{range search}
-  in four-dimensional code space.  We use \kdtrees to accelerate this
-  process.
-
-
-  Each time we match a feature in an image to a feature in our index,
-  we generate a hypothesis about the location (pointing, scale, and
-  rotation) of the image on the sky.  We are typically operating in
-  the regime where \emph{any} feature will produce several matches, so
-  we use a probabilistic model to determine whether a given match is a
-  false positive or a true solution.  We do this by computing a
-  transformation between image coordinates and the sky based on the
-  matching quad.  We then search for stars in our reference catalog
-  that should be visible in the image if the hypothesis is correct.
-  By combining our knowledge of the positional errors in the reference
-  catalog and the image with an estimate of the proportion of stars
-  that should be visible in both, we can assign a probability to the
-  hypothesis.  If it is above some threshold, we accept the match.
-
-
-  \emph{
-        \begin{itemize}
-        \item Brightness ordering to speed search only.
-        \item More about the constraints and goals of our system to differentiate it
-          from the spacecraft attitude estimation problem.
-        \item A quad is like the conjunction of two triangles: we're doing implicit agreement of two triangle features!
-        \item Applications of our system?
-        \end{itemize}
-  }
-
-  
-  To summarize, the key elements of our approach are:
-  \begin{itemize}
-  \item \textbf{geometric features} composed of sets of point features;
-  \item \textbf{continuous feature descriptors} that describe the relative positions of the point features;
-  \item \textbf{fast range-search} to match features descriptors;
-  \item \textbf{probabilistic validation} to eliminate false positives.
-  \end{itemize}
-
-
-
-  %rummage through the toolbox of computer vision and object
-  %recognition techniques that are related to our approach or would seem
-  %to be applicable to our problem.
-}
-
-
-
 \section{Conclusion}