The Bold Blueprint Podcast
The Bold Blueprint Avideh Zakhor When we fail
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 save 10% on Amazon brands like our new brand Amazon Saver, 365 by Whole Foods Market, Aplenty 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. Professional spend nearly half the work week on written communication. So focus is important. With Grammarly as your AI writing partner, focus and quickly get through your work with relevant real-time suggestions. And it works across 500,000 apps and websites so you can sound more confident and persuasive wherever you write. 93% of professionals report that Grammarly helps them get more work done. Download Grammarly for free at grammarly.com/podcast. That's Grammarly.com/podcast. Are there any questions or comments before we get started? So just let me do a quick show of hand. Let me install this. Okay. Okay. It doesn't matter. I'll just leave it at the table. How many people took between zero and five hours to do the lab? I mean total end-to-end. So nobody. Five to ten? Okay. Most people 10 to 15? Wow. 15 to 20? Okay. This was a hard lab actually. I admit up front. The next homework is a lot easier. It's four problems. Okay. Let's look into next week. And just also another show of hand to see, you know, how many of you find the TA useful and office hours useful? How many of you went to visit office hours this week? Oh my god. Okay. Very excellent. The TA is very good. Okay. Very good. You know, I always, every semester, the department normally doesn't allocate the TA for this course. And every semester, like a week before classes started, I have to go on beg. And at that moment in time, you know, everything is settled and they say, "Yeah, we have a little bit of money available. You could have a half time TA." And then I grab it and that's how we ended up with Cindy. And the last time it was the same story and the time before that, it's the same story. So it's always a bit of a struggle and I'm trying to figure out whether it's worth the last-minute fight or push to get the TA. And if you guys find it useful that's good. So, what I'm going to talk about today is, is filter design for 2D. And I'm hoping that, excuse me, this is it. This is all the 2D signal processing stuff we're going to talk about and that hopefully beginning next week. Excuse me. We're going to start talking about image processing. Start with basic human visual systems and then move on to enhancement, restoration, imaging systems, quantization sampling and other fun stuff. So this is the last of kind of the basics. If you don't know what filters are, you wouldn't know how they arrived at, you wouldn't know how to design one if the need arises. So what we talked about last time was there's basically three steps in filtering. One is figuring out what your specs is and that's very much an application domain type thing. Whether you are designing a filter, let's say for a cell phone to reject out-of-band kind of signals or whether you're designing something for a VCR. It's just very much application-dependent. By the way, how many of you attended the talk by, I can't remember the guy's name, on Wednesday from 11 to 12 in Corey Hall by the XFCC guy. Was this man in his like 70s almost, white beard, white hair. He had spent his life at FCC and the topic of the talk was spectrum property rights. In other words, right now there's a lot of demand on the spectrum and in different services chew up different parts of the spectrum. There's the there's a portion of military uses and there's a portion for emergencies, the police, this, that and the other and as you know the government of US FCC auctions these and he was talking about the notion of owning a piece of the spectrum and how difficult it is to define that simply because even when you define a simple thing like an AM radio you could say okay this is my spectrum band. What happens is that in summertime for example in wintertime for example on the east coast there's a ton of interference from European signals bouncing off the ionosphere coming out and you can almost listen to radios from Europe and the east coast of the United States because of the reflection of the ionosphere and in the summertime it all becomes noise so there's a time varying nature to the ownership or to the spectrum and to the ownership and therefore that's what makes the ownership of spectrum very difficult and a good part of his talk was about filters that are in receivers and how the companies like the fixed wireless guys who are trying to compete with the cable and the DSL companies to put a high speed modem in your homes they initially put a really cheap receivers to to minimize cost because they were adjacent to the satellite radio spectrum like the Sirius and the what's the name of the other one? XM right and then the Sirius and XM guys decided they're going to put repeaters on earth and not just they're not just going to be satellite but in urban areas they're going to put repeaters and as soon as they did this the signal spilled over to the adjacent band which is the which is what these fixed wireless guys were using and so now the receivers they have to design was much better and what does that translate in our discussion that means they have to have a much sharper kind of a filter to reject out of band kind of signals and that directly translates into cost and implementation cost increases and all that and then even for people who think that filter design is out of fashion and it's irrelevant that's that's really not the case it's still quite a bit of but it's a done deal in terms of designing filters nobody will does research in that but it's still used in day-to-day applications to reject out of band kind of signals and define the notion of interference anyway the bottom line for this guy's talk was that defining ownership of spectrum is very difficult and and the government is very hesitant to to either come up with methodology to say okay if you pass this test then this this piece of spectrum is yours and anybody who infringes on you using this test that they're in they're infringing and and you can sue them so the government is very hesitant to come up with those guidelines because of the difficulties in measuring property rights for spectrum and he kept referring to it as it's as if somebody came to to your house and invited them since I started drinking beer in your living room kind of by spilling over from one band to the other is the signal kind of coming over anyway quite interesting stuff what I'm going to talk about today is really very quickly three methods of designing to these filters and two of them are very similar or just extensions of one dimensional techniques and the third one is a transformation technique by McClellan who by the way is the same fellow who designed the parts McClellan filter in one dimensional signal processing and then and then that'll be that'll be the end of the discussion on on to the F.R. filter design and we'll move on to to other stuff so let me just begin with saying few words about filter specs lost my good pant yeah okay so I'm going to start with a one-dimensional example if I have a low pass filter then I can as a function of omega I can talk about the magnitude of each omega satisfying certain constraints in particular I can talk about a region in the frequency domain 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 save 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 bet you didn't think this would be the year you achieve the dream of flight I fly indoor skydiving lets you experience the freedom and thrill of flying no experience or wings required I fly is fun for people of all ages and abilities and it's the perfect choice for a night out with friends family birthday parties corporate events or even just celebrating a Thursday you'll never forget your first time flying go to I fly world dot com and use code take flight for 20% off that's I fly world dot com code take flight in here which we call passband where we require H of Omega to be to be within a certain range between one and but no less than one minus delta P this is this this is the region that because it's a low pass so this is the region you want the filter to pass the signal and then you can also talk about different region which is called the stop and this is the band in which the filter is going to stop the signal and you want the filter that manage the virtual mega to have a different set of satisfy set different set of characteristics if you want you want it to be very small you want not to let the signals go and this band in between Omega P and Omega S is is just called the transition band and it allows we don't we don't put any conditions or requirements or specifications on the filter here and for stop band let's say we say that this has to be smaller the magnitude of H of Omega has to be smaller than delta S so in general delta P and delta S they're called ripples this is called pass band ripple and this is called stop band ripple and it could they could take numbers like point oh one or point double oh one or they could they need not be the same anyway they could be different okay so now we move on to two dimensions and you can talk about two dimensional specifications just as easily more or less the same way okay so two dimensional specs so in now instead of having as a function of omega we have we plot something in the omega one mega one omega two plane and instead of having a pass band frequency and a stop band edge like Omega P and Omega S we're going to have a pass band contour and a stop band contour so we call this C sub P and we call this C sub S this is a pass band contour so this is again a low pass filter but in 2D okay and basically now our specification becomes something like this we want magnitude of h of omega one and omega 2 to be between one and one minus delta P for all omega one and omega two that are inside C sub P inside the pass band so this is our pass band region and then for for stop and we'll have the following thing we want magnitude of h of omega one and omega two to be smaller than delta S for all omega one and omega two that are outside C sub S the stop band so this would be the stop band region and let me just use a different color like green this would be the pass band region okay so similar sort of ideas whole and you can also have what's called a a band pass filter rather than a low pass filter and any questions on this before I move on okay so we can talk about band pass filters and in 1D it would look something like this you pass signal between omega S and omega P and you reject everything else and the equivalent of that so this is in 1D and the equivalent of that in 2D would be something like this this is omega one omega two goes from minus pi to pi minus pi to pi we're looking at the frequency response and so you stop the signal from passing through here and you stop it from passing through here so it's zero zero zero there and you pass the signal here so it's one in this region so pass band you pass the signal in the green and you stop it in the red simply because there might be some characteristics some specific kind of features you're looking for in that in that frequency band and then there's also I'm not going to talk about it but there's also band stop where you're letting all the frequencies go through except for one band for example what would be a typical example when you use band stop filters in 1D if you want to try to get rid of 60 Hertz interference you just put it for the filter that you have a signal you want all of it but there's this big spike at 60 Hertz because of whatever interference so you pass it to a band stop filter that passes everything except for that region around 60 Hertz and in 2D you can also have a different kind of filter that whose equivalent doesn't exist in 1D and that's a directional filter because the notion of direction doesn't really exist in 1D but it does exist in 2D so you want to pass frequencies along a certain direction and and reject other frequencies along a different direction so and I think one of your homework assignments is just on that so you want to talk about directional filters can't remember now I think you might have a MATLAB assignment just on this in a week or two so and what what it is is you for example you want to draw a line like this okay and again this goes from minus pi plus pi so you pass these and then you stop the rest of it okay and you could say the angular theta etc so why so in images and in two-dimensional signals if you have if you have features that are predominantly horizontal or predominantly vertical or predominantly at an arbitrary angle you can you can either eliminate those or accentuate those and try to catch catch the edges and the directions along a particular direction by using a directional filter or if you're doing two-dimensional signal processing you want to know you have filters in a plane and you want to know which direction let's say there's waves coming at you and you want to know which direction this wave was coming from you can have a series of filters like that along a different directions and then look at the output and say oh the output of that 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 save 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 we wear our work day-by-day stitch-by-stitch a dickies we believe work is what we're made of so whether you're gearing up for a new project or looking to add some tried and true work where to your collection remember the dickies has been standing the test of time for a reason their work where isn't just about looking good it's about performing under pressure and lasting through the toughest jobs head over to dickies.com and use the promo code work where 20 at checkout to save 20% on your purchase it's the perfect time to experience the quality and reliability that has made dickies a trusted name for over a century angle theta is largest so there must be some signal coming from there and back in the mid 80s where we were deeply involved in the cold war and we were we were in the business of treaty verification for example at Lawrence Livermore a bunch of my friends were working on designing adaptive directional filters they would implement them undergrounds and in order to listen to the Soviet nuclear explosions on the ground and and figure out whether what direction the signals are coming from whether or not they're doing any nuclear testing or not whether or not they can the signals are arriving from you know this part of Russia or the other part of Russia or whether it's maybe China doing the test etc so so this is used for detecting the direction at which signals kind of are arriving and it's also used actually in image processing it turns out that there's a notion of directional sub-band coding for sub-band coding which is a technique for image compression David Podman in in 1993 or for he and I published a paper on sub-band directional filters as well so there's all kinds of 2D filters one what to think about designing and what are the some of the techniques that we're going to use to do that there's are three basic ways of designing FIR filters and and we're we're primarily concerned about if why not impulse response filters because they can be done with zero phase or linear phase with a simple symmetric constraint and also they have no stability issues the first technique I'm briefly going to talk about is the window and the extension from one to two D is very straightforward the second technique is frequency sampling and again the extension is very easy and then the third technique is designed by transformation and I'm going to this is a technique that McClellan who's now a Georgia Tech came up with and many years ago and this is something the equivalent of which in 2D doesn't exist but essentially the idea is let's start let's transform the problem into a one-dimensional problem design a good filter in 1D and then and then we'll get an answer in 2D so let me begin real quickly with the window technique and again this is pretty much a review of 123 you start with an ideal frequency response something that that you want supports somebody who has come to you and says I want to break filter well we all know that's an ideal frequency response and and if you really wanted to get that you would have to have an impulse response that sync which is not only IOR it's an IOR with non rational transfer function so forget about that but but but still you can you can dream of having an ideal thing and then pick the inverse discrete time Fourier transform of that in this in the case of this thing it could be for example H of n which is a sync function okay and it could be infinitely long and let's just we call this thing H sub D of omega we call this thing H sub D of n the desired infinitely long impulse response and now because we have to because this is infinitely long and it's an IOR then to make it FIR we just multiply H of n by some window function W of n and this guy is just a window function right so all of this just straight in a very straightforward way translates into two dimensions in the following sense if you can roll up please thank you so we just do all those same steps and we'll have H of n1 and n2 being equal to a window function n1 and n2 times H sub D of n1 and n2 this window function could be very simple it could be just a rectangular window that basically just truncates this IOR filter it could have some other fancy shapes it could be a raised cosine window a hamming hamming black man there's as many windows as as your heart desires just so that I can have a quick understanding of how much you've been exposed to the people how many people have heard of the window design technique in FIR filter than before fantastic so we won't do all over it too much so really quickly if this is your H of omega the desired magnitude ranging from minus omega p to plus omega p and this is your H sub D of n which is a sync type thing then you you you multiply by window function which would truncate it by this this is your window function and essentially by by doing this multiplication in the time domain you're convolving the Fourier transform of the window function with H of omega so the resulting this is H sub D of omega sorry so the resulting H of omega that you get as a magnitude of it is going to be so here we're going to be convolving W of omega with H sub D of omega and generally speaking the longer the duration of this window is the more the Fourier transform of the window is going to be like a delta function and therefore the function involved with H sub D of omega is going to keep H sub D of omega in as intact as possible right the the shorter this this box function is I mean what is the Fourier transform of H W of n the window function if it is a rectangular one it's a sync so the shorter this W of n is the fatter the sync is and when you convolve that sync with this thing you're going to get a big transition and slower transition some ripples here and a slower transitions back okay so and and you can also have similar arguments with with other window functions so so the the the duration and the shape of this guy determines how good the final H of omega looks like so the window the shape that the length of the window let's just write that down the length of W of n and the shape of it determine how good H of omega at the end ends up looking like so how do we translate all of these things in in 2D well first of all in 2D we're very much interested in linear phase or 0 phase kind of filters so let me roll back please just a tiny bit so 2D windows generally speaking if I have an H of omega it has a magnitude and it has a phase and linear phase means that F of omega this guy here is linear in omega that's all that means and zero phase means F of omega is just zero so in this case if I were to plot as a function of omega 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 save 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 we wear our work day by day stitch by stitch the Dickies we believe work is what we're made of so whether you're gearing up for a new project or looking to add some tried and true work where to your collection remember the Dickies has been standing the test of time for a reason the work where isn't just about looking good it's about performing under pressure and last thing through the toughest jobs head over to Dickies comm and use the promo code work where 20 a checkout to save 20% on your purchase it's the perfect time to experience the quality and reliability that has made Dickies a trusted name for over a century omega I get a line and in this case if I were to plot the of omega as a functional omega I just get zero okay so we don't necessarily so in our case if you can easily show that when when you're writing down the product so if you have H of N1 and N2 equals H sub D of N1 and N2 times W of N1 and N2 that's your two-dimensional window we know that if this is a zero phase window and this is just a desired impulse response if H of D is zero phase and if W is zero phase then H of N1 and N2 is also going to be zero phase so if you're inner and the same argument is true by the word with linear phase if this is linear phase and this is the final thing is linear phase so if our goal is to design linear case filters we need to do no more than starting with an impulse response that's linear phase and starting with a zero and a window that's that's linear or zero phase what are some of the applications where you would want like linear phase almost all image processing applications are the really yeah yeah otherwise your edges all get blurred up you almost almost yeah I haven't seen many FIR filters used in image processing even when you do sub encoding that's you you want to impose in linear phase in image compression because again it messes up the edges of images if you the edge as I said earlier is it is a transition from it's a sharp transition and and the way you from a Fourier transform or for harmonics point of view the way you generate it is you have a bunch of sciences adding up with the right phase with they have to have the right phase with respect to each other if that gets filtered and the relative phase of the sinusoids that are adding up to make the edge get mixed up because the filter wasn't linear phase then the edges get blurred and you can all see why linear phase makes the the relative phase of these things to be preserved because because it delays because delay is the is the derivative of phase with respect to omega so if you have linear phase all the science will get delay the derivative of this thing is look let's bring back here if you have linear phase that the derivative of this thing is constant no matter what omega you're at and therefore the amount of delay between the sinusoids remain constant as they go into the filter as the relative shift is the same going before and as coming out after because they got delayed the same amount because this was a linear phase so the linear phase is a pretty important property we almost exclusively talk about using linear phase filters in image processing what one of the things you might say is well how come we talked about this boundary condition stuff and all these other things with with with PDEs and difference equations which was IIR filters what those those also get used in image processing for example the in computer vision a clear example of it is and an isotropic diffusion processes with which malicant corona came up with in late 80s that uses essentially a PDE that that recursively the processes but that's really done in order to kind of segment an image it and and to to make the the some of the features that are less important go away and the features are more important show up etc so there is some applications where you use difference equations solving PDEs in science and engineering applications and mechanical engineering heat transfer heat propagation etc those also use the same kind of thing but for images where you care about edges most of the time you use linear phase or zero phase okay coming back down here so what are some typical windows that we can use as I said there's thousands of them but we don't bother about writing them all down but let's talk about the Kaiser window because it has some knobs that one can easily tweak in order to to extend it to 2D so let me write down Kaiser window it's in the analog version of it not even the discrete is given by i zero of alpha 1 minus t over tau squared over i zero of alpha and I'll define all 0 i 0 in just a second for t magnitude of t smaller than tau and at zero otherwise so roughly speaking the duration of this window is is too tau an alpha is just a knob that trades off the main lobe width of the of the window with side lobe height I guess one thing that you want to walk away with in this picture just the reminder of 123 is there's a there's a there's a the main lobe width of the Fourier transfer of the window function in other words the main lobe width of this tells you how long the transition takes because you convolving this with h of which h sub d of omega so the the fatter the main lobe width of w of omega is the Fourier transfer of the window is the longer the transition is because you're convolving it with this guy right and then the second attribute of this window is the side lobe height if this guy has a lot of side lobe height as you're convolving the Fourier transfer of this thing with this when you're here at these positions if there's a lot of side lobe up and down there's gonna be a lot of ripple here and a lot of ripple here and a lot of ripple here so and and and when we teach 123 and 1d there's a whole lot of discussion okay well if you use you know rectangular window you get you get very good main lobe width but terrible side lobes if you use you know kai's if you use raised coastline hamming hamming etc the main lobe gets bigger but the side lobe gets smaller and so people are all confused what window shall I use kai's offer is a very nice compromise or trade-off it has a knob alpha it's just like a knob on your stereo you can you can tweak alpha and by doing that you can do this trade-off between main lobe width and side lobe width of the Fourier transfer of your window which translates into the trade-off between transition width of your final filter and the amount of ripple that you get in passband and stuff man okay and I still haven't defined i zero just for circuit completeness i zero of x is just a modified zero to order the vessel function and there's various ways of defining it one of them is to say vessel function one of them is to say it's a solution of a differential equation another way is to write write it in terms of series i zero of x is summation from i equals 0 to infinity of x to the power of 2 i 2 to the power of 2 i and then i factorial squared okay and you can you can look up the definitions of zero through their vessel functions these series expansions in any CRC 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 save 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 we wear our work day by day stitch by stitch a dickies we believe work is what we're made of so whether you're gearing up for a new project or looking to add some tried and true work where to your collection remember the dickies has been standing the test of time for a reason the work where isn't just about looking good it's about performing under pressure and lasting through the toughest jobs head over to dickies.com and use the promo code work where 20 at checkout to save 20 percent on your purchase it's the perfect time to experience the quality and reliability that has made dickies a trusted name for over a century okay so now that we have this Kaiser window that has this knob alpha that allows us to do this this trade-off that we just talked about how do we translate that in 2d it's extremely straightforward uh you just say if you can roll up please so the the 2d window is just come up with a continuous first come up with a continuous time 2d window and then sample it to make it discrete so the continuous time I would say WA of t1 and t2 is just WA of t1 times WA of t2 that's one simple way of doing it I'll show you a second way in just a second and then step one is this and then step two sample this to make it discrete so you say wn1 and n2 is just WA of t1 and t2 with t1 equals n1 t2 equals n2 and this is forwards n1 and n2 in some region of support r sub w and it's zero otherwise so ahead of time you've kind of decided that that um as a function of n1 and n2 you've decided that this is not a good picture let me just move on to the next page wait so you've decided that as a function of t1 and t2 this this goes from minus to plus tau in this direction minus tau plus tau in this direction and you first come up with WA of t1 and t2 and then you sample it and it's supposed to be equally spaced even though I'm not doing it equally spaced for some reason so in a sense the discrete the discrete time window that you get w of n1 and n2 is WA of n1 times WA of n2 where this is just a sampled version of WA t okay and you can also show because this is a so this is called separable right now we have a window function that's separable and the Fourier transform of this guy is just the Fourier transform of this times the Fourier transform value and WA of omega 1 times wb of omega 2 so that's one simple way you have a one-dimensional window just just multiply it in one in dimension t1 and dimension t2 and from one dimensional window to get to the two-dimensional window and the second way of doing this is um is just rotate the one-dimensional window to get the two-dimensional window out of it so are there any questions let me pause for a second yeah right right we should I think we showed that almost let let her run or something like that or we we just mentioned it you can prove it very easily the the Fourier transform property um and and right we also show what I think what we showed at the beginning of the class also is that if your impulse response was separable you can do the computation a lot faster than if it wasn't separable so another way to do to the windows is just the rotation business another will rotate WA of t to get WA of t1 and t2 and then sample WA of t1 and t2 to get W of n1 and n2 okay so what do I mean by that well what we mean is WA of t1 and t2 is just WA of t but rotated so replace t with square root of t1 square plus t2 square okay so now the picture that you get for uh W as a function of t1 and t2 the picture that you get for WA of t1 and t2 is um it's something that like takes on the value one here and takes on the value zero outside okay and uh thank you uh so now not that I did the rotation now I have to sample this so what I say is W of n1 comma n2 is WA of t1 and t2 but sample that t1 equals n1 and t2 equals n2 for all the n1s and n2 that are in some region W and it's zero otherwise okay so this is a uh circularly symmetric window and and at the end of the day if the I'll show you now some pictures of these things in action at the end of the day when you use a circularly symmetric window it turns out the h of omega one and omega two the frequency response that you get it also has contours that are circularly symmetric so let me let's take a quick look at that that'll be chapter four here we go okay if you can just zoom in as much as you possibly can great so this is an example of a using is a circular symmetric or the separable separable like we can say right or what you can tell right away by the way can you guys in matlab I bet you can do nice plots like that right yeah these are straight forward plots of half of matlab do you feel yourself that you're getting more familiar with the image processing to kill the matlab by doing the lab works are you do you now know most of the commands and stuff because you have to search so long to finally to find the commands then you won't fit it anyway so this is a separable kind of a filter and by contrast this is a circularly symmetric this is just a 4e transform of the window function we're still not talking about the filter so this is w of omega one and omega two which is a 4e transform of the window function when you do the rotation business and so this is a yeah that's kind of an interesting picture i'll just quickly talk about it what you see here is a circularly symmetric window where you when the with the one dimensional filter was hamming window where you rotated it and the expression for hamming window is shown right here some people call this a waste cosine it's uh it has a shape of a cosine that gradually dies down and goes to zero and this is the for for for tau equals eight um out here is the kaiser window with alpha equals one and down here is the kaiser window with alpha equals three so as you can see here yeah the i don't know if it really shows up in your screen or not but the main lobe of this guy is smaller than the main lobe of this guy but the ripple the side lobe of this guy is higher than the side lobe of this so as we changed the alpha from one to three which we did that trade off i just talked about um now here's uh here's an example of a low pass filter that was designed where we used the one dimensional kaiser window and in in this plot what you can see is the well here is the there's there's a three the the 3d visualization of the 2d frequency response and this is the contours of the frequency of the frequency response right how do we compute the contours it's just isocontours you cut it and find the points at which it crosses a certain level and looking at this and looking at that do you think this was a separable 2d kaiser window or circular asymmetric separable because it kind of has a squarish look to it by contrast if you look at the isocontour of the circular asymmetric one you see it's the end of circle it's good good circle right compare that with this okay and this is the circular symmetric 2d filter h of omega one omega two you can see you can detect the circles with your eyes even and this is the the separable one because it has its edges as you can see right there yeah sure i was just curious well i mean why would somebody make a point to make that like slight depression in the center and then that other like hump in the middle this one or the other one like that one right there for instance i mean it seems like if you want to make a little pass in the middle i mean where did why did someone do that why did why would somebody do that yeah they didn't want to do it on purpose it came it's it's the ripple it's the ripple of the the kaiser window in the middle you can't from an approximation theory point of view making the thing absolutely flat here and absolutely flat there it's not impossible you need to have a lot of terms that means that the f i offered to end up getting bigger and bigger each coefficient of f i offered is a knob the more knobs you have the more freedom that you have not to have these junk on top and at the bottom and uh so it's kind of like it's it's it's having given yourself more degrees of freedom always buys you better frequency responses but if you don't and you have a finite number of coefficients to play with this is kind of what you get i've absolutely a good point this is not by design it is by accident nobody nobody would wonder that's that's why that's why in the past and you want to bound your ripple delta p to be smaller if this is not no good for your application you make delta p to be point four zeros and i'm on five zeros and i'm on and you always have to be wary about applications where people tell you that you want to have a lot of zeros applications in real life where people say we want to have uh non-failure mode probability of 99.999 with seven nines after the decimal it's like well what are you trying to accomplish 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 save 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 we wear our work day by day stitch by stitch at dickies we believe work is what we're made of so whether you're gearing up for a new project or looking to add some tried and true work where to your collection remember that dickies has been standing the test of time for a reason the work where isn't just about looking good it's about performing under pressure and lasting through the toughest jobs head over to dickies.com and use the promo code work where 20 at checkout to save 20 percent on your purchase it's the perfect time to experience the quality and reliability that has made dickies a trusted name for over a century but nevertheless it's it's you can you can achieve those by having large a number of paths come back here and this is an example of a vast band pass filter using rectangular we're using separable windows and kaiser and this is the contours for it and you can see it's kind of squarish looking here in between all hell breaks loose because you're transitioning from this band to the other band uh and if you use circular symmetric again compare these contours especially in the middle with these contours they're much more circular okay um and this is the frequency response of a circular symmetric band pass versus being um acceptable and i'm going to show one last picture and that might clarify Chris's point a little bit so here's an original vega's picture when i was a student there were there were only like three pictures you could know four pictures you could process as an image processing student there was the IEEE lady which it's not even in this book but some of you have seen it she has this old style not i would i wouldn't even say 50s i'd say four or maybe 30s 1930s straight hair coming with a curl down on a straight hair coming i think the only woman in the class can you know the two women can understand what i'm talking about right it's really old i mean it's one of those old styles that it still never came back in fashion even in the 2000s or whatever and then there's the vegas picture and then there's the cameraman picture and uh what was the fourth one i was gonna say lena all right lena i forgot lena is the most uh is the most widely anyway so this was the vegas picture this is if you process it with a linear phase this is the original this process with the linear phase and this really happens if you process it with non-linear phase if you can just slightly zoom back okay um no i just want these two to be shown as big as possible not yeah zoom in uh okay great i think that the point gets to guess you know if you have the book look at 4.1 and jaylin as well so this kind of shows you the example of of processing images with the linear phase versus non-linear phase okay what is the between a and b because that's the difference between zero and linear phase right no no it was the original oh is original okay b is just applying uh in this case he does zero phase there's there's no difference between zero phase and linear phase by the way so if i if i do zero phase it's i've gone an extramental and making the phase actually zero but zero phase and linear phase are just as good because it's the derivative of the phase remember d phi omega d omega that's delay right the derivative of phase of the Fourier transform that's the delay of that filter and you want the delay to be constant no matter what the frequencies are because what that does it delays all the frequencies all the sinusoids of different frequencies the same amount so if their shift was this much before their distance is the same after the filter and process that preserve that's really what preserves the edges is that is that point clear okay so um so that's that's all i want to talk about in terms of um uh the window technique um next i wanted to quickly talk about frequency sampling uh again it's straightforward the extension of uh one dimension um i lost my pen again no this is good okay so frequency sampling technique and just just like it sounds you go to the frequency domain omega one omega two and you're going from minus pi to plus pi minus pi to plus pi um and uh let's say you want to design a low pass filter that passes these these bands and and stops all these other bands so it's it's one everywhere here and zero everywhere here so i'm going to say stop end is here and passband is here okay um and how do we do that well the way this thing works is you just sample the frequency domain at equally spaced points pretend as they're equally it's a grid and you take inverse uh DFT of it uh and and and you get a filter so so you sample this 0 0 0 and then 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 etc and then you have array of 0 0 0 1 you take the inverse DFT of it and you get it and let's say you sample it at a 10 by 10 point or let's just be realistic at 16 by 16 samples you take the inverse DFT of it you get it at 16 by 16 array and and that's it that's your filter is that a good technique or a bit and why that what's the frequency response of that filter that result in 10 by 10 FIR filter we just got what would be the frequency response of it well at these points that I sample it it would be exactly what those samples were and in between all hell breaks loose who knows what it does it could go up down ripple everything so so let me just write down the basic steps you sample the 2D Fourier space on a grid let's say m by m grid m by m equally spaced points and from Fourier theory you know that the signal that you get will have a DFT that add those samples will be what you force them to be but in between the samples so if I were to for example figure out what what if so if it's probably going to be 0 at this point at 0 at that point but the DFT in between these points here could be anything okay and then take inverse DFT to get the m by m FIR filter it's the equivalent of the 1D version where you start with a range of omega as a function of omega and you sample it out it means 0 and pi and take the inverse DFT in one dimension and let me just show you some examples of filters uh using that. So let's let's look at figures 4.10 through 4.11 in Jay Len's book so so here's what you get if you can zoom in please okay so so this is a frequency response from minus pi to pi minus pi to pi and I wanted to design a circularly symmetric low pass filter so the filled circle in the middle I'm gonna pass these these points I want to make it zero and this is a little bit more sophisticated I just explained that the he allows for a transition band you can allow for these points in the middle to be like 0.5 or something like that just to make your job easier you don't have to do that and after you do it here's a 15 so so after you do that this is the filter that you end up getting 15 by 15 let me see how many points is it yeah it's a 15 by 15 low pass filter this is the frequency respond you can see it has a hell of a lot of repoles and this is the contour plot for it well not really very not really very good it's not even as good as the windows design yep I'm just a little confused I thought we were so you're sampling the you create this grid of frequency samples and then you set some of them equal to one in the middle and some equal to zero on that so I mean isn't that going to be your frequency that's like your transfer function right no because I sampled the frequency respond at that my the samples are my frequency response add those samples will be exactly one will be exactly zero but in between the samples remember when I talk about frequency response h over mega one omega two omega one omega two are continuous variables I've only made samples of omega one omega two add just at those locations behave the way I wanted it to behave in between those that I didn't sample it goes to hell it could do anything and that's exactly what's here here add those samples it's exactly one and here it add those samples is zero it's between them that that things didn't go back which causes a ripple again omega one and i'll go to a real right so just because it's sort of like this just because I sampled the function at those points it didn't mean that in between those it's going to behave properly now if instead of doing 15 by 15 if I sampled it more finely let's say I did 30 by 30 this would look a lot better but what did I just do I made the size of my filter four times bigger um if I made a 60 by 60 that would be even better but now I have a wow 3600 point FIR filter that's terrible that's really big I mean have you got I forgot whether in the radon and the tomography homework that you just did they've done tomography oh then they've done the the phase reconstruction there you didn't have to do any filtering did you do any filtering and tomography one no not much you will get it some filtering matlab assignments and I mean most for example most filtering that you do for let's say sub-band image coding you want the number of tabs for your one-dimensional filters to be no more than five or ten and two-dimensional there no more than I don't know five by five or seven by seven you don't want to have so many tabs okay because the computation gets out 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 save 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 we wear our work day by day stitch by stitch a dickies we believe work is what we're made of so whether you're gearing up for a new project or looking to add some tried and true work where to your collection remember the dickies has been standing the test of time for a reason the work where isn't just about looking good it's about performing under pressure and lasting through the toughest jobs head over to dickies.com and use the promo code work where 20 at checkout to save 20% on your purchase it's the perfect time to experience the quality and reliability that has made dickies a trusted name for over a century and because yeah and and you can many of the tasks that you want to accomplish can be easily done if you if you if you didn't use the simple technique like frequency frequency sample but you should be aware that if you if you do that this this you get this kind of low quality filter and if you can put back the camera on and and similarly the same thing for for a band pass filter if you design a band pass filter using this technique you get all these ripples and bad stuff and this is a contour plus that you get using frequency sample but don't despair because we're going to talk about a slightly more powerful technique in in 2D unfortunately if you remember in 1D there was a there was a technique called the Proxima clone optimal filter design using grandma's exchange algorithm and all those fancy things and there was a theorem associated with that which said if you give me a set of specs then I can I can come up there's a unique filter with minimum number of taps that satisfies those those specs and and that it won't it won't go any lower than that minimum number of taps it was an excellent technique in 1D it essentially killed all the other research in one dimension which before that was highly concentrated on designing windows that's why there were so many windows and so many names of windows floating around so Proxima clone in 1972 came up with that one-dimensional optimal 1D filtered f/r filter design and just knocked that filled out no more papers on and filter design using windows unfortunately that result doesn't hold in 2D and once again it it's not surprising it has to do with fundamental theorem of algebra not holding out in 2D however my clone still came up with it with a technique called transformation it can be shown to be optimal but it's kind of a nice technique and I'll spend hopefully the rest of today wrapping it up so we don't have it doesn't have to still to next next week but let's let me just tell you what that is so 2D filters design I lost my pen again using transformation and just as the name implies we're going to transform a 1D filter into 2D so the basic idea is this you start with h of omega 1 and omega 2 and you say that's equal to h of omega with omega replaced by g of omega 1 and omega 2 okay or another way of saying it is h of omega 1 and omega 2 is h of omega where cosine omega is replaced by t of omega 1 and omega 2 and you'll see in the second why I call it cosine omega equals dad versus omega equals this they're all the same thing it's just it pops out easier so given that methodology the questions that come up is number one how to design t of omega 1 and omega 2 and number 2 how to design h of omega well how to design h of omega this part boy there's a lot of rich theory that allows us to do that there's optimal filter design that you can do that so really the basic the basic challenge challenge then becomes how to how to design this guy t okay so the first thing I want to say is once again I want to talk in talk for one minute about zero phase or linear phase because I want to end up with zero or linear phase filters right so first of all in in in one dimension how is it that how is why is it so so the the claim I want to make is this I want to say if if h of if my h of n the impulse response in in this is zero phase and if I impose certain condition on this guy t the final filter will also be zero phase so make h zero phase make t zero phase and h of omega 1 and omega 2 will automatically be zero phase so before I want to get before I get into that I like to make one other comment about one dimensional zero phase filters is it easy to design with our filters in 1d that are zero phase or linear phase extremely why what do we do in 1d to to make sure our filters are linear phase or zero phase exactly a symmetry condition is all that you need and I like to mention that because I have emphasized zero phase is so important in image process and yet if I don't tell you how to make the things zero phase or linear phase then you might be very uncomfortable and not be able to sleep tonight so let's remove that ambiguity here right away so so the question that that I want to ask is is the following how to make h of omega in 1d be zero phase is that an easy job or a hard cut and the answer is you can show that if the filter is zero phase in other words if I have an h of omega that's written as magnitude of h of omega times e to the j field omega right that means field omega is equal to zero for all omega or what does that mean that means that h of omega is equal to h complex conjugate of omega which means h of n is equal to h complex conjugate of minus n and furthermore if I assume that h of n has real coefficients not complex which is I'm dealing with real images and I don't want to have complex coefficient kind of filters that means h of n is equal to h of minus n so what does that boil down to is that zero phase in 1d implies and it's implied by h of n being h of minus n so if I just impose this symmetry condition on my one-dimensional tab filters boom my h of omega will be zero phase so in order to have in this transformation technique that I'm going to talk about in order for me to have a shot of designing h of omega 1 and omega 2 do I 2d filter to be zero phase automatic to begin with I'm going to start with an h of omega that's zero phase okay so coming back now to to to our filter design so assume h of omega is zero phase in other words h of n is equal to h of minus n and we assume h of n has two n plus one samples non-zero values okay so what what can I say well in general h of omega can be written as summation n from minus n to plus n of h of n e to the minus j omega n but now if I apply the zero phase constraint which makes the filter taps symmetric then I can write then I can pair up like h of 1 with h of minus 1 h of 2 with h of minus 2 and write this thing down as h of 0 plus summation n equals 1 to capital n of 2 h of n cosine oh my god here's the zero phase aspect of it coming in okay and I can now rewrite this this thing if you can roll up a little bit as summation over some other coefficients a of n cosine omega n where a is related to h and I make that a go n go from zero to n okay so you can easily see that you can write down the coefficients a in terms of h of 1 h of 2 h of 0 all of that junk I'm just introducing a new notation and now I'm going to make another jump and that is this is the summation from n equals zero to n of another set of coefficients b of n but power in terms in terms of powers of cosine omega I'm writing cosine omega n as sum of the powers of cosine omega and you all know how to do that right it is Chebyshev polynomials or Chebyshev whatever however you want to call this guy and well what do I just as a quick reminder you can write cosine 2 omega as cosine omega plus omega which is 2 cosine squared omega minus 1 then you can write cosine 3 omega as cosine omega plus 2 omega which is that you can write it as expand this out and you get a bunch of other stuff and then you can write it as 2 cosine cube omega minus cosine omega minus 2 1 minus cosine squared omega cosine omega so you can write down the bottom line the reason I could go from here to here is that you can write down cosine of multiple multiple integer values of omega omega n as sum of the powers of cosine omega and this is because of this relationship and we all we already used that in 1D to do our optimal filter design right and why do I want to write it like this well now now you can see why at the very beginning I want I wanted to write my transformation as cosine omega replaced by t of omega 1 omega 2 so now I can do the replacement from here to here I can just say h of omega 1 and omega 2 is h of omega with cosine omega replaced by t of omega 1 and omega 2 so now I can say that my h of omega 1 and omega 2 is summation from n equals 0 to n and now I'm going to replace this cosine omega with the t guy 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 save 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 we wear our work day by day stitch by stitch at dickies we believe work is what we're made of so whether you're gearing up for a new project or looking to add some tried and true work where to your collection remember that dickies has been standing the test of time for a reason the work where isn't just about looking good it's about performing under pressure and lasting through the toughest jobs head over to dickies dot com and use the promo code work where 20 at checkout to save 20% on your purchase it's the perfect time to experience the quality and reliability that has made dickies a trusted name for over a century t omega one and omega two whole thing to the power of n so that's my filter after the transformation and and what i propose is that if we make this guy t to be to be zero phase then because we also made h to be zero phase already we took advantage of that we took the benefits that if t is also zero phase you can easily show that h will become zero phase so let's just do that so can show and i'm not going to show it that if t of omega one and omega two is zero phase and if h of omega is zero phase which we assumed it was and we used that to get to this point then h of omega one and omega two will be zero phase and that's good that's that's very reassuring to know so now let's do a little kind of a um size argument suppose that t of omega one and omega two was itself a frequency response of another to the zero phase filter in fact it it has to be because we assume it's already zero phase so it's a frequency response of filter t of n one and n two and suppose t of n one and n two is two m plus one by two m plus one okay and we already know h of omega was two n plus one point so what can we say about the size of h well let's combine these things kind of together right let's write down t of omega one and omega two in terms of t of n one and n two what do we get well it's the t of omega one omega two is just a four-year transform of t of n one and n two so it's double summation for n and one ranging from minus m to plus m and n two ranging from minus m to plus m of e to the minus j omega one and one e to the minus j omega two and two so now i can plot this equation straight into this one that i had before into this guy instead of having t t of omega one and omega two i plug in this long expression down here so let's do that so what i get is h of omega one and omega two is the summation n equals zero sorry this is capital n there was a typo here the capital n of b of n and now i'm going to replace this t guy to the power of n with the expression i have here to the power of n which is double summation n one minus m to plus n and two minus m to plus m of t of n one and n two e to the minus j omega one and one e to the minus j omega two and two now staring at this thing what can you say about the size of h what's the h of omega one on omega two by definition is is the Fourier transform of the new filter where after the h guy e to the minus j omega one and one e to the minus j omega two and two what is the region of support of this h guy it is n one from where to where and n two from where to where well yeah i'll give you a chance to take a look at it let me see if i can get any answers from you guys well there's a power of n here this little n goes from zero to n and and so you you're going to have e to the j e to the minus j omega one n one n and n one can go from minus m to plus m and n can go from zero to capital n so what would be the powers that what would be the powers of e to the minus just on j omega one that i will experience yeah it goes all the way from minus n m to plus n m so this guy is a filter that's two n m plus one times two n m plus one so using this approach if if m was one which meant that t of n one and n two was just three by three and n was 10 which means my h of n was just a 21 point filter sorry a 21 point filter then putting those things together h of omega one h of n one and n two would be 21 by 21 point filter again which is which is large but the beauty of it if you will is that we managed to design a large filter by only designing a little two-dimensional filter t which is only three by three and then a regular one-dimensional filter so you can already imagine kind of what the steps are in in designing two-dimensional filters right so here here to sum it up to to to to design based on all of these things and roll up with so what would be the steps you would want to take in designing a 2d filter using this transformation technique well you so these are the steps you start you start with a set of specs um specs in 2d specifications in 2d and then you either choose or design this little filter t of n one and n two which is going to be no more than three by three at most five by five and then using this guy t transform the specs in your 2d into the specs for 1d filter h of omega in other words derive specs for h of omega from the specs in 2d in 2d for h of omega one and omega two and given the t you've already nailed them what t of n one and n two is either you chose it or you design it and i'll talk about it a little bit more how you design it so given that you know the t given you know the specs for h of omega one omega two you can come up with a set of specs for h of omega and now we're doing the classic thing transform problem we didn't know how to do to a problem we don't know how to do we know we have like a gazillion years of experience in designing optimal h of omegas so now so in other words we want to design omega s omega p delta s delta p four h of omega we want to come up with a set of specs for that once you have that you can now design h of omega or alternatively h of n let's say using the optimal filter design or in fact in matlab there's a remains exchange algorithm you can use etc and then when you're done with designing h of n you can combine h of n and t of n t of n one and n two to get of h of n one and n two and how do we do that well it's the thing we started off with h of omega one omega two is h of omega where we replace cosine omega with t of omega one and omega two and you might say well where does my cloud on coming to this where my cloud came out with a nice simple transformation technique a three by three kind of a filter that um that he initially used for all his designs but of course he he also came out with ways of designing t but just so that you have an idea here is the in particular so i still didn't tell you how to design the t guy or where the t comes from but um my cloud on transformation besides the technique itself there's also a particular t that he came out with which takes on the value half one fourth one eight one fourth one eight one fourth one eight one fourth one eight so this is it this here we have t of t or m one and two equals t of minus n one minus n two so it's zero phase fantastic and it also has four-fold symmetry these these are the same and these are the same so this is the kind of the transformation that my cloud started off with doing some of his filters um i guess i didn't finish this transformation technique so on wednesday i'm going to give you some examples of of using this transformation and other transformation and in designing actual 2d filters so since did you have the latest more work and the solutions can include so don't forget to take up all of these on your way out to the door and if you haven't handled in your homework please hand it in 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 save 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 we wear our work day by day stitch by stitch at dickies we believe work is what we're made of so whether you're gearing up for a new project or looking to add some tried and true work where to your collection remember the dickies has been standing the test of time for a reason the work where isn't just about looking good it's about performing under pressure and lasting through the toughest jobs head over to dickies.com and use the promo code work where 20 at checkout to save 20% on your purchase it's the perfect time to experience the quality and reliability that has made dickies a trusted name for over a century