1998.05.29 11:05 "tiffreduce.c (long)", by Tim Shaporev

This message contains source code of utility which allows to convert nearly any TIFF image to palette type. The porgram itself is much like tiffmedian (and I used tiffmdeian as a sample).

Unlike tiffmdeian this program uses my own method of color reduction. Unlike median-cut algorithm my method is semi-adaptive i.e. requires to specify in advance one parameter in the range from 0 to 50 (automatical calculation of this parameter require 5 passes onto the input image).

This method itself does not require additional memory except 768 bytes for palette (although the utility WILL require memory due to the way it is implemented - I did not even try to avoid TIFFReadRGBAImage()

I'd like to contribute the program to LIBTIFF utilities collection but main goal is another - I'd like to use this method for my thesis and want to get as much feedback as possible.

The rest of message contains source code itself.

Bye

                                Tim

/*
 * Copyright (c) 1997-1998 Tim V.Shaporev
 *
 * Permission to use, copy, modify and distribute this software
 * for any purpose is hereby granted without fee, provided that
 * the above copyright notice appear in all copies of the software and
 * related documentation.
 *
 * Note: this program utilize TIFF Reference Library "LIBTIFF" which is
 *      separate product covered by separate copyrights.
 *      The above copyright notice makes no any intention on LIBTIFF
 *      copyrights.
 *
 * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
 * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
 * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
 */
/*
 * Reduce truecolor image to palette.
 *
 * tiffreduce [-N] input output
 *     -0 - -50         - set reduction factor.
 *     -c lzw           - compress output with LZW
 *     -c none          - use no compression on output
 *     -c packbits      - use packbits compression on output
 *     -q               - quiet
 *     -r n             - create output with n rows/strip of data
 * (by default the compression scheme and rows/strip are taken
 *  from the input file)
 *
 * If the reduction factor is not specified in the command line the
 * program automatically adjust minimum value required to reduce given
 * image. Reasons to specify reduction factor explicitly are:
 * 1) Calculation of the reduction value requires time.
 * 2) Explicit reduction factor allows to restrict image quality loss
 *    (which might be intolerable after automatic reduction).
 * 3) Higher reduction values result in better compression afterwards.
 *
 * Notes:
 *
 * Main program was not optimized for either speed or memory usage;
 * its only goal is to demonstrate the method.
 *
 * The reduction scheme uses Discret Proportional Approximation for
 * RGB components where reduction factor has meaning of cube edge size
 * in color space.  For more info look into sources or ask me.
 *      tim@sierra.auriga.ru
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "tiffio.h"

#define MAX_TOLERANCE   50

#define CMAP_SIZE       256

#define streq(a,b)      (strcmp(a,b) == 0)
#define strneq(a,b,n)   (strncmp(a,b,n) == 0)

#define MAX_COLOR       256
#define COLOR_DEPTH     8

uint16  rm[CMAP_SIZE], gm[CMAP_SIZE], bm[CMAP_SIZE];
unsigned char xlat[MAX_COLOR];
int     bytes_per_pixel;
int     num_colors;
int     tolerance = -1;
int     quiet = 0;
char    *iname, *oname;
TIFF    *in, *out;
uint32  imgwidth, imglength;
uint32  rowsperstrip = (uint32) -1;
uint16  compression = (uint16) -1;
uint16  predictor = 0;

#define CopyField(tag, v) \
        if (TIFFGetField(in, tag, &v)) TIFFSetField(out, tag, v)

static char stuff[] =
"usage: tiffreduce [options] input.tif output.tif\n\
where options are:\n\
 -#             specify reduction factor (from 0 to 50)\n\
 -r #           make each strip have no more than # rows\n\
 -c lzw[:opts]  compress output with Lempel-Ziv & Welch encoding\n\
 -c zip[:opts]  compress output with deflate encoding\n\
 -c packbits    compress output with packbits encoding\n\
 -c none        use no compression algorithm on output\n\
\nLZW and deflate options:\n\
 #              set predictor value\n\
For example, -c lzw:2 to get LZW-encoded data \
with horizontal differencing\n";

static void
usage(void)
{
    fputs(stuff, stderr);
    exit(-1);
}

static int
processCompressOptions(char* opt)
{
    if (streq(opt, "none"))
        compression = COMPRESSION_NONE;
    else if (streq(opt, "packbits"))
        compression = COMPRESSION_PACKBITS;
    else if (strneq(opt, "lzw", 3)) {
        char* cp = strchr(opt, ':');
        if (cp)
            predictor = atoi(cp+1);
        compression = COMPRESSION_LZW;
    } else if (strneq(opt, "zip", 3)) {
        char* cp = strchr(opt, ':');
        if (cp)
            predictor = atoi(cp+1);
        compression = COMPRESSION_DEFLATE;
    } else
        return (0);
    return (1);
}

#define intervals(tolerance) ((255+(tolerance))/((tolerance)+1))

static void
fill_xlat(int tolerance)
{
    register k, x;
    register int N = intervals(tolerance);
    /* fill the lookup table */
    for (x=0; x<256; x++) {
        k = (x*(N+N) + 255) / 510; /* interval number */
        xlat[x] = (unsigned char)((510*k + N)/(N+N));
    }
}

static int
colorno(int r, int g, int b)
{
    register k;
    r = xlat[r]; g = xlat[g]; b = xlat[b];
    for (k=0; k<num_colors; k++) { /* look up color map */
        if (rm[k] == r && gm[k] == g && bm[k] == b) return k;
    }
    /* not found */
    if (num_colors < 256) {
        /* add the new color */
        rm[num_colors] = r;
        gm[num_colors] = g;
        bm[num_colors] = b;
        ++num_colors;
    }
    return k;
}

static int
check_colors(uint32 *raster, uint32 w, uint32 h, int tolerance)
{
    register uint32 c;
    register uint32 *row;
    register x, y;

    fill_xlat(tolerance);
    for (num_colors=0, y=0; y<h; y++) {
        for (row = raster + w*y, x=0; x<w; x++) {
            c = row[x];
            if (colorno(TIFFGetR(c), TIFFGetG(c), TIFFGetB(c)) >= 256)
                return -1;
        }
    }
    return (num_colors);
}

static int
calculate_tolerance(uint32 *raster, uint32 w, uint32 h)
{
    register k, lo, hi;
    short table[MAX_TOLERANCE+1];
    int s;

    /* collect tolerance values which produce different results */
    table[hi = 0] = intervals(0);
    for (s = -1, lo=hi=0; MAX_TOLERANCE >= ++lo;)
        if ((k=intervals(lo)) != s) {
            table[++hi] = lo; s = k;
        }

    /* Now start binary search */
    lo = -1;
    do {
        k = (hi+lo+1) / 2;
        if (check_colors(raster, w, h, table[k]) < 0)
            lo = k;
        else
            hi = k;
    } while (hi-lo > 1);
    return table[hi];
}

int
main(int argc, char *argv[])
{
    uint16 shortv, photometric;
    float floatv;
    uint32 longv;
    char *s, **argend;
    uint32 *raster, *row, code;
    unsigned char *outline;
    int x, y;

    iname = oname = NULL;
    for (argend = argv+argc; ++argv < argend;) {
        if (*(s = *argv) == '-') {
            if (s[1] >= '0' && s[1] <= '9') {
                tolerance = atoi(s+1);
                if (tolerance < 0 || tolerance > MAX_TOLERANCE)
                    usage();
            } else {
                while (*++s)
                    switch (*s) {
                      case 'c': /* compression scheme */
                        if (++argv >= argend ||
                            !processCompressOptions(*argv))
                                usage();
                        break;
                      case 'q':
                        ++quiet;
                        break;
                      case 'r': /* rows/strip */
                        if (++argv >= argend ||
                            (rowsperstrip = atoi(*argv)) < 1)
                                usage();
                        break;
                      default:
                        usage();
                        /*NOTREACHED*/
                    }
            }
        }
        else if (!iname) iname = s;
        else if (!oname) oname = s;
        else usage();
    }
    if (!iname || !oname)
            usage();

    if (NULL == (in = TIFFOpen(iname, "r")))
            return (-2);
    TIFFGetField(in, TIFFTAG_IMAGEWIDTH, &imgwidth);
    TIFFGetField(in, TIFFTAG_IMAGELENGTH, &imglength);
    if (rowsperstrip == (uint32)-1) {
        if (!TIFFGetField(in, TIFFTAG_ROWSPERSTRIP, &rowsperstrip) ||
            rowsperstrip > imglength)
            rowsperstrip = imglength;
    }
    if (TIFFGetField(in, TIFFTAG_PHOTOMETRIC, &photometric) &&
        (photometric == 0 || photometric == 1 ||
         photometric == PHOTOMETRIC_PALETTE)) {
        fprintf(stderr, "%s: Image do not need to be reduced\n", iname);
        return (-5);
    }
    {
        char errmsg[1024];
        if (!TIFFRGBAImageOK(in, errmsg)) {
            fprintf(stderr, "%s: %s\n", iname, errmsg);
            return (-6);
        }
    }
    outline = malloc(imgwidth);
    raster = (uint32*)malloc(imgwidth * imglength * sizeof(uint32));
    if (!raster) {
        fprintf(stderr,"%s: Not enough memory\n", iname);
        return (-4);
    }
    if (!TIFFReadRGBAImage(in, imgwidth, imglength, raster, 0)) {
        if (1 >= quiet)
            fprintf(stderr,"%s: Image may be distorted\n", iname);
    }
    num_colors = 0;
    if (tolerance == -1) {
        tolerance = calculate_tolerance(raster, imgwidth, imglength);
        if (!quiet)
            fprintf(stderr,"%s: Calculated reduction factor %d\n",
                oname, tolerance);
        num_colors = 0; /* clear cache */
    } else if (check_colors(raster,imgwidth,imglength,tolerance)<0) {
        if (1 >= quiet)
            fprintf(stderr,
                "%s: Image can not be reduced with given factor %d\n",
                iname, tolerance);
        return (-7);
    }

    /* scan image, match input values to table entries */
    if (NULL == (out = TIFFOpen(oname, "w")))
        return (-3);

    CopyField(TIFFTAG_SUBFILETYPE, longv);
    TIFFSetField(out, TIFFTAG_IMAGEWIDTH, imgwidth);
    TIFFSetField(out, TIFFTAG_BITSPERSAMPLE, (short)COLOR_DEPTH);
    if (compression != (uint16)-1) {
        TIFFSetField(out, TIFFTAG_COMPRESSION, compression);
        switch (compression) {
          case COMPRESSION_LZW:
          case COMPRESSION_DEFLATE:
            if (predictor != 0)
                TIFFSetField(out, TIFFTAG_PREDICTOR, predictor);
                break;
        }
    } else
            CopyField(TIFFTAG_COMPRESSION, compression);
    TIFFSetField(out, TIFFTAG_PHOTOMETRIC, (short)PHOTOMETRIC_PALETTE);
#if 0
    CopyField(TIFFTAG_ORIENTATION, shortv);
#else
    TIFFSetField(out, TIFFTAG_ORIENTATION, ORIENTATION_TOPLEFT);
#endif
    TIFFSetField(out, TIFFTAG_SAMPLESPERPIXEL, (short)1);
#if 0
    CopyField(TIFFTAG_PLANARCONFIG, shortv);
#else
    TIFFSetField(out, TIFFTAG_PLANARCONFIG, PLANARCONFIG_CONTIG);
#endif
    TIFFSetField(out, TIFFTAG_ROWSPERSTRIP,
        TIFFDefaultStripSize(out, rowsperstrip));
    CopyField(TIFFTAG_MINSAMPLEVALUE, shortv);
    CopyField(TIFFTAG_MAXSAMPLEVALUE, shortv);
    CopyField(TIFFTAG_RESOLUTIONUNIT, shortv);
    CopyField(TIFFTAG_XRESOLUTION, floatv);
    CopyField(TIFFTAG_YRESOLUTION, floatv);
    CopyField(TIFFTAG_XPOSITION, floatv);
    CopyField(TIFFTAG_YPOSITION, floatv);

    for (y=0; y<imglength; y++) {
        row = raster + (imglength-y-1)*imgwidth;
        for (x=0; x<imgwidth; x++) {
            code = row[x];
            outline[x] = (unsigned char)
                colorno(TIFFGetR(code),TIFFGetG(code),TIFFGetB(code));
#if 0
            if (!already && TIFFGetA(code) != 255) {
                if (!quiet)
                    fprintf(stderr,"%s: Alpha-channel data ignored\n",
                        opath);
                already = 1;
            }
#endif
        }
        if (TIFFWriteScanline(out, outline, (uint32)y, 0) < 0) break;
    }
    /*
     * Scale colormap to TIFF-required 16-bit values.
     */
    for (x=0; x < num_colors; ++x) {
        rm[x] <<= 8;
        gm[x] <<= 8;
        bm[x] <<= 8;
    }
    for (; x<CMAP_SIZE; x++) {
        rm[x] = gm[x] = bm[x] = 0;
    }
    TIFFSetField(out, TIFFTAG_COLORMAP, rm, gm, bm);
    (void)TIFFClose(out);
    return (0);
}

---------- the end ----------