From 442a8edf800ca1dd57e04d26e85b47d00dc615ad Mon Sep 17 00:00:00 2001 From: giraffedata Date: Sun, 26 Apr 2009 19:55:26 +0000 Subject: Fix dithering with reduction of maxval - dither at the higher maxval, lookup in colormap at the lower one git-svn-id: http://svn.code.sf.net/p/netpbm/code/trunk@898 9d0c8265-081b-0410-96cb-a4ca84ce46f8 --- editor/pnmremap.c | 506 ++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 380 insertions(+), 126 deletions(-) (limited to 'editor/pnmremap.c') diff --git a/editor/pnmremap.c b/editor/pnmremap.c index 209124a1..7301fa35 100644 --- a/editor/pnmremap.c +++ b/editor/pnmremap.c @@ -40,15 +40,6 @@ enum missingMethod { MISSING_CLOSE }; -#define FS_SCALE 1024 - -struct fserr { - long ** thiserr; - long ** nexterr; - bool fsForward; -}; - - struct cmdlineInfo { /* All the information the user supplied in the command line, in a form easy for the program to use. @@ -146,53 +137,112 @@ parseCommandLine (int argc, char ** argv, } +typedef enum { + ADJUST_NONE, + ADJUST_RGBTO1, + ADJUST_GRAYSCALETO3 +} depthAdjustment; + + static void -rgbToDepth1(const struct pam * const pamP, - tuple * const tupleRow) { - - unsigned int col; +rgbToDepth1(tuple const tuple) { - for (col = 0; col < pamP->width; ++col) { - unsigned int plane; - double grayvalue; - grayvalue = 0.0; /* initial value */ - for (plane = 0; plane < pamP->depth; ++plane) - grayvalue += pnm_lumin_factor[plane] * tupleRow[col][plane]; - tupleRow[col][0] = (sample) (grayvalue + 0.5); - } + unsigned int plane; + double grayvalue; + + grayvalue = 0.0; /* initial value */ + + for (plane = 0; plane < 3; ++plane) + grayvalue += pnm_lumin_factor[plane] * tuple[plane]; + + tuple[0] = (sample) (grayvalue + 0.5); } static void -grayscaleToDepth3(const struct pam * const pamP, - tuple * const tupleRow) { +grayscaleToDepth3(tuple const tuple) { + + tuple[1] = tuple[0]; + tuple[2] = tuple[0]; +} + + + +static void +adjustDepthTuple(tuple const tuple, + depthAdjustment const adjustment) { - unsigned int col; + switch (adjustment) { + case ADJUST_NONE: + break; + case ADJUST_RGBTO1: + rgbToDepth1(tuple); + break; + case ADJUST_GRAYSCALETO3: + grayscaleToDepth3(tuple); + break; + } +} + - assert(pamP->allocation_depth >= 3); - for (col = 0; col < pamP->width; ++col) { - tupleRow[col][1] = tupleRow[col][0]; - tupleRow[col][2] = tupleRow[col][0]; +static void +inverseAdjustDepthTuple(tuple const tuple, + depthAdjustment const adjustment) { + + switch (adjustment) { + case ADJUST_NONE: + break; + case ADJUST_RGBTO1: + grayscaleToDepth3(tuple); + break; + case ADJUST_GRAYSCALETO3: + rgbToDepth1(tuple); + break; } } static void -adjustDepth(const struct pam * const pamP, - tuple * const tupleRow, - unsigned int const newDepth) { +adjustDepthRow(tuple * const tupleRow, + unsigned int const width, + depthAdjustment const adjustment) { /*---------------------------------------------------------------------------- - Change the depth of the raster row tupleRow[] of the image - described by 'pamP' to newDepth. + Change tupleRow[] depth as indicated by 'adjustment', + i.e. turned from RGB to grayscale or grayscale to RGB. - We don't change the memory allocation; tupleRow[] must already have - space allocated for at least 'newDepth' planes. When we're done, - all but the first 'newDepth' planes are meaningless, but the space is - still there. + We assume tupleRow[] is consistent with 'adjustment' -- i.e. if + 'adjustment' says grayscale to RGB, tupleRow[] has an allocation depth of + at least 3 and if 'adjustment' says from RGB to grayscale, tupleRow[] has + RGB tuples. +-----------------------------------------------------------------------------*/ + if (adjustment == ADJUST_NONE) { + } else { + unsigned int col; + + for (col = 0; col < width; ++col) { + if (adjustment == ADJUST_RGBTO1) + rgbToDepth1(tupleRow[col]); + else { + assert(adjustment == ADJUST_GRAYSCALETO3); + grayscaleToDepth3(tupleRow[col]); + } + } + } +} + + + +static void +selectDepthAdjustment(const struct pam * const pamP, + unsigned int const newDepth, + depthAdjustment * const adjustmentP) { +/*---------------------------------------------------------------------------- + Determine what kind of depth adjustment the pixels of an image described + by 'pamP' need to be comparable to pixels with depth 'newDepth'. The only depth changes we know how to do are: @@ -200,15 +250,23 @@ adjustDepth(const struct pam * const pamP, We change it to grayscale or black and white. + For this, we return *adjustmentP == ADJUST_RGBTO1. + - from tuple type GRAYSCALE or BLACKANDWHITE depth 1 to depth 3. We change it to RGB. + For this, we return *adjustmentP == ADJUST_GRAYSCALETO3. + For any other depth change request, we issue an error message and abort the program. ------------------------------------------------------------------------------*/ - if (newDepth != pamP->depth) { + If 'newDepth' is the same depth as the original (no depth change required), + we return *adjustmentP == ADJUST_NONE. +-----------------------------------------------------------------------------*/ + if (newDepth == pamP->depth) + *adjustmentP = ADJUST_NONE; + else { if (stripeq(pamP->tuple_type, "RGB")) { if (newDepth != 1) { pm_error("Map image depth of %u differs from input image " @@ -217,7 +275,7 @@ adjustDepth(const struct pam * const pamP, "an RGB tuple is 1.", newDepth, pamP->depth); } else - rgbToDepth1(pamP, tupleRow); + *adjustmentP = ADJUST_RGBTO1; } else if (stripeq(pamP->tuple_type, "GRAYSCALE") || stripeq(pamP->tuple_type, "BLACKANDWHITE")) { if (newDepth != 3) { @@ -228,7 +286,7 @@ adjustDepth(const struct pam * const pamP, "a GRAYSCALE or BLACKANDWHITE tuple is 3.", newDepth, pamP->depth); } else - grayscaleToDepth3(pamP, tupleRow); + *adjustmentP = ADJUST_GRAYSCALETO3; } else { pm_error("Map image depth of %u differs from input image depth " "of %u, and the input image does not have a tuple type " @@ -243,7 +301,6 @@ adjustDepth(const struct pam * const pamP, - static void computeColorMapFromMap(struct pam * const mappamP, tuple ** const maptuples, @@ -266,12 +323,38 @@ computeColorMapFromMap(struct pam * const mappamP, pnm_computetuplefreqtable(mappamP, maptuples, MAXCOLORS, &colors); if (*colormapP == NULL) pm_error("too many colors in colormap!"); - pm_message("%d colors found in colormap", colors); + pm_message("%u colors found in colormap", colors); *newcolorsP = colors; } +#define FS_SCALE 1024 + +struct fserr { + unsigned int width; + /* Width of the image being dithered */ + long ** thiserr; + long ** nexterr; + bool fsForward; + /* We are in a left-to-right row */ + int begCol; + /* First column in the sweep. Determined by 'fsForward': either + the leftmost or rightmost column in the row + */ + int endCol; + /* Column after the last column in the sweep. Determined by + 'fsForward': either one past the left end or one past the right + end of the row. + */ + int step; + /* What we add to a column number to get the next one in the sweep. + Determined by 'fsForward': +1 or -1. + */ +}; + + + static void randomizeError(long ** const err, unsigned int const width, @@ -293,6 +376,28 @@ randomizeError(long ** const err, +static void +fserrSetForward(struct fserr * const fserrP) { + + fserrP->fsForward = TRUE; + fserrP->begCol = 0; + fserrP->endCol = fserrP->width; + fserrP->step = +1; +} + + + +static void +fserrSetBackward(struct fserr * const fserrP) { + + fserrP->fsForward = FALSE; + fserrP->begCol = fserrP->width - 1; + fserrP->endCol = -1; + fserrP->step = -1; +} + + + static void initFserr(struct pam * const pamP, struct fserr * const fserrP, @@ -304,6 +409,8 @@ initFserr(struct pam * const pamP, unsigned int const fserrSize = pamP->width + 2; + fserrP->width = pamP->width; + MALLOCARRAY(fserrP->thiserr, pamP->depth); if (fserrP->thiserr == NULL) pm_error("Out of memory allocating Floyd-Steinberg structures " @@ -327,7 +434,7 @@ initFserr(struct pam * const pamP, if (initRandom) randomizeError(fserrP->thiserr, fserrSize, pamP->depth); - fserrP->fsForward = TRUE; + fserrSetForward(fserrP); } @@ -348,7 +455,8 @@ floydInitRow(struct pam * const pamP, struct fserr * const fserrP) { static void floydAdjustColor(struct pam * const pamP, - tuple const tuple, + tuple const intuple, + tuple const outtuple, struct fserr * const fserrP, int const col) { /*---------------------------------------------------------------------------- @@ -358,8 +466,8 @@ floydAdjustColor(struct pam * const pamP, for (plane = 0; plane < pamP->depth; ++plane) { long int const s = - tuple[plane] + fserrP->thiserr[plane][col+1] / FS_SCALE; - tuple[plane] = MIN(pamP->maxval, MAX(0,s)); + intuple[plane] + fserrP->thiserr[plane][col+1] / FS_SCALE; + outtuple[plane] = MIN(pamP->maxval, MAX(0,s)); } } @@ -411,7 +519,11 @@ floydSwitchDir(struct pam * const pamP, struct fserr * const fserrP) { fserrP->thiserr[plane] = fserrP->nexterr[plane]; fserrP->nexterr[plane] = temperr; } - fserrP->fsForward = ! fserrP->fsForward; + + if (fserrP->fsForward) + fserrSetBackward(fserrP); + else + fserrSetForward(fserrP); } @@ -631,8 +743,177 @@ lookupThroughHash(struct pam * const pamP, static void -convertRow(struct pam * const pamP, - tuple tuplerow[], +mapTuple(struct pam * const pamP, + tuple const inTuple, + enum missingMethod const missingMethod, + tuple const defaultColor, + tupletable const colormap, + struct colormapFinder * const colorFinderP, + tuplehash const colorhash, + bool * const usehashP, + tuple const outTuple, + bool * const missingP) { + + int colormapIndex; + /* Index into the colormap of the replacement color, or -1 if + there is no usable color in the color map. + */ + + lookupThroughHash(pamP, inTuple, + missingMethod != MISSING_CLOSE, colorFinderP, + colorhash, &colormapIndex, usehashP); + + if (colormapIndex == -1) { + *missingP = TRUE; + switch (missingMethod) { + case MISSING_SPECIFIED: + pnm_assigntuple(pamP, outTuple, defaultColor); + break; + case MISSING_FIRST: + pnm_assigntuple(pamP, outTuple, colormap[0]->tuple); + break; + default: + pm_error("Internal error: invalid value of missingMethod"); + } + } else { + *missingP = FALSE; + pnm_assigntuple(pamP, outTuple, colormap[colormapIndex]->tuple); + } +} + + + +static void +convertRowStraight(struct pam * const inpamP, + struct pam * const outpamP, + tuple inrow[], + depthAdjustment const depthAdjustment, + tupletable const colormap, + struct colormapFinder * const colorFinderP, + tuplehash const colorhash, + bool * const usehashP, + enum missingMethod const missingMethod, + tuple const defaultColor, + tuple outrow[], + unsigned int * const missingCountP) { +/*---------------------------------------------------------------------------- + Like convertRow(), compute outrow[] from inrow[], replacing each pixel with + the new colors. Do a straight pixel for pixel remap; no dithering. + + Return the number of pixels that were not matched in the color map as + *missingCountP. + + *colorFinderP is a color finder based on 'colormap' -- it tells us what + index of 'colormap' corresponds to a certain color. +-----------------------------------------------------------------------------*/ + unsigned int col; + unsigned int missingCount; + + /* The following modify tuplerow, to make it consistent with + *outpamP instead of *inpamP. + */ + assert(outpamP->allocation_depth >= inpamP->depth); + + pnm_scaletuplerow(inpamP, outrow, inrow, outpamP->maxval); + + adjustDepthRow(outrow, outpamP->width, depthAdjustment); + + missingCount = 0; /* initial value */ + + for (col = 0; col < outpamP->width; ++col) { + bool missing; + mapTuple(outpamP, outrow[col], missingMethod, defaultColor, + colormap, colorFinderP, + colorhash, usehashP, outrow[col], &missing); + + if (missing) + ++missingCount; + } + + *missingCountP = missingCount; +} + + + +static void +convertRowDither(struct pam * const inpamP, + struct pam * const outpamP, + tuple const inrow[], + depthAdjustment const depthAdjustment, + tupletable const colormap, + struct colormapFinder * const colorFinderP, + tuplehash const colorhash, + bool * const usehashP, + enum missingMethod const missingMethod, + tuple const defaultColor, + struct fserr * const fserrP, + tuple outrow[], + unsigned int * const missingCountP) { +/*---------------------------------------------------------------------------- + Like convertRow(), compute outrow[] from inrow[], replacing each pixel with + the new colors. Do a Floyd-Steinberg dither, using and updating the error + accumulator *fserrP. + + Return the number of pixels that were not matched in the color map as + *missingCountP. + + *colorFinderP is a color finder based on 'colormap' -- it tells us what + index of 'colormap' corresponds to a certain color. +-----------------------------------------------------------------------------*/ + tuple const ditheredTuple = pnm_allocpamtuple(inpamP); + /* The input tuple we're converting, adjusted by the dither */ + tuple const normTuple = pnm_allocpamtuple(outpamP); + /* Same as above, normalized to the maxval of the output file / + colormap. + */ + unsigned int missingCount; + int col; + + floydInitRow(inpamP, fserrP); + + missingCount = 0; /* initial value */ + + for (col = fserrP->begCol; col != fserrP->endCol; col += fserrP->step) { + bool missing; + + floydAdjustColor(inpamP, inrow[col], ditheredTuple, fserrP, col); + + /* Convert tuple to the form of those in the colormap */ + assert(outpamP->allocation_depth >= inpamP->depth); + pnm_scaletuple(inpamP, normTuple, ditheredTuple, outpamP->maxval); + adjustDepthTuple(normTuple, depthAdjustment); + + mapTuple(outpamP, normTuple, missingMethod, defaultColor, + colormap, colorFinderP, + colorhash, usehashP, outrow[col], &missing); + + if (missing) + ++missingCount; + + /* Convert tuple back to the form of the input, where dithering + takes place. + */ + pnm_scaletuple(outpamP, normTuple, outrow[col], inpamP->maxval); + inverseAdjustDepthTuple(normTuple, depthAdjustment); + + floydPropagateErr(inpamP, fserrP, col, inrow[col], normTuple); + } + + floydSwitchDir(inpamP, fserrP); + + pnm_freepamtuple(normTuple); + pnm_freepamtuple(ditheredTuple); + + *missingCountP = missingCount; +} + + + +static void +convertRow(struct pam * const inpamP, + struct pam * const outpamP, + tuple inrow[], + depthAdjustment depthAdjustment, tupletable const colormap, struct colormapFinder * const colorFinderP, tuplehash const colorhash, @@ -641,10 +922,11 @@ convertRow(struct pam * const pamP, enum missingMethod const missingMethod, tuple const defaultColor, struct fserr * const fserrP, + tuple outrow[], unsigned int * const missingCountP) { /*---------------------------------------------------------------------------- - Replace the colors in row tuplerow[] (described by *pamP) with the - new colors. + Replace the colors in row tuplerow[] (described by *inpamP) with the + new colors and convert so it is described by *outpamP. Use and update the Floyd-Steinberg state *fserrP. @@ -653,66 +935,25 @@ convertRow(struct pam * const pamP, *colorFinderP is a color finder based on 'colormap' -- it tells us what index of 'colormap' corresponds to a certain color. ------------------------------------------------------------------------------*/ - int col; - int limitcol; - /* The column at which to stop processing the row. If we're scanning - forwards, this is the rightmost column. If we're scanning - backward, this is the leftmost column. - */ - - if (floyd) - floydInitRow(pamP, fserrP); - - *missingCountP = 0; /* initial value */ - - if ((!floyd) || fserrP->fsForward) { - col = 0; - limitcol = pamP->width; - } else { - col = pamP->width - 1; - limitcol = -1; - } - do { - int colormapIndex; - /* Index into the colormap of the replacement color, or -1 if - there is no usable color in the color map. - */ - - if (floyd) - floydAdjustColor(pamP, tuplerow[col], fserrP, col); - - lookupThroughHash(pamP, tuplerow[col], - missingMethod != MISSING_CLOSE, colorFinderP, - colorhash, &colormapIndex, usehashP); - if (floyd) - floydPropagateErr(pamP, fserrP, col, tuplerow[col], - colormap[colormapIndex]->tuple); - - if (colormapIndex == -1) { - ++*missingCountP; - switch (missingMethod) { - case MISSING_SPECIFIED: - pnm_assigntuple(pamP, tuplerow[col], defaultColor); - break; - case MISSING_FIRST: - pnm_assigntuple(pamP, tuplerow[col], colormap[0]->tuple); - break; - default: - pm_error("Internal error: invalid value of missingMethod"); - } - } else - pnm_assigntuple(pamP, tuplerow[col], - colormap[colormapIndex]->tuple); - - if (floyd && !fserrP->fsForward) - --col; - else - ++col; - } while (col != limitcol); + outrow[] doubles as a work space, so we require it to have an allocation + depth at least as great as that of inrow[]. +-----------------------------------------------------------------------------*/ + /* The following both consults and adds to 'colorhash' and + its associated '*usehashP'. It modifies 'tuplerow' too. + */ if (floyd) - floydSwitchDir(pamP, fserrP); + convertRowDither(inpamP, outpamP, inrow, + depthAdjustment, colormap, colorFinderP, colorhash, + usehashP, + missingMethod, defaultColor, + fserrP, outrow, missingCountP); + else + convertRowStraight(inpamP, outpamP, inrow, + depthAdjustment, colormap, colorFinderP, colorhash, + usehashP, + missingMethod, defaultColor, + outrow, missingCountP); } @@ -729,12 +970,30 @@ copyRaster(struct pam * const inpamP, unsigned int * const missingCountP) { tuplehash const colorhash = pnm_createtuplehash(); + + tuple * inrow; + tuple * outrow; + struct pam workpam; + /* This is for work space we use for building up the output + pixels. To save time and memory, we modify them in place in a + buffer, which ultimately holds the output pixels. This pam + structure is thus the same as the *outpamP, but with a tuple + allocation depth large enough to handle intermediate results. + */ + depthAdjustment depthAdjustment; struct colormapFinder * colorFinderP; bool usehash; struct fserr fserr; - tuple * tuplerow = pnm_allocpamrow(inpamP); int row; + workpam = *outpamP; + workpam.allocation_depth = MAX(workpam.depth, inpamP->depth); + workpam.size = sizeof(workpam); + workpam.len = PAM_STRUCT_SIZE(allocation_depth); + + inrow = pnm_allocpamrow(inpamP); + outrow = pnm_allocpamrow(&workpam); + if (outpamP->maxval != inpamP->maxval && missingMethod != MISSING_CLOSE) pm_error("The maxval of the colormap (%u) is not equal to the " "maxval of the input image (%u). This is allowable only " @@ -742,6 +1001,8 @@ copyRaster(struct pam * const inpamP, "specify -firstisdefault or -missingcolor)", (unsigned int)outpamP->maxval, (unsigned int)inpamP->maxval); + selectDepthAdjustment(inpamP, outpamP->depth, &depthAdjustment); + usehash = TRUE; createColormapFinder(outpamP, colormap, colormapSize, &colorFinderP); @@ -754,28 +1015,21 @@ copyRaster(struct pam * const inpamP, for (row = 0; row < inpamP->height; ++row) { unsigned int missingCount; - pnm_readpamrow(inpamP, tuplerow); + pnm_readpamrow(inpamP, inrow); - /* The following modify tuplerow, to make it consistent with - *outpamP instead of *inpamP. - */ - assert(inpamP->allocation_depth >= outpamP->depth); - pnm_scaletuplerow(inpamP, tuplerow, tuplerow, outpamP->maxval); - adjustDepth(inpamP, tuplerow, outpamP->depth); - - /* The following both consults and adds to 'colorhash' and - its associated 'usehash'. It modifies 'tuplerow' too. - */ - convertRow(outpamP, tuplerow, colormap, colorFinderP, colorhash, + convertRow(inpamP, &workpam, inrow, + depthAdjustment, colormap, colorFinderP, colorhash, &usehash, - floyd, missingMethod, defaultColor, &fserr, &missingCount); + floyd, missingMethod, defaultColor, + &fserr, outrow, &missingCount); *missingCountP += missingCount; - pnm_writepamrow(outpamP, tuplerow); + pnm_writepamrow(outpamP, outrow); } destroyColormapFinder(colorFinderP); - pnm_freepamrow(tuplerow); + pnm_freepamrow(inrow); + pnm_freepamrow(outrow); pnm_destroytuplehash(colorhash); } -- cgit 1.4.1