Union-Find 알고리즘을 이용하여 영역 분할 과정이다. 각각의 픽셀에서 4방향으로 연결된 픽셀이 속한 영역 merge 할 수 있는지를 시도한다. merge 조건은 현재 픽셀의 그레이 값과 인접 영역의 평균 그레이 값의 차이가 주어진 임계값보다 작은 경우다.
$$\text{merge 조건: }\quad | 그레이 값- \text{인접 영역 평균값}| < threshold$$
컬러 영상의 경우에는 RGB 채널에 조건을 부여하거나 gray level만 이용해서 판단할 수 있다. root node 수만큼의 분할 영역이 만들어지고, 임계값이 클수록 분할된 각 영역의 사이즈가 커진다.
gray = 0.2989 * r + 0.5870 * g + 0.1140 * b ;
같은 평균 픽셀값을 가지고 있더라도 4-방향으로 서로 연결된 영역이 아니면 합병되지 못하고 서로 다른 영역으로 남는다. 이를 하나의 영역으로 만들려면 분할된 영역을 다시 검사를 하는 과정이 필요하다. 자세한 과정은 Statistical Region Merge(SRM) 알고리즘(kipl.tistory.com/98)에 잘 구현이 되어 있다.
int FindCompress(int node, int *parent) { // find root node;
if (parent[node] < 0) return node; // root-node;
else return parent[node] = FindCompress(parent[node], parent); //찾음과 동시에 depth을 줄임
}
BOOL Predicate(int r1, int r2, int thresh, int *sum, int *sizes) {
double diff = double(sums[r2]) / sizes[r2] - double(sums[r1]) / sizes[r1];
return fabs(diff) < thresh;
}
// root가 r1인 집합(단일픽셀)을 root가 r2인 집합으로 합병한다;
// 전체 픽셀합과 픽셀수를 update한다;
void Merge(int r1, int r2, int *sums, int *sizes, int *parent) {
sums[r2] += sums[r1];
sizes[r2] += sizes[r1];
parent[r1] = r2;
return TRUE;
}
// root 노드는 분할영역의 픽셀 갯수와 픽셀 값의 합을 저장한다.
// 처음 각 픽셀이 root 이고, 픽셀 갯수는 1, 픽셀값은 자신의 픽셀값을 저장;
BOOL UnionFindAverage(BYTE *image, int width, int height, int thresh) {
int npixs = width * height;
int* parent = new int [npixs]; // parent table;
int* sums = new int [npixs];
int* sizes = new int [npixs];
// initial setting;
for (int pos = 0; pos < npixs; pos++) {
parent[pos] = -1; // 각 픽셀이 root임;
sums[pos] = image[pos];
sizes[pos] = 1;
}
// 첫행; LEFT 픽셀이 속한 영역의 평균값과 차이가 thresh 이내이면 left로 합병함;
for (int x = 1; x < width; x++) {
int left = FindCompress(x - 1, parent);
int curr = FindCompress(x, parent);
if (Predicate(curr, left, thresh, sums, sizes))
Merge(curr, left, sums, sizes, parent);
}
//Flatten(y=0);
for (int x = 0; x < width; x++) FindCompress(x, parent);
for (int y = 1, pos = y * width; y < height; y++) {
// x = 0; up 픽셀이 속학 영역과 합병 체크;
int up = FindCompress(pos - width, parent);
int curr = FindCompress(pos, parent);
if (Predicate(curr, up, thresh, sums, sizes))
Merge(curr, up, sums, sizes, parent);
pos++;
// UP-LEFT 픽셀 영역과 합병 체크;
for (int x = 1; x < width; x++, pos++) {
int left = FindCompress(pos - 1, parent);
int curr = FindCompress(pos, parent);
// left와 합병이 되면 left가 up과 합병이 되는지 확인; 안되면 up과 합병시도;
if (Predicate(curr, left, thresh, sums, sizes)) {
Merge(curr, left, sums, sizes, parent);
curr = left;
}
int up = FindCompress(pos - width, parent);
if ((curr != up) && (Predicate(curr, up, thresh, sums, size)))
Merge(curr, up, sums, sizes, parent);
}
// Flatten(y>0);
for (int x = 0; x < width; x++) FindCompress(x + y * width, parent);
}
// 평균 이미지를 만듬(input is overwritten);
for (int pos = 0; pos < npixs; pos++) {
// Find root;
int node = pos;
while (parent[node] >= 0) node = parent[node];
int a = int(double(sums[node]) / sizes[node] + 0.5);
image[pos] = a > 255 ? 255 : a;
};
delete [] parent;
delete [] sums;
delete [] sizes;
return TRUE;
};
728x90
'Image Recognition' 카테고리의 다른 글
| Octree Quantization (0) | 2021.01.12 |
|---|---|
| Median-Cut 컬러 양자화 (0) | 2021.01.12 |
| Multilevel Otsu Thresholding (0) | 2021.01.09 |
| Binary Image에서 Convex Hull (0) | 2021.01.06 |
| Kuwahara Filter (2) | 2020.12.28 |
