Connected Component Labeling 1

Recently, I became interested in connected component labeling (CCL) algorithms because of a competition on TopCoder. Over the next few weeks I plan to explore various algorithms including parallel algorithms written to take advantage of nVidia GPUs via the CUDA programming model.

To simply things and enable me to concentrate on the algorithms, all images will be in PPM P6 format and will be loaded into a vector (image) of integers. The image vector will be processed by the CCL algorithm. The transformed image vector will then be written out to a PPM P6 file for viewing by an external application such as GIMP.

Here is an example program which contains a PPM class for reading, writing, inverting, and displaying some information about a PPM file. An image is read into the image vector with the red, green and blue components stored in specific bits of each integer. It also contains a simple timer class which uses clock_getttime() to retrieve the monotomic time.

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <unistd.h>
#include <time.h>

using namespace std;

class Timer {

    private:

        timespec starttime, endtime;
        float elapsed;

        float difftime(timespec start, timespec end)
        {
            float temp;

            temp = (end.tv_sec - start.tv_sec)  +
                   (float) (end.tv_nsec - start.tv_nsec) / 1000000000.0;

            return temp;
        }

    public:

        Timer() {
            elapsed = 0.00;
        }

        void reset() {
            elapsed = 0.00;
        }

        void start() {
            elapsed = 0.00;
            clock_gettime(CLOCK_MONOTONIC, &starttime);
        }

        void stop() {
            clock_gettime(CLOCK_MONOTONIC, &endtime);
            elapsed = elapsed + difftime(starttime, endtime);
        }

        void restart() {
            clock_gettime(CLOCK_MONOTONIC, &starttime);
        }

        void print() {
            cout << "Elapsed time: " << elapsed << endl;
        }
};


class PPM {

  protected:

    int width;
    int height;
    int maxColor;
    vector  image;

  public:

    PPM()
    {
        width = 0;
        height = 0;
        maxColor = 0;
    }

    int readfile(char *filename);

    int writefile(char* filename);

    void printsize()
    {
       cout << "Image height: " << height << endl;
       cout << "Image width: " << width << endl;
       cout << "Image vector size: " << image.size() << endl;
    }

    void invertpixel()
    {
       for (vector::iterator it = image.begin(); it != image.end(); ++it) {
           *it = 0x00FFFFFF - *it;
       }
    }
};

int
PPM::readfile(char* filename)
{
    ifstream fin;
    char buf[256];
    unsigned char red, green, blue;
    int i, j, rgb;

    fin.open(filename);
    if (!fin.is_open()) return 1;

    fin.getline(buf, 256);
    if (buf[0] != 'P' || buf[1] != '6') {
       fin.close();
       return 1;
    }
    while (fin.peek()=='#') fin.getline(buf, 256);

    fin >> width >> height >> maxColor;
    fin.getline(buf, 256);                // discard rest of line 

    image.resize(height*width);
    for (i = 0; i < height; i++) {
        for (j = 0; j < width; j++) {
            fin >> red >> green >> blue;
            rgb = ((int)blue & 0x000000ff) << 16 |
                  ((int)green & 0x000000ff ) << 8 |
                  ((int)red & 0x000000ff) | 0x00000000;
            image[i * width + j] = rgb;
        }
    }

    fin.close();
    return 0;
}

int
PPM::writefile(char* filename)
{
    ofstream fout;
    stringstream ss;
    unsigned char red, green, blue;
    int i, j, rgb;

    fout.open(filename);
    if (!fout.is_open()) return 1;

    fout << "P6" << endl;
    ss << width << " " << height;
    fout << ss.str() << endl;
    fout << "255" << endl;

    for (i = 0; i < height; i++) {
        for (j = 0; j < width; j++) {
            rgb = image[i * width + j];
            red = (rgb & 0x000000FF);
            green = (rgb & 0x0000FF00) >> 8;
            blue = (rgb & 0x00FF0000) >> 16;
            fout << red << green << blue;
        }
    }

    fout.close();
    return 0;
}
void
usage(char *name,
      int mode)
{
    cerr << "Usage: " << name << " [-d] infile outfile" << endl;
    exit(mode);
}

int
main(int argc,
     char *argv[])
{
    int c, result = 0;
    int dflag = 0, iflag = 0;
    PPM ppm;
    Timer timer;

    if (argc == 1)
        usage(argv[0], 0);

    opterr = 0;
    while ((c = getopt( argc, argv, "di")) != -1) {
       switch (c) {
          case 'd':
             dflag = 1;
             break;
          case 'i':
             iflag = 1;
             break;
          case '?':
          case 'h':
             usage(argv[0], 0);
             break;
       }
    }

    if (optind != argc-2) {
        cerr << "ERROR: An input file and an output file must be specified" << endl;
        usage(argv[0], 1);
    }


    timer.start();
    if (ppm.readfile(argv[optind++])) {
        cerr << "ERROR: Failed to read input file" << endl;
        exit(1);
    }

    if (dflag) ppm.printsize();

    if (iflag) ppm.invertpixel();

    if (ppm.writefile(argv[optind])) {
        cerr << "ERROR: Failed to write output file" << endl;
        exit(1);
    }

    timer.stop();
    timer.print();

    exit(0);
}

Here is an alternative way of reading and writing an image file using mmap()

#include <fcntl.h>
#include <sys/mman.h>
#include <string.h>
#include <stdio.h>

int 
PPM::readfile(char *filename)
{
    FILE *fp;
    struct stat statbuf;
    char buf[256];
    int *pwidth = &width;
    int *pheight = &height;

    if ((fp = fopen(filename, "r")) == NULL) return 1;

    do {
        fgets(buf, 256, fp);
    } while(buf[0] == '#');

    if (buf[0] != 'P' || buf[1] != '6') {
       fclose(fp);
       return 1;
    }
    
    do {
        fgets(buf, 256, fp);
    } while(buf[0] == '#');

    sscanf(buf, "%u %u", pwidth, pheight);
    fscanf(fp, "%u\n", &maxColor);

    image.resize(height*width);
    long offset = ftell(fp);
    int fd = fileno(fp);
    fstat(fd, &statbuf);

    unsigned char* data = (unsigned char*)mmap(0, statbuf.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
    if (data == MAP_FAILED) {
        fprintf(stderr, "ERROR: mmap failed. %s\n", strerror(errno));
        fclose(fp);
        return 1;
    }

    unsigned char* data_offset = (unsigned char*)(data + offset);
    unsigned char red, green, blue;
    int i = 0, o = 0;
    for (int y = 0; y < height * width; y++) {
        blue = data_offset[i++];
        green = data_offset[i++];
        red = data_offset[i++];
        image[o++] = red << 16 | green << 8 | blue;
    }

    munmap(data, statbuf.st_size);
    close(fd);

    return 0;
}

int
PPM::writefile(char* filename)
{
    unsigned int rgb;
    int result;

    int fd = open(filename, O_RDWR | O_CREAT | O_TRUNC, (mode_t)0600);
    if (fd == -1) {
        fprintf(stderr, "ERROR: Cannot create output file\n");
        return 1;
    }

    char buf[256];
    sprintf(buf, "P6\n%d %d\n255\n", width, height);
    int bufsize = strlen(buf);

    int mmap_size = bufsize + (height * width * 3);
    if (((result = lseek(fd, mmap_size - 1, SEEK_SET)) == -1) ||
        ((result = write(fd, "", 1)) == -1)) {
        fprintf(stderr, "ERROR: Cannot write null at end of output file\n");
        close(fd);
        return 1;
    }

    unsigned char* data = (unsigned char*)mmap(0, mmap_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
    if (data == MAP_FAILED) {
        fprintf(stderr, "ERROR: mmap failed. %s\n", strerror(errno));
        close(fd);
        return 1;
    }

    int o = 0;
    for (int i = 0; i < bufsize; i++)
        data[o++] = buf[i];

    for (int i = 0; i < height * width; i++) {
        rgb = image[i];
        data[o++] = rgb & 0xFF;
        data[o++] = (rgb >> 8) & 0xFF;
        data[o++] = (rgb >> 16) & 0xFF;
    }

    munmap(data, mmap_size);
    close(fd);

    return(0);
}

Note the need to seek to the end of the new file and write a null before calling mmap() when writing a file. Also MAP_SHARED must be used instead of MAP_PRIVATE otherwise your file will contain nothing but zeros.

Well, that is all I have time for at present. In my next post on this subject I will implement a 4-connected thresholding union-find algorithm.