728x90

영상에서 추출한 객체(object)의 경계선은 객체의 모양에 대한 많은 정보를 담고 있지만, 어떤 경우에는 불필요하게 많은 정보가 될 수도 있다. 이 경우 원래의 경계를 충분히 닮은 다각형으로 간략화하여서 불필요한 정보를 제거할 수 있다. 이 다각형으로의  근사가  물체의 경계를 얼마나 제대로 표현할 수 있는지에 대한 기준이 있어야 한다. N개의 점 $\{(x_i, y_i) | i = 1... N\}$으로 표현된 경계가 있다고 하자. 가장 단순한 근사는 가장 멀리 떨어진 두 점(A, B)으로 만들어진 선분일 것이다(선분의 길이가 대략적인 물체의 크기를 주고, 선분 방향이 물체의 orientation을 알려준다). 이 선분을 기준으로 다시 가장 멀리 떨어진 점(C)을 찾아서 일정 거리 이상 떨어져 있으면 꼭짓점으로 추가하여 두 개의 선분으로 분할한다. 두 개의 선분에 대해서 동일한 분할 작업을 재귀적으로 반복하므로 좀 더 정밀하게 물체를 표현하는 다각형을 찾을 수 있다. 선분에서 가장 멀리 떨어진 지점이 기준 거리 이내이면 분할을 멈춘다. 닫힌 다각형 근사일 때는 시작점 = 끝점으로 조건을 부여하면 된다.

** open polyline으로 우리나라 경계를 단순화시키는 예: top-right 쪽이 시작과 끝이므로 simplication 과정에서 변화지 않는다.

// distance square from (x, y) to the line segment AB ;

double pt2SegDist2(int x, int y, CPoint A, CPoint B) ;

더보기
double pt2SegDist2(int x, int y, CPoint A, CPoint B) {
    double dx = B.x - A.x, dy = B.y - A.y ;
    double lenAB2 = dx * dx + dy * dy ;
    double du = x - A.x, dv = y - A.y ;
    if (lenAB2 == 0.) return du * du + dv * dv;
    double dot = dx * du + dy * dv ; 
    if (dot <= 0.) return du * du + dv * dv;
    else if (dot >= lenAB2) {
        du = x - B.x; dv = y - B.y;
        return return du * du + dv * dv;
    } else {
        double slash = du * dy - dv * dx ;
        return slash * slash / lenAB2;
    }
};

//  재귀 호출을 이용한 Douglas-Peucker 알고리즘;

void DouglasPeucker(double tol, CPoint vtx[], int istart, int iend, int mark[]) {
    if (iend <= istart + 1) return; //종료 조건;
    // vtx[istart] to vtx[iend]을 잇는 선분을 기준으로 분할점을 찾음;
    int ibreak = istart;			// 선분에서 가장 먼 꼭짓점;
    double maxdist2 = 0.0;
    double tolsq = tol * tol;		
    for (int i = istart + 1; i < iend; i++) {
        double dist2 = pt2SegDist2(vtx[i].x, vtx[i].y, vtx[istart], vtx[iend]);
        if (dist2 <=  maxdist2) continue;
        ibreak = i;
        maxdist2 = dist2;
    } 
    if (maxdist2 > tolsq) {		// 가장 먼 꼭짓점까지 거리가 임계값을 넘으면 => 분할;
        mark[ibreak] = 1;		// vtx[ibreak]를 마킹;
        // vtx[ibreak] 기준으로 좌/우 polyline을 분할시도;
        DouglasPeucker(tol, vtx, istart, ibreak, mark);
        DouglasPeucker(tol, vtx, ibreak, iend, mark);
    }
    return;
};

// driver routine;

int polySimplify(double tol, std::vector <CPoint>& V, std::vector <CPoint>& out );

더보기
int polySimplify(double tol, std::vector <CPoint>& V, std::vector <CPoint>& out) {
    if (V.size() < 2) return 0;    
    std::vector<int> mark(V.size(), 0); // 꼭짓점 마킹용 버퍼;
    // DP-알고리즘 호출 전에 너무 가까이 붙어있는 꼭짓점을 제거하면 보다 빠르게 동작하게 만들 수 있다;
    mark[0] = mark[V.size() - 1] = 1;   // 처음과 끝은 marking;
    DouglasPeucker( tol, &V[0], 0, V.size() - 1, &mark[0] );
    // save marked vertices;
    out.clear();    
    for (int i = 0; i < V.size(); i++)
        if (mark[i]) out.push_back(V[i]);
    return out.size();
}
Posted by helloktk

댓글을 달아 주세요