Bezier Curve을 이용한 Histogram Smoothing

히스토그램은 영상에서 각 그레이 레벨에 해당하는 픽셀의 개수를 나타내는 이산적인 함수(discrete function)로 볼 수 있다. 히스토그램의 피크 위치는 영상의 명암 분포를 분석하거나, 히스토그램을 여러 개의 그룹으로 분할하는 과정에서 중요한 정보를 제공한다.

그러나 영상으로부터 얻은 히스토그램은 양자화와 잡음의 영향으로 인해 인접한 그레이 레벨 사이에서 불규칙하게 변하는 경우가 많다. 따라서 피크를 안정적으로 검출하기 위해서는 먼저 mean filter나 Gaussian filter와 같은 저역통과(low-pass) 필터를 이용하여 히스토그램을 평활화한 후 사용하는 것이 일반적이다.

여기서는 이러한 저역통과 필터를 사용하는 대신, 히스토그램의 bin 인덱스와 bin 값을 제어점(control point)으로 하는 하나의 Bezier 곡선을 이용하여 히스토그램을 매끄러운 연속 곡선으로 근사하는 방법을 살펴본다. 그레이 레벨이 256단계인 영상에서는 제어점이 256개이므로 하나의 255차 Bezier 곡선이 생성된다. 실제 영상 처리에서는 이처럼 높은 차수의 Bezier 곡선을 사용하는 경우는 드물지만, 히스토그램 전체를 하나의 연속적인 곡선으로 근사하는 방법으로 생각할 수 있다. 이렇게 얻은 곡선은 원래의 히스토그램보다 훨씬 매끄러운 형태를 가지므로 피크의 위치를 보다 안정적으로 찾을 수 있다.

일반적으로 높은 차수의 Bezier 곡선을 Bernstein 다항식을 이용하여 직접 계산하면 매우 큰 이항계수와 부동소수점 연산으로 인해 overflow, underflow 및 round-off error와 같은 수치적인 문제가 발생할 수 있다. 따라서 이러한 경우에는 Bernstein 다항식을 직접 계산하는 대신, 수치적으로 안정한 De Casteljau 알고리즘을 이용하여 Bezier 곡선의 점들을 반복적으로(iteratively) 계산하는 것이 일반적이다.

// De Casteljau's algorithm (degree:=size(Q)-1)
double Bezier(int deg, double Q[], double t) {
    for (int k = 0; k < deg; k++)
        for (int j = 0; j < (deg - k); j++)
            Q[j] = (1 - t) * Q[j] + t * Q[j + 1];
    return Q[0];
}

void SmoothenHistogram (int hist[], int numLevels/* =256 */) {
    std::vector<double> p(numLevels);
    std::vector<int> hist2(numLevels);
    // cloning;
    for (int j = 0; j < numLevels; j++) hist2[j] = hist[j];
    for (int j = 0; j < numLevels; j++) {
        double t = double(j) / (numLevels - 1);
        // control points {p}; calling of Bezier() modifies p's;
        for (int i = 0; i < numLevels; i++) 
            p[i] = hist2[i];
        hist[j] = int(Bezier(numLevels-1, &p[0], t) + 0.5);
    }
};

data=violet,  smoothed=green;

Bezief curve 위키피디아: http://en.wikipedia.org/wiki/B%C3%A9zier_curve