[Computer Vision] Segmentation

🧑🏻‍💻용어 정리

Computer vision
Edge
Segmentation
clustering
semantic segmentation
Otsu's Method
average
variance
moving average
threshold
within-class
between-class

 

 

이번에는 Segmentation으로 더 grouping을 통해,

 

clustering을 통해서 데이터를 어떻게 더 의미있게 나눌 수 있을까를 살펴보겠습니다.

 

 

 

Segmentation

 

 

image에 대해서 pixel 들을 뭉치는 것에 대해서 clustering 보다는 Segmentation이라는 단어를 많이 씁니다.

 

두 단어가 비슷하다고 보셔도 됩니다.

 

의미가 맞는 pixel 끼리 같은 group화 하는 것도 보입니다.

 

 

그래서 group은 비슷한 것을 하는 것인데,

 

이 비슷하다는 것은 모호함이 있습니다.

 

그래서 위 왼쪽 아래 사진처럼 pixel 마다 어떤 class인가를 맞추는 것은 더 명확한 segmentation이 되겠습니다.

 

 

이외에도 segmentation에서는 다음과 같은 것들이 있습니다.

 

• Segmentation method (before deep learning)
  • K-meas clustering
  • Mean shift
  • Normalized-cut
  • Graph cut
  • Random-walk
  • Markov ranodm field (MRF) optimization

결국 Deep Learning이 도입되기 전에도 이러한 image segmentation에 대한 연구가 진행이 되었습니다.

 

그리고, 어떻게 비슷한 pixel들끼리 뭉칠까, 비슷한 의미의 pixel들을 어떻게 뭉칠까에 대한 고민이 계속 되었죠.

 

여러 가지 방법이 있었지만,

 

pixel을 하나의 node로 본다면, 8-neighborhoods와 같은 것의 개념에서도 edge로 연결하는 것이 있죠.

 

edge와 node만 있으면, graph를 그릴 수 있습니다.

 

edge를 연결하고 edge weight를 통해 node끼리 가까운지를 살필 수도 있습니다.

 

 

이와 같이 비슷한 것끼리 뭉치는 방법도 존재했습니다.

 

보이시는 것처럼 결과가 그렇게 잘 나오진 않습니다.

 

 

 

요즘은 첫번째 사진과 같이 semantic segmentation을 통해 학습 기반으로 class를 미리 정의해놓고 class에 해당되는 것을 맞추게 하도록 접근합니다.

 

아니면 위와 같이 사물 객체 인식, 아니면 instance에 대해서만 분할 할 수도 있습니다.

 

그런데 우리는 가장 classic한 방법은 image thresholding에 대해 배워볼 것입니다.

 

이제 본론으로 들어가 봅시다.

 

 

Image thresholding

 

이전 시간에 우리는 threshold을 통해 edge이다 아니다를 나누었습니다.

 

이번에는 pixel 값을 보고 판단하는 것입니다.

 

 

배경은 background, 전경은 foreground라고 보면 이 두 가지를 분류하고 싶다고 하면,

 

위 사진과 같이 이진 분류된 결과, 즉 binary segmentation의 결과를 얻을 수 있습니다.

 

 

오늘은 다음과 같이 이진화하기 좋은, 배경 - 전경으로 분류하기 편한 이미지를 다루겠습니다.

 

이 threshold를 통해, threshold 보다 크면 1, threshold 보다 작으면 0으로 봅니다.

 

이러한 single threshold을 통해 아래와 같이 박테리아를 분류할 수 있습니다.

 

 

위와 같이 threshold를 직접 지정해주며 결과가 잘 나오는지를 살펴봐야합니다.

 

그럼 사람이 하나하나 넣어주어야하는 번거로움이 있겠죠.

 

그래서 우리는 이 threshold를 결정하는 방법, 예측하는 방법을 배워보겠습니다.

 

 

 

그리고 아래 예시는 threshold를 통해 이미지 상에서 가려져 있는 것을 볼 수 있다는 것을 보여줍니다.

 

 

 

그리고 다른 threshold 예시로 Double thresholding을 사용할 수도 있습니다.

 

Canny edge에 했던 방법을 사용하여 class를 3개로 만들어, weak edge는 또다른 후처리를 통해 결정하는 그러한 것도 해볼 수가 있습니다.

 

또는 threshold를 두 개 설정하여 그 사이에 있는 값만 뽑아올 수도 있겠죠.

 

그러한 방법이 있는 것을 알아두시면 됩니다.

 

 

 

그리고, threshold를 통해서 noise가 배경에 껴있는 다음과 같은 Image에 대해서 날려버리는 효과를 가져오기도 합니다.

 



 

결국 threshold는 어떤 기준을 세워서 크고 작은 것들을 분류하는 그런 것이다 보니, noise에 대해서 threshold 이상이면 잡음으로 결과에 나타나기도 합니다.

 

threshold를 이미지에 대해 바로 거치면, 이러한 잡음이 그대로 나오게 됩니다.

 

그래서, 이러한 잡음을 없애기 위해 smoothing filter를 거친 후 그것에 threshold를 취하는 것으로 진행하는 것입니다.

 

이 과정에서 전처리로서 average filter나 Gaussian filter가 활용될 수 있습니다.

 

 

그래서 어떻게 threshold를 예측할 수 있을까요?

 

 

그렇다면, 위와 같이 foreground, background를 나누어서 볼 때,

 

threshold를 낮게 잡으면 너무 많이 날라가 버리고, 반대로 threshold를 높게 잡으면 너무 많이 남습니다.

 

여기서 threshold를 결정하는 것을 여러 번 더 해야 좀 더 괜찮은 정보를 얻을 수가 있는데, 이것을 직접하는 것은 번거롭습니다.

 

그래서 이 threshold를 어떻게 자동으로 결정할 수 있을까요?

 

 

아래와 같이 image에 대한 histogram을 봅시다.

 

0 ~ 255의 pixel 값이 image 상에서 몇 번 발생했는지 카운트해서 보여줍니다.

 

y축이 pixel의 개수가 됩니다.

 

그것을 살펴보니, 2개로 분류할 수 있는 image에 대해서는 dominant한 두 분포가 보입니다.

 

그렇다면, 이 사이의 값을 잘 결정하면, 이 두 가지를 잘 결정할 수 있을 것 같아 보입니다.

 

 

 

결국, 이 두 histogram을 잘 분리하는 threshold 값을 찾는 것입니다.

 

뒤 쪽에 있는 것이 어두운 값이니 background에 해당하는 값일 테고, 앞 쪽에 있는 값이 foreground에 해당하는 값이겠죠.

 

그래서 하나의 threshold를 잘 골라서 좋은 Segmentation 결과를 얻을 수 있겠다고 기대할 수 있습니다.

 

 

이 threshold도 하나의 pixel 값이니, 이 값을 이하 k라고 칭하겠습니다.

 

이것은 k : 0 ~ 255의 값을 가지겠습니다.

 

이 k를 0부터 256까지의 값일 때의 연산을 통해 최적의 k의 값을 찾습니다.

 

그것이 자동으로 k를 구하는 방법입니다.

 

 

 

그래서, 이 두 histogram에 대해서 threshold를 계산해주는 algorithm이 필요합니다.

 

Otsu's Method

 

 

 

두 histogrm 분포의 threshold를 자동으로 결정해주는 기법입니다.

 

아래와 같이 group을 2개로 나누겠습니다.

 

이는 k 값에 의해 나누어진 group 두 개입니다.

 

 

 

왼쪽 group1은 k 보다 같이 작은 값들이고 오른쪽 group2는 k 보다 큰 값들입니다.

 

그렇다면 잘 분류했다는 기준은 어떤 게 있을까요?

 

같은 group인 값들끼리 비슷한 pixel 값들을 가져야 우리가 잘 grouping했다고 볼 수 있게됩니다.

 

그것들을 살펴보는 지표에는 분산을 구하는 방법이 있습니다.

 

분산 계산 시 평균 구하고 각 값에 평균을 빼서 제곱하여 구했었죠.

 

 

그렇다면 각 값들이 평균 기준으로 몰려 있을 수록 분산 값이 낮을 것입니다.

 

그 값들 끼리 비슷해야한다는 것을 보려면 분산이 낮아야한다는 뜻입니다.

 

intra-class variance

 

이 group, 즉 class 안에서 이루어지는 분산을 within-class 또는 intra-class variance라고 부릅니다.

 

이것은 weighted sum of variances of the two classes의 방식으로 구합니다.

 

위에서 구한 두 분산의 합이 작아야 우리가 적절한 k 값을 구했다고 볼 수 있습니다.

 

0부터 255까지 k의 값을 계속 바꾸며 group 1, 2가 계속 바뀌고 분산 1, 2도 계속 바뀌며 이 분산의 합이 최솟값을 갖는 k를 선택하겠다는 것입니다.

 

 

위는 class 안에서 본 것입니다.

 

그리고, 위 나눈 group1과 group2가 얼마나 다른지도 봐야합니다.

 

 

inter-class variance

 

이제 내부에서 살피겠습니다.

 

group1과 group2 pixel의 분포가 얼마나 다른가를 살펴보아야합니다.

 

이 서로 다른 class간 비교를 할 때 bwtween-class, 또는 inter-class variance를 구합니다.

 

이 분산은 커야합니다.

 

분포가 다른지를 보는 것이기 때문입니다.

 

이것은 maximize해야하는 것이죠.

 

 

 

두 개를 같이 조합하여 사용하기도 하고, 둘 중 하나만 사용하기도 합니다.

 

 

 

자, 그렇다면 우리에게 image 하나가 주어진다고 하겠습니다.

 

이 image는 크기가 M x N입니다. pixel의 개수가 M x N개 있는 것이죠

 

그리고, pixel 값이 L개의 intensity가 있습니다.

 

그런데 우리가 다루는 image는 0 ~ 255의 pixel 값을 가지므로 L은 256입니다.

 

 

그러나 어디에서나 image가 8비트인 것은 아닙니다. 10비트 12비트 짜리가 있기도 합니다.

 

다른 데서도 이  Otsu's 방법이 사용 가능합니다.

 

그리고 n i는 pixel 값 i의 histogram 값이 됩니다.

 



 

그런데, 이 값을 전체 pixel 개수로 나눠주어 확률값처럼 보이게 합니다.

 

이 p i는 개수 자체의 값은 아니지만 n i에 비례합니다.

 

정확히 개수는 아니지만 개수로 받아들이고 넘어갑시다.

 

 

이 식에 의해 위 총 합은 1이 됩니다.

 

 

 

다시 돌아오면,

 

이 threshold k에 의해 class가 두 개로 나뉩니다.

 

여기서 하나의 약속이 필요합니다.

 

k가 class 1 or class 2에 속할지입니다.

 

여기선 class 1에 넣겠습니다.

 



어디에 넣든 상관은 없습니다.

 

0 ~ k의 값은 class 1, k+1 ~ L-1 은 class 2가 됩니다.

 

 

 

우선, class 1에서의 평균과 분산을 구하는 과정을 살펴봅시다.

 

 

class 1에 속하는 histogram 값들의 합에 M x N을 나눠준 것이 q 1(k)입니다.

 

 

여기서 평균을 계산해줄 것입니다.

 

i 자체가 pixel 값입니다.

 

그리고 p(i)는 i에 대한 pixel 의 개수로 보면 되죠.

 

그것에 대해서 각 개수에 각 원소의 곱을 하여 다 더해줍니다.

 

그리고, 여기서 개수로 나눠줍니다.

 

 

 

이렇게 평균을 구할 수 있습니다.

 

그리고 분산도 구하면 됩니다.

 

각각을 평균에서 빼서 제곱한 것에 개수를 곱하는 것입니다.

 

또는 각 원소의 제곱에 개수를 곱하고 평균의 제곱을 빼주는 식도 있습니다.

 

그리고 전체 개수로 나눠줍니다.



그래서 class 2에 대해서 다음과 같이 구할 수 있겠습니다.

 

단지 sigma의 범위만 달라집니다.

 



그리고 전체 class도 바로 연산 가능합니다.

 

 

m G는 이미지 전체의 평균값입니다.

 

sigma G도 전체에 대한 분산값입니다.

 

 

그리고 아래 식을 봅시다.

위 식은 p(i)를 결국 다 더하는 것이니 1이 되겠죠.

 

각각 class 1, 2의 평균을 구했을 때 전체 평균을 구하고 싶을 때 사용하는 식입니다.

 

여기서 q1(x) + q2(x) = 1 이므로 생략 되었습니다.

 

 

그래서 이제 이것들을 가지고 inter-class, intra-class를 구하는 방법에 대해 다루겠습니다.

 

Optimum Global Thresholding

 

 

 

intra-class를 구하는 방법에 대해서 살펴보겠습니다.

 

위 수식은 within-class variance를 구하는 수식입니다.

 

k라는 상황에서 k를 변수로서 계속 씁니다.

 

위 식에서 class 1과 class2의 총 개수를 q1(k), q2(k)로 보면 됩니다.

 

pixel의 개수가 많아지면 같이 비례해서 올라가는 것이죠.

 

 

이것을 왜 곱할까요?

 

 

이 두개를 단순히 더하기에는 두 개의 중요도가 다를 수 있습니다.

 

여기서 기준을 1로 놓고 보면, 적은 개수로 계산한 분산이 많은 것으로 계산한 분산보다 신뢰도가 더 높다고 보기 어렵습니다.

 

값이 적다보니 만일 5개의 값이 모두 같다면 분산이 0이 나오게 됩니다.

 

이 경우 전체 합이 낮아져서 이 때 k가 선택될 수도 있습니다.

 

이 적은 값 가지고 구한 분산은 약간 noise한 데이터일 수 있는 것입니다.

 

개수가 많은 만큼 더 중요도를 두겠다는 것입니다.

 

이것이 weighted sum입니다.

 

이 weight는 각 class에 속하는 pixel들의 개수라고 보시면 됩니다.

 

그리고 가중치의 합이 1이 되어 더 이상적인 모양새를 이룹니다.

 

 

 

그래서 이 within-class variance가 최소가 되는 k를 고르는 것입니다.

이 optimal threshold k를 구하는 것입니다.

 

이 k를 0부터 255까지 다 구해서 최소가 되는 k를 구하는 것입니다.

 

이것이 within-class 방식을 이용해서 k를 구하는 방법입니다.

 

 

 

그리고 서로 다른 class 간 얼마나 다른지를 분석하는 것이 between-class variance입니다.

 

다를 수록 variance가 큽니다.

 

 

이것은 위와 다르게 최대화를 시켜야합니다.

 



이 또한 마찬가지로 k가 0일 때부터 255일 때까지 차근차근 하나씩 다 구하면 됩니다.

 

 

이제 그 이야기를 해봅시다.

 

group 1과 group 2 사이의 차이를 다 구해서 평균을 구할 수도 있겠죠?

 

그러나 이것은 많은 시간과 비용이 듭니다.

 

가능은 한 방법이겠죠.

 

 

아니면 평균 하나와 다른 group과의 원소 간의 차이가 커야한다로 볼 수도 있습니다.

 

그리고, 전체 평균과 위 m1, m2 와의 차이가 커도 되겠습니다.

 

이 마지막 방법이 계산이 가장 적겠죠?

 

그래서 위와 같이 Between-class variance를 구하게 됩니다.

 

그래서 위와 같이 차이를 구하고 제곱을 통해 양수로 바꿔줍니다.

 

여기도 마찬가지로 개수로 weight를 주게 됩니다.

 

 

 

위 식을 아래와 같이 전개하여 정리할 수가 있습니다.

그리고 증명 식은 위와 같이 식을 전개합니다. (k는 계산의 편의를 위해 생략했습니다.)

 

주의 깊게 볼 부분은 위와 같습니다.

 

m G 대신에 q1m1 + q2m2를 대입했습니다.

 

그리고 아래와 같이 연산 과정을 거칩니다.

 

그리고, q1 + q2가 1인 것도 우리가 알고 있습니다.

 

그래서 결과적으로 위와 같은 결과가 나옵니다.

 

 

결국, group 1과 group 2의 평균 사이의 차이를 계산하게 됩니다.

 

두 개가 얼마나 다른지를 계산하는 편한 방법입니다.

 

게다가 연산량도 줄어듭니다.

 

그리고 평균만 보는 것이 아닌, q1 x q2도 같이 보는 것입니다.

 

두 q1 + q2 = 1인 것을 알고 있습니다.

 

그렇다면 이 max(q1 x q2)가 되려면 언제일까요?

 

when q1 = 0.5, q2 = 0.5입니다.

 

그래서, 결국 m1과 m2의 차이가 커져야 하지만, q1과 q2가 비슷해야한다는 것입니다.

 

이 두 값이 비슷해야 더 큰 값을 가지게 되는 것입니다.

 

이것도 결국 차이가 줄어들어야합니다.

 

아까 본 것처럼 개수가 어느정도 비슷해야 신뢰도가 올라간다는 것이 이러한 의미입니다.

 

그래서 두 가지 의미가 있습니다.

 

1. 두 group 간 평균의 차이가 달라야합니다.

 

2. 두 group의 개수가 비슷해야합니다.

 

 

평균 차이가 크지 않으면, 개수가 비슷한 상황에서 끝날 것입니다.

 

혹은 평균 차이가 크다고 하면 개수가 달라도 선택이 될 수가 있을 것입니다.

 

개수가 비슷하면서 평균 차이가 적절히 나는 구간이 선택될 수도 있습니다.

 

within-class와 비교했을 때,

 

이 between-class는 분산을 구할 필요가 없습니다.

 

분산은 평균을 구하고 분산을 구합니다.

 

그래서 더 연산량에서 앞서는 모습을 보입니다.

 

 

그리고 이 평균은 더 효과적으로 구할 수 있습니다.



 

우선 k 가 0일 때 initial 값을 구합니다.

 

0에 어떤 개수를 곱해도 0이므로 평균은 0입니다.

 



여기서, 우리가 k까지 구했다고 했을 때, k+1인 경우를 어떻게 계산할지 보겠습니다.

 

우선 q의 값은 위와 같이 쉽게 구할 수 있습니다.

 

 

이미 구해놓은 것에 더합니다.

 

그리고 m1(k)를 구해놓은 것에 새로 추가되는 것만 더해주고 총 개수로 나누어줍니다.

 

총 개수도 달라지니 그 q1(k+1)도 미리 구해놓은 것이죠.

 

 

 

이동하면서 평균을 일일이 다 구해주는 것이 아니라 이전 단계에서 구현해놓은 것을 그대로 사용하면서 새로 추가되는 것만 쓰겠다는 거죠.

 

이러한 것이 moving average입니다.

 

 

지금 k까지는 다 구해져 있다는 가정입니다.

 

그렇게 q1(k+1)와 m1(k+1)를 구해줍니다.

 

그리고, 이것은 원래 처음부터 다 더하는 것보다 원래 구해놓은 것에 하나만 더하는 것이 훨씬 빠른 것이 됩니다.

 

 

그리고 m2(k+1)은 class 2에 해당하는 것입니다.

 

q2도 1 - q1으로 치환하여 바로 구할 수 있습니다.

 

k+1 에서는 덩어리는 그대로 유지되는데, class 1에서는 하나 추가되는 것이고 class 2에서는 빼줘야합니다.

 

이 k+1번재 애들을 class 2에서는 빼줘야하는 것이죠. 총 개수도 1 - q1(k+1)이 됩니다.

 

이런식으로 moving average 방식으로 구할 수 있고,

 

이것은 분산을 구할 필요가 없기 때문에 within-class 방식보다 속도가 더 빠릅니다.

 

그리고 between-class 방식에서도 이렇게 바뀌는 애들만 더해주고 빼주는 것이 더 빠를 것입니다.

 

 

 

 

이 otsu 방식으로 image마다 서로 다른 threshold를 뽑아줄 수 있다는 것입니다.

 

그러나, 두 개로 나누기 쉬운 것,

 

두 개의 확실한 dominant한 distribution이 있는 상황에서는 잘 되지만,

 

지금 예제처럼 그렇지 않은 경우에는,

 

pixel 값 기준으로 확실히 나눠져 있지 않은 경우에는,

 

Otsu 써도 오른쪽 이상은 다 하얀색이 나와버립니다.

 

배경 부분이 충분히 밝기 때문입니다.

 

 

 

pixel 값을 3D로 보여준다면,

 

오른쪽과 같이 위 배경도 같이 올라가게 된다는 것입니다.

 

그래서 이렇게 경사를 가지게 보이게 됩니다.

 

이렇게 하나의 pixel 값만 가지고는, 하나의 threshold 값 가지고는 배경이 포함될 수밖에 없습니다.

 

즉, 이러한 배경을 분리해낼 수 없습니다.

 

 

그래서 경우에 따라 사람이 직접 관여하여 image를 4등분하여 등분마다 Otsu를 사용하여, 각각의 구간에 대해 threshold를 구하는 것입니다.

 

그래서 사람이 관여하여 조금 더 좋게 image를 뽑아낼 수 있습니다.

 



2개 밖에 나누지 못하니 활용도 면에서 좀 떨어집니다.

 

요새 color image에서 특히 쉽지 않습니다.

 

흑백 image에서도 제한이 있습니다.