How could I sort the coordinates according to the serpentine in the image?

Question

In this following binary image,

I have been able to get the list of coordinates where the value is 1.

The coordinates are stored from left to right.

Question: How could I sort the list of coordinates in such a way that they come one after the other and they follow the path of this serpentine?

Source Code:

from __future__ import division
import numpy as np

import cv2



from skimage.morphology import skeletonize, skeletonize_3d, medial_axis
diff = cv2.imread('img.png', 0)   
diff = diff.astype('uint8')

ret, thresh = cv2.threshold(diff, 1, 255, cv2.THRESH_BINARY)
thresh = cv2.dilate(thresh, None, iterations = 1)



sk = skeletonize_3d(thresh)


pixels = np.argwhere(sk==255)
pixels = np.asarray(pixels)

y = pixels[:,0]
x = pixels[:,1]

L = (x, y) # Question: How can I sort L?

np.savetxt("C:/test.csv", np.c_[L], delimiter = ',', fmt='%f')

Any idea how I could possibly go about with this and sort L according to the serpentine?

Answer 1

This is a "brute force" way of searching a path in the data. It is without back-tracking, so if there are dead-ends (and maybe lines with bigger width than 1) it will fail to find a "better" path.

Unfortunately C++ code only, but quite simple:

int main(int argc, char* argv[])
{
    cv::Mat inputBGR = cv::imread("C:/StackOverflow/Input/serpentine.png");
    if (inputBGR.empty()) return 0;

    cv::Mat input; // mask
    cv::cvtColor(inputBGR, input, CV_BGR2GRAY);

    cv::Mat mask = input.clone(); // keep the original mask. "input" will be modified during processing.

    cv::Point currentPoint = cv::Point(input.cols, input.rows);
    // find most top-left point:
    cv::Point origin(0, 0);
    for (int y = 0; y < input.rows; ++y)
        for (int x = 0; x < input.cols; ++x)
        {
            cv::Point cPoint = cv::Point(x, y);
            if (input.at<unsigned char>(cPoint))
            if (cv::norm(origin - cPoint) < cv::norm(origin - currentPoint)) // can be optimized by re-using temporary results
            {
                currentPoint = cPoint;
            }
        }

    // now find the path
    std::vector<cv::Point> path;

    // add first point:
    path.push_back(currentPoint);
    input.at<unsigned char>(currentPoint) = 0; // invalidate all used points

    while (true)
    {
        bool foundNeighbor = false;
        for (int y = -1; y <= 1; ++y)
        {
            for (int x = -1; x <= 1; ++x)
            {
                if (y != 0 || x != 0)
                {
                    cv::Point cPoint = currentPoint + cv::Point(x, y);
                    if (cPoint.x < 0 || cPoint.x >= input.cols || cPoint.y < 0 || cPoint.y >= input.rows) continue; // skip points outside of the image

                    /*
                    inputBGR.at<cv::Vec3b>(cPoint) = cv::Vec3b(0,255,0);
                    cv::imshow("debug", inputBGR);
                    cv::waitKey(0);
                    inputBGR.at<cv::Vec3b>(cPoint) = cv::Vec3b(255, 255, 255);
                    */

                    if (input.at<unsigned char>(cPoint))
                    {
                        currentPoint = cPoint;
                        path.push_back(cPoint);
                        input.at<unsigned char>(currentPoint) = 0; // invalidate all used points
                        foundNeighbor = true;
                    }
                }
                if (foundNeighbor) break; // restart on new current point
            }
            if (foundNeighbor) break; // restart on new current point
        }

        if (!foundNeighbor) break; // no more points in path...
    }

    // generate colored output
    cv::Mat output = cv::Mat::zeros(inputBGR.size(), CV_8UC1);

    // color the path...
    float nPoints = path.size();
    for (unsigned int i = 0; i < path.size(); ++i)
    {
        float posRel = i / nPoints;
        unsigned char val = 255 * posRel;
        output.at<unsigned char>(path[i]) = val;
    }

    // color code the path from blue to red
    cv::applyColorMap(output, output, cv::COLORMAP_JET);
    output.setTo(cv::Scalar::all(0), 255-mask);


    cv::imshow("output", output);
    cv::waitKey(0);
    return 0;
}

Giving this visualized result:

the points are in the path variable.

Here's pseudo-code:

0. search/select a starting point A
1. create a directed list P to construct the path
2. create a memory M to remember which points were already observerd
3. maintain current point C, initialized with A
4. while end not found:
    4.1. for each pixel in direct neighborhood (3x3 region without the center point) with coordinates (x,y)
        4.1.1. if the pixel is white and (x,y) is not yet in M:
            4.1.1.1.  add (x,y) to M
            4.1.1.2.  set C to (x,y)
            4.1.1.3.  add (x,y) to P
            4.1.1.4.  go on with 4.
        4.1.2. if no pixel is white or all the white pixel's coordinates are already in M
            4.1.2.1.  end is found

Answer 2

You can use the findContours function in cv2 ( cv2.findContours ). It can be a bit tricky if you're not used to pyopencv, but the code extract below uses the image from your question (with python2.7).

import cv2

im = cv2.imread('/home/kola/temp/serpentine.png')# change path as necessary
im2 = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY);
contours = cv2.findContours(im2,cv2.RETR_TREE,cv2.CHAIN_APPROX_NONE)
contour = contours[0][0]
# use this section if you want to animate the ploting of the contour
# WARNING - can be slow!!!
import matplotlib.pyplot as plt
plt.ion()
plt.gca().set_xlim(0,im2.shape[1])
plt.gca().set_ylim(im2.shape[0],0)
plt.gca().set_aspect('equal')
plt.ion()
for c in contour:
    plt.plot(c[0][0],c[0][1],'*')
    plt.pause(0.001)