[画像処理]C言語で理解するラベリング処理アルゴリズム

はじめに

OpenCVなどで気軽に利用できるラベリング処理ですが、どのようなアルゴリズムで動いているのかはあまり知られていないかもしれません。
アルゴリズム力を鍛えるという意味でもラベリング処理の実装は良い課題になると思われます。

今回、4近傍ラベリング処理を実装してみたので解説してみたいと思います。
(私が調べた限り、ラベリング処理アルゴリズムは解説記事が少なく、ソースコードも見つかりませんでした。したがって、私の書いたコードが正しいのか確かめられないのが正直なところです。)

一応テストケースを自前で用意し、コードの信頼性をチェックしておりますが、絶対的なものとは言えませんので悪しからず。

目次

• 環境
• 実行例
• 考え方
  • ラベリング処理の目的
  • 4近傍・8近傍の違い
  • 画像の二値化
  • ラベル値を割り当てる
  • ルックアップテーブルの更新
  • 衝突処理
  • ラベル値の圧縮
  • テストケース
• ソースコード
• 終わりに

環境

• C(Gcc6.3)
• CodeChefで実行

実行例

以下は地球の画像に4近傍ラベリング処理を施した結果です。(左が元画像、右が出力txtファイル)

拡大すると確認できますが、ラベル値が割り当てられたtxtファイルです。

以下の画像はラベリング処理で求めた連結成分ごとに色を塗った塗り絵画像です。(プログラムで生成しました)

以下同様です。(省略)

考え方

C言語への理解はある程度必要になりますが、ポインタ・構造体・メモリ管理くらいの知識で問題ありません。

ラベリング処理の目的

ラベリング処理とは、二値化画像の繋がっている部分(連結成分)ごとに番号を割り当てていく処理のことです。
主に、連結成分の特徴量を求めて欠品検査などに使われるようです。

4近傍・8近傍の違い

では、画素が連結しているかどうかをどのように判断するのでしょうか。
4近傍と8近傍という二つの判断基準があります。

4近傍・・・着目画素の上下左右に存在する画素が同じ値であれば、連結している

8近傍・・・4近傍の考え方に加え、斜め方向に存在する画素が同じ値であれば、連結している

画像の二値化

そもそも二値化とは何かという人もいると思うので触れておきます。
端的に言うと、普通の色付き(RGB)画像を白黒画像にするというものです。

大味に説明すると、
一般に見かけるラスタ画像は細かいピクセルから構成されていて、ピクセルごとに色情報などが割り当てられています。
その色情報(0~255)に対し閾値を決定し、閾値よりも小さい色情報を持つピクセルに0を、閾値よりも大きい色情報を持つピクセルに255を割り当てるというのが画像の二値化処理となります。

今回、タイムスタンプをシード値として乱数を生成し、その乱数に従ってダブルポインタに0~255の値を割り当てます。
その後、事前に指定した閾値(THRESHOLD)より大きいピクセルにNONTARGET_PIXEL(=0)を割り当て、小さいピクセルにTARGET_PIXEL(=1)を割り当て二値化しています。

また、プログラムを簡潔にするために、画像を表現するダブルポインタ(**pixel_map)に外枠を1ピクセル分用意しています。

ラベル値を割り当てる

では、ラベル値を割り当ててきましょう。
ラベル値を割り当てていくには、ラスタスキャンというものを行います。
ラスタスキャンとは、画像の上から順に左から右にかけて走査していくものです。

ラスタスキャンで着目画素を更新していきます。

ラベルを割り当てたいのは着目画素がTARGET_PIXEL(二値化したときの黒色の画素)の場合に限るので、
それ以外の場合、
つまり着目画素がNONTARGET_PIXEL(二値化したときの白色の画素)またはOUTSPACE(外枠)の場合については、スキップします。

着目画素を定めたら、次に着目画素の上と左の画素を調べます。
上と左の画素のラベル値をもとに着目画素のラベル値を決定します。

上と左の画素のラベル値が、どちらも割り当てられていない場合(NONTARGET_PIXEL=0 or OUTSPACE=0)、
存在するラベル値の中で一番大きいラベル値+1のラベル値を着目画素に割り当てます。

上と左の画素のどちらかにラベル値が割り当てられていた場合、小さいほうのラベル値を着目画素に割り当てます。

ここで、ルックアップテーブルという聞きなれない単語が出てきましたね。
ルックアップテーブルについては次の項で説明します。

ルックアップテーブルの更新

ルックアップテーブルの更新は、ラベリング処理でかなり重要な部分を占めると思います。
ルックアップテーブルを作成する理由は、ラベルの衝突を防ぐことにあります。
ラベルの衝突とは、値の異なるラベル同士が同じ連結成分の中に存在していることです。

上の画像では、ラベル値1とラベル値3が衝突しているのが分かります。
しかし、先ほど説明した方法でラベルを割り振っていくと必然的にこうなってしまいます。

この問題を解決するのがルックアップテーブルの存在です。
着目画素の上と左の画素のラベル値の大きいほうに対して、小さいほうのラベル値をルックアップテーブルに更新します。

そうすると、先ほどの衝突例は以下のように解決できます。

ルックアップテーブルの値を手掛かりにして、ラベル値3の画素をラベル値1に更新して衝突を回避していることが分かります。

基本的に、このような考え方でルックアップテーブルを更新していくことになります。
では、もうひと工夫必要になる場合について考えていきましょう。
以下の例では、衝突回避に失敗しています。

ラベル値２の更新が上手くいっていないようです。
このような状況を打破するために、逆ラスタスキャンでルックアップテーブルを更新します。
逆ラスタスキャンでは、着目画素の下と右に注目することに注意してください。

ルックアップテーブルを更新し終えたら、次はルックアップテーブルを基にラベル値の振りなおしをしていきましょう。

衝突処理

あとは、ルックアップテーブルをもとにラベル値を更新していくだけですね。
ルックアップテーブルを以下のように辿ってラベル値を更新していきます。

1. 着目画素のラベル値をNとすると、ルックアップテーブルのN番目にアクセスします。

2. ルックアップテーブルのN番目に格納されている値をMとすると、NとMが等しくない場合、N番目の値は更新されていると考えられます。

3. 次に、M番目のルックアップテーブルにアクセスします。M番目に格納されている値がMと等しい場合、M番目の値は更新されていないので、着目画素にMを挿入して終了となります。

4. M番目に格納されている値がMと等しくない場合は、2番目に戻り繰り返します。

これをラスタスキャンし、ラベルの割り当てられている全画素について行います。

ラベル値の圧縮

次にラベル値の圧縮を行います。
ラベル値の圧縮とは、連結成分ごとに不連続な間隔で割り当てられているラベル値を、1から連番で割り当てる操作のことです。(私が勝手に名付けました)

圧縮配列は、ルックアップテーブルのデータの格納番目とデータの値が等しい時に、圧縮配列にデータを追加していくことで作成できます。

圧縮をピクセルマップに適用するには、ラスタスキャンをし、着目画素のラベル値Nと等しい圧縮配列の値Nを見つけて、着目画素のラベル値にNを持つ圧縮配列番目の数字を挿入します。

テストケース

最後に、出力された結果が正しいかテストを行う関数を用意しましょう。

まずは、データが欠損していないかチェックします。
これは最初のターゲットピクセルの数と、処理後のターゲットピクセルの数が等しいかどうかでチェックすることが出来ますね。

次に、衝突が発生していないかチェックします。
これはラスタスキャンで全ての着目画素ごとに、4近傍に自分と異なるラベル値を持つ画素が存在しているかどうかを確認すれば出来ます。

以上がテストケースの内容になります。

ソースコード

ソースコードや、テストケース結果はGitHubの方でも共有しておきますので、ご参考にどうぞ。

/*
四近傍ラベリングアルゴリズム
Ito Hajime
2020/07/19
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TARGET_PIXEL 1
#define NONTARGET_PIXEL 0
#define OUTSPACE NONTARGET_PIXEL
#define THRESHOLD_BRIGHTNESS 128
#define MAX_NUM 50000 /* この大きさで処理速度が大幅に変わる。適切な大きさにする必要あり。 */
#define EXCEPTION MAX_NUM + 1
#define LABEL_MAX_SIZE MAX_NUM / 2

typedef struct picture
{
    unsigned int **pixel_map;
    unsigned int row_size;
    unsigned int col_size;
    unsigned int target_pixel_sum;
} Picture;

void print_picture(Picture p);
void init_picture(Picture *p, unsigned int h, unsigned int w);
void init_lookup_table(unsigned int t[MAX_NUM][1]);
void push_lookup_table(unsigned int t[MAX_NUM][1], unsigned int index, unsigned int value);
void update_lookup_table(unsigned int t[MAX_NUM][1], unsigned int top_label_val, unsigned int left_label_val);
unsigned int get_lookup_table(unsigned int t[MAX_NUM][1], unsigned int index);
void resolve_conflict(Picture *p, unsigned int t[MAX_NUM][1], unsigned int compression_label[LABEL_MAX_SIZE]);
void compress_label(Picture *p, unsigned int compression_label[LABEL_MAX_SIZE], unsigned int lookup_table[MAX_NUM][1]);
void labeling(Picture *p, unsigned int t[MAX_NUM][1], unsigned int compression_label[LABEL_MAX_SIZE]);
void test_case(Picture p);
void FREE(Picture *p);

int main(void)
{
    char buf[MAX_NUM] = {0};
    unsigned int lookup_table[MAX_NUM][1] = {{0}};
    unsigned int height = 0;
    unsigned int width = 0;
    unsigned int compression_label[LABEL_MAX_SIZE] = {NONTARGET_PIXEL};
    unsigned int testcase_count = 0;

    Picture picture = {0, 0, 0};

    fgets(buf, sizeof(buf), stdin);
    sscanf(buf, "%u %u\n", &height, &width);

    for (testcase_count = 0; testcase_count < 1; testcase_count++)
    {
        srand((unsigned int)time(NULL));
        printf("time: %u\n", (unsigned int)time(NULL));
        init_picture(&picture, height, width);
        init_lookup_table(lookup_table);
        labeling(&picture, lookup_table, compression_label);
        compress_label(&picture, compression_label, lookup_table);
        test_case(picture);
        //print_picture(picture);
        FREE(&picture);
    }
    return 0;
}

/* pictureをコンソールに表示する */
void print_picture(Picture p)
{
    unsigned int r = 0;
    unsigned int c = 0;

    for (r = 0; r < p.row_size; r++)
    {
        printf("\n");
        for (c = 0; c < p.col_size; c++)
        {
            if ((OUTSPACE == p.pixel_map[r][c] || NONTARGET_PIXEL == p.pixel_map[r][c]))
                printf("  ..  ");
            else
                printf(" %4u ", p.pixel_map[r][c]);
        }
    }
    printf("\n\n");
}

/* pictureの初期化関数 */
void init_picture(Picture *p, unsigned int h, unsigned int w)
{
    unsigned int r = 0;
    unsigned int c = 0;
    unsigned char brightness = 0;
    /* 上下左右に余白を持たせておく */
    p->row_size = h + 2;
    p->col_size = w + 2;
    /* target_pixel_sumの初期化 */
    p->target_pixel_sum = 0;

    /* メモリ割り当て */
    p->pixel_map = (unsigned int **)malloc(p->row_size * sizeof(unsigned int *));
    for (r = 0; r < p->row_size; r++)
        p->pixel_map[r] = (unsigned int *)malloc(p->col_size * sizeof(unsigned int));

    /* 全ての画素にOUTSPACEを割り当てる */
    for (r = 0; r < p->row_size; r++)
        for (c = 0; c < p->col_size; c++)
            p->pixel_map[r][c] = OUTSPACE;

    /* ランダムに画素値を決定し、閾値を基に二値化する */
    for (r = 1; r < p->row_size - 1; r++)
        for (c = 1; c < p->col_size - 1; c++)
        {
            brightness = (rand() % 256);
            if (brightness <= THRESHOLD_BRIGHTNESS)
            {
                p->pixel_map[r][c] = TARGET_PIXEL;
                p->target_pixel_sum += 1;
            }
            else
            {
                p->pixel_map[r][c] = NONTARGET_PIXEL;
            }
        }
}

/* loolup_tableの初期化関数 */
void init_lookup_table(unsigned int t[MAX_NUM][1])
{
    /* lookup_tableの初期化 */
    unsigned int l = 0;
    for (l = 0; l < MAX_NUM; l++)
    {
        t[l][0] = EXCEPTION;
    }
    t[0][0] = MAX_NUM;
}

/* lookup_tableに値を挿入する関数 */
void push_lookup_table(unsigned int t[MAX_NUM][1], unsigned int index, unsigned int value)
{
    /* 例外処理 */
    if (MAX_NUM < index)
    {
        fprintf(stderr, "エラー：indexの値が%u、valueの値が%uです。データの挿入に失敗しました。\n", index, value);
        return;
    }

    if (MAX_NUM == index)
        return;

    /* lookup_tableに値を挿入する(0番目は使わないのでスキップする) */
    if (0 == index)
        t[0][0] = MAX_NUM;
    else
        t[index][0] = value;
}

/* 着目画素の上・左にある画素のラベル値が、着目画素のラベル値よりも大きい場合にlookup_tableを更新する */
void update_lookup_table(unsigned int t[MAX_NUM][1], unsigned int top_label_val, unsigned int left_label_val)
{
    unsigned int max_label_val = 0; /* 着目画素のラベル値と比べて一番大きい値 */
    unsigned int min_label_val = 0; /* 着目画素のラベル値と比べて一番小さい値 */
    unsigned int pat = 0;
    unsigned int update_label_val = 0;

    /* NONTARGET_PIXELやOUTSPACEを無視して最大値と最小値を求める */
    /* 両方に適切なデータが存在あると想定した場合 */
    if (top_label_val > left_label_val)
    {
        max_label_val = top_label_val;
        min_label_val = left_label_val;
    }

    if (left_label_val > top_label_val)
    {
        max_label_val = left_label_val;
        min_label_val = top_label_val;
    }

    /* 片方のみに適切なデータが存在あると想定した場合(優先) */
    if (MAX_NUM == top_label_val)
    {
        /* top_pixel_valがMAX_NUMなら、leftはMAX_NUM以外のデータが入っている */
        max_label_val = left_label_val;
        min_label_val = left_label_val;
    }

    if (MAX_NUM == left_label_val) //(NONTARGET_PIXEL == left_label_val || OUTSPACE == left_label_val)
    {
        /* left_pixel_valがMAX_NUMなら、topはMAX_NUM以外のデータが入っている */
        max_label_val = top_label_val;
        min_label_val = top_label_val;
    }

    /* 大きいラベル値のlookup_tableの値を辿って、適切な位置のlookup_tableの値を更新する */
    /* 例) 適切な値の更新 */
    /* lookup_table */
    /* 1 -> 1 */
    /* 2 -> 2 */
    /* 3 -> 2 */
    /* 4 -> 3 */
    /* max_pixel_val 4  */
    /* min_pixel_val 1 */
    /* 以上が得られたとき、lookup_tableは2->1と更新する */
    /* ここで、2がupdate_label_valである。 */
    update_label_val = max_label_val;

    for (pat = MAX_NUM; pat > 0; pat--)
    {
        if (get_lookup_table(t, update_label_val) < update_label_val)
            update_label_val = get_lookup_table(t, update_label_val); /* 辿るべき、lookup_tableの手掛かりでupdate_label_valを更新する */

        if (get_lookup_table(t, update_label_val) == update_label_val)
        {
            if (get_lookup_table(t, update_label_val) > min_label_val)
                push_lookup_table(t, update_label_val, min_label_val); /* 更新 */
            break;                                                     /* 終了 */
        }
    }
}

/* lookup_tableの値を取得する関数 */
unsigned int get_lookup_table(unsigned int t[MAX_NUM][1], unsigned int index)
{
    /* 例外処理 */
    if (MAX_NUM < index)
    {
        fprintf(stderr, "エラー：indexの値が%uです。データの取得に失敗しました。\n", index);
        return 0;
    }

    if (MAX_NUM == index)
        return 0;

    /* lookup_tableに値を返す(0番目は使わないのでスキップする) */
    return t[index][0];
}

/* 衝突処理(繋がっているけどラベル値が違うピクセルに適切な値を割り当てる)を行う関数 */
void resolve_conflict(Picture *p, unsigned int t[MAX_NUM][1], unsigned int compression_label[LABEL_MAX_SIZE])
{
    unsigned int r = 1;
    unsigned int c = 1;
    unsigned int pat = 0;
    unsigned int update_label_val = 0;

    /* 衝突処理用ラスタスキャン */
    for (r = 1; r < p->row_size - 1; r++)
        for (c = 1; c < p->col_size - 1; c++)
        {
            if ((NONTARGET_PIXEL == p->pixel_map[r][c] || OUTSPACE == p->pixel_map[r][c]))
                continue;

            update_label_val = p->pixel_map[r][c];
            /* ここら辺はラベル割り当てとほとんど同じ */
            for (pat = MAX_NUM; pat > 0; pat--)
            {
                if (get_lookup_table(t, update_label_val) < update_label_val)
                {
                    update_label_val = get_lookup_table(t, update_label_val);
                }

                if (get_lookup_table(t, update_label_val) == update_label_val)
                {
                    p->pixel_map[r][c] = get_lookup_table(t, update_label_val);
                    break;
                }
            }
        }
}

/* ラベル値を圧縮して再度ラベリングする(必須ではない) */
void compress_label(Picture *p, unsigned int compression_label[LABEL_MAX_SIZE], unsigned int lookup_table[MAX_NUM][1])
{
    unsigned int r = 1;
    unsigned int c = 1;
    unsigned int pat = 0;

    for (r = 1; r < MAX_NUM; r++)
    {
        if (EXCEPTION == get_lookup_table(lookup_table, r))
            break;

        if (get_lookup_table(lookup_table, r) == r)
        {
            compression_label[c] = r;
            c += 1;
        }
    }

    for (r = 1; r < p->row_size - 1; r++)
        for (c = 1; c < p->col_size - 1; c++)
        {
            if ((NONTARGET_PIXEL == p->pixel_map[r][c] || OUTSPACE == p->pixel_map[r][c]))
                continue;
            for (pat = 1; pat < LABEL_MAX_SIZE; pat++)
            {
                if (NONTARGET_PIXEL == compression_label[pat])
                    continue;

                if (p->pixel_map[r][c] == compression_label[pat])
                    p->pixel_map[r][c] = pat;
            }
        }
}

/* ラベルの割り当てと、lookup_tableの作成を行う関数 */
void labeling(Picture *p, unsigned int t[MAX_NUM][1], unsigned int compression_label[LABEL_MAX_SIZE])
{
    unsigned int t_pat = 1; /* 0はスキップ */
    unsigned int top_pixel_val = 0;
    unsigned int left_pixel_val = 0;
    unsigned int top_label_val = 0;
    unsigned int left_label_val = 0;
    unsigned int r = 1;
    unsigned int c = 1;

    /* ラスタスキャン */
    for (r = 1; r < p->row_size - 1; r++)
    {
        for (c = 1; c < p->col_size - 1; c++)
        {
            /* ターゲット画素でないならスキップ */
            if (NONTARGET_PIXEL == p->pixel_map[r][c])
                continue;

            top_pixel_val = p->pixel_map[r][c - 1];
            left_pixel_val = p->pixel_map[r - 1][c];

            if ((NONTARGET_PIXEL == top_pixel_val && NONTARGET_PIXEL == left_pixel_val) || (OUTSPACE == top_pixel_val && OUTSPACE == left_pixel_val))
            {
                /* 上の画素値と左の画素値が両方ターゲット画素ではない、もしくは両方余白な場合 */
                push_lookup_table(t, t_pat, t_pat);              /* lookup_tableに新しい値を割り振る */
                p->pixel_map[r][c] = get_lookup_table(t, t_pat); /* 着目画素値のラベル値を更新 */
                t_pat += 1;
            }
            else
            {
                /* どちらかにターゲット画素値が存在する場合 */
                /* 上・左の画素には既にラベルが割り当てられているので、それぞれのlookup_tableを参照する */
                top_label_val = get_lookup_table(t, top_pixel_val);
                left_label_val = get_lookup_table(t, left_pixel_val);

                /* 上・左のラベル値のうち小さいほうを着目画素のラベル値にする */
                p->pixel_map[r][c] = (top_label_val > left_label_val) ? left_label_val : top_label_val;

                /* lookup_tableの値を更新する */
                update_lookup_table(t, top_label_val, left_label_val);
            }
        }
    }

    /* 逆ラスタスキャン */
    for (r = p->row_size - 1; r > 0; r--)
    {
        for (c = p->col_size - 1; c > 0; c--)
        {
            /* ターゲット画素でないならスキップ */
            if (NONTARGET_PIXEL == p->pixel_map[r][c])
                continue;

            top_pixel_val = p->pixel_map[r][c + 1];
            left_pixel_val = p->pixel_map[r + 1][c];

            if ((NONTARGET_PIXEL == top_pixel_val && NONTARGET_PIXEL == left_pixel_val) || (OUTSPACE == top_pixel_val && OUTSPACE == left_pixel_val))
                continue;

            /* どちらかにターゲット画素値が存在する場合 */
            /* 上・左の画素には既にラベルが割り当てられているので、それぞれのlookup_tableを参照する */
            top_label_val = get_lookup_table(t, top_pixel_val);
            left_label_val = get_lookup_table(t, left_pixel_val);

            /* 上・左のラベル値のうち小さいほうを着目画素のラベル値にする */
            p->pixel_map[r][c] = (top_label_val > left_label_val) ? left_label_val : top_label_val;

            /* lookup_tableの値を更新する */
            update_lookup_table(t, top_label_val, left_label_val);
        }
    }

    resolve_conflict(p, t, compression_label);
}

/* テストケース用の関数 */
void test_case(Picture p)
{
    char flag = 0;
    unsigned int search_table[4];
    unsigned int r = 1;
    unsigned int c = 1;
    unsigned int pat = 0;
    /* debug */
    unsigned debug = 0;
    unsigned debug_target_pixel_sum = 0;

    /* 出力結果が間違っていないかテストするための処理 */
    /* ラスタスキャン */
    for (r = 1; r < p.row_size - 1; r++)
        for (c = 1; c < p.col_size - 1; c++)
        {
            if ((NONTARGET_PIXEL == p.pixel_map[r][c] || OUTSPACE == p.pixel_map[r][c]))
                continue;

            debug_target_pixel_sum += 1;

            search_table[0] = p.pixel_map[r - 1][c];
            search_table[1] = p.pixel_map[r][c - 1];
            search_table[2] = p.pixel_map[r + 1][c];
            search_table[3] = p.pixel_map[r][c + 1];

            for (pat = 0; pat < 4; pat++)
            {
                if ((search_table[pat] != p.pixel_map[r][c] && search_table[pat] > 0))
                {
                    flag = 1;
                    debug = search_table[pat];
                }
            }
        }

    if ((0 == flag) && (debug_target_pixel_sum == p.target_pixel_sum))
        printf("success\n");
    else
    {
        printf("error -> %u\n", debug);
    }
}

void FREE(Picture *p)
{
    unsigned int r = 0;
    for (r = 0; r < p->row_size; r++)
        free(p->pixel_map[r]);
    free(p->pixel_map);
}

終わりに

この記事を書いておいてなんですが、私は画像処理の経験がほとんどなくラベリング処理を現場で使ったことはありません。

なのでラベリング処理を書いていて、ウェブ上に解説が少ないことにびっくりしました。
OpenCVなどで気軽に利用できるためアルゴリズムについての説明がないのか、ラベリング処理があまり使われるものではないのか、どちらなのでしょうか？

いずれにせよ、この記事がみなさんの学習の助けになれば幸いです。