The Take-Away with Jacob Moul

May 1, 2016

Over the past couple of weeks I have concluded all of my testing and am left with a fair amount of data. 

What Does It All Mean??

Running all the algorithm combinations resulted in lots of control networks (files that contain all the match points between the two images). After looking through all these networks, I have determined that one feature detector algorithm finds a lot of points (in the 5000s), and the other two detectors both find significantly less (in the 200s). In addition, each detector-extractor algorithm resulted in distinct clusters in different areas on the Moon's surface. I will have to do more analysis to see if the effectiveness of each combination was due to the level of each match condition (geometry, lighting, overlap), but at the moment, there is no clear pattern.

What these results tell us is that more work needs to be done, both in developing the code and in testing the code to determine the problems. My advisor told me something the other day that I did not realize: all of the algorithms we've been using have been developed for use on images of the Earth's surface, and have just been used on extraterrestrial images out of convenience. Due to the sometimes extreme difference between terrestrial and extraterrestrial surfaces, the algorithms will occasionally fail.

Fortunately, my project has been able to identify some of the issues that these algorithms run into (i.e. clustering and small numbers of match points). The purpose of my project was to help the USGS improve their image matching software. Because there was no concrete goal involved in that purpose, I would consider my project to be moderately successful. Even though I don't have the technical knowledge to address the problems myself, just identifying them provides a sort of roadmap for developers at the USGS to follow.

What Did I Learn?

Computers are frustrating. Debugging took up a good third of my project time, and that was a pain in the butt. Especially because I only have a basic understanding of programming so it was extremely difficult to identify and fix the problems. Luckily, my advisor did most of the heavy lifting in this respect...

I also learned that space is super cool. I already knew this to a certain extent, but staring at pictures of the Moon all day really sparked my interest in space. During my project I started reading a book about cosmology (the study of the universe) and dark matter and things like that and I think it's extremely interesting. Right now I'm declared as mechanical engineering major, but who knows, maybe I'll end up studying astrophysics instead. OR maybe I'll double major. We'll see what happens.

In all seriousness though, the very basic programming skills I learned during the course of my project will provide a good base to build off of in the future. I got a lot out of my project and I think it definitely has shaped the academic path I want to pursue in college.

To all who read my blog, thank you for keeping up with my project and for being interested!

Jacob Moul

Week 10: Holy Guacamole!

April 15, 2016

Catching Up From Last Week

After my last post, I started choosing manual match points and comparing them to automated match points. It turns out that this task is perhaps the most tedious task known to mankind. I'll spare you all the boring details, but the bottom line is that in the image pairs that actually gave us matches, the computer consistently performed as well as (or better than) a human (me). Here are some animations showing the shifts that occur between images for a few match points.

Computer

Computer

Me

Me

Sometimes the computer performed worse than I did, but that's alright. The "breathing" that you see is due to geometry changes from different camera angles and things like that.

This Week! (holy guacamole)

I am excited! Remember back in Week 3 when I said we got to put it all together? I 100% lied. This week we really put it all together. Let me explain.

The first half of my project (the part that was completed before capstones ended) was all about learning how to program. And I did that decently well. I learned the basics of the Python programming language and learned some cool things about file manipulation and the like.

The second half of my project has been all about helping out the USGS, and I have also done that to a certain degree. I learned how to use some of their software in order to analyze the effectiveness of some of their image matching algorithms while learning some cool and useful skills along the way.

Now when I say we put it all together, I mean we put both halves of my project together. Last week I talked about the problems we were having with the code especially when it came to communicating between my Mac and the Linux that is on my Mac. We remedied those problems by abandoning the Mac side altogether and doing everything on the Linux side.

See, before, we were matching images on the Mac side and sending the control networks that were generated to the Linux side through some computer black magic. When I say control network, all that is is a file that contains all the matched points and where they exist on each image, more or less. Anyway, since moving over to the Linux side, it has been much easier to manipulate the algorithms ourselves, and we have discovered there are about 32 total combinations of algorithms between feature detectors, matchers, and feature extractors (for each image pair), sort of like the combination problems where Jenny has to choose between 5 blouses, 3 skirts, and 2 pairs of shoes.

Here's the cool part: (wait for it.........) because there are wayyyy too many combinations to test by hand in a truly organized manner, my advisor helped me WRITE A SCRIPT that RUNS ALL OF THE POSSIBLE ALGORIthm combinations sequentially! Isn't that amazing??????????? I think it's flippin' sweet! If you couldn't tell, I'm pretty excited. Running all of the combinations will definitely take a while, perhaps up to a week or longer, because it can take 30 minutes or more to run a particular combination. It may take even longer because we keep running into issues with the script we wrote so we'll see what happens!

So that is what's going on now and will be what I talk about in more detail in my final presentation/paper. With that said, the next time you'll hear from/see me is the day of my final presentation (May 2), so adiós amigos!

Week 9: Aaaaaaand We're Back!

April 9, 2016

My advisor is back! That means that my project is back to business as usual. Unfortunately, business as usual means a lot of debugging. As my advisor says, that's the problem with being on the "bleeding edge" of technology like this: you're going to run into implementation problems no matter what you do.

The plan for the foreseeable future is the following:

1. Get all the code I'm using up to date with the code that's being written by developers at the USGS.
2. Figure out how to use the Linux programs in tandem with the software that I was using before.
3. Analyze the success of our matches.

Those are the main parts of my project going forward, and step 3 is going to take the most amount of time and will be the most involved. Although, based on the developments that have been made this week (namely bugs), Step 2 might take the longest.

Step 3 will involve many steps. First, I'll perform an image match. After the match has been completed, I'll look closely at the points that were created and do a blink comparison. This means that I'll pick a couple of points, probably one pair that corresponds to each of the images and then flash each image on the screen back and forth with the match point as a reference to see if there is any shift. A shift in this case would be the whole image moving a couple pixels to the right or left, or something similar. If a shift occurs, I'll try to determine how many pixels I'll need to move one of the points, and record what kind of manipulations I had to do.

This process was definitely not what my advisor told me verbatim, but it's close enough to understand the gist of what I'll be doing.

On a side note, I ran into an interesting problem this week where all the programs I was running on my computer taxed it completely and killed it; the memory filled completely and everything just stopped working all together. To fix this I had to get an external drive to store my virtual Linux on because I didn't realize that the Virtual Linux was really its on computer with its own memory and all that stuff (silly me!). So basically I had an entire computer on my computer (computer-ception) and that's super cool! I don't know how that escaped me.

Week 8: Nothing to See Here, Please Disperse

March 31, 2016

Hello! I am sorry to report that absolutely no progress has been made this past week. Fortunately, I am 95% confident that this will be the last lacking week, because my advisor will return soon and everything will pick back up! Fingers crossed for lots of progress.

Week 7: What We Have Here is a Lack of Communication

March 25, 2016

At a Standstill

After my last post, in which little to no progress was made, I am happy to report that little to some progress has been made! The root of all this un-productivity is the fact that my advisor has been out of town for the past two weeks, and I am more or less incapable of doing my project without the advice of my advisor. This is because I am not one with the ways of the computer so I really need help figuring things out. In addition, the programs I using to carry out my tests and tasks are in no way intuitive, so a teacher who knows the programs is necessary.

Some Forward Motion

I mentioned above that some progress has been made. This progress comes in the form of learning how to use the Virtual Linux. Within the Virtual Linux, I have to use the Terminal application that I talked about in Week 1 in order to do many things.

One of the programs I'm using on the Linux is called QView. Don't ask me what the Q stands for... Within this program I can manipulate different pairs of images (if qview displays more than two images, it moves unbearably slowly). Here's an example:

I'm supposed to be able to pick match points between the images by hand using this program, but for now, all I've encountered is frustration. As I said before, it's not exactly intuitive. Until my advisor returns from his travels and is able to rescue me from the land of research project limbo, this will remain the state of my project.

Until next time!

Week 6: Limbo

March 10, 2016

Hola, amigos! Unfortunately, this week was very unproductive so I don't have much to report. The lack of progress is due to some logistical issues.

Like I talked about last week, I began working on the manual selection of match points this week, but I didn't get very far. This is because in order to do manual matching, I have to use a program that was developed by the USGS on Linux computers and still only works on Linux computers. To get around this, I need to use a "virtual machine" which emulates another computer's operating system on my computer.

Using a Scientific Linux on my Mac (How cool!)

The problem is that the good folks at the USGS are working on a way of accessing outside drives through this virtual box, and because they haven't yet come up with a way to do this, I'm sitting here in limbo until they get that all figured out. In addition, my external advisor has been swamped with meetings and deadlines and such all week so we haven't had a lot of opportunities to meet and discuss the project. Fingers crossed that everything is resolved soon!

Week 5: More Tests, New Algorithm

March 3, 2016

Woohoo! More testing! If you've been keeping up with my blog, you'll know that last week my advisor told me that we would be using a new method to find match points that would hopefully be more accurate. This method, which uses the "Fundamental Matrix" should be more accurate and make it easier to find errors. I still don't entirely (or at all) understand how the Fundamental Matrix works (thanks Saxon math...), but that's okay because I just need to understand how to use it in the program.

The Results

Here are some of the results we got when using the Fundamental Matrix method compared to the homography method. As you can see, in a couple different image situations, the fundamental matrix gave more match points. If you look at the corresponding images, you'll notice that in addition to more match points, the fundamental matrix gives a slightly more evenly distributed set of points than the homography.

Image Set	Number of Points
Control - Homography	624
Control - Fundamental Matrix	827
5º Rotation - Homography	482
5º Rotation - Fundamental Matrix	574

Control - Homography

Control - Fundamental Matrix

Rotation - Homography

Rotation - Fundamental Matrix

Based on these results, I think we will begin replacing the homography with the fundamental matrix and epipolar lines.

Looking Ahead

Next week, the plan is for my advisor to teach me how to use the OpenCV software to choose manual match points. Once I get that down, we will be comparing the quality of automated chosen match points to the quality of our manually chosen match points. We'll see how it goes!

Week 4: Time to Test Stuff

February 25, 2016

The Tests

This week I got into the actual nitty-gritty science! I tested the algorithm on different image situations. I ran the algorithm on images with time differences, adjacency differences, rotation differences, and also on 10 images instead of 2. When I say time differences, that just means overlapping images with different shadows. When I say adjacency differences, that means the images overlap from north-to-south instead of east-to-west, because the image pairs I've been using up to this point have all overlapped east-to-west.

The Results

The main data that is of interest from these tests is the number of "good" match points that the algorithm returns. Here is a table of the results:

Image Set	Number of Points
Control	601
Time	63
Rotation (5º)	916
Rotation (45º)	0
North-South #1	68
North-South #2	1
North-South #3	5
North-South #4	0
10 Images	1543

For a more visual representation of these results, here are some images:

Control

Time

5º Rotation

45º Rotation

North-South #1

North-South #2

North-South #3

North-South #4

I didn't include images of the 10 image adjacency because my image outputs only include 2 images. In these pictures, each red dot represents a match point. The matching mechanism used in these examples is called SIFT, or Scale Invariant Feature Transform. In other words, SIFT will match images that differ by size, but not by things like rotation (hence the utter failure of the 45º rotation). If you have questions about why each individual situation performed how it did, I'd be happy to answer in the comments section.

The Problems

Unfortunately, my advisor notified me today that using homographies (see last post) makes tracking errors and bad points messy, so we are going to start using a method of matching features that includes epipolar lines and Essential Matrices. If you're confused, good. I am too. I suppose we'll both find out how Essential Matrices work and how they change our results next week.

The Statistics

Before you start lecturing me about sufficiently large sample sizes, don't worry, I understand that one trial per situation is not up to par in the statistics world. However, if I run the same pair of images through the algorithm more than once, I'll get the same match points every time (trust me I've tried). In addition, the point of these tests was to get a general idea of the strengths and weaknesses of the algorithm in question, not to prove anything in particular. So don't worry, I'll use better statistical methods in the future.

Week 3: I knew we'd get to the pictures eventually.

February 18, 2016

This week we finally got to put it all together!

There are several steps to the image matching process: identifying the features of an image, filtering out the "best" features, repeating the first two steps on the other image(s), performing a match between the two (or more) images, and filtering out the bad match points. I'll walk you through the steps.

Before we start though, let me explain a few of the terms:

• Features: a feature, in general terms, is a piece of information that a computer uses to perform a task. In this case, a feature is a specific point in the image, such as a bright spot, an edge, or the center of a crater, for example.
• ANMS: Adaptive Non-Maximal Suppression is a way of thinning out features so that they are more evenly spaced. This is basically done by finding the radius of empty space around each feature and then picking the n number of spaces with the largest radii. What you're left with is a more uniform distribution of features as you can see from the image below.
• RANSAC: Random Sample Consensus is a rather complicated "outlier detection" method that returns data without any influence from the outliers. I don't understand it well enough to explain it, but if you're interested in learning more you can read this technical Wikipedia article...

First, we extract the image's features, which gives you something like this:

Next, we do the same for the other image:

Then, we perform something called Adaptive Non-Maximal Suppression (ANMS), which cleans up some of the noise. This is done to both images, but here we only see one:

After ANMS, we can match the images:

This is not a good match, because there are many intersecting lines; a good match should ideally have no intersecting lines. In order to remedy this, we apply RANSAC, which is an outlier detector. This gives a final product that looks something like this:

This is a good match because, as you can see, there aren't any intersecting lines. And, if you looked closely, you would be able to see that each line matches identical features in each image.

In order for any of this to work, the images have to be overlapping. Otherwise, you would waste your time extracting a bunch of meaningless features from your images. In addition, the images must have the same reference frame. If one of the images is a perspective image and the other is face-on, there are computations that can be made to translate the perspective image into a face-on reference. This is done through something called a homography, and I think it's super cool. It blows my mind that somebody came up with the math and the equations to do something this complicated. While the math is way beyond me, I think you should definitely read more about it just to see how impressive it is.

This project has exposed me to a lot of complex mathematical concepts, all of which have only furthered my interest in the field of mathematics. While I don't necessarily want to pursue a degree in math, I definitely want to learn more about its nearly infinite applications.

Week 2: This time, people are the problem.

February 11, 2016

Hello again! I'm pleased to announce that I've made some actual progress this week. Since my last post, I have begun to understand the software that I'll be working with. While there are still many things I don't get (mostly because I just haven't learned about them yet), the code as a whole is starting to make sense. My advisor and I have also fixed all the environment and dependency issues that we encountered while running the code on my computer (at least as far as we know).

Now, the problem is with the software itself; as it is currently written, there are a couple of bugs that prevent successful implementation. The bugs are currently being worked out so I should be able to continue with my project sometime in the next few days.

An error message that I've encountered:


This experience has made me acutely aware of the issues that confront the field of computer science: computers and their software are created by people, and people are fallible. As a result, the programs that are written are often imperfect (my project is a perfect example), and this is usually due to a very minuscule error on the part of the programmer. Sometimes it's something as small as an incorrect character, and other times it's larger, like a fault in the logic. Whatever the problem is, a solution can sometimes take a very long time because programs are often composed of hundreds of lines of code, and combing through each line takes a decent amount of time. While working through the coding text book that my advisor supplied me with, I learned some basic methods of debugging, but I suspect that throughout the course of my project I will be learning many more methods.

Of course, when working with code, one will always expect to do some debugging; as my advisor told me, "If everything works on the first try, you've done something wrong."

Week 1: The Joy of Working with Computers

February 5, 2016

Hello! My main task for this week has been becoming familiar with the software that I'll be working with for the rest of my project. Unfortunately, I have been largely unable to do so because of some unforeseen technical difficulties. The main problem has been installing and using the "OpenCV" software, because apparently either my computer doesn't like to do what it's told, or the software encounters some bugs when being installed by new users.

Since I do not have the technical know-how to fix all the software problems, I have been relying on my advisor to remedy these issues. In turn, he has to identify the problems and try to come up with solutions. Needless to say, the process takes a while, so not a whole lot of progress has been made on the actual project front.

On the upside, I have gained some general computer skills. Specifically, I have become more familiar with Terminal, which is an old school computer interface that preceded the type of user interface you and I are familiar with today. It looks like this:

and it used to be the way in which people navigated their computers.
It can be used to install packages, manipulate files, and even wipe the entire hard drive, among other things. I have discovered that it also has some cool built in functions like games (you can imagine the amount of free time I have while waiting for complicated solutions), and I have had to use it to implement some of the solutions my advisor has come up with.

While the technical difficulties are certainly a setback in the progress of my project, it is nothing I cannot overcome with a little bit of overtime. And anyway, I think I've made pretty good use of the unexpected free time.

Why Coding?

January 22, 2016

My name is Jacob Moul and I'm a senior at BASIS Flagstaff. As you can probably tell from the title of my blog, my senior research project has to do with planetary images. 

I chose this project with the primary purpose of learning computer programming. Many college students and recent college graduates I know have extolled the value of being familiar with Computer Science in today's workforce, so I figured I might as well start early. In addition, I find this field extremely interesting for many reasons, including the fact that computer programming allows you to make things from scratch.

Some of you may be asking, "What on Earth is image matching?" I have an answer! Image matching is the process of taking two or more images of the same subject, with each image capturing a different part of the scene, and stitching the images together so that they create one large, coherent image.

"What does coding have to do with it??" I have an answer for that too! Image matching was a manual process at one point, and in some fields images are still matched by hand. However, in the field of planetary data collection, manual matching is not at all feasible due to the mind-blowing amount of data coming in from various satellites and telescopes and what have you. This is where coding comes in: various algorithms have been developed to automatically stitch all of these images together. But like anything developed by humans, these algorithms are not perfect; my project will be attempting to help the US Geological Survey improve their image matching algorithms.

If you're interested in learning more about the USGS Astrogeology Science Center (the location of my internship), just follow this link: USGS Astrogeology Science Center