124
129
return PyInt_FromLong(val);
128
def maskFromSurface(surface, threshold = 127):
129
mask = pygame.Mask(surface.get_size())
130
key = surface.get_colorkey()
132
for y in range(surface.get_height()):
133
for x in range(surface.get_width()):
134
if surface.get_at((x+0.1,y+0.1)) != key:
137
for y in range(surface.get_height()):
138
for x in range (surface.get_width()):
139
if surface.get_at((x,y))[3] > threshold:
132
static PyObject* mask_overlap_mask(PyObject* self, PyObject* args)
135
bitmask_t *mask = PyMask_AsBitmap(self);
136
bitmask_t *output = bitmask_create(mask->w, mask->h);
137
bitmask_t *othermask;
139
PyMaskObject *maskobj2 = PyObject_New(PyMaskObject, &PyMask_Type);
141
if(!PyArg_ParseTuple(args, "O!(ii)", &PyMask_Type, &maskobj, &x, &y)) {
144
othermask = PyMask_AsBitmap(maskobj);
146
bitmask_overlap_mask(mask, othermask, output, x, y);
149
maskobj2->mask = output;
151
return (PyObject*)maskobj2;
154
static PyObject* mask_fill(PyObject* self, PyObject* args)
156
bitmask_t *mask = PyMask_AsBitmap(self);
163
static PyObject* mask_clear(PyObject* self, PyObject* args)
165
bitmask_t *mask = PyMask_AsBitmap(self);
172
static PyObject* mask_invert(PyObject* self, PyObject* args)
174
bitmask_t *mask = PyMask_AsBitmap(self);
176
bitmask_invert(mask);
181
static PyObject* mask_scale(PyObject* self, PyObject* args)
184
bitmask_t *input = PyMask_AsBitmap(self);
186
PyMaskObject *maskobj = PyObject_New(PyMaskObject, &PyMask_Type);
188
if(!PyArg_ParseTuple(args, "(ii)", &x, &y)) {
192
output = bitmask_scale(input, x, y);
195
maskobj->mask = output;
197
return (PyObject*)maskobj;
200
static PyObject* mask_draw(PyObject* self, PyObject* args)
202
bitmask_t *mask = PyMask_AsBitmap(self);
203
bitmask_t *othermask;
207
if(!PyArg_ParseTuple(args, "O!(ii)", &PyMask_Type, &maskobj, &x, &y)) {
210
othermask = PyMask_AsBitmap(maskobj);
212
bitmask_draw(mask, othermask, x, y);
217
static PyObject* mask_erase(PyObject* self, PyObject* args)
219
bitmask_t *mask = PyMask_AsBitmap(self);
220
bitmask_t *othermask;
224
if(!PyArg_ParseTuple(args, "O!(ii)", &PyMask_Type, &maskobj, &x, &y)) {
227
othermask = PyMask_AsBitmap(maskobj);
229
bitmask_erase(mask, othermask, x, y);
234
static PyObject* mask_count(PyObject* self, PyObject* args)
236
bitmask_t *m = PyMask_AsBitmap(self);
238
return PyInt_FromLong(bitmask_count(m));
241
static PyObject* mask_centroid(PyObject* self, PyObject* args)
243
bitmask_t *mask = PyMask_AsBitmap(self);
245
long int m10, m01, m00;
246
PyObject *xobj, *yobj;
250
for (x = 0; x < mask->w; x++) {
251
for (y = 0; y < mask->h; y++) {
252
if (bitmask_getbit(mask, x, y)) {
261
xobj = PyInt_FromLong(m10/m00);
262
yobj = PyInt_FromLong(m01/m00);
264
xobj = PyInt_FromLong(0);
265
yobj = PyInt_FromLong(0);
268
return Py_BuildValue("(NN)", xobj, yobj);
271
static PyObject* mask_angle(PyObject* self, PyObject* args)
273
bitmask_t *mask = PyMask_AsBitmap(self);
275
long int m10, m01, m00, m20, m02, m11;
278
m10 = m01 = m00 = m20 = m02 = m11 = 0;
280
for (x = 0; x < mask->w; x++) {
281
for (y = 0; y < mask->h; y++) {
282
if (bitmask_getbit(mask, x, y)) {
296
theta = -90.0*atan2(2*(m11/m00 - xc*yc),(m20/m00 - xc*xc)-(m02/m00 - yc*yc))/M_PI;
297
return PyFloat_FromDouble(theta);
299
return PyFloat_FromDouble(0);
303
static PyObject* mask_outline(PyObject* self, PyObject* args)
305
bitmask_t* c = PyMask_AsBitmap(self);
306
bitmask_t* m = bitmask_create(c->w + 2, c->h + 2);
307
PyObject *plist, *value;
308
int x, y, every, e, firstx, firsty, secx, secy, currx, curry, nextx, nexty, n;
310
a[0] = a[1] = a[7] = a[8] = a[9] = b[1] = b[2] = b[3] = b[9] = b[10] = b[11]= 1;
311
a[2] = a[6] = a[10] = b[4] = b[0] = b[12] = b[8] = 0;
312
a[3] = a[4] = a[5] = a[11] = a[12] = a[13] = b[5] = b[6] = b[7] = b[13] = -1;
315
plist = PyList_New (0);
320
n = firstx = firsty = secx = x = 0;
322
if(!PyArg_ParseTuple(args, "|i", &every)) {
326
/* by copying to a new, larger mask, we avoid having to check if we are at
327
a border pixel every time. */
328
bitmask_draw(m, c, 1, 1);
332
/* find the first set pixel in the mask */
333
for (y = 1; y < m->h-1; y++) {
334
for (x = 1; x < m->w-1; x++) {
335
if (bitmask_getbit(m, x, y)) {
338
value = Py_BuildValue("(ii)", x-1, y-1);
339
PyList_Append(plist, value);
344
if (bitmask_getbit(m, x, y))
350
/* covers the mask having zero pixels or only the final pixel */
351
if ((x == m->w-1) && (y == m->h-1)) {
356
/* check just the first pixel for neighbors */
357
for (n = 0;n < 8;n++) {
358
if (bitmask_getbit(m, x+a[n], y+b[n])) {
359
currx = secx = x+a[n];
360
curry = secy = y+b[n];
364
value = Py_BuildValue("(ii)", secx-1, secy-1);
365
PyList_Append(plist, value);
372
/* if there are no neighbors, return */
378
/* the outline tracing loop */
380
/* look around the pixel, it has to have a neighbor */
381
for (n = (n + 6) & 7;;n++) {
382
if (bitmask_getbit(m, currx+a[n], curry+b[n])) {
388
if ((curry == firsty && currx == firstx) && (secx == nextx && secy == nexty)) {
391
value = Py_BuildValue("(ii)", nextx-1, nexty-1);
392
PyList_Append(plist, value);
398
/* if we are back at the first pixel, and the next one will be the
399
second one we visited, we are done */
400
if ((curry == firsty && currx == firstx) && (secx == nextx && secy == nexty)) {
413
static PyObject* mask_convolve(PyObject* aobj, PyObject* args)
415
PyObject *bobj, *oobj = Py_None;
416
bitmask_t *a, *b, *o;
417
int xoffset = 0, yoffset = 0;
419
if (!PyArg_ParseTuple (args, "O!|O(ii)", &PyMask_Type, &bobj, &oobj, &xoffset, &yoffset))
422
a = PyMask_AsBitmap(aobj);
423
b = PyMask_AsBitmap(bobj);
425
if (oobj == Py_None) {
426
PyMaskObject *result = PyObject_New(PyMaskObject, &PyMask_Type);
428
result->mask = bitmask_create(a->w + b->w - 1, a->h + b->h - 1);
429
oobj = (PyObject*) result;
434
o = PyMask_AsBitmap(oobj);
436
bitmask_convolve(a, b, o, xoffset, yoffset);
147
440
static PyObject* mask_from_surface(PyObject* self, PyObject* args)
267
def get_bounding_boxes(surf):
270
width, height = surf.get_width(), surf.get_height()
274
# used pixels is Rects[y][x]
276
for y in xrange(height):
278
for x in xrange(width):
279
widthones.append(None)
280
used_pixels.append(widthones)
283
for y in xrange(height):
284
for x in xrange(width):
285
c = surf.get_at((x, y))
286
# if the pixel has been set.
288
if not used_pixels[y][x]:
289
used_pixels[y][x] = pygame.Rect(x,y,1,1)
290
regions.append( used_pixels[y][x] )
292
aregion = used_pixels[y][x]
294
# check other directions, clockwise. mark a pixel as used if it is.
295
for dx, dy in [(0,-1), (1,-1), (1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1)]:
298
if surf.get_at((ax,ay))[0]:
299
if not used_pixels[ay][ax]:
300
aregion.union_ip( pygame.Rect(ax,ay, 1, 1) )
301
used_pixels[ay][ax] = aregion
555
palette_colors - this only affects surfaces with a palette
556
if true we look at the colors from the palette,
557
otherwise we threshold the pixel values. This is useful if
558
the surface is actually greyscale colors, and not palette colors.
310
/* returns an array of regions in regions. */
312
static GAME_Rect* get_bounding_rects(bitmask_t *mask, int *num_bounding_boxes) {
314
int x, y, p, i, width, height;
315
GAME_Rect **used_pixels;
316
GAME_Rect *a_used_pixels;
317
GAME_Rect *direction_used_pixels;
320
GAME_Rect *aregion, *the_regions;
322
int nx, ny, nh, nw, ay, ax;
323
int directions[8][2];
326
/* for dx, dy in [(0,-1), (1,-1), (1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1)]:
329
directions[0][0] = 0; directions[0][1] = -1;
330
directions[1][0] = 1; directions[1][1] = -1;
331
directions[2][0] = 1; directions[2][1] = 0;
332
directions[3][0] = 1; directions[3][1] = 1;
333
directions[4][0] = 0; directions[4][1] = 1;
334
directions[5][0] = -1; directions[5][1] = 1;
335
directions[6][0] = -1; directions[6][1] = 0;
336
directions[7][0] = -1; directions[7][1] = -1;
346
/* used_pixels are pointers to rects held in the regions array. */
347
used_pixels = (GAME_Rect**) malloc(sizeof(GAME_Rect*) * height * width);
350
for(y=0; y < height; y++) {
351
for(x=0; x < width; x++) {
352
/* used_pixels[y][x] = (GAME_Rect*)NULL; */
353
*((GAME_Rect **) (used_pixels + y * width) + x) = NULL;
562
void bitmask_threshold (bitmask_t *m,
569
int x, y, rshift, gshift, bshift, rshift2, gshift2, bshift2;
570
int rloss, gloss, bloss, rloss2, gloss2, bloss2;
571
Uint8 *pixels, *pixels2;
572
SDL_PixelFormat *format, *format2;
573
Uint32 the_color, the_color2, rmask, gmask, bmask, rmask2, gmask2, bmask2;
576
Uint8 tr, tg, tb, ta;
580
pixels = (Uint8 *) surf->pixels;
581
format = surf->format;
582
rmask = format->Rmask;
583
gmask = format->Gmask;
584
bmask = format->Bmask;
585
rshift = format->Rshift;
586
gshift = format->Gshift;
587
bshift = format->Bshift;
588
rloss = format->Rloss;
589
gloss = format->Gloss;
590
bloss = format->Bloss;
591
bpp1 = surf->format->BytesPerPixel;
594
format2 = surf2->format;
595
rmask2 = format2->Rmask;
596
gmask2 = format2->Gmask;
597
bmask2 = format2->Bmask;
598
rshift2 = format2->Rshift;
599
gshift2 = format2->Gshift;
600
bshift2 = format2->Bshift;
601
rloss2 = format2->Rloss;
602
gloss2 = format2->Gloss;
603
bloss2 = format2->Bloss;
604
pixels2 = (Uint8 *) surf2->pixels;
605
bpp2 = surf->format->BytesPerPixel;
606
} else { /* make gcc stop complaining */
607
rmask2 = gmask2 = bmask2 = 0;
608
rshift2 = gshift2 = bshift2 = 0;
609
rloss2 = gloss2 = bloss2 = 0;
616
SDL_GetRGBA (color, format, &r, &g, &b, &a);
617
SDL_GetRGBA (threshold, format, &tr, &tg, &tb, &ta);
619
for(y=0; y < surf->h; y++) {
620
pixels = (Uint8 *) surf->pixels + y*surf->pitch;
622
pixels2 = (Uint8 *) surf2->pixels + y*surf2->pitch;
357
regions = (GAME_Rect*) malloc(sizeof(GAME_Rect) * height * width);
359
the_regions = regions;
361
for(y=0; y < height; y++) {
362
for(x=0; x < width; x++) {
363
p = bitmask_getbit(mask, x, y);
366
/* a_used_pixels is the pointer used_pixels[y][x]. */
367
a_used_pixels = *((GAME_Rect **) (used_pixels + y * width) + x);
370
if not used_pixels[y][x]:
371
used_pixels[y][x] = pygame.Rect(x,y,1,1)
372
regions.append( used_pixels[y][x] )
374
aregion = used_pixels[y][x]
624
for(x=0; x < surf->w; x++) {
625
/* the_color = surf->get_at(x,y) */
629
the_color = (Uint32)*((Uint8 *) pixels);
633
the_color = (Uint32)*((Uint16 *) pixels);
637
pix = ((Uint8 *) pixels);
639
#if SDL_BYTEORDER == SDL_LIL_ENDIAN
640
the_color = (pix[0]) + (pix[1] << 8) + (pix[2] << 16);
642
the_color = (pix[2]) + (pix[1] << 8) + (pix[0] << 16);
645
default: /* case 4: */
646
the_color = *((Uint32 *) pixels);
654
the_color2 = (Uint32)*((Uint8 *) pixels2);
658
the_color2 = (Uint32)*((Uint16 *) pixels2);
662
pix = ((Uint8 *) pixels2);
664
#if SDL_BYTEORDER == SDL_LIL_ENDIAN
665
the_color2 = (pix[0]) + (pix[1] << 8) + (pix[2] << 16);
667
the_color2 = (pix[2]) + (pix[1] << 8) + (pix[0] << 16);
670
default: /* case 4: */
671
the_color2 = *((Uint32 *) pixels2);
675
/* TODO: will need to handle surfaces with palette colors.
379
if( !a_used_pixels ) {
380
/* Add the pixels as a rect on the_regions */
381
the_regions[num_regions].x = x;
382
the_regions[num_regions].y = y;
383
the_regions[num_regions].w = 1;
384
the_regions[num_regions].h = 1;
385
a_used_pixels = the_regions + num_regions;
389
aregion = a_used_pixels;
391
/* check other directions, clockwise. mark a pixel as used if it is. */
393
for(i=0; i < 8; i++) {
395
ax = directions[i][0] + x;
396
ay = directions[i][1] + y;
398
/* if we are within the bounds of the mask, check it. */
400
if(ax >=0 && ax < width && ay < height && ay >= 0) {
403
/* printf("ax, ay: %d,%d\n", ax, ay);
406
if(bitmask_getbit(mask, ax, ay)) {
408
if not used_pixels[ay][ax]:
409
aregion.union_ip( pygame.Rect(ax,ay, 1, 1) )
411
direction_used_pixels = *((GAME_Rect **) (used_pixels + ay * width) + ax);
412
if (!direction_used_pixels) {
413
nx = MIN (aregion->x, ax);
414
ny = MIN (aregion->y, ay);
415
nw = MAX (aregion->x + aregion->w, ax + 1) - nx;
416
nh = MAX (aregion->y + aregion->h, ay + 1) - ny;
423
/* used_pixels[ay][ax] = aregion */
424
*((GAME_Rect **) (used_pixels + ay * width) + ax) = aregion;
437
*num_bounding_boxes = num_regions;
677
if((bpp2 == 1) && (bpp1 == 1) && (!palette_colors)) {
678
/* Don't look at the color of the surface, just use the
679
value. This is useful for 8bit images that aren't
680
actually using the palette.
682
if ( (abs( (the_color2) - (the_color)) < tr ) ) {
684
/* this pixel is within the threshold of othersurface. */
685
bitmask_setbit(m, x, y);
688
} else if ((abs((((the_color2 & rmask2) >> rshift2) << rloss2) - (((the_color & rmask) >> rshift) << rloss)) < tr) &
689
(abs((((the_color2 & gmask2) >> gshift2) << gloss2) - (((the_color & gmask) >> gshift) << gloss)) < tg) &
690
(abs((((the_color2 & bmask2) >> bshift2) << bloss2) - (((the_color & bmask) >> bshift) << bloss)) < tb)) {
691
/* this pixel is within the threshold of othersurface. */
692
bitmask_setbit(m, x, y);
695
/* TODO: will need to handle surfaces with palette colors.
696
TODO: will need to handle the case where palette_colors == 0
699
} else if ((abs((((the_color & rmask) >> rshift) << rloss) - r) < tr) &
700
(abs((((the_color & gmask) >> gshift) << gloss) - g) < tg) &
701
(abs((((the_color & bmask) >> bshift) << bloss) - b) < tb)) {
702
/* this pixel is within the threshold of the color. */
703
bitmask_setbit(m, x, y);
709
static PyObject* mask_from_threshold(PyObject* self, PyObject* args)
711
PyObject *surfobj, *surfobj2 = NULL;
712
PyMaskObject *maskobj;
714
SDL_Surface* surf = NULL, *surf2 = NULL;
716
PyObject *rgba_obj_color, *rgba_obj_threshold = NULL;
718
Uint8 rgba_threshold[4] = {0, 0, 0, 255};
720
Uint32 color_threshold;
721
int palette_colors = 1;
724
if (!PyArg_ParseTuple (args, "O!O|OO!i", &PySurface_Type, &surfobj,
725
&rgba_obj_color, &rgba_obj_threshold,
726
&PySurface_Type, &surfobj2, &palette_colors))
729
surf = PySurface_AsSurface (surfobj);
731
surf2 = PySurface_AsSurface (surfobj2);
734
if (PyInt_Check (rgba_obj_color)) {
735
color = (Uint32) PyInt_AsLong (rgba_obj_color);
736
} else if (PyLong_Check (rgba_obj_color)) {
737
color = (Uint32) PyLong_AsUnsignedLong (rgba_obj_color);
738
} else if (RGBAFromColorObj (rgba_obj_color, rgba_color)) {
739
color = SDL_MapRGBA (surf->format, rgba_color[0], rgba_color[1],
740
rgba_color[2], rgba_color[3]);
742
return RAISE (PyExc_TypeError, "invalid color argument");
745
if(rgba_obj_threshold) {
746
if (PyInt_Check (rgba_obj_threshold))
747
color_threshold = (Uint32) PyInt_AsLong (rgba_obj_threshold);
748
else if (PyLong_Check (rgba_obj_threshold))
749
color_threshold = (Uint32) PyLong_AsUnsignedLong
750
(rgba_obj_threshold);
751
else if (RGBAFromColorObj (rgba_obj_threshold, rgba_threshold))
752
color_threshold = SDL_MapRGBA (surf->format, rgba_threshold[0], rgba_threshold[1], rgba_threshold[2], rgba_threshold[3]);
754
return RAISE (PyExc_TypeError, "invalid threshold argument");
756
color_threshold = SDL_MapRGBA (surf->format, rgba_threshold[0], rgba_threshold[1], rgba_threshold[2], rgba_threshold[3]);
759
bpp = surf->format->BytesPerPixel;
760
m = bitmask_create(surf->w, surf->h);
762
PySurface_Lock(surfobj);
764
PySurface_Lock(surfobj2);
767
Py_BEGIN_ALLOW_THREADS;
768
bitmask_threshold (m, surf, surf2, color, color_threshold, palette_colors);
769
Py_END_ALLOW_THREADS;
771
PySurface_Unlock(surfobj);
773
PySurface_Unlock(surfobj2);
776
maskobj = PyObject_New(PyMaskObject, &PyMask_Type);
780
return (PyObject*)maskobj;
786
/* the initial labelling phase of the connected components algorithm
788
Returns: The highest label in the labelled image
790
input - The input Mask
791
image - An array to store labelled pixels
792
ufind - The union-find label equivalence array
793
largest - An array to store the number of pixels for each label
796
unsigned int cc_label(bitmask_t *input, unsigned int* image, unsigned int* ufind, unsigned int* largest) {
798
unsigned int x, y, w, h, root, aroot, croot, temp, label;
807
/* special case for first pixel */
808
if(bitmask_getbit(input, 0, 0)) { /* process for a new connected comp: */
809
label++; /* create a new label */
810
*buf = label; /* give the pixel the label */
811
ufind[label] = label; /* put the label in the equivalence array */
812
largest[label] = 1; /* the label has 1 pixel associated with it */
820
/* special case for first row.
821
Go over the first row except the first pixel.
823
for(x = 1; x < w; x++) {
824
if (bitmask_getbit(input, x, 0)) {
825
if (*(buf-1)) { /* d label */
827
} else { /* create label */
830
ufind[label] = label;
842
/* the rest of the image */
843
for(y = 1; y < h; y++) {
844
/* first pixel of the row */
845
if (bitmask_getbit(input, 0, y)) {
846
if (*(buf-w)) { /* b label */
848
} else if (*(buf-w+1)) { /* c label */
850
} else { /* create label */
853
ufind[label] = label;
861
/* middle pixels of the row */
862
for(x = 1; x < (w-1); x++) {
863
if (bitmask_getbit(input, x, y)) {
864
if (*(buf-w)) { /* b label */
866
} else if (*(buf-w+1)) { /* c branch of tree */
867
if (*(buf-w-1)) { /* union(c, a) */
868
croot = root = *(buf-w+1);
869
while (ufind[root] < root) { /* find root */
872
if (croot != *(buf-w-1)) {
873
temp = aroot = *(buf-w-1);
874
while (ufind[aroot] < aroot) { /* find root */
875
aroot = ufind[aroot];
880
while (ufind[temp] > root) { /* set root */
886
while (ufind[croot] > root) { /* set root */
892
} else if (*(buf-1)) { /* union(c, d) */
893
croot = root = *(buf-w+1);
894
while (ufind[root] < root) { /* find root */
897
if (croot != *(buf-1)) {
898
temp = aroot = *(buf-1);
899
while (ufind[aroot] < aroot) { /* find root */
900
aroot = ufind[aroot];
905
while (ufind[temp] > root) { /* set root */
911
while (ufind[croot] > root) { /* set root */
917
} else { /* c label */
920
} else if (*(buf-w-1)) { /* a label */
922
} else if (*(buf-1)) { /* d label */
924
} else { /* create label */
927
ufind[label] = label;
936
/* last pixel of the row, if its not also the first pixel of the row */
938
if (bitmask_getbit(input, x, y)) {
939
if (*(buf-w)) { /* b label */
941
} else if (*(buf-w-1)) { /* a label */
943
} else if (*(buf-1)) { /* d label */
945
} else { /* create label */
948
ufind[label] = label;
964
/* Connected component labeling based on the SAUF algorithm by Kesheng Wu,
965
Ekow Otoo, and Kenji Suzuki. The algorithm is best explained by their paper,
966
"Two Strategies to Speed up Connected Component Labeling Algorithms", but in
967
summary, it is a very efficient two pass method for 8-connected components.
968
It uses a decision tree to minimize the number of neighbors that need to be
969
checked. It stores equivalence information in an array based union-find.
970
This implementation also has a final step of finding bounding boxes. */
973
returns -2 on memory allocation error, otherwise 0 on success.
975
input - the input mask.
976
num_bounding_boxes - returns the number of bounding rects found.
977
rects - returns the rects that are found. Allocates the memory for the rects.
980
static int get_bounding_rects(bitmask_t *input, int *num_bounding_boxes, GAME_Rect** ret_rects)
982
unsigned int *image, *ufind, *largest, *buf;
983
int x, y, w, h, temp, label, relabel;
992
/* a temporary image to assign labels to each bit of the mask */
993
image = (unsigned int *) malloc(sizeof(int)*w*h);
994
if(!image) { return -2; }
996
/* allocate enough space for the maximum possible connected components */
997
/* the union-find array. see wikipedia for info on union find */
998
ufind = (unsigned int *) malloc(sizeof(int)*(w/2 + 1)*(h/2 + 1));
999
if(!ufind) { return -2; }
1001
largest = (unsigned int *) malloc(sizeof(int)*(w/2 + 1)*(h/2 + 1));
1002
if(!largest) { return -2; }
1005
/* do the initial labelling */
1006
label = cc_label(input, image, ufind, largest);
1009
/* flatten and relabel the union-find equivalence array. Start at label 1
1010
because label 0 indicates an unset pixel. For this reason, we also use
1011
<= label rather than < label. */
1012
for (x = 1; x <= label; x++) {
1013
if (ufind[x] < x) { /* is it a union find root? */
1014
ufind[x] = ufind[ufind[x]]; /* relabel it to its root */
1015
} else { /* its a root */
1017
ufind[x] = relabel; /* assign the lowest label available */
1021
*num_bounding_boxes = relabel;
1024
/* early out, as we didn't find anything. */
1032
/* the bounding rects, need enough space for the number of labels */
1033
rects = (GAME_Rect *) malloc(sizeof(GAME_Rect) * (relabel +1));
1034
if(!rects) { return -2; }
1036
for (temp = 0; temp <= relabel; temp++) {
1037
rects[temp].h = 0; /* so we know if its a new rect or not */
1040
/* find the bounding rect of each connected component */
1042
for (y = 0; y < h; y++) {
1043
for (x = 0; x < w; x++) {
1044
if (ufind[*buf]) { /* if the pixel is part of a component */
1045
if (rects[ufind[*buf]].h) { /* the component has a rect */
1046
temp = rects[ufind[*buf]].x;
1047
rects[ufind[*buf]].x = MIN(x, temp);
1048
rects[ufind[*buf]].y = MIN(y, rects[ufind[*buf]].y);
1049
rects[ufind[*buf]].w = MAX(rects[ufind[*buf]].w + temp, x + 1) - rects[ufind[*buf]].x;
1050
rects[ufind[*buf]].h = MAX(rects[ufind[*buf]].h, y - rects[ufind[*buf]].y + 1);
1051
} else { /* otherwise, start the rect */
1052
rects[ufind[*buf]].x = x;
1053
rects[ufind[*buf]].y = y;
1054
rects[ufind[*buf]].w = 1;
1055
rects[ufind[*buf]].h = 1;
447
1070
static PyObject* mask_get_bounding_rects(PyObject* self, PyObject* args)
449
1072
GAME_Rect *regions;
450
1073
GAME_Rect *aregion;
451
int num_bounding_boxes, i;
1074
int num_bounding_boxes, i, r;
458
1079
bitmask_t *mask = PyMask_AsBitmap(self);
462
1085
num_bounding_boxes = 0;
465
if(!PyArg_ParseTuple(args, ""))
1087
Py_BEGIN_ALLOW_THREADS;
1089
r = get_bounding_rects(mask, &num_bounding_boxes, ®ions);
1091
Py_END_ALLOW_THREADS;
1095
/* memory out failure */
1096
return RAISE (PyExc_MemoryError, "Not enough memory to get bounding rects. \n");
468
1099
ret = PyList_New (0);
473
Py_BEGIN_ALLOW_THREADS;
475
regions = get_bounding_rects(mask, &num_bounding_boxes);
477
Py_END_ALLOW_THREADS;
480
/* printf("num_bounding_boxes:%d\n", num_bounding_boxes); */
483
/* build a list of rects to return. */
484
for(i=0; i < num_bounding_boxes; i++) {
1103
/* build a list of rects to return. Starts at 1 because we never use 0. */
1104
for(i=1; i <= num_bounding_boxes; i++) {
485
1105
aregion = regions + i;
486
/* printf("aregion x,y,w,h:%d,%d,%d,%d\n", aregion->x, aregion->y, aregion->w, aregion->h);
489
1106
rect = PyRect_New4 ( aregion->x, aregion->y, aregion->w, aregion->h );
490
1107
PyList_Append (ret, rect);
491
1108
Py_DECREF (rect);
503
static PyMethodDef maskobj_builtins[] =
1118
returns the number of connected components.
1119
returns -2 on memory allocation error.
1120
Allocates memory for components.
1123
static int get_connected_components(bitmask_t *mask, bitmask_t ***components, int min)
1125
unsigned int *image, *ufind, *largest, *buf;
1126
int x, y, w, h, label, relabel;
1134
/* a temporary image to assign labels to each bit of the mask */
1135
image = (unsigned int *) malloc(sizeof(int)*w*h);
1136
if(!image) { return -2; }
1138
/* allocate enough space for the maximum possible connected components */
1139
/* the union-find array. see wikipedia for info on union find */
1140
ufind = (unsigned int *) malloc(sizeof(int)*(w/2 + 1)*(h/2 + 1));
1146
largest = (unsigned int *) malloc(sizeof(int)*(w/2 + 1)*(h/2 + 1));
1153
/* do the initial labelling */
1154
label = cc_label(mask, image, ufind, largest);
1156
for (x = 1; x <= label; x++) {
1158
largest[ufind[x]] += largest[x];
1163
/* flatten and relabel the union-find equivalence array. Start at label 1
1164
because label 0 indicates an unset pixel. For this reason, we also use
1165
<= label rather than < label. */
1166
for (x = 1; x <= label; x++) {
1167
if (ufind[x] < x) { /* is it a union find root? */
1168
ufind[x] = ufind[ufind[x]]; /* relabel it to its root */
1169
} else { /* its a root */
1170
if (largest[x] >= min) {
1172
ufind[x] = relabel; /* assign the lowest label available */
1180
/* early out, as we didn't find anything. */
1187
/* allocate space for the mask array */
1188
comps = (bitmask_t **) malloc(sizeof(bitmask_t *) * (relabel +1));
1196
/* create the empty masks */
1197
for (x = 1; x <= relabel; x++) {
1198
comps[x] = bitmask_create(w, h);
1201
/* set the bits in each mask */
1203
for (y = 0; y < h; y++) {
1204
for (x = 0; x < w; x++) {
1205
if (ufind[*buf]) { /* if the pixel is part of a component */
1206
bitmask_setbit(comps[ufind[*buf]], x, y);
1216
*components = comps;
1221
static PyObject* mask_connected_components(PyObject* self, PyObject* args)
1224
PyMaskObject *maskobj;
1225
bitmask_t **components;
1226
bitmask_t *mask = PyMask_AsBitmap(self);
1227
int i, num_components, min;
1232
if(!PyArg_ParseTuple(args, "|i", &min)) {
1236
Py_BEGIN_ALLOW_THREADS;
1237
num_components = get_connected_components(mask, &components, min);
1238
Py_END_ALLOW_THREADS;
1240
if (num_components == -2)
1241
return RAISE (PyExc_MemoryError, "Not enough memory to get components. \n");
1243
ret = PyList_New(0);
1247
for (i=1; i <= num_components; i++) {
1248
maskobj = PyObject_New(PyMaskObject, &PyMask_Type);
1250
maskobj->mask = components[i];
1251
PyList_Append (ret, (PyObject *) maskobj);
1252
Py_DECREF((PyObject *) maskobj);
1260
/* Connected component labeling based on the SAUF algorithm by Kesheng Wu,
1261
Ekow Otoo, and Kenji Suzuki. The algorithm is best explained by their paper,
1262
"Two Strategies to Speed up Connected Component Labeling Algorithms", but in
1263
summary, it is a very efficient two pass method for 8-connected components.
1264
It uses a decision tree to minimize the number of neighbors that need to be
1265
checked. It stores equivalence information in an array based union-find.
1266
This implementation also tracks the number of pixels in each label, finding
1267
the biggest one while flattening the union-find equivalence array. It then
1268
writes an output mask containing only the largest connected component. */
1272
returns -2 on memory allocation error.
1274
static int largest_connected_comp(bitmask_t* input, bitmask_t* output, int ccx, int ccy)
1276
unsigned int *image, *ufind, *largest, *buf;
1277
unsigned int max, x, y, w, h, label;
1282
/* a temporary image to assign labels to each bit of the mask */
1283
image = (unsigned int *) malloc(sizeof(int)*w*h);
1284
if(!image) { return -2; }
1285
/* allocate enough space for the maximum possible connected components */
1286
/* the union-find array. see wikipedia for info on union find */
1287
ufind = (unsigned int *) malloc(sizeof(int)*(w/2 + 1)*(h/2 + 1));
1292
/* an array to track the number of pixels associated with each label */
1293
largest = (unsigned int *) malloc(sizeof(int)*(w/2 + 1)*(h/2 + 1));
1300
/* do the initial labelling */
1301
label = cc_label(input, image, ufind, largest);
1304
/* flatten the union-find equivalence array */
1305
for (x = 2; x <= label; x++) {
1306
if (ufind[x] != x) { /* is it a union find root? */
1307
largest[ufind[x]] += largest[x]; /* add its pixels to its root */
1308
ufind[x] = ufind[ufind[x]]; /* relabel it to its root */
1310
if (largest[ufind[x]] > largest[max]) { /* is it the new biggest? */
1315
/* write out the final image */
1318
max = ufind[*(buf+ccy*w+ccx)];
1319
for (y = 0; y < h; y++) {
1320
for (x = 0; x < w; x++) {
1321
if (ufind[*buf] == max) { /* if the label is the max one */
1322
bitmask_setbit(output, x, y); /* set the bit in the mask */
1335
static PyObject* mask_connected_component(PyObject* self, PyObject* args)
1337
bitmask_t *input = PyMask_AsBitmap(self);
1338
bitmask_t *output = bitmask_create(input->w, input->h);
1339
PyMaskObject *maskobj = PyObject_New(PyMaskObject, &PyMask_Type);
1344
if(!PyArg_ParseTuple(args, "|(ii)", &x, &y)) {
1348
/* if a coordinate is specified, make the pixel there is actually set */
1349
if (x == -1 || bitmask_getbit(input, x, y)) {
1350
if (largest_connected_comp(input, output, x, y) == -2) {
1351
return RAISE (PyExc_MemoryError, "Not enough memory to get bounding rects. \n");
1356
maskobj->mask = output;
1358
return (PyObject*)maskobj;
1362
static PyMethodDef mask_methods[] =
505
1364
{ "get_size", mask_get_size, METH_VARARGS, DOC_MASKGETSIZE},
506
1365
{ "get_at", mask_get_at, METH_VARARGS, DOC_MASKGETAT },
507
1366
{ "set_at", mask_set_at, METH_VARARGS, DOC_MASKSETAT },
508
1367
{ "overlap", mask_overlap, METH_VARARGS, DOC_MASKOVERLAP },
509
{ "overlap_area", mask_overlap_area, METH_VARARGS,
510
DOC_MASKOVERLAPAREA },
511
{ "get_bounding_rects", mask_get_bounding_rects, METH_VARARGS,
1368
{ "overlap_area", mask_overlap_area, METH_VARARGS, DOC_MASKOVERLAPAREA },
1369
{ "overlap_mask", mask_overlap_mask, METH_VARARGS, DOC_MASKOVERLAPMASK },
1370
{ "fill", mask_fill, METH_NOARGS, DOC_MASKFILL },
1371
{ "clear", mask_clear, METH_NOARGS, DOC_MASKCLEAR },
1372
{ "invert", mask_invert, METH_NOARGS, DOC_MASKINVERT },
1373
{ "scale", mask_scale, METH_VARARGS, DOC_MASKSCALE },
1374
{ "draw", mask_draw, METH_VARARGS, DOC_MASKDRAW },
1375
{ "erase", mask_erase, METH_VARARGS, DOC_MASKERASE },
1376
{ "count", mask_count, METH_NOARGS, DOC_MASKCOUNT },
1377
{ "centroid", mask_centroid, METH_NOARGS, DOC_MASKCENTROID },
1378
{ "angle", mask_angle, METH_NOARGS, DOC_MASKANGLE },
1379
{ "outline", mask_outline, METH_VARARGS, DOC_MASKOUTLINE },
1380
{ "convolve", mask_convolve, METH_VARARGS, DOC_MASKCONVOLVE },
1381
{ "connected_component", mask_connected_component, METH_VARARGS,
1382
DOC_MASKCONNECTEDCOMPONENT },
1383
{ "connected_components", mask_connected_components, METH_VARARGS,
1384
DOC_MASKCONNECTEDCOMPONENTS },
1385
{ "get_bounding_rects", mask_get_bounding_rects, METH_NOARGS,
512
1386
DOC_MASKGETBOUNDINGRECTS },
514
1388
{ NULL, NULL, 0, NULL }
added
removed
src/mask.c
