回答編集履歴
2
説明の誤字を修正
answer
CHANGED
|
@@ -1,6 +1,10 @@
|
|
|
1
1
|
回答が長くなってしまったので、「詰め直し」は別に回答します。
|
|
2
|
-
こちらは
|
|
2
|
+
こちらは全般的な参考に、ということで。
|
|
3
|
+
なお、コンパイル前に先頭付近のマクロ NEIGHBOR により、4連結、8連結のどちらかを選んで実行できます。
|
|
3
4
|
```C
|
|
5
|
+
#define NEIGHBOR 4 /*連結数:4か8*/
|
|
6
|
+
```
|
|
7
|
+
```C
|
|
4
8
|
/*
|
|
5
9
|
・マクロの使い方など、かなり行儀が悪い部分がありますがご了承ください。
|
|
6
10
|
*/
|
1
コードを少々修正し、説明を別枠で行うことを追記
answer
CHANGED
|
@@ -1,19 +1,16 @@
|
|
|
1
|
-
肝心の「ルックアップテーブルの詰め直し」で「なぜ」「何を」やっているかの説明が未記入ですがとりあえずコードだけ這っておきます。
|
|
2
|
-
|
|
1
|
+
回答が長くなってしまったので、「詰め直し」は別に回答します。
|
|
3
|
-
|
|
2
|
+
こちらは府全般的な参考に、ということで
|
|
4
3
|
```C
|
|
5
4
|
/*
|
|
6
5
|
・マクロの使い方など、かなり行儀が悪い部分がありますがご了承ください。
|
|
7
|
-
・変数名などかなりいじってしまいました。悪しからず
|
|
8
|
-
・インデントなども雑です。すみません
|
|
9
6
|
*/
|
|
10
7
|
#include<stdio.h>
|
|
11
8
|
#include<string.h>
|
|
12
9
|
#include<stdlib.h>
|
|
13
10
|
|
|
14
|
-
#define NEIGHBOR 4 /*連結数
|
|
11
|
+
#define NEIGHBOR 4 /*連結数:4か8*/
|
|
15
12
|
|
|
16
|
-
/* デバッ
|
|
13
|
+
/* デバッグ用 */
|
|
17
14
|
static void showIntMatrix(const char* name, const int* array, int width, int height, int line) {
|
|
18
15
|
printf("%s: %dWx%dh @%d\n", name, width, height, line);
|
|
19
16
|
for (int i = 0; i < height; i++){
|
|
@@ -32,17 +29,17 @@
|
|
|
32
29
|
#define showLabeledImage() showIntMatrix("Labels", &labeled_image[0][0], w, h, __LINE__)
|
|
33
30
|
|
|
34
31
|
|
|
35
|
-
/*デバッグ用
|
|
32
|
+
/*デバッグ用*/
|
|
36
33
|
static void showIntArray(const char* caption, const char* name, const int* array, int N) {
|
|
37
|
-
printf("%s:\n", caption);
|
|
34
|
+
printf("%s:\n%s ", caption, name);
|
|
38
35
|
for (int i=1; i<=N; i++){
|
|
39
36
|
printf("%2d ", array[i]);
|
|
40
37
|
}
|
|
41
38
|
printf("\n");
|
|
42
39
|
}
|
|
43
|
-
#define showDST(expr) showIntArray(expr, "
|
|
40
|
+
#define showDST(expr) showIntArray(expr, "Dst", dst, ((t)+1)/2)
|
|
44
41
|
#define PartN (14)
|
|
45
|
-
#define showPartOfDST(expr) showIntArray(expr, "
|
|
42
|
+
#define showPartOfDST(expr) showIntArray(expr, "Dst", dst, PartN) /*全部出すと冗長なので先頭付近のみ表示*/
|
|
46
43
|
|
|
47
44
|
|
|
48
45
|
int main(void){
|
|
@@ -63,7 +60,7 @@
|
|
|
63
60
|
fscanf(fp, "%d", &w); //画像の幅
|
|
64
61
|
fscanf(fp, "%d", &h); //画像の高さ
|
|
65
62
|
fscanf(fp, "%d", &m); //画像の輝度の階調
|
|
66
|
-
fgets(junk,10,fp); //
|
|
63
|
+
fgets(junk,10,fp); //改行を読み飛ばす
|
|
67
64
|
printf("J[%s]len(%d)\n", junk, strlen(junk));
|
|
68
65
|
|
|
69
66
|
//上記4つの画像情報を出力
|
|
@@ -125,9 +122,9 @@
|
|
|
125
122
|
/* いや、8連結はやらないよ。*/
|
|
126
123
|
output = fopen("test.pbm", "w");//白黒画像であるPBMファイルに出力
|
|
127
124
|
fp = fopen("test.pgm", "rb");
|
|
128
|
-
fgets(junk,10,fp); //
|
|
125
|
+
fgets(junk,10,fp); //ヘッダを読み飛ばす
|
|
129
|
-
fgets(junk,10,fp); //
|
|
126
|
+
fgets(junk,10,fp); //ヘッダを読み飛ばす
|
|
130
|
-
fgets(junk,10,fp); //
|
|
127
|
+
fgets(junk,10,fp); //ヘッダを読み飛ばす
|
|
131
128
|
|
|
132
129
|
|
|
133
130
|
fprintf(output, "P1\n%d %d\n", w, h);//マジックナンバーはP1、アスキー形式
|
|
@@ -165,13 +162,13 @@
|
|
|
165
162
|
|
|
166
163
|
int labeled_image[w][h];//4連結用配列
|
|
167
164
|
int Label=0; //ラベル番号
|
|
168
|
-
int NL = ((w*h)+1)/2; //
|
|
165
|
+
int NL = ((w*h)+1)/2; //ラベルの最大数
|
|
169
166
|
int dst[NL+1];//ラベリング配列 ; Srcは書き換えないし連番だから、Dstしか用意しないぜ
|
|
170
167
|
|
|
171
168
|
for (i=1;i<=NL;i++){
|
|
172
|
-
dst[i] = i; //
|
|
169
|
+
dst[i] = i; //[1]から[((w*h)+1)/2]にその値を入れるぜ;
|
|
173
|
-
//
|
|
170
|
+
//ただし質問者様は要素数と末尾の処理を間違ってるっぽい
|
|
174
|
-
//
|
|
171
|
+
//+ 領域数の最大値は、市松模様に塗り分けられた時の ceil(W*H/2) 3x3マスだと5個まであり
|
|
175
172
|
}
|
|
176
173
|
//初期化を忘れずに
|
|
177
174
|
for (i = 0; i <h; i++){//
|
|
@@ -184,7 +181,7 @@
|
|
|
184
181
|
#define _TL_ printf("%d at %d,%d L=%d \n", Label, j, i, __LINE__ );
|
|
185
182
|
#define _Tm_ printf("%d at %d,%d L=%d \n", min, j, i, __LINE__ );
|
|
186
183
|
|
|
187
|
-
/* (x,y)のラベル番号を与える。画像の範囲外に対して
|
|
184
|
+
/* (x,y)のラベル番号を与える。画像の範囲外に対してはゼロを与える */
|
|
188
185
|
#define getLabel(x,y) ((0<=(x)&&(x)<w && 0<=(y)) ? labeled_image[x][y] : 0)
|
|
189
186
|
|
|
190
187
|
/*ゼロでなくminより小さい値であればそれを与える*/
|
|
@@ -193,10 +190,10 @@
|
|
|
193
190
|
for (i = 0; i <h; i++){
|
|
194
191
|
for (j = 0; j <w; j++){
|
|
195
192
|
if(image[j][i]==1){ //対象画素が1
|
|
196
|
-
int up_m = getLabel(j, i-1); //
|
|
193
|
+
int up_m = getLabel(j, i-1); //上 4／8連結で共通
|
|
197
|
-
int left = getLabel(j-1, i); //
|
|
194
|
+
int left = getLabel(j-1, i); //左 4／8連結で共通
|
|
198
195
|
#if NEIGHBOR == 4 //4連結
|
|
199
|
-
if (up_m == 0 && left == 0) { //
|
|
196
|
+
if (up_m == 0 && left == 0) { //コメントは8連結側を参照されたし
|
|
200
197
|
labeled_image[j][i] = ++Label;
|
|
201
198
|
//_TL_
|
|
202
199
|
}else{
|
|
@@ -204,18 +201,18 @@
|
|
|
204
201
|
min = nonzeroMin(up_m, min);
|
|
205
202
|
min = nonzeroMin(left, min);
|
|
206
203
|
labeled_image[j][i] = min;
|
|
207
|
-
dst[up_m] = nonzeroMin(dst[up_m], min); //
|
|
204
|
+
dst[up_m] = nonzeroMin(dst[up_m], min); //双方ゼロではないので実は普通のmin(a,b)でよい
|
|
208
205
|
dst[left] = nonzeroMin(dst[left], min);
|
|
209
206
|
_Tm_
|
|
210
207
|
}
|
|
211
208
|
#elif NEIGHBOR == 8
|
|
212
|
-
int up_l = getLabel(j-1, i-1); //
|
|
209
|
+
int up_l = getLabel(j-1, i-1); //左上
|
|
213
|
-
int up_r = getLabel(j+1, i-1); //
|
|
210
|
+
int up_r = getLabel(j+1, i-1); //右上
|
|
214
211
|
|
|
215
|
-
//
|
|
212
|
+
//『』内は参照ページの記述の引用；なるべく書いてある通りに作るぜ
|
|
216
|
-
//
|
|
213
|
+
//『左上、上、右上、左の画素のラベル番号を参照し、全て０（ゼロ）の場合は』
|
|
217
214
|
if (up_l == 0 && up_m == 0 && up_r == 0 && left == 0) {
|
|
218
|
-
labeled_image[j][i] = ++Label; //
|
|
215
|
+
labeled_image[j][i] = ++Label; //『最後に割り振った番号＋１のラベル番号を割り振ります。』
|
|
219
216
|
_TL_
|
|
220
217
|
}else{
|
|
221
218
|
//『参照した画素のラベル番号が複数存在した場合は、』
|
|
@@ -226,9 +223,9 @@
|
|
|
226
223
|
min = nonzeroMin(up_m, min);
|
|
227
224
|
min = nonzeroMin(up_r, min);
|
|
228
225
|
min = nonzeroMin(left, min);
|
|
229
|
-
labeled_image[j][i] = min; //
|
|
226
|
+
labeled_image[j][i] = min; //（0以外の）『最小の番号を割り振ります。』
|
|
230
227
|
_Tm_
|
|
231
|
-
//
|
|
228
|
+
//『用いなかったラベル番号のルックアップテーブルの番号を最小の番号に書き換えます。』
|
|
232
229
|
/* ループ内でdst[0] は未使用だ（参照しない）からチェックせずにガンガン上書きするぜ*/
|
|
233
230
|
/* 用いたところもどうせminで同じ値だから気にせず上書きするぜ*/
|
|
234
231
|
dst[up_l] = nonzeroMin(dst[up_l], min);
|
|
@@ -241,7 +238,7 @@
|
|
|
241
238
|
#endif
|
|
242
239
|
}
|
|
243
240
|
}
|
|
244
|
-
showLabeledImage(); //
|
|
241
|
+
showLabeledImage(); //一行操作するごとに表示する…と、解説ページと似た感じの出力に
|
|
245
242
|
}
|
|
246
243
|
|
|
247
244
|
printf("RAW result (%dx%d):\n", h, w);
|
|
@@ -249,25 +246,24 @@
|
|
|
249
246
|
|
|
250
247
|
showPartOfDST("DST before");
|
|
251
248
|
|
|
252
|
-
/* ルックアップテーブルの詰め替え
|
|
249
|
+
/* ルックアップテーブルの詰め替え */
|
|
253
250
|
|
|
254
|
-
int conv[NL+1]; //
|
|
251
|
+
int conv[NL+1]; //
|
|
255
252
|
for (i=1;i<=NL;i++){
|
|
256
|
-
conv[i] = -1; //
|
|
253
|
+
conv[i] = -1; //すべて「未定」にする
|
|
257
254
|
}
|
|
258
255
|
conv[0] = 0;
|
|
259
256
|
dst[0] = 0;
|
|
260
257
|
|
|
261
|
-
|
|
258
|
+
//再帰的結合; ←これは回答者の勝手な命名で、専門用語ではない
|
|
262
|
-
for (i=1;i<=NL;i++){
|
|
263
|
-
|
|
259
|
+
for (j=1;j<=NL;j++){
|
|
264
|
-
|
|
260
|
+
while (dst[j] != dst[ dst[j] ])
|
|
265
|
-
|
|
261
|
+
dst[j] = dst[ dst[j] ];
|
|
266
|
-
|
|
262
|
+
}
|
|
267
|
-
|
|
263
|
+
|
|
268
264
|
showPartOfDST("recursed");
|
|
269
265
|
|
|
270
|
-
//
|
|
266
|
+
//番号を圧縮; 説明しないとわからんと思う
|
|
271
267
|
int seqn = 1;
|
|
272
268
|
for (i=1;i<=13;i++){
|
|
273
269
|
int dstQ = dst[i];
|
|
@@ -288,18 +284,17 @@
|
|
|
288
284
|
showPartOfDST("after:");
|
|
289
285
|
/* ルックアップテーブルの詰め替え；ここまで */
|
|
290
286
|
|
|
291
|
-
//
|
|
287
|
+
//ルックアップテーブルに従い結果を書き換え
|
|
292
|
-
// 上でさんざんdst[0]に好き放題したが、ここでは参照しうるので本来の値を入れる
|
|
293
288
|
dst[0] = 0;
|
|
294
289
|
for (i = 0; i <h; i++){
|
|
295
290
|
for (j = 0; j <w; j++){
|
|
296
291
|
labeled_image[j][i] = dst[ labeled_image[j][i] ];
|
|
297
292
|
}
|
|
298
293
|
}
|
|
299
|
-
//
|
|
294
|
+
//最終結果を表示
|
|
300
295
|
showLabeledImage();
|
|
301
296
|
|
|
302
|
-
printf("%d連結の連結成分の個数=%d\n", NEIGHBOR, dst[Label]); /*使われたラベルの値（最大値）の圧縮結果が領域の数*/
|
|
297
|
+
printf("%d連結の連結成分の個数=%d?\n", NEIGHBOR, dst[Label]); /*使われたラベルの値（最大値）の圧縮結果が領域の数…とは限らなそう*/
|
|
303
298
|
|
|
304
299
|
return 0;
|
|
305
300
|
}
|