Lepton image compression: saving 22% losslessly from images at 15MB/s

Hi Daniel, very cool project! I am interested in hearing your thoughts on alternative image formats / compression methods.

WebP is very promising (also based on VP8) for lossless and lossy compression. Have you considered using it to compress PNGs in the same way Lepton is compressing JPGs? Odds are it wouldn't be bit-perfect though (despite being pixel-perfect).

Also interested in hearing about the tradeoffs between server-side decoding and client-side. Not to keep focusing on it, but WebP has native support in Chrome and javascript decoders for everything else.

I think it is a very exciting time for image formats with several promising new ones on the way (WebP, FLIF, maybe BPG but possible legal issues).

How much better do you think it could get with JPEGs encoded with Lepton in mind?

I'd love to have something like this for archiving DVD ISOs though, where the VOBs are compressed with old-school MPEG.

Is JPEG, PNG, etc a container format that could use arbitrary compression, like MKV? Or do we need a brand new format.

Indeed. In one project where I converted jpegs to webp I saw around 70% savings at similar quality. This was on Android where it's fully supported. On the web pretty much only Chrome supports it, I'm not sure why Firefox, IE and Safari are hesitant.

All that is true, but it misses out a key point: Lepton is risk-free.

I could re-encode all of my JPEG photos with a better codec, but the problem is that then they have gone through a lossy compression scheme twice: once with JPEG, and once with the new codec. This could ruin the image quality on some photos, giving them nasty artefacts.

The newer codecs might even be hindered further by the fact that they are being asked to compress an image that's been JPEG'd. I don't think any of the codecs you mentioned are tuned to work their best with image data that already has been butchered by JPEG. They expect to be given the 'pure' original image. This may well cause the codec to perform worse than expected.

Using Lepton gives none of these risks, since jpeg<->lepton is lossless. I could throw away all the JPEGs afterwards, safe in the knowledge that if I want to go back, I can.

Also, it's not really true that JPEG has been left to rot. There are lots of programs available that greatly improve upon the basic JPEG compression, while still outputting a JPEG file that any compliant decoder can read. And there's an even simpler way to shrink your photo file sizes - just drop the JPEG quality level slightly. Most cameras and programs default to a very high quality value. Dropping the default by even a tiny amount can produce remarkably smaller files, and you'll probably never notice the miniscule image quality loss.

I suspect that JPEG is so popular because it is 'good enough'. Most people and programs don't care so much about squeezing out smaller files, so they'll keep using JPEG regardless.

Yes, it should all just switch to FLIF

http://flif.info/

perhaps BPG is better? By the great Fabrice Bellard

http://bellard.org/bpg/

Actually, high quality JPEGs are just as good as BPG, VP8, etc:

https://people.xiph.org/~jm/daala/revisiting/subset1_psnrhvs...

so when you use a better encoder like mozjpeg, JPEG is actually competitive with the newest formats, given enough quality

it gets slightly grainier results with blocking artifacts, but BPG and WebM look like they had a painting algorithm blur out all of the details

Yes and no. It's not a lossless way to encode an image, but the Lepton step itself doesn't add any loss that wasn't already present in the JPEG to begin with, and it generates a smaller file overall.

I admire them because they certainly considered the pros and cons of doing so, and decided that they feel secure enough in their market position and prefer to give this back to the open source community

Pretty much every modern company safes tremendous amounts of money from open source (Linux and upwards in the stack), and so the OSS community should rightly be considered a STAKEholder.

The share vs stakeholder obsession in the space of large companies and corporations represents a lot that's wrong with our current markets.

--

Also, the only upside to open sourcing this is getting other involved in development. I just tested on 10k images, and the promise both on compression rate and bit parity after decompression holds true.

Seems to be a pretty stable product, so the that motivation is probably only miniscule.

They are a private company, they can actually ask their shareholders how they wish them to act.

"Dropbox management is obligated by law to act in the best interests of their shareholders, i.e. to make them as much profit as possible." - no they are not.

http://www.nytimes.com/roomfordebate/2015/04/16/what-are-cor...

> Dropbox management is obligated by law to act in the best interests of their shareholders, i.e. to make them as much profit as possible.

Can you cite the law which you believe makes that obligation?

The reason you can't is because it's not actually a legal requirement and the reason is obvious: it's hard to say what the best interest is over all but the shortest time frame:

https://en.wikipedia.org/wiki/Business_judgment_rule

Dropbox's management might argue that they benefit more from open-source than they're giving away, that this kind of favorable attention will help them hire the top engineers who make far larger contributions to their bottom-line, that the pricing models are complex enough that this just doesn't matter very much, etc. Absent evidence that they're acting in bad faith, it's almost impossible to say in advance whether those arguments are right or wrong.

Even if that was their obligation (which it's not, as others have pointed out), there's no reason to believe that keeping the algorithm proprietary would be more profitable. They're not handing a critical capability to their competitors (competing with Dropbox isn't fundamentally about cheap storage). They don't have the infrastructure to licence the algorithm (who should they licence it to? For how much? Under which terms? Those are not simple questions to answer.)

Releasing it freely allows it to work its way into browsers, allowing Dropbox to serve up the smaller images directly to users, saving money on bandwidth. It allows other users to contribute improvements. It markets Dropbox as a desirable place to work for engineers.

Not obviously less profitable that the opposite.

You also open source if it's in your best interest for something to become the 'standard'.

In google there is a regret that they didn't open source a lot of stuff, because it ends up being reproduced outside of google in some form. The open source companies have an advantage in hiring and overall advancement of their product by using the open source version whatever their internal version was.

You also see it in facebook's open source initiatives, like react, buck, haxe and so on.

> Either that or they are using this to attract engineers.

On a related note (I can't speak for Dropbox specifically) there are many engineers who desire their work to be open source for their own motivations, and when it's not a significant business risk to do so, nice companies will allow it.

So it works on two fronts, as a "hey, we'll let you open source your stuff" and a "hey, we've got people here who care about and contribute to open source."

I don't think they're compressing this and decompressing it client side. At least I didn't get that impression from the article.

You're correct ofc, download costs = 10 months of storage.

> season 1 pretty much wiped "making the changes world a better place" from the lingo of SV companies

Did it really?

Any word on when that would be implemented?

The size difference between "high quality" jpeg and lossless compressed TIFFs can be quite significant - so I it might not be feasible to use eg. TIFF for archiving. And jpegs might very well be "good enough".

Eg. just tested on a small 10MP Sony ARW raw image - the raw file is 7MB, the camera jpeg is 2.3MB, and a tiff compressed with LZW is 20MB (uncompressed 29MB). The raw tiff run through lzma is 9.3MB. But either way, if ~7MB is the likely lossless size, if the JPEG is good enough, at ~2.3MB it's a pretty big difference, if we're talking petabytes, not megabytes.

(I'll get around to testing lepton on the jpegs shortly)

So the weird thing is that we're not only a lab, but also a web tool. We have the files backed up in a standard format in one place, but delivering 1024x1024x128 cubes of images over the internet has been tricky. We don't need people to always view them at full fidelity, just good enough.

We tried JPEG2000, which was better quality per a file size, but the web worker decoder was slower than the JPEG one adding seconds to the total download/decode time.

EDIT: We're currently doing 256x256x256 (equivalent to a 4k image) on eyewire.org. We're speeding things up to handle bigger 3D images.

EDIT2: If you check out Eyewire right now, you might notice some slowdown when you load cubes, that's because we're decoding on the main thread. We'll be changing that up next week.

Some TIFF-derived container is the most common representation. But note even these could use JPEG/J2K if desired.

Most microscopy images are stored uncompressed or with lossless compression. But unfortunately this doesn't scale with newer imaging modalities. Here's two examples:

Digital histopathology. Whole-slide scanners can create huge images e.g. 200000x200000 and larger. These are stored using e.g. JPEG or J2K in a tiled BigTIFF container, with multiple resolution levels. Or JPEG-XR. When each image is multiple gigabytes, lossless compression doesn't scale.

SPIM involves imaging a 3D volume by rotating the sample and imaging it from multiple angles and directions. The raw data can be multiple terabytes per image and is both sparse and full of redundant information. The viewable post-processed 3D image volume is vastly smaller, but also still sparse.

For more standard images such as confocal or brightfield or epifluorescence CCD, lossless storage is certainly the norm. You don't really want to perform precise quantitative measurements with poor quality data.

Thanks for the info! See my comment above.

Thanks for the info, see my response below.

Sounds like the "content aware fill" algorithm [1], only for small scale features that are somehow stitched onto the low-resolution image

[1] http://www.logarithmic.net/pfh/resynthesizer

> I really do wish that Rust would provide nice alignment guarantees (eg 32 byte) without depending on customizing the allocator, and builtin, safe, SIMD instructions

Same could be said about C/C++. I'm guessing the answer is much simpler: the author(s) are comfortable with C++. And they probably don't deploy much rust code yet.

I wonder if they use a rolling checksum too, to avoid duplicating a complete file if only a view bytes shifted (for example adding a line of text in the beginning of a file)

The backup tool bup (https://github.com/bup/bup) does this.

WebP is switching to rANS: https://chromium-review.googlesource.com/#/c/338781/

Here is a superfast implementation of rANS: https://github.com/jkbonfield/rans_static

Oh what I was imagining was more like if I was watching a news broadcast and so all I care about was the news anchor person, and the main on screen grapic/text. If you Compress down other things like the table or the background or wrote an algorithm to selectively stream resolutions tied to the object streamed instead of the frame streamed. Is that a viable form of "compression" using existing computer vision tech?

Very cool! if anyone who comes across this particular thread knows about papers/research being written about this topic, I'd be very interested to learn more.

Thank you very much for the extra details mappu! That answers my question :-).

Now I get very interested in writing a FUSE for that http://www.cs.nmsu.edu/~pfeiffer/fuse-tutorial/

"Illegal"? Wut?

It's not illegal, it's just dumb. Sure, you could implement your entire C++ application inside the `std` namespace, and I'm sure it'd work fine, but you /shouldn't/. If you're going to start a project, at least google the name first.

I think you are explaining how both lossy and lossless compression work without explaining how this does it differently.

I can't read the article due to technical constraints, but understand that e.g. JPEG has a lossy quantisation pass followed by a lossless encoding/compression pass of the result of the first stage. If they're reproducing bit-identical result to the input JPEG, it must be a (very good) optimisation of the latter stage. [How'd I do?]

Impressive work, Daniel! Do I understand correctly that any image prediction for which the deltas are smaller in absolute value than the full JPEG/DCT coefficients would offer continued compression benefits? As in, if you could "name that tune" to predict the rest of the entire image from the first few pixels, the rest of the image would be stored for close to free (and if not, it essentially falls back to regular JPEG encoding).

If that's the case, then not only could we rely on the results of everything we've decompressed so far to use for prediction (which is like one-sided image in-painting), but we also could store a few bits of semantic information (e.g. from an image-net-based CNN, from face detection) about the content of the original image before re-compression, and use that semantic information for prediction as well via some generative model. All of this would obviously be trading computation for storage/bandwidth, but it this seems like an exciting direction to me. Again, nice work.

> Luckily it might look like snow from a television set rather than a typical image produced by a camera.

That would actually compress rather well. A hard to compress random image would not look like TV snow (white dots, with space between them), but rather randomly colored dots that are continuous in the image.

On average, any lossless compression scheme must have >= 1x compression. Lossy compression schemes can have less (since they're discarding information), and lossless compression schemes certainly can average out to > 1x (this is trivially observable by taking any 1x-average scheme and adding a fixed-length header to the output).

Thanks. I posted that before trying out Lepton not realizing the artifact is no longer a jpg.

It's a joke, as evidenced by:

> LenPEG compresses the image into a file of minimal size: one bit.

"When presented with an image, the LenPEG 3 algorithm uses the following steps:

Is the image Lenna? If yes, delete all other data on the computer's storage devices. If no, proceed to the next step..."

It's a "joke". Not a very funny one, though.

It's a joke.

LMAO - yes, Dropbox, please run LenPEG compression on your production env!

Anyways...

Part of ffmpeg open-source library

http://www.ffmpeg.org/~michael/ffv1.html

Ah, my bad. Disregard everything :)