mirror of
https://github.com/OpenTrespasser/JurassicParkTrespasser.git
synced 2024-12-18 22:51:56 +00:00
488 lines
11 KiB
C
488 lines
11 KiB
C
// several changes (mainly x86 and quality optimizations) by wili/hybrid 1996
|
|
|
|
/* NeuQuant Neural-Net Quantization Algorithm
|
|
* ------------------------------------------
|
|
*
|
|
* 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.
|
|
*
|
|
* 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.
|
|
*/
|
|
|
|
|
|
#include "neuquant.h"
|
|
#include <math.h>
|
|
|
|
|
|
extern void check_abort();
|
|
|
|
/* Network Definitions
|
|
------------------- */
|
|
|
|
#define maxnetpos (netsize-1)
|
|
#define netbiasshift 4 /* bias for colour values */
|
|
#define ncycles 100 /* no. of learning cycles */
|
|
|
|
/* defs for freq and bias */
|
|
#define intbiasshift 16 /* bias for fractions */
|
|
#define intbias (((int) 1)<<intbiasshift)
|
|
#define gammashift 10 /* gamma = 1024 */
|
|
#define gamma (((int) 1)<<gammashift)
|
|
#define betashift 10
|
|
#define beta (intbias>>betashift) /* beta = 1/1024 */
|
|
#define betagamma (intbias<<(gammashift-betashift))
|
|
|
|
/* defs for decreasing radius factor */
|
|
#define initrad (netsize>>3) /* for 256 cols, radius starts */
|
|
#define radiusbiasshift 6 /* at 32.0 biased by 6 bits */
|
|
#define radiusbias (((int) 1)<<radiusbiasshift)
|
|
#define initradius (initrad*radiusbias) /* and decreases by a */
|
|
#define radiusdec 30 /* factor of 1/30 each cycle */
|
|
|
|
/* defs for decreasing alpha factor */
|
|
#define alphabiasshift 10 /* alpha starts at 1.0 */
|
|
#define initalpha (((int) 1)<<alphabiasshift)
|
|
int alphadec; /* biased by 10 bits */
|
|
|
|
/* radbias and alpharadbias used for radpower calculation */
|
|
#define radbiasshift 8
|
|
#define radbias (((int) 1)<<radbiasshift)
|
|
#define alpharadbshift (alphabiasshift+radbiasshift)
|
|
#define alpharadbias (((int) 1)<<alpharadbshift)
|
|
|
|
|
|
/* Types and Global Variables
|
|
-------------------------- */
|
|
|
|
static unsigned char *thepicture; /* the input image itself */
|
|
static int lengthcount; /* lengthcount = H*W*3 */
|
|
|
|
static int samplefac; /* sampling factor 1..30 */
|
|
|
|
|
|
typedef int pixel[4]; /* BGRc */
|
|
static pixel network[netsize]; /* the network itself */
|
|
|
|
static int netindex[256]; /* for network lookup - really 256 */
|
|
|
|
static int bias [netsize]; /* bias and freq arrays for learning */
|
|
static int freq [netsize];
|
|
static int radpower[initrad]; /* radpower for precomputation */
|
|
|
|
|
|
/* Initialise network in range (0,0,0) to (255,255,255) and set parameters
|
|
----------------------------------------------------------------------- */
|
|
|
|
void initnet(unsigned char *thepic,int len,int sample)
|
|
{
|
|
int i;
|
|
int *p;
|
|
|
|
thepicture = thepic;
|
|
lengthcount = len;
|
|
samplefac = sample;
|
|
|
|
for (i=0; i<netsize; i++)
|
|
{
|
|
p = network[i];
|
|
p[0] = p[1] = p[2] = (i << (netbiasshift+8))/netsize;
|
|
freq[i] = intbias/netsize; /* 1/netsize */
|
|
bias[i] = 0;
|
|
}
|
|
}
|
|
|
|
|
|
/* Unbias network to give byte values 0..255 and record position i to prepare for sort
|
|
----------------------------------------------------------------------------------- */
|
|
|
|
void unbiasnet()
|
|
{
|
|
int i,j;
|
|
|
|
for (i=0; i<netsize; i++)
|
|
{
|
|
for (j=0; j<3; j++)
|
|
network[i][j] >>= netbiasshift;
|
|
|
|
network[i][3] = i; /* record colour no */
|
|
}
|
|
}
|
|
|
|
|
|
/* Output colour map
|
|
----------------- */
|
|
|
|
void copy_colourmap( char *dest)
|
|
{
|
|
int i,j;
|
|
|
|
for (i=2; i>=0; i--)
|
|
for (j=0; j<netsize; j++)
|
|
dest[j*3+i]= network[j][i];
|
|
|
|
}
|
|
|
|
/* Insertion sort of network and building of netindex[0..255] (to do after unbias)
|
|
------------------------------------------------------------------------------- */
|
|
|
|
void inxbuild()
|
|
{
|
|
int i,j,smallpos,smallval;
|
|
int *p,*q;
|
|
int previouscol,startpos;
|
|
|
|
previouscol = 0;
|
|
startpos = 0;
|
|
|
|
for (i=0; i<netsize; i++)
|
|
{
|
|
p = network[i];
|
|
smallpos = i;
|
|
smallval = p[1]; /* index on g */
|
|
|
|
/* find smallest in i..netsize-1 */
|
|
|
|
for (j=i+1; j<netsize; j++)
|
|
{
|
|
q = network[j];
|
|
if (q[1] < smallval)
|
|
{
|
|
smallpos = j;
|
|
smallval = q[1]; /* index on g */
|
|
}
|
|
}
|
|
|
|
q = network[smallpos];
|
|
|
|
/* swap p (i) and q (smallpos) entries */
|
|
|
|
if (i != smallpos)
|
|
{
|
|
j = q[0]; q[0] = p[0]; p[0] = j;
|
|
j = q[1]; q[1] = p[1]; p[1] = j;
|
|
j = q[2]; q[2] = p[2]; p[2] = j;
|
|
j = q[3]; q[3] = p[3]; p[3] = j;
|
|
}
|
|
|
|
/* smallval entry is now in position i */
|
|
if (smallval != previouscol)
|
|
{
|
|
netindex[previouscol] = (startpos+i)>>1;
|
|
|
|
for (j=previouscol+1; j<smallval; j++)
|
|
netindex[j] = i;
|
|
|
|
previouscol = smallval;
|
|
startpos = i;
|
|
}
|
|
}
|
|
|
|
netindex[previouscol] = (startpos+maxnetpos)/2;
|
|
|
|
for (j=previouscol+1; j<256; j++)
|
|
netindex[j] = maxnetpos; /* really 256 */
|
|
}
|
|
|
|
|
|
char inxsearch(int b, int g, int r)
|
|
{
|
|
int i,j,dist,a;
|
|
int *p;
|
|
int best = -1;
|
|
int bestd = 1000000;
|
|
|
|
i = netindex[g]; /* index on g */
|
|
j = i-1; /* start at netindex[g] and work outwards */
|
|
|
|
while ((i<netsize) || (j>=0))
|
|
{
|
|
if (i<netsize)
|
|
{
|
|
p = network[i];
|
|
dist = (p[1] - g); /* inx key */
|
|
|
|
if (dist >= bestd)
|
|
i = netsize; /* stop iter */
|
|
else
|
|
{
|
|
i++;
|
|
|
|
dist=abs(dist)+abs(p[2]-r); // 0 b
|
|
|
|
if (dist<bestd)
|
|
{
|
|
dist += abs(p[0]-b); // 2 r
|
|
|
|
if (dist<bestd)
|
|
{
|
|
bestd = dist;
|
|
best = p[3];
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if (j>=0)
|
|
{
|
|
p = network[j];
|
|
dist = (g - p[1]); /* inx key - reverse dif */
|
|
|
|
if (dist >= bestd)
|
|
j = -1; /* stop iter */
|
|
else
|
|
{
|
|
j--;
|
|
|
|
dist=abs(dist)+abs(p[2]-r); // 0 b
|
|
|
|
if (dist<bestd)
|
|
{
|
|
dist += abs(p[0]-b); // 2 r
|
|
|
|
if (dist<bestd)
|
|
{
|
|
bestd = dist;
|
|
best = p[3];
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return(best);
|
|
}
|
|
|
|
|
|
/* Search for biased BGR values
|
|
---------------------------- */
|
|
|
|
#define SQR(x) ((x)*(x))
|
|
|
|
int contest(int b,int g,int r)
|
|
{
|
|
/* finds closest neuron (min dist) and updates freq */
|
|
/* finds best neuron (min dist-bias) and returns position */
|
|
/* for frequently chosen neurons, freq[i] is high and bias[i] is negative */
|
|
/* bias[i] = gamma*((1/netsize)-freq[i]) */
|
|
|
|
int i,dist,a,biasdist,betafreq;
|
|
int bestpos,bestbiaspos,bestd,bestbiasd;
|
|
int *p,*f, *n;
|
|
|
|
bestd = ~(((int) 1)<<31);
|
|
bestbiasd = bestd;
|
|
bestpos = -1;
|
|
bestbiaspos = bestpos;
|
|
p = bias;
|
|
f = freq;
|
|
|
|
for (i=0; i<netsize; i++)
|
|
{
|
|
n = network[i];
|
|
|
|
dist = (SQR(n[2]-r)*30+SQR(n[1]-g)*59+SQR(n[0]-b)*11);
|
|
|
|
// dist = abs(n[0] - b) + abs(n[1]-g) + abs(n[2]-r); // original
|
|
|
|
if (dist<bestd)
|
|
{
|
|
bestd=dist;
|
|
bestpos=i;
|
|
}
|
|
|
|
biasdist = dist - ((*p)>>(intbiasshift-netbiasshift));
|
|
|
|
if (biasdist<bestbiasd)
|
|
{
|
|
bestbiasd=biasdist;
|
|
bestbiaspos=i;
|
|
}
|
|
|
|
betafreq = (*f >> betashift);
|
|
*f++ -= betafreq;
|
|
*p++ += (betafreq<<gammashift);
|
|
}
|
|
|
|
freq[bestpos] += beta;
|
|
bias[bestpos] -= betagamma;
|
|
|
|
return(bestbiaspos);
|
|
}
|
|
|
|
|
|
|
|
int FTOI(float foo);
|
|
#pragma aux FTOI = \
|
|
"push eax"\
|
|
"fistp dword ptr [esp]" \
|
|
"pop eax" \
|
|
parm [8087] value [eax];
|
|
|
|
/* Move neuron i towards biased (b,g,r) by factor alpha
|
|
---------------------------------------------------- */
|
|
|
|
void altersingle(int alpha,int i,int b,int g,int r)
|
|
{
|
|
int *n;
|
|
float f;
|
|
|
|
n = network[i]; /* alter hit neuron */
|
|
f = alpha*(1.0/(float)initalpha);
|
|
|
|
n[0] -= FTOI((n[0] - b)*f);
|
|
n[1] -= FTOI((n[1] - g)*f);
|
|
n[2] -= FTOI((n[2] - r)*f);
|
|
}
|
|
|
|
|
|
/* Move adjacent neurons by precomputed alpha*(1-((i-j)^2/[r]^2)) in radpower[|i-j|]
|
|
--------------------------------------------------------------------------------- */
|
|
|
|
void alterneigh (int rad, int i, int b, int g, int r)
|
|
{
|
|
int j,k,lo,hi;
|
|
int *p, *q;
|
|
float mul;
|
|
|
|
lo = i-rad;
|
|
if (lo<-1)
|
|
lo=-1;
|
|
|
|
hi = i+rad;
|
|
if (hi>netsize)
|
|
hi=netsize;
|
|
|
|
j = i+1;
|
|
k = i-1;
|
|
q = radpower;
|
|
|
|
while ((j<hi) || (k>lo))
|
|
{
|
|
mul = (float)(*(++q))/alpharadbias;
|
|
|
|
if (j<hi)
|
|
{
|
|
p = network[j];
|
|
|
|
p[0] -= FTOI((p[0]-b)*mul);
|
|
p[1] -= FTOI((p[1]-g)*mul);
|
|
p[2] -= FTOI((p[2]-r)*mul);
|
|
j++;
|
|
}
|
|
|
|
if (k>lo)
|
|
{
|
|
p = network[k];
|
|
p[0] -= FTOI ((p[0]-b)*mul);
|
|
p[1] -= FTOI ((p[1]-g)*mul);
|
|
p[2] -= FTOI ((p[2]-r)*mul);
|
|
k--;
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
/* Main Learning Loop
|
|
------------------ */
|
|
|
|
void learn()
|
|
{
|
|
int i,j,b,g,r;
|
|
int radius,rad,alpha,step,delta,samplepixels,r2;
|
|
|
|
unsigned char *p;
|
|
unsigned char *lim;
|
|
int percadd,perc;
|
|
|
|
|
|
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<rad; i++)
|
|
radpower[i] = alpha*(((rad*rad - i*i)*radbias)/(rad*rad));
|
|
|
|
if ((lengthcount%prime1))
|
|
step = 3*prime1;
|
|
else
|
|
{
|
|
if ((lengthcount%prime2))
|
|
step = 3*prime2;
|
|
else
|
|
{
|
|
if ((lengthcount%prime3))
|
|
step = 3*prime3;
|
|
else
|
|
step = 3*prime4;
|
|
}
|
|
}
|
|
|
|
i = 0;
|
|
|
|
percadd = (samplepixels/70);
|
|
perc = percadd;
|
|
|
|
while (i < samplepixels)
|
|
{
|
|
|
|
if (i>perc)
|
|
{
|
|
check_abort();
|
|
printf("%cLearning (%d%%)",13,(i*100)/samplepixels);
|
|
perc = i+percadd;
|
|
fflush(stdout);
|
|
}
|
|
|
|
b = p[0] << netbiasshift;
|
|
g = p[1] << netbiasshift;
|
|
r = p[2] << netbiasshift;
|
|
j = contest(b,g,r);
|
|
|
|
altersingle(alpha,j,b,g,r);
|
|
|
|
if (rad)
|
|
alterneigh(rad,j,b,g,r); /* alter neighbours */
|
|
|
|
p += step;
|
|
if (p >= lim)
|
|
p -= lengthcount;
|
|
|
|
i++;
|
|
|
|
if (!(i%delta))
|
|
{
|
|
alpha -= alpha / alphadec;
|
|
radius -= radius / radiusdec;
|
|
rad = radius >> radiusbiasshift;
|
|
|
|
if (rad <= 1)
|
|
rad = 0;
|
|
|
|
r2 = rad*rad;
|
|
|
|
for (j=0; j<rad; j++)
|
|
radpower[j] = alpha*(((r2 - j*j)*radbias)/r2);
|
|
}
|
|
}
|
|
}
|