Connected Component Labelling(연결 요소 레이블링)

• 이진 이미지에서 연결된 영역을 식별하고 라벨을 지정하는 데 사용되는 알고리즘

왜 사용?

• binary 이미지로는 특징 추출이 어려워 연산을 통해 각 특징에 심볼을 지정함. => 정보추출, 지역 레이블링

심볼릭 이미지란?

• CCL 알고리즘을 이진 이미지에 적용한 결과

• 규칙에 따라 연결된 픽셀을 별개의 영역으로 그룹화하고 고유한 레이블을 할당

1. CCL:grass fire 알고리즘

• 시드 포인트에서 시작하여 재귀적으로 인접 픽셀이 원래 색상과 일치하는 경우 대상 색상으로 채우는 방식으로 작동합니다. 더 이상 픽셀을 채울 수 없을 때까지 프로세스가 계속됩니다.

• ex) 만약 1을 발견하면 8 방향으로 레이블을 설정함. 그리고 점마다 재귀방식으로 계속 진행됨. 연산이 매우 많고, 느리다

특징

순차적 처리

• Grassfire 알고리즘은 일반적으로 위에서 아래로, 왼쪽에서 오른쪽으로 순차적으로 이미지를 처리하여 각 픽셀을 한 번만 방문하도록 합니다.

연결성

• 이 알고리즘은 인접 픽셀을 정의하는 데 사용되는 특정 규칙에 따라 4연결 또는 8연결 등 다양한 유형의 연결을 처리할 수 있습니다.

재귀 또는 반복

• 프로그래머의 기본 설정과 사용 가능한 시스템 리소스에 따라 알고리즘을 재귀적으로 또는 반복적으로 구현할 수 있습니다.

라벨 전파

• Grassfire 알고리즘은 시작 픽셀에서 같은 영역에 속하는 인접 픽셀을 통해 레이블을 전파하여 연결된 영역에 레이블을 할당합니다. 이 과정은 더 이상 연결된 픽셀을 찾을 수 없을 때까지 수행됩니다.

여러 개의 연결된 구성 요소

• 이 알고리즘은 이미지에서 여러 개의 연결된 구성 요소를 식별하고 각각 고유한 레이블을 지정할 수 있습니다.

4연결성과 8연결성

4 연결성

• 픽셀이 바로 옆의 수평 및 수직 이웃 픽셀과 연결된 것
• 덜 엄격해
• ex) 픽셀 (i, j)의 경우 4연결 이웃은 (i-1, j), (i+1, j), (i, j-1) 및 (i, j+1)

8 연결성

• 픽셀은 바로 옆의 수평, 수직, 대각선 이웃과 연결된 것
• 더 엄격
• ex) 픽셀 (i, j)의 경우 8개의 연결된 이웃은 (i-1, j), (i+1, j), (i, j-1), (i, j+1), (i-1, j-1), (i-1, j-1), (i-1, j+1), (i+1, j-1), (i+1, j+1)

=> 근데 legacy 고 잘 안쓰임ㅎ.

4 grassfire 진행순서

• 1. 왼쪽 상단 모서리(0,0)에서 시작합니다. 배경 픽셀(값 0)이므로 다음 픽셀(0,1)로 이동합니다.

• 2.(1,1)에서 첫 번째 물체 픽셀을 발견할 때까지 스캔을 계속합니다. 여기에 고유한 라벨 번호(예: 2)를 할당합니다

• 3.픽셀(1,1)의 이웃 4개를 확인합니다. 오른쪽의 이웃(1,2)은 물체의 일부입니다. 동일한 레이블 번호(2)를 할당합니다 => 산불처럼

• 4. 새로 레이블이 지정된 픽셀의 이웃을 계속 확인합니다. 픽셀 (2,2)는 (1,2)의 이웃이며 객체의 일부입니다. 동일한 라벨 번호(2)를 할당합니다
     
• 5. 마지막으로 픽셀 (2,2)의 이웃을 확인합니다. 픽셀(2,3)은 이웃 픽셀이자 객체의 일부이므로 동일한 레이블 번호(2)를 할당합니다:
     
• 6. 더 이상 객체 픽셀이 남아 있지 않습니다. 알고리즘이 완료되었습니다.
     

2. Boundary tracing(Contour-tracing-based method)

• 이진 이미지에서 객체의 경계 또는 윤곽을 식별하고 추적하는 데 사용되는 기술

• 모든 픽셀에 레이블을 지정하는 그래스파이어 알고리즘과 달리, 경계 추적은 오브젝트의 경계를 형성하는 윤곽선 픽셀에만 초점

<1987> 런의 시작점에만

• 레이블의 실행은 시작점에만 할당.
• 시작점 식별 후 다음 라벨 지정에 중점
• 모든 경계 픽셀을 고려하지 않아서 효율적x

<2004> 모든 경계화소에

• 모든 경계 픽셀에 라벨이 할당. => 포괄적인 라벨링 및 추적 => 효율, 정확도 향상됨

• 경계에 있는 화소를 추적.

• 앞에꺼만 보고 전달.

• 전파를 해서 와.2로 경계타면서 지워버려.
  런의 시작위치인데도 1. 경계를 다시 추적하면서 2로 놓고 지워버림

GrassFire와의 차이

grassFire

• 산불처럼 타고타고 들어가서 모든요소를 탐색하지 않아.

=> 연결된 구성요소에 레이블 지정하는데 효율적. But, 전체 이미지 탐색 안해서 놓치는거 있을 수 있음.

Contour-tracing-based method

• 이미지 전체를 체계적으로 스캔하여 마주치는 각 물체의 경계를 추적.

=> 전체이미지 탐색 O, 포괄적. But 모든 픽셀 방문해 속도 느려

진행과정 예시

1. 왼쪽 상단 모서리에서 시작하여 첫 번째 객체 픽셀(값 1)을 찾을 때까지 이미지를 왼쪽에서 오른쪽으로, 위에서 아래로 스캔합니다. 이 경우 위치 (1,1)에 있습니다.

2. 이 픽셀에 고유한 라벨 번호를 할당합니다(이 예에서는 2를 사용하겠습니다). 레이블이 지정된 이미지를 업데이트합니다:

3. 모든 경계 픽셀에 동일한 레이블 번호(2)를 할당하여 시계 방향으로 주변을 따라 이동하여 개체의 경계를 추적합니다. 이 예제에서는 경계 추적 후 레이블이 지정된 이미지가 다음과 같이 표시됩니다:
   

---

시작 방향은 8+current orient - 2 (현재의 방향)

3. Raster-scan-based method(래스터 스캔)

4. Run-based method(런 베이스)