<p>I've been trying to figure out the technical details of astrometry.net for quite some time. As others already pointed out, the main input to the whole process is a list of stars. I will not go into details on how astrometry.net does it, just note that you can either use its internal <code>simplexy</code> algorithm or use <code>SExtractor</code>. In the end you need a list of coordinates for stars (plus optional flux/intensity/brightness and background).</p>
<p>The <code>.xyls</code> files are used to store these input values (small example):</p>
<pre><code> x-coord(px)   y-coord(px)        flux  background
 1008.911987,   557.925659,  10.556271,  32.320175,
 1449.509277,   643.280212,   6.580036,  27.963276,
  185.978119,  1253.869751,   5.525373,  27.713015,
</code></pre>
<p>Background is approximated before/during star extraction (<code>SExtractor</code> has a function for that).</p>
<p>Now the algorithm goes into creating <code>quads</code>. The cited paper always talks about 4 stars that form a <code>quad</code>. But by my own experiments they seem to be just triangles. Maybe they should have better named them &quot;Asterism&quot; (the code has a lot of very bad naming, as we soon will discover, took me hours to figure out).</p>
<p>So we have a triangle and want to know if a similar triangle exists anywhere in the selected astrometry.net index. So this is where the real magic happens IMO. The papers talks about <code>geometrically hashed</code> lookup. IMO the word &quot;hash&quot; is a bit misleading here as it has not much in common with real hashes. Real hashes should normally give very different results for small changes in the input (e.g. checksum or hash-table bucket distributions). I would rather say that they perform a geometric transformation where the result must be a one-dimensional value (e.g. a <code>double</code> value).</p>
<p>Abstractly speaking we want to map numerous properties to a single value. The value should vary very little if the overall properties also vary little, so from looking at the delta of both translation results we can deduct how similar the two objects were. One such property could e.g. be the angle between two lines.</p>
<p>From here it should be &quot;obvious&quot; how one can use this approach to drive a search. In this simple one-dimensional case we could e.g. use a binary search. For astrometry.net this problem gets technically more complicated, as we need to search for two &quot;hashes&quot;. This is done with a KD-Tree. The one used by astrometry.net is optimized for the pre-built index files, so they can be accessed very fast and without much (memory) overhead. Basically a KD-Tree can optimize the question &quot;give me the closest point(s) to X/Y&quot;.</p>
<p>In the picture below I tried to visualize how we can search for similar triangles by reducing the question to two numbers. We basically search for the normalized blue vectors (or ones that are pretty close). It should be obvious that this eliminates any rotation and scaling in the question asked, so any similarly shaped triangle will match, regardless of orientation or size. IMO it simply boils down to the fact that the shape of a triangle is defined by two parameters, e.g. not sure why they didn't use two angles.</p>
<p><a href="https://i.sstatic.net/Z2Ybw.png" rel="noreferrer"><img src="https://i.sstatic.net/Z2Ybw.png" alt="geometric hashing of triangles" /></a></p>
<p>In reality we have to make the lookup multiple times to also search for flipped and/or inverted variations. After a similar triangle is found (this will happen a lot), the process goes into the verification step. The resulting triangle will give the program the hint on how all other stars must be translated to match the given triangle. With that it can try to match all other stars with its know star catalog.</p>
<blockquote>
<p>Query images may contain some extra stars that are not in your index catalogue, and some catalogue stars may be missing from the image.</p>
</blockquote>
<p>These can be seen as distractors and conflicts? in the debug output of the program:</p>
<pre><code>verify: logodds -1.38629, 0 matches, 0 conflicts, 1 distractors after 0 field objects.
verify: logodds 333.123, 99 matches, 0 conflicts, 115 distractors after 213 field objects.
108 matches, 424 distractors, 2 conflicts (all sources)
</code></pre>
<p>I believe these numbers are not &quot;really&quot; accurate as the checker will probably bail out once it thinks it is impossibly a match (e.g. after certain distractors are found without any matches). Anyway, this is more or less to whole process in detail. I left out some of the magic, e.g. there are a lot of probability checks for speed. Also the way potential <code>quads</code> are chosen from all stars is quite elaborate in reality (and should probably match closely to how this was done when the index files were created).</p>
<p>Side note on indexes: As they contain x/y positions for known stars and stars wander a little over time (a few faster, most very slow), the index can get outdated and start to not match (no idea if this would be in a decade or a millenium). Regular star catalogs give x/y position at a given epoch time plus x/y-speeds to calculate the actual position in any given point of time. IMO with modern CPUs this can be done in seconds for millions of stars (so time independent indexes could be doable, although probably not for the initial triangle matching, but surely for the verify phase). Also with the new ESO Gaia data releases there shouldn't be any gaps anymore (as noted by astrometry.net as small holes in the USNO-B1.0 catalog). But it seems the official available indexes haven't been updated yet to use the new gaia catalog.</p>
<p>Disclaimer: This knowledge was acquired mostly by reading and testing with the astrometry.net source code. So any conclusions I made could be wrong. But I would say it all makes sense if put together. Below I'll give a few more details into the actual implementation inside astrometry.net.</p>
<p>Edit: After reading <a href="https://iopscience.iop.org/article/10.1088/0004-6256/139/5/1782" rel="noreferrer">https://iopscience.iop.org/article/10.1088/0004-6256/139/5/1782</a> I came to the conclusion that real quads with four stars are probably used in indexes with smaller view angles (zoomed in). I used a picture taken with a regular 55mm DSLR lens for my tests. This would make sense and it basically is exactly what an n-dimensional tree is made for (the question for the closest neighbors now involves 4 parameters).</p>
<p>Each <code>index_t</code> contains two KD-Trees, namely <code>codekd</code> and <code>starkd</code>. The tree <code>codekd</code> contains the information of all &quot;quads&quot;, while <code>starkd</code> contains regular star coordinates for later verification.</p>
<p>The &quot;hashing&quot; bits can interestingly be found in &quot;solver.c&quot; in the function &quot;check_inbox&quot;.</p>
<pre><code>static void check_inbox(pquad* pq, int start, solver_t* solver) {
    int i;
    double Ax, Ay;
    field_getxy(solver, pq-&gt;fieldA, &amp;Ax, &amp;Ay);
    // check which C, D points are inside the circle.
    for (i = start; i &lt; pq-&gt;ninbox; i++) {
        double r;
        double Cx, Cy, xxtmp;
        double tol = solver-&gt;codetol;
        if (!pq-&gt;inbox[i])
            continue;
        field_getxy(solver, i, &amp;Cx, &amp;Cy);
        Cx -= Ax;
        Cy -= Ay;
        xxtmp = Cx;
        Cx = Cx * pq-&gt;costheta + Cy * pq-&gt;sintheta;
        Cy = -xxtmp * pq-&gt;sintheta + Cy * pq-&gt;costheta;

        // make sure it's in the circle centered at (0.5, 0.5)
        // with radius 1/sqrt(2) (plus codetol for fudge):
        // (x-1/2)^2 + (y-1/2)^2   &lt;=   (r + codetol)^2
        // x^2-x+1/4 + y^2-y+1/4   &lt;=   (1/sqrt(2) + codetol)^2
        // x^2-x + y^2-y + 1/2     &lt;=   1/2 + sqrt(2)*codetol + codetol^2
        // x^2-x + y^2-y           &lt;=   sqrt(2)*codetol + codetol^2
        r = (Cx * Cx - Cx) + (Cy * Cy - Cy);
        if (r &gt; (tol * (M_SQRT2 + tol))) {
            pq-&gt;inbox[i] = FALSE;
            continue;
        }
        setx(pq-&gt;xy, i, Cx);
        sety(pq-&gt;xy, i, Cy);
    }
}
</code></pre>
<p>The <code>pquads</code> are the potential &quot;asterisms&quot; we are currently creating, and this function's job is to set the &quot;query&quot; parameters via &quot;set[xy]&quot; on the bottom. Those are the actual values later looked up in the <code>codekd</code> tree.</p>
<p>A <code>pquad</code> is basically a line between two points (also called backbone-stars) called <code>fieldA</code> and <code>fieldB</code> (which are actually indexes to get an x/y position). Additionally it must have at least one additioanl <code>xy</code> point (exactly one in our triangular case). The <code>pquad</code> also contains <code>sintheta</code> and <code>costheta</code> (set in <code>check_scale</code>).</p>
<pre><code>    double dx, dy;
    dx = field_getx(s, pq-&gt;fieldB) - field_getx(s, pq-&gt;fieldA);
    dy = field_gety(s, pq-&gt;fieldB) - field_gety(s, pq-&gt;fieldA);
    pq-&gt;scale = dx*dx + dy*dy;
    pq-&gt;costheta = (dy + dx) / pq-&gt;scale;
    pq-&gt;sintheta = (dy - dx) / pq-&gt;scale;
</code></pre>
<p>As we see both code parts translate and scale the vector AC in relation to the line AB.</p>
<p>I hope this info is useful to somebody, even if it got a bit long!</p>

CC BY-SA 4.0
2020-12-30T09:44:14.830Z
Wow, it's great when a new user jumps right in and nicely tackles an old and challenging question! Thank you for digging into this.
uhoh
CC BY-SA 4.0
2020-12-30T06:55:04.890Z
2020-12-30T09:24:23.200Z
2020-12-30T09:24:23.200Z
Marcel Greter
<p>Finding an astrometric solution from an image with Astrometry.net  is usually called plate solving. As mentioned in the comments, it is based on pattern matching, using a large set of databases that are pre-computed for various field of view and plate (or pixel) scale. The ArXiv paper <a href="https://arxiv.org/abs/0910.2233" rel="noreferrer">Astrometry.net: Blind astrometric calibration of arbitrary astronomical images</a> provides some details of how it works. From their abstract ...</p>

<blockquote>
  <p>After robust source detection is performed in the input image, asterisms (sets of four or five stars) are geometrically hashed and compared to pre-indexed hashes to generate hypotheses about the astrometric calibration. A hypothesis is only accepted as true if it passes a Bayesian decision theory test against a null hypothesis.</p>
</blockquote>

<p>The blind solution described in the paper is obtained directly from a photo without any additional input, but even a rough guess for the field of view can provide considerable speedup by narrowing the number of databases to be searched. Additional speedup is possible if the scale (arcsec/pixel), FOV and approximate coordinates in the sky are provided.</p>

<p>Astrometry.net code and databases can also be downloaded and run locally on unix/linux computers, and on Windows using Cygwin. There are several other plate solvers available, often included with, or designed to interface with, software that controls a telescope, mount, camera, etc. for astrophotography.</p>

<p><strong>Edit:</strong> Some additional info related to the comments.</p>

<p>In finding a solution, they must deal with imperfections of real images, including defects, optical and atmospheric distortion, etc. along with small positional changes of stars. Roughly speaking, they obtain a solution by using a best fit to several asterisms, each containing a small number of stars.</p>

<blockquote>
  <p>Noise in the image and distortion caused by the atmosphere and telescope optics lead to noise in the measured positions of stars in the image. In general this noise causes the stars in a quad to move slightly with respect to each other, which yields small changes in the hash code (i.e., position in code space) of the quad. Therefore, we must always match the image hash code with a neighborhood of hash codes in the index.</p>
</blockquote>

<p>Also, they are able to ignore defects and  moving objects like planets, asteroids, etc. in finding matches.</p>

<blockquote>
  <p>However, we also know that some fraction of the stars in the query image will have no counterpart in the index, due to occlusions or artifacts in the images, errors in star detection or localization, differences in the spectral bandpass, or because the query image "star" is actually a planet, satellite, comet, or some other non-star, non-galaxy object. True stars can be lost, and false stars can be added. Our foreground model is therefore a mixture of a uniform probability that a star will be found anywhere in the image--a query star that has no counterpart in the index--plus a blob of probability around each star in the index, where the size of the blob is determined by the combined positional variances of the index and query stars.</p>
</blockquote>

<p>Their goal was not to achieve high astrometric precision.</p>

<blockquote>
  <p>There are several automated calibration systems that refine the astrometric calibration of an image to produce a high-precision alignment to a reference catalog given a good first guess (for example, Valdes et al. 1995; Mink 2006; Bertin 2005). These systems are reliable and robust, but they require a reasonable first guess about the image pointing, orientation, and scale. Our system can be used to create that good first guess.</p>
</blockquote>

CC BY-SA 4.0
2019-10-04T01:51:20.287Z
@MagicOctopusUrn the point is to have software that works with any image, 100 year old plates with obscure serial numbers, erroneous exposures, etc. The second line in the abstract says **The system requires no first guess, and works with the information in the image pixels alone; that is, the problem is a generalization of the "lost in space" problem in which nothing--not even the image scale--is known.** It's not for cell phone photos, this is just an "edge case"!
uhoh
CC BY-SA 4.0
2019-10-04T01:55:24.877Z
@amateurAstro Thank you for your extremely helpful answer! The ArXiv paper is excellent, and poking around further I found a Github site: https://github.com/dstndstn/astrometry.net
uhoh
CC BY-SA 4.0
2019-10-04T19:40:47.217Z
Fascinating. One of those "why didn't I think of that" applications. Asterisms is a known concept for human skywatching, https://en.wikipedia.org/wiki/Asterism_(astronomy), and (relative) star positions from anywhere (and any time) on Earth barely ever change. So, use a reduced version (limit to 4- or 5-star groups) and hash all combinations.
Jeff Y
CC BY-SA 4.0
2019-10-07T13:49:06.197Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/99554/discussion-on-answer-by-amateurastro-how-the-heck-does-astrometry-net-work).
called2voyage
CC BY-SA 4.0
2019-10-03T17:45:01.230Z
2019-10-04T16:39:12.197Z
2019-10-04T16:39:12.197Z
amateurAstro
<p>What magic is this? </p>

<p><a href="https://astronomy.stackexchange.com/a/33573/7982">This answer</a> to my question <em>Astronomy detective question: what part of the sky are these photos of? What are a few of the stars?</em> nails it, and the output (linked there) contains the following images along with a whole lot more information.</p>

<p>The images are analyzed by <a href="http://astrometry.net/" rel="noreferrer">astrometry.net</a></p>

<p>How does it do what it does? If I understand correctly you can upload random star images with a wide variety of fields of view (from telescopes to cell phones) and random orientations and no further information, and it figures it out.</p>

<p>Is there a way to explain how the algorithm works with more detail than "a computer matches the dots to known stars"? </p>

<p>Related question about these cell phone images: <a href="https://photo.stackexchange.com/q/112389/50110">Milky Way with a cell phone, how is this possible?</a></p>

<p><a href="https://i.sstatic.net/yJISx.png" rel="noreferrer"><img src="https://i.sstatic.net/yJISx.png" alt="enter image description here"></a></p>

<p><a href="https://i.sstatic.net/RH0eB.png" rel="noreferrer"><img src="https://i.sstatic.net/RH0eB.png" alt="enter image description here"></a> <a href="https://i.sstatic.net/JyAbi.png" rel="noreferrer"><img src="https://i.sstatic.net/JyAbi.png" alt="enter image description here"></a></p>

<p><a href="https://i.sstatic.net/nQDPE.png" rel="noreferrer"><img src="https://i.sstatic.net/nQDPE.png" alt="enter image description here"></a></p>

CC BY-SA 4.0
2019-10-03T16:27:15.697Z
Matching algorithms are pretty standard nowadays - what is it you hope to get as an answer?
Rory Alsop
CC BY-SA 4.0
2019-10-03T16:37:22.147Z
@AtmosphericPrisonEscape thanks for the edit, while I kind-of like the sound of *Astronetry* I guess this isn't the right place to invent new random words
uhoh
CC BY-SA 4.0
2019-10-03T17:19:34.393Z
If this is proprietary software, you may never know.  If it's open source, then grab the source (and a bottle of your favorite spirits) and start reading.
Carl Witthoft
CC BY-SA 4.0
2019-10-04T01:48:22.483Z
@JanDaggen the material may be irrelevant to you but not to everyone (and not to me). Thanks.
uhoh
CC BY-SA 4.0
2019-10-04T01:52:14.573Z
@CarlWitthoft **wrong!** It's in Github! Python, open source, etc...
uhoh
CC BY-SA 4.0
2019-10-04T03:02:51.997Z
I fail to see how @CarlWitthoft is wrong.  Perhaps you did not read his comment correctly.
StephenG - Help Ukraine
CC BY-SA 4.0
2019-10-04T03:32:56.347Z
@StephenG I'll look into it, but my first inclination is to see proprietary and open source as orthogonal. "We may never know" doesn't seem to be valid as far as I can tell either. If I'm wrong on either count, please let me know and cite a source, thanks!
uhoh
CC BY-SA 4.0
2019-10-04T04:33:21.610Z
Your interpretation of Carl's comment is quite a long way off.   Carl said "IF A then B.  IF X then Y."  You appear to be taking that as "A is true and B is true." and just not bothering with the rest.  Carl's second sentence is very clearly saying that IF it is open source you can read that and find your answer.
StephenG - Help Ukraine
CC BY-SA 4.0
2019-10-04T05:01:23.483Z
@StephenG okay I'll put that in the queue, *thanks!*
uhoh
CC BY-SA 4.0
2019-10-04T05:39:47.413Z
Hm, guess which stupid conspiracy theory insists that "star constellations do not change" and yet the results of astronomy.net, which relies on that property alone, are completely incompatible with that "theory"?
Hagen von Eitzen
CC BY-SA 4.0
2019-10-04T06:54:56.963Z
@HagenvonEitzen that could be turned into SE Question format, e.g.  *Does* Astrometry.net *take into account the motion of planets and known asteroids, and known proper motion and parallax when available?* I haven't had a chance to actually read the ArXiv paper mentioned in [the answer](https://astronomy.stackexchange.com/a/33576/7982) but it might be answered there already.
uhoh
<photography><software><astrometry><algorithm>
How (the heck) does Astrometry.net work?
uhoh
# How (the heck) does Astrometry.net work?

(Asked by: username_0 on 2019-10-03)

What magic is this?

[This answer](https://astronomy.stackexchange.com/a/33573/7982) to my question *Astronomy detective question: what part of the sky are these photos of? What are a few of the stars?* nails it, and the output (linked there) contains the following images along with a whole lot more information.

The images are analyzed by [astrometry.net](http://astrometry.net/)

How does it do what it does? If I understand correctly you can upload random star images with a wide variety of fields of view (from telescopes to cell phones) and random orientations and no further information, and it figures it out.

Is there a way to explain how the algorithm works with more detail than "a computer matches the dots to known stars"?

Related question about these cell phone images: [Milky Way with a cell phone, how is this possible?](https://photo.stackexchange.com/q/112389/50110)

[![enter image description here](https://i.sstatic.net/yJISx.png)](https://i.sstatic.net/yJISx.png)

[![enter image description here](https://i.sstatic.net/RH0eB.png)](https://i.sstatic.net/RH0eB.png) [![enter image description here](https://i.sstatic.net/JyAbi.png)](https://i.sstatic.net/JyAbi.png)

[![enter image description here](https://i.sstatic.net/nQDPE.png)](https://i.sstatic.net/nQDPE.png)

**Tags:** photography, software, astrometry, algorithm

> **Comments:**
> **username_1**: Matching algorithms are pretty standard nowadays - what is it you hope to get as an answer?  
> **username_0**: @AtmosphericPrisonEscape thanks for the edit, while I kind-of like the sound of *Astronetry* I guess this isn't the right place to invent new random words  
> **username_2**: If this is proprietary software, you may never know.  If it's open source, then grab the source (and a bottle of your favorite spirits) and start reading.  
> **username_0**: @JanDaggen the material may be irrelevant to you but not to everyone (and not to me). Thanks.  
> **username_0**: @username_2 **wrong!** It's in Github! Python, open source, etc...  
> **username_3**: I fail to see how @username_2 is wrong.  Perhaps you did not read his comment correctly.  
> **username_0**: @username_3 I'll look into it, but my first inclination is to see proprietary and open source as orthogonal. "We may never know" doesn't seem to be valid as far as I can tell either. If I'm wrong on either count, please let me know and cite a source, thanks!  
> **username_3**: Your interpretation of username_2's comment is quite a long way off.   username_2 said "IF A then B.  IF X then Y."  You appear to be taking that as "A is true and B is true." and just not bothering with the rest.  username_2's second sentence is very clearly saying that IF it is open source you can read that and find your answer.  
> **username_0**: @username_3 okay I'll put that in the queue, *thanks!*  
> **username_4**: Hm, guess which stupid conspiracy theory insists that "star constellations do not change" and yet the results of astronomy.net, which relies on that property alone, are completely incompatible with that "theory"?  
> **username_0**: @username_4 that could be turned into SE Question format, e.g.  *Does* Astrometry.net *take into account the motion of planets and known asteroids, and known proper motion and parallax when available?* I haven't had a chance to actually read the ArXiv paper mentioned in [the answer](https://astronomy.stackexchange.com/a/33576/7982) but it might be answered there already.  

---

## 2 answers

### Answer by username_5 on 2020-12-30. Score: 18

I've been trying to figure out the technical details of astrometry.net for quite some time. As others already pointed out, the main input to the whole process is a list of stars. I will not go into details on how astrometry.net does it, just note that you can either use its internal `simplexy` algorithm or use `SExtractor`. In the end you need a list of coordinates for stars (plus optional flux/intensity/brightness and background).

The `.xyls` files are used to store these input values (small example):

```
 x-coord(px)   y-coord(px)        flux  background
 1008.911987,   557.925659,  10.556271,  32.320175,
 1449.509277,   643.280212,   6.580036,  27.963276,
  185.978119,  1253.869751,   5.525373,  27.713015,

```

Background is approximated before/during star extraction (`SExtractor` has a function for that).

Now the algorithm goes into creating `quads`. The cited paper always talks about 4 stars that form a `quad`. But by my own experiments they seem to be just triangles. Maybe they should have better named them "Asterism" (the code has a lot of very bad naming, as we soon will discover, took me hours to figure out).

So we have a triangle and want to know if a similar triangle exists anywhere in the selected astrometry.net index. So this is where the real magic happens IMO. The papers talks about `geometrically hashed` lookup. IMO the word "hash" is a bit misleading here as it has not much in common with real hashes. Real hashes should normally give very different results for small changes in the input (e.g. checksum or hash-table bucket distributions). I would rather say that they perform a geometric transformation where the result must be a one-dimensional value (e.g. a `double` value).

Abstractly speaking we want to map numerous properties to a single value. The value should vary very little if the overall properties also vary little, so from looking at the delta of both translation results we can deduct how similar the two objects were. One such property could e.g. be the angle between two lines.

From here it should be "obvious" how one can use this approach to drive a search. In this simple one-dimensional case we could e.g. use a binary search. For astrometry.net this problem gets technically more complicated, as we need to search for two "hashes". This is done with a KD-Tree. The one used by astrometry.net is optimized for the pre-built index files, so they can be accessed very fast and without much (memory) overhead. Basically a KD-Tree can optimize the question "give me the closest point(s) to X/Y".

In the picture below I tried to visualize how we can search for similar triangles by reducing the question to two numbers. We basically search for the normalized blue vectors (or ones that are pretty close). It should be obvious that this eliminates any rotation and scaling in the question asked, so any similarly shaped triangle will match, regardless of orientation or size. IMO it simply boils down to the fact that the shape of a triangle is defined by two parameters, e.g. not sure why they didn't use two angles.

[![geometric hashing of triangles](https://i.sstatic.net/Z2Ybw.png)](https://i.sstatic.net/Z2Ybw.png)

In reality we have to make the lookup multiple times to also search for flipped and/or inverted variations. After a similar triangle is found (this will happen a lot), the process goes into the verification step. The resulting triangle will give the program the hint on how all other stars must be translated to match the given triangle. With that it can try to match all other stars with its know star catalog.

> Query images may contain some extra stars that are not in your index catalogue, and some catalogue stars may be missing from the image.

These can be seen as distractors and conflicts? in the debug output of the program:

```
verify: logodds -1.38629, 0 matches, 0 conflicts, 1 distractors after 0 field objects.
verify: logodds 333.123, 99 matches, 0 conflicts, 115 distractors after 213 field objects.
108 matches, 424 distractors, 2 conflicts (all sources)

```

I believe these numbers are not "really" accurate as the checker will probably bail out once it thinks it is impossibly a match (e.g. after certain distractors are found without any matches). Anyway, this is more or less to whole process in detail. I left out some of the magic, e.g. there are a lot of probability checks for speed. Also the way potential `quads` are chosen from all stars is quite elaborate in reality (and should probably match closely to how this was done when the index files were created).

Side note on indexes: As they contain x/y positions for known stars and stars wander a little over time (a few faster, most very slow), the index can get outdated and start to not match (no idea if this would be in a decade or a millenium). Regular star catalogs give x/y position at a given epoch time plus x/y-speeds to calculate the actual position in any given point of time. IMO with modern CPUs this can be done in seconds for millions of stars (so time independent indexes could be doable, although probably not for the initial triangle matching, but surely for the verify phase). Also with the new ESO Gaia data releases there shouldn't be any gaps anymore (as noted by astrometry.net as small holes in the USNO-B1.0 catalog). But it seems the official available indexes haven't been updated yet to use the new gaia catalog.

Disclaimer: This knowledge was acquired mostly by reading and testing with the astrometry.net source code. So any conclusions I made could be wrong. But I would say it all makes sense if put together. Below I'll give a few more details into the actual implementation inside astrometry.net.

Edit: After reading <https://iopscience.iop.org/article/10.1088/0004-6256/139/5/1782> I came to the conclusion that real quads with four stars are probably used in indexes with smaller view angles (zoomed in). I used a picture taken with a regular 55mm DSLR lens for my tests. This would make sense and it basically is exactly what an n-dimensional tree is made for (the question for the closest neighbors now involves 4 parameters).

Each `index_t` contains two KD-Trees, namely `codekd` and `starkd`. The tree `codekd` contains the information of all "quads", while `starkd` contains regular star coordinates for later verification.

The "hashing" bits can interestingly be found in "solver.c" in the function "check\_inbox".

```
static void check_inbox(pquad* pq, int start, solver_t* solver) {
    int i;
    double Ax, Ay;
    field_getxy(solver, pq->fieldA, &Ax, &Ay);
    // check which C, D points are inside the circle.
    for (i = start; i < pq->ninbox; i++) {
        double r;
        double Cx, Cy, xxtmp;
        double tol = solver->codetol;
        if (!pq->inbox[i])
            continue;
        field_getxy(solver, i, &Cx, &Cy);
        Cx -= Ax;
        Cy -= Ay;
        xxtmp = Cx;
        Cx = Cx * pq->costheta + Cy * pq->sintheta;
        Cy = -xxtmp * pq->sintheta + Cy * pq->costheta;

        // make sure it's in the circle centered at (0.5, 0.5)
        // with radius 1/sqrt(2) (plus codetol for fudge):
        // (x-1/2)^2 + (y-1/2)^2   <=   (r + codetol)^2
        // x^2-x+1/4 + y^2-y+1/4   <=   (1/sqrt(2) + codetol)^2
        // x^2-x + y^2-y + 1/2     <=   1/2 + sqrt(2)*codetol + codetol^2
        // x^2-x + y^2-y           <=   sqrt(2)*codetol + codetol^2
        r = (Cx * Cx - Cx) + (Cy * Cy - Cy);
        if (r > (tol * (M_SQRT2 + tol))) {
            pq->inbox[i] = FALSE;
            continue;
        }
        setx(pq->xy, i, Cx);
        sety(pq->xy, i, Cy);
    }
}

```

The `pquads` are the potential "asterisms" we are currently creating, and this function's job is to set the "query" parameters via "set[xy]" on the bottom. Those are the actual values later looked up in the `codekd` tree.

A `pquad` is basically a line between two points (also called backbone-stars) called `fieldA` and `fieldB` (which are actually indexes to get an x/y position). Additionally it must have at least one additioanl `xy` point (exactly one in our triangular case). The `pquad` also contains `sintheta` and `costheta` (set in `check_scale`).

```
    double dx, dy;
    dx = field_getx(s, pq->fieldB) - field_getx(s, pq->fieldA);
    dy = field_gety(s, pq->fieldB) - field_gety(s, pq->fieldA);
    pq->scale = dx*dx + dy*dy;
    pq->costheta = (dy + dx) / pq->scale;
    pq->sintheta = (dy - dx) / pq->scale;

```

As we see both code parts translate and scale the vector AC in relation to the line AB.

I hope this info is useful to somebody, even if it got a bit long!

> **Comments:**
> **username_0**: Wow, it's great when a new user jumps right in and nicely tackles an old and challenging question! Thank you for digging into this.  

---

### Answer by username_6 on 2019-10-03. Score: 10

Finding an astrometric solution from an image with Astrometry.net is usually called plate solving. As mentioned in the comments, it is based on pattern matching, using a large set of databases that are pre-computed for various field of view and plate (or pixel) scale. The ArXiv paper [Astrometry.net: Blind astrometric calibration of arbitrary astronomical images](https://arxiv.org/abs/0910.2233) provides some details of how it works. From their abstract ...

> After robust source detection is performed in the input image, asterisms (sets of four or five stars) are geometrically hashed and compared to pre-indexed hashes to generate hypotheses about the astrometric calibration. A hypothesis is only accepted as true if it passes a Bayesian decision theory test against a null hypothesis.

The blind solution described in the paper is obtained directly from a photo without any additional input, but even a rough guess for the field of view can provide considerable speedup by narrowing the number of databases to be searched. Additional speedup is possible if the scale (arcsec/pixel), FOV and approximate coordinates in the sky are provided.

Astrometry.net code and databases can also be downloaded and run locally on unix/linux computers, and on Windows using Cygwin. There are several other plate solvers available, often included with, or designed to interface with, software that controls a telescope, mount, camera, etc. for astrophotography.

**Edit:** Some additional info related to the comments.

In finding a solution, they must deal with imperfections of real images, including defects, optical and atmospheric distortion, etc. along with small positional changes of stars. Roughly speaking, they obtain a solution by using a best fit to several asterisms, each containing a small number of stars.

> Noise in the image and distortion caused by the atmosphere and telescope optics lead to noise in the measured positions of stars in the image. In general this noise causes the stars in a quad to move slightly with respect to each other, which yields small changes in the hash code (i.e., position in code space) of the quad. Therefore, we must always match the image hash code with a neighborhood of hash codes in the index.

Also, they are able to ignore defects and moving objects like planets, asteroids, etc. in finding matches.

> However, we also know that some fraction of the stars in the query image will have no counterpart in the index, due to occlusions or artifacts in the images, errors in star detection or localization, differences in the spectral bandpass, or because the query image "star" is actually a planet, satellite, comet, or some other non-star, non-galaxy object. True stars can be lost, and false stars can be added. Our foreground model is therefore a mixture of a uniform probability that a star will be found anywhere in the image--a query star that has no counterpart in the index--plus a blob of probability around each star in the index, where the size of the blob is determined by the combined positional variances of the index and query stars.

Their goal was not to achieve high astrometric precision.

> There are several automated calibration systems that refine the astrometric calibration of an image to produce a high-precision alignment to a reference catalog given a good first guess (for example, Valdes et al. 1995; Mink 2006; Bertin 2005). These systems are reliable and robust, but they require a reasonable first guess about the image pointing, orientation, and scale. Our system can be used to create that good first guess.

> **Comments:**
> **username_0**: @MagicOctopusUrn the point is to have software that works with any image, 100 year old plates with obscure serial numbers, erroneous exposures, etc. The second line in the abstract says **The system requires no first guess, and works with the information in the image pixels alone; that is, the problem is a generalization of the "lost in space" problem in which nothing--not even the image scale--is known.** It's not for cell phone photos, this is just an "edge case"!  
> **username_0**: @username_6 Thank you for your extremely helpful answer! The ArXiv paper is excellent, and poking around further I found a Github site: https://github.com/dstndstn/astrometry.net  
> **username_7**: Fascinating. One of those "why didn't I think of that" applications. Asterisms is a known concept for human skywatching, https://en.wikipedia.org/wiki/Asterism_(astronomy), and (relative) star positions from anywhere (and any time) on Earth barely ever change. So, use a reduced version (limit to 4- or 5-star groups) and hash all combinations.  
> **username_8**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/99554/discussion-on-answer-by-username_6-how-the-heck-does-astrometry-net-work).  

---

