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