CEG221: Advanced C Programming for Engineers

 

Final Project: SAM (Spectral Angle Mapper) Change Detection

 

Background:

In the world of spectral processing (as well as other conditions), it is frequently necessary to compare two color images of the same color depth (RGB) to determine how similar they are. There is an algorithm called SAM – Spectral Angle Mapper – that can be used to perform basic change detection between these two images. Change detection is almost like the <, >, and == operators but for images. For I1, I2 that are images, SAM(I1, I2) produces a third image, IΔ whose first pixel is the SAM value of the first pixels of I1 and I2, and its second pixel is the SAM value of I1, I2, and so on.

 

It is important to note that, although the math below is for N-dimensional images (N bands); we will be working with 24-bit color RGB images (ie. a JPEG) which has 3 bands, where Band 1 = RED, Band 2 = GREEN, Band 3 = BLUE.

 

In order to compute the SAM Algorithm, we must review a little bit of linear algebra. Recall that, given an N-dimensional vector A = <a1, a2, a3, …, an> and another N-dimensional vector B = <b1, b2, b3, …, bn>, the dot product A ∙ B (read “A dot B”) = a1b1 + a2b2, + a3b3 + … + anbn. We can also compute the length of A, written │A│ can be computed by the equation │A│2 = A ∙ A.

 

The angle between two vectors in N-dimensional space uses these two operations in the following relation: cos θ = (A ∙ B) / (│A│ │B│). Theta is called the SAM Angle or the SAM Value.

 

Image Format:

The image that you will be reading in will have fixed width, height, and color depth, so it need not be stored in the file. I will give you that information. The image will be in BIP format – Band Interleave by Pixel – which means that the image is stored in the following format:

 

RGBARGBARGBA…

RGBA is pixel 1, RGBA is pixel 2, RGBA is pixel 3, etc…

 

The SAM Algorithm:

The SAM Algorithm was developed as a way of comparing two spectra (plural of spectrum) using linear algebra by computing the “angle” between them. If we treat each spectrum as an n-dimensional vector in n-dimensional space, we can compute the angle. The smaller this number is the greater probability that these two spectra match each other.

 

Let’s try SCD on two 3 x 3 RGBA images:

255, 100, 90

100, 100, 0

210, 210, 10

 

255, 50, 50

50, 50, 0

100, 0, 100

207, 14, 22

200, 15, 100

17, 17, 200

101, 11, 101

102, 51, 100

28, 28, 200

91, 28, 22

201, 21, 102

71, 17, 66

12, 51, 102

102, 21, 0

77, 22, 32

(X, Y, Z) è (R, G, B)

(X, Y, Z) è (R, G, B)

Image A

Image B

 

The pixel (0, 0) in Image A = <255, 100, 90> and in Image B = <255, 50, 50>, and the similarity between pixel (0, 0) in both of them = acos[ (255 * 255 + 100 * 50 + 90 * 50) /  (│<255, 100, 90>│ │<255, 50, 50>│)] =  acos( 74525 / sqrt(83125 * 70025) ) = acos( 0.9768 ) ≈ 0.2158 degrees. So we’d put 0.2158 as the value in the result matrix at position (0, 0).

 

Continuing to do this for all the pixels in Image A and Image B, we will get a new image, we’ll call the SAM Image. We can then use this to determine how similar the contents of each pixel are in terms of a percent. So the above computation reflects that pixel (0, 0) is a 97.68% match with 0.2158 degrees between them. Let’s try the next one, (0, 1):

 

Let’s compute the SAM value for pixel (1, 1). (1, 1) in Image A = <100, 100, 0> and in Image B = <50, 50, 0>. θ = acos ( 10000 / sqrt(20000 * 5000) ) ≈ acos( 1 ) ≈ 0. Thus, they are a 100% match and there is no angle between the two vectors – but that is because they are a linear combination of each other. Pixel (1, 1) of Image A is Pixel (1, 1) of Image B, scaled by a factor of 2.

 

We would keep computing the values until we get a new image of the SAM values.

 

Why This Assignment?

One of the things we always ask when given a project is why? What purpose/value does this have? In any industry, you will want to verify that your results are good – and that each successive improvement doesn’t mess up a previous implementation. What happens, however, if your output is not a numerical value or a string – but an image? You need to compare them. Sure, you can dump the memory to disk and then run diff[1] on the truth file and the output file. But what if you want to know more than just whether they are “similar” or “different?” How the two are different can aid in debugging the application.

 

What You Need

1)      Microsoft VisualStudio 6.0 or Microsoft Visual C++ 6.0

2)      Sample 521 rows x 781 columns x RGB Image Files - truth.raw, output.raw

3)      Raw Image Reader Library to read the image files into memory

 

Your Task

1)      Implement a library that performs the dot product of two dynamically allocated arrays

a.       The two arrays must be of the same size

b.      The two arrays must be of the same type (both unsigned int, etc.)

c.       This function need not take two void pointers (see (3)) as the array

d.      If successful, the function must allocate memory with malloc and return the completed array

e.       If the function fails for any reason, the function must free any malloc’ed memory and return NULL

2)      Implement a library that uses (1) to

a.       malloc memory for a result matrix that is of size rows x columns (which for the sample is 521 x 781)

b.      Performs SAM on all corresponding pixels of Image A and Image B

c.       Returns the result matrix, if successful

d.      REMEMBER: Should function fails for any reason, you must free any malloc’ed memory to prevent memory leaks and return NULL

e.       HINT: Use an indexing function that returns a pointer to the address you want to read from/write to since we’re using a 1-Dimensional array to simulate a 2-Dimensional array (an image)

3)      Implement an executable that links with (2) and performs SAM Change Detection on the two images provided

4)      Extra Credit – This would be easier in C++, but doing so in C will test your knowledge of the language and of advanced programming

a.       Implement SAM Change Detection that will work on all of the following data types: (un)signed char, (un)signed short, (un)signed int, float, double

b.      Requires all pointers to be void* and typecast to the proper type

c.       A HINT TO ACCOMPLISH THIS: You will need extensive switch statements and an enumerated type to determine the type of the data and pass it in to every function; this will also yield its size, as an unsigned int is 4 bytes and can be yielded by performing sizeof(unsigned int).

 

Program Requirements:

1)      Your program must comply with the class programming standard

2)      You must submit a hand-written program specification

3)      You must submit a hard copy of source code, as well as a soft copy on disk on the due date

 

Grading Standard: This project will be worth 250 points.

Design Document (50 points)

·        Outline of data types, data structures for each library/program (10 points)

·        Outline of the overall application (10 points)

·        Pseudo code for the algorithm, the indexing function, and the dot product function (10 points each)

Dot Product Library (60 points)

·        Is designed using information hiding: interface in the header file, implementation in the source file (10 points)

·        Is appropriately modularized (10 points)

·        Correctly performs the dot product of two n-dimensional arrays (15 points)

·        Correctly handles errors and returns appropriate values when an error is encountered (10 points)

·        No memory leaks (10 points)

·        Proper documentation of code (5 points)

SAM (100 points)

·        Is designed using information hiding: interface in the header file, implementation in the source file (10 points)

·        Is appropriately modularized (10 points)

·        Correctly performs the SAM angle between two images and stores it in a results matrix (20 points)

·        Correctly handles errors (10 points)

·        Displays appropriate error messages (5 points)

·        Returns appropriate values when an error is encountered (10 points)

·        No memory leaks (15 points)

·        Proper documentation of code (5 points)

Miscellaneous (40 points)

·        Style Issues / Following the Class Coding Standard (20 points)

·        Overall Correctness (20 points)

 

A Note on Grading: If your program does not compile or link, you will receive no credit for any programming-related parts of the project. However, you will receive credit for things such as documentation of code, correct style, etc. Also, it is incredibly important that you collaborate with your peers to learn from each other; remember that sharing ideas is permitted, but not code. Anyone found sharing code (this includes comments) will receive NO CREDIT for the assignment and may receive judicial action.

 

Due Date:

This project will be due on ??/?? at the start of class.


[1] diff is a UNIX file utility that compares two files, binary or text, and displays whether their contents are the same. In the case of text files, it displays the lines that are different and how; for binary files, it just displays “contents are the same” or “contents are different.” Since images are binary files and in our case, we want to know how the files are different, not just that they are different, diff would not be nearly as helpful.