【C++】画像の細線化処理（Hilditchの方法） ref: http://qiita.com/TatsuyaOGth/items/45965e1632f41f3eb139

file0.txt

N_8 = \left\{ P_1, P_2, P_3, P_4, P_5, P_6, P_7, P_8 \right\}

file1.txt

N_{odd} = \left\{P_1, P_3, P_5, P_7 \right\}

file2.txt

B(P_0) = 1

file3.txt

\sum_{k \ni N_{odd}} \left\{ 1-|B(P_k)| \right\} \geq 1

file4.txt

\sum_{k \ni N_8} |B(P_k)| \geq 2

file5.txt

\sum_{k \ni N_8} C_k \geq 1, C_k = \left\{ \begin{array}{} 1 & for & B(P_k) = 1 \\ 0 & for & B(P_k) \neq 1 \end{array} \right\}

file6.txt

N^{8}_{C} (P_0) = 1, WHERE, N^{8}_C (P_0) = \sum_{k \ni N_{odd}} \left\{D(P_k)-D(P_k) D(P_{k+1}) D(P_{k+2}) \right\}

file7.txt

(i) \hspace{10pt} B(P_n) \neq -1 \\
(ii) \hspace{10pt} B(P_n) = 0, THAN, N^{8}_{C} = 1

file8.cpp

/**
 *  @brief Thinning (Hilditxh method)
 *
 *  @param src Source image pixels pointer (depth: 8UC)
 *  @param dst Output image pixels pointer (dspth: 8UC)
 *  @param w   Source image width
 *  @param h   Source image height
 */
void hilditchThinning(const unsigned char* src, unsigned char* dst, int w, int h)
{
    int offset[9][2] = {{0,0}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}, {0,1}, {1,1}};
    int nOdd[4] = {1, 3, 5, 7};
    int b[9];
    int px, py;
    bitset<6> condition;

    memcpy(dst, src, w * h);

    int path = 1;
    int counter;

    auto funcNc8 = [&nOdd](int *b)
    {
        array<int, 10> d;
        int j;
        int sum = 0;

        for (int i = 0; i <= 9; ++i)
        {
            j = i;
            if (i == 9) j = 1;
            if (abs( *(b + j)) == 1)
                d[i] = 1;
            else
                d[i] = 0;
        }

        for (int i = 0; i < 4; ++i)
        {
            j = nOdd[i];
            sum = sum + d[j] - d[j] * d[j+1] * d[j+2];
        }

        return sum;
    };

    cout << "start thinning " << endl;
    clock_t beginTime = clock();

    do {
        cout << ".";
        counter = 0;

        for (int y = 0; y < h; ++y)
        {
            for (int x = 0; x < w; ++x)
            {
                for (int i = 0; i < 9; ++i)
                {
                    b[i] = 0;
                    px = x + offset[i][0];
                    py = y + offset[i][1];
                    if (px >= 0 && px < w && py >= 0 && py < h)
                    {
                        int idx = w * py + px;
                        if (dst[idx] == 255)
                        {
                            b[i] = 1;
                        }
                        else if (dst[idx] == 127)
                        {
                            b[i] = -1;
                        }
                    }
                }

                condition.reset();

                // Condition 1
                if (b[0] == 1) condition.set(0, true);

                // Condition 2
                int sum = 0;
                for (int i = 0; i < 4; ++i)
                {
                    sum = sum + 1 - abs(b[nOdd[i]]);
                }
                if (sum >= 1) condition.set(1, true);

                // Condition 3
                sum = 0;
                for (int i = 1; i <= 8; ++i)
                {
                    sum = sum + abs(b[i]);
                }
                if (sum >= 2) condition.set(2, true);

                // Condition 4
                sum = 0;
                for (int i = 1; i <= 8; ++i)
                {
                    if (b[i] == 1) ++sum;
                }
                if (sum >= 1) condition.set(3, true);

                // Condition 5
                if (funcNc8(b) == 1) condition.set(4, true);

                // Condition 6
                sum = 0;
                for (int i = 1; i <= 8; ++i)
                {
                    if (b[i] != -1)
                    {
                        ++sum;
                    }
                    else {
                        int copy = b[i];
                        b[i] = 0;
                        if (funcNc8(b) == 1) ++sum;
                        b[i] = copy;
                    }
                }
                if (sum == 8) condition.set(5, true);

                // Final judgement
                if (condition.all())
                {
                    int idx = y * w + x;
                    dst[idx] = 127;
                    ++counter;
                }
            }
        }

        if (counter != 0)
        {
            for (int y = 0; y < h; ++y)
            {
                for (int x = 0; x < w; ++x)
                {
                    int idx = y * w + x;
                    if (dst[idx] == 127)
                    {
                        dst[idx] = 0;
                    }
                }
            }
        }

        ++path;
    }
    while (counter != 0);

    clock_t endTime = clock() - beginTime;
    cout << " Done! Time: " << (double)(endTime) / CLOCKS_PER_SEC << " sec, Num Path: " << path << endl;
}