Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Differentiable Dithering

peterstefek.me

Post reply on HN
Print view View original

41–50 of 51 posts

Re: Differentiable Dithering

#41

Post by MiroF »

tonic_section wrote: post #39
MiroF wrote: post #33

Earlier quoted context omitted.

> entirely differentiable image compression pipeline Depending on what is meant by entirely differentiable, this might be impossible without relaxation. ie. you can't differentiate through the quantization step

There are a couple of solutions which work empirically - as you mentioned, one solution is a dithering-like differentiable relaxation where uniform noise is added, which simulates quantization, or just to ignore the quantization operation when taking gradients, essentially treating it as an identity operation in the backward pass.

But how do you optimize the lossless encoding of the quantized latent space? ie. how do you tell the encoder to produce something that can be well encoded, given that the encoding is a bunch of discrete steps.

Re: Differentiable Dithering

#42

Post by underanalyzer »

dbaupp wrote: post #13

Very interesting! This seems somewhat similar to the recently published GIFnets[1]. However, I believe GIFnets is training a reusable network to a predict palettes, and pixel assignments, while this post is focusing on optimising the "weights" (i.e. pixel values) for a single image. I wonder if the loss functions from GIFnets could be applied to this single-image approach to potentially solve the banding problem via…

That's interesting! One thing I was surprised about is that they don't address optimizing the palette and dither pattern across time (b/c most gifs are animated). This feels to me like it would be really interesting and a hard problem for traditional algorithms. They do mention it as a possibility for future work at the end tho. They also seem to have separate losses for the palette net and the dither net instead of just adjusting both to optimize a general image quality metric (although it does look like they have some kind of perceptual loss, it's just not the only objective)

Re: Differentiable Dithering

#43

Post by tonic_section »

MiroF wrote: post #41
tonic_section wrote: post #39

Earlier quoted context omitted.

There are a couple of solutions which work empirically - as you mentioned, one solution is a dithering-like differentiable relaxation where uniform noise is added, which simulates quantization, or just to ignore the quantization operation when taking gradients, essentially treating it as an identity operation in the backward pass.

But how do you optimize the lossless encoding of the quantized latent space? ie. how do you tell the encoder to produce something that can be well encoded, given that the encoding is a bunch of discrete steps.

Usually the lossless encoding is offloaded to a standard entropy coder, e.g. arithmetic, ANS, etc. because these approach the theoretical minimum rate given by the source entropy pretty closely, so there wouldn't be a point building a fancy differentiable replacement.

Re: Differentiable Dithering

#44

Post by MiroF »

tonic_section wrote: post #43
MiroF wrote: post #41

Earlier quoted context omitted.

But how do you optimize the lossless encoding of the quantized latent space? ie. how do you tell the encoder to produce something that can be well encoded, given that the encoding is a bunch of discrete steps.

Usually the lossless encoding is offloaded to a standard entropy coder, e.g. arithmetic, ANS, etc. because these approach the theoretical minimum rate given by the source entropy pretty closely, so there wouldn't be a point building a fancy differentiable replacement.

That makes sense, I don't think I stated my question very clearly: how do you control/optimize the entropy of the latent space?

ie. what stops the network from laundering all of the information for reconstructing the image through a super high entropy latent space that is hard to code but allows it to reconstruct perfectly

e: I guess I should just get up to date by reading some papers

Re: Differentiable Dithering

#45

Post by MiroF »

tonic_section wrote: post #38
MiroF wrote: post #30

Earlier quoted context omitted.

> any guarantees on the output of any particular image though You don't have any guarantees with this non-convex optimization. I think most of these methods would work OK on out-of-domain data.

In terms of the decoded image, yes - it's very unlikely you would get something substantially different from the original image. But in terms of the bitrate it's not hard to find examples where the compressed bitrate can be several standard deviations above the average bitrate on the training set - see e.g. the last example here: https://github.com/Justin-Tan/high-fidelity-generative-compr... (Lossy) neural compressi…

Those are very cool examples and of considerably higher quality+bitrate than when I last tuned into this field half a year ago.

Unrelated, but I actually recognize your name from Github - I guess deep image compression is a pretty small space.

Re: Differentiable Dithering

#46

Post by MiroF »

underanalyzer wrote: post #35
MiroF wrote: post #31

Earlier quoted context omitted.

> more optimized jpeg The thing about compression is that there is no single "more optimized" knob - there's a bunch of different tradeoffs. Want a compression algo that can compress existing images to smaller sizes than JPEG? You can already do that with neural image compression. Want a compression algo that can decode that compressed image in 0.01 seconds? You need JPEG.

Sorry I could have been more specific. By more optimized jpeg I meant better perceptual quality (again subjective) within the confines of what a jpeg decoder could understand. To co opt your knobs analogy I imagine each of the steps of a complex image compression pipeline comes with its own knobs each with its own tradeoffs. The dream here would be to tune all those knobs at the same time to optimize some sense of qu…

The problem here is that the JPEG decoder is not differentiable.

Re: Differentiable Dithering

#47

Post by Const-me »

Last time I did dithering was for Polyjet 3D printers. The problem is substantially different from what’s in the article.

The palette is fixed, as the colors are physically different materials. The amount of data is huge, an image is a layer and the complete model has thousands of layers, because 3D.

I implemented a 3D-generalization of ordered dithering https://en.wikipedia.org/wiki/Ordered_dithering The algorithm doesn’t have any data dependencies across voxels, the result only depends on source data, and position of the voxel. I did it on GPU with HLSL shaders, it takes a few seconds to produce thousands of images.

Re: Differentiable Dithering

#48

Post by tonic_section »

MiroF wrote: post #44
tonic_section wrote: post #43

Earlier quoted context omitted.

Usually the lossless encoding is offloaded to a standard entropy coder, e.g. arithmetic, ANS, etc. because these approach the theoretical minimum rate given by the source entropy pretty closely, so there wouldn't be a point building a fancy differentiable replacement.

That makes sense, I don't think I stated my question very clearly: how do you control/optimize the entropy of the latent space? ie. what stops the network from laundering all of the information for reconstructing the image through a super high entropy latent space that is hard to code but allows it to reconstruct perfectly e: I guess I should just get up to date by reading some papers

The objective function used in these lossy neural compression schemes usually takes the form of a rate-distortion Lagrangian - the rate term captures the expected length of the message needed to transmit the compressed information and the distortion term measures the reconstruction error. So it wouldn't be able to cheat like in your example, because this would incur a high value of the loss through the rate term.

Re: Differentiable Dithering

#49

Post by uoaei »

MiroF wrote: post #33
londons_explore wrote: post #2

> A pipedream would be an entirely differentiable image compression pipeline where all the steps can be fine tuned together to optimize a particular image with respect to any differentiable loss function. Neural Image Compression? https://arxiv.org/abs/1908.08988

> entirely differentiable image compression pipeline Depending on what is meant by entirely differentiable, this might be impossible without relaxation. ie. you can't differentiate through the quantization step

Formulate it in terms of probabilistic programming, and you will essentially be able to do exactly that.

Re: Differentiable Dithering

#50

Post by underanalyzer »

steerablesafe wrote: post #8

It's a very interesting approach, however once you have the probability distribution for each pixel, independent random sampling produces a poor dither pattern compared to Floyd-Steinberg or other error diffusion approaches. I think once you have the target distributions then maybe you can combine the sampling with some error diffusion approach. The idea is to make the sampling of neighboring pixels negatively correl…

Although I agree with the sentiment I am going to point out for fun that the algorithm does not have to assign probabilities less than 1. Technically a solution like Floyd steinberg produces is in the search space. You would just need the right objective to motivate it
Post reply on HN