이미지 Labeling 알고리즘(fu chang)

현재까지 가장 빠른 레이블링 알고리즘은 중국 교수 Chang, Fu가 2004년에 쓴 논문

Chang, Fu, Chun-Jen Chen, and Chi-Jen Lu. "A linear-time component-labeling algorithm using contour tracing technique."computer vision and image understanding 93.2 (2004): 206-220.

입니다. 4-연결, 8-연결 레이블링과는 다르게 한번의 탐색으로 이미지의 연결성을 검사해 레이블링 합니다.

 위 논문의 레이블링 방법은 크게 4방법으로 소개하고 있습니다.

기본적으로 레이블 순서는 위에서 오른쪽 방향으로 탐색하며 이진 이미지를 대상으로 수행합니다.

 첫번째로 Figure1.a의 경우 탐색중에 색인되지않은 픽셀을 만나면 외곽선을 추적(시계방향)합니다. 

외곽선 탐색 한 이후로 다시 A픽셀로 돌아오면 외곽선 탐색을 종료합니다. 외곽선 탐색시 모두 A픽셀과 같은 레이블 번호로 지정합니다.

 두번째 사진 Figure1.b를 보면 외곽선을 추적하다 보면 같은 줄 안에 비어있는 홀을 확인할 수 있습니다. 

B 까지 A'와 같은 레이블 번호를 할당하고, 이때 B를 안쪽 외곽선으로 지정하고안쪽 외곽선 또한 같은 레이블 번호로 지정합니다.(안쪽 영역 외곽선 추적)

Figure1.c을 보면 내부 외과선 추적시 반시계 방향으로 추적합니다. 이때 Figure1.d와 같이 검정 픽셀을 오른쪽 방향

으로 탐색할 경우 B'와 같은 레이블 번호를 할당합니다.