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

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

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

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

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

# 環境
- C(Gcc6.3)
- [CodeChef](https://www.codechef.com/ide)で実行

# 実行例
以下は地球の画像に__4近傍ラベリング処理__を施した結果です。(左が元画像、右が出力txtファイル)
![tikyu__.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/e91caac1-b2e2-fb7b-653d-d495db1ef8f1.jpeg)
拡大すると確認できますが、ラベル値が割り当てられた__txtファイル__です。
![tikyu_kakudai.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/f0a538df-34d2-6c51-a6ae-0cdae157bc53.png)
以下の画像はラベリング処理で求めた連結成分ごとに色を塗った塗り絵画像です。(プログラムで生成しました)
![tikyu_.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/3b8d511b-b536-f5e9-fea0-82c0f692b2ec.png)
以下同様です。(省略)
![nihon__.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/55912335-078f-27c7-1d2a-e9818b11a440.jpeg)
![nihon_kakudai.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/0bbb0443-17e0-6480-c418-2c79c9f1b4f5.png)
![nihon_.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/8358cbfa-0191-a2a7-1528-24c2301b9365.png)

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

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

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

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

8近傍・・・4近傍の考え方に加え、__斜め方向__に存在する画素が同じ値であれば、連結している
![48近傍.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/9e9ede53-f2c9-202a-b6ac-402b73374528.png)

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

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

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

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

![PIXELMAP.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/7619fffb-bf52-08dd-8181-9e1497711c2b.png)

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

![ラスタスキャン.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/35aa14d2-567a-0bd1-4aa4-31103aa1b0f3.png)

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

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

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

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

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

![ラスタスキャン１.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/cbe63b32-f4e5-5d3a-834a-15633e925ccc.png)

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

## ルックアップテーブルの更新
ルックアップテーブルの更新は、ラベリング処理でかなり__重要な部分__を占めると思います。
ルックアップテーブルを作成する理由は、ラベルの__衝突を防ぐ__ことにあります。
ラベルの衝突とは、値の異なるラベル同士が同じ連結成分の中に存在していることです。
![衝突.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/c0868663-0aee-f77e-2222-e3108dbb35ca.png)
上の画像では、ラベル値1とラベル値3が__衝突__しているのが分かります。
しかし、先ほど説明した方法でラベルを割り振っていくと必然的にこうなってしまいます。

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

![更新.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/b6044aa1-3927-a8e6-148c-c3835640de52.png)

そうすると、先ほどの衝突例は以下のように解決できます。
![更新１.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/3dd2fd80-ab92-30cc-f7fc-d73286cb0bb0.png)
ルックアップテーブルの値を手掛かりにして、ラベル値3の画素をラベル値1に更新して衝突を回避していることが分かります。

基本的に、このような考え方でルックアップテーブルを更新していくことになります。
では、__もうひと工夫__必要になる場合について考えていきましょう。
以下の例では、__衝突回避に失敗__しています。
![解決失敗.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/e78d6f99-9bcf-d00f-41a0-a15c8d0c1d2d.png)
ラベル値２の更新が上手くいっていないようです。
このような状況を打破するために、__逆ラスタスキャン__でルックアップテーブルを更新します。
逆ラスタスキャンでは、着目画素の__下__と__右__に注目することに注意してください。
![更新成功.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/87a31827-1073-8c93-e209-87fc76548c71.png)

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

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

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

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

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

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

![衝突処理解決.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/74bf431b-af48-a5f2-5467-dd881dee9288.png)

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

## ラベル値の圧縮
次にラベル値の__圧縮__を行います。
ラベル値の圧縮とは、連結成分ごとに不連続な間隔で割り当てられているラベル値を、__1から連番__で割り当てる操作のことです。(私が勝手に名付けました)
 ![圧縮.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/576493/1ff91b6e-60f6-a4c3-7861-33eb959724e0.png)

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

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

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

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

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

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

ソースコードや、テストケース結果は[GitHub](https://github.com/Hajime-Ito/C_Labeling_Algorithm)の方でも共有しておきますので、ご参考にどうぞ。

~~~ C
/*
四近傍ラベリングアルゴリズム
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などで気軽に利用できるためアルゴリズムについての説明がないのか、ラベリング処理があまり使われるものではないのか、どちらなのでしょうか？

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