Pixel chains from run length encoding

Question

I've been banging my head for a long time on this one

I am doing imaging. So far I've binarized my images, meaning that from a grayscale image, every pixel under a certain value are dropped. This gives me only some regions out of the original image with a lot of "zero pixels" all around those regions.

Next I've run length encoded my regions into "blobs". Runs are a method of compression for data. For example, suppose that you have binarized a square, the you will have only a few runs describing the whole image. The runs are defined by x,y coordinates and a length.

When recreating the image, for each run, go to x,y coordinate and add pixels on the x axis for the length of the run.

Now I have to take the runs and create a chain out of it that will describe the contour of the region. I don't know how to do that.

I have a bunch of x,y,length runs and I have to "navigate" around the edges to form a chain. Normally in imaging this process is done with the original image but I can't use the original image anymore here so I have to compute it with the runs.

I know this looks like a big wall of text but I don't know how to ask this question better.

Any hints or pointers on identical implementation would be awesome.

EDIT

thanks to unwind, Ill link a few images :

In this example, they process the image B into the contour C (which I call chain). However I'd like to generate the contour from D, the Run Lengths

Answer 1

At first glance I don't see a practical algorithm for that. A poor man's solution would be expand the original image from the length encoded one. So if your lines look like this:

A 3B 10A C 8D
C 4D 3A 6C 9A

where the characters return the actual pixel value ( e.g. A = 0, B = 127,...). You could write the pixel values into a two dimensional array (or another datastructure of your choice).It looks like this:

ABBBAAAAAAAAAACDDDDDDDD
CDDDDAAACCCCCCAAAAAAAAA

Afterwards generate your chain, delete the array and keep the chain information. Sure this is expensive so maybe you could do this before length-encoding the original picture.

Answer 2

Here's a perfectly simple and practical solution (C++):

#include <iostream>
#include <vector>

struct Run { int x, w; };
enum { EAST, NORTHEAST, NORTH, NORTHWEST, WEST, SOUTHWEST, SOUTH, SOUTHEAST };

int main() {

    const Run data[] = {
        { 7, 2 },
        { 5, 6 },
        { 5, 7 },
        { 5, 7 },
        { 6, 6 },
        { 0, 12 },
        { 0, 12 },
        { 0, 11 },
        { 1, 7 },
        { 3, 4 },
        { 3, 4 },
        { 3, 5 },
        { 3, 7 },
        { 3, 7 },
        { 5, 5 }
    };

    std::vector<Run> runs(data, data + 15);
    std::vector<int> before;
    std::vector<int> after;
    unsigned int i;
    int j;

    for (i = 0; i < runs.size() - 1; ++i) {

        if (runs[i].x < runs[i + 1].x) {

            for (j = 0; j < runs[i + 1].x - runs[i].x - 1; ++j)
                before.push_back(WEST);
            before.push_back(NORTHWEST);

        } else if (runs[i].x > runs[i + 1].x) {

            before.push_back(NORTHEAST);
            for (j = 0; j < runs[i].x - runs[i + 1].x - 1; ++j)
                before.push_back(EAST);

        } else {

            before.push_back(NORTH);

        }

        int first_right(runs[i].x + runs[i].w);
        int second_right(runs[i + 1].x + runs[i + 1].w);

        if (first_right < second_right) {

            after.push_back(SOUTHEAST);
            for (j = 0; j < second_right - first_right - 1; ++j)
                after.push_back(EAST);

        } else if (first_right > second_right) {

            for (j = 0; j < first_right - second_right - 1; ++j)
                after.push_back(WEST);
            after.push_back(SOUTHWEST);

        } else {

            after.push_back(SOUTH);

        }

    }

    for (j = 0; j < runs.back().w - 1; ++j)
        after.push_back(WEST);

    std::reverse(before.begin(), before.end());
    after.insert(after.end(), before.begin(), before.end());

    for (j = 0; j < int(after.size()); ++j) {
        switch (after[j]) {
        case EAST:      std::cout << "EAST\n";      break;
        case NORTHEAST: std::cout << "NORTHEAST\n"; break;
        case NORTH:     std::cout << "NORTH\n";     break;
        case NORTHWEST: std::cout << "NORTHWEST\n"; break;
        case WEST:      std::cout << "WEST\n";      break;
        case SOUTHWEST: std::cout << "SOUTHWEST\n"; break;
        case SOUTH:     std::cout << "SOUTH\n";     break;
        case SOUTHEAST: std::cout << "SOUTHEAST\n"; break;
        }
    }

}

This works by iterating over the runs, testing the left and right endpoints for the direction they're jumping to, and adding the appropriate number of chain elements to two vectors: one in forward order, for the right side, and one in reverse order, for the left. It then connects the two chains by adding the appropriate number of links for the last scanline, then reverses the left side chain and appends it to the right one to produce the final chain.

Hope this is what you're looking for!

Answer 3

Well I lost that contract but the answer was to use the Freeman Chain Coding technique

The fact that it is run lengths encoding has nothing to do with the algorithm, unlike I previously thought.