| 1 |
greg |
1.2 |
/* Copyright 1988 Regents of the University of California */
|
| 2 |
greg |
1.1 |
|
| 3 |
|
|
#ifndef lint
|
| 4 |
|
|
static char SCCSid[] = "$SunId$ LBL";
|
| 5 |
|
|
#endif
|
| 6 |
greg |
1.2 |
|
| 7 |
|
|
/*
|
| 8 |
greg |
1.1 |
CLOSEST - nearest-color lookup by locally ordered search
|
| 9 |
|
|
we use distance in rgb space as color metric
|
| 10 |
|
|
|
| 11 |
|
|
fillbucket subroutine makes trimmed, sorted lists of
|
| 12 |
|
|
possible closest colors to speed the closest searching.
|
| 13 |
|
|
About 6 times faster than exhaustive.
|
| 14 |
|
|
|
| 15 |
|
|
Paul Heckbert
|
| 16 |
|
|
*/
|
| 17 |
|
|
|
| 18 |
|
|
#include "ciq.h"
|
| 19 |
|
|
|
| 20 |
|
|
#define inf 3*256*256
|
| 21 |
|
|
#define key ((r&0xe0)<<1|(g&0xe0)>>2|(b&0xe0)>>5) /* hash key: rrrgggbbb */
|
| 22 |
|
|
|
| 23 |
|
|
static struct thing {int mindist,pv;} space[512*257],*next=space,*bucket[512];
|
| 24 |
|
|
/* sorted lists of colors */
|
| 25 |
|
|
|
| 26 |
|
|
static int nfill=0,tests=0,calls=0;
|
| 27 |
|
|
static char filled[512]; /* has bucket[key] been filled yet? */
|
| 28 |
|
|
static int sq[511];
|
| 29 |
|
|
|
| 30 |
|
|
initialize() { /* reset the buckets */
|
| 31 |
|
|
int k;
|
| 32 |
|
|
nfill = tests = calls = 0;
|
| 33 |
|
|
for (k=0; k<512; k++) filled[k] = 0;
|
| 34 |
|
|
next = space;
|
| 35 |
|
|
}
|
| 36 |
|
|
|
| 37 |
|
|
closest(r,g,b) /* find pv of colormap color closest to (r,g,b) */
|
| 38 |
|
|
int r,g,b;
|
| 39 |
|
|
{
|
| 40 |
|
|
register struct thing *p;
|
| 41 |
|
|
register int *rsq,*gsq,*bsq,dist,min,best;
|
| 42 |
|
|
struct thing *p0;
|
| 43 |
|
|
|
| 44 |
|
|
if (!filled[key]) fillbucket(key);
|
| 45 |
|
|
min = inf;
|
| 46 |
|
|
rsq = sq+255-r;
|
| 47 |
|
|
gsq = sq+255-g;
|
| 48 |
|
|
bsq = sq+255-b;
|
| 49 |
|
|
|
| 50 |
|
|
/* stop looking when best is closer than next could be */
|
| 51 |
|
|
for (p0=p=bucket[key]; min>p->mindist; p++) {
|
| 52 |
|
|
dist = rsq[color[0][p->pv]] + gsq[color[1][p->pv]] +
|
| 53 |
|
|
bsq[color[2][p->pv]];
|
| 54 |
|
|
if (dist<min) {
|
| 55 |
|
|
best = p->pv;
|
| 56 |
|
|
min = dist;
|
| 57 |
|
|
}
|
| 58 |
|
|
}
|
| 59 |
|
|
tests += p-p0;
|
| 60 |
|
|
calls++;
|
| 61 |
|
|
return best;
|
| 62 |
|
|
}
|
| 63 |
|
|
|
| 64 |
|
|
#define H 16 /* half-width of a bucket */
|
| 65 |
|
|
|
| 66 |
|
|
compare(a,b)
|
| 67 |
|
|
register struct thing *a,*b;
|
| 68 |
|
|
{
|
| 69 |
|
|
return a->mindist-b->mindist;
|
| 70 |
|
|
}
|
| 71 |
|
|
|
| 72 |
|
|
fillbucket(k) /* make list of colormap colors which could be closest */
|
| 73 |
|
|
int k; /* matches for colors in bucket #k */
|
| 74 |
|
|
{
|
| 75 |
|
|
register int r,g,b,j,dist,*rsq,*gsq,*bsq,min,best;
|
| 76 |
|
|
struct thing *p,*q;
|
| 77 |
|
|
|
| 78 |
|
|
if (!sq[0]) for (j= -255; j<256; j++) sq[j+255] = j*j;
|
| 79 |
|
|
|
| 80 |
|
|
r = k>>1&0xe0|H; /* center of 32x32x32 cubical bucket */
|
| 81 |
|
|
g = k<<2&0xe0|H;
|
| 82 |
|
|
b = k<<5&0xe0|H;
|
| 83 |
|
|
rsq = sq+255-r;
|
| 84 |
|
|
gsq = sq+255-g;
|
| 85 |
|
|
bsq = sq+255-b;
|
| 86 |
|
|
bucket[k] = p = next;
|
| 87 |
|
|
min = inf;
|
| 88 |
|
|
|
| 89 |
|
|
for (j=0; j<n; j++, p++) {
|
| 90 |
|
|
p->pv = j;
|
| 91 |
|
|
dist = 0; /* compute distance from cube surface */
|
| 92 |
|
|
if (color[0][j]< r-H) dist += rsq[color[0][j]+H];
|
| 93 |
|
|
else if (color[0][j]>=r+H) dist += rsq[color[0][j]-H+1];
|
| 94 |
|
|
if (color[1][j]< g-H) dist += gsq[color[1][j]+H];
|
| 95 |
|
|
else if (color[1][j]>=g+H) dist += gsq[color[1][j]-H+1];
|
| 96 |
|
|
if (color[2][j]< b-H) dist += bsq[color[2][j]+H];
|
| 97 |
|
|
else if (color[2][j]>=b+H) dist += bsq[color[2][j]-H+1];
|
| 98 |
|
|
p->mindist = dist; /* for termination test in closest */
|
| 99 |
|
|
dist = rsq[color[0][j]]+gsq[color[1][j]]+bsq[color[2][j]];
|
| 100 |
|
|
if (dist<min) { /* find color closest to cube center */
|
| 101 |
|
|
best = j;
|
| 102 |
|
|
min = dist;
|
| 103 |
|
|
}
|
| 104 |
|
|
}
|
| 105 |
|
|
|
| 106 |
|
|
dist = rsq[color[0][best]+(color[0][best]<r?1-H:H)] +
|
| 107 |
|
|
gsq[color[1][best]+(color[1][best]<g?1-H:H)] +
|
| 108 |
|
|
bsq[color[2][best]+(color[2][best]<b?1-H:H)];
|
| 109 |
|
|
/* dist is an upper bound on mindist: maximum possible distance */
|
| 110 |
|
|
/* between a color in the bucket and its nearest neighbor */
|
| 111 |
|
|
|
| 112 |
|
|
/* eliminate colors which couldn't be closest */
|
| 113 |
|
|
for (p=q=next, j=0; j<n; j++, p++)
|
| 114 |
|
|
if (p->mindist<dist) {
|
| 115 |
|
|
q->mindist = p->mindist;
|
| 116 |
|
|
q->pv = p->pv;
|
| 117 |
|
|
q++;
|
| 118 |
|
|
}
|
| 119 |
|
|
if (q<=next) fprintf(stderr,"ERROR: empty bucket!\n");
|
| 120 |
|
|
|
| 121 |
|
|
/* and sort the list by mindist */
|
| 122 |
|
|
qsort(next,q-next,sizeof(struct thing),compare);
|
| 123 |
|
|
q->mindist = inf; /* list terminator */
|
| 124 |
|
|
next = q+1;
|
| 125 |
|
|
filled[k] = 1;
|
| 126 |
|
|
nfill++;
|
| 127 |
|
|
}
|
| 128 |
|
|
|
| 129 |
|
|
/*endclosest() {
|
| 130 |
|
|
printf("filled %d buckets, averaging %d colors per list, %d of which were tested\n",
|
| 131 |
|
|
nfill,(next-space-nfill)/nfill,tests/calls);
|
| 132 |
|
|
}*/
|
