Linear Algebra math due 6 hours
amjad55
CTScan.pdf
MATH 220 - CT Scan Project (in class)
Directions This project is due Thursday April 26 at the beginning of class. There are two parts to this project - the first is an introduction to computed tomography scan, or CT scan, and works through a sample project while explaining how CT scan images are produced. If there is time, this will be worked through in class. The second part is an individual project, in which you are given the output of a two-dimensional CT scan and you are to determine what the picture is.
For this project, we do not ask that you summarize the statement of each problem, nor do we want you to turn in this paper. Please turn in one sheet of paper with the answers to each question clearly written. Answer each question using complete sentences. Answers that simply indicate a single number, a single equation, etc, will be given no credit. Although you may work in groups or even as a class, your responses should be in your own words. Any indication of plagiarism, such as duplicate sentences, will be treated as a violation of academic integrity, resulting in a zero on this project and the dishonesty reported to the Office of Academic Integrity. This project will be worth 3% of your course grade. Technology allowed. The data is given in a file that assumes you are using MatLab.
CT Scan Project
The radiation x-ray was discovered by a German physicist, Wilhelm Roentgen, who did not know what it was, so he simply called it “X-radiation”. A single x-ray passing through a body is absorbed at rates depending upon the material it goes through. Thus if an x-ray is passed through bone, a certain amount of intensity units is absorbed, while if it passes through soft material, a different amount of intensity units is absorbed. A CT scan is a scan in which an x-ray is passed through an object (part of a body) from multiple angles (on the order of 360), to produce a detailed, high quality two-dimensional image. How does it work?
Consider Figure 1, consisting of a toy two-dimensional figure consisting of 16 pixels. Each pixel can absorb 1 intensity unit (i.u.) from the X-ray beams, or none. Let’s assume the white boxes are bone and absorb 1 i.u., and the black pixels absorb no i.u.’s and represent e.g. soft tissue. Let µ1 be the attenuation coefficient of element 1 (denoted by a 1 with a circle around it), µ2 be the attenuation coefficient of element 2, ... µ16 be the attenuation coefficient of element 16. Ideally, each µ is either 0 or 1, indicating soft tissue or bone, respectively. A beam from the x-ray can be sent through the material at any location and from any direction, but must start on the outside of the material, and then the amount absorbed is measured where the x-ray exits. The goal is to use x-ray data to reconstruct this figure and determine the vector µ in IR16.
We have 16 pixels so in order to determine the attenuation coefficient of each pixel we need at least 16 equations. Let’s assume we have 16 X-ray measurements, denoted by arrows 1 through 16. Arrow 1 (first column down) would have 1 i.u. absorbed for each white pixel, so the number of i.u.’s coming out would be 4 (one for each white square). Of course a real X-ray would not be this simple, but this gives us an idea of how it works. So the first equation says that if we pass an X-ray through the first column, it goes through pixels 1, 5, 9, and 13, and the number of i.u.’s absorbed is 4. Our first equation is thus:
µ1 + µ5 + µ9 + µ13 = 4.
16
1 2 3 4
5
8
7
6
9
10
11
12
13 14 1516 17 18 19
20
21
22
1 3 4
5 7 8
9 10 12
13 14 15
Figure 1: sample system
Likewise for column 2 we would get the equation:
µ2 + µ6 + µ10 + µ14 = 2.
To solve for 16 unknowns we will need (at least) 16 equations. We have 8 row and column mea- surements so let’s also use the diagonal measurements 9-16. Diagonal measurements 9 and 10 give the equations
µ13 = 1
µ9 + µ14 = 2,
respectively. We thus have 16 equations and 16 unknowns giving the following augmented matrix
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 4 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 2 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 3 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 4 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 4 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 2 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 3 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 2 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 2 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
.
1. Use the data in the file CTScan-Data.docx 1a for the matrix A above and right-hand side, b. (Note the prime at the end of the b vector - Look at the Matlab commands at the end of the worksheet to see why it is important to include the prime). Solve the system (sample Matlab commands are given at the end of this worksheet).
(a) What does Matlab say when you try to solve the system?
(b) Calculate the determinant and rank of A and write your answers.
(c) We could try to eliminate an equation and adding an equation until we got an invertible matrix, but this is a lot of work. Instead we will try just adding equations. Write the 17th equation using the 17th diagonal sum from Figure 1. Augment your matrix and right-hand side in your Matlab code.
(d) We cannot calculate the determinant and rank of this matrix, why?
(e) Calculate the RREF of your modified A and write down how many pivots you have.
(f) Continue adding equations until your RREF has 16 pivots (which is equal to the number of unknowns). Write down the additional equations you used. How many total equations did you need?
(g) Now solve the equation using least squares:
ATAµ = ATb
Solving it, you should get the exact solution. Write down your values for µ1, µ4, µ6 and µ16. Is this consistent with Figure 1? Explain.
2. So this seems easy - what is the catch? The problem with real life, is that experiments are never exact. So the right-hand side vector b given above may have errors due to measurement. Use the sample data in CTScan-Data.docx file, 2a for b. Note that the right-hand side is close to the right-hand side used in problem 1, but with up to 10% error. Solve using least squares.
(a) Write down the values for µ1, µ6, µ11, and µ16.
(b) Looking at the value for µ16 it is not absolutely clear whether this should be interpreted as bone or soft tissue. So let us try using all of the equations! Use the data given in CTScan-Data.docx file, 2b. How many equations and how many unknowns to we have?
(c) Solve the system using least squares. Write down the values for µ1, µ6, µ11, and µ16.
(d) Compare with the values given using only 18 equations. Is it better to use more equa- tions?
3. Now it is time to do this on your own individual data. In this case we have 18 pixels, see Figure 2. The matrix associated with this system, consisting of 25 equations and 18 unknowns is provided in CTScan-Data.docx file, Problem 3. As with the sample problem, the “true” solution is that each pixel is either white (µ = 1) or black (µ = 0). Your individual output from the CT scan is provided in a separate file mailed to you. What is the result of your individual CT scan? The design is in black (µ = 0). It could be a capital letter, a number, a math symbol, or another design. The designs are oriented so that either elements 13-18 are on the bottom, or so that elements 1, 7, and 13 are at the bottom. Write down the elements that you believe are black and explain what it is.
24
1 2 3
3 4 5 621
4 5 6
7
8
9
7 8 9 10 11 12
181716151413
10
12
11
13 14 15
16 1718 19 20 21 22 23
25
Figure 2: System for Individual Part of Project
Possibly Helpful Matlab Commands
rank(A) Gives the rank of the square matrix A
A’ Gives the transpose of the matrix A, AT
A*b Multiplies matrix A and matrix b, Ab
det(A) Gives the determinant of A, det(A)
x=A\b Solves Ax = b using row reduction and stores the answer, x, into the vector x.
