컴퓨터 비전 스터디 2주차 : 21.03.28

3. 이진 영상

때로는 영상을 백(전경)과 흑(배경)의 두 가지 값만 가진 이진 영상으로 바꿀 필요가 있다.

이진 영상의 의미는 백 1, 흑 0의 값을 갖는 영상이라는 뜻이다.

1. 이진화와 오츄 알고리즘

화소의 명암값을 흑과 백 중 하나로 결정하려면,

일정한 임계값threshold T를 정하여 해당 값보다 크다면 백, 작다면 흑으로 바꾸는 방법이 있다.

이때, 임계값을 어떻게 정하느냐의 문제에서, 가장 간단한 방법은 히스토그램을 분석하여 두 봉우리 사이의 계곡 지점을 T로 취하고, 그것보다 큰 화소는 백(1 or L - 1) 그렇지 않은 화소는 흑(0)으로 바꾸는 것이다.

 

 

해당 방법은 전역 고정 이진화Global fixed thresholding이라고 한다.

(a)의 영상을 (c)처럼 이진화할 때 사용하는 방법이다.

(b)와 같은 히스토그램에서 두 봉우리(100 ~ 150) 사이의 125를 T로 취하여 (c)의 영상을 도출하는 것이다.

 

 

위와 같은 수식으로 표현 가능하다.

 

출처 : https://scikit-image.org/docs/0.14.x/auto_examples/xx_applications/plot_thresholding.html

해당 사진처럼 임계값 방법으로 계곡 지점을 알아내어 좋은 결과물을 얻을 수도 있지만 히스토그램을 보고 자동으로 임계값을 알아내는 것은 생각보다 쉽지 않다.

 

곳곳에 산재해있는 작은 계곡이 방해 요인이 된다. 해당 사진처럼 히스토그램에 두개의 봉우리가 뚜렷하지 않은 영상도 많기 때문에 임계값을 하나로 찾아내기 애매한 경우가 많다.

 

오츄 알고리즘

오츄는 아주 효과적인 이진화 알고리즘을 제시했다. 현재에도 널리 사용되는 알고리즘이다.

임계값 t를 기준으로 화소를 두 집합으로 나누었을 때,

각 집합의 명암 분포가 균일할수록 좋다는 점에 착안하여 균일성이 클수록 t에게 높은 점수를 준다.

(임계값에 따라 나눈 각각의 봉우리의 명암 분포가 균일할 수록 더 선명한 이진화 영상을 얻을 수 있다.)

균일성은 그룹의 분산으로 측정하는데, 분산이 작을수록 균일성이 높다.

가능한 모든 t에 대해 계산한 후 가장 좋은 t를 최종 임계값으로 취한다.

 

일종의 최적화 알고리즘이다.

최적화 알고리즘에서 점수를 계산하는 데 사용하는 함수를 목적함수objective function or 비용 함수cost function라고 한다.

 

오츄 알고리즘에서는 위의 함수가 목적 함수 역할을 한다.

 

w는 임계값 t에 따라 생성된 흑 화소와 백 화소 집합의 크기로, 가중치 역할을 한다.
v는 임계값 t에 따라 나누어진 두 집합의 분산이다.

 

μ는 평균값을 의미한다.

w0과 w1은 임계값 t에 따라 생성된 흑 화소와 백 화소의 집합의 크기이다.

(0 ~ t까지의 집합 크기 / t + 1 ~ L - 1까지의 집합 크기)

그리고 해당 집합크기에 따른 평균 μ0과 μ1,

v0과 v1은 해당 두 집합의 분산이다.

 

해공간이 0, 1, 2, ... , L -1 인 L개의 점(1차원 공간) 중 1개의 임계값을 찾는 단순한 최적화 문제에 해당한다. 해당 문제에서 두 개의 가중치와 두 개의 분산을 L번 계산한다. 점근적 시간복잡도는 L²이 되는데, 더 빠르게 계산하는 방법이 있을까?

 

명암 범위 전체에 대한 평균과 분산을 사용하므로, 주어진 영상에 대해 한 번만 계산하면 되기때문에 상수로 간주할 수 있게 된다. 따라서 평균 μ와 분산 v를 영상에 대해 한 번에 계산한 식으로 정의하여, 위의 수식에 대입하여 유도하게 되면 아래와 같은 결과를 얻는다.

 

기존의 최소화 문제(각각 두 개의 분산을 최소화 시키는 것)를 최대화 문제(전체 분산을 최대화 시키는 것)로 바꾸어 쓸 수 있게 된다.

이렇게 문제를 바꾸게 되면, t라는 순간을 위해 계산해 놓은 값을 이용하여 다음 순간 t+1 값을 아래의 식을 이용하여 빠르게 계산할 수 있게 된다.

 

 

오츄 알고리즘 구현

int otsh_threshold = 0;
double inter_class_variance = 0;
double calcBinary[256];
Mat dst; // 사전에 정규화된 히스토그램 행렬

// 0 ~ 256 사이의 임계값 구하기
for (int threshold = 0; threshold < 256; threshold++) {
    int alpha = 0, beta = 0;
    int sum1 = 0, sum2 = 0;
    double avg1 = 0, avg2 = 0;

    // w0 계산 (0 ~ t까지의 누적합)
    for (int i = 0; i < threshold; i++)
        sum1 += calcBinary[i];

    // w1 계산 (t + 1 ~ L - 1까지의 누적합)
    sum2 = dst.rows * dst.cols - sum1;

    // w0과 w1의 가중치 구하기
    alpha = (double)sum1 / (double)calcBinary.size();
    beta = (double)sum2 / (double)calcBinary.size();

    // μ0과 μ1 구하기 (w0과 w1의 평균)
    for (int m = 0; m < threshold; m++)
        avg1 += (double)(m * calcBinary[m]) / (double)sum1;

    for (int m = threshold; m < 256; m++)
        avg2 += (double)(m * calcBinary[m]) / (double)sum2;

    // v0과 v1 구하기 (분산)
    double temp = alpha * beta * pow((avg1 - avg2), 2);

    // 가장 큰 V between(t)를 임계값 T로 취한다.
    if (inter_class_variance < temp) {
        inter_class_variance = temp;
        otsh_threshold = threshold;
    }
}

위의 알고리즘으로 만들어진 이진 영상에서 물체를 잘 인식할 수 있다면 해당 알고리즘이 잘 작동한다고 볼 수 있다. 그러나 일부 영상에서는 원하는 영역이 사라져보이기도 한다. 하나의 임계값만 사용하는 경우 이 현상은 불가피하기 때문에, 이를 해결하기 위해서 임계값을 k개 사용하여 k+1개의 구간으로 구분하는 다중 임계값 방법을 사용해야 한다.

 

또 다른 문제는 영상의 다른 지역이 상당히 다른 밝기 분포를 가지는 경우(EX. 영상 내에 그림자가 진 경우)에 발생한다. 이런 경우에는 하나의 임계값을 영상 전체에 적용하는 전역적인 방법이 아닌, 지역의 밝기 특성에 따라 서로 다른 임계값을 적용하는 적응적 이진화Adaptive thresholding 방법을 사용해야 한다.

 

2. 연결요소

화소는 어떤 모양일까?

프린터나 모니터와 같이 화소를 물리적으로 다루어야 하는 경우에는 모양이 중요하다.

하지만 컴퓨터 비전에서 화소는 추상적인 것에 불과하기에 가장 편리한 것을 선택해서 사용하면 된다. 육각형은 좌표를 지정하기 까다롭고 원은 빈 공간이 생기는 문제가 있다.

따라서 대부분의 문헌에서 사각형을 사용하고 있다.

화소의 이웃에 대해 생각해보자.

 

이웃화소

• 약한 이웃 화소 : NW, NE, SW, SE
• 강한 이웃 화소 : N, S, W, E

 

이처럼 4-연결성에서는 각 화소가 4개의 이웃 화소와 연결되어 있다고 간주한다.

8-연결성에서는 8개의 이웃 화소와 연결되어 있다고 간주한다.

이진 영상을 살펴보면 서로 연결된 화소의 집합이 여럿 나타나는데, 이들 집합 각각을 연결요소Connected component라고 부른다. 연결요소는 보통 별도로 다루기 때문에 이들 각각에 고유한 번호를 붙인 후 다음 처리 단계로 넘겨주어야 한다. (BFS 개념으로 Flood Fill 하는 개념인 것 같다.)

 

연결요소를 찾아 번호를 붙이려면 범람 채움Flood Fill 알고리즘을 사용한다.

(해당 범람 채움 알고리즘을 통해 그림판의 Paint 기능을 개발할 수 있다. 유사한 연결요소에 동일한 색상을 채워주는 것이다.)

 

DFS 개념으로 4연결성 버전을 구현하고자 한다면 다음과 같다.

// b(j, i) - 이진 영상
// I(j, i) - 결과 값(Flood Fill)

// I의 경계를 0으로, 내부는 -1로 설정해준다.

label = 1;
for(i = 1 to M - 2)
    for(i = 1 to N - 2) {
        if(I(j, i) = -1) { // 만약 I가 labeling 되지 않은 상태라면
            flood_fill4(I, j, i, label);
            label++; // 다음으로 번호로 넘어가기
    }
}

function flood_fill4(I, j, i, label) {
    if(I(j, i) = -1) {
        I(j, i) = label; // labeling 해준다.
        flood_fill4(I, j, i + 1, label); // 오른쪽
        flood_fill4(I, j - 1, i, label); // 위
        flood_fill4(I, j, i - 1, label); // 왼쪽
        flood_fill4(I, j + 1, i, label); // 아래
    }
}

재귀적으로 4방향을 labeling 하게 된다.

하지만 이 경우에, DFS를 사용하여 재귀적으로 채워나가기 때문에, 시스템 스택이 과도하게 쌓이게 되면 스택 오버플로우가 발생할 수 있다. 이를테면 모든 화면이 0으로 이루어진 연결요소라면 첫 방문 지점부터 가장 마지막 방문 지점까지 계속해서 재귀함수의 호출 스택이 쌓이게 되고, 스택 오버플로우가 나타날 가능성이 있다.

아래는 BFS 방식으로 범람 채움을 메모리 적게 사용하게 변경한 것이다.

 

// b(j, i) - 이진 영상
// I(j, i) - 결과 값(Flood Fill)

// I의 경계를 0으로, 내부는 -1로 설정해준다.

label = 1;
for(i = 1 to M - 2)
    for(i = 1 to N - 2) {
        if(I(j, i) = -1) { // 만약 I가 labeling 되지 않은 상태라면
            efficient_floodfill4(I, j, i, label);
            label++; // 다음으로 번호로 넘어가기
    }
}

function efficient_floodfill4(I, j, i, label) {
    Queue que;
    que.push(j, i);
    while (!que.empty()) {
        (y, x) = que.pop();
        if (I(y, x) == -1) {
            left = right = x;
            while(I(y, left - 1) = -1) left--; // 인접 왼쪽 중 labeling 되지 않은 경우
            while(I(y, right + 1) = -1) right++; // 인접 오른쪽 중 labeling 되지 않은 경우
        for (c = left to right) {
            I(y, c) = label;
            // 인접 위쪽 중 labeling 되지 않은 경우
            if (I(y - 1, c) = -1 && (c = left or I(y - 1, c - 1) != -1)
                que.push(y - 1, c);
            // 인접 아래쪽 중 labeling 되지 않은 경우
            if (I(y + 1, c) = -1 && (c = left or I(y + 1, c - 1) != -1)
                que.push(y + 1, c);
        }
    }
}