Two-pass algorithm for binary image

Two-pass algorithm for binary image is one of the applications of union-find data structure. The idea of the algorithm is described in this lecture note (page 10/24)


Here is a simple implementation of the two-pass algorithm on binary image. The algorithm will add a label to each connected component in the image. The connectivity is tested based on the definition of 4-connectivity.

Sample input:

0 1 0 0 0 0 1
1 1 0 1 0 1 1
0 0 0 1 1 0 0

Sample output:

0 1 0 0 0 0 2
1 1 0 3 0 2 2
0 0 0 3 3 0 0



[twopass.h]

#ifndef TWOPASS_H_
#define TWOPASS_H_


#include <vector>
#include "UnionFind.h"

typedef vector< vector<int> > matrix;
matrix twoPassAlgorithm(const matrix & inMatrix);

#endif /* TWOPASS_H_ */

[twopass.cpp]

/*
 * twopass.cpp
 *
 *  Created on: Feb 17, 2016
 *      Author: ruikun
 */

#include "twopass.h"

matrix twoPassAlgorithm(const matrix & inMatrix)
{
 int nrow = inMatrix.size();
 int ncol = inMatrix[0].size();

 matrix label(nrow, vector<int>(ncol, -1)); // -1 indicates that there is no label in the cell


 UnionFind uf;
 // first pass
 int label_up;
 int label_left;

 for (int i = 0; i < nrow; ++i) {
  for (int j = 0; j < ncol; ++j) {

   if (inMatrix[i][j] == 1) {
    // boundary case: we can put boundary case outside the loop
    if (i == 0 && j == 0) {
     uf.add();
     label[0][0] = uf.getLatestLabel();
     continue;
    }

    if (i == 0) {
     if (label[0][j-1] != -1) {
      label[0][j] = label[0][j-1];
     } else {
      uf.add();
      label[0][j] = uf.getLatestLabel();
     }
     continue;
    }

    if (j == 0) {
     if (label[i-1][0] != -1) {
      label[i][0] = label[i-1][0];
     } else {
      uf.add();
      label[i][0] = uf.getLatestLabel();
     }
     continue;
    }

    // normal case

    // if only one of upper and left cell has label, then copy the label
    label_up = label[i-1][j];
    label_left = label[i][j-1];

    if (label_up != -1 && label_left == -1) {
     label[i][j] = label_up;
    } else if (label_up == -1 && label_left != -1) {
     label[i][j] = label_left;
    } else if (label_up != -1 && label_left != 1 && label_up == label_left) {
     label[i][j] = label_up;
    } else if (label_up != label_left) {
     label[i][j] = label_up;
     uf.unionNode(label_up, label_left);
    } else {  // in this case, neither of upper cell nor left cell has a label
     uf.add();
     label[i][j] = uf.getLatestLabel(); // get new label

    }
   }
  }
 }

 // re-labeling
 vector<int> classNumber(uf.getLabels());

 int _label;
 for (int i = 0; i < nrow; ++i) {
  for (int j = 0; j < ncol; ++j){

   _label = label[i][j];
   label[i][j] = (_label == -1 ? -1 : classNumber[label[i][j]]) + 1;
  }
 }


 return label;
}