정규화 절단

유사도 그래프와 Wu의 분할 품질 척도

• 예) 거리가 d일때 9-d로 유사도 계산

• Wu의 척도 cut[Wu93]

Shi의 정규화 절단 [Shi2000]

• cut의 문제점
  • 원래 연결요소를 작은 것과 큰 것으로 분할하는 경향
  • 두 연결요소 간의 에지 개수가 적으므로 cut이 작아짐
  • 예) 분할 1의 cut은 12, 분할 2는 7->하지만 직관적으로 분할 1이 우수
• Shi는 정규화 절단 ncut으로 확장하여 문제 해결
• ncut이 최소가 되는 분할을 찾는 문제는 NP-complete -> 스펙트럴 군집화를 이용하여 근사해 구함

근사해 탐색 알고리즘

• W는 그림 5-11의 인접 행렬이고, D는 \(\textcolor{Black}{d_{ii}=\sum{_j w_{ij}}}\) dii=sigmajwij인 대각선 행렬

영상 분할

• 식 (5.14)의 고유값과 고유 벡터를 이용하여 영상 분할
• 실제로 쓰이는 유사도
  • 화소의 특징값(명암 또는 컬러)뿐 아니라 화소 사이의 거리도 같이 사용
  • 특징값이 비슷할수록 거리가 짧을수록 큼
  • 특징값이 크게 다르더라도 이웃이면 같은 영역이 된다거나 특징값이 비슷하더라도 멀면 다른 영역에 배정할 가능성 확보 <- 전역 최적화

출처 - Computer Vision