Geometry & Recognition

이미지에서 물체를 인식할 때 물체의 윤곽 정보는 매우 중요한 역할을 한다. 이 윤곽 정보는 보통의 경우 에지를 검출한 후 적절한 영상처리를 거쳐서 단일 픽셀의 선으로 표현된다. 그러나 이렇게 만든 윤곽선은 불필요하게 많은 점으로 구성이 되어 있는 경우가 많으므로, 실제 결과를 사용할 때 적당한 길이의 직선으로 연결된 폴리 라인(polyline)으로 근사를 하여 사용한다. 이 경우 윤곽선의 연접한 점들을 어디까지 직선으로 판단할 것인가에 대한 문제가 생긴다. 

이에 대한 한 가지 접근법은 먼저 윤곽선의 처음과 끝점을 잇는 선분을 만들고 사이의 점들이 이 선분에서 벗어난 정도를 조사한다. 최대로 벗어난 윤곽선의 점이 폴리 라인의 새 꼭짓점이 되고 그 꼭짓점을 기준으로 이전 선분을 두 개로 분할한다. 다시 분할된 두 선분에 대해서 같은 작업을 시행하여 더 이상 작은 선분으로의 분할이 없을 때까지 반복하는 것이다. 이 방법은 잘 알려진 Douglas-Peucker 알고리즘이다. 

두 번째 방법은 윤곽선의 처음 점에서 시작하는 직선의 끝점의 위치를 윤곽선을 따라 순차적으로 옮겨가면 선분을 만들고, 사이의 점들이 이 선분에서 너무 멀리 떨어지지 않는가를 체크한다. 선분에서 너무 벗어난 점이 있으면, 바로 직전의 윤곽선 점을 꼭짓점으로 분류한 후 이 꼭짓점에서 시작하는 선분을 앞에서와 같은 방식으로 만들어서 다음 꼭짓점 후보를 찾는다. DP 알고리즘이 분할에 기반한 것이라면, 이 방법은 점들의 합병(merging)에 기반한 알고리즘이다. 두 알고리즘 모두 재귀적으로 구현할 수 있다. 아래 그림은 DP-알고리즘(Green Line)과 merge-알고리즘 (Blue Line)을 동시에 비교한 것이다.

거리-tolerance를 10씩 증가시키면(점점 단순해진다) 두 알고리즘을 적용하여 본 결과:

// mark는 새로운 꼭지점의 후보를 기록한다(1=꼭짓점, 0=아님)
// mark[0] = mark[end_idx] = 1;
// end = size(v) - 1: not changing;
void mergeSimplication(double tolerance, int start, int end, std::vector<CfPt>& v, 
                       std::vector<int>& mark) 
{
    if (end <= start + 1) return ; //at least 3 ;
    int k = start + 2;
    for (;k <= end; k++) {
        double dist_max = 0;
        for (int i = start+1 ; i < k; i++) {
            // distance to a segment(v[start], v[k]) from v[i];
            double dist = distance2Segment(v[start], v[k], v[i]);
            if (dist_max < dist) dist_max = dist;
        }
        if (dist_max > tolerance) break; 
    } 
    // 정상적으로 끝나면 k==end + 1;
    if (k <= end) {
        //k 에서 tolerance을 넘었으므로 새로운 vertex은 k-1;
        mark[k-1] = 1; // new_vertex;
        mergeSimplication(tolerance, k-1, end, v, mark);
    }
    return;
};

// distance2Segment()는 한 점에서 선분까지 거리를 구하는 함수;
// distantance tolerance 이내에 근접한 이웃점들은 미리 제외시킨 후 알고리즘을 적용한다.