1 |
greg |
1.1 |
#ifndef lint |
2 |
schorsch |
2.4 |
static const char RCSid[] = "$Id: closest.c,v 2.3 2003/07/27 22:12:03 schorsch Exp $"; |
3 |
greg |
1.1 |
#endif |
4 |
greg |
1.2 |
/* |
5 |
greg |
1.1 |
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 |
schorsch |
2.4 |
#include <stdlib.h> |
16 |
|
|
|
17 |
greg |
1.1 |
#include "ciq.h" |
18 |
|
|
|
19 |
|
|
#define inf 3*256*256 |
20 |
ph |
1.3 |
#define key(r,g,b) (((r)&0xe0)<<1|((g)&0xe0)>>2|((b)&0xe0)>>5) |
21 |
|
|
/* 9-bit hash key: rrrgggbbb */ |
22 |
greg |
1.1 |
|
23 |
ph |
1.3 |
static struct thing {int mindist,pv;} space[512*257],*next,*bucket[512]; |
24 |
greg |
1.1 |
/* sorted lists of colors */ |
25 |
|
|
|
26 |
ph |
1.3 |
static int nfill,tests,calls; |
27 |
greg |
1.1 |
static char filled[512]; /* has bucket[key] been filled yet? */ |
28 |
|
|
static int sq[511]; |
29 |
|
|
|
30 |
schorsch |
2.4 |
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 |
greg |
1.1 |
int k; |
37 |
|
|
nfill = tests = calls = 0; |
38 |
|
|
for (k=0; k<512; k++) filled[k] = 0; |
39 |
|
|
next = space; |
40 |
|
|
} |
41 |
|
|
|
42 |
schorsch |
2.4 |
int |
43 |
|
|
closest( /* find pv of colormap color closest to (r,g,b) */ |
44 |
|
|
int r, |
45 |
|
|
int g, |
46 |
|
|
int b |
47 |
|
|
) |
48 |
greg |
1.1 |
{ |
49 |
|
|
register struct thing *p; |
50 |
ph |
1.3 |
register int *rsq,*gsq,*bsq,dist,min; |
51 |
|
|
int best,k; |
52 |
greg |
1.1 |
struct thing *p0; |
53 |
|
|
|
54 |
ph |
1.3 |
k = key(r,g,b); |
55 |
|
|
if (!filled[k]) fillbucket(k); |
56 |
greg |
1.1 |
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 |
ph |
1.3 |
for (p0=p=bucket[k]; min>p->mindist; p++) { |
63 |
greg |
1.1 |
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 |
schorsch |
2.4 |
static int |
78 |
|
|
compare( |
79 |
|
|
const void *a, |
80 |
|
|
const void *b |
81 |
|
|
) |
82 |
greg |
1.1 |
{ |
83 |
schorsch |
2.4 |
return ((struct thing*)a)->mindist - ((struct thing*)b)->mindist; |
84 |
greg |
1.1 |
} |
85 |
|
|
|
86 |
schorsch |
2.4 |
static void |
87 |
|
|
fillbucket( /* make list of colormap colors which could be closest */ |
88 |
|
|
int k /* matches for colors in bucket #k */ |
89 |
|
|
) |
90 |
greg |
1.1 |
{ |
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 |
schorsch |
2.3 |
r = (k>>1&0xe0)|H; /* center of 32x32x32 cubical bucket */ |
97 |
|
|
g = (k<<2&0xe0)|H; |
98 |
|
|
b = (k<<5&0xe0)|H; |
99 |
greg |
1.1 |
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 |
|
|
}*/ |