Zhang-Suen Thinning Algorithm

비교: Rosenfeld Algorithm(Graphics Gem IV)

Neighborhood Map;

[0 1 2]

[7 8 3]

[6 5 4]

int Thinning_2pass(BYTE *image, int w, int h) {
    const int xmax = w - 1, ymax = h - 1;
    const int nn[9] = {-w - 1,- w, -w + 1, 1, w + 1, w, w - 1, -1, 0};//clockwise;
    const BYTE FG = 255, BG = 0;
    bool *flag = new bool [w * h];
    int pass = 0, ok = 0;
    int nb[9];
    while (!ok) {
        ok = 1; pass = (pass + 1) % 2;
        for (int i = w * h; i-->0; ) flag[i] = false;
        for (int y = 1, pos = w; y < ymax; y++) {
            pos++;//x=0;
            for (int x = 1; x < xmax; x++, pos++) {
                if (image[pos] == FG) { //fg;
                    // condition 1; 
                    int count = 0;
                    for (int k = 0; k < 8; k++) 
                        if (image[pos + nn[k]] == FG) count++;
                    if (count >= 2 && count <= 6) {
                        for (int k = 0; k < 8; k++) nb[k] = image[pos + nn[k]];
                        nb[8] = nb[0]; //cyclic;
                        // condition 2;
                        int trans = 0;
                        for (int k = 0; k < 8; k++)
                            if (nb[k] == BG && nb[k + 1] == FG) trans++;
                        if (trans == 1) {
                            // condition3: top&&left=bg || bot=bg || right=bg
                            if (pass == 0 && (nb[3] == BG || nb[5] == BG ||	
                                (nb[1] == BG && nb[7] == BG))) {
                                    flag[pos] = true; ok = 0;
                            } else { // condition4: bot&&right=bg || top=bg || left=bg 
                                if (pass == 1 && (nb[1] == BG || nb[7] == BG ||	
                                    (nb[3] == BG && nb[5] == BG))) {
                                        flag[pos] = true; ok = 0;
                                }
                            }
                        }
                    }//(2<=count<=6);
                }
            }//for_x;
            pos++;//x = w - 1 skip;
        } //for_y;
        // remove flaged pixels;
        for (int y = 1, pos = w; y < ymax; y++) {
            pos++;//x = 0;
            for (int x = 1; x < xmax; x++, pos++) 
                if (flag[pos]) image[pos] = BG;
            pos++; //x=w-1;
        }
    }
    delete [] flag;
    return 1;
}

Zhan-Suen_algorithm.pdf

0.21MB