C language version of binary image statistics connected areas

Connected region marking is the most basic image processing algorithm 1. In this algorithm, the whole image is scanned from left to right and from top to bottom, and the connected area is marked by comparing the neighborhood of each foreground pixel, and an equivalent tag list is created. Finally, merge the list of equivalent tags and scan the image again to update the tags. The advantage of the algorithm is easy to understand, the disadvantage is the need to scan the image twice, the efficiency is not high.

Using the idea of regional growth, 1 growth process can be used to mark 1 whole connected region. All connected regions can be marked by 1 scan of the image. Algorithm description is as follows:

Enter bitmap of the image to be labeled, and initialize a tag matrix labelmap, a queue queue and a tag count labelIndex of the same size as the input image; From left to right, from top to bottom of sequential scan bitmap, when scanning to 1 a was not marked p prospects of pixels, labelIndex add 1, and mark in the labelmap p (the value of the corresponding points assigned to labelIndex), at the same time, the scan p 8 neighborhood points, if there is not marked the prospect of pixels, is marked in labelmap, and into the queue, as the region growing seeds; When queue is not empty, take a growing seed point p1 from queue and scan the 8 neighborhood points of p1. If there are unmarked foreground pixels, mark them in labelmap and put them into queue. Repeat 3 until queue is empty, and 1 connected zone marker is completed; Go to 2, until the entire image is scanned, and get the number of the marker matrix labelmap and connected regions labelIndex.

In the worst case, the algorithm will conduct an 8-neighborhood search for each pixel once, with the algorithm complexity of O(n).

typedef struct QNode{
 int data;
 struct QNode *next;
}QNode;

typedef struct Queue{
 struct QNode* first;
 struct QNode* last;
}Queue;

void PushQueue(Queue *queue, int data){
 QNode *p = NULL;
 p = (QNode*)malloc(sizeof(QNode));
 p->data = data;
 if(queue->first == NULL){
  queue->first = p;
  queue->last = p;
  p->next = NULL;
 }
 else{
  p->next = NULL;
  queue->last->next = p;
  queue->last = p;
 }
}

int PopQueue(Queue *queue){
 QNode *p = NULL;
 int data;
 if(queue->first == NULL){
  return -1;
 }
 p = queue->first;
 data = p->data;
 if(queue->first->next == NULL){
  queue->first = NULL;
  queue->last = NULL;
 }
 else{
  queue->first = p->next;
 }
 free(p);
 return data;
}

static int NeighborDirection[8][2] = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};

void SearchNeighbor(unsigned char *bitmap, int width, int height, int *labelmap, 
     int labelIndex, int pixelIndex, Queue *queue){
 int searchIndex, i, length;
 labelmap[pixelIndex] = labelIndex;
 length = width * height;
 for(i = 0;i < 8;i++){
  searchIndex = pixelIndex + NeighborDirection[i][0] * width + NeighborDirection[i][1];
  if(searchIndex > 0 && searchIndex < length && 
   bitmap[searchIndex] == 255 && labelmap[searchIndex] == 0){
   labelmap[searchIndex] = labelIndex;
   PushQueue(queue, searchIndex);
  }
 }
}

int ConnectedComponentLabeling(unsigned char *bitmap, int width, int height, int *labelmap){
 int cx, cy, index, popIndex, labelIndex = 0;
 Queue *queue = NULL;
 queue = (Queue*)malloc(sizeof(Queue));
 queue->first = NULL;
  queue->last = NULL;
 memset(labelmap, 0, width * height);
 for(cy = 1; cy < height - 1; cy++){
  for(cx = 1; cx < width - 1; cx++){
   index = cy * width + cx;
   if(bitmap[index] == 255 && labelmap[index] == 0){
    labelIndex++;
    SearchNeighbor(bitmap, width, height, labelmap, labelIndex, index, queue);

    popIndex = PopQueue(queue);
    while(popIndex > -1){
    SearchNeighbor(bitmap, width, height, labelmap, labelIndex, popIndex, queue);
     popIndex = PopQueue(queue);
    }
   }
  }
 }
 free(queue);
 return labelIndex;
}