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."

Comments

this is for 3D not 2D

[spazimodo]

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.

Re:this is for 3D not 2D

[schporto]

Yes but if they came up with a method that can store 3D data in a smaller space than 2D data isn't that fairly impressive itself?

-cpd

Re:this is for 3D not 2D

[bogado]

Mpegs are 2d + time witch gives you 3 dimensions.
--
"take the red pill and you stay in wonderland and I'll show you how deep the rabitt hole goes"

Re:this is for 3D not 2D

[pug23]

MPEG4 seems to encompas a lot more than just 2-D video compression, such as scene composition, and more. See this link for more than you ever wanted to know about the MPEG-4 standard.

Re:this is for 3D not 2D

[drinkypoo]

Nope. 3d data is already smaller than 2d data. You have a set of textures (already present in a 2d movie, except that you don't tend to save space by knowing where/how they're tiled) and a set of meshes. Everything is included ONCE and then re-used later when it's needed without having to redownload if you're streaming.

For instance, if you look at the content stuff that comes with a 3d package (probably not a good example) you have ~500k of files which are used to create animations which, even when compressed (albeit with shitty indeo compression) take up over a megabyte.

Finally, if you took a look at the objects, motion files, and textures for toy story and then compared that to what a full-resolution MPEG 4 movie of the entire feature would be like, I think you'd come to the conclusion that the 3d data is more space-efficient than the 3d data. Of course, you have to walk the line between processing time needed to render on the remote end, and amount of data you're going to send.

So really, I can't see what they've actually accomplished here, and it's definitely apples and oranges to compare anything for 3d data with a 2d video standard. Perhaps they are misusing the term three-dimensional.

On a side note, a coworker says it would be possible to send vertex coloring data which you've prerendered, and then have the user's system do all the easy rendering tasks, overlaying the vertex coloring. This would let you have good dynamic lighting effects (Radiosity, anyone?) and still be able to keep the bandwidth low. If anyone does this after reading this post, you owe me two copies of the server and the content creation software :)

Re:this is for 3D not 2D

[Fourier]

Nope. 3d data is already smaller than 2d data. You have a set of textures (already present in a 2d movie, except that you don't tend to save space by knowing where/how they're tiled) and a set of meshes. Everything is included ONCE and then re-used later when it's needed without having to redownload if you're streaming.

I think what you're saying here is that *motion* 3d is smaller than 2d video. True enough, assuming the motion 3d is done in an intelligent fashion. However, a 3d geometry snapshot of a scene has more information than a 2d image of the scene. The 3d snapshot has to store 2d textures for *all* the surfaces, plus vertex information.

So really, I can't see what they've actually accomplished here, and it's definitely apples and oranges to compare anything for 3d data with a 2d video standard. Perhaps they are misusing the term three-dimensional.

As I understand things, they have come up with a new method to compress the vertex information in a 3d wireframe. I do not know whether their research has taken the next logical step of compressing a wireframe as it moves through time (an algorithm could be developed which exploits redundancy between frames).

Also it is not "apples and oranges" to compare this to MPEG4, as MPEG4 does contain a standard for compressing 3d geometry information. It's not just a simple 2D video standard.

Re:this is for 3D not 2D

[bdavenport]

thank you. explainations like yours is one major reason why i read /. moderators!!

Re:this is for 3D not 2D

[The Scooter King]

Um.. didn't it say it was based on methods incorporated into the JPEG 2000 specification? That's 2D isn't it?

Actually, it would be really cool to have a video compression algorithm with that level of shrinkage.

DiVX (MPEG-4) copy of the Matrix - 650 Meg - Download Time 6hrs

WaVX (Super Ultra 12 x compressed thingie) - 54 Meg - Download Time 30 Minutes

How long before Jack Valenti has a coronary?

Re:this is for 3D not 2D

[drfrog]

nope mpeg4 is gonna support 3d streaming read the spec its pretty simple to see vrml is the 3d its be xml-ized into x3d, which in turn is being incorp'd into mpeg4 as xmt omega

Re:this is for 3D not 2D

[civilizedINTENSITY]

wavelets are a type of series expansion (like fourier expansions) but wavelets require fewer terms to generate similar results...
the FBI has been using wavelets to compress/store fingerprints

Oh Oh

[the_other_one]

It is probably safe to assume that the MPAA will somehow try to stop this.

So how long 'till we take advantage of it?

[mu_cow]

[new algorithm] is 12 times smaller than MPEG4 and 6 times smaller than the previously best published algorithm

In other words we could already do twice better than MPEG4. This would be very significant for downloads, yet I don't see videos twice as compressed as MPEG4 on the net...do you? Somehow I think it will be a long time until this is put into standards and implemented. Sad.

Re:So how long 'till we take advantage of it?

[substrate]

High compression ratios are easy. High compression ratios that don't look like utter crap is difficult. This algorithm isn't even for movie data though, its for 3D scans points, more along the lines of a model.

As one poster jokingly stated the Matrix could be stored in a single bit, '1', for instance albeit with some loss in signal quality. An algorithm won't become popular based only on its ability to reduce data, nor will it become popular only based on its fidelity (otherwise we'd be sharing 30 frame per second raw digital data)

Re:So how long 'till we take advantage of it?

[romi]

aren't #DivX movies (see fm4.org for more) compressed using MPEG4?

This is still impressive

[KeyShark]

Don't get me wrong compression is important, but with DSL, cable, and Ethernet connections, massive compression doesn't seem as important as it was say when everything was connecting with a 14.4 modem. I think compression research will fade and speed will increase in the coming years...

Re:This is still impressive

[Smallest]

the easiest way to transmit something faster is to make that something smaller. compression isn't going away.

-c

Re:This is still impressive

[Neilly]

That is ok if you are physically connected, but i've some rumours about the internet via wireless technologies (read cellular phones) becoming popular, where this kind of compression would be particularly useful, given the limited transmission speeds.

Re:This is still impressive

[Tower]

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.

--

Re:This is still impressive

[vattervi]

You forget that compression research is done mostly by computer scientists and mathematicians. They have a completely different set of priorities than the software companies. Even if bandwidth increases to some rediculous point where software companies stop implementing the best compression algorithms, the research will not stop.

Re:This is still impressive

[sfekas]

Even the most optimistic projection of broadband penetration only sees it getting to 30 or 40% of internet users in the forseeable future. That still leaves 60 to 70% of people who will be stuck using the same old slow modems and would appreciate improvements in compression.

Re:This is still impressive

[Ollierose]

The only problem with that is that even those trasmission speeds will be increasing soon (up to 300kbps within 18 months, then over 1Mbps in 3 years)

Pretty nifty...

[Tower]

"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?
--

Patents?

[crow]

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?

Re:Patents?

[tswinzig]

"I was under the impression that most wavelet compression algorithms are patented."

That's like saying, "I was under the impression that most lossy compression algorithms are patented." Just because their are patented algorithms based on wavelet compression, does not mean all algorithms that use wavelet compression techniques are patented.

All squares are rectangles, but not all rectangles are squares.

-thomas

Re:Patents?

[sqlrob]

But with today's patent office? I think he's right. I believe the use of wavelets in compression is patented. PERIOD. With luck, the patent just mentions 2-D images, and not 3-D potentially excepting this.

hooray for piracy

[fonebone]

this can only mean one thing - download full length hollywood films which are only 50 megs instead of 300!

hooray!

--

Definition?

[Anonymous Coward]

Does anybody have a laymans definition as to what a wavelet actually is?

Re:Definition?

[John Bridges]

Interesting fact:

Fractal compression is actually the same as Wavelet compression, if the data is compressed not on a scanline basis but on a Peano Curve ( a type of fractal).

How long

[MoOsEb0y]

How long will it be before somebody hacks/cracks/pirates this and it becomes DivX ;-) 2 or whatever?

Re:Hmm.

[generic-man]

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!

Wavelet compression

[crow]

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?

Re:Wavelet compression

[Tower]

The article mentions that the wavelet concept started in motion back in the early 80's. Reasons that you haven't seen wavelets in action that much might include:

[] No standard, just a few people playing with things, so they never introduced a product.
[] More obscure than 'typical' compression, more effort and background is required to implement it.
[] Cowboy Neal (not really, this was just starting to look like a poll)

--

Re:Wavelet compression

[pohl]

I remember that NeXT had a digital video product called NeXTtime, with pluggable codecs -- their own codec was wavelet-based, I believe. That work could have been folded into Quicktime already, perhaps. Does anybody know?

Re:Wavelet compression

[kalifa]

> [] No standard, just a few people playing with
> things, so they never introduced a product.

Currently changing. JPEG 2000 is based on wavelets.

> [] More obscure than 'typical' compression, more
> effort and background is required to implement
> it

No. Maths and algoritms are quite simple in the wavelet theory.

The real reason people don't hear much about it is that people in general don't hear much about what is really going on in day-to-day technology. Wavelets are everywhere, in thousands of application, for dedicated tasks. Jpeg 2000 is one of the very first application that can attract some attention by the media. This work might be another.

Re:Wavelet compression

[Aos]

Not entirely true.
Algorithms are simple, yes. Addition and multiplication.
The idea is also very elegant.
BUT - math requires VERY STRONG background, at a level of a very good university or more likely graduate level.

I took a grad course on it and implemented it and some parts of JPEG2000 as the final project.

JPEG 2000 *compression* (after you do wavelet transformation) though is a nightmare. I read only a proposal (which wasn't even public domain at the time, but prof was on the comitee) and it was hideously complex - not math-wise but it uses tons of engineering tricks. Took me forever to translate it into a program. Kinda like Microsoft COM - I read first 50 pages in a breeze, very nice and good ideas, but when they started talking about REAL LIFE implementation, I had to drop the book. Sufficient to say is that with 10 years of C experience I had to look TWICE before concluding that it was indeed C (well, C++) code.

Re:Wavelet compression

[John Bridges]

The basic problem is that wavelet compression is asymetrical - i.e. it takes a lot longer for images to be compressed than decompressed. This means it has been difficult to promulgate wavelet compression schemes which are dramatically better than say JPEG's which pretty much everybody can generate.

Also, a lot of wavelet researchers are looking for the best wavelet (or should that be tube ;-) rather than concentrating on commercialising a particular algorithm/format.

The most exciting thing about Wavelets (and fractals) is the hierarchical information filters that they represent. E.g. its possible to compare images compressed as wavelets very efficiently. The general trend of an image is represented by the large coefficients, and the detail by the small coefficients. There are a couple of projects out there which allow you to search a database of images by roughly sketching what you think an image looks like. The database search refines itself by looking at the high coefficients followed by the smaller coefficients. This has to be pretty much how are brains operate. Very cool stuff.

Re:Wavelet compression

[zorgon]

Sufficient to say is that with 10 years of C experience I had to look TWICE before concluding that it was indeed C (well, C++) code.

{enable irony compliant mode}
Hell, I feel that way about almost all C++ code. {insert grin object}
{disable irony compliant mode}

WWJD -- What Would Jimi Do?

Re:Imagine..

[Tower]

Nah - everyone will have a cluster... all those home networks with net appliances...

"My kitchen cluster is comprised of 7 dual-processor GHz 21464 Alpha devices: my toaster, microwave, icemaker, blender, coffee maker, dishwasher, and Mr. Popeil GigaRotisserie! And that's not counting the 16-way NUMA fridge!!!"

Gotta love those $500 electric bills...

--

Commercial Parts Exist

[superid]

Analog Devices has had a part available for a while that is based on wavelet coding. They claim 350:1 realtime video compression, which sounds quite impressive!

SuperID

3d, not 2d.

[Eric_Henry]

Before everyone starts talking about the MPAA and piracy, and all of the other wonderfull uses of this technology, read the story. It has nothing to do with compressing video. It compresses 3d scenes. Think fast vmrl, not fast movies. Unless the movie is 3d cg this won't matter.

Obfuscated video algorithm contest?

[fence]

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?

Re:Obfuscated video algorithm contest?

[Tower]

I've got a smaller 3D video compression algorithm - just promise not to tell anybody else, since I'm planning on patenting it - it runs from a shell, too!:

#!/bin/sh
cat $1 > /dev/null

elegant, isn't it? The algorithm is small, and the compressed data is so tiny, even your OS can't find it!

--

Re:Obfuscated video algorithm contest?

[Psi-kick Guy]

elegant, isn't it? The algorithm is small, and the compressed data is so tiny, even your OS can't find it!

Actually, it can't find it because the compression rate is 100% :o)

Here is the equivalent for files (ala gzip)

rm -rf *

Better than gzipping all your files - and faster, too!

what does mpeg4 have to do with anything?

[hidden]

isn't mpeg4 strictly for compressing 2-D video? this thing sounds more like it's for compressing 3d meshes & stuff... and meshes are almost always smaller than the rendered videos of them... so of course this thing gets better compression!

Re:what does mpeg4 have to do with anything?

[Another MacHack]

No, mpeg4 is for a great many things, including both 2-d video -and- polygon meshes.

Compression research will not fade...

[Svartalf]

Think of it this way...

With what you've got right now, you're going to want to do more and more. With each boost of bandwidth, you're going to want to do more. Even with xDSL and Cable, raw, uncompressed video would choke all but the fattest of those pipes. And if you could do that, I'm pretty sure you'd want to do something else at the same time or someone else would.

No, so long as we keep wanting more out of what we've got, we're going to come up with clever ways of reducing the amount of info that we need to carry across from one point to another.

what this really means

[kashent]

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

Re:what this really means

[Shaheen]

You can already do that type of stuff with Metastream, and it is based on wavelets, too. They hired a guy straight from MIT to do their compression algorithms - and it was worth it. I remember that a model of a safe that was 2 megabytes in DXF was compressed down to 15 KB, with hardly any loss in quality. Try it out...

Re:what this really means

[badmonkey]

wow that Metastream stuff is really cool. A gee-whiz kind of neat I haven't seen in a while..

The 3d models look really real...

Re:Hmm.

[Tower]

Yup, I love it when the guy wiggles the camcorder, too... or somebody coughs.


--

Careful

[captaineo]

This technique compresses 3D vertex information - not 2D video as the headline implies. It will be useful in sending high-res geometry across low-bandwidth connections. Two applications:

• Streaming 3D geometry over the Internet - fully buzzword compliant, but how useful is this *really* going to be?
• Sending compressed geometry to 3D cards - this is the truly interesting application, IMHO - compressed geometry may be the solution to feeding ultra-fast OpenGL cards, where bus bandwidth may soon become a limiting factor in geometry throughput

Re:Careful

[alleria]

Streaming 3D over the 'net -- maybe VRML that doesn't suck?

Re:Careful

[Maj. Kong]

Streaming 3D over the 'net -- maybe VRML that doesn't suck?

NTT had a great package a couple of years ago: Interspace. It was a multi-user system with embedded chat, audio, and video; avatars with faces; drop-in 3DStudio objects; an event-handling scripting language based on XLISP; .jpg and .tga textures with alpha channel support for .tga.

It beat the living crap out of VRML. Unfortunately, it depended on DirectX on the client side.

Don't know what happened to it, but it was pretty sweet while it lasted.

Kong
--

Rendering Speed/Quality

[LaNMaN2000]

I wonder how the use of this compression algorithm would impact rendering speed (and possibly require a loss in quality). Whereas an uncompressed 3D environment would transmit a wireframe representation of each object with associated texture information and lighting info, and merely requires the client to perform the necessary ray-tracing. I am not familiar with wavelets and was wondering what additional interpretation msut be done on the client side and how that would impact overall rendering performance/quality.

Re:Rendering Speed/Quality

[myster0n]

I don't think that this technology would be used in the final stages of rendering a scene.
The most interesting feature of this technology to me is the fact that it can be used to filter out the noise in 3D scanned objects.And it can also be used to simplify models - low poly versions of distant objects.
While this is not new, I think that most of those routines are based on NURBS (and other spline-based) technology. And with this new algoritm it can be used for polygon-based objects. Or provide a better way to convert polygon objects to spline-based objects without losing too much details.
When modeling some highly-detailed objects, I've often wished for a good polygon-reducer - maybe this is it?(that would mean that you have to thank me - hey, I wished it)

jpeg 2k anyone?

[JakusMinimus]

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!

--

Better than MPEG4? Huh?

[David Leppik]

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.

Re:Better than MPEG4? Huh?

[Pillager]

Take a look at the MPEG4 standard overview. It is much more than just Video compresstion - it also handles things like polygon meshes, and their transforms/deformations.

Re:Better than MPEG4? Huh?

[WeeGadget]

According to the MPEG4 FAQ, the standard contains a Scene Description Specification in which the "...structure and scene description capabilities borrow several concepts from VRML".

Re:Better than MPEG4? Huh?

[chompz]

I wrote something similar to this as a computer science project. It was quite difficult to get started, but once I got rolling it was easy to see very obvious enhancements which I could use to make smaller files, and it was pretty easy to use. What I did in mine was took the wavelet transform (like a forier transform, but for finite data sets) and then used huffman encoding on the individual pieces of wavelet data. Deciding how much information was needed to store individual images was very difficult, because it depended greatly on the size of features, the amount of change which was observed per pixel, and so on. All this information could be potentially tested before performing the compression, but in a real time environment there is no time to such optimization. Huffman encoding takes long enough.

Built In Compression

[fishlet]

Reduce your images to 2 Bit pix maps, black, red, and blue... throw in a pair of those funky multi-colour 3D glasses and your in business. Brilliant 3D- Tiny Filez!

Um..

[Uberminky]

"New 'MP3' compression algorithm makes transferring digital audio to computers more feasible."

...but will it allow me to use skins, so I can make my player look pretty?

Is this just graphics?

[DrWiggy]

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. :-)
--

Re:Is this just graphics?

[JakusMinimus]

wavelet compression is lossy. however, the more passes (which maps to higher fft approximation accuracy) the better your "image" will be. but since this tech relies on an approximation at every stage this is a bad compression format to consider for normal files (executables, source code, etc.). it is great, however, for files that are processed by our senses, e.g. sound and video, because our senses are easily fooled. this isn't the compression, however, that'd you'd want to squeeze the entire human genome onto your hard drive with because i doubt any of the "missing" or "wrong" bits are insignificant.

--

Re:Is this just graphics?

[Fourier]

This is just for 3d geometry data. It is a *lossy* compression algorithm, which means that the uncompressed data is not identical to the original data, just very close. The algorithm requires certain assumptions about the data set--for example, it probably assumes that all the vertices in a certain region of space lie close to some surface that readily expressed in terms of wavelets. (If that is not the case, then the data set you are working with probably does not resemble an object occurring in nature.) It is those assumptions which make such large compression ratios possible.

Re:Is this just graphics?

[Phroggy]

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)?

Only for lossless compression. JPEG, for example, uses lossy compression - when you compress a bitmap to a JPEG, you lose some of the information, and you can't get that information back. Colors are blended together, edges are less defined, etc. It looks almost as good as the original, though. The problem is, for text and data, you must have lossless compression. Opharwize yuo migt winb up wiht txet zhat loucs leqe tjis!

--

Re:Is this just graphics?

[drini]

I just wanted to point one of the reasons for which wavelets are better than fourier.

When you use fourier.. the basis functions are sines and cosines, whose ranges extend over all the real line... thus.. even for a small modification of the data you need to consider the whole set.
With wavelets, the stury is different... the basis functions used with wavelets have often finite support (roughly the range where they aren't 0) or at least have very fast decays. So... when you modifiy some data... you don't care about the whole data (i.e. the whole song or the whole video) but only on a finite interval.
This also means that wavelets are better suited to analyzing stream data.. since you can decompose locally instead of needing to have the whole data for applying fourier.

And btw... wavelet transform is *lossless* lossy... one of its main appeals are that the wavelets preserve the information so you can always recover the original data from the transformed one.

when you said lossy... maybe you meant that the data changes when you transform.. but its because it is a transform. But this transformatin lets you recover the original data exactly.
Think on the basic RLE.. of course it changes the origianl data, if it didn't, then you could end again with raw data and not compressed. But rle can be done inverse and recover the riginal image.
On the other hjand.. when you enconde a image with jpeg, you can't recover the origianl one.. that is lossy

And finally.... while fourier gives usually information about frequencies... wavelets give informatio about variations over the time.

or...

[MenTaLguY]

[] patents

Re:or...

[Tower]

Ah yes, I knew I was missing an important one :)

--

Re:Refrain from Stupidity

[rotor]

Actually, since this is for compressing 3D vertices, gaming would be a perfect application for this.

Compression is not the issue

[zealot]

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?

Already a better algorithm

[GangstaLean]

I have already developed an algorithm that is much better than this, using a technology called "bit stripping". It works on 3D worlds and movies.

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.

Re:Already a better algorithm

[tswinzig]

As well as Quake 3 demo:

0

I'm sorry... I just ran the Quake 3 demo through my Perl interpreter, and it's telling me it doesn't exist. What next?

-thomas

Re:Already a better algorithm

[Wiggin]

yeah, but it is a shame that you have limited yourself to 2 files. =)

Re:Already a better algorithm

[Jerf]

I have contacted the RIAA and the MPAA, and have pointed them at this post, which contains so-called "bit stripped" versions of every movie and every song ever produced and that will ever be produced.

If Napster's damage can be measured in the trillions in a lawsuit, just imagine what you've opened yourself up to.

"Exadollars, and soon, petadollars. One thousand billion trillion dollars. How many lawsuits per second can your software handle?" with apologies to IBM

please forgive duplication if it occurs, I'm having trouble getting through

Re:Already a better algorithm

[King of the World]

Please, you're talking to a master of algorithms.

I, and I alone, have devised a compression format that can compress a movie down to 1 bit. That's right, 1 bit.

The movie is Fight Club. The player is 3.2 gigs.

Can't say much for sound..

[Uberminky]

..but the studies and samples I've looked at for using wavelets to compress graphics were.. um.. well, they weren't anything special. At all. Bad? No. Revolutionary? Bahaha...

Re:Can't say much for sound..

[Fourier]

Maybe you should look at some different samples. Wavelet image compression is impressive. Check out JPEG 2000 for what is bound to become the next big standard.

An attempt at humor...

[Tower]

is often lost in the text world...

--

Re:An attempt at humor...

[Salant]

Nah lost in the troll world

Re:Hmm.

[Matthew Smith]

...the window is 480x320 but half of it is occupied by knobs and sliders and there is a thick tv-like frame around the viewing that's 50 pixels on each side. In fact the viewing area is only a tad smaller than a first class postage stamp. BTW. there's no broadband access in the UK and we won't see it for a good few months yet so the picture's not animated either. We're almost there Tony, e-revolution rocks, belch.

No...

[tswinzig]

isn't is kinda bogus to compare this to MPEG4, since MPEGs are 2D and this is for compressing 3D images?

The article states "their technique for geometry compression is 12 times more efficient than the method standardized in MPEG4."

The critical sentence is: "THE method standardized in MPEG4." Therefore, I take it to mean a method for geometry compression was standardized in MPEG4. You do realize MPEG4 covers more than just 2D video, right?

-thomas

3D compression

[sxpert]

this is gonna be great for holodeck stuff...
think about what the army could do with this tech (this is related to that...)

The real reason is...

[azuretongue]

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

Re:The real reason is...

[Tower]

gotcha:
[] Need specialized hardware...
--

Re:The real reason is...

[kalifa]

> FFT is O(nlog(n)).

And the wavelet transform is o(n) since Mallat's filter bank algorithms. Speed is never a problem with wavelet processing.

Good point.

[Uberminky]

I'm wondering how this type of thing (modified, of course) could be used for stereo pairs. I mean sure, storing geometric data is great. But I'd love a way to store compressed, full stereo pairs that was standardized. I dunno if wavelets would be the way to go (don't know much about'em really) but while compressed stereograms and compressed geometry would be used for 2 totally different things, I think a good (GOOD) compression algorithm for stereo pairs couldn't hurt. It'd be just the thing to use in the new home theater. ;) Seems to me that comparing full stereo pairs to saving geometry is like, oh.. comparing MPEG video to vector animations. Yeah, it'll give you *huge* savings, and give you some darned cool (and useful) features. But we still use MPEG video... I dunno. Just blabbering. ;)

what video compression?

[Eric Sharkey]

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.

Re:what video compression?

[Animats]

Correct, it's a way to compress geometry data for 3D models. This is not about video compression.

MPEG4, though, has a whole collection of stuff in it besides video compression. There's a VRML-like 3D system. There's a 2D compositing and interaction system, sort of like Macromedia Flash. There's audio compression. There's a way to send MIDI data. There's an extension for Java content. There's even a scheme for encoding data for a text-to-speech converter with character lip sync. Most of these fancy features are unused, seldom implemented, and probably shouldn't have been there at all. But they're in the spec.

MPEG 4 and 3D

[steved]

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.

Wavelets?

[MicroBerto]

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

The use of this is obvious.

[be-fan]

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 ;)

Re:The use of this is obvious.

[Anonymous Coward]

Too bad you're an idiot, and this has nothing to do with video compression. Its a 3d mesh compression technique. they compare it to mpeg4, but what all your divx pirating kiddies don't realize is that there is a LOT more to mpeg4 than juwarezing the latest hollywood action flick.

3D wavelet compression (placing frames of video back to back, and compressing the resulting 3d image) isn't a whole lot better than mpeg4's video component.

Wavelet theory is old, but you are wrong.

[vattervi]

Wavelet theory in mathematics is relatively (in computer terms) old, but it nothing like a 'technology.' The thoery of wavelets has been used in almost all image compression to date, most notably the JPEG and MPEG formats.

What Schroeder and Sweldens have done is develop a method for generating wavelets which better compresses geometrical data. This is news, and you most certainly did not evaluate a product using this algorithm at your last job.

Re:video != 3D rendering

[cronio]

Actually, it's for 3D datasets, not video.

Stereo pairs and MPEG

[yerricde]

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!

Re:Stereo pairs and MPEG

[stuffman64]

This probably work well in most circumstances, but there may be one downside. Some objects show a completely different image for either eye, thus requiring each viewpoint to have varying information. To see what I mean, get something flat, like a playing card or a piece of paper with something on each side. Hold it a few inches in front of your eyes, and rotate it 90 degrees on the Y axis (you know, the one that runs up and down), so now you are looking at it edgewise. close one eye, and you will see one side of it. Then close your other eye, and looking through the previously-closed eye, you will see a completely different image. Also, notice how it's position relative to the background has changed when switching eyes (the parrallax effect). Also, the reason that stereograms work in the first place is that the brain interprets the miniscule difference between each eye. But this is why objects far in the distance appear flatter than they do up close, the difference becomes too small and the brain cannot read the difference. When using MPEG motion compensation, minor details can be lost, and this would make for less-than-accurate stereograms, most likely the images will not appear with the proper depth, and because MPEG compression causes "mosquitos" (A compression artifact) in certain conditions, the stereo effect may become distorted, maybe even causing parts of objects to appear at different depths than the rest. However, if both images are compressed separately, and care was taken to make sure that artifacts do not cause depth-distortions (probably possible through good coding), there should be no serious problems. When I get home from work today, I will try to make a small demonstration MPEG to show what I am talking about (hopefully you know how to view stereograms without equiptment by speading your eyes (opposite of crossing them (double, no make that triple nested parenthesis!))).

Re:Stereo pairs and MPEG

[stuffman64]

My bad, I forgot the linebreaks.

Re:Wavelet compression (OT: NeXTTIME)

[juuri]

I can verify this later... I've got a Nextcube with Dimension board in it... as well as some turbo colours. The impressive thing about the NeXT codecs (which are all software, even with the Dimension) is that they pull 25fps on a 68040 box.

Its funny to watch year old computers struggle to pull that off consistantly.
---
Solaris/FreeBSD/Openstep/NeXTSTEP/Linux/ultrix/OSF /...

Compression is MORE important

[platos_beard]

It would make sense that as high bandwidth becomes more available at ever greater distances, the effective use of that bandwidth should become less and less important. Unfortunately, it doesn't seem to work that way.

Instead, expectations seem to rise at a rate that is a multiple (>1) of the actual performance increases. Back in the day, people wanted to download, say, a clone of the Breakout arcade game (for DOS) quickly. Today, the same people want to download the Slackware Linux distro quickly. Is compression less important now?

Furthermore, the increasingly wide availability of decent bandwidth at work, at home, or wherever you have your gd cellphone, again, pushes those expectations further.

Another /. article today discuss getting /. wirelessly. Is there any doubt that soon we'll expect to watch a trailer for Star Wars on our cellphone/palm pilot before we order tickets on the same device? That ain't gonna happen without compression a little bit better than we have now.

Re:Compression is MORE important

[Neilly]

It is true that data rates in wireless cellular networks will jump significantly in the near future. In europe, where the 3rd generation system is known as UMTS, 2 MB is the maximum data rate, however this would only be available if you where a single user in cell (and a small cell at that). With the expected growth in cellular use, from an network operators point of view, it would be desirable to have as much capacity per cell as possible. A reduction in the data rates required to provide these new multimedia services would therefore be appreciated, so the more compression, the better.

How sub-band (wavelet) compression works

[yerricde]

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!

Should be able to be used for video.

[be-fan]

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.

Re:Should be able to be used for video.

[Anonymous Coward]

FYI, wavlet compression is a method that uses fractals to compress an image.

No: Wavelet image compression uses wavelets -- not fractals -- to compress images. They both look at data at multiple scales, however. Most "fractal" hype comes from the fact that they're "cool" and not from any real application outside of synthetic textures.

If you want to learn about wavelets, I'd advise looking up the Haar basis (the simplest wavelet basis to use) on a 1D scanline of an image. Better yet, check out Stollnitz's excellent and understandable Wavelets For Ccomputer Graphics: A Primer.

Re:Should be able to be used for video.

[gnomish]

This technology compresses populations of geometry and does't seem directly applicable to frames of video. However, it could spur interest in new ways of interpreting photographed images as defined sets of geometries.

Re:Should be able to be used for video.

[be-fan]

Wavelet compression has already been used to compress images. It does this by finding a fractal pattern or something like that. I've actually run the demo that compresses video using wavlets. Its a small animation of a girl brushing her hair, (I think, I don't remember it exactly.) Also, there is a site that contains pictures compressing stuff like a picture of a glass of wine, a cow, etc.

Re:Should be able to be used for video.

[be-fan]

I stand corrected. I read the article a long time ago, and somehow fractals got in there.

Full motion video over phone lines -- coming soon.

[Dr. Zowie]

I am very impressed with wavelet compression in general. The wavelet decompostion of an image isn't unique -- that gives the heuristics a litle more ``wiggle room'' to choose the most optimized representation of the image.

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.

Stereo pairs and MPEG

[yerricde]

(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!

MODERATE THIS UP

[Plasmic]

This comment explains to us all why this entire thread is worthless while educating us at the same time.

References about wavelets

[kalifa]

Here is a list of books related to wavelets.

My favorite book is this one ( Amazon). Wide-ranging, great for both engineers and mathematicians, intuitive, rigorous, and clear.

Examples of Wavelet Compression

[MagicYoshi]

Another company, called High Speed Network Solutions, has a wavelet compression product out. They have a demo page that shows video and images of the technology at http://www.hsns.com/technology.htm

Wavelet compression explained by an expert

[coult]

Okay, so all of the descriptions that people have given here for wavelet compression is wrong. I've got a Ph.D. in Applied Math and do research in wavelet compression of 3-D data (not geometry data, mind you, but 3 dimensional real data, like images, but in 3 dimensions instead of 2). The basic idea behind wavelet compression is the following:

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).

Re:Wavelet compression explained by an expert

[oldman1080]

"(known as the lifting scheme, invented by Sweldens)"

Not the "lifting scheme", popularized by Microsoft when "lifting" their GUI from Apple as well as 99.99% percent of their other "innovative" technologies?

Re:Wavelet compression explained by an expert

[Aos]

You're right. I am not sure whether wavelet "compression" is a right term at all. There is a wavelet transform or wavelet decomposition. After you've done it, you didn't do any compression at all. All you did (and that's the most important thing) is to separate "crude" details from "fine" details (in layman terms).

The benefit is that now you can quantize them, and use far more agressive quantization on the "fine" details because our eyes are far less sensitive to them. Then comes the actual compression - and that's probably the part that has most patents, and some very clever algorithms.

I doubt the idea of the wavelet transform itself has any patents - it was developed by French matematicians (I believe), not some corporate slave with pen in one hand and the phone (to call the patent office) in the other...

Stereo pairs

[Spankophile]

I like 3D. A Lot.

I just don't think there are enough of us to justify a standard for stereo-compression.

Stereo-pairs should only have to be ever-so-slightly bigger than a single image/video, since the 2nd is < insert big percentage > redundant.

Maybe we should bug the guys that make DepthCharge

CPU Usage

[TheLer]

Isn't CPU usage one of the main reasons we don't see better compression algorithms in usage on the desktop? I mean I remember when I tried to run the QuickTime StarWars Trailer on my 200MMX it looked like shit. A series of pretty interconnected screenshots. I remember before napster (heh 3 time periods -- before napster, the era of napster, and now postnapster) yamaha tried to introduce the VQF (I think thats it) format and the main reason it didn't catch on was cause it used like 3x as much CPU as MP3 or close to that.

Sometimes you by Force overwhelmed are.

Re:Best compression algorithm

[Another MacHack]

Better to ask the average Komolgorov complexity of a picture; it doesn't do a whole lot of good to compress images down to their entropic minimum when that method turns out to be to equivilant to assigning each image an ID, and looking up the decompressed version in a database.

Re:Best compression algorithm

[coult]

Actually, entropy is useful only as a guideline and not as a hard lower bound on the number of bits required. For example, I can code any image you give me using only 1 bit. The coder simply compares the input to the desired image; if it's the same, the bit is 1; otherwise its 0. Very efficient on that image, totally useless on anything else. This argument has nothing to do with entropy.

Furthermore, there is no conceivable way to define what an "average" entropy is for an image. Images take many many possible forms; the space of all possible pixel images is not infinite-dimensional but it has more dimensions than the number of particles in the universe. By using statistical tools we can try to characterize this immense variability, and that is where the use of measures like entropy come into play. But entropy says nothing about the absolute lower bound on the number of bits required to code an image.

Re:Full motion video over phone lines -- coming so

[coult]

The wavelet decomposition for a given basis is in fact unique (for scalar wavelets, anyway). You are probably thinking of the wavelet-packet/best-basis algorithm, which is a generalization of the wavelet transform and chooses the basis which minimizes the information cost for a given signal.

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?)

Vorbis and wavelets

[Voltage_Gate]

Isn't Vorbis using wavelets for audio compression? I hope they don't start claiming that there are patent-issues here.

What do you mean, "long time"

[Orne]

Ahem, last time I checked, not 5 years ago, the MP3 had just arrived on the scene, and noone could play them because processor speeds were so low (heck, math coproccessors weren't even standard in the Intel line [SX/DX] until the Pentium I) The first mp3 encoders were command-line (anyone remember l3enc?), and yet look at all the apps that are available today..

All I have to say is look how the world has changed since then; computers are now standard issue college equipement, and we have 100 times the willing manpower (programmer power, especially those with a strong sharing ethic) to speed up development of new "standards". We live in interesting times...

Re:What do you mean, "long time"

[billybob jr]

small note: 486 DX processors did have math coprocessors. the SX didn't.

Re:It's entirely for 3d datasets.

[doubleyou]

Okay Johnnie, play nice.

Ahh...

[Greyfox]

But that's for 2D display of data. By making the display of data 3D, we handily avoid all those patents.

(Moving out of the way to avoid the stampede of people rushing to patent the process of applying 2D algorithms to 3D)

Re:Ahh...

[civilizedINTENSITY]

Checkout http://www.scs.ryerson.ca/~lkolasa/CppWavelets.htm l for an egcs/c++ "freeware" (sic) for linux c++ wavelet library and join the stampede!

wim sweldens on the web

[Anonymous Coward]

check out wim sweldens website

Customized Skin?

[Ribo99]

If what you say is true, I don't think this will help at all sending customized skins around. They are, after all, just images that are mapped on to the surface of existing models.
Customized models on the other hand...

---

The difference is meaningless

[tilly]

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

Dont forget motion compensation...

[MfA]

Its seems pretty much essential for really low bandwith video.

3D wavelet compression has already been tried with IEZW and SPIHT without motion compensation, the paper for SPIHT merely compare's it to high bitrate MPEG-2... its slightly better but not dramatically so.

Too many choices...

[tilly]

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

Re:Too many choices...

[craw]

Good point, but part of a standard could include the transmission of the coefficients of the particular wavelet function. This will help out in some of the simple cases that you mention. And screw orthogonality! Hell, screw orthonormal functions! This is for math gurus, and only limits the engineer's choice of functions.:)

For more complex cases, there will probably be the need to occasionally transmit the "new" set of coefficients.

Don't know about the data ordering.

Wavelets are not lossy!

[tilly]

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

Re:Wavelets are not lossy!

[JakusMinimus]

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.

on point to what i was saying (i was being terse, however =). i believe for fast image reconstitution "all those little terms" are indeed chopped off (in common applications) and we have still a very good representation of the original "image". granted, i am stating my thoughts which are based on educated guesses. hell, i took diff eq and partial diff eq as well as quantum physics in college, because, well, i am a physicist (or i was until i got into being a software developer). so, grain of salt and all that ... which should go without saying here *chuckle*.

--

No need to be lossy there...

[tilly]

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

Re: Wavelets

[sqlrob]

The time used for compressing may be able to be written off. It may take a long time to compress, but it there are a large number of downloads, it pays for itself in bandwidth.

Of course, there are limits. A about 5-6 years ago I remember hearing about a video algorithm (don't remember what it was unfortunately) that could do full screen 30 fps on a 386. Unfortunately, it took about 30 hours per frame (if not more) on a supercomputer to compress.

From research results to actual usage

[harmonica]

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.

wavelets OK, but meshes?

[bmcnett]

one problem not addressed by this new wavelet technique is the fact that the mesh is not a good primitive. the ubiquitousness of the mesh in interactive applications tends to conceal this fact. the rendering languages used in movies, however, build a new mesh for each frame, and throw it away immediately. why? because it is not easy to perform interesting operations on a mesh. a mesh is simple enough to render, but nearly impossible to work with as a design primitive. higher-order primitives are needed by human operators and their design software. it's possible to compare this to the difference between low-level computer languages and high-level computer languages. nowadays, we even have a CPU that dynamically reoptimizes the assembly language generated by compilers (transmeta's crusoe). but all the significant optimizations happen at the highest levels, far away from the level of individual assembly language instructions. an On^3 routine will eventually lose to an On^2 routine, no matter how diligently the assembly is tuned afterwards, by man or machine. this same futility will strike the mesh - all significant operations - like compression - will eventually take place at a far higher level. attempting to compress a mesh will seem as quaint as attempting to hand-optimize assembly language seems today.

Re:oh yeah, Trolling for Jesus!

[King of Pain]

I suspect this refers to me, albeit inaccurately, if I have any say in it. Jesus started a religion with signs and wonders amplifying his message. Notice that Christian religious people often say that Easter is, or should be, more important than Christmas, but in practice, Christmas is treated as more important. In my opinion, this is how it should be. Easter was merely another sign and wonder, while Christmas represents the birth of a Messiah.

As children, most of us were told the myth of Santa Claus. Although our parents lied to us, they intended no harm and expected us to eventually figure out the truth. In my opinion, the Bible (and derivatives) are all like Santa Claus myths perpetuated by "God." Like the Santa Claus myth, the Bible is neither completely true nor completely false and "God" is not interested in explaining the truth or falsity of the myth to us. Furthermore, I hope people do not anticipate that "God" will finally be "freed" in 2001 to tell us how to solve our own problems (Emanuel Kant's name is no coincidence). Doing so would encourage humanity to become domesticated animals, like the people in the distant future predicted in Wells' book "The Time Machine" who, at first, seemed to live in the Garden of Eden...but later it became clear they were merely cattle raised to be used as food. As the serpent in the Garden of Eden wisely said in the Genesis 3:5 of the forbidden fruit, "For God knows that in the day you eat of it your eyes will be opened, and you will be like God, knowing good and evil."

Explaining my comment about not being a "Jesus" above, the last thing I am interested in doing is starting a new religion or providing ethical guidance. I am interested in helping to solve problems and am only interesting in giving guidance to the extent it helps solve those problems. I am certainly not saying we do not need one or more new "Jesuses" for the new millenium, but just that I am not the person for that job.

Sorry

[craw]

I'm sorry, but I just thought of something that is sort of on topic. Do you remember Adventure? Do you like wavelets? Then here it comes.

Haar, Haar, said the pirate.

But the whole subject is like that

[tilly]

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

You are amazing...

[MfA]

I noticed the incredible load of total BS in the AMD thread about the Willamette from you which was moderated up and now again here? Again with total bullshit. Do you have some agenda prooving something about the slashdot moderation system, or are you really sincere and just have flare for getting +1's out of clueless slashdot readers?

You can make hybrid wavelet/fractal compression schemes, but thats not the point. Wavelet compression in itself has fuck all to do with fractals.

Re:You are amazing...

[be-fan]

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.

www.sweeet.com

[yerricde]

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!

Re:www.sweeet.com

[stuffman64]

www.sweeet.com does not seem to work. Also, I believe you are incorrect, if there are two images of the pair are side by side (which I assume that is how these images are represented), you must stare beyond the monitor to focus, and the further your eyes focus, the more they go towards center. For instance, to focus on an object 3 inches away, you must cross your eyes, and the nearer the object is to an infinite distance, the more centered they are. To view a stereogram, say on a monitor, you must focus beyond the image to bring them 'together' to get the stereo effect. Believe me, I have been studying artificial stero imagery for many years.

It's NOT a factor of 12 !!!!!

[Clifton Mars]

If you go to the technical paper you will see that they claim a factor of 4 (or 12 dB). Somehow someone has confused 12 dB with a factor of 12 compression, which they do NOT claim.

Anyway, this is a static compression factor. The big problem in video compression is taking into account frame to frame changes. This is why a (broadcast quality) MPEG 4 video takes 1 MBit per second to show talking heads, but 3 Mbit per second plus to show, e.g., a basketball game. How well their static technique helps video codecs will depend on how easy it is to adapt it to the dynamic problem.

Sorry I used such strong words...

[MfA]

Well you seem sincere to me, but then Im quite naive.

But you should try to be a little less adamant in your posts unless you are really truly totally sure of your case.

As for the Willamette thread... you perpetuated the myth of the two instruction per cycle SSE throughput (second pipeline doesnt do floating point). Intel quite clearly has yield problem in the high speed bins, they have admitted themselves the quantities are low. And wether or not AMD has anything to counter the Willamette remains to be seen, they have little problems pushing the clock on the Athlon/TB and the Mustang core has been tweaked that should help. As for the target market argument for the Mustang, the Willamette isnt targeted at the consumer space either. If AMD wants to they can migrate the Mustang core to its smaller cached brethren.

Re:Sorry I used such strong words...

[be-fan]

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.
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/ 11344">this article </a> and MaximumPC proves it.
Now what were you saying about not being totally sure?

Ok, 3/4's of bullshit then :p

[MfA]

Unlike the Willamette with SSE K6-2 and K7 can execute 2 3DNow! instructions per cycle :) (although the K6-2 cant fully benefit from that due to other bottlenecks) 4*1=2*2

As for Mustang, Ill just quote the official Athlon FAQ from AMD...

"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 markets."

The Willamette SDRAM chipset wont come out till next year according to that zdnet article you mention. Unlike anything in MaximumPC Intel has actually been quoted saying its aimed at the high end, you have a strange concept of proof.

Re:Ok, 3/4's of bullshit then :p

[be-fan]

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.

Read the FAQ carefully. The thing is simply an Athlon with .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.

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.

Re:Ok, 3/4's of bullshit then :p

[MfA]

Yes it is a nice article, it tries to make very clear what parts are guesswork :) In essence the main difference with the P4 is that it can potentially lower latency in respect to PIII for the SSE instructions, because it doesnt have to do two passes through the 64 bit pipes, throughput is unaffected... wether it actually does that, I have my doubts. And Im too lazy to check :) As you said yourself though, latency is not much of a problem for 3D :)

You still have a strange concept of proof... noone without so many preconceptions as you would read AMD's FAQ like that let alone call it proof of them. You cant just move the chip to another process (copper) without making some changes.

Re:Ok, 3/4's of bullshit then :p

[be-fan]

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.

Re:Best compression algorithm

[TimoT]

The amount of entropy depends on the statistical model used. Given a statistical model you can calculate the entropy wrt that specific model. That entropy is the best a lossless compression method can do with that model. As entropy can be coded almost optimally using arithmetic coding, the real problem IMO is finding practical statistical models that work well with pictures. For lossy compression you're trying to optimize bitrate vs. distortion and good distortion measures are hard to come up with; for instance mp3 works because of a good psychoacoustic model.

What exactly do you understand under changes?

[MfA]

Actually no, I dont expect either Intel or AMD to notify us each and every time they change the layout of the chip a bit to remove timing bottlenecks... they just change the stepping of the chip update the errata if necessary and move on with shipping faster processors. Why would people care exactly why processors get faster as long as they do? The pipeline doesnt have to change, although it can happen like for instance the longer reorder buffer introduced but never publicized early in the Athlon's life, and neither the feature set. From a software point of view nothing changes but the clock.

And you cant just shrink a design from .35u .25u its never that easy...

"Don't you think they would put it in the FAQ is the actual chip was going to be changed" No I dont since they didnt publicize the reorder buffer thing either, but they put it in anyway... as I see it you just choose to read it as if they didnt for some bizarre reason.

Here another AMD quote:
"Mustang is planned to be an enhanced version of Thunderbird, featuring a reduced core size, lower power requirements and large, full-speed, on-die L2 cache. Multiple versions of the Mustang core are planned to be targeted at the high-performance server/workstation, and high-performance desktop, and mobile markets. As for frequencies, we think we can offer processors that operate at competitive frequencies."

Specific enough for you? Or are they just outright lying here huh?

( from http://www.3dgn.com/hardware/articles/amd/index.sh tml )

Re:What exactly do you understand under changes?

[be-fan]

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
"
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 .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.)

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 .35 micron PII overclocked to 333 gives the exact same performance as a 333 MHz .25 micron PII.

"enhanced version of Thunderbird...

[MfA]

featuring a reduced core size, lower power requirements and large, full-speed, on-die L2 cache"

Ill take a _literal_ quote, which you conveniently didnt bother to put in your post, over grasping deductions with AFAICS no real basis but your own intuition thanks.

Willamette is not specifically a 3D powerhouse IMO, it doesnt do any more flops per cycle, its a clock monster... like any modern CPU (except PowerPC/G4, but then... thats a bit of a dog). If Mustang cant keep up in clock its fucked, if they can their market share will keep groing.

Articles are nice, but with no benchmarks or even inside information to back them up they are just so much hot air.

"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 .35 micron PII overclocked to 333 gives the exact same performance as a 333 MHz .25 micron PII."
I agree, but then thats the only thing AMD has to do to be able to keep up... get high yields in high frequency bins.