Poisson-Disk Sampling Experiment - Part I
Poisson-Disk sampling is a nature-inspired method to collect spatially distributed samples from a {texture, scene, etc.} while avoiding aliasing (actually, it trades it aliasing for noise which is much less objectionable) in the sampled pattern. It is widely accepted as one of the best patterns to use for sampling, and was introduced to the field of computer graphics by Robert L. Cook in 1986. The basic idea is to choose random samples such that no two are closer than a fixed distance. Here are some illustrations from my experiments in matlab, and my interpretaions of how this thing actually works:-
1. Regular Grid: This is most basic sampling technique and I'm not sure if it's even used anymore. It just samples at regular grid points, resulting in a pattern as shown. fft2 of the pattern shows us that it is undesirable, because it produces high frequency peaks which will appear as aliasing in the output.
Spatial Domain
Frequency Domain
2. Jittered Grid: Here I perturb the sample positions from a grid randomly to generate a randomized sampling pattern. As can be seen, it is much better because there are no distinctive peaks in high frequencies (however, there is noise). This method seems to be the easiest to generate and provides sufficiently good results.
Spatial Domain
Frequency Domain
3. Poisson-Disk Sampling: This is a poisson-disk sampling pattern, generated by dart throwing (an exceptionally inefficient algorithm). Notice that the quality of patterns generated is good. Unlike jittering, there is no instance of samples being too close or too far -- they seem to be well distributed. Also notice that there is lesser high-frequency noise than a jittered grid (this is known as a blue-noise spectrum), which is good because it also reduces the noise in the sampled object. A much faster parallel implementation was provided by Li-Yi Wei in 2008, and should be used for any performance-sensitive application.
Spatial Domain
Frequency Domain
That's all for this time. Next time I will experiment with how a sampled image gets affected when using the three techniques.
I think there must be many variants of these techniques, but I can't seem to find enough time to study them.
Poisson-Disk sampling is a nature-inspired method to collect spatially distributed samples from a {texture, scene, etc.} while avoiding aliasing (actually, it trades it aliasing for noise which is much less objectionable) in the sampled pattern. It is widely accepted as one of the best patterns to use for sampling, and was introduced to the field of computer graphics by Robert L. Cook in 1986. The basic idea is to choose random samples such that no two are closer than a fixed distance. Here are some illustrations from my experiments in matlab, and my interpretaions of how this thing actually works:-
1. Regular Grid: This is most basic sampling technique and I'm not sure if it's even used anymore. It just samples at regular grid points, resulting in a pattern as shown. fft2 of the pattern shows us that it is undesirable, because it produces high frequency peaks which will appear as aliasing in the output.
Spatial Domain
Frequency Domain
2. Jittered Grid: Here I perturb the sample positions from a grid randomly to generate a randomized sampling pattern. As can be seen, it is much better because there are no distinctive peaks in high frequencies (however, there is noise). This method seems to be the easiest to generate and provides sufficiently good results.
Spatial Domain
Frequency Domain
3. Poisson-Disk Sampling: This is a poisson-disk sampling pattern, generated by dart throwing (an exceptionally inefficient algorithm). Notice that the quality of patterns generated is good. Unlike jittering, there is no instance of samples being too close or too far -- they seem to be well distributed. Also notice that there is lesser high-frequency noise than a jittered grid (this is known as a blue-noise spectrum), which is good because it also reduces the noise in the sampled object. A much faster parallel implementation was provided by Li-Yi Wei in 2008, and should be used for any performance-sensitive application.
Spatial Domain
Frequency Domain
That's all for this time. Next time I will experiment with how a sampled image gets affected when using the three techniques.
I think there must be many variants of these techniques, but I can't seem to find enough time to study them.
No comments:
Post a Comment