[Digital Image Processing] 08. Image Segmentation: Color Thresholding

해당 글은 건국대학교 김은이 교수님의 디지털 영상 처리 수업 내용을 정리한 글입니다.

 

Image Representation

 

아날로그 영상 F(x,y)은 공간 좌표 (x,y)와 밝기(intensity)가 연속적이며 무한한 정밀도를 갖습니다. 한편, 디지털 영상 I(x,y)는 공간과 밝기가 모두 이산적(discrete)으로 샘플링된 2D 배열입니다. 영상의 종류로는 다음과 같습니다:

 

1. Gray-scale: 픽셀당 하나의 밝기 값만 가집니다.

2. Multi-spectral: 픽셀당 벡터 값(예: RGB)을 가집니다.

3. Binary: 픽셀 값이 0(검은색) 또는 1(흰색)만 존재합니다.

4. Labeled Image: 픽셀 값이 유한한 심볼(레이블)로 표현됩니다. 이를 pseudo-color 영상이라고도 합니다.

 

Image Segmentation

 

위 그림들은 Labeled Image의 예시입니다.

 

Image Segmentation

 

image segmentation

 

image segmentation이란 이미지를 서로 연결된 픽셀 집합(regions)들로 나누는 연산입니다. 위 그림은 각각의 regions들이 segmentation된 예시입니다.

color thresholding

 

위 과정은 가장 기초적인 분할 방법인 thresholding 예제입니다. 표지판(STOP) 영상에서 특정 조건을 만족하는 픽셀만 추출합니다. 하지만 이는 고정된 threshold 값을 사용하면 상황이 달라짐에 따라(예: 햇빛의 변화) 결과가 크게 영향을 받을 수 있습니다.

 

한편, threshold는 global(local) thresholding과 multiple thresholding으로 나눠집니다. 단일 임계값 T를 사용하면 결과는 0 또는 1이 됩니다. 다중 임계값(예: T1, T2)을 사용하면 픽셀들을 n개의 구간으로 분류할 수도 있습니다:

thresholding

 

적절한 threshold 값을 설정하는 것은 중요합니다. 히스토그램의 peak(봉우리) 사이의 간격, 노이즈의 양, 객체와 배경의 상대적 크기 등을 고려해야합니다:

key factor

 

위 그림처럼 이미지에 점점 노이즈가 들어갈 수록 히스토그램의 peak가 희미해지며, 정확한 threshold를 통해 두 peak를 나누기 힘들어집니다. 따라서 contrast stretching 등의 전처리 후 thresholding을 수행하는 것이 효과적입니다.

 

Otsu's Method

 

이렇게 임계값을 직접 설정해주는 방식이 아닌, 자동으로 임계값을 설정해주는 방법이 Otsu's method입니다. 이는 히스토그램이 두 개의 봉우리(Bimodal)를 가진다고 가정합니다(만약, histogram이 multimodal이라면 local하게 otsu 알고리즘을 사용하면 됩니다). 이때 두 그룹(배경, 전경)으로 나누었을 때, 그룹 내 분산(within-group variance)의 가중 합을 최소화하는 t를 찾습니다. otsu 알고리즘은 공간적 정보(spatial coherence)를 사용하지 않고 오직 히스토그램 통계만 사용한다는 특징이 있습니다(그래서 이후 connected component labeling으로 공간 정보를 보완합니다).

 

weighted within-class 분산은 다음과 같이 정의됩니다:

weighted within-class variance

 

이때 q1(t), q2(t)는 클래스 1과 2가 발생할 확률(가중치)이며, P(i)는 히스토그램에서 i번째 레벨의 확률입니다:

where the class probabilities are estimated as(t = threshold):

 

mu1(t), mu2(t)는 각 클래스의 평균값입니다:

and the class means are given by:

 

최종적으로 각 클래스의 개별 분산 sigma1(t), sigma2(t)를 구하는 수식이 나옵니다:

finally, the individual class variances are:

 

t를 1부터 256까지 변화시키며, sigma_w(t)가 최소가 되는 t를 선택해야합니다:

ex

 

해당 방법을 t를 [1,256]까지 변화시키면서 분산의 최소값을 찾는 것은 중복된 연산을 많이 포함하기 때문에, class 내부의 분산을 줄이는 대신, class 간의 분산을 최대화하는 방향으로 재귀적인 방식으로 수행하는 두 번째 알고리즘이 실제로 많이 사용됩니다.

 

임의의 히스토그램의 전체 분산 sigma는 임계값 t와 무관하게 일정합니다. 따라서 수식적으로 그룹 내 분산 최소화는 그룹 간 분산 최대화와 동일합니다. 이는 sigma = sigma_withinclass + sigma_betweenclass가 성립하기 때문입니다.

 

조금의 수식 변환을 수행하면 전체 분산은 다음과 같이 전개될 수 있습니다:

total variance

 

이때 between-class 분산을 늘리면 되는데, 이는 recursive algorithm을 통해 t에서 간단한 연산만으로 t+1을 갱신할 수 있습니다. 이로 인해 계산 효율이 이전 otsu 알고리즘에 비해 매우 높아지게 됩니다:

recursive algorithm

 

Expansion of Otsu's method

 

만약 히스토그램이 bimodal(봉우리 2개)이 아닐 때는 어떻게 해야할까요? 봉우리가 3개 이상이면 단일 임계값으로 분리하기 어렵습니다. 따라서 이는 otsu's method를 수행하는 intensity 범위를 수동으로 입력하여, local threshold를 여러 번 수행해야 합니다(아니면 일단 전체 범위에 대해서 otsu'method를 사용한 다음, within-class variance가 높은 class에 대해서 다시 한 번 otsu's method를 사용하는 방법도 있습니다):

expansion of otsu's method

 

Connected Component Labeling

 

이는 이진화된 영상에서 객체 덩어리(blob)을 구별하는 기법입니다. 경게에 의해 분리되지 않은 픽셀들의 집합을 연결되었다(connected)고 하며, 이 최대 집합을 connected component라고 합니다. connected components operation은 이진 영상을 입력받아 배경(0)을 포함하여 integer label된 labeled image를 생성하는 것을 말합니다:

ex

 

연결성을 정의하기 위해서는 이웃(neighbors) 개념이 필요합니다:

(left) 4-neighbors, (middle) diagonal neighbors, (right) 8-neighbors

 

Connectivity

 

하나의 이미지에서 object의 경계와 components들의 region을 설정하는 것을 말하며, 같은 region의 픽셀들은 같은 intensity를 가지며, 같은 색상을 갖는다고 가정합니다. connectivity에는 3가지 종류가 존재합니다:

 

1. 4-connectivity: 두 픽셀이 서로 N4 관계일 때 연결됨.

2. 8-connectivity: 두 픽셀이 서로 N8 관계일 때 연결됨.

3. m-connectivity: 8-connectivity의 모호함(중복)을 없애기 위한 방식입니다. N4 관계이거나, ND 관계이면서, N4 교집합이 비어있을 때만 연결로 간주합니다.

 

다음은 각 connectivity의 예시입니다:

example 4-connectivity. 해당 방법이 계산 효율적이기 때문에 가장 많이 사용하는 방법입니다.

(left) example 8-connectivity, (right) example m-connectivity. 왼쪽 8-connectivity를 보면 diagonal하고 4가 서로 같은(중복된) pixel값을 connection하고 있습니다. 이런 중복성을 해결하기 위해 m-connectivity를 사용합니다.

 

Labeling algorithm

 

이미지를 좌상단에서 우하단으로 스캔하며 수행합니다:

 

1. 4-connectivity components 알고리즘:

• 현재 픽셀 p가 1일 때, 위쪽(top)과 왼쪽(left)을 봅니다.
  • 둘 다 0이면: 새 레이블 할당.
  • 하나만 레이블이 있으면: 그 레이블 복사.
  • 둘 다 있는데 서로 다른 레이블이면: 둘 중 하나를 할당하고, 두 레이블이 동등(equivalent)하다고 equivalent table에 기록해 둡니다(나중에 합침, 따라서 두 번 전체 이미지를 탐색해야 합니다. 첫 번째는 기본 labeling + equivalent table, 두 번째는 table을 보고 label을 수정).

example 4-connected components

 

2. 8-connectivity components 알고리즘:

• 기본적인 과정은 4-connectivity components 알고리즘과 똑같으며, top과 left만 보는 것이 아니라, top-left, top, top-right, left를 확인해야한다는 점만 다릅니다.

example 8-connected components

 

Multi-color labeling

 

여러 색상으로 thresholding된 이미지가 있을 때, 각 색상 그룹을 독립적으로 정의하여 레이블링하는 개념입니다:

ex