--- ray/src/px/neuclrtab.c 1994/06/10 12:33:35 2.1 +++ ray/src/px/neuclrtab.c 2011/05/20 02:06:39 2.14 @@ -1,18 +1,18 @@ -/* Copyright (c) 1994 Regents of the University of California */ - #ifndef lint -static char SCCSid[] = "$SunId$ LBL"; +static const char RCSid[] = "$Id: neuclrtab.c,v 2.14 2011/05/20 02:06:39 greg Exp $"; #endif - /* * Neural-Net quantization algorithm based on work of Anthony Dekker */ -#include "standard.h" +#include "copyright.h" -#include "color.h" +#include +#include "standard.h" +#include "color.h" #include "random.h" +#include "clrtab.h" #ifdef COMPAT_MODE #define neu_init new_histo @@ -24,25 +24,21 @@ static char SCCSid[] = "$SunId$ LBL"; #define neu_dith_colrs dith_colrs #endif /* our color table (global) */ -extern BYTE clrtab[256][3]; +extern uby8 clrtab[256][3]; static int clrtabsiz; #ifndef DEFSMPFAC -#ifdef SPEED -#define DEFSMPFAC (240/SPEED+3) -#else -#define DEFSMPFAC 30 +#define DEFSMPFAC 3 #endif -#endif int samplefac = DEFSMPFAC; /* sampling factor */ /* Samples array starts off holding spacing between adjacent * samples, and ends up holding actual BGR sample values. */ -static BYTE *thesamples; +static uby8 *thesamples; static int nsamples; -static BYTE *cursamp; +static uby8 *cursamp; static long skipcount; #define MAXSKIP (1<<24-1) @@ -51,9 +47,21 @@ static long skipcount; #define setskip(sp,n) ((sp)[0]=(n)>>16,(sp)[1]=((n)>>8)&255,(sp)[2]=(n)&255) +static void initnet(void); +static void inxbuild(void); +static int inxsearch(int b, int g, int r); +static int contest(int b, int g, int r); +static void altersingle(int alpha, int i, int b, int g, int r); +static void alterneigh(int rad, int i, int b, int g, int r); +static void learn(void); +static void unbiasnet(void); +static void cpyclrtab(void); -neu_init(npixels) /* initialize our sample array */ -long npixels; + +extern int +neu_init( /* initialize our sample array */ + long npixels +) { register int nsleft; register long sv; @@ -63,7 +71,7 @@ long npixels; nsamples = npixels/samplefac; if (nsamples < 600) return(-1); - thesamples = (BYTE *)malloc((nsamples+1)*3); + thesamples = (uby8 *)malloc(nsamples*3); if (thesamples == NULL) return(-1); cursamp = thesamples; @@ -75,51 +83,60 @@ long npixels; cumprob = 0.; while ((cumprob += (1.-cumprob)*nsleft/(npleft-sv)) < rval) sv++; - setskip(cursamp, sv); - cursamp += 3; - npleft -= sv; + if (nsleft == nsamples) + skipcount = sv; + else { + setskip(cursamp, sv); + cursamp += 3; + } + npleft -= sv+1; nsleft--; } - setskip(cursamp, 0); /* dummy tagged onto end */ + setskip(cursamp, npleft); /* tag on end to skip the rest */ cursamp = thesamples; - skipcount = nskip(cursamp); return(0); } -neu_pixel(col) /* add pixel to our samples */ -register BYTE col[]; +extern void +neu_pixel( /* add pixel to our samples */ + register uby8 col[] +) { if (!skipcount--) { + skipcount = nskip(cursamp); cursamp[0] = col[BLU]; cursamp[1] = col[GRN]; cursamp[2] = col[RED]; cursamp += 3; - skipcount = nskip(cursamp); } } -neu_colrs(cs, n) /* add a scanline to our samples */ -register COLR *cs; -register int n; +extern void +neu_colrs( /* add a scanline to our samples */ + register COLR *cs, + register int n +) { while (n > skipcount) { cs += skipcount; + n -= skipcount+1; + skipcount = nskip(cursamp); cursamp[0] = cs[0][BLU]; cursamp[1] = cs[0][GRN]; cursamp[2] = cs[0][RED]; cs++; - n -= skipcount+1; cursamp += 3; - skipcount = nskip(cursamp); } skipcount -= n; } -neu_clrtab(ncolors) /* make new color table using ncolors */ -int ncolors; +extern int +neu_clrtab( /* make new color table using ncolors */ + int ncolors +) { clrtabsiz = ncolors; if (clrtabsiz > 256) clrtabsiz = 256; @@ -129,26 +146,29 @@ int ncolors; cpyclrtab(); inxbuild(); /* we're done with our samples */ - free((char *)thesamples); + free((void *)thesamples); /* reset dithering function */ - neu_dith_colrs((BYTE *)NULL, (COLR *)NULL, 0); + neu_dith_colrs((uby8 *)NULL, (COLR *)NULL, 0); /* return new color table size */ return(clrtabsiz); } -int -neu_map_pixel(col) /* get pixel for color */ -register BYTE col[]; +extern int +neu_map_pixel( /* get pixel for color */ + register uby8 col[] +) { return(inxsearch(col[BLU],col[GRN],col[RED])); } -neu_map_colrs(bs, cs, n) /* convert a scanline to color index values */ -register BYTE *bs; -register COLR *cs; -register int n; +extern void +neu_map_colrs( /* convert a scanline to color index values */ + register uby8 *bs, + register COLR *cs, + register int n +) { while (n-- > 0) { *bs++ = inxsearch(cs[0][BLU],cs[0][GRN],cs[0][RED]); @@ -157,10 +177,12 @@ register int n; } -neu_dith_colrs(bs, cs, n) /* convert scanline to dithered index values */ -register BYTE *bs; -register COLR *cs; -int n; +extern void +neu_dith_colrs( /* convert scanline to dithered index values */ + register uby8 *bs, + register COLR *cs, + int n +) { static short (*cerr)[3] = NULL; static int N = 0; @@ -169,7 +191,7 @@ int n; if (n != N) { /* get error propogation array */ if (N) { - free((char *)cerr); + free((void *)cerr); cerr = NULL; } if (n) @@ -180,7 +202,7 @@ int n; return; } N = n; - bzero((char *)cerr, 3*N*sizeof(short)); + memset((char *)cerr, '\0', 3*N*sizeof(short)); } err[0] = err[1] = err[2] = 0; for (x = 0; x < n; x++) { @@ -205,134 +227,121 @@ int n; } /* The following was adapted and modified from the original (GW) */ -/*----------------------------------------------------------------------*/ -/* */ -/* NeuQuant */ -/* -------- */ -/* */ -/* Copyright: Anthony Dekker, June 1994 */ -/* */ -/* This program performs colour quantization of graphics images (SUN */ -/* raster files). It uses a Kohonen Neural Network. It produces */ -/* better results than existing methods and runs faster, using minimal */ -/* space (8kB plus the image itself). The algorithm is described in */ -/* the paper "Kohonen Neural Networks for Optimal Colour Quantization" */ -/* to appear in the journal "Network: Computation in Neural Systems". */ -/* It is a significant improvement of an earlier algorithm. */ -/* */ -/* This program is distributed free for academic use or for evaluation */ -/* by commercial organizations. */ -/* */ -/* Usage: NeuQuant -n inputfile > outputfile */ -/* */ -/* where n is a sampling factor for neural learning. */ -/* */ -/* Program performance compared with other methods is as follows: */ -/* */ -/* Algorithm | Av. CPU Time | Quantization Error */ -/* ------------------------------------------------------------- */ -/* NeuQuant -3 | 314 | 5.55 */ -/* NeuQuant -10 | 119 | 5.97 */ -/* NeuQuant -30 | 65 | 6.53 */ -/* Oct-Trees | 141 | 8.96 */ -/* Median Cut (XV -best) | 420 | 9.28 */ -/* Median Cut (XV -slow) | 72 | 12.15 */ -/* */ -/* Author's address: Dept of ISCS, National University of Singapore */ -/* Kent Ridge, Singapore 0511 */ -/* Email: tdekker@iscs.nus.sg */ -/*----------------------------------------------------------------------*/ -#define bool int -#define false 0 -#define true 1 +/* cheater definitions (GW) */ +#define thepicture thesamples +#define lengthcount (nsamples*3) +#define samplefac 1 -#define initrad 32 -#define radiusdec 30 -#define alphadec; 30 +/* NeuQuant Neural-Net Quantization Algorithm Interface + * ---------------------------------------------------- + * + * Copyright (c) 1994 Anthony Dekker + * + * NEUQUANT Neural-Net quantization algorithm by Anthony Dekker, 1994. + * See "Kohonen neural networks for optimal colour quantization" + * in "Network: Computation in Neural Systems" Vol. 5 (1994) pp 351-367. + * for a discussion of the algorithm. + * See also http://members.ozemail.com.au/~dekker/NEUQUANT.HTML + * + * Any party obtaining a copy of these files from the author, directly or + * indirectly, is granted, free of charge, a full and unrestricted irrevocable, + * world-wide, paid up, royalty-free, nonexclusive right and license to deal + * in this software and documentation files (the "Software"), including without + * limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons who receive + * copies from any such party to do so, with the only requirement being + * that this copyright notice remain intact. + */ +#define bool int +#define false 0 +#define true 1 + +/* network defs */ +#define netsize clrtabsiz /* number of colours - can change this */ +#define maxnetpos (netsize-1) +#define netbiasshift 4 /* bias for colour values */ +#define ncycles 100 /* no. of learning cycles */ + /* defs for freq and bias */ -#define gammashift 10 -#define betashift gammashift -#define intbiasshift 16 -#define intbias (1<>betashift) +#define intbiasshift 16 /* bias for fractions */ +#define intbias (((int) 1)<>betashift) /* beta = 1/1024 */ #define betagamma (intbias<<(gammashift-betashift)) -#define gammaphi (intbias<<(gammashift-8)) -/* defs for rad and alpha */ -#define maxrad (initrad+1) -#define radiusbiasshift 6 -#define radiusbias (1<>3) /* for 256 cols, radius starts */ +#define radiusbiasshift 6 /* at 32.0 biased by 6 bits */ +#define radiusbias (((int) 1)<> 8; /* 1/256 */ + p[0] = p[1] = p[2] = (i << (netbiasshift+8))/netsize; + freq[i] = intbias/netsize; /* 1/netsize */ bias[i] = 0; } } -static -inxbuild() +/* do after unbias - insertion sort of network and build netindex[0..255] */ + +static void +inxbuild(void) { register int i,j,smallpos,smallval; register int *p,*q; - int start,previous; + int previouscol,startpos; - previous = 0; - start = 0; - for (i=0; i>1; - for (j=previous+1; j>1; + for (j=previouscol+1; j>1; - for (j=previous+1; j>1; + for (j=previouscol+1; j<256; j++) netindex[j] = maxnetpos; /* really 256 */ } static int -inxsearch(b,g,r) /* accepts real BGR values after net is unbiased */ -register int b,g,r; +inxsearch( /* accepts real BGR values after net is unbiased */ + register int b, + register int g, + register int r +) { - register int i,j,best,x,y,bestd; + register int i,j,dist,a,bestd; register int *p; + int best; bestd = 1000; /* biggest possible dist is 256*3 */ best = -1; i = netindex[g]; /* index on g */ - j = i-1; + j = i-1; /* start at netindex[g] and work outwards */ - while ((i=0)) { - if (i=0)) { + if (i= bestd) i = clrtabsiz; /* stop iter */ + dist = p[1] - g; /* inx key */ + if (dist >= bestd) i = netsize; /* stop iter */ else { i++; - if (x<0) x = -x; - y = p[0] - b; - if (y<0) y = -y; - x += y; - if (x=0) { p = network[j]; - x = g - p[1]; /* inx key - reverse dif */ - if (x >= bestd) j = -1; /* stop iter */ + dist = g - p[1]; /* inx key - reverse dif */ + if (dist >= bestd) j = -1; /* stop iter */ else { j--; - if (x<0) x = -x; - y = p[0] - b; - if (y<0) y = -y; - x += y; - if (x> netbiasshift not needed if funnyshift used */ - if (x>funnyshift); /* y holds biasd */ - if (y> betashift); /* y holds beta*freq */ - *p -= y; - *q += (y<>(intbiasshift-netbiasshift)); + if (biasdist> betashift); + *f++ -= betafreq; + *p++ += (betafreq<clrtabsiz) hi=clrtabsiz; + lo = i-rad; if (lo<-1) lo= -1; + hi = i+rad; if (hi>netsize) hi=netsize; j = i+1; k = i-1; @@ -492,58 +533,45 @@ register int b,g,r; } -static -altersingle(alpha,j,b,g,r) /* accepts biased BGR values */ -register int alpha,j,b,g,r; +static void +learn(void) { - register int *q; - - q = network[j]; /* alter hit neuron */ - *q -= (alpha*(*q - b)) / initalpha; - q++; - *q -= (alpha*(*q - g)) / initalpha; - q++; - *q -= (alpha*(*q - r)) / initalpha; -} - - -static -learn() -{ register int i,j,b,g,r; - int radius,rad,alpha,step,delta,upto; + int radius,rad,alpha,step,delta,samplepixels; register unsigned char *p; unsigned char *lim; - upto = lengthcount/(3*samplefac); - delta = upto/ncycles; - lim = thepicture + lengthcount; + alphadec = 30 + ((samplefac-1)/3); p = thepicture; + lim = thepicture + lengthcount; + samplepixels = lengthcount/(3*samplefac); + delta = samplepixels/ncycles; alpha = initalpha; radius = initradius; + rad = radius >> radiusbiasshift; if (rad <= 1) rad = 0; for (i=0; i= lim) p -= lengthcount; @@ -560,26 +588,31 @@ learn() } } -static -unbiasnet() +/* unbias network to give 0..255 entries */ +/* which can then be used for colour map */ +/* and record position i to prepare for sort */ + +static void +unbiasnet(void) { int i,j; - for (i=0; i>= netbiasshift; network[i][3] = i; /* record colour no */ } } -/* Don't do this until the network has been unbiased */ + +/* Don't do this until the network has been unbiased (GW) */ -static -cpyclrtab() +static void +cpyclrtab(void) { register int i,j,k; - for (j=0; j