[Image Processing] Blob Algorithm (Connected component Labeling)

참고자료 1 : http://martinblog.net/826

참고자료 2 : http://blog.daum.net/shksjy/198

참고자료 3 : https://en.wikipedia.org/wiki/Connected-component_labeling

참고자료 4 : http://docs.opencv.org/2.4/modules/features2d/doc/common_interfaces_of_feature_detectors.html

Blob Algorithm

  Blob Labeling 알고리즘은 영상처리 분야에서 Labeling을 할 때 주로 쓰는 방법으로서, 인접한 화소에 모두 같은 번호(Label)을 붙이고 연결되지 않은 다른 성분에는 다른 번호를 붙이는 것이다. heuristic 기반의 방법으로 labeling 하는 것이며, 이미지 안에 연결되어 있는 객체가 몇개인지 알아내는 것이다. image recognition system 또는 human-computer interaction 분야에서 필수적으로 쓰이는 방법이다. 

  라벨링 개념은 아래 표와 같다. OpenCV 3.0 버전이 나올 때 Blob Algorithm(Connected-component labeling, connected-component analysis, blob extraction, region labeling, blob discovery, or region extraction)이 추가되었다. 

					4
	2	2	2		4	4
	2	2	2		4
	2	2	2				1
			2				1
							1
			3	3	3	3
				3	3

    

  레이블링을 하는 방식에는 4방향(십자모양), 8방향 방식(대각선이 추가된 모양)이 있다. vertices 는 comparison heuristic으로써 필요한 정보를 포함하고 있고, 'neighbors'로 연결된 영역을 가리키는 edges로 구성이 되어있다. 

알고리즘을 간략히 설명해보자면,

1. binary image를 기반으로 수행되며 처음에 이미지의 첫번째 픽셀을 시작으로 current label(curlab) 을 지정한다. 

2. 그 픽셀이 foreground pixel이고, 아직 label 되지 않았다면 curlab으로 지정하고, queue에 추가한다. 만약 background pixel이고, 이미 label 되었다면 foreground pixel이고 label 되지 않는 pixel을 찾을 때 까지 반복한다.

3. 모둔 수행이 끝나게 되면 queue에서 element를 꺼낸다. 그리고 neighbor을 보고서 (연결된 유형에 따라) foreground pixel이고 이미 라벨링 되지 않았다면 curlab 라벨을 부여하고, queue에 추가한다. 이 과정을 queue에 요소가 없을 때 까지 반복한다.

4. 다시 2번 과정으로 가서 다음픽셀에 대해 과정을 수행하고, curlab 을 1 증가하는 과정을 거친다.

Blob 알고리즘의 코드는 OpenCV Reference를 참조하도록 하는게 좋을 듯 하다.