source: trunk/JPGPROC/source/gbmsrc/gbmhist.c@ 4

Last change on this file since 4 was 2, checked in by stevenhl, 8 years ago

Import sources from cwmm-full.zip dated 2005-03-21
File size: 5.6 KB
Line 
1/*
2
3gbmhist.c - Histogram/Frequency-of-use method of colour reduction
4
5*/
6
7/*...sincludes:0:*/
8#include <stdio.h>
9#include <stddef.h>
10#include <stdlib.h>
11#include <string.h>
12#include "gbm.h"
13
14/*...vgbm\46\h:0:*/
15/*...e*/
16
17#define N_COLS 2049
18#define N_HASH 5191
19#define HASH(r,g,b) (word) ( (((r)+(g))*((g)+(b))*((b)+(r))) % N_HASH )
20
21typedef struct { byte b, g, r; dword freq; byte nearest; } FREQ;
22
23typedef struct
24 {
25 int n_cols;
26 byte rm, gm, bm;
27 FREQ f[N_COLS];
28 word ht[N_HASH];
29 } GBMHIST;
30
31/*...sgbm_create_hist \45\ create empty hist:0:*/
32GBMHIST *gbm_create_hist(
33 byte rm, byte gm, byte bm
34 )
35 {
36 GBMHIST *hist;
37
38 if ( (hist = malloc((size_t) sizeof(GBMHIST))) == NULL )
39 return NULL;
40 hist->rm = rm;
41 hist->gm = gm;
42 hist->bm = bm;
43 hist->n_cols = 0;
44 memset(hist->ht, 0xff, N_HASH * sizeof(word));
45 return hist;
46 }
47/*...e*/
48/*...sgbm_delete_hist \45\ delete hist:0:*/
49void gbm_delete_hist(GBMHIST *hist)
50 {
51 free(hist);
52 }
53/*...e*/
54/*...sgbm_add_to_hist \45\ add bitmap data to hist:0:*/
55BOOLEAN gbm_add_to_hist(
56 GBMHIST *hist,
57 const GBM *gbm, const byte *data24
58 )
59 {
60 int stride24 = ((gbm->w * 3 + 3) & ~3);
61 int step24 = stride24 - gbm->w * 3;
62 FREQ *f = hist->f ;
63 word *ht = hist->ht;
64 byte rm = hist->rm;
65 byte gm = hist->gm;
66 byte bm = hist->bm;
67 int x, y, n_cols = hist->n_cols;
68
69 for ( y = 0; y < gbm->h; y++, data24 += step24 )
70 for ( x = 0; x < gbm->w; x++ )
71 {
72 byte b = (byte) (*data24++ & bm);
73 byte g = (byte) (*data24++ & gm);
74 byte r = (byte) (*data24++ & rm);
75 word hc = HASH(r,g,b);
76 word inx;
77
78 for ( ;; )
79 {
80 inx = ht[hc];
81 if ( inx == 0xffff ||
82 (f[inx].r == r &&
83 f[inx].g == g &&
84 f[inx].b == b) )
85 break;
86 if ( ++hc == N_HASH ) hc = 0;
87 }
88
89 /* Note: loop will always be broken out of */
90 /* We don't allow ht to fill up above half full */
91
92 if ( inx == 0xffff )
93 /* Not found in hash table */
94 {
95 if ( n_cols == N_COLS )
96 return FALSE;
97 f[n_cols].freq = (dword) 1;
98 f[n_cols].b = b;
99 f[n_cols].g = g;
100 f[n_cols].r = r;
101 ht[hc] = n_cols++;
102 }
103 else
104 /* Found in hash table */
105 /* update index inx */
106 f[inx].freq++;
107 }
108 hist->n_cols = n_cols;
109 return TRUE;
110 }
111/*...e*/
112/*...sgbm_pal_hist \45\ work out a palette from hist:0:*/
113void gbm_pal_hist(
114 GBMHIST *hist,
115 GBMRGB gbmrgb[],
116 int n_cols_wanted
117 )
118 {
119 FREQ *f = hist->f;
120 int i;
121
122 /* Now find the n_cols_wanted most frequently used ones */
123
124 for ( i = 0; i < n_cols_wanted && i < hist->n_cols; i++ )
125 {
126 int j, max_j;
127 dword max_freq = 0;
128
129 for ( j = 0; j < hist->n_cols; j++ )
130 if ( f[j].freq > max_freq )
131 {
132 max_j = j;
133 max_freq = f[j].freq;
134 }
135 f[max_j].nearest = (byte) i;
136 f[max_j].freq = (dword) 0; /* Prevent later use of f[max_j] */
137 gbmrgb[i].b = f[max_j].b;
138 gbmrgb[i].g = f[max_j].g;
139 gbmrgb[i].r = f[max_j].r;
140 }
141
142 /* Unused palette entries will be medium grey */
143 for ( ; i < 0x100; i++ )
144 {
145 gbmrgb[i].r = 0x80;
146 gbmrgb[i].g = 0x80;
147 gbmrgb[i].b = 0x80;
148 }
149
150 /* For the rest, find the closest one in the first n_cols_wanted */
151
152 for ( i = 0; i < hist->n_cols; i++ )
153 if ( f[i].freq != (dword) 0 )
154 {
155 int j, min_j;
156 int min_dist = 3*256*256;
157
158 for ( j = 0; j < n_cols_wanted; j++ )
159 {
160 int db = (int) f[i].b - (int) gbmrgb[j].b;
161 int dg = (int) f[i].g - (int) gbmrgb[j].g;
162 int dr = (int) f[i].r - (int) gbmrgb[j].r;
163 int dist = dr*dr + dg*dg + db*db;
164
165 if ( dist < min_dist )
166 {
167 min_dist = dist;
168 min_j = j;
169 }
170 }
171 f[i].nearest = (byte) min_j;
172 }
173 }
174/*...e*/
175/*...sgbm_map_hist \45\ map bitmap data to hist palette:0:*/
176void gbm_map_hist(
177 GBMHIST *hist,
178 const GBM *gbm, const byte *data24, byte *data8
179 )
180 {
181 int stride24 = ((gbm->w * 3 + 3) & ~3);
182 int step24 = stride24 - gbm->w * 3;
183 int stride8 = ((gbm->w + 3) & ~3);
184 int step8 = stride8 - gbm->w;
185 FREQ *f = hist->f;
186 word *ht = hist->ht;
187 byte rm = hist->rm;
188 byte gm = hist->gm;
189 byte bm = hist->bm;
190 int x, y;
191
192 for ( y = 0; y < gbm->h; y++, data24 += step24, data8 += step8 )
193 for ( x = 0; x < gbm->w; x++ )
194 {
195 byte b = (*data24++ & bm);
196 byte g = (*data24++ & gm);
197 byte r = (*data24++ & rm);
198 word hc = HASH(r,g,b);
199 word inx;
200
201 for ( ;; )
202 {
203 inx = ht[hc];
204 if ( f[inx].r == r && f[inx].g == g && f[inx].b == b )
205 break;
206 if ( ++hc == N_HASH ) hc = 0;
207 }
208
209 *data8++ = f[inx].nearest;
210 }
211 }
212/*...e*/
213/*...sgbm_hist \45\ map single bitmap to frequency optimised palette:0:*/
214/*
215Determine the n_cols_wanted most frequently used colours from 24 bit data.
216Can be a problem since potentially 256*256*256 possible unique colours.
217Initially 8 bits green, 8 bits red, and 8 bits blue significant.
218When number of colours exceeds a limit number of bits of blue reduced by 1.
219Next time red, next time green, ...
220Sort most n_cols_wanted most frequently used colour in order of use.
221Put these in the returned palette.
222Map colours from n_cols_wanted exactly to colours in palette.
223For other colours, map them to the closest in the palette.
224*/
225
226BOOLEAN gbm_hist(
227 const GBM *gbm, const byte *data24,
228 GBMRGB gbmrgb[],
229 byte *data8,
230 int n_cols_wanted,
231 byte rm, byte gm, byte bm
232 )
233 {
234 GBMHIST *hist;
235
236 for ( ;; )
237 {
238 if ( (hist = gbm_create_hist(rm, gm, bm)) == NULL )
239 return FALSE;
240
241 if ( gbm_add_to_hist(hist, gbm, data24) )
242 break;
243
244 gbm_delete_hist(hist);
245
246 if ( gm > rm )
247 gm <<= 1;
248 else if ( rm > bm )
249 rm <<= 1;
250 else
251 bm <<= 1;
252 }
253
254 /* Above loop will always be exited as if masks get rough
255 enough, ultimately number of unique colours < N_COLS */
256
257 gbm_pal_hist(hist, gbmrgb, n_cols_wanted);
258 gbm_map_hist(hist, gbm, data24, data8);
259 gbm_delete_hist(hist);
260 return TRUE;
261 }
262/*...e*/
Note: See TracBrowser for help on using the repository browser.