| | 912 | Extra sources can be due to planets, comets, satellites, or aircraft. |
| | 913 | Missing or poorly localized source can be due to imperfections in the |
| | 914 | imaging sensor, saturation, cosmic ray interference, or (rarely) |
| | 915 | occlusion. Errors in the image processing that detects sources can |
| | 916 | lead to sources being gained or lost. We call sources that appear in |
| | 917 | only the input image or reference catalog \emph{distractors} and |
| | 918 | \emph{dropouts}, respectively. The existence of distractors and |
| | 919 | dropouts means that we can never assume that all the objects in the |
| | 920 | reference catalog will be contained in an image to be recognized, or |
| | 921 | vice versa. |
| | 922 | |
| | 923 | |
| 936 | | An additional challenge in astrometry is that the input image and |
| 937 | | reference catalog may each have fictitious or missing sources. |
| 938 | | Extra sources can be due to planets, comets, satellites, or aircraft. |
| 939 | | Missing or poorly localized source can be due to imperfections in the |
| 940 | | imaging sensor, saturation, cosmic ray interference, or (rarely) |
| 941 | | occlusion. Errors in the image processing that detects sources can |
| 942 | | lead to sources being gained or lost. We call sources that appear in |
| 943 | | only the input image or reference catalog \emph{distractors} and |
| 944 | | \emph{dropouts}, respectively. The existence of dropouts and |
| 945 | | distractors means that we can never assume that all the objects in the |
| 946 | | reference catalog will be contained in the image, or vice versa. |
| 947 | | |
| 1009 | | astrometry problems. The first are professional astronomers, whose |
| 1010 | | images are typically of small angular extent, long exposure time, and |
| 1011 | | high quality. They typically assume that there is a good initial |
| 1012 | | guess of the astrometry and the goal is to produce a very accurate |
| 1013 | | astrometric solution, including image distortion. The second group of |
| 1014 | | researchers are spacecraft engineers who want to use astrometry to |
| 1015 | | estimate the attitude of the camera (and the spacecraft to which it is |
| 1016 | | attached). Here the images are of wide angular extent, have short |
| | 1009 | astrometric calibration. The first are professional astronomers, |
| | 1010 | whose images are typically of small angular extent, long exposure |
| | 1011 | time, and high quality. They typically assume that there is a good |
| | 1012 | initial guess of the astrometry and the goal is to produce a very |
| | 1013 | accurate astrometric calibration, including image distortion. The |
| | 1014 | second group of researchers are spacecraft engineers who want to use |
| | 1015 | the stars to estimate the attitude of a camera attached to a |
| | 1016 | spacecraft. Here the images are of wide angular extent, have short |
| 1025 | | astrometry be provided. |
| 1026 | | |
| 1027 | | |
| 1028 | | Groth \cite{groth1986} presents an algorithm for matching two lists of |
| 1029 | | coordinates (eg, image coordinates in pixels and reference star |
| 1030 | | coordinates on the celestial sphere), assuming that the lists contain |
| 1031 | | a significant proportion of objects in common. To compensate for the |
| 1032 | | limited computing resources available at the time, he suggests taking |
| 1033 | | the brightest 20 or 30 objects in each list. |
| | 1025 | astrometry be provided. Groth \cite{groth1986} presents an algorithm |
| | 1026 | for matching two lists of coordinates (eg, image coordinates in pixels |
| | 1027 | and reference star coordinates on the celestial sphere), assuming that |
| | 1028 | the lists contain a significant proportion of objects in common. With |
| | 1029 | the limited computing resources available at the time, he suggests |
| | 1030 | taking the brightest 20 or 30 objects in each list. |
| 1051 | | pair of features is less than their corresponding tolerances. (This |
| 1052 | | process can be accelerated by sorting the features on one of the |
| 1053 | | feature dimensions.) If multiple matches are found for a particular |
| 1054 | | feature, only the closest is considered. After all the features have |
| 1055 | | been compared, many correct matches should be found, along with some |
| 1056 | | false matches. For each match, the difference of the log-perimeters |
| 1057 | | of the two triangles is computed; this gives the relative scale of the |
| 1058 | | two triangles and hence the coordinate frames, assuming the match is |
| | 1048 | pair of features is less than their corresponding tolerances. This |
| | 1049 | process is accelerated by sorting the features on one of the feature |
| | 1050 | dimensions. If multiple matches are found for a particular feature, |
| | 1051 | only the closest is considered. After all the features have been |
| | 1052 | compared, many correct matches should be found, along with some false |
| | 1053 | matches. For each match, the difference of the log-perimeters of the |
| | 1054 | two triangles is computed. This gives the relative scales of the two |
| | 1055 | triangles and hence their coordinate frames, assuming the match is |
| 1111 | | symmetric point matches; this process can be accelerated by sorting |
| 1112 | | each list by one of the coordinates. Each triangle match is |
| 1113 | | considered to be a vote for the correspondence of the three pairs of |
| 1114 | | points composing the triangles. These votes are accumulated in a |
| 1115 | | sparse matrix where element $(i, j)$ contains the number of votes for |
| 1116 | | a correspondence between object $i$ in the first image and object $j$ |
| 1117 | | in the second image. After all matches are considered, the top 40\% |
| 1118 | | of the nonzero matrix elements are assumed to contain the true |
| | 1100 | symmetric point matches. This process is accelerated by sorting each |
| | 1101 | list by one of the coordinates. Each triangle match is considered to |
| | 1102 | be a vote for the correspondence of the three pairs of points |
| | 1103 | composing the triangles. These votes are accumulated in a sparse |
| | 1104 | matrix where element $(i, j)$ contains the number of votes for a |
| | 1105 | correspondence between object $i$ in the first image and object $j$ in |
| | 1106 | the second image. After all matches are considered, the top 40\% of |
| | 1107 | the nonzero matrix elements are assumed to contain the true |
| 1135 | | each image, they look at each pair of points and compute the angle and |
| 1136 | | the logarithm of the length of the vector connecting the pair. For |
| 1137 | | each list, the pairwise log-distance and angle are placed in a |
| 1138 | | two-dimensional histograms. Observe that if the whole list of points |
| | 1116 | each image, they iterate over each pair of points and compute the |
| | 1117 | vector difference of their positions. For each list, the log-length |
| | 1118 | and angle of the pairwise difference vectors are accumulated in a |
| | 1119 | two-dimensional histogram. Observe that if the whole list of points |
| 1143 | | computed. (This is the same as shifting the histograms with respect |
| 1144 | | to each other and recording the dot-product at each shifted position.) |
| 1145 | | If the two lists contain a significant number of corresponding points, |
| 1146 | | the cross-correlation signal will be strong at a shift corresponding |
| 1147 | | to the difference in log-scale and rotation between the lists. |
| 1148 | | |
| 1149 | | |
| 1150 | | This process is similar to a Hough transform |
| | 1124 | computed. If the two lists contain a significant number of |
| | 1125 | corresponding points, the cross-correlation signal will be strongest |
| | 1126 | at a shift corresponding to the difference in log-scale and rotation |
| | 1127 | between the lists. This process is similar to a Hough transform |
| 1164 | | %This procedure is simple and powerful, but requires that the transformation between |
| 1165 | | %the coordinate systems be equal across the whole image. This assumption can be violated |
| 1166 | | %(but usually not by a amount) |
| 1167 | | |
| 1168 | | |
| 1169 | | |
| 1170 | | \subsection{Blind astrometry} |
| 1171 | | |
| 1172 | | |
| 1173 | | The majority of previous work on blind astrometry is motivated by the |
| 1174 | | problem of spacecraft attitude estimation. Sometimes called the |
| 1175 | | ``lost in space'' or ``stellar gyroscope'' problem, the task is to |
| 1176 | | estimate the pose of a spacecraft by using an image of the sky |
| 1177 | | captured by an onboard camera. Although similar in general spirit, |
| 1178 | | the requirements and limitations of this application are quite |
| 1179 | | different than our astronomical application. Mass, power consumption, |
| | 1141 | \subsection{Blind astrometric calibration} |
| | 1142 | |
| | 1143 | |
| | 1144 | The majority of previous work on blind astrometric calibration is |
| | 1145 | motivated by the problem of spacecraft attitude estimation. Sometimes |
| | 1146 | called the ``lost in space'' or ``stellar gyroscope'' problem, the |
| | 1147 | task is to estimate the pose of a spacecraft by using an image of the |
| | 1148 | sky captured by an onboard camera. Although similar in general |
| | 1149 | spirit, the requirements and limitations of this application are quite |
| | 1150 | different than astronomical applications. Mass, power consumption, |
| 1197 | | with a $56 \deg$ field of view and exposure time of $50 \ |
| 1198 | | \textrm{ms}$. The resulting images contain tens of stars if the |
| 1199 | | spacecraft is not rotating, but on average only three stars will be |
| 1200 | | detectable when the rotation rate is $50\deg/\textrm{s}$. The paper |
| 1201 | | does not describe a particular algorithm for star identification, with |
| 1202 | | the implication that it is not a particularly difficult problem since |
| 1203 | | absolute brightness information will be available-- individual stars |
| 1204 | | are more distinctive. |
| | 1169 | with a $56~\deg$ field of view and exposure time of $50~\unit{ms}$. |
| | 1170 | The resulting images contain tens of stars if the spacecraft is not |
| | 1171 | rotating, but on average only three stars will be detectable when the |
| | 1172 | rotation rate is $50~\deg/\unit{sec}$. The paper does not describe a |
| | 1173 | particular algorithm for star identification, with the implication |
| | 1174 | that it is not a particularly difficult problem since absolute |
| | 1175 | brightness information will be available, and the total number of |
| | 1176 | stars that are visible to the camera is only a few hundred. |
| | 1177 | |
| 1218 | | limits of the camera. |
| 1219 | | |
| 1220 | | These features are coarsely quantized and stored in a table. To |
| 1221 | | account for noise in the feature descriptors, all neighbouring cells |
| 1222 | | in the quantized feature space are also stored in the table. This |
| 1223 | | generates 185,000 features. At test time, the features in the image |
| 1224 | | are enumerated and the table of features is scanned; an exact feature |
| 1225 | | match in the quantized space is assumed to be correct. |
| | 1191 | limits of the camera. These features are coarsely quantized and |
| | 1192 | stored in a table. To account for noise in the feature descriptors, |
| | 1193 | all neighbouring cells in the quantized feature space are also stored |
| | 1194 | in the table. This generates $185,000$ features. At test time, the |
| | 1195 | features in the image are enumerated and the table of features is |
| | 1196 | scanned; an exact feature match in the quantized space is assumed to |
| | 1197 | be correct. |
| | 1198 | |
| 1277 | | The system is designed to operate on images of diameter $8\deg$, and |
| 1278 | | performs well on simulated data. They use a grid size of $40 \times |
| 1279 | | 40$, and find that on average $25$ grid cells are filled. Their index |
| 1280 | | contains 13,000 patterns, which means that false positives are quite |
| 1281 | | rare. However, misidentification of the nearest neighbour, or edge |
| 1282 | | effects (assigning a star to the wrong grid cell due to positional |
| 1283 | | noise) mean that failures to find a match are not uncommon, and are |
| 1284 | | more likely in regions of the sky with high stellar density. |
| | 1251 | The system is designed to operate on images of diameter $8~\degrees$, |
| | 1252 | and performs well on simulated data. They use a grid size of $40 |
| | 1253 | \times 40$, and find that on average $25$ grid cells are filled. |
| | 1254 | Their index contains $13,000$ patterns, which means that false |
| | 1255 | positives are quite rare. However, misidentification of the nearest |
| | 1256 | neighbour, or edge effects (assigning a star to the wrong grid cell |
| | 1257 | due to positional noise) mean that failures to find a match are not |
| | 1258 | uncommon, and are more likely in regions of the sky with high stellar |
| | 1259 | density. |
| 1291 | | $2\deg$ in diameter. |
| 1292 | | |
| 1293 | | Given two features, they compute the dot product between the bit |
| 1294 | | vectors, then proceed to estimate the probabilities that the match is |
| 1295 | | a true positive and false positive. These probability distributions |
| 1296 | | are quite complex, so several simplifying approximations are made, and |
| 1297 | | the remaining parameters are estimated by running simulations. |
| 1298 | | % With positional noise set to $0.5$ pixels (in a $1024 \times 1024$ image), |
| 1299 | | % and magnitude noise $0.8$ mag, they find a true positive rate of $96\%$ and false positive |
| 1300 | | % rate of $0.3\%$. |
| 1301 | | |
| 1302 | | |
| 1303 | | |
| | 1266 | $2~\degrees$ in diameter. |
| | 1267 | |
| | 1268 | \comment{ |
| | 1269 | Given two features, they compute the dot product between the bit |
| | 1270 | vectors, then proceed to estimate the probabilities that the match is |
| | 1271 | a true positive and false positive. These probability distributions |
| | 1272 | are quite complex, so several simplifying approximations are made, and |
| | 1273 | the remaining parameters are estimated by running simulations. |
| | 1274 | } |
| 1307 | | similar to \cite{padgett1997, clouse2000}. A coarser grid is used, so |
| 1308 | | more stars are likely to appear in each bin. To compensate, a grid |
| 1309 | | cell is only considered ``occupied'' if it contains more than some |
| 1310 | | threshold number of stars. The other major change is that he expects |
| 1311 | | a test image to be an ``overexposure'' or ``underexposure'' relative |
| 1312 | | to the reference catalog: the objects in the image are either brighter |
| 1313 | | or dimmer than those in the index. This implies that the test image |
| 1314 | | should contain either a subset or a superset of the stars in the |
| 1315 | | index, and therefore the image feature vector must be either greater |
| 1316 | | than or less than an index feature at each bit. This allows simple |
| 1317 | | bit operations to be used to find feature matches, and feature |
| 1318 | | matching is performed by a linear scan through the index. |
| | 1278 | similar to the Padgett--Kreutz-Delgado and Clouse--Padgett approaches |
| | 1279 | \cite{padgett1997, clouse2000}. A coarser grid is used, so more stars |
| | 1280 | are likely to appear in each bin. To compensate, a grid cell is only |
| | 1281 | considered ``occupied'' if it contains more than some threshold number |
| | 1282 | of stars. The other major change is that he expects a test image to |
| | 1283 | be an ``overexposure'' or ``underexposure'' relative to the reference |
| | 1284 | catalog. This implies that the test image should contain either a |
| | 1285 | subset or a superset of the stars in the index, and therefore the |
| | 1286 | image feature vector must be either greater than or less than an index |
| | 1287 | feature at each bit. This allows simple bit operations to be used to |
| | 1288 | find feature matches, and feature matching is performed by a linear |
| | 1289 | scan through the index. |
| 1321 | | in order to aggregate information from a larger number of stars |
| 1322 | | without allowing the number of potential features to grow |
| 1323 | | combinatorially. Specifically, Harvey uses a pair of stars to define |
| 1324 | | a narrow wedge in the image, then describes the relative positions and |
| 1325 | | angles of a fixed number of nearby stars within that wedge. |
| 1326 | | Unfortunately, this makes the feature highly sensitive to distractor |
| 1327 | | and dropout stars, since the feature depends on the stars in the |
| 1328 | | feature being enumerated in a particular order. As a result, all |
| 1329 | | potential features (allowing any combination of stars to drop out) |
| 1330 | | must be checked; the number of features grows exponentially as the |
| 1331 | | density of stars increases. |
| | 1292 | in order to aggregate information from a large number of stars without |
| | 1293 | allowing the number of potential features to grow combinatorially. |
| | 1294 | Specifically, Harvey uses a pair of stars to define a narrow wedge in |
| | 1295 | the image, then describes the relative positions and angles of a fixed |
| | 1296 | number of nearby stars within that wedge. Unfortunately, this makes |
| | 1297 | the feature highly sensitive to distractor and dropout stars, since |
| | 1298 | the feature depends on the stars in the feature being enumerated in a |
| | 1299 | particular order. As a result, all potential features (allowing any |
| | 1300 | combination of stars to drop out) must be checked; the number of |
| | 1301 | features grows exponentially as the density of stars increases. |
| | 1302 | |
| 1340 | | feature such as that used by \cite{padgett1997, harvey2004} leads |
| 1341 | | naturally to a hashing-based strategy. |
| 1342 | | % Each grid cell is associated with a bit that is turned on if the cell |
| 1343 | | %is occupied. |
| 1344 | | %This value is placed in a hash table with a mapping back to its |
| 1345 | | %position on the sky. |
| 1346 | | Since false positives can occur as a result of feature aliasing or |
| 1347 | | hash collision, they employ a voting scheme. |
| 1348 | | %several feature matches must accumulate before the |
| 1349 | | %field can be considered solved. |
| 1350 | | Since false negatives can occur as a result of dropouts and |
| 1351 | | distractors (\emph{any} missing or extra star causes the hash code to |
| 1352 | | change completely), many features must be extracted for each region of |
| 1353 | | the sky. |
| | 1310 | feature such as that used by Harvey leads naturally to a hashing-based |
| | 1311 | strategy. Each grid cell is associated with a bit that is turned on |
| | 1312 | if the cell is occupied. This value is placed in a hash table with a |
| | 1313 | mapping back to its position on the sky. Since false positives can |
| | 1314 | occur as a result of feature aliasing or hash collision, a voting |
| | 1315 | scheme is employed: several feature matches must accumulate before the |
| | 1316 | match is accepted. Since false negatives can occur as a result of |
| | 1317 | dropouts and distractors (\emph{any} missing or extra star causes the |
| | 1318 | hash code to change completely), many features must be extracted for |
| | 1319 | each region of the sky. |
| 1361 | | necessary to fine-tune the astrometry of the images. This is similar |
| 1362 | | to the \emph{bundle adjustment} problem in computer vision |
| 1363 | | \cite{triggs2000}, in that it involves the simultaneous optimization |
| 1364 | | of the various camera (telescope) parameters and the estimated |
| 1365 | | positions of objects in the world. Fine-tuning astrometry is easier |
| 1366 | | because it is essentially two-dimensional, but more difficult because |
| 1367 | | the camera parameters include polynomial distortion terms to model the |
| 1368 | | image distortion introduced by telescope optics. |
| 1369 | | |
| 1370 | | The software package \emph{SCAMP} by Bertin \cite{bertin2005} is a |
| 1371 | | popular tool used by astronomers to fine-tune the astrometry of their |
| 1372 | | images and solve simultaneously large collections of images. For each |
| 1373 | | image, it is assumed that the center of the image is known to about |
| 1374 | | 25\% of the size of the image, and the scale is known to within a |
| 1375 | | factor of two. The histogram-alignment method of \cite{kaiser1999} is |
| 1376 | | used to find the translation, scaling, and rotation between the image |
| 1377 | | and a reference catalog, which allows the correspondences between |
| 1378 | | image and reference catalog stars to be determined. |
| 1379 | | |
| 1380 | | The core of the SCAMP system is a $\chi^2$ minimization of the total |
| 1381 | | weighted distance between the projected positions of all star |
| | 1327 | necessary to fine-tune the astrometric calibration of their images. |
| | 1328 | This is similar to the \emph{bundle adjustment} problem in computer |
| | 1329 | vision \cite{triggs2000}, in that it involves the simultaneous |
| | 1330 | optimization of the various camera and telescope parameters and the |
| | 1331 | estimated positions of objects in the world. Fine-tuning astrometric |
| | 1332 | calibrations is easier because it is essentially two-dimensional, but |
| | 1333 | more difficult because the camera parameters include polynomial |
| | 1334 | distortion terms to model the image distortion introduced by telescope |
| | 1335 | optics. |
| | 1336 | |
| | 1337 | |
| | 1338 | The software package \scamp by Bertin \cite{bertin2005} is a popular |
| | 1339 | tool used by astronomers to fine-tune simultaneously the astrometric |
| | 1340 | calibrations of a large collection of images. For each image, it is |
| | 1341 | assumed that the center of the image is known to about 25\% of the |
| | 1342 | size of the image, and the scale is known to within a factor of two. |
| | 1343 | The histogram-alignment method of \cite{kaiser1999} is used to find |
| | 1344 | the translation, scaling, and rotation between the image and a |
| | 1345 | reference catalog, which allows the correspondences between image and |
| | 1346 | reference catalog stars to be determined. |
| | 1347 | |
| | 1348 | The core of the \scamp system is a chi-squared minimization of the |
| | 1349 | total weighted distance between the projected positions of all star |