Use libimagequant for palette generation

Issue #34 resolved
No created an issue

I've developed a library for high-quality quantization that IMHO is a big quality improvement over an old algorithm currently used by libgd (you can try it at http://tinypng.org ).

http://pngquant.org/lib/

I've managed to integrate the library with libgd at code level, but I'm not submitting a patch yet, as I haven't figured out how to link with it properly.

I'm not sure what's your approach to handling external dependencies like this. I don't have OS-level package for the library, and I'm not familiar with cmake enough to figure out how to best integrate it.

The library is BSD-licensed and could be statically linked.

What would be your approach to integrating such library? Should I create a dynamically linked library as a package? Would you just copy the code to libgd or hook it as a submodule/subrepository? Or maybe cmake could download and build static version of the library?

Comments (26)

  1. Pierre Joye

    hi!

    It looks very interesting. Thanks for thinking about gd support!

    About integrating it to GD, we still support autoconf, so if you are more familiar with this tools, I can make the CMake part. Whether it is statically linked or not is defined by the provided .a/.lib.

    However the patch for the libgd itself is relatively independent from the link mode or do you have some special initialization required?

    Btw, have you noticed the neuquant support? I was quite happy with it as well, and support alpha;

    https://bitbucket.org/pierrejoye/gd-libgd/src/2b8f5d19e0c9d68f755ccd3d57839b4d60df5a4a/src/gd_nnquant.c?at=default

    In any case, support for your library is no problem, I will see if we can do it for PHP's GD as well. However I need windows support for that, not sure how far you go with C99 tho'.

  2. No reporter

    Thanks! It's good to see GD is getting more options for palette generation.

    Neuquant algorithm is good in specific cases (images with several gradients with similar hue converted to 256 colors), but downsides of the neural network (generating unused palette entries, failing to notice colors that are only in few pixels in the image) IMHO make it a poor choice for generic conversion algorithm (but of course I'm biased :)

    The libimagequant library has a makefile already. make static produces libimagequant.a. It doesn't have any external dependencies, it's basically just gcc *.c -std=c99.

    I've hooked the library up to the existing gdImageTrueColorToPalette. Is that a good approach?

    The library will be used if HAVE_LIBIMAGEQUANT_H is defined, and if the library fails for any reason, it'll seamlessly fall back to the old code.

    https://bitbucket.org/pornel/gd-libgd/commits/10af42bdcf385e81906f71f9df32e6cbe944bb09

  3. Pierre Joye

    does have magequant various options? If yes, I would create a new function (like for neuquant).

    Binding or apps writer can then easily use one of them depending on their needs.

    Besides that, the patch looks good.

  4. No reporter

    The library has couple of interesting options:

    • speed/quality trade-off — if you can afford to burn more CPU time then you can get a bit better palette and nicer dithering. Currently I'm defaulting it to "fast" for GD, since the previous algorithm was fast.
    • option to automatically select number of colors to achieve certain quality.

    However, my main motivation is to improve PHP GD's imagetruecolortopalette() default behavior, as I wouldn't like to require everybody to update their scripts to take advantage of the improved algorithm.

    Do you think it'd be OK to add specific function for this in the future?

    Neuquant also has configurable speed/quality trade-off, so maybe a function that sets preference for both?

    gdImageTrueColorToPaletteXXX(gdImagePtr im, enum algorithm, int dither, int colorsWanted, int speed)?

    or gdImageTrueColorToPaletteSetSpeed(gdImagePtr im, int speed) + gdImageTrueColorToPaletteSetMethod(gdImagePtr im, enum pngquant_or_neuquant), etc.

  5. Pierre Joye

    Yes, I would go with two specific new functions and allow to set any available options.

    Options should have default (PNGQUANT_<option>_DEFAULT) and optional argument/options in PHP (maybe using array to avoid endless list of optional arguments).

    From an API point of view, if there are not more than 3-5 options, I would go with arguments only. If there are more (or will have more), we can create a struct that can be passed to the functions. Thoughts?

  6. No reporter

    So instead of adding many gdImageTrueColorToPalette alternatives I'm suggesting adding a function to select the preferred algorithm:

    gdImageTrueColorToPaletteSetMethod(enum method/* JQUANT, LIQ, NEUQUANT*/,
                           int speed_tradeoff /* 1-10, 0 = default speed */);
    

    Neuquant can skip every n pixels, so it could use the speed parameter as well. For the current JQUANT-based algorithm the speed would be ignored. e.g.:

    gdImageTrueColorToPaletteSetMethod(GD_LIQ, 5);
    

    For server use-case I can imagine developers wanting to reduce size of images by automatically converting them to palette, but only if it gives good-enough quality.

    gdImageTrueColorToPaletteSetQuality(int min_quality /*0-100*/, 
                                        int max_quality)
    

    This specifies quality in JPEG-like range. Number of colors will be chosen automatically to aim for max_quality. If quality of palette image ends up worse than minimum quality, then gdImageTrueColorToPalette() will leave it as true-color.

    For PHP API this could be folded into optional options array:

     imagetruecolortopalette(image, true, 256, array(
         "method"=>"neuquant", // default liq
         "speed"=>3,  // default 1 for neuquant, 3 for liq
         "min_quality"=>50, // default 0
         "max_quality"=>90, // default 100
     ));
    
  7. Pierre Joye

    I like the idea and the APIs.

    Only " If quality of palette image ends up worse than minimum quality, then gdImageTrueColorToPalette() will leave it as true-color." is not very friendly, I won't expect this function to keep the image as trueColor.

  8. No reporter

    Instead of having minimum quality setting I could expose quality achieved after remapping:

    gdImageTrueColorToPaletteSetQuality(image, int max_quality)
    int gdImageTrueColorToPaletteGetQuality(image)
    

    but that has some downsides too - to use truecolor version if quality is too low you have to do the legwork yourself, and you waste CPU time on remapping to palette of too low quality (the min_quality setting allows LIQ to abort after doing only about 30% of the work).

    gdImageTrueColorToPalette() leaves image as truecolor in other failure cases.

  9. Pierre Joye

    I understand that but the goal of this function is to return a palette image.

    What I would suggest then is to create a new function (keeping ABI/API BC) and return GD_FALSE if the requested quality cannot match the trueColor quality. This way the caller knows that the function failed and the image is still trueColor. But using the same function there is no way but testing isTrueColor again. Thoughts?

  10. No reporter

    OK, returning FALSE on failure sounds good.

    I've simply changed return type of gdImageTrueColorToPalette(), because that's harmless API change (old code will ignore return value, and since it won't be using new settings, there's no new failure case to handle)

    And as far as I know change from returning void to int won't break C ABI, because all modern platforms use register to return values when no structs are involved.

  11. Pierre Joye

    Patch looks good. Remove white spaces changes and we are good :)

    I will take care of the autconf part and port the library to windows (should not be such a big deal).

    I gave you write access to the repo, feel free to merge the PR once you are done. You may like to back port it to php's bundle GD (master only) as well, if you like to.

    Thanks for your great work!

  12. No reporter

    Great! Merged.

    Now I'm going on holiday, so please excuse me if I broke everything and disappeared for two weeks ;)

  13. Pierre Joye

    Looked at the library code.

    Is there any appealing reasons to use C99 (actually even gcc specific) but syntax sugars? It makes the port to all supported platform a real pain (not only windows).

    Any objection if I "clean" it to make it work with other compilers than gcc specific c99 support?

  14. Pierre Joye

    f.e. the inline function to_f becomes:

    inline static f_pixel to_f(const rgb_pixel px) ALWAYS_INLINE;
    inline static f_pixel to_f(const rgb_pixel px)
    {
        const float a = px.a/255.f;
        const f_pixel pxl = {
        /* a */ a,
        /* r */ gamma_lut[px.r]*a,
        /* g */ gamma_lut[px.g]*a,
        /* b */ gamma_lut[px.b]*a
        };
        return pxl;
    }
    

    same level of optimizations, or maybe even better due to const usage.

  15. No reporter

    Thanks! I'm away from my computer, so I can't check the code.

    The code for the library is in lib branch. It may be possible to rebase changes automatically.

    MSVC is the only compiler that I know of that doesn't support basic C99.

    MSVC support will definitely make it easier for Windows, but it's not necessary: mingw and cygwin compile it fine and mingw files are linkable with VC projects - for example Irfanview is going to ship with libimagequant integrated this way.

    In the lib branch I've also added option to build a DLL (I haven't tested it though)

    -- regards, Kornel

    Sent with AquaMail for Android http://www.aqua-mail.com

  16. Pierre Joye

    One thing I am not sure how to convert correctly is the rgba_as_int, is it only about packing values in a larger area? That's something I am not sure what's the best way to convert as:

                        other_items[i] = (struct acolorhist_arr_item){
                            .color = px,
                            .perceptual_weight = boost,
                        };
    

    won't work in ANSI C89. Thoughts?

  17. Pierre Joye

    Question, what is the maximum amount of color indexes supported by the library? There are rooms for cleanup&optimization if we simply use map[maxindex] instead of of map[map->colors] (or alloc)

  18. No reporter

    There's check that number of colors is <= 256, but the code would handle any number correctly.

    I've benchmarked it extensively and there's no point optimizing that bit. (and stack-allocated variable length arrays in C99 made that easy to work with :-)

    60% of time is spent in nearest_search, mostly on mispredicted branches (that function is a bit convoluted - it's like vantage point tree, except it's not a tree :)

    Most of remaining time is spent on sorting and averaging colors in mediancut (mostly memory access cost), and then a bit on Floyd-Steinberg.

    And in terms of memory use hashing for the histogram is the big one.

    -- regards, Kornel

    Sent with AquaMail for Android http://www.aqua-mail.com

  19. No reporter

    rgba as int is for comparing rgba values quickly as one int rather than 4 chars.

    and literal struct assignment is equivalent to assigning all fields at once.

    I was planning to use this for c89:

    https://github.com/mstorsjo/c99-to-c89

    except that it doesn't convert nested loops with initialisers correctly.

  20. Pierre Joye

    oh my! have to try that, almost done with the conversion but worse a try :)

    I also plan to then add MP support for the native VC11 MP implementation (same or similar macros).

    I noticed some good perf as well with well placed pragma. Do you have some tests suite? I could run them to valid my changes and to build it using PGO (profile guided optimization).

  21. No reporter

    Unfortunately the test suite I have has bunch of copyrighted pictures so I can't share.

    I'm curious to see how well VC manages. With OpenMP I see linear speedup only up to 3 cores and hyperthreading doesn't help at all :(

  22. Pierre Joye

    tested c99toc89, it works for 80% of the cases but leaves C99 stuff like int foo(int cnt, char elem[cnt]);

    Also the generated code is not that clean, I'd to go with the manual changes for now :)

  23. Log in to comment