비전 5) 영상 분할

버츄얼유튜버

비전 5) 영상 분할

두원공대88학번뚜뚜 2021. 12. 28. 00:17

전통 방법

임계화를 이용한 영역 분할

- 오츄 알고리즘: 어두운 배경에 밝은 물체의 경우, 이진화를 사용해 가능. 그러나 여러 물체가 서로 다른 밝기를 가졌다면 좋지 않다.

임계값을 두 개 사용하여, 화소를 세 그룹으로 나누면(임계값 두 개를 각 영역의 분산의 합을 최대화시키도록 설정), 효과적으로 명암 단계가 세 개일 때의 분할이 가능하다.

세 영역이 다를 수록 더 좋은 분할이므로, v_between은 클수록 좋다. 즉, w0과 w1, w2 세 부분이 많이 달라야 하므로, 분산의 최대치를 구해야 하며, 이를 위해 (t1, t2)의 쌍을 조사해야 한다.

먼저 t1 = 1로 설정하고 t2 = 2, 3, ... L-2에 대해 검사한다.

그런다음 t1 = 2로 설정하고 t2 = 3, 4, ... , L-2에 대해 검사한다.

이 과정을 t1 = L-3 까지 반복하고 가장 큰 값을 생성한 쌍을 답으로 취한다.

히스토그램에 따라 단계를 더 올려야 할 경우, 복잡도 제곱이 1씩 증가할 수는 있겠으나 어쨌든 확실한 방법이다.

그러나, 한 객체 내에 여러 밝기가 존재한다면, 이는 효과적이지 않다. 동일한 임계값을 전체 영상에 적용하면, 하나의 객체의 밝은 부분과 어두운 부분의 차이가 커져 알아보기 어려울 것이다. 이 떄 활용하는 것이 적응적 임계화다.

군집화를 이용하면, 3차원 컬러 영상에서 색이 비슷할 수록 가까이 두는 방식의 활용이 가능하다.

k-means 군집화 알고리즘을 사용하자.

화소를 x=(RGB)로 변환하여 샘플집합 X = {x1,....xn}을 구성.

k개의 군집 중심 Z={z1,....,zn}을 초기화. 이 떄, k는 임의로 X에서 k개를 뽑아 사용.
각 군집의 중심 중 가장 가까운 것을 z에 배정

while(TRUE) {
	for(i=1 to n) xi를 가장 가까운 군집 중심에 배정
    if 이 배정이 첫 배정이 아니고, 이전 루프의 배정과 같다면 break
    for(j=1 to k) zj에 배정된 샘플의 평군으로 zj를 대치
}

//분할
for(i=1 to k) zj에 배정된 샘플(화소)을 j로 번호를 매긴다.

그러나 이 알고리즘은, 화소 컬러값의 유사성만 고려하고 거리는 거려하지 않다. 이는 그래프방법, 민시프트를 통해 개선 가능하다.

분할합병은 영역의 균일성을 측정하는 Q(ri)를 이용해 분할과 합병을 반복한다.

Q(ri)이 거짓이면 ri를 네 개 영역으로 등분하고 재귀 반복하고,

Q(ri∪rj)가 참이면 ri와 rj를 합병하는데, 이 분할결과는 4진트리로 표현된다.

가령 1, 2번 블록은 동일한 색이므로 분할하지 않는다.

3의 경우, 다르기에 다시 분할을 진행, 그 다음 사이즈는 전부 같기에 분할을 추가로 진행하지 않는다.

그래프 방법

픽셀 하나하나가 노드라 보자. 서로 다른 두 노드 v_p와 v_q를 연결하는 에지는, 가중치 w_pq(= w_qp)를 갖는다.

이 에지는, v_p와 v_q가 얼마나 비슷한지 나타내는 유사도를 나타내는 것이다.

유사도가 높다면 같은 영역에 속하는 것으로 보면 된다. 가령 w67은 3, w78은 1이므로, 에지 v6,v7이 에지 v7,v8보다 분할선이 될 가능성이 더 높다.

하나의 영역을 만든 다음, 이 연결요소 C의 최소신장트리를 구한다.

다음으로, C가 얼마나 균일한지는 해당 C 내부의 w중 가장 큰 값으로 정한다.

가령 (0,1)과 그 밑의 (1,1)~(2,2)의 5개 영역의 경우(7,6,9,8,7)로 구성되어 있으며, 균일도는 2이다.

명암이 6인 v6과 v7의 9는 명암값의 차이가 3이기에 같은 영역에 속하기 어려워보이지만, 최소신장트리에 의하면 3보다 작은 에지로 연결된 경로가 존재한다. 따라서, 같은 영역일 가능성이 둘만 똑 떼놓고 볼때보다 더 높다고 할 수 있다.

이런 식으로, 균일성이 유지되는 상황에서 노드를 확장해갈 수 있다.

연결 요소가 두 개 주어질 때,

multi_intra는 둘 중 하나라도 균일하지 않으면 큰 값을 가짐으로써 균일하지 않음을 보여주고

diff는 두 연결요소가 얼마나 다른지 보여준다.

이를 이용해 두 연결요소가 잘 분할되어있는지 D를 통해 판별이 가능하다.

이 때 tau(C)는 연결요소 간의 차이 diff와 균일성 multi_intra 사이 차이를 위한 임계값으로,

|C|가 작을 수록 영역이 작아짐을 의미하며, 이러면 tau는 커지고, 인접영역과의 차이 diff는 더 커져야 한다.

매개변수 k는 분할의 세밀함을 나타내며, 작을수록 세밀하게 영역을 분할하여 더 작은 영역을 생성한다.

이렇게 T가 나온 분할은 적절한 분할일 텐데, 정작 이 분할은 어떻게 찾아내는가?

식1을 이용해, 거리를 가중치로 갖는 그래프 생성

에지를 오름차순 정렬 

초기 분할 수행(한 픽셀이 하나의 연결 요소로 다룸.) S0 = {Ci|Ci={vi}, 1<=i<=n}

 
모든 에지에 대해 반복 {
    i 번째 에지 e = (v_p, v_q)
    S_i-1에서 v_p와 v_q가 속한 연결요소를 C_p, C_q라 정의
    if C_p != C_q이며, diff(C_p, C_q) <= multi_intra(C_p, C_q):
    	C_p와 C_q를 합쳐 하나의 연결 요소 만들어 S_i로 
        ** 두 연결요소간의 거리 <= 두 연결요소 간의 균일성 
        ==>두 연결 요소간의 균일성보다 거리가 가깝다 =>하나의 연결요소로 판단
    
    else: S_i = S_i-1
}

정규화 절단

민시프트

함수를 확률밀도함수라 가정하고, 현재 자신의 주변에서 가장 데이터가 밀집한 방향으로 이동하는 방식으로, 분포 중심을 언젠간 찾아가리라는 방법.

어떤 점 x에 커널 k를 씌우고, 이 커널에 들어오는 샘플의 가중치 합을 계산하여 x에서의 함수값 p(x)를 추정한다.

p(x) = 1/(n*h^d) * sigma(i=1 to n) {k((x-xi)/h) -- 민시프트식1

커널은 평현한 함수 또는 가우시안 함수를 주로 사용하며, 이 함수는 중앙으로부터 거리가 1인 범위까지만 0이 아닌 값을 갖는다.

민시프트식1에서, h는 커널의 폭을 조절하는 매개변수로, 커질수록 창 안에 많은 점이 들어옴. 즉, h가 클수록 추정함수는 매끄러워진다.

이 함수는 보면 알 수 있지만, 차원 d가 커질수록 처리양이 많아진다. 따라서 우회하는 방식을 써야 한다.

초기점 y0에서 y1, y2...로 점차 y의 소속을 반복적으로 찾아가는 방식을 쓰자.

1. 현재 위치에서 반경 r 이내에 들어오는 데이터들을 구한다: (x1,y1), (x2,y2), ..., (xn,yn)
2. 이들의 무게중심의 좌표 (∑xi/n, ∑yi/n)로 현재 위치를 이동시킨다. 즉, y_t+1을 구함.
3. 1~2 과정을 위치변화가 거의 없을 때까지, 즉 수렴할 때까지 반복한다.

이 무게중심은 곧, 샘플에 들어온 점 xi에 가중치 k를 곱하고 전부 더한 다음, 분모항으로 나눠 정규화한 것이다.

가중치 k는 xi로부터 중앙 yt까지 거리에 따라 결정되며, 평평한 커널

k(x) = 1 (||x||<=1)

else 0 이나 가우시안커널

k(x) = e^(-||x||^2) if ||x||<=1

else 0

중 하나를 이용해 계산이 가능하다.

이를 통해, 폭 rㄹㄹ 이용해, 서로간의 거리가 r 이내인 수렴점을 하나의 군집으로 만들면 된다.

이제 이를 분할해보자. 입력영상 f에서 샘플집합 X를 확보한다.

우선, 화소 위치 2차원정보와 RGB 3차원 정보를 결합한 5차원 공간으로 매핑한다. 즉, 두 개의 정보를 합한 5size의 벡터를 만든다. 다음으로, 위치와 RGB의 서로 다른 스케일을 가짐으로 인한 차이를 보정하기 위해, 폭이 다른 두 개의 커널 함수의 곱을 사용한다. 대개 k(x) = k(x^s/h_s) * k(x^r/h_r)을 이용한다.

컬러공간을 RGB에서 Luv로 변환
모든 화소를 5차원 공간 xi=(yi,xi,Li,ui,vi)로 매핑. 이때, i = MN(총 화소 수)

for (i=1 to MN)
	y0=xi #초기점 설정
    t=0
    
    while(True):
    	위의 식을 이용해 y_t+1 계산
        if y_t+1 - y-t가 threshold보다 작으면 break
        t++
    vi = y_t+1 #수렴점 저장
    
    
#군집화 과정
vi, i=1~n에서 h 내 점을 모아 군집화, 그 중심을 zj, j=1~k라 한다
xi, i=1~n이 속한 군집 zc를 찾는다.

#후처리
크기가 min_area보다 작은 연결요소 제거

워터셰드

스네이크 알고리즘

Eimae = 스네이크가 영상의 명암값에 반응하는 에너지 항. 궁극적으로 찾고자 하는 것은 물체의 외곽선이기에, 곡선이 에지 위에 놓일 수록 좋다. 따라서, 곡선이 놓인 곳의 에지 강도 사용

Einternal = 스네이크가 움직이는 도중, 잡음에 의해 큰 에지 강도에 곡선의 일부가 도달하여 고정되는 것을 막기 위해, 곡선의 모양을 조절한다. 대부분의 물체가 갖는 대체적으로 매끄러운 형태를 유지시키도록 하는 항

Econstraint = 외부에서 사용자가 원하는 모양을 지정했을 때, 이를 반영하는 에너지

gs(s)와 gss(s)는, 각각 s라는 위치에서 구간의 거리와 곡률을 측정.

a(s)와 b(s)는, 어느 항에 더 가중치를 둘 지 결정.

del_f(g(s))는, g(s)에서의 에지 강도. 3장 에지검출의 에지연산자를 활용하여 구할 수 있다.

위의 과정을 거쳐, 전체 에너지 식이 완성된다.(5.24)

g(s)의 에너지식을 구했으니, 이제 최소의 에너지곡선을 갖는 식은 argminE*(g(s))를 통해 획득 가능.

이 과정을 통해 세 항이 만들어졌으니, 이제 이 곡선을 최초 곡선 g0(s)에서 점차 g1, g2...로 나아가며, 움직임이 둔해질 때까지 게쏙 움직이게 해야됨.

Econtinuity에서, _d는 n개 구간 거리의 평균. 즉, 현재 구간의 거리가 평균에 가까울수록 Econtinuity는 작아짐.

실제 식에선, m개의 이웃 모두에 대해 _d-||g(s)-g(s-1)||을 구하고, 가장 큰 것으로 나눔으로써 (0,1)사이에서 정규화시킴.

E_image에선, m개 이웃의 에지 강도를 조사해, 최고와 최소를 max, min으로 두고, mag는 현 조사하는 점의 에지 강도로 둔다. 이 때, 에지 강도의 차이가 작은 경우를 보정하기 위해, max-min<5이면 min = max-5로 보정.

8~15행이 gt(s)를 g_t+1(s)로 이동시킴.

9~10행에서 g(s)는 자기 자신과 이웃점 각각에 대해 williams의 개선된 곡선을 계산한다.

11~14행에서, 가장 낮은 에너지를 갖는 점으로 이동.

단, moved라는 "이동량"이 임계값보다 작으면 수렴했다 보고 끝낸다.

19~21행은, s라는 점의 곡률이 좌우 이웃보다 크고, 임계값 T1보다 크고, 에지 강도가 임계값 T2보다 크면 코너라 판단, 그 점의 가중치 b(s)를 0으로 둔다. 이는, 개선된 곡선 계산식이 곡률을 감안하지 않게 되어 그 점은 다음 반복에서 코너에 붙들릴 가능성이 높아짐.

지능가위와 레벨 셋

그래프 절단

Ford62에, 큰 그래프에서 최소 절단을 찾아내는 알고리즘이 이미 개발됨.