Context Navigation

← Previous Change
Next Change →

review.tex

Timestamp:

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

Author:

dstn

Message:

review: related astrometric calibration work

File:

: 1 edited

trunk/documents/theses/dstn/review.tex (modified) (16 diffs)

Legend:

: Unmodified
: Added
: Removed

trunk/documents/theses/dstn/review.tex

-                      r12281
+                      r12282
+Extra sources can be due to planets, comets, satellites, or aircraft.
+Missing or poorly localized source can be due to imperfections in the
+imaging sensor, saturation, cosmic ray interference, or (rarely)
+occlusion.  Errors in the image processing that detects sources can
+lead to sources being gained or lost.  We call sources that appear in
+only the input image or reference catalog \emph{distractors} and
+\emph{dropouts}, respectively.  The existence of distractors and
+dropouts means that we can never assume that all the objects in the
+reference catalog will be contained in an image to be recognized, or
+vice versa.
 The images to be recognized are subregions of the sky.  Image sizes
 range from nearly half the celestial sphere down to $10^{-7}$ of the
 …
 \comment{
-An additional challenge in astrometry is that the input image and
-reference catalog may each have fictitious or missing sources.
-Extra sources can be due to planets, comets, satellites, or aircraft.
-Missing or poorly localized source can be due to imperfections in the
-imaging sensor, saturation, cosmic ray interference, or (rarely)
-occlusion.  Errors in the image processing that detects sources can
-lead to sources being gained or lost.  We call sources that appear in
-only the input image or reference catalog \emph{distractors} and
-\emph{dropouts}, respectively.  The existence of dropouts and
-distractors means that we can never assume that all the objects in the
-reference catalog will be contained in the image, or vice versa.
 There are several useful applications for a blind astrometry solver.
 Most telescopes used by professional astronomers are
 …
 There seem to be two distinct groups of researchers who have worked on
 astrometry problems.  The first are professional astronomers, whose
+images are typically of small angular extent, long exposure time, and
+high quality.  They typically assume that there is a good initial
+guess of the astrometry and the goal is to produce a very accurate
 astrometric solution, including image distortion.  The second group of
+researchers are spacecraft engineers who want to use astrometry to
+estimate the attitude of the camera (and the spacecraft to which it is
 attached).  Here the images are of wide angular extent, have short
+astrometric calibration.  The first are professional astronomers,
+whose images are typically of small angular extent, long exposure
+time, and high quality.  They typically assume that there is a good
+initial guess of the astrometry and the goal is to produce a very
+accurate astrometric calibration, including image distortion.  The
+second group of researchers are spacecraft engineers who want to use
+the stars to estimate the attitude of a camera attached to a
+spacecraft.  Here the images are of wide angular extent, have short
 exposure time, and are very noisy.  Primary concerns include weight,
 power consumption, and robustness (especially in avoiding false
 …
 possible given the hardware.
 \subsection{Non-blind astrometry}
+\subsection{Non-blind astrometric calibration}
 Non-blind astrometry requires that an initial estimate of the image
+astrometry be provided.
+Groth \cite{groth1986} presents an algorithm for matching two lists of
+coordinates (eg, image coordinates in pixels and reference star
+coordinates on the celestial sphere), assuming that the lists contain
+a significant proportion of objects in common.  To compensate for the
+limited computing resources available at the time, he suggests taking
+the brightest 20 or 30 objects in each list.
+astrometry be provided.  Groth \cite{groth1986} presents an algorithm
+for matching two lists of coordinates (eg, image coordinates in pixels
+and reference star coordinates on the celestial sphere), assuming that
+the lists contain a significant proportion of objects in common.  With
+the limited computing resources available at the time, he suggests
+taking the brightest 20 or 30 objects in each list.
 Once the two lists of objects have been compiled and the brightest
 objects selected, all sets of three objects are enumerated and the
 triangles they form are described by a scale--, rotation--, and
 translation--invariant descriptor, composed of the length ratio of the
+triangles they form are described by a scale-, rotation-, and
+translation-invariant descriptor, composed of the length ratio of the
 longest to shortest edges, plus the cosine between these edges and the
 \emph{sense} or \emph{parity} of the triangle.  The tolerances
 …
 After triangle features are extracted from both point lists, feature
 matching is performed by checking whether the distance between each
 pair of features is less than their corresponding tolerances.  (This
 process can be accelerated by sorting the features on one of the
+feature dimensions.)  If multiple matches are found for a particular
+feature, only the closest is considered.  After all the features have
 been compared, many correct matches should be found, along with some
+false matches.  For each match, the difference of the log-perimeters
+of the two triangles is computed; this gives the relative scale of the
 two triangles and hence the coordinate frames, assuming the match is
+pair of features is less than their corresponding tolerances.  This
+process is accelerated by sorting the features on one of the feature
+dimensions.  If multiple matches are found for a particular feature,
+only the closest is considered.  After all the features have been
+compared, many correct matches should be found, along with some false
+matches.  For each match, the difference of the log-perimeters of the
+two triangles is computed.  This gives the relative scales of the two
+triangles and hence their coordinate frames, assuming the match is
 correct.  False matches are rejected by iterative outlier detection:
 the mean difference of log-perimeters is computed and matches far from
 …
 P\'al and Bakos \cite{pal2006} adapt the triangle-matching approach to
 images containing many more objects: of order $10^4$.  Since it would
+images containing many more objects (of order $10^4$).  Since it would
 become prohibitively expensive to enumerate all triangles in such an
 image, they reduce the number of triangles created by using only the
 …
 stars.  The intent is that if some of the nearby stars are distractors
 that they will be ignored when the extended triangulations are used.
-%This extended triangulation skips the nearest set of stars, which creates triangles of larger scale.
-%The hope is that distractor stars
-%which should make the algorithm more
-%robust to distractor stars.
 \begin{figure}
 \begin{center}
 \includegraphics[width=0.6\textwidth]{pal-fig2}
+\includegraphics[width=\figunit]{pal-fig2}
 \end{center}
 \caption{The triangle parameterization used by P\'al and Bakos.  This figure is copied from \cite{pal2006} Figure 2.}
 \label{pal}
+\caption{The triangle parameterization used by P\'al and Bakos.  This
+figure is a reproduction of \fig 2 in \cite{pal2006}.\label{pal}}
 \end{figure}
 This paper also introduces a new triangle parameterization which is
 continuous and sensitive to chirality (parity); see Figure \ref{pal}.
+P\'al and Bakos introduce a new triangle parameterization which is
+continuous and sensitive to chirality (parity); see \figref{pal}.
 This two-dimensional parameter space is used as the geometric feature
+space.
+% Noise propagation properties?
+When matching triangles between the two images, they demand a
+space.  When matching triangles between the two images, they demand a
 \emph{symmetric point match}: each triangle must be the other
 triangle's nearest neighbour in feature space.  Matching two images is
 done by creating the lists of triangles and attempting to find
 symmetric point matches; this process can be accelerated by sorting
+each list by one of the coordinates.  Each triangle match is
+considered to be a vote for the correspondence of the three pairs of
+points composing the triangles.  These votes are accumulated in a
+sparse matrix where element $(i, j)$ contains the number of votes for
+a correspondence between object $i$ in the first image and object $j$
+in the second image.  After all matches are considered, the top 40\%
 of the nonzero matrix elements are assumed to contain the true
+symmetric point matches.  This process is accelerated by sorting each
+list by one of the coordinates.  Each triangle match is considered to
+be a vote for the correspondence of the three pairs of points
+composing the triangles.  These votes are accumulated in a sparse
+matrix where element $(i, j)$ contains the number of votes for a
+correspondence between object $i$ in the first image and object $j$ in
+the second image.  After all matches are considered, the top 40\% of
+the nonzero matrix elements are assumed to contain the true
 correspondences.  A transformation based on these correspondence is
 computed and the unitarity of the transformation matrix is used to
 judge whether the match is true or false.
-%In practice, they only used the extended Delauney triangulation if the regular Delauney
-%triangulation fails to produce a match.
-%The algorithm was tested on $8\degree \times 8\degree$ images.  The list of reference
-%stars was generated from the Two-Micron All-Sky Survey (2MASS) \cite{twomass}.
-%They estimated the magnitude of the reference stars in the bandpass of their images,
-%and selected the brightest 3000 objects from each.
 A different approach is taken by Kaiser \etal \cite{kaiser1999}.  They
 assume they are given two lists of source positions that differ by a
 rigid transformation involving scaling, rotation, and translation.  In
 each image, they look at each pair of points and compute the angle and
+the logarithm of the length of the vector connecting the pair.  For
 each list, the pairwise log-distance and angle are placed in a
 two-dimensional histograms.  Observe that if the whole list of points
+each image, they iterate over each pair of points and compute the
+vector difference of their positions.  For each list, the log-length
+and angle of the pairwise difference vectors are accumulated in a
+two-dimensional histogram.  Observe that if the whole list of points
 is scaled up by a constant factor, then the log-distance between each
 pair of points increases by a constant amount.  Similarly, if the
 whole list is rotated then the angles shift by a constant amount.
 Once the two histograms have been computed, their cross-correlation is
+computed.  (This is the same as shifting the histograms with respect
+to each other and recording the dot-product at each shifted position.)
+If the two lists contain a significant number of corresponding points,
+the cross-correlation signal will be strong at a shift corresponding
+to the difference in log-scale and rotation between the lists.
+This process is similar to a Hough transform
+computed.  If the two lists contain a significant number of
+corresponding points, the cross-correlation signal will be strongest
+at a shift corresponding to the difference in log-scale and rotation
+between the lists.  This process is similar to a Hough transform
 \cite{duda1972,ballard1981}, except that instead of finding the peak
 of a single parameter-space histogram, we are searching for a peak in
 …
+%This procedure is simple and powerful, but requires that the transformation between
+%the coordinate systems be equal across the whole image.  This assumption can be violated
+%(but usually not by a amount)
+\subsection{Blind astrometry}
+The majority of previous work on blind astrometry is motivated by the
+problem of spacecraft attitude estimation.  Sometimes called the
+``lost in space'' or ``stellar gyroscope'' problem, the task is to
+estimate the pose of a spacecraft by using an image of the sky
+captured by an onboard camera.  Although similar in general spirit,
+the requirements and limitations of this application are quite
+different than our astronomical application.  Mass, power consumption,
+\subsection{Blind astrometric calibration}
+The majority of previous work on blind astrometric calibration is
+motivated by the problem of spacecraft attitude estimation.  Sometimes
+called the ``lost in space'' or ``stellar gyroscope'' problem, the
+task is to estimate the pose of a spacecraft by using an image of the
+sky captured by an onboard camera.  Although similar in general
+spirit, the requirements and limitations of this application are quite
+different than astronomical applications.  Mass, power consumption,
 and robustness of the system are primary concerns, and as a result the
 optical designs are very different from science-grade astronomical
 …
 the exposure time is kept short to allow the system to function while
 the spacecraft is rotating.  As a result, image quality is typically
 quite poor: often only a handfull of the brightest stars may be
+visible.  Since the field of view is large, a reference catalog of a
 few thousand stars is sufficient to ensure that any view of the sky
+quite poor: often only a handfull of the brightest stars are visible.
+Since the field of view is large, a reference catalog of a few
+thousand stars is sufficient to ensure that any view of the sky
 contains many reference stars.  Since the system will only process
 images from a single camera, the whole system can be customized and
 calibrated to that camera.  For example, the nonlinear distortions of
 the optical system can be measured, and the scale and bandpass of the
+imaging system are known.
+imaging system are known, so the reference catalog can be tailored to
+match.
 For example, Liebe \etal \cite{liebe2004} describe a system design
+with a $56 \deg$ field of view and exposure time of $50 \
+\textrm{ms}$.  The resulting images contain tens of stars if the
+spacecraft is not rotating, but on average only three stars will be
+detectable when the rotation rate is $50\deg/\textrm{s}$.  The paper
+does not describe a particular algorithm for star identification, with
+the implication that it is not a particularly difficult problem since
+absolute brightness information will be available-- individual stars
+are more distinctive.
+with a $56~\deg$ field of view and exposure time of $50~\unit{ms}$.
+The resulting images contain tens of stars if the spacecraft is not
+rotating, but on average only three stars will be detectable when the
+rotation rate is $50~\deg/\unit{sec}$.  The paper does not describe a
+particular algorithm for star identification, with the implication
+that it is not a particularly difficult problem since absolute
+brightness information will be available, and the total number of
+stars that are visible to the camera is only a few hundred.
 In earlier work \cite{liebe1993}, Liebe describes a star
 identification system.  The reference catalog is composed of the 1539
 brightest stars, with brightness calibrated to the camera used in the
 system.  The field of view is $30\deg$, and the system uses a
+system.  The field of view is $30~\degrees$, and the system uses a
 feature-matching approach, using the brightest star in the field and
 its two nearest neighbours to define a geometric feature.  The feature
 …
 so the scale is known.  An index is constructed by enumerating all
 such features that could possibly be detected, given the detection
 limits of the camera.
+These features are coarsely quantized and stored in a table.  To
+account for noise in the feature descriptors, all neighbouring cells
 in the quantized feature space are also stored in the table.  This
+generates 185,000 features.  At test time, the features in the image
+are enumerated and the table of features is scanned; an exact feature
+match in the quantized space is assumed to be correct.
+limits of the camera.  These features are coarsely quantized and
+stored in a table.  To account for noise in the feature descriptors,
+all neighbouring cells in the quantized feature space are also stored
+in the table.  This generates $185,000$ features.  At test time, the
+features in the image are enumerated and the table of features is
+scanned; an exact feature match in the quantized space is assumed to
+be correct.
 This approach is a fairly straightforward geometric hashing technique,
 except that it does not use hashing as such, and there is no voting or
 verification scheme because feature aliasing is assume not to happen.
+verification scheme because feature aliasing is assumed not to happen.
 \begin{figure}
 \begin{center}
 \includegraphics[width=0.9\textwidth]{grid}
+\includegraphics[width=\figunit]{grid}
 \end{center}
+\caption{A grid-based feature: two sources are used to define a local coordinate
+  system which is discretized into a grid of cells.  Each cell becomes a bit in
+  the feature descriptor; if a cell is occupied its bit is set.
+  This figure is copied from MacKay \cite{mackay2005}.}
+\caption{A grid-based feature: two sources are used to define a local
+  coordinate system which is discretized into a grid of cells.  Each
+  cell becomes a bit in the feature descriptor; if a cell is occupied
+  its bit is set.  This figure is copied from MacKay
+  \cite{mackay2005}.}
 \label{gridbased}
 \end{figure}
 …
 center and orientation are determined, a grid is defined, and each
 remaining stars in the image is assigned to a grid cell.  The feature
 is a bit vector, one bit per grid cell, where the bit is set if the
 cell contains a star, and zero otherwise.  See Figure \ref{gridbased}.
+is a bit vector, one bit per grid cell, where the bit is set only if
+the cell contains a star.  See \figref{gridbased}.
 …
 brightest $c n$ stars (for some safety factor $c$), computing the
 feature for each one and searching the index for a match.  A pair of
 features are defined to match if their dot product is above a
 threshold.  (This is equivalent to taking the bitwise \textsc{AND} of
 the bit vectors and counting the number of bits that are set.)  This
+features is defined to match if their dot product is above a
+threshold.  This is equivalent to taking the bitwise \textsc{AND} of
+the bit vectors and counting the number of bits that are set.  This
 search can be implemented efficiently by using lookup tables: for each
 bit, they maintain a list of the features for which that bit is set.
+(Notice that this is equivalent to using a grid-based geometric
+hashing approach: each grid cell is equivalent to a discretized pair
+of relative coordinates, which becomes a hash key, and the `lookup
+table' is a hash table.)
+Note that this is equivalent to using a grid-based geometric hashing
+approach: each grid cell is equivalent to a discretized relative
+coordinate vector, which becomes a hash key, and the ``lookup table''
+is a hash table.
 …
+The system is designed to operate on images of diameter $8\deg$, and
+performs well on simulated data.  They use a grid size of $40 \times
+$, and find that on average $25$ grid cells are filled.  Their index
+contains 13,000 patterns, which means that false positives are quite
+rare.  However, misidentification of the nearest neighbour, or edge
+effects (assigning a star to the wrong grid cell due to positional
+noise) mean that failures to find a match are not uncommon, and are
+more likely in regions of the sky with high stellar density.
+The system is designed to operate on images of diameter $8~\degrees$,
+and performs well on simulated data.  They use a grid size of $40
+\times 40$, and find that on average $25$ grid cells are filled.
+Their index contains $13,000$ patterns, which means that false
+positives are quite rare.  However, misidentification of the nearest
+neighbour, or edge effects (assigning a star to the wrong grid cell
+due to positional noise) mean that failures to find a match are not
+uncommon, and are more likely in regions of the sky with high stellar
+density.
 In later work, Clouse and Padgett \cite{clouse2000} extend this
 …
 extension, along with smaller noise levels in the (simulated) imaging
 system, allows them to extend the approach down to fields of view
+$2\deg$ in diameter.
+Given two features, they compute the dot product between the bit
+vectors, then proceed to estimate the probabilities that the match is
+a true positive and false positive.  These probability distributions
+are quite complex, so several simplifying approximations are made, and
+the remaining parameters are estimated by running simulations.
+% With positional noise set to $0.5$ pixels (in a $1024 \times 1024$ image),
+% and magnitude noise $0.8$ mag, they find a true positive rate of $96\%$ and false positive
+% rate of $0.3\%$.
+$2~\degrees$ in diameter.
+\comment{
+  Given two features, they compute the dot product between the bit
+  vectors, then proceed to estimate the probabilities that the match is
+  a true positive and false positive.  These probability distributions
+  are quite complex, so several simplifying approximations are made, and
+  the remaining parameters are estimated by running simulations.
+  }
 Harvey \cite{harvey2004} presents two different approaches, one
 grid-based and the other shape-based.  The grid-based approach is
 similar to \cite{padgett1997, clouse2000}.  A coarser grid is used, so
+more stars are likely to appear in each bin.  To compensate, a grid
+cell is only considered ``occupied'' if it contains more than some
+threshold number of stars.  The other major change is that he expects
+a test image to be an ``overexposure'' or ``underexposure'' relative
+to the reference catalog: the objects in the image are either brighter
+or dimmer than those in the index.  This implies that the test image
 should contain either a subset or a superset of the stars in the
 index, and therefore the image feature vector must be either greater
+than or less than an index feature at each bit.  This allows simple
+bit operations to be used to find feature matches, and feature
 matching is performed by a linear scan through the index.
+similar to the Padgett--Kreutz-Delgado and Clouse--Padgett approaches
+\cite{padgett1997, clouse2000}.  A coarser grid is used, so more stars
+are likely to appear in each bin.  To compensate, a grid cell is only
+considered ``occupied'' if it contains more than some threshold number
+of stars.  The other major change is that he expects a test image to
+be an ``overexposure'' or ``underexposure'' relative to the reference
+catalog.  This implies that the test image should contain either a
+subset or a superset of the stars in the index, and therefore the
+image feature vector must be either greater than or less than an index
+feature at each bit.  This allows simple bit operations to be used to
+find feature matches, and feature matching is performed by a linear
+scan through the index.
 Harvey's shape-based approach uses constrained $n$-star constellations
 in order to aggregate information from a larger number of stars
+without allowing the number of potential features to grow
+combinatorially.  Specifically, Harvey uses a pair of stars to define
 a narrow wedge in the image, then describes the relative positions and
+angles of a fixed number of nearby stars within that wedge.
+Unfortunately, this makes the feature highly sensitive to distractor
+and dropout stars, since the feature depends on the stars in the
+feature being enumerated in a particular order.  As a result, all
+potential features (allowing any combination of stars to drop out)
+must be checked; the number of features grows exponentially as the
+density of stars increases.
+in order to aggregate information from a large number of stars without
+allowing the number of potential features to grow combinatorially.
+Specifically, Harvey uses a pair of stars to define a narrow wedge in
+the image, then describes the relative positions and angles of a fixed
+number of nearby stars within that wedge.  Unfortunately, this makes
+the feature highly sensitive to distractor and dropout stars, since
+the feature depends on the stars in the feature being enumerated in a
+particular order.  As a result, all potential features (allowing any
+combination of stars to drop out) must be checked; the number of
+features grows exponentially as the density of stars increases.
 Harvey makes the useful observation that a cascade of indices can be
 …
 MacKay and Roweis \cite{mackay2005} point out that a grid-based
+feature such as that used by \cite{padgett1997, harvey2004} leads
+naturally to a hashing-based strategy.
+%  Each grid cell is associated with a bit that is turned on if the cell
+%is occupied.
+%This value is placed in a hash table with a mapping back to its
+%position on the sky.
+Since false positives can occur as a result of feature aliasing or
+hash collision, they employ a voting scheme.
+%several feature matches must accumulate before the
+%field can be considered solved.
+Since false negatives can occur as a result of dropouts and
+distractors (\emph{any} missing or extra star causes the hash code to
+change completely), many features must be extracted for each region of
+the sky.
+feature such as that used by Harvey leads naturally to a hashing-based
+strategy.  Each grid cell is associated with a bit that is turned on
+if the cell is occupied.  This value is placed in a hash table with a
+mapping back to its position on the sky.  Since false positives can
+occur as a result of feature aliasing or hash collision, a voting
+scheme is employed: several feature matches must accumulate before the
+match is accepted.  Since false negatives can occur as a result of
+dropouts and distractors (\emph{any} missing or extra star causes the
+hash code to change completely), many features must be extracted for
+each region of the sky.
 \subsection{Fine-tuning astrometry}
 In order to ``stack'' astronomical images (combine pixels from
 different images to produce higher-quality results), or to do
+In order to ``co-add'' or ``stack'' astronomical images (combine
+pixels from different images of higher signal-to-noise), or to do
 proper-motion studies (measure the movement of stars over time), it is
+necessary to fine-tune the astrometry of the images.  This is similar
+to the \emph{bundle adjustment} problem in computer vision
+\cite{triggs2000}, in that it involves the simultaneous optimization
+of the various camera (telescope) parameters and the estimated
+positions of objects in the world.  Fine-tuning astrometry is easier
+because it is essentially two-dimensional, but more difficult because
+the camera parameters include polynomial distortion terms to model the
+image distortion introduced by telescope optics.
+The software package \emph{SCAMP} by Bertin \cite{bertin2005} is a
+popular tool used by astronomers to fine-tune the astrometry of their
+images and solve simultaneously large collections of images.  For each
+image, it is assumed that the center of the image is known to about
+\% of the size of the image, and the scale is known to within a
+factor of two.  The histogram-alignment method of \cite{kaiser1999} is
+used to find the translation, scaling, and rotation between the image
+and a reference catalog, which allows the correspondences between
+image and reference catalog stars to be determined.
+The core of the SCAMP system is a $\chi^2$ minimization of the total
+weighted distance between the projected positions of all star
+necessary to fine-tune the astrometric calibration of their images.
+This is similar to the \emph{bundle adjustment} problem in computer
+vision \cite{triggs2000}, in that it involves the simultaneous
+optimization of the various camera and telescope parameters and the
+estimated positions of objects in the world.  Fine-tuning astrometric
+calibrations is easier because it is essentially two-dimensional, but
+more difficult because the camera parameters include polynomial
+distortion terms to model the image distortion introduced by telescope
+optics.
+The software package \scamp by Bertin \cite{bertin2005} is a popular
+tool used by astronomers to fine-tune simultaneously the astrometric
+calibrations of a large collection of images.  For each image, it is
+assumed that the center of the image is known to about 25\% of the
+size of the image, and the scale is known to within a factor of two.
+The histogram-alignment method of \cite{kaiser1999} is used to find
+the translation, scaling, and rotation between the image and a
+reference catalog, which allows the correspondences between image and
+reference catalog stars to be determined.
+The core of the \scamp system is a chi-squared minimization of the
+total weighted distance between the projected positions of all star
 correspondences among the set of images and the reference catalog.
 The parameters to be adjusted are the center, scale, rotation, and
 …
 share some distortion terms due to the telescope optics.  This reduces
 the degrees of freedom of the fitting process, resulting in more
 robust fits.  SCAMP can effectively fine-tune thousands of images to
 sub-pixel accuracy.
+robust fits.  \scamp can fine-tune thousands of images to sub-pixel
+accuracy.

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 12282 for trunk/documents/theses/dstn/review.tex

Legend:

trunk/documents/theses/dstn/review.tex

Download in other formats: