【C++】細線化した画像のセグメント分割 ref: http://qiita.com/TatsuyaOGth/items/292317e9f5a5256098e7

file0.txt

P_{i, j} = (p_0, p_1, ... p_{j-1} ) \\
p_j = (x, y)

file1.cpp

#include <iostream>
#include <vector>
#include <array>

/// Output data type
typedef std::vector<std::array<int, 2> > Point2dArray;

/**
 *  @brief return point from index
 *
 *  @param i     Pixel index
 *  @param width Image width
 *
 *  @return Point (x, y)
 */
static std::array<int, 2> i2p(int i, int width)
{
    int x = i % width;
    int y = i / width;
    return {x, y};
}


/**
 *  @brief Divide branched chain.
 *
 *  @param pix            Input image pixels (unsigned char, single channel)
 *  @param width          Input image width
 *  @param height         Input image height
 *  @param dstPts         Output points array (vector<Point2dArray>)
 *  @param bNeighborType4 Input image type, true=4-neighbor, false=8-neighbor.
 *
 *  @return true=Process was succeed
 */
bool divideBranchedChain(const unsigned char* pix, const int width, const int height, std::vector<Point2dArray> *dstPts, bool bNeighborType4)
{
    std::vector<std::vector<std::array<int, 2> > > dstBuf;

    // offset: [x, y, direction], direction=0...7, 0=right, 1=upper right, ...7=lower right.
    std::vector<std::array<int, 3> > offset = {{1,0,0}, {1,-1,1}, {0,-1,2}, {-1,-1,3}, {-1,0,4}, {-1,1,5}, {0,1,6}, {1,1,7}};

    // segment: [current focused pixel index, neighbor pixel index, neighbor pixel direction]
    std::vector<std::array<int, 3> > neighbors;
    std::vector<std::array<int, 3> > nextSearchPixels;

    std::unique_ptr<char[]> tPix(new char[width * height]); // searched pix
    for (int i = 0; i < width * height; ++i) tPix[i] = 0;

    /// (function) find neighbor pixels, and update neighbors.
    auto findNeighbor = [&](int focusIdx, int ignoreIdx, int startDir)
    {
        neighbors.clear();
        for (int i = 0; i < offset.size(); ++i)
        {
            int ti = (i + startDir) % 8;
            if (bNeighborType4 && ti % 2 != 0) continue;

            int x = offset[ti][0] + (focusIdx % width);
            int y = offset[ti][1] + (focusIdx / width);
            int testIdx = y * width + x;

            // tests:
            if (testIdx != ignoreIdx                            && // is not ignore?
                (x >= 0 && x < width && y >= 0 && y < height)   && // is not outside?
                tPix[testIdx] == 0                              && // is not already searched pixel?
                pix[testIdx] > 0) // is white pixel
            {
                neighbors.push_back( {focusIdx, testIdx, offset[ti][2]} );
            }
        }
    };

    /// (function) get direction
    auto getDirection = [&offset, &width](int focusIdx, int targetIdx)
    {
        for (const auto& e : offset)
        {
            int x = e[0] + (focusIdx % width);
            int y = e[1] + (focusIdx / width);
            int testIdx = y * width + x;
            if (testIdx == targetIdx)
                return e[2];
        }
        throw "can't found direction."; // error
    };

    // scan
    for (int i = 0; i < width * height; ++i)
    {
        if (pix[i] > 0 && tPix[i] == 0)
        {
            int firstIdx = i;
            int focusIdx = firstIdx;
            int lastFocus = -1;
            int beginDir = 0;
            bool bFirst = true;
            int count = 0;

            try {
                // find begin point(s) on a segment
                while (count < width * height)
                {
                    findNeighbor(focusIdx, lastFocus, beginDir);

                    // tests
                    if (neighbors.empty())
                    {
                        if (bFirst)
                        {
                            // single pixel
                            dstBuf.push_back(Point2dArray(1, i2p(focusIdx, width)));
                            tPix[focusIdx] = 1;
                            break;
                        }
                        // end point
                        nextSearchPixels.push_back({focusIdx, lastFocus, getDirection(focusIdx, lastFocus)});
                        break;
                    }
                    else {
                        if (bFirst)
                        {
                            if (neighbors.size() == 1)
                            {
                                // first pixel is end point
                                nextSearchPixels.swap(neighbors);
                                break;
                            }
                        }
                        else {
                            if (neighbors.size() >= 2 || focusIdx == firstIdx)
                            {
                                // branched point, or repeated point
                                neighbors.push_back({focusIdx, lastFocus, getDirection(focusIdx, lastFocus)});
                                nextSearchPixels.swap(neighbors);
                                break;
                            }
                        }
                    }

                    // continue
                    lastFocus = focusIdx;
                    focusIdx = neighbors[0][1];
                    beginDir = neighbors[0][2];
                    bFirst = false;
                    ++count;
                }
                if (count == width * height - 1)
                {
                    throw "endless loop exception";
                }

                // pick up points on the chains.
                while (nextSearchPixels.empty() == false)
                {
                    bFirst = true;
                    lastFocus = -1;
                    auto it = nextSearchPixels.begin();
                    firstIdx = (*it)[0];
                    focusIdx = firstIdx;
                    beginDir = (*it)[2];
                    nextSearchPixels.erase(it);
                    count = 0;
                    Point2dArray chainPts;

                    do {
                        findNeighbor(focusIdx, lastFocus, beginDir);

                        // tests
                        if (neighbors.empty() || (bFirst == false && focusIdx == firstIdx))
                        {
                            break;
                        }
                        else if (bFirst == false && neighbors.size() >= 2)
                        {
                            std::copy(begin(neighbors), end(neighbors), back_inserter(nextSearchPixels));
                            break;
                        }

                        // continue

                        if (bFirst)
                        {
                            chainPts.push_back(i2p(focusIdx, width));
                            tPix[focusIdx] = 1;
                        }

                        lastFocus = focusIdx;
                        focusIdx = neighbors[0][1];
                        beginDir = neighbors[0][2];
                        bFirst = false;

                        chainPts.push_back(i2p(focusIdx, width));
                        tPix[focusIdx] = 1;
                    }
                    while (count < width * height);
                    if (count == width * height - 1)
                    {
                        throw "endless loop exception";
                    }

                    if (chainPts.empty() == false) dstBuf.push_back(chainPts);
                }
            }
            catch (const char* e)
            {
                std::cout << "[exception] " << e << std::endl;
                return false;
            }
        }
    }

    dstPts->swap(dstBuf);
    return true;
}