The Bold Blueprint Podcast
The Bold Blueprint Avideh Zakhor Embrace Your Dreams
Hey Amazon Prime members, why pay more for groceries when you can save big on thousands of items at Amazon Fresh? Shop Prime exclusive deals and save up to 50% on weekly grocery favorites. Plus they've 10% on Amazon brands like our new brand Amazon Saver, 365 by Whole Foods Market, a plenty and more. Come back for new deals rotating every week. Don't miss out on savings. Shop Prime exclusive deals at Amazon Fresh. Select varieties. It is Ryan here and I have a question for you. What do you do when you win? Like are you a fist-pumper? A woohoo! A hand clap or a high-fiver? If you want to hone in on those winning moves, check out Chumba Casino. Choose from hundreds of social casino style games for your chance to redeem serious cash prizes. There are new game releases weekly plus three daily bonuses so don't wait. Start having the most fun ever at Chumba Casino.com. Sponsored by Chumba Casino, no purchase necessary. VGW group, void work prohibited by law, 18 plus terms and conditions apply. This is the third lecture of EV225P. We have had a bit of a rough start as you all know. We started on 1230 to 2 on Wednesday. Then people brought to my attention that the the class was online schedule and all the schedules were reflecting. It was still at 933-11 so to stick to the online schedule we switched to 933-11 but for the second lecture which was on Friday, we couldn't get an operator so finally we resolved all of those and today we're meeting at the correct time with an operator that would videotape the lecture. Just a quick show of hand, how many people were both in the first and second lecture? Okay. How many people missed at least one? Okay. So the lecture notes, the lecture number two was primarily a review of DSP. It wasn't too critical. The lecture notes for it are online. Unfortunately that's the one lecture you can't watch the video because we didn't have the operator. I hope that I've tried everything I could with mass emails and various other things to let everyone know about the time change. It says oh you mean from mute go to on? Okay that's quite possible. Is it on now? Okay. So one other announcements I'd like to make is Cindy's office hours are not Tuesdays and Thursdays from 3.30 to 5. Cindy Lou is the TA for this course and she the room for her office hours are Cory 4.79 right? Okay. Cindy Lou office hours, Tuesday, Thursday, 3.30 to 5, 4.79 Cory and my office hours are immediately after the lecture on Friday. It's Fridays 11 to 12. They're all on the website. Okay. And are there any is there anybody who didn't attend either the Wednesday or the Friday lecture of last week? No. Okay. So we have a kind of a combination of some people must have missed more than the other lecture. I check with ASUC or with the department person who deals with the books just this morning. They claim the delays from the publisher side and not from them and and they think they're going to get it by the end of January. So if if you're anxious I'm there. If I assign any homeworks at this point make sure that chapter one of Jay Lind's book is on the webpage so that you can so that you can read it so you can do the homework. Did you change the the thing to two hours the book on the reserve? Well now we have the Jalen book reserved in the library but there's only one copy and it's reserved for two hours. Okay. So if push comes to shove I'm and the book just doesn't arrive in the next two or three days. One thing I might I might do is there's two solutions. One solution is will scan chapter one of Jay Lind put it on the web so you can do the first you can have the reading material to do the first homework. That's option one option two if you can order ordered from Amazon option three will put it on it is already on reserve so each one of you goes to the library and I would dare to say it takes 15 minutes to copy the first chapter. There's a Xerox machine there at least last time I was there. So you can just copy the first chapter just just so that we can get going with the first homework. I don't want the homeworks to get piled up at the end of the semester. Students always hate that. I hate that you hate it everybody hates it. So just to get the course rolling that's that might that's one thing we might want to do. Has anybody got a copy of this book? I could there's a copyright issue I could go to jail for doing that because I mean you see you certainly don't want your instructor to go to jail. You also don't want your instructor to die either. Those are two bad things because because because just you know if everybody put chapters of books on the web then the authors in fact this will happen. This is my old professor so that's even more reason not to do it but we have taught last year because the book was delayed we did put the first the problems for the first problem set on the web and that's already on the web of spring 2003 but I've never really dared to just get a copy of a whole kind of chapter and put it on the web. But let me see let me just wait one or one or two more days. At this point I haven't covered enough material to even initiate the homework so it's still not a big deal but at the end of today's lecture we'll have enough to do that. So I'll discuss it with Cindy I think I think putting on the web is is your right it's probably what we here's what we might do is we might put it on the web and in fact let's do that okay we'll put it on the web for a very short time let's say just Friday she put it on the web just before the at 9 a.m. can you do that Cindy? 9 a.m. on Friday and we'll knock it out so we don't get caught by what what do you say probably if we do it by 4 p.m. will that give you guys enough windows just go with their print and you're done yeah does that work for everyone yes Cindy okay so I'll give you a copy of my book and let me just make sure that it is chapter one and not two yeah yeah it's wow I was gonna say it's only a few pages it's 64 pages so you'll have a yeah yeah yeah I will arrange between you and I and and the and Rosita how do we do that so I'm not going to write this announcement on the board because there will be yet another evidence of of our on miss doing here but the chapter one will be on the web on Friday from 9 to 4 so please please printed and have a copy of it until the book arrives okay that's all the administrative stuff so let me get started on the on the real lecture today today what we're gonna talk about is a is a homography yeah sure can you use the mic please that's okay yeah just in this the simple 1D convolution case I was going over we were talking about the number of operations that are required to do a convolution if there's like m samples in h and n samples in f can we go over that just one more time I wasn't sure if it was like n squared times m or n times m per convolution I didn't bring last time's lecture with me okay can we do that at the end of the lecture yeah let's do that so the the gist of it I can I have this lecture knows here the gist of it is that if you have separable filter the signal that you receive a two-dimensional image that you receive you don't have much control whether it's separable or not it's a picture of something somebody etc you got a process no matter what it is but the filter is what you can make separable and if you use a separable filter then the number of operation grows as 2 m n squared let me write that down and there was one other one other person who has the same question which means that I was probably not all that clear on it so this is the number of ops if if the filter yeah it's separable and m by m in this case is the size of the filter right and n by n is the size of the image on the other hand if you design your filter not to be separable so if filter is not separable then we get m squared n squared okay so the ratio between this and this is m over 2 so if you're not separable you're m over 2 times more complex to implement than if you are separable so if m for example is 10 then this is 5 times more complex so implement is that what you were asking okay I think in the in the in the heat of trying to arrive at these expressions I might have might have not painted the big picture which is if you design your filters to be separable you gain in computation you lower the computational complexity by a factor that's m squared and when I say ops hey Amazon Prime members why pay more for groceries when you can save big on thousands of items at Amazon fresh shop prime exclusive deals and save up to 50% on weekly grocery favorites plus they've 10% on Amazon brands like our new brand Amazon Saver 365 by Whole Foods Market a plenty and more come back for new deals rotating every week don't miss out on savings shop prime exclusive deals at Amazon Fresh select varieties with the lucky land sluts you can get lucky just about anywhere daily beloved we're gathered here today - has anyone seen the bride and groom? sorry sorry we're here we were getting lucky in the limo when we lost track of time no lucky land casino with cash prizes that add up quicker than a guest registry in that case I pronounce you lucky for free at luckylandsluts.com no purchase necessary BGW grab boy were prohibited by law 18 plus terms and conditions apply I mean marks or ads okay okay any other questions or comments okay so what I'm going to talk today is tomography application so tomography is used in quite a bit in in medicine right when you when you have a CT scan cat scan the principles of tomography are used all the time to detect tumors and various other things they're also used initially when they were designed they were very the systems are very slow because of the computational aspects of it but now you can have a cinematic reconstruction of a meeting heart for example okay you can use x-rays you can use gamma rays or positrons or all kinds of particles to do tomography it's also has applications in acoustic or microwave transmission it is also used in geologic measurements from bore holes so for example oil companies one technique they do is they drill a hole here drill another hole there they put transmitters and receivers and they send a microwave signal that and they they change the height of the transmitter and the receiver at at the two ends I'll draw a picture of it and by sending by sending a signal and receiving it at different heights it's almost like a projection and they can reconstruct the the layers of earth and by looking at the layers of earth they can figure out you know the likelihood of finding oil in this spot or not one of the biggest costs in actually an oil exploration is that of approximately every ten times that they dig a big hole and invest a lot of money only once they actually find oil so being able to come over that then signal processing techniques to increase that probability is a big deal and again over the last 18 years after this course depending upon what era we are in sometimes oil is expensive and and there and sometimes it's dirt cheap and so now we happen to be a period where it's expensive when I just graduated from from MIT looking for a job I interviewed with other oil companies like Chevron and and others and like they exactly would say what we really need is a good big healthy appetite for oil and at that time the price of oil was very low and of course now is very high so the other applications of tomography or electro microscopes you're looking at specimens and you should electrons and what you receive is a projection of the of the specimen you can reconstruct the specimen using tomography techniques radio telescopes and you're looking at the stars projections of interstellar space and and various other systems so let me just show some picture and and define so to the integral part of tomography is really the concept of projection so let me define what a projection is and draw some diagrams so that we can we can get going with the mathematical definitions of it okay so if you can bring the camera down please so tomography is what we're covering today suppose that I have some sort of an object here it's a it's a in general you talk about let me lower this so I can see this half of the class in general thank you you you have a three-dimensional objects and then you have a source let's say an x-ray and then you compute the two-dimensional projection of the three-dimensional object for the purpose of the today's lecture we're going to talk about two-dimensional object think about an object that's that has a two-dimensional two-dimensional function essentially and we take a projection of it let's say we put the x-ray here and we get a one-dimensional projection just so that I can draw it easier on paper but in real life like if you're having a CT of your body it's your body is a three-dimensional thing and the the projections are are in 2d so what so what do I mean by projection so let's say you have an object here and you put an x-ray source right here and you want to take the and let's say the object has has has two bumps so there's like two tumors or something like that one thing is here and another one is here then you can take the projection of this along this direction which is really if you think of it as a two-dimensional function it's really the integral of that function along these paths and it gives me just the one dimensional function that could look something like this and then I move my x-ray source here and then I take another set of projections which is the integral of the two-dimensional objects along that axis and I get another one dimensional function here so by by moving the x-ray source around the object then you can you can obtain projections of the two dimensional objects along different angles so this is projection number one this is projection number two this is projection and so if I put the x-ray source now next here then and the integration is done that way and I can get the third projection which is another function right there okay in real life you don't necessarily want to rotate an x-ray machine but that's so big and complicated around the patient rather you rotate the patient in order to get the different projections so that's that's one of the differences but the key thing here is what is the the definition of a projection well projection in mathematical language is just an integral and we'll write that down in just a second but it's a mathematical operation that's similar to the physical operation of taking an x-ray photograph with a collimated beam of radiation so let me write that down so so here's a definition of a projection it's a mathematical operation that is similar to the physical operation of taking an x-ray photograph with a collimated beam of radiation and because I'm not the best artist I'm going to show a picture out of this book Dodgina Mershow which is a pretty old book but it has a really nice drawing that I like to flash on the screen for just a second just just to show you if you can zoom in into this picture that would be great so so suppose again we're this is not a patient but it's an object suppose you have an object with with this kind of a density it has three holes kind of in the middle of it it's some metal that due to erosion or some other bad thing some holes have appeared in it and you want to detect it so if I put an x-ray source here and and project along this direction you get the function that as it hits these holes it has a dip here and another dip here and another dip here so by looking at the projection you might be able to you might be able to detect something is going on and then after defectors the first projection you suspect something is wrong so oh we got to do more projections because this this plane could have a crack or this object could be defective and you can take more projections to find out in general projections are expensive and time-consuming so sometimes the goal is to to collect a bunch of projections and then reconstruct this two-dimensional function here that's very costly if if you want to represent this function very accurately you have to take lots and lots of projections sometimes 64 128 or a ton of them and that could be very timely but if if the first projection already shows there's reason to take more than than you do it kind of like medical procedures you have one test so all this thing doesn't really look good let's dig in to have another test that's it for itself okay so as I said the I'm gonna draw yet another picture or show another picture from from this book for the geology application because I think it's it's a nice example if you can zoom in again okay so this is the use of boreholes to acquire information about sorry to acquire information about the geologic formation hey Amazon Prime members why pay more for groceries when you can save big on thousands of items at Amazon Fresh shop prime exclusive deals and save up to 50% on weekly grocery favorites plus they've 10% on Amazon brands like our new brand Amazon Saver 365 by Whole Foods Market a plenty and more come back for new deals rotating every week don't miss out on savings shop prime exclusive deals at Amazon Fresh select varieties it is Ryan here and I have a question for you what do you do when you win like are you a fist pumper a woohoo a hand clap for a highfiver if you want to hone in on those winning moves check out Chumba Casino choose from hundreds of social casino style games for your chance to redeem serious cash prizes they are new game releases weekly plus free daily bonuses so don't wait start having the most fun ever at Chumba Casino dot com sponsored by Chumba Casino no purchase necessary vgw group void were prohibited by law 18 plus terms and conditions apply using acoustic memes so you basically you down in the borehole you put an acoustic or microwave transmitter this is a transmitter h subties the height of the transmitter and and you transmit a signal and there's there's some two-dimensional density here that you're trying to reconstruct and and you have a receiver and you put the as this is transmitting you put the receiver here you put the receiver here at different heights you collect the signal and then you also vary the height of the transmitter and that way you're computing the projection of the the you're assuming fundamentally you're assuming that the only signal that's received propagates in a straight line from the transmitter which is a fairly good assumption in many cases and then once you've achieved the projections you want to come up with the reconstruction of this this this region which could be useful for mapping hydrocarbon deposits essentially oil exploration okay so so let's get into the mathematics of it just just a little bit more I'm going to draw another picture here a little bit with more acts is with more labels on the axis etc so suppose this is our two-dimensional object that we're interested in in reconstructing and I put these axes t1 and t2 okay and suppose that I'm projecting projecting at an angle that's that's theta that makes an angle theta with this axis here so this is my new axis u and and when I do that projection so there's a bunch of let me use a different color here so there's a bunch of lines so there's essentially line integral happening along each one of these lines and what I receive at this end and again I will use a different color should I use this earlier so this is my u-axis and this is my perpendicular to the u-axis is the t-axis this is t1 that's t2 one here okay so after I do the projection I get a some sort of a function going up and down here okay this blue is the is the projection that I've achieved and in this axis again this t makes an axis theta it makes an angle theta with this with this line here which is parallel to t1 okay so this so after I compute the line integral of this two-dimensional object along this direction this function here is called we refer to it as piece up theta of t okay what it's a function of t it for every value of t it has it for every value of t it has a value and this is called the projection of this function here this this two-dimensional function this guy we refer to it as f sub c of t1 and t2 okay it's it we're assuming it's a continuous signal a continuous space signal in 2d okay and this piece of theta of t is the projection of it so is the projection of f sub c of of t1 and t2 okay so the the first question that that you ask yourself is what is the mathematical can I write down an expression relating this piece of theta of t this this new function one-dimensional function to this to this two-dimensional function fc of t1 and t2 think of fc as something that's sticking out of the paper it's like a mountain you know some some for some values of t1 and t2 is high so for some of this low and its extent is kind of shown by here okay so how is how can I from mathematically what do I mean by projection I just tell you it's a mathematical operation that corresponds to the physical operation at x-rados but what is that mathematical operation so let me start by writing that down and then my next objective is to show what's called the projection slice theorem which relates the two-dimensional four-year transform of this two-dimensional signal the one-dimensional four-year transform of this signal so to begin with here's the definition of projection piece of theta of t the projection is the integral and and you can kind of see that as I write it I'm integrating along the the u dimension so in it it's an integral for u going from minus infinity to plus infinity of f sub c of t1 comma t2 where so if this is along the u where how do I get rid of t1 and t2s well the left hand side only have t's well t1 is related to u and t right t1 and t2 are at an angle theta with u t line so t1 is nothing but t cosine theta minus u sine theta and t2 is nothing but t sine theta plus u cosine theta okay so mathematically speaking for this picture up here this is the equation that relates this this one-dimensional projection along the angle theta along the axis u with it which makes an angle theta for this to to the original two dimensional function x of c that we had up there so this is the projection okay and what I'm going to show in the next 10 15 20 minutes is as I said relating the Fourier transform the two-dimensional Fourier transform of this guy to the one-dimensional Fourier transform here so let's let's dive into that process with hopefully without getting too bogged down in in in equations and details so so the goal to write it down is relate the 2d Fourier transform of fc to 1d d stands for dimension Fourier transform of piece of theta okay and this is done using projection slice theorem and I'll set it up and this the actual derivation will be part of your homework it's it's pretty straightforward and it merely involves in change of coordinates but just so that if you help you do the homework let's just do the setup I want to state and and this this goal is achieved but what's called projection slice theorem and this has been in existence for many many years and it's been reincarnated in signal processing in various other fields over and over again but to get going on that let's write down the two-dimensional Fourier transform of f sub c here okay what can what can we say about the 2d Fourier transform of f sub c well f sub c is the two-dimensional function of continuous t1 and t2 or continuous space so you just plug in the standard Fourier transform formula more than one on omega 2 the frequency variables and 2d so it's a this is a two-dimensional continuous time Fourier transform of f sub c of t1 and t2 okay which is then given by what's the expression for it t1 ranging from minus infinity to plus infinity t2 ranging from minus infinity to plus infinity of f sub c of t1 comma t2 e to the minus j omega 1 t1 e to the minus j omega 2 t2 and this omega 1 and omega 2s are also continuous variables in the frequency domain and we also know the the inverse Fourier transform we also can obtain so this is still fc of omega 1 and omega 2 this is the Fourier transform of little fc we can also obtain the little fc that the the space domain signal from its Fourier transform using a final mathematical equation fc of t1 and t2 is given by 1 over 4 pi square which is merely a scaling factor then double integral of fc of omega 1 and omega 2 e to the j omega 1 t1 e to the j omega 2 t2 d omega 1 d omega 2 okay and now what we have I'm going to open this sheet so some of the things we do with paper and under the camera is these things that you really cannot ever do and on the board that you can't fold the board and move it around okay so so so this is the expression for forward Fourier transform this is the expression for inverse Fourier transform and way up here if you can roll up just a tiny bit yeah this is the this is the projection relating the two-dimensional function hey Amazon Prime members why pay more for groceries when you can save big on thousands of items at Amazon Fresh shop prime exclusive deals and save up to 50% on weekly grocery favorites plus they've 10% on Amazon brands like our new brand Amazon Saver 365 by Whole Foods Market a plenty and more come back for new deals rotating every week don't miss out on savings shop prime exclusive deals at Amazon Fresh select varieties I'm Victoria Cash thanks for calling the lucky land hotline if you feel like you do the same thing every day press 1 if you're ready to have some serious fun for the chance to redeem some serious prizes press 2 we heard you loud and clear so go to luckylandslots.com right now and play over a hundred social casino style games for free get lucky today at luckylandslots.com no purchase necessary. VGW group void were prohibited by law 18 plus terms of condition supply to the projection function so because I want to relate the this 2d Fourier transform to the one-dimensional Fourier transform of this guy so let's write down the expression for one-dimensional Fourier transform of P theta and and what is that well I'm going to denote it with P theta of omega but this piece supposedly capital and this piece supposedly small but usually from the variable inside you know this is the Fourier domain and this is the time domain so this is the one-dimensional continuous time Fourier transform of P theta of t so therefore this capital P theta of omega mathematically is is written as the P theta of t times e to the minus j omega t dt and where t goes from minus infinity to plus infinity this is again straightforward definition of Fourier transistors so it's all so far I've only written down definitions and what projection slice theorem tells you is that it relates this Fourier transform is one-dimensional Fourier transform of this blue signal to the two-dimensional Fourier transform of this black signal so it relates essentially this expression to this expression here and and what it says is this projection slice theorem it says that P theta of omega the one-dimensional Fourier transform is just a slice of the two-dimensional Fourier transform that means it's just f sub c of omega 1 and omega 2 evaluated at the slice and the slice is omega 1 is equal to omega cosine theta and omega 2 is omega sin theta and pictorially so which means this is equal to f c omega cos theta comma omega sine theta so pictorially what is what is all this gibberish or mathematical stuff mean well this is what it means this is P theta of omega it means that if I were to draw in the omega 1 omega 2 plane some the this is my f c omega 1 and omega 2 then then if I go to a particular angle theta and take a slice of that so it so imagine this this red bar is a two-dimensional function sticking out of the board imagine like a like a birthday cake or something it's sticking out so if I if I take a knife cutting the birthday cake and I go and evaluate the function along each point here I get a one-dimensional function and that one dimensional function is P theta of omega it's a slice of these two-dimensional function along this okay so this is nothing but P theta of omega so that's a pretty does everybody follow this analogy that we just made okay so that's a pretty powerful theorem because and again it's pretty straightforward to show this because what does it mean well it means that if I took the projection along this angle I'd get a slice along this then if I change the angle and get another projection I get a slice along here then here here here here here here here pretty soon I get enough slices I almost have the 2d 4-year transform of the object I'm after and then at that point all I have to do is a 2d inverse 4-year transform to get the object itself and the object itself is the thing we're interested you know how many tumors have I got in my breast or how many tumors of my brain or things like that hopefully we'll never get in any of those but that's that's the information you're at you're after the two-dimensional object to begin with okay so so the main idea is by taking multiple projections then you can get a pretty good idea of the 2d 4-year transform of the object and then you do an inverse 4-year transform inverse 2d 4-year transform and you get the object which in this case in our case is f sub c of t1 and t2 which is what this is what we're after and and so in real life actually in fact we have one one professor in our department Bernard Bozer who probably some of you don't know because he's currently on sabbatical leaving Switzerland he actually worked on let's see 8d sampling techniques for x-ray tomography applications with some guys at UCSF to so essentially that when you do the in real life when you want to take a projection and when you're doing x-ray you put a to d samplers here to take to come to you it's very hard to compute or to get the continuous function you get samples of this guy and then once you have samples of this guy then you can take the 4-year discrete time for discrete 4-year transform of that and you get samples in the 4-year domain okay there are any questions so far regarding this setup before I go into more details all right how do you get the signal I'll explain that's kind of the next 40 minutes of the lecture you know you're wondering how do you heart from these how do you get this it's coming it's going right right all right oh yeah I'm gonna dive into that but so far I just wanted to make sure that the you know this concept is clear okay so what happens is now as a result of taking your projections you end up with let's say let's say you took a number of projections and one two three four five six seven eight yeah in an example I'm gonna show I suppose that you took eight projections and for each one of these projections you managed to get eight equally spaced samples in the in the 4-year domain so in the omega 1 and omega 2 suppose you take the m point DFT of the projections and let me let me just say what for my example what M is one two three four five six seven eight nine so suppose I take it nine nine equally spaced samples so and so if my angle was theta I get nine equally spaced ones here one two three four five and six seven eight nine and then I could nine more along this direction and then yeah so basically I'm gonna cheat here and basically what what it is is I get pretend I didn't do that I'm only doing that so that I can have my samples in the right place okay okay so so suppose I get these after after I take the m point in this case M is nine so I have eight projections and and this is one two three four five six seven and eight right and suppose the when I take the endpoint DFT of it you can easily show that if the if the spacing between these two samples the same as between these two samples is between these two samples okay these are my son all right so if the spacing between the samples for each projections are the same constant or don't change from one projection to the other I end up sampling what's called in a polar fashion so this is called polar sampling of my two before you domain okay so for every so in polar sampling every angle essentially a you hey Amazon Prime members why pay more for groceries when you can save big on thousands of items at Amazon fresh shop prime exclusive deals and save up to 50% on weekly grocery favorites plus they've 10% on Amazon brands like our new brand Amazon saver 365 by Whole Foods Market a plenty and more come back for new deals rotating every week don't miss out on savings shop prime exclusive deals at Amazon fresh select varieties step into the world of power loyalty and luck I'm gonna make him an offer he can't refuse with family can all these and spins mean everything now you want to get mixed up in the family business introducing the godfather at Champa casino calm test your luck in the shadowy world of the godfather slot someday I will call upon you to do a service for me play the godfather now at Champa casino calm welcome to the family this is an endpoint DFT every angle the spacing between the samples in the 48 domain are equal okay and so how would from from these from these polar samples which have now put them in red how do we get how can we compute the 2d4 your transform of the original object well the 2d4 your transform of the object let's say we wanted to compute this thing over 16 samples they're more on a rectangular kind of grid right and so there'll be like here here here here here here here here here here here here here the blue guys right so one question that that that how I know what I did wrong I have four on this side oh that's correct that's fine that's correct I have four on both sides that's good yeah something like that so the question is I've got the red dots or the red crosses how do I get the blue ones from there anybody has any ideas while I fill out this painful plane how would we do that I was something very simple you have the samples in a polar polar plane and and you want to get you want to get the and a rectangle or a Cartesian grid how would you do it interpolation how would you interpolate what would be one one easy method of interpolate there are many kinds of interpolation right you can do sink interpolation you what else can you do that simpler than sink for example you can do average so linear interpolation so if for example you could say to compute this point I'm going to look at a fixed radius of samples around it and I'm going to have a weighted average of the samples around it where the samples that are closer I'm going to give more weight and the samples that are further away or farther away that's called linear interpolation what's in fact it's got first order interpolation what's the zero-thorder interpolation it's very simple I'm sure you exactly nearest neighbor so I can just say okay so for this point this is the closest sample for this point this is the closest so so basically to get the bottom line is let me move on to the new page just to get the the blue samples blue Cartesian samples from the the red polar samples in this case I need to do some sort of interpolation and I can do a zeroth order interpolation which means that it's called nearest neighbor and that's used all the time in lots of applications I can do first order interpolation which is the weighted sum of neighboring samples on weighted average rather okay so so those are two popular techniques people use and then I'll show you the results from this in just one second if you apply it to some real real-life signal and all that but before doing that I want to talk about the different possibility and that is in this case we assumed that the distance between the red samples for this projection and the red samples between these predictions are all the same that's when we got a polar kind of a distribution now if you change the distance between these samples as a function of the angle the red dots will no longer be on a polar circle but there will be on concentric squares so let me and and it would look something like this if you can zoom in please okay so then so so this is what you get as you can see the distance between successive samples on this projection is the same as this distance between successive samples in this projection now if you change that you get something like this so along this projection this diagonal one for example the distance is is longer between successive samples they're all the distance between the samples are all equal for every projection but but that equal space here is different from that equal space here so this projection for example has samples closer so essentially you've changed the sampling wave as a function of the projection angle and then you get this kind of a thing and this is called concentric squares and there's nothing wrong with that you can now either use again either nearest neighbor or first order interpolation in order to to estimate the values of equally spaced values of the two-dimensional Fourier transform which will then allow you to take inverse Fourier transform to get the samples so so coming back here let me write it down so you can have concentric squares where the distance between the the projection samples in Fourier domain varies as a function of projection angle okay and and and then you get concentric squares so let me just with this two very simple I'm going to talk about a little bit more fancier reconstruction techniques i.e. the radar invariant formula and the iterative technique and just in just a second but for now let me just show you some results for the simple-minded nearest neighbor and and first order interpolation so what we have here this is again off of Donjuna Mersho actually zoom out just a tiny bit so all four can be shown great thank you so what we have here in the upper left is a original signal that our goal is to be constructed it has a lot of good details it's got a lot of angular details and has a small circle here and a big circle here so lots of buttons to try to reconstruct and what's shown here is if you use 64 projections 64 equal angle projections and using the polar sampling and also zeroth order which means nearest neighbor reconstruction and this is a game polar but using the first order interpolation clearly first order interpolation results in better reconstruction than zeroth order interpolation so this you're doing weighted sum or weighted averaging of the samples that are around you here you just say give me the closest sample and that's it so this does better than that and this is if you use linear interpolation and use concentric square kind of a sampling of the Fourier domain and you could argue whether this is better than this I would say this this has slightly better contrast than this but it also has this kind of Gibbs phenomenon it has a ripple thing going on that this guy doesn't okay and moving on here this picture is supposed to show the how the quality of reconstruction changes as you add more projections so that's this is trying to reconstruct that same thing that we saw before using linear interpolation and concentric square sampling here if you just use just 16 projections here if you increase the 32 here's you've increased the 64 by here you've you've increased it to 128 so as you increase the number of projections as you would expect to get better reconstruction okay so this this under any questions so this nearest neighbor and first order is kind of a naive or the first thing that hits your mind kind of way of reconstructing now there is a hey amazon prime members why pay more for groceries when you can save big on thousands of items at amazon fresh shop prime exclusive deals and save up to 50% on weekly grocery favorites plus they've 10% on amazon brands like our new brand amazon saver 365 by Whole Foods Market a plenty and more come back for new deals rotating every week don't miss out on savings shop prime exclusive deals at amazon fresh select varieties every day when you log in to chumbacacino.com the ultimate online social casino you get a free daily bonus imagine if you got daily bonuses in other parts of your life i chose french fries over loaded french fries i asked steward from accounting about his weekend even though i don't care i updated my operating system without having to call tech support collect your free daily bonus at chumbacacino.com now and live the chumbalife btw group no purchase necessary for it we're braided by lost in terms of conditions eating plus formula called the radon inversion formula that has been around again for a very long time i think almost a hundred years that radon developed uh so then and that radon inversion formula results in a technique that's called convolution back projection and the next thing i like to do is derive that so that you can see how it works and then after that i'll briefly talk about the third method of reconstruction is called an iterative uh and and then um that rocks up the lecture so um to to recap everything um here's the various reconstruction strategies okay um so the the first one is is pretty simple and as we just talked about it's um uh it's either nearest neighbor or um it's a first order this is called zero of the order interpolation this is first order interpolation okay and the second one as is as is the radon inversion formula and the third one is iterative techniques so the advantage of iterative techniques as you'll see is that as the iterations go go on you the quality of reconstruction improves uh so once again uh what you could do is if you've got n projections you can tentatively reconstruct something uh using iterative techniques and then decide kind of whether you want to take more projections and as you take more projections the quality progressively improves some other techniques uh for example if you think about the interpolation techniques if you to begin with if you just have two projections you can do the uh nearest neighbor or first order interpolation but if you got four project four projections you have to start all over again as you add more projections just kind of start from scratch again so those are not very good for for progressively construction the iterative technique is disadvantage that you can progressively reconstruct was there any question yeah the things we were looking at in the book we were just basically taking an image and sampling it and then trying to reconstruct that same image with interpolation right no we took projection you started with an image you took the projections over either 32 angle 16 64 etc then you took the the one-dimensional Fourier transform of the projections that's right and then from each of those one-dimensional Fourier transforms give us samples of projection along some angle slapped it on and then tried to to reconstruct the 2d that's right okay so let me move on to radon inversion formula okay um so if we start with um um this this continuous time signal f sub c of t1 comma t2 which is just the inverse Fourier transform of the uh the fc of omega 1 and omega 2 function e to the j omega 1 t1 e to the j omega 2 t2 d omega 1 d omega 2 and this is all omega 1 and omega 2 are going from minus infinity to plus infinity okay and why do I do well in this Fourier transform thing so much because because we are in some sense by having each time we take a projection and it takes the Fourier transform of that one projection we're getting samples of this guy right so it's inevitable to deal with the Fourier domain in fact in many medical imaging modalities the Fourier transform just without us really it comes into play automatically MRIs and other modality when you go in that magnetic tube and they do the samples etc all those junk at the end of the day they have computed the two-dimensional samples of the Fourier transform of you know a slice let's say this slice across my body automatically and and then the final step before the doctors can look at the pictures is the inverse 2d Fourier transform so so Fourier transform is one of those important the reason for the transform is so important is that in many applications it occurs naturally I mean think about it MRI what is it it's a coil and and you apply a magnetic field to select the plane and then you apply Paul says none of those things know about Fourier transform do they no I mean to a physicist let's say let's say to somebody who's never seen Fourier transform not at the things I just described have anything to do with Fourier transform it's a bunch of inductors and chords and magnets and B fields and H fields and and atoms spinning and atoms relaxing and pulse pattern not anything before your transform but when you all end all done you're sampling in those guys call it a k-space you're sampling in the 2d Fourier domain which which means that to get your image back you got to take an inverse Fourier transform so so the Fourier transform is very powerful that also in optics application in SARS synthetic aperture radar applications in many applications it automatically appears in the scene and so there's a need to undo it to get the thing you're after okay so here here's the radon inversion formula and the i'm sorry here's the here's the inverse Fourier trans inverse 2d Fourier transform of f sub c and i'm going to convert this to polar coordinates in order to be able to arrive at the radon inversion and i won't go into all these steps of it but you can show that i'm going to replace omega 1 and omega 2 with little omega and theta and so in that case f sub c of t1 and t2 is given by 1 over 4 pi squared the integral from 0 to pi of d theta and then the integral from minus infinity to plus infinity of d omega and this d omega in the polar coordinates sense i'm making theta to be this angle and omega is the kind of the radius going out okay omega is not the same omega you guys have seen in 123 which is the you know the the angular frequency okay so f sub c and now i'm going to replace omega 1 and omega 2 with the polar version of it which is a little omega cosine theta comma little omega sine theta times let's see e to the j and now i'm going to replace this omega with this omega 1 t1 omega 2 t2 with appropriate stuff so it's e to the j little omega t1 cos theta plus t2 sine theta and there's one more thing i have to add to this integral in this conversion and that's absolute value of omega okay so theta is going from 0 to pi and omega is going from minus infinity to plus infinity omega is the radius thing and um staring at this thing uh the the polar coordinate change was a good thing to do why is that can anybody say because this thing here is what this expression is nothing but yeah is the projection along the angle theta as a function of omega so i can write this thing as f sub c of t1 comma t2 1 over 4 pi square a lot of times people ask me how did you know you have to convert to polar coordinates and the always answer is i didn't figure that out somebody else did and i'm just presenting that and after a while when you're busy in this business you know you have a bag of tricks and you just keep applying that so one for 4 pi squared the integral from 0 to pi the integral from minus infinity to plus infinity now it's p theta of omega and then this this thing repeated e to the j omega t1 cos theta plus t2 sine theta times absolute value of omega the omega theta okay and um now i'm going to name this integral here hey amazon prime members why pay more for groceries when you can save big on thousands of items at amazon fresh shop prime exclusive deals and save up to 50 percent on weekly grocery favorites plus they've 10 percent on amazon brands like our new brand amazon saver 365 by whole foods market a plenty and more come back for new deals rotating every week don't miss out on savings shop prime exclusive deals at amazon fresh select varieties it is ryan c crest here there was a recent social media trend which consisted of flying on a plane with no music no movies no entertainment but a better trend would be going to chumbakasino.com it's like having a mini social casino in your pocket chumbakasino has over a hundred online casino style games all absolutely free it's the most fun you can have online and on a plane so grab your free welcome bonus now at chumbakasino.com sponsored by chumbakasino no purchase necessary vgw group void where prohibited by law 18 plus terms and conditions apply all the way from here to here i'm going to call that integral i okay okay what can we say about i well it seems very much that i is the inverse four-year transform of the following expression p theta of omega times absolute value of omega however in that four-year transform i have to replace a t with this expression here if i just took inverse four-year terms of p theta omega absolute value of omega i get something that has t in it so i have a function of one variable t but i have because and that's that variable so i have to replace whatever that if i call that t but that variable with t one cos theta plus t two sine theta okay so this is it seems like this thing here is some sort of an inverse four-year transform so but what is what is the inverse four-year transform of what is this expression here well um if we let's just define um just g theta of omega to be this guy p theta of omega times absolute value of omega so in that case what we also say that the inverse four-year transform of g theta of omega is just little g theta of t okay so what can we say about all these things well having defined all these things let me rewrite i and if you can roll up just a little bit so people can see i okay great thank you so i can rewrite i this this integral as the integral from minus infinity to plus infinity of of of the prime p theta of omega times absolute value of omega as g theta of omega times this this long exponential e to the j omega t one cos theta plus t2 sine theta times the omega so what can we say about this well because the inverse four-year transform of g theta of omega is g theta of t so i is just g theta of t but evaluated for t being t1 cos theta plus t2 sine theta that's what i is so in other words i is g sub theta i just replaced the t with t1 cos theta plus t2 sine theta that's what i is and now i'm going to come back and plug in the expression i just found for i into this thing here so fc of t1 t2 is one over four pi square this integral from zero to pi of g theta so let's let's do that so um plugging back all the way up you get f sub c of t1 and t2 is one over four pi square of integral from zero to pi of g sub theta t1 cos theta plus t2 sine theta d theta okay so that's that's a big that's a big step that's a big equation and let's now interpret and see if it is any useful after taking all these symbols and pushing them around does it amount to something interesting i think it does because why because think of what all these things mean what what is g theta well we already know from up here that g theta is the inverse Fourier transform of this capital g theta and capital g theta is the product of these two guys so putting all these things together what does it tell you it says start with your projection p theta of omega or rather start with the p theta of t your time domain projection take computers for your transform boom right here multiply it by by this guy by absolute value of omega then take inverse for your transform get g theta of t and then plug it into this thing or you can be a little bit you can go one step further and say well instead of if i'm multiplying these two functions of omega in the frequency domain what am i doing to them in the time domain convolving them right this is the Fourier transform of my projection this is omega the the the frequency axis in the continuous time domain right so this has an inverse Fourier transform it's a one-dimensional function of time t and this is this has an inverse Fourier transform that's the projection we got those are the the integral that we achieved before taking its Fourier transform it was in the time domain so get those two time domain signals convolve them with each other and that gives us g sub theta of t straight on and then plug this back here okay that's why it's called convolution back projection i'm going to convolve the projection i got in time domain with the inverse Fourier transform of this whatever the thing is that's the convolution and then plug it into this integral and it's called back projection okay so let's let's write down these steps so we're recalling that g theta of omega is p theta of omega times absolute value of omega okay so that means g theta of t is k of t convolved with p theta of t where k of t is just the inverse Fourier transform of this funny function omega absolute value of omega and what is we can also show mathematically that g theta of t is nothing but the derivative with respect to time of this integral p theta of tau over t minus tau d tau okay so this convolution with inverse Fourier transform of this guy is nothing but taking the derivative of this thing so this this explains what we mean by convolution back projection so the steps to take are start with p theta of t and then convolve with k of t which is the same as this integral to get g theta of t and then step three plug g theta of t into this equation which i call let's call it star into star and again pictorially after i compute g theta of t what what does it mean that i plug it into this let me draw another picture to kind of clarify that what what is the intuitive meaning of this this integral it it's this i come here and i have t1 and t2 this is this is the plane i want to reconstruct my two-dimensional object this is f this is where i want to find fc and after i compute g theta of t g theta of t is this function of one variable t right is it looks something like this this is g theta of t right and what it says is that for each value of t corresponds to a t1 t2 plane so when t is this value then it's t1 it corresponds to t1 taking t2 taking this and t1 taking that what that means is whatever value g theta of t takes at this particular value of t let's let's call this t0 at t equals t0 the height of this function g theta tells me the height of the fc of t1 t2 is that clear so so if this is g of t and at t0 it takes on g of t0 then and t corresponds to t1 and t0 corresponds to t10 and t20 is t0 this is t20 this is this point is t10 then f sub c at t10 comma t20 is equal to g of t0 is that clear now so i start with g theta of t it's been computed at angle theta don't forget to label that it's some sort of a function and i'm saying the value of that oh sorry sorry no no no no noise oh no no that's correct that's correct not quite actually this is not quite correct so i get this if i look at this integral all right i have to stack up all these g theta's and add them up it before i get the fc of t1 and t2 so so this is still correct actually technically speaking this is correct but it says it says that this one gives me the value of fc of t1 t2 along these these samples and if i want to get all of fc of t1 to do i just integrate this g theta along different angles here here here here here here here here until i'm all done plug it into this equation um so that um so that so that so to do the back projection to get f fc is that clear or do i confuse enough of you yeah question so you essentially you you pick a t1 and t2 and then you do add all of them for all the thetas do you know yeah that's correct that's correct for for so this part of it is strictly speaking not not not quite correct but yeah for every value of t1 and t2 i get this g theta's and i and i and do a one-dimensional integration of it so this is called again convolution back projection and the convolution part is to just to get g theta because g theta is a convolution of remember g theta is is the convolution of k with p theta so that's that part and then the back projection part is is just this for so so yeah that's correct so let me show you some pictures on page uh three seventy four of this result of convolution back projection um before the lecture is over all right um so what i have here is that original signal that that's you saw um comparing all right okay so so this is the original can you zoom in just a little bit to this partition so what it is is this is the original signal we started off with no projections nothing here is if you use um to the technique we use to reconstruct both of these is the convolution back projection however on on the left we use polo coordinate sorry on the left we use concentric squares and here we use polo coordinates so you you could i don't know how well it shows up there but um again the the polo coordinate stuff is has a little bit less resolution than than the concentric square one but this has a little bit more Gibbs phenomenon oscillation kind of going on but more interesting um then then then either one of these things is to compare this is using 64 projections to compare for example this guy with concentric square using back projection against concentric squares using again this is using 64 projection concentric squares using just linear interpolation versus this one which is using back projection so you can get a lot better reconstruction is in back projection convolution back projection then you would with just simpler interpolation so those are the two things you've got to compare 64 projections concentric square 64 projections concentric square and here is one more time can zoom out please showing back projection technique doing 16 32 64 and 128 projections so again the quality of the construction becomes much better as you increase the number of projections well at 128 this is almost indistinguishable at least by the time it gets to the tv screen from the original one okay okay just before we end today's lecture let me just talk for one minute about that another technique because i already advertised it so much and that's iterative projection iterative reconstruction sorry and the basic idea there is um you've got your projections and and you get into this iterative process and whenever you do iterative reconstruction of anything one of the biggest dangers is what convergence so the way it works is f sub c of t1 and t2 at iteration k is the the answer that you got at iteration k minus one which is f sub c of k minus one t1 comma t2 plus the sum from i equals one to n of lambda i's which are some sort of a knob that determine the convergence rate so it determines convergence rate and what do we normally put here usually you you put a error term here right so the final answer is a combination of the old answer plus some adjustment and how much you adjust depends on what depends upon how correct was your previous answer how how much error it was in the previous answer that you got and the way you do that is you compute the projections um the actual projections compute the difference between the actual projections and the computed projection of the previous answer you got so p sub theta of i of t1 uh cos theta plus t2 sine theta minus the di of um f sub c k minus one of t1 comma t2 so let me now explain this thing here so this this this thing is actual projection actual projections that you've observed this is the projection operator applied to to the previous reconstructions to the kth iteration reconstruction okay so at at the kth iteration i i computed some signal that i thought is is is my answer and now i applied the projection operator to it to compute okay if that signal was really the answer what would its projection be along these uh n angles and i compute each one of those projections from the actual projection i started off with remember that's the input to my algorithm and that causes some error when the error here is very large that means that my signal f sub c of k k1 was off from the real answer and therefore this term is large and so this term dominates the final answer and i tweak the final answer a lot like this term becomes large on the other hand as f sub c as the answer that i'm computing gets closer and closer to the to the real answer the difference between these two terms is very it's become smaller and smaller therefore i perturbed the answer that i got in the k minus first iteration less and less and my signal begins to converge so this is kind of an error term right so um let me see if i can show you if there's an example of the iterative reconstruction in uh in Mercer's book i think it's no unfortunately i i don't i don't see that um and generally speaking as i said one problem with iterative techniques is that uh convergence could be slow sometimes the convergence would not be there so and sometimes the convergence and the final answer you get depends very much on how good of an initial guess uh you made so i want possibility would need to use a simple technique like linear interpolation to get a dumb some quick answer as your initial as your zeroth iteration and then improve it by applying the iterative techniques so you can mix and match these techniques as you wish okay that's the end of today's lecture i'll see you all on Friday hey amazon prime members why pay more for groceries when you can save big on thousands of items at amazon fresh shop prime exclusive deals and save up to 50 percent on weekly grocery favorites plus they've 10 percent on amazon brands like our new brand amazon saver 365 by Whole Foods Market a plenty and more come back for new deals rotating every week don't miss out on savings shop prime exclusive deals at amazon fresh select varieties every day when you log in to chumbacocino.com the ultimate online social casino you get a free daily bonus imagine if you got daily bonuses in other parts of your life i chose french fries over loaded french fries i asked steward from accounting about his weekend even though i don't care i updated my operating system without having to call tech support collect your free daily bonus at chumbacocino.com now and live the chumba life btw group no purchase necessary void reparated by law he terms and conditions 18 plus