Trace a Path

[Brownhead]

I'm trying to create a routine that will trace a road stored in a monochrome bitmap. The road can have any amount of forks and splits in it but it stays a pretty consistent width the whole way though. Heres an example of a bitmap that may be passed to this routine.

However, the routine may also be passed a bitmap full of absolute rubbish. And it needs to detect that. If it is actually a road however, it needs to return a series of points that run along the path... Its kind of like a raster to vector conversion.
Now the problem is, I have no idea how to make this. I've come up with some ideas but I really don't think any of them will turn out very well if I actually start to put them into code, so does anyone know of some examples that deal with something like this. I just need some pointers in the right direction.. I'm very lost as to where to start.

[Mybowlcut]

I'm not aware of anything that can do this type of thing.. someone else might be.

What are your ideas? The only thing that I can think of is kind of brute force... iterate over every pixel, searching for a user-specified colour, perhaps? If the colour is found at that location, create a point. That would of course create hundreds of points... so you could do another test after you've found all your points. The test would determine whether there are two points that are more than one pixel away from each other on the same axis (no slope):



Assuming the pixels are stored consecutively, you could then erase every point between those two points?

Might not be great but that's a start haha.

[Brownhead]

Thanks but I don't think that'd work too well.. My way was very difficult to understand so I made a writeup, its on another computer though, so I'll post it when I can.

[TheCPUWizard]

The typical approach: [replace color with shade for monochrome]

1) Determine what range of colors make up a road.
2) Determine the minimum and maximum wdith of a road.
3) Scan the image collecting circular regions of the MINIMUM width that are all of road color(s).

You now have a potential list of nodes.

Walk the nodes scanning for overlaps, building them into chains. At any particular point in the chain, track the MAXIMUM included distance in any straight line.

All distances which are less then the MAXIUMUM width of a road, can be merged to a single elipse with a center point at the mid-point of the maximal qualifying distance.

You now have a series of points which align to the center or the road(s).

From here you reduce the set further be dectecting sequenctial points which do NOT diverge. This is a road segment. Each diveragance represents a junction in the roads.

Further reduce the set so that all segments which are in a straight line (or within a tolerance) are considered a single segment.

You nothave a map of all of the end points of each road segment, and can crreate your vectors as well as all intersection points.

[Brownhead]

I think I understand, I never would have though of that , thanks!

[TheCPUWizard]

Start with a small simple image that you have created in paintbrush. Just two colors, an one simple straight road.

Then write the basic classes. Factor the design well. Strive for no method having more than 20 lines of code (not counting braces or comments).

Debug it throughly. Then increase the complexity of the image gradually.

The prior description is a semi-brute force approach. As you are developing the code, you may see patterns which you can utilize and optimze the approach.

If you change the design, make sure to go back and run it through each of the test patterns you have crerated.

You should be able to do it...

[Brownhead]

Thanks , I'm sure I'll get it eventually! You've been a great help!
You seem to know a lot about graphic manipulation though, any chance you could glance through a function I've been having a lot of trouble with, its supposed to draw a cluster into a dc. The clusters are essentially black and white bitmaps. Except their not stored in standard bitmap formatting. Just a simple multidimensional char array. Each bit corresponds to a pixel. But I'm trying to convert it to a standard bitmap format to draw it on the screen. Heres the function

/*
    Function: DrawCluster
    Parameters:
        hDC - The Device Context to draw into
        Source - The cluster to draw
    Returns:
        A boolean value signifying whether the function
        suceeded or not.
    Description:
        This will draw a cluster onto the screen in two
        colors (The background color of the DC and the
        foreground color)
    Walkthrough:
        Ln 1-29: Aligns the data correctly so it can be
                 read by CreateBitmap.
        Ln 30-48: Creates the bitmap and draws it to the
                  Device Context
    History:
        DATE         AUTHOR             REASON
        5/21/2008    Brownhead          Created
*/
bool DrawCluster (HDC hDC, CLUSTER* Source)
{
    // If the cluster is empty don't try to do any operations on it.
    if (Source == NULL) return false;

    // The width and height of the source cluster
    int Source_Width = abs((*Source).Rect.right - (*Source).Rect.left) + 1;
    int Source_Height = abs((*Source).Rect.bottom - (*Source).Rect.top) + 1;

    /* The bitmap needs to be word aligned, this gets the new width
       that needs to be used. For more information please refere to:
       http://www.experts-exchange.com/Programming/Languages/CPP/Q_23415623.html */

    // Retrieve the width in bytes
    int Frmt_Width = (int) ceil(Source_Width / 8);

    // If it is not even
    if (Frmt_Width % 2 != 0)
    {
        // Add one to the width to make it even
        Frmt_Width++;

        // Sharing is caring
        cout << "Not Even";
    } else {
        cout << "Even";
    }

    // Creates a buffer that's used to write the word aligned (formatted) array
    char* Data_Frmt = (char*) calloc(Frmt_Width * Source_Height, 1);
    cout << "\nFrmt_Width=" << Frmt_Width << "\n";
    // Makes the Frmt_Width represent the width in BITS instead of BYTES
    Frmt_Width = Frmt_Width * 8;

    // Loops through the rows of the data
    for (int i_Data_Y = 0; i_Data_Y < Source_Height; i_Data_Y++)
    {
        // Loops through the entries of the current row
        for (int i_Data_X = 0; i_Data_X < Source_Width; i_Data_X++)
        {
            // The byte (char) that were editing (Index for the Data array)
            int Data_Index = (int) floor(((i_Data_Y * Source_Width) + i_Data_X) / 8);
            int Data_Frmt_Index = (int) floor(((i_Data_Y * Frmt_Width) + i_Data_X) / 8);

            // The mask for the bit were going to edit. (This should help: http://www.programmersheaven.com/mb/beginnercpp/346240/346240/ReadMessage.aspx)
            int Data_Bit = 1 << (7 - (((i_Data_Y * Source_Width) + i_Data_X) % 8));
            int Data_Frmt_Bit = 1 << (7 - (((i_Data_Y * Frmt_Width) + i_Data_X) % 8));

            // Set the bit on or off, you decide :)
            if (CHKBITS((*Source).Data[Data_Index], Data_Bit)) SETBITS(Data_Frmt[Data_Frmt_Index], Data_Frmt_Bit);
        }
    };
    CLUSTER ClusterBuffer;

    cout << "Mark 1\n" << Source_Height << 'x' << Source_Width << '\n';
    ClusterBuffer.Rect.left = ClusterBuffer.Rect.top = 1;
    ClusterBuffer.Rect.bottom = Source_Height;
    ClusterBuffer.Rect.right = Frmt_Width;
    ClusterBuffer.Data = Data_Frmt;

    PrintCluster (&ClusterBuffer);

    // Uses the data array to create a monochrome bitmap
    HBITMAP Buffer_Bitmap = CreateBitmap (Source_Width, Source_Height, 1, 1, Data_Frmt);

    cout << "Mark 3\n";
    // Get rid of our formatted DIBits as soon as possible
    free (Data_Frmt);
    cout << "Mark 4\n";

    // A buffer DC to select the bitmap into
    HDC Buffer = CreateCompatibleDC (NULL);

    // Select the bitmap into the dc
    SelectObject (Buffer, Buffer_Bitmap);

    // Attempt to draw the cluster
    bool Result = (BitBlt (hDC, 0, 0, Source_Width, Source_Height, Buffer, 0, 0, SRCCOPY) != 0);

    // Cleans up
    DeleteObject (Buffer_Bitmap);
    DeleteDC (Buffer);

    cout << "Mark 2\n";

    // Return the result
    return Result;
}

See anything I'm doing wrong? It will work some of the time. If the width of the cluster divided by 8 is an odd number, it will work, if it is an even number, it will not. I can't seem to figure it out. You've already helped so much so don't worry about it, just if you see any really obvious errors. Thanks