細線化

　今更細線化もないだろうとは思うのですが，必要になったので実装してみた．参考にしたのはOpenCV/細線化なんですが，一応これの参考文献にもあたっています．

　アルゴリズムは同じですが，実装はちょっと工夫してみた．OpenCVだから速いかというと全然そんなことはなくて，自分の実装の法が100倍ぐらい速くなりました．もちろん画像の中身依存なんですけどね．肝は，画像全体から削減可能な画素を探すのではなくて，ランレングスで黒画素のみを保持しておいて検査するところ．

　というわけで，コアの部分だけ晒しておきます*1．半分ぐらいはランレングスの管理が占めていますね．今の設定では8回に1回ランレングスを再構築しています(cnt%8==0の部分)．

　今時Cでゴリゴリ画像処理を書いている人もいないのかなぁ．というか，基本ライブラリにOpenCVを使っていないことの方が問題か．

struct runlen_s
{
    int sx, ex, y, ln;
    struct runlen_s *next;
};
typedef struct runlen_s runlen_t;

runlen_t *new_runlen(image_t *img)
{
    runlen_t *rl;
    int ri;
    rl = malloc(sizeof(runlen_t)*(px_ys(img)+1));
    for (ri = 0; ri < px_ys(img); ri++) {
        rl[ri].sx = 0;
        rl[ri].ex = px_xs(img);
        rl[ri].y = ri;
    }
    rl[ri].sx = -1;
    return rl;
}

runlen_t *get_runlen(image_t *img, runlen_t *rl_)
{
    runlen_t *rl = NULL;
    int ri, ri_, rn, x, y, onfg;
    if ((!img) || (!rl_)) { error("get_runlen: img/rl is %X/%X.", img, rl); }
    for (ri = ri_ = rn = 0; 0 <= rl_[ri_].sx; ri_++) {
        for (onfg = 0, y = rl_[ri_].y, x = rl_[ri_].sx; x < rl_[ri_].ex; x++) {
            if (onfg == 0 && px_(img,x,y) == 1) {
                if (rn <= ri) {
                    rn += 1000;
                    rl = (runlen_t*)realloc(rl, sizeof(runlen_t)*rn);
                    if (!rl) { error("runlen realloc error : %d.", rn); }
                }
                rl[ri].sx = x; rl[ri].y = y;
                onfg = 1;
            }
            else if (onfg != 0 && px_(img,x,y) != 1) {
                rl[ri++].ex = x;
                onfg = 0;
            }
        }
        if (onfg != 0) {
            rl[ri++].ex = x;
        }
    }
    rl[ri].sx = -1;
    return rl;
}

int get_runlen_num(runlen_t *rl)
{
    int ri;
    if (!rl) { error("get_runlen_num: rl is NULL."); }
    for (ri = 0; 0 <= rl[ri].sx; ri++) ; // do nothing
    return ri;
}

image_t *thinning(image_t *img)
{
    image_t *mask;
    int fg, bg, x, y, sum, ker, cnt;
    int ri, rn;
    runlen_t *rl, *rl_;
    mask = image_filled2(img, 0);
    int xo[] = {-1, 0,-1,+1, 0, -1, 0,+1,-1, 0,  0,+1,+1,-1, 0, +1,+1,+1,-1,-1,
                 0,+1,+1,-1, 0, -1,+1, 0,+1, 0, -1,-1, 0,+1, 0, -1,-1,-1,+1,+1};               
    int yo[] = {-1,-1, 0, 0,+1, -1,-1,-1,+1,+1, -1,-1, 0, 0,+1, -1, 0,+1,-1, 0,
                +1,+1, 0, 0,-1, +1,+1,+1,-1,-1,  0,+1,+1, 0,-1, -1, 0,+1, 0,+1};
    int x0, x1, x2, x3, x4, y0, y1, y2, y3, y4;

    // binarization foreground:1 background:0
    img = image_dup(img); image_forall(img,x,y) { px(img,x,y) = (px(img,x,y)<128 ? 1 : 0); }

    rl = new_runlen(img);
    ker = sum = cnt = 0;
    while(1) {
        if ((ker==0) && (cnt%8==0)) {
            rl_ = get_runlen(img, rl); free(rl); rl = rl_;
            rn = get_runlen_num(rl);
        }
        x0=xo[ker*5+0]; x1=xo[ker*5+1]; x2=xo[ker*5+2]; x3=xo[ker*5+3]; x4=xo[ker*5+4];
        y0=yo[ker*5+0]; y1=yo[ker*5+1]; y2=yo[ker*5+2]; y3=yo[ker*5+3]; y4=yo[ker*5+4];
        for (ri = 0; ri < rn; ri++) for (y = rl[ri].y, x = rl[ri].sx; x < rl[ri].ex; x++) {
            if (px_(img,x,y) == 0) { continue; }
            fg = (px0(img,x+x0,y+y0)+px0(img,x+x1,y+y1)+px0(img,x+x2,y+y2) == 0);
            bg = (px0(img,x+x3,y+y3)+px0(img,x+x4,y+y4) == 2);
            if (fg && bg) { px_(mask,x,y) = 1; sum++; }
        }
        for (ri = 0; ri < rn; ri++) for (y = rl[ri].y, x = rl[ri].sx; x < rl[ri].ex; x++) {
            if (px_(mask,x,y)) {
                px_(img,x,y) = px_(mask,x,y) = 0;
            }
        }
        ker = (ker+1)%8;
        if (ker == 0) {
            if (sum) { sum = 0; cnt++; }
            else     { break; }
        }
    } 
    image_free(mask);
    image_forall(img,x,y) { px(img,x,y) = px(img,x,y) ? 0 : 255; }
    return img;
}

*1:自作ライブラリは該当部分を持ってくるのが面倒