Image specific quantization tables

[jrmsmith]

I would like to call your attention that this patent for optimizing quantization tables [image specific] have expired:

https://www.google.com/patents/US5724453

The paper can be found here:

http://www.minds.wisconsin.edu/bitstream/handle/1793/59942/TR1257.pdf?sequence=1

The source code can be downloaded here:

http://pages.cs.wisc.edu/~ratnakar/rdopt.html

I have used the software in the past [before the creation of mozjpeg] with quite good results. If this algorithm is not yet implemented by mozjpeg, I believe that this would be a quite useful addition.

Best regards,
John Smith.

[kornelski]

Nice! Makefile and the C program from 1995 just worked on a Mac :)

And it really improves quality:

convert kodim19.png kodim19.ppm
./rdopt -numtables 2 -im ./kodim19.ppm -rgbtoycc
Command> qfile tab1
Command> bpp 1.0
Command> quit
mozjpeg/cjpeg -sample 1x1 -dct float -optimize -qtables tab1 -outfile kodim19-rdopt.jpg ./kodim19.ppm
mozjpeg/cjpeg -sample 1x1 -dct float -optimize -quality 91 -outfile kodim19-mozjpeg.jpg ./kodim19.ppm
./dssim kodim19.png kodim19*
0.001707    kodim19-mozjpeg.jpg (116432 bytes)
0.001669    kodim19-rdopt.jpg (116382 bytes)

File made with rdopt qtable is both smaller and higher-quality.

[CoolOppo]

Wow, that's exciting news! I really hope somebody generous enough implements this into mozjpeg.

[CoolOppo]

@pornel why didn't you specify the -quality parameter with the rdopt quantization table?

[kornelski]

@CoolOppo -qtables controls quality in that case.

[stefek99]

File made with rdopt qtable is both smaller and higher-quality.

(emphasis mine)

On my screen and I cannot tell much difference I wonder - https://www.google.com/search?q=how+to+measure+image+quality (excuse me asking a potentially silly question)

EDIT: https://github.com/pornel/dssim

This tool computes (dis)similarity between two (or more) PNG images using algorithm approximating human vision.

[waldoj]

Yay! Bravo to @jrmsmith for calling this up and to @pornel for a speedy test implementation. :)

[jrmsmith]

Apparently there is even a better algorithm that doubles average size savings: Joint Optimization of Run-Length Coding, Huffman Coding, and Quantization Table With Complete Baseline JPEG Decoder Compatibility.

Unfortunately, it is patent encumbered probably until 2024: https://www.google.com/patents/US7570827

[waldoj]

Well, just open another ticket and label it with inyear=2024. ;)

[CoolOppo]

@stefek99 There are a lot of ways to compare an image to the original to determine the quality. To name a few:

-PSNR (Peak Signal to Noise Ratio)
-PSNR-HVS (Peak Signal to Noise Ratio - Human Visual System)
-SSIM (Structural Similarity)
-MS-SSIM (Multi Scalar? Structural Similarity)

More examples of quality metrics:

https://en.wikipedia.org/wiki/Video_quality#Examples

[mattrco]

Is this currently work-in-progress? I'd be interested in running some benchmarks.

[kornelski]

I've e-mailed the author asking if he could relicense the sample code under MozJPEG-compatible license.

To run benchmarks you can get the code from here: http://pages.cs.wisc.edu/~ratnakar/rdopt.html (to combine it with mozjpeg compression — see commands from my previous comment).

[mattrco]

Thanks, I'll run it against a test corpus. Let's hope you hear from the author soon!

[JosePineiro]

It's been over a year now.
Do you have an answer from the author of rdopt?
Do you really need a license change if the patent has expired?

[kornelski]

I've been asking about it, but I was getting redirected from department to department. Seems like nobody's sure who owns what and who is responsible.

I need the license to use the existing code. I could write new code from scratch (which I'll probably do, but don't hold your breath).

[bydbest]

any update on this ?

[kornelski]

If someone wants to help, try implementing this algorithm:

https://pdfs.semanticscholar.org/2383/e0f04cbdc5036155e8275bbbaa2b09a00359.pdf

[bydbest]

i have installed mozjpeg and as mozjpeg is replacement of libjpeg so be default imagemagick will start using mozjpeg or we need to change something ?? how to check imagemagick is using libjpeg or mozjpeg ?

[kornelski]

@bydbest This issue is not about installation of MozJPEG. So please open another issue if you want to discuss installation.

---

It depends how imagemagick was built and whether you've installed mozjpeg in addition to system-wide libjpeg, or replaced it.

Most likely it will not use MozJPEG, and you will have to recompile imagemagick specifically telling it to use mozjpeg instead of libjpeg.

[chuck2004]

If someone wants to help, try implementing this algorithm:

https://pdfs.semanticscholar.org/2383/e0f04cbdc5036155e8275bbbaa2b09a00359.pdf

Hi,
it looks like the author has already implemented the algorithm (or tried to do so) in old cjpeg. He incorporated RD-OPT into his framework and named QCLIC.
Viresh Ratnakar has an ftp directory on UW-Madison.
https://ftp.cs.wisc.edu/pub/ratnakar/ or archive.org

gswin64c.exe -sDEVICE=pdfwrite -dPDFSETTINGS=/prepress -dCompatibilityLevel=1.3 -dNOPAUSE -dBATCH -sOutputFile=rdopt2.pdf rdopt2.ps
So this is the paper mentioned earlier.

Extending RD-OPT with global thresholding for JPEG optimization

It is worth taking a closer look at the dissertations he wrote.

[MMDBMS.ps]
1996-03-29
15 pages
Quality-Controlled Compression of Sets of Images (extended abstract)

[thesis.ps.gz / main.ps]
1998-11-24
160 pages
QUALITY-CONTROLLED LOSSY IMAGE COMPRESSION

This thesis presents the QCLIC (Quality-Controlled Lossy Image Compression) framework as a fundamental way of using lossy image compression to meet application needs while satisfying storage and bandwidth constraints.

[rdopt.ver3.0.aux.tar]
1997-12-02
include 2 versions of "cjpeg_thresh"
[cjpeg_thresh] 1997-12-03 00:49

This file contains modified/added files for IJG's cjpeg, to make it read and apply thresholding tables produced by rdopt.

This file contains jcthresh.h and jcthresh.c. It modifies 2 files in IJG encoder.
You can compare the changes made to v 6 IJG and make a diff.

Independent JPEG Group's JPEG software
Version 6 2-Aug-95
http://ftp.funet.fi/pub/amiga/graphics/formats/jpeg/jpegsrc.v6.tar.gz

· cjpeg.c diff
· jcdctmgr.c diff

Perhaps these informations will be useful to implement this algorithm in mozjpeg.

The information that RD-OPT can be implemented in the DCTune algorithm is also interesting [thesis.ps.gz / main.ps]:

That is, RD-OPT can be used for efficient quality-control for JPEG, in the QCLIC framework. RD-OPT can work with any of the distortion-based quality metrics described in Section 2.2, and with several other quality metrics. For example, RD-OPT can also be used with the quality evaluations used by Watson in [Wat93], which were based on extensive psycho-visual experiments done to evaluate the visibility of the 64 DCT basis functions.

[Wat93] Watson, A. B. DCT quantization matrices visually optimized for individual images.
· DCTune: A Technique for visual optimization of DCT quantization matrices for individual images (1993)
· DCTune perceptual optimization of compressed dental X-Rays (1997)

---

Work on the project has been suspended, but maybe it would be worth combining these two algorithms into one whole in mozjpeg?

@viresh-ratnakar , you created this program?

· Viresh Ratnakar website (work for google?)

Best regards

[viresh-ratnakar]

Hey, yes, RD-OPT was my PhD thesis work in the mid-90s. Sorry, I haven't been paying much attention to it lately, but it only just caught my eye that the patent has expired. That's great news! I would love for it to be integrated into open source software. I don't think I have the old code available (and it might not be right to just use it anyway). Someone (else :-)) would have to take the lead, but I can help.

--Viresh

[JosePineiro]

@viresh-ratnakar

Good news!!

[chuck2004]

💪

RD-OPT was my PhD thesis work in the mid-90s

· QUALITY-CONTROLLED LOSSY IMAGE COMPRESSION

gswin64c.exe -sDEVICE=pdfwrite -dPDFSETTINGS=/prepress -dCompatibilityLevel=1.3 -dNOPAUSE -dBATCH -sOutputFile=main.pdf main.ps

@viresh-ratnakar , how do you rate similar algorithms to that of those times? Is it worth rebuilding DcTune?

---

· NASA publications
·· Visually optimal DCT quantization matrices for individual images (1993)
·· Perceptual optimization of DCT color quantization matrices (1994)
·· Perceptual adaptive JPEG coding (1996)

---

CC @kornelski , @dcommander , @pengvado , @fbossen , @dwbuiten , @bdaehlie

[viresh-ratnakar]

Again, apologies, this was all so far back, and I stopped working on image processing/compression nearly 20 years ago.

I don't remember what DcTune was.

What I do remember is that there were some methods prior to RD-OPT that used various optimization techniques but were quite slow as they searched in the space of all possible quantization matrices. With RD-OPT, I was able to nearly meet their quality improvements (in terms of PSNR), but way faster. And yes, I do kinda remember how RD-OPT works: You just compute empirical values for bit-rates and distortions of the the 64 coefficients independently, for some range of quantization matrix entries and zeroing thresholds. Then you do Lagrangian optimization to come up with points on the near-optimal RD curve. Given the right coding context and someone familiar with that coding context, all this should be just a few 100 lines of code, so trying it out should not be too difficult. If someone can point me to the right coding context in mozjpeg, I might myself be tempted. (Caveat: I may not have the time right away).

[dcommander]

As a side note, if an automatic table selection algorithm could be made to perform reasonably well without being too disruptive to the code base, then it might be something I could consider for upstream integration into libjpeg-turbo. But I can tell you that DCTune was really slow.

[chuck2004]

Thank you @viresh-ratnakar, you're very kind.

I hope you will be contacted by the project maintainer and it would be great for Mozilla to fund your help as well.
Engineers try to reinvent the wheel when there are old designs that can breathe spirit and life into existing ones.

Who do the copyrights of RD-OPT / QCLIC belong to? To the University of Wisconsin? Maybe we could extract the project's source code and reuse it, make it open-source, if you didn't mind?

Best regards, Viresh

[viresh-ratnakar]

The copyright would be with University of Wisconsin, I suppose. I don't know how easy it would be to find the project's source code, and to figure out the permissions-chain needed to reuse it, tbh. I think it might be simpler and better to just rewrite the code.

[chuck2004]

All I can do to help with the project is find forgotten documents and share them with you. Perhaps it is worth recalling their authors? Regarding JPEG QTs (these will be the last ones, I promise)

· A Literature Review on Quantization Table Design for the JPEG Baseline Algorithm

This paper provides detailed survey on various approaches used to generate the image adaptive quantization table for JPEG baseline algorithm. A detailed analysis is made on various methods such as rate-distortion approach, human visual system approach and meta-heuristics approach used to generate JPEG quantization table.

The papers below show how RD-OPT can be improved.

· Transform Image Coding with Global Thresholding: Application to Baseline JPEG

· Fast JPEG rate control
@ValeryAnisimovsky , @szavalishin

· Fast Control of JPEG Compression Rate
@safonovilya , @katetolstaya

---

Other papers:

· Context Adaptive Space Quantization for Image Coding
@jeffman

· Nature Inspired JPEG Quantization Optimization
@osmarluiz

Best regards

[jeffman]

Mine unfortunately goes out of spec and isn't implementable in JPEG.

I worked very closely with the author of "Joint Optimization of Run-Length Coding, Huffman Coding, and Quantization Table With Complete Baseline JPEG Decoder Compatibility". They have some related works you may be interested in:

"Quantization Table Design Revisited for
Image/Video Coding", a method dubbed OptD which out-performs RD-OPT, and from what I remember it was also significantly faster;

"An Efficient DCT-Based Image Compression System Based on Laplacian Transparent Composite Model", an improvement on the above using a customized probability distribution.

I do not know if any of the above is covered by patents.

[chuck2004]

I found the source code.

[kornelski]

It's great to see you here @viresh-ratnakar! I think it would be fantastic if you could contribute a modern version of RD-OPT to libjpeg-turbo/MozJPEG!

[kornelski]

I've contacted Wisconsin University a few years ago about RD-OPT copyright, but unfortunately they weren't able to track down who's would be responsible for releasing it. While I'm impressed that the 1995 code still works, I think it may be quicker and easier to rewrite it than try to make the university relicense the old code, especially that they're under no obligation to do so.

[chuck2004]

In addition to Viresh, Professor Miron Livny also worked on the code. Now there is a CTO at the Wisconsin Institute for Discovery. I think Mozilla lawyers should contact him and formally request permission to use the code from wisc.edu. If they are considerate and polite, they will surely get approval. 😃

The question is, will Viresh agree as well?

Miron Livny
https://wid.wisc.edu/people/miron-livny/
http://pages.cs.wisc.edu/~miron/

[viresh-ratnakar]

Oh, I would welcome it!

But, as I said before (and I agree with @kornelski there), it may be better to re-implement rather than chase permissions from UW.

I need to read up on the current state a bit. But if someone can spell it out for me, it will be helpful: What are these three variants of the jpeg library these days: libjpeg vs libjpeg-turbo vs MozJPEG -- which one is the best entry point for adding RD-OPT to? And what would be a skeleton architecture for adding RD-OPT (what code files, functions, flags would need tweaking)?

[zvezdochiot]

Hi @viresh-ratnakar .

MozJPEG will always be able to borrow code from libjpeg, since it came about as a replacement for libjpeg, repeating its functions, but including additional analyzers for dct-generated coefficients. Libjpeg-turbo are firstly fast implementations of libjpeg decoding methods.

[dcommander]

I need to read up on the current state a bit. But if someone can spell it out for me, it will be helpful: What are these three variants of the jpeg library these days: libjpeg vs libjpeg-turbo vs MozJPEG -- which one is the best entry point for adding RD-OPT to? And what would be a skeleton architecture for adding RD-OPT (what code files, functions, flags would need tweaking)?

The Independent JPEG Group's software, AKA "libjpeg" (the colloquial but never official name for it), was the de facto standard JPEG codec in the 1990s and early 2000s. Its original purpose was to encourage convergence around the same JPEG file format (JFIF) by providing an open source codec that both proprietary and open source application developers could easily integrate in order to support this "new" format. However, after the release of libjpeg v6b in 1998, Tom Lane abandoned the project, and it stalled for nearly 10 years. In 2007, Guido Vollbeding took over the IJG and took libjpeg in a different direction, using it as a proof of concept for novel DCT algorithm tricks and JPEG format extensions that were rejected by ISO/ITU-T and that my own research revealed to be of limited utility. (Those tricks involve reducing the DCT block size in order to improve image quality, but doing so results in a lower compression ratio, so the JPEG quality has to be reduced commensurately in order to make up for that. Effectively this results in trading blocking artifacts for color banding artifacts. The tricks can also be used to produce a new mathematically lossless JPEG format, but this new format doesn't generally improve upon the existing standard JPEG lossless format or upon PNG and webp.)

libjpeg-turbo forked from libjpeg/SIMD (an early 2000s research project by Miyasaka Masaru to accelerate libjpeg v6b using MMX and SSE instructions) in 2009, primarily as a means of supporting high-speed remote display software (TigerVNC, VirtualGL, and TurboVNC.) libjpeg-turbo became its own independent project in 2010 and was soon adopted as the JPEG codec for Fedora/RHEL, which set the ball rolling for other operating system distributors to adopt it. Because libjpeg-turbo was 2-4x as fast as libjpeg (now 2-6x) and could act as a drop-in replacement for libjpeg v6b (since it maintains backward ABI compatibility with same), it eventually became the new de facto standard (with Tom Lane's blessing, in fact.) libjpeg-turbo also adopted a legacy-free approach, removing support for obsolete operating systems (MS-DOS, etc.) and non-ANSI compilers and such, and it eventually expanded into the mobile app space and received SIMD extensions for non-x86 CPUs. In more recent years, ISO and ITU-T have adopted libjpeg-turbo as an official reference implementation, making it more than just a de facto standard.

MozJPEG forked from libjpeg-turbo in 2014 in order to develop a fit-for-purpose codec that is primarily intended for lossless and near-lossless recompression of JPEG images for the web. Given that MozJPEG focuses on maximum compression at the expense of very poor compression performance, and given the need for it to be developed in a more rapid and disruptive manner than libjpeg-turbo could easily absorb, it made the most sense for the MozJPEG developers to fork libjpeg-turbo rather than to integrate with it.

I would suggest developing the patch against libjpeg-turbo. If it proves sufficiently compelling in terms of the performance vs. quality tradeoff, then I can integrate it into the next major release of libjpeg-turbo, and MozJPEG can downstream it from there. Otherwise, since MozJPEG is based on libjpeg-turbo, it will be easy to downstream the patch into MozJPEG if it isn't a good fit for libjpeg-turbo. I would not suggest developing the patch against libjpeg, since libjpeg is not widely used anymore and is not developed in the open.

[kornelski]

Agreed. libjpeg-turbo is the reference software and common codebase for MozJPEG.

If you develop for libjpeg-turbo, MozJPEG will be able to use it. Even if the implementation turns out to be not turbo-fast, it can still be merged into MozJPEG.

[Afnankhn]

Nice! Makefile and the C program from 1995 just worked on a Mac :)

And it really improves quality:

convert kodim19.png kodim19.ppm
./rdopt -numtables 2 -im ./kodim19.ppm -rgbtoycc
Command> qfile tab1
Command> bpp 1.0
Command> quit
mozjpeg/cjpeg -sample 1x1 -dct float -optimize -qtables tab1 -outfile kodim19-rdopt.jpg ./kodim19.ppm
mozjpeg/cjpeg -sample 1x1 -dct float -optimize -quality 91 -outfile kodim19-mozjpeg.jpg ./kodim19.ppm
./dssim kodim19.png kodim19*
0.001707    kodim19-mozjpeg.jpg (116432 bytes)
0.001669    kodim19-rdopt.jpg (116382 bytes)

File made with rdopt qtable is both smaller and higher-quality.

Dear kornelski,
How do you convert the image format from .png to .ppm. ?
When I convert image format using MATLAB or Python. This algorithm gives error “Premature EOF in image file” while performing optimization for images.
Kindly response

.
Thank you.

[zvezdochiot]

@Afnankhn say:

How do you convert the image format from .png to .ppm. ?

Netpbm:

• sourceforge
• github

[Afnankhn]

I use the MATLAB imwrite(___,fmt) function for format conversion. But the resultant .ppm image is not working with the above algorithm.

[zvezdochiot]

@Afnankhn say:

I use the MATLAB imwrite(___,fmt)

status = system(command)

[dcommander]

i have installed mozjpeg and as mozjpeg is replacement of libjpeg so be default imagemagick will start using mozjpeg or we need to change something ?? how to check imagemagick is using libjpeg or mozjpeg ?

mozjpeg is not a replacement for lbjpeg-turbo. mozjpeg is a highly specialized fork of libjpeg-turbo that implements several ideas for improving compression ratio at the expense of compression performance. (That expense is usually quite large.) mozjpeg is not, nor has it ever been, intended to be used as a general-purpose JPEG library. libjpeg-turbo is an ISO/ITU-T reference implementation for the JPEG standard, so it is the library that most systems/applications will use.

That being said, there is an open issue in the libjpeg-turbo issue tracker for adding RD-OPT support (libjpeg-turbo/libjpeg-turbo#629). I am not opposed to it, as long as:

• It is unencumbered by patents or incompatible licensing.
• It demonstrates clear advantages relative to the existing approach.
• The performance is not so abysmal as to be useless for common workloads
• The feature is opt-in (not enabled by default.)
• The feature can be implemented without severe disruption to the libjpeg API or architecture.

Implementing the feature in mozjpeg first would greatly facilitate implementing it in libjpeg-turbo.

In general, if the performance of this feature is within the boundaries of the performance of existing JPEG coding paths in libjpeg-turbo (with baseline being the fastest and arithmetic-coded progressive JPEG being the slowest), then I am really interested in it, because I have a downstream application (TurboVNC) that could potentially use it.

[zvezdochiot]

@dcommander say:

Implementing the feature in mozjpeg first would greatly facilitate implementing it in libjpeg-turbo.

For mozjpeg, rdopt is not really needed. ;)

[zvezdochiot]

@ValZapod say:

I do not like this

stbimmetrics -q -m ssim 99255002-300a-11e5-8fcd-4f810b0aa78b.jpg 992ee824-300a-11e5-99fe-0f56e3229c84.jpg comp.ssim.jpg.png 
0.963023    992ee824-300a-11e5-99fe-0f56e3229c84.jpg

stbimmetrics -q -m vifp1 99255002-300a-11e5-8fcd-4f810b0aa78b.jpg 992ee824-300a-11e5-99fe-0f56e3229c84.jpg comp.vifp1.jpg.png 
0.580207    992ee824-300a-11e5-99fe-0f56e3229c84.jpg

stbimmetrics -q -m shbad 99255002-300a-11e5-8fcd-4f810b0aa78b.jpg 992ee824-300a-11e5-99fe-0f56e3229c84.jpg comp.shbad.jpg.png 
0.955741    992ee824-300a-11e5-99fe-0f56e3229c84.jpg