연결 요소 라벨링(CCL)은 연결 요소 분석, 블롭 추출, 영역 라벨링 또는 블롭 발견이라고도 하며, 주어진 휴리스틱에 따라 연결 요소의 부분 집합에 고유한 라벨을 부여하는 그래프 이론의 알고리즘적 응용이다. 컴퓨터 비전에서 이진 디지털 이미지의 연결된 영역을 감지하는 데 사용되지만, 컬러 이미지와 고차원 데이터도 처리할 수 있다. CCL은 이미지 분할과 구별되며, 블롭 추출은 블롭 감지와 관련이 있지만 다르다.
실제로 CCL은 입력 데이터로 구성된 그래프에서 작동하며, 여기서 정점은 픽셀이나 요소를 나타내고 간선은 이웃 간의 연결성을 나타낸다. 알고리즘은 그래프를 탐색하여 연결성과 상대 값에 따라 정점에 라벨을 할당한다. 라벨링 후 그래프는 부분 집합으로 분할될 수 있으며, 이를 통해 원래 정보를 복구하고 개수 세기, 필터링, 블롭 추적과 같은 작업을 위해 처리할 수 있다.
정의 및 용어
연결 요소 라벨링이라는 용어는 학술 문헌에서 일관되게 사용되는 반면, 연결 요소 분석(CCA)은 용어와 문제 정의 모두에서 다양하다. Rosenfeld 등은 CCL을 이진 입력 이미지의 동일한 연결 요소와 관련된 위치가 고유한 라벨을 갖는 라벨링된 이미지를 생성하는 것으로 정의한다. Shapiro 등은 CCL을 입력이 이진 이미지이고 출력이 각 픽셀의 라벨이 해당 연결 요소를 고유하게 식별하는 정수인 기호 이미지인 연산자로 설명한다.
CCA의 정의에 대한 합의는 없으며, 종종 CCL과 상호 교환적으로 사용된다. Shapiro 등의 더 광범위한 정의는 CCA가 검은 픽셀의 연결 요소 라벨링, 구성 요소 영역의 속성 측정 및 의사 결정으로 구성된다고 명시한다. 이 문서는 이러한 관점을 통합하는 더 넓은 해석을 채택한다.
그래프 구성 및 연결성
관련 입력 데이터에서 그래프가 구성되며, 정점은 비교 휴리스틱에 필요한 정보를 포함하고 간선은 연결된 이웃을 나타낸다. 알고리즘은 그래프를 탐색하여 연결성과 상대 값에 따라 라벨을 할당한다. 연결성은 매체에 의해 결정되며, 이미지 그래프의 경우 일반적인 이웃에는 4-연결(북, 남, 동, 서) 및 8-연결(대각선 포함)이 포함된다.
라벨링 후 그래프는 부분 집합으로 분할될 수 있으며, 이후 원래 정보를 복구하고 처리할 수 있다. 이 접근 방식은 임의의 차원으로 일반화되지만, 시간 및 공간 복잡도는 그에 따라 증가한다.
한 번에 하나의 구성 요소 알고리즘
한 번에 하나의 구성 요소 알고리즘은 빠르고 구현이 간단하며 그래프 탐색 방법에 기반한다. 이는 Vincent와 Soille의 watershed 분할 알고리즘의 일부이며, 다른 구현도 존재한다. 이 방법은 연결된 픽셀의 인덱스를 유지하기 위해 연결 리스트를 사용하며, 깊이 우선 또는 너비 우선 탐색의 선택은 이 응용 프로그램에 실질적인 차이가 없다.
이 알고리즘은 전경과 배경 픽셀이 있는 이진 이미지를 가정하며, 전경의 연결 요소를 라벨링하는 것을 목표로 한다. 단계:
- 첫 번째 픽셀에서 시작하여 현재 라벨을 1로 설정한다.
- 픽셀이 전경이고 라벨이 없으면 현재 라벨을 할당하고 큐에 추가한다. 그렇지 않으면 다음 픽셀로 이동한다.
- 큐에서 요소를 꺼내고 (연결성 유형에 따라) 이웃을 검사한다. 이웃이 전경이고 라벨이 없으면 현재 라벨을 할당하고 큐에 추가한다. 큐가 빌 때까지 반복한다.
- 다음 픽셀로 이동하고 현재 라벨을 증가시킨다.
픽셀은 큐에 추가되기 전에 라벨링되며, 각 전경 픽셀의 이웃은 한 번만 검사된다. 배경 픽셀의 이웃은 검사되지 않는다. 의사 코드는 두 개의 큐를 사용하여 픽셀 처리를 관리하여 효율적인 탐색을 보장한다.
컴퓨터 비전에서의 응용
CCL은 종종 임계값 단계 후에 이진 이미지에서 연결된 영역을 감지하기 위해 컴퓨터 비전에서 널리 사용된다. 블롭 추출은 회색조 및 컬러 이미지에도 적용될 수 있다. 블롭은 개수, 필터링 및 추적될 수 있으며, 이는 이미지 인식 시스템 및 인간-컴퓨터 상호 작용 인터페이스에서 CCL을 유용하게 만든다.
예를 들어, Machine learning 파이프라인에서 CCL은 객체 감지 또는 분할 작업을 위해 이미지를 전처리할 수 있으며, U-Net 아키텍처와 같은 기술을 보완한다. 또한 의료 이미지 분석, 산업 검사 및 자율 주행을 위한 Artificial intelligence 시스템에서도 사용되며, 연결된 영역을 식별하는 것이 중요하다.
관련 개념 및 확장
CCL은 강도 변화에 기반한 관심 영역을 식별하는 데 초점을 맞춘 블롭 감지와 관련이 있지만 구별된다. 대조적으로, CCL은 연결성에 기반한 모든 연결 요소를 라벨링한다. 이 알고리즘은 의료 이미징의 3D 볼륨과 같은 고차원 데이터로 확장될 수 있으며, 계산 비용이 증가한다.
Deep learning 및 Neural network 모델의 최근 발전은 분할을 위한 학습된 접근 방식을 이끌었지만, CCL은 후처리 및 분석을 위한 기본 도구로 남아 있다. 단순성과 효율성 덕분에 컴퓨터 비전 라이브러리 및 프레임워크에서 필수 요소가 되었으며, 종종 Data Augmentation 및 Loss Functions와 함께 훈련 파이프라인에서 사용된다.
같이 보기
- Computer vision
- image-segmentation
- blob-detection
- graph-theory