In the post before last we discussed using cvBlobsLib as a tool for blob extraction. We're going to revisit the extraction theme and look at a C++ implementation of the Connected Component Labeling method, but before we do that we're going to look at an implementation of the Disjoint Set data structure that will provide us with the necessary tool for generating equivalence sets.
The Disjoint Set data structure allows us to track elements partitioned into disjoint subsets. Two sets are disjoint provided their intersection is the empty set, i.e. no element belongs to both sets. In addition to tracking the subsets the structure identifies a representative element (in the second pass of the Connected Component Labeling method we will replace all elements with the representative element of the subset to which they belong).
The data structure should implement three methods, MakeSet() for generating new sets, Find() for locating the representative element, and Union() for joining two subsets into one equivalence set. These methods are available in the declaration below. Additionally, in anticipation of the Labeling method we've include two methods, Reduce() for reducing the labels of the representative elements (node.i) to the sequence 0,1,...,n-1 and returning the number of subsets, n, and Reset() for setting the element count to zero.
#include <vector>
struct node {
node *parent;
int i, rank;
};
class cDisjointSet {
private:
std::vector<node *> nodes;
int elements, sets;
protected:
public:
cDisjointSet();
~cDisjointSet();
node* MakeSet(int i);
node* Find(node* a);
void Union(node* a0, node* a1);
int ElementCount();
int SetCount();
int Reduce();
void Reset();
};
In the definition of cDisjointSet below the MakeSet() method simply allocates a node if necessary, points the node to itself, sets the label, and sets its rank to zero (for implementing union by rank). The Find() method seeks the representative element. Here we've implemented this method with path compression to connect child nodes directly to their representative element. This will reduce the seek time by flattening out the tree. The third method, Union(), joins two sets into one. We've implemented this method with union by rank. By comparing rank we can improve the balance of the tree by joining the smaller tree to the larger. As mentioned the Reduce() method seeks out representative elements and assigns each a unique label in 0,1,...,n-1.
#include "disjointset.h"
cDisjointSet::cDisjointSet() : elements(0), sets(0) {
}
cDisjointSet::~cDisjointSet() {
for (int i = 0; i < nodes.size(); i++) delete nodes[i];
nodes.clear();
}
node* cDisjointSet::MakeSet(int i) {
if (elements + 1 > nodes.size()) nodes.push_back(new node);
nodes[elements]->parent = nodes[elements];
nodes[elements]->i = i;
nodes[elements]->rank = 0;
elements++;
sets++;
return nodes[elements-1];
}
node* cDisjointSet::Find(node* a) { // with path compression
if (a->parent == a) return a;
else {
a->parent = Find(a->parent);
return a->parent;
}
}
void cDisjointSet::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->parent = a3;
else if (a3->rank < a2->rank) a3->parent = a2;
else {
a2->parent = a3;
a3->rank++;
}
sets--;
}
int cDisjointSet::ElementCount() {
return elements;
}
int cDisjointSet::SetCount() {
return sets;
}
int cDisjointSet::Reduce() {
int j = 0;
for (int i = 0; i < elements; i++)
if (nodes[i]->parent == nodes[i])
nodes[i]->i = j++;
return j;
}
void cDisjointSet::Reset() {
elements = sets = 0;
}
Below we declare an object, cTracker2, which differs slightly from cTracker in our previous projects. Here we are not using cvBlobsLib, so we've removed those properties relevant to cvBlobsLib and added a method, extractBlobs(), to take its place.
#ifndef TRACKER2_H
#define TRACKER2_H
#include <opencv/cv.h>
#include "blob.h"
#include "disjointset.h"
class cTracker2 {
private:
double min_area, max_radius;
node **labels; unsigned int width, height;
// storage of the current blobs and the blobs from the previous frame
vector<cBlob> blobs, blobs_previous;
cDisjointSet ds;
protected:
public:
cTracker2(double min_area, double max_radius);
~cTracker2();
void extractBlobs(cv::Mat &mat);
void trackBlobs(cv::Mat &mat, bool history);
void scaleBlobs();
vector<cBlob>& getBlobs();
};
#endif
Here we will only discuss the extractBlobs() method; the rest is identical to our previous project. As it's name implies the Connected Component Labeling method will step through our threshold image labeling pixels. Those pixels that belong to the same connected component will be joined into one equivalence set. Here we've implemented the 4-connected model, i.e. the values of the pixels above, below, and to either side of each pixel are evaluated to determine if they belong to the same equivalence set. As we are stepping through the image left to right, top to bottom, we need only evaluate the pixel values above and to the left. These pixels will be joined with the pixels further on by the data structure provided they belong to the same connected component.
I've optimized this algorithm slightly in the code below. To prevent the need for checking bounds, we've separated the algorithm into three stages. The top left pixel has no need to check any neighbors, so we generate a new set for this pixel. We then process the remainder of the first row. These pixels only need to check the value of the pixel to the left. If the values are the same we assign the current pixel the label of its neighbor, otherwise we generate a new set. In the third stage we need to check the value of the pixels above and to the left. If the value of the pixel to the left of the current pixel is the same we assign the current pixel the same label and check the value of the pixel above. If the value of the pixel above is the same as that of to the left, we join them into the same equivalence set. If the value of the pixel to the left is not the same as the current pixel but the value of the pixel above is, we assign the current pixel the same label as the pixel above. Lastly, if neither condition applies, we generate a new set.
Once this first pass is complete we user our helper method, Reduce(), to generate a sequence, 0,1,...,n-1, for the representative elements and return the number of connected components, n. We then push n temporary blobs onto the vector and start our second pass. In our second pass we simple search for the axis-aligned bounding box for each blob. Afterward, we apply our blob filter based on minimum area and evaluate the blob centers based on the axis-aligned bounding boxes.
#include "tracker2.h"
cTracker2::cTracker2(double min_area, double max_radius) :
min_area(min_area), max_radius(max_radius),
labels(NULL) {
}
cTracker2::~cTracker2() {
if (labels) delete [] labels;
}
void cTracker2::extractBlobs(cv::Mat &mat) {
// mat.cols, mat.rows -- allocate vectors
if (mat.cols != width || mat.rows != height) {
width = mat.cols; height = mat.rows;
if (labels) delete [] labels;
labels = new node*[width*height];
}
// reset our data structure for reuse
ds.Reset();
int index;
// generate equivalence sets -- connected component labeling (4-connected)
labels[0] = ds.MakeSet(0);
for (int j = 1; j < mat.cols; j++)
labels[j] = mat.data[j] != mat.data[j-1] ? ds.MakeSet(0) : labels[j-1];
for (int j = mat.cols; j < mat.rows*mat.cols; j++) {
if (mat.data[j] == mat.data[j-1]) {
labels[j] = labels[j-1];
if (mat.data[j-1] == mat.data[j-mat.cols]) ds.Union(labels[j-1], labels[j-mat.cols]);
}
else if (mat.data[j] == mat.data[j-mat.cols]) labels[j] = labels[j-mat.cols];
else labels[j] = ds.MakeSet(0);
}
// the representative elements in our disjoint set data struct are associated with indices
// we reduce those indices to 0,1,...,n and allocate our blobs
cBlob temp;
temp.event = BLOB_NULL;
blobs.clear();
for (int i = 0; i < ds.Reduce(); i++)
blobs.push_back(temp);
// populate our blob vector
for (int j = 0; j < mat.rows; j++) {
for (int i = 0; i < mat.cols; i++) {
index = ds.Find(labels[j*mat.cols+i])->i;
if (blobs[index].event == BLOB_NULL) {
blobs[index].min.x = blobs[index].max.x = i;
blobs[index].min.y = blobs[index].max.y = j;
blobs[index].event = BLOB_DOWN;
blobs[index].height = 0;
} else {
if (blobs[index].min.x > i) blobs[index].min.x = i;
else if (blobs[index].max.x < i) blobs[index].max.x = i;
blobs[index].max.y = j;
}
}
}
// apply blob filter
for (int i = 0; i < blobs.size(); i++) {
if ((blobs[i].max.x-blobs[i].min.x)*(blobs[i].max.y-blobs[i].min.y) < min_area) { blobs.erase(blobs.begin()+i); i--; }
}
// find blob centers
for (int i = 0; i < blobs.size(); i++) {
blobs[i].location.x = blobs[i].origin.x = (blobs[i].max.x + blobs[i].min.x) / 2.0;
blobs[i].location.y = blobs[i].origin.y = (blobs[i].max.y + blobs[i].min.y) / 2.0;
}
}
void cTracker2::trackBlobs(cv::Mat &mat, bool history) {
// clear the blobs from two frames ago
blobs_previous.clear();
// before we populate the blobs vector with the current frame, we need to store the live blobs in blobs_previous
for (int i = 0; i < blobs.size(); i++)
if (blobs[i].event != BLOB_UP)
blobs_previous.push_back(blobs[i]);
extractBlobs(mat);
// initialize previous blobs to untracked
for (int i = 0; i < blobs_previous.size(); i++) blobs_previous[i].tracked = false;
// main tracking loop -- O(n^2) -- simply looks for a blob in the previous frame within a specified radius
for (int i = 0; i < blobs.size(); i++) {
for (int j = 0; j < blobs_previous.size(); j++) {
if (blobs_previous[j].tracked) continue;
if (sqrt(pow(blobs[i].location.x - blobs_previous[j].location.x, 2.0) + pow(blobs[i].location.y - blobs_previous[j].location.y, 2.0)) < max_radius) {
blobs_previous[j].tracked = true;
blobs[i].event = BLOB_MOVE;
blobs[i].origin.x = history ? blobs_previous[j].origin.x : blobs_previous[j].location.x;
blobs[i].origin.y = history ? blobs_previous[j].origin.y : blobs_previous[j].location.y;
}
}
}
// add any blobs from the previous frame that weren't tracked as having been removed
for (int i = 0; i < blobs_previous.size(); i++) {
if (!blobs_previous[i].tracked) {
blobs_previous[i].event = BLOB_UP;
blobs.push_back(blobs_previous[i]);
}
}
}
vector<cBlob>& cTracker2::getBlobs() {
return blobs;
}
In the main.cc file I've added a key event. Pressing e toggles the blob extraction method from cvBlobsLib to the method discussed here.
I am currently working on an event system for handling blob and fiducial events. My next post will likely focus on an event queue which parses out events to registered widgets.
Download this project: tracker2.tar.bz2
