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.