C言語による、４連結によるラベリング処理

Question

前提・実現したいこと

C言語によるラベリング処理について質問です。現在、あるpgmファイルを読み込み、それを２値化し、pbmファイルとして出力したものを、４連結でラベリング処理し、連結成分の個数をカウントするプログラムを作っています。
pgmファイルを読み込み、それを２値化し、pbmファイルとして出力するところまでは、うまくいっているのですが、４連結でラベリング処理し、連結成分の個数をカウントする部分がよくわかりません。最後のループでラベリング番号を振った配列を表示しているのですが、テスト用の画像をみてもせいぜい、１０もないぐらいだと思うのですが、かなり大きな桁が表示されます。また、ルックアップテーブルをどのように詰めれば良いのかわからずじまいです。ご教授よろしくお願いいたします。テスト用の画像は以下のをpgmファイルにして使用しています。

該当のソースコード

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


int main(void){

  FILE *fp, *output;
  int h, w, m, v, i, j;
  char type[10];
  int stage[256]={};

  //pgmファイルがNULLだった場合の処理
  if ((fp = fopen("test.pgm", "rb"))== NULL){
    printf("画像が開けません\n");
    exit(1);
  }


  fgets(type,10,fp); //画像形式の読み込み
  fscanf(fp, "%d", &w); //画像の幅
  fscanf(fp, "%d", &h); //画像の高さ
  fscanf(fp, "%d", &m); //画像の輝度の階調

  //上記4つの画像情報を出力
  printf("type=%sw=%d, h=%d, m=%d, ", type, w, h, m);

  //以下for文で1画素ずつ輝度をカウントし、ヒストグラムの元となる
  //それぞれの輝度値の合計を出力
  for (i = 0; i <w; i++){
    for (j = 0; j <h; j++){
      if((v = getc(fp)) != EOF) {
        stage[v]++;
      } else {
      }
    }
  }
  fclose(fp);

  //以下輝度0から輝度の合計をしていき、ある割合になった時、閾値を決定する
  double pixel;//画素数を保存
  double pixel_sum;//輝度値から加算して知った画素数を保存
  double pixel_average;//画素数比率の保存
  double pixel_before;//直前の画素数比率の保存
  int number;//閾値の保存

  pixel=w*h;//画素数を計算
  printf("pixel=%.f\n", pixel);

  for(i=0;i<256;i++){
    pixel_sum=pixel_sum+stage[i];
    pixel_average=pixel_sum/pixel;
    if(pixel_average>=0.7){
      printf("輝度値=%d 比率=%.4f\n",i-1,pixel_before);//閾値の１つ前の割合を出力
      printf("輝度値=%d 比率=%.4f\n",i,pixel_average);//閾値の割合を出力
      printf("閾値=%d\n",i );//閾値を出力
      number=i;//閾値を保存
      break;
    }
    pixel_before=pixel_average;//求めた割合を1つ前の割合として保存
  }

  //以下、決定した閾値から2値化画像を出力、２値化画像を２次元配列として格納
  //４連結、８連結のラベリング処理を行う
  output = fopen("test.pbm", "w");//白黒画像であるPBMファイルに出力
  fp = fopen("test.pgm", "rb");
  fgets(type,10,fp); //画像形式の読み込み
  fscanf(fp, "%d", &w); //画像の幅
  fscanf(fp, "%d", &h); //画像の高さ
  fscanf(fp, "%d", &m); //画像の輝度の階調

  fprintf(output, "P1\n%d %d\n", w, h);//マジックナンバーはP1、アスキー形式

  int image[w][h];//２値化画像を２次元配列として格納

  for (i = 0; i <h; i++){//imageの初期化
    for (j = 0; j <w; j++){
      image[w][h]=0;
    }
  }

  for (i = 0; i <h; i++){
    for (j = 0; j <w; j++){
      if((v = getc(fp)) != EOF) {
        if(v>=number){//画素を読み込んだ時、閾値以上か以下かを判定
          fprintf(output, "0 ");//閾値以上の場合白として出力
          image[j][i]=0;
        }else{
          fprintf(output, "1 ");//閾値未満の場合黒として出力
          image[j][i]=1;
        }
      } else {
      }
    }
    fprintf(output, "\n");
  }

  fclose(fp);
  fclose(output);

  int image_4[w][h];//4連結用配列
  int image_8[w][h];//8連結用配列
  int count_4[(w*h)/2][2];//4連結用ラベリング配列
  int count_8[(w*h)/2][2];//8連結用ラベリング配列
  int l4=1,l8=1;//４連結、８連結用の連結成分カウント変数
  int min=0;//検査時の最小値を保存

  for (i=1;i<(w*h)/2;i++){
    count_4[i][0]=i;
    count_4[i][1]=0;
    count_8[i][0]=i;
    count_8[i][1]=i;
  }

  for (i = 0; i <h; i++){//image_4の初期化
    for (j = 0; j <w; j++){
      image_4[w][h]=0;
    }
  }


  for (i = 0; i <h; i++){//4連結用
    for (j = 0; j <w; j++){
      if(image[j][i]==1){//対象画素が1,以下は4連結用
        if(i==0&&j==0){//画素の一番始まり(左上角)
          image_4[0][0]=l4;
          l4++;
        }

        else if(i==0){//対象画素が一番上の辺にあたる場所にある
          if(image_4[j-1][0]!=0){
            image_4[j][0]=image_4[j-1][0];
          }else{
            image_4[j][0]=l4;
            l4++;
          }

        }else if(j==0){//対象画像が一番左の辺に当たる場所にある
          if(image_4[j][i-1]!=0){
            image_4[j][i]=image_4[j][i-1];
          }else{
            image_4[j][i]=l4;
            l4++;
          }

        }else{//上記に当てはまらない全ての画素
          if(image_4[j-1][i]!=0||image_4[j][i-1]!=0){//左マスまたは上のマスが0ではない

            if(image_4[j-1][i]==image_4[j][i-1]){//左と上のマスが同じラベル番号
              image_4[j][i]=image_4[j-1][i];

            }else if((image_4[j-1][i]!=0)&&((image_4[j][i-1]==0)||(image_4[j-1][i]<image_4[j][i-1]))){
              //左のラベル番号が0ではなくかつ、左のラベル番号の方が小さい
              image_4[j][i]=image_4[j-1][i];
              count_4[image_4[j][i-1]][1]=image_4[j-1][i];

            }else{//上のラベル番号が0ではなくかつ、上のラベル番号の方が小さい
              if((image_4[j][i-1]!=0)&&((image_4[j-1][i]==0)||(image_4[j][i-1]<image_4[j-1][i]))){
              image_4[j][i]=image_4[j][i-1];
              count_4[image_4[j-1][i]][1]=image_4[j][i-1];
            }
            }

          }else{
            image_4[j][i]=l4;
            l4++;
          }
        }
      }
    }
  }

for (i = 0; i <h; i++){
  for (j = 0; j <w; j++){
    printf("%d ", image_4[j][i]);
  }
  printf("\n");
}
for(i=1;i<(w*h)/2;i++){
 if(count_4[i][1]!=0)
 printf("%d  %d\n",count_4[i][0],count_4[i][1] );

}


//printf("４連結の連結成分の個数=%d\n",max4);
return 0;

}

試したこと

最後のループでラベリング番号を振った配列を表示し、正しくラベリング番号が振られているかどうかを調べた。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[www.]

ご意見ありがとうございます。
ラベリングをするにあたって、以下のサイトを参考にさせていただきました。
https://imagingsolution.net/imaging/labelling/

[e-watt]

・なにはともあれ、image_4[][]を初期化していないのでゴミの値が出るのは必然
・＞pbmファイルとして出力するところまでは、うまくいっているのですが、
そうでもないと思いますよ。
1.fscanf()で諧調を読み込んだ後、改行はまだ読み飛ばされていないので、
　その下のループにてgetc(fp)は最初にその改行を拾ってきます。
読み込んだループの後でstage[]をダンプして確認しましょう。
2.pbmへの出力において、入力ファイルを再度オープンしていますが、
　そのあとでヘッダの分を（fgetsなりfseekなりで）読み飛ばしていないため、
　getc()はとりあえずその辺の文字をとって来ており、結果のpbmのなかみは
　かなり期待と異なっているはずです。
※実はその辺を修正済みだったらすみません。質問を修正済みのコードに更新してください。
・（閾値の判定についての質問は、元のままでよいようです。改行を読み飛ばさないままだと判断を誤るようでした）
・念のため、入力のpbmファイルそのものも添付した方が良いのではないでしょうか。
・ラベリングのコードは追っていません。悪しからず。

[e-watt]

・→その後、ちょっとだけ追いました
＊とりあえず、ご質問のコードは左と上の画素だけ見る「2連結」になっていませんか？
＊とりあえずは、コードが長くなっても、参考にしたページ通りに書くべきだと思いますよ。
　少なくとも、そのページの記述通りに書いたようには見えません。
　どこをどう云う理由で変えたかを書いていただ…くよりは、
　やはり一度は元のページ通りに書いてみては？
　　　　ご呈示のコードでは、どこか間違っていることは確実ですが、「参照ページのどこそことの相違が原因ですね」と回答するのが困難です。
＊私は自分なりに参考ページ通りに書いたら期待通りの結果が出ましたが、
　ご質問のコードとはかなり違うものになったので回答には書きません。

[fana]

とりあえず，画像を読み込んで二値化がどうの…という前処理の話と，ラベリング処理の話とを分離した状態の質問にできないのでしょうか？
ラベリングの話には前段の部分は不要でしょうし，前段の処理が既に間違っているのであれば，後段のラベリング処理の結果を見ていても仕方ない気がしますし．

あと，本件の内容とは関係ありませんけども，「参考にしたページ」には

> ラベリング処理を行う画像のパターンによってはうまくラベル番号が割り振られない場合があります。
そこは、何とかして（ちょっと説明が難しい部分）うまく割り振られるようにチャレンジしてみて下さい。

と書かれており，アルゴリズムとして完全ではない様子ですよ．
（「どうせなら」入力次第で失敗するかもしれないとかいう心配の無い話を最初から実装した方が…という気もしないでもない）

[e-watt]

・もうひとつ、元のコードの本質的な誤りが解かったので追記します。

　　}else if((image_4[j-1][i]!=0)&&(image_4[j-1][i]<image_4[j][i-1])){
　　//左のラベル番号が0ではなくかつ、左のラベル番号の方が小さい

この判定は、「上のラベル番号がゼロのとき」は避けなければいけません。
「近傍の領域に『割り振られたラベル番号(>0)』のうち、最小のもの」を割り当てる必要があるからです。
質問時点のコードでは、上のラベル番号がゼロのときに条件が偽となり、
当該箇所のラベルの値が更新されず（＝ゼロのまま放置され）、すなわち連続していないことになってしまいます。
修正案：(leftおよびupが適切に宣言及び代入されているとして； 元のコード通りには書く気がしません。読むのも面倒でしょ？)
　　}else if (left != 0 && (up == 0 || left < up)) {
　　//左のラベル番号が0ではなくかつ、上がゼロなら自動的に左を採用、または左のラベル番号の方が上より小さい

※これまでの点を修正して所期の動作をするようになれば、（「2連結」なので参照ページとラベル番号は
　ことなるものの）それなりの結果が出ます。
（修正：）ルックアップテーブルも生成できているようなので、本来の質問をするために、
あなたの考えに基づく詰め直しの手順（のわかる／わからない範囲）を日本語かコードで追加してから質問を継続すればよいと思います。

[www.]

たくさんのご指摘、ありがとうございます。
＊とりあえず、ご質問のコードは左と上の画素だけ見る「2連結」になっていませんか？
参考にしているサイトは、ラスタ走査で８連結を行なっていました。しかし、下のマス、右下は読み込んでいなかったです。私はそれを参考に、ラスタ走査で４連結を行うことにしました。そうすると、上と左に当たるため、2つのマスのみを読み込んでいます。

ご指摘があった場所を直していこうと思います。また、何かあったらご報告、ご質問させていただきます。

[e-watt]

＞８連結を行なっていました。しかし、下のマス、右下は読み込んでいなかったです。

読み直してみたらそうでした。
説明では左上、上、右上、左の4ピクセルだけ参照しているけど、それを「8連結」と呼んでいるのですね。私はそれを4連結だとばかり思いこみ、手元では説明通りの実装を試していました。失礼しました。

[www.]

ご指摘のあった部分を修正しました。
1.fscanf()で諧調を読み込んだ後、改行はまだ読み飛ばされていないので、
　その下のループにてgetc(fp)は最初にその改行を拾ってきます。
この部分なのですが、過去に、stage[]の全要素の合計==w＊h（画素数）というのを確認していたので、改行などは含まれていないと考えておりました。

最後から２番目に当たる２重ループ文で、ラベル番号を実際に割り振った画像配列を全て表示しているのですが、なぜかところどころ行の最後、または２番目あたりにかなり大きなラベル番号が表示されます。

e-watt様
可能であれば、手元の実装したもの、８連結のもので構いませんので、お見せいただくことはできますでしょうか。
よろしくお願いいたします。

[e-watt]

回答に（かなり雑な）コード例を貼りました。
詰め直しは参照ページの8連結だと割とシンプルな結果が出て簡単にできたのですが、
4連結だともうひと手間かけないといけないことが解かって時間を食ってしまいました。

[e-watt]

↑↑すでにお気づきかもしれませんが、image_4の初期化部分で
< image_4[w][h]=0;
-
> image_4[j][i]=0;
としてください。
回答は長くなってしまったので、「詰め直し」の説明は別枠の回答で追記します。（teratail的に行儀は悪いかもしれない）

[e-watt]

＞stage[]の全要素の合計==w＊h（画素数）
それはwとhのループで回したからと思われます。改行を読んでしまった分
画像の末尾が読まれずに（EOFに到達せずに）終わっているはずです。
stage[0~255]をダンプして、先頭に意図しない 13（\r）や10（\n）が入っていないか確認してみてください。
あるいは、.pgmファイルにおいて諧調数の後に改行が入らずに画素データが続いていたりしますか？

私はCygwinで試していますが、もし別の環境では意図通り読めている（pbmでも左上に余計な「1」などない）のでしたら理由がわかりません。すみません。

[www.]

e-watt様
＞stage[]の全要素の合計==w＊hの部分はやはり自分の間違えでした。
fgetsで読み飛ばしを行いました。

ルックアップテーブルについて。
丁寧なご回答ありがとうございます。
自分がわからなかったところはまさに、再帰的結合の部分です。
よくよく考えてみれば。。。という感じでした。ありがとうございます。

サンプル画像のほうもやりましたところ、結果も同じだったので問題なかったです。

とりあえず、自分の疑問は解決できました。丁寧なご解説、大変感謝板いたします。

Answer 1

ルックアップテーブルの詰め直し

（※以下をもっと簡単にやってしまう方法はあるかもしれません。）

コードは先の回答のものを参照してください。
以下では4連結で走査する場合を説明するので、NEIGHBORを4として（回答に貼ったまま）コンパイルし実行すれば下記の結果を得られるはずです。

入力画像がシンプルすぎると詰め直す必要が生じないので、参照ページの画像を
説明にある8連結ではなく4連結で走査した結果で説明します。
（質問の画像や参照ページの8連結だと走査直後のDstがきれいな昇順となり、
私のコードの「番号を圧縮」の部分だけで足りてしまう。）

念のため、サンプル画像をのソースも記載します。適当なテキストエディタで下記内容のファイルを作成し、test.pgmと名付けてプログラムに食わせてください。
テキストファイルに見えるかもしれませんが、バイナリファイルだと思えば（輝度値90と33の画素が並んだ）立派なバイナリファイルです

P5
16 15
90
ZZZZZZZZZZZZZZZZZZZZ!ZZZZZZZZZZZZZZ!!!ZZZZZZZZZZZZZ!!!ZZZZZ!ZZZZZZZ!!!!ZZZZ!!ZZZZ!!!!!!ZZZ!!!ZZZZZ!!!!!ZZZ!!!ZZZZZZ!!!!ZZ!!!ZZZZZZZ!ZZZ!!!!ZZZZZZZZZZ!ZZ!!ZZZZZZZZZZ!!!ZZZZ!ZZZZZZZ!!!!!Z!!!!ZZZZZZZ!!!ZZ!!!!ZZZZZZZZ!ZZZ!ZZZZZZZZZZZZZZZZZZZZZZ

さて、参照ページの画像を4連結で走査した結果は次の通り（ラベル番号は16進数で表示）

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ 1 _ _ _ _ _ _ _ _ _ _ _
_ _ _ 2 1 1 _ _ _ _ _ _ _ _ _ _
_ _ _ 2 1 1 _ _ _ _ _ 3 _ _ _ _
_ _ _ 2 1 1 1 _ _ _ _ 3 3 _ _ _
_ 4 4 2 1 1 1 _ _ _ 5 3 3 _ _ _
_ _ 4 2 1 1 1 _ _ _ 5 3 3 _ _ _
_ _ _ 2 1 1 1 _ _ 6 5 3 _ _ _ _
_ _ _ 2 _ _ _ 7 7 6 5 _ _ _ _ _
_ _ _ _ _ 8 _ _ 7 6 _ _ _ _ _ _
_ _ _ _ 9 8 8 _ _ _ _ a _ _ _ _
_ _ _ b 9 8 8 8 _ c c a a _ _ _
_ _ _ _ 9 8 8 _ _ c c a a _ _ _
_ _ _ _ _ 8 _ _ _ c _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Src 1  2  3  4  5  6  7  8  9 10 11 12 13 14 (Srcと書いていますが要はDstの添え字)
Dst 1  1  3  2  3  5  6  8  8 10  9 10 13 14

ここで、ラベルが{1,2,4}や{3,5,6,7}である領域はそれぞれ一つにまとまるはずです。
ルックアップテーブルを見ると、

• Dst[1]=1: ラベル1→ラベル1に変更
• Dst[2]=1: ラベル2→ラベル1に変更
• Dst[4]=2: ラベル4→ラベル2に変更

と記録されています。
「ラベル4→ラベル2に変更」して、さらに「ラベル2→ラベル1に変更」を適用すると
「ラベル4→ラベル1に変更」できます。
つまり、上の時点では Dst[4]=2 であるものを、Dst[ Dst[4] ]=1 と順次追うことになります。
そして追及は Dst[n] == n となるような n で終了します。（変更先が自分自身となる）
これをDst[]の全要素について実行しているのが当該部分の while() ループです。

このループを実行後、Dst[]は以下のように{1,3,8,10 (13以降は画像に未適用)}にまとまります。

Dst  1  1  3  1  3  3  3  8  8 10  8 10 13 14

上のようにまとまった数字に対し、{1, 2, 3, 4}と連番を振るのが次のループです。
変数seqnが連番で、Dst[]の要素の値 q をどの連番に振りなおすか、を conv[q] に記録します。
このとき、q が初出の値ならconv[q]は未設定（を示す値ｰ1）なので連番seqnを与え、seqnを次の値(++seqn)にします。
実行後は

Dst  1  1  2  1  2  2  2  3  3  4  3  4  5 14

となり、前掲の画像のラベルを添え字としてDst[]の値に置き換えれば、説明ページのような1～4で埋められた画像を得ます。

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ 1 _ _ _ _ _ _ _ _ _ _ _
_ _ _ 1 1 1 _ _ _ _ _ _ _ _ _ _
_ _ _ 1 1 1 _ _ _ _ _ 2 _ _ _ _
_ _ _ 1 1 1 1 _ _ _ _ 2 2 _ _ _
_ 1 1 1 1 1 1 _ _ _ 2 2 2 _ _ _
_ _ 1 1 1 1 1 _ _ _ 2 2 2 _ _ _
_ _ _ 1 1 1 1 _ _ 2 2 2 _ _ _ _
_ _ _ 1 _ _ _ 2 2 2 2 _ _ _ _ _
_ _ _ _ _ 3 _ _ 2 2 _ _ _ _ _ _
_ _ _ _ 3 3 3 _ _ _ _ 4 _ _ _ _
_ _ _ 3 3 3 3 3 _ 4 4 4 4 _ _ _
_ _ _ _ 3 3 3 _ _ 4 4 4 4 _ _ _
_ _ _ _ _ 3 _ _ _ 4 _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

ひとまず説明は以上です。お役に立てれば幸いです。

Answer 2

回答が長くなってしまったので、「詰め直し」は別に回答します。
こちらは全般的な参考に、ということで。
なお、コンパイル前に先頭付近のマクロ NEIGHBOR により、4連結、8連結のどちらかを選んで実行できます。

#define NEIGHBOR 4		/*連結数:4か8*/

/*
 ・マクロの使い方など、かなり行儀が悪い部分がありますがご了承ください。
 */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define NEIGHBOR 4		/*連結数:4か8*/

/* デバッグ用 */
static void showIntMatrix(const char* name, const int* array, int width, int height, int line) {
	printf("%s: %dWx%dh @%d\n", name, width, height, line);
	for (int i = 0; i < height; i++){
		for (int j = 0; j < width; j++){
			int v = array[i + j*height];
			if (v == 0) {
				printf("_ ");
			}else{
	    		printf("%x ", v);
			}
	  	}
		printf("\n");
	}
}
#define showImage() showIntMatrix("Source Image", &image[0][0], w, h, __LINE__)
#define showLabeledImage() showIntMatrix("Labels", &labeled_image[0][0], w, h, __LINE__)


/*デバッグ用*/
static void showIntArray(const char* caption, const char* name, const int* array, int N) {
	printf("%s:\n%s ", caption, name);
	for (int i=1; i<=N; i++){
		printf("%2d ", array[i]);
	}
	printf("\n");
}
#define	showDST(expr)		showIntArray(expr, "Dst", dst, ((t)+1)/2)
#define	PartN (14)
#define	showPartOfDST(expr)	showIntArray(expr, "Dst", dst, PartN)	/*全部出すと冗長なので先頭付近のみ表示*/


int main(void){

  FILE *fp, *output;
  int h, w, m, v, i, j;
  char type[10];
  char junk[10];
  int stage[256]={};

  //pgmファイルがNULLだった場合の処理
  if ((fp = fopen("test.pgm", "rb"))== NULL){
    printf("画像が開けません\n");
    exit(1);
  }

  fgets(type,10,fp); //画像形式の読み込み
  fscanf(fp, "%d", &w); //画像の幅
  fscanf(fp, "%d", &h); //画像の高さ
  fscanf(fp, "%d", &m); //画像の輝度の階調
  fgets(junk,10,fp); //改行を読み飛ばす
	printf("J[%s]len(%d)\n", junk, strlen(junk));
	
  //上記4つの画像情報を出力
  printf("type=%sw=%d, h=%d, m=%d\n", type, w, h, m);

  //以下for文で1画素ずつ輝度をカウントし、ヒストグラムの元となる
  //それぞれの輝度値の合計を出力
  for (j = 0; j <h; j++){
    for (i = 0; i <w; i++){
    	do {
	      if((v = getc(fp)) == EOF) {
	      	break;
	      }
    	} while (v == '\r' || v == '\n');
    	if (v == EOF)
    		break;

    	printf("[%d],", v);
        stage[v]++;
      	
    }
     printf("\n");
  }
  fclose(fp);
#if 0
	for (v=0; v<256; ++v) {
		printf("%d ",stage[v]);
		if (v % 16 == 15) {
			printf("\n");
		}
	}
#endif

  //以下輝度0から輝度の合計をしていき、ある割合になった時、閾値を決定する
  double pixel;//画素数を保存
  double pixel_sum;//輝度値から加算して知った画素数を保存
  double pixel_average;//画素数比率の保存
  double pixel_before;//直前の画素数比率の保存
  int number;//閾値の保存

  pixel=w*h;//画素数を計算
  printf("pixel=%.f\n", pixel);

  for(i=0;i<256;i++){
    pixel_sum=pixel_sum+stage[i];
    pixel_average=pixel_sum/pixel;
    if(pixel_average>=0.7){
      printf("輝度値=%d 比率=%.4f\n",i-1,pixel_before);//閾値の１つ前の割合を出力
      printf("輝度値=%d 比率=%.4f\n",i,pixel_average);//閾値の割合を出力
      printf("閾値=%d\n",i );//閾値を出力
      number=i;//閾値を保存
      break;
    }
    pixel_before=pixel_average;//求めた割合を1つ前の割合として保存
  }

  //以下、決定した閾値から2値化画像を出力、２値化画像を２次元配列として格納
  //４連結、８連結のラベリング処理を行う
	/* いや、8連結はやらないよ。*/
  output = fopen("test.pbm", "w");//白黒画像であるPBMファイルに出力
  fp = fopen("test.pgm", "rb");
  fgets(junk,10,fp); //ヘッダを読み飛ばす
  fgets(junk,10,fp); //ヘッダを読み飛ばす
  fgets(junk,10,fp); //ヘッダを読み飛ばす

	
	fprintf(output, "P1\n%d %d\n", w, h);//マジックナンバーはP1、アスキー形式

 int image[w][h];//２値化画像を２次元配列として格納


  for (i = 0; i <h; i++){
    for (j = 0; j <w; j++){
    	do {
	      if((v = getc(fp)) == EOF) {
	      	break;
	      }
    	} while (v == '\r' || v == '\n');
    	if (v == EOF)
    		break;
    	printf("[%d]", v);
        if(v>=number){//画素を読み込んだ時、閾値以上か以下かを判定
          fprintf(output, "0 ");//閾値以上の場合白として出力
          image[j][i]=0;
        }else{
          fprintf(output, "1 ");//閾値未満の場合黒として出力
          image[j][i]=1;
        }
    }
    printf("\n");
    fprintf(output, "\n");
  }

  fclose(fp);
  fclose(output);
	
	showImage();

	
  int labeled_image[w][h];//4連結用配列
  int Label=0;	//ラベル番号
  int NL = ((w*h)+1)/2;		//ラベルの最大数
  int dst[NL+1];//ラベリング配列 ; Srcは書き換えないし連番だから、Dstしか用意しないぜ
	
  for (i=1;i<=NL;i++){
  	dst[i] = i;	//[1]から[((w*h)+1)/2]にその値を入れるぜ; 
  					//ただし質問者様は要素数と末尾の処理を間違ってるっぽい
  					//+ 領域数の最大値は、市松模様に塗り分けられた時の ceil(W*H/2)  3x3マスだと5個まであり
  }
//初期化を忘れずに
  for (i = 0; i <h; i++){//
    for (j = 0; j <w; j++){
    	labeled_image[j][i] = 0;
    }
  }

/*変態チックなデバッグ用マクロ*/
#define	_TL_	printf("%d at %d,%d L=%d \n", Label, j, i, __LINE__ );
#define	_Tm_	printf("%d at %d,%d L=%d \n", min, j, i, __LINE__ );

/* (x,y)のラベル番号を与える。画像の範囲外に対してはゼロを与える */
#define getLabel(x,y)	((0<=(x)&&(x)<w && 0<=(y)) ? labeled_image[x][y] : 0)

/*ゼロでなくminより小さい値であればそれを与える*/
#define nonzeroMin(var,min)	(((var) != 0 && (var) < (min)) ? (var) : (min))

  for (i = 0; i <h; i++){
    for (j = 0; j <w; j++){
      if(image[j][i]==1){	//対象画素が1
			int	up_m = getLabel(j, i-1);	//上	4／8連結で共通
			int left = getLabel(j-1, i);	//左	4／8連結で共通
#if NEIGHBOR == 4 //4連結
        	if (up_m == 0 && left == 0) {	//コメントは8連結側を参照されたし
        		labeled_image[j][i] = ++Label;
//_TL_
        	}else{
        		int min = Label;
        		min = nonzeroMin(up_m, min);
        		min = nonzeroMin(left, min);
        		labeled_image[j][i] = min;
        		dst[up_m] = nonzeroMin(dst[up_m], min);		//双方ゼロではないので実は普通のmin(a,b)でよい
        		dst[left] = nonzeroMin(dst[left], min);
_Tm_
        	}
#elif NEIGHBOR == 8
			int	up_l = getLabel(j-1, i-1);	//左上
			int up_r = getLabel(j+1, i-1);	//右上
        
      		//『』内は参照ページの記述の引用；なるべく書いてある通りに作るぜ
        	//『左上、上、右上、左の画素のラベル番号を参照し、全て０（ゼロ）の場合は』
        	if (up_l == 0 && up_m == 0 && up_r == 0 && left == 0) {
        		labeled_image[j][i] = ++Label;	//『最後に割り振った番号＋１のラベル番号を割り振ります。』
_TL_
        	}else{
        		//『参照した画素のラベル番号が複数存在した場合は、』
        		/* →実際に「複数」であるかどうかを問う必要はない */
        		/* ここに来た以上一つ以上のゼロ以外の値があるので、最小値を決定しさえすればよい。 */
        		int min = Label;	/* この時点で、Labelはこれまでに割り振られた値の最大値 */
        		min = nonzeroMin(up_l, min);
        		min = nonzeroMin(up_m, min);
        		min = nonzeroMin(up_r, min);
        		min = nonzeroMin(left, min);
        		labeled_image[j][i] = min;		//（0以外の）『最小の番号を割り振ります。』
_Tm_
        		//『用いなかったラベル番号のルックアップテーブルの番号を最小の番号に書き換えます。』
        		/* ループ内でdst[0] は未使用だ（参照しない）からチェックせずにガンガン上書きするぜ*/
        		/* 用いたところもどうせminで同じ値だから気にせず上書きするぜ*/
        		dst[up_l] = nonzeroMin(dst[up_l], min);
        		dst[up_m] = nonzeroMin(dst[up_m], min);
        		dst[up_r] = nonzeroMin(dst[up_r], min);
        		dst[left] = nonzeroMin(dst[left], min);
        	}
#else
#error  bad number for 'NEIGHBOR'
#endif
      }
    }
  	showLabeledImage();	//一行操作するごとに表示する…と、解説ページと似た感じの出力に
  }

	printf("RAW result (%dx%d):\n", h, w);
	showLabeledImage();
	
	showPartOfDST("DST before");

/* ルックアップテーブルの詰め替え */

  int conv[NL+1];	//
  for (i=1;i<=NL;i++){
  	conv[i] = -1;	//すべて「未定」にする
  }	
	conv[0] = 0;
	dst[0] = 0;

	//再帰的結合; ←これは回答者の勝手な命名で、専門用語ではない
	for (j=1;j<=NL;j++){
		while (dst[j] != dst[ dst[j] ])
			dst[j] = dst[ dst[j] ];
	}

  showPartOfDST("recursed");

	//番号を圧縮; 説明しないとわからんと思う
	int seqn = 1;
  for (i=1;i<=13;i++){
  	int dstQ = dst[i];
  	printf("[%2d] dstQ=%2d conv[dstQ]=%2d...",i, dstQ, conv[dstQ]);
  	if (conv[ dstQ ] == -1) {
  		conv[ dstQ ] = seqn;
  		printf("conv[%2d] gets-to %2d", dstQ, seqn);
  		++seqn;
  	}else{
  		printf("%19s", "");
  	}
  	printf(" dst[%2d]<<%2d, dstQ=%2\n", i, conv[dstQ], dstQ);

  	dst[i] = conv[dstQ];
  }	
	
	showIntArray("Conv:", "conv", conv, PartN);
	showPartOfDST("after:");
/* ルックアップテーブルの詰め替え；ここまで */

  //ルックアップテーブルに従い結果を書き換え
	dst[0] = 0;
	for (i = 0; i <h; i++){
		for (j = 0; j <w; j++){
			labeled_image[j][i] = dst[ labeled_image[j][i] ];
		}
	}
  //最終結果を表示
  	showLabeledImage();
	
	printf("%d連結の連結成分の個数=%d?\n", NEIGHBOR, dst[Label]);	/*使われたラベルの値（最大値）の圧縮結果が領域の数…とは限らなそう*/

return 0;
}

Answer 3

ラベリングの部分を関数化して、２値化画像配列から認識した領域を保持する配列を出力する関数としてデバッグの対象にすればいいのかと思います。ラベリングの問題は単純に解けば迷路探索問題となり、これがスローバージョンのコードになると思います。これを高速化することはできるらしいのですが私はその画像処理の分野の専門家じゃないのでよくわからないです。ネットにあがっているラベリングのコードを一生懸命見てヒントを得るしかないのかと思います。

まずスローバージョンのコードをあげることを考えます。teratailに類似の質問があったと思います。

teratail - Pythonで二重配列を使った問題

もし必要があれば、ファストバージョンのコードを作成することを考えます。ネットにあがっているラベリングのソースコードを見て、わからなければコードを模写するなどしてとっかかりを作ります。

スローバージョンを作るにしろ、ファストバージョンを作るにしろ、テストケースを用意してやる必要があります。テストケースを多数用意してアルゴリズムの正しさを検証することが重要であると考えます。

もしこのサイトで、より有用なアドバイスが欲しいのであれば、自分が使用しているラベリングのアルゴリズムの参考文献かサイトのURLを追記するといいのではないかと思いました。私は画像処理の専門家ではないのですが、もしかしたら画像処理に詳しい御仁の目にとまるかもしれません。がんばってください。