최소신장트리

최소신장트리

원리

• 에지 가중치가 거리인 그래프로 표현
• 신장트리를 이용한 최적 분할 찾아냄 [Felzenszwalb 2004]
  • 그림에서 회색 표시된 부분 그래프의 최소 신장트리는 빨간 에지
  • 새로운 노드를 추가한다면 어떤 노드(화소)를 고르는것이 가장 유리할까

연결요소 C의 균일성 측정

• [그림 5-9]의 연결요소(신장트리)의 INTRA는 2
• 새로운 노드를 추가한다면 어떤 노드(화소) 고르는 것이 가장 유리할까
  • \(\textcolor{Black}{v_{13}}\) 추가하면 intra는 3이 됨. \(\textcolor{Black}{v_{8}}\)추가하면 2가 됨 -> \(\textcolor{Black}{v_{8}}\)을 선호.

    두 연결 요소의 균일성 측정

• 둘 중 하나라도 균일하지 않으면 큰 값(균일하지 않음)
• k는 분할의 세밀함 조절하는 매개변수(작을수록 세밀하게 분할)

두 연결요소가 적절히 분할 되어 있는지 판정

• \(\textcolor{Black}{D(C_i, C_j)}\)가 참이면 두 연결요소는 거칠지도 세밀하지도 않은 적당한 상태

영상 f의 분할

• 컬러 영상에서는 식 (5.10)의 거리 척도 사용
• f를 r개의 영역 \(\textcolor{Black}{S={C_1,C_2,...,C_r}}\)로 분할했을 때, 모든 쌍의 \(\textcolor{Black}{D(C_i,C_j)}\)가 참이면 분할 S는 거칠지도(저분할) 세밀하지도(과분할)않은 적절한 상태
• 이런 분할을 어떻게 찾을 것인가? -> 탐욕 알고리즘으로 해결

알고리즘

결과

출처 - Computer Vision