Computers counting craters
By Anthony Milbourne (Birkbeck College)
In this blog I would like to talk about automated crater counting, which as the name suggests, is the use of computers to identify and count craters. Computers are very good (and getting better) at many things, but they are still not as good as humans at many important classes of problems. The human brain is amazingly powerful (you knew that) and the latest generation of super-computers have only just reached the same order of magnitude of computing power. In other words, there are currently only a handful of machines in the world that can truly rival the human brain in terms of raw processing-power. Humans are particularly good at pattern recognition and computer scientists have been trying to create computer programs to do this for a long time, but the results generally look rather pathetic compared to humans. One application of pattern recognition is crater identification, which I will talk about below.
In general there are two approaches to pattern recognition: designed algorithms and machine learning.
A designed algorithm is a set of very specific instructions that allow the computer to solve a specific problem. It would be like programming a car to drive from point A to point B by defining exactly how much to accelerate or brake at what points and exactly how much to turn the wheel when. If you know the car will always be running on the same road then this approach is reliable and predictable, but it’s not very flexible. If a pedestrian steps into the road they are in trouble because the car will take no account of the changed environment, and if the car has to go on a different road it will be close to useless.
In machine learning the computer is still given detailed instructions, not on how to solve a specific task, but on how to learn what works well to solve the task. This would be like giving the car-driving program instructions on what the brake, accelerator and steering wheel did and then letting it experiment until it found a route from A to B. Obviously, this requires a training phase, where the algorithm crashes a lot (let’s hope the car wasn’t expensive), but eventually it figures out some general principles about driving and is able to deal with a certain amount of change in its environment.
Designed algorithms are safe and predictable; they don’t need training and are often easier to implement and faster to run, but they are inflexible. Machine learning may be better at the job and will certainly be more flexible, but it is tricky to train and you may end up training it to take short-cuts that you didn’t want: http://neil.fraser.name/writing/tank/
An example of a commonly used designed algorithm is the Circular Hough (pronounced like rough) Transform (CHT). We assume that the image is taken from above and that the vast majority of craters will be roughly circular. The program then uses a CHT to look for circular patterns of a set radius (perhaps repeating many times for different radii). A CHT essentially takes each image pixel that represents an edge and uses it to generate a vote for all possible circles that the edge could be on. The centres of all these possible image circles form a circle of votes around the edge point. If you do this for every edge point then the votes tend to build up at points that really are the centres of circles (it’s easier to see in the diagram).
Of course, this is much harder in practice as the images have a lot of noise and other features that generally confuse the algorithm, so various people have come up with various ways of improving it and making it faster. There are of course many other types of designed algorithm, but I won’t bore you with all of them.
An example of a machine learning approach is to use a neural network. This is a program that tries to simulate a simplified model of how the brain works. It consists of a large number of ‘nodes’ which are connected to each other by links of varying strength. The nodes are normally arranged in layers, and each node combines the inputs from nodes in the preceding layer and sends the result out to the nodes in the next layer. The nodes in the first layer act as input points and the nodes in the last layer as the output. The strength of the links can be varied in order to change the behaviour of the network, and this is done during training when the error from each training run is used to adjust the link strengths.
Neural networks are deceptively simple in concept but are very powerful and can end up spotting trends that are not clear to humans, or that are too complex or nuanced to implement easily as a designed algorithm. However the number of nodes needed to achieve anything useful is normally large, so figuring out what is actually happening inside the network is not practical. For this reason you can never be quite sure that the network, given new or unexpected data, won’t do something crazy!
Again, this is not the only way of implementing machine learning, but it gives an idea of the way this sort of system works – trained rather than designed.
In general, machine learning approaches take more processing power than designed algorithms, so in most cases a pipeline is used. First, a quicker, more predictable, designed algorithm is used to select areas of interest (potential craters), and then a machine learning approach is used to sort the real craters from the noise.
The images at left are an example of the kind of output that can be achieved by automated crater recognition (this one is based on Hough Transforms), and the problems with it. This is far from the best algorithm available, and other researchers have developed much more accurate programs, but they all suffer to a greater or lesser degree from image noise. The first image shows how accurate an algorithm can be in a clear image with little noise. It misses many smaller craters and there are a few false positives (which are somewhat surprising to a human eye), but in general it finds the rims of the most obvious craters very accurately. The second image features degraded crater rims, a lumpy surface and sub-optimal illumination. The result is that the same algorithm does very badly at spotting craters. This is not surprising; even a human would have to look harder at the second image, but the algorithm performs so badly that it is arguably not worth using, and this is the sort of image where humans really are the only (reliable) show in town at the moment.You might think that automated crater counting would be a direct competitor to crowd sourcing efforts like Moon Zoo, and in some cases you would be correct, but it can also be used as a complementary technique. This could be done by using moon Zoo crater identifications as the areas of interest and then running an algorithm to find the exact location of the crater rim, or using an algorithm to spot Moon Zoo data which has been entered by mistake, or by users who didn’t understand the task.
Most interestingly, in my view, is the idea that algorithms are just another type of user. Some algorithms are not great at spotting craters, but some human users are a bit variable too. Admittedly, the best humans are far better than the best algorithms, but the best algorithms are probably better than the worst humans, so they fall within the quality spectrum that Moon Zoo (and the rest of the Zooniverse) already deals with. They probably won’t be much good at spotting unusual objects and they certainly won’t be much fun on the forums, but perhaps we might one day be working with algorithms as our (less able) peers.
By Anthony Milbourne (Birkbeck College)
Apollo Basin is a large (538km), double-ringed impact crater on the far side, at Latitude: -36 and Longitude: -152. The feature was named in honour of the Apollo program and many individual craters within the Apollo Basin are named after the astronauts lost on the Space Shuttles Challenger and Columbia.
The Apollo crater is superimposed on the huge South Pole-Aitken basin, one of the largest impact structures in the solar system and more than 8km deep. The impact that created the Apollo Basin may have exposed a portion of the Moon’s lower crust (see the Lunar Networks link below for more information).
This crater was selected as one of the fifty sites for LRO to investigate for future exploration of the Moon as it contains rare farside mare deposits in close association with the bright highlands materials found on the basin’s inner ring of mountains.
Image from ACT-REACT, centred at Latitude: -31.558 Longitude: -141.174, showing craters named after astronauts.
Image mosaic from USGS Map-A-Planet
The images in the last two links below are well worth a look!
Challenger Astronauts Memorialized on the Moon
Messier: The Coffee Bean Crater
One of the must see telescopic sights on the Moon is the pair of young craters Messier and Messier A. They are located in Mare Fecunditatis and are thought to have formed from the same single low angled impactor moving right to left. The main impact created Messier and a secondary impact (either a bounce of the main impactor or separate chunk of it) created Messier A and the rays. A second (and more overhead) impact in Messier A made it a double crater. Messier crater is 1.3 km deep, 11 km long and 8 km wide. Messier A is 11 km long and 13 km wide. The elongated shape of the craters is characteristic of a low angled impact.
Being very small they are challenging to spot in a small telescope. You are more likely to see the two prominent white rays first extending over 100 kilometers westwards from the rim of Messier A. The rays give the craters an unusual appearance often referred to as comet tails or headlights. Up close, however, the lunar Messiers take on a more dramatic appearance. New forum member JasonJason noticed Messier’s striking resemblance to a coffee bean:
Messier A (left) and Messier craters
Spot the bean…
Zoom in and examine the bouldery floor responsible for the “groove” in the bean.
ACT_REACT Quick Map
NACs M104204818LC M104204818RE
Messiers in 3D via APOD.
Different views of the Messier craters on SEDS. (Students for the Exploration and Development of Space.)
Messier A has some amazing layering on its walls as described in this NASA Article.
And in a Moon Zoo version of the Messier Marathon why not spend some time trying to spot them yourself? You will need a telescope rather then binoculars, however, a 5 day or older Moon and a clear sky. This is the view you will get through a small (90mm) telescope with a 20mm eyepiece.
Nice find JasonJason!
Meteorites on Ice
Although not exactly Moon focused, I hope that this story is of interest to Moon Zoo Forum members as this is the way many lunar meteorites are found here on Earth (see previous Moon Zoo blog ).This past winter (2011-2012) I was lucky enough to join the Antarctic Search for Meteorites (ANSMET) team to hunt for meteorites in Antarctica. The ANSMET programme, funded by NASA and the US National Science Foundation and run between Case Western Reserve University, NASA JSC and the Smithsonian, has been running since 1976 exploring the ice of Antarctica for meteorites. So far about 20,000 meteorites have been collected and made available to the scientific community to study to understand planetary processes. Most of these meteorites originate from the asteroid belt, but some very rare ones have come from Mars and the Moon.Why Antarctica? The team collects meteorites in Antarctica because they are well preserved in the cold dry icy environment. They are also easy to spot as dark rocks on the white ice. Most meteorites are found in icefields close to the Transantarctic Mountain range – you can see a map where all the yellow labels mark places that meteorites have been collected. These localities are really great for concentrating lots meteorites that have travelled from the South Pole ice plateau, and are brought up to the ice sheet surface near mountain ranges
How do we get to Antarctica and what is life like on the ice? Our team of six guys and two girls flew to Christchurch, New Zealand, and then were flown down to the US McMurdo base in Antarctica. We spent a week or so in McMurdo preparing for our expedition. We packed up our gear and selected food supplies to last us for six weeks camping on the ice. When we were trained and prepared we flewout to the Transantarctic Mountains on a military Hercules plane with skis and then a smaller Twin Otter plane. We set up camp in the Miller Range – a stunning area with mountains and glaciers. Our camp consisted of four tents, where we lived two people to a tent, and a tent with a toilet (a glamorous bucket!) and one that we used to all gather in the evenings (the party tent). Temperatures varied from about -10°C down to -30°C outside, but when the wind was blowing from the South Pole plateau, it felt a lot colder! You have to wrap up in many layers to stay warm – I typically wore four layers on my legs and between five and seven on top, including my big orange down jacket. I also wore a full face mask to protect my face and eyes from the cold and glare from the sun.
How does meteorite hunting work? We had a surprisingly large amount of snow during our field season – which is rather unusual for Antarctica as it is supposed to be a cold dry desert. The snow caused us lots of problems trying to find the meteorites, so we spent a lot of time stuck in our tents rather than looking for meteorites. When the weather was good enough to allow us to look we would get on our snowmobiles (skidoos) and drive out to a new area of ice. We lined up and drove up and down in straight line formation with about ten metres between each team member. When someone spotted a black rock on the ice they would jump off their skidoo, check it was a meteorite, and then wave their arms madly in the air to call the other people over to come and help collect it. We photographed the meteorite, logged its location and carefully put it into a special collection bag ready to send back to NASA. Sometimes we would walk across the ice to search, and other times we would look in rocky areas called moraines to see if we could spot a meteorite. It was a frustrating process when you didn’t find a meteorite, but great fun and satisfying when you did. Our team found 302 stones this year, which considering the bad weather, wasn’t a bad total at all. In fact we were lucky enough to collect the 20,000th sample ANSMET have collected, which was cause for a big celebration.
The samples are all now back at NASA Johnson Space Center ready to be classified and studied by scientists all over the world. Initial identification of the meteorites was recently announced at http://curator.jsc.nasa.gov/antmet/amn/amn.cfm#352 and the meteorites our team collected have been given the name Miller Range 11XXX as they were collected in the 2011 ANSMET season. So far (the curation staff are still working hard to classify all the samples!) it doesn’t look like we found any lunars or martian meteorites this year, but did find a large Howardite and several Diogenite meteorites, which may have originated from the asteroid Vesta.
ANSMET will be taking place this year, the team sets off to the ice at the beginning of December 2012, and you can follow the blog charting the expedition via http://geology.cwru.edu/~ansmet/
More information about the ANSMET programme can be found at http://curator.jsc.nasa.gov/antmet/program.cfm and http://geology.cwru.edu/~ansmet/
This is modified from a blog that first appeared on http://earthandsolarsystem.wordpress.com/2012/07/30/meteorites-on-ice/