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