From: Joe Meenaghan <joe@ga...>  20090716 00:48:05
Attachments:
Message as HTML

Hey Guys, I was just wondering if there are specific mappings with regards the relationships between Gaussian kernel sizes, data set sizes, and number of passes. For example, what relationship exists between a 5x5 blur done over, say, a 1024x1024 texture and a 5x5 blur on a 512x512 texture of its downsampled data (assuming a simple average to downsample to the lower res)? Would the 5x5 over the lower res texture be approximately equivalent to a 9x9 at the higher res for example, or perhaps something along these lines? Similarly, what about running the 5x5 (or whatever size) N times in succession over the same texture? Is there a mapping that comes into play here, like, "X successive passes with a kernel of NxN is approximately equal to 1 pass with kernel of MxM"? If there are very specific mathematical relationships with proper formulae, that's great, but even if there aren't, I'd be just as happy with general rules of thumb, best practices based on experience, etc.. Thanks so much in advance for any insight you can provide! Joe Meenaghan The Game Institute joe@... 
From: Nicholas \Indy\ Ray <arelius@gm...>  20090716 01:58:17

On Wed, Jul 15, 2009 at 4:46 PM, Joe Meenaghan<joe@...> wrote: > Would the 5x5 over the lower res texture be approximately equivalent to a > 9x9 at the higher res for example, or perhaps something along these lines? No... That isn't how it works; A downsample shares very little in common with a blur. > Similarly, what about running the 5x5 (or whatever size) N times in > succession over the same texture? Is there a mapping that comes into play > here, like, "X successive passes with a kernel of NxN is approximately > equal to 1 pass with kernel of MxM"? I think the computation goes like this: Running two successive Gaussian blurs is equal to one Gaussian blur, who's distance is equal to the square root of the sum of the squares of the two blurs. Thus, for two 5x5 blurs: sqrt(5^2 + 5^2) ~= 7. Or two 5x5 blurs is about equal to a 7x7 blur. Nicholas "Indy" Ray 
From: Jon Watte <jwatte@gm...>  20090716 02:36:05

Nicholas "Indy" Ray wrote: > On Wed, Jul 15, 2009 at 4:46 PM, Joe Meenaghan<joe@...> wrote: > >> Would the 5x5 over the lower res texture be approximately equivalent to a >> 9x9 at the higher res for example, or perhaps something along these lines? >> > > No... That isn't how it works; A downsample shares very little in > common with a blur. > > Actually, they are both lowpass filters, so downsamplingplusupsampling is a form of blur. However, box filtering (the traditional downsampling function) isn't actually all that great at lowpass filtering, so it can generate aliasing, which a Gaussian filter does not. (AFAICR, the Gaussian filter kernel shares some properties with a sinc reconstruction kernel, and thus is "optimal" under certain conditions/assumptions, but details are hazy). Sincerely, jw  Revenge is the most pointless and damaging of human desires. 
From: Simon Fenney <simon.fenney@po...>  20090716 09:12:29

Jon Watte wrote: > Actually, they are both lowpass filters, so > downsamplingplusupsampling is a form of blur. However, box > filtering (the traditional downsampling function) isn't actually all > that great at lowpass filtering, so it can generate aliasing, which > a Gaussian filter does not. AFAICS a box filter won't "generate" aliasing, it's just that it's not very good at eliminating the high frequencies which cause aliasing. A Gaussian, OTOH, has better behaviour in this respect... > (AFAICR, the Gaussian filter kernel > shares some properties with a sinc reconstruction kernel, and thus is > "optimal" under certain conditions/assumptions, but details are > hazy). ...again, (and my recollection, too, is a bit hazy), the shape of a Gaussian filter in the frequency domain is, again, a Gaussian, so it's still going to let through some amount of illegally high frequencies. In order to stop that, one will probably need to make it a bit wider which, unfortunately, means it'll overfilter some of the legal frequencies you'd want to keep. A sinc filter, when mapped into the frequency domain, is a box and so has a hard cutoff of higher frequencies, which should be ideal. OTOH, I think that a box filter, when mapped into the frequency domain, looks a bit like a sinc, which is why it behaves so poorly. Cheers Simon 
From: Sam Martin <sam.martin@ge...>  20090716 10:13:57

I was typing a reply but Simon beat me to it! Some extra bits: You should think about reducing the sampling rate as a totally separate thing to any averaging/bluring that may also happen. When people say downsampling in computer graphics they usually mean a combination of averaging and reducing the sampling rate. You can 'downsample' simply by removing remove every other pixel, but this provides no defence against high frequencies aliasing. Small changes can have a large impact. For instance, downsampling by using the midpoints, as opposed to just adding up even and odd pixel pairs, approximates a Gaussian fairly well  particularly if you do it more than once. You can produce some very nice blurs by down+up sampling using this trick. Applying one filter then another is equivalent to convolving the two filters together first  so you can always reduce a series of filters down to a single filter (although this filter might be a lot larger!). You can google all the details, but this is a great starting point: http://www.dspguide.com/ And lastly, regardless of what the filters are, if you convolve several together the result will quickly start to look like a Gaussian anyway (known as the central limit theorem). Gaussians are like the home land all filters want to return to. Hope that helps, Sam Original Message From: Simon Fenney [mailto:simon.fenney@...] Sent: 16 July 2009 09:57 To: Game Development Algorithms Subject: Re: [Algorithms] Gaussian blur kernels Jon Watte wrote: > Actually, they are both lowpass filters, so > downsamplingplusupsampling is a form of blur. However, box > filtering (the traditional downsampling function) isn't actually all > that great at lowpass filtering, so it can generate aliasing, which > a Gaussian filter does not. AFAICS a box filter won't "generate" aliasing, it's just that it's not very good at eliminating the high frequencies which cause aliasing. A Gaussian, OTOH, has better behaviour in this respect... > (AFAICR, the Gaussian filter kernel > shares some properties with a sinc reconstruction kernel, and thus is > "optimal" under certain conditions/assumptions, but details are > hazy). ...again, (and my recollection, too, is a bit hazy), the shape of a Gaussian filter in the frequency domain is, again, a Gaussian, so it's still going to let through some amount of illegally high frequencies. In order to stop that, one will probably need to make it a bit wider which, unfortunately, means it'll overfilter some of the legal frequencies you'd want to keep. A sinc filter, when mapped into the frequency domain, is a box and so has a hard cutoff of higher frequencies, which should be ideal. OTOH, I think that a box filter, when mapped into the frequency domain, looks a bit like a sinc, which is why it behaves so poorly. Cheers Simon   Enter the BlackBerry Developer Challenge This is your chance to win up to $100,000 in prizes! For a limited time, vendors submitting new applications to BlackBerry App World(TM) will have the opportunity to enter the BlackBerry Developer Challenge. See full prize details at: http://p.sf.net/sfu/Challenge _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslis t 
From: Jon Watte <jwatte@gm...>  20090716 17:07:06

Simon Fenney wrote: > Jon Watte wrote: > > >> Actually, they are both lowpass filters, so >> downsamplingplusupsampling is a form of blur. However, box >> filtering (the traditional downsampling function) isn't actually all >> that great at lowpass filtering, so it can generate aliasing, which >> a Gaussian filter does not. >> > > AFAICS a box filter won't "generate" aliasing, it's just that it's not > very good at eliminating the high frequencies which cause aliasing. A > Gaussian, OTOH, has better behaviour in this respect... > > Yes, what I meant by that was that the process of box filtering plus downsampling can generate aliasing. As can Gaussian plus downsampling if your kernel isn't wide enough :) With filters, it's all about the response curve  you'll need a significantly wide Gaussian to get below the 61 dB quantization noise floor of an 8 bpp RGB image for any possible aliasing. > > ...again, (and my recollection, too, is a bit hazy), the shape of a > Gaussian filter in the frequency domain is, again, a Gaussian, so it's > still going to let through some amount of illegally high frequencies. In > All filters do that, because there are no perfect brick wall filters. You have design a filter that rejects enough of the aliasing that you care about, while retaining as much as possible of the signal that you want. I think we can agree that a box filter is pretty far from the optimal choice for the more demanding cases :) > A sinc filter, when mapped into the frequency domain, is a box and so > has a hard cutoff of higher frequencies, which should be ideal. > > That would be an infinitely wide sinc. In most cases, though, you end up with only one or two lobes of the sinc, which makes it significantly less than ideal box shape :( Not to mention that all this is defined for static processes, but texture images are, at best, only locally static. The classic transientresponsevsaliasing problem, where the answer is that you probably want to oversample by more than Nyquist suggests you should need to (or why a 48 kHz converter is surprisingly better than a 44.1 kHz converter for the 2020k audible range  but I think we're getting topic skew here :) Fabian also mentioned Multirate Filter Banks  in the audio case, the equivalent is the polyphase filter AFAICR, and that's used quite heavily in real time, because it actually saves cycles compared to first filtering and then decimating. I think a properly implemented multirate filter in a pixel shader might actually give you very good bang for the cycle buck! Sincerely, jw  Revenge is the most pointless and damaging of human desires. 
From: Fabian Giesen <f.giesen@49...>  20090716 17:30:05

> Fabian also mentioned Multirate Filter Banks  in the audio case, the > equivalent is the polyphase filter AFAICR, and that's used quite heavily > in real time, because it actually saves cycles compared to first > filtering and then decimating. I think a properly implemented multirate > filter in a pixel shader might actually give you very good bang for the > cycle buck! The basic idea behind polyphase filters is that you're doing downsample(conv(a,b),2), where conv(a,b) is the convolution of a and b and downsample is the "elementary" downsample operator (point sampling  just throw away every second sample). So since you're ignoring every second sample generated by your gaussian filter anyway, there's not much point computing it in the first place. The math behind polyphase filters are the specifics of how to do just that. It's basically splitting both the signal and filter into "odd" and "even" parts and then writing the result as a sum of convolutions of these  but it's been a while, so don't ask me about the details :) Multirate filter banks are the filter bank equivalent of discrete wavelet transforms, really  you split into low and high frequency parts, then do an extra decomposition on the low level part of the result, and so on. Each level has half the sampling rate of the previous, hence the "multirate". Nobody forces you to just use exactly 2 filters per level though. For blurring, you just don't care about the high frequency parts, so you throw them away and assume they're all 0 during reconstruction. The result is a cascade of the form downsample > downsample > ... > upsample > upsample If you want to do it correctly, the upsampling filter should match your downsampling filter. If you don't and you're cheap :), you just use the bilinear upsampler you get for free. Cheers, Fabian "ryg" Giesen 
From: Fabian Giesen <f.giesen@49...>  20090716 18:04:34

Fabian Giesen wrote: >> Fabian also mentioned Multirate Filter Banks  in the audio case, the >> equivalent is the polyphase filter AFAICR, and that's used quite heavily >> in real time, because it actually saves cycles compared to first >> filtering and then decimating. I think a properly implemented multirate >> filter in a pixel shader might actually give you very good bang for the >> cycle buck! > > The basic idea behind polyphase filters is that you're doing > downsample(conv(a,b),2), where conv(a,b) is the convolution of a and b > and downsample is the "elementary" downsample operator (point sampling  > just throw away every second sample). So since you're ignoring every > second sample generated by your gaussian filter anyway, there's not much > point computing it in the first place. The math behind polyphase filters > are the specifics of how to do just that. [..] And, after thinking about this some more on the way home: you shouldn't care :). To elaborate: most of the math in signal processing deals with signals as a whole. This gives you a whole bunch of very powerful tools and notations (Convolutions, Fourier Transforms, z Transform) but makes some basic samplebysample operations such as downsampling (or decimating as it's usually called in DSP) a bit inconvenient in terms of notation. The whole polyphase filter stuff is mainly about writing the relevant index shuffling down in a concise and neat way so you can "bubble up" convolutions. However, all of this is a nonissue in graphics. Pixel shaders give you cheap pointwise evaluations at no cost. If you want only every second pixel, then render a quad half the size in each direction. In short, the optimal "polyphase" implementation of a 5x5 Gaussian followed by a 2:1 downsample in both directions is just to render to the smaller rendertarget directly with the 5x5 Gaussian Pixel shader and the correct texture coordinates. So all you have to do is use that pixelshader instead of a cheap onetexturesample pixelshader that uses the bilinear filtering HW to average groups of 2x2 pixels together. It's more expensive though, and if you want a quarter of the size in each direction, you *do* have to do this twice  or, alternatively, use a larger gaussian during downsampling. Cheers, Fabian "ryg" Giesen 
From: Jon Watte <jwatte@gm...>  20090716 19:27:15

Fabian Giesen wrote: > However, all of this is a nonissue in graphics. Pixel shaders give you > cheap pointwise evaluations at no cost. If you want only every second > pixel, then render a quad half the size in each direction. > > But that cheap sample is using a pretty crappy box area filter for its sampling, so it is not aliasing free. > In short, the optimal "polyphase" implementation of a 5x5 Gaussian > followed by a 2:1 downsample in both directions is just to render to the > smaller rendertarget directly with the 5x5 Gaussian Pixel shader and the > correct texture coordinates. > > But originally the problem wasn't just downsampling  it was using some combination of downsampling, filtering and upsampling to approximate the result of a bigger Gaussian blur, but making it faster. Sincerely, jw  Revenge is the most pointless and damaging of human desires. 
From: Fabian Giesen <f.giesen@49...>  20090716 21:39:11

Jon Watte wrote: > Fabian Giesen wrote: >> However, all of this is a nonissue in graphics. Pixel shaders give you >> cheap pointwise evaluations at no cost. If you want only every second >> pixel, then render a quad half the size in each direction. > > But that cheap sample is using a pretty crappy box area filter for its > sampling, so it is not aliasing free. At no point is this using a box filter. I'll try to make a bit clearer what's going on: Mathematically, you perform downsampling by first lowpass filtering your signal and then throwing away every Nth sample. The latter is operation called Ndecimation and the corresponding operator is typically written as a downarrow with N after it. If you just do the decimation without any lowpass filtering, you run into trouble because of aliasing; hence the lowpass filter, which is there to remove any frequencies higher than the new nyquist frequency. Afterwards, there's (near enough) nothing there in the higher frequencies that could alias; that's the whole point. Fastforward to 2D downsampling. Similarly, you want to first run a lowpass filter (the 5x5 Gauss) and then run a decimation on the image (=copying it into a rendertarget half the size in both directions with nearest neighbor filtering). Again, running just the decimation step will alias badly. And again, the lowpass filter is there precisely to get rid of any toohigh frequencies that cause aliasing. Anyway, clearly you're doing redundant work during the filtering here, since you only keep every fourth pixel. This is where the polyphase filters come in; polyphase filters are just a way of avoiding this redundant computation, formulated in terms of convolutions of decimated versions of both the signal and the filter. But the details don't matter, since we don't have to write it in terms of convolutions here! That was the whole point of my previous mail. There's no point computing the 5x5 Gaussian convolution at full res only to throw away 3 out of every 4 resulting pixels. You can just render into a quarterarea rendertarget directly. The rest stays exactly the same  you're still using a gaussian lowpass filter, nothing has changed. You just don't compute anything you never use in the first place. > But originally the problem wasn't just downsampling  it was using some > combination of downsampling, filtering and upsampling to approximate the > result of a bigger Gaussian blur, but making it faster. Yeah. Once you get to your lower resolution, you just execute your "main" blurring filter, which works exactly as it would've before except it's got a lot less pixels to process. The usual techniques apply here  using the bilinear filtering HW to get "4 samples for the price of one", using two 1D passes instead of one large 2D pass for seperable filters, etc. The only difference is that you're running on a lowerres version of the image, and to answer the OPs question, yes, a guassian with standard deviation sigma running on the lowerres version (say a downsampling factor of 2 in each dimension) is roughly equivalent to a gaussian with standard deviation 2*sigma on the fullres version. You will still get jarring aliasing artifacts if you take too many shortcuts during downsampling though; perhaps the most obvious (and rather common) artifact being that small thin objects start flickering in the blurred version (that's what happens if you just throw the samples away without doing a small lowpass first!). If you're really going for the full multirate filterbank approach, you have to use a good filter during the upsampling pass too. But in practice, the bilinear filter really is good enough with the relatively blurry signal you usually have at this point; I've never noticed significant improvements using a better upsampler. (Unlike the downsampler, where it really *does* help). Kind regards, Fabian "ryg" Giesen 
From: Jon Watte <jwatte@gm...>  20090716 21:59:36

Fabian Giesen wrote: > versions of both the signal and the filter. But the details don't > matter, since we don't have to write it in terms of convolutions here! > > That was the whole point of my previous mail. There's no point computing > the 5x5 Gaussian convolution at full res only to throw away 3 out of > Oh, yeah, of course. I misunderstood your meaning, because the point was too obvious :) So, yes, the downsampling operation is, at the end, a single pass (assuming you do a 2D Gaussian in a single pass), and it samples some number of samples from the source, per output pixel. I guess even considering the "filter THEN discard" implementation is just too alien for those of us who have been actually implementing these things for so long that the details blend with memories of college beer bashes in the distant past... Sincerely, jw  Revenge is the most pointless and damaging of human desires. 
From: Olivier Galibert <galibert@po...>  20090716 20:29:48

On Thu, Jul 16, 2009 at 09:56:58AM +0100, Simon Fenney wrote: > Jon Watte wrote: > > > Actually, they are both lowpass filters, so > > downsamplingplusupsampling is a form of blur. However, box > > filtering (the traditional downsampling function) isn't actually all > > that great at lowpass filtering, so it can generate aliasing, which > > a Gaussian filter does not. > > AFAICS a box filter won't "generate" aliasing, it's just that it's not > very good at eliminating the high frequencies which cause aliasing. A > Gaussian, OTOH, has better behaviour in this respect... Aren't we talking about graphics here? Vision is area sampling, making box filters perfect for integer downsampling. It's sound that is point sampling and hence sensitive to high frequency aliasing. OG. 
From: Simon Fenney <simon.fenney@po...>  20090717 10:50:50

Olivier Galibert wrote: > On Thu, Jul 16, 2009 at 09:56:58AM +0100, Simon Fenney wrote: >> Jon Watte wrote: >> >>> Actually, they are both lowpass filters, so >>> downsamplingplusupsampling is a form of blur. However, box >>> filtering (the traditional downsampling function) isn't actually all >>> that great at lowpass filtering, so it can generate aliasing, which >>> a Gaussian filter does not. >> >> AFAICS a box filter won't "generate" aliasing, it's just that it's >> not very good at eliminating the high frequencies which cause >> aliasing. A Gaussian, OTOH, has better behaviour in this respect... > > Aren't we talking about graphics here? Vision is area sampling, > making box filters perfect for integer downsampling. It's sound that > is point sampling and hence sensitive to high frequency aliasing. > > OG. Oh, I agree that there is a difference between what is 'best' for audio and graphics** but a box filter is far from an ideal way of downsampling graphics. I had a test image which was rendered with 10k samples per pixel but downfiltered*** using a box filter. The amount of aliasing surprised people. To show why a box is inadequate, as a thought experiment, *temporarily* consider the pixels as little squares (apologies to Alvy Ray Smith), and draw, say, a 1/8th pixel wide, *nearly* horizontal white line on a black background. Now imagine antialiasing it with a box filter. Now consider either animating the line, shifting it vertically by a fraction of a pixel per frame (and watch it jump), OR alternatively just consider a static frame. Assuming we do the latter, start from a point where the line crosses from one scanline into the next and run along the row to the next crossing. With the box filter, except for the areas where the line actually crosses the pixel boundaries, there will be a large number of pixels with exactly the same intensity. AFAICS, your brain expects to see more variation as the line sweeps across the pixels. Simon ** I have my own hypothesis on what is the root cause of this difference which is being hotly debated here in our research office. I now just need to install a better mathematical brain in my head to prove it :) ***In a linear colour space. This is V. important. 
From: Sam Martin <sam.martin@ge...>  20090717 13:16:44

I'm not sure I quite understand what you mean by antialiasing in your experiment? If you have a line which you rasterise using the usual point sampling, you will immediately produce aliasing (jaggies). Blurring the result with any filter may make the output more acceptable  and some filters may be more pleasant any others  but it doesn't remove the aliasing. It just reduces the objectional high frequencies. To remove the aliasing completely you can't blur after sampling*. You'd need to rasterise the line by doing the integral over each pixel properly, rather than point sample. This will produce an aliasfree result, but isn't exactly easy in general :). There are further details here though. When working with a pixelbasis we aren't in exactly the same territory as when we pointsample. There is a more general theory of sampling worked out largely by Papoulis and another dude I forget. The concepts of band limited signals and the reconstruction filters change as your basis changes. Cheers, Sam * In general  but using blue noise can help push the aliasing into high frequencies which helps. Original Message From: Simon Fenney [mailto:simon.fenney@...] Sent: 17 July 2009 11:51 To: Game Development Algorithms Subject: Re: [Algorithms] Gaussian blur kernels Olivier Galibert wrote: > On Thu, Jul 16, 2009 at 09:56:58AM +0100, Simon Fenney wrote: >> Jon Watte wrote: >> >>> Actually, they are both lowpass filters, so >>> downsamplingplusupsampling is a form of blur. However, box >>> filtering (the traditional downsampling function) isn't actually all >>> that great at lowpass filtering, so it can generate aliasing, which >>> a Gaussian filter does not. >> >> AFAICS a box filter won't "generate" aliasing, it's just that it's >> not very good at eliminating the high frequencies which cause >> aliasing. A Gaussian, OTOH, has better behaviour in this respect... > > Aren't we talking about graphics here? Vision is area sampling, > making box filters perfect for integer downsampling. It's sound that > is point sampling and hence sensitive to high frequency aliasing. > > OG. Oh, I agree that there is a difference between what is 'best' for audio and graphics** but a box filter is far from an ideal way of downsampling graphics. I had a test image which was rendered with 10k samples per pixel but downfiltered*** using a box filter. The amount of aliasing surprised people. To show why a box is inadequate, as a thought experiment, *temporarily* consider the pixels as little squares (apologies to Alvy Ray Smith), and draw, say, a 1/8th pixel wide, *nearly* horizontal white line on a black background. Now imagine antialiasing it with a box filter. Now consider either animating the line, shifting it vertically by a fraction of a pixel per frame (and watch it jump), OR alternatively just consider a static frame. Assuming we do the latter, start from a point where the line crosses from one scanline into the next and run along the row to the next crossing. With the box filter, except for the areas where the line actually crosses the pixel boundaries, there will be a large number of pixels with exactly the same intensity. AFAICS, your brain expects to see more variation as the line sweeps across the pixels. Simon ** I have my own hypothesis on what is the root cause of this difference which is being hotly debated here in our research office. I now just need to install a better mathematical brain in my head to prove it :) ***In a linear colour space. This is V. important.   Enter the BlackBerry Developer Challenge This is your chance to win up to $100,000 in prizes! For a limited time, vendors submitting new applications to BlackBerry App World(TM) will have the opportunity to enter the BlackBerry Developer Challenge. See full prize details at: http://p.sf.net/sfu/Challenge _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslis t 
From: Simon Fenney <simon.fenney@po...>  20090717 13:59:12

Sam Martin wrote: > I'm not sure I quite understand what you mean by antialiasing in your > experiment? Sorry, I thought that was obvious from the context :( Pragmatically, I meant take NxN samples per pixel, apply the (trivial) weighting due to a box filter (i.e. 1/N^2), and either choose a "large enough" N or take the limit as N>infinity. The latter should then be your integral below. > To remove the aliasing completely you can't blur after sampling*. > You'd need to rasterise the line by doing the integral over each > pixel properly, rather than point sample. This will produce an > aliasfree result, but isn't exactly easy in general :). I wasn't intending it to be easy :). I just wanted to show that a box filter is not ideal. Cheers Simon 
From: Sam Martin <sam.martin@ge...>  20090718 09:31:33
Attachments:
Message as HTML

Yeah, I hit send a bit quickly on this one. It might convey the rough idea, but I can poke holes in it already and need to actually bottom out the maths once and for all. It might take a bit of time, but if I complete it I'll write it up. We had torrential rain in Cambridge (UK) yesterday. The rear entrance to our office is slightly underground. A submerged pump either broken down or was blocked causing the area to suddenly fill up with water and pour under the back door. Half the team bailed the water out while the other half rescued all the equipment. Some carpet destroyed, but otherwise we're fine! Lesson learnt: never put your UPS on the bottom rung of your server rack. ta, Sam Original Message From: Sam Martin [mailto:sam.martin@...] Sent: Fri 17/07/2009 17:10 To: Game Development Algorithms Subject: Re: [Algorithms] Gaussian blur kernels Thanks, that's clearer. I think there's an extra detail here that might explain things. Warning: this contains some handwavey maths. Let's imagine for a second that the space your original line lives in is some real domain, R^2. Instead of doing the integration as we did before we apply (convolve with) a box filter and produce a new function, also in R^2. This would look like a blurry line. Note that it doesn't look like the result we got with the projection into the pixel basis. It would instead look a bit like the bokeh effect you get on a camera, but square. If we now *pointsample* this new signal we could produce a nice looking reconstruction with a pixel basis. I believe (subject to resolving some further fiddly details) the issues with the previous solution will have gone away  I think. No integration perpixel was required this time. We had already bandlimited the signal with the previous continuouslyapplied box filter. Incidentally, I believe we could also perfectly reconstruct the R^2 blurry line from the pointsampled pixel basis, but I'm not sure exactly what the reconstruction filter would be, and whether it requires the box filter to be twice the size of the original pixel or not. It's one of those things I've wanted to find out for a while, but the maths is a bit heavy. Eek. Have to go. Office is flooding with water. Ta, Sam Original Message From: Simon Fenney [mailto:simon.fenney@...] Sent: 17 July 2009 14:59 To: Game Development Algorithms Subject: Re: [Algorithms] Gaussian blur kernels Sam Martin wrote: > I'm not sure I quite understand what you mean by antialiasing in your > experiment? Sorry, I thought that was obvious from the context :( Pragmatically, I meant take NxN samples per pixel, apply the (trivial) weighting due to a box filter (i.e. 1/N^2), and either choose a "large enough" N or take the limit as N>infinity. The latter should then be your integral below. > To remove the aliasing completely you can't blur after sampling*. > You'd need to rasterise the line by doing the integral over each > pixel properly, rather than point sample. This will produce an > aliasfree result, but isn't exactly easy in general :). I wasn't intending it to be easy :). I just wanted to show that a box filter is not ideal. Cheers Simon   Enter the BlackBerry Developer Challenge This is your chance to win up to $100,000 in prizes! For a limited time, vendors submitting new applications to BlackBerry App World(TM) will have the opportunity to enter the BlackBerry Developer Challenge. See full prize details at: http://p.sf.net/sfu/Challenge _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslis t  Enter the BlackBerry Developer Challenge This is your chance to win up to $100,000 in prizes! For a limited time, vendors submitting new applications to BlackBerry App World(TM) will have the opportunity to enter the BlackBerry Developer Challenge. See full prize details at: http://p.sf.net/sfu/Challenge _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist 
From: Sam Martin <sam.martin@ge...>  20090717 16:11:52

Thanks, that's clearer. I think there's an extra detail here that might explain things. Warning: this contains some handwavey maths. Let's imagine for a second that the space your original line lives in is some real domain, R^2. Instead of doing the integration as we did before we apply (convolve with) a box filter and produce a new function, also in R^2. This would look like a blurry line. Note that it doesn't look like the result we got with the projection into the pixel basis. It would instead look a bit like the bokeh effect you get on a camera, but square. If we now *pointsample* this new signal we could produce a nice looking reconstruction with a pixel basis. I believe (subject to resolving some further fiddly details) the issues with the previous solution will have gone away  I think. No integration perpixel was required this time. We had already bandlimited the signal with the previous continuouslyapplied box filter. Incidentally, I believe we could also perfectly reconstruct the R^2 blurry line from the pointsampled pixel basis, but I'm not sure exactly what the reconstruction filter would be, and whether it requires the box filter to be twice the size of the original pixel or not. It's one of those things I've wanted to find out for a while, but the maths is a bit heavy. Eek. Have to go. Office is flooding with water. Ta, Sam Original Message From: Simon Fenney [mailto:simon.fenney@...] Sent: 17 July 2009 14:59 To: Game Development Algorithms Subject: Re: [Algorithms] Gaussian blur kernels Sam Martin wrote: > I'm not sure I quite understand what you mean by antialiasing in your > experiment? Sorry, I thought that was obvious from the context :( Pragmatically, I meant take NxN samples per pixel, apply the (trivial) weighting due to a box filter (i.e. 1/N^2), and either choose a "large enough" N or take the limit as N>infinity. The latter should then be your integral below. > To remove the aliasing completely you can't blur after sampling*. > You'd need to rasterise the line by doing the integral over each > pixel properly, rather than point sample. This will produce an > aliasfree result, but isn't exactly easy in general :). I wasn't intending it to be easy :). I just wanted to show that a box filter is not ideal. Cheers Simon   Enter the BlackBerry Developer Challenge This is your chance to win up to $100,000 in prizes! For a limited time, vendors submitting new applications to BlackBerry App World(TM) will have the opportunity to enter the BlackBerry Developer Challenge. See full prize details at: http://p.sf.net/sfu/Challenge _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslis t 
From: Jorge Rodriguez <jrodriguez@ma...>  20090718 02:33:36
Attachments:
Message as HTML

On Fri, Jul 17, 2009 at 12:10 PM, Sam Martin <sam.martin@...>wrote: > Eek. Have to go. Office is flooding with water. > ?  Jorge Rodriguez 
From: Robin Green <robin.green@gm...>  20090720 06:25:25

On Fri, Jul 17, 2009 at 7:06 PM, Jorge Rodriguez<jrodriguez@...> wrote: > On Fri, Jul 17, 2009 at 12:10 PM, Sam Martin <sam.martin@...> > wrote: >> >> Eek. Have to go. Office is flooding with water. > > ? Yeah. That's, like, so off topic. Moderator!  R. 
From: Jon Watte <jwatte@gm...>  20090717 16:11:53

Simon Fenney wrote: > Oh, I agree that there is a difference between what is 'best' for audio > and graphics** but a box filter is far from an ideal way of downsampling > graphics. I had a test image which was rendered with 10k samples per > pixel but downfiltered*** using a box filter. The amount of aliasing > surprised people. > Didn't we discuss this like three years ago, in the context of "what are textures, really?" Once you get into those details, you start having to make assumptions about what a sample is. Is it a point sample of a bandlimited function? Is it an area average for a picture sensor? If so, what is the shape of that area filter? Sincerely, jw  Revenge is the most pointless and damaging of human desires. 
From: Fabian Giesen <f.giesen@49...>  20090716 09:39:53

>> No... That isn't how it works; A downsample shares very little in >> common with a blur. > > Actually, they are both lowpass filters, so > downsamplingplusupsampling is a form of blur. However, box filtering > (the traditional downsampling function) isn't actually all that great at > lowpass filtering, so it can generate aliasing, which a Gaussian filter > does not. (AFAICR, the Gaussian filter kernel shares some properties > with a sinc reconstruction kernel, and thus is "optimal" under certain > conditions/assumptions, but details are hazy). All "practically implementable" downsampling filters cause some degree of aliasing, including sinc; the problem is that sinc has infinite support and decays quite slowly (as 1/x), so you have to use a windowing function: either do it explicitly with a good windowing function or implicitly choose a box window by just stopping the summation at some point. Anyway, the problem with sinc is that it's very "ringy". Windowing functions help a bit, but it's still very obvious when you have highcontrast edges. Text on solid background is a good example  with sinc and other filters with a very steep frequency response, you can see "wavefronts" emanating from the edges of characters. It's a continuum  the "simple" filters (box, triangle etc.) have no ringing but exhibit serious aliasing, sinc and other "good" lowpass filters (in terms of frequency response) have neglegible aliasing and tons of ringing. Gaussians are smack in the middle  they're allpositive so there's no ringing and they have a decent frequency response. As for the original question, you can build quite good 2D lowpass filters out of gaussians and downsampling, as long as you downsample *after* lowpass filtering. One example would be 5x5 Gaussian => 2x Downsample in both directions => 5x5 Gaussian => 2x Downsample in both directions => (more Gaussian blurs) => Upsample again. The result is not a gaussian kernel, but it "looks close enough". It's still a lot more expensive than the more usual downsample then blur, since you do the gaussian blur on a lot more pixels. What most people do for realtime appplications is just do the downsample first anyway, live with the aliasing, and do something else with the milliseconds of GPU time saved. :) Anyway, if you care for it, you can even do the downsample/filter sequence "perfectly", in the sense that it really does give you the exact filter you want: look up Multirate Filter Banks. But again, nobody uses this for realtime applications, or at least I've never seen it. And of course, to do it properly, you need a better upsampling filter than bilinear too... Kind regards, Fabian "ryg" Giesen 