Union-Find 알고리즘을 이용하여 영역 분할 과정이다. 각각의 픽셀에서 4방향으로 연결된 픽셀이 속한 영역 merge 할 수 있는지를 시도한다. merge 조건은 현재 픽셀의 그레이 값과 인접 영역의 평균 그레이 값의 차이가 주어진 임계값보다 작은 경우다.
$$\tt \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)에 잘 구현이 되어 있다.
struct Universe {
int n;
std::vector<int> sizes;
std::vector<int> sums;
std::vector<int> parent;
Universe(int n, BYTE *image) {
this->n = n;
parent.resize(n, -1); // all nodes are root;
sizes.resize(n, 1);
sums.resize(n);
for (int i = 0; i < n; i++)
sums[i] = image[i];
}
int FindCompress (int node) { // find root node;
if ( parent[node] < 0 ) return node; // root-node;
else return parent[node] = FindCompress (parent[node]);
// 찾음과 동시에 depth을 줄인다;
}
int Find(int node) { // find root;
while (parent[node] >= 0) node = parent[node];
return node;
}
bool Predicate(int root1, int root2, int thresh) {
double diff = double(sums[root2]) / sizes[root2]
- double(sums[root1]) / sizes[root1];
return fabs(diff) < thresh;
}
void Merge(int root1, int root2) {
sums[root2] += sums[root1];
sizes[root2] += sizes[root1];
parent[root1] = root2; // r2 트리로 합병함;
}
};
// root 노드는 분할영역의 픽셀 갯수와 픽셀 값의 합을 저장한다.
// 처음 각 픽셀이 root 이고, 픽셀 갯수는 1, 픽셀값은 자신의 픽셀값을 저장;
BOOL UnionFindAverage(BYTE *image, int width, int height, int thresh) {
Universe *UF = new Universe(width * height, image);
// 4-connectivity:
// 첫행; LEFT 픽셀이 속한 영역의 평균값과 차이가 thresh 내이면 left로 합병;
for ( int x = 1; x < width; x++ ) {
int left = UF->FindCompress (x - 1);
int curr = UF->FindCompress (x);
if (UF->Predicate(curr, left, thresh))
UF->Merge(curr, left);
}
//Flatten(y=0);
for (int x = 0; x < width; x++) UF->FindCompress(x);
for ( int y = 1, pos = y * width; y < height; y++ ) {
// x = 0; TOP 픽셀이 속학 영역과 합병 체크;
int up = UF->FindCompress (pos - width);
int curr = UF->FindCompress (pos);
if (UF->Predicate(curr, up, thresh))
UF->Merge(curr, up);
pos++;
// TOP-LEFT 픽셀 영역과 합병 체크;
for ( int x = 1; x < width; x++, pos++ ) {
int left = UF->FindCompress(pos - 1);
int curr = UF->FindCompress(pos);
// left와 합병이 되면 left가 up과 합병이 되는지 확인;
if (UF->Predicate(curr, left, thresh)) {
UF->Merge(curr, left);
curr = left;
}
int up = UF->FindCompress (pos - width);
if ((curr != up) && (UF->Predicate(curr, up, thresh)))
UF->Merge(curr, up);
}
// Flatten(y>0)
for (int x = 0; x < width; x++) UF->FindCompress(x + y * width);
}
// 평균 이미지 생성;
for ( int k = width*height; k-->0;) {
int root = UF->Find(k);
int avg = int(double(UF->sums[root]) / UF->sizes[root] + 0.5);
image[k] = avg > 255 ? 255 : avg;
}
delete UF;
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 |
