hilditch.cpp

细化算法Hilditch 有简要地说明 效果还不错

/*
模板为： 
                                                P4  P3  P2 
                                                P5  P0  P1 
                                                P6  P7  P8 
condition1:当前点P0为1 
condition2:P1、P3、P5、P7不都为非零(1或-1) 
condition3:P1、P2……P8中的非零(1或-1)个数大于等于2个 
condition4:P1、P2……P8中为1的个数大于等于1个 
condition5: 
condition6: 
满足上面6个条件的P0点标记为2，整幅图循环完一次将标记为2的像素标记为0，再重新对整幅图进行相同的操作，直到没有标记为2的像素为止。

author: shugangwang
date: 2008-03-07
*/

int Hilditch(BYTE *pBuf, int width, int height) 
{ 
    int i, j, k, copy, sum, add; 
    BYTE *P; 
    int offSet[9][2] = {{0,0},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1}}; 
    int N[9]; 
    int odd[4] = {1, 3, 5, 7}; 
    int ii, jj; 
    int counter; 

    P = pBuf; 
#define P(i,j) P[(j)*width+(i)] 

    do{ 
        counter = 0; 
        for (j=1; j<height-1; j++) 
        for (i=1; i<width-1; i++) 
        { 
            if (1 != P(i,j)) continue;//condition 1 

            for (k=0; k<9; k++) 
            { 
                N[k] = 0; 
                ii = i+offSet[k][0]; 
                jj = j+offSet[k][1]; 

                if (1 == P(ii,jj)) 
                    N[k] = 1; 
                else if (2 == P(ii,jj)) 
                    N[k] = -1; 
            } 

            sum = 0; 
            for (k=0; k<4; k++) 
                sum = sum+1-abs(N[odd[k]]); 

            if (sum == 0) continue;//condition 2 

            sum = 0; 
            for (k=1; k<=8; k++) 
                sum = sum+abs(N[k]); 

            if (sum <= 1) continue;//condition 3 

            sum = 0; 
            for (k=1; k<=8; k++) 
                if (1 == N[k]) sum++; 

            if (0 == sum) continue;////condition 4 

            sum = 0; 
            sum += abs(N[1])-abs(N[1])*abs(N[2])*abs(N[3]); 
            sum += abs(N[3])-abs(N[3])*abs(N[4])*abs(N[5]); 
            sum += abs(N[5])-abs(N[5])*abs(N[6])*abs(N[7]); 
            sum += abs(N[7])-abs(N[7])*abs(N[8])*abs(N[1]); 

            if (1 != sum) continue;//condition 5 

            sum = 0; 
            for (k=1; k<=8; k++) 
            { 
                if (N[k] != -1) 
                    sum++; 
                else 
                { 
                    copy = N[k]; 
                    N[k] = 0; 
                    add = 0; 
                    add += abs(N[1])-abs(N[1])*abs(N[2])*abs(N[3]); 
                    add += abs(N[3])-abs(N[3])*abs(N[4])*abs(N[5]); 
                    add += abs(N[5])-abs(N[5])*abs(N[6])*abs(N[7]); 
                    add += abs(N[7])-abs(N[7])*abs(N[8])*abs(N[1]); 

                    if (1 == add) sum++; 

                    N[k] = copy; 
                } 
            } 

            if (sum != 8) continue;//condition 6 

            P(i,j) = 2; 
            counter++; 
        }//end: for (i=1; i<width-1; i++) 

        if (counter != 0) 
        { 
            for (j=0; j<height; j++) 
            for (i=0; i<width; i++) 
                if (2 == P(i,j)) P(i,j) = 0; 
        } 
    }while(counter != 0); 

#undef P 

    return 0; 
}