Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Already on GitHub? Sign in to your account

Implement trellis quantization #3

Closed
fbossen opened this Issue Feb 27, 2014 · 11 comments

Comments

Projects
None yet
8 participants
Contributor

fbossen commented Feb 27, 2014

Trellis quantization is an adaptive quantization technique that select the set of levels in a transform block that minimises a rate-distortion metric. See http://en.wikipedia.org/wiki/Trellis_quantization

An adequate distortion metric should be defined for such optimization. A weighted MSE metric may be considered.

An initial implementation should consider only the baseline entropy coding scheme of JPEG. Later refinements may consider progressive entropy coding modes.

@fbossen fbossen was assigned by bdaehlie Feb 27, 2014

gcp commented Mar 5, 2014

You probably considered this already, but right now at least for typical digital camera pictures, Adobe's JPEG encoder seems to outperform ijpeg by fairly large margins.

One of the interesting things that you can see on the files it makes are the quantization tables. They're entirely different from the gradually increasing zig-zag that ijpeg makes. They're also not image-dependent (source: http://www.dfrws.org/2008/proceedings/p21-kornblum_pres.pdf), so that removes a potential layer of complexity.

http://www.impulseadventure.com/photo/jpeg-quantization.html
http://www.impulseadventure.com/photo/jpeg-quantization-lookup.html?src1=10318

As far as I can tell, this is most likely exactly to do trellis quantization on the results.

roytam1 commented Mar 12, 2014

I wonder if trellis quantization will work in optimizing jpeg files (not creating new jpeg files).

frkay commented Mar 19, 2014

@gcp Are you suggesting it would be wise to retrieve the quantization tables used by Adobe Photoshop for its different quality levels and use these instead of the current scaling formula applied to the reference quantization tables from Annex K?
And what about JPEGmini isn't it building ad-hoc quantization table?

Member

pornel commented Mar 19, 2014

Do you have any other sources about Trellis quantization other than Wikipedia article and posts it links to?

I'm interested in implementing this, but I'm not sure I quite get it.

roytam1 commented Mar 19, 2014

You may have a look on x264 note.
http://akuvian.org/src/x264/trellis.txt

Member

pornel commented Mar 19, 2014

Thanks, I've seen that in the Wikipedia article, but it's too jargon-dense for me.

gcp commented Mar 19, 2014

@frkay I'm not sure if just using those tables will give you any gain without trellis. Trying should be easy, though.

Building quantization tables per image is possible but an extra variable and hence another level of extra complexity. There are papers on how to do this, but I'd consider it a separate issue from trellis which can be independently investigated.

Member

bdaehlie commented Mar 19, 2014

@pornel Frank is implementing trellis quant for mozjpeg, he's working on it now.

ace-dent commented Apr 9, 2014

Two fairly well known papers, related to this:

brunogm0 commented Apr 9, 2014

Well the patents on the second one expire in 2010.
On Apr 9, 2014 4:37 AM, "Andrew" notifications@github.com wrote:

Two fairly well known papers, related to this:

Extending RD-OPT with Global Thresholding forJPEG Optimization
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.3520&rep=rep1&type=pdf
DCTune: A TECHNIQUE FOR VISUAL OPTIMIZATION OF DCT QUANTIZATION MATRICES
FOR INDIVIDUAL IMAGES.
http://vision.arc.nasa.gov/publications/sid93/sid93.pdf

The patents on the first expired in 2010.
http://www.google.com.mx/patents/US5724453

@bdaehlie bdaehlie modified the milestone: v2.0 May 7, 2014

@bdaehlie bdaehlie added the enhancement label May 7, 2014

Member

bdaehlie commented May 10, 2014

Trellis branch merged to trunk.

@bdaehlie bdaehlie closed this May 10, 2014

@pornel pornel pushed a commit to pornel/mozjpeg that referenced this issue Apr 28, 2016

@dcommander dcommander SSE2 SIMD implementation of Huffman encoding
Full-color compression speedups relative to libjpeg-turbo 1.4.2:

2.8 GHz Intel Xeon W3530, Linux, 64-bit:  2.2-18% (avg. 9.5%)
2.8 GHz Intel Xeon W3530, Linux, 32-bit:  10-25% (avg. 17%)

2.3 GHz AMD A10-4600M APU, Linux, 64-bit:  4.9-17% (avg. 11%)
2.3 GHz AMD A10-4600M APU, Linux, 32-bit:  8.8-19% (avg. 15%)

3.0 GHz Intel Core i7, OS X, 64-bit:  3.5-16% (avg. 10%)
3.0 GHz Intel Core i7, OS X, 32-bit:  4.8-14% (avg. 11%)

2.6 GHz AMD Athlon 64 X2 5050e:
Performance-neutral (give or take a few percent)

Full-color compression speedups relative to IPP:

2.8 GHz Intel Xeon W3530, Linux, 64-bit:  4.8-34% (avg. 19%)
2.8 GHz Intel Xeon W3530, Linux, 32-bit:  -19%-7.0% (avg. -7.0%)

Refer to #42 for discussion.  Numerous other approaches were attempted,
but this one proved to be the most performant across all platforms.

This commit also fixes #3 (works around, really-- the clang-compiled version
of jchuff.c still performs 20% worse than its GCC-compiled counterpart, but
that code is now bypassed by the new SSE2 Huffman algorithm.)

Based on:
mayeut/libjpeg-turbo@2cb4d41
mayeut/libjpeg-turbo@36c94e0
f3a8684
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment