Slashdot Mirror
New Sampling Techniques Make Up For Lost Data
An unnamed reader writes: "Professors at Vanderbilt and the University of Connneticut have published a non-uniform sampling theory that could yield better quality digital signals than the standard Uniform sampling techniques pioneered by Shannon at Bell Labs.
The Vanderbilt press release and link to the published paper can be found here."
The paper does not seem that new. It basically is using more modern methods of wavelets and an adaptive filter to deconstruct digital samples. This does not differ too much from current JPEG encoding or MP3 encoding. Such techniques have been used in control systems for a while. For that matter, non-uniform sampling has been in use for a while, for example the telephone system (which the article implied used uniform sampling). The telephone system samples using a uLaw algorithm, though it does occur at regular sample intervals.
Actually this paper won't really make a whole big difference in compression any time soon. It's all about solving the problems that come up when you have a bunch of samples that aren't evenly spaced (that whole 'non-uniform' thing in the title), which is not really an issue for digital images, audio, or video, since the conditions for sampling those things are pretty easy to control. It does have some potential to improve algorithms for error correcting noisy signals or filling in dropped packets from a streaming signal.
Could we use non-uniform sampling techniques for these forms of media in the first place? Could be interesting. Jittered sampling tends to mask visual artifacts (anti-aliasing); same could be true for audio. Their techniques are supported by wavelet transforms, which can get some great compression anyways. Maybe Creative will bring us the SBLiveNU, with on-the-fly variable sample rates from 1-96 khz?
In fact, you're not limited by the Nyquist frequency when you are sampling non-uniformly, so it has some strengths in that respect. However, it has to be more to it than this for it to be news. Can anybody who understands this better than I provide any insights?
Employee of Inrupt, Project Release Manager and Community Manager for Solid
About 7 years ago, I was involved in a research project, trying to use video teleconferencing and doctors for remote diagnosis of patients.
We found that jpeg compression of images made medical diagnosis unreliable. Hairline fractures in x-rays are exactly the kind of small details that tend to get washed away in 'lossy' compression, and the banding caused can lead to false assumptions as well.
The article suggests that this is still a lossy compression with small amounts of data loss. I know Doctors that would take that admission as a condemnation of the technique.
If it is possible to use these mathematics techniques to replace all of the unknown parts of an image, then why not resize the image a few times larger than the original and save the random parts of it? This would allow the algorithms to fill in even more detail to each image relative pixel. Upon resizing the image to 2x the original size, you would find much better clarity and precision than just resizing the image without.
On a side note, you could apply random color-relative noise on to the entire zoomed image before you save the random parts, then it might pick up the slack of the algorithm placing the same bordering colors over the unknown pixels.
If they consider digital music captured with this set of algorithms near-perfect, then near-perfect zooming is just around the corner.
There are already many other methods for reconstructing functions from sparse, non-uniformly sampled data, so this paper doesn't solve an unsolved problem. Rather, it provides one more solution under a set of assumptions that are mathematically a bit more like those of the original sampling theorem.
Will it be useful? That's hard to tell at this point. I think it will take a lot more work to figure out whether this method is any better than existing methods on real-world problems, whether its application can be justified in real problems, and whether it leads to algorithms that are practical. It may also turn out that the method is closely related to methods already in use in other fields; for example, the kinds of function spaces they study have received some attention in neural networks, but the authors cite no papers from that work and may not be aware of it.
From what I've read, some people seem to be thinking this is some kind of "magic bullet". For example, one comment, which emanated stupidity, was titled something like, "Infinite Zooming" and the implication of the post was that it might be possible with this method to "zoom in" on an image and accurately reconstruct the image. In other words, the idea is you could zoom in on a tiny head on a photograph and accurately reconstruct all of the details.
This, my friends, is complete nonsense. You cannot zoom in on an image and accurately reconstruct further details. To imply that this is possible is to imply that you can add accurately representative data where there was none before.
As for "zooming technology" it is possible to better reconstruct a zoomed-in image, though not any more accurately. For example, when I go into MS Paint and zoom in, it simply blows up all the pixels as larger blocks. This clearly is not good. You could create some kind of algorithm to determine the "shapes" of sharp edges, as well as where gradients where, and scale those up when zooming in...for example, small a circle can be composed of four pixels -- such a technology would scale this up, not as four very large blocks, but as a circle.
But this involves assumptions about what the original pattern was representative of? Was it representative of a circle, or of four large blocks seen from a distance? So you're not really adding data, but just attempting to "zoom in" on an image "better" based on a set of good assumptions which generally work.
Such a thing could be accomplished. Indeed, it already has been accomplished -- in us. When we look at a small photograph and want to draw a poster from it, we don't draw a large, blocky, pixelated image. We are able to tell what things -- such as frecles -- are details to be scaled up in our drawing; what things are gradients -- such as a dark to light gradient going from the near to the far side of a forehead -- to be scaled up and gradiated; and what are sharp borders, to kept sharp -- such as the sides of one's face.
However, even this amazing system we have of reconstructing larger images from smaller one's cannot add detail where there is none. If a woman is freckled with tiny freckles, they won't be visible from 10 feet away; a picture taken from that distance won't show them, and if we wanted to make a portrait of her head based on that picture, we wouldn't know to add freckles.
social sciences can never use experience to verify their statemen
I have a question/theory about nonuniform sampling rates. Okay, sticking with a 44kHz sample rate, will you hear the differeces between 8, 16, and 24 bit samples? Yes, of course. It's common in digital audio to use 16 bit samples to save space, not because it's the ultimate sample size. (While it's arguable the 44kHz rate side of the equation is pretty darn good.) It's subjective and some ears don't need any "more" audio information to be happy, but I see the choice of sample size as more of a variable than the "provable" sufficient rate for 20kHz audio cutoff behing 44kHz. All I'm saying is that there is potentially audible information below 20kHz that isn't getting encoded and recreated not because of sample rate, but because of sample size. For example, if my source material didn't "need" 44kHz througout a song, could the sample rate be trimmed back in places while the sample size was increased? In the end, it's all just a stream of x samples per second, y bits deep. So if a new sampling technique allows us to reproportion (optimize) those two dimensionons in the same amount of overall space, it's possible that better audio will result. Thoughts?
There are quite some examples in math how non equidistant sampling methods can vastly improve the order of accuracy, let's think about quadratures (numerical Integration):
Integrating a function f(x) from a to b means measuring the area below the graph. So the first estimation would be to split the interval from a to b into equidistant parts and sum up the area of the rectangles below or over the graph (that would be about f(x_n)*h, where h is the width). This method is called Riemann-Sums or iterated Trapezodial-Rule.
But you could also try to plot piece-wise polynomials through these equidistant points and calculate the areas below. This would yield better (order) results; these methods are then called iterated simpsons or millne rules. But if you go higher than polynomials of 4th degree, you will get to methods that could compute negative integrals of positive functions, which does not make sense. The reason is that high order polynomials tend to "oszillate" or "run out of bonds" at the end of the intervals. Thus these "Newton-Cotes" methods of equidistant sampling points are of limited capabilites...
But if you drop the assumption that you need to take equidistant (uniform) sampling points, you will get to far better methods: With Gaussian Quadratures the sampling points are far more dense at start and end of the intervals and thus the interpolating polynomials yield far better order results!
Thus if you know what you are going to use your data for, then you can always find better sampling methods to optimize for your needs- IMO it really doesn't make sense to simply sample the voltage of the signal at equidistant time frames when trying to digitally represent sound! Where as "lossy compressions" like ogg or mp3 drop information that is less interesting, this equidistant 44kHz sampling just drops anything that does not fit into this sampling; it's kind of a "brute-force" method. And if you then compress to ogg or mp3 it's the same problem like why you should never convert mp3s to ogg... It can (and will) only get worse.
If you are interested in that quadrature methods then read "Numerical Analysis" by "Kendall E. Atkinson" Chapter 5.
I was reading somhere (can't remember where) that although we can't hear above 20Khz, sounds that are above that range will lower in frequency when they bounce around the room and fall into some peoples hearing range.
CD's sampled at 44khz miss some of these sounds and that is what audiophiles complain about when they say digital audio sounds flat.
Australian? Join EFA
Fractal compression is a cool idea, and it can achieve incredible compression rates. Unfortunately it hasn't quite panned out in the real world.
One main problem has been that no one has found an efficient way to create the PIFS functions for an arbitrary image. So fractal compression can take a long time and is non-deterministic (i.e. you can't tell ahead of time how long it will take).
Another problem is that Barnsley et al. hold patents on many of the techniques used. Until its performance makes it a clear winner, why pay royalties.
It's been a couple of years since I paid close attention fo fractal compression, but I haven't heard of anything that changes the above problems.
Two of the other replies point out that this isn't quite right - the frequencies outside of nyquist just alias. However, this can actually be used to your advantage if you know that a signal lies within a narrow band of frequencies centered around a high frequency.
For example, you can perfectly sample a signal confined to 1.0-1.1MHz using a sampling rate of just 200kHz, instead of 2.2MHz. What's even more interesting is that you can play this 200kHz sample back and get the same signal in the 1.0-1.1MHz band you had originally, but along with aliases all over the rest of the spectrum. In this case, you need bandpass anti-aliasing filters and not lowpass bandlimiting ones.