This is ColorMap.m in view mode; [Download] [Up]
/*
getmap.c 1995-07-02
ColorMap.m 1995-12-18
by T.Ogihara (ogihara@seg.kobe-u.ac.jp)
Checks number of color used in the image.
Reduces color by median cut algorithm (MCA) of Paul Heckbert.
This code refers to "ppmquant" of Jef Poskanzer, but, in
many cases, this program could generate more beautiful image.
*/
#import "ColorMap.h"
#import <stdio.h>
#import <stdlib.h>
#import <string.h>
#import <appkit/color.h>
#import <appkit/Control.h>
#import "common.h"
#import "getpixel.h"
#define EnoughMemory 1
#if EnoughMemory
# define COLORSTEPS 65536 /* = 0x10000 */
# define MAXColors 62000 /* < COLORSTEPS */
# define ColorHash(r,g,b) ( ((r)<<8) | (g) ) /* Hash KEY */
# define ColorHnew(x) (((x) + 5987) & 0xffff)
typedef int indexint;
#else
# define COLORSTEPS 32768 /* = 32 ^ 3 = 0x8000 */
# define MAXColors 30000 /* < COLORSTEPS */
# define ColorHash(r,g,b) ( ((r)<<7) | ((g) & 0x7f) ) /* Hash KEY */
# define ColorHnew(x) (((x) + 5987) & 0x7fff)
typedef short indexint;
#endif
typedef struct {
int count;
unsigned char red, green, blue;
unsigned char palidx; /* index for palette */
} tabcell;
typedef struct {
int index, colors;
int sum;
} element;
/* quick sort */
static int q_red(int);
static int q_green(int);
static int q_blue(int);
static int q_colors(int);
static int q_count(int);
static int q_palette(int);
static void inssort(int, indexint *, int (*)(int));
static void quicksort(int, indexint *, int (*)(int));
static int hashIndex(int, int, int);
static void SortMaxElement(int, int);
static void makepalette(element *, int, BOOL);
@implementation ColorMap
static tabcell *hashtab;
static indexint *pindex;
static paltype *pal;
static int colornum; /* Number of colors used in the image */
static int totalnum;
static BOOL hasalpha;
int mapping(int r, int g, int b)
{
return hashtab[hashIndex(r,g,b)].palidx;
}
- init
{
hashtab = NULL;
pindex = NULL;
pal = NULL;
return self;
}
- allocFullColor
{
hashtab = (tabcell *)calloc(COLORSTEPS, sizeof(tabcell));
pindex = (indexint *)calloc(COLORSTEPS, sizeof(indexint));
pal = (paltype *)calloc(FIXcount, sizeof(paltype));
if (!hashtab || !pindex || !pal)
return nil;
return self;
}
- allocPalColor
{
hashtab = (tabcell *)calloc(COLORSTEPS, sizeof(tabcell));
if (!hashtab)
return nil;
return self;
}
- free
{
if (hashtab) free((void *)hashtab);
if (pindex) free((void *)pindex);
if (pal) free((void *)pal);
[super free];
return nil;
}
- init_regColor
{
int i;
for (i = 0; i < COLORSTEPS; i++)
pindex[i] = i;
bzero((void *)hashtab, sizeof(tabcell)*COLORSTEPS);
colornum = 0;
totalnum = 0;
hasalpha = NO;
return self;
}
- (int)getAllColor:(unsigned char **)map limit:(int)limit alpha:(BOOL *)alpha
/* 使われている色数を返す。
limit は色数の上限で、alpha は色数として考慮しない。
limit=0 の時は MAXColors を上限とする。
色数が多すぎて数えられない、あるいはもう数える必要がない
場合は COLORSTEPS が返され、変数 colornum は０にセットされる。 */
{
int r, g, b, a;
int maxclr = MAXColors - 1;
if (limit > 0) maxclr = limit;
[self init_regColor];
resetPixel(map, 0);
while (getPixel(&r, &g, &b, &a) >= 0) {
if (a != AlphaTransp) {
(void)hashIndex(r,g,b);
if (colornum > maxclr)
break; /* Too many color */
}else hasalpha = YES;
}
*alpha = hasalpha;
if (colornum > maxclr) { /* Too many color */
colornum = 0;
return COLORSTEPS;
}
return colornum;
}
- (int)getAllColor:(unsigned char **)map limit:(int)limit
/* 使われている色数を返す。
上のメソッドと同じだが、alpha があったら１色（白）として
考慮する。alpha値を使わない形式へ変更する場合に使う。 */
{
BOOL alpha;
int cnum;
int maxclr = MAXColors - 1;
if (limit > 0) maxclr = limit;
cnum = [self getAllColor:map limit:maxclr alpha:&alpha];
if (cnum > maxclr) /* Too many color */
return COLORSTEPS;
if (alpha) {
(void)hashIndex(255, 255, 255); /* for transparent */
if ((cnum = colornum) > maxclr) { /* Too many color */
colornum = 0;
return COLORSTEPS;
}
}
return cnum;
}
- (int)regColorToMap: (int)red : (int)green : (int)blue
/* getAllColor: のように使われている色数を数えるが、１ピクセル
ごとに呼び出す。
色数が多すぎて数えられない場合は -1 が返され、変数 colornum は
０にセットされる。 */
{
(void)hashIndex(red, green, blue);
totalnum++;
if (colornum >= MAXColors) {
colornum = 0;
return -1;
}
return colornum;
}
- (int)regPalColorWithAlpha:(BOOL)alpha
/* パレットの中の色を調べ、ハッシュ表に登録しておく。 */
{
int r, g, b, idx;
BOOL hasWhite = NO;
colornum = 0;
hasalpha = NO;
for (idx = 0; getPalPixel(&r, &g, &b) >= 0; idx++) {
hashtab[hashIndex(r,g,b)].palidx = idx;
if (!hasWhite && r == 255 && g == 255 && b == 255)
hasWhite = YES;
}
if (!alpha && !hasWhite) {
if (idx >= FIXcount)
return (FIXcount + 1); /* no room */
hashtab[hashIndex(255,255,255)].palidx = idx++;
}
return idx; /* return number of colors */
}
- (paltype *)getNormalmap:(int *)cnum
/* getAllColor: の後で使い、パレットを返す。
使われている色が 256色以内であること。 */
{
unsigned char *p;
tabcell *t;
int i, x, num;
quicksort(COLORSTEPS, pindex, q_colors);
for (i = 0, num = 0; i < COLORSTEPS && num < FIXcount; i++) {
if (hashtab[x = pindex[i]].count == 0) continue;
t = &hashtab[x];
p = pal[num];
p[RED] = t->red;
p[GREEN] = t->green;
p[BLUE] = t->blue;
t->palidx = num++;
}
*cnum = num;
return pal;
}
- (paltype *)getReducedMap:(int *)cnum alpha:(BOOL)alpha
/* Median Cut Algorithm */
{
int i, w;
element elm[FIXcount];
int ncolors, elmptr, curelm;
int indx, clrs, sm;
int halfsum, lowersum;
ncolors = *cnum;
if (ncolors < 2 || ncolors > FIXcount)
ncolors = FIXcount;
if (alpha) ncolors--;
quicksort(COLORSTEPS, pindex, q_count);
for (i = 0; i < COLORSTEPS; i++)
if (hashtab[pindex[i]].count) break;
elm[0].index = i;
elm[0].colors = COLORSTEPS - i;
elm[0].sum = totalnum;
elmptr = 1;
while (elmptr < ncolors) {
/* Find largest element */
curelm = -1;
w = 2; /* should be divided */
for (i = 0; i < elmptr; i++) {
if (elm[i].colors >= w)
w = elm[curelm = i].colors;
}
if (curelm < 0)
break; /* all color was found */
indx = elm[curelm].index;
clrs = elm[curelm].colors;
sm = elm[curelm].sum;
SortMaxElement(indx, clrs);
/* Find the median */
w = clrs - 1;
lowersum = 0;
halfsum = sm / 2;
for (i = 0; i < w && lowersum < halfsum; i++)
lowersum += hashtab[pindex[indx + i]].count;
/* Divide the box */
elm[curelm].colors = i;
elm[curelm].sum = lowersum;
elm[elmptr].index = indx + i;
elm[elmptr].colors = clrs - i;
elm[elmptr].sum = sm - lowersum;
++elmptr;
}
makepalette(elm, elmptr, alpha);
*cnum = elmptr;
return pal;
}
- (paltype *)getPalette
{
paltype *p = pal;
pal = NULL;
return p;
}
@end
static int hashIndex(int r, int g, int b)
{
tabcell *tp;
int x = ColorHash(r,g,b);
tp = &hashtab[x];
while (tp->count > 0
&& (tp->red != r || tp->green != g || tp->blue != b))
tp = &hashtab[x = ColorHnew(x)];
if (tp->count == 0) {
tp->red = r;
tp->green = g;
tp->blue = b;
colornum++;
}
tp->count++;
return x;
}
static void SortMaxElement(int indx, int clrs)
{
int i, j, end;
unsigned short min[3], max[3], val[3];
float bright[3];
tabcell *t;
/* Find the minimum and maximum of each component */
for (i = 0; i < 3; i++)
min[i] = 255, max[i] = 0;
end = indx + clrs;
for (i = indx; i < end; i++) {
t = &hashtab[pindex[i]];
if (t->count == 0)
continue;
val[RED] = t->red;
val[GREEN] = t->green;
val[BLUE] = t->blue;
for (j = 0; j < 3; j++) {
if (min[j] > val[j]) min[j] = val[j];
if (max[j] < val[j]) max[j] = val[j];
}
}
/* calculate brightness */
bright[RED] = (max[RED] - min[RED]) * 0.299;
bright[GREEN] = (max[GREEN] - min[GREEN]) * 0.587;
bright[BLUE] = (max[BLUE] - min[BLUE]) * 0.114;
if ( bright[RED] >= bright[GREEN] && bright[RED] >= bright[BLUE] )
quicksort(clrs, &pindex[indx], q_red);
else if ( bright[GREEN] >= bright[BLUE] )
quicksort(clrs, &pindex[indx], q_green);
else
quicksort(clrs, &pindex[indx], q_blue);
}
static void makepalette(element *elm, int cellnum, BOOL alpha)
{
int indx, clrs, i, ex, best;
long r, g, b, w, sum;
unsigned char *p;
tabcell *t;
for (ex = 0; ex < cellnum; ex++) {
indx = elm[ex].index;
clrs = elm[ex].colors;
r = g = b = 0, sum = 0;
p = pal[ex];
w = indx + clrs;
for (i = indx; i < w; i++) {
int c = (t = &hashtab[pindex[i]])->count;
r += t->red * c;
g += t->green * c;
b += t->blue * c;
sum += c;
}
p[RED] = ((r /= sum) < 256) ? r : 255;
p[GREEN] = ((g /= sum) < 256) ? g : 255;
p[BLUE] = ((b /= sum) < 256) ? b : 255;
}
/* Values of pindex[] are not used any more.
Sort the palette. */
for (i = 0; i < cellnum; i++)
pindex[i] = i;
quicksort(cellnum, pindex, q_palette);
for (ex = 0; ex < cellnum; ex++) {
unsigned char *q;
int x, y;
x = pindex[ex];
if (ex == x) continue;
for (y = ex+1; y < cellnum; y++)
if (pindex[y] == ex) break;
p = pal[x];
q = pal[ex];
for (i = 0; i < 3; i++)
r = p[i], p[i] = q[i], q[i] = r;
pindex[ex] = ex;
pindex[y] = x;
}
if (alpha /* && cellnum < FIXcount */) {
p = pal[cellnum];
for (i = 0; i < 3; i++)
p[i] = 255;
}
for (i = 0; i < COLORSTEPS; i++) {
if (hashtab[i].count == 0) continue;
t = &hashtab[i];
r = t->red;
g = t->green;
b = t->blue;
w = 4 * 256 * 256;
best = 0;
for (ex = 0; ex < cellnum; ex++) {
long rr, gg, bb;
p = pal[ex];
rr = r - p[RED];
gg = g - p[GREEN];
bb = b - p[BLUE];
if ((sum = rr*rr + gg*gg + bb*bb) < w)
w = sum, best = ex;
}
t->palidx = best;
}
}
/* ----------------------------------------------------------------
QUICK SORT by Haruhiko Okumura
奥村晴彦「Ｃ言語による最新アルゴリズム事典」（技術評論社）
modified by T. Ogihara
----------------------------------------------------------------- */
static int q_red(int x) { return hashtab[x].red; }
static int q_green(int x) { return hashtab[x].green; }
static int q_blue(int x) { return hashtab[x].blue; }
static int q_count(int x) { return hashtab[x].count; }
static int q_colors(int x) {
tabcell *t = &hashtab[x];
return (t->count)
? ((t->red << 16) | (t->green << 8) | t->blue) : 0;
}
static int q_palette(int x) {
unsigned char *p = pal[x];
return ((p[RED] << 16) | (p[GREEN] << 8) | p[BLUE]);
}
static void inssort(int n, indexint *a, int (*qval)(int))
{
int i, j, val;
indexint x;
for (i = 1; i < n; i++) {
val = qval(x = a[i]);
for (j = i - 1; j >= 0 && qval(a[j]) > val; j--)
a[j + 1] = a[j];
a[j + 1] = x;
}
}
#define QS_THRESHOLD 10
#define QS_STACKSIZE 32 /* たかだか int のビット数程度 */
static void quicksort(int n, indexint *ar, int (*qval)(int))
{
int i, j, left, right, p;
int leftstack[QS_STACKSIZE], rightstack[QS_STACKSIZE];
indexint t;
int x;
left = 0; right = n - 1; p = 0;
for ( ; ; ) {
if (right - left <= QS_THRESHOLD) {
if (p == 0) break;
p--;
left = leftstack[p];
right = rightstack[p];
}
x = qval(ar[(left + right) / 2]);
i = left; j = right;
for ( ; ; ) {
while (qval(ar[i]) < x) i++;
while (x < qval(ar[j])) j--;
if (i >= j) break;
t = ar[i]; ar[i] = ar[j]; ar[j] = t;
i++; j--;
}
if (i - left > right - j) {
if (i - left > QS_THRESHOLD) {
leftstack[p] = left;
rightstack[p] = i - 1;
p++;
}
left = j + 1;
} else {
if (right - j > QS_THRESHOLD) {
leftstack[p] = j + 1;
rightstack[p] = right;
p++;
}
right = i - 1;
}
}
inssort(n, ar, qval);
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.