Geometry & Recognition

Input = a set S of n points 
    Assume that there are at least 2 points in the input set S of points
QuickHull (S) { 
    // Find convex hull from the set S of n points
    Convex Hull := {} 
    가장 왼쪽(A)과 오른쪽(B)에 있는 두 점을 찾아 convec hull에 추가;
    선분 AB을 기준으로 나머지 (n-2)개 점들을 두 그룹 S1과 S2로 나눔;
        S1 = 선분 AB의 오른쪽에 놓인 점; 
        S2 = 선분 BA의 오른쪽에 놓인 점;
    FindHull (S1, A, B) 
    FindHull (S2, B, A) 
};
FindHull (Sk, P, Q) { 
   If Sk has no point, 
        then  return. 
   선분 PQ에서 가장 멀리 떨어진 점(C)을 찾아 convex hull에서 P와 Q의 사이에 추가;
   세점 P, C, Q는 나머지 Sk의 나머지 점들을 세 그룹S0, S1, and S2 
        S0 = 삼각형 PCQ에 포함되는 점;
        S1 = 선분 PC의 오른쪽에 놓인 점;
        S2 = 선분 CQ의 오른쪽에 놓인 점; 
    FindHull(S1, P, C) 
    FindHull(S2, C, Q) 
}
Output = convex hull

참고: http://www.cse.yorku.ca/~aaw/Hang/quick_hull/Algorithm.html

// P가 line(A, B)의 완전히 왼쪽에 있는가?

static bool leftSide(CPoint P, CPoint A, CPoint B) ;

static bool leftSide(CPoint P, CPoint A, CPoint B) {
   int ax = P.x - A.x,  ay = P.y - A.y;
   int bx = B.x - A.x,  by = B.y - A.y;
   return (ax * by - ay * bx) >= 0;
};

double dist2ToLine(CPoint P, CPoint A, CPoint B);

double dist2ToLine(CPoint P, CPoint A, CPoint B) {
    double dx = (B.x - A.x), dy = (B.y - A.y);
    double den = (dx * dx + dy * dy);
    if (den == 0.) return 0; //degenerate;
    double du = (P.x - A.x), dv = (P.y - A.y);
    double dist = (du * dy - dv * dx);
    return dist * dist / den; //distance-square!
};

#define SWAP_POINT(A, B)

static void findHull(CPoint *S, int n, CPoint A, CPoint B, std::vector <CPoint>& hull) ;

static void findHull(CPoint *S, int n, CPoint A, CPoint B, std::vector<CPoint>& hull) {
    if (n < 1) return ;
    //Find furtherst point 
    double maxdist = 0;
    for (int i = 0; i < n; i++) {
        double dist = dist2ToLine(S[i], A, B);
        if (dist > maxdist) {
            SWAP_POINT(S[0], S[i]);
            maxdist = dist;
        }
    }
    if (maxdist == 0.) return ; //collinear case;
    hull.push_back(S[0]);
    int j = 1;
    for (int i = 1; i < n; i++) {
        if (leftSide(S[i], A, S[0])) {
            SWAP_POINT(S[i], S[j]);
            j++;
        };
    };
    int k = j;
    for (int i = j; i < n; i++) {
        if (leftSide(S[i], S[0], B)) {
            SWAP_POINT(S[i], S[k]);
            k++;
        }
    };
    //1,...,j-1;
    findHull(&S[1], j-1, A, S[0], hull);
    //j,...,k-1;
    findHull(&S[j], k-j, S[0], B, hull);
};

void findMaxMin(std::vector<CPoint>& pts) ;

void findMaxMin(std::vector<CPoint>& pts) {
    int minx = pts[0].x, maxx = minx;
    int minid = 0, maxid = 0;
    for (int i = pts.size(); i-->1;) {
        if (pts[i].x > maxx) maxid = i, maxx = pts[i].x;
        if (pts[i].x < minx) minid = i, minx = pts[i].x;
    }
    SWAP_POINT(pts[0], pts[minid]); if (maxid == 0) maxid = minid;
    SWAP_POINT(pts[1], pts[maxid]);
};

void hullToPolyline(std::vector<CPoint>& hull);

void quickHull(std::vector<CPoint>& pts, std::vector<CPoint>& hull) {
    if (pts.size() < 3) return;
    hull.clear();
    //Find left and right most points, say A & B, and add A & B to convex hull ;
    findMaxMin(pts);
    hull.push_back(pts[0]);
    hull.push_back(pts[1]);
    int j = 2;
    for (int i = 2; i < pts.size(); i++) {
        if (leftSide(pts[i], pts[0], pts[1])) {
            SWAP_POINT(pts[i], pts[j]);
            j++;
        }
    }
    //2,3,...,j-1;
    findHull(&pts[2], j-2, pts[0], pts[1], hull);
    //j,j+1,...,pts.size()-1;
    if (j < pts.size()) // in order to avoid dereferencing &pts[pts.size()];
        findHull(&pts[j], pts.size()-j, pts[1], pts[0], hull);
    hullToPolyline(hull);
};

출력 hull은 단순히 convex hull을 구성하는 정렬이 안된 점들만 주므로, hull의 에지를 구하고 싶으면 추가적인 수정이 필요함.

static int cmph(const void *a, const void *b) {
    CPoint *A = (CPoint *)a , *B = (CPoint *)b ;
    int v = (A->x - B->x) ;
    if (v > 0 ) return 1;
    if (v < 0 ) return -1;
    v = B->y - A->y ;
    if (v > 0 ) return 1;
    if (v < 0 ) return -1;
    return 0;
};
static int cmpl(const void * a, const void *b) {
    return cmph(b, a);
};
void hullToPolyline(std::vector<CPoint>& hull) {
    CPoint A = hull[0];
    CPoint B = hull[1];
    // 가장 멀리 떨어진 두 점(hull[0], hull[1])을 연결하는 직선을 기준으로 프로젝션을 구하여서 순차적으로 
    int k = 2;
    for (int i = 2; i < hull.size(); i++) {
        if (leftSide(hull[i], A, B)) {
            SWAP_POINT(hull[i], hull[k]); k++;
        };
    };
    // k-1; last index of hull left side of line(A,B);
    // upper part reordering: 
    qsort(&hull[0], k, sizeof(CPoint), cmph);
    //lower part reordering;
    if (k < hull.size())
        qsort(&hull[k], hull.size()-k, sizeof(CPoint), cmpl);
    }
};

또한 입력점들의 순서를 그대로 유지하고 싶으면, double pointer를 이용하거나 복사복은 이용하여야 한다.

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

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

// distance square from P to the line segment AB ;

double pt2SegDist2(CPoint P, CPoint A, CPoint B) ;

// P에서 두 점 A, B을 연결하는 선분까지 거리
double pt2SegDist2(CPoint P, CPoint A, CPoint B) {
    double dx = B.x - A.x, dy = B.y - A.y ;
    double lenAB2 = dx * dx + dy * dy ;
    double du = P.x - A.x, dv = P.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 = P.x - B.x; dv = P.y - B.y;
        return du * du + dv * dv;
    } else {
        double slash = du * dy - dv * dx ;
        return slash * slash / lenAB2;
    }
};

//  recursive Douglas-Peucker 알고리즘;

void DouglasPeucker(double tol, std::vector<CPoint>& vtx, int start, int end, 
                   std::vector<bool>& mark) {
    if (end <= start + 1) return; //종료 조건;
    // vtx[start] to vtx[end]을 잇는 선분을 기준으로 분할점을 찾음;
    int break_id = start;			// 선분에서 가장 먼 꼭짓점;
    double maxdist2 = 0;
    const double tolsq = tol * tol;		
    for (int i = start + 1; i < end; i++) {
        double dist2 = pt2SegDist2(vtx[i], vtx[start], vtx[end]);
        if (dist2 <=  maxdist2) continue;
        break_id = i;
        maxdist2 = dist2;
    } 
    if (maxdist2 > tolsq) {		// 가장 먼 꼭짓점까지 거리가 임계값을 넘으면 => 분할;
        mark[break] = true;		// vtx[break_id]를 유지;
        // vtx[break_id] 기준으로 좌/우 polyline을 분할시도;
        DouglasPeucker(tol, vtx, start, break_id, mark);
        DouglasPeucker(tol, vtx, break_id, end, mark);
    }
};

// driver routine;

int polySimplify(double tol, std::vector <CPoint>& V, std::vector <CPoint>& decimated) {
    if (V.size() < 2) return 0;    
    std::vector<bool> mark(V.size(), false); // 꼭짓점 마킹용 버퍼;
    // 알고리즘 호출 전에 너무 붙어있는 꼭짓점을 제거하면 보다 빠르게 동작;
    // 폐곡선이 아닌 경우 처음,끝은 marking; 
    // 폐곡선은 가장 멀리 떨어진 두점중 하나만 해도 충분;
    mark.front() = mark.back() = true; 
    DouglasPeucker( tol, V, 0, V.size()-1, mark );
    // save marked vertices;
    decimated.clear();    
    for (int i = 0; i < V.size(); i++)
        if (mark[i]) decimated.push_back(V[i]);
    return decimated.size();
}

nonrecursive version:

// nonrecursive version;
int DouglasPeucker_nonrec(double tol, std::vector<CPoint>& points,
                            std::vector<CPoint>& decimated) {
    if (points.size() <= 2) return;
    double tol2 = tol * tol; //squaring tolerance;
    // 미리 가까이 충분히 가까이 있는 꼭지점은 제거하면 더 빨라짐;
    std::vector<CPoint> vt;
    vt.push_back(points.front()) ;  // start at the beginning;
    for (int i = 1, pv = 0; i < points.size(); i++) {
        int dx = points[i].x - points[pv].x, dy = points[i].y - points[pv].y;
        double dist2 = dx * dx + dy * dy ;
        if (dist2 < tol2) continue;
        vt.push_back(points[i]); 
        pv = i; // 다시 거리를 재는 기준점;
    }
    if (vt.back()!=points.back()) vt.push_back(points.back());  // finish at the end
    points.swap(vt);
    //
    std::vector<bool> mark(points.size(), false); // vertices marking
    std::vector<int> stack(points.size());  // 분할된 라인 처음-끝 저장;
    // 폐곡선이 아닌 경우 처음,끝은 marking; 
    // 폐곡선은 가장 멀리 떨어진 두점 중 하나만 해도 충분
    mark.front() = mark.back() = true;
    int top = -1;
    // 분할 해야할 폴리라인의 양끝점을 스택에 넣음;
    stack[++top] = 0;
    stack[++top] = points.size() - 1;
    while (top >= 0) {
        // 분할을 시도할 구간의 두 끝점을 꺼냄;
        int end = stack[top--];
        int start = stack[top--];
        // 최대로 멀리 떨어진 점;
        double max_distance2 = 0;
        int break_id = -1;
        for (int i = start + 1; i < end; i++) {
            double dsq = pt2SegDist2(points[i], points[start], points[end]);
            if (dsq > max_distance2) {
                max_distance2 = dsq;
                break_id = i;
            }
        }
        // 주어진 임계값 이상 떨어졌으면 꼭지점을 유지하도록 표시;
        if (max_distance2 > tol2) {
            mark[break_id] = true;       
            // 주어진 꼭지점을 기준으로 양쪽을 다시 검사하기 위해 스택에 쌓음;
            stack[++top] = start;
            stack[++top] = break_id;
            stack[++top] = break_id;
            stack[++top] = end;
        }
    }
    // marking 된 꼭지점을 출력;
    decimated.clear();
    for (int i = 0; i < points.size(); i++)
        if (mark[i]) decimated.push_back(points[i]);
    return decimated.size();
}

이미지에서 물체를 인식할 때 물체의 윤곽 정보는 매우 중요한 역할을 한다. 이 윤곽 정보는 보통의 경우 에지를 검출한 후 적절한 영상처리를 거쳐서 단일 픽셀의 선으로 표현된다. 그러나 이렇게 만든 윤곽선은 불필요하게 많은 점으로 구성이 되어 있는 경우가 많으므로, 실제 결과를 사용할 때 적당한 길이의 직선으로 연결된 폴리 라인(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 이내에 근접한 이웃점들은 미리 제외시킨 후 알고리즘을 적용한다.