[패턴인식] 영상분할(2): 민시프트, 대화식 물체 분할

Image Segmentation

목차

0. PREVIEW

1. 영상 분할의 원리

2. 전통적 방법

3. 민시프트

4. 대화식 물체 분할

5. 알고리즘 선택

 

<0~2. 전통적 방법>은 이전 게시글을 참고해주세요

https://codingsmu.tistory.com/117

[패턴인식] 영상분할(1): 영상 분할의 원리, 전통적 방

 

 

3. 민시프트

---

모드 탐색

• 샘플이 주어진 경우, 어떤 점이 속한 모드(봉우리를 찾는 문제)
• y의 모드는?

  • 

    모드 탐색

3.1 군집화

파젠 창(Parzen Window)을 이용한 확률분포 추정

• h는 커널의 폭(클수록 많은 샘플이 창 안으로 들어와 매끄러운 함수가 생성됨)

  • 

    해당 확률분포(합 = 1)에 포함되는 경우 1, 포함되지 않은 경우(합 &amp;amp;gt; 1) 0

• 차원의 저주 발생
  • 차원이 커질수록 기하급수적으로 메모리와 계산 시간 증가
  • 명시적으로 확률분포를 추정하려는 시도는 수학적으로 그럴싸하지만 비현실적임
  • 따라서, 파젠 창은 계산, 시간복잡도가 커 현재에는 거의 사용하지 않는 방법임

 

민시프트(Mean Shift)

• 우회적으로 소속(모드)을 결정하는 기법
• $y$를 $y_0$로 놓고 시작하여, 수렴할 때까지 $y_0 -> y_1 -> y_2 -> \cdots $ 반복

  • 

  • 

  • 현재 점 $y_t$를 민시프트 $m(y_t)$가 $y_{t+1}$로 이동시킴
• (5.18)식을 다음과 같이 바꿔쓰기도 가능

  • 

 

 

 

 

민시프트 알고리즘의 특징

• K-means나 Gaussian mixture 군집화 알고리즘과 달리 군집의 개수를 사전에 알려줄 필요가 없음
• K-means나 Gaussian mixture는 일정한 모양의 분포를 가정하고 매개변수를 추정하는 모수적(Parametric) 방법이지만, 민시프트는 비모수적(non-parametric) 방법임
• 설정해야 할 파라미터가 적음
• 단, 샘플 데이터 개수가 커질수록 속도가 느려짐
  • 샘플 데이터 수가 적고 군집의 개수를 사전에 알 수 없는 경우에 적합

 

민시프트를 이용한 군집화 알고리즘

• 모든 점에 대해 식 (5.19)로 수렴점을 찾은 후 군집을 배정
• 뛰어난 군집화 알고리즘: 군집화 개수 자동 결정, 임의 모양 군집, 설정할 매개변수 적음
• 코드

  • #input = sample's set X={x_i|i=1,2,...,n}, epsilon(convergence threshold)
    #output = k modes z_i, 1<=i<=k, a(x_i)is represent x_i's group, 1<=i<=n
    
    for j in range(1, n+1):
    	y_0 = x_i // set the initial point
        t = 0
        while True:
        	# calculate y_t+1 using (5.19)
            ...
            if abs(y_t+1 - y_t) <= epsil): #convergence
            	break
            t += 1
        v_i = y_t+1 # save convergence point 
        
        
    # clustering step
    # 1) v_i, i=1,2,...,n에서 h이내에 있는 점들을 모아 군집화하고, 
    #    군집 중심을 z_j, j=1,2,...,k라 한다
    # 2) x_i, i=1,2,...,n이 속한 군집 z_c를 찾아 a(x_i)=c라 한다

• Mean-shift Clusteting 추가 설명은 나의 큰 O는 log x야 님의 블로그를 참고하시면 좋습니다
  • https://bab2min.tistory.com/637

[기계 학습] Mean Shift 클러스터링

 

 

3.2 영상분할과 스무딩

민시프트를 영상 분할에 어떻게 적용할까?

• [Comaniciu2002] 영상 f를 샘플 집합 X로 변형
  • 화소가 샘플이 됨

몇 차원으로 표현할 것인가?

• 컬러만 표현하면 2.2절의 k-means와 비슷한 결과
• 컬러 $x^r=(r,g,b)$와 화소의 위치 $x^s=(y,x)$를 같이 표현 -> 5차원 벡터 x=(r,g,b,y,x)
  • 영상 분할 시 색깔(color)과 위치 정보(Spatial locality)를 둘 다 고려해야 함
•  $x^r, x^s$의 스케일 차이를 고려하여 커널을 별도로 표현
  

  • 

• 민시프트(EDISON)로 분할한 영상

  • 

 

민시프트의 활용

• 데이터 군집화(Clustering)
• 영상 분할(Segmentation) , 스무딩(Smoothing)
  • 입력 데이터 형태를 좌표 뿐만 아니라 컬러를 포함하여 사용
    • $(x,y) \to (x,y,r,g,b) or (x,y,L,u,v)$ 
  • 에지 보존 스무딩(Edge preserving Smoothing)

    • # input: color image f_r(j,i),f_g(j,i),f_b(j,i), 0<=j<=M-1, 0<=i<=N-1
      # output: smoothing color image
      
      for i in range(1, M*N+1):
      	# replace X_i's pixel value with V_i^r

    • 왜 에지 보존 특성을 갖나?
• 객체 추적(object tracking)
  • 빠르게 하기 위해 히스토그램 역투영(histogram backprojection) 알고리즘 활용하기도 함

  • 

    히스토그램 역투영을 이용한 객체 추적

 

4. 대화식 물체 분할

---

물체/배경 분할

물체/배경 분할의 응용

• 사용자가 초기 곡선 지정->대화식 시스템
• 컴퓨터 비전과 컴퓨터 그래픽스의 협동

 

4.1 능동 외곽선 

스네이크보다 진보한 현대적인 기법 등장

• 지능가위: 편리한 사용자 인터페이스 제공[Mortenson98]
  •  

    

    지능 가위의 동작

• 레벨 셋
• GrabCut

4.2 그래프 절단(Pass)

 

 

5. 알고리즘 선택

---

어떤 알고리즘을 선택해야 하나?

• 뚜렷한 가이드라인이 없음
• 자신의 응용환경에서 성능 실험하여 알아냄

선택을 도우려는 노력: 데이터베이스

• UC 버클리, 바이츠만 연구소

• 

  영상 분할용 표준 데이터베이스

선택을 도우려는 노력: 성능 분석

• 성능 측정 방법[Unnikrishnan]
• 성능 벤치마킹[Estrada2005, Arbelaez2011]

표준 데이터베이스가 있어 좋지만, 주의할 점도 있다!

• 데이터베이스에 집착하여 과적합(overfitting) 문제를 야기할 수 있음
• 즉, 일반화 능력이 낮은 알고리즘을 낳을 수 있기 때문에 주의
• 이러한 문제를 해결하는 한 방법으로 데이터베이스의 크기를 꾸준히 키워나가는 중