Slashdot Mirror
Tighter Video Compression With Wavelets
RickMuller writes: "There is a Caltech Press Release here that talks about a new 3D video compression algorithm by Caltech's Peter Schroeder and Bell Labs' Wim Sweldens that they claim is 12 times smaller than MPEG4 and 6 times smaller than the previously best published algorithm. The algorithm uses wavelets for the data compression.
Potential applications in real estate (digital walk-throughs of houses) are cited in the article. Anyone figure out a way to wire this stuff up to Q3 Arena yet? The results were presented in a talk at SIGGRAPH 2000 in New Orleans."
isn't is kinda bogus to compare this to MPEG4, since MPEGs are 2D and this is for compressing 3D images?
-Spazimodo
Fsck the millennium, we want it now.
Fsck the millennium, we want it now.
Millennium Crisis Line: 0890 900 2000 [calls cost 50p/min]
"You'll also be able to see how it will look after you knock out a wall, reapaint the rooms, and drop in new furniture from a 3-D catalogue"
...but will it allow wireframe/noclip mode, so I can track the plumbing, electrical, and network connections through the walls?
--
"It's tough to be bilingual when you get hit in the head."
I was under the impression that most wavelet compression algorithms are patented. Of course, this is true of various MPEG formats (includeing MP3), and that hasn't slowed them down.
What's the patent issue in this case?
this can only mean one thing - download full length hollywood films which are only 50 megs instead of 300!
hooray!
--
when the rain comes, they run and hide their heads. they might as well be dead.
Yeah, all your friends are absolutely DROOLING to see the latest epic played out in 480x320 resolution on a 17-inch screen with a few little speakers. But if you turn the lights off and sit real close, it's just like being in a movie theater!
For more information, click here.
I've been hearing about how much better wavelet compression is for a long time (5 to 10 years, perhaps). The empansis has often been on sound, mainly because it's simpler to work with than video. However, you don't see people using wavelet-based audio formats in wide use. Why not?
a new 3D video compression algorithm by Caltech's Peter Schroeder and Bell Labs' Wim Sweldens that they claim is 12 times smaller than MPEG4 and 6 times smaller than the previously best published algorithm.
That's great that the algorithm is smaller, but what we really want is smaller data
---
Interested in the Colorado Lottery?
Interested in the Colorado Lottery or Powerball games?
check out http://colotto.com
This isn't going to make movies any smaller to download.
What it's going to do is make 3D worlds smaller to download.
It's not the compression technique that will allow you to view in complete 3D the inside of a house, but the fact that you can record a 3D model of a house and still have it small enough to download.
The biggest improvent would probably be for VRML type technologies. And it's not going to make quake faster, but it could possibly let someone on a 28.8 use a customized skin that can be quickly sent to all other computers. Most people download quake worlds before they start playing rather than on the fly. -Kashent
this is the next logical step from what jpeg 2000 does (which is wavelet based). the only real difference is one more spatial dimension in the fourier transforms--jpeg 2k obviously uses 2 dimensions. great applicaton of a simple mathematical idea. researchers have been using this for years (digital spatial recognition/navigation anyone?) but up until the recent past it has been prohibitively expensive to crunch the numbers for this in anywhere near realtime, but as our commodity hardware becomes more and more powerful, more and more of these great mathematical premises can be applied. bravo!
--
You can be an atheist and still not want to succumb to some weird cross-over sheep disease -- AC
They are comparing polygon mesh compression with video compression. Sounds like apples-to-oranges to me. Also sounds like it will have no effect on video compression, and it will have limited impact on rendering time.
I say limited, because you still need to draw those polygons. However, one nice feature of wavelets (at least for images) is that you can easily extract just enough data for displaying at a particular resolution. If that property holds for polygon meshes, then you should be able to draw only as many polygons as are useful for your display resolution.
Yes, speed will increase, and bandwith will also increase, but there's another factor. People. There continue to be more people on the Internet, whether with cable modems, xDSL, or dial-ups. As this continues to be a bigger part of our culture, more people each pulling down more bytes all the time creates problems faster than we can run fiber and install new routers.
Compression will be essential, since it will be one of the only things helping the backbone keep from choking. People can either download a 40-50MB version of 'Debbie does Dallas 2000" or a 300MB version (assuming, of course, that people would actually use the web for porn)... that saves a lot of bandwith. The other side of that is that people then download 5-10x the amount of content... either way, compression needs to be an intergral part of the Internet in the future.
--
"It's tough to be bilingual when you get hit in the head."
Surely this compression is taking a set of data and then working out the best way of representing that data - does this mean that wavelet compression can also be used on normal text files (after all, all video input is represented in the same 1 and 0 form)?
:-)
If that is the case, then there could be some even more interesting areas of use rather than just letting people sell their homes slightly differently. Network traffic could be lightened (if the algo is fast enough), storage requirements for data warehouses lessened, etc. All interesting stuff, and far more valuable than letting me see what my house will look like if I knock a wall down.
--
From what I understand of compression (and I'm no expert), it's easy to find supercompressive algorithms that work using various methods (wavelets, neural networks). The problem is that they're too computationally expensive. I'm sure someone can come up with an algorithm that can compress video even further... but will it even play at 1 frame/sec on a 1GHz system?
He said, "You'll be able to tell your grandchildren that you helped assemble the first NT supercomputer," and I cringed.
I have included a sample of the technology compressing "The Matrix" below:
1
As well as Quake 3 demo:
0
Note: Also decreases viewing time, increasing the ability of the user to consume more media.
-- Bird in the Bush: The Renewable Energy Blog http://www.birdinthebush.org
Trying to design an algorithm that is as fast as the Fast Fourier Transform (FFT) is *hard*. FFT is O(nlog(n)). Until we can get an algorithm that you can decode in real time, well you won't be able to listen to it in real time. This is why we see alot of work on images, they don't pop and skip if you decode them too slow. Here is a hint on a fast wavelet transform: look up the DWT of Mallat and Daubechies. But the math is way beyond me. One of the great accomplishments of algorithm design was the Fast Fourier Transform (FFT
This isn't video compression at all. This is geometric data compression. Comparing it to MPEG4 is really misleading. These things are apples and oranges.
This is like finding a better way for the Quake client and server to talk to each other, not a better way to stream The Matrix to your monitor.
MPEG-4 Can be used for 3D content. The Web 3D consortium is currently working on the project. I assume this is what they were comparing to.
When JPG2000 was announced here on slashdot, there was a major discussion about whether or not wavelet compression is the best for images. Is there any difference in this case scenario involving 3d movies?
Mike Roberto
- GAIM: MicroBerto
Berto
As anybody who has ever seen the stependous quality of high-res wavelet images knows, this compression is pretty amazing. Although there are probably other, more legitimate I might add, uses for this, the first thing that comes to mind is porn videos. Seriously! The adult market is one of the only internet ventures making money, and this new compression just helps out the US ecomony some more. (Not to mention the fact, that if wavelet compression allows streaming quality comparable to DVD, then you can cancel your subscription to the Spice channel ;)
A deep unwavering belief is a sure sign you're missing something...
Stereo pairs could probably use a system similar to the MPEG motion compensation, where a frame is generated based on moving 16x16 pixel blocks around in another frame and storing the small difference.
<O
( \
XGNOME vs. KDE: the game!
Will I retire or break 10K?
Run the image through a low-pass and a high-pass filter. Compress the high-pass information into tiny wavelets. Repeat the process on the low-pass signal a few times. Quantize and encode the images, and you have a bitstream. This works so well because the eye is believed to use wavelets to recognize features in images.
<O
( \
XGNOME vs. KDE: the game!
Will I retire or break 10K?
I know this article specifically refers to using wavelets for compressing 3D, but it should be able to be used for video. FYI, wavlet compression is a method that uses fractals to compress an image. If you've seen the wavelet demos, you know just how much better than JPEG wavlet compression looks. Using the same process, it is also possible to compress a sequence of frames as in a video. This is demonstrated in some of the wavlet demos floating around the net. Right now they're in black and white, and are pretty small, but it is conceivable that they'll get better. A big problem with wavelet compression is the CPU cost. Even single images can take a second or two to decompress. However, that can probably be offset by hardware decompression mechanisms, and it doesn't seem that they're will be a shortage of CPU power anytime soon. If you've ever seen how well wavelet lets you compress images 50:1 with so little quality degredation, you'll understand what an impact this method could have on computer video.
A deep unwavering belief is a sure sign you're missing something...
I just finished writing a proposal to NASA for some instruments on the Solar Probe spacecraft. That's a pretty telemetry-constrained mission. We tested a proprietary wavelet-compression algorithm at 50:1 on 14-bit images (yes, that's about a quarter-bit per pixel) and even at that level it's very hard to tell the difference between compressed and uncompressed images with the naked eye. (The algorithm seems to work by quantizing the sizes of features in the image).
At that level of compression, a 30Hz stream of 6bit-per-channel 640x480 images would only require just over 3Mbps of bandwidth -- and that's without taking any advantage of the relationship between frames. It's easy to believe that another factor of 50 could come out of a combination of more aggressive compression and either diferential encoding or 3-D wavelets. We could end up with full-motion, full-rate video being squirted through 60kbps connections.
(this reply will suck; slash has been eating my replies)
MPEG compresses motion by taking 16x16 pixel blocks from the previous frame and storing the (small) difference. Perhaps this same technique could be used to store the differences between the left and right eyes.
<O
( \
XGNOME vs. KDE: the game!
Will I retire or break 10K?
This comment explains to us all why this entire thread is worthless while educating us at the same time.
In most natural or real-world data (i.e. images, geometry data, etc.) the information at a given point in the data is very highly dependent on the data at nearby points. Thus, there is a certain amount of redundancy in the data, and this redundancy is spatially localized. The concept in transform coding is to apply some transformation (either linear or nonlinear; the wavelet transform and Fourier transforms are linear) to this data to reduce the statistical redundancy.
Even after applying the transform, you haven't saved anything in terms of the space required to store the data; all you've done is change the basis used to represent the data. Now you take the transformed data and place it into a bunch of bins, each of which is identified with an integer. At this stage, called quantization, you are modifying the information present, because the best accuracy with which you can recover the data is given by the width of the bins. At this stage, you take the sequence of integers and apply a lossless coding scheme to it to reduce the number of bits required to represent the stream of integers. The compression happens at this stage. Wavelets do a better job than blocked discrete Cosing transform (used in JPEG) at reducing the statistical redundancy of the input data; thus wavelet-based image compression compresses more efficiently than JPEG.
What Schroeder and Sweldens have done is taken an a very general, widely applicable method for constructing wavelet transforms (known as the lifting scheme, invented by Sweldens) and adapted it for representing mesh nodes and connectivity information, i.e. geometry (which incidentally could just as easily be higher dimensional data). Thus they have a wavelet transform for geometry. They achieve compression by using the EZW coding scheme, developed for coding wavelet coefficients of images and used in the JPEG2000 standard, and applying it to their geometry wavelets.
It should be very nice for low-bitrate storage and transmission of geometry, as well as successive-refinement transmission (i.e. the 3-d data gets better and better looking as more bits arrive).
All is Number -Pythagoras.
I agree that 60kbps full-motion high-quality video is probably possible. Using 3-D wavelets would build in some lag time (like 128 frames or so, depending on the basis) so it wouldn't ever be "live" (but heck, what's 4 seconds?)
All is Number -Pythagoras.
(Moving out of the way to avoid the stampede of people rushing to patent the process of applying 2D algorithms to 3D)
I'm trying to teach myself to set people on fire with my mind... Is it hot in here?
Sure, wavelets are O(n), FFT is O(n log(n)).
But the FFT has a much better constant, and so is generally faster on real-world data sets.
The real win with wavelets isn't speed, it is the match to the real world data. A sharp boundary in the FFT has to have a "long tail" in the coefficients, causing Fourier transforms to suffer from things like the Gibbs effect. Wavelets allow you to make a deliberate tradeoff between smoothness and sharp boundaries. So more information is in fewer coefficients.
BTW a lot of the better wavelet algorithms (eg wavelet packets) are no longer O(n). Why not? Because they allow you to dynamically choose the best representation out of a family of representations. That extra freedom requires processing time...
Cheers,
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
With wavelets at a very basic level there are too many options. Wavelet researchers don't talk about a wavelet transform, they have entire families of wavelet transforms algorithms to argue over. Each is better in different circumstances.
This makes standardization harder. There are a lot of tradeoffs. Do we go with the one that works better on smooth data? Or on boundaries? The one which is symmetric so that the errors it produces tend to be harder for the human ear to pick up? Or the one which is orthogonal, giving it a ton of nice mathematical properties? Shall we have a simple wavelet transform? Or a dynamic wavelet packet transform? Do we work from the most significant bit of data to the least? Do we try to order the data in some way? (The first allows for bandwidth to determine the compression level chosen, the second is key for streaming output.)
The basic idea of a wavelet is very flexible. So you get a lot of choices, none of which is obviously better than the others. This makes it hard to decide which should be made a standard...
Cheers,
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
Wavelet transform just turns data with local similarity of information (think about a picture for a second) into an alternate format where the fast majority of your information is squeezed into a small fraction of the terms.
It is useless on things like text where from point to point things jump around. Feeding a sentence of English into a wavelet transform would be silly.
Now what does this transform give you? Three things. First of all you now have your significant information in a small number of terms that can be easily analyzed. (Think speech recognition.) Secondly you now know that the majority of your data consists of numbers close to zero, which is something we know how to say efficiently. And thirdly we know what the least significant information is (all those little terms) and we can just chop it out for a lossy algorithm.
So wavelets are useful for data processing (visual and auditory recognition, etc), lossless compression, and lossy compression of visual, audio, and other similar data. It is particularly valuable with data that has a mix of boundaries and smooth regions. (Fourier transforms are good on smooth regions only.)
Cheers,
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
Compression works by coming up with a compact description of "predictable data". After a wavelet transform most of your data is predictable - it is in terms close to 0.
This allows wavelets to be used for efficient lossless compression (compress the small terms using their predictability) as well as decent lossy term (ah heck, throw away small terms).
Cheers,
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
As so often, there is a great algorithm (set of algorithms, actually). The problem is -- make a standard out of it. Create a file format that supports the standard. Create a library that reads and writes those files. Create a browser plugin from that library.
This usually takes several years, not to mention the problems with patents.
For instance a traditional wavelet transform cannot touch Wim's lifting scheme. There is no way that any standard that was written before he came up with it could have taken it into account.
I saw him give a talk on it a few years ago. One of the coolest visual effects that I have ever seen was a picture of a ballroom with a metal ball in the middle. He laid down a wavelet transform on the ball, and another on everything else. He strengthened the detail on the ball, and weakened it everywhere else. The room faded to a blur, while the ball was in some sort of super-focus. And the blur did not look like a smudge like you sometimes see, it looked exactly like things look when they are out of focus.
As for the data ordering, let me give you the issue in a simple form. When all is said and done a picture takes a certain amount of data. But data is not created equal. Some pieces (eg the most significant bit of the number for the average color of the whole picture) say more about the picture as a whole than others (eg the least significant bit distinguishing one dot from another).
Mathematically you can calculate the energy of each piece of information. Now wouldn't it be nice to send the information ordered from the most significant to the least significant bit? Then once the receiver has an acceptable picture they can just cut the transmission short.
OTOH now stop and think about this in context of a song. The basic tune at the end of the song is going to come through before the first word is clear! Streaming media really needs information sent in an order that is time-sensitive. Sure, some information can be sent ahead, but ideally you want to be able to have a fairly small buffer of stuff sent ahead, and be receiving the details in order of execution.
Cheers,
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
The Internet standard for stereograms is right eye on the left, left eye on the right. Cross-eyed. That's how the 3d South Park images at www.sweeet.com are presented.
<O
( \
XGNOME vs. KDE: the game!
Will I retire or break 10K?
I posted this after I read the responses to my original post. I'm not out to "prove" anything. I've read a few articles on it awhile ago, and somehow fractals got mixed in with the memory. It was a mistake. I'm sorry. It happens to everybody. As for my comments about WIllamette, I did make some mistakes and had to revise my concept a little bit, however my overall point still stands. In consumer space, Willamette will be a beast. I was wrong about some aspects of it, (for example, I thought the clock doubling applied to the whole pipeline) but nobody has disproven my point. It seems that Intel is trying to take on NVIDIA in the geometry department. In doing so, they make a chip that performs geometry acceleration very well, but is a little weaker per-clock for other tasks. However, the high clock-speeds outweigh this disadvantage, and help greatly for matrix operations where Willmatte is really strong per clock (because the 20 stage pipeline really doesn't have a negative effect on something regular like matrix operations.) Additionally, Intel not only has the motive (geometry accelerators make them less relevant in the all important games market) but the concept makes sense. If Willamette is weaker per clock than K7, but at a higher clock-speed, it's performance should match most of the time. However, the high-clock speed really helps matrix operations, where Willamette doesn't have a per-clock disadvantage. Also, I said that AMD needs to do something to counteract Willamette. AMD doesn't HAVE anything to counteract Willamette. Not only is the next chip (Mustang) not aimed at all at the consumer market, but AMD's chip after that (K8, Sledgehammer) is aimed at competing in server space. Additionally, it appears (if you read the articles recently on ZDNet and CNET) that Intel may be lowering the market they're aiming at with Willamette. If that's the case, then AMD has nothing to counter that. There you go, a summery of the entire thread. Where's the "total bullshit?" Prove me wrong here somewhere, then maybe you've got a point.
A deep unwavering belief is a sure sign you're missing something...
1) SSE2 doesn't have 2 instructions per cycle. I said it is twice as fast as 3DNow! Since SSE2 is 128bits wide (meaning 4 32bit floats per instruction) and 3DNow! is 64bits wide (2 32bit floats per cycle) that's true. Look it up. It's not two instructions per cycle, but 4 operations per instruction./ 11344">this article </a> and MaximumPC proves it.
2) You've got me on the yield problems. However, Intel has rarely had yield problems, and if AMD can take it, I'm pretty sure Intel will make it.
3) AMD cannot migrate down the Mustang since it is the same exact (K7) core with more cache. Source: Sharky Extreme (www.sharkyextreme.com) AMD/VIA roadmap, 6th page.
4) Willamette actually will be targeted at mainstream systems. Check www.zdnet.com for several articles. Additionally they are supporting PC133 SDRAM for these lower-end systems. Lastly, <a href="http://www.maximumpc.com/content/2000/05/08
Now what were you saying about not being totally sure?
A deep unwavering belief is a sure sign you're missing something...
Okay, I reread the docs. You're right, Willamette only has one FP pipe and one load/store pipe. However, the single 128bit wide pipe should be faster than P3's double 64bit wide pipes, and we already know taht SSE is as fast or faster than 3DNow!. An intersting article covers these, you can find it here.
.18 micron technology and 1MB of cache. The reduced core size and lower power requirements are simply a byproduct of the .18 micron process. Considering that the Thunderbird Athlon already runs a .18 micron process, it already has the reduced core size and lower power requirements. And instead of "1MB of on-chip, performance enhancing L2 cache memory" Thunderbird is "256KB of on-chip performance enhancing L2 cache memory." Thus, it IS simply an Athlon with more L2 cache.
Read the FAQ carefully. The thing is simply an Athlon with
As for Willamette and the MaximumPC artice, it is quite accurate. You can find similar articles on ZDnet, and yes, Intel HAS been quoted as saying it is aimed at the high end, but it HAS done focus shifts before. In fact, the article in the latest MaximumPC even mentions that quote, but says they may aim it at the lower to middle end to compete with Athlon. Ans since Willamette itself won't really come out in volume till very late this year, the SDRAM chipset isn't very far off. In fact, it is very reminiscent of the whole PII, where Intel aimed PII at more mainstream applications quite quickly.
A deep unwavering belief is a sure sign you're missing something...
But my point is that AMD's new CPU is simply an Athlon with more cache. No new features, no rearchitecturing of the pipeline. Don't you think they would put it in the FAQ is the actual chip was going to be changed? All along it has been known that the Athlon Ultra would be an Athlon with more cache, just like the Xeon chips are compared to the Pxx chips. The FAQ doesn't say anything about changes, just a new process. AMD has already done this process change. The Thunderbird Athlon is simply an Athlon with 256K of L2 cache, and based on a .18 micron process. Plus, it is already based on copper. Aside from the change in L2 size and speed (and any changes in circuit layout), there are no other changes. Same thing with Mustang. The Mustang will actually be less of a change than Athlon -> Thunderbird. It will be based on the same Thunderbird core (Most 900MHz+ Athlons are based on this core) with 1MB of L2. Process changes HAVE been made without architectural changes. Take PII Klamath to PII Deschutes. In that case the process was moved from .35 to .25 with no other changes. Athlon Ultra (Mustang) is the same way. Anyone without any preconceptions would read the FAQ as talking about an Athlon with more cache. Everything the FAQ talks about, (except the 1MB of cache) is already implemented in the regular Thunderbird Athlon.
A deep unwavering belief is a sure sign you're missing something...
You don't seem to understand what Mustang is. I just looked at the AMD faq. It says that Mustang is an enhanced version of Athlon based on a .18 micron process and with a larger cache. However, the Thunderbird Athlons are already .18 micron .18 micron copper process. This is where the "enhanced with reduced core size and power consumption" part comes in. The only difference is the case of the Mustang where it has up to 1MB of full speed L2 cache. I don't see why this is so hard to understand. My original point was that AMD doesn't have a processor that can compete with Willamette if Willamette's performance is as high as expected. I said AMDs real next gen design is the Sledgehammer chip. You put for Mustang as AMD's next chip. However, Mustang is simply an AMD Athlon Thunderbird with more cache. It is almost exactly like a PIII Xeon. Same core, same copper process, same everything except cache. Sure there may be changes in circuit layout to accomodate the cache, but no real performance benifets will come from that. It is doubtful that AMD's .18 micron process will scale to 1.5+ GHz given the limitations of the process. Even the .18 micron Thunderbirds are already producing huge amounts of heat. You can't argue that Mustang is a next-gen processor, so where's your ground? If Willamette is a big 3D powerhouse, AMD doesn't have a leg to stand on. If you actually go out and read the articles that are comming out, they say the same thing. ZDNet even said that AMD may have to go back into the value market if Intel can pull off the whole Willamette thing. (Get developers to recode, be able to get decent performance on non 3D apps, get good yeilds, etc.)
.35 micron PII overclocked to 333 gives the exact same performance as a 333 MHz .25 micron PII.
"
Q6:Does the new version of the AMD Athlon processor use a 0.18 micron manufacturing process?
A6:Yes. All of the AMD Athlon processor wafer starts are now on 0.18 micron process technology. The die size of the new
AMD Athlon processor is 120mm square
"
The other quote, from the same FAQ is this
"
A15:
"Mustang"
Enhanced version of AMD Athlon processor with reduced core size, lower power requirements, and up to 1MB of on-chip,
performance-enhancing L2 cache memory. Manufactured on a 0.18 micron copper process technology. Multiple
derivatives of the Mustang core are planned to address the requirements of the high-performance server/workstation,
value/performance desktop and mobile mark"
If you carefully read past the marketing speak, you'll notice this. Both the current Athlon (Thunderbird) and the next Athlon Ultra (Mustang) are based on the same
PS> It isn't possible to change the process without changing the layout, but steppings almost never result in performance increases, just better yeilds. Case in point. A
A deep unwavering belief is a sure sign you're missing something...