Connected-component labeling
머신비전, 영상처리 분야에서 Connected-component labeling 알고리즘에 대해 알아보겠습니다.
0. Overview
Connected-component labeling은 아래와 같이 여러 가지로 불립니다.
Connected-component labeling (CCL), connected-component analysis (CCA), blob extraction, region labeling, blob discovery, region extraction
[출처] en.wikipedia.org/wiki/Connected-component_labeling
Connected-component labeling은
아래의 그림처럼
기존의 바이너리 이미지에서
연결되어 있는 객체를 찾아내는 것입니다.
[출처] www.slideserve.com/yitro/ee465-introduction-to-digital-image-processing
위의 그림은 여러가지 색으로 다른 객체를 표현하였고,
각 개체의 픽셀에 번호(1,2,3...)를 붙어 표현하게 됩니다.
[출처] https://www.cs.auckland.ac.nz/courses/compsci773s1c/lectures/ImageProcessing-html/topic3.htm
그리고 픽셀의 연결되었다고 판단하는 방법은
위의 그림과 같이 2가지 방법이 있습니다. (4-neighbors and 8 neighbors)
현재 (x,y)에 대해 색이 칠해진 부분이 연결(이웃)되었다고 판단하는 거죠.
1. 알고리즘
실전 알고리즘에 앞서 아래의 영상을 보시면 이해하기 쉽습니다.
[출처] www.youtube.com/watch?v=ticZclUYy88
Sonka, Milan, Vaclav Hlavac, and Roger Boyle. Image processing, analysis, and machine vision. 4th ed. Cengage Learning, 2014. p333~334.
간단하게 말하자면,
Connected-component labeling 알고리즘은
1st Pass는
mask를 이용하여 이웃하는지 판별하여 Label을 만들고,
Label collisions된 것은 Equivalence table을 만듭니다.
2nd Pass때 Equivalence table을 이용하여 Label collisions을 해결하고
최종 결과를 만들어 냅니다.
2. python 구현
사용한 라이브러리는 위와 같습니다.
이미지를 불러오고 threshold를 기준으로 바이너리 이미지를 만들어줍니다.
여기서 bin_img = gray_img.copy() 대신
bin_img = gray_img 의 사용을 권하지 않습니다.
bin_img = gray_img 를 사용할 경우
bin_img의 값이 바뀌면 gray_img의 값도 같이 변하기 때문입니다.
알고리즘에서 사용한 mask는 3x3행렬로 구현했습니다.
최종적인 함수이며,
equivalence table(변수 equivalent)은 다음과 같습니다.
추가적인 부분입니다.
threshold=10,000로 설정하여,
해당 threshold를 넘는 픽셀 개수를 가진 레이블만 보이게 하는 함수입니다.
결과를 보시면,
각 레이블과 그에 해당하는 픽셀 갯수를 알 수 있습니다.
또한, 4-neighbors와 8-neighbors에는 약간의 차이가 있는데
오른쪽 확대한 그림을 보시면,
8-neighbors를 사용하였을 경우 대각선부분으로 연결되어
4-neighbors보다 같은 레이블을 가진 영역이 넓어졌음을 알 수 있습니다.
해당 소스는 아래에서 보실 수 있습니다.
github.com/jstar0525/MachineVision/tree/main/Connected-component%20labeling
jstar0525/MachineVision
Machine Vision Algorithm. Contribute to jstar0525/MachineVision development by creating an account on GitHub.
github.com