Digital Image Processing - Clustering / Segmentation

---

Clustering

Clustering은 대표적인 unsupervised learning의 예시중 하나이다. Clustering은 비슷한 특성을 가진 데이터를 군집화 하는 것을 말한다. 각 군집 내의 데이터는 최대한 유사하고 다른 군집 간의 데이터는 최대한 차별화되도록 하는 것이 clustering의 목적이다. 아래와 같이 다양한 clustering기법이 존재하고 각각 데이터 구조에 따른 분류 성능이 다르다.

 

Clustering 과정을 아주 간단히 말하면 군집내의 분산을 최소화하는 과정이다. 이는 아래와 같이 식으로도 표현할 수 있다.

각 군집의 데이터와 군집의 중심간의 거리의 합의 평균이 최소가 되도록 하는 것을 볼 수 있다.

---

K-Means Clustering

K-Means Clustering은 군집의 수 K를 미리 지정하고, 초기 군집 중심을 설정한 뒤 데이터 포인트를 가장 가까운 중심에 할당하는 과정을 반복한다. 군집 중심을 데이터의 평균값으로 갱신하면서 수렴할 때까지 반복한다. 군집의 수가 K이고 군집 중신 갱신방법이 데이터의 평균값을 이용하는 것이므로 이름이 K-Means라고 보면 된다.

K=2인 단순한 케이스를 통해 살펴보자.

처음에는 random한 두점을 중심으로 잡는 모습이다.

데이터들을 center가 되는 점들중 가장 가까운 군집으로 분류한다.

각 군집중 평균 지점을 찾아서 다시 군집의 중심으로 잡는다.

군집을 재구성하고 중심을 찾는 과정을 데이터들이 수렴할때까지 반복하여 Clustering을 해낸다.

각 데이터를 가까운 중심점으로 분류시키는 과정은 아래와 같은 식을 이용하고

군집 중심을 업데이트하는 과정은 아래와 같은 식을 이용한다.

K-Means algorithm의 설계 요소는 세 가지 정도가 있다.

 

초기화

초기 클러스터 중심을 무작위로 K개의 지점을 선택하는 방식을 선택할 수 있다. 또는 잔차(residual)를 최소화하기 위해 K개의 지점을 탐욕적으로 선택하는 방식이 존재하다.

거리 측정 방법

전통적으로 유클리드 거리를 사용하지만, 다른 거리 측정 방법도 활용이 가능하다.

최적화

알고리즘이 지역 최소값(local minimum)에 수렴할 가능성이 있다. 여러 번의 재시작을 통해 최적의 결과를 얻는 것이 바람직하다.

 

장단점은 아래와 같다.

장점

조건부 분산을 최소화하여 데이터의 좋은 표현을 제공하는 군집 중심을 찾는다. 알고리즘이 비교적 단순하여 구현하는 방법이 간단하고 실행 속도가 빠릅니다.

단점

적절한 군집 수(K)를 선택해야 하는데, 이는 정확한 결과를 위해 중요하다. 데이터에 이상치가 있으면 군집화 결과에 부정적인 영향을 줄 수 있다. 알고리즘이 local minimum에 수렴할 가능성이 있다. 모든 군집이 동일한 매개변수를 사용하므로, 거리 측정 방식 등이 adaptive하지 않다. 각 iteration마다 K개의 군집과 N차원 점에 대해 연산하므로 느려질 수 있다.

---

Segmentation

이미지 segmentation은 디지털 이미지 처리 분야에서 중요한 기술로, 이미지 내 각 부분을 의미 있는 영역으로 분리하는 작업을 의미한다. 단순히 이미지를 픽셀 단위로 나누는 것이 아니라, 각 픽셀을 특정 객체나 배경에 할당하여 이미지를 이해하고 분석하는 데 도움을 준다.

고전적인 이미지 segmentation 기법중 edge-based 기법들 부터 살펴보자.

 

Contour

컨투어(Contour) 기법은 이미지에서 동일한 값의 영역을 선으로 연결하여 객체의 윤곽을 감지하는 방법이다.

 

Active contour models(Snakes)

Snakes 기법은 초기 설정된 윤곽선을 에너지 최소화 과정을 통해 원하는 객체의 경계로 점진적으로 수렴시키는 이미지 세그멘테이션 방법이다. 내부 에너지와 외부 에너지를 조절하여 윤곽선을 객체의 형태에 맞게 적응시킨다.

 

Active contour models(Level sets)

Level Sets 기법은 객체의 경계를 추적하기 위해 암시적 표현을 사용하는 이미지 세그멘테이션 방법이다. 이 기법은 복잡한 형상이나 위상 변화를 쉽게 처리하며, 경계의 형태를 반복적으로 진화시켜 정확한 세그멘테이션을 수행한다.

 

Region-based

Region-based Model은 이미지 세그멘테이션에서 각 영역의 통계적 특성이나 픽셀 값의 분포를 활용하여 객체를 분리하는 기법이다. 픽셀의 유사한 속성을 가진 영역을 그룹화하거나 초기 시드 픽셀을 기준으로 주변 영역을 확장하여 원하는 객체의 경계를 찾는다. 대표적인 예로는 Region Growing, Manual Watershed등이 있다. 이 모델은 경계가 분명하지 않은 복잡한 배경의 이미지에서도 비교적 정확한 분할을 수행할 수 있다.

---

Mean Shift Algorithm

Mean Shift 알고리즘에 대해서는 좀더 자세히 살펴보자. Mean Shift 알고리즘은 데이터 포인트를 밀도 기반 클러스터로 그룹화하는 non-parametric 군집화 기법이다. 이는 기존 통계학에서도 쓰이던 기법인데 이미지 세그멘테이션에서도 쓰기에 적합한 기법이어서 쓰이게 되었다. 밀도 함수에 대한 사전 가정 없이 데이터를 분석하는 이 알고리즘은 이미지 세그멘테이션, 이상 탐지 등에 유용하게 활용된다.

먼저, 데이터의 밀도를 추정하기 위해 고정된 크기의 Kernel을 설정한다.

붉은 수직선부분이 가장 밀도가 높은 부분으로 추정된다.

밀도가 높은 곳으로 군집의 중심이 이동한다.

계속 이동하다가 수렴하게 되면 중지한다.

 

각 데이터 포인트의 값을 가우시안 분포에 따른 가중치로 합산하여 새로운 평균을 계산한다. 이는 아래와 같은 식을 이용하여 계산한다.

계산한 새로운 평균 지점으로 커널 윈도우를 이동한다. Mean Shift 벡터는 다음과 같이 계산된다. M = x_new ​- x

이는 기존 지점과 새로운 평균 지점 간의 벡터로, 밀집된 영역으로 윈도우를 이동시키는 역할을 한다. 평균을 계산하고 이동하는 과정을 반복하여 밀도가 높은 영역을 중심으로 클러스터링을 진행하게 된다.

하나의 중심으로 진행하면 local minimum으로 빠지는 위험이 존재하여 아래와 같이 많은 start 지점을 지정하여 안전성을 높인다.

 

 

Attraction Basin은 최적화 및 군집화 알고리즘에서 사용되는 개념으로, 특정한 최소값이나 최적화된 상태에 수렴하게 되는 영역을 뜻한다. 이는 함수의 특정 극소값 또는 로컬 최소값으로 수렴하는 초기 위치들의 집합을 의미한다. 예를 들어, 어떤 함수의 로컬 최소값 주변에는 그 값에 도달하는 영역이 존재하는데, 이 영역에 속하는 임의의 초기 위치에서 시작하면 모두 해당 로컬 최소값에 수렴한다. 이 영역이 Attraction Basin이라고 불린다. 군집화 알고리즘에서 Attraction Basin은 군집의 중심으로 수렴하는 데이터 포인트들의 집합을 나타낸다. 이러한 개념은 Mean Shift나 K-Means 같은 알고리즘에서 중요하며, 각 클러스터의 중심에 끌리는 데이터 포인트들을 정의하는 데 사용된다.

아래는 7개의 modes로 클러스터링된 결과이다.

 

Mean Shift 알고리즘의 장단점은 아래와 같다.

 

장점

다양한 유형의 이미지를 효과적으로 세그멘테이션할 수 있다.

군집 수나 형태를 미리 지정할 필요 없이 유연하게 처리한다.

데이터에 이상치가 있어도 군집화 성능에 크게 영향을 받지 않는다.

다양한 문제에 적용할 수 있는 modes 찾기 알고리즘이다.

 

단점

최적의 커널 크기를 사전에 설정해야 하는 부담이 있다.

고차원 데이터의 경우 계산량이 크게 증가해 적합하지 않을 수 있다.

 

세그멘테이션이 지나치게 세분화되었을 때 유용하고 여러 세그멘테이션을 동시에 처리할 때 효과적이다.

---