FindBlobs.icpp

/***********************************************************************
FindBlobs - Helper function to extract all eight-connected blobs of
pixels from a frame that match an arbitrary property.
Copyright (c) 2010-2013 Oliver Kreylos

This file is part of the Augmented Reality Sandbox (SARndbox).

The Augmented Reality Sandbox is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.

The Augmented Reality Sandbox is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License along
with the Augmented Reality Sandbox; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
***********************************************************************/

#define FINDBLOBS_IMPLEMENTATION

#include "FindBlobs.h"

namespace {

template <class PixelParam>
struct LineBlob { // Helper structure to assemble blobs one line at a time
    /* Embedded classes: */
public:
    typedef PixelParam Pixel; // Underlying pixel type

    /* Elements: */
public:
    unsigned int x1, x2;
    unsigned int y;
    unsigned int parent, rank;
    unsigned int min[2], max[2];
    double sumX, sumY, sumW;
    BlobProperty<Pixel> blobProperty;

    /* Methods: */
    void merge(const LineBlob& other) {
        for (int i = 0; i < 2; ++i) {
            if (min[i] > other.min[i]) {
                min[i] = other.min[i];
            }
            if (max[i] < other.max[i]) {
                max[i] = other.max[i];
            }
        }
        sumX += other.sumX;
        sumY += other.sumY;
        sumW += other.sumW;
        blobProperty.merge(other.blobProperty);
    }
};

}

template <class PixelParam, class PixelPropertyParam>
inline
std::vector<Blob<PixelParam> >
findBlobs(const unsigned int size[2],
          const PixelParam* frame,
          const PixelPropertyParam& property) {
    /* Create a list of line blobs: */
    std::vector<LineBlob<PixelParam> > lineBlobs;
    unsigned int numLineBlobs = 0; // Number of line blobs in the current list
    unsigned int lastLineStart = 0; // Index of first line blob for the previous pixel row
    unsigned int lastLineEnd = 0; // Index one after last line blob for the previous pixel row

    /* Process all pixel rows: */
    const PixelParam* frameRowPtr = frame;
    for (unsigned int y = 0; y < size[1]; ++y, frameRowPtr += size[0]) {
        /* Find all line blobs on the current line: */
        unsigned int x = 0;
        const PixelParam* framePtr = frameRowPtr;
        while (x < size[0]) {
            /* Skip non-property pixels: */
            while (x < size[0] && !property(x, y, *framePtr)) {
                ++x;
                ++framePtr;
            }
            if (x >= size[0]) {
                break;
            }

            /* Collect a new line blob: */
            LineBlob<PixelParam> lb;
            lb.x1 = x;
            lb.blobProperty.addPixel(x, y, *framePtr);
            ++x;
            ++framePtr;
            while (x < size[0] && property(x, y, *framePtr)) {
                lb.blobProperty.addPixel(x, y, *framePtr);
                ++x;
                ++framePtr;
            }
            lb.x2 = x;
            lb.y = y;
            lb.parent = numLineBlobs;
            lb.rank = 0;
            lb.min[0] = lb.x1;
            lb.min[1] = y;
            lb.max[0] = lb.x2;
            lb.max[1] = y + 1;
            lb.sumW = double(lb.x2 - lb.x1);
            lb.sumX = double(lb.x1 + lb.x2 - 1) * lb.sumW * 0.5;
            lb.sumY = double(y) * lb.sumW;
            lineBlobs.push_back(lb);
            ++numLineBlobs;

            /* Finish the line blob: */
            ++x;
            ++framePtr;

            /* Merge the new line blob with any line blobs it touches from the previous line: */
            for (unsigned int i = lastLineStart; i < lastLineEnd; ++i) {
                if (lineBlobs[i].x1 <= lb.x2 && lineBlobs[i].x2 >= lb.x1) { // Check detects eight-connected blobs
                    /* Merge the two blobs: */
                    unsigned int root1 = i;
                    while (root1 != lineBlobs[root1].parent) {
                        root1 = lineBlobs[root1].parent;
                    }
                    unsigned int root2 = numLineBlobs - 1;
                    while (root2 != lineBlobs[root2].parent) {
                        root2 = lineBlobs[root2].parent;
                    }
                    if (root1 != root2) {
                        if (lineBlobs[root1].rank > lineBlobs[root2].rank) {
                            lineBlobs[root2].parent = root1;
                            lineBlobs[root1].merge(lineBlobs[root2]);
                        } else {
                            lineBlobs[root1].parent = root2;
                            if (lineBlobs[root1].rank == lineBlobs[root2].rank) {
                                ++lineBlobs[root2].rank;
                            }
                            lineBlobs[root2].merge(lineBlobs[root1]);
                        }
                    }
                }
            }
        }

        /* Go to the next line: */
        lastLineStart = lastLineEnd;
        lastLineEnd = numLineBlobs;
    }

    /* Convert all line blobs that are their own parents into "real" blobs: */
    std::vector<Blob<PixelParam> > result;
    for (unsigned int i = 0; i < numLineBlobs; ++i) {
        /* Check if the line blob is a root and not just a single pixel: */
        if (lineBlobs[i].parent == i && lineBlobs[i].sumW > 0.0) {
            Blob<PixelParam> b;
            b.x = (lineBlobs[i].sumX + lineBlobs[i].sumW * 0.5) / lineBlobs[i].sumW;
            b.y = (lineBlobs[i].sumY + lineBlobs[i].sumW * 0.5) / lineBlobs[i].sumW;
            for (int j = 0; j < 2; ++j) {
                b.min[j] = lineBlobs[i].min[j];
                b.max[j] = lineBlobs[i].max[j];
            }
            b.blobProperty = lineBlobs[i].blobProperty;
            result.push_back(b);
        }
    }

    return result;
}