카테고리

CamelACT (9)
UVa (3)
Basics (4)
Information (2)
Statistics Graph


 영상처리에서 처음 접하게 된 라벨링이라는 알고리즘이 있다. 대표적으로 쌀알 같은 물체의 개수를 세는 것을 목적으로 만든 알고리즘이다. 이미지는 배열로 나타낼 수 있고 100*100 정도의 배열에서 배경은 0이고 물체는 1이다. 쌀알을 나타내는 1은 덩어리를 이루며 가로, 세로 +-1에 해당(대각선 포함)하는 영역까지 같은 물체로 간주한다. 이 때 배경에서 쌀알의 개수를 세어 볼 수 있는 알고리즘이 바로 라벨링이다.

 첫 번째로 물체에 번호를 매겨야 한다. 이중 for문을 통해 이미지의 왼쪽 상단(0,0)부터 오른쪽 하단(99,99)까지 한 픽셀씩 처리할 것이다만약 물체에 해당하는 픽셀이라면 라벨을 매긴다. 1, 2, 3… 를 매기다 보면 최종적으로 물체의 개수가 세어질 것이다. 하지만 한 픽셀의 차이라면 같은 물체로 봐야 한다. 물체에 해당하는 픽셀에서 서, 북서, , 북동 방향의 한 픽셀에 만약 물체가 있다면 같은 물체라는 기록을 해야 한다. 이 때 필요한 것이 라벨테이블이다. 이 테이블은 다른 라벨이지만 같은 물체라는 것을 알려주는 테이블이다. 예를 들어, 현재 픽셀이 물체이고 서쪽에 라벨이 4이고 북동쪽에 라벨이 7이라면 (4, 7)이라고 저장을 해 둔 뒤, 나중에 모든 픽셀 검사를 마치고 모든 라벨 4는 라벨 7로 간주한다는 의미를 두어 이미지 배열의 4를 7로 바꾸어 준다.

 위와 같은 방법을 수행하면 인접한 픽셀은 같은 물체로 인식하게 되고 최종적으로 물체의 개수를 셀 수 있다


// start 13:30 // end 18:30 #include <stdlib.h> #include <stdio.h> #include <windows.h> #define SIZE 50 int run_test(const char ranch[SIZE][SIZE]); void main(void) { static char ranch[SIZE][SIZE]; for(int c = 0; c < 1; c++) { for(int y = 0; y < SIZE; y++) for(int x = 0; x < SIZE; x++) ranch[x][y] = '1'; // 토양 for(int c = 0; c < SIZE * SIZE; c++) ranch[rand() % SIZE][rand() % SIZE] = '0'; // 울타리 printf("%d\n", run_test(ranch)); } } int run_test(const char ranch[SIZE][SIZE]) { for(int y = 0; y < SIZE; y++) { // 문제가 [x][y] 더라도 [y][x]로 바꾸어 풀자 for(int x = 0; x < SIZE; x++) { printf("%3c", ranch[y][x]); } printf("\n"); } printf("----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- \n"); int ranchMap[SIZE][SIZE] = {0}; int label = 1; int labelTable[SIZE * SIZE * 4][2] = {0}; labelTable[0][0] = label; // 현재 labelTable[0][1] = label; // 미래 int tableCount = 1; // 서 북서 북 북동 for(int y = 0; y < SIZE; y++) { for(int x = 0; x < SIZE; x++) { if(ranch[y][x] == '1') { bool c0 = false; bool c1 = false; bool c2 = false; bool c3 = false; // 에러 방지 범위 제한 if(x - 1 >= 0 && ranch[y][x - 1] == '1') { // 서 ranchMap[y][x] = ranchMap[y][x - 1]; // 서 c0 = true; } if(y - 1 >= 0 && x - 1 >= 0 && ranch[y - 1][x - 1] == '1') { // 북서 if(c0) { if(ranchMap[y - 1][x - 1] != ranchMap[y][x - 1]){ labelTable[tableCount][0] = ranchMap[y - 1][x - 1]; // 북서 labelTable[tableCount][1] = ranchMap[y][x - 1]; // 서 tableCount++; } } else { ranchMap[y][x] = ranchMap[y - 1][x - 1]; // 북서 } c1 = true; } if(y - 1 >= 0 && ranch[y - 1][x] == '1') { // 북 if(c0) { if(ranchMap[y - 1][x] != ranchMap[y][x - 1]){ labelTable[tableCount][0] = ranchMap[y - 1][x]; // 북 labelTable[tableCount][1] = ranchMap[y][x - 1]; // 서 tableCount++; } } else if(c1){ if(ranchMap[y - 1][x] != ranchMap[y - 1][x - 1]){ labelTable[tableCount][0] = ranchMap[y - 1][x]; // 북 labelTable[tableCount][1] = ranchMap[y - 1][x - 1]; // 북서 tableCount++; } } else { ranchMap[y][x] = ranchMap[y - 1][x]; // 북 } c2 = true; } if(y - 1 >= 0 && x + 1 < SIZE && ranch[y - 1][x + 1] == '1') { // 북동 if(c0) { if(ranchMap[y - 1][x + 1] != ranchMap[y][x - 1]){ labelTable[tableCount][0] = ranchMap[y - 1][x + 1]; // 북동 labelTable[tableCount][1] = ranchMap[y][x - 1]; // 서 tableCount++; } // printf("%3d %3d, x = %3d y = %3d\n", labelTable[tableCount][0], labelTable[tableCount][1], x, y); } else if(c1){ if(ranchMap[y - 1][x + 1] != ranchMap[y - 1][x - 1]){ labelTable[tableCount][0] = ranchMap[y - 1][x + 1]; // 북동 labelTable[tableCount][1] = ranchMap[y - 1][x - 1]; // 북서 tableCount++; } // printf("%3d %3d, x = %3d y = %3d\n", labelTable[tableCount][0], labelTable[tableCount][1], x, y); } else if(c2){ if(ranchMap[y - 1][x + 1] != ranchMap[y - 1][x]){ labelTable[tableCount][0] = ranchMap[y - 1][x + 1]; // 북동 labelTable[tableCount][1] = ranchMap[y - 1][x]; // 북 tableCount++; } } else { ranchMap[y][x] = ranchMap[y - 1][x + 1]; // 북동 } c3 = true; } if(!(c0 | c1 | c2 | c3)) { // 독립이라면 ranchMap[y][x] = label++; } else { // 독립이 아니라면 } } else { ranchMap[y][x] = 0; } } } // printf("label = %3d\n", label); // for(int L = 0; L < SIZE * SIZE; L++) { // if(!labelTable[L][0]) { // break; // } // printf("%3d %3d\n", labelTable[L][0], labelTable[L][1]); // } // printf("----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- \n"); for(int m = 0; m < SIZE * SIZE; m++) { for(int y = 0; y < SIZE; y++) { for(int x = 0; x < SIZE; x++) { if(ranchMap[y][x] == labelTable[m][0]){ ranchMap[y][x] = labelTable[m][1]; } } } for(int n = 0; n < SIZE * SIZE; n++) { if(labelTable[n][0] == labelTable[m][0] && n != m // 자기 자신마져 바뀌어 버리면 더 이상 비교가 불가능 하다. ) { labelTable[n][0] = labelTable[m][1]; } if(labelTable[n][1] == labelTable[m][0] // && n != m ) { labelTable[n][1] = labelTable[m][1]; } } } // for(int m = 0; m < SIZE * SIZE; m++) { // if(!labelTable[m][0]) { // break; // } // printf("%3d %3d\n", labelTable[m][0], labelTable[m][1]); // } for(int y = 0; y < SIZE; y++) { for(int x = 0; x < SIZE; x++) { if(!ranchMap[y][x]) { // 0 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 255); printf("%3d", ranchMap[y][x]); } else { SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ranchMap[y][x] + 255); printf("%3d", ranchMap[y][x]); } } printf("\n"); } SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 0xb2); int countTable[SIZE * SIZE] = {0, }; int count = 0; for(int y = 0; y < SIZE; y++) { for(int x = 0; x < SIZE; x++) { countTable[ranchMap[y][x]]++; } } for(int m = 1; m < SIZE * SIZE - 1; m++) { if(countTable[m]) count++; } return count; }


Input and Output



신고
Basics l 2013.04.30 22:03
1 2 3 4 5 ··· 9 
get rsstistory! Tistory Tistory 가입하기!