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."
Even better sound than what we now know as almost perfect? Great! Makes you wonder how much better it will get in the future, even when we have perfect sound....
Well, if you sample only part of the space, of course you're going to get an "improvement".
Silly boffins!
Okay
Happy downloading!
King's Cross.
You fill in the missing data
Funny, I saw no mention of DJ Shadow in this article.
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.
I tried a similar technique on a Statistics paper I had to write, and got an F for plagarism!
Religion is a gateway psychosis. -- Dave Foley
Could this lead to new data compression schemes for non-detail critical images and other files? A sort of JPG with half detail and half math? It wouldnt be high quality but it would be a fraction of the size, perhaps yet another low-bandwidth video codec?
Well.. one thing's for sure, if I ever have a doctor reading my brain MRI I sure as hell don't want half of it removed (neither my brain, nor the scan).
^nA! Creatures in my Head
If this is indeed a breakthrough, I hope the National Science Foundation (who is funding the research) decides to make the information free for anyone to use. The last thing we need is for them to kill the technology by attempting to retain control of it through copyrights, patents, and controlled licensing. Research like this should be published and given freely to the world community, not licensed to corporations to try to make a buck.
Are there any patents already taken out? If so then we could have before everyone else the video equivilant of ogg.
Bible-thumping doctors are always saying how "perfect" the human DNA is, how it's the "world's most perfect code," which I, as a Hacker, should understand.
Yeah, bible-thumpers,
WHERE'S THE ECC?
Is this how ZeroSync's decompression algorithm works?
What's the practicality of this? Well, spiral MRIs, for example, where for mechanical reasons you don't want to have to stop-and-start the very heavy "scanner", wasting time and jarring sensitive equipment. As I said, niche applications.
As for compressing audio, there are already plenty of other psychoacoustic compression schemes -- whether non-uniform sampling is better or worse will likely depend on the application.
MP3 (and Ogg Vorbis, etc.) technology. I mean, mathematical non-lossless compression technology... different algorithm, same purpose. (Side note: It seems ironic that as storage space grows, this becomes less and less necessary.) In any case, it seems to indicate a trend: the ability to get the maximum from a minimal amount of data.
It was at Bell Labs ... but the guy who developed the Uniform Sampling Theorem was Nyquist, not Shannon.
Toronto-area transit rider? Rate your ride.
As a Computer Engineering Major, this tosses a significant portion of my degree out the window, but, I suppose, it's a good thing. Aliasing (Java) and Folding (no link) were always a pain.
Michael C. Hollinger
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.
Hereby I donate the following algorithm to the public. It's called GNU-squat.
Step 1:
Non-uniformly sample your favorite music using just 1 bit. This will ofcourse take up at least 8 bits on your harddisk but let's not nitpick. The good part is you don't even need special hardware to sample the music, just enter if the music is loud (1) or soft (0).
Step 2:
Use the Vanderbilt mathematical routines to extrapolate the rest of the data, and presto: the complete song re-appears from just one bit of data.
Doctor to patient, after looking at the reconstructed images: "Ah there is the problem. The cause of your headaches is that you have a bunch of inch-long bony spikes sticking out of your neck, plus a bunch of holes in your skull."
example. It was not provided to show a compression mechanism in which the original image could be compressed. It was intended to show that if you sample randomly, then their algorithm can come up with a highly accurate representation of the original. The implication here is that given current capability to sample, if you apply the new technique, you can get a better image/audio recording using their technique, than you can using the current fixed sampling interval technique, making the image more vivid, or the musical recording more lifelike than current sampling provides.
I'm better, because I'm bigger
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.
http://citeseer.nj.nec.com/rd/72823020%2C302362%2C 1%2C0.25%2CDownload/http%253A%252F%252Fciteseer.nj .nec.com/cache/papers/cs/14699/http%253AzSzzSzatla s.math.vanderbilt.eduzSz%257EaldroubizSzSIAMRV.pdf /aldroubi00nonuniform.pdf
Go read the PDF then get back with us.
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.
Along your point, there's actually a technique that uses the self similarity of images to help you compress themselves. For example, you might have seen the "Sierpinsky Triangle." You can generate this image with a few very simple recursive move/resize/draw operations.
Fractal compression uses this technique on abstract images. It aims to find a set of operations (sometimes very large) to generate any given input picture. It's very cool, and you can get more information (including example pictures) at this page.
The "state of the art" of fractal compression beats JPEG compression at some compression ratios, but looses at others. It's also interesting that a fractally-compressed image has no implicit size (ie: 640x460), so it enlarges MUCH better than simple image enlargement.
It all goes downhill from first post
This is not quite accurate. The original signal is not "required" to be band-limited. Rather, it is accepted that frequencies outside of your design bandwidth will not be captured. The signal can stray outside of the "defined limits", but should it do so that information will be lost. Furthermore, Fourier's math tells us that a signal that is limited in time is unlimited in frequency, and a signal that is limited in frequency is unlimited in time. This has important ramifications. The biggest - and most obvious - is that all man-made signals are limited in time and therefore unlimited in frequency. Ergo there will ALWAYS be information lost no matter what bandwidth you design for.
Now to read the rest of the article - it sounds intriguing...
If their point is that they can better reconstruct the original image from non-uniform samples, then it would have been more interesting to see a comparison of reconstructions: in particular, take one MRI images with random pixels missing, and the second MRI images with the same number of missing pixels but arranged in a regular pattern, such as a grid.
However, I suspect their point is that they can reconstruct the original at all with non-uniform sampling. This is useful in cases when it is not feasible to obtain fixed samples.
Tsunami -- You can't bring a good wave down!
I was making up missing data for lab reports twenty years ago. It filled in the gaps well enough to fool the teachers :)
News article was, as usual, totally lacking in technical details. But they did link to technical articles at the bottom of the story.
NON-UNIFORM SAMPLING AND RECONSTRUCTION IN SHIFT-INVARIANT SPACES.
I skimmed the technical article (heavy math alert), and the results seem to be along the lines that: given an irregular (and possibly noisy) sample of data, reconstruct a
function that gives smoothed (continuous, not discrete) approximation for entire data set.
There is some nice mathematics that make it suitable for such purposes. The algorithms are selected to limit number of terms and guarantee convergance, and are computationally efficient. If you think of it as fancy interpolation, you are not far off the mark from what I saw.
This is not to disparage the efforts here (it looks to be quite useful in several domains), but it is a technique for generate a smooth, continuous function to represent a set of non-uniform samples. It cannot magically find missing results not were not evident in the limited sample data.
The author
I was hoping someone would finally come up with a good method to use in lunzip (see this for more details. In short, it's a superior compression utility, at least for certain jobs, like prepping your computer for the FBI).
Use 'slashdot stuff' in the subject line in any email you send me if you want to get past the spam filter.
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
Look at the sample image. Most of the details are reconstructed correctly. But some errors like the spikes are obvious.
If you use a classic technique like interpolation through splines, diff the images and remove the gross errors created by this new method, the result might be quite convincing.
For starters, if human threshold of hearing tapers off at around 20khz (its actually closer to 18khz where at 20khz most audio is fully attenuated... but anyways)...
How will a "new and improved" method of sampling help me hear audio I can't hear anyways?
Nyquist proved that with uniform sampling at 2/T you will lose no spectral information between DC and 1/T.
Somehow I think this is more "Magic Ph.D" material than real science.
Tom
Someday, I'll have a real sig.
We have enzymes called nucleases whose job is to repair specific types of DNA damage. We have nucleases that repair uv damage (in the form of thymine dymers) to our DNA for example. Anyhow, before you complain about human biology, I suggest you RTFM and take a Bio course beyond highschool level.
?-|||-----x<*))))><
(Side note: It seems ironic that as storage space grows, this becomes less and less necessary.)
Compression research continues because in the domain where latency is less than one minute (that is, not FedEx), data communication throughput does not increase nearly as quickly as storage space. Sure, you have 100 GB to store uncompressed images and audio, but how are you going to transfer the information to another computer?
Will I retire or break 10K?
the guy who developed the Uniform Sampling Theorem [wolfram.com] was Nyquist, not Shannon.
Nyquist conjectured it in 1928; Shannon proved it in 1949. Many texts split the credit, calling it the "Nyquist-Shannon sampling theorem."
Will I retire or break 10K?
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?
On a totally unrelated note, I took differential equations from Akram Aldroubi. On the first day of class when we all sat down he said, "Welcome to French 101." Scared the hell out of a class full of engineers that haven't seen anything to do with humanities/arts courses in a while. If you ever have to take math at VU this guy is really good at explaining it.
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.
The variable bit-rate in MP3 compression does not
alter the amount of time between each sample. In
terms of sampling frequency MP3, even VBR is still
uniform, uniform as in time. VBR changes how many
bits are in a sample, not the time between samples.
48kHz 24 bit is all you need to generate a perfect reproduction of audio as far as the human ear is concerned. These days, audio in the pre-amplified stage is about as good as it's going to get, because it's already as good as the human ear.
Non-uniform sampling, if it really improves matters (which I doubt in the case of audio), can't improve on what's already perfect.
Just to emphasise: by perfect I mean the theory says that none of the distortions generated are even close to what a human ear can hear. This is also true in practice.
Who cares- 98.43% of all quoted statistics are made up.
Lucius Sour
s/as/at/
Take a look at the triad of MRI images in this article. If you look at the image on the left, it appears to have been scaled up about 2-3x from the original size. If you zoom in on it, you can see that the smallest represented detail in the picture is about 3 pixels across. It looks like they just imported the MRI into Photoshop and did a Bicubic scale to 300%!
They then remove 50% of the data in the second picture, and proceed to mathematically reconstruct it in the third. In my mind, this would be a great feat, except for two things:
- More than 50% of the data was unnecessary to present the data in the first place. The original is quite obviously scaled up from its native size.
- The mathematical reconstruction introduces artifacts that were not even present in the random image, such as huge horizontal pixel smears.
Can someone point to a better demo of this set of algorithms?
Justin
"Why would God give us a waist if we wasn't supposed to rest our pants on it?" - Rev. Roy McDaniels
I looked through the paper quickly, and it is a survey of existing techniques. The benefits of non-uniform sampling have long been known. Current low-end graphics hardware uses non-uniform sub-sampling grids to give better anti-aliasing results.
It was shown in the 70's or early 80's by A. Ahumada that the human eye uses a non-uniform distribution of rods and cones (outside the fovea) because it can give better frequency response than a uniform grid (given the same number of cones over a given area).
In short, while this paper makes good reading, don't think that it represent a breakthrough in the field.
"It's overkill, of course. But you can never have too much overkill." - Anonymous Slashdot Coward
Formats supported by Eastman Kodak Company-
... given enough training data you can make a GA to give 'guesses' into any dataset.
PhotoCD works with a differential 'error' image that was created by comparing the resampled to the original, and then that was compressed. Effect? Take a small image, blow it up by a factor of 2x, apply this itty bitty 'error' transform, and you have a nearly perfect 'fixed' image for the cost of some small change on disk space
Then there is the 'much better clarity' etc statement- there's 'inverse point transform' for getting out defects.. they used that on the Hubble Telescope. Looked pretty good for being wildly out of focus.
Everything you've mentioned is already available... the technique looks interesting but it's all data dependent
I've been doing this for years. Nothing new here. Move on.
Some of the "filling in the dots" indeed produced long spikes that are *not* in the orginal. In the sample chosen, that was not a problem because we know that is not how the (normal) skull goes.
However, in some other image settings this might not be the case. For example, where there are a lot of linear-dimensioned information that tends to go by the same grain as the pixels.
They might be pulling some wool over our eyes by picking samples that minimize the downsides of their algorithms.
Perhaps they should focus on esthetics improvement, such as music and clipart and not on domains where you can get your ess sued off if somebody dies from a misleading image.
(troll mode on)
This kind of reminds me of the OOP books which tend to show change patterns that OOP seems to benefit, but completely ignores change patterns which tend to get messy under OOP.
(troll mode off)
Table-ized A.I.
Hmmm, this might be good for:
Non-skipping CD players.
De-scratching old LP records.
Reconstructing old photographs.
...where the object is to be excited about the new theorem/method/sampling technique without mentioning any details about how it works... I always get a laugh when I see things like "Our theory - which is based on a lot of beautiful new mathematics". I can just imagine the reporter: "tell us about your new mathematical theorem without mentioning anything at all about how it works!"
Karma: pi (Mostly due to circular reasoning in posts).
check out chapter 13-8:
i pe s/bookc.html
http://www.ulib.org/webRoot/Books/Numerical_Rec
(btw: that book is a decade old)
I don't see that as being true - although you may be able to create a better image of the sound through the non-uniform technique, you still have to have a highly controlled time resolution so that you at least know where your samples are. If your technology is fast enough to give you that time resolution with a low jitter, you're still better off sampling uniformly and getting rid of data later than randomly deleting data at the source.
I don't think the reconstruction they showed was anywhere near a "highly accurate representation of the original". Furthermore, I strongly suspect that simple median filtering would have resulted in at least a visually better result. And there are certainly lots of methods around already that will do better on this problem.
non-uniform sampling is not that new.... and data recovery techniques are not dependant on uniform or non-uniform sampling... maxaimum entropy methods, or bayesian analysis are very powerful at this - I wonder if a compaison has been made ?
Looking at the 'restored' pic I see only 'horizontal' distortion, imagine how well the picture would have been restored if they would have applied their maths in *two* dimensions...
Visit http://ringbreak.dnd.utwente.nl/~mrjb/growingbettersoftware to download your free copy of the book
So how's this sampling going to affect the census??
appended to the end of comments you post, 120 chars
It's essentially a POINT - it has no dimensions. When you see those little squares you actually see a poor (and fast) representation of pixels - pixels themselves are not square or non-square. Pixels won't come in various sizes, they'll still be regular 0-sized points.
Here's a good paper on why it's important to keep in mind the true nature of pixels (by Alvy Ray Smith):
A Pixel Is Not A Little Square, A Pixel Is Not A Little Square, A Pixel Is Not A Little Square! (And a Voxel is Not a Little Cube)
All Rights Reversed.
Err, I read the article. I'm left a little confused. It seems they're talking less about non-uniform sampling than how to best recreate the function of an existing dataset.
For down-to-earth, "non-uniform" sampling methods, I've used variations of two in the past:
1) Relatively low sample rate until a known significant event in the sample stream is detected.
Then shift to the appropriate sample rate (or even variable, based upon a timing profile).
This has been especially useful when decoding (radio) "bursty" datastreams where there's long periods of "silence"
interrupted infrequently by data transmissions. No sense in wasting buffer space or overhead until you know you've got data to look at.
2) A variation I've used more often: operate at full (Nyquist or better) spec sample rate, storing to a fixed-size buffer whose contents are discarded/ignored if, upon inspection, it contains no interesting data. If data of interest shows up, say, halfway into the buffer, that becomes the beginning of the buffer (can you say "ring buffer"?) and you continue to sample til the buffer is used up. Best example of this would be the way a DSO (Digital Sampling O-scope) works.
I've implemented one system which used 4 different sample rates within a single data set. The data is a pressure waveform from a pump/valve dynamic response test. In it are regions of interest which range in sampling priority from to "nothing's happened" to "gotta know what happened up to 4.7 mS after this event".
That's non-uniform sampling in my book. No need to "reconstruct missing data".
When I first looked at the brainscan images, my first thought was that this must either be a joke or a hoax. All the horizontal stripes makes it quite obvious that no vertical interpolation is done whatsoever, and all the filled-in pixels seems to be just copies of their closest horizontal (valid) neighbour. Surely you would get a better interpolation by using vertical data as well, or even do an average of the other valid datapoints weighted by, say, the inverse cube of the distance or something.
But lets think a bit harder. What if the algorith only handles one-dimensional data? That would explain why there are only horizontal stripes, but why the constant intensity in the stripes? It does give a human viewer the ability to "see" the reconstructed pixels, while at the same time doing a reasonable job of reconstructing a close resemblance to the original image. Sounds OK, but that's not mentioned in the article, and seems to be at odds with the claim in the headline. But back to the closest horizontal neighbour algorithm. If this is the case, where does the line in the middle of the eye come from? There are no datapoints of those intensities there? My best bet would be that the images we see are scaled-down images of the ones the algorithm was processing, and that the two pixels that seems to have generated that line was lost in the downscaling. Seeing as there is no intensity-smoothing on the lines sticking out, I'd say it was scaled purely by picking every n'th pixel, which fits my argument well.
So, is this for real or what?
The only way the scaling example makes sense is if the smaller picture was made from non-uniform samples.
My first thought was that this was a cheat because every pixel has more data than just it's value, it also has it's (non-uniform) x and y coordinate. More information in = more information out.
Then I remembered that non-uniform sampling doesn't have to be at random intervals, it just needs to have a pattern that doesn't coorelate with the source data. So, if you always use the same pattern, you don't have to store the x and y info.
Anyway I remember the stuff in "numerical recipies" about making a maximum entropy estimatimation of a spectrum from non-uniform samples.
Does anyone know if that relates to this guy's method?
Rocky J. Squirrel
I finally found a better explanation of the new sampling theory. It has to take repeated passes at the same analogue data. First pass is sampled at regular intervals, as usual. This data is analyzed, then on the second pass areas where the data changed fast are sampled at a higher rate. Repeat if needed...
This will usually give results similar to scanning at the maximum sample rate, then "compressing" by throwing out data points where the values are not changing much -- you need less RAM, but the maximum digitizer speed is the same, and you have to replay the analog data somehow. For instance, in an MRI, the multiple scans might mean holding the patient in the machine longer. That's not good, and enough RAM to hold everything isn't going to add much to the cost of the machine. Also, there is one condition where the results could be different -- if a detail such as a hairline fracture is so fine that it might be entirely missed between the points on the first coarse scan. If you scan at maximum resolution first, you won't miss that.