Connected Component Analysis

Connected Component Analysis 

이미지 안의 물체를 찾아내어 분석하기 위한 목적으로 thresholding에 기반한 이진화 기술들이 개발되었으며, 이진화 결과에서 노이즈를 제거하고, 결과들을 보다 정교화하기 위해서 mathematical morphology 기술들이 개발되었다. Morphology까지 거친 이미지들을 이용하면 물체를 구분 (segmention)하고, 물체를 인식 (object recognition)할 수 있는데, 그 전에 픽셀들을 물체 단위로 구분하여야 한다. 

Connectedness

하나의 물체를 구성하는 픽셀들은 이미지에서 서로 연결된 형태로 나타나게 되는데, 픽셀들이 연결되었는지를 판단하는 방법에는 2가지가 있다. 하나는 4-adjacency인데, 이것은 픽셀의 상하좌우만 연결로 인정하는 것이고, 다른 하나인 8-adjacency는 대각선에 대해서도 연결을 인정하는 것이다. 

문제는 이미지에 4, 8 adjacency를 적용했을 때 제대로된 결과를 얻기가 어려운 경우가 생긴다는 것이다. 예를 들어, 다음과 같은 이미지가 있다고 하자.

여기에 4나 8 adjacency를 적용했을 때, 원하는 결과를 얻기가 어렵다. 아래에서 좌측에 있는 그림은 8 adjacency를 적용한 결과인데, 백그라운드들이 하나로 연결된 것으로 분류한다. 하지만, 명확히는 백그라운드는 2개의 중앙링에 의해서 3부분으로 나누어져야 한다. 우측에 있는 그림은 4 adjacency를 기반으로 해서 찾은 connected component들인데, 이것은 전혀 원하는 결과가 아니다.

 

하지만, 4와 8 adjancency를 번갈아가며 적용하는 방법을 사용하면 조금 낫다. 아래 그림이 원하는 결과이다. 백그라운드가 흰색으로 구분되었고, 초록색, 빨간색으로 두개의 링이 구분되었으며, 살구색과 파란색으로 링 사이의 공간이 제대로 구분되었음을 알 수 있다. 이것을 얻기 위해서, 4, 8 adjacency를 번갈아가며 적용하였다. 맨 바깥쪽에는 4, 바깥쪽 링에는 8, 이런 식으로 교대로 적용한 결과이다.

Connected Component 찾아내기

​

Binary image에서 물체를 구성하는 연결된 픽셀들을 찾아내는 알고리즘은 예상 외로 간단하다. 알고리즘은 2-pass로 구성되는데, 첫 번째 패스에서는 4 혹는 8 adjacency 어느 것을 이용하건 간에, 좌에서 우로, 위에서 아래로 한 픽셀씩 검사하면서 previous neighboring pixel과 동일한 label을 지정하면 된다. 만약 최초 픽셀이라면 새로운 label을 할당하면 된다. x로 표시된 픽셀의 previous neighboring pixel들은 아래 그림과 같이. 위쪽 혹은 왼쪽에 위치해있는 픽셀들로서, 왼쪽 그림은 8 adjacency의 경우, 오른쪽 그림은 4 adjacency의 경우의 previous neighboring pixel들을 보여준다.



두 번째 패스에서는 다른 label이지만 같은 영역에 속하는 label들을 찾아서, label을 하나로 합치는 단계를 수행한다. 통합할 label을 찾는 것은, 어느 픽셀에 대해서 previous neighborng label이 두 개 이상일 경우, 이 들 label들은 서로 같은 label이므로 하나로 합쳐져야 된다. label 합치는 과정을 쉽게 하기 위해서, label이 정수라고 한다면, 서로 다른 label들을 합칠 때는, 낮은 숫자를 갖는 label로 통합하도록 하면된다.

OpenCV에서는 connected component를 찾기 위한 함수로 findCountours를 제공한다. 이 함수의 원래 목적은 이미지에서 물체의 윤곽선을 구성하는 픽셀들을 구한다. 사용방법은 아래와 같다.

vector<vector<Point>> contours;

- 수행 결과 여러 개의 윤곽선들이 나오게 되는데, 이 윤곽선들이 배열을 구성하고, 각 배열의 요소는 윤곽선인데, 윤곽선은 이를 구성하는 픽셀들으 배열이다.

vector<Vec4i> hierarchy;

- 윤곽선마다 고유의 번호를 매겨, 윤곽선 간의 관계를 표시한다. 각 윤곽선은 4개의 정보를 갖는데, 첫 번째는 다음 윤곽선, 두 번째는 이전 윤곽선, 세 번째는 안에 포함된 윤곽선, 네 번째는 밖을 감싸고 있는 윤곽선. 만약 이러한 정보가 필요없다면 음수로 채워진다.

findContours(binary_image, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_NONE);

contour에 의해 물체 윤곽선을 구했다면, openCV함수를 이용해서 물체들을 각각 다른 색으로 칠할 수 있다. 예를 들어 다음 코드를 이용하면 된다.

Scalar colour(255, 0, 0);

blue색을 지정

drawContours(contours_image, contours, contour, colour, CV_FILLED, 8, hierarchy);

contours_image: 물체 윤곽선이 그려지는 이미지

contours: 함수 findContours를 이용해서 구한 윤곽선들

contour: 어느 윤곽선인지를 지정하는 숫자

CV_FILLED: 윤곽선 내부를 채운다.

hierarchy: 윤곽선 간의 관계로 함수 findContour에 의해 구해진 것이다. 이 정보는 윤곽선 안에 또 다른 윤곽선이 포함되어 있을 경우, 내부 윤곽선을 칠하는 범위에서 제외하기 위해서 사용된다.

위 함수들을 이용한 예는 아래와 같다. 맨 왼쪽 사진은 입력이미지 위에다가 발견된 contour들을 청색으로 표시한 것이다. 중간 것과 이진화 이미지이며, 여기에 closing morphology (20x20 isotropic structuring element 사용) 연산을 적용한 것이 오른쪽 결과이다.

위 결과를 얻기 위한 프로그램의 소스코드는 아래와 같다. line 34 ~ 36의 함수 imshowAfterResize( )는 인수로 주어진 (이 경우 320) 값으로 이미지의 폭을 resizing한 후 display하는 함수로 자체 제작한 함수이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

int main() { Mat org_img; org_img = imread(IMG_NAME); if (org_img.empty() == true) { cout << "Unable to read " << IMG_NAME << endl; return 0; } Mat gray_img; cvtColor(org_img, gray_img, CV_BGR2GRAY); Mat bin_img; adaptiveThreshold(gray_img, bin_img, 255.0, ADAPTIVE_THRESH_GAUSSIAN_C, THRESH_BINARY_INV, 101, 0); Mat closed_img; Mat structuring_element(20, 20, CV_8U, Scalar(1)); morphologyEx(bin_img, closed_img, MORPH_CLOSE, structuring_element); // find contours vector<vector<Point>> contours; vector<Vec4i> hierarchy; Scalar colour(255, 0, 0); Mat copied_closed_img = closed_img.clone(); findContours(copied_closed_img, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_NONE); for (int i = 1; i < contours.size(); i++) { drawContours(org_img, contours, i, colour, CV_FILLED, 8, hierarchy); } imshowAfterResize("original image", org_img, 320); imshowAfterResize("bin image", bin_img, 320); imshowAfterResize("closed image", closed_img, 320); waitKey(0); return 0; }