SparseConnectedComponents - Efficient Algorithm for Finding the Connected Components of Binary OpenCV Mat and Compute Their Center of Mass

SparseConnectedComponents.cpp

// Written by Nadav Benedek 2017


#include "SparseConnectedComponents.h"
#include <iostream>  
#include "opencv2/opencv.hpp"

SparseConnectedComponents::SparseConnectedComponents() {
}

SparseConnectedComponents::~SparseConnectedComponents() {
}

void SparseConnectedComponents::Reset() {
	hashGraphUnionFind.clear();
}

node* SparseConnectedComponents::MakeSet(int x, int y) {
	node n; 

	n.rank      = 0;
	n.totalX    = x;
	n.totalY    = y;
	n.numPixels = 1;		

	hashGraphUnionFind.emplace(x * MAX_COL + y, n);

	node * nodePointer = &hashGraphUnionFind[x*MAX_COL + y];

	nodePointer->parentNode = nodePointer;

	return nodePointer; // Must return a pointer to the memory inside the hash, not to our local stack
}

node* SparseConnectedComponents::Find(node* a) {         // with path compression
	if (a->parentNode == a) return a;
	else {
		a->parentNode = Find(a->parentNode);
		return a->parentNode;
	}
}


node* SparseConnectedComponents::getNode(int x, int y) {         // with path compression
	
	
	if (hashGraphUnionFind.find(x*MAX_COL+y) != hashGraphUnionFind.end()) { // if key is found 
		return &hashGraphUnionFind[x*MAX_COL + y];
	} else {
		return 0;
	}
}



void SparseConnectedComponents::Union(node* a0, node* a1) {      // union by rank
	if (a0 == a1) return;

	node *a2 = Find(a0);
	node *a3 = Find(a1);

	if (a2 == a3) return;

	if (a2->rank < a3->rank) {
		a2->parentNode = a3;
		a3->numPixels += a2->numPixels;
		a3->totalX += a2->totalX;
		a3->totalY += a2->totalY;
	} else if (a3->rank < a2->rank) {
		a3->parentNode = a2;
		a2->numPixels += a3->numPixels;
		a2->totalX += a3->totalX;
		a2->totalY += a3->totalY;
	} else {
		a2->parentNode = a3;
		a3->rank++;
		a3->numPixels += a2->numPixels;
		a3->totalX += a2->totalX;
		a3->totalY += a2->totalY;
	}
}


void SparseConnectedComponents::processListOf2DPoints(std::vector<cv::Point>  & listOfPointsToProcess) {
	for (cv::Point & point : listOfPointsToProcess) {
		node * n = MakeSet(point.x, point.y);
		
		if (hashGraphUnionFind.find((point.x - 1) *MAX_COL + point.y) != hashGraphUnionFind.end()) { // if key is found on left
			Union(&hashGraphUnionFind[(point.x - 1) *MAX_COL + point.y], n);
		}

		if (hashGraphUnionFind.find((point.x - 1) *MAX_COL + (point.y-1)) != hashGraphUnionFind.end()) { // if key is found on up-left
			Union(&hashGraphUnionFind[(point.x - 1) * MAX_COL + (point.y-1)], n);
		}

		if (hashGraphUnionFind.find((point.x) * MAX_COL + (point.y - 1)) != hashGraphUnionFind.end()) { // if key is found on top
			Union(&hashGraphUnionFind[(point.x) * MAX_COL + (point.y - 1)], n);
		}

		if (hashGraphUnionFind.find((point.x + 1) * MAX_COL + (point.y - 1)) != hashGraphUnionFind.end()) { // if key is found on top-right
			Union(&hashGraphUnionFind[(point.x + 1) * MAX_COL + (point.y - 1)], n);
		}
	}
}

void testSparseConnectedComponents() {
	SparseConnectedComponents  scc;
	node * n1 = scc.MakeSet(100, 100);

	std::cout << n1->totalX << "  " << n1->isRoot() << std::endl;

	node * n2 = scc.MakeSet(200, 200);
	
	std::cout << "Test: " << scc.getNode(200,200)->totalX << std::endl;

	std::cout << n2->totalX << "  " << n2->isRoot() << std::endl;
	scc.Union(n1, n2);
	std::cout << "n1: " << n1->isRoot() << " totalx: " << n1->totalX << " centerX: " << n1->getCenterX() <<  std::endl;
	std::cout << "n2: " << n2->isRoot() << " totalx: " << n2->totalX << " centerX: " << n2->getCenterX() << std::endl;

	node * n3 = scc.MakeSet(300, 300);

	std::cout << n3->totalX << "  " << n3->isRoot() << std::endl;
	scc.Union(n1, n3);

	std::cout << "n1: " << n1->isRoot() << " totalx: " << n1->totalX << " centerX: " << n1->getCenterX() << std::endl;
	std::cout << "n2: " << n2->isRoot() << " totalx: " << n2->totalX << " centerX: " << n2->getCenterX() << std::endl;
	std::cout << "n3: " << n3->isRoot()  << " totalx: " << n3->totalX << " centerX: " << n3->getCenterX() << std::endl;

	std::cout << "iterate" << std::endl;

	for (std::pair<const int, node> & pair : scc.hashGraphUnionFind) {
		
		int x = pair.first / scc.MAX_COL;
		int y = pair.first % scc.MAX_COL;

		std::cout << "key: " << x << "," << y << " value: " << pair.second.getCenterX() << "," << pair.second.getCenterY() << std::endl;
	}
}

SparseConnectedComponents.h

// Written by Nadav Benedek 2017

#pragma once
#include <unordered_map>
#include "opencv2/opencv.hpp"

struct node {
	node * parentNode;
	int rank;
	int totalX, totalY, numPixels;

	bool isRoot() {
		if (this->parentNode == this) {
			return true;
		} else {
			return false;
		}
	}

	float getCenterX() {
		return (float)totalX / numPixels;
	}
	float getCenterY() {
		return (float)totalY / numPixels;
	}
};

class SparseConnectedComponents {

public:
	const int MAX_COL = 10000;
	std::unordered_map<int, node> hashGraphUnionFind; // int -> node, where int is x*MAX_COL + Y;

	SparseConnectedComponents();
	~SparseConnectedComponents();

	node* MakeSet(int x, int y);
	node* Find(node* a);
	node* getNode(int x, int y);
	void Union(node* a0, node* a1);

	bool isRoot(node* a);

	void Reset();

	void processListOf2DPoints(std::vector<cv::Point>  & listOfPointsToProcess);
};

void testSparseConnectedComponents();