/* Connected component labeling based on the SAUF algorithm by Kesheng Wu, Ekow Otoo, and Kenji Suzuki. The algorithm is best explained by their paper, "Two Strategies to Speed up Connected Component Labeling Algorithms", but in summary, it is a very efficient two pass method for 8-connected components. It uses a decision tree to minimize the number of neighbors that need to be checked. It stores equivalence information in an array based union-find. This implementation also has a final step of finding bounding boxes. */ static GAME_Rect* get_bounding_rects(bitmask_t *input, int *num_bounding_boxes) { unsigned int *image, *ufind, *buf; unsigned int x, y, w, h, root, aroot, croot, temp, label, relabel; GAME_Rect* rects; label = 0; w = input->w; h = input->h; /* a temporary image to assign labels to each bit of the mask */ image = (unsigned int *) malloc(sizeof(int)*w*h); /* allocate enough space for the maximum possible connected components */ /* the union-find array. see wikipedia for info on union find */ ufind = (unsigned int *) malloc(sizeof(int)*(w/2 + 1)*(h/2 + 1)); ufind[0] = 0; buf = image; /* special case for first pixel */ if(bitmask_getbit(input, 0, 0)) { /* process for a new connected comp: */ label++; /* create a new label */ *buf = label; /* give the pixel the label */ ufind[label] = label; /* put the label in the equivalence array */ } else { *buf = 0; } buf++; /* special case for first row */ for(x = 1; x < w; x++) { if (bitmask_getbit(input, x, 0)) { if (*(buf-1)) { /* d label */ *buf = *(buf-1); } else { /* create label */ label++; *buf = label; ufind[label] = label; } } else { *buf = 0; } buf++; } /* the rest of the image */ for(y = 1; y < h; y++) { /* first pixel of the row */ if (bitmask_getbit(input, 0, y)) { if (*(buf-w)) { /* b label */ *buf = *(buf-w); } else if (*(buf-w+1)) { /* c label */ *buf = *(buf-w+1); } else { /* create label */ label++; *buf = label; ufind[label] = label; } } else { *buf = 0; } buf++; /* middle pixels of the row */ for(x = 1; x < (w-1); x++) { if (bitmask_getbit(input, x, y)) { if (*(buf-w)) { /* b label */ *buf = *(buf-w); } else if (*(buf-w+1)) { /* c branch of tree */ if (*(buf-w-1)) { /* union(c, a) */ croot = root = *(buf-w+1); while (ufind[root] < root) { /* find root */ root = ufind[root]; } if (croot != *(buf-w-1)) { temp = aroot = *(buf-w-1); while (ufind[aroot] < aroot) { /* find root */ aroot = ufind[aroot]; } if (root > aroot) { root = aroot; } while (ufind[temp] > root) { /* set root */ aroot = ufind[temp]; ufind[temp] = root; temp = aroot; } } while (ufind[croot] > root) { /* set root */ temp = ufind[croot]; ufind[croot] = root; croot = temp; } *buf = root; } else if (*(buf-1)) { /* union(c, d) */ croot = root = *(buf-w+1); while (ufind[root] < root) { /* find root */ root = ufind[root]; } if (croot != *(buf-1)) { temp = aroot = *(buf-1); while (ufind[aroot] < aroot) { /* find root */ aroot = ufind[aroot]; } if (root > aroot) { root = aroot; } while (ufind[temp] > root) { /* set root */ aroot = ufind[temp]; ufind[temp] = root; temp = aroot; } } while (ufind[croot] > root) { /* set root */ temp = ufind[croot]; ufind[croot] = root; croot = temp; } *buf = root; } else { /* c label */ *buf = *(buf-w+1); } } else if (*(buf-w-1)) { /* a label */ *buf = *(buf-w-1); } else if (*(buf-1)) { /* d label */ *buf = *(buf-1); } else { /* create label */ label++; *buf = label; ufind[label] = label; } } else { *buf = 0; } buf++; } /* last pixel of the row, if its not also the first pixel of the row */ if (w > 1) { if (bitmask_getbit(input, x, y)) { if (*(buf-w)) { /* b label */ *buf = *(buf-w); } else if (*(buf-w-1)) { /* a label */ *buf = *(buf-w-1); } else if (*(buf-1)) { /* d label */ *buf = *(buf-1); } else { /* create label */ label++; *buf = label; ufind[label] = label; } } else { *buf = 0; } buf++; } } relabel = 0; /* flatten and relabel the union-find equivalence array */ for (x = 1; x <= label; x++) { if (ufind[x] < x) { /* is it a union find root? */ ufind[x] = ufind[ufind[x]]; /* relabel it to its root */ } else { /* its a root */ relabel++; ufind[x] = relabel; /* assign the lowest label available */ } } *num_bounding_boxes = relabel; /* the bounding rects, need enough space for the number of labels */ rects = (GAME_Rect *) malloc(sizeof(GAME_Rect) * (relabel + 1)); for (temp = 0; temp <= relabel; temp++) { rects[temp].w = 0; /* so we know if its a new rect or not */ } /* find the bounding rect of each connected component */ buf = image; for (y = 0; y < h; y++) { for (x = 0; x < w; x++) { if (ufind[*buf]) { /* if the pixel is part of a component */ if (rects[ufind[*buf]].w) { /* the component has a rect */ rects[ufind[*buf]].x = MIN(x, rects[ufind[*buf]].x); rects[ufind[*buf]].y = MIN(y, rects[ufind[*buf]].y); rects[ufind[*buf]].w = MAX(rects[ufind[*buf]].w, x - rects[ufind[*buf]].x + 1); rects[ufind[*buf]].h = MAX(rects[ufind[*buf]].h, y - rects[ufind[*buf]].y + 1); } else { /* otherwise, start the rect */ rects[ufind[*buf]].x = x; rects[ufind[*buf]].y = y; rects[ufind[*buf]].w = 1; rects[ufind[*buf]].h = 1; } } buf++; } } free(image); free(ufind); return rects; } static PyObject* mask_get_bounding_rects(PyObject* self, PyObject* args) { GAME_Rect *regions; GAME_Rect *aregion; int num_bounding_boxes, i; PyObject* ret; PyObject* rect; bitmask_t *mask = PyMask_AsBitmap(self); ret = NULL; num_bounding_boxes = 0; ret = PyList_New (0); if (!ret) return NULL; Py_BEGIN_ALLOW_THREADS; regions = get_bounding_rects(mask, &num_bounding_boxes); Py_END_ALLOW_THREADS; /* build a list of rects to return. */ for(i=1; i <= num_bounding_boxes; i++) { aregion = regions + i; rect = PyRect_New4 ( aregion->x, aregion->y, aregion->w, aregion->h ); PyList_Append (ret, rect); Py_DECREF (rect); } free(regions); return ret; }