How to trace line segments in a binary skeletonized image?

Question

I have a binarized and skeletonized image. I used Zhang-Suen algorithm for skeletonization. Now I need to get line segments from the image in a 2-point format (starting and ending point of the line segment). So far I have been using OpenCV function findContours, with CV_CHAIN_APPROX_SIMPLE and CV_RETR_LIST options. However, three problems emerge:

1. This method returns duplicate line segments (in opposite direction)
2. Connected structures get sometimes disconnected due to the "hierarchy feature"
3. Messy results in the vicinity of lines' intersections.

Is there another way to trace the line segments from the image?

Magnified section of the image I need to trace:

Answer 1

That should work. It does 4 scan of the image (you can probably reduce the number of scans, but the logic would be more complicated).

In each scan, it tracks horizontal lines, vertical lines, diagonal towards down lines, and diagonal towards up lines.

Lines are stored in a vector<Vec4i>, where each Vec4i is a line with Xstart, Ystart, Xend, Yend;

Let me know if this works for you.

#include <opencv2/opencv.hpp>

using namespace std;
using namespace cv;

int main()
{
    Mat1b img = imread("path_to_image", IMREAD_GRAYSCALE);

    Mat1b w;
    // Add bg border
    copyMakeBorder(img, w, 1, 1, 1, 1, BORDER_CONSTANT, Scalar(0));

    vector<Vec4i> lines;
    Vec4i line;

    // Scan horizontal lines 
    for (int y = 1; y < w.rows - 1; ++y)
    {
        for (int x = 1; x < w.cols - 1; ++x)
        {
            if (w(y, x) == 255)
            {
                int yy = y;
                int xx = x;

                //Save first point
                line[0] = xx - 1;
                line[1] = yy - 1;

                while (true)
                {
                    if (w(yy, xx + 1))
                    {
                        // Mark as detected
                        w(yy, xx) = 1;
                        ++xx;
                    }
                    else
                    {
                        // End of the line
                        line[2] = xx - 1;
                        line[3] = yy - 1;

                        if (line[2] - line[0] > 0)
                        {
                            lines.push_back(line);
                        }
                        break;
                    }
                }
            }
        }
    }

    // Scan vertical lines 
    for (int y = 1; y < w.rows - 1; ++y)
    {
        for (int x = 1; x < w.cols - 1; ++x)
        {
            if (w(y, x) == 255)
            {
                int yy = y;
                int xx = x;

                //Save first point
                line[0] = xx - 1;
                line[1] = yy - 1;

                while (true)
                {
                    if (w(yy + 1, xx))
                    {
                        // Mark as detected
                        w(yy, xx) = 1;
                        ++yy;
                    }
                    else
                    {
                        // End of the line
                        line[2] = xx - 1;
                        line[3] = yy - 1;

                        if (line[3] - line[1] > 0)
                        {
                            lines.push_back(line);
                        }
                        break;
                    }
                }
            }
        }
    }

    // Scan for diagonal low lines 
    for (int y = 1; y < w.rows - 1; ++y)
    {
        for (int x = 1; x < w.cols - 1; ++x)
        {
            if (w(y, x) == 255)
            {
                int yy = y;
                int xx = x;

                //Save first point
                line[0] = xx - 1;
                line[1] = yy - 1;

                while (true)
                {
                    if (w(yy + 1, xx + 1))
                    {
                        // Mark as detected
                        w(yy, xx) = 1;
                        ++xx;
                        ++yy;
                    }
                    else
                    {
                        // End of the line
                        line[2] = xx - 1;
                        line[3] = yy - 1;
                        if (line[2] - line[0] > 0)
                        {
                            lines.push_back(line);
                        }
                        break;
                    }
                }
            }
        }
    }

    // Scan for diagonal high lines 
    for (int y = 1; y < w.rows - 1; ++y)
    {
        for (int x = 1; x < w.cols - 1; ++x)
        {
            if (w(y, x) == 255)
            {
                int yy = y;
                int xx = x;

                //Save first point
                line[0] = xx - 1;
                line[1] = yy - 1;

                while (true)
                {
                    if (w(yy - 1, xx + 1))
                    {
                        // Mark as detected
                        w(yy, xx) = 1;
                        ++xx;
                        --yy;
                    }
                    else
                    {
                        // End of the line
                        line[2] = xx - 1;
                        line[3] = yy - 1;
                        if (line[2] - line[0] > 0)
                        {
                            lines.push_back(line);
                        }
                        break;
                    }
                }
            }
        }
    }

    RNG rng(12345);
    Mat3b res;
    cvtColor(img, res, COLOR_GRAY2BGR);

    for (int i = 0; i < lines.size(); ++i)
    {
        const Vec4i& lin = lines[i];
        Scalar color = Scalar(rng.uniform(0, 255), rng.uniform(0, 255), rng.uniform(0, 255));
        cv::line(res, Point(lin[0], lin[1]), Point(lin[2], lin[3]), color);
    }

    imshow("res", res);
    waitKey();

    return 0;
}

Starting from this image:

Drawing each detected line (from start to end) with random colors gives:

Zoomed: