Zhang-Suen Thinning Algorithm

Zhang-Suen Thinning Algorithm은 이진 영상에서 객체의 형태와 연결성을 유지하면서 한 픽셀 두께의 skeleton을 추출하기 위한 대표적인 thinning 알고리즘이다. 1984년 T. Y. Zhang과 C. Y. Suen이 제안하였으며, 계산이 간단하고 효율적이어서 문자 인식(OCR), 패턴 인식, 지문 분석 등 다양한 영상 처리 분야에서 널리 사용된다.

알고리즘은 객체의 경계 픽셀을 반복적으로 제거하여 객체를 점차 가늘게 만든다. 각 iteration은 두 개의 sub-iteration으로 구성되며, 각 부단계에서는 주변 8개 이웃 픽셀의 연결 상태를 검사하여 제거 가능한 경계 픽셀을 판별한다. 이때 픽셀을 제거하더라도 객체의 connectivity가 유지되고 endpoint가 삭제되지 않도록 여러 조건을 동시에 만족하는 경우에만 제거를 수행한다.

더 이상 제거할 수 있는 픽셀이 없으면 알고리즘을 종료하며, 결과적으로 원래 객체의 topology를 유지하는 한 픽셀 두께의 skeleton을 얻는다. Zhang-Suen Thinning Algorithm은 구현이 간단하고 계산 속도가 빠르다는 장점이 있지만, 생성된 skeleton이 항상 기하학적인 중심축(medial axis)과 정확히 일치하는 것은 아니며, 경계의 작은 잡음에 민감할 수 있다는 한계가 있다.

Rosenfeld Thinning Algorithm은 이진 영상에서 객체의 연결성(connectivity) 을 유지하면서 불필요한 경계 픽셀을 반복적으로 제거하여 한 픽셀 두께의 골격(skeleton) 을 추출하는 대표적인 세선화(thinning) 알고리즘이다. Azriel Rosenfeld가 제안한 초기의 thinning 알고리즘 중 하나로, 이후 Zhang-Suen, Guo-Hall 등의 알고리즘의 기반이 되었다.

알고리즘은 객체의 경계 픽셀을 반복적으로 검사하여, 해당 픽셀을 제거해도 객체가 분리되지 않고 끝점(endpoint)이 사라지지 않는 경우에만 픽셀을 삭제한다. 이러한 과정을 여러 방향에 대해 반복 수행함으로써 객체의 형태를 점차 가늘게 만들며, 더 이상 제거할 수 있는 픽셀이 없으면 알고리즘을 종료한다.

Rosenfeld Thinning Algorithm은 객체의 위상(topology) 과 연결성을 유지하면서 중심선을 추출할 수 있다는 장점이 있으나, 반복 횟수가 많아 계산량이 비교적 크고, 생성된 skeleton이 항상 기하학적인 중심축(medial axis)과 일치하는 것은 아니다. 그럼에도 불구하고 세선화 알고리즘의 기본 개념을 확립한 중요한 방법으로 평가되며, 문자 인식(OCR), 패턴 인식, 형태 분석 등의 분야에서 활용된다.

비교: 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