Image Segmentation 기법 중에서 Spectral Clustering 이라는 알고리즘이 있다.
Spectral Clustering은 기본적으로 그래프 이론을 바탕으로 Graph Partitioning Algorithm의 일종으로 사용될 수 있다. 이름을 보고 직관적으로 이해해보면, 이 알고리즘은 공간적으로 무언가를 클러스터링하겠다는 것으로 이해할 수 있다. 아래에서 더 자세히 어떤 과정으로 클러스터링을 할 수 있는것인지 간단하게 정리해보았다.
우선, 이 알고리즘은 크게 두가지 행렬을 통해 산출될 수 있다.
1. Similarity matrix(Affinity matrix)
2. Laplacian matrix
기본적으로 해당 행렬은 자료가 graph 형태로 node과 edge 정보들을 담고있다.
먼저 1, 2번 행렬을 살펴보기 전에 그래프를 표현하는 가장 기초적인 행렬인 adjacent matrix를 알아보자.
인접행렬이라고 부를 수 있고, 해당 행렬은 간단하게 연결된 node면 1, 연결되지 않았다면 0으로 연결상태를 표현한 행렬이다.
위처럼 단순히 연결상태에 따라서 adjacent matrix (A)를 구할 수 있다.
인접행렬(Adjacent matrix)처럼 Similarity matrix (=Affinity matrix; A행렬)도 node와 edge에 대한 연결상태를 표현한 행렬이다. 해당 글에서는 이미지 데이터에 대한 similarity matrix를 구하는 예시로 설명해보겠다.
우선 이미지 데이터를 graph 자료로 생각해보면 각 pixel은 node이고, edge의 가중치는 pixel의 값(intensity)을 통해 산출해 줄 수 있다. node의 값(=intensity)을 x라고 생각하면, 아래의 식처럼 Gaussian kernel을 통해 Affinity matrix의 원소로 들어갈 가중치값들을 구해줄 수 있다.
또는, neighbot graph나 k-Nearest Neighbor graph matrix로 affinity matrix를 구할 수도 있다. (이 행렬을 사용하는 경우가 정확도가 더 높아질 수 있다.)
여기에서 만들어진 행렬 A를 활용해서 Laplacian matrix를 구해줄 수 있다.
먼저, Laplacian matrix에 대해서 알아보자.
라플라시안 행렬을 구하는 방법은 아래의 4가지처럼 다양하다. 상황에 맞는 연산을 선택하여 라플라시안 행렬을 구해주면 된다.
1. Simple Laplacian
2. Normalized Laplacian
3. Generalized Laplacian
4. Ng, Jordan, and Weiss Laplacian
Laplacian matrix 식에 들어가는 A는 Adjacent matrix일 수도 있고, Affinity matrix를 대입하여 구할 수도 있다.
D는 Degree matrix(차수행렬)의 수식표현으로 A행렬의 i번째 row의 모든 원소의 합을 주대각선 원소로 갖는 대각행렬이다.
구체적인 라플라시안 행렬 계산에 대해서는 양시건님의 블로그에 잘 설명이 되어있으니, 같이 계산을 따라가보면서 이해해보면 좋을 것 같다.
Spectral Clustering - Process
1) 위에 설명된 라플라시안 행렬들 중에서 하나를 선택하고,
2) 고윳값 분해(eigenvalue decomposition)하여 고윳값과 고유벡터를 얻는다.
3) 그래프 구조 정보를 추출 후에 고유값 중에서 k개의 clustering을 할것이라는 의미로 k개의 상위 고윳값을 선택한다.
4) 고윳값에 대응되는 고유벡터들을 열벡터로 가지는 행렬 X를 구한다.
5) 행렬 X를 아래의 식으로 정규화시켜준다. (numpy.linalg.norm)
6) Y의 각 행을 개별 데이터로 취급하여, k-means 클러스터링을 수행한다.
결과로 아래의 예시처럼 Spectral Clustering을 사용하여 클러스터(커뮤니티)를 찾을 수 있다.
ref1. https://scikit-learn.org/stable/auto_examples/cluster/plot_segmentation_toy.html
Spectral clustering for image segmentation
In this example, an image with connected circles is generated and spectral clustering is used to separate the circles. In these settings, the Spectral clustering approach solves the problem know as...
scikit-learn.org
ref2. https://beginningwithml.wordpress.com/2019/04/20/11-5-spectral-clustering/
12.5 – Spectral Clustering
Spectral clustering will be the last clustering technique that we will discuss. Hopefully, all the five (including this one) algorithms that we discussed were different enough to give you an idea o…
beginningwithml.wordpress.com
'AI > Computer Vision' 카테고리의 다른 글
| Object Detection Evaluation - IoU란? (1) | 2023.12.08 |
|---|---|
| 이미지 영상의 어파인 변환 (Affine Transformation)이란 무엇인가? (0) | 2023.11.17 |
| Digital Image Processing 이란 무엇일까? (디지털 이미지 처리) (0) | 2023.04.15 |
| [트렌드] Computer Vision에서의 생성형 AI. Generative model에 대해서 알아보자. (0) | 2023.04.14 |
| DRI (Detection, Recognition, Identification의 차이) (0) | 2022.11.12 |