diff options
Diffstat (limited to 'Imaging/libImaging/GetBBox.c')
| -rw-r--r-- | Imaging/libImaging/GetBBox.c | 322 |
1 files changed, 322 insertions, 0 deletions
diff --git a/Imaging/libImaging/GetBBox.c b/Imaging/libImaging/GetBBox.c new file mode 100644 index 0000000..c06d0eb --- /dev/null +++ b/Imaging/libImaging/GetBBox.c @@ -0,0 +1,322 @@ +/* + * The Python Imaging Library + * $Id: GetBBox.c 2298 2005-02-17 21:17:29Z fredrik $ + * + * helpers to bounding boxes, min/max values, number of colors, etc. + * + * history: + * 1996-07-22 fl Created + * 1996-12-30 fl Added projection stuff + * 1998-07-12 fl Added extrema stuff + * 2004-09-17 fl Added colors stuff + * + * Copyright (c) 1997-2004 by Secret Labs AB. + * Copyright (c) 1996-2004 by Fredrik Lundh. + * + * See the README file for details on usage and redistribution. + */ + + +#include "Imaging.h" + + +int +ImagingGetBBox(Imaging im, int bbox[4]) +{ + /* Get the bounding box for any non-zero data in the image.*/ + + int x, y; + int has_data; + + /* Initialize bounding box to max values */ + bbox[0] = im->xsize; + bbox[1] = -1; + bbox[2] = bbox[3] = 0; + +#define GETBBOX(image, mask)\ + for (y = 0; y < im->ysize; y++) {\ + has_data = 0;\ + for (x = 0; x < im->xsize; x++)\ + if (im->image[y][x] & mask) {\ + has_data = 1;\ + if (x < bbox[0])\ + bbox[0] = x;\ + if (x >= bbox[2])\ + bbox[2] = x+1;\ + }\ + if (has_data) {\ + if (bbox[1] < 0)\ + bbox[1] = y;\ + bbox[3] = y+1;\ + }\ + } + + if (im->image8) { + GETBBOX(image8, 0xff); + } else { + INT32 mask = 0xffffffff; + if (im->bands == 3) + ((UINT8*) &mask)[3] = 0; + GETBBOX(image32, mask); + } + + /* Check that we got a box */ + if (bbox[1] < 0) + return 0; /* no data */ + + return 1; /* ok */ +} + + +int +ImagingGetProjection(Imaging im, UINT8* xproj, UINT8* yproj) +{ + /* Get projection arrays for non-zero data in the image.*/ + + int x, y; + int has_data; + + /* Initialize projection arrays */ + memset(xproj, 0, im->xsize); + memset(yproj, 0, im->ysize); + +#define GETPROJ(image, mask)\ + for (y = 0; y < im->ysize; y++) {\ + has_data = 0;\ + for (x = 0; x < im->xsize; x++)\ + if (im->image[y][x] & mask) {\ + has_data = 1;\ + xproj[x] = 1;\ + }\ + if (has_data)\ + yproj[y] = 1;\ + } + + if (im->image8) { + GETPROJ(image8, 0xff); + } else { + INT32 mask = 0xffffffff; + if (im->bands == 3) + ((UINT8*) &mask)[3] = 0; + GETPROJ(image32, mask); + } + + return 1; /* ok */ +} + + +int +ImagingGetExtrema(Imaging im, void *extrema) +{ + int x, y; + INT32 imin, imax; + FLOAT32 fmin, fmax; + + if (im->bands != 1) { + ImagingError_ModeError(); + return -1; /* mismatch */ + } + + if (!im->xsize || !im->ysize) + return 0; /* zero size */ + + switch (im->type) { + case IMAGING_TYPE_UINT8: + imin = imax = im->image8[0][0]; + for (y = 0; y < im->ysize; y++) { + UINT8* in = im->image8[y]; + for (x = 0; x < im->xsize; x++) { + if (imin > in[x]) + imin = in[x]; + else if (imax < in[x]) + imax = in[x]; + } + } + ((UINT8*) extrema)[0] = (UINT8) imin; + ((UINT8*) extrema)[1] = (UINT8) imax; + break; + case IMAGING_TYPE_INT32: + imin = imax = im->image32[0][0]; + for (y = 0; y < im->ysize; y++) { + INT32* in = im->image32[y]; + for (x = 0; x < im->xsize; x++) { + if (imin > in[x]) + imin = in[x]; + else if (imax < in[x]) + imax = in[x]; + } + } + ((INT32*) extrema)[0] = imin; + ((INT32*) extrema)[1] = imax; + break; + case IMAGING_TYPE_FLOAT32: + fmin = fmax = ((FLOAT32*) im->image32[0])[0]; + for (y = 0; y < im->ysize; y++) { + FLOAT32* in = (FLOAT32*) im->image32[y]; + for (x = 0; x < im->xsize; x++) { + if (fmin > in[x]) + fmin = in[x]; + else if (fmax < in[x]) + fmax = in[x]; + } + } + ((FLOAT32*) extrema)[0] = fmin; + ((FLOAT32*) extrema)[1] = fmax; + break; + case IMAGING_TYPE_SPECIAL: + if (strcmp(im->mode, "I;16") == 0) { + imin = imax = ((UINT16*) im->image8[0])[0]; + for (y = 0; y < im->ysize; y++) { + UINT16* in = (UINT16 *) im->image[y]; + for (x = 0; x < im->xsize; x++) { + if (imin > in[x]) + imin = in[x]; + else if (imax < in[x]) + imax = in[x]; + } + } + ((UINT16*) extrema)[0] = (UINT16) imin; + ((UINT16*) extrema)[1] = (UINT16) imax; + break; + } + /* FALL THROUGH */ + default: + ImagingError_ModeError(); + return -1; + } + return 1; /* ok */ +} + + +/* static ImagingColorItem* getcolors8(Imaging im, int maxcolors, int* size);*/ +static ImagingColorItem* getcolors32(Imaging im, int maxcolors, int* size); + +ImagingColorItem* +ImagingGetColors(Imaging im, int maxcolors, int* size) +{ + /* FIXME: add support for 8-bit images */ + return getcolors32(im, maxcolors, size); +} + +static ImagingColorItem* +getcolors32(Imaging im, int maxcolors, int* size) +{ + unsigned int h; + unsigned int i, incr; + int colors; + INT32 pixel_mask; + int x, y; + ImagingColorItem* table; + ImagingColorItem* v; + + unsigned int code_size; + unsigned int code_poly; + unsigned int code_mask; + + /* note: the hash algorithm used here is based on the dictionary + code in Python 2.1.3; the exact implementation is borrowed from + Python's Unicode property database (written by yours truly) /F */ + + static int SIZES[] = { + 4,3, 8,3, 16,3, 32,5, 64,3, 128,3, 256,29, 512,17, 1024,9, 2048,5, + 4096,83, 8192,27, 16384,43, 32768,3, 65536,45, 131072,9, 262144,39, + 524288,39, 1048576,9, 2097152,5, 4194304,3, 8388608,33, 16777216,27, + 33554432,9, 67108864,71, 134217728,39, 268435456,9, 536870912,5, + 1073741824,83, 0 + }; + + code_size = code_poly = code_mask = 0; + + for (i = 0; SIZES[i]; i += 2) { + if (SIZES[i] > maxcolors) { + code_size = SIZES[i]; + code_poly = SIZES[i+1]; + code_mask = code_size - 1; + break; + } + } + + /* printf("code_size=%d\n", code_size); */ + /* printf("code_poly=%d\n", code_poly); */ + + if (!code_size) { + ImagingError_MemoryError(); /* just give up */ + return NULL; + } + + if (!im->image32) { + ImagingError_ModeError(); + return NULL; + } + + table = calloc(code_size + 1, sizeof(ImagingColorItem)); + if (!table) { + ImagingError_MemoryError(); + return NULL; + } + + pixel_mask = 0xffffffff; + if (im->bands == 3) + ((UINT8*) &pixel_mask)[3] = 0; + + colors = 0; + + for (y = 0; y < im->ysize; y++) { + INT32* p = im->image32[y]; + for (x = 0; x < im->xsize; x++) { + INT32 pixel = p[x] & pixel_mask; + h = (pixel); /* null hashing */ + i = (~h) & code_mask; + v = &table[i]; + if (!v->count) { + /* add to table */ + if (colors++ == maxcolors) + goto overflow; + v->x = x; v->y = y; + v->pixel = pixel; + v->count = 1; + continue; + } else if (v->pixel == pixel) { + v->count++; + continue; + } + incr = (h ^ (h >> 3)) & code_mask; + if (!incr) + incr = code_mask; + for (;;) { + i = (i + incr) & code_mask; + v = &table[i]; + if (!v->count) { + /* add to table */ + if (colors++ == maxcolors) + goto overflow; + v->x = x; v->y = y; + v->pixel = pixel; + v->count = 1; + break; + } else if (v->pixel == pixel) { + v->count++; + break; + } + incr = incr << 1; + if (incr > code_mask) + incr = incr ^ code_poly; + } + } + } + +overflow: + + /* pack the table */ + for (x = y = 0; x < (int) code_size; x++) + if (table[x].count) { + if (x != y) + table[y] = table[x]; + y++; + } + table[y].count = 0; /* mark end of table */ + + *size = colors; + + return table; +} |